Communication efficient parallel algorithms for nonnumerical computations

The broad goal of this research is to develop a set of paradigms for mapping data-dependent symbolic computations on realistic models of parallel architectures. Within this goal, the thesis represents the initial effort to achieve efficient parallel solutions for a number of non-numerical problems on networks of processors. The specific contributions of the thesis are new parallel algorithms, exhibiting linear speedup on architectures consisting of fixed numbers of processors (i.e., bounded models). The following problems have been considered in the thesis: (1) Determine the minimum spanning tree (MST), and identify the bridges and articulation points (APs) of an undirected weighted graph represented by an $n \times n$ adjacency matrix. (2) The pattern matching problem: Given two strings of characters, of lengths $m$ and $n\ ({\geq}m)$ respectively, mark all positions in the second string where there appears an instance of the first string. (3) Sort $n$ elements. For each problem, we use a processor-network consisting of $p$ processors. The network model used in the solution of the first set of problems is the linear array; while that used in the solutions of the second and third problems is a butterfly-connected system. The solutions on the butterfly-connected system apply also on a pipelined hypercube. The performances of the solutions are summarized below. (1) For a graph on $n$ vertices and represented by a distributed adjacency matrix, we present a solution for the MST problem that requires O$(n\sp2/p + n + p)$ time for execution. We present novel data reduction schemes for identifying the bridges and articulation points. (2) The string matching solution requires time O$((n + m)/p + \log\sp2 p),$ where $n$ and $m$ are the lengths of the two strings. No previous parallel solutions achieving linear speedups have been proposed on networks of processors. (3) The execution time requirements of the sorting algorithm are O$(n/p \log n + \log\sp2p),$ which represents a linear speedup up to the use of $n/\log n$ processors. A previous solution achieved linear speedup on a $2\sp{\sqrt{\log n}}$ processor binary-cube. A new parallel merging procedure is presented in the algorithm. Also, as part of the algorithm, a new routing operation called Forward-copy is shown to result in conflict-free communication on the butterfly. (Abstract shortened with permission of author.