Schemeⁿ: Design, implementation and application

Abstract

This thesis presents the design, implementation and application of Schemeⁿ, a parallel extension of the Scheme programming language. Schemeⁿ has been designed for a distributed memory architecture to take advantage of explicitly specified large and medium grain parallelism. The language extensions and support provide for both data and control parallelism and the use of speculative computing to maximise parallel activity. Support is also provided for explicit process control for the assignment and termination of concurrent tasks. The main mechanism for introducing parallelism into a Schemeⁿ program is the future construct originally defined by Halstead for use in the Multilisp language and used in other parallel lisp designs. Implicit futures, which are dynamically assigned to available processes, via a distributed load balancing mechanism, have been used to hide the evaluation mechanism from the algorithm design. The thesis introduces the concepts of distributed processing. From these, the design of the Schemeⁿ language extensions and the supporting mechanisms required for communication between the concurrent tasks is given. An implementation of Schemeⁿ on a network of multiprocessors is then described. The behaviour of the implementation is analysed for a variety of communication topologies and the overhead of parallel invocation is quantified. Finally, an application of the language to the factorisation of large integers is demonstrated. Factorisation of an integer into its component prime factors is a computationally intensive task and several different methods exist for determining the factors and their primality. The factorisation process is parallelised by applying several factorisation methods to an integer concurrently. Where possible, the parallel features of a particular method are also utilised. A description is given of the factorisation methods and how they are combined. The application’s performance is analysed to provide understanding of the behaviour of the Schemeⁿ system.