Lazy Data-Oriented Evaluation Strategies

Prabhat Totoo, Hans-Wolfgang Loidl.
To appear in FHPC'14, ACM SIGPLAN Workshop on Functional High-Performance Computing, Gothenburg, Sweden, September 4th, 2014.

This paper presents a number of flexible parallelism control mechanisms in the form of evaluation strategies for tree-like data structures implemented in Glasgow parallel Haskell. We achieve additional flexibility by using laziness and circular programs in the coordination code. Heuristics-based parameter selection is employed to auto-tune these strategies for improved performance on a shared-memory machine without programmer-specified parameters.

In particular for unbalanced trees we demonstrate improved performance on a state-of-the-art multi-core server: giving a speedup of up to 37.5 on 48 cores for a constructed test program, and up to 15 for two other non-trivial applications using these strategies, a Barnes-Hut implementation of the n-body problem and a sparse matrix multiplication implementation.

Available in: pdf

The pardata package for this paper is:: Benchmark tarball (.tar.bz2)

GPH Papers | GPH