EN FR
EN FR


Section: New Software and Platforms

ADFG: Affine data-flow graphs scheduler synthesis

Participants : Alexandre Honorat, Jean-Pierre Talpin, Thierry Gautier, Loïc Besnard.

We proposed [2], and implemented (The ADFG tool, Adnan Bouakaz, http://people.irisa.fr/Adnan.Bouakaz/software.htm), a new data-flow design model: ADFG, initially to synthesize schedulers for SCJ/L1 applications. The principle of ADFG is to perform a linear abstraction of complex cyclo-static scheduling problems followed by the exploration of a concrete solution extracted from the abstract solution space, hence the name: abstract affine data-flow scheduling. ADFG guarantees schedules that ordinary (e.g. RTJ, SCJ) task-sets do not cause overflows or underflows. ADFG objectives are to maximize the throughput (the processors utilization) while minimizing buffering storage space needed between actors. ADFG supports EDF and fixed-priority scheduling policies for uni-, multi-processors and distributed systems.

The data-flow design model of ADFG comes with a development tool integrated in the Eclipse IDE for easing the development of SCJ/L1 applications and enforcing the restrictions imposed by the design model. It consists of a GMF editor where applications are designed graphically and timing and buffering parameters can be synthesized. Abstract affine scheduling is first applied on the data-flow subgraph, that consists only of periodic actors, to compute timeless scheduling constraints (e.g. relation between the speeds of two actors) and buffering parameters. Then, symbolic fixed-priority schedulability analysis (i.e., synthesis of timing and scheduling parameters of actors) considers both periodic and aperiodic actors.

In the case of safety-critical Java, and through a model-to-text transformations using Acceleo, SCJ code for missions, interfaces of handlers, and the mission sequencer is automatically generated in addition to the annotations needed by the memory checker. Channels are implemented as cyclic arrays or cyclical asynchronous buffers; and a fixed amount of memory is hence reused to store the infinite streams of tokens.

Figure 1. The ADFG tool
IMG/ADFGtool.png