Abstract
多層交連網路(Multistage Interconnection Newtork,簡稱MIN)在今天被廣泛地運用在多處理機系統中用以連結處理機–處理機或處理機–記憶體模組。但不具有容錯 (Fault-Tolerant) 功能的交連網路在它某個元素出錯後會使得某些輸入端無法連接到輸出口。因此，如何設計可容錯的交連網路便成為一重要的問題。本篇論文在於探討可容錯 MIN的設計與分析。我們提出兩個建構可容錯 MIN的策略：第一、在現成的網路前後級加上多工器(Multiplexer) 與解多工器 (Demultiplexer)；第二、將數個可容錯的 MIN整合成一個更大而且可靠度也較高的可容錯 MIN。根據第一個策略我們設計出“路徑共享網路”(Path Sharing Network,簡稱PSN)，它是在一個Banyan網路的前後級加上多工器和解多工器而成。根據第二個策略，我們設計出“遞迴性路徑共享網路”(Recursive Path sharing Network,簡稱RPSN) 與“選擇遞迴性路徑共享網路”(Selectively Recursive Path Sharing Network,簡稱SRPSN)，它們是由數個 PSN整合起來的可容錯網路。我們的研究內容包括：設計出適用於新網路的路徑安排法測 (Routing Algorithm)；分析它的性能 (Performance)，在此我們分析“接收機率”(Acceptance Probabili-ty，簡稱PA) 或稱為“單位時間內之輸出率”(Throughput)；另外，我們也分析它們的可靠度 (reliability)，在此分析的項目為“平均存活時間”(Nean Time To Fai-lure，簡稱 MTTF)；對上述分析，我們也比較網路硬體所需的代價以觀察它們的效率。最後，我們以程式模擬了 PSN與另一網路 EGN的可靠度。在分析比較後，我們發現 PSN在“接收機率”上有不錯的表現，雖然它不及若干高代價之網路好，但它的低價使得它的效率(Cost-Performance Ratio)比前者重要。在可靠度方向，PSN 比EGN 好，而後者曾被分析過比另外三個可容錯網路 ESC，3-Rep 和INDRA 好。而RPSN又較 PSN有更高的可靠度，而其MTTF值並隨著遞迴深度之增加而遞增。另外，SRPSN 的表現約介於遞迴深度為二或三的RPSN之間。最後，模擬的結果顯示，PSN 與EGN 的MTTF皆比分析的悲觀值要高出甚多，亦比目前被分析最佳的容錯網路Chained network 要高出許多。