Abstract
Two improved list-ranking algorithms are presented. The “peeling-off” algorithm leads to an optimal PRAM algorithm, but was designed with application on a real parallel machine in mind. It is simpler than earlier algorithms, and in a range of problem sizes, where previously several algorithms where required for the best performance, now this single algorithm suffices. If the problem size is much larger than the number of available processors, then the “sparse-ruling-sets” algorithm is even better. In previous versions this algorithm had very restricted practical application because of the large number of communication rounds it was performing. This weakness is overcome by adding two new ideas, each of which reduces the number of communication rounds by a factor of two.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bäumker, A., Dittrich, W., Heide, F.M.A.D.: Truly Efficient Parallel Algorithms: c- Optimal Multisearch for an Extension of the BSP-Model. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol. 979, pp. 17–30. Springer, Heidelberg (1995)
Hsu, T.-s., Ramachandran, V.: Efficient Massively Parallel Implementation of some Combinatorial Algorithms. Theoretical Computer Science 162(2), 297–322 (1996)
McColl, W.F.: Universal Computing. In: Fraigniaud, P., Mignotte, A., Bougé, L., Robert, Y. (eds.) Euro-Par 1996. LNCS, vol. 1123, pp. 25–36. Springer, Heidelberg (1996)
Ranade, A.: A Simple Optimal List Ranking Algorithm. In: Proc. of 5th High Performance Computing. Tata McGraw-Hill Publishing Company, New York (1998)
Reid-Miller, M.: List Ranking and List Scan on the Cray C-90. Journal of Computer and System Sciences 53(3), 344–356 (1996)
Sibeyn, J.F.: List Ranking on Interconnection Networks. In: Fraigniaud, P., Mignotte, A., Bougé, L., Robert, Y. (eds.) Euro-Par 1996. LNCS, vol. 1123, pp. 799–808. Springer, Heidelberg (1996)
Sibeyn, J.F.: Better Trade-offs for Parallel List Ranking. In: Proc. 9th Symposium on Parallel Algorithms and Architectures, pp. 221–230. ACM, New York (1997)
Valiant, L.G.: A Bridging Model for Parallel Computation. Communications of the ACM 33(8), 103–111 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sibeyn, J.F. (1999). Ultimate Parallel List Ranking?. In: Banerjee, P., Prasanna, V.K., Sinha, B.P. (eds) High Performance Computing – HiPC’99. HiPC 1999. Lecture Notes in Computer Science, vol 1745. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-46642-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-46642-0_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66907-4
Online ISBN: 978-3-540-46642-0
eBook Packages: Springer Book Archive