An efficient in-place 3D transpose for multicore processors with software managed memory hierarchy

ABSTRACT

3D transpose is an important operation in many large scale scientific applications such as seismic and medical imaging. This paper proposes a novel algorithm for fast in-place 3D transpose operation. The algorithm exploits Single Instruction Multiple Data (SIMD) multicore architecture with software managed memory hierarchy. Such architectural features are present in the next generation processors, such as the Cell Broadband Engine (Cell BE) processor. The algorithm performs transposition at two levels of granularity: at coarse level, where logical transposition is done by merely transposing the address map at each access; and at a fine grain level, where physical transposition is done by actual element displacement/swapping. Such mix combines the benefits of allowing for fast on-chip bandwidth by providing for large transfer sizes, and at the same time allows for fine-grain SIMD operations. The transfer rate is further enhanced by allowing for batch transposing spatially joined data along a major axis. Results on the Cell BE processor show substantial utilisation of on-chip communication bandwidth, and negligible processing time.

REFERENCES

• 1: Jr. C. W. Carter, and Eds R. M. Sweet. Processing of X-ray Diffraction Data Collected in Oscillation Mode, Methods in Enzymology. Macromolecular Crystallography, Volume 276: part A, p.307--326, 1997.
• 2: J. Choi, J. J. Dongarra, and D. W. Walker. Parallel matrix transpose algorithms on distributed memory concurrent computers. In Proceedings of Scalable Parallel Libraries Conference, 1993.
• 3: H. S. Cohl, X.-H. Sun, and J. E. Tohline. Parallel implementation of a data-transpose technique for the solution of Poisson's equation in cylindrical coordinates". In Proceedings of the Eighth SIAM conference on Parallel Processing for Scientific Computing. PPSC, Math 14--17 1997.
• 4: M. Elefheriou, B. G. Fitch, R. S. Germain, A. Rayshubskiy, and T. J. C. Ward. Multi-dimensional transpose for distributed memory network. US Patent 2006/0010181, January 2006.
• 5: IBM. Cell Broadband Engine Architecture, October 2006. version 1.01.
• 6: M. Kistler, M. Perrone, and F. Petrini. Cell Multiprocessor Communication Network: Built for Speed IEEE MICRO., May-June 2006.
• 7: P. Wapperom , A. N. Beris , M. A. Straka, A new transpose split method for three-dimensional FFTs: performance on an origin2000 and alphaserver cluster, Parallel Computing, v.32 n.1, p.1-13, January 2006 [doi>10.1016/j.parco.2005.06.004]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming; Parallel programming

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays; Distributed data structures

General Terms:
Algorithms, Design

Keywords:
3D transpose, SIMD, multi-core systems, parallel programming, vector programming