Is there a algorithm which can calculate matrix multiply? H!

[wufei]

Is there a algorithm which can calculate matrix multiply?
How can I optimize matrix multiply, such as A mults B.
A is a NxN matrix, so is B.
And each element of these matrices is a M-bit data which consist of integeral part and decimal part.
I want to implement this function using verilog.
forgive my ugly sentences

 

[shavakmm]

Re: Is there a algorithm which can calculate matrix multiply

systolic array method is good one especially for matrix multiplication...!

please see below posts:



https://asic-soc.blogspot.com/2007/06/matrix-multiplier-design-and-synthesis.html
https://asic-soc.blogspot.com/2007/10/verilog-code-for-systolic-array-matrix.html

 

[niuniu]

Is there a algorithm which can calculate matrix multiply?

depend on how fast your want, and how many resource the chip can afford.

 

[wufei]

当然是越快越好了,
目前还不要考虑资源,因为还没实现啊
现在关键是这个矩阵乘法的计算量好大

Added after 1 minutes:

faster better
i think an appropriate algorithm is the key

 

[master_picengineer]

Thats simple lot of algorithms are available in C language or Matlab you have only to translate them in Verilog.
Or use a C to Verilog converter tool if you are not familiar with C.

 

[kelvin_sg]

Re: Is there a algorithm which can calculate matrix multiply

当然是越快越好了,
目前还不要考虑资源,因为还没实现啊
现在关键是这个矩阵乘法的计算量好大

Added after 1 minutes:

faster better
i think an appropriate algorithm is the key

You write chinese here?

Have you studied the characteristics of the matrix, chances are you can optimize them.. FFTs and DCTs are the prettiest examples of such optimization.

 

[flyalone]

#ifndef matrix_h_
#define matrix_h_

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef void (* FCREATEPEER)(float *pData, float *pPeer0, float *pPeer1);

class CMatrix
{
private:

int row;
int column;
float *data;

public:

CMatrix();
CMatrix(CMatrix &matrix);
CMatrix(int row, int column);
template <class T>CMatrix(T *matrix, int row, int column)
{
int i, j, index;

if (row > 0 && column > 0)
{
this->row = row;
this->column = column;

data = (float *)malloc(sizeof(float) * row *column);
if (data)
{
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
data[index + j] = (float)matrix[index + j];
}
}
}
}

~CMatrix();

// free space holded by matrix
// parameter
//
// return
//
void Free()
{
if (data)
{
row = 0;
column = 0;

free(data);
}

return ;
}
// instantiation matrix
// parameter
// matrix point to a matrix whose size is row X column
// (row column) size of matrix
// return
//
template <class T>void Instantiation(T *matrix, int row, int column)
{
int i, j, index;

if (row > 0 && column > 0)
{
Free();

this->row = row;
this->column = column;

data = (float *)malloc(sizeof(float) * row *column);
if (data)
{
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
data[index + j] = (float)matrix[index + j];
}
}
}

return ;
}
// add a row vector to matrix and get a new matrix
// parameter
// matrix point to a row vector whose has n elements
// n number of elements
// return
// 0 when has no-error
// 1 when parameters illegal
// 2 when memory allocate error
// 3 when ...
template <class T> int AddRowVector(T *matrix, int n)
{
int i;
float *ptr;

if (row == 0 && column == 0)
{
if (!matrix || n <= 0)
return 1;

row = 1;
column = n;
data = (float *)malloc(sizeof(float) * row * column);
if (!data)
return 2;
for (i = 0; i < n; i++)
data = (float)matrix;

return 0;
}

if (!matrix || n != column)
return 1;

ptr = (float *)malloc(sizeof(float) * (row + 1) * column);
if (!ptr)
return 2;

memcpy(ptr, data, sizeof(float) * row * column);
free(data);
data = ptr;

ptr = ptr + row * column;
for (i = 0; i < n; i++)
ptr = (float)matrix;

row += 1;

return 0;
}
// add a column vector to matrix and get a new matrix
// parameter
// matrix point to a column vector whose has n elements
// n number of elements
// return
// 0 when has no-error
// 1 when parameters illegal
// 2 when memory allocate error
// 3 when ...
// template <class T>
int AddColVector(float *matrix, const int n)
{
int i, j, indexS, indexD;
float *ptr;

if (row == 0 && column == 0)
{
if (!matrix || n <= 0)
return 1;

row = n;
column = 1;
data = (float *)malloc(sizeof(float) * row * column);
if (!data)
return 2;

for (i = 0; i < n; i++)
data = (float)matrix;

return 0;
}

if (!matrix || n != row)
return 1;

ptr = (float *)malloc(sizeof(float) * row * (column + 1));
if (!ptr)
return 2;

for (i = 0; i < row; i++)
{
indexD = i * (column + 1);
indexS = i * column;

for (j = 0; j < column; j++)
ptr[indexD + j] = data[indexS + j];

ptr[indexD + j] = matrix;
}
free(data);
data = ptr;
column += 1;

return 0;
}
///////////////////////////////////////////////////////////////////////////////////

CMatrix operator =(const CMatrix B)
{
int i, j, index;

Free();

row = B.row;
column = B.column;
data = (float *)malloc(sizeof(float) * row *column);
if (data)
{
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
data[index + j] = B.data[index + j];
}
}

return *this;
}
CMatrix operator *(float m)
{
int i, j, index;

if (data)
{
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
data[index + j] = data[index + j] * m;
}
}

return *this;
}
template <class T> CMatrix operator /(T m)
{
int i, j, index;

if (data && m)
{
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
data[index + j] = (float) (data[index + j] / m);
}
}

return *this;
}
///////////////////////////////////////////////////////////////////////////////////
void Display()
{
int i, j, index;

if (data)
{
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
printf("%-10.5lf ", data[index + j]);

printf("\n");
}
} else
printf("matrix is NULL...\n");

return;
}
///////////////////////////////////////////////////////////////////////////////////
int Transpose();

int ReSize(int row, int column);

int Size(int row, int column);
int Size(int *prow, int *pcolumn);
float *Data();

CMatrix operator +(const CMatrix &A);
CMatrix operator -(const CMatrix &A);
CMatrix operator *(const CMatrix &A);

// create a peer from a setted matrix using some method such as a linear transform

friend int CreatePeer(CMatrix &SrcMatrix, CMatrix &A, CMatrix &B, FCREATEPEER fCreatePeer);
} ;


#endif //


#include "matrix.h"

#include <string.h>
#include <stdio.h>
#include <math.h>
//---------------------------------------------------------------------------------------

// constructor
// parameter
// matrix a matrix
// row number of rows
// column number of columns
// return
//
CMatrix::CMatrix(CMatrix &matrix)
{
int i, j, index;

row = matrix.row;
column = matrix.column;

data = (float *)malloc(sizeof(float) * row *column);
if (data)
{
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
data[index + j] = matrix.data[index + j];
}
}
}
//---------------------------------------------------------------------------------------

CMatrix::CMatrix(int row, int column)
{
int size;

this->row = row;
this->column = column;

size = row * column;
if (size > 0)
{
data = (float *)malloc(sizeof(float) * row *column);
memset(data, 0, sizeof(float) * row *column);
}
else
data = NULL;
}
//---------------------------------------------------------------------------------------

CMatrix::CMatrix()
{
row = 0;
column = 0;
data = NULL;
}
//---------------------------------------------------------------------------------------

CMatrix::~CMatrix()
{
if (data)
free(data);
}
//---------------------------------------------------------------------------------------

// transpose matrix
// parameter
//
// return
// 0 when transpose successful
// -1 when data in matrix is illegal
// -2 when memory allocate error
int CMatrix::Transpose()
{
float *element;
int i, j;

if (row <= 0 || column <= 0 || !data)
return -1;

element = (float *)malloc(sizeof(float) * row * column);
if (!element)
return -2;

for (i = 0; i < column; i++)
for (j = 0; j < row; j++)
element[i * row + j] = data[j * column + i];

i = row;
row = column;
column = i;

free(data);
data = element;

return 0;
}
//---------------------------------------------------------------------------------------

// re-set the size of matrix
// parameter
// row the number of rows in new matrix
// column the number of columns in new matrix
int CMatrix::ReSize(int row, int column)
{
int size;

size = this->row * this->column;
if (size != row * column)
return -1;

if (size)
{
this->row = row;
this->column = column;
}

return 0;
}
//---------------------------------------------------------------------------------------

// set a matrix's size
// parameter
// row number of rows
// column number of columns
// return
// 0 when O.K.
// 1 when memory allocate error
int CMatrix::Size(int row, int column)
{
int size;

if (this->row || this->column)
if (data)
free(data);
this->row = row;
this->column = column;

size = row * column;
if (size)
{
data = (float *)malloc(sizeof(float) * row *column);
if (!data)
return 1;
memset(data, 0, sizeof(float) * row *column);
}
else
data = NULL;

return 0;
}
//---------------------------------------------------------------------------------------

// get size of matrix
// parameter
// prow point to number of rows
// pcolumn point to number of columns
// return
// 0 when O.K.
// 1 when parameters illegal
int CMatrix::Size(int *prow, int *pcolumn)
{
if (!prow || !pcolumn)
return 1;

*prow = row;
*pcolumn = column;

return 0;
}
//---------------------------------------------------------------------------------------

// get point to data field of matrix
// parameter
//
// return
// point to data field of matrix
// NULL
float *CMatrix:ata()
{
return data;
}
//---------------------------------------------------------------------------------------

CMatrix CMatrix:perator +(const CMatrix &A)
{
CMatrix C;
int i, j, index;

if (row == 0 && column == 0)
{
C.Size(A.row, A.column);
for (i = 0; i < A.row; i++)
{
index = i * A.column;

for (j = 0; j < A.column; j++)
C.data[index + j] = A.data[index + j];
}

return C;
} else if (A.row != row || A.column != column)
return C;

C.Size(row, column);
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
C.data[index + j] = A.data[index + j] + data[index + j];
}

return C;
}
//---------------------------------------------------------------------------------------

CMatrix CMatrix:perator -(const CMatrix &A)
{
CMatrix C;
int i, j, index;

if (A.row != row || A.column != column)
return C;

C.Size(row, column);
for (i = 0; i < row; i++)
{
index = i * column;

for (j = 0; j < column; j++)
C.data[index + j] = data[index + j] - A.data[index + j];
}

return C;
}
//---------------------------------------------------------------------------------------

CMatrix CMatrix:perator *(const CMatrix &A)
{
CMatrix C;
int i, j, k, index;

if (column != A.row)
return C;

C.Size(row, A.column);
for (i = 0; i < row; i++)
{
index = i * A.column;

for (j = 0; j < A.column; j++)
{
C.data[index + j] = 0.0f;

for (k = 0; k < column; k++)
C.data[index + j] += data[i * column + k] * A.data[k * A.column + j];

}
}

return C;
}
//---------------------------------------------------------------------------------------

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

// create a peer from a setted matrix using some method such as a linear transform
// parameter
// SrcMatrix the reference of source image
// (A, B) the peer of image which is obtained using some transform
// fCreatePeer the point of a transform
// return
// 0 when there is no error
// -1 when the parameters are error
// -2 when ...
int CreatePeer(CMatrix &SrcMatrix, CMatrix &A, CMatrix &B, FCREATEPEER fCreatePeer)
{
int row, column, size;
int x, y, index;
int ReCode;

SrcMatrix.Size(&row, &column);
size = row * column;
if (size <= 0)
return -1;

ReCode = A.Size(row, column);
if (ReCode)
return -2;
ReCode = B.Size(row, column);
if (ReCode)
{
A.Size(0, 0);
return -3;
}

for (y = 0; y < row; y++)
{
index = y * column;
for (x = 0; x < column; x++)
{
index += x;

fCreatePeer(SrcMatrix.data + index, A.data + index, B.data + index);

index -= x;
}
}

return 0;
}
//------------------------------------------------------------------------------------------

 

[wufei]

so ........... good!
thanks , i'll try it