長期再参照のためのキャッシュライン追い出し不可属性の提案

摘要

プロセッサアーキテクチャにおいて，メモリサブシステム，キャッシュシステムの性能は依然として主要な課題の一つである．近年では半導体微細化に伴いキャッシュメモリ，特にラストレベルキャッシュ (Last Level Cache, LLC) の大容量化が進み，これを上手く利用するためにプリフェッチに協調するスマートなキャッシュ置き換えアルゴリズムが提案されている．しかしながら，これらの賢いキャッシュアルゴリズムをもってしても救えていないキャッシュミスが存在する．本研究の調査で，それは一度アクセスされたあるアドレスに対応するラインがキャッシュに載った後，実行命令数が1M命令以上経過した後に再度アクセスされた場合に生じるキャッシュミスであることが明らかになった．本研究ではこれを長期再参照ミスと命名した．これらの調査から，特にLLCでのキャッシュミスのボリュームゾーンは長期再参照ミスであることがわかった．この調査を踏まえて，本研究では，ある基準によって定めたキャッシュラインを長期間追い出さないことを特長としたキャッシュアルゴリズムの基本戦略を提案する．実行履歴に基づき置き換えを起こすアルゴリズムによって救えないキャッシュミスであるならば，いっそヒストリに頼った直近の再参照に期待するのはやめて，置き換えを起こさない手法として試行した．我々はこれにStubborn戦略と名付けた．“Stubborn”は“頑固”を意味する． Stubborn戦略は，キャッシュ中に追い出しを起こさない領域をつくることで実現させている．本提案手法を，LRUをベースに実装し，シミュレーションによる評価を行った．このようなシンプルな戦略にも関わらず，結果として最大で23.9%のIPC向上，幾何平均でも2MB構成，Prefetch awareなLRUベースでのランダム採択を行うStubbornキャッシュで最大の2.40%向上が得られた．