(57)【要約】【課題】マルチスレッド化プロセッサ・システム上での実行のために、スレッドについての優先順位値を決定する方法および装置を提供すること。【解決手段】優先順位ベース格付けおよびアプリケーション優先順位格付けに依存する優先順位値が決定される。優先順位ベース格付けは、他のスレッドに対するそのスレッドの優先順位格付けを表す。アプリケーション優先順位格付けは、スレッドのアプリケーションから見たスレッドの優先順位格付けを表す。【選択図】図２
2004206692.tif 000002
【特許請求の範囲】
【請求項１】
マルチスレッド化プロセッサ・システム上での実行のために、スレッドについての優先順位値を決定する方法であって、
優先順位ベース格付けを受け取ること、
スレッドのアプリケーションからアプリケーション優先順位格付けを受け取ること、および
前記優先順位ベース格付けおよび前記アプリケーション優先順位格付けに依存する前記優先順位値を決定することを含む方法。
【請求項２】
優先順位ベース格付けが、他のスレッドに対する前記スレッドの優先順位格付けを表し、
前記アプリケーション優先順位格付けが、前記スレッドのアプリケーションから見た前記スレッドの優先順位格付けを表す請求項１に記載の方法。
【請求項３】
前記優先順位ベース格付けが優先順位ベース値によって表され、前記アプリケーション優先順位格付けがアプリケーション優先順位値によって表される請求項１または２に記載の方法。
【請求項４】
前記優先順位値が、定義された範囲に限定される請求項１ないし３のいずれか一項に記載の方法。
【請求項５】
前記優先順位ベース値が、前記範囲の下限を定義する請求項４に記載の方法。
【請求項６】
優先順位最大値が、前記範囲の上限を定義する請求項４または５に記載の方法。
【請求項７】
前記優先順位ベース値と前記アプリケーション優先順位値を加算することによって主値を受け取ることを含む請求項３に記載の方法。
【請求項８】
前記主値と前記最大値のうち小さい方の値である第１下位値を決定することを含む請求項７に記載の方法。
【請求項９】
前記スレッドの外部優先順位格付けを受け取ること、および
前記外部優先順位格付けに依存する前記優先順位値を決定することを含む請求項１ないし８のいずれか一項に記載の方法。
【請求項１０】
前記外部優先順位格付けが、外部の必要を考慮する前記スレッドの優先順位格付けを表し、
前記外部優先順位格付けが外部優先順位値によって表される請求項９に記載の方法。
【請求項１１】
外部制限値を定義すること、および
前記外部優先順位値と前記外部制限値のうち小さい方の値である第２下位値を決定することを含む請求項１０に記載の方法。
【請求項１２】
前記第１下位値および前記第２下位値の関数として前記優先順位値を受け取ることを含む請求項１１に記載の方法。
【請求項１３】
前記優先順位値の特定の計算に関係する値のうち少なくとも１つが変化したときに、前記優先順位値が新たに決定される請求項１ないし１２のいずれか一項に記載の方法。
【請求項１４】
優先順位値がスレッドごとに決定され、
前記スレッドが、それぞれの優先順位値に従ってランク付けされる請求項１ないし１３のいずれか一項に記載の方法。
【請求項１５】
マルチスレッド化プロセッサ・システム上での実行のために、スレッドについての優先順位値を決定する装置であって、
優先順位ベース値を保管するためのベース値レジスタと、
スレッドのアプリケーションから送達された前記優先順位ベース値およびアプリケーション優先順位値に依存する優先順位値を決定するための評価ユニットとを備える装置。
【請求項１６】
前記優先順位ベース値が、他のスレッドに対する前記スレッドの優先順位格付けを表し、
前記アプリケーション優先順位格付け値が、前記スレッドのアプリケーションから見た前記スレッドの優先順位格付けを表す請求項１５に記載の装置。
【請求項１７】
前記優先順位値が、定義された範囲に限定される請求項１５または１６に記載の装置。
【請求項１８】
前記優先順位ベース値が、前記範囲の下限を定義する請求項１７に記載の装置。
【請求項１９】
前記範囲の上限を定義する優先順位最大値を保管するための最大値レジスタを備える請求項１８に記載の装置。
【請求項２０】
前記評価ユニットが、前記優先順位ベース値と前記アプリケーション優先順位値を加算し、主値を得るための加算器を備える請求項１５ないし１９のいずれか一項に記載の装置。
【請求項２１】
前記評価ユニットが、前記主値と前記最大値のうち小さい方の値である第１下位値を決定するための最小値関数を有する請求項２０に記載の装置。
【請求項２２】
前記評価ユニットが、外部の必要を考慮する前記スレッドの外部優先順位値に依存する前記優先順位値を決定するように設計される請求項１５ないし２０のいずれか一項に記載の方法。
【請求項２３】
外部制限値を保管するための外部制限値レジスタを備え、
前記評価ユニットが、前記外部優先順位値と前記外部制限値のうち小さい方の値である第２下位値を決定するための第２最小値関数を有する請求項２２に記載の装置。
【請求項２４】
前記評価ユニットが、前記第１下位値と前記第２下位値を加算して前記優先順位値を得るための第２加算器を備える請求項２３に記載の装置。
【請求項２５】
スレッドごとの優先順位値を決定するために、対応するレジスタおよび評価ユニットが設けられ、
それぞれの優先順位値に従って前記スレッドをランク付けするソータが設けられる請求項１５ないし２４に記載の装置。
【請求項２６】
装置のプロセッサ・ユニット内にロードされたときに、コンピュータが請求項１ないし１２のいずれか一項に記載の方法を実施するように前記プロセッサ・ユニットを構成するコンピュータ・プログラム・コードを含むコンピュータ・プログラム要素。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチスレッド化プロセッサ・システム上での実行のために、スレッドについての優先順位値を決定する方法および装置に関する。
【背景技術】
【０００２】
ハードウェア・マルチスレッド化をサポートするプロセッサまたはプロセッサ・コア（ＭＴＰ＝マルチスレッド化プロセッサ）では、いくつかのスレッドを同時に実行することができる。以下では、スレッドという用語を、技術的な術語によればルーチン、１組の命令、タスク、またはプロセスとも呼ばれるものに対する同義語として用いる。キャッシュ・ミス、コプロセッサの使用、または同期機構のために、スレッドの一部が、限られた時間待機しなければならないことがある。この時間では、こうしたスレッドからの命令は実行することができない。通常、残りのスレッドが、演算論理装置またはメモリ・インターフェースなどの処理資源／実行パイプラインを求めて競合する。スレッドは異なる実行パイプで並列に実行することができ、競合は、これらの実行パイプのうち１つまたは複数に対するものである。この競合は、次に命令を実行する１つまたは複数のスレッドを選択することによって解決しなければならない。
【０００３】
そのようなプロセッサに命令の発行を制御する方式が存在しない場合、実行することができる単一スレッドは、単一スレッド・プロセッサ・システム上で実行するよりも低速となる。最近は、リアル・タイム制約のあるシステム、例えばネットワークやメディア・プロセッサに対してもＭＴＰが使用されている。こうした分野では、スレッドの実行時間要件が、いくつかの問題点に応じて変動する可能性がある。したがって、スレッド実行の差別化を保証することが重要である。その目的に対して、スレッドから命令を発行する方式を制御する機構は高価である。
【０００４】
文献で調査され、議論されている現在の方法は、主にマルチスレッド化プロセッサの全スループットを向上させることに的を絞っている。
【０００５】
米国６１０５１２７号は、マルチスレッド化命令ストリームを実行するためのマルチスレッド化プロセッサを開示している。保持ユニットで保持される優先順位レベルに従って、同時に要求を発行する２つ以上の命令によって指定される機能単位にどの命令を発行するかを決定するための制御ユニットが設けられる。
【０００６】
米国６２１２５４４Ｂ１号は、少なくとも２つのスレッド間の切換えを制御する方法を開示している。優先順位は、低、中、高の３つの優先順位値のうちの１つのためのスレッド優先順位フィールドを有するスレッド状態レジスタによって取り込まれる。
【０００７】
米国６４７７５６２Ｂ２号は、マルチストリーミング・プロセッサ用の命令スケジューリングを導入している。優先順位コントローラが、命令の選択、およびある資源へのアクセス権についての優先順位を生成する。
【０００８】
多くのシステムでは、様々な重要度のタスクが、プロセッサのスレッドに割り当てられる。そのような状況では、最も重要なタスクが最初に、すなわち高速に実行されることを保証するように命令選択プロセスを制御しなければならない。同時に、命令選択を制御する労力が非常に小さくなるべきである。そのことは、アプリケーションについての処理能力の合計量に影響を及ぼし、具体的には低下させるからである。
【特許文献１】米国６１０５１２７号
【特許文献２】米国６２１２５４４Ｂ１号
【特許文献３】米国６４７７５６２Ｂ２号
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、その時点での実行の真の必要を考慮に入れてスレッドの優先順位値を定義する、マルチスレッド化プロセッサ・システム上での実行のために、スレッドについての優先順位値を決定する方法および装置を提供することが望ましい。本発明の別の目的は、優先順位値の決定を最小のコストかつ高速で実施することである。
【課題を解決するための手段】
【００１０】
本発明の一態様によれば、マルチスレッド化プロセッサ・システム上での実行のために、スレッドについての優先順位値を決定する方法が提供される。この方法は、優先順位ベース格付けを受け取ること、スレッドのアプリケーションからアプリケーション優先順位格付けを受け取ること、およびベース格付けおよびアプリケーション優先順位格付けに依存する優先順位値を決定することを含む。
【００１１】
評価すべきスレッドは、マルチスレッド化プロセッサ・システム上での実行を待機するスレッドのキュー内のスレッドでよく、または既に実行を開始したが再評価することができるスレッドでよく、最終的に、他の待ちスレッド、さらには実行スレッドの優先順位値の変化に従って再ランク付けすることができ、したがってリセットして待ちスレッドのキューに入れることができ、または実行を続行することができる。
【００１２】
スレッドについての正当化される優先順位レベルは、スレッドのアプリケーション自体からのスレッドの優先順位評価に依存する。スレッドのアプリケーションは、単一スレッドの個々の要件についての固有の知識を有する。このようなアプリケーション優先順位格付けは、スレッドの、関連付けられたアプリケーションから送達することができ、またはスレッド自体に添付される種類のものでよい。好ましくは、優先順位格付け情報の追加のソースは、システム中の全スレッドの様々な相対的要件についての固有の知識を有するマルチスレッド化プロセッサ・システムである。マルチスレッド化プロセッサ制御ユニット、例えばそのオペレーティング・システムまたは何らかの他の制御論理が、優先順位ベース値を本発明の装置に送達し、または本発明の方法の入力として送達するためのマルチスレッド化プロセッサ・システムの好ましいソースである。しかし、他のプロセッサ・システムもマルチスレッド化プロセッサ・システムのスレッドを相対的に格付けすることができる。
【００１３】
優先順位値は、最終的には、関連する他の優先順位値を有する他のスレッドとの間でスレッドのランク付けを可能にし、具体的にはスレッドについてのアクセス時間および資源を決定するものであり、優先順位ベース値およびアプリケーション優先順位値に基づく。このことは、少なくともそうした２つの格付けが何らかの形で優先順位値に影響を及ぼすことを意味する。
【００１４】
本発明は多くの利点を提示する。スレッド優先順位付け方法および装置は、明確かつ独自の方式で、スレッドの優先順位に影響を及ぼす様々なソースからの入力格付けを考慮する。こうした格付けは、入力ソースの観点から行われる。ソースは、ソースがアクセスを有する様々な情報に基づいて様々なビューを取るように選択される。
【００１５】
こうしたソースの入力値は、スレッド間の差別化を相対的に得ることができるように構築される。これにより、決定プロセスおよび入力更新プロセスが大いに単純化される。
【００１６】
命令選択のために使用される優先順位は、いくつかのソースから、最小限のソフトウェア／ハードウェア労力で修正することができる。
【００１７】
アプリケーション・コードは、その優先順位全体と、それが実行されるハードウェア状況とは無関係である。これにより、プログラム・コード・サイズおよび命令数が削減される。
【００１８】
提案の発明を、多数のハードウェア・スレッドと、スレッド優先順位への寄与の広範な分解能（resolution）と共に使用することができる。
【００１９】
様々なソースの、各スレッドの優先順位に対する影響は、ソースの寄与の修正ごとに制御プログラムの呼出しを行うことなく、制御ユニット（例えばオペレーティング・システム）で制御することができる。
【００２０】
優先順位ベース格付けは、他のスレッドに対するスレッドの優先順位格付けを表すことが好ましい。他のスレッドのベース優先順位値は通常、あるスレッドのベース優先順位値の決定に影響を及ぼす。マルチスレッド化プロセッサ・システムは、スレッドのベース優先順位値を、他のスレッドのベース優先順位値に対して評価する。アプリケーション優先順位格付けは、スレッドのアプリケーションから見たスレッドの優先順位格付けを表すことが好ましい。アプリケーションは、例えば格付けすべきスレッドが、アプリケーション全体のうちの重要な部分であり、または他のスレッドで表されるアプリケーションの他の部分と比べて非常に迅速に処理しなければならないことを認識することがある。そのような場合、アプリケーションは、このスレッドに高いアプリケーション優先順位レベルを与える。
【００２１】
優先順位ベース格付けは通常、優先順位ベース値によって表され、アプリケーション優先順位格付けは通常、アプリケーション優先順位値によって表される。そのような値は通常、装置が注意を向けたときにそれぞれのレジスタに格納される。
【００２２】
本発明の好ましい実施形態によれば、優先順位ベース値とアプリケーション優先順位値とを加算することによって主値が得られる。一実施形態では、この主値は優先順位値として使用することができる。別の実施形態では、この主値が、優先順位値の基となる暫定値として使用される。主値は、プロセッサおよびアプリケーションの、スレッドの優先順位格付けを反映している。
【００２３】
本発明の別の好ましい実施形態では、優先順位最大値が導入され、優先順位最大値および優先順位ベース値が、優先順位値についての１組の初期境界を定義する。優先順位最大値は、プロセッサ・システムから送達することができ、したがって優先順位ベース値およびアプリケーション優先順位値に基づく優先順位値が通常は超過すべきでない最大値が定義される。優先順位最大値はまた、優先順位ベース値の影響を受ける装置で計算することもできる。次いで、マルチスレッド化プロセッサ・システムから優先順位ベース値を転送するだけでよい。優先順位最大値は、異なるスレッドについて変更することができる。さらに、優先順位最大値および優先順位ベース値によって定義され、優先順位最大値および優先順位ベース値を境界として有する範囲は、スレッドごとに異なる拡張を有することができる。
【００２４】
好ましくは、第１下位値は、主値と最大値のうち小さい方の値として決定される。これは、優先順位ベース値とアプリケーション優先順位値の和が優先順位最大値を超過するときであっても、与えられた優先順位最大値に優先順位値を制限するためである。優先順位最大値の導入は、スレッドが処理能力を完全には限定せず、したがって他の待ちスレッドを窮乏（starve）させないことを保証するのに用いられる。一実施形態では、第１下位値は、考慮するスレッドについての優先順位値としても使用することができる。
【００２５】
本発明の別の好ましい実施形態では、スレッドの外部優先順位格付けが受領され、外部優先順位格付けに依存する優先順位値が決定される。外部入力は、考慮する価値がある。外部寄与は、異なるビューを取り、アプリケーションまたはマルチスレッド化プロセッサ・システムとは異なる考慮に基づくので、優先順位格付けの別の独立なソースを表す。入力は特定の外部要求に限定されないが、いくつかの外部寄与に拡張することができる。
【００２６】
好ましくは、外部優先順位格付けは、外部の必要を考慮するスレッドの優先順位格付けを表し、外部優先順位格付けは外部優先順位値によって表される。
【００２７】
別の好ましい実施形態では、外部制限値が定義され、外部優先順位値と外部制限値のうち小さい方の値である第２下位値が決定される。
【００２８】
この実施形態では、外部制限値は、スレッド、具体的にはその外部優先順位格付けが他のスレッドについての処理能力を完全には限定せず、したがって他の待ちスレッドを窮乏させないことを保証するのに使用される。好ましくは、外部制限値は装置自体で設定され、またはマルチスレッド化プロセッサ・システムによって伝送することができる。
【００２９】
好ましくは、優先順位値は、第１下位値と第２下位値の関数として得られる。例えば、これらの値を加算し、または最大値関数の対象とすることができる。このようにして優先順位値を決定するとき、優先順位値は、優先順位ベース値と、優先順位最大値に外部制限値を加えたものとの間の値の範囲に先験的に限定される。上限は、アプリケーションおよびプロセッサ・システムの格付けだけを考慮した場合の実施形態に対して拡張される。追加の外部格付けは、優先順位値についての範囲の、より大きい上限を可能にするだけの価値がある可能性がある。
【００３０】
本発明の別の好ましい実施形態では、優先順位値の特定の計算に関係する値のうち少なくとも１つが変化したときに優先順位値が新たに求められる。これにより、変更に応答し、それに応じて優先順位レベルを適合させる方法および装置が作成される。
【００３１】
好ましくは、優先順位値がスレッドごとに求められ、スレッドが、それぞれの優先順位値に従ってランク付けされる。異なるスレッドの優先順位値はまだ数値である。こうした値をランク付けに変換するために、ソータを使用することが好ましい。次いで、マルチスレッド化処理システムは、ランク付けに従ってスレッドを処理することができる。
【００３２】
本発明の別の態様によれば、マルチスレッド化システム上での実行のために、各スレッドについての値を決定する装置が提供される。この装置は、プロセッサ・システムから送達された優先順位ベース値を保管するためのベース値レジスタと、スレッドのアプリケーションから送達された優先順位ベース値およびアプリケーション優先順位値に依存する優先順位値を決定するための評価ユニットとを備える。
【００３３】
評価ユニットは、ハードウェアまたはソフトウェア、あるいはそれらの組合せとして実装することができ、または任意のその他の適切な実装として実装することができるが、具体的にはネットワーク処理の分野で使用したときに、コストが限定され、応答および速度が迅速であるため、ハードウェアの形での実装が好ましい。
【００３４】
本発明の装置およびその実施形態の利点は、前述の本発明の方法およびその実施形態の利点に付随する。
【００３５】
本発明の別の態様によれば、装置のプロセッサ・ユニット中にロードされたときに、前述の方法または方法の実施形態のうちのいずれか１つを実行するためのプロセッサ・ユニットを構成するコンピュータ・プログラム・コードを含むコンピュータ・プログラム要素が提供される。
【００３６】
現在のところ好ましいが、それでも本発明による例示的な実施形態である以下の詳細な説明を添付の図面と一緒に参照することにより、本発明およびその実施形態をより完全に理解されよう。
【００３７】
それぞれの図は、類似または同一の内容を有する要素を表す同一の参照番号を含むことがある。
【発明を実施するための最良の形態】
【００３８】
図１に、装置１および関連するマルチスレッド化プロセッサ・システム２のブロック図を示す。
【００３９】
提案の装置１は、スレッド・ランクｒをマルチスレッド化プロセッサ・システム２の命令選択要素２２に供給し、かつ制御ユニット２１、実行パイプライン２３、および外部ソース３から値を受け取ることにより、少なくとも制御ユニット２１およびソフトウェアを有するマルチスレッド化プロセッサ・システム２と通信する。外部ソース３は、外部優先順位値ｅ＿ｉを装置１に供給し、制御ユニット２１は、優先順位ベース値ｂ＿ｉおよび最大優先順位値ｍ＿ｉを装置１に供給する。アプリケーション優先順位格付けｓ＿ｉが実行パイプライン２３によって供給される。実行パイプライン２３は、ロード／ストア・コマンドＬＳによってスレッドのアプリケーションの優先順位格付けｓ＿ｉを装置１に通信する。制御ユニット２１から装置１への値ｂ＿ｉおよびｍ＿ｉの転送は、装置１内のレジスタを用いて実施することができる。マルチスレッド化プロセッサ・システム２は、「ロード」や「ストア」、または専用レジスタへの「アクセス」のような既存の命令を使用することによって装置１と通信する。例えば、図示するマルチスレッド化プロセッサ・システム２がPowerPCタイプのプロセッサである場合、専用命令を介してアクセスされる特殊機能レジスタまたはデバイス制御レジスタを使用することができる。そうでない場合、制御レジスタをメモリにマッピングすることによって通信を行うことができる。制御ユニットは外部エンティティまたはプロセッサ上のソフトウェア・プロセスでよいことに留意されたい。
【００４０】
装置１は、マルチスレッド化プロセッサ・システム２に組み込むことができ、またはプロセッサ・コアの一体部分を形成し、またはプロセッサ・コアの一部とすることができ、または別々に実装してインターフェース、例えば上記で論じたインターフェースを介して結合することができる。
【００４１】
図１のマルチスレッド化プロセッサ・システム２の右半分は、スレッドの処理を表す。実行のフロント部２４で始まり、次いで命令選択ユニット２２がそれぞれの情報を供給し、実行パイプライン２３が実行を実施する。
【００４２】
この実施形態では、スレッドに対する独立な優先順位格付けを装置に転送する３つの別々のソースが考慮され、この３つの優先順位格付けが、装置によってスレッドに割り振られる優先順位値（物理的優先順位とも呼ばれる）に影響を及ぼす。この３つのソースは以下のものである。
単一スレッドの個々の要件についての固有の知識を有するアプリケーション自体。
システム中のすべてのスレッドの様々な相対的要件についての固有の知識を有する、例えばオペレーティング・システムの一部としてのプロセッサ制御ユニット。
外部要求のステータスについての固有の知識を有する外部入力。この外部入力は、いくつかの外部寄与に対して広げることができる。
【００４３】
スレッドの通常の実行が、スレッドから見て中間のアプリケーション優先順位値ｓ＿ｉを使用すると仮定する。ある状況では、スレッドは後の実行がより小さいアプリケーション優先順位値ｓ＿ｉのものであることを認識することができる。これについての例は、スレッドが、後の時点で必要であり、その時点までに、行われる何らかの作用を有するスレッドが外部資源を要求するときである。この状況では、スレッドを低いアプリケーション優先順位値ｓ＿ｉで実行することが好ましく、したがって通常は、通常のアプリケーション優先順位値ｉで最初に実行するのではなく、より低い命令速度で実行され、要求した項目を後で待つ。これとは対照的に、スレッドが重要な資源、例えば頻繁に使用されるデータ・オブジェクトのセマフォーを占有したとき、その優先順位をより高いアプリケーション優先順位値ａ＿ｉに増加させて、この資源に対する圧力を低減することができる。
【００４４】
すべてのスレッドが同じコードを実行し、優先順位修正のオーバヘッドを低減することを可能にするため、スレッドの優先順位寄与にアクセスする共通の方式が望ましい。これは、既存の命令を介してアクセスされる専用レジスタ、例えばPowerPCプロセッサ中の特殊機能レジスタ（ＳＦＲ）またはデバイス制御レジスタ（ＤＣＲ）を使用することによって実施される。この考えは、すべてのスレッドが同じレジスタ番号を使用し、ハードウェアが、後で命令を実行したスレッドの識別を組み込むというものである。
【００４５】
しかし、スレッドは通常、同じプロセッサ上で他のどのスレッドが実行されるかを認識しない。したがって、重要度がより高いまたは低いタスクを有するスレッドが存在する可能性がある。これを考慮に入れるため、マルチスレッド化プロセッサ上でスレッドを制御する制御ユニットは、スレッドごとに優先順位ベース値ｂ＿ｉおよび最大優先順位値ｍ＿ｉを設定する。最大優先順位値ｍ＿ｉは、スレッドが他のスレッドを窮乏させないことを保証するのに使用することができる。優先順位ベース値ｂ＿ｉは、マルチスレッド化プロセッサ・システムの制御ユニットで割り当てられる相対的スレッド優先順位の平衡を保つ際の助けとなる。
【００４６】
図２に、そのような優先順位ベース値ｂ＿ｉ、そのような最大優先順位値ｍ＿ｉ、およびそのようなアプリケーション優先順位値ｓ＿ｉが供給される装置１の略図を示す。優先順位ベース値ｂ＿ｉはベース値レジスタ１１内に格納され、最大優先順位値ｍ＿ｉは最大値レジスタ１２内に格納される。アプリケーション優先順位値ｓ＿ｉも図２のレジスタ（図示せず）に格納することができる。
【００４７】
装置１は、加算器１４１および最小値関数１４２を含む評価ユニット１４をさらに備える。優先順位ベース値ｂ＿ｉおよびアプリケーション優先順位値ｓ＿ｉが加算され、主値ｍ＿ｖとなる。ある実施形態では、主値ｍ＿ｖはスレッドについての優先順位値とすることもできる。対照的に、この場合は、主値をさらに処理することが好ましい。最小値関数１４２の出力は、第１最小値ｆ＿ｖを送達する。第１最小値ｆ＿ｖは、f_v=min(m_i,b_i+s_i)である。
【００４８】
ある実施形態では第１最小値を物理的優先順位とすることができるが、物理的優先順位を決定する前に、第３の寄与が考慮される。この第３の優先順位評価は、外部ソースから来る。外部ソースの一例は同期コプロセッサである。考慮されるスレッドによって占有されるセマフォーを別のスレッドが要求したことを外部ソースが検出したとき、外部ソースは、通常の境界ｍ＿ｉを超えて一時的に優先順位をブーストすることができる。さらに、制限因子を導入することができる。この制限因子は、外部制限値レジスタ１３に格納される外部制限値ａ＿ｉである。
【００４９】
図２には図示していない関連するレジスタにも格納することができる、外部ソースから送達される値がｅ＿ｉである場合、優先順位値全体への寄与は、第２最小値s_v=min(a_i,e_i)をその出力で供給する最小値関数１４３によって決定される。次いで第２最小値ｓ＿ｖは、加算器１４４によって最小値ｆ＿ｖに加えられる。その結果は優先順位値ｐ＿ｏである。このようにしてスレッドが達することができる最大優先順位値ｐ＿ｏはm_i+a_iであることに留意されたい。
【００５０】
いくつかの外部ソースを使用する場合、それらを加算することにより、またはそれらの最大値を使用することにより、それらの値を組み合わせることができる。
【００５１】
図２は、ある単一スレッドについての優先順位値だけを計算するためのレジスタ１１から１３および評価ユニット１４を示すことに留意されたい。評価すべきスレッドがｎ個の場合、図２の点線で示すように、これらの要素をｎ倍設けなければならない。
【００５２】
このプロセスでは、ソースからの値の範囲を、物理的優先順位の有する値の範囲よりも広くすることが可能であることが望ましい。したがって、物理的優先順位についての最終的な値を生成するのにソート・ステップが必要となる可能性がある。ソータ１５は、優先順位値ｐ＿ｏからランク付けを生成することができる。ソータ出力は、優先順位値のランク付けｒである。ソータ１５は増分式に動作することができる。すなわち、ソータ１５は、入力のうち１つが変化するごとに、ソータ１５の出力ｒを再構成する。このようにして、ソータ１５のエリア・コストが削減される。
【００５３】
前述のように、加算器および２つの「最小」回路を含む構造は、プロセッサのハードウェア状況ごとに反復されることが好ましい。加算器、最小値関数、およびレジスタのような、ソータ１５の上のすべての構成要素は、精度を決定する共通幅ｗのビット・ベクトルに対して働くことができる。精度に対する適切な値は、意図するアプリケーションおよびスレッドの数に依存する。８から１６の範囲が、処理するスレッドの好ましい数である。ソータ１５は、入力の相対的サイズを保持するが、最小のサイズの出力ビット・ベクトルを生成する。例えば、８個のスレッドに対しては、各スレッドの優先順位値を表す３ビット・ベクトルで十分である。
【００５４】
図３に、本発明の実施形態による別の装置の略図を示す。この実施形態は、ベース優先順位値ｂ＿ｉからのオフセットとして最大優先順位値ｍ＿ｉを生成する。これは、ベース値レジスタ１１への優先順位ベース値ｂ＿ｉの書込みおよび最大値レジスタ１２へのオフセット値ｖ１の書込みの結果、加算器１４５によって優先順位最大値m_i=b_i+v1が得られることを意味する。同じことがａ＿ｉについても当てはまる。別のオフセット値ｖ２が外部制限値レジスタ１３に書き込まれ、加算器１４６によって優先順位ベース値ｂ＿ｉに加えられ、その結果、外部制限値ａ＿ｉが得られる。
【００５５】
このような挙動は、最小ブロックのそれぞれの前に加算器を挿入することによって得ることができる。
【００５６】
図２および図３では、すべてのレジスタ１１、１２、１３が２回描かれている。これは、非常に高速に切り換えることができるレジスタのいくつかの組を含む装置の提案の機能を示す。このようにして、緊急の状況で非常に迅速に適切な構成を確立することができ、通常のオペレーションに対して使用される以前の構成が保持され、エラー状態が解決された後に再び活動化することができる。エラー処理が改善される。ネットワーク・プロセッサでは、しばしば多数の他のプロセッサを指示する制御点が存在する。例示的なシナリオは、一部またはすべてのプロセッサについての通常オペレーション・レジスタ・セットと例外オペレーション・レジスタ・セットの間の制御点プロセッサ切換えである。
【００５７】
しかし、ある共通条件付き加算器１４７がレジスタに対する書込み経路および読取り経路で使用される場合、より安価な解決策が予想される。オフセット値ｖを供給する書込み経路を、続く図４に示す。
【００５８】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００５９】
（１）マルチスレッド化プロセッサ・システム上での実行のために、スレッドについての優先順位値を決定する方法であって、
優先順位ベース格付けを受け取ること、
スレッドのアプリケーションからアプリケーション優先順位格付けを受け取ること、および
前記優先順位ベース格付けおよび前記アプリケーション優先順位格付けに依存する前記優先順位値を決定することを含む方法。
（２）優先順位ベース格付けが、他のスレッドに対する前記スレッドの優先順位格付けを表し、
前記アプリケーション優先順位格付けが、前記スレッドのアプリケーションから見た前記スレッドの優先順位格付けを表す上記（１）に記載の方法。
（３）前記優先順位ベース格付けが優先順位ベース値によって表され、前記アプリケーション優先順位格付けがアプリケーション優先順位値によって表される上記（１）または（２）に記載の方法。
（４）前記優先順位値が、定義された範囲に限定される上記（１）ないし（３）のいずれか一項に記載の方法。
（５）前記優先順位ベース値が、前記範囲の下限を定義する上記（４）に記載の方法。
（６）優先順位最大値が、前記範囲の上限を定義する上記（４）または（５）に記載の方法。
（７）前記優先順位ベース値と前記アプリケーション優先順位値を加算することによって主値を受け取ることを含む上記（３）に記載の方法。
（８）前記主値と前記最大値のうち小さい方の値である第１下位値を決定することを含む上記（７）に記載の方法。
（９）前記スレッドの外部優先順位格付けを受け取ること、および
前記外部優先順位格付けに依存する前記優先順位値を決定することを含む上記（１）ないし（８）のいずれか一項に記載の方法。
（１０）前記外部優先順位格付けが、外部の必要を考慮する前記スレッドの優先順位格付けを表し、
前記外部優先順位格付けが外部優先順位値によって表される上記（９）に記載の方法。
（１１）外部制限値を定義すること、および
前記外部優先順位値と前記外部制限値のうち小さい方の値である第２下位値を決定することを含む上記（１０）に記載の方法。
（１２）前記第１下位値および前記第２下位値の関数として前記優先順位値を受け取ることを含む上記（１１）に記載の方法。
（１３）前記優先順位値の特定の計算に関係する値のうち少なくとも１つが変化したときに、前記優先順位値が新たに決定される上記（１）ないし（１２）のいずれか一項に記載の方法。
（１４）優先順位値がスレッドごとに決定され、
前記スレッドが、それぞれの優先順位値に従ってランク付けされる上記（１）ないし（１３）のいずれか一項に記載の方法。
（１５）マルチスレッド化プロセッサ・システム上での実行のために、スレッドについての優先順位値を決定する装置であって、
優先順位ベース値を保管するためのベース値レジスタと、
スレッドのアプリケーションから送達された前記優先順位ベース値およびアプリケーション優先順位値に依存する優先順位値を決定するための評価ユニットとを備える装置。
（１６）前記優先順位ベース値が、他のスレッドに対する前記スレッドの優先順位格付けを表し、
前記アプリケーション優先順位格付け値が、前記スレッドのアプリケーションから見た前記スレッドの優先順位格付けを表す上記（１５）に記載の装置。
（１７）前記優先順位値が、定義された範囲に限定される上記（１５）または（１６）に記載の装置。
（１８）前記優先順位ベース値が、前記範囲の下限を定義する上記（１７）に記載の装置。
（１９）前記範囲の上限を定義する優先順位最大値を保管するための最大値レジスタを備える上記（１８）に記載の装置。
（２０）前記評価ユニットが、前記優先順位ベース値と前記アプリケーション優先順位値を加算し、主値を得るための加算器を備える上記（１５）ないし（１９）のいずれか一項に記載の装置。
（２１）前記評価ユニットが、前記主値と前記最大値のうち小さい方の値である第１下位値を決定するための最小値関数を有する上記（２０）に記載の装置。
（２２）前記評価ユニットが、外部の必要を考慮する前記スレッドの外部優先順位値に依存する前記優先順位値を決定するように設計される上記（１５）ないし（２０）のいずれか一項に記載の方法。
（２３）外部制限値を保管するための外部制限値レジスタを備え、
前記評価ユニットが、前記外部優先順位値と前記外部制限値のうち小さい方の値である第２下位値を決定するための第２最小値関数を有する上記（２２）に記載の装置。
（２４）前記評価ユニットが、前記第１下位値と前記第２下位値を加算して前記優先順位値を得るための第２加算器を備える上記（２３）に記載の装置。
（２５）スレッドごとの優先順位値を決定するために、対応するレジスタおよび評価ユニットが設けられ、
それぞれの優先順位値に従って前記スレッドをランク付けするソータが設けられる上記（１５）ないし（２４）に記載の装置。
（２６）装置のプロセッサ・ユニット内にロードされたときに、コンピュータが上記（１）ないし（１２）のいずれか一項に記載の方法を実施するように前記プロセッサ・ユニットを構成するコンピュータ・プログラム・コードを含むコンピュータ・プログラム要素。
【図面の簡単な説明】
【００６０】
【図１】本発明の一実施形態による装置と、関連するマルチスレッド化プロセッサ・システムのブロック図である。
【図２】本発明の一実施形態による装置の略図である。
【図３】本発明の一実施形態による別の装置の略図である。
【図４】本発明の実施形態による装置で使用される代替レジスタ構造である。
【符号の説明】
【００６１】
１  装置
２  マルチスレッド化プロセッサ・システム
３  外部ソース
１１  ベース値レジスタ
１２  最大値レジスタ
１３  外部制限値レジスタ
１４  評価ユニット
１５  ソータ
２１  制御ユニット
２２  命令選択要素、命令選択ユニット
２３  実行パイプライン
２４  フロント部
１４１  加算器
１４２  最小値関数
１４３  最小値関数
１４４  加算器
１４５  加算器
１４６  加算器
１４７  加算器
【図１】
2004206692.tif 000003
【図２】
2004206692.tif 000004
【図３】
2004206692.tif 000005
【図４】
2004206692.tif 000006