Patent Publication Number: US-9430385-B2

Title: Moveable locked lines in a multi-level cache

Description:
PRIORITY APPLICATION 
     This application is a continuation of U.S. application Ser. No. 11/361,228, filed Feb. 24, 2006, which is incorporated herein by reference in its entirety. 
    
    
     Digital processors include cache memories for storing data and instructions that are faster static memories as compared to the slower dynamic memories used for the main memory. Through use of replacement algorithms and cache hierarchy, cache data may be moved and controlled to provide a relatively high hit rate. Improvements are needed in cache memory to speed up the flow of instructions and data to the execution unit of the processor. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings in which: 
         FIG. 1  illustrates a processor in a wireless device that incorporates lock properties stored with cache information that is used in replacement decisions in accordance with the present invention; and 
         FIG. 2  illustrates locked and unlocked cache lines that migrate through the cache hierarchy. 
     
    
    
     It will be appreciated that for simplicity and clarity of illustration, elements illustrated in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals have been repeated among the figures to indicate corresponding or analogous elements. 
     DETAILED DESCRIPTION 
     In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, components and circuits have not been described in detail so as not to obscure the present invention. 
     As shown in  FIG. 1 , wireless communications device  10  includes a radio to allow communication in an RF/location space with other devices. Accordingly, communications device  10  may operate in a wireless network such as, for example, a cellular network, a Personal Area Network (PAN), a Wireless Personal Area Network (WPAN), an Ultra-Wideband (UWB) network, a Piconet or a combination thereof. The figure illustrates a transceiver  12  that both receives and transmits a modulated signal from one or more antenna. Analog front end transceiver  12  may be a stand-alone Radio Frequency (RF) integrated analog circuit, or alternatively, be embedded with a processor  14  as a mixed-mode integrated circuit. The received modulated signal may be frequency down-converted, filtered, and then converted to a baseband, digital signal. 
     Processor  14  may include baseband and applications processing functions and utilize one or more processor cores. Processor  14 , in general, processes functions that fetch instructions, generate decodes, find operands, and perform appropriate actions, then stores results. The use of multiple cores  16  and  18  may allow one core to be dedicated to handle application specific functions and allow processing workloads to be shared across the cores. 
     A memory management unit  20  includes a hardware/software interface between a host controller software driver and the host controller hardware that exchanges data across memory interface  22  with external system memory  24 . System memory  24  may include a combination of memories such as a Random Access Memory (RAM), a Read Only Memory (ROM) and a nonvolatile memory, although neither the type nor variety of memories included in the system memory is a limitation of the present invention. 
     As illustrated in  FIG. 1 , processor  14  stores cache information in a multi-level cache memory hierarchy, and as such, processor cores  16  and  18  may include a first or inner cache, a second or outer cache, etc. More particularly and as illustrated in the diagram, processor core  16  may include a first or inner cache  42  that is labeled L 1 , a second or outer cache  44  that is labeled L 2  and a final cache  46  that is labeled L N . Similarly, processor core  18  may include a first or inner cache  52  that is labeled in the figure as L 1 , a second or outer cache  54  that is labeled as L 2  and a final cache  56  that is labeled as L N . Additional levels of cache may also exist, shared between the processors. The invention applies to caches dedicated to each processor, to caches that may be shared between the processors, and further to caches that may also be used by other components in the system. 
     When processor  14  reads or writes a location in system memory  24 , the processor generally operates by checking the smallest level cache first, i.e., the L 1  cache, to determine whether the memory location is in the inner cache as indicated by a cache hit. If the memory location is not in the smallest level or inner cache of the multi-level cache, then a cache miss occurs and the next larger cache in the cache hierarchy is checked before the processor finally checks system memory  24 . 
     The cache memory hierarchy illustrated by the L 1 , L 2 , . . . , L N  levels provides time savings in operations executed by processor cores  16  and  18 . Based on the hierarchy, if the processor core finds the data for its next operation in the L 1  cache then time is saved compared to having to retrieve that stored data from the next level in the hierarchy. Thus, the hierarchy allows cache memory data to be accessed more quickly from L 1  cache than the larger L 2 , . . . , L N  cache memories or the main system memory  24 . 
     A cache tracks the memory locations that have been modified since being loaded into the cache, especially when those modifications have not been propagated to other levels in the cache hierarchy. These memory locations are marked “dirty” and the data in these locations is written back to main memory  24  when that data is evicted from the cache. Cache lines may also be evicted from a first level of the cache memory hierarchy to a second level of the cache memory hierarchy. In accordance with the present invention, properties may be attached to a cache line that dictate actions during an eviction of the cache line within the multi-level cache hierarchy. In accordance with the present invention, one property attached to the cache line is a lock indication bit. 
     In one embodiment the lock indication bit may be a stored bit in a data field that accompanies the data associated with the cache line. The lock indication bit may be stored in the cache line&#39;s TAG which contains the index of the datum in main memory which has been cached, or alternatively, the lock indication bit may be stored separately in the cache line. In another embodiment, the lock indication property may be expressed indirectly by a particular state value that the cache maintains within a set or on a per set basis. The lock indication bit may also be a bit in a register that when set marks the cache line. Neither the number of bits nor the method of “locking” the cache line are limitations of the present invention. 
     In general, a lock condition may be determined by the Operating System (OS) or by an application running in processor  14  that apply to data or instructions that have been identified as performance-critical. Cache locking may optimize processor performance by holding the identified data and instructions within the multi-level cache memory hierarchy, thus keeping the data and instructions always present for executing algorithms and applications. Thus, when data or an instruction is designated via a sequence of commands to the system as “locked”, the locked items are maintained within the cache hierarchy or at some set of levels within the cache hierarchy. 
     Note that the term “locked” does not confine the items to a particular cache, but rather, locked items may migrate from one cache level to another cache level and back again in response to changing execution demands. This may include migration from a cache dedicated to one processor to a cache dedicated to another processor and migration to or from a shared cache. Further note that the term “locked” does ensure that the locked item is confined to some level of the cache hierarchy, and thus guarantees some minimum level of access performance for the locked items. 
       FIG. 2  illustrates a processor core such, for example, processor core  16  (see  FIG. 1 ) that is shown interacting with a first level instruction cache  42 A, a first level data cache  42 B, a second level unified cache  44  and a main memory  24 . Although this embodiment is shown with a cache configuration that includes an L 1  instruction cache, an L 1  data cache and a unified L 2  cache, it should be understood that the present invention is not limited to this cache configuration. In other words, other embodiments would include a second level having an instruction cache separate from the data cache, or any combination of separated instruction and data caches and unified cache in the various levels of the cache hierarchy. Further, the embodiment in the figure depicts two levels of cache hierarchy for simplicity of illustration. However, it should be understood that the features of the present invention that allow locked lines to move between the various levels of cache extended beyond two levels of cache hierarchy. 
     The cache in cooperation with processor core  16  shows unlocked lines that may migrate between the L 1  instruction cache  42 A and the L 2  unified cache  44  that are indicated in the figure as lines  200 . Similarly, the unlocked lines that may migrate between the L 1  data cache  42 B and the L 2  unified cache  44  are indicated in the figure as lines  202 . And finally, the unlocked lines that may migrate between the L 2  unified cache  44  and the main memory  24  are indicated in the figure as lines  204 . The unlocked lines may move back and forth between all levels of the memory hierarchy in accordance with the cache system&#39;s replacement policy. 
       FIG. 2  also shows the locked lines  210  that may migrate between the L 1  instruction cache  42 A and the L 2  unified cache  44  and the locked lines  212  that may migrate between the L 1  data cache  42 B and the L 2  unified cache  44 . The embodiment illustrates that locked lines may move back and forth between the L 2  and the L 1  caches according to the cache system&#39;s replacement policy. Note that irrespective of the direction of travel, whether from an inner cache to an outer cache or from the outer cache to the inner cache, that cache line still retains the lock indication property in accordance with the present invention. 
     The cache line is not locked into any particular level of the cache, but rather, the cache line may be moved or copied from one cache to another and the “lock” bit associated with that particular cache line moves with the cache line. Thus, a “lock” bit may be set for a cache line and the locked cache line, once fetched from memory, is not evicted from the L 2  cache, for example, back to main memory  24  unless the cache first receives a command to unlock that particular cache line. In accordance with features of the present invention, the “lock” bit associated with the cache line assures that the locked cache line is in either, or both, of the L 1  or L 2  cache which provides some minimum level of access performance for the locked items. 
     In one embodiment the multi-level caches allow the data in the L 1  cache to also be in the L 2  cache, a condition called inclusive. In an inclusive L 1  cache a line may reside in both the L 1  cache and the L 2  cache and lines are not moved from the L 1  cache back to the L 2  cache, and locked lines sent to the L 1  cache would still be retained in the L 2  cache. In another embodiment processor  16  may have exclusive caches where data is guaranteed to be in at most one of the L 1  and L 2  caches. 
     A cache line that is evicted from an inner cache to the next or outward level of the cache hierarchy and deemed performance-critical is marked with the lock indication property. Note that the lock indication property may or may not accompany a cache line being filled from the outer level cache to an inner cache in accordance with the present invention. This is because a cache line in an inner cache is not a candidate to be evicted to the main memory. However, the “lock” bit would be set when that performance-critical cache line is evicted from the inner cache to the outer most level of the cache hierarchy. 
     Thus, in one instantiation, the lock property would be sent to the inner cache and stored with the cache line so that the lock property could be sent back to the outer level cache when that line was evicted from the inner cache, but the lock property would not be used by the inner cache. Alternatively, a separate mechanism such as a table look-up (not shown) or range check may be invoked on eviction of the line from an inner cache to the outer-most cache to determine whether a line should have the lock property set. 
     In caches where the outer levels of the cache hierarchy are protected by Error Correcting Code (ECC) and the inner levels are not protected, the present invention removes the need to do sub-line read-modify-writes on lines in the outer level of the hierarchy since lines are free to move into the inner level of the cache for such operations. This greatly simplifies the control logic and data flow in the outer level of the cache. In such caches the migration of locked lines from parity-protected inner caches to ECC-protected outer caches may be used to scrub the cache for soft errors. 
     By now it should be apparent that the present invention enhances processor performance by simplifying the cache replacement logic for multi-level caches. The various embodiments of the present invention allow the lock indication property to remain associated and travel with the cache line within the multi-level cache hierarchy. At each level of the cache hierarchy, the lock indication property makes the cache line a protected line that is prevented from being overwritten when space for new data is needed in the cache. The present invention may simplify cache locking since neither the OS nor the application separately manages the lockable capacity of each cache level. System performance of the processor may be improved by allowing the hardware to move locked lines into the faster and usually smaller L 1  caches when necessary while still having the larger lockable capacity of the L 2  cache. 
     While certain features of the invention have been illustrated and described herein, many modifications, substitutions, changes, and equivalents will now occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.