Speculation

When the system workload is low, it is tempting to be able to create speculative tasks which may later become useful, and so contribute to the overall execution. Several major issues must be addressed before a speculative implementation can be produced.

• Either a priority or a fair scheduling algorithm must be implemented in order to ensure that program termination is not affected due to executing speculative tasks at the expense of mandatory ones.
• Speculative evaluation runs the risk of memory exhaustion, both directly through stack and other memory usage, and through creating results which are connected to mandatory tasks, but which are not yet required.
• It must be possible to upgrade a speculative task if a mandatory task needs its result, and to kill a speculative task if its result can no longer be reached.

An early scheme to manage speculative evaluation in a distributed system was suggested by Hudak [60]. Unfortunately, this scheme seems both complicated and costly, and has apparently never been implemented. Partridge has simulated a similar scheme for shared-memory machines. His results are promising for some applications, but remain to be verified on real machines [95].

Mattson has implemented a speculative scheme for the STG-machine on a 64-processor shared-memory Butterfly [81]. Speculative tasks create revertible ``grey holes'' (in analogy to the ``black holes'' created by mandatory tasks, which indicate that the node is under evaluation). If a speculative task demands the value of a grey hole node, it suspends until that value is computed. If a mandatory task demands the value of a grey hole, this becomes a black hole, and the speculative task is temporarily upgraded to mandatory status. Initial results were somewhat disappointing, but perhaps reflected problems with the implementation rather than the idea. Mattson and Griswold have also investigated local speculative evaluation on GRIP [82].

Several authors have proposed fairly simple systems, where speculative tasks are restricted by being given a limited amount of ``fuel'', but are otherwise treated as mandatory tasks [121][55]. The advantages are that special schedulers are not required, and that it is relatively easy to kill such tasks. However, memory reclamation is still difficult. It remains to be seen whether, and how well, this strategy performs in practice.

Speculative evaluation is applicable to both strict and non-strict languages, since even strict languages have some non-strict constructs (function bodies or conditionals, for example). Because more parallel tasks are likely to be created in a strict environment, there may be fewer opportunities to exploit speculation in a strict language, however.