On Bounding Time and Space for Multiprocessor Garbage Collection

In the Proceedings of the ACM SIGPLAN Symposium on Programming Language Design and Implementation (PLDI), May 1999.

82k compressed postscript / 243k PDF

Abstract:

This paper presents the first multiprocessor garbage collection algorithm with provable bounds on time and space. The algorithm is a real-time shared-memory copying collector. We prove that the algorithm requires at most 2 (R(1 + 2/k) + N + 5PD) memory locations, where P is the number of processors, R is the maximum reachable space during a computation (number of locations accessible from the root set), N is the maximum number of reachable objects, D is the maximum depth of any data object, and k is a parameter specifying how many locations are copied each time a location is allocated. Furthermore we show that client threads are never stopped for more than time proportional to k non-blocking machine instructions. The bounds are guaranteed even with arbitrary length arrays. The collector only requires write-barriers (reads are unaffected by the collector), makes few assumptions about the threads that are generating the garbage, and allows them to run mostly asynchronously.

@inproceedings{BlCh99,
	author = "Guy Blelloch and Perry Cheng",
	title = "On Bounding Time and Space for Multiprocessor Garbage Collection",
	booktitle = "Proc. ACM SIGPLAN Conference on Programming Language Design and
                Implementation {(PLDI)}", 
	month = may,
	pages = "104--117",
	year = 1999}