Patent Description:
A processor-based device may include multiple processing elements (PEs) (e.g., processor cores, as a non-limiting example) that each provide one or more local caches for storing frequently accessed data. Because the multiple PEs of the processor-based device may share a memory resource such as a system memory, multiple copies of shared data read from a given memory address may exist at the same time within the system memory and within the local caches of the PEs. Thus, to ensure that all of the PEs have a consistent view of the shared data, the processor-based device provides support for a cache coherence protocol to enable local changes to the shared data within one PE to be propagated to other PEs. In this manner, conflicts that may arise between the PEs due to inconsistencies between local copies of the shared data can be avoided.

Conventional cache coherence protocols include write invalidate protocols and write update protocols. Under a write invalidate protocol, when one PE writes to a coherence granule (a subdivision of the system memory representing an aligned size in bytes on which cache coherence is managed), all copies of the coherence granule stored in the local caches of the other PEs are invalidated, with dirty (i.e., modified) copies of the coherence granule being written to the system memory before being invalidated. A PE that loses a cached copy of the coherence granule in this manner may subsequently re-obtain a copy of the coherence granule via a memory load operation after the memory store operation that triggered the invalidation is completed. In contrast, under a write update protocol, when one PE writes new data to the coherence granule, all other PEs receive a copy of the new data, and update their respective local copies of the coherence granule using the new data. Consequently, the write update protocol does not require invalidation of any local cached copies of the coherence granule, and thus no additional memory load operations are needed to re-obtain a lost coherence granule.

The relative efficiency of the write invalidate protocol and the write update protocol may depend on the circumstances under which each PE is operating. In general, the write invalidate protocol is more efficient than the write update protocol in scenarios where many subsequent memory store operations to the same coherence granule are performed by a PE, and where the updated coherence granule is unlikely to be read by another PE in the near term. For example, when a software thread migrates from a first PE to a second PE, it is more efficient for a memory store operation from the second PE to invalidate a local cached copy of the coherence granule in the first PE than it would be to update the value of the local cached copy of the coherence granule in the first PE. The write update protocol, though, is more efficient than the write invalidate protocol when a memory store operation to a coherence granule is followed by memory load operations on the same coherence granule by multiple PEs. In this scenario, the write update protocol ensures that all PEs holding a local cached copy of the coherence granule receive an updated copy, whereas the write invalidate protocol in the same scenario would require PEs holding local cached copies of the coherence granule to invalidate their now-stale copies, and then perform memory load operations by sending individual read bus commands to a central ordering point (COP) to read the updated value.

Thus, while the write invalidate protocol and the write update protocol each have advantages in particular circumstances, neither is equally efficient in all scenarios. Moreover, information useful in determining which cache coherence protocol would be most efficient in a given scenario may not be accessible by a single entity such as the COP, but rather may be distributed among one or more of the master PE, the snooper PEs, and the COP. Accordingly, it is desirable to provide a mechanism by which an appropriate cache coherence protocol may be used according to existing circumstances at the time a memory store operation is performed. <CIT> describes a system that facilitates cache coherence with adaptive write updates. During operation, a cache is initialized to operate using a write-invalidate protocol. During program execution, the system monitors the dynamic behavior of the cache. If the dynamic behavior indicates that better performance can be achieved using a write-broadcast protocol, the system switches the cache to operate using the write-broadcast protocol. <NPL>; [<NPL>, describes that adaptive hybrid cache coherence protocols use both the write-invalidate mechanism and the write-update mechanism to maintain coherence among copies of data objects. Each of these protocols implements a decision function that chooses the appropriate mechanism in order to improve their performance. In the paper, the results of a performance evaluation of adaptive hybrid cache coherence protocols in both the traffic domain and in the time domain are presented. Three adaptive protocols with pure write invalidate and pure write-update protocols are compared. <NPL>, describes a Performance Monitoring System consisting of a specialized CPU core designed to allow efficient collection and evaluation of performance data for both static and dynamic optimizations. The system provides a transparent mechanism to change architectural features dynamically, inform the Operating System of process behaviors, and assist in profiling and debugging. For instance, a piece of hardware watching snoop packets can determine when a write-update cache coherence protocol would be helpful or detrimental to the currently running program. The system is designed to allow the hardware to feed performance statistics back to software, allowing dynamic architectural adjustments at runtime.

The dependent claims define particular embodiments.

Exemplary embodiments disclosed herein include providing dynamic selection of cache coherence protocols in processor-based devices. In this regard, in one exemplary embodiment, a processor-based device comprises a plurality of processing elements (PEs), including a master PE and at least one snooper PE, as well as a central ordering point (COP). As used herein, the term "master PE" refers to a PE that performs a memory store operation, and that sends cache coherence bus commands to the COP. The term "snooper PE" refers to a PE that receives snoop commands associated with the memory store operation from the COP, and then acts on the snoop commands to maintain cache coherence. Accordingly, a PE may operate as a master PE with respect to one memory store operation, and may also operate as a snooper PE with respect to a different memory store operation.

The COP of the processor-based device is configured to dynamically select, on a store-by-store basis, either the write invalidate protocol or the write update protocol as the cache coherence protocol to use for maintaining cache coherency for a memory store operation by the master PE. The selection is made by the COP based on one or more protocol preference indicators that may be generated and provided by one or more of the master PE, the at least one snooper PE, and the COP itself For example, in some embodiments, the master PE may predict, based on conditions known to the master PE, that the write update protocol is not advantageous in its current circumstances, and may prevent the write update protocol from being used for a memory store operation. Likewise, some embodiments may provide that one or more of the COP and the at least one snooper PE may indicate a preference for the write update protocol based on knowledge available to each (e.g., a number of PEs holding a local cached copy of the coherence granule, or a likelihood of subsequent re-reading of the coherence granule, as non-limiting examples). After selecting the cache coherence protocol to use based on the one or more protocol preference indicators, the COP sends a response message to each of the master PE and the at least one snooper PE indicating the selected cache coherence protocol for the memory store operation.

In another exemplary embodiment, a processor-based device is provided. The processor-based device comprises a plurality of PEs that include a master PE and at least one snooper PE. The processor-based device further comprises a COP. The master PE is configured to send a cache coherence bus command to the COP as part of a memory store operation. The COP is configured to, responsive to receiving the cache coherence bus command sent by the master PE, dynamically select, on a store-by-store basis, one of a write invalidate protocol and a write update protocol as a cache coherence protocol to use for maintaining cache coherency, based on one or more protocol preference indicators provided by one or more of the master PE, the at least one snooper PE, and the COP. The COP is further configured to send a response message to each of the master PE and the at least one snooper PE indicating the selected cache coherence protocol.

In another exemplary embodiment, a method for dynamically selecting cache coherence protocols in processor-based devices is provided. The method comprises sending, by a master PE of a plurality of PEs of a processor-based device, a cache coherence bus command to a COP of the processor-based device as part of a memory store operation. The method further comprises, responsive to receiving the cache coherence bus command, dynamically selecting, by the COP on a store-by-store basis, one of a write invalidate protocol and a write update protocol as a cache coherence protocol to use for maintaining cache coherency, based on one or more protocol preference indicators provided by one or more of the master PE, at least one snooper PE of the plurality of PEs, and the COP. The method also comprises sending, by the COP, a response message to each of the master PE and the at least one snooper PE indicating the selected cache coherence protocol.

In another exemplary embodiment, a non-transitory computer-readable medium having stored thereon computer-executable instructions is provided. The computer-executable instructions, when executed by a processor, cause the processor to send, by a master processing element (PE) of a plurality of PEs of the processor, a cache coherence bus command to a central ordering point (COP) of the processor as part of a memory store operation. The computer-executable instructions further cause the processor to, responsive to receiving the cache coherence bus command, dynamically select, by the COP on a store-by-store basis, one of a write invalidate protocol and a write update protocol as a cache coherence protocol to use for maintaining cache coherency, based on one or more protocol preference indicators provided by one or more of the master PE, at least one snooper PE of the plurality of PEs, and the COP. The computer-executable instructions also cause the processor to send, by the COP, a response message to each of the master PE and the at least one snooper PE indicating the selected cache coherence protocol.

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.

Exemplary embodiments disclosed herein include providing dynamic selection of cache coherence protocols in processor-based devices. In this regard, in one exemplary embodiment, a processor-based device comprises a plurality of processing elements (PEs), including a master PE and at least one snooper PE, as well as a central ordering point (COP). The COP of the processor-based device is configured to dynamically select, on a store-by-store basis, either the write invalidate protocol or the write update protocol as the cache coherence protocol to use for maintaining cache coherency for a memory store operation by the master PE. The selection is made by the COP based on one or more protocol preference indicators that may be generated and provided by one or more of the master PE, the at least one snooper PE, and the COP itself. For example, in some embodiments, the master PE may predict, based on conditions known to the master PE, that the write update protocol is not advantageous in its current circumstances, and may prevent the write update protocol from being used for a memory store operation. Likewise, some embodiments may provide that one or more of the COP and the at least one snooper PE may indicate a preference for the write update protocol based on knowledge available to each (e.g., a number of PEs holding a local cached copy of the coherence granule, or a likelihood of subsequent re-reading of the coherence granule, as non-limiting examples). After selecting the cache coherence protocol to use, the COP sends a response message to each of the master PE and the at least one snooper PE indicating the selected cache coherence protocol.

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, e.g., 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>(G), each representing the smallest unit of memory (e.g., <NUM> bytes, as a non-limiting example) for which cache coherence is maintained by the processor-based device <NUM>. The PEs <NUM>(<NUM>)-<NUM>(P) also include corresponding caches <NUM>(<NUM>)-<NUM>(P) comprising cache lines <NUM>(<NUM>)-<NUM>(C), <NUM>(<NUM>)-<NUM>(C), and <NUM>(<NUM>)-<NUM>(C), respectively. It is to be understood that the PEs <NUM>(<NUM>)-<NUM>(P) may include caches in addition to the caches <NUM>(<NUM>)-<NUM>(P) illustrated in <FIG>. The caches <NUM>(<NUM>)-<NUM>(P) are used by the respective PEs <NUM>(<NUM>)-<NUM>(P) to locally store data loaded from the system memory <NUM> for quicker access. For example, as seen in <FIG>, the cache lines <NUM>(<NUM>), <NUM>(<NUM>), and <NUM>(<NUM>) of the corresponding caches <NUM>(<NUM>)-<NUM>(P) store local copies ("COGRAN COPY") <NUM>, <NUM>, and <NUM>, respectively, of one of the coherence granules <NUM>(<NUM>)-<NUM>(G) (e.g., the coherence granule <NUM>(<NUM>), as a non-limiting example).

The processor-based device <NUM> further includes a central ordering point (COP) <NUM> that is configured to arbitrate among cache coherence bus commands received from master PEs among the PEs <NUM>(<NUM>)-<NUM>(P), direct snoop commands to and receive snoop replies from snooper PEs among the PEs <NUM>(<NUM>)-<NUM>(P), and send response messages to both master PEs and snooper PEs among the PEs <NUM>(<NUM>)-<NUM>(P). The COP <NUM> may work in conjunction with a snoop filter <NUM> that is configured to monitor traffic on the interconnect bus <NUM> to track coherence states of the cache lines <NUM>(<NUM>)-<NUM>(C), <NUM>(<NUM>)-<NUM>(C), and <NUM>(<NUM>)-<NUM>(C) of the PEs <NUM>(<NUM>)-<NUM>(P).

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.

As noted above, conventional processor-based devices provide support for cache coherence protocols, such as the write invalidate protocol and the write update protocol, to enable local changes to the shared data within one PE <NUM>(<NUM>)-<NUM>(P) to be propagated to other PEs <NUM>(<NUM>)-<NUM>(P) to ensure that all of the PEs <NUM>(<NUM>)-<NUM>(P) have a consistent view of the shared data. However, while the write invalidate protocol and the write update protocol each have advantages in particular circumstances, neither is equally efficient in all scenarios. Moreover, information that may be used in determining which cache coherence protocol would be most efficient in a given scenario may not be accessible by a single entity such as the COP <NUM> of <FIG>, but rather may be distributed among one or more of a master PE among the PEs <NUM>(<NUM>)-<NUM>(P), snooper PEs among the PEs <NUM>(<NUM>)-<NUM>(P), and the COP <NUM>.

In this regard, the processor-based device <NUM> of <FIG> is configured to provide dynamic selection of cache coherence protocols. As discussed in greater detail below with respect to <FIG>, the COP <NUM> is configured to dynamically select a cache coherence protocol (i.e., either the write invalidate protocol or the write update protocol) to use for a given memory store operation based on one or more protocol preference indicators provided by one or more of a master PE among the PEs <NUM>(<NUM>)-<NUM>(P), at least one snooper PE among the PEs <NUM>(<NUM>)-<NUM>(P), and the COP <NUM> itself. The selection of a cache coherence protocol is performed by the COP <NUM> on a store-by-store basis, such that different cache coherence protocols may be selected for successive memory store operations. Accordingly, instead of supporting only one cache coherence protocol (as is the case with many conventional processor-based devices), the processor-based device <NUM> is configured to support both the write invalidate protocol and the write update protocol.

In some embodiments, the PEs <NUM>(<NUM>)-<NUM>(P) and the COP <NUM> may be configured to provide one or more protocol preference indicators based on circumstantial knowledge available to each. For example, upon executing a memory store instruction ("MEM STORE INSTR") <NUM>, the PE <NUM>(<NUM>), acting as a master PE, may predict that the write invalidate protocol is preferred because the PE <NUM>(<NUM>) is aware that it will be performing subsequent multiple memory store operations to a coherence granule such as the coherence granule <NUM>(<NUM>). Similarly, the COP <NUM> may determine that a number of the PEs <NUM>(<NUM>)-<NUM>(P) holding local cached copies <NUM>, <NUM>, and <NUM> of a highly shared and contentious coherence granule exceeds an agent threshold <NUM>, and thus may predict that the write update protocol is preferred. Based on the one or more protocol preference indicators received by the COP <NUM>, the COP <NUM> dynamically selects the cache coherence protocol, and then communicates the selected cache coherence protocol to the PEs <NUM>(<NUM>)-<NUM>(P). The logic for generating, providing, and evaluating such protocol preference indicators may be embodied in prediction logic circuits <NUM>(<NUM>)-<NUM>(P) of the PEs <NUM>(<NUM>)-<NUM>(P) and/or in the prediction logic circuit <NUM> of the COP <NUM>, as non-limiting examples.

To illustrate communication flows among elements of the processor-based device <NUM> of <FIG> for generating and providing protocol preference indicators and dynamically selecting the cache coherence protocol, <FIG> are provided. Elements of <FIG> are referenced in describing <FIG> for the sake of clarity. As seen in <FIG>, a message flow diagram <NUM> shows the master PE <NUM>(<NUM>), the snooper PEs <NUM>(<NUM>) and <NUM>(P), and the COP <NUM> represented by vertical lines, with communications between these elements illustrated by captioned arrows. It is to be understood that the PE <NUM>(<NUM>) is referred to as a "master PE" and the PEs <NUM>(<NUM>) and <NUM>(P) are referred to as "snooper PEs" only for purposes of illustration, and that each of the PEs <NUM>(<NUM>)-<NUM>(P) may operate as either a master PE or a snooper PE depending on its role in a particular memory store operation. It is to be further understood that not all of the operations illustrated in <FIG> may be performed by all embodiments.

In <FIG>, operations begin with the master PE <NUM>(<NUM>), in response to a memory store operation performed by the master PE <NUM>(<NUM>), predicting whether the write invalidate protocol is preferred, as indicated by block <NUM>. Generally speaking, the master PE <NUM>(<NUM>) may defer to other agents (such as the snooper PEs <NUM>(<NUM>) and <NUM>(P), the COP <NUM>, hints provided by software, and the like, as non-limiting examples) to determine whether the write update protocol is preferred. However, the master PE <NUM>(<NUM>) in some circumstances may predict that the write update protocol would be disadvantageous, and that the write invalidate protocol is preferred. For example, the master PE <NUM>(<NUM>) in some embodiments may determine that the memory store operation will be one of a plurality of memory store operations to a same coherence granule (e.g., the coherence granule <NUM>(<NUM>) of <FIG>), and thus the write invalidate protocol is preferred. Some embodiments of the master PE <NUM>(<NUM>) may further predict that the write invalidate protocol is preferred by determining that the memory store operation will not comprise an atomic read-modify-write operation to the coherence granule <NUM>(<NUM>). Note that if the memory store operation did involve an atomic read-modify-write operation, the master PE <NUM>(<NUM>) likely would prefer the write update protocol because the master PE <NUM>(<NUM>) would probably be communicating with other executing threads using a shared memory variable.

In some embodiments, the master PE <NUM>(<NUM>) may base its prediction on software-provided hints (communicated via, e.g., an opcode hint added to a memory store instruction, a page table attribute, or an address range register, as non-limiting examples). For instance, the use of some high-level software constructs, such as C++ atomic variables and Java volatile variables, may indicate that memory addresses associated with such constructs are used for shared memory communications between software threads. If the master PE <NUM>(<NUM>) performs the memory store operation to a memory address associated with such constructs, it may be inferred that the snooper PEs <NUM>(<NUM>) and <NUM>(P) likely would need to perform subsequent memory load operations if the memory store operation resulted in the invalidation of local cached copies. Thus, if the master PE <NUM>(<NUM>) detects a software-provided hint, the master PE <NUM>(<NUM>) may predict that the write invalidate protocol is not preferred in those circumstances.

Based on its prediction, the master PE <NUM>(<NUM>) sends a cache coherence bus command <NUM> to the COP <NUM> indicating its preferred cache coherence protocol, as indicated by arrow <NUM>. The cache coherence bus command <NUM> comprises a prevent-write-update attribute <NUM> that is asserted or deasserted by the master PE <NUM>(<NUM>) to indicate its preference to the COP <NUM>. As seen in <FIG>, the prevent-write-update attribute <NUM> represents one possible embodiment of a protocol preference indicator <NUM>, and may be generally referred to as such herein. In some embodiments, a prediction by the master PE <NUM>(<NUM>) that the write invalidate protocol is preferred will be treated as definitive by the COP <NUM>, allowing the master PE <NUM>(<NUM>) to disallow the use of the write update protocol for a given memory store operation. Thus, as discussed in greater detail with respect to <FIG>, if the master PE <NUM>(<NUM>) in such embodiments sends the cache coherence bus command <NUM> to the COP <NUM> with the prevent-write-update attribute <NUM> asserted, the COP <NUM> sends a response message to the master PE <NUM>(<NUM>) and the snooper PEs <NUM>(<NUM>) and <NUM>(P) indicating that the write invalidate protocol is selected.

In some embodiments, the cache coherence bus command <NUM> may comprise a non-allocating-write bus command that is sent by the master PE <NUM>(<NUM>) responsive to a cache miss on the cache <NUM>(<NUM>), where the memory store operation is not write-allocating in the cache <NUM>(<NUM>) of the master PE <NUM>(<NUM>). Some embodiments may provide that the cache coherence bus command <NUM> comprises a read-with-intent-to-write bus command that is sent by the master PE <NUM>(<NUM>) responsive to a cache miss on the cache <NUM>(<NUM>), where the memory store operation is write-allocating in the cache <NUM>(<NUM>) of the master PE <NUM>(<NUM>). According to some embodiments, the cache coherence bus command <NUM> may comprise a promote-to-writeable bus command that is sent by the master PE <NUM>(<NUM>) responsive to a cache hit on the cache <NUM>(<NUM>), where the cache line (e.g., the cache line <NUM>(<NUM>), as a non-limiting example) is held in a shared coherence state.

Upon receiving the cache coherence bus command <NUM> from the master PE <NUM>(<NUM>), the COP <NUM> next makes its own prediction regarding whether the write update protocol is preferred, as indicated by block <NUM>. Some embodiments may provide that prediction by the COP <NUM> is based on whether or not the prevent-write-update attribute <NUM> of the cache coherence bus command <NUM> is asserted. In some embodiments, the COP <NUM> may base its prediction on how many of the PEs <NUM>(<NUM>)-<NUM>(P) hold local cached copies (e.g., the local cached copies <NUM>, <NUM>, and <NUM> of <FIG>) of the coherence granule <NUM>(<NUM>) to be written by the memory store operation. If the number of PEs <NUM>(<NUM>)-<NUM>(P) holding the local cached copies <NUM>, <NUM>, and <NUM> exceeds the agent threshold <NUM>, the COP <NUM> in such embodiments will predict that the write update protocol is preferred for servicing the memory store operation. In some embodiments, the number of PEs <NUM>(<NUM>)-<NUM>(P) holding the local cached copies <NUM>, <NUM>, and <NUM> may be determined by the COP <NUM> consulting the snoop filter <NUM> of <FIG> or another snoop directory (not shown) of the processor-based device <NUM>.

After making its prediction, the COP <NUM> sends a snoop command <NUM> to the snooper PEs <NUM>(<NUM>) and <NUM>(P), as indicated by arrows <NUM> and <NUM>, respectively. The snoop command <NUM> comprises a write-update-requested attribute <NUM> that is asserted or deasserted by the COP <NUM> to indicate its cache coherence protocol preference to the snooper PEs <NUM>(<NUM>) and <NUM>(P). As noted above, in some embodiments, the COP <NUM> may deassert the write-update-requested attribute <NUM> if the master PE <NUM>(<NUM>) sends the cache coherence bus command <NUM> with the prevent-write-update attribute <NUM> asserted. It is to be understood that, as shown in <FIG>, the write-update-requested attribute <NUM> represents another possible embodiment of the protocol preference indicator <NUM>, and thus may be generally referred to as such herein. Operations then resume in <FIG>.

Referring now to <FIG>, each of the snooper PEs <NUM>(<NUM>) and <NUM>(P) may also independently predict whether the write update protocol is preferred, as indicated by blocks <NUM> and <NUM>, respectively. In this manner, the snooper PEs <NUM>(<NUM>) and <NUM>(P) may acknowledge participation in or opt out of a requested write update (as indicated by the write-update-requested attribute <NUM> of the snoop command <NUM> being asserted), or may request the write update protocol if the write-update-requested attribute <NUM> of the snoop command <NUM> is deasserted. In the former case, if the write-update-requested attribute <NUM> of the snoop command <NUM> is asserted by the COP <NUM>, each of the snooper PEs <NUM>(<NUM>) and <NUM>(P) may default to using the write update protocol unless it determines that a reason exists to opt out. As non-limiting examples, a snooper PE such as the snooper PEs <NUM>(<NUM>) and <NUM>(P) may decide to opt out of the use of the write update protocol because the snooper PE is unwilling to receive write update data due to a lack of resources or due to operating in a configuration in which reception of write update data is disabled. Conversely, if the write-update-requested attribute <NUM> of the snoop command <NUM> is deasserted by the COP <NUM>, each of the snooper PEs <NUM>(<NUM>) and <NUM>(P) may still request the write update protocol based on its own prediction of the benefits of using the write update protocol.

According to some embodiments, the snooper PEs <NUM>(<NUM>) and <NUM>(P) each may base their respective predictions regarding whether the write update protocol is preferred on the likelihood of rereading the coherence granule <NUM>(<NUM>) that is to be written by the memory store operation. If so, the snooper PEs <NUM>(<NUM>) and <NUM>(P) would indicate a preference for the write update protocol. In some embodiments, the snooper PEs <NUM>(<NUM>) and <NUM>(P) each may determine the likelihood of rereading the coherence granule <NUM>(<NUM>) based on a position of the local cached copies <NUM> and <NUM> in the caches <NUM>(<NUM>) and <NUM>(P), respectively, as determined by the cache replacement policies of the caches <NUM>(<NUM>) and <NUM>(P). For example, if the cache <NUM>(<NUM>) uses a Least Recently Used (LRU) replacement policy, the snooper PE <NUM>(<NUM>) may determine that it is likely to reread the coherence granule <NUM>(<NUM>) if the cache line <NUM>(<NUM>) is installed between a most-recently-used cache line and the halfway point between the most-recently-used cache line and the least-recently-used cache line in the cache <NUM>(<NUM>).

Some embodiments may provide that the snooper PEs <NUM>(<NUM>) and <NUM>(P) each may determine the likelihood of rereading the coherence granule <NUM>(<NUM>) by determining whether the local cached copies <NUM> and <NUM> are held in an exclusive state at the time the corresponding snooper PEs <NUM>(<NUM>) and <NUM>(P) receive the snoop command <NUM> from the COP <NUM>. In some embodiments, the snooper PEs <NUM>(<NUM>) and <NUM>(P) each may determine the likelihood of rereading the coherence granule <NUM>(<NUM>) by determining whether the local cached copies <NUM> and <NUM> are held in a modified or owned state, but the corresponding snooper PEs <NUM>(<NUM>) or <NUM>(P) have not written to the coherence granule <NUM><NUM>(<NUM>). In either case, if the determinations are true, the snooper PEs <NUM>(<NUM>) and <NUM>(P) are likely to be communicating with other software threads via a shared memory variable, and thus would predict the write update protocol to be the preferred cache coherence protocol.

After predicting whether the write update protocol is preferred, the snooper PEs <NUM>(<NUM>) and <NUM>(P) send snoop replies <NUM> and <NUM>, respectively, to the COP <NUM>, as indicated by arrows <NUM> and <NUM>. The snoop replies <NUM> and <NUM> comprise write-update-requested attributes <NUM> and <NUM>, respectively, which are asserted or deasserted depending on whether or not the corresponding snooper PEs <NUM>(<NUM>) and <NUM>(P) predicted the write update protocol to be preferred. It is to be understood that, as shown in <FIG>, the write-update-requested attributes <NUM> and <NUM> represent further possible embodiments of the protocol preference indicator <NUM>, and thus may be generally referred to as such herein. Operations then resume in <FIG>.

Turning now to <FIG>, upon receiving the snoop replies <NUM> and <NUM>, the COP <NUM> in some embodiments may then determine whether either of the snoop replies <NUM> and <NUM> comprises an asserted write-update-requested attribute <NUM> or <NUM>, respectively, as indicated by block <NUM>. Assuming that the master PE <NUM>(<NUM>) has not precluded the use of the write update protocol (i.e., by asserting the prevent-write-update attribute <NUM> to indicate that the write invalidate protocol will be selected), the COP <NUM> will then generate a response message <NUM> with a write-update-valid attribute <NUM> that is asserted or deasserted based on the write-update-requested attributes <NUM> and <NUM>, and will send the response message <NUM> to the master PE <NUM>(<NUM>) and the snooper PEs <NUM>(<NUM>) and <NUM>(P), as indicated by arrows <NUM>, <NUM>, and <NUM>, respectively. Because the snooper PEs <NUM>(<NUM>) and <NUM>(P) independently determine whether the write update protocol is preferred, it may be possible for both of the write-update-requested attributes <NUM> and <NUM> to be asserted, for only one of the two to be asserted, or for both to be deasserted. If any one of the write-update-requested attributes <NUM> and <NUM> are asserted (and the prevent-write-update attribute <NUM> of the cache coherence bus command <NUM> sent by the master PE <NUM>(<NUM>) was not asserted), the COP <NUM> will assert the write-update-valid attribute <NUM> of the response message <NUM>. However, if both of the write-update-requested attributes <NUM> and <NUM> are deasserted (or if the prevent-write-update attribute <NUM> of the cache coherence bus command <NUM> sent by the master PE <NUM>(<NUM>) was asserted), the COP <NUM> will deassert the write-update-valid attribute <NUM> of the response message <NUM>.

The write-update-valid attribute <NUM> of the response message <NUM> indicates to the master PE <NUM>(<NUM>) and the snooper PEs <NUM>(<NUM>) and <NUM>(P) the cache coherence protocol that will be selected by the COP <NUM> for the memory store operation. Upon receiving the response message <NUM> with the write-update-valid attribute <NUM> asserted, the master PE <NUM>(<NUM>) will perform the write update by sending data to the snooper PEs <NUM>(<NUM>),<NUM>(P) for use in updating their local cached copies <NUM> and <NUM>, respectively. Likewise, upon receiving the response message <NUM> with the write-update-valid attribute <NUM> asserted, any of the snooper PEs <NUM>(<NUM>), <NUM>(P) whose snoop reply <NUM>, <NUM> included the write-update-requested attribute <NUM>, <NUM> asserted will prepare to receive write update data from the master PE <NUM>(<NUM>). Any of the snooper PEs <NUM>(<NUM>), <NUM>(P) whose snoop reply <NUM>, <NUM> included the write-update-requested attribute <NUM>, <NUM> deasserted will ignore the write-update-valid attribute <NUM> in the response message <NUM>, and will perform a write invalidate.

The mechanism for dynamic selection of cache coherence protocols described herein allows either the write invalidate protocol or the write update protocol to be selected on a store-by-store basis by the COP <NUM> based on input from one or more of the master PE <NUM>(<NUM>), the snooper PEs <NUM>(<NUM>) and <NUM>(P), and the COP <NUM> itself. In this manner, the cache coherence protocol providing the best performance and/or the lowest energy consumption may be employed for each memory store operation that finds a cached copy of a coherence granule in another PE <NUM>(<NUM>)-<NUM>(P).

To illustrate exemplary operations for providing dynamic selection of cache coherence protocols according to some embodiments, <FIG> provides a flowchart <NUM>. For the sake of clarity, elements of <FIG> and <FIG> are referenced in describing <FIG>. Operations in <FIG> begin with the master PE <NUM>(<NUM>) of the plurality of PEs <NUM>(<NUM>)-<NUM>(P) of the processor-based device <NUM> sending the cache coherence bus command <NUM> to the COP <NUM> of the processor-based device <NUM> as part of a memory store operation (block <NUM>). Responsive to receiving the cache coherence bus command <NUM>, the COP <NUM> dynamically selects, on a store-by-store basis, one of a write invalidate protocol and a write update protocol as a cache coherence protocol to use for maintaining cache coherency, based on one or more protocol preference indicators <NUM> provided by one or more of the master PE <NUM>(<NUM>), at least one snooper PE <NUM>(<NUM>), <NUM>(P) of the plurality of PEs <NUM>(<NUM>)-<NUM>(P), and the COP <NUM> (block <NUM>). The COP <NUM> then sends the response message <NUM> to each of the master PE <NUM>(<NUM>) and the at least one snooper PE <NUM>(<NUM>), <NUM>(P) indicating the selected cache coherence protocol (block <NUM>).

<FIG> provides a flowchart <NUM> illustrating further exemplary operations of the master PE <NUM>(<NUM>) of <FIG> and <FIG> for predicting that a write invalidate protocol is preferred, and providing protocol preference indicators <NUM> to the COP <NUM>, according to one embodiment. Elements of <FIG> and <FIG> are referenced in describing <FIG> for the sake of clarity. In <FIG>, operations begin with the master PE <NUM>(<NUM>) predicting that the write invalidate protocol is preferred (block <NUM>). In some embodiments, the operations of block <NUM> for predicting that the write invalidate protocol is preferred may comprise the master PE <NUM>(<NUM>) predicting that the memory store operation will be one of a plurality of memory store operations to a same coherence granule (e.g., the coherence granule <NUM>(<NUM>), as a non-limiting example) (block <NUM>). Some embodiments may provide that the operations of block <NUM> for predicting that the write invalidate protocol is preferred comprise the master PE <NUM>(<NUM>) predicting that the memory store operation will not comprise an atomic read-modify-write operation (block <NUM>). According to some embodiments, the operations of block <NUM> for predicting that the write invalidate protocol is preferred may be based on a software-provided hint (block <NUM>).

Responsive to predicting that the write invalidate protocol is preferred, the master PE <NUM>(<NUM>) asserts the prevent-write-update attribute <NUM> of the cache coherence bus command <NUM> (block <NUM>). The COP <NUM>, in response to receiving the cache coherence bus command <NUM> with the prevent-write-update attribute <NUM> of the cache coherence bus command <NUM> asserted, sends the response message <NUM> to each of the master PE <NUM>(<NUM>) and the at least one snooper PE <NUM>(<NUM>), <NUM>(P) comprising a deasserted write-update-valid attribute <NUM> indicating that the write invalidate protocol will be selected for the memory store operation (block <NUM>).

To illustrate exemplary operations of the COP <NUM> of <FIG> for predicting that a write update protocol is preferred according to one embodiment, <FIG> provides a flowchart <NUM>. For the sake of clarity, elements of <FIG> and <FIG> are referenced in describing <FIG>. Operations in <FIG> begin with the COP <NUM> predicting that the write update protocol is preferred (block <NUM>). In some embodiments, the operations of block <NUM> for predicting that the write update protocol is preferred may comprise determining that a count of the master PE <NUM>(<NUM>) and the at least one snooper PE <NUM>(<NUM>), <NUM>(P) holding the local cached copy <NUM>, <NUM>, <NUM> of the coherence granule <NUM>(<NUM>) to be written by the memory store operation exceeds an agent threshold <NUM> (block <NUM>). Responsive to predicting that the write update protocol is preferred, the COP <NUM> asserts the write-update-requested attribute <NUM> of the snoop command <NUM> (block <NUM>).

<FIG> and <FIG> provide a flowchart <NUM> illustrating exemplary operations of the snooper PEs <NUM>(<NUM>) and <NUM>(P) of <FIG> and <FIG> for predicting that a write update protocol is preferred, and providing protocol preference indicators <NUM> to the COP <NUM>, according to one embodiment. In aspects according to <FIG> and <FIG>, it is assumed that the cache coherence bus command <NUM> sent by the master PE <NUM>(<NUM>) to the COP <NUM> with its prevent-write-update attribute <NUM> deasserted, thus allowing the COP <NUM> and the snooper PEs <NUM>(<NUM>) and <NUM>(P) to make their own predictions regarding the preferred cache coherence protocol. Elements of <FIG> and <FIG> are referenced in describing <FIG> and <FIG> for the sake of clarity. In <FIG>, operations begin with a snooper PE, such as the snooper PE <NUM>(<NUM>), predicting that the write update protocol is preferred (block <NUM>). In some embodiments, the operations of block <NUM> for predicting that the write update protocol is preferred may comprise predicting that the snooper PE <NUM>(<NUM>) is likely to reread the coherence granule <NUM>(<NUM>) to be written by the memory store operation (block <NUM>). The snooper PE <NUM>(<NUM>) in some embodiments may predict that the snooper PE <NUM>(<NUM>) is likely to reread the coherence granule <NUM>(<NUM>) based on a position of the local cached copy <NUM> in the cache <NUM>(<NUM>) as determined by the cache replacement policies of the cache <NUM>(<NUM>). Some embodiments may provide that the snooper PE <NUM>(<NUM>) may predict that the snooper PE <NUM>(<NUM>) is likely to reread the coherence granule <NUM>(<NUM>) by determining that the local cached copy <NUM> is held in an exclusive state at the time the snooper PE <NUM>(<NUM>) receives the snoop command <NUM> from the COP <NUM>, or by determining that the local cached copy <NUM> is held in a modified or owned state but the snooper PEs <NUM>(<NUM>) has not written to the coherence granule <NUM>(<NUM>).

Responsive to predicting that the write update protocol is preferred, the snooper PE <NUM>(<NUM>) asserts the write-update-requested attribute <NUM> of the snoop reply <NUM> (block <NUM>). The COP <NUM> subsequently receives at least one snoop reply <NUM>, <NUM> corresponding to the at least one snooper PE <NUM>(<NUM>), <NUM>(P) (block <NUM>). The COP <NUM> then determines whether any snoop reply of the at least one snoop reply <NUM>, <NUM> comprises an asserted write-update-requested attribute <NUM>, <NUM> (block <NUM>). If not, the COP <NUM> sends the response message <NUM> to each of the master PE <NUM>(<NUM>) and the at least one snooper PE <NUM>(<NUM>), <NUM>(P) comprising the deasserted write-update-valid attribute <NUM> indicating that the write invalidate protocol will be selected for the memory store operation (block <NUM>). If the COP <NUM> determines at decision block <NUM> that any of the at least one snoop reply <NUM>, <NUM> comprises an asserted write-update-requested attribute <NUM>, <NUM>, processing resumes at block <NUM> in <FIG>.

Referring now to <FIG>, the COP <NUM> sends the response message <NUM> to each of the master PE <NUM>(<NUM>) and the at least one snooper PE <NUM>(<NUM>), <NUM>(P) comprising an asserted write-update-valid attribute <NUM> indicating that the write update protocol will be selected for the memory store operation (block <NUM>). In some embodiments, upon receiving the response message <NUM> comprising the asserted write-update-valid attribute <NUM>, each snooper PE of the at least one snooper PE <NUM>(<NUM>), <NUM>(P) that corresponds to a snoop reply of the at least one snoop reply <NUM>, <NUM> comprising an asserted write-update-requested attribute <NUM>, <NUM> may perform a write update operation (block <NUM>). Likewise, each snooper PE of the at least one snooper PE <NUM>(<NUM>), <NUM>(P) that corresponds to a snoop reply of the at least one snoop reply <NUM>, <NUM> comprising a deasserted write-update-requested attribute <NUM>, <NUM> may perform a write invalidate operation responsive to the response message <NUM> comprising the asserted write-update-valid attribute <NUM> (block <NUM>).

<FIG> is a block diagram of an exemplary processor-based device <NUM>, such as the processor-based device <NUM> of <FIG>, that provides dynamic selection of cache coherence protocols. 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 device(s) <NUM>, one or more output device(s) <NUM>, a modem <NUM>, and one or more display controller(s) <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 display(s) <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> 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.

Claim 1:
A processor-based device (<NUM>), comprising:
a plurality of processing elements (PE) (<NUM>(<NUM>)-<NUM>(P)) comprising a master PE (<NUM>(<NUM>)) and at least one snooper PE (<NUM>(<NUM>), <NUM>(P)); and
a central ordering point (COP) (<NUM>);
the master PE configured to send (<NUM>) a cache coherence bus command (<NUM>) to the COP as part of a memory store operation;
wherein a snooper PE refers to a PE that receives snoop commands associated with the memory store operation from the COP and then acts on the snoop commands to maintain cache coherence and
the COP configured to:
responsive to receiving the cache coherence bus command sent by the master PE, dynamically select (<NUM>), on a store-by-store basis, one of a write invalidate protocol and a write update protocol as a cache coherence protocol to use for maintaining cache coherency, based on one or more protocol preference indicators (<NUM>) provided by one or more of the master PE, the at least one snooper PE, and the COP; and
send (<NUM>) a response message (<NUM>) to each of the master PE and the at least one snooper PE indicating the selected cache coherence protocol, wherein the response message sent to the at least one snooper is sent as a snoop command.