bluuebunny/crossref_metadata_2025 huggingface dataset:
100 GOPS vision processor for automotive applications
Authors: Ramacher Ulrich , Brüs Nico , Hachmann Ulrich , Harnisch Jens , Raab Wolfgang , Techmer Axel
Published: July 2004

Car vision systems for the improvement of driver's comfort and safety will be introduced in the next car generation, with an exponential market growth in the next years. The Corporate Research division of lnfineon Technologies AG has developed a fully programmable vision processor, which fulfills the requirements of low power, low system costs, and high computational performance (e.g., robust approaches for object detection based on stereo processing need a performance of more than 15 GIPS).The prototype currently available achieves a peak performance of 53 GOPS. With a redesign in 0.13 μm CMOS technology, the performance increases to more than 100 GOPS, while the power consumption is less than 500 mW and the die size reduces to 70 mm
2
.
Fine-grain design space exploration for a cartographic SoC multiprocessor
Authors: Bechini Alessio , Foglia Pierfrancesco , Prete Cosimo Antonio
Published: July 2004

Traditionally, in the field of embedded systems low power consumption and low cost have been always regarded as stringent specification constraints. In recent years, high computational power has become a fundamental requirement as well. This has been mainly determined by the introduction of new features, typical of general-purpose systems, e.g. GUI-based interfaces. In this setting, low cost, low power consumption, significant computational power and short time-to-market are conflicting needs that have to be accommodated. The adoption of a simple multiprocessor on a single chip can be deemed a convenient answer, because it is able to deliver a considerable computing power using low-cost and low-power CPU cores. In this paper, we take into account SPP, a cartographic system to be deployed on hand-held devices. We present the overall methodology used for designing the multiprocessor architecture of its hardware platform, and we focus on the activities that have been carried out to get to the more convenient setting for the system, respect to the specification requirements.The adopted design process includes two phases. The former (
coarse-grain exploration
) is aimed at selecting an architecture suitable to properly support the appliance features; the latter (
finegrain exploration
) is aimed at tuning the parameter values with the purpose of obtaining to the best system setting. We show how this tuning phase for the SPP chipset has involved the selection the clock rate and the cache coherence strategy, and the analysis of bus traffic. Moreover, from the discussed study it becomes evident that further improvements in the system performance have to be pursued possibly operating on the software components.
A state-of-the-art SIMD two-dimensional FFT array processor
Authors: Yasrebi Mehrad , Lipovski G. J.
Published: July 2004

A novel implementation of a Two-dimensional FFT array processor is given. The reasons for its superior performance is the one-to-one and onto mapping of the problem communications topology onto the interconnection network, VLSI-based implementation, a proper choice for the number system, multiple-parallelism, and the use of packet-switching as opposed to circuit switching. A performance comparison also presented.
A special purpose LSI processor using the DDA algorithm for image transformation
Authors: Kawakami Katsura , Shimazaki Shigeo
Published: July 2004

A new special purpose processor, named MN8614, has been developed for the high speed execution of binary image transformations. The processor carrys out the processing based on a new extension of the DDA algorithm to reduce the number of multiplications required for image processing. In addition, a machine instruction set has been developed which makes optimal use of the new method. The processor is fabricated on a single LSI chip with 16-bit data paths. Although the basic chip design is the same as that used in the construction of a general purpose microprocessor, the processing speed of MN8614 proves to be more than 30 times faster.
The status of manip - a multicomputer architecture for solving, combinatorial extremum-search problems
Authors: Wah Benjamin W. , Li Guo-Jie , Yu Chee-Fen
Published: July 2004

In this paper, we report the status of study on MANIP, a parallel computer for solving combinatorial extremum-search problems. The most general technique that can be used to solve a wide variety of these problems on a uniprocessor system, optimally or sub-optimally, is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms with lower-bound tests for parallel processing. Three major problems are identified in the design: interconnection networks for supporting the selection of subproblems, anomalies in parallelism and virtual-memory support. A unidirectional ring network has been shown to be the most cost-effective selection network. We provide sufficient conditions so that anomalies can be eliminated under certain conditions and show that anomalies are unavoidable otherwise. Lastly, we develop a modified branch-and-bound algorithm so that the amount of memory space required under a best-first search is significantly reduced.
Performance analysis of circuit switching, baseline interconnection networks
Authors: Lee Manjai , Wu Chuan-lin
Published: July 2004

Performance evaluation, using both analytical and simulation models, of circuit switching baseline networks is presented. Two configurations of the baseline networks, single and dual, are evaluated. In each configuration, two different conflict resolution strategies, drop and hold, are tried to see the performance difference. Our analytical models are based on a more realistic assumption. New analyses are given and are verified by simulation results. In single network configuration, it is shown that the drop strategy is better than the hold strategy in the case that the data transfer time is longer than 10 cycles under a high request rate. In the dual network configuration, five different communication strategies are investigated and the optimum performance level is shown to be dependent on the length of the data transfer time.
The importance of being square
Authors: Kruskal Clyde P. , Snir Marc
Published: July 2004

We present a theory that defines performance of packet-switching interconnection networks (delay and capacity) and their cost in terms of their geometry. This is used to prove that square banyan networks have optimal performance/cost ratio. These results, together with some known results on the complexity of routing in multistage networks, show that multistage shuffle-exchange networks are the unique networks with both optimal performance and simple routing. Finally, square delta networks are shown to have optimal area complexity.
Connection principles for multipath, packet switching networks
Authors: Chin Chi-Yuan , Hwang Kai
Published: July 2004

Packet switched
Multistage Interconnection Networks
(MINs) have been mostly proposed to use unique connection path between any source and destination. We propose to add a few extra stages in an MIN to create multiple paths between any source and destination. Connection principles of
Multipath MINs
(MMINs) for packet switching are presented in this paper. Performance of such network is analyzed for possible use in multiprocessor systems and dataflow computers. For an MMIN with n nodes, the number of required stages is confined in the range [log
2
n+1, 2log
2
n-1]. Each stage consists of n/2 buffered 2-by-2 switching cells. In practice, one or two extra stages is sufficient beyond log
2
n stages required in a unique-path MIN. The delays of MMINs are shown much shorter than that of using unique-path MINs for packet switching. The improvement lies in significantly reduced packet wait delays in buffers, especially under heavy traffic conditions. The tradeoffs between reduced network delays and increased hardware cost are studied. Optimal design criteria and procedures are provided for developing MMINs with a fixed network size and stages.
Instruction issue logic for pipelined supercomputers
Authors: Weiss Shlomo , Smith James E.
Published: July 2004

Basic principles and design tradeoffs for control of pipelined processors are first discussed. We concentrate on register-register architectures like the CRAY-1 where pipeline control logic is localized to one or two pipeline stages and is referred to as “instruction issue logic”. Design tradeoffs are explored by giving designs for a variety of instruction issue methods that represent a range of complexity and sophistication. These vary from the original CRAY-1 issue logic to a version of Tomasulo's algorithm, first used in the IBM 360/91 floating point unit. Also studied are Thornton's “scoreboard” algorithm used on the CDC 6600 and an algorithm we have devised. To provide a standard for comparison, all the issue methods are used to implement the CRAY-1 scalar architecture. Then, using a simulation model and the Lawrence Livermore Loops compiled with the CRAY FORTRAN compiler, performance results for the various issue methods are given and discussed.
Fast execution of loops with if statements
Authors: Banerjee Utpal , Gajski Daniel D.
Published: July 2004

In this paper we show how to execute in parallel loops containing IF statements. We give an architectural model of parallel computation and describe the design of a hardware Boolean Recurrence Solver. Our method of handling such loops is then compared with those used by some of the existing supercomputers.
A parallel pipelined relational query processor
Authors: Gajski Daniel , Kim Won , Fushimi Shinya
Published: July 2004

This paper outlines the overall architecture of a query processor for relational queries and describes the design and control of its major processing modules. The query processor consists of only four processing modules and a number of random-access memory modules. Each processing module processes tuples of relations in a bit-serial, tuple-parallel manner for each of the primitive database operations which comprise a complex relational query. The query processor is designed to be manufacturable using existing VLSI technology, and to support in a uniform manner both the numeric and nonnumeric processing requirements a high-level query language like SQL presents.
An efficient VLSI dictionary machine
Authors: Somani Arun K. , Agarwal Vinod K.
Published: July 2004

A binary tree machine which can handle all the dictionary machine and priority queue operations as well as some other data queries is designed in this paper. This machine supports operations like Insert, Delete, Extract-Min/Max, Membership and Near and their redundant forms. If the number of keys present in the tree is n, then each of the operations takes O(log n) steps, and can be fed into the tree in a pipeline manner at a constant rate. A machine with N=2**s-1 processors can store upto N-s data elements. The output is generated at a fixed interval. It does not use any horizontal wires as in some previous designs. Moreover, this approach does not require any sorted-order, is potentially applicable to non-binary tree structures, and is significantly simpler to implement than all the previous designs.
Architecture of SOAR
Authors: Ungar David , Blau Ricki , Foley Peter , Samples Dain , Patterson David
Published: July 2004

Smalltalk on a RISC (SOAR) is a simple, Von Neumann computer that is designed to execute the Smalltalk-80 system much faster than existing VLSI microcomputers. The Smalltalk-80 system is a highly productive programming environment but poses tough challenges for implementors: dynamic data typing, a high level instruction set, frequent and expensive procedure calls, and object-oriented storage management. SOAR compiles programs to a low level, efficient instruction set. Parallel tag checks permit high performance for the simple common cases and cause traps to software routines for the complex cases. Parallel register initialization and multiple on-chip register windows speed procedure calls. Sophisticated software techniques relieve the hardware of the burden of managing objects. We have initial evaluations of the effectiveness of the SOAR architecture by compiling and simulating benchmarks, and will prove SOAR's feasibility by fabricating a 35,000-transistor SOAR chip. These early results suggest that a Reduced Instruction Set Computer can provide high performance in an exploratory programming environment.
Automatic synthesis of systolic arrays from uniform recurrent equations
Authors: Quinton Patrice
Published: July 2004

We describe a systematic method for the design of systolic arrays. This method may be used for algorithms that can be expressed as a set of uniform recurrent equations over a convex set D of Cartesian coordinates. Most of the algorithms already considered for systolic implementation may be represented in this way. The methods consists of two steps: finding a timing-function for the computations that is compatible with the dependences introduced by the equations, then mapping the domain D onto another finite set of coordinates, each representing a processor of the systolic array, in such a way that concurrent computations are mapped onto different processors. The scheduling and mapping functions meet conditions that allow the full automation of the method. The method is exemplified on the convolution product and the matrix product.
Multi-dimensional systolic networks, for discrete fourier transform
Authors: Zhang Chang nian , Yun David Y. Y.
Published: July 2004

In this paper the problem of computing the Discrete Fourier Transform (DFT) in VLSI is considered. We describe an approach to extend the linear systolic array algorithm to the multidimensional systolic network algorithm. The proposed networks is based on the pipeline design and have regular structure. Among them the mesh-connected network matches, with a small factor, the known theoretical Ω(n
2
) lower bound to the (area ×
time
2
) measure of complexity in the planar VLSI.
Unidirectional error correction/detection for VLSI memory
Authors: Bose Bella
Published: July 2004

Unidirectional error protecting codes for VLSI memories are described. After developing the theory of unidirectional error detection and correction, optimal systematic codes capable of detecting unidirectional errors are presented. Efficient single error correcting and d(d≥2)-unidirectional error detecting codes are also discussed.
Scheduling of tasks for distributed processors
Authors: Mehrotra Ravi , Talukdar Sarosh N.
Published: July 2004

The paper describes a technique for estimating the minimum execution time of an algorithm or a mix of algorithms on a distributed processing system. Bottlenecks that would have to be removed to further reduce the execution time are identified. The main applications are for the high level design of special purpose distributed processing systems.

The distributed systems are modelled by P, a set of nonidentical processors and R, a set of resources that the processors can use. The algorithms are modelled by T, an ordered set of tasks. The problem of optimally assigning the processors to the tasks while meeting the resource constraints is NP-complete. However, a heuristic using maximum weighted matchings on graphs has been devised that is extremely fast and comes reasonably close to the optimal solutions.
Fault-secure algorithms for multiple-processor systems
Authors: Banerjee Prithviraj , Abraham Jacob A.
Published: July 2004

In this paper we describe techniques for achieving fault secureness with low cost in multiple processor
7
systems. In order to do this we consider the

relationships
N

between algorithms, parallel architectures, and fault tolerance. The concept of fault-secure algorithms, described in this paper, involves the application of the ideas of fault tolerance at the system level to high-performance multiple-processor algorithms to make the results of the computation reliable. Algorithms are classified into broad classes called paradigms which are determined exclusively by the communication patterns of the processors. Fault-secure techniques are presented for three powerful paradigms: the multiplex, the recursive combination, and the multiplex-demultiplex paradigms. The basic idea used in the design of fault-tolerant algorithms is that the algorithms operate on encoded input data and produce encoded output data such that the over-head in time and number of processors is not high. This technique is distinguished by three characteristics: the encoding of the data used by the algorithm, the re-design of the algorithm to operate on the encoded data, and the distribution of the computation steps in the algorithm among the computation units.
Execution of logic programs on a dataflow architecture
Authors: Bic Lubomir
Published: July 2004

Logic programming is a mathematical formalism capable of expressing certain classes of problems in a non-procedural manner. Furthermore, logic programs do not presuppose a von Neumann computer architecture and are therefore inherently well suited to parallel computations. In this paper we consider a data-driven model for interpreting logic programs and investigate the architectural requirements necessary to support its implementation. It will be shown that the model is capable of exploiting the capabilities of highly-parallel dataflow architectures.
A Characterization of Processor Performance in the vax-11/780
Authors: Emer Joel S. , Clark Douglas W.
Published: July 2004

This paper reports the results of a study of VAX-11/780 processor performance using a novel hardware monitoring technique. A micro-PC histogram monitor was built for these measurements. It keeps a count of the number of microcode cycles executed at each microcode location. Measurement experiments were performed on live timesharing workloads as well as on synthetic workloads of several types. The histogram counts allow the calculation of the frequency of various architectural events, such as the frequency of different types of opcodes and operand specifiers, as well as the frequency of some implementation-specific events, such as translation buffer misses. The measurement technique also yields the amount of processing time spent in various activities, such as ordinary microcode computation, memory management, and processor stalls of different kinds. This, paper reports in detail the amount of time the “average” VAX instruction spends in these activities.
The peripheral processor pp4, a highly regular VLSI processor
Authors: Moeller W. D. , Sandweg G.
Published: July 2004

The architecture of an experimental 8/16-bit peripheral processor is described. The chip was fabricated in a 2-μm NMOS technology with two metal layers. There are about 300 000 transistors on a chip area of 105 mm
2
. The average time for a read-modify-write instruction is 200 ns. A highly modular and regular design style and some automatically generated layouts resulted in a short design time.
A multiprocessor network suitable for single-chip VLSI implementation
Authors: Samatham M. R. , Pradhan D. K.
Published: July 2004

This paper presents a multiprocessor network architecture suitable for VLSI implementation. The proposed class of architectures is based on De Bruijn graphs which are distinct from the well-studied shuffle-exchange graphs. Compared to these latter De Bruijn graphs possess a smaller diameter and a greater fault-tolerance. The proposed architectures are shown to be suitable for efficient execution of parallel algorithms such as the N-point fast Fourier transform (FFT). It is shown that any VLSI layout of the proposed networks requires an area of atleast Ω(N
2
/logN), thus, providing a lower bound which is greater than that for shuffle-exchange graphs. Two procedures for laying out these networks on a VLSI chip are presented. The first procedure produces an O(N
2
/logN)-area layout and has a time complexity of O(N). The second procedure also produces an O(N
2
/logN)-area layout with good aspect ratio close to unity (for small N).
A low-overhead coherence solution for multiprocessors with private cache memories
Authors: Papamarcos Mark S. , Patel Janak H.
Published: July 2004

This paper presents a cache coherence solution for multiprocessors organized around a single time-shared bus. The solution aims at reducing bus traffic and hence bus wait time. This in turn increases the overall processor utilization. Unlike most traditional high-performance coherence solutions, this solution does not use any global tables. Furthermore, this coherence scheme is modular and easily extensible, requiring no modification of cache modules to add more processors to a system. The performance of this scheme is evaluated by using an approximate analysis method. It is shown that the performance of this scheme is closely tied with the miss ratio and the amount of sharing between processors.
An economical solution to the cache coherence problem
Authors: Archibald James , Baer Jean Loup
Published: July 2004

In this paper we review and qualitatively evaluate schemes to maintain cache coherence in tightly-coupled multiprocessor systems. This leads us to propose a more economical (hardware-wise), expandable and modular variation of the “global directory” approach. Protocols for this solution are described. Performance evaluation studies indicate the limits (number of processors, level of sharing) within which this approach is viable.
Input/Output considerations in look-ahead processing
Authors: Conner William M. , Dirling Edward R.
Published: July 2004

The problems associated with input/output instructions in a look-ahead processing environment are discussed. The results of an empirical study which shows the detrimental effects of such instructions on the performance of a look-ahead central processor are presented.
The case against stack-oriented instruction sets
Authors: Myers Glenford J.
Published: July 2004

Stack-oriented (reverse-Polish-oriented) instruction sets have been claimed to be superior to register-oriented instruction sets. This paper refutes this claim and also shows that a third form is more desirable.
Computer communication techniques
Authors: Thurber Kenneth J.
Published: July 2004

This paper examines the concept of computer communication systems as seen from the viewpoint of the system architectures of distributed processor systems and networks. The fundamental concepts of bus structures, circuit switches, and message/packet switches are examined.
A variation on the PDP 11
Authors: Jennings Hal W.
Published: July 2004

This paper discusses some pros and cons of the very popular mini computer, the PDP 11, and suggests a variation on its architecture. The new architecture evolves through a few phases. The end result is a processer with variable length and width operands. This is particularly useful to support vector oriented languages such as APL.This processor has never been implemented and there are no plans to do so. There would be much more design work to do. It was originally intended to be implementable with a bit sliced microprocessor.
The nature of "computer architecture"
Authors: Cox Lyle A.
Published: July 2004

"The finest words in the world are only vain sounds if you cannot understand them." Anatole FranceThere are several different interpretations of what "computer architecture" is, and what the phrase means. An informal survey of professionals who routinely deal with computers was conducted to determine better the perceived meaning of "computer architecture". From this I hoped to identify potential areas of misunderstanding when discussing the various aspects of computer architecture.
TUKI
Authors: French Elaine , Glaser Hugh
Published: July 2004

An important feature of the Japanese Fifth Generation initiative is the investigation of novel computer architectures. One promising field of interest is that of data flow architectures inspired by the work at MIT and Manchester University. Having recognised the connection between functional programming and data flow, the work at Westfield has concentrated on the design of high level applicative languages. In this paper we describe a data flow architecture that was designed to support our language CAJOLE. We discuss a single processor architecture, a prototype of which has been built, and that can now be used as the building block for a closely-coupled distributed system.
On the design of Always Compatible Instruction Set Architecture(ACISA)
Authors: Bhujade M. R.
Published: July 2004

This note suggests a concept of a new kind of interrupt called GAP to be used in filling gaps in the Architecture of a computing system.
PASM
Authors: Siegel Howard Jay , Schwederski Thomas , Davis Nathaniel J. , Kuehn James T.
Published: July 2004

PASM is a multifunction partitionable SIMD/MIMD system being designed at Purdue for parallel image understanding. It is to be a large-scale, dynamically reconfigurable multimicroprocessor system, which will incorporate over 1,000 complex processing elements. Parallel algorithm studies and simulations have been used to analyze application tasks in order to guide design decisions. A prototype of PASM is under construction (funded by an equipment grant from IBM), including 30 Motorola MC68010 processors, a multistage interconnection network, five disk drives, and connections to the Purdue Engineering Computer Network (for access to peripherals, terminals, software development tools, etc.). PASM is to serve as a vehicle for studying the use of parallelism for performing the numeric and symbolic processing needed for tasks such as computer vision. The PASM design concepts and prototype are overviewed and brief examples of parallel algorithms are given.
Methodology for designing a computer architecture
Authors: Aslam Javaid
Published: July 2004

To design a computer architecture for a class of computations (algorithms), systematically and in a top-down fashion, a general and uniform methodology should be developed. For a given class, there exists an information structure of the architecture such that efficient performance can be achieved for the given class. The methodology is used to find such an information structure and then, to define the control structure of the architecture at functional level. The control structure itself can be treated as another architecture (with a different computing environment), and therefore, again, its Information Structure and then Control Structure (at a lower level) could be found using the same methodology. This recursive application of the methodology to define and design Information Structures and Control Structures terminates when the Control Structure can be trivially 'hard-wired'. Power of the methodology will lie in its generality, i.e. it could be used to design an architecture for practically any arbitrary computing environment.
Analysis of simulation-adapted SPEC 2000 benchmarks
Authors: Gòmez I. , Piñuel L. , Prieto M. , Tirado F.
Published: July 2004

In this paper we have compared the accuracy and representativeness of two common approaches (namely, fast forwarding and reduced input datasets) employed in current architectural studies to deal with the extremely long times involved in detailed architectural simulations. The experimental methodology chosen to perform the validation of both techniques consists in direct execution and performance monitoring through hardware performance counters, our study being focused on the nine SPECint benchmarks for which a reduced input dataset version exists. As a target system we have opted to use an Intel Pentium-4 microprocessor due to its remarkable monitoring features. The results obtained suggest that both techniques are similar, i.e. in some cases Fast-forward is preferable and vice versa, whereas for some benchmarks neither of the techniques are able to provide satisfactory results. However, the simulation cost associated with the fast-forwarding technique is about two orders of magnitude lower than that corresponding to reduced input datasets.
Temperature-aware microarchitecture
Authors: Skadron Kevin , Stan Mircea R. , Huang Wei , Velusamy Sivakumar , Sankaranarayanan Karthik , Tarjan David
Published: July 2004

With power density and hence cooling costs rising exponentially, processor packaging can no longer be designed for the worst case, and there is an urgent need for runtime processor-level techniques that can regulate operating temperature when the package's capacity is exceeded. Evaluating such techniques, however, requires a thermal model that is practical for architectural studies.This paper describes HotSpot, an accurate yet fast model based on an equivalent circuit of thermal resistances and capacitances that correspond to microarchitecture blocks and essential aspects of the thermal package. Validation was performed using finite-element simulation. The paper also introduces several effective methods for dynamic thermal management (DTM): "temperature-tracking" frequency scaling, localized toggling, and migrating computation to spare hardware units. Modeling temperature at the microarchitecture level also shows that power metrics are poor predictors of temperature, and that sensor imprecision has a substantial impact on the performance of DTM.
Half-price architecture
Authors: Kim Ilhyun , Lipasti Mikko H.
Published: July 2004

Current-generation microprocessors are designed to process instructions with one and two source operands at equal cost. Handling two source operands requires multiple ports for each instruction in structures--such as the register file and wakeup logic--which are often in the processor's critical timing paths. We argue that these structures are overdesigned since only a small fraction of instructions require two source operands to be processed simultaneously. In this paper, we propose the half-price architecture that judiciously removes this overdesign by restricting the processor's capability to handle two source operands in certain timing-critical cases. Two techniques are proposed and evaluated: one for the wakeup logic is sequential wakeup, which decouples half of the tag matching logic from the wakeup bus to reduce the load capacitance of the bus. The other technique for the register file is sequential register access, which halves the register read ports by sequentially accessing two values using a single port when needed. We show that a pipeline that optimizes scheduling and register access for a single operand achieves nearly the same performance as an ideal base machine that fully handles two operands, with 2.2% (worst case 4.8%) IPC degradation.
Transient-fault recovery for chip multiprocessors
Authors: Gomaa Mohamed , Scarbrough Chad , Vijaykumar T. N. , Pomeranz Irith
Published: July 2004

To address the increasing susceptibility of commodity chip multiprocessors (CMPs) to transient faults, we propose Chiplevel Redundantly Threaded multiprocessor with Recovery (CRTR). CRTR extends the previously-proposed CRT for transient-fault detection in CMPs, and the previously-proposed SRTR for transient-fault recovery in SMT. All these schemes achieve fault tolerance by executing and comparing two copies, called leading and trailing threads, of a given application. Previous recovery schemes for SMT do not perform well on CMPs. In a CMP, the leading and trailing threads execute on different processors to achieve load balancing and reduce the probability of a fault corrupting both threads; whereas in an SMT, both threads execute on the same processor. The inter-processor communication required to compare the threads introduces latency and bandwidth problems not present in an SMT.To hide inter-processor latency, CRTR executes the leading thread ahead of the trailing thread by maintaining a long slack, enabled by asymmetric commit. CRTR commits the leading thread before checking and the trailing thread after checking, so that the trailing thread state may be used for recovery. Previous recovery schemes commit both threads after checking, making a long slack suboptimal. To tackle inter-processor bandwidth, CRTR not only increases the bandwidth supply by pipelining the communication paths, but also reduces the bandwidth demand. By reasoning that faults propagate through dependences, previously-proposed Dependence-Based Checking Elision (DBCE) exploits (true) register dependence chains so that only the value of the last instruction in a chain is checked. However, instructions that mask operand bits may mask faults and limit the use of dependence chains. We propose Death- and Dependence-Based Checking Elision (DDBCE), which chains a masking instruction only if the source operand of the instruction dies after the instruction. Register deaths ensure that masked faults do not corrupt later computation. Using SPEC2000, we show that CRTR incurs negligible performance loss compared to CRT for inter-processor (one-way) latency as high as 30 cycles, and that the bandwidth requirements of CRT and CRTR with DDBCE are 5.2 and 7.1 bytes/cycle, respectively.
ReEnact
Authors: Prvulovic Milos , Torrellas Josep
Published: July 2004

While removing software bugs consumes vast amounts of human time, hardware support for debugging in modern computers remains rudimentary. Fortunately, we show that mechanisms for Thread-Level Speculation (TLS) can be reused to boost debugging productivity. Most notably, TLS's rollback capabilities can be extended to support rolling back recent buggy execution and repeating it as many times as necessary until the bug is fully characterized. These incremental re-executions are deterministic even in multithreaded codes. Importantly, this operation can be done automatically on the fly, and is compatible with production runs.As a specific implementation of a TLS-based debugging framework, we introduce ReEnact. ReEnact targets a particularly hairy class of bugs: data races in multithreaded programs. ReEnact extends the communication monitoring mechanisms in TLS to also detect data races. It extends TLS's rollback capabilities to be able to roll back and
deterministically
re-execute the code with races to obtain the race signature. Finally, the signature is compared to a library of race patterns and, if a match occurs, the execution may be repaired. Overall, ReEnact successfully detects, characterizes, and often repairs races automatically on the fly. Moreover, it is fully compatible with always-on use in
production runs
: the slowdown of race-free execution with ReEnact is on average only 5.8%.
Energy efficient co-adaptive instruction fetch and issue
Authors: Buyuktosunoglu Alper , Karkhanis Tejas , Albonesi David H. , Bose Pradip
Published: July 2004

Front-end instruction delivery accounts for a significant fraction of the energy consumed in a dynamic superscalar processor. The issue queue in these processors serves two crucial roles: it bridges the front and back ends of the processor and serves as the window of instructions for the out-of-order engine. A mismatch between the front end producer rate and back end consumer rate, and between the supplied instruction window from the front end, and the required instruction window to exploit the level of application parallelism, results in additional front-end energy, and increases the issue queue utilization. While the former increases overall processor energy consumption, the latter aggravates the issue queue hot spot problem.We propose a complementary combination of fetch gating and issue queue adaptation to address both of these issues. We introduce an issue-centric fetch gating scheme based on issue queue utilization and application parallelism characteristics. Our scheme attempts to provide an instruction window size that matches the current parallelism characteristics of the application while maintaining enough queue entries to avoid back-end starvation. Compared to a conventional fetch gating scheme based on flow-rate matching, we demonstrate 20% better overall energy-delay with a 44% additional reduction in issue queue energy. We identify Icache energy savings as the largest contributor to the overall savings and quantify the sources of savings in this structure. We then couple this issue-driven fetch gating approach with an issue queue adaptation scheme based on queue utilization. While the fetch gating scheme provides a window of issue queue instructions appropriate to the level of program parallelism, the issue queue adaptation approach shuts down the remaining underutilized issue queue entries. Used in tandem, these complementary techniques yield a 20% greater issue queue energy savings than the addition of the savings from each technique applied in isolation. The result of this combined approach is a 6% overall energy-delay savings coupled with a 54% reduction in issue queue energy.
Positional adaptation of processors
Authors: Huang Michael C. , Renau Jose , Torrellas Josep
Published: July 2004

Although adaptive processors can exploit application variability to improve performance or save energy, effectively managing their adaptivity is challenging. To address this problem, we introduce a new approach to adaptivity: the
Positional
approach. In this approach, both the
testing
of configurations and the
application
of the chosen configurations are associated with particular code sections. This is in contrast to the currently-used
Temporal
approach to adaptation, where both the testing and application of configurations are tied to successive intervals in
time
.We propose to use
subroutines
as the granularity of code sections in positional adaptation. Moreover, we design three implementations of subroutine-based positional adaptation that target energy reduction in three different workload environments: embedded or specialized server, general purpose, and highly dynamic. All three implementations of positional adaptation are much more effective than temporal schemes. On average, they boost the energy savings of applications by 50% and 84% over temporal schemes in two experiments.
Token coherence
Authors: Martin Milo M. K. , Hill Mark D. , Wood David A.
Published: July 2004

Many future shared-memory multiprocessor servers will both target commercial workloads and use highly-integrated "glueless" designs. Implementing low-latency cache coherence in these systems is difficult, because traditional approaches either add indirection for common cache-to-cache misses (directory protocols) or require a totally-ordered interconnect (traditional snooping protocols). Unfortunately, totally-ordered interconnects are difficult to implement in glueless designs. An ideal coherence protocol would avoid indirections and interconnect ordering; however, such an approach introduces numerous protocol races that are difficult to resolve.We propose a new coherence framework to enable such protocols by separating performance from correctness. A performance protocol can optimize for the common case (i.e., absence of races) and rely on the underlying correctness substrate to resolve races, provide safety, and prevent starvation. We call the combination Token Coherence, since it explicitly exchanges and counts tokens to control coherence permissions.This paper develops TokenB, a specific Token Coherence performance protocol that allows a glueless multiprocessor to both exploit a low-latency unordered interconnect (like directory protocols) and avoid indirection (like snooping protocols). Simulations using commercial workloads show that our new protocol can significantly outperform traditional snooping and directory protocols.
Using destination-set prediction to improve the latency/bandwidth tradeoff in shared-memory multiprocessors
Authors: Martin Milo M. K. , Harper Pacia J. , Sorin Daniel J. , Hill Mark D. , Wood David A.
Published: July 2004

Destination-set prediction can improve the latency/bandwidth tradeoff in shared-memory multiprocessors. The destination set is the collection of processors that receive a particular coherence request. Snooping protocols send requests to the maximal destination set (i.e., all processors), reducing latency for cache-to-cache misses at the expense of increased traffic. Directory protocols send requests to the minimal destination set, reducing bandwidth at the expense of an indirection through the directory for cache-to-cache misses. Recently proposed hybrid protocols trade-off latency and bandwidth by directly sending requests to a predicted destination set.This paper explores the destination-set predictor design space, focusing on a collection of important commercial workloads. First, we analyze the sharing behavior of these workloads. Second, we propose predictors that exploit the observed sharing behavior to target different points in the latency/bandwidth tradeoff. Third, we illustrate the effectiveness of destination-set predictors in the context of a multicast snooping protocol. For example, one of our predictors obtains almost 90% of the performance of snooping while using only 15% more bandwidth than a directory protocol (and less than half the bandwidth of snooping).
Performance analysis of the Alpha 21364-based HP GS1280 multiprocessor
Authors: Cvetanovic Zarka
Published: July 2004

This paper evaluates performance characteristics of the HP GS1280 shared memory multiprocessor system. The GS1280 system contains up to 64 Alpha 21364 CPUs connected together via a torus-based interconnect. We describe architectural features of the GS1280 system. We compare and contrast the GS1280 to the previousgeneration Alpha systems: AlphaServer GS320 and ES45/SC45. We further quantitatively show the performance effects of these features using application results and profiling data based on the built-in performance counters. We find that the HP GS1280 often provides 2 to 3 times the performance of the AlphaServer GS320 at similar clock frequencies. We find the key reasons for such performance gains are advances in memory, inter-processor, and I/O subsystem designs.
Parallelism in the front-end
Authors: Oberoi Paramjit S. , Sohi Gurindar S.
Published: July 2004

As processor back-ends get more aggressive, front-ends will have to scale as well. Although the back-ends of superscalar processors have continued to become more parallel, the front-ends remain sequential. This paper describes techniques for fetching and renaming multiple non-contiguous portions of the dynamic instruction stream in parallel using multiple fetch and rename units. It demonstrates that parallel front-ends are a viable alternative to high-performance sequential front-ends.Compared with an equivalently-sized trace cache, our technique increases cache bandwidth utilization by 17%, front-end throughput by 20%, and performance by 5%. Parallelism also enhances latency tolerance: a parallel front-end loses only 6% performance as the cache size is decreased from 128 KB to 8 KB, compared with a 50--65% performance loss for sequential fetch mechanisms.
Effective ahead pipelining of instruction block address generation
Authors: Seznec André , Fraboulet Antony
Published: July 2004

On a N-way issue superscalar processor, the front end instruction fetch engine must deliver instructions to the execution core at a sustained rate higher than N instructions per cycle. This means that the instruction address generator/predictor (IAG) has to predict the instruction flow at an even higher rate while the prediction accuracy can not be sacrificed.Achieving high accuracy on this prediction becomes more and more critical since the overall pipeline is becoming deeper and deeper with each new generation of processors. Then very complex IAGs featuring different predictors for jumps, returns, conditional and unconditional branches and complex logic are used. Usually, the IAG uses information (branch histories, fetch addresses, . . . ) available at a cycle to predict the next fetch address(es). Unfortunately, a complex IAG cannot deliver a prediction within a short cycle. Therefore, processors rely on a hierarchy of IAGs with increasing accuracies but also increasing latencies: the accurate but slow IAG is used to correct the fast, but less accurate IAG. A significant part of the potential instruction bandwidth is often wasted in pipeline bubbles due to these corrections.As an alternative to the use of a hierarchy of IAGs, it is possible to initiate the instruction address generation several cycles ahead of its use. In this paper, we explore in details such an ahead pipelined IAG. The example illustrated in this paper shows that, even when the instruction address generation is (partially) initiated five cycles ahead of its use, it is possible to reach approximately the same prediction accuracy as the one of a conventional one-block ahead complex IAG. The solution presented in this paper allows to deliver a sustained address generation rate close to one instruction block per cycle with state-of-the art accuracy.
Cyclone
Authors: Ernst Dan , Hamel Andrew , Austin Todd
Published: July 2004

To achieve high instruction throughput, instruction schedulers must be capable of producing high-quality schedules that maximize functional unit utilization while at the same time enabling fast instruction issue logic. Many solutions exist to the scheduling problem, ranging from compile-time to run-time approaches. Compile-time solutions feature fast and simple hardware, but at the expense of conservative schedules. Dynamic schedulers produce high-quality schedules that incorporate run-time information and dependence speculation, but implementing these schedulers requires complex circuits that can slow processor clock speeds.In this paper, we present the Cyclone scheduler, a novel design that captures the benefits of both compileand run-time scheduling. Our approach utilizes a list-based single-pass instruction scheduling algorithm, implemented by hardware at run-time in the front end of the processor pipeline. Once scheduled, instructions are injected into a timed queue that orchestrates their entry into execution. To accommodate branch and load/store dependence speculation, the Cyclone scheduler supports a simple selective replay mechanism. We implement this technique by overloading instruction register forwarding to also detect instructions dependent on incorrectly scheduled operations. Detailed simulation analyses suggest that with sufficient queue width, the Cyclone scheduler can rival the instruction throughput of similarly wide monolithic dynamic schedulers. Furthermore, the circuit complexity of the Cyclone scheduler is much more favorable than a broadcast-based scheduler, as our approach requires no global control signals.
Improving dynamic cluster assignment for clustered trace cache processors
Authors: Bhargava Ravi , John Lizy K.
Published: July 2004

This work examines dynamic cluster assignment for a clustered trace cache processor (CTCP). Previously proposed cluster assignment techniques run into unique problems as issue width and cluster count increase. Realistic design conditions, such as variable data forwarding latencies between clusters and a heavily partitioned instruction window, increase the degree of difficulty for effective cluster assignment.In this work, the trace cache and fill unit are used to perform dynamic cluster assignment. The retire-time fill unit analysis is aided by a dynamic profiling mechanism embedded within the trace cache. This mechanism provides information about inter-trace data dependencies, an element absent in previous retire-time CTCP cluster assignment work. The strategy proposed in this work leads to more intra-cluster data forwarding and shorter data forwarding distances. In addition, performing cluster assignment at retire time reduces issue-time complexity and eliminates early pipeline stages. This increases overall performance for integer programs by 11.5% over our base CTCP architecture. This speedup is significantly higher than a previously proposed retire-time CTCP assignment strategy. Dynamic cluster assignment is also evaluated for several alternate cluster designs as well as for media benchmarks.