Investigation Performance of Strassen Matrix Multiplication Algorithm on Distributed Systems

Parallel computation is the concurrent performance of a task with multiple processors in order to obtain rapid results. This method is based on that the process of solving a problem can usually be divided into smaller problem parts and with some coordination, these solution parts perform simultaneously. Simply put, parallel computing is the concurrent use of different computing resources for solving a computational problem. Parallel computing saves time, solves large problems efficiently and is cost-effective or non-local sources. There are two important models in the architecture of parallel computing: I. Shared memory: In this multiprocessor system, all of the allocated processors can access to a common memory. II. Message passing: In this multiprocessor system, each processor has its own local memory; processors exchange messages and share data through an internal connection network. In this thesis Strassen recursive algorithm is implemented for multiplying square matrices in parallel form for a distributed homogeneous system in order to improve its execution time. Strassen multiplying algorithm is a divide and conquer problem, with temporal complexity O ( ). Since this algorithm is recursive, total parallelism is impossible thus, matrices must be divided and distributed according to a special distribution topology in which affects on the performance time. This thesis represents an economical distribution topology with distributing matrices, which minimize the multiplication time of matrices in a parallel environment. Dividing and distributing matrices according to a basic distribution topology (two-fold distribution), led to favorable and unfavorable results. To improve the results, the matrix distribution topology needs to be changed. Finding a desirable and convenient topology is necessary aiming to achieve suitable results by considering matrices dimensions and the number of nodes. So, this method is expected to reduce the execution time in comparison with Strassen-BMR method. Keywords: Parallel Computation, Message Passing, Strassen Algorithm, Divide and Conquer, Topology