Accession Number : ADA586696


Title :   Communication-Avoiding Parallel Recursive Algorithms for Matrix Multiplication


Descriptive Note : Master's thesis


Corporate Author : CALIFORNIA UNIV BERKELEY DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE


Personal Author(s) : Lipshitz, Benjamin


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a586696.pdf


Report Date : 17 May 2013


Pagination or Media Count : 93


Abstract : Matrix multiplication is one of the most fundamental algorithmic problems in numerical linear algebra, distributed computing, scientific computing, and high-performance computing. Parallelization of matrix multiplication has been extensively studied (e.g., [21, 12, 24, 2, 51, 39, 36, 23, 45, 61]). It has been addressed using many theoretical approaches, algorithmic tools, and software engineering methods in order to optimize performance and obtain faster and more efficient parallel algorithms and implementations. To design efficient parallel algorithms, it is necessary not only to load balance the computation, but also to minimize the time spent communicating between processors. The interprocessor communication costs are in many cases significantly higher than the computational costs. Moreover, hardware trends predict that more problems will become communication-bound in the future [38, 35]. Even matrix multiplication, which is widely considered to be computation-bound, becomes communication-bound when a given problem is run on sufficiently many processors.


Descriptors :   *ALGORITHMS , DISTRIBUTED DATA PROCESSING , SOFTWARE ENGINEERING , THESES


Subject Categories : Numerical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE