Patent Description:
An "atomic memory access" performed by a processor-based device refers to a memory access operation (e.g., a memory read operation or a memory write operation, as non-limiting examples) in which all bytes of data being accessed are simultaneously observable. Atomic memory accesses ensure that, even if multiple agents attempt conflicting operations on a same memory location, the resulting value stored at that memory location will be either the entire previous value or the entire final value, and never a combination of the two. Depending on what memory model is supported by a processor-based device's instruction set architecture (ISA), the processor-based device may expect or require that some or all types of memory access operations be performed atomically. For instance, a system memory of a processor-based device may be organized into subdivisions referred to as "coherence granules" representing the aligned size, in bytes, at which the processor-based device manages cache coherency, and the processor-based device may require that all memory access operations within a single coherence granule be executed atomically.

However, issues may arise when an atomic memory access crosses a boundary between two coherence granules. Consider a scenario in which bytes within a system memory at memory addresses <NUM> to <NUM> are located within a first coherence granule, while bytes at memory addresses <NUM> to <NUM> are located within a second coherence granule. A memory store operation writing four (<NUM>) bytes of data starting at memory address <NUM> would thus need to write the first two (<NUM>) bytes to the first coherence granule and the second two (<NUM>) bytes to the second coherence granule. To perform the memory store operation atomically, both coherence granules would need to be acquired in an exclusive state at the same time. Once a processing element (PE) (e.g., a processor or processor core) obtains exclusive access to both coherence granules, the memory store operation can be completed, and another PE may then access one or both of the coherence granules.

Assume, though, that two PEs each attempts to execute a memory store operation atomically on the same two coherence granules at approximately the same time. The first PE may obtain the first coherence granule in an exclusive state, and then deny access to the first coherence granule by other PEs until the first PE can obtain the second coherence granule in an exclusive state. At the same time, the second PE may obtain the second coherence granule in an exclusive state, and deny access to the first coherence granule by other PEs until the second PE can obtain the first coherence granule in an exclusive state. This gives rise to a deadlock, with each PE refusing to surrender its coherence granule until the other PE surrenders its coherence granule. One technique for avoiding such a deadlock is to disallow the PEs from holding its respective coherence granule in the manner described above, and require each PE to wait until it acquires exclusive access to both coherence granules before completing its memory store operation. However, this technique may lead to a livelock, where each PE repeatedly gives up its coherence granule to the other PE upon request.

One conventional technique for atomic memory accesses across coherence granule boundaries involves the processor-based device detecting that the memory access operation crosses a coherence granule boundary, and, to handle the situation, the processor "locks the bus," or restricts access to an interconnect bus to the PE seeking to perform the memory access operation. Once that PE obtains exclusive access to both coherence granules and completes the memory access operation atomically, the interconnect bus is then unlocked. Locking the bus, though, may incur significant performance penalties due to the interconnect bus only being accessible by one PE while locked. Another conventional technique involves the underlying ISA of the processor-based device not guaranteeing that a memory access operation will be performed atomically if it crosses a coherence granule boundary. In this case, software must detect that the memory access operation crosses a coherence granule boundary, and attempt to handle the memory access operation by quiescing all other executing threads in the PE to perform a form of software-based bus lock. However, such a software-based approach may be more complex and less reliable than a hardware-based approach.

Accordingly, a more efficient mechanism for enabling atomic memory accesses across coherence granule boundaries is desirable.

<CIT> describes how methods and systems for mutual exclusion in a non-coherent memory hierarchy may include a non-coherent memory system with a shared system memory. Multiple processors and a memory connect interface may be configured to provide an interface for the processors to the shared memory. The memory connect interface may include an arbiter for atomic memory operations from the processors. In response to an atomic memory operation, the arbiter may perform an atomic memory operation procedure including setting a busy flag for an address of the atomic memory operation, blocking subsequent memory operations from any of the processors to the address while the busy flag is set, issuing the atomic memory operation to the shared memory, and in response to an acknowledgement of the atomic memory operation from the shared memory, clearing the busy flag and allowing subsequent memory operations from the processors for the address to proceed to the shared memory.

<CIT> describes a system that facilitates efficient transactional execution. During operation, the system executes a starvation-avoiding transaction for a thread, wherein executing the starvation-avoiding transaction involves: (<NUM>) placing load-marks on cache lines which are loaded during the starvation-avoiding transaction; (<NUM>) placing store-marks on cache lines which are stored to during the starvation-avoiding transaction; and (<NUM>) writing a timestamp value into metadata for load-marked and store-marked cache lines. While the thread is executing the starvation-avoiding transaction, the system prevents other threads from executing another starvation-avoiding transaction. Whereby the load-marks and store-marks prevent interfering accesses from other threads to the cache lines during the starvation-avoiding transaction.

Exemplary embodiments disclosed herein include enabling atomic memory accesses across coherence granule boundaries in processor-based devices. In this regard, in one exemplary embodiment, a processor-based device, comprising a plurality of processing elements (PEs), further includes a special-purpose central ordering point (SPCOP) that is configured to distribute a coherence granule ("cogran") pair atomic access (CPAA) token. To perform an atomic memory access on a pair of coherence granules, a PE must hold a CPAA token for a memory-aligned address block containing at least one of the pair of coherence granules before the PE can demand to obtain the pair of coherence granules in an exclusive state. Each of the coherence granules may be considered "even" or "odd" based on, e.g., the value of the lowest-order bit of the memory address used to select the coherence granule. Thus, in embodiments described herein in which each address block contains exactly one (<NUM>) coherence granule, the SPCOP may associate CPAA tokens with address blocks that each contain only an "even" coherence granule (or only an "odd" coherence granule). Because CPAA tokens are always associated with address blocks containing "even" coherence granules (or "odd" coherence granules, depending on implementation), and the SPCOP only allows one CPAA token to be active at a time for a given address block, deadlocks and livelocks between multiple PEs seeking to access the same coherence granules for atomic memory accesses can be avoided. Once a PE obtains the CPAA token for an address block containing a first coherence granule of a pair of coherence granules, the PE obtains the first coherence granule of the pair of coherence granules in an exclusive state, then obtains the second coherence granule of the pair of coherence granules in an exclusive state. The PE then completes the atomic memory access request, and returns the CPAA token to the SPCOP. Some embodiments may further provide that the SPCOP comprises a CPAA access queue for tracking requests to access coherence granules under protection by a CPAA token, while the SPCOP in some embodiments may comprise a CPAA reservation queue for tracking multiple requests for CPAA tokens for a given coherence granule.

In another exemplary embodiment, a processor-based device is provided. The processor-based device comprises a system memory comprising a plurality of address blocks and a plurality of coherence granules, and a SPCOP comprising an SPCOP logic circuit. The processor-based device further comprises a plurality of PEs each comprising a memory access logic circuit. The memory access logic circuit of a first PE of the plurality of PEs is configured to detect an atomic memory access request that spans a boundary between a first coherence granule and a second coherence granule of the system memory. The memory access logic circuit of the first PE is further configured to send a request for a CPAA token for the address block containing the first coherence granule to the SPCOP. The memory access logic circuit of the first PE is also configured to receive, from the SPCOP, the CPAA token for the address block containing the first coherence granule, the CPAA token indicating that the first PE of the plurality of PEs is allowed to protect the address block containing the first coherence granule. The memory access logic circuit of the first PE is additionally configured to obtain the first coherence granule and the second coherence granule in an exclusive state. The memory access logic circuit of the first PE is further configured to complete the atomic memory access request. The memory access logic circuit of the first PE is also configured to send a request to return the CPAA token for the address block containing the first coherence granule to the SPCOP.

In another exemplary embodiment, a method for enabling atomic memory accesses that cross coherence granule boundaries is provided. The method comprises detecting, by a first PE of a plurality of PEs of a processor-based device, an atomic memory access request that spans a boundary between a first coherence granule and a second coherence granule of a system memory of the processor-based device. The method further comprises sending, by the first PE, a first request for a CPAA token for the address block containing the first coherence granule to a SPCOP. The method also comprises receiving, by the first PE from the SPCOP, the CPAA token for the address block containing the first coherence granule, the CPAA token indicating that the first PE of the plurality of PEs is allowed to protect the address block containing the first coherence granule. The method additionally comprises obtaining, by the first PE, the first coherence granule and the second coherence granule in an exclusive state. The method further comprises completing, by the first PE, the atomic memory access request. The method also comprises sending, by the first PE, a request to return the CPAA token for the address block containing the first coherence granule to the SPCOP.

In another exemplary embodiment, a non-transitory computer-readable medium is provided. The computer-readable medium stores thereon computer-executable instructions which, when executed by a processor, cause the processor to detect an atomic memory access request that spans a boundary between a first coherence granule and a second coherence granule of a system memory. The computer-executable instructions further cause the processor to send a request for a CPAA token for the address block containing the first coherence granule to a SPCOP of the processor. The computer-executable instructions also cause the processor to receive, from the SPCOP, the CPAA token for the address block containing the first coherence granule, the CPAA token indicating that the processor is allowed to protect the address block containing the first coherence granule. The computer-executable instructions additionally cause the processor to obtain the first coherence granule and the second coherence granule in an exclusive state. The computer-executable instructions further cause the processor to complete the atomic memory access request. The computer-executable instructions also cause the processor to send a request to return the CPAA token for the address block containing the first coherence granule to the SPCOP.

Those skilled in the art will appreciate the scope of the present disclosure and realize additional embodiments thereof after reading the following detailed description of the preferred embodiments in association with the accompanying drawing figures.

The accompanying drawing figures incorporated in and forming a part of this specification illustrate several embodiments of the disclosure, and together with the description serve to explain the principles of the disclosure.

In this regard, <FIG> illustrates an exemplary processor-based device <NUM> that provides a plurality of processing elements (PEs) <NUM>(<NUM>)-<NUM>(P) for processing executable instructions. Each of the PEs <NUM>(<NUM>)-<NUM>(P) may comprise a central processing unit (CPU) having one or more processor cores, or may comprise an individual processor core comprising a logical execution unit and associated caches and functional units. In the example of <FIG>, each of the PEs <NUM>(<NUM>)-<NUM>(P) includes a corresponding execution pipeline <NUM>(<NUM>)-<NUM>(P) that is configured to perform out-of-order execution of an instruction stream comprising computer-executable instructions. As non-limiting examples, the execution pipelines <NUM>(<NUM>)-<NUM>(P) each may include a fetch stage for retrieving instructions for execution, a decode stage for translating fetched instructions into control signals for instruction execution, a rename stage for allocating physical register file (PRF) registers, a dispatch stage for issuing instructions for execution, an execute stage for sending instructions and operands to execution units, and/or a commit stage for irrevocably updating the architectural state of the corresponding PE <NUM>(<NUM>)-<NUM>(P) based on the results of instruction execution.

The PEs <NUM>(<NUM>)-<NUM>(P) of the processor-based device <NUM> of <FIG> are interconnected to each other and to a system memory <NUM> by an interconnect bus <NUM>. As seen in <FIG>, the system memory <NUM> is subdivided into multiple coherence granules <NUM>(<NUM>)-<NUM>(C), each representing the smallest unit of memory (e.g., <NUM> bytes, as a non-limiting example) for which memory coherence is maintained by the processor-based device <NUM>. The system memory <NUM> is also divided into address blocks <NUM>(<NUM>)-<NUM>(A). In the example of <FIG>, the address blocks <NUM>(<NUM>)-<NUM>(A) each contain a corresponding one of the coherence granules <NUM>(<NUM>)-<NUM>(C). The processor-based device <NUM> according to some embodiments may further provide a snoop filter <NUM> to monitor traffic on the interconnect bus <NUM> to track coherence states of cache lines (not shown) of the PEs <NUM>(<NUM>)-<NUM>(P). The processor-based device <NUM> in some embodiments may also provide a central ordering point <NUM> for ordering, e.g., cache misses and invalidation requests.

The processor-based device <NUM> of <FIG> and the constituent elements thereof may encompass any one of known digital logic elements, semiconductor circuits, processing cores, and/or memory structures, among other elements, or combinations thereof. Embodiments described herein are not restricted to any particular arrangement of elements, and the disclosed techniques may be easily extended to various structures and layouts on semiconductor sockets or packages. It is to be understood that some embodiments of the processor-based device <NUM> may include elements in addition to those illustrated in <FIG>. For example, each of the PEs <NUM>(<NUM>)-<NUM>(P) may further include one or more functional units, instruction caches, unified caches, memory controllers, interconnect buses, and/or additional memory devices, caches, and/or controller circuits, which are omitted from <FIG> for the sake of clarity. Additionally, in some embodiments, the PEs <NUM>(<NUM>)-<NUM>(P) may all be co-located on a single die <NUM>(<NUM>) of a plurality of dies <NUM>(<NUM>)-<NUM>(D) of the processor-based device <NUM>. In such embodiments, each die <NUM>(<NUM>)-<NUM>(D) includes a plurality of PEs corresponding to the PEs <NUM>(<NUM>)-<NUM>(P) of the die <NUM>(<NUM>).

As noted above, the PEs <NUM>(<NUM>)-<NUM>(P) may face issues when attempting to perform an atomic memory access that crosses a boundary between two of the coherence granules <NUM>(<NUM>)-<NUM>(C). For example, assume that the PE <NUM>(<NUM>) and the PE <NUM>(P) each attempt to perform an atomic memory store operation that spans the coherence granule <NUM>(<NUM>) and the coherence granule <NUM>(<NUM>). The PE <NUM>(<NUM>) may obtain the coherence granule <NUM>(<NUM>) in an exclusive state, and then deny access to the coherence granule <NUM>(<NUM>) by the PE <NUM>(P) until the PE <NUM>(<NUM>) can obtain the coherence granule <NUM>(<NUM>) in an exclusive state. At the same time, the PE <NUM>(P) may obtain the coherence granule <NUM>(<NUM>) in an exclusive state, and deny access to the coherence granule <NUM>(<NUM>) by the PE <NUM>(<NUM>) until the PE <NUM>(P) can obtain the coherence granule <NUM>(<NUM>) in an exclusive state. This results in a deadlock, with each PE <NUM>(<NUM>), <NUM>(P) refusing to surrender its coherence granule <NUM>(<NUM>), <NUM>(<NUM>). A livelock may also arise in similar circumstances if the PEs <NUM>(<NUM>) and <NUM>(P) continually exchange holds on the coherence granules <NUM>(<NUM>) and <NUM>(<NUM>).

In this regard, the processor-based device <NUM> of <FIG> is configured to enable atomic memory accesses across coherence granule boundaries. In particular, embodiments described herein are directed to memory access operations that require exclusive access to two (<NUM>) of the coherence granules <NUM>(<NUM>)-<NUM>(C) (e.g., coherence granules <NUM>(<NUM>) and <NUM>(<NUM>), as non-limiting examples). It is to be understood that memory access operations may store and load data using virtual addresses, and as a result a memory access operation that crosses a coherence granule boundary may cross a physical page boundary (i.e., the memory access operation may begin within a last coherence granule of one physical page and end within a first coherence granule of another physical page). Additionally, although the virtual address may be contiguous (i.e., the memory access operation begins on one coherence granule and ends on the next sequential coherence granule), the corresponding physical addresses might not be contiguous.

Each of the PEs <NUM>(<NUM>)-<NUM>(P) provides a corresponding memory access logic circuit <NUM>(<NUM>)-<NUM>(P) that works in concert with a special-purpose central ordering point (SPCOP) <NUM> to enable atomic memory accesses across coherence granule boundaries. Each of the memory access logic circuits <NUM>(<NUM>)-<NUM>(P) may exist as a discrete element of the corresponding PE <NUM>(<NUM>)-<NUM>(P), or may be integrated into one or more elements of the corresponding PE <NUM>(<NUM>)-<NUM>(P), such as the execution pipelines <NUM>(<NUM>)-<NUM>(P). In exemplary operation, and using the PE <NUM>(<NUM>) as an example, the memory access logic circuit <NUM>(<NUM>) is configured to first detect an atomic memory access request <NUM> that spans a boundary between the coherence granule <NUM>(<NUM>) and the coherence granule <NUM>(<NUM>). The memory access logic circuit <NUM>(<NUM>) of the PE <NUM>(<NUM>) is configured to require a CPAA token for the address block <NUM>(<NUM>) containing the first coherence granule <NUM>(<NUM>) of the pair of coherence granules <NUM>(<NUM>), <NUM>(<NUM>) on which the atomic memory access is to be performed before the PE <NUM>(<NUM>) can obtain exclusive access to the pair of coherence granules <NUM>(<NUM>), <NUM>(<NUM>). Thus, the memory access logic circuit <NUM>(<NUM>) next requests a CPAA token from the SPCOP <NUM>. The SPCOP <NUM> is configured to allow only one CPAA token to be active at a time for a given non-overlapping address block <NUM>(<NUM>)-<NUM>(A), but in some embodiments may allow multiple CPAA tokens to be active for different address blocks <NUM>(<NUM>)-<NUM>(A) at the same time.

In the example of <FIG>, the size of the address blocks <NUM>(<NUM>)-<NUM>(A) equals the size of the coherence granules <NUM>(<NUM>)-<NUM>(C), such that each of the pair of coherence granules <NUM>(<NUM>), <NUM>(<NUM>) is located within a different address block <NUM>(<NUM>), <NUM>(<NUM>). Accordingly, the CPAA token is always associated with a particular one of any given pair of address blocks <NUM>(<NUM>), <NUM>(<NUM>). As non-limiting examples, each of the coherence granules <NUM>(<NUM>)-<NUM>(C) may be determined to be an "even" or an "odd" coherence granule <NUM>(<NUM>)-<NUM>(C) based on, e.g., the value of the lowest order bit in the memory address of the coherence granule <NUM>(<NUM>)-<NUM>(C). The memory access logic circuit <NUM>(<NUM>) of the PE <NUM>(<NUM>) thus may be configured to always deterministically select the address block <NUM>(<NUM>) containing the "even" coherence granule <NUM>(<NUM>) (or the address block <NUM>(<NUM>) containing the "odd" coherence granule <NUM>(<NUM>), depending on implementation) as the address block for which a CPAA token is requested.

It is to be understood that in some embodiments, each of the PEs <NUM>(<NUM>)-<NUM>(P) may provide a single SPCOP, or may provide multiple SPCOPs that are each associated with a specified range of the entire address space of the system memory <NUM>. Upon receiving the request for the CPAA token, the SPCOP <NUM> in some embodiments records the memory address used to select the first coherence granule (e.g., the coherence granule <NUM>(<NUM>) in this example) and an identifier of the PE <NUM>(<NUM>) that requested the CPAA token, and then distributes the CPAA token to the PE <NUM>(<NUM>).

Once the PE <NUM>(<NUM>) has obtained a CPAA token, it can then demand to obtain the first coherence granule <NUM>(<NUM>) in an exclusive state. Upon acquiring the first coherence granule <NUM>(<NUM>) in an exclusive state, a "CPAA protection window" is established for the first coherence granule <NUM>(<NUM>). The CPAA protection window allows the PE <NUM>(<NUM>) to protect its hold of the first coherence granule <NUM>(<NUM>) until it makes progress on obtaining the second coherence granule <NUM>(<NUM>). After the PE <NUM>(<NUM>) obtains the second coherence granule <NUM>(<NUM>) in an exclusive state, the PE <NUM>(<NUM>) completes the atomic memory access request <NUM>, and then returns the CPAA token for the address block <NUM>(<NUM>) containing the first coherence granule <NUM>(<NUM>) to the SPCOP <NUM>. Because the PE <NUM>(<NUM>) must hold the CPAA token for the address block containing the first coherence granule <NUM>(<NUM>) to protect the address block containing the first coherence granule <NUM>(<NUM>) until it obtains the second coherence granule <NUM>(<NUM>) in an exclusive state, a deadlock can be avoided. Similarly, because the PE <NUM>(<NUM>), once it obtains the CPAA token for the address block containing the first coherence granule <NUM>(<NUM>), is permitted to protect the address block containing the first coherence granule <NUM>(<NUM>) until it obtains the second coherence granule <NUM>(<NUM>) in an exclusive state, a livelock can also be avoided.

In some embodiments, when the PE <NUM>(<NUM>) has a CPAA protection window open for the first coherence granule <NUM>(<NUM>) and receives a snoop request (e.g., from the PE <NUM>(P) of <FIG>) indicating an attempt to access the first coherence granule <NUM>(<NUM>), the memory access logic circuit <NUM>(<NUM>) of the PE <NUM>(<NUM>) is configured to send a response indicating that the PE <NUM>(P) should send its request to the SPCOP <NUM> before it is permitted to come back on the conventional path. This prevents access to a coherence granule that is covered by a CPAA protection window for the duration of that CPAA protection window. Otherwise, there exists the possibility of a starvation issue if the second coherence granule <NUM>(<NUM>) should need to be serviced by the same system resources that are handling the first coherence granule <NUM>(<NUM>). For example, if requests directed to the first coherence granule <NUM>(<NUM>) are not directed to the SPCOP <NUM> when they are resent, their presence in the conventional request path may prevent the PE <NUM>(<NUM>) from making progress on obtaining the second coherence granule <NUM>(<NUM>) in an exclusive state.

To illustrate communication flows among elements of the processor-based device <NUM> of <FIG> for requesting a CPAA token and performing an atomic memory access operation according to one example, <FIG> is provided. Elements of <FIG> are referenced in describing <FIG> for the sake of clarity. In the example of <FIG>, it is assumed that the size of each address block <NUM>(<NUM>)-<NUM>(A) is the same as the size of each coherence granule <NUM>(<NUM>)-<NUM>(C). As seen in <FIG>, a message flow diagram <NUM> shows the PE <NUM>(<NUM>), the COP <NUM>, and the SPCOP <NUM> represented by vertical lines, with communications between these elements illustrated by captioned arrows. Note that, while in the example of <FIG>, the COP <NUM> is shown servicing both the first coherence granule <NUM>(<NUM>) and the second coherence granule <NUM>(<NUM>), some embodiments may provide that the first coherence granule <NUM>(<NUM>) and the second coherence granule <NUM>(<NUM>) may map to different COPs.

In <FIG>, operations begin with the PE <NUM>(<NUM>) sending a request <NUM> for a CPAA token for the address block <NUM>(<NUM>) containing the first coherence granule <NUM>(<NUM>) to the SPCOP <NUM>. The SPCOP <NUM> responds by distributing a CPAA token <NUM> for the address block <NUM>(<NUM>) containing the first coherence granule <NUM>(<NUM>). This begins a period during which the CPAA token is considered to be "active. " In some embodiments, the SPCOP <NUM> may distribute the CPAA token <NUM> by sending a response comprising the CPAA token <NUM> to the first PE <NUM>(<NUM>). Some embodiments may provide that the SPCOP <NUM> distributes the CPAA token <NUM> by sending a response to the first PE <NUM>(<NUM>) indicating that the first PE <NUM>(<NUM>) is to retry its request <NUM> for the CPAA token <NUM> for the first coherence granule <NUM>(<NUM>). According to some embodiments, the SPCOP <NUM> may distribute the CPAA token <NUM> only if one of the following conditions are met: (<NUM>) the request <NUM> does not match an active CPAA token and there are CPAA tokens available; or (<NUM>) the request is from a PE <NUM>(<NUM>)-<NUM>(P) that is next in a CPAA reservation queue of the SPCOP <NUM> (as discussed in greater detail with respect to <FIG>), and the request does not correspond to an active CPAA token.

After receiving the CPAA token <NUM>, the PE <NUM>(<NUM>) then sends a request <NUM> to obtain the first coherence granule <NUM>(<NUM>) in an exclusive state to a COP (in this example, the COP <NUM>). Upon the first coherence granule <NUM>(<NUM>) becoming available, the COP <NUM> sends a response <NUM> granting access to the first coherence granule <NUM>(<NUM>) in an exclusive state to the PE <NUM>(<NUM>), thereby opening a CPAA protection window. The PE <NUM>(<NUM>) next sends a request <NUM> to obtain the second coherence granule <NUM>(<NUM>) in an exclusive state to the COP <NUM>. When the second coherence granule <NUM>(<NUM>) becomes available, the COP <NUM> sends a response <NUM> granting access to the second coherence granule <NUM>(<NUM>) in an exclusive state. At this point, the CPAA protection window ends and the normal protection window, during which the PE <NUM>(<NUM>) is able to complete the atomic memory access request <NUM>, is opened. After completing the atomic memory access request <NUM>, the PE <NUM>(<NUM>) sends a request <NUM> to return the CPAA token <NUM> to the SPCOP <NUM>. When the SPCOP <NUM> receives the request <NUM>, the CPAA token <NUM> for the address block <NUM>(<NUM>) containing the first coherence granule <NUM>(<NUM>) is considered inactive. The SPCOP <NUM> then sends a response <NUM> indicating that the CPAA token <NUM> has been returned.

To avoid starvation of CPAA tokens from other PEs <NUM>(<NUM>)-<NUM>(P), once the PE <NUM>(<NUM>) has completed its atomic memory access for the pair of coherence granules <NUM>(<NUM>), <NUM>(<NUM>), the PE <NUM>(<NUM>) must request a new CPAA token when it wants to perform an atomic memory access for a second pair of coherence granules <NUM>(<NUM>)-<NUM>(C).

In some embodiments, the atomic memory access to be performed by the PE <NUM>(<NUM>) may be to a non-cacheable memory location. In such embodiments, as part of the process of acquiring the coherence granules <NUM>(<NUM>) and <NUM>(<NUM>) in an exclusive state, the PE <NUM>(<NUM>) registers the atomic memory access request <NUM> with the snoop filter <NUM> to indicate that the snoop filter <NUM>, when handling a subsequent access to the non-cacheable memory location by another PE <NUM>(<NUM>)-<NUM>(P), causes a snoop request to be sent to the PE <NUM>(<NUM>). The PE <NUM>(<NUM>) may then follow the flow described above with respect to obtaining a CPAA token and performing the atomic memory access.

<FIG> illustrates in greater detail the constituent elements of an exemplary embodiment of the SPCOP <NUM> of <FIG>. It is to be understood that some embodiments of the SPCOP <NUM> may include more or fewer constituent elements than those illustrated in <FIG>. As seen in <FIG>, the SPCOP <NUM> provides an SPCOP logic circuit <NUM>, which is configured to provide the functionality attributed to the SPCOP <NUM> as described herein. The SPCOP <NUM> may also provide a CPAA token buffer <NUM>, which may be used to store data (e.g., a memory address of a coherence granule associated with a CPAA token and/or an identifier of the PE that requested the CPAA token, as non-limiting examples) for one or more CPAA tokens.

In some embodiments, the SPCOP <NUM> may provide a CPAA access queue <NUM>, which is used to track requests to access coherence granules (e.g., in the case of the PE <NUM>(P) that was instructed to resend its request to the SPCOP <NUM>, as discussed above). If such a request is received by the SPCOP <NUM>, the SPCOP <NUM> may first determine whether the request matches an active CPAA token, and, if not, the SPCOP <NUM> sends a response indicating that the requesting PE <NUM>(P) is to return to conventional memory coherence handling by, for example, resending its request using the conventional channel. However, if the request does match an active CPAA token such as the CPAA token <NUM>, the SPCOP <NUM> may record an identifier for the request, along with the corresponding CPAA token slot, in an entry of the CPAA access queue <NUM>. When the CPAA token <NUM> is eventually returned to the SPCOP <NUM>, the SPCOP <NUM> sends a response indicating that the requesting PE <NUM>(P) is to return to conventional memory coherence handling. If the CPAA access queue <NUM> is full when the SPCOP <NUM> attempts to add a new entry, the SPCOP <NUM> may send a response to the PE <NUM>(P) indicating that the PE <NUM>(P) should retry its request to the SPCOP <NUM> again.

Finally, the SPCOP <NUM> according to some embodiments may include a CPAA reservation queue <NUM> to allow CPAA tokens to be reserved by requesting PEs <NUM>(<NUM>)-<NUM>(P). When the SPCOP <NUM> receives a request for a CPAA token, such as the request <NUM> of <FIG>, the SPCOP <NUM> may add the request <NUM> to the CPAA reservation queue <NUM> if any one of the following conditions is met: (<NUM>) the request <NUM> does not match an active CPAA token, but no CPAA tokens are available to distribute; (<NUM>) the request <NUM> matches an active CPAA token; or (<NUM>) the request is from a PE <NUM>(<NUM>)-<NUM>(P) that is next in the CPAA reservation queue <NUM>, but the memory address of the request matches that of an active CPAA token (i.e., the memory address requires access to an address block <NUM>(<NUM>)-<NUM>(A) for which an active CPAA token is outstanding).

When the SPCOP <NUM> next has a CPAA token available, it may distribute the CPAA token as described above with respect to the CPAA token <NUM>. In particular, the SPCOP <NUM> in some embodiments may send a response comprising the CPAA token to the PE <NUM>(<NUM>)-<NUM>(P) that is next in the CPAA reservation queue <NUM>. Such embodiments require the SPCOP <NUM> to store the memory address of the coherence granule requested by the PE in the CPAA reservation queue <NUM>, which may not scale well if there are a large number of PEs <NUM>(<NUM>)-<NUM>(P) that may attempt to request a CPAA token. According to some embodiments, the SPCOP <NUM> may send a response to the PE <NUM>(<NUM>)-<NUM>(P) that is next in the CPAA reservation queue <NUM>, indicating that the PE <NUM>(<NUM>)-<NUM>(P) should retry its request to obtain a CPAA token. In such embodiments, the SPCOP <NUM> may check to ensure that an identifier of a PE <NUM>(<NUM>)-<NUM>(P) for an incoming request for a CPAA token matches the PE <NUM>(<NUM>)-<NUM>(P) that is next in the CPAA reservation queue <NUM> before distributing an available CPAA token. This allows the SPCOP <NUM> to obtain the memory address of the coherence granule for the CPAA token and also maintain the reservation for the PE <NUM>(<NUM>)-<NUM>(P) without needing to record the full memory address of the coherence granule for every entry in the CPAA reservation queue <NUM>.

Some embodiments may provide that the CPAA reservation queue <NUM> comprises a bit vector having a size that is one less than the number of PEs <NUM>(<NUM>)-<NUM>(P) that may be expected to perform an atomic memory access. In such embodiments, the SPCOP <NUM> may limit the number of concurrent CPAA tokens per PE <NUM>(<NUM>)-<NUM>(P) to be one (<NUM>), and may use the bit vector to record each request in the CPAA reservation queue <NUM> rather than storing a full identifier for each PE <NUM>(<NUM>)-<NUM>(P) per CPAA token request. In this manner, the scalability of the CPAA reservation queue <NUM> may be increased.

To prevent a denial of service (DoS) attack by a malicious agent, the SPCOP <NUM> in some embodiments may be configured to copy the CPAA reservation queue <NUM> into a next active queue <NUM>. The SPCOP <NUM> may then select the PEs <NUM>(<NUM>)-<NUM>(P) in the next active queue <NUM> as CPAA tokens become available, while recording newly arriving requests for CPAA tokens in the CPAA reservation queue <NUM>. The CPAA reservation queue <NUM> may subsequently be copied into the next active queue <NUM> when the next active queue <NUM> is emptied. Such embodiments ensure that every PE <NUM>(<NUM>)-<NUM>(P) is afforded an opportunity to obtain a CPAA token before any PE <NUM>(<NUM>)-<NUM>(P) is allowed to receive a second CPAA token.

<FIG> and <FIG> illustrate exemplary communication flows between multiple PEs <NUM>(<NUM>), <NUM>(<NUM>), and <NUM>(P) and the SPCOP <NUM> of <FIG>, where the PEs <NUM>(<NUM>), <NUM>(<NUM>), and <NUM>(P) are each attempting to obtain a CPAA token (with the assumption that, in this example, only a single CPAA token is available). Elements of <FIG> and <FIG> are referenced in describing <FIG> and <FIG> for the sake of clarity. In <FIG> and <FIG>, a message flow diagram <NUM> shows the PEs <NUM>(<NUM>), <NUM>(<NUM>), and <NUM>(P) and the SPCOP <NUM> represented by vertical lines, with communications between these elements illustrated by captioned arrows and operations performed by each element illustrated by captioned boxes. It is to be assumed that the SPCOP <NUM> in <FIG> and <FIG> implements its CPAA reservation queue (e.g., the CPAA reservation queue <NUM> of <FIG>) using a bit vector or another implementation in which the CPAA reservation queue <NUM> does not record an identifier for the PEs <NUM>(<NUM>), <NUM>(<NUM>) and <NUM>(P) or an identifier for a CPAA token.

Operations begin in <FIG> with the PE <NUM>(P) sending a request <NUM> for a CPAA token to the SPCOP <NUM>, followed by the PE <NUM>(<NUM>) sending a request <NUM> for a CPAA token to the SPCOP <NUM>. The SPCOP <NUM> distributes a CPAA token <NUM> to the PE <NUM>(P). Because the SPCOP <NUM> also received the request <NUM> from the PE <NUM>(<NUM>), the PE <NUM>(<NUM>) is added to the CPAA reservation queue <NUM> of the SPCOP <NUM>, as indicated by box <NUM>. Shortly thereafter, the PE <NUM>(<NUM>) also sends its own request <NUM> for a CPAA token, and is also added to the CPAA reservation queue <NUM> of the SPCOP <NUM>, as indicated by box <NUM>. After PE <NUM>(P) completes its atomic memory access, the PE <NUM>(P) sends a request <NUM> to return the CPAA token <NUM> to the SPCOP <NUM>. The SPCOP <NUM> acknowledges the return of the CPAA token <NUM> by sending a response <NUM> to the PE <NUM>(P).

The SPCOP <NUM> then reserves a next CPAA token for the next PE (i.e., the PE <NUM>(<NUM>)) in the CPAA reservation queue <NUM>, and begins a communications exchange to distribute a CPAA token to PE <NUM>(<NUM>). The SPCOP <NUM> thus sends a response <NUM> to the PE <NUM>(<NUM>) to retry its request <NUM> for a CPAA token. Consequent to receiving the response <NUM>, the PE <NUM>(<NUM>) sends a request <NUM> for a CPAA token to the SPCOP <NUM>. The SPCOP <NUM> then distributes a CPAA token <NUM> to the PE <NUM>(<NUM>). Communications then continue in <FIG>.

Turning now to <FIG>, the PE <NUM>(<NUM>), upon completing its atomic memory access, sends a request <NUM> to return the CPAA token <NUM> to the SPCOP <NUM>. The SPCOP <NUM> acknowledges the return of the CPAA token <NUM> by sending a response <NUM> to the PE <NUM>(<NUM>), and then sends a response <NUM> to the next PE (i.e., PE <NUM>(<NUM>)) in the CPAA reservation queue <NUM> to notify the PE <NUM>(<NUM>) to retry its request <NUM> for a CPAA token. The PE <NUM>(<NUM>) thus sends another request <NUM> for a CPAA token, and the SPCOP <NUM> responds by distributing a CPAA token <NUM>. After completing its atomic memory access, the PE <NUM>(<NUM>) sends a request <NUM> to return its CPAA token <NUM>, and the SPCOP <NUM> sends a response <NUM> to acknowledge that the CPAA token <NUM> was returned.

It is to be understood that, depending on the implementation of the CPAA reservation queue <NUM>, the SPCOP <NUM> may distribute tokens to the PEs <NUM>(<NUM>) and <NUM>(<NUM>) in a different order than their respective requests <NUM> and <NUM> were received by the SPCOP <NUM>. For example, assume that the CPAA reservation queue <NUM> is implemented as a bit vector, and the request <NUM> for the PE <NUM>(<NUM>) is received before the request <NUM> for the PE <NUM>(<NUM>). This would result in both the bits representing the PEs <NUM>(<NUM>) and <NUM>(<NUM>) being set in the CPAA reservation queue <NUM> when their respective requests <NUM> and <NUM> are received by the SPCOP <NUM>. However, the SPCOP <NUM> may still process the bits representing the PEs <NUM>(<NUM>) and <NUM>(<NUM>) in order, resulting in the PE <NUM>(<NUM>) being issued its CPAA token <NUM> before the PE <NUM>(<NUM>) is issued its CPAA token <NUM>.

To illustrate exemplary communication flows between the SPCOP <NUM> of <FIG> and multiple PEs <NUM>(<NUM>) and <NUM>(P) for using the CPAA access queue <NUM> of the SPCOP <NUM> to record attempts to access a coherence granule that is protected by an active CPAA token, <FIG> are provided. For the sake of clarity, elements of <FIG> and <FIG> are referenced in describing <FIG>. In the example of <FIG>, it is assumed that the size of each address block <NUM>(<NUM>)-<NUM>(A) is the same as the size of each coherence granule <NUM>(<NUM>)-<NUM>(C). In <FIG>, a message flow diagram <NUM> shows the PEs <NUM>(<NUM>) and <NUM>(P), the COP <NUM>, and the SPCOP <NUM> represented by vertical lines, with communications between these elements illustrated by captioned arrows and operations performed by each element illustrated by captioned boxes.

In <FIG>, operations begin with the PE <NUM>(<NUM>) sending a request <NUM> for a CPAA token to the SPCOP <NUM>. As a result of receiving the request <NUM>, the SPCOP distributes a CPAA token <NUM> to the PE <NUM>(<NUM>). The PE <NUM>(<NUM>) then sends a request <NUM> to obtain the first coherence granule (e.g., the coherence granule <NUM>(<NUM>) of <FIG>) in an exclusive state. Around the same time, the PE <NUM>(P) also sends a request <NUM> to obtain the first coherence granule <NUM>(<NUM>) in an exclusive state. The COP <NUM> responds to the PE <NUM>(<NUM>) first by sending a response <NUM> granting access to the first coherence granule <NUM>(<NUM>) an exclusive state. Additionally, due to receiving the request <NUM> from the PE <NUM>(P), the COP <NUM> sends a snoop request <NUM> to the PE <NUM>(<NUM>) for the first coherence granule <NUM>(<NUM>) (which the PE <NUM>(<NUM>) now holds in an exclusive state). The PE <NUM>(<NUM>) in the meantime sends a request <NUM> to the COP <NUM> seeking to obtain a second coherence granule (e.g., the coherence granule <NUM>(<NUM>)) in an exclusive state. Communications then continue in <FIG>.

Referring now to <FIG>, consequent to receiving the snoop request <NUM>, the PE <NUM>(<NUM>) sends a response <NUM> to the COP <NUM> indicating that the requesting PE (i.e., the PE <NUM>(P)) should retry its request <NUM> to the SPCOP <NUM>. The COP <NUM> then forwards a response <NUM> to the PE <NUM>(P) to thus inform the PE <NUM>(P). The COP <NUM> also sends a response <NUM> to the PE <NUM>(<NUM>) granting access to the second coherence granule <NUM>(<NUM>) in an exclusive state. At this point, the PE <NUM>(<NUM>) can proceed with performing its atomic memory access on the first coherence granule <NUM>(<NUM>) and the second coherence granule <NUM>(<NUM>).

The PE <NUM>(P), due to receiving the response <NUM> from the COP <NUM>, sends a request <NUM> to the SPCOP <NUM> seeking to obtain the first coherence granule <NUM>(<NUM>) in an exclusive state. The SPCOP <NUM> determines that the request <NUM> from the PE <NUM>(P) corresponds to the active CPAA token <NUM>, and thus adds the PE <NUM>(P) to the CPAA access queue <NUM> as indicated by box <NUM>. The PE <NUM>(<NUM>), having completed its atomic memory access at this point, sends a request <NUM> to return the CPAA token <NUM> to the SPCOP <NUM>, and the SPCOP <NUM> sends a response <NUM> acknowledging that the CPAA token <NUM> was returned. With the CPAA token <NUM> no longer active, the SPCOP <NUM> determines that the PE <NUM>(P) no longer has a hazard with an active CPAA token, and thus sends a response <NUM> to the PE <NUM>(P) indicating that it should retry its request <NUM> on the conventional memory coherence handling path. The PE <NUM>(P) then sends a request <NUM> to obtain the first coherence granule <NUM>(<NUM>) in an exclusive state to the COP <NUM>. Communications then continue in <FIG>.

Turning now to <FIG>, as a result of receiving the request <NUM>, the COP <NUM> sends a snoop request <NUM> for the first coherence granule <NUM>(<NUM>) to the PE <NUM>(<NUM>). The PE <NUM>(<NUM>) then sends a response <NUM> indicating that the PE <NUM>(P) may obtain the desired access to the first coherence granule <NUM>(<NUM>).

As noted above, some embodiments of the processor-based device <NUM> of <FIG> may include multiple dies <NUM>(<NUM>)-<NUM>(D), each of which may include PEs and an SPCOP corresponding to the PEs <NUM>(<NUM>)-<NUM>(P) and the SPCOP <NUM> of the die <NUM>(<NUM>) of <FIG>. In this regard, <FIG> and <FIG> provide a message flow diagram <NUM> illustrating exemplary communication flows between multiple SPCOPs and PEs that are located on multiple dies <NUM>(<NUM>)-<NUM>(D) of the processor-based device <NUM> of <FIG>. Elements of <FIG> are referenced in describing <FIG> and <FIG> for the sake of clarity. In this example, consider two dies, Die A and Die B, each of which may correspond to one of the dies <NUM>(<NUM>)-<NUM>(D) of <FIG>. Die A includes a PE <NUM> and an SPCOP <NUM> that correspond in functionality to the PEs <NUM>(<NUM>)-<NUM>(P) and the SPCOP <NUM> of <FIG>, respectively. Likewise, Die B includes a PE <NUM> and an SPCOP <NUM> that also correspond in functionality to the PEs <NUM>(<NUM>)-<NUM>(P) and the SPCOP <NUM> of <FIG>, respectively. The SPCOPs <NUM> and <NUM> each ensure that PEs on their respective dies take turns obtaining a CPAA token from a system SPCOP <NUM>, which in tum ensures that the SPCOPs <NUM> and <NUM> take turns obtaining CPAA tokens. The system SPCOP <NUM> in some embodiments may comprise one of the SPCOPs <NUM> or <NUM>, or may comprise another SPCOP on another die. As seen in <FIG> and <FIG>, each of the PEs <NUM> and <NUM>, the SPCOPs <NUM> and <NUM>, and the system SPCOP <NUM> is represented by a vertical line, with communications between these elements illustrated by captioned arrows.

In <FIG>, operations begin with the PE <NUM> sending a request <NUM> for a CPAA token to the SPCOP <NUM> for Die A, which forwards the request <NUM> for a CPAA token to the system SPCOP <NUM>. At about the same time, the PE <NUM> sends a request <NUM> for a CPAA token to the SPCOP <NUM> for Die B, which forwards the request <NUM> for a CPAA request to the system SPCOP <NUM>. The system SPCOP <NUM> opts to distribute a CPAA token <NUM> to the SPCOP <NUM>, which then forwards the CPAA token <NUM> to the PE <NUM>. The system SPCOP <NUM> also adds the SPCOP <NUM> to its own CPAA reservation queue, as indicated by block <NUM>. After the PE <NUM> completes its atomic memory access, the PE <NUM> sends a request <NUM> to return the CPAA token <NUM>, which the SPCOP <NUM> forwards to the system SPCOP <NUM>. The system SPCOP <NUM> sends a response <NUM> acknowledging the return of the CPAA token <NUM> to the SPCOP <NUM>, which is forwarded to the PE <NUM> by the SPCOP <NUM>.

The system SPCOP <NUM> then identifies the SPCOP <NUM> as the next SPCOP to receive a CPAA token, and thus sends a response <NUM> to the SPCOP <NUM> indicating that the SPCOP <NUM> should retry its request for a CPAA token. The SPCOP <NUM> then sends a request <NUM> for a CPAA token to the system SPCOP <NUM>. Communications then continue in <FIG>.

Referring now to <FIG>, the system SPCOP <NUM> distributes a CPAA token <NUM> to the SPCOP <NUM>, which forwards the CPAA token <NUM> to the PE <NUM>. After the PE <NUM> has completed its atomic memory access, the PE <NUM> sends a request <NUM> to return the CPAA token <NUM> to the SPCOP <NUM>, which forwards the request <NUM> to the system SPCOP <NUM>. The SPCOP <NUM> sends a response <NUM> acknowledging the return of the CPAA token <NUM> to the SPCOP <NUM>, and the SPCOP forwards the response <NUM> to the PE <NUM>.

To illustrate exemplary operations of the PEs <NUM>(<NUM>)-<NUM>(P) of <FIG> for requesting CPAA tokens, obtaining exclusive access to a corresponding pair of coherence granules <NUM>(<NUM>)-<NUM>(C), and performing an atomic memory access operation according to some embodiments, <FIG> and <FIG> provide a flowchart <NUM>. For the sake of clarity, elements of <FIG>, <FIG>, and <FIG> are referenced in describing <FIG> and <FIG>. Operations in <FIG> begin with the first PE <NUM>(<NUM>) of the plurality of PEs <NUM>(<NUM>)-<NUM>(P) of the processor-based device <NUM> detecting the atomic memory access request <NUM> that spans a boundary between the first coherence granule <NUM>(<NUM>) and the second coherence granule <NUM>(<NUM>) of the system memory <NUM> of the processor-based device <NUM>, wherein the lowest-order bit of the memory address used to select the first coherence granule <NUM>(<NUM>) is the inverse of the lowest-order bit of the memory address used to select the second coherence granule <NUM>(<NUM>) (block <NUM>). The first PE <NUM>(<NUM>) then sends a request, such as the request <NUM> of <FIG>, for a CPAA token for the address block <NUM>(<NUM>) containing the first coherence granule <NUM>(<NUM>) to the SPCOP <NUM> (block <NUM>).

Subsequently, the first PE <NUM>(<NUM>) receives from the SPCOP <NUM> a CPAA token (e.g., the CPAA token <NUM> of <FIG>) for the address block <NUM>(<NUM>) containing the first coherence granule <NUM>(<NUM>), the CPAA token <NUM> indicating that the first PE <NUM>(<NUM>) of the plurality of PEs <NUM>(<NUM>)-<NUM>(P) is allowed to protect the address block <NUM>(<NUM>) containing the first coherence granule <NUM>(<NUM>) (block <NUM>). In some embodiments, the first PE <NUM>(<NUM>) may receive, while the first PE <NUM>(<NUM>) holds the CPAA token <NUM>, a first snoop request (such as the snoop request <NUM> of <FIG>) for the first coherence granule <NUM>(<NUM>) from the second PE <NUM>(P) of the plurality of PEs <NUM>(<NUM>)-<NUM>(P) (block <NUM>). Responsive to receiving the first snoop request <NUM> for the first coherence granule <NUM>(<NUM>), the first PE <NUM>(<NUM>) may send a first response (i.e., the response <NUM> of <FIG>) to the second PE <NUM>(P), the first response <NUM> indicating that the second PE <NUM>(P) should redirect all requests for the first coherence granule <NUM>(<NUM>) to the SPCOP <NUM> until the CPAA token <NUM> is returned (block <NUM>). Processing then resumes at block <NUM> of <FIG>.

Turning now to <FIG>, the first PE <NUM>(<NUM>) next obtains the first coherence granule <NUM>(<NUM>) and the second coherence granule <NUM>(<NUM>) in an exclusive state (block <NUM>). According to some embodiments, if the atomic memory access request <NUM> indicates a non-cacheable memory location, the first PE <NUM>(<NUM>) may register the atomic memory access request <NUM> with a snoop filter <NUM> to indicate that, due to a subsequent access to the non-cacheable memory location by the second PE <NUM>(P) of the plurality of PEs <NUM>(<NUM>)-<NUM>(P), a snoop request is to be sent to the first PE <NUM>(<NUM>) (block <NUM>). The first PE <NUM>(<NUM>) then completes the atomic memory access request <NUM> (block <NUM>). The first PE <NUM>(<NUM>) finally sends a request <NUM> to return the CPAA token <NUM> for the first coherence granule <NUM>(<NUM>) to the SPCOP <NUM> (block <NUM>).

<FIG> provides a flowchart <NUM> to illustrate exemplary operations of the SPCOP <NUM> of <FIG> for using a CPAA access queue, such as the CPAA access queue <NUM> of <FIG>, to handle memory accesses to coherence granules (e.g., the coherence granules <NUM>(<NUM>)-<NUM>(C) of <FIG>) that are protected by an active CPAA token. Elements of <FIG> and <FIG>are referenced in describing <FIG> for the sake of clarity. In the example of <FIG>, it is assumed that only one CPAA token may be active at a given time. In <FIG>, operations begin with an SPCOP, such as the SPCOP <NUM> of <FIG>, receiving a second request, such as the request <NUM> of <FIG>, for the first coherence granule <NUM>(<NUM>) from a second PE, such the PE <NUM>(P) (block <NUM>). The SPCOP <NUM> then determines whether the memory address of the second request <NUM> corresponds to an active CPAA token, such as the CPAA token <NUM> of <FIG> (block <NUM>). If not, the SPCOP <NUM> sends a second response to the second PE <NUM>(P), the second response indicating that the second PE <NUM>(P) is to return to conventional memory coherence handling (block <NUM>).

If the SPCOP <NUM> determines at decision block <NUM> that the memory address of the second request <NUM> does correspond to the active CPAA token <NUM>, the SPCOP <NUM> next determines whether the CPAA access queue <NUM> of the SPCOP <NUM> is full (block <NUM>). If not, the SPCOP records an identifier of the second PE <NUM>(P) in the CPAA access queue <NUM> (block <NUM>). Subsequently, upon return of the CPAA token <NUM> by a first PE (e.g., the PE <NUM>(<NUM>) of <FIG>), the SPCOP <NUM> sends a fourth response to the second PE <NUM>(P) based on the identifier of the second PE <NUM>(P) in the CPAA access queue <NUM>, the fourth response indicating that the second PE <NUM>(P) is to return to conventional memory coherence handling (block <NUM>). However, if the SPCOP <NUM> determines at decision block <NUM> that the CPAA access queue <NUM> is full, the SPCOP <NUM> sends a third response to the second PE <NUM>(P), the third response indicating that the second PE <NUM>(P) should retry the second request <NUM> to the SPCOP <NUM> (block <NUM>).

To illustrate exemplary operations of the SPCOP <NUM> of <FIG> for using the CPAA reservation queue <NUM> of <FIG> to reserve a CPAA token and subsequently distribute a reserved CPAA token, <FIG> provides a flowchart <NUM>. For the sake of clarity, elements of <FIG> and <FIG> are referenced in describing <FIG>. In <FIG>, operations begin with an SPCOP, such as the SPCOP <NUM> of <FIG>, receiving the request for a CPAA token (such as the request <NUM> of <FIG>) from the first PE <NUM>(<NUM>) (block <NUM>). The SPCOP <NUM> determines whether a CPAA token is available (block <NUM>). If not, the SPCOP adds the first PE <NUM>(<NUM>) to the CPAA reservation queue <NUM> (block <NUM>).

If the SPCOP <NUM> determines at decision block <NUM> that a CPAA token is available, the SPCOP <NUM> next determines whether the atomic memory access request <NUM> corresponds to an active CPAA token, such as the CPAA token <NUM> of <FIG> (block <NUM>). If so, processing resumes at block <NUM>. If the SPCOP <NUM> determines at decision block <NUM> that the atomic memory access request <NUM> does not correspond to an active CPAA token <NUM>, the SPCOP <NUM> then determines whether the first PE <NUM>(<NUM>) is next in the CPAA reservation queue <NUM> of the SPCOP <NUM> (block <NUM>). If not, processing resumes at block <NUM>. However, if the SPCOP <NUM> determines at decision block <NUM> that the first PE <NUM>(<NUM>) is next in the CPAA reservation queue <NUM>, the SPCOP <NUM> distributes a CPAA token (i.e., the CPAA token <NUM>) to the first PE <NUM>(<NUM>) (block <NUM>). In some embodiments, the operation of block <NUM> for distributing the CPAA token <NUM> may comprise the SPCOP <NUM> sending a response comprising the CPAA token <NUM> to the first PE <NUM>(<NUM>) (block <NUM>). Some embodiments may provide that the operation of block <NUM> for distributing the CPAA token <NUM> may comprise the SPCOP <NUM> sending a response, such as the response <NUM>, to the first PE <NUM>(<NUM>) indicating that the first PE <NUM>(<NUM>) is to retry the request <NUM> for a CPAA token for the address block containing the first coherence granule <NUM>(<NUM>) (block <NUM>). For example, operations of block <NUM> may be performed in embodiments in which the first PE <NUM>(<NUM>) is next in the CPAA reservation queue <NUM>, and the CPAA reservation queue <NUM> is implemented such that an identifier of the first PE <NUM>(<NUM>) is not stored and thus not known to the SPCOP <NUM> at the time the CPAA token <NUM> is to be distributed.

<FIG> is a block diagram of an exemplary processor-based device <NUM>, such as the processor-based device <NUM> of <FIG>, that enables atomic memory accesses across coherence granule boundaries. The processor-based device <NUM> may be a circuit or circuits included in an electronic board card, such as a printed circuit board (PCB), a server, a personal computer, a desktop computer, a laptop computer, a personal digital assistant (PDA), a computing pad, a mobile device, or any other device, and may represent, for example, a server or a user's computer. In this example, the processor-based device <NUM> includes a processor <NUM>. The processor <NUM> represents one or more general-purpose processing circuits, such as a microprocessor, central processing unit, or the like, and may correspond to the PEs <NUM>(<NUM>)-<NUM>(P) of <FIG>. The processor <NUM> is configured to execute processing logic in instructions for performing the operations and steps discussed herein. In this example, the processor <NUM> includes an instruction cache <NUM> for temporary, fast access memory storage of instructions and an instruction processing circuit <NUM>. Fetched or prefetched instructions from a memory, such as from a system memory <NUM> over a system bus <NUM>, are stored in the instruction cache <NUM>. The instruction processing circuit <NUM> is configured to process instructions fetched into the instruction cache <NUM> and process the instructions for execution.

The processor <NUM> and the system memory <NUM> are coupled to the system bus <NUM> and can intercouple peripheral devices included in the processor-based device <NUM>. As is well known, the processor <NUM> communicates with these other devices by exchanging address, control, and data information over the system bus <NUM>. For example, the processor <NUM> can communicate bus transaction requests to a memory controller <NUM> in the system memory <NUM> as an example of a peripheral device. Although not illustrated in <FIG>, multiple system buses <NUM> could be provided, wherein each system bus constitutes a different fabric. In this example, the memory controller <NUM> is configured to provide memory access requests to a memory array <NUM> in the system memory <NUM>. The memory array <NUM> is comprised of an array of storage bit cells for storing data. The system memory <NUM> may be a read-only memory (ROM), flash memory, dynamic random access memory (DRAM), such as synchronous DRAM (SDRAM), etc., and a static memory (e.g., flash memory, static random access memory (SRAM), etc.), as non-limiting examples.

Other devices can be connected to the system bus <NUM>. As illustrated in <FIG>, these devices can include the system memory <NUM>, one or more input devices <NUM>, one or more output devices <NUM>, a modem <NUM>, and one or more display controllers <NUM>, as examples. The input device(s) <NUM> can include any type of input device, including, but not limited to, input keys, switches, voice processors, etc. The output device(s) <NUM> can include any type of output device, including, but not limited to, audio, video, other visual indicators, etc. The modem <NUM> can be any device configured to allow exchange of data to and from a network <NUM>. The network <NUM> can be any type of network, including, but not limited to, a wired or wireless network, a private or public network, a local area network (LAN), a wireless local area network (WLAN), a wide area network (WAN), a BLUETOOTH™ network, and the Internet. The modem <NUM> can be configured to support any type of communications protocol desired. The processor <NUM> may also be configured to access the display controller(s) <NUM> over the system bus <NUM> to control information sent to one or more displays <NUM>. The display(s) <NUM> can include any type of display, including, but not limited to, a cathode ray tube (CRT), a liquid crystal display (LCD), a plasma display, etc..

The processor-based device <NUM> in <FIG> may include a set of instructions <NUM> that may be encoded with the reach-based explicit consumer naming model to be executed by the processor <NUM> for any application desired according to the instructions. The instructions <NUM> may be stored in the system memory <NUM>, processor <NUM>, and/or instruction cache <NUM> as examples of non-transitory computer-readable medium <NUM>. The instructions <NUM> may also reside, completely or at least partially, within the system memory <NUM> and/or within the processor <NUM> during their execution. The instructions <NUM> may further be transmitted or received over the network <NUM> via the modem <NUM>, such that the network <NUM> includes the computer-readable medium <NUM>.

While the computer-readable medium <NUM> is shown in an exemplary embodiment to be a single medium, the term "computer-readable medium" should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store the one or more sets of instructions <NUM>. The term "computer-readable medium" shall also be taken to include any medium that is capable of storing, encoding, or carrying a set of instructions for execution by a processing device and that cause the processing device to perform any one or more of the methodologies of the embodiments disclosed herein. The term "computer-readable medium" shall accordingly be taken to include, but not be limited to, solid-state memories, optical medium, and magnetic medium.

The embodiments disclosed herein include various steps. The steps of the embodiments disclosed herein may be formed by hardware components or may be embodied in machine-executable instructions, which may be used to cause a general-purpose or special-purpose processor programmed with the instructions to perform the steps. Alternatively, the steps may be performed by a combination of hardware and software process.

The embodiments disclosed herein may be provided as a computer program product, or software process, that may include a machine-readable medium (or computer-readable medium) having stored thereon instructions, which may be used to program a computer system (or other electronic devices) to perform a process according to the embodiments disclosed herein. A machine-readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium includes: a machine-readable storage medium (e.g., ROM, random access memory ("RAM"), a magnetic disk storage medium, an optical storage medium, flash memory devices, etc.), and the like.

Those of skill in the art will further appreciate that the various illustrative logical blocks, modules, circuits, and algorithms described in connection with the embodiments disclosed herein may be implemented as electronic hardware, instructions stored in memory or in another computer-readable medium and executed by a processor or other processing device, or combinations of both. The components of the distributed antenna systems described herein may be employed in any circuit, hardware component, integrated circuit (IC), or IC chip, as examples. Memory disclosed herein may be any type and size of memory and may be configured to store any type of information desired. To clearly illustrate this interchangeability, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. How such functionality is implemented depends on the particular application, design choices, and/or design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present embodiments.

Unless otherwise expressly stated, it is in no way intended that any method set forth herein be construed as requiring that its steps be performed in a specific order. Accordingly, where a method claim does not actually recite an order to be followed by its steps, or it is not otherwise specifically stated in the claims or descriptions that the steps are to be limited to a specific order, it is in no way intended that any particular order be inferred.

Claim 1:
A processor-based device (<NUM>), comprising:
a system memory (<NUM>) comprising a plurality of address blocks (<NUM>(<NUM>)-<NUM>(A)) and a plurality of coherence granules (<NUM>(<NUM>)-<NUM>(C));
a special-purpose central ordering point, SPCOP, (<NUM>) comprising an SPCOP logic circuit (<NUM>); and
a plurality of processing elements, PEs, (<NUM>(<NUM>)-<NUM>(P)) each comprising a memory access logic circuit (<NUM>(<NUM>)-<NUM>(P));
the memory access logic circuit (<NUM>(<NUM>)) of a first PE (<NUM>(<NUM>)) of the plurality of PEs configured to:
detect (<NUM>) an atomic memory access request (<NUM>) that spans a boundary between a first coherence granule (<NUM>(<NUM>)) and a second coherence granule (<NUM>(<NUM>)) of the system memory;
send (<NUM>) a request (<NUM>) for a coherence granule pair atomic access, CPAA, token for an address block (<NUM>(<NUM>)) containing the first coherence granule to the SPCOP;
receive (<NUM>), from the SPCOP, the CPAA token (<NUM>) for the address block containing the first coherence granule, the CPAA token indicating that the first PE of the plurality of PEs is allowed to protect the address block containing the first coherence granule;
obtain (<NUM>) the first coherence granule and the second coherence granule in an exclusive state;
complete (<NUM>) the atomic memory access request; and
send (<NUM>) a request to (<NUM>) return the CPAA token for the address block containing the first coherence granule to the SPCOP.