Alexandre Honorat
email: alexandre.honorat@inria.fr

Thierry Gautier
email: thierry.gautier@inria.fr

Loïc Besnard
email: loic.besnard@irisa.fr

Shuvra S Bhattacharyya

Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice

Keywords: CCS Concepts:, Computer systems organization → Real-time system specification real-time systems, periodic scheduling, fixed priority, dataflow

The major drawback of using static schedules to execute dataflow applications is their high inflexibility. In realtime systems, periodic schedules make it easier to assert safety guarantees and to decrease the schedule size, but their characteristics remain hard to compute. This article presents an approach to automatically generate fixed priority schedules from a dataflow specification. To do so, precedence dependencies between actors in the dataflow graphs are abstracted, as well as the task periods, by using affine relations. This abstraction allows us to synthesize schedules efficiently considering two main objectives: the maximization of throughput and the minimization of buffer sizes. Given a dataflow graph to execute in a real-time environment, we transform it into an Affine DataFlow Graph (ADFG) and compute the task priorities, their mapping, the number of delays in the buffers, and the buffer sizes. This article is the first to present an overview of both theoretical and practical aspects of ADFG. On the theoretical side, it presents corrections and improvements on the fixed priority case. On the practical side, benchmark evaluations demonstrate the robustness and maturity of the approach that our scheduling synthesizer implements. Synthesized schedules are evaluated by using scheduling simulation and real-time implementation. Last but not least, the synthesized periods reach the optimal throughput if enough processors are available, and most of the time the periods reach the maximal processor utilization factor in the uni-processor case. Moreover, execution time of the synthesis is about only one second for the main proposed algorithms.

INTRODUCTION

The dataflow programming paradigm is widely used in embedded system design to describe Digital Signal Processing (DSP) control [START_REF] Lee | Dataflow process networks[END_REF] and stream processing [START_REF] Thies | StreamIt: A Language for Streaming Applications[END_REF] applications. Synchronous DataFlow (SDF) graphs [START_REF] Lee | Synchronous data flow[END_REF], for instance, provide automated code generation services to limit the most problematic and error-prone tasks of programming parallel applications. However, DSP applications are usually subject to additional constraints, such as throughput requirements or limited available memory, which also need to be tackled.

Constraints on throughput or memory must be respected by the application schedule. While many schedule types exist, some are easier to analyze in order to assert that all constraints are respected. Assertions are easily checked on static schedules but on the other side static schedules eventually require a high memory to store all execution times. Periodic schedules are a trade-off often used in real-time systems: efficient algorithms exist to assert their schedulability [START_REF] Audsley | Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling[END_REF][START_REF] Joseph | Finding Response Times in a Real-Time System[END_REF] and they have a limited memory cost. Periodic scheduling is then divided in two complementary problems: first to compute the periods of tasks, and second to check that all constraints are respected. In periodic real-time systems, constraints also include the fact that every task meets its periodic deadline. Although periodic schedules are still hard to synthesize in the general case, dataflow graphs provide a programming abstraction well adapted to study throughput and memory constraints under periodic real-time scheduling.

In this article, we describe and evaluate a method to solve the two aforementioned problems at once: period synthesis and constraints assessment. Our method uses several abstractions and Integer Linear Programming (ILP) formulations, and thus it is still limited by the NP-hard complexity of ILP, just as in the general case of task scheduling [START_REF] Kwok | Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[END_REF]. However, and despite this computational complexity limit, we demonstrate that our method runs in about one second for a scheduling problem with hundred tasks. In contrast to many scheduling approaches, the Affine DataFlow Graph (ADFG) tool [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF] synthesizes near-optimal and always valid periods of the real-time tasks to execute, without any simulation of the complete schedule. We say that the ADFG tool synthesizes a schedule, which actually means that it computes all needed characteristics of the tasks to schedule: period, priority, mapping. . . The periods are near-optimal in the sense that they are computed with the objective to maximize the throughput of the scheduled application; they are valid since the schedulability of the system is guaranteed by formal methods adapted from synchronous languages [START_REF] Smarandache | Validation of Mixed Signal-Alpha Real-Time Systems through Affine Calculus on Clock Synchronisation Constraints[END_REF]. Regarding optimality, the ADFG tool does not guarantee throughput optimality especially if also considering the objective to minimize the total buffer size; nevertheless the experiments show that the optimal periods are often reached. Regarding validity, the ADFG tool guarantees schedulability in the considered periodic execution model, but other timing metrics such as preemption costs are not taken into account in the ADFG synthesizer itself.

Yet, the scheduling can be highly impacted by extra factors such as preemption cost. So we also present how the ADFG tool can be used in conjunction with other software to simulate and to execute an application, for example in order to derive the amount of preemption needed. Moreover, we highlight specific details that a designer has to be aware of to make effective use of the scheduler. Simulations reveal in a few cases both pessimistic or optimistic behaviors, that a designer has to deal with when using the ADFG tool. Pessimistic schedules may occur due to the Worst Case Execution Times (WCETs) of actors in Cyclo-Static DataFlow (CSDF) graphs [START_REF] Bilsen | Cycle-static Dataflow[END_REF], while optimistic schedules may occur due to underestimated preemption costs. In any case, the synthesized schedules are inherently valid in the model of ADFG theory.

Concretely, given a Ultimately Cyclo-Static DataFlow (UCSDF) graph to execute in a periodic real-time environment with known WCETs, the following schedule characteristics are computed by the ADFG tool: the task priorities and periods, the mapping, the number of delays in the buffers, ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice 1:3 and the buffer sizes. The application to schedule is modeled thanks to an UCSDF graph. The UCSDF model is an extension of the CSDF model, being itself an extension of SDF. The tasks are periodic with implicit deadline; they are scheduled by a Fixed Priority (FP) preemptive partitioned scheduler. Synthesis algorithms are available for the uni-processor and the multi-processor cases; in the multi-processor case, the number of homogeneous processors is given as an input by the designer. Most of the provided algorithms try to maximize the throughput of the scheduled application, although two of them allows to find trade-offs between throughput and total buffer size. Numerous aspects of the ADFG theory have already been published over the past 12 years: while it started with affine equations for synchronous languages [START_REF] Smarandache | Validation of Mixed Signal-Alpha Real-Time Systems through Affine Calculus on Clock Synchronisation Constraints[END_REF], the main theory has been formalized in the Bouakaz' PhD thesis [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF] for both FP scheduling [START_REF] Bouakaz | An abstraction-refinement framework for priority-driven scheduling of static dataflow graphs[END_REF][START_REF] Bouakaz | Design of Safety-Critical Java Level 1 Applications Using Affine Abstract Clocks[END_REF][START_REF] Bouakaz | Affine Data-Flow Graphs for the Synthesis of Hard Real-Time Applications[END_REF] and Earliest Deadline First (EDF) scheduling [START_REF] Bouakaz | Earliest-deadline first scheduling of multiple independent dataflow graphs[END_REF][START_REF] Bouakaz | Buffer Minimization in Earliest-deadline First Scheduling of Dataflow Graphs[END_REF][START_REF] Honorat | ADFG: a scheduling synthesis tool for dataflow graphs in real-time systems[END_REF]. As a tool, ADFG has been used to validate a subset of Architecture Analysis and Design Language (AADL) [START_REF] Besnard | Timed behavioural modelling and affine scheduling of embedded software architectures in the AADL using Polychrony[END_REF][START_REF] Gautier | Polychronous automata and their use for formal validation of AADL models[END_REF] and to generate code compatible with the Real-Time Executive for Multiprocessor Systems (RTEMS) real-time operating system [START_REF] Nam Tran | A Framework for Fixed Priority Periodic Scheduling Synthesis from Synchronous Data-flow Graphs[END_REF]. This article is the first to provide a general overview of both theoretical and practical aspects (up to the execution of the synthesized code) and it describes and evaluates so far unpublished details of the synthesis algorithms. In a decade a few bugs have been fixed, and updated evaluations still show the efficiency of our approach.

The article is organized as follows. Next Section 2 introduces related work. Section 3 recalls the main concepts of SDF graphs and FP scheduling. Then the Section 4 provides an overview of the ADFG theory and the UCSDF graph model; and previously unpublished contributions are also detailed. Regarding practice, the generation of the scheduling code of an application thanks to the results provided by the ADFG tool is explained in Section 5. The evaluation of the schedules, by metrics obtained directly or from simulations, is presented in Section 6 and precedes closing remarks.

RELATED WORK

The ADFG tool computes the periods of actors in a UCSDF graph, ensuring that all implicit deadlines will be met, and that there is no buffer underflow or overflow when executing the graph. Thus the ADFG tool can be seen as both an analysis and a synthesis tool. Both categories of tools, dedicated to SDF or CSDF graphs, are reviewed in this section.

Many other models than SDF exist to check real-time properties but, to our knowledge, those models make the analysis and especially the synthesis of buffer sizes more tedious. For example, a real-time system implementation using Timed Automata may need one clock per buffer slot [START_REF] Sun | Verification of two real-time systems using parametric timed automata[END_REF], manually set for each possible buffer size. Conversely, the ADFG theory is not adapted to dynamic real-time systems where, for example, some tasks could be enabled/disabled by other tasks results.

Generic analysis of SDF graphs

SDF graphs and their extensions, as CSDF [START_REF] Bilsen | Cycle-static Dataflow[END_REF], have been widely analyzed on several aspects including: latency [START_REF] Ghamarian | Latency Minimization for Synchronous Data Flow Graphs[END_REF][START_REF] Khatib | Computing latency of a real-time system modeled by Synchronous Dataflow Graph[END_REF][START_REF] Moreira | Self-Timed Scheduling Analysis for Real-Time Applications[END_REF], throughput [START_REF] De Groote | Max-Plus Algebraic Throughput Analysis of Synchronous Dataflow Graphs[END_REF][START_REF] Ghamarian | Throughput Analysis of Synchronous Data Flow Graphs[END_REF], buffer size [START_REF] Govindarajan | Minimizing Buffer Requirements under Rate-Optimal Schedule in Regular Dataflow Networks[END_REF][START_REF] Wiggers | Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs[END_REF], or liveness [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF]. These analyses often relax the available processors constraint (their number is considered as potentially infinite) and use most often either static periodic scheduling (for [START_REF] Bodin | Periodic schedules for Cyclo-Static Dataflow[END_REF][START_REF] Govindarajan | Minimizing Buffer Requirements under Rate-Optimal Schedule in Regular Dataflow Networks[END_REF][START_REF] Verhaegh | A two-stage solution approach to multidimensional periodic scheduling[END_REF]) or self-timed scheduling 1(for [START_REF] Ghamarian | Throughput Analysis of Synchronous Data Flow Graphs[END_REF][START_REF] Moreira | Self-Timed Scheduling Analysis for Real-Time Applications[END_REF][START_REF] Wiggers | Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs[END_REF]). Several combinations of the aforementioned aspects have been studied, such as the minimization of the total buffer size under a throughput constraint [START_REF] Benazouz | A new method for minimizing buffer sizes for Cyclo-Static Dataflow graphs[END_REF][START_REF] Bodin | Periodic schedules for Cyclo-Static Dataflow[END_REF]. For instance the SDF3 tool [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF] provides trade-offs analysis between buffer size and throughput for SDF graphs [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF] and CSDF graphs [START_REF] Stuijk | Throughput-Buffering Trade-Off Exploration for Cyclo-Static and Synchronous Dataflow Graphs[END_REF]. The authors of SDF3 also proved that both metrics, throughput and buffer size, cannot be optimized at the same time. However most of these analytic methods are purely symbolic and do not compute a real-time schedule, including mapping and periods, or the number of delays of the graph.

Besides, many tools are able to analyze SDF graphs, to derive a few schedule characteristics (e.g. mapping and buffer size), and finally to generate the glue code of the schedule automatically: DIF-GPU [START_REF] Lin | Memory-constrained Vectorization and Scheduling of Dataflow Graphs for Hybrid CPU-GPU Platforms[END_REF], PREESM [START_REF] Pelcat | Preesm: A dataflow-based rapid prototyping framework for simplifying multicore DSP programming[END_REF], LabVIEW [START_REF] Andrade | From Streaming Models to FPGA Implementations[END_REF], MAPS [START_REF] Castrillon | MAPS: Mapping Concurrent Dataflow Applications to Heterogeneous MPSoCs[END_REF], Diplomat [START_REF] Bodin | Diplomat: Mapping of Multi-kernel Applications Using a Static Dataflow Abstraction[END_REF], Gaspard [START_REF] Gamatié | A Model-Driven Design Framework for Massively Parallel Embedded Systems[END_REF], Ocarina [START_REF] Hugues | From the prototype to the final embedded system using the Ocarina AADL tool suite[END_REF], PeaCE [START_REF] Ha | PeaCE: A Hardware-software Codesign Environment for Multimedia Embedded Systems[END_REF], and Ptolemy [START_REF] Eker | Taming heterogeneity -the Ptolemy approach[END_REF] 2 which includes the Metronomy tool [START_REF] Guo | Metronomy: A functionarchitecture co-simulation framework for timing verification of cyber-physical systems[END_REF] for timing verification. But these tools either do not consider real-time executions (e.g. PREESM and LabVIEW), or do not perform all the syntheses automatically (e.g. delay or periods are an input of the user). For example, periods usually are an input of the problem [START_REF] Joost | Temporal Analysis Flow Based on an Enabling Rate Characterization for Multi-Rate Applications Executed on Mpsocs with Non-Starvation-Free Schedulers[END_REF][START_REF] Cédric | Preemptive scheduling of dependent periodic tasks modeled by synchronous dataflow graphs[END_REF], instead of the output. Moreover, most tools computing a schedule consider only one optimization objective, usually throughput maximization. Periodic scheduling for throughput maximization [START_REF] Parhi | Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding[END_REF] has been studied pretty early by Parhi and Messerschmitt, and it is possible to derive the period achieving best throughput [START_REF] Benabid-Najjar | Periodic Schedules for Bounded Timed Weighted Event Graphs[END_REF], but not taking into account FP scheduling, nor preemption, nor the number of processors available.

Real-Time Schedule Synthesis of SDF graphs

To our knowledge, only the DARTS [START_REF] Bamakhrama | Hard-real-time scheduling of data-dependent tasks in embedded streaming applications[END_REF] and ADFG [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF][START_REF] Honorat | ADFG: a scheduling synthesis tool for dataflow graphs in real-time systems[END_REF] tools consider buffer size minimization and throughput maximization at once, while being able to derive the periods of CSDF graph. Whereas the DARTS tool considers unlimited available processors, the ADFG tool takes the number of processors as an input. Other methods synthesize real-time characteristics such as periods [START_REF] Kwak | Symbolic schedulability analysis of real-time systems[END_REF], but not for SDF graphs.

The DARTS [START_REF] Bamakhrama | Hard-real-time scheduling of data-dependent tasks in embedded streaming applications[END_REF] 3 tool allows to compute the strictly periodic schedule characteristics achieving the best throughput under EDF or Rate Monotonic (RM) policies, with a maximum total buffer size as a constraint. The DARTS tool considers only acyclic CSDF graphs and a non-constrained number of available processors on the target system. The DARTS and ADFG tools differ in the input constraints: ADFG accepts cyclic and acyclic UCSDF graphs, constrained and non-constrained buffer sizes, and it requires the number of available processors in the target system. Indeed, throughput maximization and buffer size minimization are two antagonistic objectives [START_REF] Stuijk | Throughput-Buffering Trade-Off Exploration for Cyclo-Static and Synchronous Dataflow Graphs[END_REF] and rather than solving a difficult multi-objective optimization, both the ADFG and DARTS tools constrain one of the objectives and then optimize the other. Constrained objective of the DARTS tool is the total buffer size fixed by the user; buffers are used as much as possible in order to maximize the throughput first, and then the DARTS tool minimizes the number of processors. Constrained objective of the ADFG tool is the number of available processors fixed by the user; processors are used as much as possible in order to maximize the throughput first, and then the ADFG tool minimizes the total buffer size. Furthermore, the ADFG tool provides extra trade-offs between buffer size and throughput objectives thanks to its internal algorithms SP_UNI_UDH and SP_MULT_MBS.

Like ADFG, several tools use ILP formulations to synthesize the buffer sizes. Previous ILP formulations for CSDF graphs have been made in order to maximize the throughput and minimize the total buffer size: under self-timed scheduling [START_REF] Wiggers | Efficient Computation of Buffer Capacities for Cyclo-Static Dataflow Graphs[END_REF], under static periodic scheduling with maximum number of processors constraint [START_REF] Verhaegh | A two-stage solution approach to multidimensional periodic scheduling[END_REF], or under static periodic scheduling with minimum throughput constraint [START_REF] Benazouz | A new method for minimizing buffer sizes for Cyclo-Static Dataflow graphs[END_REF], but not under EDF and FP scheduling. Also, a synthesis tool has been developed [START_REF] Dkhil | Self-timed Periodic Scheduling for a Cyclo-static DataFlow Model[END_REF] for a mix of the periodic and self-timed scheduling policies, with priorities. Finally, buffer size minimization can be improved when data access pattern of the SDF actors are known [START_REF] Wang | Communication Storage Optimization for Static Dataflow with Access Patterns Under Periodic Scheduling and Throughput Constraint[END_REF].

Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice 1:5

BACKGROUND

Common knowledge and notations of this article, about the SDF graph model and about FP scheduling, are reviewed in the following Section 3.1 and Section 3.2, respectively.

Synchronous DataFlow

A Synchronous DataFlow (SDF) graph [START_REF] Lee | Synchronous data flow[END_REF] is a directed multi-graph 𝐺 = (𝑉 , 𝐸) consisting of a finite set of actors 𝑉 = {𝑣 1 , ..., 𝑣 𝑁 } and a finite set of one-to-one buffers 𝐸. A buffer 𝑒 1→2 = (𝑣 1 , 𝑣 2 , 𝑝, 𝑞) ∈ 𝐸 connects the data producer 𝑣 1 to the data consumer 𝑣 2 such that the production (resp. consumption) rate is given by an integer 𝑝 ∈ N * (resp. 𝑞 ∈ N * ). The data unit is called a token. Every time an actor is fired (i.e. is executed), it consumes as many tokens as specified by each input buffer connected to it, and produces as many tokens as specified by each output buffer connected to it. SDF graphs actually are a subset of weighted Petri nets, with only one incoming and one outgoing transition (i.e. actor) per place (i.e. buffer). Figure 1 depicts a simple SDF graph with 3 actors. Figure 2 depicts the h263decoder which is taken from a set of real applications provided by the SDF3 benchmark [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF]. When implementing an SDF graph, it is common to impose statically-determined buffer sizesthat is denoted 𝛿 (𝑒 𝑎→𝑏 ) for a buffer 𝑒 𝑎→𝑏 . If some buffer sizes are too small, the SDF graph could deadlock. For example, with the graph in Figure 1, the buffer 𝑒 1→2 connecting 𝑣 1 to 𝑣 2 needs a minimum size of 4. The reason is that 𝑣 1 must be fired at least 2 times before 𝑣 2 has enough input tokens to be fired. There can be a number of initial tokens present on each buffer. These initial tokens are called the delays of a buffer since they can induce an offset in the execution of the consumer in relation to the producer [START_REF] Bhattacharyya | Software Synthesis from Dataflow Graphs[END_REF]. When scheduling an SDF graph, the buffer sizes are always bounded since the production and consumption rates are fixed, however consistency checks are needed when multiple buffers exist between two actors, and also for the undirected cycles in the graph (not detailed here). If the graph is consistent, it is possible to compute a repetition vector, defined in the following Definition 3.1. In this article, we study only consistent and weakly connected4 graphs. Definition 3.1 (Repetition Vector [START_REF] Bhattacharyya | Software Synthesis from Dataflow Graphs[END_REF]). The repetition vector of an SDF graph is an array of length equal to the number of actors in the graph, such that each element of the array is a positive integer, the greatest common divisor of all of the elements is 1, and if each actor is invoked for the number of times equal to its entry, then the number of tokens on each edge of the graph remains unchanged. When each actor has been fired as many times as required by the repetition vector, this defines a graph iteration, meaning that the whole application has been executed once. For the graph in Figure 1, the repetition vector is ì 𝑧 = [3, 2, 2]; actors 𝑣 2 and 𝑣 3 are fired the same number of times since the buffer 𝑒 2→3 connecting them has a consumption rate equal to its production rate. The repetition vector can be computed efficiently by applying a depth-first search algorithm [START_REF] Bhattacharyya | Software Synthesis from Dataflow Graphs[END_REF].

Fixed Priority Scheduling of Periodic Tasks

In this article, only partitioned preemptive fixed priority scheduling of asynchronous periodic tasks is considered 5 . Each SDF actor corresponds to a hard real-time periodic task with implicit deadline. The priority 𝑃 𝑣 of each actor 𝑣 is unique and fixed over time; 𝑃 𝑣 ∈ N * and the value 1 corresponds to the highest priority level. Auto-concurrency is not allowed: two firings of an actor cannot occur in parallel. Moreover, an actor 𝑣 is permanently mapped to a single processor 𝑀 𝑣 on homogeneous multi-processor architectures. Extension of the developments of this article to more relaxed versions of the scheduling problem (e.g., considering heterogenous architectures) is a useful direction for future work.

The period of an actor 𝑣 is denoted 𝑇 𝑣 ∈ N * , as in the model of Liu and Layland [START_REF] Laung | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. This period must be greater or equal to the WCET of 𝑣, denoted 𝐶 𝑣 ∈ N * . Each actor 𝑣 is released every 𝑇 𝑣 time units and it must be executed completely before the next release; otherwise the implicit hard deadline is missed and the schedule is not valid. Each actor 𝑣 may be initially released with an offset 𝑂 𝑣 ∈ N; the offset is non negative and possibly greater than the period 𝑇 𝑣 . When an actor 𝑣 is currently running, it is preempted by any released actor having a higher priority and mapped on the same processor; 𝑣 resumes only when the actors of higher priority all finished their execution. The preemption overhead is not modeled in our work.

Finally, the processor utilization factor 𝑈 is defined as follows in Equation (1); it must be lower than the number of processors 𝑚 in the targeted homogeneous multi-processor [START_REF] Horn | Some simple scheduling algorithms[END_REF].

𝑈 = ∑ 𝑣 ∈𝑉 𝐶 𝑣 𝑇 𝑣 ≤ 𝑚 (1)

FIXED PRIORITY SCHEDULING FROM AFFINE DATAFLOW GRAPHS

Before seeing the details of the theory, we recall the notations and depict the periodic scheduling thanks to the following example. Considering the Synchronous DataFlow (SDF) graph in Figure 1, and given the Worst Case Execution Times (WCETs) 𝐶 𝑣 1 = 10, 𝐶 𝑣 2 = 6 and 𝐶 𝑣 3 = 7, the Affine DataFlow Graph (ADFG) tool computes the smallest possible actor periods to ensure safety of the execution. For example, if the targeted system has 2 processors, the ADFG tool finds the periods

𝑇 𝑣 1 = 10, 𝑇 𝑣 2 = 15, 𝑇 𝑣 3 = 15 and offsets 𝑂 𝑣 1 = 0, 𝑂 𝑣 2 = 20, 𝑂 𝑣 3 = 20.
Actor 𝑣 1 is mapped alone on the first processor, for a total processor utilization factor of 𝑈 = 1.87 (over 𝑚 = 2). Part of the resulting schedule is depicted in Figure 3: the two dashed red lines delimit the indefinitely repeated schedule, omitting the first two firings of 𝑣 1 . Actors 𝑣 2 and 𝑣 3 are released at the same time but the ADFG tool assigns a higher priority to 𝑣 2 and thus 𝑣 2 is executed first.

The ADFG tool provides several algorithms to compute the schedule characteristics. Table 1 summarizes the available algorithms for uni-processor systems; the algorithms differ by the priority assignment computation. Table 2 summarizes the available algorithms for multi-processor systems; the algorithms differ by the mapping computation but all use the same priority assignment as SP_UNI in Table 1. In order to understand how these algorithms work, an overview of the ADFG tool is presented in Section 4.1; so far unpublished contributions, as priority assignment with

ADFG theory overview

To synthesize preemptive periodic schedules under Fixed Priority (FP) policy, the ADFG tool takes as input a weakly connected Ultimately Cyclo-Static DataFlow (UCSDF) graph with WCET of each actor, the number of available identical processors in the target system, and the solving method. The output of the ADFG tool includes the mapping (without auto-concurrency), the period and the priority of each actor, the number of delays and each buffer size, and finally, several metrics as the throughput or the processor utilization factor. This Section 4.1 recalls the workflow of the ADFG tool to compute the aforementioned schedule characteristics, with the main equations already presented in prior work and summed up in [START_REF] Honorat | ADFG: a scheduling synthesis tool for dataflow graphs in real-time systems[END_REF]. Hence, no proof is provided here.

4.1.1 Schedule abstraction. Affine DataFlow Graph (ADFG), the name of the tool, stands for the internal representation of the UCSDF, Cyclo-Static DataFlow (CSDF), and SDF graphs. In UCSDF graphs, the actors send data through buffers as in SDF and CSDF graphs, and Definition 3.1 for the repetition vector is the same. The difference between these three models lies in the production and consumption rates: static in SDF (one integer), cyclo-static in CSDF (a cyclic sequence of integers), and ultimately cyclo-static in UCSDF (two sequences of integers, the first being used only once).

During its 𝑖-th firing, an actor receives and sends an amount of data equal to the 𝑖-th value of its consumption/production rates; the cyclic sequence is iterated in a round-robin fashion. CSDF and UCSDF graphs can always be converted into SDF graphs [START_REF] Parks | A comparison of synchronous and cycle-static dataflow[END_REF] but at the cost of introducing many new nodes. In the graph depicted in Figure 4a, the production rate is of UCSDF form while the consumption rate can be seen as either CSDF or UCSDF form, the latter with an empty first part. Previous work on synchronous languages [START_REF] Smarandache | Validation of Mixed Signal-Alpha Real-Time Systems through Affine Calculus on Clock Synchronisation Constraints[END_REF] made it possible to retrieve an affine function to bound the buffer sizes [START_REF] Bouakaz | Affine Data-Flow Graphs for the Synthesis of Hard Real-Time Applications[END_REF], thanks to an abstraction of the production and consumption rates. In this abstraction, exact time is not considered: the schedule abstracts events on buffers over time rather than time itself.

In the ADFG tool, each buffer is abstracted by an affine relation on the two firing clocks of the producer and the consumer actors. The firing clock is detailed in the next paragraph. In a buffer 𝑒 1→2 = (𝑣 1 , 𝑣 2 , 𝑝, 𝑞), the production and consumption rates 𝑝 and 𝑞 are the concatenation of two sequences of integers: 𝑝 = 𝑝 0 .𝑝 𝑐 and 𝑞 = 𝑞 0 .𝑞 𝑐 . The first initial sequence with 0 subscript may be empty, then symbolized by 𝜖. The second non empty sequence, cyclic and so identified by 𝑐 subscript in the equations, will be repeated indefinitely during the execution of the producer/consumer actor. The cyclic sequence is written inside parenthesis in Figure 4a and Figure 8. The two sequences of integers associated with a computed average production or consumption rate will help to define the affine relation. The average production (respectively consumption) rate 𝑎 𝑝 ∈ Q + (respectively 𝑎 𝑞 ) per firing is defined as follows in Equation ( 2). In an SDF graph, average rate is the only integer of the sequence; in CSDF and UCSDF graphs, the sum of the cyclic sequence is averaged by its length. Let us first denote |𝑠 | the length of a sequence 𝑠, and 𝑠 (𝑖) the 𝑖-th value of this sequence; if

𝑖 > |𝑠 |, 𝑖 is reassigned to ((𝑖 -|𝑠 0 |) modulo |𝑠 𝑐 |) + |𝑠 0 |.
The cyclic sequence sum is defined thanks to the ⊕ operator, that is the cumulative sum over a given length, as defined in the right part of Equation [START_REF] Audsley | Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling[END_REF].

𝑎 𝑝 = ||𝑝 𝑐 || |𝑝 𝑐 | , with ||𝑝 𝑐 || = ⊕𝑝 𝑐 (|𝑝 𝑐 |) = ∑ 1≤𝑖 ≤ |𝑝 𝑐 | 𝑝 𝑐 (𝑖) (2)
While Equation (2) constitutes the linear part of the data production, the affine part comes from the following lower bound 𝜆 𝑙 ∈ Z and upper bound 𝜆 𝑢 ∈ Z defined in Equation [START_REF] Bamakhrama | Hard-real-time scheduling of data-dependent tasks in embedded streaming applications[END_REF]. In an SDF graph, those two bounds 𝜆 𝑙 𝑝 and 𝜆 𝑢 𝑝 are equal to 0 because 𝑝 0 = 𝜖.

𝜆 𝑙 𝑝 = min 1≤𝑖 ≤ |𝑝 0 |+|𝑝 𝑐 | ⊕𝑝 (𝑖) -𝑎 𝑝 𝑖 and 𝜆 𝑢 𝑝 = max 1≤𝑖 ≤ |𝑝 0 |+|𝑝 𝑐 | ⊕𝑝 (𝑖) -𝑎 𝑝 𝑖 (3)
Then, the amount of data produced at the 𝑖-th firing (𝑖 without modulo reassignment) of an actor 𝑣 1 is bounded thanks to the inequalities in Equation ( 4).

𝜆 𝑙 𝑝 + 𝑎 𝑝 𝑖 ≤ ⊕𝑥 (𝑖) ≤ 𝜆 𝑢 𝑝 + 𝑎 𝑝 𝑖 (4)
Firings themselves are abstracted over time by firing clocks which are related for a producer actor and its consumer: an actor firing will occur every 𝑛 ticks for the producer 𝑣 1 , and every 𝑑 ticks for the consumer 𝑣 2 . Integers 𝑛 and 𝑑 are related such that 𝑛 𝑑 is the irreducible fraction of 𝑎 𝑝 𝑎 𝑞 . Besides, the integer 𝜑 ∈ Z denotes the firing offset between the actors 𝑣 1 and 𝑣 2 , i.e. there are 𝜑 1→2 ticks between the first firing of 𝑣 1 and the first firing of 𝑣 2 .

Finally, an affine relation is defined by a triple of integers (𝑛, 𝜑, 𝑑). Contrary to 𝑛 and 𝑑, 𝜑 may be negative. An example of all the aforementioned metrics is given in Figure 4 with two actors connected by a single buffer. Figure 4a details the average rate and the bounds of both actor rates; Figure 4b depicts their firing clocks.

Then the two affine Equations ( 5) and ( 6) enable to compute the buffer sizes 𝛿 𝑒 , the delays 𝜃 𝑒 , and all firing offsets 𝜑 thanks to an ILP solver where the objective is to minimize the sum of all buffer sizes and firing offsets. However, as this ILP formulation only concerns the firing clocks ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice 1:9

𝑣 1 𝑣 2 𝜑 = 0 Buffer 2 (4 8) (12 8 10
) linked by affine relations, there is no concrete time and the minimization objective on buffer sizes and firing offsets has no impact on the final throughput. Moreover, Equations ( 5) and ( 6) of the ILP formulation ensure the maximal throughput according to a previously computed priority assignment and actor mapping. The ILP formulation also contains specific equations for cycles not specified here, interested readers can refer to [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF] (section 2.3.2 in ref.

𝑛 = 3 𝑑 = 5 𝑝 0 = 2, 𝑝 𝑐 = 4 8 𝑞 0 = 𝜖, 𝑞 𝑐 = 12 8 10 𝑎 𝑝 = 6, 𝜆 𝑙 𝑝 = -6, 𝜆 𝑢 𝑝 = -4 𝑎 𝑞 = 10, 𝜆 𝑙 𝑞 = 0, 𝜆 𝑢 𝑞 = 2
).

𝜃 𝑒 1→2 + 𝑎 𝑝 𝜑 1→2 𝑛 ≥ 𝜆 𝑢 𝑞 -𝜆 𝑙 𝑝 + 𝑎 𝑝 𝐶 under ( 5
)
𝜃 𝑒 1→2 + 𝑎 𝑞 𝜑 1→2 𝑑 ≤ 𝛿 𝑒 1→2 + 𝜆 𝑙 𝑞 -𝜆 𝑢 𝑝 -𝑎 𝑞 𝐶 over (6)
As Equations ( 5) and ( 6) contain integer and rational numbers, every term is multiplied by the least common multiplier of all denominators when generating the ILP formulation; this avoids the floating point imprecision. 𝐶 under and 𝐶 over are two coefficients depending on the scheduling policy and other characteristics as the producer and consumer priorities or the fact that 𝑣 1 and 𝑣 2 are mapped on the same processor or not [START_REF] Bouakaz | An abstraction-refinement framework for priority-driven scheduling of static dataflow graphs[END_REF] (end of section IV in ref.

); their values are given later in Equation [START_REF] Bouakaz | An abstraction-refinement framework for priority-driven scheduling of static dataflow graphs[END_REF]. Actor mapping is not described in this article, however, priority assignment will be discussed further, in Section 4.2.1.

The solution computed by the ILP solver closes the abstraction part of the ADFG theory, which is then followed by the synthesis part in order to retrieve the periods of each actor.

Schedule synthesis.

The goal of the schedule synthesis part is to compute the effective periods and offsets of the actors. Offset and periods are computed in the same time unit as the WCETs inputs. First, note that the input graph is weakly connected, so defining a period on one actor induces a period for all other actors; thus only one basis period is considered during the synthesis. Indeed, a producer actor must produce in average the same amount of data per time unit as the consumers connected to it consume. This assumption is materialized into Equation [START_REF] Besnard | Timed behavioural modelling and affine scheduling of embedded software architectures in the AADL using Polychrony[END_REF] thanks to the affine relations between any pair of actors connected by a buffer 𝑒 1→2 .

𝑑 • 𝑇 𝑣 1 = 𝑛 • 𝑇 𝑣 2 (7)
Regular offsets of the actors are materialized in Equation ( 8), depending on the firing offsets 𝜑.

𝑂 𝑣 2 -𝑂 𝑣 1 = 𝜑 1→2 𝑛 𝑇 𝑣 1 (8)
Equation ( 7) induces a linear relation between any actor 𝑣 and an arbitrary actor basis of the weakly connected graph, see Equation [START_REF] Bilsen | Cycle-static Dataflow[END_REF] with 𝛼 basis = 1.

𝑇 𝑣 = 𝛼 𝑣 𝑇 basis , 𝛼 ∈ Q + (9)
This linear relation allows performing standard Response Time Analysis (RTA) [START_REF] Audsley | Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling[END_REF][START_REF] Joseph | Finding Response Times in a Real-Time System[END_REF] on the actors, by setting only one period 𝑇 basis . Also, the processor utilization factor 𝑈 can be rewritten with this single period 𝑇 basis , as formalized in Equation [START_REF] Bini | A Response-Time Bound in Fixed-Priority Scheduling with Arbitrary Deadlines[END_REF].

𝑈 = ∑ 𝐶 𝑣 𝛼 𝑣 𝑇 basis = 𝜎 𝑇 basis , with 𝜎 = ∑ 𝐶 𝑣 𝛼 𝑣 (10)
Equation ( 1) can be rewritten as Equation ( 11) and gives a minimal value of 𝑇 basis .

𝑇 basis ≥ 𝜎 𝑚 (11)
Then, thanks to similar rewriting done on the lower and upper bounds of the response time [START_REF] Bini | A Response-Time Bound in Fixed-Priority Scheduling with Arbitrary Deadlines[END_REF][START_REF] Sjödin | Improved response-time analysis calculations[END_REF], a bisection search is performed on 𝑇 basis with the RTA. The minimal period ensuring schedulability according to RTA is denoted 𝑇 𝑙 basis . This point is discussed further in Section 4.2.2. As basis period and processor utilization are inversely related in Equation [START_REF] Bini | A Response-Time Bound in Fixed-Priority Scheduling with Arbitrary Deadlines[END_REF], throughput maximization corresponds to processor utilization factor maximization; so the minimal period found by the bisection search ensures the maximum throughput reachable with the given number of available processors 𝑚 and according to the previously computed priority assignment and actor mapping.

Finally, it is possible to compute all periods and offsets thanks to a second ILP formulation with the goal of minimizing 𝑇 basis . The ILP solver takes as inputs Equations ( 8), ( 9) and [START_REF] Bodin | Periodic schedules for Cyclo-Static Dataflow[END_REF]. max( 𝜎 𝑚 ,𝑇 𝑙 basis ) ≤ 𝑇 basis [START_REF] Bodin | Periodic schedules for Cyclo-Static Dataflow[END_REF] 4.1.3 Workflow of the ADFG tool. Multiple algorithms can be used to compute the final schedule and mapping, for both uni-processor or multi-processor. All implemented periodic scheduling synthesis algorithms respect the following steps:

(1) decompose the graph: compute all firing relations (with undefined 𝜑);

(2) assign the priorities: see Section 4.2.1;

(3) partition tasks across available processors: this step may call internally step 5;

(4) compute all 𝜑: thanks to an ILP formulation;

(5) perform symbolic synthesis: thanks to RTA, see Section 4.2.2; (6) compute all task periods and offsets: thanks to an ILP formulation; [START_REF] Besnard | Timed behavioural modelling and affine scheduling of embedded software architectures in the AADL using Polychrony[END_REF] refine buffer delay and buffer size computation: see Section 4.2.3. Figure 5 details which schedule characteristics are computed by each of those steps, along with the corresponding objective. Steps (2) and (3) offer trade-offs between the throughput maximization and the total buffer size minimization objectives, according to the selected algorithm in Tables 1 and2 and the input parameters. For steps ( 4) and ( 6), respectively, when the ILP problem is not feasible or when the basis period is too large, the algorithms automatically state that the system is not schedulable. Additionally, the ADFG tool computes a few metrics such as the throughput Θ, this point is discussed in Section 4. The next Section 4.2 details a few aspects of the computation, including new contributions.

ADFG in details

Multiple improvements are presented in this section, they impact on different key points of the ADFG theory: the computation of priorities, of periods, of delays, and of metrics. All those improvements increase the accuracy or the usability of the ADFG tool and were unpublished so far.

Priority assignment, step (2).

Regarding priorities, the first improvement is a heuristic to break the tie when two actors have the same deadline in the SP_UNI algorithm (see Table 1) and in all multi-processor schedule synthesis algorithms (see Table 2). The second improvement enables to find trade-offs between total buffer sizes and throughput in the SP_UNI_UDH algorithm. We also briefly recall how the SP_UNI_LOP algorithm assigns priorities, as a pretext to introduce the buffer size approximation derived from Equations ( 5) and [START_REF] Bertogna | Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms[END_REF], which have been slightly modified. While the first improvement only aims at decreasing the actor offsets and delays on buffers, the two other priority assignment algorithms proposed by the ADFG tool try to minimize the buffer sizes.

Breaking the tie in Deadline Monotonic. The heuristic to break the tie with the Deadline or Rate Monotonic priority assignment is based on a graph topological ordering. When two actors have the same relative deadline or period, respectively, we assign different priorities for each of them, according to their appearance order in the topological ordering. With this heuristic, a producer actor has a higher priority than all its consumers having the same deadline or period. Thus, this heuristic avoids the need for actor offsets or delays since the producer is always executed before its consumers thanks to its higher priority. This phenomenon has been reproduced experimentally: all test applications having only actors with equal periods have neither delays nor offset when using this improvement on uni-processor, whereas some appear when not using the improvement. However, the graph topological order is not computed on the original SDF graph, but on its reduction to a Directed Acyclic Graph (DAG) of strongly connected components, as depicted in Figure 6. This means that the heuristic does not break the tie between two actors having the same deadline when both are present in the same strongly connected component (i.e. directed cycle): at least one actor has to start the cycle execution, whatever is its priority.

In the context of implicit deadlines, the SP_UNI algorithm assigns increasing priorities to the actors with increasing periods and the heuristic is used only when two actors have the same period. Note that the priority assignment is performed before the period synthesis: this is possible since the affine relations between the actors already hold the information of the relative firing clock speed of the actors, see Figure 4. The real periods do not matter for the priority assignment, only the natural ordering of the periods is important.

Configurable Utilization Distance Heuristic. The second improvement of the ADFG tool regarding priority assignment is based on an algorithm of variable complexity, configurable by the designer, called Utilization Distance Heuristic. A first version of this algorithm has been presented in the original thesis on ADFG theory [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF] (pages 96-97 in ref.) but was not configurable; it is used by the SP_UNI_UDH algorithm. In this article, we explain how this algorithm can be configured by the designer. The SP_UNI_UDH algorithm relies on a first priority assignment (Deadline Monotonic) and period synthesis (see Section 4.2.2), and then its heuristic is to perform permutations on the priorities of actors in order to select the priority assignment minimizing the total buffer size. However, these permutations may increase the periods of actors since the response time of some actors will inevitably be increased (see the following Section 4.2.2).

The new implementation allows the designer to configure an acceptable trade-off between the buffer size decrease and the period increase. We redefine here the utilization distance in terms of basis period and relative to the best one, 𝑇 𝐷𝑀 basis , obtained with Deadline Monotonic priority assignment. It is called utilization distance since the throughput (inversely proportional to the basis period, see Section 4.2.4) is linear to the processor utilization factor, see Equation [START_REF] Bini | A Response-Time Bound in Fixed-Priority Scheduling with Arbitrary Deadlines[END_REF]. Then the utilization distance dist (𝑝) ∈ [0, ∞[ gives a measure of throughput loss for 𝑇 basis (𝑝) obtained with the permutation 𝑝, see Equation [START_REF] Bodin | Diplomat: Mapping of Multi-kernel Applications Using a Static Dataflow Abstraction[END_REF]. 𝑇 basis (𝑝) is over-estimated for each permutation with a linear complexity formula thanks to the actor response times (detailed in [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF] pages 96-97). Now a 100% throughput loss, i.e. dist (𝑝) = 1, means a throughput division by 2.

dist (𝑝) = 𝑇 basis (𝑝) 𝑇 𝐷𝑀 basis -1 (13)
In the ADFG tool, it is now possible to specify a maximum percentage loss in throughput (i.e. period increase) and a minimum percentage gain in total buffer size minimization: a priority permutation is selected only if the throughput loss is less than the maximum and the buffer size gain greater than the minimum specified. To reduce the run time of the algorithm, it is also possible to set the permutation length 𝜌; indeed the total number of permutations explodes with their length: it is 𝜌!. If the permutation length is less than the number of actors, SP_UNI_UDH will Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice 1:13 try all priority permutations of the specified length in a sliding window iterating over the actors ordered by increasing Deadline Monotonic priorities. The factorial complexity of this algorithm may limit its use; however note that the optimal priority assignment of real-time tasks with offsets on homogeneous multi-processor also has a restrictive complexity: it is NP-hard [START_REF] Joseph | On the complexity of fixed-priority scheduling of periodic, real-time tasks[END_REF].

A new approximation of buffer sizes. The SP_UNI_LOP algorithm also selects the best priority assignment minimizing the total buffer size, but not taking into account the throughput loss. Its complexity is theoretically less than SP_UNI_UDH but not configurable, since it relies on the minimization by an ILP solver of a tournament matrix weighted by approximated buffer sizes [START_REF] Bouakaz | Design of Safety-Critical Java Level 1 Applications Using Affine Abstract Clocks[END_REF] (section 5.1 in ref.

). Both SP_UNI_LOP and SP_UNI_UDH algorithms use the same approximation of buffer sizes formalized in Equation ( 14) 6 . This approximation is an underestimation, obtained from Equations ( 5) and [START_REF] Bertogna | Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms[END_REF].

𝛿 𝑒 1→2 ≥ 𝜆 + 𝑎 𝑝 𝐶 under + 𝑎 𝑞 𝐶 over , with 𝜆 = (𝜆 𝑢 𝑞 -𝜆 𝑙 𝑝 ) + (𝜆 𝑢 𝑝 -𝜆 𝑙 𝑞 ) (14)
The values of the coefficients 𝐶 over and 𝐶 under are formalized in Equation ( 15); the optional +1 depends on the priorities and mapping of the producer actor 𝑣 1 and the consumer actor 𝑣 2 of the buffer 𝛿 𝑒 1→2 , see [START_REF] Bouakaz | An abstraction-refinement framework for priority-driven scheduling of static dataflow graphs[END_REF] (section IV in ref.

) for more details.

𝐶 under = 𝑑 -1 𝑛 ( +1) and 𝐶 over = 𝑛 -1 𝑑 ( +1) (15)
Although SP_UNI_LOP and SP_UNI_UDH algorithms are dedicated to the uni-processor case, those coefficients are also used in the ILP formulation computing all firing offsets 𝜑, which is generic for both uni-and multi-processor cases. Equation ( 14) is approximated by removing the -1 term in the numerator of the fractions, and by considering the inequality as an equality, see Equation [START_REF] Bouakaz | Earliest-deadline first scheduling of multiple independent dataflow graphs[END_REF]. Moreover, 𝑛 𝑑 is the irreducible fraction of 𝑎 𝑝 𝑎 𝑞 per definition. So this approximation limits integer explosion in the resulting coefficient rational number.

𝛿 𝑒 1→2 ≈ 𝜆 + 𝑎 𝑝 + 𝑎 𝑞 ( +𝑎 𝑝 ) ( +𝑎 𝑞 ) (16) Finally, the approximation of the buffer size used by the SP_UNI_LOP and SP_UNI_UDH priority assignment algorithms is summarized in Table 3 7 . Many other priority assignment algorithms exist [START_REF] Davis | A review of priority assignment in real-time systems[END_REF], as robust priority assignment [START_REF] Davis | Robust priority assignment for fixed priority real-time systems[END_REF] or assignment with threshold to limit the number of preemptions [START_REF] Wang | Scheduling fixed-priority tasks with preemption threshold[END_REF]. Unfortunately these two algorithms are not suitable for the ADFG tool since they necessitate the actor periods which are not known yet (only linear relation between the periods are known during this step).

𝑀 𝑣 1 = 𝑀 𝑣 2 𝑀 𝑣 1 ≠ 𝑀 𝑣 2 𝑃 𝑣 1 < 𝑃 𝑣 2 𝜆 + 𝑎 𝑝 + 2𝑎 𝑞 𝜆 + 2𝑎 𝑝 + 2𝑎 𝑞 𝑃 𝑣 1 > 𝑃 𝑣 2 𝜆 + 2𝑎 𝑝 + 𝑎 𝑞 𝜆 + 2𝑎 𝑝 + 2𝑎 𝑞
To conclude this subsection, note that there are as many priority levels as actors, which may be a constraint for some implementations. In the Real-Time Executive for Multiprocessor Systems 6 A bug in the implementation of the approximation was affecting both SP_UNI_LOP and SP_UNI_UDH in a previous release of the ADFG tool: consumer and producer actors were exchanged in a function call. The bug has been fixed for the evaluation of the present article. 7 Because of the new approximation in Equation ( 16), this table is slightly different than the original one in [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF] (RTEMS) operating systems the number of tasks is unlimited, but the number of priority levels is limited 8 to 255. Thus, in the ADFG tool, the code generation for the RTEMS operating systems works only on SDF graphs having at most 255 actors. Besides, µC/OS-III is not anymore limiting the number of tasks and priorities but the previous version µC/OS-II was limiting 9 the number of tasks and priorities to 255. [START_REF] Benazouz | A new method for minimizing buffer sizes for Cyclo-Static Dataflow graphs[END_REF]. The computation of periods is based on RTA [START_REF] Audsley | Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling[END_REF]: different values of the periods are tested between two bounds by performing a bisection, and the smallest valid period, i.e. greater than response time, is kept. As all actor periods can be expressed relatively to the basis period 𝑇 basis , the algorithm is called Symbolic Response Time Analysis (SRTA). Figure 7 depicts the main idea of SRTA. The SRTA algorithm is iterative: it starts with a period in the middle of the two bounds and tests if regular RTA ensures schedulability. If not, SRTA refines the bounds by taking the tested period as new lower bound. If yes, SRTA refines the bounds by taking the tested period as new upper bound. The algorithm stops when the two bounds are equal.

Computation of periods, step

It has been stated in a previous article on the ADFG theory [START_REF] Bouakaz | Design of Safety-Critical Java Level 1 Applications Using Affine Abstract Clocks[END_REF] (section 5.2 in ref.

) that the lower bound of the response time 𝑅 𝑙 𝑣 of a periodic actor 𝑣 is :

𝑅 𝑙 𝑣 = 𝐶 𝑣 -𝑃 𝑣 <𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 (1 -𝑈 𝑣 𝑖 ) 1 -𝑃 𝑣 <𝑃 𝑣 𝑖 𝑈 𝑣 𝑖
by analogy with the upper bound [START_REF] Bini | A Response-Time Bound in Fixed-Priority Scheduling with Arbitrary Deadlines[END_REF]:

𝑅 𝑢 𝑣 = 𝐶 𝑣 + 𝑃 𝑣 <𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 (1 -𝑈 𝑣 𝑖 ) 1 -𝑃 𝑣 <𝑃 𝑣 𝑖 𝑈 𝑣 𝑖
However this is an underestimation of the lower bound since it has also been proved that 𝑅 𝑣 ≥ 𝐶 𝑣 1-𝑃𝑣 <𝑃𝑣 𝑖 𝑈 𝑣 𝑖 [START_REF] Sjödin | Improved response-time analysis calculations[END_REF], and yet

𝐶 𝑣 1-𝑃𝑣 <𝑃𝑣 𝑖 𝑈 𝑣 𝑖 ≥ 𝐶 𝑣 -𝑃𝑣 <𝑃𝑣 𝑖 𝐶 𝑣 𝑖 (1-𝑈 𝑣 𝑖 ) 1-𝑃𝑣 <𝑃𝑣 𝑖 𝑈 𝑣 𝑖 .
Thus the period synthesis algorithm SRTA has been updated with the new equations resulting from the most accurate lower bounds: the aforementioned one [START_REF] Sjödin | Improved response-time analysis calculations[END_REF] as well as 𝑅 𝑣 ≥ 𝑃 𝑣 ≤𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 [START_REF] Joseph | Finding Response Times in a Real-Time System[END_REF]. Indeed, schedulability is guaranteed when all periodic tasks (i.e. actors in the SDF case) have their response time lower than the deadline: 𝑅 𝑣 ≤ 𝐷 𝑣 = 𝑇 𝑣 . Let us consider that the deadline is relative to the period: 𝐷 𝑣 = 𝛽 𝑣 𝑇 𝑣 with 𝛽 𝑣 ∈ [0, 1]. In the context of implicit deadlines, all 𝛽 𝑣 are equal to 1.

As 𝑇 𝑣 = 𝛼 𝑣 𝑇 basis , ensuring schedulability with RTA leads to the constraint 𝑇 basis ≥ Finally, the new initial lower bound of the basis period 10 , used in the SRTA algorithm, is:

𝑇 basis ≥ max 𝑣 ∈𝑉        𝐶 𝑣 𝛼 𝑣 𝛽 𝑣 + max        𝑃 𝑣 <𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 𝛼 𝑣 𝛽 𝑣 , ∑ 𝑃 𝑣 <𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 𝛼 𝑣 𝑖               (17)
When targeting a multi-processor, SRTA is called separately on each processor and considers the only actors mapped on the current processor (the mapping has been performed previously): partitioned scheduling is considered. Then the maximum of the basis period found over all processors is kept as the new basis period. Alternatively, better response time analysis algorithms could be used, such as a faster algorithm [START_REF] Lu | A faster exact schedulability analysis for fixedpriority scheduling[END_REF] which is kept for future work, or an algorithm for multi-processor with global FP scheduling [START_REF] Bertogna | Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms[END_REF]. Holistic RTA [START_REF] Tindell | Holistic schedulability analysis for distributed hard real-time systems[END_REF], taking into account communication time in distributed systems and already implemented in a few analysis tools [START_REF] Saad Mubeen | Implementation of Holistic Response-time Analysis in Rubus-ICE[END_REF], is also another possible direction for future work. Finally, the SRTA algorithm does not take into account the offset of the actors, although theoretically possible [START_REF] José | Schedulability analysis for tasks with static and dynamic offsets[END_REF], because offsets will be computed thanks to the phases in Equation (8). 4) and [START_REF] Besnard | Timed behavioural modelling and affine scheduling of embedded software architectures in the AADL using Polychrony[END_REF]. The ILP formulation solved in the abstraction part of the ADFG tool (see Section 4.1.1) already has the delays and buffer sizes as variables and computes them thanks to Equations ( 5) and ( 6), with the coefficients in Equation [START_REF] Bouakaz | An abstraction-refinement framework for priority-driven scheduling of static dataflow graphs[END_REF]. However, in order to refine the solution of the ILP formulation which relies on safe affine overestimation, delays and buffer sizes are computed again at the very end of the synthesis part, after having computed the periods and offsets. Delays and buffer sizes are computed using a simulation performed independently for each buffer on their abstract clock relation. Their behavior is simulated during one hyperperiod 𝐻 𝑒 1→2 = 1 lcm(𝑇 𝑣 1 ,𝑇 𝑣 2 ) of the buffer 𝛿 𝑒 1→2 , plus the time of the offsets and the time ensuring that the initial parts of the rates, 𝑝 0 and 𝑞 0 , have been finished. Previous results [22] show that this simulation length is sufficient. Yet, this simulation does not take into account the WCETs of actors; nevertheless it may improve the result of the two affine Equations ( 5) and ( 6) for CSDF and UCSDF graphs since the simulation avoids the affine overestimation. For SDF graphs, 𝜆 terms are already equal to 0 in Equations ( 5) and ( 6) and the simulation will not help to improve the results.

Computation of delays and buffer sizes, steps (

During the simulation, the delay of a buffer is the maximum deficit of data observed (underflow). For example in Figure 4, 𝑇 𝑣 1 < 𝑇 𝑣 2 so 𝑃 𝑣 1 < 𝑃 𝑣 2 , and as 𝜑 = 0, there is no offset between the actors, then 𝑣 1 is executed first, producing 2 tokens, followed by 𝑣 2 consuming 12 tokens. At this point of the simulation, the observed deficit is 12 -2 = 10 tokens. Once the delay has been computed, the simulation is performed a second time to compute the maximum number of tokens present at a time on the buffer, that is its size.

Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice 1:17

𝑣 1 𝑣 2 (2 0) (1)
Fig. 8. CSDF graph where repetition vector needs specific computation.

length of its sequences of production or consumption rate). The previous throughput computation used the formula Θ = An evaluation the ADFG tool is presented in Section 6, and includes results using these new computation of the throughput and the processor utilization factor.

CODE GENERATION

The ADFG tool supports automated code generation of the computed buffer sizes and other schedule characteristics for dataflow applications that are implemented in the Lightweight Dataflow Environment (LIDE) [START_REF] Lin | The DSPCAD framework for modeling and synthesis of signal processing systems[END_REF] 11 running on the RTEMS real-time operating system 12 . The code generator inputs are the characteristics computed using the ADFG theory, including: buffer sizes, periods, offsets, priorities and mapping. The generated code is then cross-compiled and tested by using the QEMU tool to emulate an ARM platform. A detailed evaluation of the code generator has been conducted and presented in [START_REF] Nam Tran | A Framework for Fixed Priority Periodic Scheduling Synthesis from Synchronous Data-flow Graphs[END_REF]. Interested readers can refer to this article for a complete presentation of our approach to integrate the ADFG tool in a framework with scheduling simulation and code generation. In this section, we summarize our approach of code generation and provide an update on the implementation of the period characteristic compared to [START_REF] Nam Tran | A Framework for Fixed Priority Periodic Scheduling Synthesis from Synchronous Data-flow Graphs[END_REF].

Actors and buffers in LIDE

LIDE [START_REF] Lin | The DSPCAD framework for modeling and synthesis of signal processing systems[END_REF] is a flexible, lightweight design environment that enables rapid experimentations with dataflow-based implementations. The usage of LIDE allows a systematic approach to instantiate dataflow graphs with the buffer sizes computed using the ADFG theory. Actors and buffers in LIDE are designed and implemented as C-based abstract data types (ADTs). To implement a data-flow application with LIDE we need to allocate buffers, instantiate actors, and connect them together.

A buffer is instantiated with the function lide_c_fifo_new which takes two input parameters: capacity and token_size. It allows us to apply the buffer sizes computed using the ADFG theory to the code generation step.

• Capacity: the computed buffer size is given as an input parameter of the following function lide_c_fifo_new. It is the number of tokens of which sizes are given as the second input parameter to the function.

• Token size: this information is given in the specification of the graph and passed directly to the code generator. In case of complex types, we assume that their specifications in C are also provided. Each actor has an associated context, which encapsulates pointers to the FIFO buffers that are associated with the edges incident to the actor. Four interface functions, namely new, enable, invoke and terminate are required to implement an actor. Designers can develop their own actors by appropriately specializing the prototype function templates. In this work, we assume that core functions of actors are implemented and we only generate the code to instantiate actors.

An actor is instantiated with the function lide_c_<actor_name>_new. The input parameters are buffers that are connected to the actor. An example of the generated code is given in Figure 9. This example is the code generated for the SDF graph presented in Figure 1 with computed buffer sizes. In the generated code, we declare the two buffers v1_v2 and v2_v3. These buffers are used as input paramters of in the *_new functions to create the three actors v1, v2, and v3.

Schedule characteristics in RTEMS

RTEMS is an open source real-time operating system that supports open standard Application Programming Interfaces (APIs) such as POSIX. We consider the usage of RTEMS to generate the computed schedule characteristics. Actor invocations and fixed-priority periodic scheduling are achieved by the usage of the POSIX thread library. Besides buffer sizes, four schedule characteristics are computed using the ADFG theory, namely: priority, core mapping (for processor mapping), period and offset. Code generation for these characteristics is done by exploiting the POSIX pthread API supported by RTEMS. One thread is generated per actor. The priority and core mapping attributes are natively supported. The period and offset are taken into account by implementing a periodic release per actor.

• Priority: POSIX pthread_attr_setschedparam function is used to set thread priorities.

• Mapping: POSIX provides the cpu_set function that allows us to choose the set of processors that a thread can execute on. • Period: periodic release of a thread is implemented by using the clock_nanosleep function with the flag TIMER_ABSTIME. It allows us to set the absolute time at which the thread shall wake up again. The wake up time is computed as below:

𝑤𝑎𝑘𝑒_𝑢𝑝_𝑡𝑖𝑚𝑒 := 𝑠𝑡𝑎𝑟𝑡_𝑡𝑖𝑚𝑒 + (𝑟𝑒𝑙𝑒𝑎𝑠𝑒_𝑛𝑢𝑚𝑏𝑒𝑟 × 𝑝𝑒𝑟𝑖𝑜𝑑) (18)
In [START_REF] Nam Tran | A Framework for Fixed Priority Periodic Scheduling Synthesis from Synchronous Data-flow Graphs[END_REF], we used the nanosleep function to implement periodic tasks. It is because the function clock_nanosleep was not in the list of directives provided by the clock manager in RTEMS 5.1 13 , which is the version targeted by our code generator. However, the authors in [START_REF] Bloom | Real-time systems development with RTEMs and multicore processors[END_REF] indicated that it is possible to use the clock_nanosleep function to implement periodic tasks in RTEMS. • Offset: is generated by adding an idle period to the first release of a thread.

An example of the generated code is given in Figure 10. We create a data structure named rtems_actor that encapsulates a lide_c_actor_context and its schedule characteristics. Then, these characteristics are passed to the attributes of a pthread accordingly. This example and its code can be duplicated systematically for any actors in the graph and their corresponding threads in order to apply schedule characteristics computed using the ADFG theory.

EVALUATION

This section presents an evaluation of the schedules synthesized by the ADFG tool. Results are compared to the state-of-the-art theoretical methods to compute buffer sizes and throughput in Section 6.1; optimum is reached for both metrics. Scheduling simulations have also been performed to compute the number of preemptions and the usage of memory, see Section 6.2.

The code of the ADFG tool is open-source and can be accessed online 14 . Experiments using Cheddar tool require its own installation; on the code repository, we provide a link to a virtual machine with ADFG and Cheddar installed. In addition, all benchmarks, scripts, and instructions to reproduce the results presented in this section are included in the code repository and in the virtual machine. Old binaries are also available online 15 , but they are outdated and the website hosting them is not maintained anymore.

The test applications come from StreamIt [START_REF] Thies | StreamIt: A Language for Streaming Applications[END_REF] and SDF3 [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF] benchmarks, including pacemaker [START_REF] Pellizzoni | Handling Mixed-criticality in SoC-based Real-time Embedded Systems[END_REF], h263 video decoder [START_REF] Oh | Fractional Rate Dataflow Model and Efficient Code Synthesis for Multimedia Applications[END_REF]. Eleven applications 16 have been selected for their representative characteristics detailed in Table 4: dataflow model, number of actors, and number of firings.

Scheduling synthesis evaluation

In this subsection, the synthesized schedules are evaluated directly regarding several metrics: processor utilization factor, sum of all buffer sizes, and throughput. Utilization factor and buffer sizes are studied with uni-processor algorithms provided by the ADFG tool while the throughput is studied with multi-processor algorithms and increasing number of available processors.

6.1.1 Impact of the priority in uni-processor. Figure 11 presents the utilization factor obtained for all applications with all uni-processor algorithms listed in Table 1, plus an algorithm synthesizing schedules for Earliest Deadline First (EDF) policy, given for reference. The maximum processor utilization factor, 1.0, is reached for all applications except cd2dat, pacemaker and receiver, the three CSDF applications. Despite the fact that cd2dat has 6 actors in its graph and more than a thousand firings in total, its processor utilization factor is only about 0.2 over 1. This is due to a limitation of our method: the SDF model imposes linear relation between all the actor integer periods (see Equation ( 7)), enforcing a common divisor to all. For cd2dat, the ADFG tool finds that the basis period must be a multiple of 160, which is already larger than the response time upper 14 https://gitlab.inria.fr/ADFG/adfg 15 http://polychrony.inria.fr/ADFG/ 16 Digital Radio Mondial receiver [START_REF] Moonen | Cache Aware Mapping of Streaming Applications on a Multiprocessor System-on-Chip[END_REF] is not included since its average processor utilization factor is lower than computed in bound 17 . Thus, it is better to avoid using relatively prime numbers as production and consumption rates in order to maximize the efficiency of the synthesized schedule. The processor utilization factor drop of h263decoder, mp3decoder, pacemaker and receiver while using algorithm SP_UNI_LOP is caused by another reason. The SP_UNI_LOP algorithm assigns priorities thanks to an extra ILP formulation solely minimizing an approximation of total buffer size (see Section 4.2.1). Then, the actor priorities assigned by the SP_UNI_LOP minimize the total buffer size at the cost of a lower throughput: the synthesized periods are greater than for the other algorithms. Figure 12 compares the sum of all buffer sizes synthesized by the ADFG tool, using the same algorithms and application as in Figure 11. The last column of each cluster holds the minimum achievable total buffer size, as computed with the tool SDF3. The ADFG tool reaches the minimum total buffer size for all of its uni-processor algorithms and applications having ì 𝑧 = ì 1, but not always for the five other applications on the right. As for the processor utilization factor, h263decoder, mp3decoder, pacemaker and receiver applications have lower total buffer size while using algorithm SP_UNI_LOP. However while the drop factor seems constant for buffer sizes among all applications (see Figure 12), the processor utilization factor loses multiple order of magnitudes for h263decoder and receiver but remains similar for mp3decoder (see Figure 11). Besides, the complexity of the extra ILP formulation of SP_UNI_LOP is quite high (number of variables is quadratic to the number of actors), so this algorithm should be considered only at last resort by users of the ADFG tool. Instead one can use the SP_UNI_UDH algorithm described previously in Section 4.2.1: it enables to find trade-offs between the application throughput and its minimum total buffer size.

We briefly evaluate the SP_UNI_UDH algorithm on the receiver application, because this application has the highest drop of throughput for SP_UNI_LOP: it is divided by about 300 compared with the SP_UNI algorithm. At the same time, the total buffer size is divided by about 2. Thus, we 17 In comparison, a simplification of the CSDF production rate on the last buffer of cd2dat, from (0101011) to (1111111), makes the related affine relation become 𝑛 𝑑 = 1 1 instead of 4 7 . With such simplifaction, the basis period must be a multiple of only 40 instead of 160 initially and the utilization factor increases to 0.96 instead of 0. expect that SP_UNI_UDH helps to find possible trade-offs for receiver between the two extrema found by SP_UNI and SP_UNI_LOP. With the default configuration of 10 percent throughput loss allowed against 10 percent total buffer size decrease with permutation of length 4, denoted 10-10-4, SP_UNI_UDH cannot find better than SP_UNI: both throughput and total buffer size are identical on Figure 11 and Figure 12, respectively. However, the designer can specify manually the allowed loss and, for example, the SP_UNI_UDH configuration 6000-30-3 leads to a trade-off with throughput divided by about 35 and total buffer size divided by about 1.5. An automated exploration of possible trade-offs is kept for future work, but due to the approximation used to compute the periods in SP_UNI_UDH, the throughput loss is overestimated (indeed, 6000 percent is even larger than the maximum observed ratio of 300). Results of Figures 11 and12 are similar with the zero delay option. Indeed, to compensate the zero delay option, the firing offset of the actors increases according to Equations ( 5) and [START_REF] Bertogna | Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms[END_REF]. In turns, the zero delay option results in an increase of the regular offsets 18 of the actors according to Equation ( 8), whereas they are most often equal to zero without the zero delay option. Moreover all six applications with equal actor periods (Beamformer to Vocoder, with ì 𝑧 = ì 1) reach the same processor utilization factor and total buffer size independently to the algorithm used to assign actor priorities. In such case the priorities only impact on the actor offsets or on the delays, and their presence is completely avoided thanks to the first improvement presented in Section 4.2.1. Note that with the zero delay option enabled, all graphs with directed cycles deadlock and the ILP formulations of the ADFG theory are infeasible. However, the selected applications do not have directed cycles and so the ADFG tool finds a solution.

6.1.2 A closer look to SRTA bisection. All synthesis algorithms provided by the ADFG tool for FP scheduling use the SRTA algorithm described in Section 4.2.2, and some of them call it multiple times 19 ; hence, it is important to check its efficiency. As SRTA performs a bisection between the response time lower and upper bound, it is especially important to measure the gap between these bounds and so the number of bisection steps.

Figure 13 depicts the number of bisection steps of SRTA for SP_MULT_BF_FBBFFD and SP_UNI algorithms. For the multi-processor algorithm, 4 processors were considered and the reported number of bisection is actually the sum of all the 4 SRTA calls (one per partition). The number of steps per processor is quite stable, slightly below 20, for all applications having more than 10 actors. This number of steps decreases for the applications having only a few actors, cd2dat, h263decoder, pacemaker and receiver. In only one case, h263decoder, the number of bisection steps is reduced for the multi-processor algorithm compared with the uni-processor one. Most probably, this is due to the high amplitude of actor firings and WCETs in h263decoder. However, more applications and a proper statistical analysis are needed to assert the causes of this phenomenon.

Last but not least, the bisection steps plotted in Figure 13 were actually counted separately when going up or down in the search interval. Surprisingly, the bisection is always going down towards the response time lower bound, which could mean that the lower bound is close to be optimal. The first six applications (from the left) all have equal periods, it is a plausible cause of the response time lower bound being sufficient for checking schedulability. For cd2dat, the cause is the high value of the common divisor to all integer periods. But again, a more extensive analysis is needed to assert the causes of this phenomenon, especially for the four last applications (to the right).

6.1.3 A closer look to (U)CSDF applications. ADFG tool supports two extensions of the SDF model: CSDF and UCSDF, especially thanks to an approximation of the evolution of tokens in buffers with an average rate (see Equation ( 2)). However, this approximation is safe regarding to processor utilization factor and buffer sizes but makes the synthesized periods and buffer sizes suboptimal. Two independent refinements performed at the end of the synthesis part of the ADFG theory partially overcome this problem. First, for the processor utilization factor, as described in Section 4.2.4: actor periods are not updated and eventually remain suboptimal, but a more accurate value of the metric is given to the designer. Second, the buffer sizes, as described in Section 4. tool simulates each buffer over the logical clock abstraction of its producer and consumer firings, and updates the sizes to the simulated smallest value. The two aforementioned refinements have been evaluated on the three considered CSDF test applications: cd2dat, pacemaker and receiver. Figure 14a plots the average refined processor utilization factor (left column) against the overestimated one used in the schedule synthesis (right column). The refinement is useful only for CSDF applications specifying different WCET per firing, which is only the case of the receiver application. Figure 14b plots the overestimated buffer size computed in the schedule abstraction ILP (left column) against the refined one simulated after the schedule synthesis (middle column) and the minimum possible without any resource constraint (right column). Only cd2dat benefits from the buffer size refinement because two of its actors (fir3 and fir4) alternatively produce one or zero token on their outgoing buffers. The buffer size reduction is 50%: from a total size of 16 to 8 for the SP_UNI algorithm.

6.1.4 Impact of multi-processor. The authors of the DARTS [START_REF] Bamakhrama | Hard-real-time scheduling of data-dependent tasks in embedded streaming applications[END_REF] tool proved that maximum throughput is obtained for the Beamformer application with a minimum of 29 processors for any partitioned scheduling, and 51 processors is an upper bound for the partitioned EDF policy [START_REF] López | Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems[END_REF] (which is close to the number of firings equal to 57). To evaluate the efficiency of the schedule characteristics computed using the ADFG theory, we synthesized the schedule of Beamformer for an increasing number of processors, as shown in Figure 15.

On Figure 15, line plots of EDF_MULT_BF_UF_ID, SP_MULT_BF_FBBFFD and SP_MULT_BF_SRTA algorithms are actually the same, above all other lines. They are close to the maximum throughput from 28 processors, and actually reach the maximum possible throughput for 44 processors, before the upper bound of 51. Only the SP_MULT_MBS-BUFFER_MIN algorithm does not reach the maximum, even with 52 processors. This is expected since this latter algorithm minimizes the total buffer size instead of maximizing the throughput [START_REF] Honorat | ADFG: a scheduling synthesis tool for dataflow graphs in real-time systems[END_REF] 20 ; previous results proved that both objectives cannot be optimized at the same time [START_REF] Stuijk | Throughput-Buffering Trade-Off Exploration for Cyclo-Static and Synchronous Dataflow Graphs[END_REF]. The execution time of the synthesis is not impacted by the number of processors: it is stable for all number of processors, around one second for all algorithms except the SP_MULT_MBS ones, which needs up to three minutes when minimizing the buffer sizes of the Serpent application (with an Intel i7-3740QM @2.70GHz processor). Note that even if EDF scheduling policy is considered better than FP policy [START_REF] Buttazzo | Rate monotonic vs. EDF: judgment day[END_REF], the ADFG tool synthesizes periods with the same utilization factor for both policies in the uni-processor case, and reaches the maximum throughput at the same time as the SP_MULT_BF_FBBFFD and SP_MULT_BF_SRTA synthesis algorithms for FP policy.

Finally, we recall that the ADFG theory always synthesizes the periods so that the application is schedulable. Hence, the ADFG tool is inherently safe to the Dhall's effect [START_REF] Sudarshan | On a Real-Time Scheduling Problem[END_REF]. Moreover, as we use partitioned scheduling and best fit mapping with SRTA 21 , the ADFG tool synthesizes efficient period even when the WCET of an actor is the double of all others for example, as illustrated in Figure 16.

6.1.5 Impact of the graph. Different kinds of graph topology are present in the test applications. For example, Beamformer is symmetrical with at most 12 actors in parallel paths, while DES is long and thin with at most 3 parallel paths. Vocoder is a mix: widely parallel at the beginning and sequential at the end. Despite these differences of topology, we do not observe substantial differences in the efficiency of the synthesized schedules. Yet the efficiency can be severely decreased by the integer properties of the rates, as seen for the cd2dat application in Section 6.1.1. 20 SP_MULT_MBS-BUFFER_MIN algorithm actually minimizes the number of memory transfer between processors when mapping the actors, but to do so it may avoid using all available processors. Indeed, in the Table 3 used by the SP_MULT_MBS-BUFFER_MIN algorithm, buffers are larger if producer and consumer actors are not on the same processor. In practice SP_MULT_MBS-BUFFER_MIN uses only half of the available processors. 21 The mapping algorithm maps the actors, sorted by increasing priority, to the processor ensuring the highest throughput. One can think that the ADFG theory restriction to weakly connected graphs is too limiting. Yet this restriction is easily overcome by adding a dummy source actor having virtual dependencies to the unconnected actors. For example, one can consider in the graph of Figure 16a that the actor 𝑣 1 is a dummy actor (with the smallest possible WCET equal to 1), present only in order to connect the graph consisting of actors 𝑣 2 and 𝑣 3 .

(1) 2 𝑣 2 𝑣 2 Proc. 2 𝑣 (1) 1 𝑣 (1) (1) 2 𝑣
𝑣 (2) 1 𝑣 (2) 3 𝑣 1 , 𝑣 3 𝑣 1 , 𝑣 3 3
Another drawback of the ADFG theory could be the absence of auto-concurrency. However, it can be overcome by duplicating actors in the input graph, as it is done in the Beamformer SDF graph with the symmetrical parallel paths corresponding to the same kernel applied to different data.

Simulation with CHEDDAR

Scheduling simulation is used in order to provide a thorough evaluation of the schedules synthesized by the ADFG tool. It allows us not only to verify the correctness of the results but also to obtain additional information on the application execution. The ADFG tool can inter-operate with Cheddar [START_REF] Singhoff | Cheddar: a flexible real time scheduling framework[END_REF] information obtained by scheduling simulation includes the number of preemptions and the buffer utilization. The simulation is performed over one hyperperiod plus the maximum of all offsets. Figure 17 presents the number of preemptions measured in the uni-processor case. There is no preemption for all six applications in which each actor is fired only once (see Table 4a). Indeed, these actors all have the same period, and the heuristic to break priority tie presented in Section 4.2.1 avoids offsets; all firings are released at the same time and executed completely one after the other in the order of their priorities being the graph topological order. The number of preemptions is of the same order of magnitude as the total number of firings for the five other applications (see Table 4b). Moreover, when minimizing the total buffer size with SP_UNI_LOP algorithm, it also reduces the number of preemptions especially for h263decoder, mp3decoder and receiver applications.

Buffer simulation is even more interesting. Figure 18 details the buffer utilization 𝐵𝑇 𝑚𝑎𝑥 , which is computed by taking into account the maximum number of tokens that are present in all buffers during the simulation length divided by the total buffer size. Equation

For each time unit 𝑡 during the simulation length from 0 to 𝑡 𝑠𝑐ℎ𝑒𝑑 , the number of tokens stored in every buffer 𝑒 at time 𝑡, denoted 𝑛𝑏_𝑡𝑜𝑘𝑒𝑛 𝑡 𝑒 , is summed. Then, the maximum value over time is divided by the sum of buffer sizes. Tokens are popped from the input buffers of an actor at its start time, and pushed to its output buffers at its finish time. When two or more actors write or read at the same time from different processors, the simulation analysis reorders all the write operations before the reads. Buffers are all statically and independently allocated: they do not share memory.

In average of the applications and synthesis algorithms plotted in Figure 18, the memory containing all buffers is used at most to only 56% of its capacity. This percentage is similar for all applications and algorithms, except for the cd2dat CSDF application which uses approximately 68% of memory. The SP_MULT_MBS-BUFFER_MIN algorithm reaches a slightly better buffer utilization, but at the cost of a throughput loss (see Footnote 20). The fact that buffers are never filled to their maximum size is not surprising knowing that their size is refined by the ADFG tool (see Section 4.2.3) without taking into account the execution time. Such refinement may be useful for CSDF applications but has no impact otherwise. Moreover while one buffer is full, others may be empty.

The h263decoder application having only 4 actors is a simple enough example to explain why the buffer size is overestimated. Its source actor vld produces 594 token and has a WCET more than 10 times smaller than its period. vld is executed once while its only consumer, iq actor consuming 1 token, is executed 594 times. In such case the ADFG tool safely approximates the number of delays to 594 (that are all the ones consumed by iq between two executions of vld) and doubles the buffer size accordingly because vld has a lower priority than iq. However the optimal number of delays is only 44 (if fully partitioned) due to the small WCET of vld compared to its period: after 44 executions of iq, vld has already finished its execution and thus has produced 594 new token.

In any case, the buffer simulation done by Cheddar demonstrates that our synthesized buffer sizes and delays are correct but that an important ratio of memory is wasted (see Figure 12). The memory waste is due to the ADFG theory overestimation and to the independent buffer allocation model itself. Thus, other techniques to reduce the memory footprint used for static scheduling, such as the computation of a mutual exclusion graph of all firing dependencies and buffer merging techniques [START_REF] Desnos | On Memory Reuse Between Inputs and Outputs of Dataflow Actors[END_REF], would be interesting to adapt to our periodic scheduling case.

CONCLUSION

In this article, we have presented an overview of the ADFG tool, which uses affine relations as a model abstraction to efficiently map actors in dataflow graphs to real-time tasks. This tool synthesizes multiple schedule characteristics, and generates code for the RTEMS operating system. The ADFG tool applies an original and efficient combination of formal methods, and the correctness of the implementation has been evaluated through extensive synthesis experiments and simulations. Moreover, inter-operability between tools (scheduling synthesizer, simulator, code generator) was a key property to perform these experiments, and it greatly helps the system designers. Finally, the 12years work done on the ADFG tool has shown that the theory it relies on is mature enough to go up to code generation and execution 22 , although some important timing metrics (as preemption delay) are still not taken into account. Future work includes connecting our framework with a WCET analysis tool, such as Heptane [START_REF] Hardy | The Heptane Static Worst-Case Execution Time Estimation Tool[END_REF], to provide a holistic analysis. In addition, more theoretical investigations lie ahead, such as employing cyclo-static WCETs for CSDF actors with a multiframe model [START_REF] Mok | A multiframe model for real-time tasks[END_REF], or improving the effectiveness of the delay computation with retiming techniques [START_REF] Leiserson | Retiming synchronous circuitry[END_REF].

Fig. 1 .Fig. 2 .

 12 Fig. 1. A simple acyclic delayless SDF graph.

( a )

 a Buffer between 𝑣 1 and 𝑣 2 , its affine metrics are above the buffer arrow and its derived affine relation is below it. Firing clock representation over lcm(𝑛, 𝑑) = 15 ticks, the two tasks start on the same tick because 𝜑 = 0.

Fig. 4 .

 4 Fig. 4. Affine metrics and corresponding task firing clocks.

Fig. 5 .

 5 Fig. 5. Main steps of the ADFG tool: from input graph to concrete periods and buffer sizes, with intermediate results and objectives.

1 = {𝑣 4 , 𝑣 5 } 2 =Fig. 6 .

 14526 Fig.6. Graph topological order for priority assignment.

Fig. 7 .

 7 Fig. 7. Initial scheduling bounds on the basis period 𝑇 basis based on the response time of actor 𝑣. Considering all actors, lower bound is max 𝑣 ∈𝑉 𝑅 𝑙 𝑣 𝛼 𝑣 and upper bound is max 𝑣 ∈𝑉 𝑅 𝑢 𝑣 𝛼 𝑣 .

1 lcm 1 ì

 11 𝑣 ∈𝑉 {𝑇 𝑣 } , and has been replaced by Θ = 𝑧 [𝑣 ]•𝑇 𝑣 (equal for any 𝑣 ∈ 𝑉 ); this new formula is used in the evaluation.

1 /Fig. 9 .

 19 Fig. 9. An example of actors and buffers declaration with LIDE.

Fig. 10 .

 10 Fig. 10. Generated code configuring the schedule characteristics in RTEMS.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Processor utilization factor of test applications.

Fig. 13 .

 13 Fig. 13. Number of bisection steps of the SRTA algorithm in the ADFG tool.

  ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

Fig. 14 .

 14 Fig. 14. Refinement of processor utilization and buffer size for CSDF applications.

Fig. 15 .

 15 Fig. 15. Throughput of Beamformer synthesized by the ADFG tool, in function of the number of processors.

  SDF graph with repetition vectorì 𝑧 = [1, 2, 1] and WCETs 𝐶 𝑣 1 = 1, 𝐶 𝑣 2 = 2, 𝐶 𝑣 3 = 4.

Fig. 16 .

 16 Fig. 16. Real-time schedule synthesized by SP_MULT_BF_SRTA algorithm, 𝑈 = 1.5.

  , which is an open source scheduling analyzer. The CSDF graph model and the buffer verification (i.e. overflow and underflow) are already supported by the simulator. The additional ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

Fig. 17 .

 17 Fig. 17. Number of preemptions per single execution, in the uni-processor case.

Fig. 18 .

 18 Fig.[START_REF] Bouakaz | Design of Safety-Critical Java Level 1 Applications Using Affine Abstract Clocks[END_REF]. Maximum number of token present at a time in all buffers, in the multi-processor case (4 processors).

Table 1 .

 1 Uni-processor FP algorithms.

	Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice	1:7
	0		5	10	15	20	25	30	35	40	45	50
	𝑣 1			𝑣 1			𝑣 1			𝑣 1		𝑣 1
	Proc. 1	𝑣	(1) 1		𝑣	(1) 1		𝑣	(1) 1		𝑣	(2) 1	𝑣	(2) 1
							𝑣 2 , 𝑣 3				𝑣 2 , 𝑣 3
	Proc. 2						𝑣	(1) 2	𝑣	(1) 3		𝑣	(1) 2	𝑣	(1) 3
	Fig. 3. Real-time schedule synthesized by ADFG tool for the input graph in Figure 1 without delays, considering
	two processors.
	graph topological ordering, are detailed in Section 4.2. Actor mapping, or more precisely graph
	partitioning, is not addressed in this article, interested readers can refer to [40] (section 5.2 in ref.).
	Name		Priority assignment
	SP_UNI		Deadline Monotonic with graph topological ordering (see Section 4.2.1)
	SP_UNI_LOP Priorities assigned by ILP, to minimize total buffer size (see Section 4.2.1)
	SP_UNI_UDH Priorities assigned by combinatorial search with utilization distance heuristic
			(see Section 4.2.1), to minimize total buffer size
	Name				Mapping		Complementary information
	SP_MULT_MBS		SCOTCH [68] Offers throughput vs total buffer size trade-offs [40]
	SP_MULT_BF_FBBFFD Best Fit + FFD Uses demand bound function [30] for the mapping
	SP_MULT_BF_SRTA	Best Fit + SRTA Used for Figure 3, SRTA is detailed in Section 4.2.2

Table 2 .

 2 Multi-processor FP algorithms.

  2.4.Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice 𝜑 𝑒 , 𝜃 𝑒 , 𝛿 𝑒

				1:11
		(1) graph	(2) priority	(3) actor
	UCSDF	decomposition	assignment	mapping
	graph	set: 𝑛, 𝑑, 𝜆	set: 𝑃 𝑣	set: 𝑀 𝑣
		obj: -	obj: min𝛿/maxΘ	obj: min𝛿/maxΘ
	(7) buffers	(6) periods	(5) basis period	(4) offsets
	refinement	concretization	bisection	resolution
	set: 𝜃 𝑒 , 𝛿 𝑒 obj: min𝛿	set: 𝑇 𝑣 , 𝑂 𝑣 obj: maxΘ	set: 𝑇 basis obj: maxΘ	set: obj: min𝛿+𝜑

ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

Table 3 .

 3 Buffer size approximation for FP scheduling. 𝑀 𝑣 is the processor number of an actor 𝑣 and 𝑃 𝑣 is its priority.

  𝛼 𝑣 𝛽 𝑣 . The response time lower bound 𝑅 𝑙 𝑣 = max{ 𝑃 𝑣 ≤𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 , ∀𝑣 ∈ 𝑉 , 𝑇 basis ≥ 𝑃 𝑣 ≤𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 𝛼 𝑣 𝛽 𝑣 and the second part leads to: ∀𝑣 ∈ 𝑉 , 𝛼 𝑣 𝛽 𝑣 𝑇 basis ≥ 𝐶 𝑣 1 -𝑃 𝑣 <𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 𝛼 𝑣 𝑖 𝑇 basis ⇔ 𝛼 𝑣 𝛽 𝑣 𝑇 basis -𝛼 𝑣 𝛽 𝑣 ∑ 𝑃 𝑣 <𝑃 𝑣 𝑖 𝐶 𝑣 𝑖 𝛼 𝑣 𝑖 ≥ 𝐶 𝑣 ⇔ 𝑇 basis ≥ 𝐶 𝑣 𝛼 𝑣 𝛽 𝑣

	𝑅 𝑙 𝑣 } [43, 71] can be rewritten 1:15 ∑ 𝐶 𝑣 𝑖 knowing that 𝑈 Real-Time Fixed Priority Scheduling Synthesis using Affine DataFlow Graphs: from Theory to Practice 𝐶 𝑣 1-𝑃𝑣 <𝑃𝑣 𝑖 𝑈 𝑣 𝑖 bound leads to: + 𝑃 𝑣 <𝑃 𝑣 𝑖 𝛼 𝑣 𝑖

𝑣 = 𝐶 𝑣 𝑇 𝑣 = 𝐶 𝑣 𝛼 𝑣 𝑇 basis . Thus the first part of the maximum of the response time lower 8 https://docs.rtems.org/releases/rtems-5.1/c-user/task_manager.html#task-priority 9 https://micrium.atlassian.net/wiki/spaces/osiiidoc/pages/131377/uC-OS+uC-OS-II+and+uC-OS-III+Features+ Comparison ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

Table 4 .

 4 ADFG, see Section 4.2.4. Main characteristics of test applications.

	1:20

ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

  19 defines 𝐵𝑇 𝑚𝑎𝑥 .

	𝐵𝑇 𝑚𝑎𝑥 =	max ∀𝑡,0≤𝑡 ≤𝑡 𝑠𝑐ℎ𝑒𝑑	𝑒 ∈𝐸 ∑	𝑒 ∈𝐸 𝑒 / 𝑛𝑏_𝑡𝑜𝑘𝑒𝑛 𝑡 ∑	𝛿 𝑒

In self-timed scheduling, each task is fired whenever available resources allow it, regarding to the consumed and produced tokens to avoid buffer underflows and overflows, and regarding to the processors availability if not unlimited. ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January

https://ptolemy.berkeley.edu/

https://daedalus.liacs.nl/daedalus-rt.html

A directed graph is said to be weakly connected when its underlying undirected graph is connected. ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

However, the ADFG tool also supports various EDF scheduling policies[START_REF] Honorat | ADFG: a scheduling synthesis tool for dataflow graphs in real-time systems[END_REF].

ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

This constraint is used in replacement of the former second order polynomial equation in[START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF] (page 97). ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

http://dspcad.umd.edu/projects/lide/lide.htm

https://www.rtems.org/ ACM Trans. Embedd. Comput. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2023.

See examples of regular offset in Figures3 and 16.

SP_UNI_UDH calls SRTA twice. All multi-processor algorithms call it 𝑚 times, that is once per partition. Additionally

Unfortunately, this approach suffers an important drawback: the delays are a functional feature of the application and it is in general not valid to assign or rearrange delay values in arbitrary ways. For example, the ADFG tool does not respect retiming rules [START_REF] Leiserson | Retiming synchronous circuitry[END_REF][START_REF] Keshab | VLSI digital signal processing systems : design and implementation[END_REF] when computing the delays. Retiming rules have originally been depicted for task graph representing processor circuits: added delays must form a feed-forward graph cut of the graph. However, there is no generic retiming rule for any UCSDF graph.

Hence, three options have been added to the ADFG tool to improve the placement of delays. The first option keeps the delays or buffer sizes that the designer considers as fixed; the fixed values are injected in the first ILP formulation and the simulation checks if they are coherent. If the simulation finds higher value of delays or buffer sizes, it emits a warning. It is possible to keep only a part of the and buffer sizes, and let the ADFG tool compute the others. The second option enforces the delays to be a multiple of the lowest common multiple of the production and consumption rate of the buffer. It ensures that the injected tokens are synchronized with the execution of the two actors of the buffer. The third option enforces all delays to be zero, it is a specific case of the first option. Note that this zero delay option leads to unfeasible ILP formulations of Equations ( 5) and ( 6) if the UCSDF graph contains directed cycles, and leads to non-zero phases/offsets otherwise. 1) and [START_REF] Bertogna | Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms[END_REF]. Two main metrics are computed during the synthesis part of the ADFG tool: the processor utilization factor, and the throughput. However, the algorithms used to compute these two metrics where initially not consistent for CSDF and UCSDF graphs; they have been improved in the new implementation. These modifications have no impact on the SDF graphs.

Computation of metrics, steps (

First, the WCET of an actor may also be expressed in the form of a sequence of integers, as supported by the SDF3 [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF] file format, which is a supported input of the ADFG tool. This representation allows the WCET to be specific to each firing of the actor and better fits the reality where firings consuming or producing numerous data most probably have a different execution time than firings of the same actor when consuming or producing only a few data. This situation occurs in the Digital Radio Mondiale receiver CSDF application [START_REF] Moonen | Cache Aware Mapping of Streaming Applications on a Multiprocessor System-on-Chip[END_REF]: the CD actor has two different WCETs, depending on its production rate. Unfortunately, the ADFG theory is not yet adapted to consider the WCET as a sequence of integers, and instead considers only the maximum value of this sequence. Thus, the processor utilization factor computed by the ADFG tool may be overestimated when considering CSDF and UCSDF graphs. In order to give better information to the designer, the processor utilization factor 𝑈 is now computed again at the end of the synthesis part, once all periods are computed, with the average WCET over the sequence length. The second value is not used by the ADFG tool and is solely intended to inform the designer. For the Digital Radio Mondiale receiver, SP_UNI algorithm finds 𝑈 = 0.99 whereas 𝑈 avg = 0.76.

Second, the computation of the average rates 𝑎 𝑝 and 𝑎 𝑞 (see Equation ( 2)) used in the abstraction part may lead to incorrect computation of the repetition vector of the application for CSDF and UCSDF graphs. Indeed, the ADFG tool stores all the fractions in the irreducible form and thus loses the information of the minimal amount of firings needed to iterate over all the possible production and consumption rates of CSDF and UCSDF actors. For example, the actor 𝑣 1 in Figure 8 has the average production rate of 1, as does actor 𝑣 2 . Thus, the repetition vector of the graph in Figure 8 is [START_REF] Andrade | From Streaming Models to FPGA Implementations[END_REF][START_REF] Andrade | From Streaming Models to FPGA Implementations[END_REF] according to the average rates, whereas it should be [START_REF] Audsley | Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling[END_REF][START_REF] Audsley | Applying New Scheduling Theory to Static Priority Pre-emptive Scheduling[END_REF] since the cyclo-static production rate of 𝑣 1 has a length of 2. Thus, the computation of the repetition vector has been extended to the CSDF and UCSDF cases in the current version of the ADFG tool, and leads to a redefinition of the throughput Θ using the repetition vector ì 𝑧. The repetition vector is computed first using the average rates, and is multiplied by a global factor ensuring that all firings are taken into account. The global factor is the least common multiple of the first repetition factor of any actor, and of the