Article

Free access

An optimal linked list prefix algorithms on a local memory computer

Author:

Y. HanAuthors Info & Claims

CSC '89: Proceedings of the 17th conference on ACM Annual Computer Science Conference

Pages 278 - 286

https://doi.org/10.1145/75427.75462

Published: 21 February 1989 Publication History

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

[1]

R. J. Anderson, G. L. Miller. Optimal parallel algorithms for the llst ranking problem. USC- Tech. Rept. 1986.

[2]

R. J. Anderson, G. L. Miller. Deterministic parallel llst ranking, Lecture Notes in Computer Science 319, VLSI Algorithms and Archltectures(John Relf ed.), 3rd Aegean

Digital Library

[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 and U. Vishkln. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proc. 18th ACM Symp. on Theory of Computing, 206-219(1986).

Digital Library

[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. V. Goldberg, S. A. Plotkin, G. E. Shannon. Parallel Symmetry-Breaking in Sparse Graphs, Proc. 19th ACM Symposium on Theory of Computing, 315-324(1987).

Digital Library

[7]

A. Gottlieb, C. P. Kruskal. Complexity results for permuting data and other computations on parallel processors, J. ACM, Vol. 31, No. 2, 193-209(Aprll 1984).

Digital Library

[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]

H. Jung, K. Mehlhorn. Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees, Information Processing Letters, Vol. 27, No. 5, 227-236(1988).

Digital Library

[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]

T. Leighton. Tight bounds on the complexity of parallel sorting, IEEE Trans. Comput., C-34, 344-354(1985).

Digital Library

[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]

J. C. Wyllie. The complexity of parallel computation, TR 79-387, Department of Computer Science, Cornell University, Ithaca, NY, 1979.

Digital Library

Cited By

Han YHe X(2022)More Efficient Parallel Integer SortingInternational Journal of Foundations of Computer Science10.1142/S012905412250007133:05(411-427)Online publication date: 24-Mar-2022
https://doi.org/10.1142/S0129054122500071
Han YHe X(2012)More efficient parallel integer sortingProceedings of the 6th international Frontiers in Algorithmics, and Proceedings of the 8th international conference on Algorithmic Aspects in Information and Management10.1007/978-3-642-29700-7_26(279-290)Online publication date: 14-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29700-7_26
Han Y(2005)Parallel algorithms for linked list and beyondAlgorithms10.1007/3-540-52921-7_58(86-100)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-52921-7_58
Show More Cited By

Index Terms

An optimal linked list prefix algorithms on a local memory computer

Recommendations

An Optimal Linked List Prefix Algorithm on a Local Memory Computer

The author presents a deterministic parallel algorithm for the linked list prefix problem. It computes linked list prefixs 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.
Faster optimal parallel prefix sums and list ranking

We present a parallel algorithm for the prefix sums problem which runs in timeO( logn/log logn) usingnlog logn/lognprocessors (optimal speedup). This algorithm leads to a parallel list ranking algorithm which runs inO(logn) time usingn/lognprocessors (...
O(1)-time unsorting by prefix-reversals in a boustrophedon linked list
FUN'10: Proceedings of the 5th international conference on Fun with algorithms

Conventional wisdom suggests that O(k)-time is required to reverse a substring of length k. To reduce this time complexity, a simple and unorthodox data structure is introduced. A boustrophedon linked list is a doubly-linked list, except that each node ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CSC '89: Proceedings of the 17th conference on ACM Annual Computer Science Conference

February 1989

121 pages

ISBN:0897912993

DOI:10.1145/75427

Conference Chair:
Arthur M. Riehl
University of Louisville

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 February 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICMI05

Sponsor:

ACM

ICMI05: Seventh International Conference on Multimodal Interfaces 2005

February 21 - 23, 1989

Kentucky, Louisville

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
373
Total Downloads

Downloads (Last 12 months)59
Downloads (Last 6 weeks)7

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han YHe X(2022)More Efficient Parallel Integer SortingInternational Journal of Foundations of Computer Science10.1142/S012905412250007133:05(411-427)Online publication date: 24-Mar-2022
https://doi.org/10.1142/S0129054122500071
Han YHe X(2012)More efficient parallel integer sortingProceedings of the 6th international Frontiers in Algorithmics, and Proceedings of the 8th international conference on Algorithmic Aspects in Information and Management10.1007/978-3-642-29700-7_26(279-290)Online publication date: 14-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-29700-7_26
Han Y(2005)Parallel algorithms for linked list and beyondAlgorithms10.1007/3-540-52921-7_58(86-100)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-52921-7_58
Han YLiang WShen X(2001)Very fast parallel algorithms for approximate edge coloringDiscrete Applied Mathematics10.1016/S0166-218X(99)00190-0108:3(227-238)Online publication date: 15-Mar-2001
https://dl.acm.org/doi/10.1016/S0166-218X%2899%2900190-0
Han YShen XTarjan RWarnow T(1999)Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMsProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.314595(419-428)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.5555/314500.314595
Han Y(1989)Matching partition a linked list and its optimizationProceedings of the first annual ACM symposium on Parallel algorithms and architectures10.1145/72935.72961(246-253)Online publication date: 1-Mar-1989
https://dl.acm.org/doi/10.1145/72935.72961

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents