Speculative evaluation in parallel implementations of lazy functional languages
thesis
posted on 2023-05-27, 16:02authored byPartridge, Andrew Simon
The usual technique for extracting parallelism from lazy functional languages is to use strictness analysis to annotate function applications that can safely be performed as call-by-value. However, practical strictness analyses can only find partial strictness information about some programs. Speculative evaluation can gain parallelism in the presence of incomplete strictness information by creating a task to evaluate the argument of some applications in parallel with evaluation of the function, before it is known whether the value of the argument is eventually going to be needed. This thesis presents a scheme for adding speculative evaluation to the parallel implementation of lazy functional languages. Speculative tasks are assigned scheduling priorities to prevent them from hogging processing and memory resources. Simulation results demonstrate the effectiveness of the scheme in a shared-memory system. Implementation of speculative evaluation on distributed systems is also described, including a load distribution algorithm that deals with tasks according to their scheduling priorities. The performance of speculative evaluation on distributed systems remains an open research topic.
History
Publication status
Unpublished
Rights statement
Copyright 1991 the author - The University is continuing to endeavour to trace the copyright owner(s) and in the meantime this item has been reproduced here in good faith. We would be pleased to hear from the copyright owner(s). Includes bibliographical references (p. [153]-158). Thesis (Ph.D.)--University of Tasmania, 1992