Technical Report MSC-2011-02

Title: Scalable Garbage Collection on Highly Parallel Platforms
Authors: Katherine Barabash
Supervisors: Assoc. Prof. Erez Petrank
Abstract: The computing landscape is changing rapidly in recent years. On the one hand, the pervasiveness of multiprocessor and multicore hardware requires the software to be able to take advantage of the increasingly massive hardware parallelism. On the other hand, the growing complexity of the modern software application domains makes runtime language environments more popular as a major software development tool. It is predicted that these trends will progress: we can expect runtime language systems having to sustain highly complex and memory demanding workloads on servers with hundreds of processor cores in the near future. In this work, we have investigated whether a garbage collector, being a major part of the modern runtime language environment, is able to run efficiently on highly parallel hardware platforms of tomorrow. Our hypothesis was that the structure of the live objects graph in a garbage collected heap can influence the ability of a collector to scale. In particular, certain, sequential in nature, patterns in the live objects graph structure can prevent the tracing garbage collector from scaling when tracing through the object graph. We have examined the object graphs created by all the considered applications and measured object graph shape properties such as depth and width. We have devised a measure that can be used to evaluate the amount of tracing scalability the object graph allows for. We have used this measure, the idealized trace utilization, to evaluate applications in terms of their ability to sustain parallel tracing without causing it to become serial. Some of the applications we have investigated exhibited problematic object graph shapes and scored poor idealized trace utilization measure readings. Having these results, we have studied two approaches for alleviating the scalability problems caused by the object graph shapes. The first approach is modifying the application’s object graph shape by adding new inter object references, invisible to the application but useful for the tracing threads. The second approach is modifying the tracing process by allowing idle tracer threads to pick additional tracing roots in attempt to obtain more tracing work. For each approach, we have designed and prototyped one specific solution. We have evaluated each solution’s influence on the object graph shape of all the applications in our benchmarks set. In this thesis, we present and analyze the results obtained by both approaches. More promising results were achieved by the method of adding new references to the application’s object graph.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2011
To the main CS technical reports page

Computer science department, Technion