Alexandre Honorat
email: ahonorat@insa-rennes.fr

Karol Desnos
email: kdesnos@insa-rennes.fr

Shuvra S Bhattacharyya

Jean-François Nezan
email: jnezan@insa-rennes.fr

Scheduling of Synchronous Dataflow Graphs with Partially Periodic Real-Time Constraints

Keywords: CPS, SDF, real-time, periodic, scheduling

Modern Cyber-Physical Systems (CPSs) are composed of numerous components, some of which require real-time management: for example, management of sensors and actuators requires periodic deadlines while processing parts do not. We refer to these systems as partially periodic. In a partially periodic system, precedence constraints may exist between periodic and aperiodic components. It is notably the case in CPSs where sensors measuring physical variables at a fixed sampling rate are typically feeding data to one or more processing part.

A critical challenge for any real-time CPS software is its scheduling on an embedded computing platform. The increasing number of cores in such platforms (as Kalray MPPA Bostan having 288 cores) makes offline non-preemptive scheduling techniques efficient to respect real-time constraints, but requires new analysis and synthesis algorithms. In this paper, we study the schedulability of partially periodic systems modeled as Synchronous Data Flow (SDF) graphs. Our contributions are a few necessary conditions on any live SDF graph, and a linearithmic offline non-preemptive scheduling algorithm on vertices of any directed acyclic task graph. The presented algorithm has been evaluated on a set of randomly generated SDF graphs and on one real use-case. Experiments show that our proposed non-preemptive scheduling algorithm allocates thousands of tasks in less than a second. In the last experiment, the computed schedules achieve a throughput close to that one obtained with global Earliest Deadline First (EDF) scheduling.

INTRODUCTION

Cyber-Physical Systems (CPSs) are real-time systems: they are constrained by deadlines on tasks. The tasks are scheduled so that the deadlines are met, inside threads of an operating system or directly on bare-metal. In order to perform their analysis and execution, such real-time systems are modeled with tasks having extra periodicity constraints for the deadlines, and precedence constraints for the data. For systems with only periodic tasks, synchronous languages and related tools as Esterel [START_REF] Berry | The Esterel synchronous programming language: design, semantics, implementation[END_REF] and SynDEx [START_REF] Grandpierre | Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors[END_REF] are a good choice to check the schedulability and to compute a schedule. On the contrary, a few online schedulers [START_REF] Fohler | Joint scheduling of distributed complex periodic and hard aperiodic tasks in statically scheduled systems[END_REF][START_REF] Lipari | Schedulability analysis of periodic and aperiodic tasks with resource constraints[END_REF] focus on the execution of aperiodic, sporadic and periodic tasks together, but these schedulers do not consider precedences. Yet modern CPSs have periodic components interacting with aperiodic components, and with precedence constraints here expressed in the Synchronous Data Flow (SDF) model. This paper aims to analyze the schedulability of such CPSs, called partially periodic, and to schedule them systematically and efficiently. A few necessary conditions and an offline non-preemptive scheduling algorithm are introduced for this purpose. Both have been implemented in the PREESM tool [START_REF] Pelcat | Preesm: A dataflow-based rapid prototyping framework for simplifying multicore DSP programming[END_REF].

Image signal processing systems and visual servoing are typical examples of partially periodic CPSs where certain components are periodic. For example, a camera films at a periodic framerate and the images arrive to the aperiodic processing components as a stream. Other components may also be periodic, as the input of servo-motors which must be regularly updated. Thus the processing part often depends on periodic inputs and must provide periodically one or more outputs, but does not have to be periodic itself. The flexibility to deviate significantly from periodic operation arises, for example, if data is buffered between components. One possible use-case is the Simultaneous Localization And Mapping (SLAM) application: it constantly retrieves information from a camera or a LIDAR and then processes data to reconstruct a map of the environment and to move according to this map [START_REF] Wen | Camera Recognition and Laser Detection based on EKF-SLAM in the Autonomous Navigation of Humanoid Robot[END_REF]. Sensor fusion [START_REF] Zhang | Sensor Fusion of Monocular Cameras and Laser Rangefinders for Line-Based Simultaneous Localization and Mapping (SLAM) Tasks in Autonomous Mobile Robots[END_REF] or other techniques [START_REF] Gee | Lidar guided stereo simultaneous localization and mapping (SLAM) for UAV outdoor 3-D scene reconstruction[END_REF] take benefit of camera and LIDAR at the same time.

This paper focuses on CPSs with periodic and aperiodic components, which are modeled as SDF graphs [START_REF] Lee | Synchronous data flow[END_REF]. SDF is commonly used to model image processing applications, as for SLAM with one camera [START_REF] Piat | HW/SW co-design of a visual SLAM application[END_REF]. SDF graphs abstract data transfer between components, called actors, being the graph vertices. The SDF graph edges correspond to buffers, in which transmitted data are stored. SDF graphs of CPSs often have imposed periodic inputs and outputs. However our approach is more flexible as any component of the system can be periodic. This flexibility is helpful in the case where multiple processing parts rely on different sensors.

Modeling systems is the first step of the design process. The systems then have to be verified and scheduled. Unfortunately the offline non-preemptive scheduling time complexity is exponential in the number of tasks to get the optimal solution because it is in general NP-complete [START_REF] Kwok | Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[END_REF]. This complexity limits the design of CPSs since optimal schedulers do not scale. In contrast, our approach gives results that are not optimal but that can be used to quickly build and assess prototypes of large applications. In other words, our approach is useful for the design space exploration of scheduling solutions. Optimal schedulers and timing property checkers may still have to be used. However, if they are used, it would only be after the prototyping step, on a small set of prototypes.

We focus on offline non-preemptive scheduling because of two main reasons. First, modern systems embed multicore processors where preemption, useful to perform multi-tasking on a unicore processor, is not required anymore, especially when executing a single application. The absence of preemption prevents the overhead caused by context switching [START_REF] Li | Quantifying the cost of context switch[END_REF] and simplifies the timing analysis. Second, as SDF graphs model only systems where all tasks and their precedences are known in advance, there is no necessity to have a reactive online scheduler. In our case a static schedule on each core is used for a global self-timed execution of the system.

In this paper, we consider applications modeled with an SDF graph, where some actors have periodic release times with implicit deadline. Our model is a restriction of the Polygraph model [START_REF] Dubrulle | A Data Flow Model with Frequency Arithmetic[END_REF] to SDF graphs, but extended with deadlines. We say that such graph has partially periodic constraints. Given a number of identical cores to execute the application and the Worst Case Execution Time (WCET) of each actor, the addressed problems are:

(1) first, to quickly check the schedulability, without computing a schedule; (2) second, to compute an offline non-preemptive schedule satisfying the periodicity and precedence constraints.

In the context of this paper, a schedule lists the start times of all tasks and the cores on which they are allocated. The notations used in this paper and details about SDF graphs are introduced in Section 2. Then necessary conditions for the nonpreemptive scheduling of SDF graphs with some periodic actors are expressed in Section 3. Section 4 discusses the algorithm checking if SDF graphs respect the necessary conditions. A greedy algorithm to schedule graphs with some periodic actors is presented in Section 5. Finally, a discussion on this work, including an evaluation of the scheduling algorithm, is located in Section 6. The related work is located in Section 7 and is followed by a conclusion.

BACKGROUND

This work is related to real-time systems and dataflow graphs, which are discussed in the next two subsections.

Real-time systems

Real-time systems are composed of multiple computational tasks to execute before their deadlines. In this paper, each task 𝜏 has either no real-time constraint or a periodic hard deadline. 𝑇 𝜏 denotes the period of a periodic task 𝜏. Tasks without periodic deadlines are called aperiodic. For periodically released tasks, their deadline 𝑑 𝜏 (relative to their release time) is implicit, which means equal to their period. The WCET of each task 𝜏 is denoted 𝐶 𝜏 .

During the execution of a real-time system, the tasks must be ordered and mapped to the cores in such a way that all tasks meet their deadlines (if any), which is not always possible. In this paper, a schedule refers to the order and to the static mapping of the tasks. When there is no schedule respecting the deadlines, the system is said to be not schedulable. In this work only offline data-driven non-preemptive schedulers are considered; the system repeats indefinitely a precomputed schedule. We consider that the system has 𝑚 identical cores.

Sychronous Dataflow graphs

SDF graphs [START_REF] Lee | Synchronous data flow[END_REF] model systems where the computational parts, called actors, correspond to the vertices, and where the means of communication, called buffers, correspond to the edges. 𝐺 denotes the SDF graph being analyzed. 𝐺 = (𝑉 , 𝐸) is a directed multi-graph with 𝑉 the set of actors, and 𝐸 the set of buffers. A buffer 𝑒 ∈ 𝐸 links its source actor src(𝑒) ∈ 𝑉 to its destination dst(𝑒) ∈ 𝑉 . Only weakly connected SDF graphs are considered in this paper 1 .

Actors exchange data through their incoming and outgoing buffers. A token is the unit of data used in the graph, e.g. one byte. A token production rate prod(𝑒) ∈ N * is defined on the source side of a buffer 𝑒, and a consumption rate cons(𝑒) ∈ N * is defined on the destination side. The tokens produced by one execution of src(𝑒) are available to be consumed only after the end of the execution of src(𝑒). The number of tokens initially present on a buffer 𝑒 is denoted 𝑑 0 (𝑒); these tokens are called delays.

As the rates may not be equal on both sides of a buffer, there can be multiple executions of an actor 𝛼 ∈ 𝑉 in order to avoid underflow or overflow on the buffer. The graph is consistent if it ensures that buffers have bounded sizes. Then, it is possible to compute a unique repetition vector ì 𝑟 giving the minimal number of executions of each actor needed to put the graph back to its initial state with the same number of tokens in each buffer. This defines a graph iteration in which the actor executions are called firings, or equivalently jobs in the literature. Consistency implies Equation (1):

∀𝑒 ∈ 𝐸, ì 𝑟 [dst(𝑒)] × cons(𝑒) = ì 𝑟 [src(𝑒)] × prod(𝑒) (1)
Two examples of a schedule for an SDF graph are given in Figure 1, where the repetition vector is [START_REF] Berry | The Esterel synchronous programming language: design, semantics, implementation[END_REF][START_REF] Bhattacharyya | Optimization of signal processing software for control system implementation[END_REF] 𝑇 (indexed by actor names in the lexicographic order).

In this paper 𝛼 𝑗 is the 𝑗-th firing of 𝛼 in one graph iteration. The WCET of an actor 𝛼, denoted 𝐶 𝛼 , is the same for each firing of 𝛼. Actors have uppercase names for examples, and lowercase names for formula variables. P denotes the set of periodic actors in 𝐺, and N denotes the set of aperiodic actors. The periods of the actors in P are defined by the user; but the graph consistency restricts their possible values. Indeed all periods are linearly related, as expressed in Section 3.1. According to the Polygraph model [START_REF] Dubrulle | A Data Flow Model with Frequency Arithmetic[END_REF], P corresponds to actors having a frequency. Delays on buffers are allowed, with some restrictions for cycles in 𝐺. Indeed SDF graphs deadlock if there is no delays in cycles, and 𝐺 is live if no deadlock occurs. We assume in the analysis that 𝐺 is live, thanks to delays set by the user on a specific edge of each cycle. Then, such specific edges will not be considered during the analysis and thus, only SDF graphs being Directed Acyclic Graph (DAG) are considered in this work. The case of cycles that are self-loops on an actor is also considered. Self-loops disable auto-concurrency and, as cycles, require delays in order to be consistent. Auto-concurrency implies that multiple firings of an aperiodic actor can be executed at the same time on different cores. For a self-loop 𝑙 ∈ L ⊆ 𝐸, we assume cons(𝑙) = prod(𝑙) = 𝑑 0 (𝑙).

PARTIALLY PERIODIC CONSTRAINTS

Non-preemptive scheduling is often not the best strategy when considering only periodic actors since it may lead to use the cores below their full capacity. For example, consider that two periodic actors 𝐴 and 𝐵 are scheduled as in Figure 1c. Actors 𝐴 and 𝐵 are periodic, but the only functional requirement on 𝐵 is that there are 3 executions of 𝐴 for 5 of 𝐵, according to the repetition vector of the SDF graph in Figure 1a. In Figure 1c, the periods are 𝑇 𝐴 = 5 and 𝑇 𝐵 = 3. When ignoring the precedences, the system is schedulable on one core with the WCET respectively 𝐶 𝐴 = 3 and 𝐶 𝐵 = 1, and the core even idles during 1 time unit. If the execution time of 𝐴 is now 𝐶 𝐴 = 3.1 (instead of 3), the core is still not used to its full capacity but the system is not schedulable anymore since 𝐵 3 would miss its deadline in any case. However, if 𝐵 is not required to be periodic, the system is schedulable on 1 core with 𝐶 𝐴 = 3.1.

Thus in this case partially periodic constraints help to fully use the capacities of the cores in the context of non-preemptive scheduling. In this section, we focus on necessary conditions for schedulability of SDF with partially periodic constraints. The generic processor utilization necessary condition is recalled in Section 3.1 while a more precise one is established in Section 3.2.

Plain schedulability condition

A widely used necessary condition for schedulability of periodic tasks derives from the processor utilization factor [START_REF] Liu | Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment[END_REF] metric 𝑈 = 𝐶 𝜏 𝑇 𝜏 , without unit. 𝑈 ≤ 𝑚 is a necessary but not sufficient condition, for all preemptive and non-preemptive schedulers of tasks with and without precedence constraints: if 𝑈 > 𝑚 the system is not schedulable [START_REF] Horn | Some simple scheduling algorithms[END_REF].

This paper focuses on weakly connected SDF graphs, thus all actors are connected and specifying the period of one actor 𝜋 is equivalent to specifying a period for the whole graph. Indeed the graph period 𝑇 𝐺 will be ì 𝑟 [𝜋] ×𝑇 𝜋 time unit. In Figure 1c, the graph period is 15, according to the periods 𝑇 𝐴 = 5 and 𝑇 𝐵 = 3, and to the repetition vector [START_REF] Berry | The Esterel synchronous programming language: design, semantics, implementation[END_REF][START_REF] Bhattacharyya | Optimization of signal processing software for control system implementation[END_REF] 𝑇 . Formally, in one graph iteration, the start time of the 𝑘-th firing of a periodic actor 𝜋 ∈ P with an implicit deadline must occur in the following time interval:

𝑘𝑇 𝜋 ; (𝑘 + 1)𝑇 𝜋 -𝐶 𝜋 , with 𝑘 ∈ 0; ì 𝑟 [𝜋] (2)
Consequently, in average ì 𝑟 [𝛼] firings of an aperiodic actor 𝛼 are executed during each graph period 𝑇 𝐺 , since the repetition vector imposes ì 𝑟 [𝛼] firings of 𝛼 for ì 𝑟 [𝜋] firings of 𝜋. As each periodic actor 𝜋 defines a graph period 𝑇 𝐺 = ì 𝑟 [𝜋] × 𝑇 𝜋 deriving from the unique repetition vector, this implies that all the obtained graph periods must be equal: ∃𝑇 𝐺 , ∀𝜋 ∈ P, 𝑇 𝐺 = ì 𝑟 [𝜋]×𝑇 𝜋 . Then, the processor utilization factor metric may be reformulated in the context of partially periodic constraints, considering the average amount of aperiodic firings per graph period 𝑇 𝐺 . Equation (3) is a necessary but not sufficient schedulability condition for partially periodic SDF graphs.

𝑚 ≥ 𝑈 = 𝛼 ∈N ì 𝑟 [𝛼] × 𝐶 𝛼 𝑇 𝐺 + 𝜋 ∈ P 𝐶 𝜋 𝑇 𝜋 (3)

With no scheduler iteration overlapping

Results of this subsection assume the following assumption on the scheduler. Under Assumption 1, indeed another necessary condition can be derived from the path lengths in the SDF graph with partially periodic constraints. Assumption 1 (A1). For every actor 𝛼, as many firings as specified in the repetition vector ì 𝑟 [𝛼] must have been completely executed before the next scheduler iteration begins.

A scheduler iteration is the static scheduling of the application that is indefinitely repeated until the application is stopped. This assumption is made to ease the scheduling, the code generation, and the memory allocation. Under Assumption 1, if there is a graph period, all firings of one scheduler iteration must be done during a time interval equal to this graph period. Assumption 1 is present in the PREESM SDF graph scheduler [START_REF] Pelcat | Preesm: A dataflow-based rapid prototyping framework for simplifying multicore DSP programming[END_REF] where scheduler iterations cannot overlap in time and are separated by a synchronization barrier between all cores. One graph period separates two successive barriers, so it ensures that for each actor 𝛼, there are ì 𝑟 [𝛼] executions of 𝛼 between two barriers. Note that Assumption 1 is similar to K-periodic scheduling [START_REF] Bodin | K-Periodic schedules for evaluating the maximum throughput of a Synchronous Dataflow graph[END_REF] with 𝐾 being the repetition vector ì 𝑟 in our case. While K-periodic scheduling imposes a periodic schedule of 𝐾[𝛼] firings independently for each actor 𝛼, Assumption 1 enforces these periodic schedules to be synchronized with barriers.

Assumption 1 still accepts schedules with delays; but then, all firings of one graph iteration do not occur in the same scheduler iteration: this is pipelining. 2) is also respected inside one scheduler iteration.

Scheduling a partially periodic SDF graph without taking care of data dependencies may lead to buffer underflows and overflows as illustrated in Figure 3 where the SDF graph is however consistent. In this example the period of the actor Π is 4 time units (and 𝐶 Π = 1), and the graph period is 12. The Gantt diagram in Figure 3b respects the periodic constraint but not the data dependencies. An underflow occurs since 𝐵 and ∆ are executed before having received the data produced by the last firing of Π. Note that the delays are predefined by the user, and are not computed nor checked by Algorithm 1, presented at the end of this section. However, such data dependency errors are checked easily on static schedules.

Figure 3 illustrates an intuitive necessary condition to check the schedulability: all actors depending on the tokens produced by the last execution of Π must be executed in the slack time of Π. This necessary condition derives from Assumption 1. The slack time of Π is defined by 𝑇 Π -𝐶 Π . A symmetrical necessary condition can be computed for the first execution of any periodic actor, this time with all its incoming data dependencies, which are all actors on a directed path leading to the periodic actor. In order to formalize these necessary conditions, some notations and functions are introduced in the next paragraphs. Core 1

𝐴 𝐵 ∆ 1 ∆ 2 Core 2 Π 1 Π 2 Π 3 1 2 3 1 2 3
graph period (b) Schedule example of graph 3a, generating underflow. All presented equations can be applied on the transpose of 𝐺, considering the first firing of 𝜋 instead of the last. The transpose 𝐺 𝑇 of a graph 𝐺 is its mirror, where all edges are directed in the opposite direction, also exchanging token production and consumption rates. For brevity, equations on 𝐺 𝑇 are not shown.

The main metric to compute is the numbers of actor firings, enabled by a single firing of a periodic actor 𝜋. These numbers of firings allow us to compute lower bounds of the processor utilization factor. The analysis is simplified by restricting it to the last firing of 𝜋 and all induced firings of its successors in D ↑ 𝜋 . Note that the number of remaining dependent firings can be computed for two adjacent actors connected by a single buffer 𝑒: 𝑘 firings of src(𝑒) enable max{0,

𝐺 ↑ 𝜋 is denoted 𝐼𝐸 ↑ 𝜋 (𝛼); this set excludes self-loops 𝑙 ∈ L. nblf ↑ 𝜋 (𝛼) = max 𝑒 ∈𝐼 𝐸 ↑ 𝜋 (𝛼) 0, nblf ↑ 𝜋 (src(𝑒)) × prod(𝑒) -𝑑 0 (𝑒) cons(𝑒) (4)
The recursion stops at the root actor 𝜋, having no incoming edges (there is only one root, by construction of 𝐺 ↑ 𝜋 ), where nblf ↑ 𝜋 holds the value 1 if 𝜋 is periodic and 0 otherwise. Hence if the root actor is not periodic, nblf ↑ 𝜋 takes the value 0 on all vertices and it does not help to find any necessary condition. For brevity, the proof of Equation ( 4) is given for one direct predecessor only of dst(𝑒).

Proof. To prove Equation ( 4

ì 𝑟 [dst(𝑒)] -nblf ↑ 𝜋 (dst(𝑒)) = (ì 𝑟 [src(𝑒)] -nblf ↑ 𝜋 (src(𝑒))) × prod(𝑒) + 𝑑 0 (𝑒) cons(𝑒) Thus nblf ↑ 𝜋 (dst(𝑒)) is equal to: ì 𝑟 [dst(𝑒)] - ì 𝑟 [src(𝑒)] × prod(𝑒) -nblf ↑ 𝜋 (src(𝑒)) × prod(𝑒) + 𝑑 0 (𝑒) cons(𝑒) Knowing that ∀𝑥 ∈ R, -⌊𝑥⌋ = ⌈-𝑥⌉, it becomes: nblf ↑ 𝜋 (dst(𝑒)) = ì 𝑟 [dst(𝑒)] × cons(𝑒) cons(𝑒) + -ì 𝑟 [src(𝑒)] × prod(𝑒) + nblf ↑ 𝜋 (src(𝑒)) × prod(𝑒) -𝑑 0 (𝑒) cons(𝑒)
From the consistency of 𝐺, see Equation ( 1), ì 𝑟 [dst(𝑒)] × cons(𝑒)ì 𝑟 [src(𝑒)] × prod(𝑒) = 0, so the last formula can be simplified to Equation (4) (without the maximum, needed when they are multiple direct predecessors). □

The following formula is then a necessary condition for schedulability under Assumption 1. Equation ( 5) corresponds to the processor utilization factor of all firings depending on the last firing of a periodic actor. This processor utilization factor is computed over the slack time of the periodic actor, hence the division by 𝑇 𝜋 -𝐶 𝜋 .

∀𝜋 ∈ P,

𝛼 ∈ D ↑ 𝜋 nblf ↑ 𝜋 (𝛼) × 𝐶 𝛼 𝑇 𝜋 -𝐶 𝜋 ≤ 𝑚 (5)
Note that the maximal length of any graph path starting at a periodic actor 𝜋 also provides a simple necessary condition of the schedulability: this length must be less than the slack time of 𝜋. Also, actors with self-loops have a strong impact on the maximal length because they do not have auto-concurrency. This necessary condition for actors with self-loops is formalized in Equation [START_REF] Bilsen | Cycle-static Dataflow[END_REF].

∀𝛼 ∈ D ↑ 𝜋 ∩ L, nblf ↑ 𝜋 (𝛼) × 𝐶 𝛼 ≤ 𝑇 𝜋 -𝐶 𝜋 (6)
Equation ( 6) can be extended to all paths between a periodic root 𝜋 and leaves of the DAG 𝐺 ↑ 𝜋 . On each of these paths, each actor will be executed at least once except if there are enough delays before the actor; if no delays, the path length is the actor WCET sum. Again, all these path lengths must be lower than the slack time 𝑇 𝜋 -𝐶 𝜋 .

Algorithm 1 checks the schedulability of a periodic actor 𝜋 in 𝐺 ↑ 𝜋 thanks to the aforementioned necessary conditions: the one derived from the processor utilization factor, and the one derived from the critical path minimal execution time. The efficiency of Algorithm 1 is discussed in the next section. ⊲ 𝜋 is periodic.

DISCUSSION ON ALGORITHM 1

Algorithm 1 has a linear complexity in the number of edges in 𝐺 ↑ 𝜋 . Thus if all actors in 𝐺 are periodic, it may not be efficient to execute Algorithm 1 on each one: in specific cases the overall complexity can be more than quadratic in the number of vertices in 𝐺, as for the star graphs with directed paths going to/from a central vertex. In order to perform the algorithm on a subset of the periodic actors, a heuristic is presented in Section 4.1. Algorithm 1 faces another problem: as it relies only on necessary conditions, there are cases where the algorithm fails to detect a non-schedulable system. This point is discussed in Section 4.2.

Heuristic to run Algorithm 1 efficiently

In this subsection a heuristic is given to execute Algorithm 1 on a small set of periodic actors: the one having small slack time

𝐴 1 1 Γ 1 1 𝐸 1 1 𝐵 1 ∆ 1
Figure 4: Sample SDF graph and a low topological rank in 𝐺. Indeed a small period 𝑇 𝜋 will reduce the denominator in Equation ( 5), while a low topological rank may increase the numerator because it means that more actors are located after 𝜋. Thus this heuristic selects the actors being more discriminative regarding to the schedulability tests of Algorithm 1.

As we consider synchronous dataflow DAG, there is always a topological sort existing. One topological sort is used to select actors: it corresponds to an As Soon As Possible (ASAP) schedule of 𝐺 𝑇 , not constrained by the number of cores. The ASAP topological sort on 𝐺 𝑇 is denoted 𝑜 𝑇 and is used to select the periodic actors on which Algorithm 1 is called. Notice that the actor WCETs are not taken into account in this topological sort, only the structure of the graph is used. Such topological sort can be computed with a BFS, having a linear complexity in the number of edges in 𝐺.

Considering the SDF graph in Figure 4, there are three topological ranks: one per actor in the longest graph path which is 𝐴 → Γ → 𝐸. Thus 𝑜 𝑇 (𝐴) = 2, 𝑜 𝑇 (Γ) = 1, 𝑜 𝑇 (𝐸) = 0. The other actors have the lowest topological ranks at which they can be executed, that is 𝑜 𝑇 (𝐵) = 0, 𝑜 𝑇 (∆) = 1. Indeed 𝐵 has no incoming edges in 𝐺 𝑇 so its rank is 0. The ASAP sort on the transpose graph of Figure 4 can be equivalently represented as follows:

𝑜 𝑇 ≡ {𝐸, 𝐵} ≺ {Γ, ∆} ≺ {𝐴}.
Formally, the heuristic selects the periodic actors having the lowest 𝑇 𝜋 -𝐶 𝜋 𝑜(𝜋 ) . The number of selected actors with this heuristic is arbitrarily chosen by the user. Note that vertices with ASAP topological rank equal to 0 are not of interest since it means that they have no successors; Algorithm 1 is not run on such vertices.

A false positive to Algorithm 1

Algorithm 1 performs two schedulability tests. One is using the processor utilization factor 𝑈 , Equation (5) lines 21-24, and thus does not consider the precedences between actors. Considering multiple cores, it may lead to keep invalid schedules where 𝑈 < 𝑚, but where a path from a periodic actor is longer than the slack time of this actor. This situation is precisely checked by the other schedulability test using path lengths, lines 18-20 in Algorithm 1 2 . Between these two situations, the algorithm may miss that 𝑈 is too large on a small portion of the slack time: for example, if nblf ↑ of the last actor is greater than 𝑚. Thus, Algorithm 1 fails to find that the graph represented in Figure 5 is not schedulable with 2 cores. Yet the critical path starting from Π in Figure 5a is equal to the slack time of Π and 𝑈 = 15 9 is less than the number of cores 𝑚 = 2. Algorithm 1 may compute other false positive answers: only 𝐺 ↑ 𝜋 is considered and thus, periodic actors having a period smaller than 𝑇 𝜋 in 𝐺 but not being in 𝐺 ↑ 𝜋 are not taken into account. To avoid that, Algorithm 1 can be refactored with a subfunction performing 2 The equation on line 17 is actually a simplification when there is auto-concurrency. Inside cycles (including self-loops), the auto-concurrency is limited by the repetition vector of the cycle, which divides the original repetition vector. computations of lines 2-22. The subfunction is called on 𝜋 and on all the periodic actors having a period smaller than 𝑇 𝜋 , and not being connected by any path in 𝐺. For brevity, the full algorithm is not presented here. However, even if false positives appear, the system designer will logically continue its work by calling a scheduler. The scheduler will give a final answer: schedulable or not. In the next section, an offline scheduler is presented under Assumption 1. This scheduler is a heuristic and thus does not attempt to find an optimal scheduling, it rather focuses on giving quickly an answer to the designer.

SCHEDULING OF SDF GRAPHS WITH PARTIALLY PERIODIC CONSTRAINTS

The problem studied in this section is the quick scheduling of 𝐺 * with partially periodic constraints. 𝐺 * is the Single-Rate Data Flow (SRDF) graph corresponding to the SDF graph 𝐺. In other words, 𝐺 * is the unrolled version of 𝐺, where data dependencies are expressed between firings instead of actors. Since all dependencies are explicitly expressed in 𝐺 * , it enables computing a static schedule. Each SDF actor 𝛼 in 𝐺 has ì 𝑟 [𝛼] corresponding vertices in the SRDF graph 𝐺 * , and on each edge 𝑒 of 𝐺 * the rates of both sides are equal, i.e. prod(𝑒) = cons(𝑒). In this section, tasks refer to vertices in 𝐺 * . As in 𝐺, delays break cycles so 𝐺 * is a DAG.

Scheduling of DAG of tasks has been widely studied [START_REF] Kwok | Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[END_REF] however the periodic case is specific since the start times of periodic actors are bounded in an interval of the form of Equation (2).

For example, the FAST algorithm [START_REF] Kwok | FAST: a low-complexity algorithm for efficient scheduling of DAGs on parallel processors[END_REF], based on a list scheduling heuristic and a neighborhood search, is not appropriate for periodic schedules. The main difference between the problem studied here and the one solved by standard list scheduling algorithms is that, because of partially periodic constraints, we have a bound on the schedule length. This bound is the graph period.

The main difficulty to design a greedy list-scheduling scheduling algorithm is to order the vertices before trying to schedule them. The FAST algorithm cannot be used as is but some of its techniques are reused in the presented Algorithm 2. As in FAST, Algorithm 2 relies on ASAP and As Late As Possible (ALAP) orderings.

The minimum start time ns of each task in 𝐺 * as well as the maximum start time xs are computed first. This is done in two successive rounds: 1) for all periodic actors, with Equation (2), 2) for all actors, with ASAP and ALAP. During round 2), ALAP schedule has a global deadline equal to the graph period. If any task 𝜏 has ns(𝜏) > xs(𝜏), the algorithm stops: the system is not schedulable.

Algorithm 2 is executed once all ns and xs have been computed, starting with the schedule procedure. The tasks are sorted according to their average start time xs + ns 2 . This sorting criterion is a heuristic to balance the task executions over time. The list of tasks to allocate, 𝑙 line 22, contains only vertices having all their dependencies satisfied, initially the one having no incoming edges. If several tasks in 𝑙 have the same average start time, ns is used to break the tie, by increasing order. The algorithm performs a first fit approach: it selects the next task in 𝑙 and schedules it on the least loaded core. The allocateAndRemoveIfBefore procedure, lines 10 -17, also updates 𝑙 with tasks having a direct dependency on the currently allocated task. This procedure stops the scheduling in two cases: 1) if a task is scheduled after its maximum start time xs, lines 12 -13, 2) if a the total idle time is more than the maximum possible, line 7, according to the formula line 21.

Algorithm 2 is greedy since if a task 𝜏 implies an idle time, the algorithm tries to schedule before 𝜏 the tasks 𝜏 𝑏 having ns < predFinishTime(𝜏), without delaying 𝜏. This is the purpose of lines 26 -30 in Algorithm 2. The test line 14 ensures that 𝜏 𝑏 can be executed without delaying 𝜏, and if not it prevents to allocate it. Although Algorithm 2 is greedy, it is not subject to the Dhall's effect [START_REF] Sudarshan | On a Real-Time Scheduling Problem[END_REF]. Dahll's effect occurs on multicore processors when two tasks are ready at the same time and have the same deadline, but the allocation order prevents to allocate both tasks because the smallest task may be allocated first on the least loaded core, not leaving enough space for the other task. In Algorithm 2, as tasks are sorted by average start time from ASAP and ALAP scheduling, the biggest task will have a shorter average start time and thus will appear sooner in the list of tasks ready to be scheduled.

The complexity of Algorithm 2 is upper bounded by the number of edges in 𝐺 * and by the linearithmic cost of the sorting operation on the vertices: O(#𝐸 * + #𝑉 * (𝑚 + log(#𝑉 * ))). The number of cores 𝑚 appears as a factor of #𝑉 * since the list of cores 𝑐 must remain sorted to select the least loaded core for every vertex in the ready queue 𝑙. The cost of transforming 𝐺 in 𝐺 * is not included in this complexity, it is upper bounded by #𝐸 * . It is a standard transformation, already implemented in the PREESM tool for example.

EVALUATION

This section discusses how Algorithms 1 and 2 can be used for the design process of CPSs, and presents an evaluation.

Partially periodic CPSs applications

Only a few CPSs use-cases are presented in the literature as partially periodic SDF graphs. Indeed it is often assumed that every component is periodic in order to ease the analysis and the code generation. Due to the lack of available partially periodic implementations, and to the simplicity of the existing ones, the necessary conditions for schedulability have not been practically evaluated. However, two small examples are given hereafter. A pacemaker [START_REF] Pellizzoni | Handling Mixed-criticality in SoC-based Real-time Embedded Systems[END_REF] has been studied and modeled in the Architecture Analysis Design Language (AADL) 3 and it is a partially periodic system. A critical subpart of this pacemaker is described using the Cyclo-Static Data Flow (CSDF) model [START_REF] Bilsen | Cycle-static Dataflow[END_REF], an extension of SDF. In this subpart, two sensors (Motion and EKG) periodically send data to a processing component, each with its own period. A second example is in the telecommunication domain: the LTE standard has been studied and partially modeled with SDF graphs [START_REF] Pelcat | Rapid Prototyping and Dataflow-Based Code Generation for the 3GPP LTE eNodeB Physical Layer mapped onto Multi-Core DSPs[END_REF]. In the LTE standard, the signals retrieved by the antenna are down-sampled and periodically sent to the decoder. To the best of our knowledge, no open source benchmark exists that is explicitly partially periodic. Yet, the StreamIt [START_REF] Thies | StreamIt: A Language for Streaming Applications[END_REF] benchmark contains dozens of signal processing applications in the SDF model. Periods are not specified in StreamIt but signal processing applications usually have one periodic input actor and another periodic output.

Finally it is possible to generate random SDF graphs with SDF 3 [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF] and Turbine [START_REF] Bodin | Fast and Efficient Dataflow Graph Generation[END_REF], but they do not generate partially periodic constraints. Thus, our experiments, detailed in Sections 6.3 and 6.4, have been performed on ten random DAGs generated by Turbine, and on one existing use-case of the SDF 3 data set. For the first experiment, partially periodic constraints are added to these generated graphs as a post-processing step that follows the graph generation.

Schedulability check and scheduling

The practical usage of the presented algorithms is summarized in Figure 6. In terms of the number of cores 𝑚, the necessary conditions (Algorithm 1) give a schedulability lower bound (left part) while the scheduler (Algorithm 2) gives an upper bound (right part). For example, the lower bound is 4 cores while the upper bound is 7 cores in Figure 6.

The algorithms have to be run iteratively with different values of 𝑚 to tighten the bounds. A starting point can be derived using the length of the critical path as done in the experiments on the scheduler, presented in Section 6.3.

Regarding the scheduler, notice that it can actually be run for any unconnected DAG and thus is more generic than for SDF graphs with partially periodic constraints. The next subsections report two experiments done on the algorithms presented in this paper.

Gap between necessary conditions and scheduler

This experiment measures the gap between the proposed necessary conditions, the proposed scheduler, and the optimal solution. The gap is measured in number of cores required to synthesize a schedule while respecting all periodic constraints.

6.

3.1 Dataset. The dataset contains ten random SDF DAG generated with the Turbine tool [START_REF] Bodin | Fast and Efficient Dataflow Graph Generation[END_REF]. ⊲ Check and set remaining idle time.

8 function isThereACoreIdlingBefore(𝑐, deadline)

⊲ Returns true if one or multiple cores idle before the deadline.

9 function possibleAllocationsBefore(𝑙, deadline)

⊲ Returns tasks in 𝑙 which can start before the given deadline, ensuring that the selected tasks total execution time is not higher than the current idle time to the given deadline.

10 procedure allocateAndRemoveIfBefore(𝑙, 𝜏, 𝑐, deadline, maxIdleTime, currentIdleTime) 1: Details of the random directed acyclic SDF graphs generated by Turbine, and execution time of the algorithms. RandomDAG1-5 contain one periodic actor 𝜋. RandomDAG6-10 contain two periodic actors.

One periodic actor 𝜋 is set in the middle of the longest path of each SDF graph; largest number of firings breaks the tie. A second periodic actor is set on RandomDAG6-10. Their periods 𝑇 𝜋 are set manually, being the smallest integer such that a solution exists. Formally,𝑇 𝜋 is the smallest integer which ensures: ∀𝜏 ∈ 𝐺 * , ns(𝜏) < xs(𝜏).

Standard Integer Linear Programming (ILP) formulation with

Choco. A scheduling model using ILP formulation has been developed in order to compare the performance with Algorithm 2. Although the formulation is purely ILP, the generic Choco 4 CP solver has been used since there is no objective function in the formulation: the goal is only to test if there exists a valid schedule for a given number of cores 𝑚. Choco stops on the first valid schedule encountered, and otherwise enumerates all possible schedules in order to prove that there is no solution.

The model size is bounded by the size of a transient Boolean matrix storing mapping overlap of each couple of tasks: Θ(𝑚 × #𝑉 × #𝑉 ). A transitive closure of the DAG 𝐺 * is computed before the model construction in order to reduce the size of this Boolean matrix. The transitive closure prevents to add useless free variables and redundant constraints to the matrix stating mapping overlap: overlap between two tasks is checked only if there is no transitive precedence between the two tasks. The number of constraints is reduced by up to 16% thanks to the transitive closure. Last but not least, symmetries of the homogeneous cores are broken by enforcing some properties on the mapping matrix, see [START_REF] Tendulkar | Symmetry Breaking for Multi-criteria Mapping and Scheduling on Multicores[END_REF].

Implementation of algorithms in PREESM.

Algorithms 1 and 2 and the Choco model have all been implemented in the PREESM open-source 5 tool dedicated to the design of embedded systems from applications modeled as SDF graphs. PREESM automatically generates the SRDF graph 𝐺 * from a given SDF graph; the generation time of 𝐺 * is not included in the experiments. Experiments have been run on an Intel i7-7820HQ processor.

Evaluation results.

The evaluation has been performed as following. For each scheduling algorithm, the result is the smallest number of cores ensuring a valid schedule. For the necessary conditions, the result is the smallest number of cores ensuring that no valid schedule exists for all lower number of cores. All algorithms are run iteratively with an increasing number of cores. Diagram in Figure 7 presents the results for the five small random graphs. The processor utilization factor Utot of the graph is given as reference on the left column. The execution time of the algorithms are given in the right part of Table 1 (in millisecond ms, and hour h). While the proposed algorithms always run in less than a second, Choco takes hours for the small graphs.

Choco is optimal but cannot solve problems with too many firings or cores. It actually reaches timeout (T/O) of 12 hours for RandomDAG1 and RandomDAG4 with 9 cores, and it also takes multiple hours to prove that the same graphs have no solutions for 8 cores. The timeout of Choco is specified by an error interval, materialized by a small black line in Figure 7. The gap between the optimal solution and the proposed scheduler is at most two cores, for RandomDAG4, and may be zero as for RandomDAG5. 4 http://www.choco-solver.org/ 5 https://preesm.github.io/ The results of the five large graphs are pictured in Figure 8, without comparison with Choco because of the size of the problem (it would timeout in any case). On all ten graphs, the necessary conditions appear to be weakly discriminating: in most of the case, it states that the system is possibly schedulable as soon as 𝑚 > 𝑈 tot . The necessary conditions are discriminating only for RandomDAG1 and RandomDAG6. Note that RandomDAG1 and RandomDAG6 are also the graphs requiring a longer run time of the proposed scheduler. Yet two reasons may increase the complexity of the scheduler: more tasks ready at the same time (which increases the size of the sorted list 𝑙), or more idle time (which triggers the execution of lines 26-30 in Algorithm 2). Further investigation are needed to characterize this phenomenon.

Gap between the proposed scheduler and preemptive Earliest Deadline First (EDF)

This experiment measures the graph period gap between the proposed non-preemptive offline scheduler Algorithm 2 and a standard preemptive real-time scheduler: EDF. The ADFG tool [START_REF] Honorat | ADFG: a scheduling synthesis tool for dataflow graphs in real-time systems[END_REF] is used as a reference, using Global EDF scheduling [START_REF] Bertogna | Tests for Global EDF Schedulability Analysis[END_REF] (with an algorithm adapted from the forced-forward demand bound function). ADFG considers that all actors are periodic and computes their optimal smallest period for a given number of cores. ADFG also computes delays on the buffers; these delays are kept in the input of Algorithm 2. Then Algorithm 2 is initially run with a graph period equal to the sum of all WCET, and the actual latency 6 found by Algorithm 2 is kept as a result. Indeed the latency found is the smallest graph period achievable by the proposed scheduler and it may be smaller than the input graph period since Algorithm 2 is greedy and uses idle time as soon as possible.

The results are depicted in Figure 9, for the Beamformer application from the StreamIt benchmark. Beamformer graph contains 57 actors and 70 edges, each actor is fired only once. For each number of cores, Algorithm 2 finds a graph period close to the optimal, and even optimal from 28 cores. The optimal graph period is equal to the greatest WCET (5076) since numerous delays are added by ADFG and break the data dependencies.

RELATED WORK

To our knowledge, only the MAPS [START_REF] Castrillon | MAPS: Mapping Concurrent Dataflow Applications to Heterogeneous MPSoCs[END_REF] tool accepts SDF graphs with partially periodic constraints as specified in this paper. However, MAPS does not exactly compute a schedule, but instead it checks if execution traces can be executed on the targeted architecture. As MAPS is not freely accessible, we did not compare to it. Deadlock [START_REF] Derler | Specification of precise timing in synchronous dataflow models[END_REF] and consistency [START_REF] Dubrulle | A Data Flow Model with Frequency Arithmetic[END_REF] analysis of SDF graphs with partially periodic constraints have also been studied. Other tools and papers are closely related to our scheduling problem and are listed in the three next paragraphs, according to there category. Schedulers of real-time tasks with precedence constraints. Realtime systems have been widely studied for online periodic scheduling, the most common schedulers being EDF and Fixed Priority (FP). Yet an offline part is still needed in most of the online schedulers: either to compute the deadlines as in the Chetto's algorithm [START_REF] Chetto | Dynamic Scheduling of Real-time Tasks Under Precedence Constraints[END_REF] to respect precedence constraints under EDF, or to compute the task priorities in the case of FP. Some online schedulers also take into account periodic and aperiodic tasks [START_REF] Lipari | Schedulability analysis of periodic and aperiodic tasks with resource constraints[END_REF]; they still may need an offline pre-schedule [START_REF] Fohler | Joint scheduling of distributed complex periodic and hard aperiodic tasks in statically scheduled systems[END_REF], and may rely on EDF [START_REF] Isovic | Efficient scheduling of sporadic, aperiodic, and periodic tasks with complex constraints[END_REF]. Regarding offline non-preemptive scheduling, there exists an ILP formulation [START_REF] Xiao | Schedulability Analysis of Nonpreemptive Real-Time Scheduling for Multicore Processors with Shared Caches[END_REF] for sporadic and periodic tasks under EDF and FP. A CP solution for periodic tasks only has also been formulated [START_REF] Puffitsch | Off-line mapping of multi-rate dependent task sets to many-core platforms[END_REF]. Both ILP and CP formulations have a high complexity and thus are not scalable.

Schedulers of SDF graphs with periodic constraints. The Darts tool [START_REF] Bamakhrama | Hard-real-time scheduling of datadependent tasks in embedded streaming applications[END_REF] is able to schedule SDF graphs under a throughput constraint, equivalent to a graph period constraint, for EDF and FP schedulers. ADFG [START_REF] Honorat | ADFG: a scheduling synthesis tool for dataflow graphs in real-time systems[END_REF] is similar to Darts, but it optimizes the throughput under a total buffer size constraint. SDF graphs can be modeled with synchronous languages such as Prelude [START_REF] Pagetti | Multi-task implementation of multi-periodic synchronous programs[END_REF], which generates code for EDF and FP schedulers. Still using synchronous language, activation clocks with precedences [START_REF] Cohen | N-synchronous Kahn Networks: A Relaxed Model of Synchrony for Real-time Systems[END_REF] can be composed and checked. Yet, in all the aforementioned tools of this paragraph, all SDF actors are periodic. Minimal actor periods can be be computed independently from the scheduling policy [START_REF] Ali | Generalized Extraction of Real-Time Parameters for Homogeneous Synchronous Dataflow Graphs[END_REF], but only for SRDF graphs. Note that a polynomial algorithm [START_REF] Singh | Uniprocessor scheduling of real-time synchronous dataflow tasks[END_REF] exists for the unicore processor case under EDF, with real-time tasks being specific SDF graphs. Other papers [START_REF] Bhattacharyya | Optimization of signal processing software for control system implementation[END_REF] specify throughput constraints on the only input or output actor of an SDF graph 𝐺, which is equivalent to specify a graph period 𝑇 𝐺 .

Schedulers of SDF graphs with latency constraints. A latency constraint on an SDF graph 𝐺 is equivalent to a throughput constraint or graph period if and only if the scheduler assumes Assumption 1 and there is no delay in 𝐺 (except to break cycles). Indeed if delays are present, as in Figure 2, the latency may be higher than the graph period. Latency constraints for SDF graphs have been heavily studied, especially symbolically. For example, the latency has been analyzed either without scheduling assumption to derive upper and lower bounds [START_REF] Khatib | Computing latency of a real-time system modeled by Synchronous Dataflow Graph[END_REF], or with self-time scheduling of SDF [START_REF] Ghamarian | Latency Minimization for Synchronous Data Flow Graphs[END_REF] and SRDF [START_REF] Moreira | Self-Timed Scheduling Analysis for Real-Time Applications[END_REF] graphs. Practically, the Ptolemy [START_REF] Eker | Taming heterogeneity -the Ptolemy approach[END_REF] tool supporting SDF graphs has been extended to perform timing verification, as latency, through system simulation [START_REF] Guo | Metronomy: A function-architecture co-simulation framework for timing verification of cyber-physical systems[END_REF]. Finally, there exists an offline scheduler accepting throughput and latency constraints on SDF graphs [START_REF] Lin | Communicationaware Heterogeneous Multiprocessor Mapping for Real-time Streaming Systems[END_REF]; it takes into account communications and computes the static schedule with ILP and heuristics. Thus all these tools tackle only a small subset of partially periodic constraints: the specific case of one graph period without any delay on the graph.

CONCLUSION AND FUTURE WORK

A few necessary conditions and an offline non-preemptive scheduling algorithm have been presented in order to analyze and synthesize the scheduling of partially periodic SDF graphs. These results hold under a weak assumption on the execution of the systems: the presence of barriers at each graph period. The proposed algorithms have, at most, a linearithmic complexity and can thus be used on large cyber-physical systems modeled as SDF graphs. Experiments show that the proposed non-preemptive scheduler is fast, scalable, and efficient. Next step is to extend the schedulability analysis to model heterogeneous hardware, that is becoming the new standard for embedded systems. Another direction for future work is to take into account inter-core communication time while assessing the real-time schedulability.

ADDENDUM

This addendum is not part of the original accepted paper: it has been added by A. Honorat after publication and has not been reviewed. This addendum gives additional examples extracted from the presentation slides made for the RTNS conference. Most importantly, it corrects a wrong usage of Equation ( 6) in Algorithm 1.

Also, we would like to mention another work related [START_REF] Louise | Graph Transformations and Derivation of Scheduling Constraints Applied to the Mapping of Real-Time Distributed Applications[END_REF] to the Polygraph model which schedules partially periodic SDF graphs, expressed as ILP taking into account communication time. The work [START_REF] Louise | Graph Transformations and Derivation of Scheduling Constraints Applied to the Mapping of Real-Time Distributed Applications[END_REF] solves a more complex scheduling problem than us (since they take into account communication time), but is not as scalable and fast as the scheduling Algorithm 2 that we propose in this paper (since they rely on ILP formulation).

Counter-example and correction of Algorithm 1

Unfortunately, we discovered a small error after publication. Section 3.2 states: "Equation ( 6) can be extended to all paths between a periodic root 𝜋 and leaves of the DAG 𝐺 ↑ 𝜋 . " The necessary condition in Equation ( 6) is correct but its extension to all paths as expressed in Algorithm 1 (lines [START_REF] Fohler | Joint scheduling of distributed complex periodic and hard aperiodic tasks in statically scheduled systems[END_REF][START_REF] Gee | Lidar guided stereo simultaneous localization and mapping (SLAM) for UAV outdoor 3-D scene reconstruction[END_REF] is wrong: firings dependent on the selfloop may be executed at the same time and the WCET cannot simply be summed. Figure 10 gives an example where actor 𝐴 having a self-loop is executed at the same time of its ongoing dependency 𝐵 (firings 𝐴 2 and 𝐵 1 , 𝐴 3 and 𝐵 2 ). Corrected Algorithm 1 is almost identical: it just needs to remove the test on line 16 (or to replace the test by an always true statement). The assignment on line 17 should be executed even if the test on line 16 fails. Experimental results remain valid since no cycles were present in the tested graphs.

Indeed the necessary condition expressed in Equation ( 6) can be extended to all paths between a periodic root 𝜋 and leaves of the DAG 𝐺 ↑ 𝜋 , but at the cost of an underestimation of the execution time. On each of these paths, each actor will be executed at least once except if there are enough delays before the actor; if no delays, the path length is greater or equal to the WCET sum of actors located on the path. Again, all these path lengths must be lower than the slack time 𝑇 𝜋 -𝐶 𝜋 . It is possible to underestimate the number of times that the WCET of an actor must be added to the path length, given the number of cores 𝑚. The generic underestimated necessary condition is given in Equation [START_REF] Bodin | Fast and Efficient Dataflow Graph Generation[END_REF]. For example, if nblf ↑ 𝜋 (𝛼) = 6 and 𝑚 = 3, then 𝐶 𝛼 is added 2 times. Note that the computation of the whole path length is similar to a Max-Plus algebra, as used for throughput analysis [START_REF] Ghamarian | Throughput Analysis of Synchronous Data Flow Graphs[END_REF]: "Max" operation is on line 12, and "Plus" operation is on line 18 of Algorithm 1.

∀𝛼 ∈ D ↑ 𝜋 , 𝐶 𝛼 × max 1, nblf ↑ 𝜋 (𝛼) 𝑚 ≤ 𝑇 𝜋 -𝐶 𝜋 ( 7
)
Figure 11 is an intuitive example to demonstrate why the floor function is used in Equation ( 7): firings of different actors may be scheduled at the same time, and this overlap is not easily predictable. The only certainty for the path length after Π is about the concurrent execution of several firings of only one actor at a time. nblf ↑ Π (𝐴) = nblf ↑ Π (𝐵) = 3 but there are only two cores in the system so only ⌊ 3 2 ⌋ = 1 execution time of each actor is added to the path length in this case.

Example and counter-example of Assumption 1

Assumption 1 states that there are as many firings as in ì 𝑟 per scheduler iteration, see Figure 12 for a counter-example and an example.

Example of schedulability improvement due to partially periodic constraints

Figure 13b gives a schedulable example with partially periodic constraints (on actor A only), whereas fully periodic is not schedulable with the same period (see Figure 1c for a fully periodic schedule).

𝐴 5 𝐵 3 (

 53 a) SDF graph example, of repetition vector[START_REF] Berry | The Esterel synchronous programming language: design, semantics, implementation[END_REF][START_REF] Bhattacharyya | Optimization of signal processing software for control system implementation[END_REF] 𝑇 .

Figure 1 :

 1 Figure 1: SDF graph scheduling examples.

𝐴 1 𝐵 1 (Core 1 3 Core 2

 11132 a) SDF graph having two periodic actors with a dependency and one delay. The repetition vector is[1, 1] 𝑇 . 𝐴 𝑖𝑡𝑒𝑟 1 𝐴 𝑖𝑡𝑒𝑟 2 𝐴 𝑖𝑡𝑒𝑟 𝐵 𝑖𝑡𝑒𝑟 0 𝐵 𝑖𝑡𝑒𝑟 1 𝐵 𝑖𝑡𝑒𝑟 2barrier barrier (b) Schedule example of 2a on two cores. The barriers happen at the same time as the graph period, they define a scheduler iteration. Note that three scheduler iterations are represented while only two graph iterations are completed (iterations 1 and 2).

Figure 2 :

 2 Figure 2: Scheduler iteration example, under Assumption 1.

Figure 2

 2 gives an example of such a pipelined schedule with delays: the firing of 𝐵 consuming the data produced by the last firing of 𝐴 happens one scheduler iteration after. Graph iterations are denoted 𝑖𝑡𝑒𝑟 in the Gantt diagram of Figure 2b. Equation (

  D ↑ 𝜋 denotes the set of actors in 𝐺 that are transitively data dependent on an actor 𝜋: if 𝛼 ∈ D ↑ 𝜋 , the last firing of 𝜋 enables at least one firing of 𝛼. It can be computed by a graph traversal from 𝐴

Figure 3 :

 3 Figure 3: Periodic actor Π generating an underflow.

  𝑘×prod(𝑒)-𝑑 0 (𝑒) cons(𝑒) } firings of dst(𝑒). The term 𝑘 × prod(𝑒) corresponds to the new tokens incoming on the buffer 𝑒. The ceiling operator is needed since the previous execution of the producer src(𝑒) may have left unused tokens on 𝑒. At the end of the graph iteration, 𝑒 contains exactly 𝑑 0 (𝑒) delays. The function computing the number of firings enabled by the last firing of a periodic actor 𝜋 is denoted nblf ↑ 𝜋 , defined in Equation (4). nblf ↑ 𝜋 is a recursive function, depending on the predecessor actors in the graphs 𝐺 ↑ 𝜋 . The set of incoming edges to an actor 𝛼 in

Algorithm 1 :

 1 Modified Breadth-First Search (BFS) to compute nblf ↑ 𝜋 and related necessary conditions 1 function nblfExt(𝜋) 2 forall 𝛼 ∈ 𝐺 do 3 timeTo(𝛼) ← 0; nblf ↑ 𝜋 (𝛼) ← 0; 4 nbVisits(𝛼) ← 0; 5 𝐶 tot ← 0; queue ← ∅; addLast(queue, 𝜋); 6 D ↑ 𝜋 ← ∅; nblf ↑ 𝜋 (𝜋) ← 1;

7 while

 7 queue ̸ = ∅ do 8 𝛼 ← pop(queue); D ↑ 𝜋 ← D ↑ 𝜋 ∪ {𝛼 }; 9 forall 𝑒 ∈ 𝑂𝐸 ↑ 𝜋 (𝛼) do 10 dest ← dst(𝑒);

  Shortest schedule of graph in Figure5a.

Figure 5 :

 5 Figure 5: A false positive to Algorithm 1: 𝐵 3 cannot be scheduled before the graph period.

Figure 6 :

 6 Figure 6: Scheduling bounds on the number of cores 𝑚.

Figure 7 :Figure 8 :

 78 Figure 7: Evaluation of the schedulability gap on the small random graphs RandomDAG1-5.

Figure 9 :

 9 Figure 9: Evaluation of the graph period computed by Algorithm 2 compared to ADFG with global EDF policy. Number of cores in abscissa.

1 (

 1 a) Sample SDF graph. The repetition vector is[START_REF] Ali | Generalized Extraction of Real-Time Parameters for Homogeneous Synchronous Dataflow Graphs[END_REF][START_REF] Berry | The Esterel synchronous programming language: design, semantics, implementation[END_REF][START_REF] Berry | The Esterel synchronous programming language: design, semantics, implementation[END_REF] Schedule example of graph 10a, on two cores, with firings of a self-loop.

Figure 10 : 1 (

 101 Figure 10: Counter-example to generalization of Equation (6): actor 𝐴 is not always executed alone.

Figure 11 :

 11 Figure 11: Floor function underestimation example, as used in Equation (7).

𝐴 5 𝐵 3 (

 53 a) SDF graph example, of repetition vector[START_REF] Berry | The Esterel synchronous programming language: design, semantics, implementation[END_REF][START_REF] Bhattacharyya | Optimization of signal processing software for control system implementation[END_REF] 𝑇 .

Figure 13 :

 13 Figure13: Unicore partially periodic schedule example, see Figure1cfor fully periodic comparison.

  So this number can also be computed considering all tokens produced on 𝑒 by src(𝑒) during one scheduler iteration, before the last firing of 𝜋: this is why ì 𝑟 [src(𝑒)]nblf

	↑ 𝜋 (src(𝑒))
	multiplies the production rate in the following equality.

), let us consider the firings of the actor dst(𝑒) before those that are induced by the last firing of 𝜋. By definition this number of firings is ì 𝑟 [dst(𝑒)]nblf ↑ 𝜋 (dst(𝑒)). Under Assumption 1, there are exactly ì 𝑟 [𝛼] firings of each actor 𝛼 during one scheduler iteration.

Table 1

 1 Add tasks in the schedule queue only if their predecessors are allocated. If all predecessors of dst(𝑒) have visited it, dst(𝑒) is added in the queue.

	5	if nbVisits(dest) = #𝐼𝐸(dest) then
	6	push(𝑙, dest);

details the characteristics of the generated graphs. The first five graphs are small, with only ten actors, in order to make comparison with the optimal number of cores computed by a Constraint Programming (CP) solver. The generated graphs do not contain any delay. Algorithm 2: Scheduling of tasks 1 procedure addReadyTasks(𝑙, 𝜏, nbAllocations) ⊲ 2 remove(𝑙, 𝜏); nbAllocations ← nbAllocations + 1; 3 forall 𝑒 ∈ 𝑂𝐸(𝜏) do ⊲ Visit all successors of newly allocated 𝜏.

4

dest ← dst(𝑒); nbVisits(dest) ← nbVisits(dest) + 1; predFinishTime(dest) ← max{predFinishTime(dest), finishTime(𝜏)}; ⊲ 7 procedure casIdleTime(startTimeDif , currentIdleTime, maxIdleTime)

  𝐶 𝜏 ; push(coresHead, 𝜏); addReadyTasks(𝑙, 𝜏); ⊲ Update 𝜏, 𝑐 and 𝑙. all tasks without incoming edges, always maintained by increasing average start time i.e. xs + ns 2 ;

	11	coresHead ← head(𝑐); startTime ← max{predFinishTime(𝜏), finishTime(coresHead)};
	12	if startTime > xs(𝜏) then
	13	raise Scheduling failed.;
	14	if startTime + 𝐶 𝜏 > deadline then
	15	return;
	16	casIdleTime(startTime -finishTime(coresHead), currentIdleTime, maxIdleTime) ;
		Name	#actors avg. WCET #firings #deps. in 𝐺 * ì 𝑟 [𝜋]	𝑇 𝐺	Time Alg.1 Time Alg.2 Time Choco
		RandomDAG1	10	100	141	280	5	2445	7 ms	27 ms	T/O (12 h)
		RandomDAG2	10	100	184	373	7	4270	4 ms	13 ms	320327 ms
		RandomDAG3	10	100	139	370	13	9412	4 ms	10 ms	993116 ms
		RandomDAG4	10	100	143	329	3	1557	3 ms	11 ms	T/O (12 h)
		RandomDAG5	10	100	136	251	3	1377	4 ms	7 ms	9046 ms
		RandomDAG6	100	200	3226	6093	7/4	13496	10 ms	134 ms	-
		RandomDAG7	100	200	2824	6239	5/10 15040	6 ms	68 ms	-
		RandomDAG8	100	200	2978	6341	7/7	11711	5 ms	61 ms	-
		RandomDAG9	100	200	2567	5600	6/6	8496	10 ms	89 ms	-
		RandomDAG10	100	200	3358	6535	10/10 16680	8 ms	15 ms	-
	Table

⊲ Check and set idle time. 17

finishTime(𝜏) ← startTime + 18 procedure schedule(tasks, graphPeriod, 𝑚) 19 forall 𝜏 ∈ tasks do 20 nbVisits(𝜏) ← 0; predFinishTime(𝜏) ← ns(𝜏) ; ⊲ Sets initial properties of each task.

21 maxIdleTime ← 𝑚 * graphPeriod -𝜏 𝐶 𝜏 ; currentIdleTime ← 0; nbAllocations ← 0; 22 𝑙 ← 23 𝑐 ← schedule of each core, always maintained by increasing finish time; 24 while 𝑙 ̸ = ∅ do 25 𝜏 ← head(𝑙); prevNbAllocations ← nbAllocations; 26 if isThereACoreIdlingBefore(𝑐, predFinishTime(𝜏)) then ⊲ predFinishTime is the finish time of direct predecessors.

27 forall 𝜏 𝑏 ∈ possibleAllocationsBefore(𝑙, 𝑐, predFinishTime(𝜏)) do 28 allocateAndRemoveIfBefore(𝑙, 𝜏 𝑏 , 𝑐, predFinishTime(𝜏), maxIdleTime, currentIdleTime, nbAllocations); 29 if prevNbAllocations < nbAllocations then 30 continue ; ⊲ We restart the loop since new tasks may be ready now. 31 allocateAndRemoveIfBefore(𝑙, 𝜏, 𝑐, ∞, maxIdleTime, currentIdleTime, nbAllocations);

  𝐵 1 𝐵 2 𝐵 3 𝐵 5 𝐴 2 𝐵 1 𝐵 2 𝐵 3 𝐵 5Figure 12: Example and counter-example of Assumption 1.(a) SDF graph example, of repetition vector [3, 5] 𝑇 . Unicore schedule example of 13a, respecting the actor period 𝑇 𝐴 = 5 and all data dependencies.

														5					3
														𝐴						𝐵
	1	2	3	4	5	6	7	8	9	10 11 12 13 14	1	2	3	4	5	6	7	8	9	10 11 12 13 14 15
	Core 1	𝐴 1		𝐴 3				𝐴 1		𝐴 3	𝐵 4	Core 1	𝐴 1	𝐵 1			𝐴 2		𝐵 2 𝐵 3	𝐴 3	𝐵 4 𝐵 5
															𝐴					𝐴	𝐴
	Core 2	𝐴 2						𝐴 2		𝐵 1 𝐵 2 𝐵 3 𝐵 5
	Core 3							𝐵 * 1 𝐵 * 2 𝐵 * 3 𝐵 * 4 𝐵 * 5		(b)
						iteration 1			iteration 2
	(b) Alternating schedule example of 12a on three cores, not re-
	specting Assumption 1. ✘
	1	2	3	4	5	6	7	8	9	10 11 12 13 14
	Core 1	𝐴 1		𝐴 3		𝐵 4		𝐴 1		𝐴 3	𝐵 4
	Core 2	𝐴 2
	Core 3
						iteration 1			iteration 2
	(c) Normal schedule example of 12a on three cores, respecting
	Assumption 1. ✔

A directed graph is weakly connected when its undirected induced graph is connected (i.e. a path exists between each pair of distinct vertices).

http://www.aadl.info

In this paragraph, the latency is taken as the finish time of the last task in the schedule during one scheduler iteration, instead of during one graph iteration as in Section

ACKNOWLEDGMENTS

This project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement №732105 and from the Région Bretagne (France) under grant ARED 2017 ADAMS. We would like to thank J. Castrillon for his kind answers to our questions about the MAPS tool.


Blust, Robert, & Alexander D. Smith, 2014, A Bibliography of the Languages of Borneo (and Madagascar), Phillips, Maine: The Borneo Research Council, Reference Series, No. 2, 218 p. (ISBN 1-929900-15-5), CD-ROM.

Bernard Sellato (Centre Asie du Sud-Est, CNRS & EHESS, Paris) In 1958 A.A. Cense and E.M. Uhlenbeck"s Critical survey of studies on the languages of Borneo appeared, the second volume of the landmark eight-volume KITLV Bibliographical Series covering the former Dutch East Indies. Ever since, it remained the only comprehensive work exclusively devoted to Borneo as a whole, while several more recent bibliographies were both restricted to parts of the island and not solely focused on languages: e.g., Avé et al. (1983) on West Kalimantan, Rousseau (1988) on "Central Borneo", Combrink et al. (2006Combrink et al. ( -2008) ) on Sabah. As Blust and Smith straightforwardly state, "it is the specific aim of this book to provide a modernization of the broad coverage of work on the languages of Borneo that characterized the Cense and Uhlenbeck volume".

The present volume consists in one very substantial section (Part 2.3, listing in alphabetical order of authors" last names a selection of over 1,400 "Descriptive, theoretical and comparative works" by over 700 writers. Although it is not a systematically "annotated bibliography", scores of entries are accompanied by a "Comment" by either author.

Heralding this main section, a "Preface and acknowledgements (pp. i-iii), an "Introduction" (pp. v-vi), an "Overview of the languages" (Part 1, pp. 1-12), an "Overview of the literature" (Part 2, pp. 13-19), a short list of "Previous bibliographies" (Part 2.1, pp. 20-21), and a list of "Works of a wider scope" also including some valuable annotations (Part 2.2, pp. 22-40). It is followed by an index of language names and language groups (pp. 215-218). As the section outline and pagination system is a bit confusing, a table of contents may have been welcome. This bibliography grew out of R. Blust making use, as study material for graduate students" assignments, of some forty sets of linguistic field notes he had collected in Sarawak 1970-71; some students later contributed to the bibliographic compilation, one of whom being credited with co-authorship. Clearly, a number of thorny questions emerged in the process, leading to some weighty decisions. Firstly, the incorporation of studies on Madagascar languages: this is justified by the now general acceptance, since Otto Dahl"s (1951) work, of a southeastern Bornean origin of Malagasy dialects. Secondly, that of the languages of the Sama-Bajaw sea nomads: although these languages are found not only in Borneo, but also as far afield as eastern Indonesia and the Philippines, their origin is also believed to lie in southeastern Borneo. Also included is the language of long-established Bugis communities. Conversely, Malay and the Chamic languages, also believed to ultimately having appeared in (southwestern) Borneo, but at a much earlier time, were excluded from the scope of this bibliography (see a discussion of all these choices, pp. 2-4; six local Bornean Malay dialects, however, are included, p. 8), and so were those of Borneo"s Chinese communities and of the Tausug immigrants from the Philippines. The decision to include Javanese remains unexplained.

Other difficulties in compiling this bibliography lied in building an inventory of languages (pp. 4-10), beginning with those related to the language/dialect distinction and to specific chaining situations. The list of languages appearing heresome 160generally follows the Summer Institute of Linguistics International"s 17 th edition of Ethnologue, although it was sometimes found to be of inadequate reliability, and alternately over-or under-differentiating between languages.

The rationales underlying decisions made to include certain types of documents and not others and regarding how much to include of material present in earlier bibliographiesand the careful research procedures leading to the final listing are extensively exposed (pp. 13-18).

Straying from the book"s strictly linguistic focus, a brief discussion of some "distinctive cultural traits associated with much of Borneo" (longhouse habitat, distended earlobes, non-Negrito forest nomads; pp. 1-2) appears here both reductive and somewhat futile. Likewise, some observations of a more historical or ethnographic value are questionable: e.g., the phrase "masuk Melayu" ("to become Melayu"; p. 2) historically first referred to the adoption of the "Malay" way of life (riparian settlement, trade patterns, vehicular Malay dialect), and only much later to conversion to Islam, then to actually be equated with "masuk Islam"; and Kendayan (or Kanayatn) certainly should not be viewed as a catch-all term for all West Kalimantan groups speaking Malayic languages (pp. 2, 5). Despite these minor squabbles (and a few remaining typos), this Bibliography is a major and most welcome achievement that will prove of invaluable service to all Austronesian language specialists, as well as to any researcher in any discipline in Borneo and, of course, any library of Asian studies. As the authors rightly state (p. vi), it constitutes a strong established resource from which future offerings of The languages of Borneo will grow. Of considerable added value is the enclosed CD-ROM, which makes this work a powerful research tool.