Bit-reversal permutation: Difference between revisions

Revision as of 23:08, 28 June 2020

Revision as of 08:49, 29 June 2020

Line 79:

| year = 1990}}.</ref>

Another consideration that is even more important for the performance of these algorithms is the effect of the [[memory hierarchy]] on running time. Because of this effect, more sophisticated algorithms that consider the block structure of memory can be faster than this naive scan.<ref name="karp"/><ref name="cg98">{{citation|last1=Carter|first1=Larry|first2=Kang Su|last2=Gatlin|contribution=Towards an optimal bit-reversal permutation program|title=Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS)|pages=544–553|year=1998|doi=10.1109/SFCS.1998.743505|title-link=Symposium on Foundations of Computer Science|isbn=978-0-8186-9172-0|citeseerx=10.1.1.46.9319}}.</ref> Several cache optimal bit-reversal methods are developed and implemented on uniprocessor and shared memory multiprocessors to achieve high performance<ref>Zhao Zhang and Xiaodong Zhang, "[http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-01-2.pdf Fast bit-reversals on uniprocessors and shared-memory multiprocessors]", SIAM Journal on Scientific Computing, Vol. 22, No. 6, 2001, pp. 2113-2134. </ref>. An alternative to these techniques is special computer hardware that allows memory to be accessed both in normal and in bit-reversed order.<ref>{{citation

| last1 = Harley | first1 = T. R.

| last2 = Maheshwaramurthy | first2 = G. P.