CPUを本気で怒らせるデータアクセスパターン

 (blog.weineng.me)
1 ポイント 投稿者 GN⁺ 3 시간 전 | 1件のコメント | WhatsAppで共有
  • 同じ整数加算ループでもアクセス順を変えるだけで実行時間は大きく変わり、実験ではランダムアクセスより30%以上遅い順列を作れることを示している
  • 線形アクセスは1.33億サイクルと高速な一方、ランダムアクセスはCPUが次の位置を予測しにくく、15.7億サイクルまで遅くなる
  • キャッシュラインとページ境界を使ってアクセス間隔を広げると、プリフェッチャとキャッシュ再利用が弱まり、セットアソシアティブキャッシュの特性によりL1dの実質的な活用容量が768B程度まで減る
  • ページstrideを8にするとPTEキャッシュラインの局所性まで崩れ、20.6億サイクルを記録し、単純なランダムシャッフルよりさらに悪いパターンになる
  • DRAM bank/row衝突を狙った近似パターンは20.8億サイクルとわずかに遅かったが、物理アドレスのDRAMマッピングはプラットフォーム依存のため完全に制御するのは難しい

実験条件と基準

  • 目的は、data配列の整数を合計する固定されたaccumulator関数において、positionsの順列だけを変えて最も遅い実行時間を作ること
  • positionsの生成時間は除外し、累算関数の実行時間だけをrdtscのサイクルカウントで測定する
  • データサイズは2^26個のuint32_t整数
    • 65,536ページを使用
    • 各ページは4,096バイト
    • 各ページには1,024個の整数が入る
  • huge pagesは無効化されている
  • 測定マシンはIntel Core Ultra 7 268Vベースのx86_64システム
    • CPU 8個
    • L1d合計320KiB、L1i合計512KiB
    • L2合計14MiB
    • L3 12MiB
  • 全コードはGitHubリポジトリにあり、例はg++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.outで実行する
  • 中核となるループは、positions[i]が指すdata[pos]を順番に足していく単純な形

線形アクセスとランダムアクセスの違い

  • 最も単純なlinearパターンは、positions[i] = iとして配列を先頭から順にアクセスする
  • 線形アクセスは132,752,394サイクルで、CPUは逐次アクセスに強く最適化されているため、最速の部類に入る
  • fisher_yates_shuffleでpositionsをランダム順列にすると、CPUは次にアクセスするデータを予測しにくくなる
  • ランダムアクセスは1,572,108,618サイクルかかり、線形アクセスより10倍以上遅い
  • 実験ではさらに、ランダムより悪い順列を意図的に作れるかを確認する

キャッシュラインとページ単位でアクセス間隔を広げる

  • 最初の悪化パターンは、連続するアクセスが常にキャッシュライン1本分ずつ離れるようにpositionsを配置するもの
  • このパターンでは、64バイトのキャッシュラインから4バイト整数を1つだけ使ったあと、次のキャッシュラインへ移動する
    • 同じキャッシュラインに戻るころには、再利用可能なデータがキャッシュから追い出されている可能性が高い
  • キャッシュライン間隔のアクセスは718,804,156サイクルかかり、線形スキャンより4倍以上遅い
  • それでもこの場合、ハードウェアプリフェッチャはdataに対する単純なストリーミングパターンを検出し、将来のキャッシュラインを先読みできる
  • 多くのIntelハードウェアデータプリフェッチャは、4KiBページ境界を越えるプリフェッチを行わない
  • 次のパターンでは、アクセス間隔をキャッシュラインではなくページ全体に広げる
    • 各ページは4,096バイト
    • page_index * elements_per_page + element_indexという形で、ページごとの同じオフセットを先にアクセスする
  • ページ間隔のアクセスは1,411,153,154サイクルと大幅に遅くなる

セットアソシアティブキャッシュと再利用距離

  • 実験マシンのコアごとのL1dキャッシュは48KB、12-way、64 set構成
  • L1dには64個のsetがあるため、アドレスAとA + 4096バイトは同じL1d setにマップされる
    • 4,096バイトは64 sets * 64-byte cache lineに相当する
  • ページ単位のstrideでは、各内部ループが全64 setに均等に分散せず、同じsetを繰り返し叩くことになる
  • 1つのsetには12個のwayしかないため、12個を超えるアクティブなキャッシュラインが競合すると、CPUはラインを繰り返し追い出して再ロードしなければならない
  • L1d全体の容量は48KBだが、このアクセスパターンで有用に使われるL1d容量は12 ways * 64Bである768B程度
  • separated_by_a_pageパターンでは65,536本のキャッシュラインにアクセスしてから同じキャッシュラインに戻るため、キャッシュラインの再利用距離は65,536になる
  • ページ内のキャッシュラインまで分離したseparated_by_a_page_and_cachelineパターンでは、再利用距離を65536 pages * 4096 page size / 64 cacheline sizeまで伸ばす
  • しかし結果は1,408,519,172サイクルで、ページ単位アクセスとほぼ同じだった
  • 実験はcore 3で実行され、このコアは2.5MBのL2と48KBのL1を持つ
    • 65,536ページを一度巡回すると4MBのデータにアクセスする
    • これは当該コアのprivate L1/L2容量より大きい
    • 次に必要なキャッシュラインがprivate cacheに残っている可能性は低い
  • private cacheの再利用は、キャッシュラインの再利用距離がおおよそ((2560+48)*1024/64)、つまり約4万より小さい場合にのみ期待できる

ページstride、PTE、DRAMまで苦しめる

  • 次の変形は、連続ページではなくNページ間隔でアクセスするseparated_by_stride_pages_and_cachelineパターン
  • 複数のstrideを測定した結果、ページstrideが8のとき最悪の結果となり、ランダムアクセスより遅かった
  • -DSTRIDE=8で単独実行すると2,058,425,640サイクルかかる
  • stride 8でピークが生じた可能性のある理由の1つはアドレス変換
    • 仮想アドレスアクセスはMMUが物理アドレスに変換する
    • 変換にはpage table entry（PTE）が使われる
    • PTEは8バイトで、キャッシュライン1本にはPTEが8個入る
    • 8ページstrideでは、データキャッシュラインだけでなく、ページマッピング用の別のキャッシュラインも毎回取得することになると考えられる
  • 最後の段階は、DRAM controllerの動作まで妨害しようとする試み
  • DRAMはchannel、rank、chip、bank、row、columnで構成される
    • bankの中には複数のrowがある
    • 特定のrowにアクセスするには、そのrowを活性化してrow bufferにコピーする
    • 同じbankで別のrowにアクセスするには、既存のrowをprechargeで閉じ、新しいrowを活性化する必要がある
  • 同じbank内でrowを交互にアクセスするとrow-buffer conflictが発生し、DRAM controllerの応答が遅くなる
  • 逆に、すでに開いているrowへアクセスすればrow-buffer hitになり、複数のbankを同時に使えばmemory controllerが処理を重ね合わせて実行できる
  • 遅いパターンを作るための戦略は次のとおり
    • 仮想page numberをpage tableで物理frame number（PFN）に変換する
    • page offsetを保持して物理アドレスを構成する
    • 物理アドレスをDRAM channel、rank、bank group、bank、row、columnとして解釈する
    • 同じbank内の異なるrowを繰り返しアクセスし、ほぼ毎回prechargeとactivationを強制する
  • しかし、物理アドレスからDRAM channel、rank、bank、rowへのマッピングは文書化されておらず、プラットフォーム依存
    • CPU、メモリタイプ、BIOS/firmware設定、channel/rank構成、address hashingによって変わり得る
    • DRAMAやSudokuのようなツールを使えるが、この実験マシンでは動作させられなかった
  • DRAMA論文とローカル実験に基づき、bank group 4個、各groupあたりbank 4個、DRAM_ROW_SHIFT = 18を使って近似した
  • DRAM bank/row衝突まで考慮したパターンは2,082,308,014サイクルで、stride 8より一貫してわずかに遅かったが、差は大きくない
  • 完全なrow conflictを作れなかったことにはいくつか制約がある
    • bank group hash、bank hash、row shiftの推定が正確でない可能性がある
    • 8ページstrideは約32KB間隔のアクセスなので、同じDRAM rowにあるとは考えにくい
    • Intelのbank hashingにより、実際には複数のbankを同時に使うことになる
  • 全体の実行例は次の結果を示している
    • linear: 132,752,394
    • fisher_yates_shuffle: 1,572,108,618
    • separated_by_a_cacheline: 718,804,156
    • separated_by_a_page: 1,411,153,154
    • separated_by_a_page_and_cacheline: 1,408,519,172
    • stride=8 separated_by_stride_pages_and_cacheline: 2,058,425,640
    • separated_by_stride_bank_conflicts_and_cacheline: 2,082,308,014
  • キャッシュ、プリフェッチャ、キャッシュライン再利用、PTEアクセス、DRAM bank/row特性を順に悪化させると、ランダムアクセスより33%遅い加算パターンを作れる
  • 省電力モードへの移行のように累算をさらに遅くする方法もあるが、これはアクセスパターンだけを変える実験とは別の話

関連記事

1件のコメント

 
GN⁺ 3 시간 전
Lobste.rsでのコメント

  • 内部のWindows 11開発研究ってこんな感じなんだな、と思って面白く読んだ /s

  • https://github.com/ob/cache を作っているときに、この内容を学んだ

    • READMEの2つの文をどう理解すべきか気になっている
      1つは、Computer Architecture: A Quantitative Approach の476ページにある練習問題5.2で、レイテンシ数値を生成する手法を初めて見たと言っていて、もう1つはRafael Héctor Saavedra‑Barreraの博士論文からアイデアを得たと言っている
      別々の内容を指しているのか、矛盾しているのか、それとも同じ内容で、Saavedra-BarreraがCA:AQAで引用されているのか確認したい
      ClaudeプログラムがREADME作成から除外されていたのかも不明で、リポジトリのコントリビューターとしても表示されているので、まず参照が実在するのか確認したい

  • カスタムのキャッシュ階層アクセスを試してみたいなら、自分が作ったシミュレータもおすすめ
    https://github.com/TheCloudlet/Stratum

  • インデックスを計算するオーバーヘッドと実際のアクセスコストをどう分離したのか気になる

    • positionsを作る時間まで一緒に測らず、accumulatorのサイクルだけを測る方法を聞いているのなら、resetとarrange_positionsを先に実行してから、rdtsc_start()とrdtsc_end()の間にはaccumulator(data, positions)だけを入れるマクロを使った
      その後、結果を出力してsum == linear_scan_sumを検証し、do_not_optimize(sum)で最適化による削除を防いだ

  • 教授たちが教えてくれたデータアクセスパターンでも試すなら、まずSafeNumber.javaクラスを作って、add(SafeNumber b)メンバーが必要になる
    来学期には、これをRedisの後ろに配置してWebスケールの性能を出すアーキテクチャを学ぶことになりそう
    ClaudeのおかげでベンチマークをJavaに移植してみたところ、Java SafeNumber[]は線形アクセスでC++のuint32_t[]より約3.6倍遅く、Fisher-YatesシャッフルではC++の線形アクセス比で52.2倍遅かった
    絶対時間では6,700万要素の場合、C++線形が10,258,584ns、Java線形が36,740,667ns、C++シャッフルが264,856,042ns、Javaシャッフルが535,724,208nsで、思ったより「たった4倍」程度だったのが印象的

    • Javaの倍率はあまり良くないが、Project Valhallaが出ればもっと近づくかもしれない