Eric Petit
email: eric.petit@uvsq.fr

Pablo De Oliveira Castro

Tarek Menouer

Bettina Krammer

William Jalby

Computing-Kernels Performance Prediction Using data flow Analysis and Microbenchmarking

Keywords: Performance analysis, Performance prediction, Dataflow, Microbenchmarking

On modern multi-core processors, the growing gap between memory size, bandwidth and latency compared to computing capability makes the memory hierarchy predominant for performance. The Microkernel-Description-Language based Performance Evaluation Framework, MDL-PEF, accurately predicts optimized inner-loops performance depending on the loop's data access. The MDL-PEF approach revolves around a data flow description language, MDL. A static analysis step extracts the data flow structures of the assembly code. Then the predictor uses pattern matching against an MDL-Microkernel database for predicting performance. Finally, MDL-PEF provides an automatic tool to initialize a pattern matching database for the target architecture. The overall system can predict the kernel performance on different platforms and optimizations, helping the user choose the best architecture for a given kernel. Preliminary experiments, with a 56 elements database, predict the innermost loop throughput of 636 binary loops of the NAS benchmarks with an average 10% of relative error. The performance predictor is part of the Modular Assembly Quality Analyzer and Optimizer (MAQAO) performance tool framework. Future works will extend MDL-PEF to other architecture paradigms and more complex control flows such as outer loops.

Introduction

New architectures use an increasing number of cores, more complex hardware mechanisms for performance, and wider memory hierarchy. The growing complexity of the system makes their performance fuzzier, to the extent where building accurate analytical models is not possible anymore. Furthermore, to build empirical models, exhaustive approaches are not realistic.

Manual or compiler optimizations require a cost model and performance analyzer to drive the process. Cost models predict where to apply the optimizations and their potential efficiency; performance analysis quantifies their impact. Optimizing is a costly and error prone iterative-process which must converge as fast as possible. Therefore, both the performance model and analysis need to be accurate.

To tackle the emerging challenge of performance analysis on complex manycore systems, we propose a new approach based on micro-benchmarking and pattern matching. To be more precise, the remainder of the article will use the three following definitions:

-MDL-Kernel: code snippet abstraction from an external application and candidate for matching against micro-kernels (µKernels), -µKernel : atomic element of an MDL-Kernel representing a single connected dependency graph, -Micro-benchmark: machine specific code fragment instantiating a particular µKernel which MDL-PEF benchmarks to build the matching database.

Since the gap between memory and flops bandwidth in modern architectures is getting wider and wider, we base our approach on the following assumption: memory access patterns dominate performance when the accessed memory is far from the CPU. Therefore, at the core of the MDL-PEF framework is a data flow description language, MDL, which models memory access performance. The framework addresses three different issues:

1. Code abstraction: An application's code snippet is broken down into a set of independent µKernels. Each µKernel conveys the data flow and arithmetic intensity characteristics of a small code segment. 2. Pattern matching: MDL-PEF matches newly extracted µKernels against a database of existing µKernels with known performance. By identifying similar µKernels in the database it predicts the performance. 3. Micro-Benchmark code generation: To initialize the database, MDL-PEF measures a set of seed µKernels on different platforms and execution contexts. From each abstract MDL kernel, MDL-PEF generates many concrete machine specific binaries, called micro-benchmarks. Instantiated microbenchmarks have explicit addressing, operations, loop trip, and scheduling.

New hardware or software developments provide new optimization opportunities and can make older design choices obsolete or even counter productive, especially when dealing with legacy applications, in HPC or in embedded systems. In this context, MDL-PEF is useful in two ways:

1. Code optimization (a) Performance debugging: an application segment's performance being far from what is expected is a performance bug. MDL-PEF spots performance bugs by predicting the expected performance of the kernel and comparing it to the measured performance. (b) Identify code segments with high potential for optimization: MDL-PEF can predict when it is possible to perform the same data flow pattern with better performance. Examples include using a different architecture or applying new optimizations: unrolling, blocking, loop splitting, loop interchange, etc. MDF-PEF measures the potential return on investment of the proposed optimizations. 2. Hardware-software co-design either in HPC or embedded systems (a) Extract from a whole application the set of abstract µKernels used in loops: Instead of executing the whole application, MDL-PEF benchmarks and tunes the loops one by one. (b) Help tune the optimizing compiler on the target system while determining the best performing optimizations and their parameters on a set of representative benchmarks.

The remainder of this article is organized as follows. Section 2 presents related works. Section 3 details the design of MDL-PEF: it describes the MDL grammar, how to extract the MDL representation of a code segment, and how to use pattern matching on MDL. Section 4 exposes the specific algorithms used for implementing micro-benchmarks code generation during the µKernel concretization step. Section 5 presents first experiments, with a case study and preliminary results on NAS parallel benchmarks. Section 6 concludes and gives an outlook on future works.

Related Works

There are two main families of performance analysis tools: dynamic and static ones. Dynamic analysis tools, like gprof [START_REF] Graham | gprof: a call graph execution profiler[END_REF], Scalasca [START_REF] Geimer | The Scalasca performance toolset architecture[END_REF], TAU [START_REF] Shende | The Tau Parallel Performance System[END_REF], Intel Vtune, or Likwid [START_REF] Treibig | Likwid: A lightweight performance-oriented tool suite for x86 multicore environments[END_REF], analyze the live execution of a program, based on the execution trace or hardware-counter-based profile, and help users spot the performance bottlenecks. Their results are deeply linked to compiler, execution context, system, and processor. They perform on-site specific code quality measurement, optimizations and hotspots detection. Other dynamic tools, like Perpi [START_REF] Goossens | Performance Evaluation of Core Numerical Algorithms: A Tool to Measure Instruction Level Parallelism[END_REF] or Acumem [START_REF] Eklov | Fast modeling of shared caches in multicore systems[END_REF], are independent of the target system since they use architectureindependent interpretation models of the trace.

Static analysis tools, like MAQAO [START_REF] Djoudi | Exploring application performance: a new tool for a static/dynamic approach[END_REF], Salto [START_REF] Rohou | SALTO : System for Assembly-Language Transformation and Optimization[END_REF] or Intel IACA, determine the potential lower-bound of application performance based on a static model. They compute their output with various metrics such as estimated floating-point operation count, estimated data flow analysis, estimated number of live variables, register count, etc. The static tools are language and compiler dependent. They are useful for analyzing and optimizing the code quality produced by a compiler.

MDL-PEF uses fine grain static analysis based on the MAQAO [START_REF] Djoudi | Exploring application performance: a new tool for a static/dynamic approach[END_REF] framework to construct the MDL-Kernels and it optionally uses the dynamic profile to specialize the prediction context. The basic usage helps to determine and quantify the potential optimizations to apply at loop level. Furthermore, during the abstraction process, it extracts new static metrics about the code characteristic and the compiler work quality.

All optimization work starts with the kernel-to-optimize detection and extraction. ASTEX [START_REF] Petit | ASTEX: a hot path based thread extractor for distributed memory system on a chip[END_REF] is an existing source-level approach based on application instrumentation and profiling. Avoiding full-scale application execution is a necessity to make iterative optimization possible. The objective is to specialize the code generation and optimization for the hotspot using complex and costly approaches. MDL-PEF offers such a possibility with MDL concretization and replay in the micro-benchmark framework. Since the MDL-PEF replay the compiler-optimized kernel, it does not influence the process from the source code to the optimized binary. Contrary to ASTEX, MDL-PEF does not yet capture the real application working-set.

The finality of performance analysis is performance optimization. The collected metrics and performance properties need a translation into hardware or software optimizations. Performance prediction and cost model can help to explore the design space, as done in SPIRAL [START_REF] Pushel | SPIRAL: Code generation for DSP transforms[END_REF] for signal applications.

Some approaches base their predictions on a theoretical and empirical model. For instance, the Acumem Threadspotter [START_REF] Eklov | Fast modeling of shared caches in multicore systems[END_REF] tool varies the cache parameters, such as associativity and size. By replaying the sample trace with new parameters, it characterizes the cache effect in single and multi-core execution.

Other approaches use an adaptive model based on machine learning, collecting data from experiments and predicting the set of design properties based on similarities with known results. GCC milepost [START_REF] Fursin | Milepost GCC: Machine Learning Enabled Self-tuning Compiler[END_REF], for instance, measures the relation between compiler flags and performance for several codes. Based on syntactic similarities, it predicts the flags to use for a new input. Its drawback is to be a blind optimizer: it optimizes, but does not explain why the optimizations are successful.

MDL-PEF explores both approaches, respectively for performance prediction and affinity between architecture and kernel. Contrary to GCC milepost [START_REF] Fursin | Milepost GCC: Machine Learning Enabled Self-tuning Compiler[END_REF], and similarly to XARK [START_REF] Arenaz | XARK: An extensible framework for automatic recognition of computational kernels[END_REF], the MDL-PEF metrics computation and pattern matching approach is based on semantic features, mostly related to polyhedral model. Thanks to code abstraction, MDL-PEF uses a reduced database of microbenchmarks compared to [START_REF] Fursin | Milepost GCC: Machine Learning Enabled Self-tuning Compiler[END_REF]. Therefore, there is no large system requirement and the MDL-PEF pattern matching is much cheaper.

Design of MDL-PEF

This section describes the Microkernel Description Language Performance Evaluation Framework. Figure 1 represents a schematic view of the framework. The figure can be read from two different points of view:

1. Daily user : the framework's input is an application code snippet. The framework abstracts the input into the MDL language, described in section 3.1.

Then it refines the raw MDL description to its canonical form using the algorithm of section 4.1. The canonical MDL form is then matched against the MDL-µKernels database using the k-NN algorithm of section 4.2. The framework predicts the best performance and the best optimization using the information from the closest neighbors. The two previous utilizations are grouped in one single framework presenting two concepts: the MDL language described in section 3.1 and the framework, PEF, described in section 4.

Microkernel Description Language

The intuition behind MDL's abstraction is that, whatever the implementation of a kernel is, it will always use the same number of input and output data flows to compute a result-element. For instance, a Finite Impulse Response (FIR) filter is composed of one input data flow, reading N elements backwards, and one output data flow writing one output element. The description does not change after applying compiler optimizations. What makes a difference for the stencil, with unrolling for instance, is the flop/byte metrics. Thus, MDL description language focuses on the access pattern and arithmetic intensity description.

The following guidelines lead the MDL design:

-The abstraction should allow efficient pattern matching and be abstract enough so that similar programs share the same MDL representation. In addition, the number of MDL seeds in the database should be reduced to the minimum to reduce matching complexity. Therefore, complex patterns should be broken into combinations of simpler patterns using the same memory stream. -The language should be architecture independent. A machine description file is used at the concretization step to produce micro-benchmarks. This file hides the architecture specifics, such as Instruction Set Architecture's (ISA), type sizing, register mapping, from the MDL abstraction.

MDL Kernel Description

An MDL-kernel description is composed of three parts: meta-data, data and body.

The meta-data part describes all the associated metrics embodied in the MDL description, but not related to the abstract data flow pattern. It captures information specific to the original code implementation of the kernel such as unrolling factor, spill-fill, loop bounds, and array physical addresses. The metrics are produced either by the static analysis, a dynamic profiling, or any external tool.

The data section contains the set of variables describing the working set of the benchmark code such as memory streams identifier, strides value, offsets value, and immediate values.

Finally, the body describes the abstract data flow accesses of the kernel and the arithmetic intensity. The full grammar of the body follows: The terminal elements of the grammar are of two kinds: integer immediate values and identifiers for flow and scalar parameters declared in the data section.

The body description starts with the outermost loops expression. For each loop level, the description contains a loop trip count variable and the list of the polyhedric expression of the in and out accesses. They are computed from the current level code and the lower-level loop-components in and out expression. Then, it contains a list of the next level loop. The inner loop description is the lowest loop level; it contains a list of µKernels instead of a lower loop-level list. Each µKernel is built from memory accesses description and arithmetic characterization. Currently, we only consider the arithmetic intensity for addition and multiplication. The current assembly abstraction is limited to the innermost loop expression. We are also not considering indirect accesses, conditional branching, and irreducible loops. Since our first target result is the asymptotic innermost and branch-free loop body throughput prediction for MAQAO [START_REF] Djoudi | Exploring application performance: a new tool for a static/dynamic approach[END_REF] in L2, L3, and RAM memory level, the current limitations have no significant impact.

Implementation of MDL-PEF

This section describes the PEF prototype implementing the pattern matching and replay features. As described before, the PEF pipeline has three steps: normalization of the µKernels to their canonical form, pattern matching and concretization of the µKernels for replay.

MDL-Kernel Construction and Normalization

Figure 2 shows the full MDL-kernel construction from the asssembly and normalization process. It removes ISA artificial limitations to get a canonical data flow representation which assumes an unlimited number of registers, arbitrarily large memory moves, and is identical for different unroll factors. First, MDL-PEF renames registers assuming a virtual infinite number of registers and removes obsolete spill-fill code abstracting the code from any register pressure impact. During this process, to clearly separate the memory and arithmetic streams, the instructions combining arithmetic and memory access, are fissed.

Then the modified assembly code segment is broken into elementary and independent µKernels. Compiler unrolled code makes this process difficult, because unrolling factorizes instructions from different iterations. To reconstruct the original instruction stream, all the factorized memory accesses are fissed. After this process, every connected sub-graph of the Data Dependency Graph (DDG) represents a separate computation segment and Tarjan's connected components algorithm [START_REF] Tarjan | Depth-first search and linear graph algorithms[END_REF] extracts the set of µKernels.

Next, memory coalescing abstracts the access instruction size limitations of the ISA, by fusing contiguous memory accesses. The MDL language considers an ideal memory access with arbitrarily large memory stores or loads. The final step is re-rolling. µKernels that are unrolled instances of the same code segment will have a unique canonical representation after this step.

Normalization removes ISA and compiler side effects from the MDL representation, to avoid hindering the pattern matching with such effects. During the whole process, PEF extracts related static metrics for each µKernel: the unrollfactor, the spill-fill, the flop per byte and the ADD per MUL ratio.

MDL Pattern Matching

The MDL-PEF approach for pattern matching is based on the k-Nearest -Neighbor [START_REF] Cover | Nearest neighbor pattern classification[END_REF], k-NN, algorithm. The µKernel studied and each seed in the database are tagged with a feature vector. In the MDL context, feature vectors are built from five metrics: the load per stream, the store per stream, the number of streams, the ADD number, and the MUL number. In Section 5 we will show empirically that these metrics work well for the Nehalem x86 architecture. More complex feature vectors capturing the structural matches between different data flows will be studied in future. The algorithm finds the closest k seeds to the studied µKernel and predicts its performance by combining the closest seeds' performance. We iteratively apply the following algorithm: find the closest neighbor, scale it to minimize the distance, add the scaled performance to the accumulator, substract (saturated arithmetic) the scaled feature from the target vector, loop until target vector is null. Then the algorithm searches for next order performance prediction. Therefore, the closest neighbor has the higher impact on the result.

The k-NN approach works well when predicting a single µKernel's performance. In cases where multiple µKernels interact, it is not clear how to combine their individual predictions for the whole application's performance prediction. The problem is difficult because multiple µKernels performance is rarely additive [START_REF] Jalby | Measuring computer performance[END_REF]. Indeed, an out-of-order machine can overlap the work as long as the superscalar resources are not saturated and the access overhead in higher memory hierarchy benefits from the pipelining effect.

MDL Concretization: x86 Binary Generation

Concretization produces many binary versions from a single MDL seed to explore performance and optimization trade-offs. Concretization can be used in two ways:

1. Replay mode: Replay a specific µKernel with different parameters to precisely explore performance trade-offs. 2. Populate the database with performance and optimization information: Concretization can help explore the unroll factor, best amount of thread-parallelism, most efficient blocking size, etc.

The database concretization should provide accurate lower-bound throughput performance to reveal the optimization potential, whereas the replay concretization must measure real performance accurately. Therefore the replay does not normalize the µKernel to preserve the original code dependencies, aliases and alignment issues. Concretization is performed in three stages:

1. Choose assembly instructions to execute the kernel. For memory instructions, the selection policy is to maximize vector-load instructions, to produce quality vectorized code. For arithmetic instructions, current Intel x86 Nehalem architectures are able to dispatch one vectorized ADD and MUL per cycle. By avoiding clusters of ADD and MUL instructions, Algorithm 1 produces balanced schedules which maximize Instruction-Level Parallelism (ILP). 2. Schedule memory and arithmetic instructions streams together. Algorithm 2 ensures that flow dependencies between memory and arithmetic are satisfied. Therefore, each bundle is composed of a load section, an arithmetic section, and a final store section. The bundle scheduling granularity can be tuned with the nb bundles parameter in algorithm 2. The coarsest granularity is composed of only one large bundle; the finest granularity is composed of small interleaved bundles. The scheduler is able to produce all the intermediate granularity schedulings. Figure 3 shows schedules of different granularities, from one to three bundles. 3. Allocate the physical registers. Algorithm 3 is our register allocator. It is a modified round robin register allocation which minimizes registers' dependencies and maximizes the distance between definition and store in the same register. It is important to note the register allocator breaks the semantics of the original kernel assembly to be as performance-neutral as possible during the allocation. MDL's register allocation allows studying the performance of a code without worrying about register dependencies slow-downs.

Finally, MDL sends the assembly produced to an external tool, the Micro-Tools framework, which handles memory allocation, initialization, time measurement and the loop trip count.

Preliminary Experiments

This section presents preliminary experiments validating the MDL-PEF concept and prototype implementation. Section 5.1 explores the characterization of the OpenMP NAS 3.0 and the MDL database. It shows that the feature vector's distribution in the database is compatible with the feature vector's distribution in the OpenMP NAS 3.0 benchmarks [START_REF] Bailey | The NAS Parallel Benchmarks[END_REF].

Section 5.2 analyses PEF's prediction accuracy on NAS benchmarks. The section focuses on lower-bound performance estimation and across-architecture performance prediction.

Database Generation

The prototype database contains 56 seed µKernels distributed as follows: -36 memory-only µKernels: six of them are the single stream memory kernels which are shipped inside MAQAO. The remaining thirty are synthetic kernels generated by all the combinations of loads and stores with a maximum of 8 loads and 4 stores. -20 Numerical Recipes µKernels: ten of the µKernels are synthetic memoryarithmetics µKernels whose memory/arithmetic, load/store and add/mul ratios are representative of the Numerical Recipes benchmarks. The other ten seeds are extracted from long, vectorized kernels from the Numerical Recipes benchmarks [START_REF] Press | Numerical recipes[END_REF].

The right part of figure 4 presents the database load/store and flop/byte distributions. The left part presents the same distributions for all the vectorized floating point µKernels extracted from the NAS benchmarks.

The database distribution range for store over load ratio is close to the NAS distribution range: less than 5% of the NAS µKernels are outside the database distribution bounds. In the NAS benchmarks, balanced load-store kernels predominate. Therefore, the future base extension will have a particular focus on those configurations. Database and NAS arithmetic distributions are very close up to 0.8. For higher intensity, we rely on the scaling step of the pattern matching. Indeed, the database focus is mainly on memory-only seeds since we assume memory access cost predominates. However, to reduce the scaling factor, a future MDL database should explore larger arithmetic intensity bound.

Comparing the database and NAS distributions shows no large discrepancy. Therefore, we conclude that the current database correctly captures the features of the studied NAS benchmarks and it can be used to predict NAS performance.

Performance Replay and Prediction

The first case study is based on an industrial Gauss filter kernel implementation. Figure 5 compares the loop throughput in cycles and time per iteration of the MDL replay and the real code execution for different array sizes and architectures. The test architecture are: an Intel Xeon L5609@1.87GHz, an Intel Xeon E5620@2.40GHz and an Intel Core i5 M560@2.67GHz. The mean relative error in replay is 8.66% and the absolute error average is 2.28 cycles. When comparing performance across architectures, cycles per iteration throughput is a misleading metrics. Indeed, the number of cycles is not a time measure. When dividing by the frequency, the time in L1 and L2 appear to be proportional to the frequency, weheras in L3 there is no gain by moving from 2.40 to 2.67GHz, and in RAM the Xeon E5620 is clearly the fastest architecture for this code. Therefore, the user can save energy and money by choosing the best fitting architecture for an application.

The larger prediction experiment is based on the NAS benchmarks. MDL-PEF identifies 1499 FP-SSE loops in the eight benchmarks of the NAS suite. Since MDL-PEF predicts the perfectly vectorized bottom performance of the loop, the accuracy measurement of the prediction has to be checked against the vectorized FP-SSE loop. It represents 956 loops from the original set, among which 636 run with the current extraction and replay engine. Figure 6 presents the results on the 636 loops for two different architectures: a Nehalem Intel Xeon L5609@1.87GHz and a Xeon E5620@2.40GHz. The four lines present respectively L1, L2, L3, and RAM predictions. The whisker representation shows the relative error of the MDL prediction against the real loop in single thread execution. Each box is bounded by the first and third quantile value, with the bar inside each box being the median value. In L1 the median is very close to the first quantile value.

In this experiment, MDL-PEF used the database described in section 5.1. The real execution time was measured by running the original assembly through MicroTools:

-Base registers were rewritten with the adresses of the MicroTools allocated arrays. -Indirect access loops, large offset access and loops using more than 7 distinct memory streams were blacklisted. -The current approach does not consider aliasing, therefore two different baseaddress registers are always considered as different streams.

The average relative error of the prediction is presented in array 6c. For unrolled and very large kernels, results are worse because of the performance nonadditivity issues described in section 4.2. One should notice that the prediction is q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q bt cg ep ft is lu mg sp q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q bt cg ep Fig. 6: Performance prediction relative error to real measurement sequence on the 636 loops extracted from the NAS benchmarks. The left plot is on an Intel Xeon L5609@1.87GHz, the right one on an Intel Xeon E5620@2.40GHz much more accurate in L1 and RAM. L2 and L3 predictions are unstable mostly because the pattern matching algorithm does not yet deal with stride iand offset matching. To overcome this problem we have to consider using data-mining to explore all the concretization parameters more extensively.

From our experiments, we conclude that the first objective to replace the MAQAO performance predictor by a new extensible framework is reached. Future developments on the inner loop throughput prediction will have to exploit a more advanced model for performance combination of µKernels, and explore more unroll and stride parameters.

Conclusion and Future Works

This paper presents the MDL-PEF concept and its early prototype. The first implementation focus is setting the software stack of MDL-PEF.

The first step converts an x86 assembly kernel to its MDL description. Then MDL-PEF simplifies the kernel using memory access coalescing, spill-fill removal, and renaming. The final step splits the kernel in µKernels and refolds the unrolled one. MDL-PEF matches each µKernel with the closest seeds of the database and combines their predicted performance to predict the kernel throughput.

The current implementation of MDL-PEF predicts the performance of a set of 1499 inner-loops extracted from the NAS benchmarks. The prediction average relative error over the 636 studied vectorized loops is 10%. In addition, MDL-PEF enables early exploration of the impact of the unroll factor and instruction scheduling using multiple MDL kernels. To improve the current model, we identify three priority actions.

MDL represents a kernel as a data flow abstraction of the memory accesses decorated with arithmetic intensity information. Despite MDL's architecture independent representation, the MDL construction and refinement process is not ISA agnostic. To tackle this problem we propose to use an intermediate representation (IR) assembly in MDL, such as KIMPLE [START_REF] Benoit | Kimble: a Hierarchical Intermediate Representation for Multi-Grain Parallelism[END_REF] or GIMPLE [START_REF] Merrill | Generic and GIMPLE: A new tree representation for entire functions[END_REF]. The low level IR will enable more accurate replays and facilitate interfacing MDL with new ISA.

Performance is not additive. The performance predictor needs to model more precisely the interactions among µKernels on the target architecture.

Lastly, to enhance the accuracy of the pattern matching and the replay, we are exploring the MAQAO binary instrumentation for value profiling. It makes the execution context determinate and allows the extension of metric-quantification to loop-nests.

To conclude, the current development and experiments clearly validate the interest of our concept. With the future software and model extension and large experimental validation, MDL-PEF will be a great complement to existing tools.

2 .Fig. 1 :

 21 Fig. 1: The MDL-PEF organization

  loop ::= outer loop | inner loop outer loop ::= 'Trip:'. expr .'I/O:'. InOut .'LoopBody:'.( flow binding )*. loop ) inner loop ::= 'Trip:'. expr .'I/O:'. InOut .'LoopBody:'. ukernels . InOut ::= 'In:' ( flow . expr .)* . 'Out:' ( flow . expr )* flow binding ::= fixed | strided | switch fixed ::= 'fixed ' flow strided ::= 'strided '. flow . expr switch ::= 'switch'. flow .'in'. flow * expr ::= ( value |'('. expr .')').(('+'|'-'|'*'|'mod'|'div').( value |'('. expr .')'))* ukernels ::= ukernel * ukernel ::= mem access *. arith mem access ::= ( flow .'Stride:'. value .'Offset:'. value .'Size:'. value )* arith ::= ('Add:'. value .'Mul:'. value ) | AST flow ::= stream identifier value ::= integer | scalar identifier

Fig. 3 :

 3 Fig. 3: x86 code generation pipeline

Fig. 4 :

 4 Fig. 4: NAS FP-SSE loops and MDL prototype database profiles.

Fig. 5 :

 5 Fig. 5: MDL replay of the Gauss filter on multiple architecture and input datasize.

  Require: int nb add , nb mul nb f op ← nb mul + nb add minop ← min(nb mul , nb add ) if minop = 0 then ratio ← nb f op ÷ minop ratio mul ← ratio add ← 1 if nb mul ≥ nb add then ratio mul ← ratio else ratio add ← ratio end if while nb mul and nb add do print ratio mul * mul print ratio add * add nb mul ← nb mul -ratio mul nb add ← nb add -ratio add end while end if print nb mul * mul + nb add * add Algorithm 1: Arith pre sched Require: D bundle , n load , nstore, n add , n mul f op list ← Arith -pre -sched(nb add , nbstore) N bundle ← min(D bundle , n load , nstore, n add + n mul ) n f op per bundle ← f op/N bundle n load per bundle ← n load /N bundle n store per bundle ← nstore/N bundle while i < N b bundle -1 do print N load per bundle * load print N f op per bundle * get line(f op list ) print N store per bundle * store end while print (n load -n load per bundle * n bundle ) * load print (n f op -n f op per bundle * n bundle ) * get line(f op list ) print (nstore -n store per bundle * n bundle ) * store

		Algorithm 2: LSA sched
	Require: Stream input
	lastreg = -1
	reg last def [7] = 0
	while curr line == input.getLine() do
	if isLoad(curr line ) then
	lastreg = (lastreg + 1)%8
	insert load(lastreg)
	reg last def [lastreg] = curr line .id
	else if isArith(curr line ) then
	f irstreg = (lastreg + 1)%8
	lastreg = (lastreg + 2)%8
	insert arith(f irstreg, lastreg)
	reg last def [lastreg] = curr line .id
	else if isStore(curr line ) then	Register Neutral_alloc()
	lastreg = search older(reg last def )
	insert store(lastreg) end if end while	Output x86 Assembly
	Algorithm 3: Neutral alloc

Acknowledgements

This work done at LRC-ITACA/UVSQ is funded by the ITEA2-H4H project. The authors thank ECR and the MicroTools development team for their support.


Enrique Henestroza Anguiano
email: enrique.henestrozaanguiano@inria.fr

Marie Candito Alpage

Probabilistic Lexical Generalization for French Dependency Parsing

This paper investigates the impact on French dependency parsing of lexical generalization methods beyond lemmatization and morphological analysis. A distributional thesaurus is created from a large text corpus and used for distributional clustering and WordNet automatic sense ranking. The standard approach for lexical generalization in parsing is to map a word to a single generalized class, either replacing the word with the class or adding a new feature for the class. We use a richer framework that allows for probabilistic generalization, with a word represented as a probability distribution over a space of generalized classes: lemmas, clusters, or synsets. Probabilistic lexical information is introduced into parser feature vectors by modifying the weights of lexical features. We obtain improvements in parsing accuracy with some lexical generalization configurations in experiments run on the French Treebank and two out-of-domain treebanks, with slightly better performance for the probabilistic lexical generalization approach compared to the standard single-mapping approach.

Introduction

In statistical, data-driven approaches to natural language syntactic parsing, a central problem is that of accurately modeling lexical relationships from potentially sparse counts within a training corpus. Our particular interests are centered on reducing lexical data sparseness for linear classification approaches for dependency parsing. In these approaches, linear models operate over feature vectors that generally represent syntactic structure within a sentence, and feature templates are defined in part over the word forms of one or more tokens in a sentence. Because treebanks used for training are often small, lexical features may appear relatively infrequently during training, especially for languages with richer morphology than English. This may, in turn, impede the parsing model's ability to generalize well outside of its training set with respect to lexical features.

Past approaches for achieving lexical generalization in dependency parsing have used WordNet semantic senses in parsing experiments for English (Agirre et al., 2011), and word clustering over large corpora in parsing experiments for English [START_REF] Koo | Simple semisupervised dependency parsing[END_REF] as well as for French (Candito et al., 2010b). These approaches map each word to a single corresponding generalized class (synset or cluster), and integrate generalized classes into parsing models in one of two ways: (i) the replacement strategy, where each word form is simply replaced with a corresponding generalized class; (ii) a strategy where an additional feature is created for the corresponding generalized class.

Our contribution in this paper is applying probabilistic lexical generalization, a richer framework for lexical generalization, to dependency parsing. Each word form is represented as a categorical distribution over a lexical target space of generalized classes, for which we consider the spaces of lemmas, synsets, and clusters. The standard single-mapping approach from previous work can be seen as a subcase: each categorical distribution assigns a probability of 1 to a single generalized class. The method we use for introducing probabilistic information into a feature vector is based on that used by Bunescu (2008), who tested the use of probabilistic part-ofspeech (POS) tags through an NLP pipeline.

In this paper, we perform experiments for French that use the replacement strategy for integrating generalized classes into parsing models, comparing the single-mapping approach for lexical generalization with our probabilistic lexical generalization approach. In doing so, we provide first results on the application to French parsing of WordNet automatic sense ranking (ASR), using the method of [START_REF] Mccarthy | Finding predominant word senses in untagged text[END_REF]. For clustering we deviate from most previous work, which has integrated Brown clusters (Brown et al., 1992) into parsing models, and instead use distributional lexical semantics to create both a distributional thesaurus -for probabilistic generalization in the lemma space and ASR calculationand to perform hierarchical agglomerative clustering (HAC). Though unlexicalized syntactic HAC clustering has been used to improve English dependency parsing [START_REF] Sagae | Clustering words by syntactic similarity improves dependency parsing of predicate-argument structures[END_REF], we provide first results on using distributional lexical semantics for French parsing. We also include an out-of-domain evaluation on medical and parliamentary text in addition to an in-domain evaluation.

In Section 2 we describe the lexical target spaces used in this paper, as well as the method of integrating probabilistic lexical information into a feature vector for classification. In Section 3 we discuss dependency structure and transition-based parsing. In Section 4 we present the experimental setup, which includes our parser implementation, the construction of our probabilistic lexical resources, and evaluation settings. We report parsing results both in-domain and out-of-domain in Section 5, we provide a summary of related work in Section 6, and we conclude in Section 7.

Probabilistic Lexical Target Spaces

Using terms from probability theory, we define a lexical target space as a sample space Ω over which a categorical distribution is defined for each lexical item in a given source vocabulary. Because we are working with French, a language with relatively rich morphology, we use lemmas as the base lexical items in our source vocabulary. The outcomes contained in a sample space represent generalized classes in a target vocabulary. In this paper we consider three possible target vocabularies, with corresponding sample spaces: Ω l for lemmas, Ω s for synsets, and Ω c for clusters.

Ω l Lemma Space

In the case of the lemma space, the source and target vocabularies are the same. To define an appropriate categorical distribution for each lemma, one where the possible outcomes also correspond to lemmas, we use a distributional thesaurus that provides similarity scores for pairs of lemmas. Such a thesaurus can be viewed as a similarity function D(x, y), where x, y ∈ V and V is the vocabulary for both the source and target spaces.

The simplest way to define a categorical distribution over Ω l , for a lemma x ∈ V , would be to use the following probability mass function p x :

px(y) = D(x, y) y ′ ∈V D(x, y ′ ) (1)
One complication is the identity similarity D(x, x): although it can be set equal to 1 (or the similarity given by the thesaurus, if one is provided), we choose to assign a pre-specified probability mass m to the identity lemma, with the remaining mass used for generalization across other lemmas. Additionally, in order to account for noise in the thesaurus, we restrict each categorical distribution to a lemma's k-nearest neighbors. The probability mass function p x over the space Ω l that we use in this paper is finally as follows:

px(y) =                    m, if y = x (1-m)D(x, y) y ′ ∈Nx(k) D(x, y ′ ) , if y ∈ Nx(k) 0, otherwise (2)

Ω s Synset Space

In the case of the synset space, the target vacabulary contains synsets from the Princeton WordNet sense hierarchy [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF]. To define an appropriate categorical distribution over synsets for each lemma x in our source vocabulary, we first use the WordNet resource to identify the set S x of different senses of x. We then use a distributional thesaurus to perform ASR, which determines the prevalence with respect to x of each sense s ∈ S x , following the approach of [START_REF] Mccarthy | Finding predominant word senses in untagged text[END_REF]. Representing the thesaurus as a similarity function D(x, y), letting N x (k) be the set of k-nearest neighbors for x, and letting W (s 1 , s 2 ) be a similarity function over synsets in WordNet, we define a prevalence function R x (s) as follows:

Rx(s) = y∈Nx(k) D(x, y) max s ′ ∈ Sy W (s, s ′ ) t∈Sx max s ′ ∈ Sy W (t, s ′ ) (3)
This function essentially weights the semantic contribution that each distributionally-similar neighbor adds to a given sense for x. With the prevalence scores of each sense for x having been calculated, we use the following probability mass function p x over the space Ω s , where S x (k) is the set of k-most prevalent senses for x:

px(s) =            Rx(s) s ′ ∈Sx(k) Rx(s ′ ) , if s ∈ Sx(k) 0, otherwise (4)
Note that the first-sense ASR approach to using WordNet synsets for parsing, which has been previously explored in the literature (Agirre et al., 2011), corresponds to setting k=1 in Equation 4.

Ω c Cluster Space

In the case of the cluster space, any approach for word clustering may be used to create a reduced target vocabulary of clusters. Defining a categorical distribution over clusters would be interesting in the case of soft clustering of lemmas, in which a lemma can participate in more than one cluster, but we have not yet explored this clustering approach.

In this paper we limit ourselves to the simpler hard clustering HAC method, which uses a distributional thesaurus and iteratively joins two clusters together based on the similarities between lemmas in each cluster. We end up with a simple probability mass function p x over the space Ω c for a lemma x with corresponding cluster c x :

px(c) = 1, if c = cx 0, otherwise (5)

Probabilistic Feature Generalization

In a typical classifier-based machine learning setting in NLP, feature vectors are constructed using indicator functions that encode categorical information, such as POS tags, word forms or lemmas.

In this section we will use a running example where a and b are token positions of interest to a classifier, and for which feature vectors are created. If we let t stand for POS tag and l stand for lemma, a feature template for this pair of tokens might then be [t a l b ]. Feature templates are instantiated as actual features in a vector space depending on the categorical values they can take on. One possible instantiation of the template [t a l b ] would then be the feature [t a =verb∧l b =avocat], which indicates that a is a verb and b is the lemma avocat ("avocado" or "lawyer"), with the following indicator function:

f = 1, if ta=verb ∧ l b =avocat 0, otherwise (6)
To perform probabilistic feature generalization, we replace the indicator function, which represents a single original feature, with a collection of weighted functions representing a set of derived features. Suppose the French lemma avocat is in our source vocabulary and has multiple senses in Ω s (s 1 for the "avocado" sense, s 2 for the "lawyer" sense, etc.), as well as a probability mass function p av . We discard the old feature [t a =verb∧l b =avocat] and add, for each s i , a derived feature of the form [t a =verb∧x b =s i ], where x represents a target space generalized class, with the following weighted indicator function:

f (i) = pav(si), if ta=verb ∧ l b =avocat 0, otherwise (7)
This process extends easily to generalizing multiple categorical variables. Consider the bilexical feature [l a =manger∧l b =avocat], which indicates that a is the lemma manger ("eat") and b is the lemma avocat. If both lemmas manger and avocat appear in our source vocabulary and have multiple senses in Ω s , with probability mass functions p ma and p av , then for each pair i, j we derive a feature of the form [x a =s i ∧x b =s j ], with the following weighted indicator function:

f (i,j) = pma(si)pav(sj), if la=manger∧l b =avocat 0, otherwise (8)

Dependency Parsing

Dependency syntax involves the representation of syntactic information for a sentence in the form of a directed graph, whose edges encode word-to-word relationships. An edge from a governor to a dependent indicates, roughly, that the presence of the dependent is syntactically legitimated by the governor. An important property of dependency syntax is that each word, except for the root of the sentence, has exactly one governor; dependency syntax is thus represented by trees. Figure 1 shows an example of an unlabeled dependency tree.1 For languages like English or French, most sentences can be represented with a projective dependency tree: for any edge from word g to word d, g dominates any intervening word between g and d.

Dependency trees are appealing syntactic representations, closer than constituency trees to the semantic representations useful for NLP applications. This is true even with the projectivity requirement, which occasionally creates syntax-semantics mismatches. Dependency trees have recently seen a surge of interest, particularly with the introduction of supervised models for dependency parsing using linear classifiers.

Transition-Based Parsing

In this paper we focus on transition-based parsing, whose seminal works are that of [START_REF] Yamada | Statistical dependency analysis with support vector machines[END_REF] and [START_REF] Nivre | An efficient algorithm for projective dependency parsing[END_REF]. The parsing process applies a sequence of incremental actions, which typically manipulate a buffer position in the sentence and a stack for built sub-structures. In the arc-eager approach introduced by [START_REF] Nivre | Labeled pseudo-projective dependency parsing with support vector machines[END_REF] the possible actions are as follows, with s 0 being the token on top of the stack and n 0 being the next token in the buffer:

-SHIFT: Push n 0 onto the stack.

-REDUCE: Pop s 0 from the stack.

-RIGHT-ARC(r): Add an arc labeled r from s 0 to n 0 ; push n 0 onto the stack.

-LEFT-ARC(r): Add an arc labeled r from n 0 to s 0 ; pop s 0 from the stack.

The parser uses a greedy approach, where the action selected at each step is the best-scoring action according to a classifier, which is trained on a dependency treebank converted into sequences of actions. The major strength of this framework is its O(n) time complexity, which allows for very fast parsing when compared to more complex global optimization approaches.

Experimental Setup

We now discuss the treebanks used for training and evaluation, the parser implementation and baseline settings, the construction of the probabilistic lexical resources, and the parameter tuning and evaluation settings.

Treebanks

The treebank we use for training and in-domain evaluation is the French Treebank (FTB) [START_REF] Abeillé | Enriching a French treebank[END_REF], consisting of 12,351 sentences from the Le Monde newspaper, converted to projective2 dependency trees (Candito et al., 2010a). For our experiments we use the usual split of 9,881 training, 1,235 development, and 1,235 test sentences.

Moving beyond the journalistic domain, we use two additional treebank resources for out-of-domain parsing evaluations. These treebanks are part of the Sequoia corpus (Candito and Seddah, 2012), and consist of text from two non-journalistic domains annotated using the FTB annotation scheme: a medical domain treebank containing 574 development and 544 test sentences of public assessment reports of medicine from the European Medicines Agency (EMEA) originally collected in the OPUS project [START_REF] Tiedemann | News from OPUS -A collection of multilingual parallel corpora with tools and interfaces[END_REF], and a parliamentary domain treebank containing 561 test sentences from the Europarl3 corpus.

Parser and Baseline Settings

We use our own Python implementation of the arceager algorithm for transition-based parsing, based on the arc-eager setting of MaltParser [START_REF] Nivre | Malt-Parser: A language-independent system for datadriven dependency parsing[END_REF], and we train using the standard FTB training set. Our baseline feature templates and general settings correspond to those obtained in a benchmarking of parsers for French (Candito et al., 2010b), under the setting which combined lemmas and morphological features. 4 Automatic POS-tagging is performed using MElt (Denis and Sagot, 2009), and lemmatization and morphological analysis are performed using the Lefff lexicon [START_REF] Sagot | The Lefff, a freely available, accurate and large-coverage lexicon for French[END_REF]. Table 1 lists our baseline parser's feature templates.

Lexical Resource Construction

We now describe the construction of our probabilistic lexical target space resources, whose prerequisites include the automatic parsing of a large corpus, the construction of a distributional thesaurus, the use of ASR on WordNet synsets, and the use of HAC clustering.

Automatically-Parsed Corpus

The text corpus we use consists of 125 million words from the L'Est Republicain newspaper5 , 125 million words of dispatches from the Agence France-Presse, and 225 million words from a French Wikipedia backup dump6 . The corpus is Feature Templates Unigram tn 0 ; ln 0 ; cn 0 ; wn 0 ; ts 0 ; ls 0 ; cs 0 ; ws 0 ; ds 0 ; tn 1 ; ln 1 ; tn 2 ; tn 3 ; ts 1 ; ts 2 ; tn 0l ; ln 0l ; dn 0l ; ds 0l ; ds 0r ; ls 0h ; {m i n 0 : i ∈ |M |}; {m i s 0 : i ∈ |M |} Bigram ts 0 tn 0 ; ts 0 ln 0 ; ls 0 ln 0 ; ln 0 tn 1 ; tn 0 tn 0l ; tn 0 dn 0l ; {m i s 0 m j n 0 : i; j ∈ |M |}; {tn 0 m i n 0 : i ∈ |M |}; {ts 0 m i s 0 : i ∈ |M |} Trigram ts 2 ts 1 ts 0 ; ts 1 ts 0 tn 0 ; ts 0 tn 0 tn 1 ; tn 0 tn 1 tn 2 ;

tn 1 tn 2 tn 3 ; ts 0 ds 0l ds 0r

Table 1: Arc-eager parser feature templates. c = coarse POS tag, t = fine POS tag, w = inflected word form, l = lemma, d = dependency label, m i = morphological feature from set M . For tokens, n i = i th token in the buffer, s i = i th token on the stack. The token subscripts l, r, and h denote partially-constructed syntactic left-most dependent, right-most dependent, and head, respectively.

preprocessed using the Bonsai tool7 , and parsed using our baseline parser.

Distributional Thesaurus

We build separate distributional thesauri for nouns and for verbs,8 using straightforward methods in distributional lexical semantics based primarily on work by [START_REF] Lin | Automatic retrieval and clustering of similar words[END_REF] and Curran (2004). We use the FreDist tool (Henestroza Anguiano and Denis, 2011) for thesaurus creation.

First, syntactic contexts for each lemma are extracted from the corpus. We use all syntactic dependencies in which the secondary token has an open-class POS tag, with labels included in the contexts and two-edge dependencies used in the case of prepositional-phrase attachment and coordination. Example contexts are shown in Figure 2. For verb lemmas we limit contexts to dependencies in which the verb is governor, and we add unlexicalized versions of contexts to account for subcategorization. For noun lemmas, we use all dependencies in which the noun participates, and all contexts are lexicalized. The vocabulary is limited to lemmas with at least 1,000 context occurrences, resulting in 8,171 nouns and 2,865 verbs.

Each pair of lemma x and context c is subsequently weighted by mutual informativeness using the point-wise mutual information metric, with Figure 2: Example dependency contexts for the verb lemma manger. The one-edge contexts corresponds to the phrase "manger un avocat" ("eat an avocado"), and the two-edge contexts corresponds to the phrase "manger avec un avocat" ("eat with a lawyer").

probabilities estimated using frequency counts:

I(x, c) = log p(x, c) p(x)p(c) (9)
Finally, we use the cosine metric to calculate the distributional similarity between pairs of lemmas x, y:

D(x, y) = c I(x, c)I(y, c) c I(x, c) 2 × c I(y, c) 2
(10)

WordNet ASR

For WordNet synset experiments we use the French EuroWordNet 9 (FREWN). A WordNet synset mapping 10 allows us to convert synsets in the FREWN to Princeton WordNet version 3.0, and after discarding a small number of synsets that are not covered by the mapping we retain entries for 9,833 nouns and 2,220 verbs. We use NLTK, the Natural Language Toolkit (Bird et al., 2009), to calculate similarity between synsets. As explained in Section 2.2, ASR is performed using the method of [START_REF] Mccarthy | Finding predominant word senses in untagged text[END_REF]. We use k=8 for the distributional nearest-neighbors to consider when ranking the senses for a lemma, and we use the synset similarity function of [START_REF] Jiang | Semantic similarity based on corpus statistics and lexical taxonomy[END_REF]

HAC Clustering

For the HAC clustering experiments in this paper, we use the CLUTO package12 . The distributional thesauri described above are taken as input, and the UPGMA setting is used for cluster agglomeration. We test varying levels of clustering, with a parameter z which determines the proportion of cluster vocabulary size with respect to the original vocabulary size (8,171 for nouns and 2,865 for verbs).

Resource Coverage

The coverage of our lexical resources over the FTB and two out-of-domain evaluation sets, at the level of token occurrences of verbs and common nouns, is described in Table 2. We can see that the FTB training set vocabulary provides better coverage than the FREWN for both nouns and verbs, while the coverage of the thesauri (and derived clusters) is the highest overall.

Tuning and Evaluation

We evaluate four lexical target space configurations against the baseline of lemmatization, tuning parameters using ten-fold cross-validation on the FTB training set. The feature templates are the same as those in Table 1, with the difference that features involving lemmas are modified by the probabilistic feature generalization technique described in Section 2.4, using the appropriate categorical distributions. In all configurations, we exclude the French auxiliary verbs être and avoir from participation in lexical generalization, and we replace proper nouns with a special lemma13 . Below we describe the tuned parameters for each configuration.

-RC: Replacement with cluster in Ω c

For clusters and the parameter z (cf. Section 4.3.4), we settled on relative cluster vocabulary size z=0.6 for nouns and z=0.7 for verbs. We also generalized lemmas not appearing in the distributional thesaurus into a single unknown class.

-PKNL: Probabilistic k-nearest lemmas in Ω l For the parameters k and m (cf. Section 2.1), we settled on k=4 and m=0.5 for both nouns and verbs. We also use the unknown class for low-frequency lemmas, as in the RC configuration.

-RS: Replacement with first-sense (k=1) in Ω s Since the FREWN has a lower-coverage vocabulary, we did not use an unknown class for out-of-vocabulary lemmas; instead, we mapped them to unique senses. In addition, we did not perform lexical generalization for verbs, due to low cross-validation performance.

-PKPS: Probabilistic k-prevalent senses in Ω s For this setting we decided to not place any limit on k, due to the large variation in the number of senses As in the RS configuration, we mapped out-ofvocabulary lemmas to unique senses and did not perform lexical generalization for verbs.

Results

Table 3 shows labeled attachment score (LAS) results for our baseline parser (Lemmas) and four lexical generalization configurations. For comparison, we also include results for a setting that only uses word forms (Forms), which was the baseline for previous work on French dependency parsing (Candito et al., 2010b). Punctuation tokens are not scored, and significance is calculated using Dan Bikel's randomized parsing evaluation comparator14 , at significance level p=0.05.

In-Domain Results

Our in-domain evaluation yields slight improvements in LAS for some lexical generalization configurations, with PKNL performing the best. However, the improvements are not statistically significant. A potential explanation for this disappointing result is that the FTB training set vocabulary covers the FTB test set at high rates for both nouns (95.25%) and verbs (96.54%), meaning that lexical data sparseness is perhaps not a big problem for in-domain dependency parsing. While WordNet synsets could be expected to provide the added benefit of taking word sense into account, sense ambiguity is not really treated due to ASR not providing word sense disambiguation in context.

Out-Of-Domain Results

Our evaluation on the medical domain yields statistically significant improvements in LAS, particularly for the two probabilistic target space approaches. PKNL and PKPS improve parsing for both the EMEA dev and test sets, while RC improves parsing for only the EMEA test set and RS does not significantly improve parsing for either set. As in our in-domain evaluation, PKNL performs the best overall, though not significantly better than other lexical generalization settings. One explanation for the improvement in the medical domain is the substantial increase in coverage of nouns in EMEA afforded into a single class.

by the distributional thesaurus (+26%) and FREWN (+16%) over the base coverage afforded by the FTB training set.

Our evaluation on the parliamentary domain yields no improvement in LAS across the different lexical generalization configurations. Interestingly, Candito and Seddah (2012) note that while Europarl is rather different from FTB in its syntax, its vocabulary is surprisingly similar. From Table 2 we can see that the FTB training set vocabulary has about the same high level of coverage over Europarl (94.69% for nouns and 97.76% for verbs) as it does over the FTB evaluation sets (95.35% for nouns and 96.54% for verbs). Thus, we can use the same reasoning as in our in-domain evaluation to explain the lack of improvement for lexical generalization methods in the parliamentary domain.

Lexical Feature Use During Parsing

Since lexical generalization modifies the lexical feature space in different ways, we also provide an analysis of the extent to which each model's lexical features are and out-ofdomain parsing. Table 4 describes, for each configuration, the number of lexical features stored in the parsing model along with the average lexical feature use (ALFU) of classification instances (each instance represents a parse transition) during training and parsing. 15 Lexical feature use naturally decreases when moving from the training set to the evaluation sets, due to holes in lexical coverage outside of a parsing model's training set. The single-mapping configurations (RC, RS) do not increase the number of lexical features in a classification instance, which explains the fact that their ALFU on the FTB training set (6.0) is the same as that of the baseline. However, the decrease in ALFU when parsing the evaluation sets is less severe for these configurations than for the baseline: when parsing EMEA Dev with the RC configuration, where we obtain a significant LAS improvement over the baseline, the reduction in ALFU is only 13% compared to 22% for the baseline parser.

For the probabilistic generalization configurations, we also see decreases in ALFU when parsing the 15 We define the lexical feature use of a classification instance to be the number of lexical features in the parsing model that receive non-zero values in the instance's feature vector. evaluation sets, though their higher absolute ALFU may help explain the strong medical domain parsing performance for these configurations.

Impact on Running Time

Another factor to note when evaluating lexical generalization is the effect that it has on running time.

Compared to the baseline, the single-mapping configurations (RC, RS) speed up feature extraction and prediction time, due to reduced dimensionality of the feature space. On the other hand, the probabilistic generalization configurations (PKNL, PKPS) slow down feature extraction and prediction time, due to an increased dimensionality of the feature space and a higher ALFU. Running time is therefore a factor that favors the single-mapping approach over our proposed probabilistic approach. Taking a larger view on our findings, we hypothesize that in order for lexical generalization to improve parsing, an approach needs to achieve two objectives: (i) generalize sufficiently to ensure that lemmas not appearing in the training set are nonetheless associated with lexical features in the learned parsing model; (ii) substantially increase lexical coverage over what the training set can provide. The first of these objectives seems to be fulfilled through our lexical generalization methods, as indicated in Table 4. The second objective, however, seems difficult to attain when parsing text indomain, or even out-of-domain if the domains have a high lexical overlap (as is the case for Europarl). Only for our parsing experiments in the medical domain do both objectives appear to be fulfilled, as evidenced by our LAS improvements when parsing EMEA with lexical generalization.

We now discuss previous work concerning the use of lexical generalization for parsing, both in the classic in-domain setting and in the more recently popular out-of-domain setting.

Results in Constituency-Based Parsing

The use of word classes for parsing dates back to the first works on generative constituency-based parsing, whether using semantic classes obtained from hand-built resources or less-informed classes created automatically. Bikel (2000) tried incorporating WordNet-based word sense disambiguation into a parser, but failed to obtain an improvement. [START_REF] Benjamins | Parsing the penn chinese treebank with semantic knowledge[END_REF] generalized bilexical dependencies in a generative parsing model using Chinese semantic resources (CiLin and HowNet), obtaining improvements for Chinese parsing. More recently, [START_REF] Agirre | Improving parsing and PP attachment performance with sense information[END_REF] show that replacing words with Word-Net semantic classes improves English generative parsing. [START_REF] Lin | Refining grammars for parsing with hierarchical semantic knowledge[END_REF] use the HowNet resource within the split-merge PCFG framework [START_REF] Petrov | Learning accurate, compact, and interpretable tree annotation[END_REF] for Chinese parsing: they use the firstsense heuristic to append the most general hypernym to the POS of a token, obtaining a semanticallyinformed symbol refinement, and then guide further symbol splits using the HowNet hierarchy. Other work has used less-informed classes, notably unsupervised word clusters. Candito and Crabbé (2009) use Brown clusters to replace words in a generative PCFG-LA framework, obtaining substantial parsing improvements for French.

Results in Dependency Parsing

In dependency parsing, word classes are integrated as features in underlying linear models. In a seminal work, [START_REF] Koo | Simple semisupervised dependency parsing[END_REF] use Brown clusters as features in a graph-based parser, improving parsing for both English and Czech. However, attempts to use this technique for French have lead to no improvement when compared to the use of lemmatization and morphological analysis (Candito et al., 2010b). [START_REF] Sagae | Clustering words by syntactic similarity improves dependency parsing of predicate-argument structures[END_REF] augment a transitionbased English parser with clusters using unlexicalized syntactic distributional similarity: each word is represented as a vector of counts of emanating unlexicalized syntactic paths, with counts taken from a corpus of auto-parsed phrase-structure trees, and HAC clustering is performed using cosine similarity. For semantic word classes, (Agirre et al., 2011) integrate WordNet senses into a transition-based parser for English, reporting small but significant improvements in LAS (+0.26% with synsets and +0.36% with semantic files) on the full Penn Treebank with first-sense information from Semcor.

We build on previous work by attempting to reproduce, for French, past improvements for indomain English dependency parsing with generalized lexical classes. Unfortunately, our results for French do not replicate the improvements for English using semantic sense information (Agirre et al., 2011) or word clustering [START_REF] Sagae | Clustering words by syntactic similarity improves dependency parsing of predicate-argument structures[END_REF]. The primary difference between our paper and previous work, though, is our evaluation of a novel probabilistic approach for lexical generalization.

Out-Of-Domain Parsing

Concerning techniques for improving out-ofparsing, a related approach has been to use self-training with auto-parsed out-of-domain data, as [START_REF] Mcclosky | Self-training for biomedical parsing[END_REF] do for English constituency parsing, though in that approach lexical generalization is not explicitly performed. Candito et al. (2011) use word clustering for domain adaptation of a PCFG-LA parser for French, deriving clusters from a corpus containing text from both the source and target domains, and they obtain parsing improvements in both domains. We are not aware of previous work on the use of lexical generalization for improving out-of-domain dependency parsing.

Conclusion

We have investigated the use of probabilistic lexical target spaces for reducing lexical data sparseness in a transition-based dependency parser for French. We built a distributional thesaurus from an automatically-parsed large text corpus, using it to generate word clusters and perform WordNet ASR. We tested a standard approach to lexical generalization for parsing that has been previously explored, where a word is mapped to a single cluster or synset. We also introduced a novel probabilistic lexical generalization approach, where a lemma is represented by a categorical distribution over the space of lemmas, clusters, or synsets. Probabilities for the lemma space were calculated using the distributional thesaurus, and probabilities for the Word-Net synset space were calculated using ASR sense prevalence scores, with probabilistic clusters left for future work.

Our experiments with an arc-eager transitionbased dependency parser resulted in modest but significant improvements in LAS over the baseline when parsing out-of-domain medical text. However, we did not see statistically significant improvements over the baseline when parsing in-domain text or out-of-domain parliamentary text. An explanation for this result is that the French Treebank training set vocabulary has a very high lexical coverage over the evaluation sets in these domains, suggesting that lexical generalization does not provide additional benefit. Comparing the standard single-mapping approach to the probabilistic generalization approach, we found a slightly (though not significantly) better performance for probabilistic generalization across different parsing configurations and evaluation sets. However, the probabilistic approach also has the downside of a slower running time.

Based on the findings in this paper, our focus for future work on lexical generalization for dependency parsing is to continue improving parsing performance on out-of-domain text, specifically for those domains where lexical variation is high with respect to the training set. One possibility is to experiment with building a distributional thesaurus that uses text from both the source and target domains, similar to what Candito et al. ( 2011) did with Brown clustering, which may lead to a stronger bridging effect across domains for probabilistic lexical generalization methods.

Figure 1 :

 1 Figure1: An unlabeled dependency tree for "Elle ouvrit la porte avec la clé" ("She opened the door with the key").

•

  One-Edge Context: -obj→ N |avocat • One-Edge Context: -obj→ N (unlexicalized) • Two-Edge Context: -mod→ P |avec -obj→ N |avocat • Two-Edge Context: -mod→ P |avec -obj→ N (unlexicalized)

  , with default information content counts from NLTK calculated over the British National Corpus 11 .

		Source		Evaluation Set
		Vocabulary FTB Eval EMEA Eval Europarl
		FTB train	95.35	62.87	94.69
	Nouns	Thesaurus	96.25	79.00	97.83
		FREWN	80.51	73.09	87.06
		FTB train	96.54	94.56	97.76
	Verbs	Thesaurus	98.33	97.82	99.54
		FREWN	88.32	91.48	91.98
	Table 2: Lexical occurrence coverage (%) of source
	vocabularies over evaluation sets. FTB Eval contains
	both the FTB development and test sets, while EMEA
	Eval contains both the EMEA development and test sets.
	Proper nouns are excluded from the analysis.

9 http://www.illc.uva.nl/EuroWordNet/ 10 http://nlp.lsi.upc.edu/tools/download-map. php 11 http://www.natcorp.ox.ac.uk/

Our experiments involve labeled parsing, with edges additionally labeled with the surface grammatical function that the dependent bears with respect to its governor.

The projectivity constraint is linguistically valid for most French parses: the authors report < 2% non-projective edges in a hand-corrected subset of the converted FTB.

http://www.statmt.org/europarl/

That work tested the use of Brown clusters, but obtained no improvement compared to a setting without clusters. Thus, we do not evaluate Brown clustering in this paper.

http://www.cnrtl.fr/corpus/estrepublicain/

http://dumps.wikimedia.org/

http://alpage.inria.fr/statgram/frdep/fr_ stat_dep_parsing.html

We additionally considered adjectives and adverbs, but our initial tests yielded no parsing improvements.

http://glaros.dtc.umn.edu/gkhome/cluto/ cluto/download

Proper nouns tend to have sparse counts, but for computational reasons we did not include them in our distributional thesaurus construction. We thus chose to simply generalize them

http://www.cis.upenn.edu/ ˜dbikel/software. html

Acknowledgments

This work was funded in part by the ANR project Sequoia ANR-08-EMER-013. pages 317-325, Columbus, Ohio, June. E. Agirre, K. Bengoetxea, K. Gojenola, and J. Nivre. 2011. Improving dependency parsing with semantic classes. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 699-703, Portland, Oregon, June. D.M. Bikel. 2000. A statistical model for parsing and word-sense disambiguation. In Proceedings of the EMNLP/VLC-2000, pages 155-163, Hong Kong, October. S. Bird, E. Loper, and E. Klein. 2009. Natural Language Processing with Python. O'Reilly Media Inc. P.F. Brown, P.V. Desouza, R.L. Mercer, V.J.D. Pietra, and J.C. Lai. 1992. Class-based n-gram models of natural language. Computational Linguistics, 18(4):467-479. R.C. Bunescu. 2008. Learning with probabilistic features for improved pipeline models. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 670-679, Honolulu, Hawaii, October. M. Candito and B. Crabbé. 2009. Improving generative statistical parsing with semi-supervised word clustering. In Proceedings of the 11th International Conference on Parsing Technologies, pages 138-141, Paris, France, October. M. Candito and D. Seddah. 2012. Le corpus Sequoia : annotation syntaxique et exploitation pour l'adaptation d'analyseur par pont lexical. In Actes de la 19ème conférence sur le traitement automatique des langues naturelles, Grenoble, France, June. To Appear. M. Candito, B. Crabbé, and P. Denis. 2010a. Statistical French dependency parsing: Treebank conversion and first results. In Proceedings of the 7th International Conference on Language Resources and Evaluation, Valetta, Malta, May. M. Candito, J. Nivre, P. Denis, and E. Henestroza Anguiano. 2010b. Benchmarking of statistical dependency parsers for French. In Proceedings of the 23rd International Conference on Computational Linguistics, pages 108-116, Beijing, China, August. M. Candito, E. Henestroza Anguiano, D. Seddah, et al. 2011. A Word Clustering Approach to Domain Adaptation: Effective Parsing of Biomedical Texts. In Proceedings of the 12th International Conference on Parsing Technologies, Dublin, Ireland, October. J.R. Curran. 2004. distributional to semantic similarity. Ph.D. thesis, University of Edinburgh. P. Denis and B. Sagot. 2009. Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art