Efficient parallel global garbage collection on massively parallel computers

On distributed-memory high-performance massively parallel computers (MPPs) where processors are interconnected by an asynchronous network, efficient garbage collection (GC) becomes difficult, due to inter-node references and references within pending, unprocessed messages. Our parallel global GC algorithm (1) takes advantage of reference locality, (2) efficiently traverses references over nodes, (3) admits a minimum pause time for the ongoing computations, and (4) has been shown to scale up to 1024-node MPPs. The algorithm employs a global weight counting scheme to substantially reduce message traffic. Two methods for confirming the arrival of pending messages are used: one counts the number of messages and the other uses network `bulldozing´. Performance evaluations in actual implementations on a multicomputer with from 32 to 1024 nodes, the Fujitsu AP1000, reveals various favorable properties of the algorithm