{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,17]],"date-time":"2026-10-17T16:17:09Z","timestamp":1792253829602,"version":"4.4.0"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T00:00:00Z","timestamp":1784851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/legalcode"}],"funder":[{"name":"National Key Research & Development Program of China","award":["2023YFB3001700"],"award-info":[{"award-number":["2023YFB3001700"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62372432"],"award-info":[{"award-number":["62372432"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Emerging AI accelerators equipped with large-capacity scratchpad memory (SPM) provide high computational throughput and large on-chip storage capacity. However, for memory-bound HPC algorithms such as fast Fourier transform (FFT), the hierarchical SPM organization cannot be fully exploited, leading to underutilized compute resources and exacerbated bandwidth bottlenecks. In this article, we propose PyramidFFT, a memory-efficient FFT system co-designed for AI accelerators with large-capacity SPM. PyramidFFT leverages large-capacity SPM to address the memory-bound problem of FFT through three key techniques: Memory-Aware Nested Network Design tightly couples FFT computation with the memory hierarchy to reduce memory access frequency; Matrix-Aligned Butterfly Layout Optimization, which dynamically adjusts butterfly parallelism and transforms the FFT data layout to better utilize Tensor Core Units (TCUs); Symmetry-Driven Real FFT Compression, which removes conjugate symmetric components in real FFT to further ease memory pressure. The results demonstrate that PyramidFFT mitigates memory-bound limitations, achieving up to an 8.2\u00d7 efficiency improvement over the baseline without memory-hierarchy mapping. By aligning with the structural characteristics of large-capacity SPM, PyramidFFT bridges the gap between FFT\u2019s memory-bound behavior and the compute-dense design of modern AI accelerators, demonstrating the effectiveness of architecture-aware FFT co-design on SPM-based systems.<\/jats:p>","DOI":"10.1145\/3819240","type":"journal-article","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T20:56:56Z","timestamp":1781297816000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["PyramidFFT: Rearchitecting FFT with Matrix-Aligned Nested-Radix for Hierarchical Scratchpad Memory on AI Accelerators"],"prefix":"10.1145","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-2432-6507","authenticated-orcid":false,"given":"Xiang","family":"Zhao","sequence":"first","affiliation":[{"name":"The College of Computer Science and Technology, Ocean University of China","place":["Qingdao, China"]},{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Qingdao, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-7526-8980","authenticated-orcid":false,"given":"Ruge","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]},{"name":"School of Computer Science and Technology, University of the Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9855-5367","authenticated-orcid":false,"given":"Haipeng","family":"Jia","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1013-1325","authenticated-orcid":false,"given":"Kun","family":"Li","sequence":"additional","affiliation":[{"name":"Institute for AI Industry Research (AIR), Tsinghua University","place":["Beijing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-8190-7000","authenticated-orcid":false,"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"The College of Computer Science and Technology, Ocean University of China","place":["Qingdao, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9107-013X","authenticated-orcid":false,"given":"Ting","family":"Cao","sequence":"additional","affiliation":[{"name":"Institute for AI Industry Research (AIR), Tsinghua University","place":["Beijing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7352-8955","authenticated-orcid":false,"given":"Yunxin","family":"Liu","sequence":"additional","affiliation":[{"name":"Institute for AI Industry Research (AIR), Tsinghua University","place":["Beijing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7520-9640","authenticated-orcid":false,"given":"Yunquan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology Chinese Academy of Sciences","place":["Beijing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,24]]},"reference":[{"key":"e_1_3_1_2_2","volume-title":"NVIDIA A100 Tensor Core GPU Architecture","year":"2020","unstructured":"2020. NVIDIA A100 Tensor Core GPU Architecture. White Paper V1.0. NVIDIA Corporation. Retrieved January 15, 2026 from https:\/\/images.nvidia.com\/aem-dam\/en-zz\/Solutions\/data-center\/nvidia-ampere-architecture-whitepaper.pdf"},{"key":"e_1_3_1_3_2","unstructured":"2026. Intel Math Kernel Library Developer Reference (Intel MKL). Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/docs\/oneapi\/programming-guide\/2025-1\/overview.html"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2014.6854332"},{"key":"e_1_3_1_5_2","unstructured":"Krste Asanovic Ras Bodik Bryan Catanzaro Joseph Gebis Parry Husbands Kurt Keutzer David Patterson William Plishker John Shalf and Samuel Webb Williams. 2006. The landscape of parallel computing research: A view from berkeley. (2006)."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562783"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976137.2"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/47314"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2014.6983061"},{"key":"e_1_3_1_10_2","unstructured":"Cambricon Technologies. 2023. Matrix Multiplication Functions \u2014 Cambricon BANG C Developer Guide (v4.5.1). Retrieved August 29 2025 from https:\/\/www.cambricon.com\/docs\/sdk_1.13.0\/cntoolkit_3.5.2\/cambricon_bang_c_4.5.1\/2Builtin-Functions\/Matrix%20Multiplication%20Functions.html"},{"key":"e_1_3_1_11_2","unstructured":"Cambricon Technologies. 2023. Storage Model \u2014 Cambricon BANG C\/C++ Programming Guide (v1.7.0). Retrieved August 29 2025 from https:\/\/www.cambricon.com\/docs\/sdk_1.15.0\/cntoolkit_3.7.2\/programming_guide_1.7.0\/hardware_implementation\/index.html"},{"key":"e_1_3_1_12_2","unstructured":"Cambricon Technologies. 2025. MLU Architecture Overview. Retrieved from https:\/\/www.cambricon.com\/docs\/sdk_1.13.0\/cntoolkit_3.5.2\/cntoolkit_tuning_0.4.1\/chapter1_mlu_architecture\/index.html"},{"key":"e_1_3_1_13_2","unstructured":"Cambricon Technologies. 2025. MLU370-X4 Intelligent Accelerator Card. Retrieved August 26 2025 from https:\/\/www.cambricon.com\/index.php?m=content&c=index&a=lists&catid=371"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2541940.2541967"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3577193.3593735"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638476"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2021.3061394"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TE.1969.4320436"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2018.07.034"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3330345.3331057"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC55821.2022.9926354"},{"key":"e_1_3_1_23_2","unstructured":"Xinyu Ding Bangtian Liu Siyu Liao and Zhongfeng Wang. 2025. Memory-efficient training with in-place FFT implementation. arXiv:2511.01385. Retrieved from https:\/\/arxiv.org\/abs\/2511.01385"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1049\/el:19840012"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441623"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT52795.2021.00032"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2022.3163280"},{"key":"e_1_3_1_28_2","first-page":"1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"al Li Z. et","year":"2019","unstructured":"Li Z. et al. 2019. AutoFFT: A template-based fft codes auto-generation framework for ARM and X86 CPUs. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1\u201315."},{"key":"e_1_3_1_29_2","unstructured":"FFTW Developers. [n. d.]. FFTW: Fastest fourier transform in the west. Retrieved August 15 2025 from https:\/\/www.fftw.org\/"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840301"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"e_1_3_1_32_2","unstructured":"Frigo M. and Johnson S.G.2003. benchFFT: Benchmarking Fast Fourier Transform Implementations. Retrieved August 29 2025 from http:\/\/www.fftw.org\/benchfft\/"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2355585.2355596"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3710848.3710897"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.014"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/CLUSTER59578.2024.00021"},{"key":"e_1_3_1_37_2","article-title":"Dissecting the graphcore IPU architecture via microbenchmarking","volume":"1912","author":"Jia Zhe","year":"2019","unstructured":"Zhe Jia, Blake Tillman, Marco Maggioni, and Daniele Paolo Scarpazza. 2019. Dissecting the graphcore IPU architecture via microbenchmarking. CoRR abs\/1912.03413 (2019). arXiv:1912.03413. Retrieved from https:\/\/arxiv.org\/abs\/1912.03413","journal-title":"CoRR"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/3PGCIC.2015.66"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3140659.3080246"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1977.1162973"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45209-6_39"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/Cluster48925.2021.00035"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.3390\/app14010405"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.42"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.2003.822776"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/78.782222"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(03)00040-1"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50743-5_12"},{"key":"e_1_3_1_49_2","unstructured":"NVIDIA Corporation. 2024. Fast Fourier Transform for NVIDIA GPUs. Retrieved August 29 2025 from https:\/\/developer.nvidia.com\/cufft"},{"key":"e_1_3_1_50_2","volume-title":"cuFFT Library User\u2019s Guide","author":"Corporation NVIDIA","year":"2025","unstructured":"NVIDIA Corporation. 2025. cuFFT Library User\u2019s Guide. NVIDIA. Retrieved August 15, 2025 from https:\/\/docs.nvidia.com\/cuda\/pdf\/CUFFT_Library.pdf"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2014.6844463"},{"key":"e_1_3_1_52_2","article-title":"Discrete-time signal processing","author":"Pfister Henry","year":"2017","unstructured":"Henry Pfister. 2017. Discrete-time signal processing. Lecture Note, pfister. ee. duke. edu\/courses\/ece485\/dtsp. pdf (2017).","journal-title":"Lecture Note, pfister. ee. duke. edu\/courses\/ece485\/dtsp. pdf"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS49936.2021.00059"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840306"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/83.506761"},{"key":"e_1_3_1_56_2","volume-title":"Characterizing the Performance, Power Efficiency, and Programmability of AMD Matrix Cores","author":"Schieffer Gabin","year":"2024","unstructured":"Gabin Schieffer, Daniel Medeiros, Jennifer Faj, Aniruddha Marathe, and Ivy Peng. 2024. Characterizing the Performance, Power Efficiency, and Programmability of AMD Matrix Cores. Technical Report. Lawrence Livermore National Laboratory (LLNL), Livermore, CA (United States)."},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-1684(01)00201-8"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1987.1165220"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPCW.2018.8634417"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/1464182.1464209"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1142\/4610"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-592101-5.50007-5"},{"key":"e_1_3_1_63_2","unstructured":"Cambricon Technologies. 2025. Cambricon FFT kernel implementation in MLU-OPS (commit 4940a38). Retrieved August 29 2025 from https:\/\/github.com\/Cambricon\/mlu-ops\/tree\/4940a38c4345c25d76c93b632897719bd30a739a\/kernels\/fft"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2023.3242240"},{"key":"e_1_3_1_65_2","unstructured":"Dmitrii Tolmachev. 2025. VkFFT: Metal Fast Fourier Transform Library. Retrieved August 29 2025 from https:\/\/github.com\/DTolm\/VkFFT"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/29.17500"},{"key":"e_1_3_1_67_2","article-title":"Fitting FFT onto the G80 architecture","volume":"40","author":"Volkov Vasily","year":"2008","unstructured":"Vasily Volkov and Brian Kazian. 2008. Fitting FFT onto the G80 architecture. University of California, Berkeley 40 (2008).","journal-title":"University of California, Berkeley"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-05054-2_27"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/1498765.1498785"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3710848.3710853"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICECC.2011.6066463"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2010.07.010"},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS57955.2024.00088"},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/3605148"},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.21437\/Interspeech.2020-2952"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3819240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T12:57:41Z","timestamp":1784897861000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3819240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,24]]},"references-count":74,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1145\/3819240"],"URL":"https:\/\/doi.org\/10.1145\/3819240","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,24]]},"assertion":[{"value":"2026-01-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-05-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-07-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}