Estimating TLB Misses in BLIS-like GEMM

• Girlana Souza UNICAMP
• Lucas Wanner UNICAMP
• Isaías Felzmann UNICAMP

DOI: https://doi.org/10.5753/sscad.2026.34961

Resumo

Virtual memory introduces address-translation overhead that can affect the performance of highly optimized kernels such as General Matrix Multiplication (GEMM). While GEMM implementations such as BLIS employ hierarchical blocking and data packing to improve data locality, characterizing their impact on Translation Lookaside Buffer (TLB) behavior typically requires empirical hardware measurements. This work proposes an analytical model to estimate L1 and L2 TLB misses in BLIS-like GEMM implementations without requiring execution profiling. The model captures the matrix memory layout, loop hierarchy, and TLB configuration to derive virtual-page footprints, translation working sets, and reuse distances for both packed and unpacked BLIS-like GEMM variants. Experimental validation using hardware performance counters across varying workloads and page sizes (4 KiB and 2 MiB) shows that the model consistently captures the overall trends in translation pressure and provides an optimistic estimate of the absolute number of misses. Despite its structural simplifications, the model characterizes how GEMM configurations and packing strategies affect TLB behavior, including the trade-off between increased translation demand for small working sets and improved L1 TLB spatial locality for larger workloads. These results provide an analytical basis for studying translation behavior in GEMM and for guiding optimization decisions without requiring runtime performance-counter measurements.

Referências

Agredo, C., Koranek, D. F., Schubert Kabban, C. M., Gutierrez Del Arroyo, J. A., Langehaug, T. J., and Graham, S. R. (2025). Exploring the translation lookaside buffer (tlb) for low-level task differentiation and classification. IEEE Access, 13:111199–111216.

Basu, A., Gandhi, J., Chang, J., Hill, M. D., and Swift, M. M. (2013). Efficient virtual memory for big memory servers. ACM SIGARCH Computer Architecture News, 41(3):237–248.

Denning, P. J. (1970). Virtual memory. ACM Computing Surveys (CSUR), 2(3):153–189.

Denning, P. J. (2005). The locality principle. Commun. ACM, 48(7):19–24.

Dongarra, J. J., Du Croz, J., Hammarling, S., and Duff, I. S. (1990). A set of level 3 basic linear algebra subprograms. ACM Transactions on Mathematical Software (TOMS), 16(1):1–17.

Goto, K. and van de Geijn, R. A. (2008). Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software (TOMS), 34(3):1–25.

Hennessy, J., Patterson, D., and Asanović, K. (2012). Computer Architecture: A Quantitative Approach. Computer Architecture: A Quantitative Approach. Kaufmann.

Linux man-pages project (2026). perf_event_open(2) — linux manual page. [link]. System Calls Manual. Version 6.18.

Low, T. M., Igual, F. D., Smith, T. M., and Quintana-Orti, E. S. (2016). Analytical modeling is enough for high-performance blis. ACM Trans. Math. Softw., 43(2).

McKellar, A. and Coffman Jr, E. G. (1969). Organizing matrices and matrix operations for paged memory systems. Communications of the ACM, 12(3):153–165.

OpenMathLib (2026). Github - openmathlib/openblas: Openblas is an optimized blas library based on gotoblas2 1.13 bsd version. [link]. Accessed: 30 jul. 2026.

Salvador Rohwedder, C., Henderson, N., De Carvalho, J. P., Chen, Y., and Amaral, J. N. (2023). To pack or not to pack: A generalized packing analysis and transformation. In Proceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization, pages 14–27.

Van Zee, F. G. and Van De Geijn, R. A. (2015). Blis: A framework for rapidly instantiating blas functionality. ACM Transactions on Mathematical Software (TOMS), 41(3):1–33.

Zhang, J., Yang, W., Fang, J., Dong, D., and Chen, X. (2025). Flashgemm: Optimizing sequences of matrix multiplication by exploiting data reuse on cpus. ACM Transactions on Architecture and Code Optimization, 22(4):1–25.