Apparatus and method for reducing the power consumption of a microprocessor with multiple levels of caches

[0002] This invention relates to microprocessors which have two or more levels of memory caches interposed in the memory hierarchy between the main memory and the CPU.

[0003] A memory cache or “cache” is a mechanism in the memory hierarchy between the main memory and the CPU which improves the effective memory transfer rates and raises processing speeds. The term “cache” refers to the fact that the cache mechanism is not apparent to the user, who only observes an apparently higher speed main memory.

[0004] A cache has a smaller memory storage capacity than the main memory but has a much higher access speed. Caches are generally implemented by semiconductor devices, the speeds of which are comparable to that of the processor. By contrast, the main memory generally uses a less costly, lower speed technology, but has a much higher overall storage capacity.

[0005] The cache mechanism anticipates the likely re-use by the CPU of information, whether data or code, in the main memory by organizing a copy of the data or code in cache memory. When information is accessed from the main memory, it is common for associated information also to be accessed and stored in the cache. For example, if a required code is part of a sequence of instructions, the subsequent instructions should be received with the first instruction, so that access to the main memory can be minimized.

[0006] In modern microprocessors, it is common for one or more levels of memory caches to be included on a particular chip, and for an additional level of memory cache to be off-chip. Currently, some chips contain one or two on-chip caches, and it is anticipated that future products may contain more than two on-chip and off-chip caches.

[0007] In current microprocessors which access more than one level of cache, the higher-level caches generally have a larger storage capacity than the lower-level caches. For example, in the case of a two-level cache hierarchy, the second or L2 cache generally has a larger storage capacity than the first or L1 cache. The L2 cache has a significantly greater speed than the main memory, but it also has a significantly smaller storage capacity. The information on the L1 cache is usually a subset of the information on the L2 cache. The L2 cache only needs to be accessed if the desired code or data is not resident in the L1 cache.

[0008] For chips with multiple levels of caches, there is a tradeoff between the maximum processing speed and the minimum power usage of the caches. Processing speed can be maximized by simultaneously addressing more than one cache, for example, by simultaneously addressing the L1 cache and the L2 cache. However, simultaneously addressing the L1 and L2 caches uses power unnecessarily if the desired data or code is resident in the L1 cache.

[0009] Alternatively, power consumption can be reduced by accessing the higher-level cache or caches only when necessary. In the example of a chip with a 2-level cache hierarchy, power consumption can be reduced by accessing the L2 cache only when there is a “miss,” that is, when the L1 cache is addressed but the desired data or code is not currently in the L1 cache (as opposed to a “hit” where the desired data or code is currently resident). However, this method results in a larger effective access time for the L2 cache and a consequent reduction in processing speed.

[0010] A prediction of L1 cache data read misses has been implemented in the Compaq Alpha 21264. See R. E. Kessler, E. J. McLellan, and D. A. Webb, “The Alpha 21264 Microprocessor Architecture,” International Conference on Computer Design(ICCD'98), pp. 90-95 (October 1998) (“Kessler”), which is incorporated herein by reference.

[0011] However, the predictor described in Kessler does not disable the L2 cache for power savings. Instead, the Kessler predictor is used to reduce the penalty in those cases where a read access results in a “miss” of the L1 cache and the consumer of the read instruction was dispatched for execution before knowing if the data access resulted in a hit, in order to keep the L1 cache latency low. Therefore, if there is a miss, the consumer instruction and all the subsequent instructions have to be re-fetched with a high penalty in cycles.

[0012] To mitigate this problem, the Alpha 21264 has a data read miss predictor which consists of a saturated 4-bit counter that tracks the hit/miss behavior of recent data reads. This counter decrements by two on cycles when there is a read miss and increments by one when there is a hit. The most-significant bit of the counter is used to do the prediction.

[0013] It is an object of the present invention to provide a method for reducing power consumption in a multiple-cache microprocessor without creating an unacceptable reduction in processing speed.

[0014] The present invention seeks to overcome the disadvantages of optimizing either the processing speed or power consumption of caches independently. In the present invention, a dynamic predictor is used to provide a lower power consumption than the optimally fast condition, yet a faster processing speed than the condition of lowest power consumption. The misses of the lower-level cache are predicted based on the fact that misses occur in bursts which correspond to changes in the working set.

[0015] In the apparatus and method proposed, a window of size S is defined. After a miss occurs, a predicting device predicts that the next miss will occur in the next S accesses to the lower-level cache. If no miss occurs in these S accesses, a hit is predicted until the next miss.

[0016] A method of predicting access hits and misses of a lower-level cache and determining when to access one or more higher-level caches in a cache hierarchy includes the steps of: defining a window of size S for information which is sought on a cache, wherein S is measured in a number of accesses; detecting whether a hit or a miss occurs after each access of the cache; predicting, after each miss is detected, that the next miss will occur in a subsequent S accesses to the cache; and predicting, if no miss is detected within the subsequent S accesses, that the next access will be a hit.

[0017] This method is used for code access and for data reads, since data writes are handled by means of a write buffer. Therefore, the predictor method can have two parameters, S_cand S_d, that correspond to the window sizes for code accesses and data reads, respectively. These two windows can be independent of each other: the distances between L1 cache misses may be kept separately for code accesses and data reads.

[0018] An apparatus which implements the foregoing process includes: one or more detection circuits configured to receive a signal indicating whether a hit or a miss occurs after each access of a cache and in accordance therewith output a detection signal; one or more counters coupled to the one or more detection circuits, wherein the one or more counters are configured to receive the detection signal and in accordance therewith output a counting signal, wherein the one or more counters are set to a level of size S measured in a number of accesses to the cache and wherein the counters are reset each time a miss is detected and incremented each time a hit is detected; one or more comparison circuits coupled to the one or more counters, wherein the one or more comparison circuits are configured to receive the counting signal, to determine whether the number of accesses of the cache is above, below or equal to S based on the counting signal and in accordance therewith output a comparison signal; and one or more prediction circuits coupled to the one or more comparison circuits, wherein the one or more prediction circuits are configured to receive the comparison signal, to predict a hit or miss based on the comparison signal and in accordance therewith output a prediction signal.

[0019] The features and advantages of the present invention will be more clearly understood from the following detailed description, in connection with the accompanying drawings.

[0020] FIG. 1 is a block diagram which illustrates that portion of a conventional microprocessor, in this instance a microprocessor having two on-chip caches, in which the L2 cache is accessed at the same time the L1 cache is accessed regardless of whether there is a miss in the L1 cache.

[0021] FIG. 2 illustrates that portion of a conventional microprocessor having two on-chip caches in which the L2 cache is accessed only when there is a miss in the L1 cache.

[0022] FIG. 3 illustrates that portion of a microprocessor comprising an embodiment of the presently claimed invention in which there are two on-chip caches.

[0023] FIG. 4 is a graph of the distribution of L1 cache data read misses.

[0024] FIG. 5 is a graph of the distribution of L1 cache code access misses.

[0025] FIG. 6 is a block diagram which illustrates the detection, counting, comparison and prediction circuit(s) of one embodiment of the predictor circuit of FIGS. 3, 9 and 10.

[0026] FIG. 7 is a graph of the average number of instructions per cycle (“IPC”) as a function of the L2 cache data latency in processor cycles, using a predictor in accordance with one embodiment of the presently claimed invention.

[0027] FIG. 8 illustrates a portion of a cache hierarchy with N caches, in which all caches are accessed simultaneously.

[0028] FIG. 9 illustrates a portion of a cache hierarchy with N caches and an i^thpredictor placed at an i^thlevel of the cache hierarchy in accordance with another embodiment of the presently claimed invention, wherein the i^thpredictor enables or disables the i+1 through N levels based on the hit or miss prediction for level i.

[0029] FIG. 10 illustrates that portion of a cache hierarchy with an i^thpredictor placed at an i^thlevel of the cache hierarchy in accordance with another embodiment of the presently claimed invention, wherein the i^thpredictor enables or disables only the i+1 level cache based on the hit or miss prediction for level i. Here, the i+1 cache could have (but does not need to have) a predictor for enabling or disabling one or more higher-level caches. Subsequent higher-level caches (e.g., the i+2 cache, the i+3 cache, and so on) could also have predictors.

[0030] As shown in FIGS. 1 and 2, for the two-level cache organization, the following alternatives exist for the time at which the L2 cache 4 is accessed:

[0031] (a) Access the L2 cache 4 simultaneously with the L1 cache 2, irrespective of whether there will be a miss in the L1 cache 2, as shown in FIG. 1. This reduces the effective access time of the L2 cache 4 when the re is a miss in the L1 cache 2. However, this approach has the disadvantage of causing a high, useless power consumption in the L2 cache 4 when the data is provided by the L1 cache 2.

[0032] (b) Access the L2 cache 4 only when there is a miss in the L1 cache 2, as shown in FIG. 2. This results in a larger effective access time of the L2 cache 4 but has no useless power consumption.

[0033] To achieve the reduction in power consumption of approach (b) a CacheAccess input 6 is added that inhibits the pre-charging of the bit lines. Moreover, the address input is kept at the same value as for the previous access. In this situation, the cache does not consume any active power since no line toggles occur; the only source of power consumption is the static current.

[0034] As shown in FIG. 3, the proposed technique predicts the misses in the L1 cache 2 and accesses the L2 cache 4 concurrently with the L1 cache only in case a miss is predicted. On the other hand, if a hit is predicted the L2 cache 4 is only accessed if the prediction is incorrect; in this case the effective latency of the L2 cache 4 is increased by the first-level latency of the hit/miss determination.

[0035] The present invention is based on the observation that the distance (in L1 cache accesses) between consecutive L1 cache 2 misses is small. This fact is illustrated in FIGS. 4 and 5, where the percentage of L1 cache 2 misses is shown as a function of the number of consecutive LI cache 2 accesses that resulted in hits.

[0036] The following examples are based on simulations of one embodiment of the present invention applied to a two-level cache hierarchy, using the SPEC95 benchmark suite and SimpleScalar tool set, which will be described below. FIG. 4 indicates that around 25% of all data read misses in the L1 cache 2 occur after 4 consecutive hits from the previous miss and 65% occur within a distance of 10. FIG. 5 indicates that for code accesses, the distances are even smaller: around 85% of the code misses occur with a distance of 5 or less. The shape of these distributions depend mainly on the workload and on the cache structure.

[0037] Ideally, the L2 cache 4 should be accessed:

[0038] 1. Only when there is a miss in the L1 cache 2. This eliminates any unnecessary power consumption in the L2 cache 4; and

[0039] 2. Simultaneously with the L1 cache 2. This reduces the effective latency of the L2 cache 4.

[0040] Since when the L1 cache 2 is accessed it is not known yet whether there will be a miss, to achieve this operation it is necessary to predict the miss resulting in an organization as described in FIG. 3. A perfect prediction would achieve both characteristics above. On the other hand, an incorrect prediction of a miss (when there is a hit, but a miss was predicted) produces an unnecessary access to the L2 cache 4 and an incorrect prediction of a hit (when there is a miss, but a hit was predicted) results in a larger latency. Depending which of the two characteristics is most important, a predictor that predicts better misses or hits should be used. The extremes are given by the operation modes of FIGS. 1 and 2: the first case is equivalent to always predicting a miss and the second case to always predicting a hit.

[0041] In the present invention, a window of size S is defined. After a miss occurs it is predicted that the next miss will occur in the next S accesses to the L1 cache 2. If no miss occurs in these S accesses, a hit is predicted until the next miss. This method is used for code access and for data reads, since data writes are handled by means of a write buffer. Therefore, this method can have two parameters, S_cand S_d, that correspond to the window sizes for code accesses and data reads, respectively. Note that these two windows can be independent of each other. The distances between L1 cache 2 misses may be kept separately for code accesses and data reads.

[0042] As an example, S_dis set to 3. After a data read miss (the zeroth data read), we predict that the next data read miss will occur in the next 3 data reads (the first, second or third data reads) of L1. Therefore, a miss is predicted for the first data read access. Whether or not a miss occurs for the first data read access, another miss is predicted for the second data read. Again, whether or not a miss occurs during the second data read, a miss is predicted for the third data read. However, if 3 consecutive data reads have resulted in data read hits, then a data read hit is predicted until there is a data read miss.

[0043] One embodiment of this predictor circuit 8 is illustrated in FIG. 6. The predictor circuit 8 consists of one or more detection circuits 10, one or more counters 12 and one or more comparison circuits 14 to determine whether the distance in L1 cache 2 accesses is above or below the window size. The counters 12 may be saturating counters. The comparison circuits 14 may be very simple if the window size is, for example, a power of two.

[0044] In a preferred embodiment of the presently claimed invention, two detection circuits 10, counters 12 and comparison circuits 14 each are employed, one for data reads and the other for code accesses. Each counter 12 is reset by the corresponding misses and is incremented by each hit. A miss is predicted while the counter 12 is not saturated. If a hit is predicted, i.e., the counter 12 is saturated, the CacheAccess input 6 inhibits pre-charging of the bit lines, only the L1 cache 2 is accessed and thereafter power consumption is reduced. If a miss is predicted, the bit lines are pre-charged and both the L1 cache 2 and the L2 cache 4 are accessed simultaneously.

[0045] The method of the presently claimed invention has been evaluated through simulations using the SPEC95 benchmark suite. SPEC95, also known as SPEC CPU95, is a group of benchmarks established by the Standard Performance Evaluation Corporation (“SPEC”). SPEC benchmarks are widely accepted by computer scientists and engineers as standards against which to compare various aspects of computer systems. The SPEC95 benchmark suite is used by the microprocessing community as a set of standards against which to compare microprocessor configurations. See the discussions at http://open.specbench.org/, http://open.specbench.org/osg/ and http://open.specbench.org/osg/cpu95/. The SPEC95 benchmark suite is set forth in the first two columns of Table 1, below. The sets of input parameters used for simulations of the presently claimed invention are shown in the third column of Table 1.

[0046] On average, for a typical two-level cache organization, about 50% of the accesses of the second-level cache are saved, producing a reduction of about 0.5% in the average instructions per cycle (“IPC”) with respect to the case in which both caches are always accessed concurrently.

[0047] FIG. 7 shows the IPC obtained for different values of the L2 cache 4 latency, by simulating the execution of the SPEC95 benchmark suite on the SimpleScalar simulator, which is widely used in the research community of micro architecture for evaluating the performance of microprocessors. For a description of the SimpleScalar simulator, see D. Burger and T. M. Austin, “The SimpleScalar Tool Set, Version 2.0,” Technical Report #1324, Computer Sciences Department, Univ. of Wisconsin—Madison (June 1997) (http://www.cs.wisc.edu/mscalar/simplescalar.html). The architectural parameters listed below were used in the simulation.

[0048] The parameters in Table 2 are the default values used in the SimpleScalar simulator, except for the cache sizes (which are set to 2-way, 16 KB for the L1 cache 2, and 4-way, 128 KB for the unified L2 cache 4).

[0049] An IPC degradation of approximately 3% occurs when the L2 cache 4 latency increases from 3 to 4, or from 4 to 5 cycles. This degradation is smaller for larger latencies, and is around 2% when going from 5 to 6 or from 6 to 7 cycles. This IPC degradation may be too high for high-performance processors; however, the increment in internal power consumption due to the first approach, in which the effective L2 cache 4 latency is smaller, may also be a factor that prevents the microprocessor from being implemented. Thus, the proposed hardware algorithm reduces the useless power consumption due to the on-chip L2 cache 4 at the expense of slightly decreasing the IPC of the microprocessor.

[0050] To determine the effectiveness of the prediction policy, the fraction of correct predictions, for both misses and hits, when varying the size of the window are presented in Table 3. As expected, when the size of either window is increased, the corresponding prediction of misses improves and that of hits deteriorates.

[0051] The predictor presented in Kessler is also evaluated. This predictor is good in predicting the hits but has a poor performance in predicting the misses. The fraction of misses of the L1 cache 2 correctly predicted is related to the fraction of accesses to the L2 cache 4 which have a smaller latency. However, this has to be corrected by the misses to the L2 cache. The corresponding values are shown in Table 4 as Fast Hits, both for data and for code.

[0052] Similarly, the fraction of hits of the L1 cache 2 correctly predicted relates to the accesses of the L2 cache 4 that are saved. The fraction of accesses saved is given by this value with respect to the total number of accesses that would be required when the L2 cache 4 is accessed in every access of the L1 cache 2. Note that this total includes all the data writes.

[0053] The poor performance in predicting the L1 cache 2 misses of the predictor presented in Kessler results in an operation with a small number of fast L2 cache 4 hits, ie., a larger L2 cache 4 latency.

[0054] The fraction of fast accesses to the L2 cache 4 has an effect on the IPC. A simple estimate of this effect can be obtained by interpolating the values given in FIGS. 4 and 5. For instance, if the latency of the L2 cache 4 is 4 and 80% of the accesses are fast accesses, a degradation of 0.2×3=0.6% is expected. This would be obtained achieving a 60% of savings in the accesses to the L2 cache 4.

[0055] One benefit of the proposed method is the better prediction of misses in the L1 cache 2. This results in a lower L2 cache 4 latency degradation and consequently in a lower IPC degradation.

[0056] The foregoing description has been limited to the case of a microprocessor with two on-chip caches. However, the present invention applies to a microprocessor with any number of on-chip caches. FIG. 8 illustrates a microprocessor with N caches, wherein caches L12 through L_N30 are accessed simultaneously.

[0057] The presently claimed invention includes a method for reducing the power consumption of a multi-cache microprocessor, which dynamically predicts the misses of an i^th-level (L_i) cache. This method predicts the misses in L_iand accesses the i+1 level cache (L_i+1) concurrently with L_ionly if a miss is predicted. If a hit is predicted, L_i+1is accessed only if the prediction is incorrect. The prediction is based on the fact that misses occur in bursts which correspond to changes of the working set. A circuit implementing this technique occupies a very small area and its delay is not in the critical path of the microprocessor. The prediction is applied to reduce the number of unnecessary accesses to L_i+1, which translates to a reduction in power consumption in the L_i+1cache.

[0058] FIG. 9 illustrates that portion of a microprocessor in accordance with another embodiment of the presently claimed invention. Here, a prediction circuit 24 predicts hits or misses of an arbitrary cache L_i18. The prediction circuit 24 either enables or disables all levels of the cache hierarchy, caches L_i+120 through L_N30.

[0059] FIG. 10 illustrates that portion of a microprocessor in accordance with another embodiment of the presently claimed invention. Here, a prediction circuit 24 predicts hits or misses of an arbitrary cache L_i18. The prediction circuit 24 either enables or disables only the next level of the cache hierarchy, cache L_i+120. Cache L_i+120 could have—but need not have—another prediction circuit 26 which controls one or more of the caches L_i+128 through L_N30.

[0060] While the foregoing is a complete description of the preferred embodiment of the invention, various alternatives and modifications may be used. Therefore, the preferred embodiment should not be interpreted to limit the scope of the present invention, which is defined by the following claims.