Candidate: Robert F. Kelly
Advisor: Robert Hummel
3:30 p.m., Wednesday, February 20, 1991
719 Broadway, 12th floor conference room


We examine the process of parallel algorithm development for a class of image synthesis and image processing problems. Algorithms are developed for a class of parallel machines characterized by shared memory multiprocessors, such as is exhibited by the Ultracomputer model. The new algorithms are asynchronous in nature, and many employ the ``pool of tasks'' paradigm. These algorithms are prototyped using the sequential specification language SETL that has been adapted to function as a parallel specification tool. The issue of refinement of the high-level specification is illustrated with a number of examples of machine-specific implementations.

Parallel algorithms are proposed for the connected components problem, for hidden surface removal in surface rendering, and parallel algorithms for ray tracing are discussed. Within the investigation of connected components algorithms, new algorithms are suggested for four classes of approaches to the problem: (1) Adjacency matrix methods, (2) pointer graph methods based on the vertex collapse algorithm of Hirschberg, (3) pointer graph methods based on the Shiloach/Vishkin connected components algorithm, and (4) image scan algorithms, based on the sequential raster scan ``blob coloring'' algorithm. For the third area, the Shiloach/Vishkin-type connected components algorithm, we show how a stronger model of computation (one that permits constant-time concurrent additive-writes) allows the elimination of one of the steps of the algorithm. Although this modification does not improve the asymptotic time complexity of the algorithm, the MIMD version of the Shiloach/Vishkin algorithm is then considerably simplified, and contains fewer synchronization points, and has improved expected execution time performance.

All algorithms are given in the parallel-adapted SETL language. The final versions of all proposed parallel connected components algorithms are further refined into EPEX/Fortran, suitable for execution on an RP3 simulator system. Empirical results are obtained for various algorithms, by use of instrumenting either the SETL version or the EPEX/Fortran version, thereby providing estimates of expected performance times by means of examining average lengths of queues of tasks. In particular, queue activity patterns are examined for executions of the parallel adjacency matrix connected components algorithm, and the MIMD version of the Shiloach/Vishkin connected components algorithm. For the latter, run-time performance estimates are made demonstrating the utility of the modifications made to the MIMD version of the algorithm. For the image scan algorithms, estimates are obtained comparing the size of subimages that are assigned to processors against the sizes of the reduced graph connected components problem that result, based on runs of the EPEX/Fortran version. Finally, the shared-memory access patterns of the parallel ray-tracing algorithm are examined, suggesting that the algorithm is viable in terms of memory contention rates.