bluuebunny/crossref_metadata_2025 huggingface dataset:
Impact of sharing-based thread placement on multithreaded architectures
Authors: Thekkath R. , Eggers S. J.
Published: July 2004

Multithreaded architectures context switch between instruction streams to hide memory access latency. Although this improves processor utilization, it can increase cache interference and degrade overall performance. One technique to reduce the interconnect traffic is to co-locate threads that share data on the same processor. Multiple threads sharing in the cache should reduce compulsory and invalidation misses, thereby improving execution time.To test this hypothesis, we compared a variety of thread placement algorithms via trace-driven simulation of fourteen coarse- and medium-grain parallel applications on several multithreaded architectures. Our results contradict the hypothesis. Rather than decreasing, compulsory and invalidation misses remained nearly constant across all placement algorithms, for all processor configurations, even with an infinite cache. That is, sharing-based placement had no (positive) effect on execution time. Instead, load balancing was the critical factor that affected performance. Our results were due to one or both of the following reasons: (1) the sequential and uniform access of shared data by the application's threads and (2) the insignificant number of data references that require interconnect access, relative to the total number of instructions.
Combined performance gains of simple cache protocol extensions
Authors: Dahlgren F. , Dubois M. , Stenström P.
Published: July 2004

We consider three simple extensions to directory-based cache coherence protocols in shared-memory multiprocessors. These extensions are aimed at reducing the penalties associated with memory accesses and include a hardware prefetching scheme, a migratory sharing optimization, and a competitive-update mechanism. Since they target different components of the read and write penalties, they can be combined effectively.Detailed architectural simulations using five benchmarks show substantial combined performance gains obtained at a modest additional hardware cost. Prefetching in combination with competitive-update is the best combination under release consistency in systems with sufficient network bandwidth. By contrast, prefetching plus the migratory sharing optimization is advantageous under sequential consistency and/or in systems with limited network bandwidth.
A performance study of software and hardware data prefetching schemes
Authors: Chen T.-F. , Baer J.-L.
Published: July 2004

Prefetching, i.e., exploiting the overlap of processor computations with data accesses, is one of several approaches for tolerating memory latencies. Prefetching can be either hardware-based or software-directed or a combination of both. Hardware-based prefetching, requiring some support unit connected to the cache, can dynamically handle prefetches at run-time without compiler intervention. Software-directed approaches rely on compiler technology to insert explicit prefetch instructions. Mowry et al.'s software scheme [13, 14] and our hardware approach [1] are two representative schemes.In this paper, we evaluate approximations to these two schemes in the context of a shared-memory multiprocessor environment. Our qualitative comparisons indicate that both schemes are able to reduce cache misses in the domain of linear array references. When complex data access patterns are considered, the software approach has compile-time information to perform sophisticated prefetching whereas the hardware scheme has the advantage of manipulating dynamic information. The performance results from an instruction-level simulation of four benchmarks confirm these observations. Our simulations show that the hardware scheme introduces more memory traffic into the network and that the software scheme introduces a non-negligible instruction execution overhead. An approach combining software and hardware schemes is proposed; it shows promise in reducing the memory latency with least overhead.
RAID-II
Authors: Drapeau A. L. , Shirriff K. W. , Hartman J. H. , Miller E. L. , Seshan S. , Katz R. H. , Lutz K. , Patterson D. A. , Lee E. K. , Chen P. M. , Gibson G. A.
Published: July 2004

In 1989, the RAID (Redundant Arrays of Inexpensive Disks) group at U. C. Berkeley built a prototype disk array called RAID-I. The bandwidth delivered to clients by RAID-I was severely limited by the memory system bandwidth of the disk array' s host workstation. We designed our second prototype, RAID-H, to deliver more of the disk array bandwidth to file server clients. A custom-built crossbar memory system called the XBUS board connects the disks directly to the high-speed network, allowing data for large requests to bypass the server workstation. RAID-II runs Log-Structured File System (LFS) software to optimize performance for bandwidth-intensive applications.The RAID-II hardware with a single XBUS controller board delivers 20 megabytes/second for large, random read operations and up to 31 megabytes/second for sequential read operations. A preliminary implementation of LFS on RAID-II delivers 21 megabytes/second on large read requests and 15 megabytes/second on large write operations.
EVENODD
Authors: Blaum M. , Brady J. , Bruck J. , Menon J.
Published: July 2004

We present a novel method, that we call EVENODD, for tolerating up to two disk failures in RAID architectures. EVENODD is the first known scheme for tolerating double disk failures that is optimal with regard to both storage and performance. EVENODD employs the addition of only two redundant disks and consists of simple exclusive-OR computations. A major advantage of EVENODD is that it only requires parity hardware, which is typically present in standard RAID-5 controllers. Hence, EVENODD can be implemented on standard RAID-5 controllers without any hardware changes. The only previously known scheme that employes optimal redundant storage (i.e. two extra disks) is based on Reed-Solomon (RS) error-correcting codes, requires computation over finite fields and results in a more complex implementation. For example, we show that the number of exclusive-OR operations involved in implementing EVENODD in a disk array with 15 disks is about 50% of the number required when using the RS scheme.
Compressionless routing
Authors: Kim J. H. , Liu Z. , Chien A. A.
Published: July 2004

Compressionless Routing (GR) is a new adaptive routing framework which provides a unified framework for efficient deadlock-free adaptive routing and fault-tolerance. CR exploits the tight-coupling between wormhole routers for flow control to detect potential deadlock situations and recover from them. Fault-tolerant Compressionless Routing (FCR) extends Compressionless Routing to support end-to-end fault-tolerant delivery. Detailed routing algorithms, implementation complexity and performance simulation results for CR and FCR are presented.CR has the following advantages: deadlock-free adaptive routing in torus networks with no virtual channels, simple router designs, order-preserving message transmission, applicability to a wide variety of network topologies, and elimination of the need for buffer allocation messages. FCR has the following advantages: tolerates transient faults while maintaining data integrity (nonstop fault-tolerance), tolerates permanent faults, can be applied to a wide variety of network topologies, and eliminates the need for software buffering and retry for reliability. These advantages of CR and FCR not only simplify hardware support for adaptive routing and fault-tolerance, they also can simplify communication software layers.
Expected I-cache miss rates via the gap model
Authors: Quong R. W.
Published: July 2004

To evaluate the performance of a memory system, computer architects must determine the miss rate m of a cache C when running program P. Typically, the measured miss rate depends on the specific address mapping M of P set arbitrarily by the compiler and linker. In this paper, we remove the effect of the address-mapping on the miss rate by analyzing a symbolic trace T of basic blocks. By assuming each basic block has an equal probability of ending up anywhere in the address map, we determine the expected miss rate averaged over all possible address mappings.Our resulting gap model gives the expected miss rate for instruction caches of varying cache size, line size, and set associativity. Our model is simple but robust, and turns out to be the familiar LRU stack model with a statistical viewpoint. Our model allows a trace of arbitrary length to be compactly summarized in a few thousand bytes of information. Our model also predicts how an intervening trace, such as an operating system call or a task switch, will affect the miss rate. Comparisons to measured miss rates from SPEC 92 instruction traces show that our model typically has relative differences of less than 20% for a variety of cache parameters.
Decoupled sectored caches
Authors: Seznec A.
Published: July 2004

Sectored caches have been used for many years in order to reconcile low tag array size and small or medium block size. In a sectored cache, a single address tag is associated with a sector consisting on several cache lines, while validity, dirty and coherency tags are associated with each of the inner cache lines.Maintaining a low tag array size is a major issue in many cache designs (e.g. L2 caches). Using a sectored cache is a design trade-off between a low size of the tag array which is possible with large line size and a low memory traffic which requires a small line size.This technique has been used in many cache designs including small on-chip microprocessor caches and large external second level caches. Unfortunately, as on some applications, the miss ratio on a sectored cache is significantly higher than the miss ratio on a non-sectored cache (factors higher than two are commonly observed), a significant part of the potential performance may be wasted in miss penalties.Usually in a cache, a cache line location is statically linked to one and only one address tag word location. In the decoupled sectored cache we introduce in this paper, this monolithic association is broken; the address tag location associated with a cache line location is dynamically chosen at fetch time among several possible locations.The tag volume on a decoupled sectored cache is in the same range as the tag volume in a traditional sectored cache; but the hit ratio on a decoupled sectored cache is very close to the hit ratio on a non-sectored cache. A decoupled sectored cache will allow the same level of performance as a non-sectored cache, but at a significantly lower hardware cost.
History cache
Authors: Sosič Rok
Published: July 2004

Reverse execution provides access to old states of an executing process. An application of reverse execution can be found in program debugging. When an error is detected, its cause is often hidden in the history of the process. In such situations, it is important to be able to recover and examine past states of the process. Numerous other applications of reverse execution are found in programming environments, in fault-tolerant computing and in speculative computation.Since processes are in general irreversible, the history must be saved in order to provide reverse execution. The main problem in dealing with the history is the amount of data generated. This paper describes a new approach to reverse execution based on a
history cache
which compacts the history. The performance of the history cache is measured on a simulator. The history cache can compact the history by more than an order of magnitude. Efficient support for reverse execution enables many new techniques such as a generic undo operation, a real-time checkpoint, and fast backtracking.
lnternet Nuggets
Authors: Thorson Mark
Published: July 2004

This column consists of selected traffic from the
comp.arch
newsgroup, a forum for discussion of computer architecture on Internet---an international computer network.
Throughput in a counterflow pipeline processor
Authors: Severson Aimee , Nelson Brent
Published: July 2004

The Counterflow Pipeline Processor, or CFPP, is a unique form of pipelined RISC architecture whose goal is to obtain regular and modular performance from a bi-directional pipeline. In this pipeline, instructions and results move in opposite directions in a counterflow fashion. A basic synchronous model of the CFPP was created and used to study configuration options which affect the flow of instructions and results through the pipeline. These options, which varied instruction execution, pipeline movement arbitration, and result movements, were varied in order to find the configuration which maximized throughput for a set of benchmarks.
Vector prefetching
Authors: Gschwind Michael K. , Pietsch Thomas J.
Published: July 2004

This paper focuses on extending the memory subsystem by integrating a prefetch buffer mechanism. Prefetching allows high-level application knowledge to increase memory performance, which is currently constraining the performance of most system. While prefetching does not reduce the latency of memory accesses, it hides this latency by overlapping memory access and instruction execution.

The first prefetch operation to the buffer is initiated by an explicit fetch instruction. All further prefetch operations are issued automatically whenever a prefetched value is consumed. To efficiently support list and vector processing, the user can specify a stride value at the time the first prefetch operation is initiated.
Object-oriented computer architectures for new generation of applications
Authors: Karne Ramesh K.
Published: July 2004

Since the inception of von-Neumann architecture for computer design, there has been no new paradigms or revolutions in computer architectures. Computer applications have been increasing at an exponential rate, however, the basic computer architectures remained the same. The conventional computer architectures, which are based on primitive building blocks including arithmetic logic units, floating point processor units, logical shift units, and register file units created tremendous
semantic-gap
and inefficiencies in information system processing. It is about time to revisit the standard von-Neumann computation model and argue about its efficiencies, as we are entering into a new era of information processing where applications don't have any boundaries in computation, communication, and information storage.

In this paper, we propose a revolutionary computer architecture which avoids the
semantic-gap
and inefficiencies, and is based on an object-oriented paradigm to provide the benefits of abstraction, inheritance, hierarchy, modularity, extensibility, and polymorphism. We will describe the fundamental building blocks for this architecture and propose a possible approach for implementing these new generation of computers which will not make software and hardware obsolete before coming to existence. We will present the design issues related to such architectures and research directions needed to study the feasibility of these architectures.
A trace-driven simulation methodology
Authors: Khalid Humayun
Published: July 2004

This paper presents a simulation methodology for evaluating the performance of CISC computers. The method is called Message Flow Technique (MFT). MFT has several advantages over Instruction Flow Technique (IFT) we presented in [1]. The proposed methodology is applied to a single and two-level cache CISC system using 80486 SX as a case study. It was found that with a single-level on-chip cache of size 8K, the performance of the system is considerably limited by the service time of BIU(Bus Interface Unit). The average service time of BIU, per instruction, was found to be around 1.0135 microseconds for our Modified Gibson Mix (MGM). With a second-level external cache of sizes 16K, 32K, 64K, and 128K the average performance improvements were found to be 1.4%, 18.6%, 39% and 53% respectively. The methodology presented here is an efficient and easy to use tool that could help performance analysts in evaluating computer systems.
Performance modeling using the Motorola PowerPC timing simulator
Authors: Afzal Tariq
Published: July 2004

Published and projected benchmark numbers do not necessarily help predict the behavior of a user application on a particular microprocessor system. The real test comes when a user application is executed and timed on the microprocessor[5], which usually stresses the system in a different fashion than most benchmarks do. Unfortunately, the lack of stable platforms in earlier stages of system design prevents a developer from performing such evaluation tasks. This paper illustrates how application developers looking for a head start can use the Motorola Timing Simulator for the PowerPC 603™ microprocessor to analyze the expected behavior of a user program for various memory subsystems and gather fairly accurate timing information. A study of some SPEC™ benchmarks is also done in this respect.
Airdisks and airRAID (expanded extract)
Authors: Jain Ravi , Werth John
Published: July 2004

A new generation of low-cost, low-power, and portable personal computer systems is emerging; sometimes these are referred to as palmtops or Personal Digital Assistants (PDAs). One of their key features is that they utilize wireless communication media, thus freeing the user from the constraints of wired or tethered communication. In fact, the wireless medium becomes a critical component of the I/O subsystem, allowing communication with fixed servers and other users. In particular, the broadcast nature of the wireless medium can be exploited to efficiently transmit information required by a large number of PDA users (e.g. stock quotes, sports updates, etc.), with software on the PDA being used to filter the information and present only the information of interest to the PDA user.We introduce a simple model, called the airdisk, for modeling the access of data transmitted periodically over wireless media as being analogous to the access of data from a standard magnetic disk. We consider several issues related to airdisks, such as their mean rotational latency under certain assumptions. The problem of scheduling the order in which data items are broadcast is analogous to that of determining how data should be laid out on the disk. Two problems of laying out data so as to minimize read time, given information about which data items are of most interest to the clients, are defined; both are shown to be NP-complete. We discuss ways in which the information about which items are of interest to clients can be obtained. Finally we consider how to increase the performance and storage capacity of airdisks, using the magnetic disk analogy as a guide. We suggest using multiple-track airdisks or borrowing the idea of Redundant Arrays of Inexpensive Disks (RAID) which is used for magnetic disks; for the wireless data broadcast environment we call the latter approach airRAID.
Efficient shared memory with minimal hardware support
Authors: Kontothanassis Leonidas I. , Scott Michael L.
Published: July 2004

Shared memory is widely regarded as a more intuitive model than message passing for the development of parallel programs. A shared memory model can be provided by hardware, software, or some combination of both. One of the most important problems to be solved in shared memory environments is that of cache coherence. Experience indicates, unsurprisingly, that hardware-coherent multiprocessors greatly outperform distributed shared-memory (DSM) emulations on message-passing hardware. Intermediate options, however, have received considerably less attention. We argue in this position paper that one such option---a multiprocessor or network that provides a global physical address space in which processors can make non-coherent accesses to remote memory without trapping into the kernel or interrupting remote processors---can provide most of the performance of hardware cache coherence at little more monetary or design cost than traditional DSM systems. To support this claim we have developed the
Cashmere
family of software coherence protocols for NCC-NUMA (Non-Cache-Coherent, Non-Uniform-Memory Access) systems, and have used execution-driven simulation to compare the performance of these protocols to that of full hardware coherence and distributed shared memory emulation. We have found that for a large class of applications the performance of NCC-NUMA multiprocessors rivals that of fully hardware-coherent designs, and significantly surpasses the performance realized on more traditional DSM systems.
The EM-X parallel computer
Authors: Kodama Yuetsu , Sakane Hirohumi , Sato Mitsuhisa , Yamana Hayato , Sakai Shuichi , Yamaguchi Yoshinori
Published: July 2004

Latency tolerance is essential in achieving high performance on parallel computers for remote function calls and fine-grained remote memory accesses. EM-X supports interprocessor communication on an execution pipeline with small and simple packets. It can create a packet in one cycle, and receive a packet from the network in the on-chip buffer without interruption. EM-X invokes threads on packet arrival, minimizing the overhead of thread switching. It can tolerate communication latency by using efficient multi-threading and optimizing packet flow of fine grain communication. EM-X also supports the synchronization of two operands, direct remote memory read/write operations and flexible packet scheduling with priority. This paper describes distinctive features of the EM-X architecture and reports the performance of small synthetic programs and larger more realistic programs.
The SPLASH-2 programs
Authors: Woo Steven Cameron , Ohara Moriyoshi , Torrie Evan , Singh Jaswinder Pal , Gupta Anoop
Published: July 2004

The SPLASH-2 suite of parallel applications has recently been released to facilitate the study of centralized and distributed shared-address-space multiprocessors. In this context, this paper has two goals. One is to quantitatively characterize the SPLASH-2 programs in terms of fundamental properties and architectural interactions that are important to understand them well. The properties we study include the computational load balance, communication to computation ratio and traffic needs, important working set sizes, and issues related to spatial locality, as well as how these properties scale with problem size and the number of processors. The other, related goal is methodological: to assist people who will use the programs in architectural evaluations to prune the space of application and machine parameters in an informed and meaningful way. For example, by characterizing the working sets of the applications, we describe which operating points in terms of cache size and problem size are representative of realistic situations, which are not, and which re redundant. Using SPLASH-2 as an example, we hope to convey the importance of understanding the interplay of problem size, number of processors, and working sets in designing experiments and interpreting their results.
S-connect
Authors: Nowatzyk Andreas G. , Browne Michael C. , Kelly Edmund J. , Parkin Michael
Published: July 2004

S-Connect is a new high speed, scalable interconnect system that has been developed to support networks of workstations to efficiently share computing resources. It uses off-the-shelf CMOS technology to directly drive fiber-optic systems at speeds greater than 1 Gbit/sec and can realize bisection bandwidths comparable to high-end MPP systems while being >10x more cost-effective. S-Connect systems do not rely on centralized switches, but rather are composed of adaptive, topology independent routing elements that are integrated into each node. The S-Connect routing algorithm is optimized for fine grained, irregular traffic and is designed to support high traffic loads, that can utilize most of the physically available bandwidth. Such traffic is typical of a distributed shared memory system, which is one of the intended applications. S-Connect innovations include a novel distributed phase locking method that allows global synchronization, HW support for multiple message priorities, in-band monitoring and control facilities, and a low overhead channel protocol that supports multiple in-transit messages on the same fiber.The first version of the S-Connect switching element has been successfully implemented in a commercial, 0.65 µm CMOS process.
Destage algorithms for disk arrays with non-volatile caches
Authors: Varma Anujan , Jacobson Quinn
Published: July 2004

In a disk array with a nonvolatile write cache, destages from the cache to the disk are performed in the background asynchronously while read requests from the host system are serviced in the foreground. In this paper, we study a number of algorithms for scheduling destages in a RAID-5 system. We introduce a new scheduling algorithm, called
linear threshold scheduling,
that adaptively varies the rate of destages to disks based on the instantaneous occupancy of the write cache. The performance of the algorithm is compared with that of a number of alternative scheduling approaches such as
least-cost scheduling
and
high/low mark.
The algorithms are evaluated in terms of their effectiveness in making destages transparent to the servicing of read requests from the host, disk utilization, and their ability to tolerate bursts in the workload without causing an overflow of the write cache. Our results show that linear threshold scheduling provides the best read performance of all the algorithms compared, while still maintaining a high degree of burst tolerance. An approximate implementation of the linear-threshold scheduling algorithm is also described. The approximate algorithm can be implemented with much lower overhead, yet its performance is virtually identical to that of the ideal algorithm.
Evaluating multi-port frame buffer designs for a mesh-connected multicomputer
Authors: Stoll Gordon , Wei Bin , Clark Douglas , Felten Edward W. , Li Kai , Hanrahan Patrick
Published: July 2004

Multicomputers can be effectively used for interactive graphics rendering only if there are mechanisms available to rapidly composite and transfer images to an external display device. One method for achieving the necessary bandwidth for this operation is to provide multiple high-bandwidth ports into a frame buffer. In this paper, we evaluate the design space of a multiport frame buffer design for the Intel Paragon mesh routing network. We use an instrumented rendering system to capture the graphics operations needed for rendering a number of three-dimensional scenes; we then use those workloads as input to test programs running on the Paragon to estimate the performance of our hardware. Our experiments consider three major design questions: how many network ports the frame buffer needs, whether Z-Buffering should be done in hardware on the frame buffer or in software on the computing nodes, and whether the design alternatives are scalable.
Are crossbars really dead?
Authors: Nowatzyk Andreas G. , Prucnal Paul R.
Published: July 2004

Crossbar switches are rarely considered for large, scalable multiprocessor interconnect systems because they require O(n
2
) switching elements, are difficult to control efficiently and are hard to implement once their size becomes too large to fit on one integrated circuit. However these problems are technology dependent and a recent innovation in fiber optic devices has led to a new implementation of crossbar switches that does not share these problems while retaining the full advantages of a crossbar switch: low latency, high throughput, complete connectivity and multi-cast capability. Moreover, this new technology has several characteristics that allow a distributed control system which scales linearly in the number of attached nodes.The innovation that led to this research is an optical and-gate that can be used to demultiplex multiple high speed data streams that are carried on one common optical medium. Optical time domain multiplexing can combine the data from many nodes and broadcast the result back to all nodes. This paper discusses OTDM technology only to the extent necessary to understand its characteristics and capabilities. The main contribution lies in the description and analysis of interconnect architectures that utilize OTDM to achieve a level performance that is beyond electronic means. It is expected that cost-reduced OTDM systems will become competitive with the next generation of interconnect systems.
Exploring configurations of functional units in an out-of-order superscalar processor
Authors: Jourdan Stéphan , Sainrat Pascal , Litaize Daniel
Published: July 2004

This study has been carried out in order to determine cost-effective configurations of functional units for multiple-issue out-of-order superscalar processors. The trace-driven simulations were performed on the six integer and the fourteen floating-point programs from the SPEC 92 suite. We first evaluate the number of instructions allowed to be concurrently processed by the execution stages of the pipeline. We then apply some restrictions on the execution issue of different instruction classes in order to define these configurations. We conclude that five to nine functional units are necessary to exploit Instruction-Level Parallelism. An important point is that several data cache ports are required in a processor of degree 4 or more. Finally, we report on complementary results on the utilization rate of the functional units.
Implementation trade-offs in using a restricted data flow architecture in a high performance RISC microprocessor
Authors: Simone M. , Essen A. , Ike A. , Krishnamoorthy A. , Maruyama T. , Patkar N. , Ramaswami M. , Shebanow M. , Thirumalaiswamy V. , Tovey D.
Published: July 2004

The implementation of a superscalar, speculative execution SPARC-V9 microprocessor incorporating Restricted Data Flow principles required many design trade-offs. Consideration was given to both performance and cost. Performance is largely a function of cycle time and instructions executed per cycle while cost is primarily a function of die area. Here we describe our Restricted Data Flow implementation and the means with which we arrived at its configuration. Future semiconductor technology advances will allow these trade-offs to be relaxed and higher performance Restricted Data Flow machines to be built.
An efficient, fully adaptive deadlock recovery scheme
Authors: Anjan K. V. , Pinkston Timothy Mark
Published: July 2004

This paper presents a simple, efficient and cost effective routing strategy that considers deadlock recovery as opposed to prevention. Performance is optimized in the absence of deadlocks by allowing maximum flexibility in routing. Disha supports true fully adaptive routing where all virtual channels at each node are available to packets without regard for deadlocks. Deadlock cycles, upon forming, are efficiently broken by progressively routing one of the blocked packets through a deadlock-free lane. This lane is implemented using a central "floating" deadlock buffer resource in routers which is accessible to all neighboring routers along the path. Simulations show that the Disha scheme results in superior performance and is extremely simple, ensuring quick recovery from deadlocks and enabling the design of fast routers.
Analysis and implementation of hybrid switching
Authors: Shin Kang G. , Daniel Stuart W.
Published: July 2004

The
switching
scheme of a point-to-point network determines how packets flow through each node, and is a primary element in determining the network's performance. In this paper, we present and evaluate a new switching scheme called
hybrid
switching. Hybrid switching dynamically combines both virtual cut-through and wormhole switching to provide higher achievable throughput than wormhole alone, while significantly reducing the buffer space required at intermediate nodes when compared to virtual cut-through. This scheme is motivated by a comparison of virtual cut-through and wormhole switching through cycle-level simulations, and then evaluated using the same methods. To show the feasibility of hybrid switching, as well as to provide a common base for simulating and implementing a variety of switching schemes, we have designed SPIDER, a communication adapter built around a custom ASIC, the
Programmable Routing Controller
(PRC).
NIFDY
Authors: Callahan Timothy , Goldstein Seth Copen
Published: July 2004

In this paper we present
NIFDY
, a network interface that uses admission control to reduce congestion and ensures that packets are received by a processor in the order in which they were sent, even if the underlying network delivers the packets out of order. The basic idea behind
NIFDY
is that each processor is allowed to have at most one outstanding packet to any other processor unless the destination processor has granted the sender the right to send multiple unacknowledged packets. Further, there is a low upper limit on the number of outstanding packets to all processors.We present results from simulations of a variety of networks (meshes, tori, butterflies, and fat trees) and traffic patterns to verify
NIFDY
's efficacy. Our simulations show that
NIFDY
increases throughput and decreases overhead. The utility of
NIFDY
increases as a network's bisection bandwidth decreases. When combined with the increased payload allowed by in-order delivery
NIFDY
increases total bandwidth delivered for all networks. The resources needed to implement
NIFDY
are small and constant with respect to network size.
Design of cache memories for multi-threaded dataflow architecture
Authors: Kavi Krishna M. , Hurson A. R. , Patadia Phenil , Abraham Elizabeth , Shanmugam Ponnarasu
Published: July 2004

Cache memories have proven their effectiveness in the von Neumann architecture when localities of reference govern the execution loci of programs. A pure dataflow program, in contrast, contains no locality of reference since the execution sequence is enforced only by the availability of arguments. Instruction locality may be enhanced if, dataflow programs are reordered. Enhancing the locality of data references in the dataflow architecture is a more challenging problem. In this paper we report our approaches to the design of instruction, data (operand) and I-Structure cache memories using the Explicit Token Store (ETS) model of dataflow systems. We will present the performance results obtained using various benchmark programs.
Skewed associativity enhances performance predictability
Authors: Bodin François , Seznec André
Published: July 2004

Performance tuning becomes harder as computer technology advances. One of the factors is the increasing complexity of memory hierarchies. Most modern machines now use at least one level of cache memory. To reduce execution stalls, cache misses must be very low. Software techniques used to improve locality have been developped for numerical codes, such as loop blocking and copying. Unfortunately, the behavior of direct mapped and set associative caches is still erratic when large numerical data is accessed. Execution time can vary drasticly for the same loop kernel depending on uncontrolled factors such as array leading size. The only software method available to improve execution time stability is the copying of frequently used data, which is costly in execution time. Users are not usually cache organisation experts. They are not aware of such phenomena, and have no control over it.In this paper, we show that the recently proposed four-way skewed associative cache yields very stable execution times and good average miss ratios on blocked algorithms. As a result, execution time is faster and much more predictable than with conventional caches. As a result of its better comportment, it is possible to use larger blocks sizes with blocked algorithms, which will furthermore reduces blocking overhead costs.
A comparative analysis of schemes for correlated branch prediction
Authors: Young Cliff , Gloy Nicolas , Smith Michael D.
Published: July 2004

Modern high-performance architectures require extremely accurate branch prediction to overcome the performance limitations of conditional branches. We present a framework that categorizes branch prediction schemes by the way in which they partition dynamic branches and by the kind of predictor that they use. The framework allows us to compare and contrast branch prediction schemes, and to analyze why they work. We use the framework to show how a static correlated branch prediction scheme increases branch bias and thus improves overall branch prediction accuracy. We also use the framework to identify the fundamental differences between static and dynamic correlated branch prediction schemes. This study shows that there is room to improve the prediction accuracy of existing branch prediction schemes.
Next cache line and set prediction
Authors: Calder Brad , Grunwald Dirk
Published: July 2004

Accurate instruction fetch and branch prediction is increasingly important on today's wide-issue architectures. Fetch prediction is the process of determining the next instruction to request from the memory subsystem. Branch prediction is the process of predicting the likely out-come of branch instructions. Several researchers have proposed very effective fetch and branch prediction mechanisms including branch target buffers (BTB) that store the target addresses of taken branches. An alternative approach fetches the instruction following a branch by using an index into the cache instead of a branch target address. We call such an index a
next cache line and set
(NLS) predictor. A NLS predictor is a pointer into the instruction cache, indicating the target instruction of a branch.In this paper we examine the use of NLS predictors for efficient and accurate fetch and branch prediction. Previous studies associated each NLS predictor with a cache line and provided only one-bit conditional branch predictors. Our study examines the use of NLS predictors with highly accurate two-level correlated conditional branch architectures. We examine the performance of decoupling the NLS predictors from the cache line and storing them in a separate tag-less memory buffer. Our results show that the decoupled architecture performs better than associating the NLS predictors with the cache line, that the NLS architecture benefits from reduced cache miss rates, and it is particularly effective for programs containing many branches. We also provide an in-depth comparison between the NLS and BTB architectures, showing that the NLS architecture is a competitive alternative to the BTB design.
Empirical evaluation of the CRAY-T3D
Authors: Arpaci Remzi H. , Culler David E. , Krishnamurthy Arvind , Steinberg Steve G. , Yelick Katherine
Published: July 2004

Most recent MPP systems employ a fast microprocessor surrounded by a shell of communication and synchronization logic. The CRAY-T3D provides an elaborate shell to support global-memory access, prefetch, atomic operations, barriers, and block transfers. We provide a detailed empirical performance characterization of these primitives using micro-benchmarks and evaluate their utility in compiling for a parallel language. We have found that the raw performance of the machine is quite impressive and the most effective forms of communication are prefetch and write. Other shell provisions, such as the bulk transfer engine and the external Annex register set, are cumbersome and of little use. By evaluating the system in the context of a language implementation, we shed light on important trade-offs and pitfalls in the machine architecture.
Streamlining data cache access with fast address calculation
Authors: Austin Todd M. , Pnevmatikatos Dionisios N. , Sohi Gurindar S.
Published: July 2004

For many programs, especially integer codes, untolerated load instruction latencies account for a significant portion of total execution time. In this paper, we present the design and evaluation of a fast address generation mechanism capable of eliminating the delays caused by effective address calculation for many loads and stores.Our approach works by predicting early in the pipeline (part of) the effective address of a memory access and using this predicted address to speculatively access the data cache. If the prediction is correct, the cache access is overlapped with non-speculative effective address calculation. Otherwise, the cache is accessed again in the following cycle, this time using the correct effective address. The impact on the cache access critical path is minimal; the prediction circuitry adds only a single OR operation before cache access can commence. In addition, verification of the predicted effective address is completely decoupled from the cache access critical path.Analyses of program reference behavior and subsequent performance analysis of this approach shows that this design is a good one, servicing enough accesses early enough to result in speedups for all the programs we tested. Our approach also responds well to software support, which can significantly reduce the number of mispredicted effective addresses, in many cases providing better program speedups and reducing cache bandwidth requirements.
CAT—caching address tags
Authors: Wang Hong , Sun Tong , Yang Qing
Published: July 2004

This paper presents a technique for minimizing chip-area cost of implementing an on-chip cache memory of microprocessors. The main idea of the technique
Caching Address Tags, or
CAT cache
for short. The
CAT
cache exploits locality property that exists among addresses of memory references for the purpose of minimizing chip area-cost of address tags. By keeping only a limited number of distinct tags of cached data rather than having as many tags as cache lines, the
CAT
cache can reduce the cost of implementing tag memory by an order of magnitude without noticeable performance difference from ordinary caches. Therefore,
CAT
represents another level of caching for cache memories. Simulation experiments are carried out to evaluate performance of
CAT
cache as compared to existing caches. Performance results of SPEC92 programs show that the
CAT
cache with only a few tag entries performs as well as ordinary caches while chip-area saving is significant. Such area saving will increase as the address space of a processor increases. By allocating the saved chip area for larger cache capacity, or more powerful functional units,
CAT
is expected to have a great impact on overall system performance.
Simultaneous multithreading
Authors: Tullsen Dean M. , Eggers Susan J. , Levy Henry M.
Published: July 2004

This paper examines
simultaneous multithreading,
a technique permitting several independent threads to issue instructions to a superscalar's multiple functional units in a single cycle. We present several models of simultaneous multithreading and compare them with alternative organizations: a wide superscalar, a fine-grain multithreaded processor, and single-chip, multiple-issue multiprocessing architectures. Our results show that both (single-threaded) superscalar and fine-grain multithreaded architectures are limited their ability to utilize the resources of a wide-issue processor. Simultaneous multithreading has the potential to achieve 4 times the throughput of a superscalar, and double that of fine-grain multithreading. We evaluate several cache configurations made possible by this type of organization and evaluate tradeoffs between them. We also show that simultaneous multithreading is an attractive alternative to single-chip multiprocessors; simultaneous multithreaded processors with a variety of organizations outperform corresponding conventional multiprocessors with similar execution resources.While simultaneous multithreading has excellent potential to increase processor utilization, it can add substantial complexity to the design. We examine many of these complexities and evaluate alternative organizations in the design space.
Architecture validation for processors
Authors: Ho Richard C. , Yang C. Han , Horowitz Mark A. , Dill David L.
Published: July 2004

Modem, high performance microprocessors are extremely complex machines which require substantial validation effort to ensure functional correctness prior to tapeout. Generating the corner cases to test these designs is a mostly manual process, where completion is hard to judge. Experience shows that the errors that are caught late in the design, many post-silicon, are interactions between different components in very improbable corner case situations. In this paper we present a technique that targets such error-causing interactions by automatically generat- ing test vectors that will cause the processor to exercise
all
transitions of the control logic in simulation. We use techniques from formal verification to derive transition tours of a fully enumerated state graph of the control logic of the processor. Our system works from a Verilog description of the original machine and is currently being used to validate an embedded dual-issue processor in the node controller of the Stanford FLASH Multiprocessor. Modeling the processor control results in 200K states and an 8M instruction trace to check all transitions of control arcs.
Multiscalar processors
Authors: Sohi Gurindar S. , Breach Scott E. , Vijaykumar T. N.
Published: July 2004

Multiscalar processors use a new, aggressive implementation paradigm for extracting large quantities of instruction level parallelism from ordinary high level language programs. A single program is divided into a collection of tasks by a combination of software and hardware. The tasks are distributed to a number of parallel processing units which reside within a processor complex. Each of these units fetches and executes instructions belonging to its assigned task. The appearance of a single logical register file is maintained with a copy in each parallel processing unit. Register results are dynamically routed among the many parallel processing units with the help of compiler-generated masks. Memory accesses may occur speculatively without knowledge of preceding loads or stores. Addresses are disambiguated dynamically, many in parallel, and processing waits only for true data dependences.This paper presents the philosophy of the multiscalar paradigm, the structure of multiscalar programs, and the hardware architecture of a multiscalar processor. The paper also discusses performance issues in the multiscalar model, and compares the multiscalar paradigm with other paradigms. Experimental results evaluating the performance of a sample of multiscalar organizations are also presented.
Efficient strategies for software-only protocols in shared-memory multiprocessors
Authors: Grahn Håkan , Stenström Per
Published: July 2004

The cost, complexity, and inflexibility of hardware-based directory protocols motivate us to study the performance implications of protocols that emulate directory management using software handlers executed on the compute processors. An important performance limitation of such software-only protocols is that software latency associated with directory management ends up on the critical memory access path for read miss transactions. We propose five strategies that support efficient data transfers in hardware whereas directory management is handled at a slower pace in the background by software handlers. Simulations show that this approach can remove the directory-management latency from the memory access path. Whereas the directory is managed in software, the hardware mechanisms must access the memory state in order to enable data transfers at a high speed. Overall, our strategies reach between 60% and 86% of the hardware-based protocol performance.