Source-linked AI summary
A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures
Alfredo Buttari, Julien Langou, Jakub Kurzak, Jack Dongarra
TL;DR
Multicore architectures expose limits in BLAS-level parallelism, especially sequential panel work and forced synchronization. The paper reformulates Cholesky, LU, and QR as tile-based task graphs with asynchronous dynamic scheduling, and reports benefits over fork-join and vendor implementations, while noting LU pivoting-analysis limitations.
Problem
BLAS-level parallelism in existing factorization libraries leaves sequential tasks and synchronization barriers that limit multicore scalability.
Method
The paper develops tiled Cholesky, LU, and QR algorithms represented as dependency graphs of small tasks executed dynamically and asynchronously.
Results
The tiled asynchronous algorithms provide considerable benefits over traditional fork-join execution and vendor implementations across the reported factorization results.
Takeaways & Limitations
Fine-grain tiled tasks with graph-driven asynchronous execution can improve multicore factorization performance beyond traditional fork-join execution.
Takeaways & Limitations
The tiled LU pivoting strategy complicates analysis because permutation and elementary-transformation effects cannot be separated into distinct L and P matrices as in GEPP.
Abstract
from arXiv · showhide
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 an algorithm 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 an out of order execution of the tasks which will completely hide the presence of intrinsically sequential tasks in the factorization. Performance comparisons are presented with the LAPACK algorithms where parallelism can only be exploited at the level of the BLAS operations and vendor implementations.
1 Introduction
Multicore processors shift performance growth from instruction-level parallelism toward replicated cores, requiring algorithms to expose fine-grain, asynchronous task parallelism. Existing applications and algorithms often need substantial rewriting to exploit these architectural features.
- Architectural shift: Physical limits on power consumption and heat dissipation shifted processor design from instruction-level parallelism toward thread-level parallelism.Performance is pursued by replicating execution units or cores while keeping clock rates within manageable power and heat ranges.
- Programming challenge: Parallelizing compilers remain effective only for a restricted class of problems, so applications must be explicitly redesigned for multicore execution.Previously parallel applications may also require considerable rework to exploit fine-grain parallelism.
- Architectural requirements: Multicore scalability concerns motivate algorithm properties that match high degrees of thread-level parallelism.The paper identifies these properties in the surrounding discussion, including fine granularity and asynchronicity.
- Architectural requirements: Fine granularity splits operations into tasks on small data portions, reducing bus traffic and improving data locality.For architectures with explicitly managed local memories, fine granularity is described as the only means to achieve parallelism.
- Architectural requirements: As operation granularity decreases and thread-level parallelism grows, synchronization points increasingly reduce parallel execution efficiency.Asynchronous execution can also hide memory-access latency, while dynamic task execution supports this model.
- Paper direction: The paper therefore presents fine-grain, asynchronous algorithmic execution as a required response to multicore architectural features.Section 3 develops such algorithms and Section 5 evaluates their performance.
2 The LAPACK and ScaLAPACK libraries and their scalability limits
LAPACK and ScaLAPACK obtain parallelism mainly through BLAS, but shared-memory limitations create fork-join execution and scalability problems. Tiled, graph-driven algorithms instead expose finer-grain tasks for asynchronous scheduling.
- Existing libraries: LAPACK and ScaLAPACK are standard dense linear algebra libraries whose parallelism comes from parallel BLAS or PBLAS.LAPACK targets shared-memory architectures, while ScaLAPACK targets distributed-memory architectures.
- Existing libraries: Blocking concentrates most computation in Level-3 BLAS operations to improve data reuse and reduce memory traffic.Panel transformations use Level-2 BLAS, while accumulated transformations update the trailing submatrix through Level-3 BLAS.
- Scalability limits: Level-2 BLAS cannot be efficiently parallelized on shared-memory multicore systems because of the bus bottleneck, producing a fork-join execution pattern.Parallelism is exploited only at the BLAS level in the reference library implementations.
- Scalability limits: Scalability is limited because the relative cost of strictly sequential panel factorizations increases as parallelism grows.This limits the scalability of the block algorithms.
- Scalability limits: Synchronization cannot be fully asynchronous because multiple threads wait idle for sequential tasks to finish.This is identified as a limitation of the existing execution approach.
- Alternative approaches: Recursive QR, LU, and Cholesky algorithms improve Level-3 BLAS exploitation inside panels but remain unsuitable for fine-grain parallelism.The cited approaches increase BLAS-level parallelism without reaching the required granularity.
- Tiled approach: The resulting reformulation moves parallelism above the BLAS level, targeting finer granularity and greater scheduling flexibility on multicore systems.The transition is presented as a response to multicore requirements.
- Tiled approach: Tiled algorithms represent Cholesky, LU, and QR factorizations as dependent tasks on small square matrix tiles, enabling dynamic graph-driven execution.Asynchronous scheduling executes tasks out of order without violating dependencies.
3 Fine Granularity Algorithms for the Cholesky, LU and QR Factorizations
The paper develops tiled Cholesky, LU, and QR factorizations whose fine-grained tasks support dynamic, asynchronous execution. It also examines the stability and computational cost of tiled LU and QR variants, finding important trade-offs for pivoting and blocking.
- Tiled algorithms: Tiled factorizations divide operations into tasks on small square matrix tiles, enabling fine granularity and efficient storage formats such as Block Data Layout.This applies to Cholesky, LU, and QR factorizations.
- Asynchronous execution: Dynamic scheduling executes tile tasks asynchronously and out of order while respecting dependencies represented by a directed acyclic graph.The approach increases scheduling flexibility for tiled factorizations.
- QR and LU cost: QR and LU use updating factorizations with blocked transformations; choosing s ≪ b limits the additional operation cost to a negligible amount.When s = b, the tiled QR cost is 25% higher than standard LAPACK, but suitable b and s choices can reduce the overhead substantially.
- LU pivoting: Algorithm 3 uses tiled Gaussian elimination with pairwise pivoting, potentially selecting up to (n − k)/b pivots instead of GEPP’s unique pivot for column k.This pivoting strategy is called GETWP.
- LU stability: GETWP is less stable than GEPP, and decreasing tile size makes the method less stable.The authors recommend checking solution backward error and applying iterative refinement when needed.
- LU stability: GETWP stability analysis must monitor both ∥U∥∞ and ∥L∥∞ because off-diagonal entries of its combined N factor can exceed 1.Unlike GEPP, GETWP’s N combines permutations and elementary transformations and is not generally unit lower triangular.
- LU experiments: As the number of tiles increases, GETWP stability decreases, although factorization and solution backward errors can differ substantially.For random matrices with p = 128, the reported mean factorization error is 7 · 10^-11 for GETWP versus 2 · 10^-11 for GENP.
- LU experiments: On Matrix Market tests, 146 of 1475 solution cases and 121 of 147 factorization cases had GETWP backward error below 25 times GEPP’s.The worst case, orani, produced ratios of 4.6 · 10^7 for factorization and 1.9 · 10^4 for solution error.
4 Graph driven asynchronous execution
The factorization algorithms are modeled as dependency graphs of tile-level tasks, enabling asynchronous dynamic scheduling and out-of-order execution with loose synchronization. This scheduling exposes ready work and reduces idle time by adapting task assignment to available execution units.
- Dependency representation: The tiled factorizations form DAGs whose nodes are computational tasks and whose edges encode dependencies.For tiled QR, the DAG has a recursive structure: smaller matrices produce subgraphs of larger-matrix DAGs.
- Dynamic scheduling: Tasks can execute asynchronously and independently whenever their dependency constraints are satisfied.The scheduling policy prioritizes nodes with many outgoing edges to maximize the number of ready tasks.
- Out-of-order execution: Dynamic scheduling produces out-of-order execution with only very loose synchronization between threads.The execution-flow example uses an 8-core machine and assigns tasks according to DAG dependencies.
- Scheduling effects: Graph-driven execution removes idle times associated with fork-join execution and schedules tasks according to available execution units.This provides some degree of adaptivity in assigning work to threads.
- Implementation model: A pThreads implementation stores dependencies implicitly in a shared progress table, from which self-scheduled threads select doable tasks using priorities.The approach could also be implemented with OpenMP, MPI, or hybrid combinations.
5 Performance Results
Performance experiments compare dynamically scheduled tiled Cholesky, QR, and LU factorizations with LAPACK-style fork-join algorithms and vendor implementations. The tiled approach outperforms the fork-join baseline for Cholesky and QR, while LU reaches similar asymptotic performance to MKL but benefits at smaller problem sizes.
- Experimental comparison: Figures 8–10 compare tiled dynamic-scheduling algorithms for Cholesky, QR, and LU with MKL, ACML, and LAPACK multithreaded-BLAS implementations.The tiled algorithms use tuned tile sizes and internal blocking sizes, while the experiments assume nearly equal operation counts for QR and LU.
- Scalability: Figure 11 evaluates weak scalability by plotting flop rates against core count while keeping the local problem size constant at nloc=5,000.The supplied passages identify the scalability setup but do not report its numerical outcome.
- Cholesky and QR: Cholesky and QR achieve higher execution rates than the fork-join approach and perform around 50% better than a vendor implementation.The Cholesky comparison is affected by LAPACK’s poor-performing left-looking block variant.
- LU performance: LU delivers considerable speedup over fork-join execution but reaches roughly the same asymptotic performance as MKL-9.1.The reported limitations involve pairwise pivoting overhead and small-data BLAS performance.
- LU performance: The LU tiled algorithm reaches asymptotic performance faster, providing considerable benefits for lower-size problems.Fixed tile and blocking parameters make BLAS performance effectively constant, while dynamic execution reduces parallelization overhead.
6 Conclusions
The paper argues that fine-grained tiled algorithms and asynchronous execution are well suited to multicore architectures. Its results support benefits over traditional fork-join execution and vendor implementations.
- Context: The approach builds on earlier work by the authors and prior research on related parallel algorithms.The paper also notes supporting results from the FLAME group at the University of Texas Austin.
- Conclusion: Fine granularity and asynchronous execution are desirable for multicore performance because they support parallelism, local data reuse, and memory-latency hiding.These properties address architectural demands associated with higher degrees of parallelism.
- Conclusion: The reported results show considerable benefits from combining tiled algorithms with graph-driven asynchronous execution over fork-join approaches and vendor implementations.The conclusion presents this performance evidence as support for the proposed reasoning.