论文部分内容阅读
随着多处理器系统的广泛应用，系统的规模在不断扩大，一些处理器会不可避免的发生故障。因此可靠性分析与故障诊断对系统的设计和维护至关重要。互连网络是多处理器系统的拓扑结构，是影响多处理器系统性能的一个关键因素。为了选取合适的互连网络，需要研究不同互连网络的一些性质。连通度和诊断数通常被用来评估互连网络的可靠性和故障诊断能力。为了更好的研究互连网络的可靠性以及故障诊断能力，一些新的度量参数被提出：超连通度，限制连通度和额外连通度以及悲观诊断数和t/k-可诊断数。在众多互连网络中星图以及Split-Star网络因其具有小直径，对称性，可分性和高容错性等优良性质而被广泛研究。 本文首先研究了星图网络Sn的可靠性。确定了当4≤h≤5时星图网络的最小点边界，推导并证明了使得Sn-F中存在一个大的连通分支且剩下所有小连通分支至多含有h-1个点的子集F所满足的条件。进而证明了当3≤h≤4时，星图Sn网络的h-额外连通度为Kh(Sn)=(h+1)n-4h+2(n≥7)。研究结果从理论上提高了星图的容错能力。 其次探讨了Split-Star网络的故障诊断能力。在PMC模型下确定了Split-Star网络悲观诊断数为tp(S2n)=4n-9。结果表明该诊断数是传统t-可诊断数的两倍，明显提高了Split-Star网络的故障诊断能力。 最后研究了k元n立方体Qkn的h-额外连通度和t/k-可诊断数之间的关系，并确定了在PMC模型下k元n立方体Qkn的h-额外连通度等于其相应的t/k-可诊断数。类似的，对BC网络来说，当k≥4，1≤h≤n-4时，有Kh(Xn)=t(n,h)，其中t(n,h)=(k+1)n-1/2(k+1)(k+2)+1。该研究结果表明对于一些已知其h?额外连通度的互连网络可以直接得到其t/k-可诊断数。