garbage collection of timestamped data in stampede
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. Channels are not queue-like: threads may produce and consume 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 the garbage collection condition: When can an item in a channel be garbage collected? In this paper we specify precisely Stampede's semantics concerning timestamps, and we describe two associated garbage collection conditions& a weak condition, and a more expensive but stronger condition. We then 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. We conclude with some remarks about the implementation in the Stampede system.
collect timestamp data parallel parallel programming program systems interactive multimedia applications cluster variability thread communication distributed synchronization data structures structure imaging video camera requirements complexity dynamic support real-time paper semantic association concurrency algorithm implementation performance