Garbage Collection of Timestamped Data in Stampede

Rishiyur S. Nikhil and Umakishore Ramachandran

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


Stampede is a parallel programming system to facilitate the programming of interactive multimedia applications on clusters of SMPs. In a Stampede application, a variable number of threads can communicate data items to each other via "channels", which are distributed, synchronized data structures containing timestamped data such as images from a video camera. Threads may produce and consume channel items out of timestamp order; they may produce and consume items sparsely (skipping timestamps), and multiple threads (including newly created threads) may consume an item in a channel. These flexibilities are required due to the complex dynamic parallel structure of applications, to support increased parallelism, and because of real-time requirements. Under these circumstances, a key issue is: "When can an item in a channel be garbage collected?" In this paper we specify precisely Stampede's semantics concerning timestamps, and derive two associated garbage collection conditions-- a weak condition, and a computationally more expensive but stronger condition. We describe a distributed, concurrent algorithm that implements these two GC conditions. We present performance numbers that show little or no application-level performance penalty to using this algorithm for aiding automatic garbage collection in a cluster of SMPs. We conclude with some thoughts on future work.