オメガネットワーク

オメガネットワークは、並列コンピューティングアーキテクチャでよく使用されるネットワーク構成です。これは、完全なシャッフル相互接続アルゴリズムに依存する間接トポロジです。

8x8 オメガ ネットワークは多段相互接続ネットワークです。つまり、処理要素 (PE) は複数段のスイッチを使用して接続されます。図に示すように、入力と出力にはアドレスが割り当てられます。各段からの出力は、完全シャッフル接続システムを使用して次の段の入力に接続されます。つまり、各段での接続は、1 組のカードが 2 つの等しいデッキに分割されて一緒にシャッフルされ、一方のデッキの各カードがもう一方のデッキの対応するカードと交互になる動きを表します。PE のバイナリ表現では、完全シャッフルの各段は、循環論理左シフトと考えることができます。アドレスの各ビットは左に 1 回シフトされ、最上位ビットが最下位ビットに移動します。

各ステージでは、隣接する入力ペアが単純な交換要素に接続されます。この要素は、ストレート (入力を直接出力に渡す) またはクロス (上部の入力を下の出力に送り、その逆も行う) に設定できます。N 処理要素の場合、オメガ ネットワークには各ステージに N/2 個のスイッチがあり、ステージ数は log ₂ N です。これらのスイッチの設定方法によって、ネットワークで使用可能な接続パスがいつでも決定されます。このような 2 つの方法は、宛先タグ ルーティングと XOR タグ ルーティングです。これらについては、以下で詳しく説明します。

オメガ ネットワークは高度にブロック化されていますが、フリー ネットワークでは任意の入力から任意の出力への 1 つのパスを常に作成できます。

宛先タグ ルーティングでは、スイッチ設定はメッセージの宛先によってのみ決定されます。宛先アドレスの最上位ビットは、第 1 ステージのスイッチの出力を選択するために使用されます。最上位ビットが 0 の場合は上位の出力が選択され、1 の場合は下位の出力が選択されます。宛先アドレスの次の上位ビットは、次のステージのスイッチの出力を選択するために使用され、最終的な出力が選択されるまでこれが続きます。

たとえば、メッセージの宛先が PE 001 の場合、スイッチ設定は、上、上、下です。メッセージの宛先が PE 101 の場合、スイッチ設定は、下、上、下です。これらのスイッチ設定は、メッセージを送信する PE に関係なく保持されます。

XOR タグ ルーティングでは、スイッチ設定は (送信元 PE) XOR (送信先 PE) に基づきます。この XOR タグには、スワップする必要があるビット位置に 1 が含まれ、送信元と送信先の両方に共通するビット位置に 0 が含まれます。XOR タグの最上位ビットは、最初のステージでスイッチの設定を選択するために使用されます。最上位ビットが 0 の場合、スイッチはパススルーに設定され、1 の場合、スイッチはクロスされます。タグの次の上位ビットは、次のステージでスイッチを設定するために使用され、最終出力が選択されるまでこれが続きます。

たとえば、PE 001 が PE 010 にメッセージを送信する場合、XOR タグは 011 になり、適切なスイッチ設定は A2 ストレート、B3 クロス、C2 クロスになります。

マルチプロセッシングでは、 CPUとメモリ間の接続がボトルネックになる 可能性を減らすために、CPUとその共有メモリ間のコネクタとしてオメガ ネットワークが使用されることがあります。

このクラスのネットワークは、イリノイ・シーダー・マルチプロセッサ、IBM RP3、および NYU ウルトラコンピュータに組み込まれています^{[引用が必要]}。

• C言語によるオメガネットワークシミュレーション

• クロスネットワーク
• キューブ接続サイクル
• ノンブロッキング最小スパニングスイッチ
• バンヤンスイッチ
• デルタネットワーク
• 太った木
• クロスバースイッチ
• ネットワークコーディング

• Lawrie, Duncan H. (1975年12 月)。「アレイ プロセッサにおけるデータのアクセスとアラインメント」。IEEE Transactions on Computers。C - 24 (12): 1145–55。doi :10.1109/TC.1975.224157。