PDF Download

[Link]
14 January 2026
Total Citations: 78
Total Downloads: 1016
.
.
Latest updates: hps://[Link]/doi/10.1145/73007.73036

.
.
Published: 01 February 1989
.
.
.
ARTICLE

.
Citation in BibTeX format
Highly parallelizable problems

.
.
STOC89: 21st Annual ACM Symposium
on the Theory of Computing
OMER BERKMAN, Tel Aviv University, Tel Aviv-Yafo, Tel Aviv District, Israel May 14 - 17, 1989
.
Washington, Seattle, USA
ZVI GALIL*, Tel Aviv University, Tel Aviv-Yafo, Tel Aviv District, Israel

.
.
Conference Sponsors:
.
BARUCH M SCHIEBER, Tel Aviv University, Tel Aviv-Yafo, Tel Aviv District, Israel SIGACT
.
UZI VISHKIN, IBM Research, Yorktown Heights, NY, United States
.
UZI VISHKIN, Tel Aviv University, Tel Aviv-Yafo, Tel Aviv District, Israel
.
.
.
Open Access Support provided by:
.
Tel Aviv University
.
IBM Research
.
STOC '89: Proceedings of the twenty-first annual ACM symposium on eory of computing (February 1989)
hps://[Link]/10.1145/73007.73036
ISBN: 0897913078
.
 HIGHLY PARALLELIZABLE PROBLEMS
(Extended Abstract)

Omer Berkman ‘14 Dany Breslauer I,2 Zvi Galil I,2

Baruch Schieber 3 Uzi Vishkin ‘j415

Summary of Results. We establish that 1. Introduction

several problems are highly parallelizable. For each
of these problems, we design an optimal 0 (loglogn ) It is commonly agreed that the class NC
time parallel algorithm on the Common CRCW contains exactly all the problems that are
PRAM model which is the weakest among the amenable to parallel computation. It
CRCW PRAM models. These problems include: corresponds to the class P of the problems with
0 all nearest smaller values, feasible sequential solution. But establishing
l preprocessing for answering range maxima
that a problem is in NC does not really prove
queries,
l several problems in Computational Geometry, that the problem has a good parallel algorithm.
l string matching. (This is even more so than the fact that a prob-
Until recently, such algorithms were known lem is in P does not mean that it has an
only for finding the maximum and merging. efficient sequential algorithm.) Even being in
A new lower bound technique is presented NC’ is not enough because the 0 (logn ) time
showing that some of the new 0 (loglogn ) upper solution might use many processors.
bounds cannot be improved even when non optimal Optimal parallel algorithms are those with
algorithms are used. The technique extends
a linear time-processor product and linear
Ramsey-like lower bound argumentation due to auf
der Heide and Wigderson [MW-851. Its most interest- space. They correspond to
linear time and
ing applications are for Computational Geometry space sequential algorithms. We call a problem
problems for which no previous lower bounds are highly parallelizable if it can be solved by an
known. optimal parallel algorithm of time 0 (loglogn ).
We restrict attention to the CRCW PRAM
1. Department of Computer Science, Sackler Faculty of
Exact Sciences, Tel Aviv University, Tel Aviv, Israel model, because, in general, a sublogarithmic
69978. time requires the concurrent write model (see
2. Department of Computer Science, Columbia University, [CDR-861). We use the weakest Common
New York, NY 10027. The research of these authors was
CRCW PRAM model, in which the only con-
supported in part by NSF grants CCR-8605353 and
CCR-88-14977. current writes allowed are of the value one.
3. IBM Research Division, Thomas J. Watson Research There are several known highly paralleliz-
Center, P.O. Box 218, Yorktown Heights, NY 10598
4. Institute for Advanced Computer Studies, University of able problems for which there is a constant-
Maryland, College Park, Md 20742. time optimal algorithm. They include: (1) OR
5. The research of this author was supported by NSF and AND functions, (2) maximum finding for
grant CCR-86-15337 and ONR grant N00014-85-K-0046 at
“small integers” [FRW-881, (Small integers are
the Department of Computer Science, Courant Institute,
New York University. integers in the range [I, . . . , nc 1, for some
Permission to copy without fee all or part of this material is granted constant c .) (3) finding whether n integers
provided that the copies are not made or distributed for direct drawn from the domain [l...Ad], are pairwise
commercial advantage, the ACM copyright notice and the title of
the publication and its date appear, and notice is given that copying distinct given a memory of size h/l [FMW-871,
is by permission of the Association for Computing Machinery. To and (4) logjz -coloring of a cycle [CV-SG].
copy otherwise, or to republish, requires a fee and/or specific
permission.
@ 1989 ACM O-89791 -307-8/89/0005/0309 $1.50
309
 Until recently only two other highly paral- [BSV-881.
lelizable problems were known: (general) max- Using the algorithm for ANSV, as well as
imum finding and merging of isorted arrays. In some new geometric observations, we show that
both cases, Valiant [Va-751 fi:rst described an the following three problems in Computational
0 (loglogn ) algorithm in thie parallel com- Geometry are highly parallelizable. The input
parison model. His algorithms were later imple- to these three problems consists of a polygon
mented as 0 (loglogn ) time optimal algorithms P=(w(),q, . * . ,Q -I>, where (w; ,wi +I)+ is an
by Shiloach and Vishkin [SV-811 for [Link] edge of P , for i = 0 ,..., n -1. We assume that
finding (on a CRCW PRAM) and by Kruskal each vertex u is given by its x and y coordi-
[Kr-831 for merging (on a CREW PRAM). nates, denoted X(u) and Y (w ), respectively.
Note that Beame and Hastad [BHa-871 We assume that the vertices are given in
showed that the problem of computing the par- counter clockwise order.
ity of n bits requires it(logn /loglogn ) time on 1. The triangulation problem for monotone
the CRCW PRAM model with any polynomial polygons. In this problem the sequence of points
number of processors. Thus, this simple prob- in P consists of a monotone non-decreasing
lem is not highly parallelizable, and it is quite subsequence (with respect to the x axis) fol-
surprising that any problem is! lowed by a monotone non-increasing’ subse-
The contribution of this paper is showing quence. We seek to augment P by n -3 diago-
that other problems that have more elaborate nals that divide the interior of P into n -2 tri-
structure are highly parallelizable. The first angles. The highly-parallel algorithm for this
problem is new. It is called the All Nearest problem is given in [BSV-881.
Smaller Values problem, or ANSV and is 2. The convex-hull problem for monotone
defined as follows. polygons. P is given in the same way as in the
The All Nearest Smaller Values [ANSV) prob- triangulation problem above. We wish to find
lem. Given an array A =(a l,a 2, . . * , a, ) of which of the vertices of P belong to the perim-
elements from a totally ordered domain. For eter of the smallest convex polygon containing
each ai, 1 <z’ 5 n , find the nearest element to all n points. The highly-parallel algorithm for
its left and the nearest element to its right, this problem is omitted.
that are less than a;, if such elements exist. 3. The all nearest neighbors (ANN) problem for
That is, for each 15 i <n , find the maximal convex polygons. P is convex and we wish to
15 j <i , and the minimal i <k In such that find for each vertex vi of P its nearest neigh-
aj <ai and ak <ai. We say that aj is the left bor. That is, find a vertex vj, j #i , 1 sj <n ,
match and ak is the right match of ai . whose (Euclidean) distance from Vi is minimal.
The highly-parallel algorithm for this problem
We argue that the ANSV problem is fun-
is given in [ScV-881.
damental. First, it generalizes two elementary
problems: merging and finding the maximum. No previous 0 (loglogn ) time optimal
Second, it has several applications which are parallel algorithm for any of these Computa-
given below. tional Geometry problems is known to us.
[Go-87a], [Go-87b] and [Go-87~1, respectively
To show that the .ANSV problem is highly
give an optimal logarithmic time algorithm for
parallelizable we first show that the problem of
the triangulation problem, the convex-hull
prefix maxima finding, an easy extension of problem and the ANN problem. These algo-
maximum finding, is highly parallelizable. rithms use the weaker CREW PRAM model.
The prefix maxima problem. Given an array Parallel algorithms for several problems in com-
A =(aI,aS, * . . ,a, ) of elements from a totally putational geometry which also use the CREW
ordered domain. For each it l<i <n , find the PRAM model are given in [ACGOY-881 and
maximum among a r, * * * ,a; .
t The indices are taken modulo n
The highly-parallel algorithm for the
prefix maxima problem is given in [SC-871 and
310
[AG-861. problem of string matching is defined as fol-
Using the algorithm for ANSV we also lows. Given a text of length n and a pattern
show that the following two problems are of length m, find all the occurrences of the pat-
highly parallelizable: tern in the text. Optimal 0 (logm ) time paral-
(i) Reconstructing a binary tree from its inorder lel algorithms for string matching were obtained
and either preorder or postorder traversals. by Galil [Ga-851 for a fixed size alphabet and by
Sequential algorithms for this problem were Vishkin [Vi-851 for a general alphabet. We
considered recently in [BLSZ-871 and (CYL-881. design an optimal 0 (loglogm ) time parallel
The highly-parallel algorithm for this problem string matching algorithm for a general alpha-
is given in [BSV-88). bet. This algorithm also uses the ANSV algo-
(ii) Matching of a legal sequence of left and rithm as a subroutine.
right parentheses, when the level of nesting of We prove that each of the ANSV problem,
each of the parenthesis is given. Previous paral- the prefix maxima problem, preprocessing stage
lel algorithms for this problem are given in for the range maxima queries problem, and the
[DS-831 and [BV-851. The highly-parallel algo- three Computational Geometry problems need
rithm for this problem is also given in [BSV-881. fi(loglogn ) time using 0 (n log’ rt ) processors,
Recently, [KLP-881 applied our ANSV for any constant c . The proof technique for
algorithm to obtain an optimal parallel algo- the lower bound for the ANN problem is new.
rithm for forest matching. We assume a “too efficient” algorithm for the
problem being considered (in our case, the ANN
The range maxima queries problem is
problem). We then derive an algorithm for a
defined as follows. Given an array
problem outside Computational Geometry (in
A=(a1,a2, . * 1 ,a,) of n numbers preprocess
our case, merging) that contradicts a known
the array, so that for any interval
lower bound. This mapping of algorithm to
iai j % t-17 . ..,ej ], the maximum number over the
algorithm is done using Ramsey-like arguments.
interval can be found in constant time using a
(A technical part of this mapping uses a lemma
single processor. We know to perform such
from Meyer auf der Heide and Wigderson
preprocessing in 0 (loglogn ) time and
[MW-851 that was proved using Ramsey-like
12/loglogn processors. The description of this
arguments.) This gives an interesting and
preprocessing is omitted. [GBT-841 observed
rather unique application of Ramsey-like lower
that computing the maximum over any interval
bounds, All problems known to us for which
can be reduced to answering a lowest common
Ramsey-like lower bounds have been applied
ancestor (LCA) query in a Cartesian tree data
before, turn out to also have alternative lower
structure (due to [Vu-SO]) and solved the range
bounds in other models of parallel computation,
maxima problem serially in linear time. Our
such as Valiant’s comparison model. For our
preprocessing algorithm combines this serial
computational geometry problems, however,
approach with a preprocessing algorithm of
only the Ramsey-like approach was shown to be
[AS-871 and the prefix maxima algorithm.
useful, so far, The lower bounds for the other
Interestingly, [Ya-821 and [AS-871 showed that
problems are simpler. They are derived by
retrieval of information on each interval relative
reducing either merging or finding the max-
to any semi-group operation (in contrast to the
imum to them.
specific maximum operation) needs non-
constant time if only linear amount of work is
invested in the preprocessing stage. Finally, Some preliminary intuition. In many
note that an algorithm for this problem was logarithmic time algorithms on arrays, the com-
needed in [RV-$81. Other applications of the putation is guided by a complete binary tree
algorithm are given in (GBT-841. whose leaves correspond to the elements of the
input array. See, e.g., the prefix sums algorithm
Perhaps the most surprising result is that
of [LF-801. The computation in most of our
string matching is highly parallelizable. The
doubly logarithmic algorithms is guided by a
311
 balanced doubly logarithmic height tree defined parallel) algorithms are those optimal algo-
as follows. (See also Figure 1.) rithms whose running time is constant (respec-
tively, extremely slow growing function, such as
inverse-Ackermann, of the problem size). They
developed almost fully-parallel algorithmic tech-
niques for the CRCW PRAM. It turns out that
all their algorithms become fully-parallel if the
following assumption about the model of com-
putation is made: a very small number (log* of
the problem size) of processors can write simul-
taneously into different bits of the same regis-
ter. Of more specific relevance to the present
Fig. 1. The doubly logarithmic tree.
paper is a fully-parallel and almost fully-parallel
algorithms for the parentheses matching prob-
Let the size of the problem at hand be n . The lem that is considered here.
leaves of the tree correspond to the n inputs of
the problem. Each inter:nal node of heighi; one 2. The parallel algorithm for the All
has two children. Each internal node of height Nearest Smaller Values (ANSV) problem
h >1 has 22h-2 children. Observe that the In this section we describe an algorithm
number of leaves in the rooted subtree of any for solving the ANSV problem in 0 (loglogn )
internal node of height h >1 is 22h-’ (that is, time using n /loglogn processors. In order to
the square of the number of its children). Note appreciate the ANSV problem and gain some
that the height of the tree in loglogn +l. As an intuition we note that the ANSV problem is at
example, consider the doubly logarithmic time least as hard as the problem of finding the max-
algorithm for finding the maximum [V:~75]. imum and show that the same holds for the
This algorithm can be viewed as computing the merging problem.
maximum among the ‘descendant leave:: . for
Reduction from merging to ANSV: Let
each internal node in the tree, from bottom up
A =(a1,a2, * * . ,a,) and B=(b,,b,. + . ,b,)
level by level. The doubly logarithmic prefix
be the lists we wish to merge. Denote
maxima algorithm can be viewed as a b&tom
C=(al,. . . ,a,, b n,. f., b 1). Solve the ANSV
-9 : up computation in the doubly logarithmic tree
. problem with respect to C. Now, if bj is the
and ‘theh a top down one, level by level, similar
right match of ai then the location of ai in the
to the computation guided by the corrplete
binary tree in the prefiilr sums algorithm [LF- merged list is i + j . Similarly, we find the loca-
tion of each of the bk ‘s.
801.
We describe first an algorithm that takes
The rest of the paper is oiganized as f?l-
In Section 2 .wc: describe the [Link]- 0 (logn ) time using n /logn processors on a
lows.
CREW PRAM and discuss later how to extend
parallel algorithm for the ANSV problem. In
it into 0 (loglogn ) time using n /loglogn pro-
Section 3 we give the lower bound for the ANN
Finally, in Section 4 the. highly- cessors on a Common CRCW PRAM.
problem.
parallel string matching :algorithm is given. For simplicity assume that n is a power of
2. We build a complete binary tree with n
The interested reader may find fuller
leaves each corresponding to an element of the
representations in [BSV-881 (for Section 2),
input array A . First, we find for each internal
[ScV-881 (for Section 3), and [BG-881 (for Sec-
node of the tree the minimum value of its des-
tion 4).
cendant leaves. Second, for each element ai we
want to find its left and right matches.
Postscript. Berkman and Vishkin [BeV-891 con- The basic search procedure: Suppose some pro-
sidered the notion of fully-parallel algorithms. cessor is allocated to an element ai . The pro-
Fully-parallel (respectively, almost fully-
312
cessor finds the left match of ai by climbing up pairs of subarrays of A for each of our merging
the tree until it reaches a node such that the problems. For each i, 1 5 i 2 n /logn , there
value of its left brother is smaller than ai . are two pairs: a right pair and a left pair. Let
Then it proceeds down the tree aiming at the us first describe and handle the right pair of i,
rightmost leaf whose value is smaller than ai. Cases where the assumptions of Lemma 2.1 do
not hold are easy. So, let k be as in Lemma 2.1.
Note that the basic search procedure
The first subarray of such pair will span to the
implies an 0 (logn ) time algorithm using n
right of ab (i) until 1 (k ) (subarray X in Figure
processors for our problem. Next we show how
to reduce the number of processors to n /logn . 2). The second subarray of the right pair will
span to the left of a, fi) until r (k ) (subarray Y
in Figure 2). The important observations are
The optimal logarithmic time algorithm:
as follows.
Step I: Partition A into n /logn groups of
We define the first subsequence to be the
logn elements each and solve the ANSV prob-
subsequence of the first subarray that consists
lem sequentially with respect to each group.
of all the elements of this subarray that are yet
Step 2: Find the minimum value, prefix-minima unmatched to the right. Similarly, we define the
and suffix-minima within each group. second subsequence to be the subsequence of
Let b (i ) denote the index of the minimal the second subarray that consists of all the ele-
element in group i . ments of this subarray that are yet unmatched
Step 5: Solve the ANSV problem with respect to the left.
to each of the ab (i)‘s, using the above basic Observation 1: The values of the elements in
search procedure. the first subsequence are monotonically increas-
ing from left to right. The values of the ele-
In Steps 4.1 and 4.2 below, we complete
ments in the second subsequence are monotoni-
finding left and right matches for all elements.
cally increasing from right to left.
For this we need a few definitions and observa-
Observation Z?: The right matches of all ele-
tions. Let r (; ) be the index of the right match
ments in the first subsequence lie in the second
of ab ci ), and 1 (i ) be the index of its left match.
subsequence. The left matches of all elements
Lemma 2.1. Suppose r (; ) exists and the group in the second subsequence (with the exception
of r (; ) is larger than i +l. Then, there exists a of a,(i)) lie in the first subsequence.
group k > i, such that I(k) belongs to group -
Observations l-2 together with Lemma 2.1
i and r (k ) belongs to the group of r (; ).
lead to Step 4.1 for finding right matches for
Moreover, group k is unique. (See Figure 2.)
the first subsequence and left matches for the
second subsequence.
Step 4.1. Merg, the first subsequence with the
second subsequence, and derive the right match
of all the elements in the first subsequence and
the left match of all the elements in the second
subsequence.
Detailed characterization of a left pair,
Fig. 2 respective observations and how they lead to
Step 4.2 for merging such pair is similar and
therefore omitted.
The general idea behind Steps 4.1 and 4.2 Theorem 2.1: Each element that has not been
is to reduce the problem of finding these matched to the left or to the right by the end
remaining matches into many (actually of Step 3 will be matched by either the merges
2n /logn ) merging problems that will be solved of Step 4.1 or the merges of Step 4.2,
simultaneously in parallel. We characterize the

313
The optimal doubly logarithmic time .algo- For the lower bound Iproof we consider
rithm: only convex polygons P of the following form:
P = (u 1, . . . , 21, ,wn +1, . . . , 212n ), where all
We partition A into n /(loglogn )2 groups
the 5 -coordinates are dist:inct integers and
of (loglogn )2 elements each, and solve the
Y(q) = 44 ) W,+i) =g 1 for
ANSV problem with respect to each of these
i-l,...,?%. Note that since the vertices of
groups in 0 (loglogn ) time an’d loglogn proces-
P are given in counter clockwise order we have
sors (total of n /loglogn. processors) using the
above optimal parallel algorithm. Then, we XbJi-1) < XC% > and -W,,+i-1) > Xh+ih
for i = 2,...,n . We claim that the nearest
solve the ANSV problem for an array of
neighbor of a vertex w of P, is a vertex
n /(loglogn )” ” distinguished” elements, [Link] of
2 +w, such that 1 X(w)-X(Z) 1 is
them is the minimum in its group. Finally, we
minimal.
extend it to a solution of the ANSV problem
for A in a similar way to Step 4 of the :tbove In Theorem 3.2 we relate the strong
algorithm. CRCW PRAM model to the parallel com-
parison model, defined in [V&75].
The interesting part deals with solving the
ANSV problem for the distinguished elements. Theorem 3.2: If there exists an algorithm for
This part is guided by a, balanced doubly loga- the ANN problem which runs in T (n ) time
rithmic tree defined in the Introduction. We using m processors on a strong CRCW PRAM
substitute the search procedure by the follow- then there exists an algorithm for merging two
ing. For each internal node 1, we consider only ordered lists of size n each which runs in T (n )
m(1) - the minimal element among the leaves time and performs at most m 22T tn ) simultane-
of the tree rooted at 1’; we find a left (and ous comparisons in a comparison model.
right) match for m (I) among the elements of Before proving the theorem we show how
the (subtrees rooted a.t) siblings of I. This is the lower bound follows. Suppose, in contradic-
done independently in parallel for all nodes of tion, that there exists an algorithm for the
the tree. The left match is found in two ANN problem which runs in o (loglogn ) time
rounds. In the first round we identify the using n log’ n processors, for some constant c .
sibling whose tree includes the left matc:l. In By Theorem 3.1, there exists an algorithm for
the second round we find the left match itself. merging two ordered lists of size n each which
Finding the right match is similar. Suppressing runs in o (loglogn ) time and performs at most
most implementation details, we note that n log c+2n simultaneous comparisons in a com-
parallel merging (similar to the above algo- parison model. This contradicts the correspond-
rithm) will suffice to finding all left and right ing lower bound of [BHo-851 and [HH-821 for
matches. (For details see [BSV-881.) merging in a parallel comparison model. This
concludes the proof of Theorem 3.1.
3. A lower bound for the All Nearest The proof of Theorem 3.2 is based on a
Neighbors (ANN) problem lemma from [MW-851. Suppose we are given a
In this section we prove: strong CRCW PRAM [Link] for the ANN
Theorem 3.1: Any parallel algorithm for the problem. Using Claim 3.1 below we show how
ANN problem for convex polygons with 2n ver- to construct from this algorithm a comparison
tices on a CRCW PRAM which uses model algorithm for merging. Informally,
0 (72 log’ 12) processors, for some constant c , Claim 3.1 states that there exists an infinite set
requires a(loglogn ) time. of integers S with the following property.
Consider the set of all input polygons with ver-
The model of parallel computation u,jed in
tices whose z coordinates are taken from S.
this section is the stronger Priority CRCW
(Later, we refer to this set as the set of inputs
PRAM with unlimited computation power,
taken from S .) For this set of inputs and for
referred as a strong CRCW PRAM. For the
each processor pi, 1 5 i 5 m , the indices of
exact definition see [MW-851.
314
the vertices that became known to pi at time Lemma 3.1 [MW-851: Suppose that at time t,
t +1 depend on the order of the (ZZ coordinates for instances from I (S’ ,lK’ ,IIt ), processor pi
of the) vertices known at time t . (A vertex is knows only variables from Kt. Then, there are
known to a processor pi if it is in its local jb - . . , L E -L, m } and an infinite subset
memory.) S’ ’ s 4.9’ ) such that after step t , for
Let us formalize Claim 3.1. For a given instances from I(S’ ’ ,K’ ,lIt ), processor pi
input polygon we make the following knows only variables from Kit U Kj”, . That is,
definitions. the set Kt +’ is the same for all instances from
(1) For 1 5; 5 m, 05 t 5 T(n), let Ki’ be I(S’ ’ p? ,rI’ ).
the set consisting of all indices of the vertices We construct St +r from S, by applying
known to processor pi at time t . Denote Lemma 3.1 repeatedly, one time for each possi-
Kt =(Ki,. . .,Kh)’ ble partial order. Finally, STcn) is the set S
(2) For 0 5 t 5 T (n ), let II’ be a partial needed to establish Claim 3.1. q
order on the indices {l,...,Zn }. IIt is the clo-
We return to Theorem 3.2 and show how
sure of the union of m +1 (consistent) partial
to construct a corresponding algorithm for
orders rO,nrt, . . . , n;, defined as follows. no is
merging two lists of size n each in a com-
the partial order induced by the counter clock-
parison model. This merging algorithm will run
wise direction of the input vertices. That is,
in T (n ) time and perform at most m 22T(“)
1<,02<,o 1.. <non and
simultaneous comparisons. Consider an input
2n <n0 2n -1 <n, . . . <n0 n +l. Each of the instance for the merging algorithm. We index
partial orders Tit is a total order on the indices the elements from the first list in order from 1
in Kit induced by the order of the (z coordi- to n and the elements from the second list in
nates of the) vertices with indices in Kit. reverse order from 2n down to n +l. In this
Claim 9.1: There exists an infinite set of manner we have that the partial order induced
integers S with the following property. Con- on the index set {l,... ,2n } by the order of the
sider the set of inputs taken from S. For this input lists is exactly 70. The corresponding
set of inputs the m-tuple Kt+l (i.e., the merging algorithm will follow the ANN algo-
indices of the vertices known by each processor rithm for inputs from S. Specifically, the state
at time t +1) depends on the partial order IIt . of the merging algorithm at time t is defined,
as in the ANN algorithm, by an m tuple lKt
Sketch of the proof: We construct the set S
and a partial order IIt . Recall that Kt
inductively. For 0 5 t 5 T (n ), define S, to
represents m index sets and 1Tt represents the
be an infinite set of integers such that for the
partial order on {I,..., 272 } induced by the order
set of inputs taken from St and for each pro-
of the elements with indices in the sets Kit,
cessor pi, 1 5 a’ < m , the indices of the ver-
15; sm. I’It defines K ‘+’ in the ANN
tices known to pi at time s +1 5 t depend on
algorithm. Kt +’ of the merging algorithm is
the order of the (Z coordinates of the) vertices the same. At time t +1 we compute the respec-
known at time s . Clearly, So is the set of all tive partial order IIt +l. Specifically, for each
integers, Given the set S, we show that there 1 5 i 5 m we perform ) E(it 1 x ) Kj, 1 com-
exists an infinite subset St+, E S, such that
parisons. Since 1 K) 1 5 2t, for each
for the set of inputs taken from S, +i, K1 +r
1 5 i 5 m , we can compute the partial order
depends on IIt . To construct S, +r we need the
I? +’ in constant time by performing at most
following definition. For an infinite set of
m 22t 5 m 2’*ln 1 simultaneous comparisons.
integers S’ define I(S ’ ,Kt ,IIt ) to be the set
for which To complete the proof of Theorem 3.2 we
of all inputs taken from S’
prove the validity of this merging algorithm.
X(vi) < X(vj) for all 1 5 i,j < 2n such
Specifically, we show that for each input to the
that i <,t 3’ . [MW-851 p rove the following
merging algorithm, IITcn 1 must be a total
Lemma.
order. The proof is by contradiction and is

315
omitted. length @ (9 ,P ).
We remark that in a similar manner we Let us first describe the algorithm for the
can prove an fi(loglog;R) time lower bound for case when the pattern w is not periodic. Later,
merging on a strong CRC’W PRAM with we describe how to extend it to the case where
0 (n log” n ) processors, for any constant c. the pattern is periodic. In case the pattern is
(This gives an additional application of Lemma not periodic one can show that the pattern can
3.1 not mentioned in [MIV-851.) not occur at both positions i and j of the text,
if ] j-i ] <m /2. This implies that the pat-
4. The parallel string matching algorithm tern can occur in the text at most 2n /m times.
In this section we dIescribe a parallel algo- Thus, assuming we could eliminate many possi-
rithm for finding all the occurrences of a pat- ble occurrences and have only 0 (n /m ) possi-
tern of length m in a text of length n over an ble occurrences left, we can use the 0 (1) algo-
arbitrary alphabet. The algorithm rurs in rithm described above to verify them using only
0 (loglogm ) time using n /loglogm processors n processors. Below, we describe how this
on a Common CRCW IPRAM. The algo::ithm elimination is done optimally in 0 (loglogm )
works in two stages, in the first we proceza the time.
pattern and compute some information which is An important idea in our algorithm is a
used later to analyze the text. method suggested in [Vi-851, which enables us
Suppose that we ha,ve mn processors on a to eliminate many possible occurrences in 0 (1)
CRCW PRAM, then we can solve the string time. One computes some information about
matching problem in 0 (1) time as follows. the pattern which is called
First, mark all possible occurrences of the pat- WITNESS (1, . . . , m ), defined below, and
tern in the text as “match”. To each pcssible uses it for the analysis of the text.
occurrence assign m processors. Each such Let 21 be a prefix of the pattern 20, of
processor compares one symbol of the pattern length <m /2. Since the pattern is not
with the corresponding symbol of the text. If a periodic, there is an index k such that
mismatch is encountered, it marks the PATTERN(k )#PATTERN (k - 1 v I ). We
appropriate occurrence as “unmatch”. call this k a witness to the mismatch of w and
Assuming we can eliminate some of the VW, and define WTNESS( I v I +l)=k .
possible occurrences and have only 1 left, we Having computed the WITNESS array in
can use the method described above to get an the pattern analysis, Vishkin [Vi-851 suggests
0 (1) time parallel algorithm with Zm proces- the following method, which he calls a duel, to
sors. The only problem is that one can have eliminate close possible occurrences of the pat-
many occurrences of the pattern in the text, tern. Suppose that we suspect that the pattern
much more than the n ,lm needed for optimal- may start at position i and j of the text where
ity. To overcome this. problem, we u,s.e the O<j-i <m /2. Let r = kVITN.!ZSS (j -4 +l).
notion of the period suggested in [Ga-851 and Since PA TTERN (r )#PA TTERN (r -j +i ), at
also used in [Vi-851. most one of them can be equal to
A string u is called a period of a string w TEXT (r si -1). (S ee Figure 3.) This implies
if w is a prefix of u k for some positive integer that we can eliminate at least one of the two
k or equivalently if UJ is a prefix of uw . We possible occurrences in constant time.
call the shortest period of a string w the period
of w. We call a string periodic if its length is
at least twice its period length. If w occurs in
positions p and q of some string, and
IQ-P I<bJ I th en 20 has a period of length
] q-p ] . If w has periods of length p .and q
andp+qI b 1 then w has also a period of

316
 duels as described above using the available r
processors. We are left with at most a single
I T possible occurrence in each block of size r .
I To achieve optimality we first partition
I each of the n /r blocks into small blocks of size
loglogr . To each one of the r /loglogr small
Fig. 3. X#Y and therefore blocks we assign a processor and make dueIs
we cannot have T =X and T =Y . between pairs using a sequential algorithm till
left with at most one possible occurrence in
each small block. Then, we proceed with the
Having many such duels in pairs, the algo- 0 (loglogr ) algorithm having at most
rithm of [Vi-851 eliminates enough possible r /loglogr possible occurrences to start with.
occurrences of the pattern in the text in After the elimination we are left with at
0 (logm) time and verifies the rest using the most n /r possible occurrences, to verify each
0 (I) time algorithm described above. We of these occurrences, we use the 0 (1) time
manage to reduce the time of the elimination to algorithm described above, with (n /r ) m <2n
0 (loglogm ) time using the observation that processors, which can be simulated in
duels “work like” maximum. Specifically, con- 0 (loglogr > time with n /loglogr processors.
sider a block of text of length T = [m /2 1.
In case the pattern is periodic let the pat-
From the above discussion we have that at
tern w =U Ic 21, where 2) is a proper prefix (pos-
most one occurrence of the pattern might start
sible empty) of u , and k >l. Let ] u ] =p .
in this block, however, it can start anywhere
The algorithm has two stages, We divide the
within that block, Now, suppose that we have
text into n /m overlapping blocks of length
r 2 processors. We assign a processor to each
2m each, and consider each one separately. In
pair and perform a duel. Since in every pair at
the first stage we find all the occurrences of u2
least one loses, at the end we are left with at
in the text. Since u 2 is not periodic we can use
most one possible occurrence in each block.
the algorithm described above to find all these
Below, we describe how to do the same elimina-
occurrences in 0 (loglogp ) time and n /loglogp
tion in 0 (loglogm) time using m /loglogm
processors, and hence, also in 0 (loglogm ) time
processors based on having
and n /loglogm processors. In the second stage
WITNESS(2, . . . , r ), computed in the pat-
we find all the occurrences of the pattern. The
tern analysis stage. The algorithm works simi-
pattern occurs wherever we have k consecutive
larly to the maximum finding algorithm of
occurrences of u followed by an occurrence of
[SV-811.
w . Thus, it seems that to verify an occurrence
First, we describe an algorithm which runs of the pattern we need to count consecutive
in 0 (loglogr )=0 (loglogm ) time using r pro- occurrences of the period u . However, general
cessors and then we show how to reduce the counting cannot be done in 0 (loglogm ) time,
number of processors by a factor of loglogm . as counting is at Ieast as hard as computing
Partition the text into blocks of length r . We parity. Below, we show how this counting can
have n /r such blocks. In each block mark all be done using the ANSV algorithm.
positions as possible occurrences. Partition
We caI1 an occurrence of u 2 at position i
each block into groups of size r v and assign
a final occurrence if there is no occurrence of
r1j2 processors to each group. Continue recur-
u2 at position i +p . For an occurrence of u 2
sively in each group. The recursion bottoms out define its right match to be the nearest final
with one processor per block of size one, where
occurrence to its right. The main observation is
nothing is done. When done, we are left with
that if u 2 occurs at position i then its right
at most one possible occurrence in each block of for some
match must be at position i +lp
size r ij2 thus at most r 1/2 possible occurrences integer 120. This implies that the number of
altogeth:r. Then in 0 (1) time we make all
317
consecutive occurrences of u starting at posi- [BLSZ-871 H.A. Burgdorff, S. Lajodia, F.N.
tion i is 1 t2. It is not difficult to see that we Springsteel and Y. Zalcstein, ?[Link]
can compute the right match for all occurrences methods for the reconstruction of trees
of u 2 in 0 (loglogm ) time and na /loglogm. pro- from their traversals”, BIT, 27 (1987), pp.
cessors, using the ANSV algorithm. (Recall 134-140.
that ‘we partitioned the text into blocks of [BSV-881 0. Berkman, B. Schieber and U. Vishkin,
length 0 (m) each and that we consider each ” Some doubly logarithmic parallel algo-
block separately.) Also, for each final occurrence rithms based on finding all nearest smaller
we can verify whether ‘V occurs after it in values”, UMIACS-TR-88-79, University of
0 (loglogm ) time and n /loglogm processors. Maryland Inst. for Advanced Comp. Stu-
Note that z, occurs after each non-final dies (1988).
occurrence since v is a prefix of u . Using this
[BV-851 I. Bar-On and U. Vishkin, “Optimal paral-
information we can decide for each occurrence
lel generation of a computation tree
of u2 whether it is the beginning of an
form”, ACM Trans. on Prog. Lang. and
occurrence of the pattern.
Systems, 7 (1985), pp. 348-357.
The processing of the pa,ttern is similar
[BeV-891 0. Berkman and U. Vishkin, “Fully and
but technically more involved. Its description is
almost fully parallel algorithmic tech-
given in [BG-881.
niques”, manuscript, January 1989.
[CDR-861 S.A. Cook, C. Dwork and R. Reischuck,
“Upper and lower time bounds for parallel
REFERENCES random access machines without simul-
taneous writes”, SIAM J. on Computing,
[ACGOY-881 A. Aggarwal, B. Chazelle, L. Guibas,
15 (1986)) pp, 87-97.
C. O’Dunlaing and C. Yap, “Parallel com-
[CV-861 R. Cole and U. Vishkin, “Deterministic
putational geometry”, Algorithmica, 3
coin tossing with applications to optimal
(1988), pp. 293-327.
parallel list ranking”, Injc’rmation and
[AG-861 M.J. At allah and M.T. Goodrich, Control, 70 (1986), pp. 32-53.
“Efficient parallel solutions to geometric
[CYL-ss] G.H. Chen, M.S. Yu and L.T. Liu, “Two
problems,,, J. of Parallel and Distributed
algorithms for constructing a binary tree
Comp., 3 (1986), pp. 492-507.
from its traversals”, Information Process-
[AS-871 N. Alon and B. Schieber, “Optimal ing Letters, 28 (1988) 297-299.
preprocessing for answering on-line pro-
[DS-831 E. Dekel, and S. Sahni, “Parallel genera-
duct queries”, TR 71/87, The Moise and
tion of postfix and tree forms”, ACM
Frida Eskenasy Institute of Computer Sci-
Trans. on Prog. Lang. and Systems,
ence, Tel Aviv University (1987).
5(1983), pp. 300-317.
[BG-881 D. Breslauer and Z. Galil, “An optimal
[FMW-87lF.E. Fich, F. Meyer auf der Heide and A.
0 (loglogn ) time parallel string matching
Wigderson, “Lower bounds for parallel
algorithm”, manuscript, 1988.
random access machines with unbounded
[BHa-871 P. Beame and .I. Hastad, “Optimal bounds shared memory”, Advances in Computer
for decision problems on the CRCW Research, 4 (1987)) 1-15.
PRAM”, Pro c. 19th ACM Symp. on
[FRW-881 F.E. Fich, P. Ragde and A. Wigderson,
Theory of Computing (1987), pp. 83-93. concurrent-write
‘Relations between
[BHo-851 A. Borodin and J.E. Hopcroft, “Routing, models of parallel computation”, SIAM J.
merging, and sorting on parallel models of on Computing, 17 (1988), pp. 606-627.
comparison”, J. of Compl. and System Sci.,
[Ga-851 Z. Galil, “Optimal parallel algorithms for
30 (1985) pp. 130-145.
string matching”, Information and Con-
trol, 67 (1985), pp. 144-157.

318
[Go-87a] M.T. Goodrich, “Triangulating a polygon [SCV-881 B. Schieber and U. Vishkin, “Finding all
in parallel”, preprint, 1987. nearest neighbors for convex polygons in
[Go-87b] M.T. Goodrich, “Finding the convex hull parallel: a new lower bound technique and
of a sorted point set in parallel”, Informa- a matching algorithm”, UMIACS-TR-88-
tion hoc. Letters, 26 (1987), pp. 173-179. 82, University of Maryland Inst. for
Advanced Comp. Studies (1988). To
[Go-87c] M.T. Goodrich, “Efficient parallel tech-
appear in Discrete Applied Math.
niques for computational geometry”,
Ph.D. thesis, Dept. of Computer Science, [Va-751 L.G. Valiant, “Parallelism in comparison
Purdue Univ., 1987. models”, SIAM J. on Computing, 4 (1975))
pp. 348-355.
[GBT-841 H.N. G ab ow, J.L. Bentley and R.E. Tar-
[Vi-851 U. Vishkin “Optimal parallel pattern
jan, “Scaling and related techniques for
geometry problems”, Proc. 16th ACM matching in strings”, Information and
Symp. on Theory oj Computing (1984), pp. Control, 67 (1985), pp. 91-113.
135-143. {Vu-SO] J. Vuillemin, “A unified look at data
[HH-8‘21 R. Haggkvist and P. Hell, “Sorting and structures”, Comm. oj the ACM 23 (1980))
merging in rounds”, SIAM J. on Alg. and pp. 229-239.
Disc. Methods, 3 (1982), pp. 465-473. [Ya-821 A.C. Yao, “Space-time tradeoff for answer-
[Kr-831 G.P. Kruskal, “Searching, merging, and ing range queries”, Proc. 14th ACM Symp.
sorting in parallel computation”, IEEE on Theory of Computing (1982)) pp. 128-
Trans. on Computers, C-32 (1983)) pp. 136.
942-946.
[KLP-881 Z .M. Kedem, G.M. Landau and K.V.
Palem, “Optimal parallel algorithms for
matching problems”, TR 410, Dept. of
Computer Science, Courant Inst., NYU
(1988).
[LF-801 R.E. Ladner and M.J. Fischer, “Parallel
prefix computation”, J. oj the ACM 27’4
(1980), 831-838.
[MW-851 F. Meyer auf der Heide and A. Wigderson,
“The complexity of parallel sorting”,
Proc. 26th Symp. on Foundations of Com-
peter Science (1985), pp. 532-540.
[RV-881 V.L. R amachandran and U. Vishkin,
“Efficient parallel triconnectivity in loga-
rithmic parallel time” Proc. AWOC 88,
Lecture Notes in Computer Science 319,
Springer-Verlag (1988)) pp. 33-42.
[SC-871 B. Schieber, “Design and analysis of some
parallel algorithms”, Ph.D. thesis, Dept. of
Computer Science, Tel Aviv Univ., 1987.
[SV-Sl] Y. Shiloach and U. Vishkin, “Finding the
maximum, merging and sorting in a paral-
lel computation model’, J. of Algorithms,
2 (1981)) pp. 88-102.

319