Modern microprocessor designs are becoming more vulnerable to transient faults leading to transient errors due to design trends mandating low supply voltage and reduced noise margins, shrinking feature sizes and increased transistor density for fast, low power circuits. Detecting and correcting transient errors in random logic in a processor core has become an important design goal and confronts design challenges such as input replication, error confinement and overheads minimization. Transactional Memory (TM) is a recent paradigm to improve the programmability and performance of parallel programs. TM has appeared in industry, providing hardware mechanisms for conflict detection and resolution, and checkpointing and rollback. In this paper, we leverage the features of Hardware TM (HTM) to provide processor cores with transient error detection and recovery at low hardware cost. We contribute to the current state of the art of dependable systems by proposing a novel microarchitecture.

Transactional Memory (TM) is no longer just an academic interest as industry has started to adopt the idea in its commercial products. In this paper, we propose Dynamic Transaction Issue (DTI), a new scheme that can be easily implemented on top of existing Hardware TM (HTM) systems, provided additional messages. Instead of wasting power and energy in transaction aborts, Dynamic Transaction Issue puts a processor core into a low-power state when there is a reasonable suspicion that the current transaction running on it will be aborted soon in the future. We have implemented Dynamic Transaction Issue on a cycle-accurate simulator of a multicore processor system with out-of-order superscalar cores, augmented with a power package and a TM package which add accurate dynamic power estimates and a TM framework to the simulator. Our simulation results show that Dynamic Transaction Issue can achieve energy savings up to 37% from the energy consumption of a base machine with no mechanism to suppress useless aborts. We also compare Dynamic Transaction Issue with various alternative hardware TM mechanisms.

To select an appropriate level of error protection in caches, the impact of various protection schemes on the cache Failure In Time (FIT) rate must be evaluated for a target benchmark suite. However, while many simulation tools exist to evaluate area, power and performance for a set of benchmark programs, there is a dearth of such tools for reliability. This paper introduces a new cache reliability model called PARMA+ that has unique features which distinguish it from previous models. PARMA+ estimates a cache's FIT rate in the presence of spatial multi-bit faults, single-bit faults, temporal multi-bit faults and different error protection schemes including parity, ECC, early write-back and bit-interleaving. We first develop the model formally, then we demonstrate its accuracy. We have run reliability simulations for many distributions of large and small fault patterns and have compared them with accelerated fault injection simulations. PARMA+ has high accuracy and low computational complexity.

Modern microprocessor cores reach their high performance levels with the help of high clock rates, parallel and speculative execution of a large number of instructions, and vast cache hierarchies. Modern cores also have adaptive features to regulate power and temperature and avoid thermal emergencies. All of these features contribute to highly unpredictable execution times. In this article, we demonstrate that the execution time of in-order (IO), out-of-order (OoO), and OoO simultaneous multithreaded processors can be stable and predictable by stabilizing their mega instructions executed per second (MIPS) rate via a proportional, integral, and differential (PID) gain feedback controller and dynamic voltage and frequency scaling (DVFS). Processor cores in idle cycles are continuously consuming power, which is highly undesirable in systems, especially in real-time systems. In addition to meeting deadlines in real-time systems, our MIPS rate stabilization framework can be applied on top of it to reduce power and energy by avoiding idle cycles. If processors are equipped with MIPS rate stabilization, the execution time can be predicted. Because the MIPS rate remains steady, a stabilized processor meets deadlines on time in real-time systems or in systems with quality-of-service execution latency requirements at the lowest possible frequency. To demonstrate and evaluate this capability, we have selected a subset of the MiBench benchmarks with the widest execution rate variations. We stabilize their MIPS rate on a 1GHz Pentium III--like OoO single-thread microarchitecture, a 1.32GHz StrongARM-like IO microarchitecture, and the 1GHz OoO processor augmented with two-way and four-way simultaneous multithreading. Both IO and OoO cores can take advantage of the stabilization framework, but the energy per instruction of the stabilized OoO core is less because it runs at a lower frequency to meet the same deadlines. The MIPS rate stabilization of complex processors using a PID feedback control loop is a general technique applicable to environments in which lower power or energy coupled with steady, predictable performance are desirable, although we target more specifically real-time systems in this article.

In future technology nodes, reliability is expected to become a first-order design constraint. Faults encountered in a chip can be classified into three categories: transient, intermittent, and permanent. Fault classification allows a chip to take the appropriate corrective action. Mechanisms have been proposed to distinguish transient from non-transient faults where all non-transient faults are handled as permanent. Intermittent faults induced by wearout phenomena have become the dominant reliability concern in nanoscale technology, yet there is no mechanism that provides finer classification of non-transient faults into intermittent and permanent faults. In this paper, we present a new class of exceptions called Reliability-Aware Exceptions (RAEs) which provide the ability to distinguish intermittent faults in microprocessor array structures. The RAE handlers have the ability to manipulate microprocessor array structures to recover from all three categories of faults. Using RAEs, we demonstrate that the reliability of two representative microarchitecture structures, load/store queue and reorder buffer in an out-of-order processor, is improved by average factors of 1.3 and 1.95, respectively.

Due to shrinking feature sizes, processors are becoming more vulnerable to soft errors. One of the most vulnerable components of a processor is its write-back cache. This paper proposes a new reliable write-back cache called Correctable Parity Protected Cache (CPPC), which adds correction capability to parity protection. In CPPC, parity bits detect faults and the XOR of all data written into the cache is kept to recover from detected faults. The added correction scheme provides a high degree of reliability and corrects both single and spatial multi-bit faults in exchange for very small performance and power overheads. CPPC is compared to competitive schemes. Our simulation data show that CPPC improves reliability significantly while its overheads are very small, especially in the L2 cache.

In this paper, we introduce PHYS (Profiled-HYbrid Sampling), a sampling framework for soft-error benchmarking of caches. Reliability simulations of caches are much more complex than performance simulations and therefore exhibit large simulation slowdowns (two orders of magnitude) over performance simulations. The major problem is that the reliability lifetime of every accessed block must be tracked from beginning to end, on top of simulating the benchmark, in order to track the total number of vulnerability cycles (VCs) between two accesses to the block. Because of the need to track SDCs (silent error corruption) and to distinguish between true and false DUEs (detected but unrecoverable errors) vulnerability cycles cannot be truncated when data is written back from cache to main memory. Vulnerability cycles must be maintained even during a block's sojourn in main memory to track whether corrupted values in a block are used by the processor, until program termination. PHYS solves this problem by sampling intervals between accesses to each memory block, instead of sampling the execution of the processor in a time interval as is classically done in performance simulations. At first a statistical profiling phase captures the distribution of VCs for every block. This profiling step provides a statistical guarantee of the minimum sampling rate of access intervals needed to meet a desired FIT error target with a given confidence interval. Then, per cacheset sampling rates are dynamically adjusted to sample VCs with higher merit. We compare PHYS with many other possible sampling methods, some of which are widely used to accelerate performance-centric simulations but have also been applied in the past to track reliability lifetime. We demonstrate the superiority of PHYS in the context of reliability benchmarking through exhaustive evaluations of various sampling techniques.

Due to the growing trend that a Single Event Upset (SEU) can cause spatial Multi-Bit Upsets (MBUs), the effects of spatial MBUs has recently become an important yet very challenging issue, especially in large, last-level caches (LLCs) protected by protection codes. In the presence of spatial MBUs, the strength of the protection codes becomes a critical design issue. Developing a reliability model that includes the cumulative effects of overlapping SBUs, temporal MBUs and spatial MBUs is a very challenging problem, especially when protection codes are active. In this paper, we introduce a new framework called MACAU. MACAU is based on a Markov chain model and can compute the intrinsic MTTFs of scrubbed caches as well as benchmark caches protected by various codes. MACAU is the first framework that quantifies the failure rates of caches due to the combined effects of SBUs, temporal MBUs and spatial MBUs.

Due to shrinking feature sizes processors are becoming more vulnerable to soft errors. Write-back caches are particularly vulnerable since they hold dirty data that do not exist in other memory levels. While conventional error correcting codes can protect write-back caches, it has been shown that they are expensive in terms of area and power. This paper proposes a reliable write-back cache called Correctable Parity Protected Cache (CPPC) which adds error correction capability to a parity-protected cache. For this purpose, CPPC augments a write-back parity-protected cache with two registers: the first register stores the XOR of all data written to the cache and the second register stores the XOR of all dirty data that are removed from the cache. CPPC relies on parity to detect a fault and then on the two XOR registers to correct faults. By a novel combination of byte shifting and parity interleaving CPPC corrects both single and spatial multi-bit faults to provide a high degree of reliability. We compare CPPC with one-dimensional parity, SECDED (Single Error Correction Double Error Detection) and two-dimensional parity-protected caches. Our experimental results show that CPPC provides a high level of reliability while its overheads are less than the overheads of SECDED and two-dimensional parity.

The amount of charge stored in an SRAM cell shrinks rapidly with each technology generation thus increasingly exposing caches to soft errors. Benchmarking the FIT rate of caches due to soft errors is critical to evaluate the relative merits of a plethora of protection schemes that are being proposed to protect against soft errors. The benchmarking of cache reliability introduces a unique challenge as compared to internal processor storage structures, such as the load/store queue. In the case of internal processor structures the time a data bit resides in the structure is so short that it is generally safe to assume that no more than one soft error strike can occur. Thus the reliability of such structures is overwhelmingly dominated by single bit errors. By contrast, a memory block may reside for millions of cycles in a last level cache. In this case it is important to consider the impact of the spatial and temporal distribution of multiple errors within the lifetime of a cache block in the presence of error protection.

Current trends signal an imminent crisis in the simulation of future CMPs (Chip Multiprocessors). Future micro-architectures will offer more and more thread contexts to execute parallel programs, but the execution speed of each thread will not improve at the same pace. CMPs with 10’s or even100’s of cores are envisioned. Simulating these future CMP sefficiently without compromising accuracy is a challenge. Slack simulation is a general parallel simulation paradigm which provides flexible trade-offs between simulation accuracy and speed. Simulation threads do not synchronize after every target core cycle as in cycle-by-cycle simulation. Rather a maximum slack (the slack bound) is enforced between the clocks of all simulated cores. A slack simulation may become inaccurate because of simulation violations. Such violations occur when a resource is accessed by two cores in different order in the simulation and in the target system. We introduce and demonstrate techniques to detect violations, to adapt the simulation slack to maintain a target violation rate, and to checkpoint and rollback a slack simulation when violations are detected. We show some simulation performance/accuracy data for a set of five Splash benchmarks in the context of an 8-core CMP with a snooping cache coherence protocol simulated on Slack Sim, our universal slack simulation platform.

Parallel simulation is a technique to accelerate microarchitecture simulation of CMPs by exploiting the inherent parallelism of CMPs. In this paper, we explore the simulation paradigm of simulating each core of a target CMP in one thread and then spreading the threads across the hardware thread contexts of a host CMP. We start with cycle-by-cycle simulation and then relax the synchronization condition in various schemes, which we call slack simulations. In slack simulations, the Pthreads simulating different simulated cores do not synchronize after each simulated cycle, but rather they are given some slack. The slack is the difference in cycle between the simulated times of any two target cores. Small slacks, such as a few cycles, greatly improve the efficiency of parallel CMP simulations, with no or negligible simulation error. We have developed a simulation framework called SlackSim to experiment with various slack simulation schemes. Unlike previous attempts to parallelize multiprocessor simulations on distributed memory machines, SlackSim takes advantage of the efficient sharing of data in the host CMP architecture. We demonstrate the efficiency and accuracy of some well-known slack simulation schemes and of some new ones on SlackSim running on a state-of-the-art CMP platform.

Today's microprocessor cores reach high performance levels not only by their high clock rate but also by the concurrent execution of a large number of instructions. Because of the relationship between power and frequency, it becomes attractive to run an OoO (Out-of-Order) core at a frequency lower than its nominal frequency in the context of embedded or real-time systems. Unfortunately, whereas OoO pipelines have high average throughput, their highly variable and hard-to-predict execution rate makes them unsuitable for real-time systems with hard or even soft deadlines. In this paper, we demonstrate that the execution time of an OoO processor can be stable and predictable by controlling its MIPS (Mega Instructions Per Second) rate via a PID (Proportional, Integral, and Differential gain) feedback controller and DVFS (Dynamic Voltage and Frequency Scaling). The stabilized processor uses much less power per committed instruction, because of the reduced average frequency. The EPI (Energy Per Instruction) is also cut by an average of 28% across our benchmark programs. Since a stable MIPS rate is maintained consistently with lower power/energy per instruction, OoO processors stabilized by a feedback controller can realistically be deployed in real-time systems. To demonstrate this capability we select a subset of the MiBench benchmarks that displays the widest execution rate variations and stabilize their MIPS rate in the context of a 1GHz Pentium III-like microarchitecture.

We propose a generic algorithmic model called STAMP (Synchronous, Transactional, and Asynchronous Multi- Processing) as a universal performance and power complexity model for multithreaded algorithms and systems. We provide examples to illustrate how to design and analyze algorithms using STAMP and how to apply the complexity estimates to better utilize CMP(Chip MultiProcessor)-based machines within given constraints such as power.

To support dynamic address translation in today's microprocessors, the first-level cache is accessed in parallel with a translation lookaside buffer (TLB). However, this current approach faces mounting problems. This paper introduces new ideas to enable the use of virtual addresses in the cache hierarchy. The major idea is the replacement of the on-chip TLB by a synonym lookaside buffer (SLB). The SLB translates synonyms into a primary virtual address, which is a unique identifier resolving all ambiguities due to synonyms in the memory system. We introduce various system configurations with SLBs and discuss all functional issues associated with them. An SLB is much more scalable than a regular TLB. It scales with memory data set sizes, physical memory sizes and number of cores in a multiprocessor. Moreover SLB entry flushes and shootdowns due to physical memory management are eliminated. We show performance data resulting from the simulation of several applications as diverse as scientific computing, database, and JAVA virtual machines. These evaluations target SLB miss rates and flushes as well as the impact of the SLB on cache miss rates. They show that small SLBs of 8-16 entries are sufficient to solve the synonym problem in virtual caches and that their performance overhead is negligible.

As multi-core microprocessors are becoming widely adopted, the need to extract thread-level parallelism (TLP) from single-threaded applications in a seamless fashion increases. In this paper, we characterize the nature of TLP in embedded applications and study the limits of performance speedup using parallelizing compilers on platforms with and without support for thread-level speculation. First and somewhat expected, only two out of ten applications from the consumer and telecom domains of the EEMBC suite could be automatically parallelized on multi-core architectures without thread-level speculation (TLS) support. We systematically study the speedup obtained by parallelizing compiler technologies by factoring in the impact of the number of cores, thread decomposition strategies, and thread-management overhead. Overall, we have found that a TLS substrate is critical to uncover thread level parallelism and thread- management overhead must be low. On an eight-way multi-core system, it is possible to achieve a speedup of four, on average, for six out of the ten applications of EEMBC which we have analyzed.

We propose a generic algorithmic model called STAMP(synchronous, transactional, and asynchronous multi-processing) as a universal performance and power complexity model for multithreaded algorithms and systems. We provide examples to illustrate how to design and analyze algorithms using STAMP and how to apply the complexity estimates to better utilize CMP(chip multiprocessor)-based machines within given constraints such as power.

Cache replacement algorithms originally developed in the context of uniprocessors executing one instruction at a time implicitly assume that all cache misses have the same cost. However, in modern systems, some cache misses are more expensive than others. The cost may be latency, penalty, power consumption, bandwidth consumption, or any other ad hoc numerical property attached to a miss. We call the class of replacement algorithms designed to minimize a nonuniform miss cost function "cost-sensitive replacement algorithms". In this paper, we first introduce and analyze an optimum cost-sensitive replacement algorithm (CSOPT) in the context of multiple nonuniform miss costs. CSOPT can significantly improve the cost function over OPT (the replacement algorithm minimizing miss count) in large regions of the design space. Although CSOPT is an offline and unrealizable replacement policy, it serves as a lower bound on the achievable cost by realistic cost-sensitive replacement algorithms. Using the practical example of latency cost in CC-NUMA multiprocessors, we demonstrate that there is a lot of room left to improve current replacement algorithms in many situations beyond the promise of OPT. Next, we introduce three practical extensions of LRU inspired by CSOPT and we compare their performance to LRU, OPT, and CSOPT. Finally, as a practical application, we evaluate these realizable cost-sensitive replacement algorithms in the context of the second-level caches of a CC-NUMA multiprocessor with superscalar processors, using the miss latency as the cost function. By applying simple replacement policies sensitive to the latency of misses, we can improve the execution time of some parallel applications by up to 18 percent.

To support a global virtual memory space, an architecture must translate virtual addresses dynamically. In current processors, the translation is done in a TLB (translation lookaside buffer), before or in parallel with the first-level cache access. As processor technology improves at a rapid pace and the working sets of new applications grow insatiably, the latency and bandwidth demands on the TLB are difficult to meet, especially in multiprocessor systems, which run larger applications and are plagued by the TLB consistency problem. We describe and compare five options for virtual address translation in the context of distributed shared memory (DSM) multiprocessors, including CC-NUMAs (cache-coherent non-uniform memory access architectures) and COMAs (cache only memory access architectures). In CC-NUMAs, moving the TLB to shared memory is a bad idea because page placement, migration, and replication are all constrained by the virtual page address, which greatly affects processor node access locality. In the context of COMAs, the allocation of pages to processor nodes is not as critical because memory blocks can dynamically migrate and replicate freely among nodes. As the address translation is done deeper in the memory hierarchy, the frequency of translations drops because of the filtering effect. We also observe that the TLB is very effective when it is merged with the shared-memory, because of the sharing and prefetching effects and because there is no need to maintain TLB consistency. Even if the effectiveness of the TLB merged with the shared memory is very high, we also show that the TLB can be removed in a system with address translation done in memory because the frequency of translations is very low.

In the past few years, exception support for memory functions such as virtual memory, informing memory operations, software assist for shared memory protocols, or interactions with processors in memory has been advocated in various research papers. These memory traps may occur on a miss in the cache hierarchy or on a local or remote memory access. However, contemporary, dynamically scheduled processors only support memory exceptions detected in the TLB associated with the first-level cache. They do not support memory exceptions taken deep in the memory hierarchy. In this case, memory traps may be late, in the sense that the exception condition may still be undecided when a long-latency memory instruction reaches the retirement stage. In this paper we evaluate through simulation the overhead of memory traps in dynamically scheduled processors, focusing on the added overhead incurred when a memory trap is late. We also propose some simple mechanisms to reduce this added overhead while preserving the memory consistency model. With more aggressive memory access mechanisms in the processor we observe that the overhead of all memory traps - either early or late - is increased while the lateness of a trap becomes largely tolerated so that the performance gap between early and late memory traps is greatly reduced. Additionally, because of caching effects in the memory hierarchy, the frequency of memory traps usually decreases as they are taken deeper in the memory hierarchy and their overall impact on execution times becomes negligible. We conclude that support for memory traps taken throughout the memory hierarchy could be added to dynamically scheduled processors at low hardware cost and little performance degradation.

Cache replacement algorithms originally developed in the context of simple uniprocessor systems aim to reduce the miss count. However, in modern systems, cache misses have different costs. The cost may be latency, penalty, power consumption, bandwidth consumption, or any other ad-hoc numerical property attached to a miss. In many practical situations, it is desirable to inject the cost of a miss into the replacement policy. In this paper, we propose several extensions of LRU which account for nonuniform miss costs. These LRU extensions have simple implementations, yet they are very effective in various situations. We first explore the simple case of two static miss costs using trace-driven simulations to understand when cost-sensitive replacements are effective. We show that very large improvements of the cost function are possible in many practical cases. As an example of their effectiveness, we apply the algorithms to the second-level cache of a multiprocessor with superscalar processors, using the miss latency as the cost function. By applying our simple replacement policies sensitive to the latency of misses we can improve the execution time of some parallel applications by up to 18%.

Evaluating architectural impact of applications with a significant operating system interaction calls for integrating detailed microarchitectural user-level simulation with system-level simulation tools. This paper reports on our experience in integrating Simics - a system-simulation tool - with Wattch - a microarchitectural performance and power modeling user-level simulation tool built on top of SimpleScalar We first present the technical challenges we had to resolve in designing SimWattch - the integrated tool. We then use it to identify the type of errors a user-level simulator typically does when predicting performance and power consumption while omitting operating system activity. This case study is based on SPEC95, and SPEC JVM98 applications and TPC-B. We find that if operating system effects are omitted, performance is usually overestimated while energy used is underestimated. However a surprising result is that IPC, power and resource occupancy predictions from a user-level simulator often follow the trends of predictions from simulations factoring in operating system effects.

This paper proposes to transform the branch outcome history from the time domain to the frequency domain. With our proposed Fourier Analysis Branch (FAB) predictor, we can represent long periodic branch history patterns - as long as 2/sup 13/ bits - with a realistic number of bits (52 bits). We evaluate the potential gains of the FAB predictor by considering a hybrid branch predictor in which each branch is predicted using a static scheme, the 2-bit dynamic scheme, the PAp and GAp schemes, and our FAB predictor. By including our FAB predictor in the hybrid predictor, it is possible to cut the misprediction rate of integer applications in the SPEC95 suite by between 5 and 50% with an average of 20%. Besides evaluating its performance, this paper shows some key properties of our FAB predictor and presents some possible implementation approaches.

Current cache hierarchies are indexed in parallel with a TLB but their tags are part of the physical address so that the memory hierarchy is physically addressed. This design faces problems as more concurrency is exploited in the processor core and as the memory demand of emerging applications is growing fast. The traditional TLB does not scale well inside the processor core and its hit rate call be poor for data-intensive applications or scientific applications without much locality. At the same time, given current trends towards computing in memory and in communication interfaces, virtual addresses are needed not just inside the processor but throughout the memory hierarchy. These observations have prompted us to result the problem of moving virtual address translation away from the processor. This paper introduces new ideas to enable the use of virtual addresses throughout the memory hierarchy. The major idea is the replacement of the TLB with a small Synonym Lookaside Buffer (SLB), which scales well because its size depends on the number of addresses, and not on the size of the application or of the physical memory. We also characterize synonym usage, evaluate the amount of cache and SLB flushing due to remapping of addresses, and compare the miss rate of various virtual physical cache organizations for several application domains. These evaluations show that virtually addressed memory hierarchies overall have better performance behavior than physically-addressed memory hierarchies. Finally, we also show how virtually-addressed memory hierarchies facilitate natural, scalable multiprocessor extensions, as well as computing-in-memory in the context of general-purpose computers.

State-based, formal methods have been successfully applied to the automatic verification of cache coherence in sequentially consistent systems. However, coherence in shared memory multiprocessors under a relaxed memory model is much more complex to verify automatically. With relaxed memory models, incoming invalidations and outgoing updates can be delayed in each cache while processors are allowed to race ahead. This buffering of memory accesses considerably increases the amount of state in each cache and the complexity of protocol interactions. Moreover, because caches can hold inconsistent copies of the same data for long periods of time, coherence cannot be verified by simply checking that cached copies are identical at all times. This paper makes two major contributions. First, we demonstrate how to model and verify cache coherence under a relaxed memory model in the context of state-based verification methods. Frameworks for modeling the hardware and for generating correct memory access sequences driving the hardware model are developed. We also show correctness properties which must be verified on the hardware model. Second, we demonstrate a successful application of a state-based verification tool called SSM for the verification of the delayed protocol, an aggressive protocol for relaxed memory models. SSM is based on an abstraction technique preserving the properties to verify. We show that with classical, explicit approaches the verification of cache coherence is realistically unfeasible because of the state space explosion problem, whereas SSM is able to verify protocols both at both behavioral and message-passing levels.

ILP processors can execute a large number of instructions at the same time. Thus it becomes more and more difficult to support traps efficiently. On the other hand a current trend in architecture is to support various memory functions in software rather than hardware, usually by trapping the execution processor on a cache miss, TLB miss or a failed access to a local or remote memory. These late memory traps block the faulty instruction at the top of the active list, backing up the pipeline. Moreover the support for late memory traps may affect the performance of non-faulting memory instructions as well. In this paper we analyze the overhead caused by late memory traps in ILP processors and define several measures for this overhead. In order to tolerate late memory traps, we propose hardware prefetching of exception conditions and a tagged store buffer to implement deferred traps on stores. We show that, with these hardware optimizations, the overhead added by the lateness of traps is significantly reduced relative to the overhead of early traps. Because of caching effects the frequency of late memory traps usually decreases as they are taken deeper in the memory hierarchy and their overall impact on the execution time becomes negligible.

Cache replacement policies such as FIFO (First-In/First-Out), LRU (Least Recently Used) and OPT (OPTimum) were conceived in the context of uniprocessor systems in which the cost of all cache misses was uniform.With the advent of multiprocessor systems, this uniform cost assumption has lost its validity.In this paper we revisit the problem of designing optimum cache replacement algorithms for CC-NUMA multiprocessors.In CC-NUMAs the cost of a miss mapping to a remote memory is higher in terms of latency, bandwidth, or power consumption than the cost of a miss mapping to the local memory.In general we call the class of replacement algorithms to minimize a non-uniform miss cost function "cost-sensitive replacement algorithms".We evaluate a cost-sensitive optimal replacement algorithm (CSOPT) using a trace-driven simulator and we compare it to OPT, the optimal algorithm assuming uniform miss cost in a CC-NUMA multiprocessor where misses have two different static costs.In this context, CSOPT has more misses than OPT because it may trade off several "cheap" misses for one "expensive" miss, but its overall cost is lower.We run all the SPLASH-2 benchmarks for several configurations of CC-NUMAs andfor cost ratios of up to 32, and observe that CSOPT can improve the cost function by 20% over OPT.This is quite an improvement considering that the benchmarks are finely tuned to run efhciently on CC-NUMA systems.

The frequency of accesses to remote data is a key factor affecting the performance of all Distributed Shared Memory (DSM) systems. Remote data caching is one of the most effective and general techniques to fight processor stalls due to remote capacity misses in the processor caches. The design space of remote data caches (RDC) has many dimensions and one essential performance trade-off hit ratio versus speed. Some recent commercial systems have opted for large and slow (S)DRAM network caches (NC), but others completely avoid them because of their damaging effects on the remote/local latency ratio. In this paper we will explore small and fast SRAM network caches as a means to reduce the remote stalls and capacity traffic of multiprocessor clusters. The major appeal of SRAM NCs is that they add less penalty on the latency of NC hits and remote accesses. Their small capacity can handle conflict misses and a limited amount of capacity misses. However, they can be coupled with main memory page caches which satisfy the bulk of capacity misses. To maximize performance for a large spectrum of applications, we propose to organize the NC as a victim cache for remote data. We also propose a novel and scalable method to control the page cache by integrating page relocation mechanisms into the network victim cache.

In modern processors, the dynamic translation of virtual addresses to support virtual memory is done before or in parallel with the first-level cache access. As processor technology improves at a rapid pace and the working sets of new applications grow insatiably the latency and bandwidth demands on the TLB (Translation Lookaside Buffer) are getting more and more difficult to meet. The situation is worse in multiprocessor systems, which run larger applications and are plagued by the TLB consistency problem. We evaluate and compare five options for virtual address translation in the context of COMAs (Cache Only Memory Architectures). The dynamic address translation mechanism can be located after the cache access provided the cache is virtual. In a particular design, which we call V-COMA for Virtual COMA, the physical address concept and the traditional TLB are eliminated. While still supporting virtual memory, V-COMA reduces the address translation overhead to a minimum. V-COMA scales well and works better in systems with large number of processors. As a machine running on virtual addresses, V-COMA provides a simple and consistent hardware model to the operating system and the compiler, in which further optimization opportunities are possible.

Article In-memory directories: eliminating the cost of directories in CC-NUMAs Share on Authors: Christopher Ho Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CA Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CAView Profile , Heidi Ziegler Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CA Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CAView Profile , Michel Dubois Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CA Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CAView Profile Authors Info & Claims SPAA '98: Proceedings of the tenth annual ACM symposium on Parallel algorithms and architecturesJune 1998 Pages 222–230https://doi.org/10.1145/277651.277688Online:01 June 1998Publication History 1citation228DownloadsMetricsTotal Citations1Total Downloads228Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Directory-based coherence protocols in shared-memory multiprocessors are so complex that verification techniques based on automated procedures are required to establish their correctness. State enumeration approaches are well-suited to the verification of cache protocols but they face the problem of state space explosion, leading to unacceptable verification time and memory consumption even for small system configurations. One way to manage this complexity and make the verification feasible is to map the system model to verify onto a symbolic state model (SSM). Since the number of symbolic states is considerably less than the number of system states, an exhaustive state search becomes possible, even for large-scale sytems and complex protocols. In this paper, we develop the concepts and notations to verifiy some properties of a directory-based protocol designed for non-FIFO interconnection networks. We compare the verification of the protocol with SSM and with the Stanford Mur φ, a verification tool enumerating system states. We show that SSM is much more efficient in terms of verification time and memory consumption and therefore holds that promise of verifying much more complex protocols. A unique feature of SSM is that it verifies protocols for any system size and therefore provides reliable verification results in one run of the tool.

We evaluate three 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 each extension targets distinct components of the read and write penalties, they can be combined effectively. This paper identifies the combinations yielding the best performance gains and cost trade-offs in the context of a class of cache-coherent NUMA (Non-Uniform Memory Access) architectures. Detailed architectural simulations of a multiprocessor with single-issue, statically scheduled CPUs, using five benchmarks, show that the protocol extensions often provide additive gains when they are properly combined. For example, the combination of prefetching with the competitive-update mechanism speeds up the execution by nearly a factor of two under release consistency. The same speedup is obtained under sequential consistency by combining prefetching with the migratory sharing optimization. This paper shows that a basic write-invalidate protocol augmented by appropriate extensions can eliminate most memory access penalties without any support from the programmer or the compiler.

This paper describes the methods used to formulate and validate the memory subsystem of the cache-coherent Sun Scalable Shared-memory MultiProcessor (S3.mp) at three levels of abstraction: the memory consistency model, the cache coherence protocol, and the implementation.

The performance of parallel systems under commercial applications strongly depend on the speeds of IO subsystems and interconnects. Any single bottleneck in there hinder one from fully taking advantages of today's faster CPUs and better instruction architectures. Therefore, configuring bottleneck-free IO subsystems and interconnects is essential. In this paper we considered IO subsystem and interconnect in SPAX system. When the SPAX's IO subsystem is lightly equipped, the first bottleneck appears at disk drives. Although the disk bottleneck can be removed by putting more disks, another bottleneck was detected at the data buffer which is the first component in communication path. That is to say, all components in IO subsystems and interconnects must be sufficiently equipped, simultaneously, to thoroughly eliminate the bottleneck. We could reach a cost-effective bottleneck-free configuration of SPAX by making use of its flexible hardware design. The simulation results of SPAX then show significant performance gain from faster CPUs with better instruction architectures.

Traditionally, cache coherence in multiprocessors has been maintained in hardware. However, the cost-effectiveness of hardwired protocols is questionable. Virtual Shared Memory systems have highlighted the many advantages of software-implemented protocols, albeit at a performance price. The performance gap is narrowed by hybrid systems with the addition of hardware support for fine-grain sharing. We have developed a software protocol for a COMA (Cache-Only Memory Architecture). We call the system SC-COMA for Software-Controlled COMA, to emphasize that the protocol engine is emulated by software executed on the main processor. Contrary to user-level protocols, the software handling coherence events in SC-COMA runs in sub-kernel mode, transparently providing the same services to applications as a hardware counterpart. The software emulation layer has been written and we compare SC-COMA to an idealized hardware COMA through detailed simulations. Our results show that SC-COMA is competitive. On systems with 32 processors, it achieves a slowdown of 11-56% with respect to its hardware counterpart, across a range of applications and memory pressures. SC-COMA scales well, up to 32 nodes. A study on the impact of faster processors on SC-COMA's relative performance indicates a consistent improvement, but with a limitation due to the loosely-integrated design. We conclude that SC-COMA is a viable solution to easily transform networks of workstations into powerful multiprocessors.

We propose and evaluate a new data prefetching technique for cache coherent multiprocessors. Prefetches are issued by a prefetch engine which is controlled by the compiler. Second-level cache misses generate cache miss traps, and start the prefetch engine in a trap handler generated by the compiler. The only instruction overhead in our approach is when a trap handler terminates after data arrives. We present the functionality of the prefetch engine and a compiler algorithm to control it. We also study emulation of the prefetch engine in software. Our techniques are evaluated on six parallel applications using a compiler which incorporates our algorithm and a simulated multiprocessor. The prefetch engines remove up to 67% of the memory access stall time at an instruction overhead less than 0.42%. The emulated prefetch engines remove in general less stall time at a higher instruction overhead.

Recent advances in Field-Programmable Gate Arrays (FPGA) and programmable interconnects have made it possible to build efficient hardware emulation engines. In addition, improvements in Computer-Aided Design (CAD) tools, mainly in synthesis tools, greatly simplify the design of large circuits. The RPM (Rapid Prototype Engine for Multiprocessors) Project leverages these two technological advances. Its goal is to develop a common hardware platform for the emulation of multiprocessor systems with different architectures.

As microprocessor speeds continue to improve at a very fast rate the bandwidth requirements for system level interconnections in multiprocessors may eventually rule out the use of shared buses even for small scale multiprocessors. On the other hand high speed unidirectional links are an emerging technology that has the potential to scale with microprocessor technology and could replace buses as the interconnection fabric for future multiprocessors. We evaluate the performance of the unidirectional slotted ring interconnection for small to medium scale shared memory systems, using a hybrid methodology of analytical models and trace driven simulations. We use memory traces from actual execution of parallel programs to drive detailed event driven simulations of a variety of ring and bus multiprocessors. Snooping and directory coherence protocols for the slotted ring are evaluated in the context of multitasking. Snooping is shown to outperform full map and linked list directory schemes in the unidirectional slotted ring, and it also compares favorably to high performance split transaction bus systems.>

To offset the effect of read miss penalties on processor utilization in shared-memory multiprocessors, several software- and hardware-based data prefetching schemes have been proposed. A major advantage of hardware techniques is that they need no support from the programmer or compiler. Sequential prefetching is a simple hardware-controlled prefetching technique which relies on the automatic prefetch of consecutive blocks following the block that misses in the cache, thus exploiting spatial locality. In its simplest form, the number of prefetched blocks on each miss is fixed throughout the execution. However, since the prefetching efficiency varies during the execution of a program, we propose to adapt the number of pre-fetched blocks according to a dynamic measure of prefetching effectiveness. Simulations of this adaptive scheme show reductions of the number of read misses, the read penalty, and of the execution time by up to 78%, 58%, and 25% respectively.>

We introduce a cache protocol verification technique based on a symbolic state expansion procedure. A global Finite State Machine (FSM) model characterizing the protocol behavior is built and protocol verification becomes equivalent to finding whether or not the global FSM may enter erroneous states. In order to reduce the complexity of the state expansion process, all the caches in the same state are grouped into an equivalence class and the number of caches in the class is symbolically represented by a repetition constructor. This symbolic representation is partly justified by the symmetry and homogeneity of cache-based systems. However, the key idea behind the representation is to exploit a unique property of cache coherence protocols: the fact that protocol correctness is not dependent on the exact number of cached copies. Rather, symbolic states only need to keep track of whether the caches have 0, 1, or multiple copies. The resulting symbolic state expansion process only takes a few steps and verifies the protocol for any system size. Therefore, it is more efficient and reliable than current approaches. The verification procedure is first applied to the verification of five existing protocols under the assumption of atomic protocol transitions. A simple snooping protocol on a split-transaction shared bus is also verified to illustrate the extension of our approach to protocols with nonatomic transitions.>

The complexity of directory based protocols has motivated us to build a hardware emulator or testbed for the rapid prototyping of various protocols under various memory consistency models for CC-NUMA architectures. To implement and verify new protocols rapidly on the testbed, we have developed an overall methodology around a set of tools applicable to different aspects of the verification of a protocol, i.e., protocol-intrinsic errors, memory access ordering errors and protocol implementation errors. These tools include formal verification techniques, architecture simulators and hardware mechanisms implemented in the FPGAs of the testbed.

Considers 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.>

To offset the effect of read miss penalties on processor utilization in shared-memory multiprocessors, several software- and hardware-based data prefetching schemes have been proposed. A major advantage of hardware tech niques is that they need no support from the programmer or compiler. Sequential prefetching is a simple hardware-controlled prefetching technique which relies on the automatic prefetch of consecutive blocks following the block that misses in the cache. In its simplest form, the number of prefetched blocks on each miss is fixed throughout the exe cution. However, since the prefetching efficiency varies during the execution of a program, we propose to adapt the number of pref etched blocks according to a dynamic measure of prefetching effectiveness. Simulations of this adaptive scheme show significant reductions of the read penalty and of the overall execution time.

In this paper, we introduce a simple hardware mechanism supporting non-blocking loads in conjunction with lockup-free caches to hide memory latencies in high-performance processors. The cache and processor cooperate on load misses so that the overall complexity of the non-blocking mechanisms in the cache and in the processor is greatly reduced. We use detailed simulations to evaluate the effectiveness of the architecture and of a simple compiler transformation at hiding miss latencies of up to 200 processor cycles. For a given program we identify a critical latency. For latencies lower than this critical latency, the non-blocking processor/cache architecture achieves perfect memory latency tolerance by overlapping misses with processor execution. For higher latencies, significant improvements in processor efficiency are still obtained by overlapping multiple misses together. A simple model is used to illustrate this effect and improvements are proposed based on the results.

Advances in circuit and integration technology are continuously boosting the speed of microprocessors. One of the main challenges presented by such developments is the effective use of powerful microprocessors in shared memory multiprocessor configurations. We believe that the interconnection problem is not solved even for small scale shared memory multiprocessors, since the speed of shared buses is unlikely to keep up with the bandwidth requirements of new microprocessors. In this paper we evaluate the performance of unidirectional slotted ring interconnection for small to medium scale shared memory systems, using a hybrid methodology of analytical models and trace-driven simulations. We evaluate both snooping and directory-based coherence protocols for the ring and compare it to high performance split transaction buses.

In this paper we introduce a new classification of misses in shared-memory multiprocessors based on interprocessor communication. We identify the set of essential misses, i.e., the smallest set of misses necessary for correct execution. Essential misses include cold misses and true sharing misses. All other misses are useless misses and can be ignored without affecting the correctness of program execution. Based on the new classification we compare the effectiveness of five different protocols which delay and combine invalidations leading to useless misses. In cache-based systems the protocols are very effective and have miss rates close to the essential miss rate. In virtual shared memory systems the techniques are also effective but leave room for improvements.

The evaluation of cache-based systems demands careful simulations of entire benchmarks. Simulation efficiency is essential to realistic evaluations. For systems with large caches and large number of processors, simulation is often too slow to be practical. In particular, the optimized design of a cache for a multiprocessor is very complex with current techniques.This paper addresses these problems. First we introduce necessary and sufficient conditions for cache inclusion in systems with invalidations. Second, under cache inclusion, we show that an accurate trace for a given processor or for a cluster of processors can be extracted from a multiprocessor trace. With this methodology, possible cache architectures for a processor or for a cluster of processors are evaluated independently of the rest of the system, resulting in a drastic reduction of the trace length and simulation complexity. Moreover, many important system-wide metrics can be estimated with good accuracy by extracting the traces of a set of randomly selected processors, an approach we call processor sampling. We demonstrate the accuracy and efficiency of these techniques by applying them to three 64-processor traces.

In this paper we introduce a verification technique for cache coherence protocols at the behavior level. Protocols are specified by a Finite State Machine (FSM) model. The global state space is the Cartesian product of an arbitrary number of individual cache state spaces and is symbolically expanded. A global FSM characterizing the protocol behavior is built and protocol verification becomes equivalent to finding whether or not the global FSM may enter erroneous states. State expansion only takes a few steps, contrary to current approaches. The verification procedure is applied to the verification of five existing protocols Keywords: cache coherence protocol, formal verification, finite state machine, symbolic expansion and shared-memory multiprocessor. 2 The Verification of Cache Coherence Protocols Abstract In this paper we introduce a verification technique for cache coherence protocols at the behavior level. Protocols are specified by a Finite State Machine (FSM) model. The globa...

In cache based multiprocessors a protocol must maintain coherence among replicated copies of shared writable data. In delayed consistency protocols the effect of out-going and in-coming invalidations or updates are delayed. Delayed coherence can reduce processor blocking time as well as the effects offalse sharing. In this paper, we introduce several implementations of delayed consistency for cache-based systems in the framework of a weakly­ ordered consistency model. A performance comparison of the delayed protocols with the corre sponding On-the-Fly (non-delayed) consistency protocol is made, through execution-driven simulations of four parallel algorithms. The results show that,for parallel programs in which false sharing is a problem, significant reductions in the data miss rate of paraUel programs can be obtained with just a small incre ase in the cost and complexity of the cache system.

The problem studied is similar to the problems found in multiprocessor operating systems. The lockout problem in multiprocessor operating systems is a direct result of multiple processors attempting to process common data structures asynchronously. There are numerous such shared data structures. The models developed are applicable to the study of contention for software and hardware resources in multiprocessor operating systems. The authors introduce an approximate analytical model to evaluate the performance of asynchronous processes found in asynchronous algorithms, including the combined effects of software lockout on critical sections and on job queues, and of shared-memory access conflicts. Because of the strong similarities between the two effects, the same model can be used for both, leading to a uniform and elegant formulation. The models are combined to find the run-time efficiency of asynchronous iterations.>

Simulation is used to analyze shared block contention in eight parallel algorithms and its effects on the performance of a cache coherence protocol under the assumption of infinite cache sizes. A simple program model for data and block sharing is introduced, and an analytical closed-form solution is found for all components of the cache coherence overhead. This model is based on the observation that shared writable blocks are accessed in critical or in semicritical sections. The program model is applied to the analysis of multiprocessor systems with finite cache sizes and for steady state computations. The authors compare the model predictions to the results of execution-driven simulations of eight parallel algorithms. The simulation is conducted for various numbers of processors and different cache block sizes.>

This paper presents the architectural design and RISC based implementation of a prototype supercomputer, namely the Orthogonal MultiProcessor (OMP). The OMP system is constructed with 16 Intel 1860 RISC microprocessors and 256 parallel memory modules, which are 2-D interleaved and orthogonally accessed using custom-designed spanning buses. The architectural design has been validated by a CSIM-based multiprocessor simulator. The design choices are based on worst-case delay analysis and simulation validation. The current OMP prototype chooses a 2-dimensional memory architecture, mainly for image processing, computer vision, and neural network simulation applications. The 16-processor OMP prototype is targeted to achieve a peak performance of 400 RISC integer MIPS or a maximum of 640 Mflops. This paper presents the architectural design of the OMP prototype at system and PC board levels. We are presently entering the fabrication stage of all the PC boards. The system is expected to become operational in late 1991 and benchmarking results will be available in 1992. Only hardware design features are reported here. Software and simulation results are reported elsewhere.

Many problems in the area of symbolic computing can be solved by iterative algorithms. Implementations of these algorithms on multiprocessors can be synchronous or asynchronous. Asynchronous implementations are potentially more efficient because synchronization is a major source of performance degradation in most multiprocessor systems. In this paper, sufficient conditions for the convergence of asynchronous iterations to desired solutions are given. The main sufficient condition is shown to be also necessary for the case of finite data domains. The results are applied to prove the convergence of three asynchronous algorithms for the all-pairs shortest path problem, the consistent labeling problem, and a neural net model.

The presence of high-performance mechanisms in shared-memory multiprocessors such as private caches, the extensive pipelining of memory access, and combining networks may render a logical concurrency model complex to implement or inefficient. The problem of implementing a given logical concurrency model in such a multiprocessor is addressed. Two concurrency models are considered, and simple rules are introduced to verify that a multiprocessor architecture adheres to the models. The rules are applied to several examples of multiprocessor architectures.>

A mechanism called the pivot mechanism is introduced and described. It controls the dynamic migration of data pages between neighboring memory modules during program execution to improve the performance and programmability of multiprocessors with distributed global memory. The programmer or compiler is relieved from the data allocation task; moreover, because data allocation is dynamically modified to minimize communication traffic, algorithms with varying and unpredictable data access patterns can run efficiently. Flexible data migration serves the dual purpose of making algorithms the efficient machine-specific and making possible the efficient execution of algorithms for which a good static allocation is not possible. Simulation results based on a mesh-connected multiprocessor performing a matrix multiplication are presented.>

Multiprocessor architectures using point-to point interconnects and executing parallel algorithms require careful partitioning and allocation of data and processes. For a given interconnection, optimal allocation may be difficult to achieve in some cases because the data-dependent behavior of some algorithms may be impossible to predict. A mechanism called the pivot mechanism is introduced and described that controls the dynamic migration of data pages between neighboring memory modules during program execution. Flexible data migration serves the dual purpose of making algorithms less machine-specific and making possible efficient algorithm execution that is impossible to achieve by using static data allocation.>

The performance of cache-based, shared-memory multiprocessors can suffer greatly from moderate cache miss rates because of the usually high ratio between memory-access and cache-access times. The authors propose a lockup-free cache design in which the handling of one or several cache misses is overlapped with processor activity. In multiprocessors, lockup-free caches aggravate the memory coherence problem. Three different cache architectures relying on different compiler interventions are introduced. A performance model demonstrates the usefulness of lockup-free caches for high-performance processors. The merits and disadvantages of the three schemes are discussed, and compiler techniques to take advantage of the proposed designs are illustrated.>

The performance of cache-based multiprocessors for general-purpose computing and for multitasking is analyzed with simple throughput models. A private cache is associated with each processor, and multiple buses connect the processors to the shared, interleaved memory. Simple models based on dynamic instruction mix statistics are introduced to evaluate upper bounds on the throughput when independent tasks are run on each processor. With these models, one can obtain a first estimate of the MIPS (millions of instructions per second) rate of a multiprocessor.>

This paper shows that cache coherence protocols can implement indivisible synchronization primitives reliably and can also enforce sequential consistency. Sequential consistency provides a commonly accepted model of behavior of multiprocessors. We derive a simple set of conditions needed to enforce sequential consistency in multiprocessors. These conditions are easily applied to prove the correctness of existing cache coherence protocols that rely on one or multiple broadcast buses to enforce atomicity of updates; in these protocols, all processing elements must be connected to the broadcast buses. The conditions are also used in this paper to establish new protocols which do not rely on the atomicity of updates and therefore do not require single access buses to propagate invalidations or to perform distributed WRITEs. It is also shown how such protocols can implement atomic READ&MODIFY operations for synchronization purposes.

In highly-pipelined machines, instructions and data are prefetched and buffered in both the processor and the cache. This is done to reduce the average memory access latency and to take advantage of memory interleaving. Lock-up free caches are designed to avoid processor blocking on a cache miss. Write buffers are often included in a pipelined machine to avoid processor waiting on writes. In a shared memory multiprocessor, there are more advantages in buffering memory requests, since each memory access has to traverse the memory- processor interconnection and has to compete with memory requests issued by different processors. Buffering, however, can cause logical problems in multiprocessors. These problems are aggravated if each processor has a private memory in which shared writable data may be present, such as in a cache-based system or in a system with a distributed global memory. In this paper, we analyze the benefits and problems associated with the buffering of memory requests in shared memory multiprocessors. We show that the logical problem of buffering is directly related to the problem of synchronization. A simple model is presented to evaluate the performance improvement resulting from buffering.

Shared-memory multiprocessors to support concurrent languages for general-purpose multitasked systems are analyzed. To solve the traditional performance problems caused by memory access latency and conflicts, extensive caching of instructions and data is performed in each processor mode. Caches are private to each processor, and coherence is maintained in hardware between the caches. To maintain a good efficiency, several contexts are resident in each processor. On a miss in the cache, a microswitch to another resident context is operated by changing the program counter and a pointer in the register memory. The instruction set of each processor is RISC-like, so that a microswitch should waste few machine cycles. The proposed system has high efficiency, even when the number of processors increases and when the coherence overhead and conflicts are high. Models are developed to evaluate throughput and efficiency.

A possible design alternative for improving the performance of a multiprocessor system is to insert a private cache between each processor and the shared memory. The caches act as high-speed buffers by reducing the effective memory access time, and affect the delays caused by memory conflicts. In this paper, we study the effectiveness of caches in a multiprocessor system. The shared memory is pipelined and interleaved to improve the block transfer rate, and it assumes a two-dimensional organization, previously studied under random and word access. An approximate model is developed to estimate the processor utilization and the speed-up improvement provided by the caches.

In many commercial multiprocessor systems, each processor accesses the memory through a private cache. One problem that could limit the extensibility of the system and its performance is the enforcement of cache coherence. A mechanism must exist which prevents the existence of several different copies of the same data block in different private caches. In this paper, we present an indepth analysis of the effect of cache coherency in multiprocessors. A novel analytical model for the program behavior of a multitasked system is introduced. The model includes the behavior of each process and the interactions between processes with regard to the sharing of data blocks. An approximation is developed to derive the main effects of the cache coherency contributing to degradations in system performance.

In many commercial multiprocessor systems, each processor accesses the memory through a private cache. One problem that could limit the extensibility of the system and its performance is the enforcement of cache coherence. A mechanism must exist which prevents the existence of several different copies of the same data block in different private caches. In this paper, we present an in-depth analysis of the effects of cache coherency in multiprocessors. A novel analytical model for the program behavior of a multitasked system is introduced. The model includes the behavior of each process and the interactions between processes with regard to the sharing of data blocks. An approximation is developed to derive the main effects of the cache coherency contributing to degradations in system performance.

A general methodology for studying the degree of matching between an architecture and an algorithm is introduced and applied to the case of synchronized iterative algorithms in MIMD machines.

A possible design alternative to improve the performance of a multiprocessor system is to insert a private cache between each processor and the shared memory. The caches act as high-speed buffers, reducing the memory access time, and affect the delays caused by memory conflicts. In this paper, we study the performance of a multiprocessor system with caches. The shared memory is pipelined and interleaved to improve the block transfer rate, and assumes an L-M organization, previously studied under random word access. An approximate model is developed to estimate the processor utilization and the speedup improvement provided by the caches. These two parameters are essential to a cost-effective design. An example of a design is treated to illustrate the usefulness of this investigation.