Automated extraction of scenario sequences from disciplined dataflow networks

Analysing deadlock-freedom, boundedness and realtime constraints are crucial steps in the design of embedded streaming applications. Dataflow models of computation are often used to analyse such properties at design-time. To that end, scenario-based dataflow techniques isolate the individual operating scenarios of a dynamic application and analyse the executions of the possible scenario sequences. These techniques have rigorous analytical methods to verify consistency and realtime constraints. To exploit these benefits, identification of all scenarios and scenario sequences is required. This is challenging because of the large number of possible scenarios in modern-day dynamic applications. Manual construction is generally time-consuming and error-prone. In this paper, we address this challenge with an automated approach that extracts a scenario-based analysis model for a class of parallel implementations, which we call Disciplined Dataflow Network (DDN). DDN always guarantees construction of a scenario-based analysis model and enables automating the extraction process. The extraction process identifies all possible scenarios of a DDN and employs state-space enumeration to determine all possible sequences of executions of these scenarios. The approach is demonstrated for the CAL actor language and has been implemented in an openly available CAL compiler. Case studies are presented for the RVC-MPEG video decoder and WLAN 802.11a baseband processing. The case studies show the benefits of automated scenario extraction for efficient design-time analysis of dynamic streaming applications.