article

Free access

Time-work tradeoffs for parallel algorithms

Author:

Thomas H. SpencerAuthors Info & Claims

Journal of the ACM (JACM), Volume 44, Issue 5

Pages 742 - 778

https://doi.org/10.1145/265910.265923

Published: 01 September 1997 Publication History

PDF eReader

Abstract

Some parallel algorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes several algorithms with this property. These algorithms solve important problems on directed graphs, including breadth-first search, topological sort, strong connectivity, and and the single source shorest path problem. All of the algorithms run on the EREW PRAM model of parallel computer, except the algorithm for strong connectivity, which runs on the probabilistic EREW PRAM.

References

[1]

AGGARWAL, A., ANDERSON, R., AND KAO, M. 1990. Parallel depth-first search in directed graphs. SIAM J. Comput. 397-409.

Crossref

Google Scholar

[2]

AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass.

Crossref

Google Scholar

[3]

AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J.D. 1982. Data Structures and Algorithms. Addison- Wesley, Reading, Mass.

Crossref

Google Scholar

[4]

BRENT, R.P. 1974. The parallel evaluation of general arithmetic expressions. J. ACM 21, 2 (Apr.), 201-206.

Crossref

Google Scholar

[5]

COHEN, E. 1992. Parallel algorithm with improved work for shortest-paths from multiple sources. Manuscript.

Google Scholar

[6]

COPPERSMITH, D., AND WINOGRAD, S. 1987. Matrix multiplication via arithmetic progressions. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 1-6.

Crossref

Google Scholar

[7]

FREDMAN, M. L., AND TARJAN, R.E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3 (July), 596-615.

Crossref

Google Scholar

[8]

GALIL, Z. 1984. Optimal parallel algorithms for string matching. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington, D.C., Apr. 30-May 2) ACM, New York, pp. 240-248.

Crossref

Google Scholar

[9]

GAZIT, H., AND MILLER, G. L. 1988. An improved parallel algorithm that computes the BFS numbering of a directed graph. Inf. Proc. Lett. 61-65.

Crossref

Google Scholar

[10]

HAGERUP, T. 1987. Towards optimal parallel bucket sorting. Inf. Comput. 39-51.

Crossref

Google Scholar

[11]

KLEIN, P. N., AND SARIAM, S. 1992. A parallel randomized approximation scheme for shortest paths. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 750-758.

Crossref

Google Scholar

[12]

KNUTH, D. E. 1980. The Art of Computer Programming. Volume 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass.

Crossref

Google Scholar

[13]

KARP, R. M., AND RAMAcHANDRAN, V. 1990. A survey of parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science. J. van Leeuwen, ed. MIT Press, Cambridge, Mass.

Crossref

Google Scholar

[14]

PAUL, W., VISHKIN, U., AND WAGNER, H. 1983. Parallel dictionaries on 2-3 trees. In Automata, Languages and Programming. J. Diaz, ed. pp. 597-609.

Crossref

Google Scholar

[15]

REIF, J. 1985. An optimal parallel algorithm for integer sorting. In Proceedings of the 26th Annual Symposium on the Foundations of Computer Science. IEEE, New York, pp. 496-503.

Google Scholar

[16]

SPENCER, T. 1989. Time-work tradeoffs for parallel algorithms. Tech. Report, 89-26. RPI, Troy, N.Y.

Google Scholar

[17]

SPENCER, T. 1991a. Time-work tradeoffs for parallel graph algorithms. In Proceedings of the 2nd Annual Symposium on Discrete Algorithms. pp. 425-432.

Crossref

Google Scholar

[18]

SPENCER, T. 1991b. More time-work tradeoffs for parallel graph algorithms. In Proceedings of the 3rd Symposium on Parallel Algorithms and Architectures. pp. 81-93.

Crossref

Google Scholar

[19]

TARJAN, R. 1972. Depth first search and linear graph algorithms. SIAM J. Comput. 1, 215-225.

Google Scholar

[20]

TARJAN, R., AND VISHKIN, U. 1985. An efficient parallel biconnectivity algorithm. SIAM J. Comput. 14, 862-874.

Google Scholar

[21]

ULLMAN, J., AND YANNAKAKIS, M. 1990. High-probability parallel transitive closure algorithms. Symp. ParaL Algor. Arch. 200-209.

Crossref

Google Scholar

Cited By

View all

Cao NFineman JRussell KDhulipala LSun Y(2023)Efficient Construction of Directed Hopsets and Parallel Single-source Shortest Paths (Abstract)Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing10.1145/3597635.3598019(3-4)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3597635.3598019
Rozhoň VGrunau CHaeupler BZuzic GLi JLeonardi SGupta A(2022)Undirected (1+𝜀)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithmsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520074(478-487)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520074
Karczmarz ASankowski PMarx D(2021)A deterministic parallel APSP algorithm and its applicationsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458081(255-272)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458081
Show More Cited By

Index Terms

Time-work tradeoffs for parallel algorithms
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models
  2. Randomness, geometry and discrete structures

Recommendations

Space Efficient Linear Time Algorithms for BFS, DFS and Applications

Research on space efficient graph algorithms, particularly for st-connectivity, has a long history including the celebrated polynomial time, O(lg n) bits1 algorithm in undirected graphs by Reingold J. JACM. 55(4) (2008), and polynomial time, n/2ý(lgn)$n/...
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work
SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures

We study a (1+ε)-approximate single-source shortest paths (henceforth, (1+ε)-SSSP) in n-vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A randomized algorithm with polylogarithmic time and slightly super-linear work Õ(|E|•...
A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching

We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size m_h x m_w in a text array of size n_h x n_w in the concurrent-read-concurrent-write--parallel-random-access-machine (CRCW--PRAM) model. ...

Reviews

Reviewer: Linda Pagli

Problems on graphs—such as the directed spanning tree, breadth-first search, topological sort, cycle detection for directed graphs, strongly connected components, and single-source shortest paths with nonnegative edge lengths—are classic examples of problems for which no time-efficient parallel algorithm exists, although their sequential solutions are linear or almost linear. In this paper, Spencer observes that, if we do not search for the time-optimal algorithm but allow slower algorithms, we can obtain a better processor-time product (work) for the parallel algorithm. This basic idea makes it possible to define algorithms that exhibit time-work tradeoffs, which means that the slower the algorithms are allowed to be, the less work they do. The proposed parallel solutions for the above problems apply for a number of processors that vary in a given range. All of the algorithms are developed in the EREW PRAM model except for the one computing strong connectivity, which runs on the probabilistic EREW PRAM. This paper is of mainly theoretical interest.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 44, Issue 5

Sept. 1997

146 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/265910

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1997

Published in JACM Volume 44, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
1,052
Total Downloads

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

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cao NFineman JRussell KDhulipala LSun Y(2023)Efficient Construction of Directed Hopsets and Parallel Single-source Shortest Paths (Abstract)Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing10.1145/3597635.3598019(3-4)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3597635.3598019
Rozhoň VGrunau CHaeupler BZuzic GLi JLeonardi SGupta A(2022)Undirected (1+𝜀)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithmsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520074(478-487)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520074
Karczmarz ASankowski PMarx D(2021)A deterministic parallel APSP algorithm and its applicationsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458081(255-272)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458081
Elkin MMatar SAgrawal KAzar Y(2021)Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear WorkProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461809(198-207)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461809
Becker RForster SKarrenbauer ALenzen C(2021)Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming ModelsSIAM Journal on Computing10.1137/19M128695550:3(815-856)Online publication date: 4-May-2021
https://doi.org/10.1137/19M1286955
Blelloch GGu YShun JSun Y(2020)Parallelism in Randomized Incremental AlgorithmsJournal of the ACM10.1145/340281967:5(1-27)Online publication date: 19-Sep-2020
https://dl.acm.org/doi/10.1145/3402819
Andoni AStein CZhong PMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Parallel approximate undirected shortest paths via low hop emulatorsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384321(322-335)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384321
Cao NFineman JRussell KMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Efficient construction of directed hopsets and parallel approximate shortest pathsProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384270(336-349)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384270
Cao NFineman JRussell KScheideler CSpear M(2020)Improved Work Span Tradeoff for Single Source Reachability and Approximate Shortest PathsProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400222(511-513)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400222
Fineman J(2020)Nearly Work-Efficient Parallel Algorithm for Digraph ReachabilitySIAM Journal on Computing10.1137/18M1197850(STOC18-500-STOC18-539)Online publication date: 22-Oct-2020
https://doi.org/10.1137/18M1197850
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Space Efficient Linear Time Algorithms for BFS, DFS and Applications

Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work

A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations