A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures

By Alfredo Buttari, J. Langou, Jakub Kurzak, Jack J. Dongarra. Parallel Computing, 2007

592 citations recorded by the source corpus.

As multicore systems continue to gain ground in the high performance computing world, linear algebra algorithms have to be reformulated or new algorithms have to be developed in order to take advantage of the architectural features on these new processors. Fine grain parallelism becomes a major requirement and introduces the necessity of loose synchronization in the parallel execution of an operation. This paper presents algorithms for the Cholesky, LU and QR factorization where the operations can be represented as a sequence of small tasks that operate on square blocks of data. These tasks can be dynamically scheduled for execution based on the dependencies among them and on the availability of computational resources. This may result in out of order execution of tasks which will completely hide the presence of intrinsically sequential tasks in the factorization. Performance comparisons are presented with LAPACK algorithms where parallelism can only be exploited at the level of the BLAS operations and vendor implementations.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/3a6e4b12b93cb9cca7ac39e5693e8cf8bd83d6e2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Jack J. Dongarra
2. J. Demmel
3. Piotr Luszczek
4. J. Langou
5. Peter J. Schmid
6. Taraneh Sayadi

In Hardware and Architecture

1. Jack J. Dongarra
2. J. Demmel
3. Piotr Luszczek
4. J. Langou
5. Jakub Kurzak
6. S. Tomov

Citations in the corpus

• Numerical linear algebra on emerging architectures: The PLASMA and MAGMA projects (2009, methodology): “…algebra and high performance computing (HPC) community due to the introduction of multi-core architectures and GPUs, we have developed two projects called Parallel Linear Algebra Software for Multi-core Architectures (PLASMA) [2, 3] and Matrix Algebra on GPU and Multi-core Architectures (MAGMA).”
• State-of-the-art in heterogeneous computing (2010, background): “Even worse, using caches for random access applications can degrade performance, as the cache transfers full cache lines across the memory bus when only a single element is needed without reuse [48, pp. 34–35, 47].”
• PLASMA (2019, methodology): “The Cholesky factorization is a straightforward algorithm to be written in the tile-oriented fashion (Buttari et al. 2009; Haidar et al. 2011), and Figure 8 shows the algorithm used in PLASMA.”
• Communication-optimal Parallel and Sequential QR and LU Factorizations (2008, methodology): “We note that the references [8, 9, 32, 39, 51] propose an algorithm called “tiled QR,” which is the same as our sequential CAQR with square blocks.”
• StarPU: a unified platform for task scheduling on heterogeneous multicore architectures (2011, background): “Various projects intend to implement libraries with computation kernels that are actually offloaded [5], but STARPU avoids for instance the limitation of the size of problems solved by BARRACHINA et al.”
• Scaling up matrix computations on shared-memory manycore systems with 1000 CPU cores (2014, background): “Copyrights for components of this work owned by others than ACM must be honored.”