Paper Info
Title
Deadlock-avoidance for streaming applications with split-join structure: Two case studies
Abstract
Streaming is a highly effective paradigm for expressing parallelism in high-throughput applications. A streaming computation is a network of compute nodes connected by unidirectional FIFO channels. When these computations are mapped onto real parallel platforms, however, some computations, especially ones in which some nodes act as filters, can deadlock the system due to finite buffering on channels. In this paper, we focus on streaming computations which contain a commonly used structure called split-join. Based on our previous work, we propose two correct deadlock-avoidance algorithms, named the Propagating Algorithm and the Non-propagating Algorithm. Our evaluation of two representative applications, biological sequence alignment and random number generation, shows that the Non-propagating Algorithm has very small communication overhead. For systems with large buffers or a low filtering ratio, the communication overhead of the Non-propagating Algorithm is negligible.
Year
DOI
Venue
2010
10.1109/ASAP.2010.5540957
ASAP
Keywords
Field
DocType
blast,deadlock avoidance,pseudorandom number generation,streaming computation,synchronization,indexes,random number generation,topology,generators,sequence alignment,filtering,computational modeling,application software,high throughput,pseudorandom number generator,computer networks,parallel processing,computer science,concurrent computing
Synchronization,FIFO (computing and electronics),Computer science,Deadlock,Parallel computing,Filter (signal processing),Communication channel,Random number generation,Streaming computation,Computation,Distributed computing
Conference
ISSN
ISBN
Citations 
2160-0511 E-ISBN : 978-1-4244-6965-9
978-1-4244-6965-9
5
PageRank 
References 
Authors
0.46
9
5
Name
Order
Citations
PageRank
Peng Li18111.75
Kunal Agrawal268750.08
Jeremy Buhler382193.45
Roger D. Chamberlain461665.36
Joseph M. Lancaster51048.88