可重构阵列自主容错方法研究

设计了一种具有故障自诊断和自修复能力的可重构阵列单元结构。在功能细胞单元内部实现分布式的故障自诊断,在测试到故障后,可以自主地将距故障单元最近的空闲单元进行替换,接着自动取消受故障影响的线网,并在新的布线端点间对这些线网重新布线。以4位并行乘法器为例,实验结果证明了可重构单元阵列的故障自修复能力,并验证其重构时间较短且可靠性较高。     

环网处理器阵列的容错重构技术

高效的容错技术对于提高多处理器系统的可靠性至关重要。环网(Torus)是连接多处理器阵列的重要网络结构,而环网处理器阵列上的容错重构技术目前尚属空白。针对环网阵列的特殊连接方式,将环网阵列重构问题转化为矛盾图上求解最大独立集问题。矛盾图上的结点表示故障处理器的替换方案,而边代表了不同替换方案之间的不可共存特性。主要是根据三种不同的冗余处理器分布方案,设计生成矛盾图算法,求解最大独立集算法,以及由独立集生成逻辑处理器阵列算法,取得了令人满意的结果。实验结果表明,当阵列规模较小或故障率较低时,一行一列和十字型的冗余单元分布的重构能力较好;而随着阵列规模或故障率的增大,三种冗余单元分布策略的重构成功率都随之下降,但可通过增加冗余单元以及调整冗余分布来改善容错效果。此外,从实验结果中还可以看出,环网处理器阵列的容错能力显然优于网格(Mesh)处理器阵列。     

三维可重构阵列互连资源在线分布式容错方法

设计了一种新型三维可重构阵列结构, 并且对其互连资源在线分布式容错方法进行了研究。系统由相同的功能细胞和开关块以三维结构组成, 通过在线输入测试向量对互连线进行故障定位, 并且实现故障连线分层自修复。以四位加法/减法器电路为设计实例, 对可重构阵列功能和容错能力进行验证。实验结果表明该方法可有效完成容错, 且时间开销小、容错能力强、资源利用率高。     

可重构阵列的同步性能优化算法

可重构多处理器阵列上的容错技术可用来重构含有故障单元的处理器阵列,以便获得最大可用的目标阵列。现有的研究成果主要侧重于重构算法的构造,还没有涉及对重构后目标阵列的同步通讯性能的研究。提出了一种改善目标阵列同步通讯性能的电路优化算法,用来降低目标阵列行与行之间通讯的延时,使得相邻两行处理器的通讯尽可能达到同步。实验结果表明,提出的算法对不同大小、不同故障率的阵列都有相应的同步通讯性能的改善。     

一种含浮动端点的斯坦纳树的构造算法

在集成电路的自动布图技术中，在完成布局过程，即各模块（或子电路单元）的拓扑位置确定以后，布线需要完成各电路模块之间的连接。斯坦纳树的构造问题可以应用于总体布线；如果考虑已有单元或连线的障碍，它也可以应用于详细布线。     

基于信号重构的可重构机械臂主动分散容错控制

针对可重构机械臂系统传感器故障,提出一种基于信号重构的主动分散容错控制方法. 基于可重构机械臂系统模块化属性,采用自适应模糊分散控制系统实现正常工作模式时模块关节的轨迹跟踪控制. 当在线检测出位置或速度传感器故障时,分别采用数值积分器或微分跟踪器重构相应信号,并以之代替故障信号进行反馈实现系统的主动容错控制. 此方法充分利用了冗余信息,避免了故障关节控制性能的下降对其他关节的影响. 数值仿真结果验证了所提出容错控制方法的有效性.     

可重构电子系统芯片级在线自主容错方法研究

可重构电子系统芯片固定型故障的传统容错设计往往采用集中式控制方法,存在测试时间长、硬件资源利用率低、对外部控制器依赖性高等问题。因此,设计了一种具有分布式自主容错能力的可重构细胞阵列,通过将细胞内部查找表输出与参考值进行比较的方式进行循环检测,并利用冗余存储单元对故障查找表进行修复。以四位并行乘法器为例进行仿真验证,实验结果表明,新型可重构阵列的自主容错设计方法,比现有设计的硬件开销小,修复时间短,容错能力强,且设计复杂度不受阵列规模影响。     

容错处理器阵列的并行重构及VHDL实现

网格连接的处理器阵列是一种应用广泛的高性能体系结构,而容错处理器阵列的重构技术是近年来的研究热点之一.现有的研究多数集中在串行重构算法上,忽视了该结构重构时内在的可并行性.本文根据阵列结构的特点设计了一种基于VHDL语言的重构算法,该算法从第一行的各个无故障处理器单元同时向下选路,具有潜在的并行性,.实验结果表明,与现有的串行算法相比,本文提出的并行算法同样能够生成最大规模的目标阵列并且当物理阵列大小为48×48,本文提出的并行算法加速重构将近20倍.     

可重构系统的演化修复机制

利用演化算法实现系统自修复是一种新的容错设计思路,但是演化是一个非常耗时的过程.已有的演化容错系统多属于静态演化,演化过程仅发生在系统设计阶段,系统在运行过程中不具有演化修复的能力.这类演化容错系统虽然可以避免演化耗时,但是只能修复已知错误,无法修复未知错误.针对上述问题,文中提出一种基于动态演化的修复机制,容错系统采用可重构系统和被检测系统的耦合设计方案.当被检测系统出现故障时,可重构系统通过系统演化实现在线自修复.为了减少演化耗时,系统根据错误类型采取不同措施:如果出现已知错误,系统直接在预置配置库中搜索修复配置;如果出现未知错误,则通过动态演化在线生成修复配置,并更新预置配置库.最后,将该容错设计方案用于典型电路的故障模式.实验结果表明,文中提出的演化修复机制提高了系统运行的实时可靠性,预置配置库设计减少了演化耗时.     

基于SRAM型FPGA的实时容错自修复系统设计方法

为提高辐射环境中电子系统的可靠性,提出了一种基于SRAM型FPGA的实时容错自修复系统结构和设计方法。该设计方法采用粗粒度三模冗余结构和细粒度三模冗余结构对系统功能模块进行容错设计;将一种细粒度的故障检测单元嵌入到各冗余模块中对各冗余模块进行故障检测;结合动态部分重构技术可在不影响系统正常工作的前提下实现故障模块的在线修复。该设计结构于Xilinx Virtex誖-6 FPGA中进行了设计实现,实验结果表明系统故障修复时间和可靠性得到显著提高。     

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     

基于JBits的一种可重构数据处理系统可靠性研究

空间太阳望远镜(SST)是一颗对太阳进行观测的科学卫星,它使用FPGA芯片对每天采集的大量数据进行预处理.高昂的建造费用和恶劣的工作环境,确保SST数据的高可靠性成为一项艰巨任务.改进了常规TMR结构,提出一种基于配置数据的可重构硬件故障检测和修复方法,使用JBits工具简化对配置数据的各种操作.此结构和方法能及时检测到故障,通过硬件重构消除故障,提高系统可靠性.采用Markov过程理论对系统可靠性进行分析,结果表明可靠性可得到显著提高.     

可重构系统中硬件任务布局布线算法研究

可重构计算系统中,二维可重构硬件任务的布局布线问题是影响系统资源利用率的重要因素。在异质化的可重构器件和任务模型基础上,对可重构硬件任务进行了适当分类,并提出一种能够对多类型可重构硬件任务同时布局布线的算法DRS-TCW。实验表明,该算法能够有效提高可重构器件的资源利用率和任务布线连通率。     

Explorations in design space: unconventional electronics designthrough artificial evolution

Three hypotheses are formulated. First, in the “design space” of possible electronic circuits, conventional design methods work within constrained regions, never considering most of the whole. Second, evolutionary algorithms can explore some of the regions beyond the scope of contentional methods, raising the possibility that better designs can be found. Third, evolutionary algorithms can in practice produce designs that are beyond the scope of conventional methods, and that are in some sense better. A reconfigurable hardware controller for a robot is evolved, using a conventional architecture with and without orthodox design constraints. In the unconstrained case, evolution exploited the enhanced capabilities of the hardware. A tone discriminator circuit is evolved on an FPGA without constraints, resulting in a structure and dynamics that are foreign to conventional design and analysis. The first two hypotheses are true. Evolution can explore the forms and processes that are natural to the electronic medium, and nonbehavioral requirements can be integrated into this design process, such as fault tolerance. A strategy to evolve circuit robustness tailored to the task, the circuit, and the medium, is presented. Hardware and software tools enabling research progress are discussed. The third hypothesis is a good working one: practically useful but radically unconventional evolved circuits are in sight     

层次式FPGA快速可布性布线算法

提出了一种针对层次式结构FPGA的快速拆线重布布线算法.利用历史拆线信息衡量拆线区域的可布性、可重布性及拆线影响力,形成独特的资源竞争解决机制;在禁忌搜索框架下选取禁忌拆线点、拆线路径与拆线线网,并在禁忌策略的指导下解决资源冲突,提高拆线有效性与速度.文中算法分为初始布线阶段与拆线重布2个阶段.在布线过程中,针对层次式结构引入简洁实用的布线线序.实验结果表明,该算法中的拆线机制可以有效地减少拆线数目,显著提高了运行速度.     

FT²EI: A Dynamic Fault-Tolerant Routing Methodology for Fat Trees with Exclusion Intervals

Fault tolerance in the interconnection network of large clusters of PCs is an issue of growing importance, since their increasing size also increases the failure probability. The fat-tree topology is usually used in these machines since it has become very popular among high-speed interconnect manufacturers. This paper proposes a new distributed fault-tolerant routing methodology for fat trees. Unlike other previous proposals, it does not require additional network hardware, and its memory requirements, switch hardware, and routing delay scales up with the network size. Indeed, it nullifies only the strictly necessary paths, allowing adaptive routing through the healthy paths. The methodology is based on enhancing the interval routing scheme with exclusion intervals. Exclusion intervals are associated to each switch output port and represent the nodes that are unreachable from this port after a fault. We propose a methodology to identify the links where the exclusion intervals must be updated after a fault, the values to write on them, and a very efficient mechanism to distribute the required information through the network without stopping the system activity. Our methodology can tolerate a high number of network failures with a low degradation in performance. Moreover, it can achieve zero packet losing during the updating period.     

确定区域详细布线算法

提出了一种确定区域的详细布线算法,它能对不同设计模式进行布线。该算法能适用于任意多层布线情况,并且支持不同布线层具有的不同工艺参数,在构造布线树时,考虑芯片当前的走线拥挤度,使布线比较平均,并加快了算法运行速度、改善了布线质量,在连接两点线网时,构造基于二维迷宫布线结果的分层图,提出了一种对分层图的启发式染色算示来进行布线层分配,大大提高算法布线速度,采用拆线重布的方法来处理布线失败的线网。     

一种基于BENES网络的可重构比特置换系统设计

采用ATM交换机中的BENES网络，提出了一种简洁正确的寻径算法，在可重构密码芯片上实现比特置换功能单元，能够完成N！种N到N的任意比特置换。该方法可以支持新的密码算法，加速分组密码，减少资源占用。     

Fault Tolerance Using Dynamic Reconfiguration on the POEtic Tissue

Fault tolerance is a crucial operational aspect of biological systems and the self-repair capabilities of complex organisms far exceeds that of even the most advanced electronic devices. While many of the processes used by nature to achieve fault tolerance cannot easily be applied to silicon-based systems, in this paper we show that mechanisms loosely inspired by the operation of multicellular organisms can be transported to electronic systems to provide self-repair capabilities. Features such as dynamic routing, reconfiguration, and on-chip reprogramming can be invaluable for the realization of adaptive hardware systems and for the design of highly complex systems based on the kind of unreliable components that are likely to be introduced in the not-too-distant future. In this paper, we describe the implementation of fault tolerant features that address error detection and recovery through dynamic routing, reconfiguration, and on-chip reprogramming in a novel application specific integrated circuit. We take inspiration from three biological models: phylogenesis, ontogenesis, and epigenesis (hence the POE in POEtic). As in nature, our approach is based on a set of separate and complementary techniques that exploit the novel mechanisms provided by our device in the particular context of fault tolerance.