一种构建无阻塞多级互连网络的方法.pdfVIP

一种构建无阻塞多级互连网络的方法 冯勇华，罗风光，袁菁 华中科技大学光电科学与工程学院，武汉 430074 E-mail:Xwhatif@163.com 摘要：提出一种构建无阻塞多级互连网络的一般方法。与Clos、Benes及Waksman等网络的递 归构建方法不同，该方法将多级互连网络分为置换网络和无阻塞交换网络两个部分：置换网 络的输出端分组后与相应通道数目的无阻塞交换网络相连，将输入无阻塞地引入到相应的无 阻塞交换网络；无阻塞交换网络实现输入经置换网络分组后各组输入的无阻塞交换。该方法 可用于构建任意输入输出端口的无阻塞多级互连网络。文中以基于 1×1 连接器、2×2 交叉 连接器的 3×3 和4×4 互连网络为例对所提出的方法进行演示说明。 关键字：多级互连网络 无阻塞 置换 交换网络 Another Approach to Construct Nonblocking Multistage Interconnection Networks Yonghua Feng, Fengguang Luo, Jing Yuan School of Optoelectronic Science and Technology, Huazhong University of Science and Technology, Wuhan, Hubei 430074, China E-mail:Xwhatif@163.com Abstract ：Different from the classic recursive method adopted with Clos, Benes, and Waksman networks, a general approach based on permutation network and nonblocking switching network is proposed to construct nonblocking multistage interconnection networks. The permutation network assures each input can be switched to every input group of the nonblocking switching network without blocking. Nonblocking switching network realize nonblocking switching of their corresponding grouped inputs to outputs. 3×3 and 4×4 multistage interconnection networks based on 1×1 connecter and 2×2 crossbar are demonstrated with the proposed approach. Keywords: multistage interconnection network, nonblocking, permutation, switching network. 1. 简介 通过互连网络将廉价、通用的小系统连接扩展以构建一个高性价比的大系统，是互连网 络研究的初衷。并行计算、分布式处理以及交换机的扩展等都离不开高性能的互连网络[1-3]。 自Clos于1953年发表其代表作《非阻塞性交换网络的研究》以来的半个多世纪，互连网络的 研究从未中断，其中最为典型的研究成果包括Clos多级交换网络、Benes 网络、Waksman 网 络[4-7]。其中Benes 网络是Clos 网络C(m, n, k) 的特例C(