{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T14:26:32Z","timestamp":1775744792529,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>\n            In-place radix sort is a popular distribution-based sorting algorithm for short numeric or string keys due to its linear run-time and constant memory complexity. However, efficient parallelization of in-place radix sort is very challenging for two reasons. First, the initial phase of permuting elements into buckets suffers read-write dependency inherent in its\n            <jats:italic>in-place<\/jats:italic>\n            nature. Secondly, load balancing of the recursive application of the algorithm to the resulting buckets is difficult when the buckets are of very different sizes, which happens for skewed distributions of the input data. In this paper, we present a novel parallel in-place radix sort algorithm, PARADIS, which addresses both problems: a) \"speculative permutation\" solves the first problem by assigning multiple non-continuous array stripes to each processor. The resulting shared-nothing scheme achieves full parallelization. Since our speculative permutation is not complete, it is followed by a \"repair\" phase, which can again be done in parallel without any data sharing among the processors. b) \"distribution-adaptive load balancing\" solves the second problem. We dynamically allocate processors in the context of radix sort, so as to minimize the overall completion time. Our experimental results show that PARADIS offers excellent performance\/scalability on a wide range of input data sets.\n          <\/jats:p>","DOI":"10.14778\/2824032.2824050","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"1518-1529","source":"Crossref","is-referenced-by-count":42,"title":["PARADIS"],"prefix":"10.14778","volume":"8","author":[{"given":"Minsik","family":"Cho","sequence":"first","affiliation":[{"name":"IBM T. J. Watson Research Center, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Brand","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajesh","family":"Bordawekar","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich","family":"Finkler","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Kulandaisamy","sequence":"additional","affiliation":[{"name":"IBM Software Group, Hillsboro, OR"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruchir","family":"Puri","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1145\/233269.233336","volume-title":"Proc. SIGMOD","author":"Agarwal R. C.","year":"1996","unstructured":"R. C. Agarwal . A Super Scalar Sort Algorithm for RISC Processors . In Proc. SIGMOD , pages 240 -- 246 , 1996 . 10.1145\/233269.233336 R. C. Agarwal. A Super Scalar Sort Algorithm for RISC Processors. In Proc. SIGMOD, pages 240--246, 1996. 10.1145\/233269.233336"},{"key":"e_1_2_1_2_1","first-page":"85","volume-title":"Hash Revisited. In Proc. VLDB","author":"Balkesen C.","year":"2014","unstructured":"C. Balkesen , G. Alonso , J. Teubner , and M. T. Ozsu . Multi-Core, Main-Memory Joins: Sort vs . Hash Revisited. In Proc. VLDB , pages 85 -- 96 , 2014 . 10.14778\/2732219.2732227 C. Balkesen, G. Alonso, J. Teubner, and M. T. Ozsu. Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited. In Proc. VLDB, pages 85--96, 2014. 10.14778\/2732219.2732227"},{"key":"e_1_2_1_3_1","first-page":"1313","volume-title":"Proc. VLDB","author":"Chhugani J.","year":"2008","unstructured":"J. Chhugani , A. D. Nguyen , V. W. Lee , W. Macy , M. Hagog , Y.-K. Chen , A. Baransi , S. Kumar , and P. Dubey . Efficient Implementation of Sorting on Multi-core SIMD CPU Architecture . In Proc. VLDB , pages 1313 -- 1324 , 2008 . 10.14778\/1454159.1454171 J. Chhugani, A. D. Nguyen, V. W. Lee, W. Macy, M. Hagog, Y.-K. Chen, A. Baransi, S. Kumar, and P. Dubey. Efficient Implementation of Sorting on Multi-core SIMD CPU Architecture. In Proc. VLDB, pages 1313--1324, 2008. 10.14778\/1454159.1454171"},{"key":"e_1_2_1_4_1","first-page":"695","volume":"4641","author":"Dachsel H.","year":"2007","unstructured":"H. Dachsel , M. Hofmann , and G. Runger . Library Support for Parallel Sorting in Scientific Computations. Euro-Par Parallel Processing , 4641 : 695 -- 704 , 2007 . H. Dachsel, M. Hofmann, and G. Runger. Library Support for Parallel Sorting in Scientific Computations. Euro-Par Parallel Processing, 4641: 695--704, 2007.","journal-title":"Library Support for Parallel Sorting in Scientific Computations. Euro-Par Parallel Processing"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.532111"},{"key":"e_1_2_1_6_1","first-page":"1286","volume-title":"Proc. VLDB","author":"Gedik B.","year":"2007","unstructured":"B. Gedik , R. R. Bordawekar , and P. S. Yu . CellSort: High Performance Sorting on the Cell Processor . In Proc. VLDB , pages 1286 -- 1297 , 2007 . B. Gedik, R. R. Bordawekar, and P. S. Yu. CellSort: High Performance Sorting on the Cell Processor. In Proc. VLDB, pages 1286--1297, 2007."},{"key":"e_1_2_1_7_1","first-page":"325","volume-title":"Proc. SIGMOD","author":"Govindaraju N.","year":"2006","unstructured":"N. Govindaraju , J. Gray , R. Kumar , and D. Manocha . GPUTeraSort: high performance graphics co-processor sorting for large database management . In Proc. SIGMOD , pages 325 -- 336 , 2006 . 10.1145\/1142473.1142511 N. Govindaraju, J. Gray, R. Kumar, and D. Manocha. GPUTeraSort: high performance graphics co-processor sorting for large database management. In Proc. SIGMOD, pages 325--336, 2006. 10.1145\/1142473.1142511"},{"key":"e_1_2_1_8_1","first-page":"243","volume-title":"Proc. SIGMOD","author":"Gray J.","year":"1994","unstructured":"J. Gray , P. Sundaresan , S. Englert , K. Baclawski , and P. J. Weinberger . Quickly generating billion-record synthetic databases . In Proc. SIGMOD , pages 243 -- 252 , 1994 . 10.1145\/191839.191886 J. Gray, P. Sundaresan, S. Englert, K. Baclawski, and P. J. Weinberger. Quickly generating billion-record synthetic databases. In Proc. SIGMOD, pages 243--252, 1994. 10.1145\/191839.191886"},{"key":"e_1_2_1_9_1","first-page":"189","volume-title":"Proc. Int. Symp. on Computer Architecture","author":"Guo Q.","year":"2013","unstructured":"Q. Guo , X. Guo , R. Patel , E. Ipek , and E. G. Friedman . AC-DIMM: associative computing with STT-MRAM . In Proc. Int. Symp. on Computer Architecture , pages 189 -- 200 , 2013 . 10.1145\/2485922.2485939 Q. Guo, X. Guo, R. Patel, E. Ipek, and E. G. Friedman. AC-DIMM: associative computing with STT-MRAM. In Proc. Int. Symp. on Computer Architecture, pages 189--200, 2013. 10.1145\/2485922.2485939"},{"key":"e_1_2_1_10_1","first-page":"989","volume-title":"Proc. IEEE Conf. on Embedded Software and Systems","author":"Harkins J.","year":"2012","unstructured":"J. Harkins , T. El-Ghazawi , E. El-Araby , and M. Huang . A Novel Parallel Approach of Radix Sort with Bucket Partition Preprocess . In Proc. IEEE Conf. on Embedded Software and Systems , pages 989 -- 994 , 2012 . 10.1109\/HPCC.2012.144 J. Harkins, T. El-Ghazawi, E. El-Araby, and M. Huang. A Novel Parallel Approach of Radix Sort with Bucket Partition Preprocess. In Proc. IEEE Conf. on Embedded Software and Systems, pages 989--994, 2012. 10.1109\/HPCC.2012.144"},{"key":"e_1_2_1_11_1","unstructured":"http:\/\/algo2.iti.kit.edu\/singler\/mcstl\/.  http:\/\/algo2.iti.kit.edu\/singler\/mcstl\/."},{"key":"e_1_2_1_12_1","unstructured":"http:\/\/en.wikipedia.org\/wiki\/Big_data\/.  http:\/\/en.wikipedia.org\/wiki\/Big_data\/."},{"key":"e_1_2_1_13_1","unstructured":"http:\/\/sortbenchmark.org\/.  http:\/\/sortbenchmark.org\/."},{"key":"e_1_2_1_14_1","unstructured":"https:\/\/www.threadingbuildingblocks.org\/.  https:\/\/www.threadingbuildingblocks.org\/."},{"key":"e_1_2_1_15_1","unstructured":"http:\/\/tech.unige.ch\/omptl\/.  http:\/\/tech.unige.ch\/omptl\/."},{"key":"e_1_2_1_16_1","unstructured":"http:\/\/www.rrsd.com\/.  http:\/\/www.rrsd.com\/."},{"key":"e_1_2_1_17_1","first-page":"189","volume-title":"Proc. Int. Conf. on Parallel Architectures and Compilation Techniques","author":"Inoue H.","year":"2007","unstructured":"H. Inoue , T. Moriyama , H. Komatsu , and T. Nakatani . AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors . In Proc. Int. Conf. on Parallel Architectures and Compilation Techniques , pages 189 -- 198 , 2007 . 10.1109\/PACT.2007.12 H. Inoue, T. Moriyama, H. Komatsu, and T. Nakatani. AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors. In Proc. Int. Conf. on Parallel Architectures and Compilation Techniques, pages 189--198, 2007. 10.1109\/PACT.2007.12"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/377792.377816","volume-title":"Proc. Int. Conf. on Supercomputing","author":"Jim\u00e9nez-Gonz\u00e1lez D.","year":"2001","unstructured":"D. Jim\u00e9nez-Gonz\u00e1lez , J. J. Navarro , and J.-L. Larrba-Pey . Fast parallel in-memory 64-bit sorting . In Proc. Int. Conf. on Supercomputing , pages 114 -- 122 , 2001 . 10.1145\/377792.377816 D. Jim\u00e9nez-Gonz\u00e1lez, J. J. Navarro, and J.-L. Larrba-Pey. Fast parallel in-memory 64-bit sorting. In Proc. Int. Conf. on Supercomputing, pages 114--122, 2001. 10.1145\/377792.377816"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1145\/2213836.2213965","volume-title":"Proc. SIGMOD","author":"Kim C.","year":"2012","unstructured":"C. Kim , J. Park , N. Satish , H. Lee , P. Dubey , and J. Chhugani . CloudRAMSort: fast and efficient large-scale distributed RAM sort on shared-nothing cluster . In Proc. SIGMOD , pages 841 -- 850 , 2012 . 10.1145\/2213836.2213965 C. Kim, J. Park, N. Satish, H. Lee, P. Dubey, and J. Chhugani. CloudRAMSort: fast and efficient large-scale distributed RAM sort on shared-nothing cluster. In Proc. SIGMOD, pages 841--850, 2012. 10.1145\/2213836.2213965"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2001.1808"},{"key":"e_1_2_1_21_1","first-page":"5","volume":"6","author":"McIlroy P. M.","year":"1993","unstructured":"P. M. McIlroy , K. Bostic , and M. D. McIlroy . Engineering Radix Sort. Computing Systems , 6 : 5 -- 27 , 1993 . P. M. McIlroy, K. Bostic, and M. D. McIlroy. Engineering Radix Sort. Computing Systems, 6: 5--27, 1993.","journal-title":"Engineering Radix Sort. Computing Systems"},{"issue":"02","key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1142\/S0129626411000187","article-title":"High Performance and Scalable Radix Sorting: A case study of implementing dynamic parallelism for GPU computing","volume":"21","author":"Merrill D.","year":"2011","unstructured":"D. Merrill and A. Grimshaw . High Performance and Scalable Radix Sorting: A case study of implementing dynamic parallelism for GPU computing . Parallel Processing Letters , 21 ( 02 ): 245 -- 272 , 2011 . D. Merrill and A. Grimshaw. High Performance and Scalable Radix Sorting: A case study of implementing dynamic parallelism for GPU computing. Parallel Processing Letters, 21(02):245--272, 2011.","journal-title":"Parallel Processing Letters"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1713254.1713276"},{"key":"e_1_2_1_24_1","first-page":"203","volume-title":"Proc. ACM Int. Conf. on Object Oriented Programming Systems Languages and Applications","author":"Pasetto D.","year":"2011","unstructured":"D. Pasetto and A. Akhriev . A comparative study of parallel sort algorithms . In Proc. ACM Int. Conf. on Object Oriented Programming Systems Languages and Applications , pages 203 -- 204 , 2011 . 10.1145\/2048147.2048207 D. Pasetto and A. Akhriev. A comparative study of parallel sort algorithms. In Proc. ACM Int. Conf. on Object Oriented Programming Systems Languages and Applications, pages 203--204, 2011. 10.1145\/2048147.2048207"},{"key":"e_1_2_1_25_1","first-page":"755","volume-title":"Proc. SIGMOD","author":"Polychroniou O.","year":"2014","unstructured":"O. Polychroniou and K. A. Ross . A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort . In Proc. SIGMOD , pages 755 -- 766 , 2014 . 10.1145\/2588555.2610522 O. Polychroniou and K. A. Ross. A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort. In Proc. SIGMOD, pages 755--766, 2014. 10.1145\/2588555.2610522"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2011.18"},{"key":"e_1_2_1_27_1","first-page":"1","volume-title":"Proc. IEEE Int. Symp. on Parallel&Distributed Processing","author":"Satish N.","year":"2009","unstructured":"N. Satish , M. Harris , and M. Garland . Designing efficient sorting algorithms for manycore gpus . In Proc. IEEE Int. Symp. on Parallel&Distributed Processing , pages 1 -- 10 , 2009 . 10.1109\/IPDPS.2009.5161005 N. Satish, M. Harris, and M. Garland. Designing efficient sorting algorithms for manycore gpus. In Proc. IEEE Int. Symp. on Parallel&Distributed Processing, pages 1--10, 2009. 10.1109\/IPDPS.2009.5161005"},{"key":"e_1_2_1_28_1","first-page":"351","volume-title":"Proc. SIGMOD","author":"Satish N.","year":"2010","unstructured":"N. Satish , C. Kim , J. Chhugani , A. D. Nguyen , V. W. Lee , D. Kim , and P. Dubey . Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort . In Proc. SIGMOD , pages 351 -- 362 , 2010 . 10.1145\/1807167.1807207 N. Satish, C. Kim, J. Chhugani, A. D. Nguyen, V. W. Lee, D. Kim, and P. Dubey. Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort. In Proc. SIGMOD, pages 351--362, 2010. 10.1145\/1807167.1807207"},{"key":"e_1_2_1_29_1","volume-title":"GPUs and Intel MIC Architectures. Technical report","author":"Satish N.","year":"2010","unstructured":"N. Satish , C. Kim , J. Chhugani , A. D. Nguyen , V. W. Lee , D. Kim , and P. Dubey . Fast Sort on CPUs , GPUs and Intel MIC Architectures. Technical report , Intel Labs , 2010 . N. Satish, C. Kim, J. Chhugani, A. D. Nguyen, V. W. Lee, D. Kim, and P. Dubey. Fast Sort on CPUs, GPUs and Intel MIC Architectures. Technical report, Intel Labs, 2010."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1370082.1370089","volume-title":"Proc. of Int. Workshop on Multicore Software Engineering","author":"Singler J.","year":"2008","unstructured":"J. Singler and B. Konsik . The GNU Libstdc++ Parallel Mode: Software Engineering Considerations . In Proc. of Int. Workshop on Multicore Software Engineering , pages 15 -- 22 , 2008 . 10.1145\/1370082.1370089 J. Singler and B. Konsik. The GNU Libstdc++ Parallel Mode: Software Engineering Considerations. In Proc. of Int. Workshop on Multicore Software Engineering, pages 15--22, 2008. 10.1145\/1370082.1370089"},{"key":"e_1_2_1_31_1","first-page":"682","volume-title":"Proc. Int. Euro-Par Conf. on Parallel Processing","author":"Singler J.","year":"2007","unstructured":"J. Singler , P. Sanders , and F. Putze . MCSTL: The Multi-core Standard Template Library . In Proc. Int. Euro-Par Conf. on Parallel Processing , pages 682 -- 694 , 2007 . J. Singler, P. Sanders, and F. Putze. MCSTL: The Multi-core Standard Template Library. In Proc. Int. Euro-Par Conf. on Parallel Processing, pages 682--694, 2007."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1145\/277830.277903","volume-title":"Proc. Int. Conf. on Supercomputing","author":"Sohn A.","year":"1998","unstructured":"A. Sohn and Y. Kodama . Load balanced parallel radix sort . In Proc. Int. Conf. on Supercomputing , pages 305 -- 312 , 1998 . 10.1145\/277830.277903 A. Sohn and Y. Kodama. Load balanced parallel radix sort. In Proc. Int. Conf. on Supercomputing, pages 305--312, 1998. 10.1145\/277830.277903"},{"key":"e_1_2_1_33_1","first-page":"160","volume-title":"Proc. Int. Conf. on Parallel Processing","author":"Wassenberg J.","year":"2011","unstructured":"J. Wassenberg and P. Sanders . Engineering a multi-core radix sort . In Proc. Int. Conf. on Parallel Processing , pages 160 -- 169 , 2011 . J. Wassenberg and P. Sanders. Engineering a multi-core radix sort. In Proc. Int. Conf. on Parallel Processing, pages 160--169, 2011."},{"key":"e_1_2_1_34_1","unstructured":"www.itrs.net.  www.itrs.net."},{"key":"e_1_2_1_35_1","first-page":"712","volume-title":"Proc. Int. Conf. on Supercomputing","author":"Zagha M.","year":"1991","unstructured":"M. Zagha and G. E. Blelloch . Radix Sort For Vector Multiprocessors . In Proc. Int. Conf. on Supercomputing , pages 712 -- 721 , 1991 . 10.1145\/125826.126164 M. Zagha and G. E. Blelloch. Radix Sort For Vector Multiprocessors. In Proc. Int. Conf. on Supercomputing, pages 712--721, 1991. 10.1145\/125826.126164"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:16:00Z","timestamp":1672222560000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824050"}},"subtitle":["an efficient parallel algorithm for in-place radix sort"],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":35,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824050"],"URL":"https:\/\/doi.org\/10.14778\/2824032.2824050","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}