US5210848A — Multi-processor caches with large granularity exc…

Claim 1

Independent Claim 398 words

In a tightly coupled multi-processor system of the type comprising a plurality of central processors, a main storage and a storage control element connected to said main storage, each central processor having a buffer control element including a store through cache, a method for providing large granularity locking of exclusivity of a block of data in caches of said central processors comprising the steps of: reading from or writing to said main storage units of data under the control of said storage control element by said buffer control elements in response to requests by said central processors; storing by said buffer control elements in their respective caches a plurality of blocks of data read from said main storage, each of said blocks of data comprising a plurality of cache lines and each cache line having a plurality of units of data; establishing by said storage control element three possible states on a block of data, said states including a temporarily invalid state, a read only state and an exclusive state, the temporarily invalid state being the initial state for all blocks of data in caches of said central processors; recording by said storage control element states of blocks of data for the central processors at the storage control element and the buffer control elements, said recording at the storage control element being in lock tables, one for each central processor, to keep track of ownerships of exclusive states of blocks of data, and said recording at the buffer control elements being in local lock tables to maintain a subset of a corresponding lock table exclusive status of blocks of data for that central processor; enforcing by said storage control element a unique access right to a block of data in a cache for one of said central processors by giving other central processors said temporarily invalid state on said block of data, even though some lines in the block of data may still be resident in caches of said other central processors; and for any central processor trying to access said block of data in a temporarily invalid state, communicating by the accessing central processor with the storage control element to obtain proper authorization, the storage control element changing the temporarily invalid state on the block of data for the accessing central processor to a read only or exclusive state to grant authorization to the accessing central processor.

Claim 2

Dependent Claim 398 words

In a tightly coupled multi-processor system of the type comprising a plurality of central processors, a main storage and a storage control element connected to said main storage, each central processor having a buffer control element including a store through cache, a method for providing large granularity locking of exclusivity of a block of data in caches of said central processors comprising the steps of: reading from or writing to said main storage units of data under the control of said storage control element by said buffer control elements in response to requests by said central processors; storing by said buffer control elements in their respective caches a plurality of blocks of data read from said main storage, each of said blocks of data comprising a plurality of cache lines and each cache line having a plurality of units of data; establishing by said storage control element three possible states on a block of data, said states including a temporarily invalid state, a read only state and an exclusive state, the temporarily invalid state being the initial state for all blocks of data in caches of said central processors; recording by said storage control element states of blocks of data for the central processors at the storage control element and the buffer control elements, said recording at the storage control element being in lock tables, one for each central processor, to keep track of ownerships of exclusive states of blocks of data, and said recording at the buffer control elements being in local lock tables to maintain a subset of a corresponding lock table exclusive status of blocks of data for that central processor; enforcing by said storage control element a unique access right to a block of data in a cache for one of said central processors by giving other central processors said temporarily invalid state on said block of data, even though some lines in the block of data may still be resident in caches of said other central processors; and for any central processor trying to access said block of data in a temporarily invalid state, communicating by the accessing central processor with the storage control element to obtain proper authorization, the storage control element changing the temporarily invalid state on the block of data for the accessing central processor to a read only or exclusive state to grant authorization to the accessing central processor.

Claim 3

Dependent Claim 143 words

The method of providing large granularity locking according to claim 1 further comprising the steps of: when a central processor P i attempts to store into a line L in a block of data B and the central processor P i does not have an exclusive state for the block of data B, requesting by the buffer control element for said central processor P i an exclusive state for the block of data B from the storage control element; if this is a first store into said line L since the central processor P i obtained an exclusive state of said block of data B, communicating by said storage control element an XI-invalidate signal for the line L from caches at other central processors, a line being XI-invalidated from a cache only when it is actually modified remotely so as to minimize invalidates.

Claim 4

Dependent Claim 44 words

The method of providing large granularity locking according to claim 2 wherein the step of communicating the XI-invalidate signal is also done when the storage control element grants an exclusive state for the block of data B to the central processor P i .

Claim 5

Dependent Claim 73 words

The method of providing large granularity locking according to claim 2 wherein the step of enforcing comprises the step of requesting by the buffer control element for the central processor P i a read only state for the block of data B from the storage control element before accessing, even for a cache hit, when a central processor P i fetches data in a block of data B with a temporarily invalid state.

Claim 6

Dependent Claim 136 words

The method of providing large granularity locking according to claim 4 further comprising the steps of: when the storage control element receives an exclusive request from a central processor P i for a block of data B, signaling by the storage control element a temporarily invalid state for the block of data B to all remote central processors before granting an exclusive state for the block of data B to the central processor P i ; and if a remote central processor P j (j≠i) owns the exclusive state for the block of data B, communicating by the storage control element to the central processor P j a temporarily invalid state for the block of data B before granting the exclusive state for the block of data B request to the central processor P i .

Claim 7

Dependent Claim 106 words

The method of providing large granularity locking according to claim 5 further comprising the steps of: when the storage control element receives a read only request for a block of data B from a central processor P i , granting by the storage control element the request right away if no remote central processor owns an exclusive state for the block of data B; otherwise, granting by the storage control element the read only request after communicating to a remote control processor P j to turn its exclusive state for the block of data B into a read only state for the block of data B.

Claim 8

Dependent Claim 160 words

The method of providing large granularity locking according to claim 1 wherein the step of recording at the storage control element comprises the steps of: maintaining a bit vector CH (change-local) for each block of data B locked exclusive for a central processor P i , when it is actually stored by the central processor P i since the last time the exclusive state for the block of data B is granted to the central processor P i ; initializing the vector CH to zero bits when central processor P i acquires the exclusive state for the block of data B; and when a store into a line L of block of data B is received by the storage control element, sending out by the storage control element XI-invalidate signals to remote caches if the vector CH associated with the line L is OFF, and then turning the vector CH for the line L ON by the storage control element.

Claim 9

Dependent Claim 385 words

A tightly coupled multi-processor system comprising: a plurality of central processors; a main storage; storage control means connected to said main storage and including a plurality of lock tables corresponding to said plurality of central processors, said lock tables maintaining a record of exclusive states of blocks of data by respective ones of said plurality of central processors; a plurality of buffer control elements, one for each of said central processors, the buffer control element of each central processor reading from or writing to said main storage units of data via said storage control means, each said buffer control element including a cache storing a plurality of blocks of data, each of said blocks of data comprising a plurality of cache lines and each cache line having a plurality of units of data, said buffer control element including local lock tables which maintain a subset of a corresponding lock table exclusive status of blocks of data for that central processor; said storage control means establishing three possible states on a block of data, said states including a temporarily invalid state, a read only state and an exclusive state, the temporarily invalid state being the initial state for all blocks of data in caches of said central processors; said storage control means further recording states of blocks of data for the central processors in said plurality of lock tables at the storage control element and said local lock tables at the buffer control elements to keep track of ownerships of exclusive states of blocks of data; said storage control means enforcing a unique access right to a block of data in a cache for one of said central processors by giving other central processors said temporarily invalid state on said block of data, even though some lines in the block of data may still be resident in caches of said other central processors and, for any central processor trying to access said block of data in a temporarily invalid state, communicating with the accessing central processor and changing the temporarily invalid state on the block of data for the accessing central processor to a read only or exclusive state to grant authorization to the accessing central processor on the block of data to provide large granularity locking of exclusivity of blocks of data in said caches.

Claim 10

Dependent Claim 385 words

A tightly coupled multi-processor system comprising: a plurality of central processors; a main storage; storage control means connected to said main storage and including a plurality of lock tables corresponding to said plurality of central processors, said lock tables maintaining a record of exclusive states of blocks of data by respective ones of said plurality of central processors; a plurality of buffer control elements, one for each of said central processors, the buffer control element of each central processor reading from or writing to said main storage units of data via said storage control means, each said buffer control element including a cache storing a plurality of blocks of data, each of said blocks of data comprising a plurality of cache lines and each cache line having a plurality of units of data, said buffer control element including local lock tables which maintain a subset of a corresponding lock table exclusive status of blocks of data for that central processor; said storage control means establishing three possible states on a block of data, said states including a temporarily invalid state, a read only state and an exclusive state, the temporarily invalid state being the initial state for all blocks of data in caches of said central processors; said storage control means further recording states of blocks of data for the central processors in said plurality of lock tables at the storage control element and said local lock tables at the buffer control elements to keep track of ownerships of exclusive states of blocks of data; said storage control means enforcing a unique access right to a block of data in a cache for one of said central processors by giving other central processors said temporarily invalid state on said block of data, even though some lines in the block of data may still be resident in caches of said other central processors and, for any central processor trying to access said block of data in a temporarily invalid state, communicating with the accessing central processor and changing the temporarily invalid state on the block of data for the accessing central processor to a read only or exclusive state to grant authorization to the accessing central processor on the block of data to provide large granularity locking of exclusivity of blocks of data in said caches.

Claim 11

Dependent Claim 85 words

The tightly coupled multi-processor system according to claim 8 wherein said buffer control element for each processor comprises means for requesting from said storage control means a read only or exclusive state for a block of data for t he corresponding central processing unit before accessing the block of data, even for a cache hit, when the central processor attempts to fetch data in a block of data with a temporarily invalid state as indicated by the local lock table for the buffer control element.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1996-05-10	1996-11-09	1997-05-11	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2000-05-10	2000-11-09	2001-05-11	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2004-05-10	2004-11-09	2005-05-11	$7700.00	Window Closed / Lapsed

Multi-processor caches with large granularity exclusivity locking

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag