论文部分内容阅读
随着多处理器系统的应用越来越广泛,系统的规模也迅速增长。由于自身使用寿命及各种外界干扰,多处理器系统中一些处理器不可避免会发生故障。并且随着系统规模的增长,处理器发生故障的概率也会随之而增加。因此,在多处理器系统的设计及实现过程中,系统的可靠性和有效性是关键问题。系统诊断即为确定系统中故障处理器的过程。在处理器发生故障时,故障处理器的诊断发挥着重要的作用。 在系统中,可以保证被检测到的最大的故障节点数称为该系统的可诊断数。可诊断数对于故障诊断扮演着重要的角色。h额外条件可诊断数作为一个新的参数可以更好的衡量系统的诊断能力。Zhang et al.在PMC模型下研究了超立方体的h额外条件可诊断数。本文中,我们通过拓宽参数h的范围进而拓展他们的结论。拓展结果为:在PMC模型下,当n-3≤h≤3n-7,n≥9时,t~h(Qn)=kh(Qn)+h。在MM*模型下,由于Zhang et al.添加了更严格的条件,因此所确定的并非真实的h额外条件可诊断数。本文将Zhang et al.的h额外条件可诊断数修正为h额外[n-1/2]点限制可诊断数,并将其关于h和n的参数范围进行拓展,进而得到以下结论:在MM*模型下,当3≤h≤n/2-1,n≥9时,超立方体的h额外2n点限制可诊断数为t~(h,2n)(Qn)=kh(Qn)+h。 本文还研究了点边混合故障下的超立方体的可诊断性。由于现实中,故障点和故障边可能会同时发生,因此研究点边混合故障情况下互连网络的可诊断性也非常重要。本文提出了一个新的参数名为h边容错可诊断数。在系统G中发生故障的边不超过h时,可以保证被检测到的最大的故障节点数称为h边容错可诊断数,记作:teh(G)。显然0边容错可诊断数即为传统的可诊断数。本文还研究了超立方体在PMC模型下的h边容错可诊断数并且得到当1≤h<n,n≥3时,teh(Qn)=n-h。 最后,本文研究了交换交叉立方体的2额外连通度。作为衡量系统容错能力的一项标准,连通度和边连通度存在诸多缺陷。因此,Harary通过限制非连通子图G-F中的连通分支满足某些特性而提出了条件连通度,其中G,F分别表示互连网络及其故障顶点集。J.Fàbrega和M.A.Fiol提出的h额外连通度为一种特殊的条件连通度。交换交叉立方体作为超立方体的一种变形具有更多良好的性质,如:直径较小,链接规模小、成本低等。本文得到当3≤s≤t时,交换交叉立方体的2额外连通度为κ2(ECQ(s,t))=3s-2。