Generating High Performance Code for Irregular Data Structures using Dependent Types
Modern parallel architectures offer high performance but are challenging to program correctly. Data parallel functional languages offer a solution to this problem, providing a high-level programming model to work with accelerators such as GPUs. Existing languages are designed primarily to work with dense arrays and matrices, limiting their usefulness in expressing irregular data structures, such as graphs and sparse matrices. These structures are fundamental for many application domains, such as sparse linear algebra.
This paper closes this gap by extending a data-parallel functional language with limited dependent types. Particular emphasis is given to the addition of dependent pairs to model entire sparse data structures as values within the language. The approach is demonstrated through three case studies: dense to sparse matrix conversion, sparse matrix-vector multiplication, and parallel breadth-first search.
The experimental results show that this approach outperforms the state-of-the-art implementations on GPUs. Compared to NVidia cuSparse implementation, our automatically generated code achieves an average speedup of 1.2$\times$ for dense to sparse matrix conversion and 1.3$\times$ for sparse matrix-vector multiplication.
Sun 22 AugDisplayed time zone: Seoul change
18:00 - 19:30
|Welcome to FHPNC 2021|
Troels Henriksen University of Copenhagen, Denmark, Gabriele Keller Utrecht University
|Generating High Performance Code for Irregular Data Structures using Dependent Types|
Federico Pizzuti University of Edinburgh, Michel Steuwer University of Edinburgh, Christophe Dubach McGill University
|Improving GHC Haskell NUMA Profiling|
Ruairidh Macgregor University of Glasgow, Phil Trinder University of Glasgow, Hans-Wolfgang Loidl Heriot-Watt University, UK