《並行系統規則互連網路的容錯性研究》是依託山西大學，由馮凱擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：並行系統規則互連網路的容錯性研究
- 項目類別：青年科學基金項目
- 項目負責人：馮凱
- 依託單位：山西大學
項目摘要,結題摘要,
項目摘要
並行計算機系統功能的實現很大程度上依賴於系統互連網路的性能。互連網路的容錯性是衡量網路性能的關鍵指標，它用於表征有故障發生時網路中某些特有性質的保持能力。本項目擬以圖論為工具重點研究規則互連網路在出現故障的情況下對可匹配性以及子網路存在性的保持能力，主要內容包括：(1) 對於幾類著名規則互連網路，分別在隨機故障和條件故障下研究度量可匹配性的容錯參數，並設計相應的匹配查找算法；(2) 探究能確保規則互連網路對可匹配性有較強容錯能力的充分條件；(3) 對於幾類具有疊代結構的著名規則互連網路，研究衡量子網路保持程度的容錯參數，設計相應的子網路搜尋算法；(4) 對一些特定的規則互連網路中低維子網路的存在性進行機率預測研究，並進行數值模擬分析。本項目的研究成果有助於科學地分析規則互連網路的容錯性，可以為大規模並行系統互連網路的設計與最佳化提供有益參考。
結題摘要
並行計算機系統將多個處理器按照某種互連網路連線起來，使得這些處理器通過信息傳輸互相配合，從而提高運算能力。系統互連網路的性能對系統功能的實現起著至關重要的作用。互連網路的容錯性是度量網路性能的關鍵指標之一，它用於表征有故障發生時網路中某些特有性質的保持能力。本項目以圖論為數學工具研究了幾類著名規則互連網路在出現故障的情況下對可匹配性以及子網路存在性的保持能力，主要內容包括：（1）在隨機故障下對n維環面網路的強匹配排除問題進行了研究，這一工作使n維環面網路相應的強匹配排除性質得到了完整刻畫，並為在這類網路中設計無故障匹配搜尋算法提供了解決策略；（2）在條件故障下對k元n方體網路的強匹配排除問題進行了研究，對這類網路在條件故障下的匹配容錯能力進行了量化；（3）在點故障模型下對(n,k)-星圖網路的子網路排除問題進行了研究，給出了使得(n,k)-星圖網路中不存在(n-m,k-m)-星圖子網路所需要破壞的最小點數的上下界；（4）在機率故障模型下得出了k元n方體網路中k元(n-1)方體子網路的可靠性的上下界，給出了該可靠性的一個近似值，並設計了在發生點故障的k元n方體網路中搜尋k元(n-1)方體子網路的算法。本項目的研究成果豐富了規則互連網路容錯性分析的研究方法，可以為大規模並行計算機系統互連網路的設計與最佳化提供理論參考。
