Performance analysis of scalable algorithms for 3D linear transforms

• Autorzy: Ivan Lirkov , Marcin Paprzycki , Maria Ganzha , Stanislav Sedukhin , Paweł Gepner
• Języki publikacji: EN

Abstrakty

EN

The 3D forward/inverse separable discrete transforms, such as Fourier transform, cosine/sine transform, etc. are frequently the principal limiters that prevent many practical applications from scaling to the large number of processors. Existing approaches, which are based on 1D or 2D data decomposition, do not allow the 3D transforms to be scaled to the maximum possible number of computer nodes. Based on the proposed 3D decomposition of the data, highly scalable parallel algorithms of any forward/inverse 3D transform on the torus network of computer nodes was recently designed. The designed algorithms require compute-and-roll time-steps, where each step consists an execution of multiple GEMM operations and concurrent movement of cubical data between nearest-neighbor nodes. The proposed 3D orbital algorithms gracefully avoid a required 3D data transposition and can be extremely scaled up to the number of nodes which is equal to the size of the initial data.(original abstract)

Słowa kluczowe

EN

Algorithms; Linear programming; Computer programs

PL

Algorytmy; Programowanie liniowe; Programy komputerowe

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 613--622

Twórcy

autor

Ivan Lirkov

• Bulgarian Academy of Sciences

autor

Marcin Paprzycki

• Polish Academy of Sciences

autor

Maria Ganzha

• Polish Academy of Sciences

autor

Stanislav Sedukhin

• The University of Aizu, Japan

autor

Paweł Gepner

• Intel Corporation

Bibliografia

• Ayala O. and Wang L. P. Parallel implementation and scalability analysis of 3D fast Fourier transform using 2D domain decomposition. Parallel Computing, 2012. DOI: 10.1016/j.parco.2012.12.002
• Dongarra J. J., Du Croz J., Hammarling S., and Duff I. S. A set of level 3 basic linear algebra subprograms. ACM Transactions on Mathematical Software (TOMS), 16(1):1-17, 1990. DOI: 10.1145/77626.79170
• Eleftheriou M., Moreira J. E., Fitch B. G., and Germain R. S. A volumetric FFT for Blue Gene/L. In Timothy Mark Pinkston and Viktor K. Prasanna, editors, High Performance Computing - HiPC 2003, volume 2913 of Lecture Notes in Computer Science, pages 194- 203. Springer Berlin Heidelberg, 2003. DOI: 10.1007/978-3-540-24596-4 21
• Li N. and Laizet S. 2DECOMP&FFT - A Highly Scalable 2D Decomposition: Library and FFT Interface. In Cray User Group 2010 conference, pages 1-13, 2010.
• Sedukhin S. G., Co-design of Extremely Scalable Algorithms/Architecture for 3-Dimensional Linear Transforms, Technical Report TR2012-001, The University of Aizu, July 2012.
• Snir, M., Otto, S., Huss-Lederman, S., Walker, D., Dongarra, J.: MPI: The Complete Reference, second edition, Volume 1, The MPI Core. Scientific and engineering computation series, The MIT Press, Cambridge, Massachusetts (1998), ISBN: 9780262692151
• Walker, D., Dongarra, J.: MPI: a standard Message Passing Interface. Supercomputer, 12 (1), 56-68 (1996), ISSN 0168-7875