Marcelino Rodriguez-Cancio
email: marcelino.rodriguez-cancio@irisa.fr

Benoit Combemale
email: benoit.combemale@irisa.fr

Benoit Baudry
email: benoit.baudry@inria.fr

Approximate Loop Unrolling

Keywords: approximate computing, compiler optimizations, loop unrolling

We introduce Approximate Unrolling, a loop optimization that reduces execution time and energy consumption, exploiting the existence of code regions that can endure some degree of approximation while still producing acceptable results. This work focuses on a specific kind of forgiving region: counted loops that map a given functions over the elements of an array. Approximate Unrolling transforms loops in a similar way Loop Unrolling does. However, unlike its exact counterpart, our optimization does not unroll loops by adding exact copies of the loop's body. Instead, it adds interpolations.

We describe our experimental implementation of Approximate Unrolling in the Server (C2) Compiler of the Open-JDK Hotspot JVM. The choice to implement our technique directly in the compiler reduced Phase Order problems and transformation overhead. It also proved that our technique could actually improve the performance of a productionready compiler. Using our modified version of the compiler, we perform several experiments showing that Approximate Unrolling is able reduce execution time and energy consumption of the generated code by a factor of 50% with minimal accuracy losses.

INTRODUCTION

Approximate computing exploits the fact that some computations can be made less precise and still produce good results in order to reduce execution times and energy consumption [START_REF]A Survey of Techniques for Approximate Computing[END_REF]. Previous works in the field have proven that when small reductions in accuracy are acceptable, significant improvements in execution times and energy consumption can be achieved [START_REF] Xu | Approximate Computing: A Survey[END_REF]. Opportunities for approximation arise all along the stack and researchers have proposed techniques to approximate in both hardware and software.

Hardware-oriented approximation techniques have proposed components with approximation capabilities, such as FPUs [START_REF] Tong | Reducing power by optimizing the necessary precision/range of floating-point arithmetic[END_REF], adders [START_REF] Gupta | IMPACT: Imprecise adders for low-power approximate computing[END_REF][START_REF] Shafique | A Low Latency Generic Accuracy Configurable Adder[END_REF] and memories [START_REF] Chang | A Priority-Based 6t/8t Hybrid SRAM Architecture for Aggressive Voltage Scaling in Video Applications[END_REF][START_REF] Liu | Flikker: Saving Refresh-Power in Mobile Devices through Critical Data Partitioning[END_REF]. They also exploit the inherent non-determinism of existing hardware as sensors [START_REF] Luo | Compressive Network Coding for Approximate Sensor Data Gathering[END_REF] and wireless adapters [START_REF] Sen | Design and implementation of an "approximate" communication system for wireless media applications[END_REF] and some even expose it to developers [START_REF] Bornholt | Uncertain\textlessT\textgreater: A First-Order Type for Uncertain Data[END_REF]36]. On the software-oriented side of approximate computing, the proposed techniques modify existing algorithms automatically [START_REF] Sidiroglou-Douskos | Managing performance vs. accuracy trade-offs with loop perforation[END_REF][START_REF] Misailovic | Parallelizing Sequential Programs With Statistical Accuracy Tests[END_REF][START_REF] Samadi | Paraprox: Pattern-based Approximation for Data Parallel Applications[END_REF] or provides support for programming with approximation via language design [START_REF] Misailovic | Chisel: Reliability-and Accuracy-aware Optimization of Approximate Computational Kernels[END_REF][START_REF] Sampson | EnerJ: approximate data types for safe and general low-power computation[END_REF], frameworks [START_REF] Baek | Green: A framework for supporting energy-conscious programming using controlled approximation[END_REF][START_REF] Bornholt | Uncertain\textlessT\textgreater: A First-Order Type for Uncertain Data[END_REF] and compilers [START_REF] Ansel | PetaBricks: a language and compiler for algorithmic choice[END_REF].

In this work we describe a loop optimization, namely Approximate Unrolling, that uses the ideas of approximate computing to reduce execution times and energy consumption of loops mapping values to arrays. These loops are commonly encountered in programs that process signals and that exploit heuristics. In addition, these loops account for a large part of the computation, e.g., the loops that we analyze in our case study are executed millions of times in a few seconds. Consequently, saving resources on these loops can have a major impact on the program's consumption, as long as the results remain acceptable for the users.

The key insight of Approximate Unrolling relies on the following observation: data such as time series, sound, video and 3D Meshes are frequently represented as arrays where contiguous slots contain similar values. As consequence of this neighboring similarity, computations producing this data are usually locally smooth functions. In other words, computations producing or modifying nearby array values representing these kinds of data frequently yield similar results.

Our technique exploits this observation by searching for loops where computations results are assigned to contiguous array slots in each iteration. Then, we substitute some of these computations by inexpensive interpolations of the values assigned to nearby array values. In exchange for this loss in accuracy, we obtain a faster and less energy consuming loop.

To substitute iterations, Approximate Unrolling works in a similar way as Loop Unrolling. Yet, instead of unrolling by adding exact copies of the loop's body, it adds code that interpolates the computations performed by the original loop, creating approximate iterations that interpolate some mappings. The code of the approximate iteration is minimal, thus reducing execution time and energy consumption of the whole loop.

We have modified the OpenJDK Java Server (C2) compiler to include Approximate Unrolling as a machineindependent optimization. All machine-independent opti-mizations (and therefore ours as well) reshape the C2's internal representation of a program to obtain an optimized version of the same program. Approximate Unrolling performs an static analysis over the C2's Internal Representation (IR) to find loops matching certain pattern. Then, those loops are transformed by reshaping the C2's IR.

Our initial implementation of Approximate Unrolling relied on source code and bytecode transformations. Unfortunately this led to a phase ordering problem, breaking other compiler optimizations and failing to gain the expected performance. We then decided to implement the optimization directly in the compiler, allowing us to respect the existing phase order. This also reduced the overhead since we had a direct access to the internal representations provided by the compiler. In addition, this gives us garantees about the fact that Approximate Unrolling can actually has an impact on the performance of a highly optimized code created by production-ready compiler.

Our experiments shows that Approximate Unrolling is able to reduce the execution time and energy consumption of the x86 code generated around 50% to 80% while reducing the accuracy to acceptable levels.

The contributions of this work are:

• Approximate Unrolling, an approximate loop transformation

• A formal specification of loops targeted by Approximate Unrolling and of the behavior of the transformation

• An efficient implementation of Approximate Unrolling inside the OpenJDK Hostpot VM.

• An empirical assessment of the effectiveness of Approximate Unrolling to trade accuracy for time and energy savings.

The rest of the paper is organized as follows, in section 2 we describe our optimization and its scope. We then detail our implementation in section 3 and our evaluation in section 4. Section 6 describes how Approximate Unrolling compares with other approximate computing techniques and finally section 7 concludes.

APPROXIMATE UNROLLING

In this section we describe the main contribution of our paper, which is the Approximate Unrolling approximate loop optimization. We first introduce the intuition of the optimization using the toy example of listing 1. Afterwards, we formally characterize the loops that Approximate Unrolling can target. Finally, we introduce the formal semantics governing the proposed optimization.

Illustrating Example

Approximate Unrolling creates an alternative version of the loop by unrolling it with operations that interpolate the computations performed in the loop's original body. We propose two variants: linear or nearest neighbor interpolations. Both are supported by our implementation, which is able to choose one single transformation for each loop.

The loop of listing 1 will serve to illustrate both transformations. The loop maps a sine wave into an array and belongs to a music synthesizer. Conceptually, the example loop transformed by Approximate Unrolling using linear interpolation looks like the one in listing 2, while the same loop approximated with nearest neighbor looks like the one in listing 3. The output of these loops is depicted in figure 1. As the modified loop of listing 2 shows, when using linear interpolation, Approximate Unrolling adds code to the loop's body that interpolates the computations of the odd iterations as the mean of the even ones(the computations of iteration one are interpolated using the results of iterations zero and two, computations of iteration three are interpolated using the results of two and four and so on). Initially, Approximate Unrolling peels iteration zero of the loop. Then, it modifies the initialization and updates the statements to double the increment of the loop's counter variable. As result of this, if the original loop performed an even number of iterations, the last iteration would not be performed. To cover for this case, Approximate Unrolling also peels the last iteration.

@Approximate double

f o r ( i n t i = 2; i < N ; i += 2 ) { A [ i ] = Math . sin ( i * stride ) ; A [ i -1] = ( A [ i ] + A [i -2]) * 0.5 f ; } i f ( i == N ) A [i -1] = Math . sin (( i -1) * stride ) ;
The procedure with nearest neighbor is quite similar, Approximate Unrolling only modifies the update statement to double the increment of the loop's counter variable. It also adds code with the nearest neighbor interpolation at the end of the loop's body.

i, n ∈ Z B ∈ {expression} [[B]] ∈ {true, f alse} t body = C I0, C ⊂ {statement} ξ = B, i := i + n, C Figure

Target Loops

Our optimization targets the subset of Java for loops that (i) have an update expression that increments or decrements a variable by a constant value (ii) contain an array assignment inside its body (iii) the indexing expression of the array assignment is value-dependent on the loop's update expression.

We now use Backus-Naur form to formalize the syntax of the loops abiding to (i) and (ii), while (iii) is formalized using data flow equations. For the sake of simplicity, we only show the case in which the variable is being incremented. It should not be difficult for the reader to derivate these rules for the case in which the variable is being decremented.

Grammar 1 shows the BNF rules defining the kind of loops Approximate Unrolling can target. In the grammar, the non-terminal rules expression , identif ier , integer and statement , define the Java expressions, identifiers, inte-ger literals and statements respectively. Rule target f or describes the loops targeted by Approximate Unrolling. The rule introduces two other non-terminals. The first nonterminal: update expr describes the expected update expression or the loop, consisting in a variable being incremented by a literal value, while t body describes a list of statements containing at least one array assignment, which are described using the array assign non-terminal.

The index expr rule reduces to a Java expression and facilitates the formalization of condition (iii), which we do as follow: let L be a loop conforming to Grammar 1, let AL be the set of expressions inside the body of L conforming to index expr and let UL represent the update expressions conforming to update expr for the same loop L. Also, let REACH(X) be the reaching definitions set [START_REF] Cooper | Engineering a Compiler[END_REF] data-flow equation for a given expression. We say (iii) holds if:

∃ ai ∈ AL : UL ∈ REACH(ai) (1)
To recapitulate, loops targeted by Approximate Unrolling are those loops conforming to grammar 1 for which equation (1) holds.

As example, the loop of listing 1, conforms to grammar 1. The rule update expr reduces to 'i++', while rule t body reduces to a single array assign statement: 'A[i] =...'. Finally, index expr reduces to 'i'. Is also true that equation (1) holds for the loop. There, AL ={'i'}, UL ='i++' and REACH(i) = UL.

Transformation's Operational Semantics

Figures 3 and4 show the operational semantics for Approximate Unrolling in small step operational style. The rules in figure 3 specify the transformations for the linear interpolation, while the rules in 4 the transformations for the nearest neighbor. Finally, figure 2 provides a group of rules and definitions used to define the semantics of both transformations. As with the syntactic part, to keep the rules simple, we only describe the case in which the variable is incremented.

As defined in Figure 2, B is a boolean Java expression and I0, C are sets of Java statements. I0 represents the initialization statements, while C the loop's body. The tuple ξ is a syntactical sugar to make the rules more compact. We use the common definitions for rules SKIP, ASSIGNMENT, SEQUENCE and IF.

Rules For the Linear Transformation

In this subsection we describe the semantic rules of the linear transformation as follows:

For L . The F orL rule interpret a loop using linear interpolation. The rule reduces to the interpretation of the loop's initialization statement I0 and if predicate B holds, rule P re is interpreted.

Pre. As shown in listing 1 the loops approximated using linear interpolation have iteration zero peeled. This rule represents such initial peeled iteration. It reduces to the interpretation of the loop's body once, without any modifications. Then, the exact part of the loop (described by rule ExtL) is called.

Ext L . This rule represents one loop's exact iteration. The odd iteration is skipped by doubling the incrementing of the counter variable (i := i + 2n), then if predicate B still holds, an exact iteration of the loop is executed. Next, the code approximating intermediate values is called in rule AprxL.

Aprx L . Approximate the value of odd arrays slots. The approximation is found as the mean of the previous and following values of the approximate slot, the value of the even iteration array slot is calculated as:

a[i -n] := (a[i] + a[i -2n]) * 0.5.
Notice that the counter's variable i was incremented twice to skip the approximate iteration in the exact one, therefore the odd slot must be accessed now using index i -n and the previous even slot using index i -2n.

Post As the initial iteration is peeled and the counter's variable value is doubled to unroll the loop, when the amount of iterations in the original loop is an even number, the last iteration of the loop is not executed. To solve this, one last iteration is peeled and appended after the loop.

Rules For the Nearest Neighbor

Similarly to what we did for the linear transformation, in this section we describe the semantic rules for the nearest neighbor transformation.

For L . The F orL rule transforms a loop using nearest neighbor interpolation. The rule can be reduced to the execution of the initialization statements I0, followed by the execution of ExN .

Ex N This rule executes an exact iteration of the loop if the predicate B holds, then it calls AprxN .

Aprx N The rule increment the counter variable, approximates one array slot by setting its value equal to the one calculated before and then it increments the variable again. Finally ExN is called. Unlike linear interpolation, the rule is supposed to approximate the value of the array assigned in the even iteration.

IMPLEMENTATION

This section describes our experimental implementation of Approximate Unrolling in the C2 compiler of Hostpot.

The Hostpot V.M. is used by billions of devices today. It come packed with two compilers: C1 (or Client) and C2 (or Server). When a program starts to run, the bytecode is interpreted. The segments of code executed frequently (hot), are compiled using C1 or C2, depending on how 'hot' the code is. C2 is slower, but creates faster code.

We choose to implement Approximate Unrolling directly in the C2 because our initial source code manipulation techniques failed to improve performance as they forbid other optimizations. The fact that the optimization order influences the quality of the code (a. k. a Phase Ordering problem) is a well known issue [START_REF] Kulkarni | Mitigating the Compiler Optimization Phase-ordering Problem Using Machine Learning[END_REF] in compiler design. Implementing Approximate Unrolling in the compiler also reduced the implementation's overhead as otherwise we would have need to create data structures such as the value dependency graph already provided by the compiler. Also, implementing the optimization in the C2, we provide support for other JVM languages such as Scala. Finally, this implementation showed that we could improve the performance of a production-ready compiler.

Approach overview

Approximate Unrolling is a machine independent optimization. This kind of optimization operates by reshaping the Ideal Graph, which is the internal representation (IR) of the C2 compiler.

In a nutshell, our implementation for nearest neighbor works as follows: the Ideal Graph contains nodes representing operations very close to assembler instructions. Nodes are linked by edges representing data dependencies . In the graph, there is a node type called Store that represents a storage to memory. Our transformation is performed after the compiler performs the 'regular' Loop Unrolling. During the unrolling, each node in the loop's body gets duplicated, resulting in one extra node for each unrolled iteration. Let us consider StoreA, a node representing a value storage into memory owned by an array. Before the unrolling there is only one node, StoreA, after the unrolling there are node, StoreA and StoreB. If we find nodes like StoreA and StoreB in a loop body, we disconnect one of the Store nodes (say StoreA) of all its value-dependencies and connect to the value-dependencies of the other (say StoreB), resulting in both Store storing the same value in two different array slots. Then, we delete of all nodes on which StoreA was originally value-dependent, removing most computations of one iteration. For linear interpolation the process is very similar, the only difference is that some nodes are added and connected to StoreA to perform the mean calculation.

During the rest of the section we expand on this process, we first describe the internal representation of the Compiler, the Ideal Graph, then we go in details of our implementation and exemplify it using a toy loop. Our modified version of the Hostpot JVM is available on the webpage of the Approximate Unrolling project1

The Ideal Graph

The C2's internal representation is called the Ideal Graph (IG) [START_REF] Click | A Simple Graph-based Intermediate Representation[END_REF]. It is a Program Dependency Graph [START_REF] Ferrante | The Program Dependence Graph and Its Use in Optimization[END_REF]. All C2's machine independent optimizations work by reshaping this graph.

In the Ideal Graph (IG), nodes are objects and hold metadata used by the compiler to perform optimizations. Nodes in this graph represent instructions as close as possible to assembler language (i.e. AddI for integer addition and MulF for float multiplication). The IG metamodel has nearly 380 types of nodes. We deal with five of them: Store, Counted-Loop, Phi, Add and Mul.

Store nodes represent storages into memory. They contain metadata indicating the type of variable holding the memory being written, making it easy to identify Store nodes writing to arrays. The Ideal Graph is in Static Single Assignment (SSA) form and the Phi nodes represent the φ functions of the SSA. CountedLoop represents the first node of all the loops that Approximate Unrolling can target. The CountedLoop type contains two important metadata for our implementation: a list of all nodes representing the loop's body instructions and a list with all nodes of the update expression. Finally Add and Mul nodes represents the addition and multiplication operations.

Nodes in the IG are connected by control edges and data edges. Yet, data edges are the most important ones for our implementation, and we will refer to this kind of node exclusively, unless noted otherwise. Data edges describe value dependencies, therefore the IG is also a directed Value Dependency Graph [START_REF] Allen | Conversion of Control Dependence to Data Dependence[END_REF]. If a node B receives a data edge from a node A, it depends on the value produced by A. Edges are pointers to other nodes and contain no information. Edges are stored in nodes as a list of pointers. The edge's position in the list usually matters. For example, in Div (division) nodes the edge in slot 1 points to the dividend and the edge in slot 2 points to the divisor.

The Store requires a memory address and a value to be stored in the address. The memory edge eM is stored at index 2 and the value edge eV at index 3. Edge eM links the Store with the node computing the memory address where the value is being written, while eV links the Store with the node producing the value to write.

Let us consider the very simple example of listing 4,. The resulting IG for this loop is shown in figure 5. In the figure, the StoreI represents the assignment to A[i], the MulI node represents the i*i expression. The address is resolved by the nodes in the Cluster A (containing the LShift node).

f o r ( i n t i = 0; i < N ; i ++ ) A [ i ] = i * i ;
Listing 4: Example loop for the implementation

Detecting Target Loops

Section 2.2 formally described the shape of loops targeted by the proposed optimization. This section describes how our implementation detects them in the IG.

Section 2.2 defined the loops Approximate Unrolling can target. Fortunately, Java for loops having a constantincrement update expression are also the target of other well known optimizations such as Range Check Elimination and Loop Unrolling. Therefore, the C2 recognizes them and marks their start using CountedLoop nodes. When our optimization kicks in, the compiler has already marked the loops with CountedLoop nodes, recognized the nodes belonging to the update expression and the ones belonging to the loop's body. The compiler does this using the works of Click [START_REF] Click | Global Code Motion/Global Value Numbering[END_REF], Vick, [START_REF] Vick | SSA-based reduction of operator strength[END_REF] and Tarjan [START_REF] Tarjan | Testing flow graph reducibility[END_REF]. Figure 5 shows the CountedLoop recognized by the C2 for the loop in listing 4. The nodes in the graph are those listed in the CountedLoop metadata. This metadata also indicates that the update expression contains solely the AddI node (in gray).

Once the loops with constant-increment update expression are detected, the next step consists in determining if there is an array who's index expression value depends on the loop's update expression. As we mentioned, the CountedLoop node maintains a list of all the nodes in its body. To determine if there is an array assignment within the loop, we look for a Store writing to memory occupied by an array. In the example of figure 5 we find the StoreI node (in gray).

Finally, we check if the array index expression value depends on the loop's update expression. As the IG is a Value Dependency Graph, we look for a path of data edges between the Store node representing the array assignment and any node belonging to the loop's update expression. In the example of figure 5 this path is highlighted using bold gray edges. Thanks to the metadata stored in CountedLoop, we know that the update expression only contains the AddI node. Therefore, in the example, the path is composed of the following nodes:

AddI → Phi → CastII → ConvI2L → LShiftL → AddP → AddP → StoreI.

Unrolling

Our implementation piggybacks in two optimizations already present in the C2 compiler: Loop Unrolling and Range Check Removal. At the point Approximate Unrolling kicks in, the compiler has already unrolled the loop and performed Range Check Removal. Listing 5: Assembler code generated for the example loop without using Approximate Unrolling

1 B7: # B8 <-B8 top-of-loop Freq: 986889 2 movl RBX, R8 # spill 3 B8: # 4 movl [R11 + #16 + RBX << #2], RCX # int 5 movl [R11 + #20 + R8 << #2], RCX # int 6 movl RBX, R8 # spill 7 addl RBX, #2 # int 8 imull RBX, RBX # int 9 movl [R11 + #24 + R8 << #2], RBX # int 10 movl [R11 + #28 + R8 << #2], RBX # int 11 addl R8, #4 # int 12 movl RCX, R8 # spill 13 imull RCX, R8 # int 14 cmpl R8, R9 15 jl,s B7
Listing 6: Assembler code for the example loop using Approximate Unrolling While unrolling, the compiler clones all the instructions of the loop's body. Figure 6 shows the IG once the loop of listing 4 has been unrolled. The cloning process introduces two Store nodes: StoreI and StoreI-Cloned. Due to C2's design, the cloned nodes belong to the even iteration of the loop. Once the loop is unrolled, Approximate Unrolling reshapes the graph to achieve the interpolated step by modifying one of the two resulting iterations. Nearest Neighbor modifies the even iteration, while Linear interpolation reshapes the odd iteration.

Nearest Neighbor Interpolation

As mentioned in section 3.2, a Store node takes two input data edges eM and eV . Edge eM links with the node computing the memory address, while eV links with node producing the value to write.

Approximate Unrolling performs nearest neighborhood interpolation by disconnecting the cloned Store node from the node producing the value being written (i.e. it deletes eV ). In figure 6 this means to disconnect node MulI-Clone (in gray) from node StoreI-Clone by removing edge eV .

This operation causes the node producing the value (in the example MulI-Clone) to have one less value dependency and potentially become dead if it has no other dependencies. A node without value dependencies means that its computations are not being consumed and therefore is useless dead code. In this case, the node is removed from the graph. We recursively delete all nodes that do not have dependencies anymore, until no new dead nodes appear. In figure 6, we delete MulI-Cloned and then AddI-Cloned. This simplification of the IG translates into less instructions when the IG is transformed in assembler code.

After the removal, Approximate Unrolling connects the node producing the value for the original Store into the cloned Store. Figure 7 shows the shape of the IG after Approximate Unrolling has approximated the graph using nearest neighbor. Note that MulI-Clone and AddI-Clone are deleted and that Store-Clone is connected by ev to the same node as StoreI. The nodes producing the address remain different.

Listing 5 shows the code generated by C2, without performing Approximate Unrolling: the compiler has unrolled the loop twice, generating four storages to memory (lines 2, 3, 9, 10) and four multiplication instructions (imull, lines 5, 8, 12, 17). Listing 6 shows the code generated for the same loop using our transformation: there are still four storages (lines 4, 5, 9, 10), but only two multiplications (Lines 8, 13).

Linear Interpolation

To unroll using linear interpolation, Approximate Unrolling needs the first and last iteration of the loop peeled. Fortunately, this is also a requirement of other optimizations such Range Check Removal and we exploit this feature to peel the first and last iterations of the loop. The current implementation of the Range Check Removal creates two guard loops, one before the main loop and other after. These guard loops ensure that the main loop will not go off bounds of the array being assigned. We exploit these two guard loops for the linear interpolation.

Approximate Unrolling performs linear interpolation following a process similar to nearest interpolation. The differences are that it disconnects the value data edge ev from the original Store, rather than the cloned Store. This is because C2's design implies that the cloned nodes belong to the even iteration, but linear interpolation approximates odd iterations. After the value data edge is disconnected, some nodes become dead. Here we use the same process to remove unused nodes. Finally, the interpolation is performed in the following way: (i) a Add node is created that receives as input the output of the cloned Store and a Phi node representing merge between the previous odd iteration of the loop and the current one (ii) a Mul node is created to multiply the result of this addition by 0.5 and this node is connected to the the original Store effectively interpolating the loop's even iteration.

EVALUATION

To evaluate our approach, we build a version of the softwarebased musical synthesizer Osc3x2 . Using this synthesizer as case study, we run a series of experiments. The objective of our evaluation is twofold. First, we want to understand whether the accuracy loss caused by each optimized loop is significant or not. Second, we want to assess the benefits in performance and energy consumption of each optimized loop. We evaluate these concerns through the following research questions:

RQ1: Is the accuracy loss caused by the optimization to each loop acceptable?

If the accuracy loss goes to a point where the results are unacceptable there is no point in making the calculations faster. Therefore, we must carefully verify that our optimization reduces the accuracy only to acceptable levels. We introduce a metric in section 4.2, which is tailored to evaluate the accuracy of our case study.

RQ2: How big is the execution times reduction per loop?

On the other hand, without a significant increment in performance, reducing accuracy may not pay-off. Therefore, we must carefully assess these reductions to determine the actual gains in performance. In section 4.3, we implement we use microbenchmarks to estimate the computation time of each loop.

RQ3: How big are the energy savings per loop? Just like with execution times, we expect to have energy savings in exchange of accuracy loss. We use JRALP to determine the energy consumption of each loop under study. Copies the signal to the sound card's buffer Mono: 441K -Stereo: 882 K

Evaluation Program & Dataset

Our version of Osc3x is based on JSyn [START_REF] Burk | JSyn -A Real-time Synthesis API for Java[END_REF], a softwarebased musical synthesizer framework. We choose JSyn to evaluate our approach because the framework works by connecting sound units that generate or manipulate signal using loops that are good candidates for Approximate Unrolling. The loops are usually a central piece of the Jsyn units.

As shown in figure 8, Osc3x works by mixing together the signal produced by three low frequency oscillators (LFO). The mixer's output is then filtered using a digital biquad filter. We also added two sound effect (FX) units. The synthesizer can be configured by setting each oscillator type (Sine, Square, Triangle, Sawtooth), FX units effects (Delay, Phase), the filter type (LowPass, HiPass, BandPass) and the mixer's LFO level. This is called a preset. The oscillators, mixers, FXs and filters are built-in with Jsyn, our implementation only connect them together.

For our experiments, we run Osc3x with 10 musical scores. The scores are well known tunes such as Star Wars and Super Mario Bros themes. Each score is played with 10 different presets, which are designed to test all the synthesizer features.

The case study music synthesizer contains 11 loops that Approximate Unrolling can target. In all cases each loop was the central piece of code for each Jsyn unit conforming the synthesizer. Their function is described in table 1 and a letter from A to K to better represent them in figures 9, 10 and 11. The target loop are computational intensive, table 1 also shows the number of times each loop was executed to produce an arbitrary amount of 20 seconds of sound. Each loop execution counted for 10 iterations. The number of iteration is set by the JSyn engine to meet its real time requirements.

The code for our synthesizer, as well as all the microbenchmarks, resulting data and rendered sound files can be found on the webpage of the Approximate Unrolling project 3 .

RQ1: Accuracy Loss Assessment

To answer RQ1 we render each score using all the presets without approximating any loop. This results in 100 sound files that we use as baseline. Then, we play the same scores with the synthesizer in which we approximate one loop at a time. This produces 11 sets of 100 sound files. We then perform a pairwise comparison to assess the accuracy loss created by approximating each loop. This experiment was 3 https://github.com/approxunrollteam repeated twice for each loop in the synthesizer: once using the nearest neighbor and once with linear interpolation.

Notice that it is possible that a given preset causes the execution of the synthesizer not to cover the approximate loop, in such case, the resulting file is not taken into account.

To compare two audio files we use the Perceptual Evaluation of Audio Quality (PEAQ) [START_REF] Åȃalovarda | Estimating perceptual audio system quality using PEAQ algorithm[END_REF] metric. This is a standard metric designed to objectively measure the audio quality as perceived by the human ear. The metric was designed to compare sounds simulating the psychoacoustic of the human ear, which is not equally sensible to all frequencies. PEAQ takes one reference and one test file and compares them. It assigns a scale of contiguous value to the to the test audio, depending on how well it matches the reference: 0 (non audible degradation), -1 (audible but not annoying), -2 (audible slightly annoying), -3 (annoying) -4 (completely degraded).

Results.

Figure 9 is a box plot showing the distribution of PEAQ measurements for each loop presented in Table 1 (we use the letters A to K to identify each loop). The gray boxes correspond to losses when using nearest neighbor transformation while white boxes correspond to losses when using linear interpolation. Boxes corresponding to linear interpolation can be also identified because the letter assigned to the loop is followed by an 'L'. This way, 'AL' means 'Sine LFO interpolated with linear interpolation'.

Globally, the accuracy loss is very much acceptable and stable for each loop. The accuracy reduction for loops A, B, C, D (Sine, Sawtooth, Square and Triangle LFOs) is always above the -1.5 line and in many cases over the -1 line, meaning that this reduction is not significant and in many cases undetectable by the human listener. We believe there are three reasons for this good performance (i) the produced signal's nature is benign for interpolation as indeed these are locally smooth functions (ii) there were no accumulation in the error (i.e. the results mapped to y[i] are independent of those mapped to y[i + 1]) (iii) the accuracy loss produced a harmonic distortion that was attenuated later by the synthesizer's filters.

Loops F, G, H and I (representing the integrated LowPass, HighPass, BandPass filters and the Delay FX unit) appear as outliers in this experiment. The distortion was always audible and in some cases slightly annoying. We believe the main reason for this is the recursive nature of the functions governing both the filters and the delay. This accumulates error over time and eventually the resulting signal is more heavily distorted than in the case when non-recursive signals are approximate using Approximate Unrolling. For example, the recursive equation ( 2) governs the biquad filters units. Note that the resulting value y[n] depends on y[n -1] and y[n -2], which we believe is the cause for the bigger looses in accuracy of loops F,G and H as the error accumulates.

y[n] = b0x[v] + b1x[n -1] + b2x[n -2] -a1y[n -1] -a2y[n -2]
(2) In general, loops interpolated with the linear interpolation degrade accuracy less than those approximated using nearest neighbor with exception of the loop implementing the Square LFO. This occurs because the governing equation for this unit (y[t] = sgn(sin(t))) had the property that in most cases y[t] = y[t+1]. Therefore, the nearest neighbor approximated loop version output is frequently the same that the original one.

Loops E, J and K, representing the LFO Mixer, the Phaser FX unit and the Output also yield good results ranging from non-audible to non-annoying. The computations in these loops did not accumulate error either.

RQ2: Execution Times Reduction

To evaluate the execution times of the optimized versions of the loops, we generate one microbenchmark per loop.We run the same microbenchmark with Approximate Unrolling turned on and off in the Virtual Machine and compared the execution times.

Determining whether there is an effective gain in terms of performance is a challenging task in Java [START_REF] Shipilev | Necessar(il)y Evil dealing with benchmarks, ugh[END_REF]. We run our microbenchmarks using the statistical methodology introduced by George [START_REF] Georges | Statistically Rigorous Java Performance Evaluation[END_REF] to ensure that the measurements of each run were consistent. All runs where performed in an Intel i7 i7-6600U CPU, 2.60GHz with 16GB RAM running Linux Ubuntu 16.04.

Results.

Figure 10 shows the results obtained by running our microbenchmark set. In all cases, the performance boost using linear interpolation was slightly smaller. This is because of the mean calculation performed in this variant of Approximate Unrolling. However, compared to the computations skipped, the median computation is not so expensive and there not much difference in the performance of both optimizations.

All loops, except the D and K loops, run between 140% and 180%. These is a remarkable benefit of our transformation: we can succesfully increase the performance with little impact (or in some cases none) on the quality of the signal. Loop D runs 200% faster than the original version. This is because its body is mainly composed of arithmetical operations only, which our implementation is very efficient removing.

It is interesting to notice that the optimized loop K (Output) actually runs slower. The accurate loop K simply copies the value of an array to another array. Therefore, the operations removed from the body are not more time consuming than the operations added by the nearest neighbor transformation and are even less time consuming than all computations added in the case of the linear interpolation.

RQ3: Energy savings

We evaluate our energy savings by estimating the total energy consumption of our microbenchmarks using JRALP [START_REF] Liu | Data-Oriented Characterization of Application-Level Energy Optimization[END_REF], a Java library that exposes to Java programs the the Intel's Running Average Power Limit (RAPL) Technoolgy [START_REF]Intel Âő 64 and IA-32 Architectures Developer's Manual[END_REF]. We first run the microbenchmark set and estimate energy consumption without optimizing any loop with Approximate Unrolling. In a second step, we repeated the experiment, this time turning the proposed optimization on and compared the energy consumption estimates of both runs.

Results.

The results displayed in figure 11 indicate a clear reduction in energy consumption for most loops. In general, most loops are able to reduce their consumption within 50% -70 % range. Also, the transformation based on linear interpolation is less energy effective than nearest neighbor as it introduces a few more computations. Again, loop K was the counter example, as the optimization introduced more operations that the one it was able to remove.

DISCUSSION

Section 4 shows promising results as they indicate that Approximate Unrolling can actually reduce the execution times and energy consumption of optimized loops without a significant impact in the signal's quality.

We choose to keep the data set small (11 loops), enabling us to provide a per-case analysis on the impact of the transformation on each loop and to understand the reasons behind the improvement (or not) in each case. The lessons learned on this case study drive the future work, as we now have a better understanding of which loops should gain more of the optimization. Loop K got its performance reduced because Approximate Unrolling interpolations were actually more expensive than the original loop. On the other hand, the LFO loops ran significantly faster and with less energy, without significant impact on the signal's quality. We learned that this was due to the non-recursiveness and smoothness of the function being mapped to the array, as well as the capacity of the system being approximate (the Osc3x synthesizer) to absorb the accuracy loss.

As with other approximate computing techniques, Approximate Unrolling is effective in domains where some degree of inexactitude can be allowed, e.g. as video and sound, numerical simulations and games. We have evaluated Approximate Unrolling using a single domain of application. This certainly raises the question of the applicability of Approximate Unrolling outside the field of sound. However, sound signals share many properties with other time series data such as sensor readings, stock share values and even video. Therefore, we believe Approximate Unrolling could be exploited in other domains as well.

Our results suggest that the situations in which Approximate Unrolling will work best are those in which the data stored close to each other in memory are also logically related to each other in the application's data model. This is the case in numerous data representations, like sound, triangle strips, sensor data, market trends, etc. For example, in sensor data (such as sound recoding and weather) two consecutive array elements will represent two readings close to each other in time; in 3D visualizations, triangles topologically close to each other will be stored in contiguous array slots.

Threads to validity.

We did extensive testing of our code and reviewed our microbenchmarks using best practices for microbenchmarking [START_REF] Georges | Statistically Rigorous Java Performance Evaluation[END_REF][START_REF] Shipilev | Necessar(il)y Evil dealing with benchmarks, ugh[END_REF]. However, Java microbenchmarking is a very difficult craft [START_REF] Shipilev | Necessar(il)y Evil dealing with benchmarks, ugh[END_REF] and is possible to overlook a details skeweding the measurement. Also, the Hotspot's C2 is a very complex piece of code. We introduced a modification to this software and there may be bugs. We hope that if such is the case, they have only a marginal quantitative impact, and not distort the qualitative essence of our findings. Our infrastructure is publicly available on Github.

RELATED WORK

The quest for energy savings and performance has made Approximate Computing an attractive research direction in the last few years [START_REF]A Survey of Techniques for Approximate Computing[END_REF], [START_REF] Xu | Approximate Computing: A Survey[END_REF], [START_REF] Sampson | Approximate Computing: An Annotated Bibliography[END_REF]. The approaches are numerous and diverse, as they use hardware, software or a mixture of both.

Hardware-oriented approximation techniques have proposed hardware components with approximation capabilities, such as FPUs that dynamically adapts the mantissa width [START_REF] Tong | Reducing power by optimizing the necessary precision/range of floating-point arithmetic[END_REF], approximate adders [START_REF] Gupta | IMPACT: Imprecise adders for low-power approximate computing[END_REF][START_REF] Shafique | A Low Latency Generic Accuracy Configurable Adder[END_REF], memory designs that exploit voltage scaling [START_REF] Chang | A Priority-Based 6t/8t Hybrid SRAM Architecture for Aggressive Voltage Scaling in Video Applications[END_REF][START_REF] Kumar | SRAM supply voltage scaling: A reliability perspective[END_REF] or that allow bit flipping [START_REF] Liu | Flikker: Saving Refresh-Power in Mobile Devices through Critical Data Partitioning[END_REF]. Also, general circuit design techniques has been proposed to exploit the accuracy-performance trade-off [START_REF] Avinash | Energy parsimonious circuit design through probabilistic pruning[END_REF][START_REF] Ranjan | ASLAN: Synthesis of Approximate Sequential Circuits[END_REF][START_REF] Venkataramani | Substitute-and-simplify: A Unified Design Paradigm for Approximate and Quality Configurable Circuits[END_REF]. Another trend is to take advantage of an existing non-determinism of the hardware [START_REF] Luo | Compressive Network Coding for Approximate Sensor Data Gathering[END_REF][START_REF] Sen | Design and implementation of an "approximate" communication system for wireless media applications[END_REF][START_REF] Stanley-Marbell | Approximating Outside the Processor[END_REF] or expose it to the developers to let them exploit it [START_REF] Bornholt | Uncertain\textlessT\textgreater: A First-Order Type for Uncertain Data[END_REF]36].

On the other hand, software-oriented techniques proposes ways to approximate existing algorithms automatically [START_REF] Sidiroglou-Douskos | Managing performance vs. accuracy trade-offs with loop perforation[END_REF][START_REF] Misailovic | Parallelizing Sequential Programs With Statistical Accuracy Tests[END_REF][START_REF] Mcafee | EMEURO: A Framework for Generating Multi-purpose Accelerators via Deep Learning[END_REF][START_REF] Samadi | Paraprox: Pattern-based Approximation for Data Parallel Applications[END_REF][START_REF] Schkufza | Stochastic Optimization of Floating-Point Programs with Tunable Precision[END_REF] or provides support for programming using approximation [START_REF] Ansel | PetaBricks: a language and compiler for algorithmic choice[END_REF][START_REF] Baek | Green: A framework for supporting energy-conscious programming using controlled approximation[END_REF][START_REF] Misailovic | Chisel: Reliability-and Accuracy-aware Optimization of Approximate Computational Kernels[END_REF][START_REF] Sampson | EnerJ: approximate data types for safe and general low-power computation[END_REF][START_REF] Carbin | Verifying Quantitative Reliability for Programs that Execute on Unreliable Hardware[END_REF].

Closest to our technique is Loop Perforation [START_REF] Sidiroglou-Douskos | Managing performance vs. accuracy trade-offs with loop perforation[END_REF], which skip some iteration of the loop or terminate it early. Loop Perforation and Approximate Unrolling differs in the scope where they can best applied, as well in the transformation made to the code. Loop Perforation works better in patterns that can completely skip some task, like Monte-Carlo simulations, computations iteratively improving an already obtained result or explorations to filter or select elements in a given search space. Approximate Unrolling do not skips any iteration of the loop, instead, it replaces the computations of some iterations by approximate ones. Approximate Unrolling best results are obtained when applied in loops mapping values to arrays and works good even if no previous value was mapped before. By construction, it behaves better than Loop Perforation in situations when no value of the array can be left undefined.

Another related technique to Approximate Unrolling is the Paraprox framework [START_REF] Samadi | Paraprox: Pattern-based Approximation for Data Parallel Applications[END_REF]. Paraprox works by detecting and proposing approximate alternative to patterns in parallel applications. One of the detected patters (stencil) also works on the assumption that nearby array elements are similar in image and video applications. Paraprox exploits this to skip memory accesses. Approximate Unrolling and Paraprox diverge in the sense that Paraprox uses the neighbor similarity to avoid memory accesses, while Approximate Unrolling uses it to avoid computations. The stencil pattern in Paraprox is also fine-tuned for Matrix arrays (images, videos), which is not the representation of sound or times series. This set apart both approaches w.r.t. the type of data each one is better suited for.

There are a number of approaches allowing the programmer to provide multiples alternatives to the same algorithm [START_REF] Baek | Green: A framework for supporting energy-conscious programming using controlled approximation[END_REF][START_REF] Ansel | PetaBricks: a language and compiler for algorithmic choice[END_REF]. In this context, Approximate Unrolling can be used as a way to provide one of such alternatives where accuracy can be exchanged for performance or energy savings. Similarly, several languages have been designed to indicate the parts of a program that can be approximate. Examples of this are EnerJ [START_REF] Sampson | EnerJ: approximate data types for safe and general low-power computation[END_REF], FlexJava [START_REF] Park | FlexJava: Language Support for Safe and Modular Approximate Programming[END_REF] and Rely [START_REF] Carbin | Verifying Quantitative Reliability for Programs that Execute on Unreliable Hardware[END_REF]. Separating the parts of a program that can be approximate is an orthogonal concern to Approximate Unrolling. In our experiments we used EnerJ annotations to select one loop to approximate out of all the loops our optimization could target in the entire program, allowing us to assess the impact of a single loop each time and showing that our technique is indeed complementary with these approximate languages.

CONCLUSIONS & FUTURE WORK

In this paper we have described Approximate Unrolling, an a transformation that approximates the computation inside certain loops. We formally described the shape of the loops selected for Approximate Unrolling, as well as the transformations it performs to reduce execution times and energy consumption at the expenses of accuracy loss. We have also proposed an implementation of this transformation inside the OpenJDK Hotspot C2 Server compiler.

The empirical assessment of this transformation on the loops of the JSyn sound library demonstrated the ability of Approximate Unrolling to effectively trade accuracy for resource gains. We learned that not all loops respond equally well to the approximation and we gained some insights on the causes for this. Hence, our future work will consist in including these findings into the optimization, improving the detection process using a cost function that favors loops whose bodies (i) contains more instructions than the ones introduced by Approximate Unrolling (ii) have a minimal number of instructions depending on a value calculated in a previous iteration (iii) represents an smooth function. Then, the selection will filter out those loops below a given threshold of the cost function.

Another direction in the future is to assess the applicability of Approximate Unrolling in other domains. We focused this work on a single case study to gain precise insights about the nature of loops that can benefit from Approximate Unrolling. Yet, in future work we will evaluate the impact of approximating more loops and more iterations in each loop.

  A [] = new double [ N ]; double stride = Math . PI * 2 / N ; f o r ( i n t i = 0; i < N ; i ++ ) A [ i ] = Math . sin ( i * stride ) ; Listing 1: A loop mapping a sine wave into an array double A [] = new double [ N ]; double stride = Math . PI * 2 / N ; A [0] = Math . sin (0) ;

Listing 2 :Figure 1 :

 21 Figure 1: Sine waves generated by the motivation examples. The upper wave is generated by the loop of listing 1, while the middle and lower ones are generated by loops of listing 2 and 3, respectively.

Figure 5 :

 5 Figure 5: The ideal graph of the example loop of listing 4. Dashed arrows represent control edges and solid arrows represents data edges.

Figure 6 :

 6 Figure 6: The ideal graph for the unrolled loop of listing 4 before approximating. Solid arrows represent data edges.

1

  B8: # 2 movl [RCX + #16 + R9 << #2], R8 # int 3 movl R9, R10 # spill 4 addl R9, #3 # int 5 imull R9, R9 # int 6 movl R8, R10 # spill 7 incl R8 # int 8 imull R8, R8 # int 9 movl [RCX + #20 + R10 << #2], R8 # int10 movl RDI, R10 # spill 11 addl RDI, #2 # int 12 imull RDI, RDI # int 13 movl [RCX + #24 + R10 << #2], RDI # int 14 movl [RCX + #28 + R10 << #2], R9 # int 15 addl R10, #4 # int 16 movl R8, R10 # spill 17 imull R8, R10 # int 18 cmpl R10, R11 19 jl,s 7

Figure 7 :

 7 Figure 7: The ideal graph for the unrolled loop of listing 4 after Approximate Unrolling have modified the graph using nearest neighbor interpolation.

Figure 8 :

 8 Figure 8: Diagram showing how the JSyn units are connected to build our Osc3x synthesizer.

Figure 9 :

 9 Figure 9: PEAQ metric results for each approximate loop (0 to 1 -Not audible degradation; 1 to 2 -audible not annoying; 2 to 3 -slightly annoying; 3 to 4 -annoying; 4 & below -useless). Gray boxes represents loops approximated with nearest neighbor, while white boxes with linear interpolation.

Figure 10 :

 10 Figure 10: Performance improvement for each approximate loop. Like before, gray boxes nearest neighbor approximation and while white boxes linear interpolation.

Figure 11 :

 11 Figure 11: Energy consumption behavior for each approximate loop. Once again, gray boxes nearest neighbor approximation and while white boxes linear interpolation.

  2: Common definitions and rules used by both linear and nearest neighbor transformations

			ForL		(F orL(I0, B, i := i + n) C, σ) → (I0; if (B) P re(ξ) else SKIP, σ)
			ExL	(ExL(ξ), σ) → (i := i + 2 * n; if (B) C; AprxL(ξ) else P ost(ξ), C, σ)
			AprxL	(AprxL(ξ), σ) → (a[i -n] := (a[i] + a[i -2 * n]) * 0.5; ExL(ξ), σ)
	Pre	(P re(ξ), σ) → (C; ExtL(ξ), σ)	Post	(P ost(ξ), σ) → (i := i -n; if (B) C; i := i + n; else SKIP, σ)
		Figure 3: Small step SOS of Approximate Unrolling using linear interpolation
	ForN	(F orN (I0, B, i := i + n) C, σ) → (I0; ExN (ξ), σ)	ExN	(ExN (ξ), σ) → (if (B) C; AprxN (ξ), else SKIP, σ)
		AprxN	(AprxN (ξ), C, σ) → (i := i + n; if (B)a[i] := a[i -1]; i := i + n; ExN (ξ) else SKIP, σ)
		Figure 4: Small step SOS of Approximate Unrolling using nearest neighbor
	target for ::= 'for' '(' expression ';' expression ';'
	update expression ')' t body
	update expr ::= identifier '+=' integer
	t body ::= '{' statement array assign statement '}'
	array assign ::= expression '[' index expr ']' '='
	expression
	index expr := expression
	Grammar 1: Grammar of for loops targeted by Ap-
	proximate Unrolling

Table 1 :

 1 Loops targeted by Approximate Unrolling in our case study.

	Loop	Function	Executions in 20s (Min, Max)
	A. Sine LFO	Generates a sine wave.	Between 441K -1.2M depending on preset
	B. Triangle LFO	Generates a triangular impulse	Between 441K -1.2M depending on preset
	C. Square LFO	Generates an square impulse	Between 441K -1.2M depending on preset
	D. Sawtooth LFO Generates a sawtooth impulse	Between 441K -1.2M depending on preset
	E. Mixer	Mix the LFO's output in one signal	Mono: 441K -Stereo: 882 K
	F. Low Pass	Filters out higher frequencies	Mono: 441K -Stereo: 882 K
	G. High Pass	Filters out lower frequencies	Mono: 441K -Stereo: 882 K
	H. Band Pass	Attenuates higher and lower frequencies around a range Mono: 441K -Stereo: 882 K
	I. Delay	Creates a delay effect	Mono: 441K -Stereo: 882 K
	J. Phaser	Creates a phaser effect	Mono: 441K -Stereo: 882 K
	K. Output

https://github.com/approxunrollteam

https://www.image-line.com/support/FLHelp/html/ plugins/3x%20OSC.htm


Yasser Fadlallah
email: yfadlallah@gmail.com

Paul Ferrand

Leonardo S Cardoso

Jean-Marie Gorce

Interference Alignment for Downlink Cellular Networks: Joint Scheduling and Precoding

Interference Alignment (IA) is technique that, in a large sense, makes use of the increasing signal dimensions available in the system through MIMO and OFDM technologies in order to globally reduce the interference suffered by users in a network. In this paper, we address the problem of downlink cellular networks, the so-called interfering broadcast channels, where mobile users at cell edges may suffer from high interference and thus, poor performance. Starting from the downlink IA scheme proposed by Suh et al., a new approach is proposed where each user feeds back multiple selected received signal directions with high signal-to-interference gain. A exhaustive search based scheduler selects a subset of users to be served simultaneously, balancing between sum-rate performance and fairness, but becomes untractable in dense network scenarios where many users send simultaneous requests. Therefore, we develop a sub-optimal scheduler that greatly decreases the complexity while preserving a near-optimal data rate gain. More interestingly, our simulations show that the IA scheme becomes valuable only in correlated channels, whereas the matched filtering based scheme performs the best in the uncorrelated scenarios.

I. INTRODUCTION

Increasing the data rate in wireless networks usually comes through a larger bandwidth, or a more efficient use of the available bandwidth. In cellular applications, the performance is interference-limited in most cases, meaning that increasing the transmission power does not substantially improve the network capacity. On the other hand, separating users in the time or frequency domain leads to very inefficient usage of the available resources. The key challenge is thus to balance interference avoidance and spectrum reuse to reach an optimal trade-off between spectral and energy efficiency [START_REF] Tsilimantos | Spectral and energy efficiency trade-offs in cellular networks[END_REF].

This challenge has been addressed in the past, for instance using frequency/code planning in 2G/3G networks or with cooperative multiple point antennas in 4G [START_REF]Coordinated multi-point operation for LTE physical layer aspect (Release 11)[END_REF]. Dynamic interference management then became a strategic option to not only improve the spectral efficiency but also to achieve greater overall energy efficiency. The IA concept has been proposed first by [START_REF] Maddah-Ali | Communication over MIMO X channels: Interference alignment, decomposition, and performance analysis[END_REF] and extended by [START_REF] Cadambe | Interference alignment and degrees of freedom of the-user interference channel[END_REF], it gave an interesting approach for exploiting interference in a K-users interference channel (IC) situationThe theoretical achievements of IA have been largely discussed, e.g. in [START_REF] Maddah-Ali | Communication over MIMO X channels: Interference alignment, decomposition, and performance analysis[END_REF]- [START_REF] Gou | Degrees of freedom of the user MIMO interference channel[END_REF]. One of the key results is that, for a number of theoretical setups, IA can transform interference limited networks into interference-free networks, regardless of the number of users K [START_REF] Cadambe | Interference alignment and degrees of freedom of the-user interference channel[END_REF].

In the downlink cellular network, the IA extension has been addressed in several research works, e.g. [START_REF] Aziz | System-level performance study of interference alignment in cellular systems with base-station coordination[END_REF]- [START_REF] Suh | Downlink interference alignment[END_REF]. For example, [START_REF] Tresch | Clustered interference alignment in large cellular networks[END_REF] proposed to form clusters of base stations (BSs) assuming a global knowledge of channel state information (CSI). As results, only users in the center of clusters benefit from slight data rate improvementOther results showed questionable performance gains and several limitations [START_REF] Aziz | System-level performance study of interference alignment in cellular systems with base-station coordination[END_REF]. Among the major issues is that IA sacrifices half of the space dimensions in order to avoid interference for every user in the cluster, whereas some of them may not suffer strong interference.

More efficiently, Suh et al. in [START_REF] Suh | Downlink interference alignment[END_REF] proposed a dynamic precoding scheme that attempts to balance the performance gain of matched filtering for the best users with IA for celledge users. By using a fixed rank-deficient precoding step at the transmitter, each BS can ensure that users always see a subspace in their effective channel where interference is reduced or eliminated. The idea is that each mobile measures and feeds back its own free subspace to its main BS, which jointly schedules the UEs so as to maximize the overall capacity. This scheme is particularly attractive in the context of dense cellular networks because with IA and thanks to channel properties, the freed subspace perceived by interfered mobiles is different for each of them. And hence, it becomes more probable to find users for which optimal transmission spaces are quasi-orthogonal as the size of the network increases. Therefore, by performing simultaneously users scheduling and precoding, the BS highly increases the chance to maximize the system capacity.

The aforementioned IA scheme only assumes to feedback the interference-free direction. However, the additional signal directions may also present a low interference level due to fading on the interfering channel. Therefore, we propose that in addition to the interference-free directions, the users feed back alternative directions, which increases the number of candidate directions at the BS and makes the scheduler more complex. In this paper, a heuristic scheduling process is proposed to decrease the algorithmic complexity while preserving near-optimal performance. Moreover, we focus on a numerical evaluation of the IA performance compared to the matched filtering (MF). Surprisingly, our simulations show that the IA technique gains interest when the crossed channels are correlated while the MF technique performs the best in the uncorrelated case scaling up linearly with the signal-tointerference and noise ratio (SINR).

Notations: boldface upper case letters and boldface lower case letters denote matrices and vectors, respectively. The superscripts (.) † stands for the transpose conjugate matrices, respectively. I n denotes the identity matrix of dimension n. The 2 norm is denoted as ||.||.

II. SYSTEM MODEL

A downlink cellular network with B BS and N m user equipments (UEs) in the m th BS is considered. The l th UE in the m th BS receives S lm streams. All BSs and UEs are equipped with M antennas. The transmission scheme is based on a MIMO-OFDM with K available sub-carriers yielding a total M K = M × K dimensions for the transmitted signal, in both frequency and spatial domain. A complex matrix P of dimension

M K × (M K -N f ) is used at each BS (N f ≥ 0).
The data symbols at a given BS are carried out, each by a precoding vector v j lm (l, m, j denote the user, the BS, and the stream indices, respectively), and then further precoded using P . Independent flat fading channels are assumed for all subcarriers. The transmitted signal of the m th BS is given by

x m = Nm l=1 V lm x lm , (1)
where x lm contains the data for each of the S lm streams of user l in BS m, and V lm is the (M K -N f ) × S lm complex precoding matrix of user l. For the sake of simplicity, P is assumed the same for all BSs with elements selected as p ij ∈ C -a truncated Fourier or Hadamard matrix being a good candidate in practice. The condition N f ≥ 0 in P means that the transmit signal at each BS occupies a reduced signal space of dimension M k -N f and leaves the rest N f dimensions free.

The maximum number of streams in the reduced space of a given cell is S := M K -N f and the DoF is equal to

M K -N f M k
. The received signal at the l th UE of the m th cell is given by

y lm = H lm P V lm x lm desired signal + H lm P Nm i =l V im x im intra-cell interference + B i =m H li P x i inter-cell interference +w l , (2)
where H lm is the direct channel matrix between the m th BS and the l th UE,

x i = Ni n V in x in
, and w l is the M K complex circularly symmetric additive white Gaussian noise (AWGN) vector with zero mean and covariance matrix equals to σ 2 I M K . Each UE has perfect knowledge of at least the direct channel linking it to its main BS, and of its main interferers through some pilots as described e.g. in [START_REF]Enhanced performance requirement for LTE User Equipment (UE) (Release 11)[END_REF]. In traditional transmission schemes, the model is nothing but (2) except that P is an identity matrix. This means that all dimensions are exploited at the expense of strong inter-cell interference at cell-edges, which results in poor performance. By using a truncated, rankdeficient P , the BS can save some available dimensions to let the other BSs in the neighbors serve their users in an interference-free subspace. This technique allows each UE to have N f interference-free streams. The decoded signal at user l of the m th BS is given by

U † lm y lm = G lm V lm x lm + G lm Nm i =l V im x im + U † lm B i =m
H li P x i + U † lm w l , (3)
where G lm = U † lm H lm P is the direct equivalent channel between l th user and the m th BS.

III. INTERFERENCE ALIGNMENT IN DOWNLINK

In [START_REF] Suh | Downlink interference alignment[END_REF], two IA schemes have been proposed, assuming only one stream per user. The first scheme is based on a Zero-Forcing (ZF) criterion. This means that each UE estimates the interfering channels and calculates the decoding matrix as their null space vector, i.e. U lm collapses to a vector u lm verifying:

u † lm Nri i =m H li P x i = 0, subject to ||u lm || = 1. ( 4
)
where N ri is the number of interfering BSs to be canceled. The basic case is obtained for N ri = 1 which holds for the strongest interferer. Each user calculates the equivalent channel G lm given in ( 3) and feeds it back to its BS, which in turns apply a scheduler that selects a subset of users to serve.

The selected users have their equivalent channels denoted clm collected in a matrix as

Cm = [c 1m , • • • , cSm ],
and then a ZF beamforming scheme is applied to compute orthogonal transmission vectors avoiding intra-cell interference in (3),

[v 1m , • • • , vSm ] = C † m Cm C † m -1 . (5)
Each precoding vector is normalized to ensure a constant power: v0 im = P vim ||P vim|| . The second scheme exploits a Minimum Mean Square Error (MMSE) criterion and takes into account the interference-plusnoise (IN) covariance in addition to the strongest interferer properties. The decoding vector is given by:

u lm = Φ -1 lm H lm P v 0 lm ||Φ -1 lm H lm P v 0 lm || . ( 6
)
Assuming the knowledge of the strongest interferer channel, the IN covariance Φ lm is

Φ lm = (σ 2 + INR rem )I M K + p S H ln P V n V † n P † H † ln , (7)
with p the total transmit power, INR rem the remaining interference, and

V n = [v 1n , • • • , v Sn ]
the precoding matrix of the n th BS. The initial vector v 0 lm can be selected so as to maximize the beamforming (BF) gain at the receiver, and chosen as the eigenvector associated to the maximum eigenvalue of H † lm P † Φ -1 lm H lm P . As can be seen from ( 6) and ( 7), one major difference comparing to the first scheme is that the interference-free subspace is no longer fixed and becomes dependent on the precoder choices of other BSs. However, in practice, we consider that in average, V n V † n approaches an identity matrix because of the ZF BF step. The strict reduction of the coding space with the matrix P can also be relaxed using a full square matrix with the last N f columns weighted by a factor 0 < κ < 1. The motivation behind introducing the factor κ is to be able to tweak the rank-deficiency of P and color the interference space [START_REF] Suh | Downlink interference alignment[END_REF]. This approach gives more flexibility in the coding strategy and allows to adapt to situations where pure interference alignment is not necessary and may be outperformed by interference management. The new mixing matrix P is given by

P = [p 1 , • • • , p S , κp S+1 , • • • , κp M K ] , (8)
where the vectors p i ∈ C M K are mutually orthogonal.

IV. GENERALIZED IA SCHEME

The above IA schemes minimizes the dimensions lost in the signal space of each BS thanks to the controlled freed dimensions. While achieving a high SNR gain, it only assumes a stream per user, which severely restricts the dimensions of the problem. In many practical situations, we observed through simulations how this lack of diversity limits the system performance. Indeed, in each cell, some users are close to their main BSs and do not suffer from strong interference. In this case, it appears more efficient to let the user feeds back not only the interference-free signal direction but also additional directions presenting a sufficiently high overall SINR. By letting each user to feed back several directions, the scheduler has more flexibility to optimize the coding scheme.

A. Optimal coding directions

Each UE first selects the optimal directions that maximize the received SINR, with inter-cell interference only. The decoder is initialized as

U lm = Φ -1 lm H lm P ||Φ -1
lm H lm P || . The equivalent channel is then given by

G lm = P † H † lm Φ -1 lm H lm P . (9)
The optimal receive directions are computed using the eigenvalue decomposition of G lm , with eigenvalues Λ lm and eigenvectors C lm defined as

C † lm Λ lm C lm = G lm , (10)
where the elements of Λ lm are sorted in decreasing order, meaning that the first columns of C lm provide the optimal receiving directions and may be used as decoding directions.

In order to maximize the received SINR, the decoding matrix is chosen as

U d lm = Φ -1 lm H lm P C d lm ||Φ -1 lm H lm P C d lm ||
, and the precoding matrix as V lm = C d lm , where d is the number of selected streams for a given user. The resulting SINR of the i th stream can be easily found equal to λ i lm the i th element of Λ lm .

B. Directions feedback

Motivated by the fact that some users may not suffer a high interference level, we suggest that each user feeds the best L ≥ N f directions calculated in [START_REF] Tresch | Clustered interference alignment in large cellular networks[END_REF] back to its BS. In this way, UEs in the center of the cell preferably feed back decoding directions corresponding to strong eigenmodes of the direct channel, whereas cell-edge users feed back interferenceminimizing directions. For the sake of consistency, the cell and user indexes are omitted in the upcoming equations. Each user thus feeds back a set of candidate decoding directions {(c 1 , λ 1 ), • • • , (c L , λ L )} , where c i and λ i are the optimal coding direction and the SINR for the i th stream, respectively. It is worth noting that the λ i gain does not take into account the intra-cell interference, and indirectly is only an estimate of the SINR in the direction c i . When a BS serves only one user, the directions c i are mutually orthogonal, and thereby there is no intra-cell interference. In the multi-user MIMO case, the directions for two different users, e.g. c i and c j are not necessarily orthogonal, which adds an extra interference power of λ i ||c i c j ||. In order to cancel the intra-cell interference, we may call for a ZF-based precoding scheme as given in (5) 1 . However in doing so, the precoders are no longer perfectly aligned with the optimal receive directions, which introduce a potential rate loss in the network overall performance.

C. Polynomial time sub-optimal scheduling

The set of all candidates S = {(c 1 , λ 1 ), • • • , (c Nc , λ Nc )} is built by collecting all N c streams candidates from all users. Assuming a dense network scenario where N c is much greater than the number of available streams S, each BS has to select the best candidates in order to maximize a utility function defined as the sum-rate (with eventually fairness weights, see below). The optimal way is to apply an exhaustive search and to select the best subset U * that results in the highest sum-rate. The optimization problem is defined as

C(S) = max U ∈S k∈U ω k log 2 1 + p S λ k ||c k vk || , ( 11
)
where U is a given candidates streams subset, and ω k is a per-UE weight updated after each transmission in order to provide fairness among the different UEs. Since several directions are fed back per user, the dimensions of S increase exponentially, which in turns makes the optimal scheduling challenging as 1 Other precoding types than the ZF can also be straightforwardly applied, see [START_REF] Spencer | An introduction to the multi-user MIMO downlink[END_REF]. But this does not change the core of our work.

Algorithm 1 Sub-optimal heuristic algorithm

1: S 0 u ← {ŝ 0 } 2: S 0 c ← S -{ŝ 0 } 3: Q opt ← C({ŝ 0 }) 4: while |S j u | < S do 5: for i ← 1 : |S j c | do 6: Q ← C(S j u ∪ {s i }) 7: if Q > Q opt then 8: Q opt ← Q 9:
ŝj ← s i 10:

j ← j + 1 11: S j u ← S j-1 u ∪ {ŝ j } 12: S j c ← S j-1 c -{ŝ j } 13:
if {ŝ j } ← ∅ then 14:

break the network grows. The optimization problem in [START_REF] Westreicher | Interference alignment over partially connected interference networks: Application to the cellular case[END_REF] is in known as NP-hard, and its computational cost may be written as

cost = O N s S × cost zf , (12)
where cost zf is the complexity cost of a ZF precoding scheme. It is quite clear that for dense scenarios, the search among all candidate streams is not feasible. We rather propose a sub-optimal heuristic scheduling, that greatly decreases the complexity while preserving a near-optimal performance. For a given BS, the heuristic privileges the streams that provide higher rates and less inter-correlation.

Let us denote ŝ0 the stream with the highest rate among all N c streams. At iteration 0, we define the set of the chosen streams as S 0 u = {ŝ 0 }, the set of the remaining streams as S 0 c = S -{ŝ 0 }, and the utility function as C(S 0 u ) given in [START_REF] Westreicher | Interference alignment over partially connected interference networks: Application to the cellular case[END_REF]. At the i th iteration, the utilities for s

∈ S i-1 c are C(S i u , s) = k∈S i-1 u ∪{s} ω k log 2 1 + p S λ k ||c k vk || , (13)
and the stream ŝi with maximum utility is selected. The sets of remaining and chosen streams are updated according to

S i u = S i-1 u ∪ {ŝ i }, S i c = S i-1 c -{ŝ i }. (14)
The algorithm stops when no more gain can be achieved. In [START_REF] Suh | Downlink interference alignment[END_REF], c k is the fed back direction for a given stream, and vk results from the ZF precoding scheme applied on the vectors of S i-1 u ∪ {s}. Looking at the computational cost of the heuristic algorithm given in Alg.1, we can readily see that the complexity is polynomial and the cost search process is upper-bounded by

cost sub = O (N s - S -1 2 )S × cost zf , (15)
since only two loops are required.

V. SIMULATION RESULTS

The performance of the proposed scheme has been evaluated through exhaustive simulations in different load scenarios. A system level simulator with 7 cells is used, each cell being divided in 3 sectors. For the exposed results, we only consider the center cell in which the UEs are uniformly distributed, although all cells support users and compute their precoders accordingly. We assume a proportional-fair scheduling by updating the scheduling weight of each user as

ω l k = r min max(r min , R l k,avg ) , (16)
where r min is a threshold under which any rate is assumed null, and R l k,avg is the average number of bits transmitted until the l th transmission. The spectral efficiency is compared to that of a classic OFDM scheme as a reference, where all interference are considered as noise. In this paper, N u = 10 users per cell in average are considered, and an overall coding space limited to M K = 4 dimensions with K available sub-carriers and M antennas at the BSs and the UEs. Our system level simulator assumes a regular placement of BSs and random users in full buffer. More information about the propagation model used here is given in [START_REF]Reference scenarios[END_REF] (cf GT doc2a). The performance are evaluated for both channel correlation levels: low and medium, with a correlation coefficient equal to 0 and 0.3, respectively. A simplified resource block structure is adopted to save computation time, the channel is abstracted as: K sub-carriers with independent fading matrices, and each M × M fading matrix includes correlation. Each UE feeds back M K -N f preferred receive directions. By assuming M K = 4 and N f = 1 free dimension at each BS, the BS chooses S = 3 streams to be served using IA with scheduling based on Alg.1. The capacity is truncated to a maximum of 8 bits per resource use. The Monte-Carlo simulations are run for 100 independent scenarios. For each scenario, the geometry is fixed and the system is run for 100 successive transmissions. As a reference, we provide the CDF of the received SINR in Fig. 1 for our simulator, calibrated to match system-level simulations of other partners in the Greentouch project. In the following, we assume that each UE has perfect estimate of the strongest interferer while it assumes others as noise.

In comparison to the reference scenario without IA in a 4×4 uncorrelated MIMO scenario, one can observe from Fig. 2 significant gain in the low to medium SINR region, e.g. the gain varies between 1 -1.2 bits/s/Hz at SINR 0dB depending on the parameter κ. However, it decreases for high SINR because users are no longer suffering strong interference. Comparing to the MF based scheme where each BS exploits all dimensions leaving no free dimension for adjacent cells, a gain is only observed for very low SINR values i.e. SINR< -4dB. Beyond this value the MF scheme has an increasing gain specially for high SINR, where it also enjoys an almost constant gain over the OFDMA scheme. This means that due to channel diversity, a UE can frequently find a direction with low interference. The performance of the IA scheme for κ = 0 and κ = 0.4 are similar except that a slight gain is observed for SINR> 0dB. Regarding the case with κ = 1 and S = 3, it can be seen that it outperforms the case where κ = 0 and κ = 0.4 for SINR> 2dB. This is due to the additional dimension gained when κ = 1. Similar observations have been made for the MIMO-OFDM with M = 2 and K = 2. Except that in this case, the schemes with higher κ always result in a SE gain. This means that the low-interference modes are basically created by the block diagonal channel, and are almost independent of the precoding design.

Contrarily to the uncorrelated configuration, in 2 × 2 correlated channel with a factor of 0.3 between the antennas and K = 2 uncorrelated subcarriers, the performance are surprisingly different as shown in Fig. 4. For example, the IA schemes for different κ greatly outperform the MF scheme for all SINR values, and result in significant gains compared to the OFDM scheme in the low-to-medium SINR region. This means that since all modes are correlated, an almost interference-free mode does no longer exist unless it is freed. And hence, the performance are degraded. However, comparing the IA scheme with different κ, it can be seen that κ = 1, S = 3 results in a rate-loss for SINR< -3dB, and yields a gain beyond 8dB since more dimensions are available for precoding.

VI. CONCLUSION

This paper addressed the performance of IA transmission in a downlink cellular network. We have generalized the scheme proposed by [START_REF] Suh | Downlink interference alignment[END_REF] and have came up with a near-optimal lowcomplexity scheduler based on heuristic optimization. We have also shown that unlike the results obtained in [START_REF] Aziz | System-level performance study of interference alignment in cellular systems with base-station coordination[END_REF], applying a joint scheduling-precoding based on IA transmission can yield significant gains for users suffering strong inter-cell interference. Also the IA scheme becomes valuable in correlated channels where the MF scheme yields poor performance. Future works should focus on avoiding the data-rate loss caused for users enjoying high SINR which could be obtained by tuning the fairness coefficients.

CFigure 1 .

 1 Figure 1. Calibration results for our simulator (INRIA) with respect to other vendors and operators in the Greentouch consortium. This figure illustrates the distribution of the SINR experienced in average by the users, so-called the geometry.

Figure 2 .

 2 Figure 2. Performance comparison of IA scheme for different κ vs the matched filtering (MF) scheme and the basic MIMO-OFDM scheme in an uncorrelated scenario with M = 4 , K = 1.

Figure 3 .

 3 Figure 3. Performance comparison for different κ vs the MF and the basic MIMO-OFDM schemes in an uncorrelated scenario with M = 2, K = 2.

  /s/Hz) medium correlated transmission, 2x2 MIMO-OFDM (K=2) in 10-user scenario IA, κ=0,S=3 IA, κ=0.4,S=3 IA, κ=1,S=3 MF, κ=1,S=4 OFDMA, S=4

Figure 4 .

 4 Figure 4. Performance comparison for different κ versus the matched filtering based scheme and the basic MIMO-OFDM reference scheme in a medium correlated scenario with M = 2 and K = 2.

  a

					uncorrelated transmission, 2x2 MIMO-OFDM (K=2) in 10-user scenario
		8
			IA, κ=0,S=3
		7	IA, κ=0.4,S=3
		6	IA, κ=1,S=3 MF, κ=1,S=4
	SE (bits/s/Hz)	3 4 5	OFDMA, S=4
		2
		1
	-10 -8 0	-6	-4	-2	0	2	4	6	8	10	12	14	16	18	20	22
										SINR [dB]