David Nellans
email: dnellans@cs.utah.edu

Kshitij Sudan
email: kshitij@cs.utah.edu

Erik Brunvand

Rajeev Balasubramonian
email: rajeev@cs.utah.edu

Improving Server Performance on Multi-Cores via Selective Off-loading of OS Functionality

Modern and future server-class processors will incorporate many cores. Some studies have suggested that it may be worthwhile to dedicate some of the many cores for specific tasks such as operating system execution. OS off-loading has two main benefits: improved performance due to better cache utilization and improved power efficiency due to smarter use of heterogeneous cores. However, OS off-loading is a complex process that involves balancing the overheads of off-loading against the potential benefit, which is unknown while making the off-loading decision. In prior work, OS off-loading has been implemented by first profiling system call behavior and then manually instrumenting some OS routines (out of hundreds) to support off-loading. We propose a hardware-based mechanism to help automate the off-load decision-making process, and provide high quality dynamic decisions via performance feedback. Our mechanism dynamically estimates the off-load requirements of the application and relies on a run-length predictor for the upcoming OS system call invocation. The resulting hardware based off-loading policy yields a throughput improvement of up to 18% over a baseline without off-loading, 13% over a static software based policy, and 23% over a dynamic software based policy.

I. INTRODUCTION

In the era of plentiful transistor budgets, it is expected that processors will accommodate tens to hundreds of processing cores. Given the abundance of cores, it may be beneficial to allocate some chip area for special-purpose cores that are customized to execute common code patterns. One such common code is the operating system (OS). Some prior studies [START_REF] Chakraborty | Computation Spreading: Employing Hardware Migration to Specialize CMP Cores On-the-Fly[END_REF], [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF], [START_REF] Nellans | A Case for Increased Operating System Support in Chip Multi-Processors[END_REF] have advocated that selected OS system calls be offloaded to a specialized OS core. This can yield performance improvements because (i) user threads need not compete with the OS for cache/CPU/branch predictor resources, and (ii) OS invocations from different threads interact constructively at the shared OS core to yield better cache and branch predictor hit rates. Further, in a heterogeneous chip multiprocessor, the OS core could be customized for energy-efficient operation because several modern features (such as deep speculation) have been shown to not benefit OS execution [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF], [START_REF] Nellans | A Case for Increased Operating System Support in Chip Multi-Processors[END_REF].

Hardware customization for OS execution has high potential because the OS can constitute a dominant portion of many important workloads such as webservers, databases, and middleware systems [START_REF] Chakraborty | Computation Spreading: Employing Hardware Migration to Specialize CMP Cores On-the-Fly[END_REF], [START_REF] Nellans | A Case for Increased Operating System Support in Chip Multi-Processors[END_REF], [START_REF] Redstone | An Analysis of Operating System Behavior on a Simultaneous Multithreaded Architecture[END_REF]. These workloads are also expected to be dominant in future datacenters and cloud computing infrastructure, and it is evident that such computing platforms account for a large fraction of modernday energy use [START_REF]Report To Congress on Server and Data Center Energy Efficiency -Public Law[END_REF]. In these platforms, many different virtual machines (VMs) and tasks will likely be consolidated on simpler, many-core processors [START_REF] Barroso | The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines[END_REF], [START_REF]Report To Congress on Server and Data Center Energy Efficiency -Public Law[END_REF]. Not only will the applications often be similar to existing applications that have heavy OS interaction, the use of VMs and the need for resource allocation among VMs will inevitably require more operating system (or privileged) execution.

The OS off-load approach has only recently come under scrutiny and more work is required to fully exploit its potential, including a good understanding of server/OS workloads in datacenters, evaluating the impact of co-scheduled VMs, technologies for efficient process migration, technologies for efficient cache placement and cache-to-cache transfers, etc. The work by Brown and Tullsen [START_REF] Brown | The Shared-Thread Multiprocessor[END_REF], for example, attempts to design a low-latency process migration mechanism that is an important technology for OS off-load. Similarly, in this paper we assume that OS off-load is a promising approach and we attempt to resolve another component of OS off-load that may be essential for its eventual success, viz, the decision-making process that determines which operations should be off-loaded. While OS off-load has a significant energy advantage [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF], this paper primarily focuses on the performance aspect. We expect that our proposed design will also be useful in an off-loading implementation that optimizes for energy efficiency.

Past work has demonstrated the potential of OS off-load within multi-cores for higher performance [START_REF] Chakraborty | Computation Spreading: Employing Hardware Migration to Specialize CMP Cores On-the-Fly[END_REF] and energy efficiency [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF]. In these works, the fundamental mechanism for OS isolation, off-loading, remains the same. Off-loading implementations have been proposed that range from using the OS' internal process migration methods [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF], to layering a lightweight virtual machine under the OS to transparently migrate processes [START_REF] Chakraborty | Computation Spreading: Employing Hardware Migration to Specialize CMP Cores On-the-Fly[END_REF]. In these studies, the decision process of which OS sequences to off-load has been made in software, utilizing either static offline profiling or developer intuition. This process is both cumbersome and inaccurate. Firstly, there are many hundreds of system calls, as seen in Table I, and it will be extremely time-consuming to manually select and instrument candidate system calls for each possible OS/ hardware configuration. Secondly, OS utilization varies greatly across applications and off-loading decisions based on profiled averages will be highly sub-optimal for many applications.

This paper attempts to address exactly this problem. We only focus on performance optimization with OS off-loading on a homogeneous CMP. We contribute to the existing body of work by proposing a novel hardware mechanism that can be employed on nearly any OS/hardware combination. At runtime, we dynamically estimate the level of off-loading that will be most beneficial for the application. Off-loading involves non-trivial interactions: reduced cache/branch predictor interference for the user thread, more cache coherence misses for the OS and user, overhead for off-load, queuing delay at the OS core, etc. We must therefore first estimate how aggressive the off-loading mechanism needs to be and then estimate if each OS invocation should be off-loaded. At the heart of our proposed scheme is a predictor that accurately estimates the length of upcoming OS sequences. We show that such a hardware-based scheme enables significant benefits from off-loading, out-performing static software instrumentation as well as a similar dynamic instrumentation in software. It also greatly simplifies the task of the OS developer, while incurring only a minor hardware storage overhead of about 2 KB.

A related alternative to off-loading is the dynamic adaptation of a single processor's resources when executing OS sequences [START_REF] Li | Operating System Power Minimization through Run-time Processor Resource Adaptation[END_REF], [START_REF]OS Execution on Multi-Cores: Is Out-Sourcing Worthwhile?[END_REF]. While the dynamic adaptation schemes do not rely on off-loading, the decision making process on when to adapt resources is very similar to that of making offloading decisions. We therefore expect the proposed prediction mechanisms to be useful for other forms of OS optimization as well, although this is not evaluated in the paper.

II. BACKGROUND AND MOTIVATION

Historical Perspective. Off-loading execution from a traditional general purpose microprocessor is not a new idea. For instance, in the 1980's floating point hardware often existed as a co-processor that could be plugged into an additional socket on many motherboards. This essentially amounted to offloading floating-point execution. Until recently, the memory controller for the DRAM sub-system was implemented in the north-bridge, but recent CPUs now have an integrated memory controller. Graphics rendering can be done entirely within software on the CPU, or it can be sent to a dedicated video card that can render polygons more efficiently due to a (vastly) different microarchitecture. Given the abundance in transistors today, off-loading within a multi-core can be attempted as a design optimization for common code patterns such as the operating system.

Benchmarks. For this work we examine a broad variety of workloads to examine the effect that OS interference has on cache performance. We look at a subset of benchmarks from the PARSEC (blackscholes, canneal) [START_REF] Benia | The PARSEC Benchmark Suite: Characterization and Architectural Implications[END_REF] , BioBench (fasta protein, mummer) [START_REF] Albayraktaroglu | BioBench: A Benchmark Suite of Bioinformatics Applications[END_REF], and SPEC-CPU-2006 (mcf, hmmr) [START_REF] Henning | SPEC CPU2006 Benchmark Descriptions[END_REF] suites as representative of HPC compute bound applications. Apache 2.2.6 serving a variety of static webpages selected at random by a serverside CGI script, SPECjbb2005 (a middleware-type system), and Derby (a database workload from the SPECjvm2008 suite) comprise our server oriented workloads. Our server benchmarks map two threads per core except Apache which self tunes thread counts to optimize throughput. This 2:1 mapping allows workloads that might stall on I/O operations to continue making progress, if possible.

All benchmarks were warmed up for 50 million instructions prior to being run to completion within the region of interest, using throughput as the performance metric. For single threaded applications, throughput is equivalent to IPC. In many experiments, the group of compute bound applications displays extremely similar behavior. For the sake of brevity, we represent these applications as a single group in our graphs, and note any outlier behavior.

Off-loading Decisions and Instrumentation Cost. We view the work by Chakraborty et al. [START_REF] Chakraborty | Computation Spreading: Employing Hardware Migration to Specialize CMP Cores On-the-Fly[END_REF] and Mogul et al. [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF] as the state-of-the-art in OS off-loading. In both of these works, off-line profiling and developer intuition is used as a guide to identify what are typically long-running system calls. These system calls are then manually instrumented so that their invocation results in a process migration from the application's core to a dedicated OS core. The reverse migration is performed when the system call completes.

Previous proposals [START_REF] Chakraborty | Computation Spreading: Employing Hardware Migration to Specialize CMP Cores On-the-Fly[END_REF] have involved a VMM to trap OS execution and follow a static off-loading policy based on offline profiling. Manual instrumentation of the code can allow the decision-making process to be smarter as the length of that specific system call invocation can be estimated based on input arguments [START_REF] Li | Understanding and Improving Operating System Effects in Control Flow Prediction[END_REF], [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF]. For example, the duration of the read system call is a function of the number of bytes to be fetched from a file descriptor offset and thus can vary across invocations. Even such instrumentation has several short-comings. In some cases, the read syscall may return prematurely if end-offile is encountered (for other syscalls too, the input arguments may not always be good predictors of run length). In yet other cases, the system call may be preempted by an additional long OS sequence initiated by a external device interrupt. The above effects cannot be accurately captured by instrumentation alone. Therefore, even sophisticated instrumentation can often be inaccurate. A history based predictor of OS run-length has the potential to overcome these short-comings.

We frequently see one or both of the following patterns: (a) an application that invokes many short OS routines, (b) an application that invokes few, but long running, routines. Depending on the application, reduced cache interference may be observed by off-loading one or both classes of OS routines. As we show later in the Section V, contrary to what intuition might indicate, it is often beneficial to off-load short system calls, even those with shorter duration than the off-loading migration overhead. When short system calls are also considered as candidates for off-loading, the overhead of instrumentation greatly increases. The latency cost of instrumentation code can range from just tens of cycles in basic implementations to Runtime overhead of dynamic software instrumentation for all possible OS off-loading points hundreds of cycles in complex implementations. This overhead is incurred even when instrumentation concludes that a specific OS invocation should not be off-loaded. As an example, we instrumented the simple getpid syscall implementation in OpenSolaris. We found that adding a single off-loading branch that invokes off-loading functionality based on a static threshold, increases the assembly instruction count from 17 to 33 for this trivial instrumentation. Examining multiple register values, or accessing internal data structures can easily bloat this overhead to hundreds of cycles which quickly penalizes performance. Figure 1 shows the significant performance impact of instrumenting all OS entry points for the server and compute bound workloads.

The above arguments highlight that profile-based manual instrumentation is not only burdensome, it also significantly limits the potential of the off-loading approach. The upcoming sections show how hardware-based single-cycle decision making can out-perform a couple of reasonable static instrumentation policies.

Migration Implementations. The latency and operations required for off-loading are significantly impacted by the migration implementation, which depends on both hardware and software capabilities. There are other alternatives to process migration, however, such as remote procedure calls, and message passing interfaces within the operating system.

These alternate designs have the potential to lower inter-core communication cost substantially and are an interesting design point though we do not consider them in this study. For some research operating systems [START_REF] Baumann | The Multikernel: A new OS architecture for scalable multicore systems[END_REF], [START_REF] Hunt | Singularity: rethinking the software stack[END_REF], the notion of off-loading is not even valid, as sub-systems are already pinned to specific processors within a CMP system. However, no mainstream OS has chosen to implement such features yet and by far, the majority of server applications are run on traditional Unixbased systems. In this study, we attempt to be agnostic to the mechanism by which off-loading is performed and show results for a variety of possible off-loading overheads.

While our study evaluates several design points for offloading overheads, we focus most of our conclusions on the conservative and aggressive design points. The conservative scheme is based on the thread migration time of approximately 5,000 cycles for an unmodified Linux 2.6.18 kernel. Proposals exist that could improve this delay to below just below 3,000 cycles on our target machine [START_REF] Strong | Fast Switching of Threads Between Cores[END_REF]. Reliable thread migration entails interrupting program control flow on the user processor and writing architected register state to memory. The OS core must then be interrupted, save its own state if it was executing something else, read the architected state of the user core from memory, and resume execution. If there is data in cache on the user processor that must be accessed by the OS core, it must be transferred to the OS core (automatically handled by the coherence mechanism). The aggressive scheme is based on a technique proposed by Brown and Tullsen [START_REF] Brown | The Shared-Thread Multiprocessor[END_REF] and is assumed to incur a 100 cycle migration latency. They advocate hardware support for book-keeping and thread scheduling utilizing an in hardware state machine, (a process normally done in software by an OS or virtual machine).

III. HARDWARE-BASED DECISION-MAKING

Instead of a software instrumentation process based on profiled analysis, we propose a hardware-based mechanism that simplifies the task of the OS developer and makes high quality decisions about the benefits of off-loading OS execution. Offloading leads to several complex interactions. First, it isolates the working sets of the application and the OS by placing most of the application's data in its own cache and most of the OS' data in the OS core's cache. This reduces cache and branch predictor interference at the user core. It also increases the likelihood that an OS system call will find its data in cache because a similar function was recently executed (not necessarily by the invoking application). Second, the number of coherence misses may increase because the OS system call may have to access application data (that resides in the application core's cache) and conversely, the application may have to access data recently fetched by the OS syscall (that resides in the OS core's cache). These interactions are a strong function of system call length and frequency. Performance is also impacted by the overheads for migration and because of queuing delays at the OS core (since a single OS core could handle requests from multiple application cores). Many of the above effects are not easily captured with performance counters, and even if they were, it may be difficult to construct models that relate these parameters to an eventual decision regarding the benefits of off-loading the system call being currently invoked. We therefore adopt a simplified but effective approach that is based on the following two sub-components.

We adopt the simple strategy that a system call will be off-loaded if it is expected to last longer than a specified threshold, N cycles. The first sub-component employs a hardware predictor to estimate the length of a system call. At any point, we also need to determine best best value for N . This may vary depending on how closely the application and OS interact and on whether coherence effects dominate over other cache interference effects. The second sub-component of the proposed scheme determines the N value which provides best performance by sampling various candidate values.

A. Hardware Prediction of OS Syscall Length

We believe that system call run-length is the best indicator of whether off-loading will be beneficial. This is simply because the overhead of migration is amortized better if the system call is longer. The length of the syscall is often a function of the input arguments and processor architected state. We therefore propose a new hardware predictor of OS invocation length that XOR hashes the values of various architected registers. After evaluating many register combinations, the following registers were chosen for the SPARC architecture: PSTATE (contains information about privilege state, masked exceptions, FP enable, etc.), g0 and g1 (global registers), and i0 and i1 (input argument registers). The XOR of these registers yields a 64-bit value (that we refer to as AState) that encodes pertinent information about the type of OS invocation, input values, and the execution environment. Every time there is a switch to privileged execution mode, the AState value is used to index into a predictor table that keeps track of the invocation length the last time such an AState index was observed, as shown in Figure 2.

Each entry in the table also maintains a prediction confidence value, a 2-bit saturating counter that is incremented on a prediction within ±5% of the actual, and decremented otherwise. If the confidence value is 0, we find that it is more reliable to make a "global" prediction, i.e., we simply take the average run length of the last three observed invocations (regardless of their AStates). This works well because we observe that OS invocation lengths tend to be clustered and a global prediction can be better than a low-confidence "local" prediction. For our workloads, we observed that a fullyassociative predictor table with 200 entries yields close to optimal (infinite history) performance and requires only 2 KB storage space. The 200-entry table is organized as a CAM with the 64-bit AState value and prediction stored per entry. A direct-mapped RAM structure with 1500 entries also provides similar accuracy and has a storage requirement of 3.3 KB. This table is tag-less and the least significant bits of the AState are used as the index.

Averaged across all benchmarks, this simple predictor is able to precisely predict the run length of 73.6% of all privileged instruction invocations, and predict within ±5% the actual run length an additional 24.8% of the time. Large prediction errors most often occur when the processor is executing in privileged mode, but interrupts have not been disabled. In this case, it is possible for privileged mode operation to be interrupted by one or more additional routines before the original routine is completed. Our predictor does not capture these events well because they are typically caused by external devices which are not part of the processor state at prediction time. These prediction inaccuracies are part of nondeterministic execution and can not be foreseen by software or other run length prediction implementations. Fortunately, these interrupts typically extend the duration of OS invocations, almost never decreasing it. As a result, our mispredictions tend to underestimate OS run-lengths, resulting in some OS offloading possibly not occurring, based on a threshold decision. While the hardware predictor provides a discrete prediction of OS run-length, the off-load decision must distill this into a binary prediction indicating if the run length exceeds N instructions and if core migration should occur. Figure 3 shows the accuracy of binary predictions for various values of N . For example, if off-loading should occur only on OS invocation run lengths greater than 500 instructions, then our predictor makes the correct off-loading decision 94.8%, 93.4%, 96.8%, and 99.6% of the time for Apache, SPECjbb2005, Derby and the average of all compute benchmarks, respectively. While more space-efficient prediction algorithms possibly exist, we observe little room for improvement in terms of predictor accuracy.

B. Dynamic Estimation of N

The second component of a hardware assisted off-loading policy is the estimation of N that yields optimal behavior in terms of say, performance or energy-delay product (EDP). This portion of the mechanism occurs within the operating system at the software level so that it can utilize a variety of feedback information gleaned from hardware performance counters. Execution of this feedback occurs on a coarse granularity however, typically every 25-100 million cycles. As a result, the overhead is minimal compared to software instrumentation of system calls which can be invoked as often as every few thousand cycles in OS intensive applications.

For this estimation of N , we rely on algorithms described in past work to select an optimal hardware configuration [START_REF] Balasubramonian | Dynamically Managing the Communication-Parallelism Trade-Off in Future Clustered Processors[END_REF]. If the hardware system must select one of a few possible N For our implementation, where performance is our metric of interest, we use the L2 cache hit rate of both the OS and user processors, averaged together, as our performance feedback metric. Our initial sampling starts with an epoch of 25 million instructions, and an off-loading threshold of N = 1, 000 if the application is executing more than 10% of its instructions in privileged mode, otherwise the threshold is set to N = 10, 000. We also sample values for two alternate N , above and below the initial N . If either of these N results in an average L2 hit-rate that is 1% better than our initial N , we set this new value as our threshold. Having chosen an initial threshold value, we then allow the program to run uninterrupted for 100 M instructions. We then again perform a 25 M instruction sampling of two alternate values of N . If our threshold appears to still be optimal we then double the execution length (to 200 M) instructions before sampling again to help reduce sampling overhead. If at any point our current N is found to be non-optimal, the execution duration is reduced back to 100 M instructions.

Such a mechanism can work poorly if phase changes are frequent. If this is the case, the epoch length can be gradually increased until stable behavior is observed over many epochs. Such a strategy was not invoked for most of our benchmark programs as few phase changes were encountered for epochs larger than 100 million instructions. For our experiments, we use very coarse-grained values of N (as later reported in Figure 4). Increasing the resolution at which N can vary will increase the performance of the system, but it comes at the expense of increased sampling overhead.

IV. EXPERIMENTAL METHODOLOGY

To examine the design space of OS off-loading we use cycle accurate, execution driven simulation to model full OS execution during workload execution. Our simulation infrastructure is based on Simics 3.0 [START_REF] Magnusson | Simics: A Full System Simulation Platform[END_REF] and we model in-order UltraSPARC cores. By modeling in-order cores, we are able to simulate large executions in a reasonable amount of time, thus capturing representative OS behavior. It also appears that many OS-intensive server workloads are best handled by inorder cores with multi-threading [START_REF] Redstone | An Analysis of Operating System Behavior on a Simultaneous Multithreaded Architecture[END_REF] (for example, the Sun Niagara and Rock designs and the recent Intel Atom design).

On the SPARC platform, the PSTATE register [START_REF]The SPARC Architecture Manual Version 9[END_REF] holds the current state of the processor and contains information (in bit fields) such as floating-point enable, execution mode (user or privilege), memory model, interrupt enable, etc. Our proposed techniques use the execution mode bit in this register to determine which code sequences are executing within the boundaries of the OS. Based on this definition, system calls which occur in privileged mode but within the user address space are captured as part of our OS behavior in addition to functionality that occurs within the kernel address space. Thus, compared to prior work, we are considering a broader spectrum of OS behavior as a candidate for off-loading. Previous work examined only system calls, or a subset of them; we show that optimal performance can be obtained by off-loading OS sequences that are much shorter than intuition might indicate. Therefore, a general-purpose solution for capturing all OS execution is required.

The SPARC ISA has several unique features which cause many short duration (<25 instructions) OS invocations. These invocations are exclusively due to the fill and spill operations of the rotating register file the SPARC ISA implements when the register file becomes overloaded. Other architectures, like x86, perform stack push and pop operations in user space. We analyzed our results both including and excluding these invocations for SPARC ISA, and have chosen to omit these invocations from our graphs where they skew results substantially from what would be seen on an alternative architecture.

For all our simulations, Table II shows the baseline memory system parameters. Our timing parameters were obtained from CACTI 6.0 [START_REF] Muralimanohar | Optimizing NUCA Organizations and Wiring Alternatives for Large Caches with CACTI 6.0[END_REF] targeting a frequency of 3.5 GHz. A memory latency of 350 cycles is used in all experiments (based on real machine timings from Brown and Tullsen [START_REF] Brown | The Shared-Thread Multiprocessor[END_REF]). In the case of off-loading, we simulate two such cores with private L2s which are kept coherent via a directory based protocol and a simple point-to-point interconnect fabric (while this is overkill for a 2-core system, we expect that the simulated model is part of a larger multi-core system). Our system models directory lookup, cache-to-cache transfers, and coherence invalidation overheads independently. We parameterize the migration implementation so that we can examine the effects of varied latency implementations on the off-loading decision policy.

V. RESULTS

A. Impact of Design Parameters

We next evaluate the off-loading performance achievable with our predictor-directed decision making policy. On every transition to privileged mode, the run-length predictor is looked up and off-loading occurs if the run-length is predicted to exceed N (we show results for various static values of N ). Figure 4 shows the IPC performance through off-loading, relative to a baseline that executes the program on a single 0.7 0.8 0.9 core. All results use our hardware based predictor and have just a single cycle instrumentation cost. A different graph is shown for Apache, SPECjbb2005, Derby, and compute-intensive programs. Each graph shows a static off-loading threshold N on the X-axis and a different curve for various one-way offloading latencies. Evaluating multiple off-loading latencies is important because they are highly implementation dependent and can range from 5,000 cycles in current operating system implementations, down to just a few hundred cycles in some recent research proposals [START_REF] Strong | Fast Switching of Threads Between Cores[END_REF]. Figure 4 helps identify 3 major trends about OS off-loading.

Off-loading latency is the dominant factor in realizing performance gains. Performance is clearly maximized with the lowest off-loading overhead possible. If the core migration implementation is not efficient, it is possible that off-loading may never be beneficial (see SPECjbb).

For any given off-loading latency, choosing the appropriate switch trigger threshold N is critical. When finding the optimal off-loading threshold N , two factors come into play, OS/User cache interference and cache coherence overheads. When the OS and user application execute on a single core, as has traditionally occurred, the working set of each is forced to compete for space in the cache. Off-loading has the potential to improve performance because we are effectively removing the accesses to OS working set from the cache. Thus, user cache hit-rates are maximized at N = 0.

The OS and application do not have completely independent working sets -much of their memory footprint is shared. This sharing occurs because the OS often performs operations such as I/O on behalf of the application and places the resulting data into the application address space. As a result, shared data that is written, can generate substantial coherence traffic between OS and User cores. As we move to low values for N , coherence traffic is also maximized because OS/User shared data is no longer in just a single cache.

For example, Figure 4 shows that even with a zero overhead off-loading latency, moving from N = 100 to N = 0 substantially reduces performance. This is because the cost of additional coherence invalidates and transfers overshadows any improvements in cache hit-rate. Because the relationship between coherence and cache interference can vary from application to application, it is not possible to globally determine the point N at which off-loading performance is maximized. A dynamically adjusting system utilizing performance feedback is required.

Off-loading short OS sequences is required. We are somewhat surprised to see that maximum performance occurs when off-loading OS invocations as short as 100 instructions long. This indicates that though long duration invocations dominate the total OS instruction count, short frequent invocations also have a large impact on cache interference for some benchmarks. This implies that any software-based decision policy that relies on OS code instrumentation must not only consider long-running system calls, but also shortrunning ones. This supports our belief that all OS entry points must be instrumented for off-loading, and in turn, that lowcost instrumentation, such as the hardware predictor presented here, is necessary for OS off-loading to be successful.

B. Comparing Instrumentation and Hardware Prediction

Having studied the behavior of the hardware predictor, we now compare our eventual hardware-based scheme against existing techniques that have relied on manual software instrumentation. Figure 5 provides a concise view of what we consider to be state of the art in OS off-loading. We present normalized throughput results for an off-loading latency of 5,000 cycles (Conservative), that is currently available, as well as 100 cycles (Aggressive) that has been proposed in research. Static instrumentation (SI) models a low overhead software instrumentation that uses off-line profiling to identify and statically instrument only those OS routines that are determined to have a run-length that is twice the off-loading (migration) latency. SI is very similar to the technique used by Chakraborty et al. [START_REF] Chakraborty | Computation Spreading: Employing Hardware Migration to Specialize CMP Cores On-the-Fly[END_REF]. Dynamic instrumentation (DI) models a more complex software instrumentation of all possible OS entry points and allows run-time decisions about the value of off-loading. DI is very similar to the technique used by Mogul et al. [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF], but differs in that all OS entry points are instrumented, as opposed to just those which are expected to have a long average run length. DI is the functional equivalent of the hardware prediction engine proposed in this paper, but implemented entirely in software. Finally, hardware instrumentation (HI) is the new hardware predictor based approach described in this work.

Figure 5 indicates that previous OS off-loading proposals were leaving substantial performance on the table by (i) not considering short OS sequences as candidates for offloading, and (ii) utilizing high overhead software instrumentation to make off-loading decisions. At currently achievable off-loading latencies, our hardware based off-loading decision policy can yield as much as 18% throughput improvement over a baseline without off-loading, and 13% improvement over previous software-based implementations. In the future, with faster migration implementations, the importance of a low overhead decision making policy will increase and our proposal can outperform software instrumentation by as much as 20%.

In our experiments, the single-core baseline has a single 1 MB L2 cache, while the off-loading models have two 1 MB L2 caches. This is a faithful model of how off-loading is expected to work in future multi-cores, and the additional cache space is a strong contributor to the high benefit from off-loading. It is worth noting that even an off-loading model with two 512 KB L2 caches can out-perform the single-core baseline with a 1 MB L2 cache if the off-loading latency is under 1,000 cycles. Such a comparison only has academic value however, as hardware designers are unlikely to cripple an existing processor design to enable off-loading.

C. Scalability of Off-loading

Table III shows the percentage of benchmark execution time that the OS core was active while running our server intensive benchmarks with a 5,000 cycle off-loading overhead. At an off-loading threshold of N = 10, 000 the OS core shows low utilization, but at N = 1000 and N = 100, the threshold where optimal performance is found for most benchmarks, the utilization quickly increases. This high rate of utilization indicates that, unfortunately, it is unlikely that multiple usercores will be able to share a single OS core successfully. To test this hypothesis we evaluated the scaling of a single OS core to two and four user cores using SPECjbb2005, under an off-loading threshold of N = 100 and an aggressive offloading overhead of 1,000 cycles. As a non-SMT core, if the OS core is handling an off-loading request when an additional request comes in, the new request must be stalled until the OS core becomes free. With just two user cores, there was an average queuing delay of 1,348 cycles in addition to the 1,000 cycle off-loading overhead. With four user cores, the average queuing delay for the OS core exploded to over 25,000 cycles as the OS core was inundated with off-loading requests. While L2 cache hit rates remained high in both scenarios, our user cores were often stalled waiting for the OS offloading to occur. As a result, the 2:1 ratio of User to OS cores saw only a 4.5% improvement in aggregate throughput, and performance was decreased substantially at the 4:1 ratio. We conclude that 1:1, or possibly 1:N, may be the appropriate ratio of provisioning OS cores in a many-core system.

VI. RELATED WORK

A. Impact of OS on System Throughput

There have been many studies on how operating system overhead affects the throughput of user applications (the eventual metric of interest). Gloy et al. [START_REF] Gloy | An Analysis of Dynamic Branch Prediction Schemes on System Workloads[END_REF], Anderson et al. [START_REF] Anderson | The Interaction of Architecture and Operating System Design[END_REF], and Agarwal et al. [START_REF] Agarwal | Cache Performance of Operating System and Multiprogramming Workloads[END_REF] have shown that operating system execution generates memory references that negatively impact the performance of traditional memory hierarchies. Redstone et al. [START_REF] Redstone | An Analysis of Operating System Behavior on a Simultaneous Multithreaded Architecture[END_REF] and Nellans et al. [START_REF] Nellans | A Case for Increased Operating System Support in Chip Multi-Processors[END_REF] have shown that there are important classes of applications, namely webservers, databases, and display intensive applications for which the OS can contribute more than half the total instructions executed.

Nellans et al. [START_REF] Nellans | A Case for Increased Operating System Support in Chip Multi-Processors[END_REF] and Li et al. [START_REF] Li | Operating System Power Minimization through Run-time Processor Resource Adaptation[END_REF] show OS execution under-performs user applications by 3-5x on modern out-oforder processors and suggest that OS code can be run on less aggressively designed processors to improve energy efficiency.

B. Hardware Support for Efficient OS Execution

Several groups have proposed that a class of OS intensive workloads combined with the proliferation of chip multiprocessors has led us to an architectural inflection point, where off-loading operating system execution may be beneficial for both performance and power efficiency. As already described, Chakraborty et al. [START_REF] Chakraborty | Computation Spreading: Employing Hardware Migration to Specialize CMP Cores On-the-Fly[END_REF] have proposed that some system calls should be selectively migrated to and executed on an alternate, homogeneous core within a CMP. This results in better cache locality in all cores, yielding higher server throughput without requiring additional transistors.

Mogul et al. [START_REF] Mogul | Using Asymmetric Single-ISA CMPs to Save Energy on Operating Systems[END_REF] recently proposed that some OS system calls should selectively be migrated to and executed on a microprocessor with a less aggressive microarchitecture. OS code does not leverage aggressive speculation and deep pipelines, so the power required to implement these features results in little performance advantage. While system calls are executing on the low-power OS core, the aggressively designed user core can enter a low-power state. When the OS routine has completed execution, the user core is powered back up and execution returns to the high performance user core while the OS core enters low-power state. This migration of OS execution to an energy-efficient core results in overall lower energy for the system.

Li et al. [START_REF] Li | Operating System Power Minimization through Run-time Processor Resource Adaptation[END_REF] take a slightly different approach to OS execution than other proposals. They propose that rather than implementing a secondary processor, existing uni-processors should be augmented so that aggressive out-of-order features can be throttled in the microarchitecture. By limiting the instruction window and issue width, they are able to save power during operating system execution. Similar to previous proposals, they still must identify the appropriate opportunities for microarchitectural reconfiguration to occur. Identification of reconfiguration opportunities has many of the same steps as off-loading identification. We believe our hardware-based decision engine could be utilized effectively for the type of reconfiguration proposed by Li et al.

VII. CONCLUSIONS

Off-load of OS functionality has promise in future multicores because it can afford better cache utilization and energy efficiency. While it has traditionally been assumed that offloading only makes sense for long OS executions, we show that the off-load of short sequences also contributes greatly to reduced cache interference. Prior work has implemented offloading with profile-guided software instrumentation. We show that such an approach is burdensome, incurs high overheads (especially when off-loading short sequences), and is often inaccurate. All of these problems are addressed by instead implementing a hardware tunable predictor that estimates the length of OS sequences and off-loads upon expected benefit.

The predictor has a storage overhead of only 2 KB and outperforms the best instrumentation policy by 13%. For future work, we plan to study the applicability of the predictor for OS energy optimizations.

  Fig. 1.Runtime overhead of dynamic software instrumentation for all possible OS off-loading points

Fig. 2 .

 2 Fig. 2. OS Run-Length Predictor With Configurable Threshold

Fig. 3 .

 3 Fig. 3. Binary Prediction Hit Rate for Core-Migration Trigger Thresholds

Fig. 4 .

 4 Fig. 4. Normalized IPC relative to uni-processor baseline when varying the off-loading overhead and the switch trigger threshold.

Fig. 5 .

 5 Fig.5. Normalized throughput (relative to a single-core baseline) for offloading with static manual instrumentation and off-loading with the hardware predictor.

TABLE I NUMBER

 I OF DISTINCT SYSTEM CALLS IN VARIOUS OPERATING SYSTEMS.

	Benchmark	# Syscalls	Benchmark	# Syscalls
	Linux 2.6.30	344	Linux 2.2	190
	Linux 2.6.16	310	Linux 1.0	143
	Linux 2.4.29	259	Linux 0.01	67
	FreeBSD Current	513	Windows Vista	360
	FreeBSD 5.3	444	Windows XP	288
	FreeBSD 2.2	254	Windows 2000	247
	OpenSolaris	255	Windows NT	211

TABLE III PERCENTAGE

 III OF TOTAL EXECUTION TIME SPENT ON OS-CORE USING SELECTIVE MIGRATION BASED ON THRESHOLD N

		Core Migration Threshold N
	Benchmark	100	1,000	5,000	10,000+
	Apache	45.75%	37.96%	17.83%	17.68%
	SPECjbb2005	34.48%	33.15%	21.28%	14.79%
	Derby	8.2%	5.4%	1.2%	0.2%


Mel Gorman

Patrick Healy
email: patrick.healy@ul.ie

Performance Characteristics of Explicit Superpage Support

Keywords: D.4 [Storage Management]: Virtual Memory General Terms Algorithms, Measurement, Performance superpage, fragmentation, replacement policy, TLB

Many modern processors support more than one page size. In the 1990s the larger pages, called superpages, were identified as one means of reducing the time spent servicing Translation Lookaside Buffer (TLB) misses by increasing TLB reach. Transparent usage of superpages has seen limited support due to architectural limitations, the cost of monitoring and implementing promotion/demotion, the uncertainity of whether superpages will be a performance boost and the decreasing cost of TLB misses due to hardware innovations. As significant modifications are required to transparently support superpages, the perception is that the cost of transparency will exceed the benefits for real workloads.

This paper describes how processes can explicitly request memory be backed by superpages that is cross-platform, incurs no measurable cost and is suitable for use in a general operating system. By not impacting base page performance, a baseline metric is established that alternative superpage implementations can compare against. A reservation scheme for superpages is used at mmap() time that guarantees faults without depending on pre-faulting, the fragmentation state of the system or demotion strategies. It is described how to back different regions of memory using explicit superpage support without application modification and present an evaluation of an implementation running a range of workloads.

Introduction

In the 1990s, it was observed that the Translation Lookaside Buffer (TLB) reach was shrinking as a percentage of physical memory and the relative amount of program time spent servicing TLB misses was increasing. Superpages were identified as one means of reducing TLB misses. Preferably it would be fully transparent to the application but there are significant obstacles that prevent transparent superpage support being properly adopted in mainstream operating systems for general applications. This paper begins by describing architectural limitations when translating addresses for multiple page sizes that have hindered transparent superpage support. As superpages typically require physically contiguous pages, the paper summarises some earlier work on controlling external fragmentation and page reclaim [START_REF] Gorman | Supporting superpage allocation without additional hardware support In ISMM '08[END_REF] as they are important pre-requisites for supporting superpages [START_REF] Talluri | Tradeoffs in supporting two page sizes[END_REF].

This paper then progresses this earlier work by describing a superpage reservation scheme that can be applied at mmap() time to guarantee future faults. This eliminates the need for pre-faulting or demotion strategies that are problematic on a number of architectures. These are prerequisites that must be addressed for reliable Explicit Superpage Support; a mechanism that exposes interfaces directly allowing loaders, libraries or applications to directly request superpages. It is shown that explicit superpage support can back memory regions without direct application modification through the use of libraries.

Over the course of the research, superpage support was implemented on Linux and merged into the mainline releases. This paper presents an evaluation of an implementation based on Linux using AMD R Phenom (X86-64) and POWER R (PPC64) processors. By tackling the fundamental problems of superpage support and enabling usage without application modification, this implementation represents a comparison point for transparent superpage support implementations on the same platform. There is an expectation that similar mechanisms could be implemented on other platforms.

Limitations of Transparent Support

There are architectural limitations to consider when implementing superpage support that is cross-platform. Limiting the number of architecture-specific paths reduces maintenance and test costs so the common architectural features must be supported before considering architecture-specific options. This section considers three architectures that make up 99.6% of the Top 500 Supercomputers [START_REF] Meuer | Top 500 Supercomputers List for November 2008[END_REF] list as being a reasonable cross-section of mainstream architectures. Understanding the limitations of two of these architectures in particular illustrate why fully transparent superpage support be problematic for cross-platform operating systems.

POWER R

POWER R occupies 3 of the top 10 spots in the Top 500 list, has a 12% share overall and occupies the top spot as part of a hybrid system [START_REF] Meuer | Top 500 Supercomputers List for November 2008[END_REF]. The current Power Architecture specification allows multiple page sizes but initially it only allowed two; a base and an implementation-specific large page size between 8KB and 256MB [START_REF] Wetzel | PowerPC Operating Environment Architecture Book III[END_REF]. With POWER4, the page sizes were 4K and 16MB with POWER5+ adding 64K and 16GB superpages. Unfortunately, in general1 the Memory Management Unit (MMU) requires the same superpage size be used within segments of either 256MB or 1TB virtual address range, thus hindering transparent superpage support. Promotion or demotion would require modifying the entire segment at once with is prohibitively expensive and makes transparent superpage support on POWER impractical.

Itanium R (IA-64)

Itanium maintains a 1.8% share of the Top 500 list and is used on very large single-image machines such as the SGI Altrix 4700 supporting up to 1024 processors on a single machine. The Itanium supports 11 different page sizes but the Itanium port of Linux has similar problems to POWER with respect to address translation that hinder transparent support.

Two mutually exclusive hardware-defined formats usable by page table walkers exist for Itanium called short-and long-format Virtual Hashed Page Table (VHPT); SF-VHPT and LF-VHPT respectively. SF-VHPT has a smaller cache-footprint but can only use one page size per region. As the 64-bit address space is divided into eight regions, this is a significant restriction as multiple pages can only be used within a region if the hardware page table walker is disabled -a significant penalty. The LF-VHPT has larger PTEs and is less cache friendly but potentially has a smaller TLB footprint and has no restrictions on superpage placement.

Linux favours SF-VHPT for two reasons that may be important to other platforms. Firstly, TLB-and-context-switch-intensive workloads are relatively rare and Linux has a policy of minimising cache usage. Secondly, the "hardware-independent" representation of page tables used by Linux is a 4-level hierarchical page table format which, if mapped in the correct place, can be used directly by the SF-VHPT hardware walker. LF-VHPT can still be used on Linux [START_REF] Wienard | Transparent Large-Page Support for Itanium Linux[END_REF] but with more expensive TLB reloads. As this can only be potentially offset by superpage usage, the move to the long-format is currently unjustified on that system. This severely limits the possibility of transparent support on the Itanium platform.

X86 Variants

(Intel R EM64T, AMD R X86-64)
X86 variants dominate the Top 500 list with a share of 73.8% for Intel EM64T and 12% for AMD X86-64. 2MB or 4MB superpages are supported depending on the address translation used. In 32bit mode, 4MB superpages are typically available unless Physical Address Extension (PAE) is enabled. If PAE or 64-bit mode is used, the superpage size is generally 2MB but some recent AMD processors also add a 1GB superpage size.

Due to how addresses are translated, there are limits on how many superpage sizes can be supported but no significant limit on where the superpages are placed. The difficulties for transparent support are two-fold, one hardware and one software. The TLB characteristics differ significantly between processor implementations. The Intel Pentium D, including Xeon variants, have fullyassociative TLBs. Others such as the Core Duo have set-associative TLBs with different numbers of entries for different page sizes. The AMD Phenom 9950 processor reports multiple TLBs with the L1 DTLB fully-associative and L2 DTLB set-associative. This degree of variation significantly complicates cost/benefit calculations regarding superpages.

The software problem is specific to Linux "open-coding" 4level page table traversal without checking the underlying page size instead of using an abstracted API. Transparent support is possible but implementing it incurs a performance cost. Before that cost is incurred, it must be established what the limits of explicit superpage support are.

Related Work

This section summarises some earlier work [START_REF] Gorman | Supporting superpage allocation without additional hardware support In ISMM '08[END_REF] that is a prerequisite for explicit superpage support. Architectural limitations generally require that superpages be naturally aligned and physically contiguous forcing the system to handle external fragmentation. Memory defragmentation is not a complete solution as wired pages exist that cannot move and may be scattered throughout the physical address space. Being able to move arbitrary pages is costly due to locking requirements and copying, both of which vary between architectures.

Page Allocation

Grouping Pages By Mobility [START_REF] Gorman | Supporting superpage allocation without additional hardware support In ISMM '08[END_REF] divides the physical address space into superpage-sized arenas. Different arena types exist based on a page's ability to move, be it by migration or reclamation noting that the number of arenas for each type changes based on demand. Each arena has its own free-lists so the search cost is similar to that of the standard allocator. The placement policy does not guarantee that a specific number of superpages can be allocated so the system's memory may also be partitioned. Arenas for wired pages are only ever created on one side of the partition guaranteeing that one partition can be filled with superpages by reclaiming or moving pages. On Non-Uniform Memory Access (NUMA) systems, the partition for wired pages is evenly divided on all nodes to avoid kernel accesses being frequently remote. On batch systems with workloads of varying requirements, the partition would be sized to the largest estimated number of superpages required. If superpages are not allocated, movable base pages still use the partition.

Page Reclaim

On allocation failure, Age-Biased Arena Reclaim [START_REF] Gorman | Supporting superpage allocation without additional hardware support In ISMM '08[END_REF] uses the normal page reclaim algorithm to select a reference page and reclaim the naturally aligned arena if all pages are free or reclaimable as likely will be the case due to the placement policy. This minimises disturbance of the normal page reclaim decisions made by the operating system

Superpage Reservation

Systems normally ensures successful faults by recording the number of pages required for existing mappings and refusing to create new mappings that exceed available memory and swap space. This is insufficient for superpages as contiguity requirements can fail a page fault due to external fragmentation. Faulting superpagebacked mappings at mmap() time would increase the cost of mmap() and perform poorly with Non-Uniform Memory Access (NUMA). Optimally on NUMA, CPUs always access pages local to the CPU without copying data between nodes. Pre-faulting places pages local to the thread calling mmap() and not necessarily local to the threads accessing the data, incurring costly cross-node accesses.

A better alternative is to reserve the superpages necessary to guarantee future faults at mmap() time. Counters track the current state of the system, some of which are tracked on a per-NUMAnode basis so that NUMA policies can be applied correctly.

When creating a new mapping, faulting a page within an existing mapping or unmapping an existing mapping, it is determined how many pages have already been allocated or reserved. For example, pages for shared mappings may already have been allocated or a reserve created by another process. Searching the page cache or page tables for references to allocated pages would be unsuitably expensive. Instead, each mapping is treated as a file. Shared mappings of data use one file whereas private mappings have their own unique file. Each file is associated with one or more struct file region stored on a linked list and defined as follows.

struct file_region { struct list_head link; long from, to; };

The size of the file in superpages is the initial required reservation to succeed all future faults. Each file region on the list implies that to -from reserved pages have been used.

Due to the fact that shared and private mappings are accounted differently, there are differences in the run-time behaviour of an application using shared or private mappings backed by superpages.

Shared Mapping Accounting

Shared mappings reservations for the same data are based on the largest mapping created by any process i.e. the size of the file. The file region is associated with one shared structure such as an inode. On fault, the page cache is searched and the page inserted into the processes page tables if it exists, otherwise the page is allocated, inserted into both page cache before updating the reservations, file region structures and inserting into the page table.

Private Mapping Accounting

Private mappings always reserve superpages for the entire mapping as even existing pages require new pages for a Copy-On-Write (COW) fault. Read-only private mappings could avoid reserving until mprotect() was called but applications may not correctly handle mprotect() errors if the reserve could not be made. Due to the per-mapping nature of the reservation, the file region is linked to the virtual area management structure (struct vm area struct in Linux).

fork() presents a difficulty. Shared mappings can use the same pages and reservations between parent and child but it is unknowable how many superpages a child will need for private mappings. Duplicating reservations on fork() is expensive, may be impossible and impacts applications calling exec() after fork().

An alternative is to only guarantee faults within the address space that created the mapping. A child process's mappings have no reservations but on fault, a superpage allocation without a reservation is attempted. If successful, the fault completes or else the child gets killed. A COW fault from the parent similarly attempts to allocate a new superpage. On allocation failure, the page is unmapped from any children and the mappings are flagged. The parent safely uses the original page but child gets killed if it faults within the flagged mapping. Hence, a programming model based on superpage should not assume reliable superpage behaviour for private mappings in child processes. Either private mappings should be madvise() with MADV DONTFORK or child processes should take care not to access the mappings. This model guarantees the address space owner can successfully fault without depending on in-kernel demotion strategies that cannot be implemented for all architectures due to limitations on superpage placement. In the event a child is killed, a message is logged stating that "PID N killed to to inadequate hugepage pool" to make it clear what occurred.

Explicit Superpage Support

A simple interface for superpages would be similar to brk() or malloc() but it is difficult to create a shared mapping without extending the interface with unique semantics. The System V shared memory interface exists but application error can leak memory and private mappings are impossible to create. This section describes an interface for an application to map superpages without transparent support.

RAM-Based Filesystem

The Virtual File System (VFS) API for the creation, mapping and unmapping of files, both shared and private is well understood by developers. A RAM-based filesystem can create files that are backed by superpages when memory mapped. The filesystem API does not allow the passing of additional information but each mount of the filesystem can support different page sizes. Alternatively, an fadvise()-like interface could specify the page size before mmap() is called. The filesystem is a low-level interface and more suitable for use by libraries than directly by applications.

System V Shared Memory

The semantics of shared memory created and attached with the System V interfaces shmget() and shmat() are similarly well understood. By passing a new flag, SHM HUGETLB, the kernel is instructed to back the region with superpages. Internally, files of the size requested by shmget() can be created on a private instance of the filesystem. shmat() maps the file similar to a normal file mapped as mmap(MAP SHARED), thus sharing code between the filesystem and shared memory implementations. An error should be returned if the size is not superpage-aligned or sufficient superpages, leaving the decision on whether to use base pages to the library or application.

Anonymous mmap() Mappings

Memory mappings created with mmap() take a number of flags such as MAP PRIVATE, MAP ANONYMOUS and others described in the manual page. Similar to the previous interfaces, mmap() can be extended to support a MAP HUGETLB flag which automatically backs the mapping with superpages.

The difficulty with this interface is that setting the page size after mmap() is not an option due to possible architectural limitations and setting a default page size to be used for mmap() can race when threads are in use. If the architecture does not limit the placement of superpages, then madvise() can be extended after mmap() and before the pages are faulted. Otherwise, using MAP HUGETLB implies that a default superpage size is used.

Explicit Programming API

Three functions are defined that are useful to applications or libraries with superpage-awareness. The naming reflects the Linux implementation and uses the term "huge page" for superpages.

hugetlbfs unlinked fd() creates a file on the RAM-based filesystem for the requested superpage size and unlinks, rendering it invisible to other processes. This is useful when a process needs complete control over the size of the mapping placement within the address space.

get huge pages() takes a length and flags parameter. The length must be superpage-aligned and return a buffer to a superpagealigned length of memory or NULL on failure. It is suitable for use in the implementation of custom allocators. It is not suitable for use as a drop-in replacement for malloc() as it is a raw interface to superpages that does not cache-color buffers.

get hugepage region() similarly takes a length and flags parameter. The length need not be aligned and wastage is used to cache-color the buffer. On allocation failure, a buffer backed by base pages may be returned if requested by the caller. This is suitable as a drop-in replacement requiring that an application convert call-sites that create large buffers to use get hugepage region() instead.

Backing Memory Sections with Superpages

This section describes how different types of mappings of a process can be backed by superpages using explicit superpage support.

Heap

Allocations increasing the size of a heap currently use either brk() or mmap() to create memory regions. A custom allocator should use get hugepage region() and divide the superpage up into buffers as appropriate. This requires source modification which may be undesirable but it is a relatively straight-forward exercise.

If the allocator provide hooks for applications to create more heap then get huge pages() can be used by pre-loading and registering the hook before the application starts. GNU libc uses sbrk() for small allocations and mmap() for blocks larger than MMAP THRESHOLD which is 128kB by default. A morecore hook allows registry of a custom function that allocate more heap.

Mapping Text/Data/BSS

The effectiveness of backing data section with superpages depends on the compiler and the application. If the data section contains preinitialised data, then backing it with superpages will be effective. If the data section is zeros but stored on disk, then the copy will be effective. If it uses malloc() with a hook, then it can be backed similar to the heap. Otherwise, the loader must be modified.

Text and data are mapped with different permissions and the protection granularity depends on the page size. Applications should be relinked with the sections superpage-aligned which requires a suitable linker tool chain. Otherwise, architectural limitations determine if sections can be partially backed by superpages.

On mmap() of a section, the kernel can check the page cache. If the data exists but is stored in an unaligned base page, then the data should be copied to a superpage and the existing page cache entry replaced so that only one copy exists. If a superpage cannot be allocated, then the base pages are used. As the checks are made before the insertion in the process page tables, architectural limitations with address translation are avoided. Alternatively the loader can use get hugepage region() or similar to allocate a suitably large region, copy the data from disk and remap it to a suitable place. It is implementation-specific as to whether text is shared between processes or not.

Stack

The stack area of memory has similar requirements to brk() but is not as easily handled with hooks like malloc() or copied and remapped like text and data sections. The maximum stack size is unknown at application start time making it inherently unreliable to back with superpages without a demotion strategy. Consequently, explicit superpage support requires the stack be a fixed size.

Evaluation

Explicit superpage support as described in this paper has been implemented over the course of a number of kernel releases. This evaluation was based on Linux Kernel 2.6.31, downloaded from http://www.kernel.org and configured using the distribution's kernel configuration file. libhugetlbfs 2.7 was used to transparently access superpages without application modification. The distribution used was Debian GNU/Linux Lenny current as of October 2009. This distribution is freely available for independent verification and is commonly used as a server operating system. The compiler used was gcc 4.3.2.

Performance results are based on test-runs without profiling as it can distort results due to increased interrupt handling from the PMU and the profiling daemon gathering data. Profile information was gathered during a separate using OProfile2 . Due to limitations of the PMU, DTLB and cache misses data were collected during separate runs. In all cases, the relative performance of base pages and superpages matched so data collected during profiling should be indicative of what happened during no-profile runs.

During the base page runs, no superpages were used. During the superpage runs, the maximum number of superpages that was possible to use were allocated. Depending on the workload, this varied from negligible amounts to almost the size of physical memory. As the underlying implementation does not support the paging of superpages, there are no eviction rates to report but to make the comparison fair, it was confirmed that there was no meaningful paging activity while the tests were running with base pages.

The two machines were chosen based on the parts or models being readily available and are described in Table 1. Each workload was first run with base pages, then with superpages. They were rerun with profiling before moving onto the next workload. All superpages were released for each base page run and reallocated for superpage runs. All tests ran without rebooting without any failures to allocate superpages.

STREAM (Memory Throughput)

STREAM [START_REF] Mccalpin | STREAM: Sustainable Memory Bandwidth in High Performance Computers In a continually updated technical report[END_REF] is a synthetic memory bandwidth benchmark that measures the performance of four long vector operations: Copy, Scale, Add and Triad. It can be used to calculate the number of floating point operations performed during the benchmark to estimate the cost of the "average" memory access. Simplistically, more bandwidth is better.

The C version of the benchmark was selected and used three statically allocated arrays for calculations. Modified versions of the benchmark using malloc() and get hugepage region() were found to have similar performance characteristics.

The benchmark has two parameters: N, the size of the array and OFFSET, the number of elements padding the end of the array. A range of values for N were used to generate workloads between 128K and 2GB. For each size of N chosen, the benchmark was run 10 times and an average taken. The benchmark is sensitive to cache placement and optimal layout varies between architectures as noted on the benchmark author's homepage. Where the standard deviation of 10 iterations exceeded 5% of the throughput, OFFSET was increased to add one cache-line of padding between the arrays and the benchmark for that value of N reran. High standard deviation were only observed when the total working set was around the size of the L1, L2 or all caches combined.

The benchmark avoids data re-use, be it in registers or in the cache. Hence, benefits from superpages would be due to fewer faults, a slight reduction in TLB misses as fewer TLB entries are needed for the working set and an increase in available cache as less translation information needs to be stored.

To use superpages, the benchmark was first compiled with the libhugetlbfs ld wrapper to align the text and data sections to a superpage boundary [START_REF]Various Authors, libhugetlbfs 2.7 HOWTO In the libhugetlbfs source tarball[END_REF]. It was then loaded with hugectl --text --data --no-preload.

Figure 1 shows the comparison for the different STREAM operations when using base pages and superpages. On the test machines, there were massive reductions in DTLB misses. In the case of PPC64, it is reported as a 100% reduction but due to limitations to OProfile, TLB misses were not reduced to zero but there were so few that OProfile did not sample a miss. X86-64 gained 3.5% in the Add operation but was offset by a 3.31% regression in the Triad operation. Again, DTLB misses were significantly reduced and the time spent servicing misses was reduced from 1.84% to close to 0%. Cache misses were also reduced overall. The differences may again be potentially explained by cache coloring with Triad suffering significant conflicts.

On STREAM, data is not often re-used so increased cache capacity does not necessarily help STREAM unless the data is pre-fetched and cache conflicts are not an issue. As cache misses were not significantly reduced on X86-64, it implies that data was not being accurately pre-fetched or there were significant cache conflicts. Further investigation showed that there were 60 times more cache misses than TLB misses implying that cache conflicts In contrast, PPC64 has a very high TLB miss cost and the reduction in misses resulted in large performance gains of between 11.27% for the Copy operation to 16.57% for Triad. Further, an estimated 18.23% of time was spent servicing TLB misses for the STREAM benchmark. As cache misses only occurred 3-4 times more than TLB misses, it made TLB misses a more dominant factor than the other test machines. Cache misses were also significantly reduced, possibly helped by the fact that the arrays were rarely aligned to a superpage boundary.

The results show that TLB misses are not always a significant bottleneck for workloads with poor cache locality. In the situation where data structures are aligned to a superpage size, superpages can in fact impair performance due to increased cache conflicts depending on the CPU implementation. For the STREAM benchmark in particular, there is a potential for between 1.8% and 5% of performance to be gained by using superpages on X86-64 machines but care should be taken in future tests to avoid aligning arrays to the superpage size. In the PPC64 case, significant performance increases can be achieved with superpages due to the high cost of a TLB miss.

SysBench (Database Workload)

OnLine Transaction Processing (OLTP) is a general class of workload where clients perform a sequence of operations whose end result must appear to be an indivisible operation. TPC-C3 is considered an industry standard for the evaluation of OLTP but requires significant capital investment and is extremely complex to setup. Sysbench4 is a system performance benchmark comprising file IO, scheduler, memory allocation, threading and OLTP benchmarks. The setup requirements are less complicated and supports database back-ends for MySQL, Postgres and Oracle. Postgres5 was used for this experiment on the grounds that it uses a shared memory segment similar to Oracle making it a meaningful comparison with a commercial database server. Both Sysbench 0.4.8 and Postgres 8.3.4 were built from source.

Postgres was configured to use a 756MB shared buffer, an effective cache of 150MB, a maximum of 6*CPUs were allowed to connect and the "update process title" turned off. Options that checkout, fsync, log or synchronise were turned off to avoid interference from IO. pg ctl was invoked with hugectl --shm pg ctl when backing the shared memory segments superpages.

The system was configured to allow the postgres user to use superpages with shmget() (hugetlb shm group). Postgres uses System V shared memory but it has no superpage awareness. To transparently use superpages, pg ctl was invoked with hugectl --shm pg ctl to automatically back shared memory with superpages.

The Sysbench client did not use superpages as it would be expected that a database administrator has limited control of the clients. The table size was 10 million rows, read-only to avoid IO and the test type was "complex" described making each operation by the client a database transaction. Tests were run varying the number of clients accessing the database from one to four times the number of CPU cores in the system, a total of 16 clients for both systems.

Figure 2 shows the comparison of the number of transactions per second when using base pages and superpages. Overall, X86-64 shows a 2.81% improvement and 4.57% on PPC64 with reliable reductions in TLB, although not massive reductions on X86-64. Broadly speaking, the performance gains were close to predicted maximums of 2.3% for X86-64 and 3.63% for PPC64. Superpages performed slightly better than predicted due to the slight reduction in cache misses and remaining differences can be accounted for by small performance differences in performance when profiling. The difference between predictions and reality are so slight that there is a high degree of confidence that all potential performance improvements due to superpages are being achieved.

Anecdotal evidence in private communication with performance analysts presume that database workloads benefit from superpages by between 2% and 7% and these results would appear to correlate.

SPECcpu 2006 v1.1 (Computational)

SpecCPU 2006 v1.16 is a standardised CPU-intensive benchmark used in evaluations for HPC that also stresses the memory subsystem. A --reportable run was made comprising "test", "train" and three "ref" sets of input data. Three sets of runs compare base pages, superpages backing just the heap and superpages backing text, data and the heap. Only base tuning was used with no special compile options other than what was required to compile the tests. The benchmark suite classifies the run as "not publishable" on the grounds it did not recognise the -O2 -m64 compiler switches but this is not considered significant.

Figure 3 shows the comparison of the time taken to complete the Integer portion of the benchmark when using base pages and superpages.

The difficulty in analysing the performance of this benchmark was that profiling introduced an unusually large amount of overhead in comparison to other benchmarks in this study. In comparison to other workloads, the number of PMU events recorded was far higher making the overhead of interrupts was correspondingly higher and a greater amount of CPU time was dedicated to the profiler than on other benchmarks. Unfortunately, reducing the granularity impaired the accuracy of the TLB measurements and could not be otherwise worked around on the available hardware. In all case where the actual performance exceeded the predicted performance, the difference was found in the profiling overhead.

X86-64 showed negligible difference in the number of TLB misses due to the erratic nature of the reference pattern for many of the tests. However, as the cost of a superpage TLB miss is often lower on that architecture due to the different number of pagetable levels, there can still be a performance gain in many cases. PPC64 in some cases reduced the number of TLB misses due to taking advantage of a larger superpage size but they were in the minority.

Despite the difficulties in the exact analysis of the reason for the performance gain, X86-64 gained 10.40% and PPC64 gained 15.14%.

Figure 4 shows the comparison of the time taken to complete the Floating Point portion of the benchmark when using base pages and superpages.

On X86-64 there was a negligible difference in the number of TLB misses reduced and gains were due to a lower cost of a superpage TLB miss. Similarly, the profiling overhead was unavoidable and made an accurate analysis of the TLB behaviour problematic but where actual performance gains differed from expected gains, a significant portion of the difference was accounted for by the profiling overhead. Overall, X86-64 gained 5.19% and PPC64 gained 8.20%.

SPECjvm 2008 (Java)

Java is used in an increasing number of scenarios, including real time systems and it dominates in the execution of business-logic related applications. Particularly within application servers, the Java Virtual Machine (JVM) uses large quantities of virtual address space that can benefit from being backed by superpages. SpecJVM 20087 is a benchmark suite for Java Runtime Environments (JRE). According to the documentation, the intention is to reflect the performance of the processor and memory system with a low dependence on file or network I/O. Crucially for HPC, it includes SCI-Mark8 which is a Java benchmark for scientific and numerical computing.

The 64-bit versions of IBM Java Standard Edition Version 6 SP 3 were used for both X86-64 and PPC64. Installation on PPC64 required libstc++-5 from outside of the distribution as the distribution uses libstc++-6 and the backwards compatibility library was 32-bit only. The JVM was configured to use a maximum of 756MB for a heap. Unlike the other benchmarks, the JVM is superpageaware and uses superpage-backed shared memory segments when -Xlp is specified to the JVM. Superpages were allocated in a static pool as required by the JVM. As tuning parameters were used, the --peak parameter was specified as required by the run rules.

Figure 5 shows the comparison of the number of transactions per second when using base pages and superpages. Overall, X86-64 shows a 7.57% performance improvement with 4.54% on PPC64 with reliable reductions in TLB misses. There are a wide range of results in the test categories with scimarklarge suffering despite a prediction that tests would gain by between 2% and 21.2% on the three machines. An examination of the sub-tests that make up the scimarklarge benchmark showed significantly different TLB behaviour and performance benefits with a mix of gains and losses complicating a general analysis from the context of superpages. In general, the differences in the sub-tests account for the apparent difference between predicted and actual performance.

The disparity of the results show that superpages can help JVM workloads but by how much or little depends on the exact workload being executed within the JVM. As enabling superpages on JVMs is generally so trivial, the best recommendation is to test the workload with and without superpages measuring both absolute performance and profiling CPU and TLB miss counts.

Conclusions

This paper noted that transparent superpage support did not take architectural limitations into account and overly simplified cost functions. Explicit support is usable by 99.6% of the architectures making up the Top supercomputer list, was implemented for the operating system running on 87.8% of them and does necessarily require application modification. Evaluation was performed on two significantly different machines.

Average performance improvements due to explicit superpage use were very roughly in range of 2% to 10% on X86-64 and 4% to 15% PPC64 running a variety of workloads without imposing additional overhead on applications using exclusively base pages. PPC64 typically benefited to a greater degree than X86-64 which can be mostly accounted for by two facts. The first is that the cost of a TLB miss on the target machine was very high -563 cycles versus 51 cycles for a miss on the X86-64 based machine. The second is that the larger superpage size on PPC64 as well as the larger number of TLB entries meant that the TLB reach was increased by a far greater degree on PPC64 than on X86-64.

It was not reported in the figures but superpage use reduced the number of page faults incurred by the system by a factor related to the difference in size between base and superpages. The significance of this is mitigated by the fact that the workloads faulted the bulk of their data early in the process lifetime and did not page heavily. I/O rates are affected during application start-up as superpages are being allocated but as this principally affected application initialisation, it was not found to have made any meaningful performance difference to the target workload.

The performance improvements are less dramatic than predicted in early literature but those estimations were based on software TLB miss handlers and in-order processors. The returns have diminished due to faster hardware pagetable walkers and speculative address translation. However, bottlenecks still exist and superpages can reduce TLB miss rates as well as cache miss rates due to less translation information being stored. This may be of particular importance to virtualised workloads where translation an address in a guest is significantly more expensive than native translation.

Explicit superpage provides an important tool for predictably mitigating the cost of address translation on a variety of platforms. It establishes a performance baseline for continued research on transparent superpage page and should have comparable performance to specialised OS kernels that enable superpage usage on a per-application basis.

Figure 2 .

 2 Figure 2. Sysbench Comparison with Superpages

Figure

  Figure 3. SPECcpu Integer Comparison with Superpages

Figure 5 .

 5 Figure 5. SPECjvm Comparison with Superpages

Table 1 .

 1 Machine Configurations Used For Evaluation were a greater problem than TLB misses for this workload in the chosen configuration.

	CPU	AMD Phenom R 9950 Quad-Core	CPU	PPC970MP, altivec supported
	CPU Frequency	1.3GHz	CPU Frequency	2.5GHz
	# Physical CPUs	1 (4 cores)	# Physical CPUs	2 x dual core (4 cores in all)
	L1 Cache	64K Data, 64K Instruction per core	L1 Cache	32K Data, 64K Instruction per core
	L2 Cache	512K Unified per core	L2 Cache	1024K Unified per core
	L3 Cache	2048K Unified Shared per chip	L3 Cache	N/a
	Main Memory	8 GB	Main Memory	10GB
	Mainboard	Gigabyte GA-MA78GM-S2H	Mainboard	Specific to the machine model
	Superpage Size	2MB (1GB available but unused)	Superpage Size	16MB
	Est. TLB Miss Cost	51 cycles	Est. TLB Miss Cost	563 cycles
	Machine Model	Custom built	Machine Model	Terrasoft YDL Powerstation
		X86-64		PPC64

The specification allows 4K and 64K pages to mix within a segment but support is not universal.

http://oprofile.sourceforge.net/news/

http://www.tpc.org/tpcc/

http://sysbench.sourceforge.net/

http://www.postgresql.org/

http://www.spec.org/cpu2006/

http://www.specbench.org/jvm2008/

http://math.nist.gov/scimark2/

Acknowledgments

The design and implementation of superpages support in Linux has a long history and would not have reached its current state without the sterling work of the Linux community, particularly Andy Whitcroft, William Irwin, Adam Litke, David Gibson, Nishanth Aravamudan, Peter Zijlstra, Kenneth Chen, Hugh Dickins, Nick Piggin, Steve Fox, Jon Tollefson, Andi Kleen and Eric Munson. Parts of the material presented in this work are supported by the Defense Advanced Research Projects Agency under its Agreement No. HR0011-07-9-0002.