CPU性能を向上させる高効率キャッシュアルゴリズム

プロセッサの性能向上のためには、プログラムによる外部メモリへのアクセス要求を、どれだけ内部のキャッシュ・メモリとのデータ授受で完結できるかが重要となる。近年ではキャッシュ・メモリ容量は増大し、一部のプログラムでは殆どのワーキングセットをオンチップに収納できるようになった一方で、依然として解消しにくい種類のキャッシュ・ミスが実行性能低下を引き起こしている。
長期にわたり、局所性に基づいた最初期のアルゴリズムが主流となってきたキャッシュ・マネジメント・アルゴリズムだが、Last Level Cacheと呼ばれる、チップ面積の数分の一を占めるような大容量キャッシュの容量を活用するためには、より長期のプログラム挙動を考慮した方が性能が向上することが判明してきている。このため、プリフェッチ、置き換えなど様々なキャッシュ・マネジメント手法において2010年代に入ってから新しいアルゴリズムが次々に登場している。
しかし、キャッシュ・マネジメント・アルゴリズムは、実行するプログラムの傾向や他のキャッシュ最適化技術の有無によって、その効果が大きく異なり、場合によってはかえって性能を損ねる副作用を生じることが知られており、新しく登場し、複雑化したアルゴリズムでは、その差はさらに著しくなっている。
そこで本研究では、LLCを有効に利用して計算機性能を上げることを目標とし、プログラムの傾向をプロセッサが実行中に推測して、最も適したマネジメントの組み合わせを自動的に選択する手法を研究している。
現在は超長期再参照をターゲットとして我々が提案しているStubborn戦略について、固定するキャッシュラインの決定アルゴリズムに関する検討を行った。また、適応的なキャッシュ制御を可能とするための汎用技術として、メモリアクセス傾向を利用した新しいフェーズ検出手法を提案している。

CCCache_001

CCCache_002

CCCache_004

  • 力翠湖, 眞島一貴, 藤原大輔, 吉見真聡, 吉永努, 入江英嗣: 「プリフェッチ情報から再参照予測を行うキャッシュライン置き換えアルゴリズム 」,情報処理学会研究報告,Vol. 2013-ARC-206, No. 20, Aug. 2013.
  • Hidetsugu Irie, Takefumi MIYOSHI, Goki HONJO, Kei HIRAKI Tsugomu YOSHINAGA: “Using Cacheline Reuse Characteristics for Prefetcher Throttling”, IEICE Trans. on Information and Systems, Vol.E95-D, No. 12, pp.2928-2938, Dec. 2012.
  • 入江 英嗣, 本城 剛毅, 平木 敬: 「動的推定によるプリフェッチ量最適化」, 情報処理学会論文誌コンピューティングシステム, Vol. 3, No. 3, pp.56-66, Sep. 2010. (2010年度情報処理学会論文賞)