(57)【要約】【課題】リングバスを介して接続される複数の情報処理装置を有する情報処理システムにおいて、デッドロックの発生を防止する。【解決手段】リングバスを介して接続される複数の情報処理装置のある情報処理装置が、受信する他の情報処理装置への第１のリクエストを第１の保持部に保持し、第１の保持部に保持した第１のリクエストと、自身が発行する他の情報処理装置への第２のリクエストとを次段の情報処理装置へ順次送信し、第１の保持部におけるエントリの使用数が第１の閾値以上である状態が第１の時間より長く継続し、かつ次段の情報処理装置への第１のリクエスト及び第２のリクエストの送信が抑止された状態が第２の時間より長く継続した場合、第１の保持部が保持する第１のリクエストを、第１の保持部が出力した第１のリクエストを格納する記憶部に出力させるとともに、リングバスへの第２のリクエストの送信を抑止する。【選択図】図１
2019087046.tif 000002
【特許請求の範囲】
【請求項１】
環状のバスであるリングバスを介して接続される複数の情報処理装置を有する情報処理システムにおいて、
前記情報処理装置は、
前記リングバスを介して受信する、他の情報処理装置への第１のリクエストを保持する複数のエントリを有する第１の保持部と、
前記第１の保持部に保持した前記第１のリクエストと、自身が発行する他の情報処理装置への第２のリクエストとを次段の情報処理装置へ順次送信する送信部と、
前記第１の保持部が出力した前記第１のリクエストを格納する記憶部と、
前記第１の保持部における前記エントリの使用数が第１の閾値以上である状態が第１の時間より長く継続し、かつ次段の情報処理装置への前記第１のリクエスト及び前記第２のリクエストの送信が抑止された状態が第２の時間より長く継続した場合、前記第１の保持部が保持する前記第１のリクエストを前記記憶部に出力させるとともに、前記リングバスへの前記第２のリクエストの送信を抑止する制御部とを有することを特徴とする情報処理システム。
【請求項２】
前記制御部による制御に応じて、前記第１の保持部が保持する前記第１のリクエストを前記記憶部に出力するか、前記情報処理装置の外部に出力するかを切り替える切替部を有することを特徴とする請求項１記載の情報処理システム。
【請求項３】
前記制御部は、前記第１の保持部における前記エントリの使用数が第１の閾値以上である状態が第１の時間より長く継続し、かつ次段の情報処理装置への前記第１のリクエスト及び前記第２のリクエストの送信が抑止された状態が第２の時間より長く継続した場合、前記第１の保持部が保持する前記第１のリクエストの内の所定数の前記第１のリクエストを前記記憶部に出力させることを特徴とする請求項１又は２記載の情報処理システム。
【請求項４】
前記制御部は、前記第１の保持部における前記エントリの使用数が第１の閾値以上である状態が第１の時間より長く継続し、かつ次段の情報処理装置への前記第１のリクエスト及び前記第２のリクエストの送信が抑止された状態が第２の時間より長く継続した場合、前記第１のリクエストを前記情報処理装置の外部に出力するときに、デッドロック状態であるときに発行されたリクエストであることを示すフラグを設定することを特徴とする請求項１〜３の何れか１項に記載の情報処理システム。
【請求項５】
前記制御部は、前記第１の保持部における前記エントリの使用数が前記第１の閾値以上になった後、前記第１の閾値より小さい第２の閾値未満になるまで、前記リングバスへの前記第２のリクエストの送信を抑止することを特徴とする請求項１〜４の何れか１項に記載の情報処理システム。
【請求項６】
前記第２のリクエストを保持する複数のエントリを有する第２の保持部を有し、
前記制御部は、前記第２の保持部から前記送信部への前記第２のリクエストの送信を抑止することを特徴とする請求項１〜５の何れか１項に記載の情報処理システム。
【請求項７】
前記リングバスに接続された情報処理装置に接続される前記リングバスの外部の情報処理装置を有し、
前記外部の情報処理装置に接続される前記リングバスに接続された情報処理装置の制御部は、前記第１の保持部における前記エントリの使用数が第１の閾値以上である状態が第１の時間より長く継続し、かつ次段の情報処理装置への前記第１のリクエスト及び前記第２のリクエストの送信が抑止された状態が第２の時間より長く継続した場合、前記第２のリクエスト及び前記外部の情報処理装置から受信したリクエストの前記リングバスへの送信を抑止することを特徴とする請求項１〜６の何れか１項に記載の情報処理システム。
【請求項８】
環状のバスであるリングバスを介して他の情報処理装置に接続される情報処理装置において、
前記リングバスを介して受信する、他の情報処理装置への第１のリクエストを保持する複数のエントリを有する第１の保持部と、
前記第１の保持部に保持した前記第１のリクエストと、自身が発行する他の情報処理装置への第２のリクエストとを次段の情報処理装置へ順次送信する送信部と、
前記第１の保持部が出力した前記第１のリクエストを格納する記憶部と、
前記第１の保持部における前記エントリの使用数が第１の閾値以上である状態が第１の時間より長く継続し、かつ次段の情報処理装置への前記第１のリクエスト及び前記第２のリクエストの送信が抑止された状態が第２の時間より長く継続した場合、前記第１の保持部が保持する前記第１のリクエストを前記記憶部に出力させるとともに、前記リングバスへの前記第２のリクエストの送信を抑止する制御部とを有することを特徴とする情報処理装置。
【請求項９】
環状のバスであるリングバスを介して接続される複数の情報処理装置を有する情報処理システムの制御方法において、
前記複数の情報処理装置の内の第１の情報処理装置の第１の保持部が、前記リングバスを介して受信する、他の情報処理装置への第１のリクエストを保持し、
前記第１の情報処理装置の送信部が、前記第１の保持部に保持した前記第１のリクエストと、自身が発行する他の情報処理装置への第２のリクエストとを次段の情報処理装置へ順次送信し、
前記第１の情報処理装置の制御部が、前記第１の保持部におけるエントリの使用数が第１の閾値以上である状態が第１の時間より長く継続し、かつ次段の情報処理装置への前記第１のリクエスト及び前記第２のリクエストの送信が抑止された状態が第２の時間より長く継続した場合、前記第１の保持部が保持する前記第１のリクエストを、前記第１の保持部が出力した前記第１のリクエストを格納する記憶部に出力させるとともに、前記リングバスへの前記第２のリクエストの送信を抑止することを特徴とする情報処理システムの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム、情報処理装置、及び情報処理システムの制御方法に関する。
【背景技術】
【０００２】
図１１に、複数のノード（情報処理装置）１１０がリングバスＲＩＮＧを介して環状に接続された情報処理システムを示す。各ノード１１０は、ＣＰＵ（Central Processing Unit）１１１、メモリ１１２、メモリコントローラ１１３、及びクロスバ部（ＸＢ）１１４をそれぞれ有する。ＣＰＵ１１１は、演算処理を行うとともに、リクエストを発行する。メモリコントローラ１１３は、受信したリクエストに応じて、メモリ１１２へのデータの書き込み（データライト）やメモリ１１２からのデータの読み出し（データリード）を行う。クロスバ部（ＸＢ）１１４は、リングバスＲＩＮＧを介して伝送されるリクエスト等のパケットの宛先判定を行い、パケットの伝送制御を行う。
【０００３】
クロスバ部（ＸＢ）１１４同士が環状に接続されており、各ノード１１０は、リングバスＲＩＮＧを介して接続される任意のノードのメモリ１１２にアクセス可能である。各ノード１１０のクロスバ部（ＸＢ）１１４は、他ノード宛のリクエストを保持部であるキュー（バッファ）Ｑ１１、Ｑ１２に格納し、調停部１１５で調停を取って次段の他ノードに送信する。また、クロスバ部（ＸＢ）１１４は、自ノード宛のリクエストをキュー（バッファ）Ｑ２１、Ｑ２２に格納し、調停部１１６で調停を取ってメモリコントローラ１１３に送信する。このようにして各ノード１１０は、自ノード宛のリクエストを受け取って処理を行い、自ノード宛ではないリクエストを次段の他ノードに送信する。
【０００４】
ここで、図１１に示したようなリングバスＲＩＮＧを介して環状に接続される複数のノード１１０を有する情報処理システムでは、あるノードがビジー状態になり前段のノードからのリクエストの受信を抑止すると、前段のノードにリクエストが溜まっていき、最終的には最初にビジー状態となったノードの次段のノードもビジー状態となって、デッドロックが発生する。
【０００５】
例えば、図１１に示したノード（Ａ）１１０−Ａからノード（Ｃ）１１０−Ｃへのメモリアクセスリクエストにおいて、ノード（Ｃ）１１０−Ｃのメモリコントローラ１１３−Ｃの処理が遅く、ノード（Ｂ）１１０−Ｂがビジー状態になると、ノード（Ａ）１１０−Ａの他ノードからのリクエストも発行できなくなる。そして、ノード（Ａ）１１０−Ａがビジー状態になると、ノード（Ｄ）１１０−Ｄの他ノードからのリクエストも発行できなくなりビジー状態となってデッドロックが発生する。このようにリングバスＲＩＮＧを介して接続される複数のノード１１０を有する情報処理システムでは、あるノードがビジー状態になることによってデッドロックが発生してしまうことがある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−６７０２３号公報
【特許文献２】特開昭６４−２３３４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
１つの側面では、本発明の目的は、リングバスを介して接続される複数の情報処理装置を有する情報処理システムにおいて、デッドロックの発生を防止することにある。
【課題を解決するための手段】
【０００８】
情報処理システムの一態様は、環状のバスであるリングバスを介して接続される複数の情報処理装置を有し、情報処理装置は、リングバスを介して受信する、他の情報処理装置への第１のリクエストを保持する複数のエントリを有する第１の保持部と、第１の保持部に保持した第１のリクエストと、自身が発行する他の情報処理装置への第２のリクエストとを次段の情報処理装置へ順次送信する送信部と、第１の保持部が出力した第１のリクエストを格納する記憶部と、第１の保持部におけるエントリの使用数が第１の閾値以上である状態が第１の時間より長く継続し、かつ次段の情報処理装置への第１のリクエスト及び第２のリクエストの送信が抑止された状態が第２の時間より長く継続した場合、第１の保持部が保持する第１のリクエストを記憶部に出力させるとともに、リングバスへの第２のリクエストの送信を抑止する制御部とを有する。
【発明の効果】
【０００９】
発明の一態様においては、リングバスを介して接続される複数の情報処理装置を有する情報処理システムにおいて、デッドロックの発生を防止することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、第１の実施形態における情報処理システムの構成例を示す図である。
【図２】図２は、第１の実施形態におけるノードの構成例を示す図である。
【図３】図３は、第１の実施形態におけるデッドロック制御部の構成例を示す図である。
【図４】図４は、第１の実施形態におけるリクエストを説明する図である。
【図５】図５は、第１の実施形態におけるデッドロック制御の例を示すフローチャートである。
【図６】図６は、第１の実施形態におけるノードの動作例を示すフローチャートである。
【図７】図７は、第２の実施形態における情報処理システムの構成例を示す図である。
【図８】図８は、第２の実施形態におけるノードの構成例を示す図である。
【図９】図９は、第３の実施形態における情報処理システムの構成例を示す図である。
【図１０】図１０は、第３の実施形態におけるノードの構成例を示す図である。
【図１１】図１１は、情報処理システムの構成例を示す図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態を図面に基づいて説明する。
【００１２】
（第１の実施形態）
本発明の第１の実施形態について説明する。
図１は、第１の実施形態における情報処理システムの構成例を示す図である。第１の実施形態における情報処理システムは、複数のノードを環状に接続するリングバスＲＩＮＧを介して接続される複数の情報処理装置としてのノード１０を有する。図２にノード１０内部の構成例を示す。
【００１３】
本実施形態では、あるノード１０から発行されたリクエストは単方向（一方の方向のみ）に伝搬し、本例では、ノードＡ、Ｂ、Ｃ、Ｄ、Ａ、Ｂ、・・・の方向に伝搬するものとするが、逆であってもよい。なお、図１には、４つのノード１０−Ａ〜１０−ＤがリングバスＲＩＮＧを介して接続される構成を示しているが、これに限定されるものではなく、リングバスＲＩＮＧを介して接続されるノードの数は任意の複数である。
【００１４】
図２は、第１の実施形態におけるノード１０の構成例を示す図である。ノード１０は、ＣＰＵ（Central Processing Unit）１１、メモリ１２、メモリコントローラ１３、及びクロスバ部（ＸＢ）１４をそれぞれ有する。なお、図２において、説明の便宜上、ノード１０が有する機能部として、ＣＰＵ１１、メモリ１２、メモリコントローラ１３、及びクロスバ部（ＸＢ）１４を示したが、他の構成部を有していてもよい。
【００１５】
ＣＰＵ１１は、演算処理を行うとともに、リクエストを発行する。メモリコントローラ１３は、受信したリクエストに応じて、メモリ１２へのデータの書き込み（データライト）やメモリ１２からのデータの読み出し（データリード）を行う。クロスバ部（ＸＢ）１４は、リングバスＲＩＮＧを介して伝送されるリクエスト等のパケットの宛先判定を行い、パケットの伝送制御を行う。また、クロスバ部（ＸＢ）１４は、デッドロック状態の検出を行い、デッドロックが発生することを防止するための制御を行う。
【００１６】
クロスバ部（ＸＢ）１４は、それぞれ保持部に該当する４つのキュー（バッファ）Ｑ１１、Ｑ１２、Ｑ２１、Ｑ２２、調停部（セレクタ）１５、１６、デッドロック制御部１７、記憶部１８、切替部（セレクタ）１９、及び抑止部２０を有する。クロスバ部（ＸＢ）１４に入力されたリクエストＲＥＱＦ、ＲＥＱＮは、リクエスト内の宛先（発行先）情報に基づいてキュー（バッファ）Ｑ１１、Ｑ１２、Ｑ２１、Ｑ２２の何れかに格納される。キュー（バッファ）Ｑ１１、Ｑ１２、Ｑ２１、Ｑ２２は、それぞれ複数のエントリを有する。
【００１７】
第１の保持部としてのリモートキューＱ１１は、前段の（１つ前の）他ノードから受信するリクエストＲＥＱＦの内の他ノード宛のリクエストを保持するキューである。リモートキューＱ１１は、リクエストがエントリに書き込まれたときに信号Ｑ１１Ｗを出力（値“１”に）し、リクエストがエントリから読み出されたときに信号Ｑ１１Ｒを出力（値“１”に）する。
【００１８】
第２の保持部としてのローカルキューＱ１２は、自ノードのＣＰＵ１１が発行したリクエストＲＥＱＮの内の他ノード宛のリクエストを保持するキューである。リモートキューＱ１１及びローカルキューＱ１２に保持されたリクエストは、調停部１５での調停後、リクエストＲＥＱＳとして次段の（１つ後の）他ノードに送信される。なお、調停部１５は、次段の他ノードから入力されるビジー信号ＢＳＹＩが“１”である場合、次段の他ノードへのリクエストの送信を抑止する。
【００１９】
キューＱ２１は、前段の他ノードから受信するリクエストＲＥＱＦの内の自ノードのメモリ１２に対するリクエストを保持するキューである。キューＱ２２は、自ノードのＣＰＵ１１が発行したリクエストＲＥＱＮの内の自ノードのメモリ１２に対するリクエストを保持するキューである。キューＱ２１、Ｑ２２に保持されたリクエストは、調停部１６での調停後、メモリコントローラ１３に送信される。
【００２０】
デッドロック制御部１７は、次段の他ノードから入力されるビジー信号ＢＳＹＩ及びリモートキューＱ１１から出力される信号Ｑ１１Ｗ、Ｑ１１Ｒに基づいて、デッドロック状態であるか否かを判定する。デッドロック制御部１７は、デッドロック状態であると判定した場合、デッドロック解消モードへ遷移して、自ノードからのリクエストのリングバスへの新規発行を抑止する抑止信号ＱＡＳを出力（値“１”に）する。また、デッドロック制御部１７は、リモートキューＱ１１で使用しているエントリ数が閾値Ａに達した場合、前段の他ノードにビジー信号ＢＳＹＯを出力（値“１”に）する。
【００２１】
記憶部１８は、デッドロック状態であると判定した場合、リモートキューＱ１１が出力したリクエストを格納する。つまり、記憶部１８は、デッドロック状態であると判定された場合、リモートキューＱ１１が保持するリクエストを退避させることで、リモートキューＱ１１に空きエントリを設ける。切替部（セレクタ）１９は、デッドロック制御部１７からの出力制御信号ＱＣＳに応じて、リモートキューＱ１１が保持するリクエストを調停部１５又は記憶部１８に出力する。切替部（セレクタ）１９は、デッドロック状態であると判定された場合に出力制御信号ＱＣＳに応じて、リモートキューＱ１１に格納されているリクエストの内の所定数のリクエストを記憶部１８に出力し、それ以外の場合、出力制御信号ＱＣＳに応じてリモートキューＱ１１が保持するリクエストを調停部１５に出力する。
【００２２】
抑止部２０は、デッドロック制御部１７から出力される抑止信号ＱＡＳに応じて、ローカルキューＱ１２から調停部１５へのリクエストの転送を制御する。抑止部２０は、抑止信号ＱＡＳの値が“１”である場合、ローカルキューＱ１２から調停部１５へのリクエストの転送を抑止し、リングバスへの新規リクエストの発行を抑止する。
【００２３】
なお、図２においては、記憶部１８をクロスバ部（ＸＢ）１４の内部に有する構成を示したが、記憶部１８や切替部（セレクタ）１９は、各ノード１０において設ければよく、クロスバ部（ＸＢ）１４外に設けられていてもよい。また、記憶部１８の構成は任意であり、メモリ等であってもよいし、複数のレジスタ等であってもよい。
【００２４】
図３は、第１の実施形態におけるデッドロック制御部１７の構成例を示す図である。デッドロック制御部１７は、カウンタ３０１、３０２、３１１、論理和演算回路（ＯＲ回路）３０３、３０４、閾値保持回路３０５、３１２、３１３、比較回路３０６、３０７、３１４、３１５、論理積演算回路（ＡＮＤ回路）３０８、及びフラグ保持回路３０９を有する。
【００２５】
カウンタ３０１は、次段の他ノードからビジー信号ＢＳＹＩが出力されている（値が“１”である）期間をカウントしてカウント値ＣＮＴＡを出力する。また、カウンタ３０２は、自ノードからビジー信号ＢＳＹＯを出力している（値が“１”である）期間をカウントしてカウント値ＣＮＴＢを出力する。カウンタ３０１は、例えばビジー信号ＢＳＹＩが“１”である場合、図示しないクロック信号の１サイクル毎にカウント値ＣＮＴＡを１増加させ、ＯＲ回路３０３の出力が“１”となった場合、カウント値ＣＮＴＡを０にクリアする。また、カウンタ３０２は、例えばビジー信号ＢＳＹＯが“１”である場合、図示しないクロック信号の１サイクル毎にカウント値ＣＮＴＢを１増加させ、ＯＲ回路３０４の出力が“１”となった場合、カウント値ＣＮＴＢを０にクリアする。
【００２６】
ＯＲ回路３０３には、ビジー信号ＢＳＹＩの反転信号及びＡＮＤ回路３０８の出力が入力される。したがって、カウンタ３０１は、ビジー信号ＢＳＹＩが“０”である場合、又はＡＮＤ回路３０８の出力が“１”となった場合、カウント値ＣＮＴＡを０にクリアする。また、ＯＲ回路３０４には、ビジー信号ＢＳＹＯの反転信号及びＡＮＤ回路３０８の出力が入力される。したがって、カウンタ３０２は、ビジー信号ＢＳＹＯが“０”である場合、又はＡＮＤ回路３０８の出力が“１”となった場合、カウント値ＣＮＴＢを０にクリアする。
【００２７】
閾値保持回路３０５は、閾値Ｔを保持する。比較回路３０６は、カウンタ３０１から出力されるカウント値ＣＮＴＡと閾値保持回路３０５により保持される閾値Ｔとを比較して比較結果を出力する。比較回路３０６は、カウント値ＣＮＴＡが閾値Ｔより大きい場合、出力を“１”にし、カウント値ＣＮＴＡが閾値Ｔ以下である場合、出力を“０”にする。また、比較回路３０７は、カウンタ３０２から出力されるカウント値ＣＮＴＢと閾値保持回路３０５により保持される閾値Ｔとを比較して比較結果を出力する。比較回路３０７は、カウント値ＣＮＴＢが閾値Ｔより大きい場合、出力を“１”にし、カウント値ＣＮＴＢが閾値Ｔ以下である場合、出力を“０”にする。
【００２８】
ＡＮＤ回路３０８は、比較回路３０６、３０７の出力、及び抑止信号ＱＡＳの反転信号が入力され、その演算結果を出力する。すなわち、ＡＮＤ回路３０８は、カウント値ＣＮＴＡ、ＣＮＴＢがともに閾値Ｔより大きく、かつ抑止信号ＱＡＳが“０”である場合、出力を“１”にし、そうでない場合、出力を“０”にする。
【００２９】
フラグ保持回路３０９は、デッドロック解消モードであるか否かを示すフラグを保持するとともに、フラグに応じた抑止信号ＱＡＳを出力する。フラグ保持回路３０９は、ＡＮＤ回路３０８の出力が“１”になったとき、フラグを“１”（デッドロック解消モードである）に設定し、比較回路３１５の出力が“１”になったとき、フラグを“０”（デッドロック解消モードでない）に設定する。また、フラグ保持回路３０９は、フラグが“１”であれば出力する抑止信号ＱＡＳを“１”にし、フラグが“０”であれば出力する抑止信号ＱＡＳを“０”にする。
【００３０】
ここで、比較回路３１５の出力は、リモートキューＱ１１で使用しているエントリ数が閾値Ｂ未満であるときに“１”となる。したがって、フラグ保持回路３０９は、抑止信号ＱＡＳが“０”であって、かつカウント値ＣＮＴＡ、ＣＮＴＢがともに閾値Ｔより大きくなった場合、フラグを“１”に設定し、リモートキューＱ１１で使用しているエントリ数が閾値Ｂ未満になった場合、フラグを“０”に設定する。つまり、デッドロック解消モードでの動作時に、使用しているエントリ数が閾値Ｂ未満となると、デッドロック解消モードから通常モードに遷移する。
【００３１】
カウンタ３１１は、リモートキューＱ１１でのエントリの使用数をカウントしてカウント値ＣＮＴＣを出力する。カウンタ３１１は、リモートキューＱ１１からの信号Ｑ１１Ｗが“１”になるとカウント値ＣＮＴＣを１増加させ、リモートキューＱ１１からの信号Ｑ１１Ｒが“１”になるとカウント値ＣＮＴＣを１減少させる。閾値保持回路３１２は閾値Ａを保持し、閾値保持回路３１３は閾値Ｂを保持する。ここで、閾値ＡはリモートキューＱ１１のエントリ数であり、閾値Ｂはデッドロック解消モードから通常モードへ遷移する条件となるリモートキューＱ１１のエントリ数である。
【００３２】
比較回路３１４は、カウンタ３１１から出力されるカウント値ＣＮＴＣと、閾値保持回路３１２により保持される閾値Ａとを比較して、比較結果をビジー信号ＢＳＹＯとして出力する。すなわち、カウント値ＣＮＴＣと閾値Ａとの比較結果がビジー信号ＢＳＹＯとして出力される。比較回路３１４は、カウント値ＣＮＴＣが閾値Ａ以上である場合、出力（ビジー信号ＢＳＹＯ）を“１”にし、カウント値ＣＮＴＣが閾値Ａ未満である場合、出力（ビジー信号ＢＳＹＯ）を“０”にする。これにより、リモートキューＱ１１のエントリの使用数が閾値Ａになると前段の他ノードから自ノードへのリクエストの送信が抑止される。
【００３３】
比較回路３１５は、カウンタ３１１から出力されるカウント値ＣＮＴＣと、閾値保持回路３１３により保持される閾値Ｂとを比較して比較結果を出力する。比較回路３１５は、カウント値ＣＮＴＣが閾値Ｂ未満である場合、出力を“１”にし、カウント値ＣＮＴＣが閾値Ｂ以上である場合、出力を“０”にする。
【００３４】
図４に、第１の実施形態におけるリクエストの一例を示す。図４において、４１０はリクエストを含むパケットのヘッダ部であり、４２０はパケットのデータ部である。なお、リクエストを含むノード間で送受信されるパケットには、データ部４２０を有するものもあれば、データ部４２０を有しないものもある。データ部４２０を有するか否かは、データの有無を示すフィールド４１４に設定する値により示される。
【００３５】
ヘッダ部４１０は、パケットの宛先を示すディスティネーションフィールド４１１、命令の種別を示すフィールド４１２、パケットの送信元を示すソースフィールド４１３、データの有無を示すフィールド４１４、及びデータを有する場合にそのサイズを示すフィールド４１５を有する。
【００３６】
また、ヘッダ部４１０は、デッドロック解消モードの期間中に処理されたパケット、すなわちデッドロック状態であるときに発行されたリクエストであることを示すフラグ（ＦＬＧ）を設定するフィールド４１６をさらに有する。これにより、デッドロック解消モードの期間中に処理されたパケットにおいて、順序制御が必要なパケットであっても、適切な順序で処理されなかった可能性があることをノードに通知することが可能となる。なお、順序制御等が不要な情報処理システムにおいては、フィールド４１６を設けずに処理してもよい。
【００３７】
次に、図５を参照して第１の実施形態におけるデッドロック制御を説明する。図５は、第１の実施形態におけるデッドロック制御の例を示すフローチャートである。各ノード１０は、デッドロック制御部１７による制御に基づいて、図５に示す動作をそれぞれ実行する。
【００３８】
まず、ステップＳ５０１にて、デッドロック制御部１７は、デッドロック状態であるか否かの判定を行う。デッドロック制御部１７は、通常モードにおいて、カウンタ３０１、３０２のカウント値ＣＮＴＡ、ＣＮＴＢがともに閾値Ｔより大きい場合、デッドロック状態であると判定し、ステップＳ５０２へ進む。つまり、デッドロック制御部１７は、通常モードにおいて、ビジー信号ＢＳＹＩ、ＢＳＹＯが閾値Ｔよりも長く継続して出力されている場合、自ノード及び次段の他ノードのリモートキューＱ１１が詰まっているとしてデッドロック状態であると判定する。
【００３９】
次に、ステップＳ５０２にて、デッドロック制御部１７は、フラグ保持回路３０９により保持される、デッドロック解消モードであることを示すフラグを“１”に変更し、デッドロック解消モードへ遷移する。次に、ステップＳ５０３にて、デッドロック制御部１７は、フラグ保持回路３０９により保持されるフラグを“１”に変更したことに伴って、抑止信号ＱＡＳを“１”にして自ノードからリングバスへの新規リクエストの発行を抑止する。また、デッドロック制御部１７は、リモートキューＱ１１に係る制御を行い、出力制御信号ＱＣＳにより切替部（セレクタ）１９を制御して、リモートキューＱ１１に格納されているリクエストの内の所定数のリクエストを記憶部１８に退避させる。
【００４０】
また、ステップＳ５０４にて、デッドロック制御部１７は、記憶部１８にリクエストを退避させることによってリモートキューＱ１１におけるエントリの使用数が閾値Ａ未満になったことで、ビジー信号ＢＳＹＯを“０”にしてリングバスを介したリクエストの受け付け抑止状態を解除し、前段の他ノードからのリクエストを受け付ける。そして、ステップ５０５にて、デッドロック制御部１７は、リクエストが順次処理され、リモートキューＱ１１におけるエントリの使用数が閾値Ｂ未満になるまで待つ。リモートキューＱ１１におけるエントリの使用数が閾値Ｂ未満になると、ステップＳ５０６にて、デッドロック制御部１７は、ステップＳ５０３において記憶部１８に退避させたリクエストをリモートキューＱ１１に投入する。続いて、ステップＳ５０７にて、デッドロック制御部１７は、フラグ保持回路３０９により保持されるフラグを“０”に変更し、デッドロック解消モードから通常モードへ遷移する。
【００４１】
図６は、第１の実施形態におけるノードの動作例を示すフローチャートである。なお、図６においては、リングバスＲＩＮＧを介してリクエストを転送するときのノード１０の動作を示している。
【００４２】
ステップＳ６０１にて、ノード１０のクロスバ部（ＸＢ）１４は、前段の他ノードから自ノード宛ではないリクエストを受信すると、受信したリクエストをリモートキューＱ１１に格納する。このとき、リモートキューＱ１１から出力される信号Ｑ１１Ｗが“１”となり、デッドロック制御部１７が有するカウンタ３１１のカウント値ＣＮＴＣが１増加する。
【００４３】
次に、ステップＳ６０２にて、クロスバ部（ＸＢ）１４は、次段の他ノードから入力されるビジー信号ＢＳＹＩが“１”であるか否かを判定する。ビジー信号ＢＳＹＩが“１”ではないと判定した場合、ステップＳ６０３にて、クロスバ部（ＸＢ）１４は、リモートキューＱ１１が調停部１５での調停に勝利することで、リモートキューＱ１１に格納されているリクエストを次段の他ノードへ発行し、ステップＳ６０１へ戻る。このとき、リモートキューＱ１１から出力される信号Ｑ１１Ｒが“１”となり、デッドロック制御部１７が有するカウンタ３１１のカウント値ＣＮＴＣが１減少する。
【００４４】
一方、ステップＳ６０２での判定の結果、ビジー信号ＢＳＹＩが“１”であると判定した場合、ステップＳ６０４にて、デッドロック制御部１７は、リモートキューＱ１１におけるエントリの使用数が閾値Ａ以上であるか否かを判定する。その結果、リモートキューＱ１１におけるエントリの使用数が閾値Ａ以上である場合、ステップ６０５へ進み、そうでない場合、ステップＳ６０１へ戻る。
【００４５】
ステップＳ６０５にて、デッドロック制御部１７は、カウンタ３０１、３０２のカウント値ＣＮＴＡ、ＣＮＴＢがともに閾値Ｔより大きいか否かを判定する。すなわち、デッドロック制御部１７は、デッドロック状態であるか否かを判定する。その結果、カウンタ３０１、３０２のカウント値ＣＮＴＡ、ＣＮＴＢの少なくとも一方が閾値Ｔ以下である、すなわちデッドロック状態でないと判定した場合、ステップＳ６０２へ戻る。
【００４６】
一方、カウンタ３０１、３０２のカウント値ＣＮＴＡ、ＣＮＴＢがともに閾値Ｔより大きい、すなわちデッドロック状態であると判定した場合、ステップＳ６０６にて、デッドロック制御部１７は、フラグ保持回路３０９により保持される、デッドロック解消モードであることを示すフラグを“１”に変更する。これにより、デッドロック制御部１７は、デッドロック解消モードに遷移する。
【００４７】
次に、ステップＳ６０７にて、デッドロック制御部１７は、出力制御信号ＱＣＳにより切替部（セレクタ）１９を制御してリクエストの出力先を調停部１５から記憶部１８に切り替え、デッドロック状態であると判定されたリモートキューＱ１１から記憶部１８に所定数のリクエストを退避させる。つまり、デッドロック制御部１７は、リモートキューＱ１１に格納されているリクエストのうち、所定の数のリクエストをリモートキューＱ１１から記憶部１８に移して、リモートキューＱ１１に空きのエントリを設ける。
【００４８】
次に、ステップＳ６０８にて、クロスバ部（ＸＢ）１４は、次段の他ノードから入力されるビジー信号ＢＳＹＩが“１”であるか否かを判定する。ビジー信号ＢＳＹＩが“１”ではないと判定すると、ステップＳ６０９にて、クロスバ部（ＸＢ）１４は、リモートキューＱ１１が調停部１５での調停に勝利することで、リモートキューＱ１１に格納されているリクエストを次段の他ノードへ発行する。このとき、リモートキューＱ１１から出力される信号Ｑ１１Ｒが“１”となり、デッドロック制御部１７が有するカウンタ３１１のカウント値ＣＮＴＣが１減少する。また、ステップＳ６１０にて、クロスバ部（ＸＢ）１４は、発行するリクエストについて、パケットのフィールド４１６にフラグを設定し、デッドロック解消モード中に発行されたリクエストであることを示すようにしてリクエストを発行する。
【００４９】
続いて、ステップＳ６１１にて、デッドロック制御部１７は、リモートキューＱ１１におけるエントリの使用数が閾値Ｂ未満であるか否かを判定する。その結果、リモートキューＱ１１におけるエントリの使用数が閾値Ｂ未満でない場合、ステップＳ６０８へ戻り、エントリの使用数が閾値Ｂ未満である場合、ステップＳ６１２へ進む。ステップ６１２にて、クロスバ部（ＸＢ）１４は、記憶部１８に退避させたリクエストをリモートキューＱ１１に投入する。そして、ステップＳ６１３にて、デッドロック制御部１７は、フラグ保持部３０９により保持される、デッドロック解消モードであることを示すフラグを“０”に変更する。これにより、デッドロック制御部１７は、通常モードに遷移し、ステップＳ６０１へ戻る。
【００５０】
第１の実施形態によれば、デッドロック制御部１７が、デッドロック状態であると判定した場合、リングバスへの新規のリクエストの発行を抑止する。また、リモートキューＱ１１が保持するリクエストを記憶部１８に退避させることで、リモートキューＱ１１に空き領域を作成し、前段のノードからのリクエストを受信可能にする。これにより、各ノード１０のリモートキューＱ１１に格納されたリクエストを循環可能にし、デッドロック状態を解消してデッドロック状態の発生を抑止することができる。
【００５１】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。
図７は、第２の実施形態における情報処理システムの構成例を示す図である。第２の実施形態における情報処理システムは、第１の実施形態と同様に複数のノード（Ａ〜Ｄ）１０−Ａ〜１０−ＤがリングバスＲＩＮＧを介して環状に接続され、さらにノード（Ａ）１０−Ａに対してリングバスＲＩＮＧ外からリクエストを発行するノード（Ｅ）１０−Ｅが接続される。
【００５２】
第２の実施形態におけるノード（Ａ〜Ｅ）１０−Ａ〜１０−Ｅのうち、ノード（Ｂ〜Ｅ）１０−Ｂ〜１０−Ｅの構成は、図２に示した第１の実施形態におけるノード１０の構成と同様であるので説明は省略し、以下では第２の実施形態におけるノード（Ａ）１０−Ａについて説明する。図８は、第２の実施形態におけるノード（Ａ）１０−Ａの構成例を示す図である。図８において、図２に示した構成要素と同一の機能を有する構成要素には同一の符号を付し、重複する説明は省略する。
【００５３】
ノード１０−Ａは、ＣＰＵ１１、メモリ１２、メモリコントローラ１３、及びクロスバ部（ＸＢ）１４を有する。また、クロスバ部（ＸＢ）１４は、それぞれ保持部に該当する４つのキュー（バッファ）Ｑ１１、Ｑ１２、Ｑ２１、Ｑ２２、調停部（セレクタ）１５、１６、デッドロック制御部１７、記憶部１８、切替部（セレクタ）１９、及び抑止部２０に加え、さらに２つのキュー（バッファ）Ｑ１３、Ｑ２３及び抑止部２１を有する。キュー（バッファ）Ｑ１３、Ｑ２３もそれぞれ複数のエントリを有する。
【００５４】
キューＱ１３は、ノード（Ｅ）１０−Ｅから受信するリクエストＲＥＱＥの内の他ノード宛のリクエストを保持するキューである。キューＱ１１〜Ｑ１３に保持されたリクエストは、調停部１５での調停後、リクエストＲＥＱＳとして次段の他ノードに送信される。なお、調停部１５は、次段の他ノードから入力されるビジー信号ＢＳＹＩが“１”である場合、次段の他ノードへのリクエストの送信を抑止する。
【００５５】
また、キューＱ２３は、ノード（Ｅ）１０−Ｅから受信するリクエストＲＥＱＥの内の自ノードのメモリ１２に対するリクエストを保持するキューである。キューＱ２１〜Ｑ２３に保持されたリクエストは、調停部１６での調停後、メモリコントローラ１３に送信される。
【００５６】
抑止部２１は、デッドロック制御部１７から出力される抑止信号ＱＡＳに応じて、キューＱ１３から調停部１５へのリクエストの転送を制御する。抑止部２１は、抑止信号ＱＡＳの値が“１”である場合、ローカルキューＱ１３から調停部１５へのリクエストの転送を抑止し、リングバスへの新規リクエストの発行を抑止する。つまり、第２の実施形態では、抑止信号ＱＡＳの値が“１”である（デッドロック解消モードである）場合、キューＱ１２、Ｑ１３から調停部１５へのリクエストの転送を抑止し、リングバスへの新規リクエストの発行を抑止する。
【００５７】
第２の実施形態によれば、デッドロック状態と判定したときに、リングバスＲＩＮＧ外のノード（Ｅ）１０−ＥからリングバスＲＩＮＧに対して発行されるリクエストを、自身のＣＰＵ１１が発行するリクエストと同様にローカルのリクエストとして抑止することで、第１の実施形態と同様の効果が得られる。
【００５８】
（第３の実施形態）
次に、本発明の第３の実施形態について説明する。
図９は、第３の実施形態における情報処理システムの構成例を示す図である。第３の実施形態における情報処理システムは、ノード（Ａ〜Ｄ）１０−Ａ〜１０−ＤがリングバスＲＩＮＧ０を介して環状に接続され、さらにノード（Ａ、Ｅ〜Ｇ）１０−Ａ、１０−Ｅ〜１０−ＧがリングバスＲＩＮＧ０とは異なるリングバスＲＩＮＧ１を介して環状に接続される。
【００５９】
すなわち、第３の実施形態における情報処理システムでは、ノード（Ａ）１０−Ａは、２つのリングバスＲＩＮＧ０、ＲＩＮＧ１に接続されている。なお、図９において、破線で示すように、リングバスＲＩＮＧ０に接続されるノードからリングバスＲＩＮＧ１に接続されるノードへのリクエストも発行可能であり、リングバスＲＩＮＧ１に接続されるノードからリングバスＲＩＮＧ０に接続されるノードへのリクエストも発行可能である。
【００６０】
第３の実施形態におけるノード（Ａ〜Ｇ）１０−Ａ〜１０−Ｇのうち、ノード（Ｂ〜Ｇ）１０−Ｂ〜１０−Ｇの構成は、図２に示した第１の実施形態におけるノード１０の構成と同様であるので説明は省略し、以下では第３の実施形態におけるノード（Ａ）１０−Ａについて説明する。図１０は、第３の実施形態におけるノード（Ａ）１０−Ａの構成例を示す図である。図１０において、図２及び図８に示した構成要素と同一の機能を有する構成要素には同一の符号を付し、重複する説明は省略する。また、図１０において、添え字“０”を付加した構成要素は、リングバスＲＩＮＧ０に係る構成要素であることを示し、添え字“１”を付加した構成要素は、リングバスＲＩＮＧ１に係る構成要素であることを示す。
【００６１】
ノード１０−Ａは、ＣＰＵ１１、メモリ１２、メモリコントローラ１３、クロスバ部（ＸＢ）１４−０、１４−１、及び転送部３１−０、３１−１を有する。クロスバ部（ＸＢ）１４−０は、キュー（バッファ）Ｑ１３、Ｑ２３にかえてキュー（バッファ）Ｑ１４−０、Ｑ２４−０を有し、図８に示したノード１０−Ａのクロスバ部（ＸＢ）１４と同様に構成され、リングバスＲＩＮＧ０を介して転送されるリクエストを処理する。また、クロスバ部（ＸＢ）１４−１は、キュー（バッファ）Ｑ１３、Ｑ２３にかえてキュー（バッファ）Ｑ１４−１、Ｑ２４−１を有し、図８に示したノード１０−Ａのクロスバ部（ＸＢ）１４と同様に構成され、リングバスＲＩＮＧ１を介して転送されるリクエストを処理する。
【００６２】
転送部３１−０は、リングバスＲＩＮＧ０を介して入力されるリクエストＲＥＱＦ−０を、リクエスト内の宛先（発行先）情報に基づいてリングバスＲＩＮＧ０又はリングバスＲＩＮＧ１の一方に転送する。転送部３１−０は、入力されるリクエストＲＥＱＦ−０がリングバスＲＩＮＧ０に接続されたノード宛のリクエストである場合、リングバスＲＩＮＧ０上の他ノードから発行されたリクエストＲＥＱＦ−００としてクロスバ部（ＸＢ）１４−０に出力する。また、転送部３１−０は、入力されるリクエストＲＥＱＦ−０がリングバスＲＩＮＧ１に接続されたノード宛のリクエストである場合、リングバスＲＩＮＧ１外のノードからリングバスＲＩＮＧ１に対して発行されたリクエストＲＥＱＦ−０１としてクロスバ部（ＸＢ）１４−１に出力する。
【００６３】
同様に、転送部３１−１は、リングバスＲＩＮＧ１を介して入力されるリクエストＲＥＱＦ−１を、リクエスト内の宛先（発行先）情報に基づいてリングバスＲＩＮＧ０又はリングバスＲＩＮＧ１の一方に転送する。転送部３１−１は、入力されるリクエストＲＥＱＦ−１がリングバスＲＩＮＧ０に接続されたノード宛のリクエストである場合、リングバスＲＩＮＧ０外のノードからリングバスＲＩＮＧ０に対して発行されたリクエストＲＥＱＦ−１１としてクロスバ部（ＸＢ）１４−０に出力する。また、転送部３１−１は、入力されるリクエストＲＥＱＦ−１がリングバスＲＩＮＧ１に接続されたノード宛のリクエストである場合、リングバスＲＩＮＧ１上の他ノードから発行されたリクエストＲＥＱＦ−１０としてクロスバ部（ＸＢ）１４−１に出力する。
【００６４】
第３の実施形態によれば、デッドロック状態と判定した場合、他のリングバスから伝搬されるリクエストを、自身のＣＰＵ１１が発行するリクエストと同様にローカルのリクエストとして抑止する。また、第１の実施形態と同様にキューＱ１１に係る処理を行うことにより、リングバス上のキューＱ１１に格納された他ノードに対するリクエストを循環可能にし、デッドロック状態を解消してデッドロックの発生を防止することができる。
【００６５】
なお、前記実施形態は、何れも本発明を実施するにあたっての具体化のほんの一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００６６】
１０  ノード（情報処理装置）
１１  ＣＰＵ
１２  メモリ
１３  メモリコントローラ
１４  クロスバ部
１５、１６  調停部
１７  デッドロック制御部
１８  記憶部
１９  切替部
２０、２１、２２  抑止部
３１  転送部
Ｑ１１〜Ｑ１４、Ｑ２１〜Ｑ２４  キュー（バッファ）
３０１、３０２、３１１  カウンタ
３０３、３０４  論理和演算回路
３０５、３１２、３１３  閾値保持回路
３０６、３０７、３１４、３１５  比較回路
３０８  論理積演算回路
３０９  フラグ保持回路
【図１】
2019087046.tif 000003
【図２】
2019087046.tif 000004
【図３】
2019087046.tif 000005
【図４】
2019087046.tif 000006
【図５】
2019087046.tif 000007
【図６】
2019087046.tif 000008
【図７】
2019087046.tif 000009
【図８】
2019087046.tif 000010
【図９】
2019087046.tif 000011
【図１０】
2019087046.tif 000012
【図１１】
2019087046.tif 000013