US 5,428,761 A · System for achieving atomic non-sequential multi-word operations in shared memory

Abstract

A computer system provides transactional memory operations, in which a selected data item in a shared memory is referenced by a CPU in local storage (such as a write-back cache). The CPU performs some operation to alter or use the data item while it is in local memory, and meanwhile monitors the bus to the shared memory to see if another processor references the selected location (as by a snoop mechanism); if so, a status bit is toggled to indicate that the transaction must be scrubbed. When the operation has been completed by the CPU, it attempts to "commit" the transaction, and this includes checking the status bit; if the bit has been toggled, the transaction aborts, the data item is invalidated in local memory, and the selected location in shared memory is not affected. If the status bit has not been toggled, the transaction is committed and the altered data item becomes visible to the other processors, and may be written back to the shared memory. To distinguish these transactional memory operations from standard loads and stores to memory, an indication of "transactional" or "not transactional" is added to the local storage, i.e., to a cache line. The transactional memory operations have the characteristics of serializability and atomicity.

Claims28

Dependent claims

A method of operating a computer system having a CPU, local storage for said CPU, a shared memory, and at least one other processor accessing said shared memory, comprising the steps of:

(a) initiating a memory operation by said CPU, including copying a data item that includes multiple words of selected non-contiguous locations in said shared memory to corresponding locations in said local storage, and setting an indication associated with said corresponding locations in said local storage to mark them as being inaccessible by said other processor;
(b) performing an operation on said data item by said CPU to alter at least one or more parts of said data item in said corresponding location in said local storage;
(c) monitoring said shared memory beginning at the time of said copying to detect any access to said data item in said shared memory by said other processor, and altering a status indicator if said other processor (1) reads a location in said shared memory corresponding to a part of said data item that has been altered, or (2) writes to a location in said shared memory corresponding to any part of said data item;
(d) after said step of performing an operation, determining whether said status indicator has been altered, and, if not, changing said indication so that said corresponding locations in said local storage are accessible by said other processor, or, if so, discarding the content of said corresponding locations in said local storage and re-executing steps (a), (b), (c) and (d).

1 more element

A computer system having a CPU, a local storage for said CPU, a shared memory, and at least one other processor accessing said shared memory, comprising:

(a) means for initiating a memory operation by said CPU, including means for copying a data item that includes multiple words of selected non-contiguous locations in said shared memory into corresponding locations in said local storage, and means for setting an indication to mark said corresponding locations in said local storage as being inaccessible by said other processor;
(b) means in said CPU performing an operation on said data item to alter at least one or more parts of said data item in said local storage;
(c) means for monitoring said shared memory beginning at the time of said copying to detect any access to said data item in said shared memory by said other processor, and for altering a status indicator if said other processor (1) reads a location in said shared memory corresponding to a part of said data item that has been altered, or (2) writes to a location in said shared memory corresponding to any part of said data item;
(d) means for determining, after said CPU performs said operation, whether said status indicator has been altered, and, if not, for changing said indication so that said corresponding locations in said local storage are accessible by said other processor, or, if so, for invalidating said corresponding locations in said local storage of said local storage and again initiating said memory operation.

1 more element

A method of managing access by multiple processors to memory shared by the processors, wherein each processor accesses the shared memory by performing steps comprising:

(a) copying multiple words from selected locations in the shared memory into cache lines in a cache memory, and setting first indicators corresponding to the cache lines to make the lines unavailable for write-back operations to the shared memory;
(b) performing an operation upon one or more cache lines to alter the contents of those lines;
(c) monitoring the shared memory beginning at step (a) to detect any access to the selected locations by other processors, and for each cache line, altering a second indicator if any other processor (1) reads from a location in shared memory whose contents were copied into a cache line that was altered, or (2) writes to a location in the shared memory whose contents were copied into a cache line;
(d) after step (b), determining whether the second indicator has been altered, and if not, changing the first indicator so that the cache lines are accessible by all processors, or if so, discarding the contents of the cache lines and re-executing steps (a), (b), (c) and (d).

1 more element

Dependencies are inferred from the claim text.

System for achieving atomic non-sequential multi-word operations in shared memory

Life of this patent

System for achieving atomic non-sequential multi-word operations in shared memory

Life of this patent

Abstract

Claims28