一种基于局部扭曲立方体多计算机网络的顺序诊断算法

顺序诊断是对多计算机网络进行故障诊断的一种比较实际的方法。局部扭曲立方体是超立方体的一种新变体结构,具有可并行处理的某些性质。在PMC模型下提出了一个基于局部扭曲立方体的顺序诊断算法。该算法表明了n维局部扭曲立方体是Ω(NlloogglNogN)-可诊断的,这里N=2n是总的结点数。

一种基于超立方体多处理机系统的快速诊断算法

为了提高可诊断系统的诊断度,可以采用悲观诊断策略进行诊断。超立方体是一种应用广泛的互连网络拓扑结构,具有可并行处理的某些性质,且n维超立方体是(2n-2)/(2n-2)-可诊断的。文中在MM*模型下,研究了超立方体的诊断问题,提出了一个O(Nlog2N)的悲观诊断算法,N是处理器总数。而经典的YML算法所需时间为O(N2.5)。因此,文中的算法在时间复杂度方面是高效的。