A new approach to parallelising tracing algorithms

Abstract

Tracing algorithms visit reachable nodes in a graph and are central to activities such as garbage collection, marshalling etc. Traditional sequential algorithms use a worklist, replacing a nodes with their unvisited children. Previous work on parallel tracing is processor-oriented in associating one worklist per processor: worklist inser-tion and removal requires no locking, and load balancing requires only occasional locking. However, since multiple queues may con-tain the same node, significant locking is necessary to avoid con-current visits by competing processors. This paper presents a memory-oriented solution: memory is par-titioned into segments and each segment has its own worklist con-taining only nodes in that segment. At a given time at most one pro-cessor owns a given worklist. By arranging separate single-reader-single-writer forwarding queues to pass nodes from processor i to processor j we can process objects in an order that gives lock-free mainline code and improved locality of reference. This refactoring is analogous to the way in which a compiler changes an iteration space to eliminate data dependencies. While it is clear that our solution can be more effective on NUMA systems, and even necessary when processor-local memory may not be addressed from other processors, slightly surprisingly, it often gives significantly better speed-up on modern multi-cores architectures too. Using caches to hide memory latency loses much of its effectiveness when there is significant cross-processor mem-ory contention or when locking is necessary.