Efficient Deadlock Avoidance for Streaming Computation with Filtering

Authors

Jeremy Buhler, Computer SciencesFollow
Kunal Agrawal, Washington University in St LouisFollow
Peng Li, Washington University in St LouisFollow
Roger D. Chamberlain, Washington University in St. LouisFollow

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2011

Filename

WUCSE-2011-59.pdf

Technical Report Number

WUCSE-2011-59

Abstract

In this report, we show that deadlock avoidance for streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first give efficient algorithms for dummy interval computation in series-parallel DAGs, then generalize our results to a larger graph family, the CS4DAGs, in which every undirected cycle has exactly one source and one sink. Our results show that, for a large set of application topologies that are both intuitively useful and formalizable, the streaming model with filtering can be implemented safely with reasonable compilation overhead.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7707ZN5

Recommended Citation

Buhler, Jeremy; Agrawal, Kunal; Li, Peng; and Chamberlain, Roger D., "Efficient Deadlock Avoidance for Streaming Computation with Filtering" Report Number: WUCSE-2011-59 (2011). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/63