Abstract: Speculative evaluation, including leniency and futures, is often used to produce high degrees of parallelism. Existing speculative implementations, however, may serialize computation because of their implementation of queues of suspended threads. We give a provably efficient parallel implementation of a speculative functional language on various machine models. The implementation includes proper parallelization of the necessary queuing operations on suspended threads. Our target machine models are a butterfly network, hypercube, and PRAM. To prove the efficiency of our implementation, we provide a cost model using a profiling semantics and relate the cost model to implementations on the parallel machine models.
@inproceedings {GREINER96psl,
author = "John Greiner and Guy~E. Blelloch",
title = "A Provably Time-Efficient Parallel Implementation of
Full Speculation",
booktitle = "Proceedings of the 23rd ACM Symposium on Principles of Programming Languages",
year = 1996,
month = jan,
pages = "309--321"}