Time-work tradeoffs for parallel algorithms

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: Alok Aggarwal , Richard J. Anderson , Ming-Yang Kao, Parallel depth-first search in general directed graphs, SIAM Journal on Computing, v.19 n.2, p.397-409, April 1990 [doi>10.1137/0219025]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 4: Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
• 5: COHEN, E. 1992. Parallel algorithm with improved work for shortest-paths from multiple sources. Manuscript.
• 6: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 7: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 8: Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984 [doi>10.1145/800057.808687]
• 9: Hillel Gazit , Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Information Processing Letters, v.28 n.2, p.61-65, June 24, 1988 [doi>10.1016/0020-0190(88)90164-0]
• 10: Torben Hagerup, Towards optimal parallel bucket sorting, Information and Computation, v.75 n.1, p.39-51, October 1, 1987 [doi>10.1016/0890-5401(87)90062-9]
• 11: Philip N. Klein , S. Sairam, A parallel randomized approximation scheme for shortest paths, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.750-758, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129785]
• 12: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 13: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 14: Wolfgang J. Paul , Uzi Vishkin , Hubert Wagener, Parallel Dictionaries in 2-3 Trees, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.597-609, July 18-22, 1983
• 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.
• 16: SPENCER, T. 1989. Time-work tradeoffs for parallel algorithms. Tech. Report, 89-26. RPI, Troy, N.Y.
• 17: Thomas H. Spencer, Time-work tradeoffs for parallel graph algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.425-432, January 28-30, 1991, San Francisco, California, United States
• 18: Thomas H. Spencer, More time-work tradeoffs for parallel graph algorithms, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.81-93, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113387]
• 19: TARJAN, R. 1972. Depth first search and linear graph algorithms. SIAM J. Comput. 1, 215-225.
• 20: TARJAN, R., AND VISHKIN, U. 1985. An efficient parallel biconnectivity algorithm. SIAM J. Comput. 14, 862-874.
• 21: J. Ullman , M. Yannakakis, High-probability parallel transitive closure algorithms, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.200-209, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97686]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
PRAM, breadth first search, nearby lists, shortest path, topological sort, transitive closure