Mohamed Benazouz
email: mohamed.benazouz@lip6.fr

Alix Munier-Kordon

Cyclo-Static DataFlow Phases Scheduling Optimization for the Throughput Constrained Buffer Sizes Minimization Problem

Keywords: Cyclo-Static DataFlow, Buffer Capacity, Min-Max Linear Program, Digital Signal Processing, High-Level Synthesis

Cyclo-Static DataFlow (CSDF) is a powerful model for the specification of DSP applications. However, as in any asynchronous model, the synchronization of the different communicating tasks (processes) is made through buffers that have to be sized such that timing constraints are met. In this paper, we want to determine buffer sizes such that the throughput constraint is satisfied. This problem has been proved to be of exponential complexity. Exact techniques to solve this problem are too time and/or space consuming because of the self-timed schedule needed to evaluate the maximum throughput. Therefore, a periodic schedule is used. Each CSDF actor is associated with a period that satisfies the throughput constraint and sufficient buffer sizes are derived in polynomial time. However, within a period, an actor phases can be scheduled in different manners which impacts the evaluation of sufficient buffer sizes.

This paper presents a Min-Max Linear Program that derives an optimized periodic phases scheduling per CSDF actor in order to minimize buffer sizes. It is shown through an MP3 Playback and an H.263 Encoder that this Min-Max Linear Program allows to obtain close to optimal values while running in polynomial time. The impact of phases scheduling on periodic schedulability of applications with critical cycles is also highlighted on a Channel Equalizer.

I. INTRODUCTION AND RELATED WORKS

Dataflow paradigm is a powerful Model of Computation (MoC) for timing analysis of system behavior. This processbased MoC represents computation as a set of concurrent processes performing treatments on data streams that are exchanged through buffered channels. Therefore, it is widely used for modelling digital signal processing (DSP) applications. These applications are often associated with real-time constraints. In this paper, we want to determine buffer sizes such that throughput constraints are satisfied.

Initially, Synchronous DataFlow Graphs [START_REF] Lee | Synchronous data flow[END_REF] (SDFG) were adopted. Processes are represented by nodes called actors and buffers are modelled by arcs. Actors consume and produce a constant and fixed number of data. Then, to increase the scope, Cyclo-Static DataFlow graphs (CSDFG) were introduced [START_REF] Bilsen | Cyclo-static data flow[END_REF]. In this model, the number of data consumed and produced by an actor is allowed to vary from a firing to the next in a cyclic pattern. This pattern is constant and known at compile time. Its length defines the number of actor phases. Phases can be seen as iterations of a for loop that is represented by the actor. In this for loop, a condition that depends on the iteration number determines the transfer rate towards a buffer. Now, this entire loop can also be modelled by an SDF actor. The resulted single phase of this SDF actor has then for transfer rate the cumulative transfer rates from the pattern. This modelling results in a significant overestimation of buffer capacities as all the necessary data are consumed/produced in one atomic fashion respectively at the start/end of the actor execution [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF]. Besides, modelling some processes by an SDF actor may introduce deadlock situation when the actor is involved in a cycle even if the CSDF model is deadlock-free [START_REF] Bilsen | Cyclo-static data flow[END_REF], [START_REF] Parks | A comparison of synchronous and cycle-static dataflow[END_REF]. Furthermore, [START_REF] Denolf | Exploiting the expressiveness of cyclo-static dataflow to model multimedia implementations[END_REF] proves that CSDF modelling enlarge the scope of channels that can be considered. For instance, an extension is provided for shared buffers (under condition) with multiple consumers and producers.

An accurate CSDFG of an application can be obtained through an automatic extraction from the Cycle Accurate Model (CAM) delivered by the synthesis tool at the Register-Trasfer Level (RTL). An approximate modelling at higher level such as the Transactional-Level Modelling (TLM) can also be used under condition of bounding the Worst Case Execution Time (WCET) of actors. This would allow performance evaluation of a design at a higher level without having to generate the RTL.

Another issue related to buffers is preloading feedback buffers, i.e. to determine the number of data that should be initially in a feedback buffer. A feedback buffer creates a cycle (closed loop) from the forward and the feedback paths. An empty feedback buffer results in deadlock situation if buffers on the forward path are not sufficiently initialized. In addition, an under-preloaded feedback buffer results in insufficient throughput. Indeed, the first access to the feedback buffer determines the number of data in the cycle just created (closed) and thus the throughput. Non-blocking read can overcome this issue as data are read only when available in the buffer. However, dataflow semantic supposes blocking read. Furthermore, in some High-Level Synthesis tools that need to simulate C code against RTL for verification purpose, insufficiently prefilled feedback buffers cause C and/or RTL simulation to deadlock or stutter [START_REF] Fingeroff | High-Level Synthesis Blue Book[END_REF].

The capacity of a buffer is defined as the maximum number of data that the buffer can store at a time. We associate a cost per unit of storage and we limit our study to buffers for which all data stored are of the same cost. This cost may be related to the width of the buffer (size of data) or the technology/location of the memory allocated to the buffer. Then, the cost of a buffer is given by its capacity times the cost of one data. Both cost and size are used indifferently in this paper to refer to a buffer cost.

Contribution: The principal contribution of this paper is a Min-Max Linear Program (LP) that derives an optimized periodic phases scheduling per CSDF actor in order to minimize buffer sizes. This is a major improvement to some techniques based on periodic schedules [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF], [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static real-time systems with back-pressure[END_REF] to minimize the overall buffer sizes that satisfies a fixed throughput. While these techniques considered a phases scheduling that takes into account only phases execution times, the Min-Max LP will enable to consider in addition phases transfer rates, resulting then in a better estimation of sufficient buffer sizes. This is accomplished as follows. First, the throughput constrained buffer sizes minimization problem is formulated by an Integer Linear Program (ILP). The built ILP accepts any valid phases scheduling. Then, it is shown that the lower bound on the capacity of a buffer computed by this ILP is closely related to the phases schedulings of its consumer and producer. Furthermore, it is proved that the analytical approach presented in this paper enables to optimize separately these two phases schedulings. This leads to the conclusion that an actor phases scheduling optimization can be performed in isolation from the other actors. An actor may have several adjacent buffers and the cost per unit of storage may differ from an adjacent buffer to another. These constraints are taken into account and the actor phases scheduling optimization problem is modelled by a Min-Max LP. Once all actors phases scheduling optimization done, they are reported into the ILP to derive the start time of the first execution of each actor with the objective of minimizing sufficient buffer sizes. As it will be demonstrated in the experimental results section, the computed values for buffer sizes are much better than those computed in [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF], [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static real-time systems with back-pressure[END_REF] while the temporal impact due to the additional Min-Max LP calculation remains limited.

Related Works: The problem tackled in this paper has been addressed in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF]. A polynomial heuristic is presented that schedules actor phases periodically with a period that satisfies the throughput constraint. The approach used in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] is close to network calculus [START_REF] Cruz | A calculus for network delay. i. network elements in isolation[END_REF] in the way that it uses (linear) upper/lower bounds on the token production / consumption times to derive sufficient buffer capacities. It is shown that the buffer capacity is proportional to the delay between the upper bound on the data production times and the lower bound on the data consumption times. Then, the producer and the consumer phases schedulings are optimized such that this delay is minimized. These linear bounds are defined per buffer in isolation, so are the derived phases schedulings and thus the delays. Indeed, such a technique hides the fact that optimizing a phases scheduling can be done per actor in isolation as it is proved in this paper. Therefore, the technique presented in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] results, for an actor, in as much phases schedulings as the number of adjacent buffers to this actor. Authors do not specify the technique used to combine these schedulings to derive one phases scheduling per actor. Moreover, it is not clear how the impact of different costs for the adjacent buffers may be integrated, as the technique by construction cannot consider buffer costs. In the experimental results section, it is shown that our algorithm results in a more accurate estimation of sufficient buffer capacities compared to [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF].

Exact techniques compute optimal buffer capacities that satisfy the throughput constraint. In such techniques the selftimed execution is used to evaluate the maximum throughput that can be accomplished by a solution. The self-timed execution, called also the as soon as possible (in short asap) schedule, consists in executing actors as soon as there are enough data in their input buffers. No polynomial algorithm exists to evaluate the maximum throughput for SDFGs and thus for CSDFGs. The consequence is that related optimization problems are probably not in NP. In [START_REF] Marchetti | Complexity results for weighted timed event graphs[END_REF], it is proved that buffer sizes minimization problem under throughput constraint is NP-complete for Single Rate DataFlow graphs (SRDFG), i.e. SDFGs with all transfer rates equal 1. Thus, the problem is NP-Hard for general SDFGs and CSDFGs.

Exact techniques can be of two classes depending on how the maximum throughput is evaluated. One way to evaluate this throughput for a CSDFG is through a translation to the equivalent Single Rate DataFlow graph (in short SRDFG) [START_REF] Bilsen | Cyclo-static data flow[END_REF]. The Maximum Cycle Ratio analysis [START_REF] Dasdan | Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems[END_REF] can then be applied. However, the obtained SRDF graph is of exponential size on the size of the initial CSDF graph. Thus, techniques based on this approach are too space and time consuming to handle real-life DSP applications.

To the best of our knowledge, [START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclostatic and synchronous dataflow graphs[END_REF] proposes the only technique of the second class; the class of techniques that do not need a translation of the CSDFG to the equivalent SRDFG. Using a state-space exploration technique, authors determine the Pareto space of the bi-criterion problem throughput-buffer capacities for marked CSDFGs. Marked CSDFGs are graphs for which the initial number of data in known for all buffers. Thus, uninitialized feedback buffers are not considered. The maximum throughput calculation consists of finding a cycle in the state space to which corresponds a self-timed execution pattern that can be repeated infinitely. The maximum throughput of an actor equals the number of executions in this pattern divided by the duration of the pattern. The number of states to visit before finding a cycle can be exponentially large, especially if the number of actor phases is large. Thus, this maximum throughput analysis has an exponential worstcase complexity. Furthermore, the set of storage distributions to explore is of exponential size on the number of buffers to be sized and is closely related to the values of transfer rates. Therefore, the exact technique presented in [START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclostatic and synchronous dataflow graphs[END_REF] has an exponential complexity, which, as a consequence, limits the CSDFG instances that can be treated. Authors propose an approximation technique to reduce the set of storage distributions to be explored, and thus lowers run-times. Moreover, they raise a thought about the usefulness that may have fast heuristics, as the one proposed in this paper, in speeding-up the techniques proposed in [START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclostatic and synchronous dataflow graphs[END_REF]. In fact, both the exact and the approximation techniques can start exploring from the result of a heuristic, which may lead to a better solution than the heuristic in much less run-time than the exact technique. This idea can be pushed further in the growing context of high-level synthesis and design exploration [START_REF] Gajski | Embedded System Design: Modeling, Synthesis and Verification[END_REF], [START_REF] Bailey | ESL Design and Verification: A Prescription for Electronic System Level Methodology[END_REF]. The ability of high-level synthesis to deliver an RTL quickly enough enables to iterate (explore) over several variations of a design until finding the most suitable solution that satisfies a specified feature (metric). The throughput constitutes one of the most common metrics used during the exploration. A fast heuristic that sizes buffers under a throughput constraint can be of great help in this decision process as it provides a sufficiently fast evaluation tool to allow to go through several designs. Once the design is fixed, exact techniques can be used to obtain optimal values. In fact, potentially excessive run-times of exact techniques do not allow their use during the design exploration process. Thus, heuristics and exact techniques complement each other.

The paper is organized as follows: CSDF graphs are presented in Section II. Conditions for a valid periodic schedule are recalled in Section III. Section IV is dedicated to our actors isolation technique and the constraints linearization step; a necessary steps for our ILP formulation of the buffer sizes minimization problem presented in Section V. The principal contribution, that consists in a Min-Max LP formulation of the phases scheduling optimization problem, is presented in Section VI. Section VII is dedicated to experimental results. We conclude in Section VIII.

II. CYCLO-STATIC DATAFLOW GRAPHS

A Cyclo-Static DataFlow Graph G = (T, A) is a directed graph where the set of nodes T models actors and the set of arcs A corresponds to buffers. Every actor t ∈ T is decomposed into ϕ(t) ∈ N -{0} distinct phases that constitute a periodic execution sequence. As described in the introduction, t can be viewed as a loop of ϕ(t) iterations while every phase represents an iteration. For every value k ∈ {1, • • • , ϕ(t)}, the kth phase of t is denoted by t k and has a constant duration t (k) ∈ Q + . Notice that, by analogy to an execution of a loop, one execution of the actor t ∈ T will refer to the ordered execution of all its phases (iterations) t 1 , • • • , t ϕ(t) . We denote by t, n , n ∈ N -{0}, the nth execution of t. Similarly, for every phase k ∈ {1, • • • , ϕ(t)}, t k , n denotes the nth execution of the kth phase of t. For every couple (k, n) ∈ {1, • • • , ϕ(t)} × N -{0}, P red t k , n is the preceding execution phase of t k , n . More formally,

P red t k , n = t k-1 , n if k > 1 t ϕ(t) , n -1 if k = 1.
The execution t ϕ(t) , 0 is fictitious and is only introduced to simplify the definition of P red.

Every arc a = (t, t ) ∈ A represents a buffer b(a) of unbounded capacity from the actor t to the actor t . ∀k ∈ {1, • • • , ϕ(t)}, w a (k) data are produced in b(a) at the end of an execution of t k . To enable the execution of the phase t k , ∀k ∈ {1, • • • , ϕ(t )}, v a (k ) data are needed to be available in b(a). They are consumed before t k starts its execution. We define the cumulative number of data produced on a by one execution of the actor t as

w a • 1 = ϕ(t)
k=1 w a (k). Similarly, we define the cumulative number of data consumed from a by one execution of the actor t as v a • 1 = ϕ(t ) k=1 v a (k). In a DataFlow Graph, data are represented by tokens. Their initial number for each buffer b(a) is reported by M 0 (a) ∈ N. An arc a = (t, t ) models the synchronization introduced by a buffer b(a) between the actors t and t . However, this forward arc cannot by itself model the limited capacity of b(a). To model the bounded capacity of b(a) a backward arc a = (t , t) is added that models the free space. Hence, M 0 (a ) reports the number of empty containers initially in b(a). For every k ∈ {1, • • • , ϕ(t)}, v a (k) = w a (k) and for every k ∈ {1, • • • , ϕ(t )}, w k (a ) = v k (a). The capacity of the buffer b(a) equals the sum M 0 (a)+M 0 (a ) (see. Figure 1). Two phases or two successive executions of an actor are not supposed to overlap. To prevent such a behaviour, a selfarc (t, t) with one token is added for every actor t ∈ T to guarantee that at most only one phase is running at a time. These arcs are not pictured, but their effect is taken into account when constructing a schedule (see. Subsection III-B).

t ℓ t = [2, 4] t ′ ℓ t ′ = 3 t t ′ w a = [3, 5] M 0 (a) = 0 v a = 2 M 0 (a ′ )
Without loss of generality, it is assumed that the application is modelled using a connected CSDFG. It is also assumed that all the actors are connected by buffers with limited capacity, thus the graph is strongly connected. A path of G of length p ∈ N-{0} is defined by a list of actors

-→ t 1 t p = (t 1 , t 2 , • • • , t p ) such that for any k ∈ {1, • • • , p -1}, (t k , t k+1 ) ∈ A. A cycle
is a path such that t p = t 1 . The weight of a path -→ t 1 t p defines a relation between the cumulative transfer rates of the actors and is given by the ratio

W ( -→ t 1 t p ) = a∈ -→ t 1 t p w a • 1 v a • 1 .
A feasible (valid) schedule of a CSDFG is a function s that associates, for every triple (t, k, n) with t ∈ T , k ∈ {1, • • • , ϕ(t)} and n ∈ N -{0}, a start time s(t k , n) for the nth execution of t k such that the number of token in every arc a ∈ A remains non negative, i.e. no data is read before it is available. The start times of an actor coincide with those of its first phase, i.e. s(t, n) = s(t 1 , n).

Consistency is a necessary (not sufficient) condition for the existence of a valid schedule within bounded memory [START_REF] Lee | Consistency in dataflow graphs[END_REF]. Two methods exist to check consistency. In [START_REF] Bilsen | Cyclo-static data flow[END_REF], Bilsen et al. extend the condition for the consistency of SDFGs [START_REF] Lee | Consistency in dataflow graphs[END_REF] to the case of CSDFGs by considering the cumulative number of tokens produced/consumed by actors. Let us consider the pre-post |A| × |T | matrix Γ defined by

Γ at =    w a • 1 if a = (t, t ), t ∈ T -v a • 1 if a = (t , t), t ∈ T 0 Otherwise. The CSDFG is consistent if the rank of Γ is |T | -1.
Then, the rank of solutions space of the balance equation Γ

• r = 0 is not null. The smallest non trivial (∀i ∈ {1, • • • , |T |}, r(i) = 0)
positive integer solution is called the repetition vector. This vector determines the number of executions per actor in a periodic execution pattern that brings back the CSDFG to a state (i.e. the number of tokens per arc) identical to its initial state. In terms of phases, for an actor t i , r(i) × ϕ(t i ) phases are executed within this execution pattern.

Another way to check consistency is to prove that all paths that connect a couple of actors have the same weight, otherwise the graph is inconsistent [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF]. By analogy to Weighted Event Graph [START_REF] Teruel | On weighted T-systems[END_REF], a subclass of PetriNets that is equivalent to SDFG, these graphs are called unitary. A unitary graph is a graph in which all cycles have a weight of one. This property can be checked in O(|T |×|A|) using the shortest path Bellman-Ford algorithm, which, in general, performs faster than solving the system of linear equations

Γ • r = 0 that is in O(|T | 3 ) [17].
In the following, we restrict our study to consistent strongly connected CSDFGs as inconsistent graphs will either deadlock or need unbounded buffers.

We consider the existence of an input or output actor t ∈ T for which a minimum throughput (frequency) of value ν t is required. The throughput of the CSDFG for a schedule s is defined as ν(s) = lim n→∞ n s(t , n) and must then verify ν(s) ≥ ν t . For any infinite valid schedule achieved within bounded memory, to ensure no tokens lack/overflow, throughputs of two adjacent actors t and t with a = (t, t ) ∈ A must verify

ν t = v a • 1 w a • 1 ν t .
This relationship is subsequently used to compute all tasks throughputs. Starting from t for which the throughput ν t is set, the throughput of every actor t can be computed by a Depth-First Search algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF]. Consistency ensures that whatever the path used to reach t ∈ T -{t }, the computed throughput ν t is always the same, thus the following

∀t ∈ T -{t }, ν t = ν t /W ( -→ tt )
where

-→
tt is a path of G from t to t . In the next section, some already established results for the feasibility of periodic schedules are presented to enhance understanding of the contributions of this paper.

III. VALID SCHEDULES

Let us consider a bounded buffer b(a) modelled by the couple of arcs a = (t, t ) and a = (t , t). Let us consider also the phases t k and t k . The fact that an execution t k , n has to wait until an execution t k , n has finished is called a precedence constraint from t k , n to t k , n . The Dataflow semantic imposes a blocking read; an execution cannot start until enough data on input buffers are available. The forward arc a under this semantic induces then an infinite number of precedence constraints from t k executions to t k executions. To prevent data from being overwritten we will also suppose a blocking write semantic; an execution cannot start until enough empty space on output buffers are available. This semantic is equivalent to a blocking read from the backward arc a on which the number of tokens represents the number of empty containers. As mentioned, a schedule is valid if the number of tokens remains non negative all the time. Then, a valid schedule should respect all the precedence constraints for all the couple of phases. Otherwise, some tokens are consumed before they are available and the number of tokens becomes negative which invalidates the schedule.

A. Precedence constraint

Formally, an arc a induces a precedence constraint from the execution t k , n to the execution t k , n if 1. t k , n can be executed at the completion of t k , n , 2. P red t k , n can be executed before the end of t k , n but not t k , n .

Let us denote by D + a t k , n (resp. D - a t k , n ) the cumulative number of tokens produced (resp. consumed) by t (resp. t ) in the arc a from the first execution until t k , n (resp. t k , n ) included. Lemma 1, proved in [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF], defines a necessary and sufficient condition for the existence of a precedence constraint from t k , n to t k , n in terms of

D + a t k , n and D - a t k , n . Let us denote for every arc a = (t, t ) ∈ A, gcd a = gcd(w a • 1, v a (1), • • • , v a (ϕ(t ))), gcd a = gcd(v a • 1, w a (1), • • • , w a (ϕ(t)))
, where gcd is the greatest common divisor of a given list of non negative integers. For every integer α ∈ Z and γ ∈ {gcd a , gcd a }, we also set

α γ = α γ • γ and α γ = α -γ if α is a multiple of γ α γ otherwise.

Lemma 1 ([7]

). Let a = (t, t ) ∈ A and the couple of executions t k , n and t k , n . Then there exists a precedence constraint from t k , n to t k , n , iff:

min{Hmax(k), H max (k, k )} ≥ D + a t k , n -D - a t k , n ≥ Hmin(k, k )
with

Hmax(k) = -M0(a) -D + a P red t k , 1 gcda + D + a t k , 1 , H max (k, k ) = -M0(a) + D - a t k , 1 gcd a -D - a t k , 1 + wa(k) and Hmin(k, k ) = max{0, wa(k) -va(k )} -M0(a).

B. Periodic schedules

Periodic schedules are a mean to overcome the exponential complexity of the self-timed execution analysis. In counterpart to an overestimation of sufficient buffer capacities, the analysis can be made in polynomial time. In a periodic schedule s, each actor and its phases must be fired periodically with a period that ensures the actor consumes/produces an average amount of data per time units that is necessary and sufficient to satisfy the throughput constraint ν(s). Thus, every actor t ∈ T is fired periodically with a period

µ t = 1/ν t ≥ t • 1 such that 1. ∀n > 0, s(t, n) = s(t, 1)+(n-1)µ t = s(t 1 , 1)+(n-1)µ t . 2. ∀k ∈ {1, • • • , ϕ(t)}, s(t k , n) = s(t, n) + ζ t (k). 3. ζ t (1) = 0; ∀k ∈ {2, • • • , ϕ(t)}, ζ t (k) ≥ ζ t (k-1)+ t (k-1) and ζ t (ϕ(t)) + t (ϕ(t)) ≤ µ t .
Condition 1 expresses the periodicity of the executions of t. Condition 2 defines the phases scheduling ζ t that is used to determine the start times of phases in relation to the start time of the current execution of t. Condition 3 on the phases scheduling ζ t ensures that two successive phases do not overlap and that the last phase finishes before the next execution of t, i.e. t, n + 1 , starts.

A periodic schedule is then completely defined by providing for each actor t ∈ T , the start time of its first execution s(t, 1), its period µ t and its phases scheduling ζ t . In [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF], a periodic schedule is constructed that fixes ζ t (k) to k-1 l=1 t(l) t•1 µ t . This phases scheduling satisfies the previous conditions as

ζ t (k) - ζ t (k -1) = t(k-1) t•1 µ t ≥ t (k -1) if µ t ≥ t • 1.
However, it introduces an additional overestimation of the sufficient buffer sizes as it does not take into account phases transfer rates. The main goal of this paper is to compute an optimized phases scheduling to derive a better estimation of sufficient buffer sizes. Initially, we will assume that the values of ζ t (k) are arbitrary fixed so we can generalize results from [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF] to any phases scheduling. Later, in Section VI, a Min-Max LP is proposed to fix these values.

A precedence constraint induces a delay between the considered executions in any valid schedule. Furthermore, it has been proved [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF] in the case of a periodic schedule that the set of precedence constraints per couple of phases is respected if a delay exists between the start times of the first executions of t and t .

Lemma 2 ([7]

). Let a = (t, t ) ∈ A. The set of precedence constraints from t k to t k is respected if:

s(t , 1) -s(t, 1) ≥ f (k, k ) + µ t wa•1 min g(k, k ) gcda , g(k, k ) gcd a with f (k, k ) = ζt(k) + t(k) -ζ t (k ) g(k, k ) = -M 0 (a) -D + a P red t k , 1 + D - a t k , 1 .
Proof: This is a generalization of the proof in [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF] to the case of any valid phases scheduling.

Let us suppose that a = (t, t ) induces a precedence constraint from 2 . Then, it induces a delay between these two executions, s(t k , n) + t (k) ≤ s(t k , n ). Since we consider periodic schedules, this inequality can be written in terms of the start times of the first executions of t and t :

t k , n to t k , n with k ∈ {1, • • • , ϕ(t)}, k ∈ {1, • • • , ϕ(t )} and (n, n ) ∈ (N-{0})
s(t , 1) -s(t, 1) ≥ f (k, k ) + (n -1)µ t -(n -1)µ t with f (k, k ) = ζ t (k) + t (k) -ζ t (k )
. Now, we want to derive a delay that satisfies all the set of precedence constraints from t k to t k , i.e. for all the couples (n, n ) such there exists a precedence constraint from t k , n to t k , n .

By definition of D + a and

D - a , D + a t k , n -D - a t k , n = D + a t k , 1 + (n -1)w a • 1 -D - a t k , 1 -(n -1)v a • 1. We deduce then n -1 = 1 wa•1 (D + a t k , n -D - a t k , n + (n -1)v a • 1 -D + a t k , 1 + D - a t k , 1
) . If we replace n -1 in the inequality by this value, we get

s(t , 1) -s(t, 1) ≥ f (k, k ) -(n -1) µ t -va•1 wa•1 µ t + µt wa•1 (D + a t k , n -D - a t k , n -D + a t k , 1 + D - a t k , 1
) . As mentioned before, for any infinite valid schedule achieved within bounded memory, throughputs of t and t must verify

ν t = v a • 1 w a • 1 ν t .
Since, for any periodic schedule that satisfies the thoughput constraint µ t = 1/ν t and µ t = 1/ν t , then

µ t = v a • 1 w a • 1 µ t . Hence, µ t - v a • 1 w a • 1 µ t = 0.
Thus,

s(t , 1) -s(t, 1) ≥ f (k, k ) + µt wa•1 (D + a t k , n -D - a t k , n -D + a t k , 1 + D - a t k , 1 ) . According to Lemma 1, D + a t k , n -D - a t k , n ≤ min{H max (k), H max (k, k )} for any couple (n, n ) such there exists a precedence constraint from t k , n to t k , n . Then, if we replace D + a t k , n -D - a t k , n by min{H max (k), H max (k, k )} in
the inequality, the obtained delay between s(t , 1) and s(t, 1) satisfies all the precedence constraints from t k to t k :

s(t , 1)-s(t, 1) ≥ f (k, k )+ µ t wa•1 (min{Hmax(k), H max (k, k )} -D + a t k , 1 + D - a t k , 1 . Since D - a t k , 1 (resp. D + a P red t k , 1 ) is a multiple of gcd a (resp. gcd a ), H max (k) -D + a t k , 1 + D - a t k , 1 = -M 0 (a) -D + a P red t k , 1 + D - a t k , 1 gcda and H max (k, k ) -D + a t k , 1 + D - a t k , 1 = -M 0 (a) -D + a P red t k , 1 + D - a t k , 1 gcd a Hence, s(t , 1) -s(t, 1) ≥ f (k, k ) + µ t wa•1 min g(k, k ) gcda , g(k, k ) gcd a with f (k, k ) = ζ t (k) + t (k) -ζ t (k ) g(k, k ) = -M 0 (a) -D + a P red t k , 1 + D - a t k , 1 .
Then a minimum delay β a , that is the maximum of the delays computed per couple of phases, can be derived to ensure that no data is consumed by t before it is available.

Lemma 3 ([7]

). Let a = (t, t ) ∈ A. All the precedence constraints caused by a are fulfilled if:

s(t , 1) -s(t, 1) ≥ βa with βa = max k,k f (k, k ) + µ t wa•1 min g(k, k ) gcda , g(k, k ) gcd a .
Lemma 3 defines a set of potential constraints, one per arc, that prunes all the precedence constraints between the executions of adjacent actors. It is then sufficient that a periodic schedule satisfies this set of potential constraints to be valid.

Theorem 1 ([7]

). A periodic schedule that verifies:

∀a = (t, t ) ∈ A, s(t , 1) -s(t, 1) ≥ β a is feasible.
The next step is to build an Integer Linear Program based on this set of potential constraints to determine the start times of first executions of actors (i.e. s(t, 1), t ∈ T ) while minimizing buffer sizes. However, when M 0 (a) is unknown, the nonlinearity of β a on M 0 (a) prevents such an ILP formulation. The following section constitute the first contribution of this paper. It is dedicated to the linearization of β a on M 0 (a). This will lead, by a restriction on the values taken by M 0 (a), to the computation of a sufficient delay that is linear on M 0 (a).

IV. LINEARIZATION OF THE DELAY β a

A. Actors Isolation

The first disturbing part in the current formula of the minimum delay β a is the impossibility to decouple terms depending on the phase t k from those depending on the phase t k . It disables any treatment per actor in isolation, particularly the optimization of phases scheduling as we will see in Section VI. It may also increase significantly run-times in the case of large numbers of phases.

The idea to isolate t from t is as follows. We analyse the function x γ for different values of γ in order to break the coupling due to min( g(k, k ) gcda , g(k, k ) gcd a ) in the formula of β a . If we can figure out which of g(k, k ) gcda or g(k, k ) gcd a is more likely to coincide with min( g(k, k ) gcda , g(k, k ) gcd a ), then we can decide which of

β 1 a = max k,k {f (k, k ) + µt wa•1 g(k, k ) gcda } or β 2 a = max k,k {f (k, k ) + µt wa•1 g(k, k ) gcd a } should substitute for β a .
Both β 1 a and β 2 a are greater than or equal to β a . Then, all the precedence constraints induced by a are still respected if s(t , 1)s(t, 1) ≥ β 1 a or s(t , 1)s(t, 1) ≥ β 2 a . However, the choice between these two values to substitute for β a needs to be the more accurate possible, as the accuracy of computed buffer sizes depends on. Once the substitution done, terms in k and k can be decoupled. Indeed, as D - a t k , 1 (resp. D + a P red t k , 1 ) is a multiple of gcd a (resp. gcd a ):

β 1 a = max k F (k, M 0 (a)) + max k G(k ) with F (k, M0(a)) = ζt(k) + t(k) + µ t wa•1 -M0(a) -D + a P red t k , 1 gcda G(k ) = µ t wa•1 D - a t k , 1 -ζ t (k )
and

β 2 a = max k F (k) + max k G (k , M 0 (a)) with F (k) = ζt(k) + t(k) -µ t wa•1 D + a P red t k , 1 G (k , M0(a)) = -ζ t (k ) + µ t wa•1 -M0(a) + D - a t k , 1 gcd a .
Therefore, only ϕ(t) + ϕ(t ) steps are needed to compute β 1 a (resp. β 2 a ).

x min(⌊x⌋ γ1 , ⌊x⌋ γ2 )

0 0 γ2 γ1 2γ2 2γ1 γ2 γ1 2γ2 2γ1 2 3 γ1 1 2 γ2
Fig. 2. The case 2γ 1 = 2 . curve x γ 1 in blue line , x γ 2 in green line and min( x γ 1 , x γ 2 ) in dashed red line.

Figure 2 shows three curves: x γ1 in blue, x γ2 with γ 2 = 2 3 γ 1 in green and min( x γ1 , x γ2 ) in dashed red line. We can restrict the analysis to the interval [0, 2γ 1 [ as 2γ 1 is the least common multiple for both γ 1 and γ 2 . A first look shows that neither x γ1 or x γ2 is dominated (in the sense of minimization) entirely on the whole interval. However, x γ1 coincides with min( x γ1 , x γ2 ) on more than 83% of the interval while it is only 50% for x γ2 . The function x γ2 is strictly dominated by x γ1 on 50% of the interval and the difference x γ2x γ1 attains 2 3 γ 1 . In general, we can prove the following lemma. Lemma 4. Let us suppose ρ • gcd a = σ • gcd a with ρ > σ (i.e. gcd a > gcd a ). Then, x gcda is strictly dominant on (1 -σ+1 2ρ ) • 100% of an interval of σ • gcd a and coincides with x gcd a on 1 ρ • 100%. Moreover, the difference x gcd a x gcda attains ρ-1 ρ gcd a . Therefore, the more gcd a is greater than gcd a , the more the interval on which x gcda is dominant is wider. Thus, if gcd a > gcd a , we are more inclined to substitute min( g(k, k ) gcda , g(k, k ) gcd a ) in the formula of β a with g(k, k ) gcda . In the following, without loss of generality, we will suppose gcd a > gcd a . Then, the sufficient delay considered after this step of isolation is: ). Such a phase may not exist. Indeed, because -M 0 (a) -D + a P red t k , 1 gcda can have two different values depending on whether -M 0 (a) -D + a P red t k , 1 is a multiple or not of gcd a , there may exist two values x 1 and x 2 for M 0 (a) for which, there exists a couple of phases (t k 1 , t k 2 ) such that:

β 1 a = max k F (k, M 0 (a)) + max k G(k ).
∀k = k 1 , F (k 1 , x 1 ) > F (k, x 1 ) and ∀k = k 2 , F (k 2 , x 2 ) > F (k, x 2 )
. Of course, there may exist more than two critical phases. In the example of Figure 3, both k 1 and k 2 are critical as they are not dominated (in the sense of maximization) on the entire interval of M 0 (a) values. Phase k 1 is dominated by k 3 for some values of M 0 (a), however, k 3 is always strictly dominated by k 2 and thus it is not critical.

The concept of useful tokens allows to overcome this issue. In the context of buffer capacities minimization, this concept states that only some values are relevant for M 0 (a); some extra tokens have no effect on the value of the delay β 1 a . First, the case of a unique critical phase is studied. The set of useful tokens is identified and β 1 a is linearized. In case of several critical phases, only one critical phase can be considered for M 0 (a)

F (k {1,2,3} , M 0 (a)) X 1 X 1 + g c d a X 1 + 2 g c d a X 2 X 2 + g c d a X 2 + 2 g c d a x2 x1 ( y -2 ) • g c d a ( y -1 ) • g c d a y • g c d a ( y + 1 ) • g c d a +δ(k 1 )-H +δ(k 1 ) +δ(k 1 +δ(k 1 )+2H +δ(k ) +δ(k 2 )+H +δ(k 2 )+2H
rem(a, k 1

) rem(a, k 2 ) Fig. 3. An example of three phases. Phases k 1 and k 2 are critical. Phase k 3 , strictly dominated by k 2 , is not critical. In yellow, the staircase made of points of jump discontinuity of critical phases. Its height within an interval of length gcda is H = µ t wa•1 gcda.

the linearization of β 1 a . The set of useful tokens must then correspond to intervals on which the selected phase is critical.

a) The critical phase is unique: Let us fix arbitrary the value of M 0 (a). Then, F (k, M 0 (a)) can be computed for every phase k and the unique critical phase k = arg max k F (k, M 0 (a)) can be identified in ϕ(t) steps. Let us define for every phase k, quot(a, k) = -D + a P red t k , 1 gcda 0 ≤ rem(a, k) = -D + a P red t k , 1quot(a, k) < gcd a , respectively the quotient and the remainder in the euclidean division of -D + a P red t k , 1 by gcd a . Let us also define m 0 (a, k) such that m0(a, k) • gcda = --M0(a) + rem(a, k) gcda -gcda. m 0 (a, k) belongs to N ∪ {-1} (for M 0 (a) = 0 and rem(a, k) = 0, m 0 (a, k) = -1). By definition of gcda , we can prove that m 0 (a, k) • gcd a + rem(a, k) ≤ M 0 (a). For the example of Figure 3, let us ignore the phase k 1 , then the unique critical phase is k 2 . If we suppose that M 0 (a) = x 2 , then m 0 (a, k 2 ) • gcd a + rem(a, k ) equals X 2 , which is the first point of (jump) discontinuity to the left of x 2 . Since the function

F is right continuous, F (k 2 , x 2 ) = F (k 2 , X 2 ).
Then, the value of β 1 a is still the same if we replace the value of M 0 (a) by m 0 (a, k 2 ) • gcd a + rem(a, k 2 ). The following lemma formalizes this idea.

Lemma 5. M 0 (a) can be replaced by the less or equal quantity m 0 (a, k )•gcd a +rem(a, k ), with m 0 (a, k )•gcd a = --M 0 (a) + rem(a, k ) gcda -gcd a , without influencing the value of β 1 a . Proof: Since k is the critical phase, then

max k F (k, M 0 (a)) = F (k , M 0 (a)). Now, in the formula of F (k , M 0 (a)), since quot(a, k ) is a multiple of gcd a , then -M0(a) -D + a P red t k , 1 gcda = -M0(a) + rem(a, k ) gcda + quot(a, k ).
However, the substitution of M 0 (a) with the less or equal quantity m 0 (a, k ) • gcd a + rem(a, k ) in -M 0 (a) + rem(a, k ) gcda gives the same value:

-(m 0 (a, k ) • gcd a + rem(a, k )) + rem(a, k ) gcda = -M 0 (a) + rem(a, k ) gcda + gcd a gcda = -M 0 (a) + rem(a, k ) gcda . Thus, F (k , M 0 (a)) = F (k , m 0 (a, k ) • gcd a + rem(a, k )).
Moreover, for the other phases k = k , since we supposed that k is the unique critical phase, then

F (k, m 0 (a, k ) • gcd a + rem(a, k )) < F (k , m 0 (a, k ) • gcd a + rem(a, k )) . Therefore, max k F (k, m 0 (a, k ) • gcd a + rem(a, k )) = F (k , m 0 (a, k ) • gcd a + rem(a, k )) = max k F (k, M 0 (a)
). Then, the substitution does not change the value of β 1 a . Now, if M 0 (a) is unknown, it follows from the previous lemma that only values such that M 0 (a)rem(a, k ) is a multiple of gcd a deserve to be sought for M 0 (a) (points of discontinuity). These values define the set of useful tokens.

The following lemma provides the linear formula of β 1 a , i.e. β 1 a restricted to the set of useful tokens. Lemma 6. The linear formula of the sufficient delay is given by:

β 1 a = max k δa(k) + max k ψa(k ) + µ t wa•1 (-m0(a) • gcda -gcda) with δa(k) = ζt(k) + t(k) + µ t wa•1 quot(a, k)
and

ψa(k ) = G(k ) = -ζ t (k ) + µ t wa•1 D - a t k , 1 .
Then, the critical phase k is the phase that maximizes δ a (k) and the set of useful tokens is defined by M 0 (a) ∈ {0} ∪ {m 0 (a) • gcd a + rem(a, k )|m 0 (a) ∈ N} .

Proof: As a consequence of Lemma 5, for any phase k that may be the unique critical phase, M 0 (a) should be of the form m 0 (a) • gcd a + rem(a, k) with m 0 (a) a variable ∈ N ∪ {-1} that is independent of any phase. Then,

-M0(a) -D + a P red t k , 1 gcda = quot(a, k) -m0(a) • gcda -gcda . As a result, F (k, M0(a)) = ζt(k) + t(k) + µ t wa•1 quot(a, k) + µ t wa•1 (-m0(a) • gcda -gcda) = δa(k) + µ t wa•1 (-m0(a) • gcda -gcda) .
Thus the linear formula of β 1 a . The critical phase k , that is equal to arg max k F (k, M0(a)), is then equal to arg max k δa(k).

b) There are more than one critical phase: Let us denote by S a the set of critical phases. Let us suppose the interval M 0 (a) ∈ [y • gcd a , (y + 1) • gcd a [, y ∈ N (see. Figure 3). Each phase from S a behaves as the unique critical phase on a part of this interval. The points of discontinuity within the interval happen at m 0 (a, k) • gcd a + rem(a, k) with m 0 (a, k) = y, ∀k. Then,

∀k, F (k, y • gcda + rem(a, k)) = δa(k) + µ t wa•1 (-y • gcda -gcda) .
Therefore, it is sufficient to compare the values δ a (k)

to identify the critical phases (for clarity, the values on the vertical axis in Figure 3 were reduced by µt wa•1 (-y • gcd agcd a )). Intuitively, the points of discontinuity of the critical phases forms a staircase (see. yellow staircase in Figure 3). The other points of discontinuity that are below and/or to the left of that staircase belong to phases that are not critical. The point of discontinuity at the top and to the extreme left of the staircase (within the interval) belongs to the critical phase k such that δ a (k ) = max k δ a (k). For the example of Figure 3, k is k 1 . It is the critical phase with the smallest remainder. Indeed, any phase k that has a smaller remainder and δ a (k) ≤ δ a (k ) is dominated (in the sense of maximization) by k and thus it is not critical. More formally, a critical phase k i must verify two conditions:

1. δa(k ) -µ t wa•1 gcda < δa(k i ) ≤ δa(k ). 2. ∀k j ∈ Sa -{k i }, rem(a, k i ) < rem(a, j ) ⇔ δa(k i ) > δa(k j ).
first condition states that a point of discontinuity that is more than µt wa•1 gcd a below the highest point of discontinuity is too below to be on the staircase, thus its phase is not critical. Indeed, the height of the staircase, within any interval of length gcd a , is H = µt wa•1 gcd a . The second condition ensures that all dominated phases are excluded from S a -{k }. This is the case of k 3 , it verifies the first condition, however, rem(a, k 3 ) < rem(a, k 2 ) and δ a (k 3 ) < δ a (k 2 ). Then, it is dominated by k 2 and does not belong to S a .

Only one critical phase can be considered for the linearization of β 1 a . The critical phase we consider in the following is k such that δ a (k ) = max k δ a (k), which is k 1 for our example. This phase is critical on the interval [y • gcd a + max k∈Sa rem(a, k), (y + 1) • gcd a [, i.e. starting from the point of discontinuity of the critical phase with the greatest remainder until the end of the interval (for our example, k 2 is the critical phase with the greatest remainder, i.e. k 2 = arg max k∈Sa rem(a, k)). Then, on this interval

max k F (k, M0(a)) = F (k , M0(a)). Since F (k , .) is right-continuous and constant on [y • gcda + rem(a, k ), + 1) • gcda[, then F (k , M0(a)) = F (k , y • gcda + rem(a, k )) = max k δa(k) + µ t wa•1 (-y • gcda -gcda) .
Therefore,

∀M0(a) ∈ [y • gcda + max k∈Sa rem(a, k), (y + 1) • gcda[, max k F (k, M0(a)) = max k δa(k) + µ t wa•1 (-y • gcda -gcda) .
Then, it is sufficient to limit the number of tokens to the minimum y • gcd a + max k∈Sa rem(a, k), which defines useful tokens for the interval [y • gcd a , (y + 1)

• gcd a [, y ∈ N.
From the previous discussion, the following lemma holds.

Lemma 7. A linear formula of the sufficient delay is given by:

β 1 a = max k δa(k) + max k ψa(k ) + µ t wa•1 (-m0(a) • gcda -gcda) with M0(a) ∈ {0} ∪ {m0(a) • gcda + max k∈Sa rem(a, k)|m0(a) ∈ N}.
Remark 1. In the case gcd a > gcd a , the actors isolation step results in the sufficient delay β 2 a . The issue is then on the determination of the critical phase k = arg max k G (k , M 0 (a)). By the same procedure we get to the following results: let us define quot (a, k ) = D - a t k , 1 gcd a and rem (a, k ) =

D - a t k , 1 -quot (a, k ), then β 2 a = max k δ a (k) + max k ψ a (k ) + µ t wa•1 (-m0(a) • gcd a -gcd a )
with

δ a (k) = ζt(k) + t(k) -µ t wa•1 D + a P red t k , 1
and

ψ a (k ) = -ζ t (k ) + µ t wa•1 quot (a, k ).
Then, the selected critical phase k is the phase that maximizes ψ a (k ) and the set of useful tokens is defined by

M0(a) ∈ {0}∪{m0(a)•gcd a +max k ∈S a rem (a, k )|m0(a) ∈ N}
with S a the set of critical phases.

This concludes the linearization step of the minimum delay β a . The following corollary is a consequence of Theorem 1 and both actors isolation and sufficient delay linearization steps.

Corollary 1. A periodic schedule that verifies, ∀a = (t, t ) ∈ A such that gcda > gcd a , s(t , 1) -s(t, 1) ≥ β 1 a ∀a = (t, t ) ∈ A such that gcd a > gcda, s(t , 1) -s(t, 1) ≥ β 2 a is feasible.

V. BUFFER SIZES MINIMIZATION

Let us suppose an application modelled by a consistent strongly connected CSDFG G = (T, A). Each bounded buffer b(a) of this application is modelled by a forward arc a and a backward arc a . The capacity of b(a) that is defined as the maximum number of data that b(a) can store at a time is then given by M 0 (a) + M 0 (a ). All the storage units of b(a) are of the same size (cost) θ(a), then the size of b(a) is equal to θ(a) × (M 0 (a) + M 0 (a )).

The throughput constrained buffer sizes minimization problem consists in computing a feasible schedule s such that: 1. The overall buffer sizes a∈A θ(a)M 0 (a) is minimized, 2. The throughput of s, i.e. ν(s), is greater or equal to some predefined throughput.

In [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF], using a periodic schedule and a phases scheduling

ζ t (k) = k-1 l=1 t(l) t•1 µ t ,
this problem is formulated as an Integer Linear Program (ILP). In this section, a generalized version of this ILP that accepts any valid phases scheduling is presented. This is allowed by the linearization step and the useful tokens concept developed in the previous section.

At this stage we consider that actors phases schedulings ζ t , t ∈ T have already been fixed. Then, both the set of critical phases and the set of useful tokens per arc can be identified. In the previous section, it has been established that a periodic schedule is feasible if sufficient delays exist between the start times of first executions of adjacent actors (see. Corollary 1); the throughput constrained buffer sizes minimization problem defined above can then be formulated by the following Integer Linear Program Π(G):

min a∈A θ(a)M0(a) subject to                                  ∀a = (t, t ) ∈ A such that gcda ≥ gcd a , s(t , 1) -s(t, 1) ≥ max k δa(k) + max k ψa(k ) + µ t wa•1 (-m0(a) • gcda -gcda) M0(a) ≥ m0(a) • gcda + max k∈Sa rem(a, k). ∀a = (t, t ) ∈ A such that gcd a > gcda, s(t , 1) -s(t, 1) ≥ max k δ a (k) + max k ψ a (k ) + µ t wa•1 (-m0(a) • gcd a -gcd a ) M0(a) ≥ m0(a) • gcd a + max k ∈S a rem (a, k ). ∀a ∈ A, m0(a) ∈ N ∪ {-1} M0(a) ≥ 0. ∀t ∈ T, s(t, 1) ≥ 0.
Solving an ILP has exponential-time worst-case performance. We consider the LP-relaxation of the ILP by ignoring the integrity constraints on m 0 (a), a ∈ A. A solution that satisfies all the constraints of the ILP is then obtained by rounding the fractional elements of the LP-relaxation solution to their nearest higher integer.

VI. PHASES SCHEDULING OPTIMIZATION

This section describes the principal contribution of this paper. An optimized phases scheduling per CSDF actor is derived such that the evaluation of sufficient buffer sizes made by the ILP Π(G) is more accurate. For an actor t, the goal is to fix

ζ t (k), k ∈ {1, • • • , ϕ(t) -1}.
In practice, the phases scheduling optimization step is applied before the construction of the ILP, however, to be able to motivate the usefulness of this optimization step, the ILP has been presented before. First, to introduce the approach, the case of a graph of two actors and one buffer is studied. It is shown that the producer and the phases schedulings have an impact on the lower bound of the buffer capacity computed by the ILP. A Min-Max Linear Program (LP) is derived to optimize an actor phases scheduling with the aim of reducing lower bound. Then, the approach is generalized to the case of an actor with several input/output buffers.

Let us consider a CSDFG G of one buffer b(a) modelled by a forward arc a = (t, t ) and a backward arc a = (t , t). Let us suppose that gcd a > gcd a . It follows that gcd a > gcd a since gcd a = gcd a and gcd a = gcd a . The throughput constrained buffer size minimization problem is formulated by the ILP Π(G): Now, by summing the potential constraints of Π(G), a lower bound for (m 0 (a) + m 0 (a )) • gcd a can be derived:

min M0(a) + M0(a ) subject to        s(t , 1) -s(t, 1) ≥ max k δa(k) + max k ψa(k ) + µ t wa•1 (-m0(a) • gcda -gcda) s(t, 1) -s(t , 1) ≥ max k δ a (k ) + max k ψ a (k) + µ t wa•1 (-m0 (
m0(a) + m0(a ) • gcda ≥ wa • 1 µt (max k δa(k) + max k ψa(k ) + max k δ a (k ) + max k ψ a (k)) -2 • gcda.
It follows that to optimize the capacity of b(a), we have to minimize

max k δ a (k) + max k ψ a (k ) + max k δ a (k ) + max k ψ a (k) which is a linear function of ζ t and ζ t .
Since terms in k and k can be decoupled, the actor t phases scheduling optimization can be performed independently from that of the adjacent actor t . This is enabled by the actors isolation step described in Subsection IV-A. Impacts of the remainders max k∈Sa rem(a, k) and max k∈S a rem(a , k) are not taken into account during the optimization. It would increase considerably the complexity and run-times while the impact on the accuracy should be limited.

Let us denote by ∆ a = max k δ a (k) and by Ψ a = max k ψ a (k). Phases scheduling optimization problem for the actor t can be formulated by the following Min-Max LP:

min (∆a + Ψ a ) subject to                  ∀k ∈ {1, • • • , ϕ(t)}, δa(k) = ζt(k) + t(k) + µ t wa•1 quot(a, k) ≤ ∆a ∀k ∈ {1, • • • , ϕ(t)}, ψ a (k) = -ζt(k) + µ t wa•1 quot (a , k) ≤ Ψ a ζt(1) = 0 ∀k ∈ {2, • • • , ϕ(t)}, ζt(k) -ζt(k -1) ≥ t(k -1) ζt(ϕ(t)) + t(ϕ(t)) ≤ µt
The variables of the LP are ζ t (k)|∀k ∈ {1, • • • , ϕ(t)}, ∆ a and Ψ a . This Min-Max LP will fix ζ t while trying to minimize

∆ a + Ψ a = max k δ a (k) + max k ψ a (k).
As it has the same structure, the Min-Max LP that optimizes the scheduling of t phases is not presented. Now we will extend the optimization technique to the case t has more than one input/output buffer. Since the optimization can be done in isolation from the other actors, the generalization is straightforward. Both the objective function and the system of linear constraints of the previous Min-Max LP can be extended to take into account the impact that a phases scheduling may have on the capacities of adjacent buffers. This impact is weighted as the adjacent buffers may have different costs per unit of storage. In the case of one buffer, the cost does not interfere as the two arcs involved model the same buffer. As a consequence, approaches that optimize buffers in isolation [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] cannot, by construction, consider the impact of a phases scheduling on adjacent buffers with different costs . The following Min-Max LP Π(t) extends the previous linear program:

min (a i =(t,t i ),a i =(t i ,t)) θ(ai)(∆a i + Ψ a i ) subject to                    ∀ai = (t, t i ), ∀k ∈ {1, • • • , ϕ(t)}, δa i (k) = ζt(k) + t(k) + µ t wa i •1 quot(ai, k) ≤ ∆a i ∀a i = (t i , t), ∀k ∈ {1, • • • , ϕ(t)}, ψ a i (k) = -ζt(k) + µ t wa i •1 quot (a i , k) ≤ Ψ a i ζt(1) = 0 ∀k ∈ {2, • • • , ϕ(ti)}, ζt(k) -ζt(k -1) ≥ t(k -1) ζt(ϕ(t)) + t(ϕ(t)) ≤ µt
As any linear program, Min-Max LPs are solvable in polynomial time. Advanced techniques exist to solve efficiently Min-Max LPs. Indeed, because of the wide range of domain applications, Min-Max LPs have been extensively studied during last decades [START_REF] Ding-Zhu | Minimax and Applications[END_REF]. In addition to the graph theory, the game theory constitutes one of the most important applications area of Min-Max linear programming. Phases scheduling can be seen as a cooperative game. Phases are then considered players trying to maximize their own payoffs. The payoffs matrix can be obtained from the constraint matrix of the Min-Max LP. When the game converges to an equilibrium an optimal solution for the Min-Max LP is obtained.

VII. EXPERIMENTAL RESULTS

A. The Impact of Phases Scheduling

In this subsection, the impact of phases scheduling on sufficient buffer sizes evaluation is highlighted on an MP3 Playback application. The CSDFG G of this application presented in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] is composed of four actors and three buffers. The M P 3 actor delivers a 48kHz audio sample stream and the Sample Rate Converter (SRC) actor converts it to a 44.1kHz stream.

The actor AP P models an Audio Post-Processing applied to the stream before it is converted to an analog signal by the Digital-Analog Converter (DAC). The actor M P 3 performs its task in 39 phases during which 1152 samples are produced. The number of samples produced by each phase is given by w M P 3 = [0, 0, 18x32, 0, 18x32]. Phases execution times are In the first experiment, three different phases scheduling are applied to the actor M P 3. The first phases scheduling executes all phases of an occurrence one after the other without interruption, i.e.

ζ M P 3 (k) = ζ M P 3 (k -1)+ M P 3 (k - 1), k ∈ {2, • • • , 39}.
We may call it burst phases scheduling as it responds to a burst transmission criterion. This phases scheduling is not to be confused with an SDF modelling of the M P 3 actor. The SDF modelling consumes/produces the 1152 tokens in an atomic fashion at the start/end of execution while the burst phases scheduling is still consuming/producing data gradually. See [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] for a comparison between SDF and CSDF modelling of this application. The second phases scheduling fixes ζ M P 3 (k) to k-1 l=1 M P 3 (l) M P 3 •1 µ M P 3 . We called it Time Averaged phases scheduling. It was initially used in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static real-time systems with back-pressure[END_REF] for the computation of sufficient buffer capacities. However, the ILP formulation provided by [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF] offers more accurate results than [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static real-time systems with back-pressure[END_REF] for this phases scheduling. The last phases scheduling is determined by our Min-Max LP applied to the 39 phases of the M P 3 actor.

Table I lists B 1 capacities obtained for the three different phases scheduling. The comparison is made for different execution times of SRC, SRC ∈ {2.5, 5, 7.5, 10}ms. The capacities of buffer B 2 for this experiment are not reported as the same results were obtained by all the techniques and this for the different execution times of SRC. Indeed, SRC and AP P are SDF actors and their single phase is scheduled at the start of the execution of the actor. As might be expected, burst phases scheduling needs the biggest buffers. The buffer must bear a high bandwidth during a short time. While the average bandwidth (throughput) is the same for all the phases scheduling 1152 24 tokens/ms, the burst transmission bandwidth is 1152 7.51 tokens/ms during 7.51ms. The Min-Max LP delivers the best phases scheduling resulting in better buffer capacities estimation. In comparison with the Time Averaged phases scheduling, results are 40% to 50% smaller. We compared results obtained by the Min-Max LP with those obtained by an alternative approach based on periodic schedules [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] (Table II). This last technique offered the best known evaluation of sufficient buffer capacities for the MP3 Playback application (5% to 28% larger than the optimum). Our technique delivers more accurate results then [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] (up to 10%).

The technique proposed in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] is also performed in two steps: a phases scheduling optimization step called Start time postponement and a minimum delay computation step. We performed an experiment to identify if the accuracy of our technique for this example is due to the phases scheduling optimization or the computation of minimum delays. The experiment consists on using the phases scheduling as described in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] and our minimum delays computation and ILP formulation. We obtained the same results as those of the Min-Max LP (see. Table II). This result is not sufficient to derive a conclusion about the accuracy of the phases scheduling technique proposed in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF], that is discussed in the next subsection. However, it can state that our technique to compute minimum delays, and thus buffer capacities, is more accurate. This can be explained as follows. Let us suppose a couple of adjacent actors t, t and a buffer b(a) = (t, t ). The approach of [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] for the computation of the minimum delay uses linear upper bound on token production times (lub-tpt) and linear lower bound on token consumption times (llb-tct). A minimum delay is derived such that the production time of any token according to the lub-tpt is always less or equal to the consumption time of this token according to the llb-tct which guarantees that no token is consumed before it is produced. However, the smoothing effect introduced by these linear bounds may increase the real value of the minimum delay. In fact, the phase that determines the lub-tpt may not be the phase that produces the tokens that are necessary to activate the execution of the phase that determines the llb-tct. In addition, the determination of the lub-tpt needs lcm(ϕ(t), ϕ(t )) steps which may result in excessive run-times. To overcome problematic run-times, authors proposed a conservative heuristic on the computation of this linear bound that ensures no token is consumed before it is produced; however, it may overestimate the real value of the minimum delays and thus sufficient buffer capacities. On the other hand, our analytical technique for the computation of the minimum delay runs in ϕ(t) + ϕ(t ) steps and does not introduce these overestimations in the computation. Thus, it will always deliver as good results as [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] if not better.

B. The Impact of CSDF Modelling 1) Min-Max LP vs. Stuijk et al. [START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclostatic and synchronous dataflow graphs[END_REF]: We used the SDF 3 tool [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF] that implements the exact technique based on model checking [START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclostatic and synchronous dataflow graphs[END_REF] to compute optimal values. Obtained values are up to 25% better that those of the Min-Max LP. The key of optimality of [START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclostatic and synchronous dataflow graphs[END_REF] lies in the self-timed execution used to schedule several occurrences of the repetition vector until a time periodicity is reached. However, as mentioned before, this technique has an exponential worst case complexity (See [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF] for an example of a version of the MP3 Application with exponential run-times). On the other hand, periodic schedule semantic imposes a severe restriction on the periodicity of actors executions. We recall that an execution of an actor refers to the execution of all its phases. One of the major contribution of the Min-Max LP lies in its ability to relax the periodic schedule semantic by scheduling phases of multiple consecutive executions of an actor. The second experiment is devoted to highlight this improvement. We used the Min-Max LP to schedule all the actor phases involved in the repetition vector. The repetition vector of the MP3 Playback application is r = [START_REF] Denolf | Exploiting the expressiveness of cyclo-static dataflow to model multimedia implementations[END_REF][START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclostatic and synchronous dataflow graphs[END_REF]5292,5292]. In terms of executed phases, it is equal to [START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclostatic and synchronous dataflow graphs[END_REF]5292,5292]. We apply a transformation on the previous graph G to get a new CSDFG G r in which the M P 3 r actor has 195 phases. SRC r , AP P r and DAC r have respectively 12, 5292 and 5292 identical phases. The vector w M P 3 r (resp. M P 3 r ) is the concatenation of five vectors w M P 3 (resp. M P 3 ). As a result of this transformation, all the paths in G r have a weight of one and all the actors have the same period, i.e. µ r M P 3 = µ r SRC = µ r AP P = µ r DAC = µ M P 3 • 5 = 120ms. Buffer capacities obtained by applying the Time Averaged phases scheduling to G r actors are identical to those obtained in the first experiment. In fact, we can prove that this phases scheduling results in the same schedule and thus the same buffer capacities evaluation. Therefore, the Time Averaged phases scheduling cannot relax the periodic schedule semantic. When the phases scheduling obtained by the Min-Max LP is applied, the evaluated capacity of buffer B 1 is up to 60% smaller (see. SRC = 5ms). Optimal values are obtained except in the case SRC = 7.5ms for which the overestimation drops to less than 3%. with n t the number of t adjacent buffers. Table IV gives an overview of the Min-Max LP run times.

[39•5, 1•12, 1•5292, 1•5292] = [195,
The ILP (relaxation) runs with a speed of 10 -5 s per buffer and thanks to the actors isolation step, several Min-Max LPs can be executed in parallel to reduce the impact on run time of the overall treatment of phases scheduling.

2) Min-Max LP vs. Wiggers et al. [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF]: This second CSDF modelling for the MP3 Application reveals an issue with the phases scheduling technique proposed in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF]. Evaluated capacity of B 1 is up to 28.5% bigger than the capacity computed with the previous model (see. Table III) and up to 100% bigger than the capacity obtained with the Min-Max LP phases scheduling. This behaviour can be explained as follows. The Start time postponement step delays the producer phases start times starting from a burst phases scheduling. For time-complexity considerations, only the scheduling of the phases that produce the multiples of gcd a tokens are optimized. This is because tokens produced by these phases are potentially tokens that allow to activate the consumer phases. The other phases of the producer are maximally delayed while ensuring that two phases do not overlap. There is no additional mechanism to prevent from delaying too much these phases which may result in too much accumulation of tokens on the backward arc a = (t , t) since this scheduling policy delays their consumption. The number of phases effectively scheduled is then at most ϕ(t) k=1 w a (k)/gcd a . In practice, for the model proposed in the first subsection G, 1152 96 = 12 phases out of 39 phases of the MP3 actor are actually optimized. Surprisingly, in the case of the second model G r , the number of optimized phases does not change, ϕ(M P 3 r ) k=1 w a (k)/gcd a = 5760 480 = 12, while the total number of phases increases to 195. That low ratio of the number of optimized phases to the total number of phases to schedule explains why the accuracy decreases. The accuracy of the phases scheduling technique proposed in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] is subject to numerical values of transfer rates and we can easily imagine irreducible patterns of transfer rates for which the ratio is very low.

C. The Impact on Periodic Schedulability

As mentioned in the introduction, cycles are critical structures and their initialization may limit the maximum throughput achieved by an application. When a critical cycle results from feedback buffers, a solution that initializes sufficiently these buffers should allow to attain the prefixed throughput. That is the case of the H.263 Encoder [START_REF] Kim | System-level specification and cosimulation for multimedia embedded systems[END_REF], [START_REF] Oh | Fractional rate dataflow model and efficient code synthesis for multimedia applications[END_REF], [START_REF] Oh | Efficient cosynthesis from extended dataflow graphs for multimedia applications[END_REF]. The specification imposes that this application starts with only one frame in the feedback buffer between the Motion Compensation actor to the Motion Estimation actor (the other buffers are initially empty). While this specification is met when the application is scheduled with a self-timed execution or a periodic schedule together with the Min-Max LP phases scheduling, two frames are necessary to be able to schedule this application periodically with the phases scheduling proposed in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF]. Derived buffer sizes are also impacted. In addition to couples of arcs that represent buffers, arcs are added to the CSDFG of an application to model mapping decisions on platforms. In [START_REF] Moonen | Evaluation of the throughput computed with a dataflow model -a case study[END_REF], authors provide a detailed CSDFG of a channel equalizer and its mapping on a multiprocessor system. This application is used to reduce multipath distortion in an FM signal. Several tasks are mapped to the same processor and thus dependency arcs are added to model the fixed order of access to this shared resource. These arcs add new cycles for which the number of initial tokens is already fixed. While a solution to attain the prefixed throughput could be found for cycles that result from feedback buffers, we may not always be able to modify the initialization of cycles that result from resource considerations as the obtained graph will correspond to another mapping decisions.

The use of periodic schedule policy to solve the buffer sizes minimization problem in polynomial time comes at the cost of underestimation of the maximum throughput achieved. We analysed the impact of phases scheduling on periodic schedualability of the channel equalizer. The low run-time of our technique allows us to perform a dichotomic search over the value of the throughput to determine the maximum achievable throughput by a periodic schedule with different phases schedulings. The maximum throughput of the selftimed execution is estimated by a Maximum Cycle Mean (MCM) analysis applied to the equivalent SRDFG which has pseudo-polynomial complexity. The throughput is given in terms of the frequency of the input/output actors of the application. Results are presented in Table VI. First, we note that the application is not schedulable periodically with the Time Averaged and the phases scheduling proposed by [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF]. As a result, no buffer capacities can be derived and no guarantee can be given on the achievable throughput by this application using these two phases schedulings. Conversely, the Min-Max LP phases scheduling achieves a maximum throughput of 95.6KHz that is 34.7% from the maximum throughput achieved by a self-timed execution. Note also that the same buffer sizes are obtained for both schedules. This experiment shows that the Min-Max LP not only contributes on better buffer sizes estimation, but it also increases periodic schedualability of applications which allows to build a fast tool to evaluate the achievable performance for different set of mapping decisions.

VIII. CONCLUSION

In this paper we presented a technique to optimize a CSDF actor phases scheduling. The aim is to increase the accuracy of periodic schedule based approaches to solve the throughput constrained buffer sizes minimization problem. We introduced the actors isolation step which enabled the formulation of this problem by a Min-Max Linear Program. We exposed the ability of this Min-Max Linear Program to relax periodic schedule semantic and how this relaxation together with our ILP formulation allow to obtain close to optimal buffer sizes while running in polynomial time. We also exposed the impact of the phases scheduling on periodic schedualability of applications.

Fig. 1 .

 1 Fig. 1. A bounded buffer b(a) of capacity M 0 (a) + M 0 (a ). ϕ(t) = 2 and ϕ(t ) = 1.

B. Linearization of the Sufficient Delay β 1 a

 1 Due to the max k function and gcda in the formula of F , β 1 a is non-linear and discontinuous on M 0 (a). To linearize β 1 a (i.e. max k F ) on M 0 (a), we must first determine the critical phase k = arg max k F (k, M 0 (a)). However, if M 0 (a) is unknown, such in the case of a backward arc or a forward arc of a feedback buffer, it is not always possible to identify a phase k of t such that: ∀M 0 (a) ∈ N, ∀k, F (k, M 0 (a)) ≤ F (k , M 0 (a)

  a ) • gcdagcda) (obvious constraints are not represented). The first remark is that the cost (size) per unit of storage θ has been dropped from the objective function. Indeed, both arcs represent the same buffer and thus have the same cost per unit of storage, i.e. θ(a) = θ(a ). The capacity of b(a) given by M 0 (a) + M 0 (a ) verifies M0(a) + M0(a ) ≥ m0(a) + m0(a ) • gcda + max k∈Sa rem(a, k) + max k∈S a rem(a , k) .

M P 3

 3 = [670, 2700, 18x40, 2700, 18x40]µs. The three other actors have only one phase. The maximum throughput of the application is imposed by the DAC actor that runs periodically every µ DAC = DAC = 1 44100 s. Periods of the other actors can be subsequently derived: µ AP P = µ DAC = 1 44100 s, µ SRC = µ AP P • 441 1 = 10ms and µ M P 3 = µ SRC • 1152 480 = 24ms. The capacity of B 3 equals 2 that is optimal.

Fig. 4 .

 4 Fig. 4. MP3 Playback application [8].

TABLE I BUFFER

 I B 1 CAPACITIES.

	SRC =	10ms	7.5ms	5ms	2.5ms
	Burst Transmission	1824	1632	1536	1440
	Time Averaged [7]	1344	1248	1152	960
	Min-Max LP	960	864	768	672

TABLE II BUFFER

 II CAPACITIES FOR THE BUFFER B 1 .

	SRC =	10ms	7.5ms 5ms	2.5ms
	Paper [3]	1056	928	800	672
	Min-Max LP	960	864	768	672
	[3]+ILP	960	864	768	672

  Experiments show that running time increases linearly with the number of adjacent buffers and quadratically with the number of phases; i.e. the time complexity may be in O(n t ϕ(t) 2 )

		TABLE III
	MIN-MAX LP VS. OPTIMAL[12] VS. [3]
	SRC =	10ms	7.5ms	5ms	2.5ms
	Opt [12] (B1/B2) 960/882 576/921 480/662 480/552
	[3] (B1/B2) 960/882 960/772 960/662 864/552
	MM LP (B1/B2) 960/882 768/772 480/662 480/552
	MM LP Overesti	0.00%	2.87%	0.00%	0.00%

TABLE V H

 V .263 ENCODER BUFFER SIZES[START_REF] Oh | Fractional rate dataflow model and efficient code synthesis for multimedia applications[END_REF] (THROUGHPUT=15FPS).

	Technique	[3]+ILP MMLP+ILP Optimal
	Buffer Sizes (KBytes)	51.25	25.75	25.75

TABLE VI CHANNEL

 VI EQUALIZER[START_REF] Moonen | Evaluation of the throughput computed with a dataflow model -a case study[END_REF] MAXIMUM ACHIEVABLE THROUGHPUT.

	Technique	[7] [3] MM LP MCM
	Maximum Throughput (KHz)	0	0	95.6	146.6
	Buffer Sizes (Words)	-	-	108	108

We believe that, in the growing context of High-Level Synthesis, the increased accuracy together with the low run-time of the technique presented in this paper constitute significant advantages for a use in design exploration.