Practical cache replacement policies attempt to emulate optimal replacement by predicting the re-reference interval of a cache block. The commonly used LRU replacement policy always predicts a near-immediate re-reference interval on cache hits and misses. Applications that exhibit a distant re-reference interval perform badly under LRU. Such applications usually have a working-set larger than the cache or have frequent bursts of references to non-temporal data (called scans). To improve the performance of such workloads, this paper proposes cache replacement using Re-reference Interval Prediction (RRIP). We propose Static RRIP (SRRIP) that is scan-resistant and Dynamic RRIP (DRRIP) that is both scan-resistant and thrash-resistant. Both RRIP policies require only 2-bits per cache block and easily integrate into existing LRU approximations found in modern processors. Our evaluations using PC games, multimedia, server and SPEC CPU2006 workloads on a single-core processor with a 2MB last-level cache (LLC) show that both SRRIP and DRRIP outperform LRU replacement on the throughput metric by an average of 4% and 10% respectively. Our evaluations with over 1000 multi-programmed workloads on a 4-core CMP with an 8MB shared LLC show that SRRIP and DRRIP outperform LRU replacement on the throughput metric by an average of 7% and 9% respectively. We also show that RRIP outperforms LFU, the state-of the art scan-resistant replacement algorithm to-date. For the cache configurations under study, RRIP requires 2X less hardware than LRU and 2.5X less hardware than LFU.

Conjugate gradient (CG) is one of the most popular iterative approaches to solving large sparse linear systems of equations. This work reports a parallel implementation of CG on clusters with EARTH multithreaded runtime support. Interphase and intraphase communication costs are balanced using a two-dimensional blocking method, minimizing overall communication costs. EARTH'S adaptive, event-driven multithreaded execution model gives additional opportunities to overlap communication and computation to achieve even better scalability. Experiments on a large Beowulf cluster with gigabit Ethernet show notable improvements over other parallel CG implementations. For example, with the NAS CG benchmark problem size Class C, our implementation achieved a speedup of 41 on a 64-node cluster, compared to 13 for the MPl-based NAS version. The results demonstrate that the combination of the two-dimensional blocking method and the EARTH architectural runtime support helps to compensate for the low communications bandwidth common to most clusters.

The drastic increase in power consumption by modern processors emphasizes the need for power-performance trade-offs in architecture design space exploration and compiler optimizations. This paper reports a quantitative study on the power-performance trade-offs in software pipelined schedules for an Itanium-like EPIC architecture with dual-speed pipelines, in which functional units are partitioned into fast ones and slow ones. We have developed an integer linear programming formulation to capture the power-performance tradeoffs for software pipelined loops. The proposed integer linear programming formulation and its solution method have been implemented and tested on a set of SPEC2000 benchmarks. The results are compared with an Itanium-like architecture (baseline) in which there are four functional units (FUs) and all of them are fast units. Our quantitative study reveals that by introducing a few slow FUs in place of fast FUs in the baseline architecture, the total energy consumed by FUs can be considerably reduced. When 2 out of 4 FUs are set as slow, the total energy consumed by FUs is reduced by up to 31.1% (with an average reduction of 25.2%) compared with the baseline configuration, while the performance degradation caused by using slow FUs is small. If performance demand is less critical, then energy reduction of up to 40.3% compared with the baseline configuration can be achieved.

Abstract This paper reports a study of sparse Matrix Vector Multiplication (MVM) on a parallel computing platform based on a fine‐grained multithreaded program execution model. Such sparse MVM computations, when parallelized without performing graph partitioning, suffers a very high communication to computation ratio, and is well known to have a very limited scalability on traditional distributed‐memory machines. The particular multithreaded system we use is the Efficient Architecture for Running THreads (EARTH) model, which can be implemented from off‐the‐shelf processors. With the Class B input sparse matrix from the NAS CG benchmark (75 000 rows), we attain an absolute speedup of 90 on 120 nodes of a distributed memory configuration. This is achieved without using inspector/executor or graph partitioning, or any communication minimization phase, which means that similar results can be expected for adaptive problems as well. High scalability is achieved because of a number of characteristics of the EARTH architecture: local synchronizations, low communication overheads, ability to overlap communication and computation, and low context‐switching costs. Copyright © 2002 John Wiley & Sons, Ltd.

We report on our work in developing a fine-grained multithreaded solution for the communication-intensive Conjugate Gradient (CG) problem. In our recent work, we developed a simple yet efficient program for sparse matrix-vector multiply on a multi-threaded system. This paper presents an effective mechanism for the reduction-broadcast phase, which is integrated with the sparse MVM, resulting in a scalable implementation of the complete CG application. Three major observations from our experiments on the EARTH multithreaded testbed are: (1) The scalability of our CG implementation is impressive, e.g., absolute speedup is 90 on 120 processors for the NAS CG class B input. (2) Our dataflow-style reduction-broadcast network based on fine-grain multithreading is twice as fast as a serial reduction scheme on the same system. (3) By slowing down the network by a factor of 2, no notable degradation of overall CG performance was observed.

In this paper we present fine-grained multithreaded algorithms and implementations for the Fast Fourier Transform (FFT) problem. The FFT problem has been formulated using two distinct approaches based on the dataflow concepts. The first approach, referred to as the receiver-initiated algorithm, realizes the FFAT iterations as a parent-child relationship while fully exploiting the underlying parallelism. The second approach, referred to as the sender-initiated algorithm, follows a data-flow model based on the producer-consumer style of programming and can be adopted to different architectural parameters for achieving high performance. The implementations of the proposed algorithms have been carried out on the EARTH (Efficient Architecture for Running THreads) platform. For both the algorithms, we analyze the ratio of remote vs local threads and study its impact on the experimental results. Our implementation results show that for certain block sizes on fixed problem size and machine size, the receiver-initiated approach performs better than the sender-initiated approach. For large number of processors, both the algorithms perform well, yielding execution times of only 10 msec for an input of 16 K data points on a 64 processor machine, assuming each processor running at 140 MHz clock speed.

Two-level dynamic branch predictors try to predict the outcomes of conditional branches using both a table of state counters associated with specific branch instructions and a buffer of recent branch outcomes to correlate the counters with specific branch histories. However there is always a question of how much correlation to use, and some programs benefit from higher levels of correlation than others. This paper presents the Elastic History Buffer (EHB), a low-cost yet effective scheme that can exploit the property that each branch instruction may have a different degree of correlation with other branches, while keeping the simple structure of a single global branch history. We have simulated the EHB on SPECint92 for two architectures. On average, the EHB has 25% fewer mispredictions than fixed-correlation schemes and 10% fewer than frequency-based branch classification schemes. With limited hardware (1KB), the EHB is close to the optimum measured by repeating the experiments on an "oracle" two-level predictor.

There has been considerable interest in implementing a multithreaded program execution and architecture model on a multiprocessor whose primary processors consist of today's off-the-shelf microprocessors. Unlike some custom-designed multithreaded processor architectures, which can interleave multiple threads concurrently, conventional processors can only execute one thread at a time. This presents a unique and challenging problem to the compiler: partition a program into threads so that it executes both correctly and in minimal time. We present a new heuristic algorithm based on an interesting extension of the classical list scheduling algorithm. Based on a cost model, our algorithm groups instructions into threads by considering the trade-offs among parallelism, latency tolerance, thread switching costs and sequential execution efficiency. The proposed algorithm has been implemented, and its performance measured through experiments on a variety of architecture parameters and a wide ra...

Multithreading has been promoted as an effective mechanism to hide inter-processor communications and remote data access latencies by quickly switching among a set of ready threads. In this paper, we show that multitreading provides an immunity to the performance variations due to changes in data distributions in a distributed-memory multiprocessor. First, toe propose two performance metrics to quantify the sensitivity of performance to data-locality. Second, we perform a quantitative comparison of data-locality sensitivity with both single-threaded and multithreaded computations. These experiments are performed on a 20-node EARTH-MANNA system. Our results show that not only does a multithreaded computation yields higher performance than the single-threaded version, but also that its performance is more robust (less affected) by variations in data-locality.

Parallel systems supporting multithreading, or message passing in general, have typically used either polling or interrupts to handle incoming messages. Neither approach is ideal; either may lead to excessive overheads or message-handling latencies, depending on the application. This paper investigates a combined approach---Polling Watchdog, where both are used depending on the circumstances. The Polling Watchdog is a simple hardware extension that limits the generation of interrupts to the cases where explicit polling fails to handle the message quickly. As an added benefit, this mechanism also has the potential to simplify the interaction between interrupts and the network accesses performed by the program.We present the resulting performance for the EARTH-MANNA-S system, an implementation of the EARTH (Efficient Architecture for Running THreads) execution model on the MANNA multiprocessor. In contrast to the original EARTH-MANNA system, this system does not use a dedicated communication processor. Rather, synchronization and communication tasks are performed on the same processor as the regular computations. Therefore, an efficient message-handling mechanism is essential to good performance. Simulation results and performance measurements show that the Polling Watchdog indeed performs better than either polling or interrupts alone. In fact, this mechanism allows the EARTH-MANNA-S system to achieve the same level of performance as the original EARTH-MANNA multithreaded system.

Large-scale multiprocessors require an efficient interconnection network to achieve good performance. This network, like the rest of the system, should be fault-tolerant (able to continue operating even when there are hardware failures). This paper presents the W-Network, a low-cost fault-tolerant MIN which is well-suited to a large multiprocessor running fine-grain parallel programs. It tolerates all single faults without any increases in latency or decreases in band-width following a fault, because it behaves just like the fault-free network even when there is a single fault. It requires only one extra port per chip, which makes it practical for a VLSI implementation. In addition, extra ports can be added for replacing faulty processors with spares.

High-speed microprocessors need fast on-chip caches in order to keep busy. Direct-mapped caches have better access times than set-associative caches, but poorer miss rates. This has led to several hybrid on-chip caches combining the speed of direct-mapped caches with the hit rates of associative caches. In this paper, we unify these hybrids within a single framework which we call the hybrid access cache (HAC) model. Existing hybrid caches lie near the edges of the HAC design space, leaving the middle untouched. We study a group of caches in this middle region, a group we call half-and-half caches, which are half direct-mapped and half set-associative. Simulations confirm the predictive valve of the HAC model, and demonstrate that, for medium to large caches, this middle region yields more efficient cache designs.>

Several recent studies on the limits of parallelism have reported that speculative execution can substantially increase the amount of exploitable parallelism in programs, especially non-numerical programs. This is true even for parallel machines models which allow multiple flows of control. However, most architectural techniques for speculation and branch prediction are geared toward conventional computers with a single flow of control, and little has been done in studying speculation models and techniques for parallel machines with multiple threads of control.

ing with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or ([email protected]). An Efficient Parallel Algorithm for All Pairs Examination Kevin B. Theobald Guang R. Gao School of Computer Science School of Computer Science McGill University McGill University Montr'eal, Qu'ebec H3A 2A7 Montr'eal, Qu'ebec H3A 2A7 [email protected] [email protected] Abstract This paper presents a parallel algorithm for the All Pairs Examination problem, which appears in many applications. This algorithm examines all pairs in a set of n 2 elements on n processors in n+1 computation steps. Each element resides in only one processor during each step. This method uses processor time optimally and requires fewer communication steps than previous algorithms, with minimal network traffic and low run-time overhead. The most ...