João Paulo Porto
email: jpporto@ic.unicamp.br

Guido Araujo

Edson Borin
email: edson.borin@intel.com

Youfeng Wu
email: youfeng.wu@intel.com

Trace Execution Automata in Dynamic Binary Translation

Keywords: D.3.4 [Processors]: Run-time environments Dynamic Binary Translation, Deterministic Finite Automaton, Trace Recording, Trace Replaying

Program performance can be dynamically improved by optimizing its frequent execution traces. Once traces are collected, they can be analyzed and optimized based on the dynamic information derived from the program's previous runs. The ability to record traces is thus central to any dynamic binary translation system. Recording traces, as well as loading them for use in different runs, requires code replication in order to represent the trace. This paper presents a novel technique which records execution traces by using an automaton called TEA (Trace Execution Automata). Contrary to other approaches, TEA stores traces implicitly, without the need to replicate execution code. TEA can also be used to simulate the trace execution in a separate environment, to store profile information about the generated traces, as well to instrument optimized versions of the traces.

In our experiments, we showed that TEA decreases memory needs to represent the traces (nearly 80% savings).

INTRODUCTION

Dynamic Binary Translators (DBTs) rely on information about the dynamic behavior of a program to improve its performance. This is done by detecting and optimizing, code fragments, known as hot code, which accounts for the largest share of the program execution time.

To detect hot code, a DBT might use a trace selection technique. Several techniques have been proposed in the literature [START_REF] Bala | Dynamo: a transparent dynamic optimization system[END_REF][START_REF] Cifuentes | Uqbt: Adaptable binary translation at low cost[END_REF][START_REF] Duesterwald | Software profiling for hot path prediction: less is more[END_REF][START_REF] Gal | Incremental dynamic code generation with trace trees[END_REF][START_REF] Porto | Compact trace trees in dynamic binary translators[END_REF] which address the same issue: how can hot code be easily detected (i.e. with the least possible overhead)? The description of such techniques, as well as their advantages or disadvantages are beyond the scope of this paper, which describes a technique to record and replay traces.

The Trace Execution Automata technique uses a Deterministic Finite Automaton (DFA) to map executing instructions to instructions or basic blocks in previously recorded traces. When operating in recording mode, our technique builds a DFA that represents basic blocks (or instructions) from traces. During the replay mode, the transition between instructions in the executing program are mapped to transitions in the DFA, which turns into a precise map from the currently executing instructions to the represented basic blocks (or instructions) in the DFA. We found this technique useful in multiple contexts, among them:

• Building traces in one system, e.g. by using a DBT, and collecting statistics and profiling information for them on a second system, e.g. by replaying the traces on a cycle accurate simulator.

• Building and profiling traces without the need for actual trace construction (e.g without the need for code replication, code linking and original code patching). This is useful when collecting accurate profiling information before the actual traces code is generated. It is also useful when investigating trace formation techniques because it enables us to focus on the trace formation techniques without concerning about the trace code compilation correctness.

• Storing trace shape and profiling information for reuse in future executions.

This paper is organized as follows. Section 2 presents a motivation for TEA. Section 3 discusses how traces and DFAs are related to each other and shows how to build DFAs out of traces. Section 4 describes our experimental evaluation of TEA. Section 5 lists the previous work on trace recording techniques. Finally, Section 6 concludes the paper and presents the future works.

MOTIVATION

Dynamic binary translation usually relies on dynamic profiling information to record and aggressively optimize traces.

In this section we show why collecting accurate profiling information before building the actual traces may be challenging.

The code on Figure 1(a) copies one hundred words from the array pointed to by esi to the array pointed to by edi. Although simple, this optimized code presents a challenge to runtime environments which could eventually optimize it:

(c) Trace After Unrolling Assuming that the code was executed, and the loop it contains was detected as hot code, the trace of Figure 1

(A) (B) (C) (D) (E) (F) (d) Duplicated Trace
(b) comes up.
With Algorithm 1 it is possible to create a DFA to simulate that trace's execution. That DFA can now be loaded into a profiling tool (such as our profiling tool described in Section 4) and the profile information for the traces can be gathered.

An obvious question we are yet to answer is why not collecting the profile information as the traces are recorded. The simple, straightforward answer is that it might be easier to implement the trace recording algorithm in an environment where gathering profile data is substantially harder than in another environment. In our experiment, recording the traces was easily done in our DBT environment [START_REF] Wang | Stardbt: An efficient multi-platform dynamic binary translation system[END_REF], whereas gathering profile information was easier under Pin [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF] as the profile code was ordinary C functions instead of assembly language stubs. Now, assume that traces are optimized using the profile information collected by replaying the DFA. For example, let's suppose the optimizer unrolled the trace by a factor of two as seen on Figure 1(c). There are now two options to determine the new profiling option.

The first option (the easy one) is to conservatively propagate the profiling information for the new instructions. For example, assume that instructions (3) and (4) in Figure 1 The second, hard option, is to recollect the profiling information. The DFA can not be used to simulate the unrolled loop. Since it does not generate specialized code, the state for the trace would find no corresponding executable code in the executable. However, it is possible to easily work around this: the trace can be duplicated instead of unrolled. The duplicated trace is shown in Figure 1(d).

The resulting DFA after the trace has been duplicated can be safely loaded alongside the original program for profiling. This new profile data can then be used after unrolling: instructions (C) and (D) in Figure 1(d) are the same as instructions ( 5) and (6) in Figure 1(c), thus the collected profile information can be used to optimize the unrolled loop.

With the new, specialized information the runtime can accurately optimize the code.

The use for the DFA in profiling can be thought as the ability to label duplicate instructions differently for every copy of it in the running program. Code duplication might arise from optimizations such as loop unrolling (as previously illustrated) and function inlining.

FROM TRACES TO TEA

In this section we illustrate the relationship between Traces and DFAs and provide an algorithm to build TEA out of traces.

Suppose that a runtime system that builds traces 1 using the MRET strategy [START_REF] Bala | Dynamo: a transparent dynamic optimization system[END_REF][START_REF] Duesterwald | Software profiling for hot path prediction: less is more[END_REF] is running the compiled code shown, as x86 assembly language, in Figure 2 (a). That piece of code scans a linked list structure pointed to by register edx and updates eax with the number of times that the value in ecx appears on the list.

1 the word trace will be used from now on as a synonym for hot traces

It might take a few iterations for the runtime system to identify the hot code and invoke the trace recording subsystem. The generated traces heavily depend on the trace selection strategy used as well as on the program's input data. Figure 2 (c) shows two traces (T1 and T2) that could eventually be recorded by using the MRET trace selection strategy. Trace T1 is formed by the basic blocks $$begin, $$header and $$next, while trace T2 is formed by the basic blocks $$inc and $$next.

In our examples, we use the format $$Ti.block when referring to a block that belongs to a trace. This format allow us to distinguish blocks that are duplicated (e.g. $$T1.next and $$T2.next) and avoid confusion with the original block name (e.g. $$next).

A trace, or a collection of traces, implicitly defines a DFA.

As an example, the DFA for traces on Figure 2 (c) can be seen on Figure 3 represent control flow between traces and cold code. We call the whole program DFA generated from the execution traces and the NTE state TEA. For this sample program, the TEA is represented on Figure 3 (b). The TEA is logically similar to the dynamic control flow graph (DCFG) for the traces seen Figure 2 (c). TEA, however, contains just the state information, whereas the DCFG contains code replication. TEA also models the whole program execution with the aid of the NTE state, while the DCFG only represents the hot code.

NTE $$next $$next $$header $$inc $$begin (a) $$next $$next $$header $$inc $$begin $$end $$begin (b) $$begin
The generated TEA can be used to replay trace executions without running actual trace code. As an example, we could re-execute the program at Figure 2 (a) on a different system and replay the MRET traces execution by feeding the program counter into the generated TEA. The TEA states provides an accurate mapping from the current program counter to the previously recorded traces. For instance, during the re-execution of the sample program, if the current program counter points to $$next we can precisely tell whether it corresponds to the execution of the original $$next, $$T1.next or $$T2.next by looking at the TEA current state.

The following two sections presents an algorithm that, given a set of traces, builds the corresponding TEA (Section 3.1) and provides some insights on how TEA can be used online to record traces (Section 3.2).

Building TEA out of Traces

The initial motivation for TEA was the ability to generate traces in one environment and to load and execute them in another. This simple problem becomes hard when the two different environments are extremely different. TEA enabled us to generate the traces in one system, and execute them on another system. Algorithm 1 shows how we converted the generated traces to TEA, but first, some definitions are needed.

Definition 1. A Basic Block (BB) is a sequence of instructions with a single entry point and a single exit point.

Usually a BB is terminated by a branch instruction. However, different runtime systems detect basic blocks differently. For instance, on Figure 2 (a) some runtime system might be able to identify block $$inc as a basic block, even though it does not end in a branch instruction. Usually, however, DBTs merge blocks $$inc and $$next. Notice that either way, Definition 1 correctly identifies BBs. Since each BB might be on several different traces and, depending on the recording algorithm, might appear several times on the same trace, there should be a way to uniquely identify each BB on the traces. The first step in Algorithm 1, lines 1 to 2, initializes the TEA with a single state (NTE) and an empty set of transitions. As discussed, the NTE state represents the execution of basic blocks (or instructions) that does not belong to traces. The next step, lines 3 to 5, adds the states to represent the TBBs. Since each TBB is unique, and exactly one state is created for each TBB, the resulting TEA has the following property:

Property 1. The resulting TEA is capable of representing the execution of every TBB. If the successor of the TBB is not a block in a trace, a transition from the TBB to NTE is added, representing a transition from the trace to cold code. Finally, it adds the edges between the state NTE and the TBBs, representing the start of traces execution (lines 15 to 17). Thus the following holds:

Property 2. The resulting TEA contains all transitions for every TBB represented.

Properties 1 and 2 ensure the resulting TEA models the exact behavior of the program's traces, thus proving the algorithm correctness.

Recording TEA instead of Traces

As previously mentioned, TEA can be used as a online technique for trace recording. It is built by Algorithm 2, which is invoked every time the running program finishes a TBB execution but before the next TBB is executed. Trace recording is expressed as a three-state State Machine. The possible states are "Initial", "Executing" and "Creating", each of which with its own well-defined rule.

State "Initial" is executed before the program starts its real execution. It simply sets up an empty TEA (i.e. a TEA with only the NTE state) and indicates that the program is in the "Executing" state.

In the "Executing" state the application is either running cold code or executing a previously created trace. Depend-

EXPERIMENTAL RESULTS

For this paper, our goals were (1) evaluating how TEA would decrease memory required to represent traces; (2) evaluating how effective TEA is for replaying previously recorded traces on unmodified program executables; and (3) to evaluate TEA's effectiveness as a trace recording tool itself. All the experiments were executed in Ubuntu 9.10 in a virtual machine running under Windows 7 in a Core i7 EE 975 with 12 GB of DDR3 1333 MHz DRAM. Our experimental setup included two different DBT frameworks, pin [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF] and StarDBT [START_REF] Wang | Stardbt: An efficient multi-platform dynamic binary translation system[END_REF].

Pin is a well-known runtime environment which allows programmers to develop their own profiling tool (called "pintools") composed of instrumentation and analysis routines. Pin offers a rich set of APIs that offers great flexibility. It is indeed a very important tool for binary translation experiments, among other uses. For this paper, we implemented a pintool that loads traces from a input file and uses the traces for program execution. Our tool is also capable of recording traces if they are not available prior to program execution.

StarDBT is a DBT runtime environment which translates IA-32 to IA-32. It is less flexible than Pin, but it offers a greater control over how instrumentation and analysis are done. It was used as a baseline for memory requirements to represent traces. The generated traces were also used by our pintool during the "trace replaying" experiment.

Table 1 shows the data regarding the size needed to represent the traces. We recorded traces using three different techniques (MRET, CTT and TT). traces [START_REF] Porto | Compact trace trees in dynamic binary translators[END_REF] showed that memory requirements for the three techniques were different from one another. We wanted to evaluate if TEA was sensitive to the technique. The columns labeled "DBT" indicate the memory requirements (in KB) to represent the recorded traces, whereas the columns "TEA" indicate the memory requirements (also in KB) to represent traces using TEA. The "Savings" column indicates the memory usage savings achieved by representing traces with TEA instead of the usual strategy (i.e. replicating the code) to be around 80%. TEA achieves this space savings by avoiding code specialization for trace representation.

Table 2 shows the runtime aspects of trace replaying. We again compare our TEA implementation in the Pintool against our "baseline", which are the StarDBT collected traces. The "coverage" columns show how much runtime instructions were executed inside the traces. The "time" column under TEA shows the amount of time needed to replay the traces in our pintool, and under DBT shows the amount of time needed to record the traces in DBT. Since the table displays information about trace replaying, it is expected that the coverage for TEA is slightly higher than DBT's coverage since our tool will execute less cold code. This is true for all but one benchmark: 177.mesa. The 0.2% difference in coverage on this particular benchmark occur since Pin and StarDBT use slightly different algorithm to detect individual instructions. Nevertheless, the results are close enough to be considered valid.

Regarding"Time", it is noticeable that TEA presents a some-what high overhead when compared to DBT's execution. There are at least two reasons for this difference. The first reason is the way Pin inserts the instrumentation code to manipulate the TEA. Usually, pin will insert function calls to the pintool's instrumentation routines, which adds considerable overhead to the program's execution. The other reason is related to TEA's transition function. Every branch instruction is proceeded by a call to a function that eventually searches for the target trace in some sort of data structure. By replicating code to represent the traces, DBT does not need a transition function. The results on this Table (as well as the ones on Table 3) were collected with an optimized transition function. The optimizations are described in Section 4.2.

Table 3 shows the data regarding to our experiment on TEA's ability to record traces. For this experiment, we implemented the MRET [START_REF] Duesterwald | Software profiling for hot path prediction: less is more[END_REF] trace strategy in our pintool. The columns in the table have the same meaning as they have on Table 2, except "Time" which means "recording time" for both Pin and DBT. Again, the recorded traces present a slightly different coverage and take more time to record. The reasons for the later are the same as the ones for the replaying experiment. The reasons for the former are the difference in how StarDBT and Pin count runtime instructions as well as subtle algorithm implementation differences.

Implementation Challenges

The most challenging issue faced during the experiments was related to how dynamic basic blocks are identified. Besides this heuristic, Pin also create dynamic basic blocks on some unexpected instructions (e.g. x86's cpuid) and instructions with REP prefixes. To address this issues, our pintool inserts the instrumentation code on the taken and fall through edges instead of at the beginning of the TBBs. This guarantees that our pintool will see the same transitions StarDBT saw during trace recording.

Another small issue is related to instruction count. StarDBT counts every instruction to be one instructions, even if it is an instruction with a REP prefix that will iterate some times. Pin, on the other hand, creates a loop for these instructions, and counts each instruction of each iteration as one instruction. For this reason, the number of dynamic instructions seen by StarDBT and Pin are slightly different. This is why Tables 2 and3 do not show instruction count, but coverage instead.

Analyzing TEA's Performance

The numbers presented in this paper show that our implementation of TEA poses a heavy overhead for programs. Before collecting these results, we experimented several different implementations for the transition function. This Section describes the changes our pintool underwent to improve its performance. 4) were not collected since the slowdown was over 2 orders of magnitude from the native execution.

Our first attempt to speed up the transition function was the global B+ tree. The results were interesting, but the overhead was still very high. Later, we implemented the local cache to avoid going to the global trace container every time the system needed to search for a trace. Again, the results improved over the previous data. This configuration ("Local / Global") was used to collect all the data for the Recording / Replaying experiment.

We also investigated whether or not the global B+ tree was important to the overall performance. The experimental data shows that, while the local cache is more important than the global B+ tree, the B+ tree is important as well.

A comparison between columns "No Global / Local" and "Global / Local" clearly indicates a performance improvement when using the more optimized global container. Particularly, GCC and Vortex experience a severe slowdowns without the global indexing structure.

The data on the "Empty" column report a counter intuitive result. Having no traces to simulate should be faster than having several traces. However, the numbers do make sense, as the transition function is optimized for the common case (i.e. executing hot code). TEA performs more work to switch to cold code than it does for hot code transitions. This run had the global B+ tree and did not have any local caches (local caches are pointless outside of traces in our implementation anyway).

PREVIOUS AND RELATED WORK

Traces are closely related to dynamic binary translation and dynamic compilation techniques. Suganuma et al. [START_REF] Suganuma | A region-based compilation technique for dynamic compilers[END_REF] presented a complex JIT compiler for a production level Java Virtual Machine. Unlike previous approaches, that used method boundaries for JITing, they implemented a multilevel compilation strategy and use dynamic compiler to dynamically form "regions", which are their runtime system's compilation unit. Zaleski et al. [START_REF] Zaleski | Yeti: a gradually extensible trace interpreter[END_REF] presented an extensible JIT compiler which uses traces as compilation units.

Several trace recording strategies exist on the literature. MFET 2 [START_REF] Cifuentes | Uqbt: Adaptable binary translation at low cost[END_REF] instruments edges in the dynamic program execution to detect frequently executed paths. MRET 3 [START_REF] Bala | Dynamo: a transparent dynamic optimization system[END_REF][START_REF] Duesterwald | Software profiling for hot path prediction: less is more[END_REF] instruments back edges only, thus posing less runtime overhead than MFET. TT 4 [START_REF] Gal | Incremental dynamic code generation with trace trees[END_REF] record traces which always end with a branch to an "anchor", generally a loop header.

CTT 5 [17] tries to address the code duplication experienced by TTs by allowing branch targets within a path to be any Another use for traces in JIT compilers is described by Gal et al. [START_REF] Gal | Trace-based just-in-time type specialization for dynamic languages[END_REF]. They use Trace Trees [START_REF] Gal | Incremental dynamic code generation with trace trees[END_REF] as compilation units for the SpiderMonkey JavaScript Virtual Machines. Besides all the complication in a JVM JIT compiler, the authors face more challenges since JavaScript is dynamically typed.

Besides those well-known uses, recently Wimmer et al. [START_REF] Wimmer | Phase detection using trace compilation[END_REF] used traces to perform phase detection. A program phase is identified when the created traces are stable (i.e., there is a low trace exit ratio). Whenever program execution start to take side exits more often, the program is said to be in an unstable (i.e. between phases).

Several well-known optimization systems have employed traces to capture program's code locality. Examples of these environments are Dynamo [START_REF] Bala | Dynamo: a transparent dynamic optimization system[END_REF], FX!32 [START_REF] Chernoff | Digital fx!32 running 32-bit x86 applications on alpha nt[END_REF] and the IA-32 Execution Layer [START_REF] Baraz | IA-32 execution layer: A two phase dynamic translator designed to support IA-32 applications on Itanium R -based systems[END_REF].

All the previously mentioned systems work with user mode code. More complicated DBT systems can translate system level code. For instance, DAISY [START_REF] Ebcioglu | Daisy: Dynamic compilation for 100% architectural compatibility[END_REF][START_REF] Ebcioglu | Daisy: dynamic compilation for 100% architectural compatibility[END_REF][START_REF] Ebcioglu | Optimizations and oracle parallelism with dynamic translation[END_REF][START_REF] Gschwind | Binary translation and architecture convergence issues for ibm system/390[END_REF] is a compatibility layer which translates PowerPC code to a underlying VLIW systems. The Transmeta CMS [START_REF] Dehnert | The transmeta code morphing TM software: using speculation, recovery, and adaptive retranslation to address real-life challenges[END_REF] is the compatibility layer on the top of the Crusoe [START_REF] Klaiber | The technology behind Crusoe T M processors[END_REF] micro processor. They both utilize some sort of trace recording to detect hot code.

Both system could have applied TEA as a tool for dynamic trace recording.

On the hardware side, traces have been used for high-bandwidth instruction fetch [START_REF] Rotenberg | Trace cache: a low latency approach to high bandwidth instruction fetching[END_REF]. The Pentium IV processor [START_REF] Friendly | Putting the fill unit to work: dynamic optimizations for trace cache microprocessors[END_REF] implements a trace cache. High-bandwidth instruction fetch is achieved since logically contiguous instructions in the instructions stream are placed adjacent to one another in the Trace Cache. This high-bandwidth cache was needed due to the high clock frequencies that processor achieved [START_REF] Sprangle | Increasing processor performance by implementing deeper pipelines[END_REF]. TEA is not related to trace caches since it does not require instructions to be contiguous on the instruction stream.

CONCLUSIONS AND FUTURE WORK

This paper presents TEA, a technique that uses Deterministic Finite Automata (DFA) to map executing instructions to instructions or basic blocks in previously recorded traces. We list multiple contexts in which TEA is useful and we discuss the implementation challenges and solutions when implementing TEA on StarDBT and Pin frameworks.

Our experimental results show that the resulting TEA's transition lookup operation plays a fundamental role on TEA's performance. For this paper, we implemented the lookup operation with the help of a auxiliary look up data structures, which is searched whenever there is a transition from cold code to hot cold, or when there is a transition from one trace to another. In the future, we will investigate other techniques to optimize the transition lookup operation and amortize TEA's cost.

Figure 1 :

 1 Figure 1: Code Snippet and Resulting Traces

Figure 2 :

 2 Figure 2: (a) Sample code. (b) CFG for the sample code. (c) MRET traces.

  (a). Each node in the DFA represents a basic block that is part of a trace. The transitions between nodes represent the control flow in the traces. The label in a transition indicates the address, or the Program Counter, that triggers such transition. Notice that the automaton for the trace does not contain the transition from $$T1.begin to $$end. This happens because basic block $$end does not belong to any trace, therefore this transition does not represent control flow inside or between traces.Suppose that the traces at Figure2 (c) represents all the hot code for the sample program. To generate a DFA for the whole program all transitions must be accounted by the automaton, including transitions to and from hot code. To model this whole program DFA, a special state labeled NTE, which stands for No Trace being Executed, is generated. The program is on the NTE state whenever it is not executing any trace. Transitions from NTE to traces are labeled with the traces' start addresses. Transitions from traces to NTE

Figure 3 :

 3 Figure 3: (a) DFA for MRET traces. (b) TEA for whole program.

Definition 2 .

 2 A Trace Basic Block (TBB) is an instance of a BB in a trace. Each occurrence of a BB will generate a unique TBB. Given Definition 2, even if BB b occurs several times in the set of traces of a program, it is possible to distinguish between the different instances of b. As an example, Figure 2 (c) shows two MRET traces, T1 and T2, with two different instances of BB $$next: $$T1.next and $$T2.next. Definition 3. A Trace is a collection of TBBs and the control flow edges between them. Definition 3 encompasses many different kinds of traces, from traces made of superblocks to Trace Trees. With the previous definitions, it is possible to explain Algorithm 1 and to prove its correctness.

Algorithm 1 :

 1 Converting Traces to TEA Input: Ts: The set of Traces in a Program Output: TEA: the TEA

Algorithm 2 :

 2 Using TEA to Record Traces Input: Current: The TBB Previously Executed Input: Next: The Next TBB to be Executed Input: State: The Recording Algorithm's Current state

	1 switch State do
	2	case Initial
	3	InitializeTEA(TEA)
	4	State ← Executing
	5	case Executing
	6	ChangeState(TEA, Current, Next)
	7	if TriggerTraceRecording(Current, Next) then
	8	StartCreatingTrace(Current, Next)
	9	State ← Creating
	10	case Creating
	11	AddTBBToTrace(Current, Next)
	12	if DoneTraceRecording(Current, Next) then
	13	FinishTrace(Current, Next)
	14	State ← Executing
	ing on the trace recording rules (line 7) the state machine
	switches to the "Creating" state.

Trace recording takes place in the "Creating" state. Again, depending on the algorithm being used for trace selection, the state machine decides whether or not to end trace recording (line 12).

Table 1 :

 1 Size Savings with TEA

	Our previous paper on

Table 2 :

 2 TEA Runtime Aspects -Replaying identifies a TBB as starting at an address which is target of a branching instruction and ending in a branch instruction.

	StarDBT

Table 4

 4

	contains six different entries for each benchmark.
	The first column ("Native") indicates the native performance

Table 3 :

 3 TEA Runtime Aspects -Recording numbers for the benchmarks. For each benchmark, every entry is normalized with respect to this value, thus all entries in this column being 1.00.

	The remaining five entries are all related to program exe-
	cution under Pin. The column "Without Pintool" indicates
	the slowdown of running the benchmark under Pin without
	any pintool loaded. In other words, it indicates Pin's over-
	head alone, which turned out to be low. Column "Empty"
	reports the overhead to run the application with TEA with
	an empty set of traces. For these numbers, no traces were
	recorded by our Pintool at runtime.
	The remaining three columns report the results for load-
	ing and replaying traces under three different scenarios. For
	each benchmark, every experiment use the same set of traces.
	Column "No Global / Local" indicates that a local cache was
	used to speed up transitions from one trace to another while
	no auxiliary data structures were used to speed up trace
	look up (the traces were kept in a linked list) when the local
	cache misses. The "Global / No Local" experiment used the
	global B+ tree to speed up trace look up, while no local
	caching scheme was employed. The last column, "Global /
	Local", shows the results when both the global B+ tree and
	the local cache were used.
	The auxiliary structures are very important in the TEA's
	transition function, which is the responsible for most of
	TEA's overhead. In fact, the first TEA implementation em-
	ployed no auxiliary data structures for speeding up trace

Table 4 :

 4 TEA Overhead for Various Configurations look up. The numbers for this particular experiment (which would be the "No Global / No Local" column in Table

2

  Most Frequently Executed Tail 3 Most Recently Executed Tail 4 Trace Trees 5 Compact Trace Trees loop header in that path.


Hongliang Gao
email: hongliang.gao@intel.com

Chris Wilkerson
email: chris.wilkerson@intel.com

A Dueling Segmented LRU Replacement Algorithm with Adaptive Bypassing

In this paper we present a high performance cache replacement algorithm called Dueling Segmented LRU replacement algorithm with adaptive Bypassing (DSB). The base algorithm is Segmented LRU (SLRU) replacement algorithm originally proposed for disk cache management. We introduce three enhancements to the base SLRU algorithm. First, a newly allocated line could be randomly promoted for better protection. Second, an aging algorithm is used to remove stale cache lines. Most importantly, we propose a novel scheme to track whether cache bypassing is effective. Based on the tracking results, we can adaptively adjust bypassing to fit workload behavior. DSB algorithm is implemented with a policy selector to dynamically select two variants of SLRU algorithms with different enhancements.

Introduction

This paper describes a Dueling Segmented LRU replacement algorithm with adaptive Bypassing, referred to DSB in the paper. The base Segmented LRU (SLRU) algorithm is described in Section 2. We propose two simple enhancements to SLRU algorithm described in Section 3. In Section 4, we discuss our proposed adaptive bypassing algorithm that prevents the allocation of cache lines under certain circumstances. DSB is implemented with a policy selector, described in Section 5, which enables DSB to adaptively select between two variants of SLRU depending on application behavior.

In Section 6, we describe implementation cost and configurations of our algorithm. Section 7 presents performance results of the proposed algorithm.

Segmented LRU Algorithm

SLRU algorithm was originally proposed in [START_REF] Karedla | Caching Strategies to Improve Disk System Performance[END_REF] as a cache management algorithm for disk system. In this paper, we apply it as a processor cache replacement algorithm. The base SLRU algorithm augments each cache line with a reference bit dividing up the traditional LRU list of cache lines into two logical sub lists, the referenced list and the non-referenced list. The referenced-list consists of cache lines with the referenced bit set, and the non-referenced-list consists of the remainder of the cache lines. When choosing a line for replacement the LRU cache line in the non-referenced list is selected first. If all cache lines are in the referenced-list then we select the global LRU cache line from among all the cache lines in the set.

We propose three enhancements to the SLRU algorithm in this paper. By selecting which enhancements are used, we can get different variants of the SLRU algorithm. Our selected variants are described in Section 6.

SLRU with Random Promotion and Aging

Traditional implementations of SLRU mark the reference bit when a cache line is referenced, but previous work has shown benefit to making selected random promotions as well [START_REF] Qureshi | Adaptive Insertion Policies for High Performance Caching[END_REF]. The random promotion in the SLRU algorithm allows the reference bit to be randomly set for newly allocated cache lines. For example, if promotion probability is 1/32, then 1 in 32 newly allocated lines will be promoted by marking its reference bit.

Another enhancement to SLRU is an aging mechanism to allow lines in the referenced list to be aged or removed from the reference list. When a cache line is allocated the reference bit of the LRU element is cleared. We refer to the process of clearing the reference bit as aging.

SLRU with Adaptive Bypassing

The third enhancement to SLRU is our adaptive bypassing algorithm which prevents the allocation of lines in the cache under certain conditions. Although we only apply it to SLRU in this paper, it can be coupled with other replacement algorithms as well. Our experiment results have shown that it is also helpful for various other replacement algorithms.

The decision on whether or not to bypass the cache is made by bypass tracking logic implemented for each set in the cache. The bypassing logic evaluates the impact that a bypassing decision would have on the performance of the cache.

On each cache miss, we can choose to bypass the cache and keep the selected victim or we can replace the victim with the new line. The selected victim and new line are essentially competitors for the available cache line. Our scheme allows us to measure which of these two lines is more useful and to adjust the bypass algorithm accordingly.

When a line is selected to bypass the cache, we would like to assess the impact that the decision to bypass the line will have on the hit rate of the set. The decision to bypass is evaluated by storing the tag of the bypassed line in a field we refer to as competitor tag. In addition, we store a pointer to the tag of the victim line referred as competitor way. It is the line that would have been replaced without bypassing. Subsequent references to the set are compared against the tag of the bypassed line and the tag of the competitor way. We interpret a reference to the competitor way before the bypassed line as an indication of an effective bypass. Conversely, a reference to the bypassed line before the competitor way is treated as an indication of an ineffective bypass. After we detect whether a bypass is effective/ineffective, we increase/decrease the bypassing probability.

In some cases we may make a decision not to bypass a given cache line. In order to assess the impact of bypassing in this case, we randomly select some newly allocated lines as "virtually bypassing" the cache. The line is still allocated in the cache. Instead, a decision is made to evict the victim line. The decision not to bypass is evaluated in much the same way as the decision to bypass. A pointer to the tag of the allocated line, the virtually bypassed line in this case, is stored as well as a copy of the tag of the evicted line, the victim line in this case. The references to each of these are tracked and treated similarly as described for the decision to bypass.

Our bypass algorithm randomly selects newly allocated cache lines for bypassing. The probability of making the bypass is determined by how effective the decisions to bypass have been in the past as described above. Each effective bypass doubles the probability that a future a bypass will occur, for example, if the current probability is 0.25 the probability will double to 0.5. Similarly each ineffective bypass halves the probability of a future bypass, for example, cutting the current probability of 0.5 to 0.25. For virtual bypassing, we use a fixed probability.

The minimum bypassing probability is set to 0 that will prevent any bypassing and allocate all missed lines. Note that even if the probability is adjusted to 0, we can still track effectiveness of bypassing through virtual bypassing, which could turn on bypassing later if program behavior changes to favor bypassing. The maximum bypassing probability is set to 1, which will essentially bypass all cache misses until the tracking scheme detects ineffective bypassing decisions.

Policy Selector

Our design allows 2 dueling replacement algorithms to be evaluated concurrently, and uses a policy selector to select between the 2 algorithms. For example, traditional LRU and SLRU replacement polices could be evaluated and the policy selector will attempt to select the policy that is most appropriate for the application that is being run.

The policy selector uses set sampling [START_REF] Qureshi | Adaptive Insertion Policies for High Performance Caching[END_REF][3]. The sampled sets are chosen statically by the algorithm proposed in [START_REF] Qureshi | A case for MLP-aware cache replacement[END_REF] and do not vary during the execution of the workload. We augment each of these sets with an auxiliary tag directory (ATD) [START_REF] Qureshi | A case for MLP-aware cache replacement[END_REF] to concurrently implement both dueling policies (policy A, policy B) for these sets. In addition, we use a saturating counter (policy selector counter) to track the performance of policy A & B in the sampled sets.

Each reference to the sampled sets will result in an update to the saturating counter only if policy A & B yield different results. For example, if policy A & B are either both hit or miss, the policy selector counter is not updated.

On the other hand, if policy A is a miss and policy B is a hit, the policy selector counter is incremented. Conversely, if policy A produces a hit but policy B misses the policy selector counter is decremented.

Hardware Cost and Complexity

For a 16-way associative cache, the base SLRU algorithm requires 5 bits per cache line to implement. Four bits are used to implement the true LRU stack and 1 bit is used to mark lines belonging to the referenced list.

Aging do not require extra storage in the cache. Random promotion shares the random generator used in adaptive bypassing logic.

The adaptive bypassing logic requires 22 bits per cache set. First, the competitor tag is used to store the lower 16 tag bits of the tracked line. The competitor way needs 4 bits in a 16-way cache. There are two other 1-bit fields to record the status of tracking. Competitor valid bit is used to mark whether the competitor way is still valid. We set this bit when start tracking a bypassing and clear it when the competitor way is selected as the victim or we have reached a decision of whether the bypassing is effective or ineffective. Virtual bypassing bit is the indication of whether current tracked bypassing is a result of real or virtual bypassing.

The storage cost of policy selector is mainly consumed by ATD. In our configuration, the ATD includes a sampled set to track for every 32 cache sets. Each sampled set has separated tags and replacement states for each policy. Similar as earlier proposals for dynamic policy selection [START_REF] Subramanian | Adaptive Caches: Effective Shaping of Cache Behavior to Workloads[END_REF], we use 16-bit partial tags in ATD. So each set has (16-bit tag + 1-bit valid) * 16 ways * 2 policies = 544 bits. To support two variants of SLRU algorithms, we need storage for replacement state in each set for both policies. Depending on whether bypassing is enabled, the cost of replacement state is 80 bits (without adaptive bypassing) or 102 bits (with adaptive bypassing) per set for each policy.

Besides hardware cost mentioned above, there are several registers used for adaptation. An 11 bit saturating counter is used for policy selection. The bypassing probability is determined by a 4-bit register per policy to select a probability among 14 predetermined choices: 0 and 1/2 K (K ranges from 0 to 12). Random numbers are needed for random promotion and adaptive bypassing. In this paper, we use a 32-bit Linear Feedback Shift Register (LFSR) as the random number generator.

In our submission to the 1 st JILP Cache Replacement Championship (CRC1) [START_REF]1st JILP Workshop on Computer Architecture Competitions (JWAC-1): Cache Replacement Championship[END_REF], we include three representative configurations of the DSB algorithm as described in Table 1. All configurations are composed with two variants of SLRU algorithms and adaptive bypassing support. The total hardware cost of CONFIG3 is summarized in Table 2. CONFIG2 has the same cost as CONFIG3. CONFIG1 has smaller cost since bypassing is disabled in one policy so that only one policy in ATD requires extra storage to support bypassing. As shown in Table 2, the total storage cost of our proposed algorithm is less than CRC1's budget for both single thread and multi-thread tracks.

Results

In order to cover a large variant of program behaviors, we tuned our algorithm with 47 SPEC CPU2006 traces. These traces are picked based on their sensitivity to different cache replacement algorithms from 148 SPEC CPU 2006 traces with different inputs and simulation points. Due to the limited space, we only report results of 15 of these traces in this section. These 15 traces are selected based on the criteria that more than 1% performance could be achieved when increase LLC capacity from 1M to 2M with true LRU replacement algorithm. These traces are simulated for 100M instructions after skipping 40B instructions.

Using the DSB configurations shown in Table 1, LLC miss rates (measured in MPKI reduction compared to true LRU) are shown in Figure 1. Figure 2 gives performance speedups of the selected traces with true LRU as the baseline. As shown in the figures, the proposed algorithm achieves significant higher performance than true LRU. Among the 15 traces, only two traces (zeusmp and soplex) show performance degradation and the maximum degradation is relatively small (-2%). The overall performance improvements are 7.7%, 8.6% and 8.4% respectively for CONFIG1, CONFIG2 and CONFIG3. Among the three enhancements proposed in this paper, adaptive bypassing contributes to majority of the performance gain over true LRU. Without bypassing, performance gains of all three configurations drop to about 2.7%. We also observe significant performance improvement from adaptive bypassing in single policy algorithms. For example, a true LRU algorithm with adaptive bypassing has 6.9% performance gain.

Figure 1 .Figure 2 .

 12 Figure 1. MPKI reductions compared to true LRU

Table 1 . DSB Configurations

 1

		CONFIG	CONFIG	CONFIG
		1	2	3
	Enable bypassing	True	True	True
	for policy0
	Enable bypassing	False	True	True
	for policy1
	Random promotion	0	0	0
	probability for
	policy0
	Random promotion	0	0	16
	probability for
	policy1
	Aging for policy0	0	0	0
	Aging for policy1	1	1	1
	Virtual bypassing	16	8	8
	probability
	Initial bypassing	64	64	8
	probability
	Second minimum	1/256	1/4096	1/4096
	bypassing
	probability
	(minimum is 0)

Table 2 . Hardware Cost (bits)

 2

		Single-core	Multi-core track
		track
	# of cache sets	1k	4k
	# bits for SLRU per	5	5
	cache line
	# bits for bypassing	22	22
	per cache set
	Total cost of a set	5*16+22 = 102	5*16+22=102
	# bits per ATD set	544+102*2 =	544+102*2 =
		748	748
	# of sets in ATD	32	128
	Total cost of ATD	748*32=23.4k	748*128=93.5k
	LFSR	32	32
	Policy selection	11	11
	counter
	Bypassing probability	4*2 = 8	4*2 = 8
	register
	Total DSB Cost	102*1k+23.4k+	102*4k+93.5k+
		32+11+8 =	32+11+8 =
		125.4K	501.5k


Liqiang He
email: liqiang@imu.edu.cn

Yan Sun

Chaozhong Zhang

Adaptive Subset Based Replacement Policy for High Performance Caching

An Adaptive Subset Based Replacement Policy (ASRP) is proposed in this paper. In ASRP policy, each set in Last-Level Cache (LLC) is divided into multiple subsets, and one subset is active and others are inactive at a given time. The victim block for a miss is only chosen from the active subset using LRU policy. A counter in each set records the cache misses in the set during a period of time. When the value of the counter is greater than a threshold, the active subset is changed to the neighbor one. To adapt the program behavior changing, set dueling is used to choose a threshold from different thresholds according to which one causes the least number of misses in the sampling sets. Using the given framework for this competition our ASRP policy gets a geometric average of improvement over LRU by 4.5% for 28 SPEC CPU 2006 programs and some programs gain improvements up to 50%.

Introduction

Cache replacement policy plays an important role in a cache design. The Least Recently Used (LRU) policy has been widely adapted in a microprocessor for the past decades. Recently progresses in this research topic include [START_REF] Perelman | Using simpoint for accurate and efficient simulation[END_REF][START_REF] Beckmann | ASR: Adaptive selective replication for CMP caches[END_REF][START_REF] Qureshi | Adaptive insertion policies for high-performance caching[END_REF][START_REF] Qureshi | A case for MLP-aware cache replacement[END_REF][START_REF] Kharbutli | Counter-Based Cache Replacement and Bypassing Algorithms[END_REF][START_REF] Liu | Cache Bursts: A New Approach for Eliminating Dead Blocks and Increasing Cache Efficiency[END_REF][START_REF] Zahran | Cache Replacement Policy Revisited[END_REF][START_REF] Zahran | Adaptive Block Placement Policy for Cache Hierarchies[END_REF][START_REF] Zhang | Divide-and-Conquer: A Bubble Replacement for Low Level Caches[END_REF][START_REF] Jeong | Cost-sensitive cache replacement algorithms[END_REF].

In this paper, we first propose a Subset Based Replacement Policy (SRP) for high performance caching. The idea is to divide one cache set into multiple subsets and victims are always taken from one active subset at a miss occurring. The reason of dividing is trying to maintain a longer access history through keeping part of the history in a group of blocks in the subset and make the cache more accurately captures the most frequently access blocks. And each subset maintains its own local LRU stack. On a cache miss, the incoming block is put into the local LRU position. And on a cache hit, the block is moved to the Most Recently Used (MRU) position like in LRU policy. The active subset periodically changes based on a count of misses to the set. To adapt the program behavior's changing, we further propose an Adaptive Subset Based Replacement Policy (ASRP) which uses a set dueling [START_REF] Qureshi | Adaptive insertion policies for high-performance caching[END_REF] technique to dynamically select a threshold from a pool of thresholds according to which one causes fewest misses in the sampling sets. Compare with LRU policy, ASRP obtains a 4.5% of geometric average miss reduction for 28 SPEC CPU 2006 programs, and some programs gain miss reductions up to 50%.

Experimental Methodology

We use the framework provided by this competition to do our experiments. All the simulations are done for a single-core processor. The details of the cache configurations are shown in Table 1.

Table 1. Baseline system configuration. We select 28 SPEC CPU 2006 benchmarks in our experiment. The cache access traces are obtained using Pin [START_REF]Pin -Dyn mic Bin ry Instrument tion Tool A a a a[END_REF]. All the programs are simulated for 100M instructions after fast forwarding 40 billion instructions.

Subset Based Replacement Policy

Motivation

Cache replacement policy tries to keep the best blocks in a set in order to contribute maximum number of hits for the future accesses. Traditional LRU brings an incoming block directly to the MRU position and assumes that the block has the highest probability to be used again in the future. Such policy is good for workloads whose working sets are smaller than the available cache size or for workloads that have high temporal locality.

When the working set is greater than the cache capacity, the frequently used blocks in LRU policy can be easily evicted from LRU stack by less frequently used blocks or even by other frequently used blocks when it suffers a cache-thrashing problem. At this case, [START_REF] Qureshi | Adaptive insertion policies for high-performance caching[END_REF] points out that cache performance can be improved by retaining some fraction of the working set long enough that at least that fraction of the working set contributes to cache hits. Our Subset Based Replacement Policy (SRP) is a new method to adopt this idea.

Subset based replacement policy

Pierre [START_REF] Michaud | Exploiting the cache capacity of a single-chip multi-core processor with execution migration[END_REF] shows that thread migration can boost the performance of single program through exploiting the total cache capacity in multicore processor. The analysis result inspires us that grouping a cache (each group likes a private cache in a core) and keeping part of accessed blocks in a group (like the cache in a core where the program does not run) may also help to reduce the misses of a program. To do this, partition is a normally used scheme. The SRP policy we propose in this section is an adoption of this scheme.

In SRP, we evenly divide one set into multiple subsets. At a given time, only one subset is active which can accept the incoming block. A local LRU stack same as in LRU policy is maintained among the blocks in the subset. On a cache miss, victim is the least recently used block in the active subset, and the incoming block is not moved to local MRU position. And a cache hit will move the block into the local MRU position in the corresponding subset no matter it is active or not.

Fig. 1 explains the rationale. If a block B brought by the miss m i-1 is not accessed again before the new miss m i occurs, then the new incoming block B' will replace B. But if it is accessed, such as the sequence of m k , h k , m k+1 , miss m K+1 will replace the block by m k-1 instead of the block K by m k because K has been moved the local MRU position in h k . And for a same reason, if an access h i+1 hits a block H which was brought by a missed access m i+1 in a non-active subset, H will not be replaced when the subset changes to active.

As shown in Fig. 1, the active subset changing in SRP policy is based on a count of misses to the set.

When the misses are more than a threshold X, the active subset is changed to the neighbor one. In another word, we force up to X consecutive misses only replacing the blocks in the active subset, and keep the blocks in other subsets who were brought into the set before the X misses staying the cache. For a set with N subsets, it must after (N-1)*X misses that a subset can change to active again, and during that period of time the blocks can stay in the subset without being replaced. So a greater value of X, a longer time that the blocks in non-active subsets can be kept in the set thus a more possibility that an old block in the subsets contributes to a hit if it is accessed again. As an example in Fig. 2, a 4-ways cache set is divided into two subsets, and each subset contains two blocks. Subset 0 is set to active at initialization. The threshold of changing active subset is 4. From the figure, our SRP policy has 3 more hits than LRU policy. Keeping the replacement occurring in the active subset during the four misses potentially lengthen the window of access history thus some prior accessed blocks, block 1, 4 and 5 (accessed again after six or five consecutive misses) for example, can stay in the set and contribute to the hits for the future accesses. On the contrary, the LRU evicts a block if it is not accessed again during a four consecutive misses which is less than the history window stored in SRP policy and causes new miss in the future.

Hardware implementation

The hardware structure of SRP policy is shown in Fig. 3. For a 16-ways last-level cache (LLC) used in this championship, each set is evenly divided into four subsets. A dedicated 2bits active_group counter in the set points to the active subset and the other subsets are inactive. Another set_miss counter is used to count the number of misses during a period of time. When the value is greater than the value (all sets use the same value) in the global threshold register, the active subset is moved to the neighbor one. In our design, we experientially set the set_miss as a 7 bits counter. At initialization time, the active_group and set_miss counters are set to zero, and the value in threshold register is set to an experiential value, 4 for example.

Case study of thrashing workload

Fig. 4 shows the cache access pattern of xalancbmk in an arbitrary selected set, No. 513, represented by the unique block address. The Fig. 4a is the whole picture of the accessing which has a very regular pattern, but the working set (approximate 35 blocks) is greater than the cache capacity, 16, thus causing a thrashing problem. And the Fig. 4b is a zoom in snapshot of the first two hundreds accesses. It shows that the frequently accessed blocks express a cyclic pattern.

For such workload, at a cache miss happening SRP uses the LRU block in the active subset as a victim, and keep the other blocks staying in the cache. It assumes that the new incoming block will not be used again in the near future because of the big working set and limited cache size, and hopes the other blocks being retained in the cache can contribute hits for future accesses. When a block has a hit in a subset (no matter it is active or not), it is moved to MRU position of the subset thus the future replacement will select other LRU block if the subset is active at that moment. Through the LRU replacing on miss and MRU placing on hit, the cache can potentially hold maximum number of the frequently used blocks with the limited space. SRP uses a threshold to control the frequency of active subset changing. A bigger threshold value, a less frequent changing of the active subset thus the more possible is the older blocks can stay in the cache. On the contrary, a smaller threshold value, a more frequent changing the active subset thus having more chance to select victim from multiple LRU blocks in different subsets and letting each LRU block staying in the cache longer than at the case with a bigger threshold.

Case study of LRU-friendly workload

Fig. 6 shows the unique block addresses accessed by a LRU-friendly workload, GemsFDTD, in set 513.

The whole trace in Fig. 6a shows the working set is much greater than the available cache capacity, but the zoom in figure, Fig. 6b, shows that most of the block reuses are very close (high temporal locality) which favors the traditional LRU policy.

For GemsFDTD, for each miss SRP inserts the incoming block to the LRU position which causes the block to be evicted by the near future incoming block and increases the number of misses. Fig. 7 shows the varying of cache performance of GemsFDTD with the threshold. Same as in Fig. 5, SRP is sensitive to the threshold value. Due to the LRU insertion policy, SRP gets more cache misses than LRU at any threshold settings.

Result

Fig. 8 shows the cache performance of SRP policy for 28 benchmarks on three different threshold values. For five benchmarks, astar, cactusADM, hmmer, sphinx3, and xalancbmk, SRP obtains significant over LRU policy. At the best case, hmmer, SRP reduces the cache misses up to 60%. The geometric average speedup of 28 programs is 4% over LRU. Among them, six programs get worse performances than LRU.

Fig. 8 also shows that different programs have different sensitivities to the threshold varying. For three of the improved programs , astar, sphinx3, and xalancbmk, the cache performance are improved with the threshold increasing, whereas for some other programs, bzip2 and GemsFDTD for example, the cache performances get worse when the threshold is increased.

Adaptive Subset Based Replacement Policy

In last section, fig. 5 and7 show that SRP policy gets different cache performances with the threshold varying. There isn't a threshold that can get best performance for all the programs. To adapt the diversity of programs and the behavior changing inside a program itself, we propose an Adaptive Subset Based Replacement Policy (ASRP) which uses set dueling [START_REF] Qureshi | Adaptive insertion policies for high-performance caching[END_REF] to dynamically select one threshold from eight candidates according to which one causes fewest misses in the sampling sets. In ASRP, the block insertion on a miss and block moving on a hit are same as in SRP policy, so we only present the dynamic threshold sampling mechanism in this section.

Dynamic sampling mechanism

We use a set dueling technique to dynamically select one threshold from a pool of thresholds according to which one causes fewest misses in the sampling sets. The rationale is shown in Fig. 9.

Through experiments, we found that the maximum value of the threshold could be selected for a cache is 128. A threshold that is bigger than 128 always has a similar or worse performance than 128 (see Fig. 5 and7). So in our ASRP policy, we pick eight different thresholds that are 1, 2, 4, 8, 16, 32, 64, and 128. Each threshold has four dedicated sampling sets who use the threshold and not changed forever, thus totally 32 sets are sampling sets and they are evenly distributed in the cache. The other sets in the cache are follower sets whose thresholds are selected dynamically at each time of cache miss.

Hardware implementation

Fig. 9 shows the implementation of our ASRP policy. In each set, a 4 bits flag indicates whether a set is a sampling set or a follower set. Only nine values are used that corresponds to eight thresholds and follower set. In addition, eight miss_counter_group_N registers are used to count the number of misses in the sampling sets. If a cache miss happens in a sampling set, the corresponding miss_counter_group_N is incremented by one. As shown in Fig. 10, when a miss happens in a follower set, the eight numbers in the miss_counter_group_N registers are read out, and the smallest value is selected to pick the corresponding threshold from the eight thresholds. Once the dynamic threshold is obtained, the cache set where the miss happens can use it to guide the active subset changing as in SRP policy. For the sampling set, it can use the dedicated fixed threshold to do the active subset alteration.

Resetting mechanism

The value in the miss_counter_group_N will continuously increase with the misses in the sampling sets. If during a period of time, one threshold, say X, causes much more misses in the corresponding sampling sets, then the value in miss_counter_group_X will be much greater than the values in other registers. For that duration, a follower set can successfully select a small value in the registers to do the active subset alteration. After that, if the program behavior changes, now the threshold X causes fewest misses in the sampling sets, but it can not be selected by the follower set due to the accumulative big value in the register in previous duration.

To solve this problem, we introduce two registers for the whole cache, last_follow and global_follow. The last_follow records which threshold is selected by last cache miss in a follower set, and the global_follow records the times of a same threshold selected by follower sets. So if a threshold selected by a follower set on a cache miss is same as the threshold selected last time by no matter the same set or not, the global_follow is incremented by one. Otherwise, the global_follow is decremented by one. To avoid the accumulative effect, when the value of global_follow is greater than a predefined number, 4096 in our policy, all the miss_counter_group_N registers are reset to zero, and our policy starts a new sampling process for the future misses.

Budget

The hardware budget of ASRP policy is computed as follows:

3 bits last_follow // corresponding to 8 thres. + 12 bits global_follow // the max. value is 4096 + 8 * 32 bits miss_counter_group_N + (2 bits active_group * 1024 sets) + (7 bits set_miss * 1024 sets) + 7 bits threshold // the max. threshold is 128 + (4 bits flag * 1024 sets) // sample or follower + (2 bits * 16K lines) // local LRU stack = 13590 bits + 32K bits = 45K bits Our ASRP policy only needs 70% of the hardware budget of LRU policy, and only 35% of the total budget provided in this championship.

Result

Fig. 11 shows the cache performance of ASRP policy in a single core with a 1MB 16-ways LLC. Our policy gets a geometric average speedup of 4.5% over LRU for 28 SPEC CPU 2006 benchmarks, and some programs (astar, hmmer, and xalancbmk) gain about 50% of improvements. Comparing with DIP, our policy gets better performance for most of the benchmarks. Fig. 12 shows that the cache performances of ASRP policy are very close to the best cases of SRP policy which means the sampling mechanism does help ASRP to find the best thresholds for different programs.

Conclusion

In this paper, we firstly propose a subset based replacement policy for the last level cache. It uses one subset to receive incoming block during a period of time and keeps other blocks staying in the cache and contributing hits for future accesses. A threshold is used to control the frequency of active subset changing. Next, we further propose an Adaptive Subset Based Replacement Policy to adapt the program behavior's changing. With the help of set dueling mechanism, our policy dynamically selects a threshold from a pool of thresholds according to which one causes fewest misses in the sampling sets. The experiment result shows the cache performance of ASRP policy is better than DIP and LRU, and the geometric average speedup for 28 SPEC CPU 2006 programs is 4.5% over LRU.

Figure 1 .

 1 Figure 1. SRP policy.

Figure 2 .

 2 Figure 2. Example of SRP policy.

Figure 3 .

 3 Figure 3. Hardware implementation of SRP policy.

Figure 4 .

 4 Unique block addresses (a: whole trace and b: a zoom in) accessed by xalancbmk in set 513.

Fig. 5

 5 shows the cache performance of xalancbmk varies with different threshold values. SRP successfully reduces the cache misses comparing with LRU. Fig.5 also shows that the performance of SRP policy is very sensitive to the threshold value. For different thresholds, SRP can hold different fractions of cache data, and at threshold 4 and 8 it obtains the best performance.

Figure 5 .

 5 Figure 5. MPKI vs. threshold values for xalancbmk.

.

Figure 6 .

 6 Unique block addresses (a: whole trace and b: a zoom in) accessed by GemsFDTD in set 513.

Figure 7 .

 7 Figure 7. MPKI vs. threshold values for GemsFDTD.

Figure 8 .

 8 Figure 8. Cache performances of SRP on different thresholds.

Figure 9 .

 9 Figure 9. Implementation of ASRP policy.

Figure 10 .

 10 Figure 10. Threshold selection by a follower set.

Figure 11 .

 11 Figure 11. Result of single core experiment.

Figure 12 .

 12 Cache performance of ASRP for xalancbmk and GemsFDTD.

Acknowledgement

This work was supported by Inner Mongolia Natural Science Research Foundation Project (No. 20080404MS0901 and 2009BS0901) and the Inner Mongolia University Science Research Foundation Project (No. NJ09009) in P. R. China. The author would like to thank Dr. Jaleel Aamer for his help during the writing of this paper.