Patent Publication Number: US-7899993-B2

Title: Microprocessor having a power-saving instruction cache way predictor and instruction replacement scheme

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of U.S. patent application Ser. No. 11/272,719, filed Nov. 15, 2005 (now U.S. Pat. No. 7,562,191, Issued: Jul. 14, 2009), which is related to U.S. patent application Ser. No. 11/272,718, filed Nov. 15, 2005 (now allowed), entitled “Processor Utilizing A Loop Buffer to Reduce Power Consumption,” and commonly owned, U.S. patent application Ser. No. 11/272,737, filed Nov. 15, 2005 (now U.S. Pat. No. 7,496,771, Issued: Feb. 24, 2009), entitled “Processor Accessing A Scratch Pad On-Demand To Reduce Power Consumption,” each of which is incorporated herein by reference in its entirety. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates generally to microprocessors and reducing power consumption in microprocessors. 
     BACKGROUND OF THE INVENTION 
     An instruction fetch unit of a microprocessor is responsible for continually providing the next appropriate instruction to the execution unit of the microprocessor. A conventional instruction fetch unit typically employs a large instruction cache that is always enabled in order to provide instructions to the execution unit as quickly as possible. While conventional fetch units work for their intended purpose, they consume a significant amount of the total power of a microprocessor. This makes microprocessors having conventional fetch units undesirable and/or impractical for many applications. 
     What is needed is a microprocessor and an instruction fetch unit that offers the performance advantages of a large instruction cache while consuming less power than a conventional fetch unit. 
     BRIEF SUMMARY OF THE INVENTION 
     The present invention provides a microprocessor having a power-saving instruction cache way predictor and instruction replacement scheme. In one embodiment, a processor core according to the invention has a multi-cycle processing pipeline for improved performance. The processor core includes a multi-way set associative cache, a way predictor, and a policy counter. The multi-way set associative cache can be, for example, either a 2-way set associative cache, a 4-way set associative cache, an 8-way set associative cache, et cetera. The policy counter provides a policy signal to the way predictor that determines whether the way predictor operates in a first power-saving mode or a second power-saving mode. 
     When the way predictor is operating in the first power-saving mode, the way predictor enables in one processing cycle a dataram predicted to have an instruction to be fetched from the cache and a tagram associated with the dataram. If the instruction is present in the predicted dataram, the instruction is fetched, and the way predictor and the policy counter are updated to reflect that a cache hit occurred. If the instruction is not in the predicted dataram, the way predictor disables the dataram and its associated tagram and enables all remaining datarams and their associated tagrams in a second processing cycle. If the instruction is determined to be in one of the datarams enabled during the second processing cycle, the instruction is fetched, and the way predictor and the policy counter are updated to indicate that a cache hit occurred and the dataram (way) in which the instruction was stored. If the instruction is not in any of the datarams, the way predictor generates a cache miss signal, and the policy counter is updated to indicate that a cache miss occurred. 
     When the way predictor is operating in the second power-saving mode, the way predictor enables all tagrams associated with the datarams of the cache in a first processing cycle. If it is determined that the instruction is present in one of the datarams, the tagrams are disabled and the dataram containing the instruction is enabled in a second processing cycle. The instruction is then fetched, and the way predictor and the policy counter are updated to indicate that a cache hit occurred. If it is determined that the instruction is not in any of the datarams, the way predictor generates a cache miss signal, and the policy counter is updated to reflect that a cache miss occurred. 
     In one embodiment of the present invention, the policy counter includes a register configured to store a count value. The count value is incremented and decremented, based on cache hits and cache misses, between a first value and a second value. Initially, the count value is set to the first value (e.g., zero), and the policy counter provides a first policy signal to the way predictor that cause the way predictor to operate in the first power-saving mode. After a selected number of cache misses (e.g., the count value is incremented to the second value), the policy counter provides a second policy signal to the way predictor that causes the way predictor to operate in the second power-saving mode. If the count value subsequently is decremented to the first value due to a number of cache hits, the policy counter again provides the first policy signal to the way predictor, and the way predictor operates in the first power-saving mode. 
     In one embodiment of the present invention, the processor core includes a cache refill circuit that refills the cache following a cache miss using a least recent filled scheme. The cache refill circuit operates by selecting a way of the multi-way set associative cache and comparing a layer number (associated with a selected dataram field of the way) to a way set layer number. If the layer number is not equal to the way set layer number, the cache refill circuit writes a block of data from a memory to the selected field. If the layer number is equal to the way set layer number, the cache refill circuit switches to another (e.g., next higher or next lower) way and repeats the above noted steps. If the layer number is again equal to the way set layer number, the steps are repeated for additional ways of the multi-way set associative cache until the block of memory is written to the multi-way set associative cache. The cache refill circuit increments the layer number of the selected field in which the block of memory is written. 
     In one embodiment, the layer numbers associated with the fields of the datarams are stored in a wayram data structure separate from the datarams. The dataram is only accessed during cache refills, and it can be disabled between cache refills in order to reduce power consumption. 
     In one embodiment of the present invention, the functionality of the way predictor is expanded to predict whether an instruction to be fetched is residing in a memory other than the multi-way set associative cache such as, for example, a scratch pad or a fill buffer. 
     In one embodiment, a component of the processor core, such as a tagram, a dataram and/or a scratch pad, is disabled to reduce power consumption by controlling a clock signal provided to the component. By maintaining the input clock signal at either a constant high or a constant low value, state registers in the component are suspended from latching new values, and the logic blocks between the state registers are placed in a stable state. Once the component is placed in a stable state, the transistors in the state registers and the logic blocks are suspended from changing states and therefore do not consume power required to transition states. In one embodiment, when a component is disabled to reduce power consumption, a bias voltage is applied to the component to further reduce power consumption resulting from leakage. 
     Further embodiments, features, and advantages of the present invention, as well as the structure and operation of the various embodiments of the present invention, are described in detail below with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS/FIGURES 
       The accompanying drawings, which are incorporated herein and form a part of the specification, illustrate the present invention and, together with the description, further serve to explain the principles of the invention and to enable a person skilled in the pertinent art to make and use the invention. 
         FIG. 1  is a diagram of a processor core according to an embodiment of the present invention. 
         FIG. 2  is a diagram of tagrams and datarams according to an embodiment of the present invention. 
         FIG. 3  is a diagram of a predictor and a policy counter according to an embodiment of the present invention. 
         FIGS. 4A and 4B  depict a flow chart illustrating the steps of a first method of the present invention. 
         FIG. 5  is a flow chart illustrating the steps of a second method of the present invention. 
     
    
    
     The present invention is described with reference to the accompanying drawings. The drawing in which an element first appears is typically indicated by the leftmost digit in the corresponding reference number. 
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention provides a microprocessor having a power-saving instruction cache way predictor and instruction replacement scheme. In the detailed description of the invention that follows, references to “one embodiment”, “an embodiment”, “an example embodiment”, etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to effect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described. 
       FIG. 1  is a diagram of a processor core  100  according to an embodiment of the present invention. As shown in  FIG. 1 , processor core  100  includes an execution unit  102 , a fetch unit  104 , a floating point unit  106 , a load/store unit  108 , a memory management unit (MMU)  110 , an instruction cache  112 , a data cache  114 , a bus interface unit  116 , a power management unit  118 , a multiply/divide unit (MDU)  120 , and a coprocessor  122 . While processor core  100  is described herein as including several separate components, many of these components are optional components that will not be present in each embodiment of the present invention, or components that may be combined, for example, so that the functionality of two components reside within a single component. Thus, the individual components shown in  FIG. 1  are illustrative and not intended to limit the present invention. 
     Execution unit  102  preferably implements a load-store (RISC) architecture with single-cycle arithmetic logic unit operations (e.g., logical, shift, add, subtract, etc.). In one embodiment, execution unit  102  includes 32-bit general purpose registers (not shown) used for scalar integer operations and address calculations. Optionally, one or more additional register file sets can be included to minimize content switching overhead, for example, during interrupt and/or exception processing. Execution unit  102  interfaces with fetch unit  104 , floating point unit  106 , load/store unit  108 , multiple-divide unit  120  and coprocessor  122 . 
     Fetch unit  104  is responsible for providing instructions to execution unit  102 . In one embodiment, fetch unit  104  includes control logic for instruction cache  112 , a recorder for recoding compressed format instructions, dynamic branch prediction, an instruction buffer to decouple operation of fetch unit  104  from execution unit  102 , and an interface to a scratch pad (not shown). Fetch unit  104  interfaces with execution unit  102 , memory management unit  110 , instruction cache  112 , and bus interface unit  116 . 
     As used herein, a scratch pad is a memory that provides instructions that are mapped to one or more specific regions of an instruction address space. The one or more specific address regions of a scratch pad may be pre-configured or configured programmatically while the microprocessor is running. An address region is a continuous range of addresses that may be specified, for example, by a base address and a region size. When base address and region size are used, the base address specifies the start of the address region and the region size, for example, is added to the base address to specify the end of the address region. Once an address region is specified for a scratch pad, all instructions corresponding to the specified address region are retrieved from the scratch pad. 
     Floating point unit  106  interfaces with execution unit  102  and operates on non-integer data. As many applications do not require the functionality of a floating point unit, this component of processor core  100  will not be present in embodiments of the present invention. 
     Load/store unit  108  is responsible for data loads and stores, and includes data cache control logic. Load/store unit  108  interfaces with data cache  114  and other memory such as, for example, a scratch pad and/or a fill buffer. Load/store unit  108  also interfaces with memory management unit  110  and bus interface unit  116 . 
     Memory management unit  110  translates virtual addresses to physical addresses for memory access. In one embodiment, memory management unit  110  includes a translation lookaside buffer (TLB) and may include a separate instruction TLB and a separate data TLB. Memory management unit  110  interfaces with fetch unit  104  and load/store unit  108 . 
     Instruction cache  112  is an on-chip memory array organized as a multi-way set associative cache such as, for example, a 2-way set associative cache, a 4-way set associative cache, an 8-way set associative cache, et cetera. Instruction cache  112  is preferably virtually indexed and physically tagged, thereby allowing virtual-to-physical address translations to occur in parallel with cache accesses. In one embodiment, the tags include a valid bit and optional parity bits in addition to physical address bits. As described in more detail below, it is a feature of the present invention that components of instruction cache  112  can be selectively enabled and disabled to reduce the total power consumed by processor core  100 . Instruction cache  112  interfaces with fetch unit  104 . 
     Data cache  114  is also an on-chip memory array. Data cache  114  is preferably virtually indexed and physically tagged. In one embodiment, the tags include a valid bit and optional parity bits in addition to physical address bits. Data cache  114  interfaces with load/store unit  108 . 
     Bus interface unit  116  controls external interface signals for processor core  100 . In one embodiment, bus interface unit  116  includes a collapsing write buffer used to merge write-through transactions and gather writes from uncached stores. 
     Power management unit  118  provides a number of power management features, including low-power design features, active power management features, and power-down modes of operation. In one embodiment, processor core  100  implements a wait instruction that signals to selected components of processor core  100  that execution and/or clocking should be halted, thereby reducing power consumption during the idle period. These power management features are in addition to the power saving features described herein with reference, for example, to  FIGS. 3-5 . 
     Multiply/divide unit  120  performs multiply and divide operations for processor core  100 . In one embodiment, multiply/divide unit  120  preferably includes a pipelined multiplier, result and accumulation registers, and multiply and divide state machines, as well as all the control logic required to perform, for example, multiply, multiply-add, and divide functions. As shown in  FIG. 1 , multiply/divide unit  120  interfaces with execution unit  102 . 
     Coprocessor  122  performs various overhead functions for processor core  100 . In one embodiment, coprocessor  122  is responsible for virtual-to-physical address translations, implementing cache protocols, exception handling, operating mode selection, and enabling/disabling interrupt functions. Coprocessor  122  interfaces with execution unit  102 . 
       FIG. 2  is a diagram of four tagrams  202  and four datarams  204  that make up a 4-way set associative cache. This cache structure represents one embodiment for instruction cache  112 . 
     As shown in  FIG. 2 , each tagram  202  includes a plurality of fields  214  that store physical address bits or tags. Each tag has an associated valid bit  212 . Additional bits (not shown) such as parity bits may also be associated with each tag. 
     Each dataram  204  includes a plurality of fields  218  that are used to store blocks of data/instructions. As shown in  FIG. 2 , each block of data has an associated layer number  216 . As described in more detail below with reference to  FIG. 5 , layer numbers  216  are used to determine where in the cache a new block of data is stored following a cache miss. In one embodiment, layer numbers  216  are stored in a data structure  208  referred to herein as a wayram. Wayram  208  can be a separate data structure from datarams  204 , which is only enabled during cache refills/cache writes. 
     Information stored within tagrams  202   a - d  and datarams  204   a - d  are accessed using an address  206 . Address  206  includes a tag  222 , an index  224 , and an offset  226 . A particular index  224  uniquely points to selected fields  214  of each tagram  202  and selected fields  218  of each dataram  204 . In order to determine whether a particular instruction is stored in a way (e.g., a dataram  204 ) of the instruction cache, tag  222  of address  206  is compared to tags stored in tagrams  202  in a manner that will be apparent to persons skilled in the relevant arts given the description herein. 
     Data structure  210  in  FIG. 2  stores way set layer numbers  220 . As described in more detail below with reference to  FIG. 5 , way set layer numbers  220  are used together with layer numbers  216  to determine where in the cache a new block of data is stored following a cache miss. Although layer numbers  216  and way set layer numbers  220  are shown as single bit values in  FIG. 2 , it is to be understood that they can also be multi-bit values without departing from the scope of the present invention. 
       FIG. 3  is a diagram of a way predictor (predictor)  302  and a policy counter  304  according to an embodiment of the present invention. Predictor  302  predicts where an instruction to be fetched is stored and provides cache hit and miss data to policy counter  304 . In one embodiment, predictor  302  always predicts that the next instruction to be fetched is located in the way from which the last instruction was fetched. Other embodiments use more complex prediction schemes. Policy counter  304  includes a memory element such as, for example, a register that keeps track of cache hits and misses. Based on the cache hit and miss data provided by predictor  302 , policy counter  304  provides a policy signal to predictor  302  that determines the operating mode of predictor  302 . 
     Predictor  302  interfaces with a plurality of tag/datarams  306  and tag compare circuits  308 . Tag/datarams  306   a - d  represent a multi-way (e.g., 4-way) set associative cache. Predictor  302  optionally also interfaces with one or more other memory elements  306   e , such as for example a scratch pad or fill buffer, and their associated tag compare circuits  308   e.    
     In one embodiment of the present invention, policy counter  304  provides a policy signal to predictor  302  that determines whether predictor  302  operates in a first power-saving mode or a second power-saving mode. In some embodiments of the invention, predictor  302  operates in more than two power-saving modes. In each operating mode, the number of components that are enabled and/or disabled vary, thereby varying the power consumed by the processor. 
     When predictor  302  is operating in the first power-saving mode, predictor  302  enables in one processing cycle both a dataram predicted to have an instruction to be fetched and a tagram associated with the dataram. If the instruction is present in the predicted dataram, the instruction is fetched and predictor  302  and policy counter  304  are updated to indicate that a cache hit occurred. As shown in  FIG. 3 , feedback about whether a dataram contains an instruction comes from a tag compare circuit  308 . If the instruction is not in the predicted dataram, predictor  302  disables the dataram and its associated tagram and enables all remaining datarams and their associated tagrams in a second processing cycle. If the instruction is determined to be in one of the datarams enabled during the second processing cycle, the instruction is fetched and predictor  302  and policy counter  304  are updated to reflect that a cache hit occurred and the dataram in which the instruction was stored. If the instruction is not in any of the datarams, a cache miss signal is generated by predictor  302  and policy counter  304  is updated to reflect that a cache miss occurred. In one embodiment, a scratch pad, fill buffer, or other memory is checked in parallel with the remaining datarams. 
     When predictor  302  is operating in the second power-saving mode, predictor  302  enables all tagrams associated with the datarams of the cache in a first processing cycle. This mode of operation increases the power consumed by the processor, but it allows the processor to process cache misses more quickly than the first power-saving mode. If it is determined (e.g., using tag compare circuits  308 ) that the instruction to be fetched is present in one of the datarams, the tagrams are disabled and the dataram containing the instruction is enabled in a second processing cycle. The instruction is then fetched, and predictor  302  and policy counter  304  are updated. If it is determined that the instruction is not in any of the datarams, a cache miss signal is generated by predictor  302 , and policy counter  304  is updated to reflect that a cache miss occurred. In one embodiment, a scratch pad, fill buffer, or other memory element is checked in parallel with the datarams. 
     In one embodiment of the present invention, policy counter  304  includes a register (not shown) configured to store a count value. The count value is incremented and decremented, based on cache hits and cache misses, between a first value and a second value (e.g., zero and three). As illustrated in  FIG. 3 , hit and miss data is provided to policy counter  304  by predictor  302 . In operation, the count value initially is set to the first value (e.g., zero) and policy counter  304  provides a first policy signal to predictor  302  that causes predictor  302  to operate in the first power-saving mode. For each cache miss, the count value is incremented. For each cache hit, the count value is decremented. After a selected number of cache misses (e.g., the count value is incremented to a value of three), policy counter  304  provides a second policy signal to predictor  302  that causes predictor  302  to operate in the second power-saving mode. If the count value subsequently is decremented to the first value (e.g., zero), policy counter  304  again provides the first policy signal to predictor  302 , and predictor  302  operates in the first power-saving mode. 
       FIGS. 4A and 4B  depict a flow chart illustrating the steps of a method  400 . Method  400  is used to retrieve instructions from a cache according to an embodiment of the present invention. While method  400  can be implemented, for example, using a processor core according to the present invention such as processor core  100 , it is not limited to being implemented by processor core  100 . Method  400  starts with step  401 . 
     In step  401 , an address for an instruction to be fetched from a multi-way set associative cache is received. The address can be received, for example, by having it loaded into a program counter of a processor. 
     In step  402 , a determination is made whether a predictor of the processor is operating in a particular mode noted in step  402  as mode zero. If the predictor is operating in mode zero (e.g., the first power-saving mode described above), control passes to step  404 . If the predictor is not operating in mode zero, control passes to step  418 . 
     In step  404 , a dataram predicted by the predictor as containing the instruction to be fetched is enabled. A tagram associated with the dataram also is enabled. In one embodiment of the present invention, the predictor predicts that the dataram that contained the last instruction fetched also will contain the next instruction to be fetched. 
     In step  406 , a tag portion of the address of the instruction to be fetched is compared to a selected tag in the enabled tagram. The selected tag is the tag pointed to by an index portion of the address received in step  401 . If the tag portion of the address matches the selected tag stored in the enabled tagram, and assuming that the selected tag in the tagram is valid, control passes from step  406  to step  408 . If the tag portion of the address does not match the selected tag stored in the enabled tagram, control passes from step  406  to step  412 . 
     In step  408 , the instruction to be fetched is read from dataram. Control passes from step  408  to step  410 . 
     In step  410 , the predictor of the processor and a policy counter of the processor are updated regarding whether a cache hit or a cache miss occurred and whether the prediction made by the predictor regarding which dataram included the instruction was correct. The policy counter provides a policy signal to the predictor that determines whether the predictor operates in mode zero or another mode (e.g., the second power-saving mode described above) based on cache hit and cache miss information. Control passes from step  410  back to step  401 . 
     In step  412 , the tagram and dataram enabled in step  406  are disabled, and the remaining tagrams and datarams of the cache are enabled. As described herein, a component of a processor such as a tagram and a dataram can be disabled to reduce power consumption in accordance with the present invention by controlling the input clock signal of the component. Control passes from step  412  to step  414 . 
     In step  414 , a determination is made regarding whether the instruction to be fetched is stored within one of the enabled datarams. If the instruction is stored in one of the datarams, control passes to step  408 , where the instruction is read from the dataram. If the instruction is not in one of the enabled datarams, a cache miss has occurred, and control is passed to step  416 . 
     In step  416 , a new memory block of data is loaded into the cache that includes the instruction to be fetched. In one embodiment, the block of data is loaded into the cache in accordance with method  500  described below. Control passes from step  416  to step  408 . 
     In step  418 , all tagrams of the cache are enabled. This allows the processor to determine, for example in a single processing cycle, whether the instruction to be fetched resides in one of the datarams of the cache. Control passes from step  418  to step  420 . 
     In step  420 , a determination is made whether the instruction to be fetched resides in one of the datarams. If the instruction is stored in one of the datarams, control passes to step  422 . If the instruction is not stored in one of the datarams, control passes to step  428 . 
     In step  422 , the tagrams are disabled and the dataram containing the instruction is enabled to allow the instruction to be fetched. Control passes from step  422  to step  424 . 
     In step  424 , the instruction to be fetched is read from dataram. Control passes from step  424  to step  426 . 
     In step  426 , the predictor of the processor and the policy counter of the processor are updated regarding whether a cache hit or a cache miss occurred. From step  426 , control returns to step  401 . 
     In step  428 , a new memory block of data is loaded into the cache that includes the instruction to be fetched. In one embodiment, the block of data is loaded into the cache in accordance with method  500  described below. Control passes from step  428  to step  424  so that the instruction can be fetched. 
     As will be understood by persons skilled in the relevant arts, the steps of method  400  can be varied to change, for example, the number of tagrams and datarams that are enabled and/or disabled in particular steps to accommodate different control schemes. The order of some steps can also be changed. These variations remain within the scope of the present invention. Additionally, memories other than tagrams and datarams of a cache, such as a scratch pad, a fill buffer, etc., can be enabled and/or disabled, as illustrated by  FIG. 3 . 
       FIG. 5  is a flow chart illustrating the steps of a method  500  of the present invention. At a high level, method  500  can be thought of as a least recently filled cache refill scheme. More particularly, method  500  is used to load a memory block of data into a 4-way set associative cache following a cache miss. However, as will become apparent to persons skilled in the relevant arts given the description herein, method  500  can be adapted for use with other multi-way set associative caches such as, for example, 2-way set associative caches, 8-way set associative caches, et cetera. As with method  400 , method  500  can be implemented, for example, using a processor core according to the present invention such as processor core  100 , but it is not limited to being implemented by processor core  100 . 
     Method  500  starts at step  502 . In step  502 , the method waits for a cache miss to occur. When a cache miss is detected, control transfers to step  504 . 
     In step  504 , a layer number for a way set associated with the cache miss is read. As used herein, the term way set means the fields of datarams of a multi-way set associative cache in which a particular block of memory can be stored. The way set layer number is a value used to control the refilling of the cache with new blocks of data. 
     In step  506 , the way set layer number read in step  504  is compared to a layer number for way- 0  of the cache. If the layer number for way- 0  is different than the way set layer number, control passes to step  508 . If the layer number is not different than the way set layer number, control passes to step  512 . 
     In step  508 , a new memory block of data is written to way- 0  of the cache. Control then passes to step  510 . 
     In step  510 , the layer number for the way in which the memory block of data was written is incremented. Control passes from step  510  back to step  502 . 
     In step  512 , the way set layer number read in step  504  is compared to a layer number for way- 1  of the cache. If the layer number for way- 1  is different than the way set layer number, control passes to step  514 . If the layer number is not different than the way set layer number, control passes to step  516 . 
     In step  514 , a new memory block of data is written to way- 1  of the cache. Control then passes to step  510 . 
     In step  516 , the way set layer number read in step  504  is compared to a layer number for way- 2  of the cache. If the layer number for way- 2  is different than the way set layer number, control passes to step  518 . If the layer number is not different than the way set layer number, control passes to step  522 . 
     In step  518 , a new memory block of data is written to way- 2  of the cache. Control then passes to step  510 . 
     In step  522 , a new memory block of data is written to way- 3  of the cache. Control then passes to step  524 . 
     In step  524 , the layer number for way- 3  is incremented. Control then passes from step  524  to  526 . 
     In step  526 , the layer number for the way set is incremented. Control passes from step  526  back to step  502 . 
     In one embodiment of the present invention, method  500  is modified as follows. First, the way set layer number is modified to be a fixed value (e.g., one) rather than a variable value. This allows step  504  to be bypassed or eliminated. At start up of the processor, all of the layer numbers of the cache are set to a value different than the fixed value (e.g., zero). Next, step  510  is modified to change the layer number for a way to the fixed value (e.g., one) after a block of data has been written to the way. Finally, steps  524  and  526  are replaced with a new step that resets the appropriate layer numbers of the ways to a value other than the fixed value (e.g., zero) so that the next cache refill is written to way- 0  (because the layer number for way- 0  will now be different than the fixed way set layer number when step  506  is performed). 
     As will be understood by persons skilled in the relevant arts given the description herein, method  500  and its modifications eliminate much of the overhead associated with conventional least recently used cache refill schemes because there is no need to keep track of how often a block of data in the cache is used. Additionally, the refill scheme of method  500  improves the accuracy of the predictor of the present invention (e.g., when the predictor is set to predict that the next instruction will come from the same way as the last instruction). This is due to the fact that the cache refill scheme of the present invention improves the order between cache line entries and provides convergence of unordered entry segments. 
     While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example, and not limitation. It will be apparent to persons skilled in the relevant computer arts that various changes in form and detail can be made therein without departing from the spirit and scope of the invention. Furthermore, it should be appreciated that the detailed description of the present invention provided herein, and not the summary and abstract sections, is intended to be used to interpret the claims. The summary and abstract sections may set forth one or more but not all exemplary embodiments of the present invention as contemplated by the inventors. 
     For example, in addition to implementations using hardware (e.g., within or coupled to a Central Processing Unit (“CPU”), microprocessor, microcontroller, digital signal processor, processor core, System on Chip (“SOC”), or any other programmable or electronic device), implementations may also be embodied in software (e.g., computer readable code, program code, instructions and/or data disposed in any form, such as source, object or machine language) disposed, for example, in a computer usable (e.g., readable) medium configured to store the software. Such software can enable, for example, the function, fabrication, modeling, simulation, description, and/or testing of the apparatus and methods described herein. For example, this can be accomplished through the use of general programming languages (e.g., C, C++), GDSII databases, hardware description languages (HDL) including Verilog HDL, VHDL, SystemC Register Transfer Level (RTL) and so on, or other available programs, databases, and/or circuit (i.e., schematic) capture tools. Such software can be disposed in any known computer usable medium including semiconductor, magnetic disk, optical disk (e.g., CD-ROM, DVD-ROM, etc.) and as a computer data signal embodied in a computer usable (e.g., readable) transmission medium (e.g., carrier wave or any other medium including digital, optical, or analog-based medium). As such, the software can be transmitted over communication networks including the Internet and intranets. 
     It is understood that the apparatus and method embodiments described herein may be included in a semiconductor intellectual property core, such as a microprocessor core (e.g., embodied in HDL) and transformed to hardware in the production of integrated circuits. Additionally, the apparatus and methods described herein may be embodied as a combination of hardware and software. Thus, the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalence.