Deadlock-avoidance for streaming applications with split-join structure: Two case studies

Peng Li, Kunal Agrawal, Jeremy Buhler, Roger D. Chamberlain, Joseph M. Lancaster

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

12 Scopus citations

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.

Original languageEnglish
Title of host publicationASAP 10 - 21st IEEE International Conference on Application-Specific Systems, Architectures and Processors, Conference Proceedings
Pages333-336
Number of pages4
DOIs
StatePublished - 2010
Event21st IEEE International Conference on Application-specific Systems, Architectures and Processors, ASAP 2010 - Rennes, France
Duration: Jul 7 2010Jul 9 2010

Publication series

NameProceedings of the International Conference on Application-Specific Systems, Architectures and Processors
ISSN (Print)1063-6862

Conference

Conference21st IEEE International Conference on Application-specific Systems, Architectures and Processors, ASAP 2010
Country/TerritoryFrance
CityRennes
Period07/7/1007/9/10

Keywords

  • BLAST
  • Deadlock avoidance
  • Pseudorandom number generation
  • Streaming computation

Fingerprint

Dive into the research topics of 'Deadlock-avoidance for streaming applications with split-join structure: Two case studies'. Together they form a unique fingerprint.

Cite this