实时容错调度算法的自动模拟系统模型与设计

实时容错技术是实时系统中的关键技术之一,而实时容错调度算法则是实时容错研究领域中需要重点研究的问题.传统的实时容错调度算法的性能模拟是通过手工完成的,如果采用自动模拟方法,可以提高模拟实验的效率和准确性.首先给出一个实时容错调度算法的自动模拟系统模型,该模型定义了自动模拟系统中的关键参数.然后,提出了实时容错调度自动模拟算法.最后,研究了该自动模拟系统的软件结构.文章研究的自动模拟系统具重要的指导意义,可以参考该系统设计其他类型的调度算法的自动模拟系统.该系统的实现可大大节省用于研究实时容错调度算法的时间和费用.     

实时容错调度算法的自动模拟系统模型与设计

实时容错技术是实时系统中的关键技术之一,而实时容错调度算法则是实时容错研究领域中需要重点研究的问题。传统的实时容错调度算法的性能模拟是通过手工完成的,如果采用自动模拟方法,可以提高模拟实验的效率和准确性。首先给出一个实时容错调度算法的自动模拟系统模型,该模型定义了自动模拟系统中的关键参数。然后,提出了实时容错调度自动模拟算法。最后,研究了该自动模拟系统的软件结构。文章研究的自动模拟系统具重要的指导     

NFRL:一种分布系统的实时容错调度算法

在硬实时系统的应用中,如果硬实时任务不能在规定的时限完成,将会产生人员伤亡, 失等严重后果,为了保证在系统出错的情况下,硬实时任务仍然在能戴止时限之前完成,必须研究实时容错技术。本文从实时容错调度算法的角度出发,提出一种基于分布式系统的实时容错调度算法,并研究了该算法的时间复杂度,同时给出一个实例说明该容错调度算法的调度过程。这种容错调算法称为“无容错需求后调度算法（ＮＦＲＬ）,该实时容错调度算法     

语音识别音字转换中的快速容错算法

本文研究了汉语连续语音识别音字转换中的容错算法, 以纠正声学识别的替代、插入、删除错误。为了解决容错算法的计算量问题, 本文提出了两种快速算法。一是针对单独出现错误的快速容错算法；二是针对关键词的快速容错算法。快速算法有效地限制了容错算法的搜索空间, 提高了计算效率。快速容错算法应用在电话对话系统中, 字正确率从78.97%提高到86.68%, 关键词检测正确率从80.56%提高到88.52%,并且算法运算时间满足实时性要求。     

混合型实时容错调度算法的设计和性能分析

以往文献中研究的实时容错调度算法都只能调度单一的具有容错需求的任务.该文建立了一个混合型实时容错调度模型,提出一种静态实时容错调度算法.该算法能同时调度具有容错需求的实时任务和无容错需求的实时任务.该文还提出了一个求解最小处理机个数的算法,用于对静态实时容错调度算法的性能进行模拟分析.为了提高静态调度算法的调度性能,提出了一种动态调度算法.最后,通过模拟实验分析了静态和动态调度算法的性能.实验表明,调度算法的性能与实时任务的个数、任务的计算时间、周期和处理机个数等系统参数相关.     

分布式实时系统的容错调度算法

提出了两种分布式实时容错调度算法：副版本后调度算法（ＢＫＣＬ）及无容错需求后调度算法（ＮＦＲＬ）,并研究了算法的时间复杂度,这两种容雕工算法能同时调度具有容错需求的实时任务和无容错需求的实时任务,ＢＫＣＬ和ＮＦＲＬ所产生的调度可保证：在分布式系统中一个节点机失效的情况下,具有容错需求的实时任务仍然可在截止时间内完成,在描述了两个实时容错调度算法之后,分别证明了这两个算法的容错调度正确性。接着,阐述     

SISO过程突发性故障基于滑动容错拟合的在线诊断

以SISO过程输出环节脉冲型故障为研究对象,建立了过程轨线具有容错功能的滑动容错拟合算法,以滑动容错拟合算法为基础,构造了一组适用于多故障过程脉冲型故障的在线检测方法,以及故障幅度的统计辨识算法。通过理论分析和仿真计算,证实了本文滑动容错拟合和故障在线诊断方法的有效性。     

一类自选网络的容错直径与容错路由算法

作为加利图的一种,自选图AGn相对于其它网络结构,在并行计算及分布式计算领域有着更好的特性,因而受到广泛的重视.ANn是由翼有虎提出的基于AGn的一类新的网络结构.这个新的网络结构在直径、容错度、容错直径和汉密尔顿连通性上都优于网络AGn.虽然该网络结构已经有了较好的非容错路由算法,但是依然没有一种针对这个结构的容错路由算法以完善其实际应用.文中通过研究ANn的性质,得出了容错直径,然后基于该容错直径,设计并实现了ANn容错路由算法,最后验证了该算法的正确性.     

多处理机系统的一种实时容错调度算法

实时容错调度算法是实时系统容错研究中的重要问题.提出了一种多处理机系统的实时任务容错调度算法.该算法结合了基版本/副版本(Primary/Backup)方法和三模冗余(TMR)方法,以保证在一个节点机失效时,任务可以在其截止时限内完成.     

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上,建立了一种混合型实时容错模型,提出一种调度算法不仅可以调度有容错需求的周期任务,同时也能够调度无容错需求的周期任务和非周期非实时任务,实现了调度混合型任务的目的。     

A simple fault-tolerant adaptive and minimal routing approach in 3-D meshes

In this paper we propose a sufficient codition for minimal routing in 3-dimensional (3-D) meshes with faulty nodes,It is based on an early work of the author on minial routing in 2-dimensional(2-D) meshes,Unlike many traditional models that assume all the nodes know global fault distribution or just adjacent fault information,our approach is based on the concept of limited global fault information,First,we propose a fault model called faulty cube in which all faulty nodes in the system are contained in a set of faulty cubes.Fault information is then distributed to limited number of nodes while it is still sufficeint to support minimal routing.The limited fault information collcted at each node is represented by a vector caaled extended safety level.The extended safety level associated with a node can be used to determine the existence of a minimal path from this node to a given destination .Specifically,we study the existence of minimal paths at a given source node,limited distribution of fault information,minimal routing,and deadlock-free and livelock-free routing.our results show that any minimal routing that is partially adaptive can be applied in our model as long as the dstination node meets a certain conditon.We also propose a dynamic planar-adaptive routing scheme that offers better fault tolerance and adaptivity than the planar-adaptive routing scheme in 3-D meshes.Our approach is the first attempt to address adaptive and minimal routing is 3-D meshes with faulty nodes using limited fault information.     

Mesh网络路由算法容错性的概率分析

该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法，并对其容错性进行概率分析；在每个结点具有独立的出错概率的假设条件下，推导出路由算法成功返回由正确结点组成的路径的概率．该文运用严格的数学推理，证明了Mesh网络结点出错概率只要控制在1．87％以内，则对于多达几十万个结点的Mesh网络，提出的路由算法具有99％的概率确保找到正确结点组成的路径．路由算法的时间复杂性是线性的．模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度．     

Compressionless routing: a framework for adaptive andfault-tolerant routing

Compressionless routing (CR) is an adaptive routing framework which provides a unified framework for efficient deadlock free adaptive routing and fault tolerance. CR exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. Fault tolerant compressionless routing (FCR) extends CR to support end to end fault tolerant delivery. Detailed routing algorithms, implementation complexity, and performance simulation results for CR and FCR are presented. These results show that the hardware for CR and FCR networks is modest. Further, CR and FCR networks can achieve superior performance to alternatives such as dimension order routing. Compressionless routing has several key advantages: deadlock free adaptive routing in toroidal networks with no virtual channels, simple router designs, order preserving message transmission, applicability to a wide variety of network topologies, and elimination of the need for buffer allocation messages. Fault tolerant compressionless routing has several additional advantages: data integrity in the presence of transient faults (nonstop fault tolerance), permanent fault tolerance, and elimination of the need for software buffering and retry for reliability. The advantages of CR and FCR not only simplify hardware support for adaptive routing and fault tolerance, they also can simplify software communication layers     

Torus网络自适应容错路由算法

在应用于大规模并行计算机的互连网络的设计中,容错问题是其中的一个关键问题和难点问题。提出了一种基于Torus虫孔交换网络的容错路由算法,这一算法使用了矩形故障模型,无论故障区域大小多少和如何分布,算法始终是无死锁的,而且具有足够的自适应性,只要故障节点没有断开网络的连接,算法就能够通过选路使消息绕过故障区域,保持路由的连通性。同时,算法仅需要使用3个额外的虚拟通道。最后算法在不同故障率的Torus网络中进行了仿真实验,结果显示这一算法具有良好的平滑降级使用的特性。     

Mesh网络耐故障虫孔路由

耐故障是互连网络设计中的一个重要问题。本文提出了一种新的耐故障路由算法,并将其应用于使用虫孔交换技术的Mesh网络。由于使用了较低的路由限制,这一算法具有很强的自适应性,可以在各种不同故障域的Mesh网络中保持路由的连通性和无死锁性;由于使用了最小限度的虚拟通道,这一算法所需的缓冲器资源很少,非常适宜构建低成本的耐故障互连网络;由于根据本地故障信息进行绕行故障节点的决策,这一算法的路由决策速度较快并且易于在互连网络中实现。最后网络仿真试验显示,这一算法具有良好的平滑降级使用的性能。     

局部子立方体连通的超立方体网络容错路由算法和概率分析研究

In this paper, first we analyze and give opinions of fault tolerant routing and probabilistic analysis. Then,on the basis of locally subcube-connected hypercube networks, we put forward some ideas to develop efficient fault tolerant routing algorithms and powerful probabilistic analysis techniques to study fault tolerant models and the corre-sponding routing algorithms, which is of great importance to the research of parallel computer interconnection net-works.     

用于可重构硬件容错过程的辅助布线电路设计

目前可重构硬件的容错机制大多采用重新布局布线的方法,但是需要很长的重布线时间,难以满足工程应用的需要.为此,提出一种支持可重构单元阵列快速容错的辅助布线电路,该电路结构由二维的辅助布线模块构成,每个辅助布线模块可以读取并修改所在可重构单元的可编程开关配置数据.可重构单元阵列容错时,辅助布线电路代替外部软件执行故障线网的取消和线网重布线过程.以4位并行乘法器为例,证明了在系统容错时辅助布线电路可以有效地加速故障线网取消和重布线过程.     

基于子网的E-2DMesh网络容错单播路由算法

基于k-E-2DMesh子网连通概念和局部信息,提出分布式E-2DMesh网络容错单播路由算法。对算法容错性进行概率分析,假设每个节点具有独立的出错概率,推导出路由算法成功返回由正确节点组成路径的概率。推理结果表明,对于规模较大的E-2DMesh网络,当k值为3而节点出错概率小于0．03％时,该算法找到正确节点所组成路径的概率大于等于99％。其具有线性时间复杂性,构造的路由路径长度接近2点间最优路径长度。     

二维网格中基于最小通路区的自适应和最小容错路由算法

网格结构是并行与分布式处理中最流行的一种网络拓扑结构。在存在故障的情况下，如何设计具有最优性的容错路由算法一直是研究的热，点问题。本文研究了采用故障块模型的二维网格的最小路由问题，提出存在最小通路的一个充分必要条件。基于最小通路区（RMP）的概念，提出一种自适应的最小容错路由算法。如果源节点和目的节点之间存在最小通路区，则在最小通路区中进行自适应最小容错路由；反之，则采用多阶段最小容错路由。主要思想就是在存在故障的情况下，尽量保证路由算法能走最短路径。因为只要求知道每个节点的局部信息，故算法是分布式的。     

Fault-tolerant wormhole routing in mesh with overlapped solid fault regions

A fault-tolerant wormhole routing algorithm on mesh-connected processors is proposed. The proposed algorithm is based on the solid fault model and allows the fault polygons to be overlapped. The algorithm utilizes the position of fault region relative to the current channel to route a message around overlapped fault polygons. A node deactivating algorithm to convert a non-solid fault region into a solid fault region is also proposed. The proposed routing algorithm uses four virtual channels and is deadlock- and livelock-free.