Skip to Main content Skip to Navigation
New interface
Conference papers

Affine Data-Flow Graphs for the Synthesis of Hard Real-Time Applications

Adnan Bouakaz 1 Jean-Pierre Talpin 1 Jan Vitek 2 
1 ESPRESSO - Synchronous programming for the trusted component-based engineering of embedded systems and mission-critical systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Thierry Gautier Connect in order to contact the contributor
Submitted on : Monday, December 10, 2012 - 4:27:09 PM
Last modification on : Saturday, November 19, 2022 - 3:42:59 AM
Long-term archiving on: : Monday, March 11, 2013 - 12:45:47 PM


Files produced by the author(s)



Adnan Bouakaz, Jean-Pierre Talpin, Jan Vitek. Affine Data-Flow Graphs for the Synthesis of Hard Real-Time Applications. Proceedings of the 2012 12th International Conference on Application of Concurrency to System Design, Jun 2012, Hamburg, Germany. pp.183-192, ⟨10.1109/ACSD.2012.16⟩. ⟨hal-00763387⟩



Record views


Files downloads