Stream computing is a popular paradigm for parallel and distributed computing, where compute nodes are connected by first-in first-out data channels. Each channel can be considered as a concatenation of several data buffers, including an output buffer for the sender and an input buffer for the receiver. The configuration of buffer sizes impacts the performance as well as the correctness of the application. In this article, we focus on application deadlocks that are caused by incorrect configuration of buffer sizes. We describe three types of deadlock in streaming applications, categorized by how they can be created. To avoid them, we first prove necessary and sufficient conditions for deadlock-free computations; then based on the theorems, we propose both compile-time and runtime solutions for deadlock avoidance.
BeardJCChamberlainRD (2013) Analysis of a simple approach to modeling performance for streaming data applications. In: 21st Int’l symposium on modeling, analysis and simulation of computer and telecommunication systems (ed KellenbergerP), San Francisco, CA, 14–16 August 2013, pp. 345–349. Piscataway, NJ: IEEE.
2.
BuckJT (1993) Scheduling dynamic dataflow graphs with bounded memory using the token flow model. PhD Thesis, University of California, Berkeley.
3.
BuckJT (1994) Static scheduling and code generation from dynamic dataflow graphs with integer-valued control streams. In: Asilomar conference on signals, systems, and computers (ed SinghA), Pacific Grove, CA, 31 October–2 November 1994, pp. 508–513. Los Alamitos, CA: IEEE Computer Society Press.
4.
BuhlerJDAgrawalKLiPet al. (2012) Efficient deadlock avoidance for streaming computation with filtering. In: Proceedings of 17th ACM SIGPLAN symposium on principles and practice of parallel programming (ed RamanujamJ), New Orleans, LA, 25–29 February 2012, pp. 235–246. New York, NY: ACM.
5.
ChandyKMMisraJ (1982) A distributed algorithm for detecting resource deadlocks in distributed systems. In: ACM Symposium on principles of distributed computing (eds ProbertRLFischerMSantoroN), Ottawa, Canada, 18–20 August 1982, pp. 157–164. New York, NY: ACM.
6.
ChandyKMMisraJHaasLM (1983) Distributed deadlock detection. ACM Trans Comput Syst1(2): 144–156.
7.
DallyWJAokiH (1993) Deadlock-free adaptive routing in multicomputer networks using virtual channels. IEEE Trans Parallel Distrib Syst4(4): 466–475.
HeBYangMGuoZet al. (2010) Comet: batched stream processing for data intensive distributed computing. In: Proceedings of the 1st ACM symposium on cloud computing (eds HellersteinJMChaudhuriSRosenblumM), Indianapolis, IN, 10–11 June 2010, pp. 63–74. New York, NY: ACM.
12.
HirzelMSouléRSchneiderSet al. (2014) A catalog of stream processing optimizations. ACM Comput Surveys (CSUR)46(4): 46.
13.
KahnG (1974) The semantics of simple language for parallel programming. In: IFIP Congress (ed RosenfeldJL), Stockholm, Sweden, 5–10 August 1974, pp. 471–475. Amsterdam: North-Holland.
LeeEAMesserschmittDG (1987a) Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans Comput36(1): 24–35.
16.
LeeEAMesserschmittDG (1987b) Synchronous data flow. Proc IEEE75(9): 1235–1245.
17.
LiPAgrawalKBuhlerJet al. (2014) Orchestrating safe streaming computations with precise control. In: International workshop on extreme scale computing application enablement—modeling and tools, in conjunction with ICPADS’14, Hsinchu, Taiwan, 16–19 December 2014. Piscataway, NJ: IEEE.
18.
LiPAgrawalKBuhlerJet al. (2010a). Deadlock avoidance for streaming computations with filtering. In: Proceedings of the 22nd ACM symposium on parallelism in algorithms and architectures (eds der HeideFriedhelm Meyer aufPhillipsC), Thira, Santorini, Greece, 13–15 June 2010, pp. 243–252. New York, NY: ACM.
19.
LiPAgrawalKBuhlerJet al. (2010b) Deadlock-avoidance for streaming applications with split-join structure: two case studies. In: IEEE International conference on application-specific systems, architectures and processors (ed CharotF), Rennes, France, 7–9 July 2010, pp. 333–336. Los Alamitos, CA: IEEE Computer Society Press.
20.
LiPBeardJCBuhlerJ (2015) Deadlock-free buffer configuration for stream computing. In: Proceedings of the sixth international workshop on programming models and applications for multicores and manycores, PMAM ‘15, (ed BalajiP), San Francisco, CA, 7–8 February 2015, pp. 164–169. New York, NY: ACM.
21.
LiPBuhlerJ (2013) Polyhedral constraints for bounded-memory execution of synchronized filtering dataflow. In: Data-flow execution models for extreme scale computing (DFM) Edinburgh, Scotland, 8 September 2013, pp. 29–37. Piscataway, NJ: IEEE.
22.
LiebeherrJAkyildizIF (1995) Deadlock properties of queueing networks with finite capacities and multiple routing chains. Queueing Syst20(3–4): 409–431.
23.
LohrmannBWarnekeDKaoO (2012) Massively-parallel stream processing under qos constraints with nephele. In: Proceedings of the 21st international symposium on high-performance parallel and distributed computing (ed EpemaD), Delft, the Netherlands, 18–22 June 2012, pp. 271–282. New York, NY: ACM.
24.
MaxiaguineAKünzliSChakrabortySet al. (2004) Rate analysis for streaming applications with on-chip buffer constraints. In: Proceedings of the 2004 Asia and South pacific design automation conference Yokohama, Japan, 27–30 January 2004, pp. 131–136. Piscataway, NJ: IEEE.
25.
WarshallS (1962) A theorem on boolean matrices. J ACM9(1): 11–12.
26.
WelfordBP (1962) Note on a method for calculating corrected sums of squares and products. Technometrics4(3): 419–420.
27.
ZahariaMDasTLiHet al. (2013) Discretized streams: fault-tolerant streaming computation at scale. In: Proceedings of the twenty-fourth ACM symposium on operating systems principlesFarmington, PA, 3–6 November 2013, pp. 423–438. New York, NY: ACM.
