论文部分内容阅读
多处理器系统中,故障诊断是一个通过相互测试来识别出系统中的故障处理器的过程,在保障系统可靠度方面起到相对大的作用,并且被许多学者所研究。在1976年,Prepara et al.等人提出一种称为PMC模型的诊断方法,使得在故障诊断有了进一步的发展。由于传统的诊断方法存在一定的缺陷,在2005年,Lai et al.等人提出一种新的故障诊断方法——条件诊断。条件错误诊断度的大小比传统的诊断度大的多,因此条件错误诊断度能更好地衡量一个正则的互连拓扑结构的诊断问题。 本文主要研究的是网络拓扑结构图——排列图An,k和(n,k)-star图在PMC模型下的条件诊断度。排列图An,k和(n,k)-star图作为星图的两种不同的推广,它们不仅保留了星图的许多优点,如具有点对称性、最大的错误容错性、最短的简单路径和层次化结构,而且由于这两个图有两个参数,因此在设计网络中选择主要涉及参数,如度、直径和控制结点总数上比星图更具有灵活性。根据两个图的定义可知,当k=1时排列图An,1同构于(n,1)-star图,且均同构于完全图Kn,因此研究其诊断度不具有实际意义。本文主要利用计算机算法搜索构造和数学推理证明的方法确定了排列图An,k和(n,k)-star图两个图在PMC模型下的条件诊断度。我们得到的结论如下: 对于排列图An,k: (1)当k=2时,排列图An,k的条件诊断度tc(An,2)=4n-10,其中n≥5。 (2)当k≥3时,排列图An,k的条件诊断度tc(An,k)=4(k-1)(n-k)-2,其中n≥7。 (3)当k=n-2时,排列图An,k的条件诊断度tc(An,n-2)=8n-26,其中n≥6。 对于(n,k)-star图: (1)当2≤k≤n-3时,(n,k)-star图的条件诊断度tc(Sn,k)=n+3k-6。 (2)当k=n-2时,(n,n-2)-star图的条件诊断度tc(Sn.n-2)=6n-17,其中n≥6。