您的位置:首页  > 论文页面

基于Dijkstra算法的路由算法的实现与验证

发表时间:2016-08-31  浏览量:2110  下载量:868
全部作者: 马先童,祝永新
作者单位: 上海交通大学微电子学院
摘 要: 针对片上网络(network on chip,NOC)拓扑结构节点之间连接很规则和硬件可以并行计算的特点,在Dijkstra 算法计算时优化计算过程,直接计算得出邻接节点的编号。计算未访问过的节点中拥塞值最小的节点时,通过并行比较,一个时钟周期内即可得到最小拥塞值的节点编号。采用verilog 硬件描述语言实现最短路径的路由算法,编写testbench 进行验证。将仿真结果与通用的C 模型进行比较,验证了verilog 模块功能的正确性。最后将verilog 代码在Xilinx Zynq 系列现场可编程门阵列(field programmable gate array,FPGA)上实现。
关 键 词: 计算机系统结构;片上网络;最短路径算法;verilog 硬件描述语言;现场可编程门阵列
Title: Implementation and verification of routing algorithm in network on chip based on Dijkstra algorithm
Author: MA Xiantong, ZHU Yongxin
Organization: School of Microelectronics, Shanghai Jiao Tong University, Shanghai 200240, China
Abstract: By abstracting network on chip (NOC) nodes into points, weights are attached to the network channels based on the degree of congestion. Then the problem of routing selection is converted into a problem of finding the shortest paths between nodes in graph. According to the characteristics of NOC topologies, the calculation process of Dijkstra algorithm is optimized, in which adjacent nodes ID are calculated directly and the minimum congestion’s node ID is got within one clock cycle by parallel comparison in unvisited nodes. It is designed with the verilog hardware description language (HDL). A testbench is created to verify it. The simulation result is compared with the C model. Finally, the algorithm is implemented on a Xilinx Zynq series field programmable gate array (FPGA).
Key words: computer architecture; network on chip; shortest path algorithm; verilog hardware description language; field programmable gate array
发表期数: 2016年8月第16期
引用格式: 马先童,祝永新. 基于Dijkstra算法的路由算法的实现与验证[J]. 中国科技论文在线精品论文,2016,9(16):1627-1635.
 
2 评论数 0
暂无评论
友情链接