摘要
Mesh和环拓扑结构以其实现简单、易于扩展的特点成为众核处理器片上网络应用最为广泛的拓扑结构.应用于Mesh结构中的健忘型路由算法在网络流量较大时影响片上网络的负载均衡,表现在降低吞吐量和增大数据包延迟.自适应算法中的本地自适应算法和区域自适应算法均存在不同程度的短视现象,不适合大规模的Mesh结构,而目前全局自适应算法又由于路由计算量大而速度缓慢.提出一种新的层次化全局自适应路由机制,包括一个全局拥塞信息传播网络Roof-Mesh和一个层次化全局自适应路由算法(global hierarchical adaptive routing algorithm,GHARA).通过全局拥塞信息传播网络得到拥塞信息,GHARA采用全网分区逐级计算路由的方式,减少了全局路由的计算步骤,从而减少了平均数据包延迟、提升了饱和带宽.实验结果表明GHARA表现优于其他区域和全局自适应路由算法.在人工注入通信模式下,8×8 Mesh平均饱和带宽比全局自适应算法GCA提高10.7%,16×16Mesh平均饱和带宽比全局自适应算法GCA提高14.7%.在运行真实测试程序集SPLASH-2模式下,数据包延迟最高比GCA提高40%,平均提升14%.
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 ina hierarchical way among all nodes on the network.Depending on the information supplied by RoofMesh,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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2016年第6期1211-1220,共10页
Journal of Computer Research and Development
基金
国家“九七三”重点基础研究发展计划基金项目(2011CB302501)
国家自然科学基金项目(61332009,61173007,61221062)
“核高基”国家科技重大专项基金项目(2013ZX0102-8001-001-001)
国家“八六三”高技术研究发展计划基金项目(2015AA011204,2012AA010901)~~
