相互接続ネットワークの設計
アン interconnection network並列マシンでは、任意の送信元ノードから任意の宛先ノードに情報を転送します。このタスクは、可能な限り短い待ち時間で完了する必要があります。これにより、このような転送を多数同時に実行できるようになります。さらに、それは機械の他の部分のコストと比較して安価でなければなりません。
ネットワークはリンクとスイッチで構成されており、送信元ノードから宛先ノードに情報を送信するのに役立ちます。ネットワークは、そのトポロジ、ルーティングアルゴリズム、スイッチング戦略、およびフロー制御メカニズムによって指定されます。
組織構造
相互接続ネットワークは、次の3つの基本コンポーネントで構成されています。
Links−リンクは、スイッチまたはネットワークインターフェイスポートに接続された両端にコネクタが付いた1つまたは複数の光ファイバまたは電線のケーブルです。これにより、アナログ信号が一方の端から送信され、もう一方の端で受信されて、元のデジタル情報ストリームが取得されます。
Switches−スイッチは、入力ポートと出力ポートのセット、すべての入力をすべての出力に接続する内部「クロスバー」、内部バッファリング、および各時点で入出力接続を実行するための制御ロジックで構成されます。通常、入力ポートの数は出力ポートの数と同じです。
Network Interfaces−ネットワークインターフェイスはスイッチノードとはまったく異なる動作をし、特別なリンクを介して接続される場合があります。ネットワークインターフェイスはパケットをフォーマットし、ルーティングおよび制御情報を構築します。スイッチと比較して、入力と出力のバッファリングがある場合があります。エンドツーエンドのエラーチェックとフロー制御を実行する場合があります。したがって、そのコストは、処理の複雑さ、ストレージ容量、およびポートの数に影響されます。
相互接続ネットワーク
相互接続ネットワークは、スイッチング要素で構成されています。トポロジは、個々のスイッチをプロセッサ、メモリ、その他のスイッチなどの他の要素に接続するためのパターンです。ネットワークにより、並列システムのプロセッサ間でデータを交換できます。
Direct connection networks−直接ネットワークには、隣接ノード間のポイントツーポイント接続があります。これらのネットワークは静的です。つまり、ポイントツーポイント接続は固定されています。直接ネットワークの例としては、リング、メッシュ、キューブがあります。
Indirect connection networks−間接ネットワークには固定ネイバーがありません。通信トポロジは、アプリケーションの要求に基づいて動的に変更できます。間接ネットワークは、バスネットワーク、多段ネットワーク、クロスバースイッチの3つの部分に分けることができます。
Bus networks−バスネットワークは、多数のリソースが接続されている多数のビットラインで構成されています。バスがデータとアドレスに同じ物理ラインを使用する場合、データとアドレスラインは時分割多重化されます。バスに複数のバスマスターが接続されている場合は、アービターが必要です。
Multistage networks−多段ネットワークは、スイッチの複数のステージで構成されます。これは、特定の段間接続パターン（ISC）を使用して接続された「axb」スイッチで構成されています。小さな2x2スイッチ要素は、多くの多段ネットワークで一般的な選択肢です。ステージの数によって、ネットワークの遅延が決まります。さまざまな段間接続パターンを選択することにより、さまざまなタイプの多段ネットワークを作成できます。
Crossbar switches−クロスバースイッチには、接続を作成または切断するためにオンとオフを切り替えることができる単純なスイッチ要素のマトリックスが含まれています。マトリックス内のスイッチ要素をオンにすると、プロセッサとメモリを接続できます。クロスバースイッチは非ブロッキングです。つまり、すべての通信順列はブロッキングなしで実行できます。
ネットワークトポロジにおける設計のトレードオフの評価
主な関心事がルーティング距離である場合、寸法を最大化し、超立方体を作成する必要があります。ストアアンドフォワードルーティングでは、スイッチの程度とリンクの数が重要なコスト要因ではなく、リンクの数またはスイッチの程度が主なコストであると仮定すると、次元を最小化してメッシュを作成する必要があります構築されました。
各ネットワークの最悪の場合のトラフィックパターンでは、すべてのパスが短い高次元のネットワークが望ましいです。各ノードが1つまたは2つの近くの隣接ノードとのみ通信しているパターンでは、実際に使用される次元はごくわずかであるため、低次元のネットワークを使用することをお勧めします。
ルーティング
ネットワークのルーティングアルゴリズムは、送信元から宛先までの可能なパスのどれをルートとして使用するか、および特定の各パケットがたどるルートをどのように決定するかを決定します。ディメンションオーダールーティングは、各送信元から各宛先へのルートが1つだけになるように、有効なパスのセットを制限します。最初に高次の次元で正しい距離を移動し、次に次の次元を移動することによって得られるもの。
ルーティングメカニズム
算術演算、ソースベースのポート選択、およびテーブルルックアップは、高速スイッチがパケットヘッダーの情報から出力チャネルを決定するために使用する3つのメカニズムです。これらのメカニズムはすべて、従来のLANおよびWANルーターで実装されている一般的なルーティング計算よりも単純です。並列コンピュータネットワークでは、スイッチはすべてのサイクルですべての入力のルーティングを決定する必要があるため、メカニズムはシンプルで高速である必要があります。
決定論的ルーティング
メッセージがたどるルートが、ネットワーク内の他のトラフィックではなく、送信元と宛先によってのみ決定される場合、ルーティングアルゴリズムは決定論的です。ルーティングアルゴリズムが宛先への最短パスのみを選択する場合、それは最小です。それ以外の場合は非最小です。
デッドロックの自由
デッドロックはさまざまな状況で発生する可能性があります。2つのノードが相互にデータを送信しようとし、それぞれが受信する前に送信を開始すると、「正面からの」デッドロックが発生する可能性があります。ネットワーク内のリソースをめぐって競合する複数のメッセージがある場合、デッドロックの別のケースが発生します。
ネットワークにデッドロックがないことを証明するための基本的な手法は、ネットワーク内を移動するメッセージの結果としてチャネル間で発生する可能性のある依存関係をクリアし、チャネル依存関係グラフ全体にサイクルがないことを示すことです。したがって、デッドロックにつながる可能性のあるトラフィックパターンはありません。これを行う一般的な方法は、すべてのルートが特定の増加または減少シーケンスに従うようにチャネルリソースに番号を付けて、依存サイクルが発生しないようにすることです。
スイッチの設計
ネットワークの設計は、スイッチの設計とスイッチの配線方法によって異なります。スイッチの次数、その内部ルーティングメカニズム、およびその内部バッファリングによって、サポートできるトポロジと実装できるルーティングアルゴリズムが決まります。コンピュータシステムの他のハードウェアコンポーネントと同様に、ネットワークスイッチにはデータパス、制御、およびストレージが含まれています。
ポート
ピンの総数は、実際には入力ポートと出力ポートの総数にチャネル幅を掛けたものです。チップの周囲が面積に比べてゆっくりと成長するため、スイッチはピン制限される傾向があります。
内部データパス
データパスは、入力ポートの各セットとすべての出力ポートの間の接続です。これは一般に内部クロスバーと呼ばれます。ノンブロッキングクロスバーとは、各入力ポートを任意の順列で同時に個別の出力に接続できるクロスバーです。
チャネルバッファ
スイッチ内のバッファストレージの構成は、スイッチのパフォーマンスに重要な影響を及ぼします。従来のルーターとスイッチは、スイッチファブリックの外部に大きなSRAMまたはDRAMバッファーを備えている傾向がありますが、VLSIスイッチでは、バッファーはスイッチの内部にあり、データパスおよび制御セクションと同じシリコンバジェットから出力されます。チップのサイズと密度が増加するにつれて、より多くのバッファリングが利用可能になり、ネットワーク設計者はより多くのオプションを利用できますが、それでもバッファ領域が最優先され、その編成が重要になります。
フロー制御
ネットワーク内の複数のデータフローが同じ共有ネットワークリソースを同時に使用しようとする場合、これらのフローを制御するために何らかのアクションを実行する必要があります。データを失いたくない場合は、一部のフローをブロックし、他のフローを続行する必要があります。
フロー制御の問題は、すべてのネットワークおよび多くのレベルで発生します。ただし、並列コンピュータネットワークでは、ローカルおよびワイドエリアネットワークとは質的に異なります。並列コンピューターでは、ネットワークトラフィックはバスを通過するトラフィックとほぼ同じくらい正確に配信される必要があり、非常に短い時間スケールで非常に多数の並列フローがあります。