TY - GEN

T1 - Efficient deadlock avoidance for streaming computation with filtering

AU - Buhler, Jeremy D.

AU - Agrawal, Kunal

AU - Li, Peng

AU - Chamberlain, Roger D.

PY - 2012

Y1 - 2012

N2 - Parallel streaming computations have been studied extensively, and many languages, libraries, and systems have been designed to support this model of computation. In particular, we consider acyclic streaming computations in which individual nodes can choose to filter, or discard, some of their inputs in a data-dependent manner. In these applications, if the channels between nodes have finite buffers, the computation can deadlock. One method of deadlock avoidance is to augment the data streams between nodes with occasional dummy messages; however, for general DAG topologies, no polynomial time algorithm is known to compute the intervals at which dummy messages must be sent to avoid deadlock. In this paper, we show that deadlock avoidance for streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first present a new method where each dummy message is tagged with a destination, so as to reduce the number of dummy messages sent over the network. We then give efficient algorithms for dummy interval computation in seriesparallel DAGs. We finally generalize our results to a larger graph family, which we call the CS4 DAGs, in which every undirected Cycle is Single-Source and Single-Sink (CS4). 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 overhead.

AB - Parallel streaming computations have been studied extensively, and many languages, libraries, and systems have been designed to support this model of computation. In particular, we consider acyclic streaming computations in which individual nodes can choose to filter, or discard, some of their inputs in a data-dependent manner. In these applications, if the channels between nodes have finite buffers, the computation can deadlock. One method of deadlock avoidance is to augment the data streams between nodes with occasional dummy messages; however, for general DAG topologies, no polynomial time algorithm is known to compute the intervals at which dummy messages must be sent to avoid deadlock. In this paper, we show that deadlock avoidance for streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first present a new method where each dummy message is tagged with a destination, so as to reduce the number of dummy messages sent over the network. We then give efficient algorithms for dummy interval computation in seriesparallel DAGs. We finally generalize our results to a larger graph family, which we call the CS4 DAGs, in which every undirected Cycle is Single-Source and Single-Sink (CS4). 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 overhead.

KW - Deadlock avoidance

KW - Graph theory

KW - Streaming computation

UR - http://www.scopus.com/inward/record.url?scp=84858405543&partnerID=8YFLogxK

U2 - 10.1145/2145816.2145846

DO - 10.1145/2145816.2145846

M3 - Conference contribution

AN - SCOPUS:84858405543

SN - 9781450311601

T3 - Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP

SP - 235

EP - 246

BT - PPoPP'12 - Proceedings of the 2012 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Y2 - 25 February 2012 through 29 February 2012

ER -