ノードコントローラ、リクエストの出力順序決定方法及びノード間通信システム
【課題】ノード間通信により他のノードへのアクセスする際の複数のリクエスト全体の処理性能を向上すること。
【解決手段】本発明にかかるノードコントローラは、複数のノードと接続され、自己のノード内の複数のプロセッサから複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出回路と、算出された優先度に基づいて、受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定回路と、決定されたリクエストを選択して要求先のノードへ出力する選択回路と、を備える。
【解決手段】本発明にかかるノードコントローラは、複数のノードと接続され、自己のノード内の複数のプロセッサから複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出回路と、算出された優先度に基づいて、受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定回路と、決定されたリクエストを選択して要求先のノードへ出力する選択回路と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノードコントローラ、リクエストの出力順序決定方法及びノード間通信システムに関し、特に、ノード間通信により他のノードへのアクセスする際のリクエストの送信順序を調停するためのノードコントローラ、リクエストの出力順序決定方法及びノード間通信システムに関する。
【背景技術】
【０００２】
大規模なコンピュータシステムは、複数の処理を並列して実行するために複数のプロセッサを有する。そして、複数のプロセッサを一つのノードとして管理する。さらに、このようなノードを複数有し、ノード間を接続し、各ノードの処理及びノード間通信により所定の処理を実現する。このような大規模なコンピュータシステムでは、ノード間でのデータ通信が頻繁に発生する。例えば、あるプロセッサにおける処理を完了するために、他のプロセッサへ処理を行わせてその結果を必要とする場合がある。その際、要求元のプロセッサは、要求先のプロセッサへのリクエストを送信し、レスポンスを受信する。そして、要求元と要求先が異なるノードに属する場合、ノード間通信が発生する。
【０００３】
特許文献１には、１つのメモリに対する複数のアクセスマスタの競合に対して柔軟、かつ、確実にレイテンシを保証するためのメモリアクセス制御回路に関する技術が開示されている。特許文献１に開示されるメモリアクセス制御回路は、複数のアクセスマスタとメモリとの間に設けられる。優先度比較回路は。優先度レジスタに保持される優先度を比較する。セレクタは、最も優先度の高いアクセスマスタにアクセスを許可する。優先度レジスタに保持される優先度は、アクセスが待たされるごとに減算値レジスタの値が減算されることによって上昇する。これにより、アクセスされやすくなる。連続アクセス回数レジスタは、連続アクセス回数を保持する。そして、連続アクセス回数がアクセス上限回数レジスタの値に達すると、次のアクセス要求があったときに優先度レジスタに保持される初期値の優先度が低く抑えられる。
【０００４】
また、一般に、ノード間通信におけるリクエストの処理性能を向上させるためには、特定のリクエストに優先度をつけ、優先度の高いリクエストを先に送信し、当該リクエストを優先して処理させることにより性能を向上してきた。例えば、複数のリクエストに依存関係がある場合には、先に処理すべきリクエストの優先度を予め高く設定しておくことで、後続のリクエストを効率的に処理することができる。このような複数のリクエストに依存関係は、論理的に定まるものであるため、事前に優先度を設定することが可能である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−１７３８５９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、近年の複数のノードを用いた大規模なコンピュータシステムでは、ノード数が多数であり、ノード間の接続関係が複雑である。そして、ノード間の接続関係は、基本的に、複数のリクエストにおいて論理的に定まる依存関係とは無関係である。例えば、ノード間の接続関係は、全体の処理パフォーマンスやハードウェアに費やすことができるコスト等により変動するものである。そのため、同じリクエストであっても、ノードの配置や数によっては、経由するノード数つまり当該リクエストが要求先に到達するために要する時間に大きな差が出る場合がある。その場合、同じリクエストについての全体の処理時間に差が出る。よって、上述した依存関係に基づいて予めリクエストの優先度を設定することには限界があるという問題点がある。
【０００７】
例えば、後続のリクエストのＨＯＰ数がより大きい場合、優先度に従ってＨＯＰ数の小さいリクエストを先に送信してしまう場合がありえる。その場合、例え、優先度の高いリクエストの処理が完了したとしても、後続のリクエストが完了しないために、さらに後のリクエストが実行できないこととなる。そのため、リクエストの送信順序の調停に参加するタイミングによっては、処理を開始するまでに時間がかかってしまい、性能が低下してしまうことがあった。
【０００８】
尚、特許文献１は、ノード間通信における上述した課題を解決するためのものではない。
【０００９】
本発明は、このような問題点を解決するためになされたものであり、ノード間通信により他のノードへのアクセスする際の複数のリクエスト全体の処理性能を向上するためのノードコントローラ、リクエストの出力順序決定方法及びノード間通信システムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の第１の態様にかかるノードコントローラは、複数のノードと接続され、自己のノード内の複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出回路と、前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定回路と、前記決定されたリクエストを選択して前記要求先のノードへ出力する選択回路と、を備える。
【００１１】
本発明の第２の態様にかかるリクエストの出力順序決定方法は、第１のノード内の第１のプロセッサから第２のノード内のプロセッサへの第１のリクエストと、当該第１のノード内の第２のプロセッサから第３のノード内のプロセッサへの第２のリクエストとを同時に受け付け、前記第１のリクエスト及び前記第２のリクエストの要求元に応じた第１の優先度と第２の優先度を算出し、前記第１の優先度と前記第２の優先度に基づいて、前記第１のリクエスト及び前記第２のリクエストのいずれを出力すべきかを決定し、前記決定されたリクエストを選択して前記要求先のノードへ出力する。
【００１２】
本発明の第３の態様にかかるノード間通信システムは、複数のノードと接続され、複数のプロセッサと、当該複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出手段と、前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定手段と、前記決定されたリクエストを選択して前記要求先のノードへ出力する選択手段と、を備えるノードコントローラとを有するノードを含む。
【発明の効果】
【００１３】
本発明により、ノード間通信により他のノードへのアクセスする際の複数のリクエスト全体の処理性能を向上するためのノードコントローラ、リクエストの出力順序決定方法及びノード間通信システムを提供することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態１にかかるノード間通信システムの構成を示すブロック図である。
【図２】本発明の実施の形態１にかかるアクセス調停方法の処理の流れを示すフローチャートである。
【図３】本発明の実施の形態２にかかるコンピュータシステムの構成を示すブロック図である。
【図４】本発明の実施の形態２にかかるノードコントローラの構成を示すブロック図である。
【図５】本発明の実施の形態２にかかるテーブルの例を示す図である。
【図６】本発明の実施の形態２にかかるアクセス調停方法の流れを説明するためのフローチャートである。
【図７】本発明の実施の形態２にかかるセレクト係数の再設定処理の流れを説明するためのフローチャートである。
【図８】ラウンドロビンを適用した場合のリクエストの処理速度を説明するための図である。
【図９】本発明の実施の形態２にかかるリクエストの処理速度を説明するための図である。
【発明を実施するための形態】
【００１５】
以下では、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略する。
【００１６】
＜発明の実施の形態１＞
図１は、本発明の実施の形態１にかかるノード間通信システム１００の構成を示すブロック図である。ノード間通信システム１００は、少なくともノード１と、ノード２と、ノード３とを備える。ノード１乃至３は、それぞれ、複数のプロセッサを搭載した汎用的なコンピュータ装置である。そして、ノード１乃至３は、それぞれ信号線等により接続されている。これにより、各ノードに含まれるプロセッサが他のノードに含まれるプロセッサに対する処理要求を送受信することができる。
【００１７】
ノード１は、プロセッサ１１ａ、１１ｂ、・・・及び１１ｎと、ノードコントローラ１２とを備える。プロセッサ１１ａ、１１ｂ、・・・及び１１ｎは、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）である。また、各プロセッサは、相互に接続されている。そして、各プロセッサは、それぞれ独立して所定の処理を行う。その際、各プロセッサは、必要に応じてプロセッサ間通信を行う。例えば、プロセッサ１１ａは、プロセッサ１１ｂに対して処理要求すなわちリクエスト）を送信する。そして、プロセッサ１１ｂは、当該リクエストに応じた処理を実行し、リクエスト結果をプロセッサ１１ａへ返信する。その後、プロセッサ１１ａは、プロセッサ１１ｂから受信したリクエスト結果に応じて後続の処理を実行する。
【００１８】
また、プロセッサ１１ａ、１１ｂ、・・・及び１１ｎは、ノードコントローラ１２とそれぞれ接続されている。そして、各プロセッサは、リクエストを他のノードつまりノード２または３のいずれかに属するプロセッサへ送信する場合がある。その場合、各プロセッサは、ノードコントローラ１２を介して他のノードに属するプロセッサとの通信を行う。
【００１９】
ノードコントローラ１２は、各プロセッサからノード２又は３を要求先とした複数のリクエストを受け付け、受け付けた複数のリクエストの出力を制御する。また、ノードコントローラ１２は、ノード２又は３からリクエストを受け付け、プロセッサ１１ａ、１１ｂ、・・・及び１１ｎのいずれかへ当該リクエストを出力する。
【００２０】
ノードコントローラ１２は、優先度算出回路１３と、決定回路１４と、選択回路１５とを備える。優先度算出回路１３は、自己のノード内の複数のプロセッサから複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する。決定回路１４は、算出された優先度に基づいて、受け付けた複数のリクエストのうち出力すべきリクエストを決定する。選択回路１５は、決定されたリクエストを選択して前記要求先のノードへ出力する。尚、実際には、ノードコントローラ１２は、選択回路１５により出力されたリクエストについて、所定の処理を行った上でノード１の外部へ出力するが、当該所定の処理は、一般的なものであるため、詳細な説明を省略する。
【００２１】
ノード２は、複数のプロセッサ２１と、ノードコントローラ２２とを備える。また、ノード３は、複数のプロセッサ３１と、ノードコントローラ３２とを備える。尚、ノード２及び３は、ノード１と同等の機能を有するため、詳細な説明を省略する。つまり、プロセッサ２１及び３１は、プロセッサ１１ａ等と同等である。また、ノードコントローラ２２及び３２は、ノードコントローラ１２と同等である。
【００２２】
尚、ノード１乃至３が搭載するプロセッサの数は、図示したものに限定されない。例えば、ノード１には、プロセッサを１以上搭載していればよい。
【００２３】
図２は、本発明の実施の形態１にかかるアクセス調停方法の処理の流れを示すフローチャートである。まず、ノードコントローラ１２は、プロセッサ１１ａ〜１１ｎから複数のリクエストを受け付ける（Ｓ１１）。次に、優先度算出回路１３は、各リクエストの優先度を算出する（Ｓ１２）。そして、決定回路１４は、優先度に基づいて出力すべきリクエストを決定する（Ｓ１３）。その後、選択回路１５は、決定されたリクエストを選択して出力する（Ｓ１４）。
【００２４】
また、本発明の実施の形態１にかかるアクセス調停方法は、ノード間通信システム１００が３つのノードを有する場合に、少なくとも以下のように言い換えることができる。まず、第１のノード内の第１のプロセッサから第２のノード内のプロセッサへの第１のリクエストと、当該第１のノード内の第２のプロセッサから第３のノード内のプロセッサへの第２のリクエストとを同時に受け付ける。次に、第１のリクエスト及び第２のリクエストの要求元に応じた第１の優先度と第２の優先度を算出する。そして、第１の優先度と第２の優先度に基づいて、第１のリクエスト及び第２のリクエストのいずれを出力すべきかを決定する。その後、決定されたリクエストを選択して前記要求先のノードへ出力することを特徴とするリクエストの出力順序決定方法。
【００２５】
例えば、複数のリクエストの要求先のノードが異なる場合に、優先度を単にリクエストの種別により定めるのではなく、要求先のノードに応じて算出する。これにより、ノードの配置や接続状態によって、リクエストの送信時間に差が出る場合等を考慮して優先度を求めることができる。そのため、本発明の実施の形態１により、ノードの位置関係が無視された場合に比べて、ノード間通信により他のノードへのアクセスする際の複数のリクエスト全体の処理性能を向上することができる。
【００２６】
＜発明の実施の形態２＞
図３は、本発明の実施の形態２にかかるコンピュータシステム１００ａの構成を示すブロック図である。コンピュータシステム１００ａは、上述した実施の形態１にかかるノード間通信システム１００の一実施例である。コンピュータシステム１００ａは、ノード１０１乃至１０８を備える。尚、コンピュータシステム１００ａが備えるノード数はこれに限定されない。
【００２７】
ノード１０１は、ノードコントローラ１１１と、プロセッサ１１２乃至１１５とを備える。すなわち、ノードコントローラ１１１と、プロセッサ１１２乃至１１５とを一つの単位とし、それらを纏めたものをノード１０１と呼ぶ。ノードコントローラ１１１と、プロセッサ１１２乃至１１５とは、それぞれ一対一で信号線により接続されている。同様に、ノード１０２は、ノードコントローラ１２１と、プロセッサ１２２乃至１２５とを備える。そして、ノードコントローラ１２１と、プロセッサ１２２乃至１２５とは、それぞれ一対一で信号線により接続されている。
【００２８】
その他、ノード１０３、１０４、１０５、１０６、１０７及び１０８は、それぞれノードコントローラ１３１、１４１、１５１、１６１、１７１及び１８１を備え、プロセッサも複数備えているが、図示を省略する。
【００２９】
ここで、図３にかかるノード間の接続関係ついて以下に説明する。図３では、各ノードは、隣接するノード間のノードコントローラ同士が信号線で一対一に接続されている。これにより、ノード間のアクセスを実現する。
【００３０】
具体的には、ノードコントローラ１１１は、隣接するノードコントローラ１２１、１３１、１４１、１７１及び１８１と、信号線３０５、３０６、３０７、３０１及び３０２を介して一対一に接続されている。同様に、ノードコントローラ１２１は、隣接するノードコントローラ１１１、１３１、１４１、１７１及び１８１と、信号線３０５、３０８、３０９、３０３及び３０４を介して一対一に接続されている。ノードコントローラ１３１は、隣接するノードコントローラ１１１、１２１、１４１、１５１及び１６１と、信号線３０６、３０８、３１０、３１１及び３１２を介して一対一に接続されている。ノードコントローラ１４１は、隣接するノードコントローラ１１１、１２１、１３１、１５１及び１６１と、信号線３０７、３０８、３１０、３１３及び３１４を介して一対一に接続されている。ノードコントローラ１５１は、隣接するノードコントローラ１３１、１４１及び１６１と、信号線３１１、３１３及び３１５を介して一対一に接続されている。ノードコントローラ１６１は、隣接するノードコントローラ１３１、１４１及び１５１と、信号線３１２、３１４及び３１５を介して一対一に接続されている。ノードコントローラ１７１は、隣接するノードコントローラ１１１、１２１及び１８１と、信号線３０１、３０３及び３１６を介して一対一に接続されている。ノードコントローラ１８１は、隣接するノードコントローラ１１１、１２１及び１７１と、信号線３０２、３０４及び３１６を介して一対一に接続されている。その他、ノード１０５、１０６、１０７及び１０８の接続関係は、図示及び説明を省略する。
【００３１】
ノードコントローラ同士が接続されていないものとの間のアクセスは、間に別のノードコントローラを挟んでアクセスする。つまり、図３では、ノード１０１及び１０２とノード１０５及び１０６とは直接接続されておらず、ノード１０３又は１０４を介してノード間通信を行う必要があることを示す。例えば、ノードコントローラ１１１からノードコントローラ１６１へアクセスする場合には、ノードコントローラ１３１を経由し、信号線３０６及び３１２を介してアクセスするか、ノードコントローラ１４１を経由し、信号線３０７及び３１４を介してアクセスする。この際のアクセスする経路の決定は、公知の技術を用いることができるため、詳細な説明を省略する。
【００３２】
図４は、本発明の実施の形態２にかかるノードコントローラ１１１の構成を示すブロック図である。特に、図４では、ノードコントローラ１１１の構成のうち、プロセッサ１１２乃至１１５から受け付けたリクエストを出力する際の出力順序を決定するための構成について示している。そのため、ノードコントローラ１１１における他の構成については、図示及び説明を省略する。
【００３３】
ノードコントローラ１１１は、テーブル２０１と、リクエスト格納バッファ２０２乃至２０５と、セレクト係数格納レジスタ２０６乃至２０９と、セレクト係数生成回路２１０乃至２１３と、リクエスト保持レジスタ２１４乃至２１７と、セレクト係数保持レジスタ２１８乃至２２１と、セレクト係数調停回路２２２乃至２２５と、リクエスト調停回路２２６と、セレクタ２２７とを備える。
【００３４】
テーブル２０１は、プロセッサから発行されるリクエストに含まれる要求先のノードと、ホップ数とを対応付けて格納する記憶部である。ここで、ホップ数とは、リクエストが自己のノードから要求先のノードへ到達するために経由するノード数である。または、ホップ数は、現在のリクエストの位置からリクエストの送信先までにかかる時間の単位を示すものということもできる。
【００３５】
図５は、本発明の実施の形態２にかかるテーブルの例を示す図である。ここでは、例として、テーブル２０１に＃４０１〜＃４０５の５つのレコードが予め登録されているものとする。"ＤＩＮＤ"は、リクエストに含まれる要求先を２進数で表現した値である。"ＨＯＰ数"は、上述したホップ数を示す。尚、図５に示した値は、図３に示した各ノードやその接続関係とは対応しないものとする。また、テーブル２０１に登録された値は、コンピュータシステム１００ａにおけるノードの接続関係を変更した場合に、適宜、設定変更されるものとする。
【００３６】
ここで、リクエスト格納バッファ２０２、リクエスト保持レジスタ２１４、セレクト係数生成回路２１０、セレクト係数格納レジスタ２０６、セレクト係数調停回路２２２及びセレクト係数保持レジスタ２１８は、プロセッサ１１２から出力されるリクエストに対する処理を行う。同様に、リクエスト格納バッファ２０３、リクエスト保持レジスタ２１５、セレクト係数生成回路２１１、セレクト係数格納レジスタ２０７、セレクト係数調停回路２２３及びセレクト係数保持レジスタ２１９は、プロセッサ１１３から出力されるリクエストに対する処理を行う。リクエスト格納バッファ２０４、リクエスト保持レジスタ２１６、セレクト係数生成回路２１２、セレクト係数格納レジスタ２０８、セレクト係数調停回路２２４及びセレクト係数保持レジスタ２２０は、プロセッサ１１４から出力されるリクエストに対する処理を行う。リクエスト格納バッファ２０５、リクエスト保持レジスタ２１７、セレクト係数生成回路２１３、セレクト係数格納レジスタ２０９、セレクト係数調停回路２２５及びセレクト係数保持レジスタ２２１は、プロセッサ１１５から出力されるリクエストに対する処理を行う。そのため、以下では、プロセッサ１１２に対応する構成を中心に説明し、プロセッサ１１３乃至１１５に対応する構成については、適宜、説明を省略する。
【００３７】
リクエスト格納バッファ２０２は、プロセッサ１１２から出力されたリクエストを格納するバッファである。リクエスト格納バッファ２０２は、複数のリクエストを格納することが可能であり、ＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）方式により後段のリクエスト保持レジスタ２１４へリクエストを出力する。
【００３８】
セレクト係数格納レジスタ２０６は、後述するリクエスト調停回路２２６において複数のリクエストを調停する際の優先度を示した値であるセレクト係数を格納するレジスタである。セレクト係数格納レジスタ２０６に格納できる値の数は、リクエスト格納バッファ２０２に格納できるリクエスト数と同数である。
【００３９】
セレクト係数生成回路２１０は、プロセッサから出力されたリクエストから要求先を抽出する。そして、セレクト係数生成回路２１０は、抽出した要求先に対応するホップ数をテーブル２０１から取得する。その後、セレクト係数生成回路２１０乃至２１３は、取得したホップ数をデコードする。つまり、セレクト係数生成回路２１０は、プロセッサ１１２から受け付けたリクエストについて、リクエストの要求先のノードに対応付けられたホップ数をテーブル２０１から取得して、セレクト係数を算出する。
【００４０】
そのため、セレクト係数生成回路２１０乃至２１３は、プロセッサ１１２乃至１１５から外部のノードに属するプロセッサを要求先とした複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じたセレクト係数を算出するといえる。また、セレクト係数生成回路２１０乃至２１３は、ホップ数が大きいほどセレクト係数をより高く算出するといえる。
【００４１】
また、セレクト係数生成回路２１０は、リクエスト保持レジスタ２１４に保持しているリクエストがリクエスト調停回路２２６における調停により出力すべきリクエストとして決定されなかった場合に、セレクト係数格納レジスタ２０６に格納されている各セレクト係数に１を加算する。すなわち、セレクト係数生成回路２１０は、リクエスト格納バッファ２０２にリクエストが格納されており、かつ、当該リクエストがリクエスト保持レジスタ２１４へ出力されなかったときに、調停の対象外となったリクエストにおけるセレクト係数についてより優先度が高くなるように更新する。よって、
【００４２】
そのため、セレクト係数格納レジスタ２０６には、セレクト係数生成回路２１０により算出された値をセレクト係数として格納する。
【００４３】
リクエスト保持レジスタ２１４乃至２１７は、リクエスト調停回路２２６における調停の対象となるリクエストを保持するレジスタである。例えば、リクエスト保持レジスタ２１４には、リクエスト格納バッファ２０２にリクエストが格納されている順番に格納される。また、リクエスト格納バッファ２０２にリクエストが格納されていない場合、リクエスト保持レジスタ２１４には、プロセッサ１１２から出力されたリクエストがリクエスト格納バッファ２０２を経由せずに、直接、格納される。
【００４４】
セレクト係数保持レジスタ２１８は、リクエスト調停回路２２６における調停対象のリクエストに対応するセレクト係数を格納するレジスタである。具体的には、セレクト係数保持レジスタ２１８には、後述するセレクト係数調停回路２２２において出力されたセレクト係数が格納される。つまり、セレクト係数保持レジスタ２１８乃至２２１は、それぞれリクエスト保持レジスタ２１４乃至２１７に対応する。
【００４５】
セレクト係数調停回路２２２は、セレクト係数生成回路２１０、セレクト係数格納レジスタ２０６及びリクエスト調停回路２２６から出力される３つのセレクト係数とを調停する。つまり、セレクト係数調停回路２２２は、上述した３つのセレクト係数のいずれかを選択してセレクト係数保持レジスタ２１８へ出力する。例えば、リクエスト調停回路２２６によりリクエスト保持レジスタ２１４に格納されたリクエストが出力すべきリクエストとして決定された場合、セレクト係数調停回路２２２は、セレクト係数生成回路２１０又はセレクト係数格納レジスタ２０６から出力されるセレクト係数を出力する。このとき、リクエスト格納バッファ２０２にリクエストが格納済みである場合には、セレクト係数格納レジスタ２０６から出力されるセレクト係数を選択し、リクエスト格納バッファ２０２にリクエストが格納されていない場合には、セレクト係数生成回路２１０から出力されるセレクト係数を選択する。また、リクエスト調停回路２２６によりリクエスト保持レジスタ２１４に格納されたリクエストが出力すべきリクエストとして決定されなかった場合、リクエスト調停回路２２６から出力されるセレクト係数を選択する。
【００４６】
リクエスト調停回路２２６は、セレクト係数保持レジスタ２１８乃至２２１に格納されたセレクト係数に基づき調停して、出力すべきリクエストを決定し、セレクタ２２７へ通知する。すなわち、リクエスト調停回路２２６は、リクエスト保持レジスタ２１４乃至２１７に格納された複数のリクエスト、つまり調停対象のリクエストのうち出力すべきリクエストを決定し、リクエスト保持レジスタ２１４乃至２１７のいずれを選択すべきかをセレクタ２２７に通知する。
【００４７】
また、リクエスト調停回路２２６は、調停により出力対象から漏れたリクエストに対し、決められたルールを基にセレクト係数を再設定し、セレクト係数調停回路２２２乃至２２５へ出力する。つまり、リクエスト調停回路２２６は、調停対象のリクエストのうち出力すべきリクエストとして決定されなかった未決定リクエストについて、所定の基準に基づいてセレクト係数をより高く更新する。このとき、セレクト係数生成回路２１０乃至２１３は、調停対象のリクエストの後に受け付けた後続リクエストについてセレクト係数を算出する。その後、リクエスト調停回路２２６は、未決定リクエストについて更新されたセレクト係数と、後続リクエストについて算出されたセレクト係数とに基づいて、出力すべきリクエストを決定する。
【００４８】
さらに、リクエスト調停回路２２６は、後続リクエストの要求元と未決定リクエストの要求元とが同一のプロセッサである場合、当該後続リクエストを調停の対象外とする。そしてセレクト係数生成回路２１０乃至２１３は、対象外とされた後続リクエストのセレクト係数をより高く更新する。
【００４９】
セレクタ２２７は、リクエスト調停回路２２６から通知を受けたリクエストを選択して出力する。つまり、セレクタ２２７は、リクエスト調停回路２２６により出力すべきと決定されたリクエストを選択して要求先のノードへ出力する。
【００５０】
ここで、第１のリクエストと第２のリクエストを受け付け、第１のリクエストについて算出されるセレクト係数を第１の優先度、第２のリクエストについて算出されるセレクト係数を第２の優先度とした場合について、本発明の実施の形態２に係る動作を説明する。セレクト係数生成回路は、第１のリクエストにおけるホップ数が、第２のリクエストにおけるホップ数より大きい場合に、第１の優先度を第２の優先度より高く算出する。そして、リクエスト調停回路２２６は、第１のリクエストを出力すべきリクエストとして決定する。
【００５１】
図６は、本発明の実施の形態２にかかるアクセス調停方法の流れを説明するためのフローチャートである。まず、前提として、テーブル２０１には、予め自己のノードから各リクエストの要求先に応じたホップ数を格納済みであるものとする。
【００５２】
そして、ノードコントローラ１１１は、プロセッサ１１２乃至１１５からリクエストを受け付け、それぞれをリクエスト格納バッファ２０２乃至２０５に格納する（Ｓ２１）。そして、調停対象となるリクエストは、リクエスト保持レジスタ２１４乃至２１７に保持される。次に、セレクト係数生成回路２１０乃至２１３は、受け付けたリクエストについて、テーブル２０１を参照してセレクト係数を算出し、セレクト係数格納レジスタ２０６乃至２０９に格納する（Ｓ２２）。図５の例では、リクエストの要求先のＤＮＩＤが"０００"の場合、ホップ数は"１０"となる（＃４０１）。
【００５３】
その後、リクエスト調停回路２２６は、調停する（Ｓ２３）。つまり、リクエスト調停回路２２６は、リセレクト係数保持レジスタ２１８乃至２２１に格納済みのセレクト係数を比較して、対応するリクエスト保持レジスタ２１４乃至２１７に格納済みのリクエストのいずれを出力すべきかを決定する。そして、リクエスト調停回路２２６は、決定したリクエストをセレクタ２２７に通知する。
【００５４】
このとき、リクエスト調停回路２２６の決定の基準としては、第一にセレクト係数が大きいほうから調停が優先され、第二にセレクト係数が同じ値であった場合にはセレクタの番号が小さい番号から調停していくものとする。但し、リクエスト調停回路２２６による決定の基準はこれに限定されない。
【００５５】
その後、セレクタ２２７は、リクエスト調停回路２２６により決定されたリクエストを選択して出力する（Ｓ２４）。また、リクエスト調停回路２２６は、未決定リクエストのセレクト係数を更新する（Ｓ２５）。また、この間、ステップＳ２１において、後続のリクエストを受け付けた場合、ステップＳ２２において、セレクト係数生成回路２１０乃至２１３は、後続リクエストにおけるセレクト係数を算出する。また、ステップＳ２５と併せて、セレクト係数生成回路２１０乃至２１３は、未決定リクエストの後続リクエストのセレクト係数について上述したように更新する。
【００５６】
そして、ステップＳ２３に戻り、リクエスト調停回路２２６は、出力されたリクエストの後続リクエストと、未決定リクエストのいずれを出力すべきかを決定する。以後、リクエストの受け付けがなくなるまで繰り返し実行される。
【００５７】
ここで、リクエスト調停回路２２６におけるセレクト係数の再設定方法の一例を説明する。尚、本発明の実施の形態２にかかるセレクト係数の再設定方法はこれに限定されない。リクエスト調停回路２２６は、未決定リクエストについてセレクト係数を更新する際の所定の基準として、出力すべきリクエストとして決定されたリクエストのセレクト係数と、未決定のリクエストのセレクト係数と、複数のノードのうち自己のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いる。
【００５８】
図７は、本発明の実施の形態２にかかるセレクト係数の再設定処理の流れを説明するためのフローチャートである。まず、リクエスト調停回路２２６は、決定リクエストと未決定リクエストとのセレクト係数の差分を算出する（Ｓ３１）。決定リクエストとは、調停により出力すべきと決定されたリクエストである。また、未決定リクエストとは、調停により次点だったリクエストである。
【００５９】
次に、リクエスト調停回路２２６は、ステップＳ３１により算出された差分がテーブル２０１に格納されたホップ数のうち最大値である最大ホップ数の１／２以上であるか否かを判定する（Ｓ３２）。すなわち、以下の（１）式を満たすか否かを判定する。
差分 ≧ 最大ホップ数×１／２・・・（１）
【００６０】
ステップＳ３２において、１／２以上であると判定した場合、リクエスト調停回路２２６は、差分の１／２の値に、調停待ち分の１を足した値を、セレクト係数に足す（Ｓ３３）。すなわち、以下の（２）式によりセレクト係数を更新する。
セレクト係数＝ セレクト係数 ＋ 差分×１／２ ＋ １ ・・・（２）
【００６１】
ステップＳ３２において、１／２未満であると判定した場合、リクエスト調停回路２２６は、差分に調停待ち分の１を足した値をセレクト係数に足す（Ｓ３４）。つまり、以下の（３）式によりセレクト係数を更新する。
セレクト係数＝ セレクト係数 ＋ 差分 ＋ １ ・・・（３）
【００６２】
尚、セレクト係数の小数点が発生した場合には切り上げて計算する。そして、リクエスト調停回路２２６は、図７の処理を未決定リクエストの全てについて実行する。
【００６３】
以下に、具体例を示して説明する。まず、図５の例では、最大ホップ数が"２５"である。そのため、ステップＳ３２の比較に用いる比較値は、最大ホップ数の１／２である"１２．５"となる。また、以下では、リクエストＡ、Ｂ、Ｃ及びＤを対象とする。そして、リクエストＡ、Ｂ、Ｃ及びＤのＤＩＮＤは、"０１０"、"１００"、"０１１"及び"００１"であるものとする。そして、リクエストＤは、システム内でアクセスネックとなりうるリクエストであるものとする。以下、図６及び図７に沿って説明する。
【００６４】
まず、ノードコントローラ１１１は、プロセッサ１１２乃至１１４からリクエストＡ、Ｂ及びＣを同時に受け付け、それぞれをリクエスト格納バッファ２０２乃至２０４に格納する（Ｓ２１）。そして、リクエストＡ、Ｂ及びＣは、リクエスト保持レジスタ２１４乃至２１６に格納されたものとする。つまり、３つのリクエストＡ、Ｂ及びＣが同時に調停対象となったものとする。
【００６５】
次に、セレクト係数生成回路２１０乃至２１２は、リクエストＡ、Ｂ及びＣのＤＩＮＤに基づきテーブル２０１からホップ数"５"、"５"及び"２０"を取得し、セレクタ係数としてセレクト係数格納レジスタ２０６乃至２０８に格納する（Ｓ２２）。併せて、当該セレクト係数がセレクト係数保持レジスタ２１８乃至２２０にも格納される。
【００６６】
そして、リクエスト調停回路２２６は、３つのセレクタ係数を比較し、最大値である"２０"に対応するリクエストＣを出力すべきリクエストとして決定する（Ｓ２３）。そして、リクエスト調停回路２２６は、リクエストＣが決定した旨をセレクタ２２７に通知する（Ｓ２４）。
【００６７】
併せて、リクエスト調停回路２２６は、調停の勝者であるリクエストＣのセレクト数"２０"と調停の次点であるリクエストＡ及びＢのセレクト係数"５"との差分"１５"を算出する（Ｓ３１）。そして、リクエスト調停回路２２６は、差分"１５"と上述した比較値"１２．５"とを比較する（Ｓ３２）。ここでは、差分"１５"が比較値"１２．５"以上であるため、リクエスト調停回路２２６は、リクエストＡ及びＢのセレクト係数"５"に、差分"１５"の１／２である"８"と"１"とを加算してセレクト係数"１４"を算出（Ｓ３３）し、セレクト係数調停回路２２２及び２２３へ出力する。そのため、セレクト係数保持レジスタ２１８及び２１９には、それぞれ"１４"が格納される。
【００６８】
ここで、上述のステップＳ２１以後に、ノードコントローラ１１１は、プロセッサ１１５から後続リクエストとしてリクエストＤを受け付けたものとする（Ｓ２１）。そのため、ノードコントローラ１１１は、リクエストＤをリクエスト格納バッファ２０５、続いて、リクエスト保持レジスタ２１７に格納する。また、セレクト係数生成回路２１３は、リクエストＤのＤＩＮＤに基づきテーブル２０１からホップ数"２５"を取得し、セレクタ係数としてセレクト係数格納レジスタ２０９に格納する（Ｓ２２）。併せて、当該セレクト係数がセレクト係数保持レジスタ２２１にも格納される。
【００６９】
続いて、ステップＳ２３により次の調停が行われる。このとき、調停対象のリクエストは、リクエスト保持レジスタ２１４、２１５及び２１７に格納されたリクエストＡ、Ｂ及びＤとなる。そのため、リクエスト調停回路２２６は、セレクト係数保持レジスタ２１８、２１９及び２２１に格納されたセレクト係数に基づいて決定を行う。
【００７０】
ここでは、リクエストＡ、Ｂ及びＤのセレクト係数が"１４"、"１４"、"２５"であるため、リクエスト調停回路２２６は、最大値である"２５"に対応するリクエストＤを出力すべきリクエストとして決定する（Ｓ２３）。そして、リクエスト調停回路２２６は、リクエストＤが決定した旨をセレクタ２２７に通知する（Ｓ２４）。
【００７１】
また、併せて、リクエスト調停回路２２６は、調停の勝者であるリクエストＤのセレクト数"２５"と調停の次点であるリクエストＡ及びＢのセレクト係数"１４"との差分"１１"を算出する（Ｓ３１）。そして、リクエスト調停回路２２６は、差分"１１"と上述した比較値"１２．５"とを比較する（Ｓ３２）。ここでは、差分"１１"が比較値"１２．５"未満であるため、リクエスト調停回路２２６は、リクエストＡ及びＢのセレクト係数"１４"に、差分"１１"と"１"とを加算してセレクト係数"２６"を算出（Ｓ３４）し、セレクト係数調停回路２２２及び２２３へ出力する。そのため、セレクト係数保持レジスタ２１８及び２１９には、それぞれ"２６"が格納される。
【００７２】
その後、ステップＳ２３により３回目の調停が行われる。このとき、調停対象のリクエストは、リクエスト保持レジスタ２１４及び２１５に格納されたリクエストＡ及びＢとなる。そのため、リクエスト調停回路２２６は、セレクト係数保持レジスタ２１８及び２１９に格納されたセレクト係数に基づいて決定を行う。
【００７３】
ここでは、リクエストＡ及びＢのセレクト係数が"２６"、"２６"であるため、リクエスト調停回路２２６は、セレクタの番号が小さい番号であるリクエストＡを出力すべきリクエストとして決定する（Ｓ２３）。そして、リクエスト調停回路２２６は、リクエストＡが決定した旨をセレクタ２２７に通知する（Ｓ２４）。
【００７４】
また、併せて、リクエスト調停回路２２６は、調停の勝者であるリクエストＡのセレクト数"２６"と調停の次点であるリクエストＢのセレクト係数"２６"との差分"０"を算出する（Ｓ３１）。そして、リクエスト調停回路２２６は、差分"０"と上述した比較値"１２．５"とを比較する（Ｓ３２）。ここでは、差分"０"が比較値"１２．５"未満であるため、リクエスト調停回路２２６は、リクエストＢのセレクト係数"２６"に、差分"０"と"１"とを加算してセレクト係数"２７"を算出（Ｓ３４）し、セレクト係数調停回路２２３へ出力する。そのため、セレクト係数保持レジスタ２１９には、"２７"が格納される。
【００７５】
その後、ステップＳ２３により４回目の調停が行われる。このとき、調停対象のリクエストは、リクエスト保持レジスタ２１５に格納されたリクエストＢのみとなる。そのため、リクエスト調停回路２２６は、単独での調停であるため、リクエストＢを出力すべきリクエストとして決定する（Ｓ２３）。そして、リクエスト調停回路２２６は、リクエストＢが決定した旨をセレクタ２２７に通知する（Ｓ２４）。
【００７６】
続いて、本発明の実施の形態２により解決される課題及び効果について説明する。外部のノードへリクエストを送信する場合の調停方法としては、課題で上述した優先度を付ける方法の他、ラウンドロビンを用いることもできる。しかし、これらの方法を使用した場合、リクエストが処理される送信先までのホップ数に関係なく、調停が行われる。そのため、セレクタの調停タイミングによってはホップ数の大きいリクエストが後回しにされてしまう。よって、リクエストの処理を開始するまでの時間がかかってしまうことがあった。その際、あるメモリへのアクセスに対し、最初に処理されるべきホップ数が大きいリクエストがネックとなってしまう。それに伴い、処理速度が落ち、性能が低下してしまうことがあった。
【００７７】
ここで、ラウンドロビンによる調停方式を適用した場合について説明する。上述した例と同様に、３つのリクエストＡ、Ｂ及びＣが同時に調停に参加し、次の調停時にはリクエストＤが調停に参加するような場合を想定するものとする。また、リクエストＡ、Ｂ、Ｃ及びＤのＤＮＩＤも同様に、"０１０"、"１００"、"０１１"及び"００１"であるものとし、その際のホップ数が図５に示した値であるものとする。また、システム内でアクセスネックとなりうるリクエストをリクエストＤとする。
【００７８】
図８は、ラウンドロビンを適用した場合のリクエストの処理速度を説明するための図である。まず、現在の優先権が最も小さい番号にある場合、ラウンドロビンを適用して調停による勝者を決める際は、当該小さい番号から調停権を与えられる。そのため、図８に示すように、調停順は、リクエストＡ、リクエストＢ、リクエストＣ、リクエストＤの順になる。そして、調停順に従って、各リクエストが要求先のノードへ出力される。その際、経過する時間がリクエストごとの網掛け部分となる。つまり、リクエストＡが時刻１から時刻５まで経過した後、目的の要求先に到達し、要求先にてリクエストＡの処理が開始される。同様に、リクエストＢ及びＣが出力され、最後に時刻４にて、リクエストＤが出力される。そのため、システム内でのアクセスネックとなりうるリクエストＤは、セレクタ２２７がリクエストを受け取ってから、最速でも２８ホップ後に要求先に到達することになる。
【００７９】
また、単位時間当たりのリクエストの送信処理数の最大値は"４"であるが、最大値で送信処理されている時間は、２ホップ間のみである。つまり、２ホップ間において、ノード間通信が最も効率的に利用されていることとなる。そのため、処理が横長になっており、全てのリクエストについて、要求先で処理が開始されるまでに２８ホップかかっている。
【００８０】
ここで、近年の複数のノードを用いた大規模なコンピュータシステムでは、さらなるリクエストの処理性能の向上が求められている。そこで、本発明の実施の形態２により、さらなるリクエストの処理性能の向上を実現することを説明する。
【００８１】
図９は、本発明の実施の形態２にかかるリクエストの処理速度を説明するための図である。本発明の実施の形態２において、調停により勝者を決定すると、その調停順は、リクエストＣ、リクエストＤ、リクエストＡ、リクエストＢとなる。ここで、システム内でのアクセスネックとなりうるリクエストＤは、セレクタ２２７がリクエストを受け取ってから最速で２５ホップ後に要求先が受信することになる。
【００８２】
また、単位時間当たりのリクエストの送信処理数の最大値は"４"であるが、最大値で送信処理されている時間は、４ホップ間である。そのため、ラウンドロビンで処理しているときよりも送信処理期間が短くなっており、全てのリクエストについて、要求先で処理が開始されるまでに２６ホップとなる。
【００８３】
以上のことから、本発明の実施の形態２における効果を説明する。まず、同一メモリなどへのアクセスが多発したときに、全体的な性能が一番遅いリクエストに引っ張られることがある。そこで、本発明の実施の形態２では、ホップ数の大きいリクエストを先に処理することで、全体的なリクエストの処理速度が向上できる。
【００８４】
また、セレクタからリクエストの要求先までの到達にかかる時間が長いリクエストを優先させることで、システム全体における単位時間あたりのリクエストの送信処理数が増大し、全リクエストの処理時間が平均、短縮化できる。
【００８５】
＜その他の発明の実施の形態＞
本発明の実施の形態２は、大規模なシステムにおいて、あるセレクタにおけるホップ数の大きなリクエストの調停を優先させることで、全体的な処理速度の向上を図ることができる。
また、本発明の実施の形態２により、ノードコントローラ１１１に、セレクタ２２７からリクエストの要求先までのホップ数を基に、優先度を決定する機構であるリクエスト調停回路２２６を設けた。そして、ホップ数が大きいリクエストほど調停を優先的に調停させることで、アクセスネックとなる可能性のあるホップ数の大きいリクエストを先に処理することで局所的な性能低下を抑えることができる。
【００８６】
さらに、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【００８７】
上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られない。
【００８８】
（付記１） 複数のノードと接続され、
自己のノード内の複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出回路と、
前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定回路と、
前記決定されたリクエストを選択して前記要求先のノードへ出力する選択回路と、
を備えるノードコントローラ。
【００８９】
（付記２） 前記優先度算出回路は、各リクエストが自己のノードから要求先のノードへ到達するために経由するノード数であるホップ数が大きいほど、前記優先度をより高く算出することを特徴とする付記１に記載のノードコントローラ。
【００９０】
（付記３） 前記リクエストの要求先のノードと、前記ホップ数とを対応付けて格納する記憶部をさらに備え、
前記優先度算出回路は、前記受け付けた複数のリクエストのそれぞれについて、リクエストの要求先のノードに対応付けられた前記ホップ数を前記記憶部から取得して、前記優先度を算出する
ことを特徴とする付記２に記載のノードコントローラ。
【００９１】
（付記４） 前記決定回路は、前記受け付けた複数のリクエストのうち、前記出力すべきリクエストとして決定されなかった未決定リクエストについて、所定の基準に基づいて前記優先度をより高く更新し、
前記優先度算出回路は、前記複数のリクエストを受け付けた後に受け付けた後続リクエストについて前記優先度を算出し、
前記決定回路は、前記未決定リクエストの前記更新された優先度と、前記後続リクエストの前記算出された優先度とに基づいて、前記出力すべきリクエストを決定する
ことを特徴とする付記１乃至３のいずれか１項に記載のノードコントローラ。
【００９２】
（付記５） 前記決定回路は、前記未決定リクエストについて前記優先度を更新する際の前記所定の基準として、前記出力すべきリクエストとして決定されたリクエストの優先度と、前記未決定のリクエストの優先度と、前記複数のノードのうち自己のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いることを特徴とする付記４に記載のノードコントローラ。
【００９３】
（付記６） 前記決定回路は、前記後続リクエストの要求元と前記未決定リクエストの要求元とが同一のプロセッサである場合、当該後続リクエストを前記決定の対象外とし、
前記優先度算出回路は、前記対象外とされた後続リクエストの前記優先度をより高く更新する
ことを特徴とする付記４又は５に記載のノードコントローラ。
【００９４】
（付記７） 第１のノード内の第１のプロセッサから第２のノード内のプロセッサへの第１のリクエストと、当該第１のノード内の第２のプロセッサから第３のノード内のプロセッサへの第２のリクエストとを同時に受け付け、
前記第１のリクエスト及び前記第２のリクエストの要求元に応じた第１の優先度と第２の優先度を算出し、
前記第１の優先度と前記第２の優先度に基づいて、前記第１のリクエスト及び前記第２のリクエストのいずれを出力すべきかを決定し、
前記決定されたリクエストを選択して前記要求先のノードへ出力する
ことを特徴とするリクエストの出力順序決定方法。
【００９５】
（付記８） 前記第１のリクエストが前記第２のノードへ到達するために経由するノード数であるホップ数が、前記第２のリクエストが前記第３のノードへ到達するために経由するノード数より大きい場合、前記第１の優先度を前記第２の優先度より高く算出し、
前記出力すべきリクエストとして前記第１のリクエストを決定する
ことを特徴とする付記７に記載の出力順序決定方法。
【００９６】
（付記９） 前記出力すべきリクエストとして決定されなかった前記第２のリクエストについて、所定の基準に基づいて前記第２の優先度をより高く更新し、
前記第１のリクエスト及び前記第２のリクエストを受け付けた後に受け付けた第３のリクエストについて第３の優先度を算出し、
前記更新された第２の優先度と、前記算出された第３の優先度とに基づいて、前記出力すべきリクエストを決定する
ことを特徴とする付記８に記載の出力順序決定方法。
【００９７】
（付記１０） 前記第２の優先度を更新する際の前記所定の基準として、前記第１の優先度と、前記第２の優先度と、前記第１のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いることを特徴とする付記９に記載の出力順序決定方法。
【００９８】
（付記１１） 前記第３のリクエストの要求元と前記第２のリクエストの要求元とが同一のプロセッサである場合、当該第３のリクエストを前記決定の対象外とし、
前記第３の優先度をより高く更新する
ことを特徴とする付記９又は１０に記載の出力順序決定方法。
【００９９】
（付記１２） 複数のノードと接続され、
複数のプロセッサと、
当該複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出手段と、
前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定手段と、
前記決定されたリクエストを選択して前記要求先のノードへ出力する選択手段と、
を備えるノードコントローラとを有するノード
を含むノード間通信システム。
【０１００】
（付記１３） 前記優先度算出手段は、各リクエストが自己のノードから要求先のノードへ到達するために経由するノード数であるホップ数が大きいほど、前記優先度をより高く算出することを特徴とする付記１２に記載のノード間通信システム。
【０１０１】
（付記１４） 前記ノードコントローラは、前記リクエストの要求先のノードと、前記ホップ数とを対応付けて格納する記憶手段をさらに備え、
前記優先度算出手段は、前記受け付けた複数のリクエストのそれぞれについて、リクエストの要求先のノードに対応付けられた前記ホップ数を前記記憶手段から取得して、前記優先度を算出する
ことを特徴とする付記１３に記載のノード間通信システム。
【０１０２】
（付記１５） 前記決定手段は、前記受け付けた複数のリクエストのうち、前記出力すべきリクエストとして決定されなかった未決定リクエストについて、所定の基準に基づいて前記優先度をより高く更新し、
前記優先度算出手段は、前記複数のリクエストを受け付けた後に受け付けた後続リクエストについて前記優先度を算出し、
前記決定手段は、前記未決定リクエストの前記更新された優先度と、前記後続リクエストの前記算出された優先度とに基づいて、前記出力すべきリクエストを決定する
ことを特徴とする付記１２乃至１４のいずれか１項に記載のノード間通信システム。
【０１０３】
（付記１６） 前記決定手段は、前記未決定リクエストについて前記優先度を更新する際の前記所定の基準として、前記出力すべきリクエストとして決定されたリクエストの優先度と、前記未決定のリクエストの優先度と、前記複数のノードのうち自己のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いることを特徴とする付記１５に記載のノード間通信システム。
【０１０４】
（付記１７） 前記決定手段は、前記後続リクエストの要求元と前記未決定リクエストの要求元とが同一のプロセッサである場合、当該後続リクエストを前記決定の対象外とし、
前記優先度算出手段は、前記対象外とされた後続リクエストの前記優先度をより高く更新する
ことを特徴とする付記１５又は１６に記載のノード間通信システム。
【符号の説明】
【０１０５】
１００ ノード間通信システム
１ ノード
１１ａ プロセッサ
１１ｂ プロセッサ
１１ｎ プロセッサ
１２ ノードコントローラ
１３ 優先度算出回路
１４ 決定回路
１５ 選択回路
２ ノード
２１ プロセッサ
２２ ノードコントローラ
３ ノード
３１ プロセッサ
３２ ノードコントローラ
１００ａ コンピュータシステム
１０１ ノード
１０２ ノード
１０３ ノード
１０４ ノード
１０５ ノード
１０６ ノード
１０７ ノード
１０８ ノード
１１１ ノードコントローラ
１１２ プロセッサ
１１３ プロセッサ
１１４ プロセッサ
１１５ プロセッサ
１２１ ノードコントローラ
１２２ プロセッサ
１２３ プロセッサ
１２４ プロセッサ
１２５ プロセッサ
１３１ ノードコントローラ
１４１ ノードコントローラ
１５１ ノードコントローラ
１６１ ノードコントローラ
１７１ ノードコントローラ
１８１ ノードコントローラ
３０１ 信号線
３０２ 信号線
３０３ 信号線
３０４ 信号線
３０５ 信号線
３０６ 信号線
３０７ 信号線
３０８ 信号線
３０９ 信号線
３１０ 信号線
３１１ 信号線
３１２ 信号線
３１３ 信号線
３１４ 信号線
３１５ 信号線
３１６ 信号線
２０１ テーブル
２０２ リクエスト格納バッファ
２０３ リクエスト格納バッファ
２０４ リクエスト格納バッファ
２０５ リクエスト格納バッファ
２０６ セレクト係数格納レジスタ
２０７ セレクト係数格納レジスタ
２０８ セレクト係数格納レジスタ
２０９ セレクト係数格納レジスタ
２１０ セレクト係数生成回路
２１１ セレクト係数生成回路
２１２ セレクト係数生成回路
２１３ セレクト係数生成回路
２１４ リクエスト保持レジスタ
２１５ リクエスト保持レジスタ
２１６ リクエスト保持レジスタ
２１７ リクエスト保持レジスタ
２１８ セレクト係数保持レジスタ
２１９ セレクト係数保持レジスタ
２２０ セレクト係数保持レジスタ
２２１ セレクト係数保持レジスタ
２２２ セレクト係数調停回路
２２３ セレクト係数調停回路
２２４ セレクト係数調停回路
２２５ セレクト係数調停回路
２２６ リクエスト調停回路
２２７ セレクタ
【技術分野】
【０００１】
本発明は、ノードコントローラ、リクエストの出力順序決定方法及びノード間通信システムに関し、特に、ノード間通信により他のノードへのアクセスする際のリクエストの送信順序を調停するためのノードコントローラ、リクエストの出力順序決定方法及びノード間通信システムに関する。
【背景技術】
【０００２】
大規模なコンピュータシステムは、複数の処理を並列して実行するために複数のプロセッサを有する。そして、複数のプロセッサを一つのノードとして管理する。さらに、このようなノードを複数有し、ノード間を接続し、各ノードの処理及びノード間通信により所定の処理を実現する。このような大規模なコンピュータシステムでは、ノード間でのデータ通信が頻繁に発生する。例えば、あるプロセッサにおける処理を完了するために、他のプロセッサへ処理を行わせてその結果を必要とする場合がある。その際、要求元のプロセッサは、要求先のプロセッサへのリクエストを送信し、レスポンスを受信する。そして、要求元と要求先が異なるノードに属する場合、ノード間通信が発生する。
【０００３】
特許文献１には、１つのメモリに対する複数のアクセスマスタの競合に対して柔軟、かつ、確実にレイテンシを保証するためのメモリアクセス制御回路に関する技術が開示されている。特許文献１に開示されるメモリアクセス制御回路は、複数のアクセスマスタとメモリとの間に設けられる。優先度比較回路は。優先度レジスタに保持される優先度を比較する。セレクタは、最も優先度の高いアクセスマスタにアクセスを許可する。優先度レジスタに保持される優先度は、アクセスが待たされるごとに減算値レジスタの値が減算されることによって上昇する。これにより、アクセスされやすくなる。連続アクセス回数レジスタは、連続アクセス回数を保持する。そして、連続アクセス回数がアクセス上限回数レジスタの値に達すると、次のアクセス要求があったときに優先度レジスタに保持される初期値の優先度が低く抑えられる。
【０００４】
また、一般に、ノード間通信におけるリクエストの処理性能を向上させるためには、特定のリクエストに優先度をつけ、優先度の高いリクエストを先に送信し、当該リクエストを優先して処理させることにより性能を向上してきた。例えば、複数のリクエストに依存関係がある場合には、先に処理すべきリクエストの優先度を予め高く設定しておくことで、後続のリクエストを効率的に処理することができる。このような複数のリクエストに依存関係は、論理的に定まるものであるため、事前に優先度を設定することが可能である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−１７３８５９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、近年の複数のノードを用いた大規模なコンピュータシステムでは、ノード数が多数であり、ノード間の接続関係が複雑である。そして、ノード間の接続関係は、基本的に、複数のリクエストにおいて論理的に定まる依存関係とは無関係である。例えば、ノード間の接続関係は、全体の処理パフォーマンスやハードウェアに費やすことができるコスト等により変動するものである。そのため、同じリクエストであっても、ノードの配置や数によっては、経由するノード数つまり当該リクエストが要求先に到達するために要する時間に大きな差が出る場合がある。その場合、同じリクエストについての全体の処理時間に差が出る。よって、上述した依存関係に基づいて予めリクエストの優先度を設定することには限界があるという問題点がある。
【０００７】
例えば、後続のリクエストのＨＯＰ数がより大きい場合、優先度に従ってＨＯＰ数の小さいリクエストを先に送信してしまう場合がありえる。その場合、例え、優先度の高いリクエストの処理が完了したとしても、後続のリクエストが完了しないために、さらに後のリクエストが実行できないこととなる。そのため、リクエストの送信順序の調停に参加するタイミングによっては、処理を開始するまでに時間がかかってしまい、性能が低下してしまうことがあった。
【０００８】
尚、特許文献１は、ノード間通信における上述した課題を解決するためのものではない。
【０００９】
本発明は、このような問題点を解決するためになされたものであり、ノード間通信により他のノードへのアクセスする際の複数のリクエスト全体の処理性能を向上するためのノードコントローラ、リクエストの出力順序決定方法及びノード間通信システムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の第１の態様にかかるノードコントローラは、複数のノードと接続され、自己のノード内の複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出回路と、前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定回路と、前記決定されたリクエストを選択して前記要求先のノードへ出力する選択回路と、を備える。
【００１１】
本発明の第２の態様にかかるリクエストの出力順序決定方法は、第１のノード内の第１のプロセッサから第２のノード内のプロセッサへの第１のリクエストと、当該第１のノード内の第２のプロセッサから第３のノード内のプロセッサへの第２のリクエストとを同時に受け付け、前記第１のリクエスト及び前記第２のリクエストの要求元に応じた第１の優先度と第２の優先度を算出し、前記第１の優先度と前記第２の優先度に基づいて、前記第１のリクエスト及び前記第２のリクエストのいずれを出力すべきかを決定し、前記決定されたリクエストを選択して前記要求先のノードへ出力する。
【００１２】
本発明の第３の態様にかかるノード間通信システムは、複数のノードと接続され、複数のプロセッサと、当該複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出手段と、前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定手段と、前記決定されたリクエストを選択して前記要求先のノードへ出力する選択手段と、を備えるノードコントローラとを有するノードを含む。
【発明の効果】
【００１３】
本発明により、ノード間通信により他のノードへのアクセスする際の複数のリクエスト全体の処理性能を向上するためのノードコントローラ、リクエストの出力順序決定方法及びノード間通信システムを提供することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態１にかかるノード間通信システムの構成を示すブロック図である。
【図２】本発明の実施の形態１にかかるアクセス調停方法の処理の流れを示すフローチャートである。
【図３】本発明の実施の形態２にかかるコンピュータシステムの構成を示すブロック図である。
【図４】本発明の実施の形態２にかかるノードコントローラの構成を示すブロック図である。
【図５】本発明の実施の形態２にかかるテーブルの例を示す図である。
【図６】本発明の実施の形態２にかかるアクセス調停方法の流れを説明するためのフローチャートである。
【図７】本発明の実施の形態２にかかるセレクト係数の再設定処理の流れを説明するためのフローチャートである。
【図８】ラウンドロビンを適用した場合のリクエストの処理速度を説明するための図である。
【図９】本発明の実施の形態２にかかるリクエストの処理速度を説明するための図である。
【発明を実施するための形態】
【００１５】
以下では、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略する。
【００１６】
＜発明の実施の形態１＞
図１は、本発明の実施の形態１にかかるノード間通信システム１００の構成を示すブロック図である。ノード間通信システム１００は、少なくともノード１と、ノード２と、ノード３とを備える。ノード１乃至３は、それぞれ、複数のプロセッサを搭載した汎用的なコンピュータ装置である。そして、ノード１乃至３は、それぞれ信号線等により接続されている。これにより、各ノードに含まれるプロセッサが他のノードに含まれるプロセッサに対する処理要求を送受信することができる。
【００１７】
ノード１は、プロセッサ１１ａ、１１ｂ、・・・及び１１ｎと、ノードコントローラ１２とを備える。プロセッサ１１ａ、１１ｂ、・・・及び１１ｎは、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）である。また、各プロセッサは、相互に接続されている。そして、各プロセッサは、それぞれ独立して所定の処理を行う。その際、各プロセッサは、必要に応じてプロセッサ間通信を行う。例えば、プロセッサ１１ａは、プロセッサ１１ｂに対して処理要求すなわちリクエスト）を送信する。そして、プロセッサ１１ｂは、当該リクエストに応じた処理を実行し、リクエスト結果をプロセッサ１１ａへ返信する。その後、プロセッサ１１ａは、プロセッサ１１ｂから受信したリクエスト結果に応じて後続の処理を実行する。
【００１８】
また、プロセッサ１１ａ、１１ｂ、・・・及び１１ｎは、ノードコントローラ１２とそれぞれ接続されている。そして、各プロセッサは、リクエストを他のノードつまりノード２または３のいずれかに属するプロセッサへ送信する場合がある。その場合、各プロセッサは、ノードコントローラ１２を介して他のノードに属するプロセッサとの通信を行う。
【００１９】
ノードコントローラ１２は、各プロセッサからノード２又は３を要求先とした複数のリクエストを受け付け、受け付けた複数のリクエストの出力を制御する。また、ノードコントローラ１２は、ノード２又は３からリクエストを受け付け、プロセッサ１１ａ、１１ｂ、・・・及び１１ｎのいずれかへ当該リクエストを出力する。
【００２０】
ノードコントローラ１２は、優先度算出回路１３と、決定回路１４と、選択回路１５とを備える。優先度算出回路１３は、自己のノード内の複数のプロセッサから複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する。決定回路１４は、算出された優先度に基づいて、受け付けた複数のリクエストのうち出力すべきリクエストを決定する。選択回路１５は、決定されたリクエストを選択して前記要求先のノードへ出力する。尚、実際には、ノードコントローラ１２は、選択回路１５により出力されたリクエストについて、所定の処理を行った上でノード１の外部へ出力するが、当該所定の処理は、一般的なものであるため、詳細な説明を省略する。
【００２１】
ノード２は、複数のプロセッサ２１と、ノードコントローラ２２とを備える。また、ノード３は、複数のプロセッサ３１と、ノードコントローラ３２とを備える。尚、ノード２及び３は、ノード１と同等の機能を有するため、詳細な説明を省略する。つまり、プロセッサ２１及び３１は、プロセッサ１１ａ等と同等である。また、ノードコントローラ２２及び３２は、ノードコントローラ１２と同等である。
【００２２】
尚、ノード１乃至３が搭載するプロセッサの数は、図示したものに限定されない。例えば、ノード１には、プロセッサを１以上搭載していればよい。
【００２３】
図２は、本発明の実施の形態１にかかるアクセス調停方法の処理の流れを示すフローチャートである。まず、ノードコントローラ１２は、プロセッサ１１ａ〜１１ｎから複数のリクエストを受け付ける（Ｓ１１）。次に、優先度算出回路１３は、各リクエストの優先度を算出する（Ｓ１２）。そして、決定回路１４は、優先度に基づいて出力すべきリクエストを決定する（Ｓ１３）。その後、選択回路１５は、決定されたリクエストを選択して出力する（Ｓ１４）。
【００２４】
また、本発明の実施の形態１にかかるアクセス調停方法は、ノード間通信システム１００が３つのノードを有する場合に、少なくとも以下のように言い換えることができる。まず、第１のノード内の第１のプロセッサから第２のノード内のプロセッサへの第１のリクエストと、当該第１のノード内の第２のプロセッサから第３のノード内のプロセッサへの第２のリクエストとを同時に受け付ける。次に、第１のリクエスト及び第２のリクエストの要求元に応じた第１の優先度と第２の優先度を算出する。そして、第１の優先度と第２の優先度に基づいて、第１のリクエスト及び第２のリクエストのいずれを出力すべきかを決定する。その後、決定されたリクエストを選択して前記要求先のノードへ出力することを特徴とするリクエストの出力順序決定方法。
【００２５】
例えば、複数のリクエストの要求先のノードが異なる場合に、優先度を単にリクエストの種別により定めるのではなく、要求先のノードに応じて算出する。これにより、ノードの配置や接続状態によって、リクエストの送信時間に差が出る場合等を考慮して優先度を求めることができる。そのため、本発明の実施の形態１により、ノードの位置関係が無視された場合に比べて、ノード間通信により他のノードへのアクセスする際の複数のリクエスト全体の処理性能を向上することができる。
【００２６】
＜発明の実施の形態２＞
図３は、本発明の実施の形態２にかかるコンピュータシステム１００ａの構成を示すブロック図である。コンピュータシステム１００ａは、上述した実施の形態１にかかるノード間通信システム１００の一実施例である。コンピュータシステム１００ａは、ノード１０１乃至１０８を備える。尚、コンピュータシステム１００ａが備えるノード数はこれに限定されない。
【００２７】
ノード１０１は、ノードコントローラ１１１と、プロセッサ１１２乃至１１５とを備える。すなわち、ノードコントローラ１１１と、プロセッサ１１２乃至１１５とを一つの単位とし、それらを纏めたものをノード１０１と呼ぶ。ノードコントローラ１１１と、プロセッサ１１２乃至１１５とは、それぞれ一対一で信号線により接続されている。同様に、ノード１０２は、ノードコントローラ１２１と、プロセッサ１２２乃至１２５とを備える。そして、ノードコントローラ１２１と、プロセッサ１２２乃至１２５とは、それぞれ一対一で信号線により接続されている。
【００２８】
その他、ノード１０３、１０４、１０５、１０６、１０７及び１０８は、それぞれノードコントローラ１３１、１４１、１５１、１６１、１７１及び１８１を備え、プロセッサも複数備えているが、図示を省略する。
【００２９】
ここで、図３にかかるノード間の接続関係ついて以下に説明する。図３では、各ノードは、隣接するノード間のノードコントローラ同士が信号線で一対一に接続されている。これにより、ノード間のアクセスを実現する。
【００３０】
具体的には、ノードコントローラ１１１は、隣接するノードコントローラ１２１、１３１、１４１、１７１及び１８１と、信号線３０５、３０６、３０７、３０１及び３０２を介して一対一に接続されている。同様に、ノードコントローラ１２１は、隣接するノードコントローラ１１１、１３１、１４１、１７１及び１８１と、信号線３０５、３０８、３０９、３０３及び３０４を介して一対一に接続されている。ノードコントローラ１３１は、隣接するノードコントローラ１１１、１２１、１４１、１５１及び１６１と、信号線３０６、３０８、３１０、３１１及び３１２を介して一対一に接続されている。ノードコントローラ１４１は、隣接するノードコントローラ１１１、１２１、１３１、１５１及び１６１と、信号線３０７、３０８、３１０、３１３及び３１４を介して一対一に接続されている。ノードコントローラ１５１は、隣接するノードコントローラ１３１、１４１及び１６１と、信号線３１１、３１３及び３１５を介して一対一に接続されている。ノードコントローラ１６１は、隣接するノードコントローラ１３１、１４１及び１５１と、信号線３１２、３１４及び３１５を介して一対一に接続されている。ノードコントローラ１７１は、隣接するノードコントローラ１１１、１２１及び１８１と、信号線３０１、３０３及び３１６を介して一対一に接続されている。ノードコントローラ１８１は、隣接するノードコントローラ１１１、１２１及び１７１と、信号線３０２、３０４及び３１６を介して一対一に接続されている。その他、ノード１０５、１０６、１０７及び１０８の接続関係は、図示及び説明を省略する。
【００３１】
ノードコントローラ同士が接続されていないものとの間のアクセスは、間に別のノードコントローラを挟んでアクセスする。つまり、図３では、ノード１０１及び１０２とノード１０５及び１０６とは直接接続されておらず、ノード１０３又は１０４を介してノード間通信を行う必要があることを示す。例えば、ノードコントローラ１１１からノードコントローラ１６１へアクセスする場合には、ノードコントローラ１３１を経由し、信号線３０６及び３１２を介してアクセスするか、ノードコントローラ１４１を経由し、信号線３０７及び３１４を介してアクセスする。この際のアクセスする経路の決定は、公知の技術を用いることができるため、詳細な説明を省略する。
【００３２】
図４は、本発明の実施の形態２にかかるノードコントローラ１１１の構成を示すブロック図である。特に、図４では、ノードコントローラ１１１の構成のうち、プロセッサ１１２乃至１１５から受け付けたリクエストを出力する際の出力順序を決定するための構成について示している。そのため、ノードコントローラ１１１における他の構成については、図示及び説明を省略する。
【００３３】
ノードコントローラ１１１は、テーブル２０１と、リクエスト格納バッファ２０２乃至２０５と、セレクト係数格納レジスタ２０６乃至２０９と、セレクト係数生成回路２１０乃至２１３と、リクエスト保持レジスタ２１４乃至２１７と、セレクト係数保持レジスタ２１８乃至２２１と、セレクト係数調停回路２２２乃至２２５と、リクエスト調停回路２２６と、セレクタ２２７とを備える。
【００３４】
テーブル２０１は、プロセッサから発行されるリクエストに含まれる要求先のノードと、ホップ数とを対応付けて格納する記憶部である。ここで、ホップ数とは、リクエストが自己のノードから要求先のノードへ到達するために経由するノード数である。または、ホップ数は、現在のリクエストの位置からリクエストの送信先までにかかる時間の単位を示すものということもできる。
【００３５】
図５は、本発明の実施の形態２にかかるテーブルの例を示す図である。ここでは、例として、テーブル２０１に＃４０１〜＃４０５の５つのレコードが予め登録されているものとする。"ＤＩＮＤ"は、リクエストに含まれる要求先を２進数で表現した値である。"ＨＯＰ数"は、上述したホップ数を示す。尚、図５に示した値は、図３に示した各ノードやその接続関係とは対応しないものとする。また、テーブル２０１に登録された値は、コンピュータシステム１００ａにおけるノードの接続関係を変更した場合に、適宜、設定変更されるものとする。
【００３６】
ここで、リクエスト格納バッファ２０２、リクエスト保持レジスタ２１４、セレクト係数生成回路２１０、セレクト係数格納レジスタ２０６、セレクト係数調停回路２２２及びセレクト係数保持レジスタ２１８は、プロセッサ１１２から出力されるリクエストに対する処理を行う。同様に、リクエスト格納バッファ２０３、リクエスト保持レジスタ２１５、セレクト係数生成回路２１１、セレクト係数格納レジスタ２０７、セレクト係数調停回路２２３及びセレクト係数保持レジスタ２１９は、プロセッサ１１３から出力されるリクエストに対する処理を行う。リクエスト格納バッファ２０４、リクエスト保持レジスタ２１６、セレクト係数生成回路２１２、セレクト係数格納レジスタ２０８、セレクト係数調停回路２２４及びセレクト係数保持レジスタ２２０は、プロセッサ１１４から出力されるリクエストに対する処理を行う。リクエスト格納バッファ２０５、リクエスト保持レジスタ２１７、セレクト係数生成回路２１３、セレクト係数格納レジスタ２０９、セレクト係数調停回路２２５及びセレクト係数保持レジスタ２２１は、プロセッサ１１５から出力されるリクエストに対する処理を行う。そのため、以下では、プロセッサ１１２に対応する構成を中心に説明し、プロセッサ１１３乃至１１５に対応する構成については、適宜、説明を省略する。
【００３７】
リクエスト格納バッファ２０２は、プロセッサ１１２から出力されたリクエストを格納するバッファである。リクエスト格納バッファ２０２は、複数のリクエストを格納することが可能であり、ＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）方式により後段のリクエスト保持レジスタ２１４へリクエストを出力する。
【００３８】
セレクト係数格納レジスタ２０６は、後述するリクエスト調停回路２２６において複数のリクエストを調停する際の優先度を示した値であるセレクト係数を格納するレジスタである。セレクト係数格納レジスタ２０６に格納できる値の数は、リクエスト格納バッファ２０２に格納できるリクエスト数と同数である。
【００３９】
セレクト係数生成回路２１０は、プロセッサから出力されたリクエストから要求先を抽出する。そして、セレクト係数生成回路２１０は、抽出した要求先に対応するホップ数をテーブル２０１から取得する。その後、セレクト係数生成回路２１０乃至２１３は、取得したホップ数をデコードする。つまり、セレクト係数生成回路２１０は、プロセッサ１１２から受け付けたリクエストについて、リクエストの要求先のノードに対応付けられたホップ数をテーブル２０１から取得して、セレクト係数を算出する。
【００４０】
そのため、セレクト係数生成回路２１０乃至２１３は、プロセッサ１１２乃至１１５から外部のノードに属するプロセッサを要求先とした複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じたセレクト係数を算出するといえる。また、セレクト係数生成回路２１０乃至２１３は、ホップ数が大きいほどセレクト係数をより高く算出するといえる。
【００４１】
また、セレクト係数生成回路２１０は、リクエスト保持レジスタ２１４に保持しているリクエストがリクエスト調停回路２２６における調停により出力すべきリクエストとして決定されなかった場合に、セレクト係数格納レジスタ２０６に格納されている各セレクト係数に１を加算する。すなわち、セレクト係数生成回路２１０は、リクエスト格納バッファ２０２にリクエストが格納されており、かつ、当該リクエストがリクエスト保持レジスタ２１４へ出力されなかったときに、調停の対象外となったリクエストにおけるセレクト係数についてより優先度が高くなるように更新する。よって、
【００４２】
そのため、セレクト係数格納レジスタ２０６には、セレクト係数生成回路２１０により算出された値をセレクト係数として格納する。
【００４３】
リクエスト保持レジスタ２１４乃至２１７は、リクエスト調停回路２２６における調停の対象となるリクエストを保持するレジスタである。例えば、リクエスト保持レジスタ２１４には、リクエスト格納バッファ２０２にリクエストが格納されている順番に格納される。また、リクエスト格納バッファ２０２にリクエストが格納されていない場合、リクエスト保持レジスタ２１４には、プロセッサ１１２から出力されたリクエストがリクエスト格納バッファ２０２を経由せずに、直接、格納される。
【００４４】
セレクト係数保持レジスタ２１８は、リクエスト調停回路２２６における調停対象のリクエストに対応するセレクト係数を格納するレジスタである。具体的には、セレクト係数保持レジスタ２１８には、後述するセレクト係数調停回路２２２において出力されたセレクト係数が格納される。つまり、セレクト係数保持レジスタ２１８乃至２２１は、それぞれリクエスト保持レジスタ２１４乃至２１７に対応する。
【００４５】
セレクト係数調停回路２２２は、セレクト係数生成回路２１０、セレクト係数格納レジスタ２０６及びリクエスト調停回路２２６から出力される３つのセレクト係数とを調停する。つまり、セレクト係数調停回路２２２は、上述した３つのセレクト係数のいずれかを選択してセレクト係数保持レジスタ２１８へ出力する。例えば、リクエスト調停回路２２６によりリクエスト保持レジスタ２１４に格納されたリクエストが出力すべきリクエストとして決定された場合、セレクト係数調停回路２２２は、セレクト係数生成回路２１０又はセレクト係数格納レジスタ２０６から出力されるセレクト係数を出力する。このとき、リクエスト格納バッファ２０２にリクエストが格納済みである場合には、セレクト係数格納レジスタ２０６から出力されるセレクト係数を選択し、リクエスト格納バッファ２０２にリクエストが格納されていない場合には、セレクト係数生成回路２１０から出力されるセレクト係数を選択する。また、リクエスト調停回路２２６によりリクエスト保持レジスタ２１４に格納されたリクエストが出力すべきリクエストとして決定されなかった場合、リクエスト調停回路２２６から出力されるセレクト係数を選択する。
【００４６】
リクエスト調停回路２２６は、セレクト係数保持レジスタ２１８乃至２２１に格納されたセレクト係数に基づき調停して、出力すべきリクエストを決定し、セレクタ２２７へ通知する。すなわち、リクエスト調停回路２２６は、リクエスト保持レジスタ２１４乃至２１７に格納された複数のリクエスト、つまり調停対象のリクエストのうち出力すべきリクエストを決定し、リクエスト保持レジスタ２１４乃至２１７のいずれを選択すべきかをセレクタ２２７に通知する。
【００４７】
また、リクエスト調停回路２２６は、調停により出力対象から漏れたリクエストに対し、決められたルールを基にセレクト係数を再設定し、セレクト係数調停回路２２２乃至２２５へ出力する。つまり、リクエスト調停回路２２６は、調停対象のリクエストのうち出力すべきリクエストとして決定されなかった未決定リクエストについて、所定の基準に基づいてセレクト係数をより高く更新する。このとき、セレクト係数生成回路２１０乃至２１３は、調停対象のリクエストの後に受け付けた後続リクエストについてセレクト係数を算出する。その後、リクエスト調停回路２２６は、未決定リクエストについて更新されたセレクト係数と、後続リクエストについて算出されたセレクト係数とに基づいて、出力すべきリクエストを決定する。
【００４８】
さらに、リクエスト調停回路２２６は、後続リクエストの要求元と未決定リクエストの要求元とが同一のプロセッサである場合、当該後続リクエストを調停の対象外とする。そしてセレクト係数生成回路２１０乃至２１３は、対象外とされた後続リクエストのセレクト係数をより高く更新する。
【００４９】
セレクタ２２７は、リクエスト調停回路２２６から通知を受けたリクエストを選択して出力する。つまり、セレクタ２２７は、リクエスト調停回路２２６により出力すべきと決定されたリクエストを選択して要求先のノードへ出力する。
【００５０】
ここで、第１のリクエストと第２のリクエストを受け付け、第１のリクエストについて算出されるセレクト係数を第１の優先度、第２のリクエストについて算出されるセレクト係数を第２の優先度とした場合について、本発明の実施の形態２に係る動作を説明する。セレクト係数生成回路は、第１のリクエストにおけるホップ数が、第２のリクエストにおけるホップ数より大きい場合に、第１の優先度を第２の優先度より高く算出する。そして、リクエスト調停回路２２６は、第１のリクエストを出力すべきリクエストとして決定する。
【００５１】
図６は、本発明の実施の形態２にかかるアクセス調停方法の流れを説明するためのフローチャートである。まず、前提として、テーブル２０１には、予め自己のノードから各リクエストの要求先に応じたホップ数を格納済みであるものとする。
【００５２】
そして、ノードコントローラ１１１は、プロセッサ１１２乃至１１５からリクエストを受け付け、それぞれをリクエスト格納バッファ２０２乃至２０５に格納する（Ｓ２１）。そして、調停対象となるリクエストは、リクエスト保持レジスタ２１４乃至２１７に保持される。次に、セレクト係数生成回路２１０乃至２１３は、受け付けたリクエストについて、テーブル２０１を参照してセレクト係数を算出し、セレクト係数格納レジスタ２０６乃至２０９に格納する（Ｓ２２）。図５の例では、リクエストの要求先のＤＮＩＤが"０００"の場合、ホップ数は"１０"となる（＃４０１）。
【００５３】
その後、リクエスト調停回路２２６は、調停する（Ｓ２３）。つまり、リクエスト調停回路２２６は、リセレクト係数保持レジスタ２１８乃至２２１に格納済みのセレクト係数を比較して、対応するリクエスト保持レジスタ２１４乃至２１７に格納済みのリクエストのいずれを出力すべきかを決定する。そして、リクエスト調停回路２２６は、決定したリクエストをセレクタ２２７に通知する。
【００５４】
このとき、リクエスト調停回路２２６の決定の基準としては、第一にセレクト係数が大きいほうから調停が優先され、第二にセレクト係数が同じ値であった場合にはセレクタの番号が小さい番号から調停していくものとする。但し、リクエスト調停回路２２６による決定の基準はこれに限定されない。
【００５５】
その後、セレクタ２２７は、リクエスト調停回路２２６により決定されたリクエストを選択して出力する（Ｓ２４）。また、リクエスト調停回路２２６は、未決定リクエストのセレクト係数を更新する（Ｓ２５）。また、この間、ステップＳ２１において、後続のリクエストを受け付けた場合、ステップＳ２２において、セレクト係数生成回路２１０乃至２１３は、後続リクエストにおけるセレクト係数を算出する。また、ステップＳ２５と併せて、セレクト係数生成回路２１０乃至２１３は、未決定リクエストの後続リクエストのセレクト係数について上述したように更新する。
【００５６】
そして、ステップＳ２３に戻り、リクエスト調停回路２２６は、出力されたリクエストの後続リクエストと、未決定リクエストのいずれを出力すべきかを決定する。以後、リクエストの受け付けがなくなるまで繰り返し実行される。
【００５７】
ここで、リクエスト調停回路２２６におけるセレクト係数の再設定方法の一例を説明する。尚、本発明の実施の形態２にかかるセレクト係数の再設定方法はこれに限定されない。リクエスト調停回路２２６は、未決定リクエストについてセレクト係数を更新する際の所定の基準として、出力すべきリクエストとして決定されたリクエストのセレクト係数と、未決定のリクエストのセレクト係数と、複数のノードのうち自己のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いる。
【００５８】
図７は、本発明の実施の形態２にかかるセレクト係数の再設定処理の流れを説明するためのフローチャートである。まず、リクエスト調停回路２２６は、決定リクエストと未決定リクエストとのセレクト係数の差分を算出する（Ｓ３１）。決定リクエストとは、調停により出力すべきと決定されたリクエストである。また、未決定リクエストとは、調停により次点だったリクエストである。
【００５９】
次に、リクエスト調停回路２２６は、ステップＳ３１により算出された差分がテーブル２０１に格納されたホップ数のうち最大値である最大ホップ数の１／２以上であるか否かを判定する（Ｓ３２）。すなわち、以下の（１）式を満たすか否かを判定する。
差分 ≧ 最大ホップ数×１／２・・・（１）
【００６０】
ステップＳ３２において、１／２以上であると判定した場合、リクエスト調停回路２２６は、差分の１／２の値に、調停待ち分の１を足した値を、セレクト係数に足す（Ｓ３３）。すなわち、以下の（２）式によりセレクト係数を更新する。
セレクト係数＝ セレクト係数 ＋ 差分×１／２ ＋ １ ・・・（２）
【００６１】
ステップＳ３２において、１／２未満であると判定した場合、リクエスト調停回路２２６は、差分に調停待ち分の１を足した値をセレクト係数に足す（Ｓ３４）。つまり、以下の（３）式によりセレクト係数を更新する。
セレクト係数＝ セレクト係数 ＋ 差分 ＋ １ ・・・（３）
【００６２】
尚、セレクト係数の小数点が発生した場合には切り上げて計算する。そして、リクエスト調停回路２２６は、図７の処理を未決定リクエストの全てについて実行する。
【００６３】
以下に、具体例を示して説明する。まず、図５の例では、最大ホップ数が"２５"である。そのため、ステップＳ３２の比較に用いる比較値は、最大ホップ数の１／２である"１２．５"となる。また、以下では、リクエストＡ、Ｂ、Ｃ及びＤを対象とする。そして、リクエストＡ、Ｂ、Ｃ及びＤのＤＩＮＤは、"０１０"、"１００"、"０１１"及び"００１"であるものとする。そして、リクエストＤは、システム内でアクセスネックとなりうるリクエストであるものとする。以下、図６及び図７に沿って説明する。
【００６４】
まず、ノードコントローラ１１１は、プロセッサ１１２乃至１１４からリクエストＡ、Ｂ及びＣを同時に受け付け、それぞれをリクエスト格納バッファ２０２乃至２０４に格納する（Ｓ２１）。そして、リクエストＡ、Ｂ及びＣは、リクエスト保持レジスタ２１４乃至２１６に格納されたものとする。つまり、３つのリクエストＡ、Ｂ及びＣが同時に調停対象となったものとする。
【００６５】
次に、セレクト係数生成回路２１０乃至２１２は、リクエストＡ、Ｂ及びＣのＤＩＮＤに基づきテーブル２０１からホップ数"５"、"５"及び"２０"を取得し、セレクタ係数としてセレクト係数格納レジスタ２０６乃至２０８に格納する（Ｓ２２）。併せて、当該セレクト係数がセレクト係数保持レジスタ２１８乃至２２０にも格納される。
【００６６】
そして、リクエスト調停回路２２６は、３つのセレクタ係数を比較し、最大値である"２０"に対応するリクエストＣを出力すべきリクエストとして決定する（Ｓ２３）。そして、リクエスト調停回路２２６は、リクエストＣが決定した旨をセレクタ２２７に通知する（Ｓ２４）。
【００６７】
併せて、リクエスト調停回路２２６は、調停の勝者であるリクエストＣのセレクト数"２０"と調停の次点であるリクエストＡ及びＢのセレクト係数"５"との差分"１５"を算出する（Ｓ３１）。そして、リクエスト調停回路２２６は、差分"１５"と上述した比較値"１２．５"とを比較する（Ｓ３２）。ここでは、差分"１５"が比較値"１２．５"以上であるため、リクエスト調停回路２２６は、リクエストＡ及びＢのセレクト係数"５"に、差分"１５"の１／２である"８"と"１"とを加算してセレクト係数"１４"を算出（Ｓ３３）し、セレクト係数調停回路２２２及び２２３へ出力する。そのため、セレクト係数保持レジスタ２１８及び２１９には、それぞれ"１４"が格納される。
【００６８】
ここで、上述のステップＳ２１以後に、ノードコントローラ１１１は、プロセッサ１１５から後続リクエストとしてリクエストＤを受け付けたものとする（Ｓ２１）。そのため、ノードコントローラ１１１は、リクエストＤをリクエスト格納バッファ２０５、続いて、リクエスト保持レジスタ２１７に格納する。また、セレクト係数生成回路２１３は、リクエストＤのＤＩＮＤに基づきテーブル２０１からホップ数"２５"を取得し、セレクタ係数としてセレクト係数格納レジスタ２０９に格納する（Ｓ２２）。併せて、当該セレクト係数がセレクト係数保持レジスタ２２１にも格納される。
【００６９】
続いて、ステップＳ２３により次の調停が行われる。このとき、調停対象のリクエストは、リクエスト保持レジスタ２１４、２１５及び２１７に格納されたリクエストＡ、Ｂ及びＤとなる。そのため、リクエスト調停回路２２６は、セレクト係数保持レジスタ２１８、２１９及び２２１に格納されたセレクト係数に基づいて決定を行う。
【００７０】
ここでは、リクエストＡ、Ｂ及びＤのセレクト係数が"１４"、"１４"、"２５"であるため、リクエスト調停回路２２６は、最大値である"２５"に対応するリクエストＤを出力すべきリクエストとして決定する（Ｓ２３）。そして、リクエスト調停回路２２６は、リクエストＤが決定した旨をセレクタ２２７に通知する（Ｓ２４）。
【００７１】
また、併せて、リクエスト調停回路２２６は、調停の勝者であるリクエストＤのセレクト数"２５"と調停の次点であるリクエストＡ及びＢのセレクト係数"１４"との差分"１１"を算出する（Ｓ３１）。そして、リクエスト調停回路２２６は、差分"１１"と上述した比較値"１２．５"とを比較する（Ｓ３２）。ここでは、差分"１１"が比較値"１２．５"未満であるため、リクエスト調停回路２２６は、リクエストＡ及びＢのセレクト係数"１４"に、差分"１１"と"１"とを加算してセレクト係数"２６"を算出（Ｓ３４）し、セレクト係数調停回路２２２及び２２３へ出力する。そのため、セレクト係数保持レジスタ２１８及び２１９には、それぞれ"２６"が格納される。
【００７２】
その後、ステップＳ２３により３回目の調停が行われる。このとき、調停対象のリクエストは、リクエスト保持レジスタ２１４及び２１５に格納されたリクエストＡ及びＢとなる。そのため、リクエスト調停回路２２６は、セレクト係数保持レジスタ２１８及び２１９に格納されたセレクト係数に基づいて決定を行う。
【００７３】
ここでは、リクエストＡ及びＢのセレクト係数が"２６"、"２６"であるため、リクエスト調停回路２２６は、セレクタの番号が小さい番号であるリクエストＡを出力すべきリクエストとして決定する（Ｓ２３）。そして、リクエスト調停回路２２６は、リクエストＡが決定した旨をセレクタ２２７に通知する（Ｓ２４）。
【００７４】
また、併せて、リクエスト調停回路２２６は、調停の勝者であるリクエストＡのセレクト数"２６"と調停の次点であるリクエストＢのセレクト係数"２６"との差分"０"を算出する（Ｓ３１）。そして、リクエスト調停回路２２６は、差分"０"と上述した比較値"１２．５"とを比較する（Ｓ３２）。ここでは、差分"０"が比較値"１２．５"未満であるため、リクエスト調停回路２２６は、リクエストＢのセレクト係数"２６"に、差分"０"と"１"とを加算してセレクト係数"２７"を算出（Ｓ３４）し、セレクト係数調停回路２２３へ出力する。そのため、セレクト係数保持レジスタ２１９には、"２７"が格納される。
【００７５】
その後、ステップＳ２３により４回目の調停が行われる。このとき、調停対象のリクエストは、リクエスト保持レジスタ２１５に格納されたリクエストＢのみとなる。そのため、リクエスト調停回路２２６は、単独での調停であるため、リクエストＢを出力すべきリクエストとして決定する（Ｓ２３）。そして、リクエスト調停回路２２６は、リクエストＢが決定した旨をセレクタ２２７に通知する（Ｓ２４）。
【００７６】
続いて、本発明の実施の形態２により解決される課題及び効果について説明する。外部のノードへリクエストを送信する場合の調停方法としては、課題で上述した優先度を付ける方法の他、ラウンドロビンを用いることもできる。しかし、これらの方法を使用した場合、リクエストが処理される送信先までのホップ数に関係なく、調停が行われる。そのため、セレクタの調停タイミングによってはホップ数の大きいリクエストが後回しにされてしまう。よって、リクエストの処理を開始するまでの時間がかかってしまうことがあった。その際、あるメモリへのアクセスに対し、最初に処理されるべきホップ数が大きいリクエストがネックとなってしまう。それに伴い、処理速度が落ち、性能が低下してしまうことがあった。
【００７７】
ここで、ラウンドロビンによる調停方式を適用した場合について説明する。上述した例と同様に、３つのリクエストＡ、Ｂ及びＣが同時に調停に参加し、次の調停時にはリクエストＤが調停に参加するような場合を想定するものとする。また、リクエストＡ、Ｂ、Ｃ及びＤのＤＮＩＤも同様に、"０１０"、"１００"、"０１１"及び"００１"であるものとし、その際のホップ数が図５に示した値であるものとする。また、システム内でアクセスネックとなりうるリクエストをリクエストＤとする。
【００７８】
図８は、ラウンドロビンを適用した場合のリクエストの処理速度を説明するための図である。まず、現在の優先権が最も小さい番号にある場合、ラウンドロビンを適用して調停による勝者を決める際は、当該小さい番号から調停権を与えられる。そのため、図８に示すように、調停順は、リクエストＡ、リクエストＢ、リクエストＣ、リクエストＤの順になる。そして、調停順に従って、各リクエストが要求先のノードへ出力される。その際、経過する時間がリクエストごとの網掛け部分となる。つまり、リクエストＡが時刻１から時刻５まで経過した後、目的の要求先に到達し、要求先にてリクエストＡの処理が開始される。同様に、リクエストＢ及びＣが出力され、最後に時刻４にて、リクエストＤが出力される。そのため、システム内でのアクセスネックとなりうるリクエストＤは、セレクタ２２７がリクエストを受け取ってから、最速でも２８ホップ後に要求先に到達することになる。
【００７９】
また、単位時間当たりのリクエストの送信処理数の最大値は"４"であるが、最大値で送信処理されている時間は、２ホップ間のみである。つまり、２ホップ間において、ノード間通信が最も効率的に利用されていることとなる。そのため、処理が横長になっており、全てのリクエストについて、要求先で処理が開始されるまでに２８ホップかかっている。
【００８０】
ここで、近年の複数のノードを用いた大規模なコンピュータシステムでは、さらなるリクエストの処理性能の向上が求められている。そこで、本発明の実施の形態２により、さらなるリクエストの処理性能の向上を実現することを説明する。
【００８１】
図９は、本発明の実施の形態２にかかるリクエストの処理速度を説明するための図である。本発明の実施の形態２において、調停により勝者を決定すると、その調停順は、リクエストＣ、リクエストＤ、リクエストＡ、リクエストＢとなる。ここで、システム内でのアクセスネックとなりうるリクエストＤは、セレクタ２２７がリクエストを受け取ってから最速で２５ホップ後に要求先が受信することになる。
【００８２】
また、単位時間当たりのリクエストの送信処理数の最大値は"４"であるが、最大値で送信処理されている時間は、４ホップ間である。そのため、ラウンドロビンで処理しているときよりも送信処理期間が短くなっており、全てのリクエストについて、要求先で処理が開始されるまでに２６ホップとなる。
【００８３】
以上のことから、本発明の実施の形態２における効果を説明する。まず、同一メモリなどへのアクセスが多発したときに、全体的な性能が一番遅いリクエストに引っ張られることがある。そこで、本発明の実施の形態２では、ホップ数の大きいリクエストを先に処理することで、全体的なリクエストの処理速度が向上できる。
【００８４】
また、セレクタからリクエストの要求先までの到達にかかる時間が長いリクエストを優先させることで、システム全体における単位時間あたりのリクエストの送信処理数が増大し、全リクエストの処理時間が平均、短縮化できる。
【００８５】
＜その他の発明の実施の形態＞
本発明の実施の形態２は、大規模なシステムにおいて、あるセレクタにおけるホップ数の大きなリクエストの調停を優先させることで、全体的な処理速度の向上を図ることができる。
また、本発明の実施の形態２により、ノードコントローラ１１１に、セレクタ２２７からリクエストの要求先までのホップ数を基に、優先度を決定する機構であるリクエスト調停回路２２６を設けた。そして、ホップ数が大きいリクエストほど調停を優先的に調停させることで、アクセスネックとなる可能性のあるホップ数の大きいリクエストを先に処理することで局所的な性能低下を抑えることができる。
【００８６】
さらに、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【００８７】
上記の実施形態の一部又は全部は、以下の付記のようにも記載され得るが、以下には限られない。
【００８８】
（付記１） 複数のノードと接続され、
自己のノード内の複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出回路と、
前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定回路と、
前記決定されたリクエストを選択して前記要求先のノードへ出力する選択回路と、
を備えるノードコントローラ。
【００８９】
（付記２） 前記優先度算出回路は、各リクエストが自己のノードから要求先のノードへ到達するために経由するノード数であるホップ数が大きいほど、前記優先度をより高く算出することを特徴とする付記１に記載のノードコントローラ。
【００９０】
（付記３） 前記リクエストの要求先のノードと、前記ホップ数とを対応付けて格納する記憶部をさらに備え、
前記優先度算出回路は、前記受け付けた複数のリクエストのそれぞれについて、リクエストの要求先のノードに対応付けられた前記ホップ数を前記記憶部から取得して、前記優先度を算出する
ことを特徴とする付記２に記載のノードコントローラ。
【００９１】
（付記４） 前記決定回路は、前記受け付けた複数のリクエストのうち、前記出力すべきリクエストとして決定されなかった未決定リクエストについて、所定の基準に基づいて前記優先度をより高く更新し、
前記優先度算出回路は、前記複数のリクエストを受け付けた後に受け付けた後続リクエストについて前記優先度を算出し、
前記決定回路は、前記未決定リクエストの前記更新された優先度と、前記後続リクエストの前記算出された優先度とに基づいて、前記出力すべきリクエストを決定する
ことを特徴とする付記１乃至３のいずれか１項に記載のノードコントローラ。
【００９２】
（付記５） 前記決定回路は、前記未決定リクエストについて前記優先度を更新する際の前記所定の基準として、前記出力すべきリクエストとして決定されたリクエストの優先度と、前記未決定のリクエストの優先度と、前記複数のノードのうち自己のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いることを特徴とする付記４に記載のノードコントローラ。
【００９３】
（付記６） 前記決定回路は、前記後続リクエストの要求元と前記未決定リクエストの要求元とが同一のプロセッサである場合、当該後続リクエストを前記決定の対象外とし、
前記優先度算出回路は、前記対象外とされた後続リクエストの前記優先度をより高く更新する
ことを特徴とする付記４又は５に記載のノードコントローラ。
【００９４】
（付記７） 第１のノード内の第１のプロセッサから第２のノード内のプロセッサへの第１のリクエストと、当該第１のノード内の第２のプロセッサから第３のノード内のプロセッサへの第２のリクエストとを同時に受け付け、
前記第１のリクエスト及び前記第２のリクエストの要求元に応じた第１の優先度と第２の優先度を算出し、
前記第１の優先度と前記第２の優先度に基づいて、前記第１のリクエスト及び前記第２のリクエストのいずれを出力すべきかを決定し、
前記決定されたリクエストを選択して前記要求先のノードへ出力する
ことを特徴とするリクエストの出力順序決定方法。
【００９５】
（付記８） 前記第１のリクエストが前記第２のノードへ到達するために経由するノード数であるホップ数が、前記第２のリクエストが前記第３のノードへ到達するために経由するノード数より大きい場合、前記第１の優先度を前記第２の優先度より高く算出し、
前記出力すべきリクエストとして前記第１のリクエストを決定する
ことを特徴とする付記７に記載の出力順序決定方法。
【００９６】
（付記９） 前記出力すべきリクエストとして決定されなかった前記第２のリクエストについて、所定の基準に基づいて前記第２の優先度をより高く更新し、
前記第１のリクエスト及び前記第２のリクエストを受け付けた後に受け付けた第３のリクエストについて第３の優先度を算出し、
前記更新された第２の優先度と、前記算出された第３の優先度とに基づいて、前記出力すべきリクエストを決定する
ことを特徴とする付記８に記載の出力順序決定方法。
【００９７】
（付記１０） 前記第２の優先度を更新する際の前記所定の基準として、前記第１の優先度と、前記第２の優先度と、前記第１のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いることを特徴とする付記９に記載の出力順序決定方法。
【００９８】
（付記１１） 前記第３のリクエストの要求元と前記第２のリクエストの要求元とが同一のプロセッサである場合、当該第３のリクエストを前記決定の対象外とし、
前記第３の優先度をより高く更新する
ことを特徴とする付記９又は１０に記載の出力順序決定方法。
【００９９】
（付記１２） 複数のノードと接続され、
複数のプロセッサと、
当該複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出手段と、
前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定手段と、
前記決定されたリクエストを選択して前記要求先のノードへ出力する選択手段と、
を備えるノードコントローラとを有するノード
を含むノード間通信システム。
【０１００】
（付記１３） 前記優先度算出手段は、各リクエストが自己のノードから要求先のノードへ到達するために経由するノード数であるホップ数が大きいほど、前記優先度をより高く算出することを特徴とする付記１２に記載のノード間通信システム。
【０１０１】
（付記１４） 前記ノードコントローラは、前記リクエストの要求先のノードと、前記ホップ数とを対応付けて格納する記憶手段をさらに備え、
前記優先度算出手段は、前記受け付けた複数のリクエストのそれぞれについて、リクエストの要求先のノードに対応付けられた前記ホップ数を前記記憶手段から取得して、前記優先度を算出する
ことを特徴とする付記１３に記載のノード間通信システム。
【０１０２】
（付記１５） 前記決定手段は、前記受け付けた複数のリクエストのうち、前記出力すべきリクエストとして決定されなかった未決定リクエストについて、所定の基準に基づいて前記優先度をより高く更新し、
前記優先度算出手段は、前記複数のリクエストを受け付けた後に受け付けた後続リクエストについて前記優先度を算出し、
前記決定手段は、前記未決定リクエストの前記更新された優先度と、前記後続リクエストの前記算出された優先度とに基づいて、前記出力すべきリクエストを決定する
ことを特徴とする付記１２乃至１４のいずれか１項に記載のノード間通信システム。
【０１０３】
（付記１６） 前記決定手段は、前記未決定リクエストについて前記優先度を更新する際の前記所定の基準として、前記出力すべきリクエストとして決定されたリクエストの優先度と、前記未決定のリクエストの優先度と、前記複数のノードのうち自己のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いることを特徴とする付記１５に記載のノード間通信システム。
【０１０４】
（付記１７） 前記決定手段は、前記後続リクエストの要求元と前記未決定リクエストの要求元とが同一のプロセッサである場合、当該後続リクエストを前記決定の対象外とし、
前記優先度算出手段は、前記対象外とされた後続リクエストの前記優先度をより高く更新する
ことを特徴とする付記１５又は１６に記載のノード間通信システム。
【符号の説明】
【０１０５】
１００ ノード間通信システム
１ ノード
１１ａ プロセッサ
１１ｂ プロセッサ
１１ｎ プロセッサ
１２ ノードコントローラ
１３ 優先度算出回路
１４ 決定回路
１５ 選択回路
２ ノード
２１ プロセッサ
２２ ノードコントローラ
３ ノード
３１ プロセッサ
３２ ノードコントローラ
１００ａ コンピュータシステム
１０１ ノード
１０２ ノード
１０３ ノード
１０４ ノード
１０５ ノード
１０６ ノード
１０７ ノード
１０８ ノード
１１１ ノードコントローラ
１１２ プロセッサ
１１３ プロセッサ
１１４ プロセッサ
１１５ プロセッサ
１２１ ノードコントローラ
１２２ プロセッサ
１２３ プロセッサ
１２４ プロセッサ
１２５ プロセッサ
１３１ ノードコントローラ
１４１ ノードコントローラ
１５１ ノードコントローラ
１６１ ノードコントローラ
１７１ ノードコントローラ
１８１ ノードコントローラ
３０１ 信号線
３０２ 信号線
３０３ 信号線
３０４ 信号線
３０５ 信号線
３０６ 信号線
３０７ 信号線
３０８ 信号線
３０９ 信号線
３１０ 信号線
３１１ 信号線
３１２ 信号線
３１３ 信号線
３１４ 信号線
３１５ 信号線
３１６ 信号線
２０１ テーブル
２０２ リクエスト格納バッファ
２０３ リクエスト格納バッファ
２０４ リクエスト格納バッファ
２０５ リクエスト格納バッファ
２０６ セレクト係数格納レジスタ
２０７ セレクト係数格納レジスタ
２０８ セレクト係数格納レジスタ
２０９ セレクト係数格納レジスタ
２１０ セレクト係数生成回路
２１１ セレクト係数生成回路
２１２ セレクト係数生成回路
２１３ セレクト係数生成回路
２１４ リクエスト保持レジスタ
２１５ リクエスト保持レジスタ
２１６ リクエスト保持レジスタ
２１７ リクエスト保持レジスタ
２１８ セレクト係数保持レジスタ
２１９ セレクト係数保持レジスタ
２２０ セレクト係数保持レジスタ
２２１ セレクト係数保持レジスタ
２２２ セレクト係数調停回路
２２３ セレクト係数調停回路
２２４ セレクト係数調停回路
２２５ セレクト係数調停回路
２２６ リクエスト調停回路
２２７ セレクタ
【特許請求の範囲】
【請求項１】
複数のノードと接続され、
自己のノード内の複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出回路と、
前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定回路と、
前記決定されたリクエストを選択して前記要求先のノードへ出力する選択回路と、
を備えるノードコントローラ。
【請求項２】
前記優先度算出回路は、各リクエストが自己のノードから要求先のノードへ到達するために経由するノード数であるホップ数が大きいほど、前記優先度をより高く算出することを特徴とする請求項１に記載のノードコントローラ。
【請求項３】
前記リクエストの要求先のノードと、前記ホップ数とを対応付けて格納する記憶部をさらに備え、
前記優先度算出回路は、前記受け付けた複数のリクエストのそれぞれについて、リクエストの要求先のノードに対応付けられた前記ホップ数を前記記憶部から取得して、前記優先度を算出する
ことを特徴とする請求項２に記載のノードコントローラ。
【請求項４】
前記決定回路は、前記受け付けた複数のリクエストのうち、前記出力すべきリクエストとして決定されなかった未決定リクエストについて、所定の基準に基づいて前記優先度をより高く更新し、
前記優先度算出回路は、前記複数のリクエストを受け付けた後に受け付けた後続リクエストについて前記優先度を算出し、
前記決定回路は、前記未決定リクエストの前記更新された優先度と、前記後続リクエストの前記算出された優先度とに基づいて、前記出力すべきリクエストを決定する
ことを特徴とする請求項１乃至３のいずれか１項に記載のノードコントローラ。
【請求項５】
前記決定回路は、前記未決定リクエストについて前記優先度を更新する際の前記所定の基準として、前記出力すべきリクエストとして決定されたリクエストの優先度と、前記未決定のリクエストの優先度と、前記複数のノードのうち自己のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いることを特徴とする請求項４に記載のノードコントローラ。
【請求項６】
前記決定回路は、前記後続リクエストの要求元と前記未決定リクエストの要求元とが同一のプロセッサである場合、当該後続リクエストを前記決定の対象外とし、
前記優先度算出回路は、前記対象外とされた後続リクエストの前記優先度をより高く更新する
ことを特徴とする請求項４又は５に記載のノードコントローラ。
【請求項７】
第１のノード内の第１のプロセッサから第２のノード内のプロセッサへの第１のリクエストと、当該第１のノード内の第２のプロセッサから第３のノード内のプロセッサへの第２のリクエストとを同時に受け付け、
前記第１のリクエスト及び前記第２のリクエストの要求元に応じた第１の優先度と第２の優先度を算出し、
前記第１の優先度と前記第２の優先度に基づいて、前記第１のリクエスト及び前記第２のリクエストのいずれを出力すべきかを決定し、
前記決定されたリクエストを選択して前記要求先のノードへ出力する
ことを特徴とするリクエストの出力順序決定方法。
【請求項８】
前記第１のリクエストが前記第２のノードへ到達するために経由するノード数であるホップ数が、前記第２のリクエストが前記第３のノードへ到達するために経由するノード数より大きい場合、前記第１の優先度を前記第２の優先度より高く算出し、
前記出力すべきリクエストとして前記第１のリクエストを決定する
ことを特徴とする請求項７に記載の出力順序決定方法。
【請求項９】
複数のノードと接続され、
複数のプロセッサと、
当該複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出手段と、
前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定手段と、
前記決定されたリクエストを選択して前記要求先のノードへ出力する選択手段と、
を備えるノードコントローラとを有するノード
を含むノード間通信システム。
【請求項１０】
前記優先度算出手段は、各リクエストが自己のノードから要求先のノードへ到達するために経由するノード数であるホップ数が大きいほど、前記優先度をより高く算出することを特徴とする請求項９に記載のノード間通信システム。
【請求項１】
複数のノードと接続され、
自己のノード内の複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出回路と、
前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定回路と、
前記決定されたリクエストを選択して前記要求先のノードへ出力する選択回路と、
を備えるノードコントローラ。
【請求項２】
前記優先度算出回路は、各リクエストが自己のノードから要求先のノードへ到達するために経由するノード数であるホップ数が大きいほど、前記優先度をより高く算出することを特徴とする請求項１に記載のノードコントローラ。
【請求項３】
前記リクエストの要求先のノードと、前記ホップ数とを対応付けて格納する記憶部をさらに備え、
前記優先度算出回路は、前記受け付けた複数のリクエストのそれぞれについて、リクエストの要求先のノードに対応付けられた前記ホップ数を前記記憶部から取得して、前記優先度を算出する
ことを特徴とする請求項２に記載のノードコントローラ。
【請求項４】
前記決定回路は、前記受け付けた複数のリクエストのうち、前記出力すべきリクエストとして決定されなかった未決定リクエストについて、所定の基準に基づいて前記優先度をより高く更新し、
前記優先度算出回路は、前記複数のリクエストを受け付けた後に受け付けた後続リクエストについて前記優先度を算出し、
前記決定回路は、前記未決定リクエストの前記更新された優先度と、前記後続リクエストの前記算出された優先度とに基づいて、前記出力すべきリクエストを決定する
ことを特徴とする請求項１乃至３のいずれか１項に記載のノードコントローラ。
【請求項５】
前記決定回路は、前記未決定リクエストについて前記優先度を更新する際の前記所定の基準として、前記出力すべきリクエストとして決定されたリクエストの優先度と、前記未決定のリクエストの優先度と、前記複数のノードのうち自己のノードから要求先のノードへリクエストが到達するために経由するノード数の最大値とを用いることを特徴とする請求項４に記載のノードコントローラ。
【請求項６】
前記決定回路は、前記後続リクエストの要求元と前記未決定リクエストの要求元とが同一のプロセッサである場合、当該後続リクエストを前記決定の対象外とし、
前記優先度算出回路は、前記対象外とされた後続リクエストの前記優先度をより高く更新する
ことを特徴とする請求項４又は５に記載のノードコントローラ。
【請求項７】
第１のノード内の第１のプロセッサから第２のノード内のプロセッサへの第１のリクエストと、当該第１のノード内の第２のプロセッサから第３のノード内のプロセッサへの第２のリクエストとを同時に受け付け、
前記第１のリクエスト及び前記第２のリクエストの要求元に応じた第１の優先度と第２の優先度を算出し、
前記第１の優先度と前記第２の優先度に基づいて、前記第１のリクエスト及び前記第２のリクエストのいずれを出力すべきかを決定し、
前記決定されたリクエストを選択して前記要求先のノードへ出力する
ことを特徴とするリクエストの出力順序決定方法。
【請求項８】
前記第１のリクエストが前記第２のノードへ到達するために経由するノード数であるホップ数が、前記第２のリクエストが前記第３のノードへ到達するために経由するノード数より大きい場合、前記第１の優先度を前記第２の優先度より高く算出し、
前記出力すべきリクエストとして前記第１のリクエストを決定する
ことを特徴とする請求項７に記載の出力順序決定方法。
【請求項９】
複数のノードと接続され、
複数のプロセッサと、
当該複数のプロセッサから前記複数のノードのいずれかに属するプロセッサへの複数のリクエストを受け付け、当該複数のリクエストのそれぞれについて、リクエストの要求先のノードに応じた優先度を算出する優先度算出手段と、
前記算出された優先度に基づいて、前記受け付けた複数のリクエストのうち出力すべきリクエストを決定する決定手段と、
前記決定されたリクエストを選択して前記要求先のノードへ出力する選択手段と、
を備えるノードコントローラとを有するノード
を含むノード間通信システム。
【請求項１０】
前記優先度算出手段は、各リクエストが自己のノードから要求先のノードへ到達するために経由するノード数であるホップ数が大きいほど、前記優先度をより高く算出することを特徴とする請求項９に記載のノード間通信システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−９３９４５（Ｐ２０１２−９３９４５Ａ）
【公開日】平成２４年５月１７日（２０１２．５．１７）
【国際特許分類】
【出願番号】特願２０１０−２４０４４８（Ｐ２０１０−２４０４４８）
【出願日】平成２２年１０月２７日（２０１０．１０．２７）
【出願人】（０００１６８２８５）エヌイーシーコンピュータテクノ株式会社 (572)
【Ｆターム（参考）】
【公開日】平成２４年５月１７日（２０１２．５．１７）
【国際特許分類】
【出願日】平成２２年１０月２７日（２０１０．１０．２７）
【出願人】（０００１６８２８５）エヌイーシーコンピュータテクノ株式会社 (572)
【Ｆターム（参考）】
[ Back to top ]