Browse Prior Art Database

Cache Coherency based on multilevel Directories Disclosure Number: IPCOM000010839D
Original Publication Date: 2003-Jan-24
Included in the Prior Art Database: 2003-Jan-24
Document File: 3 page(s) / 8K

Publishing Venue



This patent proposal describes a method for maintaining the cache coherence in a shared-memory multiprocessor. A directory based cache coherence protocol was selected. Several versions of a two level directory are described. The second level directory increases the hit-rate for the same size directory, or allow smaller directories to achieve the same hit rate

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 38% of the total text.

Page 1 of 3

Cache Coherency based on multilevel Directories

The system consists of processing nodes, each with a portion of the shared-memory. The nodes are connected through a network (of any kind). We propose a directory-based protocol to manage the cache coherence. The directories used for this purpose are called GAD, for 'give-away-directory'. A GAD record contains the address, the state of the line (valid bit, dirty bit, and MESI state), and a pointer to identify the remote nodes who have copies of the line. This pointer may be implemented in an n-bit-vector for n nodes, or in any other way. The current implementation uses a pointer to the last copy and an extra bit for 'multiple remote copies'.

    In order to reduce the size of the directories, we introduce a multilevel directory structure.

    In the current implementation, the first level GAD records line addresses, the second level GAD records page addresses. In general, the multilevel directories introduced in this paper, require that a higher level directory records the address of a bigger portion of the memory than the lower level.

    Advantage of the invention: A smaller directory achieves the same system performance as a state of the art system with a bigger directory.

    All functions described here are planned to be built in hardware. However, some may also be implemented in software (internal code).

    The innovative idea is the multilevel GAD. As said, in our current implementation it is a two level GAD. The first level is called GAD-1, the second GAD-2. The structure of the GAD directories is similar to that of a cache directory. They are addressed using a hash function of the address.

    Each node owns a portion of the shared-memory. For this range of addresses, the GAD (GAD-1 or GAD-2) records the existence of remote copies (i.e.: copies in other nodes). Whenever a node accesses an address for the first time, the data will be loaded into the cache of the node. If the owner of the data (called Memory Master) is in another node, and if the Memory Master has not given away this line to any other node, it allocates a new entry in the GAD-1. This entry records that the subject line is given to the requesting node with the requested access rights.

    The GAD-2 comes into play when a new request requires an old GAD-1 entry to be replaced (overwritten) because the replacement algorithm selects a GAD-1 entry that is still valid.

    Let this 'to be replaced' entry be for line Lx given to node Ny as read-only. This entry now becomes a candidate to be written into GAD-2. For an allocation of the appropriate GAD-2 entry, it must fulfill the following requirements:
a. There must be at minimum Tn (threshold number) of GAD-1 entries for lines in page Px (Lx being a line in page Px). Tn is a static register value (machine configuration).
b. All Tn entries must have Ny as the only remote node.
c. All Tn entries must have read-only access rights. An entry in the GAD-2 is invalidated when a different node than node Ny...