M.Sc Thesis

M.Sc StudentGavish Yael
SubjectCache-Conscious Garbage Collection for Servers
DepartmentDepartment of Computer Science
Supervisor PROF. 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.