(57)【要約】  リンク間のデータ流量の偏りをなくすことが可能なバス制御装置を提供する。  バス制御装置は、バスマスタと、ネットワーク化された通信バスとの間に設けられ、通信バスに流れるパケットの送信経路を制御する。バス制御装置は、利用可能な複数の送信経路上に存在する複数の他のバス制御装置から、出力状況に関する情報を受信するデータ受信部と、出力状況に関する情報に基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出する経路負荷検出部と、均一化指標に基づいて、送信流量が調整された複数の送信経路を決定する経路決定部と、パケットを生成するパケット構成部と、いずれかの出力ポートからパケットを出力するデータ出力部と、パケットの送信先の情報に基づいて選択された送信経路に接続されている出力ポートを決定するヘッダ解析部と、当該出力ポートからパケットを出力するデータ出力部とを備えている。
2011004566.tif 000002
【特許請求の範囲】
【請求項１】
バスマスタと、ネットワーク化された通信バスとの間に設けられ、前記通信バスに流れるパケットの送信経路を制御するバス制御装置であって、
利用可能な複数の送信経路上に存在する複数の他のバス制御装置から、出力状況に関する情報を受信するデータ受信部と、
前記出力状況に関する情報に基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出する経路負荷検出部と、
前記均一化指標に基づいて、前記送信流量が調整された複数の送信経路を決定する経路決定部と、
前記バスマスタから受け取ったデータに基づいてパケットを生成するパケット構成部と、
各々が異なる通信バスに接続された複数の出力ポートのいずれか一つから前記パケットを出力するデータ出力部と、
前記複数の出力ポートの中から、前記パケットの送信先の情報に基づいて選択された送信経路の一つに接続されている出力ポートを決定するヘッダ解析部と
を備えた、バス制御装置。
【請求項２】
前記複数の他のバス制御装置からの要求に従って、前記データ出力部のデータ出力状況に関する情報を通知する出力監視部をさらに備えた、請求項１に記載のバス制御装置。
【請求項３】
前記経路負荷検出部は、出力するフローの優先度毎の転送頻度の平均値を少なくとも含む、前記出力監視部からの出力状況の中で前記平均値を基に均一化指標を算出する、請求項２に記載のバス制御装置。
【請求項４】
前記経路負荷検出部は、出力するフローの優先度毎の転送頻度の平均値および最大値を少なくとも含む、前記出力監視部からの出力状況の中で前記平均値および最大値に基づいて均一化指標を算出する、請求項２に記載のバス制御装置。
【請求項５】
前記経路負荷検出部は均一化指標に含まれる統計多重効果に起因する評価値の信頼度を規定するパラメータを含む、請求項４に記載のバス制御装置。
【請求項６】
前記経路負荷検出部は、前記パケットの転送状況の劣化を検出して、前記信頼度を規定するパラメータを調整し、前記パラメータの調整で転送状況が改善しない場合には、確率的にパラメータを調整する、請求項５に記載のバス制御装置。
【請求項７】
前記出力監視部は、予め定められたタイミングで発行される前記出力状況に関する情報の要求の受信をトリガとして、前記情報を通知する、請求項２に記載のバス制御装置。
【請求項８】
前記経路負荷検出部は、事前に出力状況通知の送信条件を出力監視部に伝達し、
前記出力監視部には、予め前記出力状況に関する情報の要求が送信される条件が通知されており、前記送信条件が成立した場合には前記情報を通知する、請求項２に記載のバス制御装置。
【請求項９】
前記経路負荷検出部は、前記出力状況に関する情報に対して、前記各送信経路のフローの優先度に応じた重みを加えることにより、前記各送信経路の送信流量に関する評価値を算出し、前記各送信経路の送信流量のばらつきを示す均一化指標を算出する、請求項１に記載のバス制御装置。
【請求項１０】
前記経路負荷検出部は、前記各送信経路の送信流量に関する評価値を利用して算出した統計値を、前記均一化指標として算出する、請求項９に記載のバス制御装置。
【請求項１１】
前記経路負荷検出部は、前記出力状況に関する情報と選択対象の送信経路のデータ特性に関する情報とに基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出する、請求項１に記載のバス制御装置。
【請求項１２】
バスマスタと、ネットワーク化された通信バスとの間に設けられ、前記通信バスに流れるパケットの送信経路を制御するバス制御装置のためのシミュレーションプログラムであって、
前記シミュレーションプログラムは、コンピュータに対し、
前記シミュレーションプログラム上のオブジェクト化された複数の他のバス制御装置のクラスであって、利用可能な複数の送信経路上に存在する複数の他のバス制御装置のクラスから、出力状況に関する情報を受信するステップと、
前記出力状況に関する情報に基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出するステップと、
前記均一化指標に基づいて、前記送信流量が調整された複数の送信経路を決定するステップと、
前記バスマスタとして実装されたクラスから受け取ったデータに基づいてパケットを生成するステップと、
各々が異なる通信バスに接続された複数の出力ポートのいずれか一つから前記パケットを出力するステップと、
前記複数の出力ポートの中から、前記パケットの送信先の情報に基づいて選択された送信経路の一つに接続されている出力ポートを決定するステップと、
前記決定された出力ポートから前記パケットを出力するステップと
を実行させる、バス制御装置のためのシミュレーションプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク化された通信バスを備える半導体チップにおいて、通信バスの制御を行うための装置、方法及びプログラムに関する。
【背景技術】
【０００２】
近年、ＳｏＣ（Ｓｙｓｔｅｍ  ｏｎ  Ｃｈｉｐ）が利用される組込機器分野や汎用プロセッサ分野において、半導体チップの高機能化への要求が高まっている。半導体チップの高機能化に伴い、チップ上の通信バスに接続されるバスマスタ数が増加し、バス上を流れる転送データのトラフィック制御が複雑化してきた。【０００３】
たとえば、近年の携帯電話端末は、電子メール送受信、ウェブブラウジング、「ワンセグ」と呼ばれる地上波デジタル放送の受信などが可能であり、多機能化が進んでいる。各機能に対応する一部または全部の処理を行う専用ＩＣはバスマスタとして機能するため、それらを接続する通信バス上のデータのトラフィックを適切に制御する必要がある。また、マイクロプロセッサ（ＭＰＵ）チップにおいてもマルチコア化が進んでいる。バスマスタとして機能する各プロセッサコアを同期させ、協調させるためには、各プロセッサコアを接続する通信バス上のデータのトラフィックを適切に制御する必要がある。【０００４】
トラフィック制御に関する従来の設計方法として、各バスマスタを広帯域な集中型のバスで相互に接続し、クロスバースイッチを切り換えることで、データ転送対象のバスマスタ対にバスの利用権を割り当てるバス制御方式が用いられてきた。しかしながら、このバス制御方式では、バス配線の引き回しによる配線遅延の増加や、クロスバースイッチの面積の増加、消費電力の増加等が問題となっている。また、集中型のバス設計では、平均的なバスの利用効率が向上せず、バスの動作周波数も高くなり、バス部分の消費電力が増加してしまうという問題点も存在する。その理由は、各バスマスタが要求する最大データ転送量を保証するようにバスの動作周波数が設計されるためである。【０００５】
集中型バスの問題点を解決するために、ＮｏＣ（Ｎｅｔｗｏｒｋ  ｏｎ  Ｃｈｉｐ）と呼ばれる通信バスのネットワーク化が進みつつある。【０００６】
たとえば図１（ａ）および（ｂ）は、ＮｏＣバスの一部の構成を示す。図１（ａ）はハードウェア接続構成例を示す図であり、図１（ｂ）はその模式図である。図１（ａ）および（ｂ）によれば、チップ１０上に設けられたバスマスタ１ａ〜１ｃが、それぞれバス制御装置（Ｒ）２を介してバス３に接続されていることが示されている。なお、以下の本願図面のＮｏＣバスは、図１（ｂ）に示す模式図で記載する。【０００７】
図２は、２次元メッシュ型でバスマスタを結合したＮｏＣバスの構成例を示す。マイクロプロセッサやＤＳＰ、メモリ、入出力回路等のバスマスタ毎に、データ転送経路の制御を行うバス制御装置Ｒが配置され、バス制御装置Ｒ間を短配線で接続（リンク）する。【０００８】
このような構成では、送信元のバスマスタから、受信先のバスマスタに対してデータ転送を行うための通信経路が複数存在する。たとえば図３は、送信元から送信先までの３本の経路（１）〜（３）を示す。【０００９】
また、同等機能を提供するバスマスタが複数存在する場合には、受信先及び受信先に至る経路が複数存在する。たとえば図４は、１つの送信元から３つの送信先（１）〜（３）までの各経路を示す。【００１０】
複数の選択候補経路の中から、バスの負荷状況に合わせて、最適な経路を選択することで、チップ全体のデータ転送遅延時間（レイテンシ）やバスの動作周波数を低減することが可能となる。そのため、ＮｏＣバスの性能を最大限引き出すことのできる複数経路制御技術が必要となる。【００１１】
複数のバスマスタを相互に接続するバス上で、複数のデータ転送経路をバスの状態に合わせて選択する方法が特許文献１に開示されている。特許文献１の技術によれば、送信元のバスマスタから受信先のバスマスタ迄、転送対象のデータをフレーム単位で転送する。受信先でフレームが正常に受信された場合には、アクノリッジデータを返信し、そうでない場合にはアクノリッジデータを返信しない。送信元のバスマスタはアクノリッジデータの返信がなかったことをもって、フレーム転送の不具合を検出し、他の送信経路を選択してフレームを再送信する。これにより、通信を継続することを可能としている。受信したフレームのヘッダにエラーが検出された場合には、受信先のバスマスタでフレームが破棄されるため、送信元のバスマスタがアクノリッジデータを受信することはない。また利用中のデータ転送経路において、フレームの転送遅延が大きくなり、規定時間内にフレームが受信先に着信しない場合にも、送信元のバスマスタは規定時間内にアクノリッジデータを受信することができない。このときも、経路の切換が発生する。データ転送経路の状態に合わせて経路がダイナミックに切り換えられることにより、転送遅延やエラーが少ない経路で通信することが可能となる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】日本国特許第３８１６５３１号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１３】
従来から知られている複数経路制御技術を用いる場合、送信元のバスマスタは、転送遅延時間やエラー発生状況等を評価指標として、自らのデータ転送の状態が最良となるような利己的な経路の選択を行う。【００１４】
その結果、バスマスタ間を接続するバス（リンク）間を流れる転送データの流量に偏りが生じることがある。その理由は、ＮｏＣに存在する複数のバスマスタが競合して最良経路を選択しようとすることで、データ転送経路及びリンク資源の奪い合いが生じ、いくつかのリンクに複数の送信元からのデータ転送が集中するためである。【００１５】
この偏りによって３つの課題が発生する。【００１６】
第一の課題は、流量の大きなリンクにおいて、リンク両端のバス制御装置の動作負荷が高くなり、データ転送のレイテンシが増加することである。バスマスタ間のデータ転送のレイテンシはバスマスタの動作速度を律速し、例えばプロセッサとメモリ間のデータ転送の場合には、メモリアクセスレイテンシに対応したプロセッサのウエイトサイクル増大による処理性能低下に繋がる。【００１７】
第二の課題は、流量の大きなリンクに合わせてバスの動作周波数をより高く設計する必要が生じることである。バスの動作周波数が高速になるにつれ、配線遅延やクロストークの制御が困難となり、設計工数や検証工数が増大する。【００１８】
第三の課題は、バスの動作周波数が高くなるほど、リンクの消費電力が増加することである。リンクを構成するトランジスタの消費電力Ｐは、スイッチングレートα、回路の容量Ｃ、電源電圧Ｖ、動作周波数ｆとすると、数１で表される。
【数１】
2011004566.tif 000003
【００１９】
また、動作周波数を抑えることにより、電源電圧も数２に示す関係で低減することが可能となる。
【数２】
2011004566.tif 000004
【００２０】
数２中のηはトランジスタの動作スレッショルド電圧と電源電圧の比であり、γはプロセスルールに依存する定数である。例えばγ＝２とした場合、動作周波数の低減は、３乗のオーダーで消費電力に寄与するため、流量の偏りによっては、高い転送レートを収容するためのリンクの消費電力は非常に大きくなる。【００２１】
本発明は、上記課題を解決するためになされたものであり、その目的は、リンク間のデータ流量の偏りをなくすことが可能なバス制御装置を提供することにある。
【課題を解決するための手段】
【００２２】
本発明によるバス制御装置は、バスマスタと、ネットワーク化された通信バスとの間に設けられ、前記通信バスに流れるパケットの送信経路を制御するバス制御装置であって、利用可能な複数の送信経路上に存在する複数の他のバス制御装置から、出力状況に関する情報を受信するデータ受信部と、前記出力状況に関する情報に基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出する経路負荷検出部と、前記均一化指標に基づいて、前記送信流量が調整された複数の送信経路を決定する経路決定部と、前記バスマスタから受け取ったデータに基づいてパケットを生成するパケット構成部と、各々が異なる通信バスに接続された複数の出力ポートのいずれか一つから前記パケットを出力するデータ出力部と、前記複数の出力ポートの中から、前記パケットの送信先の情報に基づいて選択された送信経路の一つに接続されている出力ポートを決定するヘッダ解析部とを備えている。【００２３】
前記バス制御装置は、前記複数の他のバス制御装置からの要求に従って、前記データ出力部のデータ出力状況に関する情報を通知する出力監視部をさらに備えていてもよい。【００２４】
前記経路負荷検出部は、出力するフローの優先度毎の転送頻度の平均値を少なくとも含む、前記出力監視部からの出力状況の中で前記平均値を基に均一化指標を算出してもよい。【００２５】
前記経路負荷検出部は、出力するフローの優先度毎の転送頻度の平均値および最大値を少なくとも含む、前記出力監視部からの出力状況の中で前記平均値および最大値に基づいて均一化指標を算出してもよい。【００２６】
前記経路負荷検出部は、均一化指標に含まれる統計多重効果に起因する評価値の信頼度を規定するパラメータを含んでいてもよい。【００２７】
前記経路負荷検出部は、前記パケットの転送状況の劣化を検出して、前記信頼度を規定するパラメータを調整し、前記パラメータの調整で転送状況が改善しない場合には、確率的にパラメータを調整してもよい。【００２８】
前記出力監視部は、予め定められたタイミングで発行される前記出力状況に関する情報の要求の受信をトリガとして、前記情報を通知してもよい。【００２９】
前記経路負荷検出部は、事前に出力状況通知の送信条件を出力監視部に伝達し、前記出力監視部には、予め前記出力状況に関する情報の要求が送信される条件が通知されており、前記送信条件が成立した場合には前記情報を通知してもよい。【００３０】
前記経路負荷検出部は、前記出力状況に関する情報に対して、前記各送信経路のフローの優先度に応じた重みを加えることにより、前記各送信経路の送信流量に関する評価値を算出し、各送信経路の送信流量のばらつきを示す均一化指標を算出してもよい。【００３１】
前記経路負荷検出部は、前記各送信経路の送信流量に関する評価値を利用して統計値を算出し、前記統計値を利用して前記各送信経路間の関係が均一か否かを判断してもよい。【００３２】
前記経路負荷検出部は、前記出力状況に関する情報と選択対象の送信経路のデータ特性に関する情報とに基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出してもよい。【００３３】
本発明によるシミュレーションプログラムは、バスマスタと、ネットワーク化された通信バスとの間に設けられ、前記通信バスに流れるパケットの送信経路を制御するバス制御装置のためのシミュレーションプログラムであって、前記シミュレーションプログラムは、コンピュータに対し、前記シミュレーションプログラム上のオブジェクト化された複数の他のバス制御装置のクラスであって、利用可能な複数の送信経路上に存在する複数の他のバス制御装置のクラスから、出力状況に関する情報を受信するステップと、前記出力状況に関する情報に基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出するステップと、前記均一化指標に基づいて、前記送信流量が調整された複数の送信経路を決定するステップと、前記バスマスタとして実装されたクラスから受け取ったデータに基づいてパケットを生成するステップと、各々が異なる通信バスに接続された複数の出力ポートのいずれか一つから前記パケットを出力するステップと、前記複数の出力ポートの中から、前記パケットの送信先の情報に基づいて選択された送信経路の一つに接続されている出力ポートを決定するステップと、前記決定された出力ポートから前記パケットを出力するステップとを実行させる。
【発明の効果】
【００３４】
本発明によれば、バス制御装置は、利用可能な複数の送信経路上の他のバス制御装置に対して出力状況の監視を行い、各送信経路間の送信流量のばらつきである均一化指標に基づいてデータの送信経路を切り換える。これにより、ＮｏＣバスを構成するリンク間の流量の偏りが自動的に抑制されるため、データ転送負荷がバス全体で均一化され、特定リンクへの負荷集中による通信遅延時間、レイテンシの増加が抑えられる。【００３５】
また、リンクの動作周波数が低減されるので、バス設計を容易にし、データ転送時のバスの消費電力を削減することが可能となる。またリンクの動作周波数の動的制御技術と組み合わせることにより、バスの消費電力を更に効率的に削減することが可能となる。【００３６】
また、同等機能を提供するバスマスタへの経路負荷を、統計多重効果を考慮した上で均一化することにより、バスマスタの負荷分散効果も得られる。このため、分散型のメモリ・アーキテクチャに本発明を適用することにより、メモリアクセスの許容レイテンシに対する信頼性を確保した上で、アクセス集中によるボトルネックを回避することが可能となる。
【図面の簡単な説明】
【００３７】
【図１】（ａ）はハードウェア接続構成例を示す図であり、（ｂ）はその模式図である。
【図２】２次元メッシュ型でバスマスタを結合したＮｏＣバスの構成例を示す図である。
【図３】送信元から受信先までの３本の経路（１）〜（３）を示す図である。
【図４】１つの送信元から３つの受信先（１）〜（３）までの各経路を示す図である。
【図５】携帯電話端末に搭載されるシステム半導体をＮｏＣバスを用いて構成した例を示す図である。
【図６】（ａ）はワンセグＴＶ視聴のアプリケーションにおけるデータ転送経路を示す図であり、（ｂ）は携帯電話用フルブラウザのネットワーク通信用スレッドにおけるデータ転送経路を示す図であり、（ｃ）はネットワークゲームのクライアントプログラムが遠隔のサーバーと通信する際のデータ転送経路を示す図である。
【図７】送信元Ｍ２１から受信先Ｍ２４へデータ転送を行う場合に、利用可能な３本の選択候補経路が定義されていることを示す図である。
【図８】データ転送処理Ｂ，Ｃ，Ｄが同時に発生している状態でのバスマスタＭ２１−Ｍ２４間での選択候補経路毎のデータ転送量を示す図である。
【図９】動画再生時のデータ転送経路を示す図である。
【図１０】チップ上で複数のデータ転送処理が同時的に発生している状態を示す図である。
【図１１】図８に対して、データ転送Ａが新たに追加された状態を示す図である。
【図１２】実施形態１によるデータ転送量の調整結果を示す図である。
【図１３】リンク間の経路流量の偏りをなくし、均一化を行うための動作詳細を説明するための部分経路図を示す図である。
【図１４】本発明の実施形態によるバス制御装置２の構成を示す図である。
【図１５】パケットの構成例を示す図である。
【図１６】出力情報通知パケットのペイロードに記述される情報の例を示す図である。
【図１７】バス制御装置Ｒ２１がバスマスタＭ２４に至る経路（２）上の出力情報を収集する際のプロトコルの例を示す図である。
【図１８】経路負荷検出部１０１の以上の処理の流れを示す図である。
【図１９】バス制御装置Ｒ２１の経路決定部１０２が管理する経路表の例を示す図である。
【図２０】分散型のメモリ・アーキテクチャに本発明を適用した構成の例を示す図である。
【図２１】出力情報の例を示す図である。
【図２２】出力情報を収集するためのプロトコルの例を示す図である。
【図２３】実施形態３のバス制御装置の性能評価をＮｏＣのシミュレータを用いて行った結果を示す図である。
【図２４】数２９において、ηiを閉区間［−０．０５，  ＋０．０５］の範囲で変動する一様分布に従うランダムノイズとしたときの、ｍ１及びｍ２の時間変化を示す図である。
【図２５】シミュレーションに用いたＮｏＣの構成を示す図である。
【図２６】メモリモジュール側でのスループットとレイテンシとの関係を示す図である。
【図２７】メモリモジュール側でのスループットとレイテンシとの関係を示す図である。
【発明を実施するための形態】
【００３８】
以下、添付の図面を参照しながら、本発明によるバス制御装置の実施形態を説明する。
【００３９】
（実施形態１）
本実施形態によるバス制御装置を具体的に説明するに先立って、ＮｏＣ（Ｎｅｔｗｏｒｋ  ｏｎ  Ｃｈｉｐ）と呼ばれる通信バス、その通信バスで利用可能な送信経路、および、各送信経路におけるデータ転送量を説明する。併せて本実施形態によるバス制御装置の動作原理を説明する。
【００４０】
図５は、携帯電話端末に搭載されるシステム半導体を、ＮｏＣバスを用いて構成した例である。図面の記載形式は、図１（ｂ）に準じている。なお、図中には各バス制御装置Ｒと１対１でバスマスタが接続されているが、バスマスタが接続されておらず中継処理のみを行うバス制御装置が混在していても良い。
【００４１】
バス制御装置Ｒにバスマスタが接続されている場合には、各バスマスタに対して一意のアドレスが付与されるが、バスマスタが接続されていない場合には、バス制御装置に対して仮想的な一意のアドレスを付与すればよい。本明細書では、いずれの場合もバスマスタアドレスと表現する。
【００４２】
携帯電話端末は、本来的な機能としての音声通話に加えて、電子メールやＷｅｂブラウジング、ワンセグＴＶの視聴、ネットワークを利用したゲームなどの、豊富な機能が要求される典型的な例と考えられる。図６（ａ）はワンセグＴＶ視聴のアプリケーションにおけるデータ転送経路を示す。バスマスタＭ１１を送信元、バスマスタＭ１４を受信先とするデータ転送処理Ｂが矢印に示された経路で行われている。また図６（ｂ）は携帯電話用フルブラウザのネットワーク通信用スレッドにおけるデータ転送経路を示す。バスマスタＭ２１を送信元、バスマスタＭ２４を受信先とするデータ転送処理Ｃが矢印に示された経路で行われていることを示す。また図６（ｃ）はネットワークゲームのクライアントプログラムが遠隔のサーバーと通信する際のデータ転送経路を示す。バスマスタＭ２３を送信元、バスマスタＭ３４を受信先とするデータ転送処理Ｄが矢印に示された経路で行われていることを示す。
【００４３】
図６（ａ）、（ｂ）および（ｃ）中のデータ転送処理Ｂ，ＣおよびＤは、マルチスレッド型のＯＳや並列処理構成のハードウェアにより、同時並行的に実行されるものである。
【００４４】
図７は、送信元Ｍ２１から受信先Ｍ２４へデータ転送を行う場合に、利用可能な３本の選択候補経路が定義されていることを示している。以下、それぞれの選択候補経路を経路（１）、経路（２）、経路（３）と表現する。
【００４５】
図８は、データ転送処理Ｂ，Ｃ，Ｄが同時に発生している状態でのバスマスタＭ２１−Ｍ２４間での選択候補経路毎のデータ転送量を示している。経路のデータ転送量は、経路上の各リンクのデータ転送量の最大値としても良い。例えば、図６（ｃ）に示すバス制御装置Ｒ３３−Ｒ３４間のリンクのデータ転送量が、経路（３）上の他の各リンクのデータ転送量よりも大きい場合には、経路（３）のデータ転送量は、Ｒ３３−Ｒ３４間のリンクのデータ転送量として定義される。
【００４６】
たとえば、ユーザが携帯電話の画面上のフルブラウザアプリケーションを操作し、動画サイトへのアクセスを行い、動画コンテンツの再生を指示したとする。このとき、動画再生用のスレッドが起動される。図９は、動画再生時のデータ転送経路を示す。図９に示すように、バスマスタＭ１２を送信元、バスマスタＭ２３を受信先とするデータ転送処理Ａが矢印に示された経路で開始される。
【００４７】
いま、図８のデータ転送処理Ｂ、ＣおよびＤが存在している状況下で、上述のデータ転送処理Ａが追加されたと仮定する。
【００４８】
図１０は、チップ上で複数のデータ転送処理が同時的に発生している状態を示す。そして図１１は、図８に対して、データ転送Ａが新たに追加された状態を示す。図１１によれば、動画再生用スレッドのデータ転送経路として、図８において最もデータ転送量の少ない経路（２）が選択されている。
【００４９】
しかしながら、図１０に示すように、バス制御装置Ｒ２２とＲ２３との間のリンクには、データ転送処理ＡおよびＣが競合している。バス制御装置Ｒ２２とＲ２３との間のリンクでは、データ転送処理ＡおよびＣが並列的に行われる。よって、データ転送量が多くなるため、動作周波数を高くせざるを得ない。その結果、図１１に示すように、結果として３本の経路のデータ転送量が不均一な状態となっている。リンクの動作周波数が図１１に示す点線のレベルにある場合には、経路（２）は高負荷な状態であり、リンクの消費するエネルギーも大きい。
【００５０】
そこで、本実施形態では、複数経路のデータ転送量が均一になるように、データ転送量を調整する。たとえば図１２は、本実施形態によるデータ転送量の調整結果を示す。図１２に示すように、３本の経路のデータ転送量を均一な状態になるように制御することによって、より低い動作周波数でデータ転送を行うことが可能となり、消費電力も低減できる。
【００５１】
図１３は、リンク間の経路流量の偏りをなくし、均一化を行うための動作詳細を説明するための部分経路図を示す。説明を簡略化するため、図１０の一部分を取り出して記載している。システム半導体全体の構成は図１０に示された通りである。図１３に描かれていない配線やバスマスタ、バス制御装置は、省略されているだけであり、図１０に示された通り存在する。
【００５２】
送信元のバスマスタＭ２１に接続されたバス制御装置Ｒ２１は、データ転送対象であるバスマスタＭ２４を受信先とする予め定義された３本の経路（１）、経路（２）、経路（３）に対して、経路負荷状況を収集する。経路負荷状況は、各バス制御装置が管理する出力情報を収集することによって行われる。各経路の出力情報の収集が完了すると、バス制御装置Ｒ２１は、各経路の流量評価値を算出し比較することによって、経路の均一性を評価する。不均一な状態となっている場合には、バス制御装置Ｒ２１は、最も均一性が高くなる経路にデータ転送経路を切り換えることで、データ転送に偏りが発生することを防ぎ、バス全体に転送データを分散するように制御する。
【００５３】
以下、図１４を参照しながら、この動作を行うためのバス制御装置の構成例を説明する。
【００５４】
図１４は、本実施形態によるバス制御装置２の構成を示す。
【００５５】
バス制御装置２は、経路負荷検出部１０１と、経路決定部１０２と、パケット構成部１０３と、データ受信部１０４と、ヘッダ解析部１０５と、データ出力部１０６と、出力監視部１０７とを備えている。以下、各構成要素の機能を説明する。
【００５６】
（パケット構成部１０３）
ネットワーク化されたＮｏＣバス上のデータ転送は、パケットの単位で行われる。パケット構成部１０３は、自身に接続されたバスマスタから受け取ったデータに基づいてパケットを生成する。
【００５７】
図１５はパケットの構成例を示す。パケットはヘッダ、バスマスタ間で交換するためのデータの実体であるペイロード、誤り検出符号等を格納するトレイラーによって構成される。このうち、ペイロードやトレイラーは必須ではない。
【００５８】
ヘッダは、以下の情報を含んでいる。ただし、受信先のバスマスタのアドレス以外は必須ではない。
・プロトコル種別
・受信先のバスマスタとバス制御装置に割り当てられたアドレス
・送信元のバスマスタとバス制御装置に割り当てられたアドレス
・同一アプリケーションまたは同一目的の一連のパケット群に割り当てられるラベル情報
・同一ラベル情報を持つパケット群に対して一意であり送信時刻順に割り当てられる番号情報であるパケット連番
・パケットが転送時に許容するレイテンシのレベルである優先度
・付加情報、および、
・後続するペイロードの有無やペイロードの長さを示すペイロード長
【００５９】
なお、プロトコル種別は、そのパケットがバスマスタ間でのデータ転送目的であるか、経路負荷検出を目的とした出力情報の要求であるか、通知であるかを示す識別コードである。以下では、それぞれの種別のパケットを、「転送データパケット」、「出力情報要求パケット」、および、「出力情報通知パケット」という。
【００６０】
パケット構成部１０３は、自身に接続されたバスマスタから発せられたデータ転送要求に従い、図１５に示すフォーマットに準拠して転送データパケットを構成し、ヘッダ解析部１０５に送る。
【００６１】
またパケット構成部１０３は、経路負荷検出部１０１から発せられた出力情報収集要求に従い、図１５に示すフォーマットに準拠して出力情報要求パケットを構成し、ヘッダ解析部１０５に送る。またパケット構成部１０３は、出力監視部１０７から発せられた出力情報通知要求に従い、図１５に示すフォーマットに準拠して出力情報通知パケットを構成し、ヘッダ解析部１０５に送る。
【００６２】
（データ受信部１０４）
データ受信部１０４は、自身が接続された単数または複数の入力リンクから、転送データパケットや出力情報通知パケットを受信し、ヘッダ解析部１０５に送る。図１４では入力ポートはＥ、Ｗ、Ｓ、Ｎの４本を記載しているが、１本以上であれば何本でも良い。各入力ポートは、異なる他のバス制御装置の出力ポートに接続される。
【００６３】
（ヘッダ解析部１０５）
ヘッダ解析部１０５は、データ受信部１０４によって渡されたパケットのプロトコル種別を照合し、パケットの種別を特定する。本実施形態では、パケットは、転送データパケット、出力情報要求パケット、または、出力情報通知パケットのいずれかであるとしている。
【００６４】
パケットの種別が転送データパケットである場合には、ヘッダ解析部１０５は、受信先のバスマスタを示すアドレス（受信先アドレス）を参照する。その結果、受信先が、自身が接続されたバスマスタへのパケットである場合には、ヘッダ解析部１０５はペイロード部分を抽出してバスマスタに送る。また、受信先が、自身が接続されたバスマスタへのパケットでない場合には、ヘッダ解析部１０５は受信先バスマスタのアドレスを経路決定部１０２に提示し、パケットを出力すべき出力ポートを決定する。
【００６５】
次に、パケットの種別が出力情報要求パケットである場合には、ヘッダ解析部１０５は、受信先アドレスを参照する。その結果、受信先が、自身が接続されたバスマスタへのパケットである場合には、ヘッダ解析部１０５は出力監視部１０７に出力情報の通知を要請し、パケットヘッダに格納されていた送信元のバスマスタアドレス（送信元アドレス）を提示する。また、受信先が、自身が接続されたバスマスタへのパケットでない場合には、ヘッダ解析部１０５は受信先バスマスタのアドレスを経路決定部１０２に提示し、パケットを出力すべき出力ポートの通知を受け取る。それにより、ヘッダ解析部１０５は出力ポートを選択する。なお、パケット構成部１０３が経路決定部１０２から選択候補経路のリスト及びホップリストを受け取っている場合には、それらに基づいて、パケットを出力すべき出力ポートを選択してもよい。
【００６６】
一方、パケットの種別が出力情報通知パケットである場合にも、ヘッダ解析部１０５は、受信先バスマスタアドレスを参照する。その結果、受信先が、自身が接続されたバスマスタへのパケットである場合には、ヘッダ解析部１０５は経路負荷検出部１０１にパケットヘッダに格納された送信元のバスマスタアドレスとペイロードに格納された出力情報を送る。一方、受信先が、自身が接続されたバスマスタへのパケットでない場合には、ヘッダ解析部１０５は受信先バスマスタのアドレスを経路決定部１０２に提示し、経路決定部１０２から通知されたポートを、パケットを出力すべき出力ポートとして決定する。
【００６７】
（データ出力部１０６）
データ出力部１０６は、ヘッダ解析部１０５によって提示された出力ポートへの配線の切換を行い、パケットを信号としてバス上に送出する。また経路の輻輳によって、データ転送パケットの送出遅延が発生した場合には、データ出力部１０６は、優先度の低いデータ転送パケットの転送を遅延させることで、優先度の高いデータ転送パケットから順に優先転送を行う。
【００６８】
（出力監視部１０７）
出力監視部１０７は、ヘッダ解析部１０５から受けた出力情報通知要請に応答するために、データ出力部１０６の各出力ポートの状態監視を行う。各出力ポートには、複数のバスマスタが送出したデータ転送パケットが混在して出力されており、同一のラベル情報を持つデータ転送パケットは同一のフローであると識別することができる。
【００６９】
ここで「フロー」とは、アプリケーションやタスクの実行等の同一目的のために、送信元バスマスタから受信先バスマスタに送信される一連のデータ転送パケット群を指し、フロー毎に異なる許容レイテンシを持つ。フローが要求する許容レイテンシのレベルは、パケットヘッダに格納された優先度によって示される。例えば、リアルタイム性が要求される信号処理用途では高優先度であり、バックグラウンドプロセスによるファイル転送用途では低優先度となる。
【００７０】
優先度は、アプリケーション毎に固定であっても良いし、アプリケーションを構成するスレッド毎に変化させても良いし、プログラマやコンパイラが決定する更に細かい処理単位毎に変化させても良い。また各フローの送信レートは一定ではなく、フローによって異なるのが通常であり、さらに同一フローであっても、送信レートは時間変動するのが通常である。
【００７１】
図１６は、出力情報通知パケットのペイロードに記述される情報の例を示す。出力監視部１０７は、図１６に示す情報を、他のバス制御装置から自身宛の出力情報要求パケットを受理した際に、該当する出力ポートに関して作成し、送信元のバス制御装置に対して通知する。出力情報は複数のエントリーから構成され、各エントリーはパケットの優先度に対応する。各優先度レベル毎に、かかる優先度のパケットを送信するために要した出力ポートのバスサイクル数の時間平均、最大値、最小値がレポートされる。
【００７２】
本実施形態では、同一優先度の複数のフローがレポート対象の出力ポート上で混在している場合において、それらを区別していないが、より詳細にフロー毎に監視しても良い。またレポートする出力ポートの情報は、本実施形態に示す通り、出力監視部１０７が計測した実測値に基づいて算出された値でも良いし、バスマスタにより付加情報として通知されるフローのスペックに基づいた値でも良い。
【００７３】
図１７は、バス制御装置Ｒ２１がバスマスタＭ２４に至る経路（２）上の出力情報を収集する際のプロトコルの例を示す。図中の「ＭＡ」は、バスマスタに付与されたＮｏＣ上の一意のアドレスである。バス制御装置もこのアドレスにより特定できる。
【００７４】
送信元のバス制御装置Ｒ２１が経路（２）上に送信した出力情報要求パケットは、経路（２）上のバス制御装置Ｒ２２及びＲ２３を通って、経路終点のバス制御装置Ｒ２４に回送される。各バス制御装置Ｒ２２、Ｒ２３は、経路（２）上の次段のバス制御装置へのリンクにつながる出力ポートに関する出力情報通知パケットの返信を行うと共に、出力情報要求パケットを経路（２）上の次段のバス制御装置に対して回送する。経路終点のバス制御装置Ｒ２４は、出力情報要求パケットを破棄する。
【００７５】
（経路負荷検出部１０１）
経路負荷検出部１０１は、自身に接続されたバスマスタが送出する各フローの受信先アドレスと送信候補経路の情報を用いて、全ての送信候補経路に対して、出力情報要求パケットを送信する。出力情報要求パケットを送信するタイミングは、一定時間毎に定期的に行っても良い。また経路負荷検出部１０１は、出力情報要求パケット内に出力情報通知パケットの返信条件を格納しておき、経路上の各バス制御装置が返信条件を満たした際に、出力情報通知パケットを返信するトラップ方式を用いても良い。この場合、返信条件はデータ転送パケットの占有サイクル数の変化量が一定の閾値を超えた場合としても良い。
【００７６】
以下、図１３において、バス制御装置Ｒ２１にある経路負荷検出部１０１から、経路（１）、経路（２）、経路（３）に対して、定期的に出力情報要求パケットを発行する場合について説明する。各経路上の各バス制御装置は、図１７に示すプロトコルに従って、バス制御装置Ｒ２１に出力情報通知パケットを返信する。そのため、バス制御装置Ｒ２１は、ｉ番目の経路上のｊ番目のバス制御装置から、優先度δ毎に、それぞれ図１６に示す出力情報ωｉｊを収集することができる。
【数３】
2011004566.tif 000005
【００７７】
重み係数行列をＰとし、行列の要素をｐｉｊと表すとする。Ｐの各行は出力情報ベクトルωｉｊの各要素に対応し、各列は優先度δに対応する。本実施形態では、出力情報として、時間平均、最大値、最小値の３種類の情報を収集するため、Ｐの行数は３であり、フローを高優先度、中優先度、低優先度の３種類に分類するため、Ｐの列数は３である。
【数４】
2011004566.tif 000006
【００７８】
このとき、経路ｉ上のｊ番目のリンクの流量評価値βｉｊは、数５で示される。ｅは全要素が１のベクトルである。
【数５】
2011004566.tif 000007
【００７９】
経路ｉの流量評価値βｉは、経路上のリンクの流量評価値の最大値として定義して良い。
【数６】
2011004566.tif 000008
【００８０】
重み係数行列の要素を調整することにより、経路負荷検出部１０１は各経路の流量を適切に評価することができる。そして経路負荷検出部１０１は、流量評価値を均一化するようにフローの経路を制御することで、データ転送量がバス全体に均一化され、バスの動作周波数低減と、消費電力削減の効果が得られる。
【００８１】
経路負荷検出部１０１は、各バスマスタが送信するフローの特性が事前設計的に想定可能であれば、その情報を基にして重み係数行列の各係数値を決定しても良い。例えば、各バスマスタが時間的に変動しないフローのみしか発生させないことが分かっている場合には、各フローの平均値、最大値、最小値は一致するため、平均値のみを流量評価に反映させれば良い。このとき、重み係数行列Ｐを数７のように定義できる。
【数７】
2011004566.tif 000009
【００８２】
しかしながら、各フローは時間的に変動する特性を有するのが通常であるため、経路毎の流量の比較は単純な平均値比較とはならない。また低優先度のフローが高優先度のフローを阻害しないように、フローの優先度も適切に考慮して流量評価を行う必要がある。フローの時間変動も考慮した重み係数行列Ｐの例を数８に示す。
【数８】
2011004566.tif 000010
【００８３】
数８の重み係数行列を用いた場合の経路ｉの流量評価値βｉは、数５及び数６より、数９のようになる。式中のδｓｅｌｆは、制御対象フローの持つ優先度である。
【数９】
2011004566.tif 000011
【００８４】
数８によって定義された重み係数行列によれば、数９によって分かる通り、自身よりも高優先度のフローに対しては、その時間変動特性のうちの最大値をもって、流量が経路負荷検出部１０１によって評価されることを示している。またこの重み係数行列によれば、制御対象フロー自身よりも低優先度のフローに対しては、データ出力部１０６が行う優先度制御を前提とした平均値評価が行われることを示している。そしてこの重み係数行列によれば、自身と同一優先度のフローに対しては、時間変動特性がベータ分布に従うことを前提とした最頻値評価が行われることを示している。数７及び数８は、重み係数行列の定義の方法を制限するものではなく、想定されるフローの特性に合わせて、最適なＰを定義して良い。
【００８５】
３本の選択候補経路間の関係が均一かそうでないかの判断を行うための指標として、閾値を導入しても良い。閾値判定の例として、数１０に示す統計値ρを用いても良い。式中のＲは選択候補経路数を示す。
【数１０】
2011004566.tif 000012
【００８６】
ρの値が事前に定義された閾値ρｔｈを下回った場合には、経路負荷検出部１０１は経路間の均一性が損なわれたという判断をしても良い。経路間の均一性が損なわれた状態を検出した場合には、経路負荷検出部１０１は、制御対象フロー自身が現在データ転送パケットを伝送している送信経路以外の選択候補経路に移動した場合の仮想的なρの値を計算する。そして、経路負荷検出部１０１はそれらを比較し、最もρの値が大きくなる選択候補経路を切換先経路として決定し、経路決定部１０２に提示することで、経路表を更新し、経路の切換を行わせる。
【００８７】
図１８は、経路負荷検出部１０１の以上の処理の流れを示す図である。
【００８８】
ステップＳ１において、経路負荷検出部１０１は、自動経路切り換え処理を開始する。
【００８９】
具体的には、ステップＳ２において、経路負荷検出部１０１は、全ての送信候補経路に対して出力情報要求パケットを送信することにより、経路上の各中継ルータから、各送信候補経路に関する出力情報を収集する。
【００９０】
ステップＳ３からＳ５では、各経路に対する処理が行われる。具体的には、ステップＳ４において、経路負荷検出部１０１は各経路の流量評価値βｉを算出する。
【００９１】
ステップＳ６において、経路負荷検出部１０１は経路間の均一性指標ρを算出する。そして次のステップＳ７において、経路負荷検出部１０１は均一性指標ρが事前に定義された閾値ρｔｈを下回ったか否かを判定する。すなわち、均一性指標ρが閾値ρｔｈを下回った場合には、均一性が損なわれたとして、経路切り替えが必要であると判定する。このとき処理はステップＳ８に進む。一方、均一性指標ρが閾値ρｔｈを下回っていない場合には、処理はステップＳ１１に進み、その時点での経路切り換えは行わず、処理を終了する。
【００９２】
ステップＳ８において、経路負荷検出部１０１は、自身のフローが選択候補経路に移動したとした場合の仮想的な均一性指標ρの値を計算して、それらを比較する。そしてステップＳ９において、経路負荷検出部１０１は最もρの値が大きくなる選択候補経路を切換先経路として決定する。その結果、経路負荷検出部１０１は、ステップＳ１０において経路決定部への処理要求を発行する。
【００９３】
ステップＳ１１まで到達すると、経路負荷検出部１０１は、再びステップＳ１からの処理を繰り返す。
【００９４】
均一性指標ρは、優先度を考慮して重み付けられた流量評価値βを利用して算出される。そして、その指標ρに基づいて均一性が損なわれたと判定された場合には経路が適切に切り換えられる。これにより、データ転送に偏りが発生することを防ぐことができる。
【００９５】
なお、送信候補経路間の均一性を示すρの値が閾値を下回る時間割合を監視し、均一性制御が功を奏していないことを検知することで、重み係数行列Ｐの各要素にフィードバック制御を働かせても良い。
【００９６】
（経路決定部１０２）
経路決定部１０２は、経路表を管理し、パケット構成部１０３が提示する宛先アドレスに基づいて経路表を検索し、ネクストホップとするバス制御装置に関連した出力ポートをパケット構成部１０３に通知する。
【００９７】
図１９は、バス制御装置Ｒ２１の経路決定部１０２が管理する経路表の例を示す。宛先アドレスＭＡ２４に位置するバスマスタＭ２４への経路として、３本の選択候補経路が定義されている。この選択候補経路のそれぞれのネクストホップとなるバス制御装置のアドレスとそれに対応する出力ポート、終点アドレスに至る迄にホップするバス制御装置のアドレスのリスト、データ転送パケットが実際に送信されている経路を示す選択情報が記録され管理される。
【００９８】
経路決定部１０２は、経路負荷検出部１０１からの要求に従い、受信先アドレスと選択候補経路のリスト及びホップリストを提示し、出力情報要求パケットの送信に必要な経路に関する情報を提供する。また経路負荷検出部１０１から提示された切換先経路の情報に従い、経路表の選択情報の更新を行うことで、データ転送パケットが送信される経路を変更する。
【００９９】
以上説明したバス制御装置２によれば、ＮｏＣバスを構成するリンク間の流量の偏りが自動的に抑制されるため、データ転送負荷がバス全体で均一化され、特定リンクへの負荷集中による通信遅延時間、レイテンシの増加が抑えられる。リンクの動作周波数を低減することで、バス設計を容易にし、データ転送時のバスの消費電力を削減することが可能となる。またリンクの動作周波数の動的制御技術と組み合わせることにより、バスの消費電力を更に効率的に削減することが可能となる。また同等機能を提供するバスマスタへの経路負荷を、統計多重効果を考慮した上で均一化することにより、バスマスタの負荷分散効果も得られる。このため、分散型のメモリ・アーキテクチャに本発明を適用することにより、メモリアクセスの許容レイテンシに対する信頼性を確保した上で、アクセス集中によるボトルネックを回避することが可能となる。
【０１００】
（実施形態２）
図２０は、分散型のメモリ・アーキテクチャに本発明を適用した構成の例を示す。３つのプロセッサＵＰ１１、ＵＰ１２、ＵＰ１３と、３つの共有メモリモジュールＭＥＭ３１、ＭＥＭ３２、ＭＥＭ３３が、３×３のメッシュ型のバス制御装置のネットワークを介して接続されている。プロセッサは、タスク起動時に必要なメモリ領域をいずれかのメモリモジュール上に割り当て、タスク終了時に割り当てた領域を解放する。しかし、特定のメモリモジュールへの割当が集中した場合、メモリモジュール間でアクセスレートにばらつきが発生し、アクセスが集中したメモリモジュールへのアクセスバスの動作周波数が上がり、設計面、消費電力面で課題となる。プロセッサでのメモリ割当時に、メモリモジュール間のアクセスレートができるだけ均一になるように割当処理を行うことで、アクセスバスの動作周波数低減と、消費電力削減の効果が得られる。
【０１０１】
本実施形態による分散型メモリネットワークを構成するバス制御装置の構成は、以下に特に説明する点を除いては、図１４に示す実施形態１のバス制御装置２の構成と同じである。共通する機能の説明は省略する。
【０１０２】
（パケット構成部１０３）
本実施形態では、前提条件として、プロセッサとメモリモジュール間の各フローのレート特性である平均レートと最大レートが事前設計されており、各フローは同一の優先度を有する場合を想定する。複数の優先度に対応するフローが混在する場合には、実施形態１と同様に扱えば良い。プロセッサ側のバス制御装置内にあるパケット構成部１０３は、図１５に示すように、プロセッサ上のタスクから提示されたフローのレート特性を、付加情報としてデータ転送パケットのヘッダに格納して送信する。これにより、メモリモジュール側のバス制御装置に対して、アクセスフローのレート特性を伝達する。
【０１０３】
（出力監視部１０７）
メモリモジュール側のバス制御装置内にある出力監視部１０７は、プロセッサ側のバス制御装置から伝達されるアクセスフロー毎のレート特性を基に、数１１、数１２に示す評価式を管理する。
【数１１】
2011004566.tif 000013
【数１２】
2011004566.tif 000014
【０１０４】
式中で、μｉｊは、ｐｉｊは、ｉ番目のメモリモジュールのｊ番目のアクセスフローに対する平均レート及び最大レートの値であり、ｎはｉ番目のメモリモジュールに割り当てられたアクセスフローの総数、μi、ｐｉはｉ番目のメモリモジュールの平均レート評価式と最大レート評価式である。他のバス制御装置から出力情報要求パケットを受理した出力監視部１０７は、図２１に示される出力情報を含んだ出力情報通知パケットを返信する。
【０１０５】
バス制御装置から伝達されるアクセスフローのレート特性は、設計時に予め算定できる情報を含んでも良い。そのような情報として、たとえばＳｏＣ上で動作するアプリケーション、信号処理のモジュールが生成する平均レート、最大レート、最小レート、アクセスレートの標準偏差、処理の優先度、許容されるアクセスレイテンシを挙げることができる。
【０１０６】
またユーザの機器操作などによって発生するメモリアクセスのように、設計段階でアクセスレート特性が予め算定ができないメモリアクセスのフローに関しては、実施の形態１に示したようにメモリ側のバス制御装置でアクセスレートの平均値や最大値を実測することで数１１、数１２を計算しても良い。
【０１０７】
設計時特性と実測値のいずれも利用可能である場合には、設計時特性を使用したほうが良い。実測値をベースにした制御では、瞬間的な負荷減少に対して、各バスマスタが集中的に当該メモリへのアクセスフローの割当を行おうとする傾向が強まる。そのため、割当可能なメモリの余剰帯域に比して、過剰なフローを収容する結果となり、直後の負荷上昇とアクセスレイテンシの増大が起こった際に、各バスマスタが再度アクセスフローの割当直しを行わざるを得ない状況に繋がり易い。このような現象は、「ルートフラッピング」として知られており、ネットワークのスループットやアクセスレイテンシを著しく劣化させる。フローの設計時特性をベースに割当制御を行った場合には、瞬間的な負荷状態に依存しない割当量を管理できるため、ルートフラッピングの発生を避けることができる。
【０１０８】
メモリモジュール側のバス制御装置内にある出力監視部１０７において、接続されたメモリへのアクセスレイテンシを計測、管理しても良い。アクセスレイテンシは、プロセッサからのデータ読出あるいは書込要求を示すデータ転送パケットをデータ受信部１０４が受信してから、対応する読出あるいは書込動作が完了する迄に要したサイクル数で表しても良い。データ転送パケットのヘッダに格納された優先度によって規定されるアクセスフローのレイテンシ要求に対して、充分なマージンが確保できていない状態を出力監視部１０７が検出した場合には、要求元のプロセッサのバス制御装置アドレスを受信先アドレスとする出力情報通知を緊急送信することで、アクセス品質の低下をプロセッサ側に通知しても良い。
【０１０９】
（経路負荷検出部１０１）
経路負荷検出部１０１は、プロセッサが平均レートμt、最大レートｐtのメモリアクセスフローを割り当てるためのメモリ領域確保のイベントをトリガとして、出力情報要求パケットを各メモリモジュールのバス制御装置宛に送信する。この出力情報要求パケットにより、図２１に示された評価値を収集する。出力情報を収集するためのプロトコルの例を図２２に示す。フローの時間変動を考慮したｉ番目のメモリの流量評価値βｉは、数１３で表される。式中のｍは同一メモリに割り当てられた複数フロー間の統計多重効果の強さと信頼性をバランスさせるための調整係数である。
【数１３】
2011004566.tif 000015
【０１１０】
また新たな割当対象フローの割当後のｉ番目のメモリの流量評価値β'ｉは、数１４で表される。
【数１４】
2011004566.tif 000016
【０１１１】
割当対象フローをｉ番目のメモリに割り当てた場合の各メモリの流量の状態をＳｉとすると、数１５のようになる。
【数１５】
2011004566.tif 000017
【０１１２】
状態Ｓｉにおけるメモリ間の流量均一性を数１６、数１７で評価しても良い。式中のｎはメモリモジュールの個数を表す。
【数１６】
2011004566.tif 000018
【数１７】
2011004566.tif 000019
【０１１３】
フローの割当対象のメモリモジュールを数１８によって決定することで、フローの時間変動を考慮した統計多重効果が最も期待でき、メモリ間のアクセスレートの均一性を向上させることができる。
【数１８】
2011004566.tif 000020
【０１１４】
経路負荷検出部１０１は、該当するタスクに対してｑ番目のメモリが割り当てられたことを、プロセッサに通知する。プロセッサ上のタスクはメモリへのデータ転送パケット送信時の送信先アドレスをｑ番目のメモリのアドレスとして認識する。
【０１１５】
このように、数１３で示される割当対象フローの割当前の各メモリの流量βｉを比較するのではなく、数１４及び数１５で示すように、仮想的な割当後の各メモリの流量Ｓｉを比較して、実際のフローの割当先のメモリを決定する。これにより、各メモリに対して、既に割当済のフロー群と割当対象のアクセスフローとの関係も考慮することができるため、より適切な割当先メモリを選択できるようになる。例えば、時間変動の激しいアクセスフローを新規に割り当てる状況を考える。割当前の流量は大きかったとしても、時間変動の少ないフロー群を割当済のメモリよりも、時間変動の大きなフロー群を割当済の経路を選択したほうが、統計多重効果によって、割当実施後の帯域利用効率を向上させることができる。仮想的な割当後の均一性を基に割当先メモリを決定することで、このような状況にも対応可能となる。
【０１１６】
またメモリモジュール側のバス制御装置内にある出力監視部１０７が発信する、アクセス品質低下の緊急出力情報通知パケットを受信した経路負荷検出部１０１は、その情報を基に、数１３及び数１４に含まれる調整係数ｍの値を動的に制御する。これにより、アクセス品質に関する信頼性を向上させることができる。経路負荷検出部１０１が管理する調整係数ｍの初期値を数１９で定義する。ｍの初期値は例えば５に設定しておいても良い。
【数１９】
2011004566.tif 000021
【０１１７】
またｍを制御するためのパラメータ変数として、αを数２０で初期化する。初期値は例えば、１に設定しておいても良い。
【数２０】
2011004566.tif 000022
【０１１８】
緊急の出力情報通知パケットの受信によって、アクセス品質の低下を検知した経路負荷検出部１０１は、αの値を数２１に従って変更する。Δαは、事前に定められたＮ回の緊急出力情報通知の受信による正の変化分である。例えば、Ｎの値を１に、Δαの値を０．５に設定しておいても良い。
【数２１】
2011004566.tif 000023
【０１１９】
調整係数ｍの値を、数２２に示すダイナミクスで制御する。式中のｍmax、ｍminは調整係数ｍの事前に決定された最大値及び最小値であり、例えば、７及び５に設定しておいても良い。ｋは調整パラメータであり、例えば１００に設定しておいても良い。δはクロネッカのデルタ関数であり、ηはランダムな正の整数である。
【数２２】
2011004566.tif 000024
【０１２０】
数２２により、調整係数ｍを、数２３のように更新すれば良い。
【数２３】
2011004566.tif 000025
【０１２１】
上述の数式に基づく処理によれば、データが流れにくくなるにつれて、Δｍの値が大きくなるため、ｍの値が大きくなる。
【０１２２】
更新した結果、ｍの値が最大値を超えた場合には、α＝０とすることで、ランダムな調整係数選択を行わせると良い。調整係数ｍの更新が完了した時点で、数２０に従って、再びαの初期化を行えば良い。調整係数ｍを制御することによって、各フローのレート変動特性が想定する確率分布に従わない場合であっても、メモリ割当の均一性と統計多重効果をバランスさせ、フローを収容可能なバスの動作周波数を引き下げる効果が得られる。
【０１２３】
以上、本発明の実施形態を説明した。
【０１２４】
上述の実施形態では、ＮｏＣのトポロジは２次元メッシュ型であるとしたが、これは一例である。本実施形態によるフロー制御は、他のトポロジであっても適用可能である。他のトポロジとして、たとえば２次元トーラス型のトポロジを採用してもよい。また、バスマスタおよび対応するバス制御装置の組をリング状に配置し、隣接するバス制御装置同士、および、リング上対向するバス制御装置同士をバスで接続するトポロジを採用してもよい。さらに２次元型に限られず、バスマスタおよび対応するバス制御装置をダイスタッキングし、バス制御装置を３次元接続するトポロジを採用してもよい。
【０１２５】
（実施形態３）
本実施形態によるバス制御装置は、実施形態２と同様、図２０に示す分散型のメモリ・アーキテクチャに適用することが可能である。図２０に示す分散型のメモリ・アーキテクチャの説明は実施形態２と同じであるため、その説明は省略する。
【０１２６】
本実施形態による分散型メモリネットワークを構成するバス制御装置の構成は、以下に特に説明する点を除いては、図１４に関連して説明した実施形態２によるバス制御装置２の構成と同じである。共通する機能の説明は省略する。
【０１２７】
（経路負荷検出部１０１）
本実施形態では、実施形態２における数１６に代えて、下記数２４を採用してもよい。
【数２４】
2011004566.tif 000026
【０１２８】
流量の均一性を優先指標としたフローの割当対象のメモリモジュールは数２５によって決定される。
【数２５】
2011004566.tif 000027
【０１２９】
一方、割当対象のフローを発生させたプロセッサからみて、最近接に位置するメモリモジュールはｑ０であるとは限らない。ここでいう「最近接に位置するメモリモジュール」（以下「最近接メモリモジュール」と記述する。）とは、設計上、プロセッサから最も低いレイテンシでアクセス可能と想定されるメモリモジュールを意味する。
【０１３０】
図２０の例では、プロセッサＵＰ１１から３つの共有メモリモジュールＭＢＭ３１、ＭＢＭ３２、ＭＢＭ３３へは、それぞれ２ホップ、３ホップ、４ホップとなっている。よって、設計上は、共有メモリモジュールＭＢＭ３１がプロセッサＵＰ１１の最近接メモリモジュールとして定義できる。プロセッサ毎に定義される最近接メモリモジュールの識別子ｑ１は、例えばＳｏＣの設計情報として定義される。当該識別子ｑ１は、予め該当するプロセッサ、または、プロセッサに接続されたＮｏＣルータの経路負荷検出部の内部にハードコードされていても良いし、初期化動作に計測パケットを送受信して選択しても良い。
【０１３１】
数２４で示されるρｉは、メモリモジュールｉに割当対象フローの割当を行った後の均一性を示している。一方、割当を行わない状態での、つまりその時点における実際の均一性を示す指標は、数２６で与えられる。ρは１を越えない正の数である。
【数２６】
2011004566.tif 000028
【０１３２】
また、各メモリモジュール毎の、現在の流量評価値として算出された数１３で示されるβｉを基にして、数２７に示すγを計算できる。式中のｂはバス幅、ｃはバスの動作周波数を表すとすれば、γは、１サイクル時間にアクセスされたフリット数を示し、物理帯域を越えるアクセスが発生していない状況下では、１を越えることはない。γは、各メモリモジュールの中で、最も割当量の大きいメモリモジュールにおける、割当量を示す指標と成り得る。
【数２７】
2011004566.tif 000029
【０１３３】
経路負荷検出部は、ρ及びγの値を基に、フローの割当先のメモリモジュールｑを決定する。最も単純な決定方法の例としては、数２８の条件式に従えば良い。
【数２８】
2011004566.tif 000030
【０１３４】
Γth及びΡthは、閾値であり事前に定義された値を用いれば良い。メモリモジュールへのアクセス量が少なく、メモリモジュール間の均一性が殆ど問題にならない低負荷領域では、フローの割当先として最近接メモリモジュールが選択され、最も近接に位置する低レイテンシな（たとえばレイテンシが最低である）メモリモジュールｑ１が選択される。メモリへの割当フローが増加し、メモリモジュール間のアクセスのばらつきが性能に影響を及ぼす中負荷から高負荷の領域では、流量の均一性を重視してメモリモジュールｑ０が選択される。このように状況に応じて流量の均一性の重みを変更することで、スループットが向上する。
【０１３５】
ｑを決定する際の他の方法として、プロセッサ毎に自律的にｑ０またはｑ１を選択させてもよい。下記数２９は、変数ｍｉのダイナミクスを支配し、式中のηは、ランダムノイズである。数２９、数３０、数３１中のαのダイナミクスは、数３２で制御される。δ、Ｋは定数である。
【数２９】
2011004566.tif 000031
【数３０】
2011004566.tif 000032
【数３１】
2011004566.tif 000033
【数３２】
2011004566.tif 000034
【０１３６】
割当先のメモリモジュールは、数３３の判定式によって決定すれば良い。
【数３３】
2011004566.tif 000035
【０１３７】
これによって、ｑ０とｑ１の選択の切換が、プロセッサ間で自律的かつ段階的に進行するため、利用帯域の無駄がなくなり、スループットが向上する。
【０１３８】
経路負荷検出部１０１は、該当するタスクに対してｑ番目のメモリモジュールが割り当てられたことを、プロセッサに通知する。プロセッサ上のタスクはメモリモジュールへのデータ転送パケット送信時の送信先アドレスをｑ番目のメモリモジュールのアドレスとして認識する。
【０１３９】
図２３は、本実施形態にかかるバス制御装置の性能評価をＮｏＣのシミュレータを用いて行った結果を示す。この結果は、数３２において、Kγ＝Kρ＝１００、Γth＝０．５、Ρth＝０．７５としたときのαのプロファイルを示している。γ及びρが閉区間［０，１］を動く場合に、αは閉区間［０．５，１．０］の範囲を変動することが分かる。
【０１４０】
図２４は、数２９において、ηｉを閉区間［−０．０５，  ＋０．０５］の範囲で変動する一様分布に従うランダムノイズとしたときの、ｍ１及びｍ２の時間変化を示す。横軸は時間軸を示している。αの変化に従って、ｍ１とｍ２の大小関係が変化していることが分かる。数３３に従って、ｍ１がｍ２より下にある場合にはｑ０が選択され、ｍ１がｍ２より上にある場合にはｑ１が選択される。常にｍ１、ｍ２の符号が負にならないように、ηｉによって負数に振れたときは、強制的に０とする数値処理が入っている。
【０１４１】
時刻［５００，１０００］及び時刻［２０００，２５００］の範囲では、α＝１．０に伴い、ｍ２がｍ１より大きくなり、均一性による割当先の選択が行われている。一方、時刻［１５００，１７００］ではこのような変化はなく、レイテンシを重視した最近接割当を維持している。これにより、他のプロセッサの変化によるαの低下によって、最近接割当を継続していることが分かる。
【０１４２】
この方法によれば、全てのプロセッサが一斉に割当先を変更することによって、一部のメモリモジュールにアクセスピークが発生することを回避することが可能となり、過渡時の性能を悪化させることなく、流量の均一性とレイテンシを重視した割当方法の切換動作を徐々に進行させることができる。
【０１４３】
図２５は、シミュレーションに用いたＮｏＣの構成を示す図である。５個のプロセッサＵＰ１１〜ＵＰ１５、および、３個のメモリモジュールＭＥＭ５１、ＭＥＭ５３、ＭＥＭ５５が接続された５ｘ５の正方メッシュトポロジーのＮｏＣで構成される。
【０１４４】
プロセッサＵＰからは、一定サイクル毎に１パケットのデータをメモリモジュールＭＥＭに対して送信するフローを発生させた。パケット長は４フリットに固定である。また各プロセッサＵＰから２０本のフローを発生させ、各フローの発生するデータ量を、１倍フローが５本、１０倍フローが５本、１００倍フローが１０本となるようにした。「１０倍フロー」とは、１００倍フローが１０パケット送信する間に１パケットを送信するフローであり、「１倍フロー」とは１０倍フローが１０パケット送信する間に１パケットを送信するフローを意味する。１倍フローのパケット送信間隔は、１０倍フローの１０倍であり、１０倍フローのパケット送信間隔は、１００倍フローの１０倍である。
【０１４５】
またルーティングプロトコルは、ＸＹ次元順ルーティングを用い、スイッチングプロトコルは、ワームホールスイッチングとし、ルータの構成は、仮想チャンネル数４、仮想チャンネルサイズ４とした。フローの送信開始のタイミングは数サイクルずつずらし、メッシュネットワーク入り口での輻輳は発生しないように配慮した。図２６および図２７は、本願発明者らがシミュレーションデータからまとめた、メモリモジュール側でのスループットとレイテンシとの関係を示す。横軸に示すスループットは、各メモリモジュールＭＥＭ５１、ＭＥＭ５３、ＭＥＭ５５の単独のスループットの総和である。各メモリモジュールの単独のスループットは、シミュレーション時間内に受信したフリット数をシミュレーション時間内の全サイクル数毎で除した値として得られる。シミュレーション中に全くフリットを受信しなかった場合は０であり、絶えずフリットを受信した場合は１となる。また１サイクルおきに１フリットを受信した場合には、０．５となる。
【０１４６】
図２５に示す例ではメモリモジュールは３個存在するため、スループットの最大値は３である。縦軸に示すレイテンシは、プロセッサでフリットを生成した時点のタイムスタンプ値とメモリモジュール側でフリットを受信した時点のタイムスタンプ値との差である。１つのパケットを構成する４つのフリットの生成時のタイムスタンプは全て同じ値である。
【０１４７】
図２６は、４０００サイクルに渡るシミュレーション結果のグラフである。このグラフにより、割当方式の相違による性能を比較することが可能である。「均一割当」を表すラインは、αの値に拘わらず、常にｑ０を選択しつづけた結果を示している。「選択割当」を表すラインは、αの値によって、ｑ０とｑ１の選択を行った結果を示す。いずれの場合でも、飽和スループットとして、２．７程度の性能が出ていることが確認できる。このシミュレーションにおける利用可能な物理帯域は３．０であるため、物理帯域の約９０％のスループットを利用可能となっている。
【０１４８】
また図２７は、同一のシミュレーションにおいて、低負荷領域におけるスループットとレイテンシとの関係に着目した結果を示す。このグラフにより、低負荷領域における割当方式の相違による性能を比較することが可能である。ｑ０とｑ１を切り換えることにより、常にｑ０のみを選択した場合と比べ、レイテンシが５サイクル程度向上している。割当時の選択を行ったほうが、低負荷の状態も含めてスループットとレイテンシの特性を改善できていることが分かる。
【０１４９】
上述の実施形態では、ＮｏＣのトポロジは２次元メッシュ型であるとしたが、これは一例である。本実施形態によるフロー制御は、他のトポロジであっても適用可能である。他のトポロジとして、たとえば２次元トーラス型のトポロジを採用してもよい。また、バスマスタおよび対応するバス制御装置の組をリング状に配置し、隣接するバス制御装置同士、および、リング上対向するバス制御装置同士をバスで接続するトポロジを採用してもよい。さらに２次元型に限られず、バスマスタおよび対応するバス制御装置をダイスタッキングし、バス制御装置を３次元接続するトポロジを採用してもよい。
【０１５０】
（実施形態４）
上述の実施形態では、本願発明がチップ上で実装された際の構成を説明した。
【０１５１】
本願発明は、チップ上に実装されるだけでなく、チップ上に実装するための設計及び検証を行うシミュレーションプログラムとしても実施される。そのようなシミュレーションプログラムは、コンピュータによって実行される。本実施形態においては、図１４に示される各構成要素は、シミュレーションプログラム上のオブジェクト化されたクラスとして実装される。各クラスは、予め定められたシミュレーションシナリオを読み込むことにより、上述した実施形態の各構成要素に対応する動作をコンピュータ上で実現する。言い換えると、各構成要素に対応する動作は、コンピュータの処理ステップとして直列的または並列的に実行される。
【０１５２】
バスマスタとして実装されたクラスは、シミュレータで定義されたシミュレーションシナリオを読み込むことにより、バス制御装置のクラスにパケットを仮想的に送信するタイミング等の条件を決定する。そして、図１３で示される各経路での送信状態をシミュレーションし、実施の形態１、２と同様に送信状態を比較することで、送信経路を決定する動作を行う。
【０１５３】
バスマスタとして実装されたクラスは、シミュレーションシナリオに記述されたシミュレーションの終了条件が成立する迄の間、動作を行い、動作中のスループットやレイテンシ、バスの流量の変動の様子、動作周波数、消費電力の見積値等を算出しプログラムの利用者に提供する。これらに基づき、プログラムの利用者はトポロジーや性能の評価を行い、設計及び検証を行う。
【０１５４】
例えばシミュレーションシナリオの各行には、送信元バスマスタのＩＤ、宛先バスマスタのＩＤ、送信するパケットのサイズ、送信するタイミング等の情報が記述されるのが普通である。また複数のシミュレーションシナリオをバッチ処理的に評価することで、想定した全てのシナリオで所望の性能が保証できているか否かを効率的に検証できる。またバスのトポロジーやノード数、プロセッサやＤＳＰ、メモリ、周辺ＩＯの配置を変化させて性能比較することにより、シミュレーションシナリオに最も適したネットワーク構成を特定することもできる。実施形態１から３のいずれもが本態様の設計及び検証ツールとしても適用可能である。本願発明は、設計及び検証ツールとして実施される際にも適用可能である。
【産業上の利用可能性】
【０１５５】
本発明は、組込機器向けのＳｏＣにおけるオンチップバスや、汎用プロセッサ、ＤＳＰ上のローカルバスにおける、データ転送経路の制御技術を備えたネットワークバス制御装置、制御方法、制御プログラムに利用可能である。
【符号の説明】
【０１５６】
１０１  経路負荷検出部
１０２  経路決定部
１０３  パケット構成部
１０４  データ受信部
１０５  ヘッダ解析部
１０６  データ出力部
１０７  出力監視部
【図１】
2011004566.tif 000036
【図２】
2011004566.tif 000037
【図３】
2011004566.tif 000038
【図４】
2011004566.tif 000039
【図５】
2011004566.tif 000040
【図６】
2011004566.tif 000041
【図７】
2011004566.tif 000042
【図８】
2011004566.tif 000043
【図９】
2011004566.tif 000044
【図１０】
2011004566.tif 000045
【図１１】
2011004566.tif 000046
【図１２】
2011004566.tif 000047
【図１３】
2011004566.tif 000048
【図１４】
2011004566.tif 000049
【図１５】
2011004566.tif 000050
【図１６】
2011004566.tif 000051
【図１７】
2011004566.tif 000052
【図１８】
2011004566.tif 000053
【図１９】
2011004566.tif 000054
【図２０】
2011004566.tif 000055
【図２１】
2011004566.tif 000056
【図２２】
2011004566.tif 000057
【図２３】
2011004566.tif 000058
【図２４】
2011004566.tif 000059
【図２５】
2011004566.tif 000060
【図２６】
2011004566.tif 000061
【図２７】
2011004566.tif 000062
【手続補正書】
【提出日】平成23年5月24日(2011.5.24)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク化された通信バスを備える半導体チップにおいて、通信バスの制御を行うための装置、方法及びプログラムに関する。
【背景技術】
【０００２】
近年、ＳｏＣ（Ｓｙｓｔｅｍ  ｏｎ  Ｃｈｉｐ）が利用される組込機器分野や汎用プロセッサ分野において、半導体チップの高機能化への要求が高まっている。半導体チップの高機能化に伴い、チップ上の通信バスに接続されるバスマスタ数が増加し、バス上を流れる転送データのトラフィック制御が複雑化してきた。
【０００３】
たとえば、近年の携帯電話端末は、電子メール送受信、ウェブブラウジング、「ワンセグ」と呼ばれる地上波デジタル放送の受信などが可能であり、多機能化が進んでいる。各機能に対応する一部または全部の処理を行う専用ＩＣはバスマスタとして機能するため、それらを接続する通信バス上のデータのトラフィックを適切に制御する必要がある。また、マイクロプロセッサ（ＭＰＵ）チップにおいてもマルチコア化が進んでいる。バスマスタとして機能する各プロセッサコアを同期させ、協調させるためには、各プロセッサコアを接続する通信バス上のデータのトラフィックを適切に制御する必要がある。
【０００４】
トラフィック制御に関する従来の設計方法として、各バスマスタを広帯域な集中型のバスで相互に接続し、クロスバースイッチを切り換えることで、データ転送対象のバスマスタ対にバスの利用権を割り当てるバス制御方式が用いられてきた。しかしながら、このバス制御方式では、バス配線の引き回しによる配線遅延の増加や、クロスバースイッチの面積の増加、消費電力の増加等が問題となっている。また、集中型のバス設計では、平均的なバスの利用効率が向上せず、バスの動作周波数も高くなり、バス部分の消費電力が増加してしまうという問題点も存在する。その理由は、各バスマスタが要求する最大データ転送量を保証するようにバスの動作周波数が設計されるためである。
【０００５】
集中型バスの問題点を解決するために、ＮｏＣ（Ｎｅｔｗｏｒｋ  ｏｎ  Ｃｈｉｐ）と呼ばれる通信バスのネットワーク化が進みつつある。
【０００６】
たとえば図１（ａ）および（ｂ）は、ＮｏＣバスの一部の構成を示す。図１（ａ）はハードウェア接続構成例を示す図であり、図１（ｂ）はその模式図である。図１（ａ）および（ｂ）によれば、チップ１０上に設けられたバスマスタ１ａ〜１ｃが、それぞれバス制御装置（Ｒ）２を介してバス３に接続されていることが示されている。なお、以下の本願図面のＮｏＣバスは、図１（ｂ）に示す模式図で記載する。
【０００７】
図２は、２次元メッシュ型でバスマスタを結合したＮｏＣバスの構成例を示す。マイクロプロセッサやＤＳＰ、メモリ、入出力回路等のバスマスタ毎に、データ転送経路の制御を行うバス制御装置Ｒが配置され、バス制御装置Ｒ間を短配線で接続（リンク）する。
【０００８】
このような構成では、送信元のバスマスタから、受信先のバスマスタに対してデータ転送を行うための通信経路が複数存在する。たとえば図３は、送信元から送信先までの３本の経路（１）〜（３）を示す。
【０００９】
また、同等機能を提供するバスマスタが複数存在する場合には、受信先及び受信先に至る経路が複数存在する。たとえば図４は、１つの送信元から３つの送信先（１）〜（３）までの各経路を示す。
【００１０】
複数の選択候補経路の中から、バスの負荷状況に合わせて、最適な経路を選択することで、チップ全体のデータ転送遅延時間（レイテンシ）やバスの動作周波数を低減することが可能となる。そのため、ＮｏＣバスの性能を最大限引き出すことのできる複数経路制御技術が必要となる。
【００１１】
複数のバスマスタを相互に接続するバス上で、複数のデータ転送経路をバスの状態に合わせて選択する方法が特許文献１に開示されている。特許文献１の技術によれば、送信元のバスマスタから受信先のバスマスタ迄、転送対象のデータをフレーム単位で転送する。受信先でフレームが正常に受信された場合には、アクノリッジデータを返信し、そうでない場合にはアクノリッジデータを返信しない。送信元のバスマスタはアクノリッジデータの返信がなかったことをもって、フレーム転送の不具合を検出し、他の送信経路を選択してフレームを再送信する。これにより、通信を継続することを可能としている。受信したフレームのヘッダにエラーが検出された場合には、受信先のバスマスタでフレームが破棄されるため、送信元のバスマスタがアクノリッジデータを受信することはない。また利用中のデータ転送経路において、フレームの転送遅延が大きくなり、規定時間内にフレームが受信先に着信しない場合にも、送信元のバスマスタは規定時間内にアクノリッジデータを受信することができない。このときも、経路の切換が発生する。データ転送経路の状態に合わせて経路がダイナミックに切り換えられることにより、転送遅延やエラーが少ない経路で通信することが可能となる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特許第３８１６５３１号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１３】
従来から知られている複数経路制御技術を用いる場合、送信元のバスマスタは、転送遅延時間やエラー発生状況等を評価指標として、自らのデータ転送の状態が最良となるような利己的な経路の選択を行う。
【００１４】
その結果、バスマスタ間を接続するバス（リンク）間を流れる転送データの流量に偏りが生じることがある。その理由は、ＮｏＣに存在する複数のバスマスタが競合して最良経路を選択しようとすることで、データ転送経路及びリンク資源の奪い合いが生じ、いくつかのリンクに複数の送信元からのデータ転送が集中するためである。
【００１５】
この偏りによって３つの課題が発生する。
【００１６】
第一の課題は、流量の大きなリンクにおいて、リンク両端のバス制御装置の動作負荷が高くなり、データ転送のレイテンシが増加することである。バスマスタ間のデータ転送のレイテンシはバスマスタの動作速度を律速し、例えばプロセッサとメモリ間のデータ転送の場合には、メモリアクセスレイテンシに対応したプロセッサのウエイトサイクル増大による処理性能低下に繋がる。
【００１７】
第二の課題は、流量の大きなリンクに合わせてバスの動作周波数をより高く設計する必要が生じることである。バスの動作周波数が高速になるにつれ、配線遅延やクロストークの制御が困難となり、設計工数や検証工数が増大する。
【００１８】
第三の課題は、バスの動作周波数が高くなるほど、リンクの消費電力が増加することである。リンクを構成するトランジスタの消費電力Ｐは、スイッチングレートα、回路の容量Ｃ、電源電圧Ｖ、動作周波数ｆとすると、数１で表される。
【数１】
2011004566.tif 000063
【００１９】
また、動作周波数を抑えることにより、電源電圧も数２に示す関係で低減することが可能となる。
【数２】
2011004566.tif 000064
【００２０】
数２中のηはトランジスタの動作スレッショルド電圧と電源電圧の比であり、γはプロセスルールに依存する定数である。例えばγ＝２とした場合、動作周波数の低減は、３乗のオーダーで消費電力に寄与するため、流量の偏りによっては、高い転送レートを収容するためのリンクの消費電力は非常に大きくなる。
【００２１】
本発明は、上記課題を解決するためになされたものであり、その目的は、リンク間のデータ流量の偏りをなくすことが可能なバス制御装置を提供することにある。
【課題を解決するための手段】
【００２２】
本発明によるバス制御装置は、バスマスタと、ネットワーク化された通信バスとの間に設けられ、前記通信バスに流れるパケットの送信経路を制御するバス制御装置であって、利用可能な複数の送信経路上に存在する複数の他のバス制御装置から、出力状況に関する情報を受信するデータ受信部と、前記出力状況に関する情報に基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出する経路負荷検出部と、前記均一化指標に基づいて、前記送信流量が調整された複数の送信経路を決定する経路決定部と、前記バスマスタから受け取ったデータに基づいてパケットを生成するパケット構成部と、各々が異なる通信バスに接続された複数の出力ポートのいずれか一つから前記パケットを出力するデータ出力部と、前記複数の出力ポートの中から、前記パケットの送信先の情報に基づいて選択された送信経路の一つに接続されている出力ポートを決定するヘッダ解析部とを備えている。
【００２３】
前記バス制御装置は、前記複数の他のバス制御装置からの要求に従って、前記データ出力部のデータ出力状況に関する情報を通知する出力監視部をさらに備えていてもよい。
【００２４】
前記経路負荷検出部は、出力するフローの優先度毎の転送頻度の平均値を少なくとも含む、前記出力監視部からの出力状況の中で前記平均値を基に均一化指標を算出してもよい。
【００２５】
前記経路負荷検出部は、出力するフローの優先度毎の転送頻度の平均値および最大値を少なくとも含む、前記出力監視部からの出力状況の中で前記平均値および最大値に基づいて均一化指標を算出してもよい。
【００２６】
前記経路負荷検出部は、均一化指標に含まれる統計多重効果に起因する評価値の信頼度を規定するパラメータを含んでいてもよい。
【００２７】
前記経路負荷検出部は、前記パケットの転送状況の劣化を検出して、前記信頼度を規定するパラメータを調整し、前記パラメータの調整で転送状況が改善しない場合には、確率的にパラメータを調整してもよい。
【００２８】
前記出力監視部は、予め定められたタイミングで発行される前記出力状況に関する情報の要求の受信をトリガとして、前記情報を通知してもよい。
【００２９】
前記経路負荷検出部は、事前に出力状況通知の送信条件を出力監視部に伝達し、前記出力監視部には、予め前記出力状況に関する情報の要求が送信される条件が通知されており、前記送信条件が成立した場合には前記情報を通知してもよい。
【００３０】
前記経路負荷検出部は、前記出力状況に関する情報に対して、前記各送信経路のフローの優先度に応じた重みを加えることにより、前記各送信経路の送信流量に関する評価値を算出し、各送信経路の送信流量のばらつきを示す均一化指標を算出してもよい。
【００３１】
前記経路負荷検出部は、前記各送信経路の送信流量に関する評価値を利用して統計値を算出し、前記統計値を利用して前記各送信経路間の関係が均一か否かを判断してもよい。
【００３２】
前記経路負荷検出部は、前記出力状況に関する情報と選択対象の送信経路のデータ特性に関する情報とに基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出してもよい。
【００３３】
本発明によるシミュレーションプログラムは、バスマスタと、ネットワーク化された通信バスとの間に設けられ、前記通信バスに流れるパケットの送信経路を制御するバス制御装置のためのシミュレーションプログラムであって、前記シミュレーションプログラムは、コンピュータに対し、前記シミュレーションプログラム上のオブジェクト化された複数の他のバス制御装置のクラスであって、利用可能な複数の送信経路上に存在する複数の他のバス制御装置のクラスから、出力状況に関する情報を受信するステップと、前記出力状況に関する情報に基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出するステップと、前記均一化指標に基づいて、前記送信流量が調整された複数の送信経路を決定するステップと、前記バスマスタとして実装されたクラスから受け取ったデータに基づいてパケットを生成するステップと、各々が異なる通信バスに接続された複数の出力ポートのいずれか一つから前記パケットを出力するステップと、前記複数の出力ポートの中から、前記パケットの送信先の情報に基づいて選択された送信経路の一つに接続されている出力ポートを決定するステップと、前記決定された出力ポートから前記パケットを出力するステップとを実行させる。
【発明の効果】
【００３４】
本発明によれば、バス制御装置は、利用可能な複数の送信経路上の他のバス制御装置に対して出力状況の監視を行い、各送信経路間の送信流量のばらつきである均一化指標に基づいてデータの送信経路を切り換える。これにより、ＮｏＣバスを構成するリンク間の流量の偏りが自動的に抑制されるため、データ転送負荷がバス全体で均一化され、特定リンクへの負荷集中による通信遅延時間、レイテンシの増加が抑えられる。
【００３５】
また、リンクの動作周波数が低減されるので、バス設計を容易にし、データ転送時のバスの消費電力を削減することが可能となる。またリンクの動作周波数の動的制御技術と組み合わせることにより、バスの消費電力を更に効率的に削減することが可能となる。
【００３６】
また、同等機能を提供するバスマスタへの経路負荷を、統計多重効果を考慮した上で均一化することにより、バスマスタの負荷分散効果も得られる。このため、分散型のメモリ・アーキテクチャに本発明を適用することにより、メモリアクセスの許容レイテンシに対する信頼性を確保した上で、アクセス集中によるボトルネックを回避することが可能となる。
【図面の簡単な説明】
【００３７】
【図１】（ａ）はハードウェア接続構成例を示す図であり、（ｂ）はその模式図である。
【図２】２次元メッシュ型でバスマスタを結合したＮｏＣバスの構成例を示す図である。
【図３】送信元から受信先までの３本の経路（１）〜（３）を示す図である。
【図４】１つの送信元から３つの受信先（１）〜（３）までの各経路を示す図である。
【図５】携帯電話端末に搭載されるシステム半導体をＮｏＣバスを用いて構成した例を示す図である。
【図６】（ａ）はワンセグＴＶ視聴のアプリケーションにおけるデータ転送経路を示す図であり、（ｂ）は携帯電話用フルブラウザのネットワーク通信用スレッドにおけるデータ転送経路を示す図であり、（ｃ）はネットワークゲームのクライアントプログラムが遠隔のサーバーと通信する際のデータ転送経路を示す図である。
【図７】送信元Ｍ２１から受信先Ｍ２４へデータ転送を行う場合に、利用可能な３本の選択候補経路が定義されていることを示す図である。
【図８】データ転送処理Ｂ，Ｃ，Ｄが同時に発生している状態でのバスマスタＭ２１−Ｍ２４間での選択候補経路毎のデータ転送量を示す図である。
【図９】動画再生時のデータ転送経路を示す図である。
【図１０】チップ上で複数のデータ転送処理が同時的に発生している状態を示す図である。
【図１１】図８に対して、データ転送Ａが新たに追加された状態を示す図である。
【図１２】実施形態１によるデータ転送量の調整結果を示す図である。
【図１３】リンク間の経路流量の偏りをなくし、均一化を行うための動作詳細を説明するための部分経路図を示す図である。
【図１４】本発明の実施形態によるバス制御装置２の構成を示す図である。
【図１５】パケットの構成例を示す図である。
【図１６】出力情報通知パケットのペイロードに記述される情報の例を示す図である。
【図１７】バス制御装置Ｒ２１がバスマスタＭ２４に至る経路（２）上の出力情報を収集する際のプロトコルの例を示す図である。
【図１８】経路負荷検出部１０１の以上の処理の流れを示す図である。
【図１９】バス制御装置Ｒ２１の経路決定部１０２が管理する経路表の例を示す図である。
【図２０】分散型のメモリ・アーキテクチャに本発明を適用した構成の例を示す図である。
【図２１】出力情報の例を示す図である。
【図２２】出力情報を収集するためのプロトコルの例を示す図である。
【図２３】実施形態３のバス制御装置の性能評価をＮｏＣのシミュレータを用いて行った結果を示す図である。
【図２４】数２９において、ηiを閉区間［−０．０５，  ＋０．０５］の範囲で変動する一様分布に従うランダムノイズとしたときの、ｍ１及びｍ２の時間変化を示す図である。
【図２５】シミュレーションに用いたＮｏＣの構成を示す図である。
【図２６】メモリモジュール側でのスループットとレイテンシとの関係を示す図である。
【図２７】メモリモジュール側でのスループットとレイテンシとの関係を示す図である。
【発明を実施するための形態】
【００３８】
以下、添付の図面を参照しながら、本発明によるバス制御装置の実施形態を説明する。
【００３９】
（実施形態１）
本実施形態によるバス制御装置を具体的に説明するに先立って、ＮｏＣ（Ｎｅｔｗｏｒｋ  ｏｎ  Ｃｈｉｐ）と呼ばれる通信バス、その通信バスで利用可能な送信経路、および、各送信経路におけるデータ転送量を説明する。併せて本実施形態によるバス制御装置の動作原理を説明する。
【００４０】
図５は、携帯電話端末に搭載されるシステム半導体を、ＮｏＣバスを用いて構成した例である。図面の記載形式は、図１（ｂ）に準じている。なお、図中には各バス制御装置Ｒと１対１でバスマスタが接続されているが、バスマスタが接続されておらず中継処理のみを行うバス制御装置が混在していても良い。
【００４１】
バス制御装置Ｒにバスマスタが接続されている場合には、各バスマスタに対して一意のアドレスが付与されるが、バスマスタが接続されていない場合には、バス制御装置に対して仮想的な一意のアドレスを付与すればよい。本明細書では、いずれの場合もバスマスタアドレスと表現する。
【００４２】
携帯電話端末は、本来的な機能としての音声通話に加えて、電子メールやＷｅｂブラウジング、ワンセグＴＶの視聴、ネットワークを利用したゲームなどの、豊富な機能が要求される典型的な例と考えられる。図６（ａ）はワンセグＴＶ視聴のアプリケーションにおけるデータ転送経路を示す。バスマスタＭ１１を送信元、バスマスタＭ１４を受信先とするデータ転送処理Ｂが矢印に示された経路で行われている。また図６（ｂ）は携帯電話用フルブラウザのネットワーク通信用スレッドにおけるデータ転送経路を示す。バスマスタＭ２１を送信元、バスマスタＭ２４を受信先とするデータ転送処理Ｃが矢印に示された経路で行われていることを示す。また図６（ｃ）はネットワークゲームのクライアントプログラムが遠隔のサーバーと通信する際のデータ転送経路を示す。バスマスタＭ２３を送信元、バスマスタＭ３４を受信先とするデータ転送処理Ｄが矢印に示された経路で行われていることを示す。
【００４３】
図６（ａ）、（ｂ）および（ｃ）中のデータ転送処理Ｂ，ＣおよびＤは、マルチスレッド型のＯＳや並列処理構成のハードウェアにより、同時並行的に実行されるものである。
【００４４】
図７は、送信元Ｍ２１から受信先Ｍ２４へデータ転送を行う場合に、利用可能な３本の選択候補経路が定義されていることを示している。以下、それぞれの選択候補経路を経路（１）、経路（２）、経路（３）と表現する。
【００４５】
図８は、データ転送処理Ｂ，Ｃ，Ｄが同時に発生している状態でのバスマスタＭ２１−Ｍ２４間での選択候補経路毎のデータ転送量を示している。経路のデータ転送量は、経路上の各リンクのデータ転送量の最大値としても良い。例えば、図６（ｃ）に示すバス制御装置Ｒ３３−Ｒ３４間のリンクのデータ転送量が、経路（３）上の他の各リンクのデータ転送量よりも大きい場合には、経路（３）のデータ転送量は、Ｒ３３−Ｒ３４間のリンクのデータ転送量として定義される。
【００４６】
たとえば、ユーザが携帯電話の画面上のフルブラウザアプリケーションを操作し、動画サイトへのアクセスを行い、動画コンテンツの再生を指示したとする。このとき、動画再生用のスレッドが起動される。図９は、動画再生時のデータ転送経路を示す。図９に示すように、バスマスタＭ１２を送信元、バスマスタＭ２３を受信先とするデータ転送処理Ａが矢印に示された経路で開始される。
【００４７】
いま、図８のデータ転送処理Ｂ、ＣおよびＤが存在している状況下で、上述のデータ転送処理Ａが追加されたと仮定する。
【００４８】
図１０は、チップ上で複数のデータ転送処理が同時的に発生している状態を示す。そして図１１は、図８に対して、データ転送Ａが新たに追加された状態を示す。図１１によれば、動画再生用スレッドのデータ転送経路として、図８において最もデータ転送量の少ない経路（２）が選択されている。
【００４９】
しかしながら、図１０に示すように、バス制御装置Ｒ２２とＲ２３との間のリンクには、データ転送処理ＡおよびＣが競合している。バス制御装置Ｒ２２とＲ２３との間のリンクでは、データ転送処理ＡおよびＣが並列的に行われる。よって、データ転送量が多くなるため、動作周波数を高くせざるを得ない。その結果、図１１に示すように、結果として３本の経路のデータ転送量が不均一な状態となっている。リンクの動作周波数が図１１に示す点線のレベルにある場合には、経路（２）は高負荷な状態であり、リンクの消費するエネルギーも大きい。
【００５０】
そこで、本実施形態では、複数経路のデータ転送量が均一になるように、データ転送量を調整する。たとえば図１２は、本実施形態によるデータ転送量の調整結果を示す。図１２に示すように、３本の経路のデータ転送量を均一な状態になるように制御することによって、より低い動作周波数でデータ転送を行うことが可能となり、消費電力も低減できる。
【００５１】
図１３は、リンク間の経路流量の偏りをなくし、均一化を行うための動作詳細を説明するための部分経路図を示す。説明を簡略化するため、図１０の一部分を取り出して記載している。システム半導体全体の構成は図１０に示された通りである。図１３に描かれていない配線やバスマスタ、バス制御装置は、省略されているだけであり、図１０に示された通り存在する。
【００５２】
送信元のバスマスタＭ２１に接続されたバス制御装置Ｒ２１は、データ転送対象であるバスマスタＭ２４を受信先とする予め定義された３本の経路（１）、経路（２）、経路（３）に対して、経路負荷状況を収集する。経路負荷状況は、各バス制御装置が管理する出力情報を収集することによって行われる。各経路の出力情報の収集が完了すると、バス制御装置Ｒ２１は、各経路の流量評価値を算出し比較することによって、経路の均一性を評価する。不均一な状態となっている場合には、バス制御装置Ｒ２１は、最も均一性が高くなる経路にデータ転送経路を切り換えることで、データ転送に偏りが発生することを防ぎ、バス全体に転送データを分散するように制御する。
【００５３】
以下、図１４を参照しながら、この動作を行うためのバス制御装置の構成例を説明する。
【００５４】
図１４は、本実施形態によるバス制御装置２の構成を示す。
【００５５】
バス制御装置２は、経路負荷検出部１０１と、経路決定部１０２と、パケット構成部１０３と、データ受信部１０４と、ヘッダ解析部１０５と、データ出力部１０６と、出力監視部１０７とを備えている。以下、各構成要素の機能を説明する。
【００５６】
（パケット構成部１０３）
ネットワーク化されたＮｏＣバス上のデータ転送は、パケットの単位で行われる。パケット構成部１０３は、自身に接続されたバスマスタから受け取ったデータに基づいてパケットを生成する。
【００５７】
図１５はパケットの構成例を示す。パケットはヘッダ、バスマスタ間で交換するためのデータの実体であるペイロード、誤り検出符号等を格納するトレイラーによって構成される。このうち、ペイロードやトレイラーは必須ではない。
【００５８】
ヘッダは、以下の情報を含んでいる。ただし、受信先のバスマスタのアドレス以外は必須ではない。
・プロトコル種別
・受信先のバスマスタとバス制御装置に割り当てられたアドレス
・送信元のバスマスタとバス制御装置に割り当てられたアドレス
・同一アプリケーションまたは同一目的の一連のパケット群に割り当てられるラベル情報
・同一ラベル情報を持つパケット群に対して一意であり送信時刻順に割り当てられる番号情報であるパケット連番
・パケットが転送時に許容するレイテンシのレベルである優先度
・付加情報、および、
・後続するペイロードの有無やペイロードの長さを示すペイロード長
【００５９】
なお、プロトコル種別は、そのパケットがバスマスタ間でのデータ転送目的であるか、経路負荷検出を目的とした出力情報の要求であるか、通知であるかを示す識別コードである。以下では、それぞれの種別のパケットを、「転送データパケット」、「出力情報要求パケット」、および、「出力情報通知パケット」という。
【００６０】
パケット構成部１０３は、自身に接続されたバスマスタから発せられたデータ転送要求に従い、図１５に示すフォーマットに準拠して転送データパケットを構成し、ヘッダ解析部１０５に送る。
【００６１】
またパケット構成部１０３は、経路負荷検出部１０１から発せられた出力情報収集要求に従い、図１５に示すフォーマットに準拠して出力情報要求パケットを構成し、ヘッダ解析部１０５に送る。またパケット構成部１０３は、出力監視部１０７から発せられた出力情報通知要求に従い、図１５に示すフォーマットに準拠して出力情報通知パケットを構成し、ヘッダ解析部１０５に送る。
【００６２】
（データ受信部１０４）
データ受信部１０４は、自身が接続された単数または複数の入力リンクから、転送データパケットや出力情報通知パケットを受信し、ヘッダ解析部１０５に送る。図１４では入力ポートはＥ、Ｗ、Ｓ、Ｎの４本を記載しているが、１本以上であれば何本でも良い。各入力ポートは、異なる他のバス制御装置の出力ポートに接続される。
【００６３】
（ヘッダ解析部１０５）
ヘッダ解析部１０５は、データ受信部１０４によって渡されたパケットのプロトコル種別を照合し、パケットの種別を特定する。本実施形態では、パケットは、転送データパケット、出力情報要求パケット、または、出力情報通知パケットのいずれかであるとしている。
【００６４】
パケットの種別が転送データパケットである場合には、ヘッダ解析部１０５は、受信先のバスマスタを示すアドレス（受信先アドレス）を参照する。その結果、受信先が、自身が接続されたバスマスタへのパケットである場合には、ヘッダ解析部１０５はペイロード部分を抽出してバスマスタに送る。また、受信先が、自身が接続されたバスマスタへのパケットでない場合には、ヘッダ解析部１０５は受信先バスマスタのアドレスを経路決定部１０２に提示し、パケットを出力すべき出力ポートを決定する。
【００６５】
次に、パケットの種別が出力情報要求パケットである場合には、ヘッダ解析部１０５は、受信先アドレスを参照する。その結果、受信先が、自身が接続されたバスマスタへのパケットである場合には、ヘッダ解析部１０５は出力監視部１０７に出力情報の通知を要請し、パケットヘッダに格納されていた送信元のバスマスタアドレス（送信元アドレス）を提示する。また、受信先が、自身が接続されたバスマスタへのパケットでない場合には、ヘッダ解析部１０５は受信先バスマスタのアドレスを経路決定部１０２に提示し、パケットを出力すべき出力ポートの通知を受け取る。それにより、ヘッダ解析部１０５は出力ポートを選択する。なお、パケット構成部１０３が経路決定部１０２から選択候補経路のリスト及びホップリストを受け取っている場合には、それらに基づいて、パケットを出力すべき出力ポートを選択してもよい。
【００６６】
一方、パケットの種別が出力情報通知パケットである場合にも、ヘッダ解析部１０５は、受信先バスマスタアドレスを参照する。その結果、受信先が、自身が接続されたバスマスタへのパケットである場合には、ヘッダ解析部１０５は経路負荷検出部１０１にパケットヘッダに格納された送信元のバスマスタアドレスとペイロードに格納された出力情報を送る。一方、受信先が、自身が接続されたバスマスタへのパケットでない場合には、ヘッダ解析部１０５は受信先バスマスタのアドレスを経路決定部１０２に提示し、経路決定部１０２から通知されたポートを、パケットを出力すべき出力ポートとして決定する。
【００６７】
（データ出力部１０６）
データ出力部１０６は、ヘッダ解析部１０５によって提示された出力ポートへの配線の切換を行い、パケットを信号としてバス上に送出する。また経路の輻輳によって、データ転送パケットの送出遅延が発生した場合には、データ出力部１０６は、優先度の低いデータ転送パケットの転送を遅延させることで、優先度の高いデータ転送パケットから順に優先転送を行う。
【００６８】
（出力監視部１０７）
出力監視部１０７は、ヘッダ解析部１０５から受けた出力情報通知要請に応答するために、データ出力部１０６の各出力ポートの状態監視を行う。各出力ポートには、複数のバスマスタが送出したデータ転送パケットが混在して出力されており、同一のラベル情報を持つデータ転送パケットは同一のフローであると識別することができる。
【００６９】
ここで「フロー」とは、アプリケーションやタスクの実行等の同一目的のために、送信元バスマスタから受信先バスマスタに送信される一連のデータ転送パケット群を指し、フロー毎に異なる許容レイテンシを持つ。フローが要求する許容レイテンシのレベルは、パケットヘッダに格納された優先度によって示される。例えば、リアルタイム性が要求される信号処理用途では高優先度であり、バックグラウンドプロセスによるファイル転送用途では低優先度となる。
【００７０】
優先度は、アプリケーション毎に固定であっても良いし、アプリケーションを構成するスレッド毎に変化させても良いし、プログラマやコンパイラが決定する更に細かい処理単位毎に変化させても良い。また各フローの送信レートは一定ではなく、フローによって異なるのが通常であり、さらに同一フローであっても、送信レートは時間変動するのが通常である。
【００７１】
図１６は、出力情報通知パケットのペイロードに記述される情報の例を示す。出力監視部１０７は、図１６に示す情報を、他のバス制御装置から自身宛の出力情報要求パケットを受理した際に、該当する出力ポートに関して作成し、送信元のバス制御装置に対して通知する。出力情報は複数のエントリーから構成され、各エントリーはパケットの優先度に対応する。各優先度レベル毎に、かかる優先度のパケットを送信するために要した出力ポートのバスサイクル数の時間平均、最大値、最小値がレポートされる。
【００７２】
本実施形態では、同一優先度の複数のフローがレポート対象の出力ポート上で混在している場合において、それらを区別していないが、より詳細にフロー毎に監視しても良い。またレポートする出力ポートの情報は、本実施形態に示す通り、出力監視部１０７が計測した実測値に基づいて算出された値でも良いし、バスマスタにより付加情報として通知されるフローのスペックに基づいた値でも良い。
【００７３】
図１７は、バス制御装置Ｒ２１がバスマスタＭ２４に至る経路（２）上の出力情報を収集する際のプロトコルの例を示す。図中の「ＭＡ」は、バスマスタに付与されたＮｏＣ上の一意のアドレスである。バス制御装置もこのアドレスにより特定できる。
【００７４】
送信元のバス制御装置Ｒ２１が経路（２）上に送信した出力情報要求パケットは、経路（２）上のバス制御装置Ｒ２２及びＲ２３を通って、経路終点のバス制御装置Ｒ２４に回送される。各バス制御装置Ｒ２２、Ｒ２３は、経路（２）上の次段のバス制御装置へのリンクにつながる出力ポートに関する出力情報通知パケットの返信を行うと共に、出力情報要求パケットを経路（２）上の次段のバス制御装置に対して回送する。経路終点のバス制御装置Ｒ２４は、出力情報要求パケットを破棄する。
【００７５】
（経路負荷検出部１０１）
経路負荷検出部１０１は、自身に接続されたバスマスタが送出する各フローの受信先アドレスと送信候補経路の情報を用いて、全ての送信候補経路に対して、出力情報要求パケットを送信する。出力情報要求パケットを送信するタイミングは、一定時間毎に定期的に行っても良い。また経路負荷検出部１０１は、出力情報要求パケット内に出力情報通知パケットの返信条件を格納しておき、経路上の各バス制御装置が返信条件を満たした際に、出力情報通知パケットを返信するトラップ方式を用いても良い。この場合、返信条件はデータ転送パケットの占有サイクル数の変化量が一定の閾値を超えた場合としても良い。
【００７６】
以下、図１３において、バス制御装置Ｒ２１にある経路負荷検出部１０１から、経路（１）、経路（２）、経路（３）に対して、定期的に出力情報要求パケットを発行する場合について説明する。各経路上の各バス制御装置は、図１７に示すプロトコルに従って、バス制御装置Ｒ２１に出力情報通知パケットを返信する。そのため、バス制御装置Ｒ２１は、ｉ番目の経路上のｊ番目のバス制御装置から、優先度δ毎に、それぞれ図１６に示す出力情報ωｉｊを収集することができる。
【数３】
2011004566.tif 000065
【００７７】
重み係数行列をＰとし、行列の要素をｐｉｊと表すとする。Ｐの各行は出力情報ベクトルωｉｊの各要素に対応し、各列は優先度δに対応する。本実施形態では、出力情報として、時間平均、最大値、最小値の３種類の情報を収集するため、Ｐの行数は３であり、フローを高優先度、中優先度、低優先度の３種類に分類するため、Ｐの列数は３である。
【数４】
2011004566.tif 000066
【００７８】
このとき、経路ｉ上のｊ番目のリンクの流量評価値βｉｊは、数５で示される。ｅは全要素が１のベクトルである。
【数５】
2011004566.tif 000067
【００７９】
経路ｉの流量評価値βｉは、経路上のリンクの流量評価値の最大値として定義して良い。
【数６】
2011004566.tif 000068
【００８０】
重み係数行列の要素を調整することにより、経路負荷検出部１０１は各経路の流量を適切に評価することができる。そして経路負荷検出部１０１は、流量評価値を均一化するようにフローの経路を制御することで、データ転送量がバス全体に均一化され、バスの動作周波数低減と、消費電力削減の効果が得られる。
【００８１】
経路負荷検出部１０１は、各バスマスタが送信するフローの特性が事前設計的に想定可能であれば、その情報を基にして重み係数行列の各係数値を決定しても良い。例えば、各バスマスタが時間的に変動しないフローのみしか発生させないことが分かっている場合には、各フローの平均値、最大値、最小値は一致するため、平均値のみを流量評価に反映させれば良い。このとき、重み係数行列Ｐを数７のように定義できる。
【数７】
2011004566.tif 000069
【００８２】
しかしながら、各フローは時間的に変動する特性を有するのが通常であるため、経路毎の流量の比較は単純な平均値比較とはならない。また低優先度のフローが高優先度のフローを阻害しないように、フローの優先度も適切に考慮して流量評価を行う必要がある。フローの時間変動も考慮した重み係数行列Ｐの例を数８に示す。
【数８】
2011004566.tif 000070
【００８３】
数８の重み係数行列を用いた場合の経路ｉの流量評価値βｉは、数５及び数６より、数９のようになる。式中のδｓｅｌｆは、制御対象フローの持つ優先度である。
【数９】
2011004566.tif 000071
【００８４】
数８によって定義された重み係数行列によれば、数９によって分かる通り、自身よりも高優先度のフローに対しては、その時間変動特性のうちの最大値をもって、流量が経路負荷検出部１０１によって評価されることを示している。またこの重み係数行列によれば、制御対象フロー自身よりも低優先度のフローに対しては、データ出力部１０６が行う優先度制御を前提とした平均値評価が行われることを示している。そしてこの重み係数行列によれば、自身と同一優先度のフローに対しては、時間変動特性がベータ分布に従うことを前提とした最頻値評価が行われることを示している。数７及び数８は、重み係数行列の定義の方法を制限するものではなく、想定されるフローの特性に合わせて、最適なＰを定義して良い。
【００８５】
３本の選択候補経路間の関係が均一かそうでないかの判断を行うための指標として、閾値を導入しても良い。閾値判定の例として、数１０に示す統計値ρを用いても良い。式中のＲは選択候補経路数を示す。
【数１０】
2011004566.tif 000072
【００８６】
ρの値が事前に定義された閾値ρｔｈを下回った場合には、経路負荷検出部１０１は経路間の均一性が損なわれたという判断をしても良い。経路間の均一性が損なわれた状態を検出した場合には、経路負荷検出部１０１は、制御対象フロー自身が現在データ転送パケットを伝送している送信経路以外の選択候補経路に移動した場合の仮想的なρの値を計算する。そして、経路負荷検出部１０１はそれらを比較し、最もρの値が大きくなる選択候補経路を切換先経路として決定し、経路決定部１０２に提示することで、経路表を更新し、経路の切換を行わせる。
【００８７】
図１８は、経路負荷検出部１０１の以上の処理の流れを示す図である。
【００８８】
ステップＳ１において、経路負荷検出部１０１は、自動経路切り換え処理を開始する。
【００８９】
具体的には、ステップＳ２において、経路負荷検出部１０１は、全ての送信候補経路に対して出力情報要求パケットを送信することにより、経路上の各中継ルータから、各送信候補経路に関する出力情報を収集する。
【００９０】
ステップＳ３からＳ５では、各経路に対する処理が行われる。具体的には、ステップＳ４において、経路負荷検出部１０１は各経路の流量評価値βｉを算出する。
【００９１】
ステップＳ６において、経路負荷検出部１０１は経路間の均一性指標ρを算出する。そして次のステップＳ７において、経路負荷検出部１０１は均一性指標ρが事前に定義された閾値ρｔｈを下回ったか否かを判定する。すなわち、均一性指標ρが閾値ρｔｈを下回った場合には、均一性が損なわれたとして、経路切り替えが必要であると判定する。このとき処理はステップＳ８に進む。一方、均一性指標ρが閾値ρｔｈを下回っていない場合には、処理はステップＳ１１に進み、その時点での経路切り換えは行わず、処理を終了する。
【００９２】
ステップＳ８において、経路負荷検出部１０１は、自身のフローが選択候補経路に移動したとした場合の仮想的な均一性指標ρの値を計算して、それらを比較する。そしてステップＳ９において、経路負荷検出部１０１は最もρの値が大きくなる選択候補経路を切換先経路として決定する。その結果、経路負荷検出部１０１は、ステップＳ１０において経路決定部への処理要求を発行する。
【００９３】
ステップＳ１１まで到達すると、経路負荷検出部１０１は、再びステップＳ１からの処理を繰り返す。
【００９４】
均一性指標ρは、優先度を考慮して重み付けられた流量評価値βを利用して算出される。そして、その指標ρに基づいて均一性が損なわれたと判定された場合には経路が適切に切り換えられる。これにより、データ転送に偏りが発生することを防ぐことができる。
【００９５】
なお、送信候補経路間の均一性を示すρの値が閾値を下回る時間割合を監視し、均一性制御が功を奏していないことを検知することで、重み係数行列Ｐの各要素にフィードバック制御を働かせても良い。
【００９６】
（経路決定部１０２）
経路決定部１０２は、経路表を管理し、パケット構成部１０３が提示する宛先アドレスに基づいて経路表を検索し、ネクストホップとするバス制御装置に関連した出力ポートをパケット構成部１０３に通知する。
【００９７】
図１９は、バス制御装置Ｒ２１の経路決定部１０２が管理する経路表の例を示す。宛先アドレスＭＡ２４に位置するバスマスタＭ２４への経路として、３本の選択候補経路が定義されている。この選択候補経路のそれぞれのネクストホップとなるバス制御装置のアドレスとそれに対応する出力ポート、終点アドレスに至る迄にホップするバス制御装置のアドレスのリスト、データ転送パケットが実際に送信されている経路を示す選択情報が記録され管理される。
【００９８】
経路決定部１０２は、経路負荷検出部１０１からの要求に従い、受信先アドレスと選択候補経路のリスト及びホップリストを提示し、出力情報要求パケットの送信に必要な経路に関する情報を提供する。また経路負荷検出部１０１から提示された切換先経路の情報に従い、経路表の選択情報の更新を行うことで、データ転送パケットが送信される経路を変更する。
【００９９】
以上説明したバス制御装置２によれば、ＮｏＣバスを構成するリンク間の流量の偏りが自動的に抑制されるため、データ転送負荷がバス全体で均一化され、特定リンクへの負荷集中による通信遅延時間、レイテンシの増加が抑えられる。リンクの動作周波数を低減することで、バス設計を容易にし、データ転送時のバスの消費電力を削減することが可能となる。またリンクの動作周波数の動的制御技術と組み合わせることにより、バスの消費電力を更に効率的に削減することが可能となる。また同等機能を提供するバスマスタへの経路負荷を、統計多重効果を考慮した上で均一化することにより、バスマスタの負荷分散効果も得られる。このため、分散型のメモリ・アーキテクチャに本発明を適用することにより、メモリアクセスの許容レイテンシに対する信頼性を確保した上で、アクセス集中によるボトルネックを回避することが可能となる。
【０１００】
（実施形態２）
図２０は、分散型のメモリ・アーキテクチャに本発明を適用した構成の例を示す。３つのプロセッサＵＰ１１、ＵＰ１２、ＵＰ１３と、３つの共有メモリモジュールＭＥＭ３１、ＭＥＭ３２、ＭＥＭ３３が、３×３のメッシュ型のバス制御装置のネットワークを介して接続されている。プロセッサは、タスク起動時に必要なメモリ領域をいずれかのメモリモジュール上に割り当て、タスク終了時に割り当てた領域を解放する。しかし、特定のメモリモジュールへの割当が集中した場合、メモリモジュール間でアクセスレートにばらつきが発生し、アクセスが集中したメモリモジュールへのアクセスバスの動作周波数が上がり、設計面、消費電力面で課題となる。プロセッサでのメモリ割当時に、メモリモジュール間のアクセスレートができるだけ均一になるように割当処理を行うことで、アクセスバスの動作周波数低減と、消費電力削減の効果が得られる。
【０１０１】
本実施形態による分散型メモリネットワークを構成するバス制御装置の構成は、以下に特に説明する点を除いては、図１４に示す実施形態１のバス制御装置２の構成と同じである。共通する機能の説明は省略する。
【０１０２】
（パケット構成部１０３）
本実施形態では、前提条件として、プロセッサとメモリモジュール間の各フローのレート特性である平均レートと最大レートが事前設計されており、各フローは同一の優先度を有する場合を想定する。複数の優先度に対応するフローが混在する場合には、実施形態１と同様に扱えば良い。プロセッサ側のバス制御装置内にあるパケット構成部１０３は、図１５に示すように、プロセッサ上のタスクから提示されたフローのレート特性を、付加情報としてデータ転送パケットのヘッダに格納して送信する。これにより、メモリモジュール側のバス制御装置に対して、アクセスフローのレート特性を伝達する。
【０１０３】
（出力監視部１０７）
メモリモジュール側のバス制御装置内にある出力監視部１０７は、プロセッサ側のバス制御装置から伝達されるアクセスフロー毎のレート特性を基に、数１１、数１２に示す評価式を管理する。
【数１１】
2011004566.tif 000073
【数１２】
2011004566.tif 000074
【０１０４】
式中で、μｉｊは、ｐｉｊは、ｉ番目のメモリモジュールのｊ番目のアクセスフローに対する平均レート及び最大レートの値であり、ｎはｉ番目のメモリモジュールに割り当てられたアクセスフローの総数、μi、ｐｉはｉ番目のメモリモジュールの平均レート評価式と最大レート評価式である。他のバス制御装置から出力情報要求パケットを受理した出力監視部１０７は、図２１に示される出力情報を含んだ出力情報通知パケットを返信する。
【０１０５】
バス制御装置から伝達されるアクセスフローのレート特性は、設計時に予め算定できる情報を含んでも良い。そのような情報として、たとえばＳｏＣ上で動作するアプリケーション、信号処理のモジュールが生成する平均レート、最大レート、最小レート、アクセスレートの標準偏差、処理の優先度、許容されるアクセスレイテンシを挙げることができる。
【０１０６】
またユーザの機器操作などによって発生するメモリアクセスのように、設計段階でアクセスレート特性が予め算定ができないメモリアクセスのフローに関しては、実施の形態１に示したようにメモリ側のバス制御装置でアクセスレートの平均値や最大値を実測することで数１１、数１２を計算しても良い。
【０１０７】
設計時特性と実測値のいずれも利用可能である場合には、設計時特性を使用したほうが良い。実測値をベースにした制御では、瞬間的な負荷減少に対して、各バスマスタが集中的に当該メモリへのアクセスフローの割当を行おうとする傾向が強まる。そのため、割当可能なメモリの余剰帯域に比して、過剰なフローを収容する結果となり、直後の負荷上昇とアクセスレイテンシの増大が起こった際に、各バスマスタが再度アクセスフローの割当直しを行わざるを得ない状況に繋がり易い。このような現象は、「ルートフラッピング」として知られており、ネットワークのスループットやアクセスレイテンシを著しく劣化させる。フローの設計時特性をベースに割当制御を行った場合には、瞬間的な負荷状態に依存しない割当量を管理できるため、ルートフラッピングの発生を避けることができる。
【０１０８】
メモリモジュール側のバス制御装置内にある出力監視部１０７において、接続されたメモリへのアクセスレイテンシを計測、管理しても良い。アクセスレイテンシは、プロセッサからのデータ読出あるいは書込要求を示すデータ転送パケットをデータ受信部１０４が受信してから、対応する読出あるいは書込動作が完了する迄に要したサイクル数で表しても良い。データ転送パケットのヘッダに格納された優先度によって規定されるアクセスフローのレイテンシ要求に対して、充分なマージンが確保できていない状態を出力監視部１０７が検出した場合には、要求元のプロセッサのバス制御装置アドレスを受信先アドレスとする出力情報通知を緊急送信することで、アクセス品質の低下をプロセッサ側に通知しても良い。
【０１０９】
（経路負荷検出部１０１）
経路負荷検出部１０１は、プロセッサが平均レートμt、最大レートｐtのメモリアクセスフローを割り当てるためのメモリ領域確保のイベントをトリガとして、出力情報要求パケットを各メモリモジュールのバス制御装置宛に送信する。この出力情報要求パケットにより、図２１に示された評価値を収集する。出力情報を収集するためのプロトコルの例を図２２に示す。フローの時間変動を考慮したｉ番目のメモリの流量評価値βｉは、数１３で表される。式中のｍは同一メモリに割り当てられた複数フロー間の統計多重効果の強さと信頼性をバランスさせるための調整係数である。
【数１３】
2011004566.tif 000075
【０１１０】
また新たな割当対象フローの割当後のｉ番目のメモリの流量評価値β'ｉは、数１４で表される。
【数１４】
2011004566.tif 000076
【０１１１】
割当対象フローをｉ番目のメモリに割り当てた場合の各メモリの流量の状態をＳｉとすると、数１５のようになる。
【数１５】
2011004566.tif 000077
【０１１２】
状態Ｓｉにおけるメモリ間の流量均一性を数１６、数１７で評価しても良い。式中のｎはメモリモジュールの個数を表す。
【数１６】
2011004566.tif 000078
【数１７】
2011004566.tif 000079
【０１１３】
フローの割当対象のメモリモジュールを数１８によって決定することで、フローの時間変動を考慮した統計多重効果が最も期待でき、メモリ間のアクセスレートの均一性を向上させることができる。
【数１８】
2011004566.tif 000080
【０１１４】
経路負荷検出部１０１は、該当するタスクに対してｑ番目のメモリが割り当てられたことを、プロセッサに通知する。プロセッサ上のタスクはメモリへのデータ転送パケット送信時の送信先アドレスをｑ番目のメモリのアドレスとして認識する。
【０１１５】
このように、数１３で示される割当対象フローの割当前の各メモリの流量βｉを比較するのではなく、数１４及び数１５で示すように、仮想的な割当後の各メモリの流量Ｓｉを比較して、実際のフローの割当先のメモリを決定する。これにより、各メモリに対して、既に割当済のフロー群と割当対象のアクセスフローとの関係も考慮することができるため、より適切な割当先メモリを選択できるようになる。例えば、時間変動の激しいアクセスフローを新規に割り当てる状況を考える。割当前の流量は大きかったとしても、時間変動の少ないフロー群を割当済のメモリよりも、時間変動の大きなフロー群を割当済の経路を選択したほうが、統計多重効果によって、割当実施後の帯域利用効率を向上させることができる。仮想的な割当後の均一性を基に割当先メモリを決定することで、このような状況にも対応可能となる。
【０１１６】
またメモリモジュール側のバス制御装置内にある出力監視部１０７が発信する、アクセス品質低下の緊急出力情報通知パケットを受信した経路負荷検出部１０１は、その情報を基に、数１３及び数１４に含まれる調整係数ｍの値を動的に制御する。これにより、アクセス品質に関する信頼性を向上させることができる。経路負荷検出部１０１が管理する調整係数ｍの初期値を数１９で定義する。ｍの初期値は例えば５に設定しておいても良い。
【数１９】
2011004566.tif 000081
【０１１７】
またｍを制御するためのパラメータ変数として、αを数２０で初期化する。初期値は例えば、１に設定しておいても良い。
【数２０】
2011004566.tif 000082
【０１１８】
緊急の出力情報通知パケットの受信によって、アクセス品質の低下を検知した経路負荷検出部１０１は、αの値を数２１に従って変更する。Δαは、事前に定められたＮ回の緊急出力情報通知の受信による正の変化分である。例えば、Ｎの値を１に、Δαの値を０．５に設定しておいても良い。
【数２１】
2011004566.tif 000083
【０１１９】
調整係数ｍの値を、数２２に示すダイナミクスで制御する。式中のｍmax、ｍminは調整係数ｍの事前に決定された最大値及び最小値であり、例えば、７及び５に設定しておいても良い。ｋは調整パラメータであり、例えば１００に設定しておいても良い。δはクロネッカのデルタ関数であり、ηはランダムな正の整数である。
【数２２】
2011004566.tif 000084
【０１２０】
数２２により、調整係数ｍを、数２３のように更新すれば良い。
【数２３】
2011004566.tif 000085
【０１２１】
上述の数式に基づく処理によれば、データが流れにくくなるにつれて、Δｍの値が大きくなるため、ｍの値が大きくなる。
【０１２２】
更新した結果、ｍの値が最大値を超えた場合には、α＝０とすることで、ランダムな調整係数選択を行わせると良い。調整係数ｍの更新が完了した時点で、数２０に従って、再びαの初期化を行えば良い。調整係数ｍを制御することによって、各フローのレート変動特性が想定する確率分布に従わない場合であっても、メモリ割当の均一性と統計多重効果をバランスさせ、フローを収容可能なバスの動作周波数を引き下げる効果が得られる。
【０１２３】
以上、本発明の実施形態を説明した。
【０１２４】
上述の実施形態では、ＮｏＣのトポロジは２次元メッシュ型であるとしたが、これは一例である。本実施形態によるフロー制御は、他のトポロジであっても適用可能である。他のトポロジとして、たとえば２次元トーラス型のトポロジを採用してもよい。また、バスマスタおよび対応するバス制御装置の組をリング状に配置し、隣接するバス制御装置同士、および、リング上対向するバス制御装置同士をバスで接続するトポロジを採用してもよい。さらに２次元型に限られず、バスマスタおよび対応するバス制御装置をダイスタッキングし、バス制御装置を３次元接続するトポロジを採用してもよい。
【０１２５】
（実施形態３）
本実施形態によるバス制御装置は、実施形態２と同様、図２０に示す分散型のメモリ・アーキテクチャに適用することが可能である。図２０に示す分散型のメモリ・アーキテクチャの説明は実施形態２と同じであるため、その説明は省略する。
【０１２６】
本実施形態による分散型メモリネットワークを構成するバス制御装置の構成は、以下に特に説明する点を除いては、図１４に関連して説明した実施形態２によるバス制御装置２の構成と同じである。共通する機能の説明は省略する。
【０１２７】
（経路負荷検出部１０１）
本実施形態では、実施形態２における数１６に代えて、下記数２４を採用してもよい。
【数２４】
2011004566.tif 000086
【０１２８】
流量の均一性を優先指標としたフローの割当対象のメモリモジュールは数２５によって決定される。
【数２５】
2011004566.tif 000087
【０１２９】
一方、割当対象のフローを発生させたプロセッサからみて、最近接に位置するメモリモジュールはｑ０であるとは限らない。ここでいう「最近接に位置するメモリモジュール」（以下「最近接メモリモジュール」と記述する。）とは、設計上、プロセッサから最も低いレイテンシでアクセス可能と想定されるメモリモジュールを意味する。
【０１３０】
図２０の例では、プロセッサＵＰ１１から３つの共有メモリモジュールＭＢＭ３１、ＭＢＭ３２、ＭＢＭ３３へは、それぞれ２ホップ、３ホップ、４ホップとなっている。よって、設計上は、共有メモリモジュールＭＢＭ３１がプロセッサＵＰ１１の最近接メモリモジュールとして定義できる。プロセッサ毎に定義される最近接メモリモジュールの識別子ｑ１は、例えばＳｏＣの設計情報として定義される。当該識別子ｑ１は、予め該当するプロセッサ、または、プロセッサに接続されたＮｏＣルータの経路負荷検出部の内部にハードコードされていても良いし、初期化動作に計測パケットを送受信して選択しても良い。
【０１３１】
数２４で示されるρｉは、メモリモジュールｉに割当対象フローの割当を行った後の均一性を示している。一方、割当を行わない状態での、つまりその時点における実際の均一性を示す指標は、数２６で与えられる。ρは１を越えない正の数である。
【数２６】
2011004566.tif 000088
【０１３２】
また、各メモリモジュール毎の、現在の流量評価値として算出された数１３で示されるβｉを基にして、数２７に示すγを計算できる。式中のｂはバス幅、ｃはバスの動作周波数を表すとすれば、γは、１サイクル時間にアクセスされたフリット数を示し、物理帯域を越えるアクセスが発生していない状況下では、１を越えることはない。γは、各メモリモジュールの中で、最も割当量の大きいメモリモジュールにおける、割当量を示す指標と成り得る。
【数２７】
2011004566.tif 000089
【０１３３】
経路負荷検出部は、ρ及びγの値を基に、フローの割当先のメモリモジュールｑを決定する。最も単純な決定方法の例としては、数２８の条件式に従えば良い。
【数２８】
2011004566.tif 000090
【０１３４】
Γth及びΡthは、閾値であり事前に定義された値を用いれば良い。メモリモジュールへのアクセス量が少なく、メモリモジュール間の均一性が殆ど問題にならない低負荷領域では、フローの割当先として最近接メモリモジュールが選択され、最も近接に位置する低レイテンシな（たとえばレイテンシが最低である）メモリモジュールｑ１が選択される。メモリへの割当フローが増加し、メモリモジュール間のアクセスのばらつきが性能に影響を及ぼす中負荷から高負荷の領域では、流量の均一性を重視してメモリモジュールｑ０が選択される。このように状況に応じて流量の均一性の重みを変更することで、スループットが向上する。
【０１３５】
ｑを決定する際の他の方法として、プロセッサ毎に自律的にｑ０またはｑ１を選択させてもよい。下記数２９は、変数ｍｉのダイナミクスを支配し、式中のηは、ランダムノイズである。数２９、数３０、数３１中のαのダイナミクスは、数３２で制御される。δ、Ｋは定数である。
【数２９】
2011004566.tif 000091
【数３０】
2011004566.tif 000092
【数３１】
2011004566.tif 000093
【数３２】
2011004566.tif 000094
【０１３６】
割当先のメモリモジュールは、数３３の判定式によって決定すれば良い。
【数３３】
2011004566.tif 000095
【０１３７】
これによって、ｑ０とｑ１の選択の切換が、プロセッサ間で自律的かつ段階的に進行するため、利用帯域の無駄がなくなり、スループットが向上する。
【０１３８】
経路負荷検出部１０１は、該当するタスクに対してｑ番目のメモリモジュールが割り当てられたことを、プロセッサに通知する。プロセッサ上のタスクはメモリモジュールへのデータ転送パケット送信時の送信先アドレスをｑ番目のメモリモジュールのアドレスとして認識する。
【０１３９】
図２３は、本実施形態にかかるバス制御装置の性能評価をＮｏＣのシミュレータを用いて行った結果を示す。この結果は、数３２において、Kγ＝Kρ＝１００、Γth＝０．５、Ρth＝０．７５としたときのαのプロファイルを示している。γ及びρが閉区間［０，１］を動く場合に、αは閉区間［０．５，１．０］の範囲を変動することが分かる。
【０１４０】
図２４は、数２９において、ηｉを閉区間［−０．０５，  ＋０．０５］の範囲で変動する一様分布に従うランダムノイズとしたときの、ｍ１及びｍ２の時間変化を示す。横軸は時間軸を示している。αの変化に従って、ｍ１とｍ２の大小関係が変化していることが分かる。数３３に従って、ｍ１がｍ２より下にある場合にはｑ０が選択され、ｍ１がｍ２より上にある場合にはｑ１が選択される。常にｍ１、ｍ２の符号が負にならないように、ηｉによって負数に振れたときは、強制的に０とする数値処理が入っている。
【０１４１】
時刻［５００，１０００］及び時刻［２０００，２５００］の範囲では、α＝１．０に伴い、ｍ２がｍ１より大きくなり、均一性による割当先の選択が行われている。一方、時刻［１５００，１７００］ではこのような変化はなく、レイテンシを重視した最近接割当を維持している。これにより、他のプロセッサの変化によるαの低下によって、最近接割当を継続していることが分かる。
【０１４２】
この方法によれば、全てのプロセッサが一斉に割当先を変更することによって、一部のメモリモジュールにアクセスピークが発生することを回避することが可能となり、過渡時の性能を悪化させることなく、流量の均一性とレイテンシを重視した割当方法の切換動作を徐々に進行させることができる。
【０１４３】
図２５は、シミュレーションに用いたＮｏＣの構成を示す図である。５個のプロセッサＵＰ１１〜ＵＰ１５、および、３個のメモリモジュールＭＥＭ５１、ＭＥＭ５３、ＭＥＭ５５が接続された５ｘ５の正方メッシュトポロジーのＮｏＣで構成される。
【０１４４】
プロセッサＵＰからは、一定サイクル毎に１パケットのデータをメモリモジュールＭＥＭに対して送信するフローを発生させた。パケット長は４フリットに固定である。また各プロセッサＵＰから２０本のフローを発生させ、各フローの発生するデータ量を、１倍フローが５本、１０倍フローが５本、１００倍フローが１０本となるようにした。「１０倍フロー」とは、１００倍フローが１０パケット送信する間に１パケットを送信するフローであり、「１倍フロー」とは１０倍フローが１０パケット送信する間に１パケットを送信するフローを意味する。１倍フローのパケット送信間隔は、１０倍フローの１０倍であり、１０倍フローのパケット送信間隔は、１００倍フローの１０倍である。
【０１４５】
またルーティングプロトコルは、ＸＹ次元順ルーティングを用い、スイッチングプロトコルは、ワームホールスイッチングとし、ルータの構成は、仮想チャンネル数４、仮想チャンネルサイズ４とした。フローの送信開始のタイミングは数サイクルずつずらし、メッシュネットワーク入り口での輻輳は発生しないように配慮した。図２６および図２７は、本願発明者らがシミュレーションデータからまとめた、メモリモジュール側でのスループットとレイテンシとの関係を示す。横軸に示すスループットは、各メモリモジュールＭＥＭ５１、ＭＥＭ５３、ＭＥＭ５５の単独のスループットの総和である。各メモリモジュールの単独のスループットは、シミュレーション時間内に受信したフリット数をシミュレーション時間内の全サイクル数毎で除した値として得られる。シミュレーション中に全くフリットを受信しなかった場合は０であり、絶えずフリットを受信した場合は１となる。また１サイクルおきに１フリットを受信した場合には、０．５となる。
【０１４６】
図２５に示す例ではメモリモジュールは３個存在するため、スループットの最大値は３である。縦軸に示すレイテンシは、プロセッサでフリットを生成した時点のタイムスタンプ値とメモリモジュール側でフリットを受信した時点のタイムスタンプ値との差である。１つのパケットを構成する４つのフリットの生成時のタイムスタンプは全て同じ値である。
【０１４７】
図２６は、４０００サイクルに渡るシミュレーション結果のグラフである。このグラフにより、割当方式の相違による性能を比較することが可能である。「均一割当」を表すラインは、αの値に拘わらず、常にｑ０を選択しつづけた結果を示している。「選択割当」を表すラインは、αの値によって、ｑ０とｑ１の選択を行った結果を示す。いずれの場合でも、飽和スループットとして、２．７程度の性能が出ていることが確認できる。このシミュレーションにおける利用可能な物理帯域は３．０であるため、物理帯域の約９０％のスループットを利用可能となっている。
【０１４８】
また図２７は、同一のシミュレーションにおいて、低負荷領域におけるスループットとレイテンシとの関係に着目した結果を示す。このグラフにより、低負荷領域における割当方式の相違による性能を比較することが可能である。ｑ０とｑ１を切り換えることにより、常にｑ０のみを選択した場合と比べ、レイテンシが５サイクル程度向上している。割当時の選択を行ったほうが、低負荷の状態も含めてスループットとレイテンシの特性を改善できていることが分かる。
【０１４９】
上述の実施形態では、ＮｏＣのトポロジは２次元メッシュ型であるとしたが、これは一例である。本実施形態によるフロー制御は、他のトポロジであっても適用可能である。他のトポロジとして、たとえば２次元トーラス型のトポロジを採用してもよい。また、バスマスタおよび対応するバス制御装置の組をリング状に配置し、隣接するバス制御装置同士、および、リング上対向するバス制御装置同士をバスで接続するトポロジを採用してもよい。さらに２次元型に限られず、バスマスタおよび対応するバス制御装置をダイスタッキングし、バス制御装置を３次元接続するトポロジを採用してもよい。
【０１５０】
（実施形態４）
上述の実施形態では、本願発明がチップ上で実装された際の構成を説明した。
【０１５１】
本願発明は、チップ上に実装されるだけでなく、チップ上に実装するための設計及び検証を行うシミュレーションプログラムとしても実施される。そのようなシミュレーションプログラムは、コンピュータによって実行される。本実施形態においては、図１４に示される各構成要素は、シミュレーションプログラム上のオブジェクト化されたクラスとして実装される。各クラスは、予め定められたシミュレーションシナリオを読み込むことにより、上述した実施形態の各構成要素に対応する動作をコンピュータ上で実現する。言い換えると、各構成要素に対応する動作は、コンピュータの処理ステップとして直列的または並列的に実行される。
【０１５２】
バスマスタとして実装されたクラスは、シミュレータで定義されたシミュレーションシナリオを読み込むことにより、バス制御装置のクラスにパケットを仮想的に送信するタイミング等の条件を決定する。そして、図１３で示される各経路での送信状態をシミュレーションし、実施の形態１、２と同様に送信状態を比較することで、送信経路を決定する動作を行う。
【０１５３】
バスマスタとして実装されたクラスは、シミュレーションシナリオに記述されたシミュレーションの終了条件が成立する迄の間、動作を行い、動作中のスループットやレイテンシ、バスの流量の変動の様子、動作周波数、消費電力の見積値等を算出しプログラムの利用者に提供する。これらに基づき、プログラムの利用者はトポロジーや性能の評価を行い、設計及び検証を行う。
【０１５４】
例えばシミュレーションシナリオの各行には、送信元バスマスタのＩＤ、宛先バスマスタのＩＤ、送信するパケットのサイズ、送信するタイミング等の情報が記述されるのが普通である。また複数のシミュレーションシナリオをバッチ処理的に評価することで、想定した全てのシナリオで所望の性能が保証できているか否かを効率的に検証できる。またバスのトポロジーやノード数、プロセッサやＤＳＰ、メモリ、周辺ＩＯの配置を変化させて性能比較することにより、シミュレーションシナリオに最も適したネットワーク構成を特定することもできる。実施形態１から３のいずれもが本態様の設計及び検証ツールとしても適用可能である。本願発明は、設計及び検証ツールとして実施される際にも適用可能である。
【産業上の利用可能性】
【０１５５】
本発明は、組込機器向けのＳｏＣにおけるオンチップバスや、汎用プロセッサ、ＤＳＰ上のローカルバスにおける、データ転送経路の制御技術を備えたネットワークバス制御装置、制御方法、制御プログラムに利用可能である。
【符号の説明】
【０１５６】
１０１  経路負荷検出部
１０２  経路決定部
１０３  パケット構成部
１０４  データ受信部
１０５  ヘッダ解析部
１０６  データ出力部
１０７  出力監視部
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
バスマスタと、ネットワーク化された通信バスとの間に設けられ、前記通信バスに流れるパケットの送信経路を制御するバス制御装置であって、
利用可能な複数の送信経路上に存在する複数の他のバス制御装置から、出力状況に関する情報を受信するデータ受信部と、
前記出力状況に関する情報に含まれる、出力ポートのバスサイクル数の最大値、時間平均値および最小値のいずれか及びパケット転送の優先度と、前記優先度ごとに設けられた、前記最大値、平均値、最小値に対する重みと、により、各送信経路の送信流量のばらつきを示す均一化指標を算出する経路負荷検出部と、
前記均一化指標に基づいて、前記送信流量が調整された複数の送信経路を決定する経路決定部と、
前記バスマスタから受け取ったデータに基づいてパケットを生成するパケット構成部と、
各々が異なる通信バスに接続された複数の出力ポートのいずれか一つから前記パケットを出力するデータ出力部と、
前記複数の出力ポートの中から、前記パケットの送信先の情報に基づいて選択された送信経路の一つに接続されている出力ポートを決定するヘッダ解析部と
を備えた、バス制御装置。
【請求項２】
前記経路負荷検出部は、現在割り当てられているパケットの平均レートと最大レートに基づく指標に対して、割り当てるべきパケットの平均レートμｔと、最大レートｐｔとを加えることにより、均一化指標を算出する、請求項１に記載のバス制御装置。
【請求項３】
前記複数の他のバス制御装置からの要求に従って、前記データ出力部のデータ出力状況に関する情報を通知する出力監視部をさらに備えた、請求項１に記載のバス制御装置。
【請求項４】
前記経路負荷検出部は、出力するフローの優先度毎の転送頻度の平均値を少なくとも含む、前記出力監視部からの出力状況の中で前記平均値を基に均一化指標を算出する、請求項３に記載のバス制御装置。
【請求項５】
前記経路負荷検出部は、出力するフローの優先度毎の転送頻度の平均値および最大値を少なくとも含む、前記出力監視部からの出力状況の中で前記平均値および最大値に基づいて均一化指標を算出する、請求項３に記載のバス制御装置。
【請求項６】
前記経路負荷検出部は均一化指標に含まれる統計多重効果に起因する評価値の信頼度を規定するパラメータを含む、請求項５に記載のバス制御装置。
【請求項７】
前記経路負荷検出部は、前記パケットの転送状況の劣化を検出して、前記信頼度を規定するパラメータを調整し、前記パラメータの調整で転送状況が改善しない場合には、確率的にパラメータを調整する、請求項６に記載のバス制御装置。
【請求項８】
前記出力監視部は、予め定められたタイミングで発行される前記出力状況に関する情報の要求の受信をトリガとして、前記情報を通知する、請求項３に記載のバス制御装置。
【請求項９】
前記経路負荷検出部は、事前に出力状況通知の送信条件を出力監視部に伝達し、
前記出力監視部には、予め前記出力状況に関する情報の要求が送信される条件が通知されており、前記送信条件が成立した場合には前記情報を通知する、請求項３に記載のバス制御装置。
【請求項１０】
前記経路負荷検出部は、前記出力状況に関する情報に対して、前記各送信経路のフローの優先度に応じた重みを加えることにより、前記各送信経路の送信流量に関する評価値を算出し、前記各送信経路の送信流量のばらつきを示す均一化指標を算出する、請求項１に記載のバス制御装置。
【請求項１１】
前記経路負荷検出部は、前記各送信経路の送信流量に関する評価値を利用して算出した統計値を、前記均一化指標として算出する、請求項１０に記載のバス制御装置。
【請求項１２】
前記経路負荷検出部は、前記出力状況に関する情報と選択対象の送信経路のデータ特性に関する情報とに基づいて各送信経路の送信流量のばらつきを示す均一化指標を算出する、請求項１に記載のバス制御装置。
【請求項１３】
バスマスタと、ネットワーク化された通信バスとの間に設けられ、前記通信バスに流れるパケットの送信経路を制御するバス制御装置のためのシミュレーションプログラムであって、
前記シミュレーションプログラムは、コンピュータに対し、
前記シミュレーションプログラム上のオブジェクト化された複数の他のバス制御装置のクラスであって、利用可能な複数の送信経路上に存在する複数の他のバス制御装置のクラスから、出力状況に関する情報を受信するステップと、
前記出力状況に関する情報に含まれる、出力ポートのバスサイクル数の最大値、時間平均値および最小値のいずれか及びパケット転送の優先度と、前記優先度ごとに設けられた、前記最大値、平均値、最小値に対する重みと、により、各送信経路の送信流量のばらつきを示す均一化指標を算出するステップと、
前記均一化指標に基づいて、前記送信流量が調整された複数の送信経路を決定するステップと、
前記バスマスタとして実装されたクラスから受け取ったデータに基づいてパケットを生成するステップと、
各々が異なる通信バスに接続された複数の出力ポートのいずれか一つから前記パケットを出力するステップと、
前記複数の出力ポートの中から、前記パケットの送信先の情報に基づいて選択された送信経路の一つに接続されている出力ポートを決定するステップと、
前記決定された出力ポートから前記パケットを出力するステップと
を実行させる、バス制御装置のためのシミュレーションプログラム。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2011004566.tif 000096
【図２】
2011004566.tif 000097
【図３】
2011004566.tif 000098
【図４】
2011004566.tif 000099
【図５】
2011004566.tif 000100
【図６】
2011004566.tif 000101
【図７】
2011004566.tif 000102
【図８】
2011004566.tif 000103
【図９】
2011004566.tif 000104
【図１０】
2011004566.tif 000105
【図１１】
2011004566.tif 000106
【図１２】
2011004566.tif 000107
【図１３】
2011004566.tif 000108
【図１４】
2011004566.tif 000109
【図１５】
2011004566.tif 000110
【図１６】
2011004566.tif 000111
【図１７】
2011004566.tif 000112
【図１８】
2011004566.tif 000113
【図１９】
2011004566.tif 000114
【図２０】
2011004566.tif 000115
【図２１】
2011004566.tif 000116
【図２２】
2011004566.tif 000117
【図２３】
2011004566.tif 000118
【図２４】
2011004566.tif 000119
【図２５】
2011004566.tif 000120
【図２６】
2011004566.tif 000121
【図２７】
2011004566.tif 000122
【国際調査報告】
2011004566.tif 000123
2011004566.tif 000124
2011004566.tif 000125
2011004566.tif 000126