Parallel computations on meshes with static and reconfiguarble buses
Dionysios I. Reisis · 1990
Mesh computers enhanced with buses have been proposed to alleviate the global communication problem of the mesh connected computer. Early algorithms showed that for problems that require sparse data communication, bus oriented organizations provide significant improvement in time performance over the mesh. Several parallel machines with buses have been built such as the Distributed Array Processor, the Gated Connection Network, etc. We propose a variety of bus models for parallel processing including the bus in which single or multiple bus access is allowed and the reconfigurable bus, which provides various interconnection patterns between the processors. The main emphasis of this thesis, is to show that the buses can be exploited to provide parallel solutions to a wide class of problems. We illustrate the use of row and column buses on a mesh by presenting parallel solutions to a variety of graph and image problems including component labeling, convexity of multiple components, distance problems, and extraction of geometric properties of a figure. Essential to these algorithms is a set of parallel sparse data movement operations which make efficient use of the bus connections. Our algorithms have asymptotic time performance similar to and in some cases superior to their counterparts on other organizations such as the pyramid. One of the main contributions of this work is the mesh with reconfigurable bus. We show how the reconfigurable bus can be used to provide parallel data operations of asymptotic time performance similar to or even faster than the powerful Concurrent Read Concurrent Write Parallel Random Access Machine (CRCW P-RAM) for certain problems. Using these data operations in divide and conquer techniques, we develop optimal or near optimal parallel solutions to graph problems under adjacency matrix input as well as unordered edge input and several image problems. The list of problems includes connected components, minimal spanning forest, biconnectivity, labeling of components in digitized images, distance problems, convexity, geometric properties of components, etc. For graph and image problems, our algorithms on the reconfigurable mesh are significantly faster than the known algorithms on the mesh connected computer, the pyramid computer and the mesh of trees organization. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089-0182.)