Albert Cohen
email: albert.cohen@prism.uvsq.fr

PRiSM Jean-François Collard
email: françois.collard@prism.uvsq.fr

Instance-wise Reaching Definition Analysis for Recursive Programs using Context-free Transductions

Keywords: Reaching Definition Analysis, Recursive Programs, Context-free Languages, Push-down Transducers

Automatic parallelization of recursive programs is still an open problem today, lacking suitable and precise static analyses. We present a novel reaching definition framework based on context-free transductions. The technique achieves a global and precise description of the data flow and discovers important semantic properties of programs. Taking the example of a real-world non-derecursivable program, we show the need for a reaching definition analysis able to handle run-time instances of statements separately.

A running example sketches our parallelization scheme, and presents our reaching definition analysis. Future fruitful research, at the crossroad of program analysis and formal language theory, is also hinted to.

Introduction

This paper tackles the reaching definition problem for recursive programs. There are several, related but different, analyses of memory accesses. For instance, alias analyses compute pairs of conflicting memory accesses, and dependence analyses express conflicts with respect to program statements (syntactic lines). Our purpose goes beyond: For a given use (a read) of a memory cell, we are looking for the identity of the write that defined the value currently associated to the memory cell. Reaching definition analysis (RDA) is thus a special case of data-flow analysis [START_REF] Aho | Compilers: Principles, Techniques and Tools[END_REF].

Let us immediately stress a very important point. Classical RDAs tell, for a given read statement, whether a write statement may be the reaching definition. In other words, they tell whether there is a definition-free path connecting a definition site to a use site. Our RDA, however, identifies which run-time instance of some write statement defined the value used by a given run-time instance. We stress this difference in calling our RDA: "Instance-wise reaching definition analysis" (IRDA) [START_REF] Collard | A comparative study of reaching definitions analyses[END_REF]. To describe the relation between write instances and read instances, we first name all these instances unambiguously, then find a mapping from names of reads to names of writes.

Array data flow analyses [START_REF] Feautrier | Dataflow analysis of scalar and array references[END_REF][START_REF] Maydan | Array dataflow analysis and its use in array privatization[END_REF] are IRDAs for loop nests with arrays. Applications are numerous, especially in automatic parallelization of imperative programs: Array expansion, conversion to single assignment form, etc. However, most reaching definition analyses focuses on loop nests, and recursive programs have received little interest. The contributions of this article are: Formalizing instance-wise reaching definitions in recursive programs. A suitable labeling scheme for runtime instances of statements is introduced. Showing the use of context-free transductions to adequately describe reaching definitions in recursive programs, at the run-time instance level. Advocating for the development of complex transformations techniques for recursive programs, and for interesting applications of formal language theory to program analysis.

Of course, the idea of using formal languages for program analysis has been around for years. However, to the best of our knowledge, this paper is the first to use formal languages in an instance-wise reaching definition analysis.

The paper is organized as follows: Section 2 discusses related work. Section 3 presents our running example and show the use of reaching definitions in parallelization frameworks. Then, still studying the motivating example, we describe in Section 4 the IRDA we want to design. Section 5 formalizes IRDA in a transduction-based model. To use this transduction in a compiler we also need to construct the corresponding push-down transducer. This is done in Section 6. The method is applied in Section 7 to build the transducer for the motivating example. Section 8 comments on our analysis and describes future work.

Related Work

Many types of static analyses on data have been proposed. Points-to analyses compute a store model using abstract locations [START_REF] Chase | Analysis of pointers and structures[END_REF]. Jensen et al. [START_REF] Jensen | Automatic verification of pointer porgrams using monadic second-order logic[END_REF] also developed an access analysis where a first-order logic serves as a store model (or, alternatively, a second-order one for sets of cells). Adapting the respective store models-tailored for pointer accesses-to array accesses with affine subscripts seems tedious. Alias analyses compute pairs of memory access paths that are, or may be, aliased [START_REF] Deutsch | Interprocedural may-alias analysis for pointers: beyond k-limiting[END_REF][START_REF] Landi | Interprocedural modification side effect analysis with pointer aliasing[END_REF]. Data dependences describe conflicts between memory accesses in computing pairs of dependent statements (or run-time instances). Some of these analyses do handle arrays. They are yet basically different from our reaching definition analysis since they do not give the identity of the last defining write.

Most RDA abstract the effects of a program by sets of flow equations; These equations are then solved in general by iterative schemes [START_REF] Aho | Compilers: Principles, Techniques and Tools[END_REF][START_REF] Cousot | Program Flow analysis: theory and applications, chapter Semantic foundations of programs analysis[END_REF]. They often require that a fixpoint can be reached in a finite (and hopefully small) number of iterations. These methods proved to be robust in the case of intricate control flow. Some analyses explicitly handle recursive programs [START_REF] Alt | Generation of efficient interprocedural analyzers with PAG[END_REF]. However, they do not identify the run-time instance of a definition site, i.e. the last write in a given memory cell.

Analyses closer to our work were proposed in [START_REF] Collard | Fuzzy array dataflow analysis[END_REF][START_REF] Feautrier | Dataflow analysis of scalar and array references[END_REF][START_REF] Maydan | Array dataflow analysis and its use in array privatization[END_REF][START_REF] Pugh | Eliminating false data dependences using the omega test[END_REF], because they give the identity of definition instances and because they precisely handle array accesses thanks to symbolic simplifiers [START_REF] Feautrier | Dataflow analysis of scalar and array references[END_REF][START_REF] Pugh | A practical algorithm for exact array dependence analysis[END_REF]. However, none of these analyses was developed for recursive programs. Our framework subsumes these analyses because loop nests can be considered as nested recursive procedures. Notice that the opposite does not hold: Recursive programs cannot in general be written as a nest of loops (without explicit stack handling). but the method applies to any imperative language.) This is an example of recursive program for which no simple non-recursive version exists: Classical derecursivation algorithms will not work since recursive calls and loop iterations are mixed 1 . This program computes all possible RAM configurations for a computer, given the size of the memory chips and the number of slots available. This program originally appeared in Java on Sun's Web-site. 1 Writing the outer loop recursively would make appear two mutually recursive procedures. To expose as much parallelism as possible, our intent is to expand the data structures (here, arrays) so as to get rid of as many output, anti-and true dependences as possible. In the extreme expansion case, we would like to convert the program into single assignment form. This program transformation is very similar to static single assignment form (SSA) [START_REF] Cytron | Efficiently computing static single assignment form and the control dependence graph[END_REF] or array expansion [START_REF] Feautrier | Dataflow analysis of scalar and array references[END_REF]. In single assignment form, all output dependences, anti-dependences, and true dependences due to memory reuse, are removed.

The Motivation: Automatic Parallelization

Let us look at the execution of FillSlots. Figure 1 displays the call tree, with some kind of "call string" associated to each node. Each call string is actually a special kind of word over the statement labels, to be formally defined later. As and AIEpAs are instances of statement s, AaIEpAITBr and AaIEpAITBbr are instances of statement r.

Now, let us consider a word w pinpointing to one runtime instance of statement r, and let us assume that an IRDA gives a mapping , from w (the read of A[j] for the appropriate loop-counter j) to the run-time instance (w) of statement s that defined the value. Then, we could expand array A into a tree T whose nodes are labeled by call strings. Since this paper focuses on IRDA, we neither discuss construction of T nor implementation of the transformed program. Therefore, we simply use the abstract syntax T[w] for the node associated with call string w. The resulting program in single assignment form appears in Figure 2. Now every instance of statement s writes in a distinct memory location, all these instances can be executed in parallel. Two instances of the inner loop-i.e. the block introduced by B-can also be executed in parallel. Loop B itself may also be parallelized, but we need more information on statement r. We can sketch an abstract parallelization scheme for FillSlots:

First, execute all instances of s-i.e. all writes-in parallel and wait for execution completion;

Then, run all B loops in parallel, executing each one

An Intuitive Flavor of the Analysis

We have shown that IRDA is a critical point in automatic parallelization of recursive programs like FillSlots. Let us now focus on the IRDA itself.

A Few De nitions

An Alphabet of Labels Program statements have been labeled for easier reference. There are two operative statements: s writes into array A and r performs some read access in A. Statement I is a conditional whose branches are T (then) and E (else), and statement p a recursive call to procedure FillSlots. Loop statements are decomposed into two sub-statements which are given distinct labels: The first one denotes the loop entry-e.g. A or B-and the second one denotes the loop iteration-e.g. a or b.

We get an alphabet = fA; a; s; I; T; E; B; b; r;pg.

In English, words are ordered by the lexicographical order generated by the alphabet order a C b C c C . Similarly, in any program one can define a partial "textual" order C over statements. Statements in the same basic block are sorted in apparition order, and statements appearing in different blocs are mutually incomparable. In our example: r C b in the block introduced by the inner loop, s C I C a in the outer loop. And that's all: T and E are branches of a conditional, B and p appear in different blocks : : :

Using C we see that instance w 0 executes before instance w iff the first differing label in w 0 and w are ordered by C:

I.e. if 0 (resp. 0 ) is the first label in w (resp. w 0 ) after the greatest common prefix of w and w 0 , one must have 0 C .

Call Strings and Control Words

In the previous section, we introduced an intuitive labeling scheme for nodes in call trees by so-called "call strings". However, to be consistent with formal language theory, we will talk about "words" instead of "strings". Second, call strings have a somewhat different meaning in the literature: They usually capture the matching of call-and return-sites, and therefore build context-free languages. In this paper, control words capture the flow of control: Each control word corresponds to a possible run-time instance of a program statement. (Whether this instance is actually executed or not depends on conditionals and loop bounds, which have not been taken into account.) They build a rational (a.k.a. regular) control word language: In the case of FillSlots, we show Section 5.1 and Figure 4 that instances of s build language A(IEpA+a) s and instances of r build language A(IEpA+a) ITBb r.

Execution Order is Lexicographical Order on Control Words As a result, the sequential execution order over instances is exactly the lexicographical order, over control words, generated by C. We write w 0 w the fact that instance w 0 executes before w. In the following, trees of control words are sorted from left to right, according to .

Reaching De nitions for FillSlots

Let us compute "by hand" the instance-wise reaching definitions for FillSlots. We are concerned in read accesses to A[j] performed by statement r. First, notice that statement r can only be executed when n = 0, i.e. when array A has been fully initialized by the successive calls to FillSlots. Moreover, the j loop-counter indexing array A in statement r ranges between 0 and N. As a result, values read by r have always been defined.

We want to compute, given the control word w of an instance of statement r, the control word w 0 of the reaching definition, i.e. the control word of the last instance of s which executes before w and writes into the array element read by w. This reaching definition is such that the value of n at instance w 0 is the same as the value of j at instance w. Since j is exactly the number of b in w and n is exactly N minus the number of p in w 0 , we have jwj b = N jw 0 j p where jwj is the occurrence number of in word w. Suppose N = 1, and let us study instance AaIEpAITBbr as shown by a circle in Figure 3.a. AaIEpAITBbr reads A [START_REF] Aho | Indexed grammars -an extension to context free grammars[END_REF]. Aas-the black square-also writes in A [START_REF] Aho | Indexed grammars -an extension to context free grammars[END_REF]. No instance executing between Aas and AaIEpAITBbr can assign A [START_REF] Aho | Indexed grammars -an extension to context free grammars[END_REF] since its control word cannot hold any occurrence of p. Moreover, we are sure that Aas is actually executed; Therefore other instances writing in the same array element such as definition As-the gray square in Figure 3.a-cannot reach the read, since they are always "killed" by Aas. Aas is thus the reaching definition of AaIEpAITBbr. Similarly, the definition reaching AaIEpAITBr in Figure 3.b is AaIEpAsthe black square-since all other write instances-like the gray square AIEpAs-are killed by AaIEpAs.

The reaching definition computation for these two examples may actually be generalized. It can be proven-and we will do this automatically in Section 7-that the definition reaching some instance w of r is an instance of s of the form us where u is the greatest prefix of w s.t. jwj b = N juj p .

Let us call (w) the definition instance reaching w. We have been able here to compute the unique reaching definition for each instance of r. But in general, maps instances to sets of possible reaching definitions, since extricate conditional expressions may cause approximative results.

Formalization of the Analysis

We start with some vocabulary in formal language theory, see [START_REF] Berstel | Transductions and Context-Free Languages[END_REF] for details. A transduction is a relation over formal languages. It is also seen as a function from one language to subsets of an other. A transducer is the "engine" to "code" this relation. A rational (resp. push-down) transducer is a generalized finite (resp. push-down) automaton with output. It implements a rational (resp. push-down) transduction. Notice that a rational transduction is also context-free. See Figure 5 for simple transducer examples. In the following, we use the shorter "transducer " for "transducer implementing transduction ".

Program Model

We handle programs with recursive calls, any loop (with unrestricted bounds), and any conditional statement (with unrestricted predicates); gotos are removed by classical processing. We only consider scalars and one-dimensional arrays. We call induction variables the integer arguments of a procedure that are initialized, incremented or decremented by a constant value at each recursive call. Loop counters are also considered as induction variables since loops can be rewritten in terms of recursive calls. Moreover, we require that all array subscripts be affine functions of induction variables and symbolic constants. For expository reasons, we make the following simplifications: We consider a single array A, any number of read accesses, and only one assignment s writing into array A.

For instance, procedure FillSlots has two induction variables appearing in array subscripts: n and j; j is incremented at each inner loop iteration, and n is decremented at each recursive call. (Notice that these conditions subsume "traditional" affine assumptions on loop nests.)

The alphabet of statement labels (see Section 4.1) is denoted with . For a word w in and a letter in , jwj denotes the number of occurrences of in w.

Control words are formally defined as words recognized by the control automaton of the program. It is a finite automaton whose states are blocks and statements in the program. An edge from a state q 1 to a state q 2 express that statement (or block) q 2 occurs in block q 1 ; It is labeled by the label of q 2 . Operative statements yield termination states (see Figure 4). L denotes the control word language.

Reaching De nitions as Transductions

The applicability of our transduction model relies on the two following properties: Without considering loop bounds and predicates, L is a rational (a.k.a. regular) language. This result is a straightforward application of L being the language recognized by the control automaton. Now consider array subscripts. Due to our syntactical restrictions, a subscripting function f is affine w.r.t. the occurrence numbers of labels in control words and w.r.t. symbolic constants. I.e., if = f 1 ; : : : ; n g and if N 1 ; : : : ; N m are symbolic constants, then there exist n + m numerical constants a 1 : : :a n+m s.t.: f(w) = a 1 jwj 1 + : : : + a n jwj n + a n+1 N 1 + : : : + a n+m N m : [START_REF] Aho | Indexed grammars -an extension to context free grammars[END_REF] The formal proof of this result is not given here, for lack of space (A restricted case is studied in [START_REF] Cohen | Analyse de flot de données pour programmes récursifs à l'aide de langages algébriques[END_REF]).

Let g be the subscript function to array A in the right-hand side (the read) and f the function subscripting array A in the left-hand side. Let us consider the read in A by an instance w of s. A read w is dependent on instance w 0 of s if the three conditions below hold.

Conflicting accesses: w and w 0 hit the same memory cell: g(w) = f(w 0 ):

(2)

Ordering: The write w 0 has to execute before the read w, denoted by w 0 w. Actually, is the lexicographical order on control words, defined by: w 0 w () w = u v ^w0 = u 0 v 0 ^ 0 C :

Execution: Obviously, write w 0 has to execute. This is denoted by e(w 0 ). Then, the reaching definition of a read w is the last write instance, with respect to order , satisfying these three conditions: max fw 0 : g(w) = f(w 0 ) ^w0 w ^e(w 0 )g.

Clearly, this maximum is unique in the course of program execution. However, since we make no assumption on recursion guards, we cannot prove nor disprove, a priori, that an instance executes. So, we have to approximate this maximum as a set (w) of possible reaching definitions. This approximation may be more or less precise, depending on the knowledge on e(w 0 ) and on how well this knowledge fits the context-free transduction framework. This (compiletime) knowledge may come from structural properties of the program, analysis of conditional expressions, etc. At first, loop bounds and conditional predicates (such as recursion guards) are not taken into account. We thus restrict ourselves to the transduction built from ( 2) and ( 3):

(w) = fw 0 2 s : f(w 0 ) = g(w) ^w0 wg [START_REF] Berstel | Transductions and Context-Free Languages[END_REF] Transduction captures the true dependences of the program. We will prove in the next section that is a contextfree transduction. But our aim is still to perform a reaching definition analysis; And true dependences are no good approximation, in general. Our IRDA scheme applies various rewriting rules to , using compile-time knowledge on the existence condition e(w 0 ):

If we can prove that some statement instance does not execute, and if adding this information keeps the transduction context-free, some true dependences can be removed. The remaining instances are described by predicate e MAY (w 0 ) (instances that may execute).

On the opposite, suppose we can prove that some statement instance w 00 does execute, and that adding this information keeps the transduction context-free. Then, writes executing before w 00 are "killed": They cannot reach an instance w such that w 00 2 (w). Instances that are effectively executed are described by predicate e MUST (w 0 ) (instances that must execute).

The number and complexity of these rules depends on the program and on the precision required. This issue is studied in more detail in the next sections.

At last, the result of our IRDA is a new transduction, call it , which is an over-approximation of : (w) (w). Formally, an instance w 0 is in (w) iff it is in dependence with w, It executes (according to the static knowledge we have), and it is not killed by an other dependence:

(w) = fw 0 : w 0 2 (w) ^eMAY (w 0 ) ^( 6 9w 00 2 (w) : w 0 w 00 ^eMUST (w 00 ))g (5) Let us now give a constructive proof that is context-free.

Building the Context-Free Transducer

We first present a construction of the dependence transducer , then show how to refine its output, in order to get a precise description of reaching definition instances.

The Dependence Transducer

Implementing the lexicographical order with a transducer (3) is easy, it is a well known example of rational transducer.

Suppose we have just read a prefix u of w: Let w = u v 2 L, u 2 , 2 and v 2 . To satisfy the lexicographical order, we have to output any word w 0 = u 0 v 0 s.t. 0 C . See example in Figure 5.a.

Satisfying the conflicting access condition ( 2) is done using a counter. The counter, therefore, checks whether g(w) f(w 0 ) is equal to zero. To comply with the standard definition of push-down transducers, the counter is implemented as a stack in a natural way [START_REF] Berstel | Transductions and Context-Free Languages[END_REF][START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF]. Such a push-down transducer allows the following counter arithmetic: Initialization to a constant, noted CNT := cst; Adding a constant, noted CNT += cst or CNT -= cst;

Comparing with zero, noted CNT = 0 or CNT 6 = 0. Intersecting the lexicographical order and conflict equation transducers is easy: The first one is essentially "statebased" and the second one is "stack-based"2 . It yields a three-state transducer checking the counter in three stages. Therefore the result is a push-down transducer.

The last stage consists in restricting input words to instances of read statements, and output words to instances of s. We need the following notations: Let INPUT (resp.

OUTPUT) be the transducer build from the finite automaton recognizing instances of read statements (resp. statement s) in copying its input to its output-i.e., when an edge in the finite automaton is labeled by , the corresponding edge in INPUT is labeled by = . Composing the input of our transducer with INPUT and the output by OUTPUT, we get the dependence transducer . We can apply Elgot and Mezei's theorem 3 [START_REF] Berstel | Transductions and Context-Free Languages[END_REF] since we compose two rational transducers-INPUT and OUTPUT-with a context-free one. It proves that is a context-free transducer. Notice that Elgot and Mezei's theorem is constructive: Building is done automatically from INPUT, OUTPUT, , g and f.

The Reaching De nitions Transducer

Here comes a few examples of rewriting rules that can be applied to refine the set of possible reaching definition instances. Any statement instance us where u is a strict prefix of some control word w is called an ancestor of w. E.g.,

AaIEpAs is an ancestor of AaIEpAIBr (see Figure 3.b).

The LAD property (Left of Ancestor in Dependence).

Let w be some read instance and w 0 in dependence with w. Suppose an ancestor u 0 s of w 0 is also in dependence and executes before w 0 . If w 0 executes, u 0 executes too, and then u 0 s does. Therefore u 0 s kills every instance executing before it, including w 0 . (w 0 may execute or not, but when it does, it is necessarily killed.) See [START_REF] Cohen | Analyse de flot de données pour programmes récursifs à l'aide de langages algébriques[END_REF] for details. LAD () (9 2 : C s):

Rule LAD then applies: If some word u 0 s is in dependence with w, no words prefixed by u 0 with C s can be reaching definitions of w. Formally, transitions "= v (v 2 ) with C s are transformed into "= v : CNT 6 = 0.

The MSF property (Monotonic Subscript Function).

A non-decreasing function f is s.t. 8uv 2 L; u; v 2 : f(uv) f(u); Non-increasing functions are defined similarly. A function is monotonic when it is either non-decreasing or non-increasing.

Suppose the write access function f to array A (in s) is monotonic, s C and v= v is a transition that does not modify the counter. Let w be some read instance and us an ancestor of w, in dependence with w. We know that u vs is executed-being an ancestor of w. And u vs is in dependence with w, since transition v= v does not modify the counter; Thus u vs kills us.

MSF () f is monotonic: For all 2 and v 2 s.t. s C and v= v does not modify the counter: Rule MSF consists in following transition v= v as much as possible before outputting s (to get the biggest ancestor). Formally, transition =s is removed, if not the only transition that outputs s. Application of this rule is shown at Section 7. 3 More precisely, a generalization to context-free transductions.

The VPA property (Values are Produced by Ancestors). This property comes from the common observation about recursive programs that "values are produced by ancestors." Indeed, a lot of sort, tree, or graph-based algorithms perform in depth explorations where values are produced by ancestors. This behavior is also strongly assessed by scope rules of local variables. Formally, VPA () (w 0 = (w) ) (9u; v : w = uv ^w0 = us)):

Rule VPA then consists in removing all transitions producing non-ancestors. Formally, all transitions = 0 s.t. 0 C and 0 6 = s are removed.

The OKA property (One Killing Ancestor).

Let w be a read instance. If it can be proven that at least one ancestor us of w is in dependence, it kills all writes executing before (since it does executes when w does).

OKA () ( (w) 6 = ; ) (9u; v : w = uv ^us 2 (w))):

Property checking Satisfaction of property LAD is easily obtained from C. Checking property MSF is done by examinating transitions of the form v= v in and coefficients in f (their sign must be the same). Property OKA can be discovered using invariant properties on induction variables (see Section 7). Checking for property VPA is difficult (automatically or not), but we have the following result:

When both OKA and MSF hold, VPA also holds. Suppose 0 is the transducer after application of the MSF rule, and-by application of OKA-suppose us 2 0 (w) is an ancestor of w. Any word u vs with s C and v 2 is s.t. f(u vs) 6 = f(us), by definition of us. Therefore, no instances in dependence execute after us: Property VPA is satisfied. This result allows to apply rule VPA from properties MSF and OKA.

To summary this section: Our IRDA checks for properties LAD, MSF and OKA-possibly using external classic analyses; Then applies rules LAD, MSF and VPA accordingly.

More properties can probably be useful that can be obtained by more involved analyses [START_REF] Cousot | Program Flow analysis: theory and applications, chapter Semantic foundations of programs analysis[END_REF]. The problem is to find a relevant and efficient rewritting rule for each one.

Algorithm for IRDA

In this section, we integrate the precedent techniques in a general IRDA algorithm.

Input: , f, g, L (from the control automaton), and C.

Step 1: Build the lexicographical order transducer .

Step 2: Build the transducer checking g(w) = f(w 0 ).

Step 3: Intersect the two, yielding a three-state transducer.

Step 4: Compute transducers INPUT and OUTPUT from L.

Step 5: Compose the input by INPUT and the output by OUTPUT. Here is transducer .

Step 6: Check properties LAD, MSF and OKA using external static analyses. Asking the user for help may be useful for VPA or other properties not described here.

Step 7: Apply rewritting rules accordingly. The result is the reaching definition transducer. Output: Return dependence and reaching definition transducers and .

Notice and are both useful to compilers. Section 8 discusses decidability results on describing dependences and reaching definitions with push-down transducers.

Back to procedure FillSlots

Let us show how to compute the transducer describing the data flow of FillSlots. Here we have g(w) = jwj b and f(w 0 ) = N jw 0 j p : The conflict equation is g(w) f(w 0 ) = jwj b + jw 0 j p N:

Intersecting the lexicographical order and the conflict equation, then applying composition with INPUT and OUTPUT, we get the dependence transducer in Figure 5.c. Rule LAD does not apply since no label precedes s for C.

Rule MSF applies since f(w 0 ) is a non-increasing function (as the length of w 0 increases). Transition a=a does not modify the counter, therefore edge a=s is removed; But transition IEpA=IEpA increments the counter thus I=s is kept. We have seen in Section 4.2 that 0 j N and n = 0 holds for all instances of statement r. These properties can be easily discovered using classical techniques [START_REF] Aho | Compilers: Principles, Techniques and Tools[END_REF][START_REF] Cousot | Program Flow analysis: theory and applications, chapter Semantic foundations of programs analysis[END_REF]. As a consequence, if w is an instance of r there exists a prefix u of w s.t. jusj p = N jw 0 j b . Property OKA is satisfied.

We have seen that combined properties OKA and MSF forces reaching definitions to be ancestors: Rule VPA thus applies.

It consists in stripping out a=I (and subsequent unreachable states and edges). The result is shown in Figure 6. This is our result for . It computes in fact a unique reaching definition for every instance: We achieved-in an automated way-the best precision possible. We also gave a formal description of the result of Section 4.2.

Discussion on This Approach

The present framework can be extended to programs with several arrays and assignments: The weakest solution to handle several assignments to the same array consists in taking the union of context-free languages, which is contextfree. We also believe that this transduction-based framework can be extended to support IRDA over more general data structures, such as trees [START_REF] Feautrier | A parallelization framework for recursive tree programs[END_REF]. Formal languages seem very natural for compile-time analysis of recursive programs. Moreover, using context-free transducers has the following benefits:

It can be decided whether a word is a reaching definition of another one. It is decidable whether a language of reaching definitions is empty or not, and therefore, whether an instance reads an uninitialized value. This makes our IRDA useful to precise program checking. Computing the cardinality of a set of reaching definitions is also possible. This is useful to detect when IRDA gives exact results (sets are singletons). Context-free languages are closed under intersection with rational languages. Any decidable property on the reaching definitions of a given read is thus decidable for a rational set of read instances. We have seen on example FillSlots that instancewise reaching definitions can be of great help in parallelizing recursive programs. Indeed, benefits of IRDA have already been studied in the case of Fortran loops [START_REF] Feautrier | Dataflow analysis of scalar and array references[END_REF][START_REF] Maydan | Array dataflow analysis and its use in array privatization[END_REF], but we advocate for an extension to recursive programs. First, IRDA allows to remove dependences due to memory reuse-via single assignment form transformation; Second, since it works on a per-instance basis, both fine-grain and coarse-grain parallelism can be discovered. Several problems obviously remain. Two of them are studied below.

1. The exact language of possible reaching definitions is not context-free: Obviously, many properties on the existence condition e(w 0 ) cannot be taken into account in our framework. More precise IRDAs require more powerful classes of languages. Indexed grammars [START_REF] Aho | Indexed grammars -an extension to context free grammars[END_REF] are an extension of context-free grammars useful to our context. This research is left for future work. 2. Multidimensional arrays could be handled by intersecting reaching definitions languages. Unfortunately, neither context-free languages nor indexed grammars are closed under intersection. Scattered context grammars [START_REF] Greibach | Scattered context grammars[END_REF] are an extension of context-free languages closed under intersection; Studying the applicability of this class is left for future work too.

Conclusion

This article presents a novel application of formal languages to the automatic discovery of some semantic properties of programs: Reaching definitions. When programs are recursive and no property is known at compile-time on recursion guards, only a conservative approximation can be hoped for. In our case, we approximate the set of possible reaching definitions of a given read by a context-free language. The relation between reads and their respective languages of possible reaching definitions is context-free, by construction. The result of the analysis is thus a pushdown transducer mapping control words of read instances to control words of write instances. Decidability properties on context-free languages and transductions allow several applications of our framework, especially in automatic parallelization of recursive programs. These applications include array expansion, parallelism extraction, and aggressive optimization and verification techniques.

  Let us consider a motivating example, as shown inFigure 1, accessing an array A. (Programs are written in C

Figure 1 .

 1 Figure 1. Procedure FillSlots and call tree

voidTFigure 2 .

 2 Figure 2. Transforming FillSlots.

Figure 3

 3 Figure 3.a. Studying AaIEpAITBbr.

Figure 3 .

 3 Figure 3. Source examples for N = 1.

Figure 4 .

 4 Figure 4. Control automaton for FillSlots.

Figure 5 .

 5 Figure 5.b is an example of conflict equation transducer.Intersecting the lexicographical order and conflict equation transducers is easy: The first one is essentially "statebased" and the second one is "stack-based" 2 . It yields a three-state transducer checking the counter in three stages.

1 .

 1 Read and write a common prefix: Transitions are of the form v= v, 2 , v 2 . 2. Read the input suffix: Transitions are of the form v=".

3 .

 3 Write an output suffix that zeroes the counter: Transitions are of the form "= v.

Figure 5 .

 5 Figure 5.a: Transducer for lexicographical order.Figure 5.b: Transducer for conflict equation.

Figure 5 .

 5 Figure 5.a: Transducer for lexicographical order.Figure 5.b: Transducer for conflict equation.

  CNT += 1 r=EpA : CNT += 1 "=a "=IEpA : CNT += 1 a="; IEpA=" b=" : CNT += 1 "=s : CNT = 0

Figure 5 Figure 5 .

 55 Figure 5.c: Transducer .I=s a=s

Figure 6 .

 6 Figure 6. Reaching definitions for FillSlots after application of VPA and MSF.

The intersection of a rational transduction and an context-free one is in general not context-free.

Acknowledgments

The authors are supported by the French Ministère de l'Enseignement Supérieur et de la Recherche (MESR), the Centre National de la Recherche Scientifique (CNRS), INRIA project AAA, and the German-French ProCoPe program.

We would like to thank Yvan Djelic, Paul Feautrier, and Martin Griebl for their help and fruitful comments about this topic.


Albert Cohen

Vincent Lefebvre

Storage Mapping Optimization for Parallel Programs

Data dependences are known to hamper e cient parallelization of programs. Memory expansion is a general method to remove dependences in assigning distinct memory locations to dependent writes. Parallelization via memory expansion requires both moderation in the expansion degree and e ciency at run-time. We present a general storage mapping optimization framework for imperative programs, applicable to most loop nest parallelization techniques.

Introduction

Data dependences are known to hamper automatic parallelization of imperative programs and their e cient compilation on modern processors or supercomputers. A general method to reduce the number of memory-based dependences is to disambiguate memory accesses in assigning distinct memory locations to non-con icting writes, i.e. to expand data structures. In parallel processing, expanding a datum also allows to place one copy of the datum on each processor, enhancing parallelism. This technique is known as array privatization 5, [START_REF] Maydan | Array data ow analysis and its use in array privatization[END_REF][START_REF] Tu | Automatic array privatization[END_REF] and is extremely important to parallelizing and vectorizing compilers.

In the extreme case, each memory location is written at most once, and the program is said to be in single-assignment form (total memory expansion). The high memory cost is a major drawback of this method. Moreover, when the control ow cannot be predicted at compile-time, some run-time computation is needed to preserve the original data ow: Similarly to the static singleassignment framework 6], -functions may be needed to \merge" possible data de nitions due to several incoming control paths.

Therefore parallelization via memory expansion requires both moderation in the expansion degree, and e ciency in the run-time computation of -functions. A technique limited to a ne loop-nests was proposed in 11] to optimize memory management. The systolic community have a similar technique implemented in ALPHA compilers 14]. A di erent approach 15] is limited to perfect uniform loop-nests, and introduces universal storage mappings. We present a general storage mapping optimization framework for expansion of imperative programs, applicable to most parallelization techniques, for any nest of loops with unrestricted conditionals and array subscripts.

Section 2 studies a motivating example showing what we want to achieve, before pointing out contributions in more detail. Section 3 formally de nes storage mapping optimization, then we present our algorithm in Section 4. Experimental results are studied in Section 5, before we conclude.

We rst study the kernel in Figure 1.1, which appears in several convolution codes 1 ; Parts denoted by have no side-e ect on variable x. For any statement in a loop nest, the iteration vector is built from surrounding loop counters 2 . Each loop iteration spawns instances of statements included in the loop body: Instances of S are denoted by hS; i; ji, for 1 i n and 1 j 1.

Instance-wise Reaching De nition Analysis

We believe that an e cient parallelization framework must rely on a precise knowledge of the ow of data, and advocate for Instance-wise Reaching De nition Analysis (IRDA): It computes which instance of which write statement de ned the value used by a given instance of a statement. This write is the (reaching) de nition of the read access.

Any IRDA is suitable to our purpose, but Fuzzy Array Data-ow Analysis (FADA) 1] is prefered since it handles any loop nest and achieves today's best precision. Value-based Dependence Analysis 17] is also a good IRDA. In the following, is alternatively seen as a function and as a relation. The results for references x in right-hand side of R and S are nested conditionals: (hS; i; ji; x) = if j = 1 then fTg else fhS; i; j 1ig, (hR; ii; x) = fhS; i; ji : 1 jg.

Conversion to Single Assignment Form

Here, memory-based dependences hampers direct parallelization via scheduling or tiling. We need to expand scalar x and remove as many output-, anti-and true-dependences as possible. In the extreme expansion case, we would like to convert the program into single-assignment (SA) form 8], where all dependences due to memory reuse are removed.

Reaching de nition analysis is at the core of SA algorithms, since it records the location of values in expanded data-structures. However, when the ow of data is unknown at compile-time, -functions are introduced for run-time restoration of values 4,6]. Figure 1.2 shows our program converted to SA form, with the outer loop marked parallel (m is the maximum number of iterations that can take the inner loop). A -function is necessary, but can be computed at low cost: It represents the last iteration of the inner loop.

Reducing Memory Usage

SA programs su er from high memory requirements: S now assigns a huge n m array. Optimizing memory usage is thus a critical point when applying memory expansion techniques to parallelization.

Figure 1.3 shows the parallel program after partial expansion. Since T executes before the inner loop in the parallel version, S and T may assign the same array. Moreover a one-dimensional array is su cient since the inner loop is not parallel. As a side-e ect, no -function is needed any more. Storage requirement is n, to be compared with n m+n in the SA version, and with 1 in the original program (with no legal parallel reordering).

We have built an optimized schedule-independent or universal storage mapping, in the sense of 15]. On many programs, a more memory-economical technique consists in computing a legal storage mapping according to a given parallel execution order, instead of nding a universal storage compatible with any legal execution order. This is done in 11] for a ne loop nests only.

Our contributions are the following: Formalize the correctness of a storage mapping, according to a given parallel execution order, for any nest of loops with unrestricted conditional expressions and array subscripts; Show that universal storage mappings de ned in 15] correspond to correct storage mappings according to the data-ow execution order; Present an algorithm for storage mapping optimization, applicable to any nest of loops and all parallelization techniques based on polyhedral dependence graphs.

Formalization of the Correctness

Let us start with some vocabulary. A run-time statement instance is called an operation. The sequential execution order of the program de nes a total order over operations, call it . Each statement can involve several array or scalar references, at most one of these being in left-hand side. A pair (o; r) of an operation and a reference in the statement is called an access. The set of all accesses is denoted by A, built of R, the set of all reads|i.e. accesses performing some read in memory|and W, the set of all writes.

Imperative programs are seen as pairs ( ; f e ), where is the sequential order over all operations and f e maps every access to the memory location it either reads or writes. Function f e is the storage mapping of the program (subscript e stands for \exact"). Parallelization means construction of a parallel program ( 0 ; f 0 e ), where 0 is a sub-order of preserving the sequential program semantics. Transforming f e into the new mapping f 0 e is called memory expansion. The basis of our parallelization scheme is instance-wise reaching de nition analysis: Each read access in a memory location is mapped to the last write access in the same memory location. To stress the point that we deal with operations (i.e. run-time instances of statements), we talk about sources instead of de nitions. In our sense, reaching de nition analysis computes a subset of the program dependences (associated with Bernstein's conditions). Practically, the source relation computed by IRDA is a pessimistic (a.k.a. conservative) approximation: A given access may have several \possible sources".

As a compromise between expressivity and computability, and because our prefered IRDA is FADA 1], we choose a ne relations as an abstraction. using tools like Omega 13] and PIP 8].

Correctness of the Parallelization

What is a correct parallel execution order for a program in SA form? Any execution order 0 (over operations) must preserve the ow of data (the source of an access in the original program executes before this access in the parallel program): 8e; 8(o 1 ; r 1 ); (o 2 ; r 2 ) 2 A : (o 1 ; r 1 ) e (o 2 ; r 2 ) ) o 1 0 o 2 (where o 1 ; o 2 are operations and r 1 ; r 2 are references in a statement). Now we want a static description and approximate e for every execution.

Theorem 1 (Correctness of execution orders). If the following condition holds, then the parallel order is correct|i.e. preserve the program semantics. 8(o 1 ; r 1 ); (o 2 ; r 2 ) 2 A : (o 1 ; r 1 ) (o 2 ; r 2 ) =) o 1 0 o 2 :

(1) Given a parallel execution order 0 , we have to characterize correct expansions allowing parallel execution to preserve the program semantics. We need to handle \absence of con ict" equations of the form f e (v) 6 = f e (w), which are undecidable since subscript function f e may be very complicated. Therefore, we suppose that pessimistic approximation 6 l is made available by a previous stage of program analysis (probably as a side-e ect of IRDA): f e (v) 6 = f e (w) ) v 6 l w: Theorem 2 (Correctness of storage mappings). If the following condition holds, then the expansion is correct|i.e. allows parallel execution to preserve the program semantics. 8v; w 2 W : 9u 2 R : v u ^w 6 0 v ^u 6 0 w ^(u w _ w v _ v 6 l w)

=) f 0 e (v) 6 = f 0 e (w): (2)
The proof is given in 3]. This result requires the source v of a read u and an other write w to assign di erent memory locations, when: In the parallel program: w executes between v and u; And in the original one: Either w does not execute between v and u or w assigns a di erent memory location from v (v 6 l w).

Building parallel program ( 0 ; f 0 e ) resumes to solving (1) and (2) in sequence.

Computing Parallel Execution Orders

We rely on classical algorithms to compute parallel order 0 from the dependence graph associated with . Scheduling algorithms 7,9] compute a function from operations to integers (or vectors of integers in the case of multidimensional schedules 9]). Building 0 from is straightforward: u 0 v , (u) < (v).

With additional hypotheses on the original program (such as being a perfect loop nest), tiling 2,10] algorithms improve data locality and reduces communications. Given a tiling function T from operations to tile names, and a tile schedule from tile names to integers: u 0 v , (u) < (v) _ (T (u) = T (v) ^u v).

In both cases|and for any polyhedral representation|computing 0 yields an a ne relation, compatible with the expansion correctness criterion.

Eventually, the data-ow order de ned by relation is supposed (from Theorem 1) to be a sub-order of every other parallel execution order. Plugging it into (2) describes schedule-independent storage mappings, compatible with any parallel execution. This generalizes the technique by Strout et al. 15] to any nest of loops. Schedule-independent storage mappings have the same \portability" as SA with a much more economical memory usage. Of course, tuning expansion to a given parallel execution order generally yields more economical mappings.

An Algorithm for Storage Mapping Optimization

Finding the minimal amount of memory to store the values produced by the program is a graph coloring problem where vertices are operations and edges represent interferences between operations: There is an edge between v and w i they can't share the same memory location, i.e. when the left-hand side of (2) holds. Since classic coloring algorithms only apply to nite graphs, Feautrier and Lefebvre designed a new algorithm 11], which we extend to general loop-nests.

Partial Expansion Algorithm

Input is the sequential program, the result of an IRDA, and a parallel execution order (not used for simple SA form conversion); It leaves unchanged its control structures but thoroughly reconstitutes its data. Let us de ne Stmt(hS; xi) = S and Index(hS; xi) = x.

1. For each statement S whose iteration vector is x: Build an expansion vector E S which gives the shape of a new data structure D S , see Section 4.2 for details. Then, the left-hand side (lhs) of S becomes D S x mod E S ]. 2. Considering as a function from accesses to sets of operations (like in Section 2), it can be expressed as a nested conditionals. For each statement S and iteration vector x, replace each read reference r in the right-hand side (rhs) with Convert(r), where:

If (hS; xi;r) = fug, then Convert(r) = D Stmt(u) Index(u) mod E Stmt(u) ].
If (hS; xi;r) = ;, then Convert(r) = r (the initial reference expression).

If (hS; xi; r) is not a singleton, then Convert(r) = ( (hS; xi;r)); There is a general method to compute at run-time, but we prefer pragmatic techniques, such as the one presented in 3] or another algorithm proposed in 4]. If (hS; xi;r) = if p then r1 else r2, then Convert(r) = if p then Convert(r1) else Convert(r2).

3. Apply partial renaming to coalesce data structures, using any classical graph coloring heuristic, see 11]. This algorithm outputs an expanded program whose data are adapted to the partial execution order 0 . We are assured that with these new data, the original program semantic will be preserved in the parallel version.

Building an Expansion Vector

For each statement S, the expansion vector must ensure that expansion is systematically done when the lhs of (2) holds, and introduce memory reuse between instances of S when it does not hold.

The dimension of E S is equal to the number of loops surrounding S, written N S . Each element E S p + 1] is the expansion degree of S at depth p (the depth of the loop considered), with p 2 0; N S 1] and gives the size of the dimension (p + 1) of D S . For a given access v, the set of operations which may not write in the same location as v can be deduced from the expansion correctness criterion (2), call it W S p (v). It holds all operations w such that: w is an instance of S: Stmt(w) = S; Index(v) 1::p] = Index(w) 1::p] and Index(v) p + 1] < Index(w) p + 1]; And lhs of ( 2) is satis ed for v and w, or w and v. Let w S p (v) be the lexicographic maximum of W S p (v). The following de nition of E S has been proven to forbid any output-dependence between instances of S satisfying the lhs of (2) 3,11]. E S p] = max(Index(w S p ) p + 1] Index(v) p + 1] + 1)

Computing this for each dimension of E S ensures that D S has a su cient size for the expansion to preserve the sequential program semantics.

Summary of the Expansion Process

Since we consider unrestricted loop nests, some approximations 3 are performed to stick with a ne relations (automatically processed by PIP or Omega).

The more general application of our technique starts with IRDA, then apply a parallelization algorithm using as dependence graph (thus avoiding constraints due to spurious memory-based dependences), describe the result as a partial order 0 , and eventually apply the partial expansion algorithm. This technique 3 Source function is a pessimistic approximation, as well as 6 l. yields the best results, but involves an external parallelization technique, such as scheduling or tiling. It is well suited to parallelizing compilers.

If one looks for a schedule-independent storage mapping, the second technique sets the partial order 0 according to , the data-ow execution order 4 . This is useful whenever no parallel execution scheme is enforced: The \portability" of SA form is preserved, at a much lower cost in memory usage.

Experimental Results

Partial expansion has been implemented for Cray-Fortran a ne loop nests 11]. Semi-automatic storage mapping optimization has also been performed on general loop-nests, using FADA, Omega, and PIP.

The result for the motivating example is that the storage mapping computed from a scheduled or tiled version is the same as the schedule-independent one (computed from the data-ow execution order). The resulting program is the same as the hand-crafted one in Figure 1.

A few experiments have been made on an SGI Origin 2000, using the mp library (but not PCA, the built-in automatic parallelizer...). As one would expect, results for the convolution program are excellent even for small values of n. The interested reader may nd more results on the following web page: http://www.prism.uvsq.fr/~acohen/smo/smo.html.

Conclusion and Perspectives

Expanding data structures is a classical optimization to cut memory-based dependences. The rst problem is to ensure that all reads refer to the correct memory location, in the generated code. When control and data ow cannot be known at compile-time, run-time computations have to be done to nd the identity of the correct memory location. The second problem is that converting programs to single-assignment form is too costly, in terms of memory usage.

We have tackled both problems here, proposing a general method for partial memory expansion based on instance-wise reaching de nition information, a robust run-time data-ow restoration scheme, and a versatile storage mapping optimization algorithm. Our techniques are either novel or generalize previous work to unrestricted nests of loops.

Future work is twofold. First, improve optimization of the generated code and study|both theoretically and experimentally|the e ect of -functions on parallel code performance. Second, study how comprehensive parallelization techniques can be plugged into this framework: Reducing memory usage is a good thing, but choosing the right parallel execution order is another one.

3 .

 3 Partial expansion.

Fig. 1 .

 1 Fig. 1. Convolution example.

E.g. Horn and Schunck's 3D Gaussian smoothing by separable convolution.

When dealing with while loops, we introduce arti cial integer counters.

But 0 must be described as an e ective order. One must compute the transitive closure of the symmetric relation: ( 1 ) + .

Acknowledgments: We would like to thank Jean-Fran cois Collard, Paul Feautrier and Denis Barthou for their help and support. Access to the SGI Origin 2000 was provided by the Universit e Louis Pasteur, Strasbourg, thanks to G.-R. Perrin.


Albert Cohen
email: albert.cohen@prism.uvsq.fr

Parallelization via Constrained Storage Mapping Optimization

A key problem for parallelizing compilers is to nd the good tradeo between memory expansion and parallelism. This paper is a new step towards solving this problem. A framework for parallel execution order and storage mapping computation is designed, allowing time and space optimization. Constrained expansion|a theoretical model for expansion strategies|is shown to be very useful in this context.

Introduction

Data dependences are known to hamper automatic parallelization of imperative programs and their e cient compilation on modern processors or supercomputers. A general method to reduce the number of memory-based dependences is to disambiguate memory accesses in assigning distinct memory locations to non-con icting writes, i.e. to expand data structures.

In the extreme case, each memory location is written at most once, and the program is said to be in single-assignment form. Unfortunately, when the control ow cannot be predicted at compile-time, some run-time computation is needed to preserve the original data ow: -functions may be needed to \merge" data de nitions due to several incoming control paths 5].

Parallelization via memory expansion thus requires both moderation in the expansion degree, and e ciency in the run-time computation of -functions. In our framework, moderation is achieved from two complementary directions:

Adding constraints to limit memory expansion, like static expansion avoiding -functions 1], privatization [START_REF] Tu | Automatic array privatization[END_REF][START_REF] Maydan | Array data ow analysis and its use in array privatization[END_REF], or array static single assignment 9]. All these techniques allow partial removal of memory-based dependences, but may extract less parallelism than conversion to single assignment form. Applying storage mapping optimization techniques 4]. Some of these are either schedule-independent 13] or schedule-dependent 10]|yielding better optimizations|whether they require former computation of a parallel execution order (scheduling, tiling, etc.) or not. Trying to get the best of both directions is the goal of this paper. Our contribution is to show the bene t of combining them into a uni ed framework for memory expansion. We present an intra-procedural algorithm applying to any imperative program and most loop nest parallelization techniques.

The paper is organized as follows: Section 2 studies a motivating example showing what we want to achieve. Section 3 introduces the general concepts, before we formally de ne correct constrained storage mappings in Section 4. Then, Section 5 presents our expansion algorithm. We draw conclusions in Section 7.

Motivating Example

We study the pseudo-code in Figure 1.a. Such nested loops with conditionals appear in many kernels, but most parallelization techniques fail to generate e cient code for these programs. Each iteration of a loop spawns instances of statements included in the loop body. In the example program, instances of T are denoted by hT; i; ji, instances of S by hS; i; j; ki, and instances of R by hR; ii, for 1 i; j m and 1 k n. (\P(i; j)" is a boolean function of i and j.) We believe that an e cient parallelization framework must rely on a precise description of the ow of data. Here comes Instance-wise Reaching De nition Analysis (IRDA): It computes for each value read in memory, the run-time instance which produced the value. This write is the (reaching) de nition of the read access|the use. Any IRDA is suitable to our purpose, but Fuzzy Array Data-ow Analysis (FADA) 2] is prefered for its high precision on unrestricted loop nests. Value-based Dependence Analysis 15] is also suitable.

On this example, assume n is non-negative and predicate \P(i; j)" evaluates to true at least one time for each iteration of the outer loop. FADA tells us that the reaching de nition of the read access hS; i; j; ki to x is hT; i; ji when k = 1 and hS; i; j; k 1i when k > 1. We only get an approximate result for de nitions that may reach hR; ii: Those are fhS; i; j; ni : 1 j mg. Indeed, the value of x may only come from S (since n > 0) for the same i (since T executes at least one time for each iteration of the outer loop), and for k = n.

Conversion to Single Assignment Form

Obviously, memory-based dependences on x hampers direct parallelization via scheduling or tiling. Our intent is to expand scalar x so as to get rid of as many dependences as possible. The extreme expansion case is single-assignment (SA) form, where all dependences due to memory reuse are removed.

Reaching de nition analysis is at the core of SA algorithms in tracking values in expanded data-structures. Figure 1.b shows our program converted to SA form, using the result of IRDA. The unique -function implements a run-time choice between values produced by hS; i; 1; ni; : : : ; hS; i; m; ni.

Parallelization

SA removed enough dependences to make the two outer loops parallel, see Figure 2.a. Function is computed at run-time using array Last j . It holds the last value of j when x was assigned. This information allows value recovery in R.

But this parallel program is unusable on any architecture. The main reason is memory usage: Variable x has been replaced by a huge three-dimensional array, plus two smaller arrays. This code is approximately ve times slower than the original program on a single processor (when arrays hold in memory).

Storage Mapping Optimization

This shows the need for a memory usage optimization technique. Storage mapping optimization (SMO) 4,13,10] consists in reducing memory usage as much as possible as soon as a parallel execution order has been crafted, see Figure 2.b. A single two-dimensional array can be used, while keeping the two outer loops parallel. Run-time computation of function with array Last seems very cheap at rst glance; But execution of Last j = max (Last j , j) hides synchronizations behind the \maximum" computation! As usual, it results a very bad scaling: Good accelerations are obtained for a very small number of processors, then speed-up drops dramatically because of synchronizations.

Figure 3 gives execution time and speed-up for the parallel program, compared to the original (not expanded) one. We used the mp library on an SGI Origin 2000, with m = 64 and n = 2048, and simple expressions for \ " parts.

Tuning Between Expansion and Parallelism

This bad result shows the need for a ner parallelization scheme. The question is to nd a good tradeo between expansion overhead and parallelism extraction. If we target widely-used parallel computers, the processor number is likely to be less than 100, but SA form extracted two parallel loops involving m 2 processors! The intuition is that we uselessly spilled memory and run-time overhead.

One would prefer a pragmatic expansion scheme, such as maximal static expansion (MSE) 1], or privatization [START_REF] Tu | Automatic array privatization[END_REF][START_REF] Maydan | Array data ow analysis and its use in array privatization[END_REF]. Choosing static expansion has the bene t that no -function is necessary any more: x can be safely expanded along outermost and innermost loops, but expansion along j is forbidden|it requires a -function thus violates the static constraint. Now, only the outer loop is parallel, see Figure 4. We get much better scaling, see Figure 4. However, on a single processor the program still runs two times slower than the original one. This is probably due to bad locality of the innermost loop.

Storage Mapping Optimization Again

Maximal static expansion expanded x along the innermost loop, but it was of no interest regarding parallelism extraction. Combined MSE and storage mapping optimization solves the problem, see Figure 5. Scaling is excellent and parallelization overhead is very low: The parallel program runs 31:5 times faster than the original one on 32 processors (for m = 64 and n = 2048).

This example shows the use of combining constrained expansions|such as privatization and static expansion|with storage mapping optimization techniques, to improve parallelization of general loop nests (with unrestricted conditionals and array subscripts). In the following, we present an algorithm useful for automatic parallelization of imperative programs. Although this algorithm cannot itself choose the \best" parallelization, it aims to simultaneous optimization of expansion and parallelization constraints.

Problem Statement

Let us start with some vocabulary. Our transformation techniques should be able to distinguish between the distinct run-time instances of a statement. A run-time statement instance is called an operation.

The sequential execution order of the program de nes a total order over operations, call it . Each statement can involve several array or scalar references, at most one of these being in left-hand side: A pair (o; r) of a statement instance (an operation) and a reference in the statement is called an access. The set of all accesses is denoted by A. It can be decomposed into: The set of all reads R|i.e. accesses performing some read in memory|and the set of all writes W.

Parallelization Scheme

Imperative programs are seen as pairs ( ; f e ), where is the sequential order over all operations and f e maps every access to the memory location it either reads or writes. Subscript e models a given execution of the program: f e may depend on input data or initial values of variables. Function f e is the storage mapping of the program. In this model, parallelization means construction of a program ( 0 ; f 0 e ) where 0 is a sub-order of . Obviously, 0 and f 0 e must satisfy several properties in order to preserve the sequential program semantics. Building a new storage mapping f 0 e from f e is called memory expansion. To stress the point that we deal with operations (i.e. run-time instances of statements), we will talk about sources instead of de nitions. In our sense, reaching de nition analysis computes a subset of the program dependences. The source relation computed by IRDA is a pessimistic (a.k.a. conservative) approximation the actual source function e that depends on the execution.

Similarly, we have to handle undecidable \con ict equations" of the form f e (v) = f e (w) and f e (v) 6 = f e (w), since f e depends on the execution. Therefore, we suppose that pessimistic (a.k.a. conservative) approximations l and 6 l are made available by a previous stage of program analysis (e.g. as a side-e ect of IRDA). Moreover, we need a mathematical representation to handle functions and relations over accesses and operations. Since we target parallelizing compilers, this representation must support basic algebraic operations, allow to decide whether a set is empty, whether some access can be the source of another, etc. For all these reasons|and the fact our preferred reaching de nition analysis is FADA 2]|we choose a ne relations as an abstraction. Tools like Omega 12] are well suited to handle such relations.

Introducing Constrained Expansion

The motivating example shows the bene ts of putting an a priori limit to expansion. Static expansion 1] is a good example of constrained expansion. The idea is to avoid dynamic restoration of the data ow by the mean of a relation between writes that possibly de ne the same read: vRw , 9u 2 R : v u^w u.

Whenever two sources of the same read assign the same memory location in the original program, they must still do so in the expanded one. Since \writing in the same memory location" is an equivalence relation, we actually use R , the transitive closure of R. The resulting constraint for f 0 e to be static is 8e; 8v; w 2 W : vR w ^fe (v) = f e (w) ) f 0 e (v) = f 0 e (w). What about other expansion schemes ? The goal of constrained expansion is to design pragmatic techniques that does not expand variables when the incurred overhead is \two strong". To generalize static expansion, we suppose that some equivalence relation on writes is available from previous compilation stages. A storage mapping constrained by is any mapping f 0 e s.t. 8e; 8v; w 2 W : v w ^fe (v) = f e (w) =) f 0 e (v) = f 0 e (w):

It is di cult to decide whether to forbid expansion of some variable or not, and building of constraint is the purpose of Section 6. We leave for Section 5 all discussion about picking the right parallel order. Indeed, the two problems are part of the same bi-criteria optimization problem: Tuning expansion and parallelism for performance. We do not present here a solution to this complex problem. The algorithm described in the next sections should be seen as an integrated tool for parallelization, as soon as the \strategy" has been chosen|what expansion constraints, what kind of schedule, tiling, etc. Most of these strategies have already shown useful and practical for some programs, the main contribution is their integration in an automatic optimization process. The summary of our optimization framework is presented in Figure 6.

What is a Correct Parallel Execution Order?

Memory expansion|partially|removes dependences due to memory reuse. Suppose exp approximates the dependence relation of ( ; f 0 e ), the expanded program with sequential execution order. ( exp matches when the program is converted to SA form.) Any parallel order 0 (over operations) compatible with dependence relation exp (over accesses) preserve the original semantics: 8(o 1 ; r 1 ); (o 2 ; r 2 ) 2 A : (o 1 ; r 1 ) exp (o 2 ; r 2 ) =) o 1 0 o 2 :

(2) Computation of relation exp from expansion f 0 e is done in Section 4.3.

What is a Correct Expansion?

Given parallel order 0 , we are looking for correct expansions allowing parallel execution to preserve original semantics. Our task is to formalize memory reuse constraints enforced by 0 . We need a new (symmetric) relation ./: v ./ w def () 9u 2 R : v u ^w 6 0 v ^u 6 0 w ^(u w _ w v _ v 6 l w) _ 9u 2 R : w u ^v 6 0 w ^u 6 0 v ^(u v _ v w _ w 6 l v) : (3)

We proved in 4] that the expansion is correct if the following condition holds. 8e; 8v; w 2 W : v ./ w =) f 0 e (v) 6 = f 0 e (w):

(4) This result requires the source v of a read u and an other write w to assign di erent memory locations, when: In the parallel program, w executes between v and u, And in the original one, either w does not execute between v and u or w assigns a di erent memory location from v (v 6 l w).

Computing Parallel Execution Orders and Expansions

We formalized the parallelization correctness with an expansion constraint [START_REF] Barthou | Maximal static expansion[END_REF] and two correctness criteria ( 2) and ( 4). Let us show how solving these equations simultaneously yields a suitable parallel program ( 0 ; f 0 e ).

Maximal constrained expansion: Following the lines of 1], we are interested in removing as many dependences as possible, without violating the expansion constraint. We can prove|like Lemma 1 in 1]|that a constrained expansion is maximal|i.e. assigns the largest number of memory locations while verifying

(1)|i 8e; 8v; w 2 W : v w ^fe (v) = f e (w) , f 0 e (v) = f 0 e (w). Still following 1], we assume that f 0 e = (f e ; ), where is constant on equivalence classes of . Indeed, if f e (v) = f e (w), condition f 0 e (v) = f 0 e (w) becomes equivalent to (v) = (w). Using \con ict equation" approximation l our maximal constrained expansion criterion becomes: 8v; w 2 W; v l w : v w () (v) = (w)

(5) Computing resumes to enumerating equivalence classes of : For any access v in a class of l (operations that \may" hit the same memory location), (v) can be de ned via a representative of the equivalence class of v for relation . Computing the lexicographical minimum is a simple way to nd representatives.

Parallel execution order: It is time to recompute dependences exp of program ( ; f 0 e ): An access w depends on v if they hit the same memory location, v executes before w, and at least one is a write. Then, applying equation (5): 8v; w 2 A : v exp w def () v w _ (v l w ^v w ^v w) _ (v l fu : u wg ^v fu : u wg ^v w) _ (fu : u vg l w ^fu : u vg w ^v w) (

We rely on classical algorithms to compute 0 from exp 6{8,3].

Reducing memory usage: Knowing (f 0 e ; 0 ), we could stop and say we have successfully parallelized our program; But nothing ensures that f 0 e is an \economical" storage mapping (remember the motivating example). We must build a new expansion from 0 that minimizes memory usage while satisfying (4).

It is exactly what the partial expansion algorithm presented in 4] has been crafted for. Following the lines of 10], it generates a new array D S for every assignment statement S, then replaces the left-hand side by D S x mod E S ], where x denotes an iteration vector. Vector E S is computed from (4) using a new graphcoloring algorithm, see 4,10]. When every array D S has been built, renaming is performed (to merge arrays) using a greedy graph-coloring algorithm.

Instead of generating code, one can redesign the output of this algorithm to compute an equivalence relation over writes: The \color" relation. When v w, it is correct to have f 0 e (v) = f 0 e (w). Let Stmt(u) (resp. Index(u)) be the statement (resp. iteration vector) associated with access u. Let NewArray(S) be the name of the new array assigned by S (after partial expansion):

8v; w 2 W : v w def () NewArray(Stmt(v)) = NewArray(Stmt(w)) ^Index(v) mod E Stmt(v) = Index(w) mod E Stmt(w) :
Relation satis es expansion correctness equation ( 4), but annoyingly, nothing ensures that expansion constraint (1) is still satis ed. We have to compute a new equivalence relation from and .

Figure 7 shows that is not su cient: Consider three writes u, v and w s.t. f e (u) = f e (v) = f e (w), u v and v w. ( 5) enforces f 0 e (u) = f 0 e (v) since u v. Moreover, to spare memory, we should apply coloration and set f 0 e (v) = f 0 e (w). Then, no expansion is done and parallel order 0 may be violated.

w if ( ) then x = rw = x u x = v if ( ) then x = ruv = x
Original program, (rw) = fwg and

(ruv) = fu; vg.

u x = w if ( ) then x = rw = x v if ( ) then x = ruv = x
Wrong expansion when moving u to the top: rw may read the value produced by u.

u y = w if ( ) then x = rw = x v if ( ) then y = ruv = y
Correct when assigning y in u and v and moving u to the top.

Fig. 7. Strange interplay of expansion constraint and correctness coloration

To avoid this pitfall, coloration relation must be used with care. One may safely set f 0 e (u) = f 0 e (v) when for all u 0 u, v 0 v: u 0 v 0 (i.e. u 0 and v 0 share the same color). Consider the following relation over writes: 8v; w 2 W : v w () v w _ (8v 0 ; w 0 : v 0 v ^w0 w =) v 0 w 0 ):

The good thing is that relation is an equivalence! The proof is simple since both and are equivalence relations. Moreover, choosing f 0 e (v) = f 0 e (w) when v w and f 0 e (v) 6 = f 0 e (w) when its not the case ensures that f 0 e satis es both the expansion constraint and the expansion correctness criterion. The result is: Theorem 1. Storage mapping f 0 e of the form (f e ; ) such that 8v; w 2 W; v l w : v w () (v) = (w) is the minimal storage mapping, according to relation , allowing the parallel execution order 0 to preserve the program semantics. (Meaning that it uses the fewer memory locations possible, being the only information about permitting two accesses to assign the same memory location or not.) Theorem 1 gives us an automatic method to minimize memory usage, according to a given parallel order and a prede ned expansion constraint.

Code Generation Algorithm

We start with a summary of the optimization problem. Section 4 yields the system:

8 > > > > < > > > > :
Constraints on f 0 e = (f e ; ):

v l w ^v w ) (v) = (w) v l w ^v ./ w ) (v) 6 = (w)
Constraints on 0 :

(o 1 ; r 1 ) exp (o 2 ; r 2 ) ) o Expansion scheme (static expansion, etc.)

The algorithm to solve this system enhances the one proposed in 4] to handle constrained expansion. We use the notations Stmt(hS; xi) = S and Index(hS; xi) = x, Array(S) is the name of the original data structure assigned by statement S, and Subscript(u) is the subscript (program text) associated with access u. Inputs are the sequential program, the result of an IRDA, the expansion constraint, and pessimistic approximations l and 6 l.

1. Compute parallel order 0 from , l, , and , by rst computing dependence relation exp then applying your prefered parallelization algorithm (scheduling, tiling, etc.).

Building Expansion Constraints

Our goal here is not to choose the right constraint suitable to expand a given program; But it does not mean leaving the user compute relation ! As shown in Section 3.2, enforcing the expansion to be static corresponds to setting = R . The constraint is thus built from IRDA results 1].

Another example is privatization, seen as expansion along some surrounding loops, without renaming. Consider two accesses u and v writing into the same memory location. After privatization, u and v assign the same location if their iteration vectors coincide on the components associated with privatized loops: u v () Index(u) privatized loops] = Index(v) privatized loops];

where Index(u) privatized loops] holds counters of privatized loops for u.

Building the constraint for array SSA is even simpler. Instances of the same statement assigning the same memory location must still do so in the expanded program (only variable renaming is performed): u v () Stmt(u) = Stmt(v);

These three practical examples give the insight that building from the formal de nition of an expansion strategy is not di cult. New expansion strategies should be designed and expressed as constraints|statement-by-statement, user-de ned, knowledge-based, and especially architecture dependent (number of processors, memory hierarchy, communication model) constraints.

Conclusion and Perspectives

Expanding data structures is a classical transformation to cut memory-based dependences. The questions are (1) \What is the good expansion for my favorite program and architecture?", and (2) \What is the good parallel loop reordering algorithm?". We believe that better performance could be achieved if both questions are handled simultaneously.

This paper introduces expansion constraints to tune between expansion overhead (time and space) and parallelism extraction. When the parallel order has been built, storage optimization is performed to reduce memory usage. We designed a kind of integrated tool for parallelization, taking the expansion strategy and parallel order computation algorithm as input from an other part of the compiler, or even the user. Our techniques are either novel or generalize previous work to unrestricted nests of loops.

We advocate for the use of constrained expansion in parallelizing compilers, since its integration with other parallelization techniques (scheduling, tiling, storage mapping optimization, etc.) has been shown possible by this work. The goal is now to design pragmatic constraints and to propose a real bi-criteria optimization algorithm for expansion overhead and parallelism extraction.

Fig. 1 .Fig. 1 .Fig. 1 .

 111 Fig.1.a. Original program

Fig. 2 .Fig. 2 .

 22 Fig.2.a. Parallel SA

Fig. 3 .

 3 Fig. 3. Performance results for storage mapping optimization 2.5 Tuning Between Expansion and Parallelism

real x 1 .Fig. 4 .Fig. 5 .

 145 Fig. 4. Maximal static expansion real x 1..m] PARALLEL for i=1 to m do for j=1 to m doif (P (i; j)) then Tx i] = 0 for k=1 to n do

Fig. 6 .

 6 Fig. 6. What we want to achieve 4 Formalization of the Correctness We de ne correct parallelizations in Sections 4.1 and 4.2 then state our optimization problem in Section 4.3.

  Any array declaration A ...] becomes A ..., max u2W ^Array(u)=A (u)]. Eventually, several methods compute -functions at run-time 4,5, 9].

	7.
	2. Compute relation ./ from , 6 l, and 0 . 3. Compute function from ./ applying the graph-coloring algorithm in 4]. 4. Compute function by enumerating equivalence classes of , in every class of l. See 1] for details. 5. For each statement S whose iteration vector is x: Replace the original left-hand side with Array(S) Subscript(hS; xi), (hS; xi)]. 6. Each reference r in right-hand side becomes Array(Stmt(u)) Subscript(u), (u)] when (hS; xi; r) = fug, and with a conditional expression thereof when (hS; xi; r) is a non-singleton set, see 4].

Acknowledgments: Thanks to Denis Barthou, Jean-Fran cois Collard, Vincent Lefebvre, Paul Feautrier, and Laurent Vibert, for their help and support. Access to the SGI Origin 2000 was provided by the Universit e Louis Pasteur, Strasbourg.


32 Blvd Victor, 75015, Paris, France {ami.aly; adriana.tapus}@ensta-paristech.fr Abstract-In human-robot interaction, gender and internal state detection play an important role in making the robot reacting in an appropriate manner. This research focuses on the important features to extract from a voice signal in order to construct successful gender and internal state detection systems, and shows the benefits of combining both systems together on the total average recognition score. Moreover, it consists a foundation on an ongoing approach to estimate the human internal state online via unsupervised clustering algorithms.

I. INTRODUCTION

The automatic recognition of emotions has recently received much attention in order to build more intuitive human robot interfaces. Relevant acoustic features from voice signals such as pitch and energy are needed ao as to reliably recognize emotions and human internal states. These features are, also, highly dependant on the gender; therefore, this study demonstrates how the extracted information of the gender could affect the accuracy of the internal state detection.

II. DATABASE

The database used in this research is the German emotional speech database (http://database.syntheticspeech.de/) [START_REF] Burkhardt | A Database of German Emotional Speech[END_REF] with more than 520 voice samples for 5 men and 5 women, discussing 7 emotional states.

III. GENDER DETECTION

The characteristic vector is based on the statistical measuring (e.g. mean, variance, max, min, range) of each of the extracted features from the voice signal (pitch, energy, formants, and mel-frequency cepstral coefficients) [START_REF] Talkin | A Robust Algorithm for Pitch Tracking[END_REF] [START_REF] Traunmuller | A Method of Measuring Formant Frequencies at High Fundamental Frequencies in the Fifth European Conference on Speech[END_REF].

The results of the gender detection recognition (using Support Vector Machine (SVM)) showed that female voices (299 voice sample) are recognized with 93.3% and the percentage of recognition of male voices (224 voice sample) is of 87.5%, making an average score of 90.4% (see Figure 1).

IV. INTERNAL STATE DETECTION

The characteristic vector detecting the internal states is similar to the characteristic vector used in gender detection, but it depends only on pitch and energy [START_REF] Breazeal | Recognition of Affective Communicative Intent in Robot-Directed Speech in the Autonomous Robots[END_REF].

The investigated internal states are: anger, boredom, disgust, fear, joy, neutral, and sadness, which are varying in the recognition score as indicated in Figure 2. The seven tested internal states achieved an average recognition score of 86.4% using the SVM algorithm. The main idea is to first classify the tested voice sample as being male or female and then to detect the internal state of the person as illustrated in Figure 3.

The total average recognition score is about 93%; however, this recognition system assumed an ideal gender detection (i.e. 100%), so as to reach a total average score of about 93% for the combined model (which is the average value between the ideal gender's recognition score 100% and the internal states' recognition score which is 86.4%). In the real case, the Fig. 3: Combined Gender and Internal States Recognition Architecture accuracy of the gender detection system had achieved only 90.4% and tests' results revealed a total average recognition score for the combined model of about 88% (which is approximately the average value between the "real" gender's recognition score 90.4% and the internal states' recognition score which is 86.4%).

VI. ONLINE DETECTION OF INTERNAL STATES

The need for an effective online internal state detection system comes from the fast growing human robot interaction applications which require the robot to be able to deal appropriately with different and varying internal states. Traditional approaches for detecting internal states are based (as illustrated in the first part of this research) on constructing a database knowing in advance the number of clusters. However, it is not possible to construct a good and big database including samples for all human internal states. Thus, we can expect that the robot will not be able to deal with different interactional situations in an appropriate way due to an error in classifying a new or unknown internal state.

Hence, this research tries to integrate an online clustering algorithm to the previously constructed gender and internal state combined detection system. The German speech database with its 7 emotional states will be the origin of the new system, and then new emotional states will be added to the database. The online clustering algorithm (e.g., subtractive clustering) will deal with the new updated database and will try to update the number of clusters to adapt the new coming elements to the database [START_REF] Pal | Mountain and Subtractive clustering method: improvements and generalizations in the international journal of intelligent systems[END_REF]. Subtractive clustering uses data points as candidates for the cluster's centers, and then it calculates for each of the proposed cluster's centers a density function which indicates how the proposed cluster's center is affected by the surrounding points in the dataset according to the following equation (where r is the neighborhood radius, X i represents the cluster point under test, and X j represents data points):

D i = n j=1 exp( -( x i -x j ) 2 (r/2) 2 ) (1)
The first cluster center is chosen as the point that has the maximum density function. Afterwards, this process is repeated until a sufficient number of centers is attained. While repeating this process to find new cluster's centers, all data points are considered as candidates for the new cluster's centers, except the previously final calculated cluster's center and its surrounding (see Figure 4). Supposing a new emotional state is added to the database which will be in this case a N-D clustering process, where N is the number of elements in the database, the subtractive clustering algorithm can work efficiently to precise the whole number of clustering centers, however, the main challenge now is to collect similar centers in terms of the possible internal state they present into separate groups, which will facilitate the detection of the new coming internal states to the database if any. More results will be available by the time of the conference, as this paper reports ongoing work in progress.

VII. CONCLUSION

This research illustrates a combined model for gender and internal state detection. The total average recognition score of the combined model is about 88% which could be considered as a good score not only because of the large processed database (i.e., all voice samples of the German speech database with more than 520 sample), but also, because of the accuracy of the gender detection system. The whole combined system could be considered as a successful system.

  Towards an Online Voice-Based Gender and Internal State Combined Detection Model Amir Aly and Adriana Tapus Cognitive Robotics Lab/UEI Computer Science Department Ecole Nationale Superieure de Techniques Avancees (ENSTA-ParisTech)

Fig. 1 :

 1 Fig. 1: Female and Male Voice Recognition Score

Fig. 4 :

 4 Fig. 4: 2-D subtractive clustering for the extracted features of 2 elements of the database of emotional type: Anger. The clustering centers presented by the black points could be averaged to have a final cluster center for the 2 groups' data.

ACKNOWLEDGEMENTS

This work is supported by the French National Research Agency (ANR) through Chaire d'Excellence program 2009 (Human-Robot Interaction for Assistive Applications).