Fernando Endo

Damien Couroussé

Henri-Pierre Charles

Pushing the Limits of Online Auto-tuning: Machine Code Optimization in Short-Running Kernels

This article proposes an online auto-tuning approach for computing kernels. Differently from existing online auto-tuners, which regenerate code with long compilation chains from the source to the binary code, our approach consists on deploying auto-tuning directly at the level of machine code generation. This allows auto-tuning to pay off in very shortrunning applications. As a proof of concept, our approach is demonstrated in two benchmarks, which execute during hundreds of milliseconds to a few seconds only. In a CPUbound kernel, the speedups achieved are 1.10 to 1.58 in average depending on the target micro-architecture, up to 2.53 in the most favourable conditions (all run-time overheads included). In a memory-bound kernel, less favourable to our runtime autotuning optimizations, the speedups are 1.04 to 1.10 in average, up to 1.30. Despite the short execution times of our benchmarks, the overhead of our runtime auto-tuning is between 0.2 and 4.2 % only of the total application execution times. By simulating the CPU-bound application in 11 different CPUs, we showed that, despite the clear hardware disadvantage of In-Order (IO) cores vs. Out-of-Order (OOO) equivalent cores, online auto-tuning in IO CPUs obtained an average speedup of 1.03 and an energy efficiency improvement of 39 % over the SIMD reference in OOO CPUs.

I. INTRODUCTION

High-performance general-purpose embedded processors are evolving with unprecedented grow in complexity. ISA back-compatibility and energy reduction techniques are among the main reasons. For sake of software development cost, applications do not necessarily run in only one target, one binary code may run in processors from different manufacturers and even in different cores inside a SoC.

Iterative optimization and auto-tuning have been used to automatically find the best compiler optimizations and algorithm implementations for a given source code and target CPU. These tuning approaches have been used to address the complexity of desktop-and server-class processors (DSCPs). They show moderate to high performance gains compared to non-iterative compilation, because default compiler options are usually based on the performance of generic benchmarks executed in representative hardware. Usually, such tools need long space exploration times to find quasi-optimal machine code. Previous work addressed auto-tuning at run-time [START_REF] Voss | ADAPT: Automated de-coupled adaptive program transformation[END_REF], [START_REF] Tiwari | Online adaptive code generation and tuning[END_REF], [START_REF] Chen | Iterative optimization for the data center[END_REF], [START_REF] Ansel | SiblingRivalry: Online autotuning through local competitions[END_REF], however previously proposed auto-tuners are only adapted to applications that run for several minutes or even hours, such as scientific or data center workload, in order to pay off the space exploration overhead and overcome the costs of static compilation.

While previous work proposed run-time auto-tuning in DSCP, no work focused on general-purpose embedded-class processors.

In hand-held devices, applications usually run for a short period of time, imposing a strong constraint to run-time autotuning systems. In this scenario, a lightweight tool should be employed to explore pre-identified code optimizations in computing kernels.

We now explain our motivation for developing run-time auto-tuning tools for general-purpose embedded processors:

Embedded core complexity. The complexity of highperformance embedded processors is following the same trend as the complexity of DSCP evolved in the last decades. For example, current 64-bit embedded-class processors are sufficiently complex to be deployed in micro-servers, eventually providing a low-power alternative for data center computing. In order to address this growing complexity and provide better performance portability than static approaches, online autotuning is a good option.

Heterogeneous multi/manycores. The power wall is affecting embedded systems as they are affecting DSCP, although in a smaller scale. Soon, dark silicon may also limit the powerable area in embedded SoC. As a consequence, heterogeneous clusters of cores coupled to accelerators are one of the solutions being adopted in embedded SoC. In the long term, this trend will exacerbate software challenges of extracting the achievable computing performance from hardware, and runtime approaches may be the only way to improve energy efficiency [START_REF] Borkar | The future of microprocessors[END_REF].

ISA-compatible processor diversity. In the embedded market, a basic core design can be implemented by different manufacturers with different transistor technologies and also varying configurations. Furthermore, customized pipelines may be designed, yet being entirely ISA-compatible with basic designs. This diversity of ISA-compatible embedded processors facilitates software development, however because of differences in pipeline implementations, static approaches can only provide sub-optimal performance when migrating between platforms. In addition, contrary to DSCP, in-order (IO) cores are still a trend in high-performance embedded devices because of low-power constraints, and they benefit more from target-specific optimizations than out-of-order (OOO) pipelines.

Static auto-tuning performance is target-specific. In average, the performance portability of statically auto-tuned code is poor when migrating between different micro-architectures [START_REF] Ansel | PetaBricks: A language and compiler for algorithmic choice[END_REF]. Hence, static auto-tuning is usually employed when the execution environment is known. On the other hand, the trends of hardware virtualization and software packages in generalpurpose processors result in applications underutilizing the hardware resources, because they are compiled to generic micro-architectures. Online auto-tuning can provide better performance portability, as previous work showed in serverclass processors [START_REF] Ansel | SiblingRivalry: Online autotuning through local competitions[END_REF].

Ahead-of-time auto-tuning. In recent Android versions (5.0 and later), when an application is installed, native machine code is generated from bytecode (ahead-of-time compilation). The run-time auto-tuning approach proposed in this work could be extended and integrated in such systems to auto-tune code to the target core(s) or pre-profile and select the best candidates to be evaluated in the run-time phase. Such approach would allow auto-tuning to be performed in embedded applications with acceptable ahead-of-time compilation overhead.

Interaction with other dynamic techniques. Some powerful compiler optimizations depend both on input data and the target micro-architecture. Constant propagation and loop unrolling are two examples. The first can be addressed by dynamically specializing the code, while the second is better addressed by an auto-tuning tool. When input data and the target microarchitecture are known only at program execution, which is usually the case in hand-held devices, mixing those two dynamic techniques can provide even higher performance improvements. If static versioning is employed, it could easily lead to code size explosion, which is not convenient to embedded systems. Therefore, run-time code generation and auto-tuning is needed. This article proposes an online auto-tuning approach for computing kernels in ARM processors. Existing online autotuners regenerate code using complex compilation chains, which are composed of several transformation stages to transform source into machine code, leading to important compilation times. Our approach consists on shortening the auto-tuning process, by deploying auto-tuning directly at the code generation level, through a run-time code generation tool, called deGoal [START_REF] Charles | deGoal a tool to embed dynamic code generators into applications[END_REF]. This allows auto-tuning to be successfully employed in very short-running kernels, thanks to the low runtime code generation overhead. Our very fast online auto-tuner that can quickly explore the tuning space, and find code variants that are efficient on the running micro-architecture. The tuning space can have hundreds or even thousands of valid binary code instances, and hand-held devices may execute applications that last for a few seconds. Therefore, in this scenario online auto-tuners have a very strong timing constraint. Our approach address this problem with a two-phase online exploration and by deploying auto-tuning directly at the level of machine code generation.

The proposed approach is evaluated in a highly CPUbound (favorable) and a highly memory-bound (unfavorable) application, to be representative of all applications between these two extreme conditions. In ARM platforms, the two benchmarks run during hundreds of milliseconds to only a few seconds. In the favorable application, the average speedup is 1.26 going up to 1.79, all run-time overheads included.

One interesting question that this work tries to answer is if run-time auto-tuning in simpler and energy-efficient cores can obtain performance similar to statically compiled code run in more complex and hence power-hungry cores. The aim is to compare the energy and performance of IO and OOO designs, with the same pipeline and cache configurations, except for the dynamic scheduling capability. This study would tell us at what extent run-time auto-tuning of code can replace OOO execution. However, given that commercial IO designs have less resources than OOO ones (e.g., smaller caches, branch predictor tables), a simulation framework was employed to perform this experiment. The simulation results show that online micro-architectural adaption of code to IO pipelines can in average outperform the hand vectorized references run in similar OOO cores: despite the clear hardware disadvantage, the proposed approach applied to the CPU-bound application obtained an average speedup of 1.03 and an energy efficiency improvement of 39 %.

II. MOTIVATIONAL EXAMPLE

In this section, we present an experiment supporting the idea that performance achievements could be obtained by the combined use of run-time code specialization and auto-tuning. The experiment is carried out with a SIMD version of the euclidean distance kernel implemented in the Streamcluster benchmark, manually vectorized in the PARVEC [START_REF] Cebrian | Optimized hardware for suboptimal software: The case for SIMD-aware benchmarks[END_REF] suite (originally from the PARSEC 3.0 suite [START_REF] Bienia | Benchmarking modern multiprocessors[END_REF]). In the reference kernel, the dimension of points is a run-time constant, but given that it is part of the input set, compilers cannot optimize it. In the following comparisons, we purposefully set the dimension as a compile-time constant in the reference code to let the compiler (gcc 4.9.3) generate highly optimized kernels (up to 15 % of speedup over generic versions). This ensures a fair comparison with auto-tuned codes. With deGoal [START_REF] Charles | deGoal a tool to embed dynamic code generators into applications[END_REF], in an offline setting, we generated various kernel versions, by specializing the dimension and auto-tuning the code implementation for an ARM Cortex-A8 and A9. The auto-tuned parameters mainly affect loop unrolling and prefetching instructions, and are detailed in Section III-A. Figure 1 shows the speedups of various generated kernels in the two core configurations. By analyzing the results, we draw several motivating ideas:

Code specialization and auto-tuning provide considerable speedups even compared to statically specialized and manually vectorized code: Auto-tuned kernel implementations obtained speedups going up to 1.46 and 1.52 in the Cortex-A8 and A9, respectively.

The best set of auto-tuned parameters and optimizations varies from one core to another: In both cases in Figure 1, there is a poor performance portability of the best configurations between the two cores. For example, in Figure 1(b), when the best kernel for the Cortex-A8 is executed in the A9, the execution time increases by 55 %, compared to the best kernel for the latter. Conversely, the best kernel for the A9 when executed in the A8 increases the execution time by 21 %, compared to the most performing kernel.

There is no performance correlation between the sets of optimizations and input data: The main auto-tuned parameters Fig. 1: Speedups of euclidean distance kernels statically generated with deGoal. The reference is a hand vectorized kernel (from PARVEC) compiled with gcc 4.9.3 and highly optimized to each target core (-O3 and -mcpu options). Both deGoal and reference kernels have the dimension of points specialized (i.e. set as a compile-time constant). The exploration space goes beyond 600 configurations, but here it was zoomed in on the main region. The peak performance of each core is labeled. Empty results in the exploration space correspond to configurations that could not generate code. are related to loop unrolling, which depends on the dimension of points (part of the input set). In consequence, the exploration space and the optimal solution depend on an input parameter. For example, the configurations of the top five peak performances for the A8 in Figure 1(b) (configurations 30, 66, 102, 137 and 138) have poor performances in Figure 1(a) or simply can not generate code with a smaller input set.

The results suggest that, although code specialization and auto-tuning provide high performance improvements, they should ideally be performed only when input data and target core are known. In the released input sets for Streamcluster, the dimensions are 32, 64 and 128, but the benchmark accepts any integer value. Therefore, even if the target core(s) was (were) known at compile time and the code was statically specialized, auto-tuned and versioned, it could easily lead to code size explosion.

We demonstrate in the following sections that the most important feature of our approach is that it is fast enough to enable the specialization of run-time constants combined with online auto-tuning, allowing the generation of highly optimized code for a target core, whose configuration may not be known prior compilation.

The optimized kernels shown in this motivational example were statically auto-tuned. The run-time auto-tuning approach proposed in this work successfully found optimized kernels whose performance is in average only 6 % away from the performance of the best kernels statically found (all run-time overheads included). It is worth observing that the auto-tuning space has up to 630 valid versions: its exploration took several hours per dimension and per platform, even if the benchmark runs for a few seconds.

III. ONLINE AUTO-TUNING APPROACH

This section describes the approach of the proposed online auto-tuner. Figure 2 presents the architecture of the framework that auto-tunes a function at run time. At the beginning of the program execution, a reference function (e.g., C compiled code) is evaluated accordingly to a defined metric (execution time in the experiments presented here). This reference function starts as the active function. In parallel to the program execution, the auto-tuning thread periodically wakes up and decides if it is time to generate and evaluate a new version. The active function is replaced by the new one, if its score is better. This approach is applicable to computing kernels frequently called.

Sections III-A, III-B and III-C describe the implementation of each block from the main loop of Figure 2.

A. Parametrizable function generator

New versions of functions are generated by a tool called deGoal. It implements a domain specific language for run-time code generation of computing kernels. It defines a pseudoassembly RISC-like language, which can be mixed with standard C code. The machine code is only generated by deGoal instructions, while the management of variables and code generation decisions are implemented by deGoal pseudoinstructions, optionally mixed with C code. The dynamic nature of the language comes from the fact that run-time information can drive the machine code generation, allowing program and data specialization.

deGoal supports high-performance ARM processors from the ARMv7-A architecture, including FP and SIMD instructions. A set of C functions were also created to be called in the host application or inside a function generator to configure the code generation, allowing the evaluation of the performance impact of various code generation options.

To illustrate some auto-tuning possibilities and how the dynamic language works, Figure 3 presents the deGoal code to auto-tune the euclidean distance implementation, focusing on the main loop of the kernel. This is the code used in the motivational example presented in Section II, and also in the run-time auto-tuning experiments later in this work. Statements between the symbols #[ and ]# are recognized as the dynamic language, which are statically converted to standard C code, calling deGoal library code to generate machine instructions at run time. Other statements are standard C code. An important symbol in the dynamic language is the sign #(): any C expression placed between the parenthesis will be dynamically evaluated, allowing the inlining of run-time constants or immediate values.

The kernel generator (called compilette in the deGoal jargon) description represented in Figure 3 can generate different machine codes, depending on the arguments that it receives. In line 1, the first argument is the dimension, which is specialized in this example. The four following arguments are the autotuned parameters:

• Hot loop unrolling factor (hotUF): Unrolls a loop and processes each element with a different register, in order to avoid pipeline stalls. • Cold loop unrolling factor (coldUF): Unrolls a loop by simply copy-pasting a pattern of code, using fewer registers, but potentially creating pipeline stalls. • Normalized vector length (vectLen): Defines the length of the vector used to process elements in the loop body, normalized to the SIMD width when generating SIMD instructions (four in the ARM ISA). Longer vectors may benefit code size and speed, because instructions that load multiple registers instructions may be generated. • Data pre-fetching stride (pldStride): Defines the stride in bytes used in hint instructions to try to pre-fetch data of the next loop iteration. Given that the dimension is specialized (run-time constant), we know exactly how many elements are going to be processed in the main loop. Hence, between the lines 5 and 21, the pair of deGoal instructions loop and loopend can produce three possible results, depending on the dimension and the unrolling factors:

1) No code for the main loop is generated if the dimension is too small. The computation is then performed by a leftover code (not shown in Figure 3). 2) Only the loop body is generated without any branch instruction, if the main loop is completely unrolled.

3) The loop body and a backward branch are generated if more than one iteration is needed (i.e. the loop is partially unrolled). The loop body iterates over the coordinates of two points (referenced by coord1 and coord2) to compute the squared euclidean distance. The computation is performed with vectors, but for the sake of paper conciseness, variable allocation is not shown in Figure 3. Briefly, in the loop body, lines 8 and 9 load vectLen coordinates of each point into vectors, lines 14 and 15 compute the difference, squaring and accumulation, and finally outside the loop, line 23 accumulates the partial sums in each vector element of Vresult into result. Between the lines 6 and 20, the loop body is unrolled by mixing three autotuning effects, whose parameters are highlighted in Figure 3: the outer for (line 6) simply replicates coldUF times the code pattern in its body, the inner for (line 7) unrolls the loop hotUF times by using different registers to process each pair of coordinates, and finally the number of elements processed in the inner loop is set through the vector length vectLen. In the lines 10 to 13, the last auto-tuned parameter affects a data pre-fetching instruction: if pldStride is zero, no prefetching instruction is generated, otherwise deGoal generates a hint instruction that tries to pre-fetch the cache line pointed by the address of the last load plus pldStride.

Besides the auto-tuning possibilities, which are explicitly coded with the deGoal language, a set of C functions can be called to configure code generation options. In this work, three code optimizations were studied:

• Instructions scheduling (IS): Reorders instructions to avoid stall cycles and tries to maximize multi-issues. • Stack minimization (SM): Only uses FP scratch registers to reduce the stack management overhead. • Vectorization (VE): Generates SIMD instructions to process vectors. Most of the explanations presented in this section were given through examples related to the Streamcluster benchmark, but partial evaluation, loop unrolling and data pre-fetching are broadly used compiler optimization techniques that can be employed in almost any kernel-based application.

B. Regeneration decision and space exploration

The regeneration decision takes into account two factors: the regeneration overhead and the achieved speedup since the beginning of the execution. The first one allows to keep the run-time overhead of the tool at acceptable limits if it fails to find better kernel versions. The second factor acts as an investment, i.e. allocating more time to explore the tuning space if previously found solutions provided sufficient speedups. Both factors are represented as percentage values, for example limiting the regeneration overhead to 1 % and investing 10 % of gained time to explore new versions.

To estimate the gains, the instrumentation needed in the evaluated functions is simply a variable that increments each time the function is executed. Knowing this information and the measured run-time of each kernel, it is possible to estimate the time gained at any moment. However, given that the reference and the new versions of kernel have their execution times measured only once, the estimated gains may not be accurate if the application has phases with very different behaviors.

Given that the whole space exploration can have hundreds or even thousands of kernel versions, it was divided in two online phases:

• First phase: Explores auto-tuning parameters that have an impact on the structure of the code, namely, hotUF, coldUF and vectLen, but also the vectorization option (VE). The previous list is also the order of exploration, going from the least switched to the most switched parameter. The initial state of the remaining auto-tuning parameters are determined through pre-profiling. • Second phase: Fixes the best parameters found in the previous phase and explores the combinatorial choices of remaining code generation options (IS, SM) and pldStride. In our experiments, the range of hotUF and vectLen were defined by the programmer in a way to avoid running out of registers, but these tasks can be automated and dynamically computed by taking into account the code structure (static) and the available registers (dynamic information). Compared to coldUF, their ranges are naturally well bounded, providing an acceptable search space size.

The range of coldUF was limited to 64 after a pre-profiling phase, because unrolling loops beyond that limit provided almost no additional speedup.

The last auto-tuned parameter, pldStride, was explored with the values 32 and 64, which are currently the two possible cache line lengths in ARM processors.

Finally, to optimize the space exploration, first the tool searches for kernel implementations that have no leftover code. After exhausting all possibilities, this condition is softened by gradually allowing leftover processing.

C. Kernel evaluation and replacement

The auto-tuning thread wakes up regularly to compute the gains and determine if it is time to regenerate a new function. Each new version is generated in a dynamically allocated code buffer, and then its performance is evaluated. When the new code has a better score than that of the active function, the global function pointer that references the active function is set to point to the new code buffer. In order to evaluate a new kernel version, the input data (i.e., processed data) used in the first and second phases can be either:

• Real input data only: Evaluates new kernel versions with real data, performing useful work during evaluation, but suffering from measurement oscillations between independent runs. These oscillations can sometimes lead to wrong kernel replacement decisions.

• Training & real input data: Uses training data with warmed caches in the first phase and real data in the second one. A training input set with warmed caches results in very stable measurements, which ensure good choices for the active function. Since no useful work is performed, using training data is only adapted to kernels that are called sufficient times to consider the overhead of this technique negligible, and to kernels that have no side effect. In the second phase, the usage of real data is mandatory, because the adequacy of pre-fetching instruction depends on the interaction of the real data and code with the target pipeline.

When the evaluation uses real data, the performance of the kernel is obtained by simply averaging the run-times of a pre-determined number of runs.

When the kernel uses a training input data, the measurements are filtered. We took the worst value between the three best values of groups with five measurements. This technique filters unwanted oscillations caused by hardware (fluctuations in the pipeline, caches and performance counters) and software (interruptions). In the studied platforms, stable measurements were observed, with virtually no oscillation between independent runs (in a Cortex-A9, we measured oscillations of less than 1 %).

The decision to replace the active function by a new version is taken by simply comparing the calculated run-times.

IV. EXPERIMENTAL SETUP

This section presents the experimental setup. First, we detail the hardware and simulation platforms employed in the experiments. Then, the chosen applications for two case studies are described. The kernel run-times and the auto-tuning overhead are measured through performance counters.

Two ARM boards were used in the experiments. One is the Snowball equipped with a dual Cortex-A9 processor [START_REF] Systems | SKY-S9500-ULP-CXX (aka Snowball PDK-SDK) Hardware Reference Manual[END_REF], an OOO pipeline. The board runs the Linaro 11.11 distribution with a Linux 3.0.0 kernel. The other is the BeagleBoard-xM, which has an IO Cortex-A8 core [START_REF] Beagleboard | BeagleBoard-xM Rev C System Reference Manual[END_REF]. The board runs a Linux 3.9.11 kernel with an Ubuntu 11.04 distribution.

A micro-architectural simulation framework [START_REF] Endo | Micro-architectural simulation of in-order and out-of-order ARM microprocessors with gem5[END_REF] was used to simulate 11 different core configurations. It is a modified version of the gem5 [START_REF] Binkert | The gem5 simulator[END_REF] and McPAT [START_REF] Li | The McPAT framework for multicore and manycore architectures: Simultaneously modeling power, area, and timing[END_REF] frameworks, for performance and power/area estimations, respectively. The 11 configurations were obtained by varying the pipeline type (IO and OOO cores) and the number of VPUs (FP/SIMD units) of one-, two-and three-way basic pipelines. Table 1 in [15] shows the main configurations of the simulated cores, and Table I shows the abbreviations used to identify each core design.

Two kernel-based applications were chosen as case studies to evaluate the proposed online auto-tuning approach. To be representative, one benchmark is CPU-bound and the other is memory-bound. In both applications, the evaluated kernels correspond to more than 80 % of execution time. The benchmarks were compiled with gcc 4.9.3 (gcc 4.5.2 for Streamcluster binaries used in the simulations) and the default PARSEC flags (-O3 -fprefetch-loop-arrays among others). The NEON flag (-mfpu=neon) is set to allow all 32 FP registers to be used. The target core is set (-mcpu option) for the real platforms and the ARMv7-A architecture (-march=armv7-a) for binaries used in the simulations. The deGoal library was also compiled for the ARMv7-A architecture, which covers all real and simulated CPUs.

The first kernel is the euclidean distance computation in the Streamcluster benchmark from the PARSEC 3.0 suite. It solves the online clustering problem. Given points in a space, it tries to assign them to nearest centers. The clustering quality is measured by the sum of squared distances. With high space dimensions, this benchmark is CPU-bound [START_REF] Bienia | Benchmarking modern multiprocessors[END_REF]. In the compilette definition, the dimension (run-time constant) is specialized. The simsmall input set is evaluated with the dimensions 32 (original), 64 and 128 (as in the native input set), which are referred as small, medium and large input sets, respectively.

The second kernel is from VIPS, an image processing application. A linear transformation is applied to an image with the Linux command line vips im_lintra_vec MUL_VEC input.v ADD_VEC output.v Here, input.v and output.v are images in the VIPS XYZ format, and MUL_VEC, ADD_VEC are respectively FP vectors of the multiplication and addition factors for each band applied to each pixels in the input image. Given that pixels are loaded and processed only once, it is highly memory-bound. Indeed, the auto-tuned parameters explored in this work are not suitable for a memory-bound kernel. However, this kind of kernel was also evaluated to cover unfavorable situations and show that negligible overheads are obtained. In the compilette description, two run-time constants, the number of bands and the width of the image, are specialized. Three input sets were tested: simsmall (1600 x 1200), simmedium (2336 x 2336) and simlarge (2662 x 5500).

V. EXPERIMENTAL RESULTS

This section presents the experimental results of the proposed online auto-tuning approach in a CPU-and a memory-bound kernels.

A. Real platforms Table 3 in [15] presents the execution times of all configurations studied of the two benchmarks in the real platforms. Figures 4(a) and 4(b) show the speedups obtained in the Streamcluster benchmark. In average, run-time auto-tuning provides speedup factors of 1.12 in the Cortex-A8 and 1.41 in the A9. The speedup sources come mostly from microarchitectural adaption, because even if the reference kernels are statically specialized, they can not provide significant speedups. The online auto-tuning performance is only 4.6 % and 5.8 % away from those of the best statically auto-tuned versions, respectively for the A8 and A9.

Figures 4(c) and 4(d) show the speedups obtained in the VIPS application. Even with the hardware bottleneck being the memory hierarchy, in average the proposed approach can still speed up the execution by factors of 1.10 and 1.04 in the A8 and A9, respectively. Most of the speedups come from SISD versions (SIMD performances almost matched the references), mainly because in the reference code run-time constants are reloaded in each loop iteration, differently from the compilette implementation. In average, online auto-tuning performances are only 6 % away from the best static ones.

Table II presents the auto-tuning statistics in both platforms. For each benchmark and input set, it shows that between 330 and 858 different kernel configurations could be generated, but in one run this space is limited between 39 and 112 versions, thanks to the proposed two phase exploration (Section III-B). The online statistics gathered in the experiments are also presented. In most cases, the exploration ends very quickly, specially in Streamcluster, in part because of the investment factor. Only with the small input in VIPS, the auto-tuning did not end during its execution, because it has a large tuning space and VIPS executes during less than 700 ms. The overhead of the run-time approach is negligible, between only 0.2 and 4.2 % of the application run-times were spent to generate and evaluate from 28 to 75 kernel versions.

B. Simulated cores

Figure 5 shows the simulated energy and performance of the reference and online auto-tuning versions of the Streamcluster benchmark. In the SISD comparisons, run-time auto-tuning can find kernel implementations with more ILP (Instruction-level parallelism) than the reference code, specially remarkable in the long triple-issue pipelines. The average speedup is 1.58. In the SIMD comparisons, the reference kernel naturally benefits from the parallelism of vectorized code, nonetheless online I. auto-tuning can provide an average speedup of 1.20. Only 6 of 66 simulations showed worse performance, mostly in big cores that quickly executed the benchmark.

In terms of energy, in general, there is no surprise that pipelines with more resources consume more energy, even if they may be faster. However, there are interesting comparisons between equivalent IO and OOO cores. Here, the term equivalent means that cores have similar configurations, except the dynamic scheduling capability.

Still analyzing Streamcluster, when the reference kernels execute in equivalent IO cores, in average their performance is worsened by 16 %, yet being 21 % more energy efficient. On the other hand, online auto-tuning improves those numbers to 6 % and 31 %, respectively. In other words, the online approach can considerably reduce the performance gap between IO and OOO pipelines to only 6 %, and further improve energy efficiency.

It is also interesting to compare reference kernels executed in OOO cores to online auto-tuning versions executed in equivalent IO ones. Despite the clear hardware disadvantage, in average the run-time approach can still provide speedups of 1.52 and 1.03 for SISD and SIMD, and improve the energy efficiency by 62 % and 39 %, respectively.

In the simulations of VIPS, the memory-boundedness is even more accentuated, because the benchmark is only called once and then Linux does not have the chance to use disk blocks cached in RAM. The performance of the proposed approach virtually matched those of the reference kernels. The speedups oscillate between 0.98 and 1.03, and the geometric mean is 1.00. Considering that between 29 and 79 new kernels were generated and evaluated during the benchmark executions, this demonstrates that the proposed technique has negligible overheads if auto-tuning can not find better versions.

In this study, we observed correlations between auto-tuning parameter and pipeline features. The results corroborate the capability of the auto-tuning system to adapt code to different micro-architectures. On the other hand, precise correlations could not be identified, because the best auto-tuning parameters depend on several factors (system load, initial pipeline state, cache behavior, application phases, to name a few), whose behaviors can not be easily modeled in complex systems. Online auto-tuning is a very interesting solution in this scenario.

VI. CONCLUSION

In this paper, we presented an approach to implement runtime auto-tuning kernels in short-running applications. This work advances the state of the art of online auto-tuning. To the best of our knowledge, this work is the first to propose an approach of online auto-tuning that can obtain speedups in short-running kernel-based applications. Our approach can both adapt a kernel implementation to a micro-architecture unknown prior compilation and dynamically explore autotuning possibilities that are input-dependent.

We demonstrated through two case studies in real and simulated platforms that the proposed approach can speedup a CPU-bound kernel-based application up to 1.79 and 2.53, respectively, and has negligible run-time overheads when autotuning does not provide better kernel versions. In the second application, even if the bottleneck is in the main memory, we observed speedups up to 1.30 in real cores, because of the reduced number of instructions executed in the auto-tuned versions.

Energy consumption is the most constraining factor in current high-performance embedded systems. By simulating the CPUbound application in 11 different CPUs, we showed that runtime auto-tuning can reduce the performance gap between IO and OOO designs from 16 % (static compilation) to only 6 %. In addition, we demonstrated that online micro-architectural adaption of code to IO pipelines can in average outperform the hand vectorized references run in similar OOO cores. Despite the clear hardware disadvantage, online auto-tuning in IO CPUs obtained an average speedup of 1.03 and an energy efficiency improvement of 39 % over the SIMD reference in OOO CPUs.

(a) 1 -

 1 D projection of the auto-tuning exploration space. Dimension = 32 (b) 1-D projection of the auto-tuning exploration space. Dimension = 128

Fig. 2 :

 2 Fig. 2: Architecture of the run-time auto-tuning framework.

Fig. 3 :

 3 Fig. 3: Main loop of the deGoal code to auto-tune the euclidean distance kernel in the Streamcluster benchmark. The first function parameter is the specialized dimension, and the other four are the auto-tuned parameters (highlighted variables).

Fig. 4 :

 4 Fig. 4: Speedup of the specialized reference and the auto-tuned applications in the real platforms (normalized to the reference benchmarks).

  (a) Small input set. (b) Medium input set. (c) Large input set.

Fig. 5 :

 5 Fig. 5: Speedup and energy efficiency improvement of online auto-tuning over the references codes in the Streamcluster benchmark, simulating the 11 cores. Core abbreviations are listed in TableI.

  1 dist_gen(int dim, int vectLen, int hotUF, int coldUF,

		int pldStride)
	2 {
	3	numIter = function(dim, vectLen, hotUF, coldUF);
	4	(...)
	5 #[ loop #(numIter)	]#
	6	for (j = 0; j < coldUF; ++j) {
	7	for (i = 0; i < hotUF; ++i) {
	8 #[	lw Vc1[#(i)], coord1	]#
	9 #[	lw Vc2[#(i)], coord2	]#
	10	if (pldStride != 0) {
	11 #[	pld coord1, #((vectLen-1) * 4 + pldStride) ]#
	12 #[	pld coord2, #((vectLen-1) * 4 + pldStride) ]#
	13	}
	14 #[	sub Vc1[#(i)], Vc1[#(i)], Vc2[#(i)]	]#
	15 #[	mac Vresult, Vc1[#(i)], Vc1[#(i)]	]#
	16
	17 #[	add coord1, coord1, #(vectLen * 4)	]#
	18 #[	add coord2, coord2, #(vectLen * 4)	]#
	19	}
	20	}
	21 #[ loopend	]#
	22	(...)
	23 #[ add result, Vresult	]#
	24	(...)
	25 }

TABLE I :

 I Abbreviation of the simulated core designs and CPU areas

	Abbrev.	Width	Type	VPUs	Area (mm 2 ) Core L2 Total
	SI-I1	1	IO	1	0.45	1.52	1.97
	TI-I1	3	IO	1	1.81	5.88	7.70
	TI-I2	3	IO	2	2.89	5.88	8.78
	DI-I1	2	IO	1	1.00	3.19	4.19
	TI-I3	3	IO	3	3.98	5.88	9.86
	DI-I2	2	IO	2	1.48	3.19	4.67
	TI-O1	3	OOO	1	2.08	5.88	7.97
	DI-O1	2	OOO	1	1.15	3.19	4.34
	TI-O2	3	OOO	2	3.21	5.88	9.10
	DI-O2	2	OOO	2	1.67	3.19	4.86
	TI-O3	3	OOO	3	4.35	5.88	10.2

ACKNOWLEDGMENTS

This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01) funded by the French program Investissement d'avenir.


Carlos Canudas-De-Wit

Antonella Ferrara

* Carlos

A Variable-Length Cell Road Traffic Model: Application to Ring Road Speed Limit Optimization

In this paper we propose a variable speed control strategy based on a new Variable-Length cell transmission Model (VLM). The VLM differs from the standard Cell

Transmission model in that only a limited number of (variable length) cells are used. Road network is subdivided into several sections which are assumed to be composed of a downstream congested cell followed by a free upstream cell. Both cells have variable lengths and are described by two lumped densities (one congested, the other free). One more state describing the length variation completes the model for each section. The paper also introduces an associated optimal speed control design based on the proposed VLM. The method is illustrated on a closed ring road and is shown to optimize the traveling time per turn.

I. INTRODUCTION

Modern technologies are now a well recognized vector to alleviate traffic congestions problems. First steep is to equip the roads with sensors collecting [START_REF] Canudas-De-Wit | Grenoble Traffic Lab: An Experimental Platform for Advanced Traffic Monitoring and Forecasting[END_REF] and processing data [START_REF] Smadi | Advantages of Using Innovative Traffic Data Collection Technologies[END_REF], in order to decide optimal traffic control policies based on reliable traffic models [START_REF] Horowitz | Design, field implementation and evaluation of adaptive ramp metering algorithms[END_REF], [START_REF] Jacquet | Non-Local Feedback Ramp Metering Controller Design[END_REF], [START_REF] Jacquet | Optimal Control of Systems of Conservation Laws and Application to Non-Equilibrium Traffic Control[END_REF], [START_REF] Lu | A new approach for combined freeway variable speed limits and coordinated ramp metering[END_REF], [START_REF] Papageorgiou | Freeway ramp metering: an overview[END_REF], [START_REF] Ferrara | Freeways as Systems of Systems: A Distributed Model Predictive Control Scheme[END_REF], [START_REF] Ferrara | Event-triggered model predictive schemes for freeway traffic control[END_REF]. Physicists, mathematicians and engineers have developed models of vehicular traffic for almost fifty years [START_REF] Treiber | Traffic flow dynamics -Data, models and simulation[END_REF], but models useful for control design are still a limited number. Control designers have preference for simple macroscopic models capturing fundamental physical features like vehicle conservation and shock wave propagation, often inspired by analogies from flows dynamics in fluids or gases.

For instance, the well-known Daganzo's Cell Transmission Model (CTM) [START_REF] Daganzo | The Cell Transmission Model: A Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory[END_REF] comes from a discretization into cells (corresponding to small portions of the road) of the LWR continuum model proposed by Lighthill and Whitham [START_REF] Lighthill | On kinematic waves II: A theory of traffic flow on long crowded roads[END_REF], and Richards [START_REF] Richards | Shock Waves on the Highway[END_REF]. The CTM keeps track of the number of vehicles in each cell, and at every time step determines the number of vehicles that cross the boundaries between adjacent cells. The interface flows between cells can be captured by the well-known and compact demand/supply formulation (see [START_REF] Gomes | Behavior of the Cell Transmission Model and Effectiveness of Ramp Metering[END_REF] for a complete study of CTM major mathematical properties).

One limitation of the CTM model is due to its complexity which is determined by the number of cells into which the considered road stretch is subdivided. Using the CTM to model large scale traffic networks results in a highdimensional switched linear model with exponential complexity.

The previous considerations have been the motivations for searching new low-dimensional macroscopic models allowing tractable control design with reduced complexity. Among those there is the so-called Link-Transmission model (LTM) which is basically a CTM with a single cell, but with the limitation that the shock propagation is only possible between links. This implies that the shock waves propagation inside the link is not captured, while it is captured by the CTM does (see [START_REF] Yperman | The link Transmission Model for Dynamic Network Laoding[END_REF] for further discussion). The use of this model is often limited to the context of traffic light control in urban network.

Store and forward models are some sort of queue models integrating the difference between the total inflows and outflows. The model traces back to the original works of [START_REF] Gazis | The oversaturated intersection, 2nd International Symposium on Traffic Theory[END_REF] [START_REF] Gazis | The oversaturated intersection, 2nd International Symposium on Traffic Theory[END_REF] and has since then been used in various road traffic control optimization studies [START_REF] Aboudolas | Store-andforward based methods for the signal control problem in largescalecongested urban road networks[END_REF]. Those models integrate several simplifications at the cost of the loss of many of the model kinematic original properties. Stochastic version of this models have been also considered [START_REF] Varaiya | Max pressure control of a network of signalized intersections[END_REF]. A common observed limitation is that queues are "vertical" with unlimited capacity. Therefore, it does not permit saturation of a downstream link that blocks the movement of vehicles from an upstream link. This may result in motion-blocking problems as observed by [START_REF] Varaiya | Max pressure control of a network of signalized intersections[END_REF], [START_REF] Aboudolas | A rolling-horizon quadratic-programming approach to the signal control problem in large-scale congested urban road networks[END_REF], and in a substantial deviation from waves propagations as predicted from the original LWR model.

In this paper, we propose a new aggregated Variable-Length cell transmission Model (VLM) aiming also at complexity reduction by limiting the number of states per link, which stems from the ground base ideas presented in [START_REF] Canudas-De-Wit | Best-effort Highway Traffic Congestion Control via Variable Speed Limits[END_REF]. In this paper we present an improved model with respect to that in [START_REF] Canudas-De-Wit | Best-effort Highway Traffic Congestion Control via Variable Speed Limits[END_REF], showing in particular that its derivation results from averaging the original LWR model while ensuring that the wave propagations are suitable considered, not only at the level of the link but also between neighbor links. Essentially, the model consists of three lumped state variables per link one of which explicitly describes the position of the congestion wave front (or the queue length). In this paper we also formally address the most prominent mathematical model properties including; the consistency with respect to its inherent mass (or vehicle) conservation law, and the capability of accurately describing the propagation of shock and advection waves. We also equipped the model with small fixed boundary cells to avoid singularities when the link is either fully congested or fully free.

The proposed model can be satisfactorily used in several possible scenarios. Moreover, it possesses a sufficient level of accuracy and the appropriate simplicity to be adopted as a basis to design controllers for traffic systems. This is testified by its effective use in the context of optimal speed design illustrated in [START_REF] De Nunzio | Urban Traffic Ecodriving: A Macroscopic Steady-State Analysis, 2014 European Control Conference[END_REF], [START_REF] De Nunzio | Urban Traffic Eco-Driving: Speed Advisory Tracking, 53rd IEEE Conference on Decision and Control[END_REF]. Even in the present paper, to better emphasize the control design oriented nature of the VSL model, we present the model utilization in a closed ring road, and the possibility of exploiting such a model to optimize the speed limits, so as to improve the traveling time in that scenario.

Φ M ρ * ρ Φ(ρ) ρ M -w v

II. PRELIMINARIES: CONSERVATION LAWS AND CTM

The simplest continuous macroscopic traffic model is the so-called LWR model, proposed by Lighthill, Whitham [START_REF] Lighthill | On kinematic waves II: A theory of traffic flow on long crowded roads[END_REF], and Richards [START_REF] Richards | Shock Waves on the Highway[END_REF]. It is based on the vehicle conservation's principle, and on the assumption that the traffic can be described by the empiric relation between flow, ϕ, and density, ρ, as: ϕ = Φ(ρ), where the function Φ(•) is called Fundamental Diagram (see Fig. 1), which can be defined in its simplest form by a triangle given by

Φ(ρ) = min{vρ, -w(ρ -ρ M )}
where v is the maximum velocity at free-flow, and -w defines the speed at which congestion travels upstream. Φ(ρ) has its maximum at Φ M = Φ(ρ * ) describing the maximum capacity of the road. The critical density ρ * defines the boundary between the decongested and the congested modes, while ρ M is the maximum density that the road can withstand.

The evolution of the number of vehicles, N , within any spatial section (0, L) is given by the conservation law

d dt N = ϕ in -ϕ out , N = L 0 ρ(x, t)dx (1)
where ϕ in and ϕ out are the input (at x = L) and output (at x = 0) flows at the boundaries of the road section of length L. Equation (1) can be rewritten (see [START_REF] Lighthill | On kinematic waves II: A theory of traffic flow on long crowded roads[END_REF]) as a hyperbolic equation involving only the density

∂ t ρ + ∂ x Φ(ρ) = ∂ t ρ + ∂ ρ Φ • ∂ x ρ = 0 (2)
The macroscopic continuous density dynamics is then given by the LWR Cauchy problem described by [START_REF] Aboudolas | A rolling-horizon quadratic-programming approach to the signal control problem in large-scale congested urban road networks[END_REF] with the initial condition ρ(x, 0) = ρ 0 (x).

Assume now that the road section is subdivided into n-cells of constant length ∆l i . Let us denote with ρ i the density of the i th cell of the section. Then, the number of vehicles per cell can be computed as

N i = ρ i ∆l i .
A well-known efficient first-order numerical method to integrate (2) is the Godunov scheme [START_REF] Godunov | A difference scheme for numerical solution of discontinuous solution of hydrodynamic equations[END_REF]. This process leads to discrete space-time equations named the Cell Transmission Model (CTM) originally proposed by Daganzo in [START_REF] Daganzo | The Cell Transmission Model: A Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory[END_REF], which in its continuous-time version takes the following form

ρi (t) = 1 ∆l i ϕ i-1 (t) -ϕ i (t) (3)
with ϕ 0 = ϕ in (t), ϕ n = ϕ out (t), ϕ i being the interface flow between the cells i and i + 1 given as

ϕ i = min{D i , S i+1 } (4)
with

D i = min{v i ρ i , ϕ M,i }, S i+1 = min{ϕ M,i+1 , w i+1 (ρ M,i+1 -ρ i+1 )}
where the demand D i is the flow that can be delivered by the cell i to the cell i + 1, while the supply S i+1 is the flow that can be received by the cell i + 1 from the cell i; ϕ M,i is the maximum flow allowed by the capacity of cell i, ρ M,i is the jam density (i.e. the maximum density that can be reached), v i corresponds to the free flow speed and w i is the congestion wave speed in cell i.

L l

Free cell

Congested cell N f , ρ f N c , ρ c 0 ϕ in ϕ I ϕ out ǫ L -ǫ

III. NEW MACROSCOPIC MODEL WITH VARIABLE-LENGTH CELLS

Consider a simple road section described by two cells of variable length: a downstream congested cell, of length l, and an upstream free cell, of length L -l, where L is the total length of the section. The former cell is characterized by the lumped (or averaged) "congested density" ρ c , the latter by the lumped (or averaged) "free density" ρ f . Note that l = l(t) is time-varying and specifies the position of the congestion wave front, see Fig. 2 (with ǫ = 0). Then, in contrast to the n-fixed cells model (3), the new macroscopic traffic model introduced in this paper, named Variable-Length cell Model (VLM), consists only of three lumped state variables, i.e. ρ f , ρ c and l.

A. Conservation law for the variable-length cells

Consider for consistency with the grow direction of l shown in Fig. 2, that the x-axis is oriented with l from right (downstream) to left (upstream). Therefore, the conservation law (2) now can be written as ∂ t ρ = ∂ x Φ(ρ), where we have replaced ∂ x with -∂ x . Moreover, let s(t) be the continuous variable describing the time-varying shock wave position along the x axis. Relying on s(t), the following lumped (averaged) densities variables ρ f and ρ c are defined:

ρ f = 1 L -s L s ρ(x, t)dx (5a) ρ c = 1 s s 0 ρ(x, t)dx (5b)
Note that the density distribution is discontinuous at the boundary x = s. Its left, ρ -, and right, ρ + , limits can be written as

ρ -= ρ -(t) = lim x→s -ρ(x, t), ρ + = ρ + (t) = lim x→s + ρ(x, t)
The time-derivatives of the lumped variables are given by

ρf = 1 L -s L s ∂tρ(x, t) dx -ρ -ṡ + ṡ (L -s) 2 L s ρ(x, t)dx ρc = 1 s s 0 ∂tρ(x, t) dx + ρ + ṡ - ṡ s 2 s 0 ρ(x, t)dx
Using ∂ t ρ(x, t) = ∂ x Φ(ρ) in the previous integrals, and the definitions (5a)-(5b), ρf rewrites as

ρf = 1 L -s Φ(ρ(L)) -Φ(ρ -) -ρ -ṡ + ṡ (L -s) ρ f = 1 L -s ϕ in -Φ(ρ -) -ρ -ṡ + ṡ (L -s) ρ f (6)
with the boundary upstream flow Φ(ρ(L)) = ϕ in . Similarly, we get for ρc

ρc = 1 s Φ(ρ + ) -Φ(ρ(0)) + ρ + ṡ - ṡ s ρ c = 1 s Φ(ρ + ) -ϕ out + ρ + ṡ - ṡ s ρ c (7)
where Φ(ρ(0)) = ϕ out , and the boundary densities and flows at the shock wave front are denoted as ρ -, ρ + , and Φ(ρ + ), Φ(ρ -), respectively. From the Rankine-Hugoniot jump condition, the shock wave speed, ṡ can be written, in the l coordinates, as

ṡ = Φ(ρ -) -Φ(ρ + ) ρ + -ρ - (8)
implying that Φ(ρ -) + ρ -ṡ = Φ(ρ + ) + ρ + ṡ. The balance between the first term (left-flow) and the second term (outflow) is a direct consequence of the principle of vehicle conservation at the interface. The interface flow ϕ I in the moving shock wave frame is given by

ϕ I = Φ(ρ + ) + ρ + ṡ = Φ(ρ -) + ρ -ṡ (9)
As such, equations ( 6) and ( 7) can be rewitten as

ρf = 1 L -s [ϕ in -ϕ I + ṡρ f ] (10) ρc = 1 s [ϕ I -ϕ out -ṡρ c ] (11)
Note all the variables in the previous equations, except for s, are expressed in the lumped form. In order to arrive at a description which only depends on lumped variables, an approximation of the shock wave position s(t), denoted with l(t), is introduced. The time evolution of l(t)

∈ (0, L) is proposed to be l = Φ(ρ f ) -Φ(ρ c ) ρ c -ρ f ( 12
)
which can be regarded as the lumped version of (8). More specifically, in [START_REF] Gomes | Behavior of the Cell Transmission Model and Effectiveness of Ramp Metering[END_REF] we assume that Φ(ρ -) and Φ(ρ + ) are approximated by Φ(ρ f ) and Φ(ρ c ), respectively. This approximation makes sense as the densities in each of the variable cells are assumed to be scalar and constant over the space variables, and not distributions.

Then on the basis of ( 12), equations ( 10) and ( 11) can be rewritten as

ρf = 1 L -l ϕ in -ϕ I + lρ f (13) ρc = 1 l ϕ I -ϕ out -lρ c (14)

B. Full dynamics

Note that the lumped model provides a piece-wise value of the traffic density for each of the two portions (the free and the congested one) of the road section, in opposition to the spatially distributed formulation. The boundary density values in the lumped case are then given as ρ + = ρ c , and ρ -= ρ f so that equation ( 9) writes now as

ϕ I = Φ(ρ c ) + ρ c l = Φ(ρ f ) + ρ f l (15)
from which we get

-ϕ I + ρ f l = -Φ(ρ f ) and ϕ I -ρ c l = Φ(ρ c ) (16)
Substitution of these expression into ( 13) and ( 14), together with [START_REF] Gomes | Behavior of the Cell Transmission Model and Effectiveness of Ramp Metering[END_REF], gives

ρf = 1 L -l [ϕ in -Φ(ρ f )] (17)
ρc = 1 l [Φ(ρ c ) -ϕ out ] (18)
l = Φ(ρ f ) -Φ(ρ c ) ρ c -ρ f (19)
Equations ( 17)-( 19) define the new macroscopic traffic model we propose. This model is a lumped variables model based on three state variables only. As for its structure, it is simpler than classical continuous macroscopic models, as well as of n-fixed cells models. Nevertheless, as discussed in the next section, it features interesting properties which allow it to capture the relevant phenomena of traffic dynamics.

Remark 1

The VLM owns fundamental mathematical properties consistent with the constructive assumptions. For instance, it can be shown that densities ρ c , and ρ f remain in their definition domain Ω f = {ρ : ρ ∈ [0, ρ * ]}, and Ω c = {ρ : ρ ∈ [ρ * , ρ M ]} as long the density initial conditions are taking values inside the respective domains. However, to ensure that l ∈ Ω l , where Ω l = {l : l ∈ (0, L)}, additional mechanisms need to be implemented to treat the singular points where l is equal to either 0 or L.

C. Special cases of singular points

The VLM model presents three degenerate cases when l = 0, l = L, and ρ f = ρ c , respectively. This subsection describes how the original model can be reformulated to cope with such cases.

1) Singular points for l(t): Consider first the case where the variable length l(t) approaches one of the two possible boundary values. In those cases, the idea is to create a εboundary layer at the two extremes of the considered road section and stop the evolution of l(t) when it reaches the εboundary layer borders. When this happens, the model collapses into the standard CTM model with fixed length cells, and the density variables evolve according to the conventional "Demand-Supply" mechanism, with the standard notation

D(ρ) = min{vρ, ϕ M }, S(ρ) = min{-w(ρ -ρ M ), ϕ M }
This idea is sketched in Fig. 2.

Let us consider an arbitrarily small ε such that 0 < ε ≪ L. Then the following two conditions can be introduced:

C 0 = {(l = ε) ∩ (D(ρ f ) ≤ S(ρ c ))} (20) C L = {(l = L -ε) ∩ (D(ρ f ) ≥ S(ρ c ))} (21)
Condition C 0 implies that the lower extreme is reached while the congestion front wave is moving downstream. Symmetrically, condition C L indicates that the upper extreme is reached while the congestion front wave is moving upstream. For those specific cases, the following model modification is proposed:

• If C 0 holds, the interface flow is ϕ I = min{D(ρ f ), S(ρ c )} = D(ρ f ), and then the model becomes

ρf = 1 L -ε [ϕ in -D(ρ f )] (22) ρc = 1 ε [D(ρ f ) -ϕ out ] (23)
l = 0 (24)
Note that in this case, the variation domain of the state variables is partially modified. The congested density variable can now take values smaller than the critical density ρ * , i.e. ρ c ∈ [0, ρ M ], while the free density variable remains in its original domain, i.e. ρ f ∈ Ω f .

• If C L holds, the interface flow is ϕ I = min{D(ρ f ), S(ρ c )} = S(ρ c ), and then the model becomes

ρf = 1 ε [ϕ in -S(ρ c )] (25) ρc = 1 L -ε [S(ρ c ) -ϕ out ] (26)
l = 0 (27)
In this case, the free density variable can take values larger than the critical density ρ * , i.e.

ρ f ∈ [0, ρ M ],
while the congested density variable remains in its original domain, i.e. ρ c ∈ Ω c . Now consider the third singular point, i.e. ρ f = ρ c . From the fundamental diagram in Fig. 1, it is apparent that this singularity only occurs at ρ f = ρ c = ρ * , where Φ(ρ f ) = Φ(ρ c ) = ϕ M . This implies that equation [START_REF] Richards | Shock Waves on the Highway[END_REF] becomes undetermined. As a consequence, in order to extend the proposed model validity to this case, a regularization mechanism needs to be introduced. To this end, let e f = ρ f -ρ * ≤ 0 and e c = ρ c -ρ * ≥ 0, we have that e

l = -v|e f | + w|e c | V (e f , e c ) + σ(e f , e c )
, lim

V (e f ,ec)→0 l = 0 is proposed, which in the original system coordinates writes as

l = Φ(ρ f ) -Φ(ρ c ) ρ c -ρ f + σ(ρ c , ρ f ) (28) with σ(ρ c , ρ f ) = ǫe -α(ρ f -ρc) 2 .

D. Singularity-free full VLM

Considering the different regularizations introduced previously, and noticing that l = ε, and l = L -ε, at C 0 and C L , respectively, the full model can be compactly written as follows

ρf = 1 L -l    ϕ in -D(ρ f ) if C 0 ϕ in -S(ρ c ) if C L ϕ in -Φ(ρ f ) else (29) ρc = 1 l    D(ρ f ) -ϕ out if C 0 S(ρ c ) -ϕ out if C L Φ(ρ c ) -ϕ out else (30) l = 0 if C 0 C L Φ(ρ f )-Φ(ρc) ρc-ρ f +σ(ρc,ρ f ) else (31)
IV. RAREFACTION WAVES IN THE VLM Model ( 29)-( 31) has been designed under the implicit assumption of the existence of a bottleneck originating an important change of capacity at the boundary l = 0, and producing a congestion whose origin in the space remains fixed. However, there are other situations in which both spatial boundaries of the congestion may evolve in time. This is the case when a sudden change from the congested mode to the free mode occurs at the downstream boundary (i.e. because of the traffic light switching from red to green, or of a car accident being eventually resolved) producing a rarefaction (or fan) wave at the downstream boundary. Consider the variables as defined in Fig. 3, with ρ u f , ρ c , ρ r , ρ d f being the densities, and l u , l r , l d being the associated cell lengths subject to the following constraints: L > l u ≥ l r ≥ l d > 0, and 0 < ρ d f < ρ * < ρ c < ρ M . The left and the right boundary of the rarefaction wave are indicated by l r , l d respectively. Assuming the rarefaction wave is initiated at l = l 0 , the solution of the Riemann problem with initial left and right distributions ρ -= ρ c , and

l ρ * ρ u f l u l d ρ(x) l r lr = w ρ c ρ r ρ d f ld = -v lu = Φ(ρc)-Φ(ρ u f ) ρ u f -ρc
ρ + = ρ d f is: ρ(l, t) =    ρ c (l -l 0 ) < Φ ′ (ρ c )t, ρ * Φ ′ (ρ c )t ≤ (l -l 0 ) < Φ ′ (ρ d f )t, ρ f (l -l 0 ) ≥ Φ ′ (ρ d f )t. (32)
For the triangular piece-wise fundamental diagram, we have Φ ′ (ρ c ) = w, and Φ ′ (ρ d f ) = -v (in the l-direction). We have then the formation of two shock waves: one traveling at velocity w, and another traveling at velocity -v, with critical density ρ r = ρ * as the intermediate state.

The model can now be constructed by following the same ideas on vehicles conservation laws used previously, i.e.

Ṅ u f = ϕ in -ϕ u I (33) Ṅc = ϕ u I -ϕ r I (34) Ṅr = ϕ r I -ϕ d I (35) Ṅ d f = ϕ d I -ϕ out (36)
with

N u f = (L -l u )ρ u f , N c = (l u -l r )ρ c , N r = (l r -L d )ρ r , N d f = l d ρ d f
, and ϕ u I , ϕ r I , ϕ d I being the interface flows at l u , l r , l d , respectively. As before, each interface flow can be computed using the speed function l

-/+ = f (ρ -, ρ + ) = Φ(ρ + )-Φ(ρ -) ρ --ρ +
of each interface, and its corresponding left and right densities ρ -, ρ + . This gives: ϕ

-/+ I = ρ - l-/+ + Φ(ρ -) = ρ + l-/+ + Φ(ρ +
). The full model is now given by

ρu f = 1 L -l u ϕ in -Φ(ρ u f ) (37) ρc = 0, (38) ρr
= 0 (39)

ρd f = 1 l d Φ(ρ d f ) -ϕ out (40)
and

lu = f (ρ u f , ρ c ) if l u > l r f (ρ u f , ρ r ) = -v if l u = l r (41) lr = f (ρ c , ρ r ) = w if l u > l r f (ρ u f , ρ r ) = -v if l u = l r (42) ld = f (ρ r , ρ d f ) = -v if l r ≥ l d (43) with initial conditions ρ u f (0), ρ c (0), ρ r (0) = ρ * , ρ d f (0), and l u f (0) > l r (0) = l d f (0) = l 0 .

V. VARIABLE SPEED OPTIMIZATION IN A CLOSED RING

ROAD

In this section, a case study of a closed ring-road scenario shown in Fig. 4 is considered to illustrate the main model properties and how the model can be used for variable speed optimization.

A. Ring-road Variable Length model

Let l u = Rθ u , l r = Rθ r , l d = Rθ d , ρ u f = ρ d f = ρ f , ϕ in = ϕ out . Model (37)-(43), in the set Ω θ = {(θ u , θ r , θ d ) : θ u ≥ θ r ≥ θ d } \ {(θ u , θ r , θ d ) : θ u = θ r = θ d },
can be written in the circular coordinates as,

ρf = 0, ρ f (0) = ρ 0 f (44) ρc = 0, ρ c (0) = ρ 0 c (45) ρr = 0, ρ r (0) = ρ * (46) θu = lu R = 1 R f (ρ f , ρ c ) if θ u > θ r f (ρ f , ρ r ) = -v if θ u = θ r (47) θr = lr R = 1 R f (ρ c , ρ r ) = w if θ u > θ r f (ρ f , ρ r ) = -v if θ u = θ r (48) θd = ld R = 1 R f (ρ r , ρ f ) = -v if θ r ≥ θ d f (ρ r , ρ c ) = w if θ d = θ u (49)
with initial conditions (θ 0 u , θ 0 r , θ 0 d ) ∈ Ω θ .

B. Equilibrium points of the VLM of the ring road

The model ( 44)-(49) has in general two classes of equilibrium points depending on the initial conditions. One class (Class A) is composed of one part in free-flow and the other at the critical density, while the second class (Class B) consists of one part in congested mode, and the other at the critical density, see Fig. 4.

Consider the following definitions:

∆θ f (t) = 2π + θ d (t) -θ u (t) ∆θ c (t) = θ u (t) -θ r (t) ∆θ * (t) = θ r (t) -θ d (t)
with the notation ∆θ (•) (0) = ∆θ 0 (•) .

Lemma 1 Consider the ring-road model (44)-( 49), with initial conditions θ 0 u > θ 0 r ≥ θ 0 d . Let

a = ρ 0 f ρ 0 c -ρ 0 f , b = Φ(ρ 0 c ) ρ 0 c -ρ 0 f , β = ∆θ 0 f ∆θ 0 c c(β, a, b) = b(1 + β) + βw a(1 + β) + 1 , f 0 = f (ρ 0 f , ρ 0 c )
Then: A) The system converges in a finite time t 1 = R ∆θ 0 c w-f0 , to the Class-A equilibrium points if initial conditions satisfy:

f 0 + v w -f 0 < β
with the final angles given as:

∆θ c (t 1 ) = 0, ∆θ f (t 1 ) = ∆θ 0 f - v + f 0 w -f 0 ∆θ 0 c ∆θ * (t 1 ) = ∆θ 0 * + v + w w -f 0 ∆θ 0 c
with ∆θ f (t 1 ) + ∆θ * (t 1 ) = 2π. B) The system converges in a finite time t 2 = R ∆θ 0 f v+f0 , to the Class-B equilibrium points if initial conditions satisfy:

f 0 + v w -f 0 > β
with the final angles given as:

∆θ c (t 2 ) = ∆θ 0 c - w -f 0 v + f 0 ∆θ 0 f , ∆θ f (t 2 ) = 0, ∆θ * (t 2 ) = ∆θ 0 * + v + w v + f 0 ∆θ 0 f with ∆θ c (t 2 ) + ∆θ * (t 2 ) = 2π.
Proof. The proof is straightforward by computing the angle evolutions of the solutions

θ r (t) = θ 0 r + w R t θ u (t) = θ 0 u + f 0 R t θ d (t) = θ 0 d - v R t
and noticing that f 0 can be rewritten as

f 0 = φ(ρ 0 f ) -Φ(ρ 0 c ) ρ 0 c -ρ 0 f = v ρ 0 f ρ 0 c -ρ 0 f - Φ(ρ 0 c ) ρ 0 c -ρ 0 f = av -b
For Class A, we require the existence of a finite time t 1 such that: i) θ r (t 1 ) = θ u (t 1 ), and ii) θ u (t 1 ) < 2π + θ d (t 1 ). Now, from the above solutions, we get

θ 0 r + w R t 1 = θ 0 u + f 0 R t 1 θ 0 u + f 0 R t 1 < 2π + θ 0 d - v R t 1
Then, t 1 is obtained from the first equation. The velocity range comes from the second equations where we replace t 1 , and noting the fact that f 0 < 0, and hence av -b < 0.

For Class B, we require the existence of a finite time t 2 such that: i) θ u (t 2 ) = 2π + θ d (t 2 ), and ii) θ u (t 2 ) > θ r (t 2 ). Now, from the above solutions, we get

θ 0 u + f 0 R t 2 = 2π + θ 0 d - v R t 2 θ 0 u + f 0 R t 2 > θ 0 r + w R t 2
As before, t 2 is obtained from the first equation. The velocity range comes from the second equation where we replace t 2 . ⋄ ⋄ ⋄ Figure 5 shows the velocity admissible domain as a function of the initial angles defined by β. Note this domain corresponds to free-flow velocities which are consistent with the model densities definition. For instance, the lower admissible value v m = b/(a + 1) is equal to Φ(ρ 0 c )/ρ 0 c , and maximum velocity bound

v M = (b + w)/a is equal to -w(1 -ρ M /ρ 0 f ). As long as v ∈ Ω v = (v m , v M ) the evolution of ρ f (t), ρ c (t)
will remain in the corresponding free and congested part of the fundamental diagram. The curve c(β, a, b) is the velocity boundary between the two possible equilibria classes.

Note that this allows for some flexibility in the selection of v ∈ Ω v , and therefore opens the possibility to optimize

v opt = min v∈Ωv ,i∈1,2 J(v, i), where J(v, i) = R ∆θ * (t i ) v + ∆θ f (t i ) v + ∆θ c (t i ) v m .
A particular case of interest is to find the optimal free-speed for the Class-A equilibria, which can be easily computed by observing Figure 5, that is

v opt = min v∈Ωv ,i=1 J(v, 1) = c(β, a, b) leading to J(v opt , 1) = 2πR/c(β, a, b).

C. Simulation of the ring road

The two possible cases (A and B) mentioned in Subsection V-B can be reproduced in simulation. The considered physical parameters of the model are given in table V-C. The initial conditions are ρ 0 f = 30veh/km, ρ 0 c = 150veh/km for case A, and ρ 0 f = 10veh/km, ρ 0 c = 100veh/km for case B. In both cases the radius is equal to R = 0.8km, and the initial congestion length is l u = 2π 3 R = 1.67km (with θ u (0) = 2π 3 , andθ r (0) = 0). Vehicles are assumed to flow in a clockwise direction. Due to these initial conditions, in case A the rotation speed is θu = 3.33km/h, while in case B is θu = -24.44km/h. Results are shown in Fig. 6 for both cases. Six different snapshots are reported. From the figure, it is possible to observe how the rarefaction process evolves and how the equilibria are reached. As expected, two possible equilibria occur. In case A, after that the rarefaction wave is produced, θ u reaches θ r and the equilibrium is given by a zone at ρ * and by one at ρ 0 f . In case B, θ u reaches θ d and the equilibrium is given by a zone at ρ 0 c and by one at ρ * .

VI. CONCLUSIONS

A new Variable-Length cell transmission Model (VLM) has been presented in the paper as a basis to develop variable speed traffic control strategies. The proposed model differs from the standard Cell Transmission model since it consists of only three lumped state variables: two lumped densities and a third state variable describing the position of the congestion wave front. A modification of the model to capture also the rarefaction wave phenomenon is provided in the paper. Moreover, the major mathematical properties of the model are discussed. The paper also addresses the beneficial use of the new model in dealing with optimal speed control design. The method is illustrated on a closed ring road, where the model facilitates the determination of the free-speed such that the traveling time per turn is minimized.

Fig. 1 .

 1 Fig. 1. Schematic representation of the triangular fundamental diagram.

Fig. 2 .

 2 Fig. 2. Schematic diagram of the two-cell variable-length model VLM with boundaries cells introduced to avoid singularities at l = 0, and l = L.

  f = -|e f |, and e c = |e c |. Hence, (19) can be rewritten as l = -v|e f | + w|e c | |e f | + |e c | Let us denote with V (e f , e c ) = |e f | + |e c |, and with σ(e f , e c ) = ǫe -αV 2 (e f ,ec) , ǫ and α being strictly positive coefficients, a suitable regularizing term. Then, the following regularization for[START_REF] Richards | Shock Waves on the Highway[END_REF]

Fig. 3 .

 3 Fig. 3. Illustration of the variables involved in the model including rarefaction waves.

Remark 2 Fig. 4 .

 24 Fig. 4. Illustration of the ring-road scenario. Left figure shown the scenario with the associated variables. Center (class A) and right (class B) figures shown the two possible equilibria classes.

Fig. 5 .

 5 Fig. 5. Admissible velocity domain as a function of the initial conditions. The domain is limited by v ∈ (vm, v M ), where vm = b/(a + 1), v M = (b + w)/a

VII. ACKNOWLEDGEMENTS

Authors would like to acknowledge Tomas Pippia for helping with the simulations of this paper.


Tiphaine Caudrelier
email: tiphaine.caudrelier@gipsa-lab.grenoble-inp.fr

Pascal Perrier

Jean-Luc Schwartz

Amélie Rochet-Capellan
email: amelie.rochet-capellan@gipsa-lab.grenoble-inp.fr

Does auditory-motor learning of speech transfer from the CV syllable to the CVCV word?

Keywords: speech units, speech goals, speech production, sensorimotor learning, transfer, auditory feedback perturbation

Speech is often described as a sequence of units associating linguistic, sensory and motor representations. Is the connection between these representations preferentially maintained at a specific level in terms of a linguistic unit? In the present study, we contrasted the possibility of a link at the level of the syllable (CV) and the word (CVCV). We modified the production of the syllable /be/ in French speakers using an auditory-motor adaptation paradigm that consists of altering the speakers' auditory feedback. After stopping the perturbation, we studied to what extent this modification would transfer to the production of the disyllabic word /bebe/ and compared it to the after-effect on /be/. The results show that changes in /be/ transfer partially to /bebe/. The partial influence of the somatosensory and motor representations associated with the syllable on the production of the disyllabic word suggests that both units may contribute to the specification of the motor goals in speech sequences. In addition, the transfer occurs to a larger extent in the first syllable of /bebe/ than in the second one. It raises new questions about a possible interaction between the transfer of auditory-motor learning and serial control processes.

Introduction

Speech can be described as a sequence of units, such as sentences, words, syllables and phonemes. These units have formal linguistic descriptions and their sequencing is structured along a number of linguistic rules involving in particular a hierarchical organization [START_REF] Fougeron | Articulatory strengthening at edges of prosodic domains[END_REF]. In the PACT theory [START_REF] Schwartz | The Perception-for-Action-Control Theory (PACT): A perceptuomotor theory of speech perception[END_REF] these units are proposed to be associated with perceptuo-motor units, i.e. perceptually shaped gestures, associating auditory somatosensory and motor representations. Does this association operate specifically at the level of one of these units? If yes, which unit is it? The Consonant-Vowel (CV) syllable has often been considered to be the main unit of speech production. In Levelt's model of speech production [START_REF] Levelt | Models of word production[END_REF] utterances are broken down into syllables in order to be translated into motor commands, using a mental syllabary. On the other hand, the exemplar-based theories proposes that the words are the smallest units stored in the brain as exemplars rather than prototypes [START_REF] Välimaa-Blum | The phoneme in cognitive phonology: episodic memories of both meaningful and meaningless units?[END_REF]. An exemplar corresponds to an element perceived or produced in a given situation. This perspective accounts for the variability of speech production depending on the speaker and the context. The theory of developmental phonology proposed by Vihman and Croft [START_REF] Vihman | Phonological development: Toward a 'radical' templatic phonology[END_REF] provides an intermediate view, where the word is the initial basic unit of speech production in infants. The syllable would then emerge from the observation of similarities in the production of the first words [START_REF] Cristia | Global and detailed speech representations in early language acquisition[END_REF]. Our goal is to question the nature of the speech units underlying speech motor realization using a classical approach in movement sciences: the transfer of sensorimotor learning. In limb motor control literature, the study of sensorimotor learning transfer is regarded as a behavioral window into the neural mechanisms that underlie the control of movements [START_REF] Shadmehr | Generalization as a Behavioral Window to the Neural Mechanisms of Learning Internal Models[END_REF]. The idea is to artificially modify the relation between sensory targets and motor commands for a specific task (e.g. reaching a target with the hand) and observe (1) how this modification is stored in the control system and is used for the same task, once the perturbation has been removed (the so-called after-effects), and (2) how it generalizes to other situations (e.g. reaching a target in another direction, the so-called transfer effect). Houde and Jordan [START_REF] Houde | Sensorimotor adaptation in speech production[END_REF] introduced a similar approach with speech using the auditory-motor learning paradigm. In their experiment, participants had to repeat the word "head" in whispered conditions while they heard their voice in headphones. The auditory feedback was altered in real time by shifting formants so that the vowel sounded more like another one (e.g. changing "head" towards "had). During a training phase, the speakers gradually compensated for the perturbation, by pronouncing something closer to "hid", suggesting sensorimotor recalibration that is designated as adaptation. The after-effect can then be assessed by comparing the formants after stopping the perturbation to their baseline values measured before the training. Purcell and Munhall [START_REF] Purcell | Compensation following real-time manipulation of formants in isolated vowels[END_REF] studied the influence of several experimental parameters (e.g. amplitude of the auditory feedback perturbation, duration of the training) on the adaptation and on the after-effect decay speed. Houde and Jordan [START_REF] Houde | Sensorimotor Adaptation of Speech I : Compensation and Adaptation[END_REF] also showed that the learning performed on one utterance can transfer partially to other utterances, in particular to the same vowel in another CVC word. This was regarded as evidence for the existence of a phoneme representation in speech production. The paradigm of auditory-motor learning transfer was then used in several studies, mostly with CVC words. In Rochet-Capellan et al. (2012) [START_REF] Rochet-Capellan | Nonhomogeneous transfer reveals specificity in speech motor learning[END_REF], different groups of speakers were trained with different C-V-/n/ words (e.g. pen, ten). The transfer was then assessed to the testing word "pen" in all speakers. A significant transfer was observed in most groups, although its amplitude was shown to vary according to the acoustic similarity between the training word and the testing word. The influence of similarity was also observed with Mandarin in the pattern of generalization from the triphthong /iau/ to other vowels [START_REF] Cai | Adaptive auditory feedback control of the production of formant trajectories in the Mandarin triphthong /iau/ and its pattern of generalization[END_REF]. Effects of linguistic factors were investigated in other studies. The lexical status (real word vs. pseudo-word) may influence the amplitude of the auditory-motor adaptation [START_REF] Bourguignon | Lexicalperceptual integration influences sensorimotor adaptation in speech[END_REF] while the word frequency seems to play a role in the transfer amplitude [START_REF] Frank | Integrating Linguistic, Motor, and Perceptual Information in Language Production[END_REF]. To our knowledge, the transfer of auditory-motor learning has not been used yet to question directly the nature of speech production units. Are motor commands associated with speech goals memorized at the level of the syllable or rather at the level of the word?

Method 2.1. Experimental design and hypotheses

The objective of this study was to contrast the transfer of sensorimotor learning at the level of the CV syllable and the corresponding disyllabic word. The training word was the syllable /be/ for all participants. At the end of the training phase, one group of participants (Group 1) pronounced /be/ while another group (Group 2) pronounced /bebe/ (which means "baby" in French), as testing words to assess the transfer. Our predictions were that if the transfer occurs at the syllable level we should observe a transfer equivalent in both groups and in both vowels in /bebe/. If it occurs at a word level only then no transfer to any of the /be/ syllables in /bebe/ should happen. Finally, if the transfer occurs at both levels, then a transfer smaller than in /be/ should occur in /bebe/. The selection of the vowel /e/ was driven mainly by auditory perturbation constraints while the consonant /b/ was chosen to limit coarticulation. Linguistic factors were also taken into consideration in this choice. The syllable /be/ is as frequent at the beginning of French words as it is in the middle or at the end, as controlled with Lexique 2 database [START_REF] New | Lexique 2: a new French lexical database[END_REF]. The frequency of auditory and articulatory neighbors (/bε/ and /bi/) had to be low since it may influence the amplitude of the adaptation [START_REF] Frank | Integrating Linguistic, Motor, and Perceptual Information in Language Production[END_REF].

Subjects, task and online perturbation

Thirty-six native speakers of French (15 females), from 18 to 35 years old, took part in the experiment. They had no reported language or audition impairment, and were naïve to the purpose of the experiment. They were seated in front of a monitor in a soundproof room, and wore headphones equipped with a microphone (Sennheiser HME 26-II-600). Words were displayed on a screen. The participants had to read them aloud in a natural way, without shouting or whispering. They were hearing their voice in the headphones at about 70 dB mixed with speech shaped noise at 50 dB. A real-time perturbation of the first two formants (F1 and F2) was realized using the Audapter system [START_REF] Cai | A System for Online Dynamic Perturbation of Formant Trajectories and Results from Perturbations of the Mandarin[END_REF]. The auditory feedback alteration consisted in transforming the vowel /e/ into /ε/ by increasing F1 by 27% and decreasing F2 by 10%. It triggered a 14ms delay which is not disruptive [START_REF] Yates | Delayed auditory feedback[END_REF][8].

Experimental procedure

The experimental procedure is described in Figure 1. In a pretest (block 1 to 3) speakers had to produce syllables in the /b/+V form (V among /a/, /ε/, /e/, /i/ and /u/) as well as minimal pairs (like real French words /epe/ and /epε/) to explore their vocalic triangle and the contrast /e/-/ε/ in their production, respectively. The experiment then consisted of 14 blocks of 20 trials each (blocks 4 to 17). At the end of each block, the participants had to press a key to continue the experiment. In the baseline phase (blocks 4 to 6) speakers produced /be/ and then /bebe/ without any perturbation. During the training phase, the auditory feedback perturbation was gradually set up (block 7) and then maintained at its maximal amplitude (blocks 8 to 15) while both groups were pronouncing /be/. The perturbation was then stopped and speakers had to pronounce their testing word (/be/ in Group 1 and /bebe/ in Group 2, transfer phase, block 16). Finally both groups pronounced /be/ again to measure the aftereffect (block 17).

Data analysis

F1 and F2 were assessed in a 30ms window in the stable part of each produced vowel. Formants were then expressed as a percentage of change compared to the corresponding vowel measured in the baseline phase in the same speaker. For example, the first /e/ of each repetition of /bebe/ was compared to the average first /e/ of /bebe/ productions in the baseline. The main measure chosen to study transfer was F2-F1, with F1 and F2 expressed in Barks.

= 7 * ℎ [START_REF] Schroeder | Objective Measure of Certain Speech Signal Degradations Based on Masking Properties of Human Auditory Perception[END_REF] (1)

The adaptation in each speaker was estimated by comparing F2-F1 in the last 40 trials of the training phase to the baseline using a one-tailed paired t-test. A one-way between-subjects ANOVA was carried out to assess any difference in the adaptation between the two groups. An ANOVA could not be conducted on transfer data since the position of the syllable in the word is a within-subject factor that only applies to Group 2 (the group being a between-subject factor). The transfer was therefore assessed using planned comparisons. In block 16, the F2-F1 change in /be/ relative to the baseline was compared to the change in the first vowel of /bebe/ using a one-tailed t-test. The transfer in the first vs. the second vowel of /bebe/ was contrasted by carrying out a two-tailed paired t-test. The intensity, pitch and duration of the first vs. the second vowel were compared using two-tailed paired t-tests. A one-way between-subjects ANOVA was conducted to assess any difference in the aftereffect between the two groups. In particular this could show any possible impact of the transfer phase on the after-effect decay.

Results

Adaptation

We were expecting participants to compensate for the perturbation of their auditory feedback by increasing their F2-F1 in /be/ during the training phase. Since this study is focused on transfer of adaptation, only participants who showed a significant adaptation were selected in the analysis. There were 27 such participants, of which 13 speakers (3 women) were in Group 1 and 14 speakers (3 women) were in Group 2.

The evolutions of F2-F1 for the 3 main phases of interest are represented in Figure 2. During the adaptation phase, F2-F1 increased on average by 8.0% (±0.6%) relative to the baseline values. The adaptation amplitude was significant. It did not depend on the group (F(1,25) = 0.026, p = 0.872). It represented a compensation of about 25% of the perturbation, which roughly matches results obtained in previous studies [START_REF] Purcell | Adaptive control of vowel formant frequency: evidence from real-time formant manipulation[END_REF].

Transfer and after-effect

During the transfer phase, F2-F1 increased by 7.0% (±1.0%) for /be/ (Group 1) relatively to the baseline. In Group 2, the amplitude of the transfer was 4.6% (±0.7%) in the first syllable and 2.6% (±0.7%) in the second syllable. The change was significantly higher in /be/ (Group 1) than in the first syllable of /bebe/ (Group 2) as revealed by a t-test (t(25) = 1.97, p = 0.03).

The transfer in the first syllable was significantly higher than in the second syllable (t(13) = 3.25, p = 0.006).The amplitude of the after-effect, always tested with /be/, was 6.1% (±1.0%) in Group 1 and 5.0% (±0.6%) in Group 2. There was no significant difference between groups (F(1,25) = 0.844, p = 0.367) suggesting that the after-effect decay was not sensitive to the transfer phase. Additional analyses related to prosodic cues show that the second syllable lasted longer (133ms ±10) than the first one (99ms ±5; t(13) = -3.66, p = 0.003). No significant difference between the two syllables was found regarding the pitch (t(13) = -0.18, p = 0.8) or the intensity (t(13) = 0.29, p = 0.8).

Discussion

The objective of this study was to contrast the transfer of sensorimotor learning at the level of the CV syllable and the word. In this section we will first comment on the two main effects related to the transfer, in order to provide a response to our research question. Then we will focus on the adaptation and discuss some limitations observed in this experiment.

CV vs CVCV

Our results indicate that some transfer occurs at the level of the syllable since a significant transfer occurred from /be/ to /bebe/. However the difference of amplitude in the transfer observed in /be/ (Group 1) and in the first and second syllables of /bebe/ (Group 2) suggests that transfer is also influenced by a larger context, in this case the produced word. This result questions the assumption that a "mental syllabary" [START_REF] Levelt | Models of word production[END_REF] would represent the only link between a targeted speech sequence and the articulatory gestures to produce it. Overall, the results suggest that several units, including both the CV syllable and the word, may contribute to define the motor goals associated with an utterance. This observation in adults is consistent with the developmental theory suggested by Vihman and Croft [START_REF] Vihman | Phonological development: Toward a 'radical' templatic phonology[END_REF] according to which several speech production units may develop gradually and therefore coexist in adults.

It may be noticed that the speakers who produced /bebe/ in the transfer block pronounced twice as many syllables as the other group. The higher number of repetitions of the syllable /be/ could be expected to trigger a faster after-effect decay. If this was the only factor driving the higher transfer in /be/ than in /bebe/ then we should observe a difference between groups in the after-effect amplitude measured in the block that followed the transfer. However, there was no significant difference between groups in the after-effect amplitude. Thus the number of repetitions could not be regarded as the main factor explaining the difference of transfer amplitude between groups.

The position of the syllable

The significant difference of transfer amplitude observed in the first and the second syllable of /bebe/ will be referred to as a position effect. This is another observation that questions the concept of a mental syllabary as it suggests an influence of the serial order of speech on the transfer. Several explanations could account for this effect. First, this position effect could be linked to an influence of prosody on sensorimotor learning transfer. A stressed syllable could be produced in a more precise way than an unstressed syllable. In most participants, the second syllable lasted longer than the first one, which is consistent with French stress pattern [START_REF] Jun | Realizations of accentual phrase in French intonation[END_REF]. However, no correlation among speakers was observed between the stress pattern and the difference of transfer amplitude between the first and the second syllable. The potential link between prosodic patterns and transfer amplitude could be further investigated by evaluating transfer while asking speakers to produce more contrasted stress patterns in CVCV words.

The observed position effect may also depend on the auditory perturbation. The training was realized on a monosyllabic word. The perturbed syllable was thus the first one (and the only one) of the utterance. In this context, the speakers may have learned to modify more specifically the first syllable of the sequence. The auditory-motor paradigm has not yet been applied in humans with words consisting of several syllables. Some research in zebra finches [START_REF] Hoffmann | Vocal Generalization Depends on Gesture Identity and Sequence[END_REF] focused on the transfer of auditory-motor learning in song sequences. The birds were wearing small headphones providing them with their auditory feedback. An alteration of their pitch was applied on a specific syllable in a given position within their vocalization. It led the birds to adapt by compensating partially for the perturbation as observed in humans. At the end of the perturbation a transfer was observed in the same syllable in any position of the sequence. The transfer partially spread to temporally nearby syllables. Selective perturbation in terms of position in the sequence would raise new perspectives in studying how speech units are put into sequence from a motor control perspective.

Adaptation to the perturbation and limitations

Twenty-seven speakers out of 36 (e.g. 75%) adapted to the perturbation by significantly increasing F2-F1. The 9 remaining speakers were all women. The perturbation did not seem to work properly in 5 of them and the 4 remaining speakers did not show significant increase of F2-F1. Although this depletion rate can seem quite high, it is very similar to what has been observed in previous studies using the same perturbation system. In Cai et al. (2010) [START_REF] Cai | Adaptive auditory feedback control of the production of formant trajectories in the Mandarin triphthong /iau/ and its pattern of generalization[END_REF] 31 speakers out of 40 were included in the results, 4 speakers had formants that were not well detected by the system, which therefore did not apply the targeted perturbation properly. The last 5 speakers were reported to follow the perturbation instead of compensating for it. It is not mentioned whether these speakers were males or females. Some studies with other perturbation systems report lower depletion rate. In MacDonald et al. (2010) [START_REF] Macdonald | Compensations in response to real-time formant perturbations of different magnitudes[END_REF] only one male out of 20 did not show any compensation. The parameters of our perturbation system may be better fine tuned to adjust to women's voices, but formants detection is inherently more difficult in high pitched voices since the gap between two harmonics is higher. Beyond technical limitations, some speakers may not have adapted to the perturbation because they rely more on their somatosensory feedback than on their auditory feedback during speech production. The existence of a sensory preference was suggested by a study in which alterations of the auditory and the somatosensory feedbacks were performed simultaneously in speakers [START_REF] Lametti | Sensory Preference in Speech Production Revealed by Simultaneous Alteration of Auditory and Somatosensory Feedback[END_REF]. Another possible explanation for the absence of compensation in some speakers could be that they do not make any distinction between /e/ and /ε/ in production as these phonemes are often confused in French speakers. However no correlation was established between the amplitude of speakers' adaptation and their contrast in production between /e/ and /ε/ as assessed in the pretest.

Conclusions

The objective of this study was to contrast the contribution of the word and the syllable in the definition of speech motor goals. We artificially modified the production of the syllable /be/ in French speakers by altering their auditory feedback. After speakers significantly adapted to the perturbation, the transfer to /bebe/ was measured under normal feedback and compared to the after-effect in /be/. The results show that the change in /be/ due to adaptation partially transferred to the production of /bebe/, suggesting that both units amongst others may contribute to defining speech motor goals. The difference of transfer amplitude observed in /bebe/ between the first and the second syllable raises new questions with regards to serial order. Several factors, from a potential prosody effect to a possible influence of the monosyllabic structure of the training word could contribute to this last effect. Further investigation is required to test these assumptions.

Figure 1 :

 1 Figure 1: The experiment consisted of 5 phases, each number corresponding to one block of 20 trials. The auditory perturbation (in grey) was applied during the training phase.

Figure 2 :

 2 Figure 2: Evolution of F2-F1 in percentage of change compared to baseline, by phase, by group and by syllable. Each point represents an average of the trials of the phase for the group. The bar represents the standard error.

Acknowledgements

The research leading to these results has received funding from the European Research Council under the European Community's Seventh Framework Program (FP7/2007-2013 Grant Agreement no. 339152). The authors would like to thank Christophe Savariaux and Takayuki Ito (CNRS, Gipsa-lab, F-38000 Grenoble, France) for their contribution to this work, in particular their help in the experimental setup. Many thanks to Frederic Field who helped enhancing the wording in this article.