Browse Prior Art Database

Optimal Parallel Generation of a Computation Tree Form Disclosure Number: IPCOM000128237D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 8 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

Ilan Bar-On: AUTHOR [+3]


Given a general arithmetic expression, we find a computation binary tree representation in 0(log n) time using n/log n processors.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 8


Optimal Parallel Generation of a Computation Tree Form

by Ilan Bar-On and Uzi Vishkin

Technical Report No, 90 Ultracomputer Note No. 61 October optimal parallel generation of a computation tree form.

Ilan Bar-On and Uzi Vishkin Department of Computer Science Courant Institute of Mathematical Sciences New York University


Given a general arithmetic expression, we find a computation binary tree representation in 0(log
n) time using n/log n processors.

1. Introduction. .

The model used in the present paper is a synchronous model of parallel computation in which all processors have access to a common memory. Simultaneous reading by several processors from the same location is allowed but not simultaneous writing. This model is sometimes called the concurrent-read exclusive-write parallel random-access-machine ( CREW PRAM ). This model is a member in a whole family of models for parallel computation. Sea Vishkin [V-83b] for a recent survey of results concerning this family. We present two algorithms:

1. For the problem of generating a tree form of a general arithmetic expression. 2. For matching pairs of parentheses in a given sequence. Both algorithms are of depth 0(1og n) using n/Log n processors for input of n characters. Such a result can be alternatively stated as depth of 0(n/p) for p < n/log n processors. Our algorithms have "optimal speed-up" (or are"optimal" ) in the following sense : The depth is of the order of the worst case running time of the fastest known sequential algorithm over the number of processors. We refer the reader to the following papers for some optimal parallel. algorithms in respective problems: [SV-81] for finding the maximum, merging And sorting, [AKS-83] for sorting, [CLC-82] and CV-811 for computing connected components of a graph and [TC-82] and [TV-83] for computing biconnected conponents of a graph. Dekel and Sahni [DS-83] present parallel algorithms for generating the postf3.x and tree form of an arithmetic expression. In their introduction they give a comprehensive discussion justifying the importance of the second problem. We mention only one of their arguments and refer the reader to their paper for the .others . All parallel algorithms for evaluating arithmetic expressions work on their tree form. See, for instance, [Br-74] and [Wi-75] . The Dekel-Sahni algorithm runs in time 0(log2n) using n processors (But in order to achieve 0(Iog n) time they use n2/log n processors). Thus, our algorithm is substantially faster using less processors. They adapted the known sequential algorithm to run in parallel. Like Reif [R-82], they emulate the stack in parallel. In contrast to this, we introduce a new "parallel oriented" algorithm. Both its design and time analysis are simpler if the parallel point of view is adopted. Dekel and Sahni find the postfix foam. Then, they use it to derive the tree form. We could not find sufficient signi...