Efficient Bit Reversal Algorithms in Parallel Computers
Rami A. Al Na'mneh, Khalid Ahmad Darabkh, Iyad F. Jafar · Int. J. Comput. Their Appl. · 2012
Fast Fourier Transform is widely used in many areas of engineering and mathematics such as digital signal and image processing systems, and polynomial multiplication. Furthermore, it has an important role in performing parallel simulations such as plasma simulation, weather forecasting, and dynamic fluids. Bit-reversal routine is considered to be an essential part of FFT and that is because of high possibility of degrading the overall execution time of FFT application if it is not perfectly designed. In this paper, we propose a new formulation for Numerical Recipes bit-reversal sequential algorithm. The formulation is based on independent steps; hence it can be efficiently implemented on parallel computers. Two algorithms that utilized the new formulation are proposed, namely, the All-to-all and Swapping algorithms. Experimental results of the proposed algorithms show that a reasonable speedup can be achieved, especially for large data sizes, when compared to the sequential implementation of the bit-reversal. Additionally, the results show that the Swapping algorithm performs better than the All-to-all algorithm.