|M.Sc Student||Gavish Yael|
|Subject||Cache-Conscious Garbage Collection for Servers|
|Department||Department of Computer Science||Supervisor||Professor Erez Petrank|
As the gap between
processor speed and main memory access speed is growing, the importance of good
cache behavior to overall program execution time is increasing. In this work we
study ways to reduce program cache misses using garbage collection. Chililmbi
and Larus [CL] proposed an algorithm meant to improve the cache performance of
garbage-collected programs by rearranging data objects at runtime. Their
algorithm detects objects which are accessed closely in time and places them
next to each other in memory. This increases the objects' likelihood to reside in the same cache block,
thereby reducing the overall cache miss rate of the program. The algorithm was
written for and tested in a single-threaded environment.
In this work we adapt the algorithm to a multi-threaded, multi-processor environment. We implement it in a commercial VM (Sun's Java HotSpotä Virtual Machine), and discuss in detail the implementation challenges and the necessary modifications to the algorithm in this environment. We also propose several enhancements and variation on the basic algorithm to reduce cache misses in an SMP system. Finally we demonstrate a way to reduce the performance hit of the algorithm in programs that do not behave according to the basic assumptions behind it.