Abstract
Sorting is an integral part of numerous algorithms and, therefore, efficient sorting support is needed by many applications. This paper presents a parallel sorting library providing efficient implementations of parallel sorting methods that can be easily adapted to a specific application. A parallel implementation of the Fast Multipole Method is used to demonstrate the configuration and the usage of the library. We also describe a parallel sorting method which provides the ability to adapt to the actual amount of memory available. Performance results for a BlueGene/L supercomputer are given.
Measurements are performed on the BlueGene/L system at the John von Neumann Institute for Computing, Jülich, Germany. http://www.fz-juelich.de/zam/ ibm-bgl
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Knuth, D.E.: The Art of Computer Programming, vol. III: Sorting and Searching. Addison-Wesley, Reading (1973)
Akl, S.G.: Parallel Sorting Algorithms. Academic Press, Inc., London (1990)
Hu, Y., Johnsson, S.L.: A data-parallel implementation of O(N) hierarchical N-body methods. In: Supercomputing 1996. Proceedings of the 1996 ACM/IEEE conference on Supercomputing, IEEE Computer Society Press, Los Alamitos (1996)
Sohn, A., Simon, H.: S-HARP: a scalable parallel dynamic partitioner for adaptive mesh-based computations. In: Supercomputing 1998. Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), IEEE Computer Society Press, Los Alamitos (1998)
Devine, K., Boman, E., Heapby, R., Hendrickson, B., Vaughan, C.: Zoltan data management service for parallel dynamic applications. Computing in Science and Engineering 4(2), 90–97 (2002)
Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. Journal of Computational Physics 73, 325–348 (1987)
Zheng, S.Q., Calidas, B., Zhang, Y.: An efficient general in-place parallel sorting scheme. The Journal of Supercomputing 14(1), 5–17 (1999)
Jiménez-González, D., Navarro, J.J., Larriba-Pey, J.L.: Fast parallel in-memory 64-bit sorting. In: ICS 2001: Proceedings of the 15th international conference on Supercomputing, pp. 114–122 (2001)
Lee, S.J., Jeon, M., Kim, D., Sohn, A.: Partitioned parallel radix sort. Journal of Parallel and Distributed Computing 62(4), 656–668 (2002)
Tridgell, A., Brent, R.P.: A general-purpose parallel sorting algorithm. International Journal of High Speed Computing (IJHSC) 7(2), 285–302 (1995)
McIlroy, P.M., Bostic, K., McIlroy, M.D.: Engineering radix sort. Computing Systems 6(1), 5–27 (1993)
Huang, B.C., Langston, M.A.: Practical in-place merging. Communications of the ACM 31(3), 348–352 (1988)
Adiga, N.R., et al.: An overview of the BlueGene/L supercomputer. In: Supercomputing 2002. Proceedings of the 2002 ACM/IEEE conference on Supercomputing, pp. 1–22. IEEE Computer Society Press, Los Alamitos (2002)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dachsel, H., Hofmann, M., Rünger, G. (2007). Library Support for Parallel Sorting in Scientific Computations. In: Kermarrec, AM., Bougé, L., Priol, T. (eds) Euro-Par 2007 Parallel Processing. Euro-Par 2007. Lecture Notes in Computer Science, vol 4641. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74466-5_73
Download citation
DOI: https://doi.org/10.1007/978-3-540-74466-5_73
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74465-8
Online ISBN: 978-3-540-74466-5
eBook Packages: Computer ScienceComputer Science (R0)