Ilya Issenin

Nikil Dutt
email: dutt@ics.uci.edu

FORAY-GEN: Automatic Generation of Affine Functions for Memory Optimizations *

In today's embedded applications a significant portion of energy is spent in the memory subsystem. Several approaches have been proposed to minimize this energy, including the use of scratch pad memories, with many based on static analysis of a program. However, often it is not possible to perform static analysis and optimization of a program's memory access behavior unless the program is specifically written for this purpose. In this paper we introduce the FORAY model of a program that permits aggressive analysis of the application's memory behavior that further enables such optimizations since it consists of 'for' loops and array accesses which are easily analyzable. We present FORAY-GEN: an automated profilebased approach for extraction of the FORAY model from the original program. We also demonstrate how FORAY-GEN enhances applicability of other memory subsystem optimization approaches, resulting in an average of two times increase in the number of memory references that can be analyzed by existing static approaches.

Introduction*

Customization of memory subsystem in embedded applications is an important part of system design that helps to achieve required power consumption and performance.

Recently a lot of attention has been paid to the use of a scratch pad memory (SPM) in the custom memory subsystems [START_REF] Issenin | Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies[END_REF][6] [START_REF] Kandemir | Dynamic Management of Scratch-Pad Memory Space[END_REF][8][9] [START_REF] Verma | Data Partitioning for Maximal Scratchpad Usage[END_REF]. Scratch pad memories have lower power consumption than caches [START_REF] Banakar | Scratchpad Memory: Design Alternative for Cache On-chip Memory in Embedded Systems[END_REF] and have predictable latency, which is important for real time applications.

Currently, many automated techniques for determining scratch pad configurations rely on compile-time analysis of the program; unfortunately these analysis approaches limit the scope of such memory optimizations, since they assume that the program is written in well structured manner, where all repeating accesses to the memory occur inside for loops and furthermore, all memory accesses are generated by array references with affine index expressions (which we name the FORAY form). However, our studies show that many real embedded applications are not written in this form. For example, Figure 1 shows code segments of the jpeg application from the MiBench benchmark suite [START_REF] Guthaus | MiBench: A free, commercially representative embedded benchmark suite[END_REF], that contain many memory/array access that do not follow the FORAY form: not all loop structures are for loops, and arrays are accessed using pointers rather than index expressions; furthermore, the iterators of for loops are not used in the index expressions of array references. Currently existing memory optimization approaches [START_REF] Issenin | Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies[END_REF][6] [START_REF] Kandemir | Dynamic Management of Scratch-Pad Memory Space[END_REF] are unable to analyze such source codes automatically. This limitation significantly reduces the opportunity for memory optimization and motivates the need for our automated approach.

We overcome these problems in this paper through two contributions. First, we introduce the FORAY model of a program, which is another C program that contains an abstraction of the memory behavior of the original program written in the FORAY form; this FORAY model of the program can be aggressively analyzed and optimized using existing memory subsystem optimization approaches. Second, we present FORAY-GEN, an approach that automatically generates the FORAY model for a given input program, thereby enabling a wider reach for aggressive optimization of the memory subsystem with minimal manual intervention or analysis. Our experimental results show that using FORAY-GEN, we are able to achieve on average a two times increase in the number of analyzable memory references, which in turn greatly increases the scope of memory optimizations.

Related work

There has been extensive research in using scratch pad memories for storing frequently used data. Some of the approaches [START_REF] Steinke | Assigning Program and Data Objects to Scratchpad for Energy Reduction[END_REF][9] [START_REF] Verma | Data Partitioning for Maximal Scratchpad Usage[END_REF] divide all the data used by a program into data objects and profile the application to determine how often and when these data objects are accessed. The most frequently used ones are relocated to scratch pad memory. These techniques do not require any knowledge about the program except declarations of data objects and the information about their use which is obtained by profiling.

for (ci = 0; ci < cinfo->num_components; ci++) for (coefi = 0; coefi < DCTSIZE2; coefi++) *last_bitpos_ptr++ = -1; currow = 0; while (currow < numrows)

for (i = rowsperchunk; i > 0; i--) { result[currow++] = workspace; }

Figure 1. Excerpts from the MiBench benchmark

However, such approaches typically do not handle finegrain array placement, i.e., determining and placing the most frequently used parts of the arrays in the scratch pad memory in order to improve power and performance.

The works [START_REF] Issenin | Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies[END_REF][6] [START_REF] Kandemir | Dynamic Management of Scratch-Pad Memory Space[END_REF] are complementary to the above techniques and are focused on optimization of array accesses. To determine the parts of the array that are going to be reused and which can be placed in the scratch pad memory, a static analysis of the program is performed. This requires all memory accesses (that need to be analyzed) to be expressed as array accesses with affine index expressions (i.e., the FORAY form). Using static analysis ensures that selected array references always expose expected behavior regardless of the input data. Unfortunately, application developers write code in styles suited to individual tastes, and therefore do not always express memory references in the FORAY form. Indeed our studies show that existing benchmarks and source codes contain many memory references that are not written in the FORAY form. This either limits the scope of these scratch pad memories optimization techniques, or requires system designers to manually transform the memory references in the input code to follow the FORAY form. Such manual transformation is cumbersome, time-consuming, and prone to errors; it rapidly becomes infeasible for large applications. For example, the jpeg application [START_REF] Guthaus | MiBench: A free, commercially representative embedded benchmark suite[END_REF] has more than 30000 lines of code with hundreds of loops. Limiting the scope of manual transformations may result in many missed opportunities.

The work of Franke et al. [START_REF] Franke | Compiler Transformation of Pointers to Explicit Array Accesses in DSP Applications[END_REF] addresses the problem of converting pointer accesses to array accesses with explicit index functions by performing compile-time analysis of the code. However, since static pointer analysis without any restrictions is intractable, many assumptions about the program structure are made.

Our FORAY-GEN approach automatically generates code in the FORAY form by performing additional dynamic analysis that exposes memory references in the FORAY form. Indeed, we are able to discover all memory references that actually behave as array references with affine index expressions but expressed in any other way in a source program.

Design flow using FORAY-GEN

We now outline the use of FORAY-GEN in the context of typical memory subsystem optimization techniques.

First, we define the FORAY model: it is a C program consisting of any combination of for loops and array references (FORAY), with all array index expressions being affine functions of outer loop iterators. Array references can also have partial affine index expressions, which is described in more detail is Section 4. Note that the FORAY model captures the memory behavior of only those memory references in the original program whose access addresses can be described by affine function of outer loop iterators. All other accesses or program functionality are left out of the model. Thus the FORAY model is not functionally equivalent to the original program, but is an abstraction enabling aggressive memory analysis that faithfully captures all memory references that are amenable to optimization by current memory optimization approaches; it is exclusively used for enhancing the reach of such optimizations.

The FORAY models for the examples in Figure 1 are shown in Figure 2, where the memory access behavior is restructured into well structured for loops containing array references with affine index expressions.

The use of the FORAY model in the context of typical SPM subsystem optimization techniques is shown in Figure 3. In Phase I, FORAY-GEN takes legacy C code as input and generates a FORAY model of the application. In Phase II, this FORAY model is optimized using a typical approach for designing a scratch pad memory subsystem (expanded in the shaded call-out of Figure 3). These SPM optimizations typically scan the memory accesses (in FORAY form) and perform compile-time (static) analysis of which data is reused and can be placed to the buffers in the scratch pad memory. Several buffer configurations are suggested and one of them is selected during the design space exploration. The output of Phase II contains FORAY model source code that is changed to access the scratch pad memory and perform the necessary data transfers between scratch pad buffers and main memory Finally in Phase III, (i.e., after determining which arrays benefit from being placed in the scratch pad memory), the designer can manually back-annotate the modified FORAY model code into the original program. At the end of this entire flow, the legacy C code is transformed into C code containing aggressive scratch pad memory optimizations.

Note that the amount of back-annotation required by the designer is significantly less than the efforts needed to manually convert the whole original program to FORAY form, since only a few arrays are typically selected to be placed in scratch pad memory.

Figure 3. The use of FORAY model in memory subsystem design

The main contribution of this paper is the automation of Phase I (FORAY-GEN) in this flow. Note that in Phase II, the generated FORAY model can be used by any scratch pad (such as [START_REF] Issenin | Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies[END_REF][6] [START_REF] Kandemir | Dynamic Management of Scratch-Pad Memory Space[END_REF]) or other memory optimization techniques.

FORAY-GEN

We now describe our profile-based FORAY-GEN approach, as outlined in Algorithm 1 (Figure 5).

First, in

Step 1 of Algorithm 1 we annotate the loop structures (for, do and while loops) in the source code of a program with checkpoints. Each checkpoint statement is converted later into special assembler instructions that instruct the simulator to add information about execution of the checkpoint to the trace file. An example of an original and the annotated program is shown in Figure 4(a) and (b).

In Step 2 of Algorithm 1 we profile the compiled program by running it on an instruction set simulator. The simulator records the information about each memory access (instruction address and address of access) as well as the information about all checkpoint instruction executed in the trace file. The trace file for the program in Figure 4(a) is shown in Figure 4(c).

In Step 3 of Algorithm 1 we process the trace file generated in the previous step and reconstruct the program loop structure (Step 3.1). In addition to that, during the same pass on the trace file, for each memory reference we try to find an affine expression that can describe all the access addresses of this reference (Step 3.2). These steps are discussed in more detail later in this section.

In Step 4 of Algorithm 1 we use a heuristic that filters out all memory references that cannot be effectively predicted by an affine function. We leave only the references that

• have affine index expression that includes at least one iterator (by this condition we exclude all references that do not have regular access patterns);

• have been executed no less than N exec times;

• address at least N loc different memory locations. The constants N exec and N loc are selected to leave only references that may benefit from being placed in the scratch pad memory by array-oriented design techniques. In our experiments we used the values of 20 and 10 correspondingly to eliminate small arrays that can fit in the scratch pad completely (and thus can be handled by other techniques like [START_REF] Steinke | Assigning Program and Data Objects to Scratchpad for Energy Reduction[END_REF][9] [START_REF] Verma | Data Partitioning for Maximal Scratchpad Usage[END_REF] with less overhead) and to eliminate references which do not exhibit a lot of reuse.

The resulting FORAY model for the program in Figure 4(a) is shown in Figure 4(d).

Next, we describe our implementation of the trace file analysis (Steps 3.1 and 3.2 of FORAY-GEN in Algorithm 1).

Reconstructing loop structure from trace (Step 3.1 of Algorithm 1)

Figure 6. Algorithm outline for loop structure reconstruction

The loop/reference structure of the program is represented as a tree with loop and memory reference nodes. During the processing of the trace file each loop node also maintains the current value of a variable that counts the number of loop iterations. The values of these iterators are used for determining index expressions in Step 3.2 of the Algorithm 1.

Identifying affine index expressions for memory references (Step 3.2 of Algorithm 1)

We first give an example of the analysis we perform, and then describe our algorithm (Algorithm 3) for identifying Affine address functions have the following form:

index = const + C 1 *iter 1 + C 2 *iter 2 + … + C N *iter N ,
where index is the access address of the memory reference; const -is some constant term (base memory address); N is the loop nest level of the memory reference; C 1 ..C N are integer coefficients; and iter 1 .. iter N are current values of the loop iterators (iter 1 is the iterator of the innermost loop).

In the example of Figure 4a the exact index expression for all memory references can be found. However, often it is not possible to describe access addresses by one affine function. Two examples of such cases are shown in Figure 7. In the first case, for each call to the function foo(), a local array A[] may be allocated to a different memory location. In the second case, the globally defined array A[] is not reallocated, but the offset is a data-dependent parameter that is passed to the function foo(). In both instances, the access addresses within the function foo() are regular and can be described by one affine function. However, with every iteration of the outer loops x and y, the constant term in the index expression changes in an unpredictable manner. In these cases our analysis algorithm finds a partial affine index expression for the loop iterators for which the value of index can be predicted by the expression in the form of

index = const(iter M+1 iter N ) + C 1 *iter 1 + … + C M *iter M ,
where M < N; const changes every time with the increment of iter M+1 .. iter N .

Finding memory references that are expressible as partial affine index expression enhances existing SPM analysis approaches [START_REF] Issenin | Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies[END_REF][6] [START_REF] Kandemir | Dynamic Management of Scratch-Pad Memory Space[END_REF]. Indeed, when no full affine index expression exist, SPM approaches can still perform analysis on a limited number of loops (which are inside the function foo() in the example in Figure 7) as if no other outer loops existed and suggest possible scratch pad buffer configurations that hold the data reused in loops in function foo().

Algorithm 3 in Figure 8 describes how index expressions are determined; it is called for each memory access recorded in the trace file in Step 2 of Algorithm 2.

In Step 1 of Algorithm 3 we create a new memory reference node if we have not encountered this memory reference in the current position inside the loop tree.

If the current memory reference has been encountered before, in Step 2 of Algorithm 3 we calculate the number H of coefficients that have an UNKNOWN value and whose corresponding iterators have changed their value after the previous execution of the same memory reference. In variable k we save the number of one of such iterators.

In Step 3 of Algorithm 3 we calculate the value of an unknown coefficient if only one iterator with unknown coefficient has changed its value.

If there are several iterators with unknown coefficients that have changed their values, in Step 4 of the Algorithm 3 we mark the current reference as non-analyzable and exclude it from further consideration. Our experiments show that there are very few such references in the benchmarks we studied.

In Step 5 of Algorithm 3 we calculate the predicted value of affine index expression.

End Figure 8. Algorithm for finding index expressions

In Step 6 of Algorithm 3 we check if this predicted value matches actual address of the memory access. If the prediction is wrong, we mark all iterators that have not changed their values, recalculate the new value of the constant term in the affine index expression and update the value of M that specifies the number of iterators included in the partial index expression. This is done by finding the outermost iterator that has changed its value in every misprediction case. All innermost iterators up to that one are forming a partial affine index expression.

Note that during the building of the FORAY model of a program, each record in the trace file is accessed only once and the records are accessed in the order the information is written to the file. This means that the proposed algorithm can be executed during profiling (Step 2 of the Algorithm 1) and there is no need to save the (typically large) trace file. In this case the space complexity is constant with respect to the number of instructions profiled.

The computational complexity of our approach is dominated by the number of calls of the Algorithms 2 and 3, and is linear with respect to the number of profiled instructions. Since the maximum loop nest level is limited in real programs, the complexity of the Algorithms 2 and 3 is constant on average if we use hash tables for the searches in Algorithm 2 and in Step 1 of Algorithm 3.

Inter-function optimizations

Our approach also helps a designer by providing hints on which functions should be inlined to enable more aggressive memory optimizations -this is particularly helpful when a designer attempts to manually restructure code for improved performance and power.

The FORAY model does not have any special representation of the hierarchical structure of a program, which is why functions appear to be inlined in our model. If FORAY-GEN inlines a function in more than one place, this provides a hint to programmer that it may be beneficial to duplicate the function in the original code. In the example shown in Figure 9 the function foo() is called in two different places. In those instances the access pattern to array A[] inside the body of the function is different. Optimizing the function for the first access pattern can produce suboptimal results for the case when foo() is called in the loop y. Duplicating the function as suggested by our approach produces better results by allowing each access pattern to be optimized separately.

Experimental results

We now describe the implementation of the FORAY-GEN framework presented in Algorithm 1. Our parser for Step 1 of Algorithm 1 parses source C files of a benchmark and inserts checkpoint instructions. We use the SimpleScalar functional simulator [START_REF] Burger | The SimpleScalar tool set, version 2.0[END_REF] for profiling (Step 2 of Algorithm 1). The simulator was modified to process checkpoint instructions and to generate the trace file. Steps 3 and 4 of Algorithm 1 are implemented in a separate program that reads the trace file, performs analysis and extracts the FORAY model.

To evaluate our approach, we used several benchmarks from the MiBench suite [START_REF] Guthaus | MiBench: A free, commercially representative embedded benchmark suite[END_REF] that contains a set of embedded codes written in standard "C". The following benchmarks were used: jpeg (image compression), lame (MP3 encoder), susan (image recognition program), fft (Fast Fourier Transformation), and the gsm and adpcm encoders.

Advantages of using FORAY-GEN

In this section we present the benefits of using our automated FORAY-GEN tool to extract FORAY models for the benchmarks.

First, we estimated the complexity of manual analysis needed to extract FORAY model that can be automated by our approach. The number of lines of code in each benchmark and total number of loops (excluding the loops that were not executed during profiling) are presented in Table I. Breakdown of the loops by the type (for, while or do loops) is also presented.

Table I shows that some of the typical embedded applications are fairly large and have hundreds of loops. Manual analysis of every loop in such applications is errorprone and impractical. We can also conclude that although for loops are used predominantly in the programs, there are a lot of other loops (23% on average) that should not be ignored during the analysis (as described earlier, existing approaches for loopbased program analysis consider only for loops).

We have also estimated how many of the useful references for scratch pad memory analysis [START_REF] Issenin | Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies[END_REF][6] [START_REF] Kandemir | Dynamic Management of Scratch-Pad Memory Space[END_REF] are not in the FORAY form in the original program and thus can not be analyzed by their static approaches. Table II shows the number of loops and references that can be expressed in FORAY form (those that were found by our algorithm and included in the FORAY model), and percentage of loops and references that are not in FORAY form in the original program.

As we can see from the Table II, in all the benchmarks except fft (the shortest one), a considerable number of loops and memory references (64% and 60% on average) are not in FORAY form and thus cannot be statically analyzed by traditional scratch pad memory optimization techniques without using our approach.

Memory behavior of the FORAY model

We now analyze the effectiveness of our extracted FORAY model in capturing the memory behavior of the original program.

We analyzed three aspects of memory behavior: the number of memory references, the number of accesses these references make, and the footprint (the number of different addresses accessed). Recall that the FORAY model captures only the , and all other memory references that can not be represented by the FORAY model. Note that system libraries are specific for the platform the code is compiled on and therefore system libraries we used are not relevant to real embedded systems.

As we can see from the breakdown in Table III, although very few references in the source code are described by the FORAY model (and worth considering for analysis by techniques [START_REF] Issenin | Data Reuse Analysis Technique for Software-Controlled Memory Hierarchies[END_REF][6][7]) -2.2% on average -these references make up to 66% (29% on average) of all accesses and cover up to 87% (44% on average) of the address space.

It is important to note that the data shown in the table includes memory references that are not present explicitly in the source C code (e.g., those placing arguments to the stack before performing function calls, memory spills, etc.). However, these references address only few locations and are not included in the FORAY model after being filtered out by the Step 4 of Algorithm 1. Note also that all functions that are called from different contexts are considered to be inlined (as explained in Section 4) for the purpose of calculating the number of loops and references in our experiments.

In summary, memory references that can be represented in FORAY form and are not in this form in a source code account for a large portion of memory activity in typical embedded applications. Our FORAY-GEN approach helps to automate the extraction of such references and thus expands the reach of SPM optimizations.

Conclusion

In this paper we introduce the notion of the FORAY model of a program which is another program consisting of for loops and array references with affine index expressions that models the memory behavior of the original program and that is amenable to optimizations. We presented FORAY-GEN, a technique for fully automated extraction of the FORAY model from a source program. We show how this model can be used to expand the reach of contemporary memory optimization techniques, increasing the number of analyzable references two times on average for typical embedded multimedia benchmarks. Our FORAY-GEN approach thus significantly increases the reach of SPM optimizations while freeing designers from the cumbersome and error-prone task of manual code analysis, thereby improving designer productivity. Our future work will study the interdependency of the FORAY models on the input data set used for profiling.

Table III. Memory behavior of the FORAY models

Figure 6 Algorithm 2 :

 62 Figure 6 outlines the algorithm we developed that reconstructs the loop/reference structure of the original program from the trace file (Step 3.1 of the Algorithm 1). Algorithm 2: Building the loop structure of a program Input: trace file Output: a tree with loop and memory reference nodes 1. Read next record from the trace file. 2. If it is memory access information, call Algorithm 3 (see below). 3. If it is checkpoint, depending of the type of checkpoint (beginning-of-the-loop, beginning-of-the-loop-body or end-ofthe-loop-body checkpoint), move current loop node pointer up or down in the tree or create a new loop node. 4. Go to Step 1.

Figure 4 .Algorithm 1 :Figure 5 .

 415 Figure 4. Example of FORAY-GEN model extraction

Figure 7 . 3 : 1 ;

 731 Figure 7. Examples when access addresses can not be described by one affine function

Figure 9 .

 9 Figure 9. Example of a code where function inlining may be beneficial

Table I . Benchmark complexity and loop distribution

 I

	Benchmark name	Number of lines	Total number of loops	Number of for loops	Number of while loops	Number of do loops
	jpeg	34590	169	65%	34%	1%
	lame	22846	479	83%	8%	9%
	susan	2173	14	79%	21%	0%
	fft	493	11	100%	0%	0%
	gsm	7089	38	87%	13%	0%
	adpcm	782	2	50%	50%	0%
	Benchmark	Total number		Included in FORAY model		In system calls		Other
	name	References Accesses Footprint	Ref.	Accesses Footprint	Ref.	Accesses Footprint	Footprint
	jpeg		6151	8.3M	123625	1%	27%	87%	33%	2%	9%	91%
	lame		16805	43M	127052	6%	22%	26%	40%	20%	33%	66%
	susan		1162	5.0M	24778	1%	66%	72%	85%	1%	47%	1%
	fft		2420	22M	28804	1%	1%	57%	95%	96%	43%	29%
	gsm		2091	37M	16215	4%	32%	5%	49%	3%	93%	8%
	adpcm		546	5.5M	4964	0.2%	28%	20%	97%	0.2%	68%	12%

Table II . Loops and references converted into FORAY form by our approach

 II

		Loops and	Percentage of loops and
		references that can	references that are not in
		be represented by	FORAY form in the original
	Benchmark	FORAY form	program (out of those that
	name	(returned by	can be expressed in
		Algorithm 1)	FORAY form)
		Number	Number of	Number of	Number of
		of loops	references	loops	references
	jpeg	73	73	41%	38%
	lame	232	980	42%	38%
	susan	9	10	78%	50%
	fft	8	19	0%	0%
	gsm	17	86	59%	74%
	adpcm	2	1	100%	100%

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

* This work was partially supported by NSF grants CCR-0203813 and CCR-0205712.


Daniel Massart

Hugo Parlier
email: hugo.parlier@unifr.ch

On the Homology Length Spectrum of Surfaces

On a surface with a Finsler metric, we investigate the asymptotic growth of the number of closed geodesics of length less than L which minimize length among all geodesic multicurves in the same homology class. An important class of surfaces which are of interest to us are hyperbolic surfaces.

Introduction

The questions we ask

Let (M, m) be a closed, orientable manifold of dimension 2, equipped with a Finsler metric. We are interested in the asymptotic growth, as T grows, of a certain set of closed geodesics of length less than T.

 showed that the cardinality of G 0 (T) grows like e T /T.

Similarly, for a fixed homology class h in H 1 (M, Z), one can count the number of closed geodesics with homology h and of length less than L. The asymptotic growth of this number has also been studied, for instance, by Philips and Sarnak [17].

2 D. Massart and H. Parlier Here, we are interested in a problem which is in some sense orthogonal to the latter: instead of picking a homology class and counting all closed geodesics therein, we consider all homology classes, and associate with each one (at most) one closed geodesic. We then estimate the asymptotic growth of this set of closed geodesics.

To be precise, we need to introduce the stable norm of m. This is the function which maps each homology class h in H 1 (M, Z) to the smallest possible length of a union of geodesics representing h. This union will always be a weighted multicurve (disjoint union of simple closed geodesics, possibly with multiplicity). Recall that since M is orientable, H 1 (M, Z) embeds as a lattice in H 1 (M, R). The map thus defined extends to a norm on H 1 (M, R), called stable norm and denoted g ( [START_REF] Balacheff | Stable norms of non-orientable surfaces[END_REF][START_REF] Federer | Real flat chains, cochains and variational problems[END_REF][START_REF] Gromov | Structures Métriques Pour Les Variétés Riemanniennes[END_REF][START_REF] Massart | Stable norms of surfaces: local structure of the unit ball at rational directions[END_REF]). We denote by B 1 its unit ball. We say a geodesic multicurve is minimizing if it minimizes the length among all multicurves within the same homology class.

There are multiple counting problems one could investigate here. The first one that comes to mind is to find asymptotic estimates for the number of elements of H 1 (M, Z) with stable norm less than T when T goes to infinity. By Minkovski's theorem, this is easily seen to be ≈ Vol(B 1 )T 2g where g is the genus of M (and thus the dimension of H 1 (M, R) is 2g). The quantity Vol(B 1 ) is the volume of the unit ball with respect to the following volume form. As M is orientable, the algebraic intersection of oriented closed curves induces a symplectic form on H 1 (M, R), which we denote Int(., .). The gth power of this symplectic form is a volume form on H 1 (M, R) with respect to which the integer lattice H 1 (M, Z) has determinant 1. The volume Vol(B 1 ) is meant with respect to this volume form.

However, we argue that this is not necessarily the most relevant counting problem when it comes to surfaces of genus > 1. Indeed, it is proved in [START_REF] Massart | Stable norms of surfaces: local structure of the unit ball at rational directions[END_REF] that infinitely many homology classes in H 1 (M, Z) have a minimal representative which is a multicurve with exactly g connected components. Furthermore, if a simple closed geodesic occurs as a connected component of a geodesic multicurve, then in fact it occurs as a connected component of infinitely many geodesic multicurves [START_REF] Massart | Stable norms of surfaces: local structure of the unit ball at rational directions[END_REF]. Therefore, when counting geodesic multicurves, there is a lot of redundancy and it is thus of interest to count these connected components.

It can be seen from [START_REF] Balacheff | Stable norms of non-orientable surfaces[END_REF][START_REF] Massart | Stable norms of surfaces: local structure of the unit ball at rational directions[END_REF] So the objects we shall focus on are the closed geodesics which minimize length in their homology class (thus among all multicurves with the same homology). We denote the set of these by G. For the sake of brevity we shall call such closed geodesics minimizing in their homology classes, or homologically minimal. Our purpose here is to find asymptotic estimates, when T → +∞, for the cardinality N(T) of the set

H (T) := {[γ ] : γ ∈ G, m (γ ) ≤ T}.
Again by Minkovski's theorem, N(T) is bounded from above by Vol(B 1 )T 2g . How far below the value this estimate the actual growth is, is a measure of how few closed geodesics minimize the length in their homology class, or how many homology classes are minimized by (non-connected) multicurves.

Observe that when M is not orientable, the unit ball of the stable norm could be a finite polyhedron (see [START_REF] Balacheff | Stable norms of non-orientable surfaces[END_REF]), in which case there are only finitely many homology classes of elements of G. This however never happens for orientable surfaces, so the asymptotic counting problem will always be non-trivial in this case.

Although we have scant evidence as to what the answer might be, we ask the following question to get the ball rolling.

Question 1.1. Does N(T) grow quadratically for all (M, m)?

When M is a torus, this follows from Minkovski's theorem. Although our setup does not allow for this, the same questions can be asked when the surface is hyperbolic torus with a cusp, a case well investigated by McShane and Rivin [START_REF] Mcshane | A norm on homology of surfaces and counting simple geodesics[END_REF][START_REF] Mcshane | Simple curves on hyperbolic tori[END_REF] where among things they prove asymptotic quadratic growth and a bound on the error term. Furthermore, minimizing geodesics do not pass through separating "long thin necks" (see Lemma 2.8 for the exact definition and statement). When M is such that these "necks" cut the surfaces into parts of genus at most 1, N(T) becomes a finite sum of functions which grow quadratically and thus also grows quadratically. This is discussed in more detail in Section 2.5.

There is a connection between the problem we investigate and the question of counting closed trajectories of a polygonal billiard table with angles commensurable to π. Such closed trajectories correspond to closed geodesics of a flat surface with cone point singularities (see [START_REF] Kerckhoff | Ergodicity of billiard flows and quadratic differentials[END_REF]). The closed geodesics which come from closed billiard trajectories are easily seen to be minimizing in their homology classes (but not all minimizing geodesics come this way). A positive answer to Question 1.1 would thus provide a generalization of Masur's quadratic upper bound on the number of strips of parallel closed billiard trajectories [START_REF] Masur | The growth rate of trajectories of a quadratic differential[END_REF]. Furthermore, Masur's bound provides further evidence that the correct bound is indeed quadratic.

The answers we give

Now that we have introduced the problem, let us lay out what we do in this paper. We want to organize the set G into families which grow quadratically and, for each family, provide a geometric interpretation of the quadratic constant. For simplicity, and for the remainder of the introduction, we suppose that M is of genus 2.

Let us fix an element of G, that is, a simple, closed, homologically minimizing geodesic γ . Denote by G γ the set of all elements δ of G, such that the reunion of γ and δ is a homologically minimizing multicurve. The sets G γ , when γ ranges over G, are the families into which we organize (but not partition) G. So, denoting

• G γ (L) the set of elements of G γ of length ≤ L, • H γ (L) the set of homology classes of elements of G γ (L), • N γ (L) the cardinality of H γ (L),
we want to prove that N γ (L)/L 2 has a limit when L goes to infinity, and provide a geometric interpretation for this limit.

Since closed geodesics which minimize the length in their homology class correspond to vertices of the unit ball of the stable norm (see Section 2.1), the approach we propose to our counting problem is to understand the set of vertices of the unit ball.

First let us observe that for any δ in G γ , since γ and δ are disjoint, we have

Int([γ ] , [δ]) = 0, that is, [δ] lies in the symplectic orthogonal [γ ] ⊥ of [γ ]. As the genus of M is 2, this symplectic orthogonal is a three-dimensional subspace of H 1 (M, R), which contains [γ ]
. Furthermore, the kernel of the restriction to [γ ] ⊥ of the symplectic form Int(., .) is the straight line generated by [γ ]. So the quotient space [γ ] ⊥ / [γ ] inherits a symplectic structure, which will be useful in the sequel. Moreover, by [START_REF] Balacheff | Stable norms of non-orientable surfaces[END_REF][START_REF] Massart | Stable norms of surfaces: local structure of the unit ball at rational directions[END_REF] (see Theorem 2.3) we know the following facts:

• For any δ in G γ , the unit ball B 1 of the stable norm has an edge joining

[γ ] / [γ ] to [δ] / [δ] . • Any edge of B 1 starting from [γ ] / [γ ] is contained in [γ ] ⊥ .
V of [γ ] / [γ ] in ∂B 1 ∩ [γ ] ⊥ such that for any homology class h in V , the straight segment joining h to [γ ] / [γ ] is contained in ∂B 1 ∩ [γ ] ⊥ . We denote by Ẽ(γ ) the reunion of all edges of B 1 starting from [γ ] / [γ ] . Thus, Ẽ(γ ) projects to a compact neighborhood E(γ ) of 0 in the quotient space [γ ] ⊥ / [γ ].
For instance, when M is a surface with long thin necks (as described in Section 2.5 and illustrated in Figure 2), for any x, y ∈ R, the homology class

x [δ] + y [β] x [δ] + y [β]
LE(γ ) = {tx : t ∈ [0, L] , x ∈ E(γ )}.
A variation on the classical Minkovski theorem (Proposition A.1) then says that N γ (L)/L 2 converges to the volume, with respect to the symplectic structure on the quotient space For a surface of genus g > 2, we have to adjust our strategy a little bit: instead of fixing an element γ of G, we fix g -1 elements γ 1 , . . . , γ g-1 elements of G, whose reunion is a minimizing multicurve, and we consider the subset G of G which consists of closed geodesics γ such that the reunion of γ and is a minimizing multicurve.

[γ ] ⊥ / [γ ], of the compact set E(γ ).
Then we prove that G , as G γ in the genus 2 case, grows quadratically, again under some genericity assumption on the metric m. The genericity hypothesis we alluded to in the previous paragraph is that in every homology class there is at most one minimizing multicurve. It would be interesting to know whether this hypothesis is truly necessary, and if it is, how restrictive it is. The word "genericity" seems to indicate that metrics not satisfying this hypothesis are Baire meagre in the set of all metrics.

However, we do not have a proof of this fact. It is true, however, in the smaller set of metrics of constant negative curvature, as outlined in Section 2.4. In the larger setting of Finsler metrics, we believe the genericity could be proved using the machinery of [START_REF] Bernard | A generic property of families of Lagrangian systems[END_REF].

Now we would like to know how much our result really says about Question 1.1.

Again, for simplicity we consider the genus 2 case. If, instead of fixing an element of G, we consider a family (γ i ) i∈I of elements of G, can we say something about the growth of the reunion i∈I G γ i ? Obviously we can if the family (γ i ) i∈I is finite, but even in that case the interpretation of the quadratic constant is not clear since for each γ i we have to use the symplectic structure of the quotient space [γi] ⊥ / [γi].

It would be interesting to interpret the quadratic constants directly in terms of the symplectic structure of H 1 (M, R). For this we suggest the following procedure.

Step 1: Prove that for each γ ∈ G, the set F γ defined as the closure in

H 1 (M, R) of the set {t [δ] : δ ∈ G γ , t ∈ [0, 1]}
is rectifiable, so we can evaluate its symplectic area with respect to the symplectic form Int(., .). Denote it (γ ).

Step 2: Prove that (γ ) equals the area, with respect to the symplectic structure

on the quotient space [γ ] ⊥ / [γ ], of the compact set E(γ ).
What is interesting about this point of view is that assuming both points above are true, if we have a countable family (γ i ) i∈I of elements of G, the reunion i∈I G γ i is again rectifiable, so we can evaluate its symplectic area.

Recall that the set of homology class of elements of G is countable. We propose the following.

• F be the closure in H 1 (M, R) of the set {t [δ] : δ ∈ G, t ∈ [0, 1]},
• G T be the set of elements of G with length ≤ T,

• H (T) the set of homology classes of elements of G(T),

• N(T) the cardinality of H (T), then

• F is rectifiable. We denote (F) its symplectic area with respect to the intersection form Int(., .).

•

We have the following asymptotic estimate:

lim T→+∞ N(T) T 2 = (F) .
Of course, even if the conjecture is true, it does not say much if (F) is infinite.

Therefore, our aim is now to find sufficient conditions for (F) to be finite.

One such condition is when M has g -1 thin long necks (we call such a surface a giraffe surface). We are able to prove the conjecture for these surfaces under the genericity condition mentioned above.

Theorem 1.3. Let (M, m) be a generic giraffe surface of genus g.Then

lim T→∞ N(T) T 2 = g i=1 (S i ∩ B 1 ), g i=1 S i ∩ B 1 = F and g i=1 (S i ∩ B 1 ) = (F).
The question that remains is how far from this somewhat obvious hypothesis can one go.

Minimizing measures

We denote by M the set of Borel measures on the unit tangent bundle T 1 M of (M, m), not necessarily normalized (i.e., the total mass need not be 1), which are invariant under the geodesic flow of m. Observe that this is the set of geodesic currents, as defined in

[3]. If μ ∈ M, we denote m(μ) := T 1 M
1 dμ so m(μ) is both the total mass of μ, and, when μ is supported by a closed geodesic α, the length of α, thus the notation m(μ) is quite convenient.

By [START_REF] Mather | Action minimizing invariant measures for positive definite Lagrangian systems[END_REF] (see also [START_REF] Balacheff | Stable norms of non-orientable surfaces[END_REF]), for any μ in M and any C 1 function f on M we have

T 1 M df dμ = 0. (1)
Thus, the measures in M have a well-defined homology class in H 1 (M, R). For instance if μ is supported by a closed orbit of the geodesic flow (γ , γ ), γ a closed geodesic, then the homology class of μ is just that of γ .

We say a measure μ in M is minimizing when it is minimizing in its homology class [μ], that is, when

m(μ) = [μ] .
One of the reasons for considering invariant measures (rather than just geodesic multicurves) is that there may be homology classes in H 1 (M, R) for which there is no minimizing multicurve. In fact, when M is an orientable surface, such classes always exist but there still always exists a minimizing measure [START_REF] Balacheff | Stable norms of non-orientable surfaces[END_REF][START_REF] Mather | Action minimizing invariant measures for positive definite Lagrangian systems[END_REF].

Lemma 2.1. Let μ, ν ∈ M be such that μ + ν is minimizing in its homology class. Then for any a, b ≥ 0, aμ + bν is minimizing in its homology class.

Proof. Take a supporting hyperplane at

[μ + ν] / [μ + ν] to the ball B 1 , that is, a cohomology class c ∈ H 1 (M, R) such that c, h ≤ h ∀h ∈ H 1 (M, R), (2)
c,

[μ + ν] = [μ + ν] . (3)
For any closed one-form ω on M such that [ω] = c, we have, by Equation ( 1),

c, [μ + ν] = T 1 M ωd(μ + ν) = T 1 M ω dμ + T 1 M ω dν. ( 4 )
Since μ + ν is minimizing in its homology class, we have

[μ + ν] = m(μ + ν) = m(μ) + m(ν). ( 5
)
so

T 1 M ω dμ + T 1 M ω dν = m(μ) + m(ν). ( 6
)
On the other hand, by the inequality (2), we have

c, [μ] ≤ [μ] ≤ m(μ), c, [ν] ≤ [ν] ≤ m(ν).
Those two inequalities sum up to the equality (6), so both inequalities are equalities : Now take a, b ≥ 0. We have

T 1 M ω dμ = m(μ), T 1 M ω dμ = m(ν).
c, a [μ] + b [ν] = a c, [μ] + b c, [ν] = am(μ) + bm(ν) = a [μ] + b [ν] ≥ a [μ] + b [ν] ,
where the last inequality is just the triangle inequality. On the other hand, by inequality

(2), we have

c, a [μ] + b [ν] ≤ a [μ] + b [ν] ,
hence

am(μ) + bm(ν) = c, a [μ] + b [ν] = a [μ] + b [ν]
which says that aμ + bν is minimizing in its homology class.

Faces of the stable norm

We will need Proposition 5.6, Theorem 6.1, Proposition 5.4, and Lemma 5.5 of [1] so we recall their statements below.

We say a homology class h in

H 1 (M, R) is • integer if h ∈ H 1 (M, Z) ⊂ H 1 (M, R),
• rational if there exists h ∈ H 1 (M, Z) and n ∈ N * such that h = nh, For all h ∈ V ( ) ⊥ , there exists s(h 0 , h) > 0 such that the subset of the unit sphere ∂B 1

h 0 + sh ||h 0 + sh|| : s ∈ 0, s(h 0 , h)
is a straight segment.

Proposition 2.4. Let γ 2 be a closed, simple, two-sided geodesic on a closed (possibly non-orientable) surface M endowed with a Finsler metric m. There exists a neighborhood

V 2 of (γ 2 , γ2 ) in T 1 M such that if γ is a simple closed geodesics entering V 2 (respectively, leaving V 2 ) then • either γ is a closed geodesic homotopic to γ 2 ,
• or γ is asymptotic to a closed geodesic homotopic to γ 2 ,

• or γ intersects γ 2 , and all intersections have the same sign with respect to some orientation of p(V 2 ), where p denotes the canonical projection

TM → M.
Lemma 2.5. Let M be a closed (possibly non-orientable) surface with a Finsler metric.

If a geodesic γ is asymptotic to a simple closed geodesic, then (γ , γ ) is not in the support of any minimizing measure.

Genericity

Definition 2.6. We say (M, m) is generic if, for every h ∈ H 1 (M, Z), there exists a unique minimizing multicurve in the homology class h.

We warn the reader that by using the word "generic" we are abusing terminology a little bit. Indeed by [START_REF] Mañé | Generic properties and problems of minimizing measures of Lagrangian systems[END_REF], the property of having only one minimizing measure for each integer homology class is residual in the set of Tonelli Lagrangians. However, this is still a much larger set than the set of all Finsler metrics. In the smaller set of hyperbolic surfaces, this property is true for a Baire dense set of surfaces. (We are considering the usual topology on the moduli space of hyperbolic metrics on a surface of fixed genus.)

Proposition 2.7. The set of hyperbolic surfaces without unique minimizing multicurves for every homology class is Baire meagre.

Proof. The ingredients for proving this can be found in [14, Lemma 4.1] so we only outline the argument here as the details are identical.

There are countably many topological types of weighted multicurves on a finite type hyperbolic surface. Any given hyperbolic metric will have a unique geodesic representative for a given topological type of multicurve, so to each type one associates a function over Teichmüller space, the space of marked hyperbolic metrics of given type.

Now given two such multicurves, we consider the subspace of Teichmüller space where the two geodesic representatives are of the same length. This subspace is the zero set for the difference of the length functions, and length functions of this type are analytic with respect to the analytic structure of Teichmüller space. If the zero set of this difference

function contained an open subset, it would be all of Teichmüller space but it is not difficult to prove that this is only possible if the topological types of the multicurves were identical to begin with. (The fact that we are dealing with collections of simple closed curves is essential as there are closed curves whose unique geodesic representatives are the same length for all points in Teichmüller space.) Furthermore, as these sets are zero sets for analytic functions, they are closed subspaces. One now concludes by applying Baire's category theorem to the countable collection of these subspaces.

When a surface is generic, any minimizing multicurve has at most g := genus(M) connected components. All the faces of B 1 are simplices.

Long thin necks and quadratic growth

We briefly describe a situation where we can guarantee quadratic growth. We begin with a lemma which says that minimizing geodesics do not cross separating geodesics with a sufficiently wide collar around them.

Lemma 2.8. Let γ be a separating closed geodesic. Assume that there exists r > 0 such that the set

V r (γ ) = {x ∈ M : d(x, γ ) ≤ r}
is homeomorphic to an annulus, and its boundary components are C 1 closed curves γ 1 and γ 2 , such that for i = 1, 2 we have 2d(γ i , γ ) ≥ l(γ i ).

Then, for any homologically minimal closed geodesic α, we have α ∩ γ = ∅.

Proof. Let α be a homologically minimal closed geodesic, and assume α ∩γ = ∅. Let a be an arc of α contained in V r (γ ), intersecting γ , with endpoints x a and y a on the boundary of V r (γ ). so, replacing a with an arc of γ 1 going from x a to y a , we obtain a closed curve homologous to α, and shorter, which contradicts the minimality of α (see Figure 1).

Second case: Assume x a and y a are on different boundary components of V r (γ )

(say, x a on γ 1 and y a on γ 2 ). Then, the algebraic intersection of a and γ is not zero. Since γ is separating and α is a closed curve, the algebraic intersection of α and γ is zero, so there exists another arc b of γ , intersecting γ , with endpoints x b and y b on γ 2 and γ 1 , respectively. Then we have

l(a) + l(b) ≥ 2 (d(γ 1 , γ ) + d(γ 2 , γ )) ≥ l(γ 1 ) + l(γ 2 )
so, replacing a and b with arcs of γ 1 and γ 2 going from x a to y b and from x b to y a , respectively, we obtain a multicurve homologous to α, and shorter, which contradicts the minimality of α. Definition 2.9. We say a separating closed geodesic has a long thin neck if it satisfies the hypothesis of lemma 2.8 above.

On a given surface we consider the set of curves with long thin necks as above.

Observe that two such curves are necessarily disjoint thus this set of curves forms a multicurve. Concrete examples of giraffes are given by hyperbolic surfaces with a collection of separating closed geodesics of length ≤ 2 arcsinh1 which cut the surface into a collection of tori and spheres (both with boundary). In this case the "long thin necks" are just the disjoint collar regions around the curves, forced by the hyperbolic metric.

In the remainder of this section we assume (M, m) be a giraffe of genus g, not necessarily hyperbolic. We denote by T 1 , . . . , T g the tori which are connected components of the complement in M of the curves with long thin necks, and by H i (for i = 1, . . . , g)

H 1 (M, R) = g i=1 S i .
Proof. Since T i is a torus with holes, we may find simple closed curves α i and β i in T i which intersect exactly once. So we have, for all i, j = 1, . . . , g,

|Int([α i] , β j )| = δ ij and |Int([α i] , α j )| = 0.
Therefore, the homology classes [αi] and [βi], i = 1, . . . , g, form a symplectic basis of H 1 (M, R). We now define S i as the linear span of [αi] and [βi] and the lemma is proved.

Now denote

G i = {γ ∈ G : γ ⊂ T i }.
Lemma 2.12. The elements of G i are in one-to-one correspondence with the elements

of S i ∩ H 1 (M, Z).
Proof. First, we pick an element γ of G i and prove its homology class lies in

S i ∩H 1 (M, Z).
Since γ is a closed curve its homology class lies in H 1 (M, Z). Since [αi] and β j , i, j = 1, . . . , g, form a basis of H 1 (M, R), we may write

[γ ] = g j=1 a j α j + b j β j . Now since γ ⊂ T i , for any j = i, Int([γ ] , α j ) = Int([γ ] , β j ) = 0 but |Int([γ ] , α j )| = |b j | and |Int([γ ] , β j )| = |a j |, so a j = b j = 0, that is, [γ ] ∈ S i .
Conversely, let us pick an element h of S i ∩ H 1 (M, Z), and prove it is the homology class of an element of G i .

Let us write

h = g j=1 a j α j + b j β j .
Since h ∈ S i , we have a j = b j = 0 for any j = i.

By the genericity of (M, m), there exists a unique h-minimizing multicurve γ . We want to prove that γ has only one connected component, and it is contained in T i , so γ is actually an element of G i .

Since (M, m) is a giraffe, by Lemma 2.8, any connected component of the multicurve γ is contained in some T j . Let us assume that γ has a connected component γ j contained in T j , for j = i. Then the homology class of γ j is not zero, for if it were zero, then γ \ γ j would be another multicurve with homology h, shorter than γ , thus contradicting the minimality of γ . But if the homology class of γ j is zero, then for some j = i, a j or b j is not zero, which we have already seen is impossible. Therefore, all connected components of γ are contained in T i . Now let us prove that γ is connected.

Assume γ has two connected components γ 1 and γ 2 , both contained in T i . Then γ 1 ∩γ 2 = ∅, because γ is a multicurve (disjoint union of simple closed curves). If the metric g was Riemannian with negative curvature, we would conclude directly that γ 1 = γ 2 . The following argument works for a generic Finsler metric. The homology classes of γ 1 and γ 2 may be written

[γ1] = a 1 [αi] + b 1 [βi] , [γ2] = a 2 [αi] + b 2 [βi] ,
and since γ 1 ∩ γ 2 = ∅, the absolute value of the algebraic intersection of γ 1 and γ 2 , which So the homology class maps G i on to S i ∩ H 1 (M, Z). It is injective by the genericity of (M, m). This finishes the proof of the lemma.

is |a 1 b 2 -a 2 b 1 |, is
In the following result, we refer the reader to the introduction for the definitions of B 1 (the unit ball of the stable norm, see Section 1.1), F (the closure in

H 1 (M, R) of the set {t [δ] : δ ∈ G, t ∈ [0, 1]}, see statement of Conjecture 1.
2), and (the symplectic area with respect to the intersection form, see statement of Conjecture 1.2).

Theorem 2.13. Let (M, m) be a giraffe of genus g. Furthermore assume that (M, m) is generic in the sense of Definition 2.6. Then, we have

• lim T→∞ N(T) T 2 = g i=1 (S i ∩ B 1 ), • g i=1 S i ∩ B 1 = F, • g i=1 (S i ∩ B 1 ) = (F).
So a generic giraffe of genus g verifies Conjecture 1.2.

Proof. By Lemma 2.8 we have

G = g i=1 G i , (7)
so, denoting

N i (T) = {γ ∈ G i : l m (γ ) ≤ T},
we have

N(T) = g i=1 N i (T).
by guest on [START_REF] Gromov | Structures Métriques Pour Les Variétés Riemanniennes[END_REF] On the other hand, by Lemma 2.12, for any T > 0,

N i (T) = {h ∈ S i ∩ H 1 (M, Z) : h ≤ T} = S i ∩ TB 1 .
Since the set S i ∩ B 1 is convex and the lattice S i ∩ H 1 (M, Z) has determinant 1 (because the subspace S i is symplectic), the classical Minkovski theorem says that lim

T→∞ N i (T) T 2 = (S i ∩ B 1 )
whence, by [START_REF] Kerckhoff | Ergodicity of billiard flows and quadratic differentials[END_REF],

lim T→∞ N(T) T 2 = g i=1 (S i ∩ B 1 )
which is the first statement of the theorem. Now, by [START_REF] Kerckhoff | Ergodicity of billiard flows and quadratic differentials[END_REF], F is the closure in H 1 (M, R) of the set

g i=1 t [γ ] [γ ] : γ ∈ G i , t ∈ [0, 1]
whence, by Lemma 2.12, F is the closure in H 1 (M, R) of the set

g i=1 t h h : h ∈ S i ∩ H 1 (M, Z), t ∈ [0, 1] ,
that is,

F = g i=1 S i ∩ B 1 ,
which is the second statement of the theorem.

Finally, since S i ∩ S j = {0} for any i = j, we have

g i=1 S i ∩ B 1 = g i=1 (S i ∩ B 1 ),
which is the third statement of the theorem.

In the general case-that is, when (M, m) is not a giraffe-there is no reason why homology classes of homologically minimal geodesics should be distributed into finitely many lattices of rank 2. So in the remainder of this paper what we do is look for a suitable replacement for the subspaces S i , which leads us into the next subsection. Recall that

V ( ) ⊥ = g-1 i=1 [γi] ⊥ ,
where orthogonality is meant with respect to the symplectic intersection form. The subspace V ( ) is integer, that is, it is generated by integer homology classes (elements of H 1 (M, Z)). Furthermore, the intersection form is integer, that is, for any h, h in H 1 (M, Z),

we have Int(h, h ) ∈ Z.
Therefore, in coordinates relative to an integer basis of H 1 (M, R) (i.e., a basis of H 1 (M, R) that consists of elements of H 1 (M, Z)), the equation Int([γ i] , .) = 0 is a system of linear equations with integer coefficients. Thus, the vector subspace of its solutions is generated by integer vectors. Hence, the subspace V ( ) ⊥ is integer. Now observe that since is a minimizing multicurve, its connected components are pairwise disjoint, so Int([γ i] , γ j ) = 0 for all i, j = 1, . . . , g -1. This means that

V ( ) ⊂ V ( ) ⊥ ,
thus the quotient space V ( ) ⊥ /V ( ) is well defined. Since both V ( ) and V ( ) ⊥ are integer subspaces of H 1 (M, R), the quotient group

L( ) := V ( ) ⊥ ∩ H 1 (M, Z) / (V ( ) ∩ H 1 (M, Z))
is a lattice (i.e., a discrete, cocompact additive subgroup) in V ( ) ⊥ /V ( ).

We want to prove that the intersection form quotients to a symplectic form on V ( ) ⊥ /V ( ). The kernel of the restriction of the intersection form to

V ( ) ⊥ is V ( ) ⊥ ⊥ = V ( ).
Thus the intersection form is well defined, and non-degenerate, hence symplectic, on the quotient space.

Finally, we point out that since (M, m) is generic, the homology classes

[γ1] , . . . , γ g-1 are linearly independent, so dim

V ( ) = g -1, thus dim V ( ) ⊥ = 2g - (g -1) = g + 1. Hence, dim V ( ) ⊥ /V ( ) = g + 1 -(g -1) = 2.
In short, we have proved that V ( ) ⊥ /V ( ) has dimension 2, and comes with a symplectic form and a lattice L( ), which are quotients of, respectively, the intersection form and the integer lattice.

Lemma 2.14. Let

• M be a closed, orientable, surface of genus g, equipped with a generic Finsler metric m;

• γ 1 , . . . , γ k be simple closed geodesics, such that the formal sum :

= γ 1 +• • •+γ k is a minimizing multicurve; • h 0 be [γ1] + • • • + [γk]; • h be a homology class in V ( ) ⊥ .
Then there exists a minimizing measure ν, such that [ν] = h mod V ( ), ν + μ is a minimizing measure, and supp(ν) ∩ ( , ˙ ) = ∅, where ( , ˙ ) denotes the set of tangent vectors to in the unit tangent bundle T 1 M .

Proof. By Theorem 2.3 there exists s(h 0 , h) > 0 such that the subset of the unit sphere ∂B 1

h 0 + sh ||h 0 + sh|| : s ∈ 0, s(h 0 , h)
is a straight segment. Let μ be an h 0 + sh-minimizing measure, for some 0 < s ≤ s(h 0 , h).

For each i = 1, . . . , g -1 let V i be the neighborhood of (γ i , γi ) given by Proposition 2.4. Let V be the union over i = 1, . . . , g -1 of the V i . First let us prove that V ∩ supp(μ) • is asymptotic to one of the γ i ,

• or cuts one of the γ i with constant sign.

In the second case, the minimizing geodesic cannot be in the support of any minimizing measure by Lemma 2.5. In the third case, the minimizing geodesic cannot be in the support of a minimizing measure τ such that Int([τ ] , γ i ) = 0 for i = 1, . . . , g -1, in particular it cannot be in the support of an h 0 + sh-minimizing measure, because of the Graph Property [START_REF] Mather | Action minimizing invariant measures for positive definite Lagrangian systems[END_REF] which says that the canonical projection p : TM → M, restricted to the support of a minimizing measure, is injective, and its inverse is Lipschitz.

Therefore, V ∩ supp(μ) consists of periodic orbits homotopic to some or all of the γ i . Thus it is φ t -invariant.

For any measurable subset

A of T 1 M, set α(A) := μ(A ∩ V ) β(A) := μ(A\ V ).
Then α and β are two measures on T 1 M. They are invariant by the geodesic flow because V ∩ supp(μ), as well as its complement in supp(μ), is φ t -invariant. They are both minimizing because their supports are contained in the support of a minimizing measure [START_REF] Mañé | On the minimizing measures of Lagrangian dynamical systems[END_REF]. The support of β is disjoint from ( , ˙ ) by the definition of β.

Since the support of α consists of periodic orbits homotopic to some or all of the γ i , the homology class of α is contained in V ( ). We have α+β = μ, hence [α]+[β] = h 0 +sh.

Thus,

ν := 1 s β is a minimizing measure by Lemma 2.1. Its homology is

h + 1 s (h 0 -[α]) , thus [ν] = h mod V ( ).
Moreover, since all of the γ i are contained in the support of α,α cannot be expressed as a convex combination of a proper subset of μ 1 , . . . , μ g-1 , so there exist We start by proving that μ + μ + μ is minimizing. Since h = h mod V ( ), there exist real numbers λ 1 , . . . , λ g-1 such that

h = h + λ 1 [γ1] + • • • + λ g-1 γ g-1 .
Set, for any λ ∈ ]0, 1[,

h λ := λ h 0 h 0 + (1 -λ) h h .
We have

λ h 0 h 0 + (1 -λ) h h = λ h 0 g-1 i=1 [γi] + 1 -λ h h + g-1 i=1 λ i [γi] = g-1 i=1 λ h 0 + (1 -λ)λ i h [γi] + 1 -λ h h,
so if we take λ sufficiently close to 1, h λ is a linear combination, with positive coefficients, of h, [γ1] , . . . , γ g-1 . Thus by Lemma 2.1, since these coefficients are positive, the measures ν := λ μ

h 0 + (1 -λ) μ h , ν := g-1 i=1 λ h 0 + (1 -λ)λ i h μ i + 1 -λ h μ
are both minimizing, and since their homology class is h λ , they are h λ -minimizing. Therefore ν + ν is 2h λ -minimizing. Using Lemma 2.1 again, we deduce that μ + μ + μ is minimizing.

Hence, by the Graph Property, μ + μ may be viewed as an invariant measure of a Lipschitz flow on M \ , which is homeomorphic to a torus with g -1 punctures, so μ + μ may be viewed as an invariant measure of a Lipschitz flow on T 2 . Recall from [START_REF] Katok | Introduction to the Modern Theory of Dynamical Systems[END_REF] that an invariant measure of a Lipschitz flow on T 2 is either ergodic, or supported on periodic orbits (or both, if it is supported on one periodic orbit).

First case: μ + μ is ergodic. Then either there exists a ∈ R such that μ = aμ , or there exists a ∈ R such that μ = aμ. So, either there exists a ∈ R such that h = ah , or there b i h i .

Let us take λ > 0 such that 1 -λa i > 0 and 1 -λb i > 0 ∀i = 1, . . . , g -1.

Recall that the measures μ

+ μ = μ + μ 1 + • • • + μ g-1 and μ + μ = μ + μ 1 + • • • + μ g-1
are minimizing. So by Lemma 2.1,

τ := λμ + g-1 i=1
(1 -λa i )μ i ,

τ := λμ + g-1 i=1
(1 -λb i )μ i are also minimizing. Now [τ ] = τ = h 0 , which is rational, hence by genericity τ = τ .

Let us take, for each i = 1, . . . , g -1, a neighborhood V i of (γ i , γi ) in T 1 M, such that

• V i ∩ supp(μ) = V i ∩ supp(μ ) = ∅, • V i ∩ V j = ∅ if i = j.
Then we have, for each i = 1, . . . , g -1,

τ (V i ) = (1 -λa i )μ i (V i ) = (1 -λa i )length(γ i ), τ (V i ) = (1 -λb i )μ i (V i ) = (1 -λb i )length(γ i ),
which, since τ = τ , implies a i = b i ∀i = 1, . . . , g -1, whence h = h . So the proposition is proved in the case when μ + μ is ergodic.

  that a closed geodesic γ is a connected component of some minimizing multicurve if and only if it minimizes the length in its homology class. That is, [γ ] = m (γ ), or equivalently, the homology class [γ ] / m (γ ) lies on the unit sphere ∂B 1 of the stable norm. More precisely, γ is a connected component of some minimizing multicurve if and only if the homology class [γ ] / m (γ ) is a vertex of the stable by guest on June 15, 2016 http://imrn.oxfordjournals.org/ Downloaded from On the Homology Length Spectrum of Surfaces 3 norm, that is, the unit ball has an open set of supporting hyperplanes at [γ ] / m (γ ) (see Sction 2.1 for a definition of a vertex of the stable norm).

5 •

 5 by guest on June 15, 2016 http://imrn.oxfordjournals.org/ Downloaded from On the Homology Length Spectrum of Surfaces For any non-zero element v of the quotient space [γ ] ⊥ / [γ ], there exists an edge e of B 1 starting from [γ ] / [γ ] , which projects to the straight line segment [0, λv] in [γ ] ⊥ / [γ ], for some positive λ. It might be useful for the reader to get a mental picture of the set of edges of B 1 starting from [γ ] / [γ ] . The intersection of the unit sphere ∂B 1 with [γ ] ⊥ , which has dimension 3, is topologically a two-sphere. The homology class [γ ] / [γ ] is a vertex of this topological two-sphere. There is a neighborhood

  is an endpoint of some edge starting from [γ ] / [γ ] . We can identify the quotient space [γ ] ⊥ / [γ ] with the subspace of H 1 (M, R) generated by [δ] and [β]. Then, the neighborhood E(γ ) is simply the set x [δ] + y [β] x [δ] + y [β] : x, y ∈ R which is also the unit ball of the stable norm of the torus with one hole obtained by cutting M along the short separating geodesic in the middle of the neck and discarding the left-hand side. For a general surface M there is no reason why all endpoints of edges starting from [γ ] / [γ ] should be co-planar, which is why we introduce the quotient space [γ ] ⊥ / [γ ]. Proposition 3.1 says that under some genericity assumption on the metric m, the elements of G γ are in one-to-one correspondence with the integer vectors in the vector space [γ ] ⊥ / [γ ]. Furthermore, for any L ≥ 0, the elements of G γ (L) are in one-to-one correspondence with the integer vectors in

  by guest on June 15, 2016 http://imrn.oxfordjournals.org/ Downloaded from 6 D. Massart and H. Parlier

  by guest on June 15, 2016 http://imrn.oxfordjournals.org/ Downloaded from 10 D. Massart and H. Parlier

13 Fig. 1 .

 131 Fig. 1. First case on left and second case on right.

First case:

  Assume x a and y a are on the same boundary component (say, γ 1 ) of V r (γ ). Then we have l(a) ≥ 2d(γ 1 , γ ) ≥ l(γ 1 )

Fig. 2 .

 2 Fig. 2. Different configurations of genus 5 surfaces with long thin necks.

Definition 2 . 10 .Figure 2 ,

 2102 Figure 2, we give three examples in genus 5 of different configurations.

  zero. Therefore the homology classes [γ1] and [γ2] are proportional, say [γ1] = λ [γ2] for some λ ∈ Z. Then if l m (γ 1 ) = |λ|l m (γ 1 ), replacing γ 1 by λγ 2 in γ , we find another h-minimizing multicurve, which contradicts the genericity of (M, m); by guest on June 15, 2016 http://imrn.oxfordjournals.org/ Downloaded from On the Homology Length Spectrum of Surfaces 17 and l m (γ 1 ) = |λ|l m (γ 1 ) contradicts the minimality of γ . Thus γ has only one connected component, that is, γ ∈ G i .

•

  supp(μ) ∩ ( , ˙ ) = supp(μ ) ∩ ( , ˙ ) = ∅; and • μ + μ = μ + μ 1 + • • • + μ g-1 and μ + μ = μ + μ 1 + • • • + μ g-1 are minimizing.

  by guest on June 15, 2016 http://imrn.oxfordjournals.org/Downloaded fromOn the Homology Length Spectrum of Surfaces 25 exists a ∈ R such that h = ah. By the hypothesis that h = h mod V ( ), this entails that either a = 1, or h = h = 0 mod V ( ).If a = 1, we have h = h , which proves that the canonical projectionF( ) -→ V ( ) ⊥ /V ( )is one-to-one, and thus the proposition.If h = h = 0 mod V ( ), then there exist a 1 , . . . , a g-1 , b 1 , . . . , b g-1 in R such that h =

Notations and Preliminaries 2.1 Vertices, edges, and faces of the stable norm

  We say an affine hyperplane in H 1 (M, R) is a supporting hyperplane to B 1 if it meets B 1 but not the interior of B 1 . The set of supporting hyperplanes to B 1 identifies with the unit sphere ∂B 1 of the dual stable norm on H 1 (M, R).We say a homology class h is a vertex of the stable norm if the set of supporting hyperplanes to B 1 at h is open in ∂B 1 . We say B 1 has an edge between two vertices h and h if the segment joining h to h in H 1 (M, R) is contained in the unit sphere ∂B 1 of the stable norm. Likewise, we say the stable norm has a k-dimensional face if there exist vertices h 1 , . . . , h k whose convex hull is a k-dimensional simplex contained in ∂B 1 .

	8 D. Massart and H. Parlier
	2
	Downloaded from
	http://imrn.oxfordjournals.org/
	by guest on June 15, 2016

  On the Homology Length Spectrum of Surfaces 15 the image in H 1 (M, R) of H 1 (T i , R) under the map induced by the canonical inclusion of T i into M. Beware that H i may not be isomorphic to H 1 (T i , R) if T i has more than one boundary component.

	Downloaded from
	http://imrn.oxfordjournals.org/
	by guest on June 15, 2016

Lemma 2.11. For each i = 1, . . . , g, the subspace H i contains a symplectic two-plane S i in H 1 (M, R), and

  On the Homology Length Spectrum of Surfaces 21 is φ t -invariant. Indeed by Proposition 2.4 a minimizing geodesic that enters V either

	Downloaded from
	http://imrn.oxfordjournals.org/
	by guest on June 15, 2016

• is homotopic to one of the γ i ,

by guest on June 15, 2016 http://imrn.oxfordjournals.org/ Downloaded from

Acknowledgments

The authors thank Jean Saint-Pierre for the statement of Proposition A.1. by guest on June 15, 2016 http://imrn.oxfordjournals.org/ Downloaded from On the Homology Length Spectrum of Surfaces 33

Funding

This work was partially supported by the ANR grant "Weak KAM Beyond Hamilton-Jacobi" [ANR-12-BS01-0020] to D.M. and was supported by Swiss National Science Foundation [PP00P2_128557 and PP00P2_153024] to H.P.

is a minimizing measure, so by Lemma 2.1,

is also a minimizing measure.

Still more notation: definitions of G( ) and F( )

Let

• M be a closed, orientable, surface of genus g, equipped with a generic Finsler metric m; and

• γ 1 , . . . , γ g-1 be simple closed geodesics, such that the formal sum := γ 1 +

• • • + γ g-1 is a minimizing multicurve.

We denote by

• G( ) the set of closed geodesics α, disjoint from , such that + α is a minimizing multicurve (observe that if α ∈ G( ), then nα ∈ G( ) for any n ∈ Z);

• μ i the element of M which is supported on (γ i , γi ) ⊂ T 1 M;

• F( ) the set of homology classes h of measures μ, supported outside of ( , ˙ ), such that μ + μ is a minimizing measure; and

• by F t ( ) the intersection of F( ) with the ball of the stable norm of radius t, centered at the origin. Observe that

• M is invariant under sums and scalar multiplication by a nonnegative number, that is, M is a convex cone with vertex at the zero measure;

• F( ) is invariant under scalar multiplication by a nonnegative number, that is, F( ) is a cone with vertex at the origin;

• for any α in G( ), the homology class of α lies in F( );

Therefore F( ) ⊂ V ( ) ⊥ .

Then, the canonical projection

Proof. Let h be an element of V ( ) ⊥ /V ( ). By Lemma 2.14 there exists a minimizing measure ν, such that [ν] mod V ( ) = h, supp(ν) ∩ ( , ˙ ) = ∅, and ν + μ is a minimizing measure. Then the homology class of ν, which is

which proves that the canonical projection

is on to. Now let us prove that it is one-to-one.

Take h, h in F( ) such that h = h mod V ( ), and minimizing measures μ, μ in M such that Second case: μ + μ is supported on periodic orbits. Recall that two simple closed curves on a torus which do not intersect have homology classes which are proportional, that is, one is a multiple of the other. Also recall that the homology of M \ is isomorphic to

Let us take λ > 0 such that 1 -λa i > 0, 1 -λb i > 0 ∀i = 1, . . . , g -1 and λa g ∈ Q.

Then

(1 -λa i )μ i ,

(

Proof. Take

• a sequence h n of elements of F( ), that converges to some h in H 1 (M, R); and

• for each n in N, an h n -minimizing measure μ n such that μ n +μ is minimizing,

Then, if μ is any limit point of the sequence μ n in the weak * topology, μ is h-minimizing, and μ + μ is minimizing because a limit of minimizing measure is minimizing. To prove that h ∈ F( ), it only remains to prove that

By Proposition 2.4 and Lemma 2.5, there exists a neighborhood V of ( , ˙ ) in T 1 M such that for all n in N, supp(μ n )∩V = ∅. Then for any continuous function f supported inside

Lemma 3.3. Let

• M be a closed, orientable, surface of genus g, equipped with a generic Finsler metric m;

• γ 1 , . . . , γ g-1 be simple closed geodesics such that the formal sum :

Then the canonical projection

Proof. The continuity of the canonical projection is obvious, so all we have to prove is the continuity of the inverse map. Take a sequence h n of points in V ( ) ⊥ /V ( ), which converges to some h ∈ V ( ) ⊥ /V ( ). By Proposition 3. Assume, after possibly taking a subsequence, that h n goes to infinity. Consider the sequence

Then h n ∈ F( ) by homogeneity of F( ). On the other hand, for all n, h n lies on the unit sphere of the stable norm, which is compact, so h n has a limit point h such that h = 1.

Since

, which converges to zero. By continuity of the projection, it follows that h projects to 0 ∈ V ( ) ⊥ /V ( ). But 0 ∈ H 1 (M, R) lies in F( ), and projects to 0 ∈ V ( ) ⊥ /V ( ). By the injectivity of the projection (Proposition 3.1), this entails h = 0, which contradicts h = 1. This contradiction shows that the sequence h n is bounded in H 1 (M, R).

Therefore it has limit points in H 1 (M, R). Any such limit point lies in F( ) by Lemma 3.2. By continuity of the projection, any limit point of the sequence h n projects to h. By the injectivity of the projection (Proposition 3.1), the sequence h n then converges to h , which proves the lemma.

Lemma 3.4. Let M be a closed, orientable, surface of genus g, equipped with a generic Finsler metric m and let γ 1 , . . . γ g-1 be simple closed geodesics such that the formal sum

Then the canonical projection

2, with the unit ball of the stable norm, which is compact, it turns out that F 1 ( ) is compact, and so is its projection to V ( ) ⊥ /V ( ).

Now we prove that the boundary ∂P 1 ( ) of P 1 ( ) is Lebesgue-negligible. For this we show that for any h in V ( ) ⊥ /V ( ) \ {0}, there exists a unique λ > 0 such that λh lies on ∂P 1 ( ). The Lebesgue-negligibility of ∂P 1 ( ) then follows from Fubini's theorem. Then, for any λ > 0, λh lies in F( ), and projects to λh. By Proposition 3.1, λh is the unique element of F( ) which projects to λh. Now, for λ ≤ 1 h , we have λh ∈ F 1 ( ), so λh ∈ P 1 ( ). For λ > 1 h , we have λh ∈ F 1 ( ), and since λh is the unique element of F( ) which projects to λh, it turns out that λh ∈ P 1 ( ). Thus the point 1 h h lies on ∂P 1 ( ), because it can be approximated from both inside and outside P 1 ( ). On the other hand, for any λ < 1 h , if h n is any sequence of elements of V ( ) ⊥ /V ( ) which converges to λh, denoting h n the only point of F( ) such that h n mod V ( ) = h n , by Lemma 3.3, h n converges to λh .

Recall that λ < 1

h , so λh < 1, hence for n large enough we have h n < 1. Thus, for n large enough, h n ∈ P 1 ( ), that is, λh lies in the interior of P 1 ( ) as a subset of V ( ) ⊥ /V ( ).

Therefore, λ = 1 h is the unique λ > 0 such that λh lies on ∂P 1 ( ). This finishes the proof of the lemma. Lemma 3.5. Let M be a closed, orientable, surface of genus g, equipped with a generic Finsler metric m and let γ 1 , . . . , γ g-1 be simple closed geodesics such that the formal sum

Then, the map

Proof. First let us observe that the map ψ is well defined: for any α in G( ), we have

because the metric m is generic. Therefore ψ is injective.

It remains to prove that ψ is on to. Take l in L( ). By Proposition 3.1, there exists h in F( ) such that h mod V ( ) = l. Hence, by the definition of L( ), there exists Since h ∈ F( ), we may take an h-minimizing measure μ, supported away from ( , ˙ ), such that μ + μ is minimizing. Then by Lemma 2.1, for any integer n such that n ≥ a i , i = 1, . . . , g -1, the measure

, which is integer, so by Proposition 2.2 ν is supported on closed geodesics. Thus, μ is supported on closed geodesics. Take two closed geodesics γ and γ in the support of μ. Then γ and γ are simple, non-separating closed curves on the punctured torus M \ , and by the Graph Theorem they are either disjoint or equal, so their homology classes (as curves in T 2 ) are proportional. Thus, there exist an integer homology class h g ∈ H 1 (M, Z), and integers

Reversing, if necessary, the orientations of γ and γ , we may assume that a g , b g ≥ 0.

Take N, N ∈ N such that Na g = N b g . Let Since μ+μ is minimizing, and (γ , γ ) is contained in the support of μ, τ +μ is minimizing, and so is which is an integer homology class. Therefore, since the metric m is generic, we have τ 1 = τ 2 , whence τ = τ , and γ = γ . So the h-minimizing measure μ is supported on the closed geodesic γ . Thus there exists λ ∈ R such that h = λ [γ ]. Since γ is a simple closed curve in M \ , there exists a closed curve α in M \ which intersects γ exactly once, so Int(h, [α]) = λ. We also have Int(h i , [α]) = 0 because γ lies in M \ . Since

this entails λ ∈ Z. On the other hand, since μ + μ is minimizing, we have γ ∈ G( ), so λγ ∈ G( ). Since λ [γ ] mod V ( ) = l, this proves the surjectivity of ψ .

For any t ≥ 0, denote by N (t) the number of elements of L( ) which are contained in the canonical projection of F t ( ) to V ( ) ⊥ /V ( ). Lemma 3.6. Let M be a closed, orientable, surface of genus g, equipped with a generic Finsler metric m and let γ 1 , . . . , γ g-1 be simple closed geodesics such that the formal sum

Then, for any t ≥ 0, N (t) equals the number G t ( ) of elements of G( ) of length < t.

Proof. We prove the lemma by showing that the map α →

and the subset G t ( ) of G( ) which consists of closed geodesics of length ≤t.

Conversely, take h in L( ) (F t ( ) mod V ( )). Since h ∈ L( ), by Lemma 3.5 there exists a unique α in G( ) such that [α] = h mod V ( ). Now h ∈ F t ( ) mod V ( ), so there exists h ∈ F t ( ) such that h = h mod V ( ). But Proposition 3.1 says that there exists a unique

which, by the inequality (A.7), entails

Now by the inequalities (A.3 and A.6), for each i = 1, . . . p, μ t (R i ) converges to Leb(R i ), so there exists a real number T such that for all t ≥ T, we have

Then by (A.8), for all t ≥ T, we have

which, being arbitrary, proves the convergence of μ t (C) to Leb(C), and the proposition.


Pu Hanlai

Ling Ming

Jin Jing

Extended Control Flow Graph Based Performance Optimization Using Scratch-Pad Memory *

This paper presents an exploration approach for the researcher to choose the suitable size of Scratch-Pad memory (SPM) for maximal performance improvement of a specified application. The approach uses an extended control flow graph (ECFG) to describe the application and provides a solution to reduce the additional overhead of moving nodes to SPM. Experiments achieves on average 11% increase in performance compared to the previous approaches and 44% decrease in the application's runtime compared to none SPM environment.

Introduction

As an important architectural consideration, SPM fills up the increasing gap between high frequency of embedded microprocessor cores and low access speed of off-chip memories which results in a heavy fall of chip performance. The decision about a suitable size of SPM has become an important problem in SoC design. In none cache system, the general solution tries to move the most frequently accessed parts of the application to SPM and establish the relationship between the SPM size and the application's performance. The relationship helps the researcher to choose the suitable size. This method has been adopted in all the previous researches [START_REF] Sjödin | Allocation of global data objects in on-chip ram[END_REF][3][4] [START_REF] Steinke | Assigning program and data objects to scratchpad for energy reduction[END_REF] in none cache system. To our knowledge, only Steinke et al [START_REF] Steinke | Moving program objects to scratch-pad memory for energy reduction[END_REF] analyze the instructions of the application and divides each function into several nodes according to the normal control flow graph (CFG). They adopt knapsack algorithm to select suitable nodes. Unfortunately, they ignore the relationships of nodes which have considerable influence on space utilization of SPM. The negative effect is caused by the strict limitations of addressing space of some ARM instructions [1], especially such as branch (B/BL) instruction and data-loading (LDR) instruction. Commonly, the huge address gap between SPM and off-chip memory blocks single branch instruction's free jump. It should be replaced by a macro consisting of two branch instructions and one data-loading instruction. Similarly, some data-loading instructions in SPM need additional space to save their operating address. All of these lead to an increase in size of nodes moved to SPM. However, if two related nodes are both selected, their total size is likely reduced because of the decrease in the number of long branch macros and additional space of data-loading instructions. Therefore, the neglect of the relationships of nodes must decrease the space utilization of SPM and lead to a minor decision about the SPM size.

Proposed Exploration Approach

To collect the application's runtime information, our target architecture model is built based on ARMulator (ARM7TDMI) [1], including three parts, SPM, off-chip memory (SDRAM) and instruction FIFO (IF). IF is used to fetch instructions saved in SDRAM via burst read operation. The diagram in Fig. 1 shows the work flow of our approach.

ECFG Generation

ECFG is built directly from the application's execution file and independent of input data. Besides detail information of the normal CFG node, each ECFG node gives a description of its call graph and the global data variables accessed by it. ECFG transforms the whole application into a directed graph consisting of nodes and relationships.

SPM Allocation Algorithm

A refined knapsack algorithm was adopted to solve the problem during the process of SPM allocation. The set I(i) is defined:

I(i) = {I j }, ∀ j ∈ [1, i]. If
I j = 1,
otherwise it is zero. I(0) means none is selected. P(n i+1 , I(i)) and S(n i+1 , I(i)) are the effect on runtime and size caused by moving n i+1 to SPM while some nodes has been in SPM, respectively.

The algorithm works as follows: (1) Sort all nodes descendingly by their priority, which is defined as: priority(n i ) = P(n i ,I(0)) S(n i ,I(0)) . ( 2) Check each node and calculate the total saved runtime (T P) until SPM is filled or no node is remained. The precondition of the selection is, S(n i+1 , I(i)) + T S(i) ≤ T S SPM . T S SPM is the specified SPM size.

T P(i+1) = max

T P(i) + P(n i+1 , I(i)), n i+1 is selected T P(i), otherwise

Experiment and results

In Table 1, it clearly shows that our approach achieves on average 11% increase in performance compared to the previous approaches and 44% decrease in the application's runtime compared to none SPM environment.

Fig. 2 shows that the application's runtime optimized by the previous approaches using simple knapsack algorithm is not always decreasing while the SPM size increases. The reason is that the negative effect caused by the imported instructions exceeds the obtained profit of the selected nodes. However, our approach avoids this bad situation and brings a more decrease of runtime.

Conclusions

We presents an exploration approach to decide the suitable size of SPM in SoC design. The special analysis of the relationships of nodes of the application leads to significant performance improvements compared to the previous researches.

Benchmark

Figure 1 .

 1 Figure 1. Work flow

Figure 2 .

 2 Figure 2. Dijkstra: Runtime comparison, SPM size(Byte) =128 × n, 1 ≤ n ≤ 128

This research was sponsored by National Natural Science Foundation under grant 60176018.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Tim Schattkowsky

UML 2.0 -Overview and Perspectives in SoC Design

The design productivity gap requires more efficient design methods. Software systems have faced the same challenge and seem to have mastered it with the introduction of more abstract design methods. The UML has become the standard for software systems modeling and thus the foundation of new design methods. Although the UML is defined as a general purpose modeling language, its application to hardware and hardware/software codesign is very limited. In order to successfully apply the UML at these fields, it is essential to understand its capabilities and to map it to a new domain.

Introduction

Today, electronic systems design has to cope with shortened product cycles and steadily increasing system complexity that are not yet complemented by a comparable increase in design productivity. Thus, the design productivity gap has become one of the most important problems in electronic systems design. Design methods allowing for increased abstraction as well as better reuse and integration of IPs are necessary to cope with this challenge.

The Unified Modeling Language (UML) has been successfully applied in software systems engineering as well as in some other domains. It has the capabilities to be applied to the design of hardware systems as well. This also promises an easy path to hardware/software codesign through integration with existing practice in software design. Furthermore, the notation has to be integrated with a design process to get a complete design method like in MDA. However, it is first necessary to understand, which capabilities the UML provides and how these can be employed in EDA design flows.

The Unified Modeling Language (UML)

The UML is a general purpose modeling language that marks the result of the unification of elements from three of the most significant object oriented design approaches in the later 90s. UML 1.x essentially combined elements from Booch [START_REF] Booch | Object-Oriented Analysis and Design, with Applications[END_REF], OOSE [START_REF] Jacobson | Object-Oriented Software Engineering: A Use Case Driven Approach[END_REF] and OMT [START_REF] Rumbaugh | Object-Oriented Modeling and Design[END_REF]. Furthermore, it was influenced by the ROOM method that later evolved into UML-RT [START_REF] Selic | Using UML for Modeling Complex Real-Time Systems[END_REF], a real-time profile for UML. At present, the UML 2.0 specification is on its way to finalization by the OMG. UML 2.0 includes significant enhancements in all areas. It covers 13 diagram types to describe various structural, behavioral and physical aspects of a system.

The different diagrams serve different purposes during the development process. It is important to note that the UML only provides a multi purpose notation that needs to be accompanied by a development process. This process defines the actual application variants of a particular UML diagram type.

The Package Diagrams can be used to define packages, which provide just a little more than a namespace for classes that can be composed from other packages and new classes.

Behavioral specification in the UML at the highest level often starts by the identification of the use cases for a system described in terms of involved actors. This is depicted in Use Case Diagrams. However, detailed behavioral specifications usually rely on State Machine Diagrams that represent the UML StateChart [START_REF] Harel | The STATEMATE Semantics of Statecharts[END_REF] variant and Activity Diagrams for describing control oriented behavior (e.g., in states of a State Machine Diagram). UML 2.0 introduces token semantics for these Activity Diagrams that move them semantically close to high-level Petri Nets. Furthermore, Interaction diagrams can be used to model interactions as traces of exchanged messages. These diagrams come in no less than four flavors including the Sequence Diagram, which has been extended in UML 2.0 to be comparable to an SDL Message Sequence Chart (MSC).

Finally, the Component Diagram and the Deployment Diagram can be used to describe the composition and physical deployment of a system.

Together, those diagrams can be used to provide a detailed model of a complete system at various levels of abstraction (e.g., starting from use cases down to activities describing every detail of a certain behavior).

However, the UML just provides a general notation that fits many purposes. It must be tailored to be effectively applied to a certain domain. The relevant model elements of the UML need to be identified and may be refined into a set of domain specific subtypes. This is achieved using a UML profile that defines a relevant domain-specific UML subset with semantic extensions for the supported model elements. On example for such profiles is the aforementioned UML-RT profile.

Thus, to apply UML to SoC design, it is important to define such a domain specific subset of the UML and its semantics as well as the diagram types to be used.

Model Driven Architecture (MDA)

The OMG MDA is essentially based on providing system specifications as a Platform Independent Model (PIM), which is to be more or less automatically transformed to a Platform Specific Model (PSM) for a different platform using a platform-specific mapping. This can be regarded as an enhancement to platform-based design. Both models are UML models at different levels of abstraction. The Platform Specific Model is then used for complete code generation. However, how these steps are accomplished is up to the actual MDA tool.

There already exist methods that follow the MDA approach. The Executable UML (xUML) approach [START_REF] Raistrick | Model Driven Architecture with Executable UML[END_REF] includes a complete development methodology. It is based on the Action Specification Language (ASL), which is essential as it describes notation and semantics for single actions like operation calls and assignments in UML models and thus closes the last gap to complete system specification. ASL has been integrated into the OMGadopted UML Standard for precise action semantics [START_REF]The Object Management Group: Action Semantics for the UML[END_REF] and is also used in the eXecutable and Translatable UML approach ( X T UML) which has been developed by Project Technology based on Mellor's approach to executable UML [START_REF] Mellor | Executable UML -A Foundation for Model-Driven Architecture[END_REF]. Both approaches use code generators to produce the actual implementations from the UML models. However, the application of such code generation for hardware descriptions still needs to be demonstrated.

Perspectives for SoC Design

The UML is quite appealing for application in hardware design, as digital hardware and software have quite a lot in common. At a reasonable level of abstraction, both already have similar structural (e.g., software components and IP cores) and behavioral models (e.g., StateCharts, Petri Nets). Application of UML to hardware systems promises to close the design gap between hardware and software systems by providing inherent interfaces that should lead to full interchangeability between hardware and software. Furthermore, the early prototyping and inherent software simulation capabilities of such an approach are appealing, as they promise cost and time savings. Finally, the application of the MDA concept also to hardware finally promises large scale reuse and portability.

However, while the UML is by definition a general purpose modeling language, it cannot be instantly applied to hardware design. As it is just a notation, meaning must be given to all the relevant language elements. It is necessary to the tailor the UML in a way that the domain specific significant requirements like seamless integration of existing IP can be met.

Thus, the real world things that need to be represented have to be identified and consistently put into the right context as UML model elements. The relation between the concepts used in the UML and real circuits has to be clarified. For example, the notion of class, object and component have to be aligned in this context and the structural semantics of operations need to be defined.

Furthermore, the application of the different diagrams in the design process needs to be clarified. Many ideas can be derived from the existing methods for software and hardware design. In the context of MDA, the integration with a design process can be achieved.

  Class Diagram is probably the most well known diagram. It describes structural aspects of a system in terms of classes and associations between those classes. A class may have attributes and operations. Furthermore, interfaces and generalizations can be used to create object oriented type hierarchies. Instances of a Class Diagram are called an Object Diagram and describe how individual class instances (objects) are related.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE