Speculative Computation in Multilisp
Abstract
This thesis demonstrates by experiments, that performing computations in parallel before their results are known to be required can yield performance improvements over conventional approaches to parallel computing. We call such eager computation of expressions speculative computation, as opposed to conventional mandatory computation that is used in almost all contemporary parallel programming languages and systems. The major requirements for speculative computation are a means to control computation to favor the most promising computations, and a means to abort computation and reclaim computation resources. We investigate these requirements in the parallel symbolic language Multilisp and conclude that we need the following support for speculative computation: for controlling computation we need ordering (ranking of computations by their promise), demand transitivity, and modularity, and for reclaiming computation we need explicit, reversible reclamation with automatic naming of descendants. The main contribution of this work is a sponsor model which provides this support for speculative computation in Multilisp. A sponsor is an agent which controls the allocation of resources to computation. This sponsor model handles control and reclamation of computation in a single, elegant framework. We also discuss the optimal scheduling of speculative computation and present new results for optimal scheduling in simple cases. Optimistic computation, Theses. (edc)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1989
- Accession Number
- ADA216579
Entities
People
- Randy B. Osborne
Organizations
- Defense Advanced Research Projects Agency