Cache behavior of combinator graph reduction

ABSTRACT

The results of cache-simulation experiments with an abstract machine for reducing combinator graphs are presented. The abstract machine, called TIGRE, exhibits reduction rates that, for similar kinds of combinator graphs on similar kinds of hardware, compare favorably with previously reported techniques. Furthermore, TIGRE maps easily and efficiently onto standard computer architectures, particularly those that allow a restricted form of self-modifying code. This provides some indication that the conventional "stored program" organization of computer systems is not necessarily an inappropriate one for functional programming language implementations. This is not to say, however, that present day computer systems are well equipped to reduce combinator graphs. In particular, the behavior of the cache memory has a significant effect on performance. In order to study and quantify this effect, trace-driven cache simulations of a TIGRE graph reducer running on a reduced instruction-set computer are conducted. The results of these simulations are presented with the following hardware-cache parameters varied: cache size, block size, associativity, memory update policy, and write-allocation policy. To begin with, the cache organization of a commercially available system is used and then the performance sensitivity with respect to variations of each parameter are measured. From the results of the simulation study, a conclusion is made that combinator-graph reduction using TIGRE runs most efficiently when using a cache memory with an allocate-on-write-miss strategy, moderately large block size (preferably with subblock placement), and copy-back memory updates.

REFERENCES

• 1: S. Abramsky , C. Hankin, Abstract interpretation of declarative languages, Halsted Press, New York, NY, 1987
• 2: AUGUSTEIJN, A., AND VAN DER HOEVEN, G. Combinatorgraphs as selLreducing programs. Tech. Rep. Univ. of Utrecht, 1984.
• 3: Lennart Augustsson, A compiler for lazy ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.218-227, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802038]
• 4: 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]
• 5: BARENDREGT, H.P. The Lambda Calculus: Its Syntax and Semant,cs. Elsevier, New York, 1981.
• 6: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 7: BURL~Y, R. An overview of the four systems in the VAX 8800 family. Digit. Tech. J. 4 (Feb. 1987), 10-19.
• 8: G. L. Burn , S. L. Peyton Jones , J. D. Robson, The spineless G-machine, Proceedings of the 1988 ACM conference on LISP and functional programming, p.244-258, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62717]
• 9: DIGITAL EQUIPMENT CORPORATION. DECstatmn 3100 Techmcal Overview (EZ-J4052-28). Maynard, Mass., 1989.
• 10: John Fairbairn , Stuart Wray, TIM: A simple, lazy abstract machine to execute supercombinators, Proc. of a conference on Functional programming languages and computer architecture, p.34-45, October 1987, Portland, Oregon, United States
• 11: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 12: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 13: Mark D. Hill , Alan Jay Smith, Experimental evaluation of on-chip microprocessor cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.158-166, January 1984
• 14: HUDAK, P., AND WADLER, P. Report on the Programmmg Language Haskell, Verswn 1.0, Res Rep. YALEU/DCS/RR-777, Apr. 1990.
• 15: 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]
• 16: Thomas Johnsson, Efficient compilation of lazy evaluation, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.58-69, June 17-22, 1984, Montreal, Canada
• 17: KABAKIBO, A., MILUTINOVIC, V., SILBEY, A., AND FURHT B. A survey of cache memory in modern microcomputer and minicomputer systems. In Tutorial: Computer Architecture D Gajski, V. Milutinovic, H. Siegel, and B Furht, Eds. IEEE Computer Society Press, 1987, pp. 210-227.
• 18: Philip John Koopman, Jr., An architecture for combinator graph reduction, Academic Press Professional, Inc., San Diego, CA, 1990
• 19: P. J. Koopman, Jr. , P. Lee, A fresh look at combinator graph reduction, ACM SIGPLAN Notices, v.24 n.7, p.110-119, July 1989
• 20: KOOPMAN, P., LES, P, AND SIEWIO~EF.. Cache Performance of Combinator Graph Reduction In Proceedings of the 1990 International Conference on Computer Languages (New Orleans, Mar. 1990), IEEE, pp. 39-48.
• 21: A. C. Norman, Faster combinator reduction using stock hardware, Proceedings of the 1988 ACM conference on LISP and functional programming, p.235-243, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62716]
• 22: S. L. Payton Jones, FLIC—a functional language intermediate code, ACM SIGPLAN Notices, v.23 n.8, p.30-48, August 1988 [doi>10.1145/47907.47910]
• 23: Simon L. Peyton Jones , Chris Clack , John Salkild , Mark Hardie, GRIP—A high-performance architecture for parallel graph reduction, Proc. of a conference on Functional programming languages and computer architecture, p.98-112, October 1987, Portland, Oregon, United States
• 24: Simon L. Peyton Jones , Jon Salkild, The spineless tagless G-machine, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.184-201, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99385]
• 25: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 26: PI~TSBURG~ SUPERCOMPUTE~ CENTER. Faczlities and Serwces Guide. Pittsburgh, Penn., 1989.
• 27: S. Prybylski , M. Horowitz , J. Hennessy, Performance tradeoffs in cache design, Proceedings of the 15th Annual International Symposium on Computer architecture, p.290-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 28: 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]
• 29: SIEWlOREK, D., AND KOOPMAN, P. A Case Study of a Parallel, Vector Workstatlon: The Titan Architecture. Academic Press, Boston. In press.
• 30: SMETSERS, J. E. W. Compiling Clean to abstract ABC-machine code. Tech. Rep. 89-20, Univ. of Nijmegen, 1989.
• 31: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 32: STALLMAN, R. GNU Project C Compiler. In UNIX Programmer's Manual. On-line system documentation, Unix version 4.3, 1988.
• 33: STOYE, W. The Implementation of Functional Languages using Custom Hardware, Tech. Rep. No. 81, Univ. of Cambridge Computer Laboratory, 1984.
• 34: TURNEa, D.A. SASL Reference Manual. Univ. of St. Andrews, 1976.
• 35: TURNER, D. A. A new implementation technique for applicative languages. Software-- Practice and Experience 9, I (Jan. 1979), 31-49.
• 36: TUaNER, D.A. Another algorithm for bracket abstraction. J. Symbolic Logic. 44, 2 (1979), 67-270.
• 37: Jean Vuillemin, Exact real computer arithmetic with continued fractions, Proceedings of the 1988 ACM conference on LISP and functional programming, p.14-27, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62681]
• 38: WRAY, S. C., AND FAIRBAIRN, J. Non-strict languages--Programming and implementation. Draft, Oct. 16, 11988.
• 39: WRAY, S.C. Private communication, Oct. 24, 1988.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages
      D.3.4 Processors
          Subjects: Interpreters; Compilers

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
abstract machine, combinators, graph reduction, self-modifying code