Browse Prior Art Database

Biased Partitioned LRU Cache Replacement Control

IP.com Disclosure Number: IPCOM000088286D
Original Publication Date: 1977-May-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Weiner, AM: AUTHOR

Abstract

The cache control is applicable to processors using a store-in cache and operating as part of a tightly-coupled multiprocessing configuration. A performance penalty can be incurred on such a configuration when reference is made by one processor, CPU A, to a block which resides in the cache of another processor, CPU B, and which has been modified by that processor (CPU B). The penalty exists if the processor design requires that the referenced block be stored in the backing store by CPU B and then fetched from the backing store by CPU A. The penalty in this case is the amount of time required for CPU B to store the referenced block in the backing store.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 80% of the total text.

Page 1 of 1

Biased Partitioned LRU Cache Replacement Control

The cache control is applicable to processors using a store-in cache and operating as part of a tightly-coupled multiprocessing configuration. A performance penalty can be incurred on such a configuration when reference is made by one processor, CPU A, to a block which resides in the cache of another processor, CPU B, and which has been modified by that processor (CPU B). The penalty exists if the processor design requires that the referenced block be stored in the backing store by CPU B and then fetched from the backing store by CPU A. The penalty in this case is the amount of time required for CPU B to store the referenced block in the backing store.

The cache control described herein has the effect of reducing the likelihood that a request for a block by CPU A will find that block residing in a modified state in the cache of CPU B. This is accomplished by biasing the partitioned LRU (least recently used) replacement algorithm so that a modified block is replaced more rapidly than if the block had been referenced but not modified.

The biased partitioned LRU replacement control places a newly-referenced and unmodified block at the top (i.e., most recently used block) of the LRU stack, as is done in standard partitioned LRU algorithms, but the biased algorithm places a newly-modified block at some position in the LRU stack other than at the top of the LRU stack, e.g., in the middle of the stack. To maximize bias, a...