Optimal bit-reversal using vector permutations

ABSTRACT

We have developed a bit-reversal algorithm (BRAVO) using vector permute operations, which is optimal in the number of permutations, and its cache-optimal version (COBRAVO). Our implementation on PowerMac G5 shows 2-4.5 fold improvement for small data sets and 15-75% improvement for large data sets (depending on the data element size) over the best known approach (COBRA).

REFERENCES

• 1: Aart J. C. Bik, Software Vectorization Handbook, The: Applying Intel Multimedia Extensions for Maximum Performance, Intel Press, 2004
• 2: Larry Carter , Kang Su Gatlin, Towards an Optimal Bit-Reversal Permutation Program, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.544, November 08-11, 1998
• 3: Keith Diefendorff , Pradeep K. Dubey , Ron Hochsprung , Hunter Scales, AltiVec Extension to PowerPC Accelerates Media Processing, IEEE Micro, v.20 n.2, p.85-95, March 2000 [doi>10.1109/40.848475]
• 4: J. Johnson and R. Johnson. Challenges of computing the fast Fourier transform. In Proc. of the Optimized Portable Application Libraries Workshop, 1997.
• 5: Alan H. Karp, Bit reversal on uniprocessors, SIAM Review, v.38 n.1, p.1-26, Mar. 1996 [doi>10.1137/1038001]
• 6: Alexei Kudriavtsev , Peter Kogge, Generation of permutations for SIMD processors, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 7: Charles Van Loan, Computational frameworks for the fast Fourier transform, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 8: Gang Ren , Peng Wu , David Padua, Optimizing data permutations for SIMD devices, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 9: Zhao Zhang , Xiaodong Zhang, Fast Bit-Reversals on Uniprocessors and Shared-Memory Multiprocessors, SIAM Journal on Scientific Computing, v.22 n.6, p.2113-2134, 2000 [doi>10.1137/S1064827599359709]

INDEX TERMS

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

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

General Terms:
Algorithms, Performance

Keywords:
FFT, SIMD, bit-reversal, permutation, vector