Title :
Affine Data-Flow Graphs for the Synthesis of Hard Real-Time Applications
Author :
Bouakaz, Adnan ; Talpin, Jean-Pierre ; Vitek, Jan
Author_Institution :
IRISA, Univ. of Rennes 1, Rennes, France
Abstract :
Data-flow models ease the task of constructing feasible schedules of computations and communications of high-assurance embedded applications. One key and open issue is how to schedule data-flow graphs so as to minimize the buffering of data and reduce end-to-end latency. Most of the proposed techniques in that respect are based on either static or data-driven scheduling. This paper looks at the problem in a different way by considering priority-driven preemptive scheduling theory of periodic tasks to execute a data-flow program. Our approach to the problem can be detailed as follows. (1) We propose a model of computation in which the activation clocks of actors are related by affine functions. The affine relations describe the symbolic scheduling constraints of the data-flow graph. (2) Based on this framework, we present an algorithm that computes affine schedules in a way that minimizes buffering requirements and, in addition, guarantees the absence of overflow and underflow exceptions over communication channels. (3) Depending on the chosen scheduling policy (earliest-deadline first or rate-monotonic), we concretize the symbolic schedule by defining the period and the phase of each actor. This concretization guarantees schedulability and maximizes the processor utilization factor.
Keywords :
buffer storage; data flow computing; data flow graphs; exception handling; scheduling; actor activation clock; affine data-flow graph; affine function; affine relation; affine schedule; buffering requirement minimization; communication channel; data buffering minimization; data-driven scheduling; data-flow graph scheduling; data-flow model; data-flow program; earliest-deadline first scheduling; end-to-end latency reduction; hard real-time application synthesis; high-assurance embedded applications; overflow exception; periodic task; priority-driven preemptive scheduling theory; processor utilization factor maximization; rate-monotonic scheduling; scheduling policy; static scheduling; symbolic scheduling constraint; underflow exception; Analytical models; Clocks; Computational modeling; Concurrent computing; Processor scheduling; Schedules; Semantics; Affine relation; Buffer minimization; Data-flow graphs; Linear programming; Priority-driven scheduling;
Conference_Titel :
Application of Concurrency to System Design (ACSD), 2012 12th International Conference on
Conference_Location :
Hamburg
Print_ISBN :
978-1-4673-1687-3
DOI :
10.1109/ACSD.2012.16