Browse Prior Art Database

Rings of Coherence

IP.com Disclosure Number: IPCOM000113644D
Original Publication Date: 1994-Sep-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 107K

Publishing Venue

IBM

Related People

Chiarot, KA: AUTHOR [+2]

Abstract

This disclosure proposes a linked data structure for storing id's of multiprocessor caches that hold a shared line. The proposed data structure has the property of being self-similar and therefore is simple and uniform to maintain as it grows. It is also scalable so that it can be used in shared memory MPPs: The depth of the data structure grows logarithmically as elements are added to it. Thus, when an invalidation is to be performed, it executes in time proportional to the logarithm of the number of ids in the structure. Although the structure may get disturbed due to deletions of nodes, the structure attempts to heal itself. Procedures for addition and deletion of elements to the structure, global invalidation, and for self-repair are also described herein.

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

Rings of Coherence

      This disclosure proposes a linked data structure for storing
id's of multiprocessor caches that hold a shared line.  The proposed
data structure has the property of being self-similar and therefore
is simple and uniform to maintain as it grows.  It is also scalable
so that it can be used in shared memory MPPs: The depth of the data
structure grows logarithmically as elements are added to it.  Thus,
when an invalidation is to be performed, it executes in time
proportional to the logarithm of the number of ids in the structure.
Although the structure may get disturbed due to deletions of nodes,
the structure attempts to heal itself.  Procedures for addition and
deletion of elements to the structure, global invalidation, and for
self-repair are also described herein.

      The processors in the system are divided into clusters of one
or more.  The clusters communicate via a non-broadcast
interconnection network.  Each cluster has a subset of the
system-wide shared memory.  Each processor within a cluster has a
private cache.  A processor may reference any address in the system's
shared memory space, and thus the reference may be satisfied either
within its cluster or it may have to be routed to a remote cluster to
be satisfied.  A directory structure per cluster is responsible for
maintaining cache coherence between clusters.  The cluster at which a
shared cache line resides is called its "home" cluster or node.

      The directory linkage data structure used to maintain
inter-node coherence is composed of 4 sibling pointers lp, rp, ls,
and rs respectively.  These pointers are ids of nodes that hold the
cache line.  lp and rp are left and right primary ring pointers, and
ls and rs are the left and right pointers for the secondary ring that
the node may engender.  Associated with each pointer is a bit to
indicate whether the pointer is valid.  The head structure is located
in the directory of the home node of the cache line.  It is created
when the first remote cluster requests a cache line.  At the home
node, pointers lp and rp are invalid and are set to null values.  The
diagram in Fig. 1 shows that clusters 1 and 2 currently hold in read
mode a cache line located in the home node 0.  These caches (i.e., 1
and 2) are considered to be siblings of each other and of node 0.

      There is a similar link structure in each of the nodes 1 and 2.
The pointers there are used to create a doubly-linked coherence ring.
Ideally, a doubly-linked ring has 3 members, although it may
occasionally accommodate more.  In Fig. 2 an 8 node coherence
structure is shown.  The Figure als...