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

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

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

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