3D DFT by block tensor-matrix multiplication via a modified Cannon's algorithm: Implementation and scaling on distributed-memory clusters with fat tree networks
Journal of Parallel and Distributed Computing · 2024-11 · 193 · 104945
DOI: 10.1016/j.jpdc.2024.104945 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Parallel and Distributed Computing, 2024-11. Verfasst von Nitin Malapally und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).
Abstract (Originalsprache)
The 3D Discrete Fourier Transform (DFT) is a technique used to solve problems in disparate fields. Nowadays, the commonly adopted implementation of the 3D-DFT is derived from the Fast Fourier Transform (FFT) algorithm. However, evidence indicates that the distributed memory 3D-FFT algorithm does not scale well due to its use of all-to-all communication. Here, building on the work of Sedukhin \textit{et al}. [Proceedings of the 30th International Conference on Computers and Their Applications, CATA 2015 pp. 193-200 (01 2015)], we revisit the possibility of improving the scaling of the 3D-DFT by using an alternative approach that uses point-to-point communication, albeit at a higher arithmetic complexity. The new algorithm exploits tensor-matrix multiplications on a volumetrically decomposed domain via three specially adapted variants of Cannon's algorithm. It has here been implemented as a C++ library called S3DFT and tested on the JUWELS Cluster at the J\"ulich Supercomputing Center. Our implementation of the shared memory tensor-matrix multiplication attained 88\% of the theoretical single node peak performance. One variant of the distributed memory tensor-matrix multiplication shows excellent scaling, while the other two show poorer performance, which can be attributed to their intrinsic communication patterns. A comparison of S3DFT with the Intel MKL and FFTW3 libraries indicates that currently iMKL performs best overall, followed in order by FFTW3 and S3DFT. This picture might change with further improvements of the algorithm and/or when running on clusters that use network connections with higher latency, e.g. on cloud platforms.
Zitieren
APA
Malapally, N., Bolnykh, V., Suarez, E., Carloni, P., Lippert, T., & Mandelli, D. (2024). 3D DFT by block tensor-matrix multiplication via a modified Cannon's algorithm: Implementation and scaling on distributed-memory clusters with fat tree networks. Journal of Parallel and Distributed Computing, 193, 104945. https://doi.org/10.1016/j.jpdc.2024.104945
Vancouver
Malapally N, Bolnykh V, Suarez E, Carloni P, Lippert T, Mandelli D. 3D DFT by block tensor-matrix multiplication via a modified Cannon's algorithm: Implementation and scaling on distributed-memory clusters with fat tree networks. Journal of Parallel and Distributed Computing. 2024;193:104945. doi:10.1016/j.jpdc.2024.104945
BibTeX
@article{Malapally2024,
author = {Malapally, Nitin and Bolnykh, Viacheslav and Suarez, Estela and Carloni, Paolo and Lippert, Thomas and Mandelli, Davide},
title = {3D DFT by block tensor-matrix multiplication via a modified Cannon's algorithm: Implementation and scaling on distributed-memory clusters with fat tree networks},
journal = {Journal of Parallel and Distributed Computing},
year = {2024},
volume = {193},
pages = {104945},
doi = {10.1016/j.jpdc.2024.104945}
}
EUVIMED