Adnan Bouakaz

Pascal Fradet

Alain Girault

Symbolic Analysis of Dataflow Graphs (Extended Version)

Keywords: Synchronous dataflow graphs, as soon as possible scheduling, buffer minimization, throughput, latency, symbolic analysis

The synchronous dataflow model is widely used to design embedded streamprocessing applications under strict quality-of-service requirements (e.g., buffering memory, throughput, input-output latency). The required analyses can either be performed at compile time (for design space exploration) or at run-time (for resource management and reconfigurable systems). However, they may cause a huge run-time overhead or make design space exploration unacceptably slow due to their exponential time complexity. In this paper, we argue that symbolic analyses are more appropriate since they express the system performance as a function of parameters (i.e., input and output rates, execution times). Such functions can be quickly evaluated for each different configuration or checked w.r.t. different qualityof-service requirements. We provide symbolic analyses for computing the maximal throughput of acyclic graphs, the minimum required buffers for which as soon as possible scheduling achieves this throughput, and finally the corresponding input-output latency of the graph. The paper first investigates these problems for a simple graph made of a single parametric edge. The results are then extended to general acyclic graphs using linear approximation techniques. We assess the proposed analyses experimentally on both synthetic and real benchmarks.

Analyse Symbolique des Graphes Flots de Données (Version Étendue)

Résumé : Les graphes flots de données sont largement utilisés pour modéliser les applications de traitement de signal et de streaming. Ces modèles permettent de prévoir et garantir les performances (e.g., débit, tailles des buffers, latence) de ces applications. L'analyse de performance peut être effectuée au moment de compilation (exploration de l'espace de conception) ou au moment d'exécution (gestion de ressources, systèmes adaptables). Cependant, ces algorithmes ont souvent une complexité exponentielle, et peuvent donc introduire une pénalité significative au moment d'exécution ou rendre l'exploration de l'espace de conception excessivement lente. Nous montrons dans ce papier que les analyses symboliques sont mieux adaptées dans ce contexte car elles expriment la performance du système par des fonctions en termes de paramètres (i.e., taux de production et de consommation, temps d'exécution). Telles fonctions peuvent être rapidement réévaluées pour tout changement de configuration du système ou utilisées pour vérifier la satisfiabilité des besoins non fonctionnels. Nous proposons des analyses symboliques pour calculer le débit maximale des graphes acycliques, les tailles de buffers minimales requise pour réaliser ce débit, et la latence entrée/sortie. Nous effectuons d'abord une étude analytique et exacte dans le cas d'un graphe avec seulement deux acteurs. En suite, nous étendons ces résultats pour les graphes acycliques. Enfin, nous évaluons notre approche en utilisant des cas d'études réels et des benchmarks synthétiques.

Mots-clés : graphes flots de données, débit, tailles minimales des buffers, latence, analyse symbolique

Introduction

Embedded stream-processing applications become computationally intensive with strict qualityof-service requirements. Many-core platforms are hence required for performance, scalability and energy consumption reasons [START_REF] Kumar | Multimedia Multiprocessor Systems: Analysis, Design and Management[END_REF]. To take advantage of such platforms, design models should express task-level parallelism and be simple enough to allow predictable system design.

Dataflow process networks (DPN) [START_REF] Dennis | First version of a data flow procedure language[END_REF] and Kahn process networks (KPN) [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] allow to explicitly express parallelism and communications where tasks (or actors) are independent and communicate only through channels. Using a dataflow model, concurrency can be implemented without explicit synchronization mechanisms and data races are ruled out by construction. Furthermore, these models are inherently functionally deterministic, i.e., for the same input sequence, the system will always produce the same output results. However, many important properties such as boundedness (i.e., the system can execute in finite memory) and liveness (i.e., no part of the system will deadlock) are undecidable.

The synchronous dataflow (SDF) model [START_REF] Lee | Synchronous data flow[END_REF] is a restriction of DPN and comes with static analyses that guarantee the boundedness and liveness of an application as well as predictable performances (e.g. throughput, latency, memory requirements). For these reasons, it is widely used to design digital signal processing and concurrent real-time streaming applications on manycore platforms.

In response to the increasing complexity of stream-processing systems, many parametric extensions of the SDF model have been proposed (e.g., PSDF [START_REF] Bhattacharya | Parameterized dataflow modeling of DSP systems[END_REF], SPDF [START_REF] Fradet | SPDF: a schedulable parametric data-flow MoC[END_REF], BPDF [START_REF] Bebelis | BPDF: a statically analyzable dataflow model with integer and boolean parameters[END_REF], πSDF [START_REF] Desnos | PiMM: parametrized and interfaced dataflow meta-model for MPSoCs runtime reconfiguration[END_REF], etc.) in which the graph (e.g., its communication rates or channels) may change at run-time.

Performance analyses of SDF graphs are used to check whether non-functional requirements are met. They can be performed both at design time and at run-time. At design time, it is a crucial step in the development of embedded applications. Many decisions and settings of the system need to be explored (e.g. hardware/software partitioning, memory allocation, granularity and different implementations of tasks, processor speeds, etc.) and the best options that satisfy the non-functional requirements can be chosen. At run-time, performance analysis is performed either for resource management or to cope with the dynamic behavior of parametric extensions of SDF.

The most prominent performance constraints of real-time stream-processing systems are throughput, latency and memory. Throughput is a crucial timing constraint of stream-processing systems. For example, a video decoder is supposed to decode a minimum number of frames per second. A throughput-optimal scheduling policy, such as self-timed scheduling, allows the designer to guarantee the timing requirements, and to use dynamic voltage and frequency scaling (DVFS) techniques to reduce energy consumption in case the maximum throughput is larger than the desired quality-of-service [START_REF] Nogues | A DVFS based HEVC decoder for energy-efficient software implementation on embedded processors[END_REF][START_REF] Stuijk | Throughputconstrained DVFS for scenario-aware dataflow graphs[END_REF]. Latency is another important timing constraint that is usually used in the design of real-time control systems. It measures the time delay between the stimulation and response, and hence the reactiveness of the system and its ability to deliver a regular and timely response. Most embedded systems must comply to severe constraints on the size, weight, power and cost. Therefore, minimization of memory requirements is a primordial step in the design of such systems. These three measures (throughput, latency and memory) are often antagonistic. A huge effort have been devoted in the past decades to solve these problems.

In this paper, we focus on self-timed scheduling which produces maximal throughput (with sufficiently large buffers). We propose symbolic analyses of dataflow graphs where communication rates and execution times of actors are parameters. Most non-functional properties of the application can be described as a function of these parameters. By evaluating these functions for specific values of parameters, the properties and performance of specific configurations can be obtained efficiently. We propose three symbolic analyses of acyclic graphs under self-timed scheduling to answer the following questions:

Q1. What is the throughput of the application? Q2. What are the minimum channel sizes that allow the application to achieve its maximum throughput?

Q3. What is the latency of the application under such channel sizes? Although our symbolic analyses may give only approximate (but safe) results, they are very useful in many cases (see Fig. 1) :

1. At early design stages, the SDF model of the application is usually partially specified and design space exploration may require analyzing of a potentially huge number of configurations (path 3 ). Symbolic analyses are a big advantage in this case: formulas are generated only once and simply evaluated for each possible configuration (i.e., set of parameters) (path 4 ). Indeed, exact algorithms for throughput and latency computation may be acceptable at compile-time in practice; however, frequent calls to these algorithms to check a large set of configuration values make design space exploration unacceptably slow.

2. Similarly, non-functional requirements of parametric dataflow models can be expressed symbolically as parametric formulas at compile-time. Then, the requirements can be either checked by evaluating formulas for all potential configurations (path 6b ) or, better, by an analytic proof (path 6a ). For instance, the designer could be interested in ensuring at compile-time that the throughput of the application is never below some given quality-of-service regardless of parameters changes at runtime.

3.

For dynamic models and run-time resource management, appropriate settings have sometimes to be chosen dynamically. Consider, for instance, a parametric application where frequency scaling is used to guarantee a specific throughput and to minimize power consumption. In such case, frequency must be adjusted at each parameter change. Instantiating the graph (path 5 ) and performing a numerical analysis is far too costly at run-time. Consequently, fast analyses, like the evaluation of symbolic formulas, are required (path 6b ).

Inria 4. Finally, even for completely static SDF models, many analyses have an exponential complexity. Indeed, exact algorithms for minimal buffer sizes are too expensive even for small graphs. [START_REF] Moreira | Buffer sizing for rate-optimal single-rate data-flow scheduling revisited[END_REF] shows that this problem is NP-complete for homogeneous SDF (HSDF) graphs. Moreover, SDFto-HSDF conversion may lead to an exponential growth of the size of the graph. Our symbolic analysis (path 2 ) is much more efficient and its approximate solution can also be considered as a starting point to prune the parameter space and hence improve the performance of the exact algorithm.

The article is organized as follows. Section 2 introduces the application model, the scheduling policy, and the needed definitions. Section 3 presents the throughput analysis of acyclic SDF graphs and a new generic result (the duality theorem) required to solve the other questions. We present in Section 4 different symbolic analyses for a single SDF edge A p q --→ B. Section 5 describes linearization techniques for graph A p q --→ B that are used in Sections 6 and 7 to extend the results of Section 4 to general acyclic graphs. The proposed algorithms are evaluated on both synthetic and real benchmarks in Section 8. Finally, we review related work in Section 9 and conclude in Section 10. Proofs of all properties and theorems can be found in the appendix which has the same structure as the paper for a better readability.

Background

In this section, we first introduce the application model and the scheduling policy. Then, we review some useful definitions and properties.

Application model

An SDF graph G = (V, E) consists of a finite set of actors (computation nodes) V and a finite set of edges E that can be seen as unbounded FIFO channels. The execution of a given actor (called firing) starts by consuming data tokens from all its incoming edges (its inputs), computes and finishes by producing data tokens to all its outgoing edges (its outputs). The number of tokens Figure 2: A simple SDF graph consumed (resp. produced) at a given input (resp. output) edge at each firing is its consumption (resp. production) rate. An actor can fire only when all its input edges have enough tokens (i.e., at least the number specified by the corresponding rate). An edge may contain some initial tokens (also called delays). In the following, we denote the execution time of an actor X by t X . For instance, Fig. 2 shows an SDF graph with two actors A and B, with execution times t A = 20 and t B = 7 respectively. The production and consumption rates of channel A → B are 8 and 5 respectively. This edge carries one initial token (represented by the black dot).

The state of a dataflow graph is the vector of the number of tokens present at each edge (i.e., buffered in each FIFO channel). Each edge carries zero or more tokens at any moment. The initial state of a graph is specified by the number of initial tokens on its edges. The state of the graph of Fig. 2 is represented by the vector [i AB = 1].

An iteration of an SDF graph is a non empty sequence of firings that returns the graph to its initial state. For the graph in Fig. 2, firing actor A five times (producing 40 tokens) and actor B eight times (consuming 40 tokens) forms an iteration. The repetition vector z

= [z A =5, z B =8]
indicates the number of firings of actors per iteration. If such a vector exists, then the graph is said to be consistent [START_REF] Lee | Synchronous data flow[END_REF]. We write z X the number of firings of actor X in the iteration. The repetition vector is obtained by solving a system of balance equations. Each edge A p q --→ B is associated with the balance equation z A p = z B q, which states that all produced tokens during an iteration must be consumed within the same iteration.

In this paper, we study only consistent acyclic SDF graphs with initially empty channels. Inconsistent graphs are of less importance since they cannot be implemented with bounded memory without deadlocking.

Homogeneous SDF (HSDF) is a restriction of SDF where all the production and consumption rates are equal to 1. HSDF graphs are particularly useful because (i ) their throughput can be computed as the inverse of the maximal cycle mean (MCM) of the graph; and, (ii ) any consistent SDF graph can be converted into an HSDF graph. The cycle mean of a cycle is equal to the sum of execution times of the actors in the cycle divided by the number of delays (i.e., initial tokens) in the channels of this cycle. This provides a way to compute the throughput of any SDF graph. There are two drawbacks in this approach: first, the translation from SDF to HSDF may lead to an exponential increase of the number of nodes; second, partially specified or parametric SDF graphs cannot be converted into HSDF.

Scheduling policy

In this paper, we focus on as soon as possible (ASAP) scheduling of consistent graphs without auto-concurrency (i.e., two firings of the same actor cannot overlap). In such self-timed executions [START_REF] Sriram | Embedded multiprocessors: scheduling and synchronization[END_REF], an actor fires as soon as it becomes idle (no auto-concurrency) and has enough tokens on its input channels. We assume that there are sufficient processing units, e.g., there are as many processors as actors or all actors are implemented in hardware. ASAP scheduling allows the graph to reach its maximal throughput. Such schedules are naturally pipelined and composed of a prologue followed by a steady state that repeats infinitely. Fig. 3 shows an ASAP schedule where thick broken lines represent the iterations boundaries. --→ B with t A =15 and t B =8 Fig. 4 shows how to make the absence of auto-concurrency explicit in an SDF graph by adding self-edges with rates equal to 1 and one initial token. A firing of actor A will consume the unique token in its self-edge, preventing any other firing of A until another token is produced to the self-edge at the end of the current firing. Disabling auto-concurrency is mandatory for stateful actors to ensure proper state update.

In the SDF model, channels are unbounded. However, the size of a channel A p q --→ B can be constrained to d tokens by adding a backward channel B q p --→ A with d initial tokens, as shown in Fig. 4. This modeling, assumed in most works, enforces that an actor can start firing only if there is enough space on its output channels. Moreover, the empty space is made available not at Inria Figure 4: The SDF graph of Fig. 2 with channel size constraint and auto-concurrency disabled the beginning of the firing of the consumer but when it produces the tokens representing buffer places. One could imagine a less conservative modeling where the consumer makes the empty space available just after consumption, and the producer checks whether there is enough empty space only at the end of its firing. This is illustrated in Fig. 5 where an actor X is represented by different actors for reading inputs (X r ), computing (X c ) and writing results (X w ). For instance, A w produces 8 tokens (and checks for 8 places) only after the computation (A c ); B r frees 5 buffer places before the computation (B c ) starts. Note that only actors representing computation have a non-null execution time. Actually, the graph in Fig. 2 requires a minimum buffer size of 20 Figure 5: Less conservative modeling of channel size constraint on the graph of Fig. 2 to achieve the maximal throughput when using the first modeling technique (Fig. 4) whereas it only needs 12 when using the second (Fig. 5). This shows that different modeling techniques may lead to different symbolic formulas. However, the approach proposed in this paper for symbolic computation of buffer sizes can be adapted to any modeling technique.

Definitions

The multi-iteration latency L G (n) of the first n iterations of a graph G is equal to the finish time of the last firing of its first n iterations (assuming timing starts at the very first firing).

The period P G of the execution of a graph G is the average length of an iteration and is formally defined as

P G = lim n→∞ L G (n) n (1)
The throughput T G of a graph G is the number of iterations per unit of time, hence:

T G = 1/P G (2)
Eq.( 1) and Eq.( 2) show the relation between throughput and multi-iteration latency. This relation is particularly useful in the case of parametric dynamic dataflow models where parameter reconfigurations are frequent. Hence, if a given configuration lasts only during m iterations, then m/L G (m) gives the achievable throughput for the current configuration. The designer can use this information, for instance, to reduce the frequency of processors and save energy as long as the desired quality-of-service is guaranteed.

The input-output latency G (n) of the n th iteration of a graph G is equal to the time between the start time of the first firing and the finish time of the last firing of the n th iteration. The definition given in [START_REF] Ghamarian | Latency minimization for synchronous data flow graphs[END_REF] is slightly different but in our context (graphs with initially empty channels) the two definitions are equivalent.

The input-output latency of the complete execution G is defined as the maximal latency over all iterations:

G = max n=1..∞ G (n) (3)
Input-output latency is particularly useful in case of real-time control systems since it specifies the maximum delay between sampling data from sensors and sending control commands to the actuators.

For a channel A p q --→ B with d initial tokens, the i th firing of B (denoted B i ) is enabled if and only if the number of produced tokens is larger than i q. Hence, B has to wait for the j th firing of A (denoted A j ) such that j p + d ≥ iq. The data-dependency between A and B is formalized by the following equation.

B i ≥ A j with j = i q -d p (4)
The ceiling function makes symbolic manipulations difficult. We propose in Section 4 a new characterization that is more intuitive and suitable to reason about buffer sizes and latency.

Throughput and Duality

In this section, we first determine the exact maximal throughput for acyclic SDF graphs (Q1). Then, we introduce the notion of duality and present a proerty on dual graphs that is used to address the minimum buffer sizes and latency questions.

Property 3.1 (Throughput). The maximal throughput of an acyclic SDF graph G=(V, E) is equal to

T G = 1 max A∈V {z A t A } (5)
Hence, the minimal period is

P G = max A∈V {z A t A }.
We say that actor A imposes a higher load than actor B when z A t A > z B t B . The throughput and period of an acyclic graph are therefore defined by the actor which has the highest load; i.e., actor argmax A∈V {z A t A }. This implies that this actor never gets idle once the execution enters the steady state. Definition 3.1. The dual of an SDF graph G, denoted G -1 , is obtained by reversing all edges of G. Theorem 3.1 (Duality theorem). Let G be any (cyclic or not) live SDF graph and G -1 be its dual, then

T G = T G -1 and ∀i. L G (i) = L G -1 (i).
Fig. 6 illustrates the duality theorem with the SDF graph G a of Fig. 4. The latency of the first iteration of the ASAP execution of that graph is equal to the latency of the first iteration of its dual i.e., L Ga (1) = L Ga -1 (1). Note 3.1. The ALAP (As Late As Possible) schedule of graph G is identical to the reversed ASAP schedule of its dual G -1 . In other terms, the ALAP schedule of G in the time interval [0, n] is identical to the ASAP schedule of G -1 starting at n and ending at 0. This provides a second method to prove the first part of the duality theorem; i.e., T G = T G -1 . Indeed, [START_REF] Geilen | Synchronous dataflow scenarios[END_REF] states that both the ASAP schedule and the ALAP schedule of an SDF graph have the same throughput.

Inria

We use the transformation of a graph to its dual as well as the associated theorem at several occasions during the analysis of minimal buffer sizes and latency.

The parametric graph

A p q --→ B
This section focuses on the simplest parameric acyclic SDF graph made of a single edge: G = A p q --→ B. We provide exact symbolic formulas for minimum buffer size and latency questions. The graph G is parametrized by the production and consumption rates p, q ∈ N + as well as the execution times t A , t B ∈ R + . This section shows that the symbolic analysis, even for such simple graphs, is quite involved.

The balance equation z A p = z B q entails that the repetition vector of this graph is:

[z A = q/ gcd(p, q), z B = p/ gcd(p, q)] and, according to Property 3.1, its throughput is:

T G = 1 max(z A t A , z B t B ) (6)

Enabling patterns

We introduce enabling patterns, which characterize the data-dependency between a producer and a consumer. Compared to Eq. ( 4), they are more intuitive and suitable to the reasoning about buffer sizes and latency. Enabling patterns between the producer A and consumer B are defined by the following grammar:

P ::= A i B j | [P ] x=1..k | P 1 ; P 2
where i, j, k evaluate to positive integers.

An enabling pattern P is either a basic pattern (A i B j ), a repetition for k times ([P ] x=1..k ), or a sequence of enabling patterns P 1 ; P 2 , The expressions i, j or k are arithmetic expressions made of integers, parameters or pattern variables defined by enclosing repetition patterns.

The semantics of an enabling pattern between actors A and B is defined w.r.t. two counters a and b representing the number of completed firings of A and B (initially 0). The pattern A i B j ; P w.r.t. (a, b) means that:

• a firings of A have produced enough tokens to fire actor B b times and not more;

• then, if A is not fired at least i times more, then B cannot be fired; otherwise B can be fired j times and not more;

• the subsequent pattern P is considered with the new values (a + i, b + j).

Formally i ≥ 1 j ≥ 1 ap ≥ bq (a + i -1)p < (b + 1)q (b + j)q ≤ (a + i)p < (b + j + 1)q (a, b, A i B j ) = (a + i, b + j) A repetition [P ] x=1.
.k is a sequence of k patterns P . The pattern [P ] x=1..k is also written [P ] k if the pattern variable x is not used in P . A correct enabling pattern describes an entire iteration, that is, at the end of the pattern, we should have a = z A and b = z B .

For example, the enabling pattern of A --→ B is A 2 B ; i.e., after every two firings of actor A, one firing of B is enabled (B 1 is written B). The enabling pattern of A --→ B is:

A B ; A B 2 ; A B ; [A B 2 ] 2
which is illustrated in Fig. 7. This pattern can also be written as the factorized pattern:

A B ; [A B 2 ] i i=1••2
This factorized representation is particularly useful when the length and shape of enabling patterns depend on parameters. Depending on the production and consumption rates p and q, there are six possible enabling patterns.

--→ B

We now use enabling patterns to compute the minimum size of the buffer A p q --→ B (denoted θ A,B ) such that the ASAP execution achieves the maximal throughput (given by Eq. ( 6)) or, equivalently, the minimal period. The buffer size is modeled by adding a backward edge with θ A,B initial tokens. We distinguish two cases:

Inria Case A. p ≥ q Let p = kq + r with 0 ≤ r < q Case A.1. r = 0 A B k Case A.2. q ≤ 2r A B k ; A B k+1 αj j=1•• q-r gcd(p,q) Case A.3. q > 2r A B k βj ; A B k+1 j=1•• r gcd(p,q)
where αj = jr q-r -(j-1)r q-r and βj = jq r -(j-1)q r -1.

Case B. p < q

Let q = kp + r with 0 ≤ r < p Case B.1. r = 0

A k B Case B.2. p ≥ 2r A k+1 B ; A k B γj j=1•• r gcd(p,q) Case B.3. p < 2r A k+1 B λj ; A k B j=1•• p-r gcd(p,q)
where γj = jp r -(j-1)p r -1

and λj = jr p-r -(j-1)r p-r

.

Figure 8: Enabling patterns.

• Case z A t A ≥ z B t B (i.e., qt A ≥ pt B ): Actor A has the highest load and should fire consecutively for maximal throughput. Let δ j be the minimum number of initial tokens in the backward edge (representing the buffer size) such that the j th firing of A can occur immediately after the (j -1) th firing of A. By definition of θ A,B , we have θ A,B = max j δ j . Let x j denote the number of firings of B that have finished by the start of the j th firing of A. Hence, δ j = jp -x j q and θ A,B = max

j (jp -x j q) (7)
The main difficulty when solving symbolically Eq. ( 7) is to identify an analytic formula for sequence (x j ). Enabling patterns are the key to solve this problem. A trivial case is (A.1) where p = kq and the enabling pattern is A B k . In order to perform the first two firings of A consecutively, the backward edge should have at least 2p tokens. Futhermore, since qt A ≥ kqt B (hence t A ≥ kt B ), the k firings of B complete before the third firing of A which still needs 2p initial tokens (i.e., δ 3 = 2p) in order to fire again immediately. Hence, the minimum buffer size is 2p. However, unlike sequence (x j ), enabling patterns are time-independent. Thus, when considering execution times t A and t B , three cases will emerge (see I., II. and III. in Fig. 9); each one has to be solved w.r.t. all possible enabling patterns. The three cases should be read as (I) else (II) otherwise (III). These cases are described in the appendix (Section B.2). For instance, case (I) corresponds to the case where at any given enabling point (i.e., any in the enabling pattern), all newly enabled firings of B complete their execution before the next enabling point. Property 4.2. If z A t A ≥ z B t B , the minimum buffer sizes of A p q --→ B for maximal throughput are given by the symbolic formulas of Fig. 9.

• Case z A t A < z B t B (i.e., qt A < pt B ): Actor B has the highest load and should fire consecutively for maximal throughput. However, in general all firings of B cannot be consecutive since initially,

Case I. Case I.1. A.1 ∨ ((A.2 ∨ A.3) ∧ (t A ≥ (k + 1)t B )) θ A,B = 2p + q -gcd(p, q) (8) Case I.2. B.1 ∨ ((B.2 ∨ B.3) ∧ (t B ≤ kt A )) θ A,B = p + q -gcd(p, q) + t B t A p (9)
Case II.

Case II.1.

(A.2 ∧ r ≥ r q-r r q-r +1 t B ) ∨ (A.3 ∧ r ≥ 1 q r t B ) where r = t A -kt B θ A,B = 2p + q -gcd(p, q) + t B -r r r ( 10
) Case II.2. (B.2 ∧ r ≤ 1 p r t A ) ∨ (B.3 ∧ r ≤ r p-r r p-r +1 t A ) where r = t B -kt A θ A,B = p + 2q -gcd(p, q) + r t A -r (p -r) (11)
Case III. Case III.1. A.2

θ A,B = 2p + q + r -gcd(p, q) + n-1 max j=1 (jr mod (q -r)) (12)
where n is the smallest positive integer such that nr there are no tokens to be consumed. The previous approach can still be followed using the duality theorem. Since the graph G and its dual G -1 have the same throughput, we can apply the former reasoning on G -1 where B is the producer and has the highest load. Then, Property 4.3 will be used.

Property 4.3. If θ B,A is the minimum buffer size that allows the ASAP execution of G -1 to achieve its maximal throughput, then the minimal buffer size θ A,B for G is such that θ A,B = θ B,A .

θ u A,B = 2(p + q -gcd(p, q)) ( 13
)
This bound is also tight, in the sense that for all p, q, there exist t A and t B such that θ A,B as given in Fig. 9 --→ B contains d initial tokens, then the minimum buffer size θ A,B that allows the maximum throughput is

θ A,B = max{0, θ A,B -d + d mod gcd(p, q)} ( 14
)
with θ A,B as defined in Fig. 9.

Multi-iteration latency of

A p q --→ B
In this section, we derive analytical formulas for the multi-iteration latency of the first n iterations (i.e. L G (n)) of graph A p q --→ B. Since we use the multi-iteration latency to approximate the maximal achievable throughput, we will suppose that buffers are unbounded. There are two cases depending on whether A or B imposes the highest load.

• Case z A t A ≥ z B t B , i.e., A imposes a higher load than B. As illustrated in Fig. 10, actor A never gets idle and P G = z A t A . Therefore, we can put

L G (n) = nP G + ∆ A,B (15)
such that ∆ A,B is the remaining execution time for actor B after actor A has finished its firings of the n th iteration (∆ A,B is constant over all iterations). The value of ∆ A,B is given by Property 4.5.

Eq. [START_REF] Lee | Synchronous data flow[END_REF] shows that the multi-iteration latency will under-approximate the maximal throughput by only a small amount that decreases with the value of n; i.e., • Case z A t A < z B t B , i.e., B imposes a higher load than A. As illustrated in Fig. 12, actor B never gets idle in the steady state. However, in general all firings of B cannot be consecutive since initially, there are no tokens on the forward edge A → B. Note that ∆ A,B is not constant over all iterations and diverges to infinity if the buffer is supposed unbounded. A simpler way to compute L G (n) is to use the duality theorem. We have

TG = n L G (n) = n nP G + ∆ A,B ≤ T G = 1 P G Figure 10: Multi-iteration latency L G (2), case z A t A ≥ z B t B (p = 5, q = 3, t A = 14, t B = 8).
L G (n) = L G -1 (n). Since the producer B in graph G -1 imposes the highest load, we have L G -1 (n) = nP G -1 + ∆ B,A
where ∆ B,A can be easily computed using Property 4.5.

Case I.

∆ A,B = p q t B (16)
Case II. Case II.1.

∆ A,B = t A + r q -r ((k + 1)t B -t A ) (17)
Case II.2.

∆ A,B = t B + p -r r (t B -kt A ) (18)
Case III. Case III.1. Let r = t A -kt B and n = q-r gcd(p,q)

∆ A,B = t A + r + t B r -qr gcd(p, q) + (t B -r ) n-1 max j=0 jr t B -r - jr q -r (19)

Input-output latency of A p q

--→ B

In this section, we derive analytical formulas for the input-output latency G (n) of graph A p q --→ B. There are two cases depending on which A or B imposes the highest load.

• Case A imposes a higher load than B: The input-output latency is equal to the finish time of the n th iteration, which is equal to L G (n) = nP G + ∆ A,B (Eq. ( 15)), minus the start time of the first firing of A in the n th iteration. This start time is equal to (n -1)P G since A never gets idle. Therefore, we have

G (n) = L G (n) -(n -1)P G = P G + ∆ A,B (20)
Hence, G = P G + ∆ A,B = L G (1); i.e., the first iteration results in the maximum delay between sampling inputs and sending results.

• Case B imposes a higher load than A:

We have G (n) = L G (n) -(n -1)z A t A if
the buffer is unbounded. In this case, the input-output latency diverges with n. However, in practice the Inria buffer is bounded. The buffer size will impact the input-output latency since the firings of A will not be consecutive. As in the previous case, we will assume that the buffer size is larger than θ A,B to allow the maximal throughput (i.e., B runs consecutively in the steady state). We propose an over-approximation of the maximum input-output latency, which uses a linearization technique presented in Section 5.2.

5 Linearization of A p q --→ B

In order to use the results of the previous section to obtain approximate analyses of general acyclic dataflow graphs, we make use of a technique that linearizes the firings of actors. We propose a forward linearization (i.e., linearizing the firings of the consumer) and a backward linearization (i.e., linearizing the firings of the producer).

Forward linearization of graph

A p q --→ B Consider the graph G = A p q
--→ B, where, as illustrated in Fig. 13, the firings of A are consecutive while those of B are neither consecutive nor uniformly distributed. Let f B (i) denote the finish time of the i th firing of actor B. In order to derive formulas that can be composed (e.g., to deal with a chain of actors), we transform B into two fictive actors B u (upper bound) and B (lower bound) that fire consecutively as many times as B and such that

∀i. f B (i) ≤ f B (i) ≤ f B u (i)
Actor B x (i.e., B u or B ) has a starting time t 0 B x and an execution time t B x , and since it fires

consecutively f B x (i) = it B x + t 0 B x .
In the following, we will present tight linearizations, in the sense that ∃i. f B (i) = f B x (i). For instance, we can see in Fig. 13 that both the 5th firings of B and B s finish at the same time.

Upper bound linearization

We present two linearization methods, Push and Stretch, illustrated in Fig. 13. Push considers the actor B p which is obtained by pushing all firings of B to the right end to get rid of all the gaps. This method is suitable only for a finite number of iterations, say n. The execution time remains the same (i.e., t B p = t B ) but the starting time of the consecutive firings is equal to the multi-iteration latency L G (n) minus the execution time of nz B firings: The second method, Stretch, considers the actor B s which is obtained by increasing the execution time of B in order to fill the gaps over an infinite execution. We distinguish two cases:

t 0 B p = L G (n) -nz B t B .
• Case z A t A ≥ z B t B :
This case is illustrated in Fig. 13. We have t B s = qt A p , i.e., both A and B s have the same load. The starting time t 0 B s is computed as follows. We have

f B s (i) = it B s + t 0 B s ≥ f B (i). Hence, t 0 B s = max i (f B (i) -it B s ).
As in the case of the minimum buffer size problem, we have to consider the three cases (I), (II) and (III) and all six enabling patterns. It can be shown (see appendix C.1) that t 0 B s = t A + t B -gcd(p,q) p t A . We conclude that:

∀i. f B s (i) = qt A p i + t A + t B - gcd(p, q) p t A (21)
Method Stretch may advance the starting of some firings (e.g., the 2 th firing of B s in Fig. 13), but always postpone their endings.

• Case z A t A < z B t B : In this case, methods Push and Stretch are identical. The firings of B are consecutive in the steady state. Therefore, we can take t B s = t B p = t B and, using the duality theorem, we have

L G (n) = L G -1 (n) = nz B t B + ∆ B,A and we can take t 0 B s = ∆ B,A
, where ∆ B,A is computed on the dual graph (see Property 4.5).

Lower bound linearization

For lower bound linearization, we use the Stretch method; i.e., the execution time of B is increased in order to fill the gaps over an infinite execution such that ∀i.

f B (i) = it B +t 0 B ≤ f B (i).
Again, we distinguish two cases: Case A. p ≥ q Let p = kq + r with 0 ≤ r < q

• Case z A t A ≥ z B t B : We have t B = qt A p and t 0 B = min i (f B (i) -it B ).
t 0 B = kt B + min t B , rt A p (22) Case B. p < q Let q = kp + r with 0 ≤ r < p and σ = pt B -qt A Case I. t 0 B = t B (23)
Cases II + III.

t 0 B = t B + p -r p t A + p r σ p + min -σ p , r -(p mod r) p t A (24)
Figure 14: Linear lower bound linearization in case

z A t A ≥ z B t B . • Case z A t A < z B t B :
This case is equivalent to a push to the left. Hence, t B = t B and t 0 B is equal to the start time of the first firing of B.

Thanks to this linearizations, a chain

A p q ---→ B p q
----→ C can be treated by first scheduling the subgraph A p q --→ B, then linearizing the firings of B if they are not consecutive, then scheduling Inria the subgraph B x p q ---→ C, and finally combining the two schedules. Thanks to this approach, we can compute a safe upper bound of the minimum buffer sizes for a chain A → B → C, instead of trying to combine the formulas of Fig. 9, and hence solving very complicated combinations.

Backward linearization of graph

A p q --→ B
In this section, we propose a backward lower bound linearization of the producer, which is needed to compute the input-output latency of chains. The previous section describes a forward lower bound linearization; i.e., a transformation of the firings of the consumer and not those of the producer.

If A imposes a higher load than B, then the backward linearization is trivial since the firings of A are already consecutive, assuming that the buffer size allows the throughput to be maximal.

Suppose now that B imposes a higher load than A and that the channel is large enough to allow B to run consecutively in the steady state (i.e., the ASAP execution achieves its maximal throughput). A safe buffer size will be θ A,B as described in Section 4.2.

Let s X (i) denote the start time of the i th firing of an actor X. We want to transform actor A into a fictive actor A with consecutive firings such that ∀i. s A (i) ≤ s A (i); i.e., start times are moved backward. This constraint is sufficient in this case to guarantee an over-approximation of the input-output latency. However, if channel A → B is a part of a chain (say Z → A → B), then we also need to ensure that the finish times of A are not postponed; otherwise, this may impact the schedule of graph Z → A by delaying the firings of Z (due to the buffer size constraint) and hence under-approximating the input-output latency. Therefore, the required linearization constraint is rather

∀i.f A (i) ≤ f A (i) Property 5.1. If z A t A < z B t B ,

then a valid backward lower bound linearization of A is given by

f A (i) = it A + (t 0 A + s B (j 0 + 1) -i 0 t A ) (25)
where (i 0 , j 0 ) is a solution of equation i 0 p -j 0 q = d (d is the buffer size), and t A and t 0 A are the results of the forward lower bound linearization of A in the dual graph G -1 .

We show now how to use this property to compute an upper bound of the input-output latency of graph A p q --→ B in case B imposes a higher load than A. Fig. 15 illustrates the ASAP execution of the graph G = A 8 5

--→ B such that t A = 5, t B = 6 and the buffer size d is equal to 22. Actor A represents the backward lower bound linearization of A.

Let ρ denote the length of the interval between the finish time of the firings of B after n iterations, i.e., L G (n), and the finish time of the firings of A also after n iterations, i.e., f

A (nz A ). So, ρ = L G (n) -f A (nz A )
which is constant over the values of n. The maximum input-output latency can therefore be given by

ˆ G = P G + ρ (26) Since L G (n) = nP G + ∆ B,A , f A (nz A ) = nP G + (t 0 A + s B (j 0 + 1) -i 0 t A ) and s B (j 0 + 1) = j 0 t B + ∆ B,A , we have ρ = i 0 t A -j 0 t B -t 0 A = d q t B -t 0 A (27) RR n°8742

Buffer Sizing for Acyclic graphs

Exact symbolic buffer sizing for a single edge graph is already so complex that it seems to be out of reach for arbitrary (even acyclic) graphs. This section shows how to use the previous results to obtain approximate analyses for the minimum buffer sizes of general acyclic dataflow graphs in order to reach the maximal throughput. To achieve this, we make use of the forward linearization techniques. We first present formulas to compute safe upper bounds for general acyclic graphs, then we present a heuristic that improves this bound for chains, trees (a DAG with only forks), and intrees (a DAG with only joins). These kinds of graphs, especially chains, are common in streaming applications. Finally, we present the exact numerical analysis that is used later to evaluate our approximate analyses.

Safe upper bounds

We first present a negative result. Let G be an acyclic graph and let the size of each channel A p q --→ B be equal to θ A,B as defined in Section 4.2. These buffer sizes do not always permit maximal throughput. They do however allow maximal throughput in some specific cases described in the next section. A simple counterexample is the graph

G b = A 3 4 --→ B 4 2
--→ C with t A = 16, t B = 11 and t C = 12. The repetition vector is z = [START_REF] Bhattacharya | Parameterized dataflow modeling of DSP systems[END_REF][START_REF] Bempelis | Boolean Parametric Data Flow: Modeling -Analysis -Implementation[END_REF][START_REF] Damavandpeyma | Parametric throughput analysis of scenario-aware dataflow graphs[END_REF]. Actor C imposes the higher load, hence the minimal period of this graph is P G b = z C t C = 72. We have θ A,B = 9 and θ B,C = 6. Locally, these buffer sizes allow the producers to run freely without any constraint from the consumers. However, when they are put together (i.e., the global execution), the maximal throughput, where actor C fires consecutively, cannot be achieved (see Fig. 16). The computation of θ B,C assumes that the execution time of actor B is t B = 11. However, as illustrated in Fig. 16, there are gaps between the firings of B due to the data-dependency A → B. The global execution proceeds as if the execution times of B were sometimes longer than 11. --→ B in G is at least θ u A,B = 2(p + q -gcd(p, q)), then the ASAP execution of the graph achieves the maximal throughput. Inria Note 6.1. Since the minimum buffer sizes below which the graph is definitely not live are equal to p + q -gcd(p, q) [1], Property 6.1 provides a first solution that is less than twice the exact one. For parametric dataflow models, the upper bound θ u A,B can actually be reached for some configurations. However, if the system supports dynamic reallocation of memory, it is still useful to evaluate the minimal buffer sizes in order to adjust the buffers sizes after each configuration change.

Unfortunately, Property 6.1 does not hold for general acyclic graphs that contain undirected cycles. A counterexample is the graph

G c = {A 4 3 ---→ B 3 8 ---→ D, A 1 3 ---→ C 3 2
---→ D} with t A = 4, t B = 3, t C = 12 and t D = 8. The repetition vector is z = [6, 8, 2, 3] and all actors impose the same load (i.e., ∀X. z X t X = 24). The ASAP execution when all buffer sizes are equal to their upper bound 2(p + q -gcd(p, q)) is shown in Fig. 17. Actor A does not fire consecutively so the throughput is not maximal. The reason is that the chain A C D imposes an earliest start time for D that is after the earliest start time imposed by the chain A B D. More precisely, the first firing of actor D is delayed by actor C (i.e., by the second chain), which delays the 7 th firing of B, which in turn delays the 8 th firing of A. Let f u D,1 (resp. f u D,2 ) denote the linear upper bound on the finish times of actor D following the first (resp. second) chain. We have

f u D,1 (i) = 8i + 16 and f u D,2 (i) = 8i + 28, hence f u D,2 (i) > f u D,1 (i).
In order to prevent the second chain A → C → D from impacting the schedule of the first chain A → B → D, we must increase the size of buffer B D so that B can fire without being blocked during f u D,2 (i)-f u D,1 (i) = 28-16 time units. Since B produces 3 tokens per firing and t B = 3, the size of the B D buffer must be increased by 28-16 3 × 3 = 12.

Figure 17: ASAP execution of G c

In the general case, Eq.(60) gives the value of s An for a chain A 1 A 2 . . . A n where all actors have the same load. If the actors do not have the same load, we consider, as in the proof of Property 6.1, the chain where all actors have the same load i.e., the maximum load of the original chain.

Property 6.2. Let two different chains from A 1 to A n such that f A u n ,1 (i) = t An i + s 1 , f A u n ,2 (i) = t An i + s 2 and s 1 < s 2 .
To prevent the second chain from disturbing the schedule of the first one, it suffices to increase the size of the last channel

A n-1 p q --→ A n of the first chain by ζ with ζ = s 2 -s 1 t An-1 p (28)
This approach can be extended to deal with any acyclic graph with undirected cycles as shown in Algorithm 1. Such an approach is safe but not always needed (e.g., when the predecessors of a node do not have common ancestors). Note 6.2. The value of ζ, like the value of θ u A,B , does not actually depend on execution times. Indeed, Eq. (60) shows that s 1 and s 2 can be expressed as z An t An k 1 and z An t An k 2 . Since z An t An = z An-1 t An-1 , term s2-s1 t A n-1 can be expressed as z An-1 (k 2 -k 1 ), which does not depend on execution times.

ALGORITHM 1: Safe upper bounds for graphs with undirected cycles Input: SDF graph with undirected cycles, all actors impose the same load. Output: Safe buffer sizes. L: list of actors in a topological order;

while L = ∅ do B = dequeue(L); pred(B) = incoming-edges(B); if pred(B) = ∅ then sB = 0 ; else for each edge A p q --→ B ∈ pred(B) do sB,A = sA + t B q (p + q -gcd(p, q)) ; sB = max A p q --→B∈pred(B) (sB,A); for each edge A p q --→ B ∈ pred(B) do size(A p q --→ B) = θ u A,B + s B -s A t A n-1 p ; Note 6.3.
There is a second more precise but more complicated method to compute the size of the last channel A n-1 p q --→ A n in Property 6.2. Consider a single edge graph A n-1 p q --→ A n where A n-1 and A n impose the same load. Hence, θ An-1,An = 2(p + q -gcd(p, q)) is the minimum buffer size that allows the ASAP execution to achieve the maximal throughput. As indicated in the proof of Property 6.1, the same size allows both actors to fire consecutively once they start firing, as long as the start time of A n is less than or equal to s An = t An q (p + q -gcd(p, q)). Let θ An-1,An (x) denote the minimum buffer size for a maximal throughput where firings of A n can start only after x unit of times. We are interested in computing θ An-1,An (s An + (s 2 -s 1 )), i.e., the impact of the extra delay on the buffer size. Following the same approach used to deduce Eq. (59), we have

θ An-1,An (s An + (s 2 -s 1 )) = max j jp -q jp -(2p + q -gcd(p, q)) q - s 2 -s 1 t An 0
This can be over-approximated by 2p + 2q -gcd(p, q) + (s2-s1)p

t A n-1
. So, the value of ζ in this case is equal to (s2-s1)p

t A n-1
+ gcd(p, q). Note 6.4. There are different ways to solve the problem in Property 6.2. If s 2 > s 1 , then the start time of actor A n in the combined schedule of the two chains is equal to max(s 2 , s 1 ) = s 2 . Suppose that, compared to the linear schedule of the first chain

A 1 p1 q1 ----→ A 2 → • • • pn-1 qn-1 --------→ A n , each actor A i ∈ {A 2 , . . . , A n-1 } is delayed in the combined schedule by Y Ai ∈ R ≥0 such that Y Ai ≤ s 2 -s 1 .
In order that A 1 does not wait for the extra delay Y A2 of A 2 , the size of the first buffer could be increased by

ζ 1 = Y A 2 t A 1 p 1 (i.e., the size is equal to θ u A1,A2 + ζ 1 )
. Similarly, in order that A 2 does not wait for the extra delay Y A3 of A 3 , the size of the second buffer could be increased by

ζ 2 = Y A 3 t A 2 p 2 .
Finally, in order that A n-1 does not wait for the extra delay (s 1 -s 1 ) -Y Ai , the size of the last buffer could be increased by

ζ n-1 = (s1-s1)-Y A i t A n-1
p n-1 . So, assuming that all tokens have the same size, we need to solve the following optimization program:

Min ζ 1 + ζ 2 + . . . + ζ n-1 Subject to Y Ai ≥ 0 ∧ Y Ai ≤ s 2 -s 1

Inria

For graph G c , we have s 2 -s 1 = 12, and hence,

ζ 1 = Y B 4 4 and ζ 2 = 12-Y B 3 3. So, the optimization problem consists in finding 0 ≤ Y B ≤ 12 that minimizes Y B 4 4 -Y B 3 3 + 12.

Improving the upper bounds

In this section, we improve the minimum buffer sizes for chains, trees, and in-trees, starting with chains. We say that a chain is monotone if each actor imposes a higher load than its successor or if each actor imposes a lower load than its successor.

Definition 6.1. The chain

A 1 → • • • → A n is monotone if and only if (∀i. z Ai t Ai ≥ z Ai+1 t Ai+1 ) ∨ (∀i. z Ai t Ai ≤ z Ai+1 t Ai+1 )
Let θ Ai,Ai+1 be the size of the buffer between A i and A i+1 as computed in Section 4.2. This size allows the single edge graph A i pi qi ---→ A i+1 to reach its maximal throughput.

Property 6.3. A monotone chain A 1 → • • • → A n
where the size of each buffer A i → A i+1 is at least θ Ai,Ai+1 achieves its maximal throughput.

Note that Property 6.3 is only a sufficient condition simply because θ Ai,Ai+1 allows actor A i to fire consecutively. However, it is not a necessary condition to achieve the maximal throughput. E.g., let

G d = A 1 2 2 ---→ A 2 4 3
---→ A 3 such that t A1 = 28, t A2 = 20 and t A3 = 15. We have θ A2,A3 = 12, but the minimum size of channel A 2 → A 3 is actually 9. Indeed, as illustrated in Fig. 18, even if this size delays firings of A 2 (see the 4 th firing), the introduced delay does not prohibit A 1 from firing consecutively. Property 6.3 also holds for non monotone chains made of an ascending sub-chain followed by a descending one. We say that those chains are of the form . The computed buffer sizes on both sub-chains allow the actors at the "top" to run consecutively.

Unfortunately, Property 6.3 does not hold for an arbitrary chain (i.e., neither ascending, descending nor of the form ) (see Example ?? in the appendix). Our solution is to put such an arbitrary chain under the form by using the same approach as in the proof of Property 6.3; i.e., by increasing the execution times of some actors (without exceeding the maximum load P G ), then computing the buffer sizes as in Property 6.3, and finally restoring the original execution times. Fig. 19 illustrates this solution.

Any chain on the form obtained by increasing the load of the actors of the original chain is a valid solution. For example, the chain A B . . . K of Fig. 19 can be transformed into the red chain which is of the form . Actually, any chain of this form inside the gray area is a valid solution. An interesting problem is to find one that minimizes the sum of the buffer sizes. In the experimental section, we will compare three possible solutions.

• MAX: All loads are raised up to the maximal load (i.e., the top boundary of the gray area). This case is identical to Property 6.1, i.e., the size of each channel A p q --→ B will be equal to θ u A,B = 2(p + q -gcd(p, q)). • MIN: All loads are raised up to the bottom boundary of the gray area. In Fig. 19, the load of B will be increased to that of A, the load of E to that of D, and the load of H to that of G.

• OPT: The third solution is an optimization heuristic based on the following criteria. Let P A = z A t A denote the load of actor A.

• According to Fig. 9, the computation of the minimum buffer size θ A,B of graph A p q --→ B, where A imposes a higher load than B, depends on the execution times of A and B. It takes its minimum value θ A,B = p + q -gcd(p, q) + t B t A p when the execution times satisfies case (I), and the worst case θ u A,B when both actors impose the same load. It follows that the difference between the loads of A and B that allows reaching the minimum value of θ A,B should be

P A P B ≥ q p p q (29)
For instance, for the sub-chain A B . . . G in Fig. 19, we have P A = 50 and P G = 168.

The new distribution of the loads should be a monotone distribution in the gray area and hence in the interval [50,168]. In order to achieve minimum buffer sizes, the new loads of each actor and its predecessor (using duality) have to satisfy Eq.( 29). However, this is not possible in all cases since the interval [P A , P G ] could be very small. The next observation handles this problem.

• The gain on buffer size that comes from satisfying Eq.( 29) is at most equal to

ω A,B = θ u A,B -θ A,B . So, ω A,B = q -gcd(p, q)
This expected size gain is used to prioritize the treatment of channels.

The case of trees is solved in the same way. If the tree does not contain any sub-trees (i.e., it consists of a set of chains originating from the same root node), then the load of the root node is first increased to be equal to the maximum of all loads in the tree and then the previous method can be applied on every chain composing the tree. This is correct because the computed buffer sizes will allow the root actor to run consecutively, thus guaranteeing that the execution reaches the maximum throughput. If the tree contains sub-trees, the same process is first applied recursively on sub-trees, and then we proceed by replacing each sub-tree by its root node. In-trees are dealt with by using the duality theorem.

Inria

Exact numerical analysis

The SDF 3 tool [START_REF] Stuijk | SDF 3 : SDF for free[END_REF] proposes an exact algorithm [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF] that starts by sizing each channel A p q --→ B in the graph as the lower bound p + q -gcd(p, q). If this buffer sizes distribution (i.e., assignment of all buffer sizes in the graph) does not allow the desired throughput, a new distribution is created by increasing the size of only one buffer by gcd(p, q). This algorithm suffers from combinatorial state explosion. In our experimental analysis, we use a different exact algorithm based on a dichotomic search (Algorithm 2). It takes as an input a SDF graph G and an upper bound buffer sizes distribution S u that allows a maximal throughput, and which can be obtained by the algorithms described in the previous section. Let B(S) denote the sum of buffer sizes in a distribution S. Algorithm 2 looks for the best distribution S b with minimal B(S b ) that allows the maximal throughput. We know that B(S ) < B(S b ) ≤ B(S u ) such that S is a lower bound buffer sizes distribution where the size of each channel A p q --→ B is equal to p + q -gcd(p, q). We also know that, for any minimal buffer sizes distribution, the size of each channel A p q --→ B should be a multiple of gcd(p, q). Thus, Algorithm 2 checks only distributions that satisfy these two conditions.

Let mingcd=min{gcd(p, q)|A p q --→ B ∈ E}. For a given buffering requirement k, if every distribution S with B(S)=k does not allow the maximal throughput, then it may be possible that there exists a smaller distribution S 0 (i.e., B(S 0 )<k) that allows such throughput. However, we must have B(S 0 ) + mingcd > k. Otherwise, for instance, if B(S 0 ) + mingcd = k, then there exists a distribution S 1 with B(S 1 ) = k such that S 1 dominates S 0 (i.e., ∀e ∈ E, S 1 (e) ≥ S 0 (e)). But, since S 1 does not allow a maximal throughput, neither should S 0 .

The algorithm uses a dichotomic search that first checks whether there is a buffer sizes distribution, whose total size is at the middle between the lower bound B(S ) and the upper bound solution B(S u ) (i.e., total size equals B[middle]), which allows the graph to achieve its maximal throughput. If there is no such distribution, we check every distribution S such B(S)

+ mingcd > B[middle].
If there is no distribution (found = false), the algorithm proceeds to the top of the search space (begin = middle), otherwise it proceeds to the bottom one (end = k).

Latency computation for acyclic graphs

Like Section 6, this section shows how we can use the results for a single edge graph A p q --→ B to obtain approximate analyses for the latency of general acyclic dataflow graphs. To achieve this, Inria we make use of the linearization techniques (Section 5.1).

Multi-iteration latency of acyclic graphs

In this section, we compute an upper bound of the multi-iteration latency of the first n iterations, denoted L G (n). A similar approach can be used to compute a lower bound. However, upper bounds are more useful in practice since they ensure important safety properties (e.g., a deadline, a minimal quality of service, etc.). In this paper, the computed upper bound is used to underapproximate the maximal achievable throughput.

An acyclic SDF graph can be represented as a set of maximal chains G(G), that is, chains from a source actor to a sink actor. By considering each chain g ∈ G(G) as an SDF graph with the same repetition vector as G, we have the following property.

Property 7.1. For any acyclic SDF graph G,

∀i. L G (i) = max g∈G(G) {L g (i)}
According to Property 7.1, the problem reduces to computing the multi-iteration latency of each chain in the graph. Each chain spreads from a source actor to a sink actor.

For each chain

A p1 q1 ----→ B p2 q2 ----→ C → • • • → Z,
we compute an upper bound of its multiiteration latency for n iterations, denoted by LA→Z (we omit n for the sake of conciseness). We can compute exactly L A→B as described in Section 4.3. However, since the technique assumes that the producer can run consecutively, it cannot be applied between B and C. We compute an upper bound linearization of the firings of B such that they are consecutive and ∀j ≤ nz B . f B u (j) ≥ f B (j).

As illustrated in Fig. 21, the exact multi-iteration latency of chain A → B → C is L G (n) = LA→B + δ where δ is the remaining execution time of C after the end of B. If η = f B u (nz B ) -LA→B (i.e., the approximation introduced by the upper bound linearization), then δ ≤ ∆ B u ,C +η. Indeed, ∆ B u ,C (computed by Equations of Fig. 11) gives the remaining time for C after the end of B u (recall that firings of B u are consecutive and hence the method described in Section 4.3 can be used).

Upper bound linearization

The critical part of this method is to find the best upper bound linearization that minimizes the difference between the exact value δ and the approximate one (∆ B u ,C + η). We propose two upper bound linearization methods, Push and Stretch (Section 5.1.1). It can be shown that the two methods are incomparable even if we distinguish the cases when B imposes a higher load than C and vice-versa. In both cases, there are graphs for which either Push or Stretch is better. Since the two methods are not costly to try, we apply both and take the minimum. In case of Push (Fig. 22), we have

LA→C ≤ LA→B + η + ∆ B p ,C = LA→B + 0 + ∆ B,C
In case of Stretch (Fig. 21), we have

LA→C ≤ LA→B + η + ∆ B s ,C = LA→B + (f B s (nz B ) -LA→B ) + ∆ B s ,C = f B s (nz B ) + ∆ B s ,C
Therefore, we have ---→ C using Push method.

LA→C ≤ min{ LA→B + ∆ B,C , f B s (nz B ) + ∆ B s ,C } (30)
The same process can be repeated to treat an arbitrary long chain. For instance, to compute the latency of the sub-chain A → B → C → D, we have LA→D = min{ LA→C + ∆ C,D , f C s (nz C ) + ∆ C s ,D } such that LA→C is the latency computed in the previous step (i.e., for sub-chain A → B → C), and C s is the linearization of C using the method Stretch applied transitively on actors of the sub-chain A → B → C.

Example 7.1. Let us consider the graph

G = A p1 1 ---→ B p2 1
---→ C which has five parameters: the production rates p 1 , p 2 and the execution times t A , t B and t C . Suppose that, at a given design stage, the only known information is that p i ∈ [1, 10 2 ] and that execution times are in [10 3 , 10 4 ]. In parametric dataflow models, it is possible that parameters change before the execution enters the steady state. Therefore, a safe over-approximation of the minimal period P G of the graph is LG (1). For this example, we want to check the following property P m : G (1) ≤ mP G where m ∈ N + ; i.e., the multi-iteration latency of the first iteration does not over-approximate the minimal period by more than m times. A naive approach would be to check this property for all configurations of rates and execution times parameters i.e., for more than 7×10 15 configurations. With our approach, we can solve this problem analytically. First, we generate a symbolic program Inria Prog (i.e., a set of equations) that computes LG (1). This step is polynomial in the number of channels of the graph and depends neither on the parameters nor on the number of iterations. Then, we check if Prog ∧ P m is satisfied for all configurations. The repetition vector of this graph is z = [1, p 1 , p 1 p 2 ]. The generated program Prog, after simplification of the equations, is

LG (1) = t A + p 1 t B + p 2 t C if t B ≥ p 2 t C t A + t B +

Input-output latency of chains

We now compute the maximum input-output latency G (or an upper bound ˆ G ) of a chain G. The input-output latency of the n th iteration, G (n) is equal to the difference between the multi-iteration latency L G (n) and the start time of the first firing of the source actor in the n th iteration.

If the source actor A imposes the highest load among all actors of the graph or if all the channels are unbounded, then the source actor never gets idle and achieves the maximal throughput. Hence, we can put

G (n) = L G (n) -(n -1)z A t A (31)
However, if the source actor does not impose the highest load, then G (n) as given by Eq. ( 31) is unbounded unless the channels are bounded. Therefore, as in the case of the graph A p q --→ B, we need to consider the buffer sizes when computing the input-output latency.

Consider for instance the chain A ---→ C with t A = 5, t B = 4 and t C = 8. The size of channel A → B is 24 and the size of channel B → C is 12. Actor C imposes the highest load. Fig. 23(a) shows the ASAP schedule for two iterations. We have ˆ G = G (2) = 83. Note that the sink actor C runs consecutively but not the source actor A, which prevents us from using Eq. (31) to compute the input-output latency.

As illustrated in Fig. 23(b), our solution consists in using a lower bound backward linearization (Section 5.2). Starting by the end of the chain (i.e., channel B → C), actor B is first transformed into a fictive actor B that runs consecutively such that ∀i.f B (i) ≤ f B (i). This constraint also implies that the start times of the firings of B s are advanced compared to start times of B (because t B ≥ t B ), which leads to an over-approximation of the input-output latency.

Since B runs consecutively and imposes a higher load than A, the same process can be repeated to backward linearize A. It follows that the start times of the firings of A in the final schedule are an under-approximation of the actual start times. The computation of the inputoutput latency is now straightforward (using Eq. ( 31)) since the input actor A runs consecutively. So, we have ˆ G = 89.8, which is only an 8.2% over-approximation compared to the actual inputoutput latency (83). The previous approach can be applied to any arbitrary chain where the sink actor imposes the highest load. If the actor with highest load1 , denoted H, is in the middle of a chain A → . . . → H → . . . → Z, then the lower bound linearization of A (i.e., A ) is computed using the above described backward linearization starting from actor H, while the upper bound linearization of Z (i.e., Z u ) is computed using the forward linearization (Section 7.1) starting from actor H. An over-approximation of the input-output latency can be then computed between A and Z u .

Experiments

Buffer sizing

In this section, we compare the results of the three algorithms (MAX, MIN and OPT) presented in Section 6.2 with each other and with the exact minimum buffer sizes (Algorithm 2) using many randomly generated SDF graphs and some real benchmarks.

First, we compare2 the results of MIN with those of MAX (i.e., safe upper bounds 2(p + q -gcd(p, q))) using two million randomly generated chains of 10 actors where the production and consumption rates (resp. execution times) are uniformly distributed over the interval [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF][START_REF] Sriram | Embedded multiprocessors: scheduling and synchronization[END_REF] (resp. [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF]200]). The number of firings per iteration, X z X , of every generated chain has been bounded by 6×10 3 . For each graph, we compute the ratio of the sum of the buffers sizes obtained by algorithm MAX to those obtained by algorithm MIN. Each black dot in Fig. 24 represents the obtained ratio for one graph, while the red line represents the average of ratios. Fig. 24 shows that, in average, algorithm MIN reduces the total buffer sizes by 8% compared to the upper bounds. Fig. 25 shows a comparison between the OPT and MIN algorithms with the same settings as for Fig. 24. For instance, the blue curve (avg MAX/OPT ) represents the average ratio of the results obtained by MAX to those of OPT. This figure shows that, in average, OPT improves over MAX by almost 11.1% and improves over MIN by almost 3.5%. This is a significant improvement knowing that transferred tokens in streaming applications could be blocks of video frames. However, if one is looking for time efficiency (which could be important for an online computation for instance), then MIN is less expensive than OPT. We also compare the results of the heuristic with the exact minimum buffer sizes computed by Algorithm 2 (which we denote by EXACT). Due to the exponential complexity of the minimum buffer sizes problem, we evaluate our approach on only 10 4 randomly generated chains of 4 actors where the production and consumption rates (resp. execution times) are uniformly distributed over the interval [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF][START_REF] Geilen | Synchronous dataflow scenarios[END_REF] (resp. [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF]100]). The blue (resp. red) line in Fig. 25 represents the average of the ratios of the exact (EXACT) (resp. approximate (OPT)) solution to the upper bounds (MAX ). In average, the OPT heuristic over-approximates the exact solution by 25%. Furthermore, Fig. 25 also shows that MAX over-approximates EXACT by 55% in average. Hence, by extrapolating this result, our OPT heuristic would over-approximate the exact solutions of Fig. 24 by 37% in average. Finally, we evaluate the heuristic using five real applications: the H.263 decoder, the data modem and sample rate converter from the SDF 3 benchmarks [START_REF] Stuijk | SDF 3 : SDF for free[END_REF], the fast fourier transformer (FFT), and the time delay equalizer (TDE) from the StreamIt benchmarks [START_REF] Thies | An empirical characterization of stream programs and its implications for languages and compiler design[END_REF]. All these graphs have a chain structure. Table 1 shows some characteristics of these applications together with the obtained results. Our approach improves better the upper bounds in case of chains with a form (H.263 decoder and FFT). It comes close to the upper bound for the sample rate converter since the two actors with the highest loads are the right and left ends of the chain; increasing the loads of the other actors to get a monotone chain results in a size of almost 2(p + q -gcd(p, q)) for every channel.

Latency computation

We first evaluate our approach for computing the multi-iteration latency using randomly generated chains of 10 actors. Five million chains have been generated such that the production and consumption rates are uniformly distributed over the interval [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF][START_REF] Geilen | Synchronous dataflow scenarios[END_REF] while the execution times are Inria uniformly distributed over then interval [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF]100]. The number of firings per iteration (i.e., A z A ) of every generated chain has been bounded by 2 × 10 3 . The exact multi-iteration latency of the first iteration (i.e., L G (1)) is compared with the latency computed using our approach (denoted by LA1→A10 ); and we report the ratio LA 1 →A 10

L G (1)
(i.e., the over-approximation). Each black dot in the upper part of Fig. 27 represents the ratio for one graph, while the red line represents the average of ratios. The average over-approximation is negligible when the number of firings per iteration is small. Indeed, if there are many harmonious rates (recall that, when p divides q or q divides p, the computed latency for A p q --→ B is exact), then the computed latency remains close to the exact value. Then, the average over-approximation increases to reach its peak (approximately 2.5%) around fifty firings per iteration. This is because the exact values of latency at these points are small and hence the over-approximation is more noticeable. Then, the average over-approximation decreases and tends to zero for graphs with large latencies. These observations were confirmed by many other experiments (e.g., with longer chains, larger rates, etc.) not reported in this paper.

The bottom part of Fig. 27 shows that using only the Stretch linearization method is better (in average) than using only the Push method. It also shows that using both methods on all channels of the chain (line Push+Stretch) is better than taking the minimum of their separate results (line min{Push, Stretch}). The results are further improved by using the duality theorem (line Push+Stretch+Dual) as explained in note 7.2. Table 2 presents the obtained results for the real benchmarks. It shows that our approach gives exact results for most of these benchmarks. Production and consumption rates of channels of these graphs are quite harmonious (p divides q or q divides p), for which our approach performs very well, as noticed in the previous experiment.

Finally, we evaluate our approach for computing the input-output latency using 10 5 randomly generated chains of 9 actors. Chains are generated such that the production and consumption rates are in the interval [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF][START_REF] Geilen | Synchronous dataflow scenarios[END_REF] while the execution times are in the interval [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF]100]. The number of firings per iteration of every generated chain has been bounded by 2 × 10 3 . The last actor in each chain imposes the highest load, and the size of each channel 2(p + q -gcd(p, q)). Each black dot in Fig. 28 represents the obtained ratio

A p q --→ B is equal to RR n°8742
ˆ G
G for one graph, while the red line represents the average of ratios. Note that the exact computation of G is very time-consuming since it requires a simulation of the schedule until reaching the steady state (hundreds of iterations for some chains). Therefore, we have limited our experiment to only 10 5 chains of 9 actors. Fig. 28 shows that our analysis over-approximates the exact computation, in average, by at most 13%. The over-approximation is less noticeable for graphs with large input-output latencies.

Related work

Few symbolic results about SDF graphs can be found in the literature. In this section, we present the most relevant ones.

Consistency can easily be checked analytically. The repetition vector can be computed symbolically as is it done in most dynamic parametric SDF models (e.g., [START_REF] Bebelis | BPDF: a statically analyzable dataflow model with integer and boolean parameters[END_REF][START_REF] Fradet | SPDF: a schedulable parametric data-flow MoC[END_REF]).

There is no exact analytical solution to check the liveness of a graph with buffers with fixed bounds. In [START_REF] Bebelis | BPDF: a statically analyzable dataflow model with integer and boolean parameters[END_REF] and [START_REF] Bempelis | Boolean Parametric Data Flow: Modeling -Analysis -Implementation[END_REF], the authors apply Eq. ( 4) transitively (which leads to nested ceilings) on edges of each cycle in the graph. Then, the obtained equations are linearized by Inria over-approximating the ceiling function (i.e., x < x + 1). However, this is a very conservative liveness analysis. As proved in [START_REF] Battacharyya | Software synthesis from dataflow graphs[END_REF], the minimum buffer size for which the simple graph A p q --→ B is live is equal to p + q -gcd(p, q) 3 . This however does not imply that any graph whose channels are sized this way is live. Still, this analytical equation is used in many algorithms of buffer sizing to compute a lower bound on buffer sizes as a starting solution ( [START_REF] Bempelis | Boolean Parametric Data Flow: Modeling -Analysis -Implementation[END_REF][START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF]).

Let s i denotes the token timestamp vector, where each entry corresponds to the production time of tokens in the i th iteration of the graph. Then, as shown in [START_REF] Geilen | Synchronous dataflow scenarios[END_REF], the max-plus algebra can be used to express the evolution of the token timestamp vector: s i = M s i-1 . It has been proved that the eigenvalue of matrix M is equal to the period of the graph. In case of parametric rates, it is sometimes possible to extract a max-plus characterization of the graph with a parametric matrix [START_REF] Skelin | Worst-cas throughput analysis for parametric rate and parametric actor execution time scenario-aware dataflow graphs[END_REF][START_REF] Skelin | Parametrized dataflow scenarios[END_REF]. However, this works only in cases where Eq. ( 4) can be somehow simplified to get rid of the ceiling function (e.g., when p = 1).

[11] presents a parametric throughput analysis for SDF graphs with bounded parametric execution times of actors but constant rates. Since rates and delays are non-parametric, the SDF-to-HSDF transformation is possible and the throughput analysis is based on the MCM of the resulting HSDF graph. Therefore, all cycle means are linear functions in terms of the parametric execution times. By using these linear functions, the parameter space is thus divided into a set of convex polyhedra called "throughput regions", each with a throughput expression. This approach has been extended in [START_REF] Damavandpeyma | Parametric throughput analysis of scenario-aware dataflow graphs[END_REF] to the case of scenario-aware dataflow (SADF) graphs.

A different analytic approach to estimate lower bounds of the maximum throughput is to compute strictly periodic schedules instead of ASAP schedules (e.g., [START_REF] Bodin | Periodic schedules for cyclo-static dataflow[END_REF]). This approach is similar to our Stretch linearization method used in Section 7 to compute the latency of the graph. We have however shown that using both Push and Stretch methods usually gives better results.

The advantage of the strictly periodic scheduling approach is its capability to handle cyclic graphs. However, not all cyclic graphs have strictly periodic schedules (it depends on the number of initial tokens). Furthermore, experiments on real-life benchmarks show that these approaches result in huge over-approximations (sometimes 7 times the exact value) [START_REF] Bodin | Periodic schedules for cyclo-static dataflow[END_REF]. In theory, the overapproximation is not even bounded.

Conclusion

We have studied analytically the different cases of the execution of a completely parametric single edge dataflow graph A p q --→ B. Enabling patterns are introduced to better characterize the data-dependency between the producer and the consumer. Then, we have presented the exact symbolic solutions for the minimum buffer size needed by a single edge graph to achieve its maximal throughput. We also presented exact symbolic analyses for computing the latencies of such a graph.

Using these results and forward linearization techniques, we have provided safe upper bounds of buffer sizes of acyclic graphs for maximal throughput. Furthermore, we have proposed a heuristic to improve these bounds for graphs with a chain or a tree structure. Experimental results show that our heuristic improves the upper bounds by 11.1% in average, over-approximates the exact solutions by 25% in average, and can give the optimal solution for some real applications. The exact solutions was computed using our numerical analysis which is based on a dichotomic search.

We also used forward and backward linearization techniques to compute over-approximations of the multi-iteration latency of general acyclic graphs and the input-output latency of chains.

Experimental results show that our symbolic analyses over-approximate the exact solutions by only 2.5% in case of the multi-iteration latency and 13% in case of the input-output latency.

Future work will concern the extension of these analysis to deal with general (i.e., possibly cyclic) dataflow graphs.

A Throughput and duality

Proof. (Property 3.1) This is easily shown by considering the corresponding HSDF graph. As illustrated in Fig. 29(a), the SDF-to-HSDF transformation algorithm [START_REF] Sriram | Embedded multiprocessors: scheduling and synchronization[END_REF] replicates each actor A in the original graph z A times (recall that z is the repetition vector), each instance represents a firing of A in one iteration. Then, each edge A p q ---→ B in the original graph is transformed into p z A edges, each one representing a data dependency between a firing of A and a firing of B. Let HSDF(G) denote the HSDF graph equivalent to the acyclic graph G. The only cycles that appear in HSDF(G) are the results of the transformation of self-edges used to disable auto-concurrency. For each actor A, its corresponding cycle contains one delay and z A instances of A. Thus, the cycle mean is equal to z A t A , and the MCM is hence equal to max A∈V {z A t A }.

Proof. (Theorem 3.1) We first prove that the graph HSDF(G) is the dual of HSDF(G -1 ). As described in the previous proof, the SDF-to-HSDF transformation is compositional in the sense that each channel is transformed independently of the rest of the graph. Hence, it is sufficient to prove that HSDF(A p q --→ B) and HSDF(B q p --→ A) are dual to each other as illustrated in Fig. 29 (see Property A.1). It follows that each cycle in HSDF(G) has a dual in HSDF(G -1 ). Therefore, both graphs have the same MCM and the same throughput i.e., T G = T G -1 .

The second step in this proof is to show that ∀i. L HSDF(G) (i) = L HSDF(G -1 ) (i). The multiiteration latency of the first i iterations of an HSDF graph can be obtained by searching the longest path in a directed acyclic graph (DAG) obtained by unfolding the HSDF graph for i iterations and deleting any edge with an initial token (since this edge does not impose a precedence constraint between firings).

Thus, by unfolding HSDF(G) and HSDF(G -1 ) for i iterations, we obtain two DAGs that are dual to each other since the unfolding transformation preserves duality. Therefore, for each maximal path in the first DAG (i.e., a path from a source node to a sink node), there is a dual maximal path in the second DAG. Both such paths have the same length hence L HSDF(G) (i) = L HSDF(G -1 ) (i). --→ B duplicates actor A z A times and actor B z B times. Furthermore, it creates pz A (or equivalently qz B ) dependencies between instances of A and instances of B. These dependencies are named as illustrated in Fig. 30.

The i th token produced by A in G creates a dependency A j -→ B k in the graph HSDF(G) with j = (i -1) mod pz A and k = (i + d -1) mod pz A where d is the number of initial tokens in channel A → B. We then prove that ∃i such that the i th token produced in graph G -1 creates a dependency B pz A -1-k -→ A pz A -1-j in the graph HSDF(G -1 ). For instance, in Fig. 30.(a) we have the dependency A 5 → B 0 in HSDF(G). Its counterpart in Fig. 30.(b) is the data-dependency B 6-1-0=5 → A 6-1-5=0 . --→ B) and HSDF(B

q p --→ A).
Therefore, we need to prove that ∀i∃i .

(i -1) mod

pz A = pz A -k -1 (i + d -1) mod pz A = pz A -j -1
Hence, by simplification, ∀i∃i . (i + i + d -2) mod pz A = pz A -1. This equation is satisfiable independently of d, p and z A . This process goes both ways; i.e., there is a bijection between edges in HSDF(G) and edges in HSDF(G -1 ). Therefore, if we rename actors in HSDF(G -1 ) in the reverse order, then each edge in HSDF(G) has a reversed counterpart in HSDF(G -1 ). Note that renaming actors (i.e., A z A +1-i instead of A i ) does not alter the ASAP execution since instances of an actor has the same execution time. Now, we prove that the numbers of initial tokens in edges A j -→ B k and B pz A -1-k -→

A pz A -1-j are the same. The number of initial tokens in

A j -→ B k is equal to d pz A if d mod pz A ≤ k; and d pz A + 1 otherwise. While the number of initial tokens in edge B pz A -1-k -→ A pz A -1-j is equal to d pz A if d mod pz A ≤ (pz A -1 -j); and d pz A + 1 otherwise. But since (d mod pz A ≤ k) ⇔ (d mod pz A ≤ (pz A -1 -j))
, the property is satisfied. • Case (A.2): (p = kq + r and q ≤ 2r) The first firing of A enables only k firings of B, yielding the pattern A B k . The number of remaining tokens in the channel after sequence AB k is equal to r. Since 2r ≥ q, the second firing of A enables k + 1 firings of B, yielding the aggregated pattern A B k ; A B k+1 . It follows that pattern A B k+1 can be repeated a number of times denoted α 1 , after which there will be r + α 1 (r -q) tokens left. So, α 1 is the largest integer such that r + α 1 (r -q) ≥ 0. Hence, α 1 = r q-r . The next firing of A will only enable k firings of B (A B k ). By the same reasoning as above, this will be followed by [A B k+1 ] α2 where α 2 is the largest integer such that r + α 1 (rq) + r + α 2 (r -q) ≥ 0. Hence, α 2 = 2r q-r -r q-r . This process is repeated until all firings of A and B of the iteration take place, yielding the complete pattern

B The parametric graph A

A B k ; [A B k+1 ] αj j=1••m
for some m that remains to compute. The number of firings of A in this pattern is equal to

c A = m j=1 1 + α j , while the number of firings of B is equal to c B = m j=1 k + (k + 1)α j . Note that since m j=1 α j = m r q-r , we have c A = m + m r q-r and c B = m k + (k + 1) m r q-r . A correct pattern covers the entire iteration, that is c A = z A and c B = z B . We have z A = q gcd(p,q) and z B = p gcd(p,q) , thus m k + (k + 1)( q gcd(p,q) -m) = p gcd(p,q)
This implies that m = q-r gcd(p,q) .

• Case (A.3): (p = kq + r and q > 2r) Similarly to case (A.2), the first firing of A enables k firings of B. However, since q > 2r, the second firing of A enables only k firings. The sequence of numbers of remaining tokens will be

0 AB k -→ r AB k -→ 2r AB k -→ • • • AB k -→ β 1 r AB k+1 -→ β 1 r + (r -q) (32)
So, β 1 is the smallest number for which β 1 r + (r -q) is non-negative. Hence, β 1 = q-r r . At this point, the next firing of A enables k + 1 instances of B. This process will repeat infinitely with β j = j(q-r) r -(j-1)(q-r) r . Sequence (β j ) is periodic with a period of length r gcd(p,q) . At the end of each period, the number of remaining tokens returns to zero.

• Case (B.1): (q = kp) The repetition vector is z = [k, 1]. Each k firings of A enable one firing of B and the enabling pattern is A k B .

• Case (B.2): (q = kp + r and p ≥ 2r) (k + 1) firings of A are needed to enable the first B. Hence, after (A k+1 B), the number of remaining tokens in the buffer is (p -r). If p ≥ 2r, then only k firings of A are needed to enable the second firing of B; and the number of remaining tokens will be (p -r) -r. As in the previous cases, we will have a sequence

0 A k+1 B -→ (p -r) A k B -→ (p -r) -r A k B -→ • • • A k B -→ (p -r) -γ 1 r (33)
So, γ 1 is the largest number for which (p -r) -γ 1 r is non-negative; thus γ 1 = p-r r . At this point, k + 1 firings of A are required to enable another firing of B. This process will repeat infinitely with γ j = j(p-r) r -(j-1)(p-r) r . Note that sequence (γ j ) is periodic with a period of length r gcd(p,q) . At the end of each period, the number of remaining tokens returns to zero.

Inria

• Case (B.3): (q = kp + r and p < 2r) Similarly to case (B.2), (k + 1) firings of A are needed to enable the first B. However, since p < 2r, (k + 1) firings of A are required to enable the second firing of B. The sequence of numbers of remaining tokens is then

0 A k+1 B -→ (p -r) A k+1 B -→ 2(p -r) A k+1 B -→ • • • A k+1 B -→ λ 1 (p -r) A k B -→ (34)
So, λ 1 is the smallest number for which λ 1 (p -r) -r is non-negative. Hence, λ 1 = r p-r . At this point, only k firings of A are required to enable the next firing of B. This process will repeat infinitely with λ j = jr p-r -(j-1)r p-r

. Sequence (λ j ) is periodic with a period of length p-r gcd(p,q) . At the end of each period, the number of remaining tokens returns to zero.

B.2 Minimum buffer size for maximum throughput

Proof. (Property 4.2)

The three cases of Fig. 9 should be read as (I) else (II) otherwise (III).

Case (I):

At any given enabling point ( i.e., any in the enabling pattern), all newly enabled firings of B complete their execution before the next enabling point.

In terms of the enabling pattern cases identified in Fig. 8, case (I) must be split into two exclusive subcases, (I.1) when p ≥ q and (I.2) otherwise. The conjunction of the condition for case (I.1) yields the condition A.1 ∨ ((A.2 ∨ A.3) ∧ (t A ≥ (k + 1)t B )) where (A.1), (A.2) and (A.3) refer to the exclusive patterns of Fig. 8. The other conditions are obtained similarly.

Case (I), pattern (A.1):

In case p ≥ q and r = 0, the parallel schedule is A; [A||B k ] * , which means that each k firings of B run in parallel with a firing of A. We have,

δ 1 = p, δ 2 = 2p, δ 3 = δ 2 + p -kq = 2p, . . .. So, θ A,B = max i δ i = 2p.

Case (I), pattern (A.2):

Let us prove the result for case (I.1) and pattern (A.2), i.e., p = kq +r with q ≤ 2r. According to the enabling pattern (A.2), at most (k + 1) firings of B can be enabled at a given point. They all run in parallel with one firing of A. Therefore, case (I.1) requires that t A ≥ (k + 1)t B .

We first expand the enabling pattern of (A.2) into an infinite pattern in order to compute the minimum buffer size θ A,B over the infinite execution of the graph:

A B k ; A B k+1 αj j∈N + (35)
For the sake of the proof, since α j ≥ 1, we can rewrite Eq. ( 35) into the equivalent infinite pattern:

A B k ;A B k+1 prologue ; [A B k+1 ] αj -1 ;A B k ;A B k+1 block j j∈N + (36)
Recall that δ j denotes the minimum number of tokens in the backward edge such that the j th firing of A can occur immediately after the (j -1) th firing of A. The minimum number of tokens to enable the first firing of A must be δ 1 = p. Then, δ 2 = δ 1 + p = 2p because no B has finished before the second A starts. Then,

δ 3 = δ 2 + (p -kq) = 2p + r. Subsequently, δ 4 = δ 3 + (p -(k + 1)q) = δ 3 + (r -q),
and all α 1 subsequent values of δ i are obtained from δ i-1 by adding (r -q) which is negative. The value of α j is defined in Fig. 8. Hence, δ 1+(α1+1)+1 = δ 3 + α 1 (r -q) = 2p + r + α 1 (r -q). This ends at the last of the α 1 patterns A B k+1 , so the next value δ 1+(α1+1)+2 is obtained by adding p -kq = r because of pattern A B k , yielding 2p + r + α 1 (r -q) + r. The computation of the infinite sequence (δ j ) is illustrated in Fig. 31. Within each block j, the subsequence (δ h ) is strictly decreasing because (r -q) is negative, so its maximum value is the value of the entry point, which we denote by j = 1 + j i=1 (α i + 1) + 2. We thus have:

δ j = 2p + r + j i=1 (α i (r -q) + r) = 2p + r + jr + (r -q) jr q -r
It follows that the maximum value of the infinite sequence (δ j ) is:

θ A,B = max j∈N δ j = max j∈N (2p + r + jr + (r -q) jr q -r ) = 2p + r + (q -r) max j∈N ( jr q -r - jr q -r )
As a conclusion, θ A,B = 2p + r + (q -r -gcd(p, q)) = 2p + q -gcd(p, q).

Case (I), pattern (A.3):

We write the parallel schedule as A; Hence, we will have a sequence similar to that of Eq. (32). If S 2 denotes that sequence, then θ A,B = max i δ i = δ 2 + max S 2 . Since (r -q) is negative, we have that max S 2 = (q -r) + Inria max j j(r -q) + r j i=1 β i = (q -r) + max j r jq r -jq = (q -r) + r max j jq r -jq r . But, max j jq r -jq r = r-gcd(q,r) r [Using Bézout identity]. Thus, max S 2 = (q -r) + r -gcd(q, r).

[[A||B k ] βj ; A||B k+1 ] * . Again, we have δ 3 = δ 2 + p -q = δ 2 + r, δ 4 = δ 3 + p -q = δ 2 + 2r, . . . (see Fig. 32)
Hence, θ A,B = 2p + q -gcd(p, q).

Case (I), pattern (B.1):

The first firing of B will not finish before the start of the

( t B t A ) th firing of A. Let us put x = k + t B t A . Hence, δ x = xp, δ x+1 = δ x + p -q, . . . , δ x+k = δ x + xp -q = δ x , . . . So, θ A,B = xp = q + t B t A p.

Case (I), pattern (B.2):

The first firing of B will not finish before the start of the

(k + 1 + t B t A ) th firing of A. Let us put x = k + 1 + t B t A . Hence, δ x = xp.
We have that δ x+k = δ x + kp -q = δ x -r, . . . , δ x+γ1k = xp -γ 1 r, . . . (See Fig. 33) This case is illustrated in Fig. 35. Each block is of the form [A B 2 ] αj ; A B , where the maximum value of α j is 2. Therefore, five firings of B have to run in parallel with three firings of A. So, we must have 5t B ≤ 3t A . The computed sequence (δ j ) in case (II) is similar to that of case (I) but with small increments.

Case (II), pattern (A.2):

Since kt B + r q t B ≤ t A < (k+1)t B (i.e., case (I) is not satisfied), we can put t A = kt B +r . If k+1 firings of B are enabled, then there execution will be larger than t A by e = (k +1)t B -t A = t B -r . According to the enabling pattern, a block is of the form [A B k+1 ] αj ; A B k . Hence, the firings of B brim over the block by α j e + kt B -t A = α j (t B -r ) -r . Thus, to satisfy case (II), we must have ∀j. α j (t B -r ) -r ≤ 0. But, the maximum value of α j is r q-r . Therefore,

t A ≥ kt B + r q-r r q-r + 1 t B
Similarly to case (I.A.1), we compute sequence (δ i ) (see Fig. 36). Compared to case (I.A.2), the sequence is incremented by a (+r). Hence, θ A,B = max i δ i = 2p + q -gcd(p, q) + r.

Case (II), pattern (A.3):

According to the enabling pattern, one block is of the form A B k+1 ; [A B k ] βj . Hence, firings of B will brim over the block by e + (kt B -t A )β j . Thus, to satisfy case (II), we must have ∀j. e + (kt B -t A )β j ≤ 0. But, the minimum value of β j is q-r r . Therefore, The sequence (δ i ) is illustrated in Fig. 37. Compared to case I.(A.3), it is incremented by (+Xr) where X is the smallest integer such that e + (kt B -t A )X ≤ 0 (i.e., the overflow is caught up). So, X = t B t A -kt B -1. Therefore, θ A,B = 2p + q -gcd(p, q) + Xr.

t A ≥ kt B + 1 q r t B Inria

Case (II), pattern (B.2):

Since kt A < t B ≤ kt A + r p t A (i.e., case (I) is not satisfied), we can put t B = + r . So, the execution time of one firing of B is larger than the execution time of k firings of A by e = t B -kt A = r . According to the enabling pattern, a block is of the form [A k B ] γj ; A k+1 B . Hence, the firings of B brim over the block by γ j r + t B -(k + 1)t A . Thus, to satisfy case (II), we must have ∀j. γ j r + r -t A ≤ 0. But, the maximum value of γ j is p-r r . Therefore,

t B ≤ kt A + 1

Case (II), pattern (B.3):

According to the enabling pattern, one block is of the form A k B ; [A k+1 B ] λj . Hence, firings of B will brim over the block by t B + λ j t B -kt A -λ j (k + 1)t A = r + λ j (r -t A ). Thus, to satisfy case (II), we must have ∀j. r + λ j (r -t A ) ≤ 0. But, the minimum value of λ j is r p-r . Therefore, we must have

t B ≤ kt A + r p-r r p-r + 1 t A
The sequence (δ i ) is illustrated in Fig. 39. Compared to case I.(B.3), the sequence is incremented by (+X(p -r)) where X is the largest integer such that r + X(r -t A ) > 0 (i.e., the overflow is not caught up). Hence, θ A,B = p+q -gcd(p, q)+ t B t A p+X(p-r). But, t B t A = k +1. Therefore, θ A,B = 2p + 2q -r -gcd(p, q) + X(p -r). We have that X = r t A -r -1. Otherwise. This is the most complicated case to solve since the sequence (x j ), which denotes the number of firings of B that have finished by the start of the j th firing of A, does not follow the enabling patterns. Our solution is based on the following observations. We define a catch-up sequence as a sequence of consecutive firings of B (i.e., without gaps) that may spread over several blocks. Fig. 40 illustrates a catch-up sequence over two blocks.

RR n°8742

The key observation is the following. For the firings of A inside a catch-up sequence, the number of firings of B that finish before firings of A actually follows the enabling pattern of graph A t A t B ----→ B, i.e., as if time was produced and consumed instead of tokens. Furthermore, the maximum of sequence (δ j ) occurs inside the maximal (in terms of blocks) catch-up sequence. For instance, n in Eq. (37) represents the length of the maximal catch-up sequence.

Case III. Case III.1. A.2 θ A,B = 2p + q + r -gcd(p, q) + n-1 max j=1 (jr mod (q -r)) ( 37
)
where n is the smallest positive integer such that nr t B -r

≥ nr q-r and r = t A -kt B . Case III.2. A.3 θ A,B = 2p + 2q -gcd(p, q) - n-1 min j=1 (jq mod r) ( 38
)
where n is the smallest positive integer such that nt B

where n is the smallest positive integer such that nr t A -r ≤ nr p-r and r = t B -kt A .

Case (III), pattern (A.2):

Sequence (α j ) takes two values4 ; ∀j. α j ∈ r q-r , r q-r . Once α j = q-r , an overflow will propagate this block to the subsequent blocks. Thus, all firings of B till the catch-up point are consecutive. We call this sequence a catch-up sequence. The value of δ i for the firing of A at the catch-up point will be equal to that computed in case II.(A.2). See Fig. 41. To know how many firings of B in the catch-up sequence finish before the start of any firing of A, we may look at the enabling pattern of the graph A t A t B ----→ B. Since t A ≥ t B and t B ≤ 2r (because A imposes a higher load than B), this enabling pattern is A B k ; A B k+1 α j with

α j = jr t B -r -(j-1)r t B -r .
If a catch-up sequence starts at the j th block, then it will end at some block (j + n -1) if and only if

n i=1 α i ≥ j+n-1 i=j α i ; i.e.
, n is the smallest integer that satisfies

nx 2 ≥ (j -1)x 1 + nx 1 -(j -1)x 1 (41)
where x 1 = r q-r and x 2 = r t B -r . One important catch-up sequence is the longest one (called the maximal catch-up sequence). If we put (j -1)r = a(q -r) + b, then the previous equation can be rewritten as nx 2 ≥ nx 1 + b q-r . This implies that n is maximal when b is maximal; i.e., b = q -r -gcd(q, r). However, this does not imply that the (j -1) th block such that (j -1)r mod (q -r) = q -r -gcd(p, q) is actually a catch-up point. To prove that we need to show that ∃m ≤ (j -1).

m i=1 α i < j-1 i=j-m α i ; i.e., mx 2 < (j -1)x 1 -(j -1)x 1 -mx 1 ;
which can be rewritten as mx 2 < -b q-r -mx 1 = mx 1 . Inequality mx 2 < mx 1 has no solution because x 2 ≥ x 1 (since A imposes a higher load than B).

This means that among all catch-up points, the maximum value of (δ i ) occurs at the catch-up point before the maximal catch-up sequence; and it is equal to 2p + q -gcd(p, q) (see Fig. 36). Furthermore, since any catch-up sequence is a prefix of the maximal catch-up sequence, the worst-case occurs inside this maximal sequence. Therefore, θ A,B = 2p + q -gcd(p, q) + (r + n-1 max j=1 (rj + (r -q) j i=1 α i ) where n is the length of the maximal catch-up sequence. So, θ A,B = 2p + q + r -gcd(p, q) + n-1 max j=1 (rj + (r -q) jx 2 ).

But, according to Eq. ( 41), the maximal n is the smallest integer such that nx 2 ≥ nx 1 (recall that (j -1)r mod (q -r) = q -r -gcd(p, q)). Hence, ∀j < n. jx 2 < jx 1 . But, we know that ∀j. jx 2 ≥ jx 1 (because x 2 ≥ x 1 ). Thus, ∀j < n. jx ≤ jx 2 < jx 1 ; thus jx 2 = jx 1 . Therefore,

θ A,B = 2p + q + r -gcd(p, q) + n-1 max j=1 (jr mod (q -r)) (42)
Case II.(A.2) is a special case of this one where all catch-up sequences are of length one. In the worst-case scenario, the catch-up sequence consists of an entire iteration. This occurs when qt A = pt B ; thus x 2 = x 1 . So, n is the smallest integer that satisfies nx 1 ≥ nx 1 ; thus n = q-r gcd(p,q) (i.e., an entire iteration). In this case, θ A,B = 2p + q + r -gcd(p, q) + q-r gcd(p,q) -1 max j=1 (jr mod (q -r)) = 2(p + q -gcd(p, q)).

Case (III), pattern (A.3):

The proof follows the same scheme as that of case III.(A.2). Sequence (β j ) takes two value; ∀j. β j ∈ q-r r , q-r r . Once β j = q-r r , an overflow will propagate from this block to the subsequent blocks. To know how many firings of B in the catch-up sequence finish before the start of any firing of A, we may look at the enabling pattern of the graph A

t A t B ----→ B. Since t A ≥ t B and t B > 2r , this enabling pattern is A B k β j ; A B k+1 where β j = jx 2 -(j -1)x 2 -1 with x 2 = t B
r . We also put x 1 = q r . If a catch-up sequence starts at the j th block, then it will end at some block (j + n -1) if

Inria and only if

n i=1 β i ≤ j+n-1 i=j β i ; i.e., n is the smallest integer that satisfies nx 2 ≤ (j -1)x 1 + nx 1 -(j -1)x 1 (43)
If (j -1)q = ar + b, then the previous equation can be rewritten as nx 2 + b r ≤ nx 1 + b r . This implies that n is maximal when b is minimal and not null; i.e., b = gcd(p, q). However, this does not imply that the (j -1) th block such that (j -1)r mod r = gcd(p, q) is actually a catchup point. To prove that we need to show that ∃m ≤ (j -1).

m i=1 β i > j-1 i=j-m β i ; i.e., mx 2 > (j -1)x 1 -(j -1)x 1 -mx 1 ; which can be rewritten as mx 2 > mx 1 -gcd(p,q) r +1 = mx 1 . But, this is impossible because x 2 ≤ x 1 .
If a catch-up point occurs at the j th block, then the value of δ i is equal to 2p + β 1 r + j i=2 (β 1 r + (r -q)) = 2p+(q -r)+ j i=1 (β i r +(r -q)) = 2p+(q -r)+r( jx 1 -jx 1 ). Its maximum occurs when jq mod r = gcd(p, q); hence at the catch-up point before the maximal catch-up point; and it is equal to 2p + q -gcd(p, q). Furthermore, since any catch-up sequence is a prefix of the maximal catch-up sequence, the worst-case occurs inside this maximal sequence. Therefore, θ A,B = 2p + q -gcd(p, q)+(

n max j=1 j(r -q) + r j i=1 β i ) + (q -r) = 2p+2q -r -gcd(p, q)+r n max j=1 ( jx 2 -jx 1 ).
According to Eq. ( 43), the maximal n is the smallest integer such that nx 2 ≤ nx 1 . Hence, ∀j < n. jx 2 > jx 1 . but, we know that ∀j. jx 2 ≤ jx 1 (because x 2 ≤ x 1 ). Therefore, ∀j < n. jx 2 = jx 1 . When j = n, we have that jx 2 -jx 1 ≤ 0; hence it can be excluded from the equation. So,

θ A,B = 2p + 2q -gcd(p, q) - n-1 min j=1 (jq mod r) (44)
In the worst-case scenario, the maximal catch-up sequence consists of an entire iteration. This occurs when qt A = pt B . Indeed, in this case, we have that x 2 = x 1 . So, n is the smallest integer that satisfies nx 1 ≤ nx 1 ; thus n = r gcd(p,q) . Therefore, θ A,B = 2p + 2q -gcd(p, q)r gcd(p,q) -1 min j=1 (jq mod r) = 2(p + q -gcd(p, q)).

Case (III), pattern (B.2):

Sequence (γ j ) takes two values; ∀j. γ j ∈ p-r r , p-r r . Once γ j = p-r r , an overflow will propagate from this block to the subsequent ones. If a catch-up sequence starts at the j th block, then it will end at some block (j + n -1) if and only if

n i=1 γ i ≥ j+n-1 i=j γ i with γ j = jt A r -(j-1)t A r -1 where r = t B -kt A . So, n is the smallest integer that satisfies nx 2 ≥ (j -1)x 1 + nx 1 -(j -1)x 1 (45)
where x 1 = p r and x 2 = t A r . If we put (j-1)p = ar+b, then the previous equation can be rewritten as nx 2 ≥ nx 1 + b r . This implies that n is maximal when b is maximal; i.e., b = r -gcd(p, q). We need to prove that the (j -1) th block such that (j -1)p mod p = r -gcd(p, q) is actually a catch-up point. To prove that, we need to show that ∃m ≤ (j -1). i.e., mx 2 < mx 1 + gcd(p,q) r -1 = mx 1 . But, this is impossible because

x 2 ≥ x 1 .
If a catch-up point occurs at the j th block, then the value of δ i is equal to 2(k + 1)p + j i=1 ((pr)-γ i r)+(r-p) = p+2q -r+r(jx 1 -jx 1 ). Its maximum occurs when jp mod r = r-gcd(p, q) (i.e., at the block before the maximal catch-up sequence) and it is equal to p + 2q -gcd(p, q). Since any catch-up sequence is a prefix of the maximal catch-up sequence, we have that θ

A,B = p+2q-gcd(p, q)+(p-r)+ n-1 max j=1 j(p -r) -r j i=1 γ i = 2p+2q-r-gcd(p, q)+r n-1 max j=1 (jx 1 -jx 2 ).
According to Eq. ( 45), the maximal n is the smallest integer such that nx 2 ≥ nx 1 . Hence, ∀j < n. jx 2 < jx 1 . But, we know that ∀j. jx 2 ≥ jx 1 (because x 2 ≥ x 1 ). Thus, ∀j < n. jx 2 < jx 1 . Therefore,

θ A,B = 2p + 2q -r -gcd(p, q) + n-1 max j=1 (jp mod r) (46)
In the worst-case scenario (i.e., x 2 = x 1 ), n is the smallest integer such that nx 1 ≥ nx 1 .

Thus, n = r gcd(p,q) . Therefore, θ A,B = 2p + 2q -r -gcd(p, q) + r gcd(p,q) -1 max j=1 (jp mod r) = 2(p + qgcd(p, q)).

Case (III), pattern (B.3):

Sequence (λ j ) takes two values; ∀j. λ j ∈ r p-r , r p-r

. Once λ j = r p-r , an overflow will propagate from this block to the subsequent ones. If a catch-up sequence starts at the j th block, then it will end at some block (j + n -1) if and only if

n i=1 λ i ≤ j+n-1 i=j λ i with λ j = jr t A -r -(j-1)r t A -r
. So, n is the smallest integer that satisfies

nx 2 ≤ (j -1)x 1 + nx 1 -(j -1)x 1 (47)
where x 1 = r p-r and x 2 = r t A -r . If we put (j -1)r = a(p -r) + b, then the previous equation can be rewritten as nx 2 + b p-r ≤ nx 1 + b p-r . This implies that n is maximal when b is minimal but not null; i.e., b = gcd(p, r). However, this does not imply that the (j -1) th block such that (j -1)r mod (p -r) = gcd(p, q) is actually a catch-up point. To prove that we need to show that ∃m ≤ (j -1).

m i=1 λ i > j-1 i=j-m λ i ; i.e., mx 2 > 1 + mx 1 -gcd(p,q) p-r = mx 1 . But, this is impossible because x 2 ≤ x 1 .
If a catch-up point occurs at the j th block, then the value of δ i is equal to 2

(k + 1)p + (λ 1 -2)(p -r) + j i=2 (λ i (p -t) -r) = 2q + r + (p -r)( jx 1 -jx 1 )
. Its maximum occurs when jr mod (p -r) = gcd(p, q) (i.e., just before the maximal catch-up sequence) and it is equal to 2q + p -gcd(p, q). Since any catch-up sequence is a prefix of the maximal catch-up sequence, we have that θ A,B = 2q + p -gcd(p, q) + (r

Inria

+ n max j=1 j i=1 (λ i (p -r) -r) ) = 2q + p + r -gcd(p, q) + (p -r) n max j=1 ( jx 2 -jx 1 ).
According to Eq. ( 46), n is the smallest integer such that nx 2 ≤ nx 1 . Hence, ∀j < n. jx 2 > jx 1 . But, we know that ∀j. jx 2 ≤ jx 1 (because x 2 ≤ x ). Thus, ∀j < n. jx 1 = jx 1 . When j = n, we have that jx 2 -jx 1 ≤ 0; hence it can be excluded from the equation. So,

θ A,B = 2p + 2q -gcd(p, q) - n-1 min j=1 (jr mod (p -r)) (48)
Proof. (Property 4.

3) The minimal buffer size of G -1 for maximal throughput is θ B,A . That is, the graph B q p --→ A with a backward edge A p q --→ B with θ B,A initial tokens, achieves the maximal throughput. Prop. 3.1 ensures that the dual graph (and therefore G) have the same throughput. This throughput is also maximal since if there exists another number of tokens allowing a better throughput for G, by duality it would also represent a better throughput for G -1 : a contradiction. Similarly, this number of tokens is minimal since if there exists θ A,B < θ B,A allowing the same maximal throughput, by duality θ A,B would also achieve a maximal throughput for G -1 which contradicts the minimality of θ B,A . Therefore, the minimal buffer size for G needed to achieve maximal throughput is equal to θ B,A .

Proof. (Property 4.4)

The initial buffer state of the graph is s

0 = d θ A,B
. Firstly, we prove that there is a live schedule (which consists of x firings of A and y firings of B) that transforms the initial state s 0 to state s 1 = d mod gcd(p, q) θ A,B + d -d mod gcd(p, q) .

Though equation d + xp -yq = d mod gcd(p, q) is a feasible equation [Using Bézout identity], this does not imply the existence of a live schedule. The schedule is constructed as follows. Initially, there are σ 0 = d tokens in the channel A → B. After firing B as much as possible, the number of remaining tokens is σ 1 = d mod q. Since the graph is live, A can fire at least once. Then, actor B is fired as much as possible; and the number of remaining tokens is σ 2 = (σ 1 + p) mod q. The process can be repeated infinitely; and the sequence of number of remaining tokens is σ n = (σ n-1 + p) mod q. Since (a mod b + c) mod b = (a + c) mod b, we can put σ n = (d + (n -1)p) mod q. The question now is whether there exists n such that σ n = d mod gcd(p, q). The answer is yes [using Bézout identity]. So, state s 1 is reachable from state s 0 . Therefore, if the ASAP execution does not achieve the maximum throughput starting from s 1 , then it cannot do that starting from s 0 .

Secondly, for a graph with d mod gcd(p, q) on the forward edge, θ A,B tokens on the backward edge are still needed to achieve the maximum throughput. This follows immediately from property B.1. The normalized channel will contain zero token since d mod gcd(p, q) < gcd(p, q).

Hence, we must have θ A,B + d -d mod gcd(p, q) ≥ θ A,B .

Property B.1 (Canonical form). Let p = p gcd(p,q) and q = q gcd(p,q) . Replacing any channel A p q --→ B with d initial tokens in the graph by a channel A p q ---→ B with d gcd(p,q) initial tokens, does not alter the ASAP execution of the graph.

Proof. (Property B.1)

The case when gcd(p, q) divides d is trivial. The other case is less evident. Firstly, know that the new rates need to have a ratio equal to p q (since i tends to infinity, any variation from this ratio will give eventually different results). So, we take the new rates as np and nq and we have to find the minimum values of n, x ∈ N such that ∀i.

iq

-d p = inq -x np (49)
Eq. 49 means that the data-dependencies created by both channels are the same. But, we have inq -x np = iq-d p + nd-x gcd(p,q) np . Let r i = (iq -d) mod p. We have that ∀i. r i = 0 since gcd(p, q) does not divide d. Thus, Eq. 49 can be rewritten as ∀i. 1 = ri p + nd-x gcd(p,q) np ; and hence ∀i. 0 < ri p + nd-x gcd(p,q) np ≤ 1. So, we have

max i ri+d-p gcd(p,q) ≤ x n < min i ri+d gcd(p,q) . But, ∀i. gcd(p, q) divides r i + d [Using Bézout identity]. Furthermore, we have that max i r i - min i r i = p -gcd(p, q) [Using Bézout identity]. So, d+min i ri gcd(p,q) -1 ≤ x n < d+min i ri
gcd(p,q) . Therefore, x n lies between two successive integers. Hence, the minimum value of n is 1, while x takes the value d+min i ri gcd(p,q) -1.

Since min i r i is the smallest integer that makes gcd(p, q) divides d + min

B.3 Multi-iteration latency

Proof. (Property 4.5) The three cases (I), (II) and (III) are those described in the previous section (see the proof of Property 4.2).

• Case (I): All the firings of B that have been enabled before the last enabling point in the iteration (i.e., the end of the last firing of A) will finish by that point. According to the enabling patterns (Fig. 8), the last firing of A enables p/q firings of B. Hence, ∆ A,B = p/q t B . Inria i.e., as the difference between the sum of execution times of A over the first (j -1) blocks minus the sum of execution times of B over the same blocks. The maximum of this difference occurs at the last catch-up point before the end of the iteration. Therefore, we can put ∆ A,B = t A + r + t B r -qr gcd(p, q) + (t B -r )

N -1 max i=0 (ix 2 -ix 1 )
So, ∆ A,B can be upper bounded by t A +r + t B r-qr gcd(p,q) +(t B -r )

N -1 max i=0 (ix 2 -ix 1 )+(t B -r ) N -1 max i=0
(ix 1ix 1 ) = t A +r + t B r-qr gcd(p,q) +(t B -r )(N -1)(x 2 -x 1 )+(t B -r ) q-r-gcd(p,q) q-r = t A + (t B -r )(q-gcd(p,q)) q-r . Therefore, ∆ A,B ≤ t A + (t B -r )(qgcd(p, q)) q -r

In the worst-case scenario (i.e., when qt A = pt B ), we have that t B -r q-r = t B q and hence ∆ A,B = t B q (p + q -gcd(p, q)). Case (III), pattern (A.3): Similarly to case (A.2), we suppose that the last catch-up sequence in the iteration starts at the j th block and we put N = r gcd(p,q) . The number of remaining firings of A is equal to If x 1 = q r and x 2 = t B r , then ∆ A,B = (k + 1)t B + t B r-qr gcd(p,q) + r ( (j -1)x 1 -(j -1)x 2 ). Hence, ∆ A,B = (k + 1)t B + t B r -qr gcd(p, q) + r

N -1 max i=0 ( ix 1 -ix 2 )
Hence, ∆ A,B ≤ (k + 1)t B + t B r-qr gcd(p,q) + r Similarly to case (B.2), the constructed sequence is illustrated in Fig. 48 where σ 1 = kt A -t B s and σ 2 = (k + 1)t A -t B s . p (p -r -gcd(p, q)). Hence, t 0 B s = t A + t B -t A p gcd(p, q).

We also have t 0 B = t B + min

j jσ 1 + σ 2 j i=1 λ i = t B .

Case (II)+(III):

pattern (A.2): As illustrated in Fig. 49, firings of B in a catch-up sequence are consecutive and the maximum of f B (i) -it B s occurs at the first firing (since both σ 1 = kt B -kt B s and σ 2 = (k + 1)t B -(k + 1)t B s are non-positive). Thus, it is sufficient to look only at the first firing after each catch-up point. At these points, the value of f B (i) -it B s is equal to that of case (I) pattern (A.2) in which the maximum occurs when jr mod (q -r) = q -r -gcd(p, q); hence at the beginning of the maximal catch-up sequence. Hence, Eq. ( 21) is also valid in this case. Since both σ 1 and σ 2 are non-positive, the minimum of f B (i) -it B s occurs at the last firing in a batch of consecutive firings. Therefore, it is sufficient to look only at the last firing of each catch-up sequence. But, as the start of the last B k of the catch-up sequence is not synchronous with the start of a firing of A (unlike in case (I) pattern (A.2)), f B (i) -it B s computed in this In case (I) pattern (B.3), the maximum of f B (i)-it B s occurs when jr mod (p-r) = gcd(p, q); hence at the beginning of the maximal catch-up sequence. Therefore, Eq. ( 21) is also valid in this case. To compute the minimum, we look only at the last firing of each batch of consecutive firings of B. Let us first consider case (II), illustrated in Fig. 51 where σ 1 = t B -t B s < 0 and X is the smallest integer such that r + X(r -t A ) ≤ 0 (i.e., the overflow is caught up). So, X =

Actually, it is possible to show that this equation is equivalent to Eq. ( 54). According to that equation and after substituting p r by one and p mod r by (p -r) (since p < 2r in case B.3), we have that t 0 B = t B + min{σ 2 , σ 1 -σ 1 }. So, we need to prove that min{σ 2 , Xσ 1σ 1 } = min{σ 2 , σ 1 -σ 1 }. Hence, we have to prove that σ 2 ≤ Xσ 1 -σ 1 ⇒ σ 2 ≤ σ 1 -σ 1 and σ 2 > Xσ 1 -σ 1 ⇒ X = 1. The first one is trivial since σ 1 is negative and X ≥ 1. The second one is less evident. Suppose that σ 2 > Xσ 1 -σ 1 when X = 2. So, σ 2 > 2σ 1 -σ 1 will imply that t A > 2r , and hence X = r t A -r = 1; i.e., contradiction.

Let us now consider case (III). As a lower bound, we assume that each sub-iteration is a catch-up sequence. Therefore, the previous equation is a valid lower bound. Actually, simulation shows that this is a precise bound. --→ A with the same buffer size. The producer B in G -1 imposes the highest load.

C.2 Backward linearization

As illustrated in Fig. 52(a), there is a prologue phase in the schedule of G, composed of i 0 firings of A and j 0 firings of B, after which the schedule of G is similar to that of G -1 . In some cases, the firings of A after the prologue can be a little bit delayed compared to those of A in the dual graph. However, assuming an exact similarity will be an under-approximation of the start times of A, and hence an over-approximation of the input-output latency.

in order to synchronize it with the schedule of the second graph. This will prevent the actors of the first graph from being blocked during the extra delay s 2 -s 1 . By using this technique at each join node, we can compute the desired schedule.

Proof. (Property 6.2) As in the proof of Property 6.1, we will construct a schedule of graph G = such that an actor never gets idle once it starts. Initially, the size of each channel A p q --→ B is equal to θ u A,B . For both chains, we construct a linear schedule as in the proof of Property 6.1. So, s 1 (resp. s 2 ) denotes the start time of the last actor A n in the schedule of the first (resp. second) chain.

Since both schedules have the same source A 1 and same sink A n , we have to synchronize both schedules such that the firings of A 1 and A n in both schedules coincide. Hence, A 1 must start at time zero while A n needs to start at time max(s 1 , s 2 ).

If s 2 > s 1 , the extra delay (s 2 -s 1 ) imposed by the second chain will force actors of the first chain to block (if buffer sizes are not increased), which will finally decrease the throughput of the graph.

Let A n-1 p q --→ A n be the last channel in the first chain. Increasing the size of this channel by s2-s1 t A n-1 p will allow actor A n-1 to fire consecutively during the extra delay (s 2 -s 1 ). That is, the impact of the second chain on the first one is avoided.

D.2 Improving the upper bounds

Proof. (Property 6.3) Suppose that the chain follows the descending order: ∀i. z Ai t Ai ≥ z Ai+1 t Ai+1 . The size θ A1,A2 allows actor A 1 to run consecutively, which is the same behavior as when there is no constraint on buffer sizes. Then, the size θ A2,A3 allows actor A 2 to fire as soon as it is enabled by actor A 1 . Actually, if there were no dependence from A 1 to A 2 , the size θ A2,A3 would allow actor A 2 to run consecutively. The same reasoning shows that all actors are fired as it there were no buffer size constraints. Therefore, the chain achieves its maximal throughput. The case of ascending order can be easily dealt with using the duality theorem. HSDF(g). Therefore, any maximal path in the DAG obtained by unfolding HSDF(G) for i iterations will be found in the DAG obtained by unfolding some graph g ∈ G(G) for i iterations. Indeed, since G does not contain any cycle (except self-edges), there will be no path from actor A to B in HSDF(G) unless both actors belong to the same chain.

E Latency computation for acyclic graphs

Inria

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES

Figure 1 :

 1 Figure 1: Symbolic and numerical analyses.

Figure 3 :

 3 Figure 3: ASAP schedule of graph A 3 2

Figure 6 :

 6 Figure 6: Illustration of the duality theorem.

Figure 7 : 5 -

 75 Figure 7: An ASAP execution of A 8 5 --→ B with t A = 20 and t B = 7.

Property 4 . 1 .

 41 Fig. 8 gathers all possible enabling patterns for the graph A p q --→ B.

4. 2

 2 Minimum buffer size for maximum throughput of A p q

t

  B -r ≥ nr q-r and r = t A -kt B . Cases III.(A.3), III.(B.2), III.(B.3) see the proof in the appendix.

Figure 9 :

 9 Figure 9: Minimum buffer size θ A,B when z A t A ≥ z B t B .

Note 4 . 1 .

 41 If actors A and B impose the same load (i.e., z A t A = z B t B ), then all four cases (III.A.2, III.A.3, III.B.2 and III.B.3) give the same upper bound :

Property 4 . 5 .

 45 If z A t A ≥ z B t B ,then the value of ∆ A,B is given by the symbolic formulas of Fig.11.

  Cases III.(A.3), III.(B.2), III.(B.3): see the proof in the appendix.

Figure 11 :

 11 Figure 11: Multi-iteration latency: value of ∆ A,B .

Figure 12 :

 12 Figure 12: Multi-iteration latency L G (2), case z A t A < z B t B (p = 5, q = 3, t A = 14,t B = 12).

Figure 13 :

 13 Figure 13: Upper bound linearization (p = 8, q = 5, tA = 20, tB = 7).

Fig. 14 shows the symbolic formulas for t 0 B

 0 . The reader may refer appendix C.1 for details.

Figure 15 :

 15 Figure 15: Backward lower bound linearization.

Figure 16 : 4 --→ B 4 2 -

 1642 Figure 16: ASAP execution of the graph G b = A 3 4 --→ B 4 2 --→ C.

Figure 18 :

 18 Figure 18: ASAP execution of G d .

  load

Figure 19 :

 19 Figure 19: Transformation of a chain to a form.

ALGORITHM 2 :

 2 Exact algorithm for minimum buffer sizes problem Input: SDF graph G, upper bound solution S u . Output: Minimum buffer sizes distribution S b . S b = S u ; B = {B(S)|B(S ) < B(S) ≤ B(S u )} in ascending order; mingcd = min A p q --→B∈E (gcd(p, q)); begin = 1; end = |B|; while begin < end -1 do middle = (begin + end)/2 ; k = middle; found = false; while True do Dist = {S|B(S) = B[k]}; if ∃S ∈ Dist, TG(S) is maximal then found = true; S b = S; break; else if k-1 > begin ∧ B[k -1] + mingcd > B[middle] then k--; else break ; if found then end = k ; else begin = middle; return S b ;

Example 6 . 1 . 14 ----→ B 15 9 -

 61149 Consider graph G = A 8 ---→ C with t A = 7, t B = 12 and t C = 13. The repetition vector of this graph is z = [21, 12, 20], and the minimal period is P G = z C t C = 260. The upper bound buffer sizes distribution is S u = [θ u A,B = 40, θ u B,C = 42] with B(S u ) = 82. The lower bound distribution is S = [20, 21] with B(S ) = 41. Algorithm 2, illustrated in Fig. 20, starts by checking distributions at the middle between B(S u ) and B(S ), i.e., distributions such that B(S) = 56 (solid blue line in Fig. 20). There are three possible distributions: [20, 36], [26, 30] and [32, 40]. Neither of them allows to achieve the maximal throughput. Distribution with B(S) < 56 and B(S) + mingcd > 56, i.e., distributions [22, 33], [28, 27] and [34, 31] (dashed blue line), are not dominated by the already checked distributions, and need to be checked. Neither of them allows to achieve the maximal throughput. This implies that all distributions in the bottom part (dominated by the checked distributions) will not allow a maximal throughput. Therefore, the dichotomic search moves to the upper part. At the middle of the upper part (green line), there is a distribution S = [26, 36] (red dot the green line) that allows a maximal throughput. The algorithm hence proceeds to the bottom part. The process continues: magenta lines (miss), brown line (hit at [26, 33], red dot). The algorithm stops and returns S b = [26, 33].

Figure 20 :

 20 Figure 20: Illustration of Algorithm 2.

Figure 21 : 5 -

 215 Figure 21: Computation of LA→C of a chain A 2 5 ---→ B 3 1 ---→ C.

Figure 22 : 5 -

 225 Figure 22: Computation of LA→C of a chain A 2 5 ---→ B 3 1

Figure 23 :

 23 Figure 23: Input-output latency computation.

Figure 24 :

 24 Figure 24: MAX vs. MIN.

Figure 25 :

 25 Figure 25: MAX vs. MIN.

Figure 26 :

 26 Figure 26: OPT vs. exact solution.

Figure 27 :

 27 Figure 27: Multi-iteration Latency computation.

Figure 28 :

 28 Figure 28: Input-output latency computation.

Figure 29 :

 29 Figure 29: SDF-to-HSDF transformation of a graph and its dual.

Property A. 1 .

 1 Let G = A p q --→ B. Graphs HSDF(G) and HSDF(G -1 ) are dual to each other. Inria Proof. (Property A.1) The SDF-to-HSDF transformation of A p q

  Figure 30: Duality of

B. 1

 1 Enabling patternsProof. (Property 4.1)RR n°8742• Case (A.1): (p = kq) The repetition vector is z =[1, k]. Each firing of A enables k firings of B and the enabling pattern is A B k .

prologue block 1 Figure 31 :

 131 Figure 31: Illustration of sequence (δ j ) in case (I.1) and pattern (A.2).

Figure 32 :

 32 Figure 32: Case (I) pattern (A.3).

Figure 33 :

 33 Figure 33: Case (I) pattern (B.2).

Figure 35 : 5 -

 355 Figure 35: An ASAP execution of A 8 5 --→ B with t A = 13 and t B = 7. Patterns (A.1) and (B.1) are not possible in case (II).

Figure 36 :

 36 Figure 36: Case (II) pattern (A.2).

Figure 37 :

 37 Figure 37: Case (II) pattern (A.3).

  Similarly to case I.(B.2), we compute sequence (δ i ) (see Fig.38). So, θ A,B = 2(k + 1k + 1)p + (rgcd(p, q)) = 2p + 2q -r -gcd(p, q).

Figure 38 :

 38 Figure 38: Case (II) pattern (B.2).

Figure 39 :

 39 Figure 39: Case (II) pattern (B.3).

Figure 40 : 5 -

 405 Figure 40: An ASAP execution of 8 5 --→ B with t A = 23 and t B = 14. The obtained formulas are the following (patterns A.1 and A.2 are not possible):

(

  t A -kt B . Case III.3. B.2 θ A,B = 2p + 2q -r -gcd(p, q) + Inria where n is the smallest positive integer such that nt A r ≥ np r and r = t B -kt A . Case III.4. B.3 θ A,B = 2p + 2q -gcd(p, q) -jr mod (p -r))

Figure 41 :

 41 Figure 41: Case (III) pattern (A.2).

a

  catch up point a catch up point

Figure 42 :

 42 Figure 42: Case (III) pattern (A.3).

Figure 43 :

 43 Figure 43: Case (III) pattern (B.2).

Figure 44 :

 44 Figure 44: Case (III) pattern (B.3).

i

  r i , we put x = d gcd(p,q) .

  while the number of remaining firings of B is equal to (k+1)+ N i=j(kβ i +(k+1)). Therefore, ∆ A,B = (k + 1)t B + (N -j + 1)(t B -r ) -r N i=j β i .

N - 1 max i=0 ( ix 1 - 1 max i=0 (ix 1 -(ix 2 -ix 1 )∆

 1i=011i=0121 Figure 47: Case (I) pattern (B.2): values of f B (i) -it B s .

Figure 48 :

 48 Figure 48: Case (I) pattern (B.3): values of f B (i) -it B s .

Figure 49 :

 49 Figure 49: Case (III) pattern (A.2): values of f B (i) -it B s .

Figure 51 :

 51 Figure 51: Case (II) pattern (B.3): values of f B (i) -it B s .

Proof. (Property 5 . 1 ) 5 -

 515 The key element to compute the backward lower bound linearization lies in the following observation, which relates backward linearization to forward linearization. Fig. 52(a) shows the ASAP schedule of graph G = A 8 -→ B such that t A = 5, t B = 6 and the buffer size is equal to 22. Actor B imposes the highest load. Fig. 52(b) shows the ASAP schedule of the dual graph G -1 = B 5 8

E. 1

 1 Multi-iteration latency of acyclic graphs Proof. (Property 7.1) This property follows immediately form the compositionality of the SDFto-HSDF transformation, i.e., HSDF(G) = g∈G(G)

  Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

  is equal to θ u A,B . This upper bound does not depend on the execution times of If If z A t A ≥ z B t B and the channel A

	the actors. Therefore, it can be used as a safe buffer size if the execution times of actors are
	unknown.
	Property 4.4. p q
	Inria

  p 1 p 2 t C otherwise Since P G = max(t A , p 1 t B , p 1 p 2 t C ), it is easy to check for all three possible maximal values (t A , p 1 t B or p 1 p 2 t C ) that P m holds for m ≥ 3 but not for m < 3.Note 7.1. Instead of analyzing separately all the chains of a DAG, it is more efficient to use the compositionality of our approach to prevent some recomputations. For instance, if we have two chains A → B → D → E and A → C → D → E (i.e., actor D is a join), then we merge the information that comes from both paths: LA→D is taken as the maximum of LA→B→D and LA→C→D .

Note 7.2. According to the duality theorem, the multi-iteration latencies of a chain A → • • • → Z and its dual are equal. However, our method may give different approximate values, i.e., LA→Z = LZ→A . Therefore, for a given chain, we analyze both the chain and its dual and return min{ LA→Z , LZ→A }. Again, since both computations have a linear complexity, this is not costly.

Table 1 :

 1 Experimental results for real benchmarks.

	graph	# actors	A z A	load shape	Upper bound Optimal size Heuristic
	modem	6	37		32	20	30
	sample con.	6	612		60	34	57
	H.263 dec.	4	1190		2378	1257	1257
	FFT	11	94		992	504	808
	TDE	27	2867		7328	3680	5272

Table 2 :

 2 Multi-iteration latency computation for real benchmarks.

	graph	P G	L G (1)	LG (1)/L G (1) LG (2)/L G (2)
	(a) modem	32	62	1	1
	(b) sample con.	960	1000	1.022	1.011
	(c) H.263 dec.	332046	369508	1	1
	(d) FFT	78844	94229	1	1
	(e) TDE	17740800 19314069	1	1

  A -r . Since σ 1 is negative, we have that t 0 B = min{t B + Xσ 1 -σ 1 + min + σ 2 } = t B + min{Xσ 1 -σ 1 , σ 2 }. Therefore,

	f B (i) =	qt A p	i + t B + min	p -r r	t A ,	r t A -r	pt B -qt A p	+	r p	t A

r t j jσ 1 + σ 2 j i=1 λ i , t B + min j jσ 1 + σ 2 j i=1 λ i

RR n°8742

If there are many, then we take any of them.

Without lost of generality, tokens are assumed to have the same size.Inria

Note that if (α j ) ((β j ), (γ j ) or (λ j )) takes only one value, then case (III) is impossible.RR n°8742

• Case (II): All the firings of B that have been enabled during one block will finish by the beginning of the next block. Hence, we have to consider the last block in each enabling pattern. There are four cases (A.2), (A.3), (B.2), and (B.3).

In case (A.2), the last block is of the form A B k ; A B k+1 r q-r . Therefore, ∆ A,B = r q-r (k + 1)t B -r q-r -1 t A . In case (A.3), the last block is of the form A B k q-r r

; A B k+1 . Thus, ∆ A,B = (k+1)t B . Both cases (A.2) and (A.3) can be unified in Eq. [START_REF] Nogues | A DVFS based HEVC decoder for energy-efficient software implementation on embedded processors[END_REF].

In case (B.2), the last block is of the form A k+1 B ; A k B p-r r

. Hence, ∆ A,B = p-r r

In case (B.3), the last block is of the form A k+1 B r p-r ; A k B . Therefore, ∆ A,B = 2t B -kt A . Both cases (B.2) and (B.3) can be unified in Eq. [START_REF] Skelin | Worst-cas throughput analysis for parametric rate and parametric actor execution time scenario-aware dataflow graphs[END_REF].

• Case (III): The obtained formulas are:

Case III.

Case III.1. Let r = t A -kt B and n = q-r gcd(p,q) ∆ A,B = t A + r + t B r -qr gcd(p, q)

Case III.

Case (III), pattern (A.2): Suppose that the last catch-up sequence in the iteration starts at the j th block. Thus, all the remaining firings of B are consecutive. Let us put N = q-r gcd(p,q) . The number of remaining

We can rewrite (t B -r )((j -1)x 2 -(j -1)x 1 ) as

Case (III), pattern (B.3): Again, we suppose that the last catch-up sequence in the iteration starts at the j th block and we put N = p-r gcd(p,q) . The number of remaining firings of A is equal to

while the number of remaining firings of B is equal to (N -j + 3)

Hence,

Forward linearization

Proof. (Forward lower and upper bound linearizations) We will show only one case, namely case (I) with pattern (A.2). In this case, since

. So, to compute the upper bound and the lower bound linearizations, we need to compute the maximum and the minimum of sequence (f B (i) -i qt A p ) respectively.

Case (I):

Case (I), pattern (A.1):

We have that f B (ik + j) = (i + 1)t A + jt B where 1 ≤ j ≤ k. Hence, t 0

Case (I), pattern (A.2):

For a batch of consecutive firings of B, the maximum of function f B (i) -it B s occurs at the first firing. The sequence of values that takes this function (for the first firing of each batch) is illustrated in Fig. 45 where

. Similarly, to compute t 0 B we need to consider the last firing in each batch of consecutive firings of B. The minimum of the constructed sequence is t B +min{kt B +σ 1 +min

Case (I), pattern (A.3):

Similarly to case (I) pattern (A.2), we construct the sequence f B (i) -it B s . See Fig. 46 where

p gcd(p, q). To compute t 0 B we need to consider the last firing in each batch of consecutive firings of B. So,

Case (I), pattern (B.1):

We have that f

Case (I), pattern (B.2):

The sequence of values of f B (i) -it B s is illustrated in Fig. 47 where

We also have t 0

Case (I), pattern (B.3):

Inria case is larger than or equal to what is computed by the formula of case (I) pattern (A.2);

i.e., kt B + σ 1 + jσ 1 + jr q-r σ 2 . So, this equation can be taken as a lower bound. However, since its minimum (kt B + σ 1 ) occurs also in case III.A.2 (see the first B k in Fig. 49), the solution of case (I) pattern (A.2) is also exact in this case. pattern (A.3):

In case (I) pattern (A.3), the maximum occurs when jq mod r = gcd(p, q); i.e., at the beginning of the maximal catch-up sequence. Therefore, Eq. ( 21) is also valid in this case.

Furthermore, the minimum of kt B + σ 1 + min j jσ 2 + σ 1 j i=1 β i (Case (I) pattern (A.3)) also occurs in this case (for the first B k ). Hence, the solution of case (I) (A.3) is also exact in this case.

pattern (B.2):

For a batch of consecutive firings of B, the maximum of f B (i) -it B s occurs at the first firing while its minimum occurs at the last firing. This is illustrated in Fig. 50 where In case (I) pattern (B.2), the maximum of f B (i) -it B s occurs when jp mod r = r -gcd(p, q); i.e., at the beginning of the maximal catch-up sequence. Therefore, Eq. ( 21) is also valid in this case.

To compute the minimum, we look only at the last firing of each batch of consecutive firings of B. As a lower bound, we assume that each sub-iteration is a catch-up sequence. Hence,

Actually, simulation shows that this lower bound is precise even when the lengths of catch-up sequences are longer than one. Recall that a buffer of size equal to d is modeled by adding a backward edge with d initial tokens. At the boundary of the prologue phase, the forward edge will contain d tokens while the backward edge will be empty; and this is exactly the dual graph G -1 . The fact that all initial tokens on the backward edge (i.e., d tokens) are transferred to the forward edge is modeled by the following equation

pattern (B.3):

This Diophantine equation is always solvable since the buffer size must be a multiple of gcd(p, q) 5 . Let fA (i) denote the finish time of the i th firing of A in the ASAP schedule of the dual graph G -1 . Hence, we have ∀i ≥ 1. fA (i) + s B (j 0 + 1)

which means that the finish time of the (i + i 0 ) th firing of A in G can be under-approximated by the finish time of the corresponding firing of A in the dual graph, i.e., fA (i), plus the shift due to the prologue phase, i.e., s B (j 0 + 1). As described in Section 5.1.2, it is possible to compute a forward lower bound linearization of the firings of A in the dual graph G -1 since A is the consumer. We can then put fA (i) ≥ it A + t0

A . Eq. ( 58) is hence a valid lower bound linearization. 58) is also a valid lower bound for all i ≤ i 0 .

D Buffer Sizing for Acyclic graphs

D.1 Safe upper bounds

Proof. (Property 6.1) For a better understanding, we first present the proof for chains. Let G be the chain {A

according to Eq. ( 5), the minimal period 5 If the buffer size is not a multiple of gcd(p, q), then it can be diminished without affecting the ASAP schedule.

Inria

of G is P G = max i=1..n {z Ai t Ai }. The period and therefore the throughput remain the same if the execution time of each actor A i is considered to be P G z A i

. Let G = be the version of G where all actors have the same load as the maximum load in G. Then G and G = have the same period and throughput.

If the size of each buffer A i pi qi ---→ A i+1 in G = is θ u Ai,Ai+1 = 2(p i + q i -gcd(p i , q i )), then G = still achieves the maximal throughput. Indeed, size 2(p 1 + q 1 -gcd(p 1 , q 1 )) for the first channel allows both A 1 and A 2 to run consecutively in the steady state (see Eq. ( 13)). Similarly, size 2(p 2 + q 2 -gcd(p 2 , q 2 )) for the second channel allows both A 2 and A 3 to run consecutively, and so on.

Since graph G = with these buffer sizes achieves the maximal throughput, reducing the execution times of actors in G = to their original values will never decrease the throughput of the graph thanks to the monotonicity of the self-timed execution. Hence, graph G with these buffer sizes achieves the maximal throughput.

To prove the general case of graphs without undirected cycles, it is sufficient to prove that there exists a schedule (not necessarily an ASAP schedule) of G = with period equals P G and where the size of each buffer A p q --→ B is equal to θ u A,B . In the computed schedule, each actor never gets idle once it starts.

The proof is based on the Stretch linearization method. For a graph

q (p + q -gcd(p, q)) (see Eq.( 21)). If B starts at s B = t B q (p + q -gcd(p, q)), then a buffer with size equal to θ u A,B still allows the graph to achieve the maximal throughput. Indeed, the required buffer size is equal to (see Eq. ( 7)) max j (jp -qx j ) such that x j is the number of firings of B that finish before the start of the j th firing of A. Hence x j is equal to the largest non-negative integer such that

where x 0 = max( x , 0). Hence, the required size is

Using Eq. ( 21) transitively, we can compute s An , the start time of actor A n in a chain

--------→ A n (all actors impose the same load) after delaying each actor in the chain as indicated by the linearization method. It follows that

Note that a size θ u Ai,Ai+1 for each channel in the chain will allow each actor to fire consecutively once it started. Hence, the execution will achieve the maximal throughput.

Suppose that there are two chains that start form the same root: chain A 1 A 2 . . . A n and chain A 1 A 2 . . . A n . Delaying each actor as described above still allow to construct the desired schedule. This solves the problem of trees.

Suppose that there are two channels that enter a join node E: channel C p q --→ E and channel D p q ---→ E. We have s E = max(s 1 , s 2 ) with s 1 = s C + t E q (p + q -gcd(p, q)) and s 2 = s D + t E q (p + q -gcd(p , q )). Since the original graph G does not contain any undirected cycle, graphs ↓C (obtained by restricting G to actor C and all its predecessors) and ↓D are disjoint graphs.

If s 2 > s 1 , then the schedule of graph ↓D imposes a larger delay on the start time of actor E than graph ↓C. Since we want to compute a schedule where each actor never gets idle once it starts, we have to delay the start time of the schedule of the first graph ↓C by s 2 -s 1 unit of time