Coherence State Awareness in Way-Replacement Algorithms for Multicore Processors
Resumo
Due to their performance impact on program execution, cache replacement policies in set-associative caches have been studied in great depth. Currently, most general-purpose processors are multi-core, and among the very large corpus of research, and much to our surprise, we could not find any replacement policy that does actually take into account information relative to the sharing state of a cache way. Therefore, in this paper we propose to add, as a complement to the classical time-based related way-selection algorithms, an information relative to the sharing state and number of sharers of the ways. We propose several approaches to take this information into account, and our simulations show that LRU-based replacement policies can be slightly improved by them. Also, a much simpler policy, MRU, can be improved by our strategies, presenting up to 3.5× more IPC than baseline, and up to 82% less cache misses.
Referências
Agarwal, T. K. (2015). Cache coherence state based replacement policies. Master’s thesis.
Bang, D.-J., Kee, M.-K., Lim, H.-Y., and Park, G.-H. (2018). An adaptive cache replacement policy based on fine-grain reusability monitor. IEICE Electronics Express, 15(2):20171099.
Bélády, L. A., Nelson, R. A., and Shedler, G. S. (1969). An anomaly in space-time characteristics of certain programs running in a paging machine. Communications of the ACM, 12(6):349–353.
Carlson, T. E., Heirman, W., Eyerman, S., Hur, I., and Eeckhout, L. (2014). An evaluation of high-level mechanistic core models. ACM Trans. on Architecture and Code Optimization (TACO).
Conti, C. J., Gibson, D. H., and Pitkowsky, S. H. (1968). Structural aspects of the system/360 model 85, i: General organization. IBM Systems Journal, 7(1):2–14.
de Dinechin, B. D., Ayrignac, R., Beaucamps, P. E., Couvert, P., Ganne, B., de Massas, P. G., Jacquet, F., Jones, S., Chaisemartin, N. M., Riss, F., and Strudel, T. (2013). A clustered manycore processor architecture for In 2013 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–6. embedded and accelerated applications.
Hennessy, J. L. and Patterson, D. A. (2003). Computer architecture, a quantitative approach, chapter 1.6, Quantitative Principles of Computer Design, pages 42–45. Morgan Kaufmann Publisher, Inc.
Jaleel, A., Theobald, K. B., Steely, Jr., S. C., and Emer, J. (2010). High performance cache replacement using re-reference interval prediction (RRIP). SIGARCH Comput. Archit. News, 38(3):60–71.
Lathigara, P., Balachandran, S., and Singh, V. (2015). Application behavior aware re-reference interval prediction for shared LLC. In IEEE International Conference on Computer Design (ICCD), pages 172–179.
Li, S., Ahn, J. H., Strong, R. D., Brockman, J. B., Tullsen, D. M., and Jouppi, N. P. (2009) Mcpat: An integrated power, area, and timing modeling framework for multicore and manycore architectures. In IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 469–480.
Mounes-Toussi, F. and Lilja, D. J. (1998) The effect of using state-based priority information in a shared-memory multiprocessor cache replacement policy. In Proceedings. 1998 International Conference on Parallel Processing (Cat. No.98EX205), pages 217–224.
Pai, S., Singh, N., and Singh, V. (2018). AB-Aware: application behavior aware management of shared last level caches. In Great Lakes Symposium on VLSI, GLSVLSI ’18, pages 237–242, New York, NY, USA. ACM.
Rao, G. S. (1978). Performance analysis of cache memories. Journal of the ACM, 25(3):378–395.
Smith, A. J. (1978). A comparative study of set associative memory mapping algorithms and their use for cache and main memory. IEEE Trans. on Software Engineering, (2):121–130.
Tada, J. (2018). A cache replacement policy with considering global fluctuations of priority values. In International Symposium on Computing and Networking Workshops (CANDARW), pages 383–386. IEEE Computer Society.
Vakil-Ghahani, A., Mahdizadeh-Shahri, S., Lotfi-Namin, M., Bakhshalipour, M., Lotfi-Kamran, P., and Sarbazi-Azad, H. (2018). Cache replacement policy based on expected hit count. IEEE Computer Architecture Letters, 17(1):64–67.
Woo, S. C., Ohara, M., Torrie, E., Singh, J. P., and Gupta, A. (1995). The SPLASH-2 programs: Characterization and methodological considerations. SIGARCH Comput. Archit. News, 23(2):24–36.
Zahran, M. (2007). Cache replacement policy revisited. WDDD held in conjunction with ISCA, pages 1–8.
Bang, D.-J., Kee, M.-K., Lim, H.-Y., and Park, G.-H. (2018). An adaptive cache replacement policy based on fine-grain reusability monitor. IEICE Electronics Express, 15(2):20171099.
Bélády, L. A., Nelson, R. A., and Shedler, G. S. (1969). An anomaly in space-time characteristics of certain programs running in a paging machine. Communications of the ACM, 12(6):349–353.
Carlson, T. E., Heirman, W., Eyerman, S., Hur, I., and Eeckhout, L. (2014). An evaluation of high-level mechanistic core models. ACM Trans. on Architecture and Code Optimization (TACO).
Conti, C. J., Gibson, D. H., and Pitkowsky, S. H. (1968). Structural aspects of the system/360 model 85, i: General organization. IBM Systems Journal, 7(1):2–14.
de Dinechin, B. D., Ayrignac, R., Beaucamps, P. E., Couvert, P., Ganne, B., de Massas, P. G., Jacquet, F., Jones, S., Chaisemartin, N. M., Riss, F., and Strudel, T. (2013). A clustered manycore processor architecture for In 2013 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–6. embedded and accelerated applications.
Hennessy, J. L. and Patterson, D. A. (2003). Computer architecture, a quantitative approach, chapter 1.6, Quantitative Principles of Computer Design, pages 42–45. Morgan Kaufmann Publisher, Inc.
Jaleel, A., Theobald, K. B., Steely, Jr., S. C., and Emer, J. (2010). High performance cache replacement using re-reference interval prediction (RRIP). SIGARCH Comput. Archit. News, 38(3):60–71.
Lathigara, P., Balachandran, S., and Singh, V. (2015). Application behavior aware re-reference interval prediction for shared LLC. In IEEE International Conference on Computer Design (ICCD), pages 172–179.
Li, S., Ahn, J. H., Strong, R. D., Brockman, J. B., Tullsen, D. M., and Jouppi, N. P. (2009) Mcpat: An integrated power, area, and timing modeling framework for multicore and manycore architectures. In IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 469–480.
Mounes-Toussi, F. and Lilja, D. J. (1998) The effect of using state-based priority information in a shared-memory multiprocessor cache replacement policy. In Proceedings. 1998 International Conference on Parallel Processing (Cat. No.98EX205), pages 217–224.
Pai, S., Singh, N., and Singh, V. (2018). AB-Aware: application behavior aware management of shared last level caches. In Great Lakes Symposium on VLSI, GLSVLSI ’18, pages 237–242, New York, NY, USA. ACM.
Rao, G. S. (1978). Performance analysis of cache memories. Journal of the ACM, 25(3):378–395.
Smith, A. J. (1978). A comparative study of set associative memory mapping algorithms and their use for cache and main memory. IEEE Trans. on Software Engineering, (2):121–130.
Tada, J. (2018). A cache replacement policy with considering global fluctuations of priority values. In International Symposium on Computing and Networking Workshops (CANDARW), pages 383–386. IEEE Computer Society.
Vakil-Ghahani, A., Mahdizadeh-Shahri, S., Lotfi-Namin, M., Bakhshalipour, M., Lotfi-Kamran, P., and Sarbazi-Azad, H. (2018). Cache replacement policy based on expected hit count. IEEE Computer Architecture Letters, 17(1):64–67.
Woo, S. C., Ohara, M., Torrie, E., Singh, J. P., and Gupta, A. (1995). The SPLASH-2 programs: Characterization and methodological considerations. SIGARCH Comput. Archit. News, 23(2):24–36.
Zahran, M. (2007). Cache replacement policy revisited. WDDD held in conjunction with ISCA, pages 1–8.
Publicado
08/11/2019
Como Citar
SOUZA, Matheus; FREITAS, Henrique Cota; PÉTROT, Frédéric.
Coherence State Awareness in Way-Replacement Algorithms for Multicore Processors. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 20. , 2019, Campo Grande.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 240-251.
DOI: https://doi.org/10.5753/wscad.2019.8672.
