导读:本文包含了无死锁论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:死锁,路由,算法,网络,子网,模型,通道。
无死锁论文文献综述
陈凌剑[1]（2017）在《数据中心网络中节能路由算法及无死锁路由算法的研究》一文中研究指出为了满足日益增长的在线活动需求,数据中心的规模变得越来越大,很多数据中心都具有数十万台服务器。正因为数据中心的规模变得越来越大,导致如今具备大量网络设备的数据中心成为了地球上最大的能源消费者之一。本课题将从路由的角度对数据中心网络的节能问题进行研究。同样,因为数据中心的规模越来越大,提供的服务种类越来越多,经常会出现突发性数据包请求的情况,在这种情况下,很容易由于网络拥塞而导致数据包丢失。数据中心通过应用数据中心桥接技术解决了网络丢包问题,却又引入了路由死锁故障。为此,很多研究人员开展了对无死锁路由算法的研究,本课题也将针对路由死锁问题,对无死锁路由算法进行研究。本文的第一部分,从路由的角度出发,对数据中心网络的节能问题进行研究,提出了一种节能路由算法。本课题在系统初期搭建好网络拓扑结构时,以节点失效概率为主要参数计算出所有节点的重要性,从大到小排序得到重要节点排序矩阵,确保最后参与网络通信的重要节点的失效概率都很小,提高系统的可靠性。然后以重要节点排序矩阵为标准,从最不重要的节点开始,逐渐关闭对应的网络设备,只留下不可删除的重要节点进行网络通信。本文提出的算法以尽可能多的关闭网络设备为目标,为数据中心网络节省最多的能量。仿真实验结果表明,本文所提出的节能路由算法节能量更高。本文的第二部分,从限制路由路径无环路与寻找更短的路由路径角度出发,对数据中心网络的路由死锁问题进行研究,提出了一个有效的无死锁路由算法。本课题首先详细分析了数据中心网络拓扑结构的特征,在网络中构建广度优先搜索生成树来限制路由路径无环路,以此来避免死锁。同时使路由路径的长度更短,得到更低的网络平均时延和更高的网络吞吐量。另外,本文设计的无死锁路由算法还利用数据中心桥接技术,将物理层划分为多个虚拟层,既增加了路由路径的多样性,也增加了备份路由的数量,提高了路由算法的容错性。仿真实验结果显示,本文所设计的算法在保证无路由死锁的同时,网络性能也更优。(本文来源于《哈尔滨工业大学》期刊2017-12-01）
谢瑞莲[2]（2017）在《片上无死锁路由算法研究》一文中研究指出半导体技术的发展和应用需求推动着处理器设计进入“多核”甚至“众核”时代。在“多核”以及“众核”环境下,传统总线或点对点通信结构面临着性能、功耗和可扩展性等方面的不足。针对这些局限,研究者们借鉴计算机通信网络的思想提出了一种新的片上通信结构—片上网络(Network-on-Chip,NoC)。随着处理器核数的不断增加,由生产缺陷、工艺偏差和芯片老化等引发的硬故障导致NoC出现故障的概率也在相应提高。另外,网络拥塞导致数据的传输延时显着增加,NoC整体性能急剧下降。因此,本文以容错路由和拥塞路由为对象,研究2D mesh结构片上网络中无死锁容错路由算法和拥塞感知自适应路由算法。路由算法主要采用虚通道技术和无虚通道转向模型来避免死锁。本文主要内容包括:1.提出了一种面向单故障无虚通道容错路由算法在分析单故障NoC结构特点的基础上,本文提出了一种适用于容错的奇偶(Fault-Tolerant Odd-Even,FTOE)转向模型,以弥补现有转向模型应用于无虚通道容错路由算法中存在故障周围负载不均衡和丢包的问题。同时基于该转向模型本文设计了一种可重构的无虚通道容错路由(Reconfigurable and Fault-Tolerant Routing,RFTR)算法。RFTR算法可以容忍任意位置的单链路故障或者单节点故障,并且均衡了故障周围的负载,缩短了部分数据包的绕行路径。2.提出了一种面向多节点故障无虚通道容错路由算法面向多节点故障的无虚通道容错路由算法通常采用故障模型将多节点故障容错问题转换为故障区域绕行问题,从而简化了算法的复杂度。然而,现有多节点故障无虚通道容错路由算法都存在故障区域周围负载不均衡和长绕行路径的问题;并且由于数据包垂直进入故障区域边界而引入被禁止的转向,造成网络死锁。为了解决上述问题,本文将FTOE转向模型与提前预测相结合,设计了一种面向多节点故障的负载均衡无虚通道容错路由(Load-Balancing and Fault-Tolerant routing,LBFT)算法。LBFT算法只需要存储少量的故障信息就能预测故障区域的位置并且提前绕过它,这样数据包就不会垂直进入故障区域边界,避免了网络死锁。更重要的是,LBFT算法可以容忍任意位置、任意数量的节点故障,并且均衡了故障区域周围的负载,缩短了部分数据包的绕行路径。3.提出了一种面向多故障的自适应容错路由算法无虚通道容错路由算法通常采用转向模型来避免死锁,而转向模型禁止了一些转向,降低了算法的自适应性。为了采用最少数量虚通道,同时又使得容错路由算法具有更大的自适应性,本文将double-Y结构应用于片上网络中,该网络Y方向采用两条虚通道,X方向采用一条虚通道。然而,应用于double-Y网络的现有转向模型由于其自身的限制,容错路由算法只能容忍单链路故障或者单节点故障。随着故障的不断增加,越来越多的数据包被丢弃。因此,本文提出了一种新的转向模型NMad-y,该转向模型将现有转向模型中被禁止的转向变为可转,大大提高了转向模型的自适应性。本文还提出了一种新的故障信息分发机制,该机制可以分发2-hop之内邻接链路的故障信息。最后基于NMad-y转向模型和2-hop之内链路的故障信息,本文设计了一种自适应容错路由(Adaptive and Fault-Tolerant Routing,AFTR)算法。该算法可在不丢失网络性能的前提下提高网络的可靠性,实现了数据包97.43%的到达率,并且可以容忍任意位置、任意数量的链路故障和节点故障。4.提出一种面向高效拥塞传播机制的非本地自适应路由算法非本地自适应路由算法通常采用本地和远端链路的拥塞信息选择输出路径,从而大大促进网络性能。现有的非本地自适应路由算法都采用专用的拥塞信息传播网络或者将拥塞信息嵌入到数据包包头中传播。经过拥塞信息的传播,网络中的每个节点都知道远端链路的状态。然而,这些拥塞传播机制要么引入额外的硬件开销,要么使得拥塞信息传播不及时,进而造成更大的拥塞。为了解决上述问题,本文提出了一种基于消息的拥塞信息传播机制,该机制采用两种专用的消息传播拥塞信息,这样既没有引入额外的硬件开销,也使得拥塞信息传播更及时。最后本文设计了一种高效的非本地自适应路由(Efficient and Non-local Adaptive Routing,ENAR)算法。ENAR算法根据被传播的拥塞信息选择输出路径,能有效避免网络拥塞。由于该算法只考虑位于源节点和目标节点之间最小象限内的链路状态,且每个方向只比较相同数量的链路状态,因此消除了冗余信息。(本文来源于《西安电子科技大学》期刊2017-04-01）
陈洁坤,管祥生,续鹏[3]（2017）在《基于3Dmesh的新型热量均衡无死锁路由算法》一文中研究指出该文根据叁维片上网络结构温度特性,提出了一种基于3D Mesh结构的新型热量均衡路由算法TLHB(Transport Layer Heat Balance Routing),并且给出无死锁证明。通过网络仿真软件OPNET14.5,将该算法在一个4*4*4的3D Mesh网络中进行仿真,并与XYZ路由算法,TADR路由算法以及TLAR路由算法进行比较,结果显示TLHB算法在网络性能几乎没有下降的前提下,热量性能指标方面较现有的叁维路由算法有所提升。(本文来源于《电子质量》期刊2017年01期）
曹继军,王克非,庞征斌,刘路[4]（2015）在《“天河一号”正交交换机无死锁负载均衡路由算法》一文中研究指出基于正交背板的交换结构(简称为正交交换机)是实现高阶互连网络高密度封装的重要技术途径。描述了"天河一号"正交交换机的结构,分析了该正交交换机容易出现的路由环路及其死锁问题,进一步提出了无死锁的负载均衡路由算法,讨论了该路由算法优缺点。提出的路由算法已实际应用于"天河一号"高性能计算系统互连网络中,既避免了路由死锁,又达到了静态负载相对均衡,分析了路由算法的可行性与有效性。研究成果对于采用类似结构正交交换机的无死锁负载均衡路由算法设计具有借鉴意义。(本文来源于《第十九届计算机工程与工艺年会暨第五届微处理器技术论坛论文集》期刊2015-10-18）
张颖,吴宁,葛芬[5]（2014）在《基于路径的无死锁NoC多播路由器的设计》一文中研究指出针对NoC中并行处理事务的增多,将计算机网络中的多播传输模式引入到NoC路由器的设计中来,提出了一种新颖的基于路径的多播路由器设计模式.采用数据包中带有多个目的地址及数据子包的模式,实现了数据包到多个目的节点的高效传输,同时,通过引入Hamiltonian路径的无死锁处理模式,避免了数据包传输过程中死锁的发生.采用Verilog HDL实现了该模型的RTL级设计,并用Synopsys EDA软件完成功能仿真、时序验证及综合.(本文来源于《微电子学与计算机》期刊2014年11期）
邢科义,康苗苗,郜振鑫[6]（2014）在《柔性制造系统的改进粒子群无死锁调度算法》一文中研究指出基于柔性制造系统的Petri网模型,以制造期最小为优化目标,将死锁避免策略嵌入粒子群算法中,提出一种无死锁改进粒子群调度算法.该算法将粒子与工件的工序序列相对应,以位置数值的大小表示对应工件工序在执行顺序中的优先级.采用一步向前看的死锁避免策略方法对序列的可行性进行验证,提出一种跳出局部极值的策略.实例仿真结果表明了粒子群调度算法的可行性和有效性,以及改进粒子群调度算法的优越性.(本文来源于《控制与决策》期刊2014年08期）
惠晓龙,郜振鑫[7]（2014）在《一种基于Petri网的多目标无死锁蚁群调度算法》一文中研究指出蚁群算法已被广泛应用于解决调度问题,针对资源受限的项目调度问题,死锁和多目标问题是重要的课题研究。文中针对具有死锁资源受限的多目标调度问题,采用Petri网模型,研究其蚁群调度算法,以紧急项目的完成时间和所有项目的完成时间最短为优化目标,并通过仿真实验验证了文中算法的有效性和实用性。(本文来源于《电子科技》期刊2014年05期）
梁锦叶,梁家荣,苏树海[8]（2014）在《交换超立方网的无死锁虫洞路由算法》一文中研究指出针对交换超立方网络通信中所出现的死锁及延迟问题,提出了一种基于虫洞路由的无死锁算法。引入交换超立方网的s-导出子网和t-导出子网的的概念,证明了s-导出子网和t-导出子网分别同构于s维超立方体网络和t维超立方体网络。通过把交换超立方网分解成若干个s-导出子网和t-导出子网,利用虚通道技术和虫洞路由策略设计了交换超立方网络的最短路径路由算法。理论分析证明,所提出的最短路径路由算法是无死锁的,且有效地减少了交换超立方网络通信的延迟。(本文来源于《计算机应用研究》期刊2014年06期）
王新玉[9]（2014）在《二维DMesh网络中基于转弯模型的无死锁路由算法研究》一文中研究指出路由算法对整个互连网络的性能有着至关重要的影响。二维DMesh网络有效地结合了Mesh网络以及高阶路由器的优势,降低了网络的拓扑直径和平均跳步数,为消息传输提供了更多的可选择路径。针对DMesh网络,设计了一种基于转弯模型的适应性无死锁路由算法,该算法为消息传输提供了更多的灵活性。当网络中负载率较高时,能够指导消息避开拥塞区域和热点路由器,降低等待时间,最终指导消息以更快的速度到达目的节点。对新提出的路由算法进行了路径多样性方面的分析,并对算法的无死锁性进行了严格的证明。仿真实验结果表明,与DMesh网络中传统的DXY路由算法相比,这种新的适应性路由算法有效地降低了平均延迟,增加了消息传输的灵活性,最终提高了整个网络的通信性能。(本文来源于《沈阳师范大学学报(自然科学版)》期刊2014年02期）
方欢,陆阳,徐自军,杨娟[10]（2013）在《井下机车运输调度的资源分配模型及无死锁优化调度》一文中研究指出对井下机车运输系统进行无死锁调度和性能优化,首先,建立叁种不同调度策略下的资源分配Petri网模型,设计对应调度策略下无死锁标识的最大边界设置算法,证明了调度策略在最大标识边界设置下的无死锁性.然后,以最小化时耗和能耗为优化目标,利用遗传算法,采用变迁标号的自然编码方式,通过检查变迁的引发条件检测染色体的可行性,修复不可行的染色体使其对应的调度满足资源约束,从而保证了算法所利用的所有染色体均可对应系统的可行调度,最后进行实例仿真.设计的无死锁调度的最大标识边界设置算法和遗传算法为井下机车的运输调度提供了可靠的理论基础.(本文来源于《系统工程理论与实践》期刊2013年08期）
无死锁论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
半导体技术的发展和应用需求推动着处理器设计进入“多核”甚至“众核”时代。在“多核”以及“众核”环境下,传统总线或点对点通信结构面临着性能、功耗和可扩展性等方面的不足。针对这些局限,研究者们借鉴计算机通信网络的思想提出了一种新的片上通信结构—片上网络(Network-on-Chip,NoC)。随着处理器核数的不断增加,由生产缺陷、工艺偏差和芯片老化等引发的硬故障导致NoC出现故障的概率也在相应提高。另外,网络拥塞导致数据的传输延时显着增加,NoC整体性能急剧下降。因此,本文以容错路由和拥塞路由为对象,研究2D mesh结构片上网络中无死锁容错路由算法和拥塞感知自适应路由算法。路由算法主要采用虚通道技术和无虚通道转向模型来避免死锁。本文主要内容包括:1.提出了一种面向单故障无虚通道容错路由算法在分析单故障NoC结构特点的基础上,本文提出了一种适用于容错的奇偶(Fault-Tolerant Odd-Even,FTOE)转向模型,以弥补现有转向模型应用于无虚通道容错路由算法中存在故障周围负载不均衡和丢包的问题。同时基于该转向模型本文设计了一种可重构的无虚通道容错路由(Reconfigurable and Fault-Tolerant Routing,RFTR)算法。RFTR算法可以容忍任意位置的单链路故障或者单节点故障,并且均衡了故障周围的负载,缩短了部分数据包的绕行路径。2.提出了一种面向多节点故障无虚通道容错路由算法面向多节点故障的无虚通道容错路由算法通常采用故障模型将多节点故障容错问题转换为故障区域绕行问题,从而简化了算法的复杂度。然而,现有多节点故障无虚通道容错路由算法都存在故障区域周围负载不均衡和长绕行路径的问题;并且由于数据包垂直进入故障区域边界而引入被禁止的转向,造成网络死锁。为了解决上述问题,本文将FTOE转向模型与提前预测相结合,设计了一种面向多节点故障的负载均衡无虚通道容错路由(Load-Balancing and Fault-Tolerant routing,LBFT)算法。LBFT算法只需要存储少量的故障信息就能预测故障区域的位置并且提前绕过它,这样数据包就不会垂直进入故障区域边界,避免了网络死锁。更重要的是,LBFT算法可以容忍任意位置、任意数量的节点故障,并且均衡了故障区域周围的负载,缩短了部分数据包的绕行路径。3.提出了一种面向多故障的自适应容错路由算法无虚通道容错路由算法通常采用转向模型来避免死锁,而转向模型禁止了一些转向,降低了算法的自适应性。为了采用最少数量虚通道,同时又使得容错路由算法具有更大的自适应性,本文将double-Y结构应用于片上网络中,该网络Y方向采用两条虚通道,X方向采用一条虚通道。然而,应用于double-Y网络的现有转向模型由于其自身的限制,容错路由算法只能容忍单链路故障或者单节点故障。随着故障的不断增加,越来越多的数据包被丢弃。因此,本文提出了一种新的转向模型NMad-y,该转向模型将现有转向模型中被禁止的转向变为可转,大大提高了转向模型的自适应性。本文还提出了一种新的故障信息分发机制,该机制可以分发2-hop之内邻接链路的故障信息。最后基于NMad-y转向模型和2-hop之内链路的故障信息,本文设计了一种自适应容错路由(Adaptive and Fault-Tolerant Routing,AFTR)算法。该算法可在不丢失网络性能的前提下提高网络的可靠性,实现了数据包97.43%的到达率,并且可以容忍任意位置、任意数量的链路故障和节点故障。4.提出一种面向高效拥塞传播机制的非本地自适应路由算法非本地自适应路由算法通常采用本地和远端链路的拥塞信息选择输出路径,从而大大促进网络性能。现有的非本地自适应路由算法都采用专用的拥塞信息传播网络或者将拥塞信息嵌入到数据包包头中传播。经过拥塞信息的传播,网络中的每个节点都知道远端链路的状态。然而,这些拥塞传播机制要么引入额外的硬件开销,要么使得拥塞信息传播不及时,进而造成更大的拥塞。为了解决上述问题,本文提出了一种基于消息的拥塞信息传播机制,该机制采用两种专用的消息传播拥塞信息,这样既没有引入额外的硬件开销,也使得拥塞信息传播更及时。最后本文设计了一种高效的非本地自适应路由(Efficient and Non-local Adaptive Routing,ENAR)算法。ENAR算法根据被传播的拥塞信息选择输出路径,能有效避免网络拥塞。由于该算法只考虑位于源节点和目标节点之间最小象限内的链路状态,且每个方向只比较相同数量的链路状态,因此消除了冗余信息。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
无死锁论文参考文献
[1].陈凌剑.数据中心网络中节能路由算法及无死锁路由算法的研究[D].哈尔滨工业大学.2017
[2].谢瑞莲.片上无死锁路由算法研究[D].西安电子科技大学.2017
[3].陈洁坤,管祥生,续鹏.基于3Dmesh的新型热量均衡无死锁路由算法[J].电子质量.2017
[4].曹继军,王克非,庞征斌,刘路.“天河一号”正交交换机无死锁负载均衡路由算法[C].第十九届计算机工程与工艺年会暨第五届微处理器技术论坛论文集.2015
[5].张颖,吴宁,葛芬.基于路径的无死锁NoC多播路由器的设计[J].微电子学与计算机.2014
[6].邢科义,康苗苗,郜振鑫.柔性制造系统的改进粒子群无死锁调度算法[J].控制与决策.2014
[7].惠晓龙,郜振鑫.一种基于Petri网的多目标无死锁蚁群调度算法[J].电子科技.2014
[8].梁锦叶,梁家荣,苏树海.交换超立方网的无死锁虫洞路由算法[J].计算机应用研究.2014
[9].王新玉.二维DMesh网络中基于转弯模型的无死锁路由算法研究[J].沈阳师范大学学报(自然科学版).2014
[10].方欢,陆阳,徐自军,杨娟.井下机车运输调度的资源分配模型及无死锁优化调度[J].系统工程理论与实践.2013
论文知识图
