PARALLEL ALGORITHM IMPLEMENTING STRASSEN’S ALGORITHM FOR MATRIX-MATRIX MULTIPLICATION (INTEL)

The included source code implements Strassen’s Algorithm for matrix-matrix 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: Breadth-First spawning (uses too much memory), Depth-First spawning (less memory, but less parallelism), and Half-and-Half (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 write-up projects that there are enough tasks and sub-tasks generated by the Half-and-Half 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.

There are downloads available under the Creative Commons License license. Download Now
For more complete information about compiler optimizations, see our Optimization Notice.