Leapfrogging: A Portable Technique for Implementing Efficient Futures

Dave Wagner and Brad Calder

4th ACM Principles and Practice of Parallel Processing, pages 208-217, May 1993.


A future, is a language construct that allows programmers to expose parallelism in applicative languages such as MultiLisp [Halstead85] with minimal effort. In this paper we describe a technique for implementing futures, which we call leapfrogging that reduces blocking due to load imbalance.

The utility of leapfrogging is enhanced by the fact that it is completely platform-independent, is free from deadlock, and places a bound on stack sizes that is at most a small constant times the maximum stack size encountered during a sequential execution of the same computation. We demonstrate the performance of leapfrogging using a prototype implementation written in C++.