システムエリアネットワークにおける適応型ルーティングの In-Order パケット配送手法 鯉 渕 道 紘†,†† Juan C. Martinez†† Jose Flich†† Jose Duato†† 動的に経路を選択することができる適応型ルーティングは，並列計算機の相互結合網やシステムエ リアネットワークにおいて幅広く研究が行われている．適応型ルーティングは高バンド幅を提供する が，メッセージパッシングライブラリが必要とする In-Order パケット配送を保証していない．本稿で は，適応型ルーティングにおいて In-Order でパケットを配送するために 1) FIFO 転送法と 2) 一対制 限法を提案する．両手法とも出発地ホストにおいてパケットの注入量を制限する．FIFO 転送法は目 的地ホストにおいてパケットのソートをする必要がない一方，一対制限法は目的地ホストにおいてパ ケットのソートのために少量のバッファが必要となる．NAS Parallel Benchmarks のトレースと典型的 なアクセスパターンを用いた評価結果より，FIFO 転送法と一対制限法は end-to-end フロー制御を行 わない適応型ルーティングとほぼ同等のスループットを達成した． In-Order Packet Delivery Techniques of Adaptive Routing in System Area Networks M K,†,†† J C. M,†† J F†† and J D†† Adaptive routing, which dynamically selects the route of a packet, has been widely studied for interconnection networks in massively parallel computers, and system area networks. Although adaptive routing has the advantage of providing high bandwidth, it doesn’t guarantee in-order packet deliver, which message passing libraries require. In this paper, we propose two mechanisms called 1) FIFO transmission and 2) couple limitation to guarantee in-order packet delivery in adaptive routing. Both of them limit packet injection at source hosts. The FIFO transmission completely avoids packet sorting at destination hosts, while the couple limitation uses few additional buffers to sort packets at destination hosts. Evaluation results show that the FIFO transmission and the couple limitation achieve a similar throughput to that of an original adaptive routing, which doesn’t employ any end-to-end flow control, under both synthetic traffic and NAS Parallel Benchmarks. 用するために解決しなければならない最も重要な問題は， Out-of-Order で到着するパケットの扱いであると考えら れる． 本稿では，適応型ルーティングにおいて In-Order パケッ ト転送を保証するために，FIFO (First-In First-Out) 転送法 と一対制限法を提案する．FIFO 転送法は，目的地ホスト におけるパケットのソートを避けるために注入制限を課 す．一対制限法は FIFO 転送法に比べて注入制限は緩い が，目的地ホストにおいてパケットのソートを行うため の少量のバッファが必要になる．以降，2 章では FIFO 転 送法と一対制限法の提案を行い，3 章ではシミュレーショ ン結果を示す．最後に 4 章で結論を述べる． 1. は じ め に 動的に経路を選択することができる適応型ルーティン グは並列計算機の相互結合網およびシステムエリアネッ トワーク (SAN) においてリンクバンド幅を活用する技術 として幅広く研究が行われてきた．しかし，現状では，多 くのシステムエリアネットワークは適応型ルーティング を採用していない．これは，適応型ルーティングを導入 することにより，新たな 2 つの問題がネットワークに発 生するためと考えられる; 1) In-Order パケット配送を保証 していない: 2) 複数経路の中から 1 つの経路を選択する機 能を付加することにより，スイッチの複雑さが増す．前者 は，メッセージパッシングライブラリが In-Order パケッ ト配送を必要とすることに起因する． しかし，後者は，並列に出力チャネル状態をチェックし， さらに，単純な選択な出力選択ポリシ (ランダム等) を採用 することにより，極端にスイッチのルーティング時間，複 雑さが増すことはないと考えられる．実際に Cray T3E1) ， Reliable Router2) において適応型ルーティングの実現性が 示されている．SAN に関しても，InfiniBand スイッチに おける適応型ルーティングを採用するための手法が検討 されている3) ．よって，適応型ルーティングを SAN に適 2. In-Order パケット配送手法 適応型ルーティングにおいて In-Order パケット転送を実 現する最も単純は方法は，Out-of-Order で到着するすべて のパケットを目的地ホストのネットワークインタフェース に格納し，追い越したパケットの到着を待つことで，ソー トする方法である．この方法は end-to-end フロー制御を 用いていない元の適応型ルーティングと同等のネットワー クスループットを提供することができる利点を持つ．し かし，この手法は，すべての出発地ホストに対して，Outof-Order で到着したパケットを格納する十分なバッファを 割当てる必要があるため，スケーラビリティに乏しい． そこで，われわれは目的地ホストにおけるパケットの ソートが必要ない FIFO 転送法と目的地ネットワークイ † 慶應義塾大学理工学部 Faculty of Science and Technology, Keio University, Japan †† バレンシア工科大学 Technical University of Valencia, Spain 1 ラグの値を反転させ，Out-of-Order フラグの 値を 1 にする． ( b ) もし，Out-of-Order で目的地に到着したパ ケットの ACK でありその Out-of-Order フ ラグが 1 の場合，Out-of-Order フラグの値 を zero にする． ( 4 ) NACK を受信した場合，その廃棄されたパケット と同じ順序フラグの値を挿入したパケットを再注 入する． ステップ 3 において，Out-Of-Order フラグは，順序フ ラグの出発地，目的地間の一貫性を取るために用いる．詳 細は，後に図 3, 4 と 5 を用いて説明を行う． ンタフェースにおいてパケットのソートのための少量の バッファを用いる一対制限法を提案する．両手法とも 1 つ の目的地ホストに一度に送信できるパケット数を制限す る．SAN では 1 つのスイッチに複数ホストが接続される ため，スイッチ間リンクは多数のホストからのパケット により共有される．よって，このリンクがホストからの 注入リンクに比べてボトルネックになる場合が多い．さ らに，SAN ではスイッチとリンク遅延は数百 ns 程度と小 さいため，この注入制限による性能低下はほとんどない (詳しくは第 4 章で評価を行う)． 2.1 FIFO 転送法 FIFO 転送法では，同一目的地への (前の) パケットの ACK (acknowledgment) を受けとった後に，次のパケット をネットワークに注入する．そのため，同一ホスト間に おいてパケットの追い越しが起こらず，目的地ホストに おけるパケットのソートなしに In-Order パケット配送を 提供することができる． 目的地ホストにおける ACK は 1) ネットワークインタ フェースにパケットの全体を格納した後，もしくは 2) パ ケットのヘッダの到着後すぐに生成することが可能であ る．後者の場合，ACK はパケット全体が正しく受信され たことを示すものではないが，レイテンシが小さくなる ため，同一目的地へのパケットの注入量を増やすことが できる． 目的地とのラウンドトリップ時間を t とすると，FIFO 転送法における 1 つの目的地への最大パケット注入量は， t 時間あたり 1 パケットとなる．この注入制限は，ACK の到着を待たずに注入可能なパケット数を増やすことに より，簡単に緩めることができる．この改善手法は，次 節において述べる． 2.2 一対制限法 一対制限法では，出発地ネットワークインタフェース において同一目的地ホストへ一度に送信できるパケット 数を 2 つとする．そのため，高々2 パケット間でのみ Outof-Order パケット転送が生じる．そこで，目的地ネット ワークインタフェースにおいてソートのために，1 パケッ トを格納するバッファを用意する． 本手法は以下のように単純に実装することができる．こ の場合，パケットに対してパケット番号，ACK に対して Out-of-Order パケット転送の発生の有無を示すために，各 1-bit 必要となる．一方，パケットを格納するためのバッファ とその制御のためのテーブルがネットワークインタフェー スに必要となる．また，ACK だけでなく NACK(negative acknowledgment) も使用する． 出発地におけるパケット処理は次の通りである． ( 1 ) 2 ビットカウンタ，1 ビットの順序フラグ，1 ビッ トの Out-of-Order フラグを各目的地ホストに対応 させ，それぞれを zero で初期化する． ( 2 ) 目的地ホストに対応しているカウンタ値が 2 以下 の場合，パケットを注入することができる．その場 合，パケットには 1 ビットの順序フラグの値を挿 入し，その後，カウンタ値を 1 増加させ，順序フラ グの値を反転させる (zero → one or one → zero)． ( 3 ) ACK を受信した場合，ACK の送信元に対応するカ ウンタ値を 1 減少させる． ( a ) もし，Out-of-Order で目的地に到着したパ ケットの ACK であり (これは ACK に格納 されている 1-bit の情報から判断する)，その Out-of-Order フラグが zero の場合，順序フ Sorting Buf. 0 Src 0 Src 1 ......... Src N 1 Seq ... b ... ,,, -1 ... 1.Compare b Network Seq (flag) Buf.ID 2.Transfer to memory Packet from N Host Memory 3.ACK Network Interface 図1 Couple limitation in destination ( when a packet arrives in-order. ) 一方，目的地のパケット処理は次の通りである． (1) 1-bit 順序フラグとソートバッファへのインデックス を各出発ホストに対応させ，各々 −1 と zero に初期 化する． (2) パケットが到着した場合，パケットヘッダの 1-bit の 順序フラグと，対応するネットワークインタフェー スの 1-bit の順序フラグの値を比較する． (3-a)もし，順序フラグの値が等しく，かつ，同じ出発地 ホストからのパケットがソートバッファに格納され ていない場合 (図 1)，そのパケットはホストメモリに 転送され，ネットワークインタフェースの 1-bit 順序 フラグの値を反転させる．そして，Out-of-Order フラ グの値を zero とした ACK を生成する． (3-b)順序フラグの値が違う場合，Out-of-Order 配送を検 出したことになる．その場合，ソートバッファの状 況に応じて次の処理を行う． (i) すべてのソートバッファが使用中，もしくは，同 じソースホストからのパケットがすでに格納さ れている場合，パケットを破棄し，NACK を生 成する． (ii) ソートバッファに空きがあり，ソートバッファに 同じソースホストからのパケットが格納されて いない場合，パケットをソートバッファに格納す る．そして，Out-of-Order フラグの値を 1 とした ACK を生成する (図 2.(a))． 3-c もし，順序フラグの値が同じであり，ソートバッファ が，同じ出発地ホストからのパケットをすでに格納し ている場合 (図 2.(b))，Out-of-Order 配送はすでに検出 されている状態である．その場合，Out-of-Order フラ グの値を 1 とした ACK を生成する．そして，今到着し たパケットをホストメモリに配送した後，ソートバッ ファに格納されているパケットを配送する (図 2.(c)). そして，1-bit 順序フラグの値を反転させ，ソートバッ 2 ファへのインデックスを再初期化する． 1-bit sequence flag 1.Send Packet2(1). 1.Send Packet 0(0). Sorting Buf. 0 Seq Src 0 Src 1 ......... Src s 1 ... ~b ... 2.Transfer to Buf. Sorting Buf. Buf.ID 0 ,,, -1 ... 1 b Network Buf.ID ... ~b ... ,,, 1 ... Src 0 Src 1 ......... Src s b 1.Compare. Seq ~b Seq Host Memory 2.ACK Network 2.Transfer to memory Packet from s Seq Flag 1 0 Host Memory 3.ACK Network Interface Network Interface (a) Phase 1 Sorting Buf. 0 1 b Src 0 Src 1 ......... Src s Seq Buf.ID ... b ... ,,, -1 ... 0 2 0 1 0 3 0 0 図4 Host Memory 0 3 0 0 Seq Flag 1 0 Dst 1.Send Packet 2(1). Src Seq Flag 1 1 2 0 OOO Flag 1 OOO Flag 0 2 1 Dst ACK of Pkt 1 is blocked. 1. Receive ACK of Pkt0. Src Seq Flag 1 0 OOO Flag 0 Src Packet 2(1) Dst OOO Flag 1 ACK of Pkt 1 is still blocked. (c) Phase 3 2.Send Packet 3(0). Src Seq Flag 1 0 2 0 図5 ACK of Pkt1 is still blocked. (b) Phase 2 1.Send Packet 2(1). Seq Flag 1 1 Dst 0 (a) Phase 1 OOO Flag 1 Dst 1. Receive ACK of Pkt 1. 0 (d) Phase 4 Couple limitation in source ( when ACKs are arrived out-of-order. ) に送信することを許すが，1-bit でそのパケットの順序を 調べることができる．さらに，目的地ネットワークインタ フェースにおいて，1 パケットを格納するバッファを用意 することで，1 つの出発地ホストからのパケットをソート することができる．多くの並列アプリケーションは，ア クセスの局所性を持つため，ネットワークインタフェー スに必要なバッファサイズは少量である．このバッファサ イズの評価は 3 章で行う． 2.3 FIFO 転送法と一対制限法における注入制限 並列計算機と異なり，SAN では複数のホストが 1 つの スイッチに接続される．よって，SAN ではより多くのホ スト間の経路が 1 つのスイッチ間リンクを共有すること になる．これは，スイッチ間リンクのバンド幅がホスト リンクに比べてボトルネックになりやすいことを示して おり，2 つの提案手法によるスループットへの影響は小さ いと考えられる． ここで，FIFO 転送法と一対制限法の注入制限について 焦点をあてる．これらは，同時に同一目的地に送信でき るパケット注入量に違いがある．FIFO 転送法が 1 つのパ ケットのみを許可するのに対し，一対制限法は 2 つのパ ケットの注入を許可する．よって，一対制限法の振舞い は，end-to-end のフロー制御を行わない元の適応型ルー ティングにより近いといえる．同様に，目的地において パケットヘッダを受けとった後すぐに ACK を生成するこ とで，全体のパケットを受信後，ACK を生成する場合に 比べて注入量を増やすことができる． Packet 0(0) is still blocked. (a) Phase 1 図3 2.Send Packet 1(1). Src (BLOCKED) 2 1 Packet 0(0) is arrived at Dst. (BLOCKED) 1.Send Packet 0(0). OOO Flag 0 (b) Phase 2 Couple limitation in source ( when ACKs are arrived in-order. ) 1-bit sequence flag 1-bit sequence flag Seq Flag 1 0 Dst 3.Send Packet3(0). 1.Send Packet 0(0). 一対制限法では図 3 に示したように同一ホスト間にお いて複数のパケットが，1 つのパケットを追い抜くことが 起こりうる．よって，NACK は目的地の処理のステップ 3-b(i) において，ソートバッファに空きがあるにも関わら ず生成される場合がある． ここで，Out-of-Order で到着したパケットの ACK が InOrder で届いた場合の処理を図 4 に示す．図 3 と 4 に示 した通り，Out-of-Order パケット配送が発生した場合に限 り，連続する 2 パケットが同じ順序フラグの値を持つ．こ れは，目的地において，追い越されたパケット (図 3 にお ける Packet 0) と新たに注入されたパケット (図 3 におけ る Packet 2) の識別を行う必要があるためである． 次に，Out-of-Order で到着したパケットの ACK が Outof-Order で届いた場合の処理を図 5 に示す．図 5 は，パ ケット 0 の ACK が Out-of-Order フラグの値を 1 に更新す る点が図 4 と異なる．しかし，両者ともパケットが Outof-Order で到着した後，はじめに到着した ACK が出発地 の Out-of-Order フラグを 1 に更新する点は同じである． また，すべてのパケットが In-Order で到着した場合，出 発地は独自に順序フラグを管理しているため，ACK の到 着順は出発地，目的地の一対制限法の処理に影響しない． 3. Receive ACK of Pkt1. OOO Flag 1 (a) Phase 1 Couple limitation in destination ( when a packet arrives out-of-order. ) 2.Send Packet 1(1). Seq Flag 1 1 3 0 (c) Phase 3 Src 2. Receive ACK of Pkt 0. Src 2 1 Network Interface 図2 Dst 3.Receive ACK of Pkt 1. OOO Flag 0 (b) Phase 2 Transfer to memory Network 2.Send Packet 1(1). Src 1.Compare. Packet from s Packet0(0) is delivered. (BLOCKED) Dst 2. Receive NACK of Pkt2. 1 (b) Phase 2 Couple limitation in source ( when a NACK is generated. ) なお，FIFO 転送法と同様に，目的地ホストにおける ACK は 1) ネットワークインタフェースにパケットの全体 を格納した後，もしくは 2) パケットのヘッダの到着後す ぐに生成することが可能である． 一対制限法は，同時に高々2 つのパケットを同一目的地 3 3. 評 表1 価 本章では，FIFO 転送法と一対制限法の性能評価を行う． また，比較のため，end-to-end フロー制御を用いない適応 型ルーティングと固定ルーティングについても同様に評 価を行う． 3.1 シミュレーション条件 3.1.1 ネットワークモデル スイッチと point-to-point リンクで構成されたネットワー クをモデルとした．各スイッチは 8 ポートを持ち，そのう ち 4 ポートはホストと接続し，残りの 4 ポートは隣接ス イッチとの接続に用いた．トポロジはランダムに接続し たイレギュラーネットワークと 2 次元メッシュを用いた． また，一対制限法では，16 パケットを格納できるサイズ のソートバッファを用いた．また，パケットヘッダは 2 フ リットとし，ACK は 3 フリットとした．デッドロックフ リールーティングとしては Descending Layers (DL) ルー ティング4) を用い，2 本の仮想チャネルを用いた．また， シミュレーション時間は 300,000 クロックとし，はじめの 50,000 クロックはネットワークの状態が安定していない と考えられるため測定しない． 3.1.2 トラフィックパターン アクセスの局所性が FIFO 転送法，一対制限法の性能に 大きく影響するため．本評価においてトラフィックパター ンは重要である．ここでは，典型的なトラフィックパター ンとして Uniform および Matrix Transpose と．NAS Parallel Benchmarks(NPB) 2.3 のトレースを用いた．Uniform, Matrix Transpose におけるパケット長は 8 フリットと 128 フリットを用いた． 一方，NPB 2.3 のトレースは，64 台のホストにより構 成される RHiNET-2 クラスタにおいてトポロジを 2 次元 メッシュに組み，DL ルーティングを実装することで，収 集した5) ．また，NPB の各ベンチマークではクラス S を用 いた．クラス S を用いることにより 1) トレースのサイズ を抑え，2) 実行時間に対する通信時間の割合を高めるこ とができるため，パケットの注入間隔を小さくすることが できる．RHiNET-2 では，最小パケット長が 17 フリット であり，一方，MTU は約 2K Byte である．よって，それ 以上のデータは複数のパケットに分割されて転送されるこ とになる．現実的な時間でシミュレーションするために， 本シミュレーションにおけるスイッチ，ネットワークイン タフェースは RHiNET-2 に比べて簡素化されている5) ．し かし，シミュレーション条件 —DL routing, メッシュ, 2 本 の仮想チャネル，スイッチあたりのホスト数, virtual カッ トスルー方式— はトレースを収集した RHiNET-2 クラス タと同じであるため，シミュレーションにおいて最も重 要なアクセスパターンとパケットの経路は RHiNET-2 ク ラスタと同じである． 3.2 シミュレーション結果 3.2.1 Uniform と Matrix Transpose トラフィック 表 1 と 2 に不規則なトポロジにおけるスループットを 示す．ここで，スループットは単位時間当たりの 1 ホスト の受信フリットの最大値とする. ただし，受信フリットに は，NACK, ACK，および一対制限法における廃棄パケッ トは含まない．“Adaptivity, FIFO, header” は FIFO 転送法 を用いた適応型ルーティングを示し，ACK はパケットの ヘッダを到着後すぐに生成した場合を示す．また，“Adaptivity, couple, packet” は一対制限法においてパケットのテ イルフリットの到着後 ACK を生成した場合を示す．一方， Average throughput under 16-switch irregular topologies [flits/clock/host] Determin,no wait, packet Adaptivity, no wait, packet Adaptivity, FIFO, packet Adaptivity, FIFO, header Adaptivity, couple, packet Adaptivity, couple, header 表2 8-flits length Uniform Matrix 0.113 0.103 0.162 0.159 0.163 0.130 0.163 0.137 0.161 0.153 0.162 0.153 128-flits length Uniform Matrix 0.178 0.169 0.238 0.226 0.238 0.210 0.235 0.212 0.237 0.218 0.236 0.217 Average throughput under 64-switch irregular topologies [flits/clock/host] Determin, no wait, packet Adaptivity, no wait, packet Adaptivity, FIFO, packet Adaptivity, FIFO, header Adaptivity, couple, packet Adaptivity, couple, header 8-flits length Uniform Matrix 0.060 0.039 0.078 0.054 0.077 0.050 0.078 0.049 0.078 0.049 0.078 0.049 128-flits length Uniform Matrix 0.085 0.061 0.118 0.076 0.117 0.072 0.116 0.072 0.118 0.071 0.118 0.072 “Determin, no wait, packet” と “Adaptivity, no wait, packet” は end-to-end フロー制御を用いない固定ルーティングと 適応型ルーティングを示し，ACK はパケットのテイルフ リットの到着後に生成した．表 1 と 2 より，すべての適応 型ルーティングは固定ルーティングに比べて，最大 39% のスループット向上を達成していることが分かる． はじめに，各適応型ルーティングの比較を行うために トラフィックパターンに焦点をあてる．これらの表より， Uniform トラフィックにおいてすべての提案手法は，endto-end フルー制御を用いていない元の適応型ルーティング とほぼ同等のスループットを達成している．これは，Uniform トラフィックではパケットの目的地がランダムに選 択されているため，各ホストにおいて連続するパケット が同一の目的地を取る可能性が極めて低いことが原因と 考えられる．したがって，同一目的地への次のパケットを 送信する前に，ACK が出発地ホストにすでに到着してい る状況といえる．一方，Matrix Transpose トラフィックに おいてすべての提案手法は元の適応型ルーティングに比 べて，スループットが低下していることが分かる．各ホ ストは 1 つのホストのみに対してパケットを送信するた め，Matrix Transpose トラフィックは最も局所性が強いと いえる．よって，Matrix Transpose トラフィックは，両提 案手法とも元の適応型ルーティングに比べ最も性能が低 下する場合といえる．それにも関わらず，すべての提案 手法は，固定ルーティングに比べて高いスループットを 保っている．特に，一対制限法は元の適応型ルーティン グに比べて高々4%のスループット低下に留まっている． 2 番目に，パケット長の影響について検討を行う．一般 的にパケット長が短い場合，ACK の待ち時間が相対的に 大きくなるため，両提案手法のパケット注入量の上限は最 も小さくなる．しかし，表 1 と 2 に示した通り，Uniform トラフィックにおいてはパケット長によらずスループット は同じである．一方で，アクセスの局所性が最大の Matrix Transpose トラフィックでは 8 フリット長のパケットを用 いた場合，FIFO 転送法は元の適応型ルーティングに比べ て，スループットが最大 18%低下していることが分かる． しかし，一対制限法ではあらゆる状況においてスループッ トの低下は高々 4%である．これより，トラフィックパター 4 図 7 より，パケットが時間軸に対して局所的に発生す るため, すべての適応型ルーティングは，固定ルーティン グに比べて最大 41% のピークスループットの向上を達成 した．加えて，ピークレイテンシも 59% 削減した．これ らの結果は，短時間に固定ルーティングにおける容量よ りも多いパケットがネットワークに注入されることを示 している．また，両提案手法とも元の適応型ルーティン グと同じ振舞いをしている．よって，提案手法と適応型 ルーティングの組み合わせは，実アプリケーションにお いて有効といえる． Accepted Traffic [flit/usec/host] 1000 Adaptivity,FIFO, header Adaptivity,couple, packet Adaptivity,couple, header Every adaptivity 4 Determin 3 Every adaptivity 400 200 0 6000 12000 18000 Clock [usec] 24000 図7 0 30000 (a) Throughput 最後に，図 6 に 16 スイッチの 2 次元メッシュにおける 受信トラフィックとレイテンシの関係を示す．レイテンシ は，パケットが出発地ホストにおいて生成されてから，目 的地ホストのネットワークインタフェースに到着するま での時間を示す．本評価では，メッシュの bisection バン ド幅が，しばしば不規則網に比べて小さくなるため，メッ シュのネットワーク容量は不規則網に比べて小さくなる． よって，各アルゴリズムとも不規則網に比べてスループッ トが小さくなっている．図 6 より，元の適応型ルーティン グは，Matrix Transpose トラフィックにおいてネットワー クが飽和した後，受信トラフィックが大幅に低下してい る．これは，元の適応型ルーティングは注入制限をして いない一方，両提案手法は，高負荷時においてスループッ トを増加させる注入制限機構として機能したためと考え られる． これらの結果より，以下が導かれる．1) FIFO 転送法と 一対制限法は，ほとんどの場合，スループットとレイテ ンシに影響しない．2) 目的地ネットワークインタフェー スにおいて ACK を生成するタイミングもほとんど性能に 影響しない．3) トラフィックパターンが極端に強い局所 性を持ち，パケット長が短い場合は，一対制限法が最も 効果的である．その他の場合は，より単純な FIFO 転送法 で十分であるといえる． 3.2.2 NAS Parallel Benchmarks 前節において，極端なトラフィックパターン—局所性の ない場合と局所性が最大の場合—について評価を行った． ここでは，NAS Parallel Benchmarks 2.3 のトレースを用 いた評価結果について議論する．図 7 に 16 プロセッサを 用いた IS benchmark における各アルゴリズムの振舞いを 示す．本トレースは 1 プロセスを 1 プロセッサに割当て ることで収集した．図 7 において縦軸は受信トラフィッ クもしくはレイテンシ，横軸は経過時間を示す．ここで， NPB を用いた評価では受信トラフィック，レイテンシは 240 µ sec 毎に測定した．また，ピークスループットとピー クレイテンシを，単位時間 (240µ sec) における最大受信 トラフィックと最大レイテンシと定義する． 600 2 1 Average ratio of out-of-order packets under irregular topologies [%] 16 switches 64 switches Uniform Matrix Uniform Matrix 8-flits length 0.1 9.2 0.0 5.6 128-flits length 0.2 12.0 0.0 4.4 Determin,no wait, packet Adaptivity,no wait,packet Adaptivity,FIFO, packet Adaptivity,FIFO, header Adaptivity,couple, packet Adaptivity,couple, header Determin 800 5 0 表3 Determin,no wait, packet Adaptivity,no wait,packet Adaptivity,FIFO, packet 6 Latency[usec] ンが極端に強い局所性を持ち，パケット長が短い場合に 限り，一対制限法が効果的である．その他の場合は，ス ループットの低下はほとんど見られないため，より単純 な FIFO 転送法で十分であるといえる． 3 番目に，元の適応型ルーティングにおける Out-of-Order パケット配送について調査する．表 3 はネットワークが飽 和する直前における Out-of-Order で到着したパケットの 割合を示す．表 3 より，Uniform トラフィックにおいては， ほぼすべてのパケットは In-Order で配送されていること が分かる．これは，同一ホスト間のパケットの発生間隔が 十分に大きいためと考えられる．一方，Matrix Transpose トラフィックの場合，最大 12%のパケットが Out-of-Order で配送されていることが分かる．これは，適応型ルーティ ングにおいて Out-of-Order 配送は高いトラフィック負荷 において頻繁に発生するため，In-Order パケット配送を強 制する仕組みが，実際に機能していることを示している． 0 6000 12000 18000 Clock[usec] 24000 30000 (b) Latency Traffic behavior under IS benchmark with 16 processors 表4 Peak throughput and latency under 16 processors [flits/µsec/host],[µsec] IS Determin,no wait, packet Adaptivity, no wait, packet Adaptivity, FIFO, packet Adaptivity, FIFO, header Adaptivity, couple, packet Adaptivity, couple, header Th 3.79 5.18 5.32 5.25 5.18 5.36 Lat 848 386 351 373 386 371 CG Th 4.26 4.44 4.44 4.44 4.44 4.44 SP Lat 65 54 67 65 56 53 Th 5.18 6.32 6.89 6.47 6.32 6.30 Lat 321 203 167 226 203 167 表 4 と 5 は，IS, CG, および SP benchmark の実行結果 を示している．16 プロセッサを用いた IS benchmark と異 なり，CG と SP benchmark は実行時間が大きいため表で 示した．表 4 において “Th” と “Lat” は各々ピークスルー プットとピークレイテンシを表す．FIFO 転送法は，レイ テンシが増加する場合があるが，SP benchmark において， 最大性能を示している．これは，SP benchmark は元の適 応型ルーティングが提供するネットワーク容量よりも多い パケットを生成しているためと考えられる．よって，高い スループットを提供するためには注入制限の仕組みが必 要になり，提案手法がこの役割を担いで高スループットを 達成したといえる．また，IS benchmark は ALL-TO-ALL 関数を頻繁に使用するため，ホスト数を n とすると O(n2 ) のパケットが一度に生成される．したがって，64 プロセッ サの IS benchmark の場合，16 プロセッサの場合に比べて レイテンシが増大したと考えられる． 表5 5 Peak throughput and latency of IS benchmark under 64 processors [flits/µsec/host],[µsec] Throughput Latency Determin,no wait, packet 1.75 2986 Adaptivity, no wait, packet 1.84 2202 1.78 2162 Adaptivity, FIFO, packet Adaptivity, FIFO, header 1.84 2212 Adaptivity, couple, packet 1.82 2202 1.86 2180 Adaptivity, couple, header 600 0 Latency[clocks] 500 400 1,2,3,4,5 300 200 500 4,5 0 300 0.03 0.06 0.09 Accepted traffic[flits/clock/host] 0.12 0 0.03 0.06 0.09 Accepted traffic[flits/clock/host] 0.12 (b) Matrix transpose, 8 flits Sorting buffer size and throughput in 16-switches irregular topologies under uniform traffic with 128-flits length Buffer Size Throughput NACK/ARC [flits/clock/host] [%] 1-packet buf 0.237 0.0 2-packets buf 0.237 0.0 4-packets buf 0.237 0.0 16-packets buf 0.237 0.0 Sorting buffer size and throughput under CG and IS benchmarks 1-pkt buf 2-pkt buf 4-pkt buf 16-pkt buf Th[flits µs/host] 4.44 4.44 4.44 4.44 CG.16 Lat [µs] 57 56 56 56 NACK/ ACK[%] 0.9 0.1 0.0 0.0 0 1200 2 1 0 3 900 600 300 0 0.04 0.08 0.12 Accepted traffic[flits/clock/host] 0.16 0 0.2 0 0.04 0.08 0.12 Accepted traffic[flits/clock/host] 0.16 0.2 (d) Matrix transpose, 128 flits Accepted traffic versus latency under mesh topology 次に，表 6 に NAS Parallel Benchmarks において元の適 応型ルーティングを用いた場合に発生した Out-of-Order パケットの割合を示す．一般的に，トラフィック負荷が低 い場合，パケットの衝突がほとんど起きないため，ほぼ すべてのパケットは In-Order で到着する．表 6 より，こ れらの benchmark の多くにおいてトラフィック負荷が高 い時間帯があることが分かる．これらの benchmark はア クセスの局所性を持つが，その度合は，Matrix Transpose トラフィックの場合に比べて緩いため，すべての提案手法 は元の適応型ルーティングと同等の性能を達成したと考 えられる． 3.2.3 一対制限法におけるソートバッファサイズの影響 本節では，一対制限法におけるネットワークインタフェー スに必要となるソートバッファの大きさについて検討する． Matrix Transpose トラフィックでは，1 つのホストに到 着するパケットの出発地はただ 1 つであるため，ネット ワークインタフェースにおいて 1 パケットを格納するソー トバッファを用意すれば一対制限法の最高性能を引きだ すことができる．よって，ここでは Uniform トラフィック と NAS Parallel Benchmarks について焦点をあてる．表 7 と 8 はソートバッファのサイズに対するスループットと NACK の発生した割合を示している Buffer Size 900 (c) Uniform, 128 flits Average ratio of out-of-order packets under NAS Parallel Benchmarks [%] Benchmark Out-of-order packets ratio IS.S.16 10.7 CG.S.16 50.9 31.0 SP.S.16 IS.S.64 3.0 表8 1,5,4.3,2 300 0 図6 表7 0 1200 5,4 Determin,no wait,packet->0 1800 Adaptivity,no wait,packet->1 Adaptivity,FIFO,packet->2 Adaptivity,FIFO,header->3 1500 Adaptivity,couple,packet->4 Adaptivity,couple,header->5 600 2 100 0 (a) Uniform, 8 flits 表6 1500 3 400 Determin,no wait,packet->0 Adaptivity,no wait,packet->1 Adaptivity,FIFO,packet->2 Adaptivity,FIFO,header->3 Adaptivity,couple,packet->4 Adaptivity,couple,header->5 1800 1 200 100 0 Determin,no wait,packet->0 Adaptivity,no wait,packet->1 Adaptivity,FIFO,packet->2 Adaptivity,FIFO,header->3 Adaptivity,couple,packet->4 Adaptivity,couple,header->5 700 Latency[clocks] 600 Latency[clocks] 800 Determin,no wait,packet->0 Adaptivity,no wait,packet->1 Adaptivity,FIFO,packet->2 Adaptivity,FIFO,header->3 Adaptivity,couple,packet->4 Adaptivity,couple,header->5 700 Latency[clocks] 800 Th[flits µs/host] 1.62 1.64 1.64 1.64 IS.64 Lat [µs] 2223 2212 2212 2212 NACK/ ACK[%] 0.22 0.15 0.15 0.15 NACK は前章で述べた通り，次の 2 つの状況において 6-E 発生しうる: 1) すべてのソートバッファが使用中である; 2) 同一目的地からのパケットがすでにソートバッファに 格納されている．前者は，ソートバッファのサイズを増や すことにより解決される．一方，後者はバッファサイズと は関係が無い．表 7 と 8 より，2 パケットを格納すること ができるソートバッファを各ネットワークインタフェー スに実装することで，一対制限法の最大のネットワーク 性能が得られていることを示している．よって，ソート バッファの大きさが一対制限法を実装する場合の致命的 な問題になることはないと考えられる． 4. 結 論 適応型ルーティングはメッセージパッシングライブラ リが必要とする In-Order パケット配送を保証していない． 本稿では，適応型ルーティングにおいて In-Order パケッ ト配送を強制する 2 つの仕組み—FIFO 転送法と一対制限 法—を提案し，評価した．FIFO 転送法は注入制限を課す ことにより，目的地ホストにおけるパケットのソートを 必要としない．一対制限法は，FIFO 転送法に比べて注入 制限が緩い一方，目的地ホストにおいて少量のソートバッ ファが必要となる．評価結果より，多くの場合，FIFO 転 送法と一対制限法は end-to-end フロー制御を用いていな い元の適応型ルーティングと同等のスループットを示し た．一対制限法は，トラフィックパターンが極端に強い局 所性を持ち，パケット長が短い場合には FIFO 転送法に比 べて効果的である．その他の場合は，より単純な FIFO 転 送法が適しているといえる． 参 考 文 献 1) Scott, S. L. and Horson, G. T.: The Cray T3E network: adaptive routing in a high performance 3D torus, Proceedings of Hot Interconnects IV, pp. 147–156 (1996). 2) W.J.Dally and et al.: Architecture and implementation of the Reliable Router, Proceedings of Hot Interconnects Symposium II (1994). 3) Martinez, J., Flich, J., Robles, A., Lopez, P. and Duato, J.: Supporting Adaptive Routing in IBA Switches, Journal of Systems Architecture, Vol. 49, pp. 441–449 (2004). 4) M.Koibuchi, A.Jouraku, K.Watanabe and H.Amano: Descending Layers Routing: A Deadlock-Free Deterministic Routing using Virtual Channels in System Area Networks with Irregular Topologies, Proceedings of the International Conference on Parallel Processing, pp. 527–536 (2003). 5) 鯉渕 道紘, 渡邊 幸之介, 大塚 智宏, 上樂 明也, 天野 英晴: RHiNET-2 クラスタを用いたデッドロックフリー固定ルー ティングの実機評価, 情報処理学会論文誌コンピューティン グシステム, No. ACS 7 (2004).
© Copyright 2024 ExpyDoc
