论文部分内容阅读
众所周知,一个互连网络的底层拓扑结构能被模拟成一个无向连通图G=(V,E),其中V是处理器的集合,E是网络中通信连线的集合.连通度是衡量该互连网络的容错性和可靠性的一个重要参数.在一定程度上,连通度能正确的反应一个含有一些故障处理器的互连网络的容错能力.然而,连通度低估了大型互连网络的容错能力.所以出于对传统的连通度参数缺点的考虑,Boesch和Esfahanian通过增加故障集的条件,提出了超连通度.后来,在超连通度的基础上,Fàbrega和Fiol提出了h-额外连通度。
在一个多处理器系统中,随着处理器的数目增加,该系统中可能会有一些处理器发生故障.所以有效地找出故障的处理器的位置是至关重要的.对一个互连网络中的每个处理器u,Lai等人通过限制与u直接相连的所有的处理器不会同时发生故障,提出了条件可诊断性。
由于k元n方体网络拥有许多理想的性质,例如当k=2时,这个网络就是著名的超立方体,所以它成为并行计算系统的一个重要的互连网络结构.在研究了k元n方体的一些性质后,本文得到:
1)当k=3时,它的1-额外连通度和2-额外连通度分别是4n-3和6n,-7;在PMC模型和MM*模型下,它的条件可诊断度分别是8n,-11和6n,-7;且在悲观策略下的可诊断度是4n-3;
2)当k≥4时,它的1-额外连通度和2-额外连通度分别是4n-2和6n-5;它的条件可诊断度在PMC模型和MM*模型下分别是8n-7和6n-5;且在悲观策略下的可诊断度是4n-2。