Browse Prior Art Database

OPTIMAL PARALLEL ALGORITHMS FOR STRING MATCHING

IP.com Disclosure Number: IPCOM000127966D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 16 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

Zvi Galil: AUTHOR [+3]

Abstract

Let WRAM [PRAM] be a parallel computer with p processors (RAM's) which share a common memory and are allowed sim-ultaneous reads and writes [only simultan-eous reads]. The only type of simultan-eous writes allowed is a simultaneous AND: several processors may write 0 simul-taneously into the same memory cell. Let t be the time bound of the computer. We design below families of parallel algori-thms that solve the string matching pro-blem with inputs of size n (n is. the sum of lengths of the pattern and the text) and have the following performance in terms of p, t and n: 1. For WRAM: [Equation ommitted] 2. For PRAM: [Equation ommitted] 3. For WRAM: [Equation ommitted] and any [Equation ommitted] For WRAM: [Equation ommitted]

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

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

OPTIMAL PARALLEL ALGORITHMS FOR STRING MATCHING

Zvi Galil*

Tel-Aviv University Columbia University

*Research supported by National Science Foundation Grant MCS-8303139.

Abstract:

Let WRAM [PRAM] be a parallel computer with p processors (RAM's) which share a common memory and are allowed sim-ultaneous reads and writes [only simultan-eous reads]. The only type of simultan-eous writes allowed is a simultaneous AND: several processors may write 0 simul-taneously into the same memory cell. Let t be the time bound of the computer. We design below families of parallel algori-thms that solve the string matching pro-blem with inputs of size n (n is. the sum of lengths of the pattern and the text) and have the following performance in terms of p, t and n:

1. For WRAM:

(Equation Omitted)

2. For PRAM:

(Equation Omitted)

3. For WRAM:

(Equation Omitted)

and any

(Equation Omitted)

For WRAM:

(Equation Omitted)

Similar families are also obtained for the problem of finding all initial palindromes of a given string.

1. Introduction.

We design parallel algorithms in the following model: p sychronized processors (RAM's) share a common memory. Any subset

Columbia University Page 1 Dec 31, 1983

Page 2 of 16

OPTIMAL PARALLEL ALGORITHMS FOR STRING MATCHING

*Research supported by National Science Foundation Grant MCS-8303139.

of the processors can simultaneously read from the same memory location. We some-times allow simultaneous writing in the weakest sense= any subset of proces-sors can write the value 0 into the same merry location (i.e., turn off a switch). We denote by WRAM [PRAM] the model that allows [does not allow] simultaneous writ-ing. We also consider (but only briefly) other models of parallel computation. we actually design a family of algorithms be-cause we have a parameter p. The perfor-mance of the family is measured in terms of three parameters: p--the number of pro-cessors, t--the time, and n--the size of the problem instance. It is well known that every parallel algorithm with p processors and time t 'can be easily converted to a sequential algorithm of time pt. Hence the analog of linear-time algorithm in sequential com-putation is a family of parallel algorithms with pt = 0(n). We therefore call such algorithms optimal. Surprisingly, while there are many problems for which linear-time algorithms are known, there are very few problems for which optimal parallel algorithms are known for a wide range of p. So few, that we list them here. Every associative function of n var-iables can be computed by a PRAM in

(Equation Omitted)

(Use a binary tree, each leaf "treats" n/p inputs.) For a certain subset of these functions includ- ing the n variable OR (AND), n(log n) time is needed on the PRAM [CDJ, so pt = O(n) is unattainable for p n/log n. Consequently, the only question left is. with how few processors can we compute these functions in constant time on a WRAM. The answer dep...