2010 · 37 citations · 28 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureParallel AlgorithmsParallel ComputingCachingData ParallelismMatrix ComputationMemory HierarchyParallel ArchitecturesParallel Numerical Linear AlgebraBlock Matrix AlgorithmsHigh PerformanceLu DecompositionParallel Matrix ComputationParallel Matrix FactorizationParallel Matrix InversionParallel Sparse Linear AlgebraSparse Matrix Computation
In LAPACK many matrix operations are cast as block algorithms which iteratively process a panel using an unblocked algorithm and then update a remainder matrix using the high performance Level 3 BLAS. The Level~3 BLAS have excellent weak scaling, but panel processing tends to be bus bound, and thus scales with bus speed rather than the number of processors (p). Amdahl's law therefore ensures that as p grows, the panel computation will become the dominant cost of these LAPACK routines. Our contribution is a novel parallel cache assignment approach which we show scales well with p. We apply this general approach to the QR and LU panel factorizations on two commodity 8-core platforms with very different cache structures, and demonstrate superlinear panel factorization speedups on both machines. Other approaches to this problem demand complicated reformulations of the computational approach, new kernels to be tuned, new mathematics, an inflation of the high-order flop count, and do not perform as well. By demonstrating a straight-forward alternative that avoids all of these contortions and scales with p, we address a critical stumbling block for dense linear algebra in the age of massive parallelism.
28
A set of level 3 basic linear algebra subprograms
Jack Dongarra, Jeremy Du Croz, Sven Hammarling et al. · ACM Transactions on Mathematical Software · 1990 · 1.8K citations · Full text
Basic Linear Algebra Subprograms for Fortran Usage
C. L. Lawson, Richard Hanson, David R. Kincaid et al. · ACM Transactions on Mathematical Software · 1979 · 1.6K citations · Full text