ICFP 2021
Sun 22 - Sat 28 August 2021
Sun 22 Aug 2021 18:15 - 18:45 at FHPNC - Session 1

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 Aug

Displayed time zone: Seoul change

18:00 - 19:30
Session 1FHPNC at FHPNC
Day opening
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