| 基于NP的Dijkstra算法硬件多线程实现与性能分析 |
| |
| 引用本文： | 杨冬,张宏科,王江林,武勇.基于NP的Dijkstra算法硬件多线程实现与性能分析[J].北京交通大学学报(自然科学版),2005,29(5):14-18. |
| |
| 作者姓名： | 杨冬 张宏科 王江林 武勇 |
| |
| 作者单位： | 北京交通大学,电子信息工程学院,北京,100044;北京交通大学,电子信息工程学院,北京,100044;北京交通大学,电子信息工程学院,北京,100044;北京交通大学,电子信息工程学院,北京,100044 |
| |
| 摘 要： | Dijkstra算法是链路状态路由协议使用的主要算法.随着Intenet中加入的路由器数目的不断增加,该算法运行的时间花费越来越大,影响了路由协议的性能,成为链路状态路由协议的一个瓶颈问题.本文将从这一瓶颈问题出发,采用Intel公司的网络处理器IXP2400为硬件平台,设计Dijkstra算法的硬件多线程实现,从而提高处理器利用率,缓解瓶颈.最后给出一种性能分析和优化的计算方法.通过计算可以看到,在节点比较密集的星形网络拓扑结构中,多线程实现可提高两倍的性能.
|
| 关 键 词： | Dijkstra算法 多线程 网络处理器 可移植性 |
| 文章编号： | 1673-0291(2005)05-0014-0 |
| 收稿时间： | 2005-03-27 |
| 修稿时间： | 2005年3月27日 |
Performance Analysis and Multithreaded Implementation of Dijkstra Algorithm Based on Network Processor |
| |
| YANG Dong,ZHANG Hong-ke,WANG Jiang-lin,WU Yong.Performance Analysis and Multithreaded Implementation of Dijkstra Algorithm Based on Network Processor[J].JOURNAL OF BEIJING JIAOTONG UNIVERSITY,2005,29(5):14-18. |
| |
| Authors: | YANG Dong ZHANG Hong-ke WANG Jiang-lin WU Yong |
| |
| Institution: | School of Electronics and Information Engineering, Beijing Jiaotong University, Beijing 100044, China |
| |
| Abstract: | 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. |
| |
| Keywords: | Dijkstra algorithm multithread network processor transplantable |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
