表題番号：2011A-045 日付：2012/02/29
研究課題世界最速を達成する階層キャッシュ構成シミュレータの研究開発
研究者所属（当時） 資格 氏名
（代表者） 理工学術院 教授 戸川　望
（連携研究者） 基幹理工学研究科 修士2年 多和田　雅師
研究成果概要
1. 研究背景
　現在，我々の身の回りにあるデジタルテレビ，ハードディスクレコーダ，携帯電話，自動車，エアコン，炊飯器などあらゆる電化製品に，ほぼ必ず大小の「組込みプロセッサ」が組み込まれている．我々の豊かで安全・安心な生活に組込みプロセッサの性能・価格は密接に関わってきている．
　高性能化された組込みプロセッサは，内部に「オンチップメモリ」と称されるメモリを搭載している．オンチップメモリとは，組込みプロセッサの性能と，DRAMなどの外部メモリの性能とのギャップを補償するために，プロセッサと外部メモリの間を仲介するメモリシステムであるが，オンチップメモリサイズの増大ならびに半導体の微細化によるリーク電流の増大を主な原因として，オンチップメモリの面積は，組込みプロセッサの全面積のうち最大で60%～80%にも達し，同様にその消費電力は最大で50%～70%にも達する．極端に言えば，組込みプロセッサの価格・性能を決定づけるのは，もはやオンチップメモリであり，その振舞いを知ることが組込みプロセッサの価格・性能の決定に大きく寄与することになる．
　オンチップメモリは，一般に(1) L1（レベル1）キャッシュ，(2) L2 （レベル2）キャッシュならびに(3) スクラッチパッドメモリによって構成される．本研究では，これら構成要素(1)～(3)に対して，特定のプログラム－例えば，デジタルテレビであれば，デジタル放送のデコード処理－が組込みプロセッサ上で実行されると仮定し，オンチップメモリの構成要素(1)～(3)の総計7個のパラメータを，それぞれその最小値から最大値まで変化させたとき，オンチップメモリ内でデータのヒットとミスが何回起こるかを，極めて高速にかつ正確にシミュレーションすることで，これを結果をベースとした【最適なオンチップメモリ構成】を得ることを目的とする．世界で最速とされるオンチップメモリシミュレータに比較して1000倍以上の高速化を達成することを目標とした．

2. 研究成果概要
　以下に示すように第1段階(L1キャッシュ/L2キャッシュ)と第2段階(L1キャッシュ/L2キャッシュ/スクラッチパッドメモリ)に分けて，研究を実施した．

【第1段階】 (L1キャッシュ/L2キャッシュの超高速シミュレーションによる最適化)
オンチップメモリの構成要素のうち，まずL1キャッシュ/L2キャッシュのシミュレーションを取り上げ，6個のパラメータを変化させたときのヒット数とミス数を正確に算出することで，メモリアクセス時間最小化あるいは消費エネルギー最小化を達成する最適パラメータを探索する．
　申請者は，L1キャッシュのシミュレーションにおいて，キャッシュメモリが持つ普遍的な数理的性質を世界で初めて見出している．これらの性質をL1キャッシュとL2キャッシュの双方に適用することで，超高速なシミュレーションベースのメモリアクセス時間最小化あるいは消費エネルギー最小化が実現することを考えた．
以上の考察のもと次の性質を見出し，さらにこれに基づくオンチップメモリの高速最適化技術を考案した．

【性質1】L1 キャッシュ構成の連想度が1 となる2階層L1キャッシュ/L2キャッシュ構成は，同じ構成をもつ1階層L1キャッシュのキャッシュミス数と同一となる．

　この性質をもとに，2階層L1キャッシュ/L2キャッシュ構成のキャッシュヒット数，ミス数を正確にシミュレーションする高速化手法CRCB-T手法を考案した．考案した手法を計算機上で評価した結果，従来の技術に比較して【1465倍】の高速化が達成できていることを確認した．

【第2段階】 (L1キャッシュ/L2キャッシュ/スクラッチパッドメモリの超高速シミュレーションによる最適化)
　組込みプロセッサのオンチップメモリは，L1キャッシュ-L2キャッシュ-スクラッチパッドメモリという構造を持つ．【第2段階】では，L1/L2キャッシュメモリだけでなく，スクラッチパッドメモリを含めたオンチップメモリ全体の高速シミュレーションによる7個のパラメータ全部の最適化を課題とする．【第1段階】の研究成果をスクラッチパッドメモリに拡張すると同時に，スクラッチパッド単独の数理的性質を見出すことで，最終的に従来最速されているシミュレーションベースのオンチップメモリ最適化手法に比較して，100倍～1000倍の高速化を実現する．
　スクラッチパッドを組み込んだL1キャッシュ-L2キャッシュ-スクラッチパッドメモリ構成において上述の性質1につづき，以下の性質を見出した．これは単純かつ明解なものであるが，不変の原理としてすべてのオンチップメモリに適用し得る極めて重要な性質である．

【性質2】より小さい容量のスクラッチパッドメモリに収容されるデータは，必ずより大きい容量のスクラッチパッドメモリに含まれる．

　この性質をもとに，L1キャッシュ-L2キャッシュ-スクラッチパッドメモリ構成のキャッシュヒット数，ミス数を正確にシミュレーションする高速化手法CRCB-S手法を考案した．考案した手法を計算機上で評価した結果，従来の技術に比較して約【3173倍】の高速化が達成できていることを確認した．
　これらの研究成果として，従来，世界最高速のシミュレーションベースのオンチップメモリ最適化に数ヶ月を要した実行時間を，提案する技術により数時間以内に完了させることになる．本研究は世界際高速のキャッシュ構成シミュレーションが達成されたことを意味する．