基于NP的Dijkstra算法硬件多线程实现与性能分析  

Performance Analysis and Multithreaded Implementation of Dijkstra Algorithm Based on Network Processor

作　　者：杨冬[1] 张宏科[1] 王江林[1] 武勇[1] 

机构地区：[1]北京交通大学电子信息工程学院,北京100044

出　　处：《北京交通大学学报》2005年第5期14-18,共5页JOURNAL OF BEIJING JIAOTONG UNIVERSITY

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

摘　　要：Dijkstra算法是链路状态路由协议使用的主要算法.随着Intenet中加入的路由器数目的不断增加,该算法运行的时间花费越来越大,影响了路由协议的性能,成为链路状态路由协议的一个瓶颈问题.本文将从这一瓶颈问题出发,采用Intel公司的网络处理器IXP2400为硬件平台,设计Dijkstra算法的硬件多线程实现,从而提高处理器利用率,缓解瓶颈.最后给出一种性能分析和优化的计算方法.通过计算可以看到,在节点比较密集的星形网络拓扑结构中,多线程实现可提高两倍的性能.Dijkstra is the most important algorithm in link-state routing protocol. As the number increase of routers in the Intenet, Dijkstra algorithm need mores and more time to run. This has affected the effectiveness of routing protocol and become a bottle-neck for the link-state routing protocol. To ease the bottle-neck, this paper desiyns a multithreaded implementation scheme of Dijkstra algorithm based on Intel＇s network processor IXP2400. At the end of the paper, an effective way to gain optimized performance is proposed. In higa-density star toplogy network, multithreaded implementation can improve the efficiency twice bascd on our experiments.

关 键 词：DIJKSTRA算法 多线程 网络处理器 可移植性 

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