標題: 高效能及高可靠度之多階連結網路之資料結合架構
A Cost-effective Fault-tolerant Combining Structure for Multistage interconnection network
作者: 林建州
Chien-Chou Lin
莊仁輝
Jen-Hui Chuang
資訊科學與工程研究所
關鍵字: 多階網路;熱點流量衝突;容錯樹;資料結合網路;multistage network;hot spot contention;fault-tolerant tree
公開日期: 1993
摘要: 在多處理器系統內連網路中,多階連結網路是一高頻寬且經濟的方法,但 是,由於在單純的多階連結網路中每一處理器和每一記憶體模組之間僅存 在一條路徑而且網路中的每一鍊節均為多條路徑所共用,因而造成了熱點 流量衝突和容錯問題,而大大地影響多階連結網路的效能.以二元樹架構來 做資料結合以解決熱點流量衝突是一有效且經濟的方法,但其容錯性卻是 很差.在本論文中,我們提出了一整合性的設計以解決上述兩問題.我們所 提出的設計包含兩部份:(1)可容錯的資料傳送網路(加鍊多階網路)及新提 出的(2)可容錯且經濟之資料結合網路(跳階樹網路).新的設計可使原有以 二元樹為基礎的資料結合網路之可靠度提高達五倍左右,其平均記憶體存 取時間也快於加鍊多階連結網路. For a shared-memory multiprocessor system, the multistage inter- connection network ( MIN )is a high-bandwidth and cost- effective choice among the various interconnection schemes. However , the pure MIN has two properties : (i) There is only a single path between any PP-MM (processing element and memory module ) pair. ( ii ) A link is always shared by multiple PE-MM paths . The problems of the fault-tolerance and the hot-spot contention caused by the above two properties may seriously degrade the system performance.A binary tree based combining network for MIN was proposed to solvethe hot spot contention.This cost-effective scheme can solve hot spot contention efficiently, but the binary tree sturcture has a poor fault-tloerant capability . In this thesis a modified fault-tolerant binary tree called Jump Tree is proposed. The reliability of the tree structure is enhanced by adding some redundant links and multiplexers. Furthermore , we propose an integrated MIN design which has a fault-tolerant MIN (chained network ) and a fault-tolerant and cost-effective combining network (Jump Tree).The chained network can handle the nonuniform traffic spots for the regular routing the Jump Tree can combine the hot-spot packets efficiently and reliably. The Jump Tree based combining MIN has a five time increases in the reliabilty compared with that based on a binary tree. The average delay of our design is also shorter than the chained combining network's.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT820394022
http://hdl.handle.net/11536/57919
Appears in Collections:Thesis