{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:55Z","timestamp":1787337235513,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2001,1]]},"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 used on many uniprocessor workstations and multiprocessors.<\/jats:p>","DOI":"10.1137\/s1064827599359709","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"2113-2134","source":"Crossref","is-referenced-by-count":7,"title":["Fast Bit-Reversals on Uniprocessors and Shared-Memory Multiprocessors"],"prefix":"10.1137","volume":"22","author":[{"given":"Zhao","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaodong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,25]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/197405.197406"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00162341"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"B. Bershad, D. Lee, T. Romer, and B. Chen,\n Avoiding conflict misses dynamically in large direct\u2010mapped caches\n , in Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems, 1994, pp. 158\u2013170.","DOI":"10.1145\/195473.195527"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/40.621215"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90039-C"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1987.1165252"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"K. S. Gatlin and L. Carter,\n Memory hierarchy considerations for fast transpose and bit\u2010reversals\n , in Proceedings of Fifth International Symposium on High\u2010Performance Computer Architecture, 1999, pp. 33\u201344.","DOI":"10.1109\/HPCA.1999.744320"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0609037"},{"key":"R10","unstructured":"IEEE,\n POSIX P1003.4a: Threads Extension for Portable Operating Systems\n , IEEE Press, Piscataway, NJ, 1994."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/1038001"},{"key":"R12","unstructured":"J. L. Hennessy and D. A. Patterson,\n Computer Architecture: A Quantitative Approach\n , Morgan\u2010Kaufmann, San Francisco, 1996."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"N. P. Jouppi,\n Improving direct\u2010mapped cache performance by the addition of a small fully\u2010associative cache and prefetch buffers\n , in Proceedings of 17th Annual International Symposium on Computer Architecture, 1990, pp. 364\u2013373.","DOI":"10.1109\/ISCA.1990.134547"},{"key":"R14","unstructured":"L. McVoy and C. Staelin,\n lmbench: Portable tools for performance analysis\n , in Proceedings of the 1996 USENIX Technical Conference, 1996, pp. 279\u2013295."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(84)90413-7"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"C. Rivera and C.\u2010W. Tseng,\n Data transformations for eliminating conflict misses\n , in Proceedings of the ACM SIGPLAN\u201898 Conference on Programming Language Design and Implementation, 1998, pp. 38\u201349.","DOI":"10.1145\/277650.277661"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/244804.244807"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"L. Xiao, X. Zhang, and S. A. Kubricht,\n Improving memory performance of sorting algorithms\n , 5 (2000), pp. 1\u201323.","DOI":"10.1145\/351827.384245"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/71.850833"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1109\/40.621212"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S1064827599359709","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:51:34Z","timestamp":1787334694000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S1064827599359709"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S1064827599359709"],"URL":"https:\/\/doi.org\/10.1137\/s1064827599359709","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}