(57)【要約】【課題】  同じデータに頻繁にアクセスされるような場合であっても、キャッシュメモリの高速性をできるだけ損なわずに、キャッシュへのヒット率を可変制御できる、より好適なキャッシュ装置および演算装置の提供。【解決手段】キャッシュコントローラ４は、プロセッサ１と主メモリ２との間に接続される。また、キャッシュコントローラ４は、主メモリ２より高速に読み書き可能なキャッシュメモリ３と接続される。キャッシュメモリ３には、主メモリ上２のアドレスを示すタグ部１１とキャッシュブロック１３の容量値を保持する容量部１２とキャッシュブロック１３からなるキャッシュライン１４を複数備えており、プロセッサ１から主メモリ１へ読み出し要求の際、キャッシュコントローラ４は、キャッシュメモリ３に、前記要求される内容が有るか否かを調べる。キャッシュ容量決定部２２は、キャッシュブロック１５の容量値を決定し、容量部１２へ提供する。【選択図】図４
2007011689.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサと主メモリとの間に接続されるキャッシュ装置であって、
前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持領域に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の容量値を保持する容量保持部とが対応付けて複数備える、前記主メモリより読み書きのアクセスが高速なメモリと、
前記タグ部に保持される各アドレスと、プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持部へ内容読み出しを指示する比較演算器と、
前記容量保持部への各容量値を決定し、前記容量保持部へそれぞれ決定された各容量値を設定する容量値決定手段とを備えたことを特徴とするキャッシュ装置。
【請求項２】
前記比較演算器でのアドレスの比較部分を、前記容量保持部で保持する各容量値に基づいて決定するようにすることを特徴とする請求項１に記載のキャッシュ装置。
【請求項３】
前記容量値決定手段は、各容量値を乱数生成器の出力値をもちいるか、あるいは前記乱数生成器の出力に基づいて複数の容量値から選択するようにしたことを特徴とする請求項１に記載のキャッシュ装置。
【請求項４】
前記容量値決定手段は、決定された各容量値で前記各容量保持部に保持される各容量値をそれぞれ変更するようにしたことを特徴とする請求項１に記載のキャッシュ装置。
【請求項５】
前記容量値決定手段は、暗号演算処理の際に動作させるようにしたことを特徴とする請求項１に記載のキャッシュ装置。
【請求項６】
プロセッサと主メモリとの間に接続されるキャッシュ装置であって、
前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持部に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の各先頭アドレスを保持する先頭アドレス保持部とが対応付けて複数備える、前記主メモリより読み書きのアクセスが高速なメモリと、
前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持領域へ内容読み出しを指示する比較演算器と、
前記先頭アドレス保持部への各アドレス値を決定し、前記先頭アドレス部へそれぞれ決定された各先頭アドレスを設定する先頭アドレス決定手段とを備えたことを特徴とするキャッシュ装置。
【請求項７】
前記比較演算器でのアドレスの比較部分を、先頭アドレスから各保持領域の容量値を求め、それら各容量に基づいて決定するようにすることを特徴とする請求項６に記載のキャッシュ装置。
【請求項８】
前記先頭アドレス決定手段は、内容保持部の容量値を乱数生成器に基づいて決定し、決定した容量値をオフセットとして次の内容保持部の先頭アドレスとするようにしたことを特徴とする請求項６に記載のキャッシュ装置。
【請求項９】
前記先頭アドレス決定手段は、暗号演算処理の開始時に動作させるようにしたことを特徴とする請求項６に記載のキャッシュ装置。
【請求項１０】
主メモリとバスを介して接続される演算装置であって、
プロセッサと、
前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持領域に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の容量値を保持する容量保持部とが対応付けて複数備える、前記主メモリより高速なキャッシュメモリと、
前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持部へ内容読み出しを指示する比較演算器と、前記容量保持部への各容量値を決定し、前記容量保持部へそれぞれ決定された各容量値を設定する容量値決定手段とを備えたキャッシュコントローラとを具備したことを特徴とする演算装置。
【請求項１１】
主メモリとバスを介して接続される演算装置であって、
プロセッサと、
前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持部に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の各先頭アドレスを保持する先頭アドレス保持部とが対応付けて複数備える、前記主メモリより高速なキャッシュメモリと、
前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持領域へ内容読み出しを指示する比較演算器と、
前記先頭アドレス保持部への各アドレス値を決定し、前記先頭アドレス部へそれぞれ決定された各先頭アドレスを設定する先頭アドレス決定手段とを備えたキャッシュコントローラとを具備したことを特徴とする演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置で利用されるキャッシュメモリの制御に係るものであって、特に各キャッシュラインの容量を制御するキャッシュ装置及び演算装置に関する。
【背景技術】
【０００２】
キャッシュ機構は、プロセッサからの主メモリへの読み出しや書き込みといったメモリアクセスに関し、プロセッサで繰り返し利用されるプログラムやデータをアクセスが低速な主メモリから読み出す代わりに、高速なキャッシュメモリから読み出す機構である。演算に利用するデータをメモリへ書き込んだり、読み出したりする間、演算処理装置はこれらのメモリへのアクセスが終了するまで演算を中断している。そのため、キャッシュ機構を用いることで、低速なメモリへアクセスするよりも、高速にアクセスできるメモリを利用することができるようになり、演算処理装置の処理時間を短くすることができる。以上のことから、キャッシュ機構を用いると、演算装置の処理能力を高める効果があり、最近のコンピュータは、多くの場合にはキャッシュ機構を備えている。
【０００３】
従来のキャッシュ機構の制御部は、キャッシュメモリにあるデータのアドレス情報とキャッシュメモリのデータの状態を示すフラグを含んだタグ部と、アクセスされるアドレスとタグ部の内容を比較する比較演算器がある。メモリアクセス時に、キャッシュメモリにデータがあるかどうかの判定は、この制御部で行う。メモリアクセス時に、キャッシュメモリにデータがあるとき、キャッシュヒットしたといい、キャッシュメモリにデータがないとき、もしくはキャッシュメモリのデータが何らかの理由で使えない状態のときは、キャッシュミスしたといい、メモリアクセス数に対して、キャッシュメモリにキャッシュヒットしたときの割合をヒット率という。
【０００４】
データを読み出す際に、キャッシュ機構を持っている演算装置においては、低速なメモリへアクセスする代わりに、高速なキャッシュメモリにあるデータを読み出して演算に用いる。キャッシュ機構は、一度アクセスされたアドレスのデータを保持し、決められたルールでデータの入れ替えを行う。そのため、一度アクセスされたデータに再びアクセスする場合には、キャッシュメモリのデータに対してアクセスする。このため、キャッシュメモリにデータがあるかどうかで、演算処理装置の処理時間が変わる。
【０００５】
キャッシュ機構は、本来は、上記のとおりデータ読み出しの高速化のために用いるものであるが、例えば、そのような特長を生かしつつも、複数備えるキャッシュメモリの全てを利用するのではなく選択的にそのうちの幾つかを利用して意図的にヒット率を制御することにより、プロセッサのビジー率を制御し、プロセッサ１の処理性能を一定に保つ技術も提案されている（例えば、特許文献１参照）。これは、ＣＰＵ負荷を一定とするためにＣＰＵ負荷を監視し、この監視結果をキャッシュコントローラに与え、キャッシュコントローラは、この結果に基づいてキャッシュメモリの個数を制御するというものであった。
【０００６】
また、キャッシュのヒット率を意図的に制御する別の例として、暗号装置に用いるキャッシュメモリのキャッシュミス回数を敢えて発生させて任意の平文に対し均一化することにより、キャッシュ攻撃による暗号解読法を防ぐものも提案されている（例えば、特許文献２参照）。
【特許文献１】特開平１０−２６９１４０号公報
【特許文献２】特開２００４−１２０３０７公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上記で説明したように、キャッシュ機構を備えつつも、意図的にキャッシュの本来の利点であるキャッシュヒットによる高速読み出しの性能を少し押さえる機能を備えたキャッシュ機構も、利用用途に応じては望まれつつある。
【０００８】
上記で説明した［特許文献１］のキャッシュ機構は、キャッシュメモリの個数を制御するというものであった。つまり、この方法では、キャッシュの数を増減することによって、キャッシュの総容量を変更し、キャッシュのヒット率を変更するものであった。しかしながら、この方法は、いろいろなデータへ少ない回数だけ繰り返しアクセスされるような場合にはキャッシュヒット率を低下させることができるものの、同じデータに頻繁にアクセスされるような場合では、一度だけキャッシュミスが生じるが、以降はキャッシュヒットするので、キャッシュのヒット率が低下しない、といった問題点があった。
【０００９】
一方、上記で説明した［特許文献２］のキャッシュ機構は、暗号化する平文によらず、均一化するよう制御するものであるから、結局はキャッシュのヒット率の低いものに合わせるようにする必要があり、キャッシュ機構の存在自身にあまりメリットが生じないという問題点が内在していた。
【００１０】
本発明は、上記課題に鑑みなされたものであって、同じデータに頻繁にアクセスされるような場合であっても、キャッシュメモリの高速性をできるだけ損なわずに、キャッシュへのヒット率を可変制御できる、より好適なキャッシュ装置および演算装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、プロセッサと主メモリとの間に接続されるキャッシュ装置であって、前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持領域に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の容量値を保持する容量保持部とが対応付けて複数備える、前記主メモリより読み書きのアクセスが高速なメモリと、前記タグ部に保持される各アドレスと、プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持部へ内容読み出しを指示する比較演算器と、前記容量保持部への各容量値を決定し、前記容量保持部へそれぞれ決定された各容量値を設定する容量値決定手段とを備えた。
【００１２】
また、本発明は、プロセッサと主メモリとの間に接続されるキャッシュ装置であって、前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持部に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の各先頭アドレスを保持する先頭アドレス保持部とが対応付けて複数備える、前記主メモリより読み書きのアクセスが高速なメモリと、前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持領域へ内容読み出しを指示する比較演算器と、前記先頭アドレス保持部への各アドレス値を決定し、前記先頭アドレス部へそれぞれ決定された各先頭アドレスを設定する先頭アドレス決定手段とを備えた。
【００１３】
また、本発明は、主メモリとバスを介して接続される演算装置であって、プロセッサと、前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持領域に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の容量値を保持する容量保持部とが対応付けて複数備える、前記主メモリより高速なキャッシュメモリと、前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持部へ内容読み出しを指示する比較演算器と、前記容量保持部への各容量値を決定し、前記容量保持部へそれぞれ決定された各容量値を設定する容量値決定手段とを備えたキャッシュコントローラとを具備した。
【００１４】
また、本発明は、主メモリとバスを介して接続される演算装置であって、プロセッサと、前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持部に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の各先頭アドレスを保持する先頭アドレス保持部とが対応付けて複数備える、前記主メモリより高速なキャッシュメモリと、前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持領域へ内容読み出しを指示する比較演算器と、前記先頭アドレス保持部への各アドレス値を決定し、前記先頭アドレス部へそれぞれ決定された各先頭アドレスを設定する先頭アドレス決定手段とを備えたキャッシュコントローラとを具備した。
【発明の効果】
【００１５】
本発明によれば、いろいろなデータへ少ない回数だけ繰り返しアクセスされるような場合でも、また、同じデータに頻繁にアクセスされるような場合でも、キャッシュへのヒット率を可変するよう制御できるようになった。
【発明を実施するための最良の形態】
【００１６】
以下に、本発明の実施の形態を、図面を用いて詳細に説明する。
【００１７】
一般にキャッシュ機構は、キャッシュ機構が管理する高速なメモリ(これをキャッシュメモリと呼ぶ)に収められているデータのアドレスの管理方法により、ダイレクトマップ方式、アソシエイティブ方式、nウェイアソシエイティブ方式の３つに大別される。キャッシュメモリの管理方式として若干の違いがあるが、基本的にはアドレスバス上のアドレスデータとキャッシュ機構が管理しているタグ部が一致するかどうかの判定を行うということは、すべての方式に共通している。以後の説明は、基本的にはすべての方式に共通している。
【００１８】
図１は、本実施の形態に係るシステム全体を示す機能ブロック図である。
【００１９】
プロセッサ１は、プログラムを実行するための演算処理を行うものである。主メモリ２は、プロセッサ１で実行されるプログラムや、プログラム実行時に利用するデータ（これらを総称して、以下単にデータと呼ぶ）などを格納するために半導体素子で構成される比較的低速で大容量なメモリであり、例えば、ＤＲＡＭなどで実現される。キャッシュメモリ３は、主メモリ２に記憶される内容の一部を一時的に保持するために揮発性の半導体素子で構成され、主メモリ２と比較して高速で小容量なメモリであり、例えば、ＳＲＡＭなどで実現される。
【００２０】
キャッシュコントローラ４は、プロセッサ１、主メモリ２、キャッシュメモリ３とそれぞれバス５を介して接続されている。キャッシュコントローラ４は、キャッシュメモリ３を制御するものであり、主に、プロセッサ１から主メモリ２へアクセスされるときにキャッシュメモリ３に保持していないかを判断し、保持していれば（ヒットと呼ぶ）キャッシュメモリ３から読み出してプロセッサ１へ送り、保持していなければ（ミスヒットと呼ぶ）主メモリ２から読み出されたデータをキャッシュメモリ３へ格納する処理を行うものである。
【００２１】
このキャッシュコントローラ４の処理の概略を、図２を用いて、簡単に説明する。（ａ）はミスヒットの場合の処理を示し、（ｂ）はヒットの場合の処理を示す。
【００２２】
まず、（ａ）について説明する。プロセッサ１から主メモリ２へ、主メモリ２上のあるアドレスを指定しデータの読出し要求を行う（Ｓ１１）。キャッシュコントローラ４は、その読出し要求の指定先のアドレスに対応するデータが、キャッシュメモリ３にも一時保持しているか否かを判断する（Ｓ１２）。キャッシュコントローラ４は、一時保持していない、つまりミスヒットであると判断すると、その読出し要求を主メモリ２へ転送する（Ｓ１３）。主メモリ２は、転送された読出し要求を受信し、指定先のアドレスが示す記憶領域からデータを読出し、その読出されたデータを、プロセッサ１へ向けて送信する（Ｓ１４）。キャッシュコントローラ４は、この送信されたデータを受け取って、プロセッサ１へ転送する（Ｓ１５）。また、キャッシュコントローラ４は、データとこのデータに対応する主メモリ２上のアドレスをキャッシュメモリ３へ一時保持させる（Ｓ１６）。以上のような処理により、キャッシュメモリ３に新たなデータが一時保持される。
【００２３】
次に、（ｂ）について説明する。プロセッサ１から主メモリ２へ、主メモリ２上のあるアドレスを指定しデータの読出し要求を行う（Ｓ２１）。キャッシュコントローラ４は、その読出し要求の指定先のアドレスに対応するデータが、キャッシュメモリ３にも一時保持しているか否かを判断する（Ｓ２２）。キャッシュコントローラ４は、一時保持している、つまりヒットであると判断すると、その読出し要求されたアドレスに対応するデータを一時保持しているキャッシュメモリ３の領域へ読出し要求を行う（Ｓ２３）。
【００２４】
キャッシュメモリ３は、キャッシュコントローラ４からの読出し要求により、その領域からデータを読出し、読み出されたデータをキャッシュコントローラ４へ送信する（Ｓ２４）。キャッシュコントローラ４は、この送信されたデータをプロセッサ１へ転送する（Ｓ２５）。以上のような処理により、キャッシュメモリ３からデータが読み出される。
【００２５】
なお、プロセッサ１、キャッシュメモリ３、キャッシュコントローラ４は、図１の点線に示すように演算装置として、同一パッケージで提供しても良い。また、特に図示しないがキャッシュメモリ３とキャッシュコントローラ４とが同一パッケージで提供されても良い。
【００２６】
次に、キャッシュメモリ３が記憶する内容の構成を図３に示す。
【００２７】
キャッシュメモリ３は、タグ部１１と容量部１２とキャッシュブロック１３とからなるキャッシュライン１４を複数個備える。キャッシュブロック１３には、主メモリ２から読み出されたデータのコピーを保持する。キャッシュブロック１３は、予め定められた固定の記憶容量（例えば、２５６ｂｉｔ）が割り当てられている。タグ部１１には、データが主メモリ２上に記憶されていた（先頭）アドレスを保持する。容量部１２には、キャッシュブロック１３の全容量の内の実際に利用する容量の値（例えば、１２８ｂｉｔ）を保持する。この容量部１２の値は、演算の開始時に決定し、保持すればよいが、更に、前の容量より同じか小さな容量となる制約を課すことによって、キャッシュブロック１３に保持されるデータの内容を変更せずに新たに容量を決定し、容量の変更を行うこともできる。
【００２８】
例えば、キャッシュブロック１３の予め定められた固定の記憶容量が２５６ｂｉｔで最小に変更可能な容量が８ｂｉｔの場合には、２５６ｂｉｔ、１２８ｂｉｔ、６４ｂｉｔ、３２ｂｉｔ、１６ｂｉｔ、８ｂｉｔの何れかから選ばれ、且つ、例えば、現在演算中で、容量が３２ｂｉｔの場合には、３２ｂｉｔ、１６ｂｉｔ、８ｂｉｔの何れかから選ばれる。なお、ここで、容量の値が２のべき乗である理由は、後述する。
【００２９】
上記制約は、キャッシュヒットを示した際には、必ずキャッシュブロック１３に要求されたデータが存在することを保証するためである。
【００３０】
繰り返しになるが、キャッシュブロック１３は、割り当てにおいてはそれぞれ物理的に容量が固定されているが、実際の利用（主に、読み出し）においては、利用許可する容量を可変にすることができるようになっている。なお、キャッシュラインには、これら以外に例えば、キャッシュメモリ３の状態（読み出し可／禁止、等）を示す情報、等を保持できるようにしてもよい。
【００３１】
次に、図４は、キャッシュコントローラ４の内、本実施の形態に係る機能についてのブロック図を示したものである。
【００３２】
タグ部読み出し部２１は、キャッシュメモリ３の各タグ部１１から、各アドレスを読み出すものである。
【００３３】
キャッシュ容量決定部２２は、各キャッシュブロック１３の容量をそれぞれ決定するためのものであり、ここでは、乱数回路または擬似乱数回路などを用いて、予め定めた数パターンの容量値から後述する制約の元、ランダムに選択し出力するよう構成する。
【００３４】
キャッシュ容量読み出し部２３は、キャッシュメモリ３の各容量部１２から、各容量値を読み出すものである。
【００３５】
比較演算部２４は、プロセッサ１から主メモリ２へ読み出し要求を行ったときに送られるアドレスが、タグ部読み出し部２１で読み出され各アドレスと、各アドレスに対応するキャッシュ容量読み出し部２３で読み出された各容量値とに基づく、各キャッシュライン１４のアドレスの範囲に含まれるか否かをそれぞれ比較するものである。比較演算部２４は、この比較結果の何れも否であるときには、キャッシュメモリ３に格納されていないことを示す信号をラッチ回路２５へ送信する。一方、比較演算部２４は、ある比較結果が含まれることを示したとき（キャッシュヒット）には、そのキャッシュライン１４のキャッシュブロック１３に対し読み出し要求を行う。
【００３６】
ラッチ回路２５は、プロセッサ１からのアドレスを一時的にラッチするものであって、比較演算部２４から前記信号を受けると、ラッチしているアドレスを主メモリ２と接続されるバス５へ出力する。
【００３７】
次に、比較演算部２４の内部回路構成の一例を、一つのキャッシュライン１４との比較に着目した構成を比較器３０として、図５に示し説明する。この一例の比較演算部２４−１の場合、キャッシュブロック１３の予め定められた固定の記憶容量、及び、キャッシュ容量決定部２２が決定する容量は、何れも２のべき乗である必要がある。また、当然ながら、キャッシュ容量決定部２２が決定する容量は、キャッシュブロック１３の予め定められた固定の記憶容量と同じかそれより小さい必要がある。そして、このような場合、キャッシュ容量決定部２２が決定する容量を、本実施の形態で用いるアドレスの幅で二値表現で表した時、下位からある桁までは全て１で、ある桁の次の桁から上位は全て０となる。
【００３８】
ＸＯＲ素子３１は、２つの入力が一致すると０を出力し、異なると１を出力する。このＸＯＲ素子３１を、図のように並列に配置し、各ＸＯＲ素子３１の、一方の入力をアドレスバス５からのアドレス（二値）とし、他方の入力をタグ部１２から読み出された各アドレス（二値）とし、互いのアドレスの同じ桁同士が比較されるようにする。ＸＯＲ素子３１の比較結果が一致すれば０が出力され不一致であれば１が出力されるから、本来はアドレスの一致／不一致はこれだけで把握できる。
【００３９】
しかしながら、プロセッサ１からのアドレスは、各キャッシュライン１４のアドレスの範囲の途中のアドレスであることが多く、このような場合もキャッシュヒットと判断する構成である必要がある。既存のキャッシュ機構の場合には、キャッシュブロックのサイズが固定であったので、キャッシュブロック毎に変わるアドレス中の上位アドレスの部分のみを比較することにより、一致／不一致を判断していた。一方、本実施の形態では、キャッシュブロック毎に容量を変更するようにしているから、比較する上位アドレスを固定にすることは出来ない。これを解決するために、この比較器３０では、キャッシュブロックの容量に応じた下位アドレスの比較結果をマスクするようにしている。
【００４０】
図５において、ＡＮＤ素子３２は、２つの入力がともに１の時のみ１を出力し、２つの入力のうち少なくとも一つが０の時、０を出力する。このＡＮＤ素子３２を図のように並列に配置し、各ＡＮＤ素子３２の、一方の入力をＸＯＲ素子３１の出力とし、他方の入力を容量部から読み出された容量を示す二値データを反転した値とする。従って、アドレスの下位から容量までに対応するＡＮＤ素子３２は、何れも０を出力し、それ以上に対応するＡＮＤ素子３２は、ＸＯＲ素子３１の出力そのものを出力する。
【００４１】
ＮＯＲ素子３３は、各ＡＮＤ素子の出力を入力する。ＮＯＲ素子３３は、全ての入力が０のときのみ、１を出力するから、出力が０ならばミスヒットであり、１であればヒットしたということがわかる。
【００４２】
以上のような比較器３０でひとつのキャッシュラインがヒットするかミスヒットするかがわかり、これらを並列的に用いることにより、キャッシュメモリの何れかにヒットしたかミスヒットしたかもわかる。その結果、キャッシュブロックの容量を変更する場合のアドレスと各タグ部１１が保持するアドレスが一致しているかどうかの判定を行う比較演算部２４を実現することができる。
【００４３】
次に、比較演算部２４の別の一例を示す。この例におけるキャッシュメモリ３が記憶する内容を図６に示すが、これを図３と比較すると、容量幅部４３を備えている点が新しく、その他のタグ部４１、容量部４２、及びキャッシュブロック４４は、図３のタグ部１１、容量部１２、キャッシュブロック部１３と同じである。
【００４４】
それぞれの容量幅部４３は、アドレスバス５のバス幅分のビットを備え、各キャッシュライン４５の各容量の値に基づき、アドレスバス５と容量部４３のマスクデータが格納される。具体的に格納されるマスクデータは、下位からｎビット（ここでｎは、ｎ≧１かつ２（ｎ−１）≦キャッシュブロックの容量＜２ｎを満たす）だけ１とし、残りのビットを０として保持している。例えば、キャッシュ容量が１５ｂｙｔｅなら下位から４ビットが“１”となり、１７ｂｙｔｅなら下位から５ビットが“１”となっている。なお、ここでも類推されるように、本例は、容量の値が２のべき乗で無くても構わない。
【００４５】
次に、図７に、本例の比較演算部２４−２の回路図を示す。
【００４６】
この例は、図上の点線より上部、即ち、ＸＯＲ素子３１、ＡＮＤ素子３２、ＮＯＲ素子３３で構成される部分は、ＮＯＲ素子３３の入力として後述する比較器５３からの出力を入力している点を除き、図５と同じであり説明を省略する。
【００４７】
ＡＮＤ素子５１は、図のように並列に配置し、一方の入力にアドレスバス５からのアドレス（二値）が、他方には容量幅部４３の各ビットが接続される。つまり、この並列化されたＡＮＤ素子５１では、アドレスの下位から容量幅部４３で保持しているビット幅分だけ、アドレスを有効として出力する。この出力は、比較器５３の一方に入力される。
【００４８】
ＡＮＤ素子５２は、図のように並列に配置し、一方の入力に容量部４２が、他方には容量幅部４３の各ビットが接続される。つまり、この並列化されたＡＮＤ素子５１でも、容量部４２の下位から容量幅部４３で保持しているビット幅分だけ、容量値を有効として出力する。この出力は、比較器５３の他方に入力される。
【００４９】
比較器５３には、上記説明から分かるように、容量幅部４３で保持しているビット幅分だけ、アドレスバス５からのアドレス（二値）と容量部４２からの容量値とが入力され、両者の大小が比較される。この比較の結果、アドレスのほうが大きければ、“１”を出力し、アドレスのほうが小さければ、“０”を出力する。このようにして、比較器５３の出力は、ＮＯＲ素子３３に入力される。
【００５０】
以上のことから、第１の比較演算部２４−１の例では、下位アドレスの比較結果をマスクするようにしていたが、本例の比較演算部２４−２の例では、下位アドレスをも比較対象としており、この結果、比較演算部２４−１では、２のべき乗でしか、容量値の指定が行えなかったが、本例の比較演算部２４−２では、２のべき乗に限ることなく、キャッシュブロックを超えない何れの容量値でも、指定できるようになった。つまり、このような本例によれば、各タグ部にキャッシュブロックの実利用容量を管理するための領域を追加するようにしたから、タグ部が管理するキャッシュブロックの実利用容量を可変とできるようになった。
【００５１】
次に、上記で説明した本発明の実施の形態では、キャッシュメモリ３を予め定められた固定の記憶容量とした複数のキャッシュブロックに割り当て、その後各キャッシュブロック内の容量を可変にするものであった。
【００５２】
これに対し変形例として、固定の記憶容量とした複数のキャッシュブロックに割り当てるのではなく、演算開始前にキャッシュメモリ３をそれぞれ異なった記憶容量で各キャッシュブロックとするようにしても良い。
【００５３】
この場合、図３に対比し、図８に示す一例のように、キャッシュブロック６３の容量を決定し、タグ部６１とキャッシュアドレス部６２とそのキャッシュブロック６３との対応関係を保つようにすれば良い。
【００５４】
キャッシュアドレス部６２には、対応するキャッシュブロック６３のキャッシュメモリ３上の先頭アドレスを備える。このキャッシュアドレス部６２への先頭アドレスの登録は、キャッシュメモリ３を利用する前に、各タグ部１１に対応付ける各キャッシュブロック６３の容量を、乱数回路などを用いて決定し、各タグ部の順に容量を積み上げるよう（追記的）にして、各キャッシュブロック６３の先頭アドレスを決定する。
【００５５】
具体的には、ｎ−１番目までのタグ部６１にあるキャッシュブロック６３の容量値を加算すると、ｎ−１番目までに割り当てたキャッシュメモリ３の容量となる。ｎ番目のタグ部６１が管理するキャッシュブロック６３は、ｎ−１番目が使っているキャッシュブロック６３の次のアドレスから利用する。言い換えれば、０番目からｎ−１番目までのタグ部６１のキャッシュブロック６３の容量を加算した値は、ｎ番目のタグ部６１のキャッシュメモリ３の先頭を表すアドレスのオフセットとして利用することができる。これにより、上記実施形態と比較し、例えば２つの先頭アドレスからキャッシュブロック容量を求める演算部（図示しない）が必要になるなどのより複雑な制御が必要になるが、一方では、タグ部１１の管理するキャッシュブロック６３の先頭アドレスを自由に変えることができるから、あるキャッシュブロックを既存に比べて大きな容量で取ることや、決定する容量も比較的自由に選定できる等、キャッシュメモリ３を有効に利用することができるようになる。
【００５６】
以上説明してきた、本実施の形態のキャッシュ機構（キャッシュメモリ３とキャッシュコントローラ４）は、例えば、暗号演算時に適用することにより、暗号演算処理時の耐解析性を向上させる効果が生じる。そこで、以下には本実施の形態を暗号演算へ適用した場合について説明する。
【００５７】
キャッシュ機構を備えた演算処理装置の暗号演算時において、主メモリ３とキャッシュメモリ
との読み出し時間差による処理時間の差を利用し、入力データ（平文）と処理時間との関係から、
暗号演算時の秘密情報を導出する解析手法がある。この、解析手法をキャッシュ攻撃といい、この解析手法について簡単に説明をする。
【００５８】
例えば、キャッシュ機構を備えた演算装置で、よく知られるＳ−ＢＯＸ等の換算用テーブルをｎ個用い、入力する平文を換算用テーブルの入力幅でＰｉ 個に分割した各分割データを、部分鍵ＫｉでＸＯＲ演算（下記式では“△”で代用する）する動作が繰り返し（ｍ回）行われる暗号アルゴリズム（例えば、ＤＥＳやＡＥＳ等）の場合、Ｓ−ＢＯＸ等の換算用テーブルの入力として、ＰｉとＫｉとのＸＯＲ演算の結果を用いる。１回の暗号演算の中で、ｎ個ある換算用テーブルの一つの換算テーブルに着目し、その換算テーブルの任意の２つの入力について以下のどちらかが成り立つ。
【００５９】
Ｐｉ  △  Ｋｉ＝  Pｊ  △  Ｋｊ  ・・・（Ａ）
Ｐｉ  △  Ｋｉ≠  Pｊ  △  Ｋｊ  ・・・（Ｂ）
（ｉ≠ｊ，０≦ｉ，ｊ＜ｍ）
上記（Ａ）の時には、必要な換算用テーブルが前回で（前ステップで）利用したものと同じであり、そのため主メモリから読み出されておりキャッシュメモリに保持されているため、キャッシュヒットし、（Ｂ）の時には、必要な換算用テーブルが前回で（前ステップで）利用したものと異なり、そのため主メモリから読み出されておりキャッシュメモリに保持されていないためキャッシュミスすることになる。つまり、途中結果が（Ａ）と（Ｂ）の時では、換算用テーブルを参照するためにアクセスする先がキャッシュメモリと主メモリとで異なるため、処理時間が大きく異なり、その結果、全体の処理時間を測定することにより、ｍ回の換算用テーブルへの入力値が同じか異なるかを判別することが出来る。
【００６０】
このような暗号アルゴリズムの元、入力する平文を工夫して選定する。この場合には、入力平文をランダムに生成した平文と比べて、実際にアクセスした換算用テーブルの内の要素数が少ない平文を作成し、そこから鍵差分を決定する。このようにすると、同じ換算用テーブルをアクセスすることが多いため、上記（Ａ）を利用してＰｉ  △  Pｊを計算し、最も出現回数が多かったもの、つまり暗号演算時間が短かったものを正しい鍵差分とする。
【００６１】
逆に、実際にアクセスした換算用テーブルの数が多い平文多数から鍵差分を決定することもできる。この場合には、異なる換算用テーブルをアクセスすることが多いため、上記（Ｂ）を利用してＰｉ  △  Pｊを計算し、最も出現回数が少なかったもの、つまり暗号演算時間が長かったものを正しい鍵差分とする。
【００６２】
以上のような方法を用いて鍵差分を生成し、そこから鍵情報を導出することができる。
【００６３】
上記で説明したキャッシュ攻撃の解析手法に対し、本実施の形態のキャッシュ機構を用いることに、対策を講じることができる。これについて説明する。
【００６４】
前記キャッシュ攻撃では、暗号演算時の処理時間が入力したデータと暗号演算時に使う秘密情報にのみ依存している場合に攻撃が成功する。従って、処理時間を変動することができるならば、攻撃を防ぐ対策となり得る。
【００６５】
処理時間の変動させるための一方法として、キャッシュのヒット率を変えることにより、キャッシュメモリ３へのアクセス回数と低速なメモリへのアクセス回数が変わり、その結果、暗号演算処理の処理時間が変更できる。
【００６６】
そこで、上記した本実施の形態のキャッシュコントローラを適用することにより、キャッシュメモリ３の容量の変更に応じてキャッシュのヒット率を変更させる。
【００６７】
この結果、攻撃者が想定している仮定である入力データと秘密情報によってのみ、処理時間が変動するという前提条件を崩す事ができ、キャッシュ攻撃に対する対策となる。
【００６８】
また、さらに、演算装置の暗号演算中の消費電力を測定し、秘密情報を導出するという差分消費電力解析(Differential Power Analysis)という攻撃方法も存在するが、この攻撃方法も処理時間を変動させることが攻撃に対する対策として有効であることが知られている。
【００６９】
そこで、演算処理装置に上記した本実施の形態のキャッシュコントローラを適用することにより、キャッシュブロックの容量の変更に応じてキャッシュのヒット率を変更させることで、処理時間も変動するから、ＤＰＡに対する対策としても有効である。
【００７０】
以上詳細に説明してきたように、本実施の形態によれば、いろいろなデータへ少ない回数だけ繰り返しアクセスされるような場合でも、また、同じデータに頻繁にアクセスされるような場合でも、キャッシュへのヒット率を可変するよう制御できるようになる。
【００７１】
また、前記何れの場合にも、キャッシュのヒット率を可変するよう制御できるから、暗号演算処理において、キャッシュ攻撃や、ＤＰＡに対する有効な対策ともなり得る。
【図面の簡単な説明】
【００７２】
【図１】本実施の形態に係るシステム全体を示す機能ブロック図。
【図２】キャッシュコントローラ４の処理の概略を示した図。
【図３】キャッシュメモリ３が記憶する内容の構成を示した図。
【図４】キャッシュコントローラ４の内、本実施の形態に係る機能について示したブロック図。
【図５】比較演算部２４の内部回路構成の一例。
【図６】キャッシュメモリ３が記憶する内容の別例。
【図７】比較演算部２４−２の内部回路構成を示す図。
【図８】キャッシュメモリ３が記憶する内容の構成の別例を示した図。
【符号の説明】
【００７３】
１・・・プロセッサ
２・・・主メモリ２
３・・・キャッシュメモリ
４・・・キャッシュコントローラ
５・・・バス
１１、４１、６１・・・タグ部
１２、４２・・・容量部
１３、４４、６２・・・キャッシュブロック
１４、４５・・・キャッシュライン
２１・・・タグ部読み出し部
２２・・・キャッシュ容量決定部
２３・・・キャッシュ容量読み出し部
２４、２４−１、２４−２・・・比較演算部
２５・・・ラッチ回路
３１・・・ＸＯＲ素子
３２、５１、５２・・・ＡＮＤ素子
３３・・・ＮＯＲ素子
４３・・・容量幅部
５３・・・比較器
６３・・・先頭アドレス部
【図１】
2007011689.tif 000003
【図２】
2007011689.tif 000004
【図３】
2007011689.tif 000005
【図４】
2007011689.tif 000006
【図５】
2007011689.tif 000007
【図６】
2007011689.tif 000008
【図７】
2007011689.tif 000009
【図８】
2007011689.tif 000010