(57)【要約】  本発明は、複数の異なる種類の処理ユニットを含む再設定可能な情報処理システムの設定情報を表すビットストリームを階層化メモリにプリロードする方法である。本方法は、所与のタスクの実行に続いて所与の種類の処理ユニットで実行可能なタスクを決定する非実行ステップを含んでいる。本方法はまた、所与のタスクの実行中に、実行可能なタスクの各々について、所与のタスクの現在の実行に関する情報に依存する優先順位を計算するステップも含んでいる。本方法はまた、所与のタスクの実行中に、実行可能なタスクをそれらの優先順位に従いソートするステップも含んでいる。本方法はまた、所与のタスクの実行中に、優先順位が最高のタスクを優先させながら、実行可能なタスクの実行に有用な設定情報を表すビットストリームをメモリにプリロードするステップも含んでいる。応用例：マイクロエレクトロニクス、内蔵システム【選択図】      図３
2011511377.tif 000002
【特許請求の範囲】
【請求項１】
複数の異なる種類の処理ユニット（２，３，４）を含む再設定可能な情報処理システムの設定情報、すなわち所与のタスクの実行に適した処理ユニットの可能な論理的編成を記述している設定を表すビットストリームを階層化メモリ（１０，１１，１２，１６）にプリロードする方法であって、
−所与のタスクの実行に続いて所与の種類の処理ユニットで実行可能なタスクを決定する非実行ステップと、
−前記所与のタスクの実行中に、実行可能な前記タスクの各々について、前記所与のタスクの現在の実行に関する情報に依存する優先順位を計算するステップと、
−前記所与のタスクの実行中に、前記実行可能なタスクをそれらの優先順位に従いソートするステップと、
−前記所与のタスクの実行中に、優先順位が最高のタスクを優先させながら、前記実行可能なタスクの実行に有用な設定情報を表すビットストリームを前記階層化メモリにプリロードするステップとを含むことを特徴とする方法。
【請求項２】
前記設定のプリローディングは、オペレーティングシステムによるメモリ（１０）へのロード要求が発行された際に割り込みが発生し、前記ロード要求が最初に処理されて、前記プリローディング方法が前記システムの動作を減速させないようにすることを特徴とする、請求項１に記載の方法。
【請求項３】
各種の処理ユニットについて、前記所与のタスクの実行に続いて前記所与の種類の処理ユニットで実行可能なタスクを示す依存性グラフ（ＴＣＤＧ）が構築されることを特徴とする、請求項１に記載の方法。
【請求項４】
前記依存性グラフ（ＴＣＤＧ）が、前記所与のタスクの実行に続いて前記所与の種類の処理ユニットで実行可能なタスクの各々について、アプリケーションパッケージ処理を記述するグラフ（ＣＤＧ，ＣＤＦＧ）を用いて構築されることを特徴とする、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
実行可能なタスクの優先順位が、Ｎ個のパラメータｐｉ、ｉ∈｛１，．．，Ｎ｝（Ｎは非ゼロ整数）の重み付き和であって、前記和における各パラメータｐｉがｎｉ乗（ｎｉは非ゼロ整数）され、パラメータｐｉがオペレーティングシステムにより実行中に動的に与えられることを特徴とする、請求項１に記載の方法。
【請求項６】
パラメータｐｉが実行前に静的に与えられることを特徴とする、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
実行可能なタスクの優先順位が、オペレーティングシステムにより与えられる処理優先順位に依存することを特徴とする、請求項１に記載の方法。
【請求項８】
実行可能なタスクの優先順位が、前記所与の種類の処理ユニットの相対的な計算負荷に依存することを特徴とする、請求項１に記載の方法。
【請求項９】
実行可能なタスクの優先順位が、前記所与の種類の処理ユニットにおける平均実行時間に依存することを特徴とする、請求項１に記載の方法。
【請求項１０】
実行可能なタスクの優先順位が、前記所与のタスクにおける条件分岐命令を実行する確率に依存することを特徴とする、請求項１に記載の方法。
【請求項１１】
前記メモリ（１０）が階層化メモリであることを特徴とする、請求項２に記載の方法。
【請求項１２】
前記設定が、パラメータ化可能なサイズのビットのブロックとして前記階層化メモリ（１０，１１，１２，１６）にプリロードされていることを特徴とする、請求項１に記載の方法。
【請求項１３】
前記再設定可能なシステムがチップ上のシステムであって、ハードウェアモジュール（１）の形式で実装されていることを特徴とする、請求項１に記載の方法。
【請求項１４】
前記ハードウェアモジュール（１）がキャッシュメモリ（２６）を含むことを特徴とする、請求項１〜１３のいずれか一項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の異なる種類の処理ユニットを含む再設定可能な情報処理システムの設定をメモリにプリロードする方法に関する。設定は、処理動作を実行するためのデジタルアーキテクチャの準備に必要な任意の種類の情報を含んでいる。本発明は、例えばマイクロエレクトロニクス分野または高い計算能力を有する組込み電子システム分野に適用できる。
【背景技術】
【０００２】
再設定可能なアーキテクチャとは、「処理コア」とも呼ばれるいくつかのハードウェア処理ユニットを含む情報処理構造であって、特定の処理動作を効果的に実行すべく構成要素および編成が適合されていてよい。そのようなアーキテクチャは、処理情報のために再設定可能な回路を利用する。再設定可能な回路は、例えばＰＡＣＴ社製の「ｅＸｔｒｅｍｅ  Ｐｒｏｃｅｓｓｉｎｇ  Ｐｌａｔｆｏｒｍ」アーキテクチャのように粗粒度のものであってよい。粗粒度の再設定可能な回路は、例えば算術的乗算のような複雑な演算を許す処理ユニットを含んでいる。再設定可能な回路はまた、「Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ」の頭文字であるＦＰＧＡ等の微細粒度の回路であってよい。微細粒度の再設定可能な回路は、例えば「ｏｒ」または「ａｎｄ」等の論理演算を許す処理ユニットを含んでいる。
【０００３】
いくつかの再設定のモードが存在する。再設定可能なアーキテクチャは、１回で再設定が完了しても、あるいは部分的に再設定されてもよいため、アプリケーションの一部を効果的に実行可能である。また、処理の実行中に動的に再設定する、すなわち処理が終了していないにもかかわらず、設定の変更を許す機構を用いることができる。特定のケースでは、完全なアプリケーションを実行するために複数回再設定が必要な場合がある。動的な再設定の実装に係る問題に、設定情報の復旧や、ある設定から別の設定への変更があり、特にオーバーヘッド時間が生じる場合に顕著である。この情報により形成される集合は、極めて可変的な構造および内容を含んでいることがある。動的に再設定可能なアーキテクチャでは、処理動作の実行前に設定データをメモリにロードすることに起因して、アプリケーションの実行を遅延させる再設定待ち時間が負担となる。これは本発明が解決すべき技術的な問題の一つである。
【０００４】
一般に「Ｓｙｓｔｅｍ−ｏｎ−Ｃｈｉｐ」の頭文字「ＳｏＣ」で表されるシステムオンチップは、複数の比較的複雑な計算要素を単一のチップへ集積することを可能にする。ＳｏＣはこのように、いくつかの再設定可能なコアを、オプションとして異なる粒度で含んでいてよい。このようなアーキテクチャは、計算要素のプログラム形式が互いに互換でない場合に「異種である」と言われる。様々な種類の計算要素により認識されるプログラム形式は各種のカテゴリに属していてよく、これらにより、インストラクションストリームの形式、または処理ユニットのハードウェア編成を記述する設定の形式で、または別途混合形式で反復的プログラムを実行することが可能になる。次いでソフトウェアの異なる部分を用いて、問題の形式、例えばいくつかのコンパイラを準備しなければならない。従って、異種な動的な再設定可能アーキテクチャには固有のプログラムモデルが存在しない。これもまた本発明が解決すべきであると提案する技術的問題の一つである。
【０００５】
オペレーティングシステムが提供するサービスに依存するソリューションが存在する。しかし、これらのサービスは、スケジューラを減速するかまたは実時間制約に準拠しないソフトウェアドライバの形式で実装されているため、複雑さが制限される。他のソリューションは再設定マネージャを使用するが、むしろ同種のマルチコアアーキテクチャに適している。最後に、アプリケーションをオフラインすなわち実行前に、その挙動を入力の動的特性に応じて解析するツールが存在する。これらは入力から、実行される処理動作の決定されたスケジューリング、従って適切なローディング順序を推論する。これらのソリューションは、実行に本質的に付随するランダム性を考慮しておらず、ランダム性は往々にして所定の静的なプリロード戦略を無効にする。解析の後、上で引用した従来技術が、再設定待ち時間を短縮またはマスキングする本質的に３種の基本技術を提案することは明らかである。これらの技術は、意思決定の静的または動的な態様とは互いに無関係である。第１の技術は、設定情報を表すビットストリームを圧縮および解凍するものである。実際、各設定に対して、設定を記述するビットストリームが対応し、ビットストリームは対応する設定をロードすべく転送されなければならない。第２の技術は、ビットストリームをキャッシュメモリにプリロードするものである。第３の技術は、対応ビットストリームをキャッシュメモリに保存することにより、既に実行された設定を再利用するものである。しかし、これらの技術はいずれも、真に重要な改良を行うものではなく、動的に再設定可能なアーキテクチャには依然として再設定待ち時間の弊害がある。
【０００６】
米国特許出願公開第２００４／０２６０８８４Ａ１号に、いくつかの再設定可能なプロセッサを含んでいて、プロセッサの１個が、共有メモリへのデータの読み書きを可能にする事前ローディング装置を備えた再設定可能なシステムが開示されている。しかし、この特許出願は、システム設定情報を表すビットストリームをプリチャージする方法を開示していない。
【発明の概要】
【課題を解決するための手段】
【０００７】
本発明の目的は特に、再設定待ち時間をマスキングすることにより、すなわち、計算コアが主処理動作を実行し続ける間に、将来の設定を先読みして準備することにより、動的に再設定可能なアーキテクチャの計算性能を向上させることである。従って、本発明は特に、設定ビットストリームを予測的な仕方でメモリにプリロードすることを提案する。このため、以下で本発明による装置を、「Ｐｒｅｄｉｃｔｉｖｅ  Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｍａｎａｇｅｒ」の頭文字「ＰＣＭ」で表記する場合がある。従って、本発明の主題は、複数の異なる種類の処理ユニットを含む再設定可能な情報処理システムの設定情報、すなわち所与のタスクの実行に適した処理ユニットの可能な論理的編成を記述している設定を表すビットストリームを階層化メモリにプリロードする方法である。本方法は、所与のタスクの実行に続いて所与の種類の処理ユニットで実行可能なタスクを決定する非実行ステップを含んでいる。本方法はまた、所与のタスクの実行中に、実行可能なタスクの各々について、所与のタスクの現在の実行に関する情報に依存する優先順位を計算するステップも含んでいる。本方法はまた、所与のタスクの実行中に、実行可能なタスクをそれらの優先順位に従いソートするステップも含んでいる。本方法はまた、所与のタスクの実行中に、優先順位が最高のタスクを優先させながら、実行可能なタスクの実行に有用な設定情報を表すビットストリームを階層化メモリにプリロードするステップも含んでいる。
【０００８】
好都合には、設定のプリローディングは、オペレーティングシステムによるメモリへのロード要求が発行された際に割り込みが発生し、前記ロード要求が最初に処理されて、プリローディング方法がシステムの動作を減速させないようにする。メモリは、階層化メモリであってよい。
【０００９】
例えば、各種の処理ユニットについて、所与のタスクの実行に続いて所与の種類の処理ユニットで実行可能なタスクを示す依存性グラフを生成することができる。
【００１０】
好都合には、依存性グラフは、所与のタスクの実行に続いて所与の種類の処理ユニットで実行可能なタスクの各々について、アプリケーションパッケージ処理を記述するグラフを用いて生成可能である。
【００１１】
例えば、実行可能なタスクの優先順位は、Ｎ個のパラメータｐｉ、ｉ∈｛１，．．，Ｎ｝（Ｎは非ゼロ整数）の重み付き和であってよく、和における各パラメータｐｉはｎｉ乗（ｎｉは非ゼロ整数）され、パラメータｐｉはオペレーティングシステムにより実行中に動的に与えられてよい。パラメータｐｉはまた、実行前に静的に与えられてもよい。
【００１２】
実行可能なタスクの優先順位は、オペレーティングシステムにより与えられる処理優先順位に依存する場合がある。優先順位はまた、所与の種類の処理ユニットの相対的な計算負荷に依存する場合がある。優先順位はまた、所与の種類の処理ユニットにおける平均実行時間に依存する場合がある。優先順位は、所与のタスクにおける条件分岐命令を実行する確率に依存する場合がある。
【００１３】
好都合には、設定はパラメータ化可能なサイズのビットのブロックとして階層化メモリにプリロードされていてよい。
【００１４】
本方法は、再設定可能なシステムがチップ上のシステムであって、ハードウェアモジュールの形式で実装されていてよい。ハードウェアモジュールはまた、キャッシュメモリを含んでいてよい。
【００１５】
本発明は、プリローディングの適宜な選択を可能にすることに加えて、本発明が生成する情報によりスケジューラと動的に協働して、計算コアに設定をロードするために必要な時間の正確な値を提供できるという主な利点がある。スケジューラは、この設定時間をタスクの実行時間に組み込むことができる。名目動作を実行する間、この値は理想的にはゼロのはずである。本発明によりスケジュールの計算に必要な全体の時間が長くならない点に注意されたい。更に、本発明の主な利点として、統一された設定インターフェースを提供することにより、および実行中にアーキテクチャで利用できる計算リソースへのタスクの割り当てを自身が行うことにより、スケジューラに対してアーキテクチャの異種性をマスキングすることが挙げられる。実行プログラムは従って、異種性について関知せず、本発明が計算コアの制御の一部を処理する。
【００１６】
本発明の他の特徴および利点は、添付図面に関する以下の説明から明らかになる。
【図面の簡単な説明】
【００１７】
【図１】本発明の装置により再設定待ち時間をマスキングできる例示的な異種再設定可能なアーキテクチャの説明図である。
【図２】本発明の装置による例示的な機能アーキテクチャの説明図である。
【図３】本発明の例示的な処理チェインの機能図である。
【図４】タスク依存性グラフによる、アプリケーションを設計する際のタスクの割り当て、および本発明に従い同種コアについて生成された設定依存性グラフの導出の原理を示す図である。
【図５】本発明による設定依存性グラフの表現を可能にする例示的なデータ構造を示す図である。
【図６】本発明による子タスクの表現を可能にする例示的なデータ構造を示す図である。
【図７】本発明による設定識別子の表現を可能にする例示的なデータ構造を示す図である。
【図８】本発明による設定記述子の表現を可能にする例示的なデータ構造を示す図である。
【図９】本発明によるメモリ索引ラインの表現を可能にする例示的なデータ構造を示す図である。
【発明を実施するための形態】
【００１８】
図１に、本発明が性能の向上をもたらすＳｏＣの典型的且つ例示的な編成をアーキテクチャ図で示す。本発明による装置は、ＰＣＭ要素１により表される。好都合には、本発明によるＰＣＭ要素１は、再設定可能なＳｏＣタイプのアーキテクチャに集積された再設定可能なタイプの回路のハードウェア要素であってよい。ＰＣＭ要素１は、オペレーティングシステムとのインターフェース２８を含んでいて、頭文字「ＯＳ」は「オペレーティングシステム」を表す。インターフェース２８の詳細を図３に示す。一組の計算コアが、一方ではデータ相互接続および実行制御ネットワーク５により、他方では設定バス６により相互接続されていてよい。入出力周辺機器１５がネットワーク５に接続されている。この相互接続スキームは、設定が単一の非専用相互接続ネットワークでも実行可能であるため、非限定的である。例えば、架橋１４が連続した相互接続になる場合である。計算コアの組は例えば、「Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｃｏｒｅ」の頭文字である「ＲＣ」と表記された再設定可能なコア２および３と共に、「Ｐｒｏｇｒａｍｍａｂｌｅ  Ｃｏｒｅ」の頭文字である「ＰＣ」と表記されたコア４等のプログラム可能な計算コアを含んでいる。このように構成されたアーキテクチャは異種である。設定の形式でコアＲＣ２およびＲＣ３をプログラムする形式は必ずしも互いに、または命令ストリームの形式でコアＰＣ４をプログラムする形式と互換性を有している訳ではない。図１の例示的な異種の動的に再設定可能なアーキテクチャは従って、固有のプログラムモデルを有していない。
【００１９】
主コントローラ７は、Ｎｉｃｏｌａｓ  Ｖｅｎｔｒｏｕｘ著「  Ｃｏｎｔｒｏｌｅ  ｅｎ  ｌｉｇｎｅ  ｄｅｓ  ｓｙｓｔｅｍｅｓ  ｍｕｌｔｉｐｒｏｃｅｓｓｅｕｒｓ  ｈｅｔｅｒｏｇｅｎｅｓ  ｅｍｂａｒｑｕｅｓ：  ｅｌａｂｏｒａｔｉｏｎ  ｅｔ  ｖａｌｉｄａｔｉｏｎ  ｄ’ｕｎｅ  ａｒｃｈｉｔｅｃｔｕｒｅ」（内蔵異種マルチプロセッサシステムのオンライン制御：アーキテクチャの考案および検証）に基づく「オンチップオペレーティングシステムアクセラレータ」タイプの専用要素の形式で、またはより従来型の方式として図１の例に示すプログラム可能マイクロプロセッサで実装できる。例えば、コントローラ７は実時間オペレーティングシステムを実行できる。変型実施形態において、本発明によるＰＣＭハードウェア要素１は、同じサービスを提供するソフトウェア要素で代替できる。次いでソフトウェア要素はコントローラ７上で、例えばオペレーティングシステムのドライバの形式で実行できる。専用の相互接続１３により、外部メモリのコントローラ９から、従って外部大容量メモリ８から設定をより高速に取得して、複数レベルの内蔵メモリを有する階層化メモリ１０へ転送できるようになる。メモリ１０の特定のレベルは、本発明によるＰＣＭ要素１の設定を管理するサービスに割り当てることができる。以下、メモリ１０のこれらのレベルを「ローカル設定メモリ」と呼ぶ。各計算コア２、３および４に対して、各メモリ１１、１２および１６は、このコア専用の設定キャッシュである。同種のコアが同一キャッシュを共有することも、あるいはいくつかの専用のキャッシュを有することもできる。外部メモリ、システムを構成するメモリ１０、キャッシュメモリ１１、１２および１６、並びに再設定可能なコアの構成設定メモリプレーンの組を一括して設定メモリ階層と呼ぶが、アーキテクチャ内ではこれらのレベル全てを表記する必要は無い。本発明によるＰＣＭ要素１は、設定階層化メモリの各種レベル間における設定を完全にまたは部分的に複製できる。取得した設定の管理を容易にすべく、サイズがパラメータ化可能で、数百ビットまたはバイトから数キロビットまたは数キロバイトまで変化し得る記憶ブロックに取得した設定を分割することができる。ＰＣＭ要素１は以下に述べる方法により、各種設定メモリ１０、１１、１２へのブロックの複製を制御できる。
【００２０】
上述のように、本発明によるＰＣＭ要素１により、設定ビットストリームを予測的にメモリにプリロードすることが可能になる。予測は特に、実行中に生成される動的な情報に依存する。例えばスケジューラの役割を果たすマイクロプロセッサ７により与えられる処理優先順位等、動的な情報を回路の他のコントローラにより伝達することができる。内蔵装置において、電池の残量は、そのような動的な情報の項目であり得る。マンマシンインターフェイスを介して入力された命令もまた、この動的な情報の一部を形成できる。ＰＣＭ要素１自体もまた、例えば各種のコアＲＣまたはＰＣの相対的な計算負荷、あるいは各種のコアＲＣまたはＰＣの平均実行時間等の動的な情報を生成できる。ＰＣＭ要素１はまた、「プロファイリング」ツールが提供する静的情報、特に条件分岐命令を実行する確率を動的に補完できる。ＰＣＭ要素１により生成またはで補完される動的な情報は、アーキテクチャを実行条件に関する自己適応の特性に合致させる。予測もまた、純然たる静的情報すなわち設定間の依存性に依存する。これらの依存性の認識はオプションとして、実行中の呼び出しのチェイニングから推論できる。従って、所与の設定をロードする必要がある場合、必然的に別の設定を続いてロードする必要があることが予測できる。呼び出しを予測することにより、適当な機会に設定を取得することにより実行命令に対するアーキテクチャの応答性を向上させることが可能になる。
【００２１】
図２に、各モジュールがサービスを提供する、本発明によるＰＣＭ要素１の例示的な内部機能アーキテクチャを示す。これは、コアＲＣ２、ＲＣ３およびＰＣ４により形成される計算コアの異種の組にタスクを割り当てるモジュール２０を含んでいてよい。各々の計算コアＲＣ２、ＲＣ３およびＰＣ４は従って、「Ｔａｒｇｅｔ＿１（ターゲット１）」〜「Ｔａｒｇｅｔ＿Ｎ（ターゲットＮ）」と表記された潜在的ターゲットを構成することができる。ＰＣＭ要素１が提供する特定のサービスはターゲットコアに依存し、他は依存しない。ターゲットコアに依存するサービスに関して、ＰＣＭ要素１は、設定を格納する設定キャッシュメモリ２６、設定をプリロードするモジュール２１、設定をキャッシュメモリに配置するモジュール２２、プリエンプションモジュール２４、マイグレーションモジュール２５、およびビットストリームを圧縮および解凍するモジュール２３を含んでいてよい。ターゲットコアに依存するサービスに関して、ＰＣＭ要素１は、ビットストリームを操作して、特に２個のターゲット「Ｔａｒｇｅｔ＿１（ターゲット１）」および「Ｔａｒｇｅｔ＿２（ターゲット２）」のビットストリームの構成と共に、あるターゲットから別のターゲットへのインプリントの変換を可能にするモジュール２７を含んでいてよい。設定キャッシュメモリ２６が、考慮するターゲットコアに依存するサービスと全く同様にＰＣＭ要素１の外部で、計算コアのなるべく近い場所で離れた箇所に配置されていてよい点に注意されたい。ＰＣＭ要素１はまた、リソースの状態に関する情報、ＯＳが利用できる情報を含むモジュール２９、および各計算コアをロードするプロトコルの仕様を管理するモジュール３６を含んでいる。
【００２２】
図３に、本発明によるＰＣＭ要素１により実装される例示的な処理チェインを示す。このチェインにより、実行中に、オペレーティングシステムが提供する動的な情報をアプリケーションの設計に起因する静的な情報と組み合わせることが可能になる。インターフェース２８は特に、モジュール２０、２１および２２がオペレーティングシステムから「スレッド優先順位」ストリームで表される処理優先順位、「必須／至急」ストリームで表される必須または至急なロード要求、「休止／終了」ストリームで表されるタスク実行休止または終了要求等の動的な情報の受け取りを可能にする。また、モジュール２０、２１および２２は純然たる静的情報、すなわちアプリケーションパッケージ記述グラフを用いることができる。これは、設定の依存性グラフであってよく、グラフは一般に「Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｄｅｐｅｎｄｅｎｃｙ  Ｇｒａｐｈ」の頭文字「ＣＤＧ」で表記される。同様に、モジュール２０、２１および２２はまた、一般に「Ｃｏｎｔｒｏｌ  Ｄａｔａ  Ｆｌｏｗ  Ｇｒａｐｈ」の頭文字「ＣＤＦＧ」で表記される制御およびデータ依存性グラフを用いることができる。これらのグラフにより、例えばオプションとしての１個以上の異種なターゲットにおける１個以上のハードウェア実装により計算タスクを実行するより高速な方法を決定することが可能になる。開発者が提供する各グラフ、および各種類のターゲットについて、「Ｔｉｌｅ−ｄｅｐｅｎｄａｎｔ  ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｄｅｐｅｎｄｅｎｃｙ  ｇｒａｐｈ」の頭文字に従い「ＴＣＤＧ」と呼ばれるグラフを好都合には導出できる。ＴＣＤＧの形式は本発明に固有のものである。ＴＣＤＧの構築については、図４〜９を参照しながら以下に詳述する。次いで、本発明によりＴＣＤＧをどのように用いるかを詳述するために再び図３を考察する。
【００２３】
図４に、タスク依存性グラフにより、一方ではアプリケーションを設計する際に開発者により実行されるタスク割り当ての原理を示し、他方では本発明による２個の設定依存性グラフの導出を示す。アプリケーションの開発者が前記アプリケーションの各々の処理、またはアプリケーションを構成する単一処理について提供するＣＣＧまたはＣＤＦＧタイプのタスク依存性グラフ４２に基づいて、２個のＴＣＤＧ４０、４１を導出することができる。１個または複数のアプリケーションを記述すべく提供されたＣＤＧまたはＣＤＦＧの各々について、ターゲット化されたアーキテクチャに存在する各種の再設定可能またはプログラム可能なコアが異なるＴＣＤＧの生成を引き起こす。グラフ４２において、黒い丸で示すタスクは第１の種類のターゲットに対して好適に実行され、山形のパターンが付けられたタスクは第２の種類のターゲットに対して好適に実行されるはずである。従来のＣＣＧまたはＣＤＦＧ形式にはタスクタイピングは存在しない。本発明は、アプリケーションの開発者によりなされる実装上の選択に関する完全な知識により、グラフ４２にこのタイピングを加えることを提案する。実際、いくつかの全く同一のソフトウェアタスクの実装が可能な場合、開発者はターゲットの種類の選択に優先順位を与えることができる。ＴＣＤＧ４０、４１は、第１の種類および第２の種類のターゲットに対して実行可能なタスクに対応する。
【００２４】
図５に、本発明によるＴＣＤＧ４０の表現を可能にする例示的なデータ構造を示す。ビットの数で表すフィールドサイズは単に例として与えるものであって、実装毎に異なっていてよい。ＴＣＤＧ４０は、ターゲット識別子を含むフィールド「ＩＰ＿ｉｄ」および処理識別子を含む「Ｔｈｒｅａｄ＿ｉｄ」フィールドにより一意に定義できる。ＴＣＤＧ４０はまた、多くのハードウェアタスクを含む「カウント」フィールドおよびノード間のリンクを記述する依存性マトリクスを含む「ｄｅｐｅｎｄｅｎｃｙ＿ｍａｔｒｉｘ（依存性マトリクス）」フィールドを含んでいてよい。ＴＣＤＧ４０はまた、アプリケーションの開発に利用可能なあらゆる静的情報を含む「ｉｎｆｏ＿ｓｔａｔｉｃ（静的情報）」フィールドを含んでいてよい。図５の例において、ＴＣＤＧ４０の全てのノードが「ｉｎｆｏ＿ｓｔａｔｉｃ（静的情報）」フィールドを含んでいる。「ｉｎｆｏ＿ｓｔａｔｉｃ（静的情報）」フィールド自体は、図５の例に示すようにいくつかのフィールドを含んでいてよい。特に、「プロファイリング」ツールにより与えられる実行の確率を含む「ｅｘｅｃ＿ｐｒｏｂ（実行確率）」フィールドを含んでいてよい。また、元のグラフに存在するノードの数を表す深さを含む「深さ」フィールドを含んでいて、ＴＣＤＧの２個ノードの間で単純化することができる。「深さ」フィールドにより、ＴＣＤＧの２個の分岐のうちどちらが最初に実行される可能性が大きいかを判別することが可能になる。また、ソフトウェアタスク識別子を含む「ｏｐｅｒａｔｉｏｎ＿ｉｄ（動作ｉｄ）」フィールドを含んでいてよい。これは、呼び出し識別子を含む「ｉｎｖｏｃａｔｉｏｎ＿ｉｄ（起動ｉｄ）」フィールドを含んでいて、グラフ内で全く同一のタスクが複数回出現することができる。これは、上述のように、全く同一のソフトウェアタスクが複数回実現される場合の選択の優先順位を含む「ｃｈｏｉｃｅ＿ｐｒｉｏ（選択優先順位）」フィールドを含んでいてよい。最後に、ループ信号を含む「ｌｏｏｐ＿ｆｌａｇ（ループフラグ）」フィールドを含んでいてよく、ループを実行する間にキャッシュメモリ２６内のビットストリームを維持するために用いられる。本発明によるＰＣＭ要素１は、タスクの実行中に、次にターゲットに呼ばれそうな子タスクを求めてＴＣＤＧ４０を探索する。従って、「ｉｎｆｏ＿ｓｔａｔｉｃ（静的情報）」フィールドの情報は、図６に示すデータ構造に複製される。
【００２５】
図６に、子タスクの表現を可能にする例示的なデータ構造を示す。ビットの数で表すフィールドサイズは単に例として与えるものであって、実装毎に異なっていてよい。この子タスク構造は、図７において詳述される設定識別子を含む「ＩＤ＿ｃｏｎｆｉｇ（ＩＤ設定）」フィールドを含んでいてよい。図７は、設定識別子の表現を可能にする例示的なデータ構造を示す。従って、「ＩＤ＿ｃｏｎｆｉｇ（ＩＤ設定）」フィールド自体が、処理番号を含む「スレッド」フィールド、ソフトウェアタスク識別子を含む「動作」フィールド、ＴＣＤＧ４０の呼び出し番号を含む「起動」フィールド、設定ファイル識別子を含む「ｂｉｔｓｔｒｅａｍ＿ｉｄ（ビットストリームｉｄ）」フィールド、およびハードウェアターゲットを含む「ＩＰ」フィールドを含んでいる。ビットストリームは必然的に所与のターゲット関連付けられているため、「ｂｉｔｓｔｒｅａｍ＿ｉｄ（ビットストリームｉｄ）」および「ＩＰ」フィールドが冗長である点に注意されたい。図６の子タスク構造はまた、正当性のブーリアンを含む「関連有り」フィールドおよびループ信号を含む「ｌｏｏｐ＿ｆｌａｇ（ループフラグ）」フィールドを含んでいてよい。これはまた、「ｉｎｆｏ＿ｓｔａｔｉｃ（静的情報）」フィールドの上述の情報を全て含んでいる。これは、ゼロに向かう動的な深さを含む「深さ」フィールドを含んでいてよい。これは、オペレーティングシステムが提供する処理優先順位を含む「ｔｈｒｅａｄ＿ｐｒｉｏ（スレッド優先順位）」フィールドを含んでいてよい。子タスク構造はまた、関連付けられた設定ファイルのブロックの数で表すサイズを含む「ｃｏｎｆｉｇ＿ｓｉｚｅ（設定サイズ）」フィールドを含んでいてよい。これは、動的に決定された宛先メモリを含む「宛先」フィールドを含んでいてよい。これは、複製される多数のブロックを含む「ｔｒａｎｓｆｅｒ＿ｍｏｄｅ（転送モード）」フィールドを含んでいてよく、この数は動的に決定される。これは、本発明により動的な情報および静的な情報に基づいて計算される動的な優先順位を含んでいる。図６の例において、この動的な優先順位は「ｄｙｎａｍｉｃ＿ｐｒｉｏ（動的優先順位）」フィールドに含まれている。多くの方法により、動的な優先順位を計算することが可能になる。例えば、動的な優先順位Ｐｄは、Ｎ個のパラメータｐｉ、ｉ∈｛１，．．．，Ｎ｝（Ｎは非ゼロ整数）重み付き和であってよく、和に含まれる各パラメータｐｉはｎｉ乗（ｎｉは非ゼロ整数）される。
【数１】
2011511377.tif 000003
【００２６】
特定のパラメータｐｉの値は、オペレーティングシステムにより実行中に動的に与えられてよく、他のパラメータｐｉの値は実行前に静的に与えられてもよい。パラメータｐｉおよび加重係数ａｉの各種の可能な選択肢は、宛先メモリの選択および複製されるブロックの数を誘導する各種の可能な方針を構成する。従って、本発明によるＰＣＭ要素１は、多数の特定のケースのアプリケーションに適合させることができる。所与の時点で識別される子タスクの全ての構造を例えば降順にソートすべく動的な優先順位の値が計算される。先頭に「ｏｒｄｅｒ＿ｎｅｘｔ（次の順序）」が付与された３個のフィールドが、ソート後に子タスクの構造をチェイニングする役割を果たし、「ｏｒｄｅｒ＿ｎｅｘｔ−>ｐｏｓｉｔｉｏｎ（位置）」および「ｏｒｄｅｒ＿ｎｅｘｔ−>ＩＰ」フィールドにより、次のノードを一意に識別することを可能にする。「ｏｒｄｅｒ＿ｎｅｘｔ−>ｅｎｄ＿ｆｌａｇ（最終フラグ）」フィールドは、最後のノードに到達した旨を通知することができる。本発明によるＰＣＭ要素１は、子タスクの構造のソートされたリストを読んで、チェイニングの順序でブロックを複製することができる。一方で、利用可能なメモリがまだ残っている限り、且つ他方で、メモリへのロードを行う新たな命令がオペレーティングシステムのスケジューラから送られていない限り、ブロックを複製することができる。新たなロード命令がスケジューラから与えられたならば、高い優先順位で処理することができる。続いて、子タスクの識別およびそれらのソーティングを再開することができる。
【００２７】
図３に示すように、オペレーティングシステムとの結合により、本発明によるＰＣＭ要素１は２種の動作モードを有することができる。実際、本発明の予測チェインは、起動されても、または起動されなくてもよい。予測チェインが起動されない場合、オペレーティングシステムは処理動作のローディングおよび実行をスケジュールする役割を担う。この場合、本発明によるＰＣＭ要素はオペレーティングシステムにより駆動され、リソースをローディングおよび解放する命令を送信する。予測チェインが起動されたならば、本発明によるＰＣＭ要素は、自身はプリロードのスケジューリングを行いながら、オペレーティングシステムにより送られた命令に応じて処理動作の実行を追跡する。
【００２８】
図８に、設定記述子の表現を可能にする例示的なデータ構造を示す。ビットの数で表すフィールドサイズは単に例として与えるものであって、実装毎に異なっていてよい。ビットのストリームに変換された際にビットストリームを形成できるのはこの設定記述である。本発明によるＰＣＭ要素１によりビットストリームのコピーが決定された場合、これがオペレーティングシステムの直接命令に続くものであるか、またはその予測に指示されてプリロードを実行するかによらず、ＰＣＭ要素１はこの設定記述子構造をメモリに確保できる。そのような構造は、構造の有効性のブーリアンを含む「ｒｅｌ」フィールドを含んでいてよい。これはまた、「ｏｒ」分岐または例えば並列実行の場合に、ビットストリーム同士が排他的であるかを通知するブーリアンを含む「ｃｈ」フィールドを含んでいてよい。これは、オプションの並列記述子へのポインタを含む「並列分岐」フィールドを含んでいてよい。これは、記述子の経年を表すと共に使用していない構造のクリーニングを許す整数を含む「経年」フィールドを含んでいてよい。これは、設定状態を表す、すなわち、設定が部分的に取得されたかまたは実行の準備ができているか否かを示す整数を含む「ｃｏｎｆｉｇ＿ｓｔａｔｕｓ（設定状態）」フィールドを含んでいてよい。これは、各々がビットストリームおよびターゲットを識別する整数を含む「ｂｉｔｓｔｒｅａｍ＿ｉｄ（ビットストリームｉｄ）」および「ＩＰ」フィールドを含んでいてよい。これは、ターゲットにロードされたブロックの数を特徴付ける整数を含む「ｂｌｏｃｋｓ＿ｏｎ＿ＩＰ（ＩＰブロック数）」フィールドを含んでいてよい。これは、キャッシュメモリに存在するブロックの数を特徴付ける整数を含む「ｂｌｏｃｋｓ＿ｉｎ＿ｃａｃｈｅ（キャッシュブロック数）」フィールドを含んでいてよい。これは、ローカルメモリに存在するブロックの数を特徴付ける整数を含む「ｂｌｏｃｋｓ＿ｉｎ＿ｌｏｃａｌ（ローカルブロック数）」フィールドを含んでいてよい。これは、既に取得されたブロックの総数を特徴付け、上で述べた３個のフィールドの合計である整数を含む「ｔｏｔａｌ＿ｂｌｏｃｋｓ（ブロック総数）」フィールドを含んでいてよい。これはまた、各々がキャッシュメモリおよびローカルメモリ内での第１のブロックのアドレスを表す整数を含む「ｂｅｇｉｎ＿ａｄｒｅｓｓ＿ｃａｃｈｅ（キャッシュアドレス開始）」および「ｂｅｇｉｎ＿ａｄｒｅｓｓ＿ｌｏｃａｌ（ローカルアドレス開始）」フィールドを含んでいてよい。「ｅｎｄ＿ａｄｒｅｓｓ＿ｃａｃｈｅ（キャッシュアドレス終了）」フィールドおよび「ｅｎｄ＿ａｄｒｅｓｓ＿ｌｏｃａｌ（ローカルアドレス終了）」フィールドは各々、キャッシュメモリおよびローカルメモリ内の最後のブロックのアドレスを表す整数を含んでいてよい。「ｂｅｇｉｎ＿ｂｌｏｃｋ＿ｃａｃｈｅ（キャッシュブロック開始）」フィールドおよび「ｂｅｇｉｎ＿ｂｌｏｃｋ＿ｌｏｃａｌ（ローカルブロック開始）」フィールドは各々、キャッシュメモリおよびローカルメモリ内の第１のブロックの数を表す整数を含んでいてよい。「ｅｎｄ＿ｂｌｏｃｋ＿ｃａｃｈｅ（キャッシュブロック終了）」フィールドおよび「ｅｎｄ＿ｂｌｏｃｋ＿ｌｏｃａｌ（ローカルブロック終了）」フィールドは各々、キャッシュメモリおよびローカルメモリ内の最後のブロックの数を表す整数を含んでいてよい。メモリにロードされたブロックは連続チェインを形成するが、非隣接的に配置されている点に注意されたい。
【００２９】
図９に、メモリ索引ラインの表現を可能にする例示的なデータ構造を示す。ビットの数で表すフィールドサイズは単に例として与えるものであって、実装毎に異なっていてよい。実際、ブロックの復旧を容易にし、且つ設定記述子を更新するために、各種のメモリの索引付けされた内容を表すデータ構造を用いる。そのような構造は、有効性のブーリアンを含む「ビジー」フィールドを含んでいてよい。これはまた、ブロックの保護を通知するブーリアンを含む「保護」フィールドを含んでいてよい。このフィールドは、ブロックがその一部をなす設定を保護する役割を果たす。メモリ索引ライン構造はまた、ブロックのチェインの終了を通知するブーリアンを含む「ｌａｓｔ＿ｂｌｏｃｋ（最終ブロック）」フィールドを含んでいてよい。これはまた、終了が設定の終了に一致するか否かを通知するブーリアンを含む「ｅｎｄ＿ｏｆ＿ｃｏｎｆｉｇ（設定の終了）」フィールドを含んでいてよい。これはまた、現在のブロックがチェインの終端にない場合に次のブロックへのポインタを含む「ｎｅｘｔ＿ｂｌｏｃｋ（次ブロック）」フィールドを含んでいてよい。これは、ビットストリームを識別する整数を含む「ｂｉｔｓｔｒｅａｍ＿ｉｄ（ビットストリームｉｄ）」フィールドを含んでいてよい。最後に、ブロック番号を表し、ビットストリーム内におけるブロックの位置を識別可能にする整数を含む「ｂｌｏｃｋ＿ｎｂｒ（ブロック番号）」フィールドを含んでいてよい。メモリに存在する各ブロックに対して、図９に示すような索引ライン構造をメモリに生成することができる。
【００３０】
図３に示すように、一連の処理動作は、インターフェース２８を介してオペレーティングシステムにより送られた命令を受信したならば直ちに開始される。
【００３１】
ロード要求を受信したならば、ビットストリームを「ｓｔａｔｕｓ＿ｕｐｄａｔｅ（状態更新）」機能３１へ転送できる「ｂｉｔｓｔｒｅａｍ＿ｔｒａｎｓｆｅｒｓ（ビットストリーム転送）」機能３０により、設定ファイルの欠落のブロックを直接ロードすることができる。これらのビットストリームに基づいて、「ｓｔａｔｕｓ＿ｕｐｄａｔｅ（状態更新）」機能３１は図８に示す、設定記述子を表すデータ構造を更新することができる。
【００３２】
予測チェインは、本発明のプリロードを実行すべく並行して起動できる。最初に、「ａｃｔｉｖｅ＿ｗｉｎｄｏｗ＿ｓｅｌｅｃｔｉｏｎ（アクティブウインドウ選択）」機能３２は、上述のように構築されているＴＣＤＧ４０、４１を使用することができる。これらのＴＣＤＧにより、実行される可能性が高いハードウェアタスクを推論することが可能になる。「ａｃｔｉｖｅ＿ｗｉｎｄｏｗ＿ｓｅｌｅｃｔｉｏｎ（アクティブウインドウ選択）」機能３２は、図６に示す子タスク構造にこれらのタスクを取り込むことができる。次いで、「ｃｏｎｆｉｇｕｒａｔｉｏｎ＿ｐｒｉｏｒｉｔｙ＿ｃｏｍｐｕｔａｔｉｏｎ（設定優先順位計算）」機能３３により、選択されたタスクの動的な優先順位を計算することができる。その後で、選択されたタスクを「ｐｒｉｏｒｉｔｙ＿ｓｏｒｔｉｎｇ（優先順位ソート）」機能３４により、例えばそれらの動的な優先順位の降順にソートすることができる。最後に、「ｈｉｅｒａｒｃｈｉｃａｌ＿ｌｅｖｅｌ＿ｃｈｏｉｃｅ（階層レベル選択）」機能３５は、取得するのに最適なブロックの位置をメモリ内で利用できる空き容量に応じて選択する。好都合には、本発明によるプリローディングは、「ｂｉｔｓｔｒｅａｍ＿ｔｒａｎｓｆｅｒｓ（ビットストリーム転送）」転送機能３０および「ｓｔａｔｕｓ＿ｕｐｄａｔｅ（状態更新）」更新機能３１が利用可能な場合、すなわちオペレーティングシステムから直接に発行されたロード要求を処理しない場合にのみ、実行可能である。従って、本発明は、たとえ自身の予測が間違っていても、オペレーティングシステムが命じたロードを遅くすることは絶対にない。
【図１】
2011511377.tif 000004
【図２】
2011511377.tif 000005
【図３】
2011511377.tif 000006
【図４】
2011511377.tif 000007
【図５】
2011511377.tif 000008
【図６】
2011511377.tif 000009
【図７】
2011511377.tif 000010
【図８】
2011511377.tif 000011
【図９】
2011511377.tif 000012
【国際調査報告】
2011511377.tif 000013
2011511377.tif 000014
2011511377.tif 000015
2011511377.tif 000016
2011511377.tif 000017
2011511377.tif 000018