掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
互連網絡的連通性和診斷度 版權信息
- ISBN：9787030693341
- 條形碼：9787030693341 ; 978-7-03-069334-1
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
互連網絡的連通性和診斷度 內容簡介
本書對于互連網絡的連通性和診斷度問題提供了一個統一的理論框架。內容包括：對網絡診斷的概述；給出網絡的高階好鄰診斷度和高階診斷度的一些充分條件；確定了一些有名網絡的高階連通度、自然診斷度、高階好鄰診斷度和高階診斷度。本書許多內容和方法是作者的研究成果，書中還提出一些問題供有興趣的讀者進一步研究。本書可作為高等院校計算機、應用數學和網絡通信專業研究生以及相關領域研究人員的參考書。
互連網絡的連通性和診斷度 目錄
目錄
前言
主要符號表
第1章 緒論 1
1.1 研究背景和意義 1
1.2 互連網絡的概述及容錯 3
1.2.1 設計規則及方法 3
1.2.2 常見的類型 4
1.2.3 容錯概述 5
1.3 故障診斷概述 5
第2章 基礎知識 8
2.1 圖的基本定義及符號 8
2.2 連通度及相關定義 9
2.3 故障診斷模型 11
2.3.1 PMC模型 11
2.3.2 MM模型 12
第3章 網絡可診斷的充要條件 15
第4章 網絡的連通度和自然診斷度 23
4.1 擴展k元n立方體的連通度和自然診斷度 23
4.1.1 預備知識 23
4.1.2 擴展k元n立方體的連通度 28
4.1.3 擴展k元n立方體在PMC模型下的自然診斷度 40
4.1.4 擴展k元n立方體在MM*模型下的自然診斷度 41
4.2 巢圖的連通度和自然診斷度 44
4.2.1 預備知識 44
4.2.2 巢圖的連通度 46
4.2.3 巢圖在PMC模型下的自然診斷度 54
4.2.4 巢圖在MM*模型下的自然診斷度 56
4.3 泡型星圖的連通度和自然診斷度 58
4.3.1 預備知識 58
4.3.2 泡型星圖的連通度 60
4.3.3 泡型星圖在PMC模型下的自然診斷度 60
4.3.4 泡型星圖在MM*模型下的自然診斷度 61
4.4 輪圖的連通度和自然診斷度 65
4.4.1 預備知識 65
4.4.2 輪圖的自然連通度 67
4.4.3 輪圖在PMC模型下的自然診斷度 72
4.4.4 輪圖在MM*模型下的自然診斷度 73
4.5 對換樹生成的凱萊圖的自然診斷度 75
4.5.1 對換樹生成的凱萊圖的連通性 75
4.5.2 對換樹生成的凱萊圖在PMC模型下的自然診斷度 80
4.5.3 對換樹生成的凱萊圖在MM*模型下的自然診斷度 81
4.6 一些說明 84
第5章 網絡的高階好鄰診斷度 85
5.1 超立方體的g好鄰診斷度 85
5.2 局部扭立方的g好鄰診斷度 89
5.2.1 預備知識 89
5.2.2 局部扭立方在PMC模型下的g好鄰診斷度 90
5.2.3 局部扭立方在MM*模型下的g好鄰診斷度 92
5.3 泡型圖的g好鄰診斷度 95
5.3.1 預備知識 95
5.3.2 泡型圖在PMC模型下的g好鄰診斷度 97
5.3.3 泡型圖在MM*模型下的g好鄰診斷度 104
5.3.4 本節小結 110
5.4 星圖的g好鄰診斷度 111
5.4.1 預備知識 111
5.4.2 星圖在PMC模型下的g好鄰診斷度 113
5.4.3 星圖在MM*模型下的g好鄰診斷度 116
5.4.4 本節小結 121
5.5 一些說明 121
第6章 網絡的高階限制連通度 122
6.1 超彼得森圖的g限制連通度 122
6.2 局部扭立方的g限制連通度 131
6.3 交叉立方的g限制連通度 133
6.4 交錯群圖的緊超3限制連通度 137
6.5 一些說明 162
參考文獻 163
前言
主要符號表
第1章 緒論 1
1.1 研究背景和意義 1
1.2 互連網絡的概述及容錯 3
1.2.1 設計規則及方法 3
1.2.2 常見的類型 4
1.2.3 容錯概述 5
1.3 故障診斷概述 5
第2章 基礎知識 8
2.1 圖的基本定義及符號 8
2.2 連通度及相關定義 9
2.3 故障診斷模型 11
2.3.1 PMC模型 11
2.3.2 MM模型 12
第3章 網絡可診斷的充要條件 15
第4章 網絡的連通度和自然診斷度 23
4.1 擴展k元n立方體的連通度和自然診斷度 23
4.1.1 預備知識 23
4.1.2 擴展k元n立方體的連通度 28
4.1.3 擴展k元n立方體在PMC模型下的自然診斷度 40
4.1.4 擴展k元n立方體在MM*模型下的自然診斷度 41
4.2 巢圖的連通度和自然診斷度 44
4.2.1 預備知識 44
4.2.2 巢圖的連通度 46
4.2.3 巢圖在PMC模型下的自然診斷度 54
4.2.4 巢圖在MM*模型下的自然診斷度 56
4.3 泡型星圖的連通度和自然診斷度 58
4.3.1 預備知識 58
4.3.2 泡型星圖的連通度 60
4.3.3 泡型星圖在PMC模型下的自然診斷度 60
4.3.4 泡型星圖在MM*模型下的自然診斷度 61
4.4 輪圖的連通度和自然診斷度 65
4.4.1 預備知識 65
4.4.2 輪圖的自然連通度 67
4.4.3 輪圖在PMC模型下的自然診斷度 72
4.4.4 輪圖在MM*模型下的自然診斷度 73
4.5 對換樹生成的凱萊圖的自然診斷度 75
4.5.1 對換樹生成的凱萊圖的連通性 75
4.5.2 對換樹生成的凱萊圖在PMC模型下的自然診斷度 80
4.5.3 對換樹生成的凱萊圖在MM*模型下的自然診斷度 81
4.6 一些說明 84
第5章 網絡的高階好鄰診斷度 85
5.1 超立方體的g好鄰診斷度 85
5.2 局部扭立方的g好鄰診斷度 89
5.2.1 預備知識 89
5.2.2 局部扭立方在PMC模型下的g好鄰診斷度 90
5.2.3 局部扭立方在MM*模型下的g好鄰診斷度 92
5.3 泡型圖的g好鄰診斷度 95
5.3.1 預備知識 95
5.3.2 泡型圖在PMC模型下的g好鄰診斷度 97
5.3.3 泡型圖在MM*模型下的g好鄰診斷度 104
5.3.4 本節小結 110
5.4 星圖的g好鄰診斷度 111
5.4.1 預備知識 111
5.4.2 星圖在PMC模型下的g好鄰診斷度 113
5.4.3 星圖在MM*模型下的g好鄰診斷度 116
5.4.4 本節小結 121
5.5 一些說明 121
第6章 網絡的高階限制連通度 122
6.1 超彼得森圖的g限制連通度 122
6.2 局部扭立方的g限制連通度 131
6.3 交叉立方的g限制連通度 133
6.4 交錯群圖的緊超3限制連通度 137
6.5 一些說明 162
參考文獻 163
展開全部
互連網絡的連通性和診斷度 節選
第1章 緒論 1.1 研究背景和意義 高性能計算(high performance computing， HPC)作為計算機科學的一個分支，主要是指從軟件開發、并行算法和體系結構等方面研究開發高性能計算系統的技術.經歷了百年的發展，它與實驗科學、理論科學一起成為推動社會和科技發展的動力，已被視為當今**生產力和第三大科學方法.通常它和并行計算、超級計算同義.作為信息領域的前沿高技術，高性能計算已然成為衡量一個國家的綜合國力和科技發展水平的重要標志.在一些新興的學科，如核研究、生物技術、航空航天及新材料技術等，高性能計算已成為科學研究的**工具之一.另外，隨著高性能計算性能的提高、成本的降低，高性能計算也逐漸開始走向更廣泛的行業應用，如石油勘探、機械設計、天氣和災害預報、生物制藥、金融分析、決策支持系統等大數據處理方面以及政府機構、教育、搜索引擎、信息中心等網格計算和協同工作等.它在各領域的應用發揮了巨大的應用價值.這不僅節約了研發成本，還減少了大量時間消耗，提高了研發進度和效率.高性能計算已然成為科學研究和科技創新的主要工具，能夠取得只依靠理論研究和實驗方法而得不到的科學發現和技術創新. TOP500排行榜通常被認為是世界上評估高性能計算發展現狀的指標.在國家對高性能計算的大力支持下，我國的高性能計算技術呈現快速發展的良好勢頭.2017年，中國擁有的超高性能計算機數量居全球首位，并且仍在保持.在2019年國內高性能計算機 TOP100排行榜中，無錫國家超級計算中心的神威 太湖之光蟬聯**，其每秒峰值速度達9.3億億次[1].同時，它也是世界TOP500超級計算機中的第三名，此前曾蟬聯過四次 TOP500冠軍.在國內，六個國家超級計算中心(無錫中心、天津中心、濟南中心、深圳中心、長沙中心、廣州中心)及一些地方、高校、科研院所的高性能計算中心紛紛建成并投入使用.如今，它們已經成為我國科學研究、信息處理、技術開發和大數據處理的關鍵計算平臺并在滲入社會各領域中發揮著巨大的作用. 隨著高性能計算的應用領域和規模進一步拓寬增大，各領域對高性能計算的依賴程度越來越高.進而，一些關系到國計民生安全等重要領域都對高性能計算的可靠性提出了特殊要求.如果系統不能穩定可靠地工作，那么將會造成巨大的損失，甚至導致不可估計的災難性后果.例如:12306火車售票網絡、天氣預報系統、機械設計系統、金融分析系統、銀行出納系統、航空航天的設計系統、衛星發射太空計劃等.若運行它們的系統出現故障，其造成的損失與產生的后果是非常巨大和可怕的.由此可見，系統發生故障是客觀的和不可避免的，絕對無故障的系統是不存在的.但是人們期望系統在部分處理器或鏈路發生故障時，仍然可以正；蚧菊５毓ぷ鞑恢劣诋a生嚴重的后果.故而，在設計高性能計算系統時，除了高速度和高性能外，高可靠性應放在設計的首位. 由于處理器制造工藝和時鐘頻率等關鍵技術的進步變慢，處理器的性能和頻率等性能提升幅度也越來越小且摩爾定律也漸近極限.因此，大規模多處理器互連組網是提升高性能計算能力的發展趨勢之一.當前主流的高性能計算系統多是采用 Cluster(集群)和MMP (大規模并行處理)，將多個處理器按專門的互連網絡組織在一起實現節點間的通信.特別是在超大規模集成技術的驅動下，系統可以集成成千上萬個處理器，它們之間依靠互連網絡實現通信.系統中處理器規模的擴大勢必造成它們之間通信開銷的增大，成為制約系統總體性能的主要因素.研究表明高性能計算不僅依賴于處理器的浮點運算速度(理論峰值)，還依賴于數據在系統中的存取和傳輸速度等[1].故而，高性能計算系統的性能取決于其互連網絡性能. 隨著系統中處理器數量不斷擴大，系統內部的結構也越來越復雜.這使得處理器出現故障的概率也隨之增加，從而導致系統在信息處理、存儲及傳遞過程中出現錯誤的可能性增大.在高性能計算系統中處理器發生故障的概率占整個系統組件故障概率的50%以上[2].為了保證系統的可靠性，系統就必須要有一定的容錯性.Esfahanian稱系統為容錯的[3]，如果在超大規模多處理器系統發生故障時仍具備功能.系統的容錯性研究成為系統可靠性的研究熱點. 同時，為了保證系統的可靠性，系統在發生故障時要能夠及時識別出故障處理器并用非故障處理器來替換.系統的故障診斷是目前能夠保證系統可靠性的一類有效的診斷方式，它的目標是按照一定的規則識別出系統中的故障處理器.系統是t可診斷的，如果系統中故障處理器數目不超過t且不經替換可一次識別出來.系統的故障診斷研究成為系統可靠性的另一研究熱點. 系統互連網絡的可靠性研究通常也稱網絡的容錯性研究.因此，互連網絡的容錯性成為評價系統可靠性的關鍵指標之一.注意到互連網絡的拓撲結構可以用一個圖來刻畫，其點集和邊集分別由節點和節點間連線構成.進而，互連網絡的容錯性研究也就轉化成對圖的容錯性研究.連通度和診斷度通常被用來衡量互連網絡的可靠性和故障診斷能力.經過國內外學者多年的研究，采用圖論的方法研究互連網絡的容錯性已經取得了豐碩的成果，并取得了一系列有價值的研究成果，尤其是在診斷度方面，許多類型互連網絡的診斷度得到了研究證明. 由于本書的主要工作集中在對互連網絡系統可靠性和故障診斷的研究，研究的思路:一是分析并選取具有高容錯性的互連網絡，以保證系統發生一定的故障而性能不降低;二是給定互連網絡研究它的故障診斷度，以便發生故障后能夠及時診斷出從而保證系統的可靠性. 1.2 互連網絡的概述及容錯 互連網絡(interconnection network)通常是若干處理器按照一定的拓撲結構，通過元器件以一定的控制方式實現處理器間相互連接和數據傳輸的網絡.在一個互連網絡中，每個處理器有本地內存和資源，通過通信鏈路與其相鄰處理器連接.其對于保證各處理器無等待計算起著極為重要的作用.從某種意義上說，高性能計算系統性能的關鍵取決于該系統各處理器間數據傳輸的能力而不是處理器的性能.因此，互連網絡是高性能計算系統性能的重要組成部分，它對系統的運行有著極大的影響[4].而互連網絡的可靠性是衡量一個互連網絡性能優劣的重要參數.如何選擇或設計一個可靠的互連網絡拓撲結構，已成為學者們研究的熱點. 1.2.1 設計規則及方法 高性能計算系統的互連網絡設計通常要遵循兩大基本原則，即高性能和低成本.但其性能和成本受眾多因素影響，在實際設計時，二者也通常需要找到一個平衡點.單從其拓撲結構上來說應遵循以下基本原則[5，6]: (1)固定或小的度.受限于處理器單元的端口數目，節點的度應該較小或固定.同時，較小的節點度意味著布線簡單，從而使得成本降低. (2)高對稱性.節點以相同的連接方式接入網絡，使得網絡中各元器件負載保持平衡. (3)低延遲性.互連網絡的直徑應較短且平均距離也應較小.這不僅會使得節點間通信延遲減小，也能降低建造和維護費用，同時提高互連網絡的有效性. (4)簡易的路由算法.互連網絡的通信開銷增大，使得通信必須要經過路由選擇.路由算法的優劣決定著互連網絡的效率和性能. (5)高容錯性.互連網絡中任意兩點之間存在多條內點不交的路徑.一旦某些元器件發生故障，系統可以有多種路由選擇從而保證正常的通信及運行. (6)可擴展性.在原有基礎上擴大網絡規模，同時保持原有互連網絡的性質不變.可擴展性有利于系統的升級擴大，是衡量網絡好壞的一個重要因素. (7)可嵌入性.新的互連網絡應能包含已有的簡單網絡.這樣有利于移植和嵌入針對簡單網絡的結構和性質以及相關的算法，進而降低開發的軟成本. (8)有效的布圖算法.它能夠解決大規模集成電路板線路的交叉問題，使得互連網絡能在多個或一個平面圖內簡易實現. 為了設計出高性能低成本的互連網絡，常用的拓撲結構設計方法有線圖法、笛卡爾乘積法和凱萊法這三種[7]. (1)線圖法是從一個現有的圖獲得另一個與之相關圖的重要構圖方法，也是互連網絡設計的一個重要方法.其思想實際上就是點邊互換.De Bruijn圖和Kautz圖是兩大類著名的線圖.它們被認為是未來實現并行計算替代超立方體的一類互連網絡. (2)笛卡爾乘積法是從若干特定的小網絡構造大網絡的*有效的方法之一.由這種方法構造出來的新網絡不僅包含了其原有的小網絡作為它的子網絡，也保留了小網絡原有的性質.因而，它也成為大規；ミB網絡設計的一個重要的方法.超立方體就是通過該方法構造得到的一類著名的網絡.超立方體作為高性能計算系統互連網絡的首選拓撲結構，具有正則性、對稱性、點可遷性及遞歸性等許多優良的網絡特性，然而它的直徑卻較大.為了彌補它的不足，通過對超立方體進行不同的變型又派生出了許多的變型互連網絡. (3)凱萊法是構造高對稱性網絡的一種設計方法.由于該方法基于有限群，也因此稱其為群論法或代數法.由該方法構造的圖稱為凱萊圖且都是點可遷的.故而該類型的網絡中任何一個節點對于網絡都是等同的，即使某個節點出現故障也不影響其余網絡的結構性能.因此，該方法構造的網絡非常有利于算法的設計和模擬.凱萊圖有很多，如泡型圖、星圖和交錯群圖等.因為凱萊圖都具有高對稱性，所以它們也被認為是下一代高性能計算互連網絡替代超立方體的選項. 1.2.2 常見的類型 按拓撲結構的不同，互連網絡可以分為靜態和動態互連網絡.在動態互連網絡中，節點間通過交換元件的設置建立不同的網絡連接.這種連接方式是按需建立的，也被稱為間接互連網絡.然而隨著網絡節點數目的增多，交換開關反而會成為系統的通信瓶頸.在靜態互連網絡中，節點間有固定的直接連線，也被稱為直接互連網絡.因此，常采用圖論模型來描述互連網絡的性能并用圖的某些參數來衡量.在多處理器系統中，互連網絡的拓撲結構可以用圖來表示，其中頂點表示處理器(節點)，邊表示處理器間的通信鏈路(節點間的連線). 在互連網絡研究初始階段，常見的互連網絡拓撲結構有線陣網(linear array)、總線(bus)、環網(torus)、樹網(tree)、星型網(star)、網格(mesh)、立方連接環(CCC)、全互連網等.全互連網(完全圖)雖是具有*高效率的網絡拓撲結構，但建設成本也受元器件引腳的限制.而隨著系統規模的變大，系統對互連網絡的要求也越來越高.許多學者對互連網絡的拓撲結構展開了研究，各種高性能互連網絡也相繼被提出.于是，超立方體(hypercube)[8]、交叉立方體(crossed cube)[9]、默比烏斯立方體(M¨obius cube)[10]、平衡立方體(balanced hypercube)[11]、折疊立方體(folded cube)[12]、扭立方體(twisted cube)[13]、局部扭立方體(locally twisted cube)[14]、交換超立方體(exchanged hypercube)[15]、交換交叉立方體(exchanged crossed cube)[16]、k元n立方體(k-ary n-cube)[17]及擴展k元n立方體(augmented k-ary n-cube)[18]等互連網絡的圖形相繼被提出來研究.每一種網絡設計都適合于特定的應用環境.其中一些已應用到實際的計算機系統中，如超立方體應用在 NCube[19]、Intel iPSC/2[20]、IPSC-860、CM-2[21]等高性能計算機系統；k元n立方體應用在 iWarp[22]、J-machine[23]、Cray T3D[24]、Cray T3E[25]、IBM Blue Gene[26]等高性能計算機系統. 1.2.3 容錯概述 互連網絡拓撲性能可以用圖的一些參數和性質來描述和度量.互連網絡的可靠性也稱為容錯性.容錯性是衡量互連網絡性能的重要指標，對應于圖來說也就是圖要有較大的連通度.連通度越大，網
書友推薦
- >
名家帶你讀魯迅:故事新編
- >
我從未如此眷戀人間
- >
巴金－再思錄
- >
史學評論
- >
中國人在烏蘇里邊疆區:歷史與人類學概述
- >
朝聞道
- >
煙與鏡
- >
人文閱讀與收藏·良友文學叢書:一天的工作
本類暢銷
