等距離間接網: MINのサーベイ

以下の項目について行なった. 1. B: (Blocking), R: (Rearrangeable), NB: (Non-Blocking), 2. 接続の方法, 3. エレメント数, 4. ルーティング (DR: Destination Routingが可能かどうか) 5. 特徴および参考文献, アルファベット順、 本文中で取り上げた網については詳しく解説していない.
名称 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].

新しい情報の提供、または間違いの訂正をお願いします。
戻る
天野英晴
Last modified: Tue Nov 26 23:05:33 1996