# Patent

## Title
Systems and methods for non-blocking implementation of cache flush instructions

## Abstract

Systems and methods for non-blocking implementation of cache flush instructions are disclosed. As a part of a method, data is accessed that is received in a write-back data holding buffer from a cache flushing operation, the data is flagged with a processor identifier and a serialization flag, and responsive to the flagging, the cache is notified that the cache flush is completed. Subsequent to the notifying, access is provided to data then present in the write-back data holding buffer to determine if data then present in the write-back data holding buffer is flagged.

## Background
CROSS-REFERENCE TO RELATED APPLICATION
This application is a continuation of U.S. application Ser.No. 13/649,532, filed Oct. 11, 2012 (now U.S. Pat. No. 9,678,882, issued Jun. 13, 2017), which is hereby incorporated by reference.


TECHNICAL FIELD
Modern microprocessors operate much faster than associated memories where program data is kept. In particular, main memories operate much slower than do modern microprocessors. Because of this, program data may not be able to be read fast enough to keep a microprocessor busy. Moreover, the performance gap creates a bottleneck that is the source of latency. Cache memory is used to help ameliorate the performance gap that exists between processors and main memory. Cache memory is memory that is smaller in storage capacity than main memory, but is memory that can be accessed much more quickly than can main memory.
As such, cache memory is used by the central processing unit of a computer to reduce the time that it takes to access data and instructions associated with the execution of an application. Cache memory is small, high speed memory, usually static RAM, which stores copies of data and instructions accessed from the most recently used main memory locations. As long as data and instructions are accessed from cached memory locations, the latency associated with data and instruction accesses is that of cache memory accesses as opposed to being that of main memory accesses, which are much slower. Cache memory improves latency by decreasing the time that it takes to move information to and from the processor.
Cache flushing is the intentional removal of information from a cache. Individual modified or dirty cache lines can be evicted from a cache and written into main memory in an operation called a write-back. The write-back updates the version of the cache line that is stored in main memory. A write-back may result from actions in either hardware or software. If the write-back was initiated by software, as a result of the execution of a cache flush instruction, after the processor finishes the write-backs, it then generates a special bus cycle called a flush acknowledge cycle.
In conventional processors, when a flush of data from a cache is requested, the processor is stalled until the flush of data to main memory or the next level of cache is completed. As such, latency that is attributable to the period during which the processor waits for the write backs to complete is incurred. Accordingly, some conventional processors exhibit an unsatisfactory latency that is attributable to the waiting period that is associated with write-backs to main memory (or other locations).
SUMMARY
Conventional processors exhibit an unsatisfactory latency that is attributable to the waiting period that is associated with data write-backs. A method for non-blocking implementation of cache flush instructions is disclosed that addresses these shortcomings. However, the claimed embodiments are not limited to implementations that address any or all of the aforementioned shortcomings. As a part of a method, data is accessed that is received in a write-back data holding buffer from a cache flushing operation, the data is flagged with a processor identifier and a serialization flag, and responsive to the flagging, the processor executing the cache flush instruction is prematurely/expediently notified that the cache flush operation is completed. Subsequent to such notification, access is provided to data then present in the write-back data holding buffer to determine if data then present in the write-back data holding buffer is flagged. The aforementioned methodology does not require a waiting period during which the processor waits (e.g., is stalled) for write-backs to complete. Accordingly, the aforementioned methodology avoids unsatisfactory latency that is attributable to the waiting period that is associated with data flushes in conventional processors.



BRIEF DESCRIPTION OF THE DRAWINGS
The invention, together with further advantages thereof, may best be understood by reference to the following description taken in conjunction with the accompanying drawings in which:
FIG. 1A shows an exemplary operating environment of a system for non-blocking implementation of cache flush instructions according to one embodiment.
FIG. 1B shows how the data that is temporarily held in the data holding buffer is tagged and thereafter an indicator that the data has been completely flushed to a main memory/next level cache/private memory of a device is provided to L2 cache.
FIG. 1C illustrates how the flagging of data enables data associated with a specific processor core and a specific cache flush to be distinguished from other data that is associated with other processor cores and cache flushes that can be extant on a chip.
FIG. 1D illustrates operations performed by system for non-blocking implementation of cache flush instructions according to one embodiment.
FIG. 2 shows components of a system for non-blocking implementation of cache flush instructions according to one embodiment.
FIG. 3 shows a flowchart of the steps performed in a method for non-blocking implementation of cache flush instructions according to one embodiment.



It should be noted that like reference numbers refer to like elements in the figures.
DETAILED DESCRIPTION
Although the present invention has been described in connection with one embodiment, the invention is not intended to be limited to the specific forms set forth herein. On the contrary, it is intended to cover such alternatives, modifications, and equivalents as can be reasonably included within the scope of the invention as defined by the appended claims.
In the following detailed description, numerous specific details such as specific method orders, structures, elements, and connections have been set forth. It is to be understood however that these and other specific details need not be utilized to practice embodiments of the present invention. In other circumstances, well-known structures, elements, or connections have been omitted, or have not been described in particular detail in order to avoid unnecessarily obscuring this description.
References within the specification to “one embodiment” or “an embodiment” are intended to indicate that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. The appearance of the phrase “in one embodiment” in various places within the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. Moreover, various features are described which may be exhibited by some embodiments and not by others. Similarly, various requirements are described which may be requirements for some embodiments but not other embodiments.
Some portions of the detailed descriptions, which follow, are presented in terms of procedures, steps, logic blocks, processing, and other symbolic representations of operations on data bits within a computer memory. These descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. A procedure, computer executed step, logic block, process, etc., is here, and generally, conceived to be a self-consistent sequence of steps or instructions leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals of a computer readable storage medium and are capable of being stored, transferred, combined, compared, and otherwise manipulated in a computer system. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.
It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present invention, discussions utilizing terms such as “receiving” or “accessing” or “flagging” or “notifying” or the like, refer to the action and processes of a computer system, or similar electronic computing device that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories and other computer readable media into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.
Exemplary Operating Environment of a System for Non-Blocking Implementation of Cache Flush Instructions According to One Embodiment
FIG. 1A shows an exemplary operating environment 100 of a system 101 for non-blocking implementation of cache flush instructions according to one embodiment. System 101 accesses data received by a write-back data holding buffer as a result of software initiated cache flushing operations, flags the data and notifies the cache that a write-back of the data to main memory/next level cache/private memory of device has completed before the write-back of the data to main memory/next level cache/private memory of device has actually completed. Subsequently, access to the write-back data holding buffer is provided to a serialization operation to determine if data that is then present in the write-back data holding buffer has been flagged. System 101 enables an efficient flushing of L2 cache, such that processor stalls, that are attributable to a necessity to wait for write-backs to main memory/next level cache/private memory of device to complete, before making L2 cache available for new/fresh data, are prevented. FIG. 1A shows system 101, cache controller 102, L1 cache 103, CPU 105, L2 cache 107, WDHB (write-back data holding buffer) 109, main memory/next level cache/private memory of device 111 and system interface 113.
Referring to FIG. 1A, L1 cache 103 is a level 1 cache and L2 cache 107 is a level 2 cache. In one embodiment, when a software based request is made to flush modified data from L2 cache 107, a copy of the modified data is written back to main memory/next level cache/private memory of device 111, replacing the old data located therein. In one embodiment, when a request to flush data from L2 cache 107 is made the data is flushed from L2 cache 107 into WDHB 109. In one embodiment, an indicator that the data has been flushed to main memory/next level cache/private memory of device 111 is provided to L2 cache 107 when the data is flushed into WDHB 109. The processor is then freed to receive new/fresh instructions that are needed by the software executing on the processor. In this manner, because requests to flush data typically involve blocking instructions, the blocking instruction is removed and the processor is not forced to wait until the write-back of the data to main memory/next level cache/private memory of device is actually completed before it can resume processing new requests. In conventional systems, it can take several hundred cycles for flushed data to reach main memory/next level cache/private memory of device 111. Accordingly, in exemplary embodiments, processor stalls that are attributable to such delays are avoided.
WDHB 109 receives data that is flushed from L2 cache 107 based on a software based request to flush the data to main memory/next level cache/private memory of device. WDHB 109 is a temporary data holding buffer that temporarily holds data that is in the process of being flushed from L2 cache 107 to main memory/next level cache/private memory of a device 111. In one embodiment, as shown in FIG. 1B, the flushed data that is temporarily held in WDHB 109 is flagged (e.g., with a processor identifier and a serialization flag). And, thereafter an indicator that the data has been completely flushed to main memory/next level cache/private memory of a device 111 is provided to L2 cache 107 (e.g., a write-back acknowledgement is provided to L2 cache 107 in response to the flagging and before the data is actually written back to main memory/next level cache/private memory of a device).
In one embodiment, as illustrated in FIG. 10, the flagging enables data associated with a specific processor core (e.g., one of P0-P3) and a specific flush (e.g., one of CF0-CF3) to be distinguished from other data in WDHB 109 that is associated with other processor cores and flushes that can be extant on a chip. In this manner a serialization operation (e.g., one of SIO-SI3) can readily identify data held in WDHB 109 that is associated with a corresponding processor core and data flush request, and can operate to block the execution of subsequent instructions in the software that includes the serialization instruction, until the write-back of the identified data is completed. In one embodiment, because the execution of the instructions that are executed, after the flush request is executed, and before the serialization instruction is executed, can take many cycles, the data that is caused to be flushed by a flush request is typically already written back to main memory/next level cache/private memory of a device 111 at the point in time when the serialization instruction is executed (see flushed data P0, CF0 in FIG. 1C); the data that is temporarily held in WDHB 109 having been forwarded to main memory/next level cache/private memory of a device 111 when the forwarding of the data to main memory/next level cache/private memory of device is approved by the interconnect fabric.
Referring again to FIG. 1A, system 101 accesses data that is received by WDHB 109 as a result of a cache flushing operation (as illustrated in FIG. 1B). The data that is placed into WDHB 109 is flagged by system 101 with a processor identifier and a serialization flag (as illustrated in FIG. 1B). Prior to the completion of the flush of the data to main memory/next level cache/private memory of device and responsive to the flagging of the data, a cache completion indicator is provided by system 101 to L2 cache 107 (as illustrated in FIG. 1B). Subsequently, system 101 provides access to data held in WDHB 109 to determine if data that is then present therein is flagged (see above discussion). In one embodiment, system 101 can be located in cache controller 102. In other embodiments, system 101 can be separate from cache controller 102 but operate cooperatively therewith.
Main Memory/Next Level Cache/Private Memory of Device 111 stores data that is flushed from L2 cache 107 to main memory/next level cache/private memory of device 111 via WDHB 109. Having been placed into WDHB 109 to avoid blocking the ingress of data into L2 cache 107, data is moved to main memory/next level cache/private memory of device 111 when the interconnect fabric authorizes the forwarding of the data from WDHB 109. The data that is flushed to main memory/next level cache/private memory of device from L2 cache 107 updates the data that is stored in the involved address of main memory/next level cache/private memory of device 111. Also shown in FIG. 1A is system interface 113.
Operation
FIG. 1D illustrates operations performed by system 101 for non-blocking implementation of cache flush instructions according to one embodiment. These operations, which relate to the implementation of cache flush instructions are illustrated for purposes of clarity and brevity. It should be appreciated that other operations not illustrated by FIG. 1D can be performed in accordance with one embodiment.
Referring to FIG. 1D, at A, a software based cache flush request is made. In one embodiment, the software based cache flush request is implemented as an instruction that is a part of the software. In one embodiment, the instruction causes the flushing of modified data from L2 cache 107 that is to be written back to main memory/next level cache/private memory of device 111.
At B, data is flushed from L2 cache 107 and forwarded to WDHB 109. In one embodiment, WDHB 109 has an 8 entry data holding capacity. In other embodiments, WDHB 109 can have other data holding capacities.
At C, system 101 accesses the data that is received by WDHB 109 and flags the data with a processor identifier and a serialization flag. In one embodiment, the processor identifier and the serialization flag refer to a specific processor and a specific cache flush.
At D, responsive to the flagging of the data, L2 cache 107 is notified that the cache flush has been completed (that the data has been written back to main memory/next level cache/private memory of device 111). In one embodiment, L2 cache 107 is notified that that the cache flush has been completed, in response to the flagging of the data and before the data is actually written-back to main memory/next level cache/private memory of device 111.
At E, the data that is flushed from L2 cache 107 is written-back to main memory/next level cache/private memory of device 111. At F, access to the contents of the write-back data holding buffer is provided to a serialization instruction in the software program that initiated the cache flush request. The serialization instruction ensures that the write-back of data is completed before subsequent instructions in the software program can be executed. The serialization operation uses the flags to identify data held in WDHB 109 that is associated with a specific processor core and data flush request, and blocks the execution of subsequent instructions, until the write-back of the identified data is completed.
Components of System for Non-Blocking Implementation of Cache Flush Instructions According to One Embodiment
FIG. 2 shows components of a system 101 for non-blocking implementation of cache flush instructions according to one embodiment. In one embodiment, components of system 101 implement an algorithm for non-blocking implementation of cache flush instructions. In the FIG. 2 embodiment, components of system 101 include data accessor 201, data flagger 203, cache notifier 205 and access provider 207.
Referring to FIG. 2, data accessor 201 accesses data that is received by a write-back data holding buffer (e.g., WDHB 109 in FIG. 1A) as part of a cache flushing operation. In one embodiment, the data is that is received is received from L2 cache (e.g., 107 in FIG. 1A) en route to main memory/next level cache/private memory of device (e.g., 111 in FIG. 1A). In one embodiment, the write-back data holding buffer temporarily holds the data until the interconnect fabric indicates that the data that is being temporarily held in the write-back holding buffer can be forwarded onward.
Data flagger 203 flags the data that is flushed to the write-back data holding buffer with a processor identifier and a serialization flag. In one embodiment, the flagging enables data associated with a specific processor core and a specific flush to be identified from among other data associated with various other processor cores and flushes that are extant on a chip.
Cache notifier 205, responsive to the flagging, notifies L2 cache that a flush of the flagged data has been completed (e.g., that the data has been written back to main memory/next level cache/private memory of device). In one embodiment, the notification is provided to L2 cache prior to the completion of the flush of the flagged data to main memory/next level cache/private memory of device.
Access provider 207, after a cache flush completion notification is provided to the cache, provides access to the data that is then present in the write-back holding buffer, such that it can be determined if the data then present in the write-back data holding buffer is flagged. In one embodiment, access is provided to a serialization instruction, which determines if any of the data then present in the write-back data holding buffer is flagged.
It should be appreciated that the aforementioned components of system 101 can be implemented in hardware or software or in a combination of both. In one embodiment, components and operations of system 101 can be encompassed by components and operations of one or more computer components or operations (e.g., cache controller 102 in FIG. 1A). In another embodiment, components and operations of system 101 can be separate from the aforementioned one or more computer components or operations but can operate cooperatively with components and operations thereof.
Method for Non-Blocking Implementation of a Cache Flush Instruction According to One Embodiment
FIG. 3 shows a flowchart 300 of the steps performed in a method for non-blocking implementation of cache flush instructions according to one embodiment. The flowchart includes processes that, in one embodiment can be carried out by processors and electrical components under the control of computer-readable and computer-executable instructions. Although specific steps are disclosed in the flowcharts, such steps are exemplary. That is the present embodiment is well suited to performing various other steps or variations of the steps recited in the flowchart.
Referring to FIG. 3, at 301, a cache flush request is made and data is flushed to a write-back data holding buffer as a part of cache flushing operations. In one embodiment, the cache flush request is made by a software program that seeks to flush modified data from L2 cache.
At 303, data is accessed that is received by a write-back data holding buffer as a part of the cache flushing operation.
At 305, the flushed data is flagged with a processor identifier and a serialization flag. In one embodiment, as described herein, the flagging enables data associated with a specific processor core and a specific flush to be distinguished from among other data associated with various other processor cores and flushes that can be extant on a chip.
At 307, the L2 cache is notified that a write-back of the data to main memory/next level cache/private memory of device has been completed (that the flush of the data to main memory/next level cache/private memory of device is completed) prior to the actual completion of the write-back of the data to main memory/next level cache/private memory of device. In one embodiment, the cache is notified that a write-back of the data to main memory/next level cache/private memory of device has been completed in response to the flagging of the data.
At 309, subsequent to notifying the L2 cache that a write-back of the flagged data to main memory/next level cache/private memory of device has been completed, access is provided to data then present in the write-back holding buffer to determine if the data then present in the write-back data holding buffer has been flagged.
With regard to exemplary embodiments thereof, systems and methods for efficient cache flushing are disclosed. As a part of a method, data is accessed that is received in a write-back data holding buffer from a cache flushing operation, the data is flagged with a processor identifier and a serialization flag, and responsive to the flagging, the cache is notified that the cache flush is completed. Subsequent to the notifying, access is provided to data then present in the write-back data holding buffer to determine if data then present in the write-back data holding buffer is flagged.
Although many of the components and processes are described above in the singular for convenience, it will be appreciated by one of skill in the art that multiple components and repeated processes can also be used to practice the techniques of the present invention. Further, while the invention has been particularly shown and described with reference to specific embodiments thereof, it will be understood by those skilled in the art that changes in the form and details of the disclosed embodiments may be made without departing from the spirit or scope of the invention. For example, embodiments of the present invention may be employed with a variety of components and should not be restricted to the ones mentioned above. It is therefore intended that the invention be interpreted to include all variations and equivalents that fall within the true spirit and scope of the present invention.

## Claims

1. A method for non-blocking implementation of cache flush instructions, comprising:
accessing data that is received in a write-back data holding buffer from a cache flushing operation;
flagging said data with a flag that comprises a processor identifier and a flag, wherein the flag is a flush identifier; and
responsive to said flagging, notifying said cache that said cache flushing operation is complete before said cache flushing operation is completed.

2. The method of claim 1, wherein the cache flushing operation is a software based cache flushing operation.

3. The method of claim 1, wherein said accessing is part of a serialization operation and said flag is a serialization flag.

4. The method of claim 1, further comprising:
subsequent to said notifying, providing access to data then present in said write-back holding buffer to determine if said data then present in said write-back data holding buffer is flagged.

5. The method of claim 1, wherein data that replaces said data that is received in said write-back data holding buffer in L2 cache replaces said data in L2 cache before said cache flushing operation has been completed.

6. The method of claim 1, wherein said notifying is performed before an execution of a serialization instruction in software that initiated said cache flushing operation.

7. The method of claim 1 wherein said data remains in said write-back data holding buffer for a period after said notifying is performed.

8. The method of claim 1 wherein said processor identifier identifies a specific processor core among a plurality of processor cores.

9. The method of claim 3 wherein said serialization flag identifies a specific flush operation associated with said processor.

10. A cache controller to support non-blocking implementation of cache flush instructions, the cache controller comprising:
an accessing component for accessing data that is received in a writeback data holding buffer from a cache flushing operation;
a flagging component for flagging said data with a processor identifier and a flush identifier; and
a notifying component coupled to the accessing component and flagging component for, responsive to said tagging, notifying said cache that said cache flushing is completed.

11. The cache controller of claim 10, further comprising:
an access provider to, subsequent to said notifying, providing access to data then present in said write-back holding buffer to determine if said data then present in said write-back data holding buffer is flagged.

12. The cache controller of claim 10 wherein data that replaces said data that is received in said write-back data holding buffer in L2 cache replaces said data in L2 cache before said cache flushing operation has been completed.

13. The cache controller of claim 10 wherein said notifying is performed before said cache flushing operation is completed.

14. The cache controller of claim 10 wherein said notifying is performed before an execution of a serialization instruction in a software program that initiated said cache flushing operation.

15. The cache controller of claim 10 wherein said data remains in said writeback holding buffer for a period after said notifying is performed.

16. The cache controller of claim 10 wherein said processor identifier identifies a specific processor core among a plurality of processor cores.

17. The cache controller of claim 10 wherein said flush identifier identifies a specific flush operation associated with said processor.

18. A processor comprising:
a cache; and
a cache controller, to support
non-blocking implementation of cache flush instructions, where the cache controller includes,
a data accessor to access data that is received in a writeback data holding buffer from a cache flushing operation;
a data flagger to flag said data with a processor identifier and a flush identifier; and
a cache notifier to, responsive to said tagging, notify said cache that said cache flushing is completed.

19. The processor of claim 18, further comprising:
an access provider to, subsequent to said notifying, provide access to data then present in said write-back holding buffer to determine if said data then present in said write-back data holding buffer is flagged.

20. The processor of claim 19 wherein data that replaces said data that is received in said write-back data holding buffer in L2 cache replaces said data in L2 cache before said cache flushing operation has been completed.

21. The processor of claim 18 wherein said notifying is performed before said cache flushing operation is completed.

22. The processor of claim 18 wherein said notifying is performed before an execution of a serialization instruction in a software program that initiated said cache flushing operation.

23. The processor of claim 18 wherein said data remains in said write-back holding buffer for a period after said notifying is performed.

24. The processor of claim 18 wherein said processor identifier identifies a specific processor core among a plurality of processor cores.