Pierre Amiranoff

Albert Cohen

Paul Feautrier

Instancewise Array Dependence Test for Recursive Programs

Starting from a generalization of induction variables, we present a dependence test framework for recursive programs. For a restricted class of programs, a statically computable function maps every run-time instance of a program statement to the data-structure elements it accesses. Statement instances and data structure layouts are described through formal language tools. This framework is applied to the automatic detection of data and control parallelism. We extend the concept of instancewise data dependences to recursive programs and we further investigate a dependence test for recursive programs operating on arrays. This test is interpreted as a flow problem in a directed graph with weighted edges; and the problem is shown to be NP-complete. We provide an exponential but efficient algorithm based on integer linear programming and explore simple examples.

Introduction

Our work aims at the compile-time computation of array access locations along any program execution, possibly recursive. We will derive from this computation a method devoted to precise dependence test and aggressive parallelization of recursive programs.

This paper focuses on the case of arrays, but our method and implementation extend to all "monoid-addressable" data structures, e.g., lists, trees, combined arrays and trees, etc. Its basis is the theory of regular languages and finite state transducers. Static properties are evaluated at the level of each run-time statement instance, and expressed by the means of automata and transducers.

Research in the field of automatic parallelization of recursive programs is still at its early stages. Compared to our previous work [START_REF] Feautrier | A parallelization framework for recursive tree programs[END_REF][START_REF] Cohen | Instance-wise reaching definition analysis for recursive programs using context-free transductions[END_REF][START_REF] Cohen | Program Analysis and Transformation: from the Polytope Model to Formal Languages[END_REF], a much more efficient technique is presented, implemented and experimented on several realistic examples. From the latter technique, we present the first instancewise dependence test for a class of recursive programs operating on multi-dimensional arrays. Most related works address the analysis of recursive programs with pointers, but [START_REF] Rugina | Automatic parallelization of divide and conquer algorithms[END_REF][START_REF] Gupta | Automatic parallelization of recursive procedures[END_REF] also deal with pointer arithmetic (and thus, arrays). They rely on more classical data-flow frameworks which blur the distinction between the multiple instances of a statement. Therefore, our instancewise technique yields much less false dependences, at the cost of a more constrained program model.

The Control Domain Model

Our basic principle is that the code operating on array locations is purely functional: variables appearing in array indices do not have any side-effects, i.e., they are fully characterized by the sequence of variable definition statements followed along an execution. Thus, instead of studying the trace of all statements along an execution of the program, we may limit the grain of the analysis to a sub-trace of the "meaningful statements". This model turns out to be more tractable than static analysis frameworks focusing on full execution traces.

As a general rule, static analysis brings only conservative results concerning control flow and variable values. Thus, we will not take conditional tests and loop bounds into account, and consider that both then and else branches can be taken. However, thanks to the instancewise analysis framework, we do not confuse the run-time properties of two exclusive branches. In other words, we avoid the pitfall of classical data-flow analyses which do not preserve the context of static properties.

To implement this framework, we have built up a special language named MOGUL, for MOnoid GUided Language. According to our objective, the MOGUL syntax concentrates on variables that carry the values of array indices, named induction variables (generalized from nested loops), ignoring all other variables. Thus, the principal constraint will concern operations over these induction variables. * and ta[q..der], both being sorted, * into tb with r = current index of tb *) let rec merge_ab p q r = if p < q && q <= der then begin let elp = !(List.nth !ta p) and elq = !(List.nth !ta q) in if elp < elq then begin List.nth !tb r := elp; merge_ab (p+1) q (r+1) end else begin

List.nth !tb r := elq; merge_ab p (q+1) (r+1) end end else begin if p < q then copya r p (q-1) else copya r q der end;; let rec merge_ba p q r = ...;; let rec sort_ab p q r = if p < r then begin if q <= (p+r)/2 (* dichotomy *) then sort_ab p (q+1) r else begin sort_ba p p (q-1); sort_ba q q r; merge_ab p q p end end and sort_ba p q r = ...;; copya 0 0 der; sort_ab 0 0 der;; Figure 2 shows the Pascaline example, a program to evaluate the binomial coefficients (a line of Pascal's triangle). It exhibits both a loop statement and a recursive call.

monoid Monoid_int [ 1, -1 | congr ]; structure Monoid_int A; structure Monoid_int B; function Copya (Monoid_int X, Monoid_int Y) { if test { B[X] = A[Y]; Copya (X.1, Y.1); } } function Copyb (Monoid_int X, Monoid_int Y) { ... } function Merge_ab (Monoid_int P, Monoid_int Q, Monoid_int R) { if test if test { B[R] = A[P]; Merge_ab (P.1, Q, R.1); } else { B[R] = A[Q]; Merge_ab (P, Q.1, R.1); } else if test Copya (R,P); else Copya (R,Q); } function Merge_ba (Monoid_int P, Monoid_int Q, Monoid_int R) { ... } function Sort_ab (Monoid_int P, Monoid_int Q, Monoid_int R) { d if test f if test B Sort_ab (P, Q.1,

Interprocedural Control Flow Graph

We represent the execution of recursive programs with control flow graphs enriched with a stack. Its role is to track the succession of procedure calls and returns.

Merge_ba

(p, q, p) Sort_ab (q, q, r) Merge_ab (p, q, p) Sort_ba (q, q, r) q < (p+r)/2 q < (p+r)/2 A trace prefix denotes the part of a complete trace relative to an unachieved execution. An instance is a particular execution of a statement during a given execution of the program, it is associated with a unique trace prefix.

Sort_ab

Control Words

The basic principle is as following: a partial or complete execution trace is structured as a nest of "blocks", each terminal or compound statement being such a block. Executing any statement (even a terminal one) will be interpreted as calling a function with dynamic stack allocation followed by deallocation when completed. In the special case of loops, each iteration is nested in the previous one and all are closed back at the loop completion.

Following this principle, we will consider the extended stack which carries the sequence of all labels representative of those statements that have been "opened" since the beginning of execution and not "closed" yet. The word stored in the extended stack is called control word. Combining this extended stack with the interprocedural control flow graph yields a pushdown automaton accepting the trace language. The stack language of a pushdown automaton is a rational language [START_REF]Handbook of Formal Languages[END_REF], hence the control words language is rational.

Example. Figure 4

Figure 5. Control Automaton of To & fro

The control automaton is derived from the control flow graph: in the latter, a sequence of successive statements takes form as successive edges, while in the control automaton each of these statements is linked by an edge from the common enclosing statement, see Figure 5. All states are final. Since return nodes are useful only for execution traces but out of interest for dependence analysis, we will simply ignore them. Note that control automaton makes no distinction between the sequence (;) and the conditional.

Instances

Among all possible executions of the program (according to input data and test results), it is easy to see that a given control word may be the abstraction of many trace prefixes, possibly an infinite number. As an example, considera trace prefix containing the trace of a conditional statement completed during the instance it represents, the control word has "forgotten" which branch has been executed. In this context, an instance is the equivalence class of all partial executions (trace prefixes) that generate the same control word.

Nevertheless, if we limit our instance domain to a particular execution of the program, it's easy to prove that no more that one trace prefix can be associated with a given control word. In that sense, a control word is representative of a unique instance during an execution.

Induction Variables and Binding Functions

Traditionally, addresses in a mono-dimensional array can be expressed via an integer index, and in a multidimensional one via a vector of integer indices. We limit ourselves to arrays indexed through affine expressions of some specific variables, from now onwards referred as induction variables.

Definition and Office

For each induction variable, a binding function maps each instance, i.e., each control word, to each value of this induction variable. Of course, the result makes sense only if the induction variable is syntactically alive at this instance. In To & fro, induction variables are the formal parameters of all functions. In Pascaline, the loop index is also an induction variable. As mentioned earlier, MOGUL syntax only allows definition of induction variables at the beginning of a block.

Since the control word loses the trail of any operation executed during a completed statement, the exigency of exactness in references computation dictates that a statement execution has no side effects upon induction variables defined outside of that statement. The environment is thus characterized by the extended stack, and induction variables are managed in single-assignment, quite similarly to a pure functional language.

Another constraint concerns the type of operations over the induction variables. Indeed, a modification of one induction variable has to be modeled as a transition in a transducer. • Given two induction variables i and j (possibly identical), we may define i with the value of j plus an increment:

Operations Over the Induction Variables

i 2 = j 1 + k.
Of course, depending on the statement, several induction variables may be defined simultaneously according to these rules. For our both running examples, it's immediate that the required exigencies are satisfied.

Binding Transducer

The representation of binding functions is called the product transducer. The latter is built as follows: except for the initial state, we duplicate the control automaton so that each induction variable is assigned its own copy of each control automaton state. Each state is a "meeting point" for the values of a given induction variable, for any control word at this program point. In addition, each statement label is paired with its induction variable definitions, in order to map control words to the value of every induction variable. Indeed, each transition is labeled with a pair of a statement label and a constant, we call such pairs bilabels, see Figure 6. If the induction variable q inherits its value from p at the entrance of statement s, as q = p + k, then the product transducerhas an edge from the node dedicated to p before s to the one dedicated to q after s.

The case of constant assignment x = k is specific: we consider an additional induction variable named z whose value is always 0. When x is defined to k at the opening of statement s, the node dedicated to induction variable x after s is the arrival state of an edge coming from the node dedicated to z just before execution of s, with the bilabel (s|k).

We may suppress from the tranducer any subgraph referring to an induction variable that is not alive at the corresponding program points, or -in the case of z -not useful for computation. Remaining nodes are final.

Figure 6 presents the product transducer for Pascaline, much simplerthan To & fro's one. Notice the loop iteration (g) is described by a loop edge. Moreover, the case of the initialization of induction variable I at loop entry G is interesting: it is captured by a "transversal" edge from a state associated with the additional induction variable z to a state associated with I.

A | @ A | @ B | @ C | @ D | @ E | @ F | 1 g | @ H | @ I | @ G | @ g | 1 H | @ I | @ J | @ J | @ B | @ C | @ E | @ D | @ F | @ G |

Figure 6. Product Transducer of Pascaline

Building the product transducer is linear in the number of statements and also linear in the number of induction variables. Surprisingly, the previously available algorithm was exponential in the worst case [START_REF] Cohen | Program Analysis and Transformation: from the Polytope Model to Formal Languages[END_REF]: it relied on Gaussian elimination on the non-commutative semi-ring of regular expressions.

Instancewise Dependence Test

Let us now apply the instancewise information captured by the binding transducer to dependence test and parallelization. In this part, the analysis must be applied separately to each array, but we will omit the array name to simplify notations.

Exploitation of the Binding Information

We focus on two forms of automatic parallelization:

• scheduling of instructions and procedure calls within a program block;

• discovery of procedure calls that may safely be made asynchronous, enabling parallel execution of the callee with the following code in the caller.

Recursive programming blurs the distinction between data and control parallelism, since any data-parallel loop may be rewritten as a procedure with asynchronous recursive calls -with a low sequential overhead. These two forms of parallelization are based on a restricted type of block-related dependence information, the synthetic dependence graph [START_REF] Feautrier | A parallelization framework for recursive tree programs[END_REF]: considering an instruction s preceding an instruction s ′ in the same program block,1 there is a synthetic dependence from s to s ′ if and only if two instances spawned by s and s ′ access the same memory location. If s and s ′ are not synthetically dependent, they may be safely reordered or executed asynchronously within the enclosing block.2 Formally, the synthetic dependence relation, denoted by ∆ is, where Σ * is the control words free monoid:

s∆s ′ ⇐⇒ ∃u, v, v ′ ∈ Σ * : B(usv) = B(us ′ v ′ ). (1)
The set of instances spawned by statement s will be called the cone from summit s. The partial order between instances s and s ′ defined in (1) is the cone-to-cone order ≪ s,s ′ . An example will be presented in Section 5. The dependence transduction δ s,s ′ = κ ∩ ≪ s,s ′ extracts from κ cone-to-cone ordered couples of control words, i.e., it describes the instancewise dependence relation between control words according to the binding function B and the cone-to-cone order ≪ s,s ′ . Dependence transductions and synthetic dependences are linked through the following result:

The Dual Dependence Test Transducer

δ s,s ′ = ∅ ⇐⇒ s∆s ′ . ( 2
) τ * s,s ′ Word Address B τ s,s ′ B ≪ s,s ′ Word Control Control Word

Figure 7. Dual Dependence Test Transducer

To decide emptiness of δ s,s ′ is equivalent to test whether the dependence test transduction τ s,s ′ = κ• ≪ s,s ′ is disjoint from the identity transduction =. Like κ, τ s,s ′ is not a rational transduction. Therefore, this way of describing dependences does not lead to a computable method. Let us define the dual dependence test transduction τ * s,s ′ = B• ≪ s,s ′ •B -1 ; τ * s,s ′ is rational since the intermediate language during both compositions is the control words free monoid Σ * . Figure 7 shows that the former δ s,s ′ emptiness problem of boils down to the disjointness of τ * s,s ′ and the identity transduction =.

Building the dual dependence test transducer involves two compositions with transducers of the same order of magnitude in states and edges number, i.e., in the total numberof statements. Its complexity is thus cubic in the number of statements. This sometimes leads to huge intermediate transducers with more than 10000 states and edges. Fortunately, these transducers are very redundant and a minimization procedure (including determinization) succeeds in achieving a simplification by a factor of 100 or more, leading to less than 10 states and edges in many cases. Improving the composition algorithm in order to limit the size of intermediate structures is a very promising topic, but the small size of the result is already sufficient to apply a somewhat more complex dependence test, as we will see in the next section.

Algorithm for Existence Test

Considering a d-dimensional array, we have just shown that dependence between two statements s and s ′ is equivalent to the existence of a d-dimensional vector v such that vτ * s,s ′ v (without taking loop bounds and conditionals into account).

From a transducer implementing τ * s,s ′ , let us build a directed graph G s,s ′ whose vertices and edges are the states and the transitions of the transducer, respectively, labeling each edge with the difference between the transition's output and input vectors. E.g., a transition labeled -1|2 yields an edge labeled 3. Initial and final states in the transducer are called initial and final vertices in G s,s ′ .

Dependence between s and s ′ is now equivalent to the following decision problem: "is there a zero-weight path between the initial and final vertices in G s,s ′ ?" Decidability. Let us examine first the case of arrays of dimension 1. From G s,s ′ , we may build a push-down automaton with empty alphabet and one stack symbol (one-counter automaton) where 0 in the counter is realized by the empty stack. Testing whether the language recognized by a pushdown automaton is empty is a well-known decidable problem.

Concerning multi-dimensional arrays, note that computations over dimensions are independent from each other.

So, its suffices to test emptiness of the intersection of each dimension languages.

A Flow Algorithm. This zero-weight path problemthough quite natural and similar to the flow problemcould not be found in the literature. It has been proved NPcomplete, even in the acyclic case, through a simple reduction from the bipartition problem. Nevertheless, this problem is known to admit a rather efficient pseudo-polynomial solution, i.e., there is a polynomial algorithm when the integers involved are small. This is the case in practical graphs G s,s ′ , since the labels are of the same orderas the induction variable strides in the source program. We are thus encouraged in the search of an exact solution to the dependence problem.

Our proposed solution is not pseudo-polynomial yet, but seems very applicable to practical graphs. It relies on a two-step encoding into integerlinearprogramming. The example in Figure 8 illustrates the formal presentation. Each edge e in G s,s ′ = (V, E) is associated with a variable k e . We assume, without loss of generality, that G s,s ′ has only one initial (resp. final) vertex with no incoming (resp. outgoing) edges (this condition is easily achieved with two additional vertices and zero-labeled edges).

First of all, suppose that G s,s ′ is acyclic. Calling O the set of outgoing edges of the initial vertex and I the set of incoming edges of the final vertex, add constraints e∈O k e = 1 and

e∈I k e = 1. (3)
By construction, there is a dependence between s and s ′ if and only if the system of affine equalities S s,s ′ = (3, 4, 5) has a solution. We have just converted our flow problem into another, well known, NP-complete problem. Fortunately, system [START_REF] Cohen | Program Analysis and Transformation: from the Polytope Model to Formal Languages[END_REF][START_REF] Cohen | Instance-wise reaching definition analysis for recursive programs using context-free transductions[END_REF] is easy to solve using Gaussian elimination, since every minor of the constraint matrix is either singular or unimodular. Thus, the full system S s,s ′ can efficiently be addressed using integerlinearprogramming techniques: traditional pivoting of the simplex method [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] applies to the unimodular part of the matrix, possibly with additional Gomory cuts [START_REF] Schrijver | Theory of Linear and Integer Programming[END_REF] to handle the remaining constraints associated with (5). Now consider the case of a cyclic graph G s,s ′ . The path constraint is not anymore enforced by [START_REF] Cohen | Program Analysis and Transformation: from the Polytope Model to Formal Languages[END_REF][START_REF] Cohen | Instance-wise reaching definition analysis for recursive programs using context-free transductions[END_REF]: there may exist an isolated circuit disconnected from the main path between the initial and final vertices. Indeed, a circuit may only exist in a path if it is reachable from the initial vertex. In other words, performing a topological sort of G s,s ′ , a backward edge targeting vertex v may be taken only if a forward edge targeting v is also taken. If we denote F v and B v the sets of forward and backward edges of v, respectively, this fact leads to a disjunction of affine constraints as follows:

e∈Bv

k e = 0 ∨ e∈Fv k e ≥ 1.
In the worst case, each vertex v (targeted with backward edges) generates two additional constraints and, leading to an exponential number of systems. Feasibility of at least one of these systems is sufficient to show that s and s ′ are dependent. But an arbitrary association of such constraints yields no solution in general, because circuits are often sequenced on a single path or nested together in G s,s ′ ; e.g., a loop nest always leads to a linear number of systems.

Implementation and further study of the algorithm complexity are left for future work, but current results show that practical solutions to our dependence test problem do exist. S 1 has no solution but S 2 has an infinite number of solutions, the shortest (in terms of the associated path) being

k 9 = 0, k 1 = k 2 = k 4 = k 5 = k 6 = k 7 = k 8 = 1 and k 3 = 3. -2 k5 2 k3 k6 0 k2 -2 k4 0 0 k9 k1 -1 -1 k7 0 k8 G s,s ′ S1 =                        k1 = 1 k8 + k9 = 1 k1 + k6 = k2 + k7 k2 = k4 k4 = k5 k5 = k6 + k9 k7 = k8 k3 = 0 -k1 -2k2 + 2k3 -2k5 -k7 = 0 S2 =                        k1 = 1 k8 + k9 = 1 k1 + k6 = k2 + k7 k2 = k4 k4 = k5 k5 = k6 + k9 k7 = k8 k2 ≥ 1 -k1 -2k2 + 2k3 -2k5 -k7 = 0

Implementation and Experiments

We realized in OCaml a complete implementation of the procedure that takes a MOGUL program source in input and returns the dual dependence test transducer according to the choice of data structure and cone summits.

In order to easily pass from any automaton or transducer to anotherone of eithertype, we have implemented a library of generic tools, parameterized by the types of state labels and transition labels. Graphs of automata and transducers are designed through the dot software [START_REF] Koutsofios | Drawing graph with dot[END_REF]. Thanks to several steps of minimization, trimming and ad-hoc reduction, the dual dependence test transducergraph appeared very simple for the programs we tested, and answer to the dependence test might be found directly while examining it.

Experiments with the To & fro Program. Function

Sort ab is recalled in Figure 10.

Applying the dependence test algorithm on the dual dependence test transducers τ * C,E and τ * D,E yields two synthetic dependences, as expected intuitively. Figure 9 is the result of our implementation for τ * C,E . Since all states, including the initial one, are final, dependence test answer is obviously "yes". Figure 11 shows the "corrected" synthetic dependence graph of function Sort ab. Using the spawn/sync asynchronous function call from the Cilk parallelization tool [START_REF] Frigo | The implementation of the cilk-5 multithreaded language[END_REF], one may automatically deduce the parallel program in Figure 12.

Beyond the To & fro program. Figure 13 shows some facts about the recursive programs we implemented in MOGUL. Since our last publication in the field [START_REF] Cohen | Program Analysis and Transformation: from the Polytope Model to Formal Languages[END_REF], we discovered many recursive algorithms suitable for implementation in MOGUL and instancewise dependence analysis. Therefore, it seems that the program model encompasses many implementations of practical algorithms despite its severe constraints.

Conclusion and Perspectives

We introduced by examples a language dedicated to a class of recursive programs. This enabled us to extract from them the instancewise mapping between run-time instances and array elements. This analysis is exploited for an instancewise dependence test that can handle multidimensional arrays. This problem was previously consid- However, much work is underway to make this technique practical. First of all, we are aware that many useful algorithms are not compatible with the induction variable constraints. In addition, recall that conditional expressions and loop bounds have not been taken into account, leading to several examples with false dependences. Generalization and/or graceful degradations of the framework should thus be developed. We are currently investigating both ap-proaches.

  let der = ... (* arrays'length -1 *) let ta = ref ... let tb = ref ...;; (* copy ta from x to r into tb at y *) let rec copya y x r = if x <= r then begin List.nth !tb y := !(List.nth !ta x); copya (y+1) (x+1) r end;; let rec copyb y x r = ...;; (* merge the sub-arrays ta[p..q-1]

Figure 1 . 2 . 1 .Figure 2 .

 1212 Figure 1. Program To & fro

Figure 3

 3 presents the control flow graph for To & fro, simplified for readability (we omitted the body of functions Merge ab and Merge ba).

Figure 3 .

 3 Figure 3. Control flow graph of To & fro

  shows a complete trace. Above the simplified version, we present a full version, i.e., enriched with the indication of statement closures (overlined). Below this trace, several associated control words are presented. We may deduce them from the full version trace, by considering that a pair of side by side corresponding labels, the first simple and the other overlined, annihilate each other from control words, according to the Dick languages reduction.Control Automaton. We show on the running example how to construct a finite state automaton that recognizes the control

Figure 4 .

 4 Figure 4. A trace and some associated control words

Figure 7

 7 Figure 7 supports the following presentation. The conflict transduction κ = B -1 • B maps each instance to each of the instances which potentially access the same references. Because the intermediate monoid is Z n , κ is not a rational transduction. Instead, we stick to transduction compositions where the intermediate monoid is free: the Elgot and Mezei theorem [6, 1] shows that such a composition yields a rational transduction, and provides a quadratic algorithm to build the resulting transducer.The dependence transduction δ s,s ′ = κ ∩ ≪ s,s ′ extracts from κ cone-to-cone ordered couples of control words, i.e., it describes the instancewise dependence relation between control words according to the binding function B and the cone-to-cone order ≪ s,s ′ . Dependence transductions and synthetic dependences are linked through the following result:

Then, calling O v and I v , respectively, the sets of outgoing and incoming edges of any non-initial and non-final vertex v, add constraint e∈Ov k e = e∈Iv k e . ( 4 )

 4 The two previous constraints are analogous to the Kirchhoff law in electrical engineering. It is easy to show that any solution (k e ) e∈E satisfying these constraints describes a path between the initial and the final vertices: each edge e has k e occurrences in this path (0 or 1 because the graph is acyclic). Finally, calling (w i e ) 1≤i≤d the d-dimensional integer vector labeling edge e, add d constraints to enforce the zero-weight property.∀i, 1 ≤ i ≤ d : e∈E w i e k e = 0.

Figure 8 .

 8 Figure 8. Encoding into systems of affine inequalities

Figure 9 .

 9 Figure 9. Test Transducer for τ * C,E .However, considering the dual dependence test transducer τ * C,D , the algorithm should not be able to find a zero-

Figure 12 .

 12 Figure 12. Parallel version of Sort ab

By definition, s and s ′ cannot label exclusive branches of a conditional.

2 A block closing implicitly corresponds to a synchronization, waiting for completion of every statement in the block.

Acknowledgments. We would like to thank Véronique Donzeau-Gouge and Catherine Dubois for their important contributions to the semantical foundation of the control word and induction variable concepts. The dependence test complexity has been studied with the help of Guillaume Huard who designed a simple reduction from the bipartion problem.


Albert Cohen

Daniela Genius

Abdesselem Kortebi

Zbigniew Chamski

Marc Duranton

Paul Feautrier

Multi-Periodic Process Networks

Keywords:

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Context and Goals

The need arises for hardware units to handle new kinds of video applications, combining multiple streams, graphics and MPEG movies, leading to increased system complexity. When beginning the design of a video system, the engineer is primarily interested in quickly determining the hardware requirements to run an application under speci c real-time constraints.

Multi-Periodic Process Networks (MPPN) model heterogeneous video-stream applications and help resource allocation. They describe an application's structure and temporal behavior, not precise functionality of processes, and they may interact with a high-level language from which scheduling and resource allocation are determined. However, MPPN are not intended to model reactive systems with unpredictable input events 2] or dynamic process creation. On the opposite, our model provides precise information regarding the steady state of a deterministic application mapped to a parallel architecture. We believe MPPN are well suited to help the mapping of a video lter or 3D graphics pipeline to explicitly parallel micro-architectures, e.g. clustered VLIW embedded processors.

Related Work

Three theoretical models have in uenced MPPN: Petri nets, data-ow graphs and Kahn Process Networks (KPN). Petri nets are inherently asynchronous and handle time constraints [START_REF] Berthomieu | Modelling and Veri cation of Time-Dependent Systems Using Time Petri Nets[END_REF][START_REF] Diaz | Time Streams Petri Nets, A Model for Timed Multimedia Informations[END_REF][START_REF] Cohen | Algebraic system analysis of timed petri nets[END_REF]. MPPN may be simulated by timed Petri nets but this does not bring precise schedule information. The sub-class of discrete event systems 1, 4] enables scheduling and performance analysis but does not model token assembling/splitting. Data-ow graphs are a well-established means to describe asynchronous processing: various properties can be veri ed, such as bounded memory 11, 5]. Both models capture repetitive actions through cyclic paths whose production rate compel performance, whereas stream-processing applications bene t from alternative descriptions such as lazy streams. Indeed, KPN 9] are closer to our approach: they provide (unbounded) FIFO bu ers with blocking reads and non-blocking writes while enforcing deterministic control. But real-time is not considered and processes have no observable semantics. Synchronous approaches 6] are based on clock calculi and enable synchronous code generation, but static steady-state properties are not available. In our deterministic stream-processing context, properties such as degree of parallelism, bu er size and bandwidth are out of reach of these popular models. Other approaches are complementary to MPPN. Alpha 12] is a high-level language for semi-automatic scheduling and mapping of numerical applications to VHDL. Within the Ptolemy project 5], Compaan targets automatic KPN generation from MatLab loop nests 10]; it is also a powerful simulation tool. KPN ing, though frequently used in co-design, is insu cient for streams of structured data. As an introductory example consider downscaling of a video image is decomposed into a sequence of horizontal and vertical ltering. The former operates on pixels and the latter operates on lines | see Figure 1 for a simpli ed KPN model. A certain number of pixels/lines is used to determine the new, smaller number of pixels/lines. We assume a horizontal downscaling of 8:3 and a vertical downscaling of 9:4 (High De nition to Single De nition). Figure 1 describes the \data reordering" occurring within stripes, between the horizontal and the vertical lters. First of all, the hierarchy captures non-FIFO communication without resorting to an explicit reorder process. More importantly, each passage through a hierarchy boundary corresponds to an explicit synchronization, where larger messages are considered, consisting of a xed number of smaller messages. This hierarchical synchronization of events is called multi-periodic: it will be characterized through multiple, hierarchically layered, periodic schemes. { if pi and p k are immediately enclosed by the same process or at the upper level, j 2 out(pi), l 2 in(p k ), then p j i p l k is a at atomic channel; { if pi is immediately enclosed by p k , j 2 in(pi), l 2 in(p k ) (resp. out(pi), out(p k )), then p l k p j i is a downward atomic channel (resp. p j i p l k is an upward atomic channel); { if p j i p l k 2 C and p l k p l 0 k 0 2 C, then p j i p l 0 k 0 is also a channel (not an atomic one); p j i p l k and p l k p n m are called sub-channels of p j i p n m .

C flat , C down and C up are the sets of at, downward and upward atomic channels, respectively. The MPPN for the downscaler in Figure 2 illustrates these de nitions. It is built from three compound processes, p 2 , p 5 , p 7 , and ve atomic ones. Digits accross process boundaries are port numbers: p 2 is a path in Figure 2. A port or process is reachable from another port or process if there exists a path from the latter to the former. Eventually, any output port of a compound process p i must be reachable from an input port of p i . For the sake of clarity, we only consider acyclic networks with periodic input streams (see Section 7 for extensions).

Network Semantics

We now enrich the network structure with data-ow activation and message semantics to model the execution of a stream-processing application.

During the course of execution, processes exchange messages and activate in response to receiving such messages. For each process p i (resp. port p j i ), the activation count is de ned as the number of activations of p i (resp. the number of messages hitting port p j i ) since the last activation of the enclosing process | or since the beginning of the execution if p i is at the highest level of the hierarchy. Activation and message dates are de ned likewise: date 0 corresponds to the last activation of the enclosing process | or the beginning of the execution of an outermost process | and all activation/message dates of sub-processes and ports are relative to this activation.

The model is designed such that local event dates only depend on the local event count, i.e., previous activations of the enclosing process have no \memory" e ect. This locality property is one of the keys to compositionality | see Section 4.3. It also enables the following de nition: an execution of a MPPN is a pair of non-decreasing functions (act; msg), such that act : P N ! R maps processes and activation counts to activation dates, msg : fp j i j p i 2 P ^j 2 in(p i ) out(p i )g N ! R maps process ports and message counts to message dates; act(p i ; n) is the date of activation n of process p i , msg(p j i ; n) is the date of message n hitting port p j i .

Propagation in atomic channels

When a big message is sent through a at channel and decomposed into smaller ones, the rst small message is received right after the big one is sent (pending some communication latency). Conversely, building a big message out of smaller ones takes additional time: many small messages must be sent before a big one is received. In both cases, n messages of size Q l k hitting port l of p k through p j i p l k correspond to dnQ l k =Q j i e messages sent by p i .

In addition, we assume a constant communication latency c j;l i;k for an elementary message sent through an atomic channel p j i p l k . Recalling that msg(p l k ; n) is the date of the (n + 1)-th message hitting port l of process p k ,

8p j i p l k 2 C flat : msg(p l k ; n) = msg p j i ; d(n + 1)Q l k =Q j i e 1 + c j;l i;k :
(1) Considering an upward channel, the propagation equation sums the activation date of the enclosing process and the local (relative) date of the last small message assembled to build an output message at port p l k : 8p j i p l k 2 C up : msg(p l k ; n) = act(p k ; n) + msg p j i ; dQ l k =Q j i e 1 : [START_REF] Berry | The synchronous approach to reactive and real-time systems[END_REF] Considering a downward channel, hierarchical composition enforces that no message enters a compound process before it activates. More precisely, when a message reaches an input port of a compound process p i , this message is not propagated further on the channel (and possibly decomposed) before p i activates on this very message. Activation of p i coincides with the reception of a message at port p l k , since Q l k Q j i (decomposition into smaller messages). Therefore, 8p j i p l k 2 C down : msg(p l k ; n) = 0:

(3)

Activation model

We consider a data-ow scheme: process activation starts as soon as there is at least one message on each input port. Let Q j i be the size of messages sent or received on port j of p i . A process p i enters activation n as soon as the following data-ow condition is met: every input port j 2 in(p i ) has been hit by message n of size Q j i (except for special clocked processes, see Sections 4.4). The data-ow activation scheme is formalized as follows:

act(p i ; n) = max j2in(pi) msg(p j i ; n): [START_REF] Boudec | Network Calculus[END_REF] This de nition allows multiple overlapping activations of a process. Considering an atomic process p i , we call `j i the latency of p i for sending a message through output port j. It is de ned as the elapsed time between an activation of p i and the corresponding output of a message through port j, supposed constant for all executions of the process: msg(p j i ; n) = act(p i ; n) + `j i :

(5) This constant latency will be extended to compound processes in Section 4.3.

In the following, details and proofs that had to be left out can be found in 7]. While any size change of messages is possible when traversing a process or channel, the same is not true when traversing a path. As a consequence of the previous equations, in order to ensure compositionality, message sizes must obey a strict scaling rule when traversing hierarchy boundaries. Let us consider a compound process p i , an input port j 2 in(p i ) and an output port l 2 out(p i ).

If these ports are connected through a path of channels and sub-processes of p i , one single message hitting p j i may traverse several assembling/splitting stages through , but it must yield one single message hitting p l i . This is intrinsic to the hierarchical model; the following path constraints enforce the scaling rule:

1 Y p j i p l k 2 (Q j i =Q l k ) = 1 and 8 0 pre x of : Y p j i p l k 2 0 (Q j i =Q l k ) 1: (6)
Activation of a source (input-less) process p i is not constrained by any data-ow scheme. We assume a periodic behavior instead: considering two real numbers act(p i ; 0) | the reference date | and per(p i ) | the period, act(p i ; n) = act(p i ; 0) + nper(p i ):

Latencies of compound processes

Consider an output port j of a compound process p i . We can prove that every activation of p i sends one message through p j i after a constant latency. This result lies in the data-ow equations (message propagation and activation rules are time invariant) and in the scale factor constraint (6) which ensures that any single activation of p i sends exactly one message through p j i . We may thus extend [START_REF] Buck | Ptolemy: A framework for simulating and prototyping heterogeneous systems[END_REF] to compound processes: msg(p j i ; n) act(p i ; n) is a constant, `j i can be computed for n = 0 based on information at the lower level: 8p i 2 P; j 2 out(p i ) : `j i = msg(p j i ; 0) act(p i ; 0): (8) Thus, MPPN exhibit compositional semantics. Latencies of compound processes do not depend on the surrounding network: they are computed once and for all.

Clocked processes

We provide an extended kind of process to synchronize streams over a xed clock period: clocked processes. These processes can be either atomic or compound, and their activation rule is generalized from ordinary processes. Considering a clocked process p i , an internal clock starts at the reference date act(p i ; 0), and subsequent activations may only occur one at a time when all input messages are present and when an internal clock tick occurs. To put it simple, a clocked process has a double role of (local) sampling and delay. A clocked process p i is characterized through a clock frequency f i such that f i 1=per(p i ); equality enforces periodicity (e.g., to enable stream resynchronization for video output).

When enclosed in compound processes, MPPN clocks behave di erently from hardware clocks (whose semantics is exclusive): two independent activations of a compound process may trigger overlapping streams of events on clocked subprocesses. This is required to preserve compositionality. In practice, the designer may want the enclosing process to be clocked itself so that executions of the clocked sub-process are sequential, e.g., in dividing the frequency of the clocked sub-process by the hierarchical scale factor.

High Level Properties

From the abovementioned MPPN semantics, one may deduce resource requirements of the application. In this paper, we focus on conservative estimates for the number of functional units, bandwidth and bu ers. We derive global (absolute) properties from the product of local evaluations.

Asymptotic Periodic Execution

We have proven that all processes follow a steady-state scheme which extends and relaxes the periodic constraint (7) on source processes; starting from [START_REF] Cohen | Multi-periodic process networks: Technical report[END_REF], this follows inductively from (1), ( 4) and (5). For each process p i , there exist an average period per(p i ) and a burstiness adv(p i ) such that 8n 0 : (n adv(p i ))per(p i ) act(p i ; n) act(p i ; 0) nper(p i ) (9) 8n 0 : (n adv(p j i ))per(p i ) msg(p j i ; n) msg(p j i ; 0) nper(p i ): [START_REF] Kienhuis | Compaan: Deriving process networks from matlab for embedded signal processing architectures[END_REF] The burstiness is the maximal number of advance activations of p i , i.e., activations ahead of the periodic execution scheme. This parameter encompasses both deterministic bursts of early messages and jittering streams with earliest/latest bounds (and, possibly, periodic resynchronization). Even under the worst-case conditions, better evaluations of act(p i ; n) can be hoped for (possibly exact ones): deterministic event bursts can be characterized e ectively within the relaxed periodic scheme.

Considering an output port j of a process p i , messages hit j after a constant delay, hence output message burstiness is equal to activation burstiness: 8j 2 out(p i ) : adv(p j i ) = adv(p i ): [START_REF] Lee | Architectures for statically scheduled data ow[END_REF] This equation stands for both upward channels (in compound processes) and atomic processes.

Sending one message and adv(p j i ) advance messages at port p j i corresponds to sending Q j i (1+adv(p j i )) bytes of data. These data are received as one message plus adv(p l k ) advance messages at port p l k , i.e., Q l k (1 + adv(p l k )) bytes. For at channels, the result is the following:

8p j i p l k 2 C flat : Q j i (1 + adv(p j i )) = Q l k (1 + adv(p l k )); ( 12
)
for downward channels, a single activation of the enclosing process is considered:

8p j i p l k 2 C down : Q j i = Q l k (1 + adv(p l k )): (13)
Notice that ( 12) and ( 13) may require burstinesses to be non-integer. In addition, communication may be implemented through bounded bu ers as long as asymptotic data throughput is the same at both ends of a channel:

8p j i p l k 2 C : Q j i =per(p i ) = Q l k =per(p k ): (14)
Activation burstiness can be deduced from the data-ow scheme, replacing act(p i ; n) and msg(p j i ; n) by their lower bounds in ( 4). The result is that processes tend to \smooth" message bursts and initiation delays:

adv(p i ) = min j2in(pi) n adv(p j i ) + act(p i ; 0) msg(p j i ; 0) per(p i ) o : (15)
This is a two-phase computation: on a given stream, sum up the burstiness and the number of messages that precede activation 0, then minimize these adjusted burstinesses. If the process is clocked, the former result is multiplied by 1 1=(f i per(p i )); one expectedly get adv(p i ) = 0 when per(p i ) = 1=f i .

Global properties

We call `i the latency for p i to complete an execution, i.e., the maximum of `j i at output ports j of p i : `i = max j2out(pi) `j i . Let overlap(p i ; d) denote the maximum number of executions of p i during a given period of time d, and triggered by a single activation of the enclosing process (if p i is a sub-process): overlap(p i ; d) = min df i de; d=per(p i ) + adv(p i ) :

We proved that the (absolute) maximal number of parallel executions of a process p i is bounded by the product of the local maximal number of activations of p i and all its enclosing processes during the same duration `i:

maxpll(p i ) = Y pivp k overlap(p k ; `i):
Depending on the architecture and the resource allocation strategy, ports associated with physical input/output may be identi ed. On this subset, it is legitimate to ask for an estimate of the average and maximal bandwidths. Such estimates can be built from the periods, burstinesses and overlapping factors, see 7] for details. Our current model assumes that actual loads/stores are distributed evenly over the whole access period `j i . This hypothesis is optimistic, but ner evaluations can be crafted following the same reasoning. Port bandwidth is of critical interest when implementing process communications through shared-memory bu ers, whereas channel bandwidth provides some insight about network contention when focusing on distributed architectures.

We describe a method to bound bu er size for any atomic channel, not considering architecture-speci c bu er requirements. The minimal size of a bu er for channel p j i p l k is the maximum amount of temporary data that must be stored during message propagation through this channel; it is denoted by maxbuf(p j i p l k ). Such a bu er must hold all the messages sent to the channel by p i and not yet received by p k , i.e., the di erence between data sent and received. An upper bound of this di erence is evaluated from the liveness of a message and the product of overlapping factors.

Network Analysis

The analysis of a multi-periodic process network consists in solving the above equations. Let us sketch an algorithm for MPPN analysis and veri cation.

Input. A multi-periodic process network, Q j i for each port, c j;l i;k for each atomic at channel, `j i for each atomic process, reference date act(pi; 0) for each source process (e.g., 0), period per(pi) for one process per weakly-connected component of the network, burstiness adv(pi) for each source process. Optional values for other parameters, e.g., burstinesses and periods at sink processes.

Output. Values for all parameters or contradiction. Resolution. The algorithm is decomposed into four phases.

1. Perform a topological sort of the network. Check the scaling rule of all compound processes, using (6).

2. Compute per(pi) traversing the network incrementally, starting from processes with known periods using (14) and checking for consistency. 3. Traverse the hierarchical structure bottom-up, applying the following steps: { choose a compound process pi whose sub-processes have known latencies; { compute (relative) reference dates for sub-processes, using (1), ( 4) and ( 5); { deduce latency `j i for every output port j, using (8).

4. Compute adv(pi) and adv(p j i ) through a top-down traversal, following the topological ordering at each hierarchical level, using [START_REF] Lee | Architectures for statically scheduled data ow[END_REF], [START_REF] Leverge | The Alpha language and its use for the design of systolic arrays[END_REF] and (15).

From the output of this algorithm, one may deduce the degree of parallelism, bandwidths and bu er sizes for all processes, ports and channels. We may now show the results on the introductory example.

Input. We consider a pixel unit for all message sizes, Q 1

1 = Q 1 2 = 1920 1080, Q 2 2 = Q 1 3 = Q 2 3 = Q 1 4 = 720 480, Q 1 7 = 8, Q 1 5 = 1920, Q 2 7 = 3, Q 2 5 = 720, Q 1 8 = 9, Q 1 6 = 720 9, Q 2 8 = 4, Q 2 6 =
720 4. Some latencies, activation dates, burstinesses, and periods are already given: act(p1; 0) = 0, adv(p1) = 0, per(p4) = 40 ms (25 Hz), adv(p4) = 0, `1 1 = 0 (source process), `2 3 = 1 ms, `2 7 = 200 ns, `2 8 = 1 s, c 1;1 1;2 = c 2;1 2;3 = c 2;1 3;4 = 1 s (communication), c 2;1 5;6 = 100 ns (local bu er). Clocks must be such that fi 1=per(pi): we choose f7 = 10 MHz and f8 = 2:5 MHz, and we deduce clocks for p5 and p6 from the hierarchical scale factors: f5 = f7 (3=720) = 41:67 kHz, f6 = f8 (4=(4 720)) = 3:47 kHz.

Output. Compound process latencies: `2 5 = 24:1 s, `2 6 = 288:6 s and `2 2 = 34:752 ms; periods: per(p5) = 37:04 s, per(p6) = 333:33 s, per(p7) = 154:3 ns, per(p8) = 462:96 ns. Burstinesses are large, adv(p7) = 154:9, adv(p8) = 621:2, adv(p5) = 699:2 and adv(p6) = 102:8, but this only reports a high variability around the average period. The clock's e ect on resource usage is more signi cant: the parallelism degree is maxpll(p7) = 2 and maxpll(p8) = 3. This demonstrates how MPPN achieve a precise description of the burst rate within an average periodic scheme. Finally, we get the bandwidth and bu er results: maxbw(p 1 7 ) = 80 Mpixel=s, maxbw(p 2 7 ) = 30 Mpixel=s, maxbw(p 1 8 ) = 22:5 Mpixel=s, maxbw(p 2 8 ) = 10 Mpixel=s and maxbuf(p 2 5 p 1 6 ) = 15:12 kpixel, which expectedly corresponds to a single stripe bu er between the two lters plus 116:7% overhead, making conservative assumptions on message liveness.

Extensions, Conclusion and Future Work

Applicability of the previous model is vastly improved when considering three simple extensions. First of all, we provide two special kinds of atomic processes for multiplexing and demultiplexing streams. For example, such processes re ne the modeling of a picture-in-picture application, where a rectangle of a larger frame is replaced by a downscaled frame from another video stream. Activation of a splitter process sends one message alternatively through each of its output ports, whereas activation of a selector process receives one message alternatively from each of its input ports. We proved that a periodic alternation of process ports preserves the periodic nature of message and activations events.

Moreover, it is quite natural to relax the periodic constraint on input streams, and only require an average periodicity. This is easily achieved in adding a burstiness parameter to source processes. We proved that conservative reference dates can be deduced from the \latest" execution scheme associated with the \latest" valid schedule of source processes (a periodic one).

Eventually, we consider cyclic networks whose semantics di ers from iteration modeling in Petri nets: in stream-processing frameworks, cycles model feedback or data reuse. The latency for a message to traverse a given circuit must be less than or equal to the average period of the initiating process. In other words, a cyclic path is legal as long as it has no in uence on the global throughput; it can be statically checked through a path constraint (analogue to the scaling rule) and an additional bootstrap constraint. Dynamic noise reduction is a typical example: a noise threshold is updated to provide dynamic control over the ltering stage.

Multi-periodic process networks are an expressive model and a powerful tool for statically manipulating real-time properties, concurrency, and resource requirements of regular stream-processing applications. Primarily in uenced by synchronous extensions to Kahn process networks, they exploit the application's regularity and hierarchical structure to extend the range of possible analyses and transformations. Six major properties can be expressed: abstraction: nested processes allow for di erent levels of speci cation, both for messages (hierarchical nature of data structures) and activation events; composition: the same property set describes all processes (latency, period...); nested processes are analyzed only once and reused through MPPN libraries; synchronization: nesting of processes and hierarchical data-ow activation provides an elegant and e cient tool for modeling synchronization; jitter: event dates | whether messages or process activations | are bounded within \earliest" and \latest" deterministic functions; bursts: deterministic bursts of events can be captured explicitly within periodic event schemes, using hierarchical layers of periodic characterizations; sequencing: communication uses First-In First-Out (FIFO) channels, but implicit reordering is allowed when assembling/splitting messages. A prototype of the veri er was implemented in Java; it uses XML representations of MPPN for easy integration into application design environments.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Example: downscaler

This equation applies when messages are multiples of one another.

Acknowledgments: We received many contributions from the further members of the SANDRA team, Christine Eisenbeis, Laurent Pasquier, Valerie Rivierre-Vier, Francois Thomasset and Qin Zhao. We thank them for their support and in-depth reviews.


Patrick Carribault

Christophe Lemuet

Jean-Thomas Acquaviva

Albert Cohen

William Jalby
email: william.jalby@prism.uvsq.fr

Branch Strategies to Optimize Decision Trees for Wide-Issue Architectures

Branch predictors are associated with critical design issues for nowadays instruction greedy processors. We study two important domains where the optimization of decision trees -implemented through switch-case or nested ifthen-else constructs -makes the precise modeling of these hardware mechanisms determining for performance: compute-intensive libraries with versioning and cloning, and high-performance interpreters. Against common belief, the complexity of recent microarchitectures does not necessarily hamper the design of accurate cost models, in the special case of decision trees. We build a simple model that illustrates the reasons for which decision tree performance is predictable. Based on this model, we compare the most significant code generation strategies on the Itanium2 processor. We show that no strategy dominates in all cases, and although they used to be penalized by traditional superscalar processors, indirect branches regain a lot of interest in the context of predicated execution and delayed branches. We validate our study with an improvement from 15% to 40% over Intel ICC compiler for a Daxpy code focused on short vectors.

Introduction

Due to the increasing depth of pipelines and wider instruction fetch, branch prediction becomes more and more crucial. Consequently, large hardware structures supporting branch prediction and acceleration are ubiquitous on modern microarchitectures. To supply the pipeline with a continuous stream of instructions, branch predictors have to forecast the outcome of the branch -taken or not taken -and the target address. In control-intensive codes, multiple kinds of branches occur at a very high rate, hence wide issue processors need to issue and predict multiple branches every cycle.

On the compilation side, many optimization strategies have been proposed [START_REF] Aho | Compilers: Principles, Techniques and Tools[END_REF], to expose more instruction-level parallelism in branch-intensive codes, or to circumvent the limitations of the branch predictor and instruction fetch engine.

We study two important domains where decision trees are responsible for a significant part of the computation time: optimized libraries with versioning and cloning, and high-performance interpreters. Decision trees are implemented through switch-case or nested if-then-else constructs. Generic strategies in general-purpose compilers are often sub-optimal, because they are not well suited to the size of the decision trees (from tens up to hundreds of leaf nodes). In addition, optimizing decision trees is a problem due to the dependence on input data, but it should be emphasized that most of the complexity is brought by the large variety of code generation options.

.

Versioning and cloning.

When optimizing high-performance libraries, decision trees are often produced by the specialization of loops with small iteration counts, e.g., vector operations (for the BLAS or FFT), memory copying routines (important for I/O routines), or sorting networks (QuickSort libraries, adaptive sort [START_REF] Li | A dynamically tuned sorting library[END_REF]): a standard strategy consists in generating specialized code for 1, 2,... up to k iterations, using a switch instruction to select the right version. Procedure specialization and cloning is also common practice when performing context-sensitive interprocedural optimizations or partial evaluation. The resulting decision trees are based on interval tests in general, implemented as nested if-then-else structures. High-performance interpreters. Bytecode interpreters and processor emulators also rely on decision trees for their computation kernel [START_REF] Ertl | Optimizing indirect branch prediction accuracy in virtual machine interpreters[END_REF]. These trees are generally implemented as switch-case structures spanning over a hundred cases. Such kernels consist of a loop iterating over a decision tree, and two orthogonal optimization directions exist: one may either minimize the latency of the decision tree itself (on average, in the worst case, based on frequency or cost of each leaf, etc.), or restructure the loop such that global correlations can be better exploited. The latter scheme is explored in great detail by Ertl and Gregg in [START_REF] Ertl | Optimizing indirect branch prediction accuracy in virtual machine interpreters[END_REF]. However, this scheme performs poorly on large decision trees whose global history overflows the hardware prediction tables. Also, it may not fit the constraints (memory capacity, performance predictability) of embedded systems.

After introducing decision trees in Section 2, and our experimental platform,the Itanium 2 -, in Section 3 we provide details on branch implementation. Section 4 is focused one one-way branches, while Section 5 depicts more advanced features of multiway branches. Section 6 is dedicated to indirect branch. Experimental results and in-depth comparisons are provided in Section 7, at last Section 8 concludes and gives several openings.

Domain-Specific Optimization for Decision Trees

Decision Tree Patterns at the Source Level

Two code patterns are dominant: the nested tree of if-then-else tree conditionals and the linear switch-case selector. Nested conditionals are often restructured at intermediate compilation steps, leading to linear sequences of else if branches, see Figure 1. These linear sequences are more general than switch selectors whose case-distinction is based on integer constants only. However the switch selector deserves a specific treatment because it enables additional optimizations and is pervasive in interpreters [START_REF] Ertl | Optimizing indirect branch prediction accuracy in virtual machine interpreters[END_REF] and codes optimized through versioning or cloning.

In this generic form, the code fragments after each else if or case may contain further branches. We will only deal with one-level structures, abstracting away the nested branches (i.e., handling them separately at each nesting depth). Notice complex nests of conditionals can be often linearized by controlflow restructuring passes.

n 0 Y ∈ [0, 3] n 1 Y / ∈ [0, 3] ¡ Y ∈ [4, 8] n 2 Y / ∈ [0, 8] ¢ Y ∈ [9, 13] £ T / ∈ [0, 13]
For the sake of simplicity, expressions in else if conditions must be integer interval checks -strict or not. These checks neither have to be exclusive nor to involve the same variable throughout the one-level structure.

Representation of Decision Tree Implementations (Assembly Level)

For both else if and switch structures, we use a tree abstraction to study code generation strategies. Since we consider one-level structures, there is no a priori restriction on the shape of the tree: all leaves can be reorganized in any possible fashion -except when dependence constraints on non-exclusive conditions require the preservation of the original execution order. Notice that, in a more general setting, identical leaves may be reachable through separate branches; this is not a real problem since the following discussion could easily be extended to a directed acyclic graph.

-Internal nodes correspond to the evaluation of the condition associated with an else if or case construct. The latter pattern restrictions guarantee that switch conditions can be evaluated by a single operation (comparison to a constant) and that else if conditions require exactly two operations.

-Leaves represent the code that has to be executed after the correct branch decision is made; it may be arbitrarily complex, but we may have to make some assumptions about its execution time in several of the proposed optimization strategies. -Directed edges are labeled with the condition of the branch or its negation. Edges have an additional attribute to tell whether they correspond to taken branchessolid lines -or fall-through -dotted lines. Notice dotted-lines correspond to the predicted case in general [START_REF] Yeh | Alternative implementations of two-level adaptive branch prediction[END_REF].

A one-level else if structure and its associated decision tree are shown in Figure 2. Such a figure is named a one-way comb in the remainder of the paper. In fact, a comb refers to any list of internal nodes, where the one-way or multi-way (introduced in next section) prefix is added to characterize the number of extra edges for every node in addition of the fall-through edge (in dotted line on the figure).

Optimizing decision trees for the Itanium architecture is interesting because the platform provides the programmer or compiler with many opportunities to "drive the processor to the correct path". It is also representative of the modern mechanisms implemented in wide-issue architectures, including the IBM Power4 and Power5 (multiway branches), as well as embedded VLIW processors like the Philips TriMedia [START_REF]TriMedia Compilation System, v.2.1User and Reference Manual[END_REF] and the HP Lx alias ST-Micro 2x0 series [START_REF] Faraboschi | Lx: a technology platform for customizable VLIW embedded processing[END_REF] (predication, delay slots). This section quickly surveys the Itanium2 branch mechanisms from a programmer perspective [START_REF]Intel IA-64 Architecture Software Developer's Manual[END_REF][START_REF] Mcnairy | Itanium 2 processor microarchitecture[END_REF][START_REF] Packard | Inside the intel itanium 2 processor: an itanium processor family member for balanced performance over a wide range of applications[END_REF].

Itanium Instruction Set for Branches

First of all, traditional conditional branches are implemented as predicated branches. Typically, a compare instruction evaluates a relation and sets accordingly a pair of mutually exclusive 1-bit predicate registers. Any instruction guarded by a predicate register (called the qualifying predicate) is "nullified" if this predicate is false; thus, a predicated branch behaves exactly like a conditional branch.

Like in any pipelined processor, there is a delay between the issue cycle of the branch and the cycle when the qualifying predicate is known. If a misprediction occurs the associated penalty corresponds to the pipeline re-steer.

Branch instructions fields descriptions are given in [START_REF]Intel IA-64 Architecture Software Developer's Manual[END_REF]. One of these fields provides a guess on branch outcome (taken or not taken) either statically or dynamically. The others for example allow to determine how many instructions should be prefetched or to avoid the pollution of predictors tables with information relative to the branch. The ISA also supports indirect branch through the storage of target address within a set of dedicated branch registers.

In addition to this fairly complex branch instruction, the Itanium instruction set provides a specific instruction (brp) for controlling instruction prefetch.

The Itanium instructions are grouped by chunks of three instructions called bundles. A bundle can contain, one, two or three branch instructions. While up to two bundles can be issued every cycle, only three branches can be dispersed to branch functional units per cycle. Interestingly, branches do not have to be mutually exclusive: their relative ordering matters when resolving the correct path.

Itanium2 Branch Hardware

The branch prediction algorithm used in the Itanium2 is based on the two-level prediction scheme proposed by Yeh and Patt [START_REF] Yeh | Alternative implementations of two-level adaptive branch prediction[END_REF] combining local prediction (branch history tables) and global predictions (pattern history tables). On the Itanium2, a large amount of hardware resources have been dedicated to branch prediction mechanisms, for instance tables keeping track of several thousands of branches.

For minimizing the impact of instruction cache misses, the Itanium2 provides an instruction streaming engine which can be controlled by the compiler through branch hints. We will always assume a perfect locality in the L1 instruction cache in this paper (thanks to compact code or smart usage of brp instructions).

Overall branch penalties (assuming no instruction miss) are given below:

-0 cycle for correctly predicted branch (both outcome and target); -1 cycle for branches for which the outcome has been correctly predicted but the predicted address is incorrect (making use of dedicated address calculation units); -6 cycles for branches whose outcome has been incorrectly predicted (the pipeline has to be drained).

Indirect (or delayed) branches behave slightly differently: they take 2 cycles to execute, and there is a 7-cycle delay corresponding to the length of the pipeline, between the assignment of the branch register (b0 to b7) and the beginning of instruction fetch at this target address. During these 7 cycles, any code can be executed (provided the branch register is not overwritten) like in traditional delay slots of many in-order issue processors. Unlike VLIW processors, delay slots do not have to be filled with nops, a pipeline flush will occur if the delay is not satisfied. In addition, the assignment to a branch register triggers a prefetch stream, and one may want to wait for a few more cycles to let this stream operate.

Experimental Settings

Throughout this paper, we use ICC version 8, choosing the best result from -O2 and -O3. The target platform is a NovaScale 4020 server from Bull featuring two Itanium2 1.5GHz (Madison) processors.

We used both "regular" and "random" data input to study the effects of our optimizations on the prediction hardware. While for the sake of results stability we used a surrounding loop, predictor learning effectiveness is tested by using data input either completely random or exhibiting regular patterns.

Special care was taken to randomize branch histories without flushing the caches, given the large prediction tables and their integration in the L1 and L2 caches.

Generating a Tree of One-Way Conditional Branches

An intuitive algorithm to order a decision tree is a balanced binary tree (built by dichotomy), with a logarithmic distance between each leaf. In practice, a balanced tree has a very poor performance since most branches are locally unpredictable and lead to strong penalties.

Conversely, a comb shape has a better branch behavior due to its bias towards the fall-through path. 4 Over a few tenths of branches, some dichotomy is needed to achieve a logarithmic complexity. An optimization framework should consider this strategy as an option.

Code Motion and Hoisting

Partially redundant expression elimination (PRE) and invariant code motion can bring significant performance benefits for decision trees. The reason is not specific to the Itanium: if an expression is common to several leaves, it can be moved up to a common branch, filling some unused issue slots into the tree of conditional branches itself.

Thanks to predicated execution, hoisting can be even more aggressive on the Itanium, allowing to fill more issue slots with speculative computations coming from the leaves. ICC and Open64/ORC [START_REF]Open research compiler[END_REF] implement both PRE and this hoisting strategy.

Alternatively, code motion can be used to fill issue slots with instructions ahead of the decision tree (if the decision is not control-dependent on them). This requires less speculation than hoisting, but increases code size by duplicating code along several branches of the tree.

Node Reordering

The order in which internal nodes are visited can often be changed, permuting the else if or case leaves at the source level. There are several motivations for this.

-When optimizing for the average-case on a distribution of decisions, leaves with the highest probability of being executed can be moved closer to the root of the tree. This type of optimization is typically interesting for high-performance interpreters. -When optimizing the performance of a versioned computation kernel, it is more important to take the relative execution time of the leaves into account. Indeed, the decision tree overhead is only significant when executing short leaves, i.e., when the versioned kernel is run on small data-sets. Typical short-vector or memory copying operations are of this kind. -Code motion and hoisting can be more profitable when grouping together leaves with similar or partially redundant expressions.

Cost Evaluation of the One-Way Comb Approach: Definition

First, we define a performance metric, the Number of Mispredictions per Decision (M pD), as the number of mispredicted branches per taken decision, i.e. per traversal of the decision tree. In addition to input data, MpD depends on the decision tree structure.

Cost evaluation for else if structures. We recall that the conditions of else if constructs are assumed to be interval tests requiring two integer comparisons per cycle, and that the cost of a branch misprediction is 6 cycles (length of the back-end of the pipeline). An extra one cycle overhead is needed to pipeline predicate computations (comparisons) ahead of their qualified branches. The cycle costs for a one-way comb implementation, for the last leaf (worst latency) and for the median one are displayed in Table 1. The last leaf corresponds to the case where the targeted leaf is the last one in the comb therefore yielding to the maximum number of branch predictions for this decision tree.

Accordingly the median leaf corresponds to the case where the targeted leaf is the median one in the comb. Per cycle, three instruction slots are consumed by the branch and the two compare instructions. This leaves three slots for hoisting instructions of each leaf, or for moving code that precedes the decision tree.

Cost evaluation for switch structures. Compared to the previous evaluation, the only difference is the number of integer comparisons per node, reduced to one. The cycle costs for a one-way comb implementation, are given in Table 1. Every cycle, only two slots are consumed, leaving four available slots for hoisting.

Cost model

Last Leaf Median Leaf One-Way else if c oneway,last = 1 + L + 6M pD c oneway,median = 1 + L 2 + 6M pD One-Way switch c oneway,last = 1 + L + 6M pD c oneway,median = 1 + L 2 + 6M pD Table 1. Cost model in cycle for one-way comb implementation in the case of else if and switch structures. MpD depends on the decision tree structure, furthermore it is not a fixed constant for each cost function.

Cost Evaluation of the One-Way Comb Approach: Analytical

Considering a tree representation, we call L the number of leaves and M pD the average M pD. Of course, M pD depends on the input data; yet we show that the strongly biased predictions in the comb-shaped implementation makes it almost impossible to find a sequence of decisions leading to bad average branch prediction performance.

Indeed considering a dumb branch predictor always predicting each branch as not taken, M pD will be equal to 1 on a one-way comb because all branches will always be correctly predicted except the last one. Notice this result is independent of input data.

Consider a more representative branch predictor based on the 2-bit saturating updown counter [START_REF] Yeh | Alternative implementations of two-level adaptive branch prediction[END_REF] shown in Figure 3; computing M pD is more difficult. For a comb, whatever is its initial state, we are going to demonstrate that the average number of mispredictions per decision (i.e bad leaves improperly called due to branches predicted as taken or the good leaf not called due to the branch in not taken predicted state) is bounded by 1.

We will denote M pD(i) the number of mispredictions for the i th decision, tk(i) the number of 2-bit counters in a taken state and T K(i) the number of potential mispredictions considering that the strongly taken state allows two possible consecutive mispredictions:

5 0 ≤ M pD(i) ≤ tk(i) + 1 T K(i + 1) ≤ T K(i) -M pD(i) + 1 M pD(i) ≤ T K(i)
The maximal number of mispredictions per decision is equal to number of branch in taken state in the comb plus 1 corresponding to the called leaf potentially in not taken state. The counter associated to this called leaf is incremented so the maximal number of possible consecutive mispredictions is decremented by the previous mispredictions and incremented by 1. By induction, one may deduce the following inequality:

T K(n + 1) ≤ n - n ∑ i=1 M pD(i) ⇒ n ∑ i=1 M pD(i) ≤ n -T K(n + 1) ≤ n
For n decisions, the total number of mispredictions is less or equal to n so M pD is at most 1 whatever the input data.

Cost Evaluation of the One-Way Comb Approach: Experimental

However, the previous reasoning does not easily extend to more precise models of the predictor, due to state-space explosion. In some unfortunate cases, it is expected that false sharing and history patterns may actually degrade the prediction rate beyond the 1 misprediction per decision limit. For example, Table 2 shows experimental results on multiple decision tree sizes and on practical distributions (for a one-way comb implementation): the M pD varies between 0 and 1.1. Although the mispredict ratio can be significant -up to 26% -on small decision trees, these experiments confirm that the comb shape keeps the number of mispredictions per decision under control. This result is a good indication that it is possible to design an accurate cost function which does not suffer from input data variability. Notice the highest prediction rates (96 % to 99.9 %) come from the global predictor, which only succeeds in capturing history patterns on small decision trees. The local predictor can act too on the deeper nodes predictions. Because these nodes are called a few times compared to the total number of decisions, this predictor could recognize a period and, therefore, make correct predictions.

Generating a Tree of Multiway Conditional Branches

We now detail the additional strategies offered by multiway conditional branches. Of course, hoisting, code motion, node reordering and rebalancing can be generalized from the one-way strategies.

Dealing With Multiway Branches

Starting from a binary decision tree, using multiway branches is equivalent to merge internal nodes. Node merging can be combined with hoisting, code motion and modifications of node ordering, see Figure 4; Figure 5 shows a three-way comb.

¤ X ≤ 16 X X > 16 ¥ X ≤ 64 ¦ X > 64 X § X ≤ 16 Ẍ ∈]16; 64] © X > 64

Cost Evaluation of the Multiway Comb Approach

Using multi-way branches makes the combs shorter, the M pD is experimentally kept below 1.1, reinforcing the ability to build an accurate cost function. MpD depends on the decision tree structure, furthermore it is not a fixed constant for each cost function.

Cost evaluation for else if structures. We recall that the conditions of else if constructs are assumed to be interval tests requiring two integer comparisons per cycle.

The cycle costs for a two-way comb implementation, for the last leaf and for the median one are displayed in Table 3. Hoisting is not possible because the branches and the four comparison instructions are already using all of the available slots. For the same reason, using three-way branches will yield to the same cost function (but requires two thirds of the predictions of the two-way implementation).

Cost evaluation for switch structures. Compared to the previous evaluation, the only difference is the number of integer comparisons per node, which is reduced to one. For a two-way comb implementation, two slots are available for hoisting. In the case of a three-way comb no hoisting is possible. Costs models are detailed in Table 3.

Cost model

Last Leaf Median Leaf Two-Way else if c twoway,last = 1 + L 2 + 6M pD c twoway,median = 1 + L 4 + 6M pD Two-Way switch c twoway,last = 1 + L 2 + 6M pD c twoway,median = 1 + L 4 + 6M pD Three Way switch c threeway,last = 1 + L 3 + 6M pD c threeway,median = 1 + L 6 + 6M pD Three Way else if c threeway,last = 1 + L 3 + 6M pD c threeway,median = 1 + L 6 + 6M pD Table 3. Cost model in cycle for two-way comb implementation in the case of else if and switch structures and three-way comb in case of a switch structure. MpD value depends on the cost model.

Generating Indirect Branches

Indirect branches have not been popular in recent compilers due to the overhead and high unpredictability of such instructions on superscalar processors. Exploring alternative implementations, we show that the delayed branch and predicated execution capabilities of the Itanium make indirect branches very attractive.

The Basics on a Simple Example

On the Itanium2, an indirect branch implies computing the target address and storing it in one of the branch registers. The execution of this indirect branch is an unconditional jump to the target address. This is a convenient way to implement Fortran gotos.

For sake of simplicity, let us start with the simple one-level switch structure with four leaves in Figure 6. Assume that the code size of each leaf is less than 64B and starts at base address a. First the code for each leaf is allocated to a very specific address: namely code k is allocated to address a + k × 64B. Such alignment can be performed by .skip assembly directives to line-up instructions on a specific boundary. Now by multiplying the value of X by 64, the value of a relative displacement can be obtained, then added to the instruction pointer and stored in a branch register. A single branch using that computed address will jump directly to the correct leaf.

General One-Level Switch Structures: the Indirect Linear Method

To extend the previous method, it is sufficient to compute the maximum code size over all leaves and to round it to the next power of two. The corresponding code generation strategy is named indirect linear. The key advantage of such method is that there is a single branch instruction (always taken) instead of running down a chain of branches. The main drawback is that code layout may be fairly sparse when leaves are disproportionate or when the dispersion of selection constants is too wide.

This problem can often be worked around by using intermediate nodes consisting of a single unconditional branch. This layer of intermediate nodes will reduce the impact on memory. There is a high risk of target address misprediction for these branches when the decision tree is large, because the address prediction tables are far smaller than the outcome prediction ones. Fortunately, the address computation only takes one cycle on the Itanium2 (cf. Section 3). Figure 7 presents an example with a one-level switch and intermediate node layer. An alternative followed by ICC consists in storing target addresses in a table, indexed by the value of the switch argument. This increases the L1 cache pressure and may lose the benefit from instruction prefetching streams of the previous implementation.

Cost evaluation of the indirect linear method. We implemented a generic version of the indirect linear method in assembly (not shown for lack of space). From this implementation, and assuming a perfect instruction cache locality, the cost of the indirect linear selection of an arbitrary leaf is: c indirect,linear = 11.

As explained in Section 3, instruction prefetching is initiated by the assignment to a branch register, therefore, in practice it could be beneficial to extend the delay beyond the minimal time required to update the branch register (7 cycles). Conversely, this code can be further optimized through code motion and hoisting. In the best case, this 7 delay cycles can be concealed, but it means that a large number of instructions must be displaced and possibly speculated (7 cycles x 6 instructions per cycle = 42 instructions).

Inserting an intermediate layer of unconditional branches adds only one or two cycles: the branch and, possibly the address calculation, likely to be mispredicted: c indirect,linear+intermediate = 13.

General One-Level Else If Structures: the Indirect Compare Method

The difficulty in extending the previous technique to else if structures is the evaluation of the condition. This is not as simple as with switch structures.

First of all, comparisons corresponding to all else if conditions have to be performed. From these comparisons, the fastest way to derive a target address is to set a predicate register guarding an add instruction to compute the target address. If the comparison is true, the correct target address will be computed, otherwise no operation is performed. Eventually, after all comparisons have been made, an indirect branch always taken will jump to the correct address.

This approach is called the indirect compare strategy. In this case, we do not need to make any assumption about the size or layout of the leaves of the tree.

Cost evaluation of the indirect compare method. The cost of the compare indirect can be split in three parts: the cost of all comparisons is L/3 (2 comparisons per node, 6 per cycle); the cost of target address updates is L/6 (6 additions per cycle); the cost of the branch register assignment, the delay for the indirect branch and its intrinsic latency is 1 + 6 + 2 = 9. Therefore the cost for the Itanium2 is: c indirect,compare = L 2 + 11. This formula counts the number of slots used, but the remaining free slots might be filled through (speculative) code motion and hoisting.

Clearly, this strategy is less effective than the indirect linear method in general, because its cost is linear in the size of the decision tree. However, it may be useful for switch structures whose dispersion of selection values is too large.

Comparison of the Code Generation Strategies

We will now compare the various implementation strategies, taking the impact of hoisting into account. We will provide a worst case evaluation -called no hoisting -for which none of the free slots are filled, as well as a best case evaluation -called hoisting -assuming all empty slots are filled with useful instructions. For these cost models, we set MpD to 1 corresponding to the theoretical worst case when using the decision tree with random data.

Comparison for Else If Structures

We consider a size-L one-level else if structure. The model-based cost evaluation for the comb and indirect compare strategies are shown in Figures 8 and9, respectively for the last and median leaf, and respectively with or without hoisting. The indirect compare method is interesting -especially on small decision trees -when code motion or hoisting can be applied very aggressively (30 to 40 instructions must be moved). Indirect compare approach One-way approach with 1 misprediction Three-way approach with 1 misprediction Indirect compare approach One-way approach with 1 misprediction Three-way approach with 1 misprediction Fig. 9. Cost models comparison for else if structures, median leaf

Comparison for Switch Structures

We consider a size-L one-level switch structure. The model-based cost evaluation for the comb and indirect linear strategies are shown in Figures 10 and11, respectively for the last and median leaf, and with or without hoisting, respectively. Without hoisting, the indirect linear strategy leads asymptotically to the most effective implementation, but the merits of the different comb approaches are hard to distinguish on smaller decision trees. This complex interplay advocates for an iterative optimization approach to empirically select the best implementation, which is what the compiler does with Profile Guided Optimizations (PGO). The indirect linear approach benefits much more from code motion and hoisting, when performed aggressively the delay before the indirect branch can be completely concealed. This situation is optimistic but may occur in practice, e.g., when leaves have a many instructions in common, or when the code ahead of the decision tree can be moved into the delay slots.

First Experimental Analysis

We compare here some decision tree implementations. For such study, we considered switch 16, switch 32, switch 64 and else if 9 structures, where all leaves are reduced to a single arithmetic instruction limiting as much as possible the impact of hoisting. Look- Indirect linear approach One-way approach with 1 misprediction Three-way approach with 1 misprediction Fig. 11. Cost models comparison for switch structures, median leaf ing at generated codes, rather than a constant degree comb, ICC favored a "mixed-way" approach trading multiway branches for speculative hoisting. 4 compares the codes generated by ICC with different code variants : oneway, two-way, three-way comb and indirect linear variants. Empty cells correspond to irrelevant evaluations. These results clearly show that one-way and two-way combs are sub-optimal, the real confrontation being between ICC, three-way combs and indirect branches code variants. While ICC uses somehow complex heuristics involving combs and even indirect branches -for a switch larger than 17, it can be outperformed by simpler approaches, and in general, the efficiency of hoisting is over-estimated by ICC. In addition, the implementation of indirect branches by ICC uses an intermediate look-up table; this only adds a one-cycle delay on small kernels, but may incur higher penalties on real benchmarks (compared to the linear approach with intermediate unconditional branches). Eventually, the indirect compare approach is less effective than combs, but its code motion potential is much higher.

Application to a Real Code

To validate cost functions on real decision trees, we compared ICC's Daxpy implementations with our indirect linear implementations for short vectors. Daxpy is a BLAS1 function which computes the following scalar-vector product and sum: y = α × x + y where α is a scalar, and x and y are vectors.

For small kernels performing a Daxpy on vectors whose sizes do not exceed 16 elements, ICC generated a comb structure, mixing one-way and two-way branches. Empty slots are filled with hoisted instructions (mainly addresses computations). Over 16 elements, ICC generated an indirect branch version with hoisting where target leaf address is stored in a look-up table. But it failed use the delay cycles between the branch register update and the branch instruction for hoisting.

We implement three versions of indirect linear Daxpy with an increasing exploitation of delay slots to perform hoisting. Hoist_adr uses some of the delay slots to compute array addresses necessary for computations in each leaf. Hoist_adr_load derives from Hoist_adr, all the 16 loads on y and x are now hoisted. Hoist_adr_load_fma derives from Hoist_adr_load, some of the floating point multiply adds required to compute a vector element are now hoisted.

With such aggressive hoisting, leaves only contain floating point arithmetics and stores instructions. Note that in Hoist_adr_load and Hoist_adr_load_fma versions, special care was required to avoid potential load exception (which can be done using speculative load instructions of the Itanium2).

Indirect Linear

ICC switch 16 ICC switch 17 Cycles (vs ICC) Gain Cycles (vs ICC) Gain 5. Performance Gain (in %) of indirect versions over ICC with random vector size. For switch 16, ICC generates a comb shape decision tree while for switch 17 it relies on indirect branch.

Table 5 summarizes performance improvements of our indirect linear versions over ICC. All these indirect linear versions outperform the ICC version from 15.6% to 40%. The performance gain comes from two combined factors :

-Filling up the delay slots allows to execute up to 32 loads and to avoid a misprediction due to wrong branch target address. -Instructions in leaves were scheduled in a better way than what the compiler did.

It is important to note that in Hoist_adr, performance improvement mainly comes from the instructions rescheduling within the leaves whereas for Hoist_adr_load and Hoist_adr_load_fma versions, performance gain really comes from their hoisting capabilities.

Additionally, our indirect linear versions also surpassed ICC indirect version (switch 17) which uses look-up table because the compiler failed to exploit delay slots for hoisting to compute the target address or to hoist other kind of instruction. We obtained similar results (with a slightly narrower gap with ICC) on a Copy kernel.

Conclusion

Studying the Itanium2 architecture, we show that the complexity of the branch mechanism does not hamper the design of accurate cost models, in the special case of decision trees. We build simple models that are both accurate and relatively independent of the input data. Based on these models, we compare the most significant code generation strategies for the Itanium processor family: tree of multiway conditional branches, indirect branch with predicated comparisons, and indirect branch with linear-computation of the target address. We show that no strategy dominates in all cases. Relying on this study we develop a simple kernel outperforming from 15% to 40% a state-of-the-art compiler such as the Intel ICC compiler.

Future works include the design of finer cost models, defining more precisely the impact of hoisting and code motion. Robustness toward either instruction cache locality or statistical distribution are also hot topic of interest. On the long run we also wish to extend our work to multiple levels of nested decision trees, and to integrate our cost models and implementation strategies in an adaptive automatic optimization tool.

Fig. 2 .

 2 Fig. 2. Graphical representation of a decision tree (dotted lines correspond to fall-through)

Fig. 3 .

 3 Fig. 3. 2-bit Saturating Up-down Counter

Fig. 4 .

 4 Fig. 4. Merging Nodes in a Decision Tree. (left: not merged, right: merged)

Fig. 5 .

 5 Fig. 5. Comb of multiway branches

Fig. 6 . 3 Fig. 7 .

 637 Fig. 6. Target code structures

Fig. 8 .

 8 Fig. 8. Cost models comparison for else if structures, last leaf

Fig. 10 .

 10 Fig. 10. Cost models comparison for switch structures, last leaf

Hoist_adr 45. 1 (

 1 53.5) 15.6 % 45.1 (53.9) 16.3 % Hoist_adr_load 35.4 (53.5) 33.8 % 35.4 (53.9) 34.3 % Hoist_adr_load_fma 31.8 (53.5) 40.6 % 31.8 (53.9) 41 % Table

  else if structures and one-level switch

			if (Y>=0 && Y<4)
	if (c 0 ) code 0 ; else if (c 1 ) code 1 ; ... else if (c k-1 ) code k-1 ; code k ; else	} switch (x) { code k ; case const 0 : code 0 ; break; ... case const k-1 : code k-1 ; break; default:	// code 0 else if (Y>=4 && Y<=8) // code 1 else if (Y>8 && Y<14) // code 2 else // fall-through code
	Fig. 1. Code patterns

Table 2 .

 2 Branch predictor experimental performance on a one-way comb implementation.

	Distribution (sequence of	Correct predictions	Mispredictions per Decision
	leaf selections)	4 leaves 8 leaves 16 leaves 4 leaves 8 leaves 16 leaves
	Random	74 % 82 %	88 %	0.9	1.0	1.1
	Upwards (0, 1, . . . , n)	99 % 83 %	89 %	0.0	0.9	1.1
	Downwards (n, . . . , 1, 0)	99.9 % 88 %	89 %	0.0	0.6	1.1
	Up-and-Down (0, 1, . . . , n, . . . , 1, 0) 96 % 82 %	92 %	0.1	0.8	0.8
	Custom (3 identical then up)	82 % 85 %	90 %	0.6	0.8	0.9

Table 4 .

 4 Experimental Results: Misprediction per Decision and cycle count (random sequences) for a decision tree

			ICC One-way Two-way Three-Way Indirect compare Indirect linear
	Switch-16	MpD	0.91 1.10	1.05	0.98	n.a.	0
		Cycle count 10.5 16.5	12.3	10.3		11.2
	Switch-32	MpD	0.94 1.08	1.06	0.98	n.a.	0
		Cycle count 12.3 24.3	16.5	13.3		11.1
	Switch-64	MpD	0.94 1.08	1.05	0.98	n.a.	0
		Cycle count 12.3 40.4	24.4	18.4		11.2
	Else-if-9	MpD	0.96 1.05	1.02	0.94	0	n.a.
	(intervals)	Cycle count 12.4 13.3	12.3	11.3	16.2	n.a.

Table

By default, branches are thus predicted not taken; only those with a recent taken history occupy hardware prediction structures.

T K(i) counts predictors in a weakly taken state plus twice those in a strongly taken state.

Acknowledgments. This work is supported by research grants from CEA DAM, Bruyèresle-Châtel, Bull Les Clayes-sous-Bois and the French Ministry of Research.