A universal interconnection pattern for parallel computers

Abstract

A number of different models of synchronous, unbounded parallel computers have appeared in the literature. Without exception, runnmg time on these models has been shown to be polynomially related to the classical space complexaty measure The general apphcabdity of this relationship is called "the parallel computaUon thesis," and evidence of its truth ts given m this paper by introducing a class of parallel machines called "conglomerates." It is argued that conglomerates include all parallel machines which could feasibly be budt with fixed connections. Basic interconnection patterns are also investigated in an attempt to pin down the notion of parallel time to within a constant factor. To this end, a universal structure ts developed which can simulate any other basic mterconnection pattern within linear time. This approach leads to fair estimates of instruction execution ttmes for various parallel models.