Jean-Yves Marion
email: jean-yves.marion@loria.fr

Romain Péchoux
email: romain.pechoux@loria.fr

Complexity Information Flow in a Multi-threaded Imperative Language

We propose a type system to analyze the time consumed by multi-threaded imperative programs with a shared global memory, which delineates a class of safe multi-threaded programs. We demonstrate that a safe multi-threaded program runs in polynomial time if (i) it is strongly terminating wrt a non-deterministic scheduling policy or (ii) it terminates wrt a deterministic and quiet scheduling policy. As a consequence, we also characterize the set of polynomial time functions. The type system presented is based on the fundamental notion of data tiering, which is central in implicit computational complexity. It regulates the information flow in a computation. This aspect is interesting in that the type system bears a resemblance to typed based information flow analysis and notions of non-interference. As far as we know, this is the first characterization by a type system of polynomial time multi-threaded programs.

Introduction

The objective of this paper is to study the notion of complexity flow analysis introduced in [START_REF] Marion | A type system for complexity flow analysis[END_REF] in the setting of concurrency. Our model of concurrency is a simple multi-threaded imperative programming language where threads communicate through global shared variables. The measure of time complexity that we consider for multi-threaded programs is the processing time. That is the total time for all threads to complete their tasks. As a result, the time measure gives an upper bound on the number of scheduling rounds. The first contribution of this paper is a novel type system, which guarantees that each strongly terminating safe multi-threaded program runs in polynomial time (See Section 3.2 and Theorem 6). Moreover, the runtime upper bound holds for all thread interactions. As a simple example, consider the two-thread program:

x : while(X 1 == Y 1 ){skip} C ; X 1 :=¬X 1 y : while(X 1 = Y 1 ){skip} C ′ ; Y 1 :=¬Y 1
This example illustrates a simple synchronization protocol between two threads x and y. Commands C and C ′ are critical sections, which are assumed not to modify X and Y . The operator ¬ denotes the boolean negation. Both threads are safe if commands C and C ′ are safe with respect to the same typing environment. Our first result states that this two-thread program runs in polynomial time (in the size of the initial shared variable values) if it is strongly terminating and safe.

Then, we consider a class of deterministic schedulers, that we call quiet (see Section 8). The class of deterministic and quiet schedulers contains all deterministic scheduling policies which depend only on threads. A typical example is a round-robin scheduler. The last contribution of this paper is that a safe multi-threaded program which is terminating wrt to a deterministic and quiet scheduler, runs in polynomial time. Despite the fact it is not strongly terminating, the two-thread program below terminates under a round-robin scheduler, if C and C ′ terminate.

x : while(X 1 > 0)

{C ; Z 1 :=0 : 1} : 1 y : while(Z 1 > 0) {C ′ ; X 1 :=0 : 1} : 1

If commands C and C ′ are safe, then this two-thread program runs in polynomial time wrt to a round-robin scheduler. The last contribution is that if we just consider one-thread programs, then we characterize exactly FPtime, which is the class of polynomial time functions. (See Theorem 7) The first rational behind our type system comes from data-ramification concept of Bellantoni and Cook [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF] and Leivant [START_REF] Leivant | Predicative recurrence and computational complexity i: Word recurrence and poly-time[END_REF]. The type system has two atomic types 0 and 1 that we called tiers. The type system precludes that values flow from tier 0 to tier 1 variables. Therefore, it prevents circular algorithmic definitions, which may possibly lead to an exponential length computation. More precisely, explicit flow from 0 to 1 is forbidden by requiring that the type level of the assigned variable is less or equal than the type level of the source expression. Implicit flow is prevented by requiring that (i) branches of a conditional are of the same type and (ii) guard and body of while loops are of tier 1. If we compare with data-ramification concept of [START_REF] Bellantoni | A new recursion-theoretic characterization of the polytime functions[END_REF][START_REF] Leivant | Predicative recurrence and computational complexity i: Word recurrence and poly-time[END_REF], tier 1 parameters correspond to variables on which a ramified recursion is performed whereas tier 0 parameters correspond to variables on which recursion is forbidden.

The second rational behind our type system comes from secure flow analysis. See Sabelfeld and Myers survey [START_REF] Sabelfeld | Language-based information-flow security[END_REF] to have an overview on information flow analysis. In [START_REF] Volpano | A sound type system for secure flow analysis[END_REF] for sequential imperative programs and in [START_REF] Smith | Secure information flow in a multi-threaded imperative language[END_REF] for multithreaded imperative programming language, Irvine, Smith and Volpano give a type system to certify a confidentiality policy. Types are based on security levels say H (High) and L (Low). The type system prevents that there is no leak of information from level H to level L, which is similar to our type system: 0 (resp. 1) corresponds to H (resp. L). In fact, our approach rather coincides with an integrity policy [START_REF] Biba | Integrity considerations for secure computer systems[END_REF] (i.e "no read down" rule) than with a confidentiality one [START_REF] Bell | Secure computer system: unified exposition and multics interpretation[END_REF]. A key property is the non-interference, which says that values of level L don't changed values of level H. We demonstrate a similar non-interference result which states that values stored in tier 1 variables are independent from tier 0 variables. See Section 4 for a precise statement. From this, we demonstrate a temporal non-interference properties which expresses that the number of unfolded (i.e. the length) while loops only depends on tier 1 variables, see Section 5. The temporal non-interference property is the crucial point to establish complexity bounds.

From a practical standpoint, an important issue is the expressivity of the class of safe multi-threaded programs. With this work and [START_REF] Marion | A type system for complexity flow analysis[END_REF], we introduce a new approach in implicit computational complexity based on a type system. This study focuses on the intrinsic mechanisms which lead to analyze computational complexity. This approach seems promising because it treats common algorithmic control structures like while-loops as well as sequential and parallel composition. Several examples are presented in Appendix. Related works. An important source of inspiration comes from Implicit Computational Complexity (ICC). Beside the works of Bellantoni, Cook and Leivant already cited, there are works on light logics [START_REF] Girard | Light linear logic[END_REF][START_REF] Baillot | Light types for polynomial time computation in lambda-calculus[END_REF], on linear types [START_REF] Hofmann | Linear types and non-size-increasing polynomial time computation[END_REF], and interpretation methods [START_REF] Bonfante | Quasi-interpretations a way to control resources[END_REF][START_REF] Marion | Sup-interpretations, a semantic method for static analysis of program resources[END_REF], just to mention a few. There are also works on resource control of imperative language like [START_REF] Jones | The expressive power of higher-order types or, life without cons[END_REF][START_REF] Jones | A flow calculus of wp-bounds for complexity analysis[END_REF][START_REF] Niggl | Certifying polynomial time and linear/polynomial space for imperative programs[END_REF]. Only a few studies based on ICC methods are related to resource control of concurrent computational models. In [START_REF] Amadio | Resource control for synchronous cooperative threads[END_REF], a bound on the resource needed by synchronous cooperative threads in a functional framework is computed. The paper [START_REF] Amadio | Feasible reactivity in a synchronous pi-calculus[END_REF] provides a static analysis for ensuring feasible reactivity in a synchronous π-calculus. In [START_REF] Madet | An elementary affine lambda-calculus with multithreading and side effects[END_REF] an elementary affine logic is introduced to tame the complexity of a modal call-by-value lambda calculus with multi-threading and side effects. There are also works on the termination of multi-threaded imperative languages [START_REF] Cook | Proving thread termination[END_REF]. In this paper, we separate complexity analysis from termination analysis but the tools on termination can be combined with our results since most of them require strong normalization of the considered process as an assumption. Finally our type system in this paper may be seen as a simplification of the type system of [START_REF] Marion | A type system for complexity flow analysis[END_REF] for imperative language but in return there is no declassification mechanism.

A complexity flow type system

A multi-threaded programming language

We introduce a multi-threaded imperative programming language similar to the language of [START_REF] Smith | Secure information flow in a multi-threaded imperative language[END_REF][START_REF] Castellani | Non-interference for concurrent programs[END_REF] and which is an extension of the simple while-imperative programming language of [START_REF] Jones | Computability and complexity, from a programming perspective[END_REF]. A multi-threaded program consists in a finite set of threads where each thread is a while-program. Threads run concurrently on a common shared memory. A thread interacts with other threads by reading and writing on the shared memory.

Commands and expressions are built from a set V of variables, and a set O of operators of fixed arity including constants (operators of arity 0) as follows:

Expressions E 1 , . . . , E n ::= X | op(E 1 , . . . , E n ) X ∈ V, op ∈ O Commands C , C ′ ::= X :=E | C ; C ′ | skip | if E then C else C ′ | while(E ){C }
A multi-threaded program M (or just program when there is no ambiguity) is a finite map from thread identifiers x , y, . . . to commands. We write dom(M ) to denote the set of thread identifiers. Note also that we do not consider the ability of generating new threads. Let V(I) be the set of variables occurring in I, where I is an expression, a command or a multi-threaded program.

Semantics

We give a standard small step operational semantics for multi-threaded programs. Let W be the set of words1 over a finite alphabet Σ including two words tt and ff that denote true and false. The length of a word d is denoted |d |. A store µ is a finite mapping from V to W. We write µ[X 1 ← d 1 , . . . , X n ← d n ] to mean the store µ ′ where X i is updated to d i .

The evaluation rules for expressions and commands are given in Figure 1. Each operator of arity n is interpreted by a total function op : W n → W. The judgment µ E e → d means that the expression E is evaluated to the word d ∈ W wrt µ. A configuration c is either a pair of store and command, µ C , or a store µ. The judgment µ C s → µ ′ expresses that C terminates and outputs the store µ ′ . µ C s → µ ′ C ′ means that the evaluation of C is still in progress: the command has evolved to C ′ and the store has been updated to µ ′ .

For a multi-threaded program M , the store µ plays the role of a global memory shared by all threads. The store µ is the only way for threads to communicate. The definition of the global relation g → is given in Figure 1, where M -x is the restriction of M to dom(M ) -{x } and M [x := C 1 ] is the map M where the command assigned to x is updated to C 1 . At each step, a thread x is chosen non-deterministically. Then, one step of x is performed and the control returns to the upper level. Note that the rule (Stop) halts the computation of a thread. In what follow, let ∅ be a notation for the (empty) multi-threaded program (i.e. all threads have terminated). We will discuss of deterministic scheduling policy in the last section.

A multi-threaded program M is strongly terminating, noted M ⇓, if for any store, all reduction sequences starting from M are finite. Let

Time M (d 1 , . . . , d n ) = max{k | µ 0 [X 1 ← d 1 , . . . , X n ← d n ] M g → k µ ∅}
where µ 0 is the empty store that maps each variable to the empty word ǫ ∈ W. A strongly terminating multi-threaded program M is running in polynomial time if there is a polynomial Q such that for all d 1 , . . . ,

d n ∈ W, Time M (d 1 , . . . , d n ) ≤ Q(max i=1,n |d i |).
Observe that, in the above definition, the time consumption of an operator is considered as constant, which is fair if operators are supposed to be computable in polynomial time.

µ skip s → µ µ E e → d µ X :=E s → µ[X ← d ] µ C1 s → µ1 µ C1 ; C2 s → µ1 C2 µ C1 s → µ1 C ′ 1 µ C1 ; C2 s → µ1 C ′ 1 ; C2 µ E e → w, w ∈ {tt, ff} µ if E then Ctt else Cff s → µ Cw µ E e → ff µ while(E ){C } s → µ µ E e → tt µ while(E ){C } s → µ C ; while(E ){C } (W tt ) M (x ) = C µ C s → µ1 µ M g → µ1 M -x (Stop) M (x ) = C µ C s → µ1 C1 µ M g → µ1 M [x := C1] (Step)
Fig. 1. Small step semantics of expressions, commands and multi-threads

Type system

Atomic types are elements of the boolean lattice ({0, 1}, , 0, ∨, ∧) where 0 1.

We call them tiers accordingly to the data ramification principle of [START_REF] Leivant | A foundational delineation of poly-time[END_REF]. We use α, β, . . . for tiers. A variable typing environment Γ is a finite mapping from V to {0, 1}, which assigns a single tier to each variable. An operator typing environment ∆ is a mapping that associates to each operator op a set of operator types ∆(op), where the operator types corresponding to an operator of arity n are of the shape α 1 → . . . α n → α with α i , α ∈ {0, 1} using implicit right associativity of →. We write dom(Γ ) (resp. dom(∆)) to denote the set of variables typed by Γ (resp. the set of operators typed by ∆). Figure 2 gives the typing discipline for expressions, commands and multi-threaded programs. Given a multi-threaded program M , a variable typing environment Γ and an operator typing environment ∆, M is well-typed if for every x ∈ dom(M ), Γ, ∆ ⊢ M (x ) : α for some tier α.

Notice that the subject reduction property is not valid, because we don't explicitly have any subtyping rule. However, a weak subject reduction property holds:

If µ C s → µ ′ C ′ then Γ, ∆ ⊢ C ′ : β where β α.
3 Safe multi-threaded program

Neutral and positive operators

As in [START_REF] Marion | A type system for complexity flow analysis[END_REF], we define two classes of operators called neutral and positive. For this, let be the sub-word relation over W, which is defined by v w , iff there are u and u ′ such that w = u.v .u ′ , where . is the concatenation. An operator op is neutral if: An operator op is positive if there is a constant c op such that:

Γ (X ) = α Γ, ∆ ⊢ X : α Γ, ∆ ⊢ X : β Γ, ∆ ⊢ E : α Γ, ∆ ⊢ X :=E : β β α Γ, ∆ ⊢ E1 : α1 . . . Γ, ∆ ⊢ En : αn α1 → . . . → αn → α ∈ ∆(op) Γ, ∆ ⊢ op(E1, . . . , En) : α Γ, ∆ ⊢ E : 1 Γ, ∆ ⊢ C : α Γ, ∆ ⊢ while(E ){C } : 1 Γ, ∆ ⊢ C : α Γ, ∆ ⊢ C ′ : β Γ, ∆ ⊢ C ; C ′ : α ∨ β Γ, ∆ ⊢ skip : α Γ, ∆ ⊢ E : α Γ, ∆ ⊢ C : α Γ, ∆ ⊢ C ′ : α Γ, ∆ ⊢ if E then C else C ′ : α
| op (d 1 , . . . , d n )| ≤ max i |d i | + c op
A neutral operator is always a positive operator but the converse is not true. In the remainder, we assume that operators are all neutral or positive.

Safe environments and safe multi-threaded programs

An operator typing environment ∆ is safe if for each op ∈ dom(∆) of arity n and for each α 1 → . . . → α n → α ∈ ∆(op), we have α ∧ i=1,n α i , and if the operator op is positive but not neutral, then α = 0. Now, given Γ a variable typing environment and ∆ a operator typing environment, we say that M is a safe multi-threaded program if M is well-typed wrt Γ and ∆ and ∆ is safe.

Intuitively, a tier 0 argument is unsafe. This means that it cannot be used as a loop guard. So for "loop-safety" reasons, if an operator has a tier 0 argument then the result is necessarily of tier 0. In return, a positive operator can increase the size of its arguments. On the other hand, a neutral operator does not increase the size of its arguments. So, we can apply it safely everywhere. The combination of the type system, which guarantees some safety properties on the information flow, and of operator specificities provides time bounds.

Example 1. Given a word d , the operator eq d tests whether or not its agument begins with the prefix d and pred computes the predecessor.

eq d (u) = = tt if u = dw = ff otherwise pred (u) = = ǫ if u = ǫ = w if u = ℓ.w , ℓ ∈ Σ
Both operators are neutral. This means that their types satisfy ∆(pred ), ∆(eq u ) ⊆ {0 → 0, 1 → 1, 1 → 0} wrt to a safe environment ∆. The operator suc d adds a prefix d . It is positive, but not neutral. So, ∆(suc d ) ⊆ {1 → 0, 0 → 0}:

(Positive) suc d (b) = d .b d ∈ Σ
4 Sequential and concurrent non-interferences

In this section, we demonstrate that classical non-interference results are obtained through the use of the considered type system. For that purpose, we introduce some intermediate lemmata. The confinement Lemma expresses the fact that no tier 1 variables are modified by a command of tier 0.

Lemma 1 (Confinement). Let Γ be a variable typing environment and ∆ be a safe operator typing environment. If Γ, ∆ ⊢ C : 0, then every variable assigned to C is of type 0, and C does not contain while loops.

Proof. By induction on the structure of C .

⊓ ⊔

The following lemma, called simple security, says that only variables at level 1 will have their content read in order to evaluate an expression E of type 1.

Lemma 2 (Simple security). Let Γ be a variable typing environment and ∆ be a safe operator typing environment. If Γ, ∆ ⊢ E : 1, then for every X ∈ V(E ), we have Γ (X ) = 1. Moreover, all operators in E are neutral.

Proof. By induction on E , and using the fact that E is necessarily only composed of operators of type 1 → . . . → 1 → 1, because the environment is safe.

⊓ ⊔ Definition 1. Let Γ be a variable typing environment and ∆ be an operator typing environment.

-The equivalence relation ≈ Γ,∆ on stores is defined as follows: µ ≈ Γ,∆ σ iff for every X ∈ dom(Γ ) s.t. Γ (X ) = 1 we have µ(X ) = σ(X ) -The relation ≈ Γ,∆ is extended to commands as follows:

1 We now establish a sequential non-interference Theorem which states that if X is variable of tier 1 then the value stored in X is independent from variables of tier 0.

. If C = C ′ then C ≈ Γ,∆ C ′ 2. If Γ, ∆ ⊢ C : 0 and Γ, ∆ ⊢ C ′ : 0 then C ≈ Γ,∆ C ′ 3. If C ≈ Γ,∆ C ′ and D ≈ Γ,∆ D ′ then C ; D ≈ Γ,∆ C ′ ; D ′ -Finally, it is extended to configurations as follows: If C ≈ Γ,∆ C ′ and µ ≈ Γ,∆ σ then µ C ≈ Γ,∆ σ C ′ Remark 1. A consequence of Lemma 2 is that if µ ≈ Γ,∆ σ and if Γ, ∆ ⊢ E : 1,
Theorem 1 (Sequential non-interference). Assume that Γ is a variable typing environment and ∆ is a safe operator typing environment s.t. Γ, ∆ ⊢ C : α and Γ, ∆ ⊢ D : α. Assume also that µ C ≈ Γ,∆ σ D . Then, we have:

-if µ C s → µ ′ C ′ then there exists σ ′ and D ′ such that σ D s → * σ ′ D ′ and µ ′ C ′ ≈ Γ,∆ σ ′ D ′ , -if µ C s → µ ′ then there exists σ ′ such that σ D s → * σ ′ and µ ′ ≈ Γ,∆ σ ′
Proof. First suppose that α = 0. Confinement Lemma 1 implies that µ ′ ≈ Γ,∆ σ ′ since no tier 1 variable is changed. Second suppose that α = 1. We proceed by induction on C . Suppose that C is while(E ){C 1 } and the evaluation under µ is:

µ E e → tt µ while(E ){C 1 } s → µ C 1 ; while(E ){C 1 } (W tt ) By Remark 1, the evaluation of E under σ is necessarily tt. Since C is an atomic command, C ≈ Γ,∆ D implies C = D . As a result, σ while(E ){C 1 } s → σ C 1 ; while(E ){C 1 }. We have µ ′ ≈ Γ,∆ σ ′ because µ = µ ′ and σ = σ ′ . We conclude that both configurations are equivalent, that is µ ′ C ′ ≈ Γ,∆ σ ′ D ′ .
The other cases are treated similarly.

⊓ ⊔ Sequential non-interference can be adapted to multi-threaded programs. For that purpose, we extend the equivalence ≈ Γ,∆ to multi-threaded programs by:

-If ∀x ∈ dom(M ) = dom(M ′ ), M (x) ≈ Γ,∆ M ′ (x) then M ≈ Γ,∆ M ′ -If M ≈ Γ,∆ M ′ and µ ≈ Γ,∆ σ then µ M ≈ Γ,∆ σ M ′
Theorem 2 (Concurrent Non-interference). Assume that Γ is a variable typing environment, that ∆ is a safe operator typing environment such that M is well-typed. Assume also that µ M

1 ≈ Γ,∆ σ M 2 . Then, if µ M 1 g → µ ′ M ′ 1 then there are σ ′ and M ′ 2 s.t. σ M 2 g → * σ ′ M ′ 2 and µ ′ M 1 ≈ Γ,∆ σ ′ M 2 .
Proof. Consequence of Theorem 1. ⊓ ⊔

Sequential and concurrent temporal non-interferences

Now we establish a property named temporal non-interference. This property ensures that the length of while-loops does not depend on variables of tier 0, and depends only on tier 1 variables. Consequently, a change in the value of a variable of tier 0 does not affect loop lengths. For this, we define a loop length measure in Figure 3 based on the small step semantics of Figure 1.

σ 0 C s → * σ ′ t C
′ holds if t is the number of while-loops, which are unfolded to reach σ ′ C ′ from σ C , that is t is the number of applications of the rule (TW tt ) in a computation. It is convenient to define the relation

⇒ t by σ C ⇒ t σ ′ C ′ iff σ 0 C s → * σ ′ t C ′ .
→ * σ ′ C ′ then σ C ⇒ 0 σ ′ C ′ since
there is no while loop inside C , by Lemma 1. Moreover, if σ C ⇒ t σ ′ C ′ , then for every k ≤ t there are σ ′′ and

C ′′ such that σ C ⇒ k σ ′′ C ′′ ⇒ t-k σ ′ C ′ .
Theorem 3 (Temporal non-interference). Assume that Γ is a variable typing environment and ∆ is a safe operator typing environment s.

t. Γ, ∆ ⊢ C : α and Γ, ∆ ⊢ D : α. Assume also that µ C ≈ Γ,∆ σ D . Then, if µ C ⇒ t µ ′ C ′ then there are σ ′ and D ′ s.t. σ D ⇒ t σ ′ D ′ and µ ′ C ′ ≈ Γ,∆ σ ′ D ′ .
Proof. The proof goes by induction on t. Suppose that t = 0. This means that no rule (TW tt ) has been fired. The conclusion is a consequence of sequential non-interference Theorem 1.

Next, suppose that µ C ⇒ t+1 µ ′ C ′ . This means that a rule (TW tt ) has been applied. So suppose that C = while(E ){C 1 } and that µ E

′ = σ, which implies that µ ′ ≈ Γ,∆ σ ′ . We conclude that µ ′ C ′ ≈ Γ,∆ σ ′ D ′ .
The other cases are similar.

⊓ ⊔

We extend the relation ⇒ t as follows:

µ M ⇒ t µ ′ M ′ if and only if µ 0 M g → * µ ′ t M ′ .
As a corollary, we obtain a temporal non-interference result for multi-threaded programs.

Theorem 4 (Concurrent temporal non-interference). Assume Γ is a variable typing environment and ∆ is a safe operator typing environment s.t. M and N are well typed. Assume that µ M ≈ Γ,∆ σ N . Then, if µ M ⇒ t µ ′ M ′ then there are σ ′ and

N ′ s.t. σ N ⇒ t σ ′ N ′ and µ ′ M ′ ≈ Γ,∆ σ ′ N ′ .
Proof. Consequence of Theorem 3.

⊓ ⊔

Multi threaded program running time

An important point is that the number of tier 1 configurations in a computation is polynomially bounded in the size of tier 1 initial values.

Lemma 3. Let M be a safe multi-threaded program wrt environments Γ and ∆.

If µ M ⇒ t µ ′ M ′ then ∀X ∈ V(M ) such that Γ (X ) = 1 either µ ′ (X ) ∈ {tt, ff} or ∃Y ∈ V(M ) such that Γ (Y ) = 1 and µ ′ (X ) µ(Y ).
Proof. Take one global computational step µ M g → µ ′ M ′ . Let X be a variable assigned to in M (x ), for some thread identifier x , such that Γ (X ) = 1. X can only be assigned to an expression E of tier 1. By simple security lemma 2, E only contains neutral operators. It means that either µ ′ (X ) is a truth value (corresponding to the computation of a predicate) or a subterm of a value of a tier 1 variable.

⊓ ⊔

In the case where a multi-threaded program strongly terminates (i.e. M ⇓), we now establish that for all thread interactions, the maximal length of whileloops is polynomially bounded in the size of tier 1 values of the initial store. This is a consequence of the temporal non-interference property. For this, define

-1 by µ 1 = max Γ (X )=1 |µ(X )|.
Theorem 5. Let M be a safe multi-threaded program such that M ⇓. There is a polynomial T such that for all stores µ, if µ M ⇒ t µ ′ M ′ then t ≤ T ( µ 1 ).

Proof. By Theorem 4, the length of while-loops depends only on variables of tier 1. It implies that if we enter twice into a configuration with the same thread, say x , and the same values of tier 1, we know that M is non-terminating. Indeed, it is possible to repeat the same transition again up to infinity by always firing the same sequence of global transitions. This contradicts the fact that M ⇓. Consequently, we never enter twice in the same thread configuration. Since the number of sub-words of a word of size n is bounded by n 2 , Lemma 3 impies the number of distinct stores σ reachable from µ is bounded polynomially by µ 1 . It follows the number of configurations is polynomially bounded. Consequently there exists a polynomial T such that the length of each terminating multithreaded computation starting from µ is bounded by T ( µ 1 ). Finally, we have that t ≤ T ( µ 1 ).

⊓ ⊔

We can now state our first main result: Theorem 6. Assume that M is a safe multi-threaded program. Moreover suppose that M strongly terminates. There is a polynomial Q such that:

∀d 1 , . . . , d n ∈ W, Time M (d 1 , . . . , d n ) ≤ Q(max i=1,n (|d i |)) Proof. Suppose that µ 0 [X 1 ← d 1 , . . . , X n ← d n ] M ⇒ t µ ′ ∅.
The overall computational time is bounded by Time M (d 1 , . . . , d n ) ≤ r.t+r, for some constant r which depends on the size of M . (Note that commands of tier 0 are computable in constant size.) We conclude by Theorem 5 and by setting Q(X) = r.T (X) + r. ⊓ ⊔

A characterization of polynomial time functions

We now come to a characterization of the set of functions computable in polynomial time. A sequential program M consists in a single thread program (i.e. dom(M ) = {x }) and an output variable, say Y . The partial function M computed by M is then defined by:

M (d 1 , . . . , d n ) = w iff µ 0 [X 1 ← d 1 , . . . , X n ← d n ] M g → * µ ∅ and µ(Y ) = w Theorem 7.
The set of functions computed by strongly terminating and safe sequential programs whose operators compute polynomial time functions is exactly FPtime, which is the set of polynomial time computable functions.

Proof. The polynomial runtime upper bound is a consequence of Theorem 5. The converse is a straightforward simulation of polynomial time Turing machines. The proof is postponed in Appendix.

Deterministic scheduling

Actually, we can extend our results to a class of deterministic schedulers. Till now, we have considered a non-deterministic scheduling policy but in return we require that multi-threaded programs strongly terminate. Define µ ↓ 1 as the restriction of the store µ to tier 1 variables. Say that a deterministic scheduler S is quiet if the scheduling policy depends only on the current multi-threaded program M and on µ ↓ 1. For example, a deterministic scheduler whose policy just depends on running threads, is quiet.

Notice that σ ≈ Γ,∆ σ ′ iff σ ↓ 1 = σ ′ ↓ 1.
Next, we replace the non-deterministic global transition of Figure 1 by:

S(M, µ ↓ 1) = x µ M (x ) s → µ ′ µ M g → µ ′ M -x S(M, µ ↓ 1) = x µ M (x ) s → µ ′ C ′ µ M g → µ ′ M [x := C ′ ]
Theorem 8. Let M be a safe multi-threaded program s.t. M is terminating wrt a deterministic and quiet scheduler S. There is a polynomial Q such that:

∀d 1 , . . . , d n ∈ W, Time M (d 1 , . . . , d n ) ≤ Q(max i=1,n (|d i |))
Proof. The proof follows the outline of proofs of theorems 5 and 6. Let µ be the initial store, i.e. µ(X i ) = d i for i = 1, n and µ(X i ) = ǫ for i > n. Since the computation of µ M terminates wrt S, the temporal non-interference theorem 3 implies that a loop can not reach the configurations σ N and σ ′ N where their restrictions to tier 1 values are identical. That is σ

↓ 1 = σ ′ ↓ 1. Now, define Config = {(σ ↓ 1, N ) | µ M g → * σ N }.
The total length of loops is bounded by the cardinality of Config. Following lemma 3, the cardinality of Config is bounded by a polynomial in µ 1 . As a result, the runtime of µ M is bounded bounded by Q(max i=1,n (|d i |)) for some polynomial Q.

A Appendix

A.1 Proofs Characterization of polynomial time functions Theorem 7. The set of functions computed by strongly terminating and safe sequential programs whose operators compute polynomial time functions is exactly FPtime, which is the set of polynomial time computable functions.

Proof. By Theorem 6, the execution time of a safe and strongly terminating sequential program is bounded by a polynomial in the size of the initial values. In the other direction, we show that every polynomial time function over the set of words W can be computed by a safe and terminating program. Consider a Turing Machine T M , with one tape and one head, which computes within n k steps for some constant k and where n is the input size. The tape of T M is represented by two variables Left and Right which contain respectively the reversed left side of the tape and the right side of the tape. States are encoded by constant words and the current state is stored in the variable State. We assign to each of these three variables that hold a configuration of TM the tier 0. A one step transition is simulated by a finite cascade of if-commands of the form:

if eq a (Right 0 ) 0 then if eq s (State 0 ) 0 then State 0 :=s ′0 ; : 0 Left 0 :=suc b (Left 0 ); : 0 Right 0 :=pred (Right 0 ) : 0 else . . . : 0 . . . The above command expresses that if the current read letter is a and the state is s, then the next state is s ′ , the head moves to the right and the read letter is replaced by b. Since each variable inside the above command is of type 0, the type of the if-command is also 0. Moreover, since suc b is a positive operator, its type is forced to be 0 → 0. eq a , eq s and pred being neutral operators, they can also be typed by 0 → 0. Finally, it just remains to show that every polynomial can be simulated by a safe program of tier 1. We have already provided the programs for addition and multiplication in Example 2 and we let the reader check that it can be generalized to any polynomial. ⊓ ⊔

A.2 Examples

In what follows, let E α , respectively C : α, be a notation meaning that the expression E , respectively command C , is of type α under the considered typing environments.

Example 2. Consider the sequential programs add Y and mul Z that compute respectively addition and multiplication on unary words using the positive successor operator +1, in infix notation, and two neutral operators, -1 and a unary predicate > 0, both in infix notation. Both programs are safe by checking that their main commands are well-typed wrt the safe operator typing environment ∆ defined by ∆(+1) = {0 → 0} and ∆(-1) = ∆(> 0) = {1 → 1}.

addY : mulZ : while(X 1 > 0) 1 { Z 0 :=0 0 ; : 0 X 1 :=X 1 -1; : 1 while(X 1 > 0) 1 { Y 0 :=Y 0 + 1 : 0 X 1 :=X 1 -1; : 1 } : 1 U 1 :=Y 1 ; : 1 while(Y 1 > 0) 1 { Y 1 :=Y 1 -1; : 1 Z 0 :=Z 0 + 1 : 0 }; : 1 Y 1 :=U 1 : 1 } : 1
Example 3. Consider the following multi-thread M composed of two threads x and y computing on unary numbers:

x : y : while (X 1 > 0) 1 { while (Y 1 > 0) 1 { Z 0 :=Z 0 + 1; : 0 Z 0 = 0; : 0 X 1 :=X 1 -1; : 1 Y 1 :=Y 1 -1; : 1 } : 1 } : 1
This program is strongly terminating. Moreover, given a store µ such that µ(X ) = n and µ(Z

) = 0, if µ M g → k µ ′ ∅ then µ ′ (Z ) ∈ [0, n].
M is safe using an operator typing environment ∆ such that ∆(-1) = ∆(> 0) = {1 → 1} and ∆(+1) = {0 → 0} and M ⇓. Consequently, by Theorem 5, there is a polynomial T such that for each store µ, k ≤ T ( µ 1 ).

Example 4. Consider the following multi-thread M that shuffles two strings given as inputs:

x : y : while (¬eq ǫ (X 1 )) 1

{ while (¬eq ǫ (Y 1 )) 1 { Z 0 :=concat(head(X 1 ), Z 0 ); : 0 Z 0 :=concat(head(Y 1 ), Z 0 ); : 0 X 1 :=pred(X 1 ); : 1 Y 1 :=pred(Y 1 ); : 1 } : 1 } : 1
The negation operator ¬ and eq ǫ are unary predicates and consequently can be typed by 1 → 1. The operator head returns the first symbol of a string given as input and can be typed by 1 → 0 since it is neutral. The pred operator can typed by 1 → 1 since its computation is a subterm of the input. Finally, the concat operator that performs the concatenation of the symbol given as first argument with the second argument can be typed by 0

→ 0 → 0 since | concat (u, v)| = |v| + 1.
This program is safe and strongly terminating consequently it also terminates in polynomial time.

Example 5. Consider the following multi-thread M :

x :

y : while (X 1 > 0) 1 { while (Y 1 > 0) 1 { Y 1 :=X 1 ; : 1 Z 0 :=Z 0 + 1; : 0 X 1 :=X 1 -1; : 1 Y 1 :=Y 1 -1; : 1 } : 1 } : 1
Observe that, contrarily to previous examples, the guard of y depends on information flowing from X to Y . Given a store µ such that µ(X ) = n, µ(Y ) =

µ(Z ) = 0, if µ M g → k µ ′ ∅ then µ ′ (Z ) ∈ [0, n × (n + 1)/2]
. This multithread is safe with respect to a safe typing operator environment ∆ such that ∆(-1) = ∆(> 0) = {1 → 1} and ∆(+1) = {0 → 0}. Moreover it strongly terminates. Consequently, it also terminates in polynomial time.

Example 6. The following program computes the exponential: expY (X 1 , Y 0 ) : while(X 1 > 0){ U ? :=Y 0 ; : ? while(U ? > 0){ Y 0 :=Y 0 + 1; : 0 U ? :=U ? -1 : ? }; : 1 X 1 :=X 1 -1 : 1 }; : 1 It is not typable in our formalism. Indeed, suppose that it is typable. The command Y :=Y + 1 enforces Y to be of tier 0 since +1 is positive. Consequently, the command U :=Y enforces U to be of tier 0 because of typing discipline for assignments. However, the innermost while loop enforces U > 0 to be of tier 1, so that U has to be of tier 1 (because 0 → 1 is not permitted for a safe operator typing environment) and we obtain a contradiction.

Example 7. As another counter-example, consider now the addition badd on binary words: baddY : while(X ? > 0) ? { X ? :=X ? -1; : ? Y 0 :=Y 0 + 1 : 0 } : 1 Contrarily to Example 2, the above program is not typable because the operator -1 has now type ∆(-1) = {0 → 0}. Indeed it cannot be neutral since binary predecessor is not a subterm operator. Consequently, -1 is positive and the assignment X :=X -1 enforces X to be of type 0 whereas the loop guard enforces X to be of tier 1. Note that this counter-example is not that surprising in the sense that a binary word of size n may lead to a loop of length 2 n using the -1 operator. Of course this does not imply that the considered typing discipline rejects computations on binary words, it only means that this type system rejects exponential time programs. Consequently,"natural" binary addition algorithms are captured as illustrated by the following program that computes the binary addition on reversed binary words of equal size: binary addZ : while(¬eq ǫ (X 1 )) 1 { R 0 :=result(bit(X 1 ), bit(Y 1 ), bit(C 1 )); : 0 C 1 :=carry(bit(X 1 ), bit(Y 1 ), bit(C 1 )); : 1 Z 0 :=concat(R 0 , Z 0 ); : 0 X 1 :=pred (X 1 ); : 1 Y 1 :=pred (Y 1 ); : 1 } : 1

As usual, pred is typed by 1 → 1. The negation operator ¬ and eq ǫ are predicates and, consequently, can be typed by 1 → 1, since they are neutral. The operator bit returns tt or ff depending on whether the word given as input has first digit 1 or 0, respectively. Consequently, it can be typed by 1 → 1. The operators carry and result, that compute the carry and the result of bit addition, can be typed by 1 → 1 → 1 → 1 since they are neutral. Finally, the operator concat(x, y) defined by if bit (x) = i, i ∈ {0, 1} then concat (x, y) = i.y is typed by 0 → 0 → 0. Indeed it is a positive operator since | concat (x, y)| = |y| + 1.

  the reflexive and transitive closure of the relation h →, h ∈ {s,g}. The running time of a strongly terminating program M is the function Time M from W n to N defined by:

→

  d1 . . . µ En e → dn µ op(E1, . . . , En) e → op (d1, . . . , dn)

Fig. 2 .

 2 Fig. 2. Type system for expressions, commands

  then computations of E are identical under the stores µ and σ , that is µ E

Fig. 3 .

 3 Fig. 3. Loop length measure for commands and multi-thread programs

e

  → tt. First, µ ≈ Γ,∆ σ and Lemma 2 imply that σ E e → tt. Second, since C ≈ Γ,∆ D , we have C = D , by definition of ≈ Γ,∆ . Since C ′ = C 1 ; C , we have D ′ = C 1 ; C . Thus, C ′ ≈ Γ,∆ D ′ and σ D ⇒ t+1 σ ′ D ′ hold. Moreover, we have µ ′ = µ and σ

Our result could be generalized to other domains such as binary trees or lists. However we have restricted this study to words in order to lighten our presentation.


SIMPLE TECHNIQUE FOR THE DETERMINATION OF THE COMPLEX TRANSMITTANCE OF SPATIAL LIGHT MODULATOR

Philippe Delaye, Gérald Roosen Laboratoire Charles Fabry de l'Institut d'Optique, Unité Associée au Centre National de la Recherche Scientifique, Bat. 503, Centre Scientifique d'Orsay, B.P. 147, 91403 Orsay Cedex, France. Tel : 33-1-69-35-87-50, Fax : 33-1-69-35-87-00, Email : Philippe.delaye@iota.u-psud.fr

Abstract :

We describe a simple technique for the determination of the complex transmittance of a spatial light modulator. The technique uses the variation of the diffraction efficiency of Ronchi gratings imprinted on the SLM, as a function of the grating contrast. The measurement is made on the central peak of the diffraction structure with a monopixel detector only. The technique can also be used in quasi real time in order to adjust the SLM in the expected working regime (phase only modulation for example).

Liquid crystal based Spatial Light Modulators (SLM) are components that are used in a great number of image processing systems, such as correlators, optical neural networks or holographic memories. In all these systems the images can be inserted as both phase and/or amplitude modulation. If it is easy to measure the amplitude response of the SLM, its phase response is more difficult to evaluate. Different methods were proposed [START_REF] Lu | Theory and design of the liquid crystal TV as an optical spatial phase modulator[END_REF][START_REF] Gregory | Using the Hybrid modulating properties of liquid crystal television[END_REF][START_REF] Kirsch | Modulation characteristics of the Epson liquid crystal television[END_REF][START_REF] Laude | Amplitude and phase coding measurements of a liquid crystal television[END_REF][START_REF] Soutar | Measurement of the complex transmittance of the Epson liquid crystal television[END_REF][START_REF] Neto | Programmable optical phase-mostly holograms with coupled-mode modulation liquid-crystal television[END_REF][START_REF] Martin-Badosa | Complex modulation characterization of liquid crystal devices by interferometric data correlation[END_REF], they were mainly interferometric measurements using for example Mach-Zehnder interferometers. More recently methods using Ronchi gratings (or more generally diffracting structures) were proposed [START_REF] Zhang | Simple method for measuring phase modulation in liquid crystal televisions[END_REF][START_REF] Mcclain | Spatial light modulator phase depth determination from optical diffraction information[END_REF], these methods avoid the use of interferometric methods, but they require a precise analysis of the amplitude of the different diffraction peaks.

We here propose a simple and robust technique derived from the Ronchi grating measurement that only requires the use of a monopixel detector, and that can give the complex transmittance of a SLM. It is based on the study of the time evolution of the zeroth order of the Fourier transform of a Ronchi grating imprinted on the SLM, as the contrast of the grating is varied. This time evolution is directly linked to the contrast of the grating and thus to the complex transmittance of the SLM, allowing the determination of this transmittance as a function of the grey level of the image.

The SLM we used is issued from an Epson video projector. It is a TFT active matrix twisted nematic liquid crystal SLM. The experimental set-up is presented in Fig. 1. The SLM is placed between a polarizer and an analyzer correctly oriented to have pure phase modulation, its electronic is used with brightness and color potentiometers both at zero [START_REF] Martin-Badosa | Complex modulation characterization of liquid crystal devices by interferometric data correlation[END_REF]. The amplitude of the phase modulation that is controlled by the contrast potentiometer (at zero level the phase modulation amplitude is at its minimum and at level 10 it is at its maximum, both these values being used in this experiment). The image is sent on the SLM through a personal computer. After the SLM a Si detector is placed at the Fourier plane of a lens, with a hole to select only one diffraction peak. The whole system is illuminated by a spatially filtered Argon laser emitting at 514nm. A Ronchi grating is made of a succession of lines having different transmissions and a squared profile (Fig. 2). It is very easy to imprint such an image on a SLM, we simply send on the SLM an image constituted of a succession of lines with a grey level n W for a "white" line and n B for a "black" line. Light will then diffract on the grating, and an observation of the diffraction structure in the Fourier plane gives a structure of diffraction peaks that depends on the contrast of the grating.

The amplitude transmission t(ξ,η) of the SLM with the grating is :

t !, " ( ) = a n # ! $ np a % & ' ( n =$ ) +) * (1)
∏(ξ) being a "gate" function of width a and height 1. The width a is taken smaller or equal to the grating step p, in order to take into account the interpixel spacing (we will suppose it completely opaque) (Fig. 2). a n is the amplitude of the window number n, its value is a n = a W = T n W ( ) e i! n W ( ) for n complex transmission and ! n ( ) its phase. In order to simplify the calculation we will suppose that both dimensions of the SLM are infinite, i.e. we have an infinite number of lines of infinite length. The amplitude of the diffracted beam in the Fourier plane is given by the Fourier transform of t(ξ,η), which value is :

A u, v ( ) = ! u " n 2p # $ % & ' sin ( a n 2p # $ % & ' ( n 2p T n W ( )e i) n W ( ) + "1 ( ) n T n B ( )e i) n B ( ) ( ) n= "* + * + (2)
As we have a≠p, even without a written grating we observe peaks that correspond to the diffraction on the pixelated structure of the SLM. When, as in our case, we write every two lines, the diffraction peaks due to the grating appear at half distance of the diffraction peaks due to the pixel structure. If we want to take into account the finite dimensions of the SLM, we just have to replace the Dirac function in equation ( 2) by a function characteristics of the aperture of the SLM. If the aperture is sufficiently large, this broadening is nevertheless negligible compared to the distance between the different peaks, and the infinite approximation is justified. In the same kind of argument, the pixelated structure of each lines would be responsible of diffraction peaks in the other direction (along v) adding new terms in equation ( 2) with similar structure. Taking into account this exact structure would complicate the calculation, but without changing the expression of the central peak.

The respective height of the peaks is given by the last term of equation ( 2) that depends on the contrast of the grating (then on "black" and "white" levels n B and n W ). Thus a measurement of the height of adjacent peaks allows the determination of the transmittance of each line and thus of grey levels. The problem is that the measurement depends on other parameters of the system, as indicated by the first terms of equation ( 2), what may complicate the determination. Nevertheless this technique was already successfully used [START_REF] Zhang | Simple method for measuring phase modulation in liquid crystal televisions[END_REF].

We prefer another measurement much simpler and robust. We place a detector on the central peak of the diffraction structure. The measured intensity is deduce from (2) and is equal to : I 0, 0

( ) = I 0 T 2 n W ( ) + T 2 n B ( ) + 2T n W ( )T n B ( )cos ! n W ( ) " ! n B ( ) ( ) ( ) (3)
We fix the "black" level, and vary the "white" level. The intensity of the central peak changes due to diffraction following a law that depends on the phase change ! n W ( ) " ! n B ( ). Thus a simple measurement of I(0,0) as a function of the grey level n, gives the phase ϕ(n). This simple measurement is only valid if T(n) does not vary, what is rarely the case. In order to remedy to this we add a measurement with a uniform "white" image. Then the detected intensity is :

I 0, 0 ( ) = 4I 0 T 2 n W ( ) (4)
This intensity can be easily compared to the "black" value, and normalized to it. With both measurements we can separately determine ϕ(n) et T(n) (normalized to "black" level n B ).

The interest of this measurement is that it does not require any calibration, only relative measurements are necessary. For example I 0 can be easily eliminated, the fact of not knowing its exact value does not prevent the measurement. Any effect due for example to the real number of lines, can be neglected, as soon as the central peak is narrow enough to have no overlap with the first peak, and that all its energy is collected by the detector.

An example of a measurement curve is given in Fig. 3. To obtain this signal we send a series of images successively uniform and with a Ronchi grating. The "black" level corresponds to n B =0 and the "white" level is varied between n W = 0 and 255 with a step of 5 between the images. So the first image is uniform with a level 0, the second image is a grating with levels 0 and 0, the third image is uniform with level 5, the fourth image is a grating with levels 0 and 5, and so on until the last image which is a grating with levels 0 and 255. Each image is presented for about 1.5s, in order to be sure to reach the steady state. The presented curve is numerically filtered (Fourier transform -low pass filter -inverse Fourier transform) from the 25Hz noise due to the flicker noise of the SLM [START_REF] Laude | Amplitude and phase coding measurements of a liquid crystal television[END_REF]. The upper envelope (neglecting the transitory spike at image change) gives the uniform image signal, whereas the lower envelope gives the grating response (still not considering the spikes). We see that very high diffraction efficiencies can be obtained as we have a quasi perfect extinction of the central peak (Fig. 3, around t=50s, that corresponds to n W ≈ 70). This indicates that phase shifts greater than π can easily be obtained.

At high contrast of the grating (∆ϕ>π) a spike can be observed each time the image is changed. This spike is attributed to the finite response time of the SLM. Indeed when the grating image is applied to the SLM, the SLM takes a certain time to reach its steady state value. As the steady state value corresponds to a phase shift greater than π, during the build-up there is an instant at which the phase shift reaches the value of π, corresponding to a complete depletion of the central peak. After passing this maximum, diffraction efficiency decreases to reach its steady state value.

So for each value of the grey level, we can measure the intensity I uni of the uniform image normalized to the signal obtained with an uniform "black" image :

I uni = 4I 0 T 2 n W ( ) 4I 0 T 2 n B ( ) = T n W ( ) T n B ( ) ! " # $ % & 2 (5)
which gives the normalized amplitude transmission T norm n

( ) = T n ( ) T n = 0 ( ).
Then the intensity I grat of the central peak in presence of the grating is determined and normalized to the signal obtained with an uniform "black" image :

I grat = 1 4 T 2 n W ( ) T 2 n B ( ) + 1+ 2 T n W ( ) T n B ( ) cos ! n W ( ) " ! n B ( ) ( ) # $ % & ' ( (6)
From it we deduce the normalized phase shift !" n ( ) = " n ( ) # " n = 0 ( ) , knowing the normalized amplitude transmission. At this point several problems occur in this measurement. The first problem is a classical one. Indeed we can reach values of the phase shift greater than π. We thus cannot determine directly ∆ϕ from I grat , we will have to unwrap the phase to determine the full variation of ∆ϕ. The second problem is the fact that close to a maximum or a minimum of diffraction efficiency (∆ϕ≈kπ), the extraction of ∆ϕ from I grat becomes very uncertain (values of cos ! n W ( ) " ! n B ( ) ( ) greater than 1). To solve this problem we make a second measurement for which we change the "black" level using the 255 value instead of 0 and performed exactly the same measurements. We thus determine normalized amplitude transmission and normalized phase shift values as previously, but now normalized to the 255 value.

Then we renormalized to the zero value using T 255 ( ) T 0 ( ) and ! 255 ( ) " ! 0 ( ), that are given in both measurements. The advantage of this technique is that maximum and minimum values occurs for different values of n (if it ever occurs we can use another "black" level that allows the measurement) and zones of uncertainty do not overlap. Moreover, in order to unwrap the phase of one measurement we can use the other curves for which unwrapping positions are distinct.

The treatment described here gives the results shown in Fig. 4, where the values of T norm n ( ) = T n ( ) T 0 ( ) and !" n ( ) = " n ( ) # " 0 ( ) are extracted from the data of 3. Here two measurements were performed with a "black" image corresponding to n=0 (circles) and to n=255 (cross). We see that the parts where there is a problem do not overlap and that these two simple measurements allow a good determination of the complex transmittance of the SLM. For the normalized amplitude transmission, the accordance is rather good both measurements giving the same result. On these curves we can see that almost linear phase shift greater than 2π can be obtained, with moderate variation of transmission.

We can obtain even better results with another setting of the SLM (Fig. 5). In this condition we have quasi linear phase shift between 0 and π, with almost no amplitude modulation, leading to a SLM working as a nearly pure phase modulator.

As a conclusion we demonstrate a simple technique for the measurement of the complex transmittance of a SLM as a function of the grey level. This technique is certainly not perfect, mainly concerning the accuracy of the measurement, due to the presence of some missing points. But it has the great advantage of being very simple and of requiring neither interferometric set-up, very often delicate to align and to stabilize, nor CCD camera, that have generally poor linearity and dynamics. The extraction of the data can require some treatment, especially to unwrap the phase, in the case of phase shifts greater than π, but in general it is rather simple and can be easily automated.

More over this simple method can easily be used to adjust the SLM. The raw data of Fig. 3 can easily be used for this purpose. Adjustment of the polarizer, analyzer and electronics of the SLM can be made in quasi-real time (some tens of seconds or even less) to obtain the expected working regime of a SLM. For example just looking at the upper envelope of the raw signal which is proportional to the amplitude transmission of the SLM (Fig. 3) we see the residual amplitude modulation. We can minimize it in order to obtain a phase only modulator, this optimization being performed on the whole curve and not on a single value of the grey level.

In these measurements we also confirm that it is possible to obtain quasi phase only modulation with our SLM, with linear response between 0 and π, and quasi linear response between 0 and 2.5π.

The accuracy of the measurement is rather good and certainly sufficient for most of application of this SLM.

Figure 1 :

 1 Figure 1 : Experimental set-up. SF : Spatial filter, P,A : Polarizers, FP : Fourier Plane.

Figure 2 :Figure 3 :

 23 Figure 2 : Ronchi grating sent to the SLM

Figure 4 :

 4 Figure 4 : Normalized phase shift (black symbols) and normalized amplitude transmission (grey symbols) of the SLM. The contrast potentiometer of the SLM is at level 10. The "black" level is at n B =0 for circles and n B =255 for crosses .

Figure 5 :

 5 Figure 5 : Normalized phase shift (black symbols) and normalized amplitude transmission (grey symbols) of the SLM. The contrast potentiometer of the SLM is at level 0. The "black" level is at n B =0 for circles and n B =255 for crosses .

Figure 1

 1 Figure 1

Figure 2

 2 Figure 2

Figure 3

 3 Figure 3

Figure 4

 4 Figure 4

Figure 5

 5 Figure 5

Acknowledgments :

Support for this research by Direction des Recherches Études et Techniques is greatly acknowledged.


Bruno Scherrer

On the Use of Non-Stationary Policies for Infinite-Horizon Discounted Markov Decision Processes

We consider infinite-horizon γ-discounted Markov Decision Processes, for which it is known that there exists a stationary optimal policy. We consider the algorithm Value Iteration and the sequence of policies π1, . . . , π k it implicitely generates until some iteration k. We provide performance bounds for non-stationary policies involving the last m generated policies that reduce the state-of-the-art bound for the last stationary policy π k by a factor 1-γ 1-γ m . In particular, the use of non-stationary policies allows to reduce the usual asymptotic performance bounds of Value Iteration with errors bounded by ǫ at each iteration from γ (1-γ) 2 ǫ to γ 1-γ ǫ, which is significant in the usual situation when γ is close to 1. Given Bellman operators that can only be computed with some error ǫ, a surprising consequence of this result is that the problem of "computing an approximately optimal non-stationary policy" is much simpler than that of "computing an approximately optimal stationary policy", and even slightly simpler than that of "approximately computing the value of some fixed policy", since this last problem only has a guarantee of 1 1-γ ǫ.

Given a Markov Decision Process, suppose on runs an approximate version of Value Iteration, that is one builds a sequence of value-policy pairs as follows:

Pick any π k+1 in Gv k v k+1 = T π k+1 v k + ǫ k+1
where v 0 is arbitrary, Gv k is the set of policies that are greedy 1 with respect to v k , and T π k is the linear Bellman operator associated to policy π k . Though it does not appear exactly in this form in the literature, the following performance bound is somewhat standard. Theorem 1. Let ǫ = max 1≤j<k ǫ j sp be a uniform upper bound on the span seminorm 2 of the errors before iteration k. The loss of policy π k is bounded as follows:

v * -v π k ∞ ≤ 1 1 -γ γ -γ k 1 -γ ǫ + γ k v * -v 0 sp . (1)
In Theorem 2, we will prove a generalization of this result, so we do not provide a proof here. Since for any f , f sp ≤ 2 f ∞ , Theorem 1 constitutes a slight improvement and a (finite-iteration) generalization of the following well-known performance bound (see [1]):

lim sup k→∞ v * -v π k ∞ ≤ 2γ (1 -γ) 2 max k ǫ k ∞ .
1 There may be several greedy policies with respect to some value v, and what we write here holds whichever one is picked. [START_REF] Kakade | On the Sample Complexity of Reinforcement Learning[END_REF] For any function f defined on the state space, the span seminorm of f is f sp = maxs f (s)mins f (s). The motivation for using the span seminorm instead of a more usual L∞-norm is twofold: 1) it slightly improves on the state-of-the-art bounds and 2) it simplifies the construction of an example in the proof of the forthcoming Proposition 1. Asymptotically, the above bounds involve a γ (1-γ) 2 constant that may be really big when γ is close to 1. Compared to a value-iteration algorithm for approximately computing the value of some fixed policy, and for which one can prove a dependency of the form [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF] 1-γ ǫ, there is an extra term γ 1-γ that suggests that the problem of "computing an approximately optimal policy" is significantly harder than that of "approximately computing the value of some fixed policy". To our knowledge, there does not exist any example in the literature that supports the tightness of the above mentionned bounds. The following proposition shows that the bound of Theorem 1 is in fact tight.

Proposition 1. For all ǫ ≥ 0, ∆ ≥ 0, and k > 0, there exists a k +1-state MDP, an initial value v 0 such that v *v 0 sp = ∆, a sequence of noise terms (ǫ j ) with ǫ j sp ≤ ǫ, such that running Value Iteration during iterations with errors (ǫ j ) outputs a value function v k-1 of which a greedy policy π k satisfies Equation (1) with equality.

Proof. Consider the deterministic MDP of Figure 1. The only decision is in state s k , where one can stay with reward r = -γ-γ k 1-γ ǫγ k ∆ or move to s k-1 with 0 reward. All other transitions give 0 reward. Thus, there are only two policies, the optimal policy π * with value equal to 0, and a policy π for which the value in s k is r 1-γ . Take

v 0 (s l ) = -∆ if l = 0 0 else and for all j < k, ǫ j (s l ) = -ǫ if j = l 0 else.
By induction, it can be seen that for all j ∈ {1, 2, . . . , k -1},

v j (s l ) = -ǫ -γǫ -• • • -γ j-1 ǫ -γ j ∆ = -1-γ j 1-γ ǫ -γ j ∆ if j = l 0 if j < l ≤ k
Since γv k-1 (s k-1 ) = r and v k-1 (s k ) = 0, both policies are greedy with respect to v k-1 , and the bound of Equation (1) holds with equality for π.

Instead of running the last stationary policy π k , one may consider running a periodic non-stationary policy, which is made of the last m policies. The following theorem shows that it is indeed a good idea. Theorem 2. Let π k,m be the following policy

π k,m = π k π k-1 • • • π k-m+1 π k π k-1 • • • .
Then its performance loss is bounded as follows:

v * -v π k,m ∞ ≤ 1 1 -γ m γ -γ k 1 -γ ǫ + γ k v * -v 0 sp .
When m = 1, one exactly recovers the result of Theorem 1. For general m, this new bound is a factor 1-γ 1-γ m better than the usual bound. Taking m = k, that is considering all the policies generated from the very start, one obtains the following bound:

v * -v π k,k ∞ ≤ γ 1 -γ - γ k 1 -γ k ǫ + γ k 1 -γ k v * -v 0 sp .
that tends to γ 1-γ ǫ when k tends to ∞. In other words, we can see here that the problem of "computing a (non stationary) approximately-optimal policy" is not harder than that of "computing approximately the value of some fixed policy". Since the respective asymptotic errors are γ 1-γ ǫ and 1 1-γ ǫ, it seems even simpler ! Proof of Theorem 2. The value of π k,m satisfies:

v π k,m = T π k T π k-1 • • • T π k-m+1 v π k,m . (2)
By induction, it can be shown that the sequence of values generated by the algorithm satisfies:

T π k v k-1 = T π k T π k-1 • • • T π k-m+1 v k-m + m-1 i=1 Γ k,i ǫ k-i (3)
where

Γ k,i = P π k P π k-1 • • • P π k-i+1
in which, for all π, P π denotes the stochastic matrix associated to policy π. By substracting Equations ( 3) and ( 2), one obtains:

T π k v k-1 -v π k,m = Γ k,m (v k-m -v π k,m ) + m-1 i=1 Γ k,i ǫ k-i
and by taking the norm

T π k v k-1 -v π k,m ∞ = γ m v k-m -v π k,m ∞ + γ -γ m 1 -γ ǫ ∞ (4)
where ǫ ∞ = max 1≤j≤k ǫ j ∞ . Essentially, Equation (4) shows that for sufficiently big m, T π k v k-1 is an γ 1-γ ǫ approximation of the value of the non-stationary policy π k,m (whereas in general, it may be a much poorer approximation of the value of the stationary policy π k .

By induction, it can also be proved that

v * -v k ∞ ≤ γ k v * -v 0 ∞ + 1 -γ k 1 -γ ǫ ∞ . (5)
Using the fact that

T π * v * -T π k v k-1 ∞ ≤ γ v * -v k-1 ∞ since π * (resp. π k
) is greedy with respect to v * (resp. v k-1 ), as well as Equations ( 4) and (5), we can conclude by observing that

v * -v π k,m ∞ ≤ T π * v * -T π k v k-1 ∞ + T π k v k-1 -v π k,m ∞ ≤ γ v * -v k-1 ∞ + γ m v k-m -v π k,m ∞ + γ -γ m 1 -γ ǫ ∞ ≤ γ γ k-1 v * -v 0 ∞ + 1 -γ k-1 1 -γ ǫ ∞ + γ m v k-m -v * ∞ + v * -v π k,m ∞ + γ -γ m 1 -γ ǫ ∞ ≤ γ k v * -v 0 ∞ + γ -γ k 1 -γ ǫ ∞ + γ m γ k-m v * -v 0 ∞ + 1 -γ k-m 1 -γ ǫ ∞ + v * -v π k,m ∞ + γ -γ m 1 -γ ǫ ∞ = γ m v * -v π k,m ∞ + 2γ k v * -v 0 ∞ + 2(γ -γ k ) 1 -γ ǫ ∞ .
Adding a constant to the value v j at any step j of the algorithm does not affect the greedy policy set Gv j and only adds a constant to the next value v j+1 . As a consequence, we can assume witout loss of generality that v *v 0 sp = 2 v *v 0 ∞ , ǫ j sp = 2 ǫ j ∞ and the result follows.

From a bibliographical point of view, the idea of using non-stationary policies to improve error bounds already appears in [2]. However, in these works, the author considers finite-horizon problems where the policy to be computed is naturally non-stationary. The fact that non-stationary policies (that loop over the last m computed policies) can also be useful in an infinite horizon context is to our knowledge new.

Figure 1 :

 1 Figure 1: The deterministic MDP used in the proof of Proposition 1

Acknowledgements I thank Boris Lesner for pointing out a flaw in a previous temptative proof of Proposition 1.


Olivier Beaumont
email: olivier.beaumont@labri.fr

Nicolas Bonichon
email: bonichon@labri.fr

Ludovic Courtès
email: ludovic.courtes@inria.fr

Xavier Hanin
email: xavier.hanin@4sh.fr

Eelco Dolstra
email: e.dolstra@tudelft.nl

Mixed Data-Parallel Scheduling for Distributed Continuous Integration

Keywords: DAG Scheduling, mixed parallelism, continuous integration

In this paper, we consider the problem of scheduling a special kind of mixed data-parallel applications arising in the context of continuous integration. Continuous integration (CI) is a software engineering technique, which consists in rebuilding and testing interdependent software components as soon as developers modify them. The CI tool is able to provide quick feedback to the developers, which allows them to fix the bug soon after it has been introduced. The CI process can be described as a DAG where nodes represent package build tasks, and edges represent dependencies among these packages; build tasks themselves can in turn be run in parallel. Thus, CI can be viewed as a mixed data-parallel application. A crucial point for a successful CI process is its ability to provide quick feedback. Thus, makespan minimization is the main goal. Our contribution is twofold. First we provide and analyze a large dataset corresponding to a build DAG. Second, we compare the performance of several scheduling heuristics on this dataset.

I. INTRODUCTION

Continuous integration [START_REF] Fowler | Continuous integration[END_REF], [START_REF] Duvall | Continuous integration: improving software quality and reducing risk[END_REF] (CI) is a simple idea, that is widely used in software development: as soon as a software component is modified, the CI tools rebuilds it, runs its test suite, and notifies developers of the build status, allowing them to quickly rectify bugs. Widespread CI tools include Jenkins [START_REF] Jenkins | [END_REF], Hudson [START_REF] Hudson | [END_REF], and CruiseControl [START_REF]CruiseControl[END_REF]. In a collaborative project, it is crucial to detect bugs as soon as possible.

The value of a CI process lies in its ability to provide quick feedback to developers, as they are more likely to understand and fix bugs that when they are uncovered quickly. Therefore, parallelism is a natural solution to improve the efficiency of the process.

In the context of CI, parallelism comes into two flavors. First, the overall process can be seen as a DAG, where nodes correspond to package builds and edges correspond to dependencies among packages. The compilation of a package must complete before the compilation of packages that use it, and if a package is built on a machine, then it has to download the packages it depends on.

Second, most build tasks can in turn run in parallel on a multi-core machine. This is because each package has a build system-e.g., using makefiles or Ant-that describes a DAG of fine-grain build tasks, and build tools can exploit it to launch this build tasks in parallel-e.g., GNU Make's -j option. As we will see, the efficiency of parallelization of elementary tasks varies from package to package. We will therefore rely on the moldable task model to model parallel tasks (see [START_REF] Dutot | Scheduling parallel tasks: Approximation algorithms[END_REF] for a complete survey on parallel task models), where for each task, the processing time of the task is given for each number of cores on which it may run.

Therefore, CI can be thought of as a mixed data-parallel application [START_REF] Suter | From heterogeneous task scheduling to heterogeneous mixed parallel scheduling[END_REF], [START_REF] N'takpé | A comparison of scheduling approaches for mixed-parallel applications on heterogeneous platforms[END_REF], [START_REF] Aida | Scheduling mixed-parallel applications with advance reservations[END_REF]. The scheduling problem for mixedparallel tasks consists in deciding which compute resources should perform which task and when, so as to optimize a given metric such as the overall execution time-i.e., the makespan. For mixed data-parallel applications, the main difficulty is to decide whether to allocate more cores to run tasks faster, or to run more tasks in parallel. This question does not have an obvious answer for general task graphs. Therefore, it is of interest to concentrate on a specific application domain and on a specific dataset.

Our contribution in this paper is twofold

• First, we analyze and make available [START_REF]Hubble, a simulator for the Nix/Hydra build tools[END_REF] to the community of large dataset that is a good representative of the task graphs arising in the context of CI and we provide a simulation tool (namely Hubble [START_REF]Hubble, a simulator for the Nix/Hydra build tools[END_REF] to perform more experimentations. Hubble is based on SimGrid [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF]. The dataset consists both in the DAG of tasks and in the moldability results for the tasks themselves. Making such a dataset available to the scheduling community is important, since it enables to compare several algorithms and heuristics in a realistic context, without relying on random DAGs generators. Moreover, this example shows that the CI DAGs have specific characteristics that strongly influence the algorithms: the overall communication volume is relatively small with respect to computations, the tasks on the critical path represent more than 10of the overall computation volume,... Another important point is that several compilation artifacts are used at many places in the DAG, therefore showing the interest of scheduling algorithms that take into account the fact that tasks share files, such as proposed in [START_REF] Giersch | Scheduling tasks sharing files on heterogeneous master-slave platforms[END_REF], [START_REF] Ucar | Task assignment in heterogeneous computing systems[END_REF].

• Second, we propose and compare the performance of several algorithms and heuristics devoted to schedule CI DAGs. For instance, we propose an algorithm to deal with tasks sharing files, although the small amount of communications makes its influence of the overall scheduling time relatively small. We also show that, if we consider that compilation tasks are sequentiali.e., not moldable-it is relatively easy to reach the optimal time (the length of the critical path), even with relatively few processors. On the other hand, we show that taking the moldability of tasks into account enables to decrease significantly the CI makespan. In the context of CI, it is also reasonable to assume that CI tasks are run on a IAAS Cloud. Therefore, our study can also be used in order to dimension how many resources should be reserved to run the CI task at optimal cost.

To model contentions, we rely on the bounded multiport model, that has already been advocated by Hong et al. [START_REF] Hong | Distributed adaptive task allocation in heterogeneous computing environments to maximize throughput[END_REF] for task scheduling on heterogeneous platforms. In this model, node P i can serve any number of clients P j simultaneously, provided that its outgoing bandwidth is not exceeded by the sum of the bandwidths allocated to the communications it is involved in. Similarly, P j can simultaneously receive messages from any set of clients P i provided that its incoming bandwidth is not exceeded. This corresponds well to modern network infrastructure, where each communication is associated to a TCP connection. This model strongly differs from the traditional one-port model used in the scheduling literature, where connections are made in exclusive mode: the server can communicate with a single client at any time-step. It is worth noting that several QoS mechanisms available in modern operating systems, enable a prescribed sharing of the bandwidth [START_REF] Downey | TCP self-clocking and bandwidth sharing[END_REF], [START_REF] Abendroth | A versatile model for TCP bandwidth sharing in networks with heterogeneous users[END_REF], [START_REF] Zhu | Enhancing TCP for networks with guaranteed bandwidth services[END_REF]. Therefore, the bounded multiport model encompasses the benefits of both bounded multi-port model and oneport model. It enables several communications to take place simultaneously and practical implementation is achieved using TCP QoS mechanisms.

In this paper, we will concentrate on dynamic (on-line) algorithms. Indeed, we have observed that the time needed to perform a task, especially in the multi-core context, varies from one experiment to another. Therefore, we cannot assume that processing times of moldable compilation tasks are known exactly and we will only rely on scheduling algorithms that make their decision at runtime, depending on the available resources (idle cores), the set of ready tasks (tasks whose all dependencies have been resolved) and the (possibly static) priorities that have been assigned to the tasks.

The rest of the paper is organized as follows. Section II presents the related works. Section III presents the software distribution Nixpkgs and the DAG of packages extracted from this distribution. The shape and the moldability of this DAG is also studied. Section IV compares the efficiency of several scheduling heuristics on Nixpkgs DAG. The paper concludes with Section V.

II. RELATED WORK

In this paper, we consider the problem of scheduling a mixed data-parallel task graphs under a realistic model for communication contentions. Parallel tasks models have been introduced in order to deal with the complexity of explicitly scheduling communications and have been first advocated in [START_REF] Chakrabarti | Modeling the benefits of mixed data and task parallelism[END_REF]. In the most general setting, a parallel task comes with its completion time on any number of resources (see [START_REF] Feitelson | Scheduling parallel jobs on clusters[END_REF], [START_REF] Drozdowski | Scheduling Parallel Tasks-Algorithms and Complexity[END_REF], [START_REF] Dutot | Scheduling Parallel Tasks-Approximation Algorithms[END_REF] and references therein for complete surveys). The tasks may be either rigid (when the number of processors for executing a dedicated code is fixed), moldable (when the number of processors is fixed for the whole execution, but may take several values) or malleable [START_REF] Blazewicz | Preemptable malleable task scheduling problem[END_REF] (when the number of processors may change during the execution due to preemptions).

Static scheduling algorithms with guaranteed performance for scheduling applications structured as mixed data-parallel task graphs have been developed in the case of a single homogeneous parallel computing platform, such as a cluster in [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF], [START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF] and have been later extended to multi-clusters in [START_REF] Suter | From heterogeneous task scheduling to heterogeneous mixed parallel scheduling[END_REF], [START_REF] N'takpé | A comparison of scheduling approaches for mixed-parallel applications on heterogeneous platforms[END_REF], [START_REF] Dutot | Scheduling Parallel Task Graphs on (Almost) Homogeneous Multicluster Platforms[END_REF]. It is worth noting that if communication costs on the edges are neglected and if all tasks have the same moldability profile, then it is possible to find the optimal schedule in polynomial time [START_REF] Srinivasa Prasanna | Generalised multiprocessor scheduling using optimal control[END_REF]. Above works do not take contentions of communications in account. The problem DAG scheduling with contentions under a realistic communication model (but sequential tasks only) has been first considered in [START_REF] Sinnen | Communication contention in task scheduling[END_REF].

III. NIXPKGS MIXED DATA-PARALLEL BUILD TASK GRAPH

In this section we first present Nixpkgs distribution. We then explain how the build process of the whole distribution can be modeled as a DAG. Then, we study the shape of the DAG and the moldability of the tasks of the DAG-i.e., of the packages of the distribution. The complete dataset can be found on the Hubble web page [START_REF]Hubble, a simulator for the Nix/Hydra build tools[END_REF].

A. Nixpkgs, Nix, and Hydra

The DAG of tasks used in our experiments is a part of Nixpkgs, a software distribution used as the basis of the NixOS GNU/Linux distribution [START_REF] Dolstra | NixOS: A purely functional Linux distribution[END_REF]. Nixpkgs is both a description of the DAG of packages of the distribution-i.e., the dependencies among them-and the set of build scripts necessary to build these packages. In turn, these packages can be built using the Nix package manager [START_REF] Dolstra | Nix: A safe and policy-free system for software deployment[END_REF].

Build results are stored in the Nix store, a special directory in the file system. There is a direct, deterministic mapping between a build task (build script and set of build inputs) and the name of its result in the Nix store. Thus, the Nix store can be seen as a build cache: build results can be reused whenever they are needed, without having to perform the build again and the directory where they are stored can be easily determined.

The Hydra continuous integration system is built on top of Nix [START_REF] Hydra | [END_REF]. Hydra is notably deployed on a heterogeneous cluster at TU Delft 1 , currently consisting of two 48-core machines and three 8-core machines running GNU/Linux, as well as two dual-core machines and three VMs running other operating systems. A Hydra instance at Inria runs on a smaller, but similarly heterogeneous cluster 2 .

The Hydra instance at TU Delft continuously builds several large free software projects, in particular Nixpkgs. By continuously building the packages defined in Nixpkgs, it allows developers of the distribution to quickly spot package integration issues. For instance, changing part of the standard environment (known as stdenv) such as the C compiler or C library triggers a rebuild of all its successors in the DAG; thus, it can be quickly determined if a change in stdenv lead to a build failure.

Nix and Hydra currently rely on naive greedy scheduling strategies. Within Nix, libstore topologically sorts the build DAG and then executes tasks in this order. When a build task is ready, it is submitted to the build hook, which, by default, submits it to one of the participating machines or declines it. In the latter case, the task is scheduled locally. In the former case, the build hook copies all necessary build inputs to the target machine, so that the build can actually take place.

Optionally, Nix can exploit parallelism within a build task: if a package uses a makefile-based build system, then Nix can be told to run GNU Make with its -jN option, which instructs it to launch up to N jobs in parallel, as permitted by the sub-DAG described in each makefile.

B. Extraction of the DAG of Mixed Data-Parallel Tasks

Here we explain how we have computed the DAG of mixed data-parallel tasks that models the Nixpkgs Distri- 1 Hydra instance at TU Delft: http://hydra.nixos.org 2 Hydra instance at Inria: http://hydra.bordeaux.inria.fr bution.

For each package (that is, each node of the DAG), the size is obtained by actually building the package and measuring the on-disk size of the build output.

Likewise, the sequential time is the observed build time, and the parallel build times are obtained when trying to exploit parallelism within the task using GNU Make with the -jN , for several values of N > 1. Given that package build tasks are deterministic, these build times are reproducible.

A subset of Nixpkgs packages (approximately 60% of them) was built on a 2.8 GHz multi-core x86_64 machine with 128 GiB of RAM, with -jN -l2N , for N = 1, 2, 4, 8, 16. Values above 16 were not tried because, as we will see below, experiments showed that few packages would be able to take advantage of more parallelism.

Nixpkgs contains depencies information on build packages:

• The direct dependencies, that is the least of packages needed to build the packages. • The residual run-time dependencies of each node. Typically, the set of direct dependencies needed at run-time by a build is a subset of the dependencies required to build it; for instance, a package's build process may require a compiler and a parser generator, but these are no longer needed at run-time when using the package.

Thus, for any node of the DAG, its actual dependencies are the union of its direct dependencies and the transitive closure of their run-time dependencies. The size of a dependency is given by the size of build output of the source of the dependency.

C. DAG Characteristics

The Nixpkgs DAG (revision 31312) of build tasks has the following characteristics:

• it consists of 7,361 nodes, 38% of which are sources such as source tarballs, build scripts, and patches; • 198,637 edges-27 times the number of nodes;

• a sequential build of the whole DAG on a 2.8 GHz machine takes 100 hours; • a complete build produces 36 GiB of data (this excludes source tarballs, patches, etc.); • the total volume of dependencies is 2,302 GiB; • 96% of the nodes have a build result greater than 8 KiB; • speedup information is available for 86% of the build tasks; these build tasks correspond to 52% of the total amount of computation; some of the packages failed to build with -jN for N > 1, for instance because of errors in the build system, preventing packages that depend on it to build, hence this percentage; • the critical path consists of 33 packages and its duration is 6 hours and 47 minutes, when build tasks are themselves performed sequentially.

We expect these characteristics to be typical of GNU/Linux distributions.

These characteristics strongly influence the relative importance of computations and communications. Indeed, performing all the transfers corresponding to all the dependencies sequentially (which is a very pessimistic assumption) only takes 8 hours (on a GiB Ethernet LAN) whereas the total computation volume is about 100 hours. Our intuition is that this ratio of computation to data transfer volume is typical of continuous integration DAGs.

Another important piece of information is the "shape" of the DAG. The Nixpkgs DAG starts with a mostly-sequential sequence of build tasks, which corresponds to the tasks that contribute to bootstrapping the standard build environment (known as stdenv), that contains the C library and the C compiler, along with build tools such as GNU Make and utilities like GNU Coreutils and Perl. The stdenv build is followed by a fork, which corresponds to the fact that stdenv is a prerequisite for all the remaining build tasks. The stdenv build phase is obviously on the critical path. A similar fork/join pattern occurs close at the other end of the DAG, with the Qt library and KDE support libraries from which many applications depend.

D. Moldability

After analyzing the topology of the DAG, we now turn to the moldability of the nodes. We can see from Figure 1 that 50% of packages are purely sequential. Few package build processes are slower with -jN option. The other packages have quite different speedup values.

We now assume that each package follows the Amdahl's law: the time T (n) to build a package on n cores is equal to T (1).((1 -α) + α/n), where α is the fraction of the task that can be run perfectly in parallel. We performed a linear regression to estimate the α. Figure 2 shows the cumulative distribution of the parameter α for the tasks for which we have measures for at least 3 different values of n and whose sequential duration is larger than 300s. We can see that 45% of tasks are purely sequential and 40% of tasks have a perfectly parallel fraction greater than 80%. The mean value of α is 0.4. parallel fraction % of packages q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Figure 2. Cumulate distribution function of the parallelization fraction of tasks.

The vast majority of packages in Nixpkgs are built using makefiles, so they should potentially benefit from parallel builds with make -j. Yet, our measurements show that many package builds do not scale well. There are mainly two explanations:

• In general, package build tasks start with a purely sequential phase, often corresponding to a ./configure run. When the make phase itself has a duration comparable to the configure phase, the build task as a whole does not scale well. • Many packages rely on recursive makefiles, which limits make's ability to parallelize the build task to individual directories [START_REF] Miller | Recursive make considered harmful[END_REF].

Tackling the two above problems is out of the scope of this paper. We collected speedup information for 40% of the build tasks. For those build tasks lacking speedup information, we use the following estimation: build tasks shorter than 300 sec. are considered purely sequential, and others are assumed to follow Amdalh's law with α = 0.4. From this, we are able to predict what can be expected if we allow to use at most k cores per task. Table I summarizes this information by displaying for each possible number of cores per node (N = 1, 2, . . . , 16) the length of the critical Using only one core per task, it is not possible to build a schedule with a makespan lower than 6 hours and 47 minutes. As the ratio between the total volume of computation and the critical path length is 14.7, at least 15 cores are necessary to achieve performance close to this bound.

If we allow to run each task on at most 2 cores, 5 hours and 6 minutes is a lower bound on the makespan. Moreover if we use exactly two cores per task, at least 30 cores are necessary to achieve performance close to this bound.

If we allow to use at most 16 cores per task, the critical path length drops to 4 hours and 6 minutes.

IV. EXPERIMENTATIONS

In this section we compare the performance of several heuristics based on HEFT algorithm [START_REF] Topcuoglu | Task scheduling algorithms for heterogeneous processors[END_REF] on multi-cores machines connected with a Ethernet network.

A. Scheduling Heuristics

In all the algorithms we consider, tasks are ordered according to their upward rank-i.e., the length of the longest path from the task to any other task, the length of a path being the sum of the computation cost of the tasks of the path. Tasks are scheduled in the non increasing order of their upward rank.

We consider one static algorithm and three dynamic algorithms. The static algorithm assigns a priori tasks to cores. Dynamic algorithms run the simulation and, as soon as there are idle cores and ready tasks-i.e., tasks such that all the packages they depend on are done-it schedules the task with the highest priority (according to the upward rank order) to one or several cores. Note that the dynamic algorithms we consider can schedule a task on one or several idle cores, even if this task could finish earlier if scheduled on another machine that is currently busy.

The considered algorithms are the following ones:

• HEFT (static). This heuristic assigns the task to the core that minimizes the finish time of the task (knowing that the previous tasks are already scheduled).

• HEFT (dynamic). While there are ready tasks and idle cores do: schedule the highest priority (considering the upward-rank) ready task on the core that minimizes its finish time.

The next two heuristics use the moldability of tasks:

• MHEFT (dynamic). While there are ready tasks and idle cores do: schedule the first ready task on the smallest set of idle cores on the same machine that minimizes its finish time. • 2-CORES (dynamic). While there are ready tasks and idle cores do: schedule the first ready task on a couple of idle cores of a machine that minimize its finish time. This algorithm works only on platforms with machines with an even number of cores.

Many other heuristics have been proposed in the literature. Nevertheless, we believe that these four heuristics well represent what can be achieved in the context of Continuous Integration, given the characteristics of the DAG and the parallel profile of the tasks.

When a package artifact generated on a machine M 1 is used by another package on another machine M 2 , this artifact must be transfered from M 1 to M 2 . Here, we consider that if an artifact that has been transfered on a machine, it will remain available for the other packages (there is no need to transfer again the same file). This cache system does not change the performance of static scheduling algorithm when no contention occurs. But when we consider dynamic scheduling algorithm or take contentions into account, this has an impact on the makespan of produced schedules. On the considered dataset (and by extension in the context of CI), the cache system is quite convenient since each generated file is used on average (and therefore potentially downloaded) 24 times.

Finally, let us note that even when the considered platforms are homogeneous, the choice of the machine on which the task will be scheduled is not driven only by the number of idle cores. It is also driven by the repartition of artifacts needed by a given tasks. Hence if several machines have one idle core, the task will be scheduled on the machine that minimizes the task completion time, taking transfers into account.

B. Target systems

Experimentations were performed using the SimGrid 3.5 simulator [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF]. The platforms we have considered are multicore machines connected by a GiB Ethernet network (with an effective bandwidth of 81MiB/s). The power of each cores is 91.5 GFlop/s. These settings correspond to typical clusters used for CI, such as those described in Section III-A.

C. Results

The first question we try to answer is: what is the smallest number of processors such that the makespan is roughly equal to the critical path length? Since communications are negligible compared with computation, such lower bound may almost be reached. Since the critical path length is 14.7 times smaller than the overall volume of computations, at least 15 cores are needed. As shown in Figure 3, only 20 to cores are in fact needed by HEFT (dynamic) algorithm to reach this bound whereas HEFT (static) doesn't reach this bound with 24 cores. Concretely, with only 2 of the 3 opto-cores used in Delft, the same level of reactivity of the CI server can be achieved using a quite straightforward heuristic. To obtain better reactivity, the moldability of tasks needs to be taken into account. If we allow tasks to run on at most 2 cores, then the theoretical bound on the makespan drops to 5 hours and 6 minutes. As shown in Figure 4, this result is achieved using 40 cores only. MHEFT seems even better since almost the same performance is achieved with only 28 cores. The main drawback of MHEFT is that it only makes use idle cores. Hence if a parallel task becomes ready when there is only one idle core, this task will be schedule on this single core.

Performances could be improved using static mixed parallel scheduling heuristics (see for instance [START_REF] Suter | From heterogeneous task scheduling to heterogeneous mixed parallel scheduling[END_REF]). However using static heuristics can be efficient only when it is possible to predict accurately the duration of tasks. This last assumption is not realistic when several applications run on the cluster on which the CI server is running.

V. SUMMARY AND CONCLUSION

In this paper, we consider the problem of scheduling DAGs obtained in the context of Continuous Integration. Our contribution is the analysis of the characteristics of a large DAG corresponding to the packages of the software distribution Nixpkgs. Continuous Integration is a very attractive application for both practical and theoretical studies on DAG Scheduling. Indeed, its practical importance is clear and the natural optimization function, so as to detect bugs as soon as possible, is makespan minimization. The process can be described as a mixed data-parallel application, where the volume of communications can in practice be neglected so that efficient approximation algorithms can be derived. In this paper, we have shown that basic scheduling heuristics can achieve quasi-optimal makespan at the price of using slightly more cores, but there is still room for improvement, both to design better algorithms and to theoretically justify why basic heuristics perform well.

Figure 1 .

 1 Figure 1. Complementary cumulative distribution of package speedups for different values of the option -jN , and for package builds with a sequential duration longer than 60 seconds.

Figure 3 .

 3 Figure 3. Execution of the DAG with one core per task.(on dual cores)

Figure 4 .

 4 Figure 4. Execution of the DAG with several cores per task. (On quad cores)

Table I LENGTH

 I OF THE CRITICAL PATH AND TOTAL COMPUTATION VOLUME AS A FUNCTION (SUM OF TASK DURATIONS TIMES THE NUMBER OF CORES PER TASK) OF THE NUMBER OF CORES USED FOR EACH BUILD TASK (NCORES CORRESPONDS TO -JN ).

	cores per task	critical path (sec.) comp. volume (sec.)
	1	24,427	359,978
	2	18,378	552,004
	4	16,003	945,770
	8	14,728	1,752,833
	16	14,115	3,399,700
	path and the overall computation time if an infinite number
	of N -cores nodes were available.

ACKNOWLEDGMENT

The authors are very grateful to Arnaud Legrand and Samuel Thibault for helfpul discussions. The authors would also like to thank Lionel Eyraud and Frédéric Suter for their help with SimDAG, and the anonymous reviewers for their insightful comments.

BIBLIOGRAPHIES

Olivier Beaumont received his PhD degree from the University of Rennes in 1999. Between 1999 and 2006, he was assistant professor at Ecole Normale Superieure de Lyon and then at ENSEIRB in Bordeaux. In 2004, he defended his "habilitation a diriger les recherches" and was appointed