Optimal eviction policies for stochastic address traces

DOI10.1016/J.TCS.2013.01.016MaRDI QIDQ386897zbMATH OpenOpenAlexFDO

Authors Gianfranco Bilardi, Francesco Versaci

Publication date 11 December 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.6643

zbMATH Keywords

Markov chainsmultiobjective optimizationoptimal controlpagingonline problemsalgorithms and data structureseviction policies

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Mathematical problems of computer architecture (68M07)

Abstract: The eviction problem for memory hierarchies is studied for the Hidden Markov Reference Model (HMRM) of the memory trace, showing how miss minimization can be naturally formulated in the optimal control setting. In addition to the traditional version assuming a buffer of fixed capacity, a relaxed version is also considered, in which buffer occupancy can vary and its average is constrained. Resorting to multiobjective optimization, viewing occupancy as a cost rather than as a constraint, the optimal eviction policy is obtained by composing solutions for the individual addressable items. This approach is then specialized to the Least Recently Used Stack Model (LRUSM), a type of HMRM often considered for traces, which includes V-1 parameters, where V is the size of the virtual space. A gain optimal policy for any target average occupancy is obtained which (i) is computable in time O(V) from the model parameters, (ii) is optimal also for the fixed capacity case, and (iii) is characterized in terms of priorities, with the name of Least Profit Rate (LPR) policy. An O(log C) upper bound (being C the buffer capacity) is derived for the ratio between the expected miss rate of LPR and that of OPT, the optimal off-line policy; the upper bound is tightened to O(1), under reasonable constraints on the LRUSM parameters. Using the stack-distance framework, an algorithm is developed to compute the number of misses incurred by LPR on a given input trace, simultaneously for all buffer capacities, in time O(log V) per access. Finally, some results are provided for miss minimization over a finite horizon and over an infinite horizon under bias optimality, a criterion more stringent than gain optimality.

Recommendations

• An optimality proof of the LRU- K page replacement algorithm
• A simple proof of optimality for the MIN cache replacement policy
• On adequate performance measures for paging
• On the separation and equivalence of paging strategies
• Probabilistic methods for web caching

Cites work

• scientific article; zbMATH DE number 5764846 (Why is no real title available?)
• scientific article; zbMATH DE number 5542186 (Why is no real title available?)
• scientific article; zbMATH DE number 53772 (Why is no real title available?)
• scientific article; zbMATH DE number 53773 (Why is no real title available?)
• scientific article; zbMATH DE number 3560401 (Why is no real title available?)
• scientific article; zbMATH DE number 1303583 (Why is no real title available?)
• scientific article; zbMATH DE number 1305458 (Why is no real title available?)
• scientific article; zbMATH DE number 1786115 (Why is no real title available?)
• A geometric framework for solving subsequence problems in computational biology efficiently
• A model of memory contention in a paging machine
• Algorithms – ESA 2004
• An efficient algorithm for determining the convex hull of a finite planar set
• Beyond Competitive Analysis
• Competitive paging with locality of reference
• Discrete Dynamic Programming
• Discrete-Time Controlled Markov Processes with Average Cost Criterion: A Survey
• Dynamic storage allocation in the Atlas computer, including an automatic use of a backing store
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Horizons of parallel computation
• LRU Stack Processing
• Markov Paging
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Minimization of demand paging for the LRU stack model of program behavior
• Multicriteria Optimization
• Nonlinear multiobjective optimization
• On adequate performance measures for paging
• On paging with locality of reference
• Some Distribution-Free Aspects of Paging Algorithm Performance
• The Complexity of Markov Decision Processes
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• The working set model for program behavior
• Use of the LRU stack depth distribution for simulation of paging behavior

This page was built for publication: Optimal eviction policies for stochastic address traces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386897)