通信チャネルを介して送られるメッセージ間の調停を行うデータ処理装置および方法
【課題】通信チャネルを介して送られるメッセージ間の調停を行うデータ処理装置および方法を得る。
【解決手段】データ処理装置は各々が受取要素に発せられるメッセージを要求するプロセスを実行する複数の処理要素と、これらの処理要素間で共有されそれを介してメッセージが送られる通信チャネルとを有する。調停回路が通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する。各処理要素はそこで実行中のプロセスに対する進捗データを発し、進捗データはプロセスに対する待ち時間含意を示す。調停制御回路が各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データが示す各プロセスの待ち時間含意を考慮した優先順位付けプロセスを実施する。優先順位付けデータは調停プロセスを制御するために調停回路に出力される。
【解決手段】データ処理装置は各々が受取要素に発せられるメッセージを要求するプロセスを実行する複数の処理要素と、これらの処理要素間で共有されそれを介してメッセージが送られる通信チャネルとを有する。調停回路が通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する。各処理要素はそこで実行中のプロセスに対する進捗データを発し、進捗データはプロセスに対する待ち時間含意を示す。調停制御回路が各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データが示す各プロセスの待ち時間含意を考慮した優先順位付けプロセスを実施する。優先順位付けデータは調停プロセスを制御するために調停回路に出力される。
【発明の詳細な説明】
【技術分野】
【０００１】
（発明の分野）
本発明は通信チャネルを介して送られるメッセージ間の調停を行う、特に、複数の処理要素間で共有される通信チャネルを介して送られるメッセージ間の調停を行うデータ処理装置および方法に関する。
【背景技術】
【０００２】
（従来技術の説明）
通信チャネルが複数の処理要素間で共有され、さまざまな処理要素が通信チャネルを介して受取要素へメッセージを発する多くのシステムがある。通信チャネルはいくつかのマスタ装置をシステム・オン・チップ（ＳｏＣ）装置等のチップ内のいくつかのスレーブ装置と接続する、またはマルチチップ・モジュール内の個別のチップと接続する、さらには印刷回路板構造内のさまざまなモジュールと相互接続するのに使用されるバス相互接続回路の形をとることができる。より大きい規模で、通信チャネルは複数のコンピュータ、または複数の装置を相互接続するのに使用される共有無線リンクにより形成することができる。
【０００３】
任意の通信チャネルに対して、そのチャネルの情報搬送容量には限界があり、通信チャネルに関連する待ち時間（ｌａｔｅｎｃｙ）もある。並列化技術および高められた動作周波数の使用等の、チャネル容量および待ち時間を変更できるようにする構成上のオプションがある。しかしながら、これらの技術は複雑さ、電力およびエリアにコストを要し、それらは必要な性能に対して取引する必要がある。
【０００４】
通信チャネルが複数の処理要素間で共有され、これらの処理要素は処理を実行する時に通信チャネルを介してメッセージを発する必要がある任意のシステムにおいて、通信チャネルが共有される事実により通信チャネルを介して処理されるメッセージの順序に関して判断を行うことが強制され、この判断は調停技術を利用して行われる。ＳｏＣの例について考えると、メッセージはトランザクション中にマスタ装置により発せられる信号の形をとることができ、特に、マスタ装置はトランザクションに関連するスレーブ装置を指定する通信チャネル上にアクセス要求を発することで典型的にトランザクションを開始する。この特定の分野において、トランザクションのある順序付けにより全体待ち時間は他の順序付けよりも低くなり、これはメモリコントローラ等の装置がしばしば特殊化するエリアであることが知られている。しかしながら、調停判断の結果そのメッセージが引き止められているプロセスが経験する待ち時間が調停判断により必然的に付加される。したがって、この調停判断が行われる方法はシステムの全体性能に有意の影響を及ぼす。
【０００５】
基本的な調停方式は固定優先順位すなわちラウンドロビン（ｒｏｕｎｄ ｒｏｂｉｎ）（公平共有）技術を利用するアルゴリズムを使用する。このような方式はメッセージ・バイ・メッセージベースの調停判断を行うのに限定され、過去になされた選択の限定された量が考慮される。ラウンドロビン方式の例外は現在の優先順位が前の優先順位によって決まることである。しかしながら、両方式共通信チャネルを介して導入される付加待ち時間をメッセージを発する個別プロセス間ではなくメッセージ・バイ・メッセージベースで割り当てるという問題がある。したがって、通信チャネルを通るハイレベルのアクセスを有するメッセージは、通信チャネル内で行われる調停判断の結果時間とともにハイレベルの付加待ち時間を受ける。
【０００６】
主としてネットワーク用に開発されている代替技術はＱｕａｌｉｔｙ−ｏｆ−Ｓｅｒｖｉｃｅ（ＱｏＳ）技術であり、それはプロセスが必要な帯域幅および制御された待ち時間特性を有することを保証しようと試みることにより時間ベース見解をとる。それ故、このようなＱｏＳ方式は各プロセスを考慮して通信チャネルの帯域幅の一部をそのプロセスに割り当て、各トランザクションまたはメッセージに適用される待ち時間を幾分制御する。しかしながら、既知のＱｏＳ方式の限界はこれらのプロセスが実行される時に生じる実際のデータフローの前に各プロセスの特性は知られているものと仮定され、かつその情報の管理に幾分ハイレベルのプロトコルを必要とすることである。それ故、このようなＱｏＳ方式は帯域幅や待ち時間特性の変化に対して柔軟性ではなく、特性を前もって知る必要があり、さらにプロセスに必要な特性を提供するように通信チャネルの動作を構成するためのよりハイレベルのプロトコルが必要である。それ故、既存のＱｏＳ方式は通信チャネルが性能を提供すると仮定することから始り、この性能をプロセスからの予め定められた要求条件に従って割当てる。それにより予想したものよりも低い帯域幅要求条件を有するプロセスとなって不公平な性能が得られ、予め定められた特性を超える他のプロセスは性能が不足することがある。
【０００７】
これら既知のＱｏＳ方式のいくつかはネットワーク環境内で受け入れられるように作動できるが、他のタイプのシステム、たとえば、ＳｏＣでは共有通信チャネルを介して生じるデータフローはランダムとなって（たとえば、キャッシュミス等により）ダイナミックに変動することがあり、既存のＱｏＳ方式には適さない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、共有通信チャネルを介して送られるメッセージ間の調停を行う改良された技術を提供することが望ましい。
【課題を解決するための手段】
【０００９】
（発明の概要）
第１の側面から見ると、本発明は共有通信チャネルを介して送られるメッセージ間の調停を行うデータ処理装置を提供し、それは各々が受取要素に発せられるメッセージを要求するプロセスを実行する複数の処理要素と、複数の処理要素間で共有されそれを介してメッセージが送られる通信チャネルと、通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する調停回路とを含み、各処理要素はそこで実行中のプロセスに対する進捗データを発するようにされていて、進捗データはプロセスに対する待ち時間含意（ｌａｔｅｎｃｙ ｉｍｐｌｉｃａｔｉｏｎｓ）を示し、さらに、各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データが示す各プロセスの待ち時間含意を考慮した優先順位付けプロセスを実施し、かつ調停プロセスを制御するために調停回路に優先順位付けデータを出力する調停制御回路を含んでいる。
【００１０】
本発明に従って、各処理要素はそこで実行中のプロセスに対する進捗データを発するようにされており、進捗データはプロセスに対する待ち時間含意を示す。最終的に、待ち時間が特定レベルまで増加するとプロセスは停止されるが、最初に実行できる十分なバッファリングまたは他の計算があるため、これはすぐには起こらない。さらに、プロセス停止の影響はそのプロセスに非常に依存し、場合によっては破滅的となることがあるが、他のプロセスに対しては停止の影響はあまり重大ではなく、プロセスを完了するのに要する時間が延びるにすぎない。それ故、待ち時間の含意はプロセスに非常に依存し、各実行中プロセスに関して発せられる進捗データはそのプロセスに特定の待ち時間含意を示すことが理解される。
【００１１】
さらに、本発明に従って調停制御回路が提供され、それは各処理要素からの進捗データに応答して進捗データにより示される待ち時間含意を考慮した優先順位付けプロセスを実施する。このプロセスの結果として、優先順位付けデータが発生され、それはその調停回路により実施される調停プロセスを制御するためにデータ処理装置により提供される調停回路へ出力される。
【００１２】
調停回路の配置は通信チャネルの構造によって決まる。典型的に、調停を実施する必要のある多数のポイントが通信チャネル内にあり、これらの各ポイントにおいて調停をできるように調停回路は通信チャネル全体にわたって分散される。このような各ポイントにおいて、調停制御回路により出力される優先順位付けデータを使用して通信チャネル内のそのポイントに現われる多数のメッセージ間の調停が行われる。
【００１３】
本発明を使用して、個別のプロセスの要求条件を考慮して、したがって、調停のＱｏＳスタイルを採用して調停を実施することができるが、既知のＱｏＳ方式とは対照的に、このＱｏＳは自動的に決定されてプロセス間に割当てられ、要求条件を前もって知る必要性がなくなる。さらに、本発明のＱｏＳ機構はプロセス間の通信の変化にダイナミックに適応する。特に、個別プロセスからの進捗データが変化すると、それは調停制御回路により作り出される優先順位付けデータに影響を及ぼし、次に、データ処理装置の調停回路により実施される調停に影響を及ぼす。
【００１４】
通信チャネルを共有する処理要素は多様な形をとることができる。しかしながら、一実施例では、各処理要素は通信チャネルに接続されたマスター装置である。典型的に、通信チャネルを介してメッセージが発せられる受取要素はスレーブ装置であり、個別のトランザクションはマスター装置および選出されたスレーブ装置間で通信チャネルを介していくつかのリードまたはライト転送を行うためにそこでプロセスを実行する時にマスター装置により発せられる。このような実施例では、各メッセージはトランザクションを開始するためにマスター装置の１つにより発せられるアクセス要求の形をとることができる。しかしながら、メッセージの正確な形は通信チャネル上で使用されるプロトコルによって決まる。ＡＲＭ Ｌｉｍｉｔｅｄ，Ｃａｍｂｒｉｄｇｅ，Ｕｎｉｔｅｄ Ｋｉｎｇｄｏｍにより開発されたＡＸＩ（Ａｄｖａｎｃｅｄ ｅＸｔｅｎｓｉｂｌｅ Ｉｎｔｅｒｆａｃｅ）プロトコル等のバスプロトコルに対して、リードおよびライトデータはトランザクションにより指定されるアドレス転送内に記述されるメッセージの一部を形成するが、パケット化されたシステムでは要求およびデータはメッセージを構成する単一パケットの一部を形成することがある。
【００１５】
さまざまな処理要素により実行される個別プロセスは多様な形をとることができる。しかしながら、一実施例では、各プロセスはプログラム・スレッド（ｔｈｒｅａｄ）であり、各処理要素は単一プログラム・スレッドを実行する。このような実施例では、進捗データはスレッド・バイ・スレッドベースで提供される。
【００１６】
代替実施例では、少なくとも１つの処理要素が多数の処理装置を含み、各処理装置がプログラム・スレッドを実行する。この実施例では、処理要素はマルチコアプロセッサであり、進捗データが発せられる「プロセス」はその処理要素のさまざまな処理装置上で実行中のさまざまなプログラム・スレッドの全てからなっている。このようなマルチコアプロセッサを構成するもう１つの方法は個別の各処理装置を個別に処理要素と見なされるマルチコアプロセッサ内に配置して、マルチコアプロセッサ内の各処理装置がそこで実行中のプログラム・スレッドに関連するそれ自体の進捗データを出力することである。
【００１７】
データ処理装置は多様な形をとることができるが、一実施例では、ＳｏＣの形をとる。通信チャネルを介して生じるさまざまなデータフローがランダムかつダイナミックに変動するため、本発明の技術はＳｏＣ装置内で特に有益である。本発明の実施例の技術は要求条件が変動する時にさまざまなプロセスの帯域幅および待ち時間を管理するのに十分柔軟性である。
【００１８】
進捗データは多様な形をとることができる。一実施例では、進捗データは関連するプロセスがリアルタイムプロセスであるか非リアルタイムプロセスであるかを識別し、リアルタイムプロセスに対しては進捗データは少なくともそのリアルタイムプロセスにより発せられたメッセージを処理する残り時間を示すスラック（ｓｌａｃｋ）値をさらに識別し、非リアルタイムプロセスに対しては進捗データは少なくとも予め定められた時間にわたるそのプロセスに関連する待ち時間を示す待ち時間値をさらに識別する。
【００１９】
本明細書の目的に対して、リアルタイムプロセスはそのプロセスに対する停止の影響が破滅的と見なされて受け入れられない任意のプロセスと考えることができる。その例はディスプレイされた映像の混乱は受け入れられないと見なされる、画面上にディスプレイされる映像を発生しているプロセスである。対照的に、本出願の状況における非リアルタイムプロセスは停止が受け入れられる任意のプロセスを意味し、それ故、停止の影響はあまり重要ではなくプロセスの完了に要する時間が延長される。そのプロセスがリアルタイムプロセスであるか非リアルタイムプロセスであるかの表示の他に、リアルタイムプロセスに対して進捗データはそのリアルタイムプロセスにより発せられたメッセージを処理する残り時間（すなわち、プロセスが停止するまでどれだけ長いか）を示すスラック値をさらに識別する。対照的に、非リアルタイムプロセスに対しては進捗データは少なくとも予め定められた時間にわたりそのプロセスに関連する待ち時間を示す待ち時間値をさらに識別する。予め定められた時間はインプリメンテーションに応じて変動することがある設計パラメータである。予め定められた時間が長いほど、待ち時間値を作り出す時に考慮するヒストリカル情報量は大きくなり、予め定められた時間が短いほど、待ち時間値は迅速に最近の変化に応答して変化し、それ故、調停制御回路により発生される優先順位付けデータは特定のプロセスからのデマンドの最近の変化により迅速に適応する。
【００２０】
前記した情報を進捗データに内蔵することにより、調停制御回路はリアルタイムプロセスが停止しないことを保証するのに十分な優先順位付けされることを保証することができるが、リアルタイムプロセスに関連するスラック値が許す場合、非リアルタイムプロセスはそれが経験する待ち時間を低減する目的でリアルタイムプロセスよりも先に優先順位付けすることができる。各非リアルタイムプロセスに対して識別された待ち時間値が予め定められた時間にわたってそのプロセスに関連する待ち時間を示すようにすれば、全体待ち時間を非リアルタイムプロセス間で公平に割り当てることができる。
【００２１】
各非リアルタイムプロセスに関連する待ち時間値を作り出すために設けられる回路は多様な形をることができる。たとえば、各プロセスに対して、負値はプロセスを停止せずに付加できる待ち時間を示し正値は既にプロセスに付加された待ち時間をカウントする符号付２進値を維持することができる。転送に待ち時間が付加されるサイクル毎に、この２進カウントは増分することができ、２進値が正であればスレッドは停止していることを示す。次に、この停止時間を積分器内で累積することができる（積分器値は時間とともに無制限となるため、全積分器から周期的に値を減じる機構を設けることができる）。したがって、積分器により出力される待ち時間値は優先順位付けデータを発生する時に調停制御回路が使用できるスレッド間の停止時間差の情報を提供する。積分器を使用することの代替策として、非リアルタイムプロセスを実行する各処理要素にフィルタ回路を関連付けることができ、フィルタ回路は単位時間当たり待ち時間の形の待ち時間値を作り出す。それ故、このような実施例では、単純なローパスフィルタを使用して累積された停止時間を追跡することができ、各フィルタからの出力は平均ストールレート（ｓｔａｌｌ ｒａｔｅ）、すなわち、スレッドが予め定められた時間にわたって停止され基準期間を形成するサイクル数に比例する。
【００２２】
一実施例では、全ての非リアルタイムプロセスを同等に処理することができ、進捗データ内に含まれる待ち時間値は待ち時間の影響を非リアルタイムプロセス間で均一に分配することをシークするのに使用される。しかしながら、代替実施例では、少なくとも１つの非リアルタイムプロセスには重み付けが関連付けられており、その重み付けはその非リアルタイムプロセスに対する待ち時間値を作り出す時に考慮される。このような各プロセスに対する重み付けは設計時に固定することができる、またはプログラマブルとすることができるが、典型的にはダイナミックに変動しない。フィルタ回路を採用する実施例では、各非リアルタイムプロセスの重み付けはこのようなフィルタ回路により適用されるフィルタアルゴリズムに異なる重み付けを適用して実現することができる。したがって、ある非リアルタイムプロセスには高い重み付けを適用できるが他の非リアルタイムプロセスには低い重み付けが適用され、調停制御回路により優先順位付けプロセスが実施されている時に、ある非リアルタイムプロセス（すなわち、より高い重み付けのプロセス）が他の非リアルタイムプロセスよりも好まれることがある。例として、これによりオーディオストリームを発生するプロセスは、そのプロセスの停止によりオーディオが非常にまれに混乱することが受け入れられれば、非リアルタイムプロセスと見なすことができ、そのプロセスに関してその時高い重み付けが適用されなければ、そのプロセスに関して出力される待ち時間値は他の重要度の低い非リアルタイムプロセスに較べて比較的迅速に増加し、調停制御回路内で優先順位付けプロセスを実施している時にそのオーディオストリーム・プロセスを優先順位の低い非リアルタイムプロセスよりも先に優先順位付けするようにされる。
【００２３】
一実施例では、データ処理装置はさらにリアルタイムプロセスを実行中の各処理要素に関連するカウンタ回路を含み、カウンタ回路は前記スラック値を作り出している。それ故、一実施例では、そのプロセスによりメッセージが発せられる時（たとえば、トランザクションが開始する）カウンタ回路はカウンタを特定の値にセットすることができ、そのカウンタ値は次に時間とともにスラック値が減少するように各クロックサイクルで減分される。スラック値が比較的高い間、調停制御回路により実施される優先順位付けプロセスはある非リアルタイムプロセスをリアルタイムプロセスよりも先に優先順位付けすることができるが、そこで優先順位付けプロセスがリアルタイムプロセスをこのような非リアルタイムプロセスよりも先に優先順位付けするレベルまでスラック値が減少するポイントとなる。
【００２４】
一実施例では、非リアルタイムプロセスに対して進捗データはそのプロセスが停止されるか否かを識別するストール値をさらに識別する。特定の一実施例では、これは１ビット値の形をとることができ一方の値はプロセスが停止されることを示し他方の値はそれが停止されないことを示す。特定の一実施例では、このストール値は待ち時間値を作り出すのに使用されるフィルタ回路への入力としても使用することができる。
【００２５】
一実施例では、非リアルタイムプロセスに対して進捗データはプロセスが停止する前にそのプロセスにより発せられるメッセージの残りの処理時間を示すスラック値をさらに識別する。それ故、非リアルタイムプロセスが事前にトランザクションを開始する（すなわち、プロセスはそのトランザクションの結果が要求される前にまだある期間継続することができる）状況では、プロセスが停止する前の残り時間を識別する進捗データ内にスラック値を含めることができ、調停制御回路は優先順位付けプロセスを実施する時にこの情報を考慮することができる。
【００２６】
優先順位付けプロセスは多様な方法で構成することができる。しかしながら、一実施例では、そのリアルタイムプロセスにより発せられるメッセージの残りの処理時間が予め定められた閾値よりも大きいことをそのリアルタイムプロセスのスラック値が示す場合、優先順位付けプロセスはリアルタイムプロセスよりも非リアルタイムプロセスに優先順位を与える。それ故、リアルタイムプロセス内のスラックが許す場合、非リアルタイムプロセスはリアルタイムプロセスよりも先に優先順位付けされて、リアルタイムプロセスにいかなる実際の影響も及ぼすことなく、これらの非リアルタイムプロセスにより経験される待ち時間を低減することができる。
【００２７】
一実施例では、優先順位付けプロセスは低い待ち時間値を有する非リアルタイムプロセスよりも高い待ち時間値を有する非リアルタイムプロセスに優先順位を与える。これらの待ち時間値はプロセスに関連する待ち時間が予め定められた時間を超えることを示すため、それにより非リアルタイムプロセスを横切して待ち時間を公平に配分することができる。
【００２８】
一実施例では、異なるストール値を有する２つの非リアルタイムプロセスに対して、優先順位付けプロセスはより高い待ち時間値を有するプロセスに優先順位を与えることよりも優先的にそのプロセスが停止されることをそのストール値が示す非リアルタイムプロセスに優先順位を与える。それ故、このような方法は任意の非リアルタイムプロセスが停止される時間を低減するようにシークする。
【００２９】
一実施例では、異なるスラック値を有する２つの非リアルタイムプロセスに対して、優先順位付けプロセスはより高い待ち時間値を有するプロセスに優先順位を与えることよりも優先的に最少スラックを有する非リアルタイムプロセスに優先順位を与える。このような方法は可能な所で非リアルタイムプロセスが停止する尤度を低減するようにシークする。
【００３０】
各処理要素により作り出される進捗データの主目的は優先順位付けプロセスを実施する時に調停制御回路がサービス品質要件を考慮できるようにすることであるが、進捗データの若干をデータ処理装置の他の部分で再使用できることも判っている。たとえば、データ処理装置にエネルギ管理回路を設けて装置のさまざまなコンポーネントが動作するパフォーマンスレベルを制御することが知られている。このようなデータ処理装置は典型的に実行時に異なる動作パフォーマンスレベル間で切り替わることができる。低いパフォーマンスレベルは軽いワークロードを実行するときにエネルギ（消費電力）を節減するために選出され、高いパフォーマンスレベルはより処理集約的ワークロードに対して選出される。典型的に、データ処理装置内の処理要素がｃｏｍｐｌｉｍｅｎｔａｒｙ ｍｅｔａｌ−ｏｘｉｄｅ ｓｅｍｉｃｏｎｄｕｃｔｏｒ（ＣＭＯＳ）技術でインプリメントされる場合、低いパフォーマンスレベルは低い周波数および動作電圧設定を意味する。
【００３１】
データ処理装置がこのようなエネルギ管理回路を含む一実施例では、これらの処理要素に対する動作パフォーマンスレベルを決定する時にエネルギ管理回路は１つ以上の処理要素により発せられる進捗データの少なくとも一部を考慮するようにされる。特定の一実施例では、エネルギ管理回路は非リアルタイムプロセスを実行中の１つ以上の処理要素により出力される待ち時間値を考慮する。
【００３２】
第２の側面から見て、本発明は各処理要素が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素と、複数の処理要素間で共有されそれを介してメッセージが送られる通信チャネルとを有するデータ処理装置の通信チャネルを介して送られるメッセージ間の調停方法を提供し、この方法は各処理要素からその上で実行中のプロセスに対する進捗データを発するステップであって、進捗データはプロセスに対する待ち時間含意を示すステップと、各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施するステップと、通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施するステップであって、優先順位付けデータは調停プロセスを制御するのに使用されるステップと、を含んでいる。
【００３３】
第３の側面から見て、本発明はデータ処理装置用調停制御回路を提供し、データ処理装置は各々が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素と、複数の処理要素により共有されそれを介してメッセージが送られる通信チャネルと、通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する調停回路とを有し、調停回路はその処理要素上で実行中のプロセスに対する進捗データを各処理要素から受信する入力インターフェイスであって、進捗データはプロセスに対する待ち時間含意を含む入力インターフェイスと、各処理要素からの進捗データに応答して優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施する優先順位付け回路と、調停プロセスを制御するために優先順位付けデータを調停回路に出力する出力インターフェイスと、を含んでいる。
【実施例】
【００３４】
（実施例の説明）
単なる例として添付図に例示されている実施例について本発明をさらに説明する。図１は本発明の一実施例に従ったデータ処理装置のブロック図である。この実施例では、データ処理装置は通信チャネル４０を介していくつかのスレーブ装置５０，６０，７０に接続されたいくつかのマスター装置１０，２０，３０を含むＳｏＣの形をとる。本発明の実施例を検討する目的に対してこのようなＳｏＣ装置が考慮されるが、当業者ならば本発明の実施例の技術は通信チャネルが複数の処理要素間で共有される多種多様な異なるシステムに応用できることが
理解される。
【００３５】
図１のＳｏＣ例について考えると、通信チャネル４０は典型的にＳｏＣ内の多数のバスマスター装置１０，２０，３０およびバススレーブ装置５０，６０，７０を相互接続するための接続のマトリクスを提供するいくつかの相互接続されたバスを含む相互接続ブロックの形をとる。
【００３６】
通信チャネルを形成するバスは典型的に指定されたバスプロトコルに従って動作し、それ故、たとえばＡＲＭ社により開発された“Ａｄｖａｎｃｅｄ Ｍｉｃｒｏｃｏｎｔｒｏｌｌｅｒ Ｂｕｓ Ａｒｃｈｉｔｅｃｔｕｒｅ”（ＡＭＢＡ）に従って動作することができる。
【００３７】
したがって、通信チャネル４０はさまざまなマスターおよびスレーブ装置間の相互接続の複雑な構成からなることが理解される。通信チャネル内のさまざまなポイントにおいて、特定のパスの使用を奪い合う多数のメッセージ間の調停を行う調停回路を設ける必要がある。
【００３８】
各マスタ１０，２０，３０はその間にさまざまなトランザクションが通信チャネル４０を介して開始されるプロセスを典型的に実行する。このようなトランザクションによりマスタからスレーブへ（ライトトランザクションの場合）またはスレーブからマスターへ（リードトランザクションの場合）データを送ることができ、各トランザクションは通信チャネル上へアクセス要求を発するマスター装置により開始される。各アクセス要求はメッセージを形成すると考えられ、通信チャネル内の調停回路は多数のメッセージが特定のパスの使用を奪い合うバスインフラストラクチュア内の任意のポイントで調停を実施する必要がある。
【００３９】
したがって、調停回路は通信チャネル全体にわたって分散された複数の調停要素からなるものと考えられ、このような各調停要素が多数のメッセージ間の調停を行う調停プロセスを実施する。本発明の実施例に従って、各調停要素により実施される調停プロセスは、それぞれ、対応するパス１２，２２，３２を介して各マスター装置１０，２０，３０により出力される進捗情報を入力インターフェイス８２において受信するようにされた調停制御回路８０により決定される。後述するように、この進捗データは各マスター装置上で実行中のプロセスに対する待ち時間含意を示し、その進捗データは調停制御回路内の優先順位付け回路８４へ転送され、そこで優先順位付けデータを発生するためにその進捗データを考慮して優先順位付けプロセスが実施される。その優先順位付けデータは、次に、プロセスの優先順位付けされたリストとして出力インターフェイス８６を介して出力され、そのリストは通信チャネル内の全調停要素（ここでは、アービター（ａｒｂｉｔｅｒｓ）とも呼ばれる）へ送られる。この優先順位付けされたリストを広めることができる多様な方法がある。一実施例では、それはメッセージを送るのに使用されるのと同じパスを介して広めることができ、代替実施例では、この優先順位付けされたリストは独立した専用バス構造により広めることができる。次に、各アービターは提供された優先順位リストに基づいてその調停プロセスを実施する。
【００４０】
調停制御回路８０はこの優先順位付けされたリストを予め定められた間隔で更新するように構成することができる。一般的に言えば、優先順位付けされたリストは調停制御回路への任意の入力が変化する時は常に更新しなければならない。典型的に、進行中のトランザクションがあまり無いか全く無い場合を除き、これによりリストは各クロックサイクルで更新される。
【００４１】
図２Ａはマルチコアプロセッサ１００を図１のデータ処理装置内に収容することができる１つの方法を例示するブロック図である。マルチコアプロセッサ１００はプロセッサ１００内の内部通信チャネル１５０を介して相互接続される複数のプロセッサコア１１０，１２０，１３０，１４０を有する。次に、マルチコアプロセッサ１００はそれを介してさまざまなスレーブ装置５０，６０，７０と通信することができる外部通信チャネル１６０に接続される。一実施例では、図１の通信チャネル４０はマルチコアプロセッサ１００の内部通信チャネル１５０とマルチコアプロセッサ外部の通信チャネル１６０の両方を包含するものと見なすことができ、実質的に各プロセッサコア１１０，１２０，１３０，１４０は各々がそれら自体の進捗情報を調停制御回路８０へ発する独立したマスター装置を形成すると見なすことができる。一実施例では、このような各プロセッサコア１１０，１２０，１３０，１４０が独立したプログラム・スレッドを実行し、したがって、任意特定のコアから出力される進捗情報は関連するスレッドに対する待ち時間含意を示す。
【００４２】
図２Ｂに例示するように、代替実施例では、マルチコアプロセッサの内部は調停制御回路から隠すことができ、替わりにマルチコアプロセッサの全体が単一マスター装置、この例ではマスター装置１０、として見られる。したがって、マスター装置１０がマルチコアプロセッサである状況においてパス１２を介して調停制御回路へ出力される進捗情報は全体としてマルチコアプロセッサにより実施される「プロセス」に対する待ち時間含意を提供し、それ故、各個別コア１１０，１２０，１３０，１４０により実行される各個別スレッドに対する待ち時間含意を直接提供することはない。
【００４３】
図３Ａはさまざまなタイプの非リアルタイムプロセスに対する時間対待ち時間コストを例示する図である。線「ａ」２００は必要な時にデータを要求するプロセスを処理要素が実行する時に生じる待ち時間コストの形を示すが、通信チャネル４０を介して任意のアクセス要求が発せられる前に内部遅延が生じる。これは、たとえば、マスター装置が内部キャッシュ、ブラックボックスシステム、等を有するプロセッサであるケースである。キャッシュを有するプロセッサの例を考えると、プロセッサによりアクセス要求が発せられると、最初にキャッシュ内でルックアップが実施されてアクセス要求の対象であるデータがキャッシュ内にあるかどうか決定される。無ければ、キャッシュミスが生じ、通信チャネル４０上にアクセス要求が生じる。線２００に関連して図３Ａに点線で示すように、非リアルタイムプロセスにより観察される待ち時間は通信チャネル４０上に任意のアクセス要求が現われる前に既に増加しており、時間ゼロにおいて通信チャネル上にアクセス要求が現われると、待ち時間コストは既に正値であるようにされる。
【００４４】
対照的に、線「ｂ」２１０はそのプロセスが必要な時にデータを要求する処理要素に対して観察されるタイプの線を示し、要求は即座に通信チャネル４０上に現れる。このような処理要素の例は、たとえば、Ｄｉｒｅｃｔ Ｍｅｍｏｒｙ Ａｃｃｅｓｓ（ＤＭＡ）コントローラである。
【００４５】
線「ｃ」２２０はそのプロセスが事前にデータを要求する処理要素に対して観察されるタイプの線を示す。それ故、この例では、要求は時間ゼロにおいて通信チャネル４０上に現われるが、プロセスは他の有用な作業をできるため、時間ｔ１に達するまで正の待ち時間コストは無い。したがって、プロセスが実際に停止するのはやっと時間ｔ１においてである。対照的に、線２１０に関連するプロセスに対して、そのプロセスは時間ゼロで停止し、線２００に関連するプロセスに対しては、時間ゼロにおいて通信チャネル４０上に要求が現われる前であってもプロセスは停止する。
【００４６】
したがって、線２００および２１０に関連するプロセスにはスラック時間は無いことが判るが、線２２０に関連するプロセスはそのプロセスにより通信チャネル４０上に発せられるメッセージをそのプロセスを停止させずに処理できるいくらかのスラック時間を有する。
【００４７】
本発明の一実施例では、非リアルタイムプロセスを実行する任意のマスター装置により発せられる進捗情報の一部はプロセスが停止される時にセットされプロセスが停止されない時にリセットされるストールビット（ｓｔａｌｌ ｂｉｔ）である。図３Ｂは図３Ａの３本の線の例に対するこのストールビットのプロファイルを示す。この例では、セット状態は論理１値で示されリセット状態は論理０値で示されるものと仮定する。図３Ｂからお判りのように、線ａに関連するプロセスはポイント２０５において停止し、したがって、ストールビットはそのポイントにセットされる。同様に、線ｂに関連するプロセスはポイント２１５において停止しまた線ｃに関連するプロセスはポイント２２５において停止し、したがって、ストールビットはポイント２１５，２２５において、それぞれ、遷移する。
【００４８】
線ａに関連するプロセスについて考えると、要求は通信チャネル４０上に発せられる必要なしに処理要素内でサービスされる。たとえば、前記したキャッシュを有するプロセッサの例について考えると、キャッシュヒットが生じると、通信チャネル４０を介してアクセス要求を伝搬させる必要なしにキャッシュに関してアクセスが進行する。したがって、点線２０７で示すように、このような状況においてストールビットは２０５において論理１値に遷移するが、アクセス要求がサービスされていると、次に、論理０値へ遷移し戻る。一実施例では、任意特定のアクセス要求が通信チャネル４０上に発せられているかどうかに拘わらず、ストールビットはまだ進捗情報の一部として出力され、実際に、一実施例ではそのプロセスに対する待ち時間情報を発生するのに使用されるフィルタへの入力として使用される。それ故、調停制御回路８０にはその停止の原因に無関係に任意特定のマスター装置のプロセスが停止される時間の割合に関する情報が提供され、特に、通信チャネル４０を介して導入される待ち時間の結果として停止が生じる状況に限定はされない。
【００４９】
図４はリアルタイムプロセスの待ち時間コストを例示する図３Ａと同様な図である。前記したように、本出願の目的のために、リアルタイムプロセスはプロセスのいくらかの停止は受け入れられる非リアルタイムプロセスとは対照的に、そのプロセスが停止することは受け入れられないプロセスである。したがって、停止することが許されないとすると、リアルタイムプロセスは典型的に事前にデータを要求し、曲線がパス２５０に従っている間、そのリアルタイムプロセスに関連するスラック時間がある。しかしながら、この場合、スラック時間はそのリアルタイムプロセスにより発せられたメッセージを処理するための残り時間を示し、スラック時間が尽きると垂直線２６０で示すように待ち時間コストは無限大となる。
【００５０】
図５は本発明の一実施例に従ったマスター装置１０，２０，３０により発せられる進捗情報のさまざまなコンポーネントを例示している。特に、図５の例では、マスター１０は非リアルタイムスレッドを実行しており、マスター２０は非リアルタイムスレッドを実行しているが、マスター３０はリアルタイムスレッドを実行しているものと仮定する。一実施例では、非リアルタイムスレッドを実行している各マスター装置は進捗情報に対して４つのコンポーネントを出し入れするようにされている。特に、プロセスは非リアルタイムスレッドであることを識別するリアルタイムビット信号がパス２００，２２０を介して発せられる。本例では、これはリアルタイムビットをゼロにセットして例示されている。さらに、非リアルタイムスレッドに関連する任意のスラック時間を識別するスラック値がパス２０５，２２５を介して出力される。図３Ａの待ち時間コストグラフに関して、このスラック値は任意の負の待ち時間コスト値で表せることが理解される。特に、線ｃ２２０について考えると、負の待ち時間コストの大きさは時間ゼロの特定の値で始り、時間ｔ１においてゼロの値に達するように、そのプロセスに関連するスラック時間中にゼロまで漸減する。
【００５１】
さらに、図５に示す実施例では、現在の時間において関連するプロセスが停止されるか否かを識別するストールビットがパス２１０，２３０を介して出力される。このストールビットはローパスフィルタ２１５，２３５にも入力されて待ち時間値を発生しパス２２０，２４０を介して出力させ、この待ち時間値は単位時間当たり遅延を表す。一実施例では、各ローパスフィルタ２１５，２３５は累積されたストール時間を追跡する単純な単極ローパスフィルタである。特に、一実施例では、ローパスフィルタは待ち時間値ｙを発生するために下記の等式をインプリメントすることができ、
ｙｋ＝α．ｙｋ−１＋ｘｋ（１−α）
ここに、ｙは待ち時間値であり、αは選出された定数であり、ｋは時点でありｘはストールビット値である。
【００５２】
したがって、待ち時間値ｙは平均ストールレート、すなわち基準期間にわたってスレッドが停止されるサイクル数、に比例し基準期間は定数αの選択によって決まる。
【００５３】
リアルタイムスレッドに対して、進行情報はやはりパス２５０を介して出力されるリアルタイムビットを含み、ここではリアルタイムビットはスレッドがリアルタイムスレッドであることを示す論理１値にセットされ、さらに、カウンタ２５５からパス２６０を介して出力されるスラック値を含んでいる。特に、リアルタイムスレッドがアクセス要求を出力する場合、カウンタ２５５はそのアクセス要求に応答するクロックサイクル数を表すある予め定められた値にセットされ、各クロックサイクルが経過するとカウンタは減分されてスラック値を時間とともに減少させる。
【００５４】
図５に例示されたさまざまな進捗情報に基づいて、一実施例の調停制御回路８０は次に、図６に示すように、各スレッドに対するデータ構造のテーブル３００を維持する。フィールド３０５に入ったスレッドＩＤにより示される各スレッドに対して、リアルタイムビット、ストールビット、フィルタ出力の値およびスラック値が、それぞれ、フィールド３１０，３１５，３２０，３２５内に格納される。特定のスレッドに対して情報のサブセットしか提供されなければ、１つ以上のフィールドはブランクのままとされる。たとえば、リアルタイムスレッドについて考えると、ストールビットやフィルタ出力はない。
【００５５】
次に、調停制御回路８０は優先順位付け回路８４を利用して各スレッドに関連するデータ構造を考慮したプロセス（スレッド）の優先順位付けされたリストを発生する。当業者ならば、一連のデータ構造が提示される時に順序付けされたリストを形成するためのいくつかの既知の技術があり、しばしばこれらのプロセスはデータ構造の選出された対に対する比較プロセスの反復実施を伴うことが理解される。１つのこのような機構は既知の「バブルソート（ｂｕｂｂｌｅ ｓｏｒｔ）」機構であり、それはソートされるリスト中を反復ステッピングし、一時に２つのデータ構造を比較し誤った順序であればそれらをスワッピングすることで働く。リストをパススルーすることはスワップが必要とされなくなるまで繰り返され、それはリストがソートされることを意味する。
【００５６】
図７はどのスレッドが他よりも優先順位を有するか判断するためにスレッドの選出された対（ここではスレッドＸおよびＹと表示されている）がどのように比較されるかを略示している。図７に示すように、両方のスレッドに対してリアルタイムビットがセットされると（すなわち、両方のスレッドがリアルタイムスレッド）、最少スラックのスレッドに優先順位が与えられる、すなわち最も早いデッドラインを有するスレッドに優先順位が与えられ、このような優先順位付け技術はしばしば“ｅａｒｌｉｅｓｔ ｄｅａｄｌｉｎｅ ｆｉｒｓｔ”優先順位付けと呼ばれる。しかしながら、スレッドＸが非リアルタイムスレッドでありスレッドＹがリアルタイムスレッドであれば、図７の右上隅に示すようにスレッドＹに対するスラック時間が予め定められた値Ｎよりも大きければ優先順位はスレッドＸに与えられる。したがって、優先順位は自動的にリアルタイムスレッドには与えられず、リアルタイムスレッドに対するスラック時間が比較的大きければ、その非リアルタイムスレッドの待ち時間の低減をシークするために優先順位は非リアルタイムスレッドに与えられる。スラック時間が切れる前にリアルタイムスレッドがサービスされると悪い結果は生じないため、これはリアルタイムスレッドに悪影響を及ぼさない。
【００５７】
同様に、スレッドＹが非リアルタイムスレッドでありスレッドＸがリアルタイムスレッドであれば、図７の左下側に示すように、スレッドＸに対するスラック時間が予め定められた値Ｎよりも大きければ優先順位はスレッドＹに与えられる。
【００５８】
両方のスレッドが非リアルタイムスレッドであれば、判断ステップは図７の右下側に示すものとなる。特に、両方のリアルタイムスレッドに対するストールビットが最初に考慮される。両方のスレッドに対するストールビットがゼロであれば、いずれのスレッドも停止されないことを意味し、優先順位は最少スラックのスレッド、すなわち最も迅速に停止するスレッド、に与えられる。一方のスレッドのストールビットがセットされ他方はセットされなければ、優先順位はストールビットがセットされているスレッドに与えられる、すなわち優先順位は既に停止しているスレッドに与えられる。最後に、両方のスレッドのストールビットがセットされておれば、優先順位はフィルタ出力の最も高いスレッド、すなわち、基準期間にわたりより高い平均ストールレートを有するスレッドに与えられる。
【００５９】
ある実施例では、図５について前記した進捗情報の全アイテムを提示する必要はない。たとえば、ある実施例では非リアルタイムスレッドに対してスラック値は手に入らないことがある。その場合、２つの非リアルタイムスレッドが考慮されていて両方の非リアルタイムスレッドがそれらのストールビットをゼロに等しくセットしておれば、優先順位はフィルタ出力の最も高いスレッドに与えられる、すなわち両方のスレッドがそれらのストールビットを１に等しくセットしている場合に適用されるのと同じ優先順位付けが適用される。
【００６０】
一実施例において、あるスレッドがストールビットを提供しなければ、そのストールビットはセットされる、すなわち論理１値を有するものと仮定される。
【００６１】
図８は優先順位付けされたリストを作り出すために一実施例に従って図８の調停制御回路８０により実施される一般的プロセスを例示している。ステップ４００において、スレッドの初期順序付けが準備される。最初の反復において、これは任意順序付けとすることができるが、後続反復に対しては初期順序付けはプロセスにより作り出された前の順序付けとなることがある。その後、プロセスはステップ４０５に進み、そこで一対のスレッドが選出され、その後ステップ４１０において図９についてより詳細に説明するように順序付けプロセスが適用される。この順序付けプロセスは図７について略示した優先順位付け方式をインプリメントする。
【００６２】
その後、ステップ４１５において、スレッドの順序付けは順序付けプロセスの結果に応じて修正され、その後ステップ４２０において順序付けプロセスを適用すべきスレッド対がまだあるのか決定される。プロセスを介した最初の反復では、典型的にスレッド対の組合せ毎に順序付けプロセスを行う必要がある。しかしながら、後続反復では、進捗情報の何の特徴が変更されているか、またどのスレッドの進捗情報が変更されているかに応じて、可能な全スレッド対のサブセットに順序付けプロセスを適用するだけでよい。ステップ４２０において順序付けプロセスを適用する必要のある少なくとももう１対のスレッドがあると判断されると、プロセスはステップ４０５へ戻り、順序付けプロセスを行うべき対はもう無いと判断されると、プロセスはステップ４２５へ進み、そこでスレッドの修正された順序付けが優先順位付けされたリストとして通信チャネル４０内の全アービターに出力される。
【００６３】
例示する目的でステップ４０５，４１０，４１５および４２０が順次示されているが、順序付けプロセスを行う必要がある全ての対が識別されるように、これらのステップは実際上並列に処理することができ、次に、スレッドの修正された順序付けを作り出すために順序付けプロセスは並列に適用されることに留意しなければならない。
【００６４】
図９は本発明の一実施例に従って図８のステップ４１０において実施されるステップを示すフロー図である。ステップ５００において、両方のスレッドがリアルタイムスレッドであるかどうか決定され、そうであればステップ５０５においてスレッドはｅａｒｌｉｅｓｔ ｄｅａｄｌｉｎｅ ｆｉｒｓｔ原理に従って優先順位付けされる。
【００６５】
ステップ５００において両方のスレッドがリアルタイムでないと決定されると、ステップ５１０において一方のスレッドがリアルタイムスレッドであるかどうか決定され、そうであればプロセスはステップ５１５へ進みそこでリアルタイムスレッドのスラックが予め定められた値Ｎよりも大きければ非リアルタイムスレッドに優先順位が与えられる。そうでなければ、リアルタイムスレッドが優先順位付けされる。
【００６６】
ステップ５１０においていずれのスレッドもリアルタイムスレッドではないと決定されると、プロセスはステップ５２０へ進みそこで両方のスレッドのストールビットがゼロに等しいかどうか、すなわち両方のスレッドにまだいくらかのスラックが残っているかどうか決定される。両方のスレッドがまだいくらかのスラックを有すると仮定すると、プロセスはステップ５２５へ進みそこでスラック値が手に入るかどうか決定され、手に入ればプロセスはステップ５３０へ進みそこでスレッドはｅａｒｌｉｅｓｔ ｄｅａｄｌｉｎｅ ｆｉｒｓｔ原理に従って優先順位付けされる、すなわち最少スラックのスレッドに優先順位が与えられる。しかしながら、ステップ５２５においてスラック値が手に入らないと決定されると、プロセスは５３５に進み、フィルタ出力の最も高いスレッドに優先順位が与えられる。
【００６７】
ステップ５２０において両方のスレッドのストールビットがゼロに等しくないと決定されると、ステップ５４０において一方のスレッドに対するストールビットがゼロに等しいかどうか、すなわち一方のスレッドがスラックを有するかどうか決定される。そうであれば、プロセスはステップ５４５へ進みそこでスラックの無いスレッド（すなわち、そのストールビットが１に等しいスレッド）に優先順位が与えられる。
【００６８】
ステップ５４０においていずれのストールビットもゼロにセットされない、すなわち、両方のスレッドがストールされると決定されると、プロセスはステップ５５０へ進みそこでフィルタ出力の最も高いスレッドに優先順位が与えられる。
【００６９】
図９の前記説明から、図９のプロセスは図７に略示された選出基準をインプリメントすることが判る。
【００７０】
一実施例では、異なる重み付けをこれらのスレッドのせいにしてある非リアルタイムスレッドを他の非リアルタイムスレッドよりも優先的に処理することができる。実際上、これらの重み付けは非リアルタイムスレッドを実行中の各処理要素に提供される関連するローパスフィルタ２１５，２３５により適用することができる。その結果、より高い重み付けを有するプロセスに対して、ストールビットがセットされる度に、関連するローパスフィルタからの出力待ち時間値はより低く重み付けされたプロセスに対する場合よりも大量に増加される。したがって、図７について略示された選出基準を適用する時に、フィルタ出力の最も高いスレッドに優先順位を与えるべきであると決定され、次に、全てが等しいため、より高い重み付けのスレッドはより高いフィルタ出力を有しより低い重み付けのスレッドよりも先に優先順位付けされる。それ故、フィルタからの出力を重み付けすることにより、さまざまな非リアルタイムスレッドの優先順位を処理するためのさらなる柔軟性が提供される。
【００７１】
本発明の実施例の前記した技術はマスター装置上で実行中のさまざまなスレッドに適用される最大待ち時間の低減をシークすることが理解される。これにより各プロセスが有用な作業を行うことができる有用なクロックサイクル数が比例して増加する。その結果実際に必要なものよりも良い性能が提供されると、マスター装置またはこれらのマスター装置により共有される通信チャネルの動作パフォーマンスレベルを低減することによりトータル待ち時間を増加する機会ができる。
【００７２】
特に、いくつかの最新システムはシステム内のあるコンポーネントのパフォーマンスレベルを、典型的にはこれらのコンポーネントの周波数および／または動作電圧を変えることにより、変えることができるエネルギ管理技術を提供する。典型的に、このようなパフォーマンスレベル設定はシステム内のエネルギ管理コントローラにより実施される。
【００７３】
前記した観察が与えられると、本発明の一実施例において、さまざまなマスター装置により出力される進捗データのある側面もこのようなエネルギ管理コントローラへの入力として送られる。図１０はこのような実施例を略示しており、図からお判りのように、パス１２，２２，３２を介して出力される進捗データのいくらかもエネルギ管理コントローラ６００への入力として、それぞれ、パス６０２，６０４，６０６を介して送ることができる。特定の一実施例では、任意の非リアルタイムスレッドにより出力される待ち時間値がエネルギ管理コントローラ６００へ送られる。この情報はさまざまな方法で使用することができる。
【００７４】
たとえば、特定のマスター装置の動作周波数が数千サイクル／ミリ秒であり、１００ストールサイクル／ミリ秒であることを待ち時間値が示す場合、これはマスター装置が９００有用サイクル／ミリ秒を有することを意味する。実際上、そのプロセスを満足に実行するのにマスター装置が６００有用サイクル／ミリ秒しか必要としなければ、そのマスター装置が必要とする６００有用サイクル／ミリ秒を提供しながらエネルギを節減するためにそのマスター装置に供給される周波数および／または動作電圧を低減することができる。パフォーマンスレベルを変えることができる粒度に応じて、このプロセスを各マスター装置に対して順次独立して実施することができる。
【００７５】
替わりに、または、さらに、通信チャネル４０のパフォーマンスレベルをエネルギ管理コントローラにより変えることができれば、エネルギ管理コントローラ６００はさまざまなマスター装置から受信した最高待ち時間値を選出し、その最高値に関係する通信チャネルのパフォーマンスレベルを調節することができる。それにより、さまざまなマスター装置上で実行中のプロセスが満足に動作し続けることを保証しながら、通信チャネルの動作周波数を低減することができる。本質的に、エネルギ管理コントローラはシステムおよびその上で実行していアプリケーションに受け入れられる基準スレッドストールレートを目指して通信チャネルのクロック速度を調節することができる。
【００７６】
本発明の前記した実施例によりＱｏＳを決定してスレッド間に自動的に割り当てることができ、要求条件を前もって知る必要がなくなり、ＱｏＳはスレッド間の通信における変化にダイナミックに適応する。
【００７７】
本発明の実施例のＱｏＳ方式は通信チャネルインプリメンテーションに対する基準パフォーマンスレベルを提供するのに使用することもできる。特に、メモリコントローラ等のコンポーネントのアーキテクチュア内で比較を行うことができ、パイプライニングステージを付加してこのタイプの調停方式を実現するコストをメモリコントローラにアクセスする全スレッドに待ち時間のサイクルを付加するコストに対して比較することができる。
【００７８】
特定の実施例について説明してきたが、本発明はそれに限定されるものではなく発明の範囲内でそれに多くの修正および追加を行うことができる。たとえば、本発明の範囲を逸脱することなく従属項の特徴を独立項の特徴とさまざまに組み合わせることができる。
【図面の簡単な説明】
【００７９】
【図１】本発明の一実施例に従ったデータ処理装置のブロック図である。
【図２Ａ】図１のデータ処理装置内にマルチコアプロセッサを収容する１つの方法を例示するブロック図である。
【図２Ｂ】図１のデータ処理装置内にマルチコアプロセッサを収容する代替方法を例示するブロック図である。
【図３Ａ】異なるタイプの非リアルタイムプロセスに対する時間対待ち時間コストを例示する略図である。
【図３Ｂ】図３Ａに例示された異なるプロセスに対して本発明の一実施例に従って発せられるストールビットの値を例示する図である。
【図４】リアルタイムプロセスに対する時間対待ち時間コストを例示する略図である。
【図５】本発明の一実施例に従って図１の調停制御回路へ各マスター装置により発せられる進捗情報のさまざまなコンポーネントを例示する図である。
【図６】本発明の一実施例に従って図１の調停制御回路内に維持できるデータ構造を例示する図である。
【図７】本発明の一実施例に従って２つのスレッドに関して図１の調停制御回路により適用される順位付けプロセスを例示する略図である。
【図８】本発明の一実施例に従って図１の調停制御回路により適用される優先順位付けプロセスを例示するフロー図である。
【図９】本発明の一実施例に従って選出された一対のスレッドに順位付けプロセスを適用するために実施されるステップをより詳細に例示するフロー図である。
【図１０】本発明の一実施例に従って図１のさまざまなマスター装置により発せられる進捗データの少なくとも一部をどのようにしてデータ処理装置内のエネルギ管理制御回路にも送ることができるかを例示するブロック図である。
【符号の説明】
【００８０】
１０，２０，３０ マスター装置
１２，２２，３２，２００，２０５，２１０，２２０，２２５，２３０，２５０，２６０，６０２，６０４，６０６ パス
４０，１６０ 通信チャネル
５０，６０，７０ スレーブ装置
８０ 調停制御回路
８２ 入力インターフェイス
８４ 優先順位付け回路
８６ 出力インターフェイス
１００ 外部通信チャネル
１１０，１２０，１３０，１４０ プロセッサコア
１５０ 内部通信チャネル
２１５，２３５ フィルタ
２５５ カウンタ
６００ エネルギ管理コントローラ
【技術分野】
【０００１】
（発明の分野）
本発明は通信チャネルを介して送られるメッセージ間の調停を行う、特に、複数の処理要素間で共有される通信チャネルを介して送られるメッセージ間の調停を行うデータ処理装置および方法に関する。
【背景技術】
【０００２】
（従来技術の説明）
通信チャネルが複数の処理要素間で共有され、さまざまな処理要素が通信チャネルを介して受取要素へメッセージを発する多くのシステムがある。通信チャネルはいくつかのマスタ装置をシステム・オン・チップ（ＳｏＣ）装置等のチップ内のいくつかのスレーブ装置と接続する、またはマルチチップ・モジュール内の個別のチップと接続する、さらには印刷回路板構造内のさまざまなモジュールと相互接続するのに使用されるバス相互接続回路の形をとることができる。より大きい規模で、通信チャネルは複数のコンピュータ、または複数の装置を相互接続するのに使用される共有無線リンクにより形成することができる。
【０００３】
任意の通信チャネルに対して、そのチャネルの情報搬送容量には限界があり、通信チャネルに関連する待ち時間（ｌａｔｅｎｃｙ）もある。並列化技術および高められた動作周波数の使用等の、チャネル容量および待ち時間を変更できるようにする構成上のオプションがある。しかしながら、これらの技術は複雑さ、電力およびエリアにコストを要し、それらは必要な性能に対して取引する必要がある。
【０００４】
通信チャネルが複数の処理要素間で共有され、これらの処理要素は処理を実行する時に通信チャネルを介してメッセージを発する必要がある任意のシステムにおいて、通信チャネルが共有される事実により通信チャネルを介して処理されるメッセージの順序に関して判断を行うことが強制され、この判断は調停技術を利用して行われる。ＳｏＣの例について考えると、メッセージはトランザクション中にマスタ装置により発せられる信号の形をとることができ、特に、マスタ装置はトランザクションに関連するスレーブ装置を指定する通信チャネル上にアクセス要求を発することで典型的にトランザクションを開始する。この特定の分野において、トランザクションのある順序付けにより全体待ち時間は他の順序付けよりも低くなり、これはメモリコントローラ等の装置がしばしば特殊化するエリアであることが知られている。しかしながら、調停判断の結果そのメッセージが引き止められているプロセスが経験する待ち時間が調停判断により必然的に付加される。したがって、この調停判断が行われる方法はシステムの全体性能に有意の影響を及ぼす。
【０００５】
基本的な調停方式は固定優先順位すなわちラウンドロビン（ｒｏｕｎｄ ｒｏｂｉｎ）（公平共有）技術を利用するアルゴリズムを使用する。このような方式はメッセージ・バイ・メッセージベースの調停判断を行うのに限定され、過去になされた選択の限定された量が考慮される。ラウンドロビン方式の例外は現在の優先順位が前の優先順位によって決まることである。しかしながら、両方式共通信チャネルを介して導入される付加待ち時間をメッセージを発する個別プロセス間ではなくメッセージ・バイ・メッセージベースで割り当てるという問題がある。したがって、通信チャネルを通るハイレベルのアクセスを有するメッセージは、通信チャネル内で行われる調停判断の結果時間とともにハイレベルの付加待ち時間を受ける。
【０００６】
主としてネットワーク用に開発されている代替技術はＱｕａｌｉｔｙ−ｏｆ−Ｓｅｒｖｉｃｅ（ＱｏＳ）技術であり、それはプロセスが必要な帯域幅および制御された待ち時間特性を有することを保証しようと試みることにより時間ベース見解をとる。それ故、このようなＱｏＳ方式は各プロセスを考慮して通信チャネルの帯域幅の一部をそのプロセスに割り当て、各トランザクションまたはメッセージに適用される待ち時間を幾分制御する。しかしながら、既知のＱｏＳ方式の限界はこれらのプロセスが実行される時に生じる実際のデータフローの前に各プロセスの特性は知られているものと仮定され、かつその情報の管理に幾分ハイレベルのプロトコルを必要とすることである。それ故、このようなＱｏＳ方式は帯域幅や待ち時間特性の変化に対して柔軟性ではなく、特性を前もって知る必要があり、さらにプロセスに必要な特性を提供するように通信チャネルの動作を構成するためのよりハイレベルのプロトコルが必要である。それ故、既存のＱｏＳ方式は通信チャネルが性能を提供すると仮定することから始り、この性能をプロセスからの予め定められた要求条件に従って割当てる。それにより予想したものよりも低い帯域幅要求条件を有するプロセスとなって不公平な性能が得られ、予め定められた特性を超える他のプロセスは性能が不足することがある。
【０００７】
これら既知のＱｏＳ方式のいくつかはネットワーク環境内で受け入れられるように作動できるが、他のタイプのシステム、たとえば、ＳｏＣでは共有通信チャネルを介して生じるデータフローはランダムとなって（たとえば、キャッシュミス等により）ダイナミックに変動することがあり、既存のＱｏＳ方式には適さない。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、共有通信チャネルを介して送られるメッセージ間の調停を行う改良された技術を提供することが望ましい。
【課題を解決するための手段】
【０００９】
（発明の概要）
第１の側面から見ると、本発明は共有通信チャネルを介して送られるメッセージ間の調停を行うデータ処理装置を提供し、それは各々が受取要素に発せられるメッセージを要求するプロセスを実行する複数の処理要素と、複数の処理要素間で共有されそれを介してメッセージが送られる通信チャネルと、通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する調停回路とを含み、各処理要素はそこで実行中のプロセスに対する進捗データを発するようにされていて、進捗データはプロセスに対する待ち時間含意（ｌａｔｅｎｃｙ ｉｍｐｌｉｃａｔｉｏｎｓ）を示し、さらに、各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データが示す各プロセスの待ち時間含意を考慮した優先順位付けプロセスを実施し、かつ調停プロセスを制御するために調停回路に優先順位付けデータを出力する調停制御回路を含んでいる。
【００１０】
本発明に従って、各処理要素はそこで実行中のプロセスに対する進捗データを発するようにされており、進捗データはプロセスに対する待ち時間含意を示す。最終的に、待ち時間が特定レベルまで増加するとプロセスは停止されるが、最初に実行できる十分なバッファリングまたは他の計算があるため、これはすぐには起こらない。さらに、プロセス停止の影響はそのプロセスに非常に依存し、場合によっては破滅的となることがあるが、他のプロセスに対しては停止の影響はあまり重大ではなく、プロセスを完了するのに要する時間が延びるにすぎない。それ故、待ち時間の含意はプロセスに非常に依存し、各実行中プロセスに関して発せられる進捗データはそのプロセスに特定の待ち時間含意を示すことが理解される。
【００１１】
さらに、本発明に従って調停制御回路が提供され、それは各処理要素からの進捗データに応答して進捗データにより示される待ち時間含意を考慮した優先順位付けプロセスを実施する。このプロセスの結果として、優先順位付けデータが発生され、それはその調停回路により実施される調停プロセスを制御するためにデータ処理装置により提供される調停回路へ出力される。
【００１２】
調停回路の配置は通信チャネルの構造によって決まる。典型的に、調停を実施する必要のある多数のポイントが通信チャネル内にあり、これらの各ポイントにおいて調停をできるように調停回路は通信チャネル全体にわたって分散される。このような各ポイントにおいて、調停制御回路により出力される優先順位付けデータを使用して通信チャネル内のそのポイントに現われる多数のメッセージ間の調停が行われる。
【００１３】
本発明を使用して、個別のプロセスの要求条件を考慮して、したがって、調停のＱｏＳスタイルを採用して調停を実施することができるが、既知のＱｏＳ方式とは対照的に、このＱｏＳは自動的に決定されてプロセス間に割当てられ、要求条件を前もって知る必要性がなくなる。さらに、本発明のＱｏＳ機構はプロセス間の通信の変化にダイナミックに適応する。特に、個別プロセスからの進捗データが変化すると、それは調停制御回路により作り出される優先順位付けデータに影響を及ぼし、次に、データ処理装置の調停回路により実施される調停に影響を及ぼす。
【００１４】
通信チャネルを共有する処理要素は多様な形をとることができる。しかしながら、一実施例では、各処理要素は通信チャネルに接続されたマスター装置である。典型的に、通信チャネルを介してメッセージが発せられる受取要素はスレーブ装置であり、個別のトランザクションはマスター装置および選出されたスレーブ装置間で通信チャネルを介していくつかのリードまたはライト転送を行うためにそこでプロセスを実行する時にマスター装置により発せられる。このような実施例では、各メッセージはトランザクションを開始するためにマスター装置の１つにより発せられるアクセス要求の形をとることができる。しかしながら、メッセージの正確な形は通信チャネル上で使用されるプロトコルによって決まる。ＡＲＭ Ｌｉｍｉｔｅｄ，Ｃａｍｂｒｉｄｇｅ，Ｕｎｉｔｅｄ Ｋｉｎｇｄｏｍにより開発されたＡＸＩ（Ａｄｖａｎｃｅｄ ｅＸｔｅｎｓｉｂｌｅ Ｉｎｔｅｒｆａｃｅ）プロトコル等のバスプロトコルに対して、リードおよびライトデータはトランザクションにより指定されるアドレス転送内に記述されるメッセージの一部を形成するが、パケット化されたシステムでは要求およびデータはメッセージを構成する単一パケットの一部を形成することがある。
【００１５】
さまざまな処理要素により実行される個別プロセスは多様な形をとることができる。しかしながら、一実施例では、各プロセスはプログラム・スレッド（ｔｈｒｅａｄ）であり、各処理要素は単一プログラム・スレッドを実行する。このような実施例では、進捗データはスレッド・バイ・スレッドベースで提供される。
【００１６】
代替実施例では、少なくとも１つの処理要素が多数の処理装置を含み、各処理装置がプログラム・スレッドを実行する。この実施例では、処理要素はマルチコアプロセッサであり、進捗データが発せられる「プロセス」はその処理要素のさまざまな処理装置上で実行中のさまざまなプログラム・スレッドの全てからなっている。このようなマルチコアプロセッサを構成するもう１つの方法は個別の各処理装置を個別に処理要素と見なされるマルチコアプロセッサ内に配置して、マルチコアプロセッサ内の各処理装置がそこで実行中のプログラム・スレッドに関連するそれ自体の進捗データを出力することである。
【００１７】
データ処理装置は多様な形をとることができるが、一実施例では、ＳｏＣの形をとる。通信チャネルを介して生じるさまざまなデータフローがランダムかつダイナミックに変動するため、本発明の技術はＳｏＣ装置内で特に有益である。本発明の実施例の技術は要求条件が変動する時にさまざまなプロセスの帯域幅および待ち時間を管理するのに十分柔軟性である。
【００１８】
進捗データは多様な形をとることができる。一実施例では、進捗データは関連するプロセスがリアルタイムプロセスであるか非リアルタイムプロセスであるかを識別し、リアルタイムプロセスに対しては進捗データは少なくともそのリアルタイムプロセスにより発せられたメッセージを処理する残り時間を示すスラック（ｓｌａｃｋ）値をさらに識別し、非リアルタイムプロセスに対しては進捗データは少なくとも予め定められた時間にわたるそのプロセスに関連する待ち時間を示す待ち時間値をさらに識別する。
【００１９】
本明細書の目的に対して、リアルタイムプロセスはそのプロセスに対する停止の影響が破滅的と見なされて受け入れられない任意のプロセスと考えることができる。その例はディスプレイされた映像の混乱は受け入れられないと見なされる、画面上にディスプレイされる映像を発生しているプロセスである。対照的に、本出願の状況における非リアルタイムプロセスは停止が受け入れられる任意のプロセスを意味し、それ故、停止の影響はあまり重要ではなくプロセスの完了に要する時間が延長される。そのプロセスがリアルタイムプロセスであるか非リアルタイムプロセスであるかの表示の他に、リアルタイムプロセスに対して進捗データはそのリアルタイムプロセスにより発せられたメッセージを処理する残り時間（すなわち、プロセスが停止するまでどれだけ長いか）を示すスラック値をさらに識別する。対照的に、非リアルタイムプロセスに対しては進捗データは少なくとも予め定められた時間にわたりそのプロセスに関連する待ち時間を示す待ち時間値をさらに識別する。予め定められた時間はインプリメンテーションに応じて変動することがある設計パラメータである。予め定められた時間が長いほど、待ち時間値を作り出す時に考慮するヒストリカル情報量は大きくなり、予め定められた時間が短いほど、待ち時間値は迅速に最近の変化に応答して変化し、それ故、調停制御回路により発生される優先順位付けデータは特定のプロセスからのデマンドの最近の変化により迅速に適応する。
【００２０】
前記した情報を進捗データに内蔵することにより、調停制御回路はリアルタイムプロセスが停止しないことを保証するのに十分な優先順位付けされることを保証することができるが、リアルタイムプロセスに関連するスラック値が許す場合、非リアルタイムプロセスはそれが経験する待ち時間を低減する目的でリアルタイムプロセスよりも先に優先順位付けすることができる。各非リアルタイムプロセスに対して識別された待ち時間値が予め定められた時間にわたってそのプロセスに関連する待ち時間を示すようにすれば、全体待ち時間を非リアルタイムプロセス間で公平に割り当てることができる。
【００２１】
各非リアルタイムプロセスに関連する待ち時間値を作り出すために設けられる回路は多様な形をることができる。たとえば、各プロセスに対して、負値はプロセスを停止せずに付加できる待ち時間を示し正値は既にプロセスに付加された待ち時間をカウントする符号付２進値を維持することができる。転送に待ち時間が付加されるサイクル毎に、この２進カウントは増分することができ、２進値が正であればスレッドは停止していることを示す。次に、この停止時間を積分器内で累積することができる（積分器値は時間とともに無制限となるため、全積分器から周期的に値を減じる機構を設けることができる）。したがって、積分器により出力される待ち時間値は優先順位付けデータを発生する時に調停制御回路が使用できるスレッド間の停止時間差の情報を提供する。積分器を使用することの代替策として、非リアルタイムプロセスを実行する各処理要素にフィルタ回路を関連付けることができ、フィルタ回路は単位時間当たり待ち時間の形の待ち時間値を作り出す。それ故、このような実施例では、単純なローパスフィルタを使用して累積された停止時間を追跡することができ、各フィルタからの出力は平均ストールレート（ｓｔａｌｌ ｒａｔｅ）、すなわち、スレッドが予め定められた時間にわたって停止され基準期間を形成するサイクル数に比例する。
【００２２】
一実施例では、全ての非リアルタイムプロセスを同等に処理することができ、進捗データ内に含まれる待ち時間値は待ち時間の影響を非リアルタイムプロセス間で均一に分配することをシークするのに使用される。しかしながら、代替実施例では、少なくとも１つの非リアルタイムプロセスには重み付けが関連付けられており、その重み付けはその非リアルタイムプロセスに対する待ち時間値を作り出す時に考慮される。このような各プロセスに対する重み付けは設計時に固定することができる、またはプログラマブルとすることができるが、典型的にはダイナミックに変動しない。フィルタ回路を採用する実施例では、各非リアルタイムプロセスの重み付けはこのようなフィルタ回路により適用されるフィルタアルゴリズムに異なる重み付けを適用して実現することができる。したがって、ある非リアルタイムプロセスには高い重み付けを適用できるが他の非リアルタイムプロセスには低い重み付けが適用され、調停制御回路により優先順位付けプロセスが実施されている時に、ある非リアルタイムプロセス（すなわち、より高い重み付けのプロセス）が他の非リアルタイムプロセスよりも好まれることがある。例として、これによりオーディオストリームを発生するプロセスは、そのプロセスの停止によりオーディオが非常にまれに混乱することが受け入れられれば、非リアルタイムプロセスと見なすことができ、そのプロセスに関してその時高い重み付けが適用されなければ、そのプロセスに関して出力される待ち時間値は他の重要度の低い非リアルタイムプロセスに較べて比較的迅速に増加し、調停制御回路内で優先順位付けプロセスを実施している時にそのオーディオストリーム・プロセスを優先順位の低い非リアルタイムプロセスよりも先に優先順位付けするようにされる。
【００２３】
一実施例では、データ処理装置はさらにリアルタイムプロセスを実行中の各処理要素に関連するカウンタ回路を含み、カウンタ回路は前記スラック値を作り出している。それ故、一実施例では、そのプロセスによりメッセージが発せられる時（たとえば、トランザクションが開始する）カウンタ回路はカウンタを特定の値にセットすることができ、そのカウンタ値は次に時間とともにスラック値が減少するように各クロックサイクルで減分される。スラック値が比較的高い間、調停制御回路により実施される優先順位付けプロセスはある非リアルタイムプロセスをリアルタイムプロセスよりも先に優先順位付けすることができるが、そこで優先順位付けプロセスがリアルタイムプロセスをこのような非リアルタイムプロセスよりも先に優先順位付けするレベルまでスラック値が減少するポイントとなる。
【００２４】
一実施例では、非リアルタイムプロセスに対して進捗データはそのプロセスが停止されるか否かを識別するストール値をさらに識別する。特定の一実施例では、これは１ビット値の形をとることができ一方の値はプロセスが停止されることを示し他方の値はそれが停止されないことを示す。特定の一実施例では、このストール値は待ち時間値を作り出すのに使用されるフィルタ回路への入力としても使用することができる。
【００２５】
一実施例では、非リアルタイムプロセスに対して進捗データはプロセスが停止する前にそのプロセスにより発せられるメッセージの残りの処理時間を示すスラック値をさらに識別する。それ故、非リアルタイムプロセスが事前にトランザクションを開始する（すなわち、プロセスはそのトランザクションの結果が要求される前にまだある期間継続することができる）状況では、プロセスが停止する前の残り時間を識別する進捗データ内にスラック値を含めることができ、調停制御回路は優先順位付けプロセスを実施する時にこの情報を考慮することができる。
【００２６】
優先順位付けプロセスは多様な方法で構成することができる。しかしながら、一実施例では、そのリアルタイムプロセスにより発せられるメッセージの残りの処理時間が予め定められた閾値よりも大きいことをそのリアルタイムプロセスのスラック値が示す場合、優先順位付けプロセスはリアルタイムプロセスよりも非リアルタイムプロセスに優先順位を与える。それ故、リアルタイムプロセス内のスラックが許す場合、非リアルタイムプロセスはリアルタイムプロセスよりも先に優先順位付けされて、リアルタイムプロセスにいかなる実際の影響も及ぼすことなく、これらの非リアルタイムプロセスにより経験される待ち時間を低減することができる。
【００２７】
一実施例では、優先順位付けプロセスは低い待ち時間値を有する非リアルタイムプロセスよりも高い待ち時間値を有する非リアルタイムプロセスに優先順位を与える。これらの待ち時間値はプロセスに関連する待ち時間が予め定められた時間を超えることを示すため、それにより非リアルタイムプロセスを横切して待ち時間を公平に配分することができる。
【００２８】
一実施例では、異なるストール値を有する２つの非リアルタイムプロセスに対して、優先順位付けプロセスはより高い待ち時間値を有するプロセスに優先順位を与えることよりも優先的にそのプロセスが停止されることをそのストール値が示す非リアルタイムプロセスに優先順位を与える。それ故、このような方法は任意の非リアルタイムプロセスが停止される時間を低減するようにシークする。
【００２９】
一実施例では、異なるスラック値を有する２つの非リアルタイムプロセスに対して、優先順位付けプロセスはより高い待ち時間値を有するプロセスに優先順位を与えることよりも優先的に最少スラックを有する非リアルタイムプロセスに優先順位を与える。このような方法は可能な所で非リアルタイムプロセスが停止する尤度を低減するようにシークする。
【００３０】
各処理要素により作り出される進捗データの主目的は優先順位付けプロセスを実施する時に調停制御回路がサービス品質要件を考慮できるようにすることであるが、進捗データの若干をデータ処理装置の他の部分で再使用できることも判っている。たとえば、データ処理装置にエネルギ管理回路を設けて装置のさまざまなコンポーネントが動作するパフォーマンスレベルを制御することが知られている。このようなデータ処理装置は典型的に実行時に異なる動作パフォーマンスレベル間で切り替わることができる。低いパフォーマンスレベルは軽いワークロードを実行するときにエネルギ（消費電力）を節減するために選出され、高いパフォーマンスレベルはより処理集約的ワークロードに対して選出される。典型的に、データ処理装置内の処理要素がｃｏｍｐｌｉｍｅｎｔａｒｙ ｍｅｔａｌ−ｏｘｉｄｅ ｓｅｍｉｃｏｎｄｕｃｔｏｒ（ＣＭＯＳ）技術でインプリメントされる場合、低いパフォーマンスレベルは低い周波数および動作電圧設定を意味する。
【００３１】
データ処理装置がこのようなエネルギ管理回路を含む一実施例では、これらの処理要素に対する動作パフォーマンスレベルを決定する時にエネルギ管理回路は１つ以上の処理要素により発せられる進捗データの少なくとも一部を考慮するようにされる。特定の一実施例では、エネルギ管理回路は非リアルタイムプロセスを実行中の１つ以上の処理要素により出力される待ち時間値を考慮する。
【００３２】
第２の側面から見て、本発明は各処理要素が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素と、複数の処理要素間で共有されそれを介してメッセージが送られる通信チャネルとを有するデータ処理装置の通信チャネルを介して送られるメッセージ間の調停方法を提供し、この方法は各処理要素からその上で実行中のプロセスに対する進捗データを発するステップであって、進捗データはプロセスに対する待ち時間含意を示すステップと、各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施するステップと、通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施するステップであって、優先順位付けデータは調停プロセスを制御するのに使用されるステップと、を含んでいる。
【００３３】
第３の側面から見て、本発明はデータ処理装置用調停制御回路を提供し、データ処理装置は各々が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素と、複数の処理要素により共有されそれを介してメッセージが送られる通信チャネルと、通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する調停回路とを有し、調停回路はその処理要素上で実行中のプロセスに対する進捗データを各処理要素から受信する入力インターフェイスであって、進捗データはプロセスに対する待ち時間含意を含む入力インターフェイスと、各処理要素からの進捗データに応答して優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施する優先順位付け回路と、調停プロセスを制御するために優先順位付けデータを調停回路に出力する出力インターフェイスと、を含んでいる。
【実施例】
【００３４】
（実施例の説明）
単なる例として添付図に例示されている実施例について本発明をさらに説明する。図１は本発明の一実施例に従ったデータ処理装置のブロック図である。この実施例では、データ処理装置は通信チャネル４０を介していくつかのスレーブ装置５０，６０，７０に接続されたいくつかのマスター装置１０，２０，３０を含むＳｏＣの形をとる。本発明の実施例を検討する目的に対してこのようなＳｏＣ装置が考慮されるが、当業者ならば本発明の実施例の技術は通信チャネルが複数の処理要素間で共有される多種多様な異なるシステムに応用できることが
理解される。
【００３５】
図１のＳｏＣ例について考えると、通信チャネル４０は典型的にＳｏＣ内の多数のバスマスター装置１０，２０，３０およびバススレーブ装置５０，６０，７０を相互接続するための接続のマトリクスを提供するいくつかの相互接続されたバスを含む相互接続ブロックの形をとる。
【００３６】
通信チャネルを形成するバスは典型的に指定されたバスプロトコルに従って動作し、それ故、たとえばＡＲＭ社により開発された“Ａｄｖａｎｃｅｄ Ｍｉｃｒｏｃｏｎｔｒｏｌｌｅｒ Ｂｕｓ Ａｒｃｈｉｔｅｃｔｕｒｅ”（ＡＭＢＡ）に従って動作することができる。
【００３７】
したがって、通信チャネル４０はさまざまなマスターおよびスレーブ装置間の相互接続の複雑な構成からなることが理解される。通信チャネル内のさまざまなポイントにおいて、特定のパスの使用を奪い合う多数のメッセージ間の調停を行う調停回路を設ける必要がある。
【００３８】
各マスタ１０，２０，３０はその間にさまざまなトランザクションが通信チャネル４０を介して開始されるプロセスを典型的に実行する。このようなトランザクションによりマスタからスレーブへ（ライトトランザクションの場合）またはスレーブからマスターへ（リードトランザクションの場合）データを送ることができ、各トランザクションは通信チャネル上へアクセス要求を発するマスター装置により開始される。各アクセス要求はメッセージを形成すると考えられ、通信チャネル内の調停回路は多数のメッセージが特定のパスの使用を奪い合うバスインフラストラクチュア内の任意のポイントで調停を実施する必要がある。
【００３９】
したがって、調停回路は通信チャネル全体にわたって分散された複数の調停要素からなるものと考えられ、このような各調停要素が多数のメッセージ間の調停を行う調停プロセスを実施する。本発明の実施例に従って、各調停要素により実施される調停プロセスは、それぞれ、対応するパス１２，２２，３２を介して各マスター装置１０，２０，３０により出力される進捗情報を入力インターフェイス８２において受信するようにされた調停制御回路８０により決定される。後述するように、この進捗データは各マスター装置上で実行中のプロセスに対する待ち時間含意を示し、その進捗データは調停制御回路内の優先順位付け回路８４へ転送され、そこで優先順位付けデータを発生するためにその進捗データを考慮して優先順位付けプロセスが実施される。その優先順位付けデータは、次に、プロセスの優先順位付けされたリストとして出力インターフェイス８６を介して出力され、そのリストは通信チャネル内の全調停要素（ここでは、アービター（ａｒｂｉｔｅｒｓ）とも呼ばれる）へ送られる。この優先順位付けされたリストを広めることができる多様な方法がある。一実施例では、それはメッセージを送るのに使用されるのと同じパスを介して広めることができ、代替実施例では、この優先順位付けされたリストは独立した専用バス構造により広めることができる。次に、各アービターは提供された優先順位リストに基づいてその調停プロセスを実施する。
【００４０】
調停制御回路８０はこの優先順位付けされたリストを予め定められた間隔で更新するように構成することができる。一般的に言えば、優先順位付けされたリストは調停制御回路への任意の入力が変化する時は常に更新しなければならない。典型的に、進行中のトランザクションがあまり無いか全く無い場合を除き、これによりリストは各クロックサイクルで更新される。
【００４１】
図２Ａはマルチコアプロセッサ１００を図１のデータ処理装置内に収容することができる１つの方法を例示するブロック図である。マルチコアプロセッサ１００はプロセッサ１００内の内部通信チャネル１５０を介して相互接続される複数のプロセッサコア１１０，１２０，１３０，１４０を有する。次に、マルチコアプロセッサ１００はそれを介してさまざまなスレーブ装置５０，６０，７０と通信することができる外部通信チャネル１６０に接続される。一実施例では、図１の通信チャネル４０はマルチコアプロセッサ１００の内部通信チャネル１５０とマルチコアプロセッサ外部の通信チャネル１６０の両方を包含するものと見なすことができ、実質的に各プロセッサコア１１０，１２０，１３０，１４０は各々がそれら自体の進捗情報を調停制御回路８０へ発する独立したマスター装置を形成すると見なすことができる。一実施例では、このような各プロセッサコア１１０，１２０，１３０，１４０が独立したプログラム・スレッドを実行し、したがって、任意特定のコアから出力される進捗情報は関連するスレッドに対する待ち時間含意を示す。
【００４２】
図２Ｂに例示するように、代替実施例では、マルチコアプロセッサの内部は調停制御回路から隠すことができ、替わりにマルチコアプロセッサの全体が単一マスター装置、この例ではマスター装置１０、として見られる。したがって、マスター装置１０がマルチコアプロセッサである状況においてパス１２を介して調停制御回路へ出力される進捗情報は全体としてマルチコアプロセッサにより実施される「プロセス」に対する待ち時間含意を提供し、それ故、各個別コア１１０，１２０，１３０，１４０により実行される各個別スレッドに対する待ち時間含意を直接提供することはない。
【００４３】
図３Ａはさまざまなタイプの非リアルタイムプロセスに対する時間対待ち時間コストを例示する図である。線「ａ」２００は必要な時にデータを要求するプロセスを処理要素が実行する時に生じる待ち時間コストの形を示すが、通信チャネル４０を介して任意のアクセス要求が発せられる前に内部遅延が生じる。これは、たとえば、マスター装置が内部キャッシュ、ブラックボックスシステム、等を有するプロセッサであるケースである。キャッシュを有するプロセッサの例を考えると、プロセッサによりアクセス要求が発せられると、最初にキャッシュ内でルックアップが実施されてアクセス要求の対象であるデータがキャッシュ内にあるかどうか決定される。無ければ、キャッシュミスが生じ、通信チャネル４０上にアクセス要求が生じる。線２００に関連して図３Ａに点線で示すように、非リアルタイムプロセスにより観察される待ち時間は通信チャネル４０上に任意のアクセス要求が現われる前に既に増加しており、時間ゼロにおいて通信チャネル上にアクセス要求が現われると、待ち時間コストは既に正値であるようにされる。
【００４４】
対照的に、線「ｂ」２１０はそのプロセスが必要な時にデータを要求する処理要素に対して観察されるタイプの線を示し、要求は即座に通信チャネル４０上に現れる。このような処理要素の例は、たとえば、Ｄｉｒｅｃｔ Ｍｅｍｏｒｙ Ａｃｃｅｓｓ（ＤＭＡ）コントローラである。
【００４５】
線「ｃ」２２０はそのプロセスが事前にデータを要求する処理要素に対して観察されるタイプの線を示す。それ故、この例では、要求は時間ゼロにおいて通信チャネル４０上に現われるが、プロセスは他の有用な作業をできるため、時間ｔ１に達するまで正の待ち時間コストは無い。したがって、プロセスが実際に停止するのはやっと時間ｔ１においてである。対照的に、線２１０に関連するプロセスに対して、そのプロセスは時間ゼロで停止し、線２００に関連するプロセスに対しては、時間ゼロにおいて通信チャネル４０上に要求が現われる前であってもプロセスは停止する。
【００４６】
したがって、線２００および２１０に関連するプロセスにはスラック時間は無いことが判るが、線２２０に関連するプロセスはそのプロセスにより通信チャネル４０上に発せられるメッセージをそのプロセスを停止させずに処理できるいくらかのスラック時間を有する。
【００４７】
本発明の一実施例では、非リアルタイムプロセスを実行する任意のマスター装置により発せられる進捗情報の一部はプロセスが停止される時にセットされプロセスが停止されない時にリセットされるストールビット（ｓｔａｌｌ ｂｉｔ）である。図３Ｂは図３Ａの３本の線の例に対するこのストールビットのプロファイルを示す。この例では、セット状態は論理１値で示されリセット状態は論理０値で示されるものと仮定する。図３Ｂからお判りのように、線ａに関連するプロセスはポイント２０５において停止し、したがって、ストールビットはそのポイントにセットされる。同様に、線ｂに関連するプロセスはポイント２１５において停止しまた線ｃに関連するプロセスはポイント２２５において停止し、したがって、ストールビットはポイント２１５，２２５において、それぞれ、遷移する。
【００４８】
線ａに関連するプロセスについて考えると、要求は通信チャネル４０上に発せられる必要なしに処理要素内でサービスされる。たとえば、前記したキャッシュを有するプロセッサの例について考えると、キャッシュヒットが生じると、通信チャネル４０を介してアクセス要求を伝搬させる必要なしにキャッシュに関してアクセスが進行する。したがって、点線２０７で示すように、このような状況においてストールビットは２０５において論理１値に遷移するが、アクセス要求がサービスされていると、次に、論理０値へ遷移し戻る。一実施例では、任意特定のアクセス要求が通信チャネル４０上に発せられているかどうかに拘わらず、ストールビットはまだ進捗情報の一部として出力され、実際に、一実施例ではそのプロセスに対する待ち時間情報を発生するのに使用されるフィルタへの入力として使用される。それ故、調停制御回路８０にはその停止の原因に無関係に任意特定のマスター装置のプロセスが停止される時間の割合に関する情報が提供され、特に、通信チャネル４０を介して導入される待ち時間の結果として停止が生じる状況に限定はされない。
【００４９】
図４はリアルタイムプロセスの待ち時間コストを例示する図３Ａと同様な図である。前記したように、本出願の目的のために、リアルタイムプロセスはプロセスのいくらかの停止は受け入れられる非リアルタイムプロセスとは対照的に、そのプロセスが停止することは受け入れられないプロセスである。したがって、停止することが許されないとすると、リアルタイムプロセスは典型的に事前にデータを要求し、曲線がパス２５０に従っている間、そのリアルタイムプロセスに関連するスラック時間がある。しかしながら、この場合、スラック時間はそのリアルタイムプロセスにより発せられたメッセージを処理するための残り時間を示し、スラック時間が尽きると垂直線２６０で示すように待ち時間コストは無限大となる。
【００５０】
図５は本発明の一実施例に従ったマスター装置１０，２０，３０により発せられる進捗情報のさまざまなコンポーネントを例示している。特に、図５の例では、マスター１０は非リアルタイムスレッドを実行しており、マスター２０は非リアルタイムスレッドを実行しているが、マスター３０はリアルタイムスレッドを実行しているものと仮定する。一実施例では、非リアルタイムスレッドを実行している各マスター装置は進捗情報に対して４つのコンポーネントを出し入れするようにされている。特に、プロセスは非リアルタイムスレッドであることを識別するリアルタイムビット信号がパス２００，２２０を介して発せられる。本例では、これはリアルタイムビットをゼロにセットして例示されている。さらに、非リアルタイムスレッドに関連する任意のスラック時間を識別するスラック値がパス２０５，２２５を介して出力される。図３Ａの待ち時間コストグラフに関して、このスラック値は任意の負の待ち時間コスト値で表せることが理解される。特に、線ｃ２２０について考えると、負の待ち時間コストの大きさは時間ゼロの特定の値で始り、時間ｔ１においてゼロの値に達するように、そのプロセスに関連するスラック時間中にゼロまで漸減する。
【００５１】
さらに、図５に示す実施例では、現在の時間において関連するプロセスが停止されるか否かを識別するストールビットがパス２１０，２３０を介して出力される。このストールビットはローパスフィルタ２１５，２３５にも入力されて待ち時間値を発生しパス２２０，２４０を介して出力させ、この待ち時間値は単位時間当たり遅延を表す。一実施例では、各ローパスフィルタ２１５，２３５は累積されたストール時間を追跡する単純な単極ローパスフィルタである。特に、一実施例では、ローパスフィルタは待ち時間値ｙを発生するために下記の等式をインプリメントすることができ、
ｙｋ＝α．ｙｋ−１＋ｘｋ（１−α）
ここに、ｙは待ち時間値であり、αは選出された定数であり、ｋは時点でありｘはストールビット値である。
【００５２】
したがって、待ち時間値ｙは平均ストールレート、すなわち基準期間にわたってスレッドが停止されるサイクル数、に比例し基準期間は定数αの選択によって決まる。
【００５３】
リアルタイムスレッドに対して、進行情報はやはりパス２５０を介して出力されるリアルタイムビットを含み、ここではリアルタイムビットはスレッドがリアルタイムスレッドであることを示す論理１値にセットされ、さらに、カウンタ２５５からパス２６０を介して出力されるスラック値を含んでいる。特に、リアルタイムスレッドがアクセス要求を出力する場合、カウンタ２５５はそのアクセス要求に応答するクロックサイクル数を表すある予め定められた値にセットされ、各クロックサイクルが経過するとカウンタは減分されてスラック値を時間とともに減少させる。
【００５４】
図５に例示されたさまざまな進捗情報に基づいて、一実施例の調停制御回路８０は次に、図６に示すように、各スレッドに対するデータ構造のテーブル３００を維持する。フィールド３０５に入ったスレッドＩＤにより示される各スレッドに対して、リアルタイムビット、ストールビット、フィルタ出力の値およびスラック値が、それぞれ、フィールド３１０，３１５，３２０，３２５内に格納される。特定のスレッドに対して情報のサブセットしか提供されなければ、１つ以上のフィールドはブランクのままとされる。たとえば、リアルタイムスレッドについて考えると、ストールビットやフィルタ出力はない。
【００５５】
次に、調停制御回路８０は優先順位付け回路８４を利用して各スレッドに関連するデータ構造を考慮したプロセス（スレッド）の優先順位付けされたリストを発生する。当業者ならば、一連のデータ構造が提示される時に順序付けされたリストを形成するためのいくつかの既知の技術があり、しばしばこれらのプロセスはデータ構造の選出された対に対する比較プロセスの反復実施を伴うことが理解される。１つのこのような機構は既知の「バブルソート（ｂｕｂｂｌｅ ｓｏｒｔ）」機構であり、それはソートされるリスト中を反復ステッピングし、一時に２つのデータ構造を比較し誤った順序であればそれらをスワッピングすることで働く。リストをパススルーすることはスワップが必要とされなくなるまで繰り返され、それはリストがソートされることを意味する。
【００５６】
図７はどのスレッドが他よりも優先順位を有するか判断するためにスレッドの選出された対（ここではスレッドＸおよびＹと表示されている）がどのように比較されるかを略示している。図７に示すように、両方のスレッドに対してリアルタイムビットがセットされると（すなわち、両方のスレッドがリアルタイムスレッド）、最少スラックのスレッドに優先順位が与えられる、すなわち最も早いデッドラインを有するスレッドに優先順位が与えられ、このような優先順位付け技術はしばしば“ｅａｒｌｉｅｓｔ ｄｅａｄｌｉｎｅ ｆｉｒｓｔ”優先順位付けと呼ばれる。しかしながら、スレッドＸが非リアルタイムスレッドでありスレッドＹがリアルタイムスレッドであれば、図７の右上隅に示すようにスレッドＹに対するスラック時間が予め定められた値Ｎよりも大きければ優先順位はスレッドＸに与えられる。したがって、優先順位は自動的にリアルタイムスレッドには与えられず、リアルタイムスレッドに対するスラック時間が比較的大きければ、その非リアルタイムスレッドの待ち時間の低減をシークするために優先順位は非リアルタイムスレッドに与えられる。スラック時間が切れる前にリアルタイムスレッドがサービスされると悪い結果は生じないため、これはリアルタイムスレッドに悪影響を及ぼさない。
【００５７】
同様に、スレッドＹが非リアルタイムスレッドでありスレッドＸがリアルタイムスレッドであれば、図７の左下側に示すように、スレッドＸに対するスラック時間が予め定められた値Ｎよりも大きければ優先順位はスレッドＹに与えられる。
【００５８】
両方のスレッドが非リアルタイムスレッドであれば、判断ステップは図７の右下側に示すものとなる。特に、両方のリアルタイムスレッドに対するストールビットが最初に考慮される。両方のスレッドに対するストールビットがゼロであれば、いずれのスレッドも停止されないことを意味し、優先順位は最少スラックのスレッド、すなわち最も迅速に停止するスレッド、に与えられる。一方のスレッドのストールビットがセットされ他方はセットされなければ、優先順位はストールビットがセットされているスレッドに与えられる、すなわち優先順位は既に停止しているスレッドに与えられる。最後に、両方のスレッドのストールビットがセットされておれば、優先順位はフィルタ出力の最も高いスレッド、すなわち、基準期間にわたりより高い平均ストールレートを有するスレッドに与えられる。
【００５９】
ある実施例では、図５について前記した進捗情報の全アイテムを提示する必要はない。たとえば、ある実施例では非リアルタイムスレッドに対してスラック値は手に入らないことがある。その場合、２つの非リアルタイムスレッドが考慮されていて両方の非リアルタイムスレッドがそれらのストールビットをゼロに等しくセットしておれば、優先順位はフィルタ出力の最も高いスレッドに与えられる、すなわち両方のスレッドがそれらのストールビットを１に等しくセットしている場合に適用されるのと同じ優先順位付けが適用される。
【００６０】
一実施例において、あるスレッドがストールビットを提供しなければ、そのストールビットはセットされる、すなわち論理１値を有するものと仮定される。
【００６１】
図８は優先順位付けされたリストを作り出すために一実施例に従って図８の調停制御回路８０により実施される一般的プロセスを例示している。ステップ４００において、スレッドの初期順序付けが準備される。最初の反復において、これは任意順序付けとすることができるが、後続反復に対しては初期順序付けはプロセスにより作り出された前の順序付けとなることがある。その後、プロセスはステップ４０５に進み、そこで一対のスレッドが選出され、その後ステップ４１０において図９についてより詳細に説明するように順序付けプロセスが適用される。この順序付けプロセスは図７について略示した優先順位付け方式をインプリメントする。
【００６２】
その後、ステップ４１５において、スレッドの順序付けは順序付けプロセスの結果に応じて修正され、その後ステップ４２０において順序付けプロセスを適用すべきスレッド対がまだあるのか決定される。プロセスを介した最初の反復では、典型的にスレッド対の組合せ毎に順序付けプロセスを行う必要がある。しかしながら、後続反復では、進捗情報の何の特徴が変更されているか、またどのスレッドの進捗情報が変更されているかに応じて、可能な全スレッド対のサブセットに順序付けプロセスを適用するだけでよい。ステップ４２０において順序付けプロセスを適用する必要のある少なくとももう１対のスレッドがあると判断されると、プロセスはステップ４０５へ戻り、順序付けプロセスを行うべき対はもう無いと判断されると、プロセスはステップ４２５へ進み、そこでスレッドの修正された順序付けが優先順位付けされたリストとして通信チャネル４０内の全アービターに出力される。
【００６３】
例示する目的でステップ４０５，４１０，４１５および４２０が順次示されているが、順序付けプロセスを行う必要がある全ての対が識別されるように、これらのステップは実際上並列に処理することができ、次に、スレッドの修正された順序付けを作り出すために順序付けプロセスは並列に適用されることに留意しなければならない。
【００６４】
図９は本発明の一実施例に従って図８のステップ４１０において実施されるステップを示すフロー図である。ステップ５００において、両方のスレッドがリアルタイムスレッドであるかどうか決定され、そうであればステップ５０５においてスレッドはｅａｒｌｉｅｓｔ ｄｅａｄｌｉｎｅ ｆｉｒｓｔ原理に従って優先順位付けされる。
【００６５】
ステップ５００において両方のスレッドがリアルタイムでないと決定されると、ステップ５１０において一方のスレッドがリアルタイムスレッドであるかどうか決定され、そうであればプロセスはステップ５１５へ進みそこでリアルタイムスレッドのスラックが予め定められた値Ｎよりも大きければ非リアルタイムスレッドに優先順位が与えられる。そうでなければ、リアルタイムスレッドが優先順位付けされる。
【００６６】
ステップ５１０においていずれのスレッドもリアルタイムスレッドではないと決定されると、プロセスはステップ５２０へ進みそこで両方のスレッドのストールビットがゼロに等しいかどうか、すなわち両方のスレッドにまだいくらかのスラックが残っているかどうか決定される。両方のスレッドがまだいくらかのスラックを有すると仮定すると、プロセスはステップ５２５へ進みそこでスラック値が手に入るかどうか決定され、手に入ればプロセスはステップ５３０へ進みそこでスレッドはｅａｒｌｉｅｓｔ ｄｅａｄｌｉｎｅ ｆｉｒｓｔ原理に従って優先順位付けされる、すなわち最少スラックのスレッドに優先順位が与えられる。しかしながら、ステップ５２５においてスラック値が手に入らないと決定されると、プロセスは５３５に進み、フィルタ出力の最も高いスレッドに優先順位が与えられる。
【００６７】
ステップ５２０において両方のスレッドのストールビットがゼロに等しくないと決定されると、ステップ５４０において一方のスレッドに対するストールビットがゼロに等しいかどうか、すなわち一方のスレッドがスラックを有するかどうか決定される。そうであれば、プロセスはステップ５４５へ進みそこでスラックの無いスレッド（すなわち、そのストールビットが１に等しいスレッド）に優先順位が与えられる。
【００６８】
ステップ５４０においていずれのストールビットもゼロにセットされない、すなわち、両方のスレッドがストールされると決定されると、プロセスはステップ５５０へ進みそこでフィルタ出力の最も高いスレッドに優先順位が与えられる。
【００６９】
図９の前記説明から、図９のプロセスは図７に略示された選出基準をインプリメントすることが判る。
【００７０】
一実施例では、異なる重み付けをこれらのスレッドのせいにしてある非リアルタイムスレッドを他の非リアルタイムスレッドよりも優先的に処理することができる。実際上、これらの重み付けは非リアルタイムスレッドを実行中の各処理要素に提供される関連するローパスフィルタ２１５，２３５により適用することができる。その結果、より高い重み付けを有するプロセスに対して、ストールビットがセットされる度に、関連するローパスフィルタからの出力待ち時間値はより低く重み付けされたプロセスに対する場合よりも大量に増加される。したがって、図７について略示された選出基準を適用する時に、フィルタ出力の最も高いスレッドに優先順位を与えるべきであると決定され、次に、全てが等しいため、より高い重み付けのスレッドはより高いフィルタ出力を有しより低い重み付けのスレッドよりも先に優先順位付けされる。それ故、フィルタからの出力を重み付けすることにより、さまざまな非リアルタイムスレッドの優先順位を処理するためのさらなる柔軟性が提供される。
【００７１】
本発明の実施例の前記した技術はマスター装置上で実行中のさまざまなスレッドに適用される最大待ち時間の低減をシークすることが理解される。これにより各プロセスが有用な作業を行うことができる有用なクロックサイクル数が比例して増加する。その結果実際に必要なものよりも良い性能が提供されると、マスター装置またはこれらのマスター装置により共有される通信チャネルの動作パフォーマンスレベルを低減することによりトータル待ち時間を増加する機会ができる。
【００７２】
特に、いくつかの最新システムはシステム内のあるコンポーネントのパフォーマンスレベルを、典型的にはこれらのコンポーネントの周波数および／または動作電圧を変えることにより、変えることができるエネルギ管理技術を提供する。典型的に、このようなパフォーマンスレベル設定はシステム内のエネルギ管理コントローラにより実施される。
【００７３】
前記した観察が与えられると、本発明の一実施例において、さまざまなマスター装置により出力される進捗データのある側面もこのようなエネルギ管理コントローラへの入力として送られる。図１０はこのような実施例を略示しており、図からお判りのように、パス１２，２２，３２を介して出力される進捗データのいくらかもエネルギ管理コントローラ６００への入力として、それぞれ、パス６０２，６０４，６０６を介して送ることができる。特定の一実施例では、任意の非リアルタイムスレッドにより出力される待ち時間値がエネルギ管理コントローラ６００へ送られる。この情報はさまざまな方法で使用することができる。
【００７４】
たとえば、特定のマスター装置の動作周波数が数千サイクル／ミリ秒であり、１００ストールサイクル／ミリ秒であることを待ち時間値が示す場合、これはマスター装置が９００有用サイクル／ミリ秒を有することを意味する。実際上、そのプロセスを満足に実行するのにマスター装置が６００有用サイクル／ミリ秒しか必要としなければ、そのマスター装置が必要とする６００有用サイクル／ミリ秒を提供しながらエネルギを節減するためにそのマスター装置に供給される周波数および／または動作電圧を低減することができる。パフォーマンスレベルを変えることができる粒度に応じて、このプロセスを各マスター装置に対して順次独立して実施することができる。
【００７５】
替わりに、または、さらに、通信チャネル４０のパフォーマンスレベルをエネルギ管理コントローラにより変えることができれば、エネルギ管理コントローラ６００はさまざまなマスター装置から受信した最高待ち時間値を選出し、その最高値に関係する通信チャネルのパフォーマンスレベルを調節することができる。それにより、さまざまなマスター装置上で実行中のプロセスが満足に動作し続けることを保証しながら、通信チャネルの動作周波数を低減することができる。本質的に、エネルギ管理コントローラはシステムおよびその上で実行していアプリケーションに受け入れられる基準スレッドストールレートを目指して通信チャネルのクロック速度を調節することができる。
【００７６】
本発明の前記した実施例によりＱｏＳを決定してスレッド間に自動的に割り当てることができ、要求条件を前もって知る必要がなくなり、ＱｏＳはスレッド間の通信における変化にダイナミックに適応する。
【００７７】
本発明の実施例のＱｏＳ方式は通信チャネルインプリメンテーションに対する基準パフォーマンスレベルを提供するのに使用することもできる。特に、メモリコントローラ等のコンポーネントのアーキテクチュア内で比較を行うことができ、パイプライニングステージを付加してこのタイプの調停方式を実現するコストをメモリコントローラにアクセスする全スレッドに待ち時間のサイクルを付加するコストに対して比較することができる。
【００７８】
特定の実施例について説明してきたが、本発明はそれに限定されるものではなく発明の範囲内でそれに多くの修正および追加を行うことができる。たとえば、本発明の範囲を逸脱することなく従属項の特徴を独立項の特徴とさまざまに組み合わせることができる。
【図面の簡単な説明】
【００７９】
【図１】本発明の一実施例に従ったデータ処理装置のブロック図である。
【図２Ａ】図１のデータ処理装置内にマルチコアプロセッサを収容する１つの方法を例示するブロック図である。
【図２Ｂ】図１のデータ処理装置内にマルチコアプロセッサを収容する代替方法を例示するブロック図である。
【図３Ａ】異なるタイプの非リアルタイムプロセスに対する時間対待ち時間コストを例示する略図である。
【図３Ｂ】図３Ａに例示された異なるプロセスに対して本発明の一実施例に従って発せられるストールビットの値を例示する図である。
【図４】リアルタイムプロセスに対する時間対待ち時間コストを例示する略図である。
【図５】本発明の一実施例に従って図１の調停制御回路へ各マスター装置により発せられる進捗情報のさまざまなコンポーネントを例示する図である。
【図６】本発明の一実施例に従って図１の調停制御回路内に維持できるデータ構造を例示する図である。
【図７】本発明の一実施例に従って２つのスレッドに関して図１の調停制御回路により適用される順位付けプロセスを例示する略図である。
【図８】本発明の一実施例に従って図１の調停制御回路により適用される優先順位付けプロセスを例示するフロー図である。
【図９】本発明の一実施例に従って選出された一対のスレッドに順位付けプロセスを適用するために実施されるステップをより詳細に例示するフロー図である。
【図１０】本発明の一実施例に従って図１のさまざまなマスター装置により発せられる進捗データの少なくとも一部をどのようにしてデータ処理装置内のエネルギ管理制御回路にも送ることができるかを例示するブロック図である。
【符号の説明】
【００８０】
１０，２０，３０ マスター装置
１２，２２，３２，２００，２０５，２１０，２２０，２２５，２３０，２５０，２６０，６０２，６０４，６０６ パス
４０，１６０ 通信チャネル
５０，６０，７０ スレーブ装置
８０ 調停制御回路
８２ 入力インターフェイス
８４ 優先順位付け回路
８６ 出力インターフェイス
１００ 外部通信チャネル
１１０，１２０，１３０，１４０ プロセッサコア
１５０ 内部通信チャネル
２１５，２３５ フィルタ
２５５ カウンタ
６００ エネルギ管理コントローラ
【特許請求の範囲】
【請求項１】
通信チャネルを介して送られるメッセージ間の調停を行うデータ処理装置であって、
各々が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素と、
複数の処理要素間で共有され、それを介してメッセージが送られる通信チャネルと、
通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する調停回路と、を含み、
各処理要素はその上で実行中のプロセスに対する進捗データを発するようにされており、進捗データはプロセスに対する待ち時間含意を示し、さらに、
各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施し、かつ調停プロセスを制御するために優先順位付けデータを調停回路に出力する調停制御回路と、
を含むデータ処理装置。
【請求項２】
請求項１に記載のデータ処理装置であって、各処理要素は通信チャネルに接続されたマスター装置であるデータ処理装置。
【請求項３】
請求項２に記載のデータ処理装置であって、各メッセージは前記マスター装置の１つにより発せられるアクセス要求であるデータ処理装置。
【請求項４】
請求項１に記載のデータ処理装置であって、各プロセスはプログラム・スレッドであり、各処理要素は単一プログラム・スレッドを実行するデータ処理装置。
【請求項５】
請求項１に記載のデータ処理装置であって、少なくとも１つの処理要素は多数の処理装置を含み、各処理装置がプログラム・スレッドを実行するデータ処理装置。
【請求項６】
請求項１に記載のデータ処理装置であって、データ処理装置はシステム・オン・チップであるデータ処理装置。
【請求項７】
請求項１に記載のデータ処理装置であって、進捗データは関連するプロセスがリアルタイムプロセスであるか非リアルタイムプロセスであるかを識別し、リアルタイムプロセスに対して、進捗データは少なくともそのリアルタイムプロセスにより発せられるメッセージの残りの処理時間を示すスラック値をさらに識別し、非リアルタイムプロセスに対して、進捗データは少なくとも予め定められた時間にわたりそのプロセスに関連する待ち時間を示す待ち時間値をさらに識別するデータ処理装置。
【請求項８】
請求項７に記載のデータ処理装置であって、さらに、非リアルタイムプロセスを実行する各処理要素に関連するフィルタ回路を含み、フィルタ回路は単位時間当たり待ち時間の形の前記待ち時間値を作り出すデータ処理装置。
【請求項９】
請求項７に記載のデータ処理装置であって、少なくとも１つの非リアルタイムプロセスはそれに関連する重み付けを有し、その重み付けはその非リアルタイムプロセスに対する待ち時間値を作り出す時に考慮されるデータ処理装置。
【請求項１０】
請求項７に記載のデータ処理装置であって、さらに、リアルタイムプロセスを実行する各処理要素に関連するカウンタ回路を含み、カウンタ回路は前記スラック値を作り出すデータ処理装置。
【請求項１１】
請求項７に記載のデータ処理装置であって、非リアルタイムプロセスに対して、進捗データはそのプロセスが停止しているか否かを識別するストール値をさらに識別するデータ処理装置。
【請求項１２】
請求項７に記載のデータ処理装置であって、非リアルタイムプロセスに対して、進捗データはプロセスが停止する前にそのプロセスにより発せられるメッセージを処理する残り時間を示すスラック値をさらに識別するデータ処理装置。
【請求項１３】
請求項７に記載のデータ処理装置であって、そのリアルタイムプロセスにより発せられるメッセージを処理する残り時間が予め定められた閾値よりも大きいことをそのリアルタイムプロセスのスラック値が示す場合に、優先順位付けプロセスはリアルタイムプロセスよりも非リアルタイムプロセスに優先順位を与えるデータ処理装置。
【請求項１４】
請求項７に記載のデータ処理装置であって、優先順位付けプロセスは待ち時間値の低い非リアルタイムプロセスよりも待ち時間値の高い非リアルタイムプロセスに優先順位を与えるデータ処理装置。
【請求項１５】
請求項１４に記載のデータ処理装置であって、非リアルタイムプロセスに対して進捗データはそのプロセスが停止しているか否かを識別するストール値をさらに識別し、異なるストール値を有する２つのリアルタイムプロセスに対して、優先順位付けプロセスはプロセスが停止していることをそのストール値が示す非リアルタイムプロセスに待ち時間値のより高いプロセスよりも優先的に優先順位を与えるデータ処理装置。
【請求項１６】
請求項１４に記載のデータ処理装置であって、非リアルタイムプロセスに対して進捗データはプロセスが停止する前にそのプロセスにより発せられるメッセージを処理する残り時間を示すスラック値をさらに識別し、異なるストール値を有する２つのリアルタイムプロセスに対して、優先順位付けプロセスは最少スラックを有する非リアルタイムプロセスに待ち時間値のより高いプロセスよりも優先的に優先順位を与えるデータ処理装置。
【請求項１７】
請求項１に記載のデータ処理装置であって、さらに、
前記複数の処理要素の中の１つ以上の処理要素の動作パフォーマンスレベルを制御するエネルギ管理回路を含み、エネルギ管理回路は動作パフォーマンスレベルを決定する時にこれら１つ以上の処理要素により発せられる進捗データの少なくとも一部を考慮して動作するデータ処理装置。
【請求項１８】
請求項１７に記載のデータ処理装置であって、進捗データは関連するプロセスがリアルタイムプロセスであるか非リアルタイムプロセスであるかを識別し、リアルタイムプロセスに対して、進捗データは少なくともそのリアルタイムプロセスにより発せられるメッセージの残りの処理時間を示すスラック値をさらに識別し、非リアルタイムプロセスに対して、進捗データは少なくとも予め定められた時間にわたりそのプロセスに関連する待ち時間を示す待ち時間値をさらに識別し、前記進捗データの少なくとも一部は非リアルタイムプロセスを実行する１つ以上の処理要素により出力される待ち時間値を含むデータ処理装置。
【請求項１９】
各々が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素を有するデータ処理装置の通信チャネルを介して送られるメッセージ間の調停方法であって、通信チャネルはそれを介してメッセージが送られる複数の処理要素間で共有され、前記調停方法は、
その処理要素上で実行中のプロセスに対して各処理要素から進捗データを発するステップであって、進捗データはプロセスに対する待ち時間含意を示すステップと、
各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施するステップと、
通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施するステップであって、調停プロセスを制御するために優先順位付けデータが使用されるステップと、
を含む方法。
【請求項２０】
データ処理装置用調停制御回路であって、データ処理装置は各々が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素と、複数の処理要素間で共有され、それを介してメッセージが送られる通信チャネルと、通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する調停回路とを含み、調停制御回路は、
その処理要素上で実行中のプロセスに対する進捗データを各処理要素から受信する入力インターフェイスであって、進捗データはプロセスに対する待ち時間含意を示す入力インターフェイスと、
各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施する優先順位付け回路と、
調停プロセスを制御するために優先順位付けデータを調停回路に出力する出力インターフェイスと、
を含む調停制御回路。
【請求項１】
通信チャネルを介して送られるメッセージ間の調停を行うデータ処理装置であって、
各々が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素と、
複数の処理要素間で共有され、それを介してメッセージが送られる通信チャネルと、
通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する調停回路と、を含み、
各処理要素はその上で実行中のプロセスに対する進捗データを発するようにされており、進捗データはプロセスに対する待ち時間含意を示し、さらに、
各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施し、かつ調停プロセスを制御するために優先順位付けデータを調停回路に出力する調停制御回路と、
を含むデータ処理装置。
【請求項２】
請求項１に記載のデータ処理装置であって、各処理要素は通信チャネルに接続されたマスター装置であるデータ処理装置。
【請求項３】
請求項２に記載のデータ処理装置であって、各メッセージは前記マスター装置の１つにより発せられるアクセス要求であるデータ処理装置。
【請求項４】
請求項１に記載のデータ処理装置であって、各プロセスはプログラム・スレッドであり、各処理要素は単一プログラム・スレッドを実行するデータ処理装置。
【請求項５】
請求項１に記載のデータ処理装置であって、少なくとも１つの処理要素は多数の処理装置を含み、各処理装置がプログラム・スレッドを実行するデータ処理装置。
【請求項６】
請求項１に記載のデータ処理装置であって、データ処理装置はシステム・オン・チップであるデータ処理装置。
【請求項７】
請求項１に記載のデータ処理装置であって、進捗データは関連するプロセスがリアルタイムプロセスであるか非リアルタイムプロセスであるかを識別し、リアルタイムプロセスに対して、進捗データは少なくともそのリアルタイムプロセスにより発せられるメッセージの残りの処理時間を示すスラック値をさらに識別し、非リアルタイムプロセスに対して、進捗データは少なくとも予め定められた時間にわたりそのプロセスに関連する待ち時間を示す待ち時間値をさらに識別するデータ処理装置。
【請求項８】
請求項７に記載のデータ処理装置であって、さらに、非リアルタイムプロセスを実行する各処理要素に関連するフィルタ回路を含み、フィルタ回路は単位時間当たり待ち時間の形の前記待ち時間値を作り出すデータ処理装置。
【請求項９】
請求項７に記載のデータ処理装置であって、少なくとも１つの非リアルタイムプロセスはそれに関連する重み付けを有し、その重み付けはその非リアルタイムプロセスに対する待ち時間値を作り出す時に考慮されるデータ処理装置。
【請求項１０】
請求項７に記載のデータ処理装置であって、さらに、リアルタイムプロセスを実行する各処理要素に関連するカウンタ回路を含み、カウンタ回路は前記スラック値を作り出すデータ処理装置。
【請求項１１】
請求項７に記載のデータ処理装置であって、非リアルタイムプロセスに対して、進捗データはそのプロセスが停止しているか否かを識別するストール値をさらに識別するデータ処理装置。
【請求項１２】
請求項７に記載のデータ処理装置であって、非リアルタイムプロセスに対して、進捗データはプロセスが停止する前にそのプロセスにより発せられるメッセージを処理する残り時間を示すスラック値をさらに識別するデータ処理装置。
【請求項１３】
請求項７に記載のデータ処理装置であって、そのリアルタイムプロセスにより発せられるメッセージを処理する残り時間が予め定められた閾値よりも大きいことをそのリアルタイムプロセスのスラック値が示す場合に、優先順位付けプロセスはリアルタイムプロセスよりも非リアルタイムプロセスに優先順位を与えるデータ処理装置。
【請求項１４】
請求項７に記載のデータ処理装置であって、優先順位付けプロセスは待ち時間値の低い非リアルタイムプロセスよりも待ち時間値の高い非リアルタイムプロセスに優先順位を与えるデータ処理装置。
【請求項１５】
請求項１４に記載のデータ処理装置であって、非リアルタイムプロセスに対して進捗データはそのプロセスが停止しているか否かを識別するストール値をさらに識別し、異なるストール値を有する２つのリアルタイムプロセスに対して、優先順位付けプロセスはプロセスが停止していることをそのストール値が示す非リアルタイムプロセスに待ち時間値のより高いプロセスよりも優先的に優先順位を与えるデータ処理装置。
【請求項１６】
請求項１４に記載のデータ処理装置であって、非リアルタイムプロセスに対して進捗データはプロセスが停止する前にそのプロセスにより発せられるメッセージを処理する残り時間を示すスラック値をさらに識別し、異なるストール値を有する２つのリアルタイムプロセスに対して、優先順位付けプロセスは最少スラックを有する非リアルタイムプロセスに待ち時間値のより高いプロセスよりも優先的に優先順位を与えるデータ処理装置。
【請求項１７】
請求項１に記載のデータ処理装置であって、さらに、
前記複数の処理要素の中の１つ以上の処理要素の動作パフォーマンスレベルを制御するエネルギ管理回路を含み、エネルギ管理回路は動作パフォーマンスレベルを決定する時にこれら１つ以上の処理要素により発せられる進捗データの少なくとも一部を考慮して動作するデータ処理装置。
【請求項１８】
請求項１７に記載のデータ処理装置であって、進捗データは関連するプロセスがリアルタイムプロセスであるか非リアルタイムプロセスであるかを識別し、リアルタイムプロセスに対して、進捗データは少なくともそのリアルタイムプロセスにより発せられるメッセージの残りの処理時間を示すスラック値をさらに識別し、非リアルタイムプロセスに対して、進捗データは少なくとも予め定められた時間にわたりそのプロセスに関連する待ち時間を示す待ち時間値をさらに識別し、前記進捗データの少なくとも一部は非リアルタイムプロセスを実行する１つ以上の処理要素により出力される待ち時間値を含むデータ処理装置。
【請求項１９】
各々が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素を有するデータ処理装置の通信チャネルを介して送られるメッセージ間の調停方法であって、通信チャネルはそれを介してメッセージが送られる複数の処理要素間で共有され、前記調停方法は、
その処理要素上で実行中のプロセスに対して各処理要素から進捗データを発するステップであって、進捗データはプロセスに対する待ち時間含意を示すステップと、
各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施するステップと、
通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施するステップであって、調停プロセスを制御するために優先順位付けデータが使用されるステップと、
を含む方法。
【請求項２０】
データ処理装置用調停制御回路であって、データ処理装置は各々が受取要素へ発せられるメッセージを要求するプロセスを実行する複数の処理要素と、複数の処理要素間で共有され、それを介してメッセージが送られる通信チャネルと、通信チャネルを介して送られる多数のメッセージ間の調停を行う調停プロセスを実施する調停回路とを含み、調停制御回路は、
その処理要素上で実行中のプロセスに対する進捗データを各処理要素から受信する入力インターフェイスであって、進捗データはプロセスに対する待ち時間含意を示す入力インターフェイスと、
各処理要素からの進捗データに応答して、優先順位付けデータを発生するために進捗データにより示される各プロセスの待ち時間含意を考慮して優先順位付けプロセスを実施する優先順位付け回路と、
調停プロセスを制御するために優先順位付けデータを調停回路に出力する出力インターフェイスと、
を含む調停制御回路。
【図１】
【図２Ａ】
【図２Ｂ】
【図３Ａ】
【図３Ｂ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２Ａ】
【図２Ｂ】
【図３Ａ】
【図３Ｂ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２００８−２３４６５９（Ｐ２００８−２３４６５９Ａ）
【公開日】平成２０年１０月２日（２００８．１０．２）
【国際特許分類】
【出願番号】特願２００８−７３１５６（Ｐ２００８−７３１５６）
【出願日】平成２０年３月２１日（２００８．３．２１）
【出願人】（５９４１５４４２８）エイアールエム リミテッド (85)
【Ｆターム（参考）】
【公開日】平成２０年１０月２日（２００８．１０．２）
【国際特許分類】
【出願日】平成２０年３月２１日（２００８．３．２１）
【出願人】（５９４１５４４２８）エイアールエム リミテッド (85)
【Ｆターム（参考）】
[ Back to top ]