{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:55:13Z","timestamp":1777676113494,"version":"3.51.4"},"reference-count":30,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T00:00:00Z","timestamp":1740009600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T00:00:00Z","timestamp":1740009600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["16ME0708"],"award-info":[{"award-number":["16ME0708"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:p>Sparse matrix-vector products (SpMVs) are a bottleneck in many scientific codes. Due to the heavy strain on the main memory interface from loading the sparse matrix and the possibly irregular memory access pattern, SpMV typically exhibits low arithmetic intensity. Repeating these products multiple times with the same matrix is required in many algorithms. This so-called matrix power kernel (MPK) provides an opportunity for data reuse since the same matrix data is loaded from main memory multiple times, an opportunity that has only recently been exploited successfully with the Recursive Algebraic Coloring Engine (RACE). Using RACE, one considers a graph based formulation of the SpMV and employs a level-based implementation of SpMV for the reuse of relevant matrix data. However, the underlying data dependencies have restricted the use of this concept to shared memory parallelization and thus to single compute nodes. Enabling cache blocking for distributed-memory parallelization of MPK is challenging due to the need for explicit communication and synchronization of data in neighboring levels. In this work, we propose and implement a flexible method that interleaves the cache-blocking capabilities of RACE with an MPI communication scheme that fulfills all data dependencies among processes. Compared to a \u201ctraditional\u201d distributed-memory parallel MPK, our new distributed level-blocked MPK yields substantial speed-ups on modern Intel and AMD architectures across a wide range of sparse matrices from various scientific applications. Finally, we address a modern quantum physics problem to demonstrate the applicability of our method, achieving a speed-up of up to 4\u00d7 on 832 cores of an Intel Sapphire Rapids cluster.<\/jats:p>","DOI":"10.1177\/10943420251319332","type":"journal-article","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T04:35:57Z","timestamp":1740026157000},"page":"385-404","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Cache blocking of distributed-memory parallel matrix power kernels"],"prefix":"10.1177","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5896-9646","authenticated-orcid":false,"given":"Dane","family":"Lacey","sequence":"first","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4548-8727","authenticated-orcid":false,"given":"Christie","family":"Alappat","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3389-1711","authenticated-orcid":false,"given":"Florian","family":"Lange","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8723-2781","authenticated-orcid":false,"given":"Georg","family":"Hager","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Holger","family":"Fehske","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"},{"name":"University of Greifswald"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard","family":"Wellein","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"},{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg"},{"name":"Delft University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2025,2,20]]},"reference":[{"key":"e_1_3_5_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3399732"},{"key":"e_1_3_5_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50743-5_21"},{"key":"e_1_3_5_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3223512"},{"key":"e_1_3_5_5_1","doi-asserted-by":"publisher","unstructured":"Alappat C Thies J Hager G et al. (2023) Algebraic temporal blocking for sparse iterative solvers on multi-core CPUs. The International Journal of High Performance Computing Applications. 2024;0(0). DOI: 10.1177\/10943420241283828.","DOI":"10.1177\/10943420241283828"},{"key":"e_1_3_5_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.109.1492"},{"key":"e_1_3_5_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_3_5_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2008.4536305"},{"key":"e_1_3_5_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physleta.2009.04.022"},{"key":"e_1_3_5_10_1","unstructured":"Gao J Liu B Ji W et al. (2024) A systematic literature survey of sparse matrix-vector multiplication. Preprint: arXiv:2404.06047."},{"key":"e_1_3_5_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.102.013303"},{"key":"e_1_3_5_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.105.L180202"},{"key":"e_1_3_5_13_1","unstructured":"Karypis G Kumar V (1998) METIS: a software package for partitioning unstructured graphs partitioning meshes and computing fill-reducing orderings of sparse matrices."},{"key":"e_1_3_5_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/130930352"},{"key":"e_1_3_5_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2015.70"},{"key":"e_1_3_5_16_1","doi-asserted-by":"publisher","DOI":"10.22489\/CinC.2019.301"},{"key":"e_1_3_5_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976137.4"},{"key":"e_1_3_5_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"issue":"148","key":"e_1_3_5_19_1","first-page":"1","article-title":"Megaman: scalable manifold learning in Python","volume":"17","author":"McQueen J","year":"2016","unstructured":"McQueen J, Meil\u0103 M, VanderPlas J, et al. (2016) Megaman: scalable manifold learning in Python. Journal of Machine Learning Research 17(148): 1\u20135.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_5_20_1","volume-title":"32th USENIX Security Symposium (USENIX Security 2023)","author":"Moghimi D","year":"2023","unstructured":"Moghimi D (2023) Downfall: exploiting speculative data gathering. In: 32th USENIX Security Symposium (USENIX Security 2023)."},{"key":"e_1_3_5_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654096"},{"key":"e_1_3_5_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.99.023629"},{"key":"e_1_3_5_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3218176.3218232"},{"key":"e_1_3_5_24_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.448136"},{"key":"e_1_3_5_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPPW.2010.38"},{"key":"e_1_3_5_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368474.3368494"},{"key":"e_1_3_5_27_1","unstructured":"Vuduc RW Demmel JW (2003) Automatic performance tuning of sparse matrix kernels. PhD Thesis University of California Berkeley. AAI3121741."},{"key":"e_1_3_5_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498765.1498785"},{"key":"e_1_3_5_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.48"},{"key":"e_1_3_5_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.81"},{"key":"e_1_3_5_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.56.12221"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/10943420251319332","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/10943420251319332","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/10943420251319332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:17:43Z","timestamp":1777450663000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/10943420251319332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,20]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["10.1177\/10943420251319332"],"URL":"https:\/\/doi.org\/10.1177\/10943420251319332","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,20]]}}}