超立方體網路及其變型之結果整理與性質探討

Abstract

連接網路（interconnection networks）對於平行與分散式計算（parallel and distributed computing）是很重要的，而因為超立方體網路（hypercube）的建構簡單且容易實現，所以是很常被用到的連接網路的架構。然而，已有學者專家指出 並未達到以其硬體花費來看的最佳直徑（diameter）、與平均距離（average distance），因此有不少的變型被提出，最常見的變型有：twisted cube、crossed cube、Möbius cube、及locally twisted cube，其中n表示這些網路的維度（dimension）。這些超立方體網路的變型的硬體花費與超立方體網路相同，但是直徑卻只有超立方體網路的一半。 本論文的目的有二，第一個目的是針對以上所提的四種最常見的超立方體網路的變型：twisted cube、crossed cube、Möbius cube、及locally twisted cube 的連通度（connectivity）、直徑（diameter）、訉息傳送演算法（routing algorithm）、及平均距離（average distance）做資料上的整理，以方便對這些網路架構有興趣的人參考；第二個目的是針對locally twisted cube 討論三個主題，第一個主題是hypercube與locally twisted cube 的平均距離（average distance）的比較，第二個主題是locally twisted cube的連接矩陣（adjacency matrix）的特殊建構方法，第三個主題是 locally twisted cube的點的分類。我們同時也更正了文獻中的一個錯誤。