Techniques for implementing barriers to efficiently support cumulativity in a weakly-ordered memory system

A technique for operating a cache memory of a data processing system includes creating respective pollution vectors to track which of multiple concurrent threads executed by an associated processor core are currently polluted by a store operation resident in the cache memory. Dependencies in a dependency data structure of a store queue of the cache memory are set based on the pollution vectors to reduce unnecessary ordering effects. Store operations are dispatched from the store queue in accordance with the dependencies indicated by the dependency data structure.

BACKGROUND

The disclosure is generally directed to a data processing system having a weakly-ordered memory system and, more particularly, to techniques for implementing barriers to efficiently support cumulativity in a data processing system having a weakly-ordered memory system.

In computing, a memory model describes the interactions of threads through memory and how threads share data. Memory barriers are widely utilized in data processing systems that are configured to perform out-of-order program execution, which refers to reordering of memory operations (i.e., load and store operations) for execution. A barrier instruction (barrier) can, for example, cause all load instructions (loads) and store instructions (stores) prior to the barrier to be committed prior to any loads and stores issued following the barrier. Some architectures provide separate acquire and release barriers that address the visibility of read-after-write operations from the point of view of a reader or writer, respectively. Still other architectures provide separate barriers to control ordering between different combinations of operations targeting system memory and input/output (I/O) memory.

BRIEF SUMMARY

A technique of operating a cache memory of a data processing system includes creating respective pollution vectors to track which of multiple concurrent threads executed by an associated processor core are currently polluted by a store operation resident in the cache memory. Dependencies in a dependency data structure of a store queue of the cache memory are set based on the pollution vectors to reduce unnecessary ordering effects. Store operations are dispatched from the store queue in accordance with the dependencies indicated by the dependency data structure.

DETAILED DESCRIPTION

The illustrative embodiments provide a cache and a data processing system that implement barriers to efficiently support cumulativity in a weakly-ordered memory system.

It should be understood that the use of specific component, device, and/or parameter names are for example only and not meant to imply any limitations on the invention. The invention may thus be implemented with different nomenclature/terminology utilized to describe the components/devices/parameters herein, without limitation. Each term utilized herein is to be given its broadest interpretation given the context in which that term is utilized. As used herein, the term ‘coupled’ may encompass a direct connection between components or elements or an indirect connection between components or elements utilizing one or more intervening components or elements. As may be used herein, the term ‘system memory’ is synonymous with the term ‘main memory’ and does not include ‘cache’ or ‘cache memory’.

Modern processors typically include storage hierarchies (i.e., caches) integrated into a single integrated circuit. For example, modern processors may include one or more processor cores that include level 1 (L1) instruction and/or data caches and level 2 (L2) instruction and/or data caches coupled to a shared interconnect bus. In order to increase efficiency, processor chips are often designed with a store queue (STQ) that is typically located in an L2 cache and receives stores from a write-through L1 cache for coalescing and processing into the L2 cache. A STQ typically includes byte-addressable storage for a number of cache lines (e.g., 8 to 16 cache lines).

With reference now to the figures and in particular, with reference toFIG. 1, a multiprocessor data processing system (MP)100is illustrated that includes one or more processor chips101, memory109, and input/output (I/O) device(s)115. As is shown, I/O device(s)115have an associated I/O controller113and memory109has an associated memory controller110that controls access to memory109. Processor chips101are coupled to memory109and I/O devices115via an interconnect111(e.g., a system bus that includes address, data, and control lines) by which processor chips101communicate with each other and with memory109, I/O devices115, and other peripheral devices. Interconnect111may be a bifurcated bus with a data bus for routing data and a separate address bus for routing address transactions and other operations or a more generalized interconnect possibly consisting of multiple point-to-point links between processor chips101.

Processor chips101each include multiple (e.g., eight) processor cores103(each of which may execute one or more threads102and have an associated L1 cache105and an L2 cache107. Each cache105and107includes a cache directory, an array of cache lines, and all data operations are completed according to a coherency protocol, e.g., a MESI coherency protocol or a variant thereof. The various features of the invention may be carried out by logic components on processor chips101and affect buffering of store operations at store queue (STQ)117and selection of entries for dispatch. For illustrative purposes, the various embodiments are described from the perspective of updating a cache line in an L2 cache with store operations and synchronization operations issued by a processor core and temporarily buffered in an STQ entry. An exemplary cache line may include multiple blocks/granules of data, corresponding to individual bytes, words, double words, etc., each of which may be the target of an update by a processor-issued store operation. The specific size of each cache line and number of updateable data blocks/granules may differ from system to system.

While the present invention is described with specific reference to an L2 cache within a multi-level cache architecture, it should be understood that the disclosed embodiments may be implemented at a different cache level. Embodiments of the present disclosure are described with reference to MP100and component parts of MP100illustrated byFIGS. 1, 4, and 10(described below), but the present invention may be applied to different configurations of data processing systems that are not necessarily conventional. As an example, embodiments of the present disclosure may be implemented within a non-uniform memory access (NUMA) system, wherein the system memory (random access memory (RAM)) is divided among two or more memory arrays (having separate memory controllers connected to the system bus) and allocated among the processing units. Also, MP100may include additional hardware components not shown inFIG. 1, or have a novel interconnect architecture for existing components. MP100may also have a different number of processing units. Those skilled in the art will therefore appreciate that the present invention is not limited to the generalized data processing system illustrated inFIG. 1.

Weakly-ordered memory systems exploiting so called ‘weak memory models’ allow for a great deal of reordering of operations and for storage modifying operations to affect other processors in a non-atomic fashion (i.e., stores may take effect at various processor cores at different points in time). In weakly-ordered memory systems, in certain circumstances, it is desirable to enforce ordering and atomicity of operations. A typical mechanism for enforcing operation ordering and atomicity has utilized a ‘synchronization fence’, or ‘barrier’ instruction. Barrier instructions (barriers) force various load and store instructions (loads and stores) on either side of the barrier to be performed in-order relative to the barrier and to possibly restore the atomicity of stores (depending on barrier type) under certain circumstances. Barrier performance is generally a critical aspect of weak memory model machines and, as such, it is desirable to ensure that barriers execute in an efficient manner. In particular, achieving atomicity can often require that a barrier executed by one thread cause operations performed by another thread to be propagated in a specific manner in order to restore atomicity.

With reference toFIG. 2, program snippets executed by thread zero (T0), thread 1 (T1), and thread 2 (T2) are provided to illustrate a notion referred to as A-cumulativity. In the program snippets ofFIG. 2(and similarly inFIG. 3discussed below) it is assumed that threads ‘T0’ and ‘T1’ execute within data processing system100on a same processor core103(thereby sharing an L1 cache105) and thread ‘T2’ executes on a different processor core and therefore accesses a different L1 cache105. In the program snippets, it is assumed that all locations (i.e., addresses ‘A’ and ‘B’) start with an initial value of ‘0’, ‘SYNC’ is a barrier instruction, and ‘<dep>’ is an instruction or sequence of instructions that creates a data dependency that requires loads (i.e., LD B and LD A) on thread ‘T2’ to be performed in program order (this can be achieved, for example, by utilizing the value returned by an earlier load to form an address of a subsequent load). When threads ‘T0’ and ‘T1’ execute on a single processor core (i.e., share an L1 cache), it is possible for the thread ‘T1’ to read a value stored by ‘T0’ (e.g., upon executing ST A, 1) from the L1 cache before a store to address ‘A’ (e.g., ST A, 1) has propagated to the thread ‘T2’, which executes on a different processor core. Following execution of a load to address ‘A’ (e.g., LD A), the thread ‘T1’ executes a SYNC followed by a store to address ‘B’ (e.g., ST B, 1).

Since the barrier (SYNC) is cumulative (i.e., any stores by other threads that are visible to the thread executing the barrier must also be propagated by the barrier ahead of any stores that occur in the thread after the barrier instruction), the SYNC for the thread ‘T1’ ensures that the store to address ‘A’ (i.e., ST A, 1) becomes visible to any given processor core (in this case the processor core that executes the thread ‘T2’) before the store to address ‘B’ (i.e., ST B, 1) becomes visible to that processor core (T2). In conventional implementations, this is achieved by having barriers from a given processor core force all older stores, regardless of the thread that executed the store, through a store queue (STQ) of an associated L2 cache before any stores from that core that are younger than the barrier. The above scenario is referred to herein as ‘A-cumulativity’. Unfortunately, this cross-thread ordering occurs whether or not the thread executing the barrier has actually read from storage locations updated by other cross-thread stores. In the absence of a read that establishes the visibility of a cross-thread store to the thread executing the barrier, it is not strictly necessary to propagate the other thread store ahead of the barrier. While the conventional implementation is relatively simple to realize, the conventional implementation can cause performance delays for a given barrier which may have to wait for many stores in the STQ that are not architecturally required to be ordered by the barrier.

Execution of the exemplary program inFIG. 2illustrates the property of causality in a multiprocessor data processing system. As used herein ‘causality’, which is a desirable property in multiprocessor programs, is defined as being preserved if, during execution of a multiprocessor program, a given thread of execution cannot read the effects (e.g., the LD of B in T2) of a computation before the writes that caused the computation (e.g. the ST of A by T0) can be read by the given thread.

InFIG. 2, thread ‘T0’ executes a store200that writes a value of ‘1’ to address ‘A’ in the distributed shared memory system. This update of address ‘A’ propagates to thread ‘T1’, and load210executed by thread ‘T1’ therefore returns a value of 1 (as thread ‘T0’ and thread ‘T1’ execute on a same processor core103and access a same L1 cache105). Even though the memory update made by store200has propagated to thread ‘T1’, that memory update may not yet have propagated to thread ‘T2’ (as thread ‘T2’ executes on a different processor core103and accesses a different L1 cache105). If store214executes on thread ‘T1’ and the associated memory update propagates to thread ‘T2’ before the memory update of store200propagates to thread ‘T2’, causality would be violated because the store of the value of ‘1’ to address ‘B’, which is an effect of the store to address ‘A’, would be visible to thread ‘T2’ before the memory update associated with store200was visible to thread ‘T2’.

To guarantee causality in a weak memory model system, barrier212(i.e., a synchronization instruction (SYNC)) is implemented to ensure that store214does not take effect or begin propagating its memory update to other processor cores until load210has bound to its value. In addition, barrier212also ensures that the memory update associated with store200propagates to thread ‘T2’ before the memory update associated with store214. Thus, causality is preserved because the cause of the computation (i.e., the memory update of store200) is visible to thread ‘T2’ before the result of the computation (i.e., the memory update of store214). Data dependency222is also enforced by thread ‘T2’ to ensure that the thread ‘T2’ executes loads220and224and binds their values in program order to guarantee that the thread ‘T2’ properly observes the memory updates made by the thread ‘T0’ and the thread ‘T1’.

With reference toFIG. 3, different program snippets, executed by thread zero (T0), thread 1 (T1), and thread 2 (T2) are provided to illustrate the notion referred to as B-cumulativity. InFIG. 3, it is assumed that threads ‘T0’ and ‘T1’ execute on a same processor core103, and thread ‘T2’ executes on a different processor core103. Thread ‘T0’ executes a store300that writes a value of ‘1’ to address ‘A’ in the distributed shared memory system, a SYNC302, and a store314that writes a value of ‘1’ to address ‘B’ in the distributed shared memory system. The thread ‘T1’ executes a load320that reads a value at address ‘B’ in the distributed shared memory system, a data dependency (<dep>)304, and a store306that writes a value of ‘1’ to address ‘C’ in the distributed shared memory system. The thread ‘T2’ executes a load308that reads a value at address ‘C’ in the distributed shared memory system, a data dependency (<dep>)310, and a load340that reads a value at address ‘A’ in the distributed shared memory system. In the program snippets, the B-cumulativity property of SYNC302ensures that store300propagates to any given processor core103before any store (in this case store306) that occurs after a load that has read from any store ordered after the barrier (in this case store314). B-cumulativity is extended recursively through as many threads as are applicable (by virtue of reading some store ordered after the barrier or ordered after a load that has read from a store previously ordered after the barrier). Therefore SYNC302, executed by the thread ‘T0’, ensures that store314to address ‘B’ (i.e., ST B, 1) which occurs after SYNC302on the thread ‘T0’ and store306to address ‘C’ (i.e. ST C, 1) will occur at all processor cores103in the system after store300to address ‘A’ (i.e., ST A, 1). This ensures that the thread ‘T2’ will read the new value of ‘1’ at the address ‘A’ if thread ‘T1’ reads the value of ‘1’ at the address ‘B’.

With reference toFIG. 4, store queue (STQ)117of processor chip101ofFIG. 1is illustrated in additional detail. As illustrated, STQ117includes a collection of entries410comprised of standard registers for storing information regarding store and barrier operations, namely address register411, data register413, control bits415, and valid bit417. Address register411contains the address, if applicable, of the operation in the entry, data register413contains store data values if the entry holds a store operation, and valid bit417indicates that entry contains a valid operation. STQ117also includes a byte enable register (not shown) that includes a number of bits, each corresponding to a smallest size of store granule within data register413indicating those bytes, if any, in register413that contain valid data. Among other control information, control bits415also include a gather bit412and a transaction type (ttype) field414. Gather bit412is utilized to determine whether subsequent store operations to the same address may be gathered (also known as coalescing) into the entry. The interval of time in which gather bit412is active is known as a ‘gather window’. Such gathering of stores reduces traffic to L2 cache107and to main memory109. Transaction type (ttype) field414is utilized to indicate the type of operation contained in the entry within STQ117, minimally whether the associated operation is a store or some form of barrier instruction (SYNC). For simplicity, the discussion herein utilizes cache lines having a length/capacity of 128-bytes that are updated via a plurality of processor-issued store operations.

STQ117also includes a dependency matrix408that includes a number of bits, where each row represents dependencies of each store queue entry on other store queue entries. For example, a ‘1’ in a row indicates that the entry corresponding to that row cannot be dispatched until the STQ entry corresponding to the column with the ‘1’ has dispatched and, if necessary, completed processing in RC machine421. For example, as depicted inFIG. 4, store queue entry ‘0’ is dependent on store queue entry ‘1’ and, as such, store queue entry ‘0’ cannot be dispatched before store queue entry ‘1’ has been dispatched and completed processing in RC machine421. STQ controller405includes a write select (Wr_sel) pointer404and arbitration (Arb) logic406. Write select pointer404selects empty entries to hold new operations when a processor core103sends a new operation to STQ117that does not gather into an existing entry. It should be appreciated that write select pointer404can utilize any appropriate algorithm to select an empty store queue entry, such as with a priority encode algorithm that enables write select pointer404to select an empty entry from any entry with valid bit417set to ‘0’ (indicating an entry that may be overwritten).

Arbitration logic406examines STQ117for eligible entries to send to RC dispatch logic419for dispatch to RC machines421. A store queue entry410is eligible for transmission to RC dispatch logic419when the dependency matrix row corresponding to the particular store queue entry indicates that all dependencies are cleared and other necessary processing in RC machines421have completed. RC machines421independently and concurrently service load (LD) and store (ST) requests received from an affiliated processor core103.

In order to service remote memory access requests originating from non-affiliated processor cores103, i.e., processor cores that do not share an L2 cache, L2 cache107may also include multiple snoop machines (not shown). Each snoop machine can independently and concurrently handle a remote memory access request “snooped” from local interconnect111. As will be appreciated, the servicing of memory access requests by RC machines421may require the replacement or invalidation of memory blocks within a cache array (not shown) of L2 cache107. L2 cache107may also include CO (castout) machines (not shown) that manage the removal and writeback of memory blocks from the cache array. While an RC machine421is processing a local memory access request, RC machine421has a busy status and is not available to service another request. RC machine421may, however, perform a directory write to update a relevant entry of a directory while busy. In addition, RC machine421may also perform a cache write to update the relevant cache line of a cache array and other functions.

FIG. 5is a high-level logical flowchart depicting an exemplary conventional process employed in writing a new store queue entry in response to a store queue (STQ) receiving a new store or SYNC operation from an associated processor core. In the discussion ofFIGS. 5-9reference is made to components ofFIGS. 1 and 4, as the components would have conventionally operated, to facilitate better understanding. It should, however, be appreciated thatFIGS. 1 and 4are configured according to the present disclosure, as is further discussed inFIGS. 10-14. The process ofFIG. 5begins at block501in response to, for example, a processor core103issuing a store operation or a SYNC operation to STQ117. In decision block502, STQ controller405determines whether STQ117is full. In response to STQ117being full in block502control transfers to block503, where STQ controller405sends a message instructing processor core103to halt sending store operations and SYNCs until some entries in STQ117have been dispatched by associated RC dispatch logic419. From block503, control returns to block502.

In response to STQ117not being full in block502control transfers to decision block504, where STQ controller405determines whether the issued operation is a SYNC. In response to the issued operation being a SYNC, control transfers to block506. In block506, STQ controller405selects an empty entry in STQ117in which to allocate the SYNC. Next, in block508, STQ controller405sets the dependency vector in dependency matrix408for the SYNC. Then, in block510, STQ controller405clears the other dependency bits. For example, if for a new SYNC operation write select pointer404updates store queue entry ‘0’ and STQ controller405determines that entry ‘0’ is dependent only on entry ‘1’, STQ controller405enters a ‘1’ into row 0, column 1 of dependency matrix408(at block508) while entering a ‘0’ in the rest of the columns in row 0 (at block510). Next, in block512, STQ controller405closes all currently active store entry gather bits412to ensure that a store after the barrier does not re-order ahead of the barrier by gathering into an older entry in STQ117. Then, in block514, STQ controller405clears gather bit412for the SYNC entry (stores may not gather with SYNC operations). From block514control returns to block502.

In response to the issued operation not being a SYNC in block504(i.e., a store operation was received at STQ117), control transfers to decision block509where STQ controller405determines, by examining address registers411and gather bits412, whether an existing entry (for the same cache line address) is currently available for gathering the store operation. It should be appreciated that gathering of store operations involves combining a series of store operations writing to the same cache line in STQ117in the same store queue entry before the cache line is dispatched to the RC dispatch logic419. If STQ controller405determines that the new store operation can be gathered into an existing STQ entry, the process continues to block511, where STQ controller405updates gatherable entry data field413with data of the new store operation. From block511, control returns to block502and continues in an iterative fashion.

In response to a determination at block509that the new store operation cannot be gathered into an existing STQ entry, control transfers to block513. In block513STQ controller405(using write select pointer404) selects an empty entry to allocate to the new store operation. The new data, address, and byte enable data corresponding to the new store operation are inserted into the new entry by STQ controller405. Next, in block515, STQ controller405sets bits in dependency matrix408(if appropriate) that correspond to valid entries in STQ117that have a dependent relationship with the new entry (where the new entry is dependent on the other valid entries). A new entry is dependent on another STQ entry if, among other things, the store operation characterized by the new entry requires an access to the same address as the other store queue entry or the other STQ entry is a SYNC operation. Then, in block517, STQ controller405clears the bits in dependency matrix408corresponding to STQ entries on which the new entry is not dependent. Next, in block518, STQ controller405sets gather bit412of the new entry to enable store gathering in the new entry. Following block518control returns to block502.

With reference toFIG. 6, a flowchart of an exemplary conventional process for setting dependencies in dependency matrix408for SYNCs and stores in STQ117ofFIG. 4is illustrated. The process is initiated in block600in response to STQ117receiving an operation (i.e., a SYNC or store instruction) from processor core103. Next, in decision block602STQ controller405determines whether the received operation is a SYNC. In response to the received operation being a SYNC in block602, control transfers to block604where STQ controller405sets a dependency for the store to all existing valid stores for all threads in STQ117. As described above with reference toFIGS. 2 and 3, setting a dependency to all valid stores regardless of thread partially ensures A and B cumulativity, but may also order more stores than is strictly necessary. Following block604, control transfers to block610where the process terminates. In response to the received operation not being a SYNC (i.e., the received operation is a store) in block602, control transfers to block606where the STQ controller405sets a dependency for the store to any SYNC for any thread. As described above with respect toFIGS. 2 and 3, setting a dependency for the store to the SYNC for any thread partially ensures A and B cumulativity, but may also order more stores than is strictly necessary. Next, in block608, STQ controller405sets a dependency to any matching store (i.e., a store that shares the same target address) for any thread. Following block606, control transfers to block610where the process terminates.

With reference toFIG. 7, a flowchart of an exemplary conventional process for closing a gather window by resetting gather bit412for an entry in STQ117is illustrated. The process depicted inFIG. 7may execute in parallel for all store queue entries. The process is initiated in block700, at which point control transfers to decision block702. In block702, STQ controller405determines whether the entry in STQ117is a SYNC. In response to the entry being a SYNC in block702control loops on block702, as SYNCs are not gathered and therefore gather bit412is never set. In response to the entry not being a SYNC (i.e., the entry is a store) in block702control transfers to decision block704, where STQ controller405determines whether the gather window for the entry is still open (e.g., whether gather bit412is still set).

In response to the gather window not being open (i.e., gather bit412is reset) in block704, control transfers to block702. In response to the gather window being open in block704, control transfers to decision block706. In block706, STQ controller405determines whether a time since a last gather is greater than a threshold. In response to the time since the last gather for the entry not being greater than the threshold in block706, control transfers to block702. In response to the time since the last gather for the entry being greater than the threshold in block706, control transfers to block708where the STQ controller405closes the gather window by resetting gather bit412for the entry. Control then transfers to block702and the process proceeds in an iterative fashion.

In reference now toFIG. 8, illustrated is a high-level logical flowchart of an exemplary conventional process for determining whether a specific entry in STQ117is eligible for dispatch by RC dispatch logic419. The process depicted inFIG. 8may execute in parallel for all store queue entries. The process begins at block800and proceeds to block802, where STQ controller405determines whether or not a particular entry in STQ117is valid. For example, STQ controller405may determine the validity of a particular entry by examining the contents of associated valid bit417. In response to STQ controller405determining that the entry is not valid, the process returns to block802and proceeds in an iterative fashion. Returning again to block802, if STQ controller405determines that the store queue entry is valid, the process proceeds to decision block804where STQ controller405determines whether all dependency bits in dependency matrix408for the entry are cleared.

In response to all dependency bits not being cleared for the entry in block804, control returns to block802. In response to all dependency bits being cleared for the entry in block804, control transfers to decision block806where STQ controller405determines whether the entry is an entry for a SYNC. If the entry does not correspond to a SYNC (i.e., the entry corresponds to a store) in block806, control transfers to decision block810where STQ controller405determines whether gathering is closed (i.e., whether gather bit412for the STQ entry is reset) for the store.

If STQ controller405determines that the entry has not finished gathering associated store operations into the entry in block810, control transfers to block802. However, if STQ controller405determines that the entry has finished gathering in block810, control transfers to block812where STQ controller405marks the entry (e.g., in an unillustrated control bit of control bits415) as available for dispatch. Following block812control transfers to block802where the process continues iteratively.

Returning to block806, when STQ controller405determines that the entry is for a SYNC, control transfers to block808where the STQ controller405determines whether all RC machines421that are performing stores have completed processing of their store operations. Conventionally, RC machines421do not complete a store operation until the store's effects have propagated to all other processor cores or achieved the same net effect. In response to a determination at block808that all RC machines421have not completed performing their respective stores, control transfers to block802. The barrier waiting for all RC machines421to complete store operations for all threads partially ensures A and B cumulativity, but may order more store operations than is strictly necessary. In response to a determination at block808that all RC machines421processing store operations have completed their processing, control transfers to block812where STQ controller405marks the entry in STQ117for the SYNC operation as available for dispatch.

With reference toFIG. 9, a flowchart of an exemplary conventional process for dispatching entries in STQ117to RC machines421and resetting associated entries in dependency matrix408is illustrated. The process is initiated at block900, at which point control transfers to decision block902. In block902, STQ controller405determines whether or not an entry in STQ117is available for dispatch (i.e., whether an entry is marked available for dispatch as described above with respect toFIG. 8). In response to an entry not being available for dispatch, control loops on block902. In response to an entry being available for dispatch in block902, control transfers to block904where STQ controller405selects an entry that is available for dispatch. Next, in decision block906, STQ controller405determines whether the selected entry contains a SYNC operation. In response to the entry containing a SYNC in block906, control transfers to block910(a SYNC requires no direct processing by an RC machine421, but rather is complete based on waiting for RC machines421to complete their prior store operations).

In block910, STQ controller405resets the dependency column in dependency matrix408corresponding to the dispatched entry to indicate the STQ entries formerly dependent on the just dispatched entry are no longer dependent on that entry. For example, if entry 0 is dependent on entry 1, a ‘1’ in row 0, column 1 of dependency matrix408indicates this dependency. When entry 1 dispatches, row 0, column 1 and column 1 in all other rows besides row 1 of dependency matrix408are updated with a ‘0’ to remove the dependency of any entries in STQ117on the recently dispatched entry 1. Next, in block912, STQ controller405resets the valid bit for the selected entry (indicating that the selected entry is no longer valid and may be used by a new operation that is received at STQ117).

In response to the selected entry not being a SYNC in block906(i.e., the entry corresponds to a store), control transfers to decision block908. In block908, STQ controller405determines whether the entry successfully dispatched to an RC machine421. In response to STQ controller405determining that the entry was not successfully dispatched to an RC machine421(e.g., an RC machine421was not available) in block908, control transfers to block902. In response to the STQ controller405determining that the entry was successfully dispatched to an RC machine421in block908, control transfers to block910, then to block912, which have been described, and finally to block902.

According to the present disclosure, the ordering effects of barriers are applied in a more precise manner to reduce undue ordering effects for operations that are not required to be ordered. As described above with respect toFIGS. 2 and 3, when a first thread reads a store from a second thread that is visible to the first thread, before the store has been performed with respect to other processor cores (e.g., the ST A, 1 by Thread 0 relative to Thread 1 inFIG. 2and the ST B, 1 by Thread 0 relative to Thread 1 inFIG. 3), an obligation to order the store that was read according to A-cumulativity and B-cumulativity has been conventionally incurred by the reading thread. At the point the reading thread binds the load value, the reading thread is ‘polluted’ by the store. In the case of A-cumulativity, this means that any barrier executed by the polluted thread must order any polluting store ahead of any stores after the barrier. Similarly for B-cumulativity, any stores executed by a polluted thread after reading a polluted store must be ordered after the store that originally polluted the thread relative to any other processor cores. Any store ordered by a polluted store (by virtue of being after the read of a polluted store by a given thread) are also considered polluted and recursively defines a set of stores ordered by B-cumulativity for a given original polluted store.

According to the present disclosure, a ‘pollution vector’ is created at each entry in STQ117and RC machine421that tracks which threads are currently polluted by the store resident in an entry of STQ117or RC machine421. In at least one embodiment, pollution vectors are as wide in bits as the number of threads on a given processor core103. As described below with respect toFIGS. 11-14, the pollution vectors may be used to more precisely set dependencies in, for example, existing dependency matrix408, to reduce the number of unnecessary ordering effects.

In various embodiments, the addresses of loads (LD Address) that hit in the L1 cache (polluting loads) are broadcast to STQ117and RC machines421of an associated L2 cache where the addresses of the polluting loads are compared to active addresses411in STQ117and active addresses in address register1015in RC machines421. In the case of an address match in an active structure, a respective bit in the pollution vector for that entry is set to indicate the thread that issued the LD hit is polluted by the store resident at the matching entry of STQ117or RC machine421. In this manner, the pollution vector indicates which threads the entry in the active entry of STQ117or RC machine421pollutes.

In one or more embodiments, when a pollution vector bit is set for a given thread, active gather stations for the given thread have their gather windows closed by resetting the appropriate gather bit412to prevent a subsequent store by the given thread (which is ordered for B-cumulativity) from being gathered with an earlier unrelated store. For example, consider the B-cumulativity example ofFIG. 3with an unrelated (and unillustrated) store to address ‘C’ (ST C, 7) that occurs before load320from address ‘B’ (i.e., LD B) on thread ‘T1’. In such a case, store306(the final ST C on Thread 1) needs to be ordered by cumulativity and cannot be gathered into the ST C, 7 before load320. If store306gathered with the assumed ‘ST C, 7’ it would potentially violate B-cumulativity by propagating before store314to other threads. At the point the load on the thread ‘T1’ pollutes that thread, gathering at any active entry of STQ117by the thread must shut down to prevent this error. However, a subsequent store to ‘C’ that occurs after store306on thread ‘T1’ can be gathered with store306.

In various embodiments, when a thread issues a SYNC to L2 cache107, bits in the dependency matrix408for the SYNC are set so as to make the SYNC dependent on the completion of all prior stores from that thread in any entry of STQ117. In addition, the SYNC is also made dependent on any polluting stores in any entry of STQ117to allow the SYNC to precisely honor A-cumulativity obligations. In various embodiments, a SYNC is released from STQ117when the dependency vector for the SYNC clears. It should be appreciated that the pollution vector for a SYNC entry in STQ117is always empty, as SYNCs do not pollute other threads, only stores pollute other threads. Moreover, SYNC operations do not have addresses and therefore no comparison is possible to set pollution vector bits.

In at least one embodiment, when a store is issued to STQ117, the store is made dependent on all prior stores with a matching target address in any thread (to preserve per address ordering known as coherence) and all stores from any other thread (a thread's store cannot pollute itself) that pollute the thread issuing the store. In one or more embodiments, the store waits for all of its dependencies to clear before it can dispatch to an RC machine. It should be appreciated that the disclosed techniques allow a STQ to more precisely honor ordering requirements of barriers, as compared to the conventional approach of making barriers affect all prior stores across all threads.

With reference toFIG. 10, a relevant portion of L2 cache107ofFIG. 4(with logic for implementing aspects of the present disclosure) is illustrated in additional detail. As is illustrated, a pollution vector control1007receives an L1 hit signal from L1 cache105and a load (LD) thread identifier (ID). Pollution vector control1007also receives a plurality of compare signals from compare blocks1005, which receive an LD address (from processor core103) and respectively compare the LD address to addresses maintained in address register411of STQ117. In the event of an address match in STQ117on a hit in L1 cache105, pollution vector control1007creates a pollution vector for an associated entry (in STQ117) in pollution vector block1009. Similarly, RC machines421include a compare block1013that is configured to compare the LD address with an address (for a dispatched entry that was formerly maintained by STQ117in address register411) in address register1015of RC machines421. RC machines421also include a pollution vector control1007athat receives the LD thread ID, the L1 hit signal, and an address match signal and creates a pollution vector that is stored in pollution vector block1009awhen the LD address matches the address stored in address register1015on an L1 hit.

Pollution vector block1009includes pollution vectors for tracking, for each valid store in STQ117of L2 cache107, which threads are polluted by the store. Pollution vectors in pollution vector blocks1009atrack, for each given thread, which threads the store present in read-claim (RC) machines421of L2 cache107currently pollutes. In various embodiments, pollution vectors included in pollution vector blocks1009and1009aare used to more precisely set dependencies in dependency matrix408of L2 cache107to significantly reduce unnecessary ordering effects.

With reference toFIG. 11, a flowchart of an exemplary process for setting a bit of a pollution vector1009or1009afor a thread whose load (LD) hits in L1 cache105and hits an address of an entry (in STQ117) or an address in one of RC machines421, according to the present disclosure, is illustrated. The process begins in block1100when a load instruction is executed by processor core103, at which point control transfers to decision block1102. In block1102, pollution vector control1007(of L2 cache107) determines, by reference to an L1 Hit′ signal from L1 cache105, whether an LD hit occurred in L1 cache105. In response to an LD not hitting in L1 cache105, control loops on block1102. In response to an LD hit in L1 cache105, control transfers from block1102to decision block1104. In block1104, pollution vector control1007determines whether an address of the LD hits in one of RC machines421or in STQ117by examining a result of the comparison, at comparators1005and1013, of the target address of the LD (LD Address) with target addresses in address register411(of STQ117) and target addresses (in address register1015) in each of RC machines421.

In response to the LD address not hitting in STQ117or one of RC machines421in block1104, control transfers to block1102. In response to the LD address hitting in STQ117or one of RC machines421in block1104, control transfers to block1106. In block1106, pollution vector control1007turns on a pollution vector bit for the loading thread on each valid entry of STQ117and RC machine421that is busy on a store with a matching target address unless the entry of STQ117or RC machine421was issued by the same thread as the LD. Next, in block1108, STQ controller405closes a gather window, by resetting gather bit412, for any valid entries of STQ117whose address matches the LD address. Following block1108, control transfers to block1110where the process terminates.

With reference toFIG. 12, a flowchart of an exemplary process for setting a dependency vector in dependency matrix408for a store or SYNC operation entering STQ117, according to the present disclosure, is illustrated. The process begins in block1200when a store or SYNC operation enters STQ117, at which point control transfers to decision block1202. In block1202, STQ controller405(of L2 cache107) determines whether a received operation is a store or a SYNC. In response to a determination at block1202that the received operation is not a SYNC but rather a store, control transfers to block1208. In block1208, STQ controller405sets, in STQ117, dependencies in the received store's dependency vector to all threads' prior stores having a same target address as the received store. Next, in block1210, STQ controller405sets dependencies in the received store's dependency vector to all prior SYNCs for the same thread as the received store. Then, in block1212, STQ controller405sets dependencies in the received store's dependency vector to any other thread's prior store(s) in STQ117whose pollution vector bit for the received store's thread is set. Following block1212, control transfers to block1214where the process terminates.

Returning to block1202, in response to the received operation being a SYNC control transfers to block1204. In block1204, STQ controller405sets dependencies to all prior stores, in STQ117, from the same thread as the SYNC. Next, in block1206, STQ controller405sets dependencies to all prior stores in STQ117whose pollution vector bit for the received SYNC's thread is set. Following block1206, control transfers to block1214where the process terminates.

With reference toFIG. 13, a flowchart of an exemplary process for marking an entry in STQ117(ofFIG. 4) available for dispatch to an RC machine421, according to the present disclosure, is illustrated. It should be appreciated that the process may execute in parallel for each entry in STQ117. The process begins in block1300, at which point control transfers to decision block1302. In block1302, STQ controller405(of L2 cache107) determines whether an entry in STQ117is valid, e.g., by examining valid bit417for the entry. In response to an entry in STQ117not being valid in block1302, control loops on block1302. In response to an entry in STQ117being valid in block1302, control transfers to decision block1304. In block1304, STQ controller405determines whether all dependency bits for the entry are cleared (indicating the entry is ready for dispatch). In response to all dependency bits for the entry not being cleared in block1304, control transfers to decision block1302. In response to all dependency bits for the entry being cleared in block1304, control transfers to decision block1306.

In block1306, STQ controller405determines whether the entry holds a SYNC operation (e.g., by examining transaction type (ttype) field414). In response to the operation for the entry being a SYNC, control transfers from block1306to decision block1308. In block1308, STQ controller405determines whether all RC machines421performing a store issued by the same thread as the SYNC and all RC machines421performing a store that pollutes the SYNC's thread (as indicated by the pollution vector1009abit for the SYNC's thread being set) have completed processing their respective stores. In response to a negative determination at block1308, control transfers to block1302. In response to a positive determination at block1308, control transfers to block1314. In block1314, STQ controller405marks the entry (e.g., in an unillustrated control bit in control bits415) available for dispatch to an RC machine421. Following block1314, the process returns to block1302and proceeds iteratively.

Returning to block1306, in response to determining the entry does not hold a SYNC operation (i.e., the entry holds a store operation), control transfers from block1306to decision block1310. In block1310, STQ controller405determines whether gathering is closed for the entry (e.g., by examining gather bit412for the entry). In response to gathering not being closed for the entry in block1310, control transfers to block1302. In response to gathering being closed for the entry in block1310, control transfers to decision block1312. In block1312, STQ controller405determines whether any RC machine421is working on a store polluting a selected thread (whether a bit of pollution vector1009ais set for the store's thread). In the event any RC machine421is working on a store polluting the selected thread, control transfers from block1312to block1302(as the entry is not ready to dispatch). In the event no RC machine421is working on a store that pollutes the selected thread, control transfers from block1312to block1314which has been described.

With reference toFIG. 14, a flowchart of an exemplary process for dispatching entries in STQ117to RC machines421and resetting associated entries in dependency matrix408, according to the present disclosure, is illustrated. The process is initiated in block1400, at which point control transfers to block1402. In block1402, STQ controller405determines whether an entry is available for dispatch to an RC machine421. In response to an entry not being available for dispatch in block1402, control loops on block1402. In response to an entry being available for dispatch in block1402, control transfers to block1404where STQ controller405selects an entry for dispatch.

Next, in decision block1406, STQ controller405determines whether the selected entry contains a SYNC. In response to a determination at block1406that the selected entry holds a SYNC operation, control transfers to block1410. In response to a determination at block1406that the selected entry does not hold a SYNC operation but rather holds a store operation, control transfers to block1408where STQ controller405determines whether the store was successfully dispatched to an RC machine421. In response to the store not being successfully dispatched in block1408, control transfers to block1402. In response to the store being successfully dispatched in block1408, control transfers to block1409. In block1409, STQ controller405transfers a pollution vector (from pollution vector block1009) for the entry to an RC machine421(more specifically, to pollution vector block1009a). Next, in block1410, STQ controller405resets a dependency column in dependency matrix408corresponding to the dispatched entry to indicate the entries in STQ117formerly dependent on the just dispatched entry are no longer dependent on that entry. Then, in block1412, STQ controller405resets valid bit417for the selected entry. From block1412, control returns to block1402.

Accordingly, techniques have been disclosed herein that implement barrier conditions in a manner that efficiently supports A-cumulativity and B-cumulativity in a weakly-ordered memory system.