An optimal reconstruction strategy of LRU stacks
By: Jun Kiniwa [and others]
Series: Working paper -- no. 188; Working paper (Kōbe Shōka Daigaku. Keizai Kenkyūjo) -- no. 188
Publisher: Institute of Economic Research, Kobe University of Commerce
Published: 2002
Place of publication: Kobe
Language: eng
Number of pages: 14
Subjects: Computer storage devices; Mathematical models; Parallel processing (Electronic computers); Cache memory
Description: We investigate an optimal reconstruction method for an implementation of LRU stacks. First we present our implementation of an LRU stack, where an array and a linked list are mixedly used. Then an effective way of reconstructing the stack can be considered by using the 'lazy update' technique proposed by Barriga and Ayani. Next we formulate the expected costs with remaining 'n' requests by dynamic programming. Analyzing the equations, we can obtain the optimal reconstruction timing of the stack, and some monotone results.- pg. 1.
Notes: "January, 2002."

Includes bibliographical references (leaf 14).