(57)【要約】  複数の装置および複数の方法は、動的コンパイラによって、１または複数のループを処理するためのパフォーマンスレベルを判断すること、および１または複数のループのために、既定の時間内に判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行することを提供する。一例において、依存関係グラフが１または複数のループのために確立されてよく、各依存関係グラフは、パフォーマンスレベルに基づき、複数のステージにパーティション化されてよい。
2016515735.tif 000002
【特許請求の範囲】
【請求項１】
動的コンパイラによって、１または複数のループを処理するためのパフォーマンスレベルを判断するための第１のモジュールと、
前記１または複数のループのために、既定の時間内に前記判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行するための第２のモジュールと、を備える、パイプラインを実行する装置。
【請求項２】
前記１または複数のループのための依存関係グラフを確立し、前記パフォーマンスレベルに基づき、各依存関係グラフを複数のステージにパーティション化するための第３のモジュールをさらに備える、請求項１に記載の装置。
【請求項３】
調整されたローカルスケジュールが、前記パフォーマンスレベルを達成するかどうか判断するための第４のモジュールと、
前記調整されたローカルスケジュールが、前記パフォーマンスレベルを達成しない場合に前記既定の時間が発生したかどうか判断するための第５のモジュールと、をさらに備える、請求項１または２に記載の装置。
【請求項４】
前記パフォーマンスレベルは、最小開始間隔（ＭＩＩ）を計算することによって判断される、請求項１から３のいずれか一項に記載の装置。
【請求項５】
実行された前記複数のコードの最適化は、複数のハードウェアリソースを割り当てること、およびローカルスケジュールを生成すべく、各パーティション化されたステージ内に含まれる複数の命令のための複数のローカルの依存関係を解決すること、を含む、請求項１から４のいずれか一項に記載の装置。
【請求項６】
実行された前記複数のコードの最適化は、複数のループ伝搬依存性を解決すべく、ローカルスケジュールを調整することを含み、調整された前記ローカルスケジュールを作成する、請求項１から５のいずれか一項に記載の装置。
【請求項７】
実行された前記複数のコードの最適化は、調整されたローカルスケジュールが前記パフォーマンスレベルを達成せず、前記既定の時間が発生しない場合、次の反復スケジュールを生成すべく、複数の命令を、それらの現在のステージから次のステージへ移動することを含む、請求項１から６のいずれか一項に記載の装置。
【請求項８】
実行された前記複数のコードの最適化は、次の反復スケジュールを使用して新しい調整されたローカルスケジュールを生成すべく、前記既定の時間が発生しない限り、前記調整されたローカルスケジュールが前記パフォーマンスレベルを達成するまで、反復される、請求項1から７のいずれか一項に記載の装置。
【請求項９】
コンピューティングデバイス上での実行時、前記コンピューティングデバイスを構成して、
動的コンパイラによって、１または複数のループを処理するためのパフォーマンスレベルを判断する手順と、
前記１または複数のループのために、既定の時間内に前記判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行する手順と、を実行させるための、少なくとも１つのコンピュータプログラム。
【請求項１０】
前記コンピューティングデバイス上での実行時、前記コンピューティングデバイスを構成して、
前記１または複数のループのための依存関係グラフを確立する手順と、
前記パフォーマンスレベルに基づき、各依存関係グラフを複数のステージにパーティション化する手順と、をさらに実行させるための、請求項９に記載の少なくとも１つのコンピュータプログラム。
【請求項１１】
前記コンピューティングデバイス上での実行時、前記コンピューティングデバイスを構成して、
調整されたローカルスケジュールが、前記パフォーマンスレベルを達成するかどうか判断する手順と、
前記調整されたローカルスケジュールが、前記パフォーマンスレベルを達成しない場合、前記既定の時間が発生したかどうか判断する手順と、をさらに実行させるための、請求項９または１０に記載の少なくとも１つのコンピュータプログラム。
【請求項１２】
前記パフォーマンスレベルは、最小開始間隔（ＭＩＩ）を計算することによって判断される、請求項９から１１のいずれか一項に記載の少なくとも１つのコンピュータプログラム。
【請求項１３】
実行された前記複数のコードの最適化は、複数のハードウェアリソースを割り当てること、およびローカルスケジュールを生成すべく、各パーティション化されたステージ内に含まれる複数の命令のための複数のローカルの依存関係を解決すること、を含む、請求項９から１２のいずれか一項に記載の少なくとも１つのコンピュータプログラム。
【請求項１４】
実行された前記複数のコードの最適化は、複数のループ伝搬依存性を解決すべく、ローカルスケジュールを調整することを含み、調整された前記ローカルスケジュールを作成する、請求項９から１３のいずれか一項に記載の少なくとも１つのコンピュータプログラム。
【請求項１５】
実行された前記複数のコードの最適化は、調整されたローカルスケジュールが前記パフォーマンスレベルを達成せず、前記既定の時間が発生しない場合、次の反復スケジュールを生成すべく、複数の命令を、それらの現在のステージから次のステージへ移動することを含む、請求項９から１４のいずれか一項に記載の少なくとも１つのコンピュータプログラム。
【請求項１６】
実行された前記複数のコードの最適化は、次の反復スケジュールを使用して新しい調整されたローカルスケジュールを生成すべく、前記既定の時間が発生しない限り、前記調整されたローカルスケジュールが前記パフォーマンスレベルを達成するまで、反復される、請求項９から１５のいずれか一項に記載の少なくとも１つのコンピュータプログラム。
【請求項１７】
動的コンパイラによって、１または複数のループを処理するためのパフォーマンスレベルを判断する段階と、
前記１または複数のループのために、既定の時間内に前記判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行する段階と、を備える、パイプラインを実行する方法。
【請求項１８】
前記１または複数のループのための依存関係グラフを確立する段階と、
前記パフォーマンスレベルに基づき、各依存関係グラフを複数のステージにパーティション化する段階と、をさらに備える、請求項１７に記載の方法。
【請求項１９】
調整されたローカルスケジュールが、前記パフォーマンスレベルを達成するかどうか判断する段階と、
前記調整されたローカルスケジュールが、前記パフォーマンスレベルを達成しない場合、前記既定の時間が発生したかどうか判断する段階と、をさらに備える、請求項１７または１８に記載の方法。
【請求項２０】
前記パフォーマンスレベルは、最小開始間隔（ＭＩＩ）を計算することによって判断される、請求項１７から１９のいずれか一項に記載の方法。
【請求項２１】
実行された前記複数のコードの最適化は、複数のハードウェアリソースを割り当てること、およびローカルスケジュールを生成すべく、各パーティション化されたステージ内に含まれる複数の命令のための複数のローカルの依存関係を解決すること、を含む、請求項１７から２０のいずれか一項に記載の方法。
【請求項２２】
実行された前記複数のコードの最適化は、複数のループ伝搬依存性を解決すべく、ローカルスケジュールを調整することを含み、前記調整されたローカルスケジュールを作成する、請求項１７から２１のいずれか一項に記載の方法。
【請求項２３】
実行された前記複数のコードの最適化は、調整されたローカルスケジュールが前記パフォーマンスレベルを達成せず、前記既定の時間が発生しない場合、次の反復スケジュールを生成すべく、複数の命令を、それらの現在のステージから次のステージへ移動することを含む、請求項１７から２２のいずれか一項に記載の方法。
【請求項２４】
実行された前記複数のコードの最適化は、次の反復スケジュールを使用して新しい調整されたローカルスケジュールを生成すべく、前記既定の時間が発生しない限り、前記調整されたローカルスケジュールが前記パフォーマンスレベルを達成するまで、反復される、請求項１７から２３のいずれか一項に記載の方法。
【請求項２５】
動的コンパイラによって、１または複数のループを処理するためのパフォーマンスレベルを判断するための手段と、
前記１または複数のループのために、既定の時間内に前記判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行するための手段と、を備える、パイプラインを実行する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に記載の複数の実施形態は概してソフトウェアパイプラインに関し、より具体的には、複数の動的コンパイラにおけるソフトウェアパイプラインの実行に関する。
【背景技術】
【０００２】
ソフトウェアパイプラインは、複数のループからの命令レベルの並列処理を採用する効率的なコンパイラ技術である。従来のソフトウェアパイプラインは、複数の静的コンパイラにおける展開に限定される可能性があるが、従来のソフトウェアパイプラインは、ハードウェア／ソフトウェアコデザイン、複数の動的言語、クラウドコンピューティング、および複数の組み込みシステムに関与するもののような、複数の動的コンパイルアクティビティには好適ではない場合がある。
【０００３】
本発明の複数の実施形態に係る様々な利点は、以下の明細書および添付の特許請求の範囲を読み、以下の複数の図面を参照することで、当業者にとって明らかになるであろう。
【図面の簡単な説明】
【０００４】
【図１】一実施形態による装置の例のブロック図である。
【図２Ａ】複数の方法の複数の実施形態による例のフローチャートである。
【図２Ｂ】複数の方法の複数の実施形態による例のフローチャートである。
【図３Ａ】一実施形態による、シナリオの説明図である。
【図３Ｂ】一実施形態による、シナリオの説明図である。
【図３Ｃ】一実施形態による、シナリオの説明図である。
【図３Ｄ】一実施形態による、シナリオの説明図である。
【図３Ｅ】一実施形態による、シナリオの説明図である。
【図４】一実施形態による、システムの例のブロック図である。
【図５】一実施形態による、プロセッサの例のブロック図である。
【発明を実施するための形態】
【０００５】
図１を参照すると、複数の動的コンパイラのためのソフトウェアパイプラインを実行するための装置２１が示されている。示される装置２１は、第１のモジュール２２、第２のモジュール２３、第３のモジュール２４、第４のモジュール２５、および第５のモジュール２６を含む。第１のモジュール２２は、動的コンパイラによる１または複数のループを処理するためのパフォーマンスレベルを判断してよく、パフォーマンスレベルは、最小開始間隔（ＭＩＩ）を計算することによって判断される。第２のモジュール２３は、１または複数のループのための、既定の時間内で判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行してよく、複数の実行されるコードの最適化は、複数のハードウェアリソースの割り当て、およびローカルスケジュールを生成すべく、各パーティション化されたステージ内に含まれる複数の命令のための複数のローカルの依存関係を判断することを含む。
【０００６】
または、複数の実行されるコードの最適化は、複数のループ伝搬依存性を解決すべくローカルスケジュールを調整して、調整されたローカルスケジュールを作成すること、および、調整されたローカルスケジュールがパフォーマンスレベルを達成せず、既定の時間が発生しなかった場合、次の反復スケジュールを生成すべく、複数の命令を、それらの現在のステージから次のステージへ移動することを含んでよい。次の反復スケジュールを使用して、新しい調整されたローカルスケジュールを生成すべく、既定の時間が発生しない限り、調整されたローカルスケジュールがパフォーマンスレベルに達成するまで、複数の実行されるコードの最適化は、反復されてよい。
【０００７】
第３のモジュール２４は、１または複数のループのための依存関係グラフを確立し、パフォーマンスレベルに基づき、各依存関係グラフを複数のステージにパーティション化してよい。第４のモジュール２５は、調整されたローカルスケジュールがパフォーマンスレベルを達成するかどうかを判断してよく、第５のモジュール２６は、調整されたローカルスケジュールがパフォーマンスレベルを達成しない場合、既定の時間が発生したかどうかを判断してよい。示される装置２１は従って、ハードウェア／ソフトウェアコデザイン、複数の動的言語、クラウドコンピューティング、および複数の組み込みシステムに関与するもののような、複数の動的コンパイルアクティビティのためのコードの最適化に有用であり得る。
【０００８】
図２Ａは、複数の動的コンパイラのための、ランタイム時における、ソフトウェアパイプラインを実行する方法を示す。示される方法は、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、プログラマブルＲＯＭ（ＰＲＯＭ）、フラッシュメモリ等の、機械またはコンピュータ可読媒体、例えばプログラマブルロジックアレイ（ＰＬＡ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、複合プログラマブル論理デバイス（ＣＰＬＤ）等の構成可能なロジック、例えば、特定用途向け集積回路（ＡＳＩＣ）、相補型金属酸化物半導体（ＣＭＯＳ）、トランジスタ−トランジスタ論理（ＴＴＬ）技術等のアセンブリ言語プログラミングおよび回路技術を用いた固定機能性ハードウェア、またはこれらの任意の組み合わせに格納された、一連の論理命令および／またはファームウェアとして実装されてよい。例えば、例示方法に示される複数の動作を実行するコンピュータプログラムコードは、Ｃ＋＋または同様のもののようなオブジェクト指向のプログラミング言語、および「Ｃ」プログラミング言語または同様の複数のプログラミング言語のような、従来の複数の手続き型プログラミング言語を含む、１または複数のプログラミング言語の任意の組み合わせで記述され得る。さらに、方法は、複数の前述の回路技術の任意のものを使用して実装されてよい。
【０００９】
方法は概して、依存関係または複数のリソース制約のいずれも違反せずに、複数のループの反復の実行を重複することによって、複数のソフトウェアパイプラインの最適化を実行してよい。示される方法は、処理ブロック１１において、最小開始間隔（ＭＩＩ）を計算することによって、開始する。最小開始間隔は、ループの反復の開始と、次のループの反復の開始との間の、最短の時間であってよい。一例において、開始間隔が短いほど、ループプロセスを完了するのに要求されるサイクル数の数が小さくなり、ソフトウェアパイプラインを使用して、ループプロセスがより迅速に実行され得る。または、ＭＩＩを計算することの副産物として、複数の重大な動作が識別され、後のスケジューリング中に優先度が付与され得る。
【００１０】
特定のループ、例えば、図３Ａに示されるループについて、依存関係グラフが確立される。依存関係グラフは、例えば、図３Ｂに示される。グラフには、２つのループ伝搬依存性のエッジ、ｄ→ｂおよびｂ→ａが示されており、それぞれ反復距離値（１）を有する。依存関係のエッジｃ→ｄは、２つのサイクルのレイテンシを有する。複数の他の依存関係はローカルであり、従って、それらは反復距離値（０）を有する。依存関係グラフから、例えば、タルジャンの強連結コンポーネントアルゴリズムのような、アルゴリズムを使用して、複数の強連結成分（ＳＣＣ）が識別され得る。
【００１１】
最小開始間隔は、例えば、ハワードイテレーションポリシーアルゴリズムのような、アルゴリズム内で識別されたＳＣＣを使用して計算され得、それは次のように実装され得る。
【００１２】
MIICalculation(H)、ここで、Ｈは、ハワードイテレーションポリシーアルゴリズムでＳＣＣがスキャンされる最大回数である。
Identify SCCs in the dependence graph
MII← - ∞
for each SCC do
ＳＣＣの一般化された最大回路平均をハワードイテレーションポリシーアルゴリズムで計算するが、ＳＣＣをＨ回スキャンした後、ポリシーが安定しない場合はアボートする。
MIl = max(MII, the generalized maximal circuit mean)
isCritical(a) ←FALSE ∀operation a
for each SCC do
if MIl = the SCC's generalized maximal circuit mean then
isCritical(a) ← TRUE ∀ operation a ∈ the critical cycles in the SCC's policy graph
【００１３】
処理ブロック１２において、示される方法は、依存関係グラフを複数のステージの初期セットにパーティション化して、最適なスケジュールに近い初期スケジュールを形成する。処理ブロック１２は、時間変数（例えば、詳細に後述される「ｉ」）の初期化も提供してよい。各ステージは、ＭＩＩの予め定められた高さを有してよい。例えば、図３Ｂに示される依存関係グラフが、各ステージが複数のＭＩＩサイクルを有するようにカットされた場合、結果的に得られる初期スケジュールは、図３Ｃに示されており、ＭＩＩは２（２）に等しい。
【００１４】
依存関係グラフは、例えばベルマン・フォードアルゴリズムのようなアルゴリズムを使用してパーティション化されてよい。アルゴリズムは、依存関係グラフの疑似開始ノードから各ノードへの最長経路を計算してよい。一例において、ＭＩＩで分割された、あるノードのための経路長は、当該ノードのステージインデックスである。そのようなアプローチは、各ノードにステージが割り当てられているような、初期スケジュールを作成してよい。この処理において、各エッジ（a→b, δ, d）は、δ‐ｄ＊ＭＩＩの長さを有してよく、疑似開始は長さ０で任意の他のノードに接続してよい。エッジa→b、δ、dは、a→ bからの依存関係を有し、δはレイテンシであり、dは反復距離である。計算された最長経路は、複数のステージに分割され得る。
【００１５】
アルゴリズムは、ベルマン・フォードアルゴリズムの反復回数を制御するための閾値Ｂを使用して、例えば、以下のように実装されてよい。いったん反復回数がＢに到達し、アルゴリズムが完了していない場合、方法の全体がアボートする。
len(a) ← 0 ∀ operation a
for i ← 1 to IV I - 1 do
changed←FALSE
for each operation b in the order in the original loop body do
len(b) ← max(len(b), len(a) + δ - d * MIl) ∀ (a→b, δ,d)
changed←TRUE if len(b)is changed by the previous step
if changed=FALSE then
break
if (i < IV I - 1) and (i = B) then
abort software pipelining
【数１】
2016515735.tif 000003
offset(a) ← len(a) mod MIl ∀ node a
d ← d + stage(b) - stage(a) ∀(a→ b, δ, d)
【００１６】
処理ブロック１３において、示される方法は、パイプライン化されたスケジュールを生成および計算されたＭＩＩを達成すべく、複数のコードの最適化の実行を開始し、特に、処理ブロック１３において、示される方法は、複数のハードウェアリソースを割り当て、複数のパーティション化されたステージ内の複数の命令に対する複数のローカルの依存関係を強制し、ローカルスケジュールを作成してよい。命令内の各動作には、リソースおよびオフセットが割り当てられてよい。処理ブロック１３は、アルゴリズムで、例えば、次のように実装される。
height(a) ← -∞∀ operation a
for each operation a in reverse order in the current kernel do
for each outgoing edge (a→ b, δ, d) do
height(a) ← max(height(a); height(b) + δ - d *MII)
height(a) ← +∞∀a, isCritical(a) =TRUE
【００１７】
例えば、複数のローカルの依存関係で、高さの優先度機能に関する複数のリソース制約下で動作する、任意の一覧スケジューリングを適用する。
【００１８】
処理ブロック１４において、示される方法は、複数のループ伝搬依存性を解決すべく、ローカルスケジュールを調整することによって、複数のコードの最適化の実行を継続してよい。ローカルスケジュールで解決されない各ループ伝搬依存性に対し、ループ伝搬依存性の解決を試行すべく、１または複数の空のステージがソースと宛先命令との間に挿入されてよい（すなわち、水平方向のカーネル拡張）。そのようなアプローチは、２つの動作間の時間距離を、少なくとも依存関係のレイテンシまで伸長する。図３Ｄは、複数のループ伝搬依存性を持つローカルスケジュールを示す。図３Ｅに示されるように、ｃとｄとの間に空のステージを追加することによって、依存関係が解決される。
【００１９】
処理ブロック１３中に解決されなかった、複数のループ伝搬依存性を解決すべく、カーネル拡張が例えば次のように実行される。
【００２０】
(a → b, δ, d)が、実行されるコードの最適化前の、元の依存関係グラフ内の未解決のループ伝搬依存性グラフであるとする。第１の選択肢として、ループ伝搬依存性に係るソースとシンクノード間に、複数の空のステージを挿入することによって、水平方向のカーネル拡張により時間距離ｄを増大させる試行が実行される。そのようなアプローチは、それらの時間差に対し、依存関係のレイテンシに合うまたは超過することを強制し、それにより、開始間隔を増加させずに、依存関係を解決する。
【００２１】
別のアプローチとして、複数の空のステージを挿入することによって解決され得ないループ伝搬依存性が存在する場合、開始間隔（ＩＩ）は増大されてよい。
【００２２】
新しい複数のステージを挿入する際、既に満たされた複数の前の依存関係は違反されない可能性がある。特定の依存関係のシンクノードステージが依存関係のソースノードステージの前にある場合、それらの間にステージを挿入することは、時間差を減少するのみである可能性がある。つまり、依存関係については、複数の「禁止された」ステージと複数の「拡張可能な」ステージがあり得る。任意の禁止された（拡張可能な）ステージの直前に、複数の空のステージを挿入することは、依存関係のソースとシンクとの間の時間差を減少（増大）させ得る。正式には、エッジe : a→bに対し、forbidden(e) = {slstage(b) < s ≦ stage(a) } expandable(e) = { slstage(a) < s ≦ stage(b)}である。stage（o）は、operation oのステージインデックスであってよい。
【００２３】
複数の空のステージが、ソースとシンクの複数のノードステージの両方の前（または両方の後）に挿入される場合、時間差に影響がないので、両方のセットは、ソースとシンクのノードステージ間の複数のステージから構成されることに留意されたい。
【００２４】
よって、未解決の依存関係については、開始間隔（ＩＩ）を変更することなく解決すべく、その複数の拡張可能なステージのうちの１つの直前に挿入する最小数のステージは、次から導くことができる。δ ≦d * II + offset(b) − offset(a)]。offset(o)は、カーネル内のそのステージにおける動作oの時間オフセットである。newStages(e) = δ− offset(b) + offset(a) )/II −d。
【００２５】
基本的に、禁止されたステージのグローバルセットが計算され得、グローバルセットは、すべての依存関係の複数の禁止されたステージに係る集合である。各ステージｓに対し、変数newStagesBefore (s)によって、その前に挿入される新しいステージ数に関するレコードが作成されてよい。０に初期化される。次に、すべてのループ伝搬依存性がスキャンされてよく、示される方法は、複数の新しいステージをどこにどのくらいの数、挿入すべきか判断する。任意のループ伝搬依存性（a -> b）、が、複数の空のステージを挿入することによって解決されない場合、それを解決すべく、開始間隔（ＩＩ）が増大される。それを解決するための最小ＩＩは、feasibleII(e) = [offset(b) + offset (a) )/d]であってよい。
【００２６】
カーネル拡張を実行するアルゴリズムは、例えば、次のように実装されてよい。
ｍ←the total stages of the current kernel
Ｆ←U forbidden (e) ∀ dependence e
newStagesBefore(s) ← 0 ∀ stage s
for each dependence e : (a→ b, δ, d) d ≠ 0 do
if δ ≦ d * II + offset(b)− offset(a)], does not hold then
if expandable(e) - F≠ { }then
n ← newStages(e)
m ← m + n
if m > S、式中Ｓはカーネル内で許容される最大ステージ数であり、II ← max(II, feasiblell(e)) ∀ dependence e、およびカーネル拡張処理は終了する。
s ← any stage ∈ expandable (e)− F
newStagesBefore(x) ← newStagesBefore(x) + n
∀ stage x > = s
stage(a) ← stage(a) + newStagesBefore(stage(a)) ∀ node a
d ← d + newStagesBefore(stage(b)) - newStagesBefore(stage(a)) and after that let II ← max(II, feasiblell(e)), ∀ (a→b, δ, d)
【００２７】
処理ブロック１５において、示される方法は、処理ブロック１４が実行された後、結果的に得られるスケジュールである、調整されたローカルスケジュールが計算されたＭＩＩを達成したかどうかを判断してよく、達成する場合、処理は停止し、示される方法は処理ブロック１７にて終了する。達成しない場合、処理ブロック１６にて、示される方法は、既定の時間が発生するかどうかを判断する。例えば、示される方法は、時間変数（例えば、変数「ｉ」）が既定の時間に等しいかどうか判断してよい。既定の時間は、例えば、予め定義された反復回数のような、閾値であってよい。示される方法が、処理ブロック１３と１４とを実行するたびに、反復が発生し、処理ブロック１９において、変数（ｉ）はそれに応じてインクリメントされる。複数の実行されるコードの最適化は、示される方法がアボートする前に、限られた回数実行されてよい。従って、示される方法が、既定の時間が発生したと判断した場合、示される方法は、処理ブロック１７にて終了する。
【００２８】
処理ブロック１８において、示される方法は、調整されたローカルスケジュールを変更し、次の処理反復のための、よりコンパクトなスケジュールを作成する。計算された最小開始間隔を達成するスケジュールを生成することを試み、調整されたローカルスケジュールは、複数の命令を現在のスケジュールに基づいて、それらの現在のステージから、次のステージへと、移動させることによって変更されてよい。そのようなアプローチは、複数のコードの最適化に係る次の反復のための次の反復スケジュールを生成する。既定の時間が発生しない限り（すなわち、i≠ 既定の時間）、計算された最小開始間隔を達成する、調整されたローカルスケジュールが取得されるまで、示される方法は複数のコードの最適化を反復する。
【００２９】
処理ブロック１９において、示される方法は、変数（ｉ）を次の処理反復に対し、インクリメントしてよく、方法は、実行を継続すべく、処理ブロック１３に戻る。
【００３０】
図２Ｂは、パイプラインを実行する方法を示す。示される方法は、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、フラッシュメモリ等の、機械またはコンピュータ可読媒体、例えばＰＬＡ、ＦＰＧＡ、ＣＰＬＤ等の構成可能なロジック、例えば、ＡＳＩＣ、ＣＭＯＳ、ＴＴＬ技術等のアセンブリ言語プログラミングおよび回路技術を用いた固定機能性ハードウェア、またはこれらの任意の組み合わせに格納された、一連の論理命令および／またはファームウェアとして実装されてよい。
【００３１】
示される方法は、処理ブロック３２で、動的コンパイラによる１または複数のループを処理するためのパフォーマンスレベルを判断することを提供し、パフォーマンスレベルは、最小開始間隔（ＭＩＩ）を計算することで判断される。処理ブロック３３において、示される方法は、１または複数のループのための、既定の時間内で判断されたパフォーマンスレベルを達成する、パイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行することを提供する。複数の実行されるコードの最適化は、複数のハードウェアリソースを割り当てること、およびローカルスケジュールを生成するための各パーティション化されたステージ内に含まれる複数の命令のための複数のローカルの依存関係を判断することを含む。
【００３２】
さらに複数の実行されるコードの最適化は、複数のループ伝搬依存性を解決すべくローカルスケジュールを調整して、調整されたローカルスケジュールを作成すること、および、調整されたローカルスケジュールがパフォーマンスレベルを達成せず、既定の時間が発生しなかった場合、次の反復スケジュールを生成すべく、複数の命令をそれらの現在のステージから次のステージへ移動することを含んでよい。既定の時間が発生しない限り、調整されたローカルスケジュールがパフォーマンスレベルに達成するまで、複数の実行されるコードの最適化は、次の反復スケジュールを使用して、新しい調整されたローカルスケジュールを生成すべく、反復されてよい。
【００３３】
処理ブロック３４において、１または複数のループのための依存関係グラフが確立され、各依存関係グラフは、パフォーマンスレベルに基づいて複数のステージにパーティション化される。処理ブロック３５において、示される方法は、調整されたローカルスケジュールがパフォーマンスレベルを達成するかどうかを判断し、処理ブロック３６において、示される方法は、調整されたローカルスケジュールがパフォーマンスレベルを達成しない場合、既定の時間が発生するかどうかを判断する。
【００３４】
ここで、図４を参照すると、マイクロプロセッサシステムの図が示されている。図４に示されるのは、第１の処理エレメント１０７０および第２の処理エレメント１０８０を含み得る、マルチプロセッサシステム１０００である。２つの処理エレメント１０７０および１０８０が示される一方、システム１０００の実施形態は、そのような処理エレメントを１つのみ含んでもよいことを理解されたい。
【００３５】
システム１０００は、ポイントツーポイントインターコネクトシステムとして示されており、第１の処理エレメント１０７０および第２の処理エレメント１０８０は、ポイントツーポイントインターコネクト１０５０を介して連結される。図４に示されるインターコネクトのいずれかあるいはすべては、ポイントツーポイントインターコネクトではなく、マルチドロップバスとして実装されてよいことを理解されたい。
【００３６】
図４に示されるように、処理エレメント１０７０および１０８０の各々は、第１のプロセッサコアおよび第２のプロセッサコア（すなわち、プロセッサコア１０７４ａおよび１０７４ｂおよびプロセッサコア１０８４ａおよび１０８４ｂ）を含む、マルチコアプロセッサであってよい。そのようなコア１０７４、１０７４ｂ、１０８４ａ、１０８４ｂは、命令コードを実行するよう構成されてよい。
【００３７】
各処理エレメント１０７０、１０８０は、少なくとも１つの共有キャッシュ１８９６を含んでよい。共有キャッシュ１８９６ａ、１８９６ｂは、プロセッサの１または複数のコンポーネント、例えば、コア１０７４ａ、１０７４ｂおよび１０８４ａ、１０８４ｂによってそれぞれ利用されるデータ（例えば、複数の命令）を格納してよい。例えば、共有キャッシュは、プロセッサの複数のコンポーネントによる、より高速なアクセスのために、メモリ１０３２、１０３４内に格納されたデータをローカルにキャッシュすることができる。１または複数の実施形態において、共有キャッシュは、レベル２（Ｌ２）、レベル３（Ｌ３）、レベル４（Ｌ４）のような１または複数の中レベルキャッシュ、または他の複数のレベルのキャッシュ、ラストレベルキャッシュ（ＬＬＣ）、および／またはそれらの組み合わせを含んでよい。
【００３８】
２つの処理エレメント１０７０、１０８０のみ示されている一方、本発明の範囲はそのように限定されないことを理解されたい。複数の他の実施形態において、１または複数の追加の処理エレメントが特定のプロセッサ内に存在してよい。あるいは、１または複数の処理エレメント１０７０、１０８０は、アクセラレータもしくはフィールドプログラマブルゲートアレイのような、プロセッサ以外の要素であってよい。例えば、追加の処理エレメントは、第１のプロセッサ１０７０と同一の追加のプロセッサ、第１のプロセッサ１０７０と異種のまたは非対称の追加のプロセッサ、複数のアクセラレータ（例えば、複数のグラフィックアクセラレータまたは複数のデジタル信号処理（ＤＳＰ）ユニット）、複数のフィールドプログラマブルゲートアレイ、あるいは任意の他の処理エレメントを含んでよい。アーキテクチャ、マイクロアーキテクチャ、熱、電力消費といった特性を含む様々な価値基準の観点から、処理エレメント１０７０と１０８０との間には、様々な差異があってよい。これらの差異は、処理エレメント１０７０、１０８０の間に、非対称性および異種性として効果的に表れる。少なくとも１つの実施形態において、様々な処理エレメント１０７０、１０８０が、同一ダイパッケージ内に存在してよい。
【００３９】
第１の処理エレメント１０７０は、さらに、メモリコントローラロジック（ＭＣ）１０７２およびポイントツーポイント（Ｐ‐Ｐ）インタフェース１０７６および１０７８を含んでよい。同様に、第２の処理エレメント１０８０は、ＭＣ１０８２およびＰ−Ｐインタフェース１０８６および１０８８を含んでよい。図４に示されるように、ＭＣ１０７２および１０８２は、複数のプロセッサをそれぞれのメモリ、すなわちメモリ１０３２およびメモリ１０３４に連結し、それらは、それぞれのプロセッサにローカルに付属されるメインメモリの複数の部分であってよい。ＭＣロジック１０７２および１０８２は、処理エレメント１０７０、１０８０に統合されているように示されている一方、複数の代替的実施形態については、ＭＣロジックは、それらに統合されておらず、処理エレメント１０７０、１０８０の外部の個別のロジックであってよい。
【００４０】
第１の処理エレメント１０７０および第２の処理エレメント１０８０は、Ｐ‐Ｐインターコネクト１０７６、１０８６、および１０８４をそれぞれ介して、Ｉ／Ｏサブシステム１０９０に連結されてよい。図４に示されるように、Ｉ／Ｏサブシステム１０９０は、Ｐ−Ｐインタフェース１０９４および１０９８を含んでよい。さらに、Ｉ／Ｏサブシステム１０９０は、Ｉ／Ｏサブシステム１０９０を高性能グラフィックスエンジン１０３８に連結するためのインタフェース１０９２を含んでよい。一実施形態において、グラフィックスエンジン１０３８をＩ／Ｏサブシステム１０９０に連結すべく、バスが使用されてよい。あるいは、ポイントツーポイントインターコネクト１０３９が、これらのコンポーネントを連結してよい。
【００４１】
そして、Ｉ／Ｏサブシステム１０９０は、インタフェース１０９６を介して第１のバス１０１６に連結されてよい。一実施形態において、第１のバス１０１６は、ペリフェラルコンポーネントインターコネクト（ＰＣＩ）バス、またはＰＣＩ  Ｅｘｐｒｅｓｓバスもしくは別の第３世代Ｉ／Ｏインターコネクトバスなどのバスであってもよいが、本発明の範囲はこれに限定されない。
【００４２】
図４に示されている通り、第１のバス１０１６には、第１のバス１０１６を第２のバス１０２０に連結し得るバスブリッジ１０１８とともに、多様なＩ／Ｏデバイス１０１４が連結され得る。一実施形態において、第２のバス１０２０は、ローピンカウント（ＬＰＣ）バスであってよい。一実施形態において、例えば、キーボード／マウス１０１２、通信デバイス１０２６（コンピュータネットワーク５０３と通信し得る）、およびコード１０３０を含み得るディスクドライブ若しくは他の大容量記憶装置等のデータストレージユニット１０１９を含む、様々なデバイスが第２のバス１０１０が連結され得る。コード１０３０は、例えば、図２Ａおよび／または２Ｂの複数の方法のような、上記の方法のうち、１または複数のものに係る複数の実施形態を実行するための複数の命令を含んでよい。さらに、オーディオＩ／Ｏ１０２４が、第２のバス１０１０に連結されてよい。
【００４３】
複数の他の実施形態が考えられることに留意されたい。例えば、図４のポイントツーポイントアーキテクチャの代わりに、システムは、マルチドロップバス若しくは別のそのような通信トポロジを実装してよい。また、図４の複数の要素は、代替的に、図４に示されるものより、さらに多いまたは少ない数の統合されたチップを使用してパーティション化されてよい。
【００４４】
図５は、一実施形態による、プロセッサコア２００を示す。プロセッサコア２００は、マイクロプロセッサ、組み込みプロセッサ、デジタルシグナルプロセッサ（ＤＳＰ）、ネットワークプロセッサ、またはコードを実行するための他のデバイスのような、任意のタイプのプロセッサのためのコアであってよい。図５では、１つのプロセッサコア２００のみが示されているが、処理エレメントは代替的に、図５に示されるプロセッサコア２００を２以上含んでよい。プロセッサコア２００は、シングルスレッドコアであってよく、あるいは、少なくとも１つの実施形態については、当該実施形態が、コアごとに、２つ以上のハードウェアスレッドコンテキスト（または「ロジカルプロセッサ」）を含み得るという点で、プロセッサコア２００はマルチスレッド化されてよい。
【００４５】
図５はまた、プロセッサ２００に連結されたメモリ２７０を示す。メモリ２７０は、当業者にとって、既知あるいは入手可能な様々なメモリ（メモリ階層の様々な層を含む）のうち任意のであってよい。メモリ２７０は、プロセッサ２００コアによって実行される１または複数のコード２１３命令を含んでよく、その場合、コード２１３は図２Ａおよび／または２Ｂに示される複数の方法を実装してよい。プロセッサコア２００は、コード２１３によって示される複数の命令からなるプログラムシーケンスに従う。各命令は、フロントエンドの一部２１０を入力してよく、１または複数のデコーダ２２０によって処理されてよい。デコーダ２２０は、その出力として、予め定義されたフォーマットで固定幅のマイクロオペレーションのようなマイクロオペレーションを生成してよく、あるいは、他の複数の命令、マイクロ命令、もしくは元のコード命令を反映する制御信号を生成してよい。示されるフロントエンド２１０はまた、概して複数のリソースおよびキューに対し、実行のための変換命令に対応する動作を割り当てるレジスタリネーミングロジック２２５およびスケジューリングロジック２３０を含んでよい。
【００４６】
プロセッサ２００は、一連の実行ユニット２５５―１から２５５‐Ｎを有する、実行ロジック２５０を含むように示されている。いくつかの実施形態は、特定の複数の機能または複数の機能セット専用の複数の実行ユニットを含んでよい。複数の他の実施形態は、１つの実行ユニットのみ、または特定の機能を実行し得る１つの実行ユニットを含んでよい。示される実行ロジック２５０は、複数のコード命令によって指定される複数の動作を実行する。
【００４７】
複数のコード命令によって指定される複数の動作の実行完了後、バックエンドロジック２６０がコード２１３の複数の命令を退避する。一実施形態において、プロセッサ２００は、アウトオブオーダ実行を可能にするが、複数の命令のインオーダ退避を要求する。退避ロジック２６５は、当業者に既知の様々な形態を取る（例えば、複数のリオーダバッファ等）。このような態様で、プロセッサコア２００は、コード２１３の実行中、少なくともデコーダによって生成される出力の観点において、レジスタリネーミングロジック２２５によって利用される複数のハードウェアレジスタおよびテーブル、および実行ロジック２５０によって変更される任意の複数のレジスタ（不図示）に変換される。
【００４８】
図５に示されないが、処理エレメントは、プロセッサコア２００を備えるチップ上に複数の他の要素を含んでよい。例えば、処理エレメントは、プロセッサコア２００とともにメモリ制御ロジックを含んでよい。処理エレメントは、Ｉ／Ｏ制御ロジックを含んでよく、および／またはメモリ制御ロジックと統合されたＩ／Ｏ制御ロジックを含んでよい。処理エレメントはまた、１または複数のキャッシュを含んでよい。
【００４９】
追加の留意点および複数の例
【００５０】
例１は、パイプラインを実行する装置を含んでよい。装置は、動的コンパイラによって、１または複数のループを処理するためのパフォーマンスレベルを判断するための第１のモジュールと、１または複数のループのために、既定の時間内に判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行するための第２のモジュールと、を備えてよい。
【００５１】
例２は、例１の装置を備えてよく、上記１または複数のループのための依存関係グラフを確立し、上記パフォーマンスレベルに基づき、各依存関係グラフを複数のステージにパーティション化するための第３のモジュールをさらに備える。
【００５２】
例３は、例２の装置を備えてよく、調整されたローカルスケジュールが、上記パフォーマンスレベルを達成するかどうか判断するための第４のモジュールと、上記調整されたローカルスケジュールが、上記パフォーマンスレベルを達成しない場合、上記既定の時間が発生したかどうか判断するための第５のモジュールと、をさらに備える。
【００５３】
例４は、例１から３のいずれかの装置を備えてよく、パフォーマンスレベルは、最小開始間隔（ＭＩＩ）を計算することによって判断される。
【００５４】
例５は、例３の装置を備えてよく、実行された複数のコードの最適化は、複数のハードウェアリソースを割り当てること、およびローカルスケジュールを生成すべく、各パーティション化されたステージ内に含まれるすべての命令のための複数のローカルの依存関係を解決することを含む。
【００５５】
例６は、例５の装置を備えてよく、実行された複数のコードの最適化は、複数のループ伝搬依存性を解決し、調整されたローカルスケジュールを作成すべく、ローカルスケジュールを調整する。
【００５６】
例７は、例６の装置を備えてよく、実行された複数のコードの最適化は、調整されたローカルスケジュールがパフォーマンスレベルを達成せず、既定の時間が発生しなかった場合、次の反復スケジュールを生成すべく、複数の命令を、それらの現在のステージから次のステージへ移動することを含む。
【００５７】
例８は、例７の装置を備えてよく、実行された上記複数のコードの最適化は、上記次の反復スケジュールを使用して新しい調整されたローカルスケジュールを生成すべく、上記既定の時間が発生しない限り、上記調整されたローカルスケジュールが上記パフォーマンスレベルを達成するまで、反復される。
【００５８】
例９は、少なくとも１つのコンピュータプログラムを備えてよく、そのプログラムはコンピューティングデバイス上での実行時、コンピューティングデバイスを構成して、動的コンパイラによって、１または複数のループを処理するためのパフォーマンスレベルを判断する手順と、１または複数のループのために、既定の時間内に判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行する手順と、を実行させる。
【００５９】
例１０は、例９の少なくとも１つのコンピュータプログラムを備えてよく、上記１または複数のループのための依存関係グラフを確立する手順と、上記パフォーマンスレベルに基づき、各依存関係グラフを複数のステージにパーティション化する手順と、をさらに実行させる。
【００６０】
例１１は、例１０の少なくとも１つのコンピュータプログラムを備えてよく、調整されたローカルスケジュールが、上記パフォーマンスレベルを達成するかどうか判断する手順と、上記調整されたローカルスケジュールが、上記パフォーマンスレベルを達成しない場合、上記既定の時間が発生したかどうか判断する手順と、をさらに実行させる。
【００６１】
例１２は、例９から１１のいずれかの少なくとも１つのコンピュータプログラムを備えてよく、パフォーマンスレベルは、最小開始間隔（ＭＩＩ）を計算することによって判断される。
【００６２】
例１３は、例１１の少なくとも１つのコンピュータプログラムを備えてよく、実行された上記複数のコードの最適化は、複数のハードウェアリソースを割り当てること、およびローカルスケジュールを生成すべく、各パーティション化されたステージ内に含まれる複数の命令のための複数のローカルの依存関係を解決すること、を含む。
【００６３】
例１４は、例１３の少なくとも１つのコンピュータプログラムを備えてよく、実行された上記複数のコードの最適化は、複数のループ伝搬依存性を解決し、上記調整されたローカルスケジュールを作成すべく、上記ローカルスケジュールを調整することを含む。
【００６４】
例１５は、例１４の少なくとも１つのコンピュータプログラムを備えてよく、実行された上記複数のコードの最適化は、上記調整されたローカルスケジュールが上記パフォーマンスレベルを達成せず、上記既定の時間が発生しなかった場合、次の反復スケジュールを生成すべく、複数の命令を、それらの現在のステージから次のステージへ移動することを含む。
【００６５】
例１６は、例１５の少なくとも１つのコンピュータプログラムを備えてよく、実行された上記複数のコードの最適化は、上記次の反復スケジュールを使用して新しい調整されたローカルスケジュールを生成すべく、上記既定の時間が発生しない限り、上記調整されたローカルスケジュールが上記パフォーマンスレベルを達成するまで、反復される。
【００６６】
例１７は、動的コンパイラによって、１または複数のループを処理するためのパフォーマンスレベルを判断する段階と、上記１または複数のループのために、既定の時間内に上記判断されたパフォーマンスレベルを達成するパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行する段階と、を備える、パイプラインを実行する方法を備えてよい。
【００６７】
例１８は、例１７の方法を備えてよく、上記１または複数のループのための依存関係グラフを確立する段階と、上記パフォーマンスレベルに基づき、各依存関係グラフを複数のステージにパーティション化する段階と、をさらに備える。
【００６８】
例１９は、例１８の方法を備えてよく、調整されたローカルスケジュールが、上記パフォーマンスレベルを達成するかどうか判断する段階と、上記調整されたローカルスケジュールが、上記パフォーマンスレベルを達成しない場合、上記既定の時間が発生したかどうか判断する段階と、をさらに備える。
【００６９】
例２０は、例１７から１９のいずれかの方法を備えてよく、パフォーマンスレベルは、最小開始間隔（ＭＩＩ）を計算することによって判断される。
【００７０】
例２１は、例１９の方法を備えてよく、実行された上記複数のコードの最適化は、複数のハードウェアリソースを割り当てること、およびローカルスケジュールを生成すべく、各パーティション化されたステージ内に含まれる複数の命令のための複数のローカルの依存関係を解決すること、を含む。
【００７１】
例２２は、例２１の方法を備えてよく、実行された複数のコードの最適化は、複数のループ伝搬依存性を解決し、調整されたローカルスケジュールを作成すべく、ローカルスケジュールを調整することを含む。
【００７２】
例２３は、例２２の方法を備えてよく、実行された上記複数のコードの最適化は、上記調整されたローカルスケジュールが上記パフォーマンスレベルを達成せず、上記既定の時間が発生しなかった場合、次の反復スケジュールを生成すべく、複数の命令を、それらの現在のステージから次のステージへ移動することを含む。
【００７３】
例２４は、例２３の方法を備えてよく、実行された上記複数のコードの最適化は、上記次の反復スケジュールを使用して新しい調整されたローカルスケジュールを生成すべく、上記既定の時間が発生しない限り、上記調整されたローカルスケジュールが上記パフォーマンスレベルを達成するまで、反復される。
【００７４】
例２５は、例１７から２４の複数の方法のうちいずれかを実行するための手段を備える、パイプラインを実行するための装置を備えてよい。
【００７５】
複数の例は、プロセッサにより実行されると、プロセッサに対し、動的コンパイラによって１または複数のループを処理するためのパフォーマンスレベルを判断させ、既定の時間内に判断されたパフォーマンスレベルを達成する１または複数のループのためのパイプライン化されたスケジュールを生成すべく、複数のコードの最適化を実行させる命令セットを有する、コンピュータ可読記憶媒体を提供してよい。
【００７６】
他の複数の例は、プロセッサにより実行されると、プロセッサに対し、動的コンパイラによって１または複数のループを処理するための最小開始間隔を計算させ、既定の時間内に計算された最小開始間隔を達成する１または複数のループのためのパイプライン化されたスケジュールを生成させる、命令セットを有する、コンピュータ可読媒体を提供してよい。
【００７７】
本発明の複数の実施形態は、すべてのタイプの半導体集積回路（「ＩＣ」）チップでの使用に適用可能である。これらのＩＣチップの複数の例は、限定されないが、複数のプロセッサ、コントローラ、チップセットコンポーネント、プログラマブルロジックアレイ（ＰＬＡ）、メモリチップ、ネットワークチップ等を含む。また、一部の図面では、信号伝導ラインは線で表している。あるものはより多くの成分信号パスを示すべく異なっており、あるものは多数の成分信号パスを示すべく数の符号を有しており、および／または、あるものは主な情報のフロー方向を示すべく、１または複数のエッジにおいて矢印を有している。しかしながら、このことは、限定的に解釈されるべきではない。むしろ、そのような追加された詳細は、１または複数の例示的実施形態と連携して使用し、回路の理解を容易化できる。表されているあらゆる信号線は、追加的な情報を有するか否かに関わらず、実際には複数の方向に移動することができ、例えば、差動対とともに実装されたデジタルまたはアナログ線、光ファイバ線、および／またはシングルエンド線などのあらゆる適切なタイプの信号スキームに実装され得る、１または複数の信号を備え得る。
【００７８】
例示としての大きさ／モデル／値／範囲を提示したが、本発明の実施形態はこれらに限定されない。将来的に製造技術（例えば、フォトリソグラフィ）が発展すれば、小型のデバイスが製造可能となると考えられる。また、ＩＣチップおよび他のコンポーネントへの周知の電力／接地接続が図面内に示されていることもあり、示されていないこともある。これは図示および説明を単純にするためであり、本発明の実施形態の特定の特徴を曖昧にしないようにするためである。さらに、配置については、本発明の実施形態をあいまいにすることを避けるべくブロック図で図示している。ブロック図で図示している理由としてはさらに、このようなブロック図で示す配置の実施例に関する具体的な内容は実施形態を実施し得るプラットフォームに大きく左右されること、つまり、このような詳細な内容については当業者の知識の範囲内であることが挙げられる。具体的且つ詳細な内容（例えば、回路）は本発明の実施形態例を説明するために記載しているが、当業者には、本発明の実施形態は、こういった具体的且つ詳細な内容を採用することなく、または、これらの変形例を用いて実施可能であることが明らかである。つまり、詳細な説明は、限定ではなく例示的なものとしてみなされるべきである。
【００７９】
いくつかの実施形態は、例えば、機械によって実行されると、機械に対し、当該複数の実施形態に係る方法および／または複数の動作を実行させる、命令もしくは命令セットを格納し得る、機械若しくは有形なコンピュータ可読媒体若しくは物品を使用して、実装されてよい。そのような機械として、例えば、任意の適切な処理プラットフォーム、コンピューティングプラットフォーム、コンピューティングデバイス、プロセッシングデバイス、コンピューティングシステム、プロセッシングシステム、コンピュータ、プロセッサ、またはその他を挙げることが可能であり、さらに、ハードウェアおよび／またはソフトウェアの任意の適切な組み合わせを用いて実装されてもよい。
【００８０】
機械可読媒体又は物品は、例えば、任意の適切な種類のメモリユニット、メモリデバイス、メモリ物品、メモリ媒体、記憶デバイス、記憶物品、記憶媒体および／または記憶ユニット、例えば、メモリ、取り外し可能または取り外し不可能媒体、消去可能または消去不可能媒体、書き込み可能又は再書き込み可能媒体、デジタル又はアナログ媒体、ハードディスク、フロッピー（登録商標）ディスク、コンパクトディスクリードオンリメモリ（ＣＤ−ＲＯＭ）、コンパクトディスクレコーダブル（ＣＤ−Ｒ）、コンパクトディスクリライタブル（ＣＤ−ＲＷ）、光ディスク、磁気媒体、光磁気媒体、取り外し可能メモリカード又はディスク、種々のタイプのデジタル多用途ディスク（ＤＶＤ）、テープ、カセットなどを含み得る。
【００８１】
機械可読媒体は、機械によって読み取り可能な形態で情報を格納、送信、または受信するための任意のメカニズムを含んでよく、当該媒体は、プログラムコードがそこを介して通過する、複数のアンテナ、光ファイバ、通信インタフェース等のような媒体を含んでよい。プログラムコードは、パケット、シリアルデータ、パラレルデータなどの形で伝送されてよく、圧縮または暗号化された形式で使用されてよい。
【００８２】
プログラムコード、または複数の命令は、例えば、限定されないが、ソリッドステートメモリ、複数のハードドライブ、複数のフロッピー（登録商標）ディスク、光学記憶装置、複数のテープ、フラッシュメモリ、複数のメモリスティック、複数のデジタルビデオディスク、複数のデジタル多目的ディスク（ＤＶＤ）等を含む、複数のストレージデバイスおよび／または関連機械可読媒体若しくは機械アクセス可能媒体、並びに機械アクセス可能な生物学的状態保持ストレージ等のよりエキゾチックな媒体といった、揮発性および／または不揮発メモリ上に格納されてよい。
【００８３】
これらの命令は、任意の適切なハイレベル、ローレベル、オブジェクト指向、ビジュアル、コンパイル済み、および／または解釈済みプログラミング言語を用いて実現される、ソースコード、コンパイル済みコード、解釈済みコード、実行可能コード、スタティックコード、ダイナミックコード、暗号化コードなどのような任意の適切な種類のコードを含むことができる。
【００８４】
別途明示される場合を除き、「処理」、「コンピューティング」、「計算」、「判断」等の用語が、計算システムのレジスタおよび／またはメモリ内の物理量（例えば、電子）として表されるデータを操作し、および／またはそのようなデータを、コンピューティングシステムのメモリ、レジスタ、若しくは他のそのような情報記憶装置、伝送デバイス、または表示デバイス内の物理量として同様に表される他のデータに変換するコンピュータ若しくはコンピューティングシステム、または同様の電子コンピューティングデバイスの動作および／またはプロセスを指すことを理解することができる。当該複数の実施形態は、当該文脈に限定されない。
【００８５】
本明細書において、用語「連結された」は、対象となるコンポーネント間の、直接的または間接的ないずれのタイプの関係についても述べるために用いることができ、電気接続、機械的接続、流体接続、光学接続、電磁接続、電気機械接続又は他の接続に適用し得る。また、用語「第１の」、「第２の」等は、本明細書において、説明を容易にするために用いられているに過ぎず、別途明記されない限り、特定の時間的または年代的重要性を有しない。当業者であれば、上記の説明から、本発明の実施形態に係る広範囲にわたる技術はさまざまな形態で実装可能であることに想到するであろう。したがって、特定の例に関連して本発明の実施形態が説明されてきた一方、本発明の実施形態の真の態様はそのように限定されるべきではない。なぜなら、当業者が図面、明細書、および以下の特許請求の範囲を検討することにより、他の修正が明らかとなるからである。
【図１】
2016515735.tif 000004
【図２Ａ】
2016515735.tif 000005
【図２Ｂ】
2016515735.tif 000006
【図３Ａ】
2016515735.tif 000007
【図３Ｂ】
2016515735.tif 000008
【図３Ｃ】
2016515735.tif 000009
【図３Ｄ】
2016515735.tif 000010
【図３Ｅ】
2016515735.tif 000011
【図４】
2016515735.tif 000012
【図５】
2016515735.tif 000013
【国際調査報告】
2016515735.tif 000014
2016515735.tif 000015