(57)【要約】【課題】ダイレクトマップ方式またはセットアソシエイティブ方式のキャッシュ機構において、キャッシュメモリの利用効率を高め、キャッシュのヒット率を向上する方法を提供する。【解決手段】ダイレクトマップ方式およびセットアソシエーション方式のキャッシュ機構であって、アドレスを変換することによりエントリ番号を生成する機構を有し、さらにアドレスを変換する方法を外部から設定する機構を有し、さらにアドレスを変換する方法を外部に通知する機構を有し、さらにアドレスを変換する方法を記憶する機構を有し、さらにエントリ番号を生成する方法がアドレスから抽出した１つのビット列の変換であり、さらにエントリ番号を生成する方法がアドレスから抽出した複数のビット列同士の演算であることにより、キャッシュメモリの利用効率を高める。【選択図】図２
2004118372.tif 000002
【特許請求の範囲】
【請求項１】
ダイレクトマップ方式およびセットアソシエーション方式のキャッシュ機構であって、アドレスを変換することによりエントリ番号を生成する機構を有することを特徴とするキャッシュ機構。
【請求項２】
アドレスを変換する方法を外部から設定する機構を有することを特徴とする請求項１に記載のキャッシュ機構。
【請求項３】
アドレスを変換する方法を外部に通知する機構を有することを特徴とする請求項１に記載のキャッシュ機構。
【請求項４】
アドレスを変換する方法を記憶する機構を有することを特徴とする請求項２に記載のキャッシュ機構。
【請求項５】
エントリ番号を生成する方法が、アドレスから抽出した１つのビット列の変換であることを特徴とする請求項１に記載のキャッシュ機構。
【請求項６】
エントリ番号を生成する方法が、アドレスから抽出した複数のビット列同士の演算であることを特徴とする請求項１に記載のキャッシュ機構。
【請求項７】
アドレスの各ビットが、アドレスから抽出したビット列の高々１つにしか含まれないことを特徴とする請求項５または６に記載のキャッシュ機構。
【請求項８】
該演算が加算を含むことを特徴とする請求項５または６に記載のキャッシュ機構。
【請求項９】
該演算が排他的論理和を含むことを特徴とする請求項５または６に記載のキャッシュ機構。
【請求項１０】
該演算が加算と排他的論理和と論理反転とビット選択とビット結合の組み合わせであることを特徴とする請求項５または６に記載のキャッシュ機構。
【請求項１１】
エントリ番号がｎビットで表されるとき、ビット列の長さがｎであることを特徴とする請求項５または６に記載のキャッシュ機構。
【請求項１２】
エントリ番号がｎビットで表されるとき、ｎビットの演算を含むことを特徴とする請求項５または６のキャッシュ機構。
【請求項１３】
データの構造に応じて、データがキャッシュメモリに格納されやすいように請求項２のキャッシュ機構の設定を変更することを特徴とするキャッシュ制御方法。
【請求項１４】
請求項３のキャッシュ機構の設定を調べて、データがキャッシュメモリに格納されやすいような順番でデータにアクセスすることを特徴とするデータアクセス方法。
【請求項１５】
請求項１のキャッシュ機構を有することを特徴とする計算機システム。
【請求項１６】
請求項１のキャッシュ機構を有することを特徴とするプロセッサ。
【請求項１７】
請求項１のキャッシュ機構を有することを特徴とするハードディスク。
【請求項１８】
請求項１３のキャッシュ制御方法を行うソフトウェア。
【請求項１９】
請求項１４のデータアクセス方法を行うソフトウェア。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はキャッシュ機構に関し、特に計算機システムにおけるキャッシュ機構に関する。
【０００２】
【従来の技術】
キャッシュ機構は、データ転送において低速なメモリーから読み出されたデータを高速なメモリーに一時的に蓄え、再び該データの読み出しが発生した時に、高速なメモリーから該データを出力することにより、見かけの読み出し速度を高速化するシステムである。これは、一度読み出されたデータは、読み出されていないデータよりも再び読み出される可能性が高いという仮定に基づいている。書き込みの場合に関しても同様のことが言える。
【０００３】
この高速なメモリーをキャッシュメモリーと呼び、キャッシュメモリーにデータが格納されていることを、キャッシュにデータが格納されている、あるいはデータがキャッシュされている、と表現する。あるデータの読み出しが発生したときに、キャッシュにそのデータが格納されており、キャッシュからデータを読み出せることを、キャッシュにヒットすると表現する。反対に、キャッシュにヒットしない状態をキャッシュミスと呼ぶ。
【０００４】
計算機システムにおけるキャッシュ機構は、メインメモリーとマイクロプロセッサの間にメインメモリーよりも高速なキャッシュメモリを置き、メインメモリーとマイクロプロセッサ間のデータ転送速度を向上する。マイクロプロセッサがキャッシュ機構を持っていることもある。計算機システムにおけるキャッシュ機構の具体例は、『ＨＩＴＡＣＨＩ　ＳｕｐｅｒＨ　ＲＩＳＣ　ｅｎｇｉｎｅ　ＳＨ７７０８　ＨＤ６４１７７０８　ハードウェアマニュアル　第５章　キャッシュ』に述べられている。
【０００５】
マイクロプロセッサがメインメモリーから読み出しを行う時、読み出そうとするデータを含むデータ領域を一度に読み出しキャッシュに格納する。この一度に読み出すデータ領域をキャッシュライン、キャッシュラインに格納されたデータをラインデータと呼び、キャッシュ機構ではキャッシュライン単位でデータを管理する。キャッシュに格納されたラインデータはキャッシュから読み出すことができる。この読み出しはメインメモリーの読み出しよりも高速である。また、マイクロプロセッサが使用するデータには、読み出されたデータに隣接するアドレスのデータが次に読み出される可能性が高いという性質があるため、一連の隣接するアドレスでキャッシュラインを構成することにより、次に読み出される可能性の高いデータを先読みしてキャッシュに格納することができる。これにより、キャッシュのヒット率を高め、プロセッサーから見たメインメモリーの見かけの読み出し速度が向上することができる。
【０００６】
キャッシュ方式には、主にダイレクトマップ方式、セットアソシエイティブ方式、フルアソシエイティブ方式の３方式がある。
【０００７】
ダイレクトマップ方式は、マイクロプロセッサのアドレス空間を複数のエントリに分割し、各エントリに対して１つのラインデータの情報を格納する方式である。エントリはラインデータの内容に加えラインデータのアドレスを示すタグの情報を格納する。既にラインデータを格納しているエントリに新たなラインデータを格納する場合は、新しいラインデータの情報でエントリを上書きする。
【０００８】
セットアソシエイティブ方式は、マイクロプロセッサのアドレス空間を複数のエントリに分割し、各エントリに対して複数のラインデータの情報を格納する方式である。特に、１エントリに対して格納できるラインデータの数をウェイ数と呼び、セットアソシエイティブ方式でウェイ数がＮであるとき、Ｎウェイセットアソシエイティブ方式と呼ぶ。既にＮ個のラインデータを格納しているエントリに新たなラインデータを格納する場合、ラインデータの入れ替えを行う。入れ替える方法としては、例えば、ＬＲＵ（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ）アルゴリズムに基づき、読み出された時刻が一番古いラインデータと新たなラインデータの情報を入れ替える。
【０００９】
フルアソシエイティブ方式は、セットアソシエイティブ方式の特殊な場合であり、マイクロプロセッサのアドレス空間を分割せずに１つのエントリとして管理する方式である。
【００１０】
ダイレクトマップ方式のキャッシュメモリのヒット率を向上させる従来技術としては、例えば特許文献１に記載がある。
【００１１】
【特許文献１】
特開平１１−２９６４３１号公報
【００１２】
【発明が解決しようとする課題】
ところで、１つ以上の要素で構成される構造体の配列をメモリー上に確保する場合、この構造体のサイズをＳバイトとすると、２＾（ｎ−１）＜Ｓ≦２＾ｎ（但し、ｎは１以上の整数、＾はべき乗を示す）を満たす２＾ｎバイトの大きさの要素からなる配列を確保し、その配列の各要素の先頭から構造体を格納することができる。これを構造体の配列としＳＴで表す。構造体の配列に含まれるｋ番目の構造体をＳＴ［ｋ］（但し、ｋは１以上の整数）、ＳＴ［ｋ］の要素の一つをＳＴ［ｋ］．ａとすると、配列の要素が隙間なくメモリー上に存在すれば、異なるｋにおいても、ＳＴ［ｋ］の先頭アドレスの下位ｎビットはすべて等しくなり、ＳＴ［ｋ］．ａの下位ｎビットも等しくなる。これにより、ｋを変化させてＳＴ［ｋ］．ａを連続して読み込む場合、下位ｎビットを変化させずに上位ビットのみを変化させるだけで読み出しが可能であるため、アドレスの演算が容易に行える。但し、ＳＴ［ｋ］の先頭を基準とした時のＳＴ［ｋ］．ａの相対アドレスはすべてのｋにおいて等しいものとする。
【００１３】
従来のキャッシュ機構では、ダイレクトマップ方式、セットアソシエイティブ方式を適用する場合、アドレスを２進数で表現した時の一部分の桁を取り出して、ラインデータを格納するエントリを決めるエントリ番号としていた。例えば、アドレスバスの幅が３２ビット、エントリ数が１２８エントリであるとき、アドレスのビット１０〜ビット４の７ビットをエントリ番号としていた。この場合、１０２４（＝２＾１０）バイトを超えるサイズの構造体の配列ＳＴに関して、ＳＴ［ｋ］．ａのｋを変化させるような読み出しを行うと、アドレスのビット１０からビット４が変化せず、即ちエントリ番号が変化しないため、同じエントリにデータが繰り返し格納され、キャッシュメモリーの利用効率が悪いという問題があった。
【００１４】
上記特許文献１に記載される方法によれば、エントリ番号を排他的論理和により求めることにより、同じエントリにデータが繰り返しキャッシュされる問題点を一部解消するが、メインメモリとキャッシュメモリでの局所的なデータの並び順が異なるため、キャッシュメモリのアクセスの先読みが困難であった。また、エントリ番号を求めるために使用するビットが変化しないアドレスに対して繰り返しアクセスを行う場合、同じエントリにデータが繰り返し格納されるため、効率が悪くなることがあった。
【００１５】
そこで、本発明は、ダイレクトマップ方式またはセットアソシエイティブ方式のキャッシュ機構において、キャッシュメモリの利用効率を高め、キャッシュのヒット率を向上する方法を提供することを目的とする。
【００１６】
【課題を解決するための手段】
上記の課題を解決するために本発明のキャッシュ機構は、ダイレクトマップ方式およびセットアソシエーション方式のキャッシュ機構であって、アドレスを変換することによりエントリ番号を生成する機構を有し、さらにアドレスを変換する方法を外部から設定する機構を有し、さらにアドレスを変換する方法を外部に通知する機構を有し、さらにアドレスを変換する方法を記憶する機構を有し、さらにエントリ番号を生成する方法がアドレスから抽出した１つのビット列の変換であり、さらにエントリ番号を生成する方法がアドレスから抽出した複数のビット列同士の演算であること特徴とし、キャッシュメモリの利用効率を高める。
【００１７】
【発明の実施の形態】
以下、本発明の実施の形態を図を用いて説明する。
【００１８】
（第１の実施の形態）
図４は、本発明のキャッシュ機構を適用した計算機システムの構成例である。図４に示す計算機システム４００は、マイクロプロセッサ２１０とキャッシュコントローラ２２０とキャッシュメモリ２４０とメインメモリー２３０と外部インターフェース４１０の各モジュールと、内部バス４０１と外部バス４０３の各バスで構成される。
【００１９】
内部バス４０１は、マイクロプロセッサ２１０とメインメモリ２３０と外部インターフェース４１０とを接続し、各モジュール間でアドレスとデータとコマンドを伝達する。コマンドには読み出しと書き込み等がある。
【００２０】
外部バス４０３は、外部インターフェース４１０と外部機器とを接続する。
【００２１】
外部インターフェース４１０は、内部バス４０１と外部バス４０３に接続し、外部バス４０３を介して計算機システム４００の情報を外部機器へ出力し、さらに外部機器の情報を計算機システム４００へ入力する。
【００２２】
マイクロプロセッサ２１０は、内部バス４０１とキャッシュコントローラ２２０に接続し、内部バス４０１を介してメインメモリ２３０へアクセスし、さらにキャッシュコントローラ２２０を介してキャッシュメモリ２４０へアクセスする。マイクロプロセッサ２１０はプログラムの示す手順に従ってデータを処理する。アクセスとはプログラムやデータの読み出しまたは書き込みのことである。
【００２３】
キャッシュコントローラ２２０は、マイクロプロセッサ２１０とキャッシュメモリ２４０に接続し、マイクロプロセッサ２１０から読み出し要求を受け、要求されたデータをキャッシュメモリ２４０から検索する。要求されたデータがキャッシュメモリ２４０に存在した場合は、キャッシュヒットを通知し、データをキャッシュメモリ２４０から読み出し、マイクロプロセッサ２１０に出力する。要求されたデータがキャッシュメモリ２４０に存在しなかった場合は、マイクロプロセッサ２１０にキャッシュミスを通知する。さらにキャッシュコントローラ２２０は、キャッシュメモリ２４０にデータとタグを書き込む。タグはキャッシュメモリ２４０からデータを検索するために使用する情報である。
【００２４】
キャッシュメモリ２４０は、キャッシュコントローラ２２０に接続し、キャッシュコントローラ２２０からデータとタグを入力され、データとタグを記憶し、キャッシュコントローラ２２０へデータとタグを出力する。マイクロプロセッサ２１０は、内部バス４０１を介してメインメモリ２３０をアクセスするより高速に、キャッシュコントローラ２２０を介してキャッシュメモリー２４０にアクセスすることができる。
【００２５】
メインメモリ２３０は、内部バス４０１に接続し、内部バス４０１を介し、マイクロプロセッサ２１０と外部インターフェース４１０からデータを入力し、データを記憶し、マイクロプロセッサ２１０と外部インターフェース４１０へデータを出力する。
【００２６】
キャッシュコントローラ２２０は、マイクロプロセッサ２１０がメインメモリ２３０からデータを読み出す時に、該データに続いて読み出される可能性の高いデータを予め読み出しキャッシュメモリ２４０に格納する。これにより、マイクロプロセッサ２１０のデータの読み出し速度が向上する。例えば、アドレスの隣接するデータが連続して読みだされる可能性が高いシステムであれば、あるアドレスのデータの読み出しに対して、アドレスの隣接するデータを予め読み出しキャッシュメモリ２４０に格納する。
【００２７】
以上に述べたマイクロプロセッサ２１０とキャッシュコントローラ２２０とキャッシュメモリ２４０とメインメモリ２３０は、それぞれ互いに互いの機能を含むことが可能である。
【００２８】
なお、以下の説明における各「機構」は電気回路により実現することが出来る。また、電気回路がプログラムを実行することにより実現しても良い。
【００２９】
次に、図２を用いて本実施形態のキャッシュ機構のデータフローを説明する。図２は前記マイクロプロセッサ２１０と前記キャッシュコントローラ２２０と前記キャッシュメモリ２４０と前記メインメモリ２３０との間のデータフローを示している。
【００３０】
マイクロプロセッサ２１０は、読み出し動作の場合、キャッシュコントローラ２２０に読み出すアドレス２５１を出力し、キャッシュコントローラ２２０が出力するＬＷデータ２６２を読み出す。書き込み動作の場合、キャッシュコントローラ２２０に書き込むアドレス２５１とＬＷデータを出力する。
【００３１】
キャッシュコントローラ２２０は、上位アドレスデコーダ２２１とキャッシュメモリ２４０とタグ比較機構２２４とラインデータ選択機構２２５とキャッシュ／メインメモリ選択機構２２６とＬＷアドレスデコーダ２２７とＬＷ選択機構２２８とで構成され、アドレスアレイ２２２とデータアレイ２２３はキャッシュメモリ２４０内に存在する。キャッシュコントローラ２２０は、マイクロプロセッサ２１０から入力されたアドレス２５１のデータがキャッシュメモリー２４０に格納されているかを調べ、格納されていた場合は、キャッシュミス信号２５５をネゲートし、キャッシュメモリー２４０からアドレス２５１のキャッシュされていたラインデータ２５８を読み出す。アドレス２５１のデータがキャッシュメモリー２４０に格納されていない場合は、キャッシュミス信号２５５をアサートし、メインメモリー２３０にアドレス２５１を出力し、メインメモリー２３０が出力するアドレス２５１のラインデータ２６１を読み出し、キャッシュメモリー２４０に格納する。さらに、キャッシュされていたラインデータ２５８またはラインデータ２６１からＬＷデータ２６２を抽出しマイクロプロセッサ２１０に出力する。
【００３２】
上位アドレスデコーダ２２１は、アドレス２５１からタグ２５２とエントリ番号２５３を生成する。マイクロプロセッサ２１０のアドレス空間は、エントリ番号２５３で区別されるエントリに分割して管理され、各エントリに格納するラインデータやタグはキャッシュメモリ２４０に記憶される。
【００３３】
アドレスアレイ２２２は、エントリ番号２５３で区別されるエントリ毎に、キャッシュしているラインデータのアドレスを示すタグを格納する配列であり、キャッシュメモリ２４０内に記憶される。
【００３４】
データアレイ２２３は、エントリ番号２５３で区別されるエントリ毎に、ラインデータを格納する配列であり、キャッシュメモリ２４０内に記憶される。アドレスアレイ２２２とデータアレイ２２３の要素は対応しており、例えば、データアレイ２２３のｉ行ｊ列目のラインデータのアドレスは、アドレスアレイ２２２のｉ行ｊ列目のタグにより示される。
【００３５】
タグ比較機構２２４は、タグ候補２５４とタグ２５２を入力し、タグ候補２５４の中にタグ２５２と一致するタグがあった場合は、一致したタグのウェイ番号２５７を出力し、キャッシュミス信号２５５をネゲートする。一致するタグがなかった場合は、キャッシュミス信号２５５をアサートする。
【００３６】
ラインデータ選択機構２２５は、ラインデータ候補２５６とウェイ番号２５７を入力し、ラインデータ候補２５６からウェイ番号２５７のラインデータをキャッシュされていたラインデータ２５８として出力する。
【００３７】
キャッシュ／メインメモリ選択機構２２６は、キャッシュミス信号２５５がアサートされている場合、ラインデータ２６１を読み出すＬＷデータを含むラインデータ２５９として出力し、キャッシュミス信号２５５がネゲートされている場合、キャッシュされていたラインデータ２５８を読み出すＬＷデータを含むラインデータ２５９として出力するセレクタである。
【００３８】
ＬＷアドレスデコーダ２２７は、アドレス２５１をＬＷアドレス２６０に変換し出力する。例えば、ラインデータのサイズが１２８ビット、ＬＷデータのサイズが３２ビットである時、ラインデータには４つのＬＷデータが含まれる。これらの４つのＬＷデータを識別するためにはＬＷアドレスとして２ビット必要である。そこでＬＷアドレスデコーダ２２７は、アドレス２５１の下位アドレス２ビットを抽出して、ＬＷアドレス２６０として出力する。
【００３９】
ＬＷ選択機構２２８は、出力するＬＷデータを含むラインデータ２５９からＬＷアドレス２６０で指定されるＬＷデータ２６２を抽出する。例えば、ラインデータ２５９が４つのＬＷデータで構成される場合、各ＬＷデータにはそれぞれ０，１，２，３のＬＷアドレスが割り当てられる。ＬＷ選択機構２２８は、ＬＷアドレス２６０で指定されるアドレスのＬＷデータを出力する。
【００４０】
メインメモリー２３０は、キャッシュコントローラ２２０が出力したキャッシュミス信号２５５がアサートされている場合、キャッシュコントローラ２２０が出力したアドレス２５１のラインデータ２６１をキャッシュコントローラ２２０に出力する。
【００４１】
次に、本実施形態のキャッシュ機構のデータ読み出し時における動作を図１、５を用いて説明する。アドレスアレイ２２２とデータアレイ２２３は、エントリ番号２５３とウェイ番号２５７をインデックスとする２次行列であり、キャッシュメモリ２４０内に存在する。説明のためにキャッシュ機構のウェイ数を４、エントリ数をエントリ番号０から１２７までの１２８エントリ、ラインデータのサイズを１２８ビット、１エントリはウェイ番号０から３までの４ウェイとする。このとき、アドレスアレイ２２２とデータアレイ２２３は、図１に示すようなエントリ番号２５３とウェイ番号２５７でそれぞれ行と列を示す１２８行４列の２次行列として表現できる。さらに、ＬＷデータはマイクロプロセッサ２１０のデータアクセス単位でありサイズは３２ビットとすると、１つのラインデータは４つのＬＷデータで構成される。データアレイ２２３の各要素はラインデータである。
【００４２】
尚、本実施形態は上記の構成のみならず、任意のウェイ数・エントリ数・ラインデータのサイズ・ＬＷデータのサイズの構成に対して適用可能である。
【００４３】
（Ｓ５０１）キャッシュコントローラ２２０はＬＷデータ２６２の読み出し要求を受け、（Ｓ５０２）読み出すアドレス２５１を入力される。（Ｓ５０３）次に、キャッシュコントローラ２２０は上位アドレスデコーダ２２１にアドレス２５１を入力し、タグ２５２とエントリ番号２５３を求める。ここで、エントリ番号２５３の値をｉとする。上位アドレスデコーダ２２１に関しては後で詳細に説明する。（Ｓ５０４）次に、キャッシュコントローラ２２０はアドレスアレイ２２２のｉ行目をタグ候補２５４として抽出する。（Ｓ５０５）次に、キャッシュコントローラ２２０はタグ比較機構２２４にタグ２５２とタグ候補２５４を入力し、ウェイ番号２５７とキャッシュミス信号２５５を得る。タグ候補２５４の１つ以上の要素の値とタグ２５２の値が一致すれば、タグ比較機構２２４はキャッシュミス信号２５５をネゲートする。タグ候補２５４の１つ以上の要素の値とタグ２５２の値が一致しなければ、タグ比較機構２２４はキャッシュミス信号２５５をアサートする。
【００４４】
（Ｓ５０６）次に、キャッシュコントローラ２２０は、キャッシュミス信号２５５を調べ、（Ｓ５０７）キャッシュミス信号がネゲートされている場合、データアレイ２２３のｉ行目をラインデータ候補２５６として求め、（Ｓ５０８）ラインデータ選択機構２２５にウェイ番号２５７とラインデータ候補２５６を入力し、キャッシュされていたラインデータ２５８を求め、（Ｓ５０９）キャッシュされていたラインデータ２５８を、読み出すＬＷデータを含むラインデータ２５９として選択し、読み出すＬＷデータを含むラインデータ２５９をＬＷ選択機構２２８に入力する。
【００４５】
（Ｓ５２１）キャッシュミス信号がアサートされている場合、キャッシュコントローラ２２０は、メインメモリ２３０からアドレス２５１のラインデータ２６１を読み出し、（Ｓ５２２）アドレスアレイ２２２のｉ行目の空いている列がある場合は、空いている列から１つ選択し、その列にタグ２５２を登録する。アドレスアレイ２２２のｉ行目に空いている列がない場合は、列を１つ選択し、その列にタグ２５２を上書きして登録する。ここでタグ２５２を登録した列、即ちウェイ番号をｊとする。続いて、キャッシュコントローラ２２０は、データアレイ２２３のｉ行目のｊ列目にラインデータを登録する。タグの登録する列の決め方は、一例として、アドレスアレイ２２２のｉ行目に空いている列がある場合は最小番号の列に登録し、アドレスアレイ２２２のｉ行目に空いている列がない場合はＬＲＵアルゴリズム等に則り、読み出されてからの時間が最も長いタグが登録されている列に上書きして登録すればよい。（Ｓ５２３）さらに、キャッシュコントローラ２２０は、ラインデータ２６１を、読み出すＬＷデータを含むラインデータ２５９として選択し、読み出すＬＷデータを含むラインデータ２５９をＬＷ選択機構２２８に入力する。
【００４６】
（Ｓ５１０）次に、キャッシュコントローラ２２０は、ＬＷアドレスデコーダ２２７にアドレス２５１を入力し、ＬＷアドレス２６０を求め、（Ｓ５１１）ＬＷ選択機構２２８にＬＷアドレス２６０と、読み出すＬＷデータを含むラインデータ２５９を入力し、ＬＷデータ２６２を求め、（Ｓ５１２）求めたＬＷデータ２６２を出力し、（Ｓ５１３）読み出し要求に対する動作を終了する。
【００４７】
図５のフローチャートでは、Ｓ５０６で条件を判断の結果に応じて、キャッシュコントローラ２２０は、Ｓ５０７、５０８、５０９の一連の処理か、またはＳ５２１、５２２、５２３の一連の処理を行うように描いているが、Ｓ５０７、５０８の一連の処理と、Ｓ５２１、５２２の一連の処理を平行して行い、Ｓ５０９とＳ５２３の処理をキャッシュ／メインメモリ選択機構２２６で行ってもよい。この場合、キャッシュコントローラ２２０は、キャッシュされていたラインデータ２５８とラインデータ２６１とキャッシュミス信号２５５をキャッシュ／メインメモリ選択機構２２６に入力し、読み出すＬＷデータを含むラインデータ２５９を得る。
【００４８】
次に、本実施形態の上位アドレスデコーダ２２１でのエントリ番号の生成方法を図３、６を用いて説明する。
【００４９】
説明のために、アドレス２５１のサイズを３２ビット、ラインデータのサイズは１６バイト、エントリ数は１２８エントリとする。また、アドレス［ａ：ｂ］という表記は、アドレス２５１のビットａからビットｂまでを取り出したビット列を示す。
【００５０】
ラインデータのサイズが１６バイトであるので、アドレス［３：０］（６０１）の４ビットでライン内のバイトデータの位置を示す。エントリ数が１２８エントリであるので、エントリ番号は７ビット必要である。１つのエントリに含まれる可能性のあるラインの総数は２＾（３２−４−７）個であるので、各ラインを区別するために２１ビット必要とする。そこで式６１０に示すように、アドレス［３１：１１］（６０３）の２１ビットをタグとして使用する。このために、図３の上位アドレスデコーダ２２１は、アドレス２５１からアドレス［３１：１１］（６０３）をサブアドレスＡ３１１として抽出し、サブアドレスＡ３１１をタグ２５２として出力する。
【００５１】
従来のキャッシュ機構は式６１１に示すように、アドレス［１０：４］（６０２）の７ビットをエントリ番号としていた。
【００５２】
本実施形態の上位アドレスデコーダ２２１は式６１２に示すように、アドレス［１７：１１］（６０４）とアドレス［１０：４］（６０２）を加算して２＾７で剰余を取ったものをエントリ番号として出力する。このために、図３の上位アドレスデコーダ２２１は、アドレス２５１からアドレス［１０：４］（６０２）をサブアドレスＢ３１２として求め、変換機構３０１によりアドレス［１７：１１］を変換値３１３として求め、加算器３０２によりサブアドレスＢ３１２と変換値３１３を加算してエントリ番号２５３として出力する。加算器３０２は最上位ビットで発生するキャリーを無視することにより２＾７の剰余を取っている。これにより、アドレス［１０：４］（６０２）が同じラインでもアドレス［１７：１１］（６０４）の値によって異なるエントリに格納され、またアドレス［１７：１１］（６０４）の値が同じラインはアドレス［１０：４］（６０２）の値によりすべて異なるエントリに格納されるため、前に述べたサイズが大きいの構造体の配列を扱う場合でも効率良くキャッシュメモリが使用される。さらに、連続するラインであればアドレス［１０：４］（６０２）による隣接関係がキャッシュエントリでも保たれることから、使用されるキャッシュエントリの予測が容易であり、効率良くキャッシュを使用するソフトウェアを開発しやすい。
【００５３】
さらに、上位アドレスデコーダ２２１の変換機構３０１は、アドレス［３１：２５］（６０６）とアドレス［２４：１８］（６０５）とアドレス［１７：１１］（６０４）とを加算したものを変換値３１３として出力する。これにより、本実施形態の上位アドレスデコーダ２２１は式６１３に示すように、アドレス［３１：２５］（６０６）とアドレス［２４：１８］（６０５）とアドレス［１７：１１］（６０４）とアドレス［１０：４］（６０２）を加算して２＾７で剰余を取ったものをエントリ番号として出力する。
【００５４】
さらに、上位アドレスデコーダ２２１の変換機構３０１は、アドレス［３１：１１］（６０３）の各部分ビット列に対し加算、排他的論理和、反転などの変換を繰り返し組み合わせて適用した値を変換値３１３として出力する。変換機構３０１による変換を関数ｆとして表すと、本実施形態の上位アドレスデコーダ２２１は式６１４に示すように、アドレス［３１：１１］（６０３）を関数ｆで変換した値とアドレス［１０：４］（６０２）とを加算して２＾７で剰余を取ったものをエントリ番号として出力する。変換機構３０１は、設定記憶機構３１４を持ち、加算、排他的論理和、反転などの変換の組み合わせ方を外部から設定し、設定を記憶し、現在の設定の内容を外部に出力することができる。この設定は本実施形態のキャッシュ機構を持つキャッシュコントローラ２２０の生産時に与えてもよいし、また外部からユーザが設定可能であってもよい。
【００５５】
さらに、上位アドレスデコーダ２２１は、アドレス２５１の各部分ビット列に対し加算、排他的論理和、反転などの変換を繰り返し組み合わせて適用した値をエントリ番号２５３として出力する。本実施形態の上位アドレスデコーダ２２１による変換を関数ｇとして表すと、エントリ番号は式６１５に示される。上位アドレスデコーダ２２１は、加算、排他的論理和、反転などの変換の組み合わせ方を外部から設定し、設定を記憶し、現在の設定の内容を外部に出力することができる。この設定は本実施形態のキャッシュ機構を持つシステムの生産時に与えることができ、またユーザが設定可能であってもよい。
【００５６】
本実施形態のキャッシュ機構において、上位アドレスデコーダ２２１の加算器３０２は、排他的論理和などのサブアドレスＢ３１２と変換値３１３を入力しエントリ番号２５３を出力する他の演算器に置き換えることができる。置き換える演算器は、サブアドレスＢ３１２が同じ値をとる場合、変換値３１３とエントリ番号２５３が一対一対応し、変換値３１３が同じ値をとる場合、サブアドレスＢ３１２とエントリ番号２５３が一対一対応ものであればキャッシュメモリ２４０の使用効率がよい。
【００５７】
以上、説明のために、プロセッサのアクセス単位は３２ビット、エントリ数は１２８エントリ、ウェイ数は４ウェイのように具体的な構成を仮定したが、本実施形態のキャッシュ機構は上で仮定した構成のみならず、任意のシステム構成に適用可能である。
【００５８】
また、本実施形態のキャッシュ機構では書き込みにおいて、上記で説明したのと同様にタグとエントリ番号を生成することで、ライトバックおよびライトスルーでキャッシュを行う。ライトキャッシュをライトバックするか、あるいはライトスルーにするかは外部からの設定により決めることができる。
（第２の実施の形態）
本実施形態のキャッシュ機構を持つ計算機システム４００で動作するプログラムは、キャッシュのエントリ番号の生成の仕方を知ることが可能である。これにより、読み出すデータが格納されるキャッシュエントリを知ることができる。また、キャッシュのエントリ番号の生成の仕方を変更することができる。これにより、既にメインメモリーに格納してあるデータが効率よくキャッシュに格納されるようにすることができる。
【００５９】
いくつかの要素で構成される構造体の配列をメモリー上に確保する場合、この構造体のサイズをＳバイトとすると、２＾（ｎ−１）＜Ｓ≦２＾ｎ（但し、ｎは１以上の整数、＾はべき乗を示す）を満たす２＾ｎバイトの要素の配列を確保し、その配列の各要素の先頭から構造体を格納することができる。これを構造体の配列としＳＴで表す。構造体の配列に含まれるｋ番目の構造体をＳＴ［ｋ］（但し、ｋは１以上の整数）、ＳＴ［ｋ］の要素の一つをＳＴ［ｋ］．ａとすると、配列の要素が隙間なくメモリー上に存在すれば、異なるｋにおいても、ＳＴ［ｋ］の先頭アドレスの下位ｎビットはすべて等しくなり、ＳＴ［ｋ］．ａの下位ｎビットも等しくなる。これにより、ｋを変化させてＳＴ［ｋ］．ａを連続して読み込む場合、下位ｎビットを変化させずに上位ビットのみを変化させるだけで読み出しが可能であるため、アドレスの演算が容易に行える。但し、ＳＴ［ｋ］の先頭を基準とした時のＳＴ［ｋ］．ａの相対アドレスはすべてのｋにおいて等しいものとする。
【００６０】
構造体のサイズが６５５３６（＝２＾１６）バイトとすると、ＳＴ［ｋ］．ａのｋを変えて読み出すとき、読み出すアドレスはビット１６より上位のみが変化し、ビット１５以下は変化しない。この場合、キャッシュエントリ数が１２８（＝２＾７）エントリであれば、キャッシュのエントリ番号をビット１６からビット２２をエントリ番号とすると効率よくキャッシュメモリにラインが格納される。したがって、プログラムはアドレスのビット１６からビット２２からエントリ番号を生成するようにキャッシュのエントリ番号の生成方法を設定することにより、キャッシュを効率よく利用することができる。
【００６１】
【発明の効果】
本発明によれば、計算機システムのキャッシュ機構においてキャッシュメモリを効率的に利用し、キャッシュミス率を下げ、計算機システムの性能を向上することができる。
【図面の簡単な説明】
【図１】本実施形態のキャッシュコントローラ２２０の動作を説明するための図である。
【図２】本実施形態のキャッシュ機構のデータフローを説明するための図である。
【図３】上位アドレスデコーダ２２１の構成例を説明するための図である。
【図４】本実施形態のキャッシュ機構を適用した計算機システム４００の構成例を説明するための図である。
【図５】読み出し時のキャッシュコントローラ２２０の動作例を説明するためのフローチャートである。
【図６】タグ２５２とエントリ番号２５３を生成する方法を説明するための図である。
【符号の説明】
２１０・・・マイクロプロセッサ、２２０・・・キャッシュコントローラ、２３０・・・メインメモリー、２４０・・・キャッシュメモリー、２２１・・・上位アドレスデコーダ、２２２・・・アドレスアレイ、２２３・・・データアレイ、２２４・・・タグ比較機構、２２５・・・ラインデータ選択機構、２２６・・・キャッシュ／メインメモリ選択機構、２２７・・・ＬＷアドレスデコーダ、２２８・・・ＬＷ選択機構、２５１・・・アドレス、２５２・・・タグ、２５３・・・エントリ番号、２５４・・・タグ候補、２５５・・・キャッシュミス信号、２５６・・・ラインデータ候補、２５７・・・ウェイ番号、２５８・・・キャッシュされていたラインデータ、２５９・・・読み出すＬＷデータを含むラインデータ、２６０・・・ＬＷアドレス、２６１・・・ラインデータ、２６２・・・データ、２６３・・・タグ候補２５４の中でタグ２５２と一致するタグ、３０１・・・変換機構、３０２・・・加算器、３１１・・・サブアドレスＡ、３１２・・・サブアドレスＢ、３１３・・・変換値、３１４・・・設定記憶機構、４００・・・計算機システム、４０１・・・内部バス、４０３・・・外部バス、４１０・・・外部インターフェース、６０１・・・アドレス［３：０］（アドレス２５１のビット３からビット０）、６０２・・・アドレス［１０：４］（アドレス２５１のビット１０からビット４）、６０３・・・アドレス［３１：１１］（アドレス２５１のビット３１からビット１１）、６０４・・・アドレス［１７：１１］（アドレス２５１のビット１７からビット１１）、６０５・・・アドレス［２４：１８］（アドレス２５１のビット２４からビット１８）、６０６・・・アドレス［３１：２５］（アドレス２５１のビット３１からビット２５）。
【図１】
2004118372.tif 000003
【図２】
2004118372.tif 000004
【図３】
2004118372.tif 000005
【図４】
2004118372.tif 000006
【図５】
2004118372.tif 000007
【図６】
2004118372.tif 000008