phjk@doc.ic.ac.uk (Paul H J Kelly) (04/08/89)
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