Show simple item record

dc.contributor.authorHarel, Nissimen_US
dc.contributor.authorMandviwala, Hasnain A.
dc.contributor.authorKnobe, Kathleen
dc.contributor.authorRamachandran, Umakishore
dc.date.accessioned2005-06-17T17:38:57Z
dc.date.available2005-06-17T17:38:57Z
dc.date.issued2002en_US
dc.identifier.urihttp://hdl.handle.net/1853/6524
dc.description.abstractStampede is a parallel programming system to support computationally demanding applications including interactive vision, speech and multimedia collaboration. The system alleviates concerns such as communication, synchronization, and buffer management in programming such real-time stream-oriented applications. A coarse-grain dataflow graph is often a convenient representation of such computations. Threads are loosely connected by channels which hold streams of items, each identified by a timestamp. A thread may read a timestamped item from one channel, perform some analysis on that item and write an item with that same timestamp onto a different channel. Useful work is signified by a timestamp making its way through the entire pipeline of threads and channels. Because threads operate at different speeds, some timestamps will not make their way through the entire pipeline. There are two performance concerns when programming with Stampede. The first concern is space, namely, ensuring that memory is not wasted on a timestamp (i.e. items bearing this timestamp) that is not fully processed. The second concern is time, namely, ensuring that processing resource is not wasted on a timestamp that is not fully processed. Prior work on Stampede, addressed these concerns separately. Our earlier work on static scheduling ensures that the pipeline only works on timestamps that are fully processed. However, this technique applies only for a restricted set of task graphs. Similarly, our earlier work on garbage collection identifies and removes garbage items from channels. Due to the global nature of this algorithm there can be a significant wastage of memory resource with this approach. In this paper we introduce a single unifying framework, dead timestamp identification, that addresses both the space and time concerns simultaneously, and does not have some of the limitations of our prior work. Dead timestamps on a channel represent garbage. Dead timestamps at a thread represent computations that need not be performed. This framework has been implemented in the Stampede system. Experimental results showing the space advantage of this framework are presented. Using a color-based people tracker application, we show that the space advantage can be significant (up to 40\%) compared to the previous techniques for garbage collection in Stampede.en_US
dc.format.extent525031 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCC Technical Report; GIT-CC-02-08en_US
dc.subjectParallel programs
dc.subjectThread schedulers
dc.subjectData channels
dc.subjectTimestamps
dc.subjectScheduling
dc.subjectGarbage collection
dc.titleDead Timestamp Identification in Stampedeen_US
dc.typeTechnical Reporteng_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record