Strassen Matrix Multiplication source code
The attached zip archive has the serial source files for Strassen's Algorithm as well as the standard Matrix Multiplication algorithm. Use this code as a starting point for your submission to the first problem in the Phase 2 part of the Intel Threading Challenge Contest 2009.
The code was developed under Windows, so Linux users may need to adjust the include files (or use better ones).
--clay
| |
Re: Strassen Matrix Multiplication source code
The attached zip archive has the serial source files for Strassen's Algorithm as well as the standard Matrix Multiplication algorithm. Use this code as a starting point for your submission to the first problem in the Phase 2 part of the Intel Threading Challenge Contest 2009.
The code was developed under Windows, so Linux users may need to adjust the include files (or use better ones).
--clay
Can we just thread this code or are we supposed to bring a completely new implementation to the table?
| |
Re: Strassen Matrix Multiplication source code
In the problem description and the above post I'm reading language such as "This source file should be used as a starting point. Your entry should keep the body of the main function, the matrix generation function, the sequential multiplication code, and the function to compare the two matrix product results."
I'm reading this as: implement Strassen's Algorithm as I see fit; but dont change the code for:
- main()
- seqMatMult()
- CheckResults()
Is this correct?
| |
Re: Strassen Matrix Multiplication source code
M, N, P must be 2 ^ n? Their range is how much? thanks！
写字楼里写字间,写字间里程序员
程序人员写程序,又拿程序换酒钱
酒醒只在网上坐,酒醉还来网下眠
酒醉酒醒日复日,网上网下年复年 | |
Re: Strassen Matrix Multiplication source code
It seems the seqMatMult() and matmultS() give different result.
When I ran with the argement "11 11 11", the ouput is,
Execute Standard matmult
Standard matrix function done in 0.00 secs
Strassen matrix function done in 0.00 secs
-0.810000 13.140000
Error in matmultS
| |
Re: Strassen Matrix Multiplication source code
Even when M, N and P are all exact power of 2, the problem still exists.
For eaxmple for "32 32 32", the output is,
Execute Standard matmult
Standard matrix function done in 0.00 secs
Strassen matrix function done in 0.00 secs
-28.700000 -17.900000
Error in matmultS
| |
Re: Strassen Matrix Multiplication source code
void matmultleaf(int mf, int ml, int nf, int nl, int pf, int pl, double **A, double **B, double **C)
/*
subroutine that uses the simple triple loop to multiply
a submatrix from A with a submatrix from B and store the
result in a submatrix of C.
*/
// mf, ml; /* first and last+1 i index */
// nf, nl; /* first and last+1 j index */
// pf, pl; /* first and last+1 k index */
{
for (int i = mf; i < ml; i++)
for (int j = nf; j < nl; j++)
{
C[i][j] = 0;
for (int k = pf; k < pl; k++)
C[i][j] += A[i][k]*B[k][j];
}
}
写字楼里写字间,写字间里程序员
程序人员写程序,又拿程序换酒钱
酒醒只在网上坐,酒醉还来网下眠
酒醉酒醒日复日,网上网下年复年 | |
Re: Strassen Matrix Multiplication source code
void matmultleaf(int mf, int ml, int nf, int nl, int pf, int pl, double **A, double **B, double **C)
/*
subroutine that uses the simple triple loop to multiply
a submatrix from A with a submatrix from B and store the
result in a submatrix of C.
*/
// mf, ml; /* first and last+1 i index */
// nf, nl; /* first and last+1 j index */
// pf, pl; /* first and last+1 k index */
{
for (int i = mf; i < ml; i++)
for (int j = nf; j < nl; j++)
{
C[i][j] = 0;
for (int k = pf; k < pl; k++)
C[i][j] += A[i][k]*B[k][j];
}
}
Thanks, 邓辉.
This can fix the problem when the parameters are the exact power of 2.
| |
Re: Strassen Matrix Multiplication source code
Thanks, 邓辉.
This can fix the problem when the parameters are the exact power of 2.
I think there was never a problem with parameters being powers of 2. I ran with m=n=p=32,64,128,256,512,1024.. and there were no problems whatsoever.
The code given by intel does not support all parameters.
I'll explain how. The code says that if m*n*p is < 1024 they will perform normal matrix multiplication that is using 3 for loops. In this case m,n and p can be anything even, odd, multiple of 2.. anything.
If m*n*p is greater than 1024 then they will divides m,n,p by 2 and tries to create 4 small matrices out of the big matrix and then use Strassens Algo. That means if m*n*p is greater than 1024 then odd numbers cannot be used for m,n and p. So m=n=p=1914 worked. If this value was big enough to get divided/2 twice then that would have failed.
So i would say the current code given by intel best works with powers of 2. Anyways for the actual solution you are free to change and support any type of parameter you like!
See below code snippets from StrassenMMult.cpp for more understanding.
#define GRAIN 1024 /* product size below which matmultleaf is used */
void strassenMMult(int mf, int ml, int nf, int nl, int pf, int pl, double **A, double **B, double **C)
{
if ((ml-mf)*(nl-nf)*(pl-pf) < GRAIN)
matmultleaf(mf, ml, nf, nl, pf, pl, A, B, C);
else {
int m2 = (ml-mf)/2;
int n2 = (nl-nf)/2;
int p2 = (pl-pf)/2;
...
...
...
| |
Re: Strassen Matrix Multiplication source code
In the problem description and the above post I'm reading language such as "This source file should be used as a starting point. Your entry should keep the body of the main function, the matrix generation function, the sequential multiplication code, and the function to compare the two matrix product results."
I'm reading this as: implement Strassen's Algorithm as I see fit; but dont change the code for:
- main()
- seqMatMult()
- CheckResults()
Is this correct?
Yes, this is the intention. The sequential multiplication and checking function should be untouched (or interpretted in the programming language used). The matrix intialization routine should remain intact or at least be shown to generate equivalent random matrices. Changes to the main() routine to support threading are allowed. All of these details should be part of the submitted write-up in order to understand the accompanying source code.
You must use Strassen's Algorithm or variation of that algorithm. You can change the memory allocation model, you can use different data structures as needed for threading or performance, and you can change the order of independent computations. Again, all the changes from the serial code should be documented in the write-up.
--clay
| |
Re: Strassen Matrix Multiplication source code
M, N, P must be 2 ^ n? Their range is how much? thanks！
Let's set the upper limit at 2^10 = 1048576.
--clay
| | |
