bluuebunny/crossref_metadata_2025 huggingface dataset:
RISCs vs. CISCs for Prolog: a case study
Authors: Borriello Gaetano , Cherenson Andrew R. , Danzig Peter B. , Nelson Michael N.
Published: July 2004

This paper compares the performance of executing compiled Prolog code on two different architectures under development at U. C. Berkeley. The first is the PLM, a special-purpose CISC architecture intended as a coprocessor for a host machine. The second is SPUR, a general-purpose RISC architecture that supports tagged data. Fourteen standard benchmark programs were run on both the PLM and SPUR simulators. The compiled code for SPUR was obtained by simple macro-expansion of PLM code generated by the PLM Prolog compiler. The two implementations are compared with regard to static and dynamic program size, execution speed, and memory system performance. On average, the macrocoded SPUR implementation has a static code size 14 times larger than the PLM, executes 16 times more instructions, yet requires only 2.3 times the number of machine cycles (or has the performance of 0.43 PLMs). When memory system performance is taken into account, SPUR is equivalent to 0.29 PLMs. Optimizations of the macro-expanded code and minor architectural changes to SPUR would increase this ratio to 0.53, or 0.60 for the largest benchmarks. Thus a tagged RISC architecture can execute Prolog at least half as fast as a special-purpose CISC architecture for Prolog.
A RISC architecture for symbolic computation
Authors: Kieburtz Richard B.
Published: July 2004

The G-machine is a language-directed processor architecture designed to support graph reduction as a model of computation. It can carry out lazy evaluation of functional language programs and can evaluate programs in which logical variables are used. To support these language features, the abstract machine requires tagged memory and executes some rather complex instructions, such as to evaluate a function application.This paper explores an implementation of the G-machine as a high performance RISC architecture. Complex instructions can be represented by RISC code without experiencing a large expansion of code volume. The instruction pipeline is discussed in some detail. The processor is intended to be integrated into a standard, 32-bit memory architecture. Tagged memory is supported by aggregating data with tags in a cache.
A VLIW architecture for a trace scheduling compiler
Authors: Colwell Robert P. , Nix Robert P. , O'Donnell John J. , Papworth David B. , Rodman Paul K.
Published: July 2004

Very Long Instruction Word (VLIW) architectures were promised to deliver far more than the factor of two or three that current architectures achieve from overlapped execution. Using a new type of compiler which compacts ordinary sequential code into long instruction words, a VLIW machine was expected to provide from ten to thirty times the performance of a more conventional machine built of the same implementation technology.Multiflow Computer, Inc., has now built a VLIW called the TRACE
TM
along with its companion Trace Scheduling
TM
compacting compiler. This new machine has fulfilled the performance promises that were made. Using many fast functional units in parallel, this machine extends some of the basic Reduced-Instruction-Set precepts: the architecture is load/store, the microarchitecture is exposed to the compiler, there is no microcode, and there is almost no hardware devoted to synchronization, arbitration, or interlocking of any kind (the compiler has sole responsibility for runtime resource usage).This paper discusses the design of this machine and presents some initial performance results.
Flow-control machines: the structured execution architecture (SXA)
Authors: Terry J. M.
Published: July 2004

Can the looping, branching, sequencing, and modularity of structured programming be implemented effectively by single instructions at the machine-instruction level? A proposal for a class of machines to do so is presented. Flow control verbs such as REPEAT and IF/THEN/ELSE are represented in large-format instructions containing pointers to conditional controls and other instructions. An active-instruction stack is used to nest flow structures. Independent buses for logically distinct memory spaces enhance performance.
A modified architecture for high-density MRAM
Authors: Wang Frank
Published: July 2004

This paper modifies the magnetic RAM (MRAM) architecture by removing a current rectifier per cell without sacrificing performance. A read operation of stored data is maintained by introducing a simple concept of"virtual ground" of operational amplifier. The modified MRAM design offers a reduced element area and therefore achieves an over tenfold improvement in storage density. The proposed architecture has been proven operable by an engineering experiment
Instruction translation for an experimental S/390 processor
Authors: Hilgendorf Rolf , Sauer Wolfram
Published: July 2004

The IBM™ S/390™ architecture is a complex architecture, which has grown over a long period of time. Typical implementations use microcode to cope with the more complex instructions and facilities of S/390. Current IBM S/390 processors even contain two levels of microcode.We report on an experimental S/390 processor based on a RISC processor kernel employing superscalar, out of order execution of instructions. S/390 instructions have to be translated into internal sequences of RISC instructions. Actually two closely coupled internal sequences - one for register based execution and one for storage based execution are generated. The translation is a straight-forward mapping in most cases with some flexibility for special instructions.The paper introduces the hardware mechanisms used for mapping S/390 instructions to internal sequences. The facilities, which provide a greater degree of flexibility are discussed. The interactions of the low-level mapping scheme with the microcode levels is examined. Finally we discuss our experiences with this type of implementation of a CISC architecture on a RISC processor kernel.
Designing computer systems with MEMS-based storage
Authors: Schlosser Steven W. , Griffin John Linwood , Nagle David F. , Ganger Gregory R.
Published: July 2004

For decades the RAM-to-disk memory hierarchy gap has plagued computer architects. An exciting new storage technology based on microelectromechanical systems (MEMS) is poised to fill a large portion of this performance gap, significantly reduce system power consumption, and enable many new applications. This paper explores the system-level implications of integrating MEMS-based storage into the memory hierarchy. Results show that standalone MEMS-based storage reduces I/O stall times by 4-74X over disks and improves overall application runtimes by 1.9-4.4X. When used as on-board caches for disks, MEMS-based storage improves I/O response time by up to 3.5X. Further, the energy consumption of MEMS-based storage is 10-54X less than that of state-of-the-art low-power disk drives. The combination of the high-level physical characteristics of MEMS-based storage (small footprints, high shock tolerance) and the ability to directly integrate MEMS-based storage with processing leads to such new applications as portable gigabit storage systems and ubiquitous active storage nodes.
Timestamp snooping
Authors: Martin Milo M. K. , Sorin Daniel J. , Ailamaki Anatassia , Alameldeen Alaa R. , Dickson Ross M. , Mauer Carl J. , Moore Kevin E. , Plakal Manoj , Hill Mark D. , Wood David A.
Published: July 2004

Symmetric muultiprocessor (SMP) servers provide superior performance for the commercial workloads that dominate the Internet. Our simulation results show that over one-third of cache misses by these applications result in cache-to-cache transfers, where the data is found in another processor's cache rather than in memory. SMPs are optimized for this case by using snooping protocols that broadcast address transactions to all processors. Conversely, directory-based shared-memory systems must indirectly locate the owner and sharers through a directory, resulting in larger average miss latencies.This paper proposes timestamp snooping, a technique that allows SMPs to i) utilize high-speed switched interconnection networks and ii) exploit physical locality by delivering address transactions to processors and memories without regard to order. Traditional snooping requires physical ordering of transactions. Timestamp snooping works by processing address transactions in a logical order. Logical time is maintained by adding a few bits per address transaction and having network switches perform a handshake to ensure on-time delivery. Processors and memories then reorder transactions based on their timestamps to establish a total order.We evaluate timestamp snooping with commercial workloads on a 16-processor SPARC system using the Simics full-system simulator. We simulate both an indirect (butterfly) and a direct (torus) network design. For OLTP, DSS, web serving, web searching, and one scientific application, timestamp snooping with the butterfly network runs 6-28% faster than directories, at a cost of 13-43% more link traffic. Similarly, with the torus network, timestamp snooping runs 6-29% faster for 17-37% more link traffic. Thus, timestamp snooping is worth considering when buying more interconnect bandwidth is easier than reducing interconnect latency.
MemorIES3
Authors: Nanda Ashwini , Mak Kwok-Ken , Sugarvanam Krishnan , Sahoo Ramendra K. , Soundarararjan Vijayaraghavan , Smith T. Basil
Published: July 2004

Modern system design often requires multiple levels of simulation for design validation and performance debugging. However, while machines have gotten faster, and simulators have become more detailed, simulation speeds have not tracked machine speeds, As a result, it is difficult to simulate realistic problem sizes and hardware configurations for a target machine. Instead, researchers have focussed on developing sealing methodologies and running smaller problem sizes and configurations that attempt to represent the behavior of the real problem. Given the increasing size of problems today, it is unclear whether such an approach yields accurate results. Moreover, although commercial workloads are prevalent and important in today's marketplace, many simulation tools are unable to adequately profile such applications, let alone for realistic sizes.In this paper we present a hardware-based emulation tool that can be used to aid memory system designers. Our focus is on the memory system because the ever-widening gap between processor and memory speeds means that optimizing the memory subsystem is critical for performance. We present the design of the
Memory
I
nstrumentation and
E
mulation
S
ystem (MemoriES). MemoriES is a programmable tool designed using FPGAs and SDRAMs. It plugs into an SMP bus to perform on-line emulation of several cache configurations, structures and protocols while the system is running real-life workloads in real-time, without any slowdown in application execution speed. We demonstrate its usefulness in several case studies, and find several important results. First, using traces to perform system evaluation can lead to incorrect results (off by 100% or more in some cases) if the trace size is not sufficiently large. Second. MemoriES is able to detect performance problems by profiling miss behavior over the entire course of a run, rather than relying on a small interval of time. Finally, we observe that previous studies of SPLASH2 applications using scaled application sizes can result in optimistic miss rates relative to real sizes on real machines, providing potentially misleading data when used for design evaluation.
Using meta-level compilation to check FLASH protocol code
Authors: Chou Andy , Chelf Benjamin , Engler Dawson , Heinrich Mark
Published: July 2004

Building systems such as OS kernels and embedded software is difficult. An important source of this difficulty is the numerous rules they must obey: interrupts cannot be disabled for ~too long," global variables must be protected by locks, user pointers passed to OS code must be checked for safety before use, etc. A single violation can crash the system, yet typically these invariants are unchecked, existing only on paper or in the implementor's mind.This paper is a case study in how system implementors can use a new programming methodology, meta-level compilation (MC), to easily check such invariants. It focuses on using MC to check for errors in the code used to manage cache coherence on the FLASH shared memory multiprocessor. The only real practical method known for verifying such code is testing and simulation. We show that simple, system-specific checkers can dramatically improve this situation by statically pinpointing errors in the program source. These checkers can be written by implementors themselves and, by exploiting the system-specific information this allows, can detect errors unreachable with other methods. The checkers in this paper found 34 bugs in FLASH code despite the care used in building it and the years of testing it has undergone. Many of these errors fall in the worst category of systems bugs: those that show up sporadically only after days of continuous use. The case study is interesting because it shows that the MC approach finds serious errors in well-tested, non-toy systems code. Further, the code to find such bugs is usually 10-100 lines long, written in a few hours, and exactly locates errors that, if discovered during testing, would require several days of investigation by an experienced implementor.The paper presents 8 checkers we wrote, their application to five different protocol implementations, and a discussion of the errors that we found.
Evaluating design alternatives for reliable communication on high-speed networks
Authors: Bhoedjang Raoul A. F. , Verstoep Kees , Rühl Tim , Bal Henri E. , Hofman Rutger F. H.
Published: July 2004

We systematically evaluate the performance of five implementations of a single, user-level communication interface. Each implementation makes different architectural assumptions about the reliability of the network hardware and the capabilities of the network interface. The implementations differ accordingly in their division of protocol tasks between host software, network-interface firmware, and network hardware. Using microbenchmarks, parallel-programming systems, and parallel applications, we assess the performance impact of different protocol decompositions. We show how moving protocol tasks to a relatively slow network interface yields both performance advantages and disadvantages, depending on the characteristics of the application and the underlying parallel-programming system. In particular, we show that a communication system that assumes highly reliable network hardware and that uses network-interface support to process multicast traffic performs best for all applications.
Communication scheduling
Authors: Mattson Peter , Dally William J. , Rixner Scott , Kapasi Ujval J. , Owens John D.
Published: July 2004

The high arithmetic rates of media processing applications require architectures with tens to hundreds of functional units, multiple register files, and explicit interconnect between functional units and register files. Communication scheduling enables scheduling to these emerging architectures, including those that use shared buses and register file ports. Scheduling to these shared interconnect architectures is difficult because it requires simultaneously allocating functional units to operations and buses and register file ports to the communications between operations. Prior VLIW scheduling algorithms are limited to clustered register file architectures with no shared buses or register file ports. Communication scheduling extends the range of target architectures by making each communication explicit and decomposing it into three components: a write stub, zero or more copy operations, and a read stub. Communication scheduling allows media processing kernels to achieve 98% of the performance of a central register file architecture on a distributed register file architecture with only 9% of the area, 6% of the power consumption, and 37% of the access delay, and 120% of the performance of a clustered register file architecture on a distributed register file architecture with 56% of the area and 50% of the power consumption.
Effective null pointer check elimination utilizing hardware trap
Authors: Kawahito Motohiro , Komatsu Hideaki , Nakatani Toshio
Published: July 2004

We present a new algorithm for eliminating null pointer checks from programs written in Java™. Our new algorithm is split into two phases. In the first phase, it moves null checks backward, and it is iterated for a few times with other optimizations to eliminate redundant null checks and maximize the effectiveness of other optimizations. In the second phase, it moves null checks forward and converts many null checks to hardware traps in order to minimize the execution cost of the remaining null checks. As a result, it eliminates many null checks effectively and exploits the maximum use of hardware traps. This algorithm has been implemented in the IBM cross-platform Java Just-in-Time (JIT) compiler. Our experimental results show that our approach improves performance by up to 71% for jBYTEmark and up to 10% for SPECjvm98 over the previously known best algorithm. They also show that it increases JIT compilation time by only 2.3%. Although we implemented our algorithm for Java, it is also applicable for other languages requiring null checking.
Frequent value locality and value-centric data cache design
Authors: Zhang Youtao , Yang Jun , Gupta Rajiv
Published: July 2004

By studying the behavior of programs in the SPECint95 suite we observed that six out of eight programs exhibit a new kind of value locality, the
frequent value locality,
according to which a few values appear very frequently in memory locations and are therefore involved in a large fraction of memory accesses. In these six programs ten distinct values occupy over 50% of all memory locations and on an average account for nearly 50% of all memory accesses during program execution. This observation holds for smaller blocks of consecutive memory locations and the set of frequent values remains quite stable over the execution of the program.In the six benchmarks with frequent value locality, on an average 50% of all cache misses occur during the reading or writing of the ten most frequently accessed values. We propose a new data cache structure, the
frequent value cache
(FVC), which employs a
value-centric
approach to caching data locations for exploiting the frequent value locality phenomenon. FVC is a small direct-mapped cache which is dedicated to holding only frequently occurring values. The value-centric nature of FVC enables us to store data in a compressed form where the compression is achieved by encoding the frequent values using a few bits. Moreover this simple compression scheme preserves the random access to data values in a cache line.Our experiments demonstrate that by augmenting a direct mapped cache (DMC) with a direct mapped FVC of size no more than 3 Kbytes we can obtain reductions in miss rates ranging from 1% to 68%. In fact we observed that higher reductions in miss rates can he achieved by augmenting a DMC with a small FVC as opposed to doubling the size of DMC for the 124.m88ksim and 134.perl benchmarks.
Efficient and flexible value sampling
Authors: Burrows M. , Erlingsson Ú , Leung S-T. A. , Vandevoorde M. T. , Waldspurger C. A. , Walker K. , Weihl W. E.
Published: July 2004

This paper presents novel sampling-based techniques for collecting statistical profiles of register contents, data values, and other information associated with instructions, such as memory latencies. Values of interest are sampled in response to periodic interrupts. The resulting value profiles can be analyzed by programmers and optimizers to improve the performance of production uniprocessor and multiprocessor systems.Our value sampling system extends the DCPI continuous profiling infrastructure, and inherits many of its desirable properties: our value profiler has low overhead (approximately 10% slowdown); it profiles all the code in the system, including the operating system kernel; and it operates transparently, without requiring any modifications to the profiled code.
Architectural support for copy and tamper resistant software
Authors: Thekkath David Lie Chandramohan , Mitchell Mark , Lincoln Patrick , Boneh Dan , Mitchell John , Horowitz Mark
Published: July 2004

Although there have been attempts to develop code transformations that yield tamper-resistant software, no reliable software-only methods are know. This paper studies the hardware implementation of a form of execute-only memory (XOM) that allows instructions stored in memory to be executed but not otherwise manipulated. To support XOM code we use a machine that supports internal compartments---a process in one compartment cannot read data from another compartment. All data that leaves the machine is encrypted, since we assume external memory is not secure. The design of this machine poses some interesting trade-offs between security, efficiency, and flexibility. We explore some of the potential security issues as one pushes the machine to become more efficient and flexible. Although security carries a performance penalty, our analysis indicates that it is possible to create a normal multi-tasking machine where nearly all applications can be run in XOM mode. While a virtual XOM machine is possible, the underlying hardware needs to support a unique private key, private memory, and traps on cache misses. For efficient operation, hardware assist to provide fast symmetric ciphers is also required.
Architectural support for fast symmetric-key cryptography
Authors: Burke Jerome , McDonald John , Austin Todd
Published: July 2004

The emergence of the Internet as a trusted medium for commerce and communication has made cryptography an essential component of modern information systems. Cryptography provides the mechanisms necessary to implement accountability, accuracy, and confidentiality in communication. As demands for secure communication bandwidth grow, efficient cryptographic processing will become increasingly vital to good system performance.In this paper, we explore techniques to improve the performance of symmetric key cipher algorithms. Eight popular strong encryption algorithms are examined in detail. Analysis reveals the algorithms are computationally complex and contain little parallelism. Overall throughput on a high-end microprocessor is quite poor, a 600 Mhz processor is incapable of saturating a T3 communication line with 3DES (triple DES) encrypted data.We introduce new instructions that improve the efficiency of the analyzed algorithms. Our approach adds instruction set support for fast substitutions, general permutations, rotates, and modular arithmetic. Performance analysis of the optimized ciphers shows an overall speedup of 59% over a baseline machine with rotate instructions and 74% speedup over a baseline without rotates. Even higher speedups are demonstrated with optimized substitutions (SBOXes) and additional functional unit resources. Our analyses of the original and optimized algorithms suggest future directions for the design of high-performance programmable cryptographic processors.
OceanStore
Authors: Kubiatowicz John , Bindel David , Chen Yan , Czerwinski Steven , Eaton Patrick , Geels Dennis , Gummadi Ramakrishna , Rhea Sean , Weatherspoon Hakim , Weimer Westley , Wells Chris , Zhao Ben
Published: July 2004

OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through pro-active movement of data. A prototype implementation is currently under development.
An analysis of operating system behavior on a simultaneous multithreaded architecture
Authors: Redstone Joshua A. , Eggers Susan J. , Levy Henry M.
Published: July 2004

This paper presents the first analysis of operating system execution on a simultaneous multithreaded (SMT) processor. While SMT has been studied extensively over the past 6 years, previous research has focused entirely on user-mode execution. However, many of the applications most amenable to multithreading technologies spend a significant fraction of their time in kernel code. A full understanding of the behavior of such workloads therefore requires execution and measurement of the operating system, as well as the application itself.To carry out this study, we (1) modified the Digital Unix 4.0d operating system to run on an SMT CPU, and (2) integrated our SMT Alpha instruction set simulator into the SimOS simulator to provide an execution environment. For an OS-intensive workload, we ran the multithreaded Apache Web server on an 8-context SMT. We compared Apache's user- and kernel-mode behavior to a standard multiprogrammed SPECInt workload, and compared the SMT processor to an out-of-order superscalar running both workloads. Overall, our results demonstrate the microarchitectural impact of an OS-intensive workload on an SMT processor and provide insight into the OS demands of the Apache Web server. The synergy between the SMT processor and Web and OS software produced a greater throughput gain over superscalar execution than seen on any previously examined workloads, including commercial databases and explicitly parallel programs.
Slipstream processors
Authors: Sundaramoorthy Karthik , Purser Zach , Rotenburg Eric
Published: July 2004

Processors execute the full dynamic instruction stream to arrive at the final output of a program, yet there exist shorter instruction streams that produce the same overall effect. We propose creating a shorter but otherwise equivalent version of the original program by removing ineffectual computation and computation related to highly-predictable control flow. The shortened program is run concurrently with the full program on a chip multiprocessor simultaneous multithreaded processor, with two key advantages:1)
Improved single-program performance.
The shorter program speculatively runs ahead of the full program and supplies the full program with control and data flow outcomes. The full program executes efficiently due to the communicated outcomes, at the same time validating the speculative, shorter program. The two programs combined run faster than the original program alone. Detailed simulations of an example implementation show an average improvement of 7% for the SPEC95 integer benchmarks.2)
Fault tolerance.
The shorter program is a subset of the full program and this partial-redundancy is transparently leveraged for detecting and recovering from transient hardware faults.
Microseqencer architecture supporting arbitrary branching up to 2
m
targets
Authors: Dvorak V.
Published: July 2004

A microsequencer presented in the paper features branching on values of a subset of up to m binary variables selected arbitrarily out of the complete set of n input variables, m < n. The subset of relevant variables whose values in the given present state determine the next state can be tested one by one, in groups of variable size or all variables in one step. The sequence of these tests and resulting multiway branches can be optimized so that the required speed of control is obtained at the minimum capacity of a control store. It is shown that the suggested architecture is generalization of a multiway branch control unit used at present.
Performance of various computers using standard linear equations software
Authors: Dongarra Jack J.
Published: July 2004

This report compares the performance of different computer systems in solving dense systems of linear equations. The comparison involves approximately a hundred computers, ranging from a CRAY Y-MP to scientific workstations such as the Apollo and Sun to IBM PCs.
Ariel
Authors: Frazier Gary
Published: July 2004

Ariel
is a multiprocessor architecture that we are developing to simulate neural networks and other models of distributed computation. The design is based upon a hierarchical network of coarse-grained processing modules. The module hardware uses fast digital signal processors and very large semiconductor memories to provide the throughput and storage capacity required to simulate large networks. Our objective is to provide a system that can be scaled up to simulate neural networks composed of millions of nodes and 10s of billions of interconnections at rates exceeding 100 billion connection operations per second. This paper discusses the technical challenges in neural network simulation and describes
Ariel's
major components.
A massively parallel and distributed I/O subsystem
Authors: Carretero J. , Pérez F. , de Miguel P. , García F. , Alonso L.
Published: July 2004

This paper presents
ParFiSys,
a parallel and distributed file system developed at the UPM. It provides several types of distributed file systems, which may be accessed using different mapping functions. Grouped management and parallelization are presented as new features of
ParFiSys,
not included in other existing parallel and distributed file systems. Moreover, the
ParFiSys
interface is briefly explained to show the facilities available to general purpose and supercomputing application programmers.
A discussion on non-blocking/lockup-free caches
Authors: Belayneh Samson , Kaeli David R.
Published: July 2004

Cache memories are commonly used to bridge the gap between processor and memory speed. Caches provide fast access to a subset of memory. When a memory request does not find an address in the cache, a cache miss is incurred. In most commercial processors today, whenever a data cache read miss occurs, the processor will stall until the outstanding miss is serviced. This can severely degrade the overall system performance.To remedy this situation, non-blocking (lockup-free) caches can be employed. A non-blocking cache allows the processor to continue to perform useful work even in the presence of cache misses.This paper summarizes past work on lockup free caches, describing the four main design choices that have been proposed. A summary of the performance of these past studies is presented, followed by a discussion on potential speedup that the processor could obtain when using lockup free caches.
Design aspects of the delft parallel processor DPP84 and its programming system
Authors: Ruighaver A. B.
Published: July 2004

In the middle of 1984 the first Delft Parallel Processor DPP84 will be delivered to the Computing Centre of the Delft University of Technology. This paper reflects on the relation between the hardware and software architecture of this improved design. Owing to a grant from the Dutch ministry of Education and Sciences a study is now in progress for the feasibility of this architecture to be extended to a next-generation MIMD supercomputer. As a result of this grant a small version of the DPP84 with a speed of approximately 5 MFLOP per processing element (64 bits precision) will be available.
PDOC - a database on paralel processing literature
Authors: Hake J.-Fr.
Published: July 2004

A systematic and economic development of the large-scale computing environment at research centers has to be accompanied by some services providing a survey on the relevant literature. This paper deals with the imbedding of a database on 'High Speed Computing and Parallel Processing' literature into the computing environment at KFA Jülich.
On “hot spot” contention
Authors: Lee Rosanna
Published: July 2004

In a recent paper. Pfister and Norton[4] brought to our attention the potential degradation in performance of multi-stage interconnection networks in the presence of nonuniform traffic patterns. More specifically, they studied the effect of a single
hot spot
- a location that is accessed more frequently - in an otherwise uniform traffic environment. Their simulations assumed that
all
input lines contribute to the hot spot. Their results showed that the effect of hot spots drastically reduced the bandwidth of the network. In this note. we confirm Pfister and Norton's results and present supplemental data and arguments which illustrate other aspects of hot spot contention. In particular, we show that the performance improves when the source of the hot spot is more localized.
Execution-based prediction using speculative slices
Authors: Zilles Craig , Sohi Gurindar
Published: July 2004

A relatively small set of static instructions has significant leverage on program execution performance. These problem instructions contribute a disproportionate number of cache misses and branch mispredictions because their behavior cannot be accurately anticipated using existing prefetching or branch prediction mechanisms.

The behavior of many problem instructions can be predicted by executing a small code fragment called a speculative slice. If a speculative slice is executed before the corresponding problem instructions are fetched, then the problem instructions can move smoothly through the pipeline because the slice has tolerated the latency of the memory hierarchy (for loads) or the pipeline (for branches). This technique results in speedups up to 43 percent over an aggressive baseline machine.

To benefit from branch predictions generated by speculative slices, the predictions must be bound to specific dynamic branch instances. We present a technique that invalidates predictions when it can be determined (by monitoring the program's execution path) that they will not be used. This enables the remaining predictions to be correctly correlated.
Dynamically allocating processor resources between nearby and distant ILP
Authors: Balasubramonian Rajeev , Dwarkadas Sandhya , Albonesi David H.
Published: July 2004

Modern superscalar processors use wide instruction issue widths and out-of-order execution in order to increase instruction-level parallelism (ILP). Because instructions must be committed in order so as to guarantee precise exceptions, increasing ILP implies increasing the sizes of structures such as the register file, issue queue, and reorder buffer. Simultaneously, cycle time constraints limit the sizes of these structures, resulting in conflicting design requirements.

In this paper, we present a novel microarchitecture designed to overcome the limitations of a register file size dictated by cycle time constraints. Available registers are dynamically allocated between the
primary
program thread and a
future
thread. The
future
thread executes instructions when the primary thread is limited by resource availability. The future thread is nor constrained by in order commit requirements. It is therefore able to examine a much larger instruction window and jump far ahead to execute ready instructions. Results are communicated back to the primary thread by warming up the register file, instruction cache, data cache, and instruction reuse buffer, and by resolving branch mispredicts early. The proposed microarchitecture is able to get on overall speedup of 1.17 over the base processor for our benchmark set, with speedups of up to 1.64
.
Concurrency, latency, or system overhead
Authors: Cuppu Vinodh , Jacob Bruce
Published: July 2004

Given a fixed CPU architecture and a fixed DRAM timing specification, there is still a large design space for a DRAM system organization. Parameters include the number of memory channels, the bandwidth of each channel, burst sizes, queue sizes and organizations, turnaround overhead, memory-controller page protocol, algorithms for assigning request priorities and scheduling requests dynamically, etc. In this design space, we see a wide variation in application execution times: for example, execution times for SPEC CPU 2000 integer suite on a 2-way ganged Direct Rambus organization (32 data bits) with 64-byte bursts are 10-20% lower than execution times on an otherwise identical configuration that uses 32-byte bursts. This represents two system configurations that are relatively close to each other in the design space; performance differences become even more pronounced for designs further apart.

This paper characterizes the sources of overhead in high-performance DRAM systems and investigates the most effective ways to reduce a system's exposure to performance loss. In particular, we look at mechanisms to increase a system's support for concurrent transactions, mechanisms to reduce request latency, and mechanisms to reduce the “system overhead”—the portion of the primary memory system's overhead that is not due to DRAM latency but rather to things like turnaround time, request queueing, inefficiencies due to read/write request interleaving, etc. Our simulator models a 2GHz, highly aggressive out-of-order uniprocessor. The interface to the memory system is fully non-blocking, supporting up to 32 outstanding misses at both the level-1 and level-2 caches and split-transaction busses to all DRAM banks.
Focusing processor policies via critical-path prediction
Authors: Fields Brian , Rubin Shai , Bodík Rastislav
Published: July 2004

Although some instructions hurt performance more than others, current processors typically apply scheduling and speculation as if each instruction was equally costly. Instruction cost can be naturally expressed through the
critical path
: if we could predict it at run-time, egalitarian policies could be replaced with cost-sensitive strategies that will grow increasingly effective as processors become more parallel.

This paper introduces a hardware predictor of instruction criticality and uses it to improve performance. The predictor is both effective and simple in its hardware implementation. The effectiveness at improving performance stems from using a dependence-graph model of the microarchitectural critical path that identifies execution bottlenecks by incorporating both data and machine-specific dependences. The simplicity stems from a token-passing algorithm that computes the critical path without actually building the dependence graph.

By focusing processor policies on critical instructions, our predictor enables a large class of optimizations. It can (i) give priority to critical instructions for scarce resources (functional units, ports, predictor entries); and (ii) suppress speculation on non-critical instructions, thus reducing “useless” misspeculations. We present two case studies that illustrate the potential of the two types of optimization, we show that (i) critical-path-based dynamic instruction scheduling and steering in a clustered architecture improves performance by as much as 21% (10% on average); and (ii) focusing value prediction only on critical instructions improves performance by as much as 5%, due to removing nearly half of the misspeculations.
Automated design of finite state machine predictors for customized processors
Authors: Sherwood Timothy , Calder Brad
Published: July 2004

Customized processors use compiler analysis and design automation techniques to take a generalized architectural model and create a specific instance of it which is optimized to a given application or set of applications. These processors offer the promise of satisfying the high performance needs of the embedded community while simultaneously shrinking design times.

Finite State Machines (FSM) are a fundamental building block in computer architecture, and are used to control and optimize all types of prediction and speculation, now even in the embedded space. They are used for branch prediction, cache replacement policies, and confidence estimation and accuracy counters for a variety of optimizations.

In this paper, we present a framework for automated design of small FSM predictors for customized processors. Our approach can be used to automatically generate small FSM predictors to perform well over a suite of applications, tailored to a specific application, or even a specific instruction. We evaluate the use of these customized FSM predictors for branch prediction over a set of benchmarks.
QoS provisioning in clusters
Authors: Yum Ki Hwan , Kim Eun Jung , Das Chita R.
Published: July 2004

Design of high performance cluster networks (routers) with Quality-of-Service (QoS) guarantees is becoming increasingly important to support a variety of multimedia applications, many of which have real-time constraints. Most commercial routers, which are based on the wormhole-switching paradigm, can deliver high performance, but lack QoS provisioning. In this paper, we present a pipelined wormhole router architecture that can provide high and predictable performance for integrated traffic in clusters. We consider two different implementations—a non-preemptive model and a more aggressive preemptive model. We also present the design of a network interface card (NIC) based on the Virtual Interface Architecture (VIA) design paradigm to support QoS in the NIC. The QoS capable router and NIC designs are evaluated with a mixed workload consisting of best-effort traffic, multimedia streams, and control traffic.

Simulation results of an 8-port router and a
(2 × 2)
mesh network indicate that the preemptive router can provide better performance than the non-preemptive router for dynamically changing workloads. Co-evaluation of the QoS-aware NIC with the proposed router models shows significant performance improvement compared to that with a traditional NIC without any QoS support.
Dead-block prediction & dead-block correlating prefetchers
Authors: Lai An-Chow , Fide Cem , Falsafi Babak
Published: July 2004

Effective data prefetching requires accurate mechanisms to predict both “which” cache blocks to prefetch and “when” to prefetch them. This paper proposes the
Dead-Block Predictors (DBPs),
trace-based predictors that accurately identify “when” an Ll data cache block becomes evictable or “dead”. Predicting a dead block significantly enhances prefetching lookahead and opportunity, and enables placing data directly into Ll, obviating the need for auxiliary prefetch buffers. This paper also proposes
Dead-Block Correlating Prefetchers (DBCPs),
that use address correlation to predict “which” subsequent block to prefetch when a block becomes evictable. A DBCP enables effective data prefetching in a wide spectrum of pointer-intensive, integer, and floating-point applications.

We use cycle-accurate simulation of an out-of-order superscalar processor and memory-intensive benchmarks to show that: (1) dead-block prediction enhances prefetching lookahead at least by an order of magnitude as compared to previous techniques, (2) a DBP can predict dead blocks on average with a coverage of 90% only mispredicting 4% of the time, (3) a DBCP offers an address prediction coverage of 86% only mispredicting 3% of the time, and (4) DBCPs improve performance by 62% on average and 282% at best in the benchmarks we studied.
Exploring and exploiting wire-level pipelining in emerging technologies
Authors: Niemier Michael Thaddeus , Kogge Peter M.
Published: July 2004

Pipelining is a technique that has long since been considered fundamental by computer architects. However, the world of nanoelectronics is pushing the idea of pipelining to new and lower levels — particularly the device level. How this affects circuits and the relationship between their timing, architecture, and design will be studied in the context of an inherently self-latching nanotechnology termed Quantum Cellular Automata (QCA). Results indicate that this nanotechnology offers the potential for “
free
” multi-threading and “processing-in-wire”. All of this could be accomplished in a technology that could be almost three orders of magnitude denser than an equivalent design fabricated in a process at the end of the CMOS curve.
A simple method for extracting models for protocol code
Authors: Lie David , Chou Andy , Engler Dawson , Dill David L.
Published: July 2004

The use of model checking for validation requires that models of the underlying system be created. Creating such models is both difficult and error prone and as a result, verification is rarely used despite its advantages. In this paper, we present a method for automatically extracting models from low level software implementations. Our method is based on the use of an extensible compiler system
, xg++,
to perform the extraction. The extracted model is combined with a model of the hardware, a description of correctness, and an initial state. The whole model is then checked with the
Murφ
model checker. As a case study, we apply our method to the cache coherence protocols of the Stanford FLASH multiprocessor. Our system has a number of advantages. First, it reduces the cost of creating models, which allows model checking to be used more frequently. Second, it increases the effectiveness of model checking since the automatically extracted models are more accurate and faithful to the underlying implementation. We found a total of 8 errors using our system. Two errors were global resource errors, which would be difficult to find through any other means. We feel the approach is applicable to other low level systems.
Removing architectural bottlenecks to the scalability of speculative parallelization
Authors: Prvulovic Milos , Garzarán María Jesús , Rauchwerger Lawrence , Torrellas Josep
Published: July 2004

Speculative thread-level parallelization is a promising way to speed up codes that compilers fail to parallelize. While several speculative parallelization schemes have been proposed for different machine sizes and types of codes, the results so far show that it is hard to deliver scalable speedups. Often, the problem is not true dependence violations, but sub-optimal architectural design. Consequently, we attempt to identify and eliminate major architectural bottlenecks that limit the scalability of speculative parallelization. The solutions that we propose are: low-complexity commit in constant time to eliminate the task commit bottleneck, a memory-based overflow area to eliminate stall due to speculative buffer overflow, and exploiting high-level access patterns to minimize speculation-induced traffic. To show that the resulting system is truly scalable, we perform simulations with up to 128 processors. With our optimizations, the speedups for 128 and 64 processors reach 63 and 48, respectively. The average speedup for 64 processors is 32, nearly four times higher than without our optimizations.
Power and energy reduction via pipeline balancing
Authors: Bahar R. Iris , Manne Srilatha
Published: July 2004

Minimizing power dissipation is an important design requirement for both portable and non-portable systems. In this work, we propose an architectural solution to the power problem that retains performance while reducing power. The technique, known as
Pipeline Balancing (PLB),
dynamically tunes the resources of a general purpose processor to the needs of the program by monitoring performance within each program. We analyze metrics for triggering
PLB,
and detail instruction queue design and energy savings based on an extension of the Alpha 21264 processor. Using a detailed simulator, we present component and full chip power and energy savings for single and multi-threaded execution. Results show an issue queue and execution unit power reduction of up to 23% and 13%, respectively, with an average performance loss of 1% to 2%
.