Dynamic task scheduling for linear algebra algorithms on distributed-memory multicore systems
Fengguang Song, Asim YarKhan, Jack J. Dongarra · 2009
This paper presents a dynamic task scheduling approach to executing dense linear algebra algorithms on multicore systems (either shared-memory or distributed-memory). We use a task-based library to replace the existing linear algebra subroutines such as PBLAS to transparently provide the same interface and computational function as the ScaLAPACK library. Linear algebra programs are written with the task-based library and executed by a dynamic runtime system. We mainly focus our runtime system design on the metric of performance scalability. We propose a distributed algorithm to solve data dependences without process cooperation. We have implemented the runtime system and applied it to three linear algebra algorithms: Cholesky, LU, and QR factorizations. Our experiments on both shared-memory machines (16, 32 cores) and distributed-memory machines (1024 cores) demonstrate that our runtime system is able to achieve good scalability. Furthermore, we provide analytical analysis to show why the tiled algorithms are scalable and the expected execution time.
Cited by 102 works. doi:10.1145/1654059.1654079
Authors
References
- The Landscape of Parallel Computing Research: A View from Berkeley
- ScaLAPACK Users' Guide
- The implementation of the Cilk-5 multithreaded language
- Larrabee
- Scheduling multithreaded computations by work stealing
- A class of parallel tiled linear algebra algorithms for multicore architectures
- The Torus-Wrap Mapping for Dense Matrix Calculations on Massively Parallel Computers
- ScaLAPACK
- IBM POWER6 microarchitecture
- Design and Implementation of the ScaLAPACK LU, QR, and Cholesky Factorization Routines