(57)【要約】【解決手段】命令フェッチユニットの電力を落とすことによりプロセッサの電力消費を低下させる装置および方法が記載される。たとえば、方法の一実施形態は、アドレッシング情報が対応付けられた分岐を検出する段階、アドレッシング情報を命令プリフェッチバッファ内のエントリと比較し、プリフェッチバッファに実行可能な命令ループが存在するかを判定する段階と、比較の結果、命令ループが検出されると、命令フェッチユニットおよび／または命令フェッチユニットのコンポーネントの電力を落とす段階と、クリア条件が検出されるまで、プリフェッチバッファから直接的に命令をストリーミングする段階を備える。【選択図】図１
2013541758.tif 000002
【特許請求の範囲】
【請求項１】
命令フェッチユニットおよびプリフェッチバッファを有するプロセッサ上での電力消費を低下させる方法であって、
アドレッシング情報が対応付けられた分岐を検出する段階と、
前記アドレッシング情報を命令プリフェッチバッファ内のエントリと比較して、前記命令プリフェッチバッファ内に実行可能な命令ループが存在するかを判定する段階と、
前記比較の結果、命令ループが検出されると、命令フェッチユニットおよび／または前記命令フェッチユニットのコンポーネントの電力を落とす段階と、
クリア条件が検出されるまで、前記命令プリフェッチバッファから直接的に命令をストリーミングする段階と
を備える方法。
【請求項２】
前記アドレッシング情報は、カレントリニアインストラクションポインタ（ＣＬＩＰ）、分岐オフセット、および／または分岐対象アドレスを含む請求項１に記載の方法。
【請求項３】
前記クリア条件は、誤予測された分岐を含む請求項１または２に記載の方法。
【請求項４】
前記命令ループは、入れ子状命令ループを含む請求項１から３のいずれか１項に記載の方法。
【請求項５】
前記命令フェッチユニットの電力を落とす段階は、命令キャッシュおよび／または命令デコードキャッシュの電力を落とす段階を有する請求項１から４のいずれか１項に記載の方法。
【請求項６】
前記命令フェッチユニットの電力を落とす段階は、分岐予測ユニット、次命令ポインタ、および／または命令変換ルックアサイドバッファ（ＩＴＬＢ）の電力を落とす段階を有する請求項１から５のいずれか１項に記載の方法。
【請求項７】
命令をストリーミングする段階は、前記命令プリフェッチバッファから命令を読み出し、前記命令をプロセッサパイプラインのデコード段階に供給する段階を有する請求項１から６のいずれか１項に記載の方法。
【請求項８】
プロセッサ上での電力消費を低下させる装置であって、
アドレッシング情報が対応付けられた分岐を予測する命令フェッチユニットと、
前記アドレッシング情報を命令プリフェッチバッファ内のエントリと比較して、前記命令プリフェッチバッファに実行可能な命令ループが存在するかを判定するループストリーム検出器ユニットと
を備え、
前記比較の結果、命令ループが検出されると、前記命令フェッチユニットおよび／または前記命令フェッチユニットのコンポーネントの電力を落とし、
クリア条件が検出されるまで、前記命令プリフェッチバッファから直接的に命令をストリーミングする
装置。
【請求項９】
前記アドレッシング情報は、カレントリニアインストラクションポインタ（ＣＬＩＰ）、分岐オフセット、および／または分岐対象アドレスを含む請求項８に記載の装置。
【請求項１０】
前記クリア条件は、誤予測された分岐を含む請求項８または９に記載の装置。
【請求項１１】
前記命令ループは、入れ子状命令ループを含む請求項８から１０のいずれか１項に記載の装置。
【請求項１２】
前記命令フェッチユニットの電力を落とすとき、命令キャッシュおよび／または命令デコードキャッシュの電力を落とす請求項８から１１のいずれか１項に記載の装置。
【請求項１３】
前記命令フェッチユニットの電力を落とすとき、分岐予測ユニット、次命令ポインタ、および／または命令変換ルックアサイドバッファ（ＩＴＬＢ）の電力を落とす請求項８から１２のいずれか１項に記載の装置。
【請求項１４】
命令をストリーミングするとき、前記命令プリフェッチバッファから命令を読み出し、前記命令をプロセッサパイプラインのデコード段階に供給する請求項８から１３のいずれか１項に記載の装置。
【請求項１５】
ディスプレイ装置と、
命令を記憶するメモリと、
前記命令を処理するプロセッサと
を備え、
前記プロセッサが、
アドレッシング情報が対応付けられた分岐を予測する命令フェッチユニットと、
前記アドレッシング情報を命令プリフェッチバッファ内のエントリと比較して、前記命令プリフェッチバッファに実行可能な命令ループが存在するかを判定するループストリーム検出器ユニットと
を有し、
前記比較の結果、命令ループが検出されると、前記命令フェッチユニットおよび／または前記命令フェッチユニットのコンポーネントの電力を落とし、
クリア条件が検出されるまで、前記命令プリフェッチバッファから直接的に命令をストリーミングする
コンピュータシステム。
【請求項１６】
前記アドレッシング情報は、カレントリニアインストラクションポインタ（ＣＬＩＰ）、分岐オフセット、および／または分岐対象アドレスを含む請求項１５に記載のコンピュータシステム。
【請求項１７】
前記クリア条件は、誤予測された分岐を含む請求項１５または１６に記載のコンピュータシステム。
【請求項１８】
前記命令ループは、入れ子状命令ループを含む請求項１５から１７のいずれか１項に記載のコンピュータシステム。
【請求項１９】
前記命令フェッチユニットの電力を落とすとき、命令キャッシュおよび／または命令デコードキャッシュの電力を落とす請求項１５から１８のいずれか１項に記載のコンピュータシステム。
【請求項２０】
前記命令フェッチユニットの電力を落とすとき、分岐予測ユニット、次命令ポインタ、よび／または命令変換ルックアサイドバッファ（ＩＴＬＢ）の電力を落とす請求項１５から１９のいずれか１項に記載のコンピュータシステム。
【請求項２１】
命令をストリーミングするとき、前記命令プリフェッチバッファから命令を読み出し、前記命令をプロセッサパイプラインのデコード段階に供給する請求項１５から２０のいずれか１項に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全体的に、コンピュータプロセッサの分野に関する。本発明は、特に、バッファ内の命令ループおよびその他の命令グループを検出し、それに応答してフェッチユニットの電力を落とす装置および方法に関する。
【背景技術】
【０００２】
最近の多くのマイクロプロセッサは、高速演算を促進する大型の命令パイプラインを有する。「フェッチ」されたプログラム命令は、パイプラインに入り、パイプラインの中間段階におけるデコード、実行等の演算が施され、パイプラインの終わりで「リタイヤ」される。パイプラインが有効な命令をクロックサイクルごとに受け取る場合、パイプラインは完全稼働し、性能は良好である。有効な命令をクロックサイクルごとに受け取らない場合、パイプラインは完全稼働せず、性能は落ちる。たとえば、性能トラブルは、プログラムコードにおける分岐命令により発生しうる。プログラムにおいて分岐命令に行き当たり、対象のアドレスに処理が分岐されると、命令パイプラインの一部をフラッシュしなければならないかもしれず、性能が損なわれる。
【０００３】
パイプラインの効率性に対する分岐命令の影響を低下させるべく、分岐対象バッファ（ＢＴＢ）が開発されている。ＢＴＢに関する議論は、Ｄａｖｉｄ  Ａ．ＰａｔｔｅｒｓｏｎおよびＪｏｈｎ  Ｌ．Ｈｅｎｎｅｓｓｙ著「コンピュータアーキテクチャ定量的アプローチ」２７１−２７５頁（第２版、１９９０年）に見つけることができる。図１は、典型的なＢＴＢアプリケーションを示しており、命令ポインタ（ＩＰ）１１８に接続されたＢＴＢ  １１０と、プロセッサパイプライン１２０とを示している。図１には、キャッシュ１３０およびフェッチバッファ１３２も含まれる。次にフェッチすべき命令の位置が、ＩＰ  １１８により特定される。プログラムの実行が順次に進むにつれ、ＩＰ  １１８はサイクルごとにインクリメントされる。ＩＰ  １１８の出力によって、キャッシュ１３０のポート１３４が駆動され、次の命令をフェッチするアドレスが特定される。キャッシュ１３０は、命令をフェッチバッファ１３２に供給し、フェッチバッファは、命令をプロセッサパイプライン１２０に供給する。
【０００４】
パイプライン１２０により受け取られると、命令はフェッチ段階１２２、デコード段階１２４、中間段階１２６（たとえば、命令実行段階）、およびリタイヤ段階１２８と示される数段階を進む。分岐命令によって分岐が実行されるかに関する情報は、リタイヤ段階１２８等のパイプラインの遅い段階になるまで得られない場合がある。ＢＴＢ  １１０がなく、分岐が実行される場合、フェッチバッファ１３２と、分岐命令より後の命令パイプライン１２０の部分とによって、間違った実行経路に行かないよう命令が保持される。プロセッサパイプライン１２０およびフェッチバッファ１３２における無効な命令はフラッシュされ、ＩＰ  １１８には分岐対象アドレスが書き込まれる。性能損失は、部分的には、フェッチバッファ１３２および命令パイプライン１２０が分岐対象アドレスから始まる命令で埋まっている間、プロセッサが待機状態に置かれることにより発生する。
【０００５】
分岐対象バッファ（ＢＴＢ）によって、実行される分岐による影響が低下する。ＢＴＢ  １１０は、分岐アドレス（ＢＡ）フィールド１１２および対象アドレス（ＴＡ）フィールド１１４をそれぞれが有する複数のレコード１１１を含む。ＴＡフィールド１１４には、対応するＢＡフィールド１１２に特定されたアドレスに存在する分岐命令からの分岐対象アドレスが保持される。プロセッサパイプライン１２０が分岐命令に遭遇すると、レコード１１１のＢＡフィールド１１２が検索され、分岐命令のアドレスに一致するレコードが検索される。見つかった場合、ＩＰ  １１８は、見つかったＢＡフィールド１１２に対応するＴＡフィールド１１４の値に変更される。その結果、以降の命令は、分岐対象アドレス以降からフェッチされる。
【０００６】
プロセッサパイプラインにおける電力節約は、特に、電池を電源とするラップトップおよびその他のモバイル装置にとっては重要である。したがって、フェッチバッファに繰り返し命令群（たとえば、入れ子状ループ）が存在する場合、命令フェッチ回路、命令キャッシュ等のプロセッサパイプラインの特定の部分の電力を落とすことは、利益に適っている。したがって、フェッチ回路もしくはその一部の電力を落としてよい条件を検出する新しい技術が有用である。
【図面の簡単な説明】
【０００７】
本発明のより良い理解は、以下の図面に関連付けられた以下の詳細な記載から得られるだろう。
【図１】分岐対象プリフェッチを実行する分岐対象バッファを採用した従来のプロセッサパイプラインを示す。
【図２】プリフェッチバッファから命令をストリーミングし、応答してプロセッサパイプラインのいくつかの部分の電力を落とすループストリーム検出器を含むプロセッサアーキテクチャの一実施形態である。
【図３】繰り返し命令分を検出し、それに応答してプロセッサパイプラインのくつかの部分の電力を落とす方法の一実施形態を示す。
【図４】ループストリーム検出器が稼働される一実施形態を示すパイプライン図である。
【図５】ループストリーム検出器を稼働させるのに使用されるプリフェッチバッファの一実施形態で用いられるフィールドを示す。
【図６】ループストリーム検出器を稼働させるのに使用されるプリフェッチバッファの別の実施形態で用いられるフィールドを示す。
【図７】入れ子状命令シーケンスを含む模範的なプログラムコードを示す。
【発明を実施するための形態】
【０００８】
以下の記載では、説明の目的において、数多くの特定的な詳細を明記して、以下に記載される本発明の実施形態の完全な理解を促す。しかし、本発明の実施形態は、これらの特定的な詳細がなくても実施しうることは、当業者には明らかであろう。他の例では、本発明の実施形態の基礎にある原理が曖昧にならないように、周知の構造および装置は、ブロック図形式で示す。
【０００９】
本発明の一実施形態は、ＣＰＵコアが入れ子状ループおよび／または入れ子状分岐等の繰り返し命令群を実行しているとき、ＣＰＵコアの動的電力を減らす。たとえば、分岐予測器により予測される命令群がプリフェッチバッファから検出されると、本発明の一実施形態は、フェッチユニットおよび関連する命令フェッチ回路（もしくはその一部）の電力を落として電力を節約する。その後、命令は、さらなる命令が必要になるまでは、プリフェッチバッファから直接的にストリーミングされ、さらなる命令が必要になったとき、命令フェッチユニットの電力が投入される。本発明の実施形態は、シングルスレッドおよびマルチスレッドの両方の環境で動作しうる。一実施形態においては、シングルスレッド環境では、プリフェッチバッファのエントリの全てが、シングルスレッドに割り当てられ、マルチスレッド環境では、プリフェッチバッファのエントリは、複数のスレッド間で均等に分割される。
【００１０】
一つの特定的な実施形態は、プリフェッチバッファを有し、繰り返し命令群を検出するループストリーム検出器（ＬＳＤ）を備える。ループストリーム検出器プリフェッチバッファは、マルチスレッドモードでは、エントリ６個分の深さ（スレッド−０に３個、スレッド−１に３個）を持ち、シングルスレッドモードでは、エントリ３個分の深さを持ってよい。または、シングルスレッドモードで、６個のエントリの全てをシングルスレッドに用いてもよい。一実施形態では、シングルスレッドモードにおいて、プリフェッチバッファにおけるエントリの数は、３または６に設定することができる。
【００１１】
一実施形態では、ループストリーム検出器プリフェッチバッファは、プリフェッチバッファに書き込まれる分岐対象バッファ（ＢＴＢ）予測分岐ごとに、カレントリニアインストラクションポインタ（ＣＬＩＰ）、オフセット、およびプリフェッチバッファの分岐対象アドレス読み出しポインタ等の分岐情報を記憶する。ＢＴＢが分岐を予測すると、その分岐のＣＬＩＰおよびオフセットがプリフェッチバッファのエントリと比較され、この分岐がすでにプリフェッチバッファに存在するかが判定される。一致するものが存在する場合、フェッチユニット、または、その一部、たとえば、命令キャッシュが停止され、クリア条件（たとえば、誤予測された分岐）に遭遇するまでは、プリフェッチバッファから命令がストリーミングされる。プリフェッチバッファの命令ループ内にＢＴＢ予測分岐が存在する場合、これらもプリフェッチバッファからストリーミングされる。一実施形態では、ループストリーム検出器は、直接分岐および条件付分岐に対して起動され、挿入フローおよび戻り／呼び出し命令に対しては起動されない。
【００１２】
入れ子状ループ、分岐、およびその他の繰り返し命令群がプリフェッチバッファから検出されたことに応じてフェッチユニット（および／またはその他の回路）の電力を落とすプロセッサアーキテクチャの一実施形態を図２に示す。図示されるように、この実施形態は、本明細書に記載される多様な機能を実行するループストリーム検出器ユニット２００を備える。特に、ループストリーム検出器２００は、分岐対象バッファ（ＢＴＢ）により予測された分岐をプリフェッチバッファ２０１内のエントリと比較する比較回路２０２を有する。上記したように、本発明の一実施形態では、ループストリーム検出器２００は、プリフェッチバッファ内から一致するものが検出されると、それに応答して、命令フェッチユニット２１０（もしくはその一部）の電力を落とす（図２にオン／オフ線で示す）。
【００１３】
ループストリーム検出器からの信号に応答して、分岐予測ユニット２１１、次命令ポインタ２１２、命令変換ルックアサイドバッファ（ＩＴＬＢ）、命令キャッシュ２１４、および／またはプリデコードキャッシュ２１５等の命令フェッチユニット２１０の多様な周知のコンポーネントの電力を落としてよく、これにより、プリフェッチバッファ内に繰り返し命令群が検出された場合の電力量が大幅に節約される。以降は、命令はプリフェッチバッファから直接的に、命令パイプラインの残りの段階、たとえば限定としてではなく例示として挙げると、デコード段階２２０、実行段階２３０等にストリーミングされる。
【００１４】
図３は、命令バッファ内から命令群（たとえば、入れ子状ループ）が検出されたことに応答して、フェッチユニット（もしくはその一部）の電力を落とす方法の一実施形態を示す。本方法は、図２に示すプロセッサアーキテクチャ、または、別のプロセッサアーキテクチャを用いて実施してよい。
【００１５】
３０１で、分岐命令が予測され、分岐命令のカレントリニアインストラクションポインタ（ＣＬＩＰ）、分岐オフセット、および／または分岐対象アドレスが判別される。３０２で、ＣＬＩＰ、分岐オフセット、および／または分岐対象アドレスが、プリフェッチバッファ内のエントリと比較される。一実施形態では、比較は、入れ子状ループがプリフェッチバッファ内に記憶されているかを判定することを目的とする。一致するものが見つかったと３０３で判定されると、３０４で、命令フェッチユニット（および／またはその各コンポーネント）が停止され、３０５で、命令がプリフェッチバッファから直接的にストリーミングされる。命令は、３０６でクリア条件（たとえば、誤予測された分岐）が発生するまで、プリフェッチバッファからストリーミングし続けられる。
【００１６】
図４は、本発明の一実施形態に係るループストリーム検出器が稼働される様子を示す。具体的には、図４では、命令パイプラインのＩＦ２＿Ｌ段階で予測器により分岐が予測され（ＢＴクリア）、次命令ポインタ（ＩＰ）多重化段階が、バブルにより予測された分岐対象アドレスにリダイレクトされる。段階ＩＤ１で、ＣＬＩＰ、分岐オフセット、および対象読み出しポインタ（分岐対象を指定するポインタ）がプリフェッチバッファに記録される。ＣＬＩＰ、分岐オフセット、および／または対象読み出しポインタの一致が検出されたことに応答して、ループストリーム検出器が稼働され、一実施形態では、フェッチユニットがディセーブルされる。これは図４の下部に示されており、ＣＬＩＰの比較および分岐オフセットの比較が行われ、ループストリーム検出器ロックが設定され、（それによりフェッチユニットおよび／またはその一部の電力が落とされる）ことが示されている。
【００１７】
図５は、ループストリーム検出器を稼働するのに使用される複数のフィールドを有するループスストリーム検出器プリフェッチバッファの一実施形態の構成を示し、図７は、図５に示す例のループストリーム検出器について用いられる模範的な命令シーケンスを示す。便宜を図るべく、模範的な命令シーケンスを以下にも示す。ＬＳＤプリフェッチバッファ内で使用されるフィールドとしては、プリフェッチバッファエントリナンバー５０１（この特定的な例では、０から５までの６個のＰＦＢエントリが存在する）、カレントリニアインストラクションポインタ（ＣＬＩＰ）５０２、分岐オフセットフィールド５０３、対象読み出しポインタフィールド５０４、およびエントリ有効フィールド５０５がある。
【００１８】
図に示されるように、カレントリニアインストラクションポインタ（ＣＬＩＰ）が０ｘ１２０ｈのところで分岐を有するループがフェッチユニットにより展開されてプリフェッチユニットに書き込まれるとき、書き込まれるＣＬＩＰおよび分岐オフセットは各ＰＦＢエントリの有効ＣＬＩＰフィールドおよび分岐オフセットフィールドと比較される。比較に応じて、図に示すように、有効ビットがＰＦＢエントリ３に設定される。さらに、ＰＦＢエントリ３にはリダイレクトＰＦＢ読み出しポインタが記録され、ＰＦＢからの命令のストリーミングがイネーブルされる。一実施形態では、以下の動作が実行される。
（１）分岐が予測される。
（２）ＣＬＩＰおよびオフセットがＰＦＢの既存のエントリと比較される。
（３）ＰＦＢのＬＳＤ構造のエントリのうち１つ（図の例では、エントリ０）と一致すると、エントリ０のＰＦＢ対象読み出しＰｔｒフィールドがＬＳＤ構造のエントリ３に複写され、ＰＦＢエントリの書き込みのときにエントリ有効ビットが設定される。一実施形態では、ＰＦＢエントリは、１６バイトのキャッシュラインデータと、マクロ命令の終わりを示す１バイトあたり１個のプリデコードビットとを含む。
（４）ＰＦＢ読み出しポインタがエントリ３に到達すると、ＰＦＢ対象読み出しポインタおよび有効ビットを含むエントリ３の情報の全てを読み出すべく、ＰＦＢ読み出しポインタが用いられる。
（５）有効ビットに基づいて、順番では次にあるＰＦＢエントリ４を読み出すかわりに、対象読み出しポインタを用いるエントリ１にリダイレクトされる。
（６）ＰＦＢエントリが、エントリ１、エントリ２、エントリ３の順に読み出される。
（７）エントリ３で、ＰＦＢ有効ビットが読み出され、ＰＦＢは対象読み出しポインタを用いて次のＰＦＢエントリを読み出す。
（８）段階６および７が繰り返される。
【表１】
2013541758.tif 000003
【００１９】
一実施形態では、各ＰＦＢエントリが、ＰＦＢからストリーミングされる命令を含む完全な１６バイトキャッシュラインを含む。キャッシュラインローデータ（ｒａｗ  ｄａｔａ）とともに、プリデコードビットと、分岐命令の最終バイトを示すＢＴＢマーカとが、ＰＦＢにさらに記憶される。プリデコードビットは、プリデコードキャッシュ２１５に記憶される。プリデコードキャッシュには、１バイト当たり１ビットのキャッシュラインが存在する。このビットは、マクロ命令の終わりを示す。ＢＴＢマーカも１バイト当たり１ビットで分岐命令の最終バイトを示す。ＰＦＢエントリに書き込まれる１６バイトキャッシュラインには、最大１６個までの命令が含まれうる。ＢＴＢ予測分岐命令については、分岐対象の命令を含むキャッシュラインは、常に、ＰＦＢにおいて順番が次のエントリに書き込まれる。一実施形態では、４：１マルチプレクサ（４：１ＭＵＸ）が設けられ、その出力がＰＦＢエントリの読み出しに用いられる。ＭＵＸへの入力は、（１）通常、ＰＦＢエントリから命令をストリーミングし、エントリからすべての命令をストリーミングしたとき、値が進むＰＦＢ読み出しポインタ、（２）分岐命令がＰＦＢエントリからストリーミングされるときの分岐対象ＰＦＢ読み出しポインタ、（３）誤予測分岐等のクリア条件後のＰＦＢ読み出しポインタ（常に、第１ＰＦＢエントリをポイントする）、および（４）ＬＳＤの稼働によるＰＦＢ対象読み出しポインタ、である。
【００２０】
図６は、ＰＦＢ  ＬＳＤの別の実施形態を示すが、ＬＳＤフィールドのエントリの数は、ＰＦＢエントリの数より小さく、電力／面積が削減される。具体的には、この例では、ＬＳＤフィールドには４個のエントリ（ＬＳＤエントリナンバー０から３）があり、ＰＦＢフィールドには６個のエントリ（ナンバー０から５）がある。各ＰＦＢエントリにおけるヘッドポインタ値は、フェッチユニットの予測器により予測された分岐命令に対応付けられたＬＳＤエントリをポイントするべく用いられる。たとえば、ヘッドポインタ０００１は、ＬＳＤエントリナンバー０をポイントし、ヘッドポインタ００１０は、ＬＳＤエントリナンバー１をポイントし、ヘッドポインタ０１００はＬＳＤエントリナンバー２をポイントし、ヘッドポインタ１０００は、ＬＳＤエントリナンバー３をポイントする。ヘッドポインタ値００００は、ＰＦＢエントリが、ＬＳＤエントリをポイントするＢＴＢ予測分岐を有さないことを示す。したがって、（１）一致するＣＬＩＰおよび分岐オフセットが検出された場合、および、（２）一致するＬＳＤエントリに、ＰＦＢエントリのいずれかから自身をポイントする対応する有効ヘッドポインタがある場合、プリフェッチバッファで一致が検出される。一実施形態では、ＰＦＢエントリのヘッドポインタのビット[０]は、論理和演算され、一致すると認識される。（３）一実施形態では、ＰＦＢのＬＳＤ構造のエントリのうち１つと一致する場合、一致するエントリのＰＦＢ対象読み出しＰｔｒフィールドが、ＰＦＢのうちＢＴＢ予測を含む対応キャッシュラインが書き込まれているエントリに複写される。さらに、ＢＴＢ予測分岐命令を有する現在書き込まれているＰＦＢエントリに、ＬＳＤ有効ビットが設定される。（４）ＰＦＢ読み出しポインタがＬＳＤ有効ビットが設定されたエントリに到達すると、ＰＦＢ読み出しポインタを用いて、ＰＦＢ対象読み出しポインタおよびＬＳＤ有効ビットを含む全ての情報がエントリから読み出される。（５）ＬＳＤ有効ビットに基づいて、順番では次にあるＰＦＢエントリを読み出すかわりに、対象読み出しポインタを用いるエントリにリダイレクトされる。（６）次に、ＰＦＢ有効ビットを含むエントリが読み出されるまで、ＰＦＢエントリが順番に読み出され、ＰＦＢは対象読み出しポインタを用いて次のＰＦＢエントリを読み出す。（７）上記の動作５および６が繰り返される。
【００２１】
本発明の一実施形態では、本発明の実施形態が実施されるプロセッサは、インテル（登録商標）コーポレーションにより設計されたＡｔｏｍ（登録商標）プロセッサ等の低電力プロセッサを含む。しかし、本発明の根底にある原理は、なんらかの特定的なプロセッサアーキテクチャに限定されない。たとえば、本発明の根底にある原理は、インテル社により設計されたコアｉ３、ｉ５、および／またはｉ７プロセッサ等の多様なプロセッサアーキテクチャ上、または、スマートホン、および／またはその他の携帯型コンピュータ装置に用いられる多様な低電力システム・オン・チップ（ＳｏＣ）アーキテクチャ上で実施してよい。
【００２２】
図８は本発明の実施形態を実施してよい模範的なコンピュータシステム８００を示す。コンピュータシステム８００は、情報を伝達するシステムバス８２０、およびバス８２０に接続され、情報を処理するプロセッサ８１０を備える。コンピュータシステム８００は、バス８２０に接続され、情報およびプロセッサ８１０により実行される命令を記憶するランダムアクセスメモリ（ＲＡＭ）もしくはその他の動的記憶装置８２５（本明細書では、メインメモリと呼ぶ）をさらに備える。メインメモリ８２５は、プロセッサ８１０により命令が実行されている間、一時的な変数もしくはその他の中間的な情報を記憶するのにも用いられうる。コンピュータシステム８００は、バス８２０に接続され、プロセッサ８１０により使用される静的情報および命令を記憶する読み出し専用メモリ（ＲＯＭ）および／またはその他の静的記憶装置８２６をさらに備えてよい。
【００２３】
磁気ディスクもしくは光ディスク等のデータストレージ装置８２７およびそれに対応するドライブも、情報および命令を記憶するべくコンピュータシステム８００に接続してよい。コンピュータシステム８００は、Ｉ／Ｏインターフェース８３０を介して第２Ｉ／Ｏバス８５０に接続することもできる。ディスプレイ装置８４３、入力装置（たとえば、英数字入力装置８４２および／またはカーソル制御装置８４１）等の複数のＩ／Ｏ装置をＩ／Ｏバス８５０に接続してよい。
【００２４】
通信装置８４０は、ネットワークを介してその他のコンピュータ（サーバまたはクライアント）にアクセスし、多様な種類のデータをアップロード／ダウンロードするべく用いられる。通信装置８４０は、モデム、ネットワークインターフェースカード、または、イーサネット（登録商標）、トークンリング、もしくはその他の種類のネットワークに接続するために用いられるもの等のその他の周知のインターフェース装置等であってよい。
【００２５】
図９は、本発明のいくつかの実施形態で用いられうる別の模範的なデータ処理システムを示すブロック図である。たとえば、データ処理システム９００は、ハンドヘルドコンピュータ、携帯情報端末（ＰＤＡ）、移動体電話、携帯ゲームシステム、携帯メディアプレーヤ、ならびに、移動体電話、メディアプレーヤ、および／もしくは、ゲームシステムであってよいタブレットもしくはハンドヘルドコンピューティング装置等であってよい。別の例では、データ処理システム９００は、ネットワークコンピュータ、または、別の装置に組み込まれた処理装置であってよい。
【００２６】
本発明の実施形態によると、データ処理システム９００の模範的アーキテクチャを、上記の移動体装置に用いてよい。データ処理システム９００は、集積回路上に１つ以上のマイクロプロセッサおよび／またはシステムを有してよい処理システム９２０を備える。処理システム９２０は、メモリ９１０、電源９２５（１つ以上の電池を含む）、オーディオ入出力９４０、ディスプレイコントローラおよびディスプレイ装置９６０、任意の入出力９５０、入力装置９７０、ならびに無線送受信機９３０に接続される。図９には示されないさらなるコンポーネントを、本発明の所定の実施形態においてデータ処理システム９００の一部としてよく、本発明の所定の実施形態では、図９に示すよりも少ないコンポーネントを含めてよい。さらに、図９に示されない１つ以上のバスを用いて、当技術分野で周知の通りに、多様なコンポーネントを相互接続してよい。
【００２７】
メモリ９１０は、データおよび／またはデータ処理システム９００により実行されるプログラムを記憶してよい。オーディオ入出力９４０は、マイクおよび／またはスピーカを含んでよく、それにより、スピーカおよびマイクを介して、たとえば、音楽の再生、および／または、電話機能の提供を行ってよい。ディスプレイコントローラおよびディスプレイ装置９６０は、グラフィカルユーザインターフェース（ＧＵＩ）を含んでよい。無線（たとえば、ＲＦ）送受信機９３０（たとえば、ワイファイ送受信機、赤外線送受信機、ブルートゥース（登録商標）送受信機、無線形態電話送受信機等）は、その他のデータ処理システムと通信するべく用いてよい。１つ以上の入力装置９７０は、ユーザがシステムに入力を行えるようにする。これらの入力装置は、キーパッド、キーボード、タッチパネル、マルチタッチパネル等であってよい。任意のその他の入出力９５０は、ドックのコネクタであってよい。
【００２８】
本発明のその他の実施形態は、携帯電話、ページャ（たとえば、ソフトウェアがマイクロチップに埋め込まれている）、ハンドヘルドコンピューティング装置（たとえば、携帯情報端末、スマートホン）、および／または、プッシュホン式電話上で実施してよい。しかし、本発明の根底にある原理は、なんらかの特定の種類の通信装置もしくは通信媒体に限定されないことは理解されるべきである。
【００２９】
本発明の実施形態は、上記した多様な段階を含みうる。段階は、汎用もしくは専用のプロセッサに実行されるべく用いられてよい機械可読命令として実施してよい。または、これらの段階は、段階を実行するためのハードワイヤードロジックを含む特定のハードウェアコンポーネントにより、または、プログラムされたコンピュータコンポーネントおよびカスタマイズしたハードウェアコンポーネントの任意の組み合わせにより、実行してよい。
【００３０】
本発明の要素は、処理を実行するようコンピュータ（もしくはその他の電子装置）をプログラムするべく用いてよい命令を記憶した機械可読媒体であってよいコンピュータプログラムプロダクトとして提供してよい。機械可読媒体は、フロッピー（登録商標）ディスケット、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、ＲＯＭ，ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気もしくは光カード、伝搬媒体、もしくは、電子的命令を記憶するのに適したその他の種類の媒体／機械可読媒体であってよいが、これらに限定されない。たとえば、本発明は、コンピュータプログラムプロダクトとしてダウンロードしてよく、プログラムは、遠隔コンピュータ（たとえば、サーバ）から要求元コンピュータ（たとえば、クライアント）に、通信リンク（たとえば、モデムもしくはネットワーク接続）を介して、搬送波もしくはその他の伝搬媒体に重畳されたデータ信号として転送される。
【００３１】
詳細な記載の全体を通して、説明の目的において、数多くの特定的な詳細を明記して、本発明を完全に理解できるようにした。しかし、これらの特定的な詳細のいくつかが無くても、本発明を実施しうることは当業者には明らかであろう。所定の例では、本発明の主題が曖昧にならないように、周知の構造および機能については、詳細に記載しなかった。したがって、本発明の範囲および趣旨は、以下の特許請求の範囲によって判断されるべきである。
【図１】
2013541758.tif 000004
【図２】
2013541758.tif 000005
【図３】
2013541758.tif 000006
【図４】
2013541758.tif 000007
【図５】
2013541758.tif 000008
【図６】
2013541758.tif 000009
【図７】
2013541758.tif 000010
【図８】
2013541758.tif 000011
【図９】
2013541758.tif 000012
【国際調査報告】
2013541758.tif 000013
2013541758.tif 000014