Kosei Shinoda

Julian Freytes

Abdelkrim Benchaib

Jing Dai

Hani Saad

Xavier Guillaud

Energy Difference Controllers for MMC without DC Current Perturbations

Keywords: High Voltage Direct Current (HVDC), Modular Multilevel Converter (MMC), Energy Difference

The Modular Multilevel Converter (MMC) is a most promising converter technology for the High Voltage DC application. The complex topology of the MMC requires several additional controllers to balance the energy in the capacitors which are distributed all over the converter. Typically, there is a requirement of two controls; one is the regulation of the total energy in each leg, and the other is the distribution of the energy between the upper and the lower arms. This paper presents control strategies for the latter one being capable of distributing the energy only by internal power flow, so that undesired interference with the associated grids can be completely avoided. The proposed controls are achieved by forcing the common mode currents to be balanced while keeping the classic cascaded control structure as much as possible. The effectiveness and advantage of the proposed solutions are demonstrated by simulations.

I. INTRODUCTION

The Modular Multilevel Converter (MMC) is a new type of converter which attracts large attention due to its several advantages compared to the conventional two-level Voltage Source Converter (VSC). MMC was first introduced in [START_REF] Lesnicar | An innovative modular multilevel converter topology suitable for a wide power range[END_REF] and the basic concepts and the operational principles are presented in [START_REF] Antonopoulos | On dynamics and voltage control of the modular multilevel converter[END_REF] [START_REF] Debnath | Operation, control, and applications of the modular multilevel converter: A review[END_REF].

The general topology of the MMC consists of a large number of two-level converter modules, so-called sub-modules. This modular topology enables to output nearly ideal sinusoidal voltage waveform, allowing prevention of harmonic injection to the power system; hence, implementation of large filters are no longer needed. Furthermore, its scalable modular topology allows to easily adjust the voltage rating, thus, it is suitable for High Voltage Direct Current (HVDC) Transmission Systems applications.

In general, the conventional VSCs type converters are attached with a large station capacitor at their DC side. In the MMC, however, the capacitors are distributed all over the converter. This makes the balancing and control of the distributed energies as an important aspect [START_REF] Saad | Mmc capacitor voltage decoupling and balancing controls[END_REF]. In literature, the requirements on the energy balancing are often divided into two [START_REF] Munch | Integrated current control, energy control and energy balancing of modular multilevel converters[END_REF] [START_REF] Wenig | Simulation framework for dc grid control and acdc interaction studies based on modular multilevel converters[END_REF]:

1) Horizontal Balancing: The energy stored in each leg must be regulated to achieve equal energy in all three phase legs. This can be achieved by a simple control which regulates the deference between the power inflow and outflows to/from the MMC in each phase. 2) Vertical Balancing: The difference between the energy stored in the upper and the lower parts must be controlled to avoid having an excess energy in one of the arms. This is also refereed to as "Energy Difference Control" [START_REF] Bergna | An energy-based controller for hvdc modular multilevel converter in decoupled double synchronous reference frame for voltage oscillation reduction[END_REF]. This paper discuss on the control strategies of Energy Difference. The control schemes proposed in [START_REF] Antonopoulos | On dynamics and voltage control of the modular multilevel converter[END_REF] and [START_REF] Delarue | Energetic macroscopic representation and inversion based control of a modular multilevel converter[END_REF] use additional oscillatory components on the common mode currents to regulate this energy difference. However, this approach can result in unwanted interferences with the DC power which may lead to fluctuations of the DC grid voltage. [START_REF] Munch | Integrated current control, energy control and energy balancing of modular multilevel converters[END_REF] presented a novel control structure utilizing a periodic linear quadratic regulator, and referred to balanced reference generation. Inspired by [START_REF] Munch | Integrated current control, energy control and energy balancing of modular multilevel converters[END_REF], this paper proposes different control structures, which enables to regulate energy difference without disturbing the DC grid. In this work, the cascaded control structure such that energy controllers adjusting the references of inner current control is preserved. Thus, the proposed controllers are simpler and more intuitive.

This paper is structured as follows. Section 2 recalls the MMC topology and the fundamental variables as well as its control hierarchy. In Section 3, the proposed energy difference controllers are presented, and difference in structure is highlighted. The functionality of the proposed controllers is validated by simulations carried out on EMTP-RV platform.

II. MODULAR MULTILEVEL CONVERTER

A. Arm Average Model (AAM)

The topology of the AAM is recalled in Fig. 1. There is one leg for each phase a, b, c. Each phase leg can be divided into upper and lower parts called arms. This model assumes that the voltages of all the sub-module capacitors in each arm are maintained in a close range, thus allowing to replace them by an equivalent capacitor. Therefore, each arm includes an arm inductance L arm , an arm resistance R arm and an equivalent capacitor C tot in parallel with a chopper.

The voltages v uj (v lj ) and currents i uj (i lj ) of each arm j (j = a, b, c) are described by the following equations:

v uj = m uj v Ctotuj , v lj = m lj v Ctotlj (1) v gc v g b v ga R f L f R f L f R f L f i gc i g b i ga i ua i u b i uc i la i l b i lc v dc 2 v dc 2 i dc i dc R arm L arm R arm L arm R arm L arm L arm R arm L arm R arm L arm R arm v ua v la
i Ctotuj = m uj i uj , i Ctotlj = m lj i lj (2)
where v Ctotuj (v Ctotlj ) is the voltage across the upper (lower) arm equivalent capacitor, m uj (m lj ) is the corresponding instantaneous duty cycle and i Ctotuj (i Ctotlj ) is the current through the upper (lower) arm capacitor. The voltage and current of the equivalent capacitor are related through the capacitor equation:

i Ctotuj = C tot dv Ctotuj dt , i Ctotlj = C tot dv Ctotlj dt (3)
Applying Kirchhoff's law, the following equations are derived for each phase j:

vdc 2 -v uj -L arm diu j dt -R arm i uj -L f dig j dt -R f i gj -v gj = 0 (4) -vdc 2 + v lj + L arm dil j dt + R arm i lj -L f dig j dt -R f i gj -v gj = 0 (5)
The addition of (4) and (5) yields:

v vj -v gj = L ac eq di gj dt + R ac eq i gj (6)
where:

i gj = i uj -i lj , v vj = -v uj + v lj 2 , (7)
R ac eq = R arm + 2R f 2 , L ac eq = L arm + 2L f 2 (8)
Equation ( 6) describes the AC side dynamics of the AAM. The subtraction of (4) and [START_REF] Munch | Integrated current control, energy control and energy balancing of modular multilevel converters[END_REF] gives:

v dc 2 - v dif fj 2 = L arm di dif fj dt + R arm i dif fj (9)
where the differential current i dif f and voltage v dif f are defined as:

i dif fj = i uj + i lj 2 , v dif fj = v uj + v lj 2 (10)
Equation ( 9) describes the DC side dynamics of the AAM. The DC current will be then expressed as:

i dc = i dif fa + i dif f b + i dif fc (11)
P * ac Q * ac Controller Coupling & Linearization Controller ig current Controller idiff current v * v,abc v * dif f,abc m * u,abc m * l,abc i * gdq i * dif f,abc i * gd i * gq ÷ ÷ vgd vgd W Σ * abc Energy (14) (12) (13) igdq idiff,abc W Σ abc Figure 2: General Control Scheme of MMC

B. Current control and Energy control

For the 3-phase MMC, as well as a classical VSC, the control of i g is achieved in rotating frame by applying Park transformation. Phase Lock Loop (PLL) is implemented to track the grid voltage angle. The implemented PI controller is denoted as C ig . Applying Park transformation on ( 6), the i g control in dq frame is derived

v * v d = v g d + (i * g d -i g d )C ig - L arm 2 + L f ωi gq (12a) v * vq = v gq+ (i * gq -i gq )C ig + L arm 2 + L f ωi g d . (12b)
The differential current in each phase is regulated by another PI controller C idif f . From (9), the i dif f control for phase j is derived as:

v * dif fj = V dc 2 -(i * dif fj -i dif fj )C i dif f . (13)
The difference between the DC power inflow and the AC outflow causes variation of the energy stored inside the MMC. Since it is preferred that the AC power follows the reference value, it is reasonable to adjust the DC power to obtain the desired internal energy level. A PI controller C W Σ is implemented to give appropriate i * dif fj to the differential current controllers. The control of W Σ is obtained as:

i * dif fj = 1 V dc W Σ * j -W Σ j C W Σ + P ac 3 (14)
where

W Σ i = 1 2 C tot v 2 Ctotui + v 2 Ctotli . (15)
Assembling the derived control laws, general control structure is built as shown in Fig. 2.

The developed controller is implemented in a simulation of an MMC station model. The pre-contingency operating power is set at P ac = 1[p.u.] and Q ac = 0[p.u.]. Then step reference changes are created at t = 1[s] for the active power and 1.1[s] for the reactive power. Fig. 3 shows the transition of the active and reactive powers. It is clearly seen that the both powers follow the change of the reference correctly. Fig. 4 pictures the capacitor voltage in each arm. Even though the capacitor voltages were perfectly balanced beforehand, each time the disturbance occurs, the voltages in the upper arms deviate from the lower ones. This is because the aforementioned energy controller can only regulate the sum of the upper and lower arms' energy, but it does not take into account the distribution of the energy between the upper and lower arms. Without explicit control, the energy in the upper and lower arms may take various levels and endanger the secure operation of the MMC. Therefore, an additional controller which enables to explicitly eliminate the deviation of the energy between the arms is needed.

III. ENERGY DIFFERENCE CONTROL

Theoretically, the power exchanged by the arm can be expressed by the product of the applied voltage v ulj and the current flows through the arms i ulj . Defining the energy difference by

W ∆ j = 1 2 C tot v 2 Ctotuj -v 2 Ctotlj , (16)
The evolution of the energy difference can be expressed by using the variables defined in the previous section:

dW ∆ j dt = i uj v uj -i lj v lj = i gj v dif fj -2i dif fj v vj . (17)
In normal operation, i gj and v vj are sinusoidal with an average of zero, while i dif fj and v dif fj are constant. In such condition, both terms in the right side of (17) are products of a constant value and a fundamental-frequency component. Thus, the time average over the period is zero. This means that, as it is, the energy difference is uncontrollable. One possible solution is to impose fundamental-frequency components on the differential current

(i dif f = i dif fac + i dif f dc ) [2]
. This decomposition allows to generate a non-zero component over the period on the right side of (17), which can be used to regulate the energy difference. Further simplification is done by supposing that v vj is fairly close to the AC grid voltage v gi since an MMC does not require large filters at its AC side. Introducing the decomposition of differential current into (17), then the time average of the evolution of the energy difference over one period is expressed by:

dW ∆ j dt = -2i dif fac j v gj . (18)
From (18), three control laws will be considered. One is the classical control scheme [START_REF] Delarue | Energetic macroscopic representation and inversion based control of a modular multilevel converter[END_REF]. The second one is developed based on the classical scheme, but the reference generation methods are improved to overcome the problem of the classical scheme. The proposed control is further improved by applying the phase shifting technique proposed by [START_REF] Munch | Integrated current control, energy control and energy balancing of modular multilevel converters[END_REF]. Each scheme is detailed in the followings.

A. Classical W ∆ control

The value of the energy difference can vary for each phase. Therefore, it is reasonable to regulated them individually by implementing one controller for each phase leg. Then the appropriate rms value of the AC components of the differential current I * dif fac can be derived by a PI controller denoted by C W ∆ . The control law can be expressed as:

I * dif fac j = - 1 2V g W ∆ * j -W ∆ j C W ∆ . ( 19
)
where V g is the rms value of the AC grid voltage. Next, the fundamental-frequency differential current reference must be generated in some way. The AC voltage angle (i.e. θ = ωt) is monitored by the PLL and used to align the current reference with the voltage in each arm. In the classical energy difference control, the instantaneous differential current reference

i * dif fac = i * dif fac a i * dif fac b i * dif fac c T is generated by i * dif fac = AI * dif fac (20)
where

A = √ 2   cos ωt 0 0 0 cos ωt -2π 3 0 0 0 cos ωt -2π 3   (21)
and

I * dif fac = I * dif fac a I * dif fac b I * dif fac c T
. The multiplication with the matrix A allows aligning the output of the controller with the AC grid voltage. Fig. 5 illustrates an example of the relation between the generated current references and the AC grid voltages.

According to (19) and (20), the classic energy difference controller is developed as depicted in Fig. 6. The developed controller is tested in the same simulation set up as previous section. The equivalent arm capacitor voltages are depicted in Fig. 7. Unlike the previous case, the capacitor voltage is well balanced after a short time. However, unwanted oscillations on the DC power are observed in Fig. 8. In this control structure, the energy difference is individually regulated per leg. Since there is no coupling between the phases, the balance dif fac may possibly be generated by the controller, and it results in inducing oscillations on the DC power. Such oscillations may cause fluctuations on the DC voltage and jeopardize the stability of the entire system, especially in small MTDC grids. Therefore, this must be avoided.

B. W ∆ Control with Balanced i dif fac

The classical W ∆ controller presented in Section III-A may generate unbalanced three-phase current references since the W ∆ of each phase is regulated individually. In other words, the current sum i * dif fac a + i * dif fac b + i * dif fac c may be non-zero, which would change the current exchanged with the DC grid. Thus, a new transform is needed so that the new current reference vector, denoted by i * dif fac , with The general principle is that to balance the current reference, for each component of i * dif fac , two new current references are introduced, one for each of the other two phases. Formally, let

i * dif fac = i * dif fac a i * dif fac b i * dif fac c T will have no impact on the external current, i.e. i * dif fac a + i * dif fac b + i * dif fac c = 0. v Ctotlc v Ctotuc v Ctotlb v Ctotub v Ctotla v Ctotua Time [s]
i * dif fac = Ki * dif fac =   k aa k ab k ac k ba k bb k bc k ca k cb k cc   i * dif fac ( 22
)
where coefficient k mn quantifies the contribution of the original reference i * dif fac n to the new reference i * dif fac m . This transform should satisfy the following 3 requirements, where we only consider phase a for simplicity:

1) It should not modify the contribution of the original reference to the corresponding phase in the new reference. This yields:

k aa = 1
2) The new reference should be balanced. This yields:

k aa + k ba + k ca = 0
3) The absolute values of the two new references in phases b and c should be identical. This yields

|k ba | = |k ca |
The above 3 requirements allow one to obtain:

K =    1 -1 2 -1 2 -1 2 1 -1 2 -1 2 -1 2 1    (23)
where we used the symmetry between the three phases. (and thus v ga ), which makes it possible to use a constant matrix K to calculate the new reference vector i * dif fac from the original one i * dif fac . Obviously, the choice of i * dif fac ba and i * dif fac ca is not unique. As long as their sum is equal to -i * dif fac a , the new current reference vector is already balanced, although the contributions by phase b and c are no longer bound to be equal. Furthermore, if the constraint on the phase shift of i * dif fac ba and i * dif fac ca with respect to i * dif fac a is relaxed, i.e. i * dif fac ba and i * dif fac ca are allowed to have other directions than i * dif fac a , then more freedom is permitted in their choice, as long as their vector sum equal to -i * dif fac a to guarantee current balance in the three phases. However, in that case, it is no longer possible to use a constant matrix to calculate i * dif fac from i * dif fac as in (22). Instead, a time-varying matrix, denoted by M , is needed to calculate i * dif fac from I * dif fac , i.e.

i * dif fac = M I * dif fac (24)
An example of choosing M is given in [START_REF] Munch | Integrated current control, energy control and energy balancing of modular multilevel converters[END_REF]. Its objective is to remove power exchanges imposed by the newly introduced current used for balancing, and its general principle is to shift the current vectors by 90 degrees from the corresponding voltage angle. Taking phase a as example, let where φ m is the phase shift between i * dif fac ma and the voltage in phase m, and l aa , l ba and l ca are positive1 constant coefficients.

i * dif fac aa (t) = l aa √ 2I * dif fac a cos (ωt + φ a ) (25) i * dif fac ba (t) = l ba √ 2I * dif fac a cos ωt + φ b -2π 3 (26) i * dif fac ca (t) = l ca √ 2I * dif fac a cos ωt + φ c + 2π 3 (27)
To determine the value of l ma and φ m , the following requirements are used.

1) The contribution of the original reference to the corresponding phase in the new reference should not be modified. This yields:

l aa = 1, φ a = 0.
2) The new reference should be balanced. This yields:

l aa cos (ωt + φ a ) + l ba cos ωt + φ b -2π 3 +l ca cos ωt + φ c + 2π 3 = 0
3) The instantaneous active powers due to i * dif fac ba and i * dif fac ca in phases b and c are zero. This yields:

l ba V g I * dif fac a cos φ b = l ca V g I * dif fac a cos φ c = 0
4) The absolute values of the two new references in phases b and c should be identical. This yields

l ba = l ca
The above four requirements allow one to obtain

l aa = 1, l ba = l ca = 1 √ 3 , φ a = 0 φ b = - π 2 , φ c = π 2 .
(28) By symmetry between the three phases, M can be obtained as

M = √ 2    cos ωt 1 √ 3 cos ωt + π 2 1 √ 3 cos ωt -π 2 1 √ 3 cos ωt -7π 6 cos ωt -2π 3 1 √ 3 cos ωt -π 6 1 √ 3 cos ωt + 7π

D. Simulation results

The two developed control structures are applied to the simulation of an MMC model. The same events as Section II are tested with the Modified Balanced W ∆ Control (Case1) and Balanced i dif fac (Case2). Fig. 13 shows the responses to the step change of the active and reactive power references. Unlike the case with the classic control (Fig. 8), no oscillation is observed on the DC power for both cases as expected. Fig. 14 shows the dynamics of the energy difference during the events. As it is observed, the energy difference is correctly regulated and converged to the reference value of zero after a short time. The Case2 takes slightly longer time due to the interactions from the other phases, which exert a modification from the expected active power exchange. In Fig. 15, the differential currents are depicted. For both cases, fundamentalfrequency components are observed. Nonetheless, they have no impact on the DC power. This proves the effectiveness of the proposed control structures which enable to regulate the energy difference without having any interaction with DC side and allows to treat them internally.

IV. CONCLUSION

In this paper, control strategies of energy difference of the MMC have been analyzed. While maintaining the cascaded control structure, two structures of energy difference controllers have been presented. The proposed controllers allow regulating the energy difference by generating balanced differential current references. Simulation results have shown the effectiveness of the proposed controllers which enable to regulate the energy difference without having any interaction with the DC and AC grid. This implies that the regulation of the energy difference is treated as internal dynamics and can

Figure 1 :

 1 Figure 1: MMC Arm average model

Figure 4 :

 4 Figure 4: Equivalent arm capacitor voltages [pu]

Figure 5 :Figure 6 :

 56 Figure 5: Vectorial representation of differential currents in Classical Control

Figure 7 :

 7 Figure 7: Equivalent arm capacitor voltages [pu] -Classical W ∆ control

Figure 8 :

 8 Figure 8: Active power and DC power [pu] -Classical W ∆ control

Fig. 9 Figure 9 :

 99 Figure 9: Vectorial representation of differential currents in W ∆ Control with Balanced i dif fac

Figure 11 :

 11 Figure 11: Vectorial representation of differential currents in Modified W ∆ Control with Balanced i dif fac

  illustrates the generated current reference by the coupling matrix M with phase a as example. The vectors i * dif fac ba and i * dif fac ca satisfy the above four requirements. According to (24) with M given in (29), the control structure is developed as illustrated in Fig.12.

Figure 12 : 2 QFigure 13 :

 12213 Figure 12: Modified W ∆ Controller with Balanced i dif fac

Figure 14 :Figure 15 :

 1415 Figure 14: W ∆ comparison (filtered) [pu] -1: Modified Balanced W ∆ , 2: Balanced W ∆

This can always be achieved by properly choosing φm.


Arjun Suresh
email: suresh.86@osu.edu

Erven Rohou

André Seznec

Compile-Time Function Memoization

Keywords: D.4.3 [Programming Languages]: Processors-Compilers, D.4.3 [Programming Languages]: Processors-Optimization, B.3 [Hardware]: Memory Structures compilation, optimization, memoization, performance, instruction set extension

Memoization is the technique of saving the results of computations so that future executions can be omitted when the same inputs repeat. Recent work showed that memoization can be applied to dynamically linked pure functions using a load-time technique and results were encouraging for the demonstrated transcendental functions. A restriction of the proposed framework was that memoization was restricted only to dynamically linked functions and the functions must be determined beforehand. In this work, we propose function memoization using a compile-time technique thus extending the scope of memoization to user defined functions as well as making it transparently applicable to any dynamically linked functions. Our compile-time technique allows static linking of memoization code and this increases the benefit due to memoization by leveraging the inlining capability for the memoization wrapper. Our compile-time analysis can also handle functions with pointer parameters, and we handle constants more efficiently. Instruction set support can also be considered, and we propose associated hardware leading to additional performance gain.

Introduction

Memoization -saving the results of a sequence of code execution for future reuse -is a time-old technique to improve the run time of programs. Over the years, memoization has been proposed at various levels of implementation ranging from function level in software to instruction level in hardware. Function memoization -where the granularity of memoization is a function -aims at limiting repeated function executions, thereby saving CPU cycles. As with other memoization schemes, there is a trade-off between saved CPU cycles and increased data storage. Overheads come from storing function results in a table, and looking-up the table at the next invocation. The challenge with memoization is to minimize these overheads and gain maximum performance. The smaller the amount of code being saved by memoization, even smaller must be the overhead. This implies a very fast lookup mechanism and a table usage which should not hamper the normal execution of the program. Further, identifying the functions for memoization and applying a suitable memoization technique is also important.

Though function memoization have been proposed long back, there was no pure software approach with performance benefit, until recent work by Suresh et al. [START_REF] Suresh | Intercepting functions for memoization: A case study using transcendental functions[END_REF] where dynamically linked functions were targeted for memoization and performance benefit was demonstrated for a variety of transcendental functions. Their main advantage is that they intercept functions at load-time and they provide a way for memoizing dynamically linked functions without the need of source code and recompilation. However, their technique is restricted to dynamically linked functions, and the target functions must be determined beforehand.

We found that most of the pure function codes are either transcendental functions or are inlined by the compiler due to very small size (like expressions used for indexing arrays). Still, pure and expensive functions are present in case of recursions and applications which are critical to numerical computation (cases where a closed form solution is not available). Also there are cases of function usage with pointers and the pointed value can be used for memoization. Further, by capturing constants at call site, we can optimize and handle more functions (by reducing arguments for memoization) for memoization. Thus we propose a compile-time memoization technique which can handle all these cases. We also propose a hardware model for our memoization scheme which can increase the potential benefit of memoization.

The remaining part of the paper is organized as follows: Section 2 first reviews related work. We then present the advantages of our compile-time approach in Section 3. Section 4 then describes our implementation, how we identify potential candidates for memoization and the involved challenges. Section 5 details the experimental setup used and the results of our memoization technique. Section 6 details our hardware proposal for memoization and estimates the additional performance gain. Section 7 concludes.

Related Work

Memoization has been implemented at various levels of execution: instruction level, block level, trace level and function level, using both hardware and software techniques. At functional level the term "memo function" was coined by Donald Michie [START_REF] Michie | Memo functions and machine learning[END_REF] in 1968.

At instruction level Richardson [START_REF] Richardson | Caching function results: Faster arithmetic by avoiding unnecessary computation[END_REF] dealt with trivial and redundant computations. Citron et al. [START_REF] Daniel Citron | Accelerating multimedia processing by implementing memoing in multiplication and division units[END_REF] propose a hardware-based technique that enables multi-cycle computation in a single-cycle.

In a follow up paper on memoization, Citron et al. [START_REF] Citron | Hardware memoization of mathematical and trigonometric functions[END_REF] showed the scope of memoizing trigonometric functions (sin, cos, log, exp . . . ) on general purpose or application specific floating-point processors. To enable memoization for user written function they propose two new instructions -to lookup and update a generic MEMO TA-BLE. By doing such a hardware implementation they achieved a computation speedup greater than 10 %. They also compared the same using a software mechanism which could not yield a speed up but gave a slowdown of 7 %.

González et al. [START_REF] González | Trace-level reuse[END_REF] explore hardware techniques for tracelevel reuse. In instruction-level memoization a single instruction is reused while in trace-level memoization a dynamic sequence of instructions are reused. At block level Huang et al. [START_REF] Huang | Exploiting basic block value locality with block reuse[END_REF] investigate the input and output values of basic blocks and find that these values can be quite regular and predictable, suggesting that using compiler support to extend value prediction and reuse to a coarser granularity may have substantial performance benefits.

Memoization has been used in programming languages such as Haskell 1 and Perl 2 . The presence of closure [START_REF] Reddy | Objects as closures: Abstract semantics of objectoriented languages[END_REF] in functional programming languages like Lisp, Javascript etc. give a ready-touse mechanism for the programmer to write the memoization code. [START_REF] Mcnamee | Developing a tool for memoizing functions in C++[END_REF] propose automatic memoization at source level in C++.

McNamee and Hall

When memoization is used in procedural languages, special techniques are needed to handle procedures with side effects. Rito et al. [START_REF] Rito | Memoization of methods using software transactional memory to track internal state dependencies[END_REF] used Software Transactional Memory (STM) for function memoization, including impure functions. Their scheme provides a memoization framework for object oriented languages which are traditionally difficult for memoization as the outcome of a method often depends not only on the arguments supplied to the method but also on the internal state of objects. Tuck et al. [START_REF] Tuck | Softsig: Software-exposed hardware signatures for code analysis and optimization[END_REF] used softwareexposed hardware signatures 3 to memoize functions with implicit arguments (such as a variable that the function reads from memory). An extension of simple memoization is used by Alvarez et al. [START_REF] Alvarez | Fuzzy memoization for floatingpoint multimedia applications[END_REF] in their work on fuzzy memoization of floating point operations.

Here, multimedia applications which can tolerate some changes in output are considered and memoization is applied for similar inputs instead of strictly identical (several inputs produce the same result). A similar technique is also used by Esmaeilzadeh et al. [START_REF] Esmaeilzadeh | Neural acceleration for general-purpose approximate programs[END_REF] in their work about neural accelerators to accelerate programs using the approximation technique. The basic idea is to offload code regions (marked as approximatable by the programmer) to a low power neural processor. Since approximation enhances the scope of memoization, the technique gave them very good results.

Memoization is also used in graphical domains and in a recent work, [START_REF] Arnau | Eliminating redundant fragment shader executions on a mobile GPU via hardware memoization[END_REF] Arnau et al. proposed a hardware scheme in GPUs for saving redundant computations across successive rendering of frames. Long et al. [START_REF] Long | Minimal multi-threading: Finding and removing redundant instructions in multi-threaded processors[END_REF] propose a multi-threading microarchitecture, Minimal Multi-Threading (MMT), that leverages register renaming and the instruction window to combine the fetch and execution of identical instructions between threads in SIMD applications. The main idea in MMT is to fetch instructions from different threads together and only splitting them if the computation is unique.

In this work, we propose function memoization at software level which can be applied across different languages using a compiletime approach. Our framework uses large memoization tables to 1 http://www.haskell.org/haskellwiki/Memoization 2 http://perldoc.perl.org/Memoize.html 3 a signature is a hardware register that can represent a set of addresses capture longer intervals of repetition that benefit computationally intensive pure functions at the software level without programmer intervention and we evaluate the benefit on current architecture. Our experimental results show that software memoization is capable of producing speed-up in current architectures over current compiler techniques. We also propose a hardware scheme for additional performance gain of our memoization approach.

The most closely linked work to ours is the work by Suresh et al. [START_REF] Suresh | Intercepting functions for memoization: A case study using transcendental functions[END_REF] where memoization is shown to be working effectively for dynamically linked math functions. We outline the major difference as follows:

1. our technique applies to any function: part of the executable or from a dynamically linked library;

2. memoized function are identified automatically, without the need to manually predetermine them;

3. memoization code is combined with the source code, and hence usually inlined by the compiler resulting in significant speedups;

4. we handle global variables, pointers and constants;

5. we propose hardware scheme for additional improvement of the memoization benefit.

Compile-Time Memoization

Doing memoization at compile-time enables both user written as well as library functions to be memoized. It also provides a way to handle some impure functions such as those which read/update global variables, have pointer arguments etc. Also, constants can be identified at call sites and possibly optimized out. Inlining the memoization wrapper is another advantage given by enabling memoization at compile-time. Though small pure functions in user code are usually inlined by the compiler, there are cases like recursion with large/unknown depth, dynamic linking, different object modules without inter-procedural optimization etc. where inlining fails.

To leverage inlining for memoization, we provide a small inline wrapper for memoization that performs the table lookup and resorts to a function call only in case of a miss. This increases the effect of memoization and lowers the threshold needed for memoizing a function. As an example, a call to function float pure_foo( float arg) is replaced by a call to the following wrapper, potentially inlined. In addition to providing compiler optimizations, inlining also saves a function call whenever there is a hit in the table. In order to measure the performance impact of saving this call we put a dummy call to a dynamically linked function in a custom code having 100 million function calls. The run time of the inlined memoization code made a time difference of 400 ms which would mean 400.10 -3 100.10 6 = 4 ns on average for a single call. We ran our experiment on a CPU running at 2.3 GHz and hence the run time amounts to 4 × 2.3 ≈ 9, which means that approximately 9 clock cycles are saved on average for a single call. So, even without considering possible compiler optimizations on the wrapper code, we expect to 1), where tmo is the miss overhead, T f the original execution time, and t h the hit time. Figure 1 shows how inlining the wrapper increases the applicability of memoization, in particular for short function (say, under 100 ns). In particular, when the load-time approach reaches its limit (100 % repetition required to have a benefit), inlining lowers the requirement to 75 %, a more feasible threshold.

H > tmo T f + tmo -t h (1)
In our work, we aim to provide memoization capability to a code using a compile-time technique. During compilation stage we should identify which functions are potential candidates for memoization and then provide memoization capability for them which is done by adding a memoization wrapper for them. The memoization wrapper must have inlining capability in order to get the potential benefit of avoiding a dynamic function call during a hit in the memoization table. Impurities for function memoization in the form of global variable usage, pointer arguments are also to be handled.

Implementation

We implemented our technique in the LLVM compiler [START_REF] Lattner | LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation[END_REF]. To support Fortran applications, we relied on the dragonegg GCC plugin. It uses the GCC front-end to parse the source code, but replaces optimizers and code generators by those of LLVM. We developed an LLVM optimizer pass at module level since we are analyzing all functions in a module and possibly modifying them. This pass iterates through each function and marks them if they are memoizable. If so, we create a template for memoization wrapper and replace each call site of the function, with a call to the corresponding memoization wrapper. The prototype of the wrapper memoization function is same as that of the original function except the name being prefixed with __memoized_ and parameter order possibly being changed under the condition detailed in Section 4.1. The pseudocode for our approach is given in Algorithm 1.

We considered functions with up to three parameters as the chance of repetition goes down and the overhead increases when the number of parameters increases. Constant arguments at call sites do not count towards this limit as per the algorithm detailed in Algorithm 6.

Function Templates and Parameter Ordering

To avoid a combinatorial explosion of the number of function types to be handled, we sort the parameters by type and our function prototype is generated as per this new order. We generate the call string for the original function during this stage itself and hence it preserves the actual call order. This is exemplified as follows.

Let the original function prototype be: Now, after sorting, suppose their order becomes arg2, arg3, arg1. Our generated prototype for function foo will be:

1 _memoized_foo(int arg1, float arg2, int* arg3)
which, in turn, calls:

1 foo(arg2, arg3, arg1);
i.e., the call string is generated based on the relative ordering of the parameters before sorting and there is no impact on the parameters of the actual function. Algorithm 6 details this mechanism.

Handling Pointers

Pointers introduce a complication for memoization. A pointer can be used to read memory (READ case), but the value stored at that location can change from one call to another. A pointer can also be used to write memory (WRITE case), essentially producing a return value. In either case, we are interested in the pointed-to value, not the address. So, we have taken a conservative approach and handle only one READ Only or READ/WRITE pointer while allowing up to

Read/Write pointers

READ/WRITE pointers are the most difficult to handle. They require both storage space and also cause extra lookup overhead, also reducing the chances of repetition.

Global Variables

Global variable usage can make an otherwise pure function impure because they can change across function invocation and thus affect the result of the function call (when it is used in function computation). Global variables can also be used to store a state of the program by the function. We handle global variable like a normal argument -in our memoized wrapper we add one extra argument for each global variable in use in the function. Global variables have pointer type in LLVM and hence our technique for handling pointers is re-used. We have considered a maximum of one global variable use and correspondingly only one extra parameter in the memoized wrapper. Global variables are not considered while generating the call string and hence this has no effect in the call to the original function. The algorithm for detecting global variables is given in Algorithm 5 and the procedure for adding it in the memoized wrapper function is given in Algorithm 6.

Constants

There are cases where one or more parameters to a function call might be constants. In such cases, it is unnecessary to consider these as regular parameters since, by definition, they are guaranteed to repeat and hence no need to be saved in the memoized table. Further, we can avoid passing these constants to the actual call, as long as there is a hit in the memoization table. This is made possible by passing the constants directly to the call string and omitting them from the memoization wrapper. The disadvantage of this approach is that the memoization wrapper becomes call site specific (a separate memoization table is needed per constant, though different call sites using the same constant use the same table) but our results show that this is not a problem. Refer to Section 5.3.2 for an example in the histo benchmark.

Memoization Table and Indexing

For comparison purposes, we use the same memoization table implementation as Suresh et al. [START_REF] Suresh | Intercepting functions for memoization: A case study using transcendental functions[END_REF] where a direct mapped table is being used, indexed using XOR operator on the arguments (repeated folding of argument bits to get the required number of bits for index) and tagged using the arguments.

Experimental Results

System Configuration

We carry out our experiments on an Intel Core i7 Ivy Bridge clocked at 2.3 GHz, equipped with 8 GB of RAM and 8 MB of L3 cache, and running Linux 3.19. Benchmarks are compiled at the -O3 optimization level. We use LLVM version 3.19. We made sure that Turbo Boost is turned off and CPU clock frequency was set at 2.3 GHz to ensure reproducible measurements. For our experiments we have used a 64 k-entry memoization table per function. This size is empirically determined to be the best on our experimental machine.

Benchmarks

Based on our criteria for memoization -pure critical functions, we selected a variety of applications both from real life as well as standard benchmark suites that extensively call transcendental functions. Applications with no, or few calls to these functions are not impacted (neither speedup nor slowdown), they are not reported here. Our experimental benchmark applications include: SPEC CPU 2006. We chose five benchmarks: bwaves, povray, GemsFDTD, tonto and wrf from SPEC CPU 2006 suite [START_REF] Henning | SPEC CPU2006 benchmark descriptions[END_REF] with ref inputs, which have a reasonable number of calls to transcendental functions. wrf and bwaves extensively use powf and pow functions respectively. tonto makes extensive use of exp and sincos calls, while povray has many calls to sin and cos.

SPEC OMP 2001 [START_REF] Aslot | SPEComp: A new benchmark suite for measuring parallel computer performance[END_REF]. Two applications match the criteria for memoizationgafort and equake. gafort has calls to sin in its critical region and equake has both sin as well as cos calls in its critical region.

ATMI [START_REF] Michaud | A study of thread migration in temperatureconstrained multicores[END_REF] is a C library for modeling steady-state and timevarying temperature in microprocessors. It is provided with a set of examples and all of them have a large number of calls to Bessel functions j0 and j1.

Population Dynamics [START_REF] Ciss | A spatiotemporal model for predicting grain aphid population dynamics and optimizing insecticide sprays at the scale of continental France[END_REF] is a model of aphid population dynamics at the scale of a whole country. It is based on convection-diffusion-reaction equations. The reaction function makes heavy use of exp and log and uses armadillo library.

Barsky [START_REF] Barsky | This is a program to solve nonlinear 2-D PDE using one-step linearization[END_REF] is a partial differential equation solver, it contains many calls to sin.

Splash2x. water_spatial [START_REF] Parsec Group | A memo on exploration of SPLASH-2 input sets[END_REF] of Parsec benchmark suite [START_REF] Bienia | The PARSEC benchmark suite: Characterization and architectural implications[END_REF] can benefit from memoization as it makes extensive use of exp and sqrt functions.

blacksholes [START_REF] Bienia | The parsec benchmark suite: Characterization and architectural implications[END_REF] is also taken from Parsec [START_REF] Bienia | The PARSEC benchmark suite: Characterization and architectural implications[END_REF] benchmark suite. This involves option pricing with Black-Scholes partial differential equation. Black-Scholes equation does not have a closed form solution and hence must be computed numerically.

histo is a histogram application taken from Parboil benchmark suite [START_REF] Stratton | Parboil: A revised benchmark suite for scientific and commercial throughput computing[END_REF] which accumulates the number of occurrences of each output value in the input set.

Discussion of Results

The result of memoization on the selected benchmark applications is shown in Table 1. We also reproduced the load-time approach [START_REF] Suresh | Intercepting functions for memoization: A case study using transcendental functions[END_REF] for comparison purposes. We obtained access to their code to guarantee fairness of comparison. The speedups are shown in Figures 4 and5.

First of all, thanks to the inlining of the wrapper, more (math) library functions benefit from memoization, compared to the plain load-time approach.

Compile-time memoization delivers much better speedup compared to the load-time approach. A major part of this is coming from the memoization wrapper getting inlined, thus providing more optimization opportunities. This cannot be achieved by the dynamically linker.

We are also able to catch more memoization opportunities as marked by boxed functions in Table 1. Note that histo and blackscholes do not benefit from load-time memoization (speedup 1.0). The case of equake is detailed below in Section 5.3.1.

In equake we capture phi0, phi1 and phi2 functions where a global variable is being used. With our scheme, we capture them as extra argument and hence these functions are getting memoized. In histo, HSVtoRGB is a user function taking in three arguments of type float and returning a structure to three variables of type char, as shown below. But this is converted to an int return type by LLVM as per the x64 Linux ABI [START_REF] Fox | Calling conventions[END_REF] and in the call site we avoid the constants and replace the call ignoring the constants to the memoization wrapper. Now in the call to the original function inside our memoization wrapper we include these constants as arguments.

equake

In equake, we have three critical user defined functions -phi0, phi1 and phi2 -all of which have similar code structures. The code of phi0 is given below: The second argument is used for passing the global variable, and global variables have pointer type in LLVM IR. Now, this function provides a challenging case for memoization. There is just an if-then-else block inside the function with the then block being expensive and the else block being very simple (just a return statement). During execution, we found that the else block has taken 90 % of the total time -284 million calls to then block compared to a total number of calls of 3.7 billion -and hence memoization is getting a benefit of only 10 % of the time, causing slight overhead during every execution of else case. So, this causes the speedup to come down. In order to avoid this, we tried applying memoization only for the then part of the function, resulting in a performance gain of 3.5 % over the normal compile-time approach, showing a further enhancement which could be applied for our approach.

The phi functions could not be memoized by the load-time approach, but the sin could. This explains why load-time produces a speedup.

histo

In histo, we have a call to HSVtoRGB: The first two arguments are constants, hence removed. We modify the call site to __memoized_HSVtoRGB_0_1(double) keeping a single argument:

1 __memoized_HSVtoRGB_0_1(cbrt(1+ 2
63.0 * ((float)value)/((float)UINT8_MAX))/4);

and we call HSVtoRGB from inside __memoized_HSVtoRGB_0_1 as follows:

1 HSVtoRGB(0.0, 1.0, arg1) thus we have saved the passing of first two parameters and avoided their use in indexing the memoization table.

blackscholes

In blackscholes, the function CNDF (Cumulative Normal Distribution Function) performs numerical computation on an input floating point data and is expensive as well as critical. The function is using a macro defined type to handle both double as well as float types as per definition during compile-time. Our experiments were run using double type. The code involves numerous floatingpoint computations in addition to a call to exp function making it expensive.

wrf

In wrf we observe a performance loss due to a low repetition rate for powf. The performance achieved by Suresh et al. is reported to be caused by a performance bug in the libm implementation of powf. This bug is partially fixed in the version of libm we used for our current experiments. We discuss in Section 5.4 a turn-off mechanism to disable memoization in case of slowdowns.

water_spatial

Our compile-time approach produces a significant speedup of 8 % in water_spatial. This is however less than the load-time approach. On a machine with a larger instruction cache size (64 KB vs 32 KB for our experimental machine), compile-time is slightly better than load-time, as for other benchmarks. We hence attribute the slowdown to an increase in miss rate for L1 instruction cache caused by inlining which increases the code size from 36 KB to 38 KB.

Transcendental Functions

For transcendental functions in all other applications, we obtain better performance than the load-time approach, (shown in Figures 4 and5). This increase in speedup comes from saving a call in case Table 1. Memoization results. Boxed names indicate functions that cannot be caught by a load-time technique. The first two columns report benchmarks names and memoizable functions. For each function, we report the number of calls. The following two columns report the total execution time, and fraction of the time spent in the memoizable functions. The last three groups report results. First, we reproduce Suresh et al.'s results with a load-time approach. We then cover the pure compile-time approach, reporting the percentage of lookup hits per function and the overall speedup. Finally, we describe the results of the hardware-assisted memoization, showing percentage of hits in the hardware table, misprediction rates, and overall speedup. of hit in the lookup table (Section 3) as well as potential further compiler optimization after inlining.

Turning off Memoization

With a load-time scheme, turning off memoization amount to overwriting the address of a function in the process' GOT (global offset table). In our compile-time scheme, the wrapper is inlined in the caller and its code is likely to be optimized by the compiler and mixed up with the surrounding code, making it impossible to disable in a simple manner. Instead, we can keep an original (i.e. without memoization) version of the caller of the memoized function, and substitute versions at run-time whenever memoization proves to be counterproductive. As in the load-time case, the monitoring is performed by a lightweight helper thread that periodically checks statistics and makes decisions based on repetition rates and execution times. Substituting code at the granularity of a function is easily accomplished by dynamic binary optimizers, such as Dy-namoRIO [START_REF] Bala | Dynamo: a transparent dynamic optimization system[END_REF] or Padrone [START_REF] Riou | PADRONE: a Platform for Online Profiling, Analysis, and Optimization[END_REF]. To avoid the impact on code size, the backup versions can be stored in a special section of the ELF file, possibly compressed, to be retrieved only as needed.

Memory Overhead

In our experiments, we used a 64 k-entry table size for each function. This requires 64 tag bits and 64 data bits for a function taking a double argument and returning a double. It amounts to 128 × 64k = 8 Mbits = 1 MB memory per function. For functions taking two double arguments, we need 1.5 MB. And for 32-bit arguments (i.e. int or float) this corresponds to 512 KB and 768 KB respectively.

Note that these tables are one-time allocated and initialized, but they cause contention in the memory hierarchy only when their content is actively used (hence useful). The initial overhead consists . As shown in the results, there are a few tables per benchmark.

In addition to memory overhead for the memoization table, inlining can also cause an increase in code size. Figure 3 shows the percentage change in the code size (text segment) due to memoization on our selected applications. The variabtion really depends on the number of memoized call sites in a function and the size of the function. Note that inlining is a decision taken by LLVM based on its standard heuristics. We have not tried to change them.

Direct Hardware Memoization

This section evaluates a proposition to implement memoization directly through the hardware. Such a hardware implementation requires some ISA modification described in Section 6.1 and the use of an extra hardware table described in Section 6.3. Hardware can enable very fast hit/miss time, hence improving the profitability of memoization.

The software implementation evaluated in the previous sections necessitates to compute hash function, then to read the table stored in the global memory and finally to check the tags. When the table read misses through the whole memory hierarchy, the total access time can reach hundred cycles. If dedicated hardware table is used for memoization then one can get fixed hit/miss time on the memoization table including hashing the index, effective table reads and tag check. Moreover using a set-associative hardware memoization table can be considered since this would only marginally increase the hit/miss time.

The compile-time approach developed in the previous sections is adapted to exploit this hardware memoization.

ISA Support for Hardware Memoization

Hardware memoization was discussed by Citron et al. [START_REF] Citron | Hardware memoization of mathematical and trigonometric functions[END_REF]. For hardware memoization of user defined functions they proposed two new instructions LUPM and UPDM which respectively does the memoization table lookup and memoization table update. Both instructions had two variants: one for single input functions and other for double input functions. We consider a very similar ISA support for hardware memoization that fits our compile-time approach. Our proposal has a new CALL instruction, specific to each function prototype supported by our compile-time approach.

We introduce the following two instructions.

MSCALL is used to call a memoized function. On such a call, the hardware memoization table is read using a hardwired hash function and on a success returns the value from the table. If the lookup fails, a normal CALL instruction is invoked to execute the original function. We assume different variants of MSCALL to handle the different possible function templates. For pointer arguments, we assume that they are WRITE Only since READ ONLY pointers can be converted to corresponding type using a LOAD instruction by the compiler. Similarly, READ/WRITE pointer arguments can be converted to two arguments: one being the data, and another WRITE Only pointer. Thus, we can restrict the required instruction variants as follows:

• 1 data argument, 1 return value;

• 2 data arguments, 1 return value;

• 1 data argument, 1 pointer argument, no return value;

• 1 data argument, 1 pointer argument, 1 return value;

• 1 data argument, 2 pointer arguments, no return value.

Moreover, to support multiple functions, the MSCALL instruction features an 8-bit function identifier.

MSUPDATE performs an update to the memoization table with the function result, therefore the compiler must allocate it immediately after MSCALL. In case of a hit of the MSCALL instruction in the memoization table, the MSUPDATE must be skipped to avoid a rewrite on the hardware memoization table. This is achieved by MSCALL incrementing the program counter.

MSCALL is tightly integrated with the branch predictor. At instruction fetch time, the hit/miss in the hardware memoization table is predicted so that the speculative execution engine is not impacted by our additions.

Benefit of Reduced Latency

For the sake of simplicity, in the remainder of the paper, we will assume that the overall lookup time t lo for hardware memoization table is 5 cycles approximately corresponding to 1 cycle hash computation, 3 cycles table read, and 1 cycle tag check and the branch misprediction penalty t bmp is 20 cycles. These values are consistent with current technology.

The overall execution cost of a call to a hardware memoized function depends on 1) hit/miss on the hardware memoization table, 2) correct/wrong branch prediction on the MSCALL instruction and 3) execution time of the normal call.

The average execution cost of a call to a memoized function is detailed in the following equation 2. Note that, if the memoization table misses and the branch prediction is correct, there is no significant execution overhead on a modern superscalar processor over the normal execution overhead. This explains why the term

(1 -H) is multiplied by t f , not t f + t lo . H × t lo + (1 -H) × t f + M pred × t bmp (2)
M pred is the misprediction ratio of the MSCALL branch.

A dynamic predictor built with a saturating counter (e.g. 4 bits) associated with each memoized function easily achieves a misprediction rate in the same range or lower than min(H, 1-H). Therefore, taking H (respectively 1-H) as a proxy for M pred when H < 0.5 (resp. H > 0.5), we can derive the condition when memoization is beneficial.

• if H < 0.5, we need t lo + t bmp < T f , i.e the average execution time of the function is higher than 25 cycles.

• if H > 0.5, we need

H×t lo +(1-H)×t bmp H < T f . As an example, if H=0.75, it is enough that T f > 12 cycles.
As a result, memoization of any function with average execution time over 25 cycles is potentially beneficial even if its hit rate on the hardware memoization table is marginal. In particular, all the functions considered in the previous sections fit in this category.

Hardware Memoization Table

In this paper, we assume a hardware memoization table with approximately the same size as the L1 data cache. This table can be set-associative to allow higher hit rate. A single table is shared by all memoized functions.

Individually each entry has a valid bit, a process identifier field (ASID) to support multi-process environments, a function identifier field of 8 bits, two input arguments of 64 bits and two possible results also of 64 bits.

In the evaluation, we use a 256 sets, 4-way associative (1024 entries) table, with pseudo LRU replacement. An entry corresponds to 2 8-byte results, 2 8-byte tags, one 8-bit function identifier, an ASID, a valid tag and a few tag bits for replacement. The total storage is around 32 KB, i.e., approximately on-par with the L1D cache.

Software Support

Function memoization necessitates software support. For our experiments, we use the same scheme as for software memoization. At link time, we no longer need to link to the memoized wrapper functions. Instead, the LLVM compiler generates the MSCALL instruction variant as per the required prototype. Further, the functions must now be numbered with its corresponding identifier which are generated sequentially starting from 0. This identifier is passed as the last parameter to the MSCALL instruction. If any function is having more than two input parameters, the compiler enables only software memoization as described previously.

Performance Evaluation

Due to the novel hardware, evaluating this proposal relies on models and simulation. We used the same set of benchmarks and the same experimental setup as in our compile-time technique. The methodology is the following.

We first instrument all memoized functions to obtain their execution times. This is achieved with Intel's RDTSCP instruction that returns the value of the time-stamp counter (monotonically incremented at each clock cycle). We subtract the time spent in memoized functions from the total execution time. We then estimate the execution time of these functions in the presence of hardware memoization, thanks to Equation 2. We obtain the hit rate (H) and misprediction (M pred ) through simulation of the lookup table and 4-bit branch predictor (Table 1). Adding this time to the previous intermediate result produces our estimate execution time. Speedups are reported in Table 1. Figures 4 and5 shows the comparative performance of hardware and software memoization approaches on our set of benchmarks.

As expected, substantial performance gains are encountered on most benchmarks, with up to 2.82× speedup for gafort, and 1.96× for populationdynamics. Both have perfect hit rates in their critical function, making efficient table lookup extremely effective.

The majority of benchmarks achieve speedups in the range 1.16× -1.48×. These figures derive from the combination of several factors. ATMI spends practically all its time in memoized functions, but achieves only modest hit rates. equake has both excellent coverage and hit rates, unfortunately the phi functions have short execution time, thus reducing the impact of memoization. In . Memoization speedups for selected applications the case of histo, only modest amount of time is spent in the user function HSVtoRGB, but the hit rate is perfect. We also benefit from two additional effects which explain the 1.48× speedup: two parameters are constant, hence optimized out by memoization, and the ABI convert the structure of char into an integer (see Section 5.3). bwaves, tonto, blackscholes, and water spatial combine fair amount of time spent in memoized functions and good hit rates, resulting in speedups in the upper range: 1.25× to 1.40×.

The least performing benchmarks, (speedups in the range 1.01× -1.07×) include barsky, gems.FDTD, povray and wrf. Barsky and gems.FDTD have excellent hit rate, but suffer from insufficient time spent in the memoized functions, in the order of 6 %. Conversely, wrf spends a significant amount of time in memoized functions, but has bad hit rate, and to some extent, poor misprediction rates. povray, impacted by both factors, has the worst speedup: 1.01× only.

Only bwaves experiences a smaller speedup than with the software memoization. This is due to the relatively small hardware table considered in the experiments resulting in a reduced hit rate, combined with a high misprediction rate.

Energy Consideration

A hardware memoization table is not useful for every application. To avoid static energy consumption on applications that do not use it, power gating the table can be considered.

Summary and Further Extensions

In this work, we have first proposed a compile-time approach for memoization as compared to [START_REF] Suresh | Intercepting functions for memoization: A case study using transcendental functions[END_REF] where a pure link time approach was proposed. Doing memoization at compile-time captures more candidate functions for memoization and enables memoization opportunity for user defined as well as library functions. With the help of LLVM framework we are able to support pointers and global variables for the functions to be memoized. Simple struct objects can also be handled as they are converted to int/double type and registers are used to pass them up to size 128 bytes as per x64 Linux ABI [START_REF] Fox | Calling conventions[END_REF]. Further we are able to optimize the function calls in case of constants being passed, by enabling function memoization per call site and passing constants directly to the original function call -constant parameters are avoided in the calls to memoized wrapper. The results of function memoization at compile-time is better compared to a load-time approach as shown in Figures 4 and5. By making a memoization wrapper at compile-time we provide inlining facility for the wrapper which improves the performance by saving the cost of a call as well as by enabling other compiler optimization. Inlining causes a slight increase in code size but still is good for performance. We used a 64k entry table for memoization but these entries are used only when indexing happens to them and hence in case of function being non-critical we would not be losing any performance.

As a second contribution, we showed that hardware memoization is also a valid approach. It necessitates minor additions in the ISA and further increases the scope and efficiency of memoization. This offers good benefit as it lowers the profitable minimum function execution time

Figure 1 .

 1 Figure 1. Profitability: load-time vs inlining

Algorithm 1

 1 LLVM Module Pass Require: Source Module Ensure: Function calls replaced by their memoized wrapper and produces function meta for memoization for each function f do if ISMEMOIZABLE(f) then MAKEMEMOIZEDFUNC(f); Copies the function prototype and create a new function (name starting with memoized _) prototype with empty body REPLACECALLSITE(f);Replaces all calls to original function with calls to new function (the function body will be available only during link time)

1

  HSVtoRGB(0.0, 1.0, 2 cbrt(1 + 63.0 * ((float)value)/((float)UINT8_MAX))/4);

Figure 3 .

 3 Figure 3. Code size change due to Memoization

Figure 4 .

 4 Figure 4. Memoization speedups for SPEC

  Identifying if function is safe for memoization Identifying if input function has safe arguments

	function CHECKFUNCTIONCALLS(f)
	for each instruction I in f do
	if ISCALLINSTRUCTION(I) then
	calledFunction, f ← GETCALLEDFUNCTION(I)
	if ISPURE(f) OR I = f then
	continue
	end if
	count++
	if count = 10 then
	We only check up to 10 levels of function calls as more than 10 levels of
	distinct pure function calls is highly unlikely
	return false
	end if
	if ISMEMOIZABLE(f) then
	continue
	end if
	return false
	end if
	end for
	end function
	Algorithm 4 continue
	end if
	return false
	end if
	end for
	end function
	function ISMEMOIZABLEPOINTER(P)
	for each use I of P do
	if I = LoadInstruction AND I = StoreInstruction then
	return false
	end if
	return true
	end for
	end function

1 void foo(float arg1, int* arg2, int arg3) Algorithm 3 function ISPROPERARGS(f) for each argument A of f do if ISPOINTERTYPE(A) then if ISMEMOIZABLEPOINTER(A) then

  Algorithm 5 Checking if function is Global Variable safe WRITE Only pointers. Also we only handle cases where the pointed value is of type int, float or double -arrays, structures and pointer to pointers are skipped and not considered for memoization.The READ/WRITE property of a parameter is analyzed by going through the use chain of the parameter and analyzing each instruction. If only STORE instructions use a parameter it is marked as WRITE Only. If no instruction with memory write capability uses a parameter, it is marked as READ Only. Otherwise, the parameter is marked as READ/WRITE.4.2.1 Read Only PointersREAD Only pointers are those which are used in a function but the pointed value is not modified. Hence, we handle them like a normal argument. The pointed value is used for indexing the memoization table and also as tag.4.2.2 Write Only PointersThese parameters are not used for indexing into the memoization table, but only for passing back the return value. They require storage space in the memoization table, but cause no direct overhead for indexing into the table. A typical case for this is the libm function sincos, where two WRITE Only pointers are used for returning simultaneously the sin and cos values for the input argument.

	two
	Require: Function F
	Ensure: If input function is safe from global variable usage for memoiza-
	tion
	function ISGLOBALSAFE(f)
	count ← 0
	global ← Null
	for each instruction I in f do
	for each operand O of I do
	if ISGLOBALVARIABLE(O) then	All global variables are
	pointers in LLVM
	ptype = GETTYPE(O)
	optype ← GETTYPE(ptype)
	if optype = Integer OR optype = float OR optype = Double
	then
	if global = Null then
	global ← O
	continue
	end if
	if global = O then	Only 1 global variable is
	considered to be useful for memoization
	continue
	end if
	return false;
	end if
	return false
	end if
	end for
	end for
	end function
	Algorithm 6 Replacing Memoizable Function Calls
	Require: Function F
	Ensure: Calls to Input function is replaced by calls to its memoized version
	globals ← GETGLOBALS(F)
	proto ← GETPROTOTYPE(F)
	SORT(proto)
	for each use cs of F do
	if ISCALLSITE(cs) then
	args ← GETARGS(cs)
	ARGS.ADD(globals)
	argsnew←SORT(args)
	for each argument x in args do
	if isPresent thenglobals,x
	continue
	end if
	index← ARGSNEW.FINDI(x)
	if ISCONSTANT(x) then
	PROTO.REMOVEFROMINDEX(index)
	ARGSNEW.REMOVEFROMINDEX(index)
	CALLSTRING.ADD(x.value)
	end if
	end for
	if HASUSE(F) then
	newF	←	MAKENEWFUNCTION(F.returntype,
	argsnew,F.parent)
	REPLACEALLUSESWITH(F, newF)
	PRINTTOFILE(callString)
	end if
	end if
	end for

Acknowledgments

This work was partially supported by the European Research Council Advanced Grant DAL Number 267175.