John Darlington
ABSTRACT
The functional or applicative languages have long been regarded as suitable vehicles for overcoming many of the problems involved in the production and maintenance of correct and reliable software. However, their inherent inefficiences when run on conventional von Neumann style machines have prevented their widespread acceptance. With the declining cost of hardware and the increasing feasibility of multi-processor architectures this position is changing, for, in contrast to conventional programs where it is difficult to detect those parts that may be executed, concurrently, applicative programs are ideally suited to parallel evaluation.
In this paper we present a scheme for the parallel evaluation of a wide variety of applicative languages and provide an overview of the architecture of a machine on which it may be implemented.
First we describe the scheme, which may be characterized as performing graph reduction, at the abstract level and discuss mechanisms that allow several modes of parallel evaluation to be achieved efficiently. We also show how a variety of languages are supported.
We then suggest an implementation of the scheme that has the property of being highly modular; larger and faster machines being built by joining together smaller ones. Performance estimates illustrate that a small machine (of the size that we envisage would form the basic building block of large systems) would provide an efficient desk-top personal applicative computer, while the larger versions promise very high levels of performance Indeed. The machine is designed to be ultimately constructed from a small number of types of VLSI component.
Finally we compare our approach with the other proposes schemes for the parallel evaluation of applicative languages and discuss planned future developments.
- 1.Ackerman W.B. A Structure Memory for Data Flow Computers. Laboratory for Computer Science, MIT, LCS/TR-186, 1977.]] Google Scholar
Digital Library
- 2.Arvind, Gostelow K. P. and Plouffe W. An Asynchronous Programming Language and Computing Machine. University of California (Irvine) Report, Dept. of Computer Science, 1978.]]Google Scholar
- 3.Backus J. Can programming be Liberated from the von Neumann Style?. ACM Turing Award Lecture. CACF Vol. 21 No. 8, Aug. 1978.]] Google ScholarDigital Library
- 4.Baron I. The Transputer. In 'The Microprocessor and its Applications', ed. Aspinall D., Cambridge University Press, 1978.]] Google ScholarDigital Library
- 5.Berkling K. Reduction Languages for Reduction Machines. |Proc. Second Int. Symp. on Computer Architecture,# 1975.]] Google ScholarDigital Library
- 6.Browning S. A. The Tree Machine. Ph.D. Thesis, Computer Science Dept., California Institute of Technology, 1980.]]Google Scholar
- 7.Burstall R.M., MacQueen D. B. and Sannella D.T. HOPE: An Experimental Applicative Language. Internal Report, Dept. of Computer Science, University of Edinburgh, 1980.]]Google Scholar
- 8.Burstall R.M. and Darlington J. A Transformation System for Developing Recursive Programs. JACM Vol. 24 No. 1, Jan. 1977.]] Google ScholarDigital Library
- 9.Burstall R.M. Design Consideration for a Functional Programming language. Proc. of Infotech State of the Art Conference, Copenhagen, 1977.]]Google Scholar
- 10.Burton F.W. and Sleep M. R. Large Symmetrical Processor Networks with Short Communication Paths. School for Computing Studies and Accountancy, University of Fast Anglia, Report CS/80/019/I, 1980.]]Google Scholar
- 11.Campbell R.H., Greenberg I. B. and Miller T. J. Path Pascal User Manual. Dept. of Computer Science, University of Illinois at Champaign-Urbana, 1978.]]Google Scholar
- 12.Clark K. L. and Gregory S. A Relational Language for Parallel Programming. Dept. of computing, Imperial College, London. This conference.]] Google ScholarDigital Library
- 13.Clark K. L., McCabe F. G. and Gregory S. IC-Prolog Reference Manual. Research Report, Dept. of Computing, Imperial College, London. (Under revision.)]]Google Scholar
- 14.Darlington J. The Structured Description of Algorithm Derivations. Invited paper. International Symposium on Algorithms, Amsterdam, 1981.]]Google Scholar
- 15.Dennis J. B., Leung C. K. C. and Misunas D. P. A Highly Parallel Processor Using a Data Flow Machine Language. Laboratory for Computer Science, MIT, CSG Memo 134-1, June 1979.]]Google Scholar
- 16.Friedman D. P. and Wise D. S. CONS Should Not Evaluate Its Arguments. In 'Automata, Language and Programming', eds. Michaelson S. and Milner R., Edinburgh University Press, 1976.]]Google Scholar
- 17.Fuller S. H. and Harbison S. P. The C.mmp Multiprocessor. Dept. of Computer Science, Carnegie-Mellon University. Technical Report CMU-CS-78-146, 1978.]]Google Scholar
- 18.Gurd J. R., Watson I. and Glauert J. R. W. A Multilayered Data Flow Computer Architecture (3rd issue). Internal Report, Dept. of Computer Science, University of Manchester, 1980.]]Google Scholar
- 19.Henderson P. and Morris J.H. A Lazy Evaluator. Proc. Third Annual ACM SIGACT-SIGPLAN Symp. on Principles of Programming Languages, 1976.]] Google ScholarDigital Library
- 20.Henderson P. 'Functional programming'. Prentice-Hall, 1980.]] Google ScholarDigital Library
- 21.Henderson P. Working Material for the Lectures of P. Henderson. Advanced Course on Functional Programming and Its Applications, University of Newcastle Upon Tyne, July 1981.]]Google Scholar
- 22.Hewitt C. The Apiary Network Architecture for Knowledgeable Systems. Proc. of the 1980 LISP Conference, 1980.]] Google ScholarDigital Library
- 23.Kahn G. and McQueen D. Coroutines and Networks of Parallel Processes. Proc. IFIP Congress 77, North Holland Publishing Co., 1977.]]Google Scholar
- 24.Keller R. M., Lindstrom G. and Patil S. An Architecture for a Loosely-Coupled Parallel Processor. Dept. of Computer Science, University of Utah, Tech. Report UUCS-78-105, 1978.]]Google Scholar
- 25.Kowalski R. A. Logic as a Programming Language. Proc IFIP Congress 74, *North Holland Publishing Co.,| 1974.]]Google Scholar
- 26.Kowalski R. A. 'Logic for Problem Solving'. North Holland Publishing Co., 1979.]] Google ScholarDigital Library
- 27.Mago G. A. A Network of Microprocessor to Execute Reduction Languages. Int. Journal of Computer and Information Sciences, Vol. 8 No. 5 and Vol. 8 No. 6, 1979.]]Google Scholar
- 28.Manna Z. 'Mathematical Theory of Computation' McGraw-Hill, 1974.]] Google ScholarDigital Library
- 29.Mycroft A. Theory and Practice of Transforming Call By Need Into Call By Value. Fourth Int. Symp. on Programming, 1980.]] Google ScholarDigital Library
- 30.Patel J.H. Processor-Memory Interconnections for Multiprocessors. Proc. Sixth Int. Symp. on Computer Architecture, 1979.]] Google ScholarDigital Library
- 31.Reeve M. J. The ALICE Compiler Target Language. Internal Report, Dept. of Computing, Imperial College, London, 1981.]]Google Scholar
- 32.Sleep M. R. and Burton F. W. Towards a Zero Assignment Parallel Processor. Proc. Second Int. Conference on Distributed Computing Systems, 1980.]]Google Scholar
- 33.Swan R. S., Fuller S.H. and Siewiorek D. P. Cm*: A Modular Multi-Microprocessor. AFIPS Conf. Proc. Vol. 46, National Computer Conference, 1977.]]Google ScholarDigital Library
- 34.Treleaven P. C. et al. Data Driven and Demand Driven Computer Architecture. Computing Laboratory, University of Newcastle upon Tyne, Internal Report ARM/15, 1980.]]Google Scholar
- 35.Proc. of the Joint SRC / University of Newcastle upon Tyne Workshop on VLSI: Machine Architecture and Very High Level Languages. ed. Treleaven P. C. University of Newcastle upon Tyne, Computing laboratory, Technical Report series, No. 156, 1980.]]Google Scholar
- 36.Turner D.A. A New Implementation Technique for Applicative Languages. Software, Practice and Experience, Vol. 9, 1979.]]Google Scholar
- 37.Turner D.A. Programming Languages - Current and Future Developments. Proc. of Infotech State of the Art Conference, Software Development Techniques, London, 1980.]]Google Scholar
- 38.Turner D.A. Aspects of the Implementation of Programming Languages. D.Phil. Thesis, University of Oxford, 1981.]]Google Scholar
Index Terms
- ALICE a multi-processor reduction machine for the parallel evaluation CF applicative languages
Recommendations
An applicative compiler for a parallel machine
SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler constructionA compiler for the applicative language HOPE is described. The compiler is itself written in HOPE and generates a machine independent compiler target language, suitable for execution on the parallel reduction machine ALICE. The advantages of writing a ...
Comparing Parallel Functional Languages: Programming and Performance
This paper presents a practical evaluation and comparison of three state-of-the-art parallel functional languages. The evaluation is based on implementations of three typical symbolic computation programs, with performance measured on a Beowulf-class ...
Compiling machine-independent parallel programs
Initial evidence is presented that explicitly parallel, machine-independent programs can automatically be translated into parallel machine code that is competitive in performance with hand-written code.The programming language used is Modula-2*, an ...
Comments