相互接続ネットワーク設計

並列マシンの*相互接続ネットワーク*は、任意のソースノードから任意の目的のノードに情報を転送します。このタスクは、可能な限り短い遅延で完了する必要があります。多数のこのような転送を同時に実行できるようにする必要があります。さらに、それは機械の残りの部分のコストと比較して安価でなければなりません。

ネットワークはリンクとスイッチで構成され、情報を送信元ノードから宛先ノードに送信するのに役立ちます。ネットワークは、トポロジ、ルーティングアルゴリズム、スイッチング戦略、およびフロー制御メカニズムによって指定されます。

組織構造

相互接続ネットワークは、次の3つの基本コンポーネントで構成されます-

リンク-リンクは、スイッチまたはネットワークインターフェイスポートに接続された各端にコネクタが付いた1つ以上の光ファイバーまたは電線のケーブルです。これにより、アナログ信号が一方の端から送信され、もう一方の端で受信されて元のデジタル情報ストリームが取得されます。
スイッチ-スイッチは、入力および出力ポートのセット、すべての入力をすべての出力に接続する内部「クロスバー」、内部バッファリング、および各時点で入出力接続を実現する制御ロジックで構成されます。一般に、入力ポートの数は出力ポートの数と同じです。
ネットワークインターフェース-ネットワークインターフェースはスイッチノードとはまったく異なる動作をし、特別なリンクを介して接続される場合があります。ネットワークインターフェイスはパケットをフォーマットし、ルーティングおよび制御情報を構築します。スイッチと比較して、入力および出力のバッファリングがある場合があります。エンドツーエンドのエラーチェックとフロー制御を実行できます。したがって、そのコストは、処理の複雑さ、ストレージ容量、ポート数に影響されます。

相互接続ネットワーク

相互接続ネットワークは、スイッチング要素で構成されています。トポロジは、個々のスイッチをプロセッサ、メモリ、その他のスイッチなどの他の要素に接続するパターンです。ネットワークにより、並列システムのプロセッサ間でデータを交換できます。

直接接続ネットワーク-直接ネットワークには、隣接ノード間のポイントツーポイント接続があります。これらのネットワークは静的です。つまり、ポイントツーポイント接続は固定されています。直接ネットワークの例には、リング、メッシュ、キューブがあります。
間接接続ネットワーク-間接ネットワークには固定ネイバーがありません。通信トポロジーは、アプリケーションの要求に基づいて動的に変更できます。間接ネットワークは、バスネットワーク、マルチステージネットワーク、クロスバースイッチの3つの部分に分割できます。
バスネットワーク-バスネットワークは、いくつかのリソースが接続されているいくつかのビット線で構成されています。バスがデータとアドレスに同じ物理ラインを使用する場合、データとアドレスラインは時間多重化されます。バスに複数のバスマスターが接続されている場合、アービターが必要です。
マルチステージネットワーク-マルチステージネットワークは、スイッチの複数のステージで構成されます。これは、特定のインターステージ接続パターン（ISC）を使用して接続された「axb」スイッチで構成されています。小型の2x2スイッチエレメントは、多くの多段ネットワークで一般的な選択肢です。ステージの数がネットワークの遅延を決定します。異なるステージ間接続パターンを選択することにより、さまざまなタイプのマルチステージネットワークを作成できます。
クロスバースイッチ-クロスバースイッチには、接続を作成または切断するためにオン/オフを切り替えることができる単純なスイッチ要素のマトリックスが含まれています。マトリックス内のスイッチエレメントをオンにすると、プロセッサとメモリを接続できます。クロスバースイッチは非ブロッキングです。つまり、すべての通信順列はブロッキングなしで実行できます。

ネットワークトポロジでの設計のトレードオフの評価

主な関心事がルーティング距離である場合、寸法を最大化し、ハイパーキューブを作成する必要があります。ストアアンドフォワードルーティングでは、スイッチの程度とリンクの数が重要なコスト要因ではなく、リンクの数またはスイッチの程度が主なコストであると仮定すると、次元を最小化し、メッシュ作りました。

各ネットワークの最悪の場合のトラフィックパターンでは、すべてのパスが短い高次元ネットワークを使用することをお勧めします。各ノードが1つまたは2つの近隣のノードとのみ通信するパターンでは、実際に使用されるディメンションはごく少数であるため、低次元のネットワークを使用することをお勧めします。

ルーティング

ネットワークのルーティングアルゴリズムは、ソースから宛先への可能なパスのどれがルートとして使用されるか、および特定の各パケットがたどるルートがどのように決定されるかを決定します。次元順序ルーティングは、各ソースから各宛先へのルートが1つだけになるように、有効なパスのセットを制限します。最初に高次元で正しい距離を移動し、次に次の次元に移動するなどして得られたもの。

ルーティングメカニズム

算術、ソースベースのポート選択、およびテーブル検索は、高速スイッチがパケットヘッダーの情報から出力チャネルを決定するために使用する3つのメカニズムです。これらのメカニズムはすべて、従来のLANおよびWANルーターに実装されている種類の一般的なルーティング計算よりも単純です。並列コンピューターネットワークでは、スイッチはすべてのサイクルですべての入力のルーティングを決定する必要があるため、メカニズムはシンプルかつ高速である必要があります。

確定的ルーティング

ルーティングアルゴリズムは、メッセージがたどるルートがネットワーク内の他のトラフィックではなく、送信元と宛先によってのみ決定される場合に決定的です。ルーティングアルゴリズムが宛先への最短パスのみを選択する場合、それは最小であり、そうでない場合は非最小です。

デッドロックの自由

デッドロックはさまざまな状況で発生する可能性があります。 2つのノードが互いにデータを送信しようとし、それぞれが受信する前に送信を開始すると、「ヘッドオン」デッドロックが発生する場合があります。ネットワーク内のリソースを奪い合う複数のメッセージがある場合、デッドロックの別のケースが発生します。

ネットワークを証明するための基本的な手法は、デッドロックがなく、ネットワーク内を移動するメッセージの結果としてチャネル間で発生する可能性のある依存関係をクリアし、チャネル依存関係グラフ全体にサイクルがないことを示すことです。したがって、デッドロックを引き起こす可能性のあるトラフィックパターンはありません。これを行う一般的な方法は、依存関係サイクルが発生しないように、すべてのルートが特定の増加または減少シーケンスに従うようにチャネルリソースに番号を付けることです。

スイッチ設計

ネットワークの設計は、スイッチの設計とスイッチの相互接続方法に依存します。スイッチの程度、内部ルーティングメカニズム、および内部バッファリングによって、サポートできるトポロジと実装可能なルーティングアルゴリズムが決まります。コンピューターシステムの他のハードウェアコンポーネントと同様に、ネットワークスイッチにはデータパス、制御、およびストレージが含まれます。

ポート

ピンの総数は、実際には入力ポートと出力ポートの総数にチャネル幅を掛けたものです。チップの周囲が面積と比較してゆっくりと成長するにつれて、スイッチはピン制限される傾向があります。

内部データパス

データパスは、入力ポートの各セットとすべての出力ポート間の接続です。通常、内部クロスバーと呼ばれます。ノンブロッキングクロスバーは、各入力ポートを任意の順列で個別の出力に同時に接続できるクロスバーです。

チャンネルバッファー

スイッチ内のバッファストレージの構成は、スイッチのパフォーマンスに重要な影響を及ぼします。従来のルーターとスイッチは、スイッチファブリックの外部に大きなSRAMまたはDRAMバッファーを持っている傾向がありますが、VLSIスイッチでは、バッファリングはスイッチの内部にあり、データパスおよび制御セクションと同じシリコンバジェットから発生します。チップのサイズと密度が増加するにつれて、より多くのバッファリングが利用可能になり、ネットワーク設計者はより多くのオプションを使用できるようになりますが、それでもバッファの不動産は最優先の選択肢であり、その構成は重要です。

フロー制御

ネットワーク内の複数のデータフローが同じ共有ネットワークリソースを同時に使用しようとする場合、これらのフローを制御するために何らかのアクションを実行する必要があります。データを失いたくない場合は、一部のフローをブロックし、他のフローを続行する必要があります。

フロー制御の問題は、すべてのネットワークおよび多くのレベルで発生します。ただし、並列コンピュータネットワークでは、ローカルネットワークやワイドエリアネットワークとは質的に異なります。並列コンピューターでは、ネットワークトラフィックをバスを通過するトラフィックとほぼ同じくらい正確に配信する必要があり、非常に短い時間スケールで非常に多数の並列フローがあります。

Parallel-computer-architecture-interconnection-network-design

目次