Browse Prior Art Database

Usage Dependent Cache Replacement by Ring Partitioned Groupings

IP.com Disclosure Number: IPCOM000077199D
Original Publication Date: 1972-Jun-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 3 page(s) / 19K

Publishing Venue

IBM

Related People

Weinberger, A: AUTHOR

Abstract

At pages 430-432 of the July 1971 issue of the IBM Technical Disclosure Bulletin (Vol. 14, No. 2) there is described a cache replacement algorithm wherein cache blocks are partitioned into groups, subgroups, etc. in a "tree"-like array. Associated with these groups, subgroups,..., blocks are a number of usage tracking bits serving to control replacement selection. The number of such bits is fewer than the number required to track and exclusively designate the least recently used (LRU) block. Replacement selections conditioned upon combinations of these tracking bits have a high-statistical probability of being made in the LRU block and zero probability of being taken from the most recently used (MRU) block.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Usage Dependent Cache Replacement by Ring Partitioned Groupings

At pages 430-432 of the July 1971 issue of the IBM Technical Disclosure Bulletin (Vol. 14, No. 2) there is described a cache replacement algorithm wherein cache blocks are partitioned into groups, subgroups, etc. in a "tree"-like array. Associated with these groups, subgroups,..., blocks are a number of usage tracking bits serving to control replacement selection. The number of such bits is fewer than the number required to track and exclusively designate the least recently used (LRU) block. Replacement selections conditioned upon combinations of these tracking bits have a high-statistical probability of being made in the LRU block and zero probability of being taken from the most recently used (MRU) block.

Following is a description of a related partitioning algorithm based upon a ring grouping arrangement which is useful to provide finer gradations of replacement selection efficiency, measured in respect to numbers of tracking bits and probabilities of retention in the cache of recently used information blocks.

Ring grouping is illustrated in table 1 below for a primitive system of four blocks A,B,C,D. Bits 1-4, the tracking bits, are seen to be associated with respective groups: [A,B], [B,C], [C,D], [D,A]; from which the designation "ring grouping" is understood.

TABLE 1 Access/Replace Set/Select Replacement Based On Block Bit 1 Bit 2 Bit 3 Bit 4
A 1/0 x/x x/x 0/1
B 0/1 1/0 x/x x/x
C x/x 0/1 1/0 x/x
D x/x x/x 0/1 1/0 x/x = hold/ don't care.

The logic for replacement selection is given by: Select A if (bit 1).(bit 4)-F(A/C)

" B " (bit 1).(bit 2).F(B/D)

" C " (bit 2).(bit 3).G(C/A)

" D " (bit 3).(bit 4).G(D/B) where the binary functions F,G are used to resolve the selection when the tracking bit conditions for selection of the two subscript associated blocks exist coincidentally.

One useful set of selection resolving functions: F(A/C) = F(B/D) = Q G(C/A) = G(D/B) = Q can be based upon the state of a 1-bit counter Q which advances with successive replacement selections. Another set: F(A/C) = (Bit 2).(Bit 3) F(B/D) = (Bi...