Victimization of clean data blocks

Details Victimization of clean data blocks Victimization of clean data blocks

1997-10-24

2001-03-13

Thai, Tuan V. (Department: 2752)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S003000, C711S130000, C711S144000, C711S146000

Reexamination Certificate

active

06202126

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates generally to computer systems and more specifically to the displacement of data elements from cache subsystems in computer systems.
As it is known in the art, a multiprocessing computer system includes a plurality of central processing units (CPUs), a main memory and system control logic. Each CPU typically includes a cache for storing data elements that are accessed most frequently by the CPU. Each CPU may also include victim buffers for temporarily storing data which is displaced from its cache. The system control logic provides a communication interconnect for data and commands sent between the CPUs and between the CPUs and main memory. The system control logic often includes a duplicate tag store and an arbitration circuit. The arbitration circuit produces a serial stream of command references which is applied to all CPUs. The duplicate tag store holds status information pertaining to data stored in the caches coupled to each of the CPUs. The duplicate tag store is coupled with the arbitration logic so that it may operate on the serial stream of commands. It is therefore implemented remote from the CPUs.
Each CPU may issue a variety of commands to the system control logic dependent upon the current cache status of a given data element and the operation the CPU needs to perform on that data element. If a CPU needs to access a copy of a data element that is not already in its cache, it issues a “read-miss” command to the system control logic. That command will retrieve an up-to-date copy of the requested data element and store it in the CPU's cache. The associated status information will indicate that the data is in an unmodified state. If the CPU needs to modify a data element that is not already in its cache, it issues a “read-miss-modify” command to the system control logic. That command will retrieve an up-to-date copy of the requested data element and store it in the CPU's cache. The associated status information for this data block will indicate that the data is in an exclusive, modified state. If the CPU needs to modify a data element that is already in its cache but in a nonexclusive or unmodified state, it issues a “change-to-dirty” command to the system control logic. This will change the state of the data element to the exclusive, modified state by invalidating each copy of the data stored in other CPU's caches.
When a CPU issues a “read miss” or “read miss modify” command to the system control logic, the requested data element may displace a previously cached data element from the CPU's cache. This displaced element is referred to as a “victim”. If the victim is in a modified state, then it is considered a “most up to date” version of the data element in the computer system. More particularly, if a victim is in the exclusive, modified state then it is the only up to date copy of the data element in the computer system. Therefore, to maintain proper system operation, all modified victims must be written back to main memory. A modified victim, exclusive or non-exclusive, is referred to as a “dirty-victim”.
When a CPU issues a “read-miss” or “read-miss-modify” command that displaces a dirty-victim, the CPU places a copy of the dirty-victim data into a victim buffer and issues both a read-miss or read-miss-modify command and a victim command to the system control logic together. A read-miss command and its associated victim command are referred to as a readmiss/victim command pair. A read-miss-modify command and its associated victim command are referred to as a readmissmod/victim command pair.
The system control logic receives commands from a plurality of CPUs. The system control logic includes an arbitration circuit through which these commands arbitrate for access to the system's duplicate tag store and main memory resources. The output stage of this arbitration circuit, referred to as the “system serialization point”, produces a serial stream of CPU commands which are issued directly to the duplicate tag and the main memory. For each command in this serial stream, the system control logic performs a duplicate tag store lookup operation. This operation returns the cache status for each CPU, for the specific data element referenced by the command. Specifically, this lookup operation will return status information indicating which CPUs have copies of the referenced data element and which copies are the most up-to-date version of the data element. Therefore, if memory does not have the most up to date version of the data in the system, the duplicate tag store will indicate which CPU does. When the system is processing a read-miss command, a read-miss-modify command, a readmiss/victim command pair or readmissmod/victim command pair, it uses this information to determine whether to fetch data from main memory or another CPU. If it must fetch data from another CPU, it does so by issuing a message referred to as a “forwarded-read” to that other CPU. When the system is processing a read-miss-modify or change-to-dirty command, it uses the duplicate tag store information to determine which CPUs need to be issued messages to remove any copies of the referenced data element that are about to become invalid. These messages are referred to as “invalidates”. Forwarded-read messages (probe read message) and invalidate messages (probe invalidate messages) are together referred to as “probe” messages. Probe messages are issued to their target CPUs through a set of “probe queues” in the system control logic. Each CPU is associated with one probe queue from that set of probe queues.
The system control logic also executes a duplicate tag store update operation for each command in the serial stream. For each command, the update operation will modify the state of the duplicate tag entries for both the CPU that issued the command and any CPUs to which this command caused probe messages to be issued. When the system control logic is processing read-miss or read-miss-modify commands, it updates the duplicate tag store state of the issuing CPU to indicate that the referenced block is now an element of the issuing CPU's cache. When the system control logic is processing a readmiss/victim command pair, it updates the state of the issuing CPU to indicate that the referenced block is now an element of the issuing CPU's cache, and also to indicate that the victim block is no longer a member of the issuing CPUs cache.
When the arbitration circuit of the system control logic issues a command to the duplicate tag store, it simultaneously issues the same command to the main memory of the computer system. If the command is a read-miss command, a read-miss-modify command, a readmiss/victim command pair or a readmissmod/victim command pair, and the duplicate tag indicates that the most up-to-date copy of the data element is in memory, then the system control logic will return a copy of the data element from main memory to the requesting CPU via a “fill” message. Similarly, if the duplicate tag indicates that the most up-to-date copy of the data element is in another CPU's cache, then the system control logic will return a copy of the data element from the other CPU to the requesting CPU via a “fill” message. Fill messages are returned to their issuing CPUs via a set of “fill queues” in the system control logic. Each CPU is associated with one fill queue from that set.
The fill queue and the probe queue associated with a given CPU operate independent from each other and are processed at different rates by the associated CPU. As such, it is possible for a probe message in a CPUs probe queue to be processed by the CPU after a fill message from the CPU's fill queue that was generated by a command that issued to the system serialization point later than the command that generated the probe. The processing of this fill message before the probe message is referred to as “bypassing”.
In such a computer system it is possible that a first CPU issues a readmiss/victim command pair to the system control logic that vict

Affiliated with

Also associated with

Rating

Victimization of clean data blocks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Victimization of clean data blocks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Victimization of clean data blocks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2481097