bluuebunny/crossref_metadata_2025 huggingface dataset:
Energy-effective issue logic
Authors: Folegnani Daniele , González Antonio
Published: July 2004

The issue logic of a dynamically-scheduled superscalar processor is a complex mechanism devoted to start the execution of multiple instructions every cycle. Due to its complexity, it is responsible for a significant percentage of the energy consumed by a microprocessor. The energy consumption of the issue logic depends on several architectural parameters, the instruction issue queue size being one of the most important. In this paper we present a technique to reduce the energy consumption of the issue logic of a high-performance superscalar processor. The proposed technique is based on the observation that the conventional issue logic wastes a significant amount of energy for useless activity. In particular, the wake-up of empty entries and operands that are ready represents an important source of energy waste. Besides, we propose a mechanism to dynamically reduce the effective size of the instruction queue. We show that on average the effective instruction queue size can be reduced by a factor of 26% with minimal impact on performance. This reduction together with the energy saved for empty and ready entries result in about 90.7% reduction in the energy consumed by the wake-up logic, which represents 14.9% of the total energy of the assumed processor.
Cache decay
Authors: Kaxiras Stefanos , Hu Zhigang , Martonosi Margaret
Published: July 2004

Power dissipation is increasingly important in CPUs ranging from those intended for mobile use, all the way up to high-performance processors for high-end servers. While the bulk of the power dissipated is dynamic switching power, leakage power is also beginning to be a concern. Chipmakers expect that in future chip generations, leakage's proportion of total chip power will increase significantly.

This paper examines methods for reducing leakage power within the cache memories of the CPU. Because caches comprise much of a CPU chip's area and transistor counts, they are reasonable targets for attacking leakage. We discuss policies and implementations for reducing cache leakage by invalidating and “turning off” cache lines when they hold data not likely to be reused. In particular, our approach is targeted at the generational nature of cache line usage. That is, cache lines typically have a flurry of frequent use when first brought into the cache, and then have a period of “dead time” before they are evicted. By devising effective, low-power ways of deducing dead time, our results show that in many cases we can reduce LI cache leakage energy by 4x in SPEC2000 applications without impacting performance. Because our
decay-based

techniques have notions of competitive on-line algorithms at their roots, their energy usage can be theoretically bounded at within a factor of two of the optimal oracle-based policy. We also examine
adaptive
decay-based policies that make energy-minimizing policy choices on a per-application basis by choosing appropriate decay intervals individually for each cache line. Our proposed adaptive policies effectively reduce LI cache leakage energy by 5x for the SPEC2000 with only negligible degradations in performance

.
Variability in the execution of multimedia applications and implications for architecture
Authors: Hughes Christopher J. , Kaul Praful , Adve Sarita V. , Jain Rohit , Park Chanik , Srinivasan Jayanth
Published: July 2004

Multimedia applications are an increasingly important workload for general-purpose processors. This paper analyzes frame-level execution time variability for several multimedia applications on general-purpose architectures. There are two reasons for such an analysis. First, it has been conjectured that complex features of such architectures (e.g., out-of-order issue) result in unpredictable execution times, making them unsuitable for meeting real-time requirements of multimedia applications. Our analysis tests this conjecture. Second, such an analysis can be used to effectively employ recently proposed adaptive architectures.

We find that while execution time varies from frame to frame for many multimedia applications, the variability is mostly caused by the application algorithm and the media input. Aggressive architectural features induce little additional variability (and unpredictability) in execution time, in contrast to conventional wisdom.

The presence of frame-level execution time variability motivates frame-level architectural adaptation (e.g., to save energy). Additionally, our results show that execution time generally varies slowly, implying it is possible to dynamically predict the behavior of future frames on a variety of hardware configurations for effective adaptation.
Rapid profiling via stratified sampling
Authors: Sastry S. Subramanya , Bodík Rastislav , Smith James E.
Published: July 2004

Sophisticated binary translators and dynamic optimizers demand a program profiler with low overhead, high accuracy, and the ability to collect a variety of profile types. A profiling scheme that achieves these goals is proposed. Conceptually, the hardware compresses a stream of profile data by counting identical events; the compressed profile dam is passed to software for analysis. Compressing the high-bandwidth event stream greatly reduces software overhead. Because optimizations can tolerate some profiling errors, we allow the stream compressor to be lossy, thereby enabling a low-cost sampling-based hardware design. Because the hardware compressor is insensitive to the event content, it supports various profile types and can process multiple types simultaneously.

Basic components of our framework are periodic and random samplers, counters, and hash functions. These components are composed to form a variety of stream compressors. One design is both simple and very effective: the input stream is hash-split into multiple substreams, each of which is fed into a simple periodic sampler that selects every kth event. This stratified periodic sampler performs better than conventional random sampling because it biases each substream towards a small number of unique events, thereby reducing sampling error, and allowing faster convergence to an accurate profile. For example, convergence to a given level of accuracy is about twice as fast for gcc. When sampling overhead is considered, the stratified periodic profiler achieves less than 3% error while incurring an overhead of only 3.5% for gcc.
Improving superscalar instruction dispatch and issue by exploiting dynamic code sequences
Authors: Vajapeyam Sriram , Mitra Tulika
Published: July 2004

Superscalar processors currently have the potential to fetch multiple basic blocks per cycle by employing one of several recently proposed instruction fetch mechanisms. However, this increased fetch bandwidth cannot be exploited unless pipeline stages further downstream correspondingly improve. In particular, register renaming a large number of instructions per cycle is difficult. A large instruction window, needed to receive multiple basic blocks per cycle, will slow down dependence resolution and instruction issue. This paper addresses these and related issues by proposing (i) partitioning of the instruction window into multiple blocks, each holding a dynamic code sequence; (ii) logical partitioning of the register file into a global file and several local files, the latter holding registers local to a dynamic code sequence; (iii) the dynamic recording and reuse of register renaming information for registers local to a dynamic code sequence. Performance studies show these mechanisms improve performance over traditional superscalar processors by factors ranging from 1.5 to a little over 3 for the SPEC Integer programs. Next, it is observed that several of the loops in the benchmarks display vector-like behavior during execution, even if the static loop bodies are likely complex for compile-time vectorization. A dynamic loop vectorization mechanism that builds on top of the above mechanisms is briefly outlined. The mechanism vectorizes up to 60% of the dynamic instructions for some programs, albeit the average number of iterations per loop is quite small.
On deadlocks in interconnection networks
Authors: Pinkston Timothy Mark , Warnakulasuriya Sugath
Published: July 2004

Deadlock avoidance-based and deadlock recovery-based routing algorithms have been proposed in recent years without full understanding of the likelihood and characteristics of actual deadlocks in interconnection networks. This work models the interrelationships between routing freedom, message blocking, correlated resource dependencies and deadlock formation. We empirically show that increasing routing freedom, as achieved by allowing unrestricted routing over multiple virtual channels, makes deadlocks highly improbable and reduces the likelihood of other types of correlated message blocking behavior that can degrade performance. Our results further substantiate that recovery-based routing algorithms have a higher potential performance advantage over deadlock avoidance-based routing algorithms which, inherently, allow less routing freedom.
Tolerating multiple failures in RAID architectures with optimal storage and uniform declustering
Authors: Alvarez Guillermo A. , Burkhard Walter A. , Cristian Flaviu
Published: July 2004

We present D
ATUM
, a novel method for tolerating multiple disk failures in disk arrays. D
ATUM
is the first known method that can mask any given number of failures, requires an optimal amount of redundant storage space, and spreads reconstruction accesses uniformly over disks in the presence of failures without needing large layout tables in controller memory. Our approach is based on information dispersal, a coding technique that admits an efficient hardware implementation. As the method does not restrict the configuration parameters of the disk array, many existing RAID organizations are particular cases of D
ATUM
. A detailed performance comparison with two other approaches shows that D
ATUM'S
response times are similar to those of the best competitor when two or less disks fail, and that the performance degrades gracefully when more than two disks fail.
Hardware fault containment in scalable shared-memory multiprocessors
Authors: Teodosiu Dan , Baxter Joel , Govil Kinshuk , Chapin John , Rosenblum Mendel , Horowitz Mark
Published: July 2004

Current shared-memory multiprocessors are inherently vulnerable to faults: any significant hardware or system software fault causes the entire system to fail. Unless provisions are made to limit the impact of faults, users will perceive a decrease in reliability when they entrust their applications to larger machines. This paper shows that fault containment techniques can be effectively applied to scalable shared-memory multiprocessors to reduce the reliability problems created by increased machine size.The primary goal of our approach is to leave normal-mode performance unaffected. Rather than using expensive fault-tolerance techniques to mask the effects of data and resource loss, our strategy is based on limiting the damage caused by faults to only a portion of the machine. After a hardware fault, we run a distributed recovery algorithm that allows normal operation to be resumed in the functioning parts of the machine.Our approach is implemented in the Stanford FLASH multiprocessor. Using a detailed hardware simulator, we have performed a number of fault injection experiments on a FLASH system running Hive, an operating system designed to support fault containment. The results we report validate our approach and show that in conjunction with an operating system like Hive, we can improve the reliability seen by unmodified applications without substantial performance cost. Simulation results suggest that our algorithms scale well for systems up to 128 processors.
The Mercury Interconnect Architecture
Authors: Weber Wolf-Dietrich , Gold Stephen , Helland Pat , Shimizu Takeshi , Wicki Thomas , Wilcke Winfried
Published: July 2004

This paper presents HAL's Mercury Interconnect Architecture, an interconnect infrastructure designed to link commodity microprocessors, memory, and I/O components into high-performance multiprocessing servers. Both shared-memory and message-passing systems, as well as hybrid systems are supported by the interconnect. The key attributes of the Mercury Interconnect Architecture are: low latency, high bandwidth, a modular and flexible design, reliability/availability/serviceability (RAS) features, and a simplicity that enables very cost-effective implementations. The first implementation of the architecture links multiple 4-processor Pentium™ Pro based nodes. In a 4-node (16-processor) shared-memory configuration, this system achieves a remote read latency of just over 1 µs, and a maximum interconnect bandwidth of 6.4 GByte/s. Both of these parameters far outpace comparable SCI-based solutions, while utilizing much fewer hardware components.
Memory-system design considerations for dynamically-scheduled processors
Authors: Farkas Keith I. , Chow Paul , Jouppi Norman P. , Vranesic Zvonko
Published: July 2004

In this paper, we identify performance trends and design relationships between the following components of the data memory hierarchy in a dynamically-scheduled processor: the register file, the lockup-free data cache, the stream buffers, and the interface between these components and the lower levels of the memory hierarchy. Similar performance was obtained from all systems having support for fewer than four in-flight misses, irrespective of the register-file size, the issue width of the processor, and the memory bandwidth. While providing support for more than four in-flight misses did increase system performance, the improvement was less than that obtained by increasing the number of registers. The addition of stream buffers to the investigated systems led to a significant performance increase, with the larger increases for systems having less in-flight-miss support, greater memory bandwidth, or more instruction issue capability. The performance of these systems was not significantly affected by the inclusion of traffic filters, dynamic-stride calculators, or the inclusion of the per-load non-unity stride-predictor and the incremental-prefetching techniques, which we introduce. However, the incremental prefetching technique reduces the bandwidth consumed by stream buffers by 50% without a significant impact on performance.
VM-based shared memory on low-latency, remote-memory-access networks
Authors: Kontothanassis Leonidas , Hunt Galen , Stets Robert , Hardavellas Nikolaos , Cierniak Michał , Parthasarathy Srinivasan , Meira Wagner , Dwarkadas Sandhya , Scott Michael
Published: July 2004

Recent technological advances have produced network interfaces that provide users with very low-latency access to the memory of remote machines. We examine the impact of such networks on the implementation and performance of software DSM. Specifically, we compare two DSM systems---Cashmere and TreadMarks---on a 32-processor DEC Alpha cluster connected by a Memory Channel network.Both Cashmere and TreadMarks use virtual memory to maintain coherence on pages, and both use lazy, multi-writer release consistency. The systems differ dramatically, however, in the mechanisms used to track sharing information and to collect and merge concurrent updates to a page, with the result that Cashmere communicates much more frequently, and at a much finer grain.Our principal conclusion is that low-latency networks make DSM based on fine-grain communication competitive with more coarse-grain approaches, but that further hardware improvements will be needed before such systems can provide consistently superior performance. In our experiments, Cashmere scales slightly better than TreadMarks for applications with false sharing. At the same time, it is severely constrained by limitations of the current Memory Channel hardware. In general, performance is better for TreadMarks.
Efficient synchronization
Authors: Kägi Alain , Burger Doug , Goodman James R.
Published: July 2004

Efficient synchronization primitives are essential for achieving high performance in fine-grain, shared-memory parallel programs. One function of synchronization primitives is to enable exclusive access to shared data and critical sections of code. This paper makes three contributions. (1) We enumerate the five sources of overhead that locking synchronization primitives can incur. (2) We describe four mechanisms (local spinning, queue-based locking, collocation, and synchronized prefetch) that reduce these synchronization overheads. (3) With detailed simulations, we show the extent to which these four mechanisms can improve the performance of shared-memory programs. We evaluate the space of these mechanisms using seventeen synchronization constructs, which are formed from six base typed of locks (T
EST
&S
ET
, T
EST
&T
EST
&S
ET
, MCS, LH, M, and Q
OLB
). We show that large performance gains (speedups of more than 1.5 for three of five benchmarks) can be achieved if at least three optimizing mechanisms are used simultaneously. We find that Q
OLB
, which incorporates all four mechanisms, outperforms all other primitives (including reactive synchronization) in all cases. Finally, we demonstrate the superior performance of a low-cost implementation of Q
OLB
, which runs on an unmodified cluster of commodity workstations.
Dynamic speculation and synchronization of data dependences
Authors: Moshovos Andreas , Breach Scott E. , Vijaykumar T. N. , Sohi Gurindar S.
Published: July 2004

Data dependence speculation is used in instruction-level parallel (ILP) processors to allow early execution of an instruction before a logically preceding instruction on which it may be data dependent. If the instruction is independent, data dependence speculation succeeds; if not, it fails, and the two instructions must be synchronized. The modern dynamically scheduled processors that use data dependence speculation do so blindly (i.e., every load instruction with unresolved dependences is speculated). In this paper, we demonstrate that as dynamic instruction windows get larger, significant performance benefits can result when intelligent decisions about data dependence speculation are made. We propose dynamic data dependence speculation techniques: (i) to predict if the execution of an instruction is likely to result in a data dependence mis-specalation, and (ii) to provide the synchronization needed to avoid a mis-speculation. Experimental results evaluating the effectiveness of the proposed techniques are presented within the context of a Multiscalar processor.
Dynamic instruction reuse
Authors: Sodani Avinash , Sohi Gurindar S.
Published: July 2004

This paper introduces the concept of dynamic instruction reuse. Empirical observations suggest that many instructions, and groups of instructions, having the same inputs, are executed dynamically. Such instructions do not have to be executed repeatedly --- their results can be obtained from a buffer where they were saved previously. This paper presents three hardware schemes for exploiting the phenomenon of dynamic instruction reuse, and evaluates their effectiveness using execution-driven simulation. We find that in some cases over 50% of the instructions can be reused. The speedups so obtained, though less striking than the percentage of instructions reused, are still quite significant.
The SGI Origin
Authors: Laudon James , Lenoski Daniel
Published: July 2004

The SGI Origin 2000 is a cache-coherent non-uniform memory access (ccNUMA) multiprocessor designed and manufactured by Silicon Graphics, Inc. The Origin system was designed from the ground up as a multiprocessor capable of scaling to both small and large processor counts without any bandwidth, latency, or cost cliffs. The Origin system consists of up to 512 nodes interconnected by a scalable Craylink network. Each node consists of one or two R10000 processors, up to 4 GB of coherent memory, and a connection to a portion of the XIO IO subsystem. This paper discusses the motivation for building the Origin 2000 and then describes its architecture and implementation. In addition, performance results are presented for the NAS Parallel Benchmarks V2.2 and the SPLASH2 applications. Finally, the Origin system is compared to other contemporary commercial ccNUMA systems.
Target prediction for indirect jumps
Authors: Chang Po-Yung , Hao Eric , Patt Yale N.
Published: July 2004

As the issue rate and pipeline depth of high performance superscalar processors increase, the amount of speculative work issued also increases. Because speculative work must be thrown away in the event of a branch misprediction, wide-issue, deeply pipelined processors must employ accurate branch predictors to effectively exploit their performance potential. Many existing branch prediction schemes are capable of accurately predicting the direction of conditional branches. However, these schemes are ineffective in predicting the targets of indirect jumps achieving, on average, a prediction accuracy rate of 51.8% for the SPECint95 benchmarks. In this paper, we propose a new prediction mechanism, the target cache, for predicting indirect jump targets. For the perl and gcc benchmarks, this mechanism reduces the indirect jump misprediction rate by 93.4% and 63.35% and the overall execution time by 14% and 5%.
The agree predictor
Authors: Sprangle Eric , Chappell Robert S. , Alsup Mitch , Patt Yale N.
Published: July 2004

Deeply pipelined, superscalar processors require accurate branch prediction to achieve high performance. Two-level branch predictors have been shown to achieve high prediction accuracy. It has also been shown that branch interference is a major contributor to the number of branches mispredicted by two-level predictors.This paper presents a new method to reduce the interference problem called agree prediction, which reduces the chance that two branches aliasing the same PHT entry will interfere negatively. We evaluate the performance of this scheme using full traces (both user and supervisor) of the SPECint95 benchmarks. The result is a reduction in the misprediction rate of gcc ranging from 8.62% with a 64K-entry PHT up to 33.3% with a 1K-entry PHT.
Trading conflict and capacity aliasing in conditional branch predictors
Authors: Michaud Pierre , Seznec André , Uhlig Richard
Published: July 2004

As modern microprocessors employ deeper pipelines and issue multiple instructions per cycle, they are becoming increasingly dependent on accurate branch prediction. Because hardware resources for branch-predictor tables are invariably limited, it is not possible to hold all relevant branch history for all active branches at the same time, especially for large workloads consisting of multiple processes and operating-system code. The problem that results, commonly referred to as aliasing in the branch-predictor tables, is in many ways similar to the misses that occur in finite-sized hardware caches.In this paper we propose a new classification for branch aliasing based on the three-Cs model for caches, and show that conflict aliasing is a significant source of mispredictions. Unfortunately, the obvious method for removing conflicts --- adding tags and associativity to the predictor tables --- is not a cost-effective solution.To address this problem, we propose the skewed branch predictor, a multi-bank, tag-less branch predictor, designed specifically to reduce the impact of conflict aliasing. Through both analytical and simulation models, we show that the skewed branch predictor removes a substantial portion of conflict aliasing by introducing redundancy to the branch-predictor tables. Although this redundancy increases capacity aliasing compared to a standard one-bank structure of comparable size, our simulations show that the reduction in conflict aliasing overcomes this effect to yield a gain in prediction accuracy. Alternatively, we show that a skewed organization can achieve the same prediction accuracy as a standard one-bank organization but with half the storage requirements.
A language for describing predictors and its application to automatic synthesis
Authors: Emer Joel , Gloy Nikolas
Published: July 2004

As processor architectures have increased their reliance on speculative execution to improve performance, the importance of accurate prediction of what to execute speculatively has increased. Furthermore, the types of values predicted have expanded from the ubiquitous branch and call/return targets to the prediction of indirect jump targets, cache ways and data values. In general, the prediction process is one of identifying the current state of the system, and making a prediction for some as yet uncomputed value based on that state. Prediction accuracy is improved by learning what is a good prediction for that state using a feedback process at the time the predicted value is actually computed. While there have been a number of efforts to formally characterize this process, we have taken the approach of providing a simple algebraic-style notation that allows one to express this state identification and feedback process. This notation allows one to describe a wide variety of predictors in a uniform way. It also facilitates the use of an efficient search technique called genetic programming, which is loosely modeled on the natural evolutionary process, to explore the design space. In this paper we describe our notation and the results of the application of genetic programming to the design of branch and indirect jump predictors.
Run-time adaptive cache hierarchy management via reference analysis
Authors: Johnson Teresa L. , Hwu Wen-mei W.
Published: July 2004

Improvements in main memory speeds have not kept pace with increasing processor clock frequency and improved exploitation of instruction-level parallelism. Consequently, the gap between processor and main memory performance is expected to grow, increasing the number of execution cycles spent waiting for memory accesses to complete. One solution to this growing problem is to reduce the number of cache misses by increasing the effectiveness of the cache hierarchy. In this paper we present a technique for dynamic analysis of program data access behavior, which is then used to proactively guide the placement of data within the cache hierarchy in a location-sensitive manner. We introduce the concept of a macroblock, which allows us to feasibly characterize the memory locations accessed by a program, and a Memory Address Table, which performs the dynamic reference analysis. Our technique is fully compatible with existing Instruction Set Architectures. Results from detailed simulations of several integer programs show significant speedups.
DataScalar architectures
Authors: Burger Doug , Kaxiras Stefanos , Goodman James R.
Published: July 2004

DataScalar architectures improve memory system performance by running computation redundantly across multiple processors, which are each tightly coupled with an associated memory. The program data set (and/or text) is distributed across these memories. In this execution model, each processor broadcasts operands it loads from its local memory to all other units. In this paper, we describe the benefits, costs, and problems associated with the DataScalar model. We also present simulation results of one possible implementation of a DataScalar system. In our simulated implementation, six unmodified SPEC95 binaries ran from 7% slower to 50% faster on two nodes, and from 9% to 100% faster on four nodes, than on a system with a comparable, more traditional memory system. Our intuition and results show that DataScalar architectures work best with codes for which traditional parallelization techniques fail. We conclude with a discussion of how DataScalar systems may accommodate traditional parallel processing, thus improving performance over a much wider range applications than is currently possible with either model.
An electro-optic data communication system for the Delft parallel processor
Authors: Frietman E. E. E. , Ruighaver A. B.
Published: July 2004

The Delft Parallel Processor (DPP), which has already been operational since 1981, is part of a long term research project for the application of a large-scale Multiple Instruction stream, Multiple Data stream (MIMD) architecture in the field of scientific computing. As a result of this project a second modern version, the DPP84, equipped with up to 16 Processing Elements (PE's), is now operational and has been installed at several sites inside and outside the Technical University Delft. The most important part of the DPP is its communication system, which is based on a "multiple broadcast" concept. This allows all the PE's to be fully interconnected through fast parallel data channels. To realize a large-scale next-generation MIMD supercomputer in which all PE's are fully interconnected, a different technical approach to this communication system is needed. This paper introduces the concept of an Electro-Optic Communication System (EOCS). In order to be able to implement a high-bandwidth parallel interconnection structure, the application of flexible polymer fiber-optic cables is considered.
An introduction to computing with neural nets
Authors: Lippmann Richard P.
Published: July 2004

Artificial neural net models have been studied for many years in the hope of achieving human-like performance in the fields of speech and image recognition. These models are composed of many nonlinear computational elements operating in parallel and arranged in patterns reminiscent of biological neural nets. Computational elements or nodes are connected via weights that are typically adapted during use to improve performance. There has been a recent resurgence in the field of artificial neural nets caused by new net topologies and a1gorithms, analog VLSI implementation techniques, and the belief that massive parallelism is essential for high performance speech and image recognition. This paper provides an introduction to the field of artificial neural nets by reviewing six important neural net models that can be used for pattern classification. These nets are highly parallel building blocks that illustrate neural- net components and design principles and can be used to construct more complex systems. In addition to describing these nets, a major emphasis is placed on exploring how some existing classification and clustering algorithms can be performed using simple neuron-like components. Single-layer nets can implement algorithms required by Gaussian maximum-likelihood classifiers and optimum minimum-error classifiers for binary patterns corrupted by noise. More generally, the decision regions required by any classification algorithm can be generated in a straightforward manner by three-layer feed-forward nets.
Software for neural networks
Authors: Anderson James A. , Wisniewski Edward J. , Viscuso Susan R.
Published: July 2004

Neural networks "compute" though not in the way that traditional computers do. It is necessary to accept their weaknesses to use their strengths. We discuss some of the assumptions and constraints that govern operation of neural nets, describe one particular non-linear network---the BSB model---in a little detail, and present two applications of neural network computations to illustrate some of the peculiarities inherent in this architecture. We show how a network can be trained to estimate answers to simple multiplication problems and how a network can be used to disambiguate lexical items by context. In both examples, the way information is represented in the pattern of system unit activities is at least as important as the details of the learning and retrieval algorithms used.
Performance of various computers using standard linear equations software in a FORTRAN environment
Authors: Dongarra Jack J.
Published: July 2004

This note compares the performance of different computer systems while solving dense systems of linear equations using the LINPACK software in a Fortran environment. About 100 computers, ranging from a CRAY X-MP to the 68000 based systems such as the Apollo and SUN Workstations to IBM PC's, are compared.
MaRs: a parallel graph reduction multiprocessor
Authors: Castan M. , Contessa A. , Cousin E. , Coustet C. , Lecussan B.
Published: July 2004

We describe the MaRS machine: a parallel, distributed control multiprocessor for graph reduction using a functional machine language. The object code language is based on an optimized set of combinators, and its functional character allows an automatic parallelisation of the execution. A programming language, "MaRS LISP", has also been developed. A prototype of MaRS is currently being designed in VLSI 1.5-micron CMOS technology with 2 levels of metal, by means of a CAD system. The machine uses three basic types of processors for Reduction, Memory and Communication, plus auxiliary I/O and Arithmetic Processors; communications do not constitute an operational bottleneck, as interprocessor messages are routed via an Omega switching network. Initially, a Host Computer will be used for startup, testing and direct memory access. The machine architecture and its functional organization are described, as well as the theoretical execution model. We conclude on a number of specialized hardware and software mechanism that differentiate MaRS machine from other similar projects currently going on.
The ultimate RISC
Authors: Jones Douglas W.
Published: July 2004

Reduced instruction set computer (RISC) architectures have attracted considerable interest during the past decade. The ultimate RISC architecture presented here is an extreme yet simple illustration of such an architecture. It has only one instruction, move memory to memory, yet it is useful.
Superscalar vs. superpipelined machines
Authors: Jouppi Norman P.
Published: July 2004

The performance and implementation cost of superscalar and superpipelined machines are compared. Superscalar machines can issue several instructions per cycle. Superpipelined machines can issue only one instruction per cycle, but they have cycle times shorter than the time required for any operation. Both of these techniques exploit instruction-level parallelism, which is often limited in many applications. Superpipelined machines are shown to have better performance and less cost than superscalar machines.
Benchmark health considered harmful
Authors: Zilles Craig B.
Published: July 2004

In the past couple of years, a number of software and architectural techniques have been proposed for improving the performance of linked data structrues. These research ideas are often evaluated using the Olden benchmark suite [1]. Frequently, in such experients, the largest speed-up is attained for the benchmark called
health
. This article demonstrates that this benchmark is a micro-benchmark for enormous linked lists traversals, and not a good one at that. Given that linked lists of such size are not an efficient data structure, it is unlikely that this benchmark corresponds to any real program. Hence the benchmark should not be used. To demonstrate the inherent inefficiency in its use of linked data structures, the
health
program was modified algorithmically to generate the same output, while improving the execution time by over a factor of 200 on a 500Mhz Pentium II Xeon.
Architectural tradeoff in implementing RSA processors
Authors: Chang Fu-Chi , Wang Chia-Jiu
Published: July 2004

An investigation of a suite of RSA processors using different exponentiation and modular arithmetic algorithms is the main theme of this paper. The execution time and the amount of hardware required of different algorithms used to implement the RSA processor are compared. The modular algorithms examined in this paper are classical modular algorithm, Barrett's modular algorithm, Hensel's odd division and Montgomery's modular algorithm. The exponentiation algorithms implemented are the left-to-right binary method, the right-to-left binary method, the Chinese remainder theorem. This work finds that the fast RSA processor is the one using the Chinese remainder theorem with right to left scan for exponentiation operations and Barrett's algorithm for modular arithmetic operations. The RSA processor using least amount of hardware is the one using the left-o-right binary method for exponentiation operations and Montgomery's algorithm for modular operations.
Disjoint Eager Execution
Authors: Uht Augustus K.
Published: July 2004

Disjoint Eager Execution (DEE) has been cited and described many times since its introduction in 1992, often incorrectly. This paper clarifies what DEE is and how it operates, as well as pointing out common DEE misconceptions.
The control mechanism for the Myrias parallel computer system
Authors: Beltrametti Monica , Bobey Kenneth , Zorbas John R.
Published: July 2004

This paper presents an overview of the issues involved in the design of the control mechanism used by the Myrias parallel computer system to manage the execution of parallel programs. The following issues are discussed: initial task distribution, dynamic load leveling, hierarchical caching, task synchronization, memory management, and scalability. Some of the more important points are illustrated using performance measurements obtained by running a test program on the Myrias Research Corporation prototype system.
YACKOS on a shared-memory multiprocessor
Authors: Finkel Raphael , Hengsen Debra
Published: July 2004

Yackos(yet another communication-kernel operating system)is designed for high speed, low latency inter-process communication. Speed is obtained by avoiding context switches and presenting to processes a low-level interface. Processes avoid context switches when passing messages by sharing data with the kernel. Yackos message passing was first implemented above Unix on Sequent shared-memory multiprocessors where round-trip messages can be passed in under 200 microseconds. It was then ported to both Sun and Vax workstations.
Dynamic RAM for on-chip instruction caches
Authors: Cortadella Jordi , Jové Teodor
Published: July 2004

On-chip memories are commonly used to reduce the external communication bandwidth of current microprocessors. Implementations with static RAM allow simple synchronization structures. The use of dynamic RAM results in an important area saving but complicates the processor control due to the refresh requirements. In this paper, a simple design approach, based on the use of dynamic RAM, is introduced for implementing on-chip instruction caches without complicating the processor control.
Comparing production system architectures
Authors: Lease Mark , Lively Mac
Published: July 2004

Expert systems have become very popular in recent years. But the forward-chaining production systems (PS) driving the expert systems have severe limitations when run on general-purpose computers. The Match phase of the Match-Act-Select cycle production systems execute is computationally expensive and creates a limitation in the performance the PS's can deliver. This paper examines the architecture of three computers (DADO2, NON-VON, and Production System Machine) designed to speed up the Match process by pattern matching many facts and rules in parallel. The speeds of the designs are compared and the systems are analyzed to determine how suitable they are for use in the commercial environment.
The Flex architecture, a high speed graphics processor
Authors: Page Ivor , Niehaus Jeff
Published: July 2004

The design of a computer graphics pipeline is examined in detail using high speed floating point multiply/add units and cross bar switches as building blocks. Various parallel and pipelined arrangements are explored for simulating the individual stages of the pipe. It is shown that a highly versatile architecture, entitled the
FLEX ARCHITECTURE
based on four processors and a 16 port switch, can be used efficiently to simulate all stages of the graphics pipeline and, for high performance systems, multiple flex units are considered. Estimates of performance are developed using a particular set of components available from Texas Instruments. Designs with performance in excess of one to two million vectors per second are feasible.
Some results concerning clock-regulated queues
Authors: Percus Ora E. , Percus J. K.
Published: July 2004

A single clock-regulated queue is fed by two Bernouilli streams of messages. We present the distributions of queue length, of waiting time, and of output for such a system. This is generalized as well to the case of a queue of finite capacity.
The optimum pipeline depth for a microprocessor
Authors: Hartstein A. , Puzak Thomas R.
Published: July 2004

The impact of pipeline length on the performance of a microprocessor is explored both theoretically and by simulation. An analytical theory is presented that shows two opposing architectural parameters affect the optimal pipeline length: the degree of instruction level parallelism (superscalar) decreases the optimal pipeline length, while the lack of pipeline stalls increases the optimal pipeline length. This theory is tested by analyzing the optimal pipeline length for 35 applications representing three classes of workloads. Trace tapes are collected from SPEC95 and SPEC2000 applications, traditional (legacy) database and on-line transaction processing (OLTP) applications, and modern (e. g. web) applications primarily written in Java and C++. The results show that there is a clear and significant difference in the optimal pipeline length between the SPEC workloads and both the legacy and modern applications. The SPEC applications, written in C, optimize to a shorter pipeline length than the legacy applications, largely written in assembler language, with relatively little overlap in the two distributions. Additionally, the optimal pipeline length distribution for the C++ and Java workloads overlaps with the legacy applications, suggesting similar workload characteristics. These results are explored across a wide range of superscalar processors, both in-order and out-of-order.
Slack
Authors: Fields Brian , Bodík Rastislav , Hill Mark D.
Published: July 2004

Many emerging processor microarchitectures seek to manage technological constraints (e.g., wire delay, power, and circuit complexity) by resorting to
non-uniform
designs that provide resources at multiple quality levels (e.g., fast/slow, bypass paths, multi-speed functional units, and grid architectures). In such designs, the constraint problem becomes a control problem, and the challenge becomes designing a
control policy
that mitigates the performance penalty of the non-uniformity. Given the increasing importance of non-uniform control policies, we believe it is appropriate to examine them in their own right.To this end, we develop
slack
for use in creating control policies that match program execution behavior, to machine design. Intuitively, the slack of a dynamic instruction
i
is the number of cycles
i
can be delayed with
no effect on execution time.
This property makes slack a natural candidate for hiding non-uniform latencies.We make three contributions in our exploration of slack. First, we formally define slack, distinguish three variants (
local, global
and
apportioned
), and perform a limit study to show that slack is prevalent in our SPEC2000 workload. Second, we show how to predict slack in hardware. Third, we illustrate how to create a control policy based on slack for steering instructions among fast (high power) and slow (lower power) pipelines.
An instruction set and microarchitecture for instruction level distributed processing
Authors: Kim Ho-Seop , Smith James E.
Published: July 2004

An instruction set architecture (ISA) suitable for future microprocessor design constraints is proposed. The ISA has hierarchical register files with a small number of accumulators at the top. The instruction stream is divided into chains of dependent instructions (strands) where intra-strand dependences are passed through the accumulator. The general-purpose register file is used for communication between strands and for holding global values that have many consumers.A microarchitecture to support the proposed ISA is proposed and evaluated. The microarchitecture consists of multiple, distributed processing elements. Each PE contains an instruction issue FIFO, a local register (accumulator) and local copy of register file. The overall simplicity, hierarchical value communication, and distributed implementation will provide a very high clock speed and a relatively short pipeline while maintaining a form of superscalar out-of-order execution.Detailed timing simulations using translated program traces show the proposed microarchitecture is tolerant of global wire latencies. Ignoring the significant clock frequency advantages, a microarchitecture that supports a 4-wide fetch/decode pipeline, 8 serial PEs, and a two-cycle inter-PE communication latency performs as well as a conventional 4-way out-of-order superscalar processor.
Detailed design and evaluation of redundant multithreading alternatives
Authors: Mukherjee Shubhendu S. , Kontz Michael , Reinhardt Steven K.
Published: July 2004

Exponential growth in the number of on-chip transistors, coupled with reductions in voltage levels, makes each generation of microprocessors increasingly vulnerable to transient faults. In a multithreaded environment, we can detect these faults by running two copies of the same program as separate threads, feeding them identical inputs, and comparing their outputs, a technique we call Redundant Multithreading (RMT).This paper studies RMT techniques in the context of both single- and dual-processor simultaneous multithreaded (SMT) single-chip devices. Using a detailed, commercial-grade, SMT processor design we uncover subtle RMT implementation complexities, and find that RMT can be a more significant burden for single-processor devices than prior studies indicate. However, a novel application of RMT techniques in a dual-processor device, which we term
chip-level redundant threading
(CRT), shows higher performance than lockstepping the two cores, especially on multithreaded workloads.
SafetyNet
Authors: Sorin Daniel J. , Martin Milo M. K. , Hill Mark D. , Wood David A.
Published: July 2004

We develop an availability solution, called
SafetyNet,
that uses a unified, lightweight checkpoint/recovery mechanism to support multiple long-latency fault detection schemes. At an abstract level,
SafetyNet
logically maintains multiple, globally consistent checkpoints of the state of a shared memory multiprocessor (i.e., processors, memory, and coherence permissions), and it recovers to a pre-fault checkpoint of the system and re-executes if a fault is detected.
SafetyNet
efficiently coordinates checkpoints across the system in logical time and uses "logically atomic" coherence transactions to free checkpoints of transient coherence state.
SafetyNet
minimizes performance overhead by pipelining checkpoint validation with subsequent parallel execution.We illustrate
SafetyNet
avoiding system crashes due to either dropped coherence messages or the loss of an interconnection network switch (and its buffered messages). Using full-system simulation of a 16-way multiprocessor running commercial workloads, we find that
SafetyNet
(a) adds statistically insignificant runtime overhead in the common-case of fault-free execution, and (b) avoids a crash when tolerated faults occur.