公开(公告)号：FR2336769A1

公开(公告)日：1977-07-22

申请号：FR7636144

申请日：1976-11-24

Applicant: IBM

Inventor： BRYANT LOUIS R ,  PEDERSEN RAYMOND J ,  WEINBERGER ARNOLD

IPC: G06F12/12 ,  G11C8/00

Abstract: A digital LRU network in which a use value in a chronology register always appears to be increasing; it is incremented for each access to a different data block currently represented in an active LRU array and this use value is copied into an index for that block in an active use-value array. Special circuits are provided to maintain the appearance of continuously increasing use values. At the start of each array search, the special circuits check the chronology register to determine if its use value is nearing its highest registerable value by testing its two high order bits for 1's. If so, the chronology register is set to 100...0, which is higher than any use value in the active array, after the use values in the active array are shifted one bit position to the right by writing them into corresponding positions in another array, which then becomes the active array. The right shift drops the low-order bit in the use values and sets the high-order bit to zero. The right shift increases the range of use values that can subsequently be set into the active array without affecting the stored relationships among the existing use values, and enables the incrementing of use values to continue. The second array is used to permit overlap of the read cycle of one array with the write cycle of the other array.

公开(公告)号：CA1059643A

公开(公告)日：1979-07-31

申请号：CA268655

申请日：1976-12-23

Applicant: IBM

Inventor： BRYANT LOUIS R ,  PEDERSEN RAYMOND J ,  WEINBERGER ARNOLD

IPC: G06F12/12 ,  G06F7/10 ,  G11C9/06

Abstract: A CIRCUIT FOR IMPLEMENTING A MODIFIED LRU REPLACEMENT ALGORITHM FOR A CACHE The invention operates with a storage hierarchy buffer such as a cache, with an LRU network which utilizes two array memory chips, array selection and addressing controls, chronology controls, next LRU addressing circuits, and mode controls for controlling the different types of operations needed by the LRU network. Each time a different block is accessed in the cache, a next use value is generated in a chronology register in the chronology controls, and the new use value is written into the active one of the arrays at a position which corresponds to the position of the block to be replaced in the cache. An LRU determination is made when a cache miss occurs by making a search of the active array to find the position of the block with the lowest use value, which block position is thus determined to be the LRU. This LRU block address is then stored in the next LRU addressing circuits for use by the next block replacement in the cache, i.e. next miss.