Fast Bit-Reversals on Uniprocessors and Shared-Memory Multiprocessors
Authors:
- Zhao ZhangZZZhao Zhang
- Xiaodong ZhangXZXiaodong Zhang
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 22 (6) , 2113-2134
Abstract
In this paper, we examine different methods using techniques of blocking, buffering, and padding for efficient implementations of bit-reversals. We evaluate the merits and limits of each technique and its application and architecture-dependent conditions for developing cache-optimal methods. Besides testing the methods on different uniprocessors, we conducted both simulation and measurements on two commercial symmetric multiprocessors (SMP) to provide architectural insights into the methods and their implementations. We present two contributions in this paper: (1) Our integrated blocking methods, which match cache associativity and translation-lookaside buffer (TLB) cache size and which fully use the available registers, are cache-optimal and fast. (2) We show that our padding methods outperform other software-oriented methods, and we believe they are the fastest in terms of minimizing both CPU and memory access cycles. Since the padding methods are almost independent of hardware, they could be widely use...Keywords
This publication has 17 references indexed in Scilit:
- Using the SimOS machine simulator to study complex computer systemsACM Transactions on Modeling and Computer Simulation, 1997
- Virtual-address caches. Part 1: problems and solutions in uniprocessorsIEEE Micro, 1997
- Bit Reversal on UniprocessorsSIAM Review, 1996
- Compiler transformations for high-performance computingACM Computing Surveys, 1994
- Optimal matrix transposition and bit reversal on hypercubes: All-to-all personalized communicationJournal of Parallel and Distributed Computing, 1991
- FFTs in external or hierarchical memoryThe Journal of Supercomputing, 1990
- Algorithms for Matrix Transposition on Boolean N-Cube Configured Ensemble ArchitecturesSIAM Journal on Matrix Analysis and Applications, 1988
- An improved digit-reversal permutation algorithm for the fast Fourier and Hartley transformsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1987
- FFT algorithms for vector computersParallel Computing, 1984
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965