On resource allocation in multistage interconnection network-based systems

A resource allocation problem in a reconfigurable multicomputer architecture based on rectangular banyan multistage interconnection network with arbitrary fanout and arbitrary number of levels is studied. Four commonly used problem structures such as ring, pipeline, broadcast, and macropipeline are introduced and the mapping problem of these structures on the system model, which is equivalent to the resource allocation problem, is discussed. Analytic solutions to several mapping questions are given and generalization of the results to other networks is presented.