From: Paul H J Kelly
Subject: book -- Functional Programming for Loosely-coupled Multiprocessors
Date:
Message-ID: <758@gould.doc.ic.ac.uk>
I hope it would not be presumptious of me to take this opportunity to
announce the publication of this book, which is a complete rewrite of
my Ph.D. work. It can be ordered now, and will reach the shelves of
select UK bookshops within a couple of weeks. Distribution to the US
and elsewhere may take a little longer.
Functional Programming for Loosely-coupled Multiprocessors
Paul Kelly
In the series 'Research Monographs in Parallel and Distributed
Computing'. Published in April 1989 by Pitman and MIT Press.
ISBN 0-273-0880401.
The blurb on the back cover:
The main subject of this book is the interesting and powerful class of
functional programming languages, and their application to parallel
programming. The reason for choosing such a language is the ease with
which such programs can be manipulated algebraically, and the bulk of
the book is devoted to introducing and demonstrating this in action.
It is through the algebraic manipulation of programs that the problems of
parallel programming are addressed. We retreat from the hope that a
single program will serve for all the different parallel computers we
might wish to use, and instead begin with a single specifying program.
Versions for different target architectures can then be derived by the
application of a toolbox reusable of mathematical transformations, leading
to versions tuned to the various machine structures available.
After giving a thorough introductory grounding to both writing and
manipulating functional programs, this book then illustrates how
these techniques can be used to specify, reason about and implement
parallel programs for a variety of multiprocessor systems, but in
particular a class of loosely-coupled multiprocessors whose operation
can be described by a process network.
The book concludes by introducing an extended functional language in
which the functional program text is augmented with a declarative
description of how processes are partitioned and mapped onto a network
of processing elements. The purpose of these annotations is to
provide an abstract description of the process network specified by
the program so that an efficient mapping of processes to processors
can be carried out by the compiler.
A survey of the contents:
* Chapter 2. Functional Programming:
This chapter introduces functional programming from first
principles. The programming language is presented by means of
examples. Simple techniques are given for manipulating programs
to modify their structure while retaining the same input/output
mapping. These are augmented by a handful of induction rules for
proving generic properties about programs.
The language is based on Miranda and Haskell (a public-domain
language design for which a specification is in preparation.
* Chapter 3. Sequential and Parallel Implementation Techniques:
The aim of this chapter to sketch how our functional
language might be compiled to run efficiently on
a conventional computer, and to examine how this scheme
(graph reduction) might be extended for a tightly-coupled
multiprocessor.
* Chapter 4. Specifying and Deriving Parallel Algorithms:
This chapter examines how parallelism and inter-process
communication are manifest in a functional program script.
Horizontal and vertical parallelism are identified and
examples are given in the form of divide-and-conquer
and pipeline algorithms respectively. The main
emphasis in this chapter is the development of program transformation
techniques. Examples are given of introducing pipeline
parallelism, and of transforming a divide-and-conquer
algorithm into a cyclic ``process network'' program.
This is illustrated by application to a simple ray tracing
program.
* Chapter 5. Distributed Parallel Functional Programming:
We can write programs for which a good placement onto
a loosely-coupled multiprocessor can be made.
This chapter applies a declarative programming language
approach to actually specifying this placement.
It incorporates abstraction mechanisms to give concise
mappings for regular architectures and algorithms.
The notation is illustrated with several examples.
* Appendix A. Proofs and Derivations:
This appendix gives proofs and derivations which would have
cluttered the presentation given in chapter 4.
Although quite dense later on, the earlier material in this chapter
is quite tutorial in nature and might be read concurrently
with Chapter 4 by those more interested in program derivation
and verification than in parallel programming.
* Appendix B. Common Definitions:
This appendix lists widely-used function definitions
for easy reference.
* Appendix C. Programming in a real functional language:
The functional language used in this book is not quite compatible
with any commonly-available language implementation.
This appendix lists the small (and quite innocuous)
differences from Miranda
in order to aid a reader who wishes to experiment.
Each chapter ends with some pointers for the interested reader towards
other books, articles and research papers which
might be of interest.
Includes index and extensive bibliography.
footnote: Miranda is a trademark of Research Software Ltd.
Yours,
Paul Kelly