【作者】 王珂景；

【导师】 钟珞；

【作者基本信息】 武汉理工大学 ， 计算机应用技术， 2010， 硕士

【摘要】 随着半导体工艺技术的发展,集成电路设计者能够将越来越复杂的电路功能集成到单硅片上,并最终在20世纪90年代中期开发出SoC(System on Chip,系统芯片)。SoC代表着集成电路向集成系统转变的大方向。但是,随着SoC中所包含的IP核数目增至成千上万的时候,现有的以总线结构为通信基础的SoC技术面临着在性能、功耗、延时和可靠性等方面的巨大挑战。为了解决复杂SoC所面临的问题,在2001年左右,一些研究机构借鉴和吸收通信网络中的一些思想,提出了以通信为核心的复杂SoC的IP核的集成方法,即片上网络(Network on Chip,NoC).本文的研究工作主要集中在一下几个方面,首先对目前片上网络设计中的路由算法,交换技术,帧传输技术,网络拓扑,映射布局等方面做了详细的介绍。其次,本文提出一种基于贪心思想的映射布局算法,本文集中讨论了几种常用的数据结构方式：0-tree, B*tree,队列结构,Map结构。随着应用负载的形式与种类的不断地增多,0-tree以及B*tree结构无法满足不规则应用负载以及非联通负载的要求。本文算法采用更加灵活的队列结构对映射布局进行建模,使用队列结构移动模块的时间复杂度仅为0(1),旋转模块的时间复杂度为0(n),计算解的质量的时间复杂度为0(a3)。通过Map结构的辅助,计算解的质量的时间复杂度降低为0(a2)。在本文中使用了一些新的技术,如：标志位标示法,动态窗口策略,初始布局优化方法,移动估值矩阵等。标志位标示法解决了Map结构中重叠模块无法分离的问题。动态窗口策略解决了使贪心算法获得全局搜索能力,避免了映射布局算法中陷入局部最优解的问题。初始布局优化以及移动估值矩阵方法为布局算法中的优化技术,通过这些优化技术使算法的收敛速度加快。通过实验看出,改进后的贪心布局算法比较目前较为常见的模拟退火算法,运行时间降低了70%左右,解的质量提升7%左右。并且根据对迭代数据的追踪发现,改进后的贪心布局算法更为高效,稳定。更多还原

【Abstract】 As development of semiconductor process technology, IC designers can integrate more and more complex circuit functions into a single silicon wafer, and ultimately the SoC (System on Chip) was developed in the 20th century. SoC represents the development of integrated circuits. However, as the number of IP core of SoC increased to more than thousands, bus-based SoC communication technology faces enormous challenges in performance, power consumption, delay, and reliability. In order to solve problems complex SoC faced, in 2001, some research institutions refer to the traditional network and propose a integrated method of complex SoC that focus on communication. It is NoC (Network on Chip).My research focuses on following aspects, first of all some technology was presented,such as the current routing algorithm, switching technology, the frame transmission technology, network topology, mapping and layout. Secondly, a mapping algorithms based on greedy was proposed in the paper. Several common data structures were compared in the paper.such as O-tree, B* tree, queue structure, Map structure. With the type of application module constantly increasing, O-tree and B* tree structure can’t express the irregular application module and non-unicom application module. So the algorithm uses a more flexible queue structure to express application module. when the queue structure was used, the time complexity of moving the module is O (1) in the algorithm, rotating the module is O (n), Calculating the quality of the layout is O (a3). If the Map structure were used for assisting my algorithm, the time complexity of Calculating the quality of the layout reduces to O (a2).In addition, some new techniques were introduced to improve efficiency of this algorithm, such as:Marker bit method, dynamical selection and weight matrix, Initialize the layout. In order to solving overlapping and connection problems,Marker bit method is proposed in this paper to merge and separate different modules. Through the dynamical selection, Greedy has an ability of global selection which avoid to get local solution. Initial layout optimization and weight matrix make Greedy more efficient. From the experiments and comparison with Simulated Annealing algorithm, the running time reduce about 70%,the quality of solution increases about 7%.on the other hand, through tracking those algorithm,improved Greedy algorithm shows better stability and accuracy.更多还原