EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

3D DFT by block tensor-matrix multiplication via a modified Cannon's algorithm: Implementation and scaling on distributed-memory clusters with fat tree networks

Nitin Malapally, Viacheslav Bolnykh, Estela Suarez, Paolo Carloni, Thomas Lippert, Davide Mandelli

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →