Apa yang penting saat mengoptimalkan cache CPU (dalam C)?

13

Membaca ini dua pertanyaan , saya melihat bahwa memahami perilaku caching CPU dapat menjadi penting ketika berhadapan dengan sejumlah besar data dalam memori. Saya ingin memahami cara kerja cache untuk menambahkan alat lain ke kotak alat optimasi saya.

Apa poin inti tentang cara kerja cache CPU sehingga saya dapat menulis kode yang menggunakannya dengan bijaksana? Terkait, apakah ada cara untuk kode profil untuk melihat apakah penggunaan cache yang buruk memperlambat segalanya?

Timothy Jones
sumber
Cache tidak sama di mana-mana; paling jelas, ukurannya bervariasi. Jangan berharap mempelajari rahasia yang dalam, hanya praktik yang baik (seperti saran Michael Borgwardt).
David Thornley

Jawaban:

17
  • Simpan data Anda kecil jika memungkinkan
  • Simpan hal-hal yang akan diakses bersama (atau setelah satu sama lain) di satu sama lain dalam memori
  • Pelajari tentang parameter optimisasi kompiler Anda
  • Baca Apa yang harus diketahui setiap programmer tentang memori untuk detail lebih dari yang Anda inginkan
Michael Borgwardt
sumber
+1 untuk "Menyimpan hal-hal yang akan diakses bersama di samping satu sama lain"; itu yang mudah dilupakan.
Donal Fellows
Dan katakan pada kompiler untuk mengoptimalkan.
dibuka kembali
@WTP: kanan - ditambahkan.
Michael Borgwardt
Juga, menjaga mutex terpisah dengan baik. Mengubah mutex (harus) flush semua jalur cache itu, di semua CPU. Ini bisa menjadi hit kinerja besar jika Anda berhasil mendapatkan 2-3 mutex dalam satu baris cache.
Vatine
12

Kerumitan masalah ini telah melampaui pemahaman manusia hari ini. (Sudah seperti itu sejak 5 tahun terakhir.) Gabungkan bahwa dengan paralelisme vektor pendek (SIMD) dan Anda memiliki perasaan putus asa bahwa mengoptimalkan kode dengan tangan tidak lagi layak secara ekonomi - bukan karena itu tidak mungkin, tetapi itu akan tidak hemat biaya lagi.

Pendekatan saat ini adalah mengandalkan pengajaran komputer bagaimana mengoptimalkan - dengan membuat variasi kode yang menghitung jawaban yang sama dengan struktur yang berbeda (loop, struktur data, algoritma) dan secara otomatis mengevaluasi kinerja. Aturan untuk transformasi kode ditentukan dengan model matematika yang sangat ketat, sehingga merupakan sesuatu yang dapat dipahami oleh kedua ilmuwan komputer dan yang dapat dieksekusi oleh komputer.

Berikut ini adalah tautan yang diposting oleh Larry OBrien dalam salah satu jawabannya .

http://onward-conference.org/2011/images/Pueschel_2011_AutomaticPerformanceProgramming_Onward11.pdf

rwong
sumber
2
implementasi BLAS fasttest (GotoBLAS) menggunakan kode yang dioptimalkan dengan tangan untuk memastikan penggunaan cache maksimal untuk perkalian matriks
quant_dev
2

Sangat mungkin untuk memahami dan mengoptimalkan cache. Dimulai dengan memahami perangkat keras dan berlanjut dengan mengendalikan sistem. Semakin sedikit kendali yang Anda miliki atas sistem, semakin kecil kemungkinan Anda untuk berhasil. Linux atau Windows menjalankan banyak aplikasi / utas yang tidak idle.

Kebanyakan cache agak mirip dalam propertinya, gunakan beberapa bagian bidang alamat untuk mencari klik, memiliki kedalaman (cara), dan lebar (garis cache). Beberapa memiliki buffer tulis, beberapa dapat dikonfigurasi untuk menulis melalui atau mem-bypass cache pada write, dll.

Anda harus benar-benar menyadari semua transaksi memori yang terjadi yang mengenai cache itu (beberapa sistem memiliki instruksi independen dan cache data yang membuat tugas lebih mudah).

Anda dapat dengan mudah membuat cache tidak berguna dengan tidak mengatur memori Anda dengan hati-hati. Misalnya, jika Anda memiliki beberapa blok data yang sedang Anda proses, berharap untuk menyimpannya dalam cache, tetapi mereka berada dalam memori di alamat yang bahkan berlipatganda relatif terhadap pengecekan hit / miss cache, katakan 0x10000 0x20000 0x30000, dan Anda memiliki lebih dari ini daripada cara-cara dalam cache, Anda mungkin sangat cepat membuat sesuatu yang berjalan cukup lambat dengan cache aktif, lebih lambat daripada dengan cache dimatikan. Tapi ubah itu menjadi 0x10000, 0x21000, 0x32000 dan itu mungkin cukup untuk mengambil keuntungan penuh dari cache, mengurangi penggusuran.

Intinya, kunci untuk mengoptimalkan cache (well, selain mengetahui sistem dengan cukup baik) adalah untuk menjaga semua hal yang Anda butuhkan untuk kinerja dalam cache pada saat yang sama, mengatur data sedemikian rupa sehingga mungkin untuk memiliki semuanya ada dalam cache sekaligus. Dan mencegah hal-hal seperti eksekusi kode, menyela, dan peristiwa reguler atau acak lainnya mengusir bagian penting dari data ini yang Anda gunakan.

Hal yang sama berlaku untuk kode. Ini sedikit lebih sulit karena Anda perlu mengontrol lokasi tempat kode hidup untuk menghindari tabrakan dengan kode lain yang ingin Anda simpan dalam cache. Saat menguji / membuat profil kode apa pun yang melewati cache yang menambahkan satu baris kode di sana-sini atau bahkan satu nomor, apa pun yang menggeser atau mengubah alamat tempat kode itu hidup dari satu kompilasi ke kompilasi lain untuk kode yang sama, mengubah di mana garis cache termasuk dalam kode itu dan mengubah apa yang diusir dan apa yang tidak untuk bagian kritis.

old_timer
sumber
1

Baik jawaban nwong dan Michael Borgwardt memberikan saran yang bagus.

Juga, percayakan terlebih dahulu optimisasi kompiler pada masalah ini.

Jika menggunakan kompiler GCC terbaru, Anda mungkin menggunakan (dengan kekikiran) __builtin_prefetchfungsinya. Lihat jawaban ini di stackoverflow.

Basile Starynkevitch
sumber