Cost-Sensitive Cache Replacement Algorithms Export

@inproceedings{citeulike:4431945, abstract = {Cache replacement algorithms originally developed in the context of simple uniprocessor systems aim to reduce the miss count. However, in modern systems, cache misses have different costs. The cost may be latency, penalty, power consumption, bandwidth consumption, or any other ad-hoc numerical property attached to a miss. In many practical situations, it is desirable to inject the cost of a miss into the replacement policy.In this paper, we propose several extensions of LRU which account for non-uniform miss costs. These LRU extensions have simple implementations, yet they are very effective in various situations. We first explore the simple case of two static miss costs using trace-driven simulations to understand when cost-sensitive replacements are effective. We show that very large improvements of the cost function are possible in many practical cases.As an example of their effectiveness, we apply the algorithms to the second-level cache of a multiprocessor with superscalar processors, using the miss latency as the cost function. By applying our simple replacement policies sensitive to the latency of misses we can improve the execution time of some parallel applications by up to 18\%.}, address = {Washington, DC, USA}, author = {Jeong, Jaeheon and Dubois, Michel}, booktitle = {HPCA '03: Proceedings of the 9th International Symposium on High-Performance Computer Architecture}, citeulike-article-id = {4431945}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=822080.822804}, isbn = {0-7695-1871-0}, keywords = {bufman, cost, interesting, pagereplacement}, pages = {327+}, posted-at = {2009-04-29 05:41:12}, priority = {0}, publisher = {IEEE Computer Society}, title = {Cost-Sensitive Cache Replacement Algorithms}, url = {http://portal.acm.org/citation.cfm?id=822080.822804}, year = {2003} }

TY - CONF ID - citeulike:4431945 L3 - citeulike-article-id:4431945 N2 - Cache replacement algorithms originally developed in the context of simple uniprocessor systems aim to reduce the miss count. However, in modern systems, cache misses have different costs. The cost may be latency, penalty, power consumption, bandwidth consumption, or any other ad-hoc numerical property attached to a miss. In many practical situations, it is desirable to inject the cost of a miss into the replacement policy.In this paper, we propose several extensions of LRU which account for non-uniform miss costs. These LRU extensions have simple implementations, yet they are very effective in various situations. We first explore the simple case of two static miss costs using trace-driven simulations to understand when cost-sensitive replacements are effective. We show that very large improvements of the cost function are possible in many practical cases.As an example of their effectiveness, we apply the algorithms to the second-level cache of a multiprocessor with superscalar processors, using the miss latency as the cost function. By applying our simple replacement policies sensitive to the latency of misses we can improve the execution time of some parallel applications by up to 18%. SN - 0-7695-1871-0 AD - Washington, DC, USA TI - Cost-Sensitive Cache Replacement Algorithms PB - IEEE Computer Society T2 - HPCA '03: Proceedings of the 9th International Symposium on High-Performance Computer Architecture SP - 327 KW - bufman KW - cost KW - interesting KW - pagereplacement AU - Jeong, Jaeheon AU - Dubois, Michel PY - 2003/// UR - http://portal.acm.org/citation.cfm?id=822080.822804 ER -