Design and Implementation of a Distributed Cache Coherence Protocol

From Tetherless World Wiki

Jump to: navigation, search

Citation: Manu Thapar and Bruce A. Delagi. (1990) Design and Implementation of a Distributed Cache Coherence Protocol. In KSL-89-72, April,1990.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Manu Thapar and Bruce A. Delagi
title Design and Implementation of a Distributed Cache Coherence Protocol
number KSL-89-72
institution Knowledge Systems, AI Laboratory
year 1990
month April
Bibtex more
Access Paper
abstract Cache coherence is an important well known problem in shared memory multiprocessor systems. If multiple caches are allowed to simultaneously have copies of a given memory location, a mechanism must exist to ensure that all copies remain consistent when the contents of that memory location are modified. The cache coherence problem may be solved through hardware or software. Hardware based protocols to solve the cache coherence problem are well understood for bus based shared memory architectures. However the shared bus limits the number of processors that can be connected to the bus without saturating it. To support scalable shared memory architectures, the cache coherence protocol needs to be able to work in the absence of a global broadcast mechanism. Directory based schemes are a possible solution in this environment.This paper describes a new distributed directory cache coherence protocol based on a linked-list of caches. The information about which caches have copies of the data is decentralized and distributed among the cache lines. Our implementation, like the fully mapped directory scheme, tracks any number of cache copies and never requires invalidates to be sent to all caches in the system. It has a lower cost and better network traffic characteristics than the fully mapped directory based coherence scheme for expected memory and cache sizes. In the fully mapped scheme, the size of the memory required to hold the state information is O(MN), where M is the size of main memory and N is the number of caches. In our scheme, on the other hand, the size of the memory required to hold the state information is only O(M log N). We allow adaptive routing (so that network performance may be more robust) and do not assume that the network connecting caches preserves the order of messages. The network traffic generated for invalidations is reduced by a factor of two in our implementation compared to a fully mapped directory scheme for networks that do not preserve the order of messages. An important feature of this protocol is that locks can be supported very efficiently with minimal extra cost.

KSL Technical Report ID: KSL-89-72
Facts about Design and Implementation of a Distributed Cache Coherence ProtocolRDF feed
Abstract Cache coherence is an important well known … Cache coherence is an important well known problem in shared memory multiprocessor systems. If multiple caches are allowed to simultaneously have copies of a given memory location, a mechanism must exist to ensure that all copies remain consistent when the contents of that memory location are modified. The cache coherence problem may be solved through hardware or software. Hardware based protocols to solve the cache coherence problem are well understood for bus based shared memory architectures. However the shared bus limits the number of processors that can be connected to the bus without saturating it. To support scalable shared memory architectures, the cache coherence protocol needs to be able to work in the absence of a global broadcast mechanism. Directory based schemes are a possible solution in this environment.This paper describes a new distributed directory cache coherence protocol based on a linked-list of caches. The information about which caches have copies of the data is decentralized and distributed among the cache lines. Our implementation, like the fully mapped directory scheme, tracks any number of cache copies and never requires invalidates to be sent to all caches in the system. It has a lower cost and better network traffic characteristics than the fully mapped directory based coherence scheme for expected memory and cache sizes. In the fully mapped scheme, the size of the memory required to hold the state information is O(MN), where M is the size of main memory and N is the number of caches. In our scheme, on the other hand, the size of the memory required to hold the state information is only O(M log N). We allow adaptive routing (so that network performance may be more robust) and do not assume that the network connecting caches preserves the order of messages. The network traffic generated for invalidations is reduced by a factor of two in our implementation compared to a fully mapped directory scheme for networks that do not preserve the order of messages. An important feature of this protocol is that locks can be supported very efficiently with minimal extra cost. very efficiently with minimal extra cost.
Author Manu Thapar and Bruce A. Delagi  +
Bibtype techreport  +
Has author Manu Thapar and Bruce A. Delagi  +
Has identifier KSL-89-72  +
Has publishing details April,1990  +
Has title Design and Implementation of a Distributed Cache Coherence Protocol  +
Has where published KSL-89-72  +
Has year 1990  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-89-72  +
Month April  +
Number KSL-89-72  +
Process note NO  +
Title Design and Implementation of a Distributed Cache Coherence Protocol  +
Year 1990  +
Retrieved from "http://tw.rpi.edu/wiki/Design_and_Implementation_of_a_Distributed_Cache_Coherence_Protocol"
Personal tools