Generalized classes of rearrangeable multistage interconnection networks = 재설정가능 다단계상호연결망의 일반화에 관한 연구

The rearrangeability and routing algorithms of multistage interconnection networks are studied in this thesis. The main contribution of this thesis is the generalization of rearrangeable networks. Two generalized classes of rearrangeable networks, called {\it Symmetric Bit-Permute Multistage Interconnection Networks(Symmetric BPMIN``s)} and {\it Generalized Rearangeable Networks(GRN``s)}, are proposed. The general routing algorithms for the classes of networks are also proposed. For the asymmetric $2\log N$ stage networks including the omega-omega network, the problems of inside-out routing algorithm suggested by Feng and Seo are addressed. A modified necessary and sufficient condition for proper routing in the omega network, which can be used for routing in the omega-based networks, is also suggested. At first, a class of $\log N$ stage interconnection networks, called {\it Bit-Permute Multistage Interconnection Networks(BPMIN``s)}, is introduced. In a BPMIN, the ports of each switching element of a stage have labels which are different at only one bit position. The BPMIN``s have recursive decomposition structures, and all of BPMIN``s are topologically equivalent and some of them are functionally equivalent. Based on the recursive decomposition structures of the BPMIN``s, a new class of $2\log N$ stage rearrangeable networks, called {\it Symmetric BPMIN``s}, are proposed. They are constructed by concatenating two $\log N$ stage BPMIN``s in sequence, and are either symmetric or asymmetric, regular or irregular in their inter-stage connections, and can be reduced into $2\log N-1$ stages by combining the two center stages. It is shown that the Symmetric BPMIN``s constitute larger class of rearrangeable networks than the equivalent Benes networks suggested by Yeh and Feng. A general routing algorithm for the Symmetric BPMIN``s is suggested by modifying slightly the looping algorithm of the Benes network. Next, a more generalized class of rearrangeable networks, ...
Maeng, Seung-Ryoulresearcher맹승렬researcher
Issue Date
106123/325007 / 000845041

학위논문(박사) - 한국과학기술원 : 전산학과, 1996.2, [ ix, 111 p. ]


Routing Algorithm; Rearrangeable Networks; Equivalence Relationships; Multistage Interconnection Networks; Multiprocessing; Network Labeling Scheme; 망 레이블링방법; 경로설정 알고리즘; 재설정가능 연결망; 동치관계; 다단계상호연결망; 다중처리

Appears in Collection
Files in This Item
There are no files associated with this item.
  • Hit : 136
  • Download : 0
  • Cited 0 times in thomson ci


  • mendeley


rss_1.0 rss_2.0 atom_1.0