不规则拓扑工作站网络中的路由算法研究.pdfVIP

葛建芳等:不规则拓扑工作站网络中的路由算法研究 不规则拓扑工作站网络中的路由算法研究 葛建芳”’ 张功釜’ 凌永丰 齐广玉. (’南京理工大学计算机科学系 南京210094) 〔南通工学院墓础部 南京226007) 摘 要 近年来工作站机群系统(NOWs)蓬勃发展，成为并行计算领域的一种主流技术。 要提高其性能，必须采用交换式高速互连网络。但交换器之间连接的不规则性，使路由避 免死锁问题变得复杂。本文介绍了不规则网络中经典的up*/down*路由算法，分析和 指出了它在链路方向指派上的不合理性，并塞于贪婪算法的思想，给出了优化的链路方向 指派方法，进而确定了新的路由算法。经模拟验证，新算法较原算法性能有了显著提商。 }`c健词 工作站网络，不规则拓扑，虫孔路由，死锁.自适应路由算法 大小)，并且，当消息长度远远大于微片长度时，消息 0 引言 的通信延迟时间与通信距离无关。因此WH机制受 到了广泛的采纳。但采用虫孔路由的网络易于发生 _]二炸站网络NOW.(NetworkofWorkstations)，或 死锁，这是因为数据包在占有许多资源的同时，又允 称机群系统，近年来受到了人们的广泛关注。这种 许申请其他资源。 系统将一群 〔作站用网络以某种结构互连起来，充 国内外有许多学者研究出各种适合规则拓扑网 分利用各砚作站资源，统一调度、协调处理，以实现 络的路由算法，而关于不规则拓扑网络中路由算法 高效并行计算。其因具有性能价格比高、结构灵活、 的文章则比较少见。在不规则拓扑网络中设计路由 可扩展性好等特点，成为继大规模并行处理系统 算法，是一件具有挑战性的事情。本文尝试对不规 (Mpp)之后，并行计算领域中的又一主流技术。要 则拓扑网络中经典的叩*/down‘路由算法作出改 实现高性能的机群系统，不仅需要高性能的计算机 进.克服其缺点，提高其性能。 作为工作结点机，而且还需要一个高带宽、低延迟网 络系统的支持。目前，出现了多种用于构造NOWs I 不规则拓扑网络中的经典算法 的交换式高速互连网络，如Autonet,Myrinet,Server- Net和ServerNet[[等。互连网络通常由拓扑结构、路 路由算法决定了消息在网络中如何选取路径。 由算法、交换技术、流控机制等几方面来表征。上述 由源结点向目的结点传送消息 根据允许选择的路 诸网络中，一般采用不规则的拓扑结构和虫孔路由 径的不同，路由算法有确定性和自适应性以及最短 交换技术。交换器之间连接的不规则性使布线灵 路径和非最短路径之分。其中确定性路由只要源结 活、设计的系统可扩展能力加强，但也使网络中路由 点与目的结点确定之后，消息传递的路径也就相应 避免死锁的问题变得复杂。 确定。相反，自适应性路由对于一对源与目的结点， 虫孔WH(Wonnhole)路由机制f21。将每个消息分 视网络的实时状况，动态地选择路径。最短路径算 为若干个微片(flit)，其中第一个(头)微片包含消息 法总是选取从源到目的结点间最短的路径，而非最 的路由信息，由它负责开辟通信路径，其他微片以类 短路径算法，路由针对网络当前状态，允许信息沿长 似流水的方式紧跟头微片传输。若头微片由于申请 路径传送。 不到资源而不能继续传输时，整个消息的所有微片 每个实用的路由算法都必须解决死锁问题。死 都进人等待状态，并不释放资源，直到最后一个(尾) 锁指的是这样一种状态，一群数据包中的每一个占 微片通过后才释放这些资源。微片的传输为原子过 有一些资源(链路或缓存)，同时申请被别的数据包 程，即在甸一步中，微片要么在结点输人队列中等 所占据的资源，形成若干包对资源的循环依赖，使这 待，要么经过该结