Article

Optimal bit-reversal using vector permutations

Authors:

Anton Lokhmotov,

Alan MycroftAuthors Info & Claims

SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

Pages 198 - 199

https://doi.org/10.1145/1248377.1248411

Published: 09 June 2007 Publication History

Get Access

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]

A. J. Bik. The Software Vectorization Handbook. Applying Multimedia Extensions for Maximum Performance. Intel Press, 2004.

Digital Library

Google Scholar

[2]

L. Carter and K. S. Gatlin. Towards an optimal bit-reversal permutation program. In Proc. of FOCS'98. IEEE.

Digital Library

Google Scholar

[3]

K. Diefendorff, P. K. Dubey, R. Hochsprung, and H. Scales. AltiVec extension to PowerPC accelerates media processing. IEEE Micro, 20(2):85--95, 2000.

Digital Library

Google Scholar

[4]

J. Johnson and R. Johnson. Challenges of computing the fast Fourier transform. In Proc. of the Optimized Portable Application Libraries Workshop, 1997.

Google Scholar

[5]

A. H. Karp. Bit-reversal on uniprocessors. SIAM Review, 38(1):1--26, 1996.

Digital Library

Google Scholar

[6]

A. Kudriavtsev and P. Kogge. Generation of permutations for SIMD processors. In Proc. of LCTES'05. ACM.

Digital Library

Google Scholar

[7]

C. V. Loan. Computational frameworks for the fast Fourier transform. SIAM, 1992.

Digital Library

Google Scholar

[8]

G. Ren, P. Wu, and D. Padua. Optimizing data permutations for SIMD devices. In Proc. of PLDI'06. ACM.

Digital Library

Google Scholar

[9]

Z. Zhang and X. Zhang. Fast bit-reversals on uniprocessors and shared-memory multiprocessors. SIAM Journal of Scientific Computing, 22(6):2113--2134, 2000.

Digital Library

Google Scholar

Cited By

View all

Villalonga BBoixo SNelson BHenze CRieffel EBiswas RMandrà S(2019)A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardwarenpj Quantum Information10.1038/s41534-019-0196-15:1Online publication date: 10-Oct-2019
https://doi.org/10.1038/s41534-019-0196-1
Knittel G(2011)QTIB: Quick bit-reversed permutations on CPUs2011 17th International Conference on Digital Signal Processing (DSP)10.1109/ICDSP.2011.6004879(1-6)Online publication date: Jul-2011
https://doi.org/10.1109/ICDSP.2011.6004879
Weng THuang SLiau WLi K(2010)Performance of parallel bit-reversal with cilk and UPC for fast fourier transformProceedings of the 5th international conference on Advances in Grid and Pervasive Computing10.1007/978-3-642-13067-0_26(224-233)Online publication date: 10-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13067-0_26
Show More Cited By

Index Terms

Optimal bit-reversal using vector permutations
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multiple instruction, multiple data
      2. Single instruction, multiple data
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computation of transforms

Recommendations

On the combinatorics of derangements and related permutations
Highlights
- Provide a bijection combinatorial proof for the facts that The number of derangements of length n equals the number of permutations of length n that have ...
Abstract
A derangement is a permutation in which no entry is at its original position. The number of derangements of [ n ] is called the “derangement number” or “de Montmort number”, and is denoted by D n. The sequence { D n } enumerates, in ...
Infinite permutations of lowest maximal pattern complexity

An infinite permutation @a is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we define maximal ...
Unshuffling Permutations: Trivial Bijections and Compositions
Theory and Applications of Models of Computation
Abstract
Given permutations , and , the permutation (viewed as a string) is said to be a shuffle of and , in symbols [inline-graphic not available: see fulltext], if can be formed by interleaving the letters of two strings and that are order-isomorphic to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

June 2007

376 pages

ISBN:9781595936677

DOI:10.1145/1248377

General Chair:
Phillip B. Gibbons
Intel Research, USA
,
Program Chair:
Christian Scheideler
Technische Universität München, Germany

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA07

Sponsor:

SPAA07: 19th ACM Symposium on Parallelism in Algorithms and Architectures

June 9 - 11, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
350
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Villalonga BBoixo SNelson BHenze CRieffel EBiswas RMandrà S(2019)A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardwarenpj Quantum Information10.1038/s41534-019-0196-15:1Online publication date: 10-Oct-2019
https://doi.org/10.1038/s41534-019-0196-1
Knittel G(2011)QTIB: Quick bit-reversed permutations on CPUs2011 17th International Conference on Digital Signal Processing (DSP)10.1109/ICDSP.2011.6004879(1-6)Online publication date: Jul-2011
https://doi.org/10.1109/ICDSP.2011.6004879
Weng THuang SLiau WLi K(2010)Performance of parallel bit-reversal with cilk and UPC for fast fourier transformProceedings of the 5th international conference on Advances in Grid and Pervasive Computing10.1007/978-3-642-13067-0_26(224-233)Online publication date: 10-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13067-0_26
Yu FWang ZGe R(2009)Novel algorithm for complex bit reversal: employing vector permutation and branch reduction methodsJournal of Zhejiang University-SCIENCE A10.1631/jzus.A092029010:10(1492-1499)Online publication date: 1-Oct-2009
https://doi.org/10.1631/jzus.A0920290
Weng THuang SPerng RHsu CLi K(2009)A Practical OpenMP Implementation of Bit-Reversal for Fast Fourier TransformScalable Information Systems10.1007/978-3-642-10485-5_15(206-216)Online publication date: 2009
https://doi.org/10.1007/978-3-642-10485-5_15

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On the combinatorics of derangements and related permutations

Infinite permutations of lowest maximal pattern complexity

Unshuffling Permutations: Trivial Bijections and Compositions