米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 株式会社東芝

発明の名称 キャッシュ装置及び演算装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2007−11689(P2007−11689A)
公開日 平成19年1月18日(2007.1.18)
出願番号 特願2005−191654(P2005−191654)
出願日 平成17年6月30日(2005.6.30)
代理人 【識別番号】100109900
【弁理士】
【氏名又は名称】堀口 浩
発明者 藤崎 浩一 / 清水 秀夫
要約 課題
同じデータに頻繁にアクセスされるような場合であっても、キャッシュメモリの高速性をできるだけ損なわずに、キャッシュへのヒット率を可変制御できる、より好適なキャッシュ装置および演算装置の提供。

解決手段
キャッシュコントローラ4は、プロセッサ1と主メモリ2との間に接続される。
特許請求の範囲
【請求項1】
プロセッサと主メモリとの間に接続されるキャッシュ装置であって、
前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持領域に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の容量値を保持する容量保持部とが対応付けて複数備える、前記主メモリより読み書きのアクセスが高速なメモリと、
前記タグ部に保持される各アドレスと、プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持部へ内容読み出しを指示する比較演算器と、
前記容量保持部への各容量値を決定し、前記容量保持部へそれぞれ決定された各容量値を設定する容量値決定手段とを備えたことを特徴とするキャッシュ装置。
【請求項2】
前記比較演算器でのアドレスの比較部分を、前記容量保持部で保持する各容量値に基づいて決定するようにすることを特徴とする請求項1に記載のキャッシュ装置。
【請求項3】
前記容量値決定手段は、各容量値を乱数生成器の出力値をもちいるか、あるいは前記乱数生成器の出力に基づいて複数の容量値から選択するようにしたことを特徴とする請求項1に記載のキャッシュ装置。
【請求項4】
前記容量値決定手段は、決定された各容量値で前記各容量保持部に保持される各容量値をそれぞれ変更するようにしたことを特徴とする請求項1に記載のキャッシュ装置。
【請求項5】
前記容量値決定手段は、暗号演算処理の際に動作させるようにしたことを特徴とする請求項1に記載のキャッシュ装置。
【請求項6】
プロセッサと主メモリとの間に接続されるキャッシュ装置であって、
前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持部に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の各先頭アドレスを保持する先頭アドレス保持部とが対応付けて複数備える、前記主メモリより読み書きのアクセスが高速なメモリと、
前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持領域へ内容読み出しを指示する比較演算器と、
前記先頭アドレス保持部への各アドレス値を決定し、前記先頭アドレス部へそれぞれ決定された各先頭アドレスを設定する先頭アドレス決定手段とを備えたことを特徴とするキャッシュ装置。
【請求項7】
前記比較演算器でのアドレスの比較部分を、先頭アドレスから各保持領域の容量値を求め、それら各容量に基づいて決定するようにすることを特徴とする請求項6に記載のキャッシュ装置。
【請求項8】
前記先頭アドレス決定手段は、内容保持部の容量値を乱数生成器に基づいて決定し、決定した容量値をオフセットとして次の内容保持部の先頭アドレスとするようにしたことを特徴とする請求項6に記載のキャッシュ装置。
【請求項9】
前記先頭アドレス決定手段は、暗号演算処理の開始時に動作させるようにしたことを特徴とする請求項6に記載のキャッシュ装置。
【請求項10】
主メモリとバスを介して接続される演算装置であって、
プロセッサと、
前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持領域に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の容量値を保持する容量保持部とが対応付けて複数備える、前記主メモリより高速なキャッシュメモリと、
前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持部へ内容読み出しを指示する比較演算器と、前記容量保持部への各容量値を決定し、前記容量保持部へそれぞれ決定された各容量値を設定する容量値決定手段とを備えたキャッシュコントローラとを具備したことを特徴とする演算装置。
【請求項11】
主メモリとバスを介して接続される演算装置であって、
プロセッサと、
前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持部に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の各先頭アドレスを保持する先頭アドレス保持部とが対応付けて複数備える、前記主メモリより高速なキャッシュメモリと、
前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持領域へ内容読み出しを指示する比較演算器と、
前記先頭アドレス保持部への各アドレス値を決定し、前記先頭アドレス部へそれぞれ決定された各先頭アドレスを設定する先頭アドレス決定手段とを備えたキャッシュコントローラとを具備したことを特徴とする演算装置。

発明の詳細な説明
【技術分野】
【0001】
本発明は、演算処理装置で利用されるキャッシュメモリの制御に係るものであって、特に各キャッシュラインの容量を制御するキャッシュ装置及び演算装置に関する。
【背景技術】
【0002】
キャッシュ機構は、プロセッサからの主メモリへの読み出しや書き込みといったメモリアクセスに関し、プロセッサで繰り返し利用されるプログラムやデータをアクセスが低速な主メモリから読み出す代わりに、高速なキャッシュメモリから読み出す機構である。演算に利用するデータをメモリへ書き込んだり、読み出したりする間、演算処理装置はこれらのメモリへのアクセスが終了するまで演算を中断している。そのため、キャッシュ機構を用いることで、低速なメモリへアクセスするよりも、高速にアクセスできるメモリを利用することができるようになり、演算処理装置の処理時間を短くすることができる。以上のことから、キャッシュ機構を用いると、演算装置の処理能力を高める効果があり、最近のコンピュータは、多くの場合にはキャッシュ機構を備えている。
【0003】
従来のキャッシュ機構の制御部は、キャッシュメモリにあるデータのアドレス情報とキャッシュメモリのデータの状態を示すフラグを含んだタグ部と、アクセスされるアドレスとタグ部の内容を比較する比較演算器がある。メモリアクセス時に、キャッシュメモリにデータがあるかどうかの判定は、この制御部で行う。メモリアクセス時に、キャッシュメモリにデータがあるとき、キャッシュヒットしたといい、キャッシュメモリにデータがないとき、もしくはキャッシュメモリのデータが何らかの理由で使えない状態のときは、キャッシュミスしたといい、メモリアクセス数に対して、キャッシュメモリにキャッシュヒットしたときの割合をヒット率という。
【0004】
データを読み出す際に、キャッシュ機構を持っている演算装置においては、低速なメモリへアクセスする代わりに、高速なキャッシュメモリにあるデータを読み出して演算に用いる。キャッシュ機構は、一度アクセスされたアドレスのデータを保持し、決められたルールでデータの入れ替えを行う。そのため、一度アクセスされたデータに再びアクセスする場合には、キャッシュメモリのデータに対してアクセスする。このため、キャッシュメモリにデータがあるかどうかで、演算処理装置の処理時間が変わる。
【0005】
キャッシュ機構は、本来は、上記のとおりデータ読み出しの高速化のために用いるものであるが、例えば、そのような特長を生かしつつも、複数備えるキャッシュメモリの全てを利用するのではなく選択的にそのうちの幾つかを利用して意図的にヒット率を制御することにより、プロセッサのビジー率を制御し、プロセッサ1の処理性能を一定に保つ技術も提案されている(例えば、特許文献1参照)。これは、CPU負荷を一定とするためにCPU負荷を監視し、この監視結果をキャッシュコントローラに与え、キャッシュコントローラは、この結果に基づいてキャッシュメモリの個数を制御するというものであった。
【0006】
また、キャッシュのヒット率を意図的に制御する別の例として、暗号装置に用いるキャッシュメモリのキャッシュミス回数を敢えて発生させて任意の平文に対し均一化することにより、キャッシュ攻撃による暗号解読法を防ぐものも提案されている(例えば、特許文献2参照)。
【特許文献1】特開平10−269140号公報
【特許文献2】特開2004−120307公報
【発明の開示】
【発明が解決しようとする課題】
【0007】
上記で説明したように、キャッシュ機構を備えつつも、意図的にキャッシュの本来の利点であるキャッシュヒットによる高速読み出しの性能を少し押さえる機能を備えたキャッシュ機構も、利用用途に応じては望まれつつある。
【0008】
上記で説明した[特許文献1]のキャッシュ機構は、キャッシュメモリの個数を制御するというものであった。つまり、この方法では、キャッシュの数を増減することによって、キャッシュの総容量を変更し、キャッシュのヒット率を変更するものであった。しかしながら、この方法は、いろいろなデータへ少ない回数だけ繰り返しアクセスされるような場合にはキャッシュヒット率を低下させることができるものの、同じデータに頻繁にアクセスされるような場合では、一度だけキャッシュミスが生じるが、以降はキャッシュヒットするので、キャッシュのヒット率が低下しない、といった問題点があった。
【0009】
一方、上記で説明した[特許文献2]のキャッシュ機構は、暗号化する平文によらず、均一化するよう制御するものであるから、結局はキャッシュのヒット率の低いものに合わせるようにする必要があり、キャッシュ機構の存在自身にあまりメリットが生じないという問題点が内在していた。
【0010】
本発明は、上記課題に鑑みなされたものであって、同じデータに頻繁にアクセスされるような場合であっても、キャッシュメモリの高速性をできるだけ損なわずに、キャッシュへのヒット率を可変制御できる、より好適なキャッシュ装置および演算装置を提供することを目的とする。
【課題を解決するための手段】
【0011】
本発明は、プロセッサと主メモリとの間に接続されるキャッシュ装置であって、前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持領域に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の容量値を保持する容量保持部とが対応付けて複数備える、前記主メモリより読み書きのアクセスが高速なメモリと、前記タグ部に保持される各アドレスと、プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持部へ内容読み出しを指示する比較演算器と、前記容量保持部への各容量値を決定し、前記容量保持部へそれぞれ決定された各容量値を設定する容量値決定手段とを備えた。
【0012】
また、本発明は、プロセッサと主メモリとの間に接続されるキャッシュ装置であって、前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持部に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の各先頭アドレスを保持する先頭アドレス保持部とが対応付けて複数備える、前記主メモリより読み書きのアクセスが高速なメモリと、前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持領域へ内容読み出しを指示する比較演算器と、前記先頭アドレス保持部への各アドレス値を決定し、前記先頭アドレス部へそれぞれ決定された各先頭アドレスを設定する先頭アドレス決定手段とを備えた。
【0013】
また、本発明は、主メモリとバスを介して接続される演算装置であって、プロセッサと、前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持領域に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の容量値を保持する容量保持部とが対応付けて複数備える、前記主メモリより高速なキャッシュメモリと、前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持部へ内容読み出しを指示する比較演算器と、前記容量保持部への各容量値を決定し、前記容量保持部へそれぞれ決定された各容量値を設定する容量値決定手段とを備えたキャッシュコントローラとを具備した。
【0014】
また、本発明は、主メモリとバスを介して接続される演算装置であって、プロセッサと、前記主メモリの一部の連続する内容を一時的に保持する内容保持部と、前記内容保持部に保持される内容の主メモリ上のアドレスを保持するタグ部と、前記内容保持領域の各先頭アドレスを保持する先頭アドレス保持部とが対応付けて複数備える、前記主メモリより高速なキャッシュメモリと、前記タグ部に保持される各アドレスと、前記プロセッサから主メモリへ読み出し要求の際のアドレスとの少なくとも一部をそれぞれ比較し、その比較結果が一致した前記タグ部に対応する前記内容保持領域へ内容読み出しを指示する比較演算器と、前記先頭アドレス保持部への各アドレス値を決定し、前記先頭アドレス部へそれぞれ決定された各先頭アドレスを設定する先頭アドレス決定手段とを備えたキャッシュコントローラとを具備した。
【発明の効果】
【0015】
本発明によれば、いろいろなデータへ少ない回数だけ繰り返しアクセスされるような場合でも、また、同じデータに頻繁にアクセスされるような場合でも、キャッシュへのヒット率を可変するよう制御できるようになった。
【発明を実施するための最良の形態】
【0016】
以下に、本発明の実施の形態を、図面を用いて詳細に説明する。
【0017】
一般にキャッシュ機構は、キャッシュ機構が管理する高速なメモリ(これをキャッシュメモリと呼ぶ)に収められているデータのアドレスの管理方法により、ダイレクトマップ方式、アソシエイティブ方式、nウェイアソシエイティブ方式の3つに大別される。キャッシュメモリの管理方式として若干の違いがあるが、基本的にはアドレスバス上のアドレスデータとキャッシュ機構が管理しているタグ部が一致するかどうかの判定を行うということは、すべての方式に共通している。以後の説明は、基本的にはすべての方式に共通している。
【0018】
図1は、本実施の形態に係るシステム全体を示す機能ブロック図である。
【0019】
プロセッサ1は、プログラムを実行するための演算処理を行うものである。主メモリ2は、プロセッサ1で実行されるプログラムや、プログラム実行時に利用するデータ(これらを総称して、以下単にデータと呼ぶ)などを格納するために半導体素子で構成される比較的低速で大容量なメモリであり、例えば、DRAMなどで実現される。キャッシュメモリ3は、主メモリ2に記憶される内容の一部を一時的に保持するために揮発性の半導体素子で構成され、主メモリ2と比較して高速で小容量なメモリであり、例えば、SRAMなどで実現される。
【0020】
キャッシュコントローラ4は、プロセッサ1、主メモリ2、キャッシュメモリ3とそれぞれバス5を介して接続されている。キャッシュコントローラ4は、キャッシュメモリ3を制御するものであり、主に、プロセッサ1から主メモリ2へアクセスされるときにキャッシュメモリ3に保持していないかを判断し、保持していれば(ヒットと呼ぶ)キャッシュメモリ3から読み出してプロセッサ1へ送り、保持していなければ(ミスヒットと呼ぶ)主メモリ2から読み出されたデータをキャッシュメモリ3へ格納する処理を行うものである。
【0021】
このキャッシュコントローラ4の処理の概略を、図2を用いて、簡単に説明する。(a)はミスヒットの場合の処理を示し、(b)はヒットの場合の処理を示す。
【0022】
まず、(a)について説明する。プロセッサ1から主メモリ2へ、主メモリ2上のあるアドレスを指定しデータの読出し要求を行う(S11)。キャッシュコントローラ4は、その読出し要求の指定先のアドレスに対応するデータが、キャッシュメモリ3にも一時保持しているか否かを判断する(S12)。キャッシュコントローラ4は、一時保持していない、つまりミスヒットであると判断すると、その読出し要求を主メモリ2へ転送する(S13)。主メモリ2は、転送された読出し要求を受信し、指定先のアドレスが示す記憶領域からデータを読出し、その読出されたデータを、プロセッサ1へ向けて送信する(S14)。キャッシュコントローラ4は、この送信されたデータを受け取って、プロセッサ1へ転送する(S15)。また、キャッシュコントローラ4は、データとこのデータに対応する主メモリ2上のアドレスをキャッシュメモリ3へ一時保持させる(S16)。以上のような処理により、キャッシュメモリ3に新たなデータが一時保持される。
【0023】
次に、(b)について説明する。プロセッサ1から主メモリ2へ、主メモリ2上のあるアドレスを指定しデータの読出し要求を行う(S21)。キャッシュコントローラ4は、その読出し要求の指定先のアドレスに対応するデータが、キャッシュメモリ3にも一時保持しているか否かを判断する(S22)。キャッシュコントローラ4は、一時保持している、つまりヒットであると判断すると、その読出し要求されたアドレスに対応するデータを一時保持しているキャッシュメモリ3の領域へ読出し要求を行う(S23)。
【0024】
キャッシュメモリ3は、キャッシュコントローラ4からの読出し要求により、その領域からデータを読出し、読み出されたデータをキャッシュコントローラ4へ送信する(S24)。キャッシュコントローラ4は、この送信されたデータをプロセッサ1へ転送する(S25)。以上のような処理により、キャッシュメモリ3からデータが読み出される。
【0025】
なお、プロセッサ1、キャッシュメモリ3、キャッシュコントローラ4は、図1の点線に示すように演算装置として、同一パッケージで提供しても良い。また、特に図示しないがキャッシュメモリ3とキャッシュコントローラ4とが同一パッケージで提供されても良い。
【0026】
次に、キャッシュメモリ3が記憶する内容の構成を図3に示す。
【0027】
キャッシュメモリ3は、タグ部11と容量部12とキャッシュブロック13とからなるキャッシュライン14を複数個備える。キャッシュブロック13には、主メモリ2から読み出されたデータのコピーを保持する。キャッシュブロック13は、予め定められた固定の記憶容量(例えば、256bit)が割り当てられている。タグ部11には、データが主メモリ2上に記憶されていた(先頭)アドレスを保持する。容量部12には、キャッシュブロック13の全容量の内の実際に利用する容量の値(例えば、128bit)を保持する。この容量部12の値は、演算の開始時に決定し、保持すればよいが、更に、前の容量より同じか小さな容量となる制約を課すことによって、キャッシュブロック13に保持されるデータの内容を変更せずに新たに容量を決定し、容量の変更を行うこともできる。
【0028】
例えば、キャッシュブロック13の予め定められた固定の記憶容量が256bitで最小に変更可能な容量が8bitの場合には、256bit、128bit、64bit、32bit、16bit、8bitの何れかから選ばれ、且つ、例えば、現在演算中で、容量が32bitの場合には、32bit、16bit、8bitの何れかから選ばれる。なお、ここで、容量の値が2のべき乗である理由は、後述する。
【0029】
上記制約は、キャッシュヒットを示した際には、必ずキャッシュブロック13に要求されたデータが存在することを保証するためである。
【0030】
繰り返しになるが、キャッシュブロック13は、割り当てにおいてはそれぞれ物理的に容量が固定されているが、実際の利用(主に、読み出し)においては、利用許可する容量を可変にすることができるようになっている。なお、キャッシュラインには、これら以外に例えば、キャッシュメモリ3の状態(読み出し可/禁止、等)を示す情報、等を保持できるようにしてもよい。
【0031】
次に、図4は、キャッシュコントローラ4の内、本実施の形態に係る機能についてのブロック図を示したものである。
【0032】
タグ部読み出し部21は、キャッシュメモリ3の各タグ部11から、各アドレスを読み出すものである。
【0033】
キャッシュ容量決定部22は、各キャッシュブロック13の容量をそれぞれ決定するためのものであり、ここでは、乱数回路または擬似乱数回路などを用いて、予め定めた数パターンの容量値から後述する制約の元、ランダムに選択し出力するよう構成する。
【0034】
キャッシュ容量読み出し部23は、キャッシュメモリ3の各容量部12から、各容量値を読み出すものである。
【0035】
比較演算部24は、プロセッサ1から主メモリ2へ読み出し要求を行ったときに送られるアドレスが、タグ部読み出し部21で読み出され各アドレスと、各アドレスに対応するキャッシュ容量読み出し部23で読み出された各容量値とに基づく、各キャッシュライン14のアドレスの範囲に含まれるか否かをそれぞれ比較するものである。比較演算部24は、この比較結果の何れも否であるときには、キャッシュメモリ3に格納されていないことを示す信号をラッチ回路25へ送信する。一方、比較演算部24は、ある比較結果が含まれることを示したとき(キャッシュヒット)には、そのキャッシュライン14のキャッシュブロック13に対し読み出し要求を行う。
【0036】
ラッチ回路25は、プロセッサ1からのアドレスを一時的にラッチするものであって、比較演算部24から前記信号を受けると、ラッチしているアドレスを主メモリ2と接続されるバス5へ出力する。
【0037】
次に、比較演算部24の内部回路構成の一例を、一つのキャッシュライン14との比較に着目した構成を比較器30として、図5に示し説明する。この一例の比較演算部24−1の場合、キャッシュブロック13の予め定められた固定の記憶容量、及び、キャッシュ容量決定部22が決定する容量は、何れも2のべき乗である必要がある。また、当然ながら、キャッシュ容量決定部22が決定する容量は、キャッシュブロック13の予め定められた固定の記憶容量と同じかそれより小さい必要がある。そして、このような場合、キャッシュ容量決定部22が決定する容量を、本実施の形態で用いるアドレスの幅で二値表現で表した時、下位からある桁までは全て1で、ある桁の次の桁から上位は全て0となる。
【0038】
XOR素子31は、2つの入力が一致すると0を出力し、異なると1を出力する。このXOR素子31を、図のように並列に配置し、各XOR素子31の、一方の入力をアドレスバス5からのアドレス(二値)とし、他方の入力をタグ部12から読み出された各アドレス(二値)とし、互いのアドレスの同じ桁同士が比較されるようにする。XOR素子31の比較結果が一致すれば0が出力され不一致であれば1が出力されるから、本来はアドレスの一致/不一致はこれだけで把握できる。
【0039】
しかしながら、プロセッサ1からのアドレスは、各キャッシュライン14のアドレスの範囲の途中のアドレスであることが多く、このような場合もキャッシュヒットと判断する構成である必要がある。既存のキャッシュ機構の場合には、キャッシュブロックのサイズが固定であったので、キャッシュブロック毎に変わるアドレス中の上位アドレスの部分のみを比較することにより、一致/不一致を判断していた。一方、本実施の形態では、キャッシュブロック毎に容量を変更するようにしているから、比較する上位アドレスを固定にすることは出来ない。これを解決するために、この比較器30では、キャッシュブロックの容量に応じた下位アドレスの比較結果をマスクするようにしている。
【0040】
図5において、AND素子32は、2つの入力がともに1の時のみ1を出力し、2つの入力のうち少なくとも一つが0の時、0を出力する。このAND素子32を図のように並列に配置し、各AND素子32の、一方の入力をXOR素子31の出力とし、他方の入力を容量部から読み出された容量を示す二値データを反転した値とする。従って、アドレスの下位から容量までに対応するAND素子32は、何れも0を出力し、それ以上に対応するAND素子32は、XOR素子31の出力そのものを出力する。
【0041】
NOR素子33は、各AND素子の出力を入力する。NOR素子33は、全ての入力が0のときのみ、1を出力するから、出力が0ならばミスヒットであり、1であればヒットしたということがわかる。
【0042】
以上のような比較器30でひとつのキャッシュラインがヒットするかミスヒットするかがわかり、これらを並列的に用いることにより、キャッシュメモリの何れかにヒットしたかミスヒットしたかもわかる。その結果、キャッシュブロックの容量を変更する場合のアドレスと各タグ部11が保持するアドレスが一致しているかどうかの判定を行う比較演算部24を実現することができる。
【0043】
次に、比較演算部24の別の一例を示す。この例におけるキャッシュメモリ3が記憶する内容を図6に示すが、これを図3と比較すると、容量幅部43を備えている点が新しく、その他のタグ部41、容量部42、及びキャッシュブロック44は、図3のタグ部11、容量部12、キャッシュブロック部13と同じである。
【0044】
それぞれの容量幅部43は、アドレスバス5のバス幅分のビットを備え、各キャッシュライン45の各容量の値に基づき、アドレスバス5と容量部43のマスクデータが格納される。具体的に格納されるマスクデータは、下位からnビット(ここでnは、n≧1かつ2(n−1)≦キャッシュブロックの容量<2を満たす)だけ1とし、残りのビットを0として保持している。例えば、キャッシュ容量が15byteなら下位から4ビットが“1”となり、17byteなら下位から5ビットが“1”となっている。なお、ここでも類推されるように、本例は、容量の値が2のべき乗で無くても構わない。
【0045】
次に、図7に、本例の比較演算部24−2の回路図を示す。
【0046】
この例は、図上の点線より上部、即ち、XOR素子31、AND素子32、NOR素子33で構成される部分は、NOR素子33の入力として後述する比較器53からの出力を入力している点を除き、図5と同じであり説明を省略する。
【0047】
AND素子51は、図のように並列に配置し、一方の入力にアドレスバス5からのアドレス(二値)が、他方には容量幅部43の各ビットが接続される。つまり、この並列化されたAND素子51では、アドレスの下位から容量幅部43で保持しているビット幅分だけ、アドレスを有効として出力する。この出力は、比較器53の一方に入力される。
【0048】
AND素子52は、図のように並列に配置し、一方の入力に容量部42が、他方には容量幅部43の各ビットが接続される。つまり、この並列化されたAND素子51でも、容量部42の下位から容量幅部43で保持しているビット幅分だけ、容量値を有効として出力する。この出力は、比較器53の他方に入力される。
【0049】
比較器53には、上記説明から分かるように、容量幅部43で保持しているビット幅分だけ、アドレスバス5からのアドレス(二値)と容量部42からの容量値とが入力され、両者の大小が比較される。この比較の結果、アドレスのほうが大きければ、“1”を出力し、アドレスのほうが小さければ、“0”を出力する。このようにして、比較器53の出力は、NOR素子33に入力される。
【0050】
以上のことから、第1の比較演算部24−1の例では、下位アドレスの比較結果をマスクするようにしていたが、本例の比較演算部24−2の例では、下位アドレスをも比較対象としており、この結果、比較演算部24−1では、2のべき乗でしか、容量値の指定が行えなかったが、本例の比較演算部24−2では、2のべき乗に限ることなく、キャッシュブロックを超えない何れの容量値でも、指定できるようになった。つまり、このような本例によれば、各タグ部にキャッシュブロックの実利用容量を管理するための領域を追加するようにしたから、タグ部が管理するキャッシュブロックの実利用容量を可変とできるようになった。
【0051】
次に、上記で説明した本発明の実施の形態では、キャッシュメモリ3を予め定められた固定の記憶容量とした複数のキャッシュブロックに割り当て、その後各キャッシュブロック内の容量を可変にするものであった。
【0052】
これに対し変形例として、固定の記憶容量とした複数のキャッシュブロックに割り当てるのではなく、演算開始前にキャッシュメモリ3をそれぞれ異なった記憶容量で各キャッシュブロックとするようにしても良い。
【0053】
この場合、図3に対比し、図8に示す一例のように、キャッシュブロック63の容量を決定し、タグ部61とキャッシュアドレス部62とそのキャッシュブロック63との対応関係を保つようにすれば良い。
【0054】
キャッシュアドレス部62には、対応するキャッシュブロック63のキャッシュメモリ3上の先頭アドレスを備える。このキャッシュアドレス部62への先頭アドレスの登録は、キャッシュメモリ3を利用する前に、各タグ部11に対応付ける各キャッシュブロック63の容量を、乱数回路などを用いて決定し、各タグ部の順に容量を積み上げるよう(追記的)にして、各キャッシュブロック63の先頭アドレスを決定する。
【0055】
具体的には、n−1番目までのタグ部61にあるキャッシュブロック63の容量値を加算すると、n−1番目までに割り当てたキャッシュメモリ3の容量となる。n番目のタグ部61が管理するキャッシュブロック63は、n−1番目が使っているキャッシュブロック63の次のアドレスから利用する。言い換えれば、0番目からn−1番目までのタグ部61のキャッシュブロック63の容量を加算した値は、n番目のタグ部61のキャッシュメモリ3の先頭を表すアドレスのオフセットとして利用することができる。これにより、上記実施形態と比較し、例えば2つの先頭アドレスからキャッシュブロック容量を求める演算部(図示しない)が必要になるなどのより複雑な制御が必要になるが、一方では、タグ部11の管理するキャッシュブロック63の先頭アドレスを自由に変えることができるから、あるキャッシュブロックを既存に比べて大きな容量で取ることや、決定する容量も比較的自由に選定できる等、キャッシュメモリ3を有効に利用することができるようになる。
【0056】
以上説明してきた、本実施の形態のキャッシュ機構(キャッシュメモリ3とキャッシュコントローラ4)は、例えば、暗号演算時に適用することにより、暗号演算処理時の耐解析性を向上させる効果が生じる。そこで、以下には本実施の形態を暗号演算へ適用した場合について説明する。
【0057】
キャッシュ機構を備えた演算処理装置の暗号演算時において、主メモリ3とキャッシュメモリ
との読み出し時間差による処理時間の差を利用し、入力データ(平文)と処理時間との関係から、
暗号演算時の秘密情報を導出する解析手法がある。この、解析手法をキャッシュ攻撃といい、この解析手法について簡単に説明をする。
【0058】
例えば、キャッシュ機構を備えた演算装置で、よく知られるS−BOX等の換算用テーブルをn個用い、入力する平文を換算用テーブルの入力幅でPi 個に分割した各分割データを、部分鍵KiでXOR演算(下記式では“△”で代用する)する動作が繰り返し(m回)行われる暗号アルゴリズム(例えば、DESやAES等)の場合、S−BOX等の換算用テーブルの入力として、PiとKiとのXOR演算の結果を用いる。1回の暗号演算の中で、n個ある換算用テーブルの一つの換算テーブルに着目し、その換算テーブルの任意の2つの入力について以下のどちらかが成り立つ。
【0059】
Pi △ Ki= Pj △ Kj ・・・(A)
Pi △ Ki≠ Pj △ Kj ・・・(B)
(i≠j,0≦i,j<m)
上記(A)の時には、必要な換算用テーブルが前回で(前ステップで)利用したものと同じであり、そのため主メモリから読み出されておりキャッシュメモリに保持されているため、キャッシュヒットし、(B)の時には、必要な換算用テーブルが前回で(前ステップで)利用したものと異なり、そのため主メモリから読み出されておりキャッシュメモリに保持されていないためキャッシュミスすることになる。つまり、途中結果が(A)と(B)の時では、換算用テーブルを参照するためにアクセスする先がキャッシュメモリと主メモリとで異なるため、処理時間が大きく異なり、その結果、全体の処理時間を測定することにより、m回の換算用テーブルへの入力値が同じか異なるかを判別することが出来る。
【0060】
このような暗号アルゴリズムの元、入力する平文を工夫して選定する。この場合には、入力平文をランダムに生成した平文と比べて、実際にアクセスした換算用テーブルの内の要素数が少ない平文を作成し、そこから鍵差分を決定する。このようにすると、同じ換算用テーブルをアクセスすることが多いため、上記(A)を利用してPi △ Pjを計算し、最も出現回数が多かったもの、つまり暗号演算時間が短かったものを正しい鍵差分とする。
【0061】
逆に、実際にアクセスした換算用テーブルの数が多い平文多数から鍵差分を決定することもできる。この場合には、異なる換算用テーブルをアクセスすることが多いため、上記(B)を利用してPi △ Pjを計算し、最も出現回数が少なかったもの、つまり暗号演算時間が長かったものを正しい鍵差分とする。
【0062】
以上のような方法を用いて鍵差分を生成し、そこから鍵情報を導出することができる。
【0063】
上記で説明したキャッシュ攻撃の解析手法に対し、本実施の形態のキャッシュ機構を用いることに、対策を講じることができる。これについて説明する。
【0064】
前記キャッシュ攻撃では、暗号演算時の処理時間が入力したデータと暗号演算時に使う秘密情報にのみ依存している場合に攻撃が成功する。従って、処理時間を変動することができるならば、攻撃を防ぐ対策となり得る。
【0065】
処理時間の変動させるための一方法として、キャッシュのヒット率を変えることにより、キャッシュメモリ3へのアクセス回数と低速なメモリへのアクセス回数が変わり、その結果、暗号演算処理の処理時間が変更できる。
【0066】
そこで、上記した本実施の形態のキャッシュコントローラを適用することにより、キャッシュメモリ3の容量の変更に応じてキャッシュのヒット率を変更させる。
【0067】
この結果、攻撃者が想定している仮定である入力データと秘密情報によってのみ、処理時間が変動するという前提条件を崩す事ができ、キャッシュ攻撃に対する対策となる。
【0068】
また、さらに、演算装置の暗号演算中の消費電力を測定し、秘密情報を導出するという差分消費電力解析(Differential Power Analysis)という攻撃方法も存在するが、この攻撃方法も処理時間を変動させることが攻撃に対する対策として有効であることが知られている。
【0069】
そこで、演算処理装置に上記した本実施の形態のキャッシュコントローラを適用することにより、キャッシュブロックの容量の変更に応じてキャッシュのヒット率を変更させることで、処理時間も変動するから、DPAに対する対策としても有効である。
【0070】
以上詳細に説明してきたように、本実施の形態によれば、いろいろなデータへ少ない回数だけ繰り返しアクセスされるような場合でも、また、同じデータに頻繁にアクセスされるような場合でも、キャッシュへのヒット率を可変するよう制御できるようになる。
【0071】
また、前記何れの場合にも、キャッシュのヒット率を可変するよう制御できるから、暗号演算処理において、キャッシュ攻撃や、DPAに対する有効な対策ともなり得る。
【図面の簡単な説明】
【0072】
【図1】本実施の形態に係るシステム全体を示す機能ブロック図。
【図2】キャッシュコントローラ4の処理の概略を示した図。
【図3】キャッシュメモリ3が記憶する内容の構成を示した図。
【図4】キャッシュコントローラ4の内、本実施の形態に係る機能について示したブロック図。
【図5】比較演算部24の内部回路構成の一例。
【図6】キャッシュメモリ3が記憶する内容の別例。
【図7】比較演算部24−2の内部回路構成を示す図。
【図8】キャッシュメモリ3が記憶する内容の構成の別例を示した図。
【符号の説明】
【0073】
1・・・プロセッサ
2・・・主メモリ2
3・・・キャッシュメモリ
4・・・キャッシュコントローラ
5・・・バス
11、41、61・・・タグ部
12、42・・・容量部
13、44、62・・・キャッシュブロック
14、45・・・キャッシュライン
21・・・タグ部読み出し部
22・・・キャッシュ容量決定部
23・・・キャッシュ容量読み出し部
24、24−1、24−2・・・比較演算部
25・・・ラッチ回路
31・・・XOR素子
32、51、52・・・AND素子
33・・・NOR素子
43・・・容量幅部
53・・・比較器
63・・・先頭アドレス部




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013