JP5116418B2 - Method for processing data in a multiprocessor data processing system, processing unit for multiprocessor data processing system, and data processing system - Google Patents

Description

The present invention relates to improved multiprocessor data processing systems and, more particularly, to an improved coherency management hierarchy cache system in multiprocessor data processing system.

Conventional symmetric multiprocessor (SMP) computer systems, such as server computer systems, typically all connect to a system interconnect bus that includes one or more address, data, and control buses A plurality of processing units. System memory connected to the system interconnect bus represents the lowest level of volatile memory in a multiprocessor computer system and is generally accessible for read and write access by all processing units. In order to reduce the access latency for instructions and data residing in system memory, each processing unit is typically further assisted by its respective multi-level cache hierarchy, with one at the lower level of that hierarchy being one. Shared by one or more processor cores.

Multiple processor cores can request write access to the same cache line of data, and the modified cache line is not directly synchronized with system memory, so the cache hierarchy of a multiprocessor computer system It will implement a cache coherency protocol to ensure at least a minimum level of coherency between "view (view)" of the various processor cores for the content of system memory. Specifically, cache coherency is at least when a processing unit accesses a copy of a memory block and then an updated copy of that memory block, after which the processing unit retrieves an old copy of that memory block. Need to be inaccessible again.

Cache coherency protocols are commonly used to communicate a set of cache states stored in association with cache lines stored at each level of the cache hierarchy, and cache state information between cache hierarchies. Define a set of coherency messages. In a typical implementation , the cache state information takes the form of the well-known MESI (Modified, Exclusive, Shared, Invalid) protocol or a variant thereof, and the coherency message is the source and / or destination of the memory access request. It represents the transition of coherency state defined by the protocol in the cache hierarchy. The MESI protocol is one of four states of data cache lines: M (Modified), E (Exclusive), S (Shared), or I (Invalid). Allows to be tagged by. The “modified” state means that the coherency granule is only valid in the cache that stores the modified coherency granule, and that the modified coherency granule value is written to system memory. Indicates that it is not included. Of all the caches in the memory hierarchy, when the coherency granule is currently represented as “exclusive”, only that cache holds the coherency granule. However, the data in the “exclusive” state is consistent with the system memory. If a coherency granule is marked as “shared” in the cache directory , the coherency granule is associated with the associated cache and possibly one or more other caches in the memory hierarchy. All copies of that coherency granule are consistent with system memory. Finally, the “invalid” state represents that both the data and address associated with the coherency granule are invalid.

The state in which each coherency granule (eg, cache line) is set includes the previous state of the data in that cache line and the type of memory access request received from the requesting device (eg, processor). And depends on both. Thus, maintaining a memory hierarchy in the system requires the processor to communicate messages throughout the system that represent the intent to read from or write to the memory location. For example, when a processor wants to write data to a memory location, the processor must first inform all other processing elements that it intends to write data to that memory location and perform the write operation Permission to do so must be obtained from all other processing elements. Grant message requesting processor has received represents that would be in or disable that copies all of the other caches of the contents of the memory location is invalidated, whereby the other Guarantees that these processors will not accidentally access their stale local data.

In some systems, the cache hierarchy includes at least two levels of cache, one or more such as a level 1 (L1) or higher level cache, and a level 2 (L2) cache and a level 3 (L3) cache. (The L2 cache is a higher level cache with respect to the L3 cache). The L1 cache is usually a dedicated cache associated with a specific processor core in the MP system. The processor core first tries to access data in its L1 cache. If not found the requested data is in the L1 cache, the processor core, one or more lower-level cache for the requested data (e.g., level 2 (L2) or level 3 (L3) cache) the to access. In many cases, the lowest level cache (eg, L3 cache) is shared among several processor cores.

  Typically, when the combined class of higher level caches is full, data lines are "evicted" or written out to lower level caches or to system memory for storage. However, in any memory hierarchy, multiple copies of the same data in the memory hierarchy can exist simultaneously. The policy of draining the line to give more space to the higher level cache results in an update to the lower level cache, which also includes an update of coherency state information in the lower level cache directory. .

Traditionally, the cache coherency protocol generally copies the coherency state from the higher level cache to the lower level cache when the cache line is drained from the higher level cache to maintain cache coherency. Was assumed. The present invention, in case, and other data processing scenarios cast out takes place, by appropriately defining the coherency status and coherency state transitions in the cache hierarchy, to achieve enhanced performance with respect to the data processing system Is recognized as being possible.

  It is an object of the present invention to provide an improved processing unit, data processing system, and method for performing coherency management in a multiprocessor data processing system.

According to one embodiment of the present invention, a data processing system includes at least a first coherency domain and a second coherency domain, and the first coherency domain includes system memory and cache memory. The method of processing data of the present invention includes the steps of buffering a cache line in a data array of cache memory, the cache line being valid in the data array, and the cache line being non-exclusive to the cache memory. Set the state field in the cache directory of the cache memory to a coherency state to indicate that it is kept and that another cache in the second coherency domain may hold a copy of that cache line Steps.

  All objects, features and advantages of the present invention will become apparent in the following detailed description.

I. Exemplary Architecture Overview Throughout the drawings, the same reference numbers refer to the same or corresponding parts. Referring to FIG. 1, a high level block diagram representing an exemplary data processing system in which the present invention may be implemented is shown. The data processing system is shown as a cache coherent symmetric multiprocessor (SMP) data processing system 100. As shown, the data processing system 100 includes a plurality of processing nodes 102a, 102b for processing data and instructions. The processing node 102 is connected to a system interconnection network 110 for communicating addresses, data, and control information. The system interconnection network 110 can be implemented as, for example, a bus type interconnection network, an exchange type interconnection network, or a hybrid interconnection network.

In the illustrated embodiment, each processing node 102 is implemented as a multi-chip module (MCM) that includes four processing units 104a-104d. Each processing unit is preferably implemented as a respective integrated circuit. The processing units 104 at each processing node 102 are connected to communicate with each other and the system interconnect network 110 by a local interconnect network 114. The local interconnect network 114 may be implemented using, for example, one or more buses or switches, like the system interconnect network 110.

  As shown in FIG. 2, each processing unit 104 includes an integrated memory controller (IMC) 206 connected to a respective system memory 108. Data and instructions residing in system memory 108 can generally be accessed and modified by a processor core in any processing unit 104 of any processing node 102 in data processing system 100. In another embodiment of the present invention, one or more memory controllers 206 (and system memory 108) may be connected to the system interconnect network 110 or the local interconnect network 114.

1 that the SMP data processing system 100 of FIG. 1 may include many additional non- illustrated components such as interconnect bridges, non-volatile storage devices, ports for connection to networks or accessory devices, and the like. It will be apparent to those skilled in the art. Such additional components are not shown in FIG. 1 and will not be described further as they are not necessary for an understanding of the present invention. However, it should be understood that the enhancements provided by the present invention are applicable to cache-coherent data processing systems of various architectures and are not limited to the general purpose data processing system architecture shown in FIG. is there.

Referring to FIG. 2, a more detailed block diagram of an exemplary processing unit 104 according to the present invention is shown. In the illustrated embodiment, each processing unit 104 that may be conveniently implemented as a single integrated circuit includes four processor cores 200a-200d for processing instructions and data independently of one another. In one preferred embodiment, each processor core 200 supports the execution of multiple (eg, two) simultaneous hardware threads.

  The operation of each processor core 200 is supported by a multi-level volatile memory subsystem that has a shared system memory 108 at the lowest level and data residing in cacheable addresses. And two or more levels of cache memory at the upper level for caching instructions. In the illustrated embodiment, a cache memory hierarchy exists within each processor core 200 for each store-through level 1 (L1) cache (not shown) dedicated to that processor core, each processor core. Each store in level 2 (L2) cache 230 dedicated to 200 and an L3 victim cache 232 for buffering L2 castouts. In the illustrated embodiment, processor cores 200a and 200d share their respective L3 cache 232a, and processor cores 200b and 200c share their L3 cache 232b. Of course, in alternative embodiments, each of the processor cores 200 may have its own L3 cache 232. In at least some embodiments, including those shown in FIG. 2, L3 caches 232a, 232b are further interconnected to allow data exchange. This data exchange is such that one L3 cache 232 holds one of its cache lines to the other L3 in order to store data likely to be accessed by the processor core 200 in the cache hierarchy of the processing unit 104 for as long as possible. Including allowing castout to cache 232.

Each processing unit 104 includes an instance of response logic 210 that implements part of a distributed coherency signaling mechanism that maintains cache coherency within the data processing system 100. In addition, each processing unit 104 includes an instance of interconnect logic 212 for managing communication between the processing unit 104 and the local interconnect network 114 and the system interconnect network 110. Each of L2 cache 230 and L3 cache 232 is connected to interconnect logic 212 to allow participation in data and coherency communications via interconnect networks 110 and 114 of FIG. Finally, each processing unit 104 includes an integrated I / O controller 214 that supports connection of one or more I / O devices, such as I / O device 216. I / O controller 214 may issue operations on local interconnect network 114 and / or system interconnect network 110 in response to requests by I / O device 216.

  Referring now to FIG. 3, a more detailed block diagram of the processor core 200 and L2 cache 230 in the processing unit 104 of FIG. 2 is shown. As shown, the processor core 200 includes an instruction sequence unit (ISU) 300 for fetching and ordering instructions for execution, one or more execution units 302 for executing instructions, and L1. A cache 306 is included.

Execution unit 302 includes a load store unit (LSU) 304 that executes memory access instructions (eg, load and store instructions) to cause data to be loaded from and stored in memory. When performing such memory access operations through the implementation of a coherency protocol by the memory subsystem, coherent view of memory contents is maintained.

In accordance with the present invention, the L1 cache 306, which may include separate L1 data and instruction caches, has cache coherency points for other processor cores 200 placed under the L1 cache 306, in the illustrated embodiment, L2 It is implemented as a store-through cache, which means that it is placed in the cache 230. Thus, the L1 cache 306 only maintains a valid / invalid bit rather than maintaining true cache coherency state for its cache line.

The L2 cache 230 includes a data array 310 that stores instruction and data cache lines, and a cache directory 312 of the data array 310. As in a normal set associative cache, a memory block in system memory 108 is assigned to a specific congruence class in data array 310 using a predetermined index bit in the system memory (real) address. Mapped. In one embodiment, the standard memory block for a coherency system is set to a 128 byte cache line. A particular memory block or cache line stored in the data array 310 is recorded in the cache directory 312. Note that cache directory 312 includes one directory entry for each cache line in data array 310. As will be apparent to those skilled in the art, each directory entry in the cache directory 312 is a tag that specifies a particular cache line stored in the data array 310 utilizing at least a portion of the corresponding real address. It includes a field 314, a state field 316 representing the coherency state of the cache line, and an LRU (least recently used) field 318 representing the replacement order for that cache line with respect to other cache lines in the same congruence class

As further shown in FIG. 3, the L2 cache 230 also includes a cache controller 330 that controls the data and coherency operations of the L2 cache 230. Cache controller 330, a plurality of read-claims to service and simultaneously independently load received from the processor core 200 (LD) request and store (ST) requests the related (Read-Claim: RC) machine 332, and is issued by the related to the processor core 200 other than the processor core and "snooped" from local interconnect network 114 remote memory access requests independently and simultaneously to service A plurality of snoop (SN) machines 334. As will be apparent, servicing memory access requests by the RC machine 332 may require replacement or invalidation of memory blocks in the data array 310. Accordingly, the cache controller 330 also includes a plurality of CO (castout) machines 336 that manage the removal or write-back of memory blocks from the data array 310.

Referring now to FIG. 4, a more detailed block diagram of an embodiment of an L3 cache according to the present invention is shown. As can be seen by comparing FIGS. 3 and 4, the L3 cache 232 that acts as a victim cache for buffering L2 castouts is configured similarly to the L2 cache 230 of FIG. Accordingly, the L3 cache 232 includes a set associative data array 360, a cache directory 362 for the contents of the data array 360, and a cache controller 380.

Each directory entry in the cache directory 362 represents a tag field 364 that specifies a particular cache line stored in the data array 360 using a portion of the corresponding real address, representing the coherency state of the cache line. It includes a status field 366 and an LRU (minimum frequency of use) field 368 representing the replacement order for that cache line with respect to other cache lines in the same congruence class. The cache controller 380 includes a plurality of snoop (SN) machines 384 and a plurality of castout (CO) machines 386 as described with reference to FIG. Instead of the RC machine, the cache controller 380 includes a plurality of read (RD) machines 382 that service data requests for the vertically connected L2 cache 230.

II. Exemplary Operation Referring now to FIG. 5, a space-time diagram of an exemplary operation through the local interconnect network 114 or system interconnect network 110 of the data processing system 100 of FIG. 1 is shown. Although the interconnect networks 110, 114 are not necessarily bus-type interconnect networks, operations transmitted over one or more local interconnect networks 114 and / or system interconnect networks 110 are referred to herein as "buses". A distinction is made between CPU requests, referred to as “operations”, which are transmitted between the processor core 200 and the cache memory in its own cache hierarchy.

Bus operations illustrated issues a request 402 via the RC machine 332 or I / O controller master (M) 400 is a local interconnection network 114, such as 214 and / or system interconnect network 110 of the L2 cache 230 To start when. Request 402 preferably includes a transaction type representing the type of access desired and a resource identifier (eg, real address) representing the resource to be accessed by the request. Desirable general types of requests include those shown in Table 1 below.

Request 402 is received by snoop machine 412, such as snoop machine 334 in L2 cache 230, snoop machine 384 in L3 cache 232, and memory controller 206 (FIG. 2). In general, a few exceptions, the snoop machine 384 snoop machine 334 and connected L3 cache 232 in the same L2 cache 230 and RC machines 332 making the request 402 does not snoop request 402 (i.e. In general, there is no self-snooping). Since the request 402, only if it can not be internally service by the processing unit 104, since transmitted over the local interconnect network 114 and / or system interconnect network 110. Each snooper 412 that receives the request 402 may provide a respective partial response 406 that represents at least that snooper's response to the request 402. Partial memory controller 206, for example, based on whether the memory controller 206 whether responsible for the request address, and it has the resources available for the requested service, to be supplied Determine the dynamic response 406. L2 or L3 cache, for example, potential uses of the L2 cache directory, the availability of a processing request to be snoop machine, and based on the associated coherency status and request address in the cache directory, parts thereof The dynamic response 406 can be determined.

The partial responses of snooper 412 are logically combined in stages or simultaneously with one or more instances of response logic 210 to determine a system-wide combined response (CR) 410 for request 402. Depending range limits described below (scope restriction), the response logic 210, the combined response 410, giving the master and snoopers of bus operation via a local interconnection network 114 and / or system interconnect network 110, request 402 System wide response to (eg, success, failure, retry, etc.). If CR 410 represents the success of request 402, CR 410 may include, for example, the data source of the requested memory block, the cache state to which the requested memory block is to be cached, and one or more. It may also indicate whether a “clean up” operation is required to invalidate the requested memory block in the current L2 cache 230 or L3 cache 232.

Typically, in response to receiving the combined response 410, one or more master 400 and snoopers 412 performs one or more operations to service the request 402. These operations provide data to the master 400, invalidate or update the coherency state of data cached in one or more L2 or L3 caches, and perform castout operations. , Writing the data back to the system memory 108, etc. If, if required by the request 402, the requested memory block or target memory block, before or after the occurrence of the combined response 410 by response logic 210, is transmitted to the master 400 or from the master 400 obtain.

In the following description, the operations performed by the snooper in response to partial response, as well as the request and / or its combined response snooper 412 to the request, the snooper is directed to request the address specified by the request, the highest point of "coherency (Highest Point of Coherency: HPC) " or " Lowest Point of Coherency (HPC) " Coherency: whether it is LPC) ", or in connection with the one or not even, to be explain. An LPC is defined herein as a memory device or I / O device that acts as a repository for memory blocks. If HPC for the memory block is not present, LPC holds the true image of the memory block, the permission or deny permission requests for generating a copy of the additional cache for that memory block Have. With respect to the general requirements in the embodiment of the data processing system of FIGS. 1 and 2, the LPC will be the memory controller 206 for the system memory 108 that holds the reference memory block. HPC is used herein to cache and modify a memory block's true image (which may or may not be consistent with the corresponding memory block in the LPC). has the authority to the request enable or deny, it is defined as a uniquely identified device. Descriptively, the HPC may provide a copy of the memory block to the requestor in response to an operation that does not modify the memory block. Thus, for a general requirement in the embodiment of the data processing system of FIGS. 1 and 2 , the HPC would be the L2 cache 230, if it exists. We are also possible to use other labels in order to specify the HPC for a memory block, but preferred embodiments of the present invention, so that to be described later with reference to Table 2 below, the L2 cache 230 L2 using the selected cache coherency states in the L3 cache directory 362 of cache directory 312 or L3 cache 232, a HPC for the memory block, when present, designates.

With further reference to FIG. 5, if there is an HPC for the memory block referenced in request 402, the HPC of the memory block in the absence of HPC or the HPC of the memory block in the absence of HPC is the duration of the protection window 404a. It is desirable to be responsible for preventing transfer of ownership of the memory block in response to request 402 during. In the illustrated exemplary scenario in Figure 5, the snooper 412 is HPC for a memory block designated by the request address of the request 402, time or lath Nupa 412 snooper 412 determines its partial response 406 during the protection window 404a which extends to receive a combined response 410, to prevent the transfer of ownership of the requested memory block to the master 400. During the protection window 404a, snooper 412, by supplying a partial response to other requests that specify the same request address, to prevent the transfer of ownership. Incidentally, the partial response prevents the ownership until it has transferred successfully to the master 400, another master to gain ownership. Master 400 similarly initiates protection window 404b to protect ownership of the memory block requested in request 402 following receipt of merge response 410.

III. Data delivery domains normal broadcast-based data processing systems handle both cache coherency and data delivery through broadcast communication. Broadcast communications are transmitted in a typical system through the system interconnect network to at least all memory controllers and cache hierarchies in the system. Compared to other architectures and similar scale systems, broadcast-based system is less access latency, and are useful in providing good data processing and coherency management of the shared memory block.

As broadcast-based systems grow in size, the amount of traffic in the system interconnect network increases, which requires additional bandwidth for communication over the system interconnect network, thus reducing the cost of the system. Means that it will rise rapidly with the scale of the system. That is, a system with m processor cores and an average traffic volume of each processor core is n transactions will have m * n traffic volume, which is the same in a broadcast-based system. This means that the traffic volume increases in a multiply rather than additive manner. In addition to requiring significantly greater interconnect network bandwidth, increasing system size has the secondary effect of increasing access latency. For example, the access latency of the data read, the worst case, the combined response of the farthest lower level cache that holds at request has been shared memory block coherency state (data requested from this condition can be delivered) Limited by waiting time.

In order to reduce the bandwidth requirements and access latency of the system interconnect network while retaining the benefits of broadcast-based systems, multiple L2 caches distributed throughout the data processing system 100 are "special" shared coherency states. Is allowed to keep a copy of the same memory block. In this way, these caches with data intervention between the cache (cache-to-cache data intervention ), it is possible to supply the memory block to the requesting L2 cache 230. In SMP data processing system, such as data processing system 100, in order to implement and distributed source over scan by multiple concurrent to the shared memory blocks, two problems must be addressed. First, the rules that govern the creation of a copy of the memory block must be implemented in a "special" shared coherency state of before mentioned. Second, if there is a snooping L2 cache 230, it manages which snooping L2 cache will supply a shared memory block to the requesting L2 cache 230 in response to, for example, a bus read operation or a bus RWITM operation. There must be a rule to do.

In this specification , all of these issues are addressed through the implementation of the data sourcing domain. As far detail, each domain in the SMP data processing system (Note that domain, one or more lower level to participate in the response to the data request (e.g., is defined to include L2 or L3) cache) is is permissible to include only the cache that holds a particular memory block in the "special" shared coherency state. If the cache exists, the cache will request that the requested memory block for the requesting cache when a bus read type (eg, READ or RWITM) operation is initiated by the requesting cache in the same domain. Responsible for delivering . Although many it is possible to define different domain sizes, in a data processing system 100 of FIG. 1, each processing node 102 (i.e., MCM) that viewed the data delivery domains strike a good convenience. Examples of such “special” shared coherency states (eg, Sl and Slg) are described below with reference to Table 2.

IV. Coherency domain
The implementation of the data delivery domains before mentioned, although improved data access latency, this enhancement is can the size of the system increases, does not address the multiplicative traffic volume of m * n. To reduce the amount of traffic while maintaining broadcast-based coherency mechanism, preferred embodiments of the present invention, prior to the data delivery domains mentioned, each processing node forming a separate coherency domain 10 2 the result (Although it is not however necessary) conveniently a multiple of coherency domain it is possible to implement additionally. Data delivery domains and coherency domains, it is possible to co-exist, need not name necessarily be the case. For convenience in describing the exemplary operation of the data processing system 100, in the following, these coherency domains, assumed to have a boundary defined by the processing node 102.

Implementation of coherency domain, if the request is serviced by the participation of low coherency domain than any coherency domain, by limiting the broadcast communication between domains via a system interconnect network 110, the system Reduce traffic. For example, if the processing unit 104a of processing node 102a has issued should do bus read operation, the processing unit 104a, first, the other coherency domain (e.g., processing node 102b) excluding participants in, its own coherency domain (e.g., processing node 102a) against the participants all in, may choose to broadcast the bus read operation. Broadcast operation in which participants in the same coherency domain as operations master only Ru is transmitted is herein defined as "local operation". If a local bus read operation can be serviced within the coherency domain of processing unit 104a, no further broadcast of the bus read operation is performed. However, if the partial and combined responses to the local bus read operation indicate that the local bus read operation cannot be serviced alone within the coherency domain of processing node 102a, the local coherency domain In addition , it is possible to extend the scope of the broadcast to include one or more additional coherency domains.

In a basic implementation , two broadcast ranges are used: a “local” range that includes only local coherency domains and a “global” range that includes all other coherency domains in the SMP data processing system. Accordingly, in this specification, all the operations that will be transmitted to a coherency domains in SMP data processing system is defined as a "Global Operations". Importantly, local operation or than more extensive range of the Operation (e.g., global operations) regardless of whether is used for operation of the service, the cache coherency, SMP Maintained across all coherency domains in the data processing system. Examples of local and global operations are described in detail in the specification of US patent application Ser. No. 11 / 055,697.

In a preferred embodiment, the range of operations, in one embodiment, the local / global scope indicator which may consist of 1-bit flag (signal), is represented in bus operation. The interconnect logic 212 in the processing unit 104 should forward the operations received via the local interconnect network 114 onto the system interconnect network 110 based on the local / global range indicator (signal) setting in that operation. It is desirable to determine whether or not

V. Therefore to limit the issue of domain indicator unwanted local operation, in order not to waste additional bandwidth on the cause and local interconnect network reducing operation latency, the present invention is related to memory It is desirable to implement a per- memory block domain indicator that indicates whether a copy of the block is cached outside the local coherency domain. Figure 6 shows a first implementation example of a domain indicator in accordance with the present invention. As shown in FIG. 6, system memory 108 which is implemented in dynamic random access memory (DRAM), stores a plurality of memory blocks 500. System memory 108, associated with each memory block 500, stores the Rue error correction code (ECC) 502 and domain indicator 504 is utilized to correct possible errors in the memory block 500. In some embodiments of the present invention, domain indicator 504 identifies a particular coherency domain (i.e., specify the coherency domain or node ID) obtained, but in the following description, domain indicator 504, 1 bit It was assumed to be a label, and if the associated memory block 500 is cached only in the same coherency domain as the memory controller 206 that acts as the LPC, (for example, to represent the "local" ones and assumptions that are) set to "1". Otherwise, the domain indicator 504 is reset (eg, “0” to represent “global”). Setting the domain indicator 504 to represent “local” will not cause any coherency error if setting “global” incorrectly, but may cause unnecessary global broadcast of the operation , that could be incorrectly implemented.

Memory controller 206 for delivering the memory blocks in response to the operation, it is desirable to transmit the domain indicator 504 associated with the requested block.

VI. In an exemplary coherency protocol preferred embodiment, L2 cache 230 and L3 cache 232 uses a variation of the MESI protocol circumferential intelligence. A collection of coherency states is
(1) an indication of whether the cache is an HPC for a memory block;
In addition , the following three attributes are displayed.
(2) the cached copy, its is unique among the cache in the memory hierarchy level (i.e., only a cached copy) whether display,
(3) cache, whether to provide a copy of the memory block to the master's request, and when the or may provide it display,
(4) An indication of whether the cached image of the memory block is consistent with the corresponding block in the LPC.
These four attributes are represented in the coherency protocol state summarized in Table 2 below.

In an embodiment of a data processing system 100 described with reference to FIG. 1, domain indicator is received by L2 / L3 cache 230 along with the memory blocks associated, optionally, the data with its memory block Stored in arrays 310, 360. This configuration allows the simplified data flow for domain indicator Suruga, first L2 cache 230, the requested second L2 of the memory blocks in different coherency domain by supplying when responding to RWITM operation of the cache 230, any "global" indicator, has not been cached in the local coherency domain. Therefore, in order to determine whether or not the child only cached in memory block Gallo Karu is known, it shall access Shinano the LPC. As a result, if, HPC for the memory block, if receive remote coherency bus RWITM operation that the requesting of domains (or other storage modify operation), the system caches the requested memory block Retry including retry cast out and bus RWITM operation - responds with a push (retry-push). As will be apparent, it is desirable to eliminate the latency and bandwidth utilization associated with retry- push operations.

Ig (Invalid Global) , Sg (Shared Global), and Slg (Shared Local Global) coherency states are provided to reduce access latency for domain indicators. The Ig state is defined herein as a cache coherency state that represents the following three states:
(1) it is invalid the associated memory block in the cache array,
(2) The address tag in the cache directory is valid.
(3) Address modified copy of the memory block identified by the tag, which is delivered to the cache at the remote coherency domain.
The Sg state is defined herein as a cache coherency state that represents the following four states.
(1) memory blocks associated in the cache array is valid,
(2) The address tag in the cache directory is valid.
(3) A modified copy of the memory block identified by the address tag was delivered to the cache in the remote coherency domain.
(4) a copy of the memory block plus Tei held in other cache, it is still held in the other cache Tei Rukoto are possible.
The Slg state is similarly defined herein as a cache coherency state that represents the following five states.
(1) memory blocks associated in the cache array is valid,
(2) The address tag in the cache directory is valid.
(3) A modified copy of the memory block identified by the address tag was delivered to the cache in the remote coherency domain.
(4) a copy of the memory block plus Tei held in other cache, it is still held in the other cache Tei Rukoto are possible.
(5) cache, the data intervention between the cache has the authority to distribute a copy of the memory block to the master at the coherency domain.

It may be desirable to form Ig, Sg, and Slg for a given memory block only within the coherency domain that contains the LPC for that memory block. In such an embodiment, one mechanism (e.g., partial response by LPC, and subsequent formation Go応 answer), compared caches to deliver the requested memory block, LPC its local coherency domain It must be implemented to indicate that it is within. In other embodiments not support the communication of the display that LPC is local, when the memory block is delivered to the remote coherency domain, Ig, Sg, and Slg state is made form, therefore, Ig, Sg, and Slg can be formed incorrectly.

Several rules govern the selection and replacement of Ig, Sg, and Slg ( collectively “X g ” ) cache entries. First, if selected as the victim for cache replacement and Xg entry, (unlike the case of when the I or S entries is selected) castout Xg entry is performed. Second, the castout in the Xg state is preferably done as a local operation or, if done as a global operation , is ignored by the remote LPG at the castout address. If, Xg entry, if is permissible to form in the cache is not in the same coherency domain as LPC for the memory block is not necessary update to the domain indicator in LPC. Fourth, cast out of Xg state, the domain indicator that (for the cache to perform the cast-out if a local) is written back to the LPC, it is preferably performed as a dataless address-only operation.

Because cache directory entries including an Xg state owns potentially useful information, it is at least some implementations, for example, LRU field to select the victim cache entry for replacement by the least-recently-used (LRU) algorithm utilized for positive Osamu to assess 318,368, same base state (e.g., S, or I) an entry in the X g state than other entries having excellent It is desirable to maintain it in advance. Since Xg directory entries are maintained in the cache , such entries can "stale" over time. Because, as a result of the exclusive access request caused the formation of Xg state cache, without notifying the cache that holds the address tag of the memory block in Xg state, a copy of that memory block This is because it can be deallocated or written back . In such a case, Xg state was "stale" global operations represents the wrong that must be issued in place of the local operation, but will not cause any coherency errors, so It would only be issued a number of operations that may be served by using a local operation as a global operation when not. The occurrence of such inefficiencies will be limited in duration by the final replacement of the “stale” sub-g cache entry.

Implementation of Xg coherency states, even when there is no valid copy of Tei Ru memory block is cached in the coherency domain (such as the case of Ig), maintaining the cached domain indicator for the memory block in the coherency domain the communication efficiency modifier for good by. As a result, the HPC for the memory block pushes the requested memory block to the LPC without retrying the exclusive access request (eg, bus RWITM operation or bus DClaim operation) from the remote coherency domain. Such requests can be serviced without having to

VII. Exemplary L2 / L3 Coherency State Transition Referring now to FIG. 7, a high level logical flow diagram of an exemplary method for performing a cast-in to an L3 cache in accordance with a preferred embodiment of the present invention is shown. The process illustrated in Figure 7, includes an operation by the L3 cache controller 380. The process begins at block 600, then, seen block 602 binary, where, L3 cache 232 (e.g., L3 Cache 232a) L3 cache controller 380 of the cache line Ru is discharged from the L2 cache 230 of the source as a result, one of the L2 cache 230 its Re is connected (e.g., L2 cache 230a) takes receiving a cast out request from. The castout request includes the target address, the cast-in cache line, and the cache directory state of the cast-in cache line. L3 cache controller 380 determines whether the cast-in cache line is stored in the data array 360, and if so, to determine the appropriate coherency state for the cache line in the status field 366 It is programmed with a replacement policy for.

Next, at block 604, the cache controller 380 reads the tag field 364 of the L3 cache directory 362 to determine if a directory entry already exists for the target address. If Kere such found its target address in the tag field 364, the process seen diblock 605 binary, where, cache controller 380, victim cache line for replacement of the system memory may be cast out and the victim cache coherency state (e.g., Xg, M, T or Tn,) accordingly select. Next, the process seen diblock 606 binary, where, cache controller 380, stores the cast-in cache line received from L2 cache 230 of the source to the L3 data array 360, corresponding to the cache directory 362 Create a cache directory entry for Cache controller 380, in accordance with the state specified in the cast-out request, to set the coherency state field 366 of the directory entry. Thereafter, the process ends at block 608.

Return description to block 604 . If the cache controller 380, if decision that exists in the directory entry is already L3 cache directory 362 for the target address of the cast-in cache line, the process seen block 610 binary, where , cache controller 380, as will be described later with reference to Table 3 and FIG. 8, by referring to a cast out request according key Yasutoin policy, to update the data array 360 and cache directory 362. As implemented in the preferred embodiment of the present invention, the cast-in specifies the following two matters. That is,
(1) Whether the cast-in cache line is stored in the L3 data array 360 or discarded
(2) The coherency state of the corresponding entry in the cache directory 366.

In a preferred embodiment, when performing the casting-in to the cache line that already has an entry in cache directory 362, cast-policy is implemented by the L3 cache 232 is summarized in Table 3 below The Table 3, as a function of the previous state and the coherency state specified in the cast-out request of the cache line in L3 cache directory 362, which identifies the results of coherency states in the state field 366.

This cast-in policy further determines whether memory blocks stored in the L3 data array 360 should be maintained or overwritten by cast-in cache lines received from the source L2 cache 230. to manage. The decision whether to overwrite the cache line data is indicated in Table 3 by the resulting coherency state underlined. If the transition of the results of the coherency state if underlined, cast-cache line, instead of the front of the cache line data are stored in L3 cache array 360. If the if the transition of the results of coherency state is not underlined, the cache line of the cache array 360 is maintained, updated coherency state in the state field 366, the result of the coherency states identified in Table 3 Is done.

Referring in detail to the Sg or Slg line in Table 3, the current state of the cache line in the L3 cache directory 362 is either In, Ig, or I coherency state, and the cast-in coherency state is Sg or Slg. The cast-in coherency state is used to update the state field 366. In addition, cache lines are replaced with cast-in data in the cache array 360, as represented by the underlined entries in Table 3. If, is the current state of Sg of the cache line in L3 cache directory 362, if the cast-in coherency state is Slg, cast-in coherency state, as is meant by "l" in the Slg, cache It is used to update the status field 366 so that the function for delivering data is maintained by intervening data intervention. However, if the current state of the cache line in the L3 cache directory 362 is the Sg state and the cast-in coherency state is Sg, coherency or data update to the L3 cache 232 is not performed. Similarly, the current state of the L3 cache directory 362 is Slg, if cast-in state is Sg or Slg, coherency update or data updates to the L3 cache 232 is not performed. If the current state of the cache line in L3 cache directory 362 is S or Slg, if cast-in coherency state is Sg or Slg, cache controller 380, should domain indicator 504 is updated In order to maintain a cache indication that there is , the status field 366 is updated from S to Sg or from Sl to Slg. In response to receiving the cast-in Slg coherency state, the cache controller 380 performs a similar coherency state update from the S state to the Slg state. As further shown in Table 3, the L2 and L3 caches both can not include a cache line in Slx state, it means that represents Sl-Slg case that an error has occurred . If the current state of the L3, as indicated in Tx and Mx column, if Tx or Mx, this information at the time of casting-in from L2 is always maintained in the L3 cache.

When the next For Sg and Slg row of Table 3, the cast-in case of Tx coherency state, cache controller 380, updates the data update and Sg or Slg to the data array 360 of the coherency state of the Tx Do both. In another case where the previous coherency state recorded in cache directory 362 is Slg , no data update or coherency state update occurs in response to receiving a cast-in. For cache lines marked Sg in the cache directory 362, the cache controller 380 updates the coherency state from Sg to Slg in response to a cast-in cache line in the Sl or Slg coherency state. Do, but do not update data or update coherency state for cast-in cache lines in In, Ig, Sg, or S coherency states.

Referring now to FIG. 8, in response to receiving a cast out request in accordance with a preferred embodiment of the present invention, the high-level logic of the L3 exemplary method that implements a cast-in policy in the cache A flow diagram is shown. The process, for example, in response to a positive determination at block 604 of FIG. 7, begins at block 700 and thereafter, see block 704 binary, where, L3 cache controller 380, the victim cache line to determine the designated coherency state, Ru examined cast out request. Furthermore, at block 706, the L3 cache controller 380, in order to determine the coherency state exists for the cast-in cache line reads the status field 366 of the entry associated in the cache directory 362. Next, the process seen block 708 binary, where, L3 cache controller 380, according to the cast-in policy is summarized in Table 3, that determine the coherency state of the appropriate results in L3 cache directory 362. This determination can be made, for example, by referring to a state table in the nonvolatile memory in the L3 cache 232. In another embodiment, L3 cache controller 380, through calculations performed by or through an integrated circuit executing the software, it is possible to make a decision indicated by block 708.

Next, the process seen diblock 710 binary, where, if a cache controller 380, based on the coherency state of the results determined at block 708, the existing coherency state for the victim cache line is updated To decide. If, as long as should the current state is updated, the process seen diblock 712 binary, where, cache controller 380 with a coherency state of the results determined at block 708, the coherency state of the cache directory 362 Is overwritten. The process from block 710. If it is not to the block 712, or updates to the coherency state is performed, see decision block 714 binary, where, cache controller 380, cast-cash received from L2 cache 230 Determine if the cast-in policy indicates that the line should be stored in the L3 data array 360. If so , the process proceeds to block 716 where the cache controller 380 was previously stored for the cast-in target address by storing the cast-in cache line in the L3 data array 360. Overwrite cache line. Following block 716, or following block 714 if no data update is to be made, the process ends at block 718.

As described with reference to Table 3 and FIGS. 7 and 8 , the implementation of Sg and Slg coherency states in accordance with the present invention affects the manner in which L3 cast-in operations are performed in addition to L In response to receiving a CPU read request or CPU update request that hits for a cache line held in L2 coherency state by two caches, it simplifies operations performed by higher level caches such as L2 cache 230. Such was depending on operating scenario (as shown in FIG. 10), in order to facilitate understanding of the exemplary method of processing in the L2 cache 230, first, with reference to FIG. 9, a conventional in L 2 Cache A processing method will be described.

Referring to FIG. 9, a timing diagram is shown representing operations performed by a conventional L2 cache in response to receiving a CPU read request that hits a cache line held in the L2 cache in an Ig coherency state. As illustrated, the process begins when a conventional L2 cache receives a CPU read request from its associated processor core. In response to receiving the CPU read request, the L2 cache assigns an RC machine to service the request, as indicated by reference numeral 802, and its cache, as indicated by reference numeral 804. Start directory reading of the directory.

In response to the determination that the coherency state recorded in the cache directory is Ig, the conventional L2 cache updates the domain indicator in system memory to a “global” state so that the coherency state is maintained. Assign a CO machine as indicated by reference numeral 806. Completion of RC and CO machine operations is asynchronous, meaning that these operations can be completed in any order. If completed its operation to the RC machine time t0, if CO machine completes its operations in time t1, the coherency resolution window 810 is formed. Until the time t0, RC machine, the directory to reflect the state of the newly acquired cache line (for example, in "shared"), but has been updated, CO machine, cast out until the time t1 Is still actively working on .

Normally, when determining the partial response to the snooped operation through the interconnection network, only separated mirrored coherency state by the active machine is discussed in the L2 cache. However , this policy is inadequate for operations snooped during a coherency resolution window that targets the same cache line that is being processed by the CO machine . Therefore, both coherency state of being reflected by the directory state and active cash out machines, must be considered when determining the snooped partial response should be given to the operation. Failure to do so can result in an inaccurate coherency state in the requesting L2 cache, which in turn leads to loss of coherency. Therefore, in order to process a snoop to pair those with the same cache line being processed by the C O machines during the coherency resolution window 800, special coherency resolution logic must be implemented in the L2 cache.

L2 cache design, in particular, the coherency process under the operating scenario shown in Figure 9, is mounted on the thus simplified Sl and Slg coherency state in accordance with the present invention. Referring now to FIG. 10, a logical flow chart of a high-level exemplary method coherency process in the higher level cache, such as L2 cache 230 in accordance with the present invention is shown. As illustrated, the process begins at block 900 and thereafter, see block 902 binary, where, L2 cache 230, Ru receive a CPU read request or CPU update request from the processor core 200 its associated. Generally it includes a transaction type (TTYPE) and target address identifying the request type, in response to receiving the CPU request, at block 904, the L2 cache controller 330 of the L2 cache 230, the target to access the cache directory 312 using the target address in order to determine its coherency state with respect to the address, it dispatches the RC machine 332 in order to service the CPU request. As shown in block 906, if the cache controller 330 determines that the coherency state is Ig, the cache controller 330 services the CPU request as shown in block 920 and subsequent blocks. If the coherency state is different from Ig, the cache controller 330 uses other processing shown in block 910 to service the CPU request.

Referring now to block 920, the dispatched RC machine 332 responds to the determination that the coherency state for the target memory block of the CPU request is Ig in the L2 cache directory 312 and TTYPE issues a CPU update request. And if so, at block 922, a global range bus RWITM operation on all local interconnect networks 114 and global interconnect networks 110 to obtain an exclusive copy of the target memory block. the you issue. RC machines 332, that updated copy of the memory block is in a remote coherency domain, based on inaccurate display supplied by the Ig coherency state to select the global operations range. When the RC machine 332 receives a copy of the target memory block, it places the target memory block in the data array 310 as shown in block 924 and the corresponding entry in the L2 cache directory 312. Update the coherency state from Ig to M. Thereafter, the RC machine 332 is deallocated and the process ends at block 940.

Reference is again made to block 920 . If, RC machines 332, the TTYPE the CPU requests, if decision that it is a CPU read request, the process seen diblock 930 binary, where, RC machine 332, a copy of the target memory block issue the bus READ operation of the global range in order to obtain. RC machine 332 is again updated copy of that memory block is based on an inaccurate indication provided by the Ig coherency state that a remote coherency domain, selects the global operations range. In response to receiving the requested memory block, the RC machine 332 places the memory block in the data array 310, as indicated by block 932, and the corresponding entry in the cache directory 312. Update the status field 316 from the Ig state to one of the Slg or Me states. In particular, RC machine 332, when the memory block is when and other caches are delivered by the memory controller 206 does not hold a copy of the memory block, updates the coherency state to Me, is not the case , Update the coherency state to Slg. Thereafter, the RC machine 332 is deallocated and the process ends at block 940.

Obviously, the implementation of Sg and Slg coherency state in accordance with the present invention, to simplify the least coherency process in two ways. First, since the display cached the global state of the domain indicator represented by Ig state, either by Sg or Slg coherency state can be maintained in the cache directory, C PU read request in the case of Ig hits to which CO machine 336 not assigned to cast out the Ig coherency state. Therefore, the utilization rate of the finite resource in the L2 cache controller 330 is reduced. Second, since any CO machine 336 not assigned to perform cast out in cases like its coherency resolution window 800 is not formed, therefore, the response logic 210, partial response to the snooped request Ru can be determined directly to the appropriate coherency state to be the foundation from the cache directory 312. As a result, the logic implemented in the response logic 210 is simplified.

As before mentioned, the present invention is, in order to perform an indication that a copy of it and that memory block specific memory block can be retained in the plurality of caches are outside the local coherency domain of the cache, Improved methods, apparatus, and systems for data processing are provided in which coherency states such as Sg or Slg are utilized. Implementation of one or more of such coherency state maintained cache low-level shared (e.g., L3) is a copy of the memory block in the case of a cast-out hit in Ig copy of memory block It is advantageous in that it is allowed to do. Furthermore, the implementation of one or more of such coherency state, the higher level (e.g., L2) simplifies cache design, the coherency process efficient.

Although the invention has been disclosed and described in detail with reference to preferred embodiments, it will be apparent to those skilled in the art that various changes in form and detail can be made without departing from the spirit and scope of the invention. Let's go.

1 is a high level block diagram of an embodiment of a cache coherent symmetric multiprocessor (SMP) data processing system according to the present invention. FIG. FIG. 3 is a block diagram of an exemplary processing unit in accordance with a preferred embodiment of the present invention. FIG. 3 is a more detailed block diagram of an embodiment of a processor core and L2 cache in accordance with a preferred embodiment of the present invention. FIG. 4 is a more detailed block diagram of an embodiment of an L3 cache according to a preferred embodiment of the present invention. FIG. 2 is a space-time representation of an exemplary operation in a local or system interconnect network of a data processing system in accordance with a preferred embodiment of the present invention. FIG. 3 is a schematic diagram illustrating a system memory including a domain indicator according to a preferred embodiment of the present invention. 3 is a high level logical flow diagram of an exemplary method for performing a cast-in to L3 cache memory in accordance with a preferred embodiment of the present invention. Is a high level logic flow diagram of an exemplary method that implements a coherency state transition method in L3 cache memory in response to the cast-in in accordance with a preferred embodiment of the present invention. A timing diagram showing a conventional operation flow in which a castout hit in an Ig coherency state creates a coherency resolution window that must be consulted in the cache directory to determine an appropriate coherency response for a snooped read type operation. is there. Is a logical flow diagram of a high-level exemplary method of L2 coherency state transition method is implemented by the cache memory in accordance with a preferred embodiment of the present invention.

Claims (8)

Processing data in a multiprocessor data processing system including at least a first coherency domain and a second coherency domain, wherein the first coherency domain includes at least one processing unit, system memory, and cache memory A way to
Buffering cache lines in the data array of the cache memory;
The cache line is valid in the data array; the cache line is held non-exclusively in the cache memory and unmodified with respect to a corresponding memory block in the system memory ; it another cache before Symbol second coherency domain may retain a copy of the cache line, and a first state representative of a first coherency communication range for the cache line that does not contain the second coherency domain And the domain indicator in the first coherency domain has to be updated to the second state with a second state representing a second coherency communication range for the cache line including the second coherency domain. , to represent the And the step of setting the coherency state of the state field in the serial cache memory of the cache directory,
Having a method. The cache memory is a lower level cache memory;
The data processing system includes a plurality of upper level cache memories coupled to the lower level cache memory;
The coherency state is a first coherency state;
The setting step is responsive to a cache line cast-in from one of the plurality of higher level cache memories to the data array indicating a second invalid cache line. Updating the state field from a coherency state to the first coherency state;
The method of claim 1. The cache memory is connected to an interconnection network of the data processing system;
The coherency state is a first coherency state;
It said cache memory further comprises the step of issuing a request for said cache line on the interconnection network,
The setting step is responsive to receiving the cache line in response to the request, wherein the cache line is invalid, and another cache in the second coherency domain is the cache line. Updating the state field from a second coherency state that represents holding a copy of the state to the first coherency state;
The method of claim 1. Selecting the cache line to drain from the data array;
In response to selecting the cache line to drain from the data array, a dataless indication of an indication that another cache in the second coherency domain holds a copy of the cache line. A castout is performed by the cache memory; and
The method of claim 1, further comprising: In response to receiving the indication that another cache in the second coherency domain holds a copy of the cache line, the memory controller of the system memory is responsible for the cache line. further comprising the method of claim 4 updating the domain indicator. Said coherency state is further said cache memory indicates that they have the authority of the first coherency domain for delivering a copy of the cache line with data intervention between the cache, according to claim 1 the method of. A processing unit for a multiprocessor data processing system including at least a first coherency domain and a second coherency domain, the first coherency domain comprising system memory and the processing unit;
A processor core;
A cache memory connected to the processor core ,
The cache memory is
A data array that holds cache lines; and
And cache directory containing an entry containing and status field associated with said cache line,
A cache controller,
The cache controller is
The cache line is valid in the data array; the cache line is held non-exclusively in the cache memory and unmodified with respect to a corresponding memory block in the system memory ; it another cache before Symbol second coherency domain may retain a copy of the cache line, and a first state representative of a first coherency communication range for the cache line that does not contain the second coherency domain And the domain indicator in the first coherency domain has to be updated to the second state with a second state representing a second coherency communication range for the cache line including the second coherency domain. , to represent the You set the serial state field to the coherency state,
Processing unit. Comprising at least interconnected cash coherent first coherency domain and a second coherency domain, said first coherency domain includes a first processing unit and domain indicator, said second coherency domain first A data processing system comprising two processing units, wherein a system memory is located in at least one of the first coherency domain and the second coherency domain ,
The first processing unit includes :
A processor core;
A cache memory connected to the processor core ,
The cache memory is
A data array that holds cache lines; and
And cache directory containing an entry containing and status field associated with said cache line,
A cache controller,
The cache controller is
The cache line is valid in the data array; the cache line is held non-exclusively in the cache memory and unmodified with respect to a corresponding memory block in the system memory ; it another cache before Symbol second coherency domain may retain a copy of the cache line, and a first state representative of a first coherency communication range for the cache line that does not contain the second coherency domain And the domain indicator in the first coherency domain has to be updated to the second state with a second state representing a second coherency communication range for the cache line including the second coherency domain. , to represent the You set the serial state field to the coherency state,
Data processing system.

Images