L1 キャッシュ上のデータのロードレイテンシが L2 と同程度になる場合がある

とあるマイクロベンチマークを作っているとき、L1 キャッシュに関する不可解な現象に遭遇しました。

何が起きたか

L1 キャッシュのロードレイテンシを計測するベンチマークを作成し、仮想アドレスと物理アドレスのマッピングを変えて実行¹していたときのことです。 アドレスが一対一に対応している場合は 4 サイクルだったレイテンシが、複数の仮想アドレスを同じ物理アドレスにマッピングする²と 12 サイクルに増加するという計測結果が得られました。

しかし、両者の間に TLB ミス数や L1 キャッシュミス数の違いは見られず、レイテンシが増える理由が見当たりませんでした。

仮想アドレスと μtag

原因を調べていると、AMD のドキュメント³に次の記述を見つけました。

Linear aliasing occurs when two different linear addresses are mapped to the same physical address. This can cause performance penalties for loads and stores to the aliased cachelines. A load to an address that is valid in the L1 DC but under a different linear alias will see an L1 DC miss, which requires an L2 cache request to be made. The latency will generally be no larger than that of an L2 cache hit.

どうやら、同じ物理アドレスに異なる仮想アドレスからアクセスすると、データが L1 キャッシュに存在するにもかかわらず、L2 キャッシュへのリクエストが発生する場合があるようです。

ドキュメントの同じ節では、この現象に関連するキャッシュの仕組みについても説明されています。 L1 キャッシュの各キャッシュラインには、仮想アドレスのハッシュ値である μtag（マイクロタグ）が記録されています。 メモリロード時に、仮想アドレスから μtag を計算し、対応するセットの各 way に記録された μtag と比較します。 一致する way が存在しない場合は L2 キャッシュへのリクエストが発生し、その応答でキャッシュラインの μtag が更新されます。

同じ物理アドレスに異なる仮想アドレスをマッピングしている場合、μtag の値は仮想アドレスごとに異なります⁴。 その結果、データが L1 キャッシュにあったとしても、μtag がキャッシュラインのものと一致せず、L2 キャッシュへのリクエストが発生することがあるわけです。

エイリアス数とレイテンシの関係

この現象を詳しく調べるために、1 つの物理ページにマッピングする仮想ページ（エイリアス）の個数を変えてロードレイテンシを計測するベンチマークを作成します⁵。

バッファサイズをページサイズに合わせて 4 KiB とし、pointer chain を作成します⁶。 ポインタが 8 バイトの場合、1 つの物理ページには 512 個のポインタを格納できます。 これらのポインタに異なる仮想ページからアクセスすれば、バッファサイズを固定したまま、エイリアス数を最大で 512 まで増やせます。 ただし、エイリアス数が TLB エントリ数を超えると TLB ミスの影響を考慮する必要が生じてしまうため、ベンチマークではエイリアス数を 1 から 32 まで変えて計測します。

エイリアス数ごとに 5 種類の乱数シードでベンチマークを実行し、得られたレイテンシの中央値を、そのエイリアス数のロードレイテンシとします。 各シードでは、100 万回のロードを 1 回の試行とし、3 回のウォームアップ実行後に 10 回計測して、サイクル数が最小となった試行の結果を記録します。

複数の仮想ページを 1 つの物理ページにマッピングする

複数の仮想ページをマッピングするために、ファイルディスクリプタを介してアクセスできる物理ページを用意します。 memfd_create でバッファを表す匿名ファイルを作成し、ftruncate でサイズを 4 KiB に拡張します。

次に、mmap で PROT_NONE を指定し、num_aliases 個の仮想ページを確保します。

1
2
3
4
5
6
7
8

auto* const virtual_pages = mmap(
    nullptr,
    num_aliases * page_size,
    PROT_NONE,
    MAP_PRIVATE | MAP_ANONYMOUS,
    -1,
    0
);

続いて、各仮想ページに物理ページを割り当てます。

1
2
3
4
5
6
7
8

auto* const mapped_page = mmap(
    virtual_page_addr,
    page_size,
    PROT_READ | PROT_WRITE,
    MAP_SHARED | MAP_FIXED,
    backing_fd,
    backing_page_offset
);

virtual_page_addr は仮想ページのアドレス、backing_fd は物理ページ用の匿名ファイルのファイルディスクリプタです。 backing_page_offset はマッピングする物理ページのファイル内オフセットです。 今回は 1 つの物理ページのみを扱うため、すべての仮想ページで 0 を指定します。

エイリアス数に応じて仮想ページの割り当てを決める

1 つの物理ページに格納される 512 個のポインタについて、アクセスに使用する仮想ページを巡回的に割り当てます。 物理ページ内の backing_slot_index 番目のポインタに割り当てる仮想ページの番号 alias_index は次式で与えられます。

1

const auto alias_index = backing_slot_index % num_aliases;

L2 キャッシュへのリクエスト数を計測する

perf-counter を使って、L1 キャッシュへのデータ供給（L1D_MISS）に加えて、L2 キャッシュへの読み出しリクエスト（L2_READ_REQUEST）と、L2 キャッシュにヒットしたリクエスト（L2_READ_REQUEST_HIT）を数えます。 Zen 2 向けのイベント定義は次の通りです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

constexpr auto L1D_MISS =
    "amd64_fam17h_zen2::DATA_CACHE_REFILLS_FROM_SYSTEM"
    ":MABRESP_LCL_L2"
    ":LS_MABRESP_LCL_CACHE"
    ":LS_MABRESP_LCL_DRAM"
    ":LS_MABRESP_RMT_CACHE"
    ":LS_MABRESP_RMT_DRAM";
constexpr auto L2_READ_REQUEST =
    "amd64_fam17h_zen2::REQUESTS_TO_L2_GROUP1"
    ":RD_BLK_L"
    ":LS_RD_BLK_C_S";
constexpr auto L2_READ_REQUEST_HIT =
    "amd64_fam17h_zen2::CORE_TO_L2_CACHEABLE_REQUEST_ACCESS_STATUS"
    ":LS_RD_BLK_C_S"
    ":LS_RD_BLK_L_HIT_X"
    ":LS_RD_BLK_L_HIT_S";

ビルドと実行

リポジトリのルートで Zen 2 向けにビルドします。 使用した GCC のバージョンは 16.1.1 です。

1
2

$ cmake -S . -B build -DCMAKE_BUILD_TYPE=Release -DMICRO_BENCHMARK_SUITE_ARCH=znver2
$ cmake --build build

CPU コア 7 番を指定し、プロセスの優先度を 99 にしてベンチマークを実行します。

1

$ sudo chrt -f 99 taskset -c 7 ./build/memory_latency/virtual_address_aliasing_latency

計測結果

AMD Ryzen 7 4700U (Zen 2) での計測結果を次の表に示します。 イベントの値は、いずれも 100 万回のロードにおける発生回数です。

エイリアス数が 1 の場合、ロードレイテンシは 4.00 サイクルであり、以前計測した L1 キャッシュのレイテンシと一致しています。 エイリアスを増やすと、レイテンシが増加していき、8 以上の場合は約 12 サイクルで、L2 キャッシュのレイテンシと同程度です。

L2 キャッシュへの読み出しリクエストは、エイリアス数とともに増え、8 以上ではほぼすべてのロードで L2 キャッシュへのリクエストが発生しています。 一方、L1 キャッシュへのデータのリフィルは、エイリアス数によらずほとんど発生していません。

すなわち、エイリアスが増えると、L1 キャッシュにデータがあるにもかかわらず L2 キャッシュへのリクエストが発生し、ロードレイテンシが増加することが確認できました。

L2 キャッシュへのリクエストが発生する条件

キャッシュラインへの前回のロードと異なるエイリアスを使う確率

「データが L1 キャッシュにある場合、同じキャッシュラインへの前回のロードと異なるエイリアスを使ってアクセスするときのみ、L2 キャッシュへのリクエストが発生する」という仮説を立てて、リクエストの発生確率を見積もります。

キャッシュラインサイズが 64 バイトの場合、1 本のキャッシュラインには 8 個のポインタが収まります。 前述の方法で各ポインタに仮想ページを割り当てると、キャッシュライン内の 8 個のポインタに割り当てられる仮想ページの番号は次の図のようになります。

pointer chain は各ポインタに 1 度ずつアクセスするため、同じキャッシュラインへの前回のロードは、別のポインタに対するものです。 また、キャッシュライン内のポインタへのアクセス順序はランダムです。したがって、前回のロードの対象は、残り 7 個のポインタから等確率で選ばれるものとみなせます。 以上をもとに、アクセスに使用するエイリアスが、同じキャッシュラインへの前回のロードで使われたエイリアスと異なる確率 $p$ は次の表のようになります。

推定値と実測値の比較

上記の仮説のもとで、ロードレイテンシは、確率 $p$ で L2 キャッシュのレイテンシ、確率 $1-p$ で L1 キャッシュのレイテンシとなります。 したがって、平均レイテンシ $T$ は次式で推定できます。

先ほど計算した確率 $p$ と L2 読み出しリクエストの発生率（L2_READ_REQUEST の発生回数をロード回数の 100 万で割った値）、およびレイテンシの推定値と実測値を次の表に示します。

同じキャッシュラインへの前回のロードと異なるエイリアスを使う確率 $p$ が、L2 読み出しリクエストの発生率とよく一致しています。 また、レイテンシの推定値は実測値とかなり近い値になっています。

すなわち、「データが L1 キャッシュにある場合、同じキャッシュラインへの前回のロードと異なるエイリアスを使ってアクセスするときのみ、L2 キャッシュへのリクエストが発生する」という仮説と矛盾しない計測結果が得られています。

参考

• memfd_create(2)
• micro-benchmark-suite
• mmap(2)
• perf-counter
• Software Optimization Guide for AMD EPYC 7002 Processors