Loading article…
ワームホールフロー制御は、ワームホールスイッチングまたはワームホールルーティングとも呼ばれ、既知の固定リンクに基づくコンピュータネットワークにおける単純なフロー制御システムです。これは、フリットバッファフロー制御と呼ばれるフロー制御方法のサブセットです。[1] ：第13.2.1章
ルーティングは宛先に到達するために取られるルートまたはパスを定義するため、スイッチングはルーティングよりも適切な用語です。[2] [3]ワームホール技術は宛先までのルートを指示するのではなく、パケットがルータから前方に移動するタイミングを決定します。
ワームホールスイッチングは、低レイテンシとノードでの要件が少ないため、マルチコンピュータで広く使用されています。[3] : 376
ワームホールルーティングは、リアルタイム通信に適した、非常に低遅延、高速、保証されたパケット配信をサポートします。[4]
メカニズムの原理
ワームホール フロー制御では、各パケットはフリット(フロー制御単位またはフロー制御桁) と呼ばれる小さな部分に分割されます。
通常、最初のフリットはヘッダー フリットと呼ばれ、このパケットのルートに関する情報 (宛先アドレスなど) を保持し、パケットに関連付けられた後続のすべてのフリットのルーティング動作を設定します。ヘッダー フリットの後には、実際のデータ ペイロードを含む 0 個以上のボディ フリットが続きます。最後のフリットはテール フリットと呼ばれ、2 つのノード間の接続を閉じるためにブックキーピングを実行します。
ワームホール スイッチングでは、各バッファはアイドル状態か、1 つのパケットに割り当てられます。バッファがアイドル状態の場合、ヘッダー フリットをバッファに転送できます。これにより、バッファがパケットに割り当てられます。ボディまたはトレーラー フリットは、このバッファがそのパケットに割り当てられていて、いっぱいでない場合、バッファに転送できます。最後のフリットによってバッファが解放されます。ヘッダー フリットがネットワークでブロックされると、バッファがいっぱいになり、いっぱいになると、それ以上のフリットを送信できなくなります。この効果は「バック プレッシャー」と呼ばれ、ソースに伝播される可能性があります。
「ワームホール」という名前は、パケットがリンク上で送信される方法に由来しています。アドレスは非常に短いため、メッセージ自体が到着する前に変換できます。これにより、ルータは実際のメッセージのルーティングをすばやく設定し、会話の残りから「退出」できます。パケットはフリットごとに送信されるため、パスに沿って複数のフリット バッファを占有し、ワームのようなイメージを作成します。
この動作は、一般に「仮想カットスルー」と呼ばれるカットスルースイッチング[5]と非常によく似ていますが、主な違いは、カットスルーフロー制御はバッファとチャネル帯域幅をパケットレベルで割り当てるのに対し、ワームホールフロー制御はフリットレベルで割り当てることです。
循環依存関係の場合、このバックプレッシャーによりデッドロックが発生する可能性があります。
ほとんどの点で、ワームホールは、セルをキューに入れる必要がない点を除いて、ATMまたはMPLS転送と非常によく似ています。
ワームホール フロー制御の特別な点の 1 つは、仮想チャネルの実装です。
仮想チャネルは、チャネル上のパケットのフリットの処理を調整するために必要な状態を保持します。この状態は、少なくとも、ルートの次のホップの現在のノードの出力チャネルと、仮想チャネルの状態（アイドル、リソース待ち、またはアクティブ）を識別します。仮想チャネルには、現在のノードでバッファリングされているパケットのフリットへのポインタと、次のノードで使用可能なフリットバッファの数も含まれる場合があります。[1] : 237
例
右図の 2x2 ネットワークで、3 つのパケットが送信されるとします。ピンク色のパケットは 4 つのフリット「UVWX」で構成され、C から D に送信されます。青色のパケットは 4 つのフリット「abcd」で構成され、A から F に送信されます。緑色のパケットは 4 つのフリット「ijkl」で構成され、E から H に送信されます。ルーティングは図のように計算されており、左下のルーターでバッファーの競合が発生していると想定します。スループットは時間単位あたり 1 フリットです。
まず、ピンク色のフローを検討します。時間 1 では、フリット「U」が最初のバッファーに送信されます。時間 2 では、フリット「U」が次のバッファーを通過し (ルートの計算に時間がかからないと仮定)、フリット「V」が最初のバッファーに送信されます。
青と緑のフローは、段階的なプレゼンテーションが必要です。
- 時間 1: 青と緑のフローの両方が最初のフリット「i」と「a」を送信します。
- 時間 2: フリット 'i' は次のバッファに進むことができます。ただし、バッファは最初のフリットから最後のフリットまでパケット専用であるため、'a' フリットは転送できません。これがバックプレッシャー効果の始まりです。'j' フリットは 'i' フリットを置き換えることができます。'b' フリットは送信できます。
- 時間 3: 緑のパケットが送信されます。青の「c」フリットは転送できません (バッファは「b」フリットと「a」フリットで占有されています)。このバック プレッシャー効果がパケット ソースに到達します。
- 時間4: 時間3と同じ
- 時間 5: 緑のパケットは左下バッファを使用しなくなりました。青のパケットはブロック解除され、転送できます (「ブロック解除された」情報がヌル時間で転送できると仮定)
- 時間 6 ～ 10: 青いパケットがネットワークを通過します。
利点
- ワームホール フロー制御は、カットスルーよりも効率的にバッファを使用します。カットスルーでは多数のパケットに相当するバッファ スペースが必要ですが、ワームホール方式では、比較的、フリット バッファが非常に少なくて済みます。
- 次のノードに移動するためにパケット全体をバッファリングする必要がないため、ストアアンドフォワードスイッチングに比べてネットワークの遅延が減少します。
- 帯域幅とチャネル割り当ては分離されている
使用法
ワームホール技術は、主にマルチプロセッサシステム、特にハイパーキューブで使用されます。ハイパーキューブ コンピュータでは、各CPU は固定パターンで複数の隣接 CPU に接続され、CPU 間のホップ数を削減します。各 CPU には、ネットワーク アドレスとなる番号 (通常は8 ビットから16 ビットのみ) が与えられ、CPU へのパケットは、ヘッダーにこの番号を付けて送信されます。パケットが転送のために中間ルーターに到着すると、ルーターはヘッダーを (非常に迅速に) 調べ、次のルーターへの回線をセットアップしてから、会話から退出します。これにより、パケット全体を待ってから転送するストア アンド フォワードスイッチングと比較して、レイテンシ (遅延) が大幅に削減されます。最近では、ワームホール フロー制御は、マルチコア プロセッサが 1 つの種類であるネットワーク オン チップシステム (NOC)のアプリケーションにも採用されています。ここでは、多数のプロセッサ コア、またはより低いレベルでは機能ユニットさえも、単一のICパッケージ上のネットワークに接続できます。配線遅延や、リンクされた処理要素に対するその他の多くのスケーラブルでない制約が設計の支配的な要因になるにつれて、エンジニアはフロー制御方法が重要な役割を果たす組織化された相互接続ネットワークの簡素化を模索しています。
IEEE 1355およびSpaceWireテクノロジーはワームホールを使用します。
仮想チャネル
ワームホール フロー制御の拡張は、仮想チャネルフロー制御です。仮想チャネル フロー制御では、複数の仮想チャネルを 1 つの物理チャネルに多重化できます。各単方向仮想チャネルは、独立して管理される (フリット) バッファのペアによって実現されます。異なるパケットは、フリットごとに物理チャネルを共有できます。仮想チャネルは、もともとデッドロック問題を回避するために導入されましたが、ワームホール ブロッキングを減らし、ネットワークの遅延とスループットを改善するためにも使用できます。ワームホール ブロッキングは、パケットがチャネルを取得すると発生し、他のパケットはチャネルを使用できなくなり、停止を余儀なくされます。パケット P0 が 2 つのルータ間のチャネルを取得したとします。仮想チャネルがない場合、後から到着するパケット P1 は、P0 の送信が完了するまでブロックされます。仮想チャネルが実装されると、次の改善が可能になります。
- P1 が到着すると、物理チャネルはフリットごとにそれらの間で多重化され、両方のパケットが半分の速度で進行します (調停方式によって異なります)。
- P0 がフルレングスのパケットであるのに対し、P1 が数フリットのサイズの小さな制御パケットである場合、この方式により、P0 は数パケットの送信に対応する短時間だけ遅くなる一方で、P1 は両方のルーターを通過できます。これにより、P1 のレイテンシが短縮されます。
- P0が現在のルータの下流で一時的にブロックされていると仮定します。P1が物理チャネルの最高速度で進むことを許可することで、スループットが向上します。仮想チャネルがなければ、P0はチャネルを占有しますが、実際には利用可能な帯域幅を使用しません（ブロックされているため）。[6]
仮想チャネルを使用してワームホール ブロッキングを削減する方法は、仮想出力キューを使用してヘッドオブライン ブロッキングを削減する方法と多くの類似点があります。
ルーティング
同じワームホールスイッチパケット内で、ソースルーティングと論理ルーティングを組み合わせて使用することができます。Myrinet または SpaceWire パケットの最初のバイトの値は、パケットのアドレスです。各SpaceWireスイッチは、このアドレスを使用してパケットのルーティング方法を決定します。[7]
ソースルーティング
ソース ルーティングでは、パケットの送信者がスイッチを介してパケットをルーティングする方法を選択します。
受信 SpaceWire パケットの最初のバイトが 1 から 31 の範囲にある場合、それは SpaceWire スイッチの対応するポート 1 から 31 を示します。その後、SpaceWire スイッチはそのルーティング文字を破棄し、パケットの残りをそのポートから送信します。これにより、元のパケットの次のバイトが次の SpaceWire スイッチに公開されます。パケット送信者は、ソース ルーティングを使用して、ネットワークから最終宛先までの完全なパスをこの方法で明示的に指定することもできます。[7]
論理ルーティング
論理ルーティングでは、Spacewire スイッチ自体がパケットのルーティング方法を決定します。
受信したSpaceWireパケットのアドレス（最初のバイト）が32～255の範囲にある場合、SpaceWireスイッチはその値を内部ルーティングテーブルのインデックスとして使用し、パケットを送信するポートと最初のバイトを削除するか保持するかを示します。[7]
アドレス0はスイッチと直接通信するために使用され、そのスイッチのルーティングテーブルエントリを設定するために使用される場合があります。[7]
参照
参考文献
- ^ ab William James Dally、Brian Towles (2004)。「13.2.1」。相互接続ネットワークの原則と実践。Morgan Kaufmann Publishers、Inc。ISBN 978-0-12-200751-4。
- ^ John L. Hennessy および David A. Patterson (2006)。「付録 E.5」。コンピュータアーキテクチャ: 定量的アプローチ(第 4 版)。Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-370490-0。
- ^ ab Mohapatra, Prasant (1998)、「直接接続されたマルチコンピュータシステム向けのワームホールルーティングテクニック」(PDF)、ACM Computing Surveys、30 (3): 374–410、CiteSeerX 10.1.1.11.9098、doi :10.1145/292469.292472、S2CID 7850481
- ^ Sharad Sundaresan、Riccardo Bettati。「ワームホールルーティングネットワーク上のリアルタイム通信のための分散接続管理」1997年。
- ^ Stefan Haas. 「IEEE 1355 規格: 高エネルギー物理学における開発、性能、応用」1998 年、59 ページ。
- ^ Pavel Tvrdik. 「なぜワームホールルーティングは重要なスイッチング技術なのか」
- ^ abcd Dr Barry M Cook、Paul Walker。「Ethernet over SpaceWire - ソフトウェアの問題」[ permanent dead link ] 2007年、p. 2。