BNR:最短路径无死锁全自适应路由算法的分析与设计工具

BNR:The Tool to Analyse and Design the Minimal Deadlock_Free Fully Adaptive Routing Algorithm

1 引言大规模并行计算机(MPP)系统性能的发挥极大程度上依赖于互连网络的通信性能,互连网络采用的路由算法决定了消息在网络中如何选取路径,其性能对网络效率的发挥起着重要作用,根据允许选择路径的不同,路由算法有最短路径和非最短路径以及确定性和自适应性之分。

In a massively parallel processors(MPP)system,a routing algorithm constitutes the primary factor influencing the performance of the interconnect network and MPP system. After analysising the characteristics of message routing in interconnection network, one new concept 'the Best Network for Routing'(BNR)is proposed. Using it,we can analyse any minimal deadlock_free fully_adaptive routing algorithm(MDF2A2)proposed,and also can design two new MDF2A2:VBA and LCFAA. On this point,it gives guidelines to the interconnection network designers.