Title :
Reconfiguration with time division multiplexed MIN´s for multiprocessor communications
Author :
Qiao, Chunming ; Melhem, Rami
Author_Institution :
Dept. of Electr. & Comput. Eng., State Univ. of New York, Buffalo, NY, USA
fDate :
4/1/1994 12:00:00 AM
Abstract :
Time division multiplexed multistage interconnection networks (TDM-MIN´s) are proposed for multiprocessor communications. Connections 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 establishing connections in each mapping are determined and stored in shift registers. By repeatedly changing switch settings, connections in each mapping are established for a time slot in a round-robin fashion. Thus, all connections required by an application may be established in an MIN in a time division multiplexed way. TDM-MIN´s can emulate a completely connected network using N time slots. It can also emulate regular networks such as rings, meshes, cube-connected-cycles (CCC), binary trees, and n-dimensional hypercubes using 2, 4, 3, 4, and n time slots, respectively. The problem of partitioning an arbitrary set of requests into a minimal number of mappings is NP-hard. Simple heuristic algorithms are presented and their performances are shown to be close to optimal. The flexibility of TDM-MIN´s allows for the support of run-time requests through dynamic reconfigurations. The techniques are especially suitable for hybrid electro-optical systems with optical interconnects
Keywords :
multiprocessor interconnection networks; time division multiplexing; MIN´s; Markov analysis; N time slots; NP-hard; TDM-MIN´s; binary trees; cube-connected-cycles; embedding; mappings; meshes; multiprocessor communications; multistage interconnection networks; n-dimensional hypercubes; optical interconnects; partition of connection requests; partitioning; reconfiguration; rings; round-robin; shift registers; time division multiplexed; Binary trees; Communication switching; Heuristic algorithms; Hypercubes; Multiprocessor interconnection networks; Partitioning algorithms; Runtime; Shift registers; Switches; Time division multiplexing;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on