The four-stroke reduction engine
Christopher D. Clack, Simon Jones · 1986
AbstrmctFunctional languages are widely claimed to be amenable to concurrent execution by multtple processors.This paper presents an algorithm for the parallel graph reduction of a functional program.The algorithm supports transparent management of parallel tasks with no explicit communication between processors.X. eaeJq~onnd A major challenge facing computer science today is the effective exploitation of parallelism.Functional languages offer a powerful lever on the programming of parallel machines, and the most promising model for implementing these languages is graph reduction. Hany current research projects are investigating parallel architectures [Kel185J [Dar181] [Hudak85| IPeyt85|.Parallel hardware can readily be built using conventional technology, but designing the system so that parallelism gives worthwhile gains, and so that harnessing this parallelism Is easy for the programmer, represents a greater challenge.This paper is concerned with the design of a parallel graph reduction algorithm that viii transparently administer the scheduling and synchronisatton of concurrent tasks in a parallel functional-programming machine.The algorithm that we present can be coded as a finite state machine.This enables us to produce a simple and efficient implementation. Functional languages and parallelismVhy not program in a conventional language which supports multiple tasks, such as Ada?In a conventional language, the programler must explicitly code the program for parallel evaluation.The behavtour of the program will depend on the scheduling of the tasks, and the programmer must ensure that parallel evaluation does not alter the semantics of the program.The absence of side effects in a functional language means that the execution of one task cannot affect the outcome of the execution of another task.This implies that task administration and synchronisatton are inherently easier for a functional language.Functional programs do not require explicit parallel programming.No extra language constructs are needed to write parallel functional programs, and the result of the program is guaranteed to be independent of task scheduling (though this may have an impact on efficiency).