BC互連網(wǎng)絡(luò)通信性能的研究.pdf

1、隨著并行與分布式系統(tǒng)的發(fā)展，并行計算機中處理器數(shù)量大量增加，處理器之間的互連網(wǎng)絡(luò)的性質(zhì)顯得越來越重要。同時，在具有大量處理器的系統(tǒng)中，處理器發(fā)生故障的情彤變得不可避免，系統(tǒng)必須在有故障處理器的情況下繼續(xù)工作。因此，對互連網(wǎng)絡(luò)通信性能和容錯通信方面的研究成為了并行與分布式系統(tǒng)領(lǐng)域重要的研究課題。
　　 超立方體是一種著名的互連網(wǎng)絡(luò)，具有直徑小，結(jié)點度數(shù)低等優(yōu)點。隨著對超立方體的研究的深入，研究者們提出了多種超立方體的變型，這些變型

2、普遍具有直徑大約是超立方體的一半的優(yōu)點。BC互連網(wǎng)絡(luò)是一大類超立方體變型，包含了超立方體和大部分已知的超立方體變型。BC互連網(wǎng)絡(luò)的提出為超立方體及其變型的研究提供了便利。
　　 本文主要工作如下：
　　 第一部分研究BC互連網(wǎng)絡(luò)上的容錯通信。首先，證明了n維BC互連網(wǎng)絡(luò)的故障直徑的上界為n+「log(｜Fn｜+1)()。其次，給出了BC互連網(wǎng)絡(luò)上的一種容錯單播和廣播算法。并且證明本文所提出的算法在故障結(jié)點數(shù)小于2n-2且

3、故障結(jié)點的分布滿足每一個結(jié)點至少有一個非故障鄰結(jié)點的條件時，單播算法在最壞情況下能以時間復(fù)雜度O(n log n)生成長度至多為n+「log(｜Fn｜+1)()+3的無故障路徑；而廣播算法在最壞情況下能以時間復(fù)雜度O(N log N)獲得以任意非故障結(jié)點為根的可靠生成樹，并且該生成樹的最大高度為n+「log(｜Fn｜+1)()+3。最后，通過JAVA程序相對算法的性能進行了評估。
　　 本文的第二部分主要研究BC互連網(wǎng)絡(luò)的直徑。