Accession Number ADA586696
Title Communication-Avoiding Parallel Recursive Algorithms for Matrix Multiplication.
Publication Date May 2013
Media Count 93p
Personal Author B. Lipshitz
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.
Keywords Algorithms
Distributed data processing
Matrix multiplication
Software engineering

Source Agency Non Paid ADAS
NTIS Subject Category 72B - Algebra, Analysis, Geometry, & Mathematical Logic
Corporate Author California Univ., Berkeley. Dept. of Electrical Engineering and Computer Science.
Document Type Thesis
Title Note Master's thesis.
NTIS Issue Number 1405
Contract Number HR0011-12-2-0016

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader