Abstract-This paper presents a new cache replacement policy based on Instruction-based Reuse Distance Prediction (IbRDP) Replacement Policy originally proposed by Keramidas, Petoumenos, and Kaxiras [START_REF] Keramidas | Cache Replacement Based on Reuse Distance Prediction[END_REF] and further optimized by Petoumenos et al. [START_REF] Petoumenos | Instruction-based Reuse Distance Prediction for Effective Cache Management[END_REF]. In these works [START_REF] Keramidas | Cache Replacement Based on Reuse Distance Prediction[END_REF][START_REF] Petoumenos | Instruction-based Reuse Distance Prediction for Effective Cache Management[END_REF] we have proven that there is a strong correlation between the temporal characteristics of the cache blocks and the access patterns of instructions (PCs) that touch these cache blocks. Based on this observation we introduced a new class of instruction-based predictors which are able to directly predict with high accuracy at run-time when a cache block is going to be accessed in the future, a.k.a. the reuse distance of a cache block. Being able to predict the reuse distances of the cache blocks permits us to make near-optimal replacement decisions by "looking into the future." In this work, we employ an extension of the IbRDP Replacement policy [START_REF] Petoumenos | Instruction-based Reuse Distance Prediction for Effective Cache Management[END_REF]. We carefully re-design the organization as well as the functionality of the predictor and the corresponding replacement algorithm in order to fit into the tight area budget provided by the CRC committee [START_REF]Cache Replacement Championship Homepage[END_REF]. Since our proposal naturally supports the ability to victimize the currently fetched blocks by not caching them at all in the cache (Selective Caching), we submit for evaluation two versions: the base-IbRDP and the IbRDP enhanced with Selective Caching (IbRDP+SC).

Our performance evaluations based on a subset of SPEC2006 applications show that IbRDP achieves an IPC improvement of 4.66% (arithmetic average) over traditional LRU, while IbRDP+SC is able to further increase its distance compared to the baseline LRU to 6.04%. Finally, we also show that IbRDP outperforms the previous state of the art proposal (namely Dynamic Insertion Policy or DIP [START_REF] Qureshi | Adaptive insertion policies for highperformance caching[END_REF]) by 2.32% in terms of IPC (3.81% for the IbRDP+SC).

INTRODUCTION

With fast advances in processor technology, the rapidly increasing imbalance between the relative speeds of processors and the main memory is the predominant problem that computer architects are trying to mitigate. With each access to the main memory taking hundreds of processor cycles, caches play an important role in bridging this performance gap. Therefore an increasingly larger portion of the chip silicon area budget is devoted to on-chip cache hierarchies (more than 60%). However, prior studies have shown that only a small fraction of the cache blocks actually hold data that will be referenced before evicted from the cache (called live blocks [START_REF] Kaxiras | Cache Decay: Exploiting Generational Behavior to Reduce Cache Leakage Power[END_REF]). Cache efficiency and not cache capacity is the correct metric to characterize the performance of the cache [START_REF] Burger | The declining effectiveness of dynamic caching for general-purpose microprocessors[END_REF]. Cache efficiency can be improved if more live blocks are stored in the cache without increasing its capacity. There are two ways to improve cache efficiency: i) by devising sophisticated prefetching mechanisms and ii) by improving the underlying replacement policy of the cache.

In this paper we investigate the design and implementation of a replacement policy for last-level caches (L3 caches) for single-threaded applications which adheres to the storage restrictions imposed by the committee of the first Cache Replacement Championship (CRC-1) [START_REF]Cache Replacement Championship Homepage[END_REF]: 8 bits per cacheline and 1 Kbit additional storage, for a total of 129 Kbit with unlimited logic complexity. The proposed mechanism leverages on our previous proposal, the Instruction-based Reuse Distance Predictor (IbRDP) Replacement Policy [START_REF] Keramidas | Cache Replacement Based on Reuse Distance Prediction[END_REF][START_REF] Petoumenos | Instruction-based Reuse Distance Prediction for Effective Cache Management[END_REF].

The remainder of this paper is organized as follows: Section 2 outlines the overall design, details the functionality of our new Instruction-based Reuse Distance Predictor and presents our simplified technique to collect at run-time the reuse distances of the cache blocks (reuse distance sampling). Section 3 describes our underlying replacement policy based on the information supplied by the IbRDP. Section 4 presents the hardware costs and demonstrates that our proposal adheres to the contest rules. Section 5 depicts our experimental results in terms of IPC compared to the traditional LRU and DIP [START_REF] Qureshi | Adaptive insertion policies for highperformance caching[END_REF] and Section 6 concludes this work.

PREDICTOR DESIGN AND FUNCTIONALITY

The effect of caching is fully determined by the program locality or the data reuse patterns of the memory references. As the memory hierarchy becomes deeper and deeper its performance increasingly depends on our ability to predict program locality. Previous work discloses mainly two ways of locality analysis: compile-time analysis and profiling. Ideally, a prediction scheme is needed that can be used at run-time and can be both efficient and accurate. In our previous work [START_REF] Keramidas | Cache Replacement Based on Reuse Distance Prediction[END_REF][START_REF] Petoumenos | Instruction-based Reuse Distance Prediction for Effective Cache Management[END_REF], we demonstrate that it is possible to quantify the temporal characteristics of the cache blocks at run-time by predicting the cache block reuse distances (measured in intervening cache accesses) based on the instructions (PCs) that touch the cache block.

Georgios Keramidas

Industrial Systems Institute, Patras, Greece keramidas@ece.upatras.gr

Stefanos Kaxiras

ECE, University of Patras, Greece kaxiras@ece.upatras.gr bottom). IbRDP is responsible to store the reuse distance predictions of the cache blocks. Due to area and performance constrains the reuse distance predictions are not represented with their actual scalar value but by using a granularity of 8K L3 accesses 1 . On every load or store L3 access the IbRDP is triggered by the instruction (PC) that caused the access (Predictor Lookup). In case of a hit, the IbRDP simply outputs the corresponding prediction (zero if the lookup misses). 2 An IbRDP hit means that this PC has already appeared in the program execution. The mechanism which is in charge of capturing and forwarding (Predictor Update) the correlations between PCs and reuse distances is the Reuse-Distance Sampler or RDSampler (Figure 1).

The RDSampler is organized as small FIFO queue (32 entries) sampling the L3 access stream. A new entry is inserted in the sampler every 4K accesses (empirically derived). Since it is a FIFO, its size and sampling rate determine the maximum reuse distance it can capture: max_reuse_distance=size × sampling_period. For example, our 32-entry FIFO sampling every 4K accesses can "see" the reuse distances of up to 32×4K=128K cache accesses. Apart from the insertion of a new entry in the RDSampler, for every L3 access a fully-associative search is also performed, triggered by the requested address. In case of a hit, we mark the hit entry as invalid, we calculate the quantized reuse distance of the access based on the position of the entry in the FIFO queue and we use this information (along with the PC) to update the IbRDP (Predictor Update). If the IbRDP does not contain information for the sampled PC, the LRU entry of the corresponding IbRDP set is filled with the information provided by the RDSampler.

Otherwise the sampled reuse distance is compared with the prediction stored in the predictor. If they match, the confidence counter (2-bit field in each entry of IbRDP) is incremented otherwise decremented. Finally, the predictor entry can change its reuse distance prediction (predictor replacement) only if its confidence counter is zero.

UNDERLYING REPLACEMENT POLICY

Having the quantized reuse distance information for each cacheline affords us to approximate an optimal replacement algorithm because we can "see" the future (as in Belady's OPT [START_REF] Belady | A study of replacement algorithms for a virtual-storage computer[END_REF]). On a miss we search the cache set. The pseudocode of the proposed replacement policy is depicted in Figure 2. Our aim is to find the cacheline that is going to be accessed farthest in the future (time_left variable in the pseudocode). The time_left (line 15-16 in the Granularities finer than 8K do not offer much additional useful information and make harder the prediction of the reuse distances (it is unlikely to encounter the exact same reuse distance over and over again due to the noise introduced at the access stream). 2 According to our study a predictor size of 256 entries is more than enough to capture all the significant PC's in a typical program phase. Additional entries would hold information for rarely executed load/stores that may not be easy to predict and do not significantly improve the effectiveness of our prediction.

preudocode) of a cacheline equals the time it was last accessed (the 3-bit time field stored in every cacheline) plus its reuse distance prediction (the 4-bit prediction field also stored in every cacheline) minus the current time (the 3-bit quantized value of the global timer). In other words, a cacheline's time_left is the (predicted) number of accesses that separate the present moment from its next access. Of course due to the tight area budget requested by the championship committee [START_REF]Cache Replacement Championship Homepage[END_REF] (max 8 bits per cacheline) all the available information (time field, prediction field and global timer) is quantized and aliasing will occur. We systematically explored the granularity of the prediction and timestamp quanta in order to achieve a good balance between accuracy and storage requirements.

In addition to the granularity problem there is another issue that we should take into account. What happens with the cache blocks which have no reuse distance prediction or whose time_left is negative -the predicted time of the access has passed. In this case, we need to also look into the past. The time_idle variable (line 17) estimates the difference between the line's last access and the global timer i.e., how long the line has remain unaccessed. The longer a line remains unaccessed the higher the probability that this line is not useful [START_REF] Kaxiras | Cache Decay: Exploiting Generational Behavior to Reduce Cache Leakage Power[END_REF]. These variables give us two ways to identify candidates for replacement, with both ways being quantified by exactly the same metric: time measured in L3 accesses. The eventual candidate will be the line with the largest time_idle (past) or time_left (future) value, because it either has remained unused or will remain unused longer in the cache than any other currently allocated cacheline. This guarantees that if we have prediction information, the replacement decision will be based on it; otherwise we revert to an LRU-like replacement.

The above algorithm (line 14 to 26) represents our base-IbRPD replacement policy. An extension of the algorithm is to victimize the currently fetched block by not caching it at all in the L3 cache (Selective Caching). This happens if the prediction for the currently fetched block is larger than the time_left or the time_idle value of the block selected by the base-IbRDP (lines 28-32). A final touch on the algorithm is an optimization which we experimentally found to be very beneficial. If the prediction for the currently fetched block is 15 (the maximum value), we choose to bypass the cache without even comparing against the other cachelines in the set (lines 7-12).

HARDWARE COST AND RULE COMPLIANCE

This section breaks down the area cost of the components used by our proposal and summarizes the overall cost. Recall that even though we submitted for evaluation two versions of our proposal (the base-IbRDP and the IbRDP enhanced with Selective Caching), both approaches account for exactly the same area budget. The detailed storage requirements are: RDSampler: 32 entries organized as a fully-associative buffer. Each entry contains: 26 bits for the address under investigation (lowest 32 bits minus the byte offset) plus 20 bits for the PC plus 5 bits containing the position of the entry in the FIFO buffer plus 1 valid bit. Total bits per entry: 52. Total bits for the FIFO sampler: 1664 bits. (We experimentally found that keeping more bits for either the PC or the recorded address produces marginal benefits). IbRDP: 256 entries organized as a 16-way set-associative cache (16 sets). Each entry contains: 16 bits for the recorded PC (20 bits minus the bits needed for indexing) plus 4 bits for the prediction information plus 2 bits for the confidence counters plus 4 bits for the local LRU information plus 1 valid bit. Total bits per entry: 27. Total bits for the predictor: 6912 bits. L3 Cache: 16K cachelines (1MB, 16-way set-associative cache). For management related purposes each block contains: 4 bits for the prediction plus 3 bits for the timestamp. Total bits per entry: 7. Total bits for the L3 Cache: 112 Kbits. Extra variables: i) 12 bits for accounting of the 4K sampling period, ii) 3 bits of the higher portion of the return candidate 34: end procedure accesses counter which provides the timestamp, and iii) 14 bits of the lower part of the accesses counter. Total bits for the extra variables: 29. The overall budget for our proposal amounts to 120.4 Kbits, below the 129 Kbit limit [START_REF]Cache Replacement Championship Homepage[END_REF].

EVALUATION

For our simulations, we relied on the standard version of the framework provided by the organizing committee of CRC-1 [START_REF]Cache Replacement Championship Homepage[END_REF]. Details about the processor and the memory configuration can be found in [START_REF]Cache Replacement Championship Homepage[END_REF]. Performance evaluations were based on 23 benchmark-input combinations from the SPEC2006 suite. The benchmark selection was done according to the following criterion: we exclude the benchmarks that do not report more than 1% decrease of their execution time when the L3 cache is doubled. Excluded benchmarks have either very low or very high cache requirements and do not benefit much from advanced replacement decisions. All executables were built with a 64bit version of gcc-4.2 using the -O2 and -msse3 flags. To generate instructional traces, 40B instructions were skipped and a trace 100M instructions long was obtained.

Figure 3 depicts the performance improvements in terms of IPC over LRU. The first bar in each set of bars represents the IPC improvement for DIP [START_REF] Qureshi | Adaptive insertion policies for highperformance caching[END_REF], while the second and the third bar illustrate the results for the base-IbRDP and the IbRDP+SC. Our results indicate that the benefits are significant for both the base-IbRDP and the IbRDP+SC. In the base-IbRDP case, bzip2.program shows the greatest performance gains over LRU (11.52%), while significant speedups are reported in the other benchmarks. A 11.46% speedup is achieved in astar.BigLakes, 9.87% in mcf.inp, and 6.43% in bzip2.chicken. Compared to DIP, our approach is almost always superior. IbRDP outperforms DIP by 2.32% on average (arithm.) and in no case degrades performance as much as DIP (up to 4.36%). When the selective cache technique is employed, our approach clearly outperforms DIP: IbRDP+SC increases IPC relative to DIP by up to 16.66% and 3.81% on average (arithm.).

CONCLUSIONS

In this paper we propose an Instruction-based Reuse Distance Prediction Replacement Policy suitable for lastlevel caches. The proposed policy was based on our previous works presented in [START_REF] Keramidas | Cache Replacement Based on Reuse Distance Prediction[END_REF][START_REF] Petoumenos | Instruction-based Reuse Distance Prediction for Effective Cache Management[END_REF]. We carefully simplify the structure and the functionality of our predictor in order to fit into the tight area budget provided by CRC-1. We submit two versions for evaluation: the base-IbRDP and IbRDP with Selective Caching. We evaluate our proposals with a 129 Kbit storage budget in the CRC-1 framework. The evaluation results show a 4.66% IPC improvement (arithm. average) over LRU for the base-IbRDP (6.04% for the IbRDP+SC) by using a subset of the SPEC2006 suite.

Figure 1

 1 outlines our proposal for predicting the reuse distances of the cache blocks at run-time: the Instruction based Reuse Distance Predictor or IbRDP (Figure 1 Instruction-based Reuse Distance Prediction Replacement Policy Pavlos Petoumenos ECE, University of Patras, Greece ppetoumenos@ece.upatras.gr

Figure 1 .

 1 Figure 1. Overall design of the proposed mechanism: Instruction-based Predictor (bottom), reuse distance FIFO Sampler (top left), detailed format of entries (top right).

Figure 2 .

 2 Figure 2. The Underlying Replacement Algorithm.

Figure 3 .

 3 Figure 3. IPC for the DIP, IbRDP, and IbRDP+SC normalized to LRU.

ACKNOWLEDGEMENTS

This work is supported by the EU-FP6 Integrated Project, Scalable computer ARChitecture (SARC), Contract No. 27648 and the EU-FP7 ICT Projects, "A highly efficient adaptive multi-processor framework (HEAP)," Contract No. 247615, and "Embedded Reconfigurable Architecture (ERA)," Contract No. 249059.


Maxwell Souza

Daniel Nicácio
email: dnicacio@ic.unicamp.br

Guido Araújo

ISAMAP: Instruction Mapping Driven by Dynamic Binary Translation

Dynamic Binary Translation (DBT) techniques have been largely used in the migration of legacy code and in the transparent execution of programs across different architectures. They have also been used in dynamic optimizing compilers, to collect runtime information so as to improve code quality. In many cases, DBT translation mechanism misses important lowlevel mapping opportunities available at the source/target ISAs. Hot code performance has been shown to be central to the overall program performance, as different instruction mappings can account for high performance gains. Hence, DBT techniques that provide efficient instruction mapping at the ISA level has the potential to considerably improve performance. This paper proposes ISAMAP, a flexible instruction mapping driven by dynamic binary translation. Its mapping mechanism, provides a fast translation between ISAs, under an easy-to-use description. At its current state, ISAMAP is capable of translating 32-bit PowerPC code to 32-bit x86 and to perform local optimizations on the resulting x86 code. Our experimental results show that ISAMAP is capable of executing PowerPC code on an x86 host faster than the processor emulator QEMU, achieving speedups of up to 3.16x for SPEC CPU2000 programs.

I. INTRODUCTION

With the availability of 64-bit multi-core processor instructions sets like EM64T1 , AMD64 2 and others (e.g. PowerPC), new cross platform optimization opportunities have surfaced. Although old 32-bit programs can still run on such architectures, they do not take full advantage of some 64-bit new architecture features (i.e. the additional number of registers). Moreover, consumer electronics have been opening up new opportunities for low-power general-purpose processors, which eventualy could benefit from DBT by running programs not compiled for that domain.

Running code in a DBT environment can considerably impact the program execution time, due to the time required to translate instructions into the new target ISA. On multicore processors this overhead can be considerably reduced, by assigning one thread to do binary translation, optimization and profiling, while another thread executes the translated code [1] [2]. This paper presents ISAMAP, an instruction mapping driven by dynamic binary translator, which uses dynamic ISA mapping in code translation. Source program instructions are decoded, mapped and encoded into host code by following the instruction set descriptions of the involved architectures. These descriptions, in assembly-like language, allows for an efficient mapping as it taps on the low-level machine code features of each architecture. The result is a good quality code for the target architecture. In the specific case of the PowerPC to x86 translation, ISAMAP achieves speedups of up to 3.16x when comparing against QEMU running SPEC CPU2000 programs.

This paper is divided as follows. Section II presents some popular Dynamic Binary Translators (DBTs). Section III shows the ISAMAP environment, how it works, format of the description, mapping statements and some issues related to the binary translation process. Section IV shows experimental results on dynamic translation between PowerPC to x86 code and optimization speedups. Section V concludes with some observations and future work.

II. RELATED WORK

Aries [START_REF] Zheng | PA-RISC to IA-64: Transparent Execution, No Recompilation[END_REF] does binary translation between PA-RISC and IA-64 code using a fast interpretation mechanism. The interpreter counts how many times each block is interpreted, once the block counter reaches a threshold it is translated into native code. Translated blocks are stored in code cache and restored when necessary. System calls, signals and exceptions are handled by the Environment Emulation System.

Digital FX!32 [START_REF] Chernoff | DIGITAL FX!32 -Running 32-Bit x86 Applications on Alpha NT[END_REF] executes x86 code on an Alpha System by employing emulation and static binary translation. The x86 program is totally interpreted during the first time it executes and information about its execution behavior is stored (profiling). Once the interpreted execution is completed, FX!32 system performs program translation based on the data collected during the profiling execution. Translated code is stored in a database. Next time the program is requested to run, FX!32 collects the translated code from a database and executes it.

IA-32 EL [START_REF] Baraz | IA-32 Execution Layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium-based systems[END_REF] allows IA-32 code execution on Itanium based systems through interpretation and dynamic binary translation. IA-32 EL uses two mechanisms: Cold Code Translation, which interprets IA-32 code and Hot Code Translation, which translates the most executed blocks to form a super-block or a trace.

Translated blocks are stored into code cache and retrieved every time it is needed. Every exception thrown is redirected to the IA-32 EL system, which translates the exception to an IA-32 exception before passing it to the original application. In integer benchmarks, IA-32 EL executes translated code with 65% of the original code performance.

Dynamo [START_REF] Bala | Dynamo: A transparent Dynamic Optimization System[END_REF] translates PA-8000 code to PA-8000. The PA-8000 code is interpreted until a hot region is found (traces, loops, etc). Once a hot region is found, optimizations are performed on code and it is stored into a code cache. Optimizations performed by Dynamo achieve speedups up to 1.22x in some benchmarks.

In UQDBT [START_REF] Ung | Optimising hot paths in a dynamic binary translator[END_REF] a set of specifications defines binary code format, instructions syntax and semantic, allowing a very flexible system. UQDBT is also capable of identifying hot paths and apply optimizations. UQDBT has slowdown between 2.5x and 7.0x when compared to native code. When optimizations are turned on, slowdown is reduced in 15%.

ADORE [START_REF] Lu | Design and implementation of a lightweight dynamic optimization system[END_REF] is a dynamic binary optimization framework with hardware (Itanium 2) mechanisms to help the code analysis during execution. The ADORE system tries to identify the most frequently executed traces, which are built with the help of dedicated registers that store the last four taken branches. Once the trace is built, several optimizations can be applied: register allocation, data cache pre-fetching and trace layout. Due to its hardware support, ADORE has a low overhead, 2%, and can achieve speedups up to 2.56x.

Yirr-Ma [START_REF]Fast dynamic binary translation the yirr-ma framework[END_REF] is another dynamic binary translation framework that uses customized code instrumentation. Like other DBTs, it collects code behavior information through emulation and uses it to translate and optimize binary code. Yirr-Ma uses the WalkAbout framework, a framework that automatically generates emulators from SLED and SSL specifications. Since Yirr-Ma is an emulator, each source ISA instruction is represented as a function in a high-level language (eg. C). This function carries instrumentation code that allows identifying hot regions on the emulated code. Once hot regions are known, they can be translated to host code and optimized.

DAISY [START_REF] Ebcioglu | Daisy: dynamic compilation for 100architectural compatibility[END_REF] is a dynamic emulator designed to target VLIW architectures. It is capable of transalating PowerPC code to VLIW primitives, then it optimizes the resulting code to take full advantage of the target architecture. The final code shows good instruction level paralelism.

QEMU [START_REF] Bellard | Qemu, a fast and portable dynamic translator[END_REF] is a fast open source emulator that uses binary translation and runs several different source ISAs on many target hosts, including x86, x86 64 and PowerPC. The instruction mapping is performed by using C functions like in Yirr-MA [START_REF]Fast dynamic binary translation the yirr-ma framework[END_REF]. These functions are compiled and its object code linked with the emulator code. The encoding process is done by a simply copy and paste method that allows a very fast host code encoding. Code cache and block linkage mechanisms guarantee a great performance, considering QEMU is an emulator. QEMU executes PowerPC code on x86 host between 4 and 10 times slower than native x86 code.

ISAMAP holds some similarities and differences when compared to the above mentioned systems. Unlike ISAMAP, DYNAMO and ADORE use dynamic translation to optimize code on the fly, and thus need no instruction mapping. The remaining systems translate code between different architectures. While most of them use a generic intermediate language, free of architecture restrictions, IA-32 EL and ISAMAP are similar in the sense that both use a direct instruction mapping mechanism. As far as we know, IA-32 EL and ISAMAP are both capable of adaptative translation, based on the instruction parameters. On the other hand, ISAMAP uses a very simple syntax, similar to those found in well-known compiler frontend and code-generator generation tools [START_REF] Aho | Code generation using tree matching and dynamic programming[END_REF], [START_REF] Fraser | Engineering a Simple, Efficient Code Generator Generator[END_REF]. As the experiments reveal, this exposes low-level mapping opportunities which result in an afficient way to translate code between architectures.

III. ISAMAP

ISAMAP descriptions are a subset of ArchC [START_REF] Azevedo | The ArchC architecture description language and tools[END_REF], an architecture description language, which has been largely used to synthesize processor simulators and assemblers [START_REF] Baldassin | Extending the ArchC language for automatic generation of assemblers[END_REF]. By using ArchC, it is possible to describe both functional and cycle accurate processor models. ISAMAP requires three ArchC models, one for the source processor, another for the target ISA and one to describe the instruction mapping between them. By using ArchC, ISAMAP can easily capture processor instructions format, registers, operands, and instruction mapping. Figure 1 shows an example of PowerPC ISA description model and figure 2 shows a x86 ISA description model. From these models, part of the binary translator source code is automatically generated.

A. Models

The main ISAMAP fields used to describe the source/target ISA and the mapping between them are listed below. ISAMAP uses such fields to automatically synthesize the source/target ISA decoder/encoder.

• isa_format: declares an instruction format, its fields and size in bits; • isa_instr: instantiates instructions and assign them to their respective formats; • isa_reg: defines names and opcodes for the processor registers; • isa_regbank: defines register banks and the register interval for bank registers; • set_operands: specifies instruction operands, their types and to which field they are assigned to. There are three possible operand types: reg: register, addr: address and imm: immediate. • set_encoder and set_decoder: describes which fields identify an instruction and their respective values. Figure 2 shows an example on how to use the ISAMAP fields. Line 2 isa_format defines a format named (op1b_r32) containing four fields of sizes: 8, 2, 3, 3 bits. Line 3 isa_instr declares two instructions (add_r32_r32 and mov_r32_r32), which belong to format op1b_r32. From line 4 to 7, registers are declared and their opcode is defined by the keyword isa_reg. Lines 9 and 11 define operands of instructions add_r32_r32 and mov_r32_r32. In the two instructions, field rm is the first operand and field regop the second. Lines 10 and 12 define values for the instruction operands, but in this case, only fields op1b and mod have their values declared.

The instruction mapping between source and target ISA is described in a third description. For each source architecture instruction, its behavior is mapped into one or more instructions. As shown in figure 3, the syntax of the description is similar to the one used in code-generator tools like iburg [START_REF] Fraser | Engineering a Simple, Efficient Code Generator Generator[END_REF] and twig [START_REF] Aho | Code generation using tree matching and dynamic programming[END_REF].

isa_map_instrs { add %reg %reg %reg; } = { mov_r32_r32 edi $1; add_r32_r32 edi $2; mov_r32_r32 $0 edi; } Although this approach is not as portable as the mapping scheme used by Yirr-MA [START_REF]Fast dynamic binary translation the yirr-ma framework[END_REF], it allows the generation of faster code and provides enough flexibility to implement different mappings for each source architecture instruction. As an example, the mapping shown in figure 3 could also be described by an lea instruction, thus resulting in one less instruction mapping. ISAMAP leverages on similar opportunities to considerably improve the quality of the target processor code.

Symbols like edi are used when a specific register of the target architecture is required, in this case, register edi. Symbols started by $ character indicate a reference to an instruction operand in the source architecture instruction, $0 refer to operand 0, $1 to operand 1 and so on. If the referenced operand is a register, the register in the target architecture, which maps the source architecture register, is defined in the instruction. Figure 4 shows an example of the resulting code after mapping the PowerPC instruction add r0, r1, r3 to x86 code. Instructions in lines 0, 2, 5 are spill code, and will be addressed later. 0 mov eax, 0x80740504 1 mov edi, eax 2 mov eax, 0x80740508 3 add edi, eax 4 mov eax, edi 5 mov 0x80740500, eax The instruction in line 0 loads the content of register R1, which is mapped to memory, as EAX. In line 2, register R3 is loaded into EAX. In line 5, the operation result is stored into register R0. This code sample can be tuned up if another add instruction mapping is used. Notice that the x86 architecture allows instruction operands to be a memory reference (but not all of them). If that is the case, instructions add and mov are used, resulting in a generated code with at least three fewer instructions. Figure 5 shows the alternative specification of instructions add and mov, when having one operand as a memory reference. Figure 6 illustrates the new mapping and figure 7 shows the generated code for the new mapping. As it can be seen, the new mapping has only three instructions.

... isa_format op1b_r32_m32disp = "%op1b:8 %mod:2 %regop:3 %rm:3 %m32disp:32"; isa_instr <op1b_r32_m32disp> add_r32_m32disp, mov_r32_m32disp; ... add_r32_m32disp.set_operands("%reg %addr", regop, m32disp); add_r32_m32disp.set_encoder(op1b=0x01, mod=0x0, rm=0x5); mov_r32_m32disp.set_operands("%reg %addr", regop, m32disp); mov_r32_m32disp.set_encoder(op1b=0x8b, mod=0x0, rm=0x5); mov_m32disp_r32.set_operands("%addr %reg", m32disp, regop); mov_m32disp_r32.set_encoder(op1b=0x89, mod=0x0, rm=0x5);

B. System Overview

The structure of binary translator ISAMAP follows the same structure of most binary translators available in the literature. The translation module is formed by two sub-modules: decode and encode. The Run-Time module contains the following sub-modules: Code Cache, Block Linker and System Call Mapping. Code Cache stores basic blocks already translated, thus allowing fast target code retrieval when needed. Block Linker, as the names states, links basic blocks, thus avoiding the intervention of Run-Time module every time a basic block is executed. At last, the System Call Mapping module is responsible for the mapping, during the translation process, between the system calls with different implementations in the involved architectures.

C. Translator Generation

The Translator Generator receives as input the source, target, and mapping descriptions and then generates the translator's source code in C, translator.c. Code in translator.c is responsible for making calls to the decoder and a C-switch block makes the mapping and code emission (into target architecture instructions). This process is performed for each source architecture decoded instruction. The following files are also generated:

• ctx switch.c: Responsible for the emission of binary code that stores and loads the target architecture registers content;

• isa init.c: Initializes the data structures that hold information about instructions, formats and field of the source architecture; • encode init.c: Initializes data structures that hold information about instructions, formats and field of the target architecture; • pc update.c: Defines function prototypes, which are responsible for emulating branch instructions. Implementation of this function must be provided. • spill.c: Defines function prototypes for spill code emission. Implementation also needs to be provided; • sys call.c: Defines functions prototypes for system call mapping. Implementation needs to be provided; The code for Decoder, Encoder and Utils are generic enough, so they are provided as a library. There is no need to have its source code generated.

D. Translator

The translator input is the binary code of the application we want to execute in the host architecture, in our case PowerPC code. The binary code is loaded from an ELF file 3of the program to be translated. The Decoder decodes one instruction at a time until a branch instruction is found. Branch instructions are defined in the source architecture description by the command set_type("jump"). Figure 9 shows an example of a PowerPC branch instruction definition.

bc.set_operands("%imm %imm %addr %imm %imm", bo, bi, bd, aa, lk); bc.set_decoder(opcd=16); bc.set_type("jump"); Source architecture instructions are decoded to an intermediate representation (IR) and from this into a target architecture IR, as indicated in the mapping description model. The target intermediate representation is then encoded as target binary code. Branch instructions are not translated at this stage; this be done later by the Block Linker. While blocks are not linked, source architecture branch instructions are emulated. Emulation does all the jump test conditions, and register update and next instruction address computation. This emulation sub-system is not generated by the Translator Generator, thus its implementation must be provided by the ISAMAP programmer.

All source architecture registers are represented in memory, thus allowing target and source architectures to have different number of registers. Static one to one register mapping is not allowed. For each reference to source registers in instruction mapping, spill code is generated to load its contents to x86 registers and store them back to memory. A simple but effective register allocation is performed later to improve code performance. Those registers that do not have their content changed in the mapping are considered read only, therefore they need only to be loaded. Registers that are written are write only, and therefore must be written into memory. If a register is read and have its value changed in the mapping, it must be loaded and written into memory. Spill code is not generated by the translator when we have mappings like the one in figure 6, where the target instruction operand is a memory reference (addr type).

The role of an instruction operand (if it is used or defined) is determined in the architecture description model by key words set_write and set_readwrite. If neither of them is used, the operand is considered read only. An example is shown in figure 10. Lines 0, 2 and 5 of figure 4 are samples of code generated to load and store register content into memory.

add_r32_r32.set_operands("%reg %reg", rm, regop); add_r32_r32.set_encoder(op1b=0x01, mod=0x3); add_r32_r32.set_readwrite(rm); mov_r32_r32.set_operands("%reg %reg", rm, regop); mov_r32_r32.set_encoder(op1b=0x89, mod=0x3); mov_r32_r32.set_write(rm); 1) Intermediate Representation: The Intermediate Representation (IR) used by the ISAMAP Translator is the same used in ArchC [START_REF] Azevedo | The ArchC architecture description language and tools[END_REF], with some changes to represent instructions, formats and fields. Table I shows the intermediate representation and some description of its fields grouped in a data structure.

Structure isa_op_field was included to represent fields that are instruction's operands and operands access mode (read, write, read/write). Field type was included to add semantic information about instruction type, as the ArchC language does not support semantics in the description models. Insertion of field format_ptr was done to improve the translator performance. Instead of performing a search in a linked list for the format name, we have a pointer to the format object. When an instruction object is created, format_ptr receives a pointer to the respective format object. So, instead of performing a linear search (O(n)) in a linked list, we have a direct pointer to the desired instruction format (O(1)).

E. Endianness

In binary translation between architectures with different endianness, like the PowerPC (big endian) and x86 (little endian), it is necessary to do endianness conversion every time data is accessed in memory. In PowerPC, endianness conversion is restricted to the translation of load and store instructions.

Before the program starts, the memory region containing data in big endian format is the data segment, where global and static variables are located. Heap segment has no initial values on program start-up and stack is initialized by the ISAMAP Run-Time System. As data can be copied from heap to stack and from stack to heap, the approach adopted by ISAMAP is to handle all data in memory as big endian. The conversion is always done when load/store instructions are executed. The same approach is used by QEMU [START_REF] Bellard | Qemu, a fast and portable dynamic translator[END_REF]. Endianness conversion code is specified in the mapping model description for all load/store instructions. A mapping example can be seen in figure 11. 486 processors and later have bswap instruction that swap the bytes of 32 bits words, this makes endianness conversion a lot faster. Endianness conversion on 16 bits words is performed by xchg instruction.

F. Run-Time

ISAMAP Run-Time System (RTS) is responsible for initialize the whole environment needed by the translated program execution, code cache management, block linkage and system calls mapping. RTS implementation is very tied to the host architecture, so its portability is penalized. As an example, context switch between RTS and translated code needs to save and restore all host registers. The code to do this is written in assembly, thus resulting in no portability, but considerably improving performance.

1) Initialization: The execution environment of the translated code is set following the source architecture ABI (Application Binary Interface) specifications, in this case PowerPC Linux. Some registers must have an initial value, like PowerPC register R1, which must store the stack pointer. Initialization process is also responsible for allocating the stack. ISAMAP allocates 512 KB stack, as it is sufficient to execute most of SPEC CPU 2000 benchmarks, except 176.gcc, that needs 8 MB of stack size. Stack initial values are also set following ABI specification [START_REF]Linux Standard Base Specification for the PPC32 Architecture 1.3[END_REF], but they can change according to the environment requirements.

2) Translated Blocks Execution: To execute translated code in a binary translator address space, a sandbox is needed. This sandbox must provide two independent environments, so that one does not interfere with the other. Before every translated code execution, all registers used by the translator must be saved (prologue); and after translated code execution, those same registers must be restored (epilogue). Prologue and Epilogue code are shown in figure 12. X86 register esp is not saved or restored because it is not used in translated code, avoiding stack issues due to the use of instructions call and ret to switch between translated code and the Run-Time system. When basic blocks are executed for the first time, the control is switched between RTS and translated code for each basic block. After the first execution of a basic block it is linked by the Block Linkage System and control switching is not needed until another basic block executes for the first time.

Prologue Epilogue mov 0x80a48000, eax mov eax, 0x80a48000 mov 0x80a48004, ecx mov ecx, 0x80a48004 mov 0x80a48008, edx mov edx, 0x80a48008 mov 0x80a4800c, ebx mov ebx, 0x80a4800c mov 0x80a48010, esi mov esi, 0x80a48010 mov 0x80a48014, edi mov edi, 0x80a48014 mov 0x80a48018, ebp mov ebp, 0x80a48018 3) Code Cache: Code translation is much slow when compared with native code execution, so is not a good approach to translate the same basic block for each loop iteration. After each basic block translation and execution, ISAMAP RTS stores it into a code cache. Unlike other DBTs where blocks are interpreted and must reach a threshold before being stored into code cache, ISAMAP stores every executed block. Code cache greatly improves performance by avoiding retranslations. Whenever a block is needed, RTS can fast retrieve it from the code cache.

Translated blocks are identified in code cache by its original address in the original code (before translation). The original address is passed to a hash function and a hash key is obtained.

This key will index the hash table. When a block is requested, search in the hash table is performed, what is done very fast. Collisions are solved by chaining other blocks at the same position of the hash table. Figure 13 shows the hash table layout used in ISAMAP.

Figure 13. Hash table used in Code Cache

As in QEMU [START_REF] Bellard | Qemu, a fast and portable dynamic translator[END_REF], ISAMAP allocates a contiguous memory region of 16MB to be used as code cache. This size is enough to execute all SPEC CPU 2000 benchmarks, but of course, it can be extended. Macro ALLOC is used to retrieve the address of the next free position in the code cache to store the translated block. Due to the code cache structure, blocks running in sequence will be next to each other in the code cache, thus improving the translated code performance.

ISAMAP code cache management policy is very simple. Whenever the cache becomes full it is totally flushed, like in QEMU [START_REF] Bellard | Qemu, a fast and portable dynamic translator[END_REF]. Code cache is rarely flushed since 16 MB is enough to execute all benchmarks and this approach simplifies the Block Linkage System implementation, as block unlinking becomes unnecessary when the cache is totally flushed. Some code cache management policies could be used to improve code cache performance. Hazelwood and Smith [START_REF] Hazelwood | Managing bounded code caches in dynamic binary optimization systems[END_REF] propose a technique that makes it easy to identify longlived code blocks to be cached and simultaneously avoid any fragmentation evicting short-lived blocks. Reddi et al. [START_REF] Reddi | Persistent code caching: Exploiting code reuse across executions and applications[END_REF] suggested storing and reusing translations across executions, thereby achieving inter-execution persistence.

4) Block Linker: To improve performance, the ISAMAP translation system has a block linkage module like QEMU [START_REF] Bellard | Qemu, a fast and portable dynamic translator[END_REF] and Yirr-MA [START_REF]Fast dynamic binary translation the yirr-ma framework[END_REF]. Linking translated blocks avoid control switch between RTS and translated code, improving overall performance.

Block Linker is capable of dealing with four link types: conditional branches, unconditional branches, system calls and indirect branches. System calls are considered unconditional branches in ISAMAP. Assume, for example, that Block A is the last translated and executed block. Block A has two possible successors, Block B and Block C. Block B is the branch instruction's target and Block C is the fall through block. If the next block to be executed is B, Blocks A and B will be linked, otherwise Blocks A and block C will be linked. The remaining block will be linked if and only if it is executed in the future. ISAMAP does block linkage on demand, avoiding that blocks which will never be executed to be linked and stored into the code cache.

Block linkage is done by adding code stubs at the translated block end. These stubs are needed to test conditions if the branch is conditional, to jump to the successor block, and to return to RTS if the target was not translated yet.

G. System Calls Mapping

System calls implementation differs for each architecture and/or operational system. The main differences are the number of available calls and parameters, parameter endianness, data structure formats and how parameters are passed. In PowerPC architecture, all system calls parameters are passed in registers, unlike in x86, in which some system calls have parameters passed by memory reference (as few registers are available).

When necessary, ISAMAP System Calls Mapping needs to convert in/out parameters, as well to perform other data conversions to assure the correct execution of the host system calls. In some cases, the values of call's parameters are kernel constants which need to be updated. Some kernel constants have different values for each architecture kernel implementation. An example is the system call sys_ioctl, where constants that identify IO devices differ from PowerPC to the x86 kernel implementation. Data structures are another issue, for example, system calls sys_fstat and sys_fstat64 use structs fstat and fstat64, which have different field alignment in PowerPC and x86 implementations.

In the PowerPC to x86 system call mapping, the six system call parameters (registers R3-R8 in PowerPC) are copied to x86 registers EBX, ECX, EDX, ESI, EDI, EBP. R0 contains system call number, so it is copied to EAX. After the system call execution, EAX content (System call return value) is copied into R0. Before calling a system call, all host registers (except EAX) are saved; after its execution they are restored.

H. Mapping Improvements

Along the design of ISAMAP, we have noticed that the way instructions are mapped can drastically change the performance of the translated code. As hot code regions are very relevant to program overall performance, mapping should be done very carefully. An example faced during this project was PowerPC instructions that change the register CR (Conditional Register). CR can be changed by arithmetic and logical instructions, and is always changed by comparison instructions. A proper mapping of such instructions has show to be crucial to improve program performance. Figure 14 shows the mapping of cmp instruction, which modifies CR; and figure 15 shows a better mapping for the same instruction.

The Conditional Register (CR) is divided in 8 groups of 4 bits. Each group has the following layout from left to right: first bit indicates "less than", second bit indicates "greater than", third bit indicates "equal", and the last bit indicates "summary overflow". The mapping in figure 14 has four branch instructions to change each bit in CR. However, the first three bits are mutual exclusive, in other words, there is no possibility of a logical expression result in "less than", "greater than" or "equal" at same time. Therefore, the mapping of lines 7 to 18 of Figure 14 can be done with lines 5 to 11 of Figure 15 instead. Mapping at figure 15 also has less branch instructions, improving performance even more.

0
As stated above, there are 8 groups of 4 bits to be updated by the cmp PowerPC instruction, given it has a parameter that shows which of the 8 groups must be updated with the comparison result. This parameter is an immediate, and thus it does not change throughout the execution. Therefore, the bit mask generated in lines 26-28 of figure 14 can be generated at translation time, which is done only once. To turn this possible, some macros were added to the ISAMAP description language. The macro nniblemask32() receives the above mentioned parameter, generates the desired bit mask and puts it into the host instruction. The and instruction in line 16 of figure 15 shows an example. This approach eliminates three extras instructions that would be required to build the bit mask. The PowerPC ISA has other instructions which present similar issues related to the bit mask generation from immediate operands; other macros are used to address them.

I. Conditional Mapping

In the PowerPC architecture, the pseudo-instruction mr (copy between registers) is implemented by instruction (or rx ry ry), which uses the same register for two of its source operands. x86 instruction or can be used to directly map mr into x86 code. However, the x86 ISA has a specific instruction to copy from one register to another: the mov instruction, which is very fast. Thus, using the mov instruction to map PowerPC mr is better than using the or instruction. The mapping will depend on the operands used by the or instruction. To address this, a if-then-else structure was added to ISAMAP, thus allowing two different mapping to mr. The decision is taken on the fly, depending on the if-then-else parameters.

Figure 16 shows the PowerPC or instruction mapping example, it illustrates the two scenarios listed above. When the two source operands (defined as rs and rb on the PowerPC models) are the same, the translator emits a mapping related to the true clause of the textttif statement, otherwise, the mapping related to the else statement is generated. By adopting this approach, whenever a PowerPC or instruction is used to make a copy between registers, it is mapped with one less instruction. Another example can be seen in Figure 17. It shows the Rlwinm instruction, which rotates source operand to the left, then performs a logical AND with a mask. If the rotate parameter (defined as sh on the PowerPC model) is zero, then the x86 instruction rol is not needed, resulting in one less instruction in the mapping.

isa_map_instrs { rlwinm %reg %reg %imm %imm %imm; } = { if(sh = 0) { mov_r32_m32disp edi $1; and_r32_imm32 edi mask32($3, $4); mov_m32disp_r32 $0 edi; } else { mov_r32_m32disp edi $1; rol_r32_imm8 edi $2; and_r32_imm32 edi mask32($3, $4); mov_m32disp_r32 $0 edi; } };

J. Run-time Optimizations

ISAMAP does a few optimization at the basic block level (ISAMAP does not have a trace building mechanism). Optimizations performed are copy propagation, dead code elimination (only mov instructions), and local register allocation. Every translated block is optimized. Therefore, almost the whole program code passes through the optimizations. After a block is optimized, it is stored in code cache and set as optimized, leaving the linkage process unchanged.

At first, all source architecture registers are mapped into memory, but with the local register allocation it is possible to exchange memory accesses by registers accesses. Registers are not reallocated, only references to source architecture registers may be allocated to host registers. Memory references to heap, code and stack segments are not considered in the allocation process.

As ISAMAP translates instruction by instruction, it generates unnecessary load instructions. For example, in Figure 18 the translation process generated two unnecessary mov instructions in lines 3 and 4. Those instructions are removed by the copy propagation optimization. Dead code elimination is used to remove any unnecessary code left by copy propagation.

A. Evaluation

Experimental results are presented as follows: ISAMAP performance compared against QEMU performance, ISAMAP optimized performance compared against QEMU performance. The SPEC CPU 2000 reference data set was used; the machine used was a Pentium 4 HT 2.4 GHz, 1 GB RAM. PowerPC code was generated with cross compilers gcc-3.4.5 and gfortran-4.1.0. QEMU version used was 0.11.0.

Figure 19 shows benchmark times for the most effective PowerPC to x86 mapping model, as well as the optimized code times. CP+DC indicates that copy propagation and dead code elimination have been applied, RA indicates that only local register allocation was performed. CP+DC+RA indicates that all optimizations were applied. With all optimizations on, we achieved a maximum speedup of 1.71x on 164.gzip run 2 and only two runs were not benefited by the optimizations (186.crafty run 1 and 252.eon run 1).

Figure 20 shows how ISAMAP compares to QEMU on SPEC INT benchmark. All programs had at least 1.11x speedup; the maximum speedup was 3.16x on 252.eon run 1 with no optimizations. With all optimizations being applied, the maximum speedup achieved was 3.01x on the 252.eon run 3.

Figure 21 shows ISAMAP results, when compared to the QEMU results for the SPEC FLOAT benchmark. Although it is not a fair comparison, we decided to show results for future references. It is not fair to compare these results because ISAMAP uses SSE instructions to translate floating point instructions and QEMU does not. The minimum speedup was 1.79x on 197.art run 1; the maximum speedup was 4.32x on 172.mgrid.

V. CONCLUSION

Multi-core processors and 64 bits architectures are quite popular nowadays, and binary translation and emulation have been improving their efficiency to allow improved legacy code execution on these architectures. Binary translation systems also allow optimizations that cannot be done at compile time, due to the lack of execution data behavior.

This paper has presented ISAMAP, a instruction mapping driven by dynamic binary translation. ISAMAP offers a flexible easy-to-use environment to construct instruction mappings between. It has shown better performance when compared to QEMU, reaching up to 3.01x speedups.

Mapping at instruction level has shown to considerably improve overall program performance, as hot code regions can considerably benefit from them. The simplicity of the ArchC constructs of has made it quite easy to design efficient mappings. However, this approach has poor portability when compared with QEMU [START_REF] Bellard | Qemu, a fast and portable dynamic translator[END_REF], and Yirr-MA [START_REF]Fast dynamic binary translation the yirr-ma framework[END_REF], where mappings are described at a higher abstraction level.

We believe that our work provides a convenient and detailed development environment for further DBT programmers. In order to extend the system to target other architectures, there is no need of knowledge of the detailed implementation of the translator, only source/target ISA descriptions and a mapping between then are needed.

A. Future Works

Dynamic optimizations have the potential to improve legacy code performance, given the availability of run time information. PIN [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF], is an efficient tool for code analysis and instrumentation, which has been extensively used to study program dynamic behavior [START_REF] Reddi | Persistent code caching: Exploiting code reuse across executions and applications[END_REF], [START_REF] Moseley | Identifying potential parallelism via loop-centric profiling[END_REF] and [START_REF] Hazelwood | A cross-architectural interface for code cache manipulation[END_REF]. Several papers present efficient binary translation systems which apply dynamic optimizations to improve sequential code execution (e.g. [START_REF] Lu | Design and implementation of a lightweight dynamic optimization system[END_REF], [START_REF] Dehnert | The Transmeta code morphing software: Using speculation, recovery, and adaptive retranslation to address reallife challenges[END_REF] and [START_REF] Li | Optimizing Dynamic Binary Translation for SIMD Instructions[END_REF]) and parallelization (e.g. [START_REF] Yardimci | Dynamic Parallelization and Mapping of Binary Executables on Hierarchical Platforms[END_REF], [START_REF] Zhao | Lazy Interprocedural Analysis for Dynamic Loop Parallelization[END_REF] and [START_REF] Wang | Dynamic parallelization of single-threaded binary programs using speculative slicing[END_REF]).

For the future, we intend to implement more sophisticated optimizations techniques, based on trace construction, and dynamic code parallelization, mainly due to multi-core architecture popularization, which demands multi-thread application to use the whole hardware potential. We also intend to expand ISAMAP, making it capable of dealing with self-modifying code and exceptions. We believe ISAMAP can also be used as a way to automatically synthesize code mapping fragments, so as to explore the potential of low-level ISA descriptions.

Figure 3 .

 3 Figure 3. Mapping sample PowerPC to x86.

Figure 4 .

 4 Figure 4. Generated code sample.

Figure 5 .Figure 6 .Figure 7 .

 567 Figure 5. Another example of x86 instructions specification.

Figure 8

 8 Figure 8. ISAMAP structure

Figure 9 .

 9 Figure 9. Conditional branch instruction definition.

Figure 10 .

 10 Figure 10. Read/write definition.

Figure 11 .

 11 Figure 11. Load instruction mapping.

Figure 12 .

 12 Figure 12. Prologue and Epilogue code.

Figure 15 .

 15 Figure 15. Improved cmp instruction mapping.

Figure 16 .

 16 Figure 16. Or instruction mapping.

Figure 17 .

 17 Figure 17. Rlwinm instruction mapping.

  At the current state, ISAMAP translates and correctly executes the following SPEC CPU 2000 benchmarks: 164.gzip, 175.vpr, 176.gcc, 181.mcf, 186.crafty, 197.parser, 252.eon, 254.gap, 256.bzip2, 300.twolf, 168.wupwise, 171.swim, 172.mgrid, 173.applu, 177.mesa, 178.galgel, 179.art, 183.equake, 187.facerec, 188.ammp, 191.fma3d, 301.apsi. Optimizations are applied only to SPEC INT programs. The following benchmarks are running properly with optimizations: 164.gzip, 175.vpr, 181.mcf, 186.crafty, 197.parser, 252.eon, 254.gap, 256.bzip2, 300.twolf.

	Source PowerPC code
	1. ADD R1 R2 R3
	2. SUB R4 R1 R5
	Resulting x86 code
	1.	MOV Rtemp R2
	2.	ADD Rtemp R3
	3.	MOV R1 Rtemp
	4.	MOV Rtemp R1
	5.	SUB Rtemp R5
	6.	MOV R4 Rtemp
	Figure 18. Translation with unnecessary load instructions in lines 3 and 4,
	which are removed by the optimization process.

EM64T (Extended Memory 64-bit Technology) Intel's implementation of x86-64 architecture. It is used in newer versions of Pentium 4, Pentium D, Pentium Extreme Edition, Celeron D, Xeon, and Pentium Dual-Core processors, and in all versions of the Core

processors. 2 AMD64 (aka x86-64) is a 64-bit superset of the x86 instruction set architecture developed by AMD.

ELF (Executable and Linking Format / Extensible Linking Format) File standard for executables files, object code, shared libraries and core dumps


Yuval Peress
email: peress@cs.fsu.edu

Dr Ian Finlayson
email: finlayso@cs.fsu.edu

Dr Gary Tyson
email: tyson@cs.fsu.edu

David Whalley
email: whalley@cs.fsu.edu

David Whalley Crc

CRC: Protected LRU Algorithm

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Abstract

Additional on-chip transistors as well as more aggressive processors have led the way for an ever expanding memory hierarchy. Multi-core architectures often employ the use of a shared L3 cache to reduce accesses to off chip memory. Such memory structures often incur long latency (as much as 30 cycles in our framework) and are configured to retain sets as large as 16 way. A baseline replacement algorithm that has proven itself over and over again is the Least Recently Used (LRU) policy. This policy seeks to replace lines that were used least recently, which works well thanks to temporal locality. This paper seeks to improve on LRU by taking advantage of the 16 ways available to include a bias for replacement. By keeping track of the relative use of each lines, some frequently used lines may become "protected". By providing protection for such lines we have managed to reduce the miss rate to 62.89% from LRU's 70.08%. Using a memory reference trace, we also demonstrated that the best replacement algorithm, an oracle which knows about future accesses, could only provide a 58.80% miss rate for our benchmarks.

Framework

The Cache Replacement Competition (CRC) provides the competitors with a trace driven simulation environment. Competitors were provided access to the class structure holding meta-data and functions responsible for selecting the evicted line in each L3 cache set.

The competition can be subdivided into 2 phases: a single and multi core execution. The L3 Cache configuration maintains 16 way sets and 64 byte lines regardless of the number of cores, and allows for 1MB per core. In each phase, submissions are judged by the performance of the L3 cache replacement algorithm. Each submission is limited to 8 bits per cache line as well as 1 Kbits of global memory. Due to the long latency of the L3 and the low frequency of L3 cache accesses, algorithm complexity was not limited.

For our tests we chose 9 SPEC2006 [START_REF]Standard Performance Evaluation Corporation[END_REF] benchmarks (astar, bzip2, gcc, h264ref, hmmer, libquantum, mcf, perlbench, and sjeng). These benchmarks provided us with a large variety of L3 cache misses (capacity, conflict, and compulsory).

Exploring the LRU Algorithm

The most common cache replacement algorithms are based on the idea of Least Recently Used (LRU).

Here, the goal is to evict the lines that were accessed the longest time ago, because temporal locality tells us that they are unlikely to be needed again very soon. Algorithms in this family include the popular Pseudo-LRU, the LRU-K algorithm [START_REF] O'neil | The lru-k page replacement algorithm for database disk buffering[END_REF], and 2Q [START_REF] Johnson | 2q: A low overhead high performance buffer management replacement algorithm[END_REF]. Another common approach in cache replacement algorithms is to try and replace the lines that are Least Frequently Used (LFU). The idea here is that lines that have been used many times are likely to be needed again.

The LRU algorithm was provided with the CRC kit and was a natural starting point for our work. Each of our benchmarks was executed using the LRU algorithm and provided us with a list of hits/misses and replacements within the cache as well as a baseline miss rate (70.08%). Using these results we began scanning for patterns that might reveal shortcomings of the LRU algorithm. Such a pattern was revealed when a line was brought into the L3 cache for a single reference, evicting a line that was referenced many times before. The heavily referenced line was then brought back into the cache to be used in what must have been another loop or iteration of an outer loop.

For example, a memory address X was used N x times before being evicted by X ′ . X ′ was then only used a few times before X was brought back into the set. It is important to note that on the second appearance of X , it does not necessarily replace X ′ . Instead, it is possible for X ′ to remain in the set unused sim-1 ply because it was referenced recently. This pattern brings up an interesting question, "Should X be kept in memory for being accessed many times?"

There have been several attempts to create an improved cache replacement algorithm by combining the LRU and LFU concepts. In [START_REF] Lee | On the existence of a spectrum of policies that subsumes the least recently used (lru) and least frequently used (lfu) policies. SIGMETRICS Perform[END_REF] it is argued that there is a spectrum of cache replacement algorithms that include both least recently used and least frequently used based on how much weight is given to each policy. They use this weight to calculate a combined recency and frequency value for each line which is used in replacement decisions.

Another replacement algorithm that uses both recency and frequency is presented in [START_REF] Dybdahl | An lru-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches[END_REF]. Similar to our work, they identify a set of least recently used lines and, among those, choose to replace the line that is least frequently used. With each line they store a counter indicating the number of accesses to that line. Since our works are similar, it becomes important to note the differences. First, [START_REF] Dybdahl | An lru-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches[END_REF] uses both the LRU stack (4 bits) and an 8 bit counter value per line which would not fit in the CRC framework. Second, their work attempts to predict when caching a line is not necessary whereas our work will always cache a line that is fetched into the L3. Finally, and perhaps most importantly, their work first selects the N least recently used lines of which they select the least frequently used to replace. Our preliminary work revealed that more misses can be avoided if frequently used lines are given protection first. Assuming that 12 lines are to be given protection from eviction, [START_REF] Dybdahl | An lru-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches[END_REF] would select the least frequently used of the 4 least recently used lines. Such a scenario could end poorly if a phase of execution is about to repeat and all 4 lines will be needed again. Our algorithm would first protect such lines that were heavily used previously, and select a replacement from the remaining lines.

The LRU + Protected MUs

To further explore the questions above, an additional concept was added to each cache set: the MU (Most Used). The initial test used an arbitrarily large counter to keep count of the total number of references per memory address. This counter value was maintained in global memory space even while the memory references was evicted from the cache. The LRU algorithm was then augmented to never evict the 4 most used addresses within the set. Such a configuration provided us with a miss rate of 69.42% (0.94% lower than LRU alone).

Since such a design is unreasonable to implement in hardware, a second concept arose. In the second design, each cache line was augmented with an arbitrarily large counter. This counter was incremented on each access and zeroed when the line was replaced. The remaining algorithm was the same, when a line needed to be replaced the top 4 MU lines were removed from the list of LRU lines before selection. The new configuration provided an average miss rate of 67.83% (2.25% lower than LRU). As it turned out, keeping the counter around for too long resulted in the cache becoming polluted with lines that were accessed many times in a previous phase of execution becoming impossible to evict. The new results drove us to limit the counter size in hopes of further removing such stagnation in the cache and meeting the space requirements.

Replacing the original 64 bit global counter per memory address, the first configuration augmented the LRU algorithm (4 bits/line) with a 4 bit counter/line and protect the 4 MU lines during an eviction. This approach increased our miss rate from 67.83% to 67.89% (still beating LRU by 2.19%). Since this design appeared to be working well, more configurations were run, allowing for anywhere from 1 to 15 protected MU lines and anywhere from 3-5 bit counters (Figure 1). Of these, we found that the best configuration across the board was 14:3 (14 protected MU lines:3 bit counters), with an average miss rate of 62.89% (7.19% lower than LRU alone). While such a configuration provided the best average miss rate, a different approach reveals a different view. Since a single benchmark provided large gains for each additional MU, we wanted to find the best configuration without giving too much bias to a single benchmark. To do this, each benchmark's best performance configuration was listed: 7:3 (astar), 10:3 (bzip2), 10:3 (gcc), 14:3 (h264ref), 15:3 (hmmer), 15:3 (libquantum), 12:4 (mcf), 14:3 (sjeng). Using the unweighted average we find that the ideal configuration (rounded down) should be 12:3.

The 12:3 configuration provides a miss rate of 63.6% (6.48% lower than LRU alone) and costs 7 bits per line with no additional global data. The Figure 1: Hit rate of different LRU + Protected MU configurations first 4 bits are used to store the LRU stack position in a 16 way cache; the following 3 bits provide a counter with a max value of 7. LRU would now be kept as it was previously, with each access to a line simply shifting that line stack index to 0 and incrementing the stack locations that were below it so that the stack values may remain continuous. The additional counter will be incremented on each access to a cache line. If the counter ever rolls over, all the counters within the set are right shifted by 1. Such a divide by 2 approach helps preserve the top most used values, while not allowing such values to become stagnant between phases of execution. Since algorithm complexity is of no issue, the top 12 counter values (in our 12:3 configuration) are ignored when looking for a line to replace using a simple scan through. Instead, the LRU of the remaining 4 lines is evicted and its counter set to 0.

An interesting observation is found when looking at the addition of counter bits. On average between all benchmarks and each number of protected MUs, we find that the addition of the 4 th bit increases the miss rate by 0.12%, while the 5 th bit further increases the miss rate by 0.24%. Such data further supports the concept of stagnation within the protected MUs. The additional bits allowed cache lines to become so dominant within the set that they be-came hard or even impossible to evict once they became useless.

A final run was performed where each benchmark produced a trace of which memory addresses are accessed. On a following run of the benchmark, the trace is loaded and is used during line eviction. When a line needs to be replaced, the oracle scans through the trace using only references that have not been seen yet. The lines in the set are check off as each memory address is seen until only a single line is left. This final line is the one that needs to be replaced since it will not be used for the most number of cycles. Using this oracle we found that the best replacement we could expect for our benchmarks will provide a 58.80% miss rate.

For completeness, the execution of 4 threads was performed. The 4 threads were selected by which threads had the greatest standard deviation between all the configurations we ran (bzip2, gcc, hmmer, and libquantum). Configuration for the 4 threaded execution followed the parameters of the competition by increasing the L3 cache size from 1MB to 4MB and altering no other parameters. The results showed that gcc and hmmer both were aggressively competing for the protected slots such that below a threshold of 6 MU's a 1:5 configuration was best with an average miss rate of 59.95%. Once the threshold is met performance improves with each additional protected MU, our selected 12:3 configuration provided a 56.96% miss rate (4.07% lower than the 61.03% miss rate provided by LRU).

Conclusion

In this work we have demonstrated that with large sets, the LRU algorithm can be improved by accounting for use frequency. With only an additional 3 bits per line over LRU, we can protect lines which may have been referenced a long time ago but used many times before. To prevent stagnation of such counter based protection, the counter is limited to 3 bits and upon saturation all counters within the set are right shifted by 1.

We would also like to compare our results with [START_REF] Dybdahl | An lru-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches[END_REF] since the concepts driving both works are very similar. Unfortunately, [START_REF] Dybdahl | An lru-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches[END_REF] used an older set of benchmarks which have only a single benchmark in common with our work, mcf. In this benchmark, their best performing scheme performed at 1% improvement from LRU (translating to a rough miss rate of 91%), where as our worst submitted configuration achieved a miss rates of 86.36% (or a 6.23% improvement over LRU when scaled as in [START_REF] Dybdahl | An lru-based replacement algorithm augmented with frequency of access in shared chip-multiprocessor caches[END_REF]).

Using SPEC-INT CPU2006 benchmarks we have demonstrated that a 12:3 configured Protected LRU can achieve an average miss rates 6.48% lower than LRU alone and a 14:3 configuration further reduce the miss rate by 0.71%. We further demonstrated that additional counter bits adversely affect performance due to stagnation. If we were to normalize our results with the oracle performance; we would find that LRU's miss rate is 119.18%, while our configurations (10:3, 12:3, and 14:3) have 109.54%, 108.16%, and 106.96% miss rates respectively. While a 14:3 configuration did perform better under our benchmarks, we believe that a 12:3 configuration is more appropriate for general purpose applications. Our submission includes 10:3, 12:3, and 14:3 configurations.

Acknowledgements

This research was supported in part by NSF grants CNS-0615085 and CNS-0915926.