Assigning modules to processors in linear arrays and rings

Abstract

The authors concentrate on linear arrays and unidirectional rings of distributed processors. They are able to derive a modeling technique that transforms the assignment problem for a linear array into a minimum-cut maximum-flow problem. They also show that the assignment problem for a unidirectional ring is equivalent to the assignment problem for an appropriately defined linear array. Thus, the authors are able to solve the assignment problem in time bounded by a polynomial in the number of processors in the linear array or the unidirectional ring.