{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:28Z","timestamp":1750220788309,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T00:00:00Z","timestamp":1589760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["SQ2018YFB020061"],"award-info":[{"award-number":["SQ2018YFB020061"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61860206011, 61625202 , 61772182, 61750110531, and 61472126"],"award-info":[{"award-number":["61860206011, 61625202 , 61772182, 61750110531, and 61472126"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>\n            The huge data volumes, big data, and the emergence of new parallel architectures lead to revisiting classic computer science topics. The motivation of the proposed work for revisiting the parallel\n            <jats:italic>k<\/jats:italic>\n            -way in-place merging is primarily related to the unsuitability of the current state-of-the-art parallel algorithms for multicore CPUs with shared memory. These architectures can be profitably employed to solve this problem in parallel. Recently, Intel introduced the parallel Standard Template Library (STL) implementation for multicore CPUs, but it has no in-place merge function with the in-place property. We propose Partition-Shuffle-merge (\n            <jats:italic>PS-merge<\/jats:italic>\n            ) to address this problem.\n            <jats:italic>PS-merge<\/jats:italic>\n            includes combining sequence partitioning with the in-place perfect shuffle effect to address the\n            <jats:italic>k<\/jats:italic>\n            -way merge task. At first, each sequence is divided into\n            <jats:italic>t<\/jats:italic>\n            equal-sized partitions or ranges. Thus, each partition is spread over at most\n            <jats:italic>k<\/jats:italic>\n            sequences. Then, perfect shuffle is utilized as a replacement for the classic block rearrangement. Finally, range subpartitions are merged using a sequential in-place merging algorithm. To evaluate the proposed algorithm, as\n            <jats:italic>PS-merge<\/jats:italic>\n            produces the standard merging format, we compare this algorithm against the state-of-the-art methods, bitonic merge, a parallel binary merge tree, and lazy-merge.\n            <jats:italic>PS-merge<\/jats:italic>\n            shows a significant improvement in overall execution time.\n          <\/jats:p>","DOI":"10.1145\/3391443","type":"journal-article","created":{"date-parts":[[2020,5,25]],"date-time":"2020-05-25T18:00:14Z","timestamp":1590429614000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["A Time-space Efficient Algorithm for Parallel\n            <i>k<\/i>\n            -way In-place Merging based on Sequence Partitioning and Perfect Shuffle"],"prefix":"10.1145","volume":"7","author":[{"given":"Ahmad","family":"Salah","sequence":"first","affiliation":[{"name":"College of Computer Science and Electrical Engineering, Hunan University, China, and Faculty of Computers and Informatics, Zagazig University, Zagazig, Sharkia, Egypt"}]},{"given":"Kenli","family":"Li","sequence":"additional","affiliation":[{"name":"Hunan University, China, and National Supercomputing Center in Changsha,, Changsha, Hunan, China"}]},{"given":"Qing","family":"Liao","sequence":"additional","affiliation":[{"name":"Department of Computer Science 8 Technology, Harbin Institute of Technology (Shenzhen), Shenzhen, Guangdong, China"}]},{"given":"Mervat","family":"Hashem","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, Hunan, China"}]},{"given":"Zhiyong","family":"Li","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, Hunan, China"}]},{"given":"Anthony T.","family":"Chronopoulos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at San Antonio, USA, and Department of Computer Engineering and Informatics, University of Patras, Rio, Greece"}]},{"given":"Albert Y.","family":"Zomaya","sequence":"additional","affiliation":[{"name":"School of Computer Science, The University of Sydney, Sydney, NSW, Australia"}]}],"member":"320","published-online":{"date-parts":[[2020,5,18]]},"reference":[{"volume-title":"Algorithm Engineering","author":"Ajwani Deepak","key":"e_1_2_1_1_1","unstructured":"Deepak Ajwani and Henning Meyerhenke . 2010. Realistic computer models . In Algorithm Engineering . Springer , 194--236. Deepak Ajwani and Henning Meyerhenke. 2010. Realistic computer models. In Algorithm Engineering. Springer, 194--236."},{"key":"e_1_2_1_2_1","unstructured":"Avmoskal. 2018. Get Started with Parallel STL. Retrieved from https:\/\/software.intel.com\/en-us\/get-started-with-pstl.  Avmoskal. 2018. Get Started with Parallel STL. Retrieved from https:\/\/software.intel.com\/en-us\/get-started-with-pstl."},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"A new constant-time parallel algorithm for merging","volume":"75","author":"Bahig Hazem M.","year":"2018","unstructured":"Hazem M. Bahig . 2018 . A new constant-time parallel algorithm for merging . J. Supercomput. 75 , 2 (2018), 1 -- 16 . Hazem M. Bahig. 2018. A new constant-time parallel algorithm for merging. J. Supercomput. 75, 2 (2018), 1--16.","journal-title":"J. Supercomput."},{"volume-title":"Construction (AFIPS\u201968 (Spring))","author":"Batcher K. E.","key":"e_1_2_1_4_1","unstructured":"K. E. Batcher . 1968. Sorting networks and their applications . In Construction (AFIPS\u201968 (Spring)) , Vol. 32 . ACM , 307--314. DOI:https:\/\/doi.org\/10.1145\/1468075.1468121 10.1145\/1468075.1468121 K. E. Batcher. 1968. Sorting networks and their applications. In Construction (AFIPS\u201968 (Spring)), Vol. 32. ACM, 307--314. DOI:https:\/\/doi.org\/10.1145\/1468075.1468121"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00116"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218014"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.660313"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2010.12.172"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378568"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90065-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/43.1.40"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90048-4"},{"volume-title":"Fundamentals of Computation Theory","author":"Geffert Viliam","key":"e_1_2_1_13_1","unstructured":"Viliam Geffert and Jozef Gajdo\u0161 . 2009. Multiway in-place merging . In Fundamentals of Computation Theory . Springer , 133--144. Viliam Geffert and Jozef Gajdo\u0161. 2009. Multiway in-place merging. In Fundamentals of Computation Theory. Springer, 133--144."},{"volume-title":"Technical Report","author":"Gries David","key":"e_1_2_1_14_1","unstructured":"David Gries and Harlan Mills . 1981. Swapping Sections . Technical Report . Cornell University . David Gries and Harlan Mills. 1981. Swapping Sections. Technical Report. Cornell University."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.88483"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062354"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/42392.42403"},{"key":"e_1_2_1_18_1","volume-title":"A simple in-place algorithm for in-shuffle. CoRR abs\/0805.1","author":"Jain Peiyush","year":"2008","unstructured":"Peiyush Jain . 2008. A simple in-place algorithm for in-shuffle. CoRR abs\/0805.1 ( 2008 ). Peiyush Jain. 2008. A simple in-place algorithm for in-shuffle. CoRR abs\/0805.1 (2008)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55599-4_79"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69507-3_29"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1791834.1791859"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_63"},{"volume-title":"Sorting and Searching.","author":"Knuth D. E.","key":"e_1_2_1_23_1","unstructured":"D. E. Knuth . 1973. The Art of Computer Programming , Vol. 3 : Sorting and Searching. Vol. 28. Addison-Wesley . 1175 pages. DOI:https:\/\/doi.org\/10.2307\/2005383 10.2307\/2005383 D. E. Knuth. 1973. The Art of Computer Programming, Vol. 3: Sorting and Searching. Vol. 28. Addison-Wesley. 1175 pages. DOI:https:\/\/doi.org\/10.2307\/2005383"},{"key":"e_1_2_1_24_1","first-page":"744","article-title":"An optimal ordering algorithm without a field of operation","volume":"10","author":"Kronrod M. A.","year":"1969","unstructured":"M. A. Kronrod . 1969 . An optimal ordering algorithm without a field of operation . Soviet Math 10 (1969), 744 -- 746 . M. A. Kronrod. 1969. An optimal ordering algorithm without a field of operation. Soviet Math 10 (1969), 744--746.","journal-title":"Soviet Math"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.852399"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1005107"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90112-1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxw105"},{"key":"e_1_2_1_29_1","first-page":"377","article-title":"Robust-ShuffleMerge: A stable and in-situ merging algorithm","volume":"86","author":"Salah Ahmad","year":"2014","unstructured":"Ahmad Salah , Kenli Li , Mervat Hashem , and Zhiyong Li . 2014 . Robust-ShuffleMerge: A stable and in-situ merging algorithm . Fut. Comput. Inf. Technol. 86 (2014), 377 . Ahmad Salah, Kenli Li, Mervat Hashem, and Zhiyong Li. 2014. Robust-ShuffleMerge: A stable and in-situ merging algorithm. Fut. Comput. Inf. Technol. 86 (2014), 377.","journal-title":"Fut. Comput. Inf. Technol."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2475763"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223205"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90022-2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.02.017"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3391443","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3391443","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:41Z","timestamp":1750200101000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3391443"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,18]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3391443"],"URL":"https:\/\/doi.org\/10.1145\/3391443","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2020,5,18]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}