ノードコントローラ及びノード並びにデッドロック検出方法
【課題】ネットワーク上のトラヒックや処理時間、又はハードウェア量の増大を招くことなく、システム運用の前にルーティング情報が正しいかを確認できるノードコントローラ、ノード、デッドロック検出方法を提供する。
【解決手段】デッドロック検出用パケットを発行するパケット発行部６０Ｘ１と、他ノード宛のデッドロック検出用パケットを受信した場合に、その送出経路が自ノードＸが既に発行したデッドロック検出用パケットと同じであるならばデッドロックが発生すると判断するデッドロック検出部６０Ｘ３と、他ノード宛のデッドロック検出用パケットを送信するために用いるポートと同じポートを用いて通信するノードが他に存在するか否かをルーティング情報８０Ｘに従って判断し、存在する場合に、該ノード宛のデッドロック検出用パケットをパケット発行回路６０Ｘ１に発行させる対象ノード検出部６０Ｘ２とを有する。
【解決手段】デッドロック検出用パケットを発行するパケット発行部６０Ｘ１と、他ノード宛のデッドロック検出用パケットを受信した場合に、その送出経路が自ノードＸが既に発行したデッドロック検出用パケットと同じであるならばデッドロックが発生すると判断するデッドロック検出部６０Ｘ３と、他ノード宛のデッドロック検出用パケットを送信するために用いるポートと同じポートを用いて通信するノードが他に存在するか否かをルーティング情報８０Ｘに従って判断し、存在する場合に、該ノード宛のデッドロック検出用パケットをパケット発行回路６０Ｘ１に発行させる対象ノード検出部６０Ｘ２とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速パケットネットワークなどのネットワークで相互に接続されるノードを制御するノードコントローラに関し、特に、システム運用の前にルーティング情報が正しいか（デッドロックしないか）を確認できるノードコントローラ及びこれを用いたノード、並びにデッドロック検出方法に関する。
【背景技術】
【０００２】
複数の処理要素（ノード）を高速パケットネットワークで接続することによって構成された大規模なコンピュータシステムにおいては、複数のパケットがネットワーク上で循環状にリソース競合を起こすと“デッドロック”が発生する。
【０００３】
デッドロックが発生すると、競合を起こしたリソースの稼働が停止し、最悪の場合はシステム全体が動作不能となる。
【０００４】
このようなデッドロックを避けるために、仮想的なチャネルを設けたり、パケットのルーティング情報をデッドロックしないように構成したりしていた。デッドロックが発生しないようにルーティング情報を構成することに関連する技術としては、特許文献１に開示される「マルチプロセッサ・システムにおける方向順ルーティング」がある。
【０００５】
しかし、前者の仮想的なチャネルを設ける方法では、ハードウェア量が増大してしまうという欠点がある（下記課題〈１〉）。
【０００６】
一方、後者のルーティング情報をデッドロックしないように構成する方法は、ハードウェア量の増大という問題は発生しないが、そのような条件を満たすルーティング情報をどのようにして構成するかが問題となる。特に、ネットワーク構成がフルクロスバやメッシュ、二次元トーラス、ハイパーキューブ等の一般的な構成ではなく、且つ各要素の縮退を許すネットワークにおいては、デッドロックを起こさず、かつノード間が可能な限り最短となるようにルーティング情報を構成するのは非常に難しい。例えば、特許文献１に開示される発明は、ｎ次元トポロジー内で各ノードが２ｎ方向で他のノードに接続された構成のシステムに関するものであるが、実際のネットワークはこのような幾何学的に整然とした構成であるとは限らないため、任意のトポロジーのネットワークに適用することは難しい（下記課題〈２〉）。
【０００７】
デッドロックが発生しうるルーティング情報でシステムを立ち上げてしまった場合でも、一般的にはすぐにはデッドロックは発生せず、負荷が重くなった時にデッドロックが発生するため、その時になって初めてルーティング情報に不備があることが認識されることとなる（下記課題〈３〉）。
【０００８】
すなわち、複数の処理要素（ノード）を高速パケットネットワークで接続することによって構成された大規模コンピュータシステムにおいては、
〈１〉ルーティング情報の設定のみならず、仮想的なチャネルを設ける方法でデッドロックを回避する場合、受信バッファ／送信バッファなどが仮想的なチャネルごとに必要となるため、ハードウェア量が増大する。
〈２〉ネットワーク構成が一般的な構成ではなく、かつ各要素の縮退を許す場合、ネットワーク構成が複雑になるため、デッドロックを起こさずノード間が可能な限り最短となるようなルーティング情報の構成が難しい。
〈３〉デッドロックが発生しうるルーティング情報でシステムを立ち上げてしまった場合、一般的にはシステムの負荷が重くなって初めてデッドロックが顕在化するため、システム運用後にルーティング情報の不備が認識される。
という問題があった。
【０００９】
上記課題〈１〉〜〈３〉に対処しつつパケット通信網におけるデッドロックを回避することに関連する技術として特許文献２に開示される「デッドロックを回避するパケットルーティング方式」がある。
【特許文献１】特表平８−５０３７９９号公報
【特許文献２】特開平１１−１５４９７７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、特許文献２に開示される発明は、通信網内の一部のノードからなるサブ通信網においてデッドロックを検出・排除し、サブ通信網に含めるノード数を順次増やしながら処理を繰り返していくものである。このため、通信網のノード数が多くなると処理に要する時間や、ネットワーク上を流れる循環検索パケットのデータ量が（換言すると、ネットワーク上のトラヒックが）増大してしまう。
【００１１】
本発明は係る問題に鑑みてなされたものであり、ネットワーク上のトラヒックや処理時間、あるいはハードウェア量の増大を招くことなく、システム運用の前にルーティング情報が正しいか（デッドロックしないか）を確認できるノードコントローラ及びこれを用いたノード、並びにデッドロック検出方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明は、第１の態様として、２以上のポートを介して複数の他のノードと接続されるノードに適用され、ポートを介しての他のノードとの通信を制御するノードコントローラであって、デッドロックが発生する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行するパケット発行手段と、他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットを宛先ノードへ送信するための送出経路が、自ノードが既に発行したデッドロック検出用パケットの送出経路と同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出手段と、他ノード宛のデッドロック検出用パケットを宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが宛先ノード以外に存在するか否かを所定のルーティング情報に従って判断し、宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対してパケット発行手段にデッドロック検出用パケットを発行させる対象ノード検出手段とを有することを特徴とするノードコントローラを提供するものである。
【００１３】
また、上記目的を達成するため、本発明は、第２の態様として、上記本発明の第１の態様に係るノードコントローラを有することを特徴とするノードを提供するものである。
【００１４】
また、上記目的を達成するため本発明は、第３の態様として、２以上のポートを介して複数の他のノードと接続され、ポートを介しての他のノードと通信するノードにおけるデッドロック検出方法であって、デッドロックが発生する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行する第１のパケット発行工程と、他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットの送出経路が、第１のパケット発行工程において発行したデッドロック検出用パケットと同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出工程と、他ノード宛のデッドロック検出用パケットを宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが宛先ノード以外に存在するか否かを所定のルーティング情報に従って判断する判断工程と、宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対してデッドロック検出用パケットを発行する第２のパケット発行工程とを有することを特徴とするデッドロック検出方法を提供するものである。
【発明の効果】
【００１５】
本発明によれば、ネットワーク上のトラヒックや処理時間、あるいはハードウェア量の増大を招くことなく、システム運用の前にルーティング情報が正しいか（デッドロックしないか）を確認できるノードコントローラ及びこれを用いたノード、並びにデッドロック検出方法を提供できる。
【発明を実施するための最良の形態】
【００１６】
〔システムの構成〕
図１に、本実施形態に係るコンピュータシステムの構成を示す。このシステムは、複数のノード０〜７がネットワーク８を介して接続された構成である。
ノード０は一般的な演算装置である複数のＣＰＵ００〜０３と、入出力制御用の演算装置である複数のＩＯ Ｈｕｂ０４〜０５と、ノードコントローラ０６とを有する。他のノードも同様の構成である。すなわち、システム構成を一般化すると、ノードＸ（Ｘは０〜７のいずれかの整数）は複数のＣＰＵ Ｘ０〜Ｘ３と、複数のＩＯ Ｈｕｂ Ｘ４〜Ｘ５と、ノードコントローラＸ６とを有する。
【００１７】
各ノード内において、ＣＰＵ−ＣＰＵ間及びＣＰＵ−ノードコントローラ間は、ノード内Ｉ／Ｆで接続されている。一方、ノード同士の接続となるノードコントローラ−ノードコントローラ間は、ノード間Ｉ／Ｆで接続されている。
【００１８】
ノード間Ｉ／Ｆで構成されるネットワーク８は、三次元ハイパーキューブとクロスバとを折衷した構成である。
ノード０−ノード１、ノード２−ノード３、ノード４−ノード５、ノード６−ノード７のそれぞれの間は、各ノードコントローラのノード間Ｉ／Ｆのポート０で接続されている。また、ノード０−ノード２、ノード１−ノード３、ノード４−ノード６、ノード５−ノード７のそれぞれの間は、各ノードコントローラのポート１で接続されている。また、ノード０−ノード３、ノード１−ノード２、ノード４−ノード７、ノード５−ノード６のそれぞれの間は、各ノードコントローラのポート２で接続されている。さらに、ノード０−ノード４、ノード１−ノード５、ノード２−ノード６、ノード３−ノード７のそれぞれの間は、各ノードコントローラのポート３で接続されている。
【００１９】
ノードコントローラの構成について説明する。
図２に、２以上のポートを介して複数の他のノードと接続されるノードＸ（Ｘは０〜７の整数）に適用されるノードコントローラＸ６の要部の構成を示す。ノードコントローラＸ６は、デッドロックが発する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行するパケット発行部６０Ｘ１と、他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットを宛先ノードへ送信するための送出経路が、自ノードが既に発行したデッドロック検出用パケットの送出経路と同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出部６０Ｘ３と、他ノード宛のデッドロック検出用パケットを宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが宛先ノード以外に存在するか否かを所定のルーティング情報８０Ｘに従って判断し、宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対してパケット発行部６０Ｘ１にデッドロック検出用パケットを発行させる対象ノード検出部６０Ｘ２とを有し、ノードＸのポートを介しての他のノードとの通信を制御する。
図３に示すように、ノードＸにはＢＭＣ Ｘ９が接続され、ルーティング情報の設定やデッドロックの原因となる箇所の判断が行われる。
【００２０】
図４に、ノードＸ及びノードコントローラＸ６の詳細な構成を示す。各ノード・ノードコントローラの構成は同様であるため、以下ではＸが０である場合を具体例として説明する。
ノードコントローラ０６は、ノード内Ｉ／Ｆ制御部１００〜１０５、ノード間Ｉ／Ｆ制御部２００〜２０３、デッドロック検出制御部３００、クロスバネットワーク４００、ルーティングテーブル５００を有する。
【００２１】
また、ノード０のノードコントローラ０６には、システムを管理するＢＭＣ（Baseboard Management Controller）０９が接続されている。ＢＭＣ０９は、ルーティング情報の設定を行うプログラムや不適切な箇所を判断するプログラムを有する。ノード１〜７も同様に、ＢＭＣ１９〜７９を備えている。
【００２２】
ノード内Ｉ／Ｆ制御部１００〜１０５は、ノード内Ｉ／Ｆを制御する。ノード間Ｉ／Ｆ制御部２００〜２０３は、ノード間Ｉ／Ｆを制御する。クロスバネットワーク４００は、ノード内Ｉ／Ｆ制御部１００〜１０５、ノード間Ｉ／Ｆ制御部２００〜２０３、及びデッドロック検出制御部３００の間を接続する。
クロスバネットワーク４００に接続された各制御部は、クロスバネットワーク４００にパケットを発行する場合には自ノード宛か否かを判断し、他ノード宛の場合はルーティングテーブル５００に記憶されているルーティング情報８００に基づいて送出先のポートを判別する。
【００２３】
ノード間Ｉ／Ｆ制御部２００〜２０３のそれぞれは、ルーティング回路２００１〜２０３１、パケット検出回路２００２〜２０３２、受信バッファ２００３〜２０３３、及び送信バッファ２００４〜２０３４を有する。ルーティング回路２００１〜２０３１は、ノード間Ｉ／Ｆから受信したパケットの宛先がどのノードであるかを判断し、他ノードであればノード間Ｉ／Ｆ制御部２００〜２０３へ、自ノード宛であればノード内Ｉ／Ｆ制御部１００〜１０５へ出力する。パケット検出回路２００２〜２０３２は、ノードコントローラ０６のデッドロック検出用パケットの受信を検出し、デッドロック検出制御部３００に発行元及び宛先ノード番号を通知する。なお、デッドロック検出用パケットについては後段で詳細に説明する。受信バッファ２００３〜２０３３は、ノード間Ｉ／Ｆから受信したパケットを一時的に格納するための記憶装置である。送信バッファ２００４〜２０３４は、ノード間Ｉ／Ｆへ送出するパケットを一時的に格納するための記憶装置である。
【００２４】
デッドロック検出制御部３００は、パケット発行回路３００１、対象ノード検出回路３００２、及びデッドロック検出回路３００３を有する。
【００２５】
パケット発行回路３００１は、図２に示したパケット発行部６０Ｘ１に対応するものであり、ＢＭＣ０９又は対象ノード検出回路３００２からの指示に応じて、指定されたノードに対してデッドロック検出用パケットを発行する。その際には、送出先のポート番号をデッドロック検出回路３００３に通知する。対象ノード検出回路３００２は、図２に示した対象ノード検出部６０Ｘ２に対応するものであり、パケット検出回路２００２〜２００２から通知された発行元ノード番号からルーティング情報を引き、同一のポートを使用する宛先ノード番号を検出し、該ノードに対してデッドロック検出用パケットを発行するようにパケット発行回路３００１に指示する。デッドロック検出回路３００３は、図２にデッドロック検出部６０Ｘ３に対応するものであり、パケット検出回路２００２〜２００２から通知された発行元ノード番号からルーティング情報を引き、パケット発行回路３００１から通知されたポート番号と同じポート番号であるか否かを比較する。また、デッドロック検出回路は、ノードコントローラのステータス（デッドロックが発生するか否か）を記録するための記憶装置を備えている。
【００２６】
以上の構成を一般化すると、ノードコントローラＸ６（Ｘは０〜７の整数）は、ノード内Ｉ／Ｆ制御部１Ｘ０〜１Ｘ５、ノード間Ｉ／Ｆ制御部２Ｘ０〜２Ｘ３、デッドロック検出制御部３０Ｘ、クロスバネットワーク４０Ｘ、及びルーティングテーブル５０Ｘを有する。そして、ポートＹ（Ｙは、０〜３の整数）を制御するノード間Ｉ／Ｆ制御部２ＸＹは、ルーティング回路２ＸＹ１、パケット検出回路２ＸＹ２、受信バッファ２ＸＹ３、及び送信バッファ２ＸＹ４を有する。また、デッドロック検出制御部３０Ｘは、パケット発行回路３０Ｘ１（図２のパケット発行部６０Ｘ１に対応）、対象ノード検出回路３０Ｘ２（図２の対象ノード検出部６０Ｘ２に対応）、及びデッドロック検出回路３０Ｘ３（図２のデッドロック検出部６０Ｘ３に対応）を有する。
【００２７】
〔デッドロック検出用パケット〕
デッドロック検出用パケットには、通常のルーティングに使用する宛先ノード番号、発行元ノード番号だけでなく、デッドロック検出用パケットの発行要因となった（ＢＭＣからの指示によって発行された以降の全ての）デッドロック検出用パケットの宛先ノード番号、発行元ノード番号も格納される。
通常のルーティングに使用する宛先ノード番号、発行元ノード番号は、（通常のパケットと同様に）デッドロック検出用パケットのヘッダ部に格納される。一方、自パケットの発行要因となったデッドロック検出用パケットの宛先ノード番号、発行元ノード番号は、デッドロック検出用パケットのデータ部に格納される。デッドロック検出用パケットのデータ部には、宛先ノード番号及び発行元ノード番号のペアをＮ−１個（Ｎはノードの総数。ここでは七つ。）格納することが可能である。
【００２８】
図５は、デッドロック検出用パケットのフォーマットを示す図である。デッドロック検出用パケットは、通常のパケットと同様にヘッダ部とデータ部とに分かれている。
ヘッダ部に格納される宛先ノード番号は、通常のパケットにも存在するものであり、デッドロック検出用パケット自身の宛先ノード番号を示している。各ノードコントローラは、ヘッダ部に格納された宛先ノード番号に基づいてデッドロック検出用パケットをルーティングする。ヘッダ部にある発行元ノード番号は、宛先ノード番号同様通常のパケットにも存在するものであり、デッドロック検出用パケット自身の発行元であるノードのノード番号を示している。発行元ノード番号は、デッドロック検出用パケット自身のルーティングには使用されないが、デッドロック検出用パケットに対して宛先ノードからレスポンスのパケットを送る場合、レスポンスパケットのヘッダ部の宛先ノード番号として、デッドロック検出用パケットのヘッダ部に格納されていた発行元ノード番号が格納される。なお、パケット通信においてはパケットのデータ部の大きさは規格によって定められているが（例えば６４バイト）、デッドロック検出用パケットのデータ部に格納される発行元ノード番号−宛先ノード番号の対のデータ量だけでは規格で定められた大きさに満たないため、残り部分（図５におけるReservedの部分）は空のデータとして扱われる。
【００２９】
データ部にある宛先ノード番号、発行元ノード番号は、デッドロック検出用パケットの発行要因となった（ＢＭＣからの指示により発行された以降の全ての）デッドロック検出用パケットのヘッダ部の宛先ノード番号、発行元ノード番号が格納される。
これらの情報は、デッドロック検出時にデッドロック検出回路３０Ｘ３にログ（記録）され、ＢＭＣによる被疑の判断時に使用される。
【００３０】
〔動作〕
デッドロック検出回路３０Ｘ３及びパケット検出回路２ＸＹ２の動作について説明する。
ＢＭＣ０９〜７９は、ルーティング情報８００〜８０７をノード０〜７の各ノードコントローラ０６〜７６のルーティングテーブル５００〜５０７に設定する。設定後、システム内のＢＭＣ０９〜７９は、自身らの中のいずれか一つを選択する。選択されたＢＭＣは、ネットワーク８を介して接続されているノード０〜７の中からデッドロック検出用パケットの宛先とするノードを一つ選択する。宛先ノードを選択した後に、選択されたＢＭＣは、接続されているノードコントローラに対して、宛先として選択したノードへデッドロック検出用パケットを発行するように指示する。その後、選択されたＢＭＣは、規定時間待機した後、デッドロック検出回路３０Ｘ３に格納されているノードコントローラのステータスをＲｅａｄし、デッドロックを検出したか否かを確認する。検出しなかった場合、選択されたＢＭＣは、宛先のノードを変更して同じ動作を実行する。ネットワーク８を介して接続されている他の全てのノードに対して上記の動作を実行してもデッドロックを検出しなかった場合、ＢＭＣ０９〜７９は、自身らの中から選択されていない別のＢＭＣを選択し、上記同様の動作を実行する。
全てのノードの組み合わせにおいてデッドロックを検出しなかった場合、各ノードに設定されたルーティング情報に問題が無いことを意味する。この場合には、最終的には、ネットワーク８で接続された全てのノードの組み合わせにおいて、上記動作が実行されることとなる。
一方、いずれかのノードの組み合わせにおいてデッドロックを検出した場合、いずれかのノードのルーティング情報に問題があることを意味する。ＢＭＣはデッドロック検出回路３０Ｘ３にログされている情報をＲｅａｄし、その情報を基に被疑箇所を特定する。
【００３１】
図６は、ノード０−ノード１、及びノード２−ノード６の間のノード間Ｉ／Ｆが故障等の理由によって切断され、かつルーティング情報が適切に設定されていないためにデッドロックが発生するケースを示している。
【００３２】
以下、ノード１のＢＭＣ１９が選択され、かつＢＭＣ１９によってデッドロック検出用パケットの宛先としてノード４が選択されているものとする。
＜１＞ＢＭＣ１９からデッドロック検出用パケットの発行を指示されたノードコントローラ１６のデッドロック検出制御部３０１のパケット発行回路３０１１は、宛先として指定されているノード４に対して、デッドロック検出用パケットを発行する。その際、デッドロック検出用パケットのヘッダ部には自身のノード番号（ここでは“１”）と宛先のノード番号（ここでは“４”）とを格納する。
【００３３】
パケット発行回路３０１１からクロスバネットワーク４０１にデッドロック検出用パケットを発行するとき、パケット発行回路３００１はルーティングテーブル５０１のルーティング情報８０１から送出先のポートを判別する。図６の“ノード１のルーティング情報”を参照すると、宛先ノード４の送出先ポートは“３”である。パケット発行回路３００１は、この送出先ポートの情報をクロスバネットワーク４０１への発行の時に使用するとともに、デッドロック検出回路３０１３に通知する。
【００３４】
＜２＞ノード１によって発行されたノード４宛のデッドロック検出用パケットは、ノード５のポート３、ポート０を経由してノード４のポート０へ送られる（図６の（１））。
【００３５】
＜３＞ノード４のポート０を制御するノードコントローラ４６のノード間Ｉ／Ｆ制御部２４０のパケット検出回路２４０２は、自ノード宛である上記デッドロック検出用パケット（ノード１から発行されたデッドロック検出用パケット）を検出すると、デッドロック検出用パケットを破棄する。
【００３６】
＜４＞一方、デッドロック検出用パケットが経由するノード５のポート３を制御するノードコントローラ５６のノード間Ｉ／Ｆ制御部２５３のパケット検出回路２５３２は、他ノード宛である上記デッドロック検出用パケット（ノード１によって発行されたノード４宛のデッドロック検出用パケット）を検出すると、デッドロック検出制御部３０５の対象ノード検出回路３０５２とデッドロック検出回路３０５３とに通知する。その際、デッドロック検出用パケットに格納されている宛先ノード番号及び発行元ノード番号も全て通知する（この場合、ヘッダ部の宛先ノード番号“４”−発行元ノード番号“１”、データ部については情報なし）。なお、パケット検出回路３５３２は、デッドロック検出用パケットは破棄しない。
【００３７】
＜５＞パケット検出回路２５３２からの通知を受けたデッドロック検出回路３０５３は、通知されたヘッダ部の宛先ノード番号（この場合“４”）について、ルーティングテーブル５０５のルーティング情報８０５から送出先のポートを判別する。図６の“ノード５のルーティング情報”を参照すると、宛先ノード４の送出先ポートは“０”である。そして、パケット検出回路２５３２からの通知の前にパケット発行回路３０５１から送出先ポート情報の通知が行われている場合、その送出先ポート情報と判別結果とを比較し、一致した場合はデッドロックが発生すると判断し、ログする。その際、パケット検出回路２５３２から通知された全ての宛先ノード番号及び発行元ノード番号もログする。図６に示す例では、パケット発行回路３０５１から送出先ポート情報の通知が行われていない（通知を受けたのはノードコントローラ１６のデッドロック検出回路３０１３である）ため、デッドロックが発生するとは判断しない。
【００３８】
＜６＞一方、上記＜５＞においてパケット検出回路２５３２からの通知を受けた対象ノード検出回路３０５２は、通知されたヘッダ部の宛先ノード番号（この場合“４”）について、ルーティングテーブル５０５のルーティング情報８０５から送出先ポートを判別する。図６の“ノード５のルーティング情報”を参照すると、宛先ノード４の送出先ポートは“０”である。次に、対象ノード検出回路３０５２は、ルーティングテーブル５０５のルーティング情報８０５を逆引きして同じポート（この場合は“ポート０”）を送出先として使用する他のノードを判定する。ノード５のルーティング情報を参照すると、送出先ポートが“０”の他のポートとしてノード０が存在する。
同じポートを送出先とする他のノードが存在するため、対象ノード検出回路３０５２は、パケット発行回路３０５１に対して該ノード（この場合ノード０）に対してデッドロック検出用パケットを発行するように指示する。その際、パケット検出回路２５３２から通知された全ての宛先ノード及び発行元ノード番号（この場合、宛先ノード番号“４”、発行元ノード番号“１”）も通知する。
なお、同じポートを送出先とする他のノードが存在しない場合、対象ノード検出回路３０５２はそれ以降は特に動作はしない。
【００３９】
＜７＞対象ノード検出回路３０５２からデッドロック検出用パケットの発行を指示されたパケット発行回路３０５１は、指示されたノード０に対してデッドロック検出用パケットを発行する。その際デッドロック検出用パケットのヘッダ部には、自分のノード番号と宛先のノード番号とを格納する（この場合には宛先ノード番号０、発行元モード番号５）。さらに、このデッドロック検出用パケットのデータ部には、対象ノード検出回路３０５２から通知された全ての宛先ノード及び発行元ノード番号を格納する（この場合は宛先ノード番号“４”、発行元ノード番号“１”）。なお、ＢＭＣからの指示によるデッドロック検出用パケットの発行時とは異なり、パケット発行回路３０５１は、送出先ポートの情報をデッドロック検出回路３０５３へ通知しない。
【００４０】
＜８＞ノード５から発行されたノード０宛のデッドロック検出用パケットは、ノード４のポート０、ポート３を経由して、ノード０のポート３に送られる（図６の（２））。
【００４１】
＜９＞デッドロック検出用パケットは、図６（３）、（４）に示すようにノード４、ノード０、ノード２、ノード１と順次送られていくため、これらのノードにおいて上記＜３＞〜＜８＞と同様の動作が行われる（図６の（３）、（４））。
【００４２】
以下、ノード２によって発行されたノード５宛のデッドロック検出用パケット（図６の（５））が経由するノード１での動作について説明する。
【００４３】
＜１０＞デッドロック検出用パケットが経由するノード１のポート２を制御するノードコントローラ１６のパケット検出回路２１２２は、他ノード宛である上記デッドロック検出用パケット（ノード２によって発行されたノード５宛のデッドロック検出用パケット）を検出すると、他ノード宛のデッドロック検出用パケットを検出したことをデッドロック検出制御部３０１の対象ノード検出回路３０１２とデッドロック検出回路３０１３とに通知する。その際、デッドロック検出用パケットに格納されている宛先ノード番号及び発行元ノード番号も全て通知する（この場合、ヘッダ部の宛先ノード番号“５”−発行元ノード番号“２”、データ部の宛先ノード番号“４”−発行元ノード番号“１”（図６の（１））、“０”−“５”（図６の（２））、“２”−“４”（図６の（３））、“１”−“０”（図６の（４））。
なお、パケット検出回路２１２２は、このデッドロック検出用パケットを破棄しない。
【００４４】
＜１１＞パケット検出回路２１２２から通知されたノード１のノードコントローラ１６のデッドロック検出回路３０１３は、通知されたヘッダ部の宛先ノード番号（この場合“５”）について、ルーティングテーブル５０１のルーティング情報８０１から送出先のポートを判別する。図６の“ノード１のルーティング情報”を参照すると、宛先ノード５の送出先ポートは“３”である。そして、パケット検出回路２１２２からの通知の前に、パケット発行回路３０１１から送出先ポート情報が通知されている場合、その送出先ポート情報と判別結果とを比較し、一致したならば、デッドロックが発生すると判断し、ログする。
その際、パケット検出回路２１２２から通知された全ての宛先ノード番号及び発行元ノード番号もログする。この場合は、パケット検出回路２１２２から送出先ポート情報の通知が行われており（上記＜１＞）、通知されている送出先ポート番号は“３”である。よって、比較結果が一致するためデッドロックが発生すると判断し、全ての宛先ノード番号及び発行元ノード番号（この場合、宛先ノード番号“４”−“発行元ノード番号“１”、“０”−“５”、“２”−“４”、“１”−“０”、“５”−“２”）も含めてログする。
【００４５】
デッドロック検出回路３０Ｘ３にログされた宛先ノード番号−発行元ノード番号の対は、ＢＭＣＸ９がデッドロックが発生する原因となった被疑箇所を特定するために用いられる。被疑箇所の特定には公知の方法を適用可能であるが、例えば、異なる宛先に発行させた複数のデッドロック検出用パケットについて同じ宛先ノード番号−発行元ノード番号の対が重複してログされている場合には、その部分に問題があると判断できる。
【００４６】
図７は、ルーティング情報が適切でデッドロックが発生しないケースを示す。図６との違いは、ノード０のルーティング情報において宛先ノード１に対応する出力先ポートが図６では“１”であり、図７では“２”であることのみである。この違いにより、ノード０においてノード１に対してデッドロック検出用パケットを発行する時（図６、図７の（４））、送出先ポートが“１”ではなく“２”となる。すなわち、経由するノードがノード２からノード３に変わる。そしてノード３においてデッドロック検出用パケット（図７の（４））の送出先ポート（この場合“１”）を送出先ポートとする他のノードは存在しない。すなわち、ノード３において、新しくデッドロック検出用パケットは発行されず、一連の動作はここで完了となる。
【００４７】
このように、本実施形態に係るコンピュータシステムは、デッドロックが発生するか否かを検出するための専用のパケットを用いてデッドロックを検出するため、デッドロックが発生するか否かをシステム運用前に確認できる。
また、実際にネットワーク上にパケットを流してデッドロックを検出するため、ルーティング情報の構成時のミスだけでなく、ネットワークの接続ミスが要因となる場合も検出可能である。
しかも、ネットワーク上の一部のノードを抜き出して検出処理を行う必要がなく、ネットワーク全体（全ノード）検出処理を行えるため、ネットワーク上のトラヒックや処理時間、あるいはハードウェア量の増大を招くことがない。
【００４８】
なお、上記実施形態は本発明の好適な実施の一例であり、本発明はこれに限定されることはない。例えば、ノード間を結ぶネットワークは完全網などの他のネットワークであっても良い。
このように本発明は様々な変形が可能である。
【図面の簡単な説明】
【００４９】
【図１】本発明の好適な実施の形態に係るコンピュータシステムの構成を示す図である。
【図２】ノードコントローラの要部の構成を示す図である。
【図３】ノードの要部の構成を示す図である。
【図４】本発明の好適な実施の形態に係るコンピュータシステムに適用されるノードの構成を示す図である。
【図５】デッドロック検出用パケットのデータ構造を示す図である。
【図６】デッドロック検出動作の一例を示す図である。
【図７】デッドロック検出動作の一例を示す図である。
【符号の説明】
【００５０】
０、１、２、３、４、５、６、７、Ｘ ノード
８ ネットワーク
００、０１、０２、０３、１０、１１、１２、１３、２０、２１、２２、２３、３０、３１、３２、３３、４０、４１、４２、４３、５０、５１、５２、５３、６０、６１、６２、６３、７０、７１、７２、７３、Ｘ０、Ｘ１、Ｘ２、Ｘ３ ＣＰＵ
０４、０５、１４、２５、３４、３５、４４、４５、５４、５５、６４、６５、７４、７５、Ｘ４、Ｘ５ ＩＯ Ｈｕｂ
０６、１６、２６、３６、４６、５６、６６、７６、Ｘ６ ノードコントローラ
０９、１９、２９、３９、４９、５９、６９、７６、Ｘ９ ＢＭＣ
１Ｘ０、１Ｘ１、１Ｘ２、１Ｘ３、１Ｘ４、１Ｘ５ ノード内Ｉ／Ｆ制御部
２Ｘ０、２ＸＹ ノード間Ｉ／Ｆ制御部
３０Ｘ デッドロック検出制御部
４０Ｘ クロスバネットワーク
５０Ｘ ルーティングテーブル
８０Ｘ ルーティング情報
２Ｘ０１、２ＸＹ１ ルーティング回路
２Ｘ０２、２ＸＹ２ パケット検出回路
２Ｘ０３、２ＸＹ３ 受信バッファ
２Ｘ０４、２ＸＹ４ 送信バッファ
３０Ｘ１ パケット発行回路
３０Ｘ２ 対象ノード検出回路
３０Ｘ３ デッドロック検出回路
６０Ｘ１ パケット発行部
６０Ｘ２ 対象ノード検出部
６０Ｘ３ デッドロック検出部
【技術分野】
【０００１】
本発明は、高速パケットネットワークなどのネットワークで相互に接続されるノードを制御するノードコントローラに関し、特に、システム運用の前にルーティング情報が正しいか（デッドロックしないか）を確認できるノードコントローラ及びこれを用いたノード、並びにデッドロック検出方法に関する。
【背景技術】
【０００２】
複数の処理要素（ノード）を高速パケットネットワークで接続することによって構成された大規模なコンピュータシステムにおいては、複数のパケットがネットワーク上で循環状にリソース競合を起こすと“デッドロック”が発生する。
【０００３】
デッドロックが発生すると、競合を起こしたリソースの稼働が停止し、最悪の場合はシステム全体が動作不能となる。
【０００４】
このようなデッドロックを避けるために、仮想的なチャネルを設けたり、パケットのルーティング情報をデッドロックしないように構成したりしていた。デッドロックが発生しないようにルーティング情報を構成することに関連する技術としては、特許文献１に開示される「マルチプロセッサ・システムにおける方向順ルーティング」がある。
【０００５】
しかし、前者の仮想的なチャネルを設ける方法では、ハードウェア量が増大してしまうという欠点がある（下記課題〈１〉）。
【０００６】
一方、後者のルーティング情報をデッドロックしないように構成する方法は、ハードウェア量の増大という問題は発生しないが、そのような条件を満たすルーティング情報をどのようにして構成するかが問題となる。特に、ネットワーク構成がフルクロスバやメッシュ、二次元トーラス、ハイパーキューブ等の一般的な構成ではなく、且つ各要素の縮退を許すネットワークにおいては、デッドロックを起こさず、かつノード間が可能な限り最短となるようにルーティング情報を構成するのは非常に難しい。例えば、特許文献１に開示される発明は、ｎ次元トポロジー内で各ノードが２ｎ方向で他のノードに接続された構成のシステムに関するものであるが、実際のネットワークはこのような幾何学的に整然とした構成であるとは限らないため、任意のトポロジーのネットワークに適用することは難しい（下記課題〈２〉）。
【０００７】
デッドロックが発生しうるルーティング情報でシステムを立ち上げてしまった場合でも、一般的にはすぐにはデッドロックは発生せず、負荷が重くなった時にデッドロックが発生するため、その時になって初めてルーティング情報に不備があることが認識されることとなる（下記課題〈３〉）。
【０００８】
すなわち、複数の処理要素（ノード）を高速パケットネットワークで接続することによって構成された大規模コンピュータシステムにおいては、
〈１〉ルーティング情報の設定のみならず、仮想的なチャネルを設ける方法でデッドロックを回避する場合、受信バッファ／送信バッファなどが仮想的なチャネルごとに必要となるため、ハードウェア量が増大する。
〈２〉ネットワーク構成が一般的な構成ではなく、かつ各要素の縮退を許す場合、ネットワーク構成が複雑になるため、デッドロックを起こさずノード間が可能な限り最短となるようなルーティング情報の構成が難しい。
〈３〉デッドロックが発生しうるルーティング情報でシステムを立ち上げてしまった場合、一般的にはシステムの負荷が重くなって初めてデッドロックが顕在化するため、システム運用後にルーティング情報の不備が認識される。
という問題があった。
【０００９】
上記課題〈１〉〜〈３〉に対処しつつパケット通信網におけるデッドロックを回避することに関連する技術として特許文献２に開示される「デッドロックを回避するパケットルーティング方式」がある。
【特許文献１】特表平８−５０３７９９号公報
【特許文献２】特開平１１−１５４９７７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、特許文献２に開示される発明は、通信網内の一部のノードからなるサブ通信網においてデッドロックを検出・排除し、サブ通信網に含めるノード数を順次増やしながら処理を繰り返していくものである。このため、通信網のノード数が多くなると処理に要する時間や、ネットワーク上を流れる循環検索パケットのデータ量が（換言すると、ネットワーク上のトラヒックが）増大してしまう。
【００１１】
本発明は係る問題に鑑みてなされたものであり、ネットワーク上のトラヒックや処理時間、あるいはハードウェア量の増大を招くことなく、システム運用の前にルーティング情報が正しいか（デッドロックしないか）を確認できるノードコントローラ及びこれを用いたノード、並びにデッドロック検出方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明は、第１の態様として、２以上のポートを介して複数の他のノードと接続されるノードに適用され、ポートを介しての他のノードとの通信を制御するノードコントローラであって、デッドロックが発生する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行するパケット発行手段と、他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットを宛先ノードへ送信するための送出経路が、自ノードが既に発行したデッドロック検出用パケットの送出経路と同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出手段と、他ノード宛のデッドロック検出用パケットを宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが宛先ノード以外に存在するか否かを所定のルーティング情報に従って判断し、宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対してパケット発行手段にデッドロック検出用パケットを発行させる対象ノード検出手段とを有することを特徴とするノードコントローラを提供するものである。
【００１３】
また、上記目的を達成するため、本発明は、第２の態様として、上記本発明の第１の態様に係るノードコントローラを有することを特徴とするノードを提供するものである。
【００１４】
また、上記目的を達成するため本発明は、第３の態様として、２以上のポートを介して複数の他のノードと接続され、ポートを介しての他のノードと通信するノードにおけるデッドロック検出方法であって、デッドロックが発生する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行する第１のパケット発行工程と、他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットの送出経路が、第１のパケット発行工程において発行したデッドロック検出用パケットと同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出工程と、他ノード宛のデッドロック検出用パケットを宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが宛先ノード以外に存在するか否かを所定のルーティング情報に従って判断する判断工程と、宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対してデッドロック検出用パケットを発行する第２のパケット発行工程とを有することを特徴とするデッドロック検出方法を提供するものである。
【発明の効果】
【００１５】
本発明によれば、ネットワーク上のトラヒックや処理時間、あるいはハードウェア量の増大を招くことなく、システム運用の前にルーティング情報が正しいか（デッドロックしないか）を確認できるノードコントローラ及びこれを用いたノード、並びにデッドロック検出方法を提供できる。
【発明を実施するための最良の形態】
【００１６】
〔システムの構成〕
図１に、本実施形態に係るコンピュータシステムの構成を示す。このシステムは、複数のノード０〜７がネットワーク８を介して接続された構成である。
ノード０は一般的な演算装置である複数のＣＰＵ００〜０３と、入出力制御用の演算装置である複数のＩＯ Ｈｕｂ０４〜０５と、ノードコントローラ０６とを有する。他のノードも同様の構成である。すなわち、システム構成を一般化すると、ノードＸ（Ｘは０〜７のいずれかの整数）は複数のＣＰＵ Ｘ０〜Ｘ３と、複数のＩＯ Ｈｕｂ Ｘ４〜Ｘ５と、ノードコントローラＸ６とを有する。
【００１７】
各ノード内において、ＣＰＵ−ＣＰＵ間及びＣＰＵ−ノードコントローラ間は、ノード内Ｉ／Ｆで接続されている。一方、ノード同士の接続となるノードコントローラ−ノードコントローラ間は、ノード間Ｉ／Ｆで接続されている。
【００１８】
ノード間Ｉ／Ｆで構成されるネットワーク８は、三次元ハイパーキューブとクロスバとを折衷した構成である。
ノード０−ノード１、ノード２−ノード３、ノード４−ノード５、ノード６−ノード７のそれぞれの間は、各ノードコントローラのノード間Ｉ／Ｆのポート０で接続されている。また、ノード０−ノード２、ノード１−ノード３、ノード４−ノード６、ノード５−ノード７のそれぞれの間は、各ノードコントローラのポート１で接続されている。また、ノード０−ノード３、ノード１−ノード２、ノード４−ノード７、ノード５−ノード６のそれぞれの間は、各ノードコントローラのポート２で接続されている。さらに、ノード０−ノード４、ノード１−ノード５、ノード２−ノード６、ノード３−ノード７のそれぞれの間は、各ノードコントローラのポート３で接続されている。
【００１９】
ノードコントローラの構成について説明する。
図２に、２以上のポートを介して複数の他のノードと接続されるノードＸ（Ｘは０〜７の整数）に適用されるノードコントローラＸ６の要部の構成を示す。ノードコントローラＸ６は、デッドロックが発する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行するパケット発行部６０Ｘ１と、他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットを宛先ノードへ送信するための送出経路が、自ノードが既に発行したデッドロック検出用パケットの送出経路と同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出部６０Ｘ３と、他ノード宛のデッドロック検出用パケットを宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが宛先ノード以外に存在するか否かを所定のルーティング情報８０Ｘに従って判断し、宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対してパケット発行部６０Ｘ１にデッドロック検出用パケットを発行させる対象ノード検出部６０Ｘ２とを有し、ノードＸのポートを介しての他のノードとの通信を制御する。
図３に示すように、ノードＸにはＢＭＣ Ｘ９が接続され、ルーティング情報の設定やデッドロックの原因となる箇所の判断が行われる。
【００２０】
図４に、ノードＸ及びノードコントローラＸ６の詳細な構成を示す。各ノード・ノードコントローラの構成は同様であるため、以下ではＸが０である場合を具体例として説明する。
ノードコントローラ０６は、ノード内Ｉ／Ｆ制御部１００〜１０５、ノード間Ｉ／Ｆ制御部２００〜２０３、デッドロック検出制御部３００、クロスバネットワーク４００、ルーティングテーブル５００を有する。
【００２１】
また、ノード０のノードコントローラ０６には、システムを管理するＢＭＣ（Baseboard Management Controller）０９が接続されている。ＢＭＣ０９は、ルーティング情報の設定を行うプログラムや不適切な箇所を判断するプログラムを有する。ノード１〜７も同様に、ＢＭＣ１９〜７９を備えている。
【００２２】
ノード内Ｉ／Ｆ制御部１００〜１０５は、ノード内Ｉ／Ｆを制御する。ノード間Ｉ／Ｆ制御部２００〜２０３は、ノード間Ｉ／Ｆを制御する。クロスバネットワーク４００は、ノード内Ｉ／Ｆ制御部１００〜１０５、ノード間Ｉ／Ｆ制御部２００〜２０３、及びデッドロック検出制御部３００の間を接続する。
クロスバネットワーク４００に接続された各制御部は、クロスバネットワーク４００にパケットを発行する場合には自ノード宛か否かを判断し、他ノード宛の場合はルーティングテーブル５００に記憶されているルーティング情報８００に基づいて送出先のポートを判別する。
【００２３】
ノード間Ｉ／Ｆ制御部２００〜２０３のそれぞれは、ルーティング回路２００１〜２０３１、パケット検出回路２００２〜２０３２、受信バッファ２００３〜２０３３、及び送信バッファ２００４〜２０３４を有する。ルーティング回路２００１〜２０３１は、ノード間Ｉ／Ｆから受信したパケットの宛先がどのノードであるかを判断し、他ノードであればノード間Ｉ／Ｆ制御部２００〜２０３へ、自ノード宛であればノード内Ｉ／Ｆ制御部１００〜１０５へ出力する。パケット検出回路２００２〜２０３２は、ノードコントローラ０６のデッドロック検出用パケットの受信を検出し、デッドロック検出制御部３００に発行元及び宛先ノード番号を通知する。なお、デッドロック検出用パケットについては後段で詳細に説明する。受信バッファ２００３〜２０３３は、ノード間Ｉ／Ｆから受信したパケットを一時的に格納するための記憶装置である。送信バッファ２００４〜２０３４は、ノード間Ｉ／Ｆへ送出するパケットを一時的に格納するための記憶装置である。
【００２４】
デッドロック検出制御部３００は、パケット発行回路３００１、対象ノード検出回路３００２、及びデッドロック検出回路３００３を有する。
【００２５】
パケット発行回路３００１は、図２に示したパケット発行部６０Ｘ１に対応するものであり、ＢＭＣ０９又は対象ノード検出回路３００２からの指示に応じて、指定されたノードに対してデッドロック検出用パケットを発行する。その際には、送出先のポート番号をデッドロック検出回路３００３に通知する。対象ノード検出回路３００２は、図２に示した対象ノード検出部６０Ｘ２に対応するものであり、パケット検出回路２００２〜２００２から通知された発行元ノード番号からルーティング情報を引き、同一のポートを使用する宛先ノード番号を検出し、該ノードに対してデッドロック検出用パケットを発行するようにパケット発行回路３００１に指示する。デッドロック検出回路３００３は、図２にデッドロック検出部６０Ｘ３に対応するものであり、パケット検出回路２００２〜２００２から通知された発行元ノード番号からルーティング情報を引き、パケット発行回路３００１から通知されたポート番号と同じポート番号であるか否かを比較する。また、デッドロック検出回路は、ノードコントローラのステータス（デッドロックが発生するか否か）を記録するための記憶装置を備えている。
【００２６】
以上の構成を一般化すると、ノードコントローラＸ６（Ｘは０〜７の整数）は、ノード内Ｉ／Ｆ制御部１Ｘ０〜１Ｘ５、ノード間Ｉ／Ｆ制御部２Ｘ０〜２Ｘ３、デッドロック検出制御部３０Ｘ、クロスバネットワーク４０Ｘ、及びルーティングテーブル５０Ｘを有する。そして、ポートＹ（Ｙは、０〜３の整数）を制御するノード間Ｉ／Ｆ制御部２ＸＹは、ルーティング回路２ＸＹ１、パケット検出回路２ＸＹ２、受信バッファ２ＸＹ３、及び送信バッファ２ＸＹ４を有する。また、デッドロック検出制御部３０Ｘは、パケット発行回路３０Ｘ１（図２のパケット発行部６０Ｘ１に対応）、対象ノード検出回路３０Ｘ２（図２の対象ノード検出部６０Ｘ２に対応）、及びデッドロック検出回路３０Ｘ３（図２のデッドロック検出部６０Ｘ３に対応）を有する。
【００２７】
〔デッドロック検出用パケット〕
デッドロック検出用パケットには、通常のルーティングに使用する宛先ノード番号、発行元ノード番号だけでなく、デッドロック検出用パケットの発行要因となった（ＢＭＣからの指示によって発行された以降の全ての）デッドロック検出用パケットの宛先ノード番号、発行元ノード番号も格納される。
通常のルーティングに使用する宛先ノード番号、発行元ノード番号は、（通常のパケットと同様に）デッドロック検出用パケットのヘッダ部に格納される。一方、自パケットの発行要因となったデッドロック検出用パケットの宛先ノード番号、発行元ノード番号は、デッドロック検出用パケットのデータ部に格納される。デッドロック検出用パケットのデータ部には、宛先ノード番号及び発行元ノード番号のペアをＮ−１個（Ｎはノードの総数。ここでは七つ。）格納することが可能である。
【００２８】
図５は、デッドロック検出用パケットのフォーマットを示す図である。デッドロック検出用パケットは、通常のパケットと同様にヘッダ部とデータ部とに分かれている。
ヘッダ部に格納される宛先ノード番号は、通常のパケットにも存在するものであり、デッドロック検出用パケット自身の宛先ノード番号を示している。各ノードコントローラは、ヘッダ部に格納された宛先ノード番号に基づいてデッドロック検出用パケットをルーティングする。ヘッダ部にある発行元ノード番号は、宛先ノード番号同様通常のパケットにも存在するものであり、デッドロック検出用パケット自身の発行元であるノードのノード番号を示している。発行元ノード番号は、デッドロック検出用パケット自身のルーティングには使用されないが、デッドロック検出用パケットに対して宛先ノードからレスポンスのパケットを送る場合、レスポンスパケットのヘッダ部の宛先ノード番号として、デッドロック検出用パケットのヘッダ部に格納されていた発行元ノード番号が格納される。なお、パケット通信においてはパケットのデータ部の大きさは規格によって定められているが（例えば６４バイト）、デッドロック検出用パケットのデータ部に格納される発行元ノード番号−宛先ノード番号の対のデータ量だけでは規格で定められた大きさに満たないため、残り部分（図５におけるReservedの部分）は空のデータとして扱われる。
【００２９】
データ部にある宛先ノード番号、発行元ノード番号は、デッドロック検出用パケットの発行要因となった（ＢＭＣからの指示により発行された以降の全ての）デッドロック検出用パケットのヘッダ部の宛先ノード番号、発行元ノード番号が格納される。
これらの情報は、デッドロック検出時にデッドロック検出回路３０Ｘ３にログ（記録）され、ＢＭＣによる被疑の判断時に使用される。
【００３０】
〔動作〕
デッドロック検出回路３０Ｘ３及びパケット検出回路２ＸＹ２の動作について説明する。
ＢＭＣ０９〜７９は、ルーティング情報８００〜８０７をノード０〜７の各ノードコントローラ０６〜７６のルーティングテーブル５００〜５０７に設定する。設定後、システム内のＢＭＣ０９〜７９は、自身らの中のいずれか一つを選択する。選択されたＢＭＣは、ネットワーク８を介して接続されているノード０〜７の中からデッドロック検出用パケットの宛先とするノードを一つ選択する。宛先ノードを選択した後に、選択されたＢＭＣは、接続されているノードコントローラに対して、宛先として選択したノードへデッドロック検出用パケットを発行するように指示する。その後、選択されたＢＭＣは、規定時間待機した後、デッドロック検出回路３０Ｘ３に格納されているノードコントローラのステータスをＲｅａｄし、デッドロックを検出したか否かを確認する。検出しなかった場合、選択されたＢＭＣは、宛先のノードを変更して同じ動作を実行する。ネットワーク８を介して接続されている他の全てのノードに対して上記の動作を実行してもデッドロックを検出しなかった場合、ＢＭＣ０９〜７９は、自身らの中から選択されていない別のＢＭＣを選択し、上記同様の動作を実行する。
全てのノードの組み合わせにおいてデッドロックを検出しなかった場合、各ノードに設定されたルーティング情報に問題が無いことを意味する。この場合には、最終的には、ネットワーク８で接続された全てのノードの組み合わせにおいて、上記動作が実行されることとなる。
一方、いずれかのノードの組み合わせにおいてデッドロックを検出した場合、いずれかのノードのルーティング情報に問題があることを意味する。ＢＭＣはデッドロック検出回路３０Ｘ３にログされている情報をＲｅａｄし、その情報を基に被疑箇所を特定する。
【００３１】
図６は、ノード０−ノード１、及びノード２−ノード６の間のノード間Ｉ／Ｆが故障等の理由によって切断され、かつルーティング情報が適切に設定されていないためにデッドロックが発生するケースを示している。
【００３２】
以下、ノード１のＢＭＣ１９が選択され、かつＢＭＣ１９によってデッドロック検出用パケットの宛先としてノード４が選択されているものとする。
＜１＞ＢＭＣ１９からデッドロック検出用パケットの発行を指示されたノードコントローラ１６のデッドロック検出制御部３０１のパケット発行回路３０１１は、宛先として指定されているノード４に対して、デッドロック検出用パケットを発行する。その際、デッドロック検出用パケットのヘッダ部には自身のノード番号（ここでは“１”）と宛先のノード番号（ここでは“４”）とを格納する。
【００３３】
パケット発行回路３０１１からクロスバネットワーク４０１にデッドロック検出用パケットを発行するとき、パケット発行回路３００１はルーティングテーブル５０１のルーティング情報８０１から送出先のポートを判別する。図６の“ノード１のルーティング情報”を参照すると、宛先ノード４の送出先ポートは“３”である。パケット発行回路３００１は、この送出先ポートの情報をクロスバネットワーク４０１への発行の時に使用するとともに、デッドロック検出回路３０１３に通知する。
【００３４】
＜２＞ノード１によって発行されたノード４宛のデッドロック検出用パケットは、ノード５のポート３、ポート０を経由してノード４のポート０へ送られる（図６の（１））。
【００３５】
＜３＞ノード４のポート０を制御するノードコントローラ４６のノード間Ｉ／Ｆ制御部２４０のパケット検出回路２４０２は、自ノード宛である上記デッドロック検出用パケット（ノード１から発行されたデッドロック検出用パケット）を検出すると、デッドロック検出用パケットを破棄する。
【００３６】
＜４＞一方、デッドロック検出用パケットが経由するノード５のポート３を制御するノードコントローラ５６のノード間Ｉ／Ｆ制御部２５３のパケット検出回路２５３２は、他ノード宛である上記デッドロック検出用パケット（ノード１によって発行されたノード４宛のデッドロック検出用パケット）を検出すると、デッドロック検出制御部３０５の対象ノード検出回路３０５２とデッドロック検出回路３０５３とに通知する。その際、デッドロック検出用パケットに格納されている宛先ノード番号及び発行元ノード番号も全て通知する（この場合、ヘッダ部の宛先ノード番号“４”−発行元ノード番号“１”、データ部については情報なし）。なお、パケット検出回路３５３２は、デッドロック検出用パケットは破棄しない。
【００３７】
＜５＞パケット検出回路２５３２からの通知を受けたデッドロック検出回路３０５３は、通知されたヘッダ部の宛先ノード番号（この場合“４”）について、ルーティングテーブル５０５のルーティング情報８０５から送出先のポートを判別する。図６の“ノード５のルーティング情報”を参照すると、宛先ノード４の送出先ポートは“０”である。そして、パケット検出回路２５３２からの通知の前にパケット発行回路３０５１から送出先ポート情報の通知が行われている場合、その送出先ポート情報と判別結果とを比較し、一致した場合はデッドロックが発生すると判断し、ログする。その際、パケット検出回路２５３２から通知された全ての宛先ノード番号及び発行元ノード番号もログする。図６に示す例では、パケット発行回路３０５１から送出先ポート情報の通知が行われていない（通知を受けたのはノードコントローラ１６のデッドロック検出回路３０１３である）ため、デッドロックが発生するとは判断しない。
【００３８】
＜６＞一方、上記＜５＞においてパケット検出回路２５３２からの通知を受けた対象ノード検出回路３０５２は、通知されたヘッダ部の宛先ノード番号（この場合“４”）について、ルーティングテーブル５０５のルーティング情報８０５から送出先ポートを判別する。図６の“ノード５のルーティング情報”を参照すると、宛先ノード４の送出先ポートは“０”である。次に、対象ノード検出回路３０５２は、ルーティングテーブル５０５のルーティング情報８０５を逆引きして同じポート（この場合は“ポート０”）を送出先として使用する他のノードを判定する。ノード５のルーティング情報を参照すると、送出先ポートが“０”の他のポートとしてノード０が存在する。
同じポートを送出先とする他のノードが存在するため、対象ノード検出回路３０５２は、パケット発行回路３０５１に対して該ノード（この場合ノード０）に対してデッドロック検出用パケットを発行するように指示する。その際、パケット検出回路２５３２から通知された全ての宛先ノード及び発行元ノード番号（この場合、宛先ノード番号“４”、発行元ノード番号“１”）も通知する。
なお、同じポートを送出先とする他のノードが存在しない場合、対象ノード検出回路３０５２はそれ以降は特に動作はしない。
【００３９】
＜７＞対象ノード検出回路３０５２からデッドロック検出用パケットの発行を指示されたパケット発行回路３０５１は、指示されたノード０に対してデッドロック検出用パケットを発行する。その際デッドロック検出用パケットのヘッダ部には、自分のノード番号と宛先のノード番号とを格納する（この場合には宛先ノード番号０、発行元モード番号５）。さらに、このデッドロック検出用パケットのデータ部には、対象ノード検出回路３０５２から通知された全ての宛先ノード及び発行元ノード番号を格納する（この場合は宛先ノード番号“４”、発行元ノード番号“１”）。なお、ＢＭＣからの指示によるデッドロック検出用パケットの発行時とは異なり、パケット発行回路３０５１は、送出先ポートの情報をデッドロック検出回路３０５３へ通知しない。
【００４０】
＜８＞ノード５から発行されたノード０宛のデッドロック検出用パケットは、ノード４のポート０、ポート３を経由して、ノード０のポート３に送られる（図６の（２））。
【００４１】
＜９＞デッドロック検出用パケットは、図６（３）、（４）に示すようにノード４、ノード０、ノード２、ノード１と順次送られていくため、これらのノードにおいて上記＜３＞〜＜８＞と同様の動作が行われる（図６の（３）、（４））。
【００４２】
以下、ノード２によって発行されたノード５宛のデッドロック検出用パケット（図６の（５））が経由するノード１での動作について説明する。
【００４３】
＜１０＞デッドロック検出用パケットが経由するノード１のポート２を制御するノードコントローラ１６のパケット検出回路２１２２は、他ノード宛である上記デッドロック検出用パケット（ノード２によって発行されたノード５宛のデッドロック検出用パケット）を検出すると、他ノード宛のデッドロック検出用パケットを検出したことをデッドロック検出制御部３０１の対象ノード検出回路３０１２とデッドロック検出回路３０１３とに通知する。その際、デッドロック検出用パケットに格納されている宛先ノード番号及び発行元ノード番号も全て通知する（この場合、ヘッダ部の宛先ノード番号“５”−発行元ノード番号“２”、データ部の宛先ノード番号“４”−発行元ノード番号“１”（図６の（１））、“０”−“５”（図６の（２））、“２”−“４”（図６の（３））、“１”−“０”（図６の（４））。
なお、パケット検出回路２１２２は、このデッドロック検出用パケットを破棄しない。
【００４４】
＜１１＞パケット検出回路２１２２から通知されたノード１のノードコントローラ１６のデッドロック検出回路３０１３は、通知されたヘッダ部の宛先ノード番号（この場合“５”）について、ルーティングテーブル５０１のルーティング情報８０１から送出先のポートを判別する。図６の“ノード１のルーティング情報”を参照すると、宛先ノード５の送出先ポートは“３”である。そして、パケット検出回路２１２２からの通知の前に、パケット発行回路３０１１から送出先ポート情報が通知されている場合、その送出先ポート情報と判別結果とを比較し、一致したならば、デッドロックが発生すると判断し、ログする。
その際、パケット検出回路２１２２から通知された全ての宛先ノード番号及び発行元ノード番号もログする。この場合は、パケット検出回路２１２２から送出先ポート情報の通知が行われており（上記＜１＞）、通知されている送出先ポート番号は“３”である。よって、比較結果が一致するためデッドロックが発生すると判断し、全ての宛先ノード番号及び発行元ノード番号（この場合、宛先ノード番号“４”−“発行元ノード番号“１”、“０”−“５”、“２”−“４”、“１”−“０”、“５”−“２”）も含めてログする。
【００４５】
デッドロック検出回路３０Ｘ３にログされた宛先ノード番号−発行元ノード番号の対は、ＢＭＣＸ９がデッドロックが発生する原因となった被疑箇所を特定するために用いられる。被疑箇所の特定には公知の方法を適用可能であるが、例えば、異なる宛先に発行させた複数のデッドロック検出用パケットについて同じ宛先ノード番号−発行元ノード番号の対が重複してログされている場合には、その部分に問題があると判断できる。
【００４６】
図７は、ルーティング情報が適切でデッドロックが発生しないケースを示す。図６との違いは、ノード０のルーティング情報において宛先ノード１に対応する出力先ポートが図６では“１”であり、図７では“２”であることのみである。この違いにより、ノード０においてノード１に対してデッドロック検出用パケットを発行する時（図６、図７の（４））、送出先ポートが“１”ではなく“２”となる。すなわち、経由するノードがノード２からノード３に変わる。そしてノード３においてデッドロック検出用パケット（図７の（４））の送出先ポート（この場合“１”）を送出先ポートとする他のノードは存在しない。すなわち、ノード３において、新しくデッドロック検出用パケットは発行されず、一連の動作はここで完了となる。
【００４７】
このように、本実施形態に係るコンピュータシステムは、デッドロックが発生するか否かを検出するための専用のパケットを用いてデッドロックを検出するため、デッドロックが発生するか否かをシステム運用前に確認できる。
また、実際にネットワーク上にパケットを流してデッドロックを検出するため、ルーティング情報の構成時のミスだけでなく、ネットワークの接続ミスが要因となる場合も検出可能である。
しかも、ネットワーク上の一部のノードを抜き出して検出処理を行う必要がなく、ネットワーク全体（全ノード）検出処理を行えるため、ネットワーク上のトラヒックや処理時間、あるいはハードウェア量の増大を招くことがない。
【００４８】
なお、上記実施形態は本発明の好適な実施の一例であり、本発明はこれに限定されることはない。例えば、ノード間を結ぶネットワークは完全網などの他のネットワークであっても良い。
このように本発明は様々な変形が可能である。
【図面の簡単な説明】
【００４９】
【図１】本発明の好適な実施の形態に係るコンピュータシステムの構成を示す図である。
【図２】ノードコントローラの要部の構成を示す図である。
【図３】ノードの要部の構成を示す図である。
【図４】本発明の好適な実施の形態に係るコンピュータシステムに適用されるノードの構成を示す図である。
【図５】デッドロック検出用パケットのデータ構造を示す図である。
【図６】デッドロック検出動作の一例を示す図である。
【図７】デッドロック検出動作の一例を示す図である。
【符号の説明】
【００５０】
０、１、２、３、４、５、６、７、Ｘ ノード
８ ネットワーク
００、０１、０２、０３、１０、１１、１２、１３、２０、２１、２２、２３、３０、３１、３２、３３、４０、４１、４２、４３、５０、５１、５２、５３、６０、６１、６２、６３、７０、７１、７２、７３、Ｘ０、Ｘ１、Ｘ２、Ｘ３ ＣＰＵ
０４、０５、１４、２５、３４、３５、４４、４５、５４、５５、６４、６５、７４、７５、Ｘ４、Ｘ５ ＩＯ Ｈｕｂ
０６、１６、２６、３６、４６、５６、６６、７６、Ｘ６ ノードコントローラ
０９、１９、２９、３９、４９、５９、６９、７６、Ｘ９ ＢＭＣ
１Ｘ０、１Ｘ１、１Ｘ２、１Ｘ３、１Ｘ４、１Ｘ５ ノード内Ｉ／Ｆ制御部
２Ｘ０、２ＸＹ ノード間Ｉ／Ｆ制御部
３０Ｘ デッドロック検出制御部
４０Ｘ クロスバネットワーク
５０Ｘ ルーティングテーブル
８０Ｘ ルーティング情報
２Ｘ０１、２ＸＹ１ ルーティング回路
２Ｘ０２、２ＸＹ２ パケット検出回路
２Ｘ０３、２ＸＹ３ 受信バッファ
２Ｘ０４、２ＸＹ４ 送信バッファ
３０Ｘ１ パケット発行回路
３０Ｘ２ 対象ノード検出回路
３０Ｘ３ デッドロック検出回路
６０Ｘ１ パケット発行部
６０Ｘ２ 対象ノード検出部
６０Ｘ３ デッドロック検出部
【特許請求の範囲】
【請求項１】
２以上のポートを介して複数の他のノードと接続されるノードに適用され、前記ポートを介しての他のノードとの通信を制御するノードコントローラであって、
デッドロックが発生する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行するパケット発行手段と、
他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットを宛先ノードへ送信するための送出経路が、自ノードが既に発行したデッドロック検出用パケットの送出経路と同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出手段と、
前記他ノード宛のデッドロック検出用パケットを前記宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが前記宛先ノード以外に存在するか否かを所定のルーティング情報に従って判断し、前記宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対して前記パケット発行手段にデッドロック検出用パケットを発行させる対象ノード検出手段とを有することを特徴とするノードコントローラ。
【請求項２】
前記デッドロック検出手段は、宛先ノードへ送信するための送出経路が、外部に接続されるコントローラからの指示に応じて自ノードが既に発行したデッドロック検出用パケットの送出経路と同じである他ノード宛のデッドロック検出用パケットを受信した場合に、デッドロックが発生すると判断することを特徴とする請求項１記載のノードコントローラ。
【請求項３】
前記ルーティング情報は、前記各ノードの識別子と前記ポートの識別子とを対とするテーブルであることを特徴とする請求項１又は２記載のノードコントローラ。
【請求項４】
前記デッドロック検出用パケットは、ヘッダ部とデータ部とからなり、自パケットの発行要因となった全てのデッドロック検出用パケットの発行元ノードの識別子と宛先ノードの識別子との対が前記データ部に格納されていることを特徴とする請求項１から３のいずれか１項記載のノードコントローラ。
【請求項５】
前記各ポートを介した通信を管理する複数のノード間通信制御手段をさらに備え、
前記ノード間通信制御手段のそれぞれは、他のノード宛のデッドロック検出用パケットを自身が管理するポートを介して受信した場合に、該デッドロック検出用パケットのヘッダ部及びデータ部に格納されていた全ての宛先ノード及び発行元ノードの識別子を、前記対象ノード検出手段に通知するパケット検出手段を備え、
前記パケット発行手段は、外部に接続されるコントローラから又は対象ノード検出手段からの指示に応じて、指示されたノードに対して前記デッドロック検出用パケットを発行するとともに、前記コントローラから指示を受けた場合のみデッドロック検出手段に対して前記デッドロック検出用パケットの発行に用いるポートを表す送出先ポート情報を通知し、
前記対象ノード検出手段は、前記デッドロック検出用パケットのヘッダ部に識別子が格納されていたと前記パケット検出手段から通知されたノードと同じポートを送出先として使用するノードが存在するか否かを前記ルーティング情報に基づいて判断し、存在するならばそのノードへのデッドロック検出用パケットの発行を前記パケット発行手段に対して指示し、
前記デッドロック検出手段は、前記デッドロック検出用パケットのヘッダ部に識別子が格納されていたと前記パケット検出手段から通知されたノードとの通信に用いるポートを前記ルーティング情報に基づいて特定するとともに、前記パケット検出手段からの通知よりも前に前記パケット発行手段から送出先ポート情報が通知されている場合は、特定したポートが前記送出先ポート情報が示すポートと一致するか否かを判断し、一致する場合にはデッドロックが発生すると判断することを特徴とする請求項３記載のノードコントローラ。
【請求項６】
前記デッドロック検出手段がデッドロックが発生すると判断した場合に、判断に用いた前記他ノード宛のデッドロック検出用パケットに格納されている発行元ノードの識別子と宛先ノードの識別子との対の全てを記録することを特徴とする請求項４又は５記載のノードコントローラ。
【請求項７】
請求項１から６のいずれか１項記載のノードコントローラを有することを特徴とするノード。
【請求項８】
前記パケット発行手段に対し前記デッドロック検出用パケットの発行を指示するコントローラが接続されることを特徴とする請求項７記載のノード。
【請求項９】
請求項６記載のノードコントローラを有し、前記パケット発行手段に対して前記デッドロック検出用パケットの発行を指示するとともに、前記デッドロック検出手段によって記録された発行元ノードの識別子と宛先ノードの識別子との対を基に、デッドロックが発生する原因となる箇所を特定するコントローラが接続されることを特徴とするノード。
【請求項１０】
２以上のポートを介して複数の他のノードと接続され、前記ポートを介しての他のノードと通信するノードにおけるデッドロック検出方法であって、
デッドロックが発生する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行する第１のパケット発行工程と、
他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットの送出経路が、前記第１のパケット発行工程において発行したデッドロック検出用パケットと同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出工程と、
前記他ノード宛のデッドロック検出用パケットを宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが前記宛先ノード以外に存在するか否かを所定のルーティング情報に従って判断する判断工程と、
前記宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対して前記デッドロック検出用パケットを発行する第２のパケット発行工程とを有することを特徴とするデッドロック検出方法。
【請求項１１】
前記第１のパケット発行工程においては、自ノードの外部に接続されるコントローラからの指示に応じて前記デッドロック検出用パケットを発行することを特徴とする請求項１０記載のデッドロック検出方法。
【請求項１２】
前記第２のパケット発行工程においては、自パケットの発行要因となった全てのデッドロック検出用パケットの発行元ノードの識別子と宛先ノードの識別子との対を前記デッドロック検出用パケットに格納して発行することを特徴とする請求項１０又は１１記載のデッドロック検出方法。
【請求項１３】
前記デッドロック検出用パケットは、ヘッダ部とデータ部とからなり、自パケットの発行要因となった全てのデッドロック検出用パケットの発行元ノードの識別子と宛先ノードの識別子との対は、前記データ部に格納されていることを特徴とする請求項１２記載のデッドロック検出方法。
【請求項１４】
前記デッドロック検出工程においてデッドロックが発生すると判断した場合に、判断に用いた前記他ノード宛のデッドロック検出用パケットに格納されている発行元ノードの識別子と宛先ノードの識別子との対の全てを記録することを特徴とする請求項１３記載のデッドロック検出方法。
【請求項１】
２以上のポートを介して複数の他のノードと接続されるノードに適用され、前記ポートを介しての他のノードとの通信を制御するノードコントローラであって、
デッドロックが発生する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行するパケット発行手段と、
他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットを宛先ノードへ送信するための送出経路が、自ノードが既に発行したデッドロック検出用パケットの送出経路と同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出手段と、
前記他ノード宛のデッドロック検出用パケットを前記宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが前記宛先ノード以外に存在するか否かを所定のルーティング情報に従って判断し、前記宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対して前記パケット発行手段にデッドロック検出用パケットを発行させる対象ノード検出手段とを有することを特徴とするノードコントローラ。
【請求項２】
前記デッドロック検出手段は、宛先ノードへ送信するための送出経路が、外部に接続されるコントローラからの指示に応じて自ノードが既に発行したデッドロック検出用パケットの送出経路と同じである他ノード宛のデッドロック検出用パケットを受信した場合に、デッドロックが発生すると判断することを特徴とする請求項１記載のノードコントローラ。
【請求項３】
前記ルーティング情報は、前記各ノードの識別子と前記ポートの識別子とを対とするテーブルであることを特徴とする請求項１又は２記載のノードコントローラ。
【請求項４】
前記デッドロック検出用パケットは、ヘッダ部とデータ部とからなり、自パケットの発行要因となった全てのデッドロック検出用パケットの発行元ノードの識別子と宛先ノードの識別子との対が前記データ部に格納されていることを特徴とする請求項１から３のいずれか１項記載のノードコントローラ。
【請求項５】
前記各ポートを介した通信を管理する複数のノード間通信制御手段をさらに備え、
前記ノード間通信制御手段のそれぞれは、他のノード宛のデッドロック検出用パケットを自身が管理するポートを介して受信した場合に、該デッドロック検出用パケットのヘッダ部及びデータ部に格納されていた全ての宛先ノード及び発行元ノードの識別子を、前記対象ノード検出手段に通知するパケット検出手段を備え、
前記パケット発行手段は、外部に接続されるコントローラから又は対象ノード検出手段からの指示に応じて、指示されたノードに対して前記デッドロック検出用パケットを発行するとともに、前記コントローラから指示を受けた場合のみデッドロック検出手段に対して前記デッドロック検出用パケットの発行に用いるポートを表す送出先ポート情報を通知し、
前記対象ノード検出手段は、前記デッドロック検出用パケットのヘッダ部に識別子が格納されていたと前記パケット検出手段から通知されたノードと同じポートを送出先として使用するノードが存在するか否かを前記ルーティング情報に基づいて判断し、存在するならばそのノードへのデッドロック検出用パケットの発行を前記パケット発行手段に対して指示し、
前記デッドロック検出手段は、前記デッドロック検出用パケットのヘッダ部に識別子が格納されていたと前記パケット検出手段から通知されたノードとの通信に用いるポートを前記ルーティング情報に基づいて特定するとともに、前記パケット検出手段からの通知よりも前に前記パケット発行手段から送出先ポート情報が通知されている場合は、特定したポートが前記送出先ポート情報が示すポートと一致するか否かを判断し、一致する場合にはデッドロックが発生すると判断することを特徴とする請求項３記載のノードコントローラ。
【請求項６】
前記デッドロック検出手段がデッドロックが発生すると判断した場合に、判断に用いた前記他ノード宛のデッドロック検出用パケットに格納されている発行元ノードの識別子と宛先ノードの識別子との対の全てを記録することを特徴とする請求項４又は５記載のノードコントローラ。
【請求項７】
請求項１から６のいずれか１項記載のノードコントローラを有することを特徴とするノード。
【請求項８】
前記パケット発行手段に対し前記デッドロック検出用パケットの発行を指示するコントローラが接続されることを特徴とする請求項７記載のノード。
【請求項９】
請求項６記載のノードコントローラを有し、前記パケット発行手段に対して前記デッドロック検出用パケットの発行を指示するとともに、前記デッドロック検出手段によって記録された発行元ノードの識別子と宛先ノードの識別子との対を基に、デッドロックが発生する原因となる箇所を特定するコントローラが接続されることを特徴とするノード。
【請求項１０】
２以上のポートを介して複数の他のノードと接続され、前記ポートを介しての他のノードと通信するノードにおけるデッドロック検出方法であって、
デッドロックが発生する可能性があるか否かを検出するために用いるデッドロック検出用パケットを発行する第１のパケット発行工程と、
他ノード宛のデッドロック検出用パケットを受信した場合に、そのデッドロック検出用パケットの送出経路が、前記第１のパケット発行工程において発行したデッドロック検出用パケットと同じであるか否かを判断し、一致する場合にデッドロックが発生すると判断するデッドロック検出工程と、
前記他ノード宛のデッドロック検出用パケットを宛先ノードに送信するために用いるポートと同じポートを用いて通信するノードが前記宛先ノード以外に存在するか否かを所定のルーティング情報に従って判断する判断工程と、
前記宛先ノードと同じポートを用いて通信するノードが存在する場合に、該ノードに対して前記デッドロック検出用パケットを発行する第２のパケット発行工程とを有することを特徴とするデッドロック検出方法。
【請求項１１】
前記第１のパケット発行工程においては、自ノードの外部に接続されるコントローラからの指示に応じて前記デッドロック検出用パケットを発行することを特徴とする請求項１０記載のデッドロック検出方法。
【請求項１２】
前記第２のパケット発行工程においては、自パケットの発行要因となった全てのデッドロック検出用パケットの発行元ノードの識別子と宛先ノードの識別子との対を前記デッドロック検出用パケットに格納して発行することを特徴とする請求項１０又は１１記載のデッドロック検出方法。
【請求項１３】
前記デッドロック検出用パケットは、ヘッダ部とデータ部とからなり、自パケットの発行要因となった全てのデッドロック検出用パケットの発行元ノードの識別子と宛先ノードの識別子との対は、前記データ部に格納されていることを特徴とする請求項１２記載のデッドロック検出方法。
【請求項１４】
前記デッドロック検出工程においてデッドロックが発生すると判断した場合に、判断に用いた前記他ノード宛のデッドロック検出用パケットに格納されている発行元ノードの識別子と宛先ノードの識別子との対の全てを記録することを特徴とする請求項１３記載のデッドロック検出方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００９−８１７９７（Ｐ２００９−８１７９７Ａ）
【公開日】平成２１年４月１６日（２００９．４．１６）
【国際特許分類】
【出願番号】特願２００７−２５１０４４（Ｐ２００７−２５１０４４）
【出願日】平成１９年９月２７日（２００７．９．２７）
【出願人】（０００１６８２８５）エヌイーシーコンピュータテクノ株式会社 (572)
【Ｆターム（参考）】
【公開日】平成２１年４月１６日（２００９．４．１６）
【国際特許分類】
【出願日】平成１９年９月２７日（２００７．９．２７）
【出願人】（０００１６８２８５）エヌイーシーコンピュータテクノ株式会社 (572)
【Ｆターム（参考）】
[ Back to top ]