新型互連網絡的可靠性-連通度與診斷性研究.pdf

1、新型互連網絡是多處理器計算機網絡拓撲結構的發(fā)展方向。新型互連網絡由于結構上的對稱性、正則性、組合的遞歸性以及相對較小的網絡直徑等特征，使得其具有低成本、高容錯、路由簡單等優(yōu)點。新型互連網絡的可靠性問題是多處理器新型互連網絡計算機系統(tǒng)發(fā)展過程中亟待解決的關鍵問題。新型互連網絡可靠性研究的核心內容是連通度和診斷性研究。然而，迄今為止新型互連網絡的可靠性研究尚處起步階段，有些方面還未涉及，特別是在連通度和診斷性的某些方面，這些情況嚴重限制了新

2、型互連網絡的應用和推廣?；诖?，本文采用集合論、圖論、計算機算法以及數據統(tǒng)計分析等相關方法對新型互連網絡的可靠性問題展開研究。本文的研究將有助于厘清新型互連網絡的可靠性能，為我國發(fā)展高可信網絡提供重要的理論基礎和性能參數。
　　本文首先以條件t-可診斷為研究對象，利用F、T、M、HF四個彼此關聯的結點集合對互測PMC模型下的條件t-可診斷展開研究，得出互測PMC模型下關聯集合的關聯規(guī)則。以此為基礎，設計了互測PMC模型下基于關聯集

3、合的條件t-可診斷算法。進而對互測PMC模型下的條件t-可診斷的判定算法展開研究，在得到基于互測PMC模型條件t-可診斷的充要條件之后，設計了條件故障集合的求取算法和基于互測PMC模型的條件t-可診斷判定算法。該算法能快速地對系統(tǒng)是否屬于條件t-可診斷進行判定。之后，本文以建立可區(qū)分函數的全新視角來對條件故障集合的可區(qū)分性展開研究，提出了基于互測PMC模型的條件故障集合可區(qū)分函數，并在此基礎上形成基于互測PMC模型的條件t-可診斷的判定

4、函數和基于互測PMC模型的條件診斷度求取算法。這些研究成果對于提高系統(tǒng)的診斷速度、降低條件診斷度的計算難度和改善條件t-可診斷的判定方法等方面有著重要的理論價值和現實意義。
　　其次，針對新型互連網絡的最新拓撲研究成果——交換交叉立方網絡的拓撲性質、連通度和診斷性展開研究。通過對交換交叉立方網絡進行拓撲分析得出交換交叉立方網絡的拓撲性質，并以其拓撲性質為基礎研究得出交換交叉立方網絡的條件連通度和限制連通度均為2s，其中t≥s＞2。

5、再以交換交叉立方網絡的限制連通度為基礎，根據限制連通度與條件診斷度之間的關聯關系研究得出交換交叉立方網絡的條件診斷度為4(s-1)+1，其中t≥s＞2。交換交叉立方網絡的連通度和診斷性的研究成果將有助于未來對其展開可靠性評價。
　　再次，本文進行了新型互連網絡診斷性的拓展研究。以g正確鄰結點條件t-可診斷理論為基礎，提出了強g正確鄰結點條件t-可診斷的定義，并展開拓撲性質研究。進而，以n維超立方網絡為研究對象，研究了n維超立方網絡

6、的強g正確鄰結點條件t-可診斷的性質定理。在此基礎上，通過研究得出互測PMC模型下n維超立方網絡的強g正確鄰結點條件診斷度小于22g(n-2g)+22g-1-1，其中n≥5，1≤g＜［n/3]。強g正確鄰結點條件t-可診斷的提出拓展了診斷性研究的邊界，也豐富了診斷性理論，具有一定的研究價值。
　　最后，本文對研究工作進行總結歸納。同時通過分析給出新型互連網絡可靠性——連通度與診斷性研究下一步的研究方向，具體包括比較診斷模型下的診斷