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 AugDisplayed time zone: Seoul change

 18:00 - 19:30 Session 1FHPNC at FHPNC 18:0015mDay opening Welcome to FHPNC 2021FHPNCTroels Henriksen University of Copenhagen, Denmark, Gabriele Keller Utrecht University 18:1530mTalk Generating High Performance Code for Irregular Data Structures using Dependent TypesFHPNCFederico Pizzuti University of Edinburgh, Michel Steuwer University of Edinburgh, Christophe Dubach McGill University 18:4530mTalk Improving GHC Haskell NUMA ProfilingFHPNCRuairidh Macgregor University of Glasgow, Phil Trinder University of Glasgow, Hans-Wolfgang Loidl Heriot-Watt University, UK