An Architecture for Combinator Graph Reduction (TIGRE)

ABSTRACT

(Abstract from 1992 TOPLAS paper)

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 sub-block placement), and copy-back memory updates.

BOOK:

Koopman, P., An Architecture for Combinator Graph Reduction, Academic Press, 1990.
(Note: this is the book version of my thesis)
```
   
```

My thesis is now available on-line as Adobe Acrobat (.pdf) files.
- Abstract
- Contents
- Chapter 1
- Chapter 2
- Chapter 3
- Chapter 4
- Chapter 5
- Chapter 6
- Chapter 7
- Chapter 8
- Appendix A
- Appendix B
- References
- Index

SOFTWARE:

Download my thesis software for Borland Turbo C & GNU C. (TIGRE.ZIP 121K)
By downloading this software, the user agrees to accept this software entirely as-is, with absolutely no warranty whatsoever, expressed or implied. The responsibility for ensuring fitness and correctness for any purpose lies entirely with the user.

PAPERS:

Koopman, P., Lee, P. & Siewiorek, D., "Cache Behavior of Combinator Graph Reduction", Transactions on Programming Languages and Systems, 14(2) 265-297, April 1992.
Koopman, P., Lee, P. & Siewiorek, D., "Architectural Considerations for Combinator Graph Reduction," Lee, P. (ed.) Topics In Advanced Language Implementation, MIT Press, 1991, pp. 369-95.
Koopman, P. "TIGRE: Combinator Graph Reduction on the RTX 2000," 1990 Rochester Forth Conference, pp. 82-86, June 1990.
Koopman, P., Lee, P. & Siewiorek, D., "Cache Performance of Combinator Graph Reduction", 1990 Int. Conf. on Computer Languages, March 12-15, 1990.
Koopman, P. & Lee, P., "A Fresh Look at Combinator Graph Reduction", Proc. of the 1989 SIGPLAN Conf. on Programming Language Design and Implementation, June 21-23, 1989.
Lee, P. & Koopman, P., Compiling for Direct Execution of Combinator Graphs, Ergo report, Carnegie Mellon University, Pittsburgh, 1989.

POINTERS:

Simon Peyton Jones home page
(My publications compare TIGRE to some of his work)

Phil Koopman -- koopman@cmu.edu