With the advent of low-cost microcomputers, it is now feasible to construct networks for interconnecting many processor and memories to achieve higher speed of computation. In this research project, the principal investigator (PI) will study tightly-coupled processors interconnected using a dynamic interconnection network. In very general terms, the problem is to provide a means of interconnecting a collection of processing elements so that any two processing elements can obtain a direct communication path. This will allow dynamic reconfigurations. The PI proposes to study the class of interconnection networks that provide full access (i.e., the ability for every input to access every output) using the fewest possible number of stages--networks which the PI refers to as "minimal full-access" (MFA). The following are expected research results: o Characterizations of structural properties of MFA networks. o Results on the set of permutations realizable by particular subclasses of MFA networks and how the results compare to permutations realizable by other classes of networks. o Efficient algorithms for routing MFA networks. o Techniques for allowing dynamic reconfigurations of one network into another better suited for applications at hand. o Simple modifications of the networks studied, to allow for increased fault tolerance. o Algorithms for deciding structural and functional equivalence of networks. This work is expected to produce new classes of networks, as well as provide a basis for an underlying theory of all interconnection networks. It is also expected to impact the (d,k) graph problem and the solution of certain matrix equations.
