基于7级Omega网络的两类16输入输出无分类路由算法  

Routing Algorithms without Classification for 2 Kinds of 16 Inputs/Outputs on 7 Stages Omega Network

作　　者：魏帅[1] 吕平[1] 宋克[1] 魏冉 

机构地区：[1]国家数字交换系统工程技术研究中心,河南郑州450002 [2]邓州市教体局,河南邓州474150

出　　处：《信息工程大学学报》2016年第5期573-578,共6页Journal of Information Engineering University

基　　金：国家973计划资助项目(2012CB315901);国家863计划资助项目(2011AA01A103)

摘　　要：路由问题一直是多级互联网络中的重要问题。早在1975年Benes就猜测（2n-1）级是N=2-n输入/输出Omega网络重排列的充要条件,但至今为止只解决了n≤4时的2n-1级Omega网络的路由构造方法,且其中存在大量的分类,不利于扩展。对Omega网络中的路由问题进行了总结和抽象,采用递归的思想引入了一个可以容纳更多相反关系的赋值定理,并基于此采用启发式的贪婪算法对两类16输入输出的路由问题进行了求解,首次实现了分类路由算法,比较简洁,同时对研究高阶网络的可重排性也有一定参考价值。Routing is a hot issue in the study of multistage interconnection network. Early in 1975 Benes has conjectured that any （2n - 1 ） stage Omega network is sufficient and necessary for rear- rangeability of N = 2n inputs/outputs. However, only the routing problems for n ≤4 have been solved so far, and the methods employ plenty of sorting, so the scalability is poor. This paper summarizes the routing problem on Omega problem, introduces a recursive assignment theorem which can ac- commodate more opposite relation and adopt heuristic greedy algorithm to solve two types of 16 in-put/output problems. It is the first to realize routing algorithm without classification. The method is simple and may provide hints for Omega network with more inputs/outputs.

关 键 词：Omega网络 路由算法 可重排性 多级互连网络 

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