(57)【要約】【課題】ＮｏＣにおいて経路の切り替えをすばやく行うことができる最適経路選択装置を提供する。【解決手段】バスマスター３００に含まれる最適経路選択装置であって、バスマスター３００からバスマスター４００までの複数の経路を示す経路情報を生成する経路情報生成部３０２と、前記各経路に少なくとも１つずつ定められるＮｏＣルータから、各ＮｏＣルータが中継する特定のフローの個数を異常生起確度値として収集し、収集した前記異常生起確度値を用いて各ＮｏＣルータにおける異常を予測する経路異常予測部３０３と、前記ＮｏＣルータの１つ以上において異常が予測された場合に、前記複数の経路の中から、前記異常が予測された前記ＮｏＣルータを含む経路を除外して、バスマスター３００からバスマスター４００までの新たな経路を選択する迂回経路選択部３０４とを備える。【選択図】図５
2010213183.tif 000002
【特許請求の範囲】
【請求項１】
複数のＮｏＣ（Network-on-Chip）ルータを介して送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択する最適経路選択装置であって、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成部と、
前記経路情報で示される各経路に少なくとも１つずつ定められる監視候補となるＮｏＣルータにおいて、同一の送信元から同一の宛て先へ伝送される１つ以上のフリットの列であるフローの個数を、各ＮｏＣルータにおける伝送品質の劣化および負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として収集し、収集した前記異常生起確度値を用いて各ＮｏＣルータにおける前記異常を予測する経路異常予測部と、
監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記異常が予測された前記ＮｏＣルータを含む経路を除外して、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択部と
を備える最適経路選択装置。
【請求項２】
前記経路異常予測部は、前記各ＮｏＣルータが中継するフローのうち、前記送信バスマスターから前記受信バスマスターへのフロー以外のフローの個数を、前記異常生起確度値として収集する
請求項１に記載の最適経路選択装置。
【請求項３】
前記経路異常予測部は、前記各ＮｏＣルータが中継するフローのうち、受信のためのネットワークの伝送帯域よりも、送信のためのネットワークの伝送帯域のほうが小さいフローの個数を、前記異常生起確度値として収集する
請求項１に記載の最適経路選択装置。
【請求項４】
前記経路異常予測部は、
前記監視候補としての前記各ＮｏＣルータの異常生起確度値を監視すべき頻度を表す監視頻度値を記憶している監視頻度値記憶部と、
前記各ＮｏＣルータについて所定の確率値である選択確率値を生成する選択確率値生成部と、
前記監視頻度値および前記選択確率値に従って、前記各ＮｏＣルータの中から異常生起確度値の監視の対象となるＮｏＣルータを選択する監視対象選択部と、
前記監視対象選択部によって選択されたＮｏＣルータから異常生起確度値を取得する異常生起確度値取得部と、
前記取得された異常生起確度値を記憶する異常生起確度値記憶部と、
前記記憶された異常生起確度値を用いて、前記監視頻度値記憶部に記憶されている前記監視頻度値の妥当性を表す活性度を算出する活性度算出部と、
前記活性度に基づき、前記監視頻度値記憶部に記憶されている前記監視頻度値を更新する監視頻度値更新部と
を有する請求項１に記載の最適経路選択装置。
【請求項５】
前記迂回経路選択部は、
前記監視候補としての前記各ＮｏＣルータについて、伝送品質を表す伝送品質値を決定し、
決定された前記伝送品質値によって表される伝送品質が予め定められた基準よりも悪いＮｏＣルータを含む経路をさらに除いた経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する
請求項１に記載の最適経路選択装置。
【請求項６】
前記迂回経路選択部は、
前記監視候補としての前記各ＮｏＣルータから、ＮｏＣルータにおける負荷の大きさを表す負荷値を収集し、
収集した前記負荷値によって表される負荷の大きさが予め定められた基準よりも小さいＮｏＣルータを含む経路をさらに除いた経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する
請求項５に記載の最適経路選択装置。
【請求項７】
前記迂回経路選択部は、
監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記異常が予測された各ＮｏＣルータの周囲で発生している異常の規模を示す異常発生規模情報を取得し、
取得された前記異常発生規模情報によって示される異常の規模が予め定められた基準よりも小さいＮｏＣルータを含む経路は、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき前記経路の選択対象から除外しない
請求項１に記載の最適経路選択装置。
【請求項８】
前記最適経路選択装置は、前記送信バスマスターか、または半導体システムを構成する前記複数のＮｏＣルータの１つに設けられる
請求項１に記載の最適経路選択装置。
【請求項９】
複数のＮｏＣルータを介して送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択する最適経路選択装置であって、
各ＮｏＣルータは、同一の送信元から同一の宛て先へ伝送される１つ以上のフリットの列であるフローの個数を、各ＮｏＣルータにおける伝送品質の劣化および負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として求め、前記異常生起確度値が予め定められた閾値を超えた場合に、前記最適経路選択装置に前記異常生起確度値を通知する経路異常検出部を備え、
前記最適経路選択装置は、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成部と、
前記ＮｏＣルータから送信される前記異常生成確度値を用いて、前記ＮｏＣルータにおける前記異常を予測し、前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記異常が予測された前記ＮｏＣルータを含む経路を除外して、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択部と
を備える最適経路選択装置。
【請求項１０】
複数のＮｏＣルータをネットワークで相互に接続してなる半導体システムにおいて、前記半導体システムに接続された送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択する最適経路選択方法であって、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成ステップと、
同一の送信元から同一の宛て先へ伝送される１つ以上のフリットの列を１つのフローと数えるとき、前記経路情報で示される各経路に少なくとも１つずつ定められる監視候補としてのＮｏＣルータから、各ＮｏＣルータが中継する特定のフローの個数を、各ＮｏＣルータにおける伝送品質の劣化または負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として収集し、収集した前記異常生起確度値を用いて各ＮｏＣルータにおける異常を予測する経路異常予測ステップと、
監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記異常が予測された前記ＮｏＣルータを含む経路を除外して、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択ステップと
を含む最適経路選択方法。
【請求項１１】
複数のＮｏＣルータをネットワークで相互に接続してなる半導体システムにおいて、前記半導体システムに接続された送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択するためのコンピュータ実行可能なプログラムであって、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成ステップと、
同一の送信元から同一の宛て先へ伝送される１つ以上のフリットの列を１つのフローと数えるとき、前記経路情報で示される各経路に少なくとも１つずつ定められる監視候補としてのＮｏＣルータから、各ＮｏＣルータが中継する特定のフローの個数を、各ＮｏＣルータにおける伝送品質の劣化または負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として収集し、収集した前記異常生起確度値を用いて各ＮｏＣルータにおける異常を予測する経路異常予測ステップと、
監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記異常が予測された前記ＮｏＣルータを含む経路を除外して、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択ステップと
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の伝送経路が利用可能な半導体システムのネットワークにおける最適経路選択装置、最適経路選択方法、およびプログラムに関する。
【背景技術】
【０００２】
従来から、半導体デバイスの大規模化のバス設計の難しさを、複数のプロセッサ間や、複数のバスマスター間を、ネットワーク技術を用いて解決するアプローチであるＮｏＣ（Network-on-Chip）の研究開発が行われている。従来からのクロスバースイッチにより、複数のプロセッサやバスマスターを集中管理的に制御するのではなく、ＮｏＣルータ（ルータ）を介して、複数のチップ間や、複数のバスマスター間を相互接続することで、バスをネットワーク化する。これにより、半導体システムでの機能の追加や削除が容易になり、トラヒックの分散化も可能になる。一方、制御も分散化されるため、制御が複雑化する。これに対し、トラヒック制御を自動的に最適化する仕組みを実現することで、バスの利用効率を最大限に高めることができ、これによりバスの動作クロックを下げ、不要な処理を減らすことで低消費電力化を図る。さらに、バスの利用効率を半導体デバイス自身が自律協調的に高めることで、半導体デバイス開発者の開発負担を低減することが可能となる。バスのトラヒック制御の難しさは、処理対象のコンテンツや、ユーザ操作、処理方式の切替えなどにより、トラヒックが変動することに起因する。トラヒック変動の難しさを回避するために、現行の半導体デバイスでは最悪値を想定する。このため、バスの利用効率が低くなり、半導体デバイスの低消費電力化を図りにくい。また、最悪値の見積もりも容易ではない。この課題は、バスが分散化したＮｏＣでは一層、深刻化する。本発明では、バスのトラヒック制御を自動的に最適化し、バスの動作クロックを下げ、不要な処理を減らす機能を新たに設けることで低消費電力化と半導体デバイス開発者の開発負担を低減する。バスの利用効率を高める方法として、バスの分散化により、目的のバスマスター（ＤＳＰ、プロセッサ、ＩＯ、メモリなど半導体デバイスの構成要素である）に対して複数経路ができる。本発明では、伝送品質の高いバスを選択し、経路を切替えることでトラヒック制御の最適化を図る方法を対象とする。
【０００３】
特許文献１では、現在、伝送中のエラーが発生時、エラーに対する応答がない場合に、予め設定された複数経路から、新たな経路を選択し、伝送を継続する技術を開示している。
【特許文献１】特許第３８１６５３１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の技術では、データの伝送に使用している経路に、伝送品質が劣化したこと、または、負荷が上昇するような異常が発生したことを、再送回数の情報を用いて事後に検出している。そのため、経路をすばやく切り替えることができないという第１の課題がある。
【０００５】
また、少ないリソース（例えば、通信量、消費電力、所要時間）で、かつ異常を適時に発見できる経路情報を収集するための好適な方法が開示されていないという第２の課題がある。
【０００６】
例えば、リソースを抑えるために所定のしきい値に達しない程度の異常を示す経路情報は収集しないという単純な方法では、しきい値に応じたリソースの抑制効果と異常を見逃す危険性とが相反する。そのため、好適なしきい値を見出せないことが多い。
【０００７】
本発明は、このような事情に鑑みてなされたものであり、ＮｏＣにおいて経路切り替えをすばやく行うことができる経路制御技術の提供を第１の目的とする。
【０００８】
また、経路情報の収集に必要なリソースを抑え、かつ起こり得る異常も見落としにくい経路制御技術の提供を第２の目的とする。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明のある局面に係る最適経路選択装置は、複数のＮｏＣ（Network-on-Chip）ルータを介して送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択する最適経路選択装置であって、前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成部と、前記経路情報で示される各経路に少なくとも１つずつ定められる監視候補となるＮｏＣルータにおいて、同一の送信元から同一の宛て先へ伝送される１つ以上のフリットの列であるフローの個数を、各ＮｏＣルータにおける伝送品質の劣化および負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として収集し、収集した前記異常生起確度値を用いて各ＮｏＣルータにおける前記異常を予測する経路異常予測部と、監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記異常が予測された前記ＮｏＣルータを含む経路を除外して、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択部とを備える。
【００１０】
また、前記経路異常予測部は、前記各ＮｏＣルータが中継するフローのうち、前記送信バスマスターから前記受信バスマスターへのフロー以外のフローの個数を、前記異常生起確度値として収集してもよい。
【００１１】
また、前記経路異常予測部は、前記各ＮｏＣルータが中継するフローのうち、受信のためのネットワークの伝送帯域よりも、送信のためのネットワークの伝送帯域のほうが小さいフローの個数を、前記異常生起確度値として収集してもよい。
【００１２】
また、前記経路異常予測部は、前記監視候補としての前記各ＮｏＣルータの異常生起確度値を監視すべき頻度を表す監視頻度値を記憶している監視頻度値記憶部と、前記各ＮｏＣルータについて所定の確率値である選択確率値を生成する選択確率値生成部と、前記監視頻度値および前記選択確率値に従って、前記各ＮｏＣルータの中から異常生起確度値の監視の対象となるＮｏＣルータを選択する監視対象選択部と、前記監視対象選択部によって選択されたＮｏＣルータから異常生起確度値を取得する異常生起確度値取得部と、前記取得された異常生起確度値を記憶する異常生起確度値記憶部と、前記記憶された異常生起確度値を用いて、前記監視頻度値記憶部に記憶されている前記監視頻度値の妥当性を表す活性度を算出する活性度算出部と、前記活性度に基づき、前記監視頻度値記憶部に記憶されている前記監視頻度値を更新する監視頻度値更新部とを有してもよい。
【００１３】
また、前記迂回経路選択部は、前記監視候補としての前記各ＮｏＣルータについて、伝送品質を表す伝送品質値を決定し、決定された前記伝送品質値によって表される伝送品質が予め定められた基準よりも悪いＮｏＣルータを含む経路をさらに除いた経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択してもよい。
【００１４】
また、前記迂回経路選択部は、前記監視候補としての前記各ＮｏＣルータから、ＮｏＣルータにおける負荷の大きさを表す負荷値を収集し、収集した前記負荷値によって表される負荷の大きさが予め定められた基準よりも小さいＮｏＣルータを含む経路をさらに除いた経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択してもよい。
【００１５】
また、前記迂回経路選択部は、監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記異常が予測された各ＮｏＣルータの周囲で発生している異常の規模を示す異常発生規模情報を取得し、取得された前記異常発生規模情報によって示される異常の規模が予め定められた基準よりも小さいＮｏＣルータを含む経路は、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき前記経路の選択対象から除外しなくてもよい。
【００１６】
また、前記最適経路選択装置は、前記送信バスマスターか、または半導体システムを構成する前記複数のＮｏＣルータの１つに設けられていてもよい。
【００１７】
本発明の他の局面に係る最適経路選択装置は、複数のＮｏＣルータを介して送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択する最適経路選択装置であって、各ＮｏＣルータは、同一の送信元から同一の宛て先へ伝送される１つ以上のフリットの列であるフローの個数を、各ＮｏＣルータにおける伝送品質の劣化および負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として求め、前記異常生起確度値が予め定められた閾値を超えた場合に、前記最適経路選択装置に前記異常生起確度値を通知する経路異常検出部を備え、前記最適経路選択装置は、前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成部と、前記ＮｏＣルータから送信される前記異常生成確度値を用いて、前記ＮｏＣルータにおける前記異常を予測し、前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記異常が予測された前記ＮｏＣルータを含む経路を除外して、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択部とを備える。
【００１８】
なお、本発明は、このような特徴的な処理部を備える最適経路選択装置として実現することができるだけでなく、最適経路選択装置に含まれる特徴的な処理部をステップとする最適経路選択方法として実現することができる。また、最適経路選択方法に含まれる特徴的なステップをコンピュータに実行させるプログラムとして実現することもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは、言うまでもない。
【発明の効果】
【００１９】
以上のように、本発明の最適経路選択装置によれば、特定のフローの個数を異常生起確度値として用いてＮｏＣルータの異常を予測し、異常が予測されたＮｏＣルータを含む経路を除外して、新たにデータの伝送に用いるべき経路を選択する。そのため、所定の統計量に反映されるような伝送品質の劣化や負荷の上昇が実際に生じる前に、すばやい迂回処理が可能になる。
【００２０】
また、異常の発生のしやすさに応じた監視頻度に従って確率的に選ばれたＮｏＣルータから異常生起確度値を収集して異常の予測に用いる。そのため、監視コスト（監視フリットの量、消費電力、観測所要時間）を抑え、かつ異常の見落としも確率的に回避可能になる。
【００２１】
さらに、トラヒック変動が頻繁に発生する場合、経路の切り替え処理が頻繁に発生するため、発明の効果は高くなり、特に、伝送品質が大きく改善される。
【発明を実施するための最良の形態】
【００２２】
本発明の実施の形態にかかる最適経路選択装置および最適経路選択方法について、図面を参照しながら説明する。
【００２３】
（経路制御の概要）
図１は、本発明の最適経路選択方法に従って伝送経路の制御が行われるＮｏＣの一例を模式的に示す図である。ＮｏＣの通信方式として、規定の時間長の伝送スロットを設け、伝送スロットに同期して対象情報を伝送してもよいし、非同期で対象情報を伝送してもよい。また、ＮｏＣルータではフリットの廃棄は発生せず、伝送が可能になるまでフリットは保持されるものとする。さらに、フロー制御を導入して、送信するフリット間隔を調整してもよい。なお、本発明では、伝送するデータの単位を、パケット又はフリットとよぶ。
【００２４】
図２には、一例として、映像符号化装置を、ＮｏＣで構成した場合の例を模式的に示している。チップ内には、複数のバスマスターがあり、バスマスター毎にＮｏＣルータと結合されている。バスマスターは、ＤＳＰ、プロセッサ、ＩＯ、メモリなど映像符号化処理を行うために必要となる機能要素である。ＮｏＣルータは、内部に行き先毎にメモリを備え、受信データを、対象となるメモリへ一時保存し、経路表に基づき、転送先のＮｏＣルータへフリットを転送する。ここでは、映像符号化のチップを例に説明したが、発明の用途はこの例に制限されず、ＳｏＣ（Ｓｙｓｔｅｍ  ｏｎ  Ｃｈｉｐ）全体をＮｏＣで構成する用途を想定してもよい。
【００２５】
図１には、一例として、複数のＮｏＣルータをネットワークで相互に接続してなるＮｏＣにおいて、送信バスマスターから受信バスマスターまでの３つの経路（１つの主経路および２つの迂回経路）が示されている。各経路には監視候補としてのＮｏＣルータが少なくとも１つずつ定められる。主経路は現用の経路を示し、迂回経路は待機中の経路を示す。
【００２６】
図１に示すＮｏＣにおいて、監視対象としてのＮｏＣルータに異常が起きると予測された場合に、前記複数の経路の中から、異常が予測されたＮｏＣルータを含む経路を除外して、送信バスマスターから受信バスマスターまでのデータの伝送に用いるべき新たな経路が選択される。典型的には、主経路上のＮｏＣルータに異常が予測された場合に、迂回経路の１つが新たな主経路として選択される。経路の選択基準については、後ほど詳しく説明する。
【００２７】
異常とは、ＮｏＣルータが望ましい通信状態から逸脱すること（例えば、伝送品質が劣化すること、および負荷が上昇することを含む）を言う。異常が発生しやすい状況を検出することを、異常を予測すると言う。
【００２８】
本発明では、異常を予測するために、従来の異常検出に用いられるリトライ回数、回線負荷値、トラヒック量などの、異常が実際に生じている事実を反映する統計量は用いていない。その代わりに、ＮｏＣルータによって中継される特定のフローの個数を、異常の発生のしやすさを表す異常生起確度値として用いる。フローとは、同一の送信元から同一の宛て先へ伝送される１つ以上のフリットの列を言う。どのようなフローの個数を異常生起確度値として数えるかは、後ほど詳しく説明する。
【００２９】
異常生起確度値は、監視候補の中から所定の監視頻度に従って監視対象に選ばれたＮｏＣルータから、周期的に収集される。この監視頻度は、既に収集されている異常生起確度値を用いて、異常が発生しやすいＮｏＣルータほど高い頻度で監視対象に選ばれ、かつ異常が発生しにくいＮｏＣルータも低い頻度で監視対象に選ばれるように定められる。監視対象になるべきＮｏＣルータは、この監視頻度に選択確率値を加えることで、確率的に選択される。
【００３０】
以上のように実行される経路制御によれば、特定のフローの個数を異常生起確度値として用いて異常を予測する。そのため、所定の統計量に反映されるような伝送品質の劣化や負荷の上昇が実際に生じる前に、主経路における異常を予測して迂回経路への切り替えを行うことができ、すばやい迂回処理が可能になる。
【００３１】
また、異常の発生のしやすさに応じた監視頻度に選択確率値を加えることで、確率的に選ばれたＮｏＣルータから異常生起確度値を収集して異常の予測に用いる。そのため、監視コスト（監視フリットの量、消費電力、観測所要時間）を抑え、かつ異常の見落としも確率的に回避できる。
【００３２】
（交差フロー数および伝送帯域ギャップ数の定義）
異常生起確度値の一例として、交差フロー数および伝送帯域ギャップ数を定義する。異常生起確度値は、前述したように、ＮｏＣルータが中継する特定のフローの個数であり、ＮｏＣルータにおける異常の発生のしやすさを表す。
【００３３】
まず、交差フロー数の定義について説明する。
【００３４】
図３（Ａ）〜図３（Ｄ）は、フローの交差について説明する図である。
【００３５】
フローとは、前述したように、同一の送信バスマスターから同一の受信バスマスターへ伝送される１つ以上のフリットの列を言う。つまり、同一の送信元アドレスおよびポート番号、ならびに、同一の宛て先アドレスおよびポート番号を持った１つ以上のフリットの列を１つのフローと数える。
【００３６】
ＮｏＣルータが複数のフローを中継する場合、ある１つのフローを着目するフローとする。これに対して、送信元アドレスおよびポート番号、ならびに、宛て先アドレスおよびポート番号のうちのいずれか１つでも着目するフローとは異なるフローを、着目するフローに対して交差するフローと定義する。
【００３７】
図３（Ａ）には、着目するフローとは送信元アドレスおよび宛て先アドレスのいずれもが異なる２本の交差するフローが模式的に示されている。なお、アドレスの違いは図中でＮｏＣルータからの方向の違いで表現される。
【００３８】
また、図３（Ｂ）には、着目するフローとは送信元アドレスおよび宛て先アドレスのいずれもが異なる３本の交差するフローが模式的に示されている。
【００３９】
また、図３（Ｃ）には、着目するフローとは送信元アドレスが同一でかつ宛て先アドレスが異なる２本の交差するフローが模式的に示されている。
【００４０】
また、図３（Ｄ）には、着目するフローに対して交差するフローが３パターンが模式的に図示されている。１つ目は、着目するフローとは送信元アドレスが異なりかつ宛て先アドレスが同一の交差するフローである。２つ目は、着目するフローとは送信元アドレスおよび宛て先アドレスが逆になっている交差するフローである。そして３つ目は、着目するフローとは送信元アドレスおよび宛て先アドレスが一致するが、送信元ポート番号および宛て先ポート番号の少なくともいずれか一方が異なる交差するフローである。
【００４１】
本発明では、送信バスマスターから受信バスマスターへ流れるフローを着目するフローとし、各ＮｏＣルータにおいて、着目するフローに対して交差するフローの個数を交差フロー数と定義する。
【００４２】
交差フロー数が多いほど、ＮｏＣルータで中継されるべきトラヒック量が多くなりやすく、かつトラヒック量の変化（例えば、コンテンツの変化、ユーザ操作、方式切替など）に対する安定性の余裕が小さくなりやすい。そのため、ＮｏＣルータで異常が発生しやすくなると判断する。
【００４３】
次に、伝送帯域ギャップ数の定義について説明する。
【００４４】
図４（Ａ）、図４（Ｂ）は、フローに発生する伝送帯域ギャップについて説明する図である。
【００４５】
ある種の半導体システムのバスは、省電力化のためにバスの動作クロックを段階的に変化させる。ＮｏＣルータが中継する１つのフローに関して、受信側と送信側のそれぞれのリンクの伝送帯域は、一般的には独立して変動する。また、一般にシステムＬＳＩでは様々な速度のバスをＮｏＣルータで収容するため、伝送帯域ギャップは設計時点から発生している。
【００４６】
図４（Ａ）には、受信側のリンクの伝送帯域よりも送信側のリンクの伝送帯域のほうが大きい場合が模式的に示されている。
【００４７】
図４（Ｂ）には、受信側のリンクの伝送帯域よりも送信側のリンクの伝送帯域のほうが小さい場合が模式的に示されている。
【００４８】
本発明では、フローの受信側のリンクの伝送帯域よりも当該フローの送信側のリンクの伝送帯域のほうが小さい場合を、伝送帯域ギャップが生じていると定義する。そして、ＮｏＣルータにおいて、伝送帯域ギャップが生じているフローの個数を伝送帯域ギャップ数と定義する。
【００４９】
伝送帯域ギャップ数が大きいほど、ＮｏＣルータ内のバッファで残留するフリットが多くなりやすいため、ＮｏＣルータで異常が発生しやすくなると判断する。
【００５０】
（最適経路選択装置を含む半導体システムの構成）
図５は、本実施の形態にかかる最適経路選択装置としてのバスマスター３００を含む半導体システム１００の構成の一例を示す図である。図５は、異常生起確度値をバスマスター３００からＮｏＣルータ２００に問い合わせる方式である。
【００５１】
図５に示すように、本実施の形態にかかる半導体システム１００は、バスマスター３００、バスマスター４００を含む複数のバスマスターと複数のＮｏＣルータ２００とがネットワークで接続されてなるＮｏＣである。バスマスター３００およびバスマスター４００は、それぞれ上述の送信バスマスターおよび受信バスマスターに対応する。ここで、一部または全てのバスマスターはＮｏＣルータとしての機能を含んでいてもよい。
【００５２】
半導体システム１００を、一般的な半導体システムとして考える場合、具体的に、バスマスター３００は、プロセッサや演算処理部に対応し、ＮｏＣルータ２００はルータやアービターに対応する。
【００５３】
また、半導体システム１００を、システムＬＳＩにおけるデータ伝送システムとして考えることもできる。その場合、具体的に、バスマスター３００は、ＣＰＵ、ＤＳＰ、メモリなどの機能ブロックに対応し、ＮｏＣルータ２００は、ルータ、アービターなどの機能ブロックに対応する。
【００５４】
図５において、ＮｏＣルータ２００は、フリット受信部２０６と、経路制御部２０７と、フリット送信部２０８と、異常生起確度値決定部２０９とを備える。
【００５５】
フリット受信部２０６は、フリットを受信し、経路制御部２０７は、受信したフリットの転送先を判定し、フリット送信部２０８は、決定された転送先へフリットを送信する。また、異常生起確度値決定部２０９は、交差フロー数および伝送帯域ギャップ数の一方または両方を異常生起確度値として決定する。
【００５６】
バスマスター３００は、データ送受信部３０１と、経路情報生成部３０２と、経路異常予測部３０３と、迂回経路選択部３０４と、通信部３０５とを備える。データ送受信部３０１は、データの送受信を行う。経路情報生成部３０２は、主経路と迂回経路とを示す経路情報を生成する。経路異常予測部３０３は、Ｃルータ２００から収集した異常生起確度値（交差フロー数および伝送帯域ギャップ数の一方または両方）を用いて、ＮｏＣルータの異常を予測する。迂回経路選択部３０４は、主経路上のＮｏＣルータに異常が予測されたときに迂回経路の１つを新たな主経路として選択する。通信部３０５は、通信制御を行う。
【００５７】
（最適経路選択装置を含む半導体システムの構成−２）
図６は、本実施の形態にかかる最適経路選択装置としてのバスマスター３２０を含む半導体システム１２０の構成の一例を示す図である。図６は、異常生起確度値をＮｏＣルータから自動的にバスマスターに通知する方式である。
【００５８】
図６に示すように、本実施の形態にかかる半導体システム１２０は、バスマスター３２０、バスマスター４００を含む複数のバスマスターと複数のＮｏＣルータ２２０がネットワークで接続されてなるＮｏＣである。バスマスター３２０およびバスマスター４００は、それぞれ上述の送信バスマスターおよび受信バスマスターに対応する。ここで、一部または全てのバスマスターはＮｏＣルータとしての機能を含んでいてもよい。
【００５９】
半導体システム１２０を、一般的な半導体システムとして考える場合、具体的に、バスマスター３２０は、プロセッサや演算処理部に対応し、ＮｏＣルータ２２０はルータやアービターに対応する。
【００６０】
また、半導体システム１２０を、システムＬＳＩにおけるデータ伝送システムとして考えることもできる。その場合、具体的に、バスマスター３２０は、ＣＰＵ、ＤＳＰ、メモリなどの機能ブロックに対応し、ＮｏＣルータ２２０は、ルータ、アービターなどの機能ブロックに対応する。
【００６１】
図６において、ＮｏＣルータ２２０は、受信部２０６と、経路制御部２０７と、フリット送信部２０８と、異常生起確度値決定部２２９とを備える。フリット受信部２０６は、フリットを受信し、経路制御部２０７は、受信したフリットの転送先を判定し、フリット送信部２０８は、決定された転送先へフリットを送信する。また、異常生起確度値決定部２２９は、交差フロー数および伝送帯域ギャップ数の一方または両方を異常生起確度値として決定する。異常生起確度値決定部２２９は、図５に示した異常生起確度値決定部２０９と異なり、異常生起確度値が予め定めた閾値を超えた場合、その異常生起確度値をバスマスター３２０へ通知する。
【００６２】
バスマスター３２０は、データ送受信部３０１と、経路情報生成部３０２と、迂回経路選択部３０４と、通信部３０５とを備える。データ送受信部３０１は、データの送受信を行い、経路情報生成部３０２は、主経路と迂回経路とを示す経路情報を生成する。また、迂回経路選択部３０４は、ＮｏＣルータ２２０から通知された異常生起確度値（交差フロー数および伝送帯域ギャップ数の一方または両方）を用いて、主経路上のＮｏＣルータに異常が起きると予測されたときに迂回経路の１つを新たな主経路として選択する。通信部３０５は、通信制御を行う。
【００６３】
以下では、ＮｏＣルータ２００（２２０）およびバスマスター３００（３２０）のそれぞれの動作の概要を、従来の技術に属する事項を含めて簡略に説明する。その後、ＮｏＣルータ２００（２２０）の特徴的な動作、およびバスマスター３００（３２０）の特徴的な構成と動作について詳細に説明する。
【００６４】
図７は、通信部３０５の構成について説明する図である。
【００６５】
通信部３０５は、バス受信処理部３３１と、フリット解釈部３３２と、コア送信処理部３３３と、コア受信処理部３３４と、フリット生成部３３５と、バス送信処理部３３６と、バスクロック制御部３３７とを含む。バス受信処理部３３１は、バスからのデータを受信し、フリット解釈部３３２は、受信したフリットの内容を解釈し、一連のデータを再構成し、コア送信処理部３３３は、データ列に再構成された時点でデータをバスマスターの各処理部に渡す。コア受信処理部３３４は、バスマスターの各処理部からのデータを受信する。フリット生成部３３５は、受信したデータ列をフリット単位に分割し、フリットを生成する。バス送信処理部３３６は、生成されたフリットをバスへ送出する。バスクロック制御部３３７は、フリットの長さやフリットを送信するタイミングの決定を行なう。バスクロック制御部３３７は、トラヒックに応じて、自動的にバスの動作クロックを制御することで、半導体システムの低消費電力化を図ってもよい。
【００６６】
（ＮｏＣルータの動作の概要）
ＮｏＣルータ２００（２２０）の動作の概要について説明する。
【００６７】
図８は、ＮｏＣルータ２００（２２０）の動作の一例を示すフローチャートである。
【００６８】
フリット受信部２０６は、ネットワークで接続されたＮｏＣルータまたはバスマスターからデータを受信する（Ｓ１０１）。
【００６９】
経路制御部２０７は、経路制御部２０７が管理する経路情報に基づき、フリットの行き先ごとの送信キューにフリットを格納する（Ｓ１０２）。
【００７０】
フリット送信部２０８は、各送信キューの残量に基づき、送信キューごとの送信間隔を制御し、フリットを送信する（Ｓ１０３）。
【００７１】
異常生起確度値決定部２０９（２２９）は、異常生起確度値としての交差フロー数および伝送帯域ギャップ数の一方または両方の最新値を、後ほど詳しく述べる手順に従って、周期的に決定する（Ｓ１０４）。
【００７２】
異常生起確度値をバスマスター３００からＮｏＣルータ２００に問い合わせる方式の構成の場合（図５に示すＮｏＣルータ２００の場合）、異常生起確度値決定部２０９は、バスマスター３００からの問合せに応じて、決定した異常生起確度値を通知する。異常生起確度値をＮｏＣルータ２００から自動的にバスマスター３００に通知する方式の構成の場合（図６に示すＮｏＣルータ２２０の場合）、異常生起確度値が閾値を越えたＮｏＣルータ２２０は、バスマスター３００へ、異常生起確度値と遅延時間、ジッターなどの伝送品質情報とを通知する（Ｓ１０５）。
【００７３】
（バスマスターの動作の概要）
最適経路選択装置としてのバスマスター３００の動作の概要について説明する。
【００７４】
図９は、バスマスター３００の動作の一例を示すフローチャートである。図９は、異常生起確度値をバスマスター３００からＮｏＣルータ２００に問い合わせる方式の半導体システム１００における、バスマスター３００の動作を示す。
【００７５】
経路情報生成部３０２は、主経路と迂回経路とを示す経路情報を生成し、主経路を示す経路情報を主経路上のＮｏＣルータ２００へ通知する（Ｓ２０１）。
【００７６】
データ送受信部３０１は、テキスト、映像、音声など様々な種類の情報を含むデータを、主経路を介して伝送する（Ｓ２０２）。
【００７７】
通信部３０５は、主経路および迂回経路のそれぞれにおける各ＮｏＣルータ２００から、各ＮｏＣルータ２００の異常生起確度値決定部２０９にて決定された異常生起確度値を収集する（Ｓ２０３）。
【００７８】
経路異常予測部３０３は、各ＮｏＣルータ２００から収集された異常生起確度値に従って異常が発生しやすいＮｏＣルータほど高い頻度で監視対象に選ぶための監視頻度値を決定する。そして、決定された監視頻度値を用いて監視対象になるべきＮｏＣルータを選択する（Ｓ２０４）。
【００７９】
経路異常予測部３０３は、通信部３０５を介して、監視対象に選ばれたＮｏＣルータから最新の異常生起確度値を収集する（Ｓ２０５）。
【００８０】
経路異常予測部３０３によるＮｏＣルータの選択および監視のための構成および処理については、後ほど詳細に説明する。
【００８１】
迂回経路選択部３０４は、監視対象に選ばれたＮｏＣルータ２００について、伝送品質を表す伝送品質値、および負荷の大きさを表す負荷値を取得する（Ｓ２０６）。
【００８２】
経路異常予測部３０３は、収集された異常生起確度値を用いて、ＮｏＣルータの異常を予測する（Ｓ２０７）。例えば、主経路上のＮｏＣルータ２００から、予め定められた良判定の上限値を超える異常生起確度値が取得された場合、経路異常予測部３０３は、主経路上のＮｏＣルータの異常が予測されたことを迂回経路選択部３０４へ通知する（Ｓ２０７でＹＥＳ）。
【００８３】
迂回経路選択部３０４は、前記通知を受けると（Ｓ２０７でＹＥＳ）、決定された伝送品質値によって表される伝送品質が予め定められた基準よりも悪いＮｏＣルータを含まない迂回経路を新たな主経路として選択する。この迂回路は、典型的には、決定された伝送品質値によって示される伝送品質が最も良い迂回経路である。そして、新たな主経路を示す経路情報を新たな主経路上のＮｏＣルータ２００へ通知することにより、新たな主経路を介してデータの伝送を行う（Ｓ２０８）。
【００８４】
迂回経路選択部３０４による迂回経路選択処理については、後ほど詳細に説明する。
【００８５】
（バスマスターの動作の概要−２）
最適経路選択装置としてのバスマスター３２０の動作の概要について説明する。
【００８６】
図１０は、バスマスター３２０の動作の一例を示すフローチャートである。図１０は、異常生起確度値を、ＮｏＣルータから自動的にバスマスター３２０に通知する方式の半導体システム１２０におけるバスマスター３２０の動作を示す。
【００８７】
経路情報生成部３０２は、主経路と迂回経路とを示す経路情報を生成し、主経路を示す経路情報を主経路上のＮｏＣルータ２００へ通知する（Ｓ２０１１）。
【００８８】
データ送受信部３０１は、テキスト、映像、音声など様々な種類の情報を含むデータを、主経路を介して伝送する（Ｓ２０２１）。
【００８９】
異常生起確度値決定部２２９から、通信部３０５を介して、ＮｏＣルータ２００からバスマスター３２０へ最新の異常生起確度値を送信する（Ｓ２０３１）。
【００９０】
バスマスター３２０は、受信した異常生起確度値が、予め決めた閾値を超えた場合（Ｓ２０４１でＹｅｓ）、閾値が超えてないＮｏＣルータ２００を含む経路を、選定し、新たな主経路とする（Ｓ２０５１）。閾値を超えていないＮｏＣルータ２００を含む経路が存在しない場合は（Ｓ２０４１でＮｏ）、現状の経路を維持する。
【００９１】
（交差フロー数、伝送帯域ギャップ数の決定処理の詳細）
異常生起確度値決定部２０９による交差フロー数および伝送帯域ギャップ数の決定処理（図８のＳ１０４）について、詳細に説明する。異常生起確度値決定部２２９も異常生起確度値決定部２０９と同様の処理を行なう。
【００９２】
まず、異常生起確度値決定部２０９が交差フロー数を決定し、決定された交差フロー数を異常生起確度値としてバスマスター３００へ通知する場合について説明する。
【００９３】
図１１（Ａ）は、ＮｏＣルータ２００で中継されるフローの一例を示す図である。図１１（Ａ）の例では、主経路上で伝送される着目するフロー１（アドレスＡからアドレスＢへのフリットの列）に対して、２つの交差するフロー２およびフロー３（アドレスＣからアドレスＤへのフリットの列）が示されている。
【００９４】
図１１（Ｂ）は、異常生起確度値決定部２０９に設けられるフロー情報テーブルの一例を示す図である。フロー情報テーブルには、ＮｏＣルータ２００が中継する個々のフローについてフロー情報が記録される。フロー情報は、フローを識別する識別番号、フローを構成するフリットの送信元アドレス、送信元ポート番号、宛て先アドレス、宛て先ポート番号、およびフローが最後に確認された時刻である更新時刻からなる。
【００９５】
図１１（Ｂ）に示されるフロー情報テーブルの内容例は、図１１（Ａ）に対応している。例えば、フロー１について、識別番号が１、送信元アドレスがＡ、送信元ポート番号が１０００、宛て先アドレスがＢ、宛て先ポート番号が２０００、更新時刻がＴ１であるフロー情報が記録されている。
【００９６】
図１２は、異常生起確度値決定部２０９によって実行される交差フロー数決定処理の一例を示すフローチャートである。交差フロー数決定処理は、例えば、ＮｏＣルータ２００が１つのフリットを中継するたびに実行される。
【００９７】
経路制御部２０７は、中継するフリットを解析することにより、フリットのヘッダーから送信元アドレスおよび宛て先アドレスを抽出し、フリットヘッダーから送信元ポート番号および宛て先ポート番号を抽出する（Ｓ３０１）。なお、フリット転送のルーティングの手法として、半導体システム１００内で、ＳｏＣルータ２００（２２０）間でのフリットの最短経路をＸ、Ｙ軸の順に求めることにより、フリット転送の最短経路を求める次元順ルーティングを想定する。
【００９８】
異常生起確度値決定部２０９は、送信元アドレス、宛て先アドレス、送信元ポート番号、および宛て先ポート番号の値が抽出されたそれぞれの値と一致するフロー情報をフロー情報テーブルから検索する。当該フロー情報がフロー情報テーブルに存在すれば、フロー情報テーブルにおける当該フロー情報の更新時刻を現在時刻に変更する。当該フロー情報がフロー情報テーブルに存在しなければ、当該フロー情報を、更新時刻を現在時刻として生成して、フロー情報テーブルへ追加する（Ｓ３０２）。
【００９９】
更新時刻と現在時刻との比較によって一定期間更新されていないことが示されるフロー情報を、フロー情報テーブルから削除する（Ｓ３０３）。
【０１００】
異常生起確度値決定部２０９は、バスマスター３００から異常生起確度値の問合せがあった場合に、フロー情報テーブルに記録されているフロー情報の個数から１減じた数である交差フロー数を異常生起確度値として、バスマスター３００へ通知する（Ｓ３０４）。なお、異常生起確度値決定部２２９の場合には、交差フロー数が所定の閾値を超えた場合に、その交差フロー数を異常生起確度値として、バスマスター３２０に通知する。
【０１０１】
次に、異常生起確度値決定部２０９が伝送帯域ギャップ数を決定し、決定された伝送帯域ギャップ数を異常生起確度値としてバスマスター３００へ通知する場合について説明する。
【０１０２】
図１３（Ａ）は、ＮｏＣルータ２００で生じている伝送帯域ギャップの一例を示す図である。図１３（Ａ）の例では、主経路上で伝送される着目するフロー１（アドレスＡからアドレスＢへのフリット列）に対して、２つの交差するフロー２およびフロー３（アドレスＣからアドレスＤへのフリット列）が示されている。
【０１０３】
フロー１について受信側の伝送帯域１０Ｍｂｐｓよりも送信側の伝送帯域５Ｍｂｐｓのほうが小さく、またフロー２およびフロー３について受信側の伝送帯域１０Ｍｂｐｓよりも送信側の伝送帯域８Ｍｂｐｓのほうが小さい。つまり、図１３（Ａ）の例では、フロー１、フロー２、およびフロー３の全てに伝送帯域ギャップが生じている。
【０１０４】
ここでは、このようなフローごとの受信側の伝送帯域を示す情報およびフローごとの送信側の伝送帯域を示す情報は、例えばフリット受信部２０６およびフリット送信部２０８でそれぞれ記録されているとする。
【０１０５】
図１３（Ｂ）は、異常生起確度値決定部２０９によって管理されるフロー情報テーブルの一例を示す図である。フロー情報テーブルには、ＮｏＣルータ２００において伝送帯域ギャップが生じている個々のフローについて、フロー情報が記録される。フロー情報は、フローを識別する識別番号、フローを構成するフリットの送信元アドレス、送信元ポート番号、宛て先アドレス、宛て先ポート番号、更新時刻からなる。
【０１０６】
図１３（Ｂ）に示されるフロー情報テーブルの内容例は、図１３（Ａ）に対応している。例えば、伝送帯域ギャップが生じている識別番号が１のフローについて、送信元アドレスとしてＡ、送信元ポート番号として１０００、宛て先アドレスとしてＢ、宛て先ポート番号として２０００、更新時刻（フロー情報が最後に確認された時刻）としてＴ１が記録されている。
【０１０７】
図１４は、異常生起確度値決定部２０９によって実行される伝送帯域ギャップ数決定処理の一例を示すフローチャートである。伝送帯域ギャップ数決定処理は、例えば、ＮｏＣルータ２００が１つのフリットを中継するたびに実行される。
【０１０８】
経路制御部２０７は、前述のステップＳ３０１と同様にして、中継するフリットから送信元アドレス、送信元ポート番号、宛て先アドレス、および宛て先ポート番号を抽出する（Ｓ４０１）。
【０１０９】
異常生起確度値決定部２０９は、中継するフローの受信側の伝送帯域を示す情報、および送信側の伝送帯域を示す情報を、それぞれフリット受信部２０６およびフリット送信部２０８から取得する。
【０１１０】
取得された情報によって中継するフローに伝送帯域ギャップが生じていると示される場合に、前述のステップＳ３０２と同様にして、中継するフローについてのフロー情報をフロー情報テーブルに追加するか、または当該フロー情報の更新時刻を変更する（Ｓ４０２）。
【０１１１】
異常生起確度値決定部２０９は、更新時刻と現在時刻との比較によって一定期間更新されていないことが示されるフロー情報を、フロー情報テーブルから削除する（Ｓ４０３）。
【０１１２】
異常生起確度値決定部２０９は、バスマスター３００から異常生起確度値の問合せがあった場合に、フロー情報テーブルに記録されているフロー情報の個数である伝送帯域ギャップ数を異常生起確度値として、バスマスター３００へ通知する（Ｓ４０４）。なお、異常生起確度値決定部２２９の場合には、伝送帯域ギャップ数が所定の閾値を超えた場合に、その伝送帯域ギャップ数を異常生起確度値として、バスマスター３２０に通知する。
【０１１３】
（経路異常予測部の構成の詳細）
経路異常予測部３０３の構成について、詳細に説明する。
【０１１４】
図１５は、経路異常予測部３０３の機能的な構成の一例を示すブロック図である。
【０１１５】
経路異常予測部３０３は、異常生起確度値取得部１０６、異常生起確度値記憶部１０７、活性度算出部１０９、監視頻度値更新部１１０、監視頻度値記憶部１１１、選択確率値生成部１１２、および監視対象選択部１１３から構成される。
【０１１６】
異常生起確度値取得部１０６は、監視対象選択部１１３によって監視対象に選ばれたＮｏＣルータから、異常生起確度値（前述の交差フロー数および伝送帯域ギャップ数）を取得する。
【０１１７】
異常生起確度値の取得は、監視対象のＮｏＣルータに対して問合せフリットを発行することによって行われる。異常生起確度値の収集は、一定周期で（例えば、現在時刻が計測予定時刻と一致または超過した時点で）行ってもよく、またその他の時間スケジューリングに従って行ってもよい。
【０１１８】
異常生起確度値取得部１０６は、主経路上のＮｏＣルータから異常生起確度値を取得した場合に、その異常生起確度値が予め定められた良判定の上限値を超えていれば、主経路において異常が発生しやすい状況になっていると判断する。そして、主経路において異常が予測されたことを迂回経路選択部３０４へ通知する。
【０１１９】
異常生起確度値記憶部１０７は、異常生起確度値取得部１０６で取得された異常生起確度値をＮｏＣルータごとに記憶する。
【０１２０】
活性度算出部１０９は、異常生起確度値記憶部１０７で記憶されている各ＮｏＣルータの異常生起確度値と、監視頻度値記憶部１１１で記憶されている各ＮｏＣルータの監視頻度値とから、異常生起確度値が大きいＮｏＣルータほど監視頻度値が高いという傾向の強さを表す活性度を算出する。
【０１２１】
監視頻度値更新部１１０は、算出された活性度に基づいて各ＮｏＣルータの新たな監視頻度値を算出し、監視頻度値記憶部１１１が記憶している監視頻度値を新たな監視頻度値で更新する。
【０１２２】
監視対象選択部１１３は、監視頻度値記憶部１１１で記憶されている各ＮｏＣルータの監視頻度値に、選択確率値生成部１１２が生成する選択確率値を加えることで、監視対象になるＮｏＣルータを確率的に選択する。
【０１２３】
監視対象に選ばれたＮｏＣルータは、異常生起確度値取得部１０６が次に異常生起確度値を取得する対象になるとともに、迂回経路選択部３０４へ通知され、迂回経路選択部３０４が伝送品質値および負荷値を決定する対象にもなる。
【０１２４】
これら一連の処理が繰り返し実行されることにより、各ＮｏＣルータを監視するための頻度に異常の起こりやすさに応じた重み付けを行いつつ、全てのＮｏＣルータへの監視を行き届かせることができる。
【０１２５】
（経路異常予測部におけるＮｏＣルータの選択および監視処理の詳細）
上述のように構成される経路異常予測部３０３におけるＮｏＣルータの選択および監視処理について、さらに詳細に説明する。
【０１２６】
まず、各ＮｏＣルータの監視精度の考え方について説明する。なお、ここでは、監視精度とは監視頻度の妥当性のことを意味する。
【０１２７】
図１６および図１７は、各ＮｏＣルータの監視頻度値と異常生起確度値の一例を示す図である。図１６および図１７の例では、送信バスマスターから受信バスマスターへの伝送経路として、実線で示される主経路と、点線で示される３つの迂回経路とが示されている。また、主経路および各迂回経路には、それぞれ１つのＮｏＣルータが監視候補として定められている。監視候補であるこれらの４つのＮｏＣルータから監視対象になるＮｏＣルータが確率的に選ばれ、異常生起確度値および伝送品質値が取得される。なお、図１６および図１７では、送信バスマスター、ＮｏＣルータ、受信バスマスターを模式的に示しており、実際の外観構成とは異なる。
【０１２８】
ここで、異常生起確度値は、前述の交差フロー数また伝送帯域ギャップ数である。ＮｏＣルータ４の異常生起確度値５０が、ＮｏＣルータ１〜ＮｏＣルータ３の異常生起確度値５の１０倍であることは、ＮｏＣルータ４では、ＮｏＣルータ１〜ＮｏＣルータ３に比べて異常が発生しやすいことを示している。
【０１２９】
また、監視頻度値は、監視対象として各ＮｏＣルータが選択される頻度を表す。例えば、ＮｏＣルータ１の監視頻度値が０．２であることは、ＮｏＣルータ１が、全ての監視回数のうち２０％の回数で監視されることを示している。
【０１３０】
異常が発生しやすいＮｏＣルータほど高い頻度で監視することは、限られた監視回数の中で異常を的確に予測する上で妥当である。
【０１３１】
しかしながら、図１６の例では、高頻度で監視されるＮｏＣルータはＮｏＣルータ３である。異常が発生しやすいと考えられるＮｏＣルータ４は、他の異常が発生しにくいと考えられるＮｏＣルータ１およびＮｏＣルータ２と同じ監視頻度値しか与えられていない。
【０１３２】
このように異常生起確度値が大きいＮｏＣルータほど監視頻度値が高いという傾向が弱い場合を、監視精度が低い状態であると定義する。
【０１３３】
これに対し、図１７の例では、他のＮｏＣルータに比べて異常生起確度値が大きいＮｏＣルータ４の監視頻度値が最も高く、その他の３つのＮｏＣルータの監視頻度値はいずれも低い。
【０１３４】
このように異常生起確度値が大きいＮｏＣルータほど監視頻度値が高いという傾向が強い場合を、監視精度が高い状態であると定義する。
【０１３５】
（異常生起確度値記憶部１０７）
異常生起確度値記憶部１０７は、異常生起確度値取得部１０６で取得された異常生起確度値を、異常生起確度値テーブルを用いて記憶する。
【０１３６】
図１８は、異常生起確度値テーブルのデータ構造の一例を示す図である。
【０１３７】
異常生起確度値テーブルにおいて、第１列に各ＮｏＣルータの識別番号、第２列に各ＮｏＣルータのアドレス、第３列に各ＮｏＣルータから取得された異常生起確度値（交差フロー数または伝送帯域ギャップ数）が記録される。
【０１３８】
（監視頻度値記憶部１１１）
監視頻度値記憶部１１１は、各ＮｏＣルータの監視頻度値を、監視頻度値テーブルを用いて記憶する。
【０１３９】
図１９は、監視頻度値テーブルのデータ構造の一例を示す図である。
【０１４０】
監視頻度値テーブルにおいて、第１列に各ＮｏＣルータの識別番号、第２列に各ＮｏＣルータのアドレス、第３列に各ＮｏＣルータの監視頻度値が記録される。
【０１４１】
（活性度算出部１０９）
活性度算出部１０９は、前述した監視精度の高さを表す活性度αを算出する。活性度αは、異常が発生しやすいＮｏＣルータほど高い頻度で監視されるという傾向の強さを数値化した指標であり、具体的には、異常生起確度値と監視頻度値との相関の大きさで与えられる。
【０１４２】
図２０は、活性度算出部１０９によって実行される処理の一例を示すフローチャートである。
【０１４３】
活性度算出部１０９は、異常生起確度値テーブルから各ＮｏＣルータの異常生起確度値ｌiを読み込み（Ｓ４０）、監視頻度値記憶部１１１の監視頻度値テーブルから各ＮｏＣルータの監視頻度値ｍiを読み込む（Ｓ４１）。そして、読み込んだ異常生起確度値と監視頻度値とを用いて、式１に従って活性度αの変化分を算出する（Ｓ４２〜Ｓ４４）。
【０１４４】
【数１】
2010213183.tif 000003
【０１４５】
式１は活性度αのダイナミクスの定義の一例である。ｎは監視候補であるＮｏＣルータの台数、ｌiは異常生起確度値テーブルに記録されているＮｏＣルータｉの異常生起確度値、ｍiは同ＮｏＣルータの監視頻度値、Ｎ、δはダイナミクスの変化速度を司る定数を表す。異常生起確度値と監視頻度値の積和演算の項は、これらの相関の大きさを示す。
【０１４６】
ｌiおよびｍiの上側に付くチルダーは、各値が正規化されていること、つまり、式２、式３の関係にあることを示している。
【０１４７】
【数２】
2010213183.tif 000004
【数３】
2010213183.tif 000005
【０１４８】
式１で算出された活性度αの変化分を用いて、式４に従って活性度αを更新する（Ｓ４５）。ここで、Δｔは更新周期によって決定される時間間隔である。
【０１４９】
【数４】
2010213183.tif 000006
【０１５０】
活性度αの変域を、扱い易さのために０から１の閉区間に制限する（Ｓ４６〜Ｓ４９）。この制限により、活性度αは０以上１以下の実数値になる。
【０１５１】
活性度αが０に近い状態は、監視精度が低い状態に対応し、活性度αが１に近い状態は、監視精度が高い状態に対応する。なぜなら、式４のダイナミクスに従えば、活性度αは、各ＮｏＣルータの監視頻度値が異常生起確度値から見て望ましい状態であるほど１に近づき、各ＮｏＣルータの監視頻度値が異常生起確度値と乖離しているほど０に近づく挙動を示すからである。
【０１５２】
（監視頻度値更新部１１０）
監視頻度値更新部１１０は、活性度算出部１０９によって決定された活性度αの値を基に、監視候補である各ＮｏＣルータに対する新たな監視頻度値ｍiを算出する。
【０１５３】
図２１は、監視頻度値更新部１１０によって実行される処理の一例を示すフローチャートである。
【０１５４】
監視頻度値更新部１１０は、活性度算出部１０９から決定された活性度αを読み込み（Ｓ５０）、監視頻度値記憶部１１１の監視頻度値テーブルから監視頻度値ｍiを読み込み（Ｓ５１）、監視頻度値の最大値ｍmaxを検索する（Ｓ５２）。読み込んだ活性度α、監視頻度値ｍi、および監視頻度値の最大値ｍmaxを用いて、各ＮｏＣルータの新たな監視頻度値を算出する（Ｓ５３〜Ｓ５６）。
【０１５５】
監視頻度値の算出について、さらに説明を続ける。
【０１５６】
式５は、監視頻度値ｍiのダイナミクスの定義の一例であり、式中のβ、γ、ψはダイナミクスの変化速度を司る定数である。
【０１５７】
【数５】
2010213183.tif 000007
【０１５８】
更新頻度値が最大になるＮｏＣルータに対するこの非線形常微分方程式の定常解は、式６のようになることが分かっている。
【０１５９】
【数６】
2010213183.tif 000008
【０１６０】
また、その他のＮｏＣルータに対する定常解は式７のようになる。
【０１６１】
【数７】
2010213183.tif 000009
【０１６２】
式５に従って監視頻度値ｍiの変化分を算出し、算出された監視頻度値ｍiの変化分を用いて、式８に従って監視頻度値を更新する。このとき、ΔＴは更新周期によって決定される時間間隔である。
【０１６３】
【数８】
2010213183.tif 000010
【０１６４】
監視頻度値更新部１１０は、監視候補である各ＮｏＣルータについて算出された新たな監視頻度値ｍiで、監視頻度値テーブルに記録されている監視頻度値を更新する。
【０１６５】
（選択確率値生成部１１２）
選択確率値生成部１１２は、監視対象選択部１１３で監視対象になるＮｏＣルータを確率的に選択する際に用いられる乱数である選択確率値を発生させる。選択確率値は乱数であることが望ましいが、比較的生成が容易な疑似乱数によって代用してもよい。またその場合に用いる確率分布としては、一般的な一様分布やガウス分布等でよい。
【０１６６】
選択確率値の変動範囲は、式６および式７から決定することができる。活性度αが０の場合を考えると、解間の距離Ｄは、式９で与えられる。
【０１６７】
【数９】
2010213183.tif 000011
【０１６８】
これより、選択確率値ηiを式１０のように決定する。
【０１６９】
【数１０】
2010213183.tif 000012
【０１７０】
Ｒａｎｄｏｍ関数は、規定された範囲内の実数乱数または疑似実数乱数を生成するものであり、κは零以上の値を取る調整係数である。κを大きくすることによって生成される選択確率値の振幅を大きくすることができる。
【０１７１】
（監視対象選択部１１３）
図２２は、監視対象選択部１１３によって実行される処理の一例を示すフローチャートである。
【０１７２】
監視対象選択部１１３は、監視頻度値記憶部１１１が管理する監視頻度値テーブルから各ＮｏＣルータの監視頻度値ｍiを読み出し、式１１により示すように選択確率値生成部１１２によって生成された対応するＮｏＣルータの選択確率値ηiと加算し、監視対象のＮｏＣルータを確率的に選択する（Ｓ６０〜Ｓ６４）。
【０１７３】
【数１１】
2010213183.tif 000013
【０１７４】
更新された各ＮｏＣルータの監視頻度値は確率値になるように式１２によって正規化される（Ｓ６５〜Ｓ６７）。
【０１７５】
【数１２】
2010213183.tif 000014
【０１７６】
図２３は、このようにして求められた正規化済監視頻度値を記録する正規化済監視頻度値テーブルのデータ構造の一例を示す図である。
【０１７７】
正規化済監視頻度値テーブルにおいて、第１列に各ＮｏＣルータの識別番号、第２列に各ＮｏＣルータのアドレス、第３列に式１２によって算出された正規化済監視頻度値が記録される。
【０１７８】
監視対象選択部１１３は、正規化済監視頻度値を各ＮｏＣルータのインデックスに対する確率分布として見ることにより、選択対象のＮｏＣルータのインデックスを確率変数とみなす。そして、この確率変数が取る値によって監視対象のＮｏＣルータを選択する。
【０１７９】
以上説明した動作によって、監視頻度値に従って選択されたＮｏＣルータを監視するため、経路上の全てのＮｏＣルータを常時監視する場合と比べて、監視処理に要するリソースが節約され、狭帯域網でも良好な監視処理が実行可能になる。
【０１８０】
また、リトライ回数、回線負荷値、トラヒック量などの、異常が実際に生じている事実を反映する統計量を参照して故障を検出する従来の方法に比して、そのような統計量に反映される異常が実際に生じる前に、早期に異常を予測することが可能になる。これは、本実施の形態に記載の発明が、ＮｏＣルータで中継される特定のフローの個数を故障生起確度値として用いて故障を予測しているためである。
【０１８１】
（迂回経路選択処理の詳細）
次に、迂回経路選択部３０４による迂回経路選択処理について、詳細に説明する。
【０１８２】
図２４は、迂回経路選択部３０４によって実行される処理の一例を示すフローチャートである。この処理は、例えば、経路異常予測部３０３から主経路において異常が予測されたことを示す通知を受信した場合に実行される。
【０１８３】
迂回経路選択部３０４は、この処理に先立って、経路異常予測部３０３で監視対象に選ばれたＮｏＣルータについて、伝送品質を表す伝送品質値（例えば、遅延時間、ジッター値など）を測定する。また、迂回経路選択部３０４は当該ＮｏＣルータにおける負荷の大きさを示す負荷値（例えば、バッファ使用率など）を当該ＮｏＣルータから取得し、図示しないテーブルを用いて、ＮｏＣルータごとに伝送品質値および負荷値を記憶している。
【０１８４】
迂回経路選択部３０４は、経路異常予測部３０３から主経路において異常が予測されたことを示す通知を受信すると、記憶されている伝送品質値と負荷値とを用いて、新たな主経路になるべき迂回経路を選択する。
【０１８５】
具体的には、次のような経路選択処理が実行される。
【０１８６】
迂回経路選択部３０４は、各迂回経路におけるＮｏＣルータについて記憶されている伝送品質値を参照し、伝送品質値によって示される最も伝送品質の良いＮｏＣルータを含む迂回経路を新たな主経路として選択する（Ｓ５０１）。伝送品質が良いＮｏＣルータとは、例えば、伝送遅延が最も低いルータが考えられる。
【０１８７】
ただし、最も良い伝送品質が所定の基準を満たさない場合は（Ｓ５０２でＮＯ）、各ＮｏＣルータについて記憶されている負荷値を参照し、負荷が低いＮｏＣルータを含む迂回経路を除外して新たな主経路を選びなおす（Ｓ５０３）。ここで、最も良い伝送品質が所定の基準を満たさない場合とは、例えば、最も伝送遅延が所定のしきい値以上である場合が考えられる。また、負荷が低いＮｏＣルータとは、例えば、バッファ使用率が所定のしきい値未満であるＮｏＣルータが考えられる。
【０１８８】
なお、上記では、遅延時間、ジッター値などの測定結果を伝送品質値として用いる例を説明したが、迂回経路選択部３０４は、これらの値を測定せず、前述の異常生起確度値の時間的な変化の大きさを、伝送品質値として用いてもよい。ここで異常生起確度値とは、交差フロー数および伝送帯域ギャップ数のことである。
【０１８９】
交差フロー数および伝送帯域ギャップ数が激しく変化するＮｏＣルータでは、伝送品質も大きく変化し、その結果、所望の伝送品質を安定して維持することが難しいと考えられるからである。異常生起確度値の時間的な変化の大きさは、例えば、１つのＮｏＣルータから所定の期間内に取得された複数の異常生起確度値の分散値で表すことができる。
【０１９０】
また、上記では、経路異常予測部３０３にて主経路における異常が予測された際に、迂回経路選択部３０４にて新たな主経路を１つ選択する例を説明したが、迂回経路選択部３０４が行うべき処理はこの例に限られない。
【０１９１】
例えば、送信バスマスターから受信バスマスターへのマルチパス伝送が行われる半導体システムでは、迂回経路選択部３０４は、マルチパスを構成する経路ごとに伝送するデータ量の割当てを行ってもよい。例えば、伝送品質が高い経路には伝送品質が低い経路に比べてより多くのデータ量を割当てる事が考えられる。また、経路ごとに伝送するデータの振分け（例えば、伝送品質が最も高い経路を用いて制御信号などの重要度の高いデータを伝送する）を行ってもよい。
【０１９２】
（適用例−１）
次に、本発明の最適経路選択方法の適用例について説明する。
【０１９３】
図２５は、本発明の最適経路選択方法が適用される半導体システムの具体的な構成の一例を示す模式図である。図２５では、異常生起確度値をバスマスター３００からＮｏＣルータ２００に問い合わせる方式を想定している。
【０１９４】
図２５の例では、送信バスマスターであるプロセッサから、受信バスマスターであるプロセッサまで、１つの主経路と２つの迂回経路とが示されている。また、監視候補であるＮｏＣルータが、各経路に１つずつ示されている。
【０１９５】
図２５の例では、監視候補である各ＮｏＣルータから収集された異常生起確度値によって異常が発生しやすいと示されるＮｏＣルータは、高頻度で監視対象に選ばれ、異常が発生しにくいと示されるＮｏＣルータも低頻度で監視対象に選ばれる。
【０１９６】
そして、監視対象に選ばれたＮｏＣルータについて、新たな異常生起確度値および伝送品質値が収集され、収集された異常生起確度値および伝送品質値を用いて、主経路における異常を予測し、新たな主経路になるべき迂回経路を選択する。これにより、異常を未然に回避することが試みられる。
【０１９７】
このような処理によって、異常が発生しやすいＮｏＣルータほど高い頻度で監視することは、限られた監視回数の中で異常を的確に予測する上で妥当である。
【０１９８】
したがって、監視回数を抑制し、かつ異常を的確に予測することができるため、迂回経路が増えた場合や、監視候補であるＮｏＣルータが数多くある場合でも、少ない量の観測フリットを用いてＮｏＣルータの状態を適正に把握することが可能となる。その結果、省電力化や、観測フリットによる半導体システムのバス負荷の軽減に貢献できる。
【０１９９】
なお、特定の条件下では、ＮｏＣルータからの異常生起確度値の収集および監視頻度値の更新を停止してもよい。例えば、伝送経路や伝送帯域を予約する通信方式の場合、通信が終了するまで、交差フロー数が変化しないため、ＮｏＣルータからの異常生起確度値の収集および監視頻度値の更新を停止し、監視対象とするＮｏＣルータを固定してもよい。
【０２００】
（適用例−２）
次に、本発明の最適経路選択方法の適用例について説明する。
【０２０１】
図２６は、本発明の最適経路選択方法が適用される半導体システムの具体的な構成の一例を示す模式図である。図２６では、異常生起確度値をＮｏＣルータから自動的にバスマスターに通知する方式を想定している。
【０２０２】
図２６の例では、送信バスマスターであるプロセッサから、受信バスマスターであるプロセッサまで、１つの主経路と２つの迂回経路とが示されている。また、予め定めた異常生起確度値の閾値を越えたＮｏＣルータが、各経路に１つずつ示されている。
【０２０３】
図２６の例では、異常生起確度値によって異常が発生しやすいと示されるＮｏＣルータは高頻度で異常生起確度値および伝送品質値をバスマスターに通知する。そして、異常が発生しにくいと示されるＮｏＣルータも低頻度で異常生起確度値および伝送品質値をバスマスターに通知する。
【０２０４】
そして、通知された異常生起確度値および伝送品質値を用いて、主経路における異常を予測し、新たな主経路になるべき迂回経路を選択することで、異常を未然に回避することが試みられる。
【０２０５】
このような処理によって、異常が発生しやすいＮｏＣルータほど高い頻度でＮｏＣルータの状態を通知することは、限られた監視回数の中で異常を的確に予測する上で妥当である。
【０２０６】
したがって、通知回数を抑制し、かつ異常を的確に予測することができるため、迂回経路が増えた場合や、ＮｏＣルータが数多くある場合でも、少ない量の観測フリットを用いてＮｏＣルータの状態を適正に把握することが可能となる。その結果、省電力化や、観測フリットによる半導体システムのバス負荷の軽減に貢献できる。
【０２０７】
（異常の規模に応じて経路制御を行う変形例）
次に、半導体システムにおける異常の規模に応じて経路制御を行う変形例について説明する。
【０２０８】
図２７は、半導体システムにおける異常の発生の仕方について説明する図である。
【０２０９】
異常の発生の仕方には、経路上のＮｏＣルータと隣接の多数のＮｏＣルータとで広域に異常が発生する場合（図２７（Ａ））と、経路上のＮｏＣルータのみで局所的に異常が発生する場合（図２７（Ｂ））とがある。異常が局所的である場合は短時間での回復を期待して迂回処理を行わず、異常が大規模である場合にのみ迂回処理を行うことで、頻繁な迂回処理による伝送性能の劣化を抑制することが可能になる。
【０２１０】
異常の規模に応じた経路制御を行う半導体システムについて、図２８および図２９を参照して詳細に説明する。
【０２１１】
図２８は、異常の規模を判定し、判定された異常の規模に応じて経路制御を行う半導体システム１０１の構成の一例を示すブロック図である。
【０２１２】
半導体システム１０１におけるＮｏＣルータ２１０は、図５の半導体システム１００におけるＮｏＣルータ２００と比べて、局所異常状態判定部２１１および広域異常状態判定部２１２が追加される。
【０２１３】
局所異常状態判定部２１１は、ＮｏＣルータ２１０における輻輳状態の程度を判定し、判定の結果を表す情報を保持している。輻輳状態の程度を表す情報は、例えばＮｏＣルータ２１０におけるバッファ使用率であり、遅延時間などの測定結果である。
【０２１４】
広域異常状態判定部２１２は、ＮｏＣルータ２１０から所定のホップ数までにある他のＮｏＣルータから輻輳状態の程度に関する情報を収集し、収集された情報を用いて輻輳状態が広域的に発生しているかを判定する。
【０２１５】
また、半導体システム１０１におけるバスマスター３１０は、図５の半導体システム１００におけるバスマスター３００と比べて、経路異常予測部３０３が経路異常予測部３１３に変更される。
【０２１６】
経路異常予測部３１３は、経路異常予測部３０３と比べて、異常生起確度値を用いて主経路における異常を予測する点で同様であるが、異常の規模を示す情報をＮｏＣルータから収集し、異常生起確度値と共に迂回の要否判断に用いる点で異なる。
【０２１７】
経路異常予測部３１３は、例えば、主経路上のＮｏＣルータから収集した異常生起確度値から異常が予測された場合、そのＮｏＣルータに対して問合せを行うことにより、異常の規模を示す情報を取得する。そして、取得された異常の規模を示す情報によって異常が小規模であることが示される場合には、迂回処理を抑止する。
【０２１８】
このように構成されるＮｏＣルータ２１０の動作について、前述のＮｏＣルータ２００の動作と異なる点について詳細に説明する。
【０２１９】
図２９は、ＮｏＣルータ２１０によって実行される、異常規模判定処理の一例を示すフローチャートである。なお、ＮｏＣルータ２１０は、上述のＮｏＣルータ２００による処理（図８を参照）と同様の処理を実行し、さらに図２９に示される処理を実行する。ＮｏＣルータ２００と同様の処理については、ここでは説明を繰り返さない。
【０２２０】
局所異常状態判定部２１１は、ＮｏＣルータ２１０における輻輳状態に関する情報として、例えば、フリット受信部２０６およびフリット送信部２０８におけるフリットの遅延時間などを測定する（Ｓ６０１）。
【０２２１】
広域異常状態判定部２１２は、ＮｏＣルータ２１０から所定のホップ数までにある他のＮｏＣルータで測定された輻輳状態に関する情報を収集する（Ｓ６０２）。
【０２２２】
具体的に、広域異常状態判定部２１２は、他のＮｏＣルータに対して問合せフリットを送ることで、他のＮｏＣルータから通知される情報を収集してもよい。
【０２２３】
広域異常状態判定部２１２は、収集された情報を用いて輻輳状態が広域に発生しているかを判定する（Ｓ６０３）。
【０２２４】
広域異常状態判定部２１２は、一例として、収集された情報によって、遅延時間の劣化（例えば、予め定められたしきい値の超過）が生じていると示されるＮｏＣルータの数を、単純に異常の規模として決定する。
【０２２５】
また、広域異常状態判定部２１２は、遅延時間の劣化が、ＮｏＣルータ２１０から何ホップ目にあるＮｏＣルータまで連続して発生しているかを特定し、特定されたホップ数を異常の規模として決定してもよい。
【０２２６】
さらに、広域異常状態判定部２１２は、収集された各ＮｏＣルータの遅延時間の劣化の度合いの合計を異常の強さと定義し、前述のホップ数と異常の強さの積を異常の規模として決定してもよい。収集された各ＮｏＣルータの遅延時間の劣化の度合いとして、例えば、予め定められたしきい値からの超過量が考えられる。
【０２２７】
広域異常状態判定部２１２は、バスマスター３１０からの問合せに応じて、異常の規模を示す情報を通知する（Ｓ６０４）。
【０２２８】
バスマスター３１０における経路異常予測部３１３は、上述のようにして通知される異常の規模を示す情報を、異常生起確度値とともに用いて迂回の要否判断を行う。
【０２２９】
例えば、主経路上のＮｏＣルータから通知される異常の規模を示す情報が、何ホップ目の距離にあるＮｏＣルータまで連続して輻輳状態が発生しているかを示す値であることを考える。このとき、前述の値が、異常が生じていないか、または生じているとしても主経路上のＮｏＣルータのみに限定されることを示す０である場合、経路異常予測部３１３は、短時間での回復を期待して、迂回経路選択部３０４に対して迂回処理を指示しない。
【０２３０】
他方、前述の値が、主経路上のＮｏＣルータの周囲で広域の異常が生じていることを示す１以上の値である場合、経路異常予測部３１３は、回復は難しいと判断して、迂回経路選択部３０４に対して迂回処理を指示する。
【０２３１】
なお、主経路上のＮｏＣルータから通知される異常の規模を示す情報は、迂回の要否判断に用いられるのみならず、新たな主経路になるべき迂回経路の選択に用いることもできる。
【０２３２】
具体的には、迂回経路選択部３０４は、例えば、主経路上のＮｏＣルータから通知される異常の規模を示す情報によって、主経路上のＮｏＣルータの周囲で広域の異常が生じていることが示される場合には、迂回経路の中で経路のホップ数が最も大きな１つを選択する。
【０２３３】
そのような迂回経路は主経路からの距離が離れている可能性が高いため、主経路上のＮｏＣルータの周囲で生じている異常の影響を受けにくい迂回経路が、新たな主経路として選択されやすくなる。
【０２３４】
以上説明したように、本発明の最適経路選択装置によれば、特定のフローの個数を異常生起確度値として用いてＮｏＣルータの異常を予測し、異常が予測されたＮｏＣルータを含む経路を除外して、新たにデータの伝送に用いるべき経路を選択する。そのため、所定の統計量に反映されるような伝送品質の劣化や負荷の上昇が実際に生じる前に、すばやい迂回処理が可能になる。
【０２３５】
また、異常の発生のしやすさに応じた監視頻度に従って確率的に選ばれたＮｏＣルータから異常生起確度値を収集して異常の予測に用いるので、監視コスト（監視フリットの量、消費電力、観測所要時間）を抑え、かつ異常の見落としも確率的に回避できる。
【０２３６】
以上、本発明の実施の形態に係る最適経路選択装置および最適経路選択方法について説明したが、本発明は、この実施の形態に限定されるものではない。
【０２３７】
例えば、上記の各装置を構成する構成要素の一部または全部は、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムであってもよい。ＲＡＭには、コンピュータプログラムが記憶されている。マイクロプロセッサが、コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。
【０２３８】
また、本発明は、マイクロプロセッサとメモリを備えたコンピュータシステムであって、上記メモリは、上記コンピュータプログラムを記憶しており、上記マイクロプロセッサは、上記コンピュータプログラムに従って動作するとしても良い。
【０２３９】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【０２４０】
本発明にかかる最適経路選択装置は、システムＬＳＩ上のネットワーク伝送システム等に利用できる。
【図面の簡単な説明】
【０２４１】
【図１】本発明の最適経路選択方法に従って伝送経路の制御が行われるＮｏＣの一例を模式的に示す図である。
【図２】ＮｏＣにより構成された映像符号化装置の一例を示す図である。
【図３】（Ａ）〜（Ｄ）フローの交差について説明する図である。
【図４】（Ａ）、（Ｂ）フローに発生する伝送帯域ギャップについて説明する図である。
【図５】本発明の実施の形態にかかる半導体システムの構成の一例を示す図である。
【図６】本発明の実施の形態にかかる半導体システムの構成の別の一例を示す図である。
【図７】通信部の構成の一例を示す図である。
【図８】ＮｏＣルータの動作の一例を示すフローチャートである。
【図９】バスマスターの動作の一例を示すフローチャートである。
【図１０】バスマスターの動作の別の一例を示すフローチャートである。
【図１１】（Ａ）ＮｏＣルータで中継されるフローの一例を示す図である。（Ｂ）フロー情報テーブルの一例を示す図である。
【図１２】交差フロー数決定処理の一例を示すフローチャートである。
【図１３】（Ａ）ＮｏＣルータ２００で生じている伝送帯域ギャップの一例を示す図である。（Ｂ）フロー情報テーブルの一例を示す図である。
【図１４】伝送帯域ギャップ数決定処理の一例を示すフローチャートである。
【図１５】経路異常予測部の機能的な構成の一例を示すブロック図である。
【図１６】各ＮｏＣルータの監視頻度値と異常生起確度値の一例を示す図である。
【図１７】各ＮｏＣルータの監視頻度値と異常生起確度値の一例を示す図である。
【図１８】異常生起確度値テーブルのデータ構造の一例を示す図である。
【図１９】監視頻度値テーブルのデータ構造の一例を示す図である。
【図２０】活性度算出部によって実行される処理の一例を示すフローチャートである。
【図２１】監視頻度値更新部によって実行される処理の一例を示すフローチャートである。
【図２２】監視対象選択部によって実行される処理の一例を示すフローチャートである。
【図２３】正規化済監視頻度値テーブルのデータ構造の一例を示す図である。
【図２４】迂回経路選択処理の一例を示すフローチャートである。
【図２５】本発明の最適経路選択方法が適用される半導体システムの具体的な構成の一例を示す模式図である。
【図２６】本発明の最適経路選択方法が適用される半導体システムの具体的な構成の別の一例を示す模式図である。
【図２７】半導体システムにおける異常の発生の仕方について説明する図である。
【図２８】本発明の変形例にかかる半導体システムの構成の一例を示す図である。
【図２９】異常の規模を判定する処理の一例を示すフローチャートである。
【符号の説明】
【０２４２】
１００、１０１  半導体システム
１０６    異常生起確度値取得部
１０７    異常生起確度値記憶部
１０９    活性度算出部
１１０    監視頻度値更新部
１１１    監視頻度値記憶部
１１２    選択確率値生成部
１１３    監視対象選択部
２００、２１０、２２０  ＮｏＣルータ
２０６    フリット受信部
２０７    経路制御部
２０８    フリット送信部
２０９、２２９    異常生起確度値決定部
２１１    局所異常状態判定部
２１２    広域異常状態判定部
３００、３１０、３２０、４００  バスマスター
３０１    データ送受信部
３０２    経路情報生成部
３０３    経路異常予測部
３０４    迂回経路選択部
３０５    通信部
３１３    経路異常予測部
３３１    バス受信処理部
３３２    フリット解釈部
３３３    コア送信処理部
３３４    コア受信処理部
３３５    フリット生成部
３３６    バス送信処理部
３３７    バスクロック制御部
【図１】
2010213183.tif 000015
【図２】
2010213183.tif 000016
【図３】
2010213183.tif 000017
【図４】
2010213183.tif 000018
【図５】
2010213183.tif 000019
【図６】
2010213183.tif 000020
【図７】
2010213183.tif 000021
【図８】
2010213183.tif 000022
【図９】
2010213183.tif 000023
【図１０】
2010213183.tif 000024
【図１１】
2010213183.tif 000025
【図１２】
2010213183.tif 000026
【図１３】
2010213183.tif 000027
【図１４】
2010213183.tif 000028
【図１５】
2010213183.tif 000029
【図１６】
2010213183.tif 000030
【図１７】
2010213183.tif 000031
【図１８】
2010213183.tif 000032
【図１９】
2010213183.tif 000033
【図２０】
2010213183.tif 000034
【図２１】
2010213183.tif 000035
【図２２】
2010213183.tif 000036
【図２３】
2010213183.tif 000037
【図２４】
2010213183.tif 000038
【図２５】
2010213183.tif 000039
【図２６】
2010213183.tif 000040
【図２７】
2010213183.tif 000041
【図２８】
2010213183.tif 000042
【図２９】
2010213183.tif 000043
【手続補正書】
【提出日】平成22年7月12日(2010.7.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のＮｏＣ（Network-on-Chip）ルータを介して送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択する経路選択装置であって、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成部と、
前記経路情報で示される各経路に少なくとも１つずつ定められる監視候補となるＮｏＣルータにおいて、所定の送信元から所定の宛て先へ伝送される１つ以上のフリットの列であるフローの個数を、各ＮｏＣルータにおける伝送品質の劣化および負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として収集し、収集した前記異常生起確度値を用いて各ＮｏＣルータにおける前記異常を予測する経路異常予測部と、
監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択部と
を備える経路選択装置。
【請求項２】
前記経路異常予測部は、前記各ＮｏＣルータが中継するフローのうち、前記送信バスマスターから前記受信バスマスターへのフロー以外のフローの個数を、前記異常生起確度値として収集する
請求項１に記載の経路選択装置。
【請求項３】
前記経路異常予測部は、前記各ＮｏＣルータが中継するフローのうち、受信のためのネットワークの伝送帯域よりも、送信のためのネットワークの伝送帯域のほうが小さいフローの個数を、前記異常生起確度値として収集する
請求項１に記載の経路選択装置。
【請求項４】
前記経路異常予測部は、
前記監視候補としての前記各ＮｏＣルータの異常生起確度値を監視すべき頻度を表す監視頻度値を記憶している監視頻度値記憶部と、
前記各ＮｏＣルータについて所定の確率値である選択確率値を生成する選択確率値生成部と、
前記監視頻度値および前記選択確率値に従って、前記各ＮｏＣルータの中から異常生起確度値の監視の対象となるＮｏＣルータを選択する監視対象選択部と、
前記監視対象選択部によって選択されたＮｏＣルータから異常生起確度値を取得する異常生起確度値取得部と、
前記取得された異常生起確度値を記憶する異常生起確度値記憶部と、
前記記憶された異常生起確度値を用いて、前記監視頻度値記憶部に記憶されている前記監視頻度値の妥当性を表す活性度を算出する活性度算出部と、
前記活性度に基づき、前記監視頻度値記憶部に記憶されている前記監視頻度値を更新する監視頻度値更新部と
を有する請求項１に記載の経路選択装置。
【請求項５】
前記迂回経路選択部は、
前記監視候補としての前記各ＮｏＣルータについて、伝送品質を表す伝送品質値を決定し、
決定された前記伝送品質値によって表される伝送品質が予め定められた基準よりも悪いＮｏＣルータを含む経路をさらに除いた経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する
請求項１に記載の経路選択装置。
【請求項６】
前記迂回経路選択部は、
前記監視候補としての前記各ＮｏＣルータから、ＮｏＣルータにおける負荷の大きさを表す負荷値を収集し、
収集した前記負荷値によって表される負荷の大きさが予め定められた基準よりも小さいＮｏＣルータを含む経路をさらに除いた経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する
請求項５に記載の経路選択装置。
【請求項７】
前記迂回経路選択部は、
監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記異常が予測された各ＮｏＣルータの周囲で発生している異常の規模を示す異常発生規模情報を取得し、
取得された前記異常発生規模情報によって示される異常の規模が予め定められた基準よりも小さいＮｏＣルータを含む経路は、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき前記経路の選択対象から除外しない
請求項１に記載の経路選択装置。
【請求項８】
前記経路選択装置は、前記送信バスマスターか、または半導体システムを構成する前記複数のＮｏＣルータの１つに設けられる
請求項１に記載の経路選択装置。
【請求項９】
複数のＮｏＣルータを介して送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択する経路選択装置であって、
各ＮｏＣルータは、所定の送信元から所定の宛て先へ伝送される１つ以上のフリットの列であるフローの個数を、各ＮｏＣルータにおける伝送品質の劣化および負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として求め、前記異常生起確度値が予め定められた閾値を超えた場合に、前記経路選択装置に前記異常生起確度値を通知する経路異常検出部を備え、
前記経路選択装置は、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成部と、
前記ＮｏＣルータから送信される前記異常生成確度値を用いて、前記ＮｏＣルータにおける前記異常を予測し、前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択部と
を備える経路選択装置。
【請求項１０】
複数のＮｏＣルータをネットワークで相互に接続してなる半導体システムにおいて、前記半導体システムに接続された送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択する経路選択方法であって、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成ステップと、
所定の送信元から所定の宛て先へ伝送される１つ以上のフリットの列を１つのフローと数えるとき、前記経路情報で示される各経路に少なくとも１つずつ定められる監視候補としてのＮｏＣルータから、各ＮｏＣルータが中継する特定のフローの個数を、各ＮｏＣルータにおける伝送品質の劣化または負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として収集し、収集した前記異常生起確度値を用いて各ＮｏＣルータにおける異常を予測する経路異常予測ステップと、
監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択ステップと
を含む経路選択方法。
【請求項１１】
複数のＮｏＣルータをネットワークで相互に接続してなる半導体システムにおいて、前記半導体システムに接続された送信バスマスターから受信バスマスターまでデータを伝送するための経路を選択するためのコンピュータ実行可能なプログラムであって、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成ステップと、
所定の送信元から所定の宛て先へ伝送される１つ以上のフリットの列を１つのフローと数えるとき、前記経路情報で示される各経路に少なくとも１つずつ定められる監視候補としてのＮｏＣルータから、各ＮｏＣルータが中継する特定のフローの個数を、各ＮｏＣルータにおける伝送品質の劣化または負荷の上昇を含む異常の発生のしやすさを表す異常生起確度値として収集し、収集した前記異常生起確度値を用いて各ＮｏＣルータにおける異常を予測する経路異常予測ステップと、
監視候補としての前記ＮｏＣルータの１つ以上において前記異常が予測された場合に、前記経路情報によって示される前記複数の経路の中から、前記送信バスマスターから前記受信バスマスターまでのデータの伝送に用いるべき経路を選択する迂回経路選択ステップと
をコンピュータに実行させるプログラム。
【請求項１２】
複数のＮｏＣルータを介して送信バスマスターから受信バスマスターまでデータを伝送するための経路の異常を予測する装置であって、
前記送信バスマスターから前記受信バスマスターまでデータを伝送するための複数の経路を示す経路情報を生成する経路情報生成部と、
前記経路情報で示される各経路に少なくとも１つずつ定められる監視候補となるＮｏＣルータにおいて、所定の送信元から所定の宛て先へ伝送される１つ以上のフリットの列であるフローの個数を、各ＮｏＣルータでの異常発生の尺度として用いることで、各ＮｏＣルータにおける異常を予測する経路異常予測部と
を備える装置。