ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (6): 1211-1220.doi: 10.7544/issn1000-1239.2016.20150149

• 系统结构 • 上一篇    下一篇

众核处理器片上网络的层次化全局自适应路由机制

张洋1,2,王达1,叶笑春1,朱亚涛1,2,3,范东睿1,李宏亮4,谢向辉4   

  1. 1(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190);2(中国科学院大学计算机与控制学院 北京 100049);3(河北农业大学信息科学与技术学院 河北保定 071001);4(数学工程与先进计算国家重点实验室 江苏无锡 214125) (zhangyang@ict.ac.cn)
  • 出版日期: 2016-06-01
  • 基金资助: 
    国家“九七三”重点基础研究发展计划基金项目(2011CB302501);国家自然科学基金项目(61332009,61173007,61221062);“核高基”国家科技重大专项基金项目(2013ZX0102-8001-001-001);国家“八六三”高技术研究发展计划基金项目(2015AA011204,2012AA010901)

A Global Hierarchical Adaptive Routing Mechanism in Many-Core Processor Network-on-Chip

Zhang Yang1,2, Wang Da1, Ye Xiaochun1, Zhu Yatao1,2,3, Fan Dongrui1, Li Hongliang4, Xie Xianghui4   

  1. 1(State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190);2(School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049);3(College of Information Science & Technology, Agricultural University of Hebei, Baoding, Hebei 071001);4(State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi, Jiangsu 214125)
  • Online: 2016-06-01

摘要: Mesh和环拓扑结构以其实现简单、易于扩展的特点成为众核处理器片上网络应用最为广泛的拓扑结构.应用于Mesh结构中的健忘型路由算法在网络流量较大时影响片上网络的负载均衡,表现在降低吞吐量和增大数据包延迟.自适应算法中的本地自适应算法和区域自适应算法均存在不同程度的短视现象,不适合大规模的Mesh结构,而目前全局自适应算法又由于路由计算量大而速度缓慢.提出一种新的层次化全局自适应路由机制,包括一个全局拥塞信息传播网络Roof-Mesh和一个层次化全局自适应路由算法(global hierarchical adaptive routing algorithm, GHARA).通过全局拥塞信息传播网络得到拥塞信息,GHARA采用全网分区逐级计算路由的方式,减少了全局路由的计算步骤,从而减少了平均数据包延迟、提升了饱和带宽.实验结果表明GHARA表现优于其他区域和全局自适应路由算法.在人工注入通信模式下,8×8 Mesh平均饱和带宽比全局自适应算法GCA提高10.7%,16×16 Mesh平均饱和带宽比全局自适应算法GCA提高14.7%.在运行真实测试程序集SPLASH-2模式下,数据包延迟最高比GCA提高40%,平均提升14%.

关键词: 众核处理器, 片上网络, 负载均衡, 全局拥塞信息传播网络, 层次化全局自适应路由算法, Roof-Mesh

Abstract: Accompanied by the arrival of the era of big data, data center has been becoming an infrastructure in human life.Many-core processor provides a highly parallel capability to solve applications in data center such as sorting and searching efficiently. For the purpose to utilize the parallelism of many-core processor, routing algorithm in interconnection network turns into one of the most important issues in many-core system. Mesh and ring are the most employed topological structures in many-core processor for their features of easy implementation and high scalability. Depending on the scope of congestion information, routing algorithms in mesh and ring can be divided into oblivious routing, local adaptive routing, regional adaptive routing and global adaptive routing. The oblivious routing algorithm applied in the mesh architecture affects the load-balance of the network which is reflected in reducing through-put and high packet latency. Current local adaptive routing and regional adaptive routing both suffer from short-sightedness and are not suitable for large scale mesh structure. And prior global adaptive routings are limited by the slow computation of global route. We propose a novel global hierarchical adaptive routing mechanism, which is comprised of a global congestion information propagation network Roof-Mesh and a global hierarchical adaptive routing algorithm GHARA. Roof-Mesh provides a platform to share global congestion information in a hierarchical way among all nodes on the network. Depending on the information supplied by Roof-Mesh, GHARA reduces the procedure of routing by hierarchically computing from large region perspective to neighbor nodes. The result of experiment shows that GHARA performs better than other regional and global adaptive routings.

Key words: many-core processor, networks-on-chip, load balance, global congestion information propagation network, global hierarchical adaptive routing algorithm (GHARA), Roof-Mesh

中图分类号: