FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

ISCA 2021の"Zero Inclusion Victim: Isolating Core Caches from Inclusive Last-level Cache Evictions"を読む

何となくマイクロアーキテクチャの論文を読みたくなったのでISCAの論文から選んで読んでみている。メモがてらブログにサマライズを書いていく。

ieeexplore.ieee.org

概要

  • Inclusive Cacheとは何か？上位のキャッシュ (LLCに対してL2キャッシュやL1キャッシュなど)がキャッシュラインを保持しているとき、下位のキャッシュ(LLC)もそのデータを一緒に持っているというキャッシュ構造。以下の点で有利。
  • Inclusive Cacheの弱点：Inclusion Victim
    • ブロックのコピーがInclusive LLCから置換される時、キャッシュの上位階層も強制的に置換しなければならないという制約。
    • Live Inclusion VictimはLLCの交換ポリシーに依存し、深刻な性能低下をもたらす可能性がある(???)
    • 複数のコアで共有している場合に、LLCのブロックをVictimすることにより、タイミングサイドチャネル攻撃をしかけて情報を漏らすことができる。
    • 上記の2つの欠点の影響を低減するために、内部のキャッシュ、特にL3のInclusiveキャッシュ階層におけるでは、Inclusion Victimが存在しなくなるという有益性を得るために中間層のキャッシュを大きくすることが有益であるとしても、中間層のキャッシュを小さく保つ必要があるということである。

Inclusion Victimは、Inclusion LLCの内容を管理する方法によって発生していることを観察した。Inclusion LLCの利点を保持しつつ、さらに改善するためのZero Inclusion Victims(ZIV) LLCを提案する。

コアキャッシュをのLLCのEvictionと分離することが出来るようになる。Inclusion Victimsが発生するのは、Set Indexから関数が指すセットからEvictするVictimを選択するという所に制約があることが分かっている。

ZIV LLCは、Inclusion型LLCのグローバルなVictimの選択方式を効率的かつ最小にすることで、この問題を解決する。

ZIV LLCは大規模な中間レベルキャッシュ(例えば、LLCの半分のサイズ)をサポートすることができ、複数のLLC置換ポリシに対して非Inclusive LLCに近い性能を出すことができることを示した。

1. Introduction

今日のチップマルチプロセッサは一般的に複数レベルのキャッシュ階層を持っており、L1,L2のプライベートキャッシュを通じて、最終的にLast Level Cacheで共有されている。LLCとプライベートキャッシュの内容の関係性として最も重要なものとしてInclusive特性というものがある。

  • J-L. Baer and W-H. Wang. On the Inclusion Properties for Multi-Level Cache Hierarchies. In ISCA, 1988.

Inclusiveであるとは、プライベートキャッシュの内容が常にLLCの内容のサブセットであるという特性になっている。Inclusive特性を維持するためにLLCに必要なコトは以下のとおりである。

  1. LLCのミスでメモリシステムから取り出されたブロックは、もともとリクエストを出されたコアのプライベートキャッシュと、LLCにも割り当てられていなければならない。

  2. LLCからブロックが追い出される時は、プライベートキャッシュのブロックも強制的に無効化する必要がある。このためのLLCとプライベートキャッシュを結ぶプロトコルメッセージのことを"Back Invalidation"と呼ぶ。この"Back Invalidation"によって追い出されたプライベートキャッシュのブロックのことを、"Inclusive Victim"と読んでいる。このInclusive VictimはLLCによりどのキャッシュブロックを追い出すかという選択アルゴリズムによって発生するものである。

    1. Iyer. On Modeling and Analyzing Cache Hierarchies using CASPER. In MASCOTS, 2003.
    1. Jaleel, et al. Achieving Non-Inclusive Cache Performance with Inclusive Caches: Temporal Locality Aware (TLA) Cache Management Policies. In MICRO, 2010.

InclusiveでないLLCの場合は、2番目の動作を実装していない。この場合はExclusive特性およびExclusiveなLLCと呼ばれ、1番目の機能も実装しないという選択をすることができる。この場合、ブロックが2つのコアによって共有されることになった場合か、プライベートキャッシュから追い出される時に、そのブロックをLLCないで保持するかどうかは実装上選択することができる。本論文において実装したExclusive LLCは、比較のために第1の機能は実装しているが、第2の機能は実装していないという構成を取っている。

Inclusiveキャッシュが人気な理由は複数ある。

  • 帯域幅
  • キャッシュコヒーレンスプロトコルの簡素化：スヌーピングを実行する際に、LLCがすべてのブロックセットを保持していることでスヌープのフィルタリングの役割を果たし、すべてのプライベートキャッシュを調べる必要がなくなるためプロトコルが簡素化する。

リクエストがコヒーレンスディレクトリ及びLLCを検索する場合、

のみが発生する。つまり、

という状態は発生しない。実際、Exclusiveキャッシュを搭載したSkylake-Xプロセッサのリバースエンジニアリングされたディレクトリを調査すると、プライベートキャッシュには存在するがLLCに存在するブロックを検索さるために、別のコヒーレンスディレクトリを導入している。また、先行研究でも、Exclusive LLCに対して2つの独立したコヒーレンスディレクトリ構造を持つ同様のディレクトリ構造が提案されている。

    1. Yan, et al. Attack Directories, Not Caches: Side Channel Attacks in a Non-inclusive World. In Security & Privacy, 2019. [61]
    1. Zhao, et al. NCID: A Non-inclusive Cache, Inclusive Directory Architecture for Flexible and Efficient Cache Hierarchies. In CF, 2010. [64]

しかし、Inclusive LLCではInclusive Victimsの問題が発生し、重大な問題につながる。Inclusive Victimsにより犠牲となったブロックがプライベートキャッシュで活発に使用されている場合、プライベートキャッシュ側のブロックも消されてしまい性能低下を招く可能性がある。Inclusive LLCとプライベートキャッシュの容量については、図1に示した通りとなる。

  • 2つの異なるLLCの交換ポリシー (LRU, Hawkeye)
    • Hawkeyeとは、実行時にBalady's MINアルゴリズムの動作から学習して、LLCブロックを動的に分類して置換するポリシーである。
        1. Belady. A Study of Replacement Algorithms for a Virtual-storage Computer. In IBM Systems Journal, 5(2): 78–101, 1966[4].
        1. Mattson, etal. Evaluation Techniques for Storage Hierarchies. In IBM Systems Journal, 9(2): 78–117, 1970[34].
  • Inclusive / Non-Inclusive
  • キャッシュ構成
    • 8MB、16ウェイの共有LLC、
    • 32kB、8ウェイのコアL1D
    • 複数コア単位のL2キャッシュ

このグラフから得られる重要な結果は、

  • キャッシュ容量が同じ場合にInclusiveキャッシュよりもNon-Inclusiveキャッシュの方が性能が高い
    • これはLRUとHawkeyeの違いよりもはるかに大きい
    • Inclusive LLCでは、Hawkeyeの能力を十分に生かし切ることが出来ていない
  • L2キャッシュの容量を増価させると、Non-Inclusiveキャッシュの性能は増加するが、Inclusiveキャッシュの場合はInclusive Victimsの量が増加するため性能が逆に低下する

ということである。