bluuebunny/crossref_metadata_2025 huggingface dataset:
Reducing virtual call overheads in a Java VM just-in-time compiler
Authors: Lee Junpyo , Yang Byung-Sun , Kim Suhyun , Ebcioğlu Kemal , Altman Erik , Lee Seungil , Chung Yoo C. , Lee Heungbok , Lee Je Hyung , Moon Soo-Mook
Published: July 2004

Java, an object-oriented language, uses
virtual methods
to support the extension and reuse of classes. Unfortunately, virtual method calls affect performance and thus require an efficient implementation, especially when just-in-time (JIT) compilation is done.
Inline caches
and
type feedback
are solutions used by compilers for dynamically-typed object-oriented languages such as SELF [1, 2, 3], where virtual call overheads are much more critical to performance than in Java. With an inline cache, a virtual call that would otherwise have been translated into an indirect jump with two loads is translated into a simpler direct jump with a single compare. With type feedback combined with adaptive compilation, virtual methods can be inlined using checking code which verifies if the target method is equal to the inlined one.This paper evaluates the performance impact of these techniques in an actual Java virtual machine, which is our new open source Java VM JIT compiler called
LaTTe
[4]. We also discuss the engineering issues in implementing these techniques.Our experimental results with the SPECjvm98 benchhmarks indicate that while monomoprhic inline caches and polymorphic inline caches achieve a speedup as much as a geometric mean of 3% and 9% respectively, type feedback cannot improve further over polymorphic inline caches and even degrades the performance for some programs.
Optimizing cache miss equations polyhedra
Authors: Bermudo Nerina , Vera Xavier , González Antonio , Llosa Josep
Published: July 2004

Cache Miss Equations (CME) [GMM97] is a method that accurately describes the cache behavior by means of polyhedra. Even though the computation cost of generating CME is a linear function of the number of references, to solve them is a very time consuming task and thus trying to study a whole program may be infeasible.In this work, we present effective techniques that exploit some properties of the particular polyhedra generated by CME. Such technique reduce the complexity of the algorithm to solve CME, which results in a significant speed-up when compared with traditional methods. In particular, the proposed approach does not require the computation of the vertices of each polyhedron, which has an exponential complexity.
A combined compiler and architecture technique to control multithreaded execution of branches and loop iterations
Authors: Unger A. , Zehendner E. , Ungerer Th.
Published: July 2004

Simultaneous Speculation Scheduling (
S
3
) is a combined compiler and architecture technique to control multiple path execution. It can be used for dual path branch speculation in case of unpredictable branches and for multiple path speculative execution of loop iterations in case of loop-carried dependences that make parallel execution otherwise impossible. We apply
S
3
In situations where purely static techniques cannot prove data independence.
S
3
can be seen as a cost-effective alternative to purely dynamic speculation techniques. We explain the
S
3
technique and discuss the requirements on possible target architectures. We further compare
S
3
to other speculation techniques.
Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures
Authors: Rashid Richard , Tevanian Avadis , Young Michael , Golub David , Baron Robert , Black David , Bolosky William , Chew Jonathan
Published: July 2004

This paper describes the design and implementation of virtual memory management within the CMU Mach Operating System and the experiences gained by the Mach kernel group in porting that system to a variety of architectures. As of this writing, Mach runs on more than half a dozen uniprocessors and multiprocessors including the VAX family of uniprocessors and multiprocessors, the IBM RT PC, the SUN 3, the Encore MultiMax, the Sequent Balance 21000 and several experimental computers. Although these systems vary considerably in the kind of hardware support for memory management they provide, the machine-dependent portion of Mach virtual memory consists of a single code module and its related header file. This separation of software memory management from hardware support has been accomplished without sacrificing system performance. In addition to improving portability, it makes possible a relatively unbiased examination of the pros and cons of various hardware memory management schemes, especially as they apply to the support of multiprocessors.
The dragon processor
Authors: Atkinson Russell R. , McCreight Edward M.
Published: July 2004

The Xerox PARC Dragon is a VLSI research computer that uses several techniques to achieve dense code and fast procedure calls in a system that can support multiple processors on a central high bandwidth memory bus.
Coherency for multiprocessor virtual address caches
Authors: Goodman James R.
Published: July 2004

A multiprocessor cache memory system is described that supplies data to the processor based on virtual addresses, but maintains consistency in the main memory, both across caches and across virtual address spaces. Pages in the same or different address spaces may be mapped to share a single physical page. The same hardware is used for maintaining consistency both among caches and among virtual addresses. Three different notions of a cache "block" are defined: (1) the unit for transferring data to/from main storage, (2) the unit over which tag information is maintained, and (3) the unit over which consistency is maintained. The relation among these block sizes is explored, and it is shown that they can be optimized independently. It is shown that the use of large address blocks results in low overhead for the virtual address cache.
Cheap hardware support for software debugging and profiling
Authors: Cargill T. A. , Locanthi B. N.
Published: July 2004

We wish to determine the effectiveness of some simple hardware for debugging and profiling compiled programs on a conventional processor. The hardware cost is small -- a counter decremented on each instruction that raises an exception when its value becomes zero. With the counter a debugger can provide data watchpoints and reverse execution: a profiler can measure the total instruction cost of a code segment and sample the program counter accurately. Such a counter has been included on a single-board MC68020 workstation, for which system software is currently being written. We will report our progress at the symposium.
The Mahler experience: using an intermediate language as the machine description
Authors: Wall David W. , Powell Michael L.
Published: July 2004

Division of a compiler into a front end and a back end that communicate via an intermediate language is a well-known technique. We go farther and use the intermediate language as the official description of a family of machines with simple instruction sets and addressing capabilities, hiding some of the inconvenient details of the real machine from the users and the front end compilers.To do this credibly, we have had to hide not only the existence of the details but also the performance consequences of hiding them. The back end that compiles and links the intermediate language tries to produce code that does not suffer a performance penalty because of the details that were hidden from the front end compiler. To accomplish this, we have used a number of link-time optimizations, including instruction scheduling and interprocedural register allocation, to hide the existence of such idiosyncracies as delayed branches and non-infinite register sets. For the most part we have been sucessful.
Compiling Smalltalk-80 to a RISC
Authors: Bush William R. , Samples A. Dain , Ungar David , Hilfinger Paul N.
Published: July 2004

The Smalltalk On A RISC project at U. C. Berkeley proves that a high-level object-oriented language can attain high performance on a modified reduced instruction set architecture. The single most important optimization is the removal of a layer of interpretation, compiling the bytecoded virtual machine instructions into low-level, register-based, hardware instructions. This paper describes the compiler and how it was affected by SOAR architectural features. The compiler generates code of reasonable density and speed. Because of Smalltalk-80's semantics, relatively few optimizations are possible, but hardware and software mechanisms at runtime offset these limitations. Register allocation for an architecture with register windows comprises the major task of the compiler. Performance analysis suggests that SOAR is not simple enough; several hardware features could be efficiently replaced by instruction sequences constructed by the compiler.
How many addressing modes are enough?
Authors: Chow F. , Correll S. , Himelstein M. , Killian E. , Weber L.
Published: July 2004

Programs naturally require a variety of memory-addressing modes. It isn't necessary to provide them in hardware, however, if a compiler can synthesize them from a few primitive modes. This not only simplifies the hardware, but also permits the compiler to use its understanding of the program to economize on the modes which it uses. We present some compilation techniques that allow the compiler to deal effectively with a single addressing mode in a target RISC processor. We also give measurements to show the benefits of such techniques, and to support our assertion that a single addressing mode is adequate for a general purpose processor, provided that mode incorporates both a pointer and an offset.
Superoptimizer: a look at the smallest program
Authors: Massalin Henry
Published: July 2004

Given an instruction set, the superoptimizer finds the shortest program to compute a function. Startling programs have been generated, many of them engaging in convoluted bit-fiddling bearing little resemblance to the source programs which defined the functions. The key idea in the superoptimizer is a probabilistic test that makes exhaustive searches practical for programs of useful size. The search space is defined by the processor's instruction set, which may include the whole set, but it is typically restricted to a subset. By constraining the instructions and observing the effect on the output program, one can gain insight into the design of instruction sets. In addition, superoptimized programs may be used by peephole optimizers to improve the quality of generated code, or by assembly language programmers to improve manually written code.
Pipelining and performance in the VAX 8800 processor
Authors: Clark Douglas W.
Published: July 2004

The VAX 8800 family (models 8800, 8700, 8550), currently the fastest computers in the VAX product line, achieve their speed through a combination of fast cycle time and deep pipelining. Rather than pipeline highly variable VAX instructions as such, the 8800 design pipelines uniform microinstructions whose addresses are generated by instruction unit hardware. This design approach helps achieve a fast cycle time, which is the prime determinan of performance. Some preliminary measurements of cycles per average instruction are reported.
The ZS-1 central processor
Authors: Smith J. E. , Dermer G. E. , Vanderwarn B. D. , Klinger S. D. , Rozewski C. M. , Fowler D. L. , Scidmore K. R. , Laudon J. P.
Published: July 2004

The Astronautics ZS-1 is a high speed, 64-bit computer system designed for scientific and engineering applications. The ZS-1 central processor uses a decoupled architecture, which splits instructions into two streams---one for fixed point/memory address computation and the other for floating point operations. The two instruction streams are then processed in parallel. Pipelining is also used extensively throughout the ZS-1.This paper describes the architecture and implementation of the ZS-1 central processor, beginning with some of the basic design objectives. Descriptions of the instruction set, pipeline structure, and virtual memory implementation demonstrate the methods used to satisfy the objectives. High performance is achieved through a combination of static (compile-time) instruction scheduling and dynamic (run-time) scheduling. Both types of scheduling are illustrated with examples.
Optimising hot paths in a dynamic binary translator
Authors: Ung David , Cifuentes Cristina
Published: July 2004

In dynamic binary translation, code is translated "on the fly" at run-time, while the user perceives ordinary execution of the program on the target machine. Code fragments that are frequently executed follow the same sequence of flow control over a period of time. These fragments form a hot path and are optimised to improve the overall performance of the program.Multiple hot paths may also exist in programs. A program may choose to execute in one hot path for some time, but later switch to another hot path, or even cycle between hot paths. Hence, each hot path is able to capture the most frequent execution pattern for a particular run-time stage of the program. The end result is that scattered code is collected, merged and optimised in a special way.In this paper we describe the optimisations performed by UQDBT - a machine-adaptable dynamic binary translator. We provide an algorithm for finding hot paths using edge weight profiles, and we explain how to optimise code in a machine-independent way, based on hot path information.
Architecture and design of AlphaServer GS320
Authors: Gharachorloo Kourosh , Sharma Madhu , Steely Simon , Van Doren Stephen
Published: July 2004

This paper describes the architecture and implementation of the AlphaServer GS320, a cache-coherent non-uniform memory access multiprocessor developed at Compaq. The AlphaServer GS320 architecture is specifically targeted at medium-scale multiprocessing with 32 to 64 processors. Each node in the design consists of four Alpha 21264 processors, up to 32GB of coherent memory, and an aggressive IO subsystem. The current implementation supports up to 8 such nodes for a total of 32 processors. While snoopy-based designs have been stretched to medium-scale multiprocessors by some vendors, providing sufficient snoop bandwidth remains a major challenge especially in systems with aggressive processors. At the same time, directory protocols targeted at larger scale designs lead to a number of inherent inefficiencies relative to snoopy designs. A key goal of the AlphaServer GS320 architecture has been to achieve the best-of-both-worlds, partly by exploiting the bounded scale of the target systems.This paper focuses on the unique design features used in the AlphaServer GS320 to efficiently implement coherence and consistency. The guiding principle for our directory-based protocol is to address correctness issues related to rare protocol races without burdening the common transaction flows. Our protocol exhibits lower occupancy and lower message counts compared to previous designs, and provides more efficient handling of 3-hop transactions. Furthermore, our design naturally lends itself to elegant solutions for deadlock, livelock, starvation, and fairness. The AlphaServer GS320 architecture also incorporates a couple of innovative techniques that extend previous approaches for efficiently implementing memory consistency models. These techniques allow us to generate commit events (which are used for ordering purposes) well in advance of formulating the reply to a transaction. Furthermore, the separation of the commit event allows time-critical replies to by-pass inbound requests without violating ordering properties. Even though our design specifically targets medium-scale servers, many of the same techniques can be applied to larger-scale directory-based and smaller-scale snoopy-based designs. Finally, we evaluate the performance impact of some of the above optimizations and present a few competitive benchmark results.
System architecture directions for networked sensors
Authors: Hill Jason , Szewczyk Robert , Woo Alec , Hollar Seth , Culler David , Pister Kristofer
Published: July 2004

Technological progress in integrated, low-power, CMOS communication devices and sensors makes a rich design space of networked sensors viable. They can be deeply embedded in the physical world and spread throughout our environment like smart dust. The missing elements are an overall system architecture and a methodology for systematic advance. To this end, we identify key requirements, develop a small device that is representative of the class, design a tiny event-driven operating system, and show that it provides support for efficient modularity and concurrency-intensive operation. Our operating system fits in 178 bytes of memory, propagates events in the time it takes to copy 1.25 bytes of memory, context switches in the time it takes to copy 6 bytes of memory and supports two level scheduling. The analysis lays a groundwork for future architectural advances.
OS and compiler considerations in the design of the IA-64 architecture
Authors: Zahir Rumi , Ross Jonathan , Morris Dale , Hess Drew
Published: July 2004

Increasing demands for processor performance have outstripped the pace of process and frequency improvements, pushing designers to find ways of increasing the amount of work that can be processed in parallel. Traditional RISC architectures use hardware approaches to obtain more instruction-level parallelism, with the compiler and the operating system (OS) having only indirect visibility into the mechanisms used.The IA-64 architecture [14] was specifically designed to enable systems which create and exploit high levels of instruction-level parallelism by explicitly encoding a program's parallelism in the instruction set [25]. This paper provides a qualitative summary of the IA-64 architecture features that support control and data speculation, and register stacking. The paper focusses on the functional synergy between these architectural elements (rather than their individual performance merits), and emphasizes how they were designed for cooperation between processor hardware, compilers and the OS.
Two economical directory schemes for large-scale cache coherent multiprocessors
Authors: Maa Yeong-Chang , Pradhan Dhiraj K. , Thiebaut Dominique
Published: July 2004

Cache coherence problem is a major issue in the design of shared-memory multiprocessors. As the number of processors grows, traditional bus-based snoopy schemes for cache coherence are no longer adequate. Instead, the directory-based scheme is a promising alternative for the large-scale cache coherence problem. However, the storage overhead of (full-map) directory scheme may become too prohibitive as the system size goes up. This paper presents two distributed directory schemes, the
tree directory
and the
hierarchical full-map directory
, to deal with the storage overhead problem. Preliminary trace-driven evaluations show that the performance of our schemes compares favorably to the full-map directory scheme, while reducing the storage overhead by over 90%. These two schemes should lend themselves to the design and implementation of large-scale cache coherent multiprocessors.
Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processors
Authors: Luk Chi-Keung
Published: July 2004

Hardly predictable data addresses in many irregular applications have rendered prefetching ineffective. In many cases, the only accurate way to predict these addresses is to directly execute the code that generates them. As multithreaded architectures become increasingly popular, one attractive approach is to use idle threads on these machines to perform
pre-execution—
essentially a combined act of speculative address generation and prefetching—to accelerate the main thread. In this paper, we propose such a pre-execution technique for simultaneous multithreading (SMT) processors. By using software to control pre-execution, we are able to handle some of the most important access patterns that are typically difficult to prefetch. Compared with existing work on pre-execution, our technique is significantly simpler to implement (e.g., no integration of pre-execution results, no need of shortening programs for pre-execution, and no need of special hardware to copy register values upon thread spawns). Consequently, only minimal extensions to SMT machines are required to support our technique. Despite its simplicity, our technique offers an average speedup of 24% in a set of irregular applications, which is a 19% speedup over state-of-the-art software-controlled prefetching.
Code layout optimizations for transaction processing workloads
Authors: Ramirez Alex , Barroso Luiz André , Gharachorloo Kourosh , Cohn Robert , Larriba-Pey Josep , Lowney P. Geoffrey , Valero Mateo
Published: July 2004

Commercial applications such as databases and Web servers constitute the most important market segment for high-performance servers. Among these applications, on-line transaction processing (OLTP) workloads provide a challenging set of requirements for system designs since they often exhibit inefficient executions dominated by a large memory stall component. This behavior arises from large instruction and data footprints and high communication miss rates. A number of recent studies have characterized the behavior of commercial workloads and proposed architectural features to improve their performance. However, there has been little research on the impact of software and compiler-level optimizations for improving the behavior of such workloads.

This paper provides a detailed study of profile-driven compiler optimizations to improve the code layout in commercial workloads with large instruction footprints. Our compiler algorithms are implemented in the context of Spike, an executable optimizer for the Alpha architecture. Our experiments use the Oracle commercial database engine running an OLTP workload, with results generated using both full system simulations and actual runs on Alpha multiprocessors. Our results show that code layout optimizations can provide a major improvement in the instruction cache behavior, providing a 55% to 65% reduction in the application misses for 64-128K caches. Our analysis shows that this improvement primarily arises from longer sequences of consecutively executed instructions and more reuse of cache lines before they are replaced. We also show that the majority of application instruction misses are caused by self-interference. However, code layout optimizations significantly reduce the amount of self-interference, thus elevating the relative importance of interference with operating system code. Finally, we show that better code layout can also provide substantial improvements in the behavior of other memory system components such as the instruction TLB and the unified second-level cache. The overall performance impact of our code layout optimizations is an improvement of 1.33 times in the execution time of our workload.
NanoFabrics
Authors: Goldstein Seth Copen , Budiu Mihai
Published: July 2004

The continuation of the remarkable exponential increases in processing power over the recent past faces imminent challenges due in part to the physics of deep-submicron CMOS devices and the costs of both chip masks and future fabrication plants. A promising solution to these problems is offered by an alternative to CMOS-based computing, chemically assembled electronic nanotechnology (CAEN).

In this paper we outline how CAEN-based computing can become a reality. We briefly describe recent work in CAEN and how CAEN will affect computer architecture. We show how the inherently reconfigurable nature of CAEN devices can be exploited to provide high-density chips with defect tolerance at significantly reduced manufacturing costs. We develop a layered abstract architecture for CAEN-based computing devices and we present preliminary results which indicate that such devices will be competitive with CMOS circuits.
Exploiting instruction level parallelism in processors by caching scheduled groups
Authors: Nair Ravi , Hopkins Martin E.
Published: July 2004

Modern processors employ a large amount of hardware to dynamically detect parallelism in single-threaded programs and maintain the sequential semantics implied by these programs. The complexity of some of this hardware diminishes the gains due to parallelism because of longer clock period or increased pipeline latency of the machine.In this paper we propose a processor implementation which dynamically schedules groups of instructions while executing them on a fast simple engine and caches them for repeated execution on a fast VLIW-type engine. Our experiments show that scheduling groups spanning several basic blocks and caching these scheduled groups results in significant performance gain over fill buffer approaches for a standard VLIW cache.This concept, which we call DIF (Dynamic Instruction Formatting), unifies and extends principles underlying several schemes being proposed today to reduce superscalar processor complexity. This paper examines various issues in designing such a processor and presents results of experiments using trace-driven simulation of SPECint95 benchmark programs.
Designing high bandwidth on-chip caches
Authors: Wilson Kenneth M. , Olukotun Kunle
Published: July 2004

In this paper we evaluate the performance of high bandwidth caches that employ multiple ports, multiple cycle hit times, on-chip DRAM, and a line buffer to find the organization that provides the best processor performance. Processor performance is measured in execution time using a dynamic superscalar processor running realistic benchmarks that include operating system references. The results show that a large dual-ported multi-cycle pipelined SRAM cache with a line buffer maximizes processor performance. A large pipelined cache provides both a low miss rate and a high CPU clock frequency. Dual-porting the cache and the use of a line buffer provide the bandwidth needed by a dynamic superscalar processor. In addition, the line buffer makes the pipelined dual-ported cache the best option by increasing cache port bandwidth and hiding cache latency.
The interaction of software prefetching with ILP processors in shared-memory systems
Authors: Ranganathan Parthasarathy , Pai Vijay S. , Abdel-Shafi Hazim , Adve Sarita V.
Published: July 2004

Current microprocessors aggressively exploit instruction-level parallelism (ILP) through techniques such as multiple issue, dynamic scheduling, and non-blocking reads. Recent work has shown that memory latency remains a significant performance bottleneck for shared-memory multiprocessor systems built of such processors.This paper provides the first study of the effectiveness of software-controlled non-binding prefetching in shared memory multiprocessors built of state-of-the-art ILP-based processors. We find that software prefetching results in significant reductions in execution time (12% to 31%) for three out of five applications on an ILP system. However, compared to previous-generation system, software prefetching is significantly less effective in reducing the memory stall component of execution time on an ILP system. Consequently, even after adding software prefetching, memory stall time accounts for over 30% of the total execution time in four out of five applications on our ILP system.This paper also investigates the interaction of software prefetching with memory consistency models on ILP-based multiprocessors. In particular, we seek to determine whether software prefetching can equalize the performance of sequential consistency (SC) and release consistency (RC). We find that even with software prefetching, for three out of five applications, RC provides a significant reduction in execution time (15% to 40%) compared to SC.
Prefetching using Markov predictors
Authors: Joseph Doug , Grunwald Dirk
Published: July 2004

Prefetching is one approach to reducing the latency of memory operations in modern computer systems. In this paper, we describe the
Markov prefetcher.
This prefetcher acts as an interface between the on-chip and off-chip cache, and can be added to existing computer designs. The Markov prefetcher is distinguished by prefetching
multiple reference predictions
from the memory subsystem, and then prioritizing the delivery of those references to the processor.This design results in a prefetching system that provides good coverage, is accurate and produces timely results that can be effectively used by the processor. In our cycle-level simulations, the Markov Prefetcher reduces the overall execution stalls due to instruction and data memory operations by an average of 54% for various commercial benchmarks while only using two thirds the memory of a demand-fetch cache organization.
The energy efficiency of IRAM architectures
Authors: Fromm Richard , Perissakis Stylianos , Cardwell Neal , Kozyrakis Christoforos , McGaughy Bruce , Patterson David , Anderson Tom , Yelick Katherine
Published: July 2004

Portable systems demand energy efficiency in order to maximize battery life. IRAM architectures, which combine DRAM and a processor on the same chip in a DRAM process, are more energy efficient than conventional systems. The high density of DRAM permits a much larger amount of memory on-chip than a traditional SRAM cache design in a logic process. This allows most or all IRAM memory accesses to be satisfied on-chip. Thus there is much less need to drive high-capacitance off-chip buses, which contribute significantly to the energy consumption of a system. To quantify this advantage we apply models of energy consumption in DRAM and SRAM memories to results from cache simulations of applications reflective of personal productivity tasks on low power systems. We find that IRAM memory hierarchies consume as little as 22% of the energy consumed by a conventional memory hierarchy for memory-intensive applications, while delivering comparable performance. Furthermore, the energy consumed by a system consisting of an IRAM memory hierarchy combined with an energy efficient CPU core is as little as 40% of that of the same CPU core with a traditional memory hierarchy.
A tagged token dataflow machine for computing small, iterative algorithms
Authors: Shippen G. B. , Archibald J. K.
Published: July 2004

A "buildable" dynamic tagged token data flow architecture tailored for small, highly iterative algorithms such as the Mandelbrot set is presented. Historically, dataflow machines have required a major hardware effort to construct. As a result, very few real machines have been built. In contrast to these large scale machines, this project was intended to be built at minimal expense and with "off-the-shelf" parts. A novel insight into the process of executing a dataflow graph is presented. This insight has resulted in a new architecture utilizing a "pseudo-program counter". This scheme allows a significant reduction in the width of the data paths throughout the PE interconnection network. To further reduce the required hardware, the traditional associative matching store has been eliminated in favor of a more brute-force approach that is workable for the class of algorithms considered for execution on this machine.
Errata on "Measuring Experimental Error in Microprocessor Simulation"
Authors: Desikan Rajagopalan , Burger Doug , Keckler Stephen W. , Cruz Llorenc , Latorre Fernando , González Antonio , Valero Mateo
Published: July 2004

This short paper serves to correct the errors contained in the paper entitled "Measuring Experimental Error in Microprocessor Simulation," presented at the 2001 International Symposium on Computer Architecture (ISCA-28) [2]. That paper contained a study of a validated microarchitectural simulator called sim-alpha, and included a case study that compared results obtained from a configuration of sim-alpha to those reported by Cruz
et al.
[1]. The comparison showed a disparity in the results between the two studies, which was invalid due to an error in the way the operand bypass network of sim-alpha was modified.In this paper, we present a revised comparison that models the bypass network in sim-alpha consistently with the work of Cruz
et al.
(henceforth called the reference study). After explaining the bypassing issues in detail, we show that the new comparison between the revised results and the reference study shows similar trends, thus validating the accuracy of the reference study.In addition, we (the authors of the sim-alpha study) would like to state explicitly that we regret any professional harm caused to the authors of the reference study (Cruz, González, Valero, and Topham). The original intent was to show that different simulators modeling similar targets could cause different conclusions to be drawn, thus emphasizing the need for consistency across simulators and research efforts. Since the comparison with the reference study was made with a (modified) validated simulator, and the two sets of results showed a different trend (because of the error in modeling the bypass), it is natural to infer that the reference study was incorrect. We thoughtlessly published the comparison without contacting the authors of the reference study beforehand. We apologize to them both for implying an error in their (correct) methodology and for the discourteous way in which it was presented.
Efficient dynamic scheduling through tag elimination
Authors: Ernst Dan , Austin Todd
Published: July 2004

An increasingly large portion of scheduler latency is derived from the monolithic content addressable memory (CAM) arrays accessed during instruction wakeup. The performance of the scheduler can be improved by decreasing the number of tag comparisons necessary to schedule instructions. Using detailed simulation-based analyses, we find that most instructions enter the window with at least one of their input operands already available. By putting these instructions into specialized windows with fewer tag comparators, load capacitance on the scheduler critical path can be reduced, with only very small effects on program throughput. For instructions with multiple unavailable operands, we introduce a last-tag speculation mechanism that eliminates all remaining tag comparators except those for the last arriving input operand. By combining these two tag-reduction schemes, we are able to construct dynamic schedulers with approximately one quarter of the tag comparators found in conventional designs. Conservative circuit-level timing analyses indicate that the optimized designs are 20-45% faster and require 10-20% less power, depending on instruction window size.
Transient-fault recovery using simultaneous multithreading
Authors: Vijaykumar T. N. , Pomeranz Irith , Cheng Karl
Published: July 2004

We propose a scheme for transient-fault recovery called
Simultaneously and Redundantly Threaded processors with Recovery (SRTR)
that enhances a previously proposed scheme for transient-fault detection, called Simultaneously and Redundantly Threaded (SRT) processors. SRT replicates an application into two communicating threads, one executing ahead of the other. The trailing thread repeats the computation performed by the leading thread, and the values produced by the two threads are compared. In SRT, a leading instruction may commit
before
the check for faults occurs, relying on the trailing thread to trigger detection. In contrast, SRTR must
not
allow
any
leading instruction to commit before checking occurs, since a faulty instruction cannot be undone once the instruction commits.To avoid stalling leading instructions at commit while waiting for their trailing counterparts, SRTR exploits the time between the completion and commit of leading instructions. SRTR compares the leading and trailing values as soon as the trailing instruction completes, typically before the leading instruction reaches the commit point. To avoid increasing the bandwidth demand on the register file for checking register values, SRTR uses the
register value queue (RVQ)
to hold register values for checking. To reduce the bandwidth pressure on the RVQ itself, SRTR employs
dependence-based checking elision (DBCE).
By reasoning that faults propagate through dependent instructions, DBCE exploits register (true) dependence chains so that only the last instruction in a chain uses the RVQ, and has the leading and trailing values checked. SRTR performs within 1% and 7% of SRT for SPEC95 integer and floating-point programs, respectively: While SRTR without DBCE incurs about 18% performance loss when the number of RVQ ports is reduced from four (which is performance-equivalent to an unlimited number) to two ports, with DBCE, a two-ported RVQ performs within 2% of a four-ported RVQ.
Going the distance for TLB prefetching
Authors: Kandiraju Gokul B. , Sivasubramaniam Anand
Published: July 2004

The importance of the Translation Lookaside Buffer (TLB) on system performance is well known. There have been numerous prior efforts addressing TLB design issues for cutting down access times and lowering miss rates. However, it was only recently that the first exploration [26] on prefetching TLB entries ahead of their need was undertaken and a mechanism called Recency Prefetching was proposed. There is a large body of literature on prefetching for caches, and it is not clear how they can be adapted (or if the issues are different) for TLBs, how well suited they are for TLB prefetching, and how they compare with the recency prefetching mechanism.This paper presents the first detailed comparison of different prefetching mechanisms (previously proposed for caches) - arbitrary stride prefetching, and markov prefetching - for TLB entries, and evaluates their pros and cons. In addition, this paper proposes a novel prefetching mechanism, called Distance Prefetching, that attempts to capture patterns in the reference behavior in a smaller space than earlier proposals. Using detailed simulations of a wide variety of applications (56 in all) from different benchmark suites and all the SPEC CPU2000 applications, this paper demonstrates the benefits of distance prefetching.
Managing multi-configuration hardware via dynamic working set analysis
Authors: Dhodapkar Ashutosh S. , Smith James E.
Published: July 2004

Microprocessors are designed to provide good average performance over a variety of workloads. This can lead to inefficiencies both in power and performance for individual programs and during individual phases within the same program. Microarchitectures with multi-configuration units (e.g. caches, predictors, instruction windows) are able to adapt dynamically to program behavior and enable/disable resources as needed. A key element of existing configuration algorithms is adjusting to program phase changes. This is typically done by "tuning" when a phase change is detected --- i.e. sequencing through a series of trial configurations and selecting the best.Algorithms that dynamically collect and analyze program working set information are studied. To make this practical, we propose working set signatures --- highly compressed working set representations (e.g. 32-128 bytes total). Algorithms use working set signatures to 1) detect working set changes and trigger re-tuning; 2) identify, recurring working sets and re-install saved optimal reconfigurations, thus avoiding the time-consuming tuning process; 3) estimate working set sizes to configure caches directly to the proper size, also avoiding the tuning process. Multi-configuration instruction caches are used to demonstrate the performance of the proposed algorithms. When applied to reconfigurable instruction caches, an algorithm that identifies recurring phases achieves power savings and performance similar to the best algorithm reported to date, but with orders-of-magnitude savings in the number of re-tunings.
Queue pair IP
Authors: Buonadonna Philip , Culler David
Published: July 2004

We propose a SAN architecture called Queue Pair IP (QPIP) that combines the interface from industry proposals for low overhead, high bandwidth networks, e.g. Infiniband, with the well established inter-network protocol suite. We evaluate how effectively the queue pair abstraction enables inter-network protocol offload. We develop a prototype QPIP system that implements basic queue pair operations over a subset of TCP, UDP and IPv6 protocols using a programmable network adapter. We assess this prototype, in terms of basic application performance, underlying processing costs, and a network storage application. With modest hardware support, QPIP can perform as well as traditional inter-network protocol implementations at a fraction of the host CPU overhead. With hardware support equivalent to Infiniband, QPIP would achieve similar performance targets.
Experiences with VI communication for database storage
Authors: Zhou Yuanyuan , Bilas Angelos , Jagannathan Suresh , Dubnicki Cezary , Philbin James F. , Li Kai
Published: July 2004

This paper examines how VI-based interconnects can be used to improve I/O path performance between a database server and the storage subsystem. We design and implement a software layer, DSA, that is layered between the application and VI. DSA takes advantage of specific VI features and deals with many of its shortcomings. We provide and evaluate one kernel-level and two user-level implementations of DSA. These implementations trade transparency and generality for performance at different degrees, and unlike research prototypes are designed to be suitable for real-world deployment. We present detailed measurements using a commercial database management system with both micro-benchmarks and industrial database workloads on a mid-size, 4 CPU, and a large, 32 CPU, database server.Our results show that VI-based interconnects and user-level communication can improve all aspects of the I/O path between the database system and the storage back-end. We also find that to make effective use of VI in I/O intensive environments we need to provide substantial additional functionality than what is currently provided by VI. Finally, new storage APIs that help minimize kernel involvement in the I/O path are needed to fully exploit the benefits of VI-based communication.
Speculative dynamic vectorization
Authors: Pajuelo Alex , González Antonio , Valero Mateo
Published: July 2004

Traditional vector architectures have shown to be very effective for regular codes where the compiler can detect data-level parallelism. However, this SIMD parallelism is also present in irregular or pointer-rich codes, for which the compiler is quite limited to discover it. In this paper we propose a microarchitecture extension in order to exploit SIMD parallelism in a speculative way. The idea is to predict when certain operations are likely to be vectorizable, based on some previous history information. In this case, these scalar instructions are executed in a vector mode. These vector instructions operate on several elements (vector operands) that are anticipated to be their input operands and produce a number of outputs that are stored on a vector register in order to be used by further instructions. Verification of the correctness of the applied vectorization eventually changes the status of a given vector element from speculative to non-speculative, or alternatively, generates a recovery action in case of misspeculation.The proposed microarchitecture extension applied to a 4-way issue superscalar processor with one wide bus is 19% faster than the same processor with 4 scalar buses to L1 data cache. This speed up is due basically to 1) the reduction in number of memory accesses, 15% for SpecInt and 20% for SpecFP, 2) the transformation of scalar arithmetic instructions into their vector counterpart, 28% for SpecInt and 23% for SpecFP, and 3) the exploitation of control independence for mispredicted branches.
Tarantula
Authors: Espasa Roger , Ardanaz Federico , Emer Joel , Felix Stephen , Gago Julio , Gramunt Roger , Hernandez Isaac , Juan Toni , Lowney Geoff , Mattina Matthew , Seznec André
Published: July 2004

Tarantula is an aggressive floating point machine targeted at technical, scientific and bioinformatics workloads, originally planned as a follow-on candidate to the EV8 processor [6, 5]. Tarantula adds to the EV8 core a vector unit capable of 32 double-precision flops per cycle. The vector unit fetches data directly from a 16 MByte second level cache with a peak bandwidth of sixty four 64-bit values per cycle. The whole chip is backed by a memory controller capable of delivering over 64 GBytes/s of raw band- width. Tarantula extends the Alpha ISA with new vector instructions that operate on new architectural state. Salient features of the architecture and implementation are: (1) it fully integrates into a virtual-memory cache-coherent system without changes to its coherency protocol, (2) provides high bandwidth for non-unit stride memory accesses, (3) supports gather/scatter instructions efficiently, (4) fully integrates with the EV8 core with a narrow, streamlined interface, rather than acting as a co-processor, (5) can achieve a peak of 104 operations per cycle, and (6) achieves excellent "real-computation" per transistor and per watt ratios. Our detailed simulations show that Tarantula achieves an average speedup of 5X over EV8, out of a peak speedup in terms of flops of 8X. Furthermore, performance on gather/scatter intensive benchmarks such as Radix Sort is also remarkable: a speedup of almost 3X over EV8 and 15 sustained operations per cycle. Several benchmarks exceed 20 operations per cycle.
Design tradeoffs for the Alpha EV8 conditional branch predictor
Authors: Seznec André , Felix Stephen , Krishnan Venkata , Sazeides Yiannakis
Published: July 2004

This paper presents the Alpha EV8 conditional branch predictor The Alpha EV8 microprocessor project, canceled in June 2001 in a late phase of development, envisioned an aggressive 8-wide issue out-of-order superscalar microarchitecture featuring a very deep pipeline and simultaneous multithreading. Performance of such a processor is highly dependent on the accuracy of its branch predictor and consequently a very large silicon area was devoted to branch prediction on EV8. The Alpha EV8 branch predictor relies on global history and features a total of 352 Kbits.The focus of this paper is on the different trade-offs performed to overcome various implementation constraints for the EV8 branch predictor. One such instance is the pipelining of the predictor on two cycles to facilitate the prediction of up to 16 branches per cycle from any two dynamically successive, 8 instruction fetch blocks. This resulted in the use of three fetch-block old compressed branch history information for accesing the predictor. Implementation constraints also restricted the composition of the index functions for the predictor and forced the usage of only single-ported memory cells.Nevertheless, we show that the Alpha EV8 branch predictor achieves prediction accuracy in the same range as the state-of-the-art academic global history branch predictors that do not consider implementation constraints in great detail.
Difficult-path branch prediction using subordinate microthreads
Authors: Chappell Robert S. , Tseng Francis , Yoaz Adi , Patt Yale N.
Published: July 2004

Branch misprediction penalties continue to increase as microprocessor cores become wider and deeper. Thus, improving branch prediction accuracy remains an important challenge. Simultaneous Subordinate Microthreading (SSMT) provides a means to improve branch prediction accuracy. SSMT machines run multiple, concurrent microthreads in support of the primary thread. We propose to dynamically construct microthreads that can speculatively and accurately pre-compute branch outcomes along frequently mispredicted paths. The mechanism is intended to be implemented entirely in hardware. We present the details for doing so. We show how to select the right paths, how to generate accurate predictions, and how to get this information in a timely way. We achieve an average gain of 8.4% (42% maximum) over a very aggressive baseline machine on the SPECint95 and SPECint2000 benchmark suites.