Graphinators and the duality of SIMD and MIMD

ABSTRACT

Combinator reduction is a well-known implementation technique for executing functional programs. In this paper we present a new method for parallel combinator reduction based on viewing combinators simply as “graph mutators.” We show that each combinator in Turner's standard set can be expressed using two primitive operations on a binary graph — one to alter an edge and one to insert a vertex — and four symmetric variants of them. We call these primitive operations graphinators, and present a single 7-step graphinator sequence which implements the reduction rules for all combinators in the set. This sequence allows redexes involving any of the combinators to be reduced in parallel on a SIMD machine. We have implemented a graph reducer on the Connection Machine based on these results, together with a novel execution strategy called prudent evaluation. Preliminary performance results suggest that our implementation does reasonably well, significantly better than previous efforts, but perhaps still not well enough to be practical. Nevertheless, the approach suggests a new way of thinking about program execution, and we have thoughts on how to improve our implementation.

REFERENCES

• 1: R. Grondalski. A vlsi chip set for a :massively parallel architecture. In IEEE International Solid- State Circuits Conference, pages 198-199,399-400, IEEE, 1987.
• 2: C L Hankin , G L Burn , S L Peyton Jones, A safe approach to parallel combinator reduction, Proc. of the European symposium on programming on ESOP 86, p.99-110, March 1986, Saarbru:9Aicken, Germany
• 3: W. Daniel Hillis, The connection machine, MIT Press, Cambridge, MA, 1986
• 4: P. Hudak. Distributed Graph Marking. Research Report YALEU/DCS/RR-268, Yale University, January 1983.
• 5: Paul Hudak , Benjamin Goldberg, Distributed execution of functional programs using serial combinators, IEEE Transactions on Computers, v.34 n.10, p.881-891, Oct. 1985
• 6: Paul Hudak , Benjamin Goldberg, Experiments in diffused combinator reduction, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.167-176, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802033]
• 7: Paul Hudak , Benjamin Goldberg, Serial combinators: “optimal” grains of parallelism, Proc. of a conference on Functional programming languages and computer architecture, p.382-399, January 1985, Nancy, France
• 8: Paul Hudak , David Kranz, A combinator-based compiler for a functional language, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.122-132, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800523]
• 9: R. J. M. Hughes, Super-combinators a new implementation method for applicative languages, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.1-10, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802129]
• 10: T. Johnsson. The G-machine: an abstract machine for graph reduction. Techn!ical Report, PMG, Department of Computer Science, Chalmers University of Tech., February 1985.
• 11: J. R. Kennaway , M. R. Sleep, Expressions as processes, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.21-28, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802131]
• 12: B. C. Kuszmaul. Simulating Applicative Architectures on the Connection Machine. Master's thesis, M.I.T., May 1986.
• 13: S. Leinwand and J. Goguen. Architectural options for the rewrite rule machine. In Proceedings Seeond International Conference on Supercomputing, Santa Clara, California, May 1987.
• 14: A. G. Ranade, S. N. Bhatt, and S. L. Johnsson. The Fluent Abstract Machine. Technical Report YALEU/DCS/TR-573, Yale University, Department of Computer Science, January 1988.
• 15: Mark Scheevel, NORMA: a graph reduction processor, Proceedings of the 1986 ACM conference on LISP and functional programming, p.212-219, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319864]
• 16: M. Lemaître , M. Castan , M.-H. Durand , G. Durrieu , B. Lecussan, Mechanisms for efficient multiprocessor combinator reduction, Proceedings of the 1986 ACM conference on LISP and functional programming, p.113-121, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319855]
• 17: D.A. Turner. Another algorithm for bracket abstraction. The Journal of Symbolic Logic, 44(2):267-270, June 1979.
• 18: D.A. Turner. A new implementation technique for applicative languages. Software -- Practice and Experience, 9'31-49, 1979.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Algorithms, Design, Languages, Performance