{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T23:09:09Z","timestamp":1648681749673},"reference-count":48,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Generation Computer Systems"],"published-print":{"date-parts":[[2002,1]]},"DOI":"10.1016\/s0167-739x(01)00056-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T12:23:57Z","timestamp":1027599837000},"page":"353-372","source":"Crossref","is-referenced-by-count":4,"title":["On a scheme for parallel sorting on heterogeneous clusters"],"prefix":"10.1016","volume":"18","author":[{"given":"Christophe","family":"C\u00e9rin","sequence":"first","affiliation":[]},{"given":"Jean-Luc","family":"Gaudiot","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"4","key":"10.1016\/S0167-739X(01)00056-5_BIB1","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/0743-7315(92)90075-X","article-title":"Parallel sorting by regular sampling","volume":"14","author":"Shi","year":"1992","journal-title":"J. Parallel Distrib. Comput."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB2","doi-asserted-by":"crossref","unstructured":"H. Li, K.C. Sevcik, Parallel sorting by over-partitioning, in: Proceedings of the Sixth Annual Symposium on Parallel Algorithms and Architectures, ACM Press, New York, June 1994, pp. 46\u201356.","DOI":"10.1145\/181014.192329"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB3","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1109\/71.852399","article-title":"Minimizing communication in the bitonic sort","volume":"11","author":"Lee","year":"2000","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB4","unstructured":"S. Akl, Parallel Sorting Algorithms, Academic Press, New York, 1985."},{"issue":"3","key":"10.1016\/S0167-739X(01)00056-5_BIB5","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1109\/71.674316","article-title":"A practical approach to dynamic load balancing","volume":"9","author":"Watts","year":"1998","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB6","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/7531.7532","article-title":"A logarithmic time sort for linear size networks","volume":"34","author":"Reif","year":"1987","journal-title":"J. ACM"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB7","doi-asserted-by":"crossref","unstructured":"J.H. Reif, L.G. Valiant, A logarithmic time sort for linear size networks, in: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, MA, April 25\u201327, 1983, pp. 10\u201316.","DOI":"10.1145\/800061.808727"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB8","doi-asserted-by":"crossref","first-page":"1079","DOI":"10.1016\/0167-8191(93)90019-H","article-title":"On the versatility of parallel sorting by regular sampling","volume":"19","author":"Li","year":"1993","journal-title":"Parallel Comput."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB9","unstructured":"D.R. Helman, J. J\u00e1j\u00e1, D.A. Bader, A new deterministic parallel sorting algorithm with an experimental evaluation, Technical Report CS-TR-3670 and UMIACS-TR-9654, Institute for Advanced Computer Studies, University of Maryland, College Park, MD, August 1996."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB10","doi-asserted-by":"crossref","unstructured":"C. C\u00e9rin, J.-L. Gaudiot, Algorithms for stable sorting to minimize communications in networks of workstations and their implementations in BSP, in: Proceedings of the IEEE Computer Society International Workshop on Cluster Computing (IWCC\u201999), 1999, pp. 112\u2013120.","DOI":"10.1109\/IWCC.1999.810815"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB11","doi-asserted-by":"crossref","unstructured":"I. Stojmenovic, Constant time BSR solutions to parenthesis matching, tree decoding, and tree reconstruction from its traversals, in: Proceedings of the IEEE Transaction of Parallel and Distributed Systems, Vol. 7, February 1996.","DOI":"10.1109\/71.485530"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB12","unstructured":"D.R. Helman, J. J\u00e1j\u00e1, Sorting on clusters of SMPs, Inform.: An Int. J. Comput. Inform. 23 (1999)."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB13","unstructured":"D.R. Helman, J. J\u00e1j\u00e1, Sorting on clusters of SMPs, Technical Report CS-TR-3833, University of Maryland, College Park, MD, November 1997."},{"issue":"2","key":"10.1016\/S0167-739X(01)00056-5_BIB14","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01952679","article-title":"Analysis and benchmarking of two parallel sorting algorithms: hyperquicksort and quickmerge","volume":"29","author":"Quinn","year":"1989","journal-title":"BIT"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB15","doi-asserted-by":"crossref","unstructured":"K.E. Batcher, Sorting networks and their applications, in: Proceedings of the AFIPS Spring Joint Computer Conference, 1968, pp. 307\u2013314.","DOI":"10.1145\/1468075.1468121"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB16","doi-asserted-by":"crossref","unstructured":"D.T. Blackston, A. Ranade, SnakeSort: a family of simple optimal randomized sorting algorithms, in: P.B. Hariri, Salim, Berra (Eds.), Proceedings of the 1993 International Conference on Parallel Processing, Algorithms and Applications, Vol. 3, CRC Press, Syracuse, NY, August 1993, pp. 201\u2013204.","DOI":"10.1109\/ICPP.1993.164"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB17","doi-asserted-by":"crossref","unstructured":"A. Borodin, J.E. Hopcroft, Routing, merging, and sorting on parallel models of computation, in: Proceedings of the ACM Symposium on Theory of Computing (STOC\u201982), ACM Press, Baltimore, MD, May 1982, pp. 338\u2013344.","DOI":"10.1145\/800070.802209"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB18","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","article-title":"Parallel merge sort","volume":"17","author":"Cole","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB19","doi-asserted-by":"crossref","unstructured":"T. Leighton, Tight bounds on the complexity of parallel sorting, in: Proceedings of the ACM Symposium on Theory of Computing (STOC\u20191984), ACM Press, Baltimore, MD, April 1984, pp. 71\u201380.","DOI":"10.1145\/800057.808667"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB20","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1145\/322326.322329","article-title":"Parallel permutation and sorting algorithms and a new generalized connection network","volume":"29","author":"Nassimi","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB21","doi-asserted-by":"crossref","unstructured":"C.G. Plaxton, Efficient computation on sparse interconnection networks, Technical Report STAN-CS-89-1283, Department of Computer Science, Stanford University, September 1989.","DOI":"10.1109\/SFCS.1989.63509"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB22","unstructured":"A. Tridgell, R. Brent, An implementation of a general-purpose parallel sorting algorithm, Technical Report TR-CS-93-01, Computer Science Laboratory, Australian National University, February 1993."},{"issue":"1","key":"10.1016\/S0167-739X(01)00056-5_BIB23","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1142\/S0129626499000098","article-title":"Efficient deterministic sorting on the BSP model","volume":"9","author":"Gerbessiotis","year":"1999","journal-title":"Parallel Process. Lett."},{"issue":"3","key":"10.1016\/S0167-739X(01)00056-5_BIB24","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1142\/S0129626499000384","article-title":"A randomized BSP\/CGM algorithm for the maximal independent set problem","volume":"9","author":"Afonso Ferreira","year":"1999","journal-title":"Parallel Process. Lett."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB25","doi-asserted-by":"crossref","unstructured":"G. Blelloch, C. Leiserson, B. Maggs, A comparison of sorting algorithms for the connection machine CM-2, in: Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, July 1991.","DOI":"10.1145\/113379.113380"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB26","unstructured":"M.P.I. Forum, MPI: a message passing interface standard, Technical Report CS-94-230, University of Tennessee, Knoxville, TX, May 1994."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB27","unstructured":"O. Bonorden, B. Juurlink, I. von Otte, I. Rieping, The Paderborn University BSP (pub) library \u2014 design, implementation and performance, in: Proceedings of the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, IEEE Computer Society, San Juan, Puerto Rico, April 12\u201316, 1999."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB28","doi-asserted-by":"crossref","unstructured":"L. Valiant, A bridging model for parallel computation, Commun. ACM 33 (August 1990), pp. 103\u2013111.","DOI":"10.1145\/79173.79181"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB29","doi-asserted-by":"crossref","unstructured":"F. Dehne, A. Fabri, A. Rau-Chaplin, Scalable parallel computational geometry for coarse grained multicomputers, in: Proceedings of the ACM Symposium on Computational Geometry, 1993, pp. 298\u2013307.","DOI":"10.1145\/160985.161154"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB30","doi-asserted-by":"crossref","unstructured":"D. Culler, R. Karp, D. Patterson, A. Sahay, K. Schauser, E. Santos, R. Subramonian, T. von Eicken, LogP: towards a realistic model of parallel computation, in: Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming, 1993, pp. 1\u201312.","DOI":"10.1145\/155332.155333"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB31","unstructured":"R. Miller, J. Reed, The Oxford BSP library: user\u2019s guide, Technical Report, Oxford University Computing Laboratory, 1994."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB32","unstructured":"B.A. Shirazi, A.R. Hurson, K.M. Kavi, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Soc. Press, Silver Spring, MD, 1995."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB33","doi-asserted-by":"crossref","unstructured":"H. Topcuoglu, S. Hariri, M.-Y. Wu, Task scheduling algorithms for heterogeneous processors, in: Proceedings of the Eighth Heterogeneous Computing Workshop (HCW\u201999), IEEE Computer Press, San Juan, Puerto Rico, April 1999.","DOI":"10.1109\/HCW.1999.765092"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB34","doi-asserted-by":"crossref","unstructured":"R.C. Agarwal, A super scalar sort algorithm for RISC processors, SIGMOD Record (ACM Special Interest Group on Management of Data), Vol. 25, 1996, pp. 240\u2013246.","DOI":"10.1145\/235968.233336"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB35","doi-asserted-by":"crossref","unstructured":"C. Nyberg, T. Barclay, Z. Cvetanovic, J. Gray, D. Lomet, AlphaSort: an RISC machine sort, SIGMOD Record (ACM Special Interest Group on Management of Data), Vol. 23, 1994, pp. 233\u2013242.","DOI":"10.1145\/191843.191884"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB36","doi-asserted-by":"crossref","unstructured":"J. Larriba-Pey, D. Jimenez, J. Navarro, An analysis of superscalar sorting algorithms on an r8000 processor, in: Proceedings of the 17th International Conference of the Chilean Computer Science Society (SCCC\u20191997), IEEE Computer Society, Valpariso, November 12\u201314, 1997.","DOI":"10.1109\/SCCC.1997.637084"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB37","doi-asserted-by":"crossref","unstructured":"Rajasekaran, A framework for simple sorting algorithms on parallel disk systems (extended abstract), in: SPAA: Annual ACM Symposium on Parallel Algorithms and Architectures, 1998.","DOI":"10.1145\/277651.277675"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB38","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/S0167-8191(97)00014-8","article-title":"Early experiences in evaluating the parallel disk model with the ViC\u2217 implementation","volume":"23","author":"Cormen","year":"1997","journal-title":"Parallel Comput."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB39","unstructured":"M.D. Pearson, Fast out-of-core sorting on parallel disk systems, Technical Report PCSTR99-351, Department of Computer Science, Dartmouth College, Hanover, NH, June 1999."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB40","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/BF01185207","article-title":"Algorithms for parallel memory. I: Two-level memories","volume":"12","author":"Vitter","year":"1994","journal-title":"Algorithmica"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB41","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01185208","article-title":"Algorithms for parallel memory. II: Hierarchical multilevel memories","volume":"12","author":"Vitter","year":"1994","journal-title":"Algorithmica"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB42","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","article-title":"The input\/output complexity of sorting and related problems","volume":"31","author":"Aggarwal","year":"1988","journal-title":"Commun. ACM"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB43","doi-asserted-by":"crossref","unstructured":"K. Salem, H. Garcia-Molina, Disk striping, in: Proceedings of the Second International Conference on Data Engineering, ACM, February 1986, pp. 336\u2013342.","DOI":"10.1109\/ICDE.1986.7266238"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB44","doi-asserted-by":"crossref","unstructured":"M.Y. Kim, Synchronized disk interleaving, in: Proceedings of the IEEE Transactions on Computers, Vol. C35, November 1986.","DOI":"10.1109\/TC.1986.1676699"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB45","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1145\/210332.210343","article-title":"Greed sort: optimal deterministic sorting on parallel disks","volume":"42","author":"Nodine","year":"1995","journal-title":"J. ACM"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB46","unstructured":"D.E. Knuth, Sorting and Searching, The Art of Computer Programming, Vol. 3, 2nd Edition, Addison-Wesley, Reading, MA, 1998."},{"key":"10.1016\/S0167-739X(01)00056-5_BIB47","doi-asserted-by":"crossref","unstructured":"D.J. DeWitt, J.F. Naughton, D.A. Schneider, Parallel sorting on a shared-nothing architecture using probabilistic splitting, in: Proceedings of the First International Conference on Parallel and Distributed Information Systems, December 1991, pp. 280\u2013291.","DOI":"10.1109\/PDIS.1991.183115"},{"key":"10.1016\/S0167-739X(01)00056-5_BIB48","doi-asserted-by":"crossref","unstructured":"J. Sibeyn, M. Kaufmann, BSP-like external-memory computation, Technical Report MPI-I-97-1001, Max-Planck Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany, 1997.","DOI":"10.1007\/3-540-62592-5_75"}],"container-title":["Future Generation Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167739X01000565?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167739X01000565?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T10:58:08Z","timestamp":1578481088000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0167739X01000565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["S0167739X01000565"],"URL":"https:\/\/doi.org\/10.1016\/s0167-739x(01)00056-5","relation":{},"ISSN":["0167-739X"],"issn-type":[{"value":"0167-739X","type":"print"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}