層次網路的嵌入限制連通性及子網排除問題研究

《層次網路的嵌入限制連通性及子網排除問題研究》是依託河南師範大學，由楊玉星擔任項目負責人的聯合基金項目。

基本介紹

• 中文名：層次網路的嵌入限制連通性及子網排除問題研究
• 項目類別：聯合基金項目
• 項目負責人：楊玉星
• 依託單位：河南師範大學

項目摘要

海量數據的處理和複雜問題的解決對並行計算機系統性能的要求愈來愈高；並行計算機系統的性能主要取決於其互連網路的性質。針對目前度量網路連通性的參數均未考慮“子網嵌入”的問題，結合層次網路中對子網嵌入的實際需求，課題提出層次網路中兩個新的連通性度量參數，即嵌入限制連通度和嵌入限制邊連通度；擬研究嵌入限制（邊）連通度和其它連通性度量參數之間的關係；設計層次網路中嵌入限制點割和嵌入限制邊割的求解算法；計算層次網路的嵌入限制（邊）連通度。為了更好地度量層次網路的容錯能力，課題擬研究層次網路的“子網排除”問題，設計求解層次網路的“子網排除點割”和“子網排除邊割”的有效算法，據此計算層次網路的子網排除數，並探究層次網路的嵌入限制連通性和子網排除問題之間的關係，為並行計算機系統的互連網路的設計和選擇提供理論依據。

結題摘要

並行計算系統通常以某個正則的層次圖作為互連網路而搭建，互連網路的性質對相應系統的性能起著重要的、甚至是決定性的作用。網路中的節點或直連線路難免發生故障，網路的容錯能力是設計或選擇互連網路的重要因素。連通性和子網保持能力是容錯能力的重要方面。針對以往的連通性度量參數均未考慮“子網嵌入”需求的問題，課題研究了層次網路的嵌入限制連通性問題；對於通用的層次網路，給出了嵌入限制連通性參數和傳統的連通性參數以及以往的條件連通性參數之間的關係；對於一些經典的層次網路，確定了某些情形下的嵌入限制連通度和嵌入限制邊連通度。針對“子網排除”問題中子網排除節點割和子網排除邊割難以確定的難點，使用二次降維的方法確定了bubble-sort網路、bubble-sort star網路和(n, m)-bubble-sort網路的某些子網排除割，並據此計算了攻擊這些網路中某些子網的最小代價。同時，課題研究了k元n立方網路、多維環面網路等著名網路中的容錯嵌入和指定嵌入問題，提出或最佳化了這些網路中路或圈的嵌入方案。此外，針對bubble-sort網路的連通性不夠優越的問題，設計了連通性更強的增廣bubble-sort網路。為並行計算機系統搭建時設計或選擇底層互連網路提供了理論支撐。