Journal of Frontiers of Computer Science and Technology ›› 2016, Vol. 10 ›› Issue (6): 811-821.DOI: 10.3778/j.issn.1673-9418.1507041

Previous Articles     Next Articles

Hyper-Graph Partition Algorithms for Heterogeneous 3D Network-on-Chip Floorplanning Optimization

SONG Guozhi+, ZHANG Dakun, MA Jiechao, TU Yao, LIU Chang   

  1. School of Computer Science & Software Engineering, Tianjin Polytechnic University, Tianjin 300387, China
  • Online:2016-06-01 Published:2016-06-07

异构三维片上网络布局优化的超图划分算法

宋国治+,张大坤,马杰超,涂  遥,刘  畅   

  1. 天津工业大学 计算机科学与软件学院,天津 300387

Abstract: Network-on-chip (NoC) is a feasible technology with a large number of embedded cores integrated into a single wafer. Compared with the traditional system-on-chip, it can better meet the challenges of the future need for more large-scale integration of the kernel, resulting in a wider range of applications. However, most of the research is based on homogeneous architecture assuming that all the tiles have the same area. But this assumption is not realistic. Therefore, the research on heterogeneous 3D NoCs is very necessary. With heterogeneous 3D NoCs, a reasonable division of network elements has a significant impact on the performance of heterogeneous 3D NoCs. This paper firstly describes the floorplanning based on 3D NoC of heterogeneous network architecture, and maps VLSI (very large scale  integration) into a hyper-graph, then divides the hyper-graph into multi-levels. Secondly, this paper introduces varivarious of common algorithms in the different phases, analyzes the potential problems of the algorithms, and puts forward several new algorithms to improve the performance of NoC. Finally, a number of simulation experiments are conducted based on a few conventional VLSI data sets to compare the performance of the different phases with different algorithms and choose the best hMetis algorithm framework on the data sets.

Key words: 3D network-on-chip, heterogeneous floorplanning, hyper-graph partition, hMetis

摘要: 片上网络作为一种将大量嵌入式内核集成到单个晶圆片上的可行性技术,与传统片上系统相比,更能应对未来需要更大规模集成内核的挑战,从而得到了更广泛的应用。然而,目前大多数对片上网络的研究是在规则的架构上进行的,即假定所有单元片面积相同,但是这种假设过于理想化。因此,基于异构布局的三维片上网络的研究是非常有必要的,而其中网络单元的合理划分对片上网络的性能有着重要的影响。介绍了基于异构布局的三维片上网络架构,并将超大规模集成网络中的单元映射成一张超图,并且对此超图进行了多级划分。在算法框架的不同阶段,介绍了常见的算法,并且对相应算法的潜在问题进行分析,随后对这几种算法进行改进以提高片上网络的性能。最后,通过对几个常见的超大规模集成单元数据集进行实验分析,比较了不同阶段的算法对该片上网络各个性能的影响,并得出各个数据集上最优的hMetis算法框架。

关键词: 三维片上网络, 异构布局, 超图划分, hMetis