TY - GEN
T1 - Deadlock-avoidance for streaming applications with split-join structure
T2 - 21st IEEE International Conference on Application-specific Systems, Architectures and Processors, ASAP 2010
AU - Li, Peng
AU - Agrawal, Kunal
AU - Buhler, Jeremy
AU - Chamberlain, Roger D.
AU - Lancaster, Joseph M.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
KW - BLAST
KW - Deadlock avoidance
KW - Pseudorandom number generation
KW - Streaming computation
UR - http://www.scopus.com/inward/record.url?scp=77955914899&partnerID=8YFLogxK
U2 - 10.1109/ASAP.2010.5540957
DO - 10.1109/ASAP.2010.5540957
M3 - Conference contribution
AN - SCOPUS:77955914899
SN - 9781424469673
T3 - Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors
SP - 333
EP - 336
BT - ASAP 10 - 21st IEEE International Conference on Application-Specific Systems, Architectures and Processors, Conference Proceedings
Y2 - 7 July 2010 through 9 July 2010
ER -