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, ...
Advisors
Maeng, Seung-Ryoulresearcher맹승렬researcher
Publisher
한국과학기술원
Issue Date
1996
Identifier
106123/325007 / 000845041
Language
eng
Description

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

Keywords

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

URI
http://hdl.handle.net/10203/33050
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=106123&flag=t
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 136
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0