Multicast snooping: a new coherence method using a multicast address network
Published 1 May 1999
E. Ender Bilir, Ross M. Dickson, Ying Hu, Manoj Plakal, Daniel J. Sorin, Mark D. Hill
Citations93
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
This paper proposes a new coherence method called "multicast snooping" that dynamically adapts between broadcast snooping and a directory protocol. Multicast snooping is unique because processors predict which caches should snoop each coherence transaction by specifying a multicast "mask." Transactions are delivered with an ordered multicast network, such as an Isotach network, which eliminates the need for acknowledgment messages. Processors handle transactions as they would with a snooping protocol, while a simplified directory operates in parallel to check masks and gracefully handle incorrect ones (e.g., previous owner missing). Preliminary performance numbers with mostly SPLASH-2 benchmarks running on 32 processors show that we can limit multicasts to an average of 2-6 destinations (<< 32) and we can deliver 2-5 multicasts per network cycle (>> broadcast snooping 's 1 per cycle). While these results do not include timing, they do provide encouragement that multic...
Keywords
Computer Science
Journal of Computational Chemistry<scp>CHARMM</scp>: A program for macromolecular energy, minimization, and dynamics calculations
14,945 Citations1983Bernard R. Brooks, Robert E. Bruccoleri +4 more
Association for Computing Machinery eBooksTime, clocks, and the ordering of events in a distributed system
1,969 Citations2019Leslie Lamport
Communications of the ACMParallel discrete event simulation
1,816 Citations1990Richard M. Fujimoto
This article deals with the execution of a simulation program on a parallel computer by decomposing the simulation application into a set of concurrently executing processes and introduces interesting synchronization problems that are at the heart of the PDES problem.
IEEE Transactions on Software EngineeringDistributed Simulation: A Case Study in Design and Verification of Distributed Programs
1,071 Citations1979K. Mani Chandy, Jayadev Misra
This work proposes a distributed solution where processes communicate only through messages with their neighbors; there are no shared variables and there is no central process for message routing or process scheduling.
ComputerThe Stanford Dash multiprocessor
972 Citations1992Daniel Lenoski, James Laudon +6 more
The overall goals and major features of the directory architecture for shared memory (Dash), a distributed directory-based protocol that provides cache coherence without compromising scalability, are presented.
The SGI Origin
779 Citations1997James Laudon, Daniel Lenoski
The motivation for building the Origin 2000 is discussed and the architecture and implementation of the multiprocessor is described, and performance results are presented for the NAS Parallel Benchmarks V2.2 and the SPLASH2 applications.
Communications of the ACMThe process group approach to reliable distributed computing
724 Citations1993Ken Birman
Six years of on ISIS is reviewed, describing the model, its implementation challenges, and the types of applications to which ISIS has been applied.
IEEE Transactions on ComputersA New Solution to Coherence Problems in Multicache Systems
620 Citations1978Censier, Feautrier
A memory hierarchy has coherence problems as soon as one of its levels is split in several independent units which are not equally accessible from faster levels or processors.
ACM SIGARCH Computer Architecture NewsThe directory-based cache coherence protocol for the DASH multiprocessor
542 Citations1990Daniel Lenoski, James Laudon +3 more
DASH is a scalable shared-memory multiprocessor currently being developed at Stanford's Computer Systems Laboratory that consists of powerful processing nodes, each with a portion of its memory dedicated to memory efficient operations.
An evaluation of directory schemes for cache coherence
419 Citations1998Anant Agarwal, Richard Simoni +2 more
Using cache memory to reduce processor-memory traffic
396 Citations1998James Goodman
It is demonstrated that a cache exploiting primarily temporal locality (look-behind) can indeed reduce traffic to memory greatly, and introduce an elegant solution to the cache coherency problem.
IEEE Transactions on Software EngineeringOrca: a language for parallel programming of distributed systems
393 Citations1992Henri E. Bal, M. Frans Kaashoek +1 more
Three example parallel applications in Orca, one of which is described in detail, are discussed, and one of the existing implementations, which is based on reliable broadcasting, is described.
Journal of Parallel and Distributed ComputingThe Network Architecture of the Connection Machine CM-5
368 Citations1996Charles E. Leiserson, Zahi S. Abuhamdeh +11 more
ACM SIGARCH Computer Architecture NewsA class of compatible cache consistency protocols and their support by the IEEE futurebus
279 Citations1986P. Sweazey, Alan Jay Smith
This paper defines a class of compatible consistency protocols supported by the current IEEE Futurebus design, referred to as the MOESI class of protocols, which has the property that any system component can select (dynamically) any action permitted by any protocol in the class, and be assured that consistency is maintained throughout the system.
Reducing Memory and Traffic Requirements for Scalable Directory-Based Cache Coherence Schemes*
277 Citations1992Anoop Gupta, Wolf-Dietrich Weber +1 more
As multiprocessors are scaled beyond single bus systems, there is renewed interest in directory-based cache coherence schemes that use a limited number of pointers per directory entry to keep track of all processors caching a memory block.
ComputerDDM-a cache-only memory architecture
253 Citations1992Erik Hägersten, Anders Landin +1 more
The Data Diffusion Machine (DDM), a cache-only memory architecture (COMA) that relies on a hierarchical network structure, is described and simulated performance results are presented.
Journal of Computer and System SciencesHow to emulate shared memory
194 Citations1991Abhiram Ranade
This work presents a simple algorithm for emulating an N processor CRCW PRAM on an N node butterfly that improves the result of Pippenger by routing permutations with bounded queues in logarithmic time, without the possibility of deadlock.
Hierarchical cache/bus architecture for shared memory multiprocessors
193 Citations1987Andrew Wilson
The model indicates that a system of over 1000 usable MIPS can be constructed using high performance microprocessors and that the additional coherency protocol overhead introduced by the clustered approach is small.
IEEE ConcurrencyWisconsin Wind Tunnel II: a fast, portable parallel architecture simulator
165 Citations2000S. Mukherjee, S.K. Reinhardt +6 more
Through four key operations, the Wisconsin Wind Tunnel II can easily run simulations on Sparc platforms ranging from a workstation cluster to an asymmetric multiprocessor.
IEEE Transactions on ComputersCache invalidation patterns in shared-memory multiprocessors
144 Citations1992Aman Gupta, W.-D. Weber
The cache invalidation patterns of several parallel applications are analyzed and a classification scheme for data objects found in parallel programs is proposed, indicating that cache line sizes in the 32-byte range yield the lowest data and invalidation traffic.
Efficient support for irregular applications on distributed-memory machines
121 Citations1995Shubhendu S. Mukherjee, Shamik D. Sharma +4 more
Three issues—partitioning, mutual exclusion, and data transfer—crucial to the efficient execution of irregular problems on distributed-memory machines are explored.
ACM SIGARCH Computer Architecture NewsThe SGI Origin
114 Citations1997James Laudon, Daniel Lenoski
The SGI Origin 2000 is a cache-coherent non-uniform memory access (ccNUMA) multiprocessor designed and manufactured by Silicon Graphics, Inc.
ACM SIGARCH Computer Architecture NewsDeadlock-free multicast wormhole routing in multicomputer networks
69 Citations1991Xiaola Lin, Lionel M. Ni
Lamport clocks
67 Citations1998Manoj Plakal, Daniel J. Sorin +2 more
This paper applies Lamport clocks to prove that a non-trivial directory protocol implements sequential consistency, describing an SGI Origin 2000-like protocol in detail, and providing a timestamping scheme that totally orders all protocol events, and proving sequential consistency.
Race-free interconnection networks and multiprocessor consistency
66 Citations1991Anders Landin, Erik Hägersten +1 more
New conditions for sequential consistency are presented which show that sequential consistency can be maintained if all accesses in a multiprocessor can be ordered in an acyclic graph and what is required to maintain processor consistency in race-free networks are investigated.
Implementing multidestination worms in switch-based parallel systems
50 Citations1997Craig Stunkel, R. Sivaram +1 more
This paper proposes alternative switch architectures with differing buffer organizations to implement multidestination worms on switch-based parallel systems and demonstrates the superiority of the central-buffer-based switch architecture.
Efficient multicast on Myrinet using link-level flow control
48 Citations2002R.A.F. Bhoedjang, Tim Rühl +1 more
A new, efficient, and reliable software multicast protocol is presented that uses the network interface to efficiently forward multicast traffic and is constructed on top of reliable, flow-controlled channels between pairs of network interfaces.
IEEE Transactions on Parallel and Distributed SystemsIsotach networks
33 Citations1997Paul F. Reynolds, Craig C. Williams +1 more
Empirical and analytic studies of Isotach synchronization techniques show that they outperform conventional techniques, in some cases by an order of magnitude or more.
An evaluation of directory protocols for medium-scale shared-memory multiprocessors
32 Citations1994Shubhendu S. Mukherjee, Mark D. Hill
The results are the first to compare all these protocols with complete applications (and the first evaluation of Tristate with a non-synthetic workload), and the choice between Dir i, B, Coarse Vector, and Gray-software depends on whether one wants to optimize for few sharers, many sharers), or hedge one's bets betweem both alternatives.
A cache consistency protocol for multiprocessors with multistage networks
31 Citations1989Per Stenström
A hardware based cache consistency protocol for multipro cessors with multistage networks is proposed and the two-mode approach limits the upper bound for the communication cost to a value considerably lower than that for other protocols.
Using Lamport clocks to reason about relaxed memory models
30 Citations1999Anne Condon, M.D. Hill +2 more
Analysis shows how to apply Lamport clocks to verify TSO and Alpha specifications at the architectural level.
A hardware multicast routing algorithm for two-dimensional meshes
28 Citations2002Prasant Mohapatra, Vara Varavithya
The simulation results show that the proposed TPM algorithm performs significantly better for both contention-free and mixed-traffic conditions, when compared with the previously proposed multicast algorithms.
Journal of Parallel and Distributed ComputingNotification and multicast networks for synchronization and coherence
16 Citations1992John B. Andrews, Carl Beckmann +1 more
Two different multistage interconnection network designs for shared-memory multiprocessors that provide unrestricted multicast and notification capabilities are presented, demonstrating their use in supporting efficient directory-based update or invalidate cache coherence.
IEEE Transactions on Parallel and Distributed SystemsAsynchronous tree-based multicasting in wormhole-switched MINs
13 Citations1999Vara Varavithya, Prasant Mohapatra
The results indicate that the proposed hardware-based ATBM scheme reduces the communication latency when compared to the software multicasting approach proposed earlier.
LibraConcurrency Control in Asynchronous Computations
13 Citations1993Carolyn Craig Williams
It is shown that isotach systems outperform conventional systems under workloads with atomicity and sequencing constraints, and a family of new cache coherence protocols called delta-cache protocols that extend isotach-based concurrency control techniques to systems that replicate and migrate shared variables, yielding protocols that are both scalable and more highly concurrent than existing protocols.
IEEE Transactions on Parallel and Distributed SystemsPerformance of pruning-cache directories for large-scale multiprocessors
13 Citations1993Steven L. Scott, James Goodman
It is shown that pruning-caches are more cost-effective and more robust than the more conventional inclusion cache for providing multilevel inclusion (MLI) in the cache hierarchy, and that the k-ary n-cube topology provides scalable, bottleneck-free communication for uniform, point-to-point traffic.
International Wound JournalLamport Clocks: Reasoning About Shared Memory Correctness1
11 Citations1999Daniel J. Sorin, Manoj Plakal +2 more
The value of Lamport clocks is demonstrated by showing that sequential consistency (SC) is obeyed by a variety of snooping bus-based coherence protocols, ranging from a simple cache-less system to a split-transaction out-of-order bus.
Tree-based multicasting on wormhole routed multistage interconnection networks
9 Citations2002V. Varavithy, Prasant Mohapatra
An asynchronous tree-based multicasting algorithm is developed in which deadlocks are prevented by serializing the initiations of branching operations that have potential for creating deadlocks.
LibraLogical Time Coherence Maintenance
5 Citations1998Bronis R. de Supinski
A new framework for isotach shared memory systems is defined that supports protocols that work for arbitrary topologies and are suited to a wide range of reference patterns, and introduces the flex algorithm, a new implementation of isotach logical time that allows different links to be assigned different logical distances.