Abstract | ||
---|---|---|
Linear operators used in iterative methods like conjugate gradient have typically been implemented either as ""matrix-driven"" subroutines backed by explicit sparse or dense matrices, or as ""matrix-free"" subroutines that implement specific linear operations directly (e.g. FFTs). The matrix-driven approach is generally more portable because it can target widely-available BLAS libraries, but it can be inefficient in terms of time and space complexity. In contrast, the matrix-free approach is more performant because it leverages structure in operations, but it requires each operator be re-implemented on each new platform. To increase performance and portability, we propose a hybrid approach that represents linear operators as expression trees. Leaf nodes in the tree are either matrix-free or matrix-driven operators, and interior nodes represent mathematical compositions (sums, products, transposes) or structural compositions (stacks, block diagonals, etc.) of the leaf operators. This representation enables expert-guided reordering and fusion transformations that can improve performance or reduce memory pressure. We implement our approach in a domain-specific language called Indigo. We assess Indigo on image reconstruction problems arising in four application areas: magnetic resonance imaging, ptychography, magnetic particle imaging, and fluorescent microscopy. We give performance results from vendor BLAS libraries, and we introduce specializations to Sparse BLAS routines that achieve near-Roofline performance on multi-core, many-core, and GPU systems. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1109/IPDPS.2018.00059 | 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
Keywords | Field | DocType |
high performance computing,medical imaging,domain specific languages | Conjugate gradient method,Iterative reconstruction,Subroutine,Iterative method,Computer science,Parallel computing,Image processing,Operator (computer programming),Binary expression tree,Sparse matrix | Conference |
ISSN | ISBN | Citations |
1530-2075 | 978-1-5386-4369-3 | 1 |
PageRank | References | Authors |
0.36 | 13 | 8 |
Name | Order | Citations | PageRank |
---|---|---|---|
Michael B. Driscoll | 1 | 50 | 2.56 |
Benjamin Brock | 2 | 8 | 2.30 |
frank ong | 3 | 12 | 2.98 |
Jonathan I. Tamir | 4 | 40 | 12.04 |
Hsiou-Yuan Liu | 5 | 1 | 0.36 |
Michael Lustig | 6 | 1468 | 78.94 |
Armando Fox | 7 | 6238 | 524.64 |
Katherine A. Yelick | 8 | 3494 | 407.23 |