|
布林n 方格網路(Boolean n-cube network)已被充份研究與廣泛應用，它具有簡單及
無死鎖傳送(deadlock-free routing and broadcast) 演算法之優點。然而，由於構
成此種網路之點數必須為2 之次方，使得用此網路所組成的系統其點數之間存在極大
的間隙(gap) 。同時，布林n 方格網路之高點分支度(high degree of node) 亦使其
系統成本增加。本文提出一種推廣型布林n方格網路(generalized Blloean n-cube n
etwork,簡稱GBN) 以改善上述兩個問題。
本文主要之結果共有四部份：
一、我們探討了一些GBN 網路之圖形理論特性，並且證明其具有超線連接度(super l
ine-connectivity)之性質，進而推得它是一種最可靠之網路結構。其可靠度(rdliab
ility)可由線分離集之數目(number of line disconnecting sets) 得到一近似值。
二、我們推導出一簡單的公式來表示GBN 之涵遍樹數目(number of spanning trees)
。由此亦可得到此網路可靠度之近似值。
三、我們探討了GBN 之容錯能力及偵錯性(diagnosability)，並且提出兩個偵錯(fau
lt-diagnosis) 演算法。
四、在GBN 人我們建立一個平行排列(parallel permutation)演算法，此GBN 使用
m n-1
２ ‧Ｎ個處理單元(processing elements) 來排列Ｎ＝ｒ 項資料，所需之時間
複雜度(time complexity) 為O((n/m)(r+n))．
|