BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Lirkov Ivan (Bulgarian Academy of Sciences), Paprzycki Marcin (Polish Academy of Sciences), Ganzha Maria (Polish Academy of Sciences), Sedukhin Stanislav (The University of Aizu, Japan), Gepner Paweł (Intel Corporation)
Performance analysis of scalable algorithms for 3D linear transforms
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 613 - 622, rys., tab., bibliogr. 7 poz.
Algorytmy, Programowanie liniowe, Programy komputerowe
Algorithms, Linear programming, Computer programs
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)
Full text
  1. 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
  2. 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
  3. 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
  4. 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.
  5. 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.
  6. 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
  7. Walker, D., Dongarra, J.: MPI: a standard Message Passing Interface. Supercomputer, 12 (1), 56-68 (1996), ISSN 0168-7875
Cited by
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu