Up*/Down*路由算法的改进方案  

Modified Scheme for the Up*/Down* Routing Algorithm

作　　者：葛建芳[1] 张功萱[2] 

机构地区：[1]南通工学院信息工程系,江苏南通226007 [2]南京理工大学计算机科学系,江苏南京210094

出　　处：《小型微型计算机系统》2004年第12期2218-2221,共4页Journal of Chinese Computer Systems

摘　　要：机群系统 (NOWs)用于并行计算具有性能价格比高、结构灵活、可扩展性好等优点 ,但要实现高性能的机群系统 ,必须采用交换式高速互连网络 .交换器之间连接的不规则性 ,使路由与死锁避免问题非常复杂 .介绍了不规则拓扑网络中经典的 up* / down*路由算法 ,分析它的实现原理 ,指出了它在链路方向指派方面的不合理性 ,并基于贪婪算法的思想 ,给出了优化的链路方向指派方法 ,由此确定新的路由算法 greedy- U D.经模拟实验证明 ,greedy- U D算法较up* /Network of workstations(NOWs) are rapidly emerging as a cost-effective alternative to parallel computers. Many NOWs are arranged as a swith-based network with irregular topology, which makes routing and deadlock avoidance quite complicated. The up*/down* routing is broadly used in irregular networks. However, this strategy assigns direction to the operation links radomly, and it follows that most minimal paths are forbidden. Proposed a new methodology to assing direction based on the greedy alogrithm. The methodology can reduce the percentage of prohibited turns, and made a better traffic balancing. The simulation result indicate that the new routing algorithm based on the new methodology can improve the performance of the network signficantly.

关 键 词：机群系统 不规则拓扑 死锁避免 up＊/down＊路由 

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