DESIGN OF A FUNCTIONAL COMPUTATION MODEL FOR MULTIPROCESSOR ARCHITECTURE

Abstract

Functional languages, due to their straightforward declarative way of expression, are finding favour as an elegant programming medium. Further, their properties of referential transparency and freedom from side-effects make them highly attractive for programming multiprocessor systems. These merits are pushing them more and more into the domain of computer research directed towards achieving higher execution speeds and/or increasing programming comfort. The research has generated radically different computation systems called reduction computers. This thesis reports the design of a multiprocessor computation model based on the functional approach. The various features that the model supports include pattern-matching, data structures, lazy evaluation of conditional expressions, and recursion. The complete design consists of two phases : first, the translation of program definitions into an intermediate form suitable for machine interpretation,- and second, the evaluation of the translated program through reduction in a multiprocessor environment. Program input to the model is a set of supercombinator definitions and an expression for evaluation. The definitions are like user defined functions having no fixed reduction rules, and have been compiled down to an intermediate representation called Structured Director String (SDS) term. The terms express the supercombinator definition bodies as variable-free annotated graph structures and are used as templates for function instantiation. They are a generalisation of Kennaway & Sleep's DS terms, and are obtained through a pattern-abstraction process for which an algorithm has been developed and tested. For dealing with local definitions within definitions, the SDS term notation has been enriched by including pointers and a concept of context-list. Various types of local definitions (nonrecursive, recursive and mutually recursive) have been interpreted via lambda calculus into the enriched notation. A coarse-grain, message-passing multiprocessor reduction scheme has been proposed. SDS term reduction rules, which are based on a modified set of (3-reduction rules framed for dealing with structured arguments, have been developed and are used during template-instantiation of a function. The reduction strategy is basically applicative (eager) so as to exploit parallelism, wherever possible. For reduction, a program expression is organised into a task-graph where each task is the smallest unit of computation consisting of a function applied to all its arguments. Tasks in task-graph reduce (as per the proposed conditions of reducibility) and communicate through messages enabling other tasks to reduce. The process continues till the result of the expression is obtained. Several control mechanisms, in the basic scheme, have been incorporated to support selective laziness in dealing with infinite data structures, lazy evaluation of conditionals, and controlled recursion through the fixed-point combinator. Safety aspect of the applicative order has been improved to some extent by leaving a sub-expression in unorganised form, although no strictness analysis of functions has been performed. The complete reduction strategy, the organisation algorithm and the message handling schemes have been formally specified in a Pascal-like notation.