Optimal parallel generation of a computation tree form

ABSTRACT

Given a general arithmetic expression, we find a computation binary tree representation in O(log n) time using n/log n processors on a concurrent-read, exclusive-write, parallel random-access machine. A new algorithm is introduced for this purpose. Unlike previous serial and parallel solutions, it is not based on using a stack.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• 2: 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]
• 3: Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982 [doi>10.1145/358628.358650]
• 4: Eliezer Dekel , Sartaj Sahni, Parallel Generation of Postfix and Tree Forms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.300-317, July 1983 [doi>10.1145/2166.357211]
• 5: ECKSTEIN, D.M. Simultaneous memory access. TR-79-6, Computer Science Dept., Iowa State Univ., Ames, 1979.
• 6: 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]
• 7: KNUTH, D.E. A history of writing compilers. Comput. Aurora. (1962), 6-19.
• 8: 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
• 9: REIF, J. Parallel time O(log n) acceptance of deterministic CFLs. In Proceedings 23rd Symposium on Foundations of Computer Science, (1982), 290-296.
• 10: SHILOACH, Y., AND VISHKIN, U. Finding the maximum, merging and sorting in parallel computation model. J. Algorithms 2, i (1981), 88-102.
• 11: TARJAN, R. E., AND VISHKIN, U. An efficient parallel biconnectivity algorithm." TR-69, Dept. of Computer Science, Courant Inst., New York Univ., 1983. To appear in SIAM J. Comput.
• 12: Tslr~, ~. H., AND CHIN, F. Y. Efficient parallel algorithms for a class of graph theoretic problems. Dept. of Computing Science, Univ. of Alberta, Edmonton, Alberta, Canada, 1982.
• 13: VISHKIN, U. An optimal parallel connectivity algorithm. Discrete Appl. Math. 9 (1984), 197- 207.
• 14: VISHKIN, U. Implementation of simultaneous memory address access in models that forbid it. J. Algorithm 4, I (1983), 45-50.
• 15: VISHKIN, U. Synchronous parallel computation--a survey. TR-71, Dept. of Computer Science, Courant Inst., New York Univ., 1983.
• 16: VISHKIN, U. An optimal parellel algorithm for selection. TR-106, Dept. of Computer Science, Courant Inst., New York Univ., 1983.
• 17: Uzi Vishkin, Randomized speed-ups in parallel computation, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.230-239, December 1984 [doi>10.1145/800057.808686]
• 18: VISHKIN, U. On efficient parallel strong orientation. TR-109, Dept. of Computer Science, Courant Inst., New York Univ., 1984. To appear in Inf. Process. Lett.
• 19: Uzi Vishkin, Optimal Parallel Pattern Matching in Strings (Extended Summary), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.497-508, July 15-19, 1985
• 20: S. Winograd, On the Parallel Evaluation of Certain Arithmetic Expressions, Journal of the ACM (JACM), v.22 n.4, p.477-492, Oct. 1975 [doi>10.1145/321906.321911]
• 21: James C. Wyllie, The Complexity of Parallel Computations, Cornell University, Ithaca, NY, 1979

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Performance, Theory