An optimal replacement algorithm for balancing multi-module caches
Resumo
Multi-module caches consist of multiple parallel caches. Their goal increase level 1 data cache hit ratios by allowing more freedom in placing blocks in the cache. Balancing multi-module caches provide the opportunity to reorganise blocks by moving them between the cache modules, in an attempt to balance the amount of data stored in each module. This capability allows for even higher hit ratios. We present an algorithm to simulate optimal replacement in balancing multi-module caches. This algorithm is optimal since it minimizes the number of cache misses. However, it is infeasible to implement it in hardware. We discuss the effects of the set index functions used in the modules and the ways they interact. The algorithm is used to investigate three cache configurations and provide some performance limits for balancing multi-module caches.
Palavras-chave:
cache memory, multi-module cache, optimal replacement algorithm
Referências
A. Agarwal and S. D. Pudar. Column-associative caches: A technique for reducing the miss rate of direct mapped caches. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 179–190, IEEE, 1993.
D. Burger, T. M. Austin, and S. Bennett. Evaluating future microprocessors: The SimpleScalar tool set., Technical report, Computer Sciences Department, University of Wisconsin-Madison, July 1996.
G. Birkhoff and T. C. Bartee. Modern Applied Algebra. McGraw-Hill, 1970.
L. A. Belady. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal, 5(2):78–101, 1966.
F. Bodin and A. Seznec. Skewed associativity enhances performance predictability. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 255–274, June 1993.
P. Dinda, T. Gross, D. O'Hallaron, E. Segall, J. Stichnoth, J. Subhlok, J. Webb, and B. Yang. The CMU task parallel program suite. Technical Report CMU-CS-94-131, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, March 1994.
A. Gonzalez, C. Aliagas, and M. Valero. A data cache with multiple caching strategies tuned to different types of locality. In ICS’95. Proceedings of the 9th ACM International Conference on Supercomputing, pages 338–347, 1995.
T. Horel and G. Lauterbach. UltraSPARC-III: Designing third-generation 64-bit performance. IEEE Micro, 19(3):73–85, May 1999.
M. D. Hill and A. J. Smith. Evaluating associativity in CPU caches. IEEE Transactions on Computers, 38(12):1612–1630, December 1989.
C. Lee, M. Potkonjak, and W. H. Mangione-Smith. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the 30th Conference on Microprogramming and Microarchitecture, pages 330–335, December 1997.
R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78–117, 1970.
J. A. Rivers, E. S. Tam, G. S. Tyson, E. S. Davidson, and M. Farrens. Utilizing reuse information in data cache management. In ICS’98. Proceedings of the 1998 International Conference on Supercomputing, pages 449–456, 1998.
R. A. Sugumar and S. G. Abraham. Efficient simulation of caches under optimal replacement with applications to miss characterization. In SIGMETRICS’93. Proceedings of the 1993 ACM Conference on Measurement and Modeling of Computer Systems, pages 24–35, 1993.
A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons Ltd., 1986.
A. Seznec. A case for two-way skewed associative caches. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 169–178, May 1993.
A. Seznec. A new case for skewed-associativity. Technical Report PI-1114, IRISA, July 1997.
J. Sánchez and A. González. A locality sensitive multi-module cache with explicit management. In ICS’99. Proceedings of the 1999 International Conference on Supercomputing, pages 51–59, Rhodes, Greece, June 1999.
E. S. Tam. Improving Cache Performance Via Active Management. PhD thesis, University of Michigan, 1999.
O. Temam. Investigating optimal local memory performance. In Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 218–227, November 1998.
G. Tyson, M. Farrens, J. Matthews, and A. R. Pleszkun. A modified approach to data cache management. In Proceedings of the 28th Annual International Symposium on Microarchitecture, pages 93–103, December 1995.
D. Burger, T. M. Austin, and S. Bennett. Evaluating future microprocessors: The SimpleScalar tool set., Technical report, Computer Sciences Department, University of Wisconsin-Madison, July 1996.
G. Birkhoff and T. C. Bartee. Modern Applied Algebra. McGraw-Hill, 1970.
L. A. Belady. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal, 5(2):78–101, 1966.
F. Bodin and A. Seznec. Skewed associativity enhances performance predictability. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 255–274, June 1993.
P. Dinda, T. Gross, D. O'Hallaron, E. Segall, J. Stichnoth, J. Subhlok, J. Webb, and B. Yang. The CMU task parallel program suite. Technical Report CMU-CS-94-131, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, March 1994.
A. Gonzalez, C. Aliagas, and M. Valero. A data cache with multiple caching strategies tuned to different types of locality. In ICS’95. Proceedings of the 9th ACM International Conference on Supercomputing, pages 338–347, 1995.
T. Horel and G. Lauterbach. UltraSPARC-III: Designing third-generation 64-bit performance. IEEE Micro, 19(3):73–85, May 1999.
M. D. Hill and A. J. Smith. Evaluating associativity in CPU caches. IEEE Transactions on Computers, 38(12):1612–1630, December 1989.
C. Lee, M. Potkonjak, and W. H. Mangione-Smith. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the 30th Conference on Microprogramming and Microarchitecture, pages 330–335, December 1997.
R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78–117, 1970.
J. A. Rivers, E. S. Tam, G. S. Tyson, E. S. Davidson, and M. Farrens. Utilizing reuse information in data cache management. In ICS’98. Proceedings of the 1998 International Conference on Supercomputing, pages 449–456, 1998.
R. A. Sugumar and S. G. Abraham. Efficient simulation of caches under optimal replacement with applications to miss characterization. In SIGMETRICS’93. Proceedings of the 1993 ACM Conference on Measurement and Modeling of Computer Systems, pages 24–35, 1993.
A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons Ltd., 1986.
A. Seznec. A case for two-way skewed associative caches. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 169–178, May 1993.
A. Seznec. A new case for skewed-associativity. Technical Report PI-1114, IRISA, July 1997.
J. Sánchez and A. González. A locality sensitive multi-module cache with explicit management. In ICS’99. Proceedings of the 1999 International Conference on Supercomputing, pages 51–59, Rhodes, Greece, June 1999.
E. S. Tam. Improving Cache Performance Via Active Management. PhD thesis, University of Michigan, 1999.
O. Temam. Investigating optimal local memory performance. In Proceedings of the 8th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 218–227, November 1998.
G. Tyson, M. Farrens, J. Matthews, and A. R. Pleszkun. A modified approach to data cache management. In Proceedings of the 28th Annual International Symposium on Microarchitecture, pages 93–103, December 1995.
Publicado
24/10/2000
Como Citar
VANDIERENDONCK, Hans; BOSSCHERE, Koen De.
An optimal replacement algorithm for balancing multi-module caches. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 12. , 2000, São Pedro/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2000
.
p. 65-72.
DOI: https://doi.org/10.5753/sbac-pad.2000.41205.
