Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2000-02-22
2002-02-26
Elmore, Reba I. (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S122000, C711S137000, C711S207000, C712S236000, C712S240000
Reexamination Certificate
active
06351796
ABSTRACT:
FIELD OF THE INVENTION
The invention pertains to the storage of data in a multi-level memory hierarchy, and more particularly, to methods and apparatus which increase the efficiency of a higher level cache in the hierarchy by selectively performing writes to the higher level cache.
BACKGROUND OF THE INVENTION
Most microprocessors use multi-level memory hierarchies to store information. For example, most of today's microprocessors store instructions and/or data in a main multi-level memory hierarchy comprising at least three tiers: a low level cache, a high level cache, and a main memory. The low and high level caches are typically implemented as tagged, n-way caches.
Lower levels in a memory hierarchy are designed to be faster than higher levels, while higher levels in a memory hierarchy are designed to store more information. As a result, lower levels in a memory hierarchy are usually much smaller than higher levels, and are constructed and managed in different ways.
The higher access speeds of lower levels come with a cost. This cost may include higher heat, more capacitance, greater development time and cost, and so on.
Most of the time, lower levels in a memory hierarchy simply store smaller subsets of the information which is maintained in higher levels. However, as will be described in the following sections of this disclosure, it is sometimes desirable to use a higher level of a memory hierarchy to store less than all of the information which is stored in a lower level of the memory hierarchy. In such a case, it has been found that the efficiency of the higher level structure can be increased by selectively performing writes to the higher level.
SUMMARY OF THE INVENTION
As computer architectures increasingly rely on parallelism, predication, speculation and the like, a processor's ability to generate and access accurate prediction information such as branch prediction information becomes critical. Heretofore, this need has been met by increasing the number of entries in prediction caches, or by implementing multi-stage prediction algorithms (see, e.g., “Alternative Implementations of Two-Level Adaptive Branch Prediction” by T. Yeh and Y. Patt (Association for Computing Machinery, July 1992). However, better methods and apparatus for managing prediction information such as branch prediction information are needed.
The invention comprises using a multi-level memory hierarchy to manage information (and particularly, prediction information) which is used by a microprocessor. By “multi-level memory hierarchy”, it is meant that the same type of prediction information is stored in more than one level of a memory hierarchy. The use of a multi-level memory hierarchy should not be confused with the use of a multi-level prediction algorithm such as that disclosed by Yeh and Patt, supra.
The multi-level memory hierarchy disclosed herein comprises a higher level cache and a lower level cache. In a preferred embodiment of the invention, the lower level cache stores branch prediction information for a number of branch instructions. One type of branch information stored in the lower level cache is branch history and trigger prediction information. Branch history information provides a historical taken
ot taken look at the behavior of a branch, and is therefore helpful in predicting the future outcomes (taken or not taken) of a branch. The next predicted outcome of a branch may be embodied in a single bit of trigger prediction information. While branch prediction information such as branch targets can be recalculated every time a branch instruction is fetched into a low level instruction cache, historical branch prediction information such as a branch history can only be recreated through repeated executions of a branch instruction. It has therefore been found that storing a backup of this information in a higher level cache which will not be as readily overwritten when new instructions are fetched into a low level instruction cache is desirable. Unfortunately, limited on-chip resources dictate that even this higher level cache cannot be made large enough to store every branch history which is generated. However, the efficiency of the higher level cache (e.g., the resistance to aliasing, etc.) can be increased by writing into the higher level cache only those branch histories which could not be recreated by a default initializer for the lower level cache.
For example, many branch instructions are stored with static and/or dynamic hint information. A default initializer for a lower level prediction information cache could initialize branch histories stored in the lower level prediction information cache to all logic zeros (if hint information indicates that a branch is usually not taken) or to all logic ones (if hint information indicates that a branch is usually taken). Since most branches are well behaved (i.e., they are typically always taken or always not taken; or they switch from being always taken to always not taken, or vice versa, only infrequently), many branch histories will never change from their default initialization. When this is the case, the storage of these default initialization values in a higher level cache provides no benefit over merely reinitializing the branch histories to their default values. The invention therefore avoids writing some or all default information into the higher level cache, except when the default information needs to overwrite a non-default value which has already been stored in the higher level cache.
In a preferred embodiment of the invention, the higher level cache is implemented as a non-tagged, n-way cache. In such a cache, redundant data is written into differently indexed locations in each of the cache's n ways. A hit is generated by the cache when data values read from a majority of the cache's n ways agree. As the volume of differently addressed data values written to the cache increases, it becomes more likely that a majority of the redundant copies of a data value will be overwritten, eventually leading to the cache generating a miss when an attempt is made to read a given data value. To reduce the volume of writes to such a cache, the invention avoids writing data into the cache when a prior attempt to read the cache has generated a cache miss and updated data which is being written to a lower level cache is simply a default value, or when a prior attempt to read the cache has generated a cache hit on a default value.
While the above summary of the invention particularly discusses the update of branch prediction information which is stored a higher level of a multi-level memory hierarchy, those skilled in the art will readily comprehend how other types of information might be selectively stored and updated in a multi-level memory hierarchy.
The above and other important advantages and objectives of the invention will be further explained in, or will become apparent from, the accompanying description, drawings and claims.
REFERENCES:
patent: 5859999 (1999-01-01), Morris et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 5922065 (1999-07-01), Hull et al.
patent: 5935241 (1999-08-01), Shiell et al.
patent: 5978909 (1999-11-01), Lempel
patent: 6108777 (2000-08-01), Puziol et al.
“Patents shed light on Merced” by Alexander Wolfe, Electronic Engineering Times, Feb. 15, 1999, pp. 43 and 44.
“Trading Conflict and Capacity Aliasing in Conditional Branch Predictors” by Michaud, et al., Proceedings of the 24th Annual International Symposium on Computer Architecture, 1997, 9 pages.
“Alternative Implementations of Two-Level Adaptive Branch Prediction”, by Tse-Yu Yeh, et al., Department of Electrical Engineering and Computer Science, University of Michigan, Jul. 1992, pp. 124-134.
“Intel's IA-64 Application Developer's Architecture Guide” (Rev 1.0, Order No. 245188-001, May 1999).
Internet Publication “The Alpha 21264 Microprocessor: Out-Of-Order Execution at 600 Mhz” by R.E. Kessler, Aug. 1998, pp. 1-30.
McCormick, Jr. James E
Saunders Steven Kenneth
Elmore Reba I.
Hewlett--Packard Company
LandOfFree
Methods and apparatus for increasing the efficiency of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for increasing the efficiency of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for increasing the efficiency of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2935270