资源描述：
《基于智能算法的片上网络布局优化研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
电子科技大学UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA博士学位论文DOCTORALDISSERTATION（电子科技大学图标）论文题目基于智能算法的片上网络布局优化研究学科专业计算机软件与理论学号201011060318作者姓名乐千桤指导教师杨国武教授万方数据 分类号密级注1UDC学位论文基于智能算法的片上网络布局优化研究（题名和副题名）乐千桤（作者姓名）指导教师杨国武教授电子科技大学成都（姓名、职称、单位名称）申请学位级别博士学科专业计算机软件与理论提交论文日期2014.09论文答辩日期2014.12学位授予单位和日期电子科技大学2014.12答辩委员会主席评阅人注1：注明《国际十进分类法UDC》的类号。万方数据 RESEACHONLAYOUTOPTIMIZATIONFORNETWORKONCHIPSBASEDONINTELLIGENTALGORITHMSADoctorDissertationSubmittedtoUniversityofElectronicScienceandTechnologyofChinaMajor:ComputerSoftwareandTheoryAuthor:LeQianqiAdvisor:Prof.YangGuowuSchool:SchoolofComputerScience&Engineering万方数据 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名：日期：年月日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）作者签名：导师签名：日期：年月日万方数据 摘要摘要片上网络（Network-on-Chip，NoC）借鉴计算机互联网络采用包交换方法替代传统总线方法，实现了处理单元和通信结构的分离，有效解决了片上系统（System-on-Chip，SoC)多核之间的复杂通信问题，片上网络以其优良特性成为研究热点。片上网络的布局结构极大地影响着系统性能，布局结构关联到IPCore(IntellectualPropertyCore)处理单元之间的平均距离、通信路径长度和通信流量分布等特性，这些特征又影响到系统的功耗、时延、面积、吞吐量和负载平衡等众多的性能。片上网络布局中的重要步骤IPCore分配、IPCore映射以及最优路由算法等都是NP问题，这一类问题采用传统的优化算法，难以求得满足条件的解，通常是采用智能算法进行求解。智能算法广泛应用于各类优化问题，当前智能算法的一个重要研究方向是基于多种智能算法思想的融合，提出优势互补的智能算法，并运用于解决具体的优化问题。本文以基于智能算法的片上网络布局优化为研究课题，重点研究了NoC布局优化建模、IPCore分配、IPCore映射、容错机制、路由算法和拓扑结构等问题，主要研究内容如下：(1)根据片上网络布局中的需求和约束条件，建立多目标优化模型。对于其中两个重要阶段IPCore分配和IPCore映射分别建立以下评价模型：IPCore分配包括计算时间、计算功耗和面积等；IPCore映射包括通信时间、通信功耗、负载平衡和可靠性等。所建立的模型能较好地反映出阶段设计要求。(2)以提高NoC可靠性和系统性能为目标，根据NoC通信及故障特点，设计了基于空间冗余的容错结构，以及自适应的容错路由算法。该容错机制可以恢复由交换节点故障引起的通信中断，提高系统可靠性，采用的容错路由算法确保容错路径的性能优化，可以避免死锁、获得最短通信路径并且兼顾通信负载平衡。(3)根据IPCore分配的需求，以优化计算时间、计算功耗和面积等性能为目标求解分配方案，本文设计了两个适用于IPCore分配的智能算法：带多样化策略的多目标优化智能算法MPDS算法和强化局部跳变的多目标优化智能算法MPEL算法。这两个算法通过关键路径算法处理任务的并行性，结合多目标优化策略及智能优化思想，在传统智能算法基础上，引入多样化处理和局部跳变搜索等优化策略，融合了粒子群算法、遗传算法和模拟退火算法等多种智能算法的优点，克服传统单一智能算法易陷入局部最优等缺点，实验结果显示本文提出的算法相比I万方数据 摘要其他常见的智能算法获得了更多，更高质量的IPCore分配方案。(4)IPCore映射是将IPCore安排到NoC结构中的合适位置的处理单元上，结合路由算法，构建NoC的拓扑结构。根据IPCore映射布局的需求和约束条件，以提高布局方案的通信时间、通信功耗、负载平衡和可靠性等性能为目标，设计了带不确定性策略的多目标分散搜索算法MSSU算法。该算法在传统智能算法的完全随机搜索过程中引入可控机制，结合局部的不确定性搜索策略，实现基于小种群的求解过程，在此基础上引入非支配排序方法，实现了多目标优化的求解。该算法兼具有分散搜索算法和遗传算法的优势，其解的搜索能力优于一般的智能算法，实验显示该算法求得的映射布局方案在数量和质量上均优于其他常见智能算法。(5)提出了基于彼得森图的可重构NoC布局结构。可重构布局策略不需要改变IPCore处理单元的映射位置，只需要通过重构节点调整拓扑关系，即可构建适用于多个NoC应用的布局结构，从而增强了布局结构的复用性。彼得森图具有网络直径短的优势，因此以彼得森图作为重构的基础结构，可以减少通信距离。由此得到的可重构布局一方面可以有效缩短节点之间的通信距离，减少中转交换节点的个数，从而达到减少通信代价的目的；另一方面可重构的方法提高了系统的重用性和灵活性。(6)根据NoC映射和路由的特点及需求，提出了多值量子进化算法MQG，并应用于求解NoC的布局优化方案。量子进化算法结合了量子优化和进化算法的思想，多值量子进化编码方法相比传统编码可以携带更多的编码信息，增强进化个体的多样性。在编码及解码过程中，摒弃传统的全路径编码，而是根据路径及节点之间的连续性构建路径，不仅缩短了编码长度，更避免了无效路径的产生。以此为基础构建的布局方案，在避免死锁的基础上搜索最优通信路径，以达到减少通信代价的目的。实验结果显示基于可重构的彼得森图的多值量子进化算法取得的布局方案相比其他常见算法和结构，获得了更低的通信代价。MQG算法思想也可以推广应用于其他NP问题的求解。关键词：片上网络，布局优化，智能算法，路由，分配，映射II万方数据 ABSTRACTABSTRACTNetworkonchips(NoCs)effectivelysolvethecomplexcommunicationproblemsbetweenthemulticoresofsystemonchips(SoCs)usingthepacketswitchingmethodfromcomputernetworksinsteadofthetraditionalbusmethod,realizingtheseparationofprocessingunitsandcommunicationstructures.NoCshaveattractedincreasingattentionsfortheirexcellentproperties.ThelayoutstructuresofNoCsgreatlyaffecttheperformancesofthesystems.ThelayoutstructureisassociatedtosomesystemcharacteristicssuchastheaveragedistancebetweenIPCore(IntellectualPropertyCore)processingunits,communicationpathlength,trafficdistributionandsoon.Thesecharacteristicsalsoaffecttheperformanceindicesofsystemssuchaspowerconsumption,area,delay,throughput,loadbalanceandsoon.TheimportantstepsoftheNoClayout,IPCoreassignment,IPCoremappingandoptimizingroutingalgorithm,areNPproblems.Thesekindsofproblemsaredifficulttoobtainsatisfactorysolutionsbyusingtraditionaloptimizationalgorithms,sointelligentalgorithmsusuallyareusedforsolvingtheseproblems.Intelligentalgorithmsareappliedtoallkindsofoptimizationproblemswidely,oneofimportantresearchtrendsofintelligentalgorithmscurrentlyisthefusionofavarietyofintelligentalgorithms,proposingthealgorithmswithmeritsofmanyalgorithmsandapplyingthemtosolveoptimizationproblems.Inthisdissertation,thelayoutoptimizationofNoCsbasedonintelligentalgorithmsarestudied,focusingonNoClayoutoptimizationmodeling,IPCoreassignment,IPCoremapping,faulttolerancemechanism,routingalgorithm,topologystructure.Themaincontentsareasfollows:(1)AccordingtotherequirementsandconstraintsofNoClayouts,theoptimizationmodelsareestablished.TheevaluationmodelsforIPCoreassignmentinclude:computingtime,computingpowerconsumptionandarea.TheevaluationmodelsforIPCoremappinginclude:communicationtime,communicationpowerconsumption,loadbalanceandreliability.Thesemodelscanreflectthedesignrequirements.(2)ToimprovereliabilitiesandperformancesofNoCsystems,accordingtothefeaturesofNoCcommunicationandfaults,afault-tolerantmechanismisdesignedbyusingspatialredundancyandadaptivefault-tolerantrouting.Thisfault-tolerantIII万方数据 ABSTRACTmechanismcanrecoverthecommunicationinterruptionscausedbyswitchingnodefailures,improvingsystemreliabilities.Thefault-tolerantroutingalgorithmensurestheperformancerequirementsofthefault-tolerantpaths,avoidingdeadlocks,obtainingtheshortestpathsandbalancingcommunicationloads.(3)AccordingtotherequirementsofIPCoreassignment,theschemesofIPCoreassignmentaredesigned,withthegoalofreducingcomputingtime,computingpowerconsumptionandarea.TwointelligentalgorithmsforIPCoreassignmentaredesigned,oneismulti-objectivePSOwithdiversifyingstrategies(MPDS),theotherismulti-objectivePSOenhancinglocalityalgorithm(MPEL).Thesetwoalgorithmsprocessparalleltasksbythecriticalpathmethod,combingthemulti-objectiveoptimizationstrategieswithintelligentoptimizationideas.Thediversifyingandenhancinglocalsearchingstrategiesareintroducedintostandardintelligentalgorithms.Thesealgorithmstakeadvantagesofparticleswarmoptimization(PSO),geneticalgorithm(GA)andsimulatedannealing(SA),overcomingtheshortcomingsofeasilyfallingintolocaloptimumoftraditionalsingleintelligentalgorithms.Theexperimentalresultsshowtheproposedalgorithms,comparedwithothertraditionalsingleintelligentalgorithms,haveobtainedmorehigherqualityIPCoreassignmentschemes.(4)IPCoremappingisarrangingIPCorestotheprocessingunitpositionsintheNoCstructure,constructingNoCtopologiesbasedonroutingalgorithms.AccordingtotherequirementsandconstraintsofIPCoremappinglayouts,withthegoalofimprovingcommunicationtime,communicationpowerconsumption,reliabilityandloadbalance,themulti-objectivescattersearchalgorithmwithuncertaintystrategies(MSSU)isproposed.Thealgorithmusesacontrollablemechanisminsteadofthecompleterandomsearchoftraditionalintelligentalgorithms.Itisbasedonasmallgroup,introducingthenon-dominatedsortingmethod,realizingmuilti-objectiveoptimization.ThisalgorithmtakesadvantagesofScatterSearch(SS)andGA,itssearchingcapabilityisbetterthanothersingleintelligentalgorithms.ThesimulationresultsshowtheproposedalgorithmhasobtainedmorehigherqualityIPCoremappingschemescomparedwithothercommonsingleintelligentalgorithms.(5)ThereconfigurableNoCstructurebasedonPetersengraphisfirstproposed.ThegoalofthereconfigurablestructureisconstructingthesuitablelayoutstructuresformultipledifferentNoCapplicationsbyadjustingtopologicalrelationswithreconfigurablenodes,notchangingtheIPCoremappingpositions.Inthisway,theIV万方数据 ABSTRACTreusabilityofNoClayoutstructuresisimproved.TakingPetersengraphasthebasicrereconfigurablestructurecanreducethecommunicationdistancesbecausePetersengraphhassmallnetworkdiameter.Theproposedreconfigurablestructurecanreducethenumbersofswitchingnodesincommunicationpathsandreducethecommunicationpowerconsumptionandtime.Atthesametime,thereconfigurableNoCstructureimprovesthereusabilityandflexibilityofNoCstructures(6)ThelayoutoptimizationalgorithmbasedonmultivaluedquantumevolutionaryalgorithmMQGisfirstproposedandappliedtosolveNoClayoutproblemsaccordingtothecharacteristicsandrequirementsofNoCmappingandrouting.Quantumevolutionaryalgorithmcombinesquantumoptimizationandevolutionaryalgorithm.Themultivaluedquantumevolutionarycodingmethodcancarrymoreinformationcomparedtothetraditionalquantumcoding,enhancingthediversityofevolutionaryindividuals.Inthecodinganddecodingprocess,pathsarebuiltbasedonthecontinuitybetweenthenodes,discardingthetraditionalwholepathcoding.Thisnewcodingmethodshortensthelengthofcodingandavoidsgeneratinginvalidpaths.Theroutingandlayoutschemesobtainedbythisalgorithmcansearchtheoptimizedcommunicationpathsandavoiddeadlocks,achievingshortestcommutationdistances.TheexperimentalresultsshowthelayoutschemesobtainedfromMQGalgorithmbasedonreconfiguredPetersengraphstructurehavelowercommunicationcost.TheideaofMQGalgorithmisalsoappliedtosolveotherNPproblems.Keywords:networkonchip(NoC),layoutoptimization,intelligentalgorithm,routing,assignment,mappingV万方数据 目录目录第一章绪论....................................................................................................................11.1课题研究背景及意义........................................................................................11.1.1片上网络布局研究及意义......................................................................11.1.2智能算法研究及意义..............................................................................21.1.2.1传统智能算法................................................................................21.1.2.2量子进化算法................................................................................41.2片上网络布局结构研究概述............................................................................51.2.1片上网络体系结构..................................................................................51.2.2片上网络设计流程..................................................................................61.2.3片上网络拓扑结构..................................................................................71.3国内外研究现状...............................................................................................111.3.1片上网络典型成果及研究方向.............................................................111.3.2片上网络布局研究方法现状................................................................131.4本文研究的主要内容......................................................................................151.5论文组织结构..................................................................................................16第二章片上网络布局优化问题的建模与评价..........................................................182.1布局优化问题描述..........................................................................................182.2性能评价模型..................................................................................................192.2.1IPCore分配方案的评价.........................................................................192.2.2IPCore映射方案的评价.........................................................................202.3多目标优化求解..............................................................................................222.3.1Pareto最优解..........................................................................................222.3.2带精英策略的非支配排序....................................................................232.4本章小结..........................................................................................................24第三章容错机制及可靠性分析..................................................................................253.1故障检测机制..................................................................................................253.1.1片上网络故障分析................................................................................253.1.2在线故障检测及定位方法....................................................................263.2基于空间冗余的容错结构..............................................................................293.3自适应容错路由算法设计..............................................................................31VI万方数据 目录3.4可靠性分析......................................................................................................353.5本章小结..........................................................................................................36第四章IPCore分配的智能优化算法设计..................................................................374.1基本算法原理描述..........................................................................................374.1.1粒子群算法原理....................................................................................374.1.2遗传算法原理........................................................................................394.1.3模拟退火算法原理................................................................................424.2MPDS算法设计...............................................................................................444.2.1算法设计原理及分析............................................................................444.2.2解的表示和更新方程............................................................................444.2.3算法实现过程........................................................................................454.3MPEL算法设计...............................................................................................474.3.1算法设计原理及分析............................................................................474.3.2局部搜索强化过程................................................................................474.3.3算法实现过程........................................................................................484.4算法分析..........................................................................................................504.5实验及结果分析..............................................................................................534.6本章小结..........................................................................................................55第五章IPCore映射布局的智能优化算法设计.........................................................575.1算法原理分析..................................................................................................575.2MSSU算法设计...............................................................................................585.2.1算法流程描述........................................................................................585.2.2解的表示和改进....................................................................................605.2.3非支配排序过程....................................................................................605.2.4参考集的操作........................................................................................615.2.5子集的操作............................................................................................625.2.6参考集的更新........................................................................................635.3实验及结果分析..............................................................................................635.3.1映射方案的评价指标对比....................................................................635.3.2Nirgam仿真结果分析............................................................................655.4本章小结..........................................................................................................71第六章面向多应用的可重构布局优化算法设计......................................................736.1基于彼得森图的可重构布局设计...................................................................73VII万方数据 目录6.1.1可重构原理分析....................................................................................746.1.2可重构结构设计....................................................................................766.1.3基于彼得森图的可重构结构................................................................786.2MQG算法设计.................................................................................................796.2.1量子进化算法原理及结构....................................................................796.2.2算法设计分析........................................................................................816.2.3量子编码设计........................................................................................826.2.4算法实现过程........................................................................................826.3实验及结果分析..............................................................................................846.3.1布局结构及路由线路............................................................................856.3.2实验结果方案性能对比........................................................................896.4本章小结..........................................................................................................91第七章结论与展望......................................................................................................927.1全文总结..........................................................................................................927.2研究展望..........................................................................................................93致谢............................................................................................................................95参考文献........................................................................................................................96攻博期间取得的研究成果..........................................................................................104VIII万方数据 第一章绪论第一章绪论1.1课题研究背景及意义1.1.1片上网络布局研究及意义随着先进半导体工艺技术的不断发展，集成电路的集成度大幅度地提高，在单个芯片上可以集成越来越多的复杂功能模块，片上系统（SystemonChip,SoC)作为一个芯片上具有特定功能的完整系统，得到了广泛应用。当今社会信息技术不断发展，掌上智能终端设备逐渐在人们生活和工作中得以普及，个人嵌入式产品的需求量不断增加，以及其他工业领域对智能化设备的要求也不断提高。因此通讯、多媒体和自动化控制等众多应用需要复杂的SoC产品，同时对芯片的性能要求也更高，多核SoC得以广泛应用，芯片的集成度和复杂度也日益增加，因此有效提高片上处理器的资源利用率以及片上互连技术成为亟待解决的问题，但是SoC的总线型通信结构使得系统的设计复杂性增加，系统结构难以扩展，通信延迟增加，这些缺陷成为了SoC设计的瓶颈。SoC的繁重通信任务需要可扩展的通信架构来支持，片上网络(NetworkonChip，NoC)作为SoC的通信解决方案而出现。NoC借鉴了计算机的互联网络，采用基于包交换的方法和分层方法来替代传统的总线方法，实现了处理单元和通信结构的分离，有效解决了SoC中多核之间[1-2]的复杂通信问题。相比SoC的总线型通信结构，NoC可以提供更好的复用性、可扩展性以及容错性。具体描述如下：(1)NoC的复用性主要体现在处理模块和通信结构两个方面，NoC中的通信组件及其所提供的通信服务，与处理单元及其所提供的计算服务，是相互对立的，其中的处理单元、交换组件、链路和通信协议等都是可以重复使用的。这些基本组件不涉及到底层网络，可以根据不同的应用需求通过网络接口组合相关的处理模块构建通信网络。(2)NoC的可扩展性主要体现在提供组件的即插即用性和地址空间的可扩展性。处理单元和交换节点之间是通过网络接口进行连接，采用了即插即用的配置方式。可扩展的地址空间允许更多的处理单元集成到芯片上。(3)NoC的容错性体现在片上网络采用了数据包传输方式，易于在通信节点之间增加检测错误和纠正错误的机制，便于设计具有冗余路径等相关容错机制的路由算法来避开故障节点。1万方数据 电子科技大学博士学位论文片上网络与普通网络有一定的区别，片上网络只适用于片上系统，通常是针对某一个或者某一类应用而设计的，普通网络通常具有一定的通用性。片上网络需要根据应用需求设计整个网络，包括拓扑结构和通信协议等；普通网络更多地是需要兼容已经存在的网络协议。片上网络的布局结构和通信关系相对固定，易于构建系统模型，便于分析及评估性能。[3-6]片上网络以其优良的特性成为研究热点。其关键技术主要包括系统建模、拓扑结构、布局优化、路由方法和服务质量等方面。其中片上网络的布局结构极大地影响着系统性能，因为布局结构关联到IPCore(IntellectualPropertyCore)之间的平均距离，链路的总长度，通信流量的分布等特性，这些特征又影响到系统的[7]功耗、时延、面积、吞吐量和负载平衡等众多的性能。片上网络的布局过程包括了拓扑结构构建、IPCore分配和映射等方面。拓扑结构确定节点之间的连接关系，IPCore分配确定选择哪些IPCore放入拓扑结构，IPCore映射确定每个IPCore在拓扑结构中的位置。IPCore分配和映射是NoC设计[8]和平台实现的重要步骤，这两个步骤的实施情况直接影响着NoC系统的总体性能。IPCore映射是该领域的研究热点，对于IPCore分配的研究相对较少。本文不仅研究了IPCore的映射算法，同时也研究了IPCore分配问题。随着集成电路规模的不断增大，越来越多的复杂设计集成到芯片上，片上通信因此受到的干扰增多，易出现各种现通信故障，降低了系统可靠性。因此容错和可靠性问题得到了越来越多的关注，研究提高片上网络可靠性的机制和技术已[9][10]成为迫切需要，研究者在该领域开展了广泛的研究。因此本文研究的具有容错机制的片上网络布局算法，具有很好的研究价值和实用性。1.1.2智能算法研究及意义1.1.2.1传统智能算法随着大数据时代的来临，在对海量数据的各种处理中，复杂的组合优化问题也与日俱增，采用经典的优化方法，如贪心算法、动态规划等，通常很难在合理的计算时间内求得满意的解。在这种情况下，人们开始采用智能优化算法来解决这一类组合优化问题，智能算法在这一领域得到了越来越广泛的应用。智能算法是人们对自然界存在的结构和规律进行抽象和总结，并且结合仿生学的原理，模仿和设计求解问题的方法，例如：粒子群算法，遗传算法，模拟退火算法，人工神经网络等。智能是指系统具有不断调整自己以适应环境，向目标接近的能力，可以体现为合理的思维和行为。自然界的生物为了适应环境，基于自身的进化本能，优化2万方数据 第一章绪论自己的生存状态，以获得生存的机会，这种无意识的寻优行为及过程就是生物智[11]能。人们研究生物智能，采用人工的方法对其进行模仿和扩展，这就是人工智能。我们所指的智能优化算法即人工智能算法，是模仿生物的寻优方式来解决实际应用问题的方法。智能算法作为一种新型的优化算法，相比传统的优化算法具有一定的优势和特点。智能算法的实施是通过智能个体来完成的，智能算法中的个体通过与其他个体的信息交换和对环境的感知来获取知识，结合一定的优化策略重构自身，并且可以根据变化的环境和进化的过程不断地与其他个体协作，更新知识和自身结构，逐渐接近目标。个体的这种学习和更新的能力体现在算法上就是对问题的求解能力的不断提升。个体之间的相互协作，与环境的交互，通常是通过计算机来模拟实现的。一般的智能算法在解决高复杂度问题时更能体现出优势，简单问题如果采用智能算法反而可能造成简单问题的复杂化，增加更多的计算时间，智能算法的优化策略和过程中通常会引入随机机制，这样更接近于生物界的无意识寻优，由此也带来了求解的不确定性，通常智能算法也是典型的随机算法。智能算法都具有自适应的驱动体系，并在计算过程中不断地修正。根据模拟的智能方法的原理和机制不同，可以得到不同的智能算法，例如：群智能算法、进化算法和人工神经网络等。(1)群智能算法，主要思想是来源于群居昆虫的生活行为，例如鸟类觅食，蜜蜂筑巢等。单个的昆虫不能完成的任务，可以通过一群昆虫集体协同完成。通过模仿昆虫的协作与竞争的群体行为，建立了群智能算法。群智能算法中的个体行为很简单，但是多个个体在一起相互协同的行为就呈现出明显的特征，不需要建立全局模型，也不需要集中监管和局部控制，为复杂问题的分布式求解提供了基础。群智能算法具有很好的稳定性和灵活性，单独个体的失败不会影响到算法整体效能，智能个体可以根据环境自适应地调整状态。常见的群智能算法有：粒子群算法、蚁群算法和蜂群算法等。(2)进化算法进化算法是借鉴了生物界优胜劣汰的自然选择机制，以及生物遗传机制的一[12][13][14]种搜索算法。主要包括遗传算法、进化规划和进化策略等。可以用来解决优化和机器学习等问题。算法通过程序的多次迭代模拟了优胜劣汰选择和遗传信息传递的过程，把待解决的问题作为环境，可能的解作为种群的个体，通过自然进化规则搜索最优解。进化算法在搜索过程中利用结构化和随机性的信息，使最能满足目标的个体获得最大的生存机会，模拟了自然界的适者生存准则。常见的3万方数据 电子科技大学博士学位论文进化算法如遗传算法、差分进化算法等。(3)人工神经网络人工神经网络是模拟人脑活动的理论化的算法模型，它模拟了人类的思维方式。人工神经网络是由很多人工神经元相互连接而成，具有自适应性的系统。单个神经元本身结构和功能比较简单，大量神经元连接而成的神经网络可能呈现很复杂的行为。人工神经网络是对人脑基本功能的简化和抽象，通过调整节点之间的连接关系、学习规则和适应环境，从而完成计算或者处理任务的过程。此外常见的智能算法还有模拟热力学中退火过程的模拟退火算法，模拟生物体中免疫响应机制的人工免疫算法等。智能算法通常都具有自主学习，自适应等特性，可以根据计算的过程，自适应地调整个体结构或者算法参数，以达到求解问题的目的。通过自身的演化，自主地寻优，就可以很好的解决问题，这种能力是计算机程序很难达到的，科学家为了解决某个问题可能要耗费大量的时间和精力，生物体通过自然进化和自然选择这类无意识的机制就可以解决问题。智能算法适合于解决采用传统优化方法难以解决的复杂问题：最优化、分类、聚类、模式识别、流程规划、机器人控制、决策支持等。不同的智能算法具有各自的优势和缺点，融合多种智能算法思想以获得优势互补，已经成为智能算法研究的一个重要方向。1.1.2.2量子进化算法量子进化算法融合了量子计算和进化算法的特点。进化算法是模拟自然界生物进化机制的搜索算法，量子计算是量子学和计算科学结合的算法。在进化算法[15]中引入量子计算的多宇宙概念和态矢量的表达方式。多宇宙概念的引入实现了多种群的并行搜索，同时种群之间还可以通过联合交叉等方式相互增进补益，扩大了解空间的搜索范围。态矢量的表达方式可以用于染色体的编码，量子系统能够描述叠加态，相比传统进化算法，在一条染色体中可以描述更多的状态，从而提高了种群多样性。在染色体的进化过程中，放弃了常规进化算法中的遗传和变异操作，而是利用量子旋转门、非门等量子的方式实现染色体的进化，取得了更好的进化效果。此外，采用量子进化原理实现的算法将来也许有可能在量子计算机上执行。[15]量子进化算法最早是在1996年由Narayanan和M．Moore等人提出的，在遗传算法中融入了多宇宙概念，通过多个种群的之间联合进化、并行搜索等方式[16]提高算法效率。K．H．Han等人于2000年在遗传染色体编码中采用了量子态矢量，在染色体的进化中采用了量子旋转门，并且在多个种群之间采用了迁徙方法4万方数据 第一章绪论[17]从而提高了种群的多样性。Zhang等人在2003年提出新的量子遗传算法，采用量子比特相位比较法以及自适应调整搜索网络等优化策略，提高了算法收敛速度[18][19]以及寻优能力。Yang等人提出了多宇宙并行量子遗传算法。Cheng等人在2004[20]年提出了混沌更新旋转门转角的方法。Khorsand等人在2005年提出了两层量子[21]遗传算法，在搜索最优解的过程中可以对自身参数进行优化。Moor等人在2005年提出了量子粒子群算法，将局部粒子群优化引入到量子优化中，有效地提高了[22]算法的解的质量和算法效率。Li等人在2006年提出了改进的量子遗传算法以求[23][24]解连续空间的优化问题。Ali等人提出了免疫量子进化算法。Izadinia等人提出了一种自适应的量子进化算法。1.2片上网络布局结构研究概述1.2.1片上网络体系结构片上网络NoC借鉴了计算机互联网络的通信结构来替代片上系统原有的总线型结构，实现了处理单元和通信结构的分离，基于此思想可以得出NoC的系统示意图，如图1-1所示。从图中可以看出NoC布局结构的几个主要部分包括：(1)处理单元：处理单元负责执行NoC应用中的任务，计算或者处理相关的数据信息。相当于计算机互联网络中的端节点，具有独立计算和处理数据的能力。处理单元通过网络接口连入片上网络，可以向网络中发送和接收数据。(2)交换节点：交换节点通过链路连接在一起构成了NoC的通信系统，负责NoC数据通信，完成片上网络中数据包的路由和转发功能，相当于计算机互联网络中的通信子网。(3)网络接口：网络接口负责处理单元与片上网络的连接工作。(4)链路：链路负责连接片上网络中的各个组件，提供数据传输的通路，在实际应用中一条链路可能由一个或者多个通信管道构成。NoC的处理单元、交换节点、链路和网络接口各部分组件通过一定的方式连接成为一个具有数据处理和通信功能的整体。由交换节点和链路组成的通信网络与处理单元相分离，采用了基于包交换的通信机制，这样构建的通信子网结构有利于应对片上系统多核之间的复杂通信任务。处理单元独立于通信子网之外，专注于数据信息的处理，处理单元产生的数据，以数据包的方式进入到通信结构，经过交换节点的转发，传递到目的处理单元。这种数据的通信与处理相对分离的结构有利于提高通信能力，系统组成模块的功能相对独立，也有助于提高系统的可扩展性。5万方数据 电子科技大学博士学位论文处理单元网络接口处理单元处理网络单元交换接口网络节点交换接口节点交换节点交换交换节点节点网络通信结构网络接口接口处理处理单元单元图1-1片上网络系统示意图1.2.2片上网络设计流程根据NoC应用任务，设计NoC系统的完整流程通常分为以下步骤：(1)NoC应用的建模根据NoC应用中的子任务及通信关系构建任务图。NoC的性能与网络中的通信流量有很大关系，在设计过程中不仅需要分析子任务本身的执行特征，例如计算时间、计算功耗等，还要分析子任务之间的数据通信关系和通信流量，抽取相关的信息，建立对应的任务图模型。(2)NoC任务到IPCore的分配为NoC应用中的子任务分配合适的IPCore。根据每一个子任务的特性，例如任务类型、执行时间和执行功耗等特征，在IPCore备选库中选择合适的IPCore分配给相应的子任务，通常首先要考虑的是IPCore能否完成相应的任务，其次要考虑IPCore的计算时间，计算功耗和面积等因素。(3)IPCore映射及拓扑结构设计为分配所得的IPCore在NoC结构中选择一个合适的处理单元位置。该步骤分为两种情况，一种情况是先选择规则的拓扑结构，然后把IPCore映射到拓扑结构6万方数据 第一章绪论中的某一个位置。另一种情况是事先不确定具体的拓扑结构，在映射IPCore过程中，动态地建立拓扑结构。在映射以及建立拓扑结构的过程中，为IPCore选择合适的处理单元位置时，通常要考虑处理单元的位置对通信关系和通信流量的影响，由此最终影响到通信时间、通信功耗等系统性能。(4)设计通信基础结构分析NoC的时延、功耗和面积等性能指标以及相关的约束条件，设计相应的路由算法，拥塞控制和流量控制等策略，在此基础上选择合适的路由器和通信通道，搭建网络拓扑结构。(5)设计方案的仿真和评价对NoC布局方案进行仿真和评价，可以采用软件工具进行仿真模拟，或者通过性能模型进行理论分析，评价指标通常包括：时延、功耗、面积、吞吐量、热量平衡、QoS、容错和可靠性等。仿真评价的结果可以为进一步完善系统设计提供参考。(6)设计的实施和验证根据前阶段所得的拓扑结构、路由算法和通信策略等方案，进行NoC基本硬件单元以及网络接口的设计，在此基础上根据映射拓扑方案将基本硬件单元组合成整体的片上网络系统。最后验证整个NoC硬件系统的有效性、可用性以及相关的性能指标。1.2.3片上网络拓扑结构片上网络的拓扑结构主要确定处理单元在网络中的相对位置，以及处理单元之间的连线关系，由此形成一定的网络形状。拓扑结构中网络节点和连接链路的布局与IPCore映射算法和路由算法紧密相关，从而影响到整个网络的时延、功耗、吞吐量和面积等性能。片上网络的拓扑结构通常分为规则和不规则结构两大类，其中典型的规则片上网络拓扑结构包括网格(Mesh)、环绕网(Torus)、环网（Ring）、星形(Star)、树形(Tree)和蝶形(Butterfly)等。不规则的结构包括根据具体的NoC应用定制的结构、分层网络结构和网络-总线混合结构等。规则的拓扑结构，适合二维硅平面设计工艺，可以利用成熟的架构和方法，通用性很强，开发设计相对容易，复用性和扩展性强。缺点是只适用于通用的体系结构，对于某些NoC应用，结构与应用的切合性不足，不能最大限度的发挥系统的功效。不规则的拓扑结构更适用于具体的NoC应用，能更好的实现特定的应用功能，优化时延、功耗等性能，最大限度的发挥系统功效，缺点是开发设计的7万方数据 电子科技大学博士学位论文过程更复杂，不具有通用性。除了常见二维(TwoDimension，2D)拓扑结构以外，目前三维(ThreeDimension，3D)拓扑结构也逐渐受到研究者的青睐。典型的规则结构有如下几种：(1)2Dmesh结构如图1-2所示，2Dmesh是一个平面网格结构，由交换节点和链路互连而成。图中的圆形表示交换节点，矩形表示处理单元。每个交换节点与本地处理单元连接，同时也与相邻的其他交换节点互连。除了边界处节点以外，交换节点在东南西北四个方向上与其他交换节点都有链路连接。该结构简单规整，易于芯片实现，便[25-26][27]于扩展，得到了广泛的应用。例如一些著名的NoC系统Nostrum,AEthereal,[28]SoCBus等均采用了该结构。图1-22Dmesh结构图1-32Dtorus结构(2)2Dtorus结构[29]2Dtorus结构如图1-3所示，是由Dally等人提出，在2Dmesh结构上对边界节点改进而得。每一行的最后一个节点与第一个节点相连，每一列的最后一个节点与第一个节点相连，每一行和每一列分别构成了一个环，该结构可以减少数据在首尾节点之间传递需要的中转节点数。由于构成的环路之间有交叉，因此在布线时需要更多的资源和开销。(3)环形结构如图1-4所示，环形结构由交换节点和链路首尾相连而成，数据包可以沿着环的顺时针或者逆时针方向传输。当网络中资源较多时，数据传输的跳数可能较多，网络的时延较大。为了减小网络直径和通信时延，可以让环上不相邻的节点之间[30]也相互连接，如图1-5所示，由此得到Spidergon结构。该结构中每个交换节点有四个接口，一个连接本地处理单元，另外三个接口分别与其他交换节点相连，数据包不仅可以沿环链路双向传输，还可以沿着中心方向传输，由此减少了网络8万方数据 第一章绪论直径，增加网络吞吐量。缺点是连线资源的增多导致功耗、面积的增加，芯片内部的布局结构复杂性也随之增加。图1-4环形结构图1-5Spidergon结构(4)树形结构树形结构中，树的叶子节点放置处理单元，非叶子节点放置交换节点。因为树中每个节点只能有一个父节点，整棵树只能有一个根节点，根节点在通信过程中可能与多个节点交换数据，交换的数据量较大，容易成为瓶颈，因此提出了SPIN[31-32]结构，如图1-6所示。该结构中的交换节点可以有多个父节点，由此增加了交换节点的冗余度，可以产生更多的可选路径。树的深度对该结构的通信时延有较大影响。图1-6SPIN结构图1-7蝶形结构(5)蝶形结构蝶形结构如图1-7所示，该结构灵活地组合了交换节点之间的连接关系，每一对处理单元之间的路径距离跳数是相等的，网络直径较小。蝶形结构有效地利用了交换节点之间的互连，但是处理单元之间的通信路径缺乏多样性，可选路径少，因此处理拥塞的能力较弱。(6)三维结构9万方数据 电子科技大学博士学位论文为了进一步优化片上网络的性能，研究者们对3D的NoC拓扑结构开始关注及研究。如图1-8所示，图中的圆形表示交换节点，每一个交换节点都有一个端口跟本地的处理单元连接，其他端口跟相邻交换节点连接，为了更清晰地显示拓扑连接关系，在图中只展示出了交换节点的互连关系，没有画出处理单元。3D结构在垂直方向增加了处理单元的堆叠，可以缩短片上处理单元之间的距离，降低通信时延和功耗，提高吞吐量等性能。在基本立方体结构的基础上，研究者又提出了各种扩展3D结构，如图1-9所示的超立方体结构，超立方体的对称性更好，具有更多的链路，网络直径也更短。但是3D拓扑结构在当前广泛使用的2D芯片中，布局不易实现，3D拓扑结构对NoC布局和封装的工艺技术提出了更高的要求。图1-83D立方体结构图1-93D超立方体结构非规则NoC拓扑主要是针对某一种或者一类特定的NoC应用需求而定制的，可以大致分为专用网络和混合网络两类。专用网络完全根据具体的应用需求设计每一个网络节点的位置和连线关系，没有统一的规则。专用网络很好的切合了应用要求，通常可以减少交换节点的使用，从而减少处理单元之间的通信距离，降低通信时延、功耗和面积等系统开销，图1-7[33]图1-10展示了MP3encoder的专用NoC结构，该结构结合MP3encoder的具体应用需求，将通信流量大的网络节点安排在邻近的位置，以减少功耗等通信代价，并且尽量集中安排所有的网络节点，最大化交换节点的连接度，从而减少节点之间的通信距离。混合网络主要是为了提高系统性能，对已有的规则网络进行改进或者扩展。可以根据应用需求减少规则网络中的某些网络节点或者链路；可以把几种不同的规则网络组合在一起；可以采用分层的方式在不同的层次采用不同的拓扑结构；可以实现网络结构和总线结构的组合架构。图1-11展示了一种层次化的全连通拓[34]扑结构（HierarchicalCompletely-ConnectedNetworks，HCC）。该结构中首先构建基本模块，图中的四个交换节点组成的四边形即为基本模块，然后在此基10万方数据 第一章绪论础上实现多个模块之间的互连，由此减少了通信节点之间相互访问经历的跳数，减少了通信时延和通信功耗。图1-10MP3encoder专用NoC结构图1-11HCC结构总体而言，规则的拓扑结构适用于通用同构的NoC系统，具有较好的复用性，开发周期短。此外二维布局技术因为其成熟的工艺技术，可以降低设计成本，减少开发时间，因此目前使用最广泛的还是二维规则网络结构。1.3国内外研究现状1.3.1片上网络典型成果及研究方向NoC在2001年第一次被提出并引起了研究者的关注，逐渐得到人们的应用和[35-36]研究。2007年召开了第一个以NoC为主题的国际会议：第一届IEEE片上网络国际研讨会(IEEEInternationalSymposiumonNetworks-on-Chip)，标志着该研究领域的兴起，NoC作为SoC的前沿研究领域，已经初步形成了一个完整的设计[35]理论和研究体系。目前国内外很多高校和研究机构在从事着NoC各个方面的研究，主要包括布局结构、任务调度、通信策略、路由算法以及服务质量等方面，开发了各种实验系统，其中具有代表性的成果主要包括：[31-32](1)法国PierreetMarieCurie大学的SPIN工程，该工程研究的NoC采用了树型拓扑结构和自适应路由策略，具有很好的可扩展性和通用性，并且开发了CASS模拟器对通信结构进行评估。[25-26](2)瑞典RoyalInstituteofTechnology研究的Nostrum工程，这是一种通用的片上网络，采用了2Dmesh拓扑结构、使用了频率相同但相位不同的伪同11万方数据 电子科技大学博士学位论文步时钟，同时还提供了NNSE仿真环境。[37-38](3)Stanford大学和Bologna大学共同研究的Xpipes，这是一个高性能的、可综合的多核异构片上网络结构，同时还提供了两个片上网络辅助开发工具SUNMAP和XpipesCompiler。[27](4)荷兰Philips实验室开发了Aethereal系统，该系统采用了时分复用技术和无竞争路由策略，时隙分配策略可以采用分布式和集中式编程，致力于提供最大努力的服务和保证服务。[39](5)英国Manchester大学开发的CHAIN，该NoC结构是基于异步系统设计的，在控制数据交换的过程中采用握手信号的方式，并且使用细粒度流水线和降低元件面积等方式提高系统性能。[28](6)瑞典Linkopings大学研发的SoCBUS结构，该系统主要适用于对时延要求严格的硬实时系统。数据交换采用了包连接电路的方式，不会发生死锁，也不需要缓冲器，该结构采用了2Dmesh拓扑结构。[40](7)芬兰Tampere科技大学研发了Proteo结构，该结构是多种基本拓扑结构组合而成的分级结构，主要由双向环网、星型网络和总线子网组合构建而成的网络，可以使用OIDIPUS工具配置可选的拓扑结构和模块。该系统为NoC的混合拓扑设计提供了参考。[41](8)丹麦Technical大学开发的MANGO，该系统可以提供有连接和无连接两种方式，为了保证通信质量，该系统的虚拟通道技术采用了独立的物理缓存，并且提供标准的网络接口，以便于实现协议转换。[30](9)ST公司开发的STNoC，该系统采用了Spidergon拓扑结构，采用了低开销的NoC技术，并且可以与STBUS总线兼容，该系统具有高吞吐率和低延迟等优点。国内多所高校和研究机构也开展了大量的NoC研究，主要研究如下：清华大学的研究主要包括：采用分布式同步策略实现全局异步局部同步的片[42]上系统的研究；NoC高性能实现及其可测性的研究；无线NoC的研究；专用NoC[43]设计方法的研究；三维NoC的架构方面的研究。[44]中科院计算所的研究主要包括：NoC端到端反馈随机路由算法的研究；NoC[43]路由器电路以及连线的测试方法等方面的研究。国防科技大学的研究主要包括：[43]有界延迟服务NoC研究；基于差分CDMA的高性能NoC等方面的研究。哈尔滨工业大学的研究主要包括：NoC通信模型的研究，NoC动态可重构结构及其切换方法[43]等方面的研究。西安电子科技大学的研究主包括：甚低功耗NoC系统模型的研究；NoC异步互12万方数据 第一章绪论[43]连技术；NoC高性能互连技术等问题的研究。西安邮电学院进行了基于无线通信[43]的NoC结构，以及自重构容错功能等方面的研究。浙江大学主要研究了在有限制的资源条件下提高NoC性能的策略；提出了数据安全通信、提高通信效率、资[43]源分配和路径分配等问题的解决方案[43]合肥工业大学开展了NoC低功耗通信协议栈等问题的研究。中山大学对NoC[43]的拓扑结构和路由等问题进行了研究。南京大学对三维NoC的相关问题进行了[43]研究。电子科技大学主要进行了高能效NoC设计及相关技术的研究，主要包括[45-46]拓扑结构、通信优化等方面。[47][48]此外，很多著名的企业也开展了NoC的研究和应用。iNoCs、Arteris、[49]Silistix等公司开发了NoC辅助设计工具，帮助设计者快速有效地开展NoC的设计工作。Intel、IBM、Sony、Toshiba等多家公司在MPSoC设计中引入了NoC的通信架构。1.3.2片上网络布局研究方法现状NoC布局以提高NoC系统性能为目标，安排片上各个网络节点的位置与连线关系，设计网络形状，在此基础上设计路由算法，构建节点之间的通信路径。NoC布局中的两个重要步骤IPCore分配和IPCore映射决定了最终的布局方案。不同的布局方案在很大程度上影响着后续步骤的进行，并最终影响NoC的性能。布局优化目标主要包括：能耗、面积、延时、热量平衡、吞吐量和QoS等，优化目标呈现多样化，优化方法从传统的启发式优化发展到智能优化算法。(1)NoC的布局算法[50]Tang等人提出两阶段遗传算法，第一阶段根据计算时间为任务分配IPCore，[51]第二阶段根据通信时间，设计NoC的布局位置。Hu等人采用分支限界法实现IPCore映射，力求在带宽约束下获得功耗最低。上述文献主要针对单一的优化指[52]标。Zhou等人提出NoC布局的多目标优化，以最小化平均跳数和热点的热量平衡作为评价指标，采用非支配遗传算法(non-dominatedsortinggeneticalgorithm,[53]NSGA)实现了优化。Jena等人采用NSGAⅡ算法实现了优化能耗和带宽需求的[54]目标。Choudhary等人采用遗传算法实现IPCore映射，优化目标是不同路由算[55]法下的通信能耗和链路平均负载。Sepulveda等人采用免疫算法实现IPCore的映[56]射优化，评价指标是时间和功耗。daSilva等人分别采用了NSGAⅡ和microGA算法实现了NoC的多目标优化，评价指标包括：面积、功耗和时间。上述文献是[57]对NoC布局进行多目标优化。此外还有Sahu等人采用了粒子群算法解决NoC[58][7]映射问题，Chou等人提出了带拥塞控制的映射算法，Carvalho等人提出了动13万方数据 电子科技大学博士学位论文[59]态任务映射算法，Khajekarimi等人提出了基于整数线性规划的映射算法，Zhou[60]等人改进分支限界法，提出了一种基于任务绑定的NoC应用算法。综上所述，优化目标主要包括：功耗、时间、面积和负载等，实现算法主要包括分支限界算法、粒子群算法、遗传算法、免疫算法以及其他启发式算法。除了上述文献中提到的常用的NoC性能指标以外，随着芯片上集成元件的个数增加，网络节点之间的通信更频繁，系统的总体复杂性也增加，因此故障发生[61]的概率也随之增大。NoC的容错和可靠性研究受到越来越多的关注。Zonouz等人[62]提出一种容错结构，把IPCore连接到两个交换节点；Kabiri等人采用了空闲交[63]换节点替换故障交换节点的方式；Refan等人提出了替换故障交换节点，重新路由构建通信路径的方法。(2)NoC的路由算法片上网络的拓扑结构决定了通信节点之间的数据包能否从起点到达终点，路由算法决定数据包沿着怎样的路径从起点到达终点。路由算法影响路径的长短，也就影响了通信时延等相关的性能指标，因此路由算法在NoC的设计中很重要，[64-70]也是研究热点。路由算法的基本要求是数据可以正常在源节点和目的节点之间传输，不会出现死锁、活锁或者饥饿。死锁是指多个节点相互等待，不能继续推进。活锁是指数据在网络节点之间无休止传输，不能终止。饥饿是指某些节点的数据一直占用网络资源进行传输，导致另一些节点的数据一直没有机会获得网络资源进行传输。NoC的路由算法大致可分为无关路由和自适应路由两类。无关路由实现原理较简单，在构建路径时不考虑网络的实时状态，常用的无关路由算法主要包括:确定性路由、随机路由和维序路由等算法。其中确定性路由算法适用于网络拥塞较少、流量较低的网络，硬件实现简单，网络时延小。随机路由算法以一定的概率发送数据选择路径，该类算法原理简单，具有一定的容错性，但是速度较慢。维序路由适用于2Dmesh和2Dtorus等结构。自适应路由算法通常会根据网络的实时流量、拥塞状况以及其他相关条件,自动地选择有效路径,以达到减少网络时延等提高网络性能的目标。常用的自适应[71][72][73]路由算法包括伪自适应XY路由算法、转向路由算法、奇偶转弯模型算法[74][66]NoC-LS路由算法和SRN路由算法等。其中伪自适应XY路由主要适用于2Dmesh结构，转向路由算法主要适用于树型和蝶型结构、NoC-LS路由算法是基于最短路径思想的算法，可以高效地传输数据，但是算法实现比较复杂。SRN路由算法将计算机网络中的源路由算法用于片上网络，该算法采用广播请求分组的方式收集路径信息，类似于洪泛路由可以搜索到多条路径，具有较好的健壮性，该方法相比洪泛路由减少了冗余信息量。14万方数据 第一章绪论(3)NoC的性能评价模型在评价NoC性能时，采用的评价模型对评价效果有比较重要的影响。Wiklund[28][75]等人采用了直接建模的方式评价功耗和时间；Saastamoinen等人提出了NoC[76]路由器功耗和面积的计算模型；Tortosa等人提出了功耗的精确模型，包括交换[77]节点、缓冲区和交换节点内部连线等细节部分的计算模型；Cheng等人提出了[78]一种NoC通信性能评估模型；Kalimuthu等人提出了功耗和面积的评价模型；[79]DiTomaso等人提出了无线NoC的评价模型。以上文献提出的模型有的是粗糙估算，有的是精确计算，在实际应用中精确计算比较准确，但是计算过程较为复杂，粗糙估算虽然欠缺精度，但是实施简单，能反映出性能变化趋势，所以应用比较广泛。总体而言，NoC布局设计发展的主要方向是：设计高性能低复杂度的布局方案，增强系统的可靠性和可预测性，从而降低设计风险。开发NoC辅助设计工具和模拟工具，从而提高设计效率，降低开发成本。1.4本文研究的主要内容本文主要研究了片上网络设计过程中的布局优化问题，主要包括对系统性能具有较大影响的几个方面，包括IPCore分配，IPCore映射、容错策略、路由算法和拓扑结构等。根据上述研究中提出的多个优化问题，设计智能算法进行求解，以期获得高性能的布局方案。此外还研究了可重构布局结构，以提高系统的可重用性。具体描述如下：(1)片上网络布局优化及性能评价模型的建立分析片上网络布局过程建立优化模型，根据布局的两个重要阶段IPCore分配和IPCore映射的不同需求和约束条件，建立能反映出设计要求的评价模型，以及对多目标优化模型的研究。(2)NoC的容错布局结构及路由算法设计以提高NoC可靠性和系统性能为目标，设计具有容错功能的NoC布局结构，在该结构上设计自适应的容错路由算法，既可以在发生故障时，恢复通信提高可靠性，又能避免死锁，获得最短通信路径和负载平衡等性能优化。(3)IPCore分配优化的智能算法设计IPCore分配是为NoC应用中的子任务分配能完成该任务的IPCore，该问题是[80]属于NP问题，本文通过关键路径算法处理任务的并行性，结合智能算法思想和多目标优化策略，设计适用于IPCore分配的优化算法：MPDS算法和MPEL算法。本文所提出的算法以获得分配方案的计算时间、计算功耗和面积等性能优化为目15万方数据 电子科技大学博士学位论文标。(4)IPCore映射优化的智能算法设计IPCore映射是将IPCore安排到NoC结构中适当位置的处理单元上，结合路由[80]算法，构建NoC的拓扑结构。该问题也属于NP问题，本文采用了智能优化算法进行求解。根据IPCore映射的需求，结合智能优化思想和非支配排序方法，设计多目标优化算法：MSSU算法，该算法以提高布局方案的通信时间、功耗、可靠性和负载平衡等性能为目标。(5)面向多应用的可重构NoC布局结构为了增强系统的重用性和提高系统性能，设计基于彼得森图的可重构布局结构。重构策略不需要改变IPCore的映射位置，只是通过调整拓扑关系，即可构建适用于多个NoC应用的布局结构，以增强结构的重用性。结合具有网络直径短等优点的彼得森图，可以获取最短的通信路径，从而提高NoC通信性能。(6)基于多值量子进化的布局优化算法设计量子进化算法结合了量子计算和进化算法的优化思想，在此基础上设计多值量子编码方案，携带更多的进化信息，增强进化个体的多样性。摒弃传统的全路径路由编码方式，根据路径的连续性设计编码解码方案，缩短编码长度且避免无效路径，以实现通信节点之间的通信路径寻优，从而获得高性能的NoC布局和路由方案。1.5论文组织结构第一章主要介绍课题的研究背景和意义以及本文的主要研究内容。首先概述研究片上网络及其布局方法的意义和重要性，接着介绍了片上网络布局的基本概念和方法，概述了智能算法的研究和应用，然后分析国内外在该领域的研究现状，最后介绍了本文的主要内容和组织结构。第二章主要完成片上网络布局问题的建模。首先采用任务图描述NoC应用任务，接着提出了IPCore分配和映射的评价模型，然后提出NoC布局的多目标问题以及Pareto最优解的定义，最后提出了带精英策略的非支配排序算法。第三章主要提出了基于空间冗余的容错结构及可靠性分析。首先分析了NoC的常见故障类型，介绍了在线故障检测方法，然后提出了基于空间冗余的容错结构，以恢复交换节点故障引起的通信中断，在此结构上设计了自适应的容错路由算法，最后进行了可靠性分析。第四章主要设计IPCore分配的智能算法MPDS和MPEL。首先介绍了相关智能算法原理，接着根据IPCore分配的需求和约束提出了MPDS算法和MPEL算法，16万方数据 第一章绪论并且描述了算法实现的详细过程，然后对算法进行分析，最后采用E3S的测试用例进行实验，并对比分析不同算法获得的实验结果。第五章主要设计IPCore映射的智能算法MSSU。首先分析了算法原理，接着根据IPCore映射的要求提出了MSSU算法，描述了算法实现的详细过程，然后对算法进行实验测试，采用E3S测试平台的数据进行实验，并用Nirgam仿真器对实验所得的布局方案进行仿真，对比分析仿真结果。第六章主要提出了基于彼得森图的可重构NoC布局结构，在此基础上设计了多值量子进化算法MQE，描述了可重构结构的实现方法，分析了MQE算法的实现原理和过程，最后采用典型的NoC测试用例进行实验，并对实验结果进行对比分析。第七章总结了全文内容，对未来研究方向提出了展望。17万方数据 电子科技大学博士学位论文第二章片上网络布局优化问题的建模与评价2.1布局优化问题描述IPCore分配是根据每一个子任务的类型从IPCore库中选择能完成该任务的IPCore。IPCore映射是为被选中的IPCoe在NoC拓扑结构中安排一个位于恰当位置的处理单元（ProcessElement，PE），该过程是基于子任务之间的通信关系和通信流量进行的，处理过程如图2-1所示。在NoC的设计中通常使用任务图(TasksGraph,TG)来描述NoC应用中的多SSSV1IP1ePEPEPE12V2e13IP2e32SSSV3分配映射e34e26IP3PEPEPEV4eVIP4SSS456e56V5PEPEPE子任务IPCoretile(a)(b)图2-1IPCore分配和映射过程(a)任务图；(b)基于tile的2Dmesh结构个子任务，以及子任务之间的数据交换关系，如图2-1(a)所示。任务图表示为TG=，TG是一个有向图，图中顶点集合V表示子任务的集合，边集合E代表子任务之间的通讯关系集合。vi∈V表示应用中的第i个子任务，箭头指向表示任务i和任务j之间的通信数据传输方向，边上的权值eij∈E，表示任务i和任务j之间通信的数据量。片上网络的映射结构可以表示为三元组(T(P,L),Rp,Ω(C))，其中T（P,L）表示网络拓扑结构，P表示处理单元(ProcessElem，PE)集合，L表示通信链路(Link)集合，{Rp（i，j）|i，j∈P}表示从第i个起点处理单元PE到第j个终点PE的路由规则。Ω：C->P,其中C表示IPCore集合，P表示处理单元PE的集合，Ω表示每个IPCore到处理单元PE的映射。18万方数据 第二章片上网络布局优化问题的建模与评价图2-1(b)所示的是基于tile的2Dmesh拓扑结构，该结构以其带宽高、结构简单、时钟周期短、可扩展性强，便于实现和分析等优点得到广泛应用。基于tile的2Dmesh结构主要由处理单元(ProcessElem，PE)和交换节点(Switch，S)以及连接链路(Link，L)构成。每个处理单元PE分别位于不同的tile中，每一个tile是由交换节点和链路围成的矩形块，每一个交换节点通过链路与相邻的交换节点连接。IPCore分配和映射都是具有高复杂度的组合优化问题，如果有N个子任务和NM个可选的IPCore,那么存在M种分配方案，如果有M个IPCore和N个可映[80]射的位置，那么存在N!/(N-M)!种映射方案。它们都是NP问题，解空间会随着问题规模的增大，急剧膨胀。目前常用的处理方式是通过智能优化算法求得近似最优解。2.2性能评价模型2.2.1IPCore分配方案的评价IPCore分配阶段首先要确保选择的IPCore能够执行所分配的任务，然后再根据评价指标选择最优的分配方案，该阶段没有涉及到IPCore的布局位置和通信关系，因此优化的评价指标为：计算功耗，计算时间和面积。(1)计算功耗累加每个IPCore映射的处理单元PE执行NoC应用中的子任务所消耗的计算功耗，计算方法见公式(2-1)。Powercomputingpt(2-1)tTG其中t表示NoC应用中的第t个子任务，pt表示执行第t个任务的PE完成该任务所产生的功耗。(2)计算时间NoC应用中的子任务可能存在并行执行的情况，不能直接累加每个任务的处理时间，应该要考虑并行执行对总时间的减少，也要考虑多个并行任务分配到同一个IPCore执行时，必须排队串行执行的时间。为了减少热点，我们设置在一个NoC应用中，每个IPCore最多可以分配两个子任务。因为计算时间应该包括关键路径上的任务执行时间和并行任务执行时间两部分，所以首先要找出任务图的关键路径，然后累加关键路径上的任务执行时间。当有并行任务与关键任务分配在同一个IPCore上时，则依次执行并行任务，相应的执行总时间将增加。由此所得计算方法见公式(2-2)。19万方数据 电子科技大学博士学位论文TmeicomputingTimetTimeParaptcritical-taskpcritiacl-taskiftaskpisexecutedinparallelandshareTimepthesameIPCoreswithcriticaltasks(2-2)TimeParap0others其中critical-task表示关键路径上的子任务集，子任务t表示关键路径上的子任务，Timet表示执行子任务t所消耗的时间。子任务p表示非关键子任务，Timep表示执行子任务p所消耗的时间。TimeParap表示当并行任务跟关键任务分配到同一个IPCore时，必须等前一个任务完成了，才能执行下一个任务，由此增加的计算时间。(3)面积累计分配给子任务的所有IPCore的面积，如果不同子任务分配到同一个IPCore则只算一次面积。面积计算方法见公式(2-3)。NAreacomputingAi(2-3)i1其中Ai表示第i个IPCore的面积，N表示在一个NoC应用中采用的IPCore的总个数。2.2.2IPCore映射方案的评价(1)通信功耗NoC应用的功耗主要包括计算功耗和通信功耗。前者是处理单元执行任务时的功耗，通常在IPCore分配阶段进行评估，在映射阶段主要评估通信功耗，通常是通过累计所有处理单元PE之间数据传输的通信功耗来计算。功耗可以分为静态功耗和动态功耗两类，静态功耗是指来自于漏电流(leakage[81]current)的功耗。参考文献中的数据显示在NoC的通信链路中，静态功耗在一般情况下远小于动态功耗，以70纳米技术为例，假设一条链路长度为3.5mm，链路-12-9-12上的动态功耗是0.6*10J。漏电流产生的静态功耗是(10.2*10w)*(233*10s)=-170.23766*10J。由此可以看到在NoC通信中，静态功耗远远小于动态功耗。本文只是评估比较各个映射方案的性能，只要能呈现各种方案的功耗差异即可，不用计算出精确的功耗值，因此主要考虑了动态功耗。但是随着深纳米技术的发展，以及低功耗设计的重要性，在今后的研究中将进一步考虑静态功耗。从处理单元i到j传送数据的通信功耗计算见公式(2-4)所示。20万方数据 第二章片上网络布局优化问题的建模与评价Powerij,P*hopP*(hop1)commlinki,jswitchij,(2-4)P表示每条通信链路上的功耗，P表示每个交换节点的功耗，交换节点linkswitch的功耗主要由三部分组成：缓存、交叉电路和仲裁，本文所使用的这两个功耗参[81-82]数值来自于Das等人提出的模型。hopij表示两个处理单元i和j之间的通信路径所经历的链路条数，即跳数。(2)通信时间NoC应用中的时间消耗主要包括计算时间和通信时间，计算时间在IPCore分配阶段进行考虑，通信时间在IPCore映射阶段进行考虑。本文主要是对比不同算法所得的NoC布局结构的性能优劣，没有进行精确的通信时间计算，而是对比了不同布局结构对通信时间的影响，本文建立的通信时间模型相对简单易行，同时也考虑了拥塞带来的时延，基本能反映出不同NoC布局结果对通信时间的影响，也能为算法性能的对比提供参考。所以在映射阶段，主要考虑的是通信时间对性能的影响，通信时间是数据在IPCore之间传输所花费的时间。因为子任务可能并行执行，所以不仅要累加最长路径即关键路径上的数据通信时间，同时也考虑了并行任务通信拥塞带来的额外的通信时间。通信时间的评价模型见公式(2-5)。Timecomm=(Tlink*hop+Ti,jswitch*(hop+1))+Ti,jpara(2-5)i,jcritpath其中i和j表示分配有关键任务（关键路径上的任务）的IPCore。hopij表示通信的两个处理单元之间的距离跳数，其中Tlink表示每一段通信链路上传输数据的时间，Tswitch表示在交换节点中路由缓存排队的时间，Tpara表示并行任务使用同一条链路传输数据排队等待的时间。并行任务共享同一条链路的时候要考虑两种情[56]况，一种情况是在同一个处理单元上的IPCore执行的并行任务发出的通信数据共享同一条链路；另一种情况是两个并行任务的通信数据发向同一个处理单元时共享同一条链路。如果在这些并行任务中包含有关键任务，那么通信的总时间必[81-83]然增加。本文采用的Tlink和Tswitch的参数值来自于Das等人提出的模型。(3)负载平衡链路负载平衡可以缓减通信网络的拥塞，减低排队等待的时延，同时避免产生通信节点的过热点。我们尽量把通信任务分散到不同的通信链路上，如果大量的通信任务集中在少数链路上，有可能导致网络拥塞和热点，因此我们在选择通信链路的过程中，尽量平衡每条链路上的负载。本文通过统计每条链路上的通信流量与所有链路平均流量的方差，对负载均衡情况进行评估，计算模型见公式21万方数据 电子科技大学博士学位论文(2-6)，在此基础上优先选择通信负载低的链路。LL2Loadi1loadi-i1loadi/L/L(2-6)其中loadi表示第i条链路上的通信流量负载，L表示通信链路的总条数。方差值越小则负载分布越均匀。2.3多目标优化求解2.3.1Pareto最优解在NoC设计中通常有多个优化目标，例如在IPCore分配阶段的计算时间、计算功耗和面积优化指标，在IPCore映射阶段的通信功耗，通信时间，负载均衡和可靠性优化指标等。这些优化目标中有的是相互冲突的，通常没有一个方法可以同时优化所有的目标。例如提高系统可靠性可能导致通信时间的增加，缩短通信距离可能导致负载方差的增大。如果采用单目标优化，以优化可靠性为例，具有高可靠性的方案通常需要较多的通信时间，这样系统的整体性能不高。因此需要采用多目标优化以实现多个优化目标之间的平衡。以IPCore映射为例，假设需要优化的目标是较少的通信时间，较小的负载方差和较高可靠性。为了方便描述，我们将可靠性指标reliability改成1-reliability，这样可靠性跟其他两个优化指标一样，转换成优化最小值的问题。假设有五个解，每个解的指标值如下表示：A(5,9,0.8),B(8,5,0.9),C(7,9,0.5),D(5,4,0.5),E(5,5,0.4)。每个三元组中从左到右的数字依次表示通信时间，负载方差和可靠性，为了便于分析此处忽略指标的量纲单位。对于单目标优化问题，假设优化最少通信时间，比较五个解的通信时间值，解A、D和E的通信时间一样，并且都是最小的，所以如果只是按照单目标优化，这三个解都是最优解。但是解A的通信时间虽然少，负载方差却偏大，而且可靠性也很低，总体性能不好。对于多目标优化，需要比较五个解的所有三个优化指标，采用非支配排序方法对解进行分层。解D和E的每一个评价指标值都小于或者等于其他解对应的指标值，再比较解D和E，可以看出D中的有些指标优于E，有些指标劣于E，难分伯仲，因此D和E标记为第一层。排除已分层的解，剩下的解A、B和C中，不存在一个解的所有指标值都优于其他指标，因此这三个解标注为第二层。我们把第一层的解作为首选，同一层的解可以一起提供给决策者做参考。基于以上分析描述，在评估过程中，单目标优化只考虑某一个优化目标，不22万方数据 第二章片上网络布局优化问题的建模与评价能获得整体的性能优化，多目标优化综合考虑了所有的优化目标以期获得整体的[84]性能最优。所以需要对多个目标进行协调，搜索Pareto最优解集，本文采用了带精英策略的非支配排序算法实现多目标优化。IPCore分配和映射的多目标优化模型见公式(2-7)。minimizeF(x)(f1(x),...,fm(x))(2-7)nsubjecttoxRn其中R是解空间,n在IPCore分配中表示备选IPCore的个数，在IPCore映射中nmm表示NoC拓扑结构中IPCore处理单元的个数。F:R->R，R是目标空间，由m个目标方程构成，也就是本文提出的NoC分配和映射方案的性能评价模型，见公式(2-1)至公式(2-6)，以及公式(3-1)所示，m是目标方程的个数，在分配和映射阶段根据优化目标的个数，m分别取值为3和4。由此所得非支配定义描述如公式(2-8)所示。nn定义2.1一个解向量vectorx1∈R支配另一个解向量x2∈R，当且仅当fk(x1)fk(x2),k1,...,m(2-8)fk(x1)fk(x2)foratleastonek.nn定义2.2对于一个可行解x∈R，如果不存在另一个解x*∈R支配它，我们称之为Pareto最优解，所有Pareto最优解构成的集合就是Pareto前沿即Pareto最优解集。为了在多个可能冲突的优化目标中需求平衡，以取得总体性能的提高，本文采用Pareto最优解集来替代单一的最优解，为设计者提供各个优化目标尽量平衡的总体性能最高的NoC布局方案。2.3.2带精英策略的非支配排序本文采用了带精英策略的非支配排序算法搜索Pareto最优解集，实现多目标优化。对所有的解进行非支配排序，并且将其分配到一定的非支配层次。Pareto最优解集的解标记为第一层，然后排除已标记的解，对剩下的解继续进行非支配排序，得到新的Pareto最优解集，即下一个非支配解集合，标注为第二层，以此类推，直到所有的解都标注了层次。进一步，我们根据支配层次选择高质量的解进入精英集合。同一层次的解，我们优先选择距离大的解进入精英集合。解的距离计算方法见公式(2-9)。NcrowdifCm(i1)fCm(i1)fCm(n1)fCm(0)(2-9)m123万方数据 电子科技大学博士学位论文其中Ci表示该非支配层中的第i个解，即第i种分配或者映射方案，C0表示该非支配层中的第一个解，Cn表示该非支配层中的最后一个解，fm(Ci)表示第m个评价指标函数，N表示评价函数的总个数。公式(2-9)中以第i+1个解和第i-1个解的评价函数的差值除以第n-1和第0个解的评价函数差值的计算，是为了减小不同评价指标的量纲差异。2.4本章小结本章主首先根据NoC应用的特点建立了应用模型任务图，以典型的2Dmesh结构作为拓扑结构，描述了布局的两个重要步骤IPCore分配和映射过程。然后建立了IPCore分配的评价模型：计算时间、计算功耗和面积；建立了IPCore映射的评价模型：通信时间，通信功耗和负载平衡。针对片上网络布局的多目标优化问题，描述了Pareto最优解集的定义，针对NoC布局优化问题，提出了带精英策略的非支配排序算法，并描述其实现过程。24万方数据 第三章容错机制及可靠性分析第三章容错机制及可靠性分析3.1故障检测机制3.1.1片上网络故障分析半导体工艺技术的发展使得集成电路的集成度大规模提高，片上系统的复杂性增加，同时引发各种故障问题的可能性也随之增大，对片上网络的系统性能构成了威胁。NoC常见的故障从时效性可以分为瞬时性故障和永久性故障。瞬时性故障也称为软故障，主要由外部电磁干扰、内部通信链路间的串扰等因素导致的逻辑值、数据位错误等故障。瞬时性故障发生的时间和位置具有一定的随机性，通常采用重传或者纠错等方式来提高可靠性，常见解决方法如下：(1)信息备份：从源结点向目的结点发送多个信息备份，该方法可能增加通信代价，产生网络拥塞，所以适用于通信量较小的NoC。(2)纠错码：在数据包中添加检错或者纠错的冗余码，该方法在数据包中增加了额外的信息，因此可能降低数据包的有效负载。(3)应答确认：源结点发送数据后，等待目的结点发回确认信息，如果在规定时间内没有收到确认，则重传数据，该方法在应答确认过程中会增加系统时延，适用于对响应时间要求不高的NoC。永久性故障也称为硬故障，主要由制造工艺或者制造过程中产生的元件缺陷、电子击穿和栅氧击穿等元件老化原因引起的故障，发生永久性故障的元件通常无法逆转，从而导致通信节点和通信链路失效，数据包丢失，甚至系统通信中断。解决永久性故障的常用方法是：(1)更换硬件：更换NoC芯片上出现故障的元件，甚至更换整个芯片，更换硬件的过程是费时费工的。(2)冗余硬件：在NoC的结构中增加部分冗余元件，例如冗余的交换节点和通信链路等，当某些元件出现故障时启动冗余硬件保证NoC通信畅通。该方法会增加硬件开销，增大NoC面积，适用于硬件资源充分，且对面积要求不高的NoC系统。(3)冗余路径：为通信节点之间建立多条冗余路径，当一条路径发生故障时，采用其他路径恢复通信。该方法没有增加额外的硬件开销，只是利用了NoC的网络互连结构建立多条通信路径。冗余路径相比其他容错方法具有一定的优势，冗余路径的构建策略也一直是研究者关注的热点问题，主要包括如何设置冗余路径25万方数据 电子科技大学博士学位论文的数量，选择哪些链路或者网络节点来构建冗余路径，如何在恢复通信的同时兼顾系统性能等。本文是在设计NoC布局的过程引入容错机制，NoC布局主要是安排硬件的位置及连接方式，该阶段主要涉及的是硬件故障容错，因此本文主要针对交换节点的永久性故障，采用容错结构和容错路由来恢复由此引发的通信中断，同时兼顾系统性能。3.1.2在线故障检测及定位方法采用容错机制提高系统可靠性的前提是要检测出错误，然后再针对错误采取相关的容错措施。通信故障的出现具有一定的随机性，因此自动检测片上网络故障的机制一直是研究和关注的热点。在采用故障检测和纠错机制来保证通信系统可靠性的同时，会考虑实施容错结构带来的其他开销和代价，复杂的检错方案可能会比较准确地检测出故障，但是也可能带来较大硬件代价或者功耗和面积等开销，在一定程度上影响系统的总吞吐量和时延。所以需要设计有效的检测机制，既可以实现NoC在线故障检测，又不会增加太多额外的开销，具有一定的灵活性，可以通过软件或者硬件方式来实现检测。故障检测使用较广泛的方法是：奇偶校验码(paritycheckcode)和双轨编码(dual-railcode)。奇偶校验码方法通过在数据片中增加一个校验位来检测故障，双轨编码方法需要增加更多的物理连线用于传输每一位数据的原始信息和增加的校验信息。虽然后者检测效果更好，但是会增加更多的系统开销。[85]NoC的故障检测可以分为两类：端节点之间的检测方式(end-to-end，EtoE)和交换节点之间的检测方式(switch-to-switch，StoS)。端节点端节点处理单元处理单元(PE)(PE)编码解码交换交换交换交换节点节点节点节点图3-1端节点之间的检测方式EtoE26万方数据 第三章容错机制及可靠性分析EtoE检测过程如图3-1所示，把故障检测码加入数据包，在端节点的发送接口和接收接口都要分别进行编码检测，接收端根据数据的接收情况，向发送端发出NACK或者ACK应答确认信号，传输的数据缓存在发送端，如果发送端接收到NACK信号则表示发送不成功，重传数据；如果收到ACK信号则表示发送成功，清除发送缓存的数据。端节点端节点处理单元处理单元(PE)(PE)编解编解编解交换交换交换交换码码码码码码节点节点节点节点图3-2交换节点之间的检测方式StoSStoS检测过程如图3-2所示，在每两个相邻交换节点之间都要进行故障检测，数据进入和离开每一个交换节点都要进行校验，传输的数据缓存在每一个交换节点处，在端节点收到NACK信号时需要重传，直到端节点收到ACK确认信号才清除缓存。以上两种方式均需要大量用于重传的数据缓存，由此也带来了更多的系统开销，采用的校验位和应答信号增加了数据负载，并且不能确保重传机制能使数据通信恢复正常。在EtoE检测中，如果是发生了永久性故障，重传数据在原有的通信路径上依然不能正常传输，因此需要先定位错误发生的地点，再重新路由，然后再发送重传的数据，但是EtoE方式无法定位故障位置，因为故障检测仅仅在端节点处执行。StoS方式可以定位故障错误，因为数据经过每一处交换节点都需要进行故障检测。本文采用了一种在线检测和定位故障的方法，该方法采用了基于Code-disjoint[85]的故障检测机制。可以精确定位故障发生的位置，可以区分错误类型是通信链路故障还是交换节点内部故障。并且实现方法简单易行，不需要增加太多的额外开销。该方法实施的检测位置与StoS检测过程类似，数据包在进入和离开交换节点的时候都需要进行故障检测。NoC交换节点的功能是根据路由信息，为从输入端口进入的数据包选择合适的输出端口，并且输出数据。交换节点不仅只有简单的组合连接电路，其结构包括控制部分、数据传输部分和校验部分。控制部分决定27万方数据 电子科技大学博士学位论文由哪一个端口输出数据，数据传输部分构成了从输入端口到输出端口的通路，校验部分用于计算校验位的值，如图3-3所示。端口3校验计算PoutPcout校验计算缓冲队列缓冲队列PinPoutMin路由决策Mout端口1端口2校验计算PcinPin校验计算端口4图3-3具有故障检测功能的交换节点结构示意图图3-3展示了基于Code-disjoint的具有故障检测功能的交换节点结构，在实际的交换节点结构中，每对端口之间应该有两组通道，分别用于输入和输出，为了简化图的表示，更清晰地表示结构的工作原理，在该图中只画出了一组输入或输出通道，主要展示了传输数据从端口1输入，经过交换节点的校验检查，然后从端口2输出的过程，具体过程如下描述：数据从端口1进入交换节点，输入的数据包括数据片Min和其校验位Pin。通过校验计算模块对数据片进行计算，产生实际的计算校验位Pcin。比较输入校验位Pin和计算校验位Pcin的值，如果匹配成功则表示没有发生故障，如果匹配不成功则表示有故障发生，并且可以确定故障是发生在数据包进入交换节点之前，可能是前一个交换节点的故障，也可能是进入该交换节点之前的链路故障。如果检验结果是没有发生故障，则通过路由决策模块仲裁确定输出端口的编号，再将输入28万方数据 第三章容错机制及可靠性分析数据送到合适的输出端口，此处假设输出端口是端口2。输入数据Min到达输出端口后标记为Mout，输入校验位Pin到达输出端口后标记为输出校验位Pout。数据输出之前再次进行校验计算，Mout通过校验计算模块得到实际校验位Pcout。比较Pout和输出校验位Pcout，如果两者匹配成功则表示没有检测到故障，数据通过输出端口离开该交换节点，进入下一条通信链路。如果匹配不成功，则表示检测到故障，并且故障是发生在该交换节点内部。3.2基于空间冗余的容错结构[86]容错策略近年来得到广泛的研究。容错策略通常包括容错结构和容错路由，根据出现故障的链路或者节点位置，容错路由分为局部容错和全局容错两类。本文首先提出了基于空间冗余的容错结构，然后在此基础上提出了容错路由，主要是根据故障位置，实现局部重路由。[87-89]Bogdan等人提出了一种随机通信的方法用于故障的容错处理，通过覆盖[90]率仿真模拟验证随机通信；Murali等人综合考虑了可靠性策略和多路径策略，[91]通过向多条路径发送数据备份来获得数据的冗余；Sanusi等人提出了一种智能[92]洪泛法进行容错处理；W.Song等人提出了自适应的随机路由，该方法发送探测数据片flit去探测网络状况，并且存储经历的路径信息，在此基础上自适应地选择[93][94]合适的路径；Zimmer等人以Nosturm结构为例提出了容错算法；Chen等人[95]提出了一种基于数据片序列的容错方法；Ren等人针对NoC的容错，提出一种[96][97]基于网格的容错算法；Sethi等人提出了一种启发式的NoC容错算法；Jafri等人[98]提出了在功耗约束下的NoC容错结构；Hsieh等人提出了一种3D片上网络的容错结构。上述算法中大多数是基于随机通信或者洪泛方式，这类算法通常需要对数据复制多份，然后发送到多条路径，这些方法可以有效解决瞬时故障和永久故障，获得高标准的容错，但是采用洪泛方法通常会产生大批的数据副本，并且在网络中进行传输占用大量的带宽，我们研究的是片上网络布局结构中的容错方法，主要涉及到的是与硬件有关的永久性故障，这一类故障发生的频率并不是特别频繁，没有必要占用大量的带宽采用洪泛类的容错方式，因此我们采用了冗余路径和重路由方式来获得容错。该方法可以有效实现容错，同时不会增加硬件开销或者其他的通信代价。基于随机通信和洪泛的容错方法是属于信息冗余，冗余路径是属[93]于空间冗余，前者适用于瞬时和永久故障，后者适用于发生概率相对较低的永久故障。交换节点发生故障时，可以更换掉出现故障的交换节点，但是那样会花费较29万方数据 电子科技大学博士学位论文故障交换节点的位置路径的末端路径的中间故障节点和替换节点起点处理单元和终点之间的位置关系处理单元的位置关系同行同列同行异行终点处理单元终点处理单元和替换节点的和替换节点的位置关系位置关系在故障节点的异侧在故障节点的同侧在故障节点的异侧在故障节点的同侧X-Y路由Y-X路由图3-4重路由算法决策树大的代价，而且在芯片上更换交换节点的操作不太容易实施，有时候是直接更换整块芯片。所以我们选择建立冗余路径，利用芯片上已有的交换节点，作为路径的冗余交换节点，当某些节点发生故障时，系统还可以继续工作。当然冗余节点也并不是永远有效，也可能坏掉，当多个交换节点出现故障，系统性能受到严重影响时，就需要替换掉发生故障的节点，或者整块芯片。冗余路径是一条新路径，它跟原来的路径具有相同的起点和终点，可以绕过故障交换节点，构建冗余路径的过程如下：从通信的起点处理单元开始，通过X-Y或者Y-X路由搜索一条路径，该路径能确保是最短路径而且不会发生死锁，当遇到故障交换节点时，就选择其相邻交换节点作为替换，直到到达终点处理单元。为了增强系统可靠性，为每个IPCore选择一定数量的相邻交换节点作为冗余节点，采用容错路由算法，建立冗余通信链路，以确保当路径上的某个交换节点出现故障后，可以通过冗余链路完成通信任务。本文的重路由算法可以自适应地选择X-Y或者Y-X路由算法，以获取最短路径，同时避免死锁。根据发现故障的交换节点的位置可分为两种情况，端交换节点和中间交换节点，在此基础上，我们设计了自适应的重路由算法，以期在恢复通信的同时获取最短通信路径。重路由决策树如图3-4所示。30万方数据 第三章容错机制及可靠性分析SRCSRCDESDES(a)(b)SRCDESSRCDES(c)(d)图3-5故障交换节点与起点PE连接的四种路由情况分析(a)X-Y路由情况：故障节点和替换节点在同一行，终点PE和替换节点在故障节点的同一侧；(b)Y-X路由情况：故障节点和替换节点在同一行，终点PE和替换节点在故障节点的不同侧；(c)Y-X路由情况：故障节点和替换节点在同一列，终点PE和替换节点在故障节点的同一侧；(d)X-Y路由情况：故障节点和替换节点在同一列，终点PE和替换节点在故障节点的不同侧3.3自适应容错路由算法设计路由算法过程如下：首先根据每个IPCore的流量确定冗余交换节点的个数。因为具有较高流量负载的IPCore对系统性能的影响大于低负载的IPCore，所以为其设置更多的冗余交换节点，这样在建立高性能的冗余路径的时候就可以有更多的替换路径可选择。然后根据映射位置和子任务之间的通信流量计算每个交换节点上的流量负载，按照负载从低到高的顺序选择冗余交换节点，直到达到预定的个数。根据故障交换节点的位置，分三种情况选择路由，具体描述如下：31万方数据 电子科技大学博士学位论文(1)故障发生在起点即与起点处理单元PE连接的交换节点，如图3-5所示，其中黑色圆圈表示发生故障的节点，灰色圆圈表示可用于替换的冗余节点，标记为SRC的是起点处理单元PE，标记为DES的是终点处理单元PE。替换节点是从相邻的冗余节点中，按照流量负载从低到高选择出来的，这样可以使流量分布尽量均衡，以减少拥塞发生。冗余路径采用被选择的冗余节点作为起点，依然以终点处理单元作为终点，根据图3-4所示的重路由决策树，自动选择X-Y或者Y-X路由建立而成。图3-5显示了四种路由选择的情况。(2)故障发生在与终点PE相连的交换节点，替换的节点依然从相邻的冗余节点中按照流量负载从小到大进行选择，然后以起点处理单元PE作为路由起点，被选择的替换节点作为终点，按照自适应的路由算法选择通信链路和节点，建立冗余路径，其路由选择的过程类似于故障发生在起点处的情况，即上文(1)中所描述的情况。综合(1)和(2)两种情况，可以得出处于端节点位置的交换节点发生故障的路由算法如下：EndFault-tolerantRoutingAlgorithm//TheredundantswitchandsourcePEareatthesamerow1{if(rowRedund==rowSrc)2if(rowSrc==rowDes)3{if(colRedundprobabilitycross9crossOperator(individuali);10ifrandom()>probabilitymutation11mutationOperator(individuali);12}//for13foreachindividualiinnewP(t)14computeFitness(individuali);15store(bestindividual);16P(t)=newP(t);41万方数据 电子科技大学博士学位论文17t=t+1;18}//while19output(bestindividual);20}由上述算法描述可以看出，迭代次t=1时,首先产生初始种群P(t)，计算每一个初始个体的适应度computeFitness，然后开始遗传迭代：从种群P(t)中选择适应度高的个体newP(t)进入下一步操作，如果个体满足交叉概率probabilitycross，则执行交叉算子crossOperator，如果个体满足变异概率probabilitymutation，则执行变异算子mutationOperator，计算新个体的适应度，保存当前最优个体bestindividual，迭代次数t加1，进入下一次迭代。重复迭代过程直到满足迭代终止条件，输出适应度最高的最优个体bestindividual。4.1.3模拟退火算法原理模拟退火算法(SimulatedAnnealing，SA)是一种求解最优化问题的智能算法，其主要思想是模拟物理学中固体物质退火的过程，其主要特征是局部搜索方法和概率跳变策略结合，逐步向全局最优解接近。模拟退火算法在解的搜索过程中不依赖初始条件，适用范围广，可以处理任意约束条件的评价函数，广泛应用于组合优化等领域。模拟退火思想最早是在1953年由Metropolis等人提出，模拟了固体达到热[103]平衡的过程，在此基础上Kirkpatrick等人分析了固体退火过程与组合优化问题之间的关联性，于1983年提出了将迭代Metropolis过程用于解决组合优化问题的算法，即模拟退火算法。退火过程是指固体在高温状态下，粒子具有较高热能，呈现随机无序的排列状态，离开原来位置，在其他位置中随机移动。随着温度的逐渐降低，粒子的热运动减缓，热能降低，逐渐排列有序，趋于稳定。当到达一定的低温时，所有的粒子达到稳定状态。模拟退火算法从一较高的初始温度开始，在解空间中进行搜索。从初始解开始，在其临近解集中随机移动产生新解，根据评价函数和当前温度值依概率判断是否接受新解，重复上述过程直到满足预设的迭代终止条件。然后根据降温系数降低温度，继续在当前解的临近解集中搜索新解，直到达到终止温度。由此得到的评价函数值最优的解即可能是近似最优解。每次产生的新解是否被接受，通常采用Metropolis方法进行判断，在该方法中当温度较高的时候，新解被接受的可能性较大，具有较强的随机性，当温度较低的时候，新解被接受的可能性较小，42万方数据 第四章IPCore分配的智能优化算法设计算法逐渐收敛。模拟退火算法的基本步骤如下：(1)初始化参数值：设置初始温度T，产生初始解S，设置在每个温度上的迭代次数L。(2)在当前解的邻域解集中进行搜索，产生新解S'。(3)计算当前解和新解的评价函数E(S)和E(S')，计算增量ΔE=E(S')-E(S)。(4)若ΔE<0则接受S'，否则依概率exp(-ΔE/T)接受S'作为新解。(5)重复第(2)-(4)步操作，直到满足迭代次数L，则转向第(6)步。(6)判断是否到达终止温度，或者是否已满足预设的终止条件，如果没有则根据降温函数降低温度T，然后转到第(2)步执行。如果已经达到终止温度或满足预设条件则算法终止。标准的模拟退火算法描述如下：SimulatedAnnealingAlgorithm1{initial(T);//Tisatemperature2generateSolution(S);3valuation(S)E(S);4while(notreachingtheterminationtemperature)5{L=1;//Listhenumoflocalsearching6while(notreachingtheterminationvalueofL)7{S’=search(neighborofS);8valuation(S’)E(S’);9△S=E(S’)-E(S);10if(△S<0)11{accept(S’);12S=S’;13}14elseif(exp(-ΔE/T)>Random(0,1))15{accept(S’);16S=S’;17}18L=L+1；19}//while20T=T*decay;//decayiscoolingrate43万方数据 电子科技大学博士学位论文21}//while22}根据以上算法描述可以看出，模拟退火算法首先设置初始温度T，计算初始解S并且以S作为当前解，计算当前解S的评价函数值，接着开始迭代过程：在当前解的邻域中搜索新解S’，如果新解评价函数值小于当前解S，则接受新解S’，把新解作为下一次搜索的当前解，否则按照概率exp(-ΔE/T)判断是否接受新解S’，重复邻域搜索迭代过程直到满足预设的邻域搜索次数，然后降低温度T，开始新一轮的迭代，直到达到终止温度。4.2MPDS算法设计4.2.1算法设计原理及分析粒子群算法是通过将个体的最优解与群体的最优解进行结合，生成下一代个[104]体。因为其收敛速度快和易实现等特性，经常应用于复杂问题求最优解。但是该算法在搜索过程中，所有粒子逐渐向搜索空间的当前最优解靠近，容易陷入局[105]部最优。所以本文分别采用遗传算法的遗传算子和模拟退火算法的局部搜索策略对基本的粒子群算法进行优化。本节是采用遗传算子进行优化所得到的改进算法，该算法是以粒子群和遗传算法为基础的带多样化策略的多目标优化算法MPDS(multi-objectivePSOwithdiversifyingstrategies)。本文提出的这个优化算法是在标准粒子群算法基础上，首先实施遗传选择算子，然后根据改进的粒子群更新公式对粒子进行更新，接着对更新后的粒子实施遗传变异操作。由此所得的混合优化算法中引入的选择算子有利于提高解的质量，变异算子可以有效地避免过早地陷入局部最优，算法的详细实现过程如下所述。4.2.2解的表示和更新方程每一个粒子都是一个潜在的解，在这里是表示一个NoC的分配方案，粒子的维度由NoC应用中子任务的个数所决定，表示为d。粒子的位置表示为向量p=(p1，p2，……pi…...pd)，pi表示分配给第i个子任务的IPCore编号，例如p=(5,3,4,6,0,8,7,2,1),第一个元素是5，表示IPCore5分配给第一个子任务，第二个元素是3，表示IPCore3分配给第二个子任务，以此类推。为了满足NoC映射的需要，我们改进了标准的粒子更新公式，设计了对换算子和对换度。对换算子是对粒子中元素的位序进行对换，见公式(4-1)所示。PsourceXPdestination(4-1)44万方数据 第四章IPCore分配的智能优化算法设计①②13572468③Psource④①②24571368③④Pdestination图4-2对换操作其中Psource表示原粒子，X表示对换度，即进行对换的元素的个数。Pdestination是对换原粒子中的某些元素之后得到的目标粒子。例如：如果Psource=(1,3,5,7,2,4,6,8),X=4,那么Pdestination=(2,4,5,7,1,3,6,8)。这表示原粒子中的四个元素位序对换之后，得到的目标粒子，对换过程如图4-2所示。在此基础上，我们给出位置和速度的更新公式，见公式(4-2)。Vt1Vtc1rand1(pBestVt)c2rand2(gBestVt)(4-2)Pt11PVtt其中Vt和Pt分别表示粒子在t时刻的速度和位置，+表示对换操作，是惰性因子，用于控制保留粒子当前速度的比例，c1是局部学习因子，c2是全局学习因子，均为非负数，rand1和rand2是[0,1]区间内服从均匀分配的的随机数。pBest-Vt是指粒子相对于局部最优解的对换度，gBest-Vt是粒子相对于全局最优解的对换度，粒子[106]的位置根据对换后的速度进行更新。4.2.3算法实现过程MPDS算法的主要步骤如下：(1)产生初始种群，种群的大小以N表示，初始种群的粒子随机产生，每个粒子的初始值作为它们的个体最优解初值，即局部最优解，在所有局部最优解中，选择最优粒子作为全局最优解初值。(2)计算适应度，根据评价指标函数计算每个粒子的适应度。(3)非支配排序，根据每个粒子的适应度对粒子进行排序，把粒子分配到对应的非支配层次。(4)根据非支配排序的结果，更新全局最优和局部最优粒子。45万方数据 电子科技大学博士学位论文(5)实施选择算子，选择处于较高非支配层的、高适应度的粒子进入下一步操作。在选择过程中，采用了轮盘赌算法，根据每个粒子的适应度计算其选择概率，选择概率能确保高适应度的粒子有更多被选中的机会。选择步骤描述如下：首先为每一个粒子根据其适应度分配一个数字区间，然后产生一个随机数，观察随机数位于哪一个数值区间，则对应的粒子被选中。为具有较高适应度的粒子分配较宽的数值区间，则其被选中的机会也较大。(6)更新粒子，根据公式(4-2)更新粒子的速度和位置。(7)实施变异算子，变异算子以较小的概率Pm作用于粒子。因为在NoC分配算法中，粒子中的每个元素表示一个可以完成对应位序的子任务的IPCore，所以在变异操作时不能完全随机的改变变异元素的值，必须在能够完成当前子任务的IPCore备选库中随机选择一个作为变异元素的值。通过这种方式，可以避免产生无效的解。(8)根据评价指标函数，计算所得新粒子的适应度。(9)判断是否满足迭代终止条件，如果满足则输出当前全局最优解，算法停止，否则回到第(3)步继续迭代操作。根据以上步骤可得MPDS算法描述如下所示：MPDSAlgorithm1{generateInitialSwarm(particles);2multi-objectiveevaluation(particles);3non-dominatedsort(particles);4select(pBest);//localbest5select(gBest);//globalbest6while(notreachingtheterminationcondition)7{betterParticles=select(particles)usingrouletteselection;8update(betterParticles);9newParticles=mutationoperating(betterParticles);10multi-objectiveevaluation(newParticless);11non-dominatedsort(newparticles);12update(pBest);update(gBest);//updatelocalbestandglobalbest13particles=newParticles;14}//while15output(gbest);16}46万方数据 第四章IPCore分配的智能优化算法设计在上述算法描述中，首先产生初始粒子群particles,按照多目标优化函数计算每个粒子的适应度进行评价multi-objectiveevaluation，对粒子进行非支配排序non-dominatedsort，从中选择初始的局部最优粒子pBest和全局最优粒子gBest。开始迭代过程，采用轮盘赌方法rouletteselection选择适应度较高的粒子betterParticles，根据公式(4-2)更新选中的粒子，实施变异操作得到新的粒子群newParticles，按照多目标评价函数计算新粒子的适应度，并且进行非支配排序，更新局部最优和全局最优粒子，对新粒子群开始开始下一轮的迭代。重复迭代过程，直到满足迭代终止条件，则输出全局最优粒子作为最优解。4.3MPEL算法设计4.3.1算法设计原理及分析在这一节我们基于粒子群PSO和模拟退火算法(SimulatedAnnealing，SA)思想设计了强化局部跳变的多目标优化算法MPEL(multi-objectivePSOenhancinglocality)，该算法中解的表示和粒子更新方法，跟上文描述的MPDS算法中对应方法一致，在此不重复描述。SA是一种模拟固体退火的算法，提供了一种概率跳变机制以脱离局部最优解。在SA算法中没有隐含的并行计算，它的搜索过程开始于一个解，在每一个优化步骤中都将获得一个解。在本文提出的改进算法中，采用PSO构建算法主体框架，SA算法作为PSO一个增益。PSO算法跟GA类似，具有隐含的并行计算。搜索过程开始于一个解集，在每一步都可以获得多个解，但是PSO的搜索仅参考了当前最优解和全局最优解，导致易陷入局部最优。而SA算法可以依概率接受一个更差的解，这个差解在迭代搜索中有可能最终引导出更好的解。按照这种方式，SA可以减少陷入局部最优的可能性，所以在PSO中引入SA算法的局部搜索进行改进是有效。PSO算法首先提供初始解，当前种群的粒子根据PSO的更新公式进行更新，然后再采用SA算法的局部搜索策略对粒子进行邻域搜索。在执行邻域搜索后，按照公式(4-5)所计算的概率，允许从当前解跳变到一个更差的解，这种跳变有可能在后继阶段引导出一个更好的解。改进的MPEL算法很好的协调了全局搜索和局部搜索，提高了解的质量。4.3.2局部搜索强化过程实现局部搜索的主要方法如下所示：(1)参数设置：设置初始温度T0，见公式(4-3)。47万方数据 电子科技大学博士学位论文TmaxFun((f))(4-3)0i其中△fi表示各个解之间的第i个评价指标的最大差值，Fun()用于对评价指标做标准化处理，采用各个指标的最大标准差作为初始温度，设置终止温度Tend.，设置局部搜索次数L。(2)邻域的定义：我们把与当前粒子中的元素在位序上有两个不同的粒子所构成的集合定义为当前粒子的邻域。邻域粒子可以通过随机选择当前粒子的两个元素进行对换产生。(3)接受公式：按照公式(4-4)计算粒子与其邻域粒子评价指标差值。difneighbori()fcurrenti()(4-4)其中di表示第i个评价指标的差值，fi表示第i个评价指标函数，i=1,2,…N。N是评价指标的个数。如果邻域粒子的所有指标均优于当前粒子，则接受该粒子，否则按照公式(4-5)计算概率p0,依此概率接受邻域粒子。p0expfT/(4-5)fmaxabsdii/fcurrent()1iN其中T表示当前温度，N表示评价指标的个数，abs表示绝对值计算。(4)降温：根据公式Tt+1=Tt*decay，进行降温计算，在更低的温度下进行下一次迭代操作，其中decay表示降温系数。(5)产生下一代种群：计算新产生粒子的评价指标，进行非支配排序，更新全局最优和局部最优解，根据非支配层次选择高质量或者多样化的粒子进入下一次迭代。4.3.3算法实现过程基于上述分析，我们得到MPEL算法描述如下：MPELAlgorithm1{generateInitialSwarm(particles);2multi-objectiveevaluation(particles);3select(pBest);//localbest4select(gBest);//globalbest5while(notreachingtheterminationcondition)6{update(particles);7foreachparticlei48万方数据 第四章IPCore分配的智能优化算法设计8{ifrandom()>probabilitylocal//probabilityoflocalsearch9{initialize(T);//Tisatemperature10S=particlei;11multi-objectiveevaluation(S)E(S);12while(notreachingthefinaltemperature)13{initialize(L);//Listhenumberoflocalsearch14while(notreachingthefinalvalueofL)15{S’=search(neighborofS);16multi-objectiveevaluation(S’)E(S’);17△S=E(S’)-E(S);18if(△S<=0)19{accept(S’);S=S’;}20elseif(exp(-ΔE/T)>Random(0,1))21{accept(S’);S=S’;}22L++；23}//while24T=T*decay;//decayiscoolingrate25}//while26}//if27}//for28multi-objectiveevaluation(particles);29non-dominatedsort(particles);30update(pBest);//localbest31update(gBest);//globalbest32}//while33output(gbest);34}通过上述算法描述可以看出，MPEL算法首先按照标准PSO算法产生初始粒子群particles，根据多目标评价函数计算每个粒子的评价值multi-objectiveevaluation，确定当前局部最优粒子pBest和全局最优粒子gBest，然后开始迭代过程：根据公式(4-2)对粒子进行更新，判断粒子是否满足局部搜索概率probabilitylocal，49万方数据 电子科技大学博士学位论文如果满足，则对该粒子按照SA算法进行局部搜索，步骤如下：设置初始温度T，以该粒子作为搜索起点即当前粒子S，取得S的邻域粒子S’，计算当前粒子和邻域粒子的评价函数差值△S，如果差值小于等于0，则接受邻域粒子S’，以它作为新的搜索起点，如果差值大于0则以概率exp(-ΔE/T)接受邻域粒子S’，重复搜索邻域粒子的过程直到满足预设的局部搜索次数L，然后降低温度T，启动下一轮的邻域粒子搜索操作，直到到达终止温度则停止该粒子的邻域搜索操作。对所有满足邻域搜索概率的粒子完成操作之后，计算得到的新粒子的评价函数值，重新确定局部最优粒子pBest和全局最优gBest，至此完成了一次粒子群的迭代，重复上述迭代过程，直到满足迭代终止条件，输出全局最优粒子gbest即是问题的最优或者近似最优解。4.4算法分析本文提出的改进算法是一种混合智能算法，当前对混合算法的收敛性分析通常是基于实验和经验进行，很少有展开理论分析的。本文采用数学推导的方法对所提出的混合算法的收敛性进行了分析。为了便于推导，将粒子更新公式(4-2)改写为公式(4-6)和(4-7)。Vt1Vt1*(pBestPt)2*(pBestPt)Pt(4-6)Pt11PVtt(4-7)其中1c1*rand1，2c2*rand2，rand1和rand2仍然是[0,1]区间服从均匀分配的随机数。因为c1和c2是两个非负数，所以1和2也是非负数，是惰性因子，01，是改进算法的扰动参数，在MPDS算法中表示变异概率，在MPEL算法中表示局部搜索参数，并且0。把公式(4-6)带入(4-7)可得迭代公式(4-8)。Pt1(112)PtPt11*pBest2*gBest(4-8)用矩阵向量乘积的方式改写公式(4-8)，得到公式(4-9)。ptt11121pBest2gBestppp100(4-9)tt110011公式(4-9)的特征方程如公式(4-10)所示。2[(112)](1)0(4-10)计算可得特征值如(4-11)所示。50万方数据 第四章IPCore分配的智能优化算法设计121112112421221121124(4-11)231[107]F.vandenBergh证明了标准PSO算法中的收敛条件如公式(4-12)所示。pBestgBestlimp12iffmax1(4-12)tt1213ii对混合算法的收敛性分析是基于此公式进行的。为了便于分析，把12带入公式(4-11)，简化特征值的表示，显然是非负数。分别按照以下两种情况进行分析：2(1)1422特征值是实数，相当于1或者1。2当1时max=1112412i=2需要满足1且01。1i322当1时max122i=1=1141需要满足12(1)且1i3201。2(2)1422特征值是复数，相当于11max12222i=1141需要满足11且1i3401。综合两种情况，迭代方程的收敛条件表示为公式(4-13)所示。01,02(1)即0c1*rand1c2*rand22(1)(4-13)此处是混合参数，在MPDS算法中表示变异因子，在MPEL算法中表示局部搜索参数，用来控制当前粒子相对于全局最优解的对换度。rand1和rand2是[0,1]区间服从均匀分配的两个随机数。如果rand1和rand2取它们的上界值1，那么c1和c2表示对换元素的最大值。显然0≤c1,c2≤d。当rand1=rand2=1,=1,我们可以获得收敛条件的上界值，如公式(4-14)所示。51万方数据 电子科技大学博士学位论文c12c2(1d)(4-14)基于上述分析，改进的混合算法当参数满足公式(4-14)所示的条件，则算法收敛。接下来讨论混合算法中使用的参数值，以3*3的2Dmesh拓扑结构为例，粒子的维度d=9，c1和c2分别表示相对于局部最优粒子pBest和全局最优粒子gBest,对换元素个数的上界值。参数选择主要是基于实验和经验，在实验过程中，结合经验调整参数进行多次尝试。为了更好的选择参数值，此处不仅考虑了IPCore分配的性能，也综合考虑了对下一阶段IPCore映射的性能影响，因此对比分析了四个评价指标。表4-1列出了参数c1和c2取值组合所得到的四个评价指标值。为了方便比较，在表中最后一列中列出了四个指标在归一化处理之后，加权平均的综合评价值，权重分配为：加权平均值=功耗*0.3+时延*0.3+(1-可靠性)*0.3+负载方差*0.1。表4-1参数c1和c2不同组合值对性能影响对比功耗时延负载方差c1c2可靠性加权平均(10e-6J)(10e-8s)(10e-1)222.047.630.73037.00.3792242.038.440.7113.560.3833262.017.680.6982.810.2659282.057.270.75130.10.3193422.156.540.67217.20.3319442.007.950.72017.40.3226462.056.790.75630.10.2520482.238.720.68727.50.7665622.017.170.73817.10.2250642.067.980.70629.70.4447662.017.130.7082.810.1868682.137.120.73717.70.3780822.007.280.7103.000.1923842.056.530.74929.20.2159862.017.130.7242.190.1801882.018.190.7512.910.3194因为我们采用的是随机算法，计算具有一定的不确定性，所以对应每一对c1和c2的取值组合，分别测试10次，选择最优值作为对比。因为版面空间限制，列出了部分实验结果见表4-1，从表中可以看出，当c1=8,c2=6时可以获得最优的加权52万方数据 第四章IPCore分配的智能优化算法设计平均值。在MPDS算法中，通过对换两个元素实现变异操作，因此混合因子=2，在MPEL算法中，邻域粒子定义为与当前粒子位序相差两个元素的粒子，因此扰动因子=2。由此可见，本文算法选择的参数满足公式(4-14)的条件，在给定参数的约束条件下，MPDS算法和MPEL算法是收敛的。4.5实验及结果分析将本文提出的算法应用于测试平台E3S（EmbeddedSystemsSynthesis[108]benchmarksSuite）。E3S测试平台提供了一组NoC的应用实例和IPCore备选库，E3S提供的任务图均来自于真实的应用，并且给出了任务完成的时间约束等参数。IPCore备选库中包含了多种嵌入式处理器，并且提供了每种处理器的相关参数。本文对E3S平台中七个典型的测试用例采用不同算法进行了测试。测试的目标是在满足时间和功耗的约束条件下尽可能多地获得可行解，即IPCore分配方案。表4-2列出了通过不同算法获得的满足条件的IPCore分配方案的个数。可以看出本文提出的MPDS算法和MPEL算法获得的解的个数，多于传统[56]的智能算法非支配排序遗传算法(NSGAⅡ)和粒子群算法(PSO)所求解的个数，其中非支配排序遗传算法NSGAⅡ是在遗传算法的基础上，增加了多目标优化的思想。因为本文算法在标准PSO基础上，通过遗传算子和局部搜索等策略改进，减少了陷入局部最优的可能性，所以可以搜索到更多的高质量的解。在CPU2.66GHz的计算机上，MPDS算法上运行七个测试用例平均耗时2.60秒，MPEL平均耗时4.18秒。MPDS算法运行效率更高。表4-2满足性能约束的可行的IPCore分配方案数量NSGAⅡPSOMPDSMPELautoTg024129autoTg217232935consumerTg0961010consumerTg1391511networkingTg22697officeTg08182222telecomTg12266图4-3到图4-5列出了四种算法所获得的分配方案，在面积、计算功耗和计算时间三个优化指标上的对比情况。53万方数据 电子科技大学博士学位论文35.0030.00NSGAⅡ25.0020.00PSO15.00MPDS10.00MPEL面积(1e-5m^2)5.000.00autoTg0autoTg2officeTg0telecomTg1consumerTg0consumerTg1networkingTg2测试用例图4-3面积对比图由图4-3显示，本文设计的MPDS算法和MPEL算法所得到的分配方案的IPCore总面积相比NSGAⅡ和PSO算法都有一定的减少，MPDS和MPEL两个算法的基本框架一致，只是改进的策略不同，在不同的测试用例上各有优势。10.008.00NSGAⅡ6.00PSO4.00MPDS2.00MPEL计算功耗(1e-4J)0.00autoTg0autoTg2officeTg0telecomTg1consumerTg0consumerTg1networkingTg2测试用例图4-4计算功耗对比图由图4-4中可以看出，在七个测试用例中，MPDS算法和MPEL算法得到的分配方案中的IPCore执行任务的总功耗相比其他两个算法更低，MPDS和MPEL两个算法所得的计算功耗比较接近，MPEL在个别子任务数较多的测试用例上略有优势。由图4-5中可以看出，MPDS算法和MPEL算法所得的分配方案中的IPCore执行任务的总时间相比其他两个算法有所减少。MPDS和MPEL两个算法基本框架类似，仅在优化策略上不同，所以计算时间结果很接近，难分伯仲。本文在对多个目标进行优化时，根据工程实际优先考虑了计算功耗和计算时54万方数据 第四章IPCore分配的智能优化算法设计12.0010.00NSGAⅡ8.00PSO6.00MPDS4.002.00MPEL计算时间(1e-3s)0.00autoTg0autoTg2officeTg0telecomTg1consumerTg0consumerTg1networkingTg2测试用例图4-5计算时间对比图间，然后再考虑面积。MPEL算法的邻域搜索策略有助于优选侧重的优化目标，因此在图4-3和图4-5中可以看到MPEL算法在计算功耗和时间相对于MPDS算法均取得了较小或者相近的计算功耗和时间。在图4-3中显示对于autoTg0、autoTg2和consumerTg0这三个测试用例，MPEL计算所得的面积劣于MPDS算法，是因为这三个测试用例的子任务个数相比其他几个测试用例更多，因此组合的方案总数也更多，在有限时间内选择出优化方案的难度也增加，MPEL算法选择的优化方案侧重于优选计算功耗和时间，所以在兼顾面积的优化时就稍弱于MPDS算法。为了更好的展示本文提出的算法在多个优化目标均取得了较好的优化效果，在图4-6中将每个测试用例的三个指标展现在同一个子图中，三个坐标轴分别代表了计算时间、计算功耗和面积三个不同的评价指标。图中可以看出我们提出的MPDS和MPEL算法求得的解在三个指标上均优于其他两个算法。4.6本章小结本章首先介绍了三种智能算法粒子群算法、遗传算法和模拟退火算法的原理，然后基于三种算法的基本思想，结合IPCore分配的约束和要求，设计了MPDS和MPEL算法用于IPCore分配方案的求解，并且分析了所提出算法取得收敛的条件。本文所设计的智能算法有效的融合了三种基本智能算法的优点，使得求解质量得到了提高。为了验证算法的有效性和性能，基于E3S测试平台，对本文提出的算法与传统的智能算法非支配排序遗传算法(NSGAⅡ)和粒子群算法(PSO)进行了测试，并且对比分析测试结果。测试数据表明，本文提出的算法获得了更多满足条件的NoC分配方案，计算所得的分配方案在面积、计算功耗和计算时间等性能指标上均优55万方数据 电子科技大学博士学位论文于传统的遗传算法和粒子群算法。(a)(b)(c)(d)(e)(f)(g)图4-6测试用例多目标优化比较(a)autoTg0；(b)autoTg2；(c)consumerTg0；(d)consumerTg1；(e)networkingTg2；(f)officeTg0；(g)telecomTg156万方数据 第五章IPCore映射布局的智能优化算法设计第五章IPCore映射布局的智能优化算法设计5.1算法原理分析IPCore映射是NoC布局中的重要步骤，在IPCore分配阶段，为NoC应用中的每个子任务分配了IPCore，接下来需要为每个IPCore在NoC结构中选择一个合适的位置，即IPCore映射。IPCore映射决定了芯片上处理单元的位置，直接影响到NoC通信路径的长度和通信性能，IPCore映射阶段的优化目标是通信时间、通信功耗、负载平衡和可靠性。本文根据NoC映射的需求和约束，基于分散搜索算法(ScatterSearch，SS)，将非支配排序引入分散搜索以实现多目标优化，为了加强算法的搜索能力，采用遗传算法的交叉和变异算子的不确定性操作，替换标准SS算法中的确定性操作，基于上述原理，我们设计了带不确定性策略的多目标分散搜算法MSSU(multi-objectivescattersearchwithuncertainty)，该算法结合了分散搜索和遗[109]传算法的优点。分散搜索算法是FredGlover早在1977年提出，但是一直被人们忽略，直到近[110][111]年来才开始被关注，分散搜索算法的目标是快速找到高质量的解。分散搜索[112]算法的优化策略是其他智能算法所不能比拟的。分散搜索实施于参考集上，通过组合参考集中的解构造新解，构造新解的主要方法是对两个原有解进行组合。分散搜索算法的参考集与遗传算法中的种群不一样，参考集中的元素个数相对较少，通常包含20个解，在遗传算法中种群包含的个体数量通常是远大于20个。遗传算法是从种群中随机选择若干个解，通过交叉和变异算子产生下一代个体。在分散搜索SS算法中，构造新解是从参考集中选择两个或者更多的元素进行组合，组合过程会涉及到参考集中的所有解。这也是因为参考解集元素个数较少，所以所有解均参与组合过程。标准分散搜索算法SS的实现过程如下：(1)产生一组初始解向量，确保解具有多样性，并且能够适用于求解问题的启发迭代过程。按照预定的规则选择解构成参考集，通常是选择高质量和多样性的解。(2)对参考集中的解进行组合产生新解。(3)局部改善解，以提高解的质量。(4)在新解中选取高质量和多样性的解加入参考集。(5)重复第(2)到(4)步，直到参考集不再产生变化则转入第(6)步。(6)判断是否满足迭代终止条件？如果已经满足则算法终止；否则重新启动57万方数据 电子科技大学博士学位论文第(1)步操作。分散搜索三个重要的特征是：(1)参考集中的高质量解蕴含着搜索最优解的启发信息，在其引导下逐渐靠近最优解。(2)参考集中的远距离解，使得参考集足够分散，保证了解的多样性，减少了陷入局部最优的可能。(3)在组合解的过程，并行地考虑了多个解，兼顾了解的多样性和质量，增加了获得最优解的机会。标准分散搜索算法描述如下所示：ScatterSearchAlgorithm1{do{2CreatePopulation(Solutions);3Improvement(Solutions);4Generate(ReferenceSet);5do6{SubSet=GenerateSubSet(ReferenceSet);7combSolutions=Combinate(Subset);8Improvement(combSolutions);9Update(ReferenceSet)usingcombSolutions;10}while(ReferenceSethasbeenchanged)11}while(notreachingiterationterminationcondition)12}通过以上算法描述可以看出，分散搜索算法首先随机产生初始解群Solutions，再通过Improvement函数改进解，选择一部分最优解和距离最远的解构造参考集ReferenceSet。通过参考集中的解构建子集Subset，进行子集的组合操作产生新解combSolutions，选择其中最优解和距离最远的解对原参考集进行更新，重复上述过程，直到参考集中的解不再被替换改变，达到稳定，则开始下一轮的迭代，直到满足迭代终止条件。5.2MSSU算法设计5.2.1算法流程描述在标准分散搜索SS算法中引入了非支配排序算法和遗传算子的不确定性策略，由此提出了带不确定性策略的多目标分散搜算法MSSU算法。MSSU算法首58万方数据 第五章IPCore映射布局的智能优化算法设计先按照标准SS算法的过程产生初始解，并且改进解提高解的质量，然后选取高质量和多样性的解构成参考集，在参考集中随机选择两个子集配对进行组合操作，采用交叉算子对子集的解实施交叉操作产生新解，对满足变异概率的子集实施变异算子操作。根据评价函数计算组合所得新解的评价指标值，进行非支配排序，根据解的质量和多样性原则更新参考集，重复上述步骤直到参考集不再发生变化，判断是否到达迭代终止条件，如果已经到达则终止算法，否则重新启动算法，开始新的迭代操作。通过上述步骤可得MSSU算法描述如下：MSSUAlgorithm1{CreatePopulation(Solutions);2Improvement(Solutions);3Evaluation(Solutions);4Non-dominatedsort(Solutions);5ReferenceSet=GenerateSet(BestSolutions,FarSolutions,Ref_size);6do7{do8{SubSet=GenerateSubSet(ReferenceSet,Sub_size);9combSolution=Combination(Subset,crossoverOperater);10combSolution=Combination(Subset,mutationOperater);11Improvement(combSolutions);12Evaluation(combSolutions);13Non-dominatedsort(combSolutions);14Update(ReferenceSet)usingcombSolutions;15}while(ReferenceSethasbeenchanged)16CreatePopulation(Solutions);17Evaluation(Solutions,ReferenceSet);18Non-dominatedsort(Solutions,ReferenceSet);19ReferenceSet=GenerateSet(BestSolutions,FarSolutions,Ref_size);20}while(notreachingiterationterminationcondition);21}由上述算法描述可以看出，MSSU算法首先随机产生初始种群Solutions，改进解Improvement，评价解Evaluation，并且进行多目标优化非支配排序Non-dominatedsort，选择部分最优解BestSolutions和距离最远的解FarSolutions创建参考集ReferenceSet，参考集中解的个数为Ref_size，接着开始迭代过程：采用59万方数据 电子科技大学博士学位论文参考集中的解构造子集SubSet，子集中解的个数为Sub_size，对子集进行组合操作Combination，MSSU算法中分别采用了交叉算子crossoverOperater和变异算子mutationOperater组合子集构造新解，对组合产生的新解combSolutions进行优化改进，计算新解的评价函数值并进行非支配排序，根据排序结果更新参考集ReferenceSet，更新操作是选择适应度高的和距离远的新解进入参考集替换适应度较低或者距离较近的解，重复子集的组合以及参考集的更新操作，直到参考集的解趋于稳定，不再有新的解进行替换则终止子集更新参考集的操作，然后再判断是否已经满足迭代终止条件，如果满足则算法终止，如果不满足则重新产生解，评价排序，并且构造新的参考集，开始下一轮的迭代。5.2.2解的表示和改进MSSU算法中的初始种群是由尽量分散的解构成，以确保解的多样性，因此按照种群大小，随机产生初始解。使用0,1,...,N-1的随机排列作为一个解，表示为(p0,p1,„,pN-1)，解中的每一位表示NoC拓扑结构中一个tile。例如pi表示第i个IPCore映射的处理单元所在的位置tile的编号，N是在给定NoC拓扑结构中tile的总个数。在分散搜索算法中，解的改进是一个很重要的步骤，本文通过局部调整来改进解。选择通信负载最大的IPCore映射到NoC拓扑结构中连接度最大的节点，并且将与该节点有通信流量的IPCore安排在其相邻位置，由此缩短了流量较多的IPCore之间的通信距离。5.2.3非支配排序过程IPCore映射是多目标优化问题，需要把标准SS算法改进为多目标优化算法，以搜索Pareto最优解。因此在MSSU算法中对参考集的解实施了非支配排序，把每个解分配到相应的非支配层。Pareto最优解集设为第一层，下一个非支配集合的解集设为第二层，以此类推，直到所有的解都分配到一定的层次。非支配排序和层次分配算法描述如下：Non-dominatedsortingforNoCmapping1{while(P≠NIL)//Pisthesetofallsolutions2{getasolutionxfromP;3Sx=NIL;Nx=0;//Sxisthesetofsolutionsthataredominatedbyx,Nxisthenumberofsolutionswhichdominatex.60万方数据 第五章IPCore映射布局的智能优化算法设计4while(P≠NIL)5{getasolutionyfromP;6if(xdominatesy)//thevaluesoffourobjectivesofxaresuperiortoy7yentersSx;8elseif(ydominatesx)9Nx=Nx+1;10}11if(Nx==0)12xentersRank1;13}14i=1;//irepresentstheIDofrank15while(Ranki≠NIL)16{do17{getxfromRanki;18while(Sx≠NIL)19{getyfromSx;Ny=Ny-1;20if(Ny==0)21NyentersRanki+1;22}23}while(Ranki≠NIL)24i=i+1;25}}由上述算法描述可以看出，P表示所有解的集合，首先对于P中任意一个解x，用Sx表示x所支配的解的集合，Nx表示支配x的解的个数，然后依次取出P中的解记为y，比较解x和解y的支配关系，如果x支配y，那么就把y加入到集合Sx，如果y支配x，则Nx加1，重复上述判断，直到所有解的支配关系都判断完毕，然后把Nx为0的解标注为第一层的解，接着把它所支配的解(即Sx集合中的解)的支配个数减1，再把当前支配个数为0的解作为第二层，以此类推，直到所有的解都分配到一定的层次。5.2.4参考集的操作参考集ReferenceSet,是一个由高质量解和分散解构成的集合。参考子集61万方数据 电子科技大学博士学位论文ReferenceSet1包含10个最优解，参考子集ReferenceSet2是分散解的集合，包含10个距离最远的解。解的质量评判是由IPCore分配的四个评价指标经过求Pareto最优解决定，所有的解在经历了非支配排序之后，根据解的支配层次从高到低，选择10个最优解进入ReferenceSet1。计算两个解的距离方法是：比较两个解的相同位，如果值相同，该位标注为1，否则标注为0，累加所有位标注的值，所得到的和即是两个解之间的距离。第i个解和参考集ReferenceSet之间的距离定义为该解与ReferenceSet中所有解的距离之和，其计算方法见公式(5-1)所示：N1distancei([][]siksjk[][])(5-1)jRefeSetk0其中i=1,2„,popsize，popsize是种群大小，j表示参考集ReferenceSet(RefeSet)中的解，N是每个解中的总位数。s[i][k]是第i个解中的第k位，表示在第i个解中分配给第k个IPCore的处理单元所在位置tile编号，s[j][k]表示在第j个解中分配给第k个IPCore的tile编号，在每次迭代过程中选择10个与现有参考集距离最远的解加入参考子集ReferenceSet2。5.2.5子集的操作S1S2253807416146783520123456789123456789对换第二个和第七个243807516146783520123456789123456789对换第三个和第六个247803516146783520123456789123456789对换第四个和第五个247083516Snew图5-1匹配交叉算法62万方数据 第五章IPCore映射布局的智能优化算法设计542637810548637210图5-2置换变异[110]构造子集用于产生新解，本文采用了2元子集法，从参考集中随机选择解，每两个配成一对，产生一个子集。对每一个子集的解进行组合操作产生新的解，我们采用了交叉和变异的方法组合构造新解。传统的交叉方法直接用于NoC映射可能产生无效解。所以本文根据映射的约束条件设计了一种匹配交叉算法，如图5-1所示。图5-1中假设有两个解S1和S2，交叉起点设为point1,参与交叉的位数设为clength，S1中第point1位的值设为x，在S2中搜索值同样为x的位，标记为cpoint2,然后对换S1中cpoint1和cpoint2位的值。例如,S1=(2,5,3,8,0,7,4,1,6),S2=(1,4,6,7,8,3,5,2,0),假设cpoint1值为2，则在S2中cpoint2值为7,交换S1中的第2和第7位,得到新解S1=(2,4,3,8,0,7,5,1,6).继续对第cpoint1+1,cpoint1+2位执行上述操作，直到完成预设的交叉位数。假设交叉位数clength值为3，则对换三次之后得到的新解为Snew=(2,4,7,0,8,3,5,1,6)。交叉操作所得的新解具有部分父代解S1和S2的特征，也具有部分自己的特征，并且是一个有效的解。变异操作以较小的概率作用于参考集，对每个解中的每个位进行判断，如果其变异概率超过预设的值，则对该位进行变异操作。此处采用置换变异的方式以避免产生无效解，变异过程如图5-2所示。5.2.6参考集的更新对组合操作所获取的新解进行性能评价，根据评价函数计算解的四个优化指标值，然后与参考集中已有的旧解进行对比，如果四个指标都优于旧解，那么就用新解替代之。此外还需要计算新解跟参考集的距离，距离大于旧解的新解将进入参考集，替换掉旧解。5.3实验及结果分析5.3.1映射方案的评价指标对比为了验证算法的性能，将MSSU算法应用于E3S平台的七个典型测试用例。实验目标是期望在性能约束条件下，尽可能多地获得满足性能要求的映射方案。63万方数据 电子科技大学博士学位论文表5-1满足性能约束的可行的IPCore映射方案个数NSGAⅡPSOMSSUautoTg02919autoTg2114854consumerTg031221consumerTg172323networkingTg231019officeTg082833telecomTg11813表5-1显示了将三种算法应用于E3S测试平台中的七个典型测试用例获得的结果。表中列出了每种算法所获得的可行解的个数，即满足性能要求的映射方案的个数。从表中可以看出本文提出的MSSU算法获得的解的个数多于NSGAⅡ所求解的个[56]数和PSO算法所求解的个数。MSSU算法在CPU2.66GHz的计算机上运行七个测试用例平均耗时1.18秒。图5-3到5-6展示了E3S平台的七个测试用例的四个评价指标值。因为智能算法是随机算法，因此所求得的解具有一定的随机性，为了分析算法的稳定性能，对于每一种优化指标，我们累计了10次测试最优解在图中展示出来。12108NSGAⅡ6PSO4MSSU2通信时间(1e-7s)0autoTg0autoTg2officeTg0telecomTg1consumerTg0consumerTg1networkingTg2测试用例图5-3通信时间减少通信时间是映射阶段的重要目标，在图5-3中显示MSSU算法在所有的测试用例中都获得了最少的时间，PSO算法仅次于MSSU。NSGAⅡ算法获得的映射方案的通信时延最长。低功耗也是NoC映射的重要优化指标，图5-4显示了各种算法获得的测试用例的通信功耗，由MSSU算法获得的映射方案功耗最低。PSO次之，NSGAⅡ求解的方案最差。测试用例autoTg2的优化效果最明显，该测试用例是包含任务数最64万方数据 第五章IPCore映射布局的智能优化算法设计302520NSGAⅡ15PSO10MSSU5通信功耗(1e-6J)0autoTg0autoTg2officeTg0telecomTg1consumerTg0consumerTg1networkingTg2测试用例图5-4通信功耗多的例子。图5-5展示了各种算法获得的链路负载方差，负载均衡有助于减少网络拥塞和排队时延，负载方差越小意味着负载越均衡。由MSSU算法获得的效果最好，PSO算法仅次于MSSU算法。141210NSGAⅡ8PSO64MSSU链路负载方差20autoTg0autoTg2officeTg0telecomTg1consumerTg0consumerTg1networkingTg2测试用例图5-5负载方差高可靠性也是NoC映射追求的目标，我们采用了冗余路径提高系统可靠性，设每个交换节点的正常工作概率为0.92。在图5-6中显示了MSSU获得的可靠性高于其他算法，这是因为MSSU的搜索策略可以引导更多的可靠路径被搜索，PSO算法次之，NSGAⅡ算法获得的映射方案可靠性最低。5.3.2Nirgam仿真结果分析为了进一步测试算法所得到的的映射布局结构的性能，我们用Nirgam仿真器[113-114]对布局方案进行仿真模拟。Nirgam是一种基于时钟周期的模拟器，主要用于片上网络的互联路由和应用建模等仿真。由南安普顿大学的教授BashirAl-Hashimi及其研发团队开发，该仿真器在NoC设计过程中被广泛应用。65万方数据 电子科技大学博士学位论文109.59NSGAⅡ8.5PSO可靠性8MSSU7.57autoTg0autoTg2officeTg0telecomTg1consumerTg0consumerTg1networkingTg2测试用例图5-6可靠性实验采用了PSO、NSGAⅡ和MSSU三种算法对E3S平台的七个测试用例计算所得的最优布局方案在Nirgam仿真器上进行仿真，仿真的是3*3的2Dmesh结构，2Dmesh是使用最广泛的结构，所以采用它做测试。实验设置为仿真开始后5个时钟周期开始产生通信流量，流量产生持续500个时钟周期。数据片flit间隔2个时钟周期，每一条链路的通信负载根据测试用例中处理单元之间的通信流量进行设置。仿真3000个时钟周期之后结束。因为Nirgam基于链路测试NoC的性能，[115]所以此处对比分析了不同布局方案中数据片flit在各条通信链路上的平均时延。限于篇幅，文中列出了E3S中三个典型测试用例的映射方案图和Nirgam模拟的详细结果，如图5-7至图5-12所示，包括用例的映射布局方案，以及仿真在每条链路上数据片的平均时延。其他测试用例在表5-2中列出了总的链路平均时延。图5-7中列出的是测试用例AutoTg2由不同算法分别获得的映射布局方案，其中每一个网格表示NoC拓扑结构中的一个IPCore处理单元所在的tile，网格中的圆圈表示分配给这个tile中的处理单元所能完成的子任务编号。为了避免产生热点，我们设置每个网格tile最多分配两个子任务。例如图5-7(a)中，在tile5中有圆圈6和8，表示子任务6和8由tile5中的处理单元执行。图5-8展示了测试用例AutoTg2由三种算法分别所得的三种布局方案，每条链路上数据片flit的平均延迟。图中的数字0-8标识的是tile的位置，tile之间的柱子表示不同方向上flit在平均时延。例如，在tile0和tile1之间，红色柱子表示从tile0到tile1传输数据片的时延，蓝色柱子表示从tile1到tile0传输数据片的时延。从图中的几种算法对比可以看到，MSSU算法获得布局方案的总平均时延是最低的，PSO算法仅次于MSSU，NSGAⅡ算法得到时延最长。图5-9和图5-10显示的是测试用例consumerTg1的布局方案和仿真结果。图5-11和图5-12显示的是测试用例telecomTg1的布局方案和仿真结果。66万方数据 第五章IPCore映射布局的智能优化算法设计testcaseautoTg2036036036523799414714714791236841685232582582584687571（a）(b)(c)图5-7测试用例autoTg2的映射布局方案(a)NSGAⅡ映射；(b)PSO映射；(c)MSSU映射（a）（b）（c）图5-8测试用例autoTg2布局方案的链路平均时延(inclockcyclesperflit)分析(a)NGSAⅡ算法获得布局方案，所有链路总平均时延=2.81105；(b)PSO算法获得布局方案，所有链路总平均时延=2.31612；(c)MSSU算法获得布局方案，所有链路总平均时延=1.9071067万方数据 电子科技大学博士学位论文testcase：consumerTg1036036036132147147147233040412582582580421（a）(b)(c)图5-9测试用例consumerTg1的映射布局方案(a)NSGAⅡ映射；(b)PSO映射；(c)MSSU映射（a）（b）（c）图5-10测试用例consumerTg1布局方案的链路平均时延(inclockcyclesperflit)分析(a)NGSAⅡ算法获得布局方案，所有链路总平均时延=3.7314；(b)PSO算法获得布局方案，所有链路总平均时延=2.4167；(c)MSSU算法获得布局方案，所有链路总平均时延=1.916768万方数据 第五章IPCore映射布局的智能优化算法设计testcase：telecomTg1036036036524514714714730132432582582580124510（a）(b)(c)图5-11测试用例telecomTg1的映射布局方案(a)NSGAⅡ映射；(b)PSO映射；(c)MSSU映射（a）（b）（c）图5-12测试用例telecomTg1布局方案的链路平均时延(inclockcyclesperflit)分析(a)NGSAⅡ算法获得布局方案，所有链路总平均时延=1.8889；(b)PSO算法获得布局方案，所有链路总平均时延=1.0245；(c)MSSU算法获得布局方案，所有链路总平均时延=1.008569万方数据 电子科技大学博士学位论文表5-2中列出了三种算法在七个测试用例上的映射方案通过Nirgam模拟器执行后，得到的总链路平均时延，可以看出在这七个测试用例上MSSU算法均取得了很好的优化效果，对于通信关系最复杂的测试用例AutoTg2，MSSU算法的优化效果也最显著。表5-2映射方案的总链路平均时延对比(inclockcyclesperflit)NSGAⅡPSOMSSUAutoTg01.8671.5331.200AutoTg22.8112.3161.907ConsumerTg02.0571.7191.500ConsumerTg13.7312.4171.917networkingTg21.3331.3331.333OfficeTg01.5811.5331.533TelecomTg11.8891.0251.009为了更好地展示算法取得的多个优化目标之间的平衡情况，图5-13至图5-16显示了测试用例AutoTg2采用不同算法得到的解的分布情况，该测试用例是E3S平台中拥有子任务最多，且最具代表性的用例。在PSO、NSGAⅡ和MSSU三个算法产生的解中，根据Pareto最优解及非支配排序思想，分别选择50个排序最靠前的解，列出这些解的分布情况。图5-13通信时间和通信功耗的性能平衡图5-14可靠性和通信功耗的性能平衡图5-13显示了通信时间和通信功耗的性能平衡，虚线框里的解是具有较高质量的解，即兼具较低的通信时间和较低的通信功耗。圆点表示由MSSU算法获取70万方数据 第五章IPCore映射布局的智能优化算法设计的解，“+”表示由PSO算法获得的解，“×”表示由NSGAⅡ算法获得的解。因为有部分解的值相同的，所以图中部分图形是重合在一起的。图中可以看出虚线框里的解多数是由MSSU算法获得的，由此说明MSSU算法相比其他算法获得更多的高质量解。MSSU算法致力于把具有较重通信任务的IPCore安排在位置邻近的tile中的处理单元，从而缩短了通信路径，降低了通信时间和功耗，促进了获得更多高质量解。图5-14显示了可靠性和通信功耗的性能平衡，虚线框里的解是具有较高质量的解，即兼具较高可靠性和较低功耗，这些高质量的解多数由MSSU获得。MSSU算法的策略有效地避免陷入局部最优，所以更多的高可靠性路径有机会被搜索到，从而提高了解的质量。图5-15可靠性和通信时间之间的性能平衡图5-16通信时间和负载方差之间的关系图5-15显示了可靠性和通信时间之间的性能平衡，虚线框里的解兼具高可靠性和较低通信时间，图中可见虚线框里圆圈较多，表示MSSU获取的高质量解多于PSO和NSGAⅡ算法图5-16显示了通信时间和链路负载方差之间的关系，图中的曲线是50个最优解通过Matlab工具所得到的的拟合曲线。通信时间和链路负载方差两个优化目标并不冲突，负载方差较低意味着通信负载更加均衡分散，可以减少网络堵塞和排队等待时间，从而减少总的通信时间，图中显示由MSSU算法获得的解具有更好的负载平衡和更低的通信时间。5.4本章小结本章根据IPCore分配的需求和约束设计了MSSU算法。该算法是基于分散搜71万方数据 电子科技大学博士学位论文索算法，引入了非支配排序以实现多目标优化，引入了遗传算子的不确定性策略以提高搜索最优解的能力。本章首先分析了MSSU算法的原理，然后描述了算法的实现步骤和具体方法。在本章的实验部分，主要将MSSU算法与PSO和NSGAⅡ算法做对比分析。将算法用于E3S平台的测试用例，并且用Nirgam仿真器对算法所得的布局方案进行仿真模拟，由实验结果看出MSSU算法获得的布局方案在时延、功耗和可靠性等性能上均优于PSO和NSGAⅡ算法。72万方数据 第六章面向多应用的可重构布局优化算法设计第六章面向多应用的可重构布局优化算法设计6.1基于彼得森图的可重构布局设计嵌入式系统中的多核片上系统通常具有不同的通信需求，而且这些通信需求是可以静态获知的，因此基于应用的定制拓扑结构更能满足片上网络的应用特点和需要。但是通常基于应用的片上网络只是针对某一个应用而设计，不能满足其他的应用，不同的NoC应用通常有不同的通信连接方式和通信流量等特征，一旦映射完成，确定了NoC的拓扑结构，节点之间的物理位置和连接关系就不会再发生改变。随着当前NoC系统规模的增大，需要集成更多的模块，模块的可重用性就更为重要，不仅芯片功能实现可重用，通信结构也需要重构。可重构结构设计是为了增加系统的重用性，节省系统设计时间，降低系统构建代价。一些研究者在该[116]领域展开了研究，Kim等人提出的可重构结构是通过增加一组可重构的缓存和链路等组件来实现重构，但是该方法可能会增加较多的面积开销，因为交换节点的缓存是影响片上网络面积的重要因素，增加缓存，就意味着面积的大幅度增加。[117]Modarressi等人提出的可重构结构是基于2Dmesh结构的重构，采用分支限界[118]法构建路径。Stensgaard等人提出了一种重构方案，在构建网络的时候建立绕行路线，避开一些交换节点，不过该文献没有提供产生一个具体应用的拓扑结构[119]的详细算法描述，并且也没有考虑可能出现的死锁问题。Sbiai等人提出了一种[120]基于测试访问机制的可重构结构。Morris等人基于3D片上光网络提出了可重构结构。规则的布局结构例如2Dmesh结构，可以提供规整的连接，利用成熟的架构和开发方法，易于实现和控制，通用性强，但是网络直径较大，距离较远的节点通信会有较大的时延，导致更多的功耗。基于NoC应用的不规则结构，对于特定的应用任务具有较高的性能，但是不具备可重用性，适用范围有较大局限性。因此本文采用了一种介于规则与不规则结构之间的结构，其基本思想是利用规则结构的规整性和易行性，采用简单且代价较小的重构技术，构建能适用于不同NoC应用的布局结构。本文设计的是基于彼得森图的可重构布局结构。该结构以彼得森图为基本结构，通过简单的重构技术可使得布局适用于多个片上网络应用，具有一定的重用性，也可以获得通信最短路径以提高NoC性能。在规则结构的基础上，采用可重构技术，根据当前应用任务之间的通信关系和流量，重新构建节点之间的连接关73万方数据 电子科技大学博士学位论文系，结合彼得森图的网络直径短的特征，所得到的布局结构能确保NoC系统的正常通信，可以减少多个NoC应用的总通信代价。6.1.1可重构原理分析本文使用重构节点改变NoC通信节点之间的连接关系，如图6-1所示，重构节点由12组开关来控制数据通路，其目标是尽量让通信负载高的节点可通过网络链路直接通信，减少通信路径中的中转节点，因为通信路径中的交换节点会产生较多时延和功耗。例如因特尔公司的TeraFlops巨型机片上通信功耗中，有超过30%[121]的功耗是由通信网络引起的，所以在通信路径上尽量减少经过交换节点。图6-1重构节点示意图[117]在传统的NoC拓扑结构中，插入重构节点构建拓扑结构，原有的交换节点仍然是五个端口，其中一个依旧与本地的处理单元连接，但是另外的四个端口并不是直接与其他的交换节点相连，而是通过重构节点进行连接。如图6-2所示，图中标识有“S”的正方形表示普通的交换节点，标识有“PE”的矩形表示处理单元，标识有“R”的圆圈表示重构节点。ＳＲＳＲＳＲＳＰＥＰＥＰＥＰＥＲＲＲＲＲＲＲＳＲＳＲＳＲＳＰＥＰＥＰＥＰＥＲＲＲＲＲＲＲＳＲＳＲＳＲＳＰＥＰＥＰＥＰＥ图6-2基于2Dmesh的可重构结构74万方数据 第六章面向多应用的可重构布局优化算法设计通路1通路2通路4通路3图6-3可重构节点的连通方式重构节点的连通功能主要是由开关来完成，重构节点有四个端口，每两个端口之间可以分别建立连接通路，用于数据的进入和输出，以实现双向通信。每对端口之间的连接通路是由开关来控制的，可以组合多种连通方式，图6-3中列出了部分可能的连通方式。例如图6-3中的第一幅图所示，上端的输入端口与右边的输出端口连通，形成一条从上向右的通路1；右端的输入端口与左端的输出端口相连，形成一条从右向左的通路2；下端的输入端口与上端的输出端口相连，形成一条自下而上的通路3；左边的输入端口与下端的输出端口相连，形成一条从左向下的通路4。因为片上网络的缓存资源有限，而且要求通信时延低，所以适合虫洞的交换方式。片上网络的通信需求通常是可以静态获知的，并且具有通信代价低，易实现等特点，所以实际应用中较多地采用静态路由，尤其适用于基于应用的片上网络。首先根据通信关系、通信流量结合拥塞控制等策略建立路由表，然后根据路由表信息来选择路径。因此本文针对面向多应用的片上网络设计了静态路由算法。本文采用的可重构方法是通过插入可重配置的重构节点来实现的，虽然会增75万方数据 电子科技大学博士学位论文加一定的面积，但是对系统总面积不会有太大影响。因为重构节点的面积远小于交换节点的面积，每个普通的交换节点包含缓冲区、虚拟通道、开关分配器和路由逻辑等元件，其中缓冲区的大小是影响面积的主要因素之一。而本文采用的重构节点主要由多路开关组成，没有虚拟通道和路由选择等控制逻辑，结构很简单，只有在重构节点连接的链路过长，在一个时钟周期内不能完成数据传送时，需要增加一个寄存器进行中继。因此插入重构节点导致增加的面积，相对交换节点的面积是很少的。虽然增加了少量的面积开销，但是增加的重构节点可以构建路径绕过交换节点，减少了通信路径的中转跳数，从而减少了通信时延和通信功耗。根据Orion[122]计算模型，按照70纳米技术、32位链路、1个数据片的寄存器计算，可得出[123]经由一个重构节点消耗的通信代价大约是一个普通交换节点的五分之一。所以我们把经过一个重构节点的代价cost设置为1，经过一个普通交换节点的代价cost设置为5。由此得到重构结构的通信代价评估模型，见公式(6-1)所示。costtotalflowij*costk(6-1)eijEkpathij其中E表示NoC应用任务图的边集合，eij表示IPCore处理单元i和j之间的通信关系，flowij表示i和j之间的通信流量，k表示i和j之间的通信路径上的中间节点，如果节点k是重构节点，则其通信代价costk取值为1，如果节点k是交换节点，则coskk取值为5。设计布局方案的目标是让多个NoC应用中的通信总代价最小。6.1.2可重构结构设计为了尽量缩短节点之间的通信路径，从而减少通信时延和功耗等通信代价，本文的可重构结构采用了彼得森图作为可重构结构的基本框架，彼得森图具有网络直径短的优点，为缩短通信路径提供了基础。彼得森图是由数学家彼得森提出的，因为彼得森图具有对称性、最小直径等[83]特性受到研究者的广泛关注。[124]定义6.1彼得森图PG(5,2)={V,E}，其中V={u0,u1,…,u4,v0,v1,…,v4},E={uiu(i+1)mod5,uivi,viv(i+2)mod5,0≤i≤4}。此处的V表示顶点集合，E表示边集合。彼得森图如图6-4所示，图中可以看出PG(5,2)总共有10个结点，由两个环构成，每个环有5个节点，外环的相邻节点顺次相连，内环节点每间隔一个相连，76万方数据 第六章面向多应用的可重构布局优化算法设计u0v0u4u1v4v1v3v2u3u2图6-4彼得森图PG(5,2)内环和外环对应位置的节点也相连。图中每个节点的度都是3，图的直径是2，任意两个节点可能直接相连，也可能由一个中转节点间接相连。任意两个节点之间具有3条互不相交的路径相连，增强了容错性。彼得森图具有对称性、低连接度、短直径等优点，是有效的小网络。彼得森图的对称性是兼有中心对称和轴对称，是可以旋转的，节点之间也具有轮换性，边跟随节点具有对称性，图中节点之间的平均距离小，简单规整。由于彼得森图独有的特性，受到图论及相关应用领域研究者的青睐。在彼得森图PG(5,2)的基础上，很多研究者进行了扩展和推广，其中[124]Coxeter在PG(5,2)的基础上进行扩展，提出了一类广义彼得森图，该结构得到了广泛的应用。[124]定义6.2广义彼得森图PG(n,k)={V,E}，其中V={u0,u1,…,un-1,v0,v1,…,vn-1},E={uiu(i+1)modn,uivi,viv(i+k)modn,0≤i≤n-1}。V是顶点集合，ui是构成外环的节点，vi是构成内环的节点。E是边集合，边包括三部分，外环节点连接的边，外环和内环对应位置的节点连接的边以及内环节点连接的边。图6-5和图6-6分别展示了广义彼得森图PG(7,2)和PG(8,3)。由图中可以看出广义彼得森图PG(n,k)的一般连接特性：具有2n个节点和3n条边，其中内环和外环均有n个节点。外环的节点相邻顺次连接，内环的节点每间隔k个节点相连，内环和外环的对应位置节点也相连。广义彼得森图不仅具有短直径、规整性和优良的连接特性，还具备可扩展性。77万方数据 电子科技大学博士学位论文u0u0u7u1u6u1v0v0v7v1v6v1u6v6v2u3v5v2u5u2v5v3v4v3v4u5u3u4u3u4图6-5广义彼得森图PG(7,2)图6-6广义彼得森图PG(8,3)6.1.3基于彼得森图的可重构结构本文提出了基于广义彼得森图的可重构拓扑结构。采用彼得森图是为了缩小网络通信距离，采用可重构策略是为了提高NoC的重用性。图6-7显示了基于PG(6,2)建立的可重构结构，为了便于分析，图中把交换节点和处理单元组合在一起由图中的方形表示，交换节点具有多个端口，其中一个端口跟本地处理单元链接，其余端口从不同的方向与其他交换节点或者重构节点相连，接入通信链路。62312131107221451211542201631081917189图6-7基于彼得森图的可重构结构78万方数据 第六章面向多应用的可重构布局优化算法设计图中圆形是重构节点，它的作用是根据路由选择，对通信链路进行连接组成通信路径。我们以广义彼得森图为基础，在内环和外环之间插入了重构节点，在内环仍然采用的了原有的交换节点进行连接，这样可以让负载较大的节点映射到内环，通过交换节点直接通信，对于其他通信任务相对较少的节点可以映射到外环，通过重构节点，构建尽量短的路径进行通信。可重构结构的优点是可以根据具体的应用通信情况在具有较高通信负载的节点之间建立通信捷径，缩短通信路径，从而降低时延和功耗等通信代价。6.2MQG算法设计本文设计的重构布局由映射和路由两个阶段完成，实现过程如下：首先计算要处理的多个NoC应用中的每个IPCore平均通信负载量，接着映射IPCore到NoC结构中，具有较大通信流量的节点尽量映射到相互邻近的位置，然后再根据路由算法为通信节点构建路径，按照所构建的路径，依次连接对应的网络节点，从而得到最终的拓扑结构和布局方案。IPCore映射阶段可以采用第五章设计的映射算[80]法完成，此处的路由问题也是NP问题，计算时间复杂度高，通常需要采用各种智能算法求解。本文在可重构结构的基础上，设计了多值量子进化算法完成路由以及布局构建的工作。6.2.1量子进化算法原理及结构量子进化算法将量子位的概率幅应用于进化算法的个体编码，通过旋转门和非门等量子门实现个体的进化和变异，产生新个体，再通过多次迭代搜索最优解或者满足条件的解。优化算法在寻优过程中，需要利用先前搜索积累的信息，同时也要探索未知的解空间，在保持原有的优势信息的基础上兼顾新的探索空间。在量子进化算法中，通过选择算子保留高适应度的个体以延续优势信息，通过模拟量子坍塌观察个体的值，积累搜索过程中的寻优收益。量子编码携带的多状态信息为个体的多样性提供了基础，通过量子门对个体的进化操作，产生新解，探索未知的解空间，引导个体以较大的概率向优良的趋势进行发展。量子进化算法相对于传统进化算法的主要区别体现在个体的编码方式和进化策略上。量子进化算法中的主要实现方法如下：(1)量子位的表示量子位是量子计算中表示信息的基本单位，一个量子位可以处于|0>态、|1>态、79万方数据 电子科技大学博士学位论文或者|0>与|1>之间的线性叠加态。通常一个量子位表示为公式(6-2)所示。01(6-2)22其中α和β分别表示量子位对应态的概率幅，|α|是量子位表现为|0>态的概率，|β|22是量子位表现为|1>态的概率，并且满足|α|+|β|=1。(2)量子个体的描述多个量子位的概率幅组成的串构成了量子个体，如公式(6-3)所示。12...m(6-3)12...m22其中|αi|+|βi|=1，i=1,2…m，m是量子个体的位数。这种个体的构造方式可以通过叠加态表现多种状态，体现了量子个体的多样性。(3)量子个体进化方法量子的个体进化主要有两种途径，种群内部通过量子比特相位旋转或者量子非门实现个体进化，种群之间通过合并或者交叉操作实现个体的更新。其中量子旋转门如公式(6-4)所示。aa'cossinii(6-4)b'sincosbii其中αi和bi分别表示第i个量子位的初始概率幅，αi’和bi’分别表示根据旋转门更新后的概率幅度。其中旋转角度的计算是根据问题的具体情况，结合当前最优解等信息进行设置。概率幅的改变会导致观察值的改变，根据优化策略，引导个体逐渐接近最优解。这种基于量子态的概率幅编码方法，可以通过叠加态呈现出多种状态，从而使个体具有更丰富的多样性，随着进化的迭代，旋转门以及非门作用于个体，更新概率幅，当αi’和bi’的值趋近于0或者1的时候，个体的多样性就逐渐消失，个体会收敛到一个确定的状态。量子进化算法的基本步骤如下：首先采用量子位的概率幅对染色体进行编码，产生初始种群，并将每个量子位初始化为相同的值，以表示每条染色体处于可能的叠加态的概率相同；接着开始迭代过程：观察染色体的状态值，解码应用问题的解，根据适应度函数计算每个解的适应度，选择当前最优解保存；然后采用量子门结合当前最优解更新染色体；重复迭代直到满足迭代终止条件。量子进化算法的一般流程描述如下：80万方数据 第六章面向多应用的可重构布局优化算法设计QuantumEvolutionaryAlgorithm1{gen=0；2generateinitialpopulationQ(gen);3observeQ(gen)states;4makeP(gen)bydecodingQ(gen);5computefitnessesofP(gen);6storethecurrentbestsolutionofP(gen);7while(notreachingthetermination-condition)8{updateQ(gen)usingquantumgatesU(gen);9observeQ(gen)states;10makeP(gen)bydecodingQ(gen);11computefitnessesofP(gen);12storethecurrentbestsolutionofP(gen);13gen=gen+1;14}15}首先迭代次数gen等于0时，产生初始种群Q(gen)，观察Q(gen)解的状态，根据观察值解码染色体生成解集P(gen)，计算解集中每个解的适应度computefitnesses，存储当前最优解，然后开始迭代过程：使用量子门gatesU(gen)更新种群的染色体updateQ(gen)，观察更新后的染色体状态，并且解码生成新的解集，计算解集中解的适应度，存储当前最优解，迭代次数gen加1，开始下一轮迭代，直到满足迭代终止条件。6.2.2算法设计分析片上网络NoC中的通信数据从从源节点达到目的节点的路径，通常是由一系列的链路和中转节点构成，路由算法负责选择合适的中间节点，在源节点和目的节点之间构造可通的路径。路由算法会影响网络的时延、服务质量和功耗等性能，同时也可能影响到网络节点的结构，因此，在设计路由算法时通常需要遵循以下原则：路由算法必须保证网络中的通信节点按照路由规则可以进行通信，同时确保不会发生死锁和活锁，路由算法应该尽量选择最短路径，或者限制绕道次数，以缓解网络资源紧张。路由算法在设计之前，应该对其应用的网络特点进行分析，使得路由算法对性能的优化有所侧重，比如功耗、延迟、负载均衡和服务质量等。本文提出的一种基于多值量子进化的路由算法(MultivaluedQuantum81万方数据 电子科技大学博士学位论文Evolution，MQE)，有效地融合了量子计算和进化计算的优点。虽然该算法是基于广义彼得森图的可重构结构而设计，但是其算法思想也适用于一般规则的网络结构。该算法力图根据通信流量为通信节点构建合理的通信路径，以期达到总的通信代价最小。量子编码是量子进化计算的基础，决定了后继可用的进化操作，最终影响算法的计算结果。在现有的量子进化算法中，量子编码通常是两态的，用0或者1表示一条边是否存在于路径中，这样产生的边不能保证路径的连通性，可[125-126]能构造出无效的路径，本文采用的量子编码算法是根据每个网络节点的连通性进行编码，这样保证了路径的连续性，避免了无效路径的产生。6.2.3量子编码设计根据NoC的布局结构和路由寻径的需求和约束，我们设计了多值量子编码方案，如公式(6-5)所示。12...mqjm12...(6-5)12...m按照量子编码方案得到的个体称为量子染色体，多个染色体构成量子种群，种群中的每个染色体qj对应于一条通信路径，其中j=1,2,…n,n表示种群大小。αi，222βi，γi是每个量子位三种态的概率幅度，在这里表示节点的概率，|αi|+|βi|+|γi|=1，i=1,2…m。m是量子位数，此处表示是NoC拓扑结构中节点的总个数。在编码方案中我们设计了多值量子表示方法，可以在一条染色体上携带更多的路由信息，传统的二值编码对每一条链路采用二值编码，判断路径存在或者不存在，忽略了路径之间的延续性，有可能产生无效的路径。采用多值编码，可以携带多条路径信息，更适用于路由寻径的算法需要，可以根据路径连通性，建立节点之间的连接关系，不会产生无效路径。同时多值编码携带的信息量超过二值编码，因此可以进一步提高算法的并行性。6.2.4算法实现过程本文根据路由以及布局的需求和约束，提出基于多值量子进化的算法，其中的主要方法实现描述如下：(1)产生初始种群初始种群Q(t)，其中t表示种群的迭代次数，初始种群即t=0。全部n条染色体的每个量子位概率幅度值初始化为1/√3，表示在初始状态每条染色体以相同概率处于所有可能状态的线性叠加态之中，如公式(6-6)所示。82万方数据 第六章面向多应用的可重构布局优化算法设计m301qks(6-6)jmk13其中sk是整数串（x1,x2,…xi,…xm）描述的第k个状态，xi=0,1,2，i=1，2,….m。m是量子位数，根据编码方案产生个体，构建多个初始种群。(2)观察值观察Q(t)状态，产生随机数，根据每个量子位的概率幅度，确定其状态，生成ttttt解集p(t)=(x1,x2,xj,…xn)，j=1,2…n，每个解xj为一个长度为m的整数串，其值取222决于相应量子位的观察概率|αi|，|βi|或者|γi|。(3)根据观察值产生路径将观察值所得到的解集转换成路径信息，每一个观察值代表一个路径节点，根据观察值依次从终点到起点构建路径。在路径构建中，如果选取的是重构节点，则需要判断该节点能否再建通路，重构节点因为其结构特点，在同一个应用中最多构建两组输入输出通路，如果当前待选的重构节点已经有两组通路，而且当前路径不能利用已有的通路，则不能再选择该重构节点，需要选择其他节点构建新的通路进行通信。(4)计算适应度根据通信路径上的节点类型及通信距离，按照公式(6-1)计算所有路径的通信总代价，作为染色体的适应度，比较并且记录最优路径，以作为下一步更新的参考值。(5)使用量子旋转门更新染色体更新染色体，为每个基因位选择需要增大的概率幅度，参照最优染色体的取值，使用量子旋转门，如公式(6-7)所示。aa'cossinii(6-7)b'sincosbii其中bi表示第i个量子位中，被选中增大的概率幅度，αi表示没有被选中的概率幅度，bi’和αi’分别表示根据旋转门更新后的概率幅度。其中旋转角度的计算如公式(6-8)所示:/2arcsinai/8(6-8)如果更新后的染色体相比原染色体具有更高的适应度，则用它替换原染色体进入下一代进化操作。(6)重复第(2)-(5)步，直到满足迭代终止条件，转到第(7)步。83万方数据 电子科技大学博士学位论文(7)进行种群交互操作，采用遗传算子的轮盘赌选择、交叉和变异操作更新种群中的个体。(8)判断是否满足算法终止条件，如果不满足，则回到第(2)步继续操作。如果满足终止条件则算法停止。6.3实验及结果分析为了测试算法以及可重构结构所求得的布局方案的性能，我们采用了片上网络测试中广泛使用的一组多媒体测试用例：H.263encoder、H.263decoder、MP31120363102036390801441972523380167641770538016338488470656（a）11203631033848120363764233384838016738016197380165116873750256（b）84万方数据 第六章面向多应用的可重构布局优化算法设计02523770535326470656（c）2824825197061080640289242335326770546（d）图6-8测试用例任务图(a)H.263decoder；(c)H.263encoder；(c)MP3decoder；(d)MP3encoderencoder和MP3decoder。在图6-8中显示了四个用例的任务图，图中的顶点表示NoC应用中的子任务，其编号标识了子任务的类型；图中的边表示两个子任务之间的通信关系，边上的权重表示通信流量。图中可以看出这四个测试用例具有一定的相关性，它们的部分子任务和通信关系是相同的，可重构的拓扑结构特别适用于这一类具有相关性的测试用例。6.3.1布局结构及路由线路对这一组测试用例，分别采用三种算法计算布局方案并对比分析，包括：分[117]支限界法应用于可重构2Dmesh结构；本文提出多值量子进化算法MQE应用85万方数据 电子科技大学博士学位论文于可重构2Dmesh结构；MQE算法应用于可重构广义彼得森图结构。在图6-9至图6-11分别列出了三种算法所得的布局及路由结构。为了便于对比各种方案的性能，根据公式(2-4)计算了布局方案的通信功耗，根据公式(6-1)计算了通信总代价，均在第6.3.2节中进行分析比较。如图6-9所示，该图列出了基于2Dmesh重构结构的分支限界法所得布局及路[117]由方案。图中的灰色矩形是处理单元，白色正方形是普通的交换节点，其中的编号i，表示执行第i个子任务的IPCore映射的处理单元与该交换节点相连，白色圆形是重构节点。图中的粗线表示通信的处理单元之间的路径即所经历的链路，也是拓扑结构中需要连通的链路。四个NoC应用的IPCore处理单元映射位置都是相同的，固定的，只是通过重构节点的连接更改了处理单元的连接关系，力图让通信量较大的处理单元，可以绕过交换节点中转进行通信，重构节点的通信代价小于交换节点，因此减少了总的通信代价。图6-10展示了四个测试在2Dmesh可重构结构上采用多值量子进化算法MQE计算所得的布局和路由线路图。四个应用的IPCore处理单元映射位置是相同且固定，通过简单地修改可重构节点的连接方式，产生四个面向不同应用的布局结构。在图6-11中展示了四个测试用例，在基于广义彼得森图的可重构结构上，采10582116731094（a）10582116731094（b）86万方数据 第六章面向多应用的可重构布局优化算法设计10582116731094（c）10582116731094（d）图6-9分支限界法基于2Dmesh可重构结构所得的布局及路由图(a)H.263decoder；（b）H.263encoder；(c)MP3decoder；(d)MP3encoder用多值量子进化算法MQE计算所得的布局结构和路由图。图中可以看出，四个测试NoC应用的IPCore处理单元映射的位置是固定且相同的，因此只映射一次，即可用于多个NoC应用，提高了系统重用性。在采用广义彼得森图的布局结构中，通信负载多的节点安排在内环，可以直接通信，减少了中转的代价，而通信负载10111976528304(a)87万方数据 电子科技大学博士学位论文10111976528304(b)10111976528304(c)101131976528304(d)图6-10MQE算法基于2Dmesh可重结构所得的布局及路由图(a)H.263decoder；（b）H.263encoder；(c)MP3decoder；(d)MP3encoder相对较低的节点安排在外环；然后根据每个应用的通信特征，简单地修改重构节点的连接方式，为每个NoC测试应用产生了不同的布局和路由方案。在构建的通信路径中更多地采用了由重构节点连成的路径，绕过通信代价较88万方数据 第六章面向多应用的可重构布局优化算法设计高的交换节点，在通信负载较高的处理单元之间构建较短的路径。因为本文设计的拓扑结构是面向多个应用的，因此在优先减少通信负载较高的NoC应用的通信代价基础上，力图获得多个应用的总通信代价最低。9923121323121311211121221422143030211521154545201620168810610619171917181877(a)(b)9923121323121311211121221422143030211521154545201620168810610619171917181877(c)(d)图6-11MQE算法基于彼得森图可重构结构所得的布局及路由图(a)H.263decoder；（b）H.263encoder；(c)MP3decoder；(d)MP3enecoder6.3.2实验结果方案性能对比对于三种算法在四个测试用例上得到的布局拓扑结构和路由线路进行对比分析。结合应用任务图中的通信流量，首先根据公式(2-4)中的功耗评价模型，计算89万方数据 电子科技大学博士学位论文三种算法所得布局方案的通信功耗，结果如表6-1所示。从表中可以看出MQE应用在2Dmesh结构或者彼得森图结构，通信功耗相比分支限界法都有所减少，由此看出MQE算法在求解最优化问题的优势。MQE算法用于彼得森图结构，相对2Dmesh结构，通信功耗也得到了减少，说明了基于彼得森图的可重构结构相比2Dmesh结构有效地降低了通信距离。表6-1三种算法计算所得的布局方案的通信功耗（1e-6J）比较MQE基于彼得森图与其分支限界MQE算法MQE算法他算法比较通信功耗减少基于基于基于彼得森比较分支限比较MQE2Dmesh重2Dmesh图重构结构界法基于算法基于构结构重构结构2Dmesh2DmeshH263ecoder7.30667.10296.94754.91%2.19%H263encoder10.593110.446410.16184.07%2.72%MP3decoder1.83001.39841.388824.11%0.69%MP3encoder3.63323.08193.033816.50%1.56%TotalCost23.362922.029621.53187.84%2.26%根据公式(6-1)计算布局方案的通信总代价，三种算法的计算结果如表6-2所示。对比结果可以看到MQE算法用于彼得森图结构，相比其他两种算法减少了通信总代价，比分支限界法四个测试用例总共减少了28%的通信总代价。同样是采用MQE算法，应用于彼得森结构图相比2Dmesh结构，总共减少了17.1%的通信总代价。表6-2三种算法计算所得的布局方案的通信总代价比较MQE基于彼得森图与其他分支限界MQE算法MQE算法算法比较通信总代价减少基于基于基于彼得森2Dmesh2Dmesh比较分支限比较MQE图重构结构重构结构重构结构界法基于算法基于2Dmesh2DmeshH263ecoder79999253874265563018%11.25%H263encoder939426109389482182513%24.87%MP3decoder33612312575212468663%0.85%MP3encoder56968255057830369447%44.84%TotalCost26452232298966190583528%17.10%90万方数据 第六章面向多应用的可重构布局优化算法设计MQE算法基于彼得森图的结构，在CPU2.66GHz的计算机上运行四个测试用例总耗时2.751秒。上述的实验结果显示，在可接受的时间内，基于彼得森图可重构结构上，采用MQE算法计算所得的布局结构以及路由线路，在实现了通信可达的基础上，力求通信路径最短，相比另外两种算法和结构，在实验中的所有测试用例上都获得最小的通信功耗和通信总代价。6.4本章小结本章首先描述了可重构布局结构的原理和设计方法，在规则的彼得森图结构上进行扩展，根据具体的NoC应用通信需求，不改变IPCore映射位置，只是利用重构节点改变部分拓扑关系，构建满足当前应用的布局结构，既能利用规则结构的简单易实现的特点，又可以通过局部重构，构建适用于不同NoC应用的布局结构。在可重构布局的基础上，设计了多值量子进化算法MQE用于路由及布局方案的计算。该算法采用了多值量子编码，相比传统量子编码可以携带更多的信息，增强了量子个体的多样性，并且在编码过程中摒弃传统的全路径编码，有效地利用了网络节点的连通性，避免了无效路径的产生。最后将三种不同算法应用于四个典型的测试用例，并对所得的布局方案的通信功耗和通信总代价进行对比分析，实验结果显示MQE算法基于彼得森图可重构结构，所得的布局方案相比其他算法获得了更低的通信代价。91万方数据 电子科技大学博士学位论文第七章结论与展望7.1全文总结本文主要对片上网络NoC设计中的重要步骤NoC布局以及相关问题进行研究，主要包括IPCore分配、IPCore映射、路由算法、拓扑结构和容错策略等方面。根据NoC布局问题的需求和约束条件，建立优化模型，结合智能优化算法思想，以获得高性能的布局方案为目标，设计智能优化算法以解决NoC布局过程中的优化问题。论文首先分析和总结了片上网络布局研究的国内外现状，以及智能算法的研究和应用现状；接着建立了NoC布局优化的相关模型，根据NoC布局的主要步骤IPCore分配和IPCore映射的性能要求，提出了多目标评价模型；分析了NoC结构的故障类型，提出了容错策略，包括容错结构和路由算法。然后结合NoC的布局需求和智能算法思想设计了适用于IPCore分配的优化算法MPDS和MPEL算法，以及适用于IPCore映射的MSSU算法，最后提出了基于彼得森图的可重构布局结构，在此基础上设计基于多值量子优化的布局优化算法MQG。获得的可重构布局方案不仅减少了通信代价，同时提高了布局结构的可重用性。本文的主要贡献和创新点如下：(1)根据NoC通信及故障特点，设计了基于空间冗余的容错结构，以及相应的容错路由算法。本文提出的容错机制可以恢复由交换节点故障引起的通信中断，从而提高系统可靠性；所设计的自适应的局部重路由算法，不仅可以恢复系统通信，避免死锁，而且能确保容错路径的距离最短，同时兼顾了负载平衡等性能优化。(2)根据IPCore分配的需求，设计了MPDS算法和MPEL算法。设计对换算子等进化策略以适用于分配问题的特点，在传统智能算法基础上，引入多样化处理和局部跳变搜索等策略，并提出算法收敛的参数条件。本文所设计的算法融合了PSO、GA和SA等智能算法的优点，克服传统智能算法易陷入局部最优的缺点。实验证明本文提出的算法比其他常见智能算法取得了更多，更高质量的IPCore分配方案。(3)根据IPCore映射布局的需求及约束条件，设计了MSSU算法，该算法在传统智能算法的完全随机搜索过程中引入了可控机制，再结合局部的不确定性搜索策略，实现基于小种群的优化求解和多目标优化求解，该算法兼具有SS和GA算法的优势，其解的搜索能力优于一般的智能算法，实验显示该算法求得的映射92万方数据 第七章结论与展望布局方案在数量和质量上均优于其他常见智能算法。(4)提出了基于彼得森图的可重构NoC拓扑结构。彼得森图具有网络直径短等优势，所以采用彼得森图作为重构结构的基础可以减少节点之间的通信距离。重构的布局结构无需改变处理单元的映射位置，只需通过重构节点的连接导向来调整处理单元之间的拓扑关系，就可适用于不同的NoC应用。由此方法得到的布局结构，一方面可以有效地缩短节点之间通信距离，减少中转交换节点的个数，从而达到减少通信代价的目的；另一方面可重构的策略提高了NoC系统的重用性和灵活性。(5)根据NoC映射和路由的特点及需求，设计了多值量子进化算法MQG，并应用于求解NoC的路由和构建布局方案。本文的多值量子进化编码方法相比传统编码可以携带更多的个体进化信息，从而增强了进化个体的多样性，减少陷入局部最优的可能性。在编码及解码过程中，摒弃了传统的全路径编码，而是利用路径的连续性来构建路径，不仅减少了进化个体的长度，还避免了无效路径的产生。以此为基础构建的布局方案，在避免死锁的基础上搜索最优通信路径，达到减少通信代价的目的。MQG算法思想也可以推广应用于其他类似的NP问题和优化问题的求解。7.2研究展望本文在NoC设计过程中的IPCore分配和映射优化、容错结构和路由方法、以及可重构结构设计等方面取得了一些研宄成果，但是存在需要进一步完善和研究的地方，未来的研究工作主要从以下方面展开：(1)在可靠性模型方面，目前国内外尚未有成熟的动态评价模型。本文建立的可靠性模型也是传统的基于概率方法的静态模型，该模型是采用概率方法预先估计可能出现的故障对可靠性的影响，如果能够对实际运行过程中产生的可靠性变化进行动态评价将更加有意义，我们将在今后的研究中尝试建立动态的可靠性模型。(2)本文主要研究了2D拓扑结构的优化，因为现在广泛应用的是2D拓扑结构，但是3D拓扑结构也在逐渐受到人们的关注。在今后的研究中，我们将在2D结构基础上进一步利用垂直方向上的连线特性，构建和优化分层的、3D的NoC布局结构。(3)在未来的研究中，我们将进一步考虑影响NoC布局性能的更多其他因素，建立更加完善的优化模型；在容错处理过程中，考虑更多的容错对象，建立更加完善的容错机制。93万方数据 电子科技大学博士学位论文我们将在今后的工作中进一步研究和完善NoC设计过程中的技术和实施细节，为NoC设计提供有价值的辅助方法和技术，同时也为构建NoC设计方法学提供基础。94万方数据 致谢致谢首先向我的导师杨国武教授，致以最诚挚的谢意。感谢杨老师为我提供了一个学习深造的机会和科学研究的平台，在知识学习和课题研究的各个方面给予我的悉心指导和大力帮助。杨老师具有深厚的学术功底和严谨的治学态度，是我景仰的榜样。感谢宋晓宇教授和William.N.N.Hung博士，感谢您们在我的课题研究和论文撰写中给予我的诸多指引和帮助，在科研方法和和写作技巧上对我的悉心指导，让我受益匪浅，启迪良多。感谢郭文生老师在我提交论文和申请答辩过程中给予的大力帮助。感谢实验室的各位师兄弟姐妹们，感谢大家在学习和生活上对我的关照和帮助，跟大家一起学习的岁月将会成为我的美好回忆。最后感谢我的家人，感谢您们多年来给予我的关爱和支持，我的每一次进步都有您们的功劳。95万方数据 电子科技大学博士学位论文参考文献[1]R.Marculescu,U.Y.Ogras,L.-S.Peh,etal.OutstandingresearchproblemsinNoCdesign:System,microarchitecture,andcircuitperspectives.IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems[J].2009,28(1):3-21[2]T.Bjerregaard,S.Mahadevan,T.Bjerregaard,etal.Asurveyofresearchandpracticesofnetwork-on-chip.AcmComputingSurveys[J].2006,38(1):1-51[3]J.Minje,W.W.Ro,E.-Y.Chung.ExploitingImplementationDiversityandPartialConnectionofRoutersinApplication-SpecificNetwork-on-ChipTopologySynthesis.IEEETransactionsonComputers[J].2014,63(6):1434-1445[4]H.Ou,D.Sheqin,J.Wooyoung,etal.UNISM:UnifiedSchedulingandMappingforGeneralNetworksonChip.IEEETransactionsonVeryLargeScaleIntegration(VLSI)Systems[J].2012,20(8):1496-1509[5]J.Postman,T.Krishna,C.Edmonds,etal.SWIFT:ALow-PowerNetwork-On-ChipImplementingtheTokenFlowControlRouterArchitectureWithSwing-ReducedInterconnects.IEEETransactionsonVeryLargeScaleIntegration(VLSI)Systems[J].2013,21(8):1432-1446[6]Y.S.C.Huang,K.C.K.Chou,K.Chung-Ta.Application-DrivenEnd-to-EndTrafficPredictionsforLowPowerNoCDesign.IEEETransactionsonVeryLargeScaleIntegration(VLSI)Systems[J].2013,21(2):229-238[7]E.L.deSouzaCarvalho,N.L.V.Calazans,F.G.Moraes.DynamicTaskMappingforMPSoCs.Design&TestofComputers[J].2010,27(5):26-35[8]R.Marculescu,J.Hu,U.Y.Ogras.KeyresearchproblemsinNoCdesign:aholisticperspective[C].ThirdIEEE/ACM/IFIPInternationalConferenceonHardware/SoftwareCodesignandSystemSynthesis,Jersey,2005,69-74[9]D.Bertozzi,A.Jalabert,S.Murali,etal.NoCsynthesisflowforcustomizeddomainspecificmultiprocessorsystems-on-chip.IEEETransactionsonParallelandDistributedSystems[J].2005,16(2):113-129[10]Q.Yu,P.Ampadu.AFlexibleParallelSimulatorforNetworks-on-ChipWithErrorControl.IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems[J].2010,29(1):103-116[11]S.R.Kallem.ArtificialIntelligenceAlgorithms.IOSRJournalOfComputerEngineering[J].2012,6(3):1-8[12]J.R.Koza.GeneticProgramming:OntheProgrammingofComputersbyMeansofNaturalSelection[M],Cambridge:MITPress,1993.[13]L.J.Foge,A.J.Owens,M.T.Walsh.Artificialintelligencethroughsimulatedevolution[M],NewYork:Wiley,1966.[14]H.P.Schwefel.NumericalOptimizationofComupterModels[M],NewYork:Wiley,1981.[15]A.Narayanan,M.Moore.Quantum-inspiredgeneticalgorithms[C].InternationalConferenceonEvolutionaryComputation,Nagoya,1996,61-66[16]H.Kuk-Hyun,K.Jong-Hwan.Geneticquantumalgorithmanditsapplicationtocombinatorialoptimizationproblem[C].InternationalConferenceonEvolutionaryComputation,LaJolla,2000,96万方数据 参考文献1354-1360[17]G.Zhang,W.Jin,L.Hu.Anovelparallelquantumgeneticalgorithm[C].theFourthInternationalConferenceonParallelandDistributedComputing,ApplicationsandTechnologies,LasVegas,2003,693-697[18]J.-a.Yang,B.Li,Z.Zhuang.Multi-universeparallelquantumgeneticalgorithmitsapplicationtoblind-sourceseparation[C].InternationalConferenceonNeuralNetworksandSignal,Nanjing,2003,393-398[19]H.Chen,J.Zhang,C.Zhang.Chaosupdatingrotatedgatesquantum-inspiredgeneticalgorithm[C].InternationalConferenceonCommunications,CircuitsandSystems,Chengdu,2004,1108-1112[20]A.R.Khorsand,M.R.Akbarzadeh-T.Quantumgateoptimizationinameta-levelgeneticquantumalgorithm[C].InternationalConferenceonSystems,ManandCybernetics,Hawaii,2005,3055-3062[21]P.Moore,G.K.Venayagamoorthy.Evolvingcombinationallogiccircuitsusingahybridquantumevolutionandparticleswarminspiredalgorithm[C].ConferenceonEvolvableHardware,Washington,2005,97-102[22]P.Li,S.Li.Quantum-inspiredevolutionaryalgorithmforcontinuousspacesoptimization.ChineseJournalofElectronics[J].2008,17(1):80-84[23]H.M.Ali,J.S.Oberoi,J.Liu,etal.BaseStationandRelayStationBroadbandNetworkPlanningUsingImmuneQuantumEvolutionaryAlgorithm[C].IEEE78thVehicularTechnologyConference,LasVegas,2013,1-6[24]H.Izadinia,M.M.Ebadzadeh.AdaptiveQuantum-inspiredEvolutionStrategy[C].IEEECongressonEvolutionaryComputation(CEC),Brisbane,2012,1-8[25]Z.Lu,R.Thid,M.Millberg,etal.NNSE:NostrumNetwork-on-ChipSimulationEnvironment[C].ProceedingsofSwedishSystem-on-ChipConference,Stockholm,April2005,1-4[26]M.Millberg,E.Nilsson,R.Thid,etal.TheNostrumbackbone-acommunicationprotocolstackforNetworksonChip[C].17thInternationalConferenceonVLSIDesign,Mumbai,2004,693-696[27]K.Goossens,J.Dielissen,A.Radulescu.AEtherealnetworkonchip:concepts,architectures,andimplementations.IEEEDesign&TestofComputers[J].2005,22(5):414-421[28]D.Wiklund,D.Liu.SoCBUS:switchednetworkonchipforhardrealtimeembeddedsystems[C].InternationalProceedingsonParallelandDistributedProcessingSymposium,Aizu,2003,22-26[29]W.J.Dally,B.Towles.Routepackets,notwires:on-chipinterconnectionnetworks[C].ProceedingsofDesignAutomationConference,LasVegas,2001,684-689[30]M.Coppola,R.Locatelli,G.Maruccia,etal.Spidergon:anovelon-chipcommunicationnetwork[C].InternationalSymposiumonSystem-on-Chip,Tampere,2004,16-18[31]A.Adriahantenaina,H.Charlery,A.Greiner,etal.SPIN:ascalable,packetswitched,on-chipmicro-network[C].Design,AutomationandTestinEuropeConferenceandExhibition,Munich,2003,suppl.70-73[32]A.Andriahantenaina,A.Greiner.Micro-networkforSoC:implementationofa32-portSPINnetwork[C].Design,AutomationandTestinEuropeConferenceandExhibition,Munich,2003,1128-1129[33]S.Tosun,Y.Ar,S.Ozdemir.Application-specifictopologygenerationalgorithmsfornetwork-on-chipdesign.Computers&DigitalTechniques,IET[J].2012,6(5):318-333[34]T.Takabatake.SimulationsofNoCtopologiesforgeneralizedhierarchicalcompletely-connected97万方数据 电子科技大学博士学位论文networks[C].InternationalWorkshoponReconfigurableCommunication-centricSystems-on-Chip,Montpellier,2011,1-5[35]J.Axel,T.Hannu.Networksonchip[M],Hingham:KluwerAcademicPublishers,2003.[36]W.Dally,B.Towles.PrinciplesandPracticesofInterconnectionNetworks[M],SanFrancisco:MorganKaufmannPublishersInc.,2003.[37]D.Bertozzi,L.Benini.Xpipes:anetwork-on-chiparchitectureforgigascalesystems-on-chip.CircuitsandSystemsMagazine[J].2004,4(2):18-31[38]A.Jalabert,S.Murali,L.Benini,etal.XpipesCompiler:atoolforinstantiatingapplicationspecificnetworksonchip[C].Design,AutomationandTestinEuropeConferenceandExhibition,Paris,2004,884-889[39]J.Bainbridge,S.Furber.Chain:adelay-insensitivechipareainterconnect.IEEEMicro[J].2002,22(5):16-23[40]I.Saastamoinen,M.Alho,J.Nurmi.Bufferimplementationforproteonetwork-on-chip[C].InternationalSymposiumonCircuitsandSystems,Bangkok,2003,113-116[41]T.Bjerregaard,J.Sparso.Arouterarchitectureforconnection-orientedserviceguaranteesintheMANGOclocklessnetwork-on-chip[C].ProceedingsofDesign,AutomationandTestinEurope,2005,1226-1231[42]林世俊,张凡,金德鹏.分布式同步的GALS片上网络及其接口设计.北京：清华大学学报[J].2008,48(1):32-35[43]NSFC[EB/OL].http://www.nsfc.gov.cn/[44]张磊,李华伟,李晓维.用于片上网络的容错通信算法.北京：计算机辅助设计与图形学学报[J].2007,19(4):508-513[45]常政威,网络化MPSoC高能效设计技术研究[D],成都:电子科技大学,2009[46]武畅,片上网络体系结构和关键通信技术研究[D],成都:电子科技大学,2008[47]iNocs[EB/OL].http://www.inocs.com/[48]Arteris[EB/OL].http://www.arteris.com/[49]Silistix[EB/OL].http://www.silistix.com/[50]L.Tang,S.Kumar.Atwo-stepgeneticalgorithmformappingtaskgraphstoanetworkonchiparchitecture[C].EuromicroSymposiumonDigitalSystemDesign,Belek-Antalya,2003,180-187[51]J.Hu,R.Marculescu.Energy-awaremappingfortile-basedNoCarchitecturesunderperformanceconstraints[C].ProceedingsoftheAsiaandSouthPacificDesignAutomationConference,Yokohama,2003,233-239[52]W.Zhou,Y.Zhang,Z.Mao.ParetobasedMulti-objectiveMappingIPCoresontoNoCArchitectures[C].IEEEAsiaPacificConferenceonCircuitsandSystems,Singapore,2006,331-334[53]R.K.Jena,G.K.Sharma.AMulti-ObjectiveEvolutionaryAlgorithmBasedOptimizationModelforNetwork-on-ChipSynthesis[C].FourthInternationalConferenceonInformationTechnology,LasVegas,2007,977-982[54]N.Choudhary,M.S.Gaur,V.Laxmi,etal.GAbasedcongestionawaretopologygenerationforapplicationspecificNoC[C].6thIEEEInternationalSymposiumonElectronicDesign,TestandApplication,Queenstown,2011,93-98[55]J.Sepulveda,M.,M.Strum,W.J.Chau.AMulti-objectiveAdaptiveimmunealgorithmforNoCmapping[C].17thIFIPInternationalConferenceonVeryLargeScaleIntegration,Florianopolis,98万方数据 参考文献2011,193-196[56]M.V.C.daSilva,N.Nedjah,L.M.Mourelle.Power-awaremulti-objectiveevolutionaryoptimisationforapplicationmappingonnetwork-on-chipplatforms.InternationalJournalofElectronics[J].2010,97(10):1163-1179[57]P.K.Sahu,P.Venkatesh,S.Gollapalli,etal.ApplicationmappingontomeshstructuredNetwork-on-ChipusingParticleSwarmOptimization[C].2011IEEEComputerSocietyAnnualSymposiumonVLSI,Chennai,2011,335-336[58]C.-L.Chou,R.Marculescu.Contention-awareapplicationmappingfornetwork-on-chipcommunicationarchitectures[C].26thIEEEInternationalConferenceonComputerDesignLakeTahoe,2008,164-169[59]E.Khajekarimi,M.R.Hashemi.Energy-awareILPformulationforapplicationmappingonNoCbasedMPSoCs[C].21stIranianConferenceonElectricalEngineering(ICEE),Mashhads,2013,1-5[60]L.Zhou,M.Jing,L.Zhong,etal.Task-bindingbasedbranch-and-boundalgorithmforNoCmapping[C].IEEEInternationalSymposiumonCircuitsandSystems(ISCAS),Seoul,2012,648-651[61]A.E.Zonouz,M.Seyrafi,A.Asad,etal.AFaultTolerantNoCArchitectureforReliabilityImprovementandLatencyReduction[C].12thEuromicroConferenceonDigitalSystemDesign,Architectures,MethodsandTools,Patras,2009,473-480[62]F.Refan,P.Kabiri,H.Alemzadeh,etal.Applicationspecificconfigurationofafault-tolerantNoCarchitecture[C].11thInternationalBiennialBalticElectronicsConference,Tallinn,2008,179-182[63]F.Refan,H.Alemzadeh,S.Safari,etal.Reliabilityinapplicationspecificmesh-basedNoCarchitectures[C].14thIEEEInternationalOn-LineTestingSymposium,Rhodes,2008,207-212[64]S.Mubeen,EvaluationofSourceRoutingforMeshTopologyNetworkonChipPlatforms[D],Sweden:JönköpingUniversity,June,2009[65]Y.S.Liwei.On-chipnetworkdesignautomationwithsourceroutingswitches.TsinghuaScienceandTechnology[J].2007,12(1):77-85[66]K.YoungBok,K.Yong-Bin.FaultTolerantSourceRoutingforNetwork-on-chip[C].22ndIEEEInternationalSymposiumonDefectandFault-ToleranceinVLSISystems,Rome,2007,12-20[67]N.Kavaldjiev,G.J.M.Smit,P.T.Wolkotte,etal.Routingofguaranteedthroughputtrafficinanetwork-on-chip[M],Enschede:UniversityofTwente,CentreforTelematicaandInformationTechnology(CTIT),2005.[68]J.Flich,S.Rodrigo,J.Duato.AnEfficientImplementationofDistributedRoutingAlgorithmsforNoCs[C].SecondACM/IEEEInternationalSymposiumonNetworks-on-Chip,NewcastleuponTyne,2008,87-96[69]Y.Zhang,Q.Cao.RIPNoC:Adistributedroutingschemeforbalancingon-chipnetworkload[C].2010AsiaPacificConferenceonPostgraduateResearchinMicroelectronicsandElectronicsShanghai,2010,351-355[70]J.Flich,P.Lopez,M.P.Malumbres,etal.Improvingtheperformanceofregularnetworkswithsourcerouting[C].InternationalConferenceonParallelProcessing,Toronto,2000,353-361[71]M.Dehyadgari,M.Nickray,A.Afzali-Kusha,etal.EvaluationofpseudoadaptiveXYroutingusinganobjectorientedmodelforNOC[C].The17thInternationalConferenceonMicroelectronics,Islamabad,2005,204-20899万方数据 电子科技大学博士学位论文[72]C.J.Glass,L.M.Ni.TheTurnModelforAdaptiveRouting[C].The19thAnnualInternationalSymposiumonComputerArchitecture,1992,278-287[73]J.Hu,R.Marculescu.DyAD-smartroutingfornetworks-on-chip[C].41stDesignAutomationConference,SanDiego,2004,260-263[74]M.Ali,W.Michael,S.Hellebrand.Adynamicroutingmechanismfornetworkonchip[C].23rdNORCHIPConference,Oulu,2005,70-73[75]I.Saastamoinen,M.Alho,J.Nurmi.BufferimplementationforProteonetwork-on-chip[C].InternationalSymposiumonCircuitsandSystems,Bangkok,2003,113-116[76]D.S.Tortosa,J.Nurmi.SystemmonitoringandreconfigurationinProteoNoC[C].ProceedingofReconfigurableCommunication-CentricSoCs,Montpellier,2005,99-104[77]A.-l.Cheng,Y.Pan,X.-l.Yan,etal.Ageneralcommunicationperformanceevaluationmodelbasedonroutingpathdecomposition.JournalOfZhejiangUniversity-ScienceC-Computers&Electronics[J].2011,12(7):561-573[78]A.Kalimuthu,M.Karthikeyan.ComparativeperformanceevaluationofpowerandareaNetworkonChip(NoC)architectures[C].IEEEInternationalConferenceonComputationalIntelligence&ComputingResearch(ICCIC),Coimbatore,2012,1-4[79]D.DiTomaso,S.Laha,A.Kodi,etal.EvaluationandperformanceanalysisofenergyefficientwirelessNoCarchitecture[C].InternationalMidwestSymposiumonCircuitsandSystems(MWSCAS),Boise,2012,798-801[80]W.Liu,Z.Gu,J.Xu,etal.SatisfiabilityModuloGraphTheoryforTaskMappingandSchedulingonMultiprocessorSystems.IEEETransactionsonParallelandDistributedSystems[J].2011,22(8):1382-1389[81]R.Das,S.Eachempati,A.K.Mishra,etal.Designandevaluationofahierarchicalon-chipinterconnectfornext-generationCMPs[C].IEEEInternationalConferenceonMechatronicsandAutomation,Takamatsu,2009,175-186[82]N.Muralimanohar,R.Balasubramonian,N.Jouppi.OptimizingNUCAorganizationsandwiringalternativesforlargecacheswithCACTI6.0[C].40thIEEE/ACMInternationalSymposiumonMicroarchitecture,Chicago,2007,3-14[83]P.C.Saxena,S.Gupta,J.Rai.Adelayoptimalcoterieonthek-dimensionalfoldedPetersengraph.JournalofParallelandDistributedComputing[J].2003,63(11):1026-1035[84]V.N.Sastry,T.N.Janakiraman,S.IsmailMohideen.NewpolynomialtimealgorithmstocomputeasetofParetooptimalpathsformulti-objectiveshortestpathproblems.InternationalJournalofComputerMathematics[J].2005,82(3):289-300[85]C.Grecu,A.Ivanov,R.Saleh,etal.On-linefaultdetectionandlocationforNoCinterconnects[C].12thIEEEInternationalOn-LineTestingSymposium,Como,2006,145-150[86]E.Ashkan,Y.P.M.,P.H.,etal.Designingfault-tolerantnetwork-on-chiprouterarchitecture.InternationalJournalofElectronics[J].2010,97(10):1181-1192[87]P.Bogdan,T.Dumitraş,R.Marculescu.StochasticCommunication:ANewParadigmforFault-TolerantNetworks-on-Chip.VLSIDesign[J].2007,1-17[88]P.Bogdan,R.Marculescu.Atheoreticalframeworkforon-chipstochasticcommunicationanalysis[C].InternationalConferenceonNano-NetworksandWorkshops,Nano-Net,Lausanne,2006,1-5[89]Y.Aydogan,C.B.Stunkel,C.Aykanat,etal.Adaptivesourceroutinginmultistageinterconnection100万方数据 参考文献networks[C].The10thInternationalParallelProcessingSymposiumHonolulu,1996,258-267[90]S.Murali,D.Atienz,L.Benini,etal.Amulti-pathroutingstrategywithguaranteedin-orderpacketdeliveryandfault-tolerancefornetworksonchip[C].43rdACM/IEEEDesignAutomationConference,Piscataway,2006,845-848[91]A.Sanusi,M.A.Bayoumi.Smart-flooding:Anovelschemeforfault-tolerantNoCs[C].IEEEInternationalSOCConference,Belfast,2009,259-262[92]W.Song,D.Edwards,J.L.Nunez-Yanez,etal.Adaptivestochasticroutinginfault-toleranton-chipnetworks[C].3rdACM/IEEEInternationalSymposiumonNetworks-on-Chip,SanDiego,2009,32-37[93]H.Zimmer,A.Jantsch.Error-TolerantInterconnectSchemes[M],NewYork:Springer,2006.[94]C.Chen,Y.Lu,S.D.Cotofana.Anovelflitserializationstrategytoutilizepartiallyfaultylinksinnetworks-on-chip[C].6thIEEE/ACMInternationalSymposiumonNetworks-on-Chip,Copenhagen,2012,124-131[95]Y.Ren,L.Liu,S.Yin,etal.AVLSIarchitectureforenhancingthefaulttoleranceofNoCusingquad-sparemeshtopologyanddynamicreconfiguration[C].IEEEInternationalSymposiumonCircuitsandSystems,Beijing,2013,1793-1796[96]M.A.J.Sethi,F.A.Hussin,N.H.Hamid.ImplementationofbiologicalsproutingalgorithmforNoCfaulttolerance[C].IEEEInternationalConferenceonCircuitsandSystems(ICCAS),KualaLumpur,2013,39-44[97]S.M.A.H.Jafri,G.Liang,A.Hemani,etal.Energy-AwareFault-TolerantNetwork-on-ChipsforAddressingMultipleTrafficClasses[C].15thEuromicroConferenceonDigitalSystemDesign(DSD),Izmir,2012,242-249[98]K.-Y.Hsieh,B.-C.Cheng,R.-T.Gu,etal.Fault-tolerantmeshfor3Dnetworkonchip[C].6thInternationalMicrosystems,Packaging,AssemblyandCircuitsTechnologyConference(IMPACT),Taipei,2011,202-205[99]B.Paul,M.Radu.Hittingtimeanalysisforfault-tolerantcommunicationatnanoscaleinfuturemultiprocessorplatforms.IEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems[J].2011,30(8):1197-1210[100]J.Kennedy,R.Eberhart.Particleswarmoptimization[C].IEEEInternationalConferenceonNeuralNetworks,Perth,1995,1942-1948[101]E.Masehian,D.Sedighizadeh.Multi-objectiverobotmotionplanningusingaparticleswarmoptimizationmodel.JournalOfZhejiangUniversity-ScienceC-Computers&Electronics[J].2010,11(8):607-619[102]J.H.Holland.AdaptationinNaturalandArtificialSystems[M],Cambridge:MITPress,1992[103]S.Kirkpatrick,C.D.Gelatt,M.P.Vecchi.Optimizationbysimulatedannealing.Science[J].1983,220(4598):671-680[104]J.Sun,J.Liu,W.Xu.Usingquantum-behavedparticleswarmoptimizationalgorithmtosolvenon-linearprogrammingproblems[C].DistributedAlgorithmsinScienceandEngineering,Abingdon,2007,261-272[105]J.-B.Wang,M.Chen,X.Wan,etal.Ant-colony-optimization-basedschedulingalgorithmforuplinkCDMAnonreal-timedata.IEEETransactionsonVehicularTechnology[J].2009,58(1):231-241[106]Q.Le,G.Yang,W.N.N.Hung,etal.Paretooptimalmappingfortile-basednetwork-on-chipunder101万方数据 电子科技大学博士学位论文reliabilityconstraints.InternationalJournalofComputerMathematics[J].2014,inPress,1-18[107]F.VanDenBergh,A.P.Engelbrecht.Astudyofparticleswarmoptimizationparticletrajectories.InformationSciences[J].2006,176(8):937-971[108]R.Dick,E3S(EmbeddedSystemSynthesisBenchmarksSuite)[EB/OL].http://ziyang.eecs.umich.edu/~dickrp/e3s/[109]Q.Le,G.Yang,W.N.N.Hung,etal.Amultiobjectivescattersearchalgorithmforfault-tolerantNoCmappingoptimisation.InternationalJournalofElectronics[J].2014,101(8):1056-1073[110]W.N.N.Hung,X.Song.BDDvariableorderingbyscattersearch[C].InternationalConferenceonComputerDesign,Austin,2001,368-373[111]W.N.N.Hung,S.Xiaoyu.OnoptimalcellassignmentsinPCSnetworks[C].IEEEInternationalConferenceonPerformance,Computing,andCommunicationsPhoenix,2002,225-232[112]A.RamaMohanRao,N.Arvind.Ascattersearchalgorithmforstackingsequenceoptimisationoflaminatecomposites.CompositeStructures[J].2005,70(4):383-402[113]Nirgm[EB/OL].http://nirgam.ecs.soton.ac.uk/home.php[114]L.Jain,NIRGAM:ASimulatorforNoCInterconnectRoutingandApplicationModeling[EB/OL].http://nirgam.ecs.soton.ac.uk/home.php[115]Q.Le.Performance-drivenassignmentandmappingforreliablenetworks-on-chips.JournalofZhejiangUniversity-SCIENCECComputers&Electronics[J].2014,15(11):1009-1020[116]M.M.Kim,J.D.Davis,M.Oskin,etal.PolymorphicOn-ChipNetworks[C].35thInternationalSymposiumonComputerArchitecture,Beijing,2008,101-112[117]M.Modarressi,A.Tavakkol,H.Sarbazi-Azad.Application-AwareTopologyReconfigurationforOn-ChipNetworks.IEEETransactionsonVeryLargeScaleIntegration(VLSI)Systems[J].2011,19(11):2010-2022[118]M.B.Stensgaard,J.Sparso.ReNoC:ANetwork-on-ChipArchitecturewithReconfigurableTopology[C].SecondACM/IEEEInternationalSymposiumonNetworks-on-Chip,NewcastleuponTyne,2008,55-64[119]T.Sbiai,K.Namba.NoCDynamicallyReconfigurableasTAM[C].IEEE21stAsianTestSymposium(ATS),Niigata,2012,326-331[120]R.Morris,A.K.Kodi,A.Louri.3D-NoC:Reconfigurable3Dphotonicon-chipinterconnectformulticores[C].IEEE30thInternationalConferenceonComputerDesign(ICCD),Montreal,2012,413-418[121]Y.Hoskote,S.Vangal,A.Singh,etal.A5-GHzMeshInterconnectforaTeraflopsProcessor.IEEEMicro[J].2007,27(5):51-61[122]H.Wang,X.Zhu,L.Peh,etal.Orion:apower-performancesimulatorforinterconnectionnetworks[C].35thAnnualIEEE/ACMInternationalSymposiumonMicroarchitecture,Istanbul,2002,294-305[123]M.Modarressi,H.Sarbazi-Azad.Power-awaremappingforreconfigurableNoCarchitectures[C].InternationalConferenceonComputerDesign,LakeTahoe,2007,417-422[124]H.S.M.Coxeter.self-dualconfigurationsandregulargraphs.BULL.Amer.Math.Soc.[J].1950,56(5):431-455[125]J.Hao,W.Ming-rui,L.Min,etal.Aquantum-inspiredant-basedroutingalgorithmforWSNs[C].IEEE16thInternationalConferenceonComputerSupportedCooperativeWorkinDesign,Wuhan,2012,609-615102万方数据 参考文献[126]W.Luo.AquantumgeneticalgorithmbasedQoSroutingprotocolforwirelesssensornetworks[C].IEEEInternationalConferenceonSoftwareEngineeringandServiceSciences,Beijing,2010,37-40103万方数据 电子科技大学博士学位论文攻博期间取得的研究成果发表论文[1]QianqiLe,GuowuYang,WilliamN.N.Hung,XinpengZhang,FuyouFan.Amultiobjectivescattersearchalgorithmforfault-tolerantNoCmappingoptimisation.InternationalJournalofElectronics[J].2014,101(8),1056-1073.(SCI:AJ4XB)[2]QianqiLe,GuowuYang,WilliamN.N.Hung,XiaoyuSong,FuyouFan.Performance-drivenassignmentandmappingforreliablenetworks-on-chips.JournalofZhejiangUniversity-SCIENCECComputers&Electronics[J].2014,15(11),1009-1020.(SCI:AT3WR)[3]QianqiLe,GuowuYang,WilliamN.N.Hung,XiaoyuSong,XinpengZhang.Paretooptimalmappingfortile-basednetwork-on-chipunderreliabilityconstraints.InternationalJournalofComputerMathematics[J].Accepted.(SCI)[4]QianqiLe,GuowuYang,WilliamN.N.Hung,WenshengGuo.ReliableNoCmappingbasedonscattersearch.InternationalConferenceonInformationComputingandApplications[C],Harbin,2012,640-647.(EI:13002367)[5]WenshengGuo,GuowuYang,QianqiLe,WilliamN.N.Hung,.CompleteSATsolverbasedonsettheory.InternationalConferenceonInformationComputingandApplications[C],Harbin,2012,616-623.(EI:13002364)[6]FuyouFan，ChaoZhao,QianqiLe.Theresearchonmatrixtransformationof2-levelquantumlogicgates.WaveletActiveMediaTechnologyandInformationProcessing[C],Chengdu,2013,231-234.(EI:20140917370066)[7]FuyouFan，GuowuYang,QianqiLe,QingbinLuo.Asurveyoftheresearchonmulti-valuedquantumcircuits.InternationalConferenceonWaveletActiveMediaTechnologyandInformationProcessing[C],Chengdu,2012,338-341.(EI:20130816044202)参与科研项目[1]产品设计流程建模、分析与优化工具系统测试，2013年，国家973计划子课题，项目编号2010CB328004[2]可逆逻辑电路的分类和多值量子逻辑电路的综合，2013年，国家自然科学基金项目，项目编号：61272175[3]基于广义符号轨迹赋值理论的模型检测，2012年，国家自然科学基金项目，项目编号60973016104万方数据
