Can I read Proceedings of the 17th ACM SIGPLAN international conference on Functional programming - ICFP '12 - Work efficient higher-order vectorisation on EtoBox?

Proceedings of the 17th ACM SIGPLAN international conference on Functional programming - ICFP '12 - Work efficient higher-order vectorisation by Lippmeier, Ben; Chakravarty, Manuel M.T.; Keller, Gabriele; Leshchinskiy, Roman; Peyton Jones, Simon is a scholarly article available to read on EtoBox.

What is Proceedings of the 17th ACM SIGPLAN international conference on Functional programming - ICFP '12 - Work efficient higher-order vectorisation about?

Existing approaches to higher-order vectorisation, also known as flattening nested data parallelism, do not preserve the asymptotic work complexity of the source program. Straightforward examples, such as sparse matrix-vector multiplication, can suffer a severe blow-up in both time and space, which limits the practicality of this method. We discuss why this problem arises, identify the mis-handling of index space transforms as the root cause, and present a solution using a refined representation of nested arrays. We have implemented this solution in Data Parallel Haskell (DPH) and present benchmarks showing that realistic programs, which used to suffer the blow-up, now have the correct asymptotic work complexity. In some cases, the asymptotic complexity of the vectorised program is even better than the original.

Author

Lippmeier, Ben; Chakravarty, Manuel M.T.; Keller, Gabriele; Leshchinskiy, Roman; Peyton Jones, Simon

Publisher

ACM Press

Published

2012

Language

DE