Paper Info
Title
Worst-Case Throughput Analysis For Parametric Rate And Parametric Actor Execution Time Scenario-Aware Dataflow Graphs
Abstract
Scenario-aware dataflow (SADF) is a prominent tool for modeling and analysis of dynamic embedded dataflow applications. In SADF the application is represented as a finite collection of synchronous dataflow (SDF) graphs, each of which represents one possible application behaviour or scenario. A finite state machine (FSM) specifies the possible orders of scenario occurrences. The SADF model renders the tightest possible performance guarantees, but is limited by its finiteness. This means that from a practical point of view, it can only handle dynamic dataflow applications that are characterized by a reasonably sized set of possible behaviours or scenarios. In this paper we remove this limitation for a class of SADF graphs by means of SADF model parametrization in terms of graph port rates and actor execution times. First, we formally define the semantics of the model relevant for throughput analysis based on (max,+) linear system theory and (max,+) automata. Second, by generalizing some of the existing results, we give the algorithms for worst-case throughput analysis of parametric rate and parametric actor execution time acyclic SADF graphswith a fully connected, possibly infinite state transition system. Third, we demonstrate our approach on a few realistic applications from digital signal processing (DSP) domain mapped onto an embedded multi-processor architecture.
Year
DOI
Venue
2014
10.4204/EPTCS.145.7
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE
Field
DocType
Issue
Programming language,Parametrization,Linear system,Computer science,Digital signal,Automaton,Finite-state machine,Theoretical computer science,Dataflow,Parametric statistics,Throughput
Journal
145
ISSN
Citations 
PageRank 
2075-2180
8
0.49
References 
Authors
12
4
Name
Order
Citations
PageRank
Mladen Skelin1163.37
Marc Geilen2134684.30
Francky Catthoor33932423.30
Sverre Hendseth4234.67