摺疊式二項式圖形

Abstract

在這篇論文裡，我們提出了一個新的多處理機網路系統:摺疊式二項式圖 形,它是由二項式圖形加上一些邊線改良而成。二項式圖形已獲證明其具 有優良之特性。除了承襲二項式圖形的卓越特性,我們介紹摺疊式二項式 圖形的最短傳輸路徑,討論其connectivity, 在兩種網路診測策略: precise strategy以及 pessimistic strategy 之下的診測能力分別優於 二項式圖形,以及摺疊式二項式圖形在k-diameter上的優越改進。 In this thesis, we propose and analyze a new large multiprocessor system, the folded binomial graph, which is basically a binomial graph with some extra edges established between its vertices. It has been shown that binomial graphs have very good properties. We describe the shortest routing strategy and show the connectivity of a folded binomial. We also study two diagnosis strategies: the precise strategy and the pessimistic strategy, and prove that under these two strategies the diagnosabilities of a folded binomial graph enhance excellent improvement.