The most common and generally best performing replacement algorithm in modern caches is LRU. Despite LRU's superiority, it is still possible that other feasible and implementable replacement policies could yield better performance. (34) found that an optimal replacement policy (OPT) would often have a miss rate 70% that of LRU. / If better replacement policies exist, they may not be obvious. One way to find better policies is to study a large number of address traces for common patterns. Such an undertaking involves such a large amount of data, that some automated method of generating and evaluating policies is required. Genetic Algorithms provide such a method, and have been used successfully on a wide variety of tasks (21). / The best replacement policy found using this approach had a mean improvement in overall hit rate of 0.6% over LRU for the benchmarks used. This corresponds to 27% of the 2.2% mean difference between LRU and OPT. Performance of the best of these replacement policies was found to be generally superior to shadow cache (33), an enhanced replacement policy similar to some of those used here.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.61096 |
| Date | January 1991 |
| Creators | Altman, Erik R. (Erik Richter) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Engineering (Department of Electrical Engineering.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 001271713, proquestno: AAIMM74699, Theses scanned by UMI/ProQuest. |
Page generated in 0.0016 seconds