Speculative Evaluation for Parallel Graph Reduction
James S. Mattson, William G. Griswold · 1994
: Speculative evaluation can improve the performance of parallel graph reduction systems through increased parallelism. Although speculation is costly, much of the burden can be absorbed by processors which would otherwise be idle. Despite the overhead required for speculative task management, our prototype implementation achieves 70% efficiency for speculative graph reduction, with little impact on mandatory tasks. Through speculative evaluation, some simple benchmarks exhibit nearly a factor of five speedup over their conservative counterparts. Keyword Codes: D.1.1; D.1.3. Keywords: Programming Techniques, Applicative (Functional) Programming; Concurrent Programming. 1 Motivation Graph reduction is a popular implementation technique for non-strict functional programming languages. Because graph reduction is free of side-effects, it is well-suited to parallel processing. With conservative evaluation, an expression is not evaluated until its results are actually required. Speculativ...