Designing fast and efficient parallel algorithms
Yu Han · 1987
With the advance of VLSI technology parallel computers with thousands or even millions of processors will be available. Thus studying the inherent parallelism of computational problems and developing parallel algorithms are currently important research topics. In this dissertation we present parallel algorithms for some fundamental computational problems. We present algorithms for finding a maximal matching for a linked list of n nodes in time $O\left({nG(n)\over p}+G(n)\right)$ or $O\left({n\over p}+{\rm log}n\right)$ using processors on an exclusive read exclusive write parallel computation model, where G(n) is defined as follows: ${\rm log}\sp{(1)}n$ = ${\rm log}n,$ ${\rm log}\sp{(i)}n$ = ${\rm log(log}\sp{(i-1)}n),$ $G(n) = {\rm min} \{ i\mid {\rm log}\sp{(i)}n\le 2 \}.$ On a concurrent read concurrent write model we achieve time complexity $O\left({n\over p} + {{\rm log}n\over {\rm log}\sp{(2)}n}\right).$ For the linked list prefix problem, we show an algorithm which achieves time complexity $O\left({n\over p}+ {\rm log}n\right)$ using processors on the concurrent read concurrent write parallel computation model. The technique of the algorithm yields time complexity $O\left({n {\rm log}\sp{(k)}n\over p}+k {\rm log}n\right)$ for the linked list prefix problem on the exclusive read exclusive write model, where k is an arbitrary positive integer. In particular, when $k = G(n),$ we present an algorithm with time complexity $O\left({n\over p}+G(n){\rm log}n\right).$ We also present a parallel algorithm for computing connected components for an undirected graph of e edges and n nodes in time $O\left({eh(e,n,p)\over p} + {n {\rm log}n\over p {\rm log}(2n/p)} + {\rm log}\sp2n\right)$ using processors on a concurrent read exclusive write model, where function h is very slow growing. This algorithm is optimal when $e \ge n{\rm log}\sp{(i)}n$ for any positive integer i.