CACHE BEHAVIOR OF COMBINATOR GRAPH REDUCTION

The results of cache-simulation experiments with an abstract machine f or reducing combinator graphs are presented. The abstract machine, cal led TIGRE, exhibits reduction rates that, for similar kinds of combina tor graphs on similar kinds of hardware, compare favorably with previo usly reported techniques. Furthermore, TIGRE maps easily and efficient ly onto standard computer architectures, particularly those that allow a restricted form of self-modifying code. This provides some indicati on that the conventional "stored program" organization of computer sys tems is not necessarily an inappropriate one for functional programmin g 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-dri ven cache simulations of a TIGRE graph reducer running on a reduced in struction-set computer are conducted. The results of these simulations are presented with the following hardware-cache parameters varied: ca che size, block size, associativity, memory update policy, and write-a llocation policy. To begin with, the cache organization of a commercia lly available system is used and then the performance sensitivity with respect to variations of each parameter are measured. From the result s 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.