Abstract: This survey paper describes our research in the development of very fast parallel algorithms, ones faster than those available through normal parallel programming techniques or standard parallel computers. Algorithms have been developed for problems in geometry, graph theory, arithmetic, sorting, and image processing. The computing models that these algorithms have been developed for are concurrent read concurrent write parallel random access machines (CRCW PRAMs), and reconfigurable meshes (rmeshes).

For CRCW PRAMS, our work has shown that by combining randomization with the use of some extra memory, one can solve some problems far faster than they can be solved if only randomization is used. We have developed ultrafast algorithms for several problems, where by ultrafast parallel algorithm we mean a parallel algorithm with an input of size n which uses at most a linear number of processors and finishes in poly-loglog time, i.e., in time O((loglog n)^k) time for some k > 0. An important ultrafast algorithm is padded sort, where n random numbers are placed in sorted order in an array of size n+o(n) in poly-loglog time. Such a time is impossible, even using a polynomial number of processors, if one insists on removing the padding and sorting into an array of size n. The simple parallel target shooting problem proves the optimality of several of our graph algorithms.

For rmeshes, our work has shown that they can deterministically solve many problems faster than regular mesh-connected computers, and in some cases can solve problems even faster than a CRCW PRAM. For example, it is possible to do a comparison-based sort in constant time, using a number of processors polynomial in the size of the input. Such a sort is impossible for the PRAM. While various notions of reconfigurability have been around for some time, rmeshes are a class of machines which have only recently been studied and built, and which show great promise for a variety of tasks.

Keywords: SIMD parallel computer, ultrafast parallel algorithm, CRCW PRAM, reconfigurable mesh, rmesh, randomized algorithm, graph theory, geometry, sorting, lower bounds

Complete paper.    This paper appears in Proc. DARPA Software Technology Conference 1992, pp. 184-188.

Ultrafast PRAM Algorithms

The geometric results surveyed here appear in Constant-Time Geometry on PRAMs and in Ultra-Fast Expected Time Algorithms; the graph algorithms appear in Optimal Parallel Construction of Hamiltonian Cycles and Spanning Trees in Random Graphs.

Reconfigurable Mesh

Important early papers are Parallel computations on reconfigurable meshes and Reconfigurable SIMD parallel processors.

Parallel Computing

A modest explanation of parallel computing, a tutorial on parallel computing, and a list of parallel computing resources
An overview of my work, and relevant papers.

Copyright © 2005-2017 Quentin F. Stout