{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,3]],"date-time":"2024-03-03T10:13:29Z","timestamp":1709460809815},"reference-count":13,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,24]],"date-time":"2006-10-24T00:00:00Z","timestamp":1161648000000},"content-version":"vor","delay-in-days":5289,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1992,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Sorting on a parallel architecture is a communications intensive event which can incur a high penalty in applications where it is required. In the case of particle simulation, only integer sorting is necessary, and sequential implementations easily attain the minimum performance bound of <jats:italic>O(N)<\/jats:italic> for <jats:italic>N<\/jats:italic> particles. Parallel implementations, however, have to cope with the parallel sorting problem which, in addition to incurring a heavy communications cost, can make the minimum performance bound difficult to attain. This paper demonstrates how the sorting problem in a particle simulation can be reduced to a merging problem, and describes an efficient data parallel algorithm to solve this merging problem in a particle simulation. The new algorithm is shown to be optimal under conditions usual for particle simulation, and its fieldwise implementation on the Connection Machine is analysed in detail. The new algorithm is about four times faster than a fieldwise implementation of radix sort on the Connection Machine.<\/jats:p>","DOI":"10.1002\/cpe.4330040304","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:23:37Z","timestamp":1163780617000},"page":"241-255","source":"Crossref","is-referenced-by-count":8,"title":["Data parallel sorting for particle simulation"],"prefix":"10.1002","volume":"4","author":[{"given":"Leonardo","family":"Dagum","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,24]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Molecular Gas Dynamics","author":"Bird G. A.","year":"1976"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.857625"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"L.Dagum \u2018Implementation of a hypersonic rarefied flow particle simulation on the connection machine\u2019 Proceedings of Supercomputing '89 Reno NV 1989.","DOI":"10.1145\/76263.76268"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/7902.7903"},{"key":"e_1_2_1_6_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"},{"issue":"11","key":"e_1_2_1_7_2","first-page":"1526","article-title":"Scans as primitive parallel operations","volume":"38","author":"Blelloch G.","year":"1989","journal-title":"IEEE Trans."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218041"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90120-8"},{"key":"e_1_2_1_10_2","unstructured":"L.Dagum On the Suitability of the Connection Machine for Direct Particle Simulation Ph.D. thesis Department of Aeronautics and Astronautics Stanford University 1990."},{"key":"e_1_2_1_11_2","unstructured":"S.Chatterjee G. E.BlellochandM.Zagha \u2018Scan primitives for vector computers\u2019 Proceedings Supercomputing '90 New York NY 1990."},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"L.Dagum \u2018Three dimensional direct particle simulation on the connection machine\u2019 AIAA 91\u20131365(1991).","DOI":"10.2514\/6.1991-1365"},{"issue":"5","key":"e_1_2_1_13_2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1080\/00029890.1986.11971821","article-title":"Shuffling cards and stopping times","volume":"93","author":"Aldous D.","year":"1986","journal-title":"American Mathematical Monthly"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"G.Blelloch C. E.Leiserson B. M.Maggs C. G.Plaxton S. J.SmithandM.Zagha \u2018A comparison of sorting algorithms for the connection machine CM\u20102\u2019 inProceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures 1991.","DOI":"10.1145\/113379.113380"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330040304","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330040304","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T16:42:57Z","timestamp":1698165777000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330040304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["10.1002\/cpe.4330040304"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330040304","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"value":"1040-3108","type":"print"},{"value":"1096-9128","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}