基于二进制寻路法和多Omega网络的自路由无阻塞多级网  

New self-routing and non-blocking MINS based on binary splitting concept and omega network

作　　者：张联[1] 顾乃杰[1] 刘刚[1] 

机构地区：[1]中国科学技术大学计算机科学技术系

出　　处：《计算机应用》2005年第12期2923-2924,2937,共3页journal of Computer Applications

摘　　要：提出了一种可以无阻塞地传输其输入与输出间任意多播信号的新型自路由无阻塞多级网。该网络采用了循环重建法,以二进制扩散概念为基础。它由一个二进制扩散网络和两个二分之一大小的多播路由网络循环构建而成。多播信号由第一个Omega网复制并二分扩散到输出端口,进入N×N的Omega×Omega-1网络,再进入紧随其后的N/2×N/2的Omega×Omega-1网络……。每个Omega×Omega-1网络负责依照目的地址的有效标志位将输入置换到输出的上半部分和下半部分,再分别进入上下两个子Omega×Omega-1网络中做同样的处理,如此类推,直到全部地址有效位处理完毕,从而完成自路由无阻塞的多播传输。由于各大小不等的Omega×Omega-1网络皆可并行设置和并行路由,故此种新型多Omega网络的设置时间为O(NlogN),路由时间为O(log2N),硬件代价则为O(Nlog2N)。它比现行已知的多播网络设计具有较优的代价。A design for a new self-routing multicast network which can realize arbitrary multicast assignments between its inputs and outputs without any blocking was proposed. The network design used a recursive decomposition approach and was based on the binary splitting concept. It was recursively constructed by cascading a binary splitting network and two half-size multicast networks, The multicast assignments were copyed and binary splitted by the first Omega network and then routing through the N ×N Omega× Omega^-1 networks and the N/2× N/2 Omega × Omega^-1 networks and so on. All kinds of Omega ×Omega^-1 networks have different size, but they can be connected and routing parallel. This new muhicast network uses O（Nlog^2N） logic gates, and has O（log^2N） depth and O（log^2N） routing time, It is compared favorably with the previously proposed multicast networks,

关 键 词：多播 多级网 Omega网络 二进制寻路法 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]