Response modeling runtime schedulers for timing analysis of self-timed dataflow graphs

Alok Lele, Orlando Moreira, P.J.L. Cuijpers, C.H.V. van Berkel

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
4 Downloads (Pure)


Constituent tasks of modern day Embedded Streaming Applications (ESAs), such as engine control systems, multimedia and software defined radios often exhibit execution behaviors that do not conform to conventional task models. ESAs consist of iterative, pipelined sequences of tasks that are conditioned by intra- and inter-iteration dependencies, and often have strict throughput and latency requirements. We model ESAs as dataflow graphs, where actors represent computational units, and directed edges represent communication channels between actors. Due to practical constraints like cost-effectiveness, power consumption and chip-area, multiple ESAs are run on a shared (multi-processor) platform. Thus rigorous timing analysis is required to verify whether individual ESAs meet their respective timing requirements.We look at response modeling, a compositional timing analysis approach wherein the local worst-case influence of runtime scheduling is represented within the constructs provided in dataflow. These local representations (called response models) can be composed together to construct a global understanding of an ESA's worst-case execution which is then used to verify whether its real-time requirements are met. This paper proposes a generic response modeling technique for runtime scheduling of ESAs. We focus on preemptive Fixed Priority Scheduling (FPS) but also demonstrate that we can apply our technique to a wide range of runtime schedulers. In our experiments, we present academic and industrial case-studies that highlight the effectiveness of our approach in the timing analysis of ESAs with unconventional execution behavior.

Original languageEnglish
Pages (from-to)15-29
JournalJournal of Systems Architecture
Publication statusPublished - 1 Apr 2016


  • Dataflow graph
  • Runtime scheduling
  • Timing analysis


Dive into the research topics of 'Response modeling runtime schedulers for timing analysis of self-timed dataflow graphs'. Together they form a unique fingerprint.

Cite this