(57)【特許請求の範囲】
【請求項１】
複数のプロセッサユニットを含むファットツリー構造の情報処理装置において、異なるプロセッサユニット間で伝送される信号の信号伝送方法であって、
あるプロセッサユニットから信号を発行するステップと、
複数のブリッジユニットによって前記信号を中継するステップと、
を含み、
前記信号を中継するステップは、
前記ブリッジユニットに信号を入力するステップと、
当該ブリッジユニットが、前記ファットツリー構造において当該ブリッジユニットが属する列の識別番号と、当該ブリッジユニットが属する行の階層番号と、送信先のプロセッサユニットが管理するブリッジユニットの列の識別番号と、に基づく所定の規則に従い出力先のバスを選択するステップと、
選択したバスへ前記信号を出力するステップと、
を含むことを特徴とする信号伝送方法。
【請求項２】
前記選択するステップは、前記ブリッジユニットが属する列の識別番号と、前記送信先のプロセッサユニットが管理するブリッジユニットの列の識別番号を、それぞれ２進数で表した際のビット列を、上位ビットから、前記ブリッジユニットが属する行の階層番号に応じた位まで比較した結果に基づき出力先のバスを選択することを特徴とする請求項１に記載の信号伝送方法。
【請求項３】
前記信号を中継するステップは、前記選択に応じて、前記ブリッジユニットを管理するプロセッサユニットが管理するバスのエンドポイントと、別のプロセッサユニットが管理するバスのエンドポイントとを中継するブリッジを介して前記信号を別のプロセッサユニットが管理するブリッジユニットへ出力するステップを含むことを特徴とする請求項１または２に記載の信号伝送方法。
【請求項４】
前記信号を中継するステップは、複数のブリッジユニットを経由して伝送される信号が、下流方向から上流方向へ１回のみの方向転換によって、前記送信先のプロセッサユニットへ到達するように出力先のバスが選択されることを特徴とする請求項１から３のいずれかに記載の信号伝送方法。
【請求項５】
複数のプロセッサユニットを含むファットツリー構造の情報処理装置において異なるプロセッサユニット間を伝送する信号を中継するブリッジユニットであって、
複数のバスブリッジと、
２つのプロセッサユニットが管理する２つのデバイスツリーのエンドポイント間の信号伝送を中継するエンドポイントブリッジと、
入力信号の出力先のバスを選択するスイッチルーティング回路と、
を備え、
前記スイッチルーティング回路は、前記ファットツリー構造において当該ブリッジユニットが属する列の識別番号と、当該ブリッジユニットが属する行の階層番号と、を設定するレジスタを備え、前記レジスタに設定された前記識別番号および前記階層番号と、前記入力信号の送信先のプロセッサユニットが管理するブリッジユニットの列の識別番号と、に基づき、所定の規則に従い出力先のバスを選択し、それに応じて前記信号が前記バスブリッジまたは前記エンドポイントブリッジのいずれかを通過するように出力を制御することを特徴とするブリッジユニット。
【請求項６】
前記スイッチルーティング回路は、前記ブリッジユニットが属する列の識別番号と、前記送信先のプロセッサユニットが管理するブリッジユニットの列の識別番号を、それぞれ２進数で表した際のビット列を、上位ビットから、前記ブリッジユニットが属する行の階層番号に応じた位まで比較した結果に基づき出力先のバスを選択することを特徴とする請求項５に記載のブリッジユニット。
【請求項７】
前記ファットツリー構造が２ｎ個のプロセッサユニットを有し、前記ブリッジユニットの階層番号ｍが０＜ｍ＜ｎであった場合、前記送信先のプロセッサユニットが管理するブリッジユニットの列の識別番号を２進数で表した際の数列をｔｎ［ｎ−１：０］、前記ブリッジユニットの識別番号を２進数で表した際の数列をｂｎ［ｎ−１：０］とすると、前記スイッチルーティング回路によって、前記ブリッジユニットの上流から入力した信号は、
ｔｎ［ｎ−１：ｍ］≠ｂｎ［ｎ−１：ｍ］
ならいずれかの下流のバスへ、
ｔｎ［ｎ−１：ｍ］＝ｂｎ［ｎ−１：ｍ］
なら
ｂｎ'［ｍ−１］＝ｔｎ［ｍ−１］
なる識別番号の２進数の数列ｂｎ'［ｎ−１：０］を有する列に属するブリッジユニットへ出力され、
前記ブリッジユニットの下流から入力した信号は、全て
ｂｎ'［ｍ−１］＝ｔｎ［ｍ−１］
なる識別番号２進数の数列ｂｎ'［ｎ−１：０］を有する列に属するブリッジユニットへ出力されることを特徴とする請求項５または６に記載のブリッジユニット。
【請求項８】
前記スイッチルーティング回路はさらに異なるパラメータに基づくルーティングの規則を実行するモードを有し、
前記ブリッジユニットは、
ユーザによる前記モードの選択に応じて、前記エンドポイントブリッジの出力信号と、前記バスブリッジの出力信号のいずれかを選択して有効な出力信号とするマルチプレクサをさらに備えることを特徴とする請求項５から７のいずれかに記載のブリッジユニット。
【請求項９】
複数のプロセッサユニットと、
異なるプロセッサユニット間を伝送する信号を中継するブリッジユニットと、
を備え、前記ブリッジユニットは、
１つのプロセッサユニットが管理するデバイスツリー内の信号伝送を中継するバスブリッジと、
２つのプロセッサユニットが管理する２つのデバイスツリーのエンドポイント間の信号伝送を中継するエンドポイントブリッジと、
異なるプロセッサユニット間を伝送する入力信号が最短経路で送信先のプロセッサユニットへ到達するように、自らが属するブリッジユニットのノードの識別番号と前記送信先のプロセッサユニットのノードの識別番号とに基づく所定の規則に従い、前記入力信号の出力先を前記バスブリッジおよび前記エンドポイントブリッジのいずれかから選択するスイッチルーティング回路と、
を備えることを特徴とする情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理技術に関し、特に複数の演算処理ユニットを有する情報処理装置、情報処理装置における信号伝送方法、および実装されるブリッジユニットに関する。
【背景技術】
【０００２】
近年のコンピュータはその機能が多様化し、それとともに接続されるデバイスも多岐に渡るようになった。これらのデバイスはバスを介してＣＰＵと相互に信号のやり取りを行う。ＣＰＵと直接接続するバスと、デバイス接続のためのポートを形成するバスを中継して、異種のバスの互換性を確保するためにはバスブリッジが用いられる。さらにバスブリッジを階層的に接続していくことにより同種のバスによるデバイスツリーを形成し、デバイスが接続できるポート数を増やすことができる。
【０００３】
一方、演算処理の高速化の要求に対応するために近年ではプロセッサを複数備えたマルチプロセッサ構成や、プロセッサユニットを複数備えたマルチホスト構成を有する情報処理装置が一般的に用いられるようになっている。これらの並列処理技術においては、１つのアプリケーションを複数のプロセッサまたは複数のホストに分散させて処理することによって、処理の高速化を図っている。マルチホスト構成の構造例としてはファットツリー構造が挙げられる（例えば、非特許文献１参照）。
【非特許文献１】C. E. Leiserson. Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing. IEEE Transactions on Computer, Vol. 34, No. 10, pp. 892.901, 1985
【発明の開示】
【発明が解決しようとする課題】
【０００４】
例えばマルチホスト構成を有する情報処理装置において、１つのアプリケーションを複数のプロセッサユニットに分散させて処理を行う場合、プロセッサユニットごとに管理するバスが異なるため、異なるデバイスツリー相互のアクセスが複雑となる。高速化を図るためにプロセッサユニットの数を増加させるほど、プロセッサユニット同士の信号の送受信の処理が複雑化し、アクセスに要する時間が増大してしまう傾向にある。
【０００５】
本発明はこのような課題に鑑みてなされたものであり、その目的は複数のプロセッサユニット間での信号の伝送を高速に行うことのできる技術を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は信号伝送方法に関する。この信号伝送方法は、複数のプロセッサユニットを含むファットツリー構造の情報処理装置において、異なるプロセッサユニット間で伝送される信号の信号伝送方法であって、あるプロセッサユニットから信号を発行するステップと、複数のブリッジユニットによって信号を中継するステップと、を含み、信号を中継するステップは、ブリッジユニットに信号を入力するステップと、ファットツリー構造において当該ブリッジユニットが属する列の識別番号と、当該ブリッジユニットが属する行の階層番号と、送信先のプロセッサユニットが管理するブリッジユニットの列の識別番号と、に基づき、出力先のバスを選択して信号を出力するステップと、を含むことを特徴とする。
【０００７】
本発明の別の態様はブリッジユニットに関する。このブリッジユニットは、複数のプロセッサユニットを含むファットツリー構造の情報処理装置において異なるプロセッサユニット間を伝送する信号を中継するブリッジユニットであって、複数のバスブリッジと、２つのプロセッサユニットが管理する２つのデバイスツリーのエンドポイント間の信号伝送を中継するエンドポイントブリッジと、入力信号の出力先のバスを選択するスイッチルーティング回路と、を備える。スイッチルーティング回路は、ファットツリー構造において当該ブリッジユニットが属する列の識別番号と、当該ブリッジユニットが属する行の階層番号と、を設定するレジスタを備え、レジスタに設定された識別番号および階層番号と、入力信号の送信先のプロセッサユニットが管理するブリッジユニットの列の識別番号と、に基づき、出力先のバスを選択し、それに応じて信号がバスブリッジまたはエンドポイントブリッジのいずれかを通過するように出力を制御することを特徴とする。
【０００８】
デバイスツリーはプロセッサユニットが位置するルートノードを起点として、ブリッジを多段にツリー状に接続し、ツリーの末端、すなわちエンドポイントに位置するデバイスへのアクセスを可能とする構成をいう。このデバイスツリー構造において、ツリーを構成するブリッジ、バス、エンドポイントは、ルートノードにあるプロセッサユニットによってそれぞれが識別され、管理される。
【０００９】
本発明のさらに別の態様は情報処理装置に関する。この情報処理装置は、複数のプロセッサユニットと、異なるプロセッサユニット間を伝送する信号を中継するブリッジユニットと、を備え、前記ブリッジユニットは、１つのプロセッサユニットが管理するデバイスツリー内の信号伝送を中継するバスブリッジと、２つのプロセッサユニットが管理する２つのデバイスツリーのエンドポイント間の信号伝送を中継するエンドポイントブリッジと、異なるプロセッサユニット間を伝送する入力信号が最短経路で送信先のプロセッサユニットへ到達するように、前記入力信号の出力先を前記バスブリッジおよび前記エンドポイントブリッジのいずれかから選択するスイッチルーティング回路と、を備えることを特徴とする。
【００１０】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１１】
本発明によれば、マルチホスト構成の情報処理装置における信号伝送処理を高速に行うことができる。
【発明を実施するための最良の形態】
【００１２】
まず本実施の形態の情報処理装置の基本的な構成について説明する。図１は情報処理装置に含まれるある単位の構成を模式的に示している。この構成は、例えばＰＣＩ（Peripheral Component Interconnect）のバスアーキテクチャを用いて実現できる。情報処理装置の構成単位１０は演算処理を行う２つのプロセッサユニット１２ａおよび１２ｂ、プロセッサユニット１２ａおよび１２ｂのローカルなバスと周辺機器を接続するためのＰＣＩなどのバスとを中継するホストブリッジ２２ａおよび２２ｂ、ＰＣＩｔｏＰＣＩブリッジなど同種のバス同士を中継するバスブリッジ２４ａ〜２４ｄ、他方のプロセッサユニットのデバイスツリーとのインターフェースを形成するエンドポイントブリッジ３０を含む。
【００１３】
エンドポイントブリッジ３０は、プロセッサユニット１２ａが管理するエンドポイント１８ａと、プロセッサユニット１２ｂが管理するエンドポイント１８ｂとの信号授受を中継する。ホストブリッジ２２ａはバス１４ａを介して、バスブリッジ２４ａ、２４ｂ、エンドポイント１８ａと信号の送受を行う。ホストブリッジ２２ｂはバス１４ｂを介して、バスブリッジ２４ｃ、２４ｄ、エンドポイント１８ｂと信号の送受を行う。ホストブリッジ２２ａ、バスブリッジ２４ａ、２４ｂ、エンドポイントブリッジ３０は１単位の信号送信ユニットとして、ブリッジチップ１６を形成する。
【００１４】
プロセッサユニット１２ａ、１２ｂなどのプロセッサユニット１２は例えば複数のプロセッサからなるマルチプロセッサ構造を有する。またプロセッサユニット１２は図示しないメインメモリやＩ／Ｏインターフェースなどを適宜含んでよい。エンドポイントブリッジ３０は、例えば一方のプロセッサユニット１２ａから他方のプロセッサユニット１２ｂへの信号をエンドポイント１８ａから取得し、エンドポイント１８ｂから送信する。これによりデバイスツリーまたいで伝送された信号は、異なるプロセッサユニット１２間を伝送する。エンドポイントブリッジ３０は入力信号に対し適宜変換処理を施し、出力先のデバイスツリーにおいて有効な信号を生成したうえで送信する。
【００１５】
同図は本実施の形態における情報処理装置のある構成単位１０を示しており、バスブリッジ２４ａ〜２４ｄにはさらにバス１４ｃ〜１４ｆがそれぞれ接続している。実際の情報処理装置ではこれらのバス１４ｃ〜１４ｆにさらなるバスブリッジまたはエンドポイントを設けてよい。その際、バス１４ａ、１４ｂのようにバス１４ｃ〜１４ｄを分岐させることにより、デバイスツリーを形成することができる。
【００１６】
同図では、各プロセッサユニット１２に対してバスブリッジ２４が２つ、エンドポイントブリッジ３０が１つ接続されているが、それらの個数はこれに限定されない。またプロセッサユニット１２は３つ以上設けてよく、あるプロセッサユニット１２から別のプロセッサユニット１２への信号送信は、エンドポイントブリッジ３０を介して行う。ここでプロセッサユニット間の信号送受信は後述するように、エンドポイントブリッジ３０を介して直接行う場合と、複数のエンドポイントブリッジ３０を通過させることにより、中間にあるプロセッサユニットのデバイスツリーを経由して行う場合とがある。
【００１７】
図２は図１で示した構成単位１０を実現するために、本実施の形態の情報処理装置に実装されるブリッジチップ１６の構成例を示している。ブリッジチップ１６は３つのバスブリッジ２４ａ、２４ｂ、２４ｅ、エンドポイント１８ａおよびエンドポイント１８ｂを含むエンドポイントブリッジ３０、ホストブリッジ２２、スイッチルーティング回路３２を含む。バスブリッジ２４ａ、ホストブリッジ２２、およびエンドポイントブリッジ３０は、ブリッジチップ１６の上流側に接続されたユニットやブリッジと信号の送受を行う。バスブリッジ２４ｂおよびバスブリッジ２４ｅは、ブリッジチップ１６の下流側に接続されたユニットやブリッジと信号の送受を行う。
【００１８】
バスブリッジ２４ａおよびホストブリッジ２２は、どちらか一方を有効とし、ブリッジチップ１６の上側に接続するユニットがプロセッサユニット１２であればホストブリッジ２２が、別のブリッジチップ１６であればバスブリッジ２４ａが使用される。同図のエンドポイント１８ａおよびエンドポイント１８ｂは、図１のエンドポイント１８ａおよび１８ｂに相当する。すなわち、エンドポイント１８ａはブリッジチップ１６を管理するプロセッサユニット１２ａのデバイスツリーに属し、エンドポイント１８ｂは他のプロセッサユニット、例えばプロセッサユニット１２ｂのデバイスツリーに属する。したがってプロセッサユニット１２ａから他のプロセッサユニットへの信号送受信はブリッジチップ３０を通過する。
【００１９】
スイッチルーティング回路３２は、バスブリッジ２４ａ、ホストブリッジ２２、エンドポイントブリッジ３０が取得した上流からの信号、バスブリッジ２４ｂまたはバスブリッジ２４ｅが取得した下流からの信号が適切な経路を通過するように、出力するブリッジの選択を行う。適切な経路とは例えば、あるプロセッサユニット１２ａから発行された信号が送信先のプロセッサユニット１２ｂへ到達するための最短経路である。スイッチルーティング回路３２は、経路選択のために参照される各種パラメータを設定するレジスタ３４を含む。パラメータについては後述する。
【００２０】
次に、本実施の形態においてスイッチルーティング回路３２が信号の経路を適切に選択する方法について説明する。まず本実施の形態における情報処理装置の構成について説明する。図３は図２で示したブリッジチップ１６を導入したファットツリー構造を有する情報処理装置を示している。図３（ａ）はプロセッサユニットが２つの場合の情報処理装置４０ａ、図３（ｂ）はプロセッサユニットが４つの場合の情報処理装置４０ｂ、図３（ｃ）はプロセッサユニットが８つの場合の情報処理装置４０ｃを示している。図３（ａ）において、プロセッサユニット１２ａおよび１２ｂを表す矩形内に示される数字「０」および「１」は、プロセッサユニット１２ごとに与えられる番号であり、以後、ノードＩＤと呼ぶ。
【００２１】
各プロセッサユニット１２には管理するブリッジチップ１６が縦方向に２つ連なっている。例えばプロセッサユニット１２ａにはブリッジチップ１６ａおよび１６ｂが連なっている。以後、このプロセッサユニット１２と複数のブリッジチップ１６の縦方向の列をノード列４２と呼ぶ。同図においてエンドポイントブリッジ３０ａは、ブリッジチップ１６ｂ内の斜線を施した矩形によって表される。ブリッジチップ１６ａまたはブリッジチップ１６ｂ内のその他の矩形は、ホストブリッジ２２またはバスブリッジ２４を表している。図３（ｂ）および図３（ｃ）も同様の方法で表示されており、プロセッサユニットが４つの場合は、各ノード列にブリッジチップ１６が３つ（図３（ｂ））、プロセッサユニットが８つの場合は、各ノード列にブリッジチップ１６が４つ（図３（ｃ））設けられる。
【００２２】
図３（ａ）において、例えばプロセッサユニット１２ａからプロセッサユニット１２ｂへ信号を送信する場合に、当該信号はノード列４２をまたいで伝送されることになる。このときのインターフェースがエンドポイントブリッジ３０ａまたは３０ｂである。すなわち、異なるノード列４２に属するブリッジチップ１６同士は、エンドポイントブリッジ３０を介して接続しており、ノード列４２をまたいで信号が伝送する場合は、必ず１つ以上のエンドポイントブリッジ３０を通過する。
【００２３】
上述の例における信号の経路は、プロセッサユニット１２ａ→ブリッジチップ１６ａ→ブリッジチップ１６ｂ（エンドポイントブリッジ３０ａ）→ブリッジチップ１６ｃ→プロセッサユニット１２ｂ、または、プロセッサユニット１２ａ→ブリッジチップ１６ａ→ブリッジチップ１６ｄ（エンドポイントブリッジ３０ｂ）→ブリッジチップ１６ｃ→プロセッサユニット１２ｂのいずれかとなる。
【００２４】
図３で示したようなファットツリー構造の情報処理装置において、各ブリッジチップ１６内のスイッチルーティング回路３２は、ノード列４２をまたぐ信号の伝送が最短経路で行われるように経路の選択を行う。最短経路とは、信号を別のノード列４２へ移動させるためにエンドポイントブリッジ３０を通過する回数が最小となる経路である。このためには、図３に示す構造において、あるプロセッサユニット１２から発行された信号が複数のブリッジチップ１６を経由して送信先のプロセッサユニット１２へ到達する間に、下流方向から上流方向へ信号の伝送方向が転じる回数を１回とする。
【００２５】
このような条件を満足する伝送経路を選択するためには、次に述べる法則を利用する。まず法則に用いるパラメータとして、先に述べたノードＩＤの他にブリッジチップ階層を導入する。図４はプロセッサユニットが８つの情報処理装置４０ｃにおける信号の最短経路とノードＩＤ、およびブリッジチップ階層との関係を示している。ここでブリッジチップ階層は各ブリッジチップ１６に対し、上流から下流に向けて昇順で付与される。図４の例におけるブリッジチップ階層はレベル「０」、レベル「１」、レベル「２」、レベル「３」となる。
【００２６】
一方、ノードＩＤは各ノード列４２に対し左から昇順で付与される。同図の場合、プロセッサユニットの数は８つであるため、ノードＩＤは左から「０」〜「７」と設定される。ここで、各ノードＩＤを２進数で表した場合を考える。表１は各ノードＩＤを１０進数と２進数で示しており、２進数の場合はビット位置を下位ビットからビット「０」、ビット「１」、ビット「２」、ビット「３」と名づける。なお、８＝２３であるため、ビット３は全てのノードＩＤにおいて「０」である。
【００２７】
【表１】
0004611901.tif 000002
【００２８】
このように設定されたノードＩＤおよびブリッジチップ階層を導入すると、信号の発行元であるノード列４２のノードＩＤと、信号の送信先であるノード列４２のノードＩＤとから、上流から伝送された信号が唯一方向を転じる際のブリッジチップ階層が一意に求まる。具体的には、発行元のノードＩＤと送信先のノードＩＤとを２進数で上位ビットから比較していき、連続して等しい値となるビットのうち、最下位のビット位置の数字が、方向を転じる際のブリッジチップ階層と等しくなる。
【００２９】
例えば図４において、ノードＩＤ「０」のプロセッサユニット１２ａから発行した信号を、ノードＩＤ「１」のプロセッサユニット１２ｂへ送信する場合を考える。ノードＩＤ「０」とノードＩＤ「１」を２進数で比較すると、ビット「３」からビット「１」までは同じ「０」という値である。そのうち最下位のビットがビット「１」であるため、信号が方向を転じるブリッジチップ階層がレベル「１」であることがわかる。これが信号の最短経路であり、図４の矢印４４で示されている。同様に、ノードＩＤ「１」のプロセッサユニット１２ｂから発行した信号を、ノードＩＤ「７」のプロセッサユニット１２ｃへ送信する場合は、ノードＩＤ「１」とノードＩＤ「７」を２進数で比較すると、ビット「３」のみが同じ「０」という値であるため、レベル「３」のブリッジチップ階層で信号を折り返す。この場合の経路は図４の矢印４６で示されている。
【００３０】
この法則は、情報処理装置を構成するプロセッサユニット１２の数や、信号の送信元、送信先のノード列４２のノードＩＤによらず当てはまる。そこでこの法則をふまえて各ブリッジチップ１６のスイッチルーティング回路３２を動作させることにより、信号を最短経路で所望のノード列４２へ到達させることができる。以下にスイッチルーティング回路３２によってなされる経路選択のアルゴリズムを示す。
【００３１】
まず、スイッチルーティング回路３２を動作させるための初期化処理について述べる。図５は一例としてプロセッサユニット１２が４つのファットツリー構造を有する情報処理装置４０ｂに対する初期化処理の様子を模式的に示している。まず図５（ａ）は初期化処理の第１段階として各ブリッジチップ１６にノードＩＤを設定することを示している。例えばプロセッサユニット１２ａは、同じノード列４２に属するブリッジチップ１６ａ、１６ｂ、１６ｅ内のスイッチルーティング回路３２に含まれるレジスタ３４に、自らのノードＩＤ「０」を設定する。他のノード列についても同様である。
【００３２】
次に図５（ｂ）は初期化処理の第２段階として、各ブリッジチップ１６にブリッジチップ階層を設定することを示している。例えばプロセッサユニット１２ａは、同じノード列４２に属するブリッジチップ１６ａ、１６ｂ、１６ｅ内のレジスタ３４に、ブリッジチップ階層、すなわちレベル「０」、レベル「１」、レベル「２」をそれぞれ設定する。他のノード列についても同様である。ブリッジチップ階層はデバイスツリーを構成する際にプロセッサユニット１２がそれぞれ把握している。
【００３３】
次に図５（ｃ）は初期化処理の第３段階として、各ブリッジチップ１６におけるポートの接続先のノード列のノードＩＤを設定することを示している。初期化処理の第１段階で、各ブリッジチップ１６にはノードＩＤが設定されているため、例えばプロセッサユニット１２ａは同じノード列に属するブリッジチップ１６ｅの接続先であるブリッジチップ１６ｆのノードＩＤの設定を参照することによって、ブリッジチップ１６ｅに含まれるエンドポイントブリッジ３０ｅの接続先のノードＩＤを「２」と設定する。これもスイッチルーティング回路３２に含まれるレジスタ３４に設定する。他のブリッジおよびノード列についても同様である。
【００３４】
次に上述のような設定を用いてスイッチルーティング回路３２が経路を選択する処理について述べる。図６から図８はブリッジチップ１６が信号を取得した際の経路選択処理の手順を示している。これらの図において、ｔｎ［ｎ−１：０］は送信先のノードＩＤを、ｂｎ［ｎ−１：０］は信号を取得したブリッジチップ１６のノードＩＤを表している。送信先のノードＩＤは、信号に含まれる情報である。
【００３５】
ここでｎは情報処理装置に含まれるプロセッサユニット１２の個数を２進数で表したときのビット数を表している。すなわちプロセッサユニット１２の個数は２ｎ個である。プロセッサユニット１２が８個のファットツリー構造であれば、ｎ＝３である。そしてｔｎ［ｎ−１：０］およびｂｎ［ｎ−１：０］はどちらもノードＩＤを２進数で表したときの各ビットの数値を示す数列を表す。例えばｔｎ［４：０］＝"０１１０１"の場合、ｔｎ［４］＝０、ｔｎ［３］＝１、ｔｎ［２］＝１、ｔｎ［１］＝０、ｔｎ［０］＝１である。ここでｔｎ［ｘ：ｘ］はｔ［ｘ］と等しいとする。上記の例ではｔｎ［３：３］＝ｔｎ［３］＝１である。
【００３６】
図６はブリッジチップ階層がレベル「０」にあるブリッジチップ１６、例えば図５のプロセッサユニット１２ａの直下に接続されたブリッジチップ１６ａにおける経路選択の処理手順を示している。信号が上流から伝送された場合（Ｓ１０のＹ）、当該ブリッジチップ１６のスイッチルーティング回路３２は、図２のバスブリッジ２４ｂまたはバスブリッジ２４ｅを介して信号を任意の下流に出力する（Ｓ１２）。信号が下流から伝送された場合は（Ｓ１０のＮ）、図２のホストブリッジ２２を介して信号を上流にあるプロセッサユニット１２ａに出力する（Ｓ１４）。
【００３７】
図７はブリッジチップ階層がレベル「ｍ」（０＜ｍ＜ｎ）のブリッジチップ１６における経路選択の処理手順を示している。例えば図５の４つのプロセッサユニットを有するファットツリー構造ではｎ＝２であるため、レベル「１」のブリッジチップ１６ｂが該当する。このブリッジチップ１６に上流または別のブリッジチップ１６に含まれるエンドポイントブリッジ３０から信号が伝送された場合（Ｓ２０のＹ）、ｔｎ［ｎ−１：ｍ］≠ｂｎ［ｎ−１：ｍ］であるとき（Ｓ２２のＹ）は、図２のバスブリッジ２４ｂまたはバスブリッジ２４ｅを介して信号を任意の下流に出力する（Ｓ２４）。ｔｎ［ｎ−１：ｍ］＝ｂｎ［ｎ−１：ｍ］であるとき（Ｓ２２のＮ）は、上述の法則における信号の折り返し点であるため、ｂｎ'「ｍ−１」＝ｔｎ［ｍ−１］となるノードＩＤ、ｂｎ'［ｎ−１：０］を有するノード列に属する上流のブリッジチップ１６へ図２のバスブリッジ２４ａを介して出力するか、当該ノード列に接続するエンドポイントブリッジ３０へ信号を出力する（Ｓ２６）。信号が下流から伝送された場合も（Ｓ２０のＮ）、Ｓ２２のＮの場合と同様の処理を行う（Ｓ２６）。
【００３８】
図８はブリッジチップ階層がレベル「ｎ」にあるブリッジチップ１６、例えば図５のブリッジチップ１６ｅにおける経路選択の処理手順を示している。この場合は図７のＳ２６と同様、ｂｎ'「ｍ−１」＝ｔｎ［ｍ−１］となるノードＩＤ、ｂｎ'［ｎ−１：０］を有するノード列に属する上流のブリッジチップ１６または当該ノード列に接続したエンドポイントブリッジ３０へ信号を出力する（Ｓ３０）。
【００３９】
次に上述のアルゴリズムによる経路選択の実例について説明する。図９は４つのプロセッサユニットを有するファットツリー構造の情報処理装置４０ｂにおいて、ノードＩＤ「０」のプロセッサユニット１２ａからノードＩＤ「３」のプロセッサユニット１２ｄへ信号を送信する際の経路を示している。このときｎ＝２、ｔn［１：０］＝"１１"である。
【００４０】
まずノードＩＤ「０」のブリッジチップ１６ａは、ブリッジチップ階層がレベル「０」であるためいずれかの下流へ出力する。図９ではブリッジチップ１６ｂに出力している（矢印５０）。次にブリッジチップ１６ｂはレベル「１」であるため、０＜ｍ＜ｎに該当する。ここでブリッジチップ１６ｂのノードＩＤは「０」のため、ｂｎ［１：０］＝"００"である。従ってｔｎ［１：１］＝ｔｎ［１］≠ｂｎ［１：１］＝ｂｎ［１］であるため、いずれかの下流へ出力する。図９ではブリッジチップ１６ｅに出力している（矢印５２）。
【００４１】
次にブリッジチップ１６ｅはレベル「２」でｎと等しいため、ノードＩＤのビット「１」がｔｎ［１］＝１である、ノードＩＤ「２」のノード列に属するブリッジチップ１６ｆへ出力する（矢印５４）。そしてブリッジチップ１６ｆはレベル「１」であるため、０＜ｍ＜ｎに該当する。矢印５４の伝送によってｔｎ［１：１］＝ｔｎ［１］＝ｂｎ［１：１］＝ｂｎ［１］となったため、さらにノードＩＤのビット「０」がｔｎ［０］＝１である、ノードＩＤ「３」のノード列に属するブリッジチップ１６ｇへ出力する（矢印５６）。これによりプロセッサユニット１２ａからプロセッサユニット１２ｄへの信号が最短経路で送信される。
【００４２】
次に経路選択の別の例を説明する。図１０は４つのプロセッサユニットを有するファットツリー構造の情報処理装置４０ｂにおいて、ノードＩＤ「３」のプロセッサユニット１２ｄからノードＩＤ「２」のプロセッサユニット１２ｃへ信号を送信する際の経路を示している。このときｎ＝２、ｔｎ［１：０］＝"１０"である。まずノードＩＤ「３」のブリッジチップ１６ｇは、ブリッジチップ階層がレベル「０」であるためいずれかの下流へ出力する。図１０ではブリッジチップ１６ｆに出力している（矢印６０）。
【００４３】
次にブリッジチップ１６ｆはレベル「１」であるため、０＜ｍ＜ｎに該当する。ここでブリッジチップ１６ｆのノードＩＤは「２」であるため、ｂｎ［１：０］＝"１０"である。従ってｔｎ［１：１］＝ｔｎ［１］＝ｂｎ［１］となり、ノードＩＤのビット「０」がｔｎ［０］＝０である、ノードＩＤ「２」のノード列に属するブリッジチップ１６ｉへ出力する（矢印６２）。これによりプロセッサユニット１２ｄからプロセッサユニット１２ｃへの信号が最短経路で送信される。
【００４４】
以上述べた、複数のプロセッサユニットによって構成されるファットツリー構造内でのルーティングの方法を、他のルーティング手法と組み合わせてブリッジチップ１６に実装し、２つ以上のモードを切り替えて使用できるようにしてもよい。図１１は２つのルーティングモードを切り替える機能を有するブリッジチップ１６の構成を示している。ブリッジチップ１６は、図２において示したブリッジチップ１６と同様、複数のバスブリッジ２４ａ〜２４ｄ、エンドポイント１８ａおよび１８ｂを含むエンドポイントブリッジ３０、スイッチルーティング回路３２、ホストブリッジ２２を含む。このときスイッチルーティング回路３２には、これまで述べたアルゴリズムの他、例えばバスブリッジ２４ｄ等に接続されるバスの規格に基づくアルゴリズムを実現するための回路が実装されている。例えばＰＣＩバスの場合は、ＢＡＲ（Base Address Register）に基づくアルゴリズムである。
【００４５】
さらにブリッジチップ１６には、ルーティングのモードによって信号を選択して出力するマルチプレクサ７０およびマルチプレクサ７２を設ける。マルチプレクサ７０は、エンドポイントブリッジ３０からの入力信号、またはバスブリッジ２４ｄからの入力信号を、モードの切り替わりによって選択し、スイッチルーティング回路３２に出力する。エンドポイントブリッジ３０からの入力信号に対してスイッチルーティング回路３２は、上述の最短経路を選択する手法のルーティングを行う。バスブリッジ２４ｄからの入力信号に対しては、例えばＢＡＲに基づくルーティングを行う。同様にマルチプレクサ７２も、エンドポイントブリッジ３０からの入力信号、またはバスブリッジ２４ｄからの入力信号を、モードの切り替わりによって選択し、ブリッジチップ１６に接続されたバスへ出力する。これにより、単一のブリッジチップにおいて複数のルーティング方法をサポートすることができ、汎用性が向上する。
【００４６】
以上述べた本実施の形態によれば、複数のプロセッサユニットを含む情報処理装置において、異なるプロセッサユニットを送信先とした信号を、ノードＩＤを用いたアルゴリズムによりルーティングを行い伝送する。これにより、信号を最短経路で送信先に到達させることができ、信号伝達にかかる時間が短縮できるため、効率のよい情報処理が可能となる。本実施の形態は、プロセッサユニットの数によらず適用できるため、多数のプロセッサユニットで分散させて処理を行うような高速処理を必要とするアプリケーションの実行においては、より効果的である。また本実施の形態はブリッジチップにおける回路変更によって実現できるため、バス帯域の拡張などハードウェアを改良した他の高速化対策と比較すると、設計面、コストの面において導入障壁が低い。さらにマルチプレクサを導入して他のルーティングアルゴリズムと選択できるようにすることで、ユーザのニーズに対応したより汎用性の高い実装形態を実現することができる。
【００４７】
以上、本発明を実施の形態をもとに説明した。上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【図面の簡単な説明】
【００４８】
【図１】本実施の形態の情報処理装置に含まれるある単位の構成を模式的に示す図である。
【図２】本実施の形態の情報処理装置に実装されるブリッジチップの構成例を示す図ある。
【図３】本実施の形態のブリッジチップを導入したファットツリー構造を有する情報処理装置を模式的に示す図である。
【図４】本実施の形態において、プロセッサユニットが８つのファットツリー構造において最短経路とノードＩＤ、およびブリッジチップ階層との関係を説明する図である。
【図５】プロセッサユニットが４つのファットツリー構造に対する初期化処理の様子を模式的に示す図である。
【図６】ブリッジチップ階層がレベル「０」にあるブリッジチップにおける経路選択の処理手順を示すフローチャートである。
【図７】ブリッジチップ階層がレベル「ｍ」（０＜ｍ＜ｎ）のブリッジチップにおける経路選択の処理手順を示すフローチャートである。
【図８】ブリッジチップ階層がレベル「ｎ」にあるブリッジチップにおける経路選択の処理手順を示すフローチャートである。
【図９】本実施の形態を適用したファットツリー構造における経路選択の実例について説明する図である。
【図１０】本実施の形態を適用したファットツリー構造における経路選択の実例について説明する図である。
【図１１】ブリッジチップにおいて２つのルーティングモードを切り替える機能を有するブリッジチップの構成を示す図である。
【符号の説明】
【００４９】
１２  プロセッサユニット、  １４  外部バス、  １６  ブリッジチップ、  １８  エンドポイント、  ２２  ホストブリッジ、  ２４  バスブリッジ、  ３０  エンドポイントブリッジ、  ３２  スイッチルーティング回路、  ４０  情報処理装置、  ４２  ノード列、  ７０  マルチプレクサ、  ７２  マルチプレクサ。
【図１】
0004611901.tif 000003
【図２】
0004611901.tif 000004
【図３】
0004611901.tif 000005
【図４】
0004611901.tif 000006
【図５】
0004611901.tif 000007
【図６】
0004611901.tif 000008
【図７】
0004611901.tif 000009
【図８】
0004611901.tif 000010
【図９】
0004611901.tif 000011
【図１０】
0004611901.tif 000012
【図１１】
0004611901.tif 000013