计算机04-6724关于异构片上网络布图优化问题研究

毕业设计（）开题报告

2015324学计算机学专计算机科学技班计算题关于异构片上网络布图优化问题的研指导教一、与本课题有关的国内外研究情况、课题研究的主要内容、目的和意义1.片上网络NoC（networkonchip）是一种新的系统体系结构，其思想是将计算机网过长、连线延迟、功耗开销等一系列相关问题。于此同时，3DIC技术日趋完善，并备受瞩目。因此，将上述两种技术融合形成的3DNoC技术应运而生。其充分结合了上述技术各自的优势，用三维架构实现多核间互连，以获得更好的性能。国内方面，的何鸥，在他的博士[1]中，过将布图和其他设计阶段相结合，长优化水平相近的情况下，缓冲器的也是提高互连性能的重要。理工大学的，在他的[2]，提出现代布图规划问题已经从传统的、简单的布图规划问题向具有各种*-ree示法。该优化算法可以动态的将随机产生的解有效、快速的转化为合法解从而大大提高了搜索效率而不是采用惩罚函数法复旦大学的在她的[3]中，究了传统的平面布图规划问题,束条件下的平面布图规划问题以及基于平面布图规划的电源布线。在传统的平面布图规划问题研究中,提出了模拟退火的加速策略。在模拟退火的加速策略研究中,针对领域构造对模拟退火算法的影响进行研究分析,并在此基础上根约束的平面布图规划算法以及考虑模块电压降的平面布图规划算法。理工大学的，在他的[4]中，出了基于传递规约无环图的三维布图规划技术3-TR可以根据特定应用优化三维片上网络中模块的布局,从而使功耗更低文中3D-TRG三维布图规划表示法可以表示几乎所有的布局结构,而且具有表达两两模他的[5]中，提出了布图规划与多供电网络的协同设计方法，将电源网络电压降的分析步骤验结果表明算法在优化面积、线长的基础上，能有效降低模块温度。个在层内通信，这样使的通信性能有了很大的提高。。。vnoc3，有一定的编程基础及查阅国内外相关领域文献的能力。意指导教师年月日学院意主管年月日工业大学毕业设计 ）成绩考核学学院名专业班题1．毕业设计）指导教师评语及成绩成绩指导教师签字年月日2．毕业设计）答辩评语及成绩成绩答辩（或组长）签字年月日3．毕业设计）总成绩a.b.c.Withtherapiddevelopmentofintegratedcircuitmanufacturingprocesses,problemofpoorsystemscalabilitythatSoC(SystemonChip)faceshas increasinglyprominent.Tosolvetheseproblems,networkonchipNoC(NetworkonChip)emergedasanewkindofon-chipcommunicationmode.Withthedevelopmentofnetworkonchip,itsresearchhasexpandedfromtwo-dimensionaltothree-dimensionalspace.3Dnetworkonchipisacollectionof3Dintegrationtechnologyandnetworkonchip,anditinheritstheiradvantagesandmeetsthedevelopmenttrendofchipfunctionaldiversity.Thisdissertationpresentsanimprovedfloorplanningoptimizationalgorithmbasedonsimulatedannealingalgorithm(ImprovedSimulatedAnnealing,hereinafterreferredtoasISAalgorithm)toreplacetheoriginalfloorplanningoptimizationalgorithmbasedonsimulatedannealingalgorithm(SimulatedAnnealing,hereinafterreferredtoasSAalgorithm)tomakeitmoreapplicabletothethree-dimensionalnetworkonchipsimulation.ThisdissertationdescribestheISAalgorithm’simprovementideasandusesanexisting3Dnetworkonchipsimulatortogetonasimulationtest,theresultsshowthattheproposedISAalgorithmisbetterthantheoriginalSAalgorithmanditismoresuitableforsimulationofthree-dimensionalnetworkonchip.Keywords:SystemonChip;3DNetworkonChip;FloorplanningOptimization;SimulatedAnnealingAlgorithm本章小 第五章结论和展 结 展 参考文 附 谢 1.1.2本课题研究的目的和意随着集成电路制造工艺的飞速发展，IP核数目的不断上升，单个的集成度也越来越大[16]。尽管SoC遇到的可扩展性差、时钟同步比较、总线结构资源利用率较问题，都已经被2DNoC解决，但是信号传输产生延迟和失真、面积增大以、功耗开销以及散热等难题依然没有得到有效的解决。随着3D集成技术的产生，改进了的平面布局，减小了的面积与功耗开销。因此，3DNoCNoC3DNoC中，IP核数目众多，因此合理的布局IP结点将具有降低延时、减小面积、减小功三维片上网络国内外研究现国内研究现2003年才开始的，而对三维片上网以看出，最近几年国家自然科学基金对三维片上网络资助的力度越来越，。的何鸥在其博士[18]中，针对片上网络传统总线的互连优化，他提出把缓冲器到中，这样可以提高互连性能。而且他还利用最小度优先算法，把布图的拓扑结构和模块之间的几何结构都进行了优化。随着IP核数量的增加，结点之间的通信量也逐渐增加，针对总线如何布线才能提高系统互连的问题一个新的算法，在算法中增加扰动函数，对布图优化后产生的结果进行扰动，从而进一步提高互连性能。复旦大学的，在其硕士[19]中，针对传统布局规划问题、电源布线问题和布局规划中新的约束条件，分别提出了模拟退火加速策略、快速分析电源网络的计算方法以及SoC约束的平面布图规划算法。理工大学的，在其[20]中针对片上网布局，进一步降低了片上网络的总功耗，提升了片上网络的吞吐量理工大学的，在其[21]中，针对复杂的、带有各种约束的布图规划问题，，。。使空间更加的连续。而且一种新的优化算法，可以把通过扰动策略产生的划分方法被他提出来了。第二阶段，为了减轻计算复杂度，他提出转换器和网络接口时，分别运用启发式方法和最小代价流方法大学的，在其[23]中提出了一个分层基于分布式群集的3DNoC架构，以提高3DNoC的整体性能。该体系结构包括一个全局网络和集群两部分，使用分组交的，在其[24]中，针对TurnModel模型设计了无死锁的确定性的路由算法，实验表明，该算法由于避免了以前经典的XY路由算在一个相同学的，在其博士[25]中，针对片上网络拓扑结构和通信方法两个方向3DNoC3DNoC上的拓扑结构，并针对每种架构设计出与之对应的路由算法。。1-13DNoC三维片上网络关键设2015-2018-2015-2018-2014-热/究2016-基于多级裂变2013-学2016-三维片上网络体系结2012-2015-2012-2014-2012-TSV学2014-2011-学2013-三维片上网络(3DNoC)2009-2011-国外研究现由于3DNoC的研究起步较晚，所以有关3DNoC的第一篇[26]在2005年，由KangminLee、Se-JoongLee等人的。目前在国外，仅仅有十几个团队在研究3DNoC。这些团队主要集中在的一些大学，如加利福尼亚大学、大学、州立大学等。VitordePaulo，CristinelAbabei在其[27]2.5D的片上网络结构，这种结构可以在异构的平面布局VitordePaulo，CristinelAbabei在其另外一篇[28]中，提出了3D片上网络结构，这种结构可以在一个分离层或者在一个异构的平面布局层利用同构的规则的mesh网络。Srinivasan.K，Chatha.K.S和Konjevod.G在其[29]中提出了一种混合整数线NoC架构，这种技术的优化目的是减小功率消耗，为此提出了一Yuan-LongJeang3DNoC的拓扑结构设计方面做了很多的贡献，他出，使结点之间的通信速度加快了，功耗也减小了[30]。WalidLafi等人针对其他3Dmesh结构下吞吐量较小、延迟较大等问题，在[31]中提出了一种新的路大的提高。K.Somasundaram在研究网络拓扑和路由技术上做出了很大贡献，在耗和分组延时等方面表明作者两种架构比起现有的经典架构性能上有显著的改善。SrinivasanMuraliGiovanniDeMicheli3DNoCNMAP种单个路径路由和分段路由选择[33]ParthaPratimPande等人在关于3DNoC的低功耗编码方式上做出了很大贡献，他们在[34]中表明减少能源消耗的最重要一点就是要在系统设计阶段解决地址完整性的问题，于是他们把CAC和MECs联系起来提出来一种支持纠错和能力强的编码方式与原来的2DNoC相应的方式比较，这种方式很大程度上减小了功耗。主要内容与文章结、随着超大规模集成电路的发展，集成电路的复杂度越来越高，IP核的数目不断增加，二维片上网络遇到了功耗增大、散热面积增大等一系列难此三维片上网络引起了国内外众多科研机构的由于三维片上网络的研究起模拟退火算法布局优化算法。通过利用NorthDakotaState大学的教授、第三章介绍了改进后的模拟退火算法主要介绍了改进的方案的第二章遗传算遗传算法的20世纪60年代末70年代初密歇根大学的JohnH.Holland教授及其学生首次提出了遗传算法。在《自然与人工系统的自适应性》一书中，Holland系DeJongGoldberg遗传算法的基本思得适应值最好的作为问题的最优解。遗传算法的具体步骤和流程用来表示种群内的每个对生存环境的适应度也就是说每个都会有一个规定适应值为非负这是为了能够直接的将适值函数与群体内的优劣性联系起来，所以在任何情况下，希望适应值越大越好代之后，得到的适应值最好的对应的解即被认作是问题的最优解。2-12-1粒子群优化算粒子群优化算法的Reynolds和Heppner两位动物学家在1987年和1990年的中都关保证了这些同步的行为。后来，KennedyEberhartHepper的模仿鸟群的模粒子群优化算法的基本思D维搜索空间中飞行。每个粒子有一个速度值来决定他们的位置（状态，也粒子群优化算法的具体步第五步：根据公式（2.1）和（2.2）本章小本章第一节先是介绍了遗传算法的，它是由JohnH.Holland教授及其学生首次，其次介绍了遗传算法的基本思想，最好写出了具体操作的步骤，并给出了流程图；第二节先是介绍了粒子群优化算法的，其次介绍了粒子群第三 一种改进的基于模拟退火的三维片上网络布局算一般的模拟退火算模拟退火算法模拟退火算法（SimulatedAnnealingSA算法）是一种随机性求解的方法，主要用于寻找组合优化问题的最优解[35]。SAMetropolis[36]在二十年代，在求解组合最优化问题时，Kirkpatrick[37]SA引入到了该问题中，从而SA算法。模拟退火算法的基本思MetropolisSA算法。因此，我SA算法的思想就是通过模仿热力学中的退火过程，使其与一般优化问题结SAMetropolis准则。MetropolisSAMetropolisTi产生一个扰动，通过状态函数产生一个新的状jMiMjMi>Mj，就把新状态作为当前的状态，否则的话以一定的概率来判断是否把新状态作为当前的状态。SA算法Metropolis准则的抽样策略，在每个温SA算法是一种启发式的随机搜索方法[38]，在搜索策略上与传统的随机搜索方模拟退火算法的具体步骤和流程第一步：通过扰动函数产生一个初始解x0f(x0)，并设置一个初始控制温度T0第二步：在可行解空间中再通过扰动函数次随机产生一个新解x1，并计算其f(x1)，算出△f=f(x0)-f(x1)。SA3-1改进的模拟退火算改进策（1）maxstep（maxstep是一个经过多次实验取得的最（2）（3）改进后的模拟退火算法的具体步骤和流程第一步：通过扰动函数产生一个初始解x0，通过目标函数计算它的对应值f(x0)T0。f(x1)，算出△f=f(x0)-f(x1)，转向第四步。f(x1)，然后取前一个温度找到的最优解xbest，算出 =f(xbest)-f(x1)。3-1SA<准则判断是否接受，若接受，则把x1作为当前解,设置q=0，f=1,若不接受，则让x0继续作为当前解，且+1,qflag==0，则重ISA3-2本章小本章第一节介绍了模拟退火算法的和发展历程，该算法是由Metropolis首先，然后Kirkpatrick将该算法首次用于实际问题中；其次详细介绍了3-2ISA第四章仿真实验设C仿真系统进行的，其主要原因是以现在的环境来看，专门设计一个实际的来验证算法的优劣是不太现实的。特别是随着集成电路制造工艺技术的发展IP核数量不断增加3DC架构的设计异常复杂设计出一个3D所花的时间较长而且设计的成本较高。因此，本文采用的是由aeCristieli研发27的仿真器来检验本文所ISA算法的优劣。vnoc3是一个用来仿真三维片上网络架构的仿真器。Software.html这个提供了这个仿真器的源程序该仿真器是由CristinelAbabei教授经过几年的努力C++语言在Linux系统下开发的。它可以在Fedora8中运行，也可以在Windows中运行。CristinelAbabei教授把该仿真器的源代码放在了个人上，鼓励其他研究者对其进行修改，期望进一步改进该仿真器。vnoc3的运行环境配4-1所示。4-1vnoc3使用的平台的参数选 参数CPU配置

(R)Core(TM)2QuadCPUQ9400@ATIRadeonHD4650VMwareWorkstation8Fedoragcc4.6.020110428RedHat4.6.0-6)6个测试用4-2IP核的数量和直接拓扑结构的大小。CristinelAbabeiMCNC测试用例的启发，然后构造出这六个4-2IP核的比核的比R8vnoc3是通过指令：./sfrafile:(testfile)cycles:(int)warmup:(int)[Options...]4-3中，作者列举了一些常用令参数及其含义。4-3vnoc3参 参数的意义与取值范

160架构的选择，2.5D代表两层架构，3D代表三层架构disabled调整注入负载（10%-100%10的倍数增加），100%在注入负载的范围（10%-100%）disabled缓存尺寸的范围（1x5x）disabled实验结果分为了验证本文ISA算法是否比原有的SA算法在性能上更加优化作vnoc3CPU运行时间（CPUprocessprtime(s)、平均微片延迟（averageflitlatency(s)）和吞吐量（throughput(flit/s)）进行了统计，通过比较这面的数据变化来衡量算法的优劣。对于同一条指令，CPU运行时间越短，平均微片延迟越小，吞拟信道这来观察两个算法在上述面性能的情况为了把实验结果的误差降到而且本文所有的实验都是在循环1000次之后，才开始收集实验数据的，设置改变测试用CristinelAbabeivnoc3提供的六个测试用apte，xeroxhpIP核数量少且拓扑结构较小，因此决apte，xeroxhpIP核数量较少的网络ami25，ami33ami49IP核数量多且拓扑结构ami25，ami33ami49IP核数候，应该保证其他参数不变，这里作者选择注入负载为50%和100%两种，虚拟CPU4-1，4-24-1100%4-250%4-14-2IPapte、xerox中，ISASACPU运行时间上没有太大的变化，基本上趋于IPIP10的时候，本文提ISACPUSAIP核数量越多，ISACPU运行时间上的优势就越突出。所以作者得出结CPU运行时间这个性能上，ISASAISA算法IP核数量多且拓扑结构较大的网络架构。4-34-44-3100%IP核数量较少时，即在aptexeroxIP核数量稍微增加时，hp、ami25中，ISASAIP核数33ami33ami49中，SAISA4-3100%4-450%IP核数量稍微增加时，ISASAIP核数量较少或较多时，即在测试用4-450%xerox、ami33、ami49，SAISA算法。所以得出结论，在平均微片延迟这个性能上，本文ISA算法比SA算法更适用于IP4-54-64-5100%通过观察图4-54-6，可以看出，注入负载为50%的时候IP核数量较吐量高于SA算法。当IP核数量大于33个时，两种算法的吞吐量没有明显的变化，趋于稳定。注入负载为100%的时候，当IP核数量较少时，ISA算法的吞吐量略低于SA算法的吞吐量。随着IP核数量增加，ISA算法的吞吐量高于SA算IP49个时，两种算法的吞吐量没有明显的变化。SAIP核数量较少或较多的测试用例中，两种算法的差距不明显。由此表明本文ISA算法比原有的SA算法更适用于IP核数量适4-650%改变虚拟信CPU运行时间、平均微片延迟和吞吐量方面的变化。4-7IPaptexeroxhpIP核数量较少的一组测试用例随着虚拟信道CPU4-7ami25、ami33ami49IP核数量较多的一组测试用例随着虚拟信道数的变化，两种CPU4-8所示。4-8IP4-7aptexerox在仿真时，ISA算法的运SAhp在仿真时，ISA算法的运行时间明显小SA4-8看出，IPami25、ami33和ISACPUCPU运行时间测试用例aptexerox和hp，即IP核数量较少的一组测试用例随着虚拟信道数的变化，两种算法平均延迟的变化比较如图4-9所示。测试用例ami25、ami33ami49IP核数量较多的一组测试用例随着虚拟信道数的变化，两种算法4-10所示。观察图4-9，可以看出，测试用例apte和xerox在仿真时，随着虚拟信道数的增加，ISASAhp在4-9IP4-10ami25ISA4-10IP算法的平均延迟略低于SA算法的平均延迟，而测试用例ami33在仿真时，两种IP核数量最多的测试SA算法的。测试用例aptexerox和hp，即IP核数量较少的一组测试用例随着虚拟信道数的变化，两种算法吞吐量的变化比较如图4-11所示。测试用例ami25、ami33ami49IP核数量较多的一组测试用例随着虚拟信道数的变化，两种算法4-12所示。4-11IP4-11可以看出，随着虚拟信道数的增加，IP核数量较少的三个测试用apte、xeroxhp的吞吐量在逐渐减小。对于aptexerox这两个测试用例而言，在每一个虚拟信道上，ISASAhp这个25时，SAISA算法,而在其他虚拟信道，ISA算法在吞吐量方面优于SA算法。从图4-12看出，随着虚拟渐减小。对于ami25和ami49这两个测试用例而言，在每一个虚拟信道上，ISASAami3324时，SAISA算法，在其他剩余的虚拟信道上，ISASA算法。4-12IP平均微片延迟和吞吐量这三个方面的性能上，ISASA算法好，特别是在CPU运行时间这个性能上，ISA算法的优化效果更加明显。改变注入负20%100%CPU运行aptexeroxhpIP核数量较少的一组测试用例随着注入负载CPU4-13ami25、ami33ami49IP核数量较多的一组测试用例随着注入负载量的增加，两种CPU4-14所示。4-13IP4-134-14可以看出，对于每一个测试用例而言，随着注入负载的增加，CPU运行时间的变化基本不明显，趋于平稳。ISAapte4-14IPxerox、ami25ami33SAISAami49SAaptexeroxhpIP核数量较少的一组测试用例随着注入负载4-15ami25、ami33ami49IP核数量较多的一组测试用例随着注入负载量的增加，两种4-16所示。4-15IP4-154-16，可以看出，注入负载的多少对于算法的平均延迟影响hp在注入负载20%增加到70%的时候，平均延迟缓慢增加，增长率很低，而注入负载达70%hpISAhp的平SA4-16上来看，IP核数量较多的三个测试用例在20%60%时候，平均延迟增长平缓，且增长率低。当注入负载60%ami49，增长最快。测试用例ami25和ami33在负载超过的平均延迟上，ISA算法的性能略优于SA算法。而测试用例ami49在超过的平均延迟上，SA算法ISA算法。所以，从总体来看，ISA算法在改变注入负载影响平均延SA算法。4-16IP4-17ami25、4-17IPami49IP核数量较少多的一组测试用例随着注入负载量的增加，两种算4-18所示.4-18IP4-174-18，可以看出，总体趋势上，随着注入负载量的增加，吞吐量呈现逐渐上升的趋势。观察图4-17，可以看出，IP核数量较少的三个测试ISASA4-18，可以看出，测试用例ami25ISASAami33和ami49，体的趋势，得出结论，随着注入负载量的增加，ISASA算CPU运行时间、平均微片延迟和吞吐量这三个方面的性能上ISA算法比SA算法好特别是在CPU运行时间这个性能上，ISA算法的优化效果更加明显。改变缓存尺测试用例aptexeroxhp随着缓存尺寸的增加ISA算法和SA关于平均延迟的变化比较如图4-19所示。测试用例ami25、ami33ami49随着缓存尺寸的ISASA4-20所示。4-19IP4-194-204-20IP4-19上来看，IPaptexerox下的两种算法的平均延迟几乎是没有变化的。但是测试用例hp下的ISA算法的平均延迟明显低于SA算法。从图4-20来看，测试用例ami25下的ISA算法的平均延迟低于SA算法。测试用例ami33下的两种算法的平均延迟几乎是一样的。而测试用例ami49下的ISA算法的平均延迟略高于SA算法。因此，从总体上来看，ISA算法在IPSA算法。测试用例aptexeroxhp随着缓存尺寸的增加ISA算法和SA关于吞吐量ISASA4-22所示。4-21IP4-214-22，可以看出，对于同一个测试用例而言，从总体的趋4-21来看，IP核数ISASA4-22来看，ami25ISASAami33和ami49下的两种算法的吞吐量基本保持不变。因此，从总体上来看，ISA算法在SA算法。4-22IP这两个方面的性能上，ISASA算法好。本章小CPU运行时第五章结本文利用vnoc3仿真器，对两种算法进行了仿真实验，通过收集到的CPU运行时间、平均微片延迟和吞吐量这三个方面展文用到的六个测试用例，最大的IP核数量是49个，而现在的IP核数量已经达到了数亿个，为了使实验得出的结论更加具有说服力，增加测试用例的IP总而言之，集成电路制造工艺的迅速发展，IP核数量的不断增加，使得芯3DNoC技术也会得到越来越快的发展。参考文 .3D片上网络拓扑与路由的研究[D].西安电子科技大学, .SoC技术简述[J].水利水电学院学报,2006, 夏国宏,.SoC技术及其相关问题的探讨[J].黄石理工学院学报,2012,28(3):6-:: .片上网络及路由器研究[D].华东师范大学,YeTT,BeniniL,DeMicheliG.PacketizedOn-ChipInterconnectCommunicationysisForMpsoc[J].Proc.DesignAutomationandTestinEurope,2003:10344.WingardD.MicroNetwork-BasedIntegrationforSOCs[J].ProceedingsofDesignAutomationConference,2001:673--677.FurberS,BainbridgeJ.FuturetrendsinSoCinterconnect[C]//VLSIDesign,AutomationandTest,2005.(VLSI-TSA-DAT).2005IEEEVLSI-TSAInternationalSymposiumon.IEEE,2005:183-186.BeniniL,MicheliGD.NetworksonChips:aneradigmforcomponent-basedMPSoCdesign[J].ProcMpsoc,2004.DallyWJ,TowlesB.RoutePackets,NotWires:On-ChipInterconnectionNetworks[C]//DesignAutomationConference,Proceedings.IEEE,2001:684-689..3D-Mesh片上网络服务质量保证机制研究[D].电子科技大学LeeHHS,ChakrabartyK.TestChallengesfor3DIntegratedCircuits[J].Design&TestofComputersIEEE,2009,26(5):26-35.LiuCC,ChenJH,ManoharR,etal.Mapsystem-on-chipdesignsfrom2-Dto3-DICs[C]//CircuitsandSystems,2005.ISCAS2005.IEEEInternationalSymposiumon.IEEE,2005:2939-2942Vol.3..低功耗3DNoC综合设计优化算法研究[D].理工大学,李磊.片上网络NoC的通信研究[D].浙江大学电气,.三维片上网络拓扑结构与容错机制研究[D].航空航天大学,何鸥.互连驱动的片上系统布图规划算法的研究[D].,SoC平面布图规划算法的若干研究[D].复旦大学.基于布图规划的三维片上网络功耗优化与仿真[D].理工大学,.带约束的VLSI布图规划算法的研究[D].理工大学,宋斌杰.基于划分的低功耗NoC设计算法[D].理工大学,.3DNoC研究[D].大学,.NoC路由算法及仿真模型的设计与研究[D].合肥工业大学,2009.::.面向实时复杂系统的片上网络架构及技术研究[D].电子科技大学,LeeK,LeeSJ,KimD,etal.Networks-on-chipandNetworks-in-PackageforHigh-PerformanceSoCPlatforms[C]//AsianSolid-StateCircuitsConference,2005.IEEE,2005:485-488.PauloVD,AbabeiC.AFrameworkfor2.5DNoCExplorationUsingHomogeneousNetworksoverHeterogeneousFloorplans[C]ReconfigurableComputingandFPGAs,InternationalConferenceon.IEEE,2009:267-272.PauloVD,AbabeiC.3DNetwork-on-ChipArchitecturesUsingHomogeneousMeshesandHeterogeneousFloorplans[J].InternationalJournalofReconfigurableComputing,2010,SrinivasanK,ChathaKS,KonjevodG.Linear-programming-basedtechniquesforsynthesisofnetwork-on-chiparchitectures[J].IEEETransactionsonVeryLargeScaleIntegrationSystems,2006,14(4):407-420.JeangYL,WeyTS,WangHY,etal.Mesh-TreeArchitectureforNetwork-on-ChipDesign[C]ProceedingsoftheSecondInternationalConferenceonInnovativeComputing,InformatioandControl.IEEEComputerSociety,2007:262.LafiW,LattardD,JerrayaA.Anefficienthierarchicalrouterforlarge3DNoCs[C]RapidSystemPrototy(RSP),201021stIEEEInternationalSymposiumon.IEEE,2010:1-ViswanathanN,ParamasivamK,SomasundaramK.Performanceysisofclusterbased3DroutingalgorithmsforNoC[C]RecentAdvancesinInligentComputationalSystems(RAICS),2011IEEE.IEEE,2011:157-162. MuraliS,DeMicheliG.Bandwidth-constrainedmapofcoresontoNoCarchitectures[C]Design,AutomationandTestinEuropeConferenceandExhibition,2004.Proceedings.IEEE,2004:896-901Vol.2.PandePP,GangulA,FeeroB,etal.ApplicabilityofEnergyEfficientCodingMethodologytoAddressSignalIntegrityin3DNoCFabrics[C]Proceedingsofthe13thIEEEInternationalOn-LineTestingSymposium.IEEEComputerSociety,2007:161-166.MetropolisN,RosenbluthAW,Rosenbluth.MN,lerAH,lerE:Equationofstatecalculationsbyfastcomputingmachines[J].JournalofChemicalPhysics,1953,KirkpatrickS,JrGC,Mp.V.OptimizationbySimulatedAnnealing[J].Science,1983,.模拟退火算法在Web服务中的应用[J].计算机技术与发展,2006,ZeineldinRA.Animprovedsimulatedannealingapproachforsolvingtheconstrainedoptimizationproblems[C]//InformaticsandSystems(INFOS),20128thInternationalConferenceon.IEEE,2012:BIO-27-BIO-31.,.一种改进的模拟退火算法[J].计算机技术与发展,2009,19(6):32-::.基于3D-MESH的CMP片上网络方法研究[D].工业大学,附录毕设期间参与科研项目和研究成参与科研项 参与纵向课题国家自然科学（基于多级裂变模型的3DNoC拓扑结构的研究，61272006毕设期间研究成 基于改进模拟退火算法异构三维片上网络的布图优化。理论计算机科附录Ⅱ文献翻英文原Withtherapiddevelopmentofintegratedcircuitmanufacturingprocess,thenumberofIPcoreofeachchiphasreachedbillionsandhasbeengrowing,two-dimensionalnetworkonchipsolvesaseriesofproblemsthatsystemonchipfacesthesynchronousglobalandsoon,buttwo-dimensionalnetworkonchip’slayoutisconfinedbyflat,hampersthepromotionofsystemperformanceandscale,andcannotavoidpoweroverhead、wiringdelayandotherrelatedissues.Becausethree-dimensionalnetworkonchip’sstructureisvertical,itsadvantagescan challengesfacingtwo-dimensionalnetworkonchip,three-dimensionalnetworkonchiphasadvantagesofanti-jammingcapability、lowerlatency、reducingpowerconsumption,、reducingtheumpathlengthandsoon.Asaresultofbiggeradvantages,three-dimensionalnetworkonchipquicklyattractestheattentionofdomesticandforeignresearchinstitutions.Abroad,VitordePaulo,CristinelAbabeiVitorproposedanew2.5DNoCarchitecturethatusesahomogeneousnetworkononelayerontopofaheterogeneousfloorplanninglayer.Thepurposeofthisapproachistoexploitthebenefitsofcompactheterogeneousfloorplansandregularmeshnetworksthroughanautomateddesignspaceexplorationprocedure.Andinanotherpaper,VitordePaulo,CristinelAbabeiVitorproposednew3D2-layerand3-layerNoCarchitecturesthatutilizehomogeneousregularmeshnetworksonaseparatelayerandoneortwoheterogeneousfloorplanninglayers.Srinivasan.K，Chatha.K.SandKonjevod.GpresentednovelmixedintegerlinearprogrammingformulationsforsynthesisofcustomNoCarchitectures.Theoptimizationobjectiveofthetechniquesistominimizethepowerconsumptionsubjecttotheperformanceconstraints.Theypresentedatwo-stageapproachforsolvingthecustomNoCsynthesisproblem.Inthestage,theyaddressedthefloorplanningproblemthatdeterminesthelocationsofthevariouscoresandtherouters.Inthesecondstage,theyutilizedthefloorplanfromthestagetogeneratetopologyoftheNoCandtheroutesforthevarioustrafficDomestically,HeOu,whoisastudentofTsinghuaUnversity,inhisdoctoralpaper,withrespecttointerconnectiontooptimizethenetworkoftraditionalnetworkonchipbus,presentedcorrespondingoptimizationalgorithms.Againstthetraditionallineofnetworkoptimizationproblems,hewasinspiredbythoughtofsolutionoftheequation.Anewsetboundariesfloorplanningalgorithmshavebeenproposed.Forcasessimilarlinelengthoptimizationlevel,heproposedtheinsertionbuffer,whichcouldimproveinterconnectperformance.ChenShanshan,whoisastudentofFudanUnversity,inhermaster’spaper,accordingtotraditionalfloorplanningproblem,powercablingproblemsandfloorplanninginthenewconstraintsissues,proposedtoacceleratethestrategysimulatedannealing,rapidysisandcalculationmethodofthesupplynetworkandfloorplanningalgorithmconstrainedSoC.ZhengFei,whoisastudentofWuhanUniversityofTechnology,inhismaster’spaper,accordingtonetworkonchip’sspecificapplication,proposedthree-dimensionalfloorplanning’stechniques,therebyreducingpowerconsumption.Thispointofview,althoughthecountryhasbeguntostudythree-dimensionalnetworkonchip’sfloorplanning,thisissuestartedlate,lessresearch,whichshowsthree-dimensionalnetworkofchip’sfloorplanninghasalotofresearchspacetobeexcavated.Therefore,onthebasisoftheexistingsimulatedannealing,thispaperimprovesthethreeaspects.Thesesolutionsaretoincreasecomparisonoftheoptimalsolution,setthresholdsandwarmed.Thusimprovedoptimizationalgorithmbasedonsimulatedannealingfloorplanningreplacedtheoriginaloptimizationalgorithmbasedonsimulatedannealingfloorplanning.Thepartdescribesthetraditionalsimulatedannealingalgorithm,thesecondpartintroducestheimprovedmethod,thethirdpartconcludesbysimulation,thefourthpartistheconclusion.Simulatedannealingalgorithmisacommonrandomsearchalgorithmandisanextensionofthelocalsearchalgorithm.SAispresentedbyMetropolisin1953,andin1983,SAisappliedincombinatorialoptimizationproblemsbyKirkpatrick,whichreallycreatedthemodernSAalgorithm.ThebasicideaofSAalgorithmderivedfromthermodynamicsannealingprocess. Thermodynamicsannealingprocessisdividedintoheating,isothermalandcooling.Heatingprocessisheatingthesolid.Afteritreachesacertaintemperature,allmoleculeswillmoveinthestatespace.Distributionofmoleculesisfromtheorderedstateintoastateofdisorder,sothatsubsequentcoolingprocessstartswithacertainequilibrium.Isothermalprocessistoensurethatthesystemineachofthetemperaturereachesequilibrium,andreachessolidgroundstateeventually.Thecoolingprocessgraduallydecreasesfromasolidhightolowtemperature,finalcoolingprocess.Inthisprocess,thesystem’senergygraduallydecreases,molecularmovementgraduallyesordered,moleculesareinalignedstatearrangemen,solidreachesastableSAalgorithm’sthoughtisimitatinghermodynamicsannealingprocess,sothatitisgenerallyformedbycombiningtheoptimizationproblem.BeforeintroducingSAalgorithm’sconcretesteps,IwillintroduceMetropoliscriterionly.In1953,MetropoliscriterionisproposedbyMetropolis,itisaimportancesamplingmethod,andisbasedontheprobabilityofacceptingthenewstate.Specifically,attemperatureT,currentstateigeneratesnewstatej,theirenergyareEiandEj.IfEi>Ej,acceptthenewstate,otherwiseacceptthenewstatejbycertainprobability.ThebasicideaofSAalgorithmisgivenaninitialhightemperature,SAsearchesrandomlyinthesolutionspacebyusingMetropoliscriterionsamplingstrategy.Withthetemperaturedropped,SArepeatessamplingprocess.Finally,SAfindsglobaloptimalsolutions.ThuswecanknowSAalgorithmisaheuristicrandomsearethod.SAalgorithmfollowsspecificThestep:selectaninitialsolutionx0infeasiblesolutionspace,computeitsobjectivefunction’svaluef(x0),andselecttheinitialcontroltemperatureT0.Thesecondstep:generaterandomlyanewsolutionx1infeasiblesolutionspace,andcalculatethecorrespondingobjectivefunction’svaluef(x1),calculate△f=Thethirdstep:If△f>0,thenacceptthenewsolutions,if△f<0,accordingtoMetropoliscriteriondeterminewhethertoacceptnewsolutionx1,ifaccepted,currentsolutionisx1,ifnotaccepted,currentsolutionisx0.Thefouthstep:accordingtoaconvergencecriterion,determinewhetherornotofthesamplingprocess,ifcompleted,turntothefifthstep,otherwiserepeatthesecondandthreestep.Thefifthstep:reducethecontroltemperatureTbythepresettemperatureofthecoolingscheme,ifthetemperaturereachesagivenminimumtemperature,SAwillstopsearching,otherwiseturntothesecondstep.Thepaperwasinspiredbyliterature,thenpresentedanimprovedsimulatedannealingalgorithm,sothatitcanbemoresuitableforlarge-scaleinfrastructurefloorplanning.Specificimprovementstrategiesaresettingthreshold,warmimgandincreasingtheoptimalvalue’scomparison.ISAalgorithmfollowsspecificThestep:selectaninitialsolutionx0infeasiblesolutionspace,computeitsobjectivefunction’svaluef(x0),andselecttheinitialcontroltemperatureT0.Thesecondstep:generaterandomlyanewsolutionx1infeasiblesolutionandcalcul