Varying Diameter and Problem Size in Mesh-Connected Computers (Preliminary Version)

On a mesh-connected computer, moving data across the mesh is the most time-consuming operation in many algorithms. This time can be reduced by using a mesh with smaller diameter, i.e., with fewer processing elements. To accomodate inputs of the same size, this requires that the processors have more memory. For image processing and graph theoretic algorithms we analyze the time as a function of the mesh diameter and problem size. We show that for many problems, smaller diameters can yield faster algorithms, and that there is a choice of diameter that is simultaneously best for several of these problems. Further, for these problems and this number of processing elements (or any smaller number), the mesh is an optimal interconnection scheme.