[[alternative]]A study on fault-tolerant multistage interconnection networks with augmented links

[[abstract]]多階段連結網路(Multistage Interconnection Network)是多重處理系統連結網路研 究中之一重要領域。在多階段連結網路中各輸入埠與各輸出埠間具有唯一路徑性質， 故當錯誤發生時將無法連線通訊。為提高容錯之能力，本研究提出一種單一環及雙重 環擴增連線架構於多階段連結網路中，並使用分散式繞線規劃以設計出容錯之演算法 。在連結網路中當錯誤發生時可藉由擴增連線將訊息資料傳遞至共軛之交換開關 (Switching Element) ，再經由正常之元件(element) 將訊息資料傳送至目的輸出埠 。本研究之製作方法簡單，利用網路結構對稱之特性，且當網路中錯誤發生時並不浪 費繞線時間。在單一環擴增連線架構中區域及整體執行效率受錯誤所在位置之影響； 在各種情況下，當錯誤之發生接近目的端時，整體執行效率將產生實際的遞降。而雙 重環境擴增連結線架構可改進此項缺點，並提高執行效率。此規劃法並經分析得到所 需要之可靠度，包括終端可靠度 (Terminal Reliability) 及擴散可靠度 (Broadcast Reliability) 。由實際計算之可靠度分析資料顯示本研究規劃可大為提 高網路整體之執行效率，且和具有相同硬體複雜度之其化階段間(inter-stage) 擴增 連結線架構比較時，本規劃使用同階段內(intra-stage) 擴增連結線架構之可靠度較 之為佳，且當網路結構增大時更為顯著。