Browse Prior Art Database

Associative Scheme for Cache Coherence in Multi-Processors

IP.com Disclosure Number: IPCOM000117728D
Original Publication Date: 1996-May-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 193K

Publishing Venue

IBM

Related People

Deshpande, SR: AUTHOR [+2]

Abstract

This invention relates to the problem of cache consistency in shared memory multiprocessors. Solutions to the cache consistency problem can be broadly classified into two categories: 1. Snoopy schemes that rely on a broadcast medium (such as a bus); and, 2. Directory based schemes used mainly in MP's with a switch/network as the processor-memory interconnect. Directory based schemes use a coherence protocol and a random access memory (either SRAM or DRAM) structure which tracks the use of all blocks in main memory by the caches in the system. Thus, there is an entry for every block in main memory. This makes the directory very large. For example, a 2GB main memory and a block size of 256B needs a directory with 8 million entries.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 31% of the total text.

Associative Scheme for Cache Coherence in Multi-Processors

      This invention relates to the problem of cache consistency in
shared memory multiprocessors.  Solutions to the cache consistency
problem can be broadly classified into two categories: 1.  Snoopy
schemes that rely on a broadcast medium (such as a bus); and, 2.
Directory based schemes used mainly in MP's with a switch/network as
the processor-memory interconnect.  Directory based schemes use a
coherence protocol and a random access memory (either SRAM or DRAM)
structure which tracks the use of all blocks in main memory by the
caches in the system.  Thus, there is an entry for every block in
main memory.  This makes the directory very large.  For example, a
2GB main memory and a block size of 256B needs a directory with 8
million entries.  The width of each entry is determined by whether
one is using a limited directory or a full-map directory.  A limited
directory scheme uses fewer bits than a full-map directory.  For
example, Rio Bravo requires 40 bits per entry for a limited directory
and 160 bits per entry for a full-map scheme.  This implies a
directory size of 40MB per module for the limited directory and 160MB
per module for the full-map scheme.  Thus, these directories form a
significant portion of the cost of the system and also affect the
packaging of the main memory subsystem.

      This disclosure proposes a directory structure that
significantly reduces the number of directory entries required
without affecting the cache coherence protocol.  First, notice that
it is not necessary to maintain an entry in the directory for every
block of main memory.  It is sufficient to maintain an entry for
every cached block.  In Rio Bravo, for example, there are 16 caches
each with 2MB for a total of 32MB of cache.  A single main memory
module contains 2GB.  At any given time, at most 32MB (128K blocks)
of this main memory module can be cached.  Thus, the directory could
have 128K entries instead of 8M entries.  However, since each block
of the main memory module does not have a dedicated entry, the
directory has to be organized as an associative memory much like the
cache in the processor.

      The directory is logically organized as shown in Figs. 1
and 2.  Each entry consists of an address tag and protocol field.
The address tag is identical with the cache address tag.  Each memory
module has its own directory.  Assume N caches, C lines per cache,
and M memory modules.  Each directory contains N*C entries that are
divided into N equal partitions.  Partition i has an entry for every
block from the particular memory module that is in cache i.  Thus,
each partition in a directory partially reflects the contents of the
corresponding cache directory.  The union of the ith partitions of
every directory completely reflects the contents of the ith cache
directory.  Each partition is organized exactly like the
corresponding cache directory.  For e...