不规则网络中基于拐弯模型的路由算法的设计  

Designing Routing Algorithms Based on Turn Model for Irregular Networks

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

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

出　　处：《小型微型计算机系统》2005年第9期1470-1473,共4页Journal of Chinese Computer Systems

基　　金：国家自然基金重大国际(地区)合作研究项目(40120140817)资助.

摘　　要：由虫孔路由交换器连接而成的不规则拓扑网络,越来越多地用于构建工作站机群系统(NOWs),以实现高性能价格比的并行处理.采用虫孔路由技术,网络中容易发生死锁.交换器之间连接的不规则性,使路由避免死锁问题变得更加复杂.本文给出了在不规则网络中,设计基于拐弯模型的无死锁路由算法的一般方法,并采用扩展链路方向的方法得到多种路由策略,确定了up-first与down-last两种性能较优的路由算法.最后通过模拟实验,评价了算法的性能.Irregular networks connected by wormhole-routed switches are becoming increasingly popular for building networks of workstations for cost-effective parallel processing. Networks using wormhole routing techniques are particularly vulnerable to deadlock. The irregularity makes routing and deadlock avoidance on such systems quite complicated. This paper proposes a general methodology to design deadlock-free routing algorithms based on turn model, and extends link directions to obtain several routing strategies, in the end determines two new routing algorithms. By simulations it is showed that the up-first routing algorithm and down-last routing algorithm achieve higher performance, in terms of delay, than other algorithms, such as the spanning tree and up ＊ /down ＊ routing algorithms.

关 键 词：机群系统 不规则拓扑 死锁 路由算法 

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