LP-GEMM: Integrating Layout Propagation into GEMM Operations
Resumo
High-Performance Computing and Machine Learning workloads spend much of their time in chains of dependent Matrix Multiplications (GEMMs), but GEMM implementations, such as those in most BLAS libraries, optimize each call in isolation, missing cross-call redundancy. We present LP-GEMM, a decomposition of the OpenBLAS GEMM kernel into Initial, Intermediate and Ending kernels propagating the packed layout through a chain, with BLAS-correct endpoints. LP-GEMM on 14 GEMM chains using one thread of an x86 (AVX-512) CPU, and excluding conversions at the chain’s end, is within 7% of the fastest of five libraries on 8 of the 14 chains and faster on three. In a parallelism experiment, LP-GEMM scales like OpenBLAS across 1–24 threads.
Referências
Alman, J., Duan, R., Vassilevska Williams, V., Xu, Y., Xu, Z., and Zhou, R. (2025). More asymmetry yields faster matrix multiplication. In Azar, Y. and Panigrahi, D., editors, SODA’2025, pages 2005–2039.
Devlin, J., Chang, M., Lee, K., and Toutanova, K. (2019). BERT: pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT’2019.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. (2021). An image is worth 16x16 words: Transformers for image recognition at scale. In 9th International Conference on Learning Representations, ICLR.
Genc, H., Kim, S., Amid, A., Haj-Ali, A., Iyer, V., Prakash, P., Zhao, J., Grubb, D., Liew, H., Mao, H., Ou, A. J., Schmidt, C., Steffl, S., Wright, J. C., Stoica, I., Ragan-Kelley, J., Asanovic, K., Nikolic, B., and Shao, Y. S. (2021). Gemmini: Enabling systematic deep-learning architecture evaluation via full-stack integration. In DAC’2021.
Golub, G. H. and Van Loan, C. F. (2013). Matrix Computations. Johns Hopkins University Press, 4th edition.
Goto, K. and van de Geijn, R. A. (2008). Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software (TOMS), 34:1–25.
Intel Corporation (2024). Intel math kernel library (Intel MKL). [link]. Accessed: 2025-12-10.
Kim, H., Ye, G., Wang, N., Yazdanbakhsh, A., and Kim, N. S. (2024). Exploiting Intel advanced matrix extensions (AMX) for large language model inference. IEEE Comput. Archit. Lett., 23(1):117–120.
Lam, M. D., Rothberg, E. E., and Wolf, M. E. (1991). The cache performance and optimizations of blocked algorithms. ACM SIGOPS Operating Systems Review, 25(Special Issue):63–74.
Li, J., Qin, Z., Mei, Y., Cui, J., Song, Y., Chen, C., Zhang, Y., Du, L., Cheng, X., Jin, B., Zhang, Y., Ye, J., Lin, E., and Lavery, D. (2024a). oneDNN graph compiler: A hybrid approach for high-performance deep learning compilation. In Grosser, T., Dubach, C., Steuwer, M., Xue, J., Ottoni, G., and Pereira, F. M. Q., editors, IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2024, Edinburgh, United Kingdom, March 2-6, 2024, pages 460–470. IEEE.
Li, M., Liu, C., Liao, J., Zheng, X., Yang, H., Sun, R., Xu, J., Gan, L., Yang, G., Luan, Z., and Qian, D. (2024b). Towards optimized tensor code generation for deep learning on sunway many-core processor. Frontiers Comput. Sci., 18:182101.
Liu, Y., Wang, Y., Yu, R., Li, M., Sharma, V., and Wang, Y. (2019). Optimizing CNN model inference on CPUs. In USENIX ATC’19, pages 1025–1040.
Meta’s Llama 3 team (2024). The Llama 3 herd of models. arXiv e-prints.
Naumov, M., Mudigere, D., et al. (2019). Deep learning recommendation model for personalization and recommendation systems. CoRR, abs/1906.00091.
NVIDIA Corporation (2024). cuBLAS: CUDA basic linear algebra subroutines. [link]. Accessed: 2025-12-10.
Pouchet, L.-N. and Yuki, T. (2016). PolyBench/C 4.2: The polyhedral benchmark suite. [link].
Rohwedder, C. S., Henderson, N., De Carvalho, J. P. L., Chen, Y., and Amaral, J. N. (2023). To pack or not to pack: A generalized packing analysis and transformation. In CGO’23, page 14–27.
Simonyan, K. and Zisserman, A. (2015). Very deep convolutional networks for large-scale image recognition. In 3rd International Conference on Learning Representations, ICLR.
The Netlib (2025). BLAS (Basic Linear Algebra Subprograms). [link]. Accessed: 2025-11-25.
Van Zee, F. G. and van de Geijn, R. A. (2015). BLIS: A framework for rapidly instantiating BLAS functionality. ACM Transactions on Mathematical Software, 41(3):14:1–14:33.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is all you need. In NeurIPS’17.
Wolfe, M. J., Shanklin, C., and Ortega, L. (1995). High Performance Compilers for Parallel Computing. Addison-Wesley Longman Publishing Co., Inc.
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 Trans. Archit. Code Optim., 22(4).
Devlin, J., Chang, M., Lee, K., and Toutanova, K. (2019). BERT: pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT’2019.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. (2021). An image is worth 16x16 words: Transformers for image recognition at scale. In 9th International Conference on Learning Representations, ICLR.
Genc, H., Kim, S., Amid, A., Haj-Ali, A., Iyer, V., Prakash, P., Zhao, J., Grubb, D., Liew, H., Mao, H., Ou, A. J., Schmidt, C., Steffl, S., Wright, J. C., Stoica, I., Ragan-Kelley, J., Asanovic, K., Nikolic, B., and Shao, Y. S. (2021). Gemmini: Enabling systematic deep-learning architecture evaluation via full-stack integration. In DAC’2021.
Golub, G. H. and Van Loan, C. F. (2013). Matrix Computations. Johns Hopkins University Press, 4th edition.
Goto, K. and van de Geijn, R. A. (2008). Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software (TOMS), 34:1–25.
Intel Corporation (2024). Intel math kernel library (Intel MKL). [link]. Accessed: 2025-12-10.
Kim, H., Ye, G., Wang, N., Yazdanbakhsh, A., and Kim, N. S. (2024). Exploiting Intel advanced matrix extensions (AMX) for large language model inference. IEEE Comput. Archit. Lett., 23(1):117–120.
Lam, M. D., Rothberg, E. E., and Wolf, M. E. (1991). The cache performance and optimizations of blocked algorithms. ACM SIGOPS Operating Systems Review, 25(Special Issue):63–74.
Li, J., Qin, Z., Mei, Y., Cui, J., Song, Y., Chen, C., Zhang, Y., Du, L., Cheng, X., Jin, B., Zhang, Y., Ye, J., Lin, E., and Lavery, D. (2024a). oneDNN graph compiler: A hybrid approach for high-performance deep learning compilation. In Grosser, T., Dubach, C., Steuwer, M., Xue, J., Ottoni, G., and Pereira, F. M. Q., editors, IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2024, Edinburgh, United Kingdom, March 2-6, 2024, pages 460–470. IEEE.
Li, M., Liu, C., Liao, J., Zheng, X., Yang, H., Sun, R., Xu, J., Gan, L., Yang, G., Luan, Z., and Qian, D. (2024b). Towards optimized tensor code generation for deep learning on sunway many-core processor. Frontiers Comput. Sci., 18:182101.
Liu, Y., Wang, Y., Yu, R., Li, M., Sharma, V., and Wang, Y. (2019). Optimizing CNN model inference on CPUs. In USENIX ATC’19, pages 1025–1040.
Meta’s Llama 3 team (2024). The Llama 3 herd of models. arXiv e-prints.
Naumov, M., Mudigere, D., et al. (2019). Deep learning recommendation model for personalization and recommendation systems. CoRR, abs/1906.00091.
NVIDIA Corporation (2024). cuBLAS: CUDA basic linear algebra subroutines. [link]. Accessed: 2025-12-10.
Pouchet, L.-N. and Yuki, T. (2016). PolyBench/C 4.2: The polyhedral benchmark suite. [link].
Rohwedder, C. S., Henderson, N., De Carvalho, J. P. L., Chen, Y., and Amaral, J. N. (2023). To pack or not to pack: A generalized packing analysis and transformation. In CGO’23, page 14–27.
Simonyan, K. and Zisserman, A. (2015). Very deep convolutional networks for large-scale image recognition. In 3rd International Conference on Learning Representations, ICLR.
The Netlib (2025). BLAS (Basic Linear Algebra Subprograms). [link]. Accessed: 2025-11-25.
Van Zee, F. G. and van de Geijn, R. A. (2015). BLIS: A framework for rapidly instantiating BLAS functionality. ACM Transactions on Mathematical Software, 41(3):14:1–14:33.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is all you need. In NeurIPS’17.
Wolfe, M. J., Shanklin, C., and Ortega, L. (1995). High Performance Compilers for Parallel Computing. Addison-Wesley Longman Publishing Co., Inc.
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 Trans. Archit. Code Optim., 22(4).
Publicado
03/11/2026
Como Citar
CARNEIRO, César G.; ALVARENGA, Lucas F.; ARAUJO, Guido C.; RIGO, Sandro.
LP-GEMM: Integrating Layout Propagation into GEMM Operations. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 27. , 2026, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 623-636.
DOI: https://doi.org/10.5753/sscad.2026.34995.
