名称 |
Blockingかどうか |
接続法 |
エレメント数 |
ルーティング |
特徴および参考文献 |
ADM/IADM |
B |
Cube + 直線 |
N log2N (3×3) |
Cubeに似た方法で複数パスを得られる |
Data Manupilatorのエレメント機能を強化, 本文4.4.1. |
ASEN (Argumented Shuffle Exchange Network) |
B |
Baseline網に縦方向ループを持つ |
N/2 (log2N + 1) (3×3) |
DR可 |
縦方向ループを利用し耐故障性を持つ[156]
|
Baseline |
B |
範囲を 1/2 にしたシャッフル接続 |
N/2 log2N |
DR可 |
本文4.4.1. |
Batcher-Banyan |
NB |
Batcher網 + Banyan網 |
(N n (n-1))/4 + N/2 log2N , (N = 2n)
|
DR可 |
ソートした後にBlocking網を繋ぐことでノンブロッキングにする, 本文
4.4.3. |
Benes |
R |
Baseline + 逆Baseline |
N (log2N - 1) |
DR可 |
本文 4.4.2. |
β network |
|
U ターン能力を持った β エレメントにより結合されたMINで、
トポロジーには依存しない. |
|
|
Uターン能力を用いることで故障回避能力を持つ[165]. |
BDOC |
NB |
Batcher網+2倍サイズOmega網+2倍サイズ逆Omega網 |
(N n (n-1))/4 + 2N log2N |
DR可 |
Batcher網の後でラベルを付け変え, 2倍の大きさのOmega網と逆Omega網
を用いて, 同一宛先があってもノンブロッキングにする[115]. |
Cantor network |
NB |
3ステージでステージ間は階層シャフル |
入力: 1 × log2N, 出力: log2N × 1 ,
中間層: N/2 log2N |
ルーティングアルゴリズムはやや複雑 |
クロスポイント数が少ない[157]. |
CC-Banyan |
B |
CC-banyanはバレルシフタを含む, 広い範囲のネットワークを
指し, 作り方を示すことで結合網が定義されている.
ここでは(3, 2, 2) CC-banyanの作り方を紹介するに
とどめる. まず, 基本的なグラフ(a)を作る. このグラフは, 円錐形の
展開図上に描かれたものと考え, これを二つ重ねたグラフと三つ重ねた
グラフを用意し(b), くっつけると(3, 2, 2) CC banyanを形成することが
できる[107] |
Clos |
NB |
3ステージ |
中間ステージの構成に依存 |
簡単なルーティング法 |
3ステージで中間ステージ数を多くすると, ノンブロッキングになる, 本
文4.4.3. |
Delta |
B |
シャッフル接続 |
エレメントのサイズは柔軟 |
DR可 |
Omega網の一般化, 本文4.4.1. |
Enhanced IADM |
B |
ADMのスイッチを拡張 |
N log2N (5×5) |
|
ADMのスイッチの直線リンクを強化するとともに, 半分の距離に行くリン
クを付加し, 5×5 にして故障回避能力を強化[155]. |
ESC (Extra Stage Cube) |
B |
Gcube+冗長ステージ |
N/2 ( log2N + 1) , |
DRはできないがアルゴリズムは簡単 |
バイパスの付いた冗長ステージで故障を回避, 本文4.4.5. |
Extra stage Gamma |
B |
Gamma+冗長ステージ |
N log2(N+1) (3×3) |
DRはできないがアルゴリズムは簡単 |
剰余数を用いて冗長パスを見つける[158] |
Flip network |
B |
シャッフル接続 |
N/2 log2N |
SIMD制御 |
SIMDマシンのSTARANに用いられた.トポロジーは逆Omegaと同じだが制御
がSIMD的[162]. |
F-network |
B |
ADMのスイッチを拡張 |
N log2N (4×4) |
|
ADMのスイッチを4×4にして、冗長パスを生成[159] |
FTB/EFTB (Fault Torelant Batcher/Extended FTB) |
NB |
Batcher網+並べ変え装置+Banyan網 |
Batcher Banyan網 +α |
DR可 |
FTBはBatcher網の出力でミスソートを並べ変える. EFTBはバイパスをつ
けてリンク故障にも対応する[163],[164]. |
Gamma |
B |
Cube接続+直線 |
N log2N (3×3) |
冗長経路を求めるルーティング法がある. |
トポロジーはIADMと同じだが, スイッチの機能が高い [161]. |
Generalized Cube |
B |
Cube接続 |
N/2 log2N |
DRはできないが, アルゴリズムは簡単 |
本文4.4.1 |
INDRA |
複数の任意のMINを用いて入出力部でまとめることで耐故障性
を得る [154]. |
Merged Delta |
B |
複数のDelta網の重ね合わせ |
重ね合わせの網数に依存 |
DR可 |
冗長パス, エレメントにより故障を回避[160]. |
Multipath Omega |
B |
Omega網+冗長ステージ |
N/2( log2N + 1) |
DR可 |
Omega網のスイッチサイズを大きくして冗長パスを生成[166]. |
Omega/逆(Inverse)Omega |
B |
シャッフル接続 |
N/2 log2N |
DR可 |
最も有名なMIN,本文4.4.1 |
PBSF(Piled Banyan Switching Fabrics) |
B |
Banyan網の3次元接続 |
K(N/2) log2N (4×4) |
DR可 |
多重出力可能,本文4.4.4 |
π network |
B |
シャッフル接続 |
N log2N |
DR可 |
Omega網の縦列接続,並び変え能力が高い,本文4.4.1 |
SW-Banyan |
B |
最もポピュラーな正規Banyan |
普通は N/2 log2N |
|
Omega網など, 多くのブロッキング網を含む.本文4.4.1. |
TBSF(Tandem Banyan Switching Fabrics) |
B |
Banyan網の縦列接続 |
K(N/2) log2N |
DR可 |
多重出力可能,本文4.4.4 |
Waksman network |
R |
Benes網に近い |
N log2N -N+1 |
DR可 |
Benes網から不必要なスイッチングエレメントを取り去った構成[141]. |