JP2008107983A

JP2008107983A - キャッシュメモリ

Info

Publication number: JP2008107983A
Application number: JP2006288862A
Authority: JP
Inventors: Satoru Chiba; 哲千葉; Takumi Kato; 匠加藤
Original assignee: NEC Electronics Corp
Current assignee: NEC Electronics Corp
Priority date: 2006-10-24
Filing date: 2006-10-24
Publication date: 2008-05-08
Also published as: US20080098174A1; US7836253B2; GB2443298B; KR100955433B1; GB2443298A; KR20080036940A; GB0719926D0

Abstract

【課題】多段パイプライン構造のキャッシュメモリにおいて、連続するメモリアクセスを効率的に処理可能とする。
【解決手段】キャッシュメモリ１は、第１ステージで、タグメモリ１１からのタグアドレスの読み出しを実行する。第２ステージで、ヒット判定部１２によるヒット判定を実行する。キャッシュヒットの場合には、第３ステージ以降で、データメモリ１０からのデータ読み出しと、データメモリ１０から読み出されたデータのプロセッサ２への出力を実行する。一方、ミスヒットの場合には、第３ステージで、コントローラ１３によるタグメモリ１１の更新制御及びタグメモリ１１を迂回してアドレスラッチ１７の保持データをヒット判定部１２に入力するためのセレクタ１９の制御を実行し、第４ステージ以降で、主記憶３からのデータ読み出しによるデータメモリ１０の更新と、主記憶３から読み出されたデータのプロセッサ２への出力を実行する。
【選択図】図１

Description

本発明は、プロセッサによるメモリアクセスを複数の処理ステージに分割されたパイプラインにより処理するキャッシュメモリに関する。

クロック同期式ＳＲＡＭ（シンクロナスＳＲＡＭ）等を利用し、パイプライン構造を採用したキャッシュメモリが実用化されている。このようなパイプライン構造を有するキャッシュメモリは、プロセッサと低速メモリの間に配置され、プロセッサによるメモリアクセスを複数の処理ステージに分割されたパイプラインにより処理する（例えば特許文献１を参照）。ここで、パイプライン構造のキャッシュメモリにメモリアクセス要求を行うプロセッサは、典型的にはＲＩＳＣ（Reduced Instruction Set Computer）方式のマイクロプロセッサであるが、ＣＩＳＣ（Complex Instruction Set Computer）方式のプロセッサである場合や、音声処理や画像処理等のデジタル信号処理を行うＤＳＰ（Digital Signal Processor）である場合もある。また、パイプライン構造のキャッシュメモリが２次キャッシュ以下で使用される場合であれば、当該キャッシュメモリにメモリアクセス要求を行うプロセッサは、上位キャッシュメモリとなる。

キャッシュメモリのパイプラインステージ数を増加させることによりスループットの向上が期待できるが、その半面、キャッシュアクセス時間、つまり、プロセッサがアクセス要求をキャッシュメモリに与えてから結果が得られるまでの時間は増加することになる。このようなキャッシュアクセス時間の増加が敬遠されるために、キャッシュメモリのパイプラインステージ数は２段であることが一般的である。

一方、キャッシュメモリの消費電力を削減するために、特にセットアソシアティブ方式のキャッシュメモリにおいては、ロード要求に応答してデータメモリの全てのウェイからデータの読み出しを行うのではなく、ヒットしたウェイにのみアクセスしてデータの読み出しを行う構成も知られている。

２段パイプライン構造を有する従来のキャッシュメモリの構成例を図５に示す。図５に示すキャッシュメモリ８は、プロセッサ２と低速メモリである主記憶３との間に設けられた４ウェイ・セットアソシアティブ方式のキャッシュメモリである。キャッシュメモリ８とプロセッサ２との間は、アドレスバス４、データバス５及びＷＡＩＴ信号線７により接続されている。また、キャッシュメモリ８と主記憶３の間はメモリバス６により接続されている。

キャッシュメモリ８が有するデータメモリ１０は、主記憶３に格納されているデータの部分集合に相当するデータを格納するためのメモリである。データメモリ１０の記憶領域は、物理的又は論理的に４つのウェイに分割されている。また、各ウェイはさらにラインと呼ばれる複数ワードのデータ格納単位により管理される。データメモリ１０のデータ格納位置は、アドレスバス４から入力される入力アドレスの下位部分をデコードすることによって指定される。具体的には、入力アドレスの下位部分の上位側であるインデックスアドレスによりラインが指定され、入力アドレスの最下位部分であるワードアドレスによりライン内でのワード位置が指定される。入力アドレスの一例を図７に示す。ワードアドレス、インデックスアドレス及び上位部分のタグアドレスのそれぞれのビット数は、キャッシュメモリ８のウェイ数、１ウェイに含まれるライン数、及び１ラインに含まれるワード数をどのように設計するかに応じて定められる。

タグメモリ１１は、データメモリ１０にライン単位で格納されているデータに対応するタグアドレスを格納するメモリである。タグメモリ１１は、入力アドレスに含まれるインデックスアドレスによってアクセスされ、インデックスアドレスをデコードすることにより特定されたタグアドレスを出力する。なお、キャッシュメモリ８は４ウェイ方式であるため、１つのインデックスアドレスに対し４つのウェイに対応する４つのタグアドドレスを出力する。また、タグメモリ１１は、格納されたタグアドレスの有効性を示すバリッドフラッグ（不図示）と、ストアアクセスによりデータメモリ１０が更新されたことにより、データメモリ１０の保持データと主記憶３の保持データの間に不整合が生じていることを示すダーティフラグ（不図示）を保持している。

ヒット判定部１２は、入力アドレスに含まれるタグアドレスと、タグメモリ１１から出力される4つのタグアドレスとの比較によって、キャッシュヒットであるかミスヒットであるかを判定する。具体的には、入力アドレスに含まれるタグアドレスとタグメモリ１１の出力とが一致する場合にキャッシュヒットを示す信号を出力し、不一致である場合にキャッシュミスを示す信号を出力する。ヒット判定部１２の出力信号は、１ウェイ毎のヒット判定結果をそれぞれ１ビットの論理値で示す合計4ビットの信号である。

コントローラ８３は、ヒット判定部１２によりキャッシュヒットと判定された場合に、チップセレクト信号（ＣＳ信号）及びリードストローブ信号（ＲＳ信号）をデータメモリ１０に出力することによりデータメモリ１０からのデータ読み出しを制御する。一方、ヒット判定部１２によりミスヒットと判定された場合に、コントローラ８３は、入力アドレスに含まれるタグアドレスによるタグメモリ１１の書き換え制御、データリフィル制御を行う。ここで、データリフィル制御とは、主記憶３からのデータ読み出し、及び、主記憶から読み出されたデータによるデータメモリ１０の書き換えの制御である。また、コントローラ８３は、ミスヒットの発生をプロセッサ２に通知するためにＷＡＩＴ信号線７を用いてＷＡＩＴ信号を出力する。

アドレスラッチ１４は、入力アドレスの少なくともタグアドレス部分を１クロックサイクルだけ保持する回路であり、例えば、Ｄフリップフロップにより構成することができる。アドレスラッチ１４の保持するデータは、タグメモリ１１の書き換えを行う際の入力データとして利用される。

次に、図６を参照してキャッシュメモリ８の動作を説明する。図６は、プロセッサ２によるロード要求に対するキャッシュメモリ８のパイプライン動作を示しており、図６（ａ）がキャッシュヒット時の動作、図６（ｂ）がミスヒット時の動作を示している。まず、パイプラインの第１ステージにおいて、プロセッサ２から入力される入力アドレスによりタグメモリ１１がアクセスされ、これに対応するタグアドレスが読み出される。さらに、同じ第１ステージにおいて、ヒット判定部１２よりヒット判定が行われる。

ヒット判定部１２による判定がキャッシュヒットである場合は、第１ステージの終端において、入力アドレス、ＣＳ信号及びＲＳ信号がデータメモリ１０に入力される。また、図６（ａ）に示すように、第１ステージに引き続く第２ステージにおいて、データメモリ１０からデータが読み出され、読み出されたデータがプロセッサ２に出力される。キャッシュメモリ８の出力データは、汎用レジスタ等のプロセッサ２の所定の格納領域に格納される。

一方、ヒット判定部１２による判定がミスヒットである場合は、第１ステージの終端におけるＣＳ信号及びＲＳ信号の出力は行われない。そして、図６（ｂ）に示すように、第１ステージに引き続く第２ステージにおいて、置換ウェイを決定する処理、タグメモリ１１に保持されている置換ウェイに決定されたラインに対応するタグアドレスを入力アドレスのタグアドレスによって更新する処理が行われる。また、同じく第２ステージにおいて、メモリバス６を介して接続された主記憶３に対するリードアクセスが行われ、入力アドレスに対応するデータが主記憶３から読み出されてデータメモリ１０に格納される。さらに、同じく第２ステージにおいて、主記憶３から読み出されたデータがプロセッサ２に出力される。
特開平１０−６３５７５号公報

上述したように、図５に示した従来のキャッシュメモリ８は、１段目のパイプラインステージにおいてタグメモリ１１からのタグアドレスの読み出し、及びヒット判定部１２によるヒット判定までを行う。キャッシュヒットした場合は、２段目のパイプラインステージで、データメモリ１０のヒットしたウェイからのデータ読み出し、及び読み出されたデータのプロセッサ２への転送を行う。ミスヒットであった場合は、２段目のパイプラインステージで、置換ウェイの決定、タグメモリ１１の更新、主記憶３から読み出されたデータによるデータメモリ１０の更新、主記憶３から読み出されたデータのプロセッサ２への転送を行う。

しかしながら、上述したような２段パイプラインのキャッシュメモリでは、１ステージでの処理量が多いためにキャッシュメモリ８の動作周波数の向上が難しく、十分な高速化（スループットの向上）が達成できない。そこで、本願の発明者は、３段以上の多段パイプライン化を図り、タグメモリからのタグアドレス読み出し処理と、読み出されたタグアドレスと入力アドレスに含まれるタグアドレスの比較によるヒット判定処理とを分割して異なるパイプラインステージで実行する構成を考案した。しかしながら、このようにパイプラインステージの分割を行ってパイプラインの多段化を進める場合には、キャッシュメモリの効率的な動作の妨げとなる以下に述べる問題が発生することが分かった。

つまりその問題とは、あるメモリアクセス要求においてミスヒットが発生しタグメモリの更新が行われた場合に、直後のメモリアクセス要求におけるヒット判定に直前のメモリアクセス要求でのミスヒット発生によるタグメモリの更新が反映されないという問題である。これを放置すると、例えば、直後のメモリアクセス要求がミスヒットの発生した直前のメモリアクセス要求と同一メモリブロックに対するアクセスであり、ミスヒット検出に応じて既に低速メモリからのデータリフィルが行われているにもかかわらず、再度ミスヒットと判定して無駄なデータリフィル処理を行ってしまうことになる。また、直後のメモリアクセス要求が、直前のメモリアクセス要求でのミスヒット検出に基づくデータリフィル処理によって置換対象とされたメモリブロックに対するアクセスである場合は、本来ミスヒットと判定すべきところをキャッシュヒットと誤判定し、誤ったデータの読み出しが実行されてしまう。

このような無駄なデータリフィル動作やデータメモリからの誤ったデータの読み出しを回避する１つの解決策として、あるメモリアクセス要求でミスヒットが発生した場合に、後続のメモリアクセス要求の処理をパイプラインの先頭、つまりタグメモリの読み出し処理から再度実行するアーキテクチャを採用することが考えられる。このようなアーキテクチャは、ＲＩＳＣ方式のマイクロプロセッサ等で採用されるアーキテクチャである。しかしながら、このようなアーキテクチャは、ハードウェア規模の増大、再実行シーケンスを制御する制御部の複雑性の増大を招くという問題がある。

タグメモリからのタグアドレス読み出し処理とヒット判定処理とを異なるパイプラインステージに分割する場合に生じる上述の問題を解消するために、本発明の第１の態様にかかるキャッシュメモリは以下のように構成される。つまり、本発明の第１の態様にかかるキャッシュメモリは、プロセッサと低速メモリの間に配置されて、前記プロセッサによるメモリアクセスをパイプライン処理するキャッシュメモリであって、前記低速メモリの部分集合に相当するデータを格納するデータメモリと、前記データメモリに格納されたデータに対応付けられたタグアドレスを格納するタグメモリと、前記プロセッサより入力される入力アドレスに含まれるインデックスアドレスを用いて前記タグメモリを検索することにより得られるタグアドレスと前記入力アドレスに含まれるタグアドレスとの比較によってキャッシュヒットかミスヒットかを判定するヒット判定部と、前記入力アドレスに含まれるタグアドレスを保持するラッチ回路と、前記ラッチ回路の保持データを、前記タグメモリを迂回して前記ヒット判定部に入力するためのバイパス回路と、前記ヒット判定部によりキャッシュヒットと判定された場合に、前記データメモリからのデータ読み出しを制御し、前記ヒット判定部によりミスヒットと判定された場合に、前記入力アドレスに含まれるタグアドレスによる前記タグメモリの更新処理、前記低速メモリからのデータ読み出しによる前記データメモリの更新処理、及び前記バイパス回路の動作を制御するコントローラとを備える。さらに、本発明の第１の態様にかかるキャッシュメモリは、第１のパイプラインステージにおいて、前記インデックスアドレスを用いた前記タグメモリからのタグアドレスの読み出し処理を実行する。次に、前記第１のパイプラインステージに続く第２のパイプラインステージにおいて、前記ヒット判定部による判定処理を実行する。続いて、前記第２のパイプライステージにおいてキャッシュヒットと判定された場合には、前記第２のパイプラインステージの直後に引き続く第３のパイプラインステージ以降において、前記データメモリからのデータ読み出し処理と、前記データメモリから読み出されたデータの前記プロセッサへの出力とを実行する。一方、前記第２のパイプライステージにおいてミスヒットと判定された場合には、前記第３のパイプラインステージにおいて、前記コントローラによる前記タグメモリの更新制御及び前記タグメモリを迂回して前記ラッチ回路の保持データを前記ヒット判定部に入力するための前記バイパス回路の制御を実行し、前記第３のパイプラインステージに続く第４のパイプラインステージ以降において、前記低速メモリからのデータ読み出しによる前記データメモリの更新処理と、前記低速メモリから読み出されたデータの前記プロセッサへの出力とを実行する。

上述した本発明の第１の態様にかかるキャッシュメモリによれば、先行するメモリアクセス要求においてミスヒットが発生した場合に、先行するメモリアクセス要求でのミスヒット発生によるタグメモリの更新を後続のメモリアクセス要求におけるヒット判定に反映させることができる。このため、後続のメモリアクセス要求に関するヒット判定における判定誤りを防止し、無駄なデータリフィル動作やデータメモリからの誤ったデータの読み出しを抑制することができる。さらに、前記第１の態様にかかるキャッシュメモリによれば、先行するメモリアクセス要求でミスヒットが発生した場合に、後続のメモリアクセス要求の処理をパイプライン先頭のタグメモリの読み出し処理からやり直す必要がない。このため、タグメモリの読み出し処理から再度実行するための冗長なハードウェアを必要としない。

本発明により、キャッシュメモリのパイプラインの多段化を進める場合にも、連続するメモリアクセスを効率的に処理可能なキャッシュメモリを提供することができる。

以下では、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略する。

本実施の形態にかかるキャッシュメモリ１の構成を図１に示す。本実施の形態にかかるキャッシュメモリ１は、４ウェイ・セットアソシアティブ方式のキャッシュメモリである。なお、図５に示した従来のキャッシュメモリ８との対比を容易にするために、４ウェイ・セットアソシアティブ構成としているが当該構成は一例である。つまり、キャッシュメモリ１のウェイ数は他の数でもよく、またダイレクトマップ方式であっても良い。

なお、キャッシュメモリ１が有するデータメモリ１０、タグメモリ１１、ヒット判定部１２及びデータラッチ１４は、図５に示した構成要素と同様であるため、対応する構成要素と同一の符号を付して詳細な説明を省略する。

キャッシュメモリ１が有するコントローラ１３のキャッシュヒット時の動作は、従来のコントローラ８３と同様である。つまり、コントローラ１３は、ヒット判定部１２によりキャッシュヒットと判定された場合に、チップセレクト信号（ＣＳ信号）及びリードストローブ信号（ＲＳ信号）をデータメモリ１０に出力することによりデータメモリ１０からのデータ読み出しを制御する。一方、ヒット判定部１２によりミスヒットと判定された場合には、コントローラ１３は、入力アドレスに含まれるタグアドレスによるタグメモリ１１の書き換え制御及びデータリフィル制御に加えて、後述するセレクタ１９の動作制御を行う。

また、キャッシュメモリ１は、４段パイプライン構造を採用しているため、パイプラインステージ間での中間データを保持するためのラッチ回路を図５のキャッシュメモリ８に比べて多く有している。アドレスラッチ１５〜１７及び２０と、データラッチ２１がこれに相当する。アドレスラッチ１５は、入力アドレスの少なくともインデックスアドレス及びワードアドレス部分を保持する回路である。アドレスラッチ１６及び１７は、アドレスラッチ１４と同様に、入力アドレスの少なくともタグアドレス部分を保持する回路である。

アドレスラッチ２０は、セレクタ１９とヒット判定回路１２との間で中間データを保持する回路である。なお、アドレスラッチ２０は、入力アドレスに対応してタグメモリ１１から出力される４つのタグアドレスを保持できるよう構成される。例えば、平行して出力される４つのタグアドレスを保持できるように、それぞれが１つのタグアドレスを保持可能なＤフリップフロップを４つ設ければ良い。

データラッチ２１は、データメモリ１０の出力データを保持する回路である。つまり、データラッチ２１は、データメモリ１０へアクセスする処理と、プロセッサ２にデータを転送する処理とを別々のパイプラインステージに分割するために設けられている。

バイパス配線１８及びセレクタ１９は、タグメモリ１１を迂回してアドレスラッチ１７の保持データをヒット判定部１２に入力するためのバイパス回路である。セレクタ１９の動作は、コントローラ１３から出力される制御信号（ＳＣ信号）により行われる。

続いて以下では、図２を参照してキャッシュメモリ１の動作を説明する。図２は、プロセッサ２によるロード要求に対するキャッシュメモリ１のパイプライン動作を示しており、図２（ａ）がキャッシュヒット時の動作、図２（ｂ）がミスヒット時の動作を示している。まず、パイプラインの第１ステージにおいて、プロセッサ２から入力される入力アドレスによりタグメモリ１１がアクセスされ、これに対応する４つのタグアドレスが読み出される。読み出された４つのタグアドレスは、セレクタ１９を経由してアドレスラッチ２０に保持される。

次に、第１ステージに引き続く第２ステージにおいて、ヒット判定部１２によりヒット判定が行われる。ヒット判定部１２は、アドレスラッチ１６に保持された入力アドレスに含まれるタグアドレスと、アドレスラッチ２０に保持されタグアドレスとを比較する。

ヒット判定部１２による判定がキャッシュヒットである場合は、第２ステージの終端において、入力アドレス、ＣＳ信号及びＲＳ信号がデータメモリ１０に入力される。また、図２（ａ）に示すように、第２ステージに引き続く第３ステージにおいて、データメモリ１０からデータが読み出され、読み出されたデータがデータラッチ２１に保持される。最後に、第３ステージに引き続く第４ステージにおいて、データラッチ２１の保持データがプロセッサ２に転送され、汎用レジスタ等のプロセッサ２の所定の格納領域に格納される。

一方、ヒット判定部１２による判定がミスヒットである場合は、第２ステージの終端におけるＣＳ信号及びＲＳ信号の出力は行われない。そして、図２（ｂ）に示すように、第２ステージに引き続く第３ステージにおいて、置換するウェイを決定する処理、タグメモリ１１に保持されている置換ウェイに決定されたタグアドレスを入力アドレスのタグアドレスにより更新する処理が行われる。置換ウェイの決定は、４つのウェイからランダムに選択するランダム法、最も過去に参照されたウェイを選択するＬＲＵ法など、従来から知られている決定方法により行えば良い。

さらに、コントローラ１３は、第３ステージにおいてセレクタ１９を制御し、置換ウェイに対応するタグアドレスを保持しているアドレスラッチ２０を、アドレスラッチ１７の格納値、つまり入力アドレスのタグアドレスにより更新する。

ここで、コントローラ１３は、上述した置換ウェイの決定処理及びタグメモリ１１の更新処理、セレクタ１９の制御を第３ステージの最初のクロックサイクル、つまり図２（ｂ）のＣ３サイクルにおいて実行するとともに、ＷＡＩＴ信号を出力してパイプライン動作を1クロックサイクルだけストールさせる。

ストールされた第３ステージの２サイクル目の後に続く第４ステージでは、メモリバス６を介して接続された主記憶３に対するリードアクセスが行われ、入力アドレスに対応するデータが主記憶３から読み出されてデータメモリ１０に格納される。さらに、同じく第４ステージにおいて、主記憶３から読み出されたデータがプロセッサ２に出力される。

上述のように動作するキャッシュメモリ１の効果について、図３及び４を参照して説明する。図３は、２つのロード要求（ロード要求Ａ及びＢ）が連続して行われる場合のキャッシュメモリ１のパイプライン処理を示すタイミングチャートである。さらに詳しくは、先行するロード要求Ａにおいてミスヒットが発生した場合の処理を示している。

図３に示すように、ロード要求Ａの２段目（ｍ＋１ステージ）のヒット判定がミスヒットとなると、引き続く３段目（ｍ＋２ステージ）の１サイクル目（Ｃ３サイクル）において置換ウェイの決定及びタグメモリ１１の書き換えが行われる。さらに、バイパス配線１８及びセレクタ１９により、新たにタグメモリ１１に格納されるタグアドレスが、タグメモリ１１を迂回してアドレスラッチ２０に与えられる。さらに、パイプラインが１サイクルだけストールされる。

なお、上述したロード要求Ａに対する処理に平行して、後続のロード要求Ｂに対する処理が開始されている。つまり、ロード要求Ａの２段目に当たるｍ＋１ステージでは、ロード要求Ｂの１段目の処理であるタグメモリ１１からのタグアドレス読み出しが行われる。つまり、ロード要求Ｂのタグアドレス読み出し時点では、先行するロード要求Ａのミスヒットに伴うタグメモリ１１の更新は完了していない。このため、ロード要求Ｂの２段目（ｍ＋２ステージ）では、ロード要求Ｂに対するヒット判定が行われるが、このヒット判定は、先行するロード要求Ａのミスヒットに伴うタグメモリ１１の更新を反映せずに行われる。

しかしながら、ストールされたｍ＋２ステージの２サイクル目（Ｃ４サイクル）で再び実行されるロード要求Ｂのヒット判定は、タグメモリ１１を迂回してアドレスラッチ２０に与えられた新しいタグアドレスを用いてヒット判定が再実行される。

このように、本実施の形態にかかるキャッシュメモリ１によれば、先行するメモリアクセス要求においてミスヒットが発生した場合に、先行するメモリアクセス要求でのミスヒット発生によるタグメモリ１１の更新を後続のメモリアクセス要求におけるヒット判定に反映させることができる。このため、後続のメモリアクセス要求に関するヒット判定における判定誤りを防止し、無駄なデータリフィル動作やデータメモリからの誤ったデータの読み出しを抑制することができる。さらに、キャッシュメモリ１によれば、図３に示したように、先行するメモリアクセス要求でミスヒットが発生した場合に、後続のメモリアクセス要求の処理を先頭のタグメモリ１１の読み出し処理からやり直す必要がない。このため、タグメモリ１１の読み出し処理から再度実行するための冗長なハードウェアが不要となる。また、タグメモリ１１の読み出し処理の再実行によって、後続のメモリアクセス要求のキャッシュアクセス時間が増加することを抑制できる。

また、本実施の形態にかかるキャッシュメモリ１は、以下に説明する点で有効である。図４は、プロセッサ２がキャッシュメモリ１を介さずに直接主記憶３にデータ書き込みを行う直接ストア要求と、キャッシュメモリ１に対するロード要求が連続して行われる場合を示したタイミングチャートである。つまり、図４（ｂ）の直接ストアアクセスのパイプラインはプロセッサ２のパイプラインを示しており、図４（ｃ）のロード要求のパイプラインは、キャッシュメモリ１２のパイプラインを示している。

図４（ｂ）の直接ストアアクセスは、プロセッサ２においてＩＦステージ（Ｃ１サイクル）からＥＸＥステージ（Ｃ６サイクル）までの６段パイプラインで実行される。具体的には、ＩＦステージ（Ｃ１サイクル）では、命令キャッシュからの命令取り込みが行われ、ＩＤステージ（Ｃ２サイクル）ではフェッチされた命令のデコードが行われ、ＡＤＲステージ（Ｃ３サイクル）では実効アドレスの計算が行われる。ＥＸＥステージ（Ｃ６サイクル）では、主記憶３へのデータ書き込みが実行されるが、この場合、メモリバス６のバス速度とプロセッサ２の処理速度との速度差によりプロセッサ２がストールすることを防止するため、直接主記憶３に対してデータ書き込みを行うのではなく、いったんストアバッファ（不図示）を経由する構成が一般的である。このようにストアバッファを経由する場合、ＥＸＥステージ（Ｃ６サイクル）では、ストアバッファに対する書き込みデータの出力のみが行われ、主記憶へのデータ書き込みは、ＥＸＥステージ以降のクロックサイクル（Ｃ７サイクル）以降で行われる。

このように、直接ストアアクセスによる主記憶３への実アクセスがＣ７サイクル以降で発生する場合、Ｃ６サイクルではストアバッファに書き込み中であり、メモリバス６へのアクセス要求は出ていないことになる。このため、仮に、ミスヒットを検出したキャッシュメモリ１によるメモリバス６へのアクセス要求が図４のＣ６サイクルで先に発生すると、競合する命令が存在しないために、ミスヒットによる主記憶３からのデータ読み出しが先に開始されてしまい、直前のストア命令（直接ストアアクセス）によるメモリバス６へのアクセスが後で実行されることになる。もし、同一アドレス対する直接ストア要求及びロード要求であった場合は、処理順序が入れ替わることによって、これ以降のプログラムの正常実行ができなくなる。

しかしながら、本実施の形態のキャッシュメモリ１は、ミスヒット発生時の主記憶３からのデータ読み出しをパイプラインの最終ステージで行うこととしている。このため、図４のタイミングチャートにおいて、キャッシュメモリ１によるメモリバス６へのアクセスが発生するのはＣ８サイクル以降であり、これより前にストアバッファによるメモリバス６へのアクセスが開始されていることになる。なお、図４（ｃ）において、Ｃ５サイクルのＣＭＰステージはヒット判定が行われるパイプラインステージを表しており、Ｃ６サイクルのＷＴＧステージは、ミスヒットに伴うタグメモリ１１の更新が行われるパイプラインステージを表しており、Ｃ８サイクル以降のＭａｃステージは、主記憶３からのデータ読み出し及び読み出されたデータのプロセッサ２への転送が行われるパイプラインステージを表している。図４に示すように、ストアバッファ（不図示）によるメモリバス６へのアクセス要求とキャッシュメモリ１によるメモリバス６へのアクセス要求とが共に発生しているか、又は、キャッシュメモリ１によるアクセス要求が後から発生すれば、メモリバス６のバスコントローラ（不図示）は命令実行順序に応じてアクセス要求を調停することができる。したがって、同一アドレス対する直接ストア要求及びロード要求であっても、プログラムを正常に実行することができる。

なお、本実施の形態にかかるキャッシュメモリ１の構成は一例であって、様々な変形が可能である。例えば、パイプラインステージ数は４段に限定されない。また、コントローラ１３の具体的な構成は、複数の回路の集合でも良く、例えば、置換ウェイの計算、セレクタ１９の制御、主記憶３へのアクセス制御を個別の回路で実現しても良い。

また、本発明のその他の実施の形態には、上述したキャッシュメモリ１が有する構成の一部を有するキャッシュメモリがある。具体的には、タグメモリ１１の読み出し処理とヒット判定処理を分割して別々のパイプラインステージで実行するキャッシュメモリとし、ミスヒットが発生した場合に、ヒット判定を行うパイプラインステージの直後のパイプラインステージにおいて、置換ウェイの決定及びタグメモリ１１の書き換えを実行するとともに、ミスヒットのあったアクセス要求に関するタグアドレスを、タグメモリ１１を迂回して後続のアクセス要求のヒット判定にフォワーディングする構成とすればよい。これにより、後続のアクセス要求をパイプラインの先頭から再実行することなく、ヒット判定の誤りを防止することができる。

また、上述したキャッシュメモリ１は、ミスヒット時にパイプラインをストールさせる構成である。このような構成は、置換されるタグアドレスの情報を後続のメモリアクセス要求のヒット判定に確実に反映せることができる点で有効である。しかしながら、例えば、ランダム方式による置換ウェイの決定などによって置換ウェイの決定処理を高速化することにより、パイプラインをストールさせずに置換されるタグアドレスの情報を後続のメモリアクセス要求のヒット判定に反映させることも可能である。

さらに、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。

本発明の実施の形態にかかるキャッシュメモリの構成図である。本発明の実施の形態にかかるキャッシュメモリによるパイプライン処理を示す図である。本発明の実施の形態にかかるキャッシュメモリによるパイプライン処理を示す図である。本発明の実施の形態にかかるキャッシュメモリによるパイプライン処理を示す図である。従来のキャッシュメモリの構成図である。従来のキャッシュメモリパイプライン処理を示す図である。入力アドレスの構成を示す図である。

符号の説明

１キャッシュメモリ
２プロセッサ
３主記憶
４アドレスバス
５データバス
６メモリバス
７ＷＡＩＴ信号線
１０データメモリ
１１タグメモリ
１２ヒット判定部
１３コントローラ
１４〜１７アドレスラッチ
１８バイパス配線
１９セレクタ
２０アドレスラッチ
２１データラッチ

Claims

プロセッサと低速メモリの間に配置されて、前記プロセッサによるメモリアクセスをパイプライン処理するキャッシュメモリであって、
前記低速メモリの部分集合に相当するデータを格納するデータメモリと、
前記データメモリに格納されたデータに対応付けられたタグアドレスを格納するタグメモリと、
前記プロセッサより入力される入力アドレスに含まれるインデックスアドレスを用いて前記タグメモリを検索することにより得られるタグアドレスと前記入力アドレスに含まれるタグアドレスとの比較によってキャッシュヒットかミスヒットかを判定するヒット判定部と、
前記入力アドレスに含まれるタグアドレスを保持するラッチ回路と、
前記ラッチ回路の保持データを、前記タグメモリを迂回して前記ヒット判定部に入力するためのバイパス回路と、
前記ヒット判定部によりキャッシュヒットと判定された場合に、前記データメモリからのデータ読み出しを制御し、前記ヒット判定部によりミスヒットと判定された場合に、前記入力アドレスに含まれるタグアドレスによる前記タグメモリの更新処理、前記低速メモリからのデータ読み出しによる前記データメモリの更新処理、及び前記バイパス回路の動作を制御するコントローラとを備え、
第１のパイプラインステージにおいて、前記インデックスアドレスを用いた前記タグメモリからのタグアドレスの読み出し処理を実行し、
前記第１のパイプラインステージに続く第２のパイプラインステージにおいて、前記ヒット判定部による判定処理を実行し、
前記第２のパイプライステージにおいてキャッシュヒットと判定された場合には、前記第２のパイプラインステージの直後に引き続く第３のパイプラインステージ以降において、前記データメモリからのデータ読み出し処理と、前記データメモリから読み出されたデータの前記プロセッサへの出力とを実行し、
前記第２のパイプライステージにおいてミスヒットと判定された場合には、前記第３のパイプラインステージにおいて、前記コントローラによる前記タグメモリの更新制御及び前記タグメモリを迂回して前記ラッチ回路の保持データを前記ヒット判定部に入力するための前記バイパス回路の制御を実行し、前記第３のパイプラインステージに続く第４のパイプラインステージ以降において、前記低速メモリからのデータ読み出しによる前記データメモリの更新処理と、前記低速メモリから読み出されたデータの前記プロセッサへの出力とを実行する、キャッシュメモリ。
前記低速メモリからのデータ読み出しによる前記データメモリの更新処理が、最終段のパイプラインステージで実行されることを特徴とする請求項１に記載のキャッシュメモリ。
前記ヒット判定部によりミスヒットと判定された場合に前記第３のパイプラインステージには少なくとも２クロックサイクルが割り当てられ、前記コントローラは前記タグメモリの更新を前記第３のパイプラインステージの最終クロックサイクルより前のクロックサイクルまでに実行するとともに、前記最終クロックサイクルにおいて前記ラッチ部の保持データが前記ヒット判定部に入力されるよう前記バイパス回路の動作を制御する、請求項１又は２に記載のキャッシュメモリ。
前記バイパス回路は、
前記ラッチ部から出力されるタグアドレス及び前記タグメモリから出力されるデータのいずれかを前記ヒット判定部に対して選択的に出力するセレクタを備え、
前記コントローラは、前記第３のパイプラインステージにおいて、前記ヒット判定部の判定結果がミスヒットであることに応じて前記セレクタに前記ラッチ部に格納されたデータの出力を選択させ、前記ヒット判定部の判定結果がミスヒットでない場合に前記セレクタに前記タクグメモリから出力されるデータを選択させる、請求項１乃至３のいずれかに記載のキャッシュメモリ。