(57)【特許請求の範囲】
【請求項１】
直列に接続される複数の選択回路を有し、
前記複数の選択回路のうちの少なくとも一つの選択回路は、
送信元又は前段の選択回路からデータを入力される複数の入力部と、
前記複数の入力部のうちのデータが入力されている一以上の入力部から、いずれか１つの入力部を選択する選択部と、
前記選択部が選択した前記１つの入力部から入力される第１のデータを転送先に転送する転送部と、
前記選択部が前記１つの入力部として選択した第１の入力部が前記前段の選択回路に接続されている場合、前記前段の選択回路から前記第１のデータに続いて前記第１の入力部に入力される一以上の第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させる制御部と、を有することを特徴とする、演算処理装置。
【請求項２】
前記制御部は、前記第１の入力部から入力される前記第１のデータに付加される第１の情報であって前記前段の選択回路から前記第１のデータに続けて前記第２のデータが入力されることを表す前記第１の情報が有効である場合、前記第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させることを特徴とする、請求項１記載の演算処理装置。
【請求項３】
前記転送部は、前記第１のデータを次段の選択回路に転送し、
前記制御部は、前記選択部が選択しなかった一以上の第２の入力部について、前記選択部が前記一以上の第２の入力部を選択するまで、前記転送部に、前記次段の選択回路に転送するデータに付加される前記第１の情報を有効を示すように更新させることを特徴とする、請求項２記載の演算処理装置。
【請求項４】
前記少なくとも一つの選択回路は、
所定の期間に前記選択部が選択した入力部を示す第２の情報を、前記制御部に通知する通知部をさらに有し、
前記制御部は、前記第２の情報に基づいて、前記選択部が前記一以上の第２の入力部のうちの最後の入力部を選択したことを検出すると、前記転送部に、前記次段の選択回路に転送するデータに付加される前記第１の情報を無効を示すように更新させることを特徴とする、請求項３記載の演算処理装置。
【請求項５】
前記選択部は、前記複数の入力部の各々に対して設定された優先度情報に基づいて前記第１の入力部の選択を行ない、選択した前記第１の入力部の優先度情報を、前記複数の入力部のうちの他の入力部の優先度情報よりも低い優先度を表す値に更新し、
前記制御部は、前記第１の入力部が前記前段の選択回路に接続されており、且つ、前記第１のデータに付加される前記第１の情報が有効である場合、前記選択部による前記第１の入力部の優先度情報の更新を抑止させる、又は、前記選択部に前記第１の入力部の優先度情報を前記他の入力部の優先度情報よりも高い優先度を表す値に更新させることを特徴とする、請求項２〜４のいずれか１項記載の演算処理装置。
【請求項６】
前記前段の選択回路は、
複数の前段入力部と、
前記複数の前段入力部のうちのデータが入力されている一以上の前段入力部から、いずれか１つの前段入力部を選択する前段選択部と、
前記前段選択部が選択した前記１つの前段入力部から入力されるデータを前記第１の入力部に転送する前段転送部と、を有し、
前記一以上の第２のデータは、前記前段選択部により選択されなかった他の前段入力部に入力されているデータである、ことを特徴とする、請求項１〜５のいずれか１項記載の演算処理装置。
【請求項７】
複数の演算処理装置を有し、
前記複数の演算処理装置のうちの少なくとも一つの演算処理装置は、直列に接続される複数の選択回路を有し、前記複数の選択回路を介して他の演算処理装置からデータを受信し、
前記複数の選択回路のうちの少なくとも一つの選択回路は、
前記他の演算処理装置又は前段の選択回路からデータを入力される複数の入力部と、
前記複数の入力部のうちのデータが入力されている一以上の入力部から、いずれか１つの入力部を選択する選択部と、
前記選択部が選択した前記１つの入力部から入力される第１のデータを転送先に転送する転送部と、
前記選択部が前記１つの入力部として選択した第１の入力部が前記前段の選択回路に接続されている場合、前記前段の選択回路から前記第１のデータに続いて前記第１の入力部に入力される一以上の第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させる制御部と、を有することを特徴とする、情報処理装置。
【請求項８】
複数の演算処理装置を有する情報処理装置の制御方法であって、
前記複数の演算処理装置のうちの少なくとも一つの演算処理装置が、直列に接続される複数の選択回路を介して他の演算処理装置からデータを受信し、
前記複数の選択回路のうちの少なくとも一つの選択回路において、
複数の入力部のうちの前記他の演算処理装置又は前段の選択回路からデータを入力されている一以上の入力部から、選択部がいずれか１つの入力部を選択し、
前記選択部が選択した前記１つの入力部から入力される第１のデータを転送部が転送先に転送し、
前記選択部が前記１つの入力部として選択した第１の入力部が前記前段の選択回路に接続されている場合、前記前段の選択回路から前記第１のデータに続いて前記第１の入力部に入力される一以上の第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させることを特徴とする、情報処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置，情報処理装置，及び情報処理装置の制御方法に関する。
【背景技術】
【０００２】
サーバ等の情報処理装置では、情報処理装置に用いられる演算処理装置としてのＣＰＵ（Central Processing Unit）等のプロセッサが複数結合して設けられる場合がある。このような情報処理装置では、例えば並列コンピューティング（並列処理）等の実行のためにＣＰＵ間で通信が行なわれることがある。
【０００３】
図１５に例示するように、情報処理装置１００では、他のＣＰＵ２００又は図示しない他の装置（以下、送信元又はソースという）から送信されるパケット（データ）は、宛先のＣＰＵ２００のインタフェースにある物理層２１０で受信確認が行なわれる。そして、受信確認が行なわれたパケットは、ルータ部２２０にて調停され、キャッシュ部２３０を通過して、コア部２４０に通知される。
【０００４】
なお、クロスバスイッチにおける調停アルゴリズムにＬＲＵ（Least Recently Used）アルゴリズムが用いられる技術が知られている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２０１０／１１３２６２号パンフレット
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ルータ部２２０での調停は、各インタフェース（例えばソース）に対して公平であることが好ましい。例えば、ルータ部２２０が各ソースからのパケットを完全ＬＲＵ等により調停（選択）する場合、ソースの数が増えると、各ソースの調停参加信号が一か所に集約されるため、ＬＲＵで調停（選択）するための回路規模が増大し得る。
【０００７】
１つの側面では、本発明は、複数の送信元から入力されるデータを処理する演算処理装置において、回路規模の増大を抑制しつつ、各送信元のバス使用率を適切に調整することを目的とする。
【０００８】
なお、前記目的に限らず、後述する発明を実施するための形態に示す各構成により導かれる作用効果であって、従来の技術によっては得られない作用効果を奏することも本発明の他の目的の１つとして位置付けることができる。
【課題を解決するための手段】
【０００９】
１つの態様では、本件の演算処理装置は、直列に接続される複数の選択回路を有する。前記複数の選択回路のうちの少なくとも一つの選択回路は、送信元又は前段の選択回路からデータを入力される複数の入力部と、前記複数の入力部のうちのデータが入力されている一以上の入力部から、いずれか１つの入力部を選択する選択部とを有する。また、前記少なくとも一つの選択回路は、前記選択部が選択した前記１つの入力部から入力される第１のデータを転送先に転送する転送部と、制御部とをさらに有する。さらに、前記制御部は、前記選択部が前記１つの入力部として選択した第１の入力部が前記前段の選択回路に接続されている場合、以下の処理を行なう。すなわち、前記制御部は、前記前段の選択回路から前記第１のデータに続いて前記第１の入力部に入力される一以上の第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させる。
【発明の効果】
【００１０】
１つの側面では、複数の送信元から入力されるデータを処理する演算処理装置において、回路規模の増大を抑制しつつ、各送信元のバス使用率を適切に調整することができる。
【図面の簡単な説明】
【００１１】
【図１】図１５に示すルータ部の一例を示す図である。
【図２】図１５に示すルータ部の他の例を示す図である。
【図３】（ａ）は、図２に示すルータ部において、調停回路ごとにバス使用率が平等の場合の例を示す図であり、（ｂ）は、図２に示すルータ部において、ソースごとにバス使用率が平等の場合の例を示す図である。
【図４】一実施形態に係る情報処理装置の構成例を示す図である。
【図５】図４に示すルータ部の一例を示す図である。
【図６】（ａ）は、図２に示す調停回路Ａの動作例を示す図であり、（ｂ）は、図２に示す調停回路Ｂの動作例を示す図である。
【図７】（ａ）は、図５に示す調停回路Ａの動作例を示す図であり、（ｂ）は、図５に示す調停回路Ｂの動作例を示す図である。
【図８】（ａ）は、図６に示す調停回路による調停のタイミングチャートの一例を示す図であり、（ｂ）は、図７に示す調停回路による調停のタイミングチャートの一例を示す図である。
【図９】図４に示すルータ部の一例を示す図である。
【図１０】図９に示す調停回路の構成例を示す図である。
【図１１】図９に示す調停回路による調停のタイミングチャートの一例を示す図である。
【図１２】一実施形態に係るルータ部によるパケット転送処理の一例を説明するフローチャートである。
【図１３】一実施形態に係るルータ部によるＬＲＵ更新処理の一例を説明するフローチャートである。
【図１４】一実施形態に係るルータ部によるフラグ更新処理の一例を説明するフローチャートである。
【図１５】情報処理装置の構成例を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施の形態を説明する。ただし、以下に説明する実施形態は、あくまでも例示であり、以下に明示しない種々の変形や技術の適用を排除する意図はない。すなわち、本実施形態を、その趣旨を逸脱しない範囲で種々変形して実施することができる。なお、以下の実施形態で用いる図面において、同一符号を付した部分は、特に断らない限り、同一若しくは同様の部分を表す。
【００１３】
〔１〕対比例について
はじめに、図１〜図３（ａ）及び（ｂ）を参照しながら、一実施形態の対比例について説明する。図１５に示すルータ部２２０は、例えば図１に示す一元管理方式の調停回路２２０Ａをそなえることができる。以下、ＣＰＵ２００又は図示しない他の装置等のパケットの送信元をソース２００又はソースＡ〜Ｄ（図１参照）といい、コア部２４０（又はキャッシュ部２３０）等のパケットの送信先をターゲット２４０という場合がある。図１に示すルータ部２２０は、１つの調停回路２２０Ａ（調停器）をそなえ、複数のソースＡ〜Ｄからパケットを受け取り、受け取ったパケットを調停回路２２０Ａにて調停して一つのターゲット２４０に転送する回路である。
【００１４】
図１に示す調停回路２２０Ａにおいて、各ソース２００からのパケットを完全ＬＲＵ等により調停（選択）する場合、ソース２００の数が増えると、各ソース２００の調停参加信号が一か所に集約される。このため、ＬＲＵで調停（選択）するための論理回路の遅延が大きくなり得、複雑なタイミング設計が行なわれることになる。また、調停に勝ったバス（ソース２００）を選択するための論理回路（優先権獲得信号を送信する回路を含む）も各ソース２００分そなえられるため、回路規模が増大し得る。
【００１５】
そこで、ルータ部２２０は、例えば図２に示す直列多段調停方式の複数の調停回路２２０Ｂをそなえることも考えられる。図２に示すルータ部２２０は、図１に示すような１段の調停回路２２０Ａではなく、多段の調停回路２２０Ｂ（調停器）を直列に接続（結合）する。以下、調停回路２２０Ｂを調停回路Ａ〜Ｃという場合がある。図２に示すルータ部２２０では、複数のソースＡ〜Ｄをいくつかのグループ（調停回路Ａ〜Ｃに対応）に分け、例えば調停回路Ａのグループの勝者（ソースＡ又はＢ）を後段の調停回路Ｂのグループ（ソースＣ）での調停に参加させる。
【００１６】
これにより、複数のソース２００を各段で少しずつ調停することができ、ルータ部２２０の各調停回路２２０Ｂの負担が調停回路２２０Ａよりも軽減されるため、調停回路２２０Ｂの設計が容易になり得る。また、調停に参加するバスを絞り込みながらパケットを転送することができるため、回路規模も小さくできる。
【００１７】
しかしながら、図２に示すルータ部２２０では、調停回路２２０Ｂごとにバス使用率を平等とすると、ターゲット２４０に近いソース２００ほどバスの使用率が高くなる。例えば各調停回路２２０Ｂにおいて、単純なＬＲＵ等により調停に参加するソース２００ごとに公平な選択を行なうと、ターゲット２４０に近いソース２００ほど、ターゲット２４０から離れたソース２００よりも多くバスを占有することになる（図３（ａ）参照）。
【００１８】
このため、図３（ｂ）に例示するように、ソース２００ごとにバス使用率を平等として、全ソース２００間での調停を公平（平等）にする仕組みを設けることが好ましい。
【００１９】
なお、関連する技術として、複数の計算ノードが直列に接続された並列計算機システムにおいて、各計算ノードにそなえられたルータが、パケットに合流数を含めて転送する技術が知られている（例えば、特開２０１２−１９８８１９号公報等参照）。
【００２０】
この並列計算機システムの技術では、ルータが、複数のパケットを受信した場合、各パケットに格納されている合流数を取得し、受信したパケットの数に応じて合流数を更新する。そして、ルータは、更新した合流数に基づいて、受信した複数のパケットから後段のルータへ送信するパケットを選択し、選択したパケットに更新した合流数を格納して送信する。これにより、並列計算機システムでは、パケットのソース間の帯域使用率を平等にすることができる。
【００２１】
しかし、この並列計算機システムの技術では、合流数の比較や合流数の更新値をパケットに書き換える処理が行なわれる。従って、この技術をプロセッサの内部（例えばルータ部２２０）に適用した場合、小規模な論理回路で構成することや少ないゲート遅延で調停を行なうことが困難である。
【００２２】
〔２〕一実施形態
〔２−１〕情報処理装置について
そこで、一実施形態に係る情報処理装置では、各演算処理装置は、直列に接続される複数の選択回路をそなえることができる。この複数の選択回路のうちの一以上の選択回路では、以下の処理を行なうことにより、回路規模の増大を抑制しつつ、各ソースのバス（帯域）使用率を適切、例えば公平に調整することができる。例えば一以上の選択回路では、選択した第１の入力ポートが前段の選択回路に接続されている場合、前段の選択回路において第１のデータとの間で選択されなかった一以上の第２のデータを転送先に転送するまで、第１の入力ポートを選択することができる。なお、第１のデータとは、第１の入力ポートを選択したときに転送先に転送したデータである。以下、情報処理装置１について説明する。
【００２３】
図４に例示するように、一実施形態に係る情報処理装置１は、複数のＣＰＵ２，コントローラ１ａ，メモリ１ｂ，記憶部１ｃ，インタフェース部１ｄ，及び入出力部１ｅをそなえることができる。情報処理装置１としては、例えばサーバやＰＣ（Personal Computer）等のコンピュータが挙げられる。好ましくは、情報処理装置１としては、演算処理装置が複数の入力元（例えば他の演算処理装置や他の装置）からデータを入力されるコンピュータ、例えば並列コンピュータ等が挙げられる。
【００２４】
ＣＰＵ２は、種々の制御や演算を行なうプロセッサ（演算処理装置）の一例である。ＣＰＵ２は、他のＣＰＵ２及びコントローラ１ａとそれぞれ接続され、メモリ１ｂ，記憶部１ｃ，又は図示しないＲＯＭ（Read Only Memory）等に格納されたプログラムを実行することにより、種々の機能を実現することができる。例えば一実施形態に係るＣＰＵ２は、他のＣＰＵ２と協働して、並列コンピューティング（並列処理）を実行することができる。
【００２５】
コントローラ１ａは、ＣＰＵ２間，ＣＰＵ２−メモリ１ｂ間，又はＣＰＵ２−他のブロック１ｃ〜１ｅ間の少なくとも１つの制御（例えば通信制御）を行なうコントローラである。コントローラ１ａとしては、例えばシステムコントローラ及びメモリコントローラの少なくとも一方が挙げられる。
【００２６】
メモリ１ｂは、種々のデータやプログラムを格納する記憶装置である。各ＣＰＵ２は、プログラムを実行する際に、メモリ１ｂにデータやプログラムを格納し展開する。なお、メモリ１ｂとしては、例えばＲＡＭ（Random Access Memory）等の揮発性メモリが挙げられる。図４では、メモリ１ｂが複数のＣＰＵ２で共用される例を示すが、これに限定されるものではなく、メモリ１ｂは少なくとも１つのＣＰＵ２ごとにそなえられてもよい。
【００２７】
記憶部１ｃは、種々のデータやプログラム等を格納するハードウェアである。記憶部１ｃとしては、例えばＨＤＤ（Hard Disk Drive）等の磁気ディスク装置，ＳＳＤ（Solid State Drive）等の半導体ドライブ装置，フラッシュメモリやＲＯＭ等の不揮発性メモリ等の各種装置が挙げられる。
【００２８】
インタフェース部１ｄは、有線又は無線による、ネットワークや他の情報処理装置等との間の接続及び通信の制御等を行なう通信インタフェースである。インタフェース部１ｄとしては、例えば、ＬＡＮ（Local Area Network），ファイバチャネル（Fibre Channel；ＦＣ），インフィニバンド（InfiniBand）等に準拠したアダプタが挙げられる。
【００２９】
入出力部１ｅは、ＣＰＵ２と通信を行なう各種装置，入力装置，及び出力装置の少なくとも１つを含むことができる。入力装置としては、例えばマウス，キーボード，タッチパネル，及び音声操作のためのマイク等が挙げられる。また、出力装置としては、ディスプレイ，スピーカー，及びプリンタ等が挙げられる。
【００３０】
上述した各ブロック２及び１ａ〜１ｅ間はそれぞれバスで相互に通信可能に接続される。なお、情報処理装置１の上述したハードウェア構成は例示であり、情報処理装置１内でのハードウェアの増減（例えば任意のブロックの追加や省略），分割，任意の組み合わせでの統合，バスの追加又は省略等は適宜行なわれてもよい。
【００３１】
次に、ＣＰＵ２について説明する。図４に例示するように、ＣＰＵ２は、物理層２１，ルータ部２２，キャッシュ部２３，及びコア部２４をそなえることができる。物理層２１は、他のＣＰＵ２又は図示しない他の装置から送信されＣＰＵ２に入力されるパケット（データ）を受信（パケットの受信確認）するものであり、ＣＰＵ２のインタフェースの一例である。以下、ＣＰＵ２又は図示しない他の装置等のパケットの送信元をソース２又はソースＡ〜Ｄ（図５参照）という場合がある。
【００３２】
ルータ部２２は、物理層２１で受信確認を行なったパケットを入力ポート（図示省略）で受け取り、調停（選択）を行なって選択したパケットをキャッシュ部２３に格納する。キャッシュ部２３は、例えばＣＰＵ２とバス又はメモリ１ｂ等との間の遅延等を軽減するためにパケットを一時的に記憶する記憶装置である。キャッシュ部２３としては、例えばＳＲＡＭ（Static RAM）等の高速メモリが挙げられる。
【００３３】
コア部２４は、ルータ部２２からキャッシュ部２３を介して（又はルータ部２２から直接）入力されるパケットに対する種々の演算（処理）を行なうとともに、演算結果等の種々のデータや要求や指示等の種々のコマンド等を発行することができる。図４では、コア部２４は１つである例を示すが、コア部２４はＣＰＵ２に複数そなえられてもよい。以下、パケットの送信先としてのコア部２４（又はキャッシュ部２３）をターゲット２４という場合がある。
【００３４】
図５に例示するように、ＣＰＵ２のルータ部２２は、調停回路２２０Ｂと同様、直列に接続（結合）された直列多段調停方式の複数の調停回路３をそなえることができる。以下、調停回路３を調停回路Ａ〜Ｃという場合がある。ルータ部２２では、ＣＰＵ２等の複数のソース２（例えばソースＡ〜Ｄ）をいくつかのグループ（調停回路Ａ〜Ｃに対応）に分け、例えば調停回路Ａのグループの勝者（ソースＡ又はＢ）を後段の調停回路Ｂのグループ（ソースＣ）での調停に参加させる。このようにして、調停回路Ｃでの調停の勝者のパケットがターゲット２４に送出される。
【００３５】
これにより、複数のソース２を各段で少しずつ調停することができ、ルータ部２２の各調停回路３の負担が図１に示す調停回路２２０Ａよりも軽減されるため、調停回路３の設計が容易になり得る。また、調停に参加するバスを絞り込みながらパケットを転送することができるため、回路規模も小さくできる。
【００３６】
以下、一実施形態に係る情報処理装置１の動作の一例を説明する。
【００３７】
はじめに、対比例として、図２に示す複数の調停回路２２０Ｂを有するＣＰＵ２００を複数そなえる情報処理装置１００における、調停回路２２０Ｂ（調停回路Ａ及びＢ）の動作例を説明する。
【００３８】
１段目の調停回路２２０Ｂである調停回路Ａは、図６（ａ）に示すように、ソースＡからのパケットＡとソースＢからのパケットＢとを調停し、例えばパケットＡ，パケットＢの順で調停回路Ｂへ送出する。
【００３９】
２段目の調停回路２２０Ｂである調停回路Ｂは、図６（ｂ）に示すように、調停回路ＡからのパケットＡとソースＣからのパケットＣ０とを調停し、例えばパケットＡ，パケットＣ０の順で調停回路Ｃへ送出する。次いで、調停回路Ｂは、調停回路ＡからのパケットＢとソースＣからのパケットＣ１とを調停し、先行して送出したパケットＣ０に続けて、例えばパケットＢ，パケットＣ１の順で調停回路Ｃへ送出する。
【００４０】
上述したルータ部２２０（調停回路２２０Ｂ）による調停のタイミングチャートを図８（ａ）に例示する。なお、図８（ａ）において、横軸は時間を示す。横軸の１枠は１回の調停周期、例えば１クロックである。以下、ソースＡ〜Ｃからのパケット“Ａ０”〜“Ｃ４”等を、単に“Ａ０”〜“Ｃ４”と表記する。
【００４１】
図８（ａ）に示すように、調停回路Ｂからの出力（ターゲット（調停回路Ｃ））は、“Ａ０”，“Ｃ０”，“Ｂ０”，“Ｃ１”，・・・となるため、ソースＡ〜Ｃが選択される比率（バスの使用率）は、（Ａ：Ｂ：Ｃ＝１：１：２）となる。図８（ａ）のソースＡ〜Ｃが各パケットを送出している期間を見ても明らかなように、ソースＣは、調停回路Ｂにおいて、ソースＡ及びＢの２倍の頻度で選択され、ソース間のバス使用率が不公平であるといえる。なお、ＬＲＵは、調停回路２２０Ｂでの調停方式の一例であり、“０”の場合は一方の入力ポートが、“１”の場合は他方の入力ポートが選択されることを示す。
【００４２】
一方、一実施形態に係る情報処理装置１では、図５に例示する調停回路３（調停回路Ａ及びＢ）は以下のように動作することができる。ここで、一実施形態に係る情報処理装置１では、パケットにパケット連結フラグを付加することができる。
【００４３】
パケット連結フラグは、有効（例えば“１”）を示す場合、合流（調停回路３において異なるソース２が同時に調停に参加したこと）が発生して、当該パケットが調停に勝利した（選択された）ことを表す。パケット連結フラグは、例えば１ビットで表すことができる。すなわち、調停回路３に入力されたパケットに付加されたパケット連結フラグは、有効を示す場合、前段の選択回路３からの当該パケットに続けて他のパケットが入力されることを示す第１の情報であるといえる。
【００４４】
なお、パケット連結フラグは、パケットの先頭又は末尾等、パケットの任意の位置に付加されてもよく、パケットの内容を変化させない任意の態様でパケットに含められて（埋め込まれて）もよい。また、パケット連結フラグは、パケットとは異なるバスで送出されてもよい。以下、パケット連結フラグがパケットの末尾に付加されるものとして説明する。
【００４５】
ＣＰＵ２（例えば物理層２１或いはルータ部２２）は、受信したパケット又は送信するパケットに、無効（例えば“０”）に設定したパケット連結フラグを付加することができる。なお、ＣＰＵ２がパケットにパケット連結フラグを付加するタイミングとしては、１段目の調停回路３が次段の調停回路３にパケットを送出するときであってもよく、任意のタイミングとすることができる。
【００４６】
１段目の調停回路３である調停回路Ａは、図７（ａ）に示すように、ソースＡからのパケットＡとソースＢからのパケットＢとを調停し、例えばパケットＡを選択する。このとき、調停回路Ａは、パケットＡ及びパケットＢが合流しているため、調停に勝ったパケットＡに付加されたパケット連結フラグを無効から有効に更新して、パケットＡを調停回路Ｂへ送出する。また、調停回路Ａは、次に選択したパケットＢについて、パケットＢの他に合流するパケットが存在しないため、パケット連結フラグを無効のまま更新せず、パケットＢをパケットＡに続けて調停回路Ｂへ送出する。
【００４７】
２段目の調停回路３である調停回路Ｂは、図７（ｂ）に示すように、調停回路ＡからのパケットＡとソースＣからのパケットＣとを調停し、例えばパケットＡを選択する。このとき、調停回路Ｂは、パケットＡ及びパケットＣが合流しているため、調停に勝ったパケットＡに付加されたパケット連結フラグを有効にしようとする。ところが、パケットＡには、既に調停回路Ａによって、有効を示す（パケットＡ及びパケットＢが合流したことを示す）パケット連結フラグが付加されている（図７（ａ）参照）。従って、調停回路Ｂは、パケットＡに付加されたパケット連結フラグをそのまま更新せずに（有効のまま）、パケットＡを調停回路Ｃへ送出する。
【００４８】
また、調停回路Ｂは、パケットＡに付加されたパケット連結フラグが有効であったため、次の調停でもパケットＡが入力された入力ポート（パケットＢ）を選択する。すなわち、調停回路Ｂは、選択した入力ポートについて、パケット連結フラグが付加されたパケット及びその後続のパケットを、連結された１つのパケットと見做すのである。このとき、調停回路Ｂは、パケットＢ及びパケットＣが合流しているため、調停に勝ったパケットＢに付加されたパケット連結フラグを無効から有効に更新して、パケットＢを調停回路Ｃへ送出する。
【００４９】
なお、調停回路Ｂは、パケットＡの入力ポートを選択後に同じ入力ポートを選択するために、例えばＬＲＵを更新しないことにより、パケットＢの入力ポートの優先度をパケットＣの入力ポートよりも高い状態に維持することができる。これにより、調停回路Ｂは、パケットＢとパケットＣとの調停において、パケットＣの入力ポートに優先権を渡さず、再度パケットＢの入力ポートを選択することができる。
【００５０】
さらに、調停回路Ｂは、次に選択したパケットＣについて、パケットＣの他に合流するパケットが存在しないため、パケット連結フラグを無効のまま更新せず、パケットＣをパケットＢに続けて調停回路Ｃへ送出する。
【００５１】
上述したルータ部２２（調停回路３）による調停のタイミングチャートを図８（ｂ）に例示する。図８（ｂ）に示すように、調停回路Ｂからの出力（ターゲット（調停回路Ｃ））は、“Ａ０”，“Ｂ０”，“Ｃ０”，“Ａ１”，・・・となるため、ソースＡ〜Ｃが選択される比率（バスの使用率）は、（Ａ：Ｂ：Ｃ＝１：１：１）となり、平等である。なお、“Ａ０”，“Ａ１”，“Ａ２”が選択された後に参照されるＬＲＵ（図８（ｂ）の例では“Ａ０”，“Ａ１”，“Ａ２”と同じクロックのＬＲＵ）は、その直前のクロックから引き続いて“０”である。これにより、調停回路Ｂは、“Ａ０”，“Ａ１”，“Ａ２”の調停後、同じ入力ポートを選択して“Ｂ０”，“Ｂ１”，“Ｂ２”を調停回路Ｃに送出することができる。
【００５２】
このように、一実施形態に係る情報処理装置１では、図７（ａ），（ｂ）及び図８（ｂ）に示すように、調停回路Ａで合流したパケットＡ及びパケットＢは次の調停回路Ｂで勝った場合、最後尾のパケットＢが転送されるまで、パケットＣに優先権を渡さない。これにより、３つのソースＡ〜Ｃについてパケットによるバスの使用率を公平にすることが可能となる。なお、図７（ｂ）の例で、パケットＡが調停回路ＢでのパケットＣとの調停で敗者になっても同様である。パケットＣ，パケットＡが順に次段に転送された後、パケットＢの転送が完了するまで、ソースＣは調停回路Ｂから次のパケットを送出するための優先権を渡されないためである。
【００５３】
また、情報処理装置１によれば、調停回路２２０ＢをそなえるＣＰＵ２００に対して、ルータ部２２にパケットへのパケット連結フラグの付加及び合流の判定を行なう機能（回路）等を設けることで上記の動作を実現できるため、回路規模の増大を抑制できる。
【００５４】
〔２−２〕ルータ部の構成例
次に、一実施形態に係るルータ部２２の構成例を説明する。以下、図９に例示するように、ルータ部２２が直列に接続された３段の調停回路（選択回路）３（調停回路Ａ〜Ｃ）をそなえ、調停回路Ｃがターゲット２４に接続されるものとする。また、調停回路ＡにはソースＡ〜Ｃから、調停回路Ｂには調停回路Ａ，ソースＤ及びＥから、調停回路Ｃには調停回路Ｂ，ソースＦ及びＧから、それぞれパケットが入力されるものとする。なお、調停回路Ａ〜Ｃからの出力パケットは、各調停回路３内のバッファに一時的に保持される。
【００５５】
各調停回路３は、図１０に示すように、例示的に、資源管理部３１，データバッファ３２，複数（図１０の例では３つ）の入力ポート３３，調停器３４，セレクタ３５，及び合流制御部３６をそなえることができる。
【００５６】
資源管理部３１は、データバッファ３２の資源を監視し、パケットを格納するための記憶領域（空き）が確保できた場合、調停器３４に空き通知信号を出力する。これにより、資源管理部３１は、調停器３４にデータ転送の可否（ＯＮ又はＯＦＦ）を通知することができる。
【００５７】
データバッファ３２は、セレクタ３５で選択され転送された、パケット連結フラグを付加されたパケットを一時的に格納するバッファ３２ａをそなえることができる。データバッファ３２は、バッファ３２ａにパケットが格納されると、転送先（次段の調停回路３又はターゲット２４）へ調停参加信号を通知する。そして、転送先から優先権獲得信号を受信すると、バッファ３２ａに格納するパケットを転送先へ送出する。バッファ３２ａとしては、例えばＦＩＦＯ（First In First Out）のレジスタ等が挙げられる。
【００５８】
入力ポート３３は、物理層２１又は前段の調停回路３に接続され、ソース２から送出されたパケット又は前段の調停回路３で調停されて送出されたパケット等の情報を入力される入力端である。図１０の例では、“入力Ａ”〜“入力Ｃ”と接続された信号線（バス）が分岐する部位（入力部）を入力ポート３３と表記する。
【００５９】
入力ポート３３に入力される情報には、例えばパケット等のデータのほかに、調停参加信号が含まれる。入力ポート３３に入力された情報は、調停器３４，セレクタ３５，及び合流制御部３６に出力される。なお、図１０の例では、便宜上、パケット連結フラグが付加されたパケット（データ）のバスとパケット連結フラグのバスとを分離して示すが、これらのバスは、データのバスに統一してもよいし、入力ポート３３においてデータのバスからパケットとパケット連結フラグとを分離してもよい。
【００６０】
また、入力ポート３３は、調停器３４から出力される優先権獲得信号を、物理層２１又は前段の調停回路３，セレクタ３５，及び合流制御部３６に出力することができる。
【００６１】
調停器３４は、入力される複数のパケットを調停し、１のパケット（入力ポート３３）を選択するものであり、例示的に、ＬＲＵレジスタ３４ａ，選択部３４ｂ，及び制御部３４ｃをそなえることができる。
【００６２】
ＬＲＵレジスタ３４ａは、選択部３４ｂにより参照及び更新される入力ポート３３の優先度情報を格納するレジスタの一例である。ＬＲＵレジスタ３４ａは、優先度情報の一例として、入力ポート３３ごとに、最も過去に選択された、つまり最後に選択されてから最も時間が経っている入力ポート３３ほど大きな（又は小さな）値が設定されたＬＲＵ情報を格納することができる。なお、ＬＲＵ情報の内容としては、入力ポート３３ごとの最後に選択された時刻（タイムスタンプ）の情報や、各入力ポート３３を示す値を最も過去に（又は最近）選択された順で並べた情報等、既知の種々の内容とすることができる。
【００６３】
選択部３４ｂは、資源管理部３１から空き通知信号を入力されると、複数の入力ポート３３のうちのパケットが入力されている１以上の入力ポート３３から、１の入力ポート３３を選択し、選択した入力ポート３３に優先権を与える。
【００６４】
例えば、選択部３４ｂは、調停参加信号を出力する入力ポート３３を、パケットが入力されている入力ポート３３と特定することができる。また、選択部３４ｂは、複数の入力ポート３３の各々に対して設定された優先度情報に基づいて１の入力ポート３３の選択を行なうことができる。例えば、選択部３４ｂは、ＬＲＵレジスタ３４ａに格納されたＬＲＵ情報を参照して、パケットが入力されている１以上の入力ポート３３から、最も過去に選択された入力ポート３３を選択することができる。さらに、選択部３４ｂは、選択した入力ポート３３を示す優先権獲得信号を出力することができる。
【００６５】
なお、選択部３４ｂは、選択した入力ポート３３について、選択した入力ポート３３の優先度情報を、他の入力ポート３３の優先度情報よりも低い（例えば最低の）優先度を表す値に更新することができる。例えば、選択部３４ｂは、選択した入力ポート３３のＬＲＵ情報を、他の入力ポート３３のＬＲＵ情報よりも小さな（又は大きな）値に変更することができる。
【００６６】
制御部３４ｃは、例えば以下の２つの条件を満たす場合、選択部３４ｂが選択した第１の入力ポート３３を、第１の入力ポート３３から入力された第１のパケットが転送先に転送された後の調停（次の調停）において、引き続き選択部３４ｂに選択させる。なお、この制御は、少なくとも２段目以降の調停回路３において実行されることが好ましい。つまり、この制御は、パケット連結フラグが付加されていないパケット、又は、無効を示すパケット連結フラグが全パケットに付加されたパケットを入力される、１段目の調停回路３では省略することができる。
【００６７】
（ａ）選択部３４ｂが選択した第１の入力ポート３３が前段の選択回路３に接続されている場合。
（ｂ）前段の選択回路３において、第１のパケットとの間で選択されなかった一以上の第２のパケットが、未だ自身の調停回路３から転送先（次段の調停回路３又はターゲット２４）に転送されていない場合。
【００６８】
例えば制御部３４ｃは、第１の入力ポート３３から入力される第１のパケットに付加される（調停参加信号とともに調停器３４に入力された）パケット連結フラグが有効である場合に、上記（ａ）及び（ｂ）の条件を満たすと判断することができる。上述のように、パケット連結フラグが有効（例えば“１”）を示すのは、当該第１のパケットを入力された第１の入力ポート３３が前段の調停回路３に接続されており、且つ前段の調停回路３で合流が発生している場合である。従って、制御部３４ｃは、上記（ａ）及び（ｂ）の条件を満たすか否かの判断を、パケット連結フラグの有効又は無効の検出により行なうことができ、制御部３４ｃを簡素な回路で実現することができる。
【００６９】
制御部３４ｃは、上記（ａ）及び（ｂ）の条件を満たす場合、第２のパケットをセレクタ３５が転送先に転送するまで、選択部３４ｂに第１の入力ポート３３を選択させることができる。なお、選択部３４ｂに第１の入力ポート３３を選択させる手法は、種々の手法を用いてよい。例えば制御部３４ｃは、選択部３４ｂによる第１の入力ポート３３のＬＲＵ情報（優先度情報）の更新を抑止させることができる。又は、制御部３４ｃは、選択部３４ｂに第１の入力ポート３３のＬＲＵ情報を他の入力ポート３３の優先度情報よりも高い（例えば最高の）優先度を表す値に更新させてもよい。
【００７０】
このように、制御部３４ｃは、選択部３４ｂが入力ポート３３の選択に用いる優先度情報の更新を上記のように制御することで、選択部３４ｂに第１の入力ポート３３を容易に選択させることができる。
【００７１】
なお、制御部３４ｃは、選択部３４ｂに選択させている第１の入力ポート３３から、パケット連結フラグが無効（例えば“０”）のパケットが入力されると（調停に参加すると）、連結の切れ目であると判断する。この場合、制御部３４ｃは、例えば、抑止させていた、選択部３４ｂによる第１の入力ポート３３のＬＲＵ情報の更新を再開させる等により、第１の入力ポート３３のＬＲＵ情報を他の入力ポート３３のＬＲＵ情報よりも低い優先度を表す値に更新させる。
【００７２】
ところで、上述のように、パケット連結フラグは、調停回路３で合流したパケットを次段の調停回路３で連続して送出させる（入力ポート３３を選択させる）ためにパケットに付加される。そこで、制御部３４ｃは、選択部３４ｂが第１の入力ポート３３を選択した際に選択しなかった１以上の第２の入力ポート３３について、以下の制御を行なうことができる。
【００７３】
すなわち、制御部３４ｃは、選択部３４ｂが全ての第２の入力ポート３３を選択するまで（つまり他に合流するパケットがある場合）、次段の選択回路３に転送するパケットに付加されるパケット連結フラグを有効を示すように更新する。また、制御部３４ｃは、有効を示すパケット連結フラグが付加されたパケットについては、有効のままセレクタ３５に転送させる。例えば制御部３４ｃは、パケット連結フラグの更新通知信号をセレクタ３５に送出することで、セレクタ３５に、パケットに付加されたパケット連結フラグを有効に更新させることができる。なお、この制御は、少なくとも１段目から最終段の１段前までの調停回路３において実行されることが好ましい。つまり、この制御は、ターゲット２４の直前の調停回路３では省略することができる。
【００７４】
これにより、次段の調停回路３に、当該パケット連結フラグが付加されたパケットに続いて他のパケットが入力されることを通知することができ、ルータ部２２が複数段の調停回路３をそなえる場合でも、各調停回路３で上述した制御を行なうことができる。
【００７５】
また、制御部３４ｃは、後述する合流制御部３６から入力された合流フラグに基づいて、パケットの結合を停止することができる。この場合、例えば制御部３４ｃは、セレクタ３５に、パケットに付加されたパケット連結フラグを無効に維持（更新）させる。なお、パケット連結フラグは、初期値は無効を示し、無効から有効に更新された場合、再度無効に更新される可能性は低い。このため、制御部３４ｃは、パケット連結フラグを無効に維持させる場合、セレクタ３５に更新通知信号を送出しなくてもよい。
【００７６】
セレクタ３５は、選択部３４ｂが選択した第１の入力ポート３３から入力される第１のパケット（データ）を転送先に転送する転送部３５ａをそなえることができる。例えば転送部３５ａは、選択部３４ｂから出力される優先権獲得信号で指定された入力ポート３３からのパケットを、データバッファ３２に送出することができる。また、転送部３５ａは、制御部３４ｃからの更新通知信号に応じて、パケットに付加されたパケット連結フラグを有効又は無効に更新することができる。
【００７７】
転送部３５ａでは、以上のように、１ビットのパケット連結フラグの更新によって、高速且つ容易に、合流の発生を示す情報を次段の調停回路３に通知することができる。また、パケット連結フラグが１ビットの情報であるため、パケットにパケット連結フラグが付加されてバスに送出されても、ルータ部２２内の帯域使用率の増加を無視できる程度に抑えることができる。
【００７８】
合流制御部３６は、制御部３４ｃにパケットの合流を通知するものであり、例示的に、合流レジスタ３６ａ及び通知部３６ｂをそなえることができる。
【００７９】
合流レジスタ３６ａは、調停に勝利した入力ポート３３の情報を保持するレジスタである。例えば合流レジスタ３６ａは、入力ポート３３ごとに１ビットの合流フラグを格納することができる。一例として、合流レジスタ３６ａは、入力ポート３３が３つある場合、“１００”のように各１ビットが個々の入力ポート３３に対応した、３ビットの情報を格納する。
【００８０】
ここで、各ソース２によるパケットのバス使用率を公平にするという観点から、調停回路３で合流するパケットの一連の連結につき、各ソース２が選択される機会を一回とすることが好ましい。
【００８１】
そこで、合流制御部３６は、例えば以下の（Ａ）及び（Ｂ）の条件を満たす場合、該当する入力ポート３３の合流フラグを有効（例えば“１”）に設定する。
【００８２】
（Ａ）選択部３４ｂで選択された（優先権獲得通知で示される）入力ポート３３について、当該入力ポート３３から入力されるパケットに付加されたパケット連結フラグが無効を示す場合。
（Ｂ）“合流フラグが無効を示し、且つ、調停参加信号が有効を示す他の入力ポート３３”が存在する場合。
【００８３】
なお、上記（Ａ）について、パケット連結フラグが有効である場合には、当該入力ポート３３からのパケットが後続のパケットと結合されているため、合流制御部３６は、該当する入力ポート３３の合流フラグを無効（例えば“０”）のまま維持する。なお、結合されている最後尾のパケットに付加されるパケット連結フラグは無効を示すため、合流制御部３６は、最後尾のパケットが入力されたときに、上記（Ａ）の条件を満たすと判断するのである。これにより、当該入力ポート３３は複数回選択されるが、当該入力ポート３３から入力される複数のパケットは、それぞれ異なるソース２からのパケットとなるため、一連の連結につき各ソース２が選択されるのを一回とすることができる。
【００８４】
また、合流制御部３６は、以下の場合、合流レジスタ３６ａの全合流フラグを無効に更新（リセット）する。全合流フラグを無効にする場合としては、例えば上記（Ｂ）の条件を満たさない場合が挙げられる。一例として、１つの入力ポート３３から調停参加信号が入力され、当該入力ポート３３からのパケットが転送部３５ａから送出された場合、つまり合流が発生しない場合や、全ての入力ポート３３についての合流フラグが有効になる場合等が挙げられる。
【００８５】
すなわち、合流制御部３６が管理する合流フラグは、所定の期間に選択部３４ｂが選択した入力ポート３３を示す第２の情報の一例であるといえる。この所定の期間とは、パケットの一連の結合が開始してから現在までの期間であり、例えば制御部３４ｃが転送部３５ａにパケット連結フラグを有効に更新することを指示してから現在までの期間とすることができる。
【００８６】
通知部３６ｂは、合流レジスタ３６ａの合流フラグの情報を制御部３４ｃに通知することができる。
【００８７】
制御部３４ｃは、通知部３６ｂからの合流フラグの情報に基づいて、以下の（ｉ）及び（ii）に該当する場合、選択部３４ｂが選択した入力ポート３３からのパケットについて、転送部３５ａにパケット連結フラグを無効に維持（更新）させる。
【００８８】
（ｉ）選択部３４ｂで選択された（優先権獲得通知で示される）入力ポート３３について、当該入力ポート３３から入力されるパケットに付加されたパケット連結フラグが無効を示す場合。
（ii）“合流フラグが無効を示し、且つ、調停参加信号が有効を示す他の入力ポート３３”が存在しない場合。
【００８９】
なお、（ｉ）は合流制御部３６が合流フラグを有効にする条件のうちの上記（Ａ）と同一の条件であり、（ii）は、上記（Ｂ）の逆の条件、つまり合流制御部３６が合流フラグを無効にする条件である。
【００９０】
上記（ｉ）を条件とする理由は、パケット連結フラグが無効を示す場合、当該パケットを出力する入力ポート３３から連結されたパケットが出力されないからである。
【００９１】
なお、上記（ｉ）に該当する場合でも、合流フラグが無効を示す他の入力ポート３３からパケットが合流する場合、つまり上記（ii）に該当しない場合には、制御部３４ｃは、上記（ｉ）に係るパケットに付加されるパケット連結フラグを有効に更新する。
【００９２】
一方、合流フラグが有効を示し且つ調停参加信号が有効を示す他の入力ポート３３が存在する場合、現在送出している一連の連結パケットに、当該他の入力ポート３３から過去に送出されたパケットが含まれている。この場合、制御部３４ｃは、当該他の入力ポート３３を合流相手とは見做さず、上記（ｉ）に係るパケットに付加されるパケット連結フラグを無効に維持する。また、調停参加信号が有効を示す他の入力ポート３３が存在しない場合（合流が発生しない場合）にも、制御部３４ｃは、上記（ｉ）に係るパケットに付加されるパケット連結フラグを無効に維持する。
【００９３】
このように、制御部３４ｃは、合流フラグに基づいて、選択部３４ｂが、合流が発生した調停において選択しなかった入力ポート３３のうちの最後の入力ポート３３を選択したことを検出することができる。そして、制御部３４ｃは、転送部３５ａに、次段の選択回路３に転送するパケットに付加されるパケット連結フラグを無効を示すように更新させることができる。
【００９４】
制御部３４ｃによる合流フラグの情報に基づく上記制御は、上述のように、一連の連結につき各ソース２が選択されるのを一回とするためである。これにより、合流フラグが有効を示す入力ポート３３からのパケットは、パケットの連結に含まれないため、各ソース２によるパケットのバス使用率を、より正確に、公平にすることができる。
【００９５】
上述したルータ部２２（調停回路３）（図９参照）による調停のタイミングチャートを図１１に例示する。図１１に示すように、調停回路Ａでは、ソースＡ〜Ｃから入力されるパケットについて、単純なＬＲＵによる調停が行なわれ、調停回路Ａからは“Ａ０”，“Ｂ０”，“Ｃ０”，・・・の順で、各ソース２について平等にパケットが送出される。
【００９６】
調停回路Ｂでは、１クロック目でソースＤとソースＥとの調停が行なわれ、勝者のソースＤが優先権を獲得し、調停回路Ｂから“Ｄ０”が送出される。２クロック目では、調停回路Ａの送出バスとソースＥとの調停が行なわれ、勝者の調停回路Ａの送出バスが優先権を獲得し、調停回路Ｂから“Ａ０”が送出される。このとき、“Ａ０”のパケット連結フラグは有効であるため、３クロック目における調停回路Ａの送出バスとソースＥとの調停でも、調停回路Ａの送出バスが勝者となり優先権を獲得し、調停回路Ｂから“Ｂ０”が送出される。“Ｂ０”も同様にパケット連結フラグは有効であるため、４クロック目でも調停回路Ａの送出バスが勝者となり優先権を獲得し、調停回路Ｂから“Ｃ０”が送出される。なお、“Ｃ０”のパケット連結フラグは無効である。５クロック目では、調停に参加するソース２がソースＥのため、ソースＥが優先権を獲得し、調停回路Ｂから“Ｅ０”が送出される。
【００９７】
このように、調停回路Ａの送出バスから送出される連結パケットは“Ａ０”，“Ｂ０”，“Ｃ０”となる。調停回路Ａにおける合流レジスタ３６ａでは、合流フラグ（Ａ，Ｂ，Ｃ）に示すように、“Ａ０”，“Ｂ０”，“Ｃ０”がそれぞれ送出されると、合流フラグが“１００”，“１１０”，“０００（“１１１”になりリセット）”と変化する。また、調停回路Ａは、合流フラグが“０００”に変化するときに送出するパケット（“Ｃ０”）に付加されるパケット連結フラグを“０”に維持（更新）する。
【００９８】
調停回路Ｃでは、１クロック目でソースＦとソースＧとの調停が行なわれ、勝者のソースＦが優先権を獲得し、調停回路Ｃから“Ｆ０”が送出される。２クロック目では、調停回路Ｂの送出バスとソースＧとの調停が行なわれ、勝者の調停回路Ｂの送出バスが優先権を獲得し、調停回路Ｃから“Ｄ０”が送出される。このとき、“Ｄ０”のパケット連結フラグは有効であるため、３クロック目における調停回路Ｂの送出バスとソースＧとの調停でも、調停回路Ｂの送出バスが勝者となり優先権を獲得する。従って、３クロック目〜６クロック目までは、調停回路Ｃから、順に“Ａ０”，“Ｂ０”，“Ｃ０”，“Ｅ０”が送出される。なお、“Ｃ０”のパケット連結フラグは、調停回路Ｂにおいて無効から有効に更新される（図１１中、網掛けの２箇所の領域参照）。
【００９９】
このように、調停回路Ｂの送出バスから送出される連結パケットは“Ｄ０”，“Ａ０”，“Ｂ０”，“Ｃ０”，“Ｅ０”となる。調停回路Ｂにおける合流レジスタ３６ａでは、合流フラグ（調停回路Ａ，（ソース）Ｄ，（ソース）Ｅ）に示すように、“調停回路Ａからの連結パケット”，“Ｄ０”，“Ｅ０”がそれぞれ送出されると、合流フラグが“１００”，“１１０”，“０００”と変化する。また、調停回路Ｂは、合流フラグが“０００”に変化するときに送出するパケット（“Ｅ０”）に付加されるパケット連結フラグを“０”に維持（更新）する。
【０１００】
以上のような動作により、調停回路Ｃの出力（調停回路Ｃの送出バス）から送出されるパケットは、順に、“Ｆ０”，“Ｄ０”，“Ａ０”，“Ｂ０”，“Ｃ０”，“Ｅ０”，“Ｇ０”，・・・となる。
【０１０１】
図９に示す各ソース２が最大限のパケットを調停回路３に供給した場合、ターゲット２４へ転送される理想的なデータ量（バス使用率）は、ソース数が７であるため平等に分割してソース単位で１／７となる。図１１に示すタイミングチャートでは、“Ｆ０”，“Ｄ０”，“Ａ０”，“Ｂ０”，“Ｃ０”，“Ｅ０”，“Ｇ０”の順でターゲット２４にパケットが転送されており、理想的なバス使用率と等しく、ソース２ごとにバス使用率を公平とすることが可能となっている。
【０１０２】
〔２−３〕動作例
次に、上述の如く構成されたＣＰＵ２におけるルータ部２２の動作例を、図１２〜図１４を参照して説明する。
【０１０３】
はじめに、図１２を参照して、ルータ部２２におけるパケット転送処理の一例を説明する。図１２に例示するように、ルータ部２２の各調停回路３（選択部３４ｂ）は、入力ポート３３から調停参加要求があり、且つ、データバッファ３２に空きがあるか否かを判断する（ステップＳ１）。例えば入力ポート３３から調停参加信号の入力がない、又は、資源管理部３１から空き通知信号の入力がない場合（ステップＳ１のＮｏルート）、選択部３４ｂは、調停参加信号及び空き通知信号の入力を待ち受ける（処理がステップＳ１に移行する）。
【０１０４】
一方、入力ポート３３から調停参加信号が入力され、且つ、資源管理部３１から空き通知信号が入力された場合（ステップＳ１のＹｅｓルート）、選択部３４ｂは、ＬＲＵレジスタ３４ａを参照してＬＲＵに基づき入力ポート３３を選択する（ステップＳ２）。例えば選択部３４ｂは、選択した入力ポート３３を示す優先権獲得信号を出力する。また、調停回路３は、後述するＬＲＵ更新処理及びフラグ更新処理を行なう（ステップＳ３）。
【０１０５】
次いで、転送部３５ａは、優先権獲得信号が示す入力ポート３３からのパケットをデータバッファ３２のバッファ３２ａに格納する（ステップＳ４）。データバッファ３２は、パケットがバッファ３２ａに格納されると、バッファ３２ａからパケットを格納順に転送先（次段の調停回路３又はターゲット２４）に送出し（ステップＳ５）、処理がステップＳ１に移行する。なお、ステップＳ１〜Ｓ５の処理は、調停回路３ごとに実行される。
【０１０６】
次に、図１３を参照して、ルータ部２２におけるＬＲＵ更新処理（図１２のステップＳ３）の一例を説明する。図１３に例示するように、制御部３４ｃは、選択部３４ｂが選択した入力ポート３３からのパケットに付加されたパケット連結フラグがＯＮ（有効）であるか否かを判断する（ステップＳ１１）。
【０１０７】
パケット連結フラグがＯＮではない（ＯＦＦ（無効）である）場合（ステップＳ１１のＮｏルート）、選択部３４ｂは、選択部３４ｂが選択した入力ポート３３についてＬＲＵレジスタ３４ａのＬＲＵ情報を更新し（ステップＳ１３）、ＬＲＵ更新処理が終了する。一方、パケット連結フラグがＯＮである場合（ステップＳ１１のＹｅｓルート）、制御部３４ｃは、選択部３４ｂが選択した入力ポート３３についてのＬＲＵ情報の更新を抑止させ（ステップＳ１２）、ＬＲＵ更新処理が終了する。
【０１０８】
次に、図１４を参照して、ルータ部２２におけるフラグ更新処理（図１２のステップＳ３）の一例を説明する。図１４に例示するように、制御部３４ｃ及び合流制御部３６は、選択部３４ｂが選択した入力ポート３３からのパケットに付加されたパケット連結フラグがＯＮつまり有効であるか否かを判断する（ステップＳ２１）。
【０１０９】
パケット連結フラグがＯＮである場合（ステップＳ２１のＹｅｓルート）、処理がステップＳ２４に移行する。
【０１１０】
一方、パケット連結フラグがＯＮではない（ＯＦＦ（無効）である）場合（ステップＳ２１のＮｏルート）、合流制御部３６は、“合流フラグがＯＦＦ且つ調停参加信号がＯＮ”である他の入力ポート３３が存在するか否かを判定する（ステップＳ２２）。上記条件を満たす他の入力ポート３３が存在する場合（ステップＳ２２のＹｅｓルート）、合流制御部３６は、選択部３４ｂが選択した入力ポート３３に対応する合流レジスタ３６ａの合流フラグをＯＮ（有効）に更新する（ステップＳ２３）。
【０１１１】
また、制御部３４ｃは、選択部３４ｂが選択した入力ポート３３からのパケットに付加されたパケット連結フラグをＯＮに更新し（ステップＳ２４）、フラグ更新処理が終了する。なお、ステップＳ２４では、制御部３４ｃは、転送部３５ａに有効への更新を示す更新通知信号を送出することで、転送部３５ａにパケット連結フラグを更新させる。
【０１１２】
一方、ステップＳ２２において、上記条件を満たす他の入力ポート３３が存在しない場合（ステップＳ２２のＮｏルート）、合流制御部３６は、合流レジスタ３６ａの全合流フラグをＯＦＦ（無効）に更新する（ステップＳ２５）。
【０１１３】
また、制御部３４ｃは、選択部３４ｂが選択した入力ポート３３からのパケットに付加されたパケット連結フラグをＯＦＦに維持（更新）し（ステップＳ２６）、フラグ更新処理が終了する。なお、ステップＳ２６では、制御部３４ｃは、転送部３５ａに無効への更新を示す更新通知信号を送出することで、転送部３５ａにパケット連結フラグを維持（更新）させることができる。或いは、制御部３４ｃは、転送部３５ａに更新通知信号を送出しないことによりパケット連結フラグを無効に維持させてもよい。
【０１１４】
以上のように、一実施形態に係る情報処理装置１では、ＣＰＵ２において複数バスからのパケットを多段で調停する際に、１ビットの情報をパケットに付加することで、少ない演算による制御で、ソースごとのバス使用率を公平にすることができる。
【０１１５】
〔３〕その他
以上、本発明の好ましい実施形態について詳述したが、本発明は、かかる特定の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲内において、種々の変形、変更して実施することができる。
【０１１６】
例えば、ルータ部２２は、図５及び図９の例では３つの調停回路３をそなえるものとしたが、これに限定されるものではなく、任意の数の調停回路３をそなえることができる。
【０１１７】
また、ＣＰＵ２は、図４の例では１つのコア部２４をそなえるものとしたが、これに限定されるものではなく、複数のコア部２４をそなえてもよい。この場合、複数のコア部２４から他のＣＰＵ２又は図示しない他の装置へ送出されるデータやコマンド等の情報（例えばパケット）は、複数のコア部２４間で調停されてもよく、この調停には、上述したルータ部２２の構成を適用することも可能である。
【０１１８】
具体的には、ＣＰＵ２は、直列多段調停方式の複数の調停回路を、各コア部２４をソースとし、他のＣＰＵ２又は図示しない他の装置をターゲットとして、複数の調停回路３とは逆方向の通信用にそなえることができる。なお、便宜上、複数の調停回路３とは逆方向の通信に適用する調停回路には符号を付していないが、当該調停回路の機能（構成）は、入力ポート３３の数や調停回路の段数等が異なってよいものの、基本的に調停回路３と同様である。このように、一実施形態では、ＣＰＵ２における受信用の複数の調停回路３について説明したが、ソースとターゲットとを入れ替えるだけで、ＣＰＵ２からの送信用の複数の調停回路を実現することも可能である。
【０１１９】
また、図１０に示す調停回路３の各機能ブロックは、任意の組み合わせで併合してもよく、分割してもよい。
【０１２０】
さらに、一実施形態に係る調停回路３は、例えば、ＬＳＩ（Large Scale Integration）等の集積回路，ＡＳＩＣ（Application Specific Integrated Circuit），ＦＰＧＡ（Field Programmable Gate Array）等の電子回路によって実現され得る。調停回路３又は複数の調停回路３をそなえるルータ部２２は、コア部２４等とともに集積されてＣＰＵ２を構成してもよいし、コア部２４等とは別個に集積されてＣＰＵ２を構成してもよい。
【０１２１】
〔４〕付記
以上の実施形態に関し、更に以下の付記を開示する。
【０１２２】
（付記１）
直列に接続される複数の選択回路を有し、
前記複数の選択回路のうちの少なくとも一つの選択回路は、
送信元又は前段の選択回路からデータを入力される複数の入力部と、
前記複数の入力部のうちのデータが入力されている一以上の入力部から、第１の入力部を選択する選択部と、
前記選択部が選択した前記第１の入力部から入力される第１のデータを転送先に転送する転送部と、
前記選択部が選択した前記第１の入力部が前記前段の選択回路に接続されている場合、前記前段の選択回路において前記第１のデータとの間で選択されなかった一以上の第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させる制御部と、を有することを特徴とする、演算処理装置。
【０１２３】
（付記２）
前記制御部は、前記第１の入力部から入力される前記第１のデータに付加される第１の情報であって前記前段の選択回路から前記第１のデータに続けて前記第２のデータが入力されることを表す前記第１の情報が有効である場合、前記第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させることを特徴とする、付記１記載の演算処理装置。
【０１２４】
（付記３）
前記第１の情報は、１ビットの情報であることを特徴とする、付記２記載の演算処理装置。
【０１２５】
（付記４）
前記転送部は、前記第１のデータを次段の選択回路に転送し、
前記制御部は、前記選択部が選択しなかった一以上の第２の入力部について、前記選択部が前記一以上の第２の入力部を選択するまで、前記転送部に、前記次段の選択回路に転送するデータに付加される前記第１の情報を有効を示すように更新させることを特徴とする、付記２又は付記３記載の演算処理装置。
【０１２６】
（付記５）
前記少なくとも一つの選択回路は、
所定の期間に前記選択部が選択した入力部を示す第２の情報を、前記制御部に通知する通知部をさらに有し、
前記制御部は、前記第２の情報に基づいて、前記選択部が前記一以上の第２の入力部のうちの最後の入力部を選択したことを検出すると、前記転送部に、前記次段の選択回路に転送するデータに付加される前記第１の情報を無効を示すように更新させることを特徴とする、付記４記載の演算処理装置。
【０１２７】
（付記６）
前記選択部は、前記複数の入力部の各々に対して設定された優先度情報に基づいて前記第１の入力部の選択を行ない、選択した前記第１の入力部の優先度情報を、前記複数の入力部のうちの他の入力部の優先度情報よりも低い優先度を表す値に更新し、
前記制御部は、前記第１の入力部が前記前段の選択回路に接続されており、且つ、前記第１のデータに付加される前記第１の情報が有効である場合、前記選択部による前記第１の入力部の優先度情報の更新を抑止させる、又は、前記選択部に前記第１の入力部の優先度情報を前記他の入力部の優先度情報よりも高い優先度を表す値に更新させることを特徴とする、付記２〜５のいずれか１項記載の演算処理装置。
【０１２８】
（付記７）
前記優先度情報は、ＬＲＵ（Least Recently Used）に関する情報であることを特徴とする、付記６記載の演算処理装置。
【０１２９】
（付記８）
複数の演算処理装置を有し、
前記複数の演算処理装置のうちの少なくとも一つの演算処理装置は、直列に接続される複数の選択回路を有し、前記複数の選択回路を介して他の演算処理装置からデータを受信し、
前記複数の選択回路のうちの少なくとも一つの選択回路は、
前記他の演算処理装置又は前段の選択回路からデータを入力される複数の入力部と、
前記複数の入力部のうちのデータが入力されている一以上の入力部から、第１の入力部を選択する選択部と、
前記選択部が選択した前記第１の入力部から入力される第１のデータを転送先に転送する転送部と、
前記選択部が選択した前記第１の入力部が前記前段の選択回路に接続されている場合、前記前段の選択回路において前記第１のデータとの間で選択されなかった一以上の第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させる制御部と、を有することを特徴とする、情報処理装置。
【０１３０】
（付記９）
前記制御部は、前記第１の入力部から入力される前記第１のデータに付加される第１の情報であって前記前段の選択回路から前記第１のデータに続けて前記第２のデータが入力されることを表す前記第１の情報が有効である場合、前記第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させることを特徴とする、付記８記載の情報処理装置。
【０１３１】
（付記１０）
前記第１の情報は、１ビットの情報であることを特徴とする、付記９記載の情報処理装置。
【０１３２】
（付記１１）
前記転送部は、前記第１のデータを次段の選択回路に転送し、
前記制御部は、前記選択部が選択しなかった一以上の第２の入力部について、前記選択部が前記一以上の第２の入力部を選択するまで、前記転送部に、前記次段の選択回路に転送するデータに付加される前記第１の情報を有効を示すように更新させることを特徴とする、付記９又は付記１０記載の情報処理装置。
【０１３３】
（付記１２）
前記少なくとも一つの選択回路は、
所定の期間に前記選択部が選択した入力部を示す第２の情報を、前記制御部に通知する通知部をさらに有し、
前記制御部は、前記第２の情報に基づいて、前記選択部が前記一以上の第２の入力部のうちの最後の入力部を選択したことを検出すると、前記転送部に、前記次段の選択回路に転送するデータに付加される前記第１の情報を無効を示すように更新させることを特徴とする、付記１１記載の情報処理装置。
【０１３４】
（付記１３）
前記選択部は、前記複数の入力部の各々に対して設定された優先度情報に基づいて前記第１の入力部の選択を行ない、選択した前記第１の入力部の優先度情報を、前記複数の入力部のうちの他の入力部の優先度情報よりも低い優先度を表す値に更新し、
前記制御部は、前記第１の入力部が前記前段の選択回路に接続されており、且つ、前記第１のデータに付加される前記第１の情報が有効である場合、前記選択部による前記第１の入力部の優先度情報の更新を抑止させる、又は、前記選択部に前記第１の入力部の優先度情報を前記他の入力部の優先度情報よりも高い優先度を表す値に更新させることを特徴とする、付記９〜１２のいずれか１項記載の情報処理装置。
【０１３５】
（付記１４）
前記優先度情報は、ＬＲＵ（Least Recently Used）に関する情報であることを特徴とする、付記１３記載の情報処理装置。
【０１３６】
（付記１５）
複数の演算処理装置を有する情報処理装置の制御方法であって、
前記複数の演算処理装置のうちの少なくとも一つの演算処理装置が、直列に接続される複数の選択回路を介して他の演算処理装置からデータを受信し、
前記複数の選択回路のうちの少なくとも一つの選択回路において、
複数の入力部のうちの前記他の演算処理装置又は前段の選択回路からデータを入力されている一以上の入力部から、選択部が第１の入力部を選択し、
前記選択部により選択した前記第１の入力部から入力される第１のデータを転送部が転送先に転送し、
前記選択部が選択した前記第１の入力部が前記前段の選択回路に接続されている場合、前記前段の選択回路において前記第１のデータとの間で選択されなかった一以上の第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させることを特徴とする、情報処理装置の制御方法。
【０１３７】
（付記１６）
前記前段の選択回路において、
前記第１の入力部に転送する前記第１のデータに、前記前段の選択回路から前記第１のデータに続けて前記第２のデータを転送することを表す第１の情報を付加し、
前記少なくとも一つの選択回路において、
前記第１の入力部から入力される前記第１のデータに付加される前記第１の情報が有効である場合、前記第２のデータを前記転送部が前記転送先に転送するまで、前記選択部に前記第１の入力部を選択させることを特徴とする、付記１５記載の情報処理装置の制御方法。
【０１３８】
（付記１７）
前記少なくとも一つの選択回路において、
前記転送部が前記第１のデータを次段の選択回路に転送し、
前記選択部が選択しなかった一以上の第２の入力部について、前記選択部が前記一以上の第２の入力部を選択するまで、前記転送部に、前記次段の選択回路に転送するデータに付加される前記第１の情報を有効を示すように更新させることを特徴とする、付記１６記載の情報処理装置の制御方法。
【０１３９】
（付記１８）
前記少なくとも一つの選択回路において、
所定の期間に選択した入力部を示す第２の情報を管理し、
前記第２の情報に基づいて、前記選択部が前記一以上の第２の入力部のうちの最後の入力部を選択したことを検出すると、前記転送部に、前記次段の選択回路に転送するデータに付加される前記第１の情報を無効を示すように更新させることを特徴とする、付記１７記載の情報処理装置の制御方法。
【０１４０】
（付記１９）
前記少なくとも一つの選択回路において、
前記選択部が、前記複数の入力部の各々に対して設定された優先度情報に基づいて前記第１の入力部の選択を行ない、選択した前記第１の入力部の優先度情報を、前記複数の入力部のうちの他の入力部の優先度情報よりも低い優先度を表す値に更新し、
前記第１の入力部が前記前段の選択回路に接続されており、且つ、前記第１のデータに付加される前記第１の情報が有効である場合、前記選択部による前記第１の入力部の優先度情報の更新を抑止させる、又は、前記選択部に前記第１の入力部の優先度情報を前記他の入力部の優先度情報よりも高い優先度を表す値に更新させることを特徴とする、付記１６〜１８のいずれか１項記載の情報処理装置の制御方法。
【０１４１】
（付記２０）
前記優先度情報は、ＬＲＵ（Least Recently Used）に関する情報であることを特徴とする、付記１９記載の情報処理装置の制御方法。
【符号の説明】
【０１４２】
１    情報処理装置
１ａ    コントローラ
１ｂ    メモリ
１ｃ    記憶部
１ｄ    インタフェース部
１ｅ    入出力部
２    ＣＰＵ（ソース，演算処理装置）
２１    物理層
２２    ルータ部
２３    キャッシュ部
２４    コア部（ターゲット）
３    調停回路（選択回路）
３１    資源管理部
３２    データバッファ
３２ａ    バッファ
３３    入力ポート（入力部）
３４    調停器
３４ａ    ＬＲＵレジスタ
３４ｂ    選択部
３４ｃ    制御部
３５    セレクタ
３５ａ    転送部
３６    合流制御部
３６ａ    合流レジスタ
３６ｂ    通知部
【図１】
0006350098.tif 000002
【図２】
0006350098.tif 000003
【図３】
0006350098.tif 000004
【図４】
0006350098.tif 000005
【図５】
0006350098.tif 000006
【図６】
0006350098.tif 000007
【図７】
0006350098.tif 000008
【図８】
0006350098.tif 000009
【図９】
0006350098.tif 000010
【図１０】
0006350098.tif 000011
【図１１】
0006350098.tif 000012
【図１２】
0006350098.tif 000013
【図１３】
0006350098.tif 000014
【図１４】
0006350098.tif 000015
【図１５】
0006350098.tif 000016