多段相互接続ネットワーク

多段相互接続ネットワーク( MIN ) は、高速コンピュータ ネットワークの一種で、通常、ネットワークの一方の端にある処理要素 (PE) と、もう一方の端にあるメモリ要素 (ME) で構成され、スイッチング要素 (SE)によって接続されています。スイッチング要素自体は通常、段階的に相互に接続されているため、この名前が付けられています。

MIN は、通常、高性能コンピューティングまたは並列コンピューティングで低遅延の相互接続として使用されます (従来のパケット交換ネットワークとは対照的)。ただし、パケット交換ネットワーク上に実装することもできます。ネットワークは通常、ルーティングの目的で使用されますが、ソート、完全シャッフルネットワークでの巡回シフト、およびビットニック ソートなどの用途で、実際のプロセッサのコプロセッサとして使用することもできます。

相互接続ネットワークは、ノード（単一のプロセッサまたはプロセッサのグループ）を他のノードに接続するために使用されます。

相互接続ネットワークは、トポロジに基づいて分類できます。トポロジとは、1 つのノードが他のノードに接続されるパターンです。

トポロジには、静的と動的の 2 つの主なタイプがあります。

静的相互接続ネットワークはハードワイヤードであり、構成を変更することはできません。通常の静的相互接続は、疎結合ノードで構成された小規模ネットワークで主に使用されます。通常の構造とは、ノードが特定の形状に配置され、その形状がネットワーク全体で維持されることを意味します。

静的規則的相互接続の例としては、次のものがある: ^{[1] [2]}

• 完全に接続されたネットワーク

  

  メッシュ ネットワークでは、複数のノードが相互に接続されます。ネットワーク内の各ノードは、ネットワーク内の他のすべてのノードに接続されます。この配置により、ノード間で適切なデータ通信が可能になります。ただし、ノード接続の数が増えるため、通信のオーバーヘッドが大きくなります。
• 乗り合いバス

  

  このネットワーク トポロジでは、バスを介してノードが相互に接続されます。各ノードはバスを使用して他のすべてのノードと通信します。バス ユーティリティは、データが間違ったノードに送信されないようにします。ただし、バス トラフィックはシステムに影響を与える重要なパラメータです。
• 指輪

  

  これは、ノード同士を接続する最も簡単な方法の 1 つです。ノードは互いに接続されてリングを形成します。ノードが他のノードと通信するには、そのノードの隣接ノードにメッセージを送信する必要があります。したがって、データ メッセージは宛先に到達する前に一連の他のノードを通過します。これにより、システムの待ち時間が長くなります。
• 木

  

  このトポロジでは、ノードを接続してツリーを形成します。ノードは接続されてクラスターを形成し、クラスターは接続されてツリーを形成します。この方法論により、ネットワークの複雑さが増します。
• ハイパーキューブ

  

  このトポロジは、キューブを形成するノードの接続で構成されます。ノードは、他のキューブ上のノードにも接続されます。
• 蝶

  

  これは、ノードの最も複雑な接続の 1 つです。図が示すように、接続され、ランクに基づいて配置されたノードがあります。これらはマトリックスの形式で配置されます。

動的相互接続ネットワークでは、ノードは単純なスイッチング要素の配列を介して相互接続されます。^[3]この相互接続は、ルーティングアルゴリズムを使用して変更することができ、1つのノードから他のノードへのパスを変更できます。動的相互接続は次のように分類できます。

• シングルステージ相互接続ネットワーク
• 多段相互接続ネットワーク
• クロスバースイッチ接続

クロスバー スイッチでは、1 つのプロセッサから他のプロセッサへの専用パスが存在します。したがって、n 個の入力と m 個の出力がある場合、クロスバーを実現するには n*m 個のスイッチが必要になります。

出力の数が増えると、スイッチの数は n 倍に増加します。大規模ネットワークではこれが問題になります。

この方式の代替案は段階的な切り替えです。

シングル ステージ相互接続ネットワークでは、入力ノードは 1 ステージのスイッチを介して出力に接続されます。

この図は、シャッフル交換を使用した 8*8 シングル ステージ スイッチを示しています。

ご覧のとおり、1 回のシャッフルでは、すべての入力がすべての出力に到達できるわけではありません。すべての入力をすべての出力に接続するには、複数回のシャッフルが必要です。

マルチステージ相互接続ネットワークは、複数のシングルステージ スイッチをカスケード接続することで形成されます。スイッチは独自のルーティング アルゴリズムを使用するか、集中型ルーターによって制御され、完全に相互接続されたネットワークを形成します。

多段相互接続ネットワークは3つのタイプに分類できます。^[4]

1. 非ブロッキング: 非ブロッキング ネットワークは、ネットワーク全体で既に確立されている接続に関係なく、アイドル入力をアイドル出力に接続できます。クロスバーは、このタイプのネットワークの例です。
2. 再配置可能な非ブロッキング: このタイプのネットワークは、既存の接続を再配置することで、入力と出力間の可能なすべての接続を確立できます。
3. ブロッキング: このタイプのネットワークでは、入力と出力間のすべての可能な接続を実現することはできません。これは、1 つの空き入力から別の空き出力への接続が、ネットワーク内の既存の接続によってブロックされるためです。

ノンブロッキング ネットワークを実現するために必要なスイッチング要素の数は、最も多く、次に再配置可能なノンブロッキング ネットワークの順になります。ブロッキング ネットワークでは、スイッチング要素の使用数は最も少なくなります。

多段相互接続ネットワークには複数の種類が存在します。

オメガ ネットワークは、2*2 スイッチング エレメントの複数のステージで構成されます。各入力には、出力への専用接続があります。N*N オメガ ネットワークには、ステージ間の完全なシャッフルのために、log(N) 個のステージと各ステージの N/2 個のスイッチング エレメントがあります。したがって、ネットワークの複雑性は 0(N log(N)) です。各スイッチング エレメントは、独自のスイッチング アルゴリズムを使用できます。8*8 オメガ ネットワークを考えてみましょう。入力から出力への 1 対 1 のマッピングは 8! = 40320 あります。合計順列は 2^12 = 4096 で、スイッチング エレメントは 12 個あります。したがって、これはブロッキング ネットワークです。

Clos ネットワークは、N 個の入力から N 個の出力に切り替えるために 3 つのステージを使用します。最初のステージには、r = N/n 個のクロスバー スイッチがあり、各スイッチのサイズは n*m です。2 番目のステージには、サイズが r*r の m 個のスイッチがあり、最後のステージは最初のステージのミラーで、サイズが m*n の r 個のスイッチがあります。clos ネットワークは、m >= 2n-1 の場合、完全に非ブロッキングになります。接続数は、オメガ ネットワークよりは多いですが、クロスバー ネットワークよりははるかに少なくなります。

Beneš ネットワークは、n = m = 2 に初期化することで clos ネットワークから派生した、再配置可能な非ブロッキング ネットワークです。(2log(N) - 1) ステージがあり、各ステージには N/2 個の 2*2 クロスバー スイッチが含まれます。8*8 Beneš ネットワークには 5 ステージのスイッチング エレメントがあり、各ステージには 4 個のスイッチング エレメントが含まれます。中央の 3 ステージには 2 つの 4*4 beneš ネットワークが含まれます。4*4 Beneš ネットワークは、任意の入力を任意の出力に再帰的に接続できます。