PDF Download

[Link]
23 December 2025
Total Citations: 36
Total Downloads: 719
.
.
Latest updates: hps://[Link]/doi/10.1145/800057.808687

.
.
Published: 01 December 1984
.
.
.
ARTICLE

.
Citation in BibTeX format
Optimal parallel algorithms for string matching

.
.
Conference Sponsors:
SIGACT
ZVI GALIL*
.
.
.
STOC '84: Proceedings of the sixteenth annual ACM symposium on eory of computing (December 1984)
hps://[Link]/10.1145/800057.808687
ISBN: 0897911334
.
 OPTIMAL P A R A L L E L A L G O R I T H M S FOR STRING MATCHING

Zvi G a l i l *
Tel-Aviv University
Columbia University

Abstract: Let W R A M [PRAM] be a p a r a l l e l of the p r o c e s s o r s can s i m u l t a n e o u s l y read

computer with p p r o c e s s o r s (RAM's) w h i c h from the same m e m o r y location. W e some-
share a c o m m o n m e m o r y and are a l l o w e d sim- times a l l o w s i m u l t a n e o u s w r i t i n g in the
u l t a n e o u s reads and w r i t e s [only s i m u l t a n - w e a k e s t sense: any subset of proces-
eous reads]. The only type of s i m u l t a n - sors can w r i t e the v a l u e 0 into the same
eous w r i t e s a l l o w e d is a s i m u l t a n e o u s AND: m e m o r y l o c a t i o n (i.e., turn off a switch).
several p r o c e s s o r s may w r i t e 0 simul- W e d e n o t e by W R A M [PRAM] the m o d e l that
t a n e o u s l y into the same m e m o r y cell. Let allows [does not allow] s i m u l t a n e o u s writ-
t be the time b o u n d of the computer. We ing. W e also c o n s i d e r (but only briefly)
d e s i g n b e l o w families of p a r a l l e l algori- o t h e r m o d e l s of p a r a l l e l computation. We
thms that solve the string m a t c h i n g pro- a c t u a l l y d e s i g n a family of a l g o r i t h m s be-
b l e m w i t h inputs of size n (n is the cause we have a parameter p. The p e r f o r -
sum of lengths of the p a t t e r n and the text) m a n c e of the family is m e a s u r e d in terms
and h a v e the f o l l o w i n g p e r f o r m a n c e in terms of thmee p a r a m e t e r s : p - - t h e n u m b e r of pro-
of p, t and n: cessors, t--the time, and n - - t h e size of
the p r o b l e m instance.
i. For WRAM: pt = o(n) for
It is w e l l k n o w n that every p a r a l l e l
for p ~ n/log n.
algorithm with p p r o c e s s o r s and time t
2. For PRAM: pt = O(n) for can be easily c o n v e r t e d to a s e q u e n t i a l
P ~ n/log2n. a l g o r i t h m of time pt. H e n c e the analog
of l i n e a r - t i m e a l g o r i t h m i n s e q u e n t i a l com-
3. For W R A M : t = c o n s t a n t for
p u t a t i o n is a family of p a r a l l e l a l g o r i t h m s
i~¢
p = n and any ¢ > 0. w i t h pt = O(n). W e t h e r e f o r e call such
a l g o r i t h m s optimal. Surprisingly, while
4. For W R A M : t = o(log n / l o g log n)
there are m a n y p r o b l e m s for w h i c h linear-
for p = n.
time a l g o r i t h m s are known, there are very
S i m i l a r families are also o b t a i n e d for the few p r o b l e m s for w h i c h o p t i m a l p a r a l l e l
p r o b l e m of finding all initial p a l i n d r o m e s a l g o r i t h m s are k n o w n for a w i d e range of
of a g i v e n string. p. So few, that w e list them here.
E v e r y a s s o c i a t i v e f u n c t i o n of n var-
i. Introductio n . iables can be c o m p u t e d by a P R A M in pt =
O(n) for p ~ n/log n. (Use a b i n a r y tree,
W e d e s i g n p a r a l l e l a l g o r i t h m s in the
each leaf "treats" n/p inputs.) For a
f o l l o w i n g model: p s y c h r o n i z e d p r o c e s s o r s
c e r t a i n s u b s e t of these functions includ-
(RAM's) share a c o m m o n m e m o r y . A n y subset
ing the n v a r i a b l e OR (AND), D(log n)
* R e s e a r c h s u p p o r t e d by N a t i o n a l S c i e n c e time is n e e d e d on the P R A M [CD], so pt =
F o u n d a t i o n G r a n t MCS-8303139, O(n) is u n a t t a i n a b l e for p >> n / l o g n.
C o n s e q u e n t l y , the only q u e s t i o n left is
w i t h h o w few p r o c e s s o r s can we c o m p u t e
t h e s e f u n c t i o n s in c o n s t a n t time on a WRAM.
Permission to copy without fee all or part of this material is granted
provided that the copies are not made or distributed for direct The answer depends on the s p e c i f i c function.
commercial advantage, the ACM copyright notice and the title of the The n v a r i a b l e OR (or AND) f u n c t i o n can
publication and its date appear, and notice is given that copying is by be c o m p u t e d by W R A M in pt = n for p ~ n
permission of the Association for Computing Machinery. To copy (i.e., in time = 1 w i t h n processors).
otherwise, or to republish, requires a fee and/or specific permission. The n v a r i a b l e M A X I M U M f u n c t i o n can be
c o m p u t e d in pt = O(n) for p ~ n / l o g log n
© 1984 ACM 0 - 8 9 7 9 1 - 1 3 3 - 4 / 8 4 / 0 0 4 / 0 2 4 0 $00.75 and in c o n s t a n t time w i t h n I÷~ p r o c e s s o r s

240
 (for every ¢ > 0) [V], [SV]. and p a r a l l e l time in the lowest level.
Optimal p a r a l l e l algorithms are k n o w n
for m e r g i n g two sorted arrays (for p 4. As in the a l g o r i t h m in [GS], it
is p o s s i b l e to w r i t e a very short p r o g r a m
n/log n on a PRAM); m e r g i n g can be done in
c o n s t a n t time even by a P R A M w i t h n l+C (for each processor), but a longer explan-
ation is needed m a i n l y b e c a u s e the algo-
p r o c e s s o r s [SV] and in log log n w i t h n
r i t h m uses implicitly p r o p e r t i e s of perio-
p r o c e s s o r s [V], [BM]. Recently, optimal
dicities several times.
p a r a l l e l algorithms w e r e d e s i g n e d for the
p r o b l e m of c o n v e r t i n g an e x p r e s s i o n to its 5. The algorithms use w h a t seems to
p a r s e tree [BV] and for S e l e c t i o n [Vi]. be a novel m e t h o d of c o m m u n i c a t i o n among
W h a t is c o m m o n to all these p r o b l e m s the various processors, as w i l l be indi-
e x c e p t S e l e c t i o n is that for each one of cated below.
them there is a trivial (sequential) lin-
String matchinq is the following pro-
e a r - t i m e algorithm. In this p a p e r w e de-
blem. The input consists of two strings,
sign optimal p a r a l l e l a l g o r i t h m s for string
x (the pattern) and y (the text), over
matching. The l i n e a r - t i m e a l g o r i t h m for
a g i v e n a l p h a b e t of a fixed size. The-out-
string m a t c h i n g is by now very w e l l under-
put is a B o o l e a n array indicating all the
stood, but at one time, it was q u i t e a ma-
o c c u r r e n c e s of x in y.
jor discovery. U n l i k e the case of c o m p u t i n g
In Section 2 we p r o v e several sim-
n v a r i a b l e functions (where it is trivial)
ple facts on p e r i o d i c i t i e s of strings used
and m e r g i n g (where it is q u i t e simple) de-
by the algorithm. In S e c t i o n 3 we sketch
signing optimal p a r a l l e l algorithms for
the m a i n a l g o r i t h m w h i c h is non optimal
string m a t c h i n g was not immediate.
(p = 3n t = log n) and only d e a l s w i t h
As for the p r o b l e m s m e n t i o n e d above,
a special case (ly I = 21x ~ = 2n). In
w e d e s i g n e d other p a r a l l e l algorithms that
S e c t i o n 4 we c o m p l e t e the details of the
p e r f o r m string m a t c h i n g on W R A M in c o n s t a n t
i+¢ algorithm. In Section 5 we show h o w the
time w i t h only n processors. As in the four families of p a r a l l e l algorithms men-
cases above the time is p r o p o r t i o n a l to tioned above are d e r i v e d from the main
I/¢. If only n p r o c e s s o r s are a v a i l a b l e algorithm. In S e c t i o n 6 we b r i e f l y dis-
the time needed is O(log n/log log n). cuss other models of p a r a l l e l c o m p u t a t i o n
The families of algorithms w e d e s i g n and the p r o b l e m of finding all initial
h a v e several a p p e a l i n g features: p a l i n d r o m e s of a g i v e n string.
i. They are nqt d e r i v e d from any of
2. P e r i o d i c i t y in Strinqs.
the variants of the l i n e a r - t i m e s e q u e n t i a l
algorithms ([KMP], [BM]). The latter do A string u is a p e r i o d of a string
not s e e m to be p a r a l l e l i z a b l e , b e c a u s e w if w is a p r e f i x of u ~ for some k
they c o n s t r u c t s e q u e n t i a l l y tables w h i c h are or e q u i v a l e n t l y if w is a p r e f i x of uw.
u s e d sequentially. So, even giving the W e call the s h o r t e s t p e r i o d of a string
tables for free does not seem to h e l p much. w the p e r i o d of w. Thus a is the
Two k n o w n algorithms are p a r a l l e l i z a b l e p e r i o d of aaaaaaa w h i l e aa,aaa, etc are
b u t do not y i e l d optimal p a r a l l e l algori- also periods of w. W e say that w has
thms: the O(n log n) a l g o r i t h m in [KMR] p e r i o d size P if the length of the per-
y i e l d s tp = O(n log2n) and the p r o b a b i l i s - iod of w is P. If w is at least
tic l i n e a r - t i m e a l g o r i t h m in [KR] yields t w i c e longer than its p e r i o d we say that
a p r o b a b i l i s t i c family w i t h tp = O(n log n). w is periodic.
W e w i l l c o n s i d e r p r e f i x e s of the pat-
2. The a l g o r i t h m s w e d e s i g n are all
tern x of increasing length. A s s u m e we
d e r i v e d from one algorithm: it is an al-
consider a prefix u and then a p r e f i x
g o r i t h m for W R A M w i t h p = n and t = log n
v. In the case that u is p e r i o d i c we
for the case that the text is twice longer
w i l l say that the p e r i o d i c i t y continues
than the pattern.
in v if the p e r i o d of v is the same as
3. The algorithms m a k e use of pro- the p e r i o d of u (e.g. u = abcabcab,
p e r t i e s of p e r i o d i c i t i e s in strings d e r i v e d v = abcabcabcabcabca) and that the perio-
from the P e r i o d i c i t y L e m m a w h i c h states dicity terminates o t h e r w i s e (e.g. the same
that two d i f f e r e n t p e r i o d i c i t i e s c a n n o t co- u, v = abcabcabcd...).
exist long enough (if they do, then there W e w i l l n e e d some simple facts about
is a common refinement). S i m i l a r proper- periodicities.
ties w e r e used in a d i f f e r e n t way to d e s i g n
a l i n e a r - t i m e a l g o r i t h m for string m a t c h i n g F a c t 1 (The P e r i o d i c i t y Lemma)[LS] : If
w h i c h uses only c o n s t a n t (five) r e g i s t e r s w has two periods of size P and Q and
[GS]. Therefore, we h a v e h e r e an e x a m p l e lwl ~ P + Q, then w has a p e r i o d of size
for a r e l a t i o n s h i p b e t w e e n s e q u e n t i a l space gcd(P,Q).

241
 F o r a o n e l i n e p r o o f see [GS]. h a s 3n + 1 p r o c e s s o r s . Processor i is
In the r e s t of this s e c t i o n an o c c u r - responsible for z. and S W I T C H [ i ] .
l
r e n c e at j w i l l m e a n an o c c u r r e n c e at
Given a string u of l e n g t h L we
position j in a g i v e n f i x e d s t r i n g z.
s a y t h a t w e t e s t for u a t (position) i
(of z) if w e e x e c u t e A N D ( u I = z i , . . . , u ~
F a c t 2: If v o c c u r s at j and j + P,
'P ~ Ivl/2, t h e n (i[ v is p e r i o d i c w i t h a = zi+~_l). Such a test finds if u occurs
p e r i o d of l e n g t h P, and (2) v o c c u r s at
at i and t a k e s one u n i t of t i m e o n the
j + P, w h e r e P is t h e p e r i o d s i z e of v.
WRAM. The straight forward algorithm that
T h e f i r s t h a l f of F a c t 2 f o l l o w s f r o m the
2
a l t e r n a t i v e d e f i n i t i o n of period• T h e se- tests for x at all i's n e e d s n proces-
c o n d h a l f of F a c t 2 h o l d s s i n c e by F a c t 1 sors. (i)
P must divide P. Let x be the prefix of x of s i z e
In t h e r e s t of this s e c t i o n w e con-
2 i, a n d let x (i+l) = x ( i ) y (i). T h e algo-
s i d e r a p e r i o d i c s t r i n g v = U k u ', k > i, r i t h m c o n s i s t s of log n stages. After
u the p e r i o d of v, u' a p r o p e r p r e f i x of stage i S W I T C H [j] = 1 if and o n l y if
u, and lul = P. L e t L = ~p, L = [Ivl/Pl .•
x (i) o c c u r s at j.
T h e n e x t t w o facts f o l l o w f r o m a s i m p l e
W e n o w d e s c r i b e s t a g e i + i, w h i c h
c o u n t i n g of p e r i o d s :
takes a c o n s t a n t (at m o s t six) steps. The
t a s k of the s t a g e is to t e s t w h e t h e r e a c h
Fact 3: If v occurs at j and j + mP,
m ~ k, then uk+mu ' occurs at j. occurrence of x (i) is followed by an oc-
c u r r e n c e of y(i). In c a s e t h e a n s w e r is
Fact 4: v occurs at j, j + P and j + L negative the corresponding 1 in S W I T C H is
t u r n e d off.
iff u k + L u ' o c c u r s at j.
W e d i v i d e the a r r a y S W I T C H i n t o b l o c k s
F a c t 5: If v o c c u r s at j a n d j + 4, of s i z e 2 i-l. W e say t h a t p r o p e r t y i
~ Ivl - P, t h e n A is a m u l t i p l e of P. h o l d s if e a c h b l o c k has at m o s t o n e i. We
d i s t i n g u i s h b e t w e e n two c a s e s : t h e r e g u l a r
Proof: Otherwise ~ = mP + r, 0 < r < P, case, a n d the p e r i o d i c case.
T h e r e g u l a r c a s e is the o n e in w h i c h
a n d m < k. L e t w = u ( k - m ) u '. w is a
the f i r s t b l o c k of S W I T C H h a s o n l y o n e 1
s u f f i x of v, so it o c c u r s at j + mP. It
(at p o s i t i o n i). By i n d u c t i o n , the o t h e r
is a l s o a p r e f i x of v, so it o c c u r s at
b l o c k s m a y h a v e at m o s t two l's. In a
j + ~ = j + mP + r. B y F a c t 2, w has
b l o c k w i t h t w o l's, the 1 at t h e s m a l l e r
a p e r i o d of s i z e r in a d d i t i o n to a
p o s i t i o n is t u r n e d off. (This o c c u r r e n c e
period of size P. B y F a c t i, it h a s a
p e r i o d of s i z e g c d ( p , r ) < P w h i c h d i v i d e s of x (i) is n o t a beginning of an o c c u r r e n c e
P. Hence P cannot be the period size
of x (i+l).) As a result, property i
Of v. Q
W e c a l l an o c c u r r e n c e of v at j holds •
T h e r e are 2 i - 1 p r o c e s s o r s r e s p o n -
i m p o r t a n t if v does n o t o c c u r at j + P. sible for the block. H e n c e , in two s t e p s
t h e y c a n t e s t for y(i) at t h e a p p r o p r i a t e
F a c t 6: If t h e r e a r e two i m p o r t a n t o c c u r -
p o s i t i o n if t h e y k n e w w h i c h c o m p a r i s o n s
r e n c e s of v at r and s, r > s, t h e n
they o u g h t to p e r f o r m • We will explain
r - s > Ivl - P.
b e l o w h o w this is done. W e c a l l it a r e g u -
lar step.
Proof: Assume r - s i Ivl - P- By F a c t 5,
In t h e p e r i o d i c c a s e t h a t f o l l o w s a
r - s = mP. B y F a c t 4, u k + m u ' o c c u r s at r e g u l a r c a s e the f i r s t b l o c k h a s two l's;
r, a n d h e n c e v o c c u r s at r + P, a n d the the s e c o n d o f w h i c h a t p o s i t i o n p + i. It
o c c u r r e n c e at r cannot be important. 0
f o l l o w s f r o m F a c t 2 t h a t x (i) is p e r i o d i c
with period size P. In the p e r i o d i c c a s e
3. A sketch of t h e m a i n algorithm.
w e t e s t w h e t h e r the p e r i o d i c i t y of
The i n p u t is a s t r i n g z = x $ y of
x(i)i~ c o n t i n u e s in x (i+l). We do it in two
l e n g t h 3n + 1. x is the p a t t e r n , Ixl = n,
and y is the text, ly I = 2n. B o t h are s t e p s u s i n g x (i) as a y a r d s t i c k • If x (i+l)
o v e r a g i v e n a l p h a b e t of f i x e d s i z e w h i c h has t h e s a m e p e r i o d w e s i m i l a r l y f i n d a l l
d o e s n o t c o n t a i n $. T h e o u t p u t is a B o o - its o c c u r r e n c e s . Then we start stage i + 2
l e a n a r r a y of l e n g t h 3n + 1 c a l l e d SWITCH.
in the p e r i o d i c case. If x (i+l) does not
T h e f i n a l v a l u e of S W I T C H [ i ] is 1 iff an
have the same period we turn off (justifi ~
o c c u r r e n c e of x s t a r t s w i t h z.. The WRAM
l

242
ably) many l's in SWITCH. As a result, pro- differently. Since SWITCH(l) = i, the
perty i holds and we c o m p l e t e the stage p r o c e s s o r r e s p o n s i b l e for the second Ibb
w i t h a regular step. Each part in the dis- of stage i (the first of stage i+l)
cussion above makes some use of p r o p e r t i e s looks at its ibb. If it is n o n e m p t y it
of periodicities. contains P; i.e., x (i) is p e r i o d i c a l with
During the a l g o r i t h m the p r o c e s s o r s period size P. The p r o c e s s o r posts P on BB.
need to communicate. For g l o b a l c o m m u n i c a - D u r i n g the p e r i o d i c loop (boxes 5,6)
tion w e h a v e a b u l l e t i n board, B B, w h e r e the ibb's are not u p d a t e d and are not used.
some a n n o u n c e m e n t s are posted; e.g. if the BB w i l l c o n t a i n P and L ~ ~P, w h e r e
case is p e r i o d i c and the size of the period.
= [2i/pl. W h e n w e enter box 5 from box 1
Also, the p r o c e s s o r s r e s p o n s i b l e for a
b l o c k need to c o m m u n i c a t e in order to find E [2,3} (2 i-2 < P + 1 ~ 2i-I).
w h i c h c o m p a r i s o n s they ought to m a k e in a Updating L in the loop is easy: L ~ if
r e g u l a r step. For this p u r p o s e we h a v e
2L - P > 2 i+l then 2L - P else 2L.
local b u l l e t i n boards, ibb's. W e can use
an a d d i t i o n a l array to store the ibb's. L e t ~(i+l) be the p r e f i x of x of
A l t e r n a t i v e l y , each ibb can be stored at size 2 i + L (Ix(i+l) I = 2i+i ~ Ix ('i+l) <
the last element of its block. A t the end
of each stage one of every two c o n s e c u t i v e 2 i+l + P). In box 5 we test w h e t h e r the
ibb's dies and may transfer some informa-
p e r i o d i c i t y continues in ~(i+l) by using
tion to the s u r v i v i n g one b e f o r e it passes
(i) (i)
away. (See F i g u r e i. ) x as a yardstick. (Fact 4 v = x ,
k+L
j = i, ~(i+l) = u u'): the first pro-
4. The Details.
cessor tests w h e t h e r SWITCH(P+1) = 1
The flow chart of the a l g o r i t h m is and SWITCH(L+1) = i. Recall. that P and
g i v e n in F i g u r e 2. In this s e c t i o n we give L are posted. The first test is redund-
the details Of each one of the seven boxes ant w h e n we come from box i. Similarly,
in the flow chart. The first and last
in Box 6, we find the occurences of ~(i+l)
s t a g e are s l i g h t l y d i f f e r e n t and are dis-
cussed at the end of the section. as follows (Fact 4 v = x(i),x(i+l)= uk+~u ') :
W e enter box 1 after a regular step p r o c e s s o r pj that sees 1 at SWITCH(j)
in stage i. C o n s i d e r blocks numbers
checks w h e t h e r SWITCH(P+j) = 1 and
2j-I and 2j at the end of stage i. They
SWITCH(L+j) = I. If one of the tests fails
c o n t a i n at m o s t one i. The ibb of the
pj turns off the i.
first b l o c k dies at the end of the stage.
Recall that an o c c u r r e n c e of v = x (i)
The p r o c e s s o r r e s p o n s i b l e for the second
at j is called i m p o r t a n t if x (i) does
Ibb (number 2j.2 i-2) looks at the dying
not occur at j+P. Since SWITCH(l) = 1 and
ibb and if it is not empty, it tries to
one of SWITCH(P+1), SWITCH(L+1) is zero,
t r a n s f e r its contents to its ibb. Two l's
per b l o c k are d i s c o v e r e d w h e n its ibb is at least one of the occurrenees of x (i)
already nonempty. at p o s i t i o n s j ~ L + 1 - P is important.
B o x 1 deals w i t h the case j = i. If By Facts 5,6, either the o c c u r r e n c e at 1
two l's are d i s c o v e r e d in the (new) first is i m p o r t a n t or there is exactly one im-
b l o c k we are in the p e r i o d i c case, w h i c h p o r t a n t o c c u r r e n c e at some j 1 ~ j
is e x p l a i n e d below. Boxes 2, 3 deal w i t h L+i-P.
the case j > i. If two l's are d i s c o v e r e d W h e n we test if the p e r i o d i c i t y con-
the first is turned off by the p r o c e s s o r tinues, first, Pl checks SWITCH(P+1). If
r e s p o n s i b l e for the s u r v i v i n g Ibb. (It
it is zero, then the o c c u r r e n c e at 1 is
is the p r o c e s s o r that d i s c o v e r s the two
i m p o r t a n t and Pl posts 0 on BB. Other-
l's.)
To u n d e r s t a n d box 4, the regular w i s e it tests SWITCH(P+L). If it is i,
step, c o n s i d e r F i g u r e i. If the o c c u r r e n c e the p e r i o d i c i t y continues. Otherwise,
starts at Z4+l, then the ibb contains 4. each p r o c e s s o r pj tests (using SWITCH)
Processor j in the g r o u p that c o r r e s p o n d s w h e t h e r there is an important o c c u r r e n c e
to the b l o c k makes two comparisons : at j. The u n i q u e pj that succeeds posts
= Zk+4? for k e [j+2i,j+21+21-1}. If j-i on BB.
Next, each p r o c e s s o r Pr w i t h
one of the answers is n e g a t i v e it turns off
the 1 at S W I T C H (4+1). This is the only SWITCH(r) = 1 uses S W I T C H and the p o s t e d
p l a c e w h e r e the c o n c u r r e n t w r i t e is used. v a l u e of j-i to check w h e t h e r there is an
The test in box 1 is a c t u a l l y h a n d l e d
i m p o r t a n t o c c u r r e n c e of x (i) at r+j-l. If

243
t h e r e is no such an o c c u r r e n c e it turns off turns off the i. If the test succeeds
the 1 at SWITCH(r). This is j u s t i f i e d it checks w h e t h e r S W I T C H ( r + j - I + P ) = I. If
the test s u c c e e d s w e k n o w that x occurs
b e c a u s e ~(i+l) c a n n o t o c c u r at r, since
at r (since the tests imply that um+k+lu'
in ~(i+l) t h e r e is an i m p o r t a n t o c c u r r e n c e
occurs at j). If the test fails w e still
o f x (i) at j. A t this p o i n t p r o p e r t y i do not k n o w the answer. N o t e t h a t in this
h o l d s by F a c t 6.
case the o c c u r r e n c e at x (i)- - at r+j-i is
B e f o r e e x e c u t i n g the r e g u l a r step
i m p o r t a n t and by Fact 6 if we r e s t r i c t at-
(box 4) the Ibb's are restored. E a c h pro-
t e n t i o n to o c c u r r e n c e s at r's such that
c e s s o r Pr w i t h SWITCH(r) = 1 w r i t e s r-i in
the o c c u r r e n c e at r+j-I is important, then
its ibb. By C l a i m 2, no c o n f l i c t occurs. property i holds. So we a c t i v a t e the
To be a b l e to do it, each p r o c e s s o r k n o w s ibb's and use a r e g u l a r step to test whe-
in each s t a g e w h e r e is its ibb. This infor-
ther such o c c u r r e n c e s of x ~i)"
" extend to
m a t i o n can be e a s i l y p r e c o m p u t e d or u p d a t e d
o c c u r r e n c e s of x.
dynamically.
The first s t a g e is v e r y simple. Pro-
5. The Four Families.
c e s s o r pj tests w h e t h e r z.z = XlX 2 If
3 j+l
the test succeeds, pj turns on SWITCH(j) 5.1 U s i n g only n/loq n processors.
and m a k e s the j-th ibb for the s e c o n d stage The m a i n a l g o r i t h m can be i m p l e m e n t e d
p o i n t to the i. R e c a l l that the size of w i t h only n/log n p r o c e s s o r s using the four
the b l o c k s in the s e c o n d s t a g e is i. R U s s i a n s t r i c k [AHU] to p a c k log n symbols
W e now d i s c u s s the changes n e e d e d for into one number.
the last stage, b u t first w e n e e d to elabor- E a c h p r o c e s s o r is r e s p o n s i b l e for s
ate on the o t h e r stages. C o n s i d e r stage c o n s e c u t i v e symbols in z and in SWITCH,
w h e r e 8 = c log n and c d e p e n d s on the
f+l, and an o c c u r r e n c e of x (i) at j ~ n.
a l p h a b e t size: p r o c e s s o r Pr w i l l be
A s s u m e j+2 i+l > n+l, so X (i+l) c a n n o t o c c u r
responsible for z., SWITCH(j) j ¢ A
at j s i m p l y b e c a u s e it is too long, and 3 r
the $ does not m a t c h any symbol of x. In [(r-l)s+l,...,rs]. First, each Pr packs
c a s e the first m i s m a t c h from the left is
each s u b s t r i n g of z of length s that
the S the a l g o r i t h m w i l l not turn off the 1
starts w i t h zj, j ~ Ar, into a new symbol
at S W I T C H (j). (It is as though the $
and the f o l l o w i n g symbols always m a t c h the z''3 T h e n it c o m p a r e s each zj, j ¢ A r ,
s y m b o l s c o m p a r e d to them. As a result, a
w i t h z I and if they are equal it s e t s
1 in S W I T C H may s t a n d for an o v e r h a n g i n g
occurrence. SWITCH(j) = i. This has the effect of the
In the last stage, if p r o p e r t y i holds, first t = log s stages and takes O(s) =
or if the p e r i o d i c i t y t e r m i n a t e s (and as a O ( l o g n) time.
r e s u l t of i n c l u d i n g o v e r h a n g i n g o c c u r r e n c e s A s s u m e the n e x t ((t+l)-st) s t a g e is in
it m e a n s that it t e r m i n a t e s b e f o r e the S) the r e g u l a r case. The o t h e r stages are as
w e e x e c u t e a r e g u l a r step w i t h o u t any change. in the m a i n algorithm. The only differ-
The o n l y c h a n g e is in the case that the ence is that in each r e g u l a r step the pack-
p e r i o d i c i t y continues. W h i l e in the o t h e r ed symbols z~ are used.
stages it means t h a t the p e r i o d i c i t y con- If the ~ t + l ) - s t s t a g e is p e r i o d i c a l ,
then the p e r i o d size P < s/2, and we n e e d
t i n u e s to x(i+l),in the last s t a g e it con-
also to p a c k the bits in SWITCH. Each Pr
tinues only to the $. W e find o u r s e l f in
packs the s c o n s e c u t i v e s e g m e n t s of
this c a s e w h e n L + 2 i ~ n (]~(i+l)[ ~ixl).
S W I T C H s t a r t i n g w i t h each SWITCH(j) j ~ A .
r
W e call an o c c u r r e n c e of x (i) at j special
W h e n the p e r i o d i c i t y c o n t i n u e s and w e test
if j + 2 i ~ n and j + P + 2 i > n + 1 (if
for o c c u r r e n c e s of ~(i+l)'" w e can h a n d l e
the n e x t o c c u r r e n c e of x (i), at j+P is the all the l's in a p a c k e d symbol of S W I T C H
first o v e r h a n g i n g occurrence). As w i t h im- s i m u l t a n e o u s l y using some s i m p l e bit vec-
p o r t a n t o c c u r r e n c e s the u n i q u e pj t h a t finds tor o p e r a t i o n s on the p a c k e d symbols. Even
if w e d i s a l l o w bit v e c t o r operations, the
a special o c c u r r e n c e at j p o s t s j-i on
n/log n p r o c e s s o r s can p r e p a r e (in time
BB. (Note that j = mP + 1 for s o m e m,
O(log n)) a table to i m p l e m e n t t h e s e oper-
x = umu
' R u'' u "-, u ' u a p r e f i x of u 2.) Then ations.
each Pr that sees a 1 at SWITCH(r) checks
whether SWITCH(r+j-I) = 1 and if n o t it

244
5.2 The general case.
t = 0 ( l o g 2 n ) . T h e rest is as in s u b s e c t i o n
W e now h a v e an a l g o r i t h m w i t h tP0 = 5. 2. The a l g o r i t h m can be implemented
w i t h o u t simultaneous reads.
O(n) for P0 = n/log n. This i m m e d i a t e l y
yields a family w i t h tp = O(n) for p 5.4 Having many processors.
n/log n b e c a u s e of the w e l l k n o w n d o w n w a r d
Assume ly I = 21x I = 2n. As waS noted
translation. In general, if tP0 = f(n),
2
above, w i t h n p r o c e s s o r s we can solve
then w e h a v e a family w i t h tp = f(n) for
string m a t c h i n g in c o n s t a n t (t = 2) time
P i P0' b e c a u s e h a v i n g only p processors,
on the WRAM. W e show below that if
each one will. simulate p0/p p r o c e s s o r s and l+i/k
p = n w e can solve string m a t c h i n g
the time w i l l be slowed down by a factor in time O(k). This i m m e d i a t e l y gives the
of p u p . t h i r d and fourth families: for the third,
W e still h a v e to deal w i t h the case take c = i/k and the c o n s t a n t is k. For
in w h i c h Ixl and !Yl are unrelated. Let the fourth, take k = log n/log log n. In
n = Ixl+lyl (the length of the input) and this case p = n log n, but by packing
m = Ixl. If p ~ 2 n / m we d i v i d e y into symbols we reduce p to n.
p/2 equal parts. Let the i-th p i e c e be In this s u b s e c t i o n we use a stronger
the c o n c a t e n a t i o n of the i-th and (i+l)st v e r s i o n of WRAM. In case of a w r i t e con-
parts. There are p pieces and we assign flict the p r o c e s s o r w i t h the m i n i m u m num-
one p r o c e s s o r per piece. The size of a ber is the one that writes. At the moment,
p i e c e S = 21y~/(p/2) satisfies 4 n / p ~ S if it is not k n o w n w h e t h e r such a W R A M can
2n/p ~ m. Each p r o c e s s o r looks for all be s i m u l a t e d by our w e a k e r type w i t h o u t
o c c u r r e n c e s of x in its p i e c e in time time loss. However, in our case, such sim-
O(S) = O(n/p). H e n c e in this case, w h e n u l a t i o n is possible.
we h a v e a small n u m b e r of processors, w e A s s u m e one s u b s e t of p p r o c e s s o r s
h a v e an optimal a l g o r i t h m simply because we tries to w r i t e s i m u l t a n e o u s l y into a re-
still solve the p r o b l e m sequentially. g i s t e r and the p r o c e s s o r w i t h the minimal
If p > 2 n / m (p ~ n/log m) w e b r e a k n u m b e r succeeds. It was o b s e r v e d in [FRW]
y into o v e r l a p p i n g pieces of size 2m. The that our w e a k e r model of W R A M can do the
number s of such pieces s a t i s f i e s same in four steps: the p r o c e s s o r s are
n / m ~ s ~ 2 n / m < p. W e assign p/s p a r t i t i o n e d into 4 ~ groups of size ~ .
(~ m / l o g m) p r o c e s s o r s per piece. By the In the first step each g r o u p computes
first p a r a g r a p h above, all the o c c u r r e n c e s w h e t h e r one of its members wants to write.
in a p i e c e can be found in time t such The r e s u l t is a B o o l e a n array of size 4~.
that t.p/s = O(m), or tp = O(ms) = O(n). In the second step the l's in that array
that are not first are turned off. This
5.3 On the PRAM. is p o s s i b l e b e c a u s e there are 4 ~ p r o c e s s o r s
for each i. Now, the p r o c e s s o r s in the
C o n s i d e r the m a i n algorithm. The
c o r r e s p o n d i n g group find in a similar way
only case of c o n c u r r e n t w r i t e is the
the m i n i m a l in the group. Such a simula-
r e g u l a r step: the 2 i-I p r o c e s s o r s of a tion w i l l easily be e x t e n d e d to our case.
block c o m p u t e a n AND. If w e do not allow W h e n we h a v e n or m o r e p r o c e s s o r s
c o n c u r r e n t write, we can no longer e x e c u t e
w e can use them to h a v e x {i+l)'" m o r e than
one stage in c o n s t a n t time. The a l g o r i t h m
twice larger than x (i) and as a result,
on the P R A M takes time O(log2n), b e c a u s e
to h a v e less than log n stages. Specifi-
each stage takes O(log n) time.
Fortunately, we can i m p l e m e n t this cally, let p = 3nl+i/k . The p r o c e s s o r s
a l g o r i t h m w i t h only n / l o g 2 n processors. are d i v i d e d into 3n groups of n I/k- pro-
E a c h p r o c e s s o r is r e s p o n s i b l e for cessors. Each group contains one prin-
2 cipal processor, and is r e s p o n s i b l e for
log n symbols or for log n p a c k e d symbols.
one symbol of z and SWITCH. The length
In a regular step, the p r o c e s s o r s in a
b l o c k m a k e log n c o m p a r i s o n s of p a c k e d of x ~i)"
" is n i/k.- In the first stage (find-
symbols (in time log n). They r e c o r d only
ing all o c c u r r e n c e s of x (I)) the i-th group
w h e t h e r all the c o m p a r i s o n s succeed. Then
looks for an o c c u r r e n c e at i.
using the i m p l i c i t tree structure, t h e y
The size of the blocks for stage i + 1 is
'and' their results in time O(log n).
The d i s c u s s i o n above yields an algo- IX (i) I/2 = hi/K/2.---- A regular step is
simple, since we h a v e enough processors:
r i t h m on a P R A M w i t h p = n/log 2 n and
the n u m b e r of p r o c e s s o r s in the groups

245
 There are some questions unresolved:
corresponding to a block is n (i+l)'-/2k =
i. Can we solve string m a t c h i n g on
IX ( i + l ) I/2. WRAM with n p r o c e s s o r s in con-
The parts c o n c e r n i n g p e r i o d i c i t y are
stant (O(log log n)) time?
slightly different, b e c a u s e the size of
blocks much more than doubles from one stage 2. Can we solve string m a t c h i n g
to the next. To test for periodicity, each d e t e r m i n i s t i c a l l y on P R A M w i t h
p r i n c i p a l p r o c e s s o r in the first block that n/log n (or even n) p r o c e s s o r s
sees 1 w r i t e s its group number minus 1 in O(log n) time? (The parallel
on the same p l a c e of BB. The one with the v e r s i o n of [KR] has p = n,
m i n i m a l group number succeeds, and posts t = O(log n) b u t is p r o b a b i l i s -
the p e r i o d size P. tic.)
Let L i = [x(i)/pJP. Li can be easily 3. Can we find optimal p a r a l l e l al-
gorithms for string m a t c h i n g on
maintained and is a v a i l a b l e in stage i + i.
fixed c o n n e c t i o n networks?
Note that Li+ 1 ~ 2nl/kL i. To test if the
Finally, families of p a r a l l e l algori-
periodicity continues, the first group thms c o r r e s p o n d i n g to all the families men-
tioned above can be d e r i v e d for finding all
checks w h e t h e r SWITCH(i+JLi)=i for j=l .... , initial p a l i n d r o m e s of a g i v e n string w.
2n I/k • (In this case ~(i+l) = 2nl/kLi+x(i) , The r e d u c t i o n of the latter p r o b l e m to
so x ( i + l ) < I~ ( i + l ) ] < 3x ( i + l ) .) string m a t c h i n g [FP] does not help, be-
cause it makes use of the table of the KMP
If the test succeeds, a similar test
algorithm. It is not clear h o w to compute
is used to test which o c c u r r e n c e of x (i) is e f f i c i e n t l y this table in parallel. In-
extended to an o c c u r r e n c e of ~(i+l). If stead we look for w in w rev, recording in
the test fails, using the stronger form of SWITCH,,also o v e r h a n g i n g occurrences. The
c o n c u r r e n t w r i t i n g the first group finds main a l g o r i t h m discovers the initial palin-
the first j ~ i t h ~SWITCH(i+jL i) = 0. The
dromes of length i, 2 i-I < Z ~ 2 i t
in staae _
i •

value of j is p o s t e d on BB, and next

SWITCH(r) = 1 is not turned off only if the Acknowledgement: I am indebted to Uzi
r-th group finds that SWITCH(r+JLi) = 0, V i s h k i n for s u g g e s t i o n s that h a v e led to
several improvements.
and for all k < j SWITCH(r+kL=) = i.
The s t r o n g e r type of c o n c u r r e n t w r i t e
References :
is u s e d only w i t h i n groups, and the memory
locations are d i f f e r e n t for d i f f e r e n t [AHU] A.V. Aho, J.E. H o p c r o f t and J.D.
groups. The s i m u l a t i o n m e n t i o n e d above Ullman, The d e s i g n and analysis of
(for one group) can be o b v i o u s l y extended computer algorithms, A d d i s o n Wesley,
to our case. W e left out the details of Reading MA, 1974.
a l l o c a t i n g of processors. For fixed k [BH] A. B o r o d i n and J.E. Hopcroft,
this task is i m m e d i a t e b e c a u s e we can assume Routing, m e r g i n g and sorting on
that n = 2 kr for some r. In the general p a r a l l e l models of computation, Proc.
case (Ixl and ly I unrelated) the number of 14th A C M STOC (1982), pp. 338-344.
p r o c e s s o r s needed is only nm I/~^" and with [BM] R.S. Boyer and J.S. Moore, A fast
p = n the time b o u n d is O(log m/log log m). string searching algorithm, Comm. A C M
2 0 (1977), pp. 762-772.
6. Conclusion [BY] I. B a r - O n and U. Vishkin, Optimal
W e can i m p l e m e n t the main a l g o r i t h m in p a r a l l e l g e n e r a t i o n of a c o m p u t a t i o n
other models for p a r a l l e l computation: tree form, Manuscript, D e p a r t m e n t of
C o m p u t e r Science, C o u r a n t Institute,
i. Boolean circuits of size
O c t o b e r 1983.
O(n log2n)~Jand depth O(log2n).
[CD] S.A. Cook and C. Dwork, Bounds
2. Fixed c o n n e c t i o n networks (the on the time for p a r a l l e l RAM's to
k - d i m e n s i o n a l cube) and even net- c o m p u t e simple functions, Proc. 14th
works with fixed degree (CCC's A C M STOC (1982), pp. 231-233.
[PV]) in pt = O(n log n). [FP] M.J. F i s c h e r and M.S. Paterson,
The details of these i m p l e m e n t a t i o n are S t r i n g - m a t c h i n g and other products,
straightforward. Both use shifting net- i__n C o m p l e x i t y and Computation, SIAM-
works as building blocks. AMS p r o c e e d i n g s ! (R.M. Karp, Ed.),

246
 pp. i13-125, American Mathematical [PV] F.P. Preparata and J. Vuillemin,
Society, Providence, R.I., 1974. The cube-connected-cycles: a versa-
tile network for parallel computa-
[FRW] F.E. Fich, RoL. Ragde and A. Wig-
tion, Proc. 20th IEEE FOCS (1979),
derson, Relations between concurrent-
pp. 140-147.
write models of parallel computation,
Manuscript, November 1983. [SV] Y. Shiloach and U. Vishkin, Find-
ing the maximum, merging and sorting
[GS] Z. Galil and J.I. Seiferas, Time- in a parallel computation model, J__~
space-optimal string matching, JCSS 26 of Algorithms 2 (1981), pp. 88-102.
(1983), pp. 280-294.
[V] L.G. Valiat, Parallelism in com-
[KMP] D.E. Knuth, J.H. Morris and V.R. parison problems, SIAM J. on Comput- "
Pratt, Fast pattern matching in inq 4 (1975), pp. 348-355.
strings, SIAM J. Gomput. 6 (1977),
[Vi] U. Vishkin, An optimal parallel
pp. 322-350.
algorithm for selection, Manuscript,
[KMR] R.M. Karp, R.E. Miller, and A.L. Department of Computer Science,
Rosenberg, Rapid identification of Courant Institute, December 1983.
repeated patterns in strings, trees
and arrays, Proc. 4th A C M STOC (1972),
pp. 125-136.
[KR] R.M. Karp and M.O. Rabin, Effi-
cient randomized pattern-matching
algorithms, a manuscript.
[LS] R.C. Lyndon and M.P. Schutzen-
berger, The equation aM = bNc P in a
free group, Michigan Math. J.
(1962), 289-298.

(i) (i)
I x I i---- Y 1

,
!
I
!
I
I

z I

SWITCH ... [ Z ]

A+i
1bb

~ure I. An occurrence of x (i) in z followed by a potential

occurrence of y(i) ; a block in SWITCH and its ibb.

247
 i+i+ i

periodical

yes no

/ i+i+l

property
i holds

continues
the periodic
yes
loop

@
\ find
occurences
turn
off
turn
off

of x (i+l)

regu]. a t
step

I
[!gure 2. Stage i+ 1

Q = property i holds

248