Parallel Schedules for Sparse Triangular Solve

Speaker: Raphael S. Steiner

Abstract: Parallel sparse triangular solve is a problem troubled with irregular patterns, dependencies, limited parallelism, and fine-grained operations and synchronisations. Numerous algorithms have been put forward to address these issues. Broadly speaking they can be categorised as synchronous and asynchronous. In this talk, I will summarise the important contributions by Anderson--Saad, Park et al., and Yilmaz et al. and present our new technique to generate synchronous schedules based on the popular list-scheduling method for directed-acyclic-graph scheduling. This allowed us to reduce the number of synchronisation barriers by 10x and execution times by 1.42x over state of the art methods. This talk is on joint work with T. Boehnlein, P. A. Papp, C. K. Matzoros, and A. N. Yzelman.

Biography: Raphael S. Steiner is research engineer at the Huawei research center in Zurich. He got his Ph.D. from the University of Bristol under the supervision of Tim Browning and Andy Booker. He subsequently held two postdoc positions at the Institute for Advanced Study in Princeton and ETH Zurich, respectively, before joining Huawei. His field of expertise includes analytic number theory and automorphic forms with applications to expander graphs and quantum computing. Nowadays, he focuses on questions in high performance computing, such as partitioning and scheduling, with far ranging applications such as compression and long integer multiplication.

Hosts: Prof. Olaf Schenk and Dimosthenis Pasadakis