SPORT:一种面向基三分层互连网络的最短路径路由算法  

SPORT: A Shortest Path Routing Algorithm for Triplet-Based Hierarchical Interconnection Network

作　　者：张杨[1,2] 石峰[1] 计卫星[1] 左琦[1] 

机构地区：[1]北京理工大学计算机科学技术学院,北京100081 [2]河北科技大学信息科学与工程学院,河北石家庄050018

出　　处：《北京理工大学学报》2013年第1期57-61,共5页Transactions of Beijing Institute of Technology

基　　金：国家自然科学基金资助项目(60973010)

摘　　要：针对基三分层互连网络(THIN)中已有编码方法和路由算法不能应用于非平衡构造THIN的问题,提出一种既适合表示平衡构造THIN又适合表示非平衡构造THIN的编码方法,并基于该编码方法提出一种最短路径路由算法SPORT.该算法采用源路由方式,可以在源节点计算目的节点的最短路径.使用Noxim片上网络模拟器搭建了仿真实验平台,并将SPORT算法与已有的DDRA算法及Min-DDRA算法进行了比较,实验结果表明,SPORT算法具有较小的通信延迟.此外,还研究了局域性对THIN和2D-mesh两种网络通信延迟的影响,实验结果表明,对局域性特征明显的程序负载,THIN的通信延迟要低于2D-mesh.Existing routing algorithm for triplet-based hierarchical interconnection network （THIN） could not be applied to non-balanced THIN. To solve this problem, this paper proposes a new shortest path routing algorithm （SPORT）. It computes the shortest path at the source node and constructs the output port lists, which can apply to both balanced THIN and non-balanced THIN. The platform of experiment was established by utilizing Noxim simulator. Simulation results show that the traffic latency of SPORT is lower than existing routing algorithms such as DDRA and Min-DDRA ones. Furthermore, when the localization is considered to compare the latency of THIN with 2D-mesh, results show that, for those networks with high-localized workloads, the performance of THIN is superior to that of 2D-mesh.

关 键 词：路由算法 基三分层互连网络 编码 性能评估 

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