Annotations to Control Parallelism, Reduction Order in the Distributed Evaluation of Functional Programs

Abstract

When evaluating a functional program on a network of processors, it is necessary to decide when parallelism is desirable, which work may be transferred to another processor, and in what form the work is to be transferred.If the wrong decisions are made, a parallel evaluation may require asymptotically more time than a sequential evaluation, owing to communication costs.The introduction of annotations to give the programmer control over the above decisions is proposed.The annotations and their effects are defined in terms of the lambda calculus.Each application must have one of three annotations.No other annotations are required.Examples and possible extensions to this work, including annotated combinators, are briefly considered.