相互結合網制御システム、相互結合網制御方法
【課題】情報間の順序を保証しつつ相互結合網の性能低下を抑制する相互結合網制御システム及び方法を提供すること。
【解決手段】本発明にかかる相互結合網制御システムは、相互結合網２と、順序保証バッファ３と、順序情報制御部４と、読出制御部５とを有する。相互結合網２は、複数の入力ポートと複数の出力ポートとを有し、入力ポートから入力された情報を、情報の出力先である出力ポートに出力する。順序情報制御部４は、入力ポートに入力される情報に対し、情報の出力先である出力ポート毎に、情報の読出順序を定める順序情報を付与する。順序保証バッファ３は、出力ポートから出力された情報を蓄積する。読出制御部５は、順序保証バッファ３に蓄積された情報を、順序情報により定められる順序にしたがって読出す。
【解決手段】本発明にかかる相互結合網制御システムは、相互結合網２と、順序保証バッファ３と、順序情報制御部４と、読出制御部５とを有する。相互結合網２は、複数の入力ポートと複数の出力ポートとを有し、入力ポートから入力された情報を、情報の出力先である出力ポートに出力する。順序情報制御部４は、入力ポートに入力される情報に対し、情報の出力先である出力ポート毎に、情報の読出順序を定める順序情報を付与する。順序保証バッファ３は、出力ポートから出力された情報を蓄積する。読出制御部５は、順序保証バッファ３に蓄積された情報を、順序情報により定められる順序にしたがって読出す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は相互結合網の制御システム及び方法に関するものであり、特に、順序保証が必要な情報を相互結合網の性能低下を抑制しつつ転送する方法に関する。
【背景技術】
【０００２】
近年の情報処理システムにおいては、複数の入出力を相互に結合するため、相互結合網が用いられることが多くなっている。例えば、リクエスタと複数のメモリポートとを結び、リクエストを転送するクロスバは典型的な相互結合網である。かかるクロスバを含む情報処理システムの一般的な構成を図６に示す。
【０００３】
図６においてリクエスタ６より発行されたリクエストは、キュー１に入力される。ここで、キュー１は、具体的にはＦＩＦＯすなわち先入れ先出し方式のバッファである。リクエスタ６が発行したリクエストは順次キュー１に蓄えられ、必要に応じ調停制御部７により調停されたのち、クロスバ２に入力される。クロスバ２は複数の入力ポートと複数の出力ポートとを接続する結合網である。図中では、入力ポートを１６、出力ポートを１６持つ、１６ｘ１６のクロスバを例示している。クロスバ２から出力された情報は、メモリポート８に格納される。図６に示す構成は、典型的には、１つのロード／ストア命令で複数の要素のメモリアクセスを実施する、ベクトルアーキテクチャにおいて採用されている。
【０００４】
かかる構成におけるキュー１に、リクエストが蓄積された状態を図７に示す。キュー１はクロスバ２の各入力ポートに対応して備えられており、リクエスタ６から発行されて各入力ポートへ入力を待つリクエストを蓄積している。この例では、入力ポートＰ０向けのキューには、要素（リクエスト）ｅ０００，ｅ０１６，…，ｅ２４０が蓄積されている。同様に入力ポートＰ１５向けのキューには、要素ｅ０１５，ｅ０３１，…，ｅ２５５が蓄積されている。
【０００５】
この状態のキュー１から、リクエストがクロスバ２を通過するまでの様子を二例示す。一例目は、同一ライン内の複数の要素の行き先がすべて異なる出力ポートである場合である。ここで、同一ラインとは、同時に調停に入る１６要素のことをいう。この場合に、要素がクロスバ２から出力されるタイミングを図８に示す。入力ポートにおける同一ラインのすべての要素（ｅ０００，ｅ００１，…，ｅ０１５）の行き先がすべて別の出力ポートだった場合には、行き先である出力ポートが競合しないため、全１６要素はクロスバ２を同じタイミングで通過でき、１Ｔのサイクルで出力される。全２５６要素は、１６Ｔのサイクルで出力される。
【０００６】
二例目は、同一ライン内の複数の要素の行き先が同じ出力ポートである場合である。例えば、入力ポートにおける同一ラインの要素（ｅ０００，ｅ００１，…，ｅ０１５）のすべてが同じ行き先である場合を想定する。この場合のクロスバ２の出力の様子を図９に示す。ここでは、１ライン目（ｅ０００〜ｅ０１５）の行き先がすべて出力ポートＰ０、２ライン目（ｅ０１６〜ｅ０３１）の行き先がすべて出力ポートＰ１となっており、以下同様に繰り返して、１６ライン目（ｅ２４０〜ｅ２５５）の行き先がすべて出力ポートＰ１５となる。このように１ラインの全１６要素がすべて同じ行き先である場合、出力ポートの競合が発生する。競合する要素は、クロスバ２を同時に通過することができない。このとき、調停制御部７は、競合している要素を、１サイクルにつき１つずつクロスバ２に入力させる調停制御を行う。競合に負けた要素はキュー１で待たされ、次のサイクルで入力されるか、再び競合する場合は再度調停を受けることになる。この場合、全２５６要素がクロスバ２を通過するには３１Ｔのサイクルを要する。
【０００７】
次に、命令が連続するケースにおける問題点を図１０、図１１、図１２を用いて説明する。図１０、図１１、図１２において、最初のｅ０００〜ｅ２５５までが命令１を構成する要素であり、次のｅ０００〜ｅ２５５までが命令２を構成する要素と定義する。すなわち、２５６の要素からなる命令を連続して転送する場面を想定する。
【０００８】
まず、同一ライン内の要素の行き先がすべて別の出力ポートである命令が２回続いた状態を、図１０に示す（なお、説明の便宜上、命令１は要素ｅ０００，ｅ０１６，…，ｅ２４０を出力ポートＰ０からルーティングし、命令２は要素ｅ０００，ｅ０１６，…，ｅ２４０を出力ポートＰ１５からルーティングする例を記載している）。同一ライン内の要素の行き先がすべて別の場合は、命令１、２ともに競合が発生することなくクロスバ２を通過するので、転送性能の低下は発生しない。
【０００９】
次に、同一ライン内の要素の行き先がすべて同じ出力ポートである命令が２回続いた状態を、図１１に示す。同一ライン内のすべての要素の行き先が同じ場合は、先頭ラインで競合が発生し、ラインのすべての要素が流れるまでに１５Ｔを要する。２５６要素のトータルでは４７Ｔのサイクルを要することになる。なお、この例では命令１と命令２の間に隙間は空いていない。
【００１０】
しかしながら、仮に入力ポートＰ１５に何らかの遅延があった場合には、命令１のｅ２５５のクロスバ２への発行が遅れ、命令２のｅ０００の発行が先に行なわれることがある。すると、図１２に示すような命令１の要素と命令２の要素の到着順序の逆転現象が発生する。命令１と命令２の間で要素の到着順序の保証が必要なければ、この制御方式で問題はないが、命令１と命令２の間で要素の到着順序の保証が必要な場合、すなわち、命令１の要素が、必ず命令２の要素よりも先に出力ポートに到着しなければならない場合は問題となる。
【００１１】
このような順序保証にかかる問題を回避するための手段として、ＡＴＭ交換機にかかるものではあるが、交換網を通過するパケットの順序保証を行うための構成が提案されている（特許文献１）。しかしながら、かかる構成は、クロスバのように複数の出力ポートをもつ結合網において、個々の出力ポート毎に順序保証を行うものではない。また、特許文献２には、パケットをシーケンシャルに転送するための構成が開示されているが、かかる構成は連続するメモリバンクへ効率よくデータを格納することを目的とするものであり、クロスバにおけるような複数の経路により転送されるデータを、複数の出力先毎に順序保証するという目的に適するものではない。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平５−０８３２８３号公報
【特許文献２】特開２００９−０７７４５３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
ここで、本発明が解決しようとする課題を説明するために、図１３に示す制御方法を想定する。この制御方法をホールドオール制御と定義する。ホールドオール制御では、命令１のすべての要素がクロスバを通過した後に、命令２の先頭要素のクロスバへの転送が開始される。このようにすれば、命令間で要素の到着順の逆転現象は発生しなくなり、命令間での順序保証を保つことができる。ただし、ホールドオール制御では、命令２の転送は、命令１のすべての要素の転送が終了するのを待ってから開始されるため、命令１と命令２の間で１５Ｔ間のペナルティが発生する。これは、クロスバの性能を大きく低下させる要因となる。
【００１４】
このように、相互結合網を流れる情報、例えば命令やデータ間での到着順序の保証が必要な場合、先行の情報が流れるまで後続の情報を一時ホールドする制御を行うと、相互結合網の利用効率が著しく低下するという問題があった。
【００１５】
本発明は、かかる問題を解決するためになされたものであり、情報間の順序を保証しつつ相互結合網の性能低下を抑制する相互結合網制御システム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明にかかる相互結合網制御システムは、複数の入力ポートと複数の出力ポートとを有し該入力ポートから入力された情報を該情報の出力先である出力ポートに出力する相互結合網と、該入力ポートに入力される情報に対し、該情報の出力先である出力ポート毎に、該情報の読出順序を定める順序情報を付与する順序情報制御部と、該出力ポート毎に設けられ、該出力ポートから出力された情報を蓄積する順序保証バッファと、該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出す読出制御部とを有するものである。
【００１７】
本発明にかかる相互結合網制御方法は、相互結合網に入力される情報に対し、該情報の出力先毎に、該情報の読出順序を定める順序情報を付与するステップと、該出力先から出力された該情報を順序保証バッファに蓄積するステップと、該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出すステップとを有するものである。
【発明の効果】
【００１８】
本発明により、情報間の順序を保証しつつ相互結合網の性能低下を抑制する相互結合網制御方法を提供することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施の形態１の構成図である。
【図２】本発明におけるキュー及び順序保証バッファの状態を示す図である。
【図３】本発明の実施の形態２の構成図である。
【図４】本発明の実施の形態２における順序保証バッファの構成例を示す図である。
【図５】本発明の実施の形態２のシーケンス図である。
【図６】背景技術の構成を示す図である。
【図７】背景技術におけるキューの状態を示す図である。
【図８】背景技術におけるキューの状態を示す図である。
【図９】背景技術におけるキューの状態を示す図である。
【図１０】背景技術におけるキューの状態を示す図である。
【図１１】背景技術におけるキューの状態を示す図である。
【図１２】背景技術におけるキューの状態を示す図である。
【図１３】背景技術におけるキューの状態を示す図である。
【発明を実施するための形態】
【００２０】
発明の実施の形態１
はじめに、図１を用いて、本発明の実施の形態１にかかる相互結合網制御システムの構成を説明する。１０１〜１１６はキューである。３０１〜３１６は順序保証バッファ、４は順序情報制御部、５は読出制御部である。
【００２１】
キュー１０１〜１１６は、クロスバ２に入力すべきリクエストを蓄積しておく機能を有する。典型的には、ＦＩＦＯすなわち先入れ先出し方式のバッファである。本実施形態では、クロスバ２の各入力ポートに対しそれぞれＦＩＦＯを設けた例を用いているが、入力ポート毎にキューを管理できるものであればどのような構成でもよい。
【００２２】
クロスバ２は、複数の入力ポートと複数の出力ポートを接続する相互結合網である。クロスバ２は、任意の入力ポートから入力された情報（リクエスト又はデータ）を調停制御部７の調停にしたがって任意の出力ポートに出力する。本実施形態では、入力１６ポート、出力１６ポート、すなわち１６ｘ１６の構成を有するクロスバである。また、入力ポート側には各入力ポートに対応してＦＩＦＯが、出力ポート側には各出力ポートに対応して順序保証バッファ３０１〜３１６がそれぞれ接続されている。
【００２３】
順序保証バッファ３０１〜３１６は、リクエスト間の順序保証（シリアライズ）を行なう機能を有する。典型的には、ＳＲＡＭで構成されるバッファである。本実施形態では、クロスバ２の各出力ポートに対しそれぞれ順序保証バッファを設けた例を用いているが、出力ポート毎にリクエストを管理できるものであればどのような構成でもよい。
【００２４】
順序情報制御部４は、リクエストをキュー１０１〜１１６に投入する前に、リクエストに順序情報を付与する。順序情報は、例えば昇順のシーケンス番号であり、リクエストの出力先であるクロスバ２の出力ポート毎に付与される。該順序情報はクロスバ２の特定の出力ポートに向かう何番目のリクエストであるかを表すものであり、順序保証が必要なリクエスト間の正しい読み出し順を示すものである。
【００２５】
読出制御部５は、順序保証バッファ３０１〜３１６からリクエストを読み出す制御を実行する。
【００２６】
つづいて、図１及び図２を用いて、本発明の実施の形態１にかかる方法における処理について説明する。
【００２７】
順序情報制御部４は、リクエストに対して順序情報を付与する。図２は命令１及び命令２の２つの命令をクロスバ２に入力する場合の例である。命令１及び命令２はそれぞれ２５６個のリクエストで構成されている。このうち連続する１６リクエスト（同一ライン）の行き先がすべて同じ出力ポートであるとする。この例の場合、リクエストには、該出力ポートに対応する０００から０３１までのシリアル番号が、順序情報として付与される。
【００２８】
順序情報が付与されたリクエストは、命令１と命令２の間におけるホールドオール制御が行なわれることなく、クロスバ２を通過する。これにより、クロスバ２の転送性能を維持することができる。
【００２９】
クロスバ２の出力ポートからリクエストが出力されると、リクエストは順序保証バッファ３０１〜３１６に書き込まれる。
【００３０】
ついで、読出制御部５は、順序保証バッファ３０１〜３１６から、順序情報の古い順にリクエストを読み出す。古い順序情報は先に付与されたリクエストに割り当てられているため、古い順序情報から順に読み出しを行なうことで命令間での順序が保証される。例えば、順序情報として昇順に付与されるシリアル番号が用いられている場合には、順序保証バッファ３０１〜３１６に格納されているすべてのリクエストのシリアル番号を参照し、該シリアル番号の小さいものから順に、リクエストを読み出すことができる。ここで、クロスバ２での転送に遅延が生じるなどして、次に読み出すべきシリアル番号を付与されたリクエストが順序保証バッファ３０１〜３１６の中に存在しない場合がありうる。この場合、読出制御部５は、該リクエストが順序保証バッファ３０１〜３１６に書き込まれるまで、読み出しを待機する。すなわち、順序保証バッファ３０１〜３１６の内容を定期的に参照しつづけ、次に読み出すべきシリアル番号を付与されたリクエストが発見されたときに、読み出しを再開する。
【００３１】
本実施形態では、このような一連の処理でリクエスト間の順序を保証することにより、ホールドオール制御を行うことなくリクエストを転送するため、クロスバ２の性能低下を抑制することができる。
【００３２】
発明の実施の形態２
つぎに、図３を用いて、本発明の実施の形態２にかかる相互結合網制御システムの構成を説明する。
【００３３】
リクエスタ６は、リクエストを発行する。本構成で想定しているリクエスタ６は、１つの命令から、それぞれ行き先となる出力ポートが定義される複数のリクエストを発行する機能を有している。例えば、実施の形態１と同様に、１命令からｅ０００〜ｅ２５５までの２５６の要素（リクエスト）を発行することができる。
【００３４】
順序情報制御部４は、リクエスタ６から発行されたリクエストに対して、順序情報の付与を行なう。順序情報は出力ポート毎に付与される。また、順序保証バッファ３０１〜３１６に格納すべきリクエストの数を上限として、付与することが可能である。例えば、該上限は、順序保証バッファ３０１〜３１６にリクエストを書き込むことのできる容量（深さ）であってよい。順序情報の付与数が該上限に達しており、新たな順序情報を付与できない場合には、リクエストは待たされることになる。待たされたリクエストには、古い順序情報が解放された後に、順序情報を割り当てる。
【００３５】
調停制御部７は、クロスバ２に対する入力の調停制御を行なう。すなわち、同じ出力ポートを行き先とする複数のリクエストが、同じタイミングで入力される場合には、１つのリクエストのみを通し、残りのリクエストはキュー１０１〜１１６にホールドさせる。
【００３６】
キュー１０１〜１１６は、実施の形態１におけるものと同様のバッファである。前述の調停制御で競合負けしたリクエストは、順次キュー１０１〜１１６で待たされることになる。
【００３７】
クロスバ２は、実施の形態１におけるものと同様のものである。
【００３８】
順序保証バッファ３０１〜３１６は、実施の形態１におけるものと同様であるが、本実施の形態では、補助機能として、各アドレスに有効なデータが書き込まれているかを示す情報（Ｖａｌｉｄ情報）を持つことができるものを用いている。かかる補助機能を有する順序保証バッファ３０１〜３１６の構成例（１ポート分）を図４に示す。図４に示されるように、順序保証バッファ３０１〜３１６は、データ格納バッファ３１のほかに、Ｖａｌｉｄ情報格納バッファ３２を備えている。
【００３９】
クロスバ２の出力ポートからリクエストが出力されると、該リクエストは順序保証バッファ３０１〜３１６に書き込まれる。本実施の形態においては、リクエストは、所定のルールにしたがって、順序情報と１対１に対応するアドレスのデータ格納バッファ３１に書き込まれる。
【００４０】
読出制御部５は、順序保証バッファ３０１〜３１６からリクエストを読み出し、メモリポート８０１〜８１６への出力を行う。ここで、古い順序情報が付与されたリクエストから順に読み出しを行うことで、命令間の順序を保証することができる。本実施例では、読み出す順序情報に対応するアドレスに有効なデータの書き込みが完了しているか否かを、Ｖａｌｉｄ情報を参照することにより検査する。もし書き込みが完了していなければ、当該アドレスへの書き込みが完了するまで読み出しは行わない。
【００４１】
順序保証バッファ３０１〜３１６又は読出制御部５は、順序保証バッファ３０１〜３１６からのリクエストの読み出しが完了すると、読み出されたリクエストの順序情報を解放するよう順序情報制御部４に通知する（順序情報の解放通知）。順序情報の解放通知は、例えば、一つのリクエストが読み出される度に行なうことが可能である。
【００４２】
メモリポート８０１〜８１６は、リクエストの最終的な出力先となるポートである。読出制御部５は、順序保証バッファ３０１〜３１６からリクエストを読み出し、順序保証バッファ３０１〜３１６に対応するメモリポート８０１〜８１６に対して該リクエストを出力する。メモリは、データのリードライト順を考慮しなければならないという性質を有するため、本実施形態の出力先の一例として好適である。
【００４３】
つづいて、図５に示すフローチャートを用いて、本発明の実施の形態２にかかる相互結合網制御システムにおける処理について説明する。
【００４４】
まず、リクエスタ６がリクエストを発行する（ステップＳ１）。通常、リクエスタ６は１命令あたり複数のリクエストを発行する。
【００４５】
ついで、順序情報制御部４が順序情報を各リクエストに付与する（ステップＳ２）。順序情報は出力ポート毎に付与される。また、順序保証バッファ３０１〜３１６に格納すべきリクエストの数がしきい値として定められ、該しきい値が付与できる順序情報の上限となる。このように順序情報は有限であるため、付与が可能な場合と不可能な場合とがある（ステップＳ３）。付与が可能である場合は、リクエストに対し順序情報が付与され、次のステップに進む。一方、付与済みの順序情報の数が該上限に達しており、付与できない場合には、順序情報が解放されるまで、リクエストは順序情報制御部で待たされることになる。待たされたリクエストには、過去に利用されていた古い順序情報が解放された後に順序情報が割り当てられ、その後、次のステップに進む。
【００４６】
キュー１０１〜１１６は、順序情報を付与されたリクエストを順序情報制御部４より受け取り、キューイングする（ステップＳ４）。
【００４７】
その後、調停制御部７は、キュー１０１〜１１６の先頭に到達したリクエストに対する調停制御を行う（ステップＳ５）。すなわち、同じ出力ポートを行き先とする複数のリクエストが同じタイミングで入力される場合には、調停制御部７は複数のリクエストのうち１つのリクエストのみクロスバ２を通過させ、残りのリクエストはキュー１０１〜１１６にホールドさせる。
【００４８】
調停制御されたリクエストは、クロスバ２を通過する（ステップＳ６）。
【００４９】
クロスバ２を通過したリクエストは、順序保証バッファ３０１〜３１６に書き込まれる（ステップＳ７）。本実施の形態では、順序保証バッファ３０１〜３１６への書き込みは、所定のルールに従って定められる、順序情報と１対１に対応する書き込みアドレスに対して行う。例えば、はじめに順序情報ｎのリクエストをアドレスｐに書き込んだ場合、順序情報ｎ＋１のリクエストはアドレスｐ＋１に、順序情報ｎ＋２のリクエストはアドレスｐ＋２に書き込み、以下同様に、順序情報ｎ＋ｍのリクエストはアドレスｐ＋ｍに書き込んでゆく。
【００５０】
読出制御部５は、順序情報の古い順にリクエストを読み出せるよう、書き込みの際に用いたルールにしたがう順番で、順序保証バッファ３０１〜３１６のアドレスから順次データを読み出してゆく。まず、読出制御部５は、最初に読み出すべき順序情報に対応するアドレス位置に有効なデータが書き込まれているかを判定する（ステップＳ８）。この判定は、本実施の形態においては、順序保証バッファ３０１〜３１６内のＶａｌｉｄ情報の値を参照することにより行う。例えば、はじめに順序情報ｎのリクエストがアドレスｐに書き込まれ、順序情報ｎ＋１のリクエストがアドレスｐ＋１に、順序情報ｎ＋２のリクエストがアドレスｐ＋２に、以下同様に、順序情報ｎ＋ｍのリクエストがアドレスｐ＋ｍに順次書き込まれた場合には、まずアドレスｐのＶａｌｉｄ情報を参照する。ここで、該Ｖａｌｉｄ情報が、有効なデータが書き込まれていることを示すものである場合に、読出制御部５は、該アドレスからデータ、すなわち順序情報ｎが付与されたリクエストを読み出す（ステップＳ９）。つぎに、アドレスｐ＋１のＶａｌｉｄ情報を参照し、同様の処理を行う。
【００５１】
なお、読出制御部５は、該Ｖａｌｉｄ情報が、有効なデータが書き込まれていないことを示すものであった場合は、該アドレスからの読出しは行わない。読出制御部５は、該アドレスに有効なデータ、すなわち該アドレスに対応する順序情報を付与されたリクエストが書き込まれるまで待機する。具体的には、読出制御部５は、該Ｖａｌｉｄ情報を定期的に参照しつづけ、該Ｖａｌｉｄ情報が、有効なデータが書き込まれていることを示すものとなったときに、読み出しを再開することができる。
【００５２】
その後、順序保証バッファ３０１〜３１６又は読出制御部５は、リクエストが読み出されたバッファエントリを無効化し、該リクエストの順序情報を解放するよう順序情報制御部４に通知する（ステップＳ１０）。
【００５３】
最後に、読出制御部は、順序保証バッファから読み出されたリクエストを、順次メモリポート８０１〜８１６に出力する（ステップＳ１１）。こうした一連の処理によって、リクエストは、順序情報の古いものから順にメモリポートに出力されることになる。
【００５４】
その他の実施形態
なお、本発明はこの実施形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【００５５】
例えば、この実施形態では相互結合網としてクロスバを例示したが、クロスバのような接続網を持つものであればどのような形態のものでもよい。具体的には、パケット（命令列又はデータ列）間での到着順序の保証が要求される通信網やコンピュータシステム、又はネットワークスイッチ等であってもよい。この場合、リクエスタはパケットを発生する手段、リクエストはパケット、ＦＩＦＯはデータ送信側に設けられるバッファ、順序保証バッファはデータ受信側に設けられるバッファと適宜読み替えることが可能である。
【００５６】
上記実施の形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００５７】
（付記１）
複数の入力ポートと複数の出力ポートとを有し、該入力ポートから入力された情報を該情報の出力先である出力ポートに出力する相互結合網と、該入力ポートに入力される情報に対し、該情報の出力先である出力ポート毎に、該情報の読出順序を定める順序情報を付与する順序情報制御部と、該出力ポートから出力された情報を蓄積する順序保証バッファと、該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出す読出制御部とを有する、相互結合網制御システム。
【００５８】
（付記２）
前記順序保証バッファは、前記順序情報と所定の格納ルールに基づいて一意に定められる格納位置に前記情報を格納し、前記読出制御部は、該格納ルールに基づいて定められる格納位置の読出順序にしたがって、読出すべき情報を決定する、付記１に記載の相互結合網制御システム。
【００５９】
（付記３）
前記読出制御部は、前記順序保証バッファに格納されている前記情報の前記順序情報を参照し、該順序情報と所定の読出ルールとに基づいて読出すべき情報を決定する、付記１に記載の相互結合網制御システム。
【００６０】
（付記４）
前記読出制御部は、読出すべき情報が前記順序保証バッファに書き込まれている場合にのみ情報を読出す、付記１−３いずれかに記載の相互結合網制御システム。
【００６１】
（付記５）
前記順序情報制御部は、付与済の順序情報の数が、前記順序保証バッファに格納すべき情報の数として定められるしきい値以下である場合に順序情報を付与し、該順序保証バッファから情報が読みだされたときに、付与済の順序情報の数を減ずる、付記１−４いずれかに記載の相互結合網制御システム。
【００６２】
（付記６）
前記順序保証バッファ又は読出制御部は、該順序保証バッファから情報が読出されたことを順序情報制御部に通知する、請求項６に記載の相互結合網制御システム。
【００６３】
（付記７）
相互結合網に入力される情報に対し、該情報の出力先毎に、該情報の読出順序を定める順序情報を付与するステップと、該出力先から出力された該情報を順序保証バッファに蓄積するステップと、該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出すステップとを有する、相互結合網制御方法。
【００６４】
（付記８）
前記蓄積するステップでは、前記順序情報と所定の格納ルールとに基づいて一意に定められる格納位置に前記情報を格納し、前記読出すステップでは、該格納ルールに基づいて定められる格納位置の読出順序にしたがって、読出すべき情報を決定する、付記７に記載の相互結合網制御方法。
【００６５】
（付記９）
前記読出すステップでは、前記順序保証バッファに格納されている前記情報の前記順序情報を参照し、該順序情報と所定の読出ルールとに基づいて読出すべき情報を決定する、付記７に記載の相互結合網制御方法。
【００６６】
（付記１０）
前記読出すステップでは、読出すべき情報が前記順序保証バッファに書き込まれている場合にのみ情報を読出す、付記７−９いずれかに記載の相互結合網制御方法。
【００６７】
（付記１１）
前記付与するステップでは、付与済の順序情報の数が、前記順序保証バッファに格納すべき情報の数として定められるしきい値以下である場合に順序情報を付与し、該順序保証バッファから情報が読みだされたときに、付与済の順序情報の数を減ずる、付記７−１０いずれかに記載の相互結合網制御方法。
【００６８】
（付記１２）
前記読出すステップでは、該順序保証バッファから情報が読出されたことを順序情報制御部に通知する、付記１１に記載の相互結合網制御方法。
【符号の説明】
【００６９】
１ キュー（ＦＩＦＯ）
２ クロスバ
３ 順序保証バッファ
４ 順序情報制御部
５ 読出制御部
６ リクエスタ
７ 調停制御部
８ メモリポート
【技術分野】
【０００１】
本発明は相互結合網の制御システム及び方法に関するものであり、特に、順序保証が必要な情報を相互結合網の性能低下を抑制しつつ転送する方法に関する。
【背景技術】
【０００２】
近年の情報処理システムにおいては、複数の入出力を相互に結合するため、相互結合網が用いられることが多くなっている。例えば、リクエスタと複数のメモリポートとを結び、リクエストを転送するクロスバは典型的な相互結合網である。かかるクロスバを含む情報処理システムの一般的な構成を図６に示す。
【０００３】
図６においてリクエスタ６より発行されたリクエストは、キュー１に入力される。ここで、キュー１は、具体的にはＦＩＦＯすなわち先入れ先出し方式のバッファである。リクエスタ６が発行したリクエストは順次キュー１に蓄えられ、必要に応じ調停制御部７により調停されたのち、クロスバ２に入力される。クロスバ２は複数の入力ポートと複数の出力ポートとを接続する結合網である。図中では、入力ポートを１６、出力ポートを１６持つ、１６ｘ１６のクロスバを例示している。クロスバ２から出力された情報は、メモリポート８に格納される。図６に示す構成は、典型的には、１つのロード／ストア命令で複数の要素のメモリアクセスを実施する、ベクトルアーキテクチャにおいて採用されている。
【０００４】
かかる構成におけるキュー１に、リクエストが蓄積された状態を図７に示す。キュー１はクロスバ２の各入力ポートに対応して備えられており、リクエスタ６から発行されて各入力ポートへ入力を待つリクエストを蓄積している。この例では、入力ポートＰ０向けのキューには、要素（リクエスト）ｅ０００，ｅ０１６，…，ｅ２４０が蓄積されている。同様に入力ポートＰ１５向けのキューには、要素ｅ０１５，ｅ０３１，…，ｅ２５５が蓄積されている。
【０００５】
この状態のキュー１から、リクエストがクロスバ２を通過するまでの様子を二例示す。一例目は、同一ライン内の複数の要素の行き先がすべて異なる出力ポートである場合である。ここで、同一ラインとは、同時に調停に入る１６要素のことをいう。この場合に、要素がクロスバ２から出力されるタイミングを図８に示す。入力ポートにおける同一ラインのすべての要素（ｅ０００，ｅ００１，…，ｅ０１５）の行き先がすべて別の出力ポートだった場合には、行き先である出力ポートが競合しないため、全１６要素はクロスバ２を同じタイミングで通過でき、１Ｔのサイクルで出力される。全２５６要素は、１６Ｔのサイクルで出力される。
【０００６】
二例目は、同一ライン内の複数の要素の行き先が同じ出力ポートである場合である。例えば、入力ポートにおける同一ラインの要素（ｅ０００，ｅ００１，…，ｅ０１５）のすべてが同じ行き先である場合を想定する。この場合のクロスバ２の出力の様子を図９に示す。ここでは、１ライン目（ｅ０００〜ｅ０１５）の行き先がすべて出力ポートＰ０、２ライン目（ｅ０１６〜ｅ０３１）の行き先がすべて出力ポートＰ１となっており、以下同様に繰り返して、１６ライン目（ｅ２４０〜ｅ２５５）の行き先がすべて出力ポートＰ１５となる。このように１ラインの全１６要素がすべて同じ行き先である場合、出力ポートの競合が発生する。競合する要素は、クロスバ２を同時に通過することができない。このとき、調停制御部７は、競合している要素を、１サイクルにつき１つずつクロスバ２に入力させる調停制御を行う。競合に負けた要素はキュー１で待たされ、次のサイクルで入力されるか、再び競合する場合は再度調停を受けることになる。この場合、全２５６要素がクロスバ２を通過するには３１Ｔのサイクルを要する。
【０００７】
次に、命令が連続するケースにおける問題点を図１０、図１１、図１２を用いて説明する。図１０、図１１、図１２において、最初のｅ０００〜ｅ２５５までが命令１を構成する要素であり、次のｅ０００〜ｅ２５５までが命令２を構成する要素と定義する。すなわち、２５６の要素からなる命令を連続して転送する場面を想定する。
【０００８】
まず、同一ライン内の要素の行き先がすべて別の出力ポートである命令が２回続いた状態を、図１０に示す（なお、説明の便宜上、命令１は要素ｅ０００，ｅ０１６，…，ｅ２４０を出力ポートＰ０からルーティングし、命令２は要素ｅ０００，ｅ０１６，…，ｅ２４０を出力ポートＰ１５からルーティングする例を記載している）。同一ライン内の要素の行き先がすべて別の場合は、命令１、２ともに競合が発生することなくクロスバ２を通過するので、転送性能の低下は発生しない。
【０００９】
次に、同一ライン内の要素の行き先がすべて同じ出力ポートである命令が２回続いた状態を、図１１に示す。同一ライン内のすべての要素の行き先が同じ場合は、先頭ラインで競合が発生し、ラインのすべての要素が流れるまでに１５Ｔを要する。２５６要素のトータルでは４７Ｔのサイクルを要することになる。なお、この例では命令１と命令２の間に隙間は空いていない。
【００１０】
しかしながら、仮に入力ポートＰ１５に何らかの遅延があった場合には、命令１のｅ２５５のクロスバ２への発行が遅れ、命令２のｅ０００の発行が先に行なわれることがある。すると、図１２に示すような命令１の要素と命令２の要素の到着順序の逆転現象が発生する。命令１と命令２の間で要素の到着順序の保証が必要なければ、この制御方式で問題はないが、命令１と命令２の間で要素の到着順序の保証が必要な場合、すなわち、命令１の要素が、必ず命令２の要素よりも先に出力ポートに到着しなければならない場合は問題となる。
【００１１】
このような順序保証にかかる問題を回避するための手段として、ＡＴＭ交換機にかかるものではあるが、交換網を通過するパケットの順序保証を行うための構成が提案されている（特許文献１）。しかしながら、かかる構成は、クロスバのように複数の出力ポートをもつ結合網において、個々の出力ポート毎に順序保証を行うものではない。また、特許文献２には、パケットをシーケンシャルに転送するための構成が開示されているが、かかる構成は連続するメモリバンクへ効率よくデータを格納することを目的とするものであり、クロスバにおけるような複数の経路により転送されるデータを、複数の出力先毎に順序保証するという目的に適するものではない。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平５−０８３２８３号公報
【特許文献２】特開２００９−０７７４５３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
ここで、本発明が解決しようとする課題を説明するために、図１３に示す制御方法を想定する。この制御方法をホールドオール制御と定義する。ホールドオール制御では、命令１のすべての要素がクロスバを通過した後に、命令２の先頭要素のクロスバへの転送が開始される。このようにすれば、命令間で要素の到着順の逆転現象は発生しなくなり、命令間での順序保証を保つことができる。ただし、ホールドオール制御では、命令２の転送は、命令１のすべての要素の転送が終了するのを待ってから開始されるため、命令１と命令２の間で１５Ｔ間のペナルティが発生する。これは、クロスバの性能を大きく低下させる要因となる。
【００１４】
このように、相互結合網を流れる情報、例えば命令やデータ間での到着順序の保証が必要な場合、先行の情報が流れるまで後続の情報を一時ホールドする制御を行うと、相互結合網の利用効率が著しく低下するという問題があった。
【００１５】
本発明は、かかる問題を解決するためになされたものであり、情報間の順序を保証しつつ相互結合網の性能低下を抑制する相互結合網制御システム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明にかかる相互結合網制御システムは、複数の入力ポートと複数の出力ポートとを有し該入力ポートから入力された情報を該情報の出力先である出力ポートに出力する相互結合網と、該入力ポートに入力される情報に対し、該情報の出力先である出力ポート毎に、該情報の読出順序を定める順序情報を付与する順序情報制御部と、該出力ポート毎に設けられ、該出力ポートから出力された情報を蓄積する順序保証バッファと、該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出す読出制御部とを有するものである。
【００１７】
本発明にかかる相互結合網制御方法は、相互結合網に入力される情報に対し、該情報の出力先毎に、該情報の読出順序を定める順序情報を付与するステップと、該出力先から出力された該情報を順序保証バッファに蓄積するステップと、該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出すステップとを有するものである。
【発明の効果】
【００１８】
本発明により、情報間の順序を保証しつつ相互結合網の性能低下を抑制する相互結合網制御方法を提供することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施の形態１の構成図である。
【図２】本発明におけるキュー及び順序保証バッファの状態を示す図である。
【図３】本発明の実施の形態２の構成図である。
【図４】本発明の実施の形態２における順序保証バッファの構成例を示す図である。
【図５】本発明の実施の形態２のシーケンス図である。
【図６】背景技術の構成を示す図である。
【図７】背景技術におけるキューの状態を示す図である。
【図８】背景技術におけるキューの状態を示す図である。
【図９】背景技術におけるキューの状態を示す図である。
【図１０】背景技術におけるキューの状態を示す図である。
【図１１】背景技術におけるキューの状態を示す図である。
【図１２】背景技術におけるキューの状態を示す図である。
【図１３】背景技術におけるキューの状態を示す図である。
【発明を実施するための形態】
【００２０】
発明の実施の形態１
はじめに、図１を用いて、本発明の実施の形態１にかかる相互結合網制御システムの構成を説明する。１０１〜１１６はキューである。３０１〜３１６は順序保証バッファ、４は順序情報制御部、５は読出制御部である。
【００２１】
キュー１０１〜１１６は、クロスバ２に入力すべきリクエストを蓄積しておく機能を有する。典型的には、ＦＩＦＯすなわち先入れ先出し方式のバッファである。本実施形態では、クロスバ２の各入力ポートに対しそれぞれＦＩＦＯを設けた例を用いているが、入力ポート毎にキューを管理できるものであればどのような構成でもよい。
【００２２】
クロスバ２は、複数の入力ポートと複数の出力ポートを接続する相互結合網である。クロスバ２は、任意の入力ポートから入力された情報（リクエスト又はデータ）を調停制御部７の調停にしたがって任意の出力ポートに出力する。本実施形態では、入力１６ポート、出力１６ポート、すなわち１６ｘ１６の構成を有するクロスバである。また、入力ポート側には各入力ポートに対応してＦＩＦＯが、出力ポート側には各出力ポートに対応して順序保証バッファ３０１〜３１６がそれぞれ接続されている。
【００２３】
順序保証バッファ３０１〜３１６は、リクエスト間の順序保証（シリアライズ）を行なう機能を有する。典型的には、ＳＲＡＭで構成されるバッファである。本実施形態では、クロスバ２の各出力ポートに対しそれぞれ順序保証バッファを設けた例を用いているが、出力ポート毎にリクエストを管理できるものであればどのような構成でもよい。
【００２４】
順序情報制御部４は、リクエストをキュー１０１〜１１６に投入する前に、リクエストに順序情報を付与する。順序情報は、例えば昇順のシーケンス番号であり、リクエストの出力先であるクロスバ２の出力ポート毎に付与される。該順序情報はクロスバ２の特定の出力ポートに向かう何番目のリクエストであるかを表すものであり、順序保証が必要なリクエスト間の正しい読み出し順を示すものである。
【００２５】
読出制御部５は、順序保証バッファ３０１〜３１６からリクエストを読み出す制御を実行する。
【００２６】
つづいて、図１及び図２を用いて、本発明の実施の形態１にかかる方法における処理について説明する。
【００２７】
順序情報制御部４は、リクエストに対して順序情報を付与する。図２は命令１及び命令２の２つの命令をクロスバ２に入力する場合の例である。命令１及び命令２はそれぞれ２５６個のリクエストで構成されている。このうち連続する１６リクエスト（同一ライン）の行き先がすべて同じ出力ポートであるとする。この例の場合、リクエストには、該出力ポートに対応する０００から０３１までのシリアル番号が、順序情報として付与される。
【００２８】
順序情報が付与されたリクエストは、命令１と命令２の間におけるホールドオール制御が行なわれることなく、クロスバ２を通過する。これにより、クロスバ２の転送性能を維持することができる。
【００２９】
クロスバ２の出力ポートからリクエストが出力されると、リクエストは順序保証バッファ３０１〜３１６に書き込まれる。
【００３０】
ついで、読出制御部５は、順序保証バッファ３０１〜３１６から、順序情報の古い順にリクエストを読み出す。古い順序情報は先に付与されたリクエストに割り当てられているため、古い順序情報から順に読み出しを行なうことで命令間での順序が保証される。例えば、順序情報として昇順に付与されるシリアル番号が用いられている場合には、順序保証バッファ３０１〜３１６に格納されているすべてのリクエストのシリアル番号を参照し、該シリアル番号の小さいものから順に、リクエストを読み出すことができる。ここで、クロスバ２での転送に遅延が生じるなどして、次に読み出すべきシリアル番号を付与されたリクエストが順序保証バッファ３０１〜３１６の中に存在しない場合がありうる。この場合、読出制御部５は、該リクエストが順序保証バッファ３０１〜３１６に書き込まれるまで、読み出しを待機する。すなわち、順序保証バッファ３０１〜３１６の内容を定期的に参照しつづけ、次に読み出すべきシリアル番号を付与されたリクエストが発見されたときに、読み出しを再開する。
【００３１】
本実施形態では、このような一連の処理でリクエスト間の順序を保証することにより、ホールドオール制御を行うことなくリクエストを転送するため、クロスバ２の性能低下を抑制することができる。
【００３２】
発明の実施の形態２
つぎに、図３を用いて、本発明の実施の形態２にかかる相互結合網制御システムの構成を説明する。
【００３３】
リクエスタ６は、リクエストを発行する。本構成で想定しているリクエスタ６は、１つの命令から、それぞれ行き先となる出力ポートが定義される複数のリクエストを発行する機能を有している。例えば、実施の形態１と同様に、１命令からｅ０００〜ｅ２５５までの２５６の要素（リクエスト）を発行することができる。
【００３４】
順序情報制御部４は、リクエスタ６から発行されたリクエストに対して、順序情報の付与を行なう。順序情報は出力ポート毎に付与される。また、順序保証バッファ３０１〜３１６に格納すべきリクエストの数を上限として、付与することが可能である。例えば、該上限は、順序保証バッファ３０１〜３１６にリクエストを書き込むことのできる容量（深さ）であってよい。順序情報の付与数が該上限に達しており、新たな順序情報を付与できない場合には、リクエストは待たされることになる。待たされたリクエストには、古い順序情報が解放された後に、順序情報を割り当てる。
【００３５】
調停制御部７は、クロスバ２に対する入力の調停制御を行なう。すなわち、同じ出力ポートを行き先とする複数のリクエストが、同じタイミングで入力される場合には、１つのリクエストのみを通し、残りのリクエストはキュー１０１〜１１６にホールドさせる。
【００３６】
キュー１０１〜１１６は、実施の形態１におけるものと同様のバッファである。前述の調停制御で競合負けしたリクエストは、順次キュー１０１〜１１６で待たされることになる。
【００３７】
クロスバ２は、実施の形態１におけるものと同様のものである。
【００３８】
順序保証バッファ３０１〜３１６は、実施の形態１におけるものと同様であるが、本実施の形態では、補助機能として、各アドレスに有効なデータが書き込まれているかを示す情報（Ｖａｌｉｄ情報）を持つことができるものを用いている。かかる補助機能を有する順序保証バッファ３０１〜３１６の構成例（１ポート分）を図４に示す。図４に示されるように、順序保証バッファ３０１〜３１６は、データ格納バッファ３１のほかに、Ｖａｌｉｄ情報格納バッファ３２を備えている。
【００３９】
クロスバ２の出力ポートからリクエストが出力されると、該リクエストは順序保証バッファ３０１〜３１６に書き込まれる。本実施の形態においては、リクエストは、所定のルールにしたがって、順序情報と１対１に対応するアドレスのデータ格納バッファ３１に書き込まれる。
【００４０】
読出制御部５は、順序保証バッファ３０１〜３１６からリクエストを読み出し、メモリポート８０１〜８１６への出力を行う。ここで、古い順序情報が付与されたリクエストから順に読み出しを行うことで、命令間の順序を保証することができる。本実施例では、読み出す順序情報に対応するアドレスに有効なデータの書き込みが完了しているか否かを、Ｖａｌｉｄ情報を参照することにより検査する。もし書き込みが完了していなければ、当該アドレスへの書き込みが完了するまで読み出しは行わない。
【００４１】
順序保証バッファ３０１〜３１６又は読出制御部５は、順序保証バッファ３０１〜３１６からのリクエストの読み出しが完了すると、読み出されたリクエストの順序情報を解放するよう順序情報制御部４に通知する（順序情報の解放通知）。順序情報の解放通知は、例えば、一つのリクエストが読み出される度に行なうことが可能である。
【００４２】
メモリポート８０１〜８１６は、リクエストの最終的な出力先となるポートである。読出制御部５は、順序保証バッファ３０１〜３１６からリクエストを読み出し、順序保証バッファ３０１〜３１６に対応するメモリポート８０１〜８１６に対して該リクエストを出力する。メモリは、データのリードライト順を考慮しなければならないという性質を有するため、本実施形態の出力先の一例として好適である。
【００４３】
つづいて、図５に示すフローチャートを用いて、本発明の実施の形態２にかかる相互結合網制御システムにおける処理について説明する。
【００４４】
まず、リクエスタ６がリクエストを発行する（ステップＳ１）。通常、リクエスタ６は１命令あたり複数のリクエストを発行する。
【００４５】
ついで、順序情報制御部４が順序情報を各リクエストに付与する（ステップＳ２）。順序情報は出力ポート毎に付与される。また、順序保証バッファ３０１〜３１６に格納すべきリクエストの数がしきい値として定められ、該しきい値が付与できる順序情報の上限となる。このように順序情報は有限であるため、付与が可能な場合と不可能な場合とがある（ステップＳ３）。付与が可能である場合は、リクエストに対し順序情報が付与され、次のステップに進む。一方、付与済みの順序情報の数が該上限に達しており、付与できない場合には、順序情報が解放されるまで、リクエストは順序情報制御部で待たされることになる。待たされたリクエストには、過去に利用されていた古い順序情報が解放された後に順序情報が割り当てられ、その後、次のステップに進む。
【００４６】
キュー１０１〜１１６は、順序情報を付与されたリクエストを順序情報制御部４より受け取り、キューイングする（ステップＳ４）。
【００４７】
その後、調停制御部７は、キュー１０１〜１１６の先頭に到達したリクエストに対する調停制御を行う（ステップＳ５）。すなわち、同じ出力ポートを行き先とする複数のリクエストが同じタイミングで入力される場合には、調停制御部７は複数のリクエストのうち１つのリクエストのみクロスバ２を通過させ、残りのリクエストはキュー１０１〜１１６にホールドさせる。
【００４８】
調停制御されたリクエストは、クロスバ２を通過する（ステップＳ６）。
【００４９】
クロスバ２を通過したリクエストは、順序保証バッファ３０１〜３１６に書き込まれる（ステップＳ７）。本実施の形態では、順序保証バッファ３０１〜３１６への書き込みは、所定のルールに従って定められる、順序情報と１対１に対応する書き込みアドレスに対して行う。例えば、はじめに順序情報ｎのリクエストをアドレスｐに書き込んだ場合、順序情報ｎ＋１のリクエストはアドレスｐ＋１に、順序情報ｎ＋２のリクエストはアドレスｐ＋２に書き込み、以下同様に、順序情報ｎ＋ｍのリクエストはアドレスｐ＋ｍに書き込んでゆく。
【００５０】
読出制御部５は、順序情報の古い順にリクエストを読み出せるよう、書き込みの際に用いたルールにしたがう順番で、順序保証バッファ３０１〜３１６のアドレスから順次データを読み出してゆく。まず、読出制御部５は、最初に読み出すべき順序情報に対応するアドレス位置に有効なデータが書き込まれているかを判定する（ステップＳ８）。この判定は、本実施の形態においては、順序保証バッファ３０１〜３１６内のＶａｌｉｄ情報の値を参照することにより行う。例えば、はじめに順序情報ｎのリクエストがアドレスｐに書き込まれ、順序情報ｎ＋１のリクエストがアドレスｐ＋１に、順序情報ｎ＋２のリクエストがアドレスｐ＋２に、以下同様に、順序情報ｎ＋ｍのリクエストがアドレスｐ＋ｍに順次書き込まれた場合には、まずアドレスｐのＶａｌｉｄ情報を参照する。ここで、該Ｖａｌｉｄ情報が、有効なデータが書き込まれていることを示すものである場合に、読出制御部５は、該アドレスからデータ、すなわち順序情報ｎが付与されたリクエストを読み出す（ステップＳ９）。つぎに、アドレスｐ＋１のＶａｌｉｄ情報を参照し、同様の処理を行う。
【００５１】
なお、読出制御部５は、該Ｖａｌｉｄ情報が、有効なデータが書き込まれていないことを示すものであった場合は、該アドレスからの読出しは行わない。読出制御部５は、該アドレスに有効なデータ、すなわち該アドレスに対応する順序情報を付与されたリクエストが書き込まれるまで待機する。具体的には、読出制御部５は、該Ｖａｌｉｄ情報を定期的に参照しつづけ、該Ｖａｌｉｄ情報が、有効なデータが書き込まれていることを示すものとなったときに、読み出しを再開することができる。
【００５２】
その後、順序保証バッファ３０１〜３１６又は読出制御部５は、リクエストが読み出されたバッファエントリを無効化し、該リクエストの順序情報を解放するよう順序情報制御部４に通知する（ステップＳ１０）。
【００５３】
最後に、読出制御部は、順序保証バッファから読み出されたリクエストを、順次メモリポート８０１〜８１６に出力する（ステップＳ１１）。こうした一連の処理によって、リクエストは、順序情報の古いものから順にメモリポートに出力されることになる。
【００５４】
その他の実施形態
なお、本発明はこの実施形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【００５５】
例えば、この実施形態では相互結合網としてクロスバを例示したが、クロスバのような接続網を持つものであればどのような形態のものでもよい。具体的には、パケット（命令列又はデータ列）間での到着順序の保証が要求される通信網やコンピュータシステム、又はネットワークスイッチ等であってもよい。この場合、リクエスタはパケットを発生する手段、リクエストはパケット、ＦＩＦＯはデータ送信側に設けられるバッファ、順序保証バッファはデータ受信側に設けられるバッファと適宜読み替えることが可能である。
【００５６】
上記実施の形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００５７】
（付記１）
複数の入力ポートと複数の出力ポートとを有し、該入力ポートから入力された情報を該情報の出力先である出力ポートに出力する相互結合網と、該入力ポートに入力される情報に対し、該情報の出力先である出力ポート毎に、該情報の読出順序を定める順序情報を付与する順序情報制御部と、該出力ポートから出力された情報を蓄積する順序保証バッファと、該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出す読出制御部とを有する、相互結合網制御システム。
【００５８】
（付記２）
前記順序保証バッファは、前記順序情報と所定の格納ルールに基づいて一意に定められる格納位置に前記情報を格納し、前記読出制御部は、該格納ルールに基づいて定められる格納位置の読出順序にしたがって、読出すべき情報を決定する、付記１に記載の相互結合網制御システム。
【００５９】
（付記３）
前記読出制御部は、前記順序保証バッファに格納されている前記情報の前記順序情報を参照し、該順序情報と所定の読出ルールとに基づいて読出すべき情報を決定する、付記１に記載の相互結合網制御システム。
【００６０】
（付記４）
前記読出制御部は、読出すべき情報が前記順序保証バッファに書き込まれている場合にのみ情報を読出す、付記１−３いずれかに記載の相互結合網制御システム。
【００６１】
（付記５）
前記順序情報制御部は、付与済の順序情報の数が、前記順序保証バッファに格納すべき情報の数として定められるしきい値以下である場合に順序情報を付与し、該順序保証バッファから情報が読みだされたときに、付与済の順序情報の数を減ずる、付記１−４いずれかに記載の相互結合網制御システム。
【００６２】
（付記６）
前記順序保証バッファ又は読出制御部は、該順序保証バッファから情報が読出されたことを順序情報制御部に通知する、請求項６に記載の相互結合網制御システム。
【００６３】
（付記７）
相互結合網に入力される情報に対し、該情報の出力先毎に、該情報の読出順序を定める順序情報を付与するステップと、該出力先から出力された該情報を順序保証バッファに蓄積するステップと、該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出すステップとを有する、相互結合網制御方法。
【００６４】
（付記８）
前記蓄積するステップでは、前記順序情報と所定の格納ルールとに基づいて一意に定められる格納位置に前記情報を格納し、前記読出すステップでは、該格納ルールに基づいて定められる格納位置の読出順序にしたがって、読出すべき情報を決定する、付記７に記載の相互結合網制御方法。
【００６５】
（付記９）
前記読出すステップでは、前記順序保証バッファに格納されている前記情報の前記順序情報を参照し、該順序情報と所定の読出ルールとに基づいて読出すべき情報を決定する、付記７に記載の相互結合網制御方法。
【００６６】
（付記１０）
前記読出すステップでは、読出すべき情報が前記順序保証バッファに書き込まれている場合にのみ情報を読出す、付記７−９いずれかに記載の相互結合網制御方法。
【００６７】
（付記１１）
前記付与するステップでは、付与済の順序情報の数が、前記順序保証バッファに格納すべき情報の数として定められるしきい値以下である場合に順序情報を付与し、該順序保証バッファから情報が読みだされたときに、付与済の順序情報の数を減ずる、付記７−１０いずれかに記載の相互結合網制御方法。
【００６８】
（付記１２）
前記読出すステップでは、該順序保証バッファから情報が読出されたことを順序情報制御部に通知する、付記１１に記載の相互結合網制御方法。
【符号の説明】
【００６９】
１ キュー（ＦＩＦＯ）
２ クロスバ
３ 順序保証バッファ
４ 順序情報制御部
５ 読出制御部
６ リクエスタ
７ 調停制御部
８ メモリポート
【特許請求の範囲】
【請求項１】
複数の入力ポートと複数の出力ポートとを有し、該入力ポートから入力された情報を該情報の出力先である出力ポートに出力する相互結合網と、
該入力ポートに入力される情報に対し、該情報の出力先である出力ポート毎に、該情報の読出順序を定める順序情報を付与する順序情報制御部と、
該出力ポートから出力された情報を蓄積する順序保証バッファと、
該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出す読出制御部とを有する、
相互結合網制御システム。
【請求項２】
前記順序保証バッファは、前記順序情報と所定の格納ルールに基づいて一意に定められる格納位置に前記情報を格納し、
前記読出制御部は、該格納ルールに基づいて定められる格納位置の読出順序にしたがって、読出すべき情報を決定する、
請求項１に記載の相互結合網制御システム。
【請求項３】
前記読出制御部は、前記順序保証バッファに格納されている前記情報の前記順序情報を参照し、該順序情報と所定の読出ルールとに基づいて読出すべき情報を決定する、
請求項１に記載の相互結合網制御システム。
【請求項４】
前記読出制御部は、読出すべき情報が前記順序保証バッファに書き込まれている場合にのみ情報を読出す、
請求項１−３いずれかに記載の相互結合網制御システム。
【請求項５】
前記順序情報制御部は、付与済の順序情報の数が、前記順序保証バッファに格納すべき情報の数として定められるしきい値以下である場合に順序情報を付与し、該順序保証バッファから情報が読みだされたときに、付与済の順序情報の数を減ずる、
請求項１−４いずれかに記載の相互結合網制御システム。
【請求項６】
相互結合網に入力される情報に対し、該情報の出力先毎に、該情報の読出順序を定める順序情報を付与するステップと、
該出力先から出力された該情報を順序保証バッファに蓄積するステップと、
該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出すステップとを有する、
相互結合網制御方法。
【請求項７】
前記蓄積するステップでは、前記順序情報と所定の格納ルールとに基づいて一意に定められる格納位置に前記情報を格納し、
前記読出すステップでは、該格納ルールに基づいて定められる格納位置の読出順序にしたがって、読出すべき情報を決定する、
請求項６に記載の相互結合網制御方法。
【請求項８】
前記読出すステップでは、前記順序保証バッファに格納されている前記情報の前記順序情報を参照し、該順序情報と所定の読出ルールとに基づいて読出すべき情報を決定する、
請求項６に記載の相互結合網制御方法。
【請求項９】
前記読出すステップでは、読出すべき情報が前記順序保証バッファに書き込まれている場合にのみ情報を読出す、
請求項６−８いずれかに記載の相互結合網制御方法。
【請求項１０】
前記付与するステップでは、付与済の順序情報の数が、前記順序保証バッファに格納すべき情報の数として定められるしきい値以下である場合に順序情報を付与し、該順序保証バッファから情報が読みだされたときに、付与済の順序情報の数を減ずる、
請求項６−９いずれかに記載の相互結合網制御方法。
【請求項１】
複数の入力ポートと複数の出力ポートとを有し、該入力ポートから入力された情報を該情報の出力先である出力ポートに出力する相互結合網と、
該入力ポートに入力される情報に対し、該情報の出力先である出力ポート毎に、該情報の読出順序を定める順序情報を付与する順序情報制御部と、
該出力ポートから出力された情報を蓄積する順序保証バッファと、
該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出す読出制御部とを有する、
相互結合網制御システム。
【請求項２】
前記順序保証バッファは、前記順序情報と所定の格納ルールに基づいて一意に定められる格納位置に前記情報を格納し、
前記読出制御部は、該格納ルールに基づいて定められる格納位置の読出順序にしたがって、読出すべき情報を決定する、
請求項１に記載の相互結合網制御システム。
【請求項３】
前記読出制御部は、前記順序保証バッファに格納されている前記情報の前記順序情報を参照し、該順序情報と所定の読出ルールとに基づいて読出すべき情報を決定する、
請求項１に記載の相互結合網制御システム。
【請求項４】
前記読出制御部は、読出すべき情報が前記順序保証バッファに書き込まれている場合にのみ情報を読出す、
請求項１−３いずれかに記載の相互結合網制御システム。
【請求項５】
前記順序情報制御部は、付与済の順序情報の数が、前記順序保証バッファに格納すべき情報の数として定められるしきい値以下である場合に順序情報を付与し、該順序保証バッファから情報が読みだされたときに、付与済の順序情報の数を減ずる、
請求項１−４いずれかに記載の相互結合網制御システム。
【請求項６】
相互結合網に入力される情報に対し、該情報の出力先毎に、該情報の読出順序を定める順序情報を付与するステップと、
該出力先から出力された該情報を順序保証バッファに蓄積するステップと、
該順序保証バッファに蓄積された情報を、該順序情報により定められる順序にしたがって読出すステップとを有する、
相互結合網制御方法。
【請求項７】
前記蓄積するステップでは、前記順序情報と所定の格納ルールとに基づいて一意に定められる格納位置に前記情報を格納し、
前記読出すステップでは、該格納ルールに基づいて定められる格納位置の読出順序にしたがって、読出すべき情報を決定する、
請求項６に記載の相互結合網制御方法。
【請求項８】
前記読出すステップでは、前記順序保証バッファに格納されている前記情報の前記順序情報を参照し、該順序情報と所定の読出ルールとに基づいて読出すべき情報を決定する、
請求項６に記載の相互結合網制御方法。
【請求項９】
前記読出すステップでは、読出すべき情報が前記順序保証バッファに書き込まれている場合にのみ情報を読出す、
請求項６−８いずれかに記載の相互結合網制御方法。
【請求項１０】
前記付与するステップでは、付与済の順序情報の数が、前記順序保証バッファに格納すべき情報の数として定められるしきい値以下である場合に順序情報を付与し、該順序保証バッファから情報が読みだされたときに、付与済の順序情報の数を減ずる、
請求項６−９いずれかに記載の相互結合網制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−１５５４４０（Ｐ２０１２−１５５４４０Ａ）
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願番号】特願２０１１−１２７０４（Ｐ２０１１−１２７０４）
【出願日】平成２３年１月２５日（２０１１．１．２５）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２４年８月１６日（２０１２．８．１６）
【国際特許分類】
【出願日】平成２３年１月２５日（２０１１．１．２５）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]