(57)【要約】タグミスアロケーションに続いて複数のセットウエイのレジデンシーを最大にするようにキャッシュメモリアロケーションを交換することを含む、ＣＤＭＡに基づいた製品およびサービスに使用するための技術。ここに、ステップは、キャッシュメモリのためのビクティムウエイのファーストイン、ファーストアウト（ＦＩＦＯ）交換リストを形成する。この場合、ＦＩＦＯ交換リストの深さは、キャッシュセット内の数にほぼ等しい。この方法とシステムは、タグミスがタグミスアロケーションを生じた場合にのみビクティムウエイをＦＩＦＯ交換リスト上に配置する。ビクティムウエイは任意の以前に選択されたビクティムウエイの後でＦＩＦＯ交換リストのおわりに配置される。例えば、ビクティムウエイのイニシャルアロケーションが完了するまで引き止めておくことにより、またはビクティムウエイのイニシャルアロケーションが完了するまで再使用リクエストをリプレイ(replay)することによりビクティムウエイの不完全な先のアロケーションの場合にＦＩＦＯ交換リスト上のビクティムウエイの使用が防止される。
2009537912.tif 000002
【特許請求の範囲】
【請求項１】
下記を具備する、キャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換するための方法：
デジタルシグナルプロセッサの動作に使用するためにキャッシュウエイのＦＩＦＯリスト上の前記キャッシュウエイの位置によって交換されるキャッシュウエイとしてビクティムウエイを選択するステップ；
次のキャッシュタグミスでビクティムウエイを再使用する前記キャッシュセットについての次のキャッシュタグミスをキャッシュセットＦＩＦＯリストのおわりに配置するステップ；
前記ビクティムウエイのイニシャルアロケーションがキャッシュタグと前記キャッシュセットとの間のインコヒーレンシー(incoherency)を回避するまでビクティムウエイの再使用を防止するステップ；
前記ビクティムウエイのイニシャルアロケーションが完了するまで再使用リクエストに対する応答を引き止めておくことにより前記ビクティムウエイのそのようなイニシャルアロケーションが完了するまでビクティムウエイの再使用を防止するステップ；
前記ビクティムウエイのそのようなイニシャルアロケーションが完了するまで再使用リクエストをリプレイ(replay)することにより前記ビクティムウエイのイニシャルアロケーションが完了するまでビクティムウエイの再使用を防止するステップ。
【請求項２】
前記選択ステップはさらに前記キャッシュミスに続いてキャッシュセットＦＩＦＯリストの終わりに前記ビクティムウエイを配置することにより交換される前記キャッシュウエイとしてビクティムウエイを選択するステップをさらに備えた、請求項１の方法。
【請求項３】
デジタルシグナルプロセッサデータユニット命令に関連したキャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換するステップをさらに備えた、請求項１の方法。
【請求項４】
デジタルシグナルプロセッサ命令ユニット命令の実行に関連したキャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換するステップをさらに備えた、請求項１の方法。
【請求項５】
再使用ハザードの場合に、
現在の／入ってくる一次ミスビクティムウエイを前記ＦＩＦＯリスト内の他のウエイと比較するステップと、
前記入ってくる一次ミスのセットアドレスを他のセットアドレスと比較するステップと、
前記比較ステップに応答して、再使用ハザードが無いビクティムウエイが生じるまで現在の／入ってくるスレッドをリプレイするステップと、
をさらに備えた請求項４の方法。
【請求項６】
最も最近に使用されたビクティムウエイを前記ＦＩＦＯリストの終わりに加えるステップをさらに備えた、請求項１の方法。
【請求項７】
マルチスレッドデジタルシグナルプロセッサ内の前記ビクティムウエイを交換するステップをさらに備えた、請求項１の方法。
【請求項８】
使用されたビクティムウエイを記録するために記憶ビットの使用を必要とすることなく前記交換ステップを実行するステップをさらに備えた、請求項１の方法。
【請求項９】
キャッシュウエイミスの場合に前記ＦＩＦＯリストを単にインクリメントするステップをさらに備えた、請求項１の方法。
【請求項１０】
下記を具備する、デジタルシグナルプロセッサに関連して動作するためのキャッシュウエイ交換回路であって、キャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換するキャッシュウエイ交換回路：
デジタルシグナルプロセッサの動作に使用するためにキャッシュウエイのＦＩＦＯリスト上の前記キャッシュウエイの位置によって交換される前記キャッシュウエイとしてビクティムウエイを選択するビクティムウエイ選択回路；
次のキャッシュタグミスでビクティムウエイを再使用する前記キャッシュセットについての次のキャッシュタグミスを前記キャッシュセットＦＩＦＯリストのおわりに配置するＦＩＦＯリストポピュレーション(population)回路；
前記ビクティムウエイのイニシャルアロケーションがキャッシュタグと前記キャッシュセットとの間のインコヒーレンシー(incoherency)を回避するまでビクティムウエイの再使用を防止するキャッシュウエイ再使用ハザード検出回路であって、前記ビクティムウエイのイニシャルアロケーションが完了するまで再使用リクエストに対する応答を引き止めておくことにより前記ビクティムウエイのそのようなイニシャルアロケーションが完了するまでビクティムウエイの再使用を防止するキャッシュウエイ再使用ハザード検出回路。
【請求項１１】
前記キャッシュミスに続いてキャッシュセットＦＩＦＯリストの終わりに前記ビクティムウエイを配置することにより交換される前記キャッシュウエイとしてビクティムウエイを選択するためのビクティムウエイ選択回路をさらに備え、前記ＦＩＦＯの深さは、前記キャッシュセット内のウエイの数にほぼ等しい、請求項１０のキャッシュウエイ交換回路。
【請求項１２】
デジタルシグナルプロセッサデータユニット命令の実行に関連したキャッシュタグミスの場合にはキャッシュセットの複数のセットウエイの１つを交換するためのデータユニット回路をさらに備えた、請求項１０のキャッシュウエイ交換回路。
【請求項１３】
デジタルシグナルプロセッサ命令ユニット命令の実行に関連したキャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換する命令ユニット回路をさらに備えた、請求項１０のキャッシュウエイ交換回路。
【請求項１４】
現在の／入ってくる一次ミスビクティムウエイを前記ＦＩＦＯリスト内の他のウエイと比較し、入ってくる一次ミスのセットアドレスを他のセットアドレスと比較する比較回路と、
再使用ハザードが無いビクティムウエイが生じるまで前記比較ステップに応答して前記現在の／入ってくるスレッドをリプレイするためのキャッシュウエイリプレイ回路とをさらに備えた、請求項１０のキャッシュウエイ交換回路。
【請求項１５】
最も最近に使用されたビクティムウエイを前記ＦＩＦＯリストのおわりに加えるＦＩＦＯリスト回路をさらに備える、請求項１０のキャッシュウエイ交換リスト。
【請求項１６】
マルチスレッドのデジタルシグナルプロセッサ内の前記ビクティムウエイを交換するマルチスレッドのデジタルシグナルプロセッサをさらに備えた、請求項１０のキャッシュウエイ交換回路。
【請求項１７】
使用されたビクティムウエイを記録するために記憶ビットの使用を必要とせずに前記交換ステップの性能を可能にする交換回路をさらに備えた、請求項１０のキャッシュウエイ交換回路。
【請求項１８】
キャッシュウエイミスの場合に前記ＦＩＦＯリストを単にインクリメントするインクリメント回路をさらに備えた、請求項１０のキャッシュウエイ交換回路。
【請求項１９】
キャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換するための手段を含むデジタルシグナルプロセッサであって、下記を具備するデジタルシグナルプロセッサ：
デジタルシグナルプロセッサの動作で使用するためにキャッシュウエイのＦＩＦＯリスト上の前記キャッシュウエイの位置にしたがって交換される前記キャッシュウエイとしてビクティムウエイを選択する手段；
次のキャッシュタグミスでビクティムウエイを再使用する前記キャッシュセットについての次のキャッシュタグミスを前記キャッシュセットＦＩＦＯリストのおわりに配置する手段；
前記ビクティムウエイのイニシャルアロケーションがキャッシュタグと前記キャッシュセットとの間のインコヒーレンシー(incoherency)を回避するまでビクティムウエイの再使用を防止する手段；
ビクティムウエイのイニシャルアロケーションが完了するまで再使用リクエストに対する応答を引き止めておくことにより前記ビクティムウエイのそのようなイニシャルアロケーションが完了するまで前記ビクティムウエイの再使用を防止する手段；
前記ビクティムウエイのイニシャルアロケーションが完了するまで再使用リクエストをリプレイすることにより前記ビクティムウエイのそのようなイニシャルアロケーションが完了するまでビクティムウエイの再使用を防止する手段。
【請求項２０】
前記キャッシュミスに続いてキャッシュセットＦＩＦＯリストのおわりに前記ビクティムウエイを配置することにより交換される前記キャッシュウエイとしてビクティムウエイを選択する手段をさらに備えた、請求項１９のデジタルシグナルプロセッサ。
【請求項２１】
デジタルシグナルプロセッサデータユニット命令に関連したキャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換する手段をさらに備えた、請求項１９のデジタルシグナルプロセッサ。
【請求項２２】
デジタルシグナルプロセッサ命令ユニット命令の実行に関連したキャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換する手段をさらに備えた、請求項１９のデジタルシグナルプロセッサ。
【請求項２３】
現在の／入ってくる一次ミスビクティムウエイを前記ＦＩＦＯリスト内の他のウエイと比較する手段と、
前記入ってくる一次ミスのセットアドレスを他のセットアドレスと比較する手段と、
再使用ハザードの無いビクティムウエイが生じるまで前記比較に応答して現在の／入ってくるスレッドをリプレイする手段、
とをさらに備えた、請求項２２のデジタルシグナルプロセッサ。
【請求項２４】
最も最近に使用されたビクティムウエイを前記ＦＩＦＯリストの終わりに加える手段をさらに備えた、請求項１９のデジタルシグナルプロセッサ。
【請求項２５】
マルチスレッドのデジタルシグナルプロセッサ内の前記ビクティムウエイを交換する手段をさらに備えた、請求項１９のデジタルシグナルプロセッサ。
【請求項２６】
使用されるビクティムウエイを記録するために記憶ビットの使用を必要とすることなく前記交換を実行する手段をさらに備えた、請求項１９のデジタルシグナルプロセッサ。
【請求項２７】
キャッシュウエイミスの場合に前記ＦＩＦＯリストを単にインクリメントする手段をさらに備えた、請求項１９のデジタルシグナルプロセッサ。
【請求項２８】
キャッシュタグミスの場合にキャッシュセットの複数のセットウエイの１つを交換するデジタルシグナルプロセッサ上の命令を処理するためにコンピュータ読み取り可能プログラムコード手段が具現化されたコンピュータ使用可能媒体において、前記コンピュータ読み取り可能媒体は下記を具備する：
デジタルシグナルプロセッサの動作で使用するためにキャッシュウエイのＦＩＦＯリスト上の前記キャッシュウエイの位置によって交換されるキャッシュウエイとしてビクティムウエイを選択するコンピュータ読み取り可能プログラムコード手段；
次のキャッシュタグミスでビクティムウエイを再使用する前記キャッシュセットについての次のキャッシュタグミスを前記キャッシュセットＦＩＦＯリストのおわりに配置するコンピュータ読み取り可能プログラムコード手段；
前記ビクティムウエイのイニシャルアロケーションがキャッシュタグと前記キャッシュセットとの間のインコヒーレンシーを回避するまでビクティムウエイの再使用を防止するコンピュータ読み取り可能プログラムコード手段；
前記ビクティムウエイのイニシャルアロケーションが完了するまで再使用リクエストに対する応答を引き止めておくことにより前記ビクティムウエイのそのようなイニシャルアロケーションが完了するまで前記ビクティムウエイの再使用を防止するコンピュータ読み取り可能プログラムコード手段；
前記ビクティムウエイのイニシャルアロケーションが完了するまで再使用リクエストをリプレイすることにより前記ビクティムウエイのそのようなイニシャルアロケーションが完了するまで前記ビクティムウエイの再使用を防止するコンピュータ読み取り可能プログラムコード手段。
【請求項２９】
前記キャッシュミスに続いてキャッシュセットＦＩＦＯリストの終わりに前記ビクティムウエイを配置することにより交換される前記キャッシュウエイとしてビクティムウエイを選択するコンピュータ読み取り可能プログラムコードをさらに備えた、請求項２８のコンピュータ使用媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
開示された主題は通信製品およびサービスを支持するデジタル信号処理に関する。特にこの開示は、ハンドセットまたは他の通信システムのためにデジタルシグナルプロセッサにおける使用を見つけてもよいキャッシュメモリの最大レジデンシー交換のための新規で改良された方法およびシステムに関する。
【背景技術】
【０００２】
ますます、電子機器および支援するソフトウェアプリケーションはデジタル信号処理を含む。ホームシアター、コンピューターグラフィックス、医用画像および電気通信はすべて、信号処理技術に依存する。デジタル信号処理は、複合体中の速い数学だが反復のアルゴリズムを要求する。多くのアプリケーションが、リアルタイムにおいて計算を要求する。つまり、信号は時間の連続関数である。それは数値処理のためにサンプリングされバイナリに変換されなければならない。従って、サンプルが到着すると、サンプルに対してディスクリートな計算を実行するアルゴリズムを実行しなければならない。デジタルシグナルプロセッサ、すなわちＤＳＰのアーキテクチャはそのようなアルゴリズムを処理するように最適化される。良い信号処理エンジンの特性は高速で柔軟な演算計算ユニット、計算ユニットへ、および計算ユニットからの拘束されないデータフロー、計算ユニットにおける拡張精度およびダイナミックレンジ、効率的なプログラムシークエンシング(sequencing)、およびプログラミングの容易さを含む。
【０００３】
ＤＳＰ技術の１つの前途有望なアプリケーションは、衛星または地上リンクを介してユーザー間の音声およびデータ通信をサポートする符号分割多重アクセス（ＣＤＭＡ）システムのような通信システムを含む。多重アクセス通信システムにおけるＣＤＭＡプロセスの使用は、「衛星または地上リピーターを用いた拡散スペクトル多重アクセス通信システム」(SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS）というタイトルの米国特許第４，９０１，３０７、および「ＣＤＭＡセルラテレハンドセットシステムにおいて波形を発生するためのシステムおよび方法」（SYSYTEM AND METHOD FOR GENERATING WAVEFORMS IN A CDMA CELLULAR TELEHANDSET SYSTEM）というタイトルの米国特許第５、１０３、４５９に開示されている。両特許はクレームされた主題の譲受人に譲渡されている。
【０００４】
ＣＤＭＡシステムは典型的に１つ以上の遠隔通信に、そして現在ではストリーミングビデオ(streaming video)規格に一致するように設計される。1つのそのような第一世代規格は、以下にIS-95規格と呼ばれた「デュアルモードの広帯域のスペクトラム拡散セルラシステムのためのＴＩＡ／ＥＩＡ／ＩＳ−９５端末−基地局互換規格」です。ＩＳ−９５  ＣＤＭＡシステムは音声データとパケットのデータを送信することができる。より効率的にパケットデータを送信することができるより新しい世代規格は、「第三世代パートナーシッププロジェクト」(3GPP)という名の、および文献番号3G TS 25.211、3G TS 25.212、3G TS 25.213および3G TS 25.214を含むセットの文献で具現化されたコンソーシアムによって提示される。それは公に容易に利用可能である。3GPP規格は以下にW-CDMA規格と呼ばれる。そのような無線送受話器がますます使用する他の多くのものと同様にMPEG-1、MPEG2、MPEG-4、H.264およびWMV(ウインドウズメディアビデオ)のようなビデオの圧縮規格もある。
【０００５】
デジタルシグナルプロセッサ（ＤＳｐｓ）は、上述した規格に従う無線ハンドセットに価値のある使用を見つけてもよい。特に、無線ハンドセットは、ユーザー指向、科学、およびマルチメディアアプリケーション並びに他の多くのその他のタイプのアプリケーションからの命令をＤＳＰが実行することを要求しているし、ますます要求するであろう。プロセッサリソース必要条件は、すべてが同じＤＳＰからのものである、テレビ放送、ストリーミングメッセージチケット、（添付された文献を有したメッセージを含む）電子メール、並びにストリーミングビデオ（例えばテレビ会議）、写真、およびドキュメント（ワードプロセッシング、スプレッドシート、プレゼンテーション等）アプリケーションに対して広範囲におよび動的に変化してもよい。
【０００６】
ＤＳＰの動作において、例えば、そのようなポータブルおよびハンドヘルドアプリケーションの広まりつつある使用により、より低い電力消費はデータ処理システムにおいて増大する重要性である。今日、多くのＤＳＰｓはメインメモリへのアクセスの回数を低減するために、時々キャッシュと呼ばれるより小型で、高速かつより効率的なメモリを使用する。キャッシュメモリへのアクセスは一般により少ない電力を消費し、他の内部あるいは外部記憶装置へのアクセスと比較して、縮小された待ち時間をもたらす。より速く、より効率的なキャッシュ中で続いて再び要求されるアイテムの記憶によって、著しい電力低減および性能増加が生じるかもしれない。
【０００７】
キャッシュメモリは、またプロセッサに、DRAMのようなメインメモリソースに関連した待機状態を招かずに、データを速くフェッチするための方法を供給する。キャッシュメモリの使用は典型的にコンピューターシステム性能を改良し、複雑なバス構造のメインメモリの使用から生じるページングサイクルまたは物理的な遅延を必要とせずに、共通に使用されるデータをプロセッサに提供する。
【０００８】
典型的には、キャッシュメモリは「セット」あるいは「ウエイ(way)」で組織される(以下、集合的に「ウエイ」と呼ぶ)。キャッシュメモリウエイは典型的には、共通のアドレスを使用してアクセスされてもよい多数のキャッシュメモリエントリーロケーションを含む。セットアソシエィティブキャッシュ(set-associative cache)は、ＤＲＭのようなメインメモリソース内の特定のロケーションに割当てられる、または「マップ」されるキャッシュウエイでデータを組織するキャッシュメモリの１つのタイプである。その方法内で記憶されたデータがメインメモリ内の別のロケーションからのデータと交換されるとき、キャッシュメモリウエイはリマップ(re-mapped)される。さらに、キャッシュウエイは、キャッシュにおいて、特定のメインメモリロケーションに関連する最も最新のバージョンのデータを維持することを支援するために同じメインメモリロケーションにマップされてもよい。
【０００９】
さて、キャッシュメモリはメインメモリより典型的に小さい。したがって、キャッシュに記憶されない新しくアクセスされたデータに場所を空けるためにキャッシュウエイを削除する必要がある。交換されるそれらのキャッシュウエイは「ビクティムウエイ(victim way)」として知られている。ビクティムウエイに印加されるデータは、しばらくの間キャッシュにあったデータよりも、統計的に近い将来再びアクセスされる可能性が高いはずである。典型的には、キャッシュは、与えられたトランザクションに対応するデータを記憶するのに適格な1つ以上のキャッシュエントリーを選択し、ヒット(hit)またはミス(miss)を検出するためにこれらのエントリーをサーチする。セットアソシエイティブキャッシュでは、2つ以上のエントリーがデータのアドレスに基づいてデータを記憶するのに適格である。ミスの場合に2つ以上のエントリーのうちの任意の1つのキャッシュラインを立ち退かせることができるかもしれない。セットアソシエイティブキャッシュは立ち退かせるために２つ以上の適格なエントリーのうちの1つを選択する交換政策を採用する。様々な交換政策が存在する。
【００１０】
キャッシュ交換処理の２つの周知のタイプは、最も最近に使用された（「ＬＲＵ」）および最近使用されなかった（「ＮＲＵ」）キャッシュ交換政策である。これらのキャッシュ交換政策の各々は、所定の時でも交換政策の状態を決定する実施された交換政策についての詳細な知識に加えてキャッシュに提示されたトランザクションの複雑な監視を要求する。したがって、キャッシュウエイの各使用に対して、キャッシュウエイに関連した記憶ビットを更新する必要がある。この更新は、運用上のリソース使用およびエネルギー消費の点から高価である。
【００１１】
従って、ＮＲＵアプローチおよびＬＲＵアプローチの本質的に同じ性能を達成する、低価格で非常に効率的なキャッシュ交換プロセスの必要がある。低価格利点はキャッシュ交換プロセスでの必用メモリを低減することを含む。また、また、必要メモリの縮小は、DSP実施中の改善されたエネルギー消費を促進する。
【００１２】
LRUとNRUのプロセスの使用での別の考察は、マルチスレッド処理を実行するDSPの中の特別の関連である。そのようなプロセッサでは、LRUおよびNRUキャッシュ交換政策で、１つのパイプラインから次のパイプラインに記憶ビット情報を送るために繰り返し発生する必要性がある。特に各パイプライン段階の制限のあるタイムバジェット(time budget)がある場合、パイプラインからパイプラインへ記憶ビット情報を転送するコストは過度である可能性がある。すなわち、あるパイプラインステージから別のステージまでの記憶ビット情報の処理は、マルチスレッド動作の期間に望ましくないコストを要求するかもしれない。
【００１３】
また、上に言及されるように、ＬＲＵおよびＮＲＵ交換政策において必要とされる記憶ビットの処理は、記憶ビット情報を伝えるために広く大きなバスの使用を一般に必用とする。記憶ビット情報を伝える大きなバスが電力を消費し、動作遅延をひき起こすので、キャッシュウエイ交換政策でのそのような記憶ビット情報の運搬を縮小するか除去する要望がある。
【００１４】
従って、既知のLRUおよびNRUキャッシュ交換政策に対して改善する必要性が存在する。特に、そのような必要性はマルチスレッドＤＳＰまたは類似のプロセッサの動作に存在する。
【００１５】
ＤＳＰまたは類似のプロセッサの周知のキャッシュ交換プロセッサに存在する電力消費および性能遅延を低減するためのさらなる必要性が存在する。
【００１６】
それゆえ、本質的にＤＳＰまたは類似のプロセッサのキャッシュウエイ交換動作の期間に記憶ビット情報の処理を除去するための必要性が存在する。
【発明の開示】
【００１７】
本明細書に開示された技術はデジタルシグナルプロセッサのキャッシュメモリの最大のレジデンシー(residency)交換を提供する。この技術は、プロセッサの動作と、デジタルシグナルプロセッサ命令の効率的でより迅速な処理の両方を改善する。この開示は、例えば、複数のプロセッサスレッドがn-ウエイの（但し、ｎは２またはそれより大きい）セットアソシエイティブ方法でキャッシュメモリを共有するマルチスレッドプロセッサシステムに役立つかもしれないし、特に、ミスヒット(miss-hit)が生じたときに適用可能な交換制御技術に役立つかもしれない。開示された主題の使用は、パーソナルコンピュータ、パーソナルデジタルアシスタンツ、無線のハンドセット、および類似の電子装置のためのますまる堅固なソフトウェアプリケーションを可能にし、並びにプロセッサ速度とサービス品質を増大させることを可能にする。
【００１８】
開示された主題の１つの観点によれば、タグミスアロケーションに続く複数のセットウエイのレジデンシーを最大にするようにキャッシュメモリアロケーションを交換するための方法とシステムが提供される。この開示は、キャッシュメモリのビクティムウエイのファーストイン、ファーストアウト（ＦＩＦＯ）交換リスト(listing)を形成することを含む。この場合ＦＩＦＯ交換リストの深さはキャッシュセット内のウエイの数にほぼ等しい。この方法とシステムは、タグミスがタグミスアロケーションを生じるという場合にのみビクティムウエイをＦＩＦＯ交換リストに配置する。ビクティムウエイは任意の以前に選択されたビクティムウエイの後で、ＦＩＦＯ交換リストのおわりに配置される。ＦＩＦＯ交換リスト上のビクティムウエイの使用は、例えば、ビクティムウエイのそのようなイニシャルアロケーションが完了するまで再使用要求を遅らせることによって、またはビクティムウエイのそのようなイニシャルアロケーションが完了するまで、再使用要求をリプレイ(replay)することによって、ビクティムウエイの不完全な先行するアロケーションの場合には防止される。
【００１９】
開示された主題のこれらの観点および他の観点並びにさらなる新規な特徴は、本明細書に提供される記載から明白になるであろう。この要約の意図は、クレームされた主題の包括的記述にあるのではなく、主題の機能性のいくらかの短い概説を提供することである。本明細書で提供される他のシステム、方法、特徴および利点は、以下の図面および詳細な説明を検査することにより当業者に明白になるであろう。この記載内に含まれるそのようなさらなるシステム、方法、特徴および利点のすべてが添付されたクレームの範囲内にあることが意図される。
【発明を実施するための最良の形態】
【００２０】
本発明の特徴、性質及び利点は、類似による参照文字が相応して、全体で特定する図面と関連して解釈されるときに後述される詳細な説明からさらに明らかになるであろう。
【００２１】
本明細書において提示されたキャッシュメモリの最大レジデンシー交換のための方法およびシステムの開示された主題は、マルチスレッド処理を含むアプリケーションを含む、非常に多種多様なデジタルシグナルプロセッシングアプリケーションの使用を有する。１つのそのようなアプリケーションは電気通信に現れる。特に、１つまたは複数のＤＳＰ回路を採用する無線ハンドセットに現れる。従って、以下の図面は、この教示を使用してもよい電気通信ＤＳＰを記述する。しかしながら、本明細書に記載された実施は、開示された主題が適用されてもよいアプリケーションの事実上無限のセットの１つを提供することを覚えておかれたい。
【００２２】
そのような無線ハンドセットがどのように使用されてもよいかを説明する目的のために、図１は開示されたデータ処理方法およびシステムの提示された実施形態を実施してもよい通信システム１０の簡単化されたブロック図を提供する。送信器ユニット１２において、データは、典型的にブロックで、データソース１４から、データをフォーマット化し、コード化し、処理して１つまたは複数のアナログ信号を発生する送信（ＴＸ）データプロセッサ１６に送信される。次に、アナログ信号は、ベースバンド信号を変調し、濾波し、増幅し、アップコンバートして変調された信号を発生する送信機（ＴＭＴＲ）１８に供給される。次に、変調された信号はアンテナ２０を介して１つまたは複数の受信機ユニットに送信される。
【００２３】
受信機ユニット２２において、送信された信号は、アンテナ２４により受信され受信機（ＲＣＶＲ）２６に供給される。受信機２６内において、受信された信号は増幅され、濾波され、ダウンコンバートされ、復調され、デジタル化されて同相で（Ｉ）サンプルおよび（Ｑ）サンプルが発生される。次に、サンプルは、送信されたデータをリカバーするために受信（ＲＸ）データプロセッサ２８により復号され処理される。受信機ユニット２２における符号化および処理は、送信機ユニット１２において実行される符号化および処理に対して相補的な方法で実行される。リカバーされたデータは次にデータシンク３０に供給される。
【００２４】
上述した信号処理は、音声、ビデオ、パケットデータ、メッセージングおよび一方向における他のタイプの通信をサポートする。双方向通信システムは双方向のデータ送信をサポートする。しかしながら、他の方向のための信号処理は簡単のために図１には示されていない。通信システム１０は符号分割多重アクセス（ＣＤＭＡ）システム、時分割多重アクセス（ＴＤＭＡ）通信システム（例えば、ＧＳＭシステム）、周波数分割多重アクセス（ＦＤＭＡ）通信システム、または、地上リンクを介してユーザー間の音声およびデータ通信をサポートする他の多重アクセス通信システムであり得る。特定の実施形態において、通信システム10はW-CDMA規格に一致するCDMAシステムである。
【００２５】
図２は図１の送信データプロセッサ１６および受信データプロセッサ２８として機能してもよいＤＳＰ４０アーキテクチャを図示する。今一度、ＤＳＰ４０アーキテクチャは、本明細書において提示された教示と概念を効率的に使用してもよい非常にたくさんの可能なデジタルシグナルプロセッサ実施形態の中の１つの実施形態を表しているに過ぎないことが強調される。ＤＳＰ４０は、スレッドＴ０：Ｔ５が命令のセットを含むマルチスレッドプロセッサを表す。命令は、命令ユニット（ＩＵ）４２を介して命令キュー（ＩＱ）４４にキューイングされる。ＩＱ４４内の命令はプロセッサパイプライン４６に発行される準備ができている。命令キュー４４から、単一スレッド、例えばスレッドＴ０が復号および発行論理回路４８により選択されてもよい。
【００２６】
ＩＵ４２内のＩＱ４４は命令ストリームのスライディングバッファ(sliding buffer)を維持する。ＤＳＰ４０がサポートする６つのスレッドＴ０：Ｔ５の各々は別個のＩＱ４４をサポートする。この場合、各エントリーは１つのＶＬＩＷパケットまたは４つまでの個別の命令を記憶してもよい。復号および発行回路４８ロジックは、ＶＬＩＷパケット、または一度に２つまでのスーパースカラー(superscalar)命令を復号および出力するために、並びに各パイプラインＳＬＯＴ０：ＳＬＯＴ３に対して制御バスおよびオペランドを発生するために、すべてのスレッドにより共有される。また、ＰＬＣ５０も、例外を無くし、スレッドイネーブル／ディスエーブル、状態をリプレイ(replay)すること、プログラムフローを維持すること等のようなパイプラインストール(stall)状態を検出するためにすべてのスレッドにより共有される。
【００２７】
動作において、選択されたスレッドのジェネラルレジスタファイル（ＧＲＦ）５２および制御レジスタファイル（ＣＲＦ）５４が読まれ、読まれたデータはＳＬＯＴ０：ＳＬＯＴ３のための実行データ経路に送信される。この例において、ＳＬＯＴ０：ＳＬＯＴ３は、この実施形態において採用されるパケットグルーピングコンビネーション(packet grouping combination)を提供する。ＳＬＯＴ０：ＳＬＯＴ３からの出力は、ＤＳＰ４０から結果を返す。
【００２８】
本明細書に開示された主題は、単一スレッドのキャッシュ交換政策を処理する。単一スレッドは、すべてのレジスタと命令が利用可能な完全なユニプロセッサＤＳＰ４０へのアクセスを有する。コヒーレント(coherent)な共有メモリ設備を介してこのスレッドは他のスレッドと通信し同期することができる。これらの他のスレッドが同じプロセッサあるいは別のプロセッサ上で実行しているかどうかは、ユーザーレベルソフトウェアに対して大部分はトランスペアレント(transparent)である。
【００２９】
図3に変わって、DSP40のための現在のマイクロアーキテクチャ60は制御ユニット(CU)62を含む。それは、プロセッサパイプライン46のための制御機能の多くを行なう。ＣＵ６２はスレッドをスケジュールし、ＩＵ４２から１６ビットと３２ビットの混合した命令を要求する。さらに、ＣＵ６２は命令をスケジュールし、３つの実行ユニット、シフトタイプユニット（ＳＵ）６４、マルチプライ(multiply)タイプユニット（ＭＵ）６６、およびロード／ストアユニット（ＤＵ）６８に命令を発行する。CU 62はまたスーパースカラー依存チェックを行なう。バスインタフェースユニット（ＢＩＵ）７０は（図示されない）システムバスにＩＵ４２とＤＵ６８をインターフェースする。
【００３０】
SLOT0とSLOT1のパイプラインはDU 68にある。SLOT2はMU 66にある。また、SLOT3はSU 64にある。CU 62はパイプラインSLOT0:SLOT3にソースオペランドおよび制御バスを供給し、GRF 52およびCRF 54ファイル更新を行う。CU 62は、割り込みおよびリセットのような外部入力を受理し、またエミュレーションユニット(EU)72をサポートする。CU 62は、また、アドレス変換中に生じる保護違反による例外を処理する。マイクロアーキテクチャ６０の一実施形態において、混合された１６ビットおよび３２ビット命令は、一度に４つまで並列に発行できる。しかしながら、１６ビット、３２ビット、および他の長さの命令の多くの異なるバリエイションが他の実施形態において実施されてもよく、すべて開示された主題の範囲内である。さらに、マイクロアーキテクチャ６０は、サイクル毎に２つの６４ビットダブルワードをＣＵ６２から移動させることをサポートしてもよい。
【００３１】
マイクロアーキテクチャ60を使用するDSP 40は特に次の種類のアプリケーションをサポートする。
【００３２】
(1)通信信号処理(例えばモデム);
(2)ビデオ処理(例えばH.264フォーマット);
(3) イメージ処理;
(4) 音声処理;
(5) 3Dグラフィックスフロントエンドソフトウェア;
そして、(6)制御コード、プロトコルスタック、RTOSなどをサポートする。そのため、ＤＳＰ４０はＶＬＩＷ命令パケット並びに個々のスーパースカラー発行命令の両方を発行する。個々の命令のための発行幅は、発行スロットあたり１命令から最大ＶＬＩＷパケットに及ぶことができる。例示として、DSP 40は、発行スロットあたりVLIMパケット中の4つもの命令を発行してもよい。また、DSP 40はスーパースカラー発行を使用して、1つあるいは2つの命令を発行してもよい。
【００３３】
図４は開示された主題を適用してもよいブロックパーティション(block partitioning)する代表的なデータユニット、ＤＵ６８を提示する。ＤＵ６８は、ＣＵ６２からの入力を受信するためのＡＧＵ０  ８１およびＡＧＵ１  ８３をさらに含むアドレスジェネレーティングユニット、ＡＧＵ８０を含む。本明細書に開示された主題は、ＤＵ６８の動作を備えた主要なアプリケーションを有する。ロード／ストアコントロールユニット、ＬＣＵ８２は、ＣＵ６２と通信し、制御信号をＡＧＵ８０およびＡＬＵ８４に供給し、並びにデータキャッシュユニット、ＤＣＵ８６と通信する。ALU 84は、またAGU 80およびCU 62から入力を受信する。AGU 80からの出力はDCU 86に行く。DCU 86は、メモリ管理ユニット(「MMU」)87およびCU 62と通信する。ＡＬＵ８４は、各スロットに対して１つの割合でＡＬＵ０  ８５およびＡＬＵ１  ８９を含み、ＤＵ６８内の算術／転送／比較（ＡＴＣ）演算を実行するためのデータ経路を含む。
【００３４】
ＤＣＵ８６は、ＳＲＡＭ状態アレイ回路８８、ストアアライナ(store aligner)回路９０、ＣＡＭタグアレイ９２、ＳＲＡＭデータアレイ９４、およびロードアライナ回路９６を含む。クレームされた主題が動作されてもよいＤＵ６８の動作をさらに説明するために、以下の記載のいくつかのパーティションによってＤＵ６８で行なわれる基本機能がこれから言及される。特に、ＤＵ６８は、ＡＬＵ８４からのロードタイプ命令、ストアタイプ命令および３２ビット命令を実行する。
【００３５】
ＤＵ６８は、即値オペランドを含むDEパイプラインステージにおいて、CU 60から、サイクル当たり2つまでのデコードされた命令を受信する。ＲＦパイプラインステージにおいて、ＤＵ６８は適当なスレッド用レジスタから汎用レジスタ（ＧＰＲ）および／または制御レジスタ（ＣＲ）ソースオペランドを受信する。GPRオペランドは、CU 60の中のGPRレジスタファイルから受信される。EX1パイプラインステージでは、DU 68は、ロードまたはストアメモリ命令の実効アドレス(EA)を生成する。ＥＡはＭＭＵ８７に供給される。ＭＭＵ８７は、仮想アドレスから物理アドレスへのアドレス変換、およびページレベルパーミッションチェック(page level permissions checking)を行い、ページレベル属性を供給する。キャッシュ可能なロケーションにアクセスするために、ＤＵ６８は、物理アドレスを備えたEX2パイプラインステージのデータキャッシュタグを調べる。アクセスがヒットするなら、ＤＵ６８はＥＸ３パイプラインステージにおいてデータアレイアクセスを行う。
【００３６】
キャッシュロードのために、キャッシュから読み出されたデータは適当なアクセスサイズにより一列に並べられ、指定されたようにゼロ／符号により拡張され、ＷＢパイプラインステージ内のＣＵ６０に送られ、命令用のＧＰＲに書かれる。キャッシュ可能なストアのために、記憶されるデータは、ＣＵ６０内のスレッド専用レジスタから読み出される。
【００３７】
DU 68は、またDCU 86を管理するためのキャッシュ命令を実行する。命令は、特定のキャッシュラインをＧＰＲ専用キャッシュラインにロックし、アンロックし、無効にし、アロケートすることを可能にする。また、全体的にキャッシュを無効にする命令がある。これらの命令はロードおよびストア命令と同様にパイプライン化される。データキャッシュをミスしたキャッシュ可能なロケーションへのロードとストアのために、およびキャッシュ不可能なアクセスのために、ＤＵ６８は要求をＢＩＵ７０に供給する。キャッシュ不可能なロードはリードリクエストを示す。ストアヒット(store hit)、ミスおよびキャッシュ不可能なストアはリード／ライトリクエストを示す。ＤＵ６８は、現在のリードおよびラインフィルリクエスト(line fill request)をＢＩＵ７０まで追跡する。また、ＤＵ６８は他のスレッドによるアクセスを可能にし、一方現在のロードリクエストの完了まで１つまたは複数のスレッドがブロックされる。すなわち、ＤＵ６８はＤＳＰ４０コアプロセッサへのおよびＤＳＰ４０コアプロセッサからの両方のリード／ライトリクエストをサポートする。それゆえ、ＢＩＵ７０はこれらの動作のためにバスへの双方向インターフェースを提供する。
【００３８】
2つのタイプのストアがある。第１に、キャッシュに直接記憶するストア、すなわち、「ライトバック」ストアがある。また、キャッシュに記憶してもよいストアがある。しかし、それらはトランザクションをバスに送信した。「ライトスルー(write-through)」および「アンキャッシュド(uncached)」ストアは両方ともデータをバス並びにキャッシュに送信する。ストアヒット(store hit)は、ライトスルーストアのためにリード／ライトリクエストを示すであろう。ライトバックストアの場合にストアミスの場合、バス上に現れるのはリードリクエストであろう。リクエストがライトスルーなら、データは直接バスに行き、キャッシュに書かれない。
【００３９】
開示された主題は、ＤＵ６８で生じる処理のようなデジタル信号処理の期間にキャッシュ交換動作のための「ファーストインファーストアウト」または「ＦＩＦＯ」リスト処理を提供する。ここに開示されたFIFOキャッシュ交換プロセスの有効性を分析する際に、より効率的でそれほど厄介でないキャッシュ置換プロセスが存在する。これは、記憶ビットのロケーションを転送し追跡するプロセスがないにもかかわらず真実である。
【００４０】
開示されたプロセスの技術的な利点は、どのキャッシュラインが最も最近に使用されたかを追跡する必要性を回避することである。このプロセスはそのような要求を課さない。このFIFOキャッシュ交換プロセスで、利用可能なキャッシュリソースの存在を決定する必要だけがある。キャッシュメモリへのアクセス経路の連続している記録を維持することを知る必要はない。したがって、各キャッシュロードでは、NRUまたはLRUのプロセスを使用する場合、使用するべきキャッシュウエイを決定するために生じるに違いない計算がある。
【００４１】
開示された主題は、ミスが生じた場合キャッシュウエイを更新する。したがって、多くのミスが生じる場合、開示された主題のプロセスは、次のストアリクエストの場合に使用するためにキャッシュウエイを連続的に同定するように動作するであろう。他方では、キャッシュミスが生じない場合、本明細書に開示されたプロセスは、ＬＲＵまたはＮＲＵプロセスの使用がそうするように、連続的に更新しない。代わりに、次のキャッシュミスが生じるまで、現在のFIFOキャッシュ交換プロセスは待つ。すなわち、ＮＲＵおよびＬＲＵプロセスが、生じたキャッシュヒットを追跡するのに対し、本明細書に開示されたＦＩＦＯキャッシュ交換プロセスは、生じたキャッシュミスを追跡する。
【００４２】
開示された主題では、ミスが生じたときにのみ、使用すべきキャッシュウエイがあるであろう。ＦＩＦＯキャッシュ交換プロセスは、キャッシュが置換されることになっている時点でリストから置換されたキャッシュウエイによって置換されるべき次のキャッシュウエイの基礎を形成する。従って、ウエイが置換されていないなら、置換すべきキャッシュウエイのＦＩＦＯリストは変わらないであろう。ミスが生じた場合、それが事件的に最も早い時期に置換されたので、最も古いミスしたキャッシュは交換プロセスに対して最小の値である。ＦＩＦＯ交換リスト上のウエイが古くなればなるほど、キャッシュウエイがＦＩＦＯ交換リストから取り除かれる可能性が高くなる。
【００４３】
この開示はＦＩＦＯ交換プロセスのフィードバックパスの必要性を回避する。したがって、領域必要条件は2つのウエイでより小さくなる。第１に、示された内容は記憶ビットを要求しない。第２に、すべてのキャッシュリードで記憶ビットをリードする必要が存在しないので、プロセスはよりエネルギー効率がよい。さらに、記憶ビット情報を伝える際に大きなバスリード線を使用する必要はない。
【００４４】
開示された主題では、リクエストルックアップ（request lookup)がキャッシュタグミスを受信する場合、セットウエイのうちの1つは置換されなければならない。ある場合には、タグミスアロケーションに場所を空けるためにキャッシュからビクティムウエイのキャッシュコンテンツを取り除かなければならないので、交換のために選ばれるキャッシュウエイはビクティムウエイ(victime way)と呼ばれる。キャッシュ中のコンテンツが、DSP 40メインメモリ中のコンテンツとはとにかく異なる場合、これらの場合は発生する。例えば、1列に並んだストアが生じる場合、コンテンツは変わるかもしれないし、それによって、交換の必要を要求する。
【００４５】
各ウエイがキャッシュに残る時を最大限にするために、ビクティムウエイはキャッシュミスに続いてセットベースのFIFOリストのおわりに配置される。交換ＦＩＦＯリストの深さは、キャッシュセット内のウエイの数に等しく、それにより、同じウエイが再び立ち退かせられる前に、ミスアロケーションの時間またはレジデンシーを最大にする。同じセットへの後のタグミスは同様にビクティムウエイを生成し、セットFIFOのおわりに配置されるであろう。各新しいビクティムは交換ＦＩＦＯリストの先頭への初期のビクティムを強要する。同じセットのビクティムの数がキャッシュウエイの数と等しいとき、ビィティムウエイは次のタグミスで再使用される。
【００４６】
本明細書に開示されるようなFIFO交換政策の実施は2つの規則を満たす。最初に、その実施は、各セット中のウエイの数に基づいたキャッシュレジデンシー(residency)を最大限にしなければならない。これは、タグミスがアロケーションを生じる場合にのみビクティムウエイをセットＦＩＦＯリスト上に配置することにより遂行される。現在のアロケーションリクエストが先行するタグミスに対して既に存在する場合、現在のタグミスはFIFOリストを更新しない。任意の実施によって執行されなければならない第2の規則はキャッシュコヒーレンシー(coherency)に関係がある。
【００４７】
その事例において、ビクティムウエイがＦＩＦＯリストのおわりに配置されているとき、同じウエイが先頭に達し、イニシャルアロケーションが完了するまえに再使用されるであろう。ビクティムウエイ法再使用が修正されない場合、このハザード(hazard)は、タグとデータのキャッシュ間のインコヒーレンシー(incoherency)をひき起こすかもしれない。このハザードへのいくつかの解決法は、再使用リクエストを遅らせるかリプレイすること、または再使用ウエイがＦＩＦＯリストのおわりに配置された後２度目にＦＩＦＯリストの先頭を読むことを含んで、存在する。
【００４８】
高度に待ち時間が寛容でないソフトウェアプリケーションを用いた処理環境において、開示された主題は処理時間を低減し、記憶ビットロケーションを追跡することを回避する。
【００４９】
そのような処理環境は、ストリームビデオおよびデータアプリケーションを提出する処理環境ならびに即時のトーンフィードバック(tone feedback)、例えば無線ハンドセットキーパッドが押されるとウエイファイルテーブルからのデータを再生する処理環境を含んでいてもよい。
【００５０】
ストリームビデオの別の例では、毎秒20＋の画像フレームのフローが無線ハンドセットスクリーンに現われているかもしない。画像フレームにおいて、流れているフレームの一部は有用な情報を含み、一方フレームの他の部分は冗長な情報を含む。情報が冗長であるかまたは新しい情報であるかどうかを決定するための能力およびタイミング考察は、処理リソースの効率的な使用に対して重要になり得る。
【００５１】
このイントロダクションで、2つの実施が図５および図６に記載されるであろう。これらの実施は図５のＩＵ４２プロセスおよび図６のＤＵ６８プロセス１０２内のＤＳＰ４０のようなデジタルシグナルプロセッサにおいて使用されてもよい。それゆえ、第１にＩＵ４２プロセス１００を考察する。このプロセスにおいて、ＩＵ４２はタグルックアップ(tag lookup)（ステップ１０４）を実行し、タグミスが生じるかもしれない（ステップ１０６）。そのような場合、リクエストアドレスは、現在のリクエストバッファ（ＯＲＢ）に記憶されたアクティブリクエストと比較される（ステップ１０８）。ルックアップアドレスがユニークな場合(ステップ110)、リクエストは主要なミス(PM)(ステップ112)と考えられる。PMアドレスはアロケーション(ステップ114)のためにシステムメモリに送られる。また、交換FIFOリストはビクティムウエイ(ステップ116)用に読まれる。ビクティムウエイがこのセットアドレスにすでに使用されている場合、アドレスは以前に前のリクエスト(ステップ118)によってシステムメモリに送られた。そのリクエストは第2のミス(SM)(ステップ120)と考えられる。この場合、交換FIFOリストは読まれない。また、キャッシュレジデンシーは最大限にされる(ステップ122)。
【００５２】
問い合わせ110から、YESパスはステップ112に行く。そこでは、リクエストはPMか主要なミスであることが決定される。リクエストが主要なミスである場合、ビクティムウエイはステップ114においてアロケーションのためにFIFOバッファに記憶される。次に、ステップ116において、FIFOリストは次のビクティムウエイのために読まれる。ステップ116から、プロセスフロー100は両方のステップ126および130に行く。ステップ126において、FIFOリストの先頭は、リストのおわりに配置される。また、ステップ128において、ビクティムウエイはラストウエイ(lastway)バッファに記憶される。ステップ１３０において、プロセスフロー１００は、ビクティムウエイ再使用ハザードの存在を決定する。これは、現在／入力ビクティムウエイを他のラストウエイバッファと比較する（ステップ１３２）ことを含む。ビクティムウエイが一致し、セットアドレスが一致するなら、再使用ハザードが存在する。これは、キャッシュ交換アルゴリズムが、すでにアロケートされたキャッシュウエイを使用しようとしていることを意味する。また、プロセス（ステップ１３６）は入力ＰＭのセットアドレスを他のスレッドセットアドレスと比較する。ステップ１３２に応答して問い合わせ１３４において、またはステップ１３６に応答してステップ１３８において、ヒットが検出されるなら、プロセスフローはＯＲステップ１４０に続く。ＯＲステップ１４０は、現在の／入ってくるスレッドがリプレイされるステップ１４２に入力を供給する。リプレイされたスレッドがＰＭなら、プロセスフロー１００はステップ１４６に続く。そうでなければ、プロセスフロー１００は、そのリクエストが二次ミス（ＳＭ）であると決定する（ステップ１２０）。プロセスフロー１００はＦＩＦＯリストを読むので（ステップ１４６）、新しいビクティムウエイがＦＩＦＯリストの先頭から検索される（ステップ１４８）。
【００５３】
それゆえ、再使用ハザードが存在するとき、プロセスフロー１００は現在のスレッドをリプレイする。次のときにスレッドは戻り、再びミスをするであろう。次に、プロセスフローは、ＦＩＦＯが示す現在のウエイがすでに使用されていると決定するであろう。プロセスフローが同じウエイを再び返すなら、再使用ハザードが存在する。プロセスが同じウエイをＦＩＦＯリストから再び供給するなら、現在のリクエストは、返されたスレッドがすでに参照されており、スレッドがリプレイされると決定するであろう。スレッドは戻り、再びリプレイするであろう。FIFOリストは、したがって、1だけインクリメントされた最後のサイクルにそれが与えたものすべてを提供する。再使用ハザードを実証しないビクティムウエイがあるまで、同じプロセスが続く。再使用ハザードを実証しない最初のビクティムウエイはプロセスフロー100が使用するウエイになるであろう。
【００５４】
ビクティムウエイアロケーションのための決定の後に交換FIFOリストアクセスをパイプラインで送ることによって、IU 42は、同じクロックでＦＩＦＯリストの先頭からおわりにビクティムウエイを直ちに移動させることができる。これは、リプレイなしで交換ＦＩＦＯリスト内の連続するマルチスレッドアクセスをサポートすることを可能にする。
【００５５】
セットアドレスとビクティムウエイがヒットし、両方がＰＭリクエストなら（ステップ１４０）、若いほうのまたは入ってくるスレッドがリプレイされる（ステップ１４２）。スレッドがリプレイされ、ＰＭであると再び決定されると（ステップ１４４）、交換ＦＩＦＯリストが読まれ（ステップ１４６）、新しいビクティムウエイが先頭から検索される（ステップ１４８）。
【００５６】
IUは、交換ＦＩＦＯリストを簡単な４ビットカウンタとして実施する。各ＰＭは交換セットカウンタを読み、セットカウンタを１だけインクリメントする。セットカウンタは常にＰＭでインクリメントされ、ハザードをヒットしたスレッドがリプレイされる前に再使用ハザードをクリアする。
【００５７】
図６は、ＤＵ６８に適用されるこの開示のＤＵプロセス１０２内のステップを詳述する。ＤＵ６８がリクエストルックアップを実行すると（ステップ１５０）、タグ、状態、および交換リストが同時に読まれる（ステップ１５２）。ヒットベクトルまたは状態ベクトルを用いて一次のまたは二次のミスを決定する（ステップ１５４）。状態／ＦＩＦＯリストリードと状態／ＦＩＦＯリストライトとの間には遅延があるので、リクエストセットアドレスはより若いスレッドとの比較のためにパイプラインで送られる。セットアドレスヒットが２つのリクエストの間に生じるなら（ステップ１５８）、より若いスレッドがリプレイされるかもしれない（ステップ１６０）。それゆえ、タグミスが検出されるなら（ステップ１６２）、すなわち、状態が保存されていないなら、セットアドレスはより古いセットアドレスと比較され（ステップ１６４）、より若い／入力されるスレッドがリプレイされなければならないかどうかが決定される（ステップ１６６）。そうでなければ、FIFOリストは読まれない。ビクティムウエイ再使用ハザードを検出するために、DUは、ビクティムウエイ（すなわち、ＦＩＦＯリストの先頭にあるウエイ）を状態ベクトルと比較する（ステップ１６８）。ビクティムウエイが同じウエイで保存された状態をヒットするなら、以前のリクエストキャッシュウエイを保存し、ビクティムウエイ再使用が検出される（ステップ１７０）。そうでなければ、FIFOリストは読まれない。セットアドレスがユニークで、ビクティムウエイ再使用ハザードが無いなら（ステップ１７４）、リクエストは真のＰＭであり、アロケーションのためにシステムメモリに送られる（ステップ１７６）。そうでなければ、FIFOリストは読まれない。
【００５８】
この実施形態では、ＤＵ６８は交換ＦＩＦＯリストを更新することができ、最大キャッシュレジデンシー(residency)とキャッシュコヒーレンシー(coherency)を維持することができる。しかしながら、上述したように、他の実施は、交換ＦＩＦＯリスト内の連続マルチスレッドアクセスを更新しないかもしれない。前記のことは、正確な状態およびＦＩＦＯリスト情報がセットに書き戻されるまで正確な状態およびＦＩＦＯリスト情報を維持するように、状態と交換バイパスの追加が機能する場合、生じるかもしれない。
【００５９】
ＩＵ４２がそうであるように、ＤＵ６８もまた、簡単な４ビットカウンタとして交換ＦＩＦＯリストを実施する。各ルックアップは交換セットカウンタをリードし、リクエストがＰＭであるかどうか決定する。ＰＭの決定に続いて、交換カウンタが１だけインクリメントされ、更新された状態情報とともにセットカウンタに書き戻される。セットカウンタは再使用ハザードでインクリメントされるであろう。ビクティムウエイ再使用ハザードがリプレイされると、新しいカウントがルックアップ上で検索され、ハザードがクリアされるであろう。
【００６０】
それゆえ、開示された主題は、キャッシュタグミスの場合には、キャッシュセットの複数のセットウエイの１つを交換するための方法を提供する。この開示は、キャッシュミスに続いてキャッシュセットＦＩＦＯリストのおわりにビクティムウエイを配置することにより交換されるキャッシュウエイとしてビクティムウエイを選択するステップを含む。この場合、ＦＩＦＯの深さは、キャッシュセット内のウエイの数にほぼ等しい。次に、プロセスは、キャッシュセットについての次のキャッシュタグミスをキャッシュセットＦＩＦＯリストの終わりに配置する。したがって、プロセスは、キャッシュセットのビクティムウエイの数がキャッシュセットウエイの数に等しい場合に次のキャッシュタグミスでビクティムウエイを再使用することを含む。ビクティムウエイのイニシャルアロケーションが完了するまでビクティムウエイの再使用は防止される。これは、キャッシュタグとキャッシュセットとの間のインコヒーレンシー(incoherency)を回避する。さらに、プロセスは、ビクティムウエイのそのようなイニシャルアロケーションが完了するまで再使用リクエストを再び行うことによりビクティムウエイのイニシャルアロケーションが完了するまでビクティムウエイの再使用を防止する。また、プロセスは、ビクティムウエイのそのようなイニシャルアロケーションが完了するまで再使用リクエストをリプレイすることによりビクティムウエイのイニシャルアロケーションが完了するまでビクティムウエイの再使用を防止する。このプロセス、および実質的にそれに類似したプロセスを実行することにより、開示された主題は、周知のＬＲＵおよびＮＲＵアルゴリズムの既存の制限を回避する効率的なキャッシュウエイ交換政策を、実施する回路とともに、提供する。
【００６１】
本明細書に記載された処理特徴および機能は種々の方法で実施することができる。例えば、ＤＳＰ４０は上述した動作を実行できるだけでなく、この実施形態は、特定用途向け集積回路（ＡＳＩＣ）、マイクロコントローラー、マイクロプロセッサ、または本明細書において記載された機能を実行するように設計された他の電子回路において実施されてもよい。それゆえ、好適実施形態の上述した記述は当業者がクレームされた主題を製作または使用可能にするために提供される。これらの実施形態への様々な変形は当業者に容易に明白であろう。また、ここに定義された総括的な法則は、革新的な機能の使用のない他の実施形態に適用されてもよい。したがって、クレームされた主題は、ここに示された実施形態に制限されることを意図したものではなく、ここに開示された原理と新規な特徴と一致する最も広い範囲が与えられるべきである。
【図面の簡単な説明】
【００６２】
【図１】図１は、この実施形態を実施することができる通信システムの簡単化されたブロック図である。
【図２】図２は、この実施形態の教示を実行するためのＤＳＰアーキテクチャを示す。
【図３】図３は、この開示の教示を採用するシステムにおいて動作されてもよい制御ユニット（ＣＵ）のブロック図を示す。
【図４】図４はこの開示のキャッシュウエイ交換プロセスを採用してもよい例示回路としてデータユニット（ＤＵ）のブロック図を示す。
【図５】図５は、図３で示されるような命令ユニット（ＩＵ）においてこの開示の使用を教示するためのフローチャートの１つの実施を詳細に示す図である。
【図６】図６は図３に図示されるデータユニット（ＤＵ）における現在開示されている主題の他の使用のためのフローチャートの実施を詳細に示す図である。
【図１】
2009537912.tif 000003
【図２】
2009537912.tif 000004
【図３】
2009537912.tif 000005
【図４】
2009537912.tif 000006
【図５】
2009537912.tif 000007
【図６】
2009537912.tif 000008
【国際調査報告】
2009537912.tif 000009
2009537912.tif 000010
2009537912.tif 000011