RECONFIGURATION WITH TIME-DIVISION MULTIPLEXED MINS FOR MULTIPROCESSOR COMMUNICATIONS

In this paper, time division multiplexed multistage interconnection ne tworks (TDM-MIN's) are proposed for multi-processor communications. Co nnections required by an application are partitioned into a number of subsets, called mappings, such that connections in each mapping can be established in an MIN without conflict. Switch settings for establish ing connections in each mapping are determined and stored in shift reg isters. By repeatedly changing switch settings, connections in each ma pping are established for a time slot in a round-robin fashion. Thus, all connections required by an application may be established in an MI N in a time division multiplexed way. TDM-MIN's can emulate a complete ly connected network using N time slots. It can also emulate regular n etworks such as rings, meshes, cube-connected-cycles (CCC), binary tre es, and n-dimensional hypercubes using 2, 4, 3, 4, and n time slots, r espectively. The problem of partitioning an arbitrary set of requests into a minimal number of mappings is NP-hard. Simple heuristic algorit hms are presented and their performances are shown to be close to opti mal. The flexibility of TDM-MIN's allows for the support of run-time r equests through dynamic reconfigurations. The techniques are especiall y suitable for hybrid electro-optical systems with optical interconnec ts.