ルータおよび並列分散システム
【課題】予測機構を有するルータ装置における予測ミスによって生じたパケットを検出して処理し、ネットワークのレイテンシ、スループットを向上させるルータ装置および並列分散システムを提供する。
【解決手段】予測器(112)で予測された経路に基づき、パケットを少なくとも１つの入力ポートから複数の出力ポートの１つへ転送するようにスイッチ(140)を制御する制御器(110)と、パケットに含まれる目的地関連情報および予測器(112)により予測された経路情報とを比較し、予測が正しいか否かを判定する予測成否判定器(150)とを具え、制御器(110)は、予測が正しくない場合、パケットの宛先アドレスに基づく通常の経路計算処理を行って求めた経路に基づき、パケットを少なくとも１つの入力ポートから複数の出力ポートの１つへ転送するようにスイッチ(140)を制御することを特徴とする。
【解決手段】予測器(112)で予測された経路に基づき、パケットを少なくとも１つの入力ポートから複数の出力ポートの１つへ転送するようにスイッチ(140)を制御する制御器(110)と、パケットに含まれる目的地関連情報および予測器(112)により予測された経路情報とを比較し、予測が正しいか否かを判定する予測成否判定器(150)とを具え、制御器(110)は、予測が正しくない場合、パケットの宛先アドレスに基づく通常の経路計算処理を行って求めた経路に基づき、パケットを少なくとも１つの入力ポートから複数の出力ポートの１つへ転送するようにスイッチ(140)を制御することを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルータおよび並列分散システムに関し、特に、レイテンシ、スループットを向上させたルータおよび並列分散システムに関する。
【背景技術】
【０００２】
オンチップマルチプロセッサ、ＰＣクラスタ、並列計算機などの並列分散システムでは、ネットワークでパケットの破棄が生じないロスレスネットワークが用いられている。このようなロスレスネットワークでは、スイッチング技術として、各ルータがパケット全体を格納できるチャネルバッファを有し、パケット全体をチャネルバッファに受けとってから順に次のルータに渡していくストア・アンド・フォワード（Ｓｔｏｒｅ−ａｎｄ−Ｆｏｒｗａｒｄ：ＳＦ）方式ではなく、ワームホール方式、あるいはバーチャルカットスルー方式を採用し、ルータ間におけるパケットのバッファオーバフローを防いでいる。ワームホール方式では、各ルータが基本的に１フリット分を格納できるチャネルバッファを有し、パケットの先頭フリット（ヘッダフリット）は、送り先のフリットバッファが空いている限り、次々と先のルータへ進んでいく。パケットは複数のルータのチャネルバッファの列にまたがって格納され、全体が、ワーム（いも虫）のように前進する。先頭フリットが進もうとするバッファが、他のパケットによって使われていた場合、パケットの進行はそこでストップし、チャネルバッファが空くのを待って前進を再開する。バーチャルカットスルー方式では、ＳＦ方式と同様に、各ルータはパケット全体を格納することのできるチャネルバッファを有するが、ワームホール方式と同様に、パケットの先頭フリットは、パケット本体の到着を待つことなく次々と先のルータへ進んでいく。パケットの先頭フリットが他のパケットによってブロックされた場合は、パケット本体の転送は停止されずに、先頭フリットのあるルータのチャネルバッファに格納される。ロスレスネットワークでは、パケットの転送を開始する場合、専用のハンドシェーク線を使ってハンドシェークを取るが、転送を開始した後は、クロックに同期して１フリットごとに転送を行っていく。この場合、ワームホール方式では、受信バッファのオーバフローを抑えるために、先頭フリットがブロックされていないか、専用のハードウェアで監視している。一方ＳＦ方式では、パケットを受けとりつつ次のルータには送らないため、受信バッファのオーバフローが生じず、ソフトウェア処理が可能である。
【０００３】
前述したようにロスレスネットワークでは、ネットワーク内においてパケットの廃棄が許されていないため、メッシュトポロジなどにおいてパケット間の循環依存によるデッドロックが生じうる。従って通常は、デッドロックフリー方式、場合によってはデッドロックリカバリー方式を採用して経路を管理し、デッドロックを防いでいる。これらのネットワークのルータは、高クロック、高スループットを実現するために、パケット処理を複数に細分化して、パイプライン方式を採用している。その場合、パケットは複数のクロックサイクルを経て、入力ポートから出力ポートへ転送される。すなわち、パイプライン処理の１ステージは、１クロックサイクル以上かけて処理される。例えば、非特許文献２に記載されている典型的なルータでは、図２０に示す典型的なルータによるパイプライン処理Ｐ２のように、パケット処理を以下のステージに分割している。
（１）入力パケットの入力仮想チャネルでのバッファリング（Ｉｎｐｕｔ Ｂｕｆｆｅｒｒｉｎｇ：ＩＢ）
（２）入力ポートにおける、パケットヘッダからの出力ポート情報の解読、または、ルータの制御ユニットからの出力ポート情報の取得（ルーティング計算、Ｒｏｕｔｉｎｇ Ｃｏｍｐｕｔａｔｉｏｎ：ＲＣ）
（３）出力ポートの設定（出力仮想チャネルの割当て、Ｖｉｒｔｕａｌ−Ｃｈａｎｎｅｌ Ａｌｌｏｃａｔｉｏｎ：ＶＡ）
（４）その出力ポートへのクロスバーの設定（Ｓｗｉｔｃｈ Ａｌｌｏｃａｔｉｏｎ：ＳＡ）
（５）パケット転送（スイッチ転送、Ｓｗｉｔｃｈ Ｔｒａｎｓｆｅｒ：ＳＴ）
【０００４】
従って、入力ポートに入力されたパケットは、５クロックサイクル以上かかって出力ポートへ転送される。最近の並列分散システムのルータでは、これらのステージをさらに細分化し、数段から十数段のパイプラインと、物理的な転送および配送遅延を吸収するためのバッファリングステージなどで処理される場合が多い。また、パケットが他のパケットによりブロックされた場合、このパイプラインは、ＣＰＵでのパイプライン処理のようにストール（停止）される。そして、ブロックされた他のパケットは、占有されたルータ資源が開放され次第、処理が再開される。
【０００５】
ロスレスネットワークは、ルータ間のリンク長がｍｍ〜数ｍオーダと短いため、リンク通過遅延ではなく、パケットのルータ遅延が、ネットワークの転送遅延の支配的な要因となる。従って、このパイプライン処理時間を隠蔽するために、パケットが到着する前に、そのパケットの出力ポートを予測する予測機構を設けて、ルータ内転送の設定をその予測機構の予測に基づいて投機的に実行する手法が、例えば非特許文献２〜４に提案されている。この、予測機構によるパイプライン処理の一例を、図２０の予測機構によるパイプライン処理Ｐ１に示す。予測機構は、入力ポートの通信履歴を参照して次の出力ポートを予測し、予測された出力ポートに利用可能な仮想チャネルがある場合、ＶＡステージを実行する。ＶＡステージまでを前処理しておくことで、パケットのヘッダフリットが入力ポートに到着すると、図の予測機構によるパイプライン処理Ｐ１のように、ＩＢステージと同時にＳＡステージの実行が可能となり、ＲＣおよびＶＡステージの遅延なしにＳＴステージを実行できる。すなわち、この手法では、予測が成功した場合（すなわち、ルータが予測した出力ポートと、パケットの宛先アドレスに対する適切な出力ポートが一致した場合）、パケットが、入力ポートに到着した直後に出力ポートにただちに転送される。この予測に基づくＳＴを、ＰＳＴ（Ｐｒｅｄｉｃｔｉｖｅ Ｓｗｉｔｃｈ Ｔｒａｖｅｒｓａｌ）と呼ぶ。現在、ポートを多数持つ高次元ルータにおけるＳＡステージ、多数のバッファを持つルータにおけるＶＣステージでは、実際には１ステージの処理に多くのサイクルが必要になることから、予測が成功すればパケットを高速に処理することができ、予測機構の効果はさらに大きくなる。
【０００６】
なお、パケットが到着する前に、上述のＲＣ，ＶＡ，ＳＡステージを予め投機的に行う予測処理（ＰＳＴ）は、予測した出力ポートへの（データ）パスが空いている場合にのみ実現することができ、他のパケットにより使用されている出力ポートに対しては、事前の予測に基づくパイプライン処理を実行することはできない。
【０００７】
ロスレスネットワークは、並列科学技術計算のアプリケーションなどの、アクセス局所性の生じる可能性が高い通信トラフィックを扱うものであるため、前述の予測機構によるパケットの出力ポートの予測は、高い精度で当たることが分かっている。従って、予測機構の付加により、各パケットの転送処理が早く進み、パケットがネットワークに滞在する時間が減るため、ヘッド・オブ・ライン（Ｈｅａｄ−Ｏｆ−Ｌｉｎｅ：ＨＯＬ）ブロッキングが減り、パケットの平均レイテンシのみならず、スループットが向上する。
【０００８】
なお、スループットを向上させるためのルータ遅延低減方法の関連研究には、以下のものがある。
＜スペキュレイティブ・ルータ（Ｓｐｅｃｕｌａｔｉｖｅ Ｒｏｕｔｅｒ）＞
Ｄａｌｌｙらは、ルータ内のパケット処理遅延を削減するために、Ｓｐｅｃｕｌａｔｉｖｅ Ｒｏｕｔｅｒを提案している。Ｓｐｅｃｕｌａｔｉｖｅ Ｒｏｕｔｅｒは、ルータのパケットのパイプライン処理の順番を入れ換え、さらに複数のパイプラインステージを１つに統合することで、パイプラインの段数を削減している。しかし、実際には、その制御機構が複雑になるため、一部のパイプラインステージを統合するに留めた設計が多く、予測機構を持つルータのように、生じる遅延をスイッチ内の転送遅延のみに留めてパケット処理を行うことは難しい。
【０００９】
＜ルックアヘッド（Ｌｏｏｋａｈｅａｄ）法＞
スーパーコンピュータＢｌｕｅＧｅｎｅ／Ｌで採用されているルックアヘッド（Ｌｏｏｋａｈｅａｄ）法は、ルータのパイプライン処理の順番を変更し、ＲＣステージを最後に行うものである。これにより、ルータ内においてＲＣステージに複数クロックサイクルが必要になる場合でも、ＲＣステージのオーバヘッドが隠蔽される。すなわちルックアヘッド法では、次のルータにおけるＲＣ処理をそれ以前のルータで行うことで、そのパケットが隣接ルータに到着した後ただちに、ＶＡ，ＳＡ等のステージ処理を行うことができる。このルックアヘッド法も、パイプライン処理の順番を交換することが特徴であり、ＶＡ，ＳＡ等のステージ処理は行うため、予測機構付きルータのように、ＶＡ，ＳＡ等の遅延を完全に隠蔽することは難しい。
【００１０】
＜マッドポストマンスイッチング＞
マッドポストマンスイッチングは、メッシュトポロジにおいて、ソースルーティング実装を用いた次元順ルーティングを対象として、同一方向へパケットを投機的に連続転送するものである。しかしながら、この手法はシリアル転送を対象にしており、ルーティング情報を複数フリットに分割して格納する必要がある。さらに、この手法によるルータは、予測機構を持たず、１つのパケット処理のパイプラインでルータ内でパケットの複製を作成せずに、経路を間違えた場合は必ず異なるルータで破棄させるものである。
【非特許文献１】Ｗ．Ｊ．Ｄａｌｌｙ ａｎｄ Ｂ．Ｔｏｗｌｅｓ：Ｐｒｉｎｃｉｐｌｅｓ ａｎｄ Ｐｒａｃｔｉｃｅｓ ｏｆ Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ Ｎｅｔｗｏｒｋｓ， Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ（２００３）
【非特許文献２】鎌倉正司郎、西村康彦、吉永努、鯉渕道紘：２Ｄトーラスネットワークにおける通信方向予測ルーティング、情報処理学会全国大会（２００６）
【非特許文献３】Ｙｏｓｈｉｎａｇａ．Ｔ，Ｋａｍａｋｕｒａ．Ｓ，ａｎｄ Ｋｏｉｂｕｃｈｉ．Ｍ：Ｐｒｅｄｉｃｔｉｖｅ Ｓｗｉｔｃｈｉｎｇ ｉｎ ２Ｄ Ｔｏｒｕｓ Ｒｏｕｔｅｒｓ， Ｐｒｅｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｉｎｎｏｖａｔｉｖｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｆｕｔｕｒｅ Ｇｅｎｅｒａｔｉｏｎ Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ Ｐｒｏｃｅｓｓｏｒｓ ａｎｄ Ｓｙｓｔｅｍｓ （ＩＷＩＡ），（２００６）
【非特許文献４】鎌倉正司郎、吉永努、鯉渕道紘：２Ｄトーラスネットワークにおける動的予測ルーティング、情報処理学会技術研究報告［計算機アーキテクチャ］，（２００６）
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ただし、現状の予測機構では以下のような問題点があり、予測機構の効果を低減させている。
（ａ）予測処理によって転送されたパケットは、予測の成否が判明するまで出力ポートに留まる。よって、予測ミスが判明したときには、既にパケットはルータ内の間違った出力ポートに転送されてしまっており、このミスパケットは、ルータ内におけるクロスバスイッチや出力ポート、論理チャネル等のルータ資源を消費／占有し、他のパケットの通過を阻害する。これによって、ネットワーク資源の使用効率が落り、他のパケットの遅延が増大する。
（ｂ）パケットは、正しい出力ポートに転送された場合でも、予測の成否が判明するまで（ＲＣステージの処理が終了するまで）、当該出力ポートに留まり、隣接ルータへ送出されない。従って、ルータ全体のルーティングテーブルに対してパケットのエントリ数が多い等の理由で、ＲＣステージの処理に時間がかかる場合には、出力ポートにおいてパケットヘッダの待ち時間（遅延）が生じる。例えば、ＲＣステージに１０サイクル、ＶＡ，ＳＡ，ＳＴステージに各１サイクルかかる場合、予測が成功しても、ルータ遅延は１３サイクルから１０サイクルに短縮されるのみであり、ヘッダフリットの通過遅延の削減効果が小さくなってしまう。
（ｃ）予測が不成功である場合は、予測を行わない通常のパイプライン処理を行うため、既存のルータと同様の遅延が生じる。
まとめると、上述の問題点（ａ）は、他のパケットをブロックして、ルータのスループット、ひいてはシステム全体のスループットを低下させる可能性があることを示し、（ｂ）、（ｃ）は、パケットのルータ通過遅延の削減効果が限定される場合があることをを示している。
【００１２】
上述した課題について、図を用いて説明する。図１８は、従来の並列分散システムにおいて用いられている、予測機構を有するルータの構成を示す概略的なブロック図である。ルータ２００は、入力ポートＩＮ１，ＩＮ２を含む入力部１２０、出力ポートＯＵＴ１，ＯＵＴ２を含む出力部１３０、制御部１１０、ならびにクロスバユニット（クロスバスイッチ）１４０を具える既存の典型的なルータにおいて、制御部１１０に予測部１１２を付加した構成となっている。このルータ２００において、到着したパケットは、上述したように大きく５つのステージに分けられ、パイプライン方式で処理される。この、ルータ２００内でのパケットの処理を、図１９、図２０を用いて説明する。図１９は、各ステージでのパケットの流れ、図２０は、上述したように、予測機構によるパイプライン処理Ｐ１および典型的なパイプライン（ここでは５ステージとする）処理Ｐ２を示している。まず、パケットが入力ポートＩＮ１に到着すると、入力チャネル（仮想チャネル）にパケットがバッファリングされる（ＩＢ）。入力ポートＩＮ１においてパケットのヘッダから出力ポート情報が解読（デコード）され、出力候補となるポートが計算される（ＲＣ、ステップＳ３０）。なお、出力ポート情報は制御部１１０が取得してもよい。このＲＣステージと同時に、制御部１１０は、矢印Ａ３０のように、予測部１１２が予め予測した出力ポートＯＵＴ２へ、ＩＢステージで入力チャネルに格納されているパケットを転送する（ＰＳＴ、ステップＳ３１）。なお予測部１１２による予測には、既知の予測アルゴリズムを用いることができ、それらについては後述する。ＲＣステージが終了して予測が成功している場合には、パケットの先頭部分（ヘッダフリット）は、１サイクルで出力ポートに転送される。しかしながら、予測が外れた場合（予測ミスの場合）は、ＲＣステージに続いて、矢印Ａ３１のように、正しい出力ポート（図の例では、出力ポートＯＵＴ１）の設定（ＶＡ、ステップＳ３２）、正しい出力ポートＯＵＴ１へのクロスバスイッチの設定（ＳＡ、ステップＳ３３）、パケットの転送（ＳＴ、ステップＳ３４）の一連の処理を経て、パケットが出力ポートＯＵＴ１へ転送される。なお、図１８において制御部は入力部と別になっているが、入力部の中に統合されているルータアーキテクチャにおいてもパケット処理は同様であり、以下に述べる問題点も同様に生じる。その問題にも、本発明の解決法を同様に適用することができる。
さらに、図２０において典型的なパイプライン処理Ｐ２における処理順番、各ステージの処理内容が異なるルータアーキテクチャにおいてもパケット処理に複数ステージ必要な場合は、同様の問題点が生じる。その場合にも、本発明の解決法を同様に適用することができる。
【００１３】
このルータ２００の問題点を再度述べる。まず、入力ポートにおいて、次に到着するパケットの出力ポートの予測ミスが生じた場合、ルータ２００内でのパケットのヘッダフリットの通過遅延が、予測が成功した場合に比べて、ＶＡ，ＳＡ，ＳＴの処理の分だけ大きくなる。さらに、ＲＣステージの期間、予測ミスのパケットは、予測した出力ポート（この例ではＯＵＴ２）を占有して、他のパケットの通過を阻害するため、ネットワークの使用効率、すなわちスループットが低下し、遅延が大きくなる。また、正しい出力ポートに再送するためにパケットヘッダから一部分をルータ内の仮想チャネルに格納する必要があり、ルータ資源を浪費する。さらに、パケットのルーティング計算処理（ＲＣ、ステップＳ３０）時間が大きい場合（図２０ではＲＣを１サイクルで示したが、これが数サイクルかかる場合）は、ルータにおいて予測成否の判定に時間がかかる。そのため、予測が成功した場合においても、隣接ルータへパケットを送出するまでに待ち時間（遅延）が生じる。なお、予測機構ルータは、予測が成功した場合、入力ポートから出力ポートへの転送のみでルータを通過するが、ルックアヘッドルーティング法のようにＲＣステージの順番を変更しても、そのＲＣ処理遅延が大きい場合には、遅延を完全に隠蔽することはできない。
【００１４】
よって、本発明の目的は、上述の問題を克服し、予測機構を有するルータ装置における予測ミスによって生じたパケットを検出して処理し、ルータ資源を浪費させず、結果としてネットワークのスループットを向上させる技法（ルータ装置およびそのルータを含む並列分散システム）を提供することである。
【課題を解決するための手段】
【００１５】
上述した諸課題を解決すべく、第１の発明によるルータは、
パケットを受ける前にパケットの経路を予測する予測器と、前記パケットを受ける少なくとも１つの入力ポートと、前記パケットを受け、隣接するノード（ルータなど）に転送する複数の出力ポートと、前記少なくとも１つの入力ポートで受けたパケットが転送されるべき出力ポートを設定するスイッチ（クロスバスイッチなど）とを持つルータであって、
前記予測器で予測された経路に基づき、前記パケットを前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送するように前記スイッチを制御する制御器と、
前記入力ポートで受けたパケットに含まれる当該パケットの目的地関連情報、および、前記予測器により予測された経路情報とを比較し、前記予測器による予測が正しいか否かを判定する予測成否判定器とを具え、
前記制御器は、
前記予測成否判定器により予測が正しくないと判定された場合、前記予測された経路を用いずに、前記入力ポートで受けたパケットの宛先アドレスに基づく通常の経路計算処理（例えば、経路計算処理のステージおよびその他のステージを含むパイプライン処理）を行って、前記通常の経路計算処理で求めた経路に基づき、前記パケットを前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送するように前記スイッチを制御する、
ことを特徴とする。
【００１６】
第２の発明によるルータは、
前記制御器が、
前記予測器により予測された経路に基づき、前記パケットの経路を設定して１ステージで前記パケットを隣接するノードに転送するように前記スイッチおよび前記複数の出力ポートの１つを制御し、
前記予測された経路に基づき設定された経路と、通常の経路計算処理で求めた経路とが異なる場合（即ち、予測が外れた場合）には、前記通常の経路計算処理で求めた経路に基づいて、前記パケットの転送処理をさらに行うように前記スイッチを制御する、
ことを特徴とする。
【００１７】
さらに、第３の発明によるルータは、
パケットを受ける前にパケットの経路を予測する予測器と、
前記パケットを受ける少なくとも１つの入力ポートと、前記パケットを受け、隣接するノード（ルータなど）に転送する複数の出力ポートと、前記少なくとも１つの入力ポートで受けたパケットが転送されるべき出力ポートを設定するスイッチ（クロスバスイッチなど）とを持つルータであって、
前記予測器により予測された経路に基づき、前記パケットが前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送されるように前記パケットの経路を仮想チャネルに設定して、１ステージで前記パケットを隣接するノードに転送するように前記スイッチおよび前記複数の出力ポートの１つを制御し、前記予測された経路に基づき設定された経路と、通常の経路計算処理で求めた経路とが異なる場合（即ち、予測が外れた場合）には、前記通常の経路計算処理で求めた経路に基づいて、前記パケットの転送処理をさらに行うように前記スイッチを制御する制御器、
を具えることを特徴とする。
【００１８】
第４の発明によるルータは、
前記制御器が、
特定の入力ポートから特定の出力ポートに転送されると予測されたパケットに対しては、予測の成否に関わらず、前記予測された経路に基づき設定された経路に基づいて前記パケットの転送処理を行うように前記スイッチを制御する、
ことを特徴とする。
【００１９】
また、本発明の別の実施態様によるルータは、
パケットを受ける前にパケットの経路を予測する予測器と、
前記パケットを受ける少なくとも１つの入力ポートと、前記パケットを受け、隣接するノード（ルータなど）に転送する複数の出力ポートと、前記少なくとも１つの入力ポートで受けたパケットが転送されるべき出力ポートを設定するスイッチ（クロスバスイッチなど）とを持つルータであって、
前記予測器により予測された経路に基づき、前記パケットが前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送されるように前記パケットの経路を設定して、１ステージで前記パケットを隣接するノードに転送するように前記スイッチおよび前記複数の出力ポートの１つを制御し、前記予測された経路に基づき設定された経路と、通常の経路計算処理で求めた経路とが異なる場合（即ち、予測が外れた場合）には、前記通常の経路計算処理で求めた経路に基づいて、前記パケットの転送処理をさらに行うように前記スイッチを制御する制御器、
を具えることを特徴とする。
【００２０】
上述したように本発明の解決手段を装置として説明してきたが、本発明はこれらの装置を含むシステムとしても実現し得るものであり、本発明の範囲にはこれらも包含されるものと理解されたい。例えば、本発明を実現した並列分散システムは、
前記ルータを少なくとも１つ含む並列分散システムであって、
前記ルータから送出された（０または１以上のノードを経た）パケットを受け、当該パケットの目的地までの経路が存在しない場合は（即ち、予測ミスで転送されたパケットであるとき）、当該パケットを廃棄する少なくとも１つの予測ミス検出ルータ、
を具えることを特徴とする。
【００２１】
さらに、本発明を実現した別の並列分散システムは、ネットワークトポロジにおいて、ハミルトニアン閉路、またはすべてのプロセッサノードを接続しているルータを通過する閉路上に前記特定の入力ポートおよび特定の出力ポートがあるように配置し、前記ルータから送出されたパケットを受け、当該パケットの目的地までの経路が存在しない場合は、当該パケットを廃棄する少なくとも１つの予測ミス検出ルータを具える、
ことを特徴とする。
【発明の効果】
【００２２】
上述の発明により、予測機構を有するルータ装置におけるルータ資源を浪費せず、ネットワークのスループットを向上させることができる。
【発明を実施するための最良の形態】
【００２３】
以降、諸図面を参照しながら、本発明の実施態様を詳細に説明する。図１に、本発明によるルータの概略的なブロック図を示す。ルータ１００は、上述した予測機構を具える既存のルータ２００に、新たに予測成否判定部１５０を具えるものである。予測成否判定部１５０は、目的地情報格納部ＤＩＲ、予測結果格納部ＰＴ、および比較器ＣＭＰを具える。制御部１１０、予測部１１２、入力部１２０、出力部１３０、およびクロスバスイッチ１４０は、ルータ２００と同様であり、同一の符号を付す。
【００２４】
（第１の実施の形態）
第１の実施の形態では、予測成否判定部１５０は、パケットのヘッダに含まれる目的地関連情報（目的地に関する数ビットの情報であり、以降、「ヒントビット」と称する。）に基づき、予測部１１２が予め予測した出力ポートが、パケットの目的地に対して適切なポートであるか否かを、パケットの到着時に数ビットの比較器を用いて高速に判定する。ヒントビットに格納される目的地に関する情報としては、例えば目的地の方向を示す情報とすることができ、パケットの出発地で挿入される。このヒントビットの具体例を以下に示す。図４は、２次元メッシュトポロジのネットワークを示す図である。図４では、それぞれＲ０〜Ｒ１５の符号を付した１６個のルータが、各コンピュータノードとともに示してある。図のような２次元メッシュトポロジでは、出発地において、目的地は北東（ＮＥ）、東南（ＳＥ）、南西（ＳＷ）および北西（ＮＷ）の４象限に大雑把に大別される。従ってこれらを識別すべく、２ビットのヒントビットをパケットヘッダに挿入すればよい。図示しないが、ツリー系のトポロジの場合は、パケットのルートの通過の有無を１ビットのヒントビットとして用いることができる。
【００２５】
以下に、本発明による予測成否判定部１５０を具えるルータのパケット処理を、図を用いて説明する。図３は、予測が不成功の場合のパイプライン処理を示す図であり、予測機構による処理Ｐ１および典型的なパイプライン処理Ｐ２を示している。図２は、図３のパイプライン処理に対応するルータ１００におけるパケットの流れを示す図である。図２に示すように、ルータ１００で受信したパケットヘッダに含まれるヒントビットは、矢印Ａ１０のように予測成否判定部１５０に送られ、目的地情報格納部ＤＩＲに格納される。予測成否判定部１５０では、比較器ＣＭＰが、予測結果格納部ＰＴに格納されている予測部１１２が予め予測した結果と、目的地情報格納部ＤＩＲに格納されているヒントビットとを比較して、予測部１１２の予測が適当か否か、すなわち、ヒントビットの目的地の方向に、予測した出力ポートの方向が含まれているか否かを判定する（ステップＳ１０）。予測部１１２の予測が適当でない場合、すなわち、比較器ＣＭＰからの判定結果がＰＳＴ不可であった場合（ステップＳ１１）、制御部１１０は、矢印Ａ１１に示すようにパケットを転送する。すなわち、入力ポートＩＮ１にてＲＣステージを実行し（ステップＳ１２）、取得した出力ポートの情報に基づいて出力ポートを割り当てるＶＡステージを実行し（ステップＳ１３）、クロスバスイッチ１４０の設定（ＳＡステージ、ステップＳ１４）、パケット転送（ＳＴステージ、ステップＳ１５）を実行する。
【００２６】
図３に示すように、予測成否判定部１５０における予測結果の判定は、ＰＳＴおよびＲＣステージの実行前、すなわち、パイプライン処理Ｐ１およびＰ２の開始前に行われて、予測が不成功の場合にはＰＳＴが実行されないため、出力ポートの占有や仮想チャネル割当などの、「外れるであろう予測に基づく無駄な動作」が実行されず、ネットワーク資源の浪費を防ぐことができる。ここで、図２０の、予測成否判定部１５０を具えない既存の予測機構によるルータのパイプライン処理Ｐ１と、図３とを比較し、予測成否判定部１５０の効果を述べる。いま、図ではＲＣステージを１サイクルで示してあるが、このＲＣステージに複数サイクル必要である場合、ＲＣステージが終了するまで、図２０の場合、予測機構による処理Ｐ１では、ＰＳＴによって出力ポートが占有されてしまう。一方、本発明では、予測正否判定部を設けることによって、予測が外れたことがＰＳＴの実行前に判明するため、予測機構による処理Ｐ１、すなわち、予測による無駄な動作（ＰＳＴ、出力ポート占有、仮想チャネル割当など）を行わずに済み、誤って予測された出力ポートへの他のパケットの通過をブロックすることがなくなり、結果としてルータ全体としてのスループットが向上するものである。
【００２７】
図４を用いて、本発明によるルータ１００を含むネットワークでのパケットの流れを説明する。図において、パケットはノードＮＳを有するルータＲ９を出発して、ノードＮＤを有するルータＲ０を目的地とする。ルータＲ９を出発するパケットのパケットヘッダには、ノードＮＳにて、目的地が北西（ＮＷ）方向であるという情報がヒントビットとして挿入される。ルータＲ８では、予め予測部１１２によって、出力方向が南方向であると予測されていたとする。しかしながら、ルータＲ９から矢印Ｄ１０のようにルータＲ８に進んだパケットは、予測成否判定部１５０によって北西（ＮＷ）方向のヒントビットに基づき、ルータ８の予測部１１２の予測が不成功であると判定される。その後、ルータＲ８での通常のＲＣ，ＶＡ，ＳＡおよびＳＴステージにより、パケットは矢印Ｄ１２のようにルータＲ４の方向に送出される。ルータＲ８にてＰＳＴステージを行わないため、例えばルータＲ８からルータＲ１２へ矢印Ｄ１１のように進む他のパケットに対して、出力ポートを使用させることができる。
【００２８】
なお、予測が成功した場合は、そのパケットはルータ内をＰＳＴの１ステージで移動していくため、ルックアヘッド法によるルーティングのように、ルーティング情報（すなわちヒントビット）を各ルータで更新していくことは難しい。従って、出発地において挿入されたヒントビットは、経由する他のルータにて更新しなくてもよい。なお、予測成否判定部１５０における比較は、数ビットの単純な比較で非常に軽量であるため、ＲＣステージに含めた実装も可能であり、また、ＲＣステージの前に転送遅延やタイミング制御を行うためのバッファリングのサイクルを用いているルータの場合は、このバッファリングサイクルにおいて実施することができる。また、予測成否判定部１５０は、ネットワークを構成するルータの一部、またはネットワークを構成する全てのルータに設置してもよい。
【００２９】
（第２の実施の形態）
第２の実施の形態では、ルータ１００または２００の制御部１１０は、予測部１１２による予測の成否の判定前、すなわち、制御部１１０は、ＲＣステージが終了する前に、予測部１１２による予測に基づいてＰＳＴステージにおいて転送された出力ポートから、パケットを隣接ルータへ送出する。なお、従来の予測機構を具えるルータでは、ＲＣステージの終了後にパケットが転送される構成である。これは、予測機構によるパケット転送の影響をルータ内にとどめ、パケットのルーティング経路に影響を与えないためである。一方、本第２の実施の形態では以下に述べる通り、予測機構がパケットのルーティング経路に影響を与えうるが、パケットの目的地への経路の存在は常に保証される。本実施の形態では、入力ポートで受信したパケットは、ＲＣステージが終了して、予測が不成功（予測ミス）であった場合、通常のＲＣ，ＶＡ，ＳＡおよびＳＴステージによるパイプライン処理を通して、正しい出力ポートへ別途転送される。これにより、ＲＣステージの処理時間が大きい場合、すなわち予測成否の判定を含むＲＣステージに複数のクロックサイクルが必要となる場合に、予測成功時のルータ遅延を、既存の予測機構を具えるルータと比べて削減することができる。
【００３０】
この機構を具えたルータでは、予測が成功した場合には１ステージ、かつ、出力ポートにおいて遅延することなくパケットを転送すること可能となる。従って、当該ルータは、１ステージにかかる処理時間（クロックサイクル）でパケットを転送することができる。そこで、このような機構を具えたルータを、本明細書では、１ステージルータと呼ぶこととする。なお、１ステージルータには、第１の実施の形態で述べた予測成否判定部１５０を含めても、含めなくともよい。すなわち、１ステージルータとしては、図１８のルータ２００または図１のルータ１００において、制御部１１０に上述した機構を持たせたものとすることができる。なお、予測ミスによってネットワークに生じた予測ミスパケットをルーティングする場合、予測ミスパケットの存在は予め考慮されていないため、通常のパイプライン処理におけるＲＣステージにおいて、適切な出力ポートが見つからない場合が起こり得る。この場合は、そのパケットの処理はＲＣステージで強制的に終了させてもよい。さらに、１ステージルータには隣接ルータとの接続に用いられているポートの中から特定の入力ポートおよび出力ポートを設けて、この特定の入力ポートから特定の出力ポートに転送されると予測されたパケットに対しては、ＰＳＴステージのみを行う。すなわち、特定の出力ポートに転送されたパケットに対しては、ＲＣ，ＶＡ，ＳＡおよびＳＴステージ全てを行わない。さらに、図４のように、この１ステージルータに計算ノード（即ち、当該ルータに結合されたプロセッサ）が接続されている場合、図２１に示したように、この特定の入力ポート間から計算ノード乃至ノード１６０が接続されている出力ポートへのクロスバスイッチ１４０等の、ルータ内部のデータパスをバイパスする専用のリンク１７０を設ける。そして、特定の入力ポートから特定の出力ポートにＰＳＴステージを用いて転送されたパケットを、計算ノード１６０へもこのバイパスする専用のリンク１７０を通って送出させるようにする。このバイパス処理により、特定の入力ポートに到着した、この計算ノード宛のパケットが、予測ミスにより間違って特定の出力ポートに転送された場合でも、この計算ノードにパケットが配送される。その他のパケットは、このバイパスする専用のリンクを使った転送を行わない。なお、図２１においては、予測成否判定器１５０を具えるルータを示しているが、前述したように、１ステージルータには、予測成否判定部１５０を含めても、含めなくともよい。
【００３１】
第２の実施の形態による１ステージルータを含む並列分散システムでは、予測ミスパケットがネットワーク上に生じ得る。デッドロックフリー方式によるルーティングのアルゴリズムでは、ルータにおけるパケットの転送方向に制限があり、この制限によって、予測ミスパケットは目的地まで到達できなくなる可能性がある。従って、ネットワーク上の適当な位置に、検出ルータを配置する。この検出ルータは、受信したパケットが目的地まで到達できるか否かを判定して、１つ以上前のルータにおける予測ミスにより目的地までの経路が存在しなくなった場合に、その予測ミスパケットを破棄するものである。検出ルータにおける目的地までの経路の検出は、ターンモデル（Ｔｕｒｎ Ｍｏｄｅｌ）（例えば、C. J. Glass and L. M. Ni, “The Turn Model for Adaptive Routing, Proceedings of International Symposium on Computer Architecture,” pp. 278-287, 1992を参照されたい。）等の並列分散システムにおいて一般的に使われているＮ×Ｎ→Ｃ型のデッドロックフリールーティングアルゴリズムの場合、目的地と現在地の位置を比較することで、簡単に識別することができる。なお、検出ルータとしては、上述した条件を満足する機能を有すれば、アーキテクチャに関する制限はなく、既存の予測機構を具えるルータまたはスペキュレイティブ・ルータ等にすることができる。
【００３２】
１ステージルータおよび検出ルータは、以下で述べるようにネットワーク上に配置して、パケットのネットワーク遅延を削減する。まず、規則性を有するネットワークトポロジの場合は、予測ミスパケットを廃棄できるように検出ルータをネットワーク上に配置し、その他のルータは、全て１ステージルータとする。ただし、１ステージルータは、ハミルトニアン閉路、またはすべてのプロセッサノードを接続しているルータを通過する閉路上に特定の出力ポートがあるように配置する。任意のネットワークトポロジの場合においても、以下のアルゴリズムにより検出ルータを配置し、その他のルータは１ステージルータとすることが可能である。
ステップ１：各ルータをノードとして、ノード集合Ｎ、チャネル集合Ｃから構成されるネットワークグラフＧ（Ｎ，Ｃ）を作成する。
ステップ２：Ｇ（Ｎ，Ｃ）において、各ノードから、各目的地まで、予測ミスにより転送されうる隣接ノードを訪問する。
ステップ３：目的地に到達するまで、到達先のノードにて予測ミスにより転送されうる出力ポートが存在する限り、深さ優先探索により訪問を続ける。
ステップ４：訪問先のノードにて、転送されうる出力ポートが存在しない場合、そのノードを検出ルータとする。そして、直前のノードに戻り、ステップ３に従って探索を続ける。
【００３３】
図５に、ハミルトニアン閉路を含めない場合の、１ステージルータおよび検出ルータの簡単な配置例を示す。図において、検出ルータは、Ｒ０〜Ｒ３，Ｒ７，Ｒ１１およびＲ１５であり、それ以外のルータは１ステージルータである。パケットは、ノードＮＳを有するルータＲ９を出発して、ノードＮＤを有するルータＲ６を目的地とする。２次元トーラスにおける次元順ルーティングの場合、出発地のルータＲ９（ノードＮＳ）から、目的地のルータＲ６（ノードＮＳ）へのパケット転送時に、ルータＲ９から矢印Ｄ２０で示す方向に進む予測ミス１、矢印Ｄ２１で示す方向に進む予測ミス２の、最大２個のミスパケットが生じ得るが、これらは検出ルータＲ１およびＲ１１にてそれぞれ廃棄される。
【００３４】
次に、図６に、ハミルトニアン閉路を含む場合の配置例を示す。図には、ハミルトニアン閉路Ｄ３０、上述したアルゴリズムに基づいて配置された検出ルータＲ０，Ｒ５，Ｒ１０およびＲ１５が示されている。また、図に示すように、ハミルトニアン閉路D３０上に、黒点で示す１ステージルータの特定の出力ポートが配置されている。図６では、複数の仮想チャネルおよびターンモデルルーティングアルゴリズムを用いている。すなわち、デッドロックフリーを保証するために、パケットの経路切り換えの禁止パターン（禁止ターン）を行う場合は、仮想チャネル番号を増加させ、ハミルトニアン閉路Ｄ３０またはすべてのルータを通過する閉路上の１ステージルータの出力ポート（特定の出力ポート）を通過するパケットは、ルータでの予測の成否を確認せずに、ＰＳＴステージで転送された出力ポートからそのまま転送される。しかしながら、すべてのルータを通過するハミルトニアン閉路の特性により、目的地に到着することが保証される。このことを、図６を用いて説明する。図において、パケットはルータＲ５（ノードＮＳ）を出発地、ルータＲ１１（ノードＮＤ）を目的地としており、最短経路は矢印Ｄ３１で示す経路となる。ここで、図のルータＲ６の予測部が南方向を予測した場合、南方向はＰＳＴのみで転送される出力ポートであるため、パケットはルータＲ６から矢印Ｄ３２の方向に送出される。よって図に示すように、パケットの転送経路が矢印Ｄ３２に変更され、パケットのホップ数は増加するが、ハミルトニアン閉路上に特定の出力ポートを配置していることにより、目的地へのパケットの配送が補償される。この場合、ホップ数が増加するデメリットに比べて、ネットワーク遅延の支配的な要素であるルータ内の遅延を削減した効果の方が大きいため、結果として、パケットのネットワーク転送遅延を低減することができる。
【００３５】
なお、ルータでの予測において、デッドロックフリールーティングアルゴリズムを満たす出力ポートの中から１つのポートが選択される。よって、予測成功の成否に関わらず、（ハミルトニアン閉路を含めた）隣接ルータへ転送されるパケットは、デッドロックフリー転送の条件を満たすことになり、本ネットワークはデッドロックフリーである。また、デッドロックフリーを保証しつつ、目的地への経路を保証するようにルーティングを設定する場合、最短経路を迂回できる回数は制限される。そのため、目的地へのパケットの転送が保証され、本ネットワークではライブロックは生じない。さらに、予測ミスにより生じる、デッドロックフリーは満たすが目的地までの経路を失ったパケットは、検出ルータにより廃棄され、予測ミスが発生したルータにおいて、別途正しい方向へパケットが複製・転送される。よって、目的地へのパケットの配送が保証される。
【００３６】
これ以降に、本発明による予測成否判定部を具えるルータを配置した並列分散システム、および、上述したアルゴリズムに基づき１ステージルータおよび検出ルータを配置した並列分散システムをシミュレーションした結果を示す。シミュレータとしては、非特許文献１に記載のシミュレータブックシム（Ｂｏｏｋｓｉｍ）を、予測機構に対応させたものを用いている。ネットワークは、８×８，１６×１６の２次元トーラスとして構成し、デッドロックフリールーティングアルゴリズムには次元順ルーティング（ＤＯＲ）を用いている。その他のシミュレーション条件は、以下の通りである。
ネットワーク：ｋ−ａｒｙ ２−ｃｕｂｅ （ｋ＝８，１６，３２）
予測アルゴリズム：静的直進予測アルゴリズムＳＳ（入力パケットが常に同一次元を直進すると予測する。例えば、NORTHポートに入力されたパケットはSOUTHポートに出力されると予測し、WESTポートに入力されたパケットはEASTポートに出力されると予測する。）、直前ポート予測アルゴリズムＬＰ（入力パケットが１つ前のパケットと同一の出力ポートを選択すると予測する。）、およびパターンマッチ予測アルゴリズムＳＰＭ（パターンマッチングに基づくユニバーサル予測アルゴリズムに、系列の長さ制限等の制約条件を付け、過去の通信履歴から繰り返しパターンを検索することによって、並列プログラムが有する通信の規則性を抽出する。）の３種類とする。
【００３７】
通信パターン：ユニフォームランダム、ビット列逆順およびＮＡＳ並列ベンチマークのＬＵ分解（サイズＷ）で生じるＭＰＩメッセージトレースから作成した３種類とする。
パケット長：ユニフォーム、ビット列逆順において８フリットとする。ＬＵ分解で生じるトラフィックはアプリケーションメッセージに応じた可変長とする。
スイッチング：バーチャルカットスルー方式とする。
ルータ間ケーブル遅延：２サイクルとする。
ルーティング：Ｘ−Ｙ次元順ルーティング（ＤＯＲ）とする。
仮想チャネル（ＶＣ）数：物理チャネル当たり２本のＶＣ（各８フリット分）を実装し、各次元ともデータライン（ｄａｔｅｌｉｎｅ）を越えないパケットはＶＣ０を使用し、データラインを越えるパケットはＶＣ１を使用する。
パイプライン：予測に基づかない場合は５ステージ、予測に基づく場合は２ステージで動作する。ただし、ＲＣは３サイクル、他のステージは１サイクルで動作すると仮定する（１フリットのＳＴによる転送は１サイクルとする。）。
特定の出力ポートの配置：Ｘ，Ｙの各次元の特定の出力ポートを、それぞれｋ＝２だけ離れた２つの行と列に配置する。
【００３８】
ＳＳの実験条件：予測値取得の遅延は特に考慮せず、潜在的に全パケットが予測スイッチング（ＰＳＴ）可能と仮定する。
ＬＰの実験条件：入力ポート毎の通信履歴長は、直前のパケットの出力ポートを記憶する１×３ビットとし、予測処理における遅延は発生せず、全パケットについて通信履歴の値を参照可能とする。
ＳＰＭの実験条件：パラメータα＝１とし、入力ポート毎の通信履歴長は５１２×３ビットとする。また、予測器はルータ当たり１つとし、入力ポートまたは注入ポートが通信履歴を更新してから、当該ポートに対する次パケットの出力ポートを予測するのに、４サイクルかかると仮定する。他の入力ポートの予測処理待ちの間に到着したパケットに対してはＰＳＴを行わないものとする。
データ収集方法：ユニフォームトラフィック、ビット列逆順トラフィックではネットワークをウォームアップした後、約１２，０００パケットを受信するまでのスループット、平均遅延を測定する。ＬＵ分解ではアプリケーションの開始から終了までに生じた通信メッセージのについて同様に測定する。
【００３９】
図７〜図１２に、本発明の第１の実施の形態における予測成否判定部の有無によるネットワークの特性への影響を、上述の条件において測定した結果を示す。図における（ａ）、（ｂ）は、各予測アルゴリズムＳＳ，ＬＰ，ＳＰＭについて、平均遅延（レイテンシ）およびスループットをそれぞれシミュレーションした結果である。図７〜図９、図１０〜図１２は、それぞれ、ネットワークのサイズを１６−ａｒｙ ２−ｃｕｂｅとした場合、および３２−ａｒｙ ２−ｃｕｂｅとした場合である。各図において、横軸はネットワークへのパケット注入負荷である。なお、ネットワークの性能は、平均遅延が小さいものほど、またスループットが大きいものほど優れたものとなる。これらの図より、パケットヘッダにヒントビットを、および、ルータに予測成否判定部を具えることにより、いずれの場合においても、スループット、レイテンシが改善され、ネットワークが飽和していないパケット注入負荷において、レイテンシを最大で７％削減できていることが分かる。これらの結果からも、本発明による予測成否判定部が、並列分散システムのネットワークにおいて有効であることが分かる。
【００４０】
図１３〜図１７に、本発明による１ステージルータと検出ルータの配置方法（予測ミスペナルティ削減方法）に基づいて、上述の条件で構成したネットワークへのパケットの注入負荷を変化させた場合の、各予測アルゴリズムによるパケット平均遅延をシミュレーションした結果を示す。各図は、通信パターンおよびネットワークの大きさが異なっている。各図において、横軸はネットワークへのパケット注入負荷、縦軸はパケット平均遅延であり、破線で示すｎｏｒｍａｌは、予測機構（予測部１１２）のない既存のルータでネットワークを構成した場合をシミュレーションしたものである。なお、ＲＣステージの実行に多数のクロックサイクルが必要な場合は、上述したように、既存の予測機構を有するルータでの予測による遅延削減効果は極めて小さくなる。つまり、予測機構を有するルータの性能は、予測機構のないルータ（ｎｏｒｍａｌ）の性能に近づく。
【００４１】
図１３および図１４は、ユニフォームランダム通信における、それぞれ１６−ａｒｙ ２−ｃｕｂｅ、３２−ａｒｙ ２−ｃｕｂｅでのシミュレーション結果である。図より、本発明による１ステージルータと検出ルータの配置方法は、いずれの予測アルゴリズムを用いた場合においても、既存のルータ（予測機構のないルータ）でネットワークを構成した場合（凡例ｎｏｒｍａｌ）に対して平均遅延が低下し、ひいてはネットワーク全体のスループットが向上している。
【００４２】
図１５および図１６は、ビット逆順通信における、それぞれ１６−ａｒｙ ２−ｃｕｂｅ、３２−ａｒｙ ２−ｃｕｂｅでのシミュレーション結果である。この通信パターンは、２進数で表した送信元ノード番地から宛先ノードに、パケットの送信を繰り返すもので、通信の規則性を有する。図１５の１６−ａｒｙ ２−ｃｕｂｅのパケット注入負荷０．０５では、ＳＳの平均遅延がｎｏｒｍａｌよりも大きな値となっているが、これは、ＳＳの予測ヒット率が低く、ビット逆順通信が高負荷時にホットスポットを形成する通信パターンであるため、予測ミスパケットが輻輳を悪化させたことによる。しかしながら、全体として、本発明による１ステージルータと検出ルータの配置方法を採用した並列分散システムの性能が向上していることが分かる。
【００４３】
図１７は、８−ａｒｙ ２−ｃｕｂｅにＬＵ分解で発生する通信パターンを与えた場合のシミュレーション結果を示す。この通信パターンは、全て隣接ノード間通信で構成され、パケット平均遅延は、ＳＰＭの場合、ＰＳＴステージによるパイプライン処理で転送する最短時間に近くなる。これら上述のシミュレーション結果からも、本発明による１ステージルータと検出ルータの配置方法の有効性を確認することができる。
【００４４】
本発明を諸図面や実施例に基づき説明してきたが、当業者であれば本開示に基づき種々の変形や修正を行うことが容易であることに注意されたい。従って、これらの変形や修正は本発明の範囲に含まれることに留意されたい。例えば、各手段、各部、各ステップなどに含まれる機能などは論理的に矛盾しないように再配置可能であり、複数の手段やステップなどを１つに組み合わせたり、あるいは分割したりすることが可能である。
【図面の簡単な説明】
【００４５】
【図１】本発明に係るルータ装置の概略的なブロック図である。
【図２】本発明に係るルータ装置におけるパケットの流れを示す図である。
【図３】本発明に係るパケットのパイプライン処理を示す図である。
【図４】２次元メッシュトポロジのネットワークを示す図である。
【図５】ハミルトニアン閉路を含めない場合の、１ステージルータおよび検出ルータの簡単な配置例を示す図である。
【図６】ハミルトニアン閉路を含む場合の１ステージルータおよび検出ルータの簡単な配置例を示す図である。
【図７ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＳでの平均遅延のシミュレーション結果である。
【図７ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＳでのスループットのシミュレーション結果である。
【図８ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＬＰでの平均遅延のシミュレーション結果である。
【図８ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＬＰでのスループットのシミュレーション結果である。
【図９ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＰＭでの平均遅延のシミュレーション結果である。
【図９ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＰＭでのスループットのシミュレーション結果である。
【図１０ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＳでの平均遅延のシミュレーション結果である。
【図１０ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＳでのスループットのシミュレーション結果である。
【図１１ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＬＰでの平均遅延のシミュレーション結果である。
【図１１ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＬＰでのスループットのシミュレーション結果である。
【図１２ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＰＭでの平均遅延のシミュレーション結果である。
【図１２ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＰＭでのスループットのシミュレーション結果である。
【図１３】本発明の第３の実施の形態における並列分散ネットワークの、ユニフォームランダム通信における１６−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１４】本発明の第３の実施の形態における並列分散ネットワークの、ユニフォームランダム通信における３２−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１５】本発明の第３の実施の形態における並列分散ネットワークの、ビット逆順通信における１６−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１６】本発明の第３の実施の形態における並列分散ネットワークの、ビット逆順通信における３２−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１７】本発明の第３の実施の形態における並列分散ネットワークの、ユニフォームランダム通信における８−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１８】従来の並列分散システムにおいて用いられている、予測機構を有するルータの構成を示す概略的なブロック図である。
【図１９】ルータ内部でのパケットの流れを示す図である。
【図２０】予測機構および典型的なパイプライン処理を示す図である。
【図２１】図４の２次元メッシュトポロジにおける１ステージルータの一例を示す図である。
【符号の説明】
【００４６】
１００ ルータ
１１０ 制御部
１１２ 予測部
１２０ 入力部
１３０ 出力部
１４０ クロスバスイッチ
１５０ 予測成否判定部
１６０ ノード
１７０ ルータ内部のデータパスをバイパスする専用のリンク
２００ ルータ
Ａ１０，Ａ１１ 矢印
Ａ３０，Ａ３１ 矢印
ＣＭＰ 比較器
Ｐ１ 予測機構によるパイプライン処理
Ｐ２ 典型的なパイプライン処理
Ｄ１０〜Ｄ１２ 矢印
Ｄ３０ ハミルトニアン閉路
Ｄ３１ 最短経路を示す矢印
Ｄ３２ 変更後の経路を示す矢印
ＤＩＲ 目的地情報格納部
ＩＮ１，ＩＮ２ 入力ポート
ＯＵＴ１，ＯＵＴ２ 出力ポート
ＮＤ 目的地ノード
ＮＳ 出発地ノード
ＰＴ 予測結果格納部
Ｒ０〜Ｒ１５ ルータ
【技術分野】
【０００１】
本発明は、ルータおよび並列分散システムに関し、特に、レイテンシ、スループットを向上させたルータおよび並列分散システムに関する。
【背景技術】
【０００２】
オンチップマルチプロセッサ、ＰＣクラスタ、並列計算機などの並列分散システムでは、ネットワークでパケットの破棄が生じないロスレスネットワークが用いられている。このようなロスレスネットワークでは、スイッチング技術として、各ルータがパケット全体を格納できるチャネルバッファを有し、パケット全体をチャネルバッファに受けとってから順に次のルータに渡していくストア・アンド・フォワード（Ｓｔｏｒｅ−ａｎｄ−Ｆｏｒｗａｒｄ：ＳＦ）方式ではなく、ワームホール方式、あるいはバーチャルカットスルー方式を採用し、ルータ間におけるパケットのバッファオーバフローを防いでいる。ワームホール方式では、各ルータが基本的に１フリット分を格納できるチャネルバッファを有し、パケットの先頭フリット（ヘッダフリット）は、送り先のフリットバッファが空いている限り、次々と先のルータへ進んでいく。パケットは複数のルータのチャネルバッファの列にまたがって格納され、全体が、ワーム（いも虫）のように前進する。先頭フリットが進もうとするバッファが、他のパケットによって使われていた場合、パケットの進行はそこでストップし、チャネルバッファが空くのを待って前進を再開する。バーチャルカットスルー方式では、ＳＦ方式と同様に、各ルータはパケット全体を格納することのできるチャネルバッファを有するが、ワームホール方式と同様に、パケットの先頭フリットは、パケット本体の到着を待つことなく次々と先のルータへ進んでいく。パケットの先頭フリットが他のパケットによってブロックされた場合は、パケット本体の転送は停止されずに、先頭フリットのあるルータのチャネルバッファに格納される。ロスレスネットワークでは、パケットの転送を開始する場合、専用のハンドシェーク線を使ってハンドシェークを取るが、転送を開始した後は、クロックに同期して１フリットごとに転送を行っていく。この場合、ワームホール方式では、受信バッファのオーバフローを抑えるために、先頭フリットがブロックされていないか、専用のハードウェアで監視している。一方ＳＦ方式では、パケットを受けとりつつ次のルータには送らないため、受信バッファのオーバフローが生じず、ソフトウェア処理が可能である。
【０００３】
前述したようにロスレスネットワークでは、ネットワーク内においてパケットの廃棄が許されていないため、メッシュトポロジなどにおいてパケット間の循環依存によるデッドロックが生じうる。従って通常は、デッドロックフリー方式、場合によってはデッドロックリカバリー方式を採用して経路を管理し、デッドロックを防いでいる。これらのネットワークのルータは、高クロック、高スループットを実現するために、パケット処理を複数に細分化して、パイプライン方式を採用している。その場合、パケットは複数のクロックサイクルを経て、入力ポートから出力ポートへ転送される。すなわち、パイプライン処理の１ステージは、１クロックサイクル以上かけて処理される。例えば、非特許文献２に記載されている典型的なルータでは、図２０に示す典型的なルータによるパイプライン処理Ｐ２のように、パケット処理を以下のステージに分割している。
（１）入力パケットの入力仮想チャネルでのバッファリング（Ｉｎｐｕｔ Ｂｕｆｆｅｒｒｉｎｇ：ＩＢ）
（２）入力ポートにおける、パケットヘッダからの出力ポート情報の解読、または、ルータの制御ユニットからの出力ポート情報の取得（ルーティング計算、Ｒｏｕｔｉｎｇ Ｃｏｍｐｕｔａｔｉｏｎ：ＲＣ）
（３）出力ポートの設定（出力仮想チャネルの割当て、Ｖｉｒｔｕａｌ−Ｃｈａｎｎｅｌ Ａｌｌｏｃａｔｉｏｎ：ＶＡ）
（４）その出力ポートへのクロスバーの設定（Ｓｗｉｔｃｈ Ａｌｌｏｃａｔｉｏｎ：ＳＡ）
（５）パケット転送（スイッチ転送、Ｓｗｉｔｃｈ Ｔｒａｎｓｆｅｒ：ＳＴ）
【０００４】
従って、入力ポートに入力されたパケットは、５クロックサイクル以上かかって出力ポートへ転送される。最近の並列分散システムのルータでは、これらのステージをさらに細分化し、数段から十数段のパイプラインと、物理的な転送および配送遅延を吸収するためのバッファリングステージなどで処理される場合が多い。また、パケットが他のパケットによりブロックされた場合、このパイプラインは、ＣＰＵでのパイプライン処理のようにストール（停止）される。そして、ブロックされた他のパケットは、占有されたルータ資源が開放され次第、処理が再開される。
【０００５】
ロスレスネットワークは、ルータ間のリンク長がｍｍ〜数ｍオーダと短いため、リンク通過遅延ではなく、パケットのルータ遅延が、ネットワークの転送遅延の支配的な要因となる。従って、このパイプライン処理時間を隠蔽するために、パケットが到着する前に、そのパケットの出力ポートを予測する予測機構を設けて、ルータ内転送の設定をその予測機構の予測に基づいて投機的に実行する手法が、例えば非特許文献２〜４に提案されている。この、予測機構によるパイプライン処理の一例を、図２０の予測機構によるパイプライン処理Ｐ１に示す。予測機構は、入力ポートの通信履歴を参照して次の出力ポートを予測し、予測された出力ポートに利用可能な仮想チャネルがある場合、ＶＡステージを実行する。ＶＡステージまでを前処理しておくことで、パケットのヘッダフリットが入力ポートに到着すると、図の予測機構によるパイプライン処理Ｐ１のように、ＩＢステージと同時にＳＡステージの実行が可能となり、ＲＣおよびＶＡステージの遅延なしにＳＴステージを実行できる。すなわち、この手法では、予測が成功した場合（すなわち、ルータが予測した出力ポートと、パケットの宛先アドレスに対する適切な出力ポートが一致した場合）、パケットが、入力ポートに到着した直後に出力ポートにただちに転送される。この予測に基づくＳＴを、ＰＳＴ（Ｐｒｅｄｉｃｔｉｖｅ Ｓｗｉｔｃｈ Ｔｒａｖｅｒｓａｌ）と呼ぶ。現在、ポートを多数持つ高次元ルータにおけるＳＡステージ、多数のバッファを持つルータにおけるＶＣステージでは、実際には１ステージの処理に多くのサイクルが必要になることから、予測が成功すればパケットを高速に処理することができ、予測機構の効果はさらに大きくなる。
【０００６】
なお、パケットが到着する前に、上述のＲＣ，ＶＡ，ＳＡステージを予め投機的に行う予測処理（ＰＳＴ）は、予測した出力ポートへの（データ）パスが空いている場合にのみ実現することができ、他のパケットにより使用されている出力ポートに対しては、事前の予測に基づくパイプライン処理を実行することはできない。
【０００７】
ロスレスネットワークは、並列科学技術計算のアプリケーションなどの、アクセス局所性の生じる可能性が高い通信トラフィックを扱うものであるため、前述の予測機構によるパケットの出力ポートの予測は、高い精度で当たることが分かっている。従って、予測機構の付加により、各パケットの転送処理が早く進み、パケットがネットワークに滞在する時間が減るため、ヘッド・オブ・ライン（Ｈｅａｄ−Ｏｆ−Ｌｉｎｅ：ＨＯＬ）ブロッキングが減り、パケットの平均レイテンシのみならず、スループットが向上する。
【０００８】
なお、スループットを向上させるためのルータ遅延低減方法の関連研究には、以下のものがある。
＜スペキュレイティブ・ルータ（Ｓｐｅｃｕｌａｔｉｖｅ Ｒｏｕｔｅｒ）＞
Ｄａｌｌｙらは、ルータ内のパケット処理遅延を削減するために、Ｓｐｅｃｕｌａｔｉｖｅ Ｒｏｕｔｅｒを提案している。Ｓｐｅｃｕｌａｔｉｖｅ Ｒｏｕｔｅｒは、ルータのパケットのパイプライン処理の順番を入れ換え、さらに複数のパイプラインステージを１つに統合することで、パイプラインの段数を削減している。しかし、実際には、その制御機構が複雑になるため、一部のパイプラインステージを統合するに留めた設計が多く、予測機構を持つルータのように、生じる遅延をスイッチ内の転送遅延のみに留めてパケット処理を行うことは難しい。
【０００９】
＜ルックアヘッド（Ｌｏｏｋａｈｅａｄ）法＞
スーパーコンピュータＢｌｕｅＧｅｎｅ／Ｌで採用されているルックアヘッド（Ｌｏｏｋａｈｅａｄ）法は、ルータのパイプライン処理の順番を変更し、ＲＣステージを最後に行うものである。これにより、ルータ内においてＲＣステージに複数クロックサイクルが必要になる場合でも、ＲＣステージのオーバヘッドが隠蔽される。すなわちルックアヘッド法では、次のルータにおけるＲＣ処理をそれ以前のルータで行うことで、そのパケットが隣接ルータに到着した後ただちに、ＶＡ，ＳＡ等のステージ処理を行うことができる。このルックアヘッド法も、パイプライン処理の順番を交換することが特徴であり、ＶＡ，ＳＡ等のステージ処理は行うため、予測機構付きルータのように、ＶＡ，ＳＡ等の遅延を完全に隠蔽することは難しい。
【００１０】
＜マッドポストマンスイッチング＞
マッドポストマンスイッチングは、メッシュトポロジにおいて、ソースルーティング実装を用いた次元順ルーティングを対象として、同一方向へパケットを投機的に連続転送するものである。しかしながら、この手法はシリアル転送を対象にしており、ルーティング情報を複数フリットに分割して格納する必要がある。さらに、この手法によるルータは、予測機構を持たず、１つのパケット処理のパイプラインでルータ内でパケットの複製を作成せずに、経路を間違えた場合は必ず異なるルータで破棄させるものである。
【非特許文献１】Ｗ．Ｊ．Ｄａｌｌｙ ａｎｄ Ｂ．Ｔｏｗｌｅｓ：Ｐｒｉｎｃｉｐｌｅｓ ａｎｄ Ｐｒａｃｔｉｃｅｓ ｏｆ Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ Ｎｅｔｗｏｒｋｓ， Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ（２００３）
【非特許文献２】鎌倉正司郎、西村康彦、吉永努、鯉渕道紘：２Ｄトーラスネットワークにおける通信方向予測ルーティング、情報処理学会全国大会（２００６）
【非特許文献３】Ｙｏｓｈｉｎａｇａ．Ｔ，Ｋａｍａｋｕｒａ．Ｓ，ａｎｄ Ｋｏｉｂｕｃｈｉ．Ｍ：Ｐｒｅｄｉｃｔｉｖｅ Ｓｗｉｔｃｈｉｎｇ ｉｎ ２Ｄ Ｔｏｒｕｓ Ｒｏｕｔｅｒｓ， Ｐｒｅｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｉｎｎｏｖａｔｉｖｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｆｕｔｕｒｅ Ｇｅｎｅｒａｔｉｏｎ Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ Ｐｒｏｃｅｓｓｏｒｓ ａｎｄ Ｓｙｓｔｅｍｓ （ＩＷＩＡ），（２００６）
【非特許文献４】鎌倉正司郎、吉永努、鯉渕道紘：２Ｄトーラスネットワークにおける動的予測ルーティング、情報処理学会技術研究報告［計算機アーキテクチャ］，（２００６）
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ただし、現状の予測機構では以下のような問題点があり、予測機構の効果を低減させている。
（ａ）予測処理によって転送されたパケットは、予測の成否が判明するまで出力ポートに留まる。よって、予測ミスが判明したときには、既にパケットはルータ内の間違った出力ポートに転送されてしまっており、このミスパケットは、ルータ内におけるクロスバスイッチや出力ポート、論理チャネル等のルータ資源を消費／占有し、他のパケットの通過を阻害する。これによって、ネットワーク資源の使用効率が落り、他のパケットの遅延が増大する。
（ｂ）パケットは、正しい出力ポートに転送された場合でも、予測の成否が判明するまで（ＲＣステージの処理が終了するまで）、当該出力ポートに留まり、隣接ルータへ送出されない。従って、ルータ全体のルーティングテーブルに対してパケットのエントリ数が多い等の理由で、ＲＣステージの処理に時間がかかる場合には、出力ポートにおいてパケットヘッダの待ち時間（遅延）が生じる。例えば、ＲＣステージに１０サイクル、ＶＡ，ＳＡ，ＳＴステージに各１サイクルかかる場合、予測が成功しても、ルータ遅延は１３サイクルから１０サイクルに短縮されるのみであり、ヘッダフリットの通過遅延の削減効果が小さくなってしまう。
（ｃ）予測が不成功である場合は、予測を行わない通常のパイプライン処理を行うため、既存のルータと同様の遅延が生じる。
まとめると、上述の問題点（ａ）は、他のパケットをブロックして、ルータのスループット、ひいてはシステム全体のスループットを低下させる可能性があることを示し、（ｂ）、（ｃ）は、パケットのルータ通過遅延の削減効果が限定される場合があることをを示している。
【００１２】
上述した課題について、図を用いて説明する。図１８は、従来の並列分散システムにおいて用いられている、予測機構を有するルータの構成を示す概略的なブロック図である。ルータ２００は、入力ポートＩＮ１，ＩＮ２を含む入力部１２０、出力ポートＯＵＴ１，ＯＵＴ２を含む出力部１３０、制御部１１０、ならびにクロスバユニット（クロスバスイッチ）１４０を具える既存の典型的なルータにおいて、制御部１１０に予測部１１２を付加した構成となっている。このルータ２００において、到着したパケットは、上述したように大きく５つのステージに分けられ、パイプライン方式で処理される。この、ルータ２００内でのパケットの処理を、図１９、図２０を用いて説明する。図１９は、各ステージでのパケットの流れ、図２０は、上述したように、予測機構によるパイプライン処理Ｐ１および典型的なパイプライン（ここでは５ステージとする）処理Ｐ２を示している。まず、パケットが入力ポートＩＮ１に到着すると、入力チャネル（仮想チャネル）にパケットがバッファリングされる（ＩＢ）。入力ポートＩＮ１においてパケットのヘッダから出力ポート情報が解読（デコード）され、出力候補となるポートが計算される（ＲＣ、ステップＳ３０）。なお、出力ポート情報は制御部１１０が取得してもよい。このＲＣステージと同時に、制御部１１０は、矢印Ａ３０のように、予測部１１２が予め予測した出力ポートＯＵＴ２へ、ＩＢステージで入力チャネルに格納されているパケットを転送する（ＰＳＴ、ステップＳ３１）。なお予測部１１２による予測には、既知の予測アルゴリズムを用いることができ、それらについては後述する。ＲＣステージが終了して予測が成功している場合には、パケットの先頭部分（ヘッダフリット）は、１サイクルで出力ポートに転送される。しかしながら、予測が外れた場合（予測ミスの場合）は、ＲＣステージに続いて、矢印Ａ３１のように、正しい出力ポート（図の例では、出力ポートＯＵＴ１）の設定（ＶＡ、ステップＳ３２）、正しい出力ポートＯＵＴ１へのクロスバスイッチの設定（ＳＡ、ステップＳ３３）、パケットの転送（ＳＴ、ステップＳ３４）の一連の処理を経て、パケットが出力ポートＯＵＴ１へ転送される。なお、図１８において制御部は入力部と別になっているが、入力部の中に統合されているルータアーキテクチャにおいてもパケット処理は同様であり、以下に述べる問題点も同様に生じる。その問題にも、本発明の解決法を同様に適用することができる。
さらに、図２０において典型的なパイプライン処理Ｐ２における処理順番、各ステージの処理内容が異なるルータアーキテクチャにおいてもパケット処理に複数ステージ必要な場合は、同様の問題点が生じる。その場合にも、本発明の解決法を同様に適用することができる。
【００１３】
このルータ２００の問題点を再度述べる。まず、入力ポートにおいて、次に到着するパケットの出力ポートの予測ミスが生じた場合、ルータ２００内でのパケットのヘッダフリットの通過遅延が、予測が成功した場合に比べて、ＶＡ，ＳＡ，ＳＴの処理の分だけ大きくなる。さらに、ＲＣステージの期間、予測ミスのパケットは、予測した出力ポート（この例ではＯＵＴ２）を占有して、他のパケットの通過を阻害するため、ネットワークの使用効率、すなわちスループットが低下し、遅延が大きくなる。また、正しい出力ポートに再送するためにパケットヘッダから一部分をルータ内の仮想チャネルに格納する必要があり、ルータ資源を浪費する。さらに、パケットのルーティング計算処理（ＲＣ、ステップＳ３０）時間が大きい場合（図２０ではＲＣを１サイクルで示したが、これが数サイクルかかる場合）は、ルータにおいて予測成否の判定に時間がかかる。そのため、予測が成功した場合においても、隣接ルータへパケットを送出するまでに待ち時間（遅延）が生じる。なお、予測機構ルータは、予測が成功した場合、入力ポートから出力ポートへの転送のみでルータを通過するが、ルックアヘッドルーティング法のようにＲＣステージの順番を変更しても、そのＲＣ処理遅延が大きい場合には、遅延を完全に隠蔽することはできない。
【００１４】
よって、本発明の目的は、上述の問題を克服し、予測機構を有するルータ装置における予測ミスによって生じたパケットを検出して処理し、ルータ資源を浪費させず、結果としてネットワークのスループットを向上させる技法（ルータ装置およびそのルータを含む並列分散システム）を提供することである。
【課題を解決するための手段】
【００１５】
上述した諸課題を解決すべく、第１の発明によるルータは、
パケットを受ける前にパケットの経路を予測する予測器と、前記パケットを受ける少なくとも１つの入力ポートと、前記パケットを受け、隣接するノード（ルータなど）に転送する複数の出力ポートと、前記少なくとも１つの入力ポートで受けたパケットが転送されるべき出力ポートを設定するスイッチ（クロスバスイッチなど）とを持つルータであって、
前記予測器で予測された経路に基づき、前記パケットを前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送するように前記スイッチを制御する制御器と、
前記入力ポートで受けたパケットに含まれる当該パケットの目的地関連情報、および、前記予測器により予測された経路情報とを比較し、前記予測器による予測が正しいか否かを判定する予測成否判定器とを具え、
前記制御器は、
前記予測成否判定器により予測が正しくないと判定された場合、前記予測された経路を用いずに、前記入力ポートで受けたパケットの宛先アドレスに基づく通常の経路計算処理（例えば、経路計算処理のステージおよびその他のステージを含むパイプライン処理）を行って、前記通常の経路計算処理で求めた経路に基づき、前記パケットを前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送するように前記スイッチを制御する、
ことを特徴とする。
【００１６】
第２の発明によるルータは、
前記制御器が、
前記予測器により予測された経路に基づき、前記パケットの経路を設定して１ステージで前記パケットを隣接するノードに転送するように前記スイッチおよび前記複数の出力ポートの１つを制御し、
前記予測された経路に基づき設定された経路と、通常の経路計算処理で求めた経路とが異なる場合（即ち、予測が外れた場合）には、前記通常の経路計算処理で求めた経路に基づいて、前記パケットの転送処理をさらに行うように前記スイッチを制御する、
ことを特徴とする。
【００１７】
さらに、第３の発明によるルータは、
パケットを受ける前にパケットの経路を予測する予測器と、
前記パケットを受ける少なくとも１つの入力ポートと、前記パケットを受け、隣接するノード（ルータなど）に転送する複数の出力ポートと、前記少なくとも１つの入力ポートで受けたパケットが転送されるべき出力ポートを設定するスイッチ（クロスバスイッチなど）とを持つルータであって、
前記予測器により予測された経路に基づき、前記パケットが前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送されるように前記パケットの経路を仮想チャネルに設定して、１ステージで前記パケットを隣接するノードに転送するように前記スイッチおよび前記複数の出力ポートの１つを制御し、前記予測された経路に基づき設定された経路と、通常の経路計算処理で求めた経路とが異なる場合（即ち、予測が外れた場合）には、前記通常の経路計算処理で求めた経路に基づいて、前記パケットの転送処理をさらに行うように前記スイッチを制御する制御器、
を具えることを特徴とする。
【００１８】
第４の発明によるルータは、
前記制御器が、
特定の入力ポートから特定の出力ポートに転送されると予測されたパケットに対しては、予測の成否に関わらず、前記予測された経路に基づき設定された経路に基づいて前記パケットの転送処理を行うように前記スイッチを制御する、
ことを特徴とする。
【００１９】
また、本発明の別の実施態様によるルータは、
パケットを受ける前にパケットの経路を予測する予測器と、
前記パケットを受ける少なくとも１つの入力ポートと、前記パケットを受け、隣接するノード（ルータなど）に転送する複数の出力ポートと、前記少なくとも１つの入力ポートで受けたパケットが転送されるべき出力ポートを設定するスイッチ（クロスバスイッチなど）とを持つルータであって、
前記予測器により予測された経路に基づき、前記パケットが前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送されるように前記パケットの経路を設定して、１ステージで前記パケットを隣接するノードに転送するように前記スイッチおよび前記複数の出力ポートの１つを制御し、前記予測された経路に基づき設定された経路と、通常の経路計算処理で求めた経路とが異なる場合（即ち、予測が外れた場合）には、前記通常の経路計算処理で求めた経路に基づいて、前記パケットの転送処理をさらに行うように前記スイッチを制御する制御器、
を具えることを特徴とする。
【００２０】
上述したように本発明の解決手段を装置として説明してきたが、本発明はこれらの装置を含むシステムとしても実現し得るものであり、本発明の範囲にはこれらも包含されるものと理解されたい。例えば、本発明を実現した並列分散システムは、
前記ルータを少なくとも１つ含む並列分散システムであって、
前記ルータから送出された（０または１以上のノードを経た）パケットを受け、当該パケットの目的地までの経路が存在しない場合は（即ち、予測ミスで転送されたパケットであるとき）、当該パケットを廃棄する少なくとも１つの予測ミス検出ルータ、
を具えることを特徴とする。
【００２１】
さらに、本発明を実現した別の並列分散システムは、ネットワークトポロジにおいて、ハミルトニアン閉路、またはすべてのプロセッサノードを接続しているルータを通過する閉路上に前記特定の入力ポートおよび特定の出力ポートがあるように配置し、前記ルータから送出されたパケットを受け、当該パケットの目的地までの経路が存在しない場合は、当該パケットを廃棄する少なくとも１つの予測ミス検出ルータを具える、
ことを特徴とする。
【発明の効果】
【００２２】
上述の発明により、予測機構を有するルータ装置におけるルータ資源を浪費せず、ネットワークのスループットを向上させることができる。
【発明を実施するための最良の形態】
【００２３】
以降、諸図面を参照しながら、本発明の実施態様を詳細に説明する。図１に、本発明によるルータの概略的なブロック図を示す。ルータ１００は、上述した予測機構を具える既存のルータ２００に、新たに予測成否判定部１５０を具えるものである。予測成否判定部１５０は、目的地情報格納部ＤＩＲ、予測結果格納部ＰＴ、および比較器ＣＭＰを具える。制御部１１０、予測部１１２、入力部１２０、出力部１３０、およびクロスバスイッチ１４０は、ルータ２００と同様であり、同一の符号を付す。
【００２４】
（第１の実施の形態）
第１の実施の形態では、予測成否判定部１５０は、パケットのヘッダに含まれる目的地関連情報（目的地に関する数ビットの情報であり、以降、「ヒントビット」と称する。）に基づき、予測部１１２が予め予測した出力ポートが、パケットの目的地に対して適切なポートであるか否かを、パケットの到着時に数ビットの比較器を用いて高速に判定する。ヒントビットに格納される目的地に関する情報としては、例えば目的地の方向を示す情報とすることができ、パケットの出発地で挿入される。このヒントビットの具体例を以下に示す。図４は、２次元メッシュトポロジのネットワークを示す図である。図４では、それぞれＲ０〜Ｒ１５の符号を付した１６個のルータが、各コンピュータノードとともに示してある。図のような２次元メッシュトポロジでは、出発地において、目的地は北東（ＮＥ）、東南（ＳＥ）、南西（ＳＷ）および北西（ＮＷ）の４象限に大雑把に大別される。従ってこれらを識別すべく、２ビットのヒントビットをパケットヘッダに挿入すればよい。図示しないが、ツリー系のトポロジの場合は、パケットのルートの通過の有無を１ビットのヒントビットとして用いることができる。
【００２５】
以下に、本発明による予測成否判定部１５０を具えるルータのパケット処理を、図を用いて説明する。図３は、予測が不成功の場合のパイプライン処理を示す図であり、予測機構による処理Ｐ１および典型的なパイプライン処理Ｐ２を示している。図２は、図３のパイプライン処理に対応するルータ１００におけるパケットの流れを示す図である。図２に示すように、ルータ１００で受信したパケットヘッダに含まれるヒントビットは、矢印Ａ１０のように予測成否判定部１５０に送られ、目的地情報格納部ＤＩＲに格納される。予測成否判定部１５０では、比較器ＣＭＰが、予測結果格納部ＰＴに格納されている予測部１１２が予め予測した結果と、目的地情報格納部ＤＩＲに格納されているヒントビットとを比較して、予測部１１２の予測が適当か否か、すなわち、ヒントビットの目的地の方向に、予測した出力ポートの方向が含まれているか否かを判定する（ステップＳ１０）。予測部１１２の予測が適当でない場合、すなわち、比較器ＣＭＰからの判定結果がＰＳＴ不可であった場合（ステップＳ１１）、制御部１１０は、矢印Ａ１１に示すようにパケットを転送する。すなわち、入力ポートＩＮ１にてＲＣステージを実行し（ステップＳ１２）、取得した出力ポートの情報に基づいて出力ポートを割り当てるＶＡステージを実行し（ステップＳ１３）、クロスバスイッチ１４０の設定（ＳＡステージ、ステップＳ１４）、パケット転送（ＳＴステージ、ステップＳ１５）を実行する。
【００２６】
図３に示すように、予測成否判定部１５０における予測結果の判定は、ＰＳＴおよびＲＣステージの実行前、すなわち、パイプライン処理Ｐ１およびＰ２の開始前に行われて、予測が不成功の場合にはＰＳＴが実行されないため、出力ポートの占有や仮想チャネル割当などの、「外れるであろう予測に基づく無駄な動作」が実行されず、ネットワーク資源の浪費を防ぐことができる。ここで、図２０の、予測成否判定部１５０を具えない既存の予測機構によるルータのパイプライン処理Ｐ１と、図３とを比較し、予測成否判定部１５０の効果を述べる。いま、図ではＲＣステージを１サイクルで示してあるが、このＲＣステージに複数サイクル必要である場合、ＲＣステージが終了するまで、図２０の場合、予測機構による処理Ｐ１では、ＰＳＴによって出力ポートが占有されてしまう。一方、本発明では、予測正否判定部を設けることによって、予測が外れたことがＰＳＴの実行前に判明するため、予測機構による処理Ｐ１、すなわち、予測による無駄な動作（ＰＳＴ、出力ポート占有、仮想チャネル割当など）を行わずに済み、誤って予測された出力ポートへの他のパケットの通過をブロックすることがなくなり、結果としてルータ全体としてのスループットが向上するものである。
【００２７】
図４を用いて、本発明によるルータ１００を含むネットワークでのパケットの流れを説明する。図において、パケットはノードＮＳを有するルータＲ９を出発して、ノードＮＤを有するルータＲ０を目的地とする。ルータＲ９を出発するパケットのパケットヘッダには、ノードＮＳにて、目的地が北西（ＮＷ）方向であるという情報がヒントビットとして挿入される。ルータＲ８では、予め予測部１１２によって、出力方向が南方向であると予測されていたとする。しかしながら、ルータＲ９から矢印Ｄ１０のようにルータＲ８に進んだパケットは、予測成否判定部１５０によって北西（ＮＷ）方向のヒントビットに基づき、ルータ８の予測部１１２の予測が不成功であると判定される。その後、ルータＲ８での通常のＲＣ，ＶＡ，ＳＡおよびＳＴステージにより、パケットは矢印Ｄ１２のようにルータＲ４の方向に送出される。ルータＲ８にてＰＳＴステージを行わないため、例えばルータＲ８からルータＲ１２へ矢印Ｄ１１のように進む他のパケットに対して、出力ポートを使用させることができる。
【００２８】
なお、予測が成功した場合は、そのパケットはルータ内をＰＳＴの１ステージで移動していくため、ルックアヘッド法によるルーティングのように、ルーティング情報（すなわちヒントビット）を各ルータで更新していくことは難しい。従って、出発地において挿入されたヒントビットは、経由する他のルータにて更新しなくてもよい。なお、予測成否判定部１５０における比較は、数ビットの単純な比較で非常に軽量であるため、ＲＣステージに含めた実装も可能であり、また、ＲＣステージの前に転送遅延やタイミング制御を行うためのバッファリングのサイクルを用いているルータの場合は、このバッファリングサイクルにおいて実施することができる。また、予測成否判定部１５０は、ネットワークを構成するルータの一部、またはネットワークを構成する全てのルータに設置してもよい。
【００２９】
（第２の実施の形態）
第２の実施の形態では、ルータ１００または２００の制御部１１０は、予測部１１２による予測の成否の判定前、すなわち、制御部１１０は、ＲＣステージが終了する前に、予測部１１２による予測に基づいてＰＳＴステージにおいて転送された出力ポートから、パケットを隣接ルータへ送出する。なお、従来の予測機構を具えるルータでは、ＲＣステージの終了後にパケットが転送される構成である。これは、予測機構によるパケット転送の影響をルータ内にとどめ、パケットのルーティング経路に影響を与えないためである。一方、本第２の実施の形態では以下に述べる通り、予測機構がパケットのルーティング経路に影響を与えうるが、パケットの目的地への経路の存在は常に保証される。本実施の形態では、入力ポートで受信したパケットは、ＲＣステージが終了して、予測が不成功（予測ミス）であった場合、通常のＲＣ，ＶＡ，ＳＡおよびＳＴステージによるパイプライン処理を通して、正しい出力ポートへ別途転送される。これにより、ＲＣステージの処理時間が大きい場合、すなわち予測成否の判定を含むＲＣステージに複数のクロックサイクルが必要となる場合に、予測成功時のルータ遅延を、既存の予測機構を具えるルータと比べて削減することができる。
【００３０】
この機構を具えたルータでは、予測が成功した場合には１ステージ、かつ、出力ポートにおいて遅延することなくパケットを転送すること可能となる。従って、当該ルータは、１ステージにかかる処理時間（クロックサイクル）でパケットを転送することができる。そこで、このような機構を具えたルータを、本明細書では、１ステージルータと呼ぶこととする。なお、１ステージルータには、第１の実施の形態で述べた予測成否判定部１５０を含めても、含めなくともよい。すなわち、１ステージルータとしては、図１８のルータ２００または図１のルータ１００において、制御部１１０に上述した機構を持たせたものとすることができる。なお、予測ミスによってネットワークに生じた予測ミスパケットをルーティングする場合、予測ミスパケットの存在は予め考慮されていないため、通常のパイプライン処理におけるＲＣステージにおいて、適切な出力ポートが見つからない場合が起こり得る。この場合は、そのパケットの処理はＲＣステージで強制的に終了させてもよい。さらに、１ステージルータには隣接ルータとの接続に用いられているポートの中から特定の入力ポートおよび出力ポートを設けて、この特定の入力ポートから特定の出力ポートに転送されると予測されたパケットに対しては、ＰＳＴステージのみを行う。すなわち、特定の出力ポートに転送されたパケットに対しては、ＲＣ，ＶＡ，ＳＡおよびＳＴステージ全てを行わない。さらに、図４のように、この１ステージルータに計算ノード（即ち、当該ルータに結合されたプロセッサ）が接続されている場合、図２１に示したように、この特定の入力ポート間から計算ノード乃至ノード１６０が接続されている出力ポートへのクロスバスイッチ１４０等の、ルータ内部のデータパスをバイパスする専用のリンク１７０を設ける。そして、特定の入力ポートから特定の出力ポートにＰＳＴステージを用いて転送されたパケットを、計算ノード１６０へもこのバイパスする専用のリンク１７０を通って送出させるようにする。このバイパス処理により、特定の入力ポートに到着した、この計算ノード宛のパケットが、予測ミスにより間違って特定の出力ポートに転送された場合でも、この計算ノードにパケットが配送される。その他のパケットは、このバイパスする専用のリンクを使った転送を行わない。なお、図２１においては、予測成否判定器１５０を具えるルータを示しているが、前述したように、１ステージルータには、予測成否判定部１５０を含めても、含めなくともよい。
【００３１】
第２の実施の形態による１ステージルータを含む並列分散システムでは、予測ミスパケットがネットワーク上に生じ得る。デッドロックフリー方式によるルーティングのアルゴリズムでは、ルータにおけるパケットの転送方向に制限があり、この制限によって、予測ミスパケットは目的地まで到達できなくなる可能性がある。従って、ネットワーク上の適当な位置に、検出ルータを配置する。この検出ルータは、受信したパケットが目的地まで到達できるか否かを判定して、１つ以上前のルータにおける予測ミスにより目的地までの経路が存在しなくなった場合に、その予測ミスパケットを破棄するものである。検出ルータにおける目的地までの経路の検出は、ターンモデル（Ｔｕｒｎ Ｍｏｄｅｌ）（例えば、C. J. Glass and L. M. Ni, “The Turn Model for Adaptive Routing, Proceedings of International Symposium on Computer Architecture,” pp. 278-287, 1992を参照されたい。）等の並列分散システムにおいて一般的に使われているＮ×Ｎ→Ｃ型のデッドロックフリールーティングアルゴリズムの場合、目的地と現在地の位置を比較することで、簡単に識別することができる。なお、検出ルータとしては、上述した条件を満足する機能を有すれば、アーキテクチャに関する制限はなく、既存の予測機構を具えるルータまたはスペキュレイティブ・ルータ等にすることができる。
【００３２】
１ステージルータおよび検出ルータは、以下で述べるようにネットワーク上に配置して、パケットのネットワーク遅延を削減する。まず、規則性を有するネットワークトポロジの場合は、予測ミスパケットを廃棄できるように検出ルータをネットワーク上に配置し、その他のルータは、全て１ステージルータとする。ただし、１ステージルータは、ハミルトニアン閉路、またはすべてのプロセッサノードを接続しているルータを通過する閉路上に特定の出力ポートがあるように配置する。任意のネットワークトポロジの場合においても、以下のアルゴリズムにより検出ルータを配置し、その他のルータは１ステージルータとすることが可能である。
ステップ１：各ルータをノードとして、ノード集合Ｎ、チャネル集合Ｃから構成されるネットワークグラフＧ（Ｎ，Ｃ）を作成する。
ステップ２：Ｇ（Ｎ，Ｃ）において、各ノードから、各目的地まで、予測ミスにより転送されうる隣接ノードを訪問する。
ステップ３：目的地に到達するまで、到達先のノードにて予測ミスにより転送されうる出力ポートが存在する限り、深さ優先探索により訪問を続ける。
ステップ４：訪問先のノードにて、転送されうる出力ポートが存在しない場合、そのノードを検出ルータとする。そして、直前のノードに戻り、ステップ３に従って探索を続ける。
【００３３】
図５に、ハミルトニアン閉路を含めない場合の、１ステージルータおよび検出ルータの簡単な配置例を示す。図において、検出ルータは、Ｒ０〜Ｒ３，Ｒ７，Ｒ１１およびＲ１５であり、それ以外のルータは１ステージルータである。パケットは、ノードＮＳを有するルータＲ９を出発して、ノードＮＤを有するルータＲ６を目的地とする。２次元トーラスにおける次元順ルーティングの場合、出発地のルータＲ９（ノードＮＳ）から、目的地のルータＲ６（ノードＮＳ）へのパケット転送時に、ルータＲ９から矢印Ｄ２０で示す方向に進む予測ミス１、矢印Ｄ２１で示す方向に進む予測ミス２の、最大２個のミスパケットが生じ得るが、これらは検出ルータＲ１およびＲ１１にてそれぞれ廃棄される。
【００３４】
次に、図６に、ハミルトニアン閉路を含む場合の配置例を示す。図には、ハミルトニアン閉路Ｄ３０、上述したアルゴリズムに基づいて配置された検出ルータＲ０，Ｒ５，Ｒ１０およびＲ１５が示されている。また、図に示すように、ハミルトニアン閉路D３０上に、黒点で示す１ステージルータの特定の出力ポートが配置されている。図６では、複数の仮想チャネルおよびターンモデルルーティングアルゴリズムを用いている。すなわち、デッドロックフリーを保証するために、パケットの経路切り換えの禁止パターン（禁止ターン）を行う場合は、仮想チャネル番号を増加させ、ハミルトニアン閉路Ｄ３０またはすべてのルータを通過する閉路上の１ステージルータの出力ポート（特定の出力ポート）を通過するパケットは、ルータでの予測の成否を確認せずに、ＰＳＴステージで転送された出力ポートからそのまま転送される。しかしながら、すべてのルータを通過するハミルトニアン閉路の特性により、目的地に到着することが保証される。このことを、図６を用いて説明する。図において、パケットはルータＲ５（ノードＮＳ）を出発地、ルータＲ１１（ノードＮＤ）を目的地としており、最短経路は矢印Ｄ３１で示す経路となる。ここで、図のルータＲ６の予測部が南方向を予測した場合、南方向はＰＳＴのみで転送される出力ポートであるため、パケットはルータＲ６から矢印Ｄ３２の方向に送出される。よって図に示すように、パケットの転送経路が矢印Ｄ３２に変更され、パケットのホップ数は増加するが、ハミルトニアン閉路上に特定の出力ポートを配置していることにより、目的地へのパケットの配送が補償される。この場合、ホップ数が増加するデメリットに比べて、ネットワーク遅延の支配的な要素であるルータ内の遅延を削減した効果の方が大きいため、結果として、パケットのネットワーク転送遅延を低減することができる。
【００３５】
なお、ルータでの予測において、デッドロックフリールーティングアルゴリズムを満たす出力ポートの中から１つのポートが選択される。よって、予測成功の成否に関わらず、（ハミルトニアン閉路を含めた）隣接ルータへ転送されるパケットは、デッドロックフリー転送の条件を満たすことになり、本ネットワークはデッドロックフリーである。また、デッドロックフリーを保証しつつ、目的地への経路を保証するようにルーティングを設定する場合、最短経路を迂回できる回数は制限される。そのため、目的地へのパケットの転送が保証され、本ネットワークではライブロックは生じない。さらに、予測ミスにより生じる、デッドロックフリーは満たすが目的地までの経路を失ったパケットは、検出ルータにより廃棄され、予測ミスが発生したルータにおいて、別途正しい方向へパケットが複製・転送される。よって、目的地へのパケットの配送が保証される。
【００３６】
これ以降に、本発明による予測成否判定部を具えるルータを配置した並列分散システム、および、上述したアルゴリズムに基づき１ステージルータおよび検出ルータを配置した並列分散システムをシミュレーションした結果を示す。シミュレータとしては、非特許文献１に記載のシミュレータブックシム（Ｂｏｏｋｓｉｍ）を、予測機構に対応させたものを用いている。ネットワークは、８×８，１６×１６の２次元トーラスとして構成し、デッドロックフリールーティングアルゴリズムには次元順ルーティング（ＤＯＲ）を用いている。その他のシミュレーション条件は、以下の通りである。
ネットワーク：ｋ−ａｒｙ ２−ｃｕｂｅ （ｋ＝８，１６，３２）
予測アルゴリズム：静的直進予測アルゴリズムＳＳ（入力パケットが常に同一次元を直進すると予測する。例えば、NORTHポートに入力されたパケットはSOUTHポートに出力されると予測し、WESTポートに入力されたパケットはEASTポートに出力されると予測する。）、直前ポート予測アルゴリズムＬＰ（入力パケットが１つ前のパケットと同一の出力ポートを選択すると予測する。）、およびパターンマッチ予測アルゴリズムＳＰＭ（パターンマッチングに基づくユニバーサル予測アルゴリズムに、系列の長さ制限等の制約条件を付け、過去の通信履歴から繰り返しパターンを検索することによって、並列プログラムが有する通信の規則性を抽出する。）の３種類とする。
【００３７】
通信パターン：ユニフォームランダム、ビット列逆順およびＮＡＳ並列ベンチマークのＬＵ分解（サイズＷ）で生じるＭＰＩメッセージトレースから作成した３種類とする。
パケット長：ユニフォーム、ビット列逆順において８フリットとする。ＬＵ分解で生じるトラフィックはアプリケーションメッセージに応じた可変長とする。
スイッチング：バーチャルカットスルー方式とする。
ルータ間ケーブル遅延：２サイクルとする。
ルーティング：Ｘ−Ｙ次元順ルーティング（ＤＯＲ）とする。
仮想チャネル（ＶＣ）数：物理チャネル当たり２本のＶＣ（各８フリット分）を実装し、各次元ともデータライン（ｄａｔｅｌｉｎｅ）を越えないパケットはＶＣ０を使用し、データラインを越えるパケットはＶＣ１を使用する。
パイプライン：予測に基づかない場合は５ステージ、予測に基づく場合は２ステージで動作する。ただし、ＲＣは３サイクル、他のステージは１サイクルで動作すると仮定する（１フリットのＳＴによる転送は１サイクルとする。）。
特定の出力ポートの配置：Ｘ，Ｙの各次元の特定の出力ポートを、それぞれｋ＝２だけ離れた２つの行と列に配置する。
【００３８】
ＳＳの実験条件：予測値取得の遅延は特に考慮せず、潜在的に全パケットが予測スイッチング（ＰＳＴ）可能と仮定する。
ＬＰの実験条件：入力ポート毎の通信履歴長は、直前のパケットの出力ポートを記憶する１×３ビットとし、予測処理における遅延は発生せず、全パケットについて通信履歴の値を参照可能とする。
ＳＰＭの実験条件：パラメータα＝１とし、入力ポート毎の通信履歴長は５１２×３ビットとする。また、予測器はルータ当たり１つとし、入力ポートまたは注入ポートが通信履歴を更新してから、当該ポートに対する次パケットの出力ポートを予測するのに、４サイクルかかると仮定する。他の入力ポートの予測処理待ちの間に到着したパケットに対してはＰＳＴを行わないものとする。
データ収集方法：ユニフォームトラフィック、ビット列逆順トラフィックではネットワークをウォームアップした後、約１２，０００パケットを受信するまでのスループット、平均遅延を測定する。ＬＵ分解ではアプリケーションの開始から終了までに生じた通信メッセージのについて同様に測定する。
【００３９】
図７〜図１２に、本発明の第１の実施の形態における予測成否判定部の有無によるネットワークの特性への影響を、上述の条件において測定した結果を示す。図における（ａ）、（ｂ）は、各予測アルゴリズムＳＳ，ＬＰ，ＳＰＭについて、平均遅延（レイテンシ）およびスループットをそれぞれシミュレーションした結果である。図７〜図９、図１０〜図１２は、それぞれ、ネットワークのサイズを１６−ａｒｙ ２−ｃｕｂｅとした場合、および３２−ａｒｙ ２−ｃｕｂｅとした場合である。各図において、横軸はネットワークへのパケット注入負荷である。なお、ネットワークの性能は、平均遅延が小さいものほど、またスループットが大きいものほど優れたものとなる。これらの図より、パケットヘッダにヒントビットを、および、ルータに予測成否判定部を具えることにより、いずれの場合においても、スループット、レイテンシが改善され、ネットワークが飽和していないパケット注入負荷において、レイテンシを最大で７％削減できていることが分かる。これらの結果からも、本発明による予測成否判定部が、並列分散システムのネットワークにおいて有効であることが分かる。
【００４０】
図１３〜図１７に、本発明による１ステージルータと検出ルータの配置方法（予測ミスペナルティ削減方法）に基づいて、上述の条件で構成したネットワークへのパケットの注入負荷を変化させた場合の、各予測アルゴリズムによるパケット平均遅延をシミュレーションした結果を示す。各図は、通信パターンおよびネットワークの大きさが異なっている。各図において、横軸はネットワークへのパケット注入負荷、縦軸はパケット平均遅延であり、破線で示すｎｏｒｍａｌは、予測機構（予測部１１２）のない既存のルータでネットワークを構成した場合をシミュレーションしたものである。なお、ＲＣステージの実行に多数のクロックサイクルが必要な場合は、上述したように、既存の予測機構を有するルータでの予測による遅延削減効果は極めて小さくなる。つまり、予測機構を有するルータの性能は、予測機構のないルータ（ｎｏｒｍａｌ）の性能に近づく。
【００４１】
図１３および図１４は、ユニフォームランダム通信における、それぞれ１６−ａｒｙ ２−ｃｕｂｅ、３２−ａｒｙ ２−ｃｕｂｅでのシミュレーション結果である。図より、本発明による１ステージルータと検出ルータの配置方法は、いずれの予測アルゴリズムを用いた場合においても、既存のルータ（予測機構のないルータ）でネットワークを構成した場合（凡例ｎｏｒｍａｌ）に対して平均遅延が低下し、ひいてはネットワーク全体のスループットが向上している。
【００４２】
図１５および図１６は、ビット逆順通信における、それぞれ１６−ａｒｙ ２−ｃｕｂｅ、３２−ａｒｙ ２−ｃｕｂｅでのシミュレーション結果である。この通信パターンは、２進数で表した送信元ノード番地から宛先ノードに、パケットの送信を繰り返すもので、通信の規則性を有する。図１５の１６−ａｒｙ ２−ｃｕｂｅのパケット注入負荷０．０５では、ＳＳの平均遅延がｎｏｒｍａｌよりも大きな値となっているが、これは、ＳＳの予測ヒット率が低く、ビット逆順通信が高負荷時にホットスポットを形成する通信パターンであるため、予測ミスパケットが輻輳を悪化させたことによる。しかしながら、全体として、本発明による１ステージルータと検出ルータの配置方法を採用した並列分散システムの性能が向上していることが分かる。
【００４３】
図１７は、８−ａｒｙ ２−ｃｕｂｅにＬＵ分解で発生する通信パターンを与えた場合のシミュレーション結果を示す。この通信パターンは、全て隣接ノード間通信で構成され、パケット平均遅延は、ＳＰＭの場合、ＰＳＴステージによるパイプライン処理で転送する最短時間に近くなる。これら上述のシミュレーション結果からも、本発明による１ステージルータと検出ルータの配置方法の有効性を確認することができる。
【００４４】
本発明を諸図面や実施例に基づき説明してきたが、当業者であれば本開示に基づき種々の変形や修正を行うことが容易であることに注意されたい。従って、これらの変形や修正は本発明の範囲に含まれることに留意されたい。例えば、各手段、各部、各ステップなどに含まれる機能などは論理的に矛盾しないように再配置可能であり、複数の手段やステップなどを１つに組み合わせたり、あるいは分割したりすることが可能である。
【図面の簡単な説明】
【００４５】
【図１】本発明に係るルータ装置の概略的なブロック図である。
【図２】本発明に係るルータ装置におけるパケットの流れを示す図である。
【図３】本発明に係るパケットのパイプライン処理を示す図である。
【図４】２次元メッシュトポロジのネットワークを示す図である。
【図５】ハミルトニアン閉路を含めない場合の、１ステージルータおよび検出ルータの簡単な配置例を示す図である。
【図６】ハミルトニアン閉路を含む場合の１ステージルータおよび検出ルータの簡単な配置例を示す図である。
【図７ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＳでの平均遅延のシミュレーション結果である。
【図７ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＳでのスループットのシミュレーション結果である。
【図８ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＬＰでの平均遅延のシミュレーション結果である。
【図８ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＬＰでのスループットのシミュレーション結果である。
【図９ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＰＭでの平均遅延のシミュレーション結果である。
【図９ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ１６−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＰＭでのスループットのシミュレーション結果である。
【図１０ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＳでの平均遅延のシミュレーション結果である。
【図１０ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＳでのスループットのシミュレーション結果である。
【図１１ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＬＰでの平均遅延のシミュレーション結果である。
【図１１ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＬＰでのスループットのシミュレーション結果である。
【図１２ａ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＰＭでの平均遅延のシミュレーション結果である。
【図１２ｂ】本発明の第１の実施の形態における予測成否判定部の有無による、ネットワークのサイズ３２−ａｒｙ ２−ｃｕｂｅ、予測アルゴリズムＳＰＭでのスループットのシミュレーション結果である。
【図１３】本発明の第３の実施の形態における並列分散ネットワークの、ユニフォームランダム通信における１６−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１４】本発明の第３の実施の形態における並列分散ネットワークの、ユニフォームランダム通信における３２−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１５】本発明の第３の実施の形態における並列分散ネットワークの、ビット逆順通信における１６−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１６】本発明の第３の実施の形態における並列分散ネットワークの、ビット逆順通信における３２−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１７】本発明の第３の実施の形態における並列分散ネットワークの、ユニフォームランダム通信における８−ａｒｙ ２−ｃｕｂｅでの平均遅延のシミュレーション結果である。
【図１８】従来の並列分散システムにおいて用いられている、予測機構を有するルータの構成を示す概略的なブロック図である。
【図１９】ルータ内部でのパケットの流れを示す図である。
【図２０】予測機構および典型的なパイプライン処理を示す図である。
【図２１】図４の２次元メッシュトポロジにおける１ステージルータの一例を示す図である。
【符号の説明】
【００４６】
１００ ルータ
１１０ 制御部
１１２ 予測部
１２０ 入力部
１３０ 出力部
１４０ クロスバスイッチ
１５０ 予測成否判定部
１６０ ノード
１７０ ルータ内部のデータパスをバイパスする専用のリンク
２００ ルータ
Ａ１０，Ａ１１ 矢印
Ａ３０，Ａ３１ 矢印
ＣＭＰ 比較器
Ｐ１ 予測機構によるパイプライン処理
Ｐ２ 典型的なパイプライン処理
Ｄ１０〜Ｄ１２ 矢印
Ｄ３０ ハミルトニアン閉路
Ｄ３１ 最短経路を示す矢印
Ｄ３２ 変更後の経路を示す矢印
ＤＩＲ 目的地情報格納部
ＩＮ１，ＩＮ２ 入力ポート
ＯＵＴ１，ＯＵＴ２ 出力ポート
ＮＤ 目的地ノード
ＮＳ 出発地ノード
ＰＴ 予測結果格納部
Ｒ０〜Ｒ１５ ルータ
【特許請求の範囲】
【請求項１】
パケットを受ける前にパケットの経路を予測する予測器と、前記パケットを受ける少なくとも１つの入力ポートと、前記パケットを受け、隣接するノードに転送する複数の出力ポートと、前記少なくとも１つの入力ポートで受けたパケットが転送されるべき出力ポートを設定するスイッチとを持つルータであって、
前記予測器で予測された経路に基づき、前記パケットを前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送するように前記スイッチを制御する制御器と、
前記入力ポートで受けたパケットに含まれる当該パケットの目的地関連情報と、前記予測器により予測された経路情報とを比較し、前記予測器による予測が正しいか否かを判定する予測成否判定器とを具え、
前記制御器は、
前記予測成否判定器により予測が正しくないと判定された場合、前記予測された経路を用いずに、前記入力ポートで受けたパケットの宛先アドレスに基づく通常の経路計算処理を行って、前記通常の経路計算処理で求めた経路に基づき、前記パケットを前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送するように前記スイッチを制御する、
ことを特徴とするルータ。
【請求項２】
請求項１に記載のルータにおいて、
前記制御器が、
前記予測器により予測された経路に基づき、前記パケットの経路を設定して１ステージで前記パケットを隣接するノードに転送するように前記スイッチおよび前記複数の出力ポートの１つを制御し、
前記予測された経路に基づき設定された経路と、通常の経路計算処理で求めた経路とが異なる場合には、前記通常の経路計算処理で求めた経路に基づいて、前記パケットの転送処理をさらに行うように前記スイッチを制御する、
ことを特徴とするルータ。
【請求項３】
請求項１に記載のルータにおいて、
前記制御器が、
特定の入力ポートから特定の出力ポートに転送されると予測されたパケットに対しては、予測の成否に関わらず、前記予測された経路に基づき設定された経路に基づいて前記パケットの転送処理を行うように前記スイッチを制御する、
ことを特徴とするルータ。
【請求項４】
請求項１または２に記載のルータを少なくとも１つ含み、前記ルータから送出されたパケットを受け、当該パケットの目的地までの経路が存在しない場合は、当該パケットを廃棄する少なくとも１つの予測ミス検出ルータ、
を具えることを特徴とする並列分散システム。
【請求項５】
請求項３に記載のルータを少なくとも１つ含む並列分散システムであって、前記並列分散システムのネットワークトポロジにおいてハミルトニアン閉路、またはプロセッサノードを接続しているすべてのルータを通過する閉路上に特定の入力ポートおよび出力ポートがあるように配置し、前記ルータから送出されたパケットを受け、当該パケットの目的地までの経路が存在しない場合は、当該パケットを廃棄する少なくとも１つの予測ミス検出ルータ、
を具えることを特徴とする並列分散システム。
【請求項１】
パケットを受ける前にパケットの経路を予測する予測器と、前記パケットを受ける少なくとも１つの入力ポートと、前記パケットを受け、隣接するノードに転送する複数の出力ポートと、前記少なくとも１つの入力ポートで受けたパケットが転送されるべき出力ポートを設定するスイッチとを持つルータであって、
前記予測器で予測された経路に基づき、前記パケットを前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送するように前記スイッチを制御する制御器と、
前記入力ポートで受けたパケットに含まれる当該パケットの目的地関連情報と、前記予測器により予測された経路情報とを比較し、前記予測器による予測が正しいか否かを判定する予測成否判定器とを具え、
前記制御器は、
前記予測成否判定器により予測が正しくないと判定された場合、前記予測された経路を用いずに、前記入力ポートで受けたパケットの宛先アドレスに基づく通常の経路計算処理を行って、前記通常の経路計算処理で求めた経路に基づき、前記パケットを前記少なくとも１つの入力ポートから前記複数の出力ポートの１つへ転送するように前記スイッチを制御する、
ことを特徴とするルータ。
【請求項２】
請求項１に記載のルータにおいて、
前記制御器が、
前記予測器により予測された経路に基づき、前記パケットの経路を設定して１ステージで前記パケットを隣接するノードに転送するように前記スイッチおよび前記複数の出力ポートの１つを制御し、
前記予測された経路に基づき設定された経路と、通常の経路計算処理で求めた経路とが異なる場合には、前記通常の経路計算処理で求めた経路に基づいて、前記パケットの転送処理をさらに行うように前記スイッチを制御する、
ことを特徴とするルータ。
【請求項３】
請求項１に記載のルータにおいて、
前記制御器が、
特定の入力ポートから特定の出力ポートに転送されると予測されたパケットに対しては、予測の成否に関わらず、前記予測された経路に基づき設定された経路に基づいて前記パケットの転送処理を行うように前記スイッチを制御する、
ことを特徴とするルータ。
【請求項４】
請求項１または２に記載のルータを少なくとも１つ含み、前記ルータから送出されたパケットを受け、当該パケットの目的地までの経路が存在しない場合は、当該パケットを廃棄する少なくとも１つの予測ミス検出ルータ、
を具えることを特徴とする並列分散システム。
【請求項５】
請求項３に記載のルータを少なくとも１つ含む並列分散システムであって、前記並列分散システムのネットワークトポロジにおいてハミルトニアン閉路、またはプロセッサノードを接続しているすべてのルータを通過する閉路上に特定の入力ポートおよび出力ポートがあるように配置し、前記ルータから送出されたパケットを受け、当該パケットの目的地までの経路が存在しない場合は、当該パケットを廃棄する少なくとも１つの予測ミス検出ルータ、
を具えることを特徴とする並列分散システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７ａ】
【図７ｂ】
【図８ａ】
【図８ｂ】
【図９ａ】
【図９ｂ】
【図１０ａ】
【図１０ｂ】
【図１１ａ】
【図１１ｂ】
【図１２ａ】
【図１２ｂ】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７ａ】
【図７ｂ】
【図８ａ】
【図８ｂ】
【図９ａ】
【図９ｂ】
【図１０ａ】
【図１０ｂ】
【図１１ａ】
【図１１ｂ】
【図１２ａ】
【図１２ｂ】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２００８−２９４５８６（Ｐ２００８−２９４５８６Ａ）
【公開日】平成２０年１２月４日（２００８．１２．４）
【国際特許分類】
【出願番号】特願２００７−１３５９４０（Ｐ２００７−１３５９４０）
【出願日】平成１９年５月２２日（２００７．５．２２）
【出願人】（５０４２０２４７２）大学共同利用機関法人情報・システム研究機構 (119)
【出願人】（５０４１３３１１０）国立大学法人 電気通信大学 (383)
【Ｆターム（参考）】
【公開日】平成２０年１２月４日（２００８．１２．４）
【国際特許分類】
【出願日】平成１９年５月２２日（２００７．５．２２）
【出願人】（５０４２０２４７２）大学共同利用機関法人情報・システム研究機構 (119)
【出願人】（５０４１３３１１０）国立大学法人 電気通信大学 (383)
【Ｆターム（参考）】
[ Back to top ]