A no-busy-wait balanced tree parallel algorithmic paradigm

ABSTRACT

Suppose that a parallel algorithm can include any number of parallel threads. Each thread can proceed without ever having to busy wait to another thread. A thread can proceed till its termination, but no new threads can be formed. What kind of problems can such restrictive algorithms solve and still be competitive in the total number of operations they perform with the fastest serial algorithm for the same problem? Intrigued by this informal question, we considered one of the most elementary parallel algorithmic paradigms, that of balanced binary trees. The main contribution of this paper is a new balanced (not necessarily binary) tree no-busy-wait paradigm for parallel algorithms; applications of the basic paradigm to two problems are presented: building heaps, and executing parallel tree contraction (assuming a preparatory stage); the latter is known to be applicable to evaluating a family of general arithmetic expressions. For putting things in context, we also discuss our “PRAM-on-chip” vision (actually a small update to it), presented at SPAA98.

REFERENCES

• AG94: George S. Almasi , Allan Gottlieb, Highly parallel computing (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• ADKP89: K. Abrahamson , N. Dadoun , D. G. Kirkpatrick , T. Przytycka, A simple parallel tree contraction algorithm, Journal of Algorithms, v.10 n.2, p.287-302, June 1989 [doi>10.1016/0196-6774(89)90017-5]
• BSV93: Omer Berkman , Baruch Schieber , Uzi Vishkin, Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values, Journal of Algorithms, v.14 n.3, p.344-370, May 1993 [doi>10.1006/jagm.1993.1018 ]
• CV88a: R. Cole and U. Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica, 3:329-348, 1988.
• CLR90: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• CS99: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• DL99: William J. Dally , Steve Lacy, VLSI Architecture: Past, Present, and Future, Proceedings of the 20th Anniversary Conference on Advanced Research in VLSI, p.232, March 21-24, 1999
• DS99: Shlomit Dascal , Uzi Vishkin, Experiments with List Ranking for Explicit Multi-Threaded (XMT) Instruction Parallelism, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.43-59, July 19-21, 1999
• Gi93: P.B. Gibbons. Asynchronous P RAM algorithms. In Synthesis of Parallel Algorithms, J.H. Reif (editor), Morgan- Kaufmann, 1993, 957-997.
• HP96: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• KD88: S. R. Kosaraju , A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• MR89: G.L. Miller and J.I-I. Reif. Parallel tree contraction part 1: fundamentals. Advances in Computing Research, Vol 5, 47- 72, 1989.
• MR91: Gary L. Miller , John H. Reif, Parallel tree contraction part 2: further applications, SIAM Journal on Computing, v.20 n.6, p.1128-1147, Dec. 1991 [doi>10.1137/0220070]
• RMM: M. Reid-Miller, G.L. Miller and F. Modugno. List ranking and parallel tree contraction, J.H. Reif (editor), Morgan- Kaufmann, 1993, 115-194.
• VDBN98: Uzi Vishkin , Shlomit Dascal , Efraim Berkovich , Joseph Nuzman, Explicit multi-threading (XMT) bridging models for instruction parallelism (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.140-151, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277680]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

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: Trees

General Terms:
Algorithms, Design, Measurement, Performance, Theory