Reconfigurable cellular computers

When a collection of processors P1,,Pn< operates in parallel, it is desirable that at any given stage of the computation, each {ifPi should have a task of about the same size to perform, and each {ifPi should require about the same amount of information from the other P's in order to perform its task. To the extent that these conditions are violated, parallelism is impaired, in the sense that the P's are not all used with equal efficiency. In cellular computers, e.g., as they might be used for parallel image processing, these conditions are maintained by having the P's all perform similar computations on different parts of the input data, and by allowing each Pi to receive information from a fixed set of the others (its “neighbors≓), where these sets are all of bounded size. This paper discusses, on an abstract level, the concept of a reconfigurable cellular computer, in which each Pi can receive information from a set Si of the other P's, and the Si's areall of bounded size, but they need not remain fixed throughout a computation. Requiring the Si's to have bounded size implies that most P's cannot communicate directly; the expected time required for two arbitrary P's to communicate depends on the graph structure defined by the sets Si. The question of how to change the Si's in parallel during the course of a computation is also discussed