JP4173858B2 - 命令キャッシュ、及びメモリ競合を低減する方法 - Google Patents

Description

本発明は、命令キャッシュ及びその動作方法に関し、詳細にはキャッシュ・メモリにおける競合を低減することに関する。

キャッシュ・メモリは、処理システムの性能を改善するため用いられ、そして多くの場合ディジタル信号プロセッサ（ＤＳＰ）・コアと一緒に用いられる。通常、キャッシュ・メモリは、外部メモリ（多くの場合遅い）とＤＳＰコアの速い中央処理装置（ＣＰＵ）との間に配置される。キャッシュ・メモリは、典型的には、要求次第で迅速にＣＰＵに与えることができて且つ頻繁に用いられるプログラム命令（又はコード）のようなデータを格納する。キャッシュ・メモリの内容は、（ソフトウエア制御の下で）フラッシュされ、そしてＤＳＰコアによる引き続いての使用のため新しいコードでもって更新される。

図１において、命令キャッシュ２の一部を形成するキャッシュ・メモリ１は、外部メモリ４に格納されているコードでもって（更新バス３を介して）更新される。ＤＳＰコア５は、命令キャッシュ２及びそのキャッシュ・メモリ１にプログラム・バスを経由してアクセスする。ＤＳＰコア５がキャッシュ・メモリ１に既に格納されているコードを要求する場合、これを「キャッシュ・ヒット」と呼ぶ。逆に、ＤＳＰコア５がキャッシュ・メモリ１に現在格納されていないコードを要求する場合、これを「キャッシュ・ミス」と呼ぶ。「キャッシュ・ミス」は、外部メモリ４からの要求されたコードの「フェッチ」を要求する。この「フェッチ」動作は、コードを直接キャッシュ・メモリ１からアクセスするタスクと比較して、非常に時間を消費する。従って、「ヒット対ミス」比が高ければ高いほど、ＤＳＰの性能は一層良い。従って、この比を増大する機構は有利であろう。

同時係属中の米国特許出願ＵＳ ０９／９０９，５６２はプリフェッチ機構を開示し、そのプリフェッチ機構により、プリフェッチ・モジュールは、キャッシュ・ミスの際に、要求されたコードを外部メモリからフェッチし、そしてそれをキャッシュ・メモリにロードし、次いでＤＳＰが次にどのコードを次に要求するかを推測し、そしてまたそのようなコードを外部メモリからキャッシュ・メモリにロードする。このプリフェッチ・コード・アドレスは、キャッシュ・ミスのアドレスに連続している。しかしながら、競合は、（ＤＳＰにより要求されるとき）コードをキャッシュ・メモリから読み出すこととキャッシュ・メモリを（プリフェッチ動作の結果として）更新することとの同時の試みに起因してキャッシュ・メモリで生じる場合があり得る。即ち、全ての読み出し及び書き込みが並行して実行されることができるとは限らないことである。従って、競合しているアクセス源の１つが機能停止（ｓｔａｌｌ）され又はアボート（中途停止）されねばならないので、ＤＳＰコアの性能の劣化がある場合がある。更に、ＤＳＰコアのアクセス及びプリフェッチの両方の順次的性質に起因して、競合状況は、幾つかのＤＳＰ動作サイクルにわたり継続する場合があり得る。

メモリ・インターリービングは、この問題を一部改善することができる。米国特許出願明細書ＵＳ−Ａ−４，８１８，９３２は、アクセスされるべきメモリ位置のアドレスの最下位ビット（ＬＳＢ）の状態に従って奇数バンクと偶数バンクとに編成されるランダム・アクセス・メモリ（ＲＡＭ）を開示する。この構成は、ＲＡＭへのアクセスが競合する２又はそれより多くの処理装置のため待ち時間を低減する。しかしながら、キャッシュ・メモリの更新及びＤＳＰの要求の順次的性質に起因して、メモリ・インターリービングのみでは、完全には競合の可能性を除去できない。

従って、そのような競合の発生率を低減する更なる改善の必要性が存在する。

本発明の第１の局面に従って、プロセッサ・コアと外部メモリとの間の接続のための命令キャッシュであって、各サブブロックがメモリ・アドレスの１又はそれより多い最下位ビットにより区別可能である少なくとも２つのサブブロックから成るキャッシュ・メモリと、要求されるデータ・シーケンスを前記キャッシュ・メモリから読み出す要求を前記プロセッサ・コアから受け取る手段と、前記キャッシュ・メモリに書き込むため前記外部メモリから受け取られた更新データ・シーケンスを前記要求されるデータ・シーケンスに対して時間的にシフトさせることにより、前記キャッシュ・メモリのサブブロックにおける読み出し／書き込みの競合を低減するバッファとを含む命令キャッシュが提供される。

本発明の第２の局面に従って、プロセッサ・コアと外部メモリとの間に接続されるキャッシュ・メモリにおける読み出し／書き込みの競合を低減する方法であって、前記キャッシュ・メモリが少なくとも２つのメモリ・サブブロックから成り、各メモリ・サブブロックがメモリ・アドレスの１又はそれより多い最下位ビットにより区別可能である、前記方法において、
前記プロセッサ・コアから、要求されるデータ・シーケンスを前記キャッシュ・メモリから読み出す要求を受け取るステップと、
前記キャッシュ・メモリに書き込むための更新データ・シーケンスを前記外部メモリから受け取るステップと、
更新データをバッファリングすることにより、前記要求されるデータ・シーケンスに対して前記更新データ・シーケンスを時間的にシフトさせることにより、前記キャッシュ・メモリのサブブロックにおける読み出し／書き込みの競合を低減するステップと
を備える方法が提供される。

本発明は、コア・プログラムの要求及び外部更新が大部分の時間の間順次的であるという仮定に基づいている。
一実施形態において、キャッシュ・メモリは、２つのサブブロックに分割され、そこでは、一方が偶数アドレスのため用いられ、他方が奇数アドレスのため用いられる。このようにして、競合は、コアの要求及び更新の両方が同じパリティ・ビットを用いてアドレスすることになる場合のみ起こる場合がある。

一般に、メモリ・サブブロックは、アドレスの最下位ビットにより区別される。しかしながら、単に複数のメモリ・サブブロックを設けることは、メモリ・サブブロックが１つの読み出し（ＤＳＰコアに対して）か、又は１つの更新（プリフェッチ・ユニットを介した外部メモリから）かの一方しかサポートすることができないので、全てのケースにおいて、プリフェッチ・ユニットを介した順次的更新がＤＳＰコアからの順次的要求と競合することを防止することができない。

バッファは、更新対ＤＳＰコア要求の有り得るシーケンスを壊す単一の競合をバッファするよう働く。バッファのエントリ／入力ポートは、キャッシュ・メモリの更新バス・ポートに接続され、そして全てのサブブロックに供給するよう構成され得る。

従って、本発明は、最小のバッファリングを特定のメモリ・インターリーブと組み合わせ、それは非常に小さいコア性能不利益（ｐｅｎａｌｔｙ）をもたらす。
一実施形態においては、バッファは、更新バスをサイクル毎にサンプリングする。しかしながら、キャッシュ・メモリに書き込まれたデータ・シーケンスは、バッファリングされたデータであることが常に必要であるわけではない。例えば、書き込み動作を遅延させる理由が無い場合には、更新データは、バッファをバイパスすることにより、直接キャッシュ・メモリに書き込まれる。従って、バッファを介するか、又は直接に外部メモリからかのいずれかでキャッシュ・メモリの中へ流れる更新データの多重化が存在する。バッファからか又はバッファをバイパスするルートからかのいずれかでデータ・シーケンスを選択する選択器手段が設けられる。

メモリ競合のケースにおける調停機構は単純である。競合が外部バス間にある場合、本発明は、更新バスをバッファするよう働き、そしてコアのため働くか、さもないとコアを機能停止し、そしてバッファのデータをキャッシュ・メモリに書き込むよう働く。

本発明はまた、プロトコルを定義する何かのシーケンスを用いる必要性を排除する。シーケンスは、本発明により任意の他の入力として本来的に認識され、そして処理される。コア及び外部メモリに対するインターフェースがまた非常に単純にすることができる。外部メモリは、全てのキャッシュ調停に気づかないままでいて、そしてコアが機能停止信号しか必要としない。

上記の利点により、本発明はメモリの非常に大きいアレイのシステム構成にスムーズに適合することが可能になる。また、単一段のバッファしか必要でない。更なる不利益の低減が、大きな再設計無しで、キャッシュのメモリをより小さいサブブロックに分割しそしてインターリーブのため一層多くの最下位ビットを用いることにより達成されることができる。

本発明の幾つかの実施形態が、ここで例示としてのみ、図面を参照して説明されるであろう。

図２において、ＤＳＰコア６は、プログラム・バス８を介した命令キャッシュ７へのアクセスを獲得することができる。命令キャッシュ７は、マルチプレクサ・モジュール９、入力バッファ１０及びキャッシュ・メモリ１１を含む。キャッシュ・メモリ１１は、偶数・アレイ・メモリ・サブブロック１２及び奇数アレイ・メモリ・サブブロック１３、及びアレイ論理モジュール１４を備え、後者のアレイ論理モジュール１４は、プログラム・バス８及びメモリ・ブロック１２，１３に接続される。アレイ論理モジュール１４はまた、マルチプレクサ・モジュール９と、命令キャッシュ７の外にあるプリフェッチ・ユニット１５とに接続される。プリフェッチ・ユニット１５は、入力バッファ１０、マルチプレクサ・モジュール９及び更新バス１６への接続を有する。外部メモリ１７は、更新バス１６に接続される。

入力バッファ１０は、常に、更新バス１６をプリフェッチ・ユニット１５を介してサンプリングし、そして入力バッファ１０は、各キャッシュ・メモリ・サブブロック１２，１３が競合状態の読み出し動作が完了してしまうまで例えばプリフェッチ・ユニット１５によりフェッチされたコードをバッファリングすることにより交互のＤＳＰクロック・サイクルで更新（書き込み）動作とアクセス（読み出し）動作とを交互に行うことを可能にする。

プリフェッチ・ユニット１５は次のように動作する。ＤＳＰコア６が、実際にはいずれのメモリ・サブブロックにも無いコードへキャッシュ・メモリ１１からアクセスを要求する要求をアレイ論理モジュール１４を介して送るとき、ミス指示が、アレイ論理モジュール１４からプリフェッチ・ユニット１５へ送られる。このミス命令を受信すると、プリフェッチ・ユニット１５は、ミス・アドレスから始まる外部メモリ１７からの１ブロックのコードを（順次的に）フェッチすることを開始する。ブロックのサイズは、通常２以上のコア要求であるユーザが形成可能のパラメータである。従って、単一のキャッシュ・ミスは、入力バッファ１０を介したキャッシュ・メモリ１１への一連の順次的更新を発生する。更新（即ち、レイテンシー（待ち時間））間のタイミングは、外部メモリ１７に達するため及び要求されたコードが入力バッファ１０に到達するためプリフェッチ・ユニット１５から連続的な更新要求を取る時間に依存する。更新同士は、幾つかのＤＳＰ動作サイクル離間し得る。しかしながら、本発明は、それ自体レイテンシー及びバーストの能力に関する限り異なる外部メモリ挙動を有するディジタル信号処理システムでの使用に適合させることができる。

アレイ論理モジュール１４が、読み出し／書き込みの競合が存在することを検出するとき、それは、信号をマルチプレクサ・モジュール９に送って、入力バッファ１０に現在格納されているデータ・シーケンスをキャッシュ・メモリ１１にロードする。競合が存在しないとき、アレイ論理モジュール１４は、マルチプレクサ・モジュール９に、データをキャッシュ・メモリ１１の中へ直接プリフェッチ・ユニット１５からロードするよう命令する。

図３は、更新間の高いレイテンシーがあるケースにおいて図２の処理システムの動作を示す。各ＤＳＰクロック・サイクルで、偶数メモリ・アレイと奇数メモリ・アレイとの間で交互に切り替わる読み出しシーケンスＰ０，Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５と、偶数メモリ・アレイと奇数メモリ・アレイとの間でまた切り替わる書き込みシーケンスＵ０，Ｕ１，Ｕ２，Ｕ３，Ｕ４とが示されている。クロック・サイクルＴ０の間、更新バスは、偶数メモリ・アレイにローディングするためのコードＵ０を搬送し、そしてＤＳＰはたま、コードＰ０を偶数メモリ・アレイから読み出すことを希望する。従って、内部の競合Ｐ０−Ｕ０が存在するであろう。これを改善するため、バッファは、ＤＳＰが奇数メモリ・アレイにアクセス（Ｐ１を読み出す）している間に、Ｕ０を１クロック・サイクルＴ０の間格納し、そして次いでそれ（メモリ書き込み）を偶数メモリ・アレイに後続のクロック・サイクルＴ１の間にロードする。同様に、後続の読み出し／書き込みシーケンスＰ１−Ｐ５及びＵ１−Ｕ４は、性能の不利益無しで並行して実行される。従って、更新シーケンスを１サイクルだけバッファによりシフトし、且つ偶数／奇数メモリ・インターリービングを利用することにより、両方のシーケンスを、任意のコア機能停止無しに処理することができる。

図４は、更新間の大きいレイテンシーを有する処理システムにおける本発明の動作を示し、そして偶数メモリ・アレイと奇数メモリ・アレイとの間で各ＤＳＰクロック・サイクルで交互に切り替わる読み出しシーケンスＰ０，Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５を示す。書き込みシーケンスＵ０，Ｕ１は、３クロック・サイクル後に偶数メモリ・アレイと奇数メモリ・アレイとの間で交番する。クロック・サイクルＴ０及びＴ３中に、内部競合Ｐ０−Ｕ０及びＰ３−Ｕ１の可能性がある。これを改善するため、入力バッファは、競合する更新（メモリ書き込み）を１クロック・サイクルだけシフトするよう動作し、それによりＵ０及びＵ１は、バッファから書き込まれ、一方Ｐ１及びＰ４は読み出されている。従って、コア機能停止が回避される。

図５は、シフトされた更新が新しいコア要求と衝突するそれらのケース、即ち、２つの連続的なコア要求が同じ最下位ビットを有するときＤＳＰコアが機能停止されるケースを示す。そのようなケースにおいてさえ、本発明は、新しいコアのシーケンスがここで更新シーケンスに対してシフトされるので、不利益を１個のＤＳＰクロック・サイクルへ低減する。この例における読み出しシーケンスは、それぞれ、第１のクロック・サイクルＴ０の間にＰ０であり、クロック・サイクルＴ１及びＴ２の間にＰ４であり、クロック・サイクルＴ３，Ｔ４及びＴ５の間にＰ５，Ｐ６，Ｐ７である。更新は、クロック・サイクルＴ０，Ｔ１，Ｔ２，Ｔ３及びＴ４のそれぞれの間のＵ０，Ｕ１，Ｕ２，Ｕ３，Ｕ４から成る。従って、いずれのバッファリング無しに、クロック・サイクルＴ０，Ｔ２，Ｔ３及びＴ４の間に競合（及びコア機能停止）の可能性が存在する。更新シーケンスを１クロック・サイクルだけ（入力バッファの活動により）シフトすることにより、呼び出し機能停止を丁度１クロック・サイクルまで低減することができる。

図１は、既知の命令キャッシュ構成のブロック図である。 図２は、本発明に従った命令キャッシュを含む処理システムのブロック図である。 図３は、３つの異なる環境のうちの１つの環境の下での本発明の動作を説明するタイミング図である。 図４は、３つの異なる環境のうちの別の１つの環境の下での本発明の動作を説明するタイミング図である。 図５は、３つの異なる環境のうちの更に別の環境の下での本発明の動作を説明するタイミング図である。

Claims (4)

1. プロセッサ・コアと外部メモリとの間の接続のための命令キャッシュであって、
   各サブブロックがメモリ・アドレスの１又はそれより多い最下位ビットにより区別可能である少なくとも２つのサブブロックから成るキャッシュ・メモリと、
   要求されるデータ・シーケンスを前記キャッシュ・メモリから読み出す要求を前記プロセッサ・コアから受け取る手段と、
   前記キャッシュ・メモリに書き込むため前記外部メモリから受け取られた更新データ・シーケンスを前記要求されるデータ・シーケンスに対して時間的にシフトさせることにより、前記キャッシュ・メモリのサブブロックにおける読み出し／書き込みの競合を低減するバッファと
   を含む命令キャッシュ。
2. 前記キャッシュ・メモリは、一方が偶数アドレスを有し、他方が奇数アドレスを有する２つのサブブロックに分割されている請求項１記載の命令キャッシュ。
3. 前記バッファからか、又は前記バッファをバイパスするルートを介して直接に前記外部メモリからかのいずれかから、前記キャッシュ・メモリに書き込むための更新データ・シーケンスを選択する手段を更に含む請求項１又は２記載の命令キャッシュ。
4. プロセッサ・コアと外部メモリとの間に接続される命令キャッシュ・メモリにおける読み出し／書き込みの競合を低減する方法であって、前記キャッシュ・メモリが少なくとも２つのメモリ・サブブロックから成り、各メモリ・サブブロックがメモリ・アドレスの１又はそれより多い最下位ビットにより区別可能である、前記方法において、
   前記プロセッサ・コアから、要求されるデータ・シーケンスを前記キャッシュ・メモリから読み出す要求を受け取るステップと、
   前記キャッシュ・メモリに書き込むための更新データ・シーケンスを前記外部メモリから受け取るステップと、
   入力データをバッファリングすることにより、前記要求されるデータ・シーケンスに対して前記更新データ・シーケンスを時間的にシフトさせることにより、前記キャッシュ・メモリのサブブロックにおける読み出し／書き込みの競合を低減するステップと
   を備える方法。

Images