bluuebunny/crossref_metadata_2025 huggingface dataset:
An implementation independent approach to cache memories
Authors: Bril Reinder J.
Published: July 2004

This paper presents an implementation independent approach to cache memories with states of blocks and kinds of blocks.An implementation independent description of states of blocks in a tightly coupled multi-processor system with private caches is presented, which distinguishes between (abstract) states of blocks and (implementation oriented) tags. Two approaches to cache consistency protocols are described using abstract states: the
ownership
approach and the
responsibleness
approach.Blocks are looked at as constituents of logical entities such as segments. Different kinds of blocks are distinguished based on different kinds of segments. Whenever caches are able to distinguish between different kinds of blocks, then cache schemes, block sizes, and other implementation related aspects may be chosen independently, facilitating a separation of concerns.
Overview of concert multilisp: a multiprocessor symbolic computing system
Authors: Halstead Robert H.
Published: July 2004

Multilisp is a parallel programming language derived from the Scheme dialect of Lisp by addition of the future construct. Multilisp has been implemented on Concert, a shared-memory muitiprocessor that uses a novel
RingBus
interconnection. Concert currently has 28 MC68000 processors, with a design goal of 32 processors. Several application programs have been developed and measured using Concert Multilisp. Experience with these programs has contributed to tuning the Multilisp language design and will ultimately contribute to the design of a parallel architecture streamlined for high performance on Multilisp programs.
A centrally controlled shuffle network for reconfigurable and fault-tolerant architecture
Authors: Biswas Nripendra N. , Srinivas S. , Dharanendra Trishala
Published: July 2004

The paper describes a multistage shuffle interconnection network which is controlled by a central monitor. A control code broadcast by the monitor to all the basic switching elements of the network simultaneously, makes the network dynamically reconfigurable. The control code plays three vital roles. Firstly, it establishes conflict-free paths between several source-destination pairs. Thus the problem of collision, a major obstacle of a self-routing network, is completely eliminated. Secondly, the direct paths are established in one clock period irrespective of the number of stages. This makes the system faster. Thirdly, the control code also acts as a grouping code for executing a table of arbitrary data exchange requests between nodes in minimum number of passes. It is also shown that the network can be made fault-tolerant by the addition of an extra stage. Any single fault and some multiple faults in the intermediate stages can be tolerated by this scheme. Moreover, the switching from the faulty state to the fault-free state can be done in a single clock period, thus enabling fast fault-tolerant reconfiguration.
OMP
Authors: Hwang K. , Dubois M. , Panda D. K. , Rao S. , Shang S. , Uresin A. , Mao W. , Nair H. , Lytwyn M. , Hsieh F. , Liu J. , Mehrotra S. , Cheng C. M.
Published: July 2004

This paper presents the architectural design and RISC based implementation of a prototype supercomputer, namely the
Orthogonal MultiProcessor
(OMP). The OMP system is constructed with 16 Intel 1860 RISC microprocessors and 256 parallel memory modules, which are 2-D interleaved and orthogonally accessed using custom-designed spanning buses. The architectural design has been validated by a CSIM-based multiprocessor simulator. The design choices are based on worst-case delay analysis and simulation validation. The current OMP prototype chooses a 2-dimensional memory architecture, mainly for image processing, computer vision, and neural network simulation applications. The 16-processor OMP prototype is targeted to achieve a peak performance of 400 RISC integer MIPS or a maximum of 640 Mflops. This paper presents the architectural design of the OMP prototype at system and PC board levels. We are presently entering the fabrication stage of all the PC boards. The system is expected to become operational in late 1991 and benchmarking results will be available in 1992. Only hardware design features are reported here. Software and simulation results are reported elsewhere.
Analysis of a variant hypercube topology
Authors: Tzeng Nian-Feng
Published: July 2004

Each node of a hypercube system, when fabricated, comes with a fixed number of links designed for a maximum sized construction. Very often, there are links left unused at each node in a real system. In this article, we study the hypercube in which extra connections are added between pairs of nodes through otherwise unused links. Those extra connections are made in order to maximize the improvement of the performance measure of interest under various traffic distributions. The resulting hypercube, called the variant hypercube, requires a simple routing algorithm and is guaranteed not to create any traffic-congested point or link. The variant hypercube is found to achieve considerable reduction in diameter, and noticeable improvement in mean internode distance and traffic density. In addition, a variant hypercube is more cost-effective than a regular hypercube and does not suffer from practical implementation difficulty. As a result, it also appears advantageous for hypercube systems with no available unused links to augment each node so as to accommodate an extra link, provided that the building block is not pin limited and is allowed to do so.
Solving general sparse linear systems using conjugate gradient-type methods
Authors: Gallivan K. , Sameh A. , Zlatev Z.
Published: July 2004

The problem of finding an approximation of @@@@ =
A
†
b
(where
A
†
is the pseudo-inverse of
A
∈ @@@@

m
@@@@
n

with
m
≥
n
and
rank
(
A
) =
n
) is discussed. It is assumed that
A
is sparse but has neither a special pattern (as bandedness) nor a special property (as symmetry or positive definiteness). In this paper it is shown that preconditioners obtained by neglecting small elements during the decomposition of
A
into easily invertible matrices can be used efficiently with conjugate gradient-type methods if an adaptive strategy for deciding when an element is small is implemented. The resulting preconditioned methods are often better than the corresponding direct and pure iterative methods or those based on preconditionings in which elements are neglected when they appear in a predefined set of positions in the matrix, i.e. positional rather than numerical dropping. Numerical results are given to illustrate the performance of the CG-type methods preconditioned via numerical dropping.
Compiler techniques for data synchronization in nested parallel loops
Authors: Tang Peiyi , Yew Pen-Chung , Zhu Chuan-Qi
Published: July 2004

The major source of parallelism in ordinary programs is do loops. When loop iterations of parallelized loops are executed on multiprocessors, the cross-iteration data dependencies need to be enforced by synchronization between processors. Existing data synchronization schemes are either too simple to handle general nested loop structures with non-trivia array subscript functions or inefficient due to the large run-time overhead.

In this paper, we propose a new synchronization scheme based on two data-oriented synchronization instructions: synch_read(x,s) and synch_write(x,s). We present the algorithm to compute the ordering number, s, for each data access. Using our scheme, a parallelizing compiler can parallelize a general nested loop structure with complicated cross-iteration data dependencies. If the computations of ordering numbers cannot be done at compile time, the run-time overhead is smaller than the other existing run-time schemes.
SPARK
Authors: Saad Youcef , Wijshoff Harry A. G.
Published: July 2004

As the diversity of novel architectures expands rapidly there is a growing interest in studying the behavior of these architectures for computations arising in different applications. There has been significant efforts in evaluating the performance of supercomputers on typical dense computations, and several packages for this purpose have been developed, such as the Linpack benchmark, the Lawrence Livermore Loops, and the Los Alamos Kernels. On the other hand there has been little effort put into evaluating the performance of these architectures on the more complicated and perhaps more important sparse computations. In this paper a package is proposed to fill this gap. Its goal is not only to evaluate the performance of supercomputers on sparse computations, but also to analyze the machine-algorithm interaction.
Strategies for large-scale structural problems on high-performance computers
Authors: Noor Ahmed K. , Peters Jeanne M.
Published: July 2004

Novel computational strategies are presented for the analysis of large and complex structures. The strategies are based on generating the response of the complex structure using
large perturbations
from that of a simpler model, associated with a simpler structure (or a simpler mathematical/discrete model of the original structure). Numerical examples are presented to demonstrate the effectiveness of the strategies developed.
Incremental dependence analysis for interactive parallelization
Authors: Smith Kevin , Appelbe Bill , Stirewalt Kurt
Published: July 2004

Incrementally updating dependence information during interactive parallelization is a difficult proposition. We have developed a tool (PAT) that maintains dependence information during incremental transformations to a Fortran program, including loop parallelization, code
replication, alignment
and
shifting
, as well as
insertion
and
deletion
of code including parallel primitives. Our analysis is based on a variation on the standard approach to dependence graph generation, with program wide and local information separated in a
sequential
and a
parallel
dependence graph.
Designing algorithms on hierarchical memory multiprocessors
Authors: Brochard Luigi , Freau Alex
Published: July 2004

We study here the behavior of two numerical algorithms (matrix multiplications and finite difference methods) on a three-level memory hierarchy multiprocessor RP3. Using different versions of these algorithms which differ on data placement (global, local, global and cacheable, local and cacheable) and on data access (blocked on non-blocked), we study the impact of these parameters on the performance of the program. This performance analysis is done using a very accurate monitoring system (VPMC) which records instructions, memory requests, cache requests and misses. We perform also a theoretical performance analysis of these programs using a model of computation and communication. Good agreements are found between theoretical and experimental results. As a conclusion we discuss the use of local memory on such a machine and show it is not worth with the RP3 ratio of communication between local and global memories. We also discuss optimal use of cache, show the optima can only be met under some cache properties (private store-in cache with user control of write-back) and show blocked optimal algorithms are to be used to meet it.
Impact of task duplication on static-scheduling performance in multiprocessor systems with variable execution-time tasks
Authors: Luque Emilio , Ripoll Ana , Hernández Porfidio , Margalef Tomás
Published: July 2004

The problem of scheduling a set of partially ordered tasks on a nonpreemptive multiprocessor system of identical processors assuming that the execution time of some tasks can vary within a set of known values is studied in an effort to construct a more realistic static schedule.

A new heuristic algorithm (CP/MISF/TD) based on task duplication is proposed. The effectiveness of the algorithm is proved by comparing the results obtained for a wide variety of task graphs with the ones obtained by applying the classical list scheduling algorithms which consider fixed time tasks.

Keywords: Static scheduling, List scheduling, Heuristic algorithms, Task duplication, Multiprocessor systems.
Performance of the KORA-2 cache replacement scheme
Authors: Khalid Humayun
Published: July 2004

In this paper, we propose a new strategy (KORA-2) for the replacement of lines in cache memories. The algorithm is efficient and easily implementable. It is basically an extension of our previous work presented in [1]-[5]. Key to our algorithm is to identify and discard inactive lines relatively quickly as opposed to the conventional replacement algorithms. Trace-driven simulations were performed for 42 different cache configurations using benchmark programs from SPEC92 (Standard performance Evaluation Corporation) benchmark suites. Simulation results illustrate that our algorithm can provide a peak value of approximately 8.71% improvement in the miss ratio over the best performing conventional algorithm (LRU) for the selected benchmark trace files generated from SPEC programs. This translates to a savings of hundreds of thousands of misses for typical programs referencing well over 100 million addresses.
Out-of-order execution in sequentially consistent shared-memory systems
Authors: Hu Weiwu , Xia Peisu
Published: July 2004

Typical implementation of sequential consistency in shared-memory systems requires each access to be delayed until the previous access in the same process completes. This is detrimental to system performance. This paper proposes a way of out-of-order execution in sequentially consistent shared-memory systems. It first builds an execution model of shared-memory systems, studies the event ordering condition for correct executions in write atomic and write nonatomic systems, and then proposes and proves that out-of-order execution does not influence the correctness of an execution providing certain condition is met. Implementation strategy of out-of-order execution in sequentially consistent shared-memory systems is also discussed.
An analysis of correlation and predictability
Authors: Evers Marius , Patel Sanjay J. , Chappell Robert S. , Patt Yale N.
Published: July 2004

Pipeline flushes due to branch mispredictions is one of the most serious problems facing the designer of a deeply pipelined, superscalar processor. Many branch predictors have been proposed to help alleviate this problem, including two-level adaptive branch predictors and hybrid branch predictors.Numerous studies have shown which predictors and configurations best predict the branches in a given set of benchmarks. Some studies have also investigated effects, such as pattern history table interference, that can be detrimental to the performance of these predictors. However, little research has been done on which characteristics of branch behavior make predictors perform well.In this paper, we investigate and quantify reasons why branches are predictable. We show that some of this predictability is not captured by the two-level adaptive branch predictors. An understanding of the predictability of branches may lead to insights ultimately resulting in better or less complex predictors. We also investigate and quantify what fraction of the branches in each benchmark is predictable using each of the methods described in this paper.
Branch prediction based on universal data compression algorithms
Authors: Federovsky Eitan , Feder Meir , Weiss Sholomo
Published: July 2004

Data compression and prediction are closely related. Thus prediction methods based on data compression algorithms have been suggested for the branch prediction problem. In this work we consider two universal compression algorithms: prediction by partial matching (PPM), and a recently developed method, context tree weighting (CTW). We describe the prediction algorithms induced by these methods. We also suggest adaptive algorithms --- variations of the basic methods that attempt to fit limited memory constraints and to match the non-stationary nature of the branch sequence. Furthermore, we show how to incorporate address information and to combine other relevant data. Finally, we present simulation results for selected programs from the SPECint95, SYSmark/32, SYSmark/NT, and transactional processing benchmarks. Our results are most promising in programs with difficult to predict branch behavior.
Modeling program predictability
Authors: Sazeides Yiannakis , Smith James E.
Published: July 2004

Basic properties of program predictability --- for both values and control --- are defined and studied. We take the view that program predictability originates at certain points during a program's execution, flows through subsequent instructions, and then ends at other points in the program. These key components of predictability:
generation, propagation,
and
termination;
are defined in terms of a model. The model is based on a graph derived from dynamic data dependences and a predictor.Using the SPEC95 benchmarks, we analyze the predictability phenomena both separately and in combination. Examples are provided to illustrate relationships between model-based characteristics and program constructs. It is shown that most predictability derives from program control structure and immediate values, not program input data. Furthermore, most predictability originates from a relatively small number of generate points. The analysis of obtained results suggests a number of ramifications regarding predictability and its use.
Declustered disk array architectures with optimal and near-optimal parallelism
Authors: Alvarez Guillermo A. , Burkhard Walter A. , Stockmeyer Larry J. , Cristian Flaviu
Published: July 2004

This paper investigates the placement of data and parity on redundant disk arrays. Declustered organizations have been traditionally used to achieve fast reconstruction of a failed disk's contents. In previous work, Holland and Gibson identified six desirable properties for ideal layouts; however, no declustered layout satisfying all properties has been published in the literature. We present a complete, constructive characterization of the collection of ideal declustered layouts possessing all six properties. Given that ideal layouts exist only for a limited set of configurations, we also present two novel layout families.

P
RIME

and

R
ELPR

can tolerate multiple failures in a wide variety of configurations with slight deviations from the ideal. Our simulation studies show that the new layouts provide excellent parallel access performance and reduced incremental loads during degraded operation, when compared with previously published layouts. For large accesses and under high loads, response times for the new layouts are typically smaller than those of previously published declustered layouts by a factor of 2.5.
Memory dependence prediction using store sets
Authors: Chrysos George Z. , Emer Joel S.
Published: July 2004

For maximum performance, an out-of-order processor must issue load instructions as early as possible, while avoiding memory-order violations with prior store instructions that write to the same memory location. One approach is to use memory dependence prediction to identify the stores upon which a load depends, and communicate that information to the instruction scheduler. We designate the set of stores upon which each load has depended as the load's "store set". The processor can discover and use a load's store set to accurately predict the earliest time the load can safely execute. We show that store sets accurately predict memory dependencies in the context of large instruction window, superscalar machines, and allow for near-optimal performance compared to an instruction scheduler with perfect knowledge of memory dependencies. In addition, we explore the implementation aspects of store sets, and describe a low cost implementation that achieves nearly optimal performance.
Accurate indirect branch prediction
Authors: Driesen Karel , Hölzle Urs
Published: July 2004

Indirect branch prediction is likely to become increasingly important in the future because indirect branches occur more frequently in object-oriented programs. With misprediction rates of around 25% on current processors, indirect branches can incur a significant fraction of branch misprediction overhead even though they remain less frequent than the more predictable conditional branches. We investigate a wide range of two-level predictors dedicated exclusively to indirect branches. Starting with predictors that use full-precision addresses and unlimited tables, we progressively introduce hardware constraints and minimize the loss of predictor performance at each step. For programs from the SPECint95 suite as well as a suite of large C++ applications, a two-level predictor achieves a misprediction rate of 9.8% with a 1K-entry table and 7.3% with an 8K-entry table, representing more than a threefold improvement over an ideal BTB. A hybrid predictor further reduces the misprediction rates to 8.98% (1K) and 5.95% (8K).
Dynamic IPC/clock rate optimization
Authors: Albonesi David H.
Published: July 2004

Current microprocessor designs set the functionality and clock rate of the chip at design time based on the configuration that achieves the best overall performance over a range of target applications. The result may be poor performance when running applications whose requirements are not well-matched to the particular hardware organization chosen. We present a new approach called Complexity-Adaptive Processors (CAPs) in which the IPC/clock rate tradeoff can be altered at runtime to dynamically match the changing requirements of the instruction stream. By exploiting repeater methodologies used increasingly in deep sub-micron designs, CAPs achieve this flexibility with potentially no cycle time impact compared to a fixed architecture. Our preliminary results in applying this approach to on-chip caches and instruction queues indicate that CAPs have the potential to significantly outperform conventional approaches on workloads containing both general-purpose and scientific applications.
Performance modeling and code partitioning for the DS architecture
Authors: Zhang Yinong , Adams George B.
Published: July 2004

DS (Decoupled-Superscalar) is a new microarchitecture that combines decoupled and superscalar techniques to exploit instruction level parallelism. Issue bandwidth is increased while circuit complexity growth is controlled with little negative impact on performance. Programs for DS are compiled into two instruction substreams: the dominant substream navigates the control flow and the rest of computational task is shared between the dominant and subsidiary substreams. Each substream is processed by a separate superscalar core realizable with current VLSI technology. DS machines are binary compatible with superscalar machines having the same instruction set, and a family of DS machines is binary compatible without recompilation.DS run time behavior is examined with an analytical model. A novel technique for controlling slip between substreams is introduced. Code partitioning issues of instruction count balancing and residence time balancing, important to any split-stream scheme, are discussed. Simulation shows DS achieves performance comparable to an aggressive superscalar, but with potentially less complex hardware and faster clock rate.
Flexible use of memory for replication/migration in cache-coherent DSM multiprocessors
Authors: Soundararajan Vijayaraghavan , Heinrich Mark , Verghese Ben , Gharachorloo Kourosh , Gupta Anoop , Hennessy John
Published: July 2004

Given the limitations of bus-based multiprocessors, CC-NUMA is the scalable architecture of choice for shared-memory machines. The most important characteristic of the CC-NUMA architecture is that the latency to access data on a remote node is considerably larger than the latency to access local memory. On such machines, good data locality can reduce memory stall time and is therefore a critical factor in application performance.In this paper we study the various options available to system designers to transparently decrease the fraction of data misses serviced remotely. This work is done in the context of the Stanford FLASH multiprocessor. FLASH is unique in that each node has a single pool of DRAM that can be used in a variety of ways by the programmable memory controller. We use the programmability of FLASH to explore different options for cache-coherence and data-locality in compute-server workloads. First, we consider two protocols for providing base cache-coherence, one with centralized directory information (dynamic pointer allocation) and another with distributed directory information (SCI). While several commercial systems are based on SCI, we find that a centralized scheme has superior performance. Next, we consider different hardware and software techniques that use some or all of the local memory in a node to improve data locality. Finally, we propose a hybrid scheme that combines hardware and software techniques. These schemes work on the same base platform with both user and kernel references from the workloads. The paper thus offers a realistic and fair comparison of replication/migration techniques that has not previously been feasible.
Low load latency through sum-addressed memory (SAM)
Authors: Lynch William L. , Lauterbach Gary , Chamdani Joseph I.
Published: July 2004

Load latency contributes significantly to execution time. Because most cache accesses hit, cache-hit latency becomes an important component of expected load latency. Most modern microprocessors have base+offset addressing loads; thus effective cache-hit latency includes an addition as well as the RAM access.This paper introduces a new technique used in the UltraSPARC III microprocessor, Sum-Addressed Memory (SAM), which performs true addition using the decoder of the RAM array, with very low latency. We compare SAM with other methods for reducing the add part of load latency. These methods include sum-prediction with recovery, and bitwise indexing with duplicate-tolerance. The results demonstrate the superior performance of SAM.
Analytic evaluation of shared-memory systems with ILP processors
Authors: Sorin Daniel J. , Pai Vijay S. , Adve Sarita V. , Vernon Mary K. , Wood David A.
Published: July 2004

This paper develops and validates an analytical model for evaluating various types of architectural alternatives for shared-memory systems with processors that aggressively exploit instruction-level parallelism. Compared to simulation, the analytical model is many orders of magnitude faster to solve, yielding highly accurate system performance estimates in seconds.The model input parameters characterize the ability of an application to exploit instruction-level parallelism as well as the interaction between the application and the memory system architecture. A trace-driven simulation methodology is developed that allows these parameters to be generated over 100 times faster than with a detailed execution-driven simulator.Finally, this paper shows that the analytical model can be used to gain insights into application performance and to evaluate architectural design trade-offs.
Speculation techniques for improving load related instruction scheduling
Authors: Yoaz Adi , Erez Mattan , Ronen Ronny , Jourdan Stephan
Published: July 2004

State of the art microprocessors achieve high performance by executing multiple instructions per cycle. In an out-of-order engine, the instruction scheduler is responsible for dispatching instructions to execution units based on dependencies, latencies, and resource availability. Most existing instruction schedulers are doing a less than optimal job of scheduling memory accesses and instructions dependent on them, for the following reasons:• Memory dependencies cannot be resolved prior to execution, so loads are not advanced ahead of preceding stores.• The dynamic latencies of load instructions are unknown, so scheduling dependent instructions is based on either optimistic load-use delay (may cause re-scheduling and re-execution) or pessimistic delay (creating unnecessary delays).• Memory pipelines are more expensive than other execution units, and as such, are a scarce resource. Currently, an increase in the memory execution bandwidth is usually achieved through multi-banked caches where bank conflicts limit efficiency.In this paper we present three techniques to address these scheduler limitations. One is to improve the scheduling of load instructions by using a simple memory disambiguation mechanism. The second is to improve the scheduling of load dependent instructions by employing a Data Cache Hit-Miss Predictor to predict the dynamic load latencies. And the third is to improve the efficiency of load scheduling in a multi-banked cache through Cache-Bank Prediction.
Effective jump-pointer prefetching for linked data structures
Authors: Roth Amir , Sohi Gurindar S.
Published: July 2004

Current techniques for prefetching linked data structures (LDS) exploit the work available in one loop iteration or recursive call to overlap pointer chasing latency. Jump pointers, which provide direct access to non-adjacent nodes, can be used for prefetching when loop and recursive procedure bodies are small and do not have sufficient work to overlap a long latency. This paper describes a framework for jump-pointer prefetching (JPP) that supports four prefetching idioms: queue, full, chain, and root jumping and three implementations: software-only, hardware-only, and a cooperative software/hardware technique. On a suite of pointer intensive programs, jump pointer prefetching reduces memory stall time by 72% for software, 83% for cooperative and 55% for hardware, producing speedups of 15%, 20% and 22% respectively.
Performance of image and video processing with general-purpose processors and media ISA extensions
Authors: Ranganathan Parthasarathy , Adve Sarita , Jouppi Norman P.
Published: July 2004

This paper aims to provide a quantitative understanding of the performance of image and video processing applications on general-purpose processors, without and with media ISA extensions. We use detailed simulation of 12 benchmarks to study the effectiveness of current architectural features and identify future challenges for these workloads.Our results show that conventional techniques in current processors to enhance instruction-level parallelism (ILP) provide a factor of 2.3X to 4.2X performance improvement. The Sun VIS media ISA extensions provide an additional 1.1X to 4.2X performance improvement. The ILP features and media ISA extensions significantly reduce the CPU component of execution time, making 5 of the image processing benchmarks memory-bound.The memory behavior of our benchmarks is characterized by large working sets and streaming data accesses. Increasing the cache size has no impact on 8 of the benchmarks. The remaining benchmarks require relatively large cache sizes (dependent on the display sizes) to exploit data reuse, but derive less than 1.2X performance benefits with the larger caches. Software prefetching provides 1.4X to 2.5X performance improvement in the image processing benchmarks where memory is a significant problem. With the addition of software prefetching, all our benchmarks revert to being compute-bound.
A hardware-driven profiling scheme for identifying program hot spots to support runtime optimization
Authors: Merten Matthew C. , Trick Andrew R. , George Christopher N. , Gyllenhaal John C. , Hwu Wen-mei W.
Published: July 2004

This paper presents a novel hardware-based approach for identifying, profiling, and monitoring hot spots in order to support runtime optimization of general purpose programs. The proposed approach consists of a set of tightly coupled hardware tables and control logic modules that are placed in the retirement stage of a processor pipeline removed from the critical path. The features of the proposed design include rapid detection of program hot spots after changes in execution behavior, runtime-tunable selection criteria for hot spot detection, and negligible overhead during application execution. Experiments using several SPEC95 benchmarks, as well as several large WindowsNT applications, demonstrate the promise of the proposed design.
Value prediction in VLIW machines
Authors: Nakra Tarun , Gupta Rajiv , Soffa Mary Lou
Published: July 2004

The performance of VLIW architectures is dependent on the capability of the compiler to detect and exploit instruction-level parallelism during instruction scheduling. To exploit the detected parallelism, instructions are reordered to reduce the length of the code schedule and minimize the cycle count for execution. Code reordering is limited by the dependencies among instructions arising from both control flow and data flow. In this paper, we present the design of a VLIW architecture that uses value prediction to remove data dependencies and improve the instruction schedule. Our architecture consists of two execution engines, one for executing the original VLIW code, and the other for executing compensation code after a misprediction. Any code executed due to mispredictions is executed in parallel with the VLIW instructions. The instruction set and hardware of a traditional VLIW machine are modified accordingly to support this type of concurrent execution. The efficacy of the proposed architecture is demonstrated by implementing the prediction model in the Trimaran compiler infrastructure and studying the speedups that result due to the parallel execution of compensation code.
Weak ordering—a new definition
Authors: Adve Sarita V. , Hill Mark D.
Published: July 2004

A memory model for a shared memory, multiprocessor commonly and often implicitly assumed by programmers is that of
sequential consistency
. This model guarantees that all memory accesses will appear to execute atomically and in program order. An alternative model,
weak ordering
, offers greater performance potential. Weak ordering was first defined by Dubois, Scheurich and Briggs in terms of a set of rules for hardware that have to be made visible to software.

The central hypothesis of this work is that programmers prefer to reason about sequentially consistent memory, rather than having to think about weaker memory, or even write buffers. Following this hypothesis, we re-define weak ordering as a contract between software and hardware. By this contract, software agrees to some formally specified constraints, and hardware agrees to appear sequentially consistent to at least the software that obeys those constraints. We illustrate the power of the new definition with a set of software constraints that forbid data races and an implementation for cache-coherent systems that is not allowed by the old definition.
APRIL
Authors: Agarwal Anant , Lim Beng-Hong , Kranz David , Kubiatowicz John
Published: July 2004

Processors in large-scale multiprocessors must be able to tolerate large communication latencies and synchronization delays. This paper describes the architecture of a rapid-context-switching processor called APRIL with support for fine-grain threads and synchronization. APRIL achieves high single-thread performance and supports virtual dynamic threads. A commercial RISC-based implementation of APRIL and a run-time software system that can switch contexts in about 10 cycles is described. Measurements taken for several parallel applications on an APRIL simulator show that the overhead for supporting parallel tasks based on
futures
is reduced by a factor of two over a corresponding implementation on the Encore Multimax. The scalability of a multiprocessor based on APRIL is explored using a performance model. We show that the SPARC-based implementation of APRIL can achieve close to 80% processor utilization with as few as three resident threads per processor in a large-scale cache-based machine with an average base network latency of 55 cycles.
Performance measurement and trace driven simulation of parallel CAD and numeric applications on a hypercube multicomputer
Authors: Hsu Jiun-Ming , Banerjee Prithviraj
Published: July 2004

This paper presents the performance evaluation, workload characterization and trace driven simulation of a hypercube multi-computer running realistic workloads. Six representative parallel applications were selected as benchmarks. Software monitoring techniques were then used to collect execution traces. Based on the measurement results, we investigated both the computation and communication behavior of these parallel programs, including CPU utilization, computation task granularity, message interarrival distribution, the distribution of waiting times in receiving messages, and message length and destination distributions. The localities in communication were also studied. A trace driven simulation environment was developed to study the behavior of the communication hardware under real workload. Simulation results on DMA and link utilizations are reported.
Generation and analysis of very long address traces
Authors: Borg Anita , Kessler R. E. , Wall David W.
Published: July 2004

Existing methods of generating and analyzing traces suffer from a variety of limitations including complexity, inaccuracy, short length, inflexibility, or applicability only to CISC machines. We use a trace generation mechanism based on link-time code modification which is simple to use, generates accurate long traces of multi-user programs, runs on a RISC machine, and can be flexibly controlled. On-the-fly analysis of the traces allows us to get accurate performance data for large second-level caches. We compare the performance of systems with 512K to 16M second-level caches, and show that for today's large programs, second-level caches of more than 4MB may be unnecessary. We also show that set associativity in second-level caches of more than 1MB does not significantly improve system performance. In addition, our experiments also provide insights into first-level and second-level cache line size.
The TLB slice—a low-cost high-speed address translation mechanism
Authors: Taylor George , Davies Peter , Farmwald Michael
Published: July 2004

The MIPS R6000 microprocessor relies on a new type of translation lookaside buffer — called aTLB slice— which is less than one-tenth the size of a conventional TLB and as fast as one multiplexer delay, yet has a high enough hit rate to be practical. The fast translation makes it possible to use a physical cache without adding a translation stage to the processor's pipeline. The small size makes it possible to include address translation on-chip, even in a technology with a limited number of devices.

The key idea behind the TLB slice is to have both a virtual tag and a physical tag on a physically-indexed cache. Because of the virtual tag, the TLB slice needs to hold only enough physical page number bits — typically 4 to 8 — to complete the physical cache index, in contrast with a conventional TLB, which needs to hold both a virtual page number and a physical page number. The virtual page number is unnecessary because the TLB slice needs to provide only a hint for the translated physical address rather than a guarantee. The full physical page number is unnecessary because the cache hit logic is based on the virtual tag. Furthermore, if the cache is multi-level and references to the TLB slice are “shielded” by hits in a virtually indexed primary cache, the slice can get by with very few entries, once again lowering its cost and increasing its speed. With this mechanism, the simplicity of a physical cache can been combined with the speed of a virtual cache.
Completion time multiple branch prediction for enhancing trace cache performance
Authors: Rakvic Ryan , Black Bryan , Shen John Paul
Published: July 2004

The need for multiple branch prediction is inherent to wide instruction fetching. This paper presents a completion time multiple branch predictor called the Tree-based Multiple Branch Predictor (TMP) that builds on previous single branch prediction techniques. It employs a tree structure of branch predictors, or tree-node predictors, and achieves accurate multiple branch prediction by leveraging the high accuracies of the individual branch predictors. A highly-efficient TMP design uses the 2-bit saturating counters for the tree-node predictors. To achieve higher prediction rate, the TMP employs two-level schemes for the tree-node predictors resulting in a three-level TMP design. Placing the TMP at completion time reduces the critical latency in the front-end of the pipeline; the resultant longer update latency does not significantly impact the overall performance. In this paper the TMP is applied to a trace cache design and shown to be very effective in increasing its performance.

Results: A realistic-size TMP (72KB) can predict 1, 2, 3, and 4 consecutive blocks with compounded prediction accuracies of 96%, 93%, 87%, and 82%, respectively. The block-based trace cache with this TMP achieves 4.75 IPC for SPECint95 on an idealized machine, which is a 20% performance improvement over the original design [1]. This improved performance is 8% above that of a conventional I-cache design with perfect single branch prediction.
Understanding the backward slices of performance degrading instructions
Authors: Zilles Craig B. , Sohi Gurindar S.
Published: July 2004

For many applications, branch mispredictions and cache misses limit a processor's performance to a level well below its peak instruction throughput. A small fraction of static instructions, whose behavior cannot be anticipated using current branch predictors and caches, contribute a large fraction of such performance degrading events. This paper analyzes the dynamic instruction stream leading up to these performance degrading instructions to identify the operations necessary to execute them early. The backward slice (the subset of the program that relates to the instruction) of these performance degrading instructions, if small compared to the whole dynamic instruction stream, can be pre-executed to hide the instruction's latency. To overcome conservative dependance assumptions that result in large slices, speculation can be used, resulting in speculative slices.

This paper provides an initial characterization of the backward slices of L2 data cache misses and branch mispredictions, and shows the effectiveness of techniques, including memory dependence prediction and control independence, for reducing the size of these slices. Through the use of these techniques, many slices can be reduced to less than one tenth of the full dynamic instruction stream when considering the 512 instructions before the performance degrading instruction.
Circuits for wide-window superscalar processors
Authors: Henry Dana S. , Kuszmaul Bradley C. , Loh Gabriel H. , Sami Rahul
Published: July 2004

Our program benchmarks and simulations of novel circuits indicate that large-window processors are feasible. Using our redesigned superscalar components, a large-window processor implemented in today's technology can achieve an increase of 10-60% (geometric mean of 31%) in program speed compared to today's processors. The processor operates at clock speeds comparable to today's processors, but achieves significantly higher ILP.

To measure the impact of a large window on clock speed, we design and simulate new implementations of the logic components that most limit the critical path of our large-window processor: the schedule logic and the wake-up logic. We use log-depth cyclic segmented prefix (CSP) circuits to reimplement these components. Our layouts and simulations of critical paths through these circuits indicate that our large-window processor could be clocked at frequencies exceeding 500MHz in today's technology. Our commit logic and rename logic can also run at these speeds.

To measure the impact of a large window on ILP, we compare two microarchitectures, the first has a 128-instruction window, an 8-wide fetch unit, and 20-wide issue (four integer, branch, multiply, float, and memory units), whereas the second has a 32-instruction window, and a 4-wide fetch unit and is comparable to today's processors. For each, we simulate different window reuse and bypass policies. Our simulations show that the large-window processor achieves significantly higher IPC. This performance increase comes despite the fact that the large-window processor uses a wrap-around window while the small-window processor uses a compressing window, thus effectively increasing its number of outstanding instructions. Furthermore, the large-window processor sometimes pays an extra clock cycle for bypassing.
Clock rate versus IPC
Authors: Agarwal Vikas , Hrishikesh M. S. , Keckler Stephen W. , Burger Doug
Published: July 2004

The doubling of microprocessor performance every three years has been the result of two factors: more transistors per chip and superlinear scali ng of the processor clock with technology generation. Our results show that, due to both diminishing improvements in clock rates and poor wire scaling as semiconductor devices shrink, the achievable performance growth of conventional microarchitectures will slow substantially. In this paper, we describe technology-driven models for wire capacitance, wire delay, and microarchitectural component delay. Using the results of these models, we measure the simulated performance—estimating both clock rate and IPC —of an aggressive out-of-order microarchitecture as it is scaled from a 250nm technology to a 35nm technology. We perform this analysis for three clock scaling targets and two microarchitecture scaling strategies:
pipeline scaling
and
capacity scaling.
We find that no scaling strategy permits annual performance improvements of better than 12.5%, which is far worse than the annual 50-60% to which we have grown accustomed.
Vector instruction set support for conditional operations
Authors: Smith J. E. , Faanes Greg , Sugumar Rabin
Published: July 2004

Vector instruction sets are receiving renewed interest because of their applicability to multimedia. Current multimedia instruction sets use short vectors with SIMD implementations, but long vector, pipelined implementations have a number of advantages and arc a logical next step in multimedia ISA development.

Support for conditional operations (as occur in loops containing IF statements) is an important aspect of a vector ISA. Seven ISA alternatives for implementing conditional operations are systematically explored. Performance considerations are discussed through evaluation of a typical IF loop over a range of vector lengths and
true
conditional values. An approach using masked operations is shown to be one of the better methods, especially if its implementation is able to skip over blocks of
false
mask bits. Additional analyses of complex IF loops and parallel pipeline implementations support the masked operation approach. The paper concludes with a practical implementation of masked operations that skips over power-of-2-length blocks of false values. This implementation is simpler than skipping arbitrary-length blocks and provides similar performance.