Blogs (28) >>
ICFP 2017
Sun 3 - Sat 9 September 2017 Oxford, United Kingdom
Thu 7 Sep 2017 14:00 - 14:30 at L4 - Parallel Programming Chair(s): Geoffrey Mainland

Recursion schemes, such as the well-known map, can be used as loci of potential parallelism, where, e.g., map is replaced with an equivalent parallel implementation. This paper formalises a novel technique, using program slicing, that automatically and statically identifies computations in recursive functions that can be lifted out of the function and potentially performed in parallel. We define a new program slicing algorithm, and show the soundness and completeness of our algorithm. We have built a prototype implementation, and demonstrated its use on 12 Haskell examples, including benchmarks from the NoFib suite and functions from the standard Haskell Prelude. In all cases, we obtain the expected results in terms of finding potential parallelism. Moreover, we have tested our prototype against synthetic benchmarks, demonstrating our prototype has quadratic time complexity. For the NoFib benchmark examples we demonstrate that real parallel speedups can be obtained (up to 32.93 times the sequential performance on 56 hyperthreaded cores).

Thu 7 Sep

Displayed time zone: Belfast change

14:00 - 15:00
Parallel ProgrammingFHPC at L4
Chair(s): Geoffrey Mainland Drexel University, USA
14:00
30m
Talk
In Search of a Map: using Program Slicing to Discover Potential Parallelism in Recursive Functions
FHPC
A: Adam Barwell , A: Kevin Hammond University of St. Andrews, UK
14:30
30m
Talk
Strategies for Regular Segmented Reductions on GPU
FHPC
A: Rasmus Wriedt Larsen DIKU, University of Copenhagen, A: Troels Henriksen DIKU, University of Copenhagen