Abstract
List ranking is one of the fundamental techniques in parallel algorithm design. Hayashi, Nakano, and Olariu proposed a deterministic list ranking algorithm that runs in O(log* n) time and a randomized one that runs in O(1) expected time, both on a reconfigurable mesh of size n × n. In this paper we show that the same deterministic and randomized time complexities can be achieved using only O(n 1+∈) processors, where ∈ is an arbitrary positive constant < 1. To reduce the number of processors, we adopt a reconfigurable mesh of high dimensions and develop a new technique called path embedding.
This work was supported by the Brain Korea 21 Project.
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.
References
Chen, Y. C. and Chen, W. T.: Constant Time Sorting on Reconfigurable Meshes. IEEE Transactions on Computers. Vol. 43, No. 6 (1994) 749–751
Chen, G. H. and Wang, B. F.: Sorting and Computing Convex Hull on Processor Arrays with Reconfigurable Bus System. Information Science. 72 (1993) 191–206
Chen, G. H., Wang, B. F., and Lu, C. J.: On Parallel Computation of the Algebraic Path Problem. IEEE Transactions on Parallel and Distributed Systems. Vol. 3, No. 2, Mar. (1992) 251–256
Hao, E., MacKenzie, P. D., and Stout, Q. F.: Selection on the Reconfigurable Mesh. Proc. of fourth Symposium on the Frontiers of Massively Parallel Computation. (1992) 38–45
Hayashi, T., Nakano, K., and Olariu, S.: Efficient List Ranking on the Reconfigurable Mesh, with Applications. Proc. of 7th International Simposium on Algorithms and Computation, ISAAC’96. (1996) 326–335
Jang, J. and Prasanna, V. K.: Efficient Parallel Algorithms for Geometric Problems on Reconfigurable Mesh. Proc. of International Conference on Parallel Processing. 3 (1992) 127–130
Jang, J. and Prasanna, V. K.: An Optimal Sorting Algorithm on Reconfigurable Mesh. International Parallel Processing Symposium. (1992) 130–137
Jenq, J. F. and Sahni, S.: Reconfigurable Mesh Algorithms for the Hough Transform. Proc. of International Conference on Parallel Processing. 3 (1991) 34–41
Li, H. and Maresca, M.: Polymorphic-torus Network. IEEE Transactions on Computers. 38 (1989) 1345–1351
Maresca, M.: Polymorphic Processor Arrays. IEEE Transactions on Parallel and Distributed Systems. 4 (1993) 490–506
Miller, R., Prasanna Kumar, V. K., Reisis, D. I., and Stout, Q. F.: Parallel Computations on Reconfigurable Mesh. Technical Report # 229. USC, Mar. (1922)
Miller, R. and Stout, Q. F.: Efficient Parallel Convex Hull Algorithms. IEEE Transactions on Computer. Vol 37, No. 12, Dec. (1988) 1605–1618
Niven, I., Zuckerman, H. S., and Montgomery, H. L.: An Introduction to the Theory of Numbers, Fifth Edition. (1991) John Wiley & Sons
Olariu, S., Schwing, J. L., and Jhang, J.: Fundamental Algorithms on Reconfigurable Meshes. Proc. of 29th Annual Allerton Conference on Communication, Control, and Computing. (1991) 811–820
Wang, B. F. and Chen, G. H.: Constant Time Algorithms for the Transitive Closure and Some Related Graph Problems on Processor Arrays with Reconfigurable Bus System. IEEE Transactions on Parallel and Distributed Systems. Vol. 1, No. 4, Oct. (1990) 500–507
Wylie, J.C.: The Complexity of Parallel Computation. Doctoral Thesis, Cornell University. (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, SR., Park, K. (2000). Efficient List Ranking Algorithms on Reconfigurable Mesh. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_26
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive