Cache And Interconnect Architectures In Multiprocessors Eilat, Israel May 25-261989 Michel Dubois UniversityofSouthernCalifornia Shreekant S. Thakkar SequentComputerSystems The aim of the workshop was to bring together researchers working on cache coherence protocols for shared-memory multiprocessors with various interconnect architectures. Shared-memory multiprocessors have become viable systems for many applications. Bus based shared-memory systems (Eg. Sequent's Symmetry, Encore's Multimax) are currently limited to 32 processors. The fIrst goal of the workshop was to learn about the performance ofapplications on current cache-based systems. The second goal was to learn about new network architectures and protocols for future scalable systems. These protocols and interconnects would allow shared-memory architectures to scale beyond current imitations. The workshop had 20 speakers who talked about their current research. The discussions were lively and cordial enough to keep the participants away from the wonderful sand and sun for two days. The participants got to know each other well and were able to share their thoughts in an informal manner. The workshop was organized into several sessions. The summary of each session is described below. This book presents revisions of some of the papers presented at the workshop.

Abstract: "In this paper, we study a hardware-supported, compiler-directed (HSCD) cache coherence scheme, which can be implemented on a large-scale multiprocessor using off-the-shelf microprocessors, such as the Cray T3D. The scheme can be adapted to various cache organizations, including multi-word cache lines and byte-addressable architectures. Several system related issues, including critical sections, inter-thread communication, and task migration have also been addressed. The cost of the required hardware support is minimal and proportional to the cache size. The necessary compiler algorithms, including intra- and interprocedural array data flow analysis, have been implemented on the Polaris parallelizing compiler [33]. From our simulation study using the Perfect Club benchmarks [5], we found that in spite of the conservative analysis made by the compiler, the performance of the proposed HSCD scheme can be comparable to that of a full-map hardware directory scheme. Given its comparable performance and reduced hardware cost, the proposed scheme can be a viable alternative for large-scale multiprocessors such as the Cray T3D, which rely on users to maintain data coherence."

"Chip multiprocessors continue to provide programmers with a coherent view of shared memory in hardware across all cores. At large core counts, maintaining coherence in hardware across cached copies of data is a challenge due to bandwidth and metadata storage consumption. A cache block is the basic unit for data storage and communication, chosen at design time to match average locality across a range of applications. Conventional hardware implements the coherence protocol using a fixed granularity (of a cache block) for all coherence operations. Coherence metadata is recorded for every cache block, and coherence permissions are also granted in cache block units. Metadata is typically proportional both to the number of cores and the amount of data cached. Empirical analysis shows that applications typically exhibit a small number of sharing patterns, resulting in redundant information in the metadata. Similarly, considerable bandwidth is wasted due to a mismatch between application access granularity and the fixed granularity data and coherence communication. This dissertation leverages the inherent patterns of data access and sharing behavior in applications to design protocols that eliminate the bandwidth and metadata storage waste in conventional coherence protocols. The sharing pattern-aware directory designs, which we call SPACE and SPATL, recognize and represent only one copy of the subset of sharing patterns exhibited at any given instant in an application. The resulting protocols eliminate the linear proportionality of metadata storage to the number of cores. The adaptive coherence granularity designs, which we call Protozoa, match data movement to an application's spatial locality and access behavior, supporting fine granularity sharing without increasing metadata storage needs. The application-directed approach allows bandwidth needs to track inherent application access and sharing behavior"--Page vii-viii.

The book illustrates state-of-the-art software solutions for cache coherence maintenance in shared-memory multiprocessors. It begins with a brief overview of the cache coherence problem and introduces software solutions to the problem. The text defines and details static and dynamic software schemes, techniques for modeling performance evaluation mechanisms, and performance evaluation studies.

Mathematics of Computing -- Parallelism.

Many modern computer systems, including homogeneous and heterogeneous architectures, support shared memory in hardware. In a shared memory system, each of the processor cores may read and write to a single shared address space. For a shared memory machine, the memory consistency model defines the architecturally visible behavior of its memory system. Consistency definitions provide rules about loads and stores (or memory reads and writes) and how they act upon memory. As part of supporting a memory consistency model, many machines also provide cache coherence protocols that ensure that multiple cached copies of data are kept up-to-date. The goal of this primer is to provide readers with a basic understanding of consistency and coherence. This understanding includes both the issues that must be solved as well as a variety of solutions. We present both high-level concepts as well as specific, concrete examples from real-world systems. This second edition reflects a decade of advancements since the first edition and includes, among other more modest changes, two new chapters: one on consistency and coherence for non-CPU accelerators (with a focus on GPUs) and one that points to formal work and tools on consistency and coherence.