| dc.description.abstract | This thesis presents cache performance analysis of the Chronological Garbage Collection
Algorithm used in LVM system. LVM is a new Logic Virtual Machine for Prolog. It
adopts one stack policy for all dynamic memory requirements and cooperates with an
efficient garbage collection algorithm, the Chronological Garbage Collection, to recycle
space, not as a deliberate garbage collection operation, but as a natural activity of the
LVM engine to gather useful objects. This algorithm combines the advantages of the
traditional copying, mark-compact, generational, and incremental garbage collection
schemes.
In order to determine the improvement of cache performance under our garbage-
collection algorithm, we developed a simulator to do trace-driven cache simulation.
Direct-mapped cache and set-associative cache with different cache sizes, write policies,
block sizes and set associativities are simulated and measured. A comparison of LVM
and SICStus 3.1 for the same benchmarks was performed.
From the simulation results, we found important factors influencing the
performance of the CGC algorithm. Meanwhile, the results from the cache simulator fully
support the experimental results gathered from the LVM system: the cost of CGC Is
almost paid by the improved cache performance. Further, we found that the memory
reference patterns of our benchmarks share the same properties: most writes are for
allocation and most reads are to recently written objects. In addition, the results also
showed that the write-miss policy can have a dramatic effect on the cache performance of
the benchmarks and a write-validate policy gives the best performance. The comparison
shows that when the input size of benchmarks is small, SICStus is about 3-8 times faster
than LVM. This is an acceptable range of performance ratio for comparing a binary-code
engine against a byte-code emulator. When we increase the input sizes, some benchmarks
maintain this performance ratio, whereas others greatly narrow the performance gap and
at certain breakthrough points perform better than their counterparts under SICStus. | |
