Leapfrogging: A Portable Technique for Implementing Efficient Futures

Abstract

A future is a language construct that allows programmers to expose parallelism in applicative languages such as MultiLisp [5] 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++.