分层超立方网络的可靠性评估

刘西蒙，张郁芳，周书明，李小燕

（1.福州大学数学与计算机科学学院，福建 福州 350108；2.福州大学网络安全福建省高校重点实验室，福建 福州 350108；3.福建师范大学数学与信息学院，福建 福州 350007）

1 引言

随着多处理器系统规模不断扩大，处理器发生故障的情形不可避免。为了确保系统的稳定运行，需要对处理器进行测试和诊断，从而修复或更换有故障的处理器，以提高系统的可靠性。

故障诊断是评估系统可靠性和可用性的关键研究。系统中识别故障处理器的过程称为系统级诊断[1]。最早的系统级诊断模型由Preparata、Metze和Chien[1]提出，称为PMC 模型。PMC 模型通过相邻2 个处理器互相测试来进行诊断。Maeng 和Malek[2]提出了基于比较的MM 模型，该模型是通过一个处理器把任务发送到与它相邻的2 个处理器，然后比较它们的测试结果来进行诊断。随后，Sengupta 等[3]提出了MM*模型，该模型是MM 模型的一种特殊情况，在该模型下，每个处理器均对与它有直接物理相连的任意2 个不同处理器的测试结果进行比较。在系统级诊断中，如果系统可以检测出不超过t个故障处理器，则称该系统为t-可诊断的。在t-诊断系统中可以实现的t的最大值称为诊断度[1]。由于系统的最小度的限制，传统的诊断度很小。为进一步提高系统的诊断能力，Zhang 等[4]提出了一种新的度量方法，称为h-额外条件诊断度，并研究了超立方网络的h-额外条件诊断度。图G的h-额外条件诊断度（用(G)表示）是指在满足G中每个无故障分支至少包含h+1个顶点的条件下，G可以保证识别的最大故障顶点数目。……