| 名称 | 結合法 | 次数 | 直径 | 特徴および参考文献 |
|---|---|---|---|---|
| base-m n-cube/ハイパクロスバ/Hypermesh | 不等距離間接網に属する. Prodigy, R256, CP-PACSに利用. 本文5.4.2参照 | |||
| CCC(Cube Connected Cycle) | Hypercubeのノードをリングで置き換えた結合法 | 3 | サイクル数をn, サイクルのメンバ数をlとすると 2log2 n + l/2 | 本文5.3.4. |
| CCTCube | Complete Connection of Torus hyperCube, サブネットのハイパーキュー ブにバイパスリンクを加え,直径を減らすとともに, 階層を上げるたびに拡張 用のリンクを加える. | Hypercubeより小さい | Hypercubeより小さい | 本文5.3.4. |
| Chordal Ring | 全ノード(偶数に限る)をリング状に結び,3本目の線を a)奇数番目のノードiに対し,(i+w) mod Nノードへ, b)偶数番目のノードiに対し,(i-w) mod Nノードへ それぞれリンクを接続する. | 3 | N1/2 | 付加リングの代表[219] |
| Circular Omega | MINのOmega網を輪にして,各スイッチの所にプロセッシングノードも付け た結合方式. | 次数は4(2入力,2出力) | N=n× log2nとすると,2n. | 本文5.3.2. |
| Cubemat | メッシュ上に縦横にバスを付けるとともに,スイッチを付加する. | 様々なアルゴリズムが考案されている[218]. | ||
| Crossed Cube | 全体が対称になるように,ハイパーキューブのリンクを入れ換える. | log2 N | log2 Nより減る. | 本文5.3.5. |
| dBCube | Hypercubeでクラスタを作って,それをDe Bruijn結合する. dBC(c,d)は,c個のd次元cubeのDe Bruijn接続からなる結合網. 図はc=8, d=2のdBCUBEを示す. | d+1 | d(1+logr c) | VLSI上のレイアウトについて詳しく検討されている[221] |
| De Bruijn | 各ノードにr進数D桁で番号を振る. この数を1桁左にシフトして,空いた 所に任意の数を入れ,でき上がった数をノード番号に持つノードとの間をリン クで結ぶ. | 2r | logr | 本文5.3.1. |
| Enhanced Hypercube | ハイパーキューブがサイズにより, 余ったリンクを持っている場合,この リンクを繋いで交信を緩和する. | log2 N | 場合によっては log 2Nより減る. | 本文5.3.5. |
| Express Cube | k-ary n-cubeに対してスイッチを介した飛び越しパスを付加する. | 飛び越しパスをねじることによって, 性能が上がる場合がある[222]. | ||
| Express Torus | トーラスを折り畳むことで, 長いラップアラウンドパスをなくすととも に,スイッチを配置して再構成可能にする. | スイッチの構成に現実的な検討が行なわれている[186] | ||
| Extended Hypercubes | Hypercubeを8進ツリー状にピラミッド状に階層化した構造を持つ. | 11 | Hypercubeより小さい | 本文5.3.5 |
| Fat Tree | 不等距離間接網に属する.CM-5に利用.本文5.4.1参照. | |||
| Fibonacci Cube | Fibonacci数列に基づきΓnとΓn-1の同じ構造 の対応するノード同士を結合し,Γn+1を形成する. この結合網は 非対称形で,ノード0が最大のリンクを持つ. | Fibonacci数列の次数をnとすると,通常degreeはn-2となる. | n-2 | 不平衡木(フィボナッチツリー)を内蔵し, 通信遅延まで含んで考えるアル ゴリズムを最適に実装することができる[223] |
| フィボネット | Fibonacci数列に基づくが, a) Fibonacci Cubeが非対称であるのに対し て,対称性を保持する. b)任意のノード数で構成可. という特徴を持つ.このた めにリング構造を導入し, 各ノードは,正,負の両方向に f2i つま り偶数番目のfibonacci数分離れたノードとの間をリンクで結ぶ.つまり,± 3 と± 8離れたノード間をリンクで結ぶ(奇数の場合もう少し複雑である). | Fibonnacci Cubeと同程度 | Hypercubeより大 | Fibonacci cube同様, 不平衡木を内蔵[224] |
| Folded Hypercube | ハイパーキューブに拡張用のリンクをつけ,直径方向に折り畳む. | log2 N+1 | log2 N/2 | 本文5.3.5. |
| Hierachical Hypercube | Hypercubeを階層化し, CCC状に接続. | 完全形はサブハイパーキューブの次元m+1 | Hypecubeよりやや悪いがCCCより良い. | Divide and Conquerタイプの問題のアルゴリズムが検討されている[225]. |
| ハイパクロス | 不等距離間接網に属する.ADENARTに利用.本文5.4.2.参照. | |||
| Hyper Debruijn | Hyper Debruijn HD(x,y)はx,次元のHypercubeとy次元のDebruijnの外積 グラフとして定義される.下の図に示すのは,HDB(2,2)をHypercubeの方の番号 (x)が同じものが近くにくるように配置した図で,2次元のDebruijn網が2次元の Hypercube状に接続されている. | Debruijn網形成用の4本にx次元のHypercubeを作るためのx本が加わり 4+x. | HD(x,y)の直径は,x+y. | Hypercube構成のリンクを利用することによって,メッシュのエミュレー ションが可能になる[226] |
| Hypernet | 任意の結合でビルディングブロックを作り,ブロック同士を完全結合に より多階層に結合する. | Hypercubeをサブネットとして選んだ場合,次数は5か6 | Hypercubeよりやや大きい. | 本文5.3.4 |
| Kautz | 各ノードをr+1進D桁の番号で表わすが, この場合,同じ数字が続いては ならず,規則に反する番号は使われない. このため,自己ループができない. | 2r | logr | 本文5.3.1. |
| 格子らせんネットワーク | トーラスに斜め方向のリンクを2本付加する. | 6 | ハイパーキューブより小 | リンクが少ない割に直径がさほど大きくならない[233] |
| Lens Network | 共有バス接続網に属する.図に示す構造を再帰的に結合する. MINのOmega網と等価になる[232] | |||
| MDCE/CCCB/(CB)n | Multidimensional Directed Cycles Ensemble,MINのGeneralized Cube 網のエレメントをノードとし,循環ループを付けた構造を多元化した網. | 3次元では6 | サイクル2周分 | 超並列マシンRWC-1に利用. 本文5.3.2. |
| MDX | Multidimensional X'bar,不等距離間接網のクラスで base-m n-cube,ハイパクロス,MDX-De Bruijn, MDX-Baselineなどを含む.本文 5.4.2. | |||
| MGM (Mesh with Global Mesh) | メッシュ上に上位メッシュを階層的に構成していく. | 再帰構造を利用して漸化式計算を効率良く行なう[227]. | ||
| Midimew | Midimew(Minimum Distance Mesh with Wrap-around links)は,トーラス の横方向の端を螺旋状に結合した構造. | 4 | トーラスより小 | 本文5.3.6. |
| n-RTN | Recursive Torus Network, RDT同様上位トーラスを持つが,対角方向では なく2×4の長方形状をしている. | 8 | ハイパーキューブより小 | 階層転送アルゴリズムの実装がRDTより楽[229]. |
| Polymorphic Torus | トーラスの格子点ノードをバイパスすることのできるスイッチを利用す る. | SIMD用のアルゴリズムが開発されている.[184]. | ||
| Pradhan | ノード番号をr進数で表わし, 左方向に1回ローテイトした番号との間に リンクを作る. 次に,左シフトして空いた桁に,隣と違う数字を入れて作った基 本形にリンクを付加する. | 2r+1 | logr | 本文5.3.1. |
| Recursive Circulant | リングで結んで1次元番号を振ったノード(総数N=2m)間に, ± 4 \lceil m/2 \rceil -1だけ離れたノード間をリンクで結んで できたグラフがDN(m). | m | \lceil (3m-1)/4 \rceil | Circulant Graphの1つ[220] |
| RDT/Diagonal Mesh | Recursive Diagonal Torus, 2次元トーラスのあるノード(x,y)に対して, ± 2離れたノードに付加リンクを加え,45度傾いた目の粗い上位トーラスを構 成する. この上位トーラス上に, 同様のアルゴリズムで次々に上位トーラスを 構成する. | 8 | ハイパーキューブより小 | 超並列マシンJUMP-1に利用,本文5.3.6. |
| RTA(再帰トーラス) | トーラスを分割して折り返し点にスイッチを挿入し, これによってトー ラスのサイズを変更する. | 画像処理用にアルゴリズムが開発されている[185]. | ||
| RTM | Ring Tree on Mesh, メッシュまたはトーラスにより結合されたノード 間を, 大きさの異なる複数のリングにより階層的に結合. | 8 (DTRM) | 単方向リングなので光結合向き[230]. | |
| Star Graph | 重ならないn個の記号の並びで表されれたノードについてあるノードは, 先頭の記号を他の任意の記号といれかえた識別子を持つノードとの間にリンク をつける.リンクはない.いれかえる対象はあくまで先頭の記号である. | n-1 (ノード数n!について) | 直径は3(n-1)/2(切り上げ) | 本文5.3.3. |
| Snow Flake/Dens Snow Flake | 共有バス接続網に属する.図に示す構造を再帰的に結合する. 中央がボトルネックになるため,二重化したのがDens Snow Flake[231] | |||
| SNT | Symmetrical Network Topology, 2次元格子に飛び越しリンクを設けた 構造を持つ.リンクを設ける角度と,飛び越しリンクの数により,SNT-U, SNT-V, SNT-W, SNT-X SNT-XX等の結合網が得られる. | 6〜8 | ハイパーキューブより小 | 本文5.3.6. |
| SRT(Shifted Recursive Torus) | 1次元SRTはリングにバイパスリンクを付加する構成で,2次元,3次元SRTは これを2次元,3次元状にシフトしながら並べた構造を持つ. | 2次元は8 | ハイパーキューブより小 | 結合方式はやや複雑[228]. |
| Twisted Hypercube | Hypercubeのリンクを一部を入れ換え（捻って）直径を減らす. | log2 N | log2 Nより減る. | 本文5.3.5. |
| X-tree | Tree構造の同一レベルのノードに対し, バイパスを付加する. | 4 | 古くから提案されている網で, アルゴリズムやLSI実装法が検討されてい る[234]. | |