Abstract:
A method, computer program product, and system is described that enforces a release consistency with special accesses sequentially consistent (RCsc) memory model and executes release synchronization instructions such as a StRel event without tracking an outstanding store event through a memory hierarchy, while efficiently using bandwidth resources. What is also described is the decoupling of a store event from an ordering of the store event with respect to a RCsc memory model. The description also includes a set of hierarchical read/write combining buffers that coalesce stores from different parts of the system. In addition, a pool component maintains partial order of received store events and release synchronization events to avoid content addressable memory (CAM) structures, full cache flushes, as well as direct write-throughs to memory. The approach improves the performance of both global and local synchronization events since a store event may not need to reach main memory to complete.

Description:
BACKGROUND 
       [0001]    1. Field 
         [0002]    The embodiments are generally directed to managing memory, and more specifically to managing memory among heterogeneous computer components. 
         [0003]    2. Background Art 
         [0004]    A computing device generally includes one or more processing units (e.g., a central processing unit (CPU), a graphics processing unit (GPU), a general purpose GPU (GPGPU), an accelerated processing unit (APU), or the like), that access a shared main memory. The processing units may execute programs (e.g., instructions or threads) that result in accesses to main memory. Because memory accesses may traverse a memory hierarchy including levels of cache and main memory, memory accesses may have different latencies, and may be performed in a different order than what was intended by the programs. In addition there may be conflicts, e.g., when two memory accesses attempt to store data in the same memory location. 
         [0005]    Memory accesses are also called memory events, and examples include a store event (i.e., a memory access request to write data to main memory), a load event (i.e., a memory access request to read data from main memory), and synchronization events that are used to order conflicting memory events. 
         [0006]    Memory consistency models provide rules for ordering memory events. A type of memory consistency model, release consistency with special accesses sequentially consistent (RCsc), provides a framework for event ordering for parallel programs with synchronization. Current systems that implement an RCsc memory model, a write-through (WT) memory system and a write-combining (WC) memory system, have difficulty with synchronization events such as a store release (StRel) synchronization event. 
         [0007]    A StRel synchronization event is a release synchronizing store instruction that acts like an upward memory fence such that prior memory operations are visible to threads that share access to the ordering point before the store event portion of the StRel completes. A load acquire (LdAcq) synchronization event is a synchronizing load instruction that acts as downward memory fence such that later operations cannot occur before this operation. 
         [0008]    Upon executing a StRel synchronization event in a WT memory system, data is immediately written-through to main memory which is an inefficient use of the precious bandwidth resources to main memory. In addition, the system tracks acknowledgements for individual store completions which is highly inefficient. Further, upon receiving a load acquire synchronization event, the system performs a full cache flush to invalidate clean and potentially stale data which makes data reuse in the presence of synchronization impossible. 
         [0009]    The WC memory system uses cache hierarchies to coalesce store events. Executing a StRel synchronization event in the WC triggers a slow and intensive cache flush to determine when the prior stores have completed to a next level of hierarchy. A cache flush entails walking through an entire cache hierarchy to track outstanding store events to completion. 
         [0010]    A hierarchical directory/snooping cache coherence protocol solution is a “read for ownership” solution that could support an RCsc memory consistency model, however, the memory access requests to write data encounter long delays. A requesting processor (e.g., a CPU or GPU) has to read or own a memory block before writing to local cache and completing a store event. 
       BRIEF SUMMARY OF EMBODIMENTS 
       [0011]    What is needed therefore, are embodiments that enforce an RCsc memory model and can execute release synchronization instructions such as a StRel event without tracking an outstanding store event through a memory hierarchy, while efficiently using bandwidth resources. In embodiments, a requesting processor does not have to read or own a memory block before writing in local cache and completing a store event. Embodiments improve the performance of both global synchronization events (e.g., writing to main memory for completion) and local synchronization events (e.g., writing to a common ordering point such as level 2 cache for completion) since the cache hierarchy does not need to be flushed and a store event may not need to reach main memory to complete. Embodiments decouple a store event from an ordering of the store event with respect to a RCsc memory model. 
         [0012]    Embodiments include a method, computer program product, and a system. For example, the system includes a set of hierarchical read/write combining buffers that coalesce stores from different parts of the system. In addition, a component maintains a partial order of received store events and release synchronization events to avoid content addressable memory (CAM) structures, full cache flushes, and direct write-throughs to memory. Embodiments provide RCsc memory model programmability while efficiently using limited bandwidth. 
         [0013]    Certain embodiments include a method, computer program product, and a system. For example, when a store memory event is received, a method embodiment includes writing data to a level n cache, where n is an integer representing the level of cache hierarchy, and writing a store entry that includes an address of the data in the level n cache to a level n pool, where the level n pool maintains a partial order among the store entry, a prior received store entry, and a release marker entry. When a release marker is present, the method further includes ordering the store entry in the level n pool to be after a most-recent release marker. The level n cache and corresponding level n pool are closer to a processor (e.g., core) than a level (n+1) cache and a corresponding level (n+1) pool. For example, when n is 1, the level 1 cache and corresponding level 1 pool are closer to the processor than the level 2 cache and the corresponding level 2 pool. 
         [0014]    Certain embodiments include a computer-readable storage device that includes stored instructions which are executed by a processing unit. In response to receiving a store memory event, instructions are executed that cause the processing unit to perform operations. The operations include writing data to a level n cache, where n is an integer representing the level of cache hierarchy, and writing a store entry that includes an address of the data in the level n cache to a level n pool, where the level n pool maintains a partial order among the store entry, a prior received store entry, and a release marker entry. When a release marker is present, further operations include ordering the store entry in the level n pool to be after a most-recent release marker. 
         [0015]    A further embodiment includes a processing unit including one or more compute units configured to respond to a store memory event. The processing unit writes data to a level n cache, where n is an integer representing the level of cache hierarchy. The processing unit also writes a store entry that includes an address of the data in the level n cache to a level n pool, where the level n pool maintains a partial order among the store entry, a prior received store entry, and a release marker entry. When a release marker is present the processing unit orders the store entry in the level n pool to be after a most-recent release marker. 
         [0016]    Further features and advantages of the embodiments, as well as the structure and operation of various embodiments, are described in detail below with reference to the accompanying drawings. It is noted that the embodiments are not limited to the specific embodiments described herein. Such embodiments are presented herein for illustrative purposes only. Additional embodiments will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS/FIGURES 
         [0017]    The accompanying drawings, which are incorporated herein and form part of the specification, illustrate the embodiments and, together with the description, further serve to explain the principles of the embodiments and to enable a person skilled in the pertinent art to make and use the embodiments. Various embodiments are described below with reference to the drawings, wherein like reference numerals are used to refer to like elements throughout. 
           [0018]      FIG. 1  illustrates an APU environment, according to an embodiment. 
           [0019]      FIG. 2  illustrates a write-back write-combine system, according to an embodiment. 
           [0020]      FIG. 3  illustrates a GPU, according to an embodiment. 
           [0021]      FIG. 4  illustrates a method of handling the receipt of memory events, according to an embodiment. 
           [0022]      FIG. 5  illustrates a method of evicting entries, according to an embodiment. 
           [0023]      FIG. 6  illustrates a method of handing memory synchronization events, according to an embodiment. 
           [0024]      FIG. 7  illustrates a method of evicting entries from a queue, according to an embodiment. 
           [0025]      FIG. 8  illustrates an example computer system in which embodiments may be implemented. 
       
    
    
       [0026]    The embodiments will be described with reference to the accompanying drawings. Generally, the drawing in which an element first appears is typically indicated by the leftmost digit(s) in the corresponding reference number. 
       DETAILED DESCRIPTION OF EMBODIMENTS 
       [0027]    In the detailed description that follows, references to “one embodiment,” “an embodiment,” “an example embodiment,” etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described. 
         [0028]    The term “embodiments” does not require that all embodiments include the discussed feature, advantage or mode of operation. Alternate embodiments may be devised without departing from the scope of the disclosure, and well-known elements of the disclosure may not be described in detail or may be omitted so as not to obscure the relevant details. In addition, the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the disclosure. For example, as used herein, the singular forms “a,” “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises,” “comprising,” “includes” and/or “including,” when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof. 
         [0029]    Computing devices process data and provide many applications to users. Example computing devices include, but are not limited to, mobile phones, personal computers, workstations, and game consoles. Computing devices use a central processing unit (“CPU”) to process data. A CPU is a processor which carries out instructions of computer programs or applications. For example, a CPU carries out instructions by performing arithmetical, logical and input/output operations. In an embodiment, a CPU performs control instructions that include decision making code of a computer program or an application, and delegates processing to other processors in the electronic device, such as a graphics processing unit (“GPU”). 
         [0030]    A GPU is a processor that is a specialized electronic circuit designed to rapidly process mathematically intensive applications on electronic devices. The GPU has a highly parallel structure that is efficient for parallel processing of large blocks of data, such as mathematically intensive data common to computer graphics applications, images and videos. The GPU may receive data for processing from a CPU or generate data for processing from previously processed data and operations. In an embodiment, the GPU is a hardware-based processor that uses hardware to process data in parallel. 
         [0031]    Due to advances in technology, a GPU also performs general purpose computing (also referred to as GPGPU computing). In the GPGPU computing, a GPU performs computations that traditionally were handled by a CPU. An accelerated processing unit (APU) includes at least the functions of a CPU and a GPU. The GPU can be a GPGPU. 
         [0032]    In an embodiment, a GPU includes one or more compute units (CUs) that process data. A compute unit (CU) includes arithmetic logic units (ALUs) and other resources that process data on the GPU. Data can be processed in parallel within and across compute units. 
         [0033]    In an embodiment, a control processor on a GPU schedules task processing on compute units. Tasks include computation instructions. Those computation instructions may access data stored in the memory system of a computing device and manipulate the accessed data. In an embodiment, the data may be stored in volatile or non-volatile memory. An example of volatile memory includes random access memory (RAM). Examples of RAM include dynamic random access memory (DRAM) and static random access memory (SRAM). Volatile memory typically stores data as long as the electronic device receives power. Examples of non-volatile memory include read-only memory (ROM), flash memory, ferroelectric RAM (F-RAM), hard disks, floppy disks, magnetic tape, optical discs, etc. Non-volatile memory retains its memory state when the electronic device loses power or is turned off. 
         [0034]      FIG. 1  illustrates an APU environment, according to an embodiment. In the example shown, system  100  is an APU environment that includes CPU  110 , GPU  130 , main memory  150 , and bus  140 . 
         [0035]    Bus  140  may be any type of communication infrastructure used in computer systems, including a peripheral component interface (PCI) bus, a memory bus, a PCI Express (PCIE) bus, front-side bus (FSB), hypertransport (HT), or another type of communication structure or communications channel whether presently available or developed in the future. 
         [0036]      FIG. 2  illustrates a write-combining (WC) system, according to an environment. WC system  200  includes a conventional GPU and bus  140 . WC system  200  includes CUs  210   a  and  210   b , and a multi-tiered write-combining cache including Level 1 (L1) caches  220   a  and  220   b , as well as Level 2 (L2) cache  240 . L2 cache  240  is shared among CUs  210  in system  200 . Bus  230  is substantially the same as bus  140  of  FIG. 1 . 
         [0037]    In WC system  200 , write-combining caches provide coherence for data-race-free programs (e.g., programs free of memory accesses conflicts) by writing updates to an ordering point (e.g., L2 cache  240  or main memory  150 ) at synchronization events. In addition, write-combining caches use a write-back policy that keeps previously written data in cache longer than the WT alternative. This policy increases the chance that the results of two store events coalesce in cache before consuming the limited bandwidth at a synchronization event to evict the data to a next-level cache in the memory hierarchy. However, the cost of a synchronization event in WC system  200  is high. Upon execution of a StRel synchronization event, for example, WC system  200  must perform a full cache flush to find and flush outstanding writes throughout the cache hierarchy to completion to ensure proper ordering of memory events. A write is data written by a store event. WC system  200  searches L1 caches  220   a  and  220   b  as well as L2 cache  240  to find data previously written, also called dirty data. Once dirty data is found, WC system  200  evicts the dirty data to a next level of cache hierarchy, or main memory  150  if a next-level cache is not present, and waits for acknowledgements to be received before processing another memory event. The cache flush process is a very slow and tedious process to be avoided. 
         [0038]    Embodiments utilize read-write combining caches to enforce a RCsc model, and avoid tracking outstanding store events via the memory hierarchy. Embodiments utilize extra knowledge to manage a partial order of outstanding writes and release synchronization events separately from the outstanding writes that move through a memory hierarchy. Because store events are not tracked via the memory hierarchy, acknowledgement messages are not needed for store event completions resulting in reduced traffic. In addition, embodiments allow a store event to complete without having to write-through to main memory  150 . 
         [0039]    A memory fence is an operation used to delay a memory access until the previous memory access has been performed. Synchronization events utilize memory fences to provide order by making results visible (i.e., available for reading) in a globally shared memory so that other instructions in the computing device may utilize the results. 
         [0040]    The RCsc consistency model requires that prior store events that occur before a StRel synchronization event be visible (i.e., readable) in a specified scope (e.g., global or local) and that loads after a LdAcq appear to be executed after the LdAcq. Also, the LdAcqs and StRels themselves obey sequential consistency so a StRel needs to complete the writes before a LdAcq may proceed to read the writes. 
         [0041]    A scope is a group of threads that access a shared memory or a common ordering point. Global scope requires global synchronization and a store event is complete when the data written in main memory  150  is visible to other threads in the system. Local scope requires local synchronization and a store event is complete when the data is written to a common ordering point such as a level 2 cache, and is visible to threads that share access to that common ordering point. The ability to synchronize to a local scope when possible, instead of having to synchronize to a global scope provides considerable savings with regards to limited bandwidth access to main memory, reduced latency, and power savings. 
         [0042]      FIG. 3  illustrates a GPU, according to an embodiment. System  300  includes a memory hierarchy of read-write combining buffers L1 cache  320   a , L1 cache  320   b , and L2 cache  340 , corresponding co-located pool components L1 pool  350   a , L1 pool  350   b  and L2 pool  360 , as well as compute units CU  310   a  and CU  310   b.    
         [0043]    Pool components contain knowledge to track outstanding store events separately from the ordering of store events in the memory hierarchy that occurs when enforcing an RCsc memory model. Pool components L1 pool  350   a , L1 pool  350   b , and L2 pool  360  contain knowledge that enables system  300  to track which prior writes and corresponding addresses that may not yet be written back to main memory  150 , without having to perform a cache walk, or implementing power-hungry CAM lookups to track acknowledgements. 
         [0044]    Pool components L1 pool  350   a , L1 pool  350   b , and L2 pool  360  may be implemented for example, by a synchronization First In First Out (S-FIFO) or a Bloom-filter with signatures as are well known in the art. A pool component may contain entries associated with a store event or a release synchronization event. An entry associated with a store event may include but is not limited to an address in main memory and a thread identity of a store event. A thread identity is used to recognize different threads. An entry associated with a release synchronization event is a release marker that may include but is not limited to a thread identity of a release synchronization event. 
         [0045]      FIG. 4  illustrates a method of handling the receipt of memory events, according to an embodiment. In one example, system  100  and system  300  may be used to demonstrate method  400 . It is to be appreciated that operations in method  400  may be performed in a different order than shown, and method  400  may not include all operations shown. For ease of discussion, and without limitation, method  400  will be described in terms of elements shown in  FIG. 1  and  FIG. 3 . 
         [0046]    Method  400  begins at step  410  and proceeds to step  415 . 
         [0047]    At step  415 , memory events such as a store, a load, or a release synchronization are received from a compute unit such as CU  310   a . The memory events are read from a software program e.g., instruction code, in program order. 
         [0048]    When a load event is received, at step  420 , method  400  looks for the address of the data in L1 cache  320   a . At step  425 , if the data is found in L1 cache  320   a  (a hit), the data is read and method  400  returns to step  415  to await another memory event. If the data is not found (a miss), method  400  proceeds to step  427 . If L2 cache  340  is not present, method  400  proceeds to step  430 . 
         [0049]    At step  425 , if the data is partially found (a partial hit), the dirty data in L1 cache  320   a  is written to L2 cache  340 . Method  400  proceeds to step  427 . 
         [0050]    At step  427 , method  400  looks for the data, or the remaining data in the case of a partial hit, in L2 cache  340 ; if the data or the remaining data is found (a hit), the data is read and method  400  returns to step  415 . Thus, the load can be completed at level 2 rather than at main memory  150 . 
         [0051]    At step  427 , if the data is not found in L2 cache  340  (a miss), or if L2 cache  340  is not present, method  400  proceeds to step  430 . 
         [0052]    At step  427 , if the data is partially found and read from L2 cache  340  (a partial hit), the dirty data in L2 cache  340  is written to main memory  150 . Data at L1 cache  320   a  and L1  320   b  with that address are invalidated, and method  400  proceeds to stop  430 . 
         [0053]    At step  430 , the data is read from main memory  150 . Method  400  proceeds to step  415 . 
         [0054]    When a store event is received at step  415 , method  400  proceeds to step  435 . 
         [0055]    At step  435 , method  400  writes the data affiliated with an address to L1 cache  320   a  and the data is called dirty data as it is not the same as the memory location at the same address in main memory  150 . 
         [0056]    At step  440 , a store entry is written to L1 pool  350   a  that can include but is not limited to the address location in main memory  150  to which the data is to be written, and a thread identity. A thread is a work item involved with the current instruction execution that includes the store event. The L1 pool  350   a  maintains a partial order among the store entry, any prior received store entries that may exist, and any release marker entries. 
         [0057]    In an example, two groups of prior store entries may exist in L1 pool  350   a  that are separated by a release marker described below. While no particular order within a group of prior store entries exists, the first group of prior store entries is ordered to be evicted before the release marker, and the second group is ordered to be evicted after the release marker. Thus there is partial order in the pool. 
         [0058]    The store entry is written in L1 pool  350   a  to be after the most-recent release marker. In the example, the store entry would be added to the second group of existing prior store entries in no particular order. 
         [0059]    Method  400  proceeds to step  415 . 
         [0060]    When a release synchronization event such as a release, a StRel, a fence, a kernel end, or a barrier operation is received at step  415 , method  400  proceeds to step  445 . A release marker is written to L1 pool  350   a  and ordered to be after any prior write entries in L1 pool  350   a . The entry of the release marker in L1 pool  350   a  triggers eviction of any prior write entries from the L1 pool  350   a . Thus, the release marker will be evicted after the prior entries in L1 pool  350   a  to ensure proper visibility of prior writes. 
         [0061]    At step  450 , if the release synchronization event is a StRel, method  400  proceeds to step  455 . At step  455 , method  400  writes data associated with the store event portion of the StRel to L1 cache  320   a . At step  460 , a corresponding store entry associated with the store event portion of the StRel is made to L1 pool  350   a  and ordered to be after the most-recent release marker. The store entry includes an address location in main memory  150  to which the data is to be written, and a thread identity, for example. The method proceeds to step  415 . 
         [0062]    At step  450 , if the release synchronization event is not a StRel, method  400  proceeds to step  415 . 
         [0063]      FIG. 5  illustrates a method of evicting entries, according to an embodiment. In one example, system  100  and system  300  may be used to demonstrate method  500 . It is to be appreciated that operations in method  500  may be performed in a different order than shown, and method  500  may not include all operations shown. For ease of discussion, and without limitation, method  500  will be described in terms of elements shown in  FIG. 1  and  FIG. 3 . 
         [0064]    Method  500  depicts the flow of operations when evictions from a pool occur. Evictions can occur, for example, when the number of entries in a pool exceeds a settable maximum value, or when a release marker is added to the pool and triggers prior write evictions. Method  500  includes operations at the L1 pool  350   a  and L2 pool  360 , for example. 
         [0065]    Method  500  begins at step  510  and proceeds to step  515 . 
         [0066]    At step  515 , method  500  proceeds to step  520  to depict L1 pool  350   a  eviction operations. 
         [0067]    At step  520 , method  500  determines whether L1 pool  350   a  evicts a store entry or a release marker entry. 
         [0068]    If a release marker is present in L1 pool  350   a  and no prior writes exist ahead of the release marker entry, method  500  determines to evict a release marker entry and proceeds to step  525 . 
         [0069]    At step  525 , the release marker is evicted from L1 pool  350   a  to L2 pool  360 . The release marker is ordered to be after any prior store entries in L2 pool  360 . The addition of the release marker triggers evictions of any prior store entries from L2 pool  360 , before the eviction of the release marker from L2 pool  360 . When a L2 cache  340  is not present, the release marker is evicted from L1 pool  350   a , and an acknowledgement is sent to the originating thread that the release is complete. 
         [0070]    Method  500  proceeds to step  545 . 
         [0071]    At step  520 , if a release marker is present in L1 pool  350   a , the prior store entries in L1 pool  350   a  ahead of the release marker are determined to be evicted to a L2 pool  360 , and corresponding data in L1 cache  320   a  are correspondingly evicted to L2 cache  340 . The prior store entries can be evicted in any order with respect to prior store entries. But, prior store entries and corresponding data in L1 cache  320   a  are evicted before the oldest release marker is evicted. Thus, the written data is guaranteed to be at the next level of the hierarchy by the time the release marker is evicted. 
         [0072]    At step  520 , if L1 pool  350   a  is determined to evict a store entry, method  500  proceeds to step  530 . 
         [0073]    At step  530 , method  500  determines if the corresponding data exists in the read-write L1 cache  320   a . If the corresponding data does not exist, method  500  proceeds to step  535 . At step  535 , a cache replacement policy as is well known in the art, may be enforced and previously evicted the data from L1 cache  320   a ; the store entry in L1 pool  350   a  is evicted to L2 pool  360 . In addition, a special case of a load event with a partial hit may also cause an early data eviction. Thus, embodiments support early evictions from the memory hierarchy. Method  500  proceeds to step  545 . 
         [0074]    At step  530 , if the corresponding data does exist in the L1 cache  320   a , method  500  proceeds to step  540 . 
         [0075]    At step  540 , the store entry in L1 pool  350   a  is evicted to L2 pool  360 . In addition, the corresponding data in L1 cache  320   a  is evicted to L2 cache  340 . 
         [0076]    When a L2 cache level is not present (not shown), embodiments include the following: evicting the prior store entry from the L1 pool  350   a ; evicting data, when present, from the L1 cache  320   a  associated with the evicted prior store entry to main memory; when the evicted prior store entry is associated with a StRel release synchronization event, signaling completion of release to the originating thread. 
         [0077]    When a L2 cache level is present and the L2 cache level is an ordering point (not shown), embodiments further include the following: evicting the prior store entry from L1 pool  350   a ; evicting data, when present, from the L1 cache  320   a  associated with the evicted prior store entry to the ordering point; when the evicted prior store entry is associated with a StRel release synchronization event, signaling completion of release to the originating thread. Thus, a StRel can complete at an ordering point other than main memory, and local synchronization is possible (e.g., receipt of a LdAcq can complete at L2 cache  340  without having to access main memory  150 ). Note that main memory can also be an ordering point and would be a global ordering point. 
         [0078]    Method  500  proceeds to step  545 . 
         [0079]    At step  515 , method  500  proceeds to step  545  to depict L2 pool  360  eviction operations. 
         [0080]    At step  545 , method  500  determines whether L2 pool  360  evicts a store entry or a release marker entry. Evictions may occur when a release marker entry is added to L2 pool  360  that triggers evictions, or when the number of L2 pool  360  entries exceeds a configurable threshold, for example. If L2 pool  360  evicts a release marker entry, method  500  proceeds to step  550 . 
         [0081]    At step  550 , the release marker is evicted from L2 pool  360 . In addition, method  500  transmits an acknowledgment to the originating thread or original requester, CU  310   a , that the release event is complete. This provides assurance that safe forward progress is possible beyond the release synchronization event. 
         [0082]    Note that for a StRel release synchronization event, CU  310   a  does not need to wait for the acknowledgement, but rather CU  310   a  can continue processing other memory events until executing the next LdAcq. But, for barrier and fence release synchronization events, CU  310   a  waits until a corresponding acknowledgement is received. Further, additional embodiments enable unsynchronized stores, if allowed by the memory model. These unsynchronized stores would not generate a store entry in L1 Pool  350   a , rather, corresponding data could be written to L1 cache  320   a . Thus, unsynchronized stores would not load pool components with unnecessary operations. 
         [0083]    The method proceeds to step  565 . 
         [0084]    At step  545 , if L2 pool  360  evicts a store entry, method  500  proceeds to step  555 . 
         [0085]    At step  555 , method  500  determines if the corresponding data exists in the read-write L2 cache  340 . If the corresponding data does not exist, (e.g., due to a cache replacement policy enforcement) the store entry is evicted from L2 pool  360  and method  500  proceeds to step  565 . 
         [0086]    At step  555 , if the corresponding data does exist, method  500  proceeds to step  560 . 
         [0087]    At step  560 , the store entry is evicted from L2 pool  360 . In addition, the corresponding data in L2 cache  340  is evicted to main memory  150 . Further, if the data was from a store event portion of a StRel, method  500  signals completion of release to the originating thread. 
         [0088]    Embodiments invalidate all data in L1 caches  320   a  and  320   b  associated with the corresponding address. The invalidations may be completed by broadcasting invalidation messages to all L1 read-write combining caches, L1 cache  320   a  and  320   b , to ensure release consistency. The invalidations are not critical to performance as the invalidations only delay release synchronization completions and are bound based on the number of entries in L2 pool  360  when a release synchronization event occurs. Note that write evictions and load requests do not stall waiting for invalidations. In addition, the data in L1  320   a  and L1  320   b  can be invalidated with a flash clear, e.g., when a LdAcq is received, all blocks in the cache are invalidated. The flash clear does not need to be associated with the corresponding address. 
         [0089]    Method  500  proceeds to step  565 . 
         [0090]    Logically, L1 pool  350   a , L1 pool  320   b , and L2 pool  360  may be implemented per thread identity or group of threads (e.g., wavefront identity). 
         [0091]      FIG. 6  illustrates a method of handing memory synchronization events, according to an embodiment. In one example, system  100  and system  300  may be used to demonstrate method  600 . It is to be appreciated that operations in method  600  may be performed in a different order than shown, and method  600  may not include all operations shown. For ease of discussion, and without limitation, method  600  will be described in terms of elements shown in  FIG. 1  and  FIG. 3 . 
         [0092]    The top portion of  FIG. 6  includes an execution order of two threads, one from compute unit CU  310   a  and another from CU  310   b , communicating a value in a simple system that contains one level of read-write combining cache including L1 cache  320   a  and L1 cache  320   b . The lower portion of  FIG. 6  illustrates method  600 . 
         [0093]    Method  600  begins at step  601  when CU  310   a  issues a store event, ST X (1), and writes data, 1, to a cache block in a cache line of L1 cache  320   a , associated with address X in main memory  150 . In addition, a store entry is added to L1 pool  350   a  that can include but is not limited to the address, X, associated with the data and a thread identity. If prior store entries are present, the new store entry is added to the group of prior store entries and no particular order is maintained. However, if a release marker is present, the new store entry would be ordered to be after the most-recent release marker. If prior store entries are present after the most-recent release marker, the new store entry would join that group and no particular order is maintained among the prior store entries. 
         [0094]    At step  602 , CU  310   a  issues a StRel synchronization event that triggers pool evictions through the memory hierarchy to main memory  150 . A release marker (Rel) entry is added to L1 pool  350   a , and is ordered to be after any prior store entries in L1 pool  350   a , to be evicted after the prior write entries in L1 pool  350   a  are evicted. 
         [0095]    At step  603 , L1 pool  350   a  begins evicting prior write entries ordered before the release marker (Rel). The entry associated with address X is evicted from L1 pool  350   a , and the corresponding data in the cache in L1 cache  320   a  associated with address X is evicted to main memory  150 . 
         [0096]    At step  604 , the prior write entries have been evicted from L1 pool  350   a , the release marker (Rel) is evicted from L1 pool  350   a  and an acknowledgement is sent to CU  310   a  to signal that the release event portion of the StRel is complete. 
         [0097]    At step  605 , CU  310   a  issues the store event portion of the StRel synchronization event and writes data, 2, to a cache in L1 cache  320   a  associated with address A. In addition, a L1 pool  350   a  store entry is added that may include but is not limited to the address, A, associated with the cached data, and a thread identity. In an embodiment, an entry of the store event portion of a StRel to L1 pool  350   a  will trigger L1 pool  350   a  evictions. 
         [0098]    At step  606 , the prior write associated with address A is eventually evicted from L1 pool  350   a  (e.g., if the number of pool entries exceed a settable maximum value (not shown) or another release synchronization event occurs (not shown)). When the entry associated with address A is evicted from L1 pool  350   a , the data associated with address A in L1 cache  320   a  is evicted to main memory  150  and signals completion of the release event portion of the StRel synchronization event to other threads in the system. The data at address A in main memory  150  is now visible to all threads in the system. 
         [0099]    At step  607 , CU  310   b  issues a load acquire LdAcq synchronization event to complete the synchronization. Method  600  searches L1 cache  320   b , to read the data at address A, and when the address A is not found (a miss), method  600  searches main memory  150 . When the address A and corresponding data, 2, are found and read from main memory  150  (a hit), the data is copied (i.e., loaded) to L1 cache  320   b  and is transmitted to (i.e., read by) CU  310   b.    
         [0100]    At step  608 , CU  310   b  issues a load event and searches L1 cache  320   b , to read the data at address X, and when the address X is not found (a miss), method  600  searches main memory  150 . When the address X and corresponding data, 1, are found and read from main memory  150  (a hit), the data is copied to L1 cache  320   b  and is read by CU  310   b.    
         [0101]    In an embodiment, a pool can be implemented with a synchronization First In First Out (S-FIFO) that maintains complete order for prior writes as well as a release synchronization event. For example, at step  601 , when a store event occurs, an entry would be made to the tail of an S-FIFO that can include but is not limited to the address, X, associated with the data and a thread identity. If prior writes are present, the new L1 pool  350   a  store entry would be added to the tail of the queue and complete order is maintained among the prior writes as well as the release synchronization events. 
         [0102]    When the S-FIFO is filled, method  600  would begin to dequeue the S-FIFO. This is similar to a pool component exceeding a settable maximum value. The entry at the top of the S-FIFO and the corresponding cache in the L1 cache  320   a  would be evicted to the corresponding next-level S-FIFO and next-level cache, e.g. L2 cache  340  if present. If the next-level cache is not present, the entry at the top of the S-FIFO is removed (e.g., popped) and the corresponding cache in L1 cache  320   a  is written to main memory  150 . 
         [0103]    Logically there can be a S-FIFO per thread, but physically the S-FIFO can be implemented as a single FIFO, or as many FIFOs that are partitioned based on thread identity or a group of thread identities. Thus the physical implementation can balance space versus performance concerns. 
         [0104]      FIG. 7  illustrates a method of evicting entries, according to an embodiment. In one example, system  100  and system  300  may be used to demonstrate method  700 . It is to be appreciated that operations in method  700  may be performed in a different order than shown, and method  700  may not include all operations shown. For ease of discussion, and without limitation, method  700  will be described in terms of elements shown in  FIG. 1  and  FIG. 3 . 
         [0105]    Method  700  depicts the flow of operations when evictions from a queue such as a First In First Out (FIFO) instead of a pool occur. Evictions can occur, for example, when the number of entries in the FIFO exceeds the size of the FIFO and the entry at the head of the FIFO is popped off the FIFO, or when a release marker is added to the tail of the FIFO and triggers prior write evictions. Method  700  includes operations at a L1 FIFO and L2 FIFO (not shown), for example. 
         [0106]    Method  700  begins at step  710  and proceeds to step  715 . 
         [0107]    At step  715 , method  700  proceeds to step  720  to depict L1 FIFO eviction operations. 
         [0108]    At step  720 , method  700  determines whether L1 FIFO evicts a store entry or a release marker entry. 
         [0109]    When a release marker is present in L1 FIFO and no prior writes exist ahead of the release marker entry, method  700  evicts a release marker entry and proceeds to step  725 . 
         [0110]    At step  725 , the release marker is evicted from the head of L1 FIFO to the tail of L2 FIFO. The addition of the release marker triggers evictions of any prior store entries from L2 FIFO until the release marker itself is evicted from the head of L2 FIFO. When a L2 cache  340  (and hence L2 FIFO) is not present, the release marker is evicted from L1 FIFO, and an acknowledgement is sent to the originating thread that the release is complete. 
         [0111]    Method  700  proceeds to step  745 . 
         [0112]    At step  720 , if a release marker is present in L1 FIFO, the prior store entries in L1 FIFO ahead of the release marker are evicted in turn, to a L2 FIFO, and corresponding data in L1 cache  320   a  are correspondingly evicted to L2 cache  340 . The prior store entries are evicted in the order of placement in L1 FIFO. Thus, the written data is guaranteed to be at the next level of the hierarchy by the time the release marker is evicted. 
         [0113]    At step  720 , if L1 FIFO evicts a store entry, method  700  proceeds to step  730 . 
         [0114]    At step  730 , method  700  determines if the corresponding data exists in the read-write L1 cache  320   a . When the corresponding data does not exist, method  700  proceeds to step  735 . At step  735 , a cache replacement policy as is well known in the art, may be enforced and previously evicted the data from L1 cache  320   a ; the store entry at the head of L1 FIFO is evicted to the tail of L2 FIFO. Thus, embodiments support early evictions from the memory hierarchy. 
         [0115]    Method  700  proceeds to step  745 . 
         [0116]    At step  730 , if the corresponding data does exist in the L1 cache  320   a , method  700  proceeds to step  740 . 
         [0117]    At step  740 , the store entry at the head of L1 FIFO is evicted to the tail of L2 FIFO. In addition, the corresponding data in L1 cache  320   a  is evicted to L2 cache  340 . 
         [0118]    When a L2 cache level is not present (not shown), embodiments include the following: evicting the prior store entry from the head of L1 FIFO; evicting data, when present, from the L1 cache  320   a  associated with the evicted prior store entry to main memory; when the evicted prior store entry is associated with a StRel release synchronization event, signaling completion of release to the originating. 
         [0119]    When a L2 cache level is present and the L2 cache level is an ordering point (not shown), embodiments further include the following: evicting the prior store entry from L1 FIFO; evicting data, when present, from the L1 cache  320   a  associated with the evicted prior store entry to the ordering point; when the evicted prior store entry is associated with a StRel release synchronization event, signaling completion of release to the originating thread. Thus, a StRel can complete at an ordering point other than main memory, and local synchronization is possible (e.g., receipt of a LdAcq can complete at L2 cache  340  without having to access main memory  150 ). Note that main memory can also be an ordering point and would be a global ordering point. 
         [0120]    Method  700  proceeds to step  745 . 
         [0121]    At step  715 , method  700  proceeds to step  745  to depict L2 FIFO eviction operations. 
         [0122]    At step  745 , method  700  determines whether L2 FIFO evicts a store entry or a release marker entry. Evictions may occur when a release marker entry is added to the tail of L2 FIFO that triggers evictions, or when the number of L2 FIFO entries exceeds a configurable threshold, for example. If L2 FIFO determines to evict a release marker entry, method  700  proceeds to step  750 . 
         [0123]    At step  750 , the release marker is evicted from L2 FIFO. In addition, method  700  transmits an acknowledgment to the originating thread or original requester, CU  310   a , that the release event is complete. This provides assurance that safe forward progress is possible beyond the release synchronization event. 
         [0124]    Note that for a StRel release synchronization event, CU  310   a  does not need to wait for the acknowledgement, but rather CU  310   a  can continue processing other memory events until executing the next LdAcq. But, for barrier and fence release synchronization events, CU  310   a  waits until a corresponding acknowledgement is received. Further, additional embodiments enable unsynchronized stores, if allowed by the memory model. These unsynchronized stores would not generate a store entry in L1 FIFO, rather, corresponding data could be written to L1 cache  320   a . Thus, unsynchronized stores would not load pool components with unnecessary operations. 
         [0125]    The method proceeds to step  765 . 
         [0126]    At step  745 , if L2 FIFO determines to evict a store entry, method  700  proceeds to step  755 . 
         [0127]    At step  755 , method  700  determines if the corresponding data exists in the read-write L2 cache  340 . If the corresponding data does not exist, (e.g., due to a cache replacement policy enforcement) the store entry is evicted from the head of L2 FIFO and method  700  proceeds to step  765 . 
         [0128]    At step  755 , when the corresponding data does exist, method  700  proceeds to step  760 . 
         [0129]    At step  760 , the store entry is evicted from the head of L2 FIFO. In addition, the corresponding data in L2 cache  340  is evicted to main memory  150 . Further, if the data was from a store event portion of a StRel, method  700  signals completion of release to the originating thread. 
         [0130]    Embodiments invalidate all data in L1 caches  320   a  and  320   b  associated with the corresponding address. The invalidations may be completed by broadcasting invalidation messages to all L1 read-write combining caches, L1 cache  320   a  and  320   b , to ensure release consistency. The invalidations are not critical to performance as the invalidations only delay release synchronization completions and are bound based on the number of entries in L2 FIFO when a release synchronization event occurs. Note that write evictions and load requests do not stall waiting for invalidations. In addition, the data in L1  320   a  and L1  320   b  can be invalidated with a flash clear, e.g., when a LdAcq is received, all blocks in the cache are invalidated. The flash clear does not need to be associated with the corresponding address. 
         [0131]    Method  700  proceeds to step  765 . 
         [0132]    Logically, L1 FIFO and L2 FIFO may be implemented per thread identity or group of threads (e.g., wavefront identity). 
         [0133]    In another embodiment, a pool of entries can be implemented with a Bloom-filter with a set of entries. A Bloom filter is an inexact representation of a set of elements. Bloom filters are implemented with an array of bits, and that array is indexed through two or more hash functions. To insert an element in the bloom filter, the element is hashed and all corresponding bits are set. To test membership, the element is hashed and all corresponding bits are checked. If all bits are set (e.g., to “1”), the element may be in the set. If any one of the bits is cleared (e.g., to “0”), the element is not in the set. Unlike a mathematical set, Bloom filters have no remove function (though a variant called a counting bloom filter does). A signature is a representation of a set of elements. It can be implemented with a bloom filter, an exact list (and/or array), or a FIFO, for example. 
         [0134]    In summary, a prior store event is guaranteed to be ordered in the memory hierarchy whenever the store event has been evicted from a pool, dequeued from a FIFO, or tested for membership in a set using a Bloom-filter. 
         [0135]    Various aspects of the disclosure can be implemented by software, firmware, hardware, or a combination thereof.  FIG. 8  illustrates an example computer system  800  in which some embodiments, or portions thereof, can be implemented as computer-readable code. For example, the methods  400 - 700 , of  FIGS. 4 through 7  can be implemented in system  800 . Various embodiments are described in terms of the example computer system  800 . After reading this description, it will become apparent to a person skilled in the relevant art how to implement the embodiments using other computer systems and/or computer architectures. 
         [0136]    Computer system  800  includes one or more processors, such as processor  804 . Processor  804  can be a special purpose or a general purpose processor. Examples of processor  804  are CPU  110  and GPU  130  of  FIG. 1 , or a GPGPU, or APU as described earlier. Processor  804  is connected to a communication infrastructure  806  (for example, a bus or network) such as bus  140  of  FIG. 1 . 
         [0137]    Computer system  800  also includes a main memory  808 , such as random access memory (RAM) such as main memory  150  of  FIG. 1 , and may also include a secondary memory  810 . Secondary memory  810  may include, for example, a hard disk drive  812 , a removable storage drive  814 , and/or a memory stick. Removable storage drive  814  may comprise a floppy disk drive, a magnetic tape drive, an optical disk drive, a flash memory, or the like. The removable storage drive  814  reads from and/or writes to a removable storage unit  818  in a well-known manner. Removable storage unit  818  may comprise a floppy disk, magnetic tape, optical disk, etc. that is read by and written to by removable storage drive  814 . As will be appreciated by persons skilled in the relevant art(s), removable storage unit  818  includes a computer usable storage medium having stored therein computer software and/or data. 
         [0138]    In alternative implementations, secondary memory  810  may include other similar means for allowing computer programs or other instructions to be loaded into computer system  800 . Such means may include, for example, a removable storage unit  822  and an interface  820 . Examples of such means may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units  822  and interfaces  820  that allow software and data to be transferred from the removable storage unit  822  to computer system  800 . 
         [0139]    Computer system  800  may also include a communications interface  824 . Communications interface  824  allows software and data to be transferred between computer system  800  and external devices. Communications interface  824  may include a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, or the like. Software and data transferred via communications interface  824  are in the form of signals that may be electronic, electromagnetic, optical, or other signals capable of being received by communications interface  824 . These signals are provided to communications interface  824  via a communications path  826 . Communications path  826  carries signals and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link or other communications channels. 
         [0140]    In this document, the terms “computer program medium” and “computer usable medium” are used to generally refer to media such as removable storage unit  818 , removable storage unit  822 , and a hard disk installed in hard disk drive  812 . Signals carried over communications path  826  can also embody the logic described herein. Computer program medium and computer usable medium can also refer to memories, such as main memory  808  and secondary memory  810 , which can be memory semiconductors (e.g. DRAMs, etc.). These computer program products are means for providing software to computer system  800 . 
         [0141]    Computer programs (also called computer control logic) are stored in main memory  808  and/or secondary memory  810 . Computer programs may also be received via communications interface  824 . Such computer programs, when executed, enable computer system  800  to implement the embodiments as discussed herein. In particular, the computer programs, when executed, enable processor  804  to implement the disclosed processes, such as the steps in the methods  400 - 700  of  FIGS. 4-7  as discussed above. Accordingly, such computer programs represent controllers of the computer system  800 . Where the embodiments are implemented using software, the software may be stored in a computer program product and loaded into computer system  800  using removable storage drive  814 , interface  820 , hard drive  812  or communications interface  827 . This can be accomplished, for example, through the use of general-programming languages (such as C or C++). The computer program code can be disposed in any known computer-readable medium including semiconductor, magnetic disk, or optical disk (such as, CD-ROM, DVD-ROM). As such, the code can be transmitted over communication networks including the Internet and internets. It is understood that the functions accomplished and/or structure provided by the systems and techniques described above can be represented in a core (such as a processing-unit core) that is embodied in program code and may be transformed to hardware as part of the production of integrated circuits. This can be accomplished, for example, through the use of hardware-description languages (HDL) including Verilog HDL, VHDL, Altera HDL (AHDL) and so on, or other available programming and/or schematic-capture tools (such as, circuit-capture tools). 
         [0142]    Embodiments are also directed to computer program products comprising software stored on any computer useable medium. Such software, when executed in one or more data processing device, causes a data processing device(s) to operate as described herein. Embodiments employ any computer useable or readable medium, known now or in the future. Examples of computer useable mediums include, but are not limited to, primary storage devices (e.g., any type of random access memory), secondary storage devices (e.g., hard drives, floppy disks, CD ROMS, ZIP disks, tapes, magnetic storage devices, optical storage devices, MEMS, nanotechnological storage device, etc.), and communication mediums (e.g., wired and wireless communications networks, local area networks, wide area networks, intranets, etc.). 
         [0143]    It is to be appreciated that the Detailed Description section, and not the Summary and Abstract sections, is intended to be used to interpret the claims. The Summary and Abstract sections may set forth one or more but not all exemplary embodiments as contemplated by the inventor(s), and thus, are not intended to limit the disclosure and the appended claims in any way. 
         [0144]    The disclosure has been described above with the aid of functional building blocks illustrating the implementation of specified functions and relationships thereof. The boundaries of these functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternate boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. 
         [0145]    The foregoing description of the specific embodiments will so fully reveal the general nature of the embodiments that others can, by applying knowledge within the skill of the art, readily modify and/or adapt for various applications such specific embodiments, without undue experimentation, without departing from the general concept of the present disclosure. Therefore, such adaptations and modifications are intended to be within the meaning and range of equivalents of the disclosed embodiments, based on the teaching and guidance presented herein. It is to be understood that the phraseology or terminology herein is for the purpose of description and not of limitation, such that the terminology or phraseology of the present specification is to be interpreted by the skilled artisan in light of the teachings and guidance. 
         [0146]    The breadth and scope of the present disclosure should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.