Managing latency in embedded streaming applications under hard-real-time scheduling
Open Access
- 7 October 2012
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 83-92
Abstract
In this paper, we consider the problem of hard-real-time scheduling of embedded streaming applications, modeled using dataflow graphs, while minimizing the application latency. Recently, it has been shown that the actors in an acyclic Cyclo-Static Dataflow (CSDF) graph can be scheduled as a set of implicit-deadline periodic tasks. Such scheduling approach has been shown to yield the maximum achievable throughput for a large set of graphs, called matched I/O rates graphs. We show that scheduling the graph actors as implicit-deadline periodic tasks increases the latency significantly for a class of graphs called unbalanced graphs. To alleviate this problem, we propose a new task-set representation for the actors in which the actors are scheduled as a set of constrained-deadline periodic tasks. We prove that scheduling the actors as constrained-deadline periodic tasks delivers optimal throughput (i.e., rate) and latency for graphs with repetition vector equal to $\vec{1}$. Furthermore, we evaluate the constrained-deadline representation using a set of 19 real-life applications and show that it is capable of achieving the minimum achievable latency for more than 70% of the applications, and even if the application has a repetition vector not equal to $\vec{1}$. We show that choosing the task deadline involves a trade-off between the latency and the resources requirements. Finally, we propose a decision tree to assist the designer in choosing the appropriate real-time periodic task model for scheduling acyclic CSDF graphs.
Keywords
This publication has 13 references indexed in Scilit:
- A survey of hard real-time scheduling for multiprocessor systemsACM Computing Surveys, 2011
- Hard-real-time scheduling of data-dependent tasks in embedded streaming applications2011
- Trends in multicore DSP platformsIEEE Signal Processing Magazine, 2009
- Self-Timed Scheduling Analysis for Real-Time ApplicationsEURASIP Journal on Advances in Signal Processing, 2007
- Scheduling multiple independent hard-real-time jobs on a heterogeneous multiprocessor2007
- The partitioned multiprocessor scheduling of deadline-constrained sporadic task systemsIEEE Transactions on Computers, 2006
- Efficient Feasibility Analysis for Real-Time Systems with EDF Scheduling2005
- An improved schedulability test for uniprocessor periodic task systems2004
- Cycle-static dataflowIEEE Transactions on Signal Processing, 1996
- Synchronous data flowProceedings of the IEEE, 1987