保证QoS的片上网络动态路径分配算法研究
|
摘要
随着集成电路制造工艺技术的进步,片上系统SoC在设计过程中遇到了难以解决的问题,如通信能力难以满足系统需求、全局时钟难以同步等问题,制约了单一芯片上集成的IP核的规模和数量。片上网络NoC采用基于包交换的通信方式和全局异步局部同步技术,将从体系结构上解决片上系统设计遇到的问题。对于片上网络路由算法的研究是片上网络研究领域中的一个重要分支。论文研究保证QoS并且适用于片上网络的动态路径分配算法,使之能够根据全局网络状态的变化调整路由路径,以解决网络拥塞和故障链路的问题。
论文首先分析了QoS的性能指标,在此基础上设计了一组适用于片上网络路径分配算法的性能约束条件。针对设计的性能约束条件,提出了一种面向特定应用的动态路径分配算法。其次,在C语言环境设计实现了路径分配算法和片上网络模型,基于该模型对算法进行功能验证和仿真,分析不同通信任务模型下网络负载的分布情况,初步评估算法的性能。然后,在RTL级采用Verilog语言设计实现了路径分配算法,将设计的算法与课题组的RTL级片上网络模型连接,进行功能验证。在功能验证无误的基础上,仿真算法在不同网络状态和不同网络负载下的QoS性能指标,并与XY维序路由和DyXY路由算法对比分析算法的性能。最后,在Synopsys的EDA平台对算法进行综合,分析面积和功耗开销。
通过对比分析RTL级仿真获得的平均传输延时、网络吞吐量、链路利用率等QoS性能指标,结果表明论文提出的动态路径分配算法在不同的网络状态下均获得了较优的性能,有效地平衡了网络负载,从而降低了数据包阻塞率,改善了网络中有链路拥塞和故障状态下的性能。
As technology scales down, the design of System-on-Chip encounters some difficult problems: the communication ability can not satisfy the need of system, the overall synchronous clock system is difficult to design, et al. Those problems restrict the scale of IP cores integrated on a sigle chip. Network on chip which based on GALS and packet switching could solve the problems SoC design encounted. Research on routing algorithm is an important branch of NoC research. This article focuses on the research of dynamic routing algorithm for NoC with Quality-of-Service gruarantees, so that it could adjust routing path according to the change of global network states to resolve the problem of network with congestion and failed links.
Frist, we analyze QoS requirements and design a group of performance constraints for NoC routing algorithm. On this basis, we propose a dynamic routing algorithm for specific application. In order to evaluate the performance of the routing algorithm, we design NoC model and the routing algorithm with C language.Then, we simulate the routing algorithm in different communication tasks model to evaluate the distribution of network load. After that, we design the routing algorithm with Verilog HDL, and connect it with NoC system model of our group to evaluate the design. On this basis, we simulate the routing algorithm in different network status and network load to acquire QoS metrics. Then we compare them with XY routing and DyXY routing to analyze the performance of the algorithm. Finally, we synthesize the algorithm on EDA platform of Synopsys to analyze area and power cost.
By comparing and analyzing the QoS metrics we obtained from RTL-level simulation, the results indicate that the routing algorithm proposed in this paper could balance the network load effectively. Thereby, packet congestion probability is reduced and the performance of the network with congestion and failed links is improved.
论文首先分析了QoS的性能指标,在此基础上设计了一组适用于片上网络路径分配算法的性能约束条件。针对设计的性能约束条件,提出了一种面向特定应用的动态路径分配算法。其次,在C语言环境设计实现了路径分配算法和片上网络模型,基于该模型对算法进行功能验证和仿真,分析不同通信任务模型下网络负载的分布情况,初步评估算法的性能。然后,在RTL级采用Verilog语言设计实现了路径分配算法,将设计的算法与课题组的RTL级片上网络模型连接,进行功能验证。在功能验证无误的基础上,仿真算法在不同网络状态和不同网络负载下的QoS性能指标,并与XY维序路由和DyXY路由算法对比分析算法的性能。最后,在Synopsys的EDA平台对算法进行综合,分析面积和功耗开销。
通过对比分析RTL级仿真获得的平均传输延时、网络吞吐量、链路利用率等QoS性能指标,结果表明论文提出的动态路径分配算法在不同的网络状态下均获得了较优的性能,有效地平衡了网络负载,从而降低了数据包阻塞率,改善了网络中有链路拥塞和故障状态下的性能。
As technology scales down, the design of System-on-Chip encounters some difficult problems: the communication ability can not satisfy the need of system, the overall synchronous clock system is difficult to design, et al. Those problems restrict the scale of IP cores integrated on a sigle chip. Network on chip which based on GALS and packet switching could solve the problems SoC design encounted. Research on routing algorithm is an important branch of NoC research. This article focuses on the research of dynamic routing algorithm for NoC with Quality-of-Service gruarantees, so that it could adjust routing path according to the change of global network states to resolve the problem of network with congestion and failed links.
Frist, we analyze QoS requirements and design a group of performance constraints for NoC routing algorithm. On this basis, we propose a dynamic routing algorithm for specific application. In order to evaluate the performance of the routing algorithm, we design NoC model and the routing algorithm with C language.Then, we simulate the routing algorithm in different communication tasks model to evaluate the distribution of network load. After that, we design the routing algorithm with Verilog HDL, and connect it with NoC system model of our group to evaluate the design. On this basis, we simulate the routing algorithm in different network status and network load to acquire QoS metrics. Then we compare them with XY routing and DyXY routing to analyze the performance of the algorithm. Finally, we synthesize the algorithm on EDA platform of Synopsys to analyze area and power cost.
By comparing and analyzing the QoS metrics we obtained from RTL-level simulation, the results indicate that the routing algorithm proposed in this paper could balance the network load effectively. Thereby, packet congestion probability is reduced and the performance of the network with congestion and failed links is improved.
引文
[1] Shashi Kumar,Axel Jantsch,Juha-Pekka Soininen,et al. A Network on Chip Architecture and Design Methodology. Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI’02),2002.
[2] Luca Benini, Giovanni De Micheli. Networks on chips: a new SoC paradigm. Computer, 2002, 35(1):70~78.
[3]杨晓强.片上网络关键技术研究.微计算机信息,2008,20:173~175.
[4]张浩,张盛兵.片上网络:一种新兴的片上系统设计方法.计算机工程与科学,2009,31(2): 97~99.
[5] Jantsch Axel, Hannu Tenhunen. Networks on Chip. Kluwer Academic Publishers,2003,1.
[6]周干民. NoC基础研究,[博士学位论文].合肥:合肥工业大学,2005.
[7] William J. Dally, Brian Towles. Route Packets, not Wires: on-Chip Interconnection Networks.Proceedings of Design Automation Conference,2001:684~689.
[8] Guerrier P., Greiner A.. A generic architecture for on chip packet-switched interconnections. Proceedings of Design, Automation and Test in Europe Conference and Exhibition, 2000:250~256.
[9] Ville Rantala, Teijo Lehtonen, Juha Plosila. Network on chip routing algorithms.TUCS Technical Report,2006, 8.
[10] Ge Ming Chiu. The odd-even turn model for adapyive routing. IEEE Transactions on Parallel and Distributed Systems,2000: 729~738.
[11] Ming Li, Qing-An Zeng, Wen-Ben Jone. DyXY-A proximity congestion aware deadlock free dynamic routing method for network on chip. Proceedings of Design Automation Conference,2006:849~852.
[12] Glass C.J., Ni L.M.. The turn model for adaptive routing. Proceedings of the 19th Annual International Symposium on Computer Architecture,1992:278~287.
[13] Hu J, Marculescu R. DyAD-smart routing for networks-on-chip. Proceedings of Design Automation Conference,2004:260~263.
[14] Pejman Lotfi-Kamran, Masoud Daneshtalab, Caro Lucas, et al. BARP-A Dynamic Routing Protocol for Balanced Distribution of Traffic in NOCs. Design, Proceedings of Automation and Test in Europe,2008,3:10~14.
[15] Daneshtalab M., Sobhani A, Afzali-Kusha A., et al.NoC Hot Spot minimization Using AntNet Dynamic Routing Algorithm. Proceedings of International Conference on Application-specific Systems, Architectures and Processors,2006,9:33~38.
[16] Dehyadgari M., Nickray M., Afzali-kusha A., et al. Elevation of Pseudo Adaptive XY Routing Using an Objected Model for NOC. Proceedings of the 17th International Conference on Microelectronics,2005:5~12.
[17] Dauto J.A. New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks. IEEE Transactions on Parallel and Distributed Systems,1993,12:1320~1331.
[18] Mohamed M. Sabry, M. Watheq El-Kharashi, Hassan Shehata Bedor.A New Dynamic Routing Algorithm for Networks-on-Chips. IEEE Pacific Rim Conference on Computers and Signal Processing,2007:346~349.
[19]朱晓静.片上网络的结构设计与性能分析,[博士学位论文].合肥:中国科学技术大学,2008.
[20] Mediratta S.D., Draper J.. Characterization of a Fault-tolerant NoC Router. Proceedings of IEEE International Symposium on Circuits and Systems,2007:381~384.
[21] Jie Wu. A Fault-Tolerant and Deadlock_Free Routing Protocol in 2D Meshes Based on Odd_Even Turn Model. IEEE Computer Society,2003.
[22] Chen Kuo-hsuan, Chiu Ge-ming. Fault-tolerant Routing Algorithm for Meshes without Using Virtual Channels.Journal of information science and engineer,1998:765~783.
[23] Jie Wu. A Deterministic Fault-Tolerant and Deadlock free Routing Protocol in 2-D Meshed Based on Odd-Even Turn Model. Proceedings of the 16th international conference on Supercomputing,2002:67~76.
[24]黎黎.片上网络路由算法研究及路由节点的FPGA设计,[硕士学位论文].成都:电子科技大学,2007.
[25]岳培培,刘建,Sheikh Anjum, et al.NoC映射问题中的列举路径分配算法.电子科技大学学报,2008,1(1):54~57.
[26]朱小虎,曹阳,王力纬.多级拥塞控制的NoC路由算法.北京邮电大学学报,2007,10(5): 91~94.
[27]吕勇,赵光宙,苏凡军.基于蚁群算法的自适应动态路径算法.浙江大学学报,2005, 10(10):8350~8353.
[28]刘宝起,王长山,李瑞.NoC中基于蜂群算法的QoS路由.中国集成电路,2009,1:44~48.
[29]张磊,李华伟,李晓维.用于片上网络的容错通信算法.计算机辅助设计与图形学学报,2007,4(4):904~912.
[30]张磊,李华伟,李晓维.一种用于片上容错通信的随机路由算法.第四届中国测试学术会议论文集,2006.
[31]柴松.片上网络拓扑结构研究及仿真平台设计,[硕士学位论文].成都:电子科技大学,2009.
[32]张恒龙,顾华玺,王长山.片上网络拓扑结构的研究.中国集成电路,2007,11:42~47.
[33]常政威,谢晓娜,熊光泽.片上网络拓扑结构.计算机应用,2007,11(11):2847~2850.
[34] ITRS 2001. http://public.itrs.net/Files/2001ITRS/Home.htm.
[35] Lee W.C., Kamat P.. Integrated packet networks with quality of service constraints. Proceeding of Global Telecommunications Conference, 1991:223~227.
[36]王祺,吴宁,葛芬.片上网络仿真与性能评估.全国第19届计算机技术与应用(CACIS)学术会议论文集,2008.
[37]付方发.片上网络性能评估平台设计,[硕士学位论文].哈尔滨:哈尔滨工业大学,2007.
[38]卢强,姚放吾.片上网络的分析与设计.航空计算技术,2007,3(2):127~130.
[39] Palesi M., Holsmark R., Kumar, S.. A methodology for design of application specific routing algorithms for noc systems. Proceedings of the 4th International Conference on Hardware/Software Codesign and System Synthesis, 2006:142~147.
[40] Sudhakar Yalamanchili.并行计算机互联网络技术:一种工程方法.电子工业出版社,2004,4.
[41]詹奇,腾胡宁.网络化芯片.西安:西安交通大学出版社,2007,6.
[42] Zheng Wang, Crowcroft J.. Quality of service routing for supporting multimedia application. IEEE Journal on Selected Areas in Communications,1996,9(7):1228~1234.
[43]刘华阳.网络系统仿真中的流量模型研究.军民两用技术与产品,2006,2:42~43.
[44]付方发,张庆利,王进祥等.支持多种流量分布的片上网络性能评估技术研究.哈尔滨工业大学学报,2007,5(5):830~834.
[2] Luca Benini, Giovanni De Micheli. Networks on chips: a new SoC paradigm. Computer, 2002, 35(1):70~78.
[3]杨晓强.片上网络关键技术研究.微计算机信息,2008,20:173~175.
[4]张浩,张盛兵.片上网络:一种新兴的片上系统设计方法.计算机工程与科学,2009,31(2): 97~99.
[5] Jantsch Axel, Hannu Tenhunen. Networks on Chip. Kluwer Academic Publishers,2003,1.
[6]周干民. NoC基础研究,[博士学位论文].合肥:合肥工业大学,2005.
[7] William J. Dally, Brian Towles. Route Packets, not Wires: on-Chip Interconnection Networks.Proceedings of Design Automation Conference,2001:684~689.
[8] Guerrier P., Greiner A.. A generic architecture for on chip packet-switched interconnections. Proceedings of Design, Automation and Test in Europe Conference and Exhibition, 2000:250~256.
[9] Ville Rantala, Teijo Lehtonen, Juha Plosila. Network on chip routing algorithms.TUCS Technical Report,2006, 8.
[10] Ge Ming Chiu. The odd-even turn model for adapyive routing. IEEE Transactions on Parallel and Distributed Systems,2000: 729~738.
[11] Ming Li, Qing-An Zeng, Wen-Ben Jone. DyXY-A proximity congestion aware deadlock free dynamic routing method for network on chip. Proceedings of Design Automation Conference,2006:849~852.
[12] Glass C.J., Ni L.M.. The turn model for adaptive routing. Proceedings of the 19th Annual International Symposium on Computer Architecture,1992:278~287.
[13] Hu J, Marculescu R. DyAD-smart routing for networks-on-chip. Proceedings of Design Automation Conference,2004:260~263.
[14] Pejman Lotfi-Kamran, Masoud Daneshtalab, Caro Lucas, et al. BARP-A Dynamic Routing Protocol for Balanced Distribution of Traffic in NOCs. Design, Proceedings of Automation and Test in Europe,2008,3:10~14.
[15] Daneshtalab M., Sobhani A, Afzali-Kusha A., et al.NoC Hot Spot minimization Using AntNet Dynamic Routing Algorithm. Proceedings of International Conference on Application-specific Systems, Architectures and Processors,2006,9:33~38.
[16] Dehyadgari M., Nickray M., Afzali-kusha A., et al. Elevation of Pseudo Adaptive XY Routing Using an Objected Model for NOC. Proceedings of the 17th International Conference on Microelectronics,2005:5~12.
[17] Dauto J.A. New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks. IEEE Transactions on Parallel and Distributed Systems,1993,12:1320~1331.
[18] Mohamed M. Sabry, M. Watheq El-Kharashi, Hassan Shehata Bedor.A New Dynamic Routing Algorithm for Networks-on-Chips. IEEE Pacific Rim Conference on Computers and Signal Processing,2007:346~349.
[19]朱晓静.片上网络的结构设计与性能分析,[博士学位论文].合肥:中国科学技术大学,2008.
[20] Mediratta S.D., Draper J.. Characterization of a Fault-tolerant NoC Router. Proceedings of IEEE International Symposium on Circuits and Systems,2007:381~384.
[21] Jie Wu. A Fault-Tolerant and Deadlock_Free Routing Protocol in 2D Meshes Based on Odd_Even Turn Model. IEEE Computer Society,2003.
[22] Chen Kuo-hsuan, Chiu Ge-ming. Fault-tolerant Routing Algorithm for Meshes without Using Virtual Channels.Journal of information science and engineer,1998:765~783.
[23] Jie Wu. A Deterministic Fault-Tolerant and Deadlock free Routing Protocol in 2-D Meshed Based on Odd-Even Turn Model. Proceedings of the 16th international conference on Supercomputing,2002:67~76.
[24]黎黎.片上网络路由算法研究及路由节点的FPGA设计,[硕士学位论文].成都:电子科技大学,2007.
[25]岳培培,刘建,Sheikh Anjum, et al.NoC映射问题中的列举路径分配算法.电子科技大学学报,2008,1(1):54~57.
[26]朱小虎,曹阳,王力纬.多级拥塞控制的NoC路由算法.北京邮电大学学报,2007,10(5): 91~94.
[27]吕勇,赵光宙,苏凡军.基于蚁群算法的自适应动态路径算法.浙江大学学报,2005, 10(10):8350~8353.
[28]刘宝起,王长山,李瑞.NoC中基于蜂群算法的QoS路由.中国集成电路,2009,1:44~48.
[29]张磊,李华伟,李晓维.用于片上网络的容错通信算法.计算机辅助设计与图形学学报,2007,4(4):904~912.
[30]张磊,李华伟,李晓维.一种用于片上容错通信的随机路由算法.第四届中国测试学术会议论文集,2006.
[31]柴松.片上网络拓扑结构研究及仿真平台设计,[硕士学位论文].成都:电子科技大学,2009.
[32]张恒龙,顾华玺,王长山.片上网络拓扑结构的研究.中国集成电路,2007,11:42~47.
[33]常政威,谢晓娜,熊光泽.片上网络拓扑结构.计算机应用,2007,11(11):2847~2850.
[34] ITRS 2001. http://public.itrs.net/Files/2001ITRS/Home.htm.
[35] Lee W.C., Kamat P.. Integrated packet networks with quality of service constraints. Proceeding of Global Telecommunications Conference, 1991:223~227.
[36]王祺,吴宁,葛芬.片上网络仿真与性能评估.全国第19届计算机技术与应用(CACIS)学术会议论文集,2008.
[37]付方发.片上网络性能评估平台设计,[硕士学位论文].哈尔滨:哈尔滨工业大学,2007.
[38]卢强,姚放吾.片上网络的分析与设计.航空计算技术,2007,3(2):127~130.
[39] Palesi M., Holsmark R., Kumar, S.. A methodology for design of application specific routing algorithms for noc systems. Proceedings of the 4th International Conference on Hardware/Software Codesign and System Synthesis, 2006:142~147.
[40] Sudhakar Yalamanchili.并行计算机互联网络技术:一种工程方法.电子工业出版社,2004,4.
[41]詹奇,腾胡宁.网络化芯片.西安:西安交通大学出版社,2007,6.
[42] Zheng Wang, Crowcroft J.. Quality of service routing for supporting multimedia application. IEEE Journal on Selected Areas in Communications,1996,9(7):1228~1234.
[43]刘华阳.网络系统仿真中的流量模型研究.军民两用技术与产品,2006,2:42~43.
[44]付方发,张庆利,王进祥等.支持多种流量分布的片上网络性能评估技术研究.哈尔滨工业大学学报,2007,5(5):830~834.