DocumentCode
1380300
Title
On optimal replacement of nonuniform cache objects
Author
Hosseini-Khayat, Saied
Author_Institution
Dept. of Electr. Eng., Ferdowski Univ. of Mashad, Iran
Volume
49
Issue
8
fYear
2000
fDate
8/1/2000 12:00:00 AM
Firstpage
769
Lastpage
778
Abstract
This paper studies a generalized version of the well-known page replacement problem. It assumes that page sizes and page fault penalties are nonuniform. This problem arises in distributed information systems, in particular the World Wide Web. It is shown that finding an optimal solution of this problem is an NP-complete problem. A dynamic programming algorithm that finds an optimal solution is presented. Since this algorithm is inefficient, we explore modified algorithms that allow a trade-off between optimality and speed
Keywords
computational complexity; dynamic programming; information resources; paged storage; NP-complete problem; World Wide Web; distributed information systems; dynamic programming; nonuniform cache objects; optimal replacement; page fault penalties; page replacement problem; page sizes; Computer applications; Cost function; Distributed information systems; Dynamic programming; Heuristic algorithms; Large-scale systems; NP-complete problem; Web server; Web sites; Yarn;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.868024
Filename
868024
Link To Document