(57)【要約】【課題】データエントリをバッファから廃棄するか否かを決定するシステムを提供する。【解決手段】システムは、データエントリを受信するように構成されたバッファ４２５と、事前復号論理装置４５０と、廃棄論理装置４３５とを含む。事前復号論理装置４５０は、データエントリに対する第１のセットの廃棄条件に対応する第１の情報を受信し、第１の情報に基づいてデータエントリに対する事前復号された廃棄情報を発生するように構成される。廃棄論理装置４３５は、事前復号された廃棄情報と、データエントリに対する第２のセットの廃棄条件に対応する第２の情報とを受信し、事前復号された廃棄情報及び第２の情報に基づいてデータエントリを廃棄するか否かを決定するように構成される。【選択図】      図４
2006059350.tif 000002
【特許請求の範囲】
【請求項１】
データエントリを受信するように構成されたバッファと、事前復号論理装置と、廃棄論理装置とを具備するシステムであって、
前記事前復号論理装置は、
前記データエントリに対する第１のセットの廃棄条件に対応する第１の情報を受信し、
前記データエントリを前記バッファ中に記憶するのに先立って、前記第１の情報に基づいて前記データエントリに対する事前復号された廃棄情報を発生するように構成され、
前記廃棄論理装置は、
前記事前復号された廃棄情報と、前記データエントリに対する第２のセットの廃棄条件に対応する第２の情報とを受信し、
前記事前復号された廃棄情報及び前記第２の情報に基づいて前記データエントリを廃棄するか否かを決定するように構成される、システム。
【請求項２】
前記事前復号された廃棄情報は前記バッファとは分離された別のメモリ区域に記憶され、前記事前復号された廃棄情報は前記事前復号された廃棄情報と前記データエントリとの関係を示す情報と共に記憶される請求項１に記載のシステム。
【請求項３】
１以上の外部事象を監視し、前記外部事象に従って前記事前復号された廃棄情報を変更するように構成される外部事象処理論理装置を更に具備し、前記１以上の外部事象は、スヌープ動作、アドレス変換情報の更新、及びデータの有効性の情報の更新からなるグループから選択される請求項１に記載のシステム。
【請求項４】
前記事前復号論理装置は、
前記データエントリを前記バッファ中に記憶する前に、前記第１の情報の第１のサブセットに基づいて前記事前復号された廃棄情報を発生する第１のコンポーネントと、
前記データエントリを前記バッファ中に記憶した後に、前記第１の情報の第２のサブセットに基づいて前記事前復号された廃棄情報を更新する第２のコンポーネントと、
を具備する請求項１に記載のシステム。
【請求項５】
前記第２のコンポーネントは、前記データエントリをバッファ中に記憶した後に、前記事前復号された廃棄情報と前記第１の情報の第２のサブセットに基づいて、前記事前復号された廃棄情報を更新する請求項４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データエントリのバッファデータの廃棄（retirement）条件の処理を最適化するためのシステム及び方法に関する。特に本発明は、データエントリがバッファから廃棄することを考慮する準備ができる前に少なくともバッファデータ廃棄条件の一部を処理し、データエントリの更に高速度で更に効率的な廃棄を可能にするシステム及び方法に関する。
【背景技術】
【０００２】
デジタル回路において、待ち行列とも呼ばれるメモリバッファがしばしば使用される。メモリバッファは、ある装置から別の装置への転移されるデータの一時的な保持領域である。通信装置はしばしば異なる速度でデータを処理し、その結果として、中間バッファなしでは、これらの装置間の通信が困難となり、不可能でさえもありうる。ある装置ではデータの送信の準備ができ、受信装置ではデータの受信の準備がまだできていないならば、受信装置がデータを受取る準備ができるまで、データが装置間のバッファに一時的に記憶される。
【０００３】
メモリバッファは、プロセッサ、ＲＡＭ、ハードディスク等のような装置間の通信を容易にすることができる。ほとんどのキーボードは、キーストロークを一時的に記憶するためのメモリバッファを有する。ほとんどのプリンタは、印刷される文書を待ち行列に入れるためのバッファを有する。メモリバッファはまた、例えばソフトウェアプログラムとオペレーティングシステムとの間の通信を容易にするためのバッファとして作用するように、コンピュータシステムのＲＡＭの一部を割当てることによってソフトウェアプログラムに対して形成されることができる。メモリバッファはまた、ソフトウェアプログラムと装置との間に設けることもできる。ＣＤ書込みプログラムは、例えばデータがＣＤに書込まれる前にデータを一時的に記憶するために、書込みプロセスの間にＲＡＭにメモリバッファを形成する。
【０００４】
典型的には、エントリは、まずバッファ中に記憶（登録）され、その後、ある条件が満たされるならば、除去（廃棄）される。簡単な先入れ先出し待ち行列（ＦＩＦＯ）のような非常に簡単なバッファでは、データエントリは、データが適切に受信装置に送信された後、バッファから廃棄されることができる。しかしながら、デジタル回路及び装置が更に複雑になると、データエントリをバッファから廃棄することができる前に、満たさなければならない条件の数は非常に増加する。例えば、複雑なマルチプロセッサシステムでは、データエントリをプロセッサの記憶またはロード待ち行列から廃棄することができる前に、満たさなければならない条件は１０以上である。
【０００５】
増加した数の廃棄条件を処理するため、多レベルの深さである複雑な論理装置が必要とされる。更に、データエントリが廃棄されることが論理装置により決定されたならば、付加的な論理装置は、その目的としてデータの廃棄を容易にするために、多数の出力を発生しなければならない。例えば、データエントリの転送は、書込みリクエストの生成、ポインタの更新、カウンタのインクリメント等を必要とする。これらの付加的な要求は更に論理装置の複雑度を増加させる。
【０００６】
典型的には、データエントリはある頻度で待ち行列から廃棄されることが望ましい。例えばクロックサイクル毎にエントリを廃棄することが望ましい。しかしながら、廃棄論理装置が更に複雑になるので、データエントリを廃棄されるか否かについて決定するのに必要な時間は増加する。それ故、廃棄論理装置は、特に、待ち行列エントリをクロックサイクル毎に廃棄することを必要とする、高クロック周波数の高性能システムでは問題点となる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
それ故、データエントリをバッファから廃棄するか否かを決定する効率を増加することのできるシステム及び方法が必要とされている。そのシステム及び方法は、廃棄条件を効率的に、必要な時間（例えば１サイクル）内で処理できなければならず、それによって高速度システムの性能が影響を受けないようにしなければならない。
【課題を解決するための手段】
【０００８】
概説した１以上の問題は本発明の種々の実施形態により解決されることができる。概略的に説明すれば、本発明はデータエントリをバッファから廃棄するか否かを決定するシステム及び方法を含む。廃棄条件の一部はデータエントリの廃棄が考慮されるのに先立って評価される。その結果として、データエントリが廃棄について考慮されるときに残っている評価されるべき条件の数（及び評価に必要な時間）は大幅に減少し、所望の時間（例えば１クロックサイクル）内に廃棄の決定が完了することを可能にする。
【０００９】
本発明の１実施形態によれば、廃棄条件の一部はデータエントリがバッファに記憶される前に処理されることができる。中間的な結果は、バッファ中に対応するデータエントリを有する事前復号（predecode）されたバッファデータ廃棄条件データとして記憶されることができる。１実施形態では、データエントリがバッファに記憶される間に変化しない（または変化のないことが予測される）廃棄条件は、データエントリがバッファに記憶される前に処理される条件である。データエントリがバッファ中に記憶される前に廃棄条件の一部を処理することにより、データエントリの廃棄が考慮されるときに残りの廃棄条件を処理するために必要な論理装置の複雑度（及び対応する論理レベルの数）を顕著に減少させることができる。
【００１０】
別の実施形態では、データエントリがバッファ中を進行している間に、廃棄条件の一部が評価されることができる。この方法で廃棄条件を予め処理することにより、複雑度の付加的なレベルを最終的な廃棄論理装置から消去することができる。データエントリがバッファ中に係属している間に処理するように選択された廃棄条件は、比較的静止状態であるか、或いはそれらはデータエントリがバッファに記憶されたときに変化する可能性があるが、その後に変化する可能性が少ないと考えられた条件である。
【００１１】
本発明の別の実施形態は、バッファ、事前復号論理装置、廃棄論理装置を具備する。事前復号論理装置は、データエントリの第１の組の廃棄条件に対応する情報を受信し、この情報に基づいてデータエントリの事前復号された廃棄情報を発生するように構成される。廃棄論理装置は、事前復号された廃棄情報と、データエントリの第２の組の廃棄条件に対応する情報とを受信するように構成される。廃棄論理装置は、事前復号された廃棄情報及び付加的な情報に基づいて、データエントリを廃棄するか否かを決定するように構成される。
【００１２】
本発明の更に別の実施形態は方法に関するものであり、その方法は、データエントリの第１の組の廃棄条件に対応する情報を受信し、この情報に基づいてデータエントリの事前復号された廃棄情報を発生する工程を含む。この方法は、更に事前復号された廃棄情報と、データエントリの第２の組の廃棄条件に対応する付加的な情報とを受信し、事前復号された廃棄情報及び付加的な情報に基づいて、データエントリを廃棄するか否かを決定する工程を含む。
【００１３】
多数の付加的な実施形態も可能である。
【００１４】
本発明の種々の実施形態は従来技術にまさる多くの利点を提供することができる。第１に、データエントリを廃棄するか否かの決定に必要な時間を著しく減少させることができ、それによって高速プロセッサの干渉のない実行を可能にする。同様の利点は他の実施形態でも与えられ、データエントリの廃棄について考慮される時間前に廃棄条件を評価するための他の処理を含む。
【発明を実施するための最良の形態】
【００１５】
本発明のその他の目的及び利点は、以下の詳細な説明を読み、添付図面を参照して更に明白になるであろう。  
本発明は種々の変形及び別の形態が可能であるが、その特定の実施形態を図面に例示し詳細な説明によって示す。しかしながら、このような図面及び詳細な説明は、記載された特定の実施形態に本発明を限定する意図はないことを理解すべきである。この開示は、特許請求の範囲に規定されている本発明の技術的範囲内に入る全ての変形、等価、代替をカバーすることを意図している。
【００１６】
本発明の１以上の実施形態を以下説明する。以下説明するこれら及び任意の他の実施形態は例示であり、発明を限定するものではなく、本発明の例示することを意図していることに注意すべきである。
【００１７】
概説すると、本発明はデータエントリをバッファから廃棄するか否かを決定するためのシステム及び方法を含んでおり、ここで、廃棄条件の一部はデータエントリの廃棄が考慮される前に評価される。結果として、データエントリが廃棄されるときに残っている評価されるべき条件の数（及び評価に必要な時間）は大幅に減少し、高速度システムで所望の時間（例えば１クロックサイクル）内に廃棄の決定が完了することを可能にする。
【００１８】
本発明の１実施形態によれば、廃棄条件の一部はデータエントリがバッファに記憶される前に処理されることができる。中間的な結果は対応するデータエントリと共にバッファ中に事前復号されたバッファデータ廃棄条件データとして記憶されることができる。１実施形態では、データエントリがバッファに記憶される間に変化しない（または変化のないことが予測される）廃棄条件はデータエントリがバッファ中に記憶される前に処理される条件である。データエントリがバッファに記憶される前に廃棄条件の一部を処理することによって、データエントリの廃棄が考慮されるときに残っている廃棄条件を処理するために必要な論理装置の複雑度（及び対応する論理装置レベルの数）が著しく減少される。
【００１９】
別の実施形態では、データエントリがバッファ中を進行している間に、廃棄条件の一部が評価されることができる。この方法で廃棄条件を予め処理することにより、論理ゲートの１以上のレベルを最終的な廃棄論理装置から消去することができる。データエントリがバッファ中に係属している間に処理するように選択された廃棄条件は、比較的静止状態であるか、或いはそれらはデータエントリがバッファ中に記憶されたときに変化する可能性があるが、後に変化の可能性が少なくなると考えられた条件である。
【００２０】
本発明の種々の実施形態は従来技術にまさる多数の利点を提供できる。第１に、データエントリを廃棄するか否かの決定に必要な時間を著しく減少させることができ、それによって高速度のプロセッサの干渉のない実行を可能にする。同様の利点は他の実施形態でも与えられ、データエントリが廃棄について考慮される時間の前に廃棄条件を評価するための他の処理を含む。
【００２１】
図１を参照すると、従来技術に従って、データエントリをバッファ中に記憶し、そのデータエントリの廃棄が準備されると、バッファから廃棄するように構成されるシステムを示すブロック図が示される。バッファ１２５はプロセッサのパイプライン１１５とＬ２キャッシュ１４０との間にインターフェースを設定するように構成される。他の実施形態では、バッファは２つの他のタイプの装置間のインターフェースを行うように構成されることができる。パイプライン１１５は、データエントリ１１０のようなデータを受信し、そのデータを処理し、処理されたデータをバッファ１２５へ記憶するように構成される。パイプライン制御ユニット１２０、バッファ制御ユニット１３０、キャッシュ制御ユニット１４５は、パイプライン１１５、バッファ１２５、Ｌ２キャッシュ１４０をそれぞれ制御し、これらの装置間の通信を制御するように構成される。
【００２２】
バッファ１２５に記憶される各データエントリは、データをバッファ１２５から廃棄することを考慮するまでバッファ中を進行する。バッファデータ廃棄条件ユニット１３５は多数の廃棄条件に従って、廃棄を考慮されるデータエントリを廃棄できるか否かを決定するように構成される。バッファデータ廃棄条件ユニット１３５は、バッファ制御ユニット１３０の一部とするか、バッファ制御ユニット１３０とは別のユニットとすることができる。
【００２３】
バッファデータ廃棄条件ユニット１３５がバッファ１２５中のデータエントリを廃棄できることを決定する場合、バッファデータ廃棄条件ユニット１３５は、データエントリの廃棄を促すために必要な適切な信号を発生し出力するように構成される。
【００２４】
図２を参照すると、１実施形態によるデータエントリをバッファから廃棄できるか否かを決定するように構成されるバッファデータ廃棄条件ユニットを示すブロック図が示される。バッファデータ廃棄条件ユニット２１０は、データ廃棄情報に関連する多くの信号を受信し、これらの信号を処理し、それによって廃棄を考慮しているデータエントリをバッファから廃棄できるか否かを決定するように構成される。バッファデータ廃棄条件ユニット２１０は、データエントリの廃棄が考慮されているとき、廃棄情報を受信し処理するように構成される。
【００２５】
バッファデータ廃棄条件ユニット２１０により処理される廃棄情報は、スタチックな廃棄情報２１５とダイナミックな廃棄情報２２０とを含むことができる。スタチックな廃棄情報は、データエントリがバッファに記憶された後、変化されない状態である可能性が非常に高い情報（データが有効であるか、アドレスが有効である等）を含む。他方で、ダイナミックな廃棄情報は、データエントリがバッファを伝播中であるときに変化する可能性が非常に高い情報（低いレベルのメモリの利用可能性、ロード／記憶の古さ等）を含む。この通常のシステムでは、全ての廃棄情報は、それがスタチック、ダイナミック、半ダイナミック等に関係なく、データエントリの廃棄が考慮されるとき、バッファデータ廃棄条件ユニット２１０に供給される。
【００２６】
バッファデータ廃棄条件ユニット２１０は更に、それがデータエントリの廃棄条件が満たされたことを決定したとき、バッファからのデータの廃棄に関連する必要とされる出力信号２２５を発生するように構成される。バッファデータ廃棄条件ユニット２１０は、例えばデータエントリの廃棄を容易にするために、書込みを可能にし、ポインタを変更し、カウンタを増加するように構成されることもできる。
【００２７】
図３を参照すると、従来技術に従って、バッファデータ廃棄条件の論理回路のブロック図が示される。この論理回路は入力３１０から信号を受信するように構成され、これはデータエントリをバッファから廃棄するか否かを決定するために評価されなければならない条件を表す。
【００２８】
廃棄論理装置３２０は入力３１０を受信するように構成され、一連の論理ゲートを通って入力を処理した後、廃棄決定３３０を発生する。廃棄決定３３０はバッファ中のデータエントリを廃棄すべきであるか否かについての決定を表す。入力が多数であるために、論理ゲートの複雑な回路が必要とされる。
【００２９】
入力３１０の例は、命令のタイプ、有効なデータ、無効にされたエントリ、有効なアドレス、ページ属性、Ｌ１キャッシュヒット、Ｌ１キャッシュタイムスロットの利用可能性、Ｌ２キャッシュインターフェース待ち行列の有効性、エントリの古さ、同期動作の確認等を含むことができる。１実施形態では、命令のタイプに応じて、論理条件の異なるセットがデータエントリを廃棄すべきであるか否かを評価するために使用されることができる。
【００３０】
図４を参照すると、本発明の１実施形態に従って、データエントリをバッファに記憶し、対応するデータエントリと共にバッファに事前復号された廃棄データを記憶するように構成されるシステムのブロック図が示される。このシステムは構造において図１のシステムに類似している。しかしながら、データエントリがバッファ４２５の最後に廃棄を考慮されているとき、データ廃棄条件を処理するのに必要な時間を減少させるために、付加的なユニット（事前復号バッファデータ廃棄条件ユニット４５０）が導入されている。
【００３１】
事前復号バッファデータ廃棄条件ユニット４５０は、パイプライン４１５からデータエントリがバッファ４２５に記憶される前に、データエントリに関連する廃棄条件の少なくとも一部を評価するように構成される。１実施形態では、事前復号バッファデータ廃棄条件ユニット４５０は、データエントリがバッファ４２５中に記憶された後に変更される可能性が低いか全くない廃棄情報を受取るように構成される。
【００３２】
事前復号バッファデータ廃棄条件ユニット４５０はバッファ４２５に記憶される各データエントリに対応する事前復号された廃棄情報を発生するように構成される。事前復号された廃棄情報は対応するデータエントリと共にバッファ４２５に記憶され、後にデータエントリの廃棄が考慮されるとき、バッファデータ廃棄条件ユニット４３５により読取られる。バッファデータ廃棄条件ユニット４３５はデータエントリをバッファ４２５から廃棄するか否かについての最終決定を行うために付加的な廃棄情報と共に、事前復号された廃棄情報を使用する。
【００３３】
図４の実施形態では、例えば各バッファエントリはデータエントリを記憶するためのデータエントリ部分４６０と、データエントリに対応する事前復号された廃棄情報を記憶するための事前復号された廃棄情報部分４６５とを含む。他の実施形態では、事前復号された廃棄情報は、廃棄情報を対応するデータエントリに接続している情報と共に他の記憶区域に記憶されてもよい。
【００３４】
事前復号された情報がベースとされる廃棄条件は典型的にスタチックであるが、事前復号された情報が変更されなければならない状態が存在しうる。例えばキャッシュの一貫性を維持するためにバッファ中のデータエントリを無効にすることが必要とされる可能性がある。それ故、１実施形態では、事前復号された廃棄情報は、その情報がバッファ４２５に記憶された後でさえも外部事象４５５に基づいて変化されることができる。
【００３５】
図５を参照すると、１実施形態に従って、データエントリをバッファから廃棄することができるか否かを決定するように構成されるバッファデータ廃棄条件ユニットと事前復号バッファデータ廃棄条件ユニットとを示すブロック図が示される。１実施形態では、事前復号バッファデータ廃棄条件ユニット５３５は、データエントリがバッファに記憶された後に変更の可能性が低いか全くないデータエントリについての廃棄情報を受信するように構成される。このような情報は、例えばアドレスの有効性の情報、データの有効性の情報等を含むことができる。
【００３６】
廃棄情報の一部の受信後、事前復号バッファデータ廃棄条件ユニット５３５は、事前復号された廃棄情報を生成し、１実施形態では、その情報を対応するデータエントリと共にバッファ５２５中に記憶するように構成される。
【００３７】
データエントリの廃棄が準備されると、バッファデータ廃棄条件ユニット５１０は、事前復号されたバッファ廃棄情報と、（ダイナミックな廃棄情報のような）任意の他の残りの廃棄情報とを受信し、データエントリを廃棄するか否かを決定するように構成される。更に、バッファデータ廃棄条件ユニット５１０は、書込みのエネーブル、ポインタのインクリメント、カウンタのインクリメント等のようなデータエントリの廃棄に関連する出力信号を生成するように構成される。
【００３８】
外部事象（外部事象５３０のような）は、情報がバッファを通って伝播している期間でさえも（即ち、データが事前復号バッファデータ廃棄条件ユニット５３５によりバッファに記憶された後）、データエントリと共にバッファ中に記憶された事前復号された廃棄情報を変更することができる。
【００３９】
１実施形態では、バッファ５２５は記憶待ち行列とすることができる。記憶待ち行列では、事前復号されたバッファデータ廃棄条件５３５のスタチックな廃棄データとして使用されることのできる情報は、データが有効であるか否か、命令のタイプ、エントリが無効にされているか否か、ページの属性、エントリがキャッシュのヒット／ミスに対応するか否か、アドレスが有効であるか否か等を含むことができる。記憶待ち行列中の事前復号された廃棄データを変更できる外部事象には、スヌープ、変換索引バッファ（ＴＬＢ）のページフォルトのようなメモリ管理ユニット（ＭＭＵ）の例外、後のデータを記憶する浮動小数点ユニット等が含まれることができる。
【００４０】
別の実施形態では、バッファ５２５はロードミス待ち行列とすることができる。ロードミス待ち行列では、事前復号されたバッファデータ廃棄条件５３５のスタチック廃棄データとして使用されることのできる情報には、データが有効であるか否か、命令のタイプ、エントリが無効にされているか否か、ページの属性、エントリが係属している理由等が含まれることができる。記憶待ち行列中の事前復号された廃棄データを変更できる外部事象には、スヌープ、ＴＬＢページフォルトのようなＭＭＵ例外、再ロードの完了、削除を係属させる理由等が含まれることができる。
【００４１】
更に別の実施形態では、バッファ５２５は、Ｌ２キャッシュまたは他の低いレベルのキャッシュをアクセスするためのバッファであるか、または非キャッシュバッファとすることができる。このようなバッファでは、事前復号されたバッファデータ廃棄条件５３５のスタチック廃棄データとして使用されることのできる情報は、データが有効であるか否か、動作のタイプ、エントリが無効にされるか否か、ページ属性、エントリがキャッシュのヒット／ミスに対応するか否か、エントリが係属している理由等を含むことができる。このタイプのバッファ中の事前復号された廃棄データを変更できる外部事象には、スヌープ、再ロードの完了、削除を係属させる理由、メモリアクセス動作を取消すためのリクエスト等が含まれることができる。
【００４２】
更に別の実施形態では、バッファ５２５は、バス動作を行うためのバスインターフェースバッファとすることができる。バスバッファでは、事前復号されたバッファデータ廃棄条件５３５のスタチック廃棄データとして使用されることのできる情報は、データが有効であるか否か、バスコマンドのタイプ、エントリが無効にされるか否か、ページの属性、エントリが係属している理由等を含むことができる。バスバッファの事前復号された廃棄データを変更できる外部事象は、スヌープ、削除を係属させる理由、バスの動作を取消すためのリクエスト等を含むことができる。
【００４３】
更に別の実施形態では、バッファ５２５は、不適切な（out-of-order）プロセッサの予約局のような命令を発生するバッファとすることができる。命令を発生するバッファに対しては、事前復号されたバッファデータ廃棄条件５３５のスタチック廃棄データとして使用されることのできる情報には、データが有効であるか否か、命令のタイプ、レジスタ依存（ＲＡＷ、ＷＡＲ、ＷＡＷ）が存在するか否か、ロード／記憶命令間にアドレス依存が存在するか否か、エントリが係属している理由等を含むことができる。命令を発生するバッファの事前復号された廃棄データを変更できる外部事象は、命令フラッシュ、レジスタ依存の解決、アドレス依存の解決、命令の終了等が含まれることができる。
【００４４】
図６を参照すると、１実施形態によるデータエントリをバッファから廃棄することができるか否かを決定する方法を示すフローチャートが示される。処理は６００で開始し、ブロック６１０で、データエントリは受信され、バッファ中に記憶される。１実施形態では、データエントリは、プロセッサのパイプラインから受信されることができ、ロードまたは待ち行列（バッファ）中に記憶されることができる。
【００４５】
ブロック６１５で、受信されたデータエントリに対応する事前復号された廃棄データが発生される。１実施形態では、事前復号された廃棄データは廃棄条件に部分的に基づいていてもよく、従ってデータエントリがバッファを伝播中に、条件が変化する可能性は非常に低い。
【００４６】
ブロック６２５で、事前復号された廃棄データが記憶される。１実施形態では、事前復号された廃棄データは対応するデータエントリと共にバッファ中に記憶される。別の実施形態では、事前復号された廃棄データはそのデータを対応するデータエントリに関連付ける情報と共に異なる区域に記憶されることができる。
【００４７】
データエントリがバッファ中に係属しているときに、外部事象の監視が実行される。その後、決定ブロック６３０で、バッファに記憶される事前復号された廃棄データの変更を外部事象が必要とするか否かの決定を行う。バッファ中の事前復号された廃棄データの変更が必要であるならば、決定ブロック６３０は“Ｙｅｓ”分岐路へ進み、ブロック６３５で、バッファの事前復号された廃棄データは外部事象に従って変更される。
【００４８】
他方で、事前復号された廃棄データの変更を必要とする外部事象がないならば、決定ブロック６３０は“Ｎｏ”分岐路へ進み、決定ブロック６３８で処理は継続し、ブロック６３５を迂回する。
【００４９】
決定ブロック６３８において、データエントリの廃棄を考慮する準備ができているか否かの決定が行われる。エントリの廃棄を考慮する準備ができているならば、決定ブロック６３８は“Ｙｅｓ”分岐路へ進み、予め定められたプロセス６４０へ進行する。予め定められたプロセス６４０で、データエントリを廃棄できるか否かの決定が行われる。予め定められたプロセス６４０についての詳細は図７及び図９と、それに対応する明細書の説明で与えられており、そこでは２つの別の実施形態が説明されている。処理はその後、６９９で終了する。
【００５０】
他方で、エントリの廃棄を考慮する準備ができていないならば、決定ブロック６３８は“Ｎｏ”分岐路へ進み、処理ループは決定ブロック６３０へ戻る。処理はその後、６９９で終了する。
【００５１】
図７を参照すると、１実施形態に従って、データエントリをバッファから廃棄することができるか否かを決定する方法を示すフローチャートが示される。処理は７００で開始し、ブロック７１０で、事前復号されたバッファデータの廃棄条件データがバッファ（またはデータが記憶されるその他の区域）から読取られる。ブロック７１５で、付加的なバッファデータ廃棄条件データが受信される。
【００５２】
ブロック７２０で、データエントリを事前復号されたバッファデータ廃棄条件データと、付加的なバッファデータ廃棄条件データとに基づいて廃棄するべきか否かが決定される。その後、決定ブロック７２５でデータエントリを廃棄することができるか否かの決定が行われる。データエントリが廃棄できるならば、決定ブロック７２５は“Ｙｅｓ”分岐路へ進み、ブロック７３０で、データエントリを廃棄する。処理ループは７９９で終了する。
【００５３】
データエントリを廃棄する準備ができないならば、決定ブロック７２５は“Ｎｏ”分岐路へ進み、ブロック７３５で、データエントリの廃棄が延期される。処理はその後、７９９で終了する。
【００５４】
図８を参照すると、１実施形態に従って、データエントリがバッファに記憶される間に、処理される情報に部分的に基づいて、データエントリをバッファから廃棄するか否かを決定するように構成されるシステムのブロック図が示される。更に性能を強化し、データ廃棄情報の処理に必要な時間を減少させるために、中間バッファデータ廃棄条件ユニット８７０が導入されている。このユニットはデータエントリがバッファを通過中に、付加的な廃棄条件を処理するように構成される。
【００５５】
１実施形態では、事前復号バッファデータ廃棄条件ユニット８５０は、依然として廃棄条件の一部を処理し、事前復号された廃棄情報を生成し、その情報をバッファ８２５に記憶する。バッファデータ廃棄条件ユニット８３５は、依然としてこの事前復号された廃棄情報を使用して対応するデータエントリを廃棄するか否かを決定する。しかしながら、データエントリの廃棄が考慮されているときには、バッファデータ廃棄条件ユニット８３５はまた、データエントリを廃棄するか否かを決定するために中間バッファデータ廃棄条件ユニット８７０により生成される付加的な廃棄情報を考慮する。
【００５６】
１実施形態では、中間バッファ廃棄条件ユニット８７０は、並行してバッファ８２５中の多数のエントリについて動作できる。これは各エントリに対して付加的な処理時間を可能にする。別の実施形態では、中間バッファ廃棄条件ユニット８７０及び／またはバッファ８２５は、１つのエントリに対する事前復号されたデータのあるビットが別のエントリに伝播することを可能にするように構成されることができる。これは廃棄条件入力の同じセットからのデータを再計算する必要なく、幾つかのデータエントリに対する事前復号されたデータの更新を可能にする。
【００５７】
代わりの実施形態では、バッファデータ廃棄条件ユニットの他の組合せがデータエントリを廃棄するか否かを決定するために使用されることができる。例えば、バッファデータ廃棄条件ユニット８３５は、事前復号バッファデータ廃棄条件ユニット８５０だけと共にまたは中間バッファデータ廃棄条件ユニット８７０だけと共に使用されることができる。
【００５８】
図９を参照すると、別の実施形態によるデータエントリをバッファから廃棄できるか否かを決定する方法を示すフローチャートが示される。この実施形態では、廃棄の決定は、エントリがバッファ中に記憶される前に発生される事前復号されたデータに部分的に基づいて、及びエントリがバッファに記憶された後で、かつエントリの廃棄の準備ができる前の廃棄条件情報の処理に部分的に基づいている。
【００５９】
処理は９００で開始し、ブロック９１０で、事前復号された廃棄データがバッファ（またはデータが記憶されることのできる別の区域）から読取られる。ブロック９１２で、付加的な廃棄条件データが受信される。ブロック９１５で、事前復号されたデータ及び付加的なデータは、更新された事前復号された廃棄データを生成するように処理される。ブロック９２０で、もとの事前復号された廃棄データは更新された事前復号された廃棄データと置換される。
【００６０】
幾らか後で、データエントリの廃棄が考慮される。ブロック９２１で、事前復号された廃棄データがバッファ（またはデータが記憶される他の区域）から読取られる。ブロック９２２で、付加的な廃棄条件データが受信される。この廃棄条件データはブロック９１５で処理された廃棄条件データとは異なる。ブロック９２２で受信された廃棄条件データは、データエントリの廃棄が考慮される時点までに変化する可能性が非常に高いダイナミック情報を含むことができる。
【００６１】
ブロック９２３で、事前復号された廃棄条件データと付加的な廃棄条件データとに基づいて、データエントリを廃棄するか否かが決定される。その後、決定ブロック９２５でデータエントリを廃棄できるか否かの決定が行われる。データエントリを廃棄できるならば、決定ブロック９２５は“Ｙｅｓ”分岐路へ進み、ブロック９３０で、データエントリは廃棄される。処理はその後、９９９で終了する。データエントリの廃棄の準備ができていないならば、決定ブロック９２５は“Ｎｏ”分岐路へ進み、ブロック９３５で、データエントリの廃棄が延期される。処理はその後、９９９で終了する。
【００６２】
前述の実施形態をプロセッサ待ち行列（例えば記憶待ち行列、ロードミス待ち行列、キャッシュアクセス待ち行列等）に関して説明したが、代わりの実施形態では他の形式のシステムの他の形式のバッファ／待ち行列で構成されることができることに注意すべきである。前述したように、待ち行列エントリの事前処理の必要性は、更に迅速なデータの処理（及び待ち行列エントリの廃棄）に対する要求が増加しているので、プロセッサの場合には更に緊急である。それ故、本発明は特許請求の範囲に記載されているように、これらの別の実施形態を含むものと解釈されるべきである。
【００６３】
前述のある実施形態（例えばマイクロプロセッサの記憶待ち行列）は、特定の頻度（例えばクロックサイクル当り１エントリ）による廃棄を可能にすることを目的としているが、バッファエントリ毎にこれを実現することは可能ではない場合もあることに注意すべきである。それ故、幾つかの実施形態では、幾つかのバッファエントリでこのような制約を緩和する必要がある可能性がある。例えば、他の形式の命令よりも多数の廃棄条件を考慮しなければならないある形式の命令では、１クロックサイクルではなく２クロックサイクルでマイクロプロセッサの記憶待ち行列から廃棄されることを可能にされる。
【００６４】
当業者であれば、情報及び信号が任意の種々の異なる技術を使用して表されることができることを理解するであろう。例えば、先の説明を通して参照されることのできるデータ、命令、コマンド、情報、信号、ビット、及びシンボルは、電圧、電流、電磁波、磁界または粒子、光フィールドまたは粒子、或いは任意のそれらの組合せによって表されることができる。
【００６５】
当業者であれば更に、ここで開示した実施形態を伴って説明した種々の例示的な論理ブロック、モジュール、回路、アルゴリズムステップが、ハードウェア（コンピュータシステムを含む）、ソフトウェア（ファームウェアを含む）またはその両者の組合せとして構成されることを認識するであろう。このハードウェアとソフトウェアとの交換能力を明白に示すために、種々の例示的なコンポーネント、ブロック、モジュール、回路、及びステップをそれらの機能に関して一般的に説明した。このような機能がハードウェアまたはソフトウェアのいずれとして構成されるかは、特定の応用と、システム全体に課された設計制約に依存する。当業者であれば、それぞれの特定の応用に対して、説明した機能を種々の方法で実行できるが、このような実行の決定は本発明の技術的範囲からの逸脱するものとして解釈されるべきではない。
【００６６】
ここで使用されている“コンピュータ”及び“コンピュータシステム”は、ここで説明した機能を実行できる任意のタイプのデータ処理システムを含むことを意図している。このようなコンピュータは、コンピュータで読取り可能な媒体を使用することができ、それらは、コンピュータにより実行されることのできるソフトウェアプログラム命令を記憶できる任意の媒体、例えば、フロッピー（Ｒ）ディスク、ハードディスクドライブ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＲＡＭ、ＲＯＭ、ＤＡＳＤアレイ、磁気テープ、フロッピー（Ｒ）ディスケット、光記憶装置等を含むことができる。
【００６７】
ここで開示した実施形態に関して説明した種々の例示的な論理ブロック、モジュール及び回路は、汎用目的のプロセッサ、デジタル信号プロセッサ（ＤＳＰＳ）、メディアプロセッサ、特定用途用集積回路（ＡＳＩＣ）、フィールドプログラム可能なゲートアレイ（ＦＰＧＡ）、または他のプログラム可能な論理装置、ディスクリートなゲートまたはトランジスタ論理装置、ディスクリートなハードウェアコンポーネント、或いはここで説明した機能を実行するように設計された任意のその組合せによって構成または実行されることができる。汎用目的のプロセッサは、任意の通常のプロセッサ、コントローラ、マイクロコントローラ、状態マシン等とすることができる。プロセッサはまた、コンピュータ装置の組合せ、例えばＤＳＰ、メディアプロセッサ、マイクロプロセッサまたは複数のマイクロプロセッサ、ＤＳＰコアと連結した１以上のマイクロプロセッサ、メディアプロセッサ或いは任意の他のこのような構造として構成されることもできる。
【００６８】
ここで開示した実施形態に関連して説明した方法またはアルゴリズムのステップは、直接ハードウェア、プロセッサにより実行されるソフトウェアモジュール、またはその２つの組み合わせで実施されてもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、取出し可能なディスク、ＣＤ−ＲＯＭ、または技術で知られているその他の形態の記憶媒体中に存在してもよい。例示的な記憶媒体はプロセッサに結合され、このようなプロセッサは情報を記憶媒体から読み出し、そこに情報を書込むことができる。その代りに、記憶媒体はプロセッサに一体化されることもできる。プロセッサ及び記憶媒体は例えばＡＳＩＣ中に存在していてもよい。ＡＳＩＣはユーザ端末に存在してもよい。その代りに、プロセッサ及び記憶媒体はユーザ端末中にディスクリートなコンポーネントとして存在することもできる。
【００６９】
本発明により与えられる効果及び利点を特定の実施形態に関して説明した。これらの効果及び利点、ならびに行われまたは更に明白にされるその他のエレメントまたは限定は、特許請求の範囲に記載された任意または全ての特徴は臨界的で必要とされるまたは基本的特性として解釈されるべきではない。ここで使用されるように、用語「具備する」、「具備している」または任意の他のその変形は排他的ではなく、これらの用語に付随するエレメントまたは限定を含むとして解釈されることを意図する。従って、システム、方法または、１組のエレメントを含むその他の実施形態はこれらのエレメントだけに限定されることを意図するものではなく、記載されていないか、請求された実施形態に固有ではないその他のエレメントを含むことができる。
【００７０】
本発明を特定の実施形態を参照して説明したが、実施形態は単なる例示であって、本発明の技術的範囲はそれらの実施形態に限定されないことを理解すべきである。前述の実施形態に対する多数の変形、変更、付加、改良が可能である。これらの変形、変更、付加、改良は特許請求の範囲に詳細にされている本発明の技術的範囲内含まれると考慮される。
【００７１】
例えば、本発明によれば、下記のようなシステム及び方法を提供することができる。
【００７２】
（１）データエントリを受信するように構成されたバッファと、事前復号論理装置と、廃棄論理装置とを具備するシステムであって、
前記事前復号論理装置は、
前記データエントリに対する第１のセットの廃棄条件に対応する第１の情報を受信し、
前記第１の情報に基づいて前記データエントリに対する事前復号された廃棄情報を発生するように構成され、
前記廃棄論理装置は、
前記事前復号された廃棄情報と、前記データエントリに対する第２のセットの廃棄条件に対応する第２の情報とを受信し、
前記事前復号された廃棄情報及び前記第２の情報に基づいて前記データエントリを廃棄するか否かを決定するように構成される。
【００７３】
（２）上記（１）のシステムにおいて、前記事前復号論理装置は、前記データエントリを前記バッファ中に記憶するのに先立って前記事前復号された廃棄情報を発生するように構成される。
【００７４】
（３）上記（２）のシステムにおいて、前記事前復号された廃棄情報は前記データエントリを有するバッファ中に記憶される。
【００７５】
（４）上記（２）のシステムにおいて、前記事前復号された廃棄情報は前記バッファとは分離された別のメモリ区域に記憶され、前記事前復号された廃棄情報は前記事前復号された廃棄情報と前記データエントリとの関係を示す情報と共に記憶される。
【００７６】
（５）上記（１）のシステムにおいて、１以上の外部事象を監視し、前記外部事象に従って前記事前復号された廃棄情報を変更するように構成される外部事象処理論理装置を更に具備する。
【００７７】
（６）上記（５）のシステムにおいて、前記１以上の外部事象は、スヌープ動作、アドレス変換情報の更新、及びデータの有効性の情報の更新からなるグループから選択される。
【００７８】
（７）上記（１）のシステムにおいて、前記事前復号論理装置は、前記データエントリが前記バッファに記憶された後で、前記データエントリの廃棄が考慮される前に、前記事前復号された廃棄情報を発生するように構成される。
【００７９】
（８）上記（１）のシステムにおいて、前記事前復号論理装置は、
前記データエントリを前記バッファ中に記憶する前に、前記第１の情報の第１のサブセットに基づいて前記事前復号された廃棄情報を発生する第１のコンポーネントと、
前記データエントリを前記バッファ中に記憶した後に、前記第１の情報の第２のサブセットに基づいて前記事前復号された廃棄情報を更新する第２のコンポーネントと、
を具備する。
【００８０】
（９）上記（８）のシステムにおいて、前記第２のコンポーネントは、前記データエントリをバッファ中に記憶した後に、前記事前復号された廃棄情報と前記第１の情報の第２のサブセットに基づいて、前記事前復号された廃棄情報を更新する。
【００８１】
（１０）上記（１）のシステムにおいて、前記事前復号論理装置は、
前記データエントリを前記バッファ中に記憶する前に、前記第１の情報の第１のサブセットに基づいて前記事前復号された廃棄情報の第１のコンポーネントを発生する第１のコンポーネントと、
前記データエントリを前記バッファ中に記憶する前に、前記第２の情報の第２のサブセットに基づいて前記事前復号された廃棄情報の第２のコンポーネントを発生する第２のコンポーネントと、
を具備する。
【００８２】
（１１）上記（１）のシステムにおいて、前記バッファは、記憶待ち行列、ロード待ち行列、下位メモリアクセス待ち行列、バスインターフェースバッファ、命令発生バッファからなるグループから選択される。
【００８３】
（１２）上記（１）のシステムにおいて、前記事前復号論理装置は、データエントリに対する廃棄条件の中間セットに対応する中間情報に基づいて、前記記憶された事前復号された廃棄情報を更新するように構成される中間コンポーネントを具備し、前記中間コンポーネントは、多数のバッファエントリに対する前記記憶された事前復号された廃棄情報を並列に更新するように構成される。
【００８４】
（１３）上記（１）のシステムにおいて、前記事前復号論理装置は、データエントリに対する廃棄条件の中間セットに対応する中間情報に基づいて、前記記憶された事前復号された廃棄情報を更新するように構成される中間コンポーネントを具備し、前記中間コンポーネントは、１つのバッファエントリに対する前記記憶された事前復号された廃棄情報の１以上のビットが別のバッファエントリへ伝播することを可能にするように構成される。
【００８５】
（１４）バッファのデータエントリを受信する工程と、
前記データエントリに対する第１のセットの廃棄条件に対応する第１の情報を受信する工程と、
前記第１の情報に基づいて前記データエントリに対する事前復号された廃棄情報を発生する工程と、
前記事前復号された廃棄情報と、前記データエントリに対する第２のセットの廃棄条件に対応する第２の情報とを受信する工程と、
前記事前復号された廃棄情報及び前記第２の情報に基づいて前記データエントリを廃棄するか否かを決定する工程と、
を具備する方法。
【００８６】
（１５）上記（１４）の方法において、前記事前復号された廃棄情報が発生された後、前記データエントリを前記バッファ中に記憶する工程を更に含む。
【００８７】
（１６）上記（１５）の方法において、前記事前復号された廃棄情報は前記データエントリと共にバッファ中に記憶される。
【００８８】
（１７）上記（１５）の方法において、前記事前復号された廃棄情報は前記バッファとは分離された別の区域に記憶され、前記方法は、前記事前復号された廃棄情報と前記データエントリとの関係を示す情報と共に前記事前復号された廃棄情報を記憶する工程を更に含む。
【００８９】
（１８）上記（１４）の方法において、外部事象を監視し、前記外部事象に基づいて前記事前復号された廃棄情報を変更する工程を更に含む。
【００９０】
（１９）上記（１８）の方法において、前記外部事象は、スヌープ動作、アドレス変換情報の更新、データの有効性の情報の更新からなるグループから選択される。
【００９１】
（２０）上記（１４）の方法において、前記復号された廃棄情報が発生される前に、前記データエントリをバッファ中に記憶し、前記復号された廃棄情報が発生された後に、前記データエントリの廃棄を考慮する工程を更に含む。
【００９２】
（２１）上記（１４）の方法において、前記復号された廃棄情報の発生は、前記データエントリを前記バッファ中に記憶する前に、前記第１の情報の第１のサブセットに基づいて前記事前復号された廃棄情報を発生し、前記データエントリを前記バッファ中に記憶した後に、前記第１の情報の第２のサブセットに基づいて前記事前復号された廃棄情報を更新する工程を含む。
【００９３】
（２２）上記（２１）の方法において、前記事前復号された廃棄情報の更新は、前記事前復号された廃棄情報と前記第１の情報の第２のサブセットとに基づいてなされる。
【００９４】
（２３）上記（１４）の方法において、前記事前復号された廃棄情報の発生は、
前記データエントリを前記バッファ中に記憶する前に、前記第１の情報の第１のサブセットに基づいて、前記事前復号された廃棄情報の第１のサブセットを発生し、
前記データエントリを前記バッファ中に記憶する前に、前記第２の情報の第２のサブセットに基づいて、前記事前復号された廃棄情報の第２のサブセットを発生する工程を含む。
【００９５】
（２４）上記（１４）の方法において、前記バッファは、記憶待ち行列、ロード待ち行列、下位メモリアクセス待ち行列、バスインターフェースバッファ、命令発生バッファからなるグループから選択される。
【００９６】
（２５）上記（１４）の方法において、廃棄条件の対応する中間セットに基づいて多数のデータエントリに対して前記記憶された事前復号された廃棄情報を更新する工程を更に含み、前記更新は多数のバッファのエントリに対して並列に行われる。
【００９７】
（２６）上記（１４）の方法において、廃棄条件の対応する中間セットに基づいて多数のデータエントリに対して前記記憶された事前復号された廃棄情報を更新し、１つのバッファのエントリに対する前記記憶された事前復号された廃棄情報の１以上のビットを別のバッファのエントリへ伝播する工程を更に含む。
【図面の簡単な説明】
【００９８】
【図１】従来技術に従って、データエントリをバッファ中に記憶し、そのデータエントリの廃棄が準備されると、バッファから廃棄するように構成されるシステムを示すブロック図。
【図２】従来技術に従って、データエントリをバッファから廃棄することができるか否かを決定するように構成されるバッファデータ廃棄条件ユニットを示すブロック図。
【図３】従来技術に従って、バッファデータ廃棄条件の論理回路を示すブロック図。
【図４】本発明の１実施形態に従って、データエントリをバッファに記憶し、対応するデータエントリと共にバッファに事前復号された廃棄データを記憶するように構成されるシステムを示すブロック図。
【図５】本発明の１実施形態に従って、データエントリをバッファから廃棄することができるか否かを決定するように構成されるバッファデータ廃棄条件ユニットと事前復号バッファデータ廃棄条件ユニットとを示すブロック図。
【図６】本発明の１実施形態に従って、データエントリをバッファから廃棄することができるか否かを決定する方法を示すフローチャート。
【図７】本発明の１実施形態に従って、データエントリをバッファから廃棄することができるか否かを決定する方法を示すフローチャート。
【図８】本発明の１実施形態に従って、データエントリがバッファに記憶される間に、処理された情報に部分的に基づいて、データエントリをバッファから廃棄するか否かを決定するように構成されるシステムを示すブロック図。
【図９】本発明の１実施形態に従って、部分的にエントリがバッファに記憶される間に、及び部分的にエントリの廃棄が準備できる前に、データエントリを部分的に廃棄できるか否かを決定する方法を示すフローチャート。
【図１】
2006059350.tif 000003
【図２】
2006059350.tif 000004
【図３】
2006059350.tif 000005
【図４】
2006059350.tif 000006
【図５】
2006059350.tif 000007
【図６】
2006059350.tif 000008
【図７】
2006059350.tif 000009
【図８】
2006059350.tif 000010
【図９】
2006059350.tif 000011