ALICE a multi-processor reduction machine for the parallel evaluation CF applicative languages

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.

REFERENCES

• 1: W. B. Ackerman, A STRUCTURE MEMORY FOR DATA FLOW COMPUTERS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 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.
• 3: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 4: Baron I. The Transputer. In 'The Microprocessor and its Applications', ed. Aspinall D., Cambridge University Press, 1978.
• 5: K. J. Berkling, Reduction languages for reduction machines, Proceedings of the 2nd annual symposium on Computer architecture, p.133-140, January 20-22, 1975
• 6: Browning S. A. The Tree Machine. Ph.D. Thesis, Computer Science Dept., California Institute of Technology, 1980.
• 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.
• 8: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 9: Burstall R.M. Design Consideration for a Functional Programming language. Proc. of Infotech State of the Art Conference, Copenhagen, 1977.
• 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.
• 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.
• 12: Keith L. Clark , Steve Gregory, A relational language for parallel programming, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.171-178, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806776]
• 13: Clark K. L., McCabe F. G. and Gregory S. IC-Prolog Reference Manual. Research Report, Dept. of Computing, Imperial College, London. (Under revision.)
• 14: Darlington J. The Structured Description of Algorithm Derivations. Invited paper. International Symposium on Algorithms, Amsterdam, 1981.
• 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.
• 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.
• 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.
• 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.
• 19: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 20: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 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.
• 22: Carl Hewitt, The Apiary network architecture for knowledgeable systems, Proceedings of the 1980 ACM conference on LISP and functional programming, p.107-117, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802796]
• 23: Kahn G. and McQueen D. Coroutines and Networks of Parallel Processes. Proc. IFIP Congress 77, North Holland Publishing Co., 1977.
• 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.
• 25: Kowalski R. A. Logic as a Programming Language. Proc IFIP Congress 74, *North Holland Publishing Co.,| 1974.
• 26: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 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.
• 28: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 29: Alan Mycroft, The Theory and Practice of Transforming Call-by-need into Call-by-value, Proceedings of the Fourth 'Colloque International sur la Programmation' on International Symposium on Programming, p.269-281, April 22-24, 1980
• 30: Janak H. Patel, Processor-memory interconnections for multiprocessors, Proceedings of the 6th annual symposium on Computer architecture, p.168-177, April 23-25, 1979 [doi>10.1145/800090.802906]
• 31: Reeve M. J. The ALICE Compiler Target Language. Internal Report, Dept. of Computing, Imperial College, London, 1981.
• 32: Sleep M. R. and Burton F. W. Towards a Zero Assignment Parallel Processor. Proc. Second Int. Conference on Distributed Computing Systems, 1980.
• 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.
• 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.
• 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.
• 36: Turner D.A. A New Implementation Technique for Applicative Languages. Software, Practice and Experience, Vol. 9, 1979.
• 37: Turner D.A. Programming Languages - Current and Future Developments. Proc. of Infotech State of the Art Conference, Software Development Techniques, London, 1980.
• 38: Turner D.A. Aspects of the Implementation of Programming Languages. D.Phil. Thesis, University of Oxford, 1981.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Languages, Performance