research-article

Deterministic parallel list ranking

Authors:

Richard J. Anderson,

Gary L. MillerAuthors Info & Claims

Algorithmica, Volume 6, Issue 1-6

Pages 859 - 868

https://doi.org/10.1007/BF01759076

Published: 01 June 1991 Publication History

Abstract

In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs inO(logn) time on an EREW PRAM withn/logn processors. The algorithm matches the performance of the Cole-Vishkin [CV3] algorithm but is simple and has reasonable constant factors.

References

[1]

Cole R. and Vishkin U. Deterministic coin tossing with applications to optimal parallel list ranking Information and Computation 1986 70 32-53

[2]

Cole R. and Vishkin U. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time Algorithmica 1988 3 329-346

[3]

Cole R. and Vishkin U. Approximate parallel scheduling, part I: The basic technique with applications to optimal parallel list ranking on logarithmic time SIAM Journal on Computing 1988 17 128-142

[4]

Cole R. and Vishkin U. Faster optimal parallel prefix sums and list ranking Information and Computation 1989 81 334-352

[5]

H. Gazit, G. L. Miller, and S. H. Teng. Optimal tree contraction in the EREW model. Extended abstract, 1986.

[6]

A. V. Goldberg, S. A. Plotkin, and G. E. Shannon. Parallel symmetry-breaking in sparse graphs. InProceedings of the 19th ACM Symposium on Theory of Computation, pages 315–324, 1987.

[7]

Y. Han. Designing Fast and Efficient Parallel Algorithms. Ph.D. thesis, Duke University, 1987.

[8]

S. R. Kosaraju and A. L. Delcher. Optimal parallel evaluation of tree-structured computations by raking. InAegean Workshop on Computing, pages 101–110, 1988.

[9]

C. Kruskal, L., Rudolf, and M. Snir. The power of parallel prefix computation. InInternational Conference on Parallel Processing, pages 180–185, 1985.

[10]

G. L. Miller and J. H. Reif. Parallel tree contraction and its applications. In26th Symposium on Foundations of Computer Science, pages 478–489, 1985.

[11]

Rajasekaran S. and Reif J. Optimal and sublogarithmic time randomized parallel sorting algorithms SIAM Journal on Computing 1989 18 594-607

[12]

Tarjan R. E. and Vishkin U. An efficient parallel biconnectivity algorithm SIAM Journal on Computing 1985 14 862-874

[13]

U. Vishkin. Randomized speed-ups in parallel computation. InProceedings of the 16th ACM Symposium on Theory of Computation, pages 230–239, 1984.

[14]

R. A. Wagner and Y. Han. Parallel algorithms for bucket sorting and the data dependent prefix problem. InInternational Conference on Parallel Processing, pages 924–930, 1986.

[15]

J. C. Wyllie. The Complexity of Parallel Computation. Ph.D. thesis, Department of Computer Science, Cornell University, 1979.

Cited By

Geissmann BGianinazzi L(2021)Parallel Minimum Cuts in Near-linear Work and Low DepthACM Transactions on Parallel Computing10.1145/34608908:2(1-20)Online publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1145/3460890
Geissmann BGianinazzi LScheideler CFineman J(2018)Parallel Minimum Cuts in Near-linear Work and Low DepthProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures10.1145/3210377.3210393(1-11)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3210377.3210393
Blelloch GMaggs B(2010)Parallel algorithmsAlgorithms and theory of computation handbook10.5555/1882723.1882748(25-25)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882748
Show More Cited By

Recommendations

On the computational power of WECPAR

Reconfigurable models were shown to be very powerful in solving many problems faster than non-reconfigurable models. WECPAR $$W(M,N,k)$$ W ( M , N , k ) is an $$M\times N$$ M N reconfigurable model that has point-to-point reconfigurable interconnection with $$k$$ k wires between neighboring processors. ...
Tight Bounds on Parallel List Marking

The list marking problem involves marking the nodes of an -node linked list stored in the memory of a (p,n)-PRAM, when only the position of the head of the list is initially known, while the remaining list nodes are stored in arbitrary memory locations. ...
List-ranking on interconnection networks

The list-ranking problem is considered for parallel computers which communicate through an interconnection network. Each PU holds k nodes of a set of linked lists. A novel randomized algorithm gives a considerable improvement over earlier ones: for a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 6, Issue 1-6

Jun 1991

883 pages

ISSN:0178-4617

Issue’s Table of Contents

© Springer-Verlag New York Inc. 1991.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 June 1991

Revision received: 10 August 1989

Received: 15 September 1988

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Geissmann BGianinazzi L(2021)Parallel Minimum Cuts in Near-linear Work and Low DepthACM Transactions on Parallel Computing10.1145/34608908:2(1-20)Online publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1145/3460890
Geissmann BGianinazzi LScheideler CFineman J(2018)Parallel Minimum Cuts in Near-linear Work and Low DepthProceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures10.1145/3210377.3210393(1-11)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3210377.3210393
Blelloch GMaggs B(2010)Parallel algorithmsAlgorithms and theory of computation handbook10.5555/1882723.1882748(25-25)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882748
Han YSaxena SShen X(2010)An efficient parallel algorithm for building the separating treeJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.01.00770:6(625-629)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.jpdc.2010.01.007
Cormode GMuthukrishnan S(2007)The string edit distance matching problem with movesACM Transactions on Algorithms10.1145/1186810.11868123:1(1-19)Online publication date: 2-Feb-2007
https://dl.acm.org/doi/10.1145/1186810.1186812
Sibeyn J(2003)List-ranking on interconnection networksInformation and Computation10.1016/S0890-5401(02)00029-9181:2(75-87)Online publication date: 15-Mar-2003
https://dl.acm.org/doi/10.1016/S0890-5401%2802%2900029-9
Nakano KOlariu SZomaya A(2003)A time-optimal solution for the path cover problem on cographsTheoretical Computer Science10.1016/S0304-3975(02)00068-3290:3(1541-1556)Online publication date: 3-Jan-2003
https://dl.acm.org/doi/10.1016/S0304-3975%2802%2900068-3
Calamoneri TOlariu SPetreschi R(2000)A Simple Parallel Algorithm to Draw Cubic GraphsIEEE Transactions on Parallel and Distributed Systems10.1109/71.88864111:10(1009-1018)Online publication date: 1-Oct-2000
https://dl.acm.org/doi/10.1109/71.888641
Lange KNiedermeier R(2000)Data Independence of Read, Write, and Control Structures in PRAM ComputationsJournal of Computer and System Sciences10.1006/jcss.1999.166560:1(109-144)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.1006/jcss.1999.1665
Dahlhaus E(2000)Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph RecognitionJournal of Algorithms10.1006/jagm.2000.109036:2(205-240)Online publication date: 1-Aug-2000
https://dl.acm.org/doi/10.1006/jagm.2000.1090
Show More Cited By

View Options

View options

Get Access

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 Issue’s Table of Contents