FPGA開発日記

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

Top-Down Microarchitecture Analysisとは何か(4. Memory Bound はどのように分類されるのか)

前回の続き。

msyksphinz.hatenablog.com

前回は Top-Down Analysis の4分類、

  • Retiring
  • Bad Speculation
  • Frontend Bound
  • Backend Bound

について整理した。次は Backend Bound の中でも特に重要な「Memory Bound」について論文の Section 3.7 を中心に読み解いていく。

Top-Down Analysis における Memory Bound の考え方は非常に重要である。なぜならこの論文は、cache miss が起きたかではなくその cache miss が本当に CPU を止めたかを基準にしているためである。

ここに従来の PMU ベース解析との本質的な違いがある。

なぜ単純な cache miss カウントでは駄目なのか

従来の性能解析では「L2 miss が多い → memory bottleneck」のような解析が行われていた。しかし Out-of-Order CPU ではこのような分析は成立しない。理由は単純である。

  • cache miss が起きても CPU は止まらない

からである。Out-of-Order CPU は miss が発生している間も、独立な命令を実行できる。つまり重要なのは「miss があったか」ではなく「execution unit が idle になったか」である。


Top-Down Analysis における Memory Bound

Top-Down Analysis では Backend Bound をさらに「Core Bound」「Memory Bound」に分解する。ここで Memory Bound は「memory subsystem が原因でexecution resource が idle になった時間」として定義される。

論文ではこれをExecutionStallsという考え方で説明している。つまり「uop が実行できなかった cycle」を見る。ここが非常に重要である。


Execution Stall という考え方

論文では execution stall を十分な uop が execute されなかった cycleとして定義している。例えば 4-wide issue CPU なら、0 / 1 / 2 uops しか execute されなかった cycle はsub-optimalとみなされる。つまり CPU が持つ execution bandwidth を使い切れていない。


本当に重要なのは「実行器が止まった時間」

ここで論文の最も重要なポイントが出てくる。

例えば L3 miss が発生していても、「別の independent instruction」を execute できているなら、「その miss はまだ性能を止めていない」のである。逆に、execution unit が空になったなら、その時点で初めて memory stall が性能ボトルネックになる。つまり Top-Down Analysis はmemory access latencyではなくvisible execution stallを見ている。


Memory Bound の分解

Top-Down Analysis では Memory Bound をさらに「L1 Bound」「L2 Bound」「L3 Bound」「Ext. Memory Bound」へと分解する。

論文中のフローチャートを簡略化すると次のようになる。

Execution Stall がある
    ├─ L1 miss がない
    │      → L1 Bound
    ├─ L1 miss はある
    │    L2 miss はない
    │      → L2 Bound
    ├─ L2 miss はある
    │    L3 miss はない
    │      → L3 Bound
    └─ L3 miss がある
           → DRAM Bound

ここで重要なのは、どこで miss したかではなくexecution stall 中にどのレベルまで到達していたかで分類している点である。


L1 Bound の意味

L1 Bound は非常に興味深いカテゴリである。通常、L1 hit = 高速と考えられる。しかし論文では、L1 hit でも stall しうることを強調している。

例として挙げられているのが「store-to-load forwarding failure」「4K aliasing」である。つまりデータは L1 に存在していても、依存関係やforwarding failureによって execution が止まる場合がある。このような stall は従来のcache miss countingでは見えない。

ここが Top-Down Analysis の非常に重要な点である。


L2 / L3 Bound

L2 Bound や L3 Bound は比較的素直である。execution stall 中にどの cache level まで miss したかで分類される。例えばL1 miss はある / L2 miss はない ならL2 Boundとなる。


Ext. Memory Bound

L3 miss が発生すると、DRAM accessが必要になる。Top-Down Analysis ではこれを Ext. Memory Boundとして扱う。ここまでは比較的単純である。しかし論文ではさらにこれを「Memory Latency Bound」「Memory Bandwidth Bound」へ分解する。

Latency Bound と Bandwidth Boundの分類は非常に重要な区別である。

Memory Latency Bound

これは単発アクセスの待ち時間が支配的な状態である。典型的には「pointer chasing」「linked list traversal」などである。この場合、memory outstanding request 数は少ない。

Memory Bandwidth Bound

こちらは大量アクセスによって帯域が飽和している状態である。典型例は「streaming workload」「dense matrix access」などである。論文ではmemory controller outstanding queue occupancyを観測して、一定以上埋まっている場合を bandwidth bound と判定している。

なぜこの分類が重要なのかというと、Latency Bound と Bandwidth Bound は改善方法が全く異なるためである。

Latency Bound の改善

Latency Bound の場合はlatency hidingが重要になる。例えば software prefetch / hardware prefetch / memory-level parallelism などである。

Bandwidth Bound の改善

一方で Bandwidth Bound の場合、prefetchはむしろ悪化要因になりうる。重要なのはtraffic reductionである。例えば blocking / tiling / cache reuse / compression などが重要になる。


Top-Down Analysis の本質

Top-Down Analysis はイベントを分類する手法ではない。CPU execution resource がなぜ idle になったかを分類する手法である。

つまり観測対象はcache missではなくexecution stallである。


実際の計算式

論文では Memory Bound 系 metrics は次のように定義されている。

Memory Bound = MemStalls.AnyLoad + MemStalls.Stores
L1 Bound = MemStalls.AnyLoad - MemStalls.L1miss
L2 Bound = MemStalls.L1miss - MemStalls.L2miss
L3 Bound = MemStalls.L2miss - MemStalls.L3miss
Ext. Memory Bound = MemStalls.L3miss

重要なのはこれらすべてがstall cycleベースである点である。単なる miss count ではない。