An optimal linked list prefix algorithms on a local memory computer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An optimal linked list prefix algorithms on a local memory computer

Full text

Pdf (586 KB)

Source

ACM Annual Computer Science Conference archive
Proceedings of the 17th conference on ACM Annual Computer Science Conference table of contents

Louisville, Kentucky

Pages: 278 - 286

Year of Publication: 1989

ISBN:0-89791-299-3

Author

Y. Han

Department of Computer Science, University of Kentucky, Lexlngton, KY

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 9, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/75427.75462 What is a DOI?

ABSTRACT

We present a deterministic parallel algorithm for the linked list prefix problem. It computes linked list prefix for an input list of n elements in time O(n/p+logn) on a local memory PRAM model using p processors and p shared memory cells. We also show that a maximal matching for a linked list can be computed in O(logG(n)) time with n processors and n shared cells.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. J. Anderson, G. L. Miller. Optimal parallel algorithms for the llst ranking problem. USC- Tech. Rept. 1986.
	2	Richard J. Anderson , Gary L. Miller, Deterministic Parallel List Ranking, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.81-90, June 28-July 01, 1988
	3	R. A. Borodinand J. E. Hoperoft Routing computation, Proc. 14th ACM Symposium on Theory of Computing, San Franslsco, 338- 344(April, 1982).
	4	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	5	R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications to list, tree and graph problems, 27th gymp. on Foundations of Comput. Scl., IEEE, 478- 491(1986).
	6	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States [doi>10.1145/28395.28429]
	7	Allan Gottlieb , Clyde P. Kruskal, Complexity Results for Permuting Data and Other Computations on Parallel Processors, Journal of the ACM (JACM), v.31 n.2, p.193-209, April 1984 [doi>10.1145/62.322423]
	8	Y. Ran. Designing fast and efficient parallel algorithms. Ph.D. dissertation. Dept. Computer Sci., Duke Univ., 1987.
	9	Y. Han. An optimal parallel algorithm for computing linked list prefix, Tech. Report, TR No. 100-87, Dept. Computer Sel., U. of Kentucky-Lexington, Nov. 1987.
	10	Hermann Jung , Kurt Mehlhorn, Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees, Information Processing Letters, v.27 n.5, p.227-236, April 28, 1988 [doi>10.1016/0020-0190(88)90084-1]
	11	C.P. Kruskal, T. MadeJ, L. Rudolph. Parallel prefix on fully connected direct connection machine, Proceedings of 1986 International Conf. on Parallel Processing, 278-284.
	12	C.P. Kruskal, L. Rudolph, M. Snir. The power of parallel prefix, IEEE Trans. Comput., Vol. C-34, No. I0, 965-968(0ct. 1985).
	13	Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
	14	N. Linial. Distributive graph algorithms global solutions from local data, Proc. 1987 IEEE Annual Symposium on Foundations of Computer Science, 331-336(1987).
	15	G. L. Miller, J. H. Reif. Parallel tree contraction and its application, 26th Symp. on Foundations of Computer Scl., IEEE 478- 489(1985).
	16	G. F. Pfister and V. A. Norton. "Hot Spot" contention and combining in multistage interconnection networks, IEEE Trans. Comput., Vol. C-34, No. I0, Oct. 1985, 934-948.
	17	J.H. Reif. An optimal parallel algorithm for integer sorting, 26th Symp. on Foundations of Computer Sci., IEEE, 291-298(1985).
	18	J. H. Reif. Probabilistic parallel prefix computation, Proe. of 1984 International Conf. on Parallel Processing, 493-443(Aug. 1984).
	19	M. Snir. On parallel searching, SlAM J. Comput., Vol. 14, No. 3, 688-708(Aug. 1985).
	20	R.A. Wagner and Y. Han. Parallel algorithms for bucket sorting and the data dependent prefix problem, Proceedings 1986 International Conf. on Parallel Processing, 924-930.
	21	James C. Wyllie, The Complexity of Parallel Computations, Cornell University, Ithaca, NY, 1979

CITED BY 2

	Yijie Han , Xiaojun Shen, Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.419-428, January 17-19, 1999, Baltimore, Maryland, United States
	Y. Han, Matching partition a linked list and its optimization, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.246-253, June 18-21, 1989, Santa Fe, New Mexico, United States