Low latency management of processor core wait state

A data processing system includes multiple processing units all having access to a shared memory. A processing unit includes a lower level cache memory and a processor core coupled to the lower level cache memory. The processor core includes an execution unit for executing instructions in a plurality of simultaneous hardware threads, an upper level cache memory, and a plurality of wait flags each associated with a respective one of the plurality of simultaneous hardware threads. The processor core is configured to set a wait flag among the plurality of wait flags to indicate the associated hardware thread is in a wait state in which the hardware thread suspends instruction execution and to exit the wait state based on the wait flag being reset.

BACKGROUND OF THE INVENTION

The present invention relates in general to data processing system and, in particular, to managing accesses to data in shared memory of a data processing system. Still more particularly, the present invention relates to a processor, data processing system and method providing low latency management of a wait state of a hardware thread in a processor core.

In shared memory multiprocessor (MP) data processing systems, each hardware thread of the multiple processors in the system may access and modify data stored in the shared memory. In order to synchronize access to a particular granule of memory (e.g., a lock or other variable) between multiple processing units and hardware threads of execution, load-reserve and store-conditional instruction pairs are often employed. For example, load-reserve and store-conditional instructions have been implemented in the POWER® instruction set architecture with request codes (opcodes) associated with various mnemonics, referred to herein generally as LARX (load-and-reserve) and STCX (store-conditional). The goal of load-reserve and store-conditional instruction pairs is to load and modify data and then to commit the modified data to coherent memory only if no other hardware thread of execution has modified the data in the interval between the load-reserve and store-conditional instructions. Thus, a read-modify-write operation targeting shared memory can be emulated without the use of an atomic update primitive that directly enforces atomicity.

When a hardware thread is competing to acquire a lock held by another hardware thread, it is common for the hardware thread seeking to acquire the lock to simply execute in a programming loop (i.e., to “spin”) in which the hardware thread repeatedly checks whether or not the lock is in an unlocked state. In some cases, this programming loop employs a load-reserve instruction to test the lock state; in other cases a regular load instruction is utilized. In either case, because the hardware thread remains active but is not performing a useful task while “spinning” on the lock in this manner, some prior art processor architectures support the ability for the hardware thread waiting to acquire the lock to instead enter a suspend or wait state until the lock is unlocked. By placing the thread in a wait state, the consumption of power and processor resources associated with “spinning” on the lock is reduced.

BRIEF SUMMARY

The present disclosure appreciates that in prior art architectures it is common for the availability of a lock (or other variable to which access is sought) to be determined at a point of coherence residing at a lower level of the vertical cache hierarchy associated with a processor core. Consequently, management of a hardware thread entering a wait (or suspend) state based on the variable being unavailable and exiting the wait (or suspend) state based on the variable potentially becoming available entails communication between the processor core and the point of coherence. This communication increases latency and consumes some of the limited bandwidth of the request communication paths coupling the processor core and the lower level cache(s). Accordingly, the present disclosure appreciates that it would be desirable to reduce such communication by supporting management of thread wait states within the processor core through implementation of per-thread wait flags.

According to at least one embodiment, a data processing system includes multiple processing units all having access to a shared memory. A processing unit includes a lower level cache memory and a processor core coupled to the lower level cache memory. The processor core includes an execution unit for executing instructions in a plurality of simultaneous hardware threads, an upper level cache memory, and a plurality of wait flags each associated with a respective one of the plurality of simultaneous hardware threads. The processor core is configured to set a wait flag among the plurality of wait flags to indicate the associated hardware thread is in a wait state in which the hardware thread suspends instruction execution and to exit the wait state based on the wait flag being reset.

DETAILED DESCRIPTION

With reference now to the figures and in particular with reference toFIG. 1A, there is illustrated a high level block diagram of a data processing system100in accordance with one embodiment. As shown, data processing system100includes multiple processing units102(including at least processing units102a-102b) for processing data and instructions. Processing units102are coupled for communication to a system interconnect104for conveying address, data and control information between attached devices. In the depicted embodiment, these attached devices include not only processing units102, but also a memory controller106providing an interface to a shared system memory108and one or more host bridges110, each providing an interface to a respective mezzanine bus112. Mezzanine bus112in turn provides slots for the attachment of additional unillustrated devices, which may include network interface cards, I/O adapters, non-volatile memory, non-volatile storage device adapters, additional bus bridges, etc.

As further illustrated inFIG. 1A, each processing unit102, which may be realized as a single integrated circuit, includes one or more processor cores120(of which only one is explicitly shown) for processing instructions and data. Each processor core120includes an instruction sequencing unit (ISU)122for fetching and ordering instructions for execution, one or more execution units124for executing instructions dispatched from ISU122, and a set of registers123for temporarily buffering data and control information. The instructions executed by execution units124include load-reserve and store-conditional instructions, which are utilized to synchronize access to shared memory between a particular thread of execution and other concurrent threads of execution, whether executing in the same processor core120, a different processor core120in the same processing unit102, or in a different processing unit102. In a preferred embodiment, execution units124execute at least load-reserve and store-conditional instructions in-order (other instructions may or may not be executed out-of-order).

Each processor core120further includes an L1 store queue (STQ)127and a load unit128for managing the completion of store and load requests, respectively, corresponding to executed store and load instructions (including load-reserve and store-conditional instructions). In a preferred embodiment, L1 STQ127is implemented as a First-In, First-Out (FIFO) queue containing a plurality of queue entries. Store requests are accordingly loaded in the “top” entry of L1 STQ127at execution of the corresponding store instruction to determine the target address, and are initiated when the store request reaches the “bottom” or “commit” entry of L1 STQ127. In the depicted embodiment, load unit128includes, for each of multiple simultaneous hardware threads of execution, a respective wait flag125indicating whether execution of the hardware thread is temporarily suspended while awaiting availability of a variable. Thus, for example, if the wait flag125is set, execution of the associated hardware thread is suspended, and if the wait flag125is reset, execution of the associated hardware thread is not suspended. Each wait flag125has a respective address register129indicating the cache line address of the variable, if any, upon which the hardware thread is waiting.

It is important to note that the present application makes a distinction between “instructions”, such as load-reserve and store-conditional instructions, and “requests.” Load and store “instructions” (including load-reserve and store-conditional instructions) are defined herein as inputs to an execution unit that include an request code (opcode) identifying the type of instruction and one or more operands specifying data to be accessed and/or its address. Load and store “requests,” including load-reserve and store-conditional requests, are defined herein as data and/or signals generated following instruction execution that specify at least the target address of data to be accessed. Thus, load-reserve and store-conditional requests may be transmitted from a processor core120to the shared memory system to initiate data accesses, while load-reserve and store-conditional instructions are not.

The operation of processor core120is supported by a multi-level volatile memory hierarchy having, at its lowest level, shared system memory108, and at its upper levels two or more levels of cache memory, which in the illustrative embodiment include a L1 cache126and a L2 cache130. As in other shared memory multiprocessor data processing systems, the contents of the memory hierarchy may generally be accessed and modified by threads of execution executing in any processor core120in any processing unit102of data processing system100.

In accordance with one embodiment, L1 cache126, which may include bifurcated L1 data and instruction caches, is implemented as a store-through cache, meaning that the point of cache coherency with respect to other processor cores120is located below L1 cache126and, in the depicted embodiment, is located at store-in L2 cache130. Accordingly, as described above, L1 cache126does not maintain true cache coherency states (e.g., Modified, Exclusive, Shared, Invalid) for its cache lines, but only maintains valid/invalid bits. Because L1 cache126is implemented as a store-through cache, store requests first complete relative to the associated processor core120in L1 cache126and then complete relative to other processing units102at a point of system-wide coherency, which in the depicted embodiment is L2 cache130.

As further illustrated inFIG. 1A, L2 cache130contains a storage array and directory140that store cache lines of instructions and data in association with their respective memory addresses and coherence states. L2 cache130also includes a number of read-claim (RC)/Castout (CO) state machines142a-142nfor independently and concurrently servicing memory access requests received from the associated processor cores120. RC/CO machines142receive core load requests from LD unit128in processor core120via load bus160, an in-order L2 load queue (LDQ)161, and command bus162. Similarly, RC/CO machines142receive core store requests from L1 STQ127in processor core120via store bus164, an in-order L2 store queue (STQ)166, and command bus162. RC/CO machines142also handle castouts of data from L2 storage array140to system memory108, as necessary.

L2 cache130further includes a number of snoop (SN) state machines144a-144nfor servicing memory access and other requests received from other processing units102via system interconnect104and snoop bus170. SN machines144and RC/CO machines142are each connected to a back-invalidation bus172by which any SN machine144or RC/CO machine142can signal the invalidation of a cache line to processor core120.

It is important to note that in a preferred embodiment L2 cache130is constructed such that at most a single one of RC/CO machines142and SN machines144can be active servicing a request targeting a given target cache line address at any one time. Consequently, if a second request is received while a first request targeting the same cache line is already being serviced by an active RC/CO machine142or SN machine144, the later-in-time second request must be queued or rejected until servicing of the first request is completed and the active state machine returns to an idle state.

L2 cache130finally includes reservation logic146for recording reservations of the associated processor core120. An exemplary embodiment of reservation logic146is described in greater detail below with reference toFIG. 1B. As shown, reservation logic146provides pass and fail indications indicating the success or failure of store-conditional (STCX) requests of the associated processor core120. These pass/fail indications, as well as invalidation commands of RC/CO machines142and SN machines144on back-invalidation bus172and data received on system interconnect104, are received as inputs by a multiplexer150. Multiplexer150orders these various inputs for transmission to processor core120via reload bus174.

Those skilled in the art will additionally appreciate that data processing system100ofFIG. 1Acan include many additional non-illustrated components, such as interconnect bridges, non-volatile storage, ports for connection to networks or attached devices, etc. Because such additional components are not necessary for an understanding of the described embodiments, they are not illustrated inFIG. 1Aor discussed further herein. It should also be understood, however, that the enhancements described herein are applicable to cache coherent data processing systems of diverse architectures and are in no way limited to the generalized data processing system architecture illustrated inFIG. 1A.

Referring now toFIG. 1B, there is depicted a more detailed block diagram of reservation logic146ofFIG. 1in accordance with one embodiment. In the illustrated embodiment, reservation logic146includes, for each hardware thread that may be concurrently executed by the associated processor core120, a respective reservation register comprising a reservation address field148and a reservation flag150. In the depicted example, which assumes that processor core120can each execute two concurrent hardware threads, reservation logic146includes two reservation registers: reservation address field148aand reservation flag150afor thread 0 and reservation address field148band reservation flag150bfor thread 1. When set (e.g., to ‘1’), a reservation flag150indicates that the corresponding thread holds a reservation for the address contained in the associated reservation address field148and otherwise indicates no reservation is held.

Reservation logic146additionally includes per-thread comparators152a-152b. As described further below, comparators152receive target addresses of memory access requests snooped from system interconnect104and compare the target addresses with the reservation addresses, if any, specified in reservation address fields148. In response to detection of an address match, reservation logic146resets the associated reservation flag150and issues a RSV_Invalidate command for the applicable hardware thread to the processor core120.

Referring now toFIG. 2A, there is depicted a first exemplary instruction sequence200that employs load-reserve and store-conditional instructions to synchronize access to shared memory. In particular, instruction sequence200is utilized to update the value of a variable in shared memory.

Instruction sequence200begins with a LARX instruction202that loads the value of the variable (i.e., var) from shared memory into a private register r1in the processor core executing the instruction. The value of the variable is then updated locally in register r1, in this case, by an ADD instruction204incrementing the value of the variable by 1. The new value of the variable is then conditionally stored back into shared memory by STCX instruction206. The success or failure of STCX instruction206in updating the value of the variable in shared memory is reflected in a condition code register (e.g., one of registers123) in the processor core. Conditional branch instruction208then tests the condition code found in the condition code register and conditionally redirects execution based on the success or failure of STCX instruction206. If the relevant bit(s) of the condition code register is/are equal to zero, indicating that the conditional update to the variable indicated by STCX instruction206failed (e.g., due to an intervening storage-modifying access to the variable by another thread between execution of LARX instruction202and STCX instruction208), instruction sequence200will be repeated, and execution branches from conditional branch instruction208back to LARX instruction202. If, however, the conditional update indicated by STCX instruction206succeeds, the condition code will be non-zero, and processing will continue with the next sequential instruction following instruction sequence200.

With reference now toFIG. 2B, there is illustrated a second exemplary instruction sequence210that employs load-reserve and store-conditional instructions to coordinate execution of a critical section of a multithreaded program. As indicated, instruction sequence210includes, in program order, a polling instruction sequence212, lock acquisition sequence214, critical section216, and lock release sequence218.

As is known in the art, critical section216is, by definition, a portion of a program that includes accesses to a shared resource (e.g., a shared in-memory data set) that must not be concurrently accessed by more than one thread of the multiprocessor program. In order to keep the various hardware threads from making concurrent accesses to the shared resource, the multithreaded program bounds critical section206with barrier instructions240,244that order execution of instructions within critical section216with respect to both instructions in the same thread that are outside critical section216. In addition, the multiprocessor program ensures that not more than one thread at a time enters into a critical section by implementing a lock to which access is synchronized by load-reserve and store-conditional instructions.

In particular, a thread attempts to acquire the lock needed to enter critical section216through execution of lock acquisition sequence214. Lock acquisition sequence214begins with a LARX instruction230that loads the value of the lock variable (i.e., lock) from shared memory into a private register r1(e.g., one of registers123) in the executing processor core. The value of the lock variable is then tested by compare instruction232to determine whether or not the lock is currently in a locked state (i.e., the lock is held by another thread). If so, conditional branch instruction234causes execution to return to the beginning of polling instruction sequence212(which is described in greater detail below). If a determination that the lock is not currently held by another thread, a LOAD immediate instruction236places a value of ‘1’ (representing a locked state) into a register r2. A STCX instruction238then conditionally updates the lock variable in shared memory to the locked state, thus securing the lock for the executing thread. As before, the success or failure of the STCX instruction in updating the value of the lock variable in shared memory is reflected in a condition code register in the processor core. Conditional branch instruction239tests the condition code found in the condition code register and conditionally redirects execution based on the success or failure of STCX instruction238. If the relevant bit(s) of the condition code register is/are equal to zero, indicating that the conditional update to the lock variable indicated by STCX instruction238failed (e.g., due to an intervening storage-modifying access to the lock variable by another thread between execution of LARX instruction230and STCX instruction238), instruction sequence210will be repeated from the beginning of instruction polling sequence212. If, however, the conditional update to the lock variable indicated by STCX instruction238succeeds, the condition code will be non-zero, and processing will proceed sequentially to critical section216. Once critical section216completes, the thread will release the lock by updating the lock variable in shared memory by executing a lock release sequence218including a LOAD immediate instruction250that loads register r2with a value of ‘0’ (representing an unlocked state) and a STORE instruction252that updates the lock variable in shared memory with this value. Thereafter, execution of the thread proceeds to subsequent instructions, if any.

Although a multiprocessor program could be implemented with only lock acquisition sequence214, critical section216, and lock release sequence218(i.e., omitting polling instruction sequence212), in practice such a multiprocessor program would not efficiently utilize the resources of a processing unit, such as a processing unit102inFIG. 1A. In particular, LARX instruction230, which is utilized to load the lock value and set the reservation for the lock address upon which the execution of STCX instruction238depends, is generally a resource-intensive instruction. Irrespective of the chosen implementation of the cache hierarchy, a LARX instruction requires communication with the coherence point of the cache hierarchy, and in implementations in which that the coherence point is not in the L1 cache, this communication results in the LARX instruction being more resource-intensive than a corresponding LOAD instruction. For example, in the current embodiment, regardless of whether the target address of LARX instruction230hits or misses in L1 cache126, execution of LARX instruction230requires allocation of an entry in L2 LDQ161, dispatch of an RC/CO machine142in L2 cache130, and update of reservation logic146. Consequently, it is desirable that the thread iterate on a load target address using a less resource-intensive LOAD instruction rather than a more resource-intensive a LARX instruction.

Therefore, it is common for lock acquisition sequence214to be proceeded by a polling instruction sequence212. Polling instruction sequence212, which is constructed very similarly to the beginning of lock acquisition sequence214, includes a polling LOAD instruction220(rather than a LARX instruction) that loads the lock value from shared memory, a compare instruction222that compares the lock value to a value of ‘1’ (indicating a locked state), and a conditional branch instruction224that returns execution back to polling LOAD instruction220until the lock is found to be in the unlocked state. It is advantageous to employ polling LOAD instruction220to poll on the lock variable rather than a LARX instruction since a hit on the target address of polling LOAD instruction220in L1 cache126will not require utilization of any of the limited resources of L2 cache130(e.g., L2 LDQ161, RC/CO machines142, and reservation logic146).

In multithreaded programs that include instruction sequences such as instruction sequences200and210, it is common for a hardware thread to execute multiple STCX instructions targeting the same store target address. For example, in the multithreaded program including instruction sequence210, a hardware thread may need to acquire the same lock multiple times in order to execute various different critical sections of code. Because the target cache lines identified by STCX requests are commonly highly contended, it is not uncommon for these cache lines to bounce back and forth between the caches of various processing units, leading to significant traffic on the system interconnect and execution inefficiency due to the conditional updates to shared memory indicated by the STCX requests being attempted multiple times prior to succeeding.

As an alternative to conventional polling instruction sequence such as polling instruction sequence212, a program can enter a wait state instead of continuing to iteratively execute a polling loop. Referring now toFIG. 2C, there is depicted an exemplary polling instruction sequence270including a polling loop272in which a hardware thread enters a wait state if a flag does not have a predetermined value. In this example, polling loop272includes a polling LARX instruction274that loads a flag value from shared memory, a compare instruction276that compares the flag value to a predetermined value (e.g., ‘1’), and a conditional branch instruction278that exits polling instruction sequence272if the flag is found to have the predetermined value. If conditional branch instruction278determines that the flag does not have the predetermined value, execution of the hardware thread proceeds to WAITRSV instruction280, which causes the executing hardware thread to enter a wait (suspend) state if the flag is still set when WAITRSV instruction280is executed. As will be appreciated, while in the wait state, the executing hardware thread does not consume power or resources of its processing unit102. Once the flag is updated or due to other conditions, the executing hardware thread exits the wait state, and unconditional branch instruction282is executed to return execution to LARX instruction274. LARX instruction274causes the executing processor core to load the updated value of the flag, and compare instruction276causes the processor core to test whether the flag has been updated to the predetermined state. If so, conditional branch instruction278will cause the executing hardware thread to exit polling loop272; if not, the executing hardware thread will again enter the wait state in response to execution of WAITRSV instruction280.

As noted above, in conventional system architectures, the determination associated with wait WAITRSV instruction280of whether the flag had been updated (and thus whether the executing hardware thread can exit the wait state) is made at the point of coherence. Because the point of coherence is commonly implemented at a lower level of the vertical cache memory hierarchy supporting the processor core, this determination incurs non-negligible communication latency between the processor core and the lower level of the vertical cache hierarchy and consumes bandwidth on the data paths communicating requests of the processor core to the lower level of the vertical cache hierarchy. However, according to the disclosed embodiments, this latency and the consumption of core-to-cache bandwidth are reduced through the implementation of wait flags125with the processor core120. As discussed below in greater detail, the wait flag125of a hardware thread of a processor core120is set when the hardware thread enters into a wait state, and the hardware thread exits the wait state based on its associated wait flag125being reset among other conditions, as described below.

With reference now toFIG. 3A, there is depicted a high level logical flowchart of an exemplary method by which a processor core120of data processing system100processes a load-reserve (LARX) instruction in accordance with one embodiment. As shown, the process begins at block300and thereafter proceeds to block302, which illustrates execution units124receiving a LARX instruction from ISU122and then executing the LARX instruction to calculate the load target address. In a preferred embodiment, execution units124execute LARX instructions within a hardware thread in-order and without pipelining, meaning that the data words(s) requested by a LARX instruction must be loaded to one or more registers123in processor core120before the next LARX or STCX instruction begins execution. These restrictions simplify the management of reservations by reservation logic146in L2 cache130.

Following execution of the LARX instruction, an indication of the instruction type, a thread identifier, and the load target address calculated by execution of the LARX instruction are received from execution units124by LD unit128. At block306, LD unit128determines whether or not the load target address of the LARX instruction resides in L1 cache126. If so, LD unit128invalidates the cache line containing the load target address in L1 cache126(block308). Those skilled in the art should appreciate that the invalidation of the cache line containing the load target address in L1 cache126is a simplifying design choice and that in other embodiments the cache line containing the load target address need not be invalidated in L1 cache126. Following block308or in response to determining that the load target address of the LARX instruction missed in L1 cache126, LD unit128issues a LARX request to L2 cache130via load bus160(block310). The LARX request includes, for example, an indication of the request type, the load target address, and an identifier of the issuing thread. After buffering the LARX request in L2 LDQ161, L2 cache130dispatches the LARX request to an RC/CO machine142for servicing, as described further below with reference toFIG. 4A. As indicated at block311, LD unit128also sets the wait flag125associated with the requesting hardware thread and places the load target address (or a portion thereof) in the associated address register129.

Next, at block312, LD unit128awaits return of the requested cache line identified by the load target address from L2 cache130. In response to receipt of the requested cache line, LD unit128transfers the data word(s) associated with the load target address into a core register123, but does not cache the requested cache line in L1 cache126(block314). It should be appreciated that in an alternative embodiment that does not invalidate the requested cache line at block308, the requested cache line can instead be cached in L1 cache126to permit subsequent loads (including subsequent load-reserve requests), to hit in L1 cache126. Following block314, the process ofFIG. 3Aterminates at block316.

Referring now toFIG. 4A, there is depicted a high level logical flowchart of an exemplary method by which an L2 cache130of data processing system100processes a load-reserve (LARX) request in accordance with one embodiment. The process begins at block400and then proceeds to block402, which depicts L2 cache126dispatching an RC/CO machine142to service a next LARX request of the associated processor core120that is enqueued in L2 LDQ161. As illustrated at block406, RC/CO machine142establishes a reservation for the load target address in L2 cache130in the reservation register of the appropriate thread by placing the load target address in the appropriate reservation address field148and setting the associated reservation flag150.

At block410, RC/CO machine142additionally determines whether or not the load target address of the LARX request hit in L2 storage array and directory140. If so, the process passes directly to block418. If not, RC/CO machine142determines whether or not a castout (CO) is required to accommodate the cache line associated with the load target address within L2 storage array and directory140(block412). If not, the process passes to block416, which is described below. If, however, RC/CO machine142determines at block412that a castout is required, RC/CO machine142casts out a victim cache line from the relevant congruence class of L2 storage array and directory140(block414). At block416, RC/CO machine142also issues one or more requests on system interconnect104in order to obtain a copy of the cache line associated with the load target address from another cache hierarchy or system memory108. Following block416, the process proceeds to block418, which depicts RC/CO machine142returning the requested cache line to the associated processor core120. Thereafter, the RC/CO machine142servicing the LARX request transitions from the busy state to the idle state, and the process ofFIG. 4Aends at block420.

With reference now toFIG. 3B, there is illustrated a high level logical flowchart of an exemplary method of processing a load instruction in a processor core120of data processing system100in accordance with one embodiment. As shown, the process begins at block320and thereafter proceeds to block322, which illustrates execution units124receiving a LOAD instruction from ISU122and then executing the LOAD instruction to calculate the load target address. Following execution of the LOAD instruction, an indication of the instruction type, a thread identifier, and the load target address calculated by execution of the LOAD instruction are received from execution units124by LD unit128. At block326, LD unit128determines whether or not the load target address of the LOAD instruction resides in L1 cache126. If so, LD unit128returns the relevant data words of the target cache line associated with the load target address from L1 cache126to one of registers123(block328). Thereafter, the process ofFIG. 3Bends at block336.

Returning to block326, in response to determining that the load target address of the LOAD instruction missed in L1 cache126, LD unit128issues a LOAD request to L2 cache130via load bus160(block330). The LOAD request includes, for example, an indication of the request type, the load target address, and an identifier of the issuing thread. After buffering the LOAD request in L2 LDQ161, L2 cache130dispatches the LOAD request to an RC/CO machine142for servicing, as described further below with reference toFIG. 4B. Next, at block332, LD unit128awaits return of the requested cache line identified by the load target address from L2 cache130. In response to receipt of the requested cache line, LD unit128transfers the data word(s) associated with the load target address into a core register123and caches the requested cache line in L1 cache126(block334). Following block334, the process ofFIG. 3Bterminates at block336.

Referring now toFIG. 4B, there is depicted a high level logical flowchart of an exemplary method by which an L2 cache130of data processing system100processes a load request in accordance with one embodiment. The process begins at block430and then proceeds to block432, which depicts L2 cache126dispatching an RC/CO machine142to service a next LOAD request of the associated processor core120that is enqueued in L2 LDQ161. At block434, RC/CO machine142determines whether or not the load target address of the LOAD request hit in L2 storage array and directory140. If so, the process passes directly to block436. If not, RC/CO machine142determines whether or not a castout (CO) is required to accommodate the cache line associated with the load target address within L2 storage array and directory140(block442). If not, the process passes to block446, which is described below. If, however, RC/CO machine142determines at block442that a castout is required, RC/CO machine142casts out a victim cache line from the relevant congruence class of L2 storage array and directory140(block444). At block446, RC/CO machine142also issues one or more requests on system interconnect104in order to obtain a copy of the cache line associated with the load target address from another cache hierarchy or system memory108. Following block446, the process proceeds to block436, which depicts RC/CO machine142returning the requested cache line to the associated processor core120. Thereafter, the RC/CO machine142servicing the LARX request transitions from the busy state to the idle state, and the process ofFIG. 4Bends at block440.

With reference now toFIG. 5A, there is illustrated a high level logical flowchart of an exemplary method of processing a store-conditional (STCX) instruction in a processor core120of data processing system100in accordance with one embodiment. As depicted, the process begins at block500and thereafter proceeds to block502, which illustrates execution units124receiving a STCX instruction from ISU122and then executing the store-type instruction to calculate a store target address. As with the LARX execution described above, execution units124also preferably execute STCX instructions appearing in the same hardware thread in-order and without pipelining with respect to both LARX and STCX instructions.

Upon execution of the STCX instruction, execution units124reset the wait flag125associated with any other hardware thread (i.e., not the hardware thread including the STCX instruction) for which the address register129contains an address matching the store target address. It will be appreciated that this reset of wait flag(s)125is optimistic in that the STCX may not succeed in updating the flag, as discussed below with reference to block520. An alternative pessimistic implementation would reset the wait flag(s)125only after the STCX has been determined to succeed. Following execution of the STCX instruction, execution units124also place a corresponding store-type request including the store target address calculated by execution of the STCX instruction, a thread identifier, and the store data specified by the operands of the STCX instruction within L1 STQ127. In one preferred embodiment, L1 STQ127is implemented as a shared FIFO queue that buffers and orders store requests of all threads executing within processor unit102. When the STCX request corresponding to the executed STCX instruction reaches the bottom or commit entry of L1 STQ127, L1 STQ127determines at block512whether or not the store target address of the STCX request hits in L1 cache126. If so, L1 STQ127invalidates the target cache line held in L1 cache126(block514). Following block514or in response to the store target address missing in L1 cache126at block512, L1 STQ127issues the STCX request to L2 STQ166of L2 cache130via store bus164(block516). L1 STQ127then awaits return via pass/fail bus174of a pass or fail indication for the STCX request indicating whether or not the STCX request succeeded in updating L2 cache130(block518). In response to receipt of the pass or fail indication via pass/fail bus174, processor core120provides the pass or fail indication to execution units124(e.g., to indicate whether the path of execution should change) and, as shown at block520-524, updates a condition code register among registers123to indicate whether the STCX request passed or failed. Thereafter, the STCX request is deallocated from L1 STQ127, and the process ofFIG. 5Aterminates at block530.

Referring now toFIG. 6A, there is depicted a high level logical flowchart of an exemplary method of processing a store-conditional (STCX) request in a lower level cache in accordance with one embodiment. As described above, STCX requests are received by L2 cache130within L2 STQ166via store bus164. In some embodiments, L2 STQ166may be implemented, like L1 STQ127, as a FIFO queue. In such embodiments, the process begins at block600in response to receipt of a STCX request in the bottom entry of L2 STQ166. The STCX request at the bottom entry of L2 STQ166will then be selected for dispatch to an idle RC/CO machine142for processing, as shown at block602.

In response to receipt of a STCX request for servicing, the dispatched RC/CO machine142transitions from an idle state to the busy state. While in the busy state, the RC/CO machine142protects the store target address of the STCX request against any conflicting access to the same store target address executing on another hardware thread of the same processing unit102or a different processing unit102. The process ofFIG. 6Aproceeds from block602to block606, which illustrates the RC/CO machine142determining whether or not the issuing thread has a valid reservation for the store target address by determining whether the thread's RSV flag150is set and the associated RSV register148specifies a reservation address matching the store target address. If not, RC/CO machine142resets the RSV flag150of the issuing thread (block608) and returns a fail indication to the processor core120via pass/fail bus174to report that the STCX request made no update to L2 cache130(block610). Thereafter, the RC/CO machine142allocated to service the STCX request returns to the idle state, and the process ofFIG. 6Aends at block640.

Returning to block606, in response to RC/CO machine142determining that the issuing thread has a valid reservation for the store target address of the STCX request, RC/CO machine142resets the issuing thread's RSV flag150(block612), as well as the RSV flag150of any other thread specifying a matching store target address in its associated RSV address register148(block620). It should be noted that in this exemplary embodiment a STCX request only cancels the reservations of other threads at block620after it is verified at block606that the STCX is going to succeed in its conditional update of shared memory.

The process proceeds from block620to block622, which illustrates RC/CO machine142determining whether or not the store target address of the STCX request hits in L2 storage array and directory140in a “writeable” coherence state that confers authority on L2 cache130to modify the target cache line. If not, RC/CO machine142determines whether or not a castout (CO) is required to accommodate the target cache line associated with the store target address within L2 storage array and directory140(block623). If not, the process passes to block625, which is described below. If, however, RC/CO machine142determines at block623that a castout is required, RC/CO machine142casts out a victim cache line from the relevant congruence class of L2 storage array and directory140(block624). At block625, RC/CO machine142also obtains authority to modify the target cache line and, if necessary, a copy of the target cache line from another cache hierarchy or memory controller106by issuing one or more requests on system interconnect104. Following block625or in response to an affirmative determination at block622, RC/CO machine142updates the target cache line in L2 storage array and directory140with the store data of the store-type request (block626). RC/CO machine142additionally returns a pass indication to processor core120via pass/fail bus174to report successful update of the L2 cache130(block630). Thereafter, RC/CO machine142returns to the idle state, and the process ofFIG. 6Aends at block640.

With reference now toFIG. 5B, there is illustrated a high level logical flowchart of an exemplary method of processing a store instruction in a processor core120of data processing system100in accordance with one embodiment. As depicted, the process begins at block540and thereafter proceeds to block542, which illustrates execution units124receiving a store-type instruction from ISU122and then executing the store-type instruction to calculate a store target address.

Upon execution of the store instruction, execution units124reset the wait flag125associated with any other hardware thread (i.e., not the hardware thread including the store instruction) for which the address register129contains an address matching the store target address (block544). Execution units124also place a corresponding store-type request including the store target address calculated by execution of the store-type instruction, a thread identifier, and the store data specified by the operands of the store-type instruction within L1 STQ127. In one preferred embodiment, L1 STQ127is implemented as a shared FIFO queue that buffers and orders store requests of all threads executing within processor unit102. When the STORE request corresponding to the executed store-type instruction reaches the bottom or commit entry of L1 STQ127, L1 STQ127determines at block550whether or not the store target address of the STORE request hits in L1 cache126. If so, L1 STQ127updates the target cache line held in L1 cache126with the store data (block552). Following block552or in response to the store target address missing in L1 cache126at block550, L1 STQ127issues the STORE request to L2 STQ166of L2 cache130via store bus164(block554). Thereafter, the STORE request is deallocated from L1 STQ127, and the process ofFIG. 5Bterminates at block556.

Referring now toFIG. 6B, there is illustrated a high level logical flowchart of an exemplary method of processing a store request in lower level cache in accordance with one embodiment. As described above, in data processing system100, STORE requests are received by L2 cache130within L2 STQ166via store bus164. In some embodiments, L2 STQ166may be implemented, like L1 STQ127, as a FIFO queue. In such embodiments, the process begins at block650in response to receipt of a STORE request in the bottom entry of L2 STQ166. The STORE request at the bottom entry of L2 STQ166will then be selected for dispatch to an idle RC/CO machine142for processing, as shown at block652.

In response to receipt of a STORE request for servicing, the dispatched RC/CO machine142transitions from an idle state to the busy state. While in the busy state, the RC/CO machine142protects the store target address of the STCX request against any conflicting access to the same store target address executing on another hardware thread of the same processing unit102or a different processing unit102. The process ofFIG. 6Bproceeds from block652to block654, which illustrates the RC/CO machine142determining whether or not the store target address of the STORE request hits in L2 storage array and directory140in a “writeable” coherence state that confers authority on L2 cache130to modify the target cache line. If not, RC/CO machine142determines whether or not a castout (CO) is required to accommodate the target cache line associated with the store target address within L2 storage array and directory140(block656). If not, the process passes to block660, which is described below. If, however, RC/CO machine142determines at block656that a castout is required, RC/CO machine142casts out a victim cache line from the relevant congruence class of L2 storage array and directory140(block658). At block660, RC/CO machine142also obtains authority to modify the target cache line and, if necessary, a copy of the target cache line from another cache hierarchy or memory controller106by issuing one or more requests on system interconnect104. Following block660or in response to an affirmative determination at block654, RC/CO machine142updates the target cache line in L2 storage array and directory140with the store data of the STORE request (block662). Thereafter, RC/CO machine142returns to the idle state, and the process ofFIG. 6Bends at block670.

With reference toFIG. 7, there is illustrated a high level logical flowchart of an exemplary method of casting out a line from a lower level cache (e.g., L2 cache130) in accordance with one embodiment. The illustrated process, which is performed, for example, at blocks414,444,624, and658, begins at block700and then proceeds to block702. At block702, the RC/CO machine142dispatched to service the castout determines whether or not the victim cache line to be castout is modified with respect to system memory108, for example, by reference to the coherence state associated with the victim cache line in the L2 directory. If not, the process passes to block706, which is described below. If, however, RC/CO machine142determines at block702that the victim cache line is modified, RC/CO machine142issues a memory write request on system interconnect104to update the corresponding memory block within system memory108with the modified data contained in the victim cache line (block704). In addition, at block706, the RC/CO machine142sends a CO_Invalidate command identifying the victim cache line to processor core120via reload bus174. RC/CO machine142also invalidates the victim cache line in L2 storage array and directory140(block708). Thereafter, the castout process presented inFIG. 7ends at block710.

Referring now toFIGS. 8A-8C, there is depicted a high level logical flowchart of an exemplary method by which a processing unit102of data processing system100processes a request snooped on system interconnect104in accordance with one embodiment. The process begins at block800ofFIG. 8Aand then proceeds to block802, which illustrates a processing unit102snooping a memory access request on system interconnect104. Following block802, the process bifurcates and proceeds through page connector A toFIG. 8B, which depicts processing the snooped request with respect to the reservations recorded in reservation logic146, and additionally proceeds through page connector B toFIG. 8C, which illustrates performing any required processing to service the snooped request. After the processing depicted in bothFIGS. 8B-8Ccompletes, the process returns toFIG. 8Avia page connectors C and D and terminates at block842.

Referring now toFIG. 8B, the process begins at page connector A and then proceeds to block804, which illustrates reservation logic146determining whether or not the memory access request snooped on interconnect logic104is a store-type request that entails an update to a memory block. If not, the process proceeds directly to page connector C and returns toFIG. 8A. If, however, reservation logic146determines at block804that the snooped memory access request is a store-type request, reservation logic146determines utilizing comparators152whether or not the target address specified by the snooped request matches any of the reservation address recorded in reservation address fields148(block806). If not, the process passes to page connector C. If, however, a match is detected between the target address of the snooped memory access request and one or more of the reservation addresses recorded in reservation address field148, reservation logic146cancels the relevant reservation(s) by resetting the reservation flag150of each reservation register storing a matching reservation address (block808).

Reservation logic146also determines whether or not a SN machine144will be dispatched to service the snooped memory access request (block810). If so, the SN machine144will handle the transmission of any required invalidation commands to the processor core, as described below with reference toFIG. 8C. Consequently, the process passes to page connector C. If, however, reservation logic determines at block810that no SN machine144will be dispatched to service the snooped memory access request (e.g., the snooped memory access request is a Kill request that simply invalidates any cached copy of the target cache line), reservation logic146further determines at block812whether or not processing unit102is configured to permit a hardware thread of processor core102to remain in a wait state despite the castout or invalidation from L2 storage array and directory140of the cache line containing the flag on which a hardware thread was awaiting an update. If reservation logic146determines at block812that processing unit102is not configured to permit a hardware thread of processor core102to remain in a wait state despite the castout or invalidation from L2 storage array and directory140of the cache line upon which the wait state depends, the process passes to page connector C. Otherwise, reservation logic146issues a RSV_Invalidate command to the processor core102via reload bus174(block814). Thereafter, the process returns toFIG. 8Avia page connector C.

Turning now toFIG. 8C, the process begins at block connector B and then proceeds to block820, which depicts L2 cache130providing a snoop response for the snooped memory access request in accordance with the snoop-based coherence protocol implemented by data processing system100. In general, this snoop response is determined based on the coherence state, if any, for the target cache line of the snooped memory access request recorded in L2 storage array and directory140. In addition at block822, L2 cache130determines at block822whether or not a SN machine144needs to be dispatched to service the snooped memory access request. In general, L2 cache130determines that a SN machine144needs to be dispatched if (1) the target address specified in the snooped memory access request hits in L2 storage array and directory140in a valid coherence state and (2) the snooped memory access request requests a copy of the target cache line or write authority for the target cache line identified by the target address. In response to a determination at block822that no SN machine144need be dispatched to service the snooped memory access request, the process passes to page connector D.

Returning to block822, in response to a determination that dispatch of a SN machine144is required to service the snooped memory access request, L2 cache130determines at block824whether or not it is able to dispatch a SN machine144to service the snooped memory access request (e.g., SN machine144is then in an idle state and no other RC/CO machine142or SN machine144is busy servicing a memory access request specifying a conflicting target address). If not, the process passes to page connector D. If, however, L2 cache130determines at block824that it is able to dispatch a SN machine144to service the snooped memory access request, L2 cache130dispatches an idle SN machine144to service the snooped memory access request at block826.

At block830, the SN machine144dispatched to service the snooped memory access request determines whether or not the snooped memory access request is a store-type request that indicates an update to the target cache line. If so, SN machine144issues a SN_Invalidate command to processor core102(block832) and performs other processing to service the store-type request, such as updating L2 storage array and directory140to invalidate the target cache line of the snooped memory access request, sourcing a copy of the target cache line via cache-to-cache intervention, etc. (block834).

If, however, SN machine144determines at block830that the snooped memory access request is not a store-type request, SN machine144additionally determines at block836if the snooped memory access request is a flush request, which causes any modified data to be written to system memory108and the target cache line to be invalidated. A flush does not cause a reservation to be canceled because no update of shared memory occurs; instead, the cache line is only transferred back to system memory. If not, meaning that the snooped memory access request is some type of a read request, SN machine performs the processing, if any, necessary to service the read request (block834), which can include, for example, updating L2 storage array and directory140and/or sourcing a copy of the target cache line via cache-to-cache intervention.

In response to a determination at block836that the snooped memory access request is a flush request, SN machine144further determines at block838whether or not processing unit102is configured to permit a hardware thread of processor core102to remain in a wait state despite the castout or invalidation from L2 storage array and directory140of the cache line containing the flag on which the hardware thread was awaiting an update. If so, the process passes directly to block834. If not, SN machine144issues a SN_Flush command specifying the target address to the processor core120via reload bus174. The process then passes to block834, which depicts SN machine144servicing the snooped flush request, for example, by writing any modified data to system memory108and then invalidating the target cache line in L2 storage array and directory140. Following block834, the process returns toFIG. 8Avia page connector D and ends at block842.

With reference now toFIG. 9, there is illustrated a high level logical flowchart of an exemplary method of processing invalidate and flush commands in a processor core120of data processing system100in accordance with one embodiment. The process ofFIG. 9begins at block900in response to receipt by processor core120of an inbound command from L2 cache130via reload bus174. In at least one preferred embodiment, the command specifies a command type and a target address.

The process then proceeds to block902, which illustrates processor core120determining whether the inbound command is an RSV_Invalidate command or SN_Invalidate command as discussed above with reference to blocks814and832. If so, the process passes to block908, which is described below. If, however, the inbound command is not an RSV_Invalidate or SN_Invalidate command, processor core120additionally determines at block904whether or not the inbound command is a CO_Invalidate command as described above with reference to block706. If not, meaning the command is a SN_Flush command as described above with reference to block840, processor core120refrains from resetting any of wait flags125, and the process proceeds directly to block910, which is described below.

However, in response to a determination at block904that the command is a CO_Invalidate command, processor core120additionally determines at block906whether or not processing unit102is configured to permit a hardware thread of processor core102to remain in a wait state despite the castout or invalidation from L2 storage array and directory140of the cache line containing the flag on which the hardware thread was awaiting an update. If so, processor core102refrains from resetting any of wait flags125, and the process passes to block910. If, however, a negative determination is made at block906, processor core120resets each wait flag125for which the associated address register129stores an address matching the target address of the inbound command (block908). As discussed below with reference to block1002ofFIG. 10, resetting the wait flag125of a hardware thread causes the hardware thread to end its wait state and resume execution.

The process ofFIG. 9passes from block908to block910, which illustrates the processor core120invalidating in L1 cache126any valid copy of the target cache line identified by the target address of the inbound command, thus maintaining the inclusivity of L2 cache130. Thereafter, the process ofFIG. 9ends at block912.

Referring now toFIG. 10, there is depicted a high level logical flowchart of an exemplary method of managing the wait state of a hardware thread of a processor core in accordance with one embodiment. The illustrated process can be performed for each hardware thread supported by processor core120that is in a wait state, as indicated by the associated wait flag125being set.

The process ofFIG. 10begins at block1000and then proceeds to blocks1002-1006, which illustrates processor core120monitoring for the occurrence of any event that would end the wait state of the hardware thread. For example, at block1002, processor core120determines if the wait flag125associated with a hardware thread in a wait state has been reset, for example, at block908ofFIG. 9. In addition, at block1004, processor core120monitors for any interrupt for the hardware thread that is in the wait state. Processor core120additionally monitors at block1006for any implementation-specific event would indicate that the wait state of the hardware thread should be terminated. If none of these events is detected, the process ofFIG. 10continues to iterate at blocks1002-1006. If, however, any of these events is detected, processor core120ends the wait state of the hardware thread and resumes instruction execution in the hardware thread (block1008), either in the suspended instruction sequence or in an interrupt handler. Thereafter, the process ofFIG. 10ends at block1010. It will be appreciated that, because wait flags125reside in processor core120, the determination by the processor core120of whether a wait state of its hardware threads should end can made be at reduced latency as compared to prior art systems.

Design flow1100may vary depending on the type of representation being designed. For example, a design flow1100for building an application specific IC (ASIC) may differ from a design flow1100for designing a standard component or from a design flow1100for instantiating the design into a programmable array, for example a programmable gate array (PGA) or a field programmable gate array (FPGA) offered by Altera® Inc. or Xilinx® Inc.

FIG. 11illustrates multiple such design structures including an input design structure1120that is preferably processed by a design process1110. Design structure1120may be a logical simulation design structure generated and processed by design process1110to produce a logically equivalent functional representation of a hardware device. Design structure1120may also or alternatively comprise data and/or program instructions that when processed by design process1110, generate a functional representation of the physical structure of a hardware device. Whether representing functional and/or structural design features, design structure1120may be generated using electronic computer-aided design (ECAD) such as implemented by a core developer/designer. When encoded on a machine-readable data transmission, gate array, or storage medium, design structure1120may be accessed and processed by one or more hardware and/or software modules within design process1110to simulate or otherwise functionally represent an electronic component, circuit, electronic or logic module, apparatus, device, or system such as those shown herein. As such, design structure1120may comprise files or other data structures including human and/or machine-readable source code, compiled structures, and computer-executable code structures that when processed by a design or simulation data processing system, functionally simulate or otherwise represent circuits or other levels of hardware logic design. Such data structures may include hardware-description language (HDL) design entities or other data structures conforming to and/or compatible with lower-level HDL design languages such as Verilog and VHDL, and/or higher level design languages such as C or C++.

Design process1110may include hardware and software modules for processing a variety of input data structure types including netlist1180. Such data structure types may reside, for example, within library elements1130and include a set of commonly used elements, circuits, and devices, including models, layouts, and symbolic representations, for a given manufacturing technology (e.g., different technology nodes, 32 nm, 45 nm, 110 nm, etc.). The data structure types may further include design specifications1140, characterization data1150, verification data1160, design rules1190, and test data files1185which may include input test patterns, output test results, and other testing information. Design process1110may further include, for example, standard mechanical design processes such as stress analysis, thermal analysis, mechanical event simulation, process simulation for operations such as casting, molding, and die press forming, etc. One of ordinary skill in the art of mechanical design can appreciate the extent of possible mechanical design tools and applications used in design process1110without deviating from the scope and spirit of the invention. Design process1110may also include modules for performing standard circuit design processes such as timing analysis, verification, design rule checking, place and route operations, etc.

Design structure1190may also employ a data format used for the exchange of layout data of integrated circuits and/or symbolic data format (e.g., information stored in a GDSII (GDS2), GL1, OASIS, map files, or any other suitable format for storing such design data structures). Design structure1190may comprise information such as, for example, symbolic data, map files, test data files, design content files, manufacturing data, layout parameters, wires, levels of metal, vias, shapes, data for routing through the manufacturing line, and any other data required by a manufacturer or other designer/developer to produce a device or structure as described above and shown herein. Design structure1190may then proceed to a stage1195where, for example, design structure1190: proceeds to tape-out, is released to manufacturing, is released to a mask house, is sent to another design house, is sent back to the customer, etc.

As has been described, in at least one embodiment, a data processing system includes multiple processing units all having access to a shared memory. A data processing system includes multiple processing units all having access to a shared memory. A processing unit includes a lower level cache memory and a processor core coupled to the lower level cache memory. The processor core includes an execution unit for executing instructions in a plurality of simultaneous hardware threads, an upper level cache memory, and a plurality of wait flags each associated with a respective one of the plurality of simultaneous hardware threads. The processor core is configured to set a wait flag among the plurality of wait flags to indicate the associated hardware thread is in a wait state in which the hardware thread suspends instruction execution and to exit the wait state based on the wait flag being reset.

While various embodiments have been particularly shown and described, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the appended claims and these alternate implementations all fall within the scope of the appended claims.

Although a particular embodiment of a memory hierarchy has been described in which L1 and L2 caches are incorporated within a processing unit, those skilled in the art will appreciate that a greater or lesser number of levels of cache hierarchy may be employed. Further, these levels of cache hierarchy may include in-line or lookaside caches and may include one or more levels of off-chip cache. Further, the level of cache hierarchy at which coherency is determined may differ from that discussed with reference to the described embodiments.

Further, although aspects have been described with respect to a computer system executing program code that directs the functions of the present invention, it should be understood that present invention may alternatively be implemented as a program product including a computer-readable storage device storing program code that can be processed by a data processing system. The computer-readable storage device can include volatile or non-volatile memory, an optical or magnetic disk, or the like. However, as employed herein, a “storage device” is specifically defined to include only statutory articles of manufacture and to exclude signal media per se, transitory propagating signals per se, and energy per se.

The program product may include data and/or instructions that when executed or otherwise processed on a data processing system generate a logically, structurally, or otherwise functionally equivalent representation (including a simulation model) of hardware components, circuits, devices, or systems disclosed herein. Such data and/or instructions may include hardware-description language (HDL) design entities or other data structures conforming to and/or compatible with lower-level HDL design languages such as Verilog and VHDL, and/or higher level design languages such as C or C++. Furthermore, the data and/or instructions may also employ a data format used for the exchange of layout data of integrated circuits and/or symbolic data format (e.g. information stored in a GDSII (GDS2), GL1, OASIS, map files, or any other suitable format for storing such design data structures).