Programming matrix algorithms-by-blocks for thread-level parallelism
Open Access
- 23 July 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 36 (3) , 1-26
Abstract
With the emergence of thread-level parallelism as the primary means for continued performance improvement, the programmability issue has reemerged as an obstacle to the use of architectural advances. We argue that evolving legacy libraries for dense and banded linear algebra is not a viable solution due to constraints imposed by early design decisions. We propose a philosophy of abstraction and separation of concerns that provides a promising solution in this problem domain. The first abstraction, FLASH, allows algorithms to express computation with matrices consisting of contiguous blocks, facilitating algorithms-by-blocks. Operand descriptions are registered for a particular operation a priori by the library implementor. A runtime system, SuperMatrix, uses this information to identify data dependencies between suboperations, allowing them to be scheduled to threads out-of-order and executed in parallel. But not all classical algorithms in linear algebra lend themselves to conversion to algorithms-by-blocks. We show how our recently proposed LU factorization with incremental pivoting and a closely related algorithm-by-blocks for the QR factorization, both originally designed for out-of-core computation, overcome this difficulty. Anecdotal evidence regarding the development of routines with a core functionality demonstrates how the methodology supports high productivity while experimental results suggest that high performance is abundantly achievable.Keywords
Funding Information
- Fundación Bancaja (P1B-2007-19P1B-2007-32)
- Division of Computing and Communication Foundations (CCF-0540926CCF-072714)
- CICYT (TIN2005-09037-C02-02)
This publication has 26 references indexed in Scilit:
- Updating an LU Factorization with PivotingACM Transactions on Mathematical Software, 2008
- Families of algorithms related to the inversion of a Symmetric Positive Definite matrixACM Transactions on Mathematical Software, 2008
- Anatomy of high-performance matrix multiplicationACM Transactions on Mathematical Software, 2008
- Representing linear algebra algorithms in code: the FLAME application program interfacesACM Transactions on Mathematical Software, 2005
- Parallel out-of-core computation and updating of the QR factorizationACM Transactions on Mathematical Software, 2005
- A framework for high-performance matrix multiplication based on hierarchical abstractions, algorithms and optimized low-level kernelsConcurrency and Computation: Practice and Experience, 2002
- FLAMEACM Transactions on Mathematical Software, 2001
- A set of level 3 basic linear algebra subprogramsACM Transactions on Mathematical Software, 1990
- An extended set of FORTRAN basic linear algebra subprogramsACM Transactions on Mathematical Software, 1988
- Basic Linear Algebra Subprograms for Fortran UsageACM Transactions on Mathematical Software, 1979