Indigo: A Domain-Specific Language for Fast, Portable Image Reconstruction

Citations Over Time

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.

Related Papers

• → Runtime System for Parallel Execution of Fragmented Subroutines(2007)6 cited
• → OS Subset Structure Achieving AP Portability(1990)4 cited
• → The pitfalls of portability . . or . . why more is not better(2002)3 cited
• Application of User Subroutine UAMP of ABAQUS(2014)
• → Standardization -portability of crystallographic data(1993)