Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Patent
1997-03-14
1999-08-24
Cabeca, John W.
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
711133, 711135, G06F 1318
Patent
active
059436875
ABSTRACT:
Cache data replacement techniques enable improved performance in a computer system having a central processing unit (CPU), a cache memory and a main memory, wherein the cache memory has a plurality of data items stored therein. The cache data replacement techniques include associating a priority value with each of the stored data items, wherein for each data item, the priority value is an estimate of how much CPU stall time will occur if an attempt is made to retrieve the data item from the cache memory when the data item is not stored in the cache memory. When a cache entry must be replaced, the priority values are analyzed to determine a lowest priority value. One of the data items that has the lowest priority value is selected and replaced by a replacement data item. The priority value of a data item may be determined, as a function of how many other instructions have been fetched and stored in a buffer memory between a time interval defined by initiation and completion of retrieval of the data item from the main memory, wherein execution of the other instructions is dependent on completing retrieval of the data item. In other aspects of the invention, the priority values of cache entries may periodically be lowered in order to improve the cache hit ratio, and may also be reinitialized whenever the associated data item is accessed, in order to ensure retention of valuable data items in the data cache.
REFERENCES:
patent: 5546559 (1996-08-01), Kyushima
patent: 5555393 (1996-09-01), Tanaka
patent: 5649137 (1997-07-01), Favor
patent: 5671444 (1997-09-01), Akkary
patent: 5696932 (1997-12-01), Smith
patent: 5774685 (1998-06-01), Dubey
patent: 5787471 (1998-07-01), Inoue
"PowerPC 604, RISC Microprocessor User's Manual", pp. 1-3 and 1-7, published by Motorola Inc. in Nov. 1994.
David A. Patterson, et al., "Computer Architecture a Quantitative Approach", Second Edition, Morgan Kaufmann Publishers, Inc., pp. 374-385, published in 1990.
William Johnson, "Superscaler Microprocessor Design", P T R Prentice-Hall Inc., 1991, pp. 18-21.
"Algorithm for Instruction Cache Arbitration Among Multiple Instruction Streams," IBM Technical Disclosure Bulletin, vol. 39, No. 8, Aug. 1996, pp. 113-116.
D. K. Chia, et al., "Replacement Algorithm using Priority Class Structure," IBM Technical Disclosure Bulletin, vol. 15, No. 12, May 1973, pp. 3803-3805.
Jong-Hong Bae, et al., "A Supplementary Scheme for Reducing Cache Access Time," vol. E79-D, No. 4, Apr. 1996, pp. 385-387.
Cabeca John W.
Chow Christopher S.
Telefonakiebolaget LM Ericsson
LandOfFree
Penalty-based cache storage and replacement techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Penalty-based cache storage and replacement techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Penalty-based cache storage and replacement techniques will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-477138