Adaptive System-Level Diagnosis for Hypercube Multiprocessors
Adaptive System-Level Diagnosis for Hypercube Multiprocessors
复制标题
超立方体多处理器的自适应系统级诊断
DOI：
10.1109/12.543709
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
F. Lombardi
中科院分区：
文献类型：
--
作者：
C. Feng;L. Bhuyan;F. Lombardi
系统级诊断是多处理器计算系统故障检测和定位的重要技术。高效的诊断是非常需要的，以维持原始系统功率。此外，有效的诊断是特别重要的多处理器系统具有高可扩展性，但低连接。由于诊断成本高、可诊断性有限，现有的大多数结果在实际中并不适用。过d故障诊断（其中d是可诊断性）在文献中仅使用概率方法进行了解决。针对这两个问题，我们提出了一个分层的自适应系统级诊断方法的超立方体系统，采用分而治之的策略。我们首先提出了一个概念算法HADA制定严格的分析。然后，我们提出了它的实用变种IHADA。在HADA和IHADA中，过d故障问题本质上是通过确定性方法来解决的。三个措施的诊断成本（诊断时间，测试次数，测试链接数）进行了分析，所提出的算法。证明了该方法所需的诊断代价低于以往的诊断算法。结果表明，所提出的算法的诊断成本取决于系统中的故障单元的数量和位置，当只有少量的故障单元存在时，成本非常低。它还表明，我们的算法的特点是较低的成本比一个悲观的诊断算法，以较低的诊断成本为较低的准确度。nCUBE上的实验结果。
System-level diagnosis is an important technique for fault detection and location in multiprocessor computing systems. Efficient diagnosis is highly desirable for sustaining the original system power. Moreover, effective diagnosis is particularly important for a multiprocessor system with high scalability but low connectivity. Most of the existing results are not applicable in practice because of the high diagnosis cost and limited diagnosability. Over-d fault diagnosis, where d is the diagnosability, has only been addressed using a probabilistic method in the literature. Aiming at these two issues, we propose a hierarchical adaptive system-level diagnosis approach for hypercube systems using a divide-and-conquer strategy. We first propose a conceptual algorithm HADA to formulate a rigorous analysis. Then we present its practical variant IHADA. In HADA and IHADA, the over-d fault problem is inherently tackled through a deterministic method. Three measures for diagnosis cost (diagnosis time, number of tests, and number of test links) are analyzed for the proposed algorithms. It is proved that the diagnosis cost required by our approach is lower than in previous diagnosis algorithms. It is shown that the diagnosis cost for the proposed algorithms depends on the number and location of faulty units in the system and the cost is extremely low when only a small number of faulty units exist. It is also shown that our algorithms are characterized by lower costs than a pessimistic diagnosis algorithm which trades lower diagnosis cost for a lower degree of accuracy. Experimental results on the nCUBE are provided.