Bit-permute multistage interconnection networks |
| |
| Institution: | 1. Department of Computer Science & Engineering, Indian Institute of Technology Bombay, India;2. Fernuniversität in Hagen, Germany;1. School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China;2. School of Mathematics, Shandong University, Jinan, 250100, China;3. School of Information Science and Engineering, Shandong Normal University, Jinan 250358, China;4. School of Software, Shandong University, Jinan, 250101, China;1. Department of Computer Engineering, Faculty of Engineering, Arak Branch, Islamic Azad University, Arak, Iran;2. Young Researchers and Elite Club, Arak Branch, Islamic Azad University, Arak, Iran;3. Department of Computer and Communication Systems Engineering, Faculty of Engineering, UPM, Malayasia;4. Department of Computer Engineering, Faculty of Engineering, Hamedan Branch, Islamic Azad University, Hamedan, Iran |
| |
| Abstract: | In this paper, we consider a class of log N stage interconnection networks called Bit-Permute Multistage Interconnection Networks (BPMIN's) where the ports of each switch of a stage are different at only one bit position of their labels. We describe the decomposition structure of the BPMIN's and prove that all of the BPMIN's are topologically equivalent and some of them are functionally equivalent. We also identify a class of 2 log N stage rearrangeable networks called symmetric BPMIN's where two log N stage BPMIN's are connected in sequence. The symmetric BPMIN's are either symmetric or asymmetric and regular or irregular in their inter-stage connections and can be reduced into 2 log N-1 stages by combining the two center stages. We show that the symmetric BPMIN's constitute larger class of rearrangeable networks than ever known. We also propose a general routing algorithm for the symmetric BPMIN's by modifying slightly the looping algorithm of the Benes network. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
