Bi-Level Reconfigurations of Fault Tolerant Arrays in Bi- Modal Computational Environments

本研究的目的是为处理器阵列开发容错架构和算法。假设这些系统的计算负载在两个阶段之间交替：一个以重负载和严格的响应时间约束为特征的严格阶段，以及一个以轻负载和相对宽松的响应时间约束为特征的宽松阶段。在这种负载下，采用双级算法对故障后的系统进行重新配置。具体来说，在一个称为快速响应级别的级别上，在严格阶段使用本地分布式容错算法来实现快速故障恢复，但代价是可能会迅速降低容忍未来故障的潜力。为了最小化这种退化的影响，第二个级别，称为优化级别，在放松阶段使用相对较慢的重组算法将系统恢复到确保系统任务剩余部分具有足够容错能力的状态。计算阵列提供的计算能力可与超级计算机相媲美。这些数组的容错是一个非常重要的问题。传统方法侧重于用固定的本地备用池重新配置故障处理器。这种不灵活性降低了故障覆盖能力，从而降低了整个系统的可靠性。本文研究的方法考虑了两种类型的算法：局部算法和全局算法。局部算法利用局部信息重新配置故障处理器，全局算法根据容错标准优化冗余。这两种算法的组合可以更好地权衡整个系统的容错性。

The objective of this research is on developing fault-tolerant architectures and algorithms for processor arrays. The computational loads of these systems are assumed to alternate between two phases: a strict phase that is characterized by a heavy load and strict constraints on response time, and a relaxed phase that is characterized by a light load and relatively relaxed constraints on response time. Under this type of load, a bi-level algorithm is applied to reconfigure the system after faults. Specifically, at one level, called the fast response level, a local distributed fault-tolerant algorithm is used during strict phases to achieve fast fault recovery at the expense of possible rapid degradation in the potential to tolerate future faults. To minimize the effect of this degradation, a second level, called the optimization level, uses a relatively slow reorganization algorithm during relaxed phases to restore the system into a state that ensures adequate fault tolerance in the remaining part of the system's mission. Computing arrays provide computational power that is comparable to that of supercomputers. Fault tolerance of these arrays is a very important issue. Traditional approaches focus on reconfiguring a faulty processor with a fixed local pool of spares. This inflexibility reduces the fault coverage capability and thus the reliability of the entire system. The approach studied in this research considers two types of algorithms: local algorithms and global algorithms. Local algorithms reconfigure faulty processors using local information, while global algorithms optimizes redundancy according to some fault tolerance criteria. A combination of these two types of algorithms allow a better tradeoff in fault tolerance of the overall system.