{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:35:03Z","timestamp":1763458503296,"version":"3.45.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T00:00:00Z","timestamp":1521763200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-0830516, CCF-1217989, CCF-1527568, CCF-0830737 and CCF-1320675"],"award-info":[{"award-number":["CCF-0830516, CCF-1217989, CCF-1527568, CCF-0830737 and CCF-1320675"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2017,3,23]]},"abstract":"<jats:p>\n                    We present a deterministic sorting algorithm, Sample, Partition, and Merge Sort (SPMS), that interleaves the partitioning of a sample sort with merging. Sequentially, it sorts\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    elements in\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) time cache-obliviously with an optimal number of cache misses. The parallel complexity (or critical path length) of the algorithm is\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    log log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ), which improves on previous bounds for deterministic sample sort. The algorithm also has low false sharing costs. When scheduled by a work-stealing scheduler in a multicore computing environment with a global shared memory and\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    cores, each having a cache of size\n                    <jats:italic toggle=\"yes\">M<\/jats:italic>\n                    organized in blocks of size\n                    <jats:italic toggle=\"yes\">B<\/jats:italic>\n                    , the costs of the additional cache misses and false sharing misses due to this parallel execution are bounded by the cost of\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    \u00b7\n                    <jats:italic toggle=\"yes\">M<\/jats:italic>\n                    \/\n                    <jats:italic toggle=\"yes\">B<\/jats:italic>\n                    ) and\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    \u00b7\n                    <jats:italic toggle=\"yes\">B<\/jats:italic>\n                    ) cache misses, respectively, where\n                    <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    is the number of steals performed during the execution. Finally, SPMS is resource oblivious in that the dependence on machine parameters appear only in the analysis of its performance and not within the algorithm itself.\n                  <\/jats:p>","DOI":"10.1145\/3040221","type":"journal-article","created":{"date-parts":[[2017,3,23]],"date-time":"2017-03-23T12:19:44Z","timestamp":1490271584000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Resource Oblivious Sorting on Multicores"],"prefix":"10.1145","volume":"3","author":[{"given":"Richard","family":"Cole","sequence":"first","affiliation":[{"name":"New York University, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,3,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-002-1057-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579338"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378573"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347137"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989553"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810519"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"R. Blumofe and C. E. Leiserson. 1999. Scheduling multithreaded computations by work stealing. J. ACM (1999) 720--748. 10.1145\/324133.324234","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378574"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.04.008"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880944"},{"key":"e_1_2_1_12_1","unstructured":"R. Cole and V. Ramachandran. 2011. Efficient resource oblivious algorithms for multicores. CoRR abs\/1103.4071 (2011)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.28"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2013.86"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"T. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/155332.155333"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258500"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90192-K"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612678"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_2"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3040221","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3040221","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3040221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:26:51Z","timestamp":1763458011000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3040221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,23]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,3,23]]}},"alternative-id":["10.1145\/3040221"],"URL":"https:\/\/doi.org\/10.1145\/3040221","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2017,3,23]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}