Christoph M Angerer
email: angererc@inf.ethz.ch

Thomas R Gross

Parallel Continuation-Passing Style

We present a parallel version of continuation passing style, called pCPS. Using pCPS as the intermediate representation allows a compiler to first translate a sequential program into a form with explicit scheduling and then gradually increase the parallelism by removing happens-before constraints whenever possible.

Introduction

Many compiler optimizations require a program to be first transformed into a suitable internal representation (IR). The two most common IR forms are static single assignment (SSA) and continuation-passing style (CPS).

In SSA, every variable is assigned exactly once. Multiple assignments to the same variable are translated into single assignments to different versions of this variable. A versioned variable is written as the original variable name with a unique subscript. Because this subscript makes it easy to find the one point where a variable has been defined, use-def chains are explicit in SSA form. This greatly simplifies the analysis of the program and thus benefits optimizations working with SSA.

While SSA is widely used in compilers for imperative languages, many compilers for functional languages prefer CPS, even though both forms are technically equivalent [START_REF] Appel | SSA is functional programming[END_REF][START_REF] Kelsey | A Correspondence Between Continuation-Passing Style and Static Single Assignment form[END_REF]. In CPS, a function never returns to its caller as in the more familiar direct style. Instead, it expects a continuation function as an additional parameter. When the function has finished its computation, it will call this continuation function and pass it the result value. Similar to SSA, CPS is easier to analyze than a program in direct style because it makes the control flow explicit.

For both forms, algorithms exist that can automatically transform a direct style source program into SSA or CPS. These algorithms work on the unmodified source code and do not require the programmers to change anything-an important factor for their success.

Both forms, however, have a serious drawback when it comes to multicore systems: Neither one has any support for parallelism. In CPS, for example, the call to the continuation function must be in tail-position; that is, it must be the last thing the function does. Because there can be only one such tail-call, a function cannot fork computation in CPS. This makes CPS inherently single-threaded. A program can start parallel tasks by calling library functions, but this makes it hard for the compiler to analyze and optimize.

In this paper, we present parallel continuation-passing style (pCPS) as a superset of single threaded CPS. pCPS is a superset of CPS in the sense that there exists a simple substitution that transforms a program in CPS into a program in pCPS with equivalent behavior. Unlike CPS, however, pCPS allows the program to be transformed into a parallel version through a combination of automatic, semi-automatic, and manual means. The transformation of a program can be done in one pass or gradually over multiple iterations, increasing the parallelism incrementally with every optimization pass.

Parallel Continuation-Passing Style

In this section, we present pCPS in the context of Java. The basic building blocks in pCPS are tasks. A task is similar to a method in that it contains code that is executed in the context of a this object (or the class in the case of static methods/tasks). Unlike a method, however, one does not call a task, which would result in the immediate execution of the body, but instead schedules it for later execution.

Consider the following snippet of a Java class with explicit pCPS task scheduling: At runtime, a scheduler constantly chooses activations that are eligible for execution and executes them. The order in which the scheduler is allowed to start the activations is specified by happens-before edges in the schedule graph. If the schedule contains a happensbefore edge o1, t1() → o2, t2() , for example, the scheduler must guarantee that activation o1, t1() has finished execution before activation o2, t2() is started.

In the code, the currently executing activation is accessible through the keyword now. Whenever a new task is scheduled, the scheduler automatically adds an initial happens-before relationship between now and the new activation node. This prevents the immediate execution of the new activation and therefore allows the current task to add additional constraints to the schedule before it finishes.

In addition to those implicit happens-before relationships, the example contains the statement a→b. This explicitly adds an edge to the schedule between the two activation objects a and b.

Because pCPS does not have call-return semantics, an activation cannot directly return a value. To simplify the passing of results between activations, however, Activation provides a built-in field called res that we can use by convention to store the result of a computation.

Example

As an example, consider a method fib() for computing fibonacci numbers.

int fib(int k) { if (k <= 2) return 1; else return fib(k-1) + fib(k-2); }
The else case contains two recursive calls to fib(). Because of the +, however, none of these calls is a tail call because we have to wait until both functions return before we can add their results.

A translation into CPS splits the else case into three inner functions generated by the compiler 1 :

int fib(int k, fun ret) { if (k <= 2) ret(1); else fib(k-1, fun(left) { fib(k-2, fun(right) { ret(left+right); })}) }
This example demonstrates how the translation into CPS adds the additional parameter ret for the continuation to fib(). A return in direct style is translated into a tail call to this continuation function, passing the result as a parameter. A function call that is not in tail position requires the CPS transformation to split the function at that point, packaging the rest of the function body inside a newly generated block that is passed to the called function.

Such a CPS function can be trivially translated into pCPS by simply wrapping each tail call to the continuation with a sched() statement. Scheduling a single task without adding any other happens-before edges results in a linear schedule a → b which has the same execution behavior as a tail call.

However, there is often a more direct translation into pCPS that generates less anonymous functions, which is beneficial for finding parallelization opportunities. A sequence of function calls can be directly translated 1 In the current version, Java does not contain function pointers and real closures, which are both important for CPS translation. Both could be somewhat simulated with anonymous classes at the expense of much increased verbosity. For the sake of this example, however, we just use an imaginary notation fun(param){body} for creating closures. into a sequence of sched() statements in pCPS. Only the parts that use the results (the + in the fib() example) need to be wrapped inside a single task so that we can correctly schedule it.

Figure 1 shows a pCPS version of the fib() function with this more direct translation. In contrast to CPS, we do not pass a continuation function but an activation object. For this, we have added an additional parameter later to the task on line 1.

Unlike a continuation function, an activation object allows us to join two parallel flows. Consider passing a continuation function to two parallel activations. Both activations will ultimately call the continuation independently from each other; but there will still be two execution threads. By passing the same activation object, however, we can schedule subtasks relative to that common activation object allowing the parallel execution threads to eventually join at that single activation.

On line 8 we store a reference to the current activation now it in the local variable then. Inside the closure of sum(), then allows us to set the result slot in behalf of the outer fib() activation so that our clients can read it from there. We must wrap the summation + inside its own task because it is dependent on the results of fib(k-1) and fib(k-2) and must be scheduled after those.

The actual recursive invokations are scheduled on lines 15 and 16. By passing our sum activation we make sure that sum is not executed before both subtasks have finished their computations. Because the recursive calls to fib() and their summation were ordered in the original program, the translation also added two ordering constraints on lines 17 and 18. The return in the original program is translated into sum→later to accomodate the fact that the return happens before the parent continues.

Introducing Automatic, Semi-automatic, and Manual Parallelism

The last section demonstrated the translation of a sequential program into pCPS. The transformed program used explicit task scheduling but still obeyed all ordering constraints of the original program. As a result, the pCPS version is still a sequential program. The difference, however, is that it is now in a form that allows different optimizations to gradually increase the parallelism. Optimizations may add or remove edges and split or combine tasks whenever they think it is beneficial.

There exist analyses that can identify parallelism in a fully automated way, such as polyhedral optimization [START_REF] Bondhugula | Sadayappan A Practical Automatic Polyhedral Parallelizer and Locality Optimizer[END_REF]. In other cases, the programmer must provide program annotations allowing or disallowing certain optimizations, as in, for example, OpenMP [START_REF] Balart | Experiences Parallelizing a Web Server with OpenMP[END_REF][START_REF]OpenMP Specification: Version 3.0[END_REF] or Cilk [START_REF] Randall | Cilk: Efficient Multithreaded Computing[END_REF].

By exposing pCPS features to the source programming language, programmers can additionally handoptimize certain parts in the program. The lightweight, ad hoc nature of pCPS allows adding parallelism with minimal impact on the rest of the program. Adding parallelization through threads, on the other hand, often requires major redesigns of the overall application architecture to incorporate the thread management and synchronization.

After an optimization found an opportunity to introduce parallelism, the compiler will transform the IR to incorporate this result. As an example, we show how to transform the example from Figure 1 into a parallelized version.

In the pCPS version, the happens-before edge on line 17 is not strictly necessary and can be removed. The edge was introduced by the pCPS translation only because of the implicit ordering in the original expression fib(k-1) + fib(k-2). Figure 2(a) shows the schedule that can be extracted from the code in Figure 1. As expected, the schedule is a linear list of activations representing the sequential control flow.

Consider an optimization that checks whether each edge in a schedule is required or not. Because fib() only accesses local variables, it is trivial for the compiler to see that the two recursive calls to fib() can be parallelized and therefore the edge f is unnecessary. For more complex scenarios, the compiler may use a more advanced data-race detection mechanism to figure out whether two activations would interfere with each other when parallelized.

Removing the edge f requires us to adjust the schedule to ensure that the transitive ordering of the predecessors and successors of the edge source and targets remain intact. Simply deleting the edge f , for example, would destroy the transitive ordering of nodes f ib(k -1) and sum() .

When deleting an edge a → b, the transitive ordering is maintained by adding additional edges to the schedule: for each incoming edge x → a into node a we create a new edge x → b; similarly, for each outgoing edge b → y from b we create an edge a → y.

The result of this transformation for our example can be seen in Figure 2(b). The two new edges e and g were created to retain the transitive ordering through edges e and g. In this schedule, f ib(k -1) and f ib(k -2) can be executed in parallel while sum() is still (correctly) ordered. For the source code, this transformation changes the happens-before edge on line 17 to left→sum.

Related Work

SSA for parallel programs [START_REF] Lee | Concurrent Static Single Assignment Form and Constant Propagation for Explicitly Parallel Programs[END_REF][START_REF] Srinivasan | Static Single Assignment Form for Explicitly Parallel Programs[END_REF], OpenMP [START_REF]OpenMP Specification: Version 3.0[END_REF] and Cilk [START_REF] Randall | Cilk: Efficient Multithreaded Computing[END_REF] are examples of programming systems with lightweight ad hoc parallelism. Similar to pCPS, in these systems parallelism can be incrementally added to a program by gradual refinement. pCPS, however, allows for unstructured parallelism whereas the forkjoin style constructs of parallel SSA, OpenMP and Cilk are lexically scoped. Lexical scoping comes at the cost of flexibility, making it difficult to model common patterns such as futures or producer-consumer [START_REF] Balart | Experiences Parallelizing a Web Server with OpenMP[END_REF].

Futures [START_REF] Baker | The Incremental Garbage Collection of Processes[END_REF][START_REF] Niehren | A Concurrent Lambda Calculus with Futures[END_REF] are a mechanism for encapsulating computations. When a future is resolved before the computation has finished, the resolution blocks until the result is available. This behavior is very similar to task scheduling. While being convenient for programmers, however, futures are not very well suited as a compiler IR. Because futures do not make the happensbefore edges explicit, as pCPS does, it is much harder for the compiler to statically reason about the schedule and derive optimizations from that.

The join-calculus [START_REF] Fournet | The Join-Calculus: A Language for Distributed Mobile Programming[END_REF] and π-calculus [START_REF] Milner | Communicating and Mobile Systems: the π-Calculus[END_REF] are examples of process calculi for concurrent systems. A process calculus defines an algebra for describing and analyzing the interaction, communication, and synchronization between concurrent processes. As algebras, process calculi permit formal reasoning about many of their properties, such as behavioral equivalence through bisimulation [START_REF] Fournet | Bisimulations in the Join-Calculus[END_REF]. For a program to make use of this formal foundation, however, it must have been designed and written with the process calculus in mind. For this reason, process calculi are used as the basis for programming languages, but not for compiler IRs. We do not know of any successful translation of an imperative, shared-memory program into a process calculus that would allow for further optimizations.

Concluding Remarks

Most compilers use SSA or CPS as their intermediate representation. Neither form, however, has any support for parallelism but are inherently single threaded.

In this paper we propose a parallel version of CPS, called pCPS. pCPS allows a compiler to incrementally increase the parallelism using multiple optimization phases. If pCPS is used as the common in-and output for each optimization, different independent optimizations can be seamlessly integrated into a single optimizing compiler.

10 / 12 +Figure 1 .

 10121 Figure 1. Fibonacci in pCPS.

Figure 2 .

 2 Figure 2. (a) The schedule extracted from Figure 1 after transitive edges have been removed; (b) deleting the unnecessary edge f requires the addition of e and g to keep the transitive ordering intact.


George Patsilaras

Niket K Choudhary

James Tuck
email: jtuck@ncsu.edu

Design Trade-offs for Memory Level Parallelism on an Asymmetric Multicore System

Asymmetric Multicore Processors (AMP) offer a unique opportunity to integrate many kinds of cores together with each core optimized for different uses. However, the impact of techniques for exploiting high Memory Level Parallelism (MLP) on core specialization and selection on AMPs has not been investigated. Extracting high memory-level parallelism is essential to tolerate long memory latencies, and such techniques are critical for speeding up singlethreaded codes which are memory bound. In this work, we explored multiple core configurations with different widths and frequencies and concluded that a narrow faster core is better than a wide slower core for regions of high MLP.

We use an effective hardware-level scheduling mechanism, which requires identifying MLP phases on the fly and scheduling execution on the appropriate core. We successfully exploit the custom MLP core during clustered L2 misses and otherwise use the wider issue core. Compared to a single-core design optimized for both modes of operation, our AMP design provides a geometric mean performance improvement of 4% and 10% for SPECint and SPECfp, respectively, with a maximum speedup of 19.5%. For the same study, it achieves a 10% and 25% energy delay 2 reduction fo SPECint and SPECfp, respectively.

Introduction

Asymmetric Multicore Processors (AMPs) have been proposed as a means to achieve an improved performance per watt ratio for a wide range of applications [START_REF] Kumar | Single-isa heterogeneous multicore architectures: The potential for processor power reduction[END_REF][START_REF] Kumar | Core architecture optimization for heterogeneous chip multiprocessors[END_REF][START_REF] Kumar | Single-isa heterogeneous multicore architectures for multithreaded workload performance[END_REF], when compared to Symmetric Multicore Processor Systems. This advantage comes from the way AMPs can exploit diverse behavior across and within applications. Applications targeted by AMPs tend to be split into two groups: single-threaded sequential applications or parallel applications. A further classification of single-threaded applications is: CPU-intensive applications, which have high amounts of instruction level parallelism (ILP), and Memory-intensive, which have high cache-miss rates and thus high amounts of processor stall time.

AMPs have been shown to be beneficial when execut-ing the CPU-intensive single-threaded applications on the powerful cores [START_REF] Becchi | Dynamic thread assignment on heterogeneous multiprocessor architectures[END_REF] while being more power efficient for the Memory-intensive single threaded applications by executing on the simpler cores during regions of high L2 cache miss rates [START_REF] Kumar | Single-isa heterogeneous multicore architectures: The potential for processor power reduction[END_REF]. Finally, AMPs provide higher performance per watt when executing highly parallel applications on a group of simpler cores [START_REF] Kumar | Single-isa heterogeneous multicore architectures for multithreaded workload performance[END_REF]. Despite being in the multi-core era, sequential performance matters. Memory level parallelism (MLP) has been proposed as a way to boost the performance of applications that stall frequently. Rather than waiting for one access at a time, the goal is to exploit available memory bandwidth to request many memory accesses at once. A variety of hardware-only MLP enhancing techniques have been proposed [START_REF] Collins | Dynamic speculative precomputation[END_REF][START_REF] Moshovos | Slice-processors: an implementation of operation-based prediction[END_REF][START_REF] Ganusov | Future execution: A prefetching mechanism that uses multiple cores to speed up single threads[END_REF][START_REF] Mutlu | Efficient runahead execution: Power-efficient memory latency tolerance[END_REF][START_REF] Dundas | Improving data cache performance by pre-executing instructions under a cache miss[END_REF][START_REF] Ceze | CAVA: using checkpoint-assisted value prediction to hide l2 misses[END_REF][START_REF] Kirman | Checkpointed early load retirement[END_REF][START_REF] Zhou | Enhancing memory level parallelism via recovery-free value prediction[END_REF][START_REF] Lebeck | A large, fast instruction window for tolerating cache misses[END_REF][START_REF] Srikanth | Continual flow pipelines[END_REF][START_REF] Zhou | Dual-core execution: Building a highly scalable single-thread instruction window[END_REF]. These techniques are advantageous since they can transparently accelerate sequential codes, but they are limited by their high energy consumption.

Some of these MLP techniques leverage precomputation to issue loads in advance. Other techniques leverage hardware within a single core to detect a long latency load then speculate past it to generate overlapping misses [START_REF] Ganusov | Future execution: A prefetching mechanism that uses multiple cores to speed up single threads[END_REF][START_REF] Ceze | CAVA: using checkpoint-assisted value prediction to hide l2 misses[END_REF][START_REF] Kirman | Checkpointed early load retirement[END_REF][START_REF] Zhou | Enhancing memory level parallelism via recovery-free value prediction[END_REF]. Multithreaded approaches have been considered which automatically construct prefetching threads [START_REF] Ganusov | Future execution: A prefetching mechanism that uses multiple cores to speed up single threads[END_REF], or tightly couple two cores to act as a large instruction window [START_REF] Zhou | Dual-core execution: Building a highly scalable single-thread instruction window[END_REF]. Given the importance of tolerating long latencies to memory within a single thread, future processors will likely incorporate techniques to overlap long latency misses.

Given the performance benefits of techniques for boosting MLP, a key question is how to best integrate high MLP techniques on an AMP. The possible answers to this question are not trivial or obvious. For example, applications which benefit the most from MLP techniques tend to have a low IPC and favor simpler cores for power-efficient performance, thereby favoring the integration of MLP techniques on such cores. But, when MLP techniques are added to the cores, past studies have shown that wider cores are needed to extract enough cache misses to make high MLP techniques worthwhile [START_REF] Chou | Microarchitecture optimizations for exploiting memory-level parallelism[END_REF]. On the other hand, smaller cores can run faster with better power efficiency than larger cores. Therefore, core selection for MLP will depend on the behavioral characteristics of applications with problematic L2 miss rates, the core-level needs of MLP techniques, and the design implications of different core widths.

This article makes the following contributions:

• We are the first to design an AMP which couples an independent ILP core with a customized core, that incorporates an MLP technique.

• We explore the customization of our MLP technique by investigating different combinations of core designs for code regions with varied L2 miss rates. With this analysis, we can identify trends in core behavior and pinpoint a better core design among those studied for our MLP technique.

• For Checkpointed L2 Miss Processing with Value Prediction (CLP+VP), a scheme similar to CAVA [START_REF] Ceze | CAVA: using checkpoint-assisted value prediction to hide l2 misses[END_REF] and Clear [START_REF] Kirman | Checkpointed early load retirement[END_REF], we find that a narrower 2-wide issue core outperforms a 4-wide issue core. This advantage is born from the interaction of higher frequency and the systematic behavior of CLP+VP. Overall, our analysis advocates an Asymmetric Multicore Processor design that supports MLP by integrating CLP+VP on the 2wide issue core.

• We propose Symbiotic Core Execution (SCE) to exploit fine grained differences in application behavior to run moderate to high MLP regions on the narrower core customized for MLP and the other regions on an aggressive 4-wide issue core designed for high ILP.

• For SCE, we identify an effective scheduling mechanism which judiciously switches cores to exploit regions of high MLP on the customized MLP core without incurring too much overhead from switching.

The rest of the paper is organized as follows. Section 2 gives an overview of AMPs and the MLP enhancing technique we consider; Section 3 presents a detailed study of different core designs for varying levels of MLP. Section 4 describes our proposed Symbiotic Core Execution; Section 5 discusses our methodology and provides a detailed evaluation. Section 6 is devoted to related work, and Section 7 concludes.

Background

Asymmetric Multicore Processors with Core Customization

AMP customization works by tailoring a core for the particular needs of an application or workload. For example, some applications benefit tremendously from variations in branch predictor design, cache size, or issue window size [START_REF] Kumar | Core architecture optimization for heterogeneous chip multiprocessors[END_REF][START_REF] Hashem | Architectural contesting: exposing and exploiting temperamental behavior[END_REF] that would not be generally applicable to a wide range of programs. By building many customized cores that target such behaviors, applications can benefit more by running on the customized core than running on a core designed for the general case. Designing customized cores requires a careful design space and design cost exploration. A processor design has an associated cost, where the cost can be quantified in terms of propagation delay, power consumption, die area, design effort, manufacturability, or fault vulnerability. A complex microarchitecture might enhance IPC, but at the same time could increase the propagation delay. For instance, increasing the size of the issue window and issue width can boost IPC for applications with abundant ILP, but at the same time, clock rate may decrease to accommodate the larger content addressable memory and deeper select tree.

Fabscalar [START_REF] Niket | Fabscalar[END_REF], is a state of the art tool that enables architects to synthesize customized designs and evaluate the effects of different designs, in great detail, in terms of frequency, area and power. Using fabscalar we can synthesize a Verilog model of an arbitrary superscalar processor and analyze how sizing structures can affect frequency. Figures 1(a) 1(b) 1(c) show the impact of increasing the issue window on the delay, area, and peak energy consumption of the wakeup-select logic for different issue widths. These assume a 45nm technology and the same input voltage. As we can see from the graph the smaller the width and issue queue size the faster the clock frequency can be.

We used Fabscalar to perform a design space exploration that searched for the fastest 1-wide, 2-wide, and 4-wide issue cores. In our search, we assumed a pipelined architecture with a constant depth and fixed supply voltage, then we varied the issue width and all related microarchitectural structures. We found that the 4-wide cores maximum frequency was 3GHz, the 2-wide core frequency was 3.6GHz and the 1-wide core had a maximum frequency of 4.5GHz (more architectural details can be found in Section 5.1). The design search considers all possible timing critical paths of a modern superscalar out-of-order processor, for example wake-select logic, rename logic, cache access time etc. [START_REF] Palacharla | Complexity-effective superscalar processors[END_REF], to synthesize a processor with a realistic clock frequency. Since we keep the total pipeline depth constant for our exploration, the synthesized core reflects the trade-off between the pipeline complexity and the propagation delay.

As in any design space exploration, it is important to search an appropriate set of designs. Fabscalar considers many circuit-level and architecture-level optimizations, although it is not exhaustive. Therefore, a design team could find other core designs our search did not consider. In general, however, attempts to increase the frequency through microarchitectural complexity do not always have the expected effect on performance, area, or power consumption. For example, while pipelining can help mitigate the increased propagation delay for larger structures or wider processors, it can also lead to a decreased IPC [START_REF] Hartstein | The optimum pipeline depth for a microprocessor[END_REF][START_REF] Borch | Loose loops sink chips[END_REF]. While our exploration is not exhaustive, we believe the relative performance, while not absolutely the same, may be indicative of what a state-of-the-art design team could achieve in industry.

In the rest of the article, we use the core designs found by Fabscalar to investigate how to customize an AMP for our MLP technique.

Checkpointed L2 Miss Processing with

Value Prediction: CLP+VP Several MLP mechanisms have been described in previous work, such as Runahead Execution [START_REF] Mutlu | Efficient runahead execution: Power-efficient memory latency tolerance[END_REF], CAVA [START_REF] Ceze | CAVA: using checkpoint-assisted value prediction to hide l2 misses[END_REF], and others [START_REF] Kirman | Checkpointed early load retirement[END_REF][START_REF] Lebeck | A large, fast instruction window for tolerating cache misses[END_REF]. Our basic mechanism, shown in Figure 2(a) adopts some features from CAVA [START_REF] Ceze | CAVA: using checkpoint-assisted value prediction to hide l2 misses[END_REF] and Clear [START_REF] Kirman | Checkpointed early load retirement[END_REF]. Once an L2 miss reaches the head of the ROB, a checkpoint of the register file is recorded at the point just before the load. Then, we place a predicted value in the destination register of the load and continue execution as a speculative epoch. By retiring the load with a speculative value, forward progress can be made while waiting for the mem- Once the L2 miss completes, the processor checks the actual value with the predicted one; and, if the prediction was correct, we exit the speculative epoch. If the load's value was incorrect, execution is restored to the checkpoint, the value predictor tables are updated, and the processor resumes from the mispredicted load instruction. In order to avoid recovery in the case of a successful prediction, the L1 cache buffers the speculative state [START_REF] Ceze | CAVA: using checkpoint-assisted value prediction to hide l2 misses[END_REF]. We will refer to this basic strategy as Checkpointed L2 Miss Processing with Value Prediction(CLP+VP). CLP+VP supports making predictions on multiple outstanding loads, but, only one checkpoint is kept, so any misprediction results in rolling back the entire speculative epoch back to the first predicted load value. Therefore, we adopt CAVA's mechanisms to prevent aggressive speculative execution through loads which are value predicted with low confidence. Figure 2(b) shows the CLP+VP architecture with the required Speculative Data Cache [START_REF] Ceze | CAVA: using checkpoint-assisted value prediction to hide l2 misses[END_REF]. In addition, the OPB is the Outstanding Prediction Buffer. It tracks all outstanding predictions, and if the prediction does not match, the Recovery and Rollback logic is triggered.

MLP Design Trade-offs on an AMP

In this section, we investigate how best to integrate high MLP techniques in an AMP. As a motivational discussion, consider the systems shown in Figure 3. Figure 3(a) shows a Asymmetric CMP similar to that proposed by Kumar et al. [START_REF] Kumar | Single-isa heterogeneous multicore architectures: The potential for processor power reduction[END_REF] but we assume that a base core design is optimized for different issue-widths. We are primarily interested in answering two related questions. ( 1) is there a core preference when implementing an MLP technique? In other words, are MLP techniques heterogeneous and should be integrated on particular cores, or should we integrate the technique throughout the entire chip (homogeneously). Integrating a technique on every core is preferable only when it offers compelling advantages, given design effort and validation costs. Figure 3(b) shows the case where all cores receive the high MLP technique.

To answer these questions, we divide the analysis into two parts in the following sections. First, we investigate core preference for regions of code with a large L2 miss rate. This establishes baseline performance for the cores considered in our study. For every configuration looked at we used Fabscalar [START_REF] Niket | Fabscalar[END_REF] for a logic synthesis of the entire processor in order to measure frequencies and power, we then use SESC [START_REF] Renau | SESC Simulator[END_REF] for our simulations. The core configurations are described in Table 1 however more details on our experimental setup can be found in Section 5.1.

Exploring MLP Potential on Different Core Widths

In this section, we investigate the behavior of our baseline AMP design in code regions sensitive to MLP techniques. Our goal is to establish a relationship between core performance on a code region and suitability for exploiting MLP in the same region. To establish enough data points to draw a strong conclusion about potential for MLP and core preference, we extract code regions of 10K instructions from a dynamic trace of the SPEC CPU 2000 applications and bin these regions according to their L2 miss rate. Hence, for a wide range of applications, we can average out behavior based solely on potential for MLP.

Figure 4 plots the performance of the Core2 and Core1 designs normalized to the Core4 design. The dashed lines are forcing all cores to run at the same frequency, while solid lines are taking frequency explicitly into account. Each point on the y-axis is calculated by summing the execution time of all code regions for the L2 miss count specified on the x-axis as measured on each core. This execution time is then used to calculate speedup relative to Core4. As a result each bin on the x-axis indicates a different L2 miss rate (L2 misses/10K instructions). In this analysis, we presume that regions with higher miss rates will have more potential for MLP. Since these cores have no additional MLP technique, they are not exploiting the MLP available from out-of-order execution.

The clear advantage goes to Core4 across the entire MLP continuum under the same frequency. The relative performance gap is larger for low MLP and narrows significantly at higher MLP potential. This narrowing is the result of significantly less ILP in regions of many L2 misses, thereby eliminating Core4's primary advantage.

When considering frequency, rather than maintaining a significant advantage across the continuum, Core4 loses its advantage over Core2 for L2 miss rates above 10 per region. Furthermore, Core4 is no longer competitive with Core2 for high miss rates above 90 per region and not competitive with Core1 above 100 misses. Since the frequent L2 misses prevent the wider core from leveraging its greater width for more ILP, the higher frequency cores are able to process instructions faster. However, the frequency advantage of Core1 is not enough to overcome the higher IPC of Core2; hence, Core2 always outperforms Core1. In between 10 misses and 90 misses per region, there is no clear winner when comparing Core4 and Core2 but we will consider Core2 winner due to power savings of a smaller core. This analysis is important because it shows that the narrower cores are not only better for power, as previously reported [START_REF] Kumar | Single-isa heterogeneous multicore architectures: The potential for processor power reduction[END_REF], but can also provide a performance advantage when designed and clocked at their highest frequency. Even though our design space exploration isn't perfect, given the same design team, a 2-wide core will likely be faster than a 4-wide one. Also, it is clear that core choice is related to MLP potential. Where there is little to no potential for MLP, Core4 is undoubtedly the better choice even with a slower frequency. However, with moderate to high potential for MLP Core2 is best.

Exploring CLP+VP On Different Core Widths

We analyze the performance when CLP+VP is added to each core in the AMP and evaluated it with respect to MLP potential. In Figure 5, clearly, Core4+CLP+VP is better than Core4 with as few as 5 misses per region. We can also observe that Core2+CLP+VP is competitive with Core4+CLP+VP somewhere between 5 and 10 misses. From that point on, the designs appear to be equivalent with Core2+CLP+VP achieving a distinct advantage with more than 80 misses. CLP+VP eliminates many costly pipeline stalls due to L2 cache misses, however, high ILP still cannot be achieved because the MLP technique does not kick in until the L2 miss has been detected. This will delay the processing of the load enough to favor narrower cores with higher frequencies.

Symbiotic Core Execution

An AMP design that dynamically leverages the best core for a region of execution may be advantageous compared to an application level policy which waters down the advantage of any particular core over the regions where it is less effective. We propose incorporating the Core2+CLP+VP core along with Core4 on an AMP and leveraging fine grained scheduling in hardware to instantaneously choose the best core depending on the MLP potential present in the code. When a MLP technique is needed, execution switches to Core2+CLP+VP. When an application is not in a moderate to high MLP region, it executes on the Core4. We call our proposal Symbiotic Core Execution (SCE).

The term symbiosis is borrowed from biology: two self sufficient organisms exist symbiotically when they survive better together than when alone. Symbiosis is a compelling description because it identifies the cores as being independent and capable of working alone, as is often needed in a multiprocessing environment. However, when prudent, they can be used together for a greater performance advantage. A key challenge of SCE is efficient scheduling.

Effective Hardware Scheduling on the MLP Core

To effectively schedule for MLP, we build our policy around the observation that L2 misses tend to cluster. Hence, it is our goal to judiciously schedule work on the MLP core during regions of many L2 misses and switch back when the region ends. An effective hardware scheduling policy requires a balance between switching eagerly to ensure that no region is missed and switching lazily so that core switching is not invoked on isolated L2 misses nor incurs significant overhead.

Eager Switching for Clustered Misses

The first goal of our scheduling policy is to eagerly switch to the MLP core to exploit regions of clustered misses. We leverage our analysis from Section 3 to determine the rate of L2 misses needed for the MLP core to overtake the ILP core. According to Figure 5, on average, we see the cross over point at 10 L2 misses per 10K instructions. So, as a heuristic, we assume that we need to observe misses at that rate for the MLP core to be profitable. We identify this rate as r miss . We use r miss to identify the minimum number of L2 misses that should be observed in For each contiguous chunk of N inst instructions, our scheduler counts the number of misses. If fewer than N inst × r miss misses are observed at the end of the region, the counter is cleared. As soon as N inst × r miss misses are observed, the application is switched to the MLP core. Figure 6(a) illustrates this policy.

A key challenge is tuning N inst . If it is too small, we will switch every time we see an L2 miss. However, if N inst is too large, it increases the likelihood that we wait too long to switch and miss good scheduling opportunities. After a series of experiments we concluded that N inst = 3000 works well for a variety of applications. Assuming r miss = 0.001, this means we are looking for 3 or more misses in a region to switch to the MLP core. The hardware cost associated with these counters is very small and similar mechanisms are already present in current microprocessors. Note that this miss rate corresponds to the point in Figure 5 when Core2+CLP+VP becomes the desirable core.

Lazy Switching to Correct Core

Once running on the MLP core, our scheduler evaluates a) if it was a correct decision to switch and b) when there is no longer a benefit from MLP. It is important to remain on Core2+CLP+VP long enough to exploit any MLP. However, if the decision to switch was erroneous, it is desirable to catch this mistake quickly before too much time elapses.

Since L2 misses cluster, if the application is entering a region of clustered misses, we expect an elevated miss rate If this phenomenon is not observed, it is unlikely there will be any benefit from the MLP technique. Therefore, we define N stay as the number of instructions that must be executed on the MLP core; during that region, an L2 miss must be observed. If no misses are observed, it is likely that clustering is not present (or no longer present), and execution should return to the wide core. However, if a single miss is observed, we remain on the core for an extended execution, N ext . At the end of the extended region, we perform the same evaluation again. Figure 6(b

Operating System Interaction

OS view of cores. We assume that the chip can operate in two modes. In SCE mode, we assume that the OS sees one logical core and hardware can initiate context switching among the symbiotic cores. In the case where two threads are waiting to execute, SCE is disabled, and the OS has a view of two available cores. Scheduling is done in a similar way as [START_REF] Kumar | Single-isa heterogeneous multicore architectures for multithreaded workload performance[END_REF].

Context Switching. During SCE mode, when hardware determines the need to switch cores, it stalls the fetch engine. Once the pipeline is empty and all instructions from the pipeline retire, we context switch between the cores. We assume a constant delay of 100 cycles to model the latency for copying registers from one core to the other. Once the context switch is finished, we resume execution on the new core. Our simulations modeled behaviors such as cache warm-up penalty, effects on the TLB, and branch predictor due to switching cores. These costs are modeled separately from the 100 cycle register copy penalty.

Evaluation of SCE

Experimental Setup

To evaluate our AMP proposal we used SESC [START_REF] Renau | SESC Simulator[END_REF] an execution-driven simulator, and compiled SPEC2000 applications using a MIPS cross compiler built from GCC 4.4 [START_REF]Gnu compiler collection[END_REF]. We also used the FabScalar framework [START_REF] Niket | Fabscalar[END_REF] to weigh the cost of different superscalar designs in terms of clock period, area, and power (static and dynamic). The FabScalar framework can be used to synthesize Verilog models of arbitrary superscalar processors, where each superscalar processor can be customized in terms of pipeline ways (width of the processor) and sizes of the memory structures within a stage.

Since a superscalar processor makes use of many specialized and highly-ported RAMs/CAMs/FIFOs (e.g., physical register file, rename map table, issue queue, loadstore queue, active-list etc.), we are also using the register file compiler from the FabScalar framework. The register file compiler uses custom layouts of multi-ported bit-cells and peripheral circuits to generate memory structures and characterize their access times and power consumption by doing SPICE level simulation. We used Synopsis Design Compiler C2005.09-SP3 and placed-and-routed with Cadence SoC Encounter V7.1, using the FreePDK OpenAccess 45nm Standard Cell Library [START_REF] Stine | Freepdk: An open-source variation-aware design kit[END_REF] to synthesize our different designs in order to estimate timing.

Table 2 shows the SESC configuration parameters used for the Core4, Core2, Core1, and CLP+VP configurations. Labels used in the graphs are explained in Table 1.

Performance

Figure 7 shows the speedups of CLP+VP described in Section 2.2 over Core4, our base case. We see that SCE with CLP+VP delivers a geometric mean speedup of 1.13 for SPECint applications and 1.20 for SPECfp over Core4.

Looking at individual benchmarks we see that applu, equake, mcf, mgrid, swim, and wupwise benefit from SCE utilizing the CLP+VP core for MLP regions and the high ILP core for the other regions. SCE scheduling yields higher performance than any of the cores on their own. For benchmarks with no benefits we see that they are characterized by low L2 miss rates.Finally, crafty and vortex, which have a slight degradation do not benefit from CLP+VP technique indicating that these benchmarks have no exploitable MLP regions.

When comparing to a single core with the CLP+VP technique, we see that our technique is better. SCE CLP+VP's speedup of 1.13 and 1.20 for SPECint and SPECfp applications, respectively, are higher than CLP+VP's, 1.09 and 1.10. The benefits come from the faster 2-wide CLP+VP core achieving better performance than the 4wide CLP+VP for high MLP regions.

Power and Energy Delay 2

Figure 8(a) shows the power consumption for each design we evaluated. This includes the static and dynamic power for the occupied core and the static power from the core not used. Caches remain active for the entire execution, and so we modeled the static and dynamic power during the entire execution for regular accesses and invalidations triggered by the coherence protocol. As we can see, our SCE CLP+VP design consumes less power compared to Core4+CLP+VP by a geometric mean of 9% and 19% for SPECint and SPECfp, respectively. SCE however, does require more power than Core2+CLP+VP this is a direct consequence of using Core4 to accelerate non MLP Overall, SCE is power efficient despite the added MLP core. The main reason is because the L2 Cache constitutes more than half the total chip area, and thus contributes the most to the total static and dynamic power consumed. The second reason is that the dynamic power consumed by the 4-wide core is significantly higher than the dynamic power consumed by a 2-wide core. During regions where execution is on the MLP core the dynamic power difference compensates for the extra static power added for the MLP core.

Figure 8(b) displays the energy delay 2 for each configuration. Overall, SCE with CLP+VP reduces the energy delay 2 by 27% and 28% for SPECint and SPECfp over Core4. When compared to the Core4+CLP+VP design, it is reduced by 10% and 25% for SPECint and SPECfp, respectively. Note that equake and swim are particular advantageous when considering energy delay 2 because their higher performance offsets their higher power. On the other hand, we see that crafty, vortex, and vpr, which do not benefit from CLP+VP in performance, have a slightly worse energy delay 2 over Core4 due to the added core's static power and the added instructions executed. The sources of overhead can be split into flushing the pipeline of a core in order to switch execution and then copying the register file from core to core. In this table, we have marked StallCore4 and StallCLP+VP as the time spent waiting to flush the pipeline during a switching decision. Finally, Switch is the time copying the register file over to the other core. We see that flushing the pipeline is a significant overhead. More specifically we see that for mcf and equake this overhead composes more than 80% of the total overhead. This is due to the increase in L2 misses needed to be serviced before switching. An interesting fact is that switching from the CLP+VP core back to the ILP is faster since the core is not as wide and has fewer in-flight instructions. One more source of overhead is the invalidation of shared cache lines that are a result of switching cores. We have not measured this, but we modeled it in our simulations.

Switching Overhead

6 Related Work

Memory Level Parallelism

Although we are in the era of CMP, sequential performance is important. Lots of research has focused on designing processors addressing the memory wall issue by increasing the programs MLP. Prefetching in the form of helper threads is a technique used to extract MLP [START_REF] Collins | Dynamic speculative precomputation[END_REF][START_REF] Zilles | Execution-based prediction using speculative slices[END_REF][START_REF] Roth | Pre-execution via speculative data-driven multithreading[END_REF][START_REF] Moshovos | Slice-processors: an implementation of operation-based prediction[END_REF][START_REF] Ganusov | Future execution: A prefetching mechanism that uses multiple cores to speed up single threads[END_REF]. Execution of the helper thread is done in-parallel on a SMT, or on a separate core for CMP architectures.

Other techniques focus on increasing the window size by unblocking the pipeline on cache misses, increasing the MLP [START_REF] Lebeck | A large, fast instruction window for tolerating cache misses[END_REF][START_REF] Srikanth | Continual flow pipelines[END_REF][START_REF] Cristal | Toward kilo-instruction processors[END_REF]. In these techniques long-latency operations (and dependent instructions) are removed from the scheduling window and inserted to buffers, thus freeing resources. When the latency is resolved the instructions are reinserted into the scheduling window.

Runahead execution [START_REF] Mutlu | Efficient runahead execution: Power-efficient memory latency tolerance[END_REF][START_REF] Dundas | Improving data cache performance by pre-executing instructions under a cache miss[END_REF], CAVA [START_REF] Ceze | CAVA: using checkpoint-assisted value prediction to hide l2 misses[END_REF], and Clear [START_REF] Kirman | Checkpointed early load retirement[END_REF] tolerate the long latency of L2 misses by retiring the load instruction when it reaches the head of the ROB and continuing execution despite the fact that the load has not completed. This is done by using a value prediction. When the memory request returns it re-executes the instructions or if the value was correct continue execution. Chou et al. [START_REF] Chou | Microarchitecture optimizations for exploiting memory-level parallelism[END_REF] evaluates the effectiveness of out-of-order execution on MLP compared to in-order processors as well as the effectiveness of value predictors, branch predictors and runahead execution in enabling the extraction of more MLP. Our work contributes to how an MLP technique could be added to an AMP.

For our MLP core we implement a technique which is like CAVA along with optimizations proposed for Runahead. We picked a runahead like MLP technique because it does not require any modification to the binary. The hardware modifications also require significantly less design effort (modify cache modules) over a technique like CFP which modifies the processor pipeline. We picked a CAVA-like implementation instead of Runahead due to the benefits of Value Prediction on the load miss. This can avoid rollback and provide power savings.

Asymmetric Chip Multiprocessors

Asymmetric Chip Multi-Processor designs have been proposed as a solution to achieve higher performance per watt ratio for executing a wider range of applications [START_REF] Kumar | Single-isa heterogeneous multicore architectures: The potential for processor power reduction[END_REF][START_REF] Kumar | Single-isa heterogeneous multicore architectures for multithreaded workload performance[END_REF][START_REF] Becchi | Dynamic thread assignment on heterogeneous multiprocessor architectures[END_REF][START_REF] Aater Suleman | Accelerating critical section execution with asymmetric multicore architectures[END_REF]. This doesn't always result to an improved performance over a homogeneous system for single threaded applications. Given the same area previous proposals [START_REF] Aater Suleman | Accelerating critical section execution with asymmetric multicore architectures[END_REF][START_REF] Becchi | Dynamic thread assignment on heterogeneous multiprocessor architectures[END_REF][START_REF] Kumar | Single-isa heterogeneous multicore architectures for multithreaded workload performance[END_REF][START_REF] Carlos Saez | A comprehensive scheduler for asymmetric multicore systems[END_REF] achieve performance improvements when scheduling between cores at the multi-application or multi-thread level. No previous proposal has suggested that fine grain scheduling can achieve performance benefits, while only using one core at a time and running one version of the application, which is what our scheme provides.

Recent work on AMPs designed for MLP is presented by Pericas et al. [START_REF] Pericas | A flexible heterogeneous multi-core architecture[END_REF]. In this work, an AMP design is composed of a fast cache core and a small in-order memory core to exploit high and low locality code respectively. By coupling the cores together an increased instruction execution window is created. Our approach is different in that the ILP and MLP cores are fully functional cores which can work independently if needed. Execution of threads is always on one core rather than spread across cores. Architectural Contesting [START_REF] Hashem | Architectural contesting: exposing and exploiting temperamental behavior[END_REF] is another AMP proposal that uses a slipstream [START_REF] Purser | A study of slipstream processors[END_REF] to speed up sequential performance. Our approach is different since we use one thread of the application executing on one core, however both papers try to exploit phases at a fine grain level. Another slipstream paradigm using AMPs is presented in [START_REF] Garg | A performance-correctness explicitly-decoupled architecture[END_REF] where one core is of reduced complexity and the other is the correctness core. The reduced-core executes speculatively optimized code, which works as a value and branch predictor to the correctness core. This approach, however, requires recompilation of the application to create a reduced version of the program that will run on the reduced complexity core. The reduced complexity core is also not an independent functioning core. We do not need recompilation for our scheme, and both cores can function independently.

Another multi-core design for MLP is described in dualcore execution [START_REF] Zhou | Dual-core execution: Building a highly scalable single-thread instruction window[END_REF], where we have two homogeneous cores, coupled together with a forwarding queue to form a larger instruction execution window. The first core executes the instructions and when a long latency stall occurs, an invalid value is used to prevent the cache miss from blocking the pipeline. When instructions retire from the front processor, they are inserted into a queue and forwarded to the second processor. The front processor, besides providing the correct (due to resolving branches) instructions stream, acts as a warm up for the cache by prefetching data. In this proposal every instruction is executed twice and requires both cores on at the same time during the entire execution.

Conclusion

Main memory latency is still a significant performance limiting factor in today's systems. Asymmetric Multicore Processors(AMPs) offer a unique opportunity to exploit MLP by incorporating techniques onto customized cores specifically designed to exploit it. Using a detailed model of cores accurate enough to calculate detailed timing and power characteristics, we determined that narrower cores, in our case a 2-wide issue width, were more effective at exploiting Checkpointed L2 Miss Processing than a wider 4-wide issue core -providing better performance and energy efficiency across the MLP continuum.

We leveraged this finding to support Symbiotic Core Execution on an AMP. SCE is an effective scheduling mechanism because it allows MLP regions to exploit the higher performance and better power efficiency of the customized core while still leveraging the high ILP core during regions with little to no MLP. Using SCE, we achieve performance improvements of 4% and 10% over a single core MLP technique for SPECint and SPECfp with a maximum speedup of 19.5%, while at the same time reducing the energy delay 2 by 10% and 25%.

Figure 1 :

 1 Figure 1: Scaling of Issue Queue in terms of Delay, Area, and Peak Power

Figure 2 Figure 3 :

 23 Figure 2: MLP regions 2 MLP 4 MLP 4 2 1

Figure 4 :

 4 Figure 4: Performance versus MLP potential normalized to Core4

Figure 5 :

 5 Figure 5: Performance versus MLP potential normalized to Core4

Figure 6 :

 6 Figure 6: SCE Scheduling Illustration a region of N inst instructions in order to switch cores.For each contiguous chunk of N inst instructions, our scheduler counts the number of misses. If fewer than N inst × r miss misses are observed at the end of the region, the counter is cleared. As soon as N inst × r miss misses are observed, the application is switched to the MLP core. Figure6(a) illustrates this policy.A key challenge is tuning N inst . If it is too small, we will switch every time we see an L2 miss. However, if N inst is too large, it increases the likelihood that we wait too long to switch and miss good scheduling opportunities. After a series of experiments we concluded that N inst = 3000 works well for a variety of applications. Assuming r miss = 0.001, this means we are looking for 3 or more misses in a region to switch to the MLP core. The hardware cost associated with these counters is very small and similar mechanisms are already present in current microprocessors. Note that this miss rate corresponds to the point in Figure5when Core2+CLP+VP becomes the desirable core.4.1.2 Lazy Switching to Correct Core

Figure 7 :

 7 Figure 7: Performance comparison Normalized to Core

Figure 8 :

 8 Figure 8: Power and Energy Delay 2 for Core4

Table 1 :

 1 Asymmetric Core Configurations

	Label	Configuration
	Core4	4-wide 3GHz Core
	Core2	2-wide 3.6GHz Core
	Core1	1-wide 4.5GHz Core
	Core2 CLP+VP	2-wide 3.6GHz Core with CLP+VP
	Core4 CLP+VP	4-wide 3GHz Core with CLP+VP
	SCE CLP+VP	4-wide 3GHz Core+2-wide 3.6GHz CLP+VP core

  ) illustrates

	Frequency	3 GHz	3.6 GHz	4.5 GHz
	Fetch Rate	6	4	2
	Issue Rate	4	2	1
	Retire Rate	4	2	1
	ROB	128	96	64
	LD/ST Queue	54/38	42/38	36/24
	Mem/Int/Fp Units	2/3/2	2/2/2	1/1/1
	Area(mm 2 )	2.513	1.251	0.540
	Pipeline: 3-cycle fetch, 1-cycle decode,1-cycle Rename, 1-cycle dispatch,
	2-cycle issue,2-cycle issue,1-cycle RegRead, 2-cycle Mem/Int/Fp Units,
	1-cycle DataCache, 1-cycle writeback, 1-cycle retire
	I L1 Cache: Size=32KB; Assoc=4-way; Line size=64B; RT=2 cycles
	Private D L1 Cache: Size=32KB; Assoc=4-way; Line size=64B; RT=2 cycles
	L2 Cache: Size=2MB; Assoc=8-way; Line size=64B; RT=10 cycles
	Main Memory RT=100 nanosec, Core switching delay=100 cycles
	BTB: size=2K; Assoc=2-way
	Branch predictor: bimodal size=16K; gshare-11 size=16K;
	Branch Mispred. Pen.=14 cycles
	H/W Pref.: 16-stream stride prefetcher; hit delay=8 cycles; buffer size= 16KB
	SCE param.: Nstay=700cycles, rmiss=0.001 and Nexit=3000cycles
	CLP+VP configuration: OPB = 128 entries Max. Outs. preds./Instr.=512/3072
	BHLV+GLV predictor, table size=4096 entries each

Table 2 :

 2 Core details. Cycle counts are in processor cycles this policy. We found that N inst = 3000, N stay = 700 and N ext = 3000 work well.

Table 3

 3 displays details on the switching overhead for our SCE proposal. The Overhead column indicates the overhead due to switching cores over the total execution.

		Total
	Benchmark	Overhead	StallCore4	StallCLP+VP	Switch
	ammp	2.02%	61.81%	15.56%	22.63%
	applu	0.22%	51.81%	19.64%	28.55%
	bzip2	0.42%	32.22%	24.92%	42.86%
	crafty	0.06%	33.05%	11.23%	55.72%
	equake	7.30%	67.86%	10.88%	21.26%
	gap	9.21%	42.55%	25.82%	31.62%
	gzip	0.70%	44.17%	33.49%	22.33%
	mcf	8.48%	68.78%	6.90%	24.32%
	mesa	6.45%	35.76%	22.58%	41.66%
	mgrid	1.37%	10.31%	19.00%	70.69%
	parser	6.07%	55.25%	14.61%	30.14%
	swim	2.03%	45.60%	20.25%	34.15%
	twolf	0.15%	61.37%	13.67%	24.97%
	vortex	1.56%	58.32%	14.73%	26.95%
	vpr	0.25%	44.54%	19.27%	36.19%
	wupwise	8.59%	81.75%	12.64%	5.61%

Table 3 :

 3 Overhead Breakdown: Total Overhead of switching over entire execution and percentage of overhead spent flushing pipeline and switching cores


András Vajda
email: andras.vajda@ericsson.com

Per Stenström
email: pers@chalmers.se

Semantic information based speculative parallel execution

As the number of cores within one processor will continue to increase, while per-core frequency is likely to stagnate, speculative execution in general and data value prediction in particular, will once again be a prime candidate for speeding up execution of applications with limited inherent parallelism. In order to succeed however, we need to improve the semantic information the applications will be able to provide to the hardware; in this paper we present initial results based on using formal contracts to convey such information to the run-time environment in order to guide the type and scope of speculative execution. Experiments with an application that is traditionally considered hard to parallelize -Huffman decoding -show the potential of such an approach, without the need to re-write the actual application. One of the strengths of this method is that it can make efficient use of large number of cores, opening a possible path for scaling applications with limited amount of parallelism on massively multi-core processors.

INTRODUCTION

Multi-core architectures has established itself as the main-stream approach for building processors delivering improved performance according to Moore's law. There are however two major issues that the industry and the research community have to tackle: (1) performance of applications with limited inherent parallelism and (2) increasing unreliability of HW as the industry progresses to newer process technologies.

In fact, in the absence of a universal method for turning software with limited parallelism into software with unlimited parallelism, the computing industry is in the front of a stark reality: while we can keep increasing the transistor count, we simply cannot use these transistors to run software with limited parallelism any faster. Thread-level speculation is an approach that has been well studied [START_REF] Hammond | Data speculation support for a chip multiprocessor[END_REF][START_REF] Hammond | Transactional Memory Coherence and Consistency[END_REF][START_REF] Ohsawa | Pinot: Speculative multi-threading processor architecture exploiting parallelism over a wide range of granularities[END_REF][START_REF] Warg | Improving speculative threadlevel parallelism through module run-length prediction[END_REF]; while intuitively appealing, it has not yet been very successful. A major reason for that is that it is very difficult to decide at run-time when speculation will be successful. Relying on run-time information has not offered much gain. On the other hand, limit studies have shown that there is indeed a wealth of parallelism to be exploited [START_REF] Hill | Amdahl's law in the multicore era[END_REF][START_REF] Steffan | The potential for using threadlevel data speculation to facilitate automatic parallelization[END_REF], therefore speculation as an approach should not be abandoned. Provided that we can apply speculation where it pays off, the upside is that we can use the higher amount of transistors to perform speculative execution of sequential software at radically larger scale than attempted before.

The pre-requisite however, in our opinion, is to strengthen the interface between high level software and hardware, so that hardware can utilize detailed semantic knowledge at large scale to support execution of single threaded applications and improve HW reliability. In this position paper we argue for using the possibilities offered by the design by contract paradigm -in terms of possible and/or realistic execution paths -coupled with speculative, run-ahead execution of sequential programs. We believe that such an approach can exploit chips with thousands of simple cores, running at lower speed for improving the performance of applications with limited amount of parallelism, without the need for rewriting the actual software. We will illustrate the potential of this technique by applying it to decoding Huffmanencoded streams,, a problem usually considered embarrassingly sequential. We will show that significant speedup can be achieved using thread-level speculation within a fixed power budget and without actually re-writing the sequential version of the algorithm.

Relevant previous work includes the Galois system [START_REF] Kulkarni | Optimistic Parallelism Requires Abstractions[END_REF], which provides a mechanism for expressing and exploiting semantic commutativity; the software behavior oriented parallelization method [START_REF] Ding | Software Behavior Oriented Parallelization[END_REF] using programmer-defined or automatically detected possibly parallel regions as well as the copy or discard execution model [START_REF] Tian | Copy or Discard Execution Model for Speculative Parallelization on Multicores[END_REF] that provides a mechanism for low cost isolation of speculative, uncommitted data. These methods all fall short however of an approach to providing pervasive and varied semantic information to the run-time system.

. THE BUILDING BLOCKS

We build our proposal on two existing technologies that we will briefly introduce below: design by contract and speculative execution.

Design by contract

The concept of design by contract was introduced in the context of the Eiffel programming language (see [START_REF] Eiffel | The Language[END_REF]). Design by contract is a method for specifying logical constraints on software entities (e.g. functions) in terms of dependencies between variables, side effects, invariants etc. A contract is the formalization of obligations and benefits of a given software component, in terms of what does it expect, guarantee and maintain when it's executed. The original goal of the design by contract paradigm was to improve the reliability of software systems by providing means to verify that the execution is still consistent with a predefined set of conditions (or contracts).

Contracts may cover a wide range of conditions, such as

• Acceptable or unacceptable input values or types (e.g. to a function) • Return value types, meaning and ranges

• Side effects

• Pre-conditions and post-conditions

• Invariants

The key property of the design by contract paradigm is that it offers formal ways to pass semantic information on software components to the run-time system and HW.

Speculative Execution

Speculative execution has been explored extensively as a way to improve parallelism, both instruction-level parallelism (ILP) and thread-level parallelism (TLP) (e.g. [START_REF] Hammond | Data speculation support for a chip multiprocessor[END_REF][START_REF] Hammond | Transactional Memory Coherence and Consistency[END_REF][START_REF] Ohsawa | Pinot: Speculative multi-threading processor architecture exploiting parallelism over a wide range of granularities[END_REF][START_REF] Warg | Improving speculative threadlevel parallelism through module run-length prediction[END_REF]). One sub-branch of the research focused on data value prediction (e.g., [START_REF] Burtscher | Hybrid Load-Value Predictors[END_REF]), but with very limited results due to the large overhead in terms of logic, power and the high percentage of squashed execution branches.

We believe the main reason for limited success was that all previous approaches relied on methods -such as static code analysis, observation of dynamic behavior -that did not take into account semantic information that only the programmer could have provided. There has been only a very limited amount of research focusing on provision of semantic information to the HW (such as [START_REF] Shepelow | Scheduling on Heterogeneous Multicore Processors Using Architectural Signatures[END_REF]).

SEMANTIC INFORMATION DRIVEN SPECULATIVE EXECUTION 3.1 Overview

As the number of cores will continue to increase, while per-core frequency is likely to stagnate, speculative execution, especially data value prediction, will in our opinion, re-emerge as a candidate for speeding up execution of single-threaded applications. However, the key to success will lie in improving the semantic information the applications will be able to provide to the hardware; we believe this is an interesting new direction worth exploring. While there are certainly several ways of achieving this, we believe one of the promising approaches to consider is to exploit the possibilities offered by the design by contract paradigm. The main reason is that design by contract is a well established method that offers a suitable level of abstraction and formalism that can be translated into definitions that can be interpreted by the hardware.

Programming Model

The fundamental principle of our proposal is to associate with any software -even not parallelized applications -deployed on a multi-core chip, wherever it's needed, a set of contracts that capture semantic information in a formalized and HW readable manner. We believe the following types of contracts are the most relevant:

• Value ranges on input parameters, variables

• Relationships between parameters and variables (for example, "if x < 0 then y is always even and less than 20") • Accessed global, shared memory areas • Constraints on valid pointer values, valid types for dynamically typed parameters • Expected loop and array sizes, as well potential splitting options • Constraints on branch conditions

• Helper computations that can provide, based on input data, useful insights to the expected behavior of the system An important and useful enhancement (from speculative execution perspective) is the usage of probabilistic contracts (e.g. "with 95% probability, x is either 0, 1 or 2"). The goal is to provide as much as possible formalized semantic information to the runtime system and hardware. Instead of trying to parallelize the execution of the software, we aim to reduce the lead-time of the execution. We aim to achieve this by limiting the possible -or probable -scope of the next step in the execution of the software to a subset of possible branches and values that makes it feasible to preemptively execute all (or most) of these alternatives. This way, at the moment the respective piece of code comes to execution in the logical flow of the program the execution would have actually already taken place -and hence the software is sped up without being written in a parallel style or have been automatically parallelized.

For example, consider the code fragment written in C below. The #CONTRACT statements contain the semantic information the programmer provided, based on the actual problem that is being solved. If f1 is called with e.g. a = 5, the two contracts above the "for" statement will indicate that b will be 0, 1, 2, 3, 4 or 5, with a 90% probability and the for loop will have less than 10 iterations. Using this information, it's possible to spawn 60 speculative threads of execution, with a 16% success rate at 90% probability level. For inherently sequential applications this may lead to significant performance gains.

Much of the information provided in this simple example could be obtained through profiling; however, our contracts based approach provides the means to express more subtle, even data dependent relationships and constraints that cannot be derived through profiling, as we'll illustrate with the case study on Huffman decoding. One important such class of contracts is related to the commutability of operations (such as memory allocations): the fact that e.g. two memory allocations can be interchanged cannot be detected through profiling. // more code };

Compiler, Run-time System and HW

The first step in turning the semantic information encoded in the contracts into run-time information is compilation. The compiler shall turn the contracts into a separate chunk of code; depending on the nature of the contracts, the compiler may perform a static analysis of the constraints and turn those into a new set of contracts more suitable for execution. In any event, the outcome is a special program that will be allocated to one of the cores that we will call the contract analyzer core.

During run-time, the contract analyzer core will execute in loose synch with the actual code and will evaluate in advance the contracts relevant for the upcoming branch, loop or function call events and will identify a set of potential -or probable, in case of probabilistic contracts -execution paths that all fulfill the conditions defined in the contracts. Contracts may also instruct the HW how to split up computations, what could and what should not be executed in parallel.

The next step is to select a subset (ideally, all) of alternatives that can be executed in advance -this selection will depend on the number of available cores and can involve previous knowledge (such as previous executions of the same code segment). Once this selection is done, the selected alternatives are dispatched for execution on the available cores -we will call these speculative fibers. For each speculative fiber, a new contract analyzer core can be allocated and the same procedure performed in the limit of available cores. In the example from the previous chapter, if f1() is called with a = 4, the contract analyzer core can decide to execute 50 instances of f2 () (for b = 0, 1, 2, 3, 4 and x = 8), assuming there are so many cores available.

In order to perform speculative execution, two issues need to be addressed: permanent side effects (such as disk access and I/O operations) and duplication of memory areas. These are issues in any speculative approach such as transactional memory (e.g., [START_REF] Bobba | Performance Pathologies in Hardware Transactional Memory[END_REF][START_REF] Hammond | Transactional Memory Coherence and Consistency[END_REF]). However, in order to unlock significant amounts of parallelism, solutions must be scalable and energy efficient.

First, user interaction cannot be performed using speculative execution, hence functions performing user interactions -primarily input operations -cannot be subject to run-ahead execution. For output operations (terminal or disk) buffering followed by commit can be used.

Second, regarding memory, a method for quickly creating private memory contexts with same virtual address space needs to be used. This can be done through e.g. creating a private copy in the local cache of the core executing a speculative fiber of all memory areas accessed during speculative execution. The private memory context can be discarded and need not be committed to memory.

As the main thread of execution progresses, the contract analyzer core will refine the evaluation of contracts and may squash some of the speculative fibers if the pre-conditions are not valid anymore. Eventually, only one speculative fiber's result will be committed and the same process of run-ahead execution of potential alternatives based on contract evaluation will resume.

HW Architecture Considerations

This method clearly favors usage of simple, low speed cores for three main reasons:

• Speculative fibers are usually relatively simple pieces of code (one program-level function) • The larger number of cores are available, the higher the number of speculative fibers that can be executed in parallel • Simple, low frequency cores yield better power efficiency

An asymmetric multi-core architecture [START_REF] Hill | Amdahl's law in the multicore era[END_REF] with few powerful cores (running the main thread(s) of execution) coupled with several simpler cores (for running the speculative fibers) would be a suitable platform for the method we propose in this paper. The main issue that needs to be addressed is the replication of certain parts of the data memory for each speculative fiber. This will clearly require more onchip memory per core.

Potential speedup

Traditionally the issue related to speculative execution was the large number of squashed speculative fibers.

A theoretical model of the possible speedup that can be achieved through speculative execution -Amdahl's law for speculative hardware -provides the following formula:

Where:

• FTime(i): is the execution time of one function run (one execution instance) • M: total number of function runs

• SpecMiss: amount of speculative fibers that were squash (as % relative to single threaded execution) • N: total number of cores Applying a simplification (FTime(i)==Max(FTime(i)), the formula becomes

In practice, if we can keep SpecMiss constant -not dependent on N -we can achieve linear speedup of sequential applications without the need of re-writing.

The key insight we promote in this paper is the expansion of speculative execution to application level functions and pervasive usage of programmer provided, fine-grained, formalized semantic information -conveyed through contracts -in order to dramatically improve the accuracy of the selection of speculative fibers.

IMPROVING HW RELIABILITY

It is probable that HW will be increasingly unreliable. We argue that contracts based approaches can be used to mitigate this unreliability as well. We propose a statistical voting scheme, whereas software would always be executed on multiple cores and the result most often generated would be chosen as the correct answer. This fits clearly into the context of design by contract driven speculative execution, by defining the contract as the 'the result must be the dominant result from multiple executions'. Applications can provide additional semantic information in forms of contracts to steer the HW for electing the correct result.

CASE STUDY: PARALLEL HUFFMAN DECODING

Huffman coding [START_REF] Huffman | A method for the construction of minimum redundancy codes[END_REF] is one of the oldest, but still widely used lossless compression algorithms, e.g. in image and video compression (as part of the JPEG and MPEG formats). It relies on building a binary tree where leafs represent symbols from the data that is being compressed; characters with higher frequency are closer to the root, while those with lower frequency are deeper down. Each symbol is assigned a code based on the path to the corresponding leaf from the root: left path means '0', right one means '1'. In short the algorithm relies on assigning shorter codes for more frequent symbols.

Traditionally, decoding of Huffman-encoded streams is considered hard to parallelize. Indeed, it's impossible to split up the compressed stream into chunks, as there are no reliable ways to detect where a new code starts. Previous proposals ( [START_REF] Klein | Parallel Huffman Decoding with Applications to JPEG Files[END_REF], [START_REF] Tsai | A Low-Latency Multi-Layer Prefix Grouping Technique for Parallel Huffman Decoding of Multimedia Standards[END_REF]) relied on re-designed algorithms, either exploiting that the decompression will re-synchronize or on carefully designed coding schemes that partitioned the code tree into independent structures. All these methods required however re-design of the basic algorithm.

Prior work closest to our proposal is in [START_REF] Prabhu | Safe Programmable Speculative Parallelism[END_REF]. The method described therein relies on programmer provided prediction functions that predict the likely outcome of the execution of a subset of the program in order to guide the speculative execution of the second part. When applied to the Huffman decoding algorithm, this method is similar to [START_REF] Klein | Parallel Huffman Decoding with Applications to JPEG Files[END_REF] and requires modification of the code. In addition, it only provides a prediction mechanism and no other semantic input to speculative execution.

We propose an approach where the basic decoding algorithm is not modified at all; instead, we annotate it with semantic information in form of contracts that the run-time system can exploit for parallel execution.

Identifying semantic information and contracts

The fundamental question we need to answer is what kind of semantic information could the programmer provide to the run-time system and the hardware that would help speeding up the algorithm?

Even if it's difficult to detect the boundary between two consecutive codes, the programmer knows that it certainly occurs within a bit-range equal to the length of the longest code (corresponding to the least frequent symbol). For example, if the largest code is 12 bits long, within a range of 12 bits of the compressed stream, there will certainly be at least one inter-code boundary. Using a probabilistic approach, the bit-range for different frequency levels of input symbols can also be calculated; for example, our experiments with different types of texts (scientific, novel and the complete Bible) show that even for maximum code lengths of 19 bits, code lengths of up to 7 already cover 95% of all symbols, while code lengths of up to 9 cover 99% of all symbols (see Figure 1 for the statistics obtained from compressing the complete Bible)

Code length vs Frequency

Based on this observation, the task of decoding a Huffman encoded stream may be parallelized by splitting the stream up into several (equal-sized) chunks of compressed code (into several streams); however, to address the issue of unknown code boundaries, for each chunk (except the first one), a number of speculative fibers would be spawned (depending on the desired probability level: in the example above, 7 for a probability level of 95%), each starting at a specific bit position. At least one of these will start at the right position (with e.g. 95% probability), and, since it's executed in parallel with the rest will speed up of decoding.

Thus, a contract expressing the above approach will look like this (using an intuitive pseudo-code description): Speculative fibers may be squashed earlier by exploiting the resynchronization characteristic of the Huffman code. The programmer may provide a third contract that checks the results of fibers acting on the same chunk and if two or more of these produce exactly the same result, all but one may be terminated in advance.

#CONTRACT #

Performance evaluation

Our experiments with various input data sets have shown that, even at only about 95% probability level, there was always at least one fiber (and, in many cases, several fibers, due to frequent short -3 or 4 bitcodes) that was started at the right position. We ran experiments where we split the compressed stream into 2, 4 and 8 chunks respectively, each executed on 7 speculative fibers; the result was the same for even the largest data set (at close to 4MB of input data), hence a speedup of 100% (two chunks), 300% (four chunks) and 700% (eight chunks) can be obtained.

However, this comes at a cost: the method requires an increasing number of additional cores to achieve this speedup. (for N chunks and seven fibers, the method needs (N-1)*7 + 1 cores, thus 8 cores for 2 chunks, 22 cores for 4 chunks, 50 cores for 8 chunks). This obviously highlights one of the drawbacks generally ascribed to speculative execution: waste of (computational and electric) power.

To run the fibers, there is no need for complicated cores. The fibers will act on relatively small pieces of data that could even fit into the core-local cache, thus some features -such as HW threads, out-of-order execution, ILP support etc -can be left out. Therefore, we assume that cores on which the fibers execute can be significantly more power efficient than the original core, at the same frequency and voltage level. In addition, we can apply frequency and voltage scaling to further reduce the power consumption. Table 1 shows the estimated speedup that can be obtained while keeping the power constant and assuming a factor of 8x better power efficiency for simpler cores. Assuming two chunks and eight simple cores, we note that a speedup of two can be obtained without increasing power consumption. If we consider ten chunks and 64 simple cores, a speedup of 16 is possible but that would increase the power consumption. By applying frequency-voltage scaling with a factor 0.5 we can keep the power consumption at the same level but enjoy a speedup of eight.

These estimations indicate that our method can lead to significant speedup, in case sufficient amount of simpler cores is available, without re-writing the application. These calculations do not take into account the potential savings due to early squashing of speculative fibers.

SUMMARY AND FUTURE RESEARCH

In this position paper we argue for research into speculative execution coupled with fine-grained, formalized and pervasive semantic information provided by the application in terms of contracts. By reducing the number of squashed speculative fibers, we believe we can open up for a new approach to parallel programming that does not require parallelization, but enables scaling of performance with the number of cores. Our preliminary experiments indicate that this is possible, showing good speedup on a problem traditionally considered hard to parallelize.

There are several new directions to pursue: exploit semantic information provided by applications, make the speculative execution much more coarse grained (application level functions) and deploy machine learning techniques for improving accuracy.

  unsigned f1(unsigned a) { unsigned y[50]; unsigned x, b; // some code #CONTRACT x < 2*a #CONTRACT b <= a PROBABILITY 90% for (i = 1; i <= x; i++) y[i] = f2( b * i);

Figure 1

 1 Figure 1 Code length versus frequency of symbols for the complete Bible

  Table 1Estimated speed-up factors at different power levels

	Speculative fibers per
	chunk:		7
			Speedup		Speedup
		Required	without	Freq.	at same
	Number	number of	power	reduction	power
	of chunks	cores	saving	multiplier	level
	2	8	2	1	2
	4	22	4	0,71	2,84
	8	50	8	0,54	4,32
	10	64	16	0,5	8