bluuebunny/crossref_metadata_2025 huggingface dataset:
Performance comparison of ILP machines with cycle time evaluation
Authors: Hara Tetsuya , Ando Hideki , Nakanishi Chikako , Nakaya Masao
Published: July 2004

Many studies have investigated performance improvement through exploiting instruction-level parallelism (ILP) with a particular architecture. Unfortunately, these studies indicate performance improvement using the number of cycles that are required to execute a program, but do not quantitatively estimate the penalty imposed on the cycle time from the architecture. Since the performance of a microprocessor must be measured by its execution time, a cycle time evaluation is required as well as a cycle count speedup evaluation. Currently, superscalar machines are widely accepted as the machines which achieve the highest performance. On the other hand, because of hardware simplicity and instruction scheduling sophistication, there is a perception that the next generation of microprocessors will be implemented with a VLIW architecture. A simple VLIW machine, however, has a serious weakness regarding speculative execution. Thus, it is a question whether a simple VLIW machine really outperforms a superscalar machine. We recently proposed a mechanism called
predicating
that supports speculative execution for the VLIW machine, and showed a significant cycle count speedup over a scalar machine. Although the mechanism is simple, it is unknown how much it imposes a penalty on the cycle time, and how much the performance is improved as a result. This paper evaluates both the cycle count speedup and the cycle time for three ILP machines: a superscalar machine, a simple VLIW machine, and the VLIW machine with predicating. The evaluation results show that the simple VLIW machine slightly outperforms the superscalar machine, while the VLIW machine with predicating achieves a significant speedup of 1.41x over the superscalar machine.
A router architecture for real-time point-to-point networks
Authors: Rexford Jennifer , Hall John , Shin Kang G.
Published: July 2004

Parallel machines have the potential to satisfy the large computational demands of emerging real-time applications. These applications require a predictable communication network, where
time-constrained
traffic requires bounds on latency or throughput while good average performance suffices for
best-effort
packets. This paper presents a router architecture that tailors low-level routing, switching, arbitration and flow-control policies to the conflicting demands of each traffic class. The router implements deadline-based scheduling, with packet switching and table-driven multicast routing, to bound end-to-end delay for time-constrained traffic, while allowing best-effort traffic to capitalize on the low-latency routing and switching schemes common in modern parallel machines. To limit the cost of servicing time-constrained traffic, the router shares packet buffers and link-scheduling logic between the multiple output ports. Verilog simulations demonstrate that the design meets the performance goals of both traffic classes in a single-chip solution.
Compiler and hardware support for cache coherence in large-scale multiprocessors
Authors: Choi Lynn , Yew Pen-Chung
Published: July 2004

In this paper, we study a hardware-supported, compiler directed (HSCD) cache coherence scheme, which can be implemented on a large-scale multiprocessor using off-the-shelf microprocessors, such as the Cray T3D. It can be adapted to various cache organizations, including multi-word cache lines and byte-addressable architectures. Several system related issues, including critical sections, inter-thread communication, and task migration have also been addressed. The cost of the required hardware support is small and proportional to the cache size. The necessary compiler algorithms, including intra- and interprocedural array data-flow analysis, have been implemented on the Polaris compiler [17].From our simulation study using the Perfect Club benchmarks, we found that, in spite of the conservative analysis made by the compiler, the performance of the proposed HSCD scheme can be comparable to that of a full-map hardware directory scheme. With its comparable performance and reduced hardware cost, the scheme can be a viable alternative for large-scale multiprocessors, such as the Cray T3D, that rely on users to maintain data coherence.
STiNG
Authors: Lovett Tom , Clapp Russell
Published: July 2004

"STiNG" is a Cache Coherent Non-Uniform Memory Access (CC-NUMA) Multiprocessor designed and built by Sequent Computer Systems, Inc. It combines four processor Symmetric Multi-processor (SMP) nodes (called Quads), using a Scalable Coherent Interface (SCI) based coherent interconnect. The Quads are based on the Intel P6 processor and the external bus it defines. In addition to 4 P6 processors, each Quad may contain up to 4 GBytes of system memory, 2 Peripheral Component Interface (PCI) busses for I/O, and a Lynx board. The Lynx board provides the datapath to the SCI-based interconnect and ensures system-wide cache coherency. STiNG is one of the first commercial CC-NUMA systems to be built. This paper describes the motivation for building STiNG as well as its architecture and implementation. In addition, performance analysis is provided for On-Line Transaction Processing (OLTP) and Decision Support System (DSS) workloads. Finally, the status of the current implementation is reviewed.
The RISC processor DMN-6: a unified data-control flow architecture
Authors: Páez-Monzón Gerard , Páez-Monzón Charles
Published: July 2004

This work presents an academic RISC processor architecture, named DMN-6 that executes every instruction in the datapath. It concentrates all the movement, branch and alu instructions in the arithmetic-logic unit. The idea is to normalize the control signal generation for an integer functional unit. This is obtained by implementing a number of queue registers of different deepness around the datapath unit. These queues will control an assigned logic corresponding to a stage in the pipeline. The architecture reduces even more the complexity of a pipelined program execution. The main features are : Load/Store architecture, 4-stage pipeline, integer arithmetic, sixteen byte registers, internal separate data and instruction main memories, thirteen 16-bit instruction words.
Efficient data sharing with conditional remote memory transfers
Authors: Hummel Susan Flynn
Published: July 2004

Remote memory transfers (RMTs) allow processors to access non-local memories without involving the remote processor. As the only interprocessor synchronization required is setting flags on the local and remote processors after the transfer is complete, RMTs do not entail the overhead due to the handshaking and buffering of message passing nor require the complex hardware of cache-coherent shared memory. The minimal synchronization of RMTs, however, necessiates extra remote communications to enforce common data sharing paradigms, such as producer/consumer. We propose a new hardware mechanism: the conditional RMT (CMRT). CRMTs succeed or fail depending on the state of the remote data. We describe potential CRMT hardware definitions, and illustrate their utility by presenting efficient software protocols for producer/consumer and check-in/check-out data sharing.
Eliminating operand read latency
Authors: Widigen Larry , Sowadsky Elliot , McGrath Kevin
Published: July 2004

Programs generally exhibit load or memory operand read latencies that account for a significant portion of pipeline interlocks or stalls. In this paper we present an approach for the prediction of operand read data during the instruction fetch stage of a pipelined processor. For the X86 programs studied many have a significant percentage of such operand data that can be predicted with a high accuracy.
On the use of SPEC benchmarks in computer architecture research
Authors: Weicker Reinhold
Published: July 2004

Benchmarks, in particular the SPEC CPU benchmarks, are frequently used in academic computer research. With ASPLOS-7 as an example, observations about such usage are reported, and suggestions are made for a meaningful use of benchmarks in computer architecture research. Forward-looking computer architecture research may need more than one benchmark collection.
What should graduate students know before joining a large computer architecture project?
Authors: Mukherjee Shubhendu S.
Published: July 2004

Large projects have become common in the computer architecture research community today. This article examines some of the things that graduate students who become involved in such large projects should be aware of.The purpose of this article is not to advocate that a graduate student should join a large project; rather, this article should be viewed as an aid that helps a new graduate student make this decision.
A new cache replacement scheme based on backpropagation neural networks
Authors: Khalid Humayun
Published: July 2004

In this paper, we present a new neural network-based algorithm,
KORA
(
K
halid Shad
O
w
R
eplacement
A
lgorithm), that uses backpropagation neural network (BPNN) for the purpose of guiding the line/block replacement decisions in cache. This work is a continuation of our previous research presented in [1]-[3]. The KORA algorithm attempts to approximate the replacement decisions made by the optimal scheme (OPT). The key to our algorithm is to identify and subsequently discard the dead lines in cache memories. This allows our algorithm to provide better cache performance as compared to the conventional LRU (Least Recently Used), MRU (Most Recently Used), and FIFO (First In First Out) replacement policies. Extensive trace-driven simulations were performed for 30 different cache configurations using different SPEC (Standard Performance Evaluation Corp.) programs. Simulation results have shown that KORA can provide substantial improvement in the miss ratio over the conventional algorithms. Our work opens new dimensions for research in the development of new and improved page replacement schemes for virtual memory systems and disk caches.
Internet Nuggets
Authors: Thorson Mark
Published: July 2004

This column consists of selected traffic from the
comp.arch
newsgroup, a forum for discussion of computer architecture on Internet---an international computer network.
The LDF 100: a large grain dataflow parallel processor
Authors: Kaplan Ian
Published: July 2004

The LDF 100 is a large grain dataflow parallel processor. The systems is designed to be incrementally expandable from 10 to over 128 processing elements. To avoid memory contention or prohibitive cost, the LDF 100 uses a distributed memory architecture. The LDF 100 also supports parallelism in the processing element. Each processing element consists of two microprocessors. One microprocessor is responsible for collecting data from the dataflow bus and one microprocessor is responsible for application execution.
An improvement of I/O function for auxiliary storage
Authors: Nagashima Umpei , Nishimoto Fumio , Shibata Takashi , Itoh Hiroshi , Gotoh Minoru
Published: July 2004

New I/O technique for external auxiliary storage: magnetic disk unit, has been developed to improve the I/O performance on HITAC VOS3/ES1 with usual hardware architecture. Since the I/O technique is based on the idea that the sequence of I/O processes should be divided to some groups and be executed in parallel, and is quite similar to a pipeline on vector computer, we call it Parallel I/O (PIO).

The PIO function has been realized and opened to end-users without any change to previous protocols.

Comparison of actual performance of PIO with 16 degrees of parallelization (16 PIO), the speed of the PIO is about 26 times faster than the standard (sequential) I/O technique by using chained schedule function. In the case of 8 PIO, PIO is 13 times faster than the standard I/O technique. The efficiency of PIO correlates well with the degree of parallelization. Elapsed time is inversely proportional to the degree of parallelization. The change of acceleration ratio of PIO to the standard I/O is normally proportional to the degree of parallelization.

The PIO is quite efficient for large scale supercomputing because I/O between external auxiliary storage and CPU is indispensable in large scale computations. Since the performance of I/O has not been improved, while the performance of supercomputer has made remarkable progress in CPU speed, I/O speed may become bottleneck for computations with supercomputers.
Schur complement preconditioned conjugate gradient methods for spline collocation equations
Authors: Christara Christina C.
Published: July 2004

We are interested in the efficient solution of linear second order Partial Differential Equation (PDE) problems on rectangular domains. The PDE discretisation scheme used is of Finite Element type and is based on quadratic splines and the collocation methodology. We integrate the Quadratic Spline Collocation (QSC) discretisation scheme with a Domain Decomposition (DD) technique. We develop DD motivated orderings of the QSC equations and unknowns and apply the Preconditioned Conjugate Gradient (PCG) method for the solution of the Schur Complement (SC) system. Our experiments show that the SC-PCG-QSC method in its sequential mode is very efficient compared to standard direct band solvers for the QSC equations. We have implemented the SC-PCG-QSC method on the iPSC/2 hypercube and present performance evaluation results for up to 32 processors configurations. We discuss a type of nearest neighbour communication scheme, in which the amount of data transfer per processor does not grow with the number of processors. The estimated efficiencies are at the order of 90%.
Dataflow computer development in Japan
Authors: Yuba Toshitsugu , Shimada Toshio , Yamaguchi Yoshinori , Hiraki Kei , Sakai Shuichi
Published: July 2004

This paper describes the research activity on dataflow computing in Japan focusing on dataflow computer development at the Electrotechnical Laboratory (ETL). First, the history of dataflow computer development in Japan is outlined. Some distinguished milestones in the history are mentioned in detail. Second, two types of dataflow computing systems developed at ETL, SIGMA-1 and EM-4, are described with their research goals. The fundamental characteristics of the both systems are given and some comparisons are made. Finally, future problems toward new generation computer systems to meet the challenge of Tera FLOPS machines are discussed.
Compiler techniques for data partitioning of sequentially iterated parallel loops
Authors: Hudak David E. , Abraham Santosh G.
Published: July 2004

This paper uses bottom-up, static program partitioning to minimize the execution time of parallel programs by reducing interprocessor communication. Program partitioning is applied to a parallel programming construct known as a sequentially iterated parallel loop. This paper develops and evaluates compiler techniques to automatically generate data partitions for sequentially iterated parallel loops that minimize interprocessor communication. These techniques could be included as a communication-reducing back end for existing parallelizing compilers.

A multiprocessor model is defined to analyze program execution factors that lead to interprocessor communication. A model for the sequentially iterated parallel loop is defined to quantify communication patterns within a program. A vector notation is chosen to quantify communication across a global data set. Communication parameters used in generating data partitions are found and used within equations which are shown to generate rectangular and hexagonal partition shapes that minimize interprocessor communication.

Experiments measuring the impact of communication on program performance and the improvements gained by using the automatically generated data partitions were conducted on a sixteen-processor Encore Multimax. The new method outperformed established data partitioning methods.
A hardware-based performance monitor for the Intel iPSC/2 hypercube
Authors: Malony Allen D. , Reed Daniel A.
Published: July 2004

The complexity of parallel computer systems makes
a priori
performance prediction difficult and experimental performance analysis crucial. A complete characterization of software and hardware dynamics, needed to understand the performance of high-performance parallel systems, requires execution time performance instrumentation. Although software recording of performance data suffices for low frequency events, capture of detailed, high-frequency performance data ultimately requires hardware support if the performance instrumentation is to remain efficient and unobtrusive.

This paper describes the design of HYPERMON, a hardware system to capture and record software performance traces generated on the Intel iPSC/2 hypercube. HYPERMON represents a compromise between fully-passive hardware monitoring and software event tracing; software generated events are extracted from each node, timestamped, and externally recorded by HYPERMON. Using an instrumented version of the iPSC/2 operating system and several application programs, we present a performance analysis of an operational HYPERMON prototype and assess the limitations of the current design. Based on these results, we suggest design modifications that should permit capture of event traces from the coming generation of high-performance distributed memory parallel systems.
Hierarchical algorithms and architectures for parallel scientific computing
Authors: Chan Tony F.
Published: July 2004

There has been a recent emergence of many interesting and highly efficient hierarchical (multilevel) algorithms (e.g. multigrid, domain decomposition, wavelets, multilevel preconditioning, the fast multipole algorithms, etc.) for solving numerical problems in scientific computing. These algorithms derive their efficiency from using a hierarchical approach to capture the sharing of global information which is inherent in the physical processes being modelled. In addition to being computationally efficient, these algorithms also possess relatively high degrees of parallelism. I therefore argue that the architectures of parallel computers (especially massively parallel ones) should be designed to support hierarchical communication and synchronization needs of these algorithms. Hierarchical architectures are also more universal because they go beyond supporting a particular class of algorithms to supporting the underlying physical processes being modelled. Finally, I propose that algorithm designers take a critical look at traditional kernel algorithms and re-examine their cost-effectiveness in a massively parallel computing environment.
Clustering task graphs for message passing architectures
Authors: Gerasoulis Apostolos , Venugopal Sesh , Yang Tao
Published: July 2004

Clustering is a mapping of the nodes of a task graph onto labeled clusters. We present a unified framework for clustering of directed acyclic graphs (DAGs). Several clustering algorithms from the literature are compared using this framework. For coarse grain DAGs two interesting properties are presented. For every nonlinear clustering there exists a linear clustering whose parallel time is less than the nonlinear one. Furthermore, the parallel time of any linear clustering is within a factor of two of the optimal. Two clustering algorithms are presented with near linear time complexity for coarse grain DAGs. The conclusion is that linear clustering is an efficient and accurate operation.
Cache design with path balancing table, skewing and indirect tags
Authors: Jokinen Tommi , Wang Chia-Jiu
Published: July 2004

A cache design aimed to reduce cycle time, area, and miss rate simultaneously is proposed in this paper. A cache with path balancing table, skewing, and indirect tags can reduce cycle time, use less area, and reduce miss rate at the same time as compared with a baseline cache. From our simulation results, we propose cache design alternatives in achieving lower cycle time, lower miss rate, and using less area.
The SimpleScalar tool set, version 2.0
Authors: Burger Doug , Austin Todd M.
Published: July 2004

This document describes release 2.0 of the SimpleScalar tool set, a suite of free, publicly available simulation tools that offer both detailed and high-performance simulation of modern microprocessors. The new release offers more tools and capabilities, precompiled binaries, cleaner interfaces, better documentation, easier installation, improved portability, and higher performance. This paper contains a complete description of the tool set, including retrieval and installation instructions, a description of how to use the tools, a description of the target SimpleScalar architecture, and many details about the internals of the tools and how to customize them. With this guide, the tool set can be brought up and generating results in under an hour (on supported platforms).
Improving applications performance
Authors: Jutla D. N. , Bodorik P.
Published: July 2004

This paper presents a memory model and architecture for synchronization of threads or tasks when accessing regions of virtual memory. Access control is defined on a memory region through a view that defines the size of access units and also the protocol in terms of a Finite State Machine (FSM). The size of access units, although fixed within a view, can vary across views and is thus customizable to applications. Variable-sized access units are obtained without altering the underlying fixed sized paging implementation. By defining access control through FSM definitions, any protocol that is decomposable into a set of states and can be expressed using an FSM can be supported.A cache-based architecture of the Protection Control Unit (PCU), which decides whether a read/write memory access to an access unit of a region/view can proceed or leads to a fault, is presented. The PCU is not invoked on each read/write memory access, but only on data cache misses and write access faults. The cache-based architecture forms flexible hardware support for access control in that by loading the caches with definitions of different FSM, different protocols can be supported. Furthermore, by providing for hardware supported changes in state of access through state transitions, frequency of context switching is reduced.Trace-driven simulation is used to examine the delay in the memory hierarchy due to inclusion of the caches in the PCU unit, and to examine delay in the memory hierarchy for a conventional software implementation of the same access control protocol. A TPC-C benchmark application under different transaction loads was traced and the results show that it is the number of TLB accesses (approximately 15 times more as compared to PCU accesses) for the modeled application that incurs the dominant delay, as compared to delay in the PCU memory hierarchy.
An innovative implementation for directory-based cache coherence in shared memory multiprocessors
Authors: Shi Weisong , Hu Weiwu , Zhu Ming
Published: July 2004

Directory-based cache coherence protocol is accepted as the common technique in large scale shared memory multiprocessors because of its scalability. Although it was extensively studied in the past, however, the memory overhead and long miss penalty entailed by this protocol are the major obstacles to scale for large scale multiprocessors. On the other hand, the ever-increasing cache line size makes the false sharing problem more serious than before, which will lead to high miss rate. Based on the scope consistency, we propose a lock-specific home-based cache coherence protocol. In this new cache coherence protocol, all directory memory overhead are eleminated completely and false sharing problem and high miss rate will be sloved greatly at the cost of small write notice buffer in each processor.
Techniques for fast simulation of associative cache directories
Authors: Moudgill Mayan
Published: July 2004

We describe a technique for simulating associative cache directories that considerably reduces simulation time with respect to a sequential search of the tag array. We also describe techniques for maintaining LRU information that use considerably less memory than time-stamps. The combination of these techniques makes possible the simulation of set-associative cache directories at a much higher speed than other techniques.
Performance characterization of a Quad Pentium Pro SMP using OLTP workloads
Authors: Keeton Kimberly , Patterson David A. , He Yong Qiang , Raphael Roger C. , Baker Walter E.
Published: July 2004

Commercial applications are an important, yet often overlooked, workload with significantly different characteristics from technical workloads. The potential impact of these differences is that computers optimized for technical workloads may not provide good performance for commercial applications, and these applications may not fully exploit advances in processor design. To evaluate these issues, we use hardware counters to measure architectural features of a four-processor Pentium Pro-based server running a TPC-C-like workload on an Informix database. We examine the effectiveness of out-of-order execution, branch prediction, speculative execution, superscalar issue and retire, caching and multiprocessor scaling. We find that out-of-order execution, superscalar issue and retire, and branch prediction are not as effective for database workloads as they are for technical workloads, such as SPEC. We find that caches are effective at reducing processor traffic to memory; even larger caches would be helpful to satisfy more data requests. Multiprocessor scaling of this workload is good, but even modest bus utilization degrades application memory latency, limiting database throughput.
Execution characteristics of desktop applications on Windows NT
Authors: Lee Dennis C. , Crowley Patrick J. , Baer Jean-Loup , Anderson Thomas E. , Bershad Brian N.
Published: July 2004

This paper examines the performance of desktop applications running on the Microsoft Windows NT operating system on Intel x86 processors, and contrasts these applications to the programs in the integer SPEC95 benchmark suite. We present measurements of basic instruction set and program characteristics, and detailed simulation results of the way these programs use the memory system and processor branch architecture. We show that the desktop applications have similar characteristics to the integer SPEC95 benchmarks for many of these metrics. However, compared to the integer SPEC95 applications, desktop applications have larger instruction working sets, execute instructions in a greater number of unique functions, cross DLL boundaries frequently, and execute a greater number of indirect calls.
An analysis of database workload performance on simultaneous multithreaded processors
Authors: Lo Jack L. , Barroso Luiz André , Eggers Susan J. , Gharachorloo Kourosh , Levy Henry M. , Parekh Sujay S.
Published: July 2004

Simultaneous multithreading (SMT) is an architectural technique in which the processor issues multiple instructions from multiple threads each cycle. While SMT has been shown to be effective on scientific workloads, its performance on database systems is still an open question. In particular, database systems have poor cache performance, and the addition of multithreading has the potential to exacerbate cache conflicts.This paper examines database performance on SMT processors using traces of the Oracle database management system. Our research makes three contributions. First, it characterizes the memory-system behavior of database systems running on-line transaction processing and decision support system workloads. Our data show that while DBMS workloads have large memory footprints, there is substantial data reuse in a small, cacheable "critical" working set. Second, we show that the additional data cache conflicts caused by simultaneous multithreaded instruction scheduling can be nearly eliminated by the proper choice of software-directed policies for virtual-to-physical page mapping and per-process address offsetting. Our results demonstrate that with the best policy choices, D-cache miss rates on an 8-context SMT are roughly equivalent to those on a single-threaded superscalar. Multithreading also leads to better interthread instruction cache sharing, reducing I-cache miss rates by up to 35%. Third, we show that SMT's latency tolerance is highly effective for database applications. For example, using a memory-intensive OLTP workload, an 8-context SMT processor achieves a 3-fold increase in instruction throughput over a single-threaded superscalar with similar resources.
Multi-level texture caching for 3D graphics hardware
Authors: Cox Michael , Bhandari Narendra , Shantz Michael
Published: July 2004

Traditional graphics hardware architectures implement what we call the
push architecture
for texture mapping. Local memory is dedicated to the accelerator for fast local retrieval of texture during rasterization, and the application is responsible for managing this memory. The push architecture has a bandwidth advantage, but disadvantages of limited texture capacity, escalation of accelerator memory requirements (and therefore cost), and poor memory utilization. The push architecture also requires the programmer to solve the bin- packing problem of managing accelerator memory each frame. More recently graphics hardware on PC-class machines has moved to an implementation of what we call the
pull architecture.
Texture is stored in system memory and downloaded by the accelerator as needed. The pull architecture has advantages of texture capacity, stems the escalation of accelerator memory requirements, and has good memory utilization. It also frees the programmer from accelerator texture memory management. However, the pull architecture suffers escalating requirements for bandwidth from main memory to the accelerator. In this paper we propose multi-level texture caching to provide the accelerator with the bandwidth advantages of the push architecture combined with the capacity advantages of the pull architecture. We have studied the feasibility of 2-level caching and found the following: (1) significant re-use of texture between frames; (2) L2 caching requires significantly less memory than the push architecture; (3) L2 caching requires significantly less bandwidth from host memory than the pull architecture; (4) L2 caching enables implementation of smaller L1 caches that would otherwise bandwidth-limit accelerators on the workloads in this paper. Results suggest that an L2 cache achieves the original advantage of the pull architecture --- stemming the growth of local texture memory --- while at the same time stemming the current explosion in demand for texture bandwidth between host memory and the accelerator.
Dynamic history-length fitting
Authors: Juan Toni , Sanjeevan Sanji , Navarro Juan J.
Published: July 2004

Accurate branch prediction is essential for obtaining high performance in pipelined superscalar processors that execute instructions speculatively. Some of the best current predictors combine a part of the branch address with a fixed amount of global history of branch outcomes in order to make a prediction. These predictors cannot perform uniformly well across all workloads because the best amount of history to be used depends on the code, the input data and the frequency of context switches. Consequently, all predictors that use a fixed history length are therefore unable to perform up to their maximum potential.We introduce a method---called DHLF---that dynamically determines the optimum history length during execution, adapting to the specific requirements of any code, input data and system workload. Our proposal adds an extra level of adaptivity to two-level adaptive branch predictors. The DHLF method can be applied to any one of the predictors that combine global branch history with the branch address. We apply the DHLF method to gshare (
dhlf-gshare
) and obtain near-optimal results for all
SPECint95
benchmarks, with and without context switches. Some results are also presented for gskewed (
dhlf-gskewed
), confirming that other predictors can benefit from our proposal.
Using prediction to accelerate coherence protocols
Authors: Mukherjee Shubhendu S. , Hill Mark D.
Published: July 2004

Most large shared-memory multiprocessors use directory protocols to keep per-processor caches coherent. Some memory references in such systems, however, suffer long latencies for misses to remotely-cached blocks. To ameliorate this latency, researchers have augmented standard coherence protocols with optimizations for specific sharing patterns, such as read-modify-write, producer-consumer, and migratory sharing. This paper seeks to replace these directed solutions with general prediction logic that monitors coherence activity and triggers appropriate coherence actions.This paper takes the first step toward using general prediction to accelerate coherence protocols by developing and evaluating the Cosmos coherence message predictor. Cosmos predicts the source and type of the next coherence message for a cache block using logic that is an extension of Yeh and Patt's two-level PAp branch predictor. For five scientific applications running on 16 processors, Cosmos has prediction accuracies of 62% to 93%. Cosmos' high prediction accuracy is a result of predictable coherence message signatures that arise from stable sharing patterns of cache blocks.
Selective eager execution on the PolyPath architecture
Authors: Klauser Artur , Paithankar Abhijit , Grunwald Dirk
Published: July 2004

Control-flow misprediction penalties are a major impediment to high performance in wide-issue superscalar processors. In this paper we present
Selective Eager Execution
(SEE), an execution model to overcome mis-speculation penalties by executing both paths after diffident branches. We present the micro-architecture of the
PolyPath
processor, which is an extension of an aggressive superscalar, out-of-order architecture. The PolyPath architecture uses a novel instruction tagging and register renaming mechanism to execute instructions from multiple paths simultaneously in the same processor pipeline, while retaining maximum resource availability for single-path code sequences.Results of our execution-driven, pipeline-level simulations show that SEE can improve performance by as much as 36% for the go benchmark, and an average of 14% on SPECint95, when compared to a normal superscalar, out-of-order, speculative execution, monopath processor. Moreover, our architectural model is both elegant and practical to implement, using a small amount of additional state and control logic.
Effects of architectural and technological advances on the HP/Convex Exemplar's memory and communication performance
Authors: Abandah Gheith A. , Davidson Edward S.
Published: July 2004

Advances in microarchitecture, packaging, and manufacturing processes enable designers to build new systems with higher performance and scalability. Using microbenchmark techniques, we contrast the memory and communication performance of two generations of the HP/Convex Exemplar scalable parallel processing system. The SPP1000 and SPP2000 have significant architectural and implementation differences, but maintain upward binary compatibility. The SPP2000 employs manufacturing and packaging advances to obtain shorter system interconnects with wider data paths and improved functionality, thereby reducing the latency and increasing the bandwidth of remote communication. Although the memory latency is not significantly improved, newer out-of-order execution processors coupled with nonblocking caches achieve much higher memory bandwidth. The SPP2000 has a richer system interconnect topology that allows scalability to a larger number of processors. The SPP2000 also employs innovations in its coherence protocols to improve synchronization and communication performance. This paper characterizes the performance effects of these changes, and identifies some remaining inefficiencies, in the cache coherence protocol and the node configuration, that future systems should address.
Design choices in the SHRIMP system
Authors: Blumrich Matthias A. , Alpert Richard D. , Chen Yuqun , Clark Douglas W. , Damianakis Stefanos N. , Dubnicki Cezary , Felten Edward W. , Iftode Liviu , Li Kai , Martonosi Margaret , Shillner Robert A.
Published: July 2004

The SHRIMP cluster-computing system has progressed to a point of relative maturity; a variety of applications are running on a 16-node system. We have enough experience to understand what we did right and wrong in designing and building the system. In this paper we discuss some of the lessons we learned about computer architecture, and about the challenges involved in building a significant working system in an academic research environment. We evaluate significant design choices by modifying the network interface firmware and the system software in order to empirically compare our design to other approaches.
Selective value prediction
Authors: Calder Brad , Reinman Glenn , Tullsen Dean M.
Published: July 2004

Value Prediction is a relatively new technique to increase instruction-level parallelism by breaking true data dependence chains. A value prediction architecture
produces
values, which may be later
consumed
by instructions that execute speculatively using the predicted value.This paper examines selective techniques for using value prediction in the presence of predictor capacity constraints and reasonable misprediction penalties. We examine prediction and confidence mechanisms in light of these constraints, and we minimize capacity conflicts through instruction filtering. The latter technique filters which instructions put values into the value prediction table. We examine filtering techniques based on instruction type, as well as giving priority to instructions belonging to the longest data dependence path in the processor's active instruction window. We apply filtering both to the producers of predicted values and the consumers. In addition, we examine the benefit of using different confidence levels for instructions using predicted values on the longest dependence path.
Tolerating late memory traps in ILP processors
Authors: Qiu Xiaogang , Dubois Michel
Published: July 2004

ILP processors can execute a large number of instructions at the same time. Thus it becomes more and more difficult to support traps efficiently. On the other hand a current trend in architecture is to support various memory functions in software rather than hardware, usually by trapping the execution processor on a cache miss, TLB miss or a failed access to a local or remote memory. These late memory traps block the faulting instruction at the top of the active list, backing up the pipeline. Moreover the support for late memory traps may affect the performance of non-faulting memory instructions as well.In this paper we analyze the overhead caused by late memory traps in ILP processors and define several measures for this overhead. In order to tolerate late memory traps, we propose hardware prefetching of exception conditions and a tagged Store buffer to implement deferred traps on Stores. We show that, with these hardware optimizations, the overhead added by the lateness of traps is significantly reduced relative to the overhead of early traps. Because of caching effects the frequency of late memory traps usually decreases as they are taken deeper in the memory hierarchy and their overall impact on the execution time becomes negligible.
Commit-reconcile & fences (CRF)
Authors: Shen Xiaowei , Arvind  , Rudolph Larry
Published: July 2004

We present a new mechanism-oriented memory model called Commit-Reconcile & Fences (CRF) and define it using algebraic rules. Many existing memory models can be described as restricted versions of CRF. The model has been designed so that it is both easy for architects to implement, and stable enough to serve as a target machine interface for compilers of high-level languages. The CRF model exposes a semantic notion of caches (saches), and decomposes load and store instructions into finer-grain operations. We sketch how to integrate CRF into modern microprocessors and outline an adaptive coherence protocol to implement CRF in distributed shared-memory systems. CRF offers an upward compatible way to design next generation computer systems.
A performance comparison of contemporary DRAM architectures
Authors: Cuppu Vinodh , Jacob Bruce , Davis Brian , Mudge Trevor
Published: July 2004

In response to the growing gap between memory access time and processor speed, DRAM manufacturers have created several new DRAM architectures. This paper presents a simulation-based performance study of a representative group, each evaluated in a small system organization. These small-system organizations correspond to workstation-class computers and use on the order of 10 DRAM chips. The study covers Fast Page Mode, Extended Data Out, Synchronous, Enhanced Synchronous, Synchronous Link, Rambus, and Direct Rambus designs. Our simulations reveal several things: (a) current advanced DRAM technologies are attacking the memory bandwidth problem but not the latency problem; (b) bus transmission speed will soon become a primary factor limiting memory-system performance; (c) the post-L2 address stream still contains significant locality, though it varies from application to application; and (d) as we move to wider buses, row access time becomes more prominent, making it important to investigate techniques to exploit the available locality to decrease access time.
Using network interface support to avoid asynchronous protocol processing in shared virtual memory systems
Authors: Bilas Angelos , Liao Cheng , Singh Jaswinder Pal
Published: July 2004

The performance of page-based software shared virtual memory (SVM) is still far from that achieved on hardware-coherent distributed shared memory (DSM) systems. The interrupt cost for asynchronous protocol processing has been found to be a key source of performance loss and complexity.This paper shows that by providing simple and general support for asynchronous message handling in a commodity network interface (NI), and by altering SVM protocols appropriately, protocol activity can be decoupled from asynchronous message handling and the need for interrupts or polling can be eliminated. The NI mechanisms needed are generic, not SVM-dependent. They also require neither visibility into the node memory system nor code instrumentation to identify memory operations. We prototype the mechanisms and such a
synchronous home-based LRC
protocol, called GeNIMA (GEneral-purpose Network Interface support in a shared Memory Abstraction), on a cluster of SMPs with a programmable NI, though the mechanisms are simple and do not require programmability.We find that the performance improvements are substantial, bringing performance on a small-scale SMP cluster much closer to that of hardware-coherent shared memory for many applications, and we show the value of each of the mechanisms in different applications. Application performance improves by about 37% on average for reasonably well performing applications, even on our relatively slow programmable NI, and more for others. We discuss the key remaining bottlenecks at the protocol level and use a firmware performance monitor in the NI to understand the interactions with and the implications for the communication layer.
Scaling application performance on a cache-coherent multiprocessor
Authors: Jiang Dongming , Singh Jaswinder Pal
Published: July 2004

Hardware-coherent, distributed shared address space systems are increasingly successful at moderate scale. However, it is unclear whether, or with how much difficulty, the performance of a load-store shared address space programming model scales to large processor counts on real applications. We examine this question using an aggressive case-study machine, the SGI Origin2000, up to 128 processors. We show for the first time that scalable performance can indeed be achieved in this programming model on a wide range of applications, including challenging kernels like FFT. However, this does not come easily, even for applications considered to be already highly optimized, and is very often not simply a matter of increasing problem size. Rather, substantial further application restructuring is often needed, which is usually quite algorithmic in nature. We examine how the restructurings compare with those needed for performance portability to shared virtual memory on clusters, and we comment on common programming guidelines for performance portability and scalability as well as on how the programming difficulty compares with that of explicit message passing. We also examine where applications spend their time on this large machine, the impact of special hardware features that the machine provides, and the impact of mapping to the network topology.
A new approach to fast control of
r
2
×
r
2
3-stage benes networks of
r
×
r
crossbar switches
Authors: Youssef Abdou , Arden Bruce
Published: July 2004

The routing control of Benes networks has proven to be costly. This paper introduces a new approach to fast control of
N
×
N
3-stage Benes networks of
r
×
r
crossbar switches as building blocks, where
N
=
r
2
and
r
≥ 2. The new approach consists of setting the leftmost column of switches to an appropriately chosen configuration so that the network becomes self-routed while still able to realize a given family of permutations. This approach requires that, for any given family of permutations, a configuration for the leftmost column be found. Such a family is called compatible and the configuration of the leftmost column is called the compatibility factor. In this paper, compatibility is characterized and a technique to determine compatibility and the compatibility factor is developed. The technique is used to show the compatibility and find the compatibility factor of Ω-realizable permutations, the permutations needed to emulate a hypercube, and the families of permutations required by FFT, bitonic sorting, tree computations, multidimensional mesh and torus computations, and multigrid computations. An O(log
2
N
) time routing algorithm for the 3-stage Benes will also be developed. Finally, as only 3 compatibility factors are required by the above families of permutations, it will be proposed to replace the first column by 3 multiplexed connections yielding a self-routing network with strong communication capabilities.