Pola Akses Data yang Benar-Benar Membuat CPU Marah

 (blog.weineng.me)
1 poin oleh GN⁺ 3 jam lalu | 1 komentar | Bagikan ke WhatsApp
  • Bahkan pada loop penjumlahan bilangan bulat yang sama, hanya dengan mengubah urutan akses waktu eksekusi bisa berubah drastis, dan eksperimen menunjukkan bahwa dimungkinkan membuat permutasi yang lebih dari 30% lebih lambat daripada akses acak
  • Akses linear cepat di 132,7 juta siklus, sedangkan akses acak melambat hingga 1,57 miliar siklus karena CPU sulit memprediksi lokasi berikutnya
  • Dengan memanfaatkan batas cache line dan halaman untuk merenggangkan akses, prefetcher dan penggunaan ulang cache melemah, dan karena karakteristik cache set-associative, kapasitas L1d yang efektif menyusut hingga sekitar 768B
  • Saat stride halaman diatur ke 8, locality cache line PTE ikut rusak sehingga tercatat 2,06 miliar siklus, menjadikannya pola yang lebih buruk daripada shuffle acak biasa
  • Pola aproksimasi yang menargetkan konflik bank/row DRAM sedikit lebih lambat di 2,08 miliar siklus, tetapi pemetaan DRAM dari alamat fisik bergantung pada platform sehingga sulit dikendalikan sepenuhnya

Kondisi eksperimen dan acuan

  • Tujuannya adalah mengubah hanya permutasi positions dalam fungsi accumulator tetap yang menjumlahkan bilangan bulat pada array data untuk menghasilkan waktu eksekusi paling lambat
  • Waktu pembuatan positions tidak dihitung, dan hanya waktu eksekusi fungsi akumulasi yang diukur dengan penghitung siklus rdtsc
  • Ukuran data adalah 2^26 bilangan bulat uint32_t
    • Menggunakan 65.536 halaman
    • Tiap halaman berukuran 4.096 byte
    • Tiap halaman berisi 1.024 bilangan bulat
  • Huge pages dinonaktifkan
  • Mesin pengukuran adalah sistem x86_64 berbasis Intel Core Ultra 7 268V
    • 8 CPU
    • Total L1d 320KiB, total L1i 512KiB
    • Total L2 14MiB
    • L3 12MiB
  • Seluruh kode ada di repositori GitHub, dan contoh dijalankan dengan g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out
  • Loop intinya berbentuk sederhana: menjumlahkan data[pos] yang ditunjuk oleh positions[i] secara berurutan

Perbedaan akses linear dan akses acak

  • Pola paling sederhana, linear, mengakses array dari depan secara berurutan dengan positions[i] = i
  • Akses linear memerlukan 132.752.394 siklus, dan termasuk yang paling cepat karena CPU sangat dioptimalkan untuk akses berurutan
  • Jika positions dibuat menjadi permutasi acak dengan fisher_yates_shuffle, CPU akan sulit memprediksi data yang akan diakses berikutnya
  • Akses acak memerlukan 1.572.108.618 siklus, lebih dari 10 kali lebih lambat daripada akses linear
  • Eksperimen kemudian melangkah lebih jauh untuk melihat apakah permutasi yang lebih buruk daripada acak bisa dibuat secara sengaja

Merenggangkan akses per cache line dan per halaman

  • Pola pemburuk pertama menata positions agar akses berurutan selalu berjarak satu cache line
  • Dalam pola ini, dari cache line 64 byte hanya satu bilangan bulat 4 byte yang dipakai, lalu langsung pindah ke cache line berikutnya
    • Saat kembali ke cache line yang sama, kemungkinan besar data yang bisa dipakai ulang sudah terdesak keluar dari cache
  • Akses berjarak cache line memerlukan 718.804.156 siklus, lebih dari 4 kali lebih lambat daripada pemindaian linear
  • Meski begitu, dalam kasus ini hardware prefetcher masih bisa mendeteksi pola streaming sederhana pada data dan mengambil cache line masa depan lebih dulu
  • Banyak hardware data prefetcher Intel tidak melakukan prefetch melintasi batas halaman 4KiB
  • Pola berikutnya merenggangkan interval akses bukan per cache line melainkan per seluruh halaman
    • Tiap halaman berukuran 4.096 byte
    • Dengan bentuk page_index * elements_per_page + element_index, offset yang sama di setiap halaman diakses lebih dulu
  • Akses berjarak halaman melambat besar menjadi 1.411.153.154 siklus

Cache set-associative dan jarak penggunaan ulang

  • Cache L1d per core pada mesin eksperimen berukuran 48KB, 12-way, dengan 64 set
  • Karena L1d memiliki 64 set, alamat A dan A + 4096 byte dipetakan ke set L1d yang sama
    • 4.096 byte adalah 64 sets * 64-byte cache line
  • Stride per halaman membuat tiap loop internal tidak tersebar merata ke seluruh 64 set, melainkan terus menghantam set yang sama
  • Karena satu set hanya punya 12 way, jika lebih dari 12 cache line aktif saling berebut, CPU harus berulang kali menendang keluar line lalu memuatnya kembali
  • Walaupun kapasitas total L1d adalah 48KB, pada pola akses ini kapasitas L1d yang benar-benar berguna turun ke sekitar 768B, yaitu 12 ways * 64B
  • Pola separated_by_a_page mengakses 65.536 cache line sebelum kembali ke cache line yang sama, sehingga jarak penggunaan ulang cache line adalah 65.536
  • Pola separated_by_a_page_and_cacheline, yang juga memisahkan cache line di dalam halaman, memperbesar jarak penggunaan ulang menjadi 65536 pages * 4096 page size / 64 cacheline size
  • Namun hasilnya hampir sama dengan akses per halaman, yaitu 1.408.519.172 siklus
  • Eksperimen dijalankan pada core 3, dan core tersebut memiliki L2 2,5MB serta L1 48KB
    • Satu putaran melalui 65.536 halaman berarti mengakses 4MB data
    • Ini lebih besar daripada kapasitas private L1/L2 pada core tersebut
    • Karena itu, kecil kemungkinan cache line yang dibutuhkan berikutnya masih tersisa di private cache
  • Penggunaan ulang private cache hanya realistis diharapkan ketika jarak penggunaan ulang cache line kira-kira lebih kecil dari sekitar 40 ribu, yaitu ((2560+48)*1024/64)

Menyiksa page stride, PTE, hingga DRAM

  • Variasi berikutnya adalah pola separated_by_stride_pages_and_cacheline, yang mengakses bukan halaman berurutan melainkan dengan jarak N halaman
  • Setelah beberapa stride diukur, hasil terburuk muncul saat stride halaman adalah 8, dan ini lebih lambat daripada akses acak
  • Jika dijalankan sendiri dengan -DSTRIDE=8, hasilnya adalah 2.058.425.640 siklus
  • Salah satu kemungkinan penyebab puncak pada stride 8 adalah translasi alamat
    • Saat alamat virtual diakses, MMU menerjemahkannya menjadi alamat fisik
    • Translasi ini menggunakan page table entry (PTE)
    • PTE berukuran 8 byte, dan satu cache line memuat 8 PTE
    • Pada stride 8 halaman, diduga bukan hanya cache line data yang harus diambil setiap kali, tetapi juga cache line terpisah untuk pemetaan halaman
  • Tahap terakhir adalah mencoba mengganggu sampai ke cara kerja DRAM controller
  • DRAM terdiri dari channel, rank, chip, bank, row, dan column
    • Di dalam bank terdapat banyak row
    • Untuk mengakses row tertentu, row tersebut harus diaktifkan dan disalin ke row buffer
    • Jika ingin mengakses row lain dalam bank yang sama, row lama harus ditutup dengan precharge lalu row baru diaktifkan
  • Jika akses bergantian terjadi antara row-row berbeda dalam bank yang sama, akan timbul row-buffer conflict dan respons DRAM controller melambat
  • Sebaliknya, jika mengakses row yang sudah terbuka, itu menjadi row-buffer hit, dan jika beberapa bank dipakai bersamaan memory controller bisa menumpuk pekerjaan secara paralel
  • Strategi untuk membuat pola lambat adalah sebagai berikut
    • Menerjemahkan virtual page number melalui page table menjadi physical frame number (PFN)
    • Mempertahankan page offset untuk membentuk alamat fisik
    • Menafsirkan alamat fisik menjadi channel, rank, bank group, bank, row, dan column DRAM
    • Berulang kali mengakses row-row berbeda dalam bank yang sama agar hampir setiap permintaan memaksa precharge dan activation
  • Namun, pemetaan dari alamat fisik ke channel, rank, bank, dan row DRAM tidak terdokumentasi dan bergantung pada platform
    • Bisa berbeda tergantung CPU, tipe memori, pengaturan BIOS/firmware, konfigurasi channel/rank, dan address hashing
    • Alat seperti DRAMA atau Sudoku bisa dipakai, tetapi pada mesin eksperimen ini keduanya tidak bisa dijalankan
  • Berdasarkan makalah DRAMA dan eksperimen lokal, digunakan pendekatan dengan 4 bank group, 4 bank per group, dan DRAM_ROW_SHIFT = 18
  • Pola yang juga mempertimbangkan konflik bank/row DRAM mencatat 2.082.308.014 siklus, konsisten sedikit lebih lambat daripada stride 8, tetapi selisihnya tidak besar
  • Ada beberapa keterbatasan yang membuat row conflict sempurna tidak tercapai
    • Estimasi bank group hash, bank hash, dan row shift mungkin tidak akurat
    • Stride 8 halaman berarti akses berjarak sekitar 32KB, sehingga sulit tetap berada pada row DRAM yang sama
    • Karena bank hashing Intel, pada praktiknya beberapa bank mungkin tetap dipakai bersamaan
  • Contoh hasil keseluruhan menunjukkan angka berikut
    • 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
  • Dengan secara bertahap memperburuk karakteristik cache, prefetcher, penggunaan ulang cache line, akses PTE, dan bank/row DRAM, dimungkinkan membuat pola penjumlahan yang 33% lebih lambat daripada akses acak
  • Ada juga cara lain untuk memperlambat akumulasi, seperti perpindahan ke mode hemat daya, tetapi itu terpisah dari eksperimen yang hanya mengubah pola akses

Bacaan terkait

1 komentar

 
GN⁺ 3 jam lalu
Komentar di Lobste.rs

  • Menarik membacanya karena terasa seperti beginilah rupa riset pengembangan internal Windows 11 /s

  • Saya mempelajari ini saat membuat https://github.com/ob/cache

    • Saya penasaran bagaimana harus memahami dua kalimat di README
      Yang satu mengatakan bahwa teknik untuk menghasilkan angka latensi pertama kali dilihat di soal latihan 5.2 halaman 476 Computer Architecture: A Quantitative Approach, sementara yang lain mengatakan idenya berasal dari disertasi doktoral Rafael Héctor Saavedra‑Barrera
      Saya ingin memastikan apakah keduanya membicarakan hal yang berbeda, saling bertentangan, atau sebenarnya sama dan Saavedra-Barrera dikutip di CA:AQA
      Juga tidak jelas apakah program Claude dikecualikan dari penulisan README, dan karena ia juga ditampilkan sebagai kontributor repositori, saya ingin terlebih dahulu memastikan apakah referensinya benar-benar nyata

  • Kalau ingin bereksperimen dengan akses hierarki cache kustom, saya juga merekomendasikan simulator yang saya buat
    https://github.com/TheCloudlet/Stratum

  • Saya penasaran bagaimana overhead menghitung indeks dipisahkan dari biaya akses sebenarnya

    • Jika yang ditanyakan adalah cara mengukur hanya siklus accumulator tanpa ikut menghitung waktu pembuatan positions, saya memakai makro yang menjalankan reset dan arrange_positions terlebih dahulu, lalu hanya menaruh accumulator(data, positions) di antara rdtsc_start() dan rdtsc_end()
      Setelah itu hasilnya dicetak, sum == linear_scan_sum diverifikasi, dan do_not_optimize(sum) dipakai untuk mencegah optimisasi menghapusnya

  • Kalau kita coba juga dengan pola akses data yang diajarkan para profesor, pertama-tama kita perlu membuat kelas SafeNumber.java dan anggota add(SafeNumber b)
    Semester depan sepertinya kita akan belajar arsitektur yang menaruh ini di belakang Redis untuk mendapatkan performa skala web
    Berkat Claude, saya mencoba memindahkan benchmark ke Java, dan Java SafeNumber[] sekitar 3,6 kali lebih lambat daripada C++ uint32_t[] pada akses linear, sementara pada shuffle Fisher-Yates sekitar 52,2 kali lebih lambat dibanding linear C++
    Dalam waktu absolut, untuk 67 juta elemen, C++ linear 10.258.584 ns, Java linear 36.740.667 ns, C++ shuffle 264.856.042 ns, Java shuffle 535.724.208 ns; cukup mengesankan karena ternyata “hanya 4 kali” lebih lambat dari yang saya bayangkan

    • Kelipatan Java memang tidak terlalu bagus, tetapi dengan hadirnya Project Valhalla nanti mungkin bisa menjadi lebih mendekati