Multiple Memory Structure Bit Reversal Algorithm Based on Recursive Patterns of Bit Reversal Permutation
Joint Authors
Becker, T.
Adikaram, K. K. L. B.
Effenberger, M.
Hussein, M. A.
Source
Mathematical Problems in Engineering
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-12, 12 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-07-17
Country of Publication
Egypt
No. of Pages
12
Main Subjects
Abstract EN
With the increasing demand for online/inline data processing efficient Fourier analysis becomes more and more relevant.
Due to the fact that the bit reversal process requires considerable processing time of the Fast Fourier Transform (FFT) algorithm, it is vital to optimize the bit reversal algorithm (BRA).
This paper is to introduce an efficient BRA with multiple memory structures.
In 2009, Elster showed the relation between the first and the second halves of the bit reversal permutation (BRP) and stated that it may cause serious impact on cache performance of the computer, if implemented.
We found exceptions, especially when the said index mapping was implemented with multiple one-dimensional memory structures instead of multidimensional or one-dimensional memory structure.
Also we found a new index mapping, even after the recursive splitting of BRP into equal sized slots.
The four-array and the four-vector versions of BRA with new index mapping reported 34% and 16% improvement in performance in relation to similar versions of Linear BRA of Elster which uses single one-dimensional memory structure.
American Psychological Association (APA)
Adikaram, K. K. L. B.& Hussein, M. A.& Effenberger, M.& Becker, T.. 2014. Multiple Memory Structure Bit Reversal Algorithm Based on Recursive Patterns of Bit Reversal Permutation. Mathematical Problems in Engineering،Vol. 2014, no. 2014, pp.1-12.
https://search.emarefa.net/detail/BIM-501343
Modern Language Association (MLA)
Adikaram, K. K. L. B.…[et al.]. Multiple Memory Structure Bit Reversal Algorithm Based on Recursive Patterns of Bit Reversal Permutation. Mathematical Problems in Engineering No. 2014 (2014), pp.1-12.
https://search.emarefa.net/detail/BIM-501343
American Medical Association (AMA)
Adikaram, K. K. L. B.& Hussein, M. A.& Effenberger, M.& Becker, T.. Multiple Memory Structure Bit Reversal Algorithm Based on Recursive Patterns of Bit Reversal Permutation. Mathematical Problems in Engineering. 2014. Vol. 2014, no. 2014, pp.1-12.
https://search.emarefa.net/detail/BIM-501343
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-501343