 Parallel algorithm implementing Strassen’s Algorithm for matrixmatrix multiplication ( Akshay Singh)

Material Type:
Coding example, Problem set Technical Format:
PDF document, zip archive, text file Location:
Go to materials Date Added:
04/12/2010 Date Modified:
04/12/2010 Author
Akshay Singh, Intel Threading Challenge Description: The included source code implements Strassen’s Algorithm for matrixmatrix multiplication in parallel, as described in the included problem description text file. The parallel algorithm uses Pthreads to implement a thread pool and the standard recursive algorithm to create smaller instances of the matrix multiplication. The smaller instances become tasks that can be assigned to threads within the thread pool. The code was intended for Linux OS and includes a makefile to build the application.
Recommended Audience:
Programmers experienced in C/C++ and Pthreads; students of linear algebra with C/C++ and parallel programming skillDISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.
Recommended Audience:
Advanced programmers, Beginning programmers, Undergraduate students Language:
English Keywords:
Strassens Algorithm, matrixmatrix multiplication, POSIX Threads, linear algebra, Pthreads, thread pool
 Parallel algorithm implementing Strassen’s Algorithm for matrixmatrix multiplication (Bradley Kuszmaul)

Material Type:
Coding example, Problem set Technical Format:
text file, zip archive, PDF document Location:
Go to materials Date Added:
04/12/2010 Date Modified:
04/12/2010 Author
Bradley Kuszmaul, MIT Computer Science and Artificial Intelligence Laboratory Description: The included source code implements Strassen’s Algorithm for matrixmatrix multiplication in parallel, as described in the included problem description text file. The included writeup gives an overview of Cilk++ and some of the tools available for Cilk programming. Six different methods for computing matrixmatrix multiplication are discussed. The pros and cons of the parallelization (using Cilk++) of each method and the performance of each on different sized matrices are provided within the writeup. Source files for the alternate algorithms are provided and these alternatives can be built for comparison against each other. The code was intended for Linux OS and includes a makefile to build the applications.
Recommended Audience:
Programmers experienced in C/C++ (some exposure to Cilk++ and parallel programming is helpful); students of linear algebra with C/C++ and parallel programming skill.DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.
Recommended Audience:
Advanced programmers, Beginning programmers, Undergraduate students Language:
English Keywords:
Strassens Algorithm, matrixmatrix multiplication, Cilk++, linear algebra, Goto BLAS, Intel Math Kernel Library MKL, divide and conquer, MKL
 Parallel algorithm implementing Strassen’s Algorithm for matrixmatrix multiplication ( G. Koloskov)

Material Type:
Coding example, Problem set Technical Format:
text file, PDF document, zip archive Location:
Go to materials Date Added:
04/12/2010 Date Modified:
04/12/2010 Author
G Koloskov, Intel Threading Challenge Description: The included source code implements Strassen’s Algorithm for matrixmatrix multiplication in parallel, as described in the included problem description text file. The parallel algorithm uses OpenMP* to implement the standard recursive algorithm. However, to better load balance the work assigned to threads, the code has been written to handle nonsquare matrix instances by detecting small matrix dimensions and not subdividing such matrices. The code was intended for Linux OS and includes a makefile to build the application.
DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.
Recommended Audience:
Advanced programmers, Beginning programmers, Undergraduate students Language:
English Keywords:
Strassens Algorithm, matrixmatrix multiplication, OpenMP, linear algebra, load balance
 Parallel algorithm implementing Strassen’s Algorithm for matrixmatrix multiplication (Intel)

Material Type:
Coding example, Problem set Technical Format:
PDF document, text file, zip archive Location:
Go to materials Date Added:
04/12/2010 Date Modified:
04/12/2010 Author
Byung Kim, Intel Description: The included source code implements Strassen’s Algorithm for matrixmatrix multiplication in parallel, as described in the included problem description text file. The parallel algorithm uses Intel Threading Building Blocks (TBB) to implement the parallelization from the standard recursive algorithm. Three alternatives for creating TBB tasks are examined: BreadthFirst spawning (uses too much memory), DepthFirst spawning (less memory, but less parallelism), and HalfandHalf (best features of previous methods). The implemented code has two phases of tasks generated. The temporary matrices used in the first phase are used in the second phase to cut down the memory requirements. The writeup projects that there are enough tasks and subtasks generated by the HalfandHalf method to keep at least 8 cores busy. The code was intended for Linux OS and includes a makefile to build the application.
DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.
Recommended Audience:
Advanced programmers, Beginning programmers, Undergraduate students Language:
English Keywords:
Strassens Algorithm, Intel Threading Building Blocks, TBB, tasks, linear algebra, matrixmatrix multiplication, BreadthFirst spawning, DepthFirst spawning
 Implementing Strassen’s Algorithm for matrixmatrix multiplication with OpenMP* 3.0 tasks (Intel)

Material Type:
Lecture / Presentation, Coding example, Problem set Technical Format:
text file, .docx, .pptx, .icproj, .sln, .suo, .vcproj, zip archive Location:
Go to materials Date Added:
03/31/2010 Date Modified:
03/31/2010 Author
Clay Breshears, Intel Software Description: he included source code implements Strassen’s Algorithm for matrixmatrix multiplication in parallel using OpenMP* 3.0 tasks. Microsoft Visual Studio* solution and project files are included to build the application for testing. The PowerPoint* lecture foils describe 1) the standard triplenested algorithm and how different insertion points of OpenMP* pragmas will affect the parallelism to be expected, 2) a recursive algorithm with the same number of multiplication operations, and 3) the Strassen’s Algorithm and how to use OpenMP* 3.0 task constructs to parallelize the recursive calls. The writeup follows the outline in the PowerPoint presentation. Potential modifications to the included code that may have an effect on parallel performance are postualted in both the PowerPoint and written description of the code development for Strassen’s Algorithm. These modifications could be assigned as lab exercises by students to determine if there is any significant performance benefit to the potential optimizations.
Recommended Audience
Programmers experienced in C/C++ and OpenMP* 3.0 task constructs; students of linear algebra with C/C++ and parallel programming skillRecommended Audience:
Beginning programmers, Undergraduate students Language:
English Keywords:
matrixmatrix multiplication, OpenMP, OpenMP task constructs, recursion, linear algebra, C++, Strassens Algorithm