(57)【要約】【課題】ストリーム長予測を使用する分岐予測器検索限定のコンピュータ実装方法、システムおよびプログラムを提供する。【解決手段】コンピュータ実装方法が、プロセッサのストリーム・ベース・インデックス・アクセラレータ予測器によって、命令アドレスと、命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定することを含む。プロセッサの階層的非同期先読み分岐予測器の第１のレベルの分岐予測器が、命令アドレスと予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリにおける分岐予測を見つけるために検索される。階層的非同期先読み分岐予測器の第２のレベルの分岐予測器の検索が、検索範囲内の分岐予測を見つけるのに失敗することに基づいてトリガされる。【選択図】図８
2020501242.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ実装方法であって、
プロセッサのストリーム・ベース・インデックス・アクセラレータ予測器によって、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定することと、
前記命令アドレスと前記予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリにおける分岐予測を見つけるために前記プロセッサの階層的非同期先読み分岐予測器の第１のレベルの分岐予測器を検索することと、
前記検索範囲内の前記分岐予測を見つけるのに失敗することに基づいて前記階層的非同期先読み分岐予測器の第２のレベルの分岐予測器の検索をトリガすることと
を含む、コンピュータ実装方法。
【請求項２】
前記第１のレベルの分岐予測器が、分岐ターゲット・バッファと分岐ターゲット・バッファ・プリロード・テーブルとを備える、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記第２のレベルの分岐予測器の前記検索に基づいて、複数の分岐を前記第２のレベルの分岐予測器から前記分岐ターゲット・バッファまたは前記分岐ターゲット・バッファ・プリロード・テーブルに転送することをさらに含む、請求項２に記載のコンピュータ実装方法。
【請求項４】
前記階層的非同期先読み分岐予測器の前記第２のレベルの分岐予測器の前記検索をトリガすることが、デフォルトの検索の深さに達する前に実施される、請求項１に記載のコンピュータ実装方法。
【請求項５】
前記階層的非同期先読み分岐予測器の前記第２のレベルの分岐予測器の前記検索が、デフォルトの検索の深さを超えて拡張される、請求項１に記載のコンピュータ実装方法。
【請求項６】
前記ストリーム・ベース・インデックス・アクセラレータ予測器が前記予測ストリーム長を正しく予測し前記正しい予測が使用される回数に基づいて精度カウンタを更新することをさらに含む、請求項１に記載のコンピュータ実装方法。
【請求項７】
前記精度カウンタが精度閾値超であることを決定することに基づいて前記検索範囲の使用を有効にすることと、
前記精度カウンタが前記精度閾値未満であることを決定することに基づいて前記検索範囲の使用を無効にし、デフォルトの検索の深さの使用を有効にすることと
をさらに含む、請求項６に記載のコンピュータ実装方法。
【請求項８】
システムであって、
命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定するように動作可能であるプロセッサのストリーム・ベース・インデックス・アクセラレータ予測器と、
第１のレベルの分岐予測器および第２のレベルの分岐予測器を備える前記プロセッサの階層的非同期先読み分岐予測器と
を備え、前記階層的非同期先読み分岐予測器が、
前記命令アドレスと前記予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリにおける分岐予測を見つけるために前記第１のレベルの分岐予測器を検索し、
前記検索範囲内の前記分岐予測を見つけるのに失敗することに基づいて前記第２のレベルの分岐予測器の検索をトリガするように動作可能である、システム。
【請求項９】
前記第１のレベルの分岐予測器が、分岐ターゲット・バッファと分岐ターゲット・バッファ・プリロード・テーブルとを備える、請求項８に記載のシステム。
【請求項１０】
前記階層的非同期先読み分岐予測器が、前記第２のレベルの分岐予測器の前記検索に基づいて複数の分岐を前記第２のレベルの分岐予測器から前記分岐ターゲット・バッファまたは前記分岐ターゲット・バッファ・プリロード・テーブルに転送するように動作可能である、請求項９に記載のシステム。
【請求項１１】
前記階層的非同期先読み分岐予測器の前記第２のレベルの分岐予測器の前記検索が、デフォルトの検索の深さに達する前にトリガされる、請求項８に記載のシステム。
【請求項１２】
前記階層的非同期先読み分岐予測器の前記第２のレベルの分岐予測器の前記検索が、デフォルトの検索の深さを超えて拡張される、請求項８に記載のシステム。
【請求項１３】
精度カウンタが、前記ストリーム・ベース・インデックス・アクセラレータ予測器が前記予測ストリーム長を正しく予測し前記正しい予測が使用される回数に基づいて更新される、請求項８に記載のシステム。
【請求項１４】
前記精度カウンタが精度閾値超であることを決定することに基づいて、前記検索範囲の使用が有効にされ、前記精度カウンタが前記精度閾値未満であることを決定することに基づいて、前記検索範囲の使用が無効にされ、デフォルトの検索の深さの使用が有効にされる、請求項１３に記載のシステム。
【請求項１５】
プログラム命令が具現化されたコンピュータ可読記憶媒体を備えるコンピュータ・プログラム製品であって、前記コンピュータ可読記憶媒体が、一時的信号それ自体ではなく、前記プログラム命令が、プロセッサによって、
前記プロセッサのストリーム・ベース・インデックス・アクセラレータ予測器によって、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定することと、
前記命令アドレスと前記予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリにおける分岐予測を見つけるために前記プロセッサの階層的非同期先読み分岐予測器の第１のレベルの分岐予測器を検索することと、
前記検索範囲内の前記分岐予測を見つけるのに失敗することに基づいて前記階層的非同期先読み分岐予測器の第２のレベルの分岐予測器の検索をトリガすることと
を含む方法を前記プロセッサに実施させるように実行可能である、コンピュータ・プログラム製品。
【請求項１６】
前記第１のレベルの分岐予測器が、分岐ターゲット・バッファと分岐ターゲット・バッファ・プリロード・テーブルとを備える、請求項１５に記載のコンピュータ・プログラム製品。
【請求項１７】
前記プログラム命令により、前記プロセッサが、
前記第２のレベルの分岐予測器の前記検索に基づいて複数の分岐を前記第２のレベルの分岐予測器から前記分岐ターゲット・バッファまたは前記分岐ターゲット・バッファ・プリロード・テーブルに転送することをさらに実施する、請求項１６に記載のコンピュータ・プログラム製品。
【請求項１８】
前記階層的非同期先読み分岐予測器の前記第２のレベルの分岐予測器の前記検索をトリガすることが、デフォルトの検索の深さに達する前に実施される、請求項１５に記載のコンピュータ・プログラム製品。
【請求項１９】
前記階層的非同期先読み分岐予測器の前記第２のレベルの分岐予測器の前記検索が、デフォルトの検索の深さを超えて拡張される、請求項１５に記載のコンピュータ・プログラム製品。
【請求項２０】
前記プログラム命令により、前記プロセッサが、
前記ストリーム・ベース・インデックス・アクセラレータ予測器が前記予測ストリーム長を正しく予測し前記正しい予測が使用される回数に基づいて精度カウンタを更新することと、
前記精度カウンタが精度閾値超であることを決定することに基づいて前記検索範囲の使用を有効にすることと、
前記精度カウンタが前記精度閾値未満であることを決定することに基づいて前記検索範囲の使用を無効にし、デフォルトの検索の深さの使用を有効にすることと
をさらに実施する、請求項１５に記載のコンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、マイクロプロセッサ設計の分野に関し、より詳しくは、ストリーム長予測を使用する分岐予測器検索限定（branch predictor search qualification）に関する。
【背景技術】
【０００２】
分岐予測は、パイプライン化された高周波マイクロプロセッサの性能重視の構成要素である。分岐予測は、各分岐命令の方向（取られるのか取られないのか）および宛先アドレスを予測するのに使用される。分岐予測により、処理は、分岐の結果が決定されるのを待つ必要なく、分岐の予測経路に沿って継続することが可能になるので、これは有益である。分岐が間違って予測された場合にはペナルティが発生する。パイプライン化された分岐予測器は、予測をするのにいくつかのサイクルを要する。
【０００３】
従来、分岐予測は、プログラム内で実行すべき最も可能性の高いコードの経路に沿ってプロセッサ・パイプラインを下るよう命令の流れを導くのに使用される。分岐予測は、ＩＦ−ＴＨＥＮ−ＥＬＳＥ構造体に含まれるコードのどの部分が、コードのどの部分が過去において実行されたのかに基づいて実行されるのかを予測することなど、所与の分岐が行われるのかまたは行われないのかを予測するために履歴情報を使用する。次いで、最初に行われる分岐であることが期待される分岐がフェッチされ、投機的に実行される。予測が間違っていたことが後で決定される場合、投機的に実行されたまたは部分的に実行された命令は破棄され、パイプラインはもう一度やり直しされ、命令は正しい分岐経路を有する分岐まで進み、分岐と次に実行すべき命令との間に遅延を招く。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
分岐予測を提供するのに使用される構造体のアクセス時間は、それらの容量を制限する。階層的分岐予測器は、システムにより大きな容量を提供することができる。そのような設計において、第１のレベルの予測器の複数の連続検索からの分岐予測の不在は、典型的には、レベル２構造体からレベル１構造体への「レベル１ミス」に近い複数の分岐の検索およびバルク転送をトリガするのに使用することができる「レベル１ミス」の表示として使用される。しかし、予測の不在は、容量問題によることであり得るか、その場合、階層の第２のレベルにアクセスするのは有益である、または予測の不在は、検索されるコードのセクションに位置する分岐命令が何もないことによることであり得るかのいずれかである。非同期先読み分岐予測器は、典型的には、これらの２つの場合を区別することができない。したがって、階層的分岐予測器内の検索および転送プロセスを改善することが有利であろう。
【課題を解決するための手段】
【０００５】
実施形態によれば、コンピュータ実装方法が、プロセッサのストリーム・ベース・インデックス・アクセラレータ予測器によって、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定することを含む。プロセッサの階層的非同期先読み分岐予測器の第１のレベルの分岐予測器が、命令アドレスと予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリにおける分岐予測を見つけるために検索される。階層的非同期先読み分岐予測器の第２のレベルの分岐予測器の検索が、検索範囲内の分岐予測を見つけるのに失敗することに基づいてトリガされる。
【０００６】
他の実施形態によれば、システムが、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定するように動作可能であるプロセッサのストリーム・ベース・インデックス・アクセラレータ予測器を備える。システムは、第１のレベルの分岐予測器と第２のレベルの分岐予測器とを備えたプロセッサの階層的非同期先読み分岐予測器も備える。階層的非同期先読み分岐予測器は、命令アドレスと予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリにおける分岐予測を見つけるために第１のレベルの分岐予測器を検索し、検索範囲内の分岐予測を見つけるのに失敗することに基づいて第２のレベルの分岐予測器の検索をトリガするように動作可能である。
【０００７】
さらに他の実施形態によれば、コンピュータ・プログラム製品が、プログラム命令が具現化されたコンピュータ可読記憶媒体を備え、その場合、コンピュータ可読記憶媒体は、一時的信号それ自体ではない。プログラム命令は、プロセッサのストリーム・ベース・インデックス・アクセラレータ予測器によって、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定することを含む方法をプロセッサに実施させるようにプロセッサによって実行可能である。プロセッサの階層的非同期先読み分岐予測器の第１のレベルの分岐予測器が、命令アドレスと予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリにおける分岐予測を見つけるために検索される。階層的非同期先読み分岐予測器の第２のレベルの分岐予測器の検索が、検索範囲内の分岐予測を見つけるのに失敗することに基づいてトリガされる。
【０００８】
主題は、明細書の結論において、特に指摘され、特許請求の範囲において明確に特許請求される。次に、本発明の好ましい実施形態を、例としてのみ、および以下の図面を参照して説明する。
【図面の簡単な説明】
【０００９】
【図１】実施形態によるコンピューティング・デバイスの構成要素のブロック図である。
【図２】実施形態によるシステムのブロック図である。
【図３】実施形態による分岐ターゲット・バッファにおけるエントリを示す図である。
【図４】実施形態による別のシステムのブロック図である。
【図５】実施形態による分岐予測器検索を示す図である。
【図６】実施形態による分岐予測器拡張検索を示す図である。
【図７】実施形態による分岐予測器縮小検索を示す図である。
【図８】実施形態によるコンピュータ実装方法を示すフローチャートである。
【発明を実施するための形態】
【００１０】
実施形態は、ストリーム・ベース分岐予測インデックス・アクセラレータ（ＳＰＲＥＤ）と組み合わせて分岐予測プロセスにプロセッサの階層的非同期先読み分岐予測器を使用する。階層的非同期先読み分岐予測器は、第１のレベルの分岐予測器と、第１のレベルの分岐予測器における分岐を見つけるのに失敗することにより検索される第２のレベルの分岐予測器とを含む。第１のレベルの分岐予測器および第２のレベルの分岐予測器は、それぞれ、異なるサイズおよび性能特性を有する１つまたは複数の分岐ターゲット・バッファ（ＢＴＢ）を含むことができる。ＢＴＢは、分岐、目標情報、および任意選択で他の予測支援情報を記憶する構造体である。
【００１１】
非同期先読み分岐予測は、命令フェッチから開始するプロセッサ・パイプラインとは非同期的に行われる。命令フェッチと同じ時間フレームにおいて、指定した命令アドレスから再開され次第、分岐予測は、再開アドレスにおいて、またはその後に、第１の分岐を見つけるために第１のレベルの分岐予測器を独立して検索する。分岐を見つけ次第、分岐予測論理は、それを命令フェッチ論理に、およびパイプライン論理に報告し、分岐予測と、デコードされる命令との間の結果としての相関が可能になるようにする。パイプラインの残りとは独立して、分岐予測論理は、予測された行われる分岐の予測宛先アドレスを用いてそれ自体のインデックスを再作成する。予測された行われない分岐では、それは連続して検索を継続する。次いで、それは次の分岐を探す。次いで、このプロセスは繰り返される。分岐予測器のインデックスを作成すること、それらから内容を読み出すこと、および予測された行われる分岐があるかどうかを決定すること、およびそうである場合、その宛先アドレスは、現代の高周波設計で複数のプロセッサ・サイクルを要することがある。
【００１２】
第１のレベルの分岐予測器は、一般に、命令アドレスを使用してインデックスが作成され、ある量だけインクリメントされて、コードの領域内の分岐を連続して検索することを継続する。間違った分岐の場合など、プロセッサ命令ストリームが再開されるたびに、検索が開始し、新たなストリームが開始される。したがって、各予測された行われる分岐は、新たなストリームを開始する。実施形態は、ＳＰＲＥＤからストリーム長情報を利用して、潜在的な第１のレベルの分岐予測器ミスに対してどのように動作するかを決定する。第２のレベルの分岐予測器の完全な検索などの完全な動作は、検索される現在のストリームを終了させる行われる分岐予測の命令アドレスが現在の検索アドレスよりも大きいことをＳＰＲＥＤが示すとき、防止することができ、そのとき、分岐予測が何も見つけられなかったとき普通ならレベル１のミスとして報告されたはずであるくらいにその現在の検索アドレスが開始点を超えて十分に離れている。ストリームが早期に終了することをＳＰＲＥＤが予測したが、分岐は何も見つけられなかったとき（例えば、固定ミス限度の前に）、ミスは加速させることができる。
【００１３】
図１は、実施形態を含むシステムの例であるコンピュータ・システム１００を示す。コンピュータ・システム１００は、分岐予測器１０５およびインデックス・アクセラレータ１０７を含むコンピュータ・プロセッサ１０４の間に通信を提供する通信ファブリック１０２と、メモリ１０６と、永続記憶装置１０８と、通信ユニット１１０と、入出力（Ｉ／Ｏ）インターフェース１１２と、キャッシュ１１６とを含む。通信ファブリック１０２は、システム内のプロセッサ（マイクロプロセッサ、通信およびネットワーク・プロセッサなど）、システム・メモリ、周辺デバイス、および任意の他のハードウェア構成要素の間でデータを渡し、または情報を制御し、あるいはその両方をするように設計された任意のアーキテクチャを用いて実装することができる。例えば、通信ファブリック１０２は、１つまたは複数のバスを用いて実装することができる。
【００１４】
メモリ１０６および永続記憶装置１０８は、コンピュータ可読記憶媒体である。この実施形態において、メモリ１０６は、ランダム・アクセス・メモリ（ＲＡＭ）を含む。概して、メモリ１０６は、任意の適切な揮発性または非揮発性コンピュータ可読記憶媒体を含むことができる。キャッシュ１１６は、最近アクセスしたデータおよびメモリ１０６からアクセスしたデータに近いデータを保持することによってプロセッサ１０４の性能を高める高速メモリである。キャッシュ１１６は、プロセッサ１０４内にまたはその外部にあるいはその両方に分散させることができ、命令（例えば、Ｉキャッシュ）またはデータ（例えば、Ｄキャッシュ）あるいはその両方を含むことができる。
【００１５】
実施形態を実施するのに使用されるプログラム命令およびデータは、キャッシュ１１６およびメモリ１０６の１つまたは複数のメモリを介してそれぞれのプロセッサ１０４の１つまたは複数によって実行するために永続記憶装置１０８に記憶することができる。実施形態において、永続記憶装置１０８は、磁気ハード・ディスク・ドライブを含む。代替案として、または磁気ハード・ディスク・ドライブに加えて、永続記憶装置１０８は、固体ハード・ドライブ、半導体記憶デバイス、読出し専用メモリ（ＲＯＭ）、消去可能プログラマブル読出し専用メモリ（ＥＰＲＯＭ）、フラッシュ・メモリ、またはプログラム命令もしくはデジタル情報を記憶することができる任意の他のコンピュータ可読記憶媒体を含むことができる。
【００１６】
永続記憶装置１０８によって使用される媒体は、取外し可能でもよい。例えば、取外し可能ハード・ドライブを永続記憶装置１０８に使用することができる。他の例には、光および磁気ディスク、サム・ドライブおよび永続記憶装置１０８の一部でもある別のコンピュータ可読記憶媒体への転送のためにドライブに挿入されるスマート・カードが含まれる。
【００１７】
これらの例における通信ユニット１１０は、他のデータ処理システムまたはデバイスとの通信を提供する。これらの例において、通信ユニット１１０は、１つまたは複数のネットワーク・インターフェース・カードを含む。通信ユニット１１０は、物理的通信リンクまたは無線通信リンクのいずれか、あるいはその両方の使用を通じて通信を提供することができる。実施形態を実施するのに使用されるプログラム命令およびデータは、通信ユニット１１０を通じて永続記憶装置１０８にダウンロードすることができる。
【００１８】
Ｉ／Ｏインターフェース１１２により、各コンピュータ・システムに接続することができる他のデバイスとのデータの入力および出力が可能になる。例えば、Ｉ／Ｏインターフェース１１２は、キーボード、キーパッド、タッチ・スクリーン、または他の何らかの適切な入力デバイス、あるいはその組合せなど、外部デバイス１１８との接続をもたらすことができる。外部デバイス１１８は、例えば、サム・ドライブ、ポータブル光または磁気ディスク、およびメモリ・カードなどのポータブル・コンピュータ可読記憶媒体を含むこともできる。実施形態を実施するのに使用されるソフトウェアおよびデータは、そのようなポータブル・コンピュータ可読記憶媒体に記憶することができ、Ｉ／Ｏインターフェース１１２を介して永続記憶装置１０８にロードすることができる。Ｉ／Ｏインターフェース１１２は、ディスプレイ１２０に接続することもできる。ディスプレイ１２０は、データを表示する機構をユーザに提供することができ、例えば、コンピュータ・モニタであることができる。
【００１９】
分岐予測器１０５およびインデックス・アクセラレータ１０７は、命令ストリームにおける分岐の位置に関する予測を行い、記憶することができるハードウェア論理構成要素の１つまたは複数の組を含むことができる。分岐予測器１０５およびインデックス・アクセラレータ１０７の実施形態例は、図２〜８を参照して本明細書においてさらに説明する。
【００２０】
図２は、図１の分岐予測器１０５の実施形態として階層的非同期先読み分岐予測器２０５と、図１のインデックス・アクセラレータ１０７の実施形態としてＳＰＲＥＤ２０７とを含むシステム２００を示す。図２の階層的非同期先読み分岐予測器例２０５は、第１のレベルの分岐予測器（ＢＴＢ１）２０４と、ＢＴＢ１検索およびヒット論理２０２と、第２のレベルの分岐予測器（ＢＴＢ２）２０６と、ＢＴＢ２検索トラッカ２０８と、ＢＴＢ２検索およびヒット論理２１０とを含む。ＢＴＢ１検索およびヒット論理２０２は、ＢＴＢ１  ２０４におけるＢＴＢエントリのアクセスおよび更新を制御するが、ＢＴＢ２検索およびヒット論理２１０は、ＢＴＢ２  ２０６におけるＢＴＢエントリのアクセスおよび更新を制御する。例示的な実施形態において、ＢＴＢ１  ２０４は、一次または第１のレベルのＢＴＢであり、ＢＴＢ２  ２０６は、二次または第２のレベルのＢＴＢである。ＢＴＢ２検索トラッカ２０８は、ＳＰＲＥＤ限定（qualified）ＢＴＢ１ミスに基づいてＢＴＢ２  ２０６からの複数のＢＴＢエントリのバルク転送を検索し、制御するためのフィルタとして構成することができる。ＳＰＲＥＤ限定ＢＴＢ１ミスは、メモリの同じ領域に関連した命令キャッシュ・ミスによってさらに制限することができる。ＢＴＢ１検索およびヒット論理２０２、ＳＰＲＥＤ２０７、ならびにＢＴＢ２検索およびヒット論理２１０を別々に示すが、それらは組み合わせて単一の論理ブロックにし、またはさらに細かく分割することができることが理解されよう。
【００２１】
ＢＴＢ１  ２０４およびＢＴＢ２  ２０６のそれぞれは、ＢＴＢエントリの複数の組を含むセット・アソシエイティブ方式である。ＢＴＢ２  ２０６は、分岐予測情報のより高いレベルのキャッシュである。ＢＴＢ２  ２０６の容量は、エントリを記憶するためにＢＴＢ１  ２０４の容量よりも大きく、ＢＴＢ１  ２０４は、図１のキャッシュ１１６の命令キャッシュよりも大きな、またはそれに等しい命令フットプリントを包含する。ＢＴＢエントリの一般的な例をＢＴＢエントリ３００（エントリ３００とも称する）として図３に示し、それは分岐アドレス・タグ３０２と、予測宛先アドレス３０６とを含む。図１〜３を引き続いて参照すると、分岐アドレス・タグ３０２が、ＢＴＢ行３１０内のエントリを見つけるのに使用され、その場合、図２のＢＴＢ１  ２０４およびＢＴＢ２  ２０６のそれぞれは、複数のＢＴＢ行３１２と、ＢＴＢ行３１０ごとの複数のセット・アソシエイティブ方式のＢＴＢエントリとを含むことができる。ＢＴＢ１  ２０４およびＢＴＢ２  ２０６は、互いに対して異なる数のＢＴＢ行３１２および列を有することができる。各ＢＴＢエントリ３００は、関連した分岐が行われたか、または行われなかったかを示すために分岐方向などの他の分岐予測情報（図示せず）を含むことができる。
【００２２】
例示的な実施形態において、図１のプロセッサ１０４における命令フェッチの再開に対応する検索アドレスが、ＢＴＢ１検索およびヒット論理２０２に送られ、その後、それは次の再開まで命令フェッチとは非同期的に動作する。分岐予測を探すとき、ＢＴＢ１  ２０４は、読み出され、それが検索アドレスと一致する分岐アドレス・タグ３０２を有するエントリを含む場合、分岐予測を提供することができる。ＢＴＢ１  ２０４は、入力をＢＴＢ１検索およびヒット論理２０２に提供して、一致または「ヒット」が検索アドレスに基づいて見つけられるかどうかを決定する。一致が見つかった場合、ＢＴＢ１検索およびヒット論理２０２が予測宛先アドレスを出力する。一致が見つからなかった場合、ＢＴＢ１  ２０４の連続検索は、検索範囲にわたって継続してから、ＢＴＢ１ミスを宣言し、ＢＴＢ２検索トラッカ２０８を通じてさらに動作を行う。
【００２３】
ＢＴＢ１  ２０４の検索範囲は、ＳＰＲＥＤ２０７によって設定することができる。実施形態において、ＳＰＲＥＤ２０７は、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定する。ＢＴＢ１  ２０４は、命令アドレスと予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリ３００における分岐予測を見つけるために検索される。ＢＴＢ２  ２０６の検索は、検索範囲内の分岐予測を見つけるのに失敗することに基づいてトリガすることができる。
【００２４】
いくつかの実施形態において、ＢＴＢ２検索トラッカ２０８は、省略することができる。ＢＴＢ２検索トラッカ２０８を含む実施形態において、ＢＴＢ１ミスは、ＢＴＢ２ページの粒度により追跡することができる。例えば、ＢＴＢ２バルク転送粒度（ページ・サイズ）が４ＫＢである場合、同じ４ＫＢページにおける任意の限定されたＢＴＢ１ミスが同じページ・ミスとみなされる。ＢＴＢ２検索トラッカ２０８における検索トラッカが特定のページにおけるＢＴＢ１ミスに対してアクティブである場合、その同じページにおける任意の後続のミスは無視されるが、その検索トラッカはアクティブであり、そのページ・アドレスは、最近完了したものとして識別される。有効な命令キャッシュ・ミス妥当性インジケータ（例えば、「１」に設定されたビット）を有するが、ＢＴＢ１ミス妥当性インジケータが無効である（例えば、「０」に設定されたビット）、ＢＴＢ２検索トラッカ２０８におけるアクティブな検索トラッカの複製であるＢＴＢ１ミスを検出し次第、検索トラッカの関連したＢＴＢ１ミス妥当性インジケータは、有効（例えば、「１」）に設定することができる。
【００２５】
ＢＴＢ１ミスとは独立して、命令キャッシュ・ミスが起きたとき、それらはＢＴＢ２検索トラッカ２０８に送ることができる。各検索トラッカは、命令キャッシュ・ミスを追跡することもできる。命令キャッシュ・ミスは、ＢＴＢ２バルク転送と同じページ粒度、または異なる命令キャッシュ粒度により追跡することができる。命令キャッシュ・ミス・アドレスがＢＴＢ１ミス（ＢＴＢ１ミス・アドレス）に対してアクティブであるが、命令キャッシュ・ミスに対してはアクティブでないトラッカのアドレスと一致した場合、命令キャッシュ・ミス妥当性インジケータは、有効（例えば、「１」）に設定することができる。
【００２６】
アクティブな検索トラッカは、ＢＴＢ２  ２０６の検索を実施するのに使用することができる。例示的な実施形態において、検索トラッカがＢＴＢ１ミスおよび命令キャッシュ・ミスの両方に対してアクティブであるときは、全ページ転送を行うことができる。ページ内のＢＴＢ２  ２０６のすべての行は検索され、ヒットがＢＴＢ１  ２０４に書き込まれる。ＢＴＢ１ミスおよび命令キャッシュ・ミスの両方に対してアクティブである検索トラッカは、ＢＴＢ２バルク転送が完了するまでアクティブのままであることができる。
【００２７】
ＳＰＲＥＤ２０７は、命令ストリームにおいて受け取った第１の命令のアドレスに対応する行のインデックスを追跡することができ、ＳＰＲＥＤ２０７の現在の行に含まれる情報が読み出される。様々な実施形態において、アドレス空間の幅により、様々な数の固有の命令アドレスが存在することがあり、結果として、異なる数の行が様々な実施形態においてＳＰＲＥＤ２０７に必要とされる可能性がある。一般に、所与の命令に対する命令アドレスのビットのサブセットだけが、所与の命令に対する分岐予測データを含むＳＰＲＥＤ２０７における行番号を識別するのに使用される。例えば、３２ビットの命令アドレスが使用される（ビット０から３１までを含む）実施形態において、各命令アドレスは、命令アドレスの最初の１７ビット（ビット０から１６まで）で構成された左タグ（Ｌタグ）、命令アドレスの次の１０ビット（ビット１７から２６まで）で構成されたインデックス、および命令アドレスの最後の５ビット（ビット２７から３１まで）で構成された右タグ（Ｒタグ）に分割することができる。この実施形態において、インデックスとして使用される命令アドレスの１０ビットだけが、分岐予測データがその命令に対して記憶されるＳＰＲＥＤ２０７における行を決定するのに使用されるので、ＳＰＲＥＤ２０７は１０２４行を含む。さらに、いくつかの実施形態において、ＳＰＲＥＤ２０７は、ＢＴＢ１  ２０４と同じ数の行を含み、命令アドレスの、ＢＴＢ１  ２０４と同じ１０ビットに基づいてインデックスが作成されるように設計される。他の実施形態において、ＢＴＢ１  ２０４およびＳＰＲＥＤ２０７は、それぞれのテーブルにおいてどの行がその命令に対する分岐予測情報を含むのかを決定するのに異なる数のビットを使用する。これらの実施形態において、ＢＴＢ１  ２０４およびＳＰＲＥＤ２０７は、異なる数の行を有し、それでも正しい動作ができることが可能である。
【００２８】
現在の命令に対応するＳＰＲＥＤ２０７の行に含まれるデータは、現在の命令に分岐が期待されるかどうかを決定するために読み出すことができる。ＳＰＲＥＤ２０７の１つの行が、偽信号が使用される実施形態において、多数の命令アドレスに対応することができること、およびこれらの実施形態において、複数の命令アドレスがＳＰＲＥＤ２０７における同じ行に対応することができることを理解されたい。一実施形態において、ＳＰＲＥＤ２０７の現在の行に記憶されたデータの最初のビットは、行われる予測がＢＴＢ１  ２０４の対応する行に存在するか否かの２進法表示を含む。この実施形態において、行われる予測がＢＴＢ１  ２０４の対応する行に存在するか否かの決定は、ＢＴＢ１  ２０４のいくつの検索がストリームを終了させる行われる分岐に出合う前に行う必要があるのかを示すオフセット・フィールドを使用して行われる。
【００２９】
プロセッサ１０４は、ＳＰＲＥＤ２０７の現在の選択された行に示される最初に行われる分岐予測の宛先アドレスを識別することができる。いくつかの実施形態において、ＳＰＲＥＤ２０７の１つまたは複数の行によって示される最初に行われる予測に対する宛先アドレスを予測するために、変更ターゲット・バッファ（ＣＴＢ）などの追加の構造体を使用することができる。これらの実施形態において、最初に行われる予測の宛先アドレスは、省略することができ、ＢＴＢ１  ２０４の列の表示は、ＣＴＢなどの追加の構造体を使用して、最初に行われる予測の宛先アドレスをより容易に識別するのに使用することができる。
【００３０】
ＳＰＲＥＤ２０７から予測が取り出されるのと同時にＢＴＢ１  ２０４から予測を取り出すことができる。ＳＰＲＥＤ２０７から取り出された予測は、ＢＴＢ１  ２０４から取り出された予測によって確認または論争されるまで有効とみなすことができる。様々な実施形態において、ＳＰＲＥＤ２０７に含まれるデータのビットは、予測の宛先アドレスに対してＳＰＲＥＤ２０７のインデックスを再度作成するのに使用されるデータのビットであることができる。ＳＰＲＥＤ２０７のインデックスを再度作成するためにデータのより多いまたはより少ないビットが使用される実施形態において、ＳＰＲＥＤ２０７の所与の行に含まれる数の長さは異なることがある。最初に行われる分岐予測の宛先アドレスが識別されると、プロセッサ１０４は、最初に行われる分岐予測に対する宛先アドレスに対応する行に対してＳＰＲＥＤ２０７およびＢＴＢ１  ２０４のインデックスを再度作成する。ＳＰＲＥＤ２０７およびＢＴＢ１  ２０４のインデックスが再度作成されると、プロセッサ１０４は、新たな宛先アドレスにおける分岐予測に対してＢＴＢ１  ２０４およびＳＰＲＥＤ２０７を検索するプロセスを再開する。
【００３１】
プロセッサ１０４は、より多くの検索すべきアドレス空間があるかどうかを決定することができる。ＢＴＢ１検索およびヒット論理２０２などの検索論理が、検索を停止すべきであると判断した場合、分岐予測検索が終了する。再開は、分岐予測論理における新たな検索ストリームを開始する。再開が行われると、プロセッサ１０４は、分岐に対する検索を連続して続けることができる。他の実施形態において、プロセッサ１０４は、ＳＰＲＥＤ２０７がストリームの終了を見つけたときは、インデックスを再度作成することを加速させることもでき、したがって、プロセッサ１０４は、新たなストリームへの検索を開始するように分岐予測器１０５をリダイレクトする。命令アドレスが前の命令アドレスに続く再開の要求を受け取った場合、プロセッサ１０４は、分岐の存在の予測に対するＢＴＢ１  ２０４およびＳＰＲＥＤ２０７の次の連続行を検索することを継続することができる。概して、ＢＴＢ１  ２０４  およびＳＰＲＥＤ２０７のインデックスは、ＢＴＢ１  ２０４およびＳＰＲＥＤ２０７における次の行が命令ストリームに存在する命令の次の連続の組に対する分岐予測情報を含むので、インクリメントすることができる。
【００３２】
ＳＰＲＥＤ２０７は、予測出口点またはストリームを終了させる行われる分岐を決定することができる。例えば、ストリーム０の開始において、０ｘ００の開始命令アドレスは、ＳＰＲＥＤ２０７へのインデックスを作成するのに使用することができ、ＳＰＲＥＤ２０７の出力は、出口点がストリーム０の開始からＸ位置／命令であることを示すことができる。ＳＰＲＥＤ２０７の出力は、Ｘ位置／命令がストリーム０において検索されると、ストリーム１へのインデックスを作成することを加速させるのに使用することができる。インデックスを作成することは、開始命令アドレスとともに進んで、Ｙ位置／命令の出力を生じ、ストリーム１の出口点が存在するところなどを示すことができる。この方式により、ＳＰＲＥＤ２０７は、ストリームの検索開始アドレスとともに（例えば）、ストリームごとに１回読み出しする必要があるだけであり得る。ＳＰＲＥＤ２０７のエントリは、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長として予測出口点へのオフセットを含む情報を含むことができる。
【００３３】
いくつかの実施形態において、精度カウンタ２０９（すなわち、ＳＰＲＥＤ精度カウンタ）が、ＳＰＲＥＤ２０７が予測ストリーム長を正しく予測し正しい予測が使用される回数に基づいて更新される。検索範囲の使用は、命令アドレスと予測ストリーム長とによって境界されるとき、精度カウンタ２０９が精度閾値超であることを決定することに基づくことができる。ＳＰＲＥＤ２０７の精度が精度閾値未満である場合、ＳＰＲＥＤ２０７を不正確とみなすことができ、結果として、精度カウンタ２０９が精度閾値未満であることを決定することに基づいて検索範囲の使用を無効にし、デフォルトの検索の深さの使用を有効にすることになる。例えば、デフォルトの検索範囲を、ミスを宣言する前の３つのエントリの検索などの所定の値に設定することができる。対照的に、ＳＰＲＥＤ２０７は、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長に基づいてデフォルトの検索範囲よりも大きいまたは小さい検索範囲を設定することができる。
【００３４】
図４は、図１の分岐予測器１０５の実施形態として階層的非同期先読み分岐予測器４０５と、図１のインデックス・アクセラレータ１０７の実施形態としてＳＰＲＥＤ４０７とを含むシステム４００を示す。図４の階層的非同期先読み分岐予測器例４０５は、ＢＴＢ１  ４０４および分岐ターゲット・バッファ・プリロード・テーブル（ＢＴＢＰ）４０３を有する第１のレベルの分岐予測器４０１と、ＢＴＢ１検索およびヒット論理４０２と、第２のレベルの分岐予測器（ＢＴＢ２）４０６と、ＢＴＢ２検索トラッカ４０８と、ＢＴＢ２検索およびヒット論理４１０とを含む。
【００３５】
ＢＴＢＰ４０３は、分岐命令のターゲットおよび任意選択で方向を予測するためにより大きな主ＢＴＢ（ＢＴＢ１  ４０４）と並列に検索される小型のＢＴＢであることができる。ＢＴＢ１  ４０４がより大きいので、それは限定された数の読出し書込みポート（同じサイクルで同じバンクに読出しおよび書込みをすることが可能でない制限を有する、通常１つまたは２つの読出しおよび単一の書込みポート）を有することができる大型のＳＲＡＭアレイを用いて実装することができる。しかし、ＢＴＢＰ４０３は、ＢＴＢ１  ４０４よりもずっと小さいので、それは、例えば、ＳＲＡＭレジスタ・ファイルを用いて実装することができる。ＢＴＢＰ４０３は、同時に使用することができる多くの読出し書込みポートを有することができる。したがって、分岐予測情報の複数のソースは、まずＢＴＢＰ４０３に書き込まれることによってＢＴＢＰ４０３の書込み帯域幅を利用することができる。ＢＴＢＰ４０３は、ＢＴＢ１  ４０４のフィルタとして働くように構築することができ、その場合、ＢＴＢ１  ４０４は、ＢＴＢＰ４０３から分岐予測情報を受け取る。例示的な実施形態において、ＢＴＢＰ４０３は、ＢＴＢＰ４０３からＢＴＢ１  ４０４への最も有用（例えば、少なくとも１つの検索ヒット）とみなされる分岐を促進する。ＢＴＢＰ４０３は、ＢＴＢ１  ４０４から最近退去された分岐予測情報を記憶することによってセット・アソシエイティブ方式のビクティムＢＴＢキャッシュとしての機能を果たすこともできる。ＢＴＢＰ４０３は、ソフトウェア・プリロード・インストールをサポートすることができ、ＢＴＢ２  ４０６などの他の構造体とインターフェースすることができる。
【００３６】
図２の実施形態と同様に、ＢＴＢ１検索およびヒット論理４０２は、ＢＴＢ１  ４０４（および任意選択でＢＴＢＰ４０３）におけるＢＴＢエントリのアクセスおよび更新を制御するが、ＢＴＢ２検索およびヒット論理４１０は、ＢＴＢ２  ４０６におけるＢＴＢエントリのアクセスおよび更新を制御する。例示的な実施形態において、ＢＴＢＰ４０３  およびＢＴＢ１  ４０４は、第１のレベルの分岐予測器４０１を集合的に形成し、ＢＴＢ２  ４０６は、二次または第２のレベルのＢＴＢである。ＢＴＢ２検索トラッカ４０８は、ＳＰＲＥＤ限定ＢＴＢ１ミスに基づいてＢＴＢ２  ４０６からＢＴＢＰ４０３へのＢＴＢエントリのバルク転送を検索し、制御するためのフィルタとして構成することができる。ＳＰＲＥＤ限定ＢＴＢ１ミスは、メモリの同じ領域に関連した命令キャッシュ・ミスによってさらに制限することができる。ＢＴＢ１検索およびヒット論理４０２、ＳＰＲＥＤ４０７、ならびにＢＴＢ２検索およびヒット論理４１０を別々に示すが、それらは組み合わせて単一の論理ブロックにすることができ、またはさらに細かく分割することができることが理解されよう。直接ＢＴＢ２  ４０６からＢＴＢ１  ４０４への複数の分岐を転送するのではなく、ＢＴＢ２検索およびヒット論理４１０は、分岐をＢＴＢＰ４０３に転送することができる。ＢＴＢＰ４０３に位置した分岐は、ＢＴＢＰ４０３内の分岐の「ヒット」を識別し次第、ＢＴＢ１  ４０４に転送することができる。
【００３７】
いくつかの実施形態において、ＢＴＢ１  ４０４およびＢＴＢＰ４０３は、ＳＰＲＥＤ４０７によって定義された検索範囲と並列に検索される。他の実施形態において、ＳＰＲＥＤ  ４０７によって定義された検索範囲は、ＢＴＢ１  ４０４の検索を制限するが、ＢＴＢＰ４０３の検索範囲は制限しない。ＢＴＢ１  ４０４およびＢＴＢ２  ４０６は、図２のＢＴＢ１  ２０４およびＢＴＢ２  ２０６と同様に構造化することができる。ＳＰＲＥＤ４０７、ＢＴＢ２検索トラッカ４０８、精度カウンタ４０９、ならびにＢＴＢ２検索およびヒット論理４１０は、図２のＳＰＲＥＤ２０７、ＢＴＢ２検索トラッカ２０８、精度カウンタ２０９、ならびにＢＴＢ２検索およびヒット論理２１０と同様に動作することができる。
【００３８】
図５〜７は、図２および４のＳＰＲＥＤ２０７、４０７を有効にし、および有効にせずに実施された第１のレベルの分岐予測器検索の例を示す。ＳＰＲＥＤ２０７、４０７が無効にされているとき、通常の検索プロセス５００を実施することができる。精度カウンタ２０９、４０９を含む実施形態では、精度カウンタ２０９、４０９が精度閾値未満である間、ＢＴＢ１  ２０４、４０４は、オフセット０において検索開始アドレス５０２から調べ、デフォルトの検索の深さ５０４に達するまでオフセット１およびオフセット２において検索を継続することができる。デフォルトの検索の深さ５０４に達した後、一致が何も見つからなかった場合、ミスが示され、それは結果としてＢＴＢ２  ２０６、４０６をさらに検索することになり得る。精度カウンタ２０９、４０９が精度閾値超である（または精度カウンタ２０９、４０９は省略される）場合、命令アドレスと予測ストリーム長とによって境界される検索範囲にわたってＳＰＲＥＤ２０７、４０７から検索が実施される。予測ストリーム長は、デフォルトの検索の深さ５０４を超えて拡張することができ、それにより、ＢＴＢ２  ２０６、４０６の不必要な検索の時期尚早のトリガが防止され、または予測ストリーム長は、デフォルトの検索の深さ５０４未満であることができ、それにより、ＢＴＢ２  ２０６、４０６検索の早期トリガが可能になり得る。
【００３９】
検索プロセス６００は、ＳＰＲＥＤ有効拡張検索の例である。オフセット０において検索開始アドレス６０２からＢＴＢ１  ２０４、４０４を調べ、デフォルトの検索の深さ６０４に達するまでオフセット１およびオフセット２において検索を継続することができる。ミスを宣言するのではなく、検索は、デフォルトの検索の深さ６０４を超えてオフセット３および４まで拡張し、予測ストリーム長６０６に達するとミスを示す。ＳＰＲＥＤ２０７、４０７によって予測されたように、行われる分岐がオフセット４で見つかった場合、精度カウンタ２０９、４０９は、インクリメントすることができる。それ以外の場合、ＢＴＢ２  ２０６、４０６の検索をトリガすることができ、精度カウンタ２０９、４０９をデクリメントすることができる。
【００４０】
検索プロセス７００は、ＳＰＲＥＤ有効縮小検索の例である。オフセット０において検索開始アドレス７０２からＢＴＢ１  ２０４、４０４を調べることができる。デフォルトの検索の深さ７０４に達するまでオフセット１およびオフセット２において検索を継続するのではなく、予測ストリーム長７０６においてオフセット０に達し次第、デフォルトの検索の深さ７０４の前にミスが早期に示される。ＳＰＲＥＤ２０７、４０７によって予測されたように、行われる分岐がオフセット０において見つかった場合、精度カウンタ２０９、４０９をインクリメントすることができる。それ以外の場合、ＢＴＢ２  ２０６、４０６の検索をトリガすることができ、精度カウンタ２０９、４０９をデクリメントすることができる。
【００４１】
次に図８を参照すると、ストリーム長予測を使用する分岐予測器検索限定のプロセス８００が、例示的な実施形態において、ここで説明される。プロセス８００は、図１〜７を参照して説明され、図１の分岐予測器１０５およびインデックス・アクセラレータ１０７によって実装することができる。
【００４２】
ブロック８０２において、プロセッサ１０４のＳＰＲＥＤ２０７、４０７は、命令アドレスと命令ストリームを終了させる行われる分岐との間の予測ストリーム長を決定する。ブロック８０４において、プロセッサ１０４の階層的非同期先読み分岐予測器２０５、４０５の第１のレベルの分岐予測器（ＢＴＢ１  ２０４、４０４またはＢＴＰ４０３あるいはその組合せ）は、命令アドレスと予測ストリーム長とによって境界される検索範囲内の１つまたは複数のエントリにおける分岐予測を検索する。
【００４３】
ブロック８０６において、階層的非同期先読み分岐予測器２０５、４０５の第２のレベルの分岐予測器（ＢＴＢ２  ２０６、４０６）の検索が、検索範囲内の分岐予測を見つけるのに失敗することに基づいてトリガされる。検索のトリガは、結果としてＢＴＢ２  ２０６、４０６からＢＴＢ１  ２０４、４０４またはＢＴＢＰ４０３あるいはその両方への複数の分岐のバルク転送となることがある。ＳＰＲＥＤ２０７、４０７の使用は、図２、４、および６の例に示すように、デフォルトの検索の深さ（命令キャッシュ・ミスにより、さらに限定される可能性がある）を超えてＢＴＢ２  ２０６、４０６の検索を拡張することができる。ＳＰＲＥＤ２０７、４０７は、図２、４、および７の例に示すように、代替案として、デフォルトの検索の深さ（命令キャッシュ・ミスにより限定される可能性がある）に達する前にＢＴＢ２  ２０６、４０６の検索をトリガすることができる。
【００４４】
前に説明したように、いくつかの実施形態において、ＳＰＲＥＤ２０７、４０７が予測ストリーム長を正しく予測し正しい予測が使用される回数に基づいて精度カウンタ２０９、４０９を更新することができる。検索範囲の使用は、精度カウンタ２０７、４０７が精度閾値超であることを決定することに基づいて有効にすることができる。精度カウンタ２０７、４０７が精度閾値未満であることを決定することに基づいて、検索範囲の使用は、無効にすることができ、デフォルトの検索の深さの使用は有効にすることができる。
【００４５】
本発明は、統合の任意の可能な技術詳細レベルにおけるシステム、方法、またはコンピュータ・プログラム製品あるいはその組合せでもよい。コンピュータ・プログラム製品は、プロセッサに本発明の態様を実行させるための、上にコンピュータ可読プログラム命令を有するコンピュータ可読記憶媒体（または複数の媒体）を含むことができる。
【００４６】
コンピュータ可読記憶媒体は、命令実行デバイスによって使用するための命令を保持し、記憶することができる有形デバイスであることができる。コンピュータ可読記憶媒体は、例えば、電子記憶デバイス、磁気記憶デバイス、光記憶デバイス、電磁気記憶デバイス、半導体記憶デバイス、または前述のものの任意の適切な組合せでもよいが、それに限定されない。コンピュータ可読記憶媒体のより具体的な例の非網羅的リストには、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、消去可能プログラマブル読出し専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク読出し専用メモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピ・ディスク、パンチ・カードまたは上に記録された命令を有する溝における隆起構造体などの機械的にエンコードされたデバイス、および前述のものの任意の適切な組合せが含まれる。コンピュータ可読記憶媒体は、本明細書では、電波または他の自由に伝搬する電磁波、導波管もしくは他の伝送媒体中を伝搬する電磁波（例えば、光ファイバ・ケーブル中を通過する光パルス）、または電線中を伝送される電気信号などの一時的信号それ自体であるとはみなされない。
【００４７】
本明細書に説明するコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体からそれぞれのコンピューティング／処理デバイスに、またはネットワーク、例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワークまたは無線ネットワークあるいはその組合せを介して外部コンピュータまたは外部記憶デバイスにダウンロードすることができる。ネットワークは、銅伝送ケーブル、光伝送ファイバ、無線伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータまたはエッジ・サーバあるいはその組合せを備えることができる。各コンピューティング／処理デバイスにおけるネットワーク・アダプタ・カードまたはネットワーク・インターフェースは、コンピュータ可読プログラム命令をネットワークから受け取り、それぞれのコンピューティング／処理デバイス内のコンピュータ可読記憶媒体における記憶のためにコンピュータ可読プログラム命令を転送する。
【００４８】
本発明の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データ、集積回路用構成データ、またはＳｍａｌｌｔａｌｋ（Ｒ）もしくはＣ＋＋などのオブジェクト指向プログラミング言語および「Ｃ」プログラミング言語もしくは同様のプログラミング言語などの手続き型プログラミング言語を含む１つまたは複数のプログラミング言語の任意の組合せで作成されたソース・コードもしくはオブジェクト・コードのいずれかでもよい。コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で、部分的にユーザのコンピュータ上で、独立型ソフトウェア・パッケージとして、部分的にユーザのコンピュータ上で、および部分的に遠隔コンピュータ上または完全に遠隔コンピュータもしくはサーバ上で実行することができる。最後のシナリオでは、遠隔コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意の種類のネットワークを通じてユーザのコンピュータに接続することができ、または接続は、外部コンピュータと（例えば、インターネット・サービス・プロバイダを使用してインターネットを通じて）行うことができる。いくつかの実施形態において、例えば、プログラマブル論理回路、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、またはプログラマブル・ロジック・アレイ（ＰＬＡ）を含む電子回路は、本発明の態様を実施するために、コンピュータ可読プログラム命令の状態情報を利用して、電子回路を個人向けにすることによって、コンピュータ可読プログラム命令を実行することができる。
【００４９】
本発明の態様は、本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラム製品のフローチャートまたはブロック図あるいはその両方を参照して本明細書に説明する。フローチャートまたはブロック図あるいはその両方の各ブロックおよびフローチャートまたはブロック図あるいはその両方におけるブロックの組合せは、コンピュータ可読プログラム命令によって実装することができることが理解されよう。
【００５０】
これらのコンピュータ可読プログラム命令は、コンピュータまたは他のプログラマブル・データ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作を実装する手段を作り出すべく、汎用コンピュータ、専用コンピュータ、または他のプログラマブル・データ処理装置のプロセッサに提供されて、マシンを作り出すものであってよい。これらのコンピュータ可読プログラム命令は、命令が記憶されたコンピュータ可読記憶媒体が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作の態様を実装する命令を含んだ製品を含むべく、コンピュータ可読記憶媒体に記憶され、コンピュータ、プログラマブル・データ処理装置、または他のデバイスあるいはその組合せに特定の方式で機能するように指示するものであってもよい。
【００５１】
コンピュータ可読プログラム命令は、コンピュータ、他のプログラマブル装置、または他のデバイスで実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作を実装するように、コンピュータ実装プロセスを作出するべく、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスにロードされ、コンピュータ、他のプログラマブル装置または他のデバイス上で一連の動作ステップを実施させるものであってもよい。
【００５２】
図におけるフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品の可能な実装形態のアーキテクチャ、機能、および動作を示す。この点において、フローチャートまたはブロック図における各ブロックは、指定した論理機能を実装するための１つまたは複数の実行可能な命令を含む、命令のモジュール、セグメントまたは部分を表すことができる。いくつかの代替実装形態において、ブロックにおいて記載した機能は、図に記載した順序以外で起きる可能性がある。例えば、連続して示す２つのブロックは、実際、関与する機能により、実質的に同時に実行されることがあり、またはブロックは、逆の順序で実行されることもある。ブロック図またはフローチャートあるいはその両方の各ブロック、およびブロック図またはフローチャートあるいはその両方におけるブロックの組合せは、指定した機能もしくは動作を実施し、または専用ハードウェアとコンピュータ命令との組合せを実行する専用ハードウェア・ベース・システムによって実装することができることも留意されたい。
【００５３】
本発明の様々な実施形態の説明を例示のために提示してきたが、開示した実施形態に対して網羅的であることまたは限定されることは意図されてない。多くの変更形態および変形形態が、説明した実施形態の範囲および思想から逸脱することなく当業者には明らかであろう。本明細書に使用した用語は、実施形態の原理、市場に見出される技術に対する実際の適用または技術的改善を最もよく説明するように、または本明細書に開示した実施形態を当業者が理解することを可能にするように選択された。
【図１】
2020501242.tif 000003
【図２】
2020501242.tif 000004
【図３】
2020501242.tif 000005
【図４】
2020501242.tif 000006
【図５】
2020501242.tif 000007
【図６】
2020501242.tif 000008
【図７】
2020501242.tif 000009
【図８】
2020501242.tif 000010
【国際調査報告】
2020501242.tif 000011
2020501242.tif 000012