Bagaimana cara menulis kode yang paling baik menggunakan cache CPU untuk meningkatkan kinerja?

159

Ini bisa terdengar seperti pertanyaan subyektif, tapi yang saya cari adalah contoh spesifik, yang bisa Anda temui terkait dengan ini.

  1. Bagaimana cara membuat kode, efektif cache / ramah cache (hit cache lebih banyak, sesedikit mungkin cache gagal)? Dari kedua perspektif, cache data & cache program (cache instruksi), yaitu hal-hal apa dalam kode seseorang, yang terkait dengan struktur data dan konstruksi kode, harus dipelihara untuk membuatnya menjadi cache yang efektif.

  2. Apakah ada struktur data tertentu yang harus digunakan / dihindari, atau adakah cara khusus untuk mengakses anggota struktur itu, dll ... untuk membuat kode cache lebih efektif.

  3. Apakah ada konstruksi program (jika, untuk, beralih, break, kebagian, ...), aliran-kode (untuk di dalam if, jika di dalam for, dll ...) orang harus mengikuti / menghindari dalam hal ini?

Saya menantikan pengalaman individual yang terkait dengan pembuatan kode efisien cache secara umum. Ini bisa berupa bahasa pemrograman (C, C ++, Majelis, ...), semua target perangkat keras (ARM, Intel, PowerPC, ...), semua OS (Windows, Linux, S ymbian, ...), dll. .

Variasi akan membantu untuk lebih memahaminya secara mendalam.

berarti emas
sumber
1
Sebagai pengantar, pembicaraan ini memberikan ikhtisar yang bagus youtu.be/BP6NxVxDQIs
schoetbi
URL singkat di atas tampaknya tidak berfungsi lagi, ini adalah URL lengkap untuk pembicaraan: youtube.com/watch?v=BP6NxVxDQIs
Abhinav Upadhyay

Jawaban:

119

Cache ada untuk mengurangi berapa kali CPU akan berhenti menunggu permintaan memori untuk dipenuhi (menghindari latensi memori ), dan sebagai efek kedua, mungkin untuk mengurangi jumlah keseluruhan data yang perlu ditransfer (menjaga bandwidth memori ).

Teknik untuk menghindari penderitaan akibat latensi pengambilan memori biasanya adalah hal pertama yang perlu dipertimbangkan, dan terkadang membantu jauh. Bandwidth memori yang terbatas juga merupakan faktor pembatas, terutama untuk aplikasi multicores dan multithread di mana banyak thread ingin menggunakan bus memori. Serangkaian teknik yang berbeda membantu mengatasi masalah yang terakhir.

Meningkatkan lokalitas spasial berarti Anda memastikan bahwa setiap baris cache digunakan secara penuh setelah dipetakan ke cache. Ketika kita telah melihat berbagai tolok ukur standar, kita telah melihat bahwa sebagian besar yang mengejutkan dari mereka gagal menggunakan 100% dari garis cache yang diambil sebelum garis cache digusur.

Meningkatkan pemanfaatan jalur cache membantu dalam tiga hal:

  • Itu cenderung lebih cocok dengan data yang berguna dalam cache, pada dasarnya meningkatkan ukuran cache yang efektif.
  • Itu cenderung lebih cocok dengan data yang berguna di baris cache yang sama, meningkatkan kemungkinan bahwa data yang diminta dapat ditemukan dalam cache.
  • Ini mengurangi persyaratan bandwidth memori, karena akan ada lebih sedikit pengambilan.

Teknik umum adalah:

  • Gunakan tipe data yang lebih kecil
  • Atur data Anda untuk menghindari lubang penyelarasan (mengurutkan anggota struct Anda dengan mengurangi ukuran adalah satu cara)
  • Waspadalah terhadap pengalokasi memori dinamis standar, yang dapat menyebabkan lubang dan menyebarkan data Anda ke dalam memori saat memanas.
  • Pastikan semua data yang berdekatan benar-benar digunakan dalam loop panas. Kalau tidak, pertimbangkan memecah struktur data menjadi komponen panas dan dingin, sehingga loop panas menggunakan data panas.
  • menghindari algoritma dan struktur data yang menunjukkan pola akses tidak teratur, dan mendukung struktur data linier.

Kami juga harus mencatat bahwa ada cara lain untuk menyembunyikan latensi memori daripada menggunakan cache.

CPU modern: sering memiliki satu atau lebih prefetcher perangkat keras . Mereka melatih pada kesalahan dalam cache dan mencoba untuk menemukan keteraturan. Misalnya, setelah beberapa kali melewatkan baris cache selanjutnya, prefetcher hw akan mulai mengambil baris cache ke dalam cache, mengantisipasi kebutuhan aplikasi. Jika Anda memiliki pola akses reguler, prefetcher perangkat keras biasanya melakukan pekerjaan yang sangat baik. Dan jika program Anda tidak menampilkan pola akses reguler, Anda dapat meningkatkan hal-hal dengan menambahkan sendiri instruksi pengambilan sebelumnya .

Mengelompokkan kembali instruksi sedemikian rupa sehingga mereka yang selalu ketinggalan dalam cache terjadi berdekatan satu sama lain, CPU kadang-kadang dapat tumpang tindih mengambil ini sehingga aplikasi hanya mempertahankan satu latensi hit ( Memory level parallelism ).

Untuk mengurangi tekanan bus memori keseluruhan, Anda harus mulai menangani apa yang disebut temporal locality . Ini berarti bahwa Anda harus menggunakan kembali data saat itu masih belum diusir dari cache.

Menggabungkan loop yang menyentuh data yang sama ( loop fusion ), dan menggunakan teknik penulisan ulang yang dikenal sebagai ubin atau memblokir semua upaya untuk menghindari pengambilan memori ekstra.

Meskipun ada beberapa aturan praktis untuk latihan penulisan ulang ini, Anda biasanya harus mempertimbangkan dengan hati-hati dependensi data yang dibawa, untuk memastikan bahwa Anda tidak memengaruhi semantik program.

Hal-hal inilah yang benar-benar terbayar di dunia multicore, di mana Anda biasanya tidak akan melihat banyak peningkatan throughput setelah menambahkan utas kedua.

Mats N
sumber
5
Ketika kita telah melihat berbagai tolok ukur standar, kita telah melihat bahwa sebagian besar yang mengejutkan dari mereka gagal menggunakan 100% dari garis cache yang diambil sebelum garis cache digusur. Bolehkah saya bertanya alat bantu profil seperti apa yang memberi Anda informasi semacam ini, dan bagaimana?
Dragon Energy
"Atur data Anda untuk menghindari lubang penyelarasan (mengurutkan anggota struct Anda dengan mengurangi ukuran adalah satu cara)" - mengapa kompiler tidak mengoptimalkannya sendiri? mengapa kompiler tidak selalu dapat "mengurutkan anggota dengan mengurangi ukuran"? apa untungnya menjaga anggota tidak disortir?
javapowered
Saya tidak tahu asal-usulnya, tetapi untuk satu, pesanan anggota sangat penting dalam katakanlah komunikasi jaringan, di mana Anda mungkin ingin mengirim seluruh struktur byte demi byte melalui web.
Kobrar
1
@javapowered Kompiler mungkin dapat melakukan itu tergantung pada bahasanya, meskipun saya tidak yakin apakah ada yang melakukannya. Alasan Anda tidak dapat melakukannya di C adalah bahwa itu benar-benar valid untuk mengalamatkan anggota dengan alamat dasar + offset daripada dengan nama, yang berarti memesan kembali anggota akan benar-benar merusak program.
Dan Bechard
56

Saya tidak percaya tidak ada lagi jawaban untuk ini. Bagaimanapun, satu contoh klasik adalah untuk mengulangi array multidimensi "dalam ke luar":

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

Alasan ini adalah cache tidak efisien karena CPU modern akan memuat garis cache dengan alamat memori "dekat" dari memori utama ketika Anda mengakses satu alamat memori. Kami melakukan iterasi melalui baris "j" (luar) dalam array di loop dalam, jadi untuk setiap perjalanan melalui loop dalam, garis cache akan menyebabkan memerah dan dimuat dengan garis alamat yang dekat dengan [ j] [i] entri. Jika ini diubah ke yang setara:

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]

Ini akan berjalan lebih cepat.

INFORMASI 1800
sumber
9
kembali di perguruan tinggi, kami memiliki tugas pada perkalian matriks. Ternyata lebih cepat mengambil transpos matriks "kolom" terlebih dahulu dan mengalikan baris demi baris daripada baris demi baris untuk alasan yang tepat.
ykaganovich
11
sebenarnya, sebagian besar kompiler modern dapat mengetahui hal ini dengan sendirinya (dengan optimisasi diaktifkan)
Ricardo Nolde
1
@ykaganovich Itu juga contoh dalam artikel Ulrich Dreppers: lwn.net/Articles/255364
Simon Stender Boisen
Saya tidak yakin ini selalu benar - jika seluruh array cocok dengan cache L1 (sering 32k!) Kedua pesanan akan memiliki jumlah hit dan miss cache yang sama. Mungkin pre-fetching memori mungkin memiliki dampak, saya kira. Senang bisa diperbaiki tentu saja.
Matt Parkins
siapa yang akan memilih versi pertama dari kode ini jika pesanan tidak menjadi masalah?
silver_rocket
45

Aturan dasar sebenarnya cukup sederhana. Di mana itu menjadi rumit adalah bagaimana mereka berlaku untuk kode Anda.

Cache bekerja pada dua prinsip: temporal locality dan spatial locality. Yang pertama adalah gagasan bahwa jika Anda baru-baru ini menggunakan sepotong data tertentu, Anda mungkin akan membutuhkannya lagi segera. Yang terakhir berarti bahwa jika Anda baru-baru ini menggunakan data di alamat X, Anda mungkin akan segera membutuhkan alamat X + 1.

Cache mencoba untuk mengakomodasi ini dengan mengingat potongan data yang terakhir digunakan. Ini beroperasi dengan garis cache, biasanya berukuran 128 byte atau lebih, jadi bahkan jika Anda hanya membutuhkan satu byte, seluruh baris cache yang berisi itu akan ditarik ke dalam cache. Jadi jika Anda memerlukan byte berikut setelahnya, itu sudah ada dalam cache.

Dan ini berarti Anda akan selalu menginginkan kode Anda sendiri untuk mengeksploitasi dua bentuk lokalitas ini sebanyak mungkin. Jangan lompati memori. Lakukan sebanyak mungkin pekerjaan di satu area kecil, dan kemudian pindah ke yang berikutnya, dan lakukan sebanyak mungkin pekerjaan di sana.

Contoh sederhana adalah larik array 2D yang ditunjukkan oleh jawaban 1800. Jika Anda melewatinya satu per satu, Anda membaca memori secara berurutan. Jika Anda melakukannya dengan bijaksana, Anda akan membaca satu entri, lalu melompat ke lokasi yang sama sekali berbeda (awal baris berikutnya), membaca satu entri, dan melompat lagi. Dan ketika Anda akhirnya kembali ke baris pertama, itu tidak akan lagi berada di cache.

Hal yang sama berlaku untuk kode. Lompatan atau cabang berarti penggunaan cache yang kurang efisien (karena Anda tidak membaca instruksi secara berurutan, tetapi melompat ke alamat lain). Tentu saja, pernyataan if kecil mungkin tidak akan mengubah apa pun (Anda hanya melewatkan beberapa byte, sehingga Anda masih akan berakhir di dalam wilayah cache), tetapi pemanggilan fungsi biasanya menyiratkan bahwa Anda melompat ke yang benar-benar berbeda alamat yang mungkin tidak di-cache. Kecuali jika itu disebut baru-baru ini.

Instruksi penggunaan cache biasanya jauh dari masalah. Apa yang biasanya perlu Anda khawatirkan adalah data cache.

Dalam sebuah struct atau kelas, semua anggota diletakkan secara bersebelahan, yang bagus. Dalam sebuah array, semua entri ditata secara bersamaan. Dalam daftar tertaut, setiap node dialokasikan di lokasi yang sama sekali berbeda, yang buruk. Pointer secara umum cenderung mengarah ke alamat yang tidak terkait, yang mungkin akan menghasilkan cache yang hilang jika Anda merujuknya.

Dan jika Anda ingin mengeksploitasi banyak core, itu bisa menjadi sangat menarik, seperti biasanya, hanya satu CPU yang mungkin memiliki alamat yang diberikan dalam cache L1 pada suatu waktu. Jadi jika kedua core secara konstan mengakses alamat yang sama, itu akan mengakibatkan cache yang terus-menerus hilang, karena mereka berebut alamat.

jalf
sumber
4
+1, saran yang bagus dan praktis. Satu tambahan: Waktu lokalitas dan lokalitas ruang digabungkan menyarankan, bahwa untuk operasi matriks misalnya, mungkin disarankan untuk membaginya menjadi matriks yang lebih kecil yang benar-benar cocok dengan garis cache, atau yang baris / kolomnya cocok dengan garis cache. Saya ingat melakukan itu untuk visualisasi multidim. data. Ini memberikan beberapa tendangan serius di celana. Adalah baik untuk mengingat bahwa cache memang menampung lebih dari satu 'baris';)
AndreasT
1
Anda mengatakan hanya 1 CPU yang dapat memiliki alamat yang diberikan dalam cache L1 pada suatu waktu - saya berasumsi maksud Anda garis cache daripada alamat. Saya juga pernah mendengar masalah berbagi yang salah ketika setidaknya salah satu CPU melakukan penulisan, tetapi tidak jika keduanya hanya melakukan membaca. Jadi dengan 'akses', apakah maksud Anda menulis?
Joseph Garvin
2
@ JosephephGarvin: ya, maksud saya menulis. Anda benar, banyak core dapat memiliki garis cache yang sama di cache L1 mereka pada saat yang sama, tetapi ketika satu core menulis ke alamat-alamat ini, itu akan tidak valid di semua cache L1 lainnya, dan kemudian mereka harus memuatnya kembali sebelum mereka dapat melakukan apa saja dengan itu. Maaf untuk kata-kata yang salah (salah). :)
jalf
44

Saya sarankan membaca artikel 9-bagian Apa yang harus diketahui setiap programmer tentang memori oleh Ulrich Drepper jika Anda tertarik pada bagaimana memori dan perangkat lunak berinteraksi. Ini juga tersedia dalam format 104 halaman PDF .

Bagian yang sangat relevan dengan pertanyaan ini mungkin Bagian 2 (cache CPU) dan Bagian 5 (Apa yang dapat dilakukan oleh programmer - optimasi cache).

Tomi Kyöstilä
sumber
16
Anda harus menambahkan ringkasan poin utama dari artikel.
Azmisov
Banyak membaca, tetapi buku lain yang HARUS disebutkan di sini adalah Hennessy, Patterson, Arsitektur Komputer, Pendekatan Kuantitatif , yang tersedia dalam edisi ke-5 hari ini.
Haymo Kutschbach
15

Terlepas dari pola akses data, faktor utama dalam kode ramah-cache adalah ukuran data . Lebih sedikit data berarti lebih banyak cocok dengan cache.

Ini terutama merupakan faktor dengan struktur data yang disejajarkan dengan memori. "Konvensional" kebijaksanaan mengatakan struktur data harus disejajarkan pada batas-batas kata karena CPU hanya dapat mengakses seluruh kata, dan jika sebuah kata mengandung lebih dari satu nilai, Anda harus melakukan pekerjaan tambahan (baca-modifikasi-tulis alih-alih menulis sederhana) . Tetapi cache bisa sepenuhnya membatalkan argumen ini.

Demikian pula, array boolean Java menggunakan seluruh byte untuk setiap nilai untuk memungkinkan operasi pada nilai individual secara langsung. Anda dapat mengurangi ukuran data dengan faktor 8 jika Anda menggunakan bit aktual, tetapi kemudian akses ke nilai individual menjadi jauh lebih kompleks, membutuhkan operasi bit shift dan mask ( BitSetkelas melakukan ini untuk Anda). Namun, karena efek cache, ini masih bisa jauh lebih cepat daripada menggunakan boolean [] ketika arraynya besar. IIRC I pernah mencapai speedup dengan faktor 2 atau 3 dengan cara ini.

Michael Borgwardt
sumber
9

Struktur data yang paling efektif untuk cache adalah array. Cache berfungsi paling baik, jika struktur data Anda diletakkan secara berurutan karena CPU membaca seluruh baris cache (biasanya 32 byte atau lebih) sekaligus dari memori utama.

Algoritma apa pun yang mengakses memori secara acak mengacak cache karena selalu membutuhkan baris cache baru untuk mengakomodasi memori yang diakses secara acak. Di sisi lain suatu algoritma, yang berjalan secara berurutan melalui array adalah yang terbaik karena:

  1. Ini memberi CPU kesempatan untuk membaca-depan, misalnya secara spekulatif memasukkan lebih banyak memori ke dalam cache, yang akan diakses nanti. Membaca-depan ini memberikan peningkatan kinerja yang sangat besar.

  2. Menjalankan loop ketat pada array besar juga memungkinkan CPU untuk cache kode yang dieksekusi dalam loop dan dalam kebanyakan kasus memungkinkan Anda untuk mengeksekusi algoritma sepenuhnya dari memori cache tanpa harus memblokir akses memori eksternal.

grover
sumber
@Grover: Tentang poin Anda 2. jadi bisa dikatakan bahwa jika di dalam loop ketat, sebuah fungsi dipanggil untuk setiap loop, maka ia akan mengambil kode baru sekaligus dan menyebabkan cache miss, alih-alih jika Anda dapat menempatkan fungsi sebagai kode dalam for loop itu sendiri, tidak ada panggilan fungsi, itu akan lebih cepat karena lebih sedikit cache yang hilang?
goldenmean
1
Iya dan tidak. Fungsi baru akan dimuat dalam cache. Jika ada cukup ruang cache, maka pada iterasi kedua ia sudah memiliki fungsi itu di dalam cache sehingga tidak ada alasan untuk memuatnya lagi. Jadi itu adalah hit pada panggilan pertama. Dalam C / C ++ Anda dapat meminta kompiler untuk menempatkan fungsi tepat di sebelah satu sama lain menggunakan segmen yang sesuai.
grover
Satu lagi catatan: Jika Anda memanggil keluar dari loop dan tidak ada ruang cache yang cukup, fungsi baru akan dimasukkan ke dalam cache terlepas. Bahkan mungkin terjadi bahwa loop asli akan dibuang dari cache. Dalam hal ini panggilan akan dikenakan hingga tiga penalti untuk setiap iterasi: Satu untuk memuat target panggilan dan satu lagi untuk memuat ulang loop. Dan yang ketiga jika loop head tidak berada di jalur cache yang sama dengan alamat panggilan balik. Dalam hal ini melompat ke loop head juga membutuhkan akses memori baru.
grover
8

Salah satu contoh yang saya lihat digunakan dalam mesin permainan adalah memindahkan data dari objek dan ke array mereka sendiri. Objek permainan yang tunduk pada fisika mungkin memiliki banyak data lain yang melekat padanya. Tetapi selama loop pembaruan fisika, semua mesin yang dipedulikan adalah data tentang posisi, kecepatan, massa, kotak pembatas, dll. Jadi semua itu ditempatkan ke dalam susunannya sendiri dan dioptimalkan sebanyak mungkin untuk SSE.

Jadi selama loop fisika, data fisika diproses dalam susunan array menggunakan matematika vektor. Objek game menggunakan ID objek mereka sebagai indeks ke berbagai array. Itu bukan pointer karena pointer bisa menjadi tidak valid jika array harus dipindahkan.

Dalam banyak hal ini melanggar pola desain berorientasi objek tetapi membuat kode jauh lebih cepat dengan menempatkan data berdekatan yang perlu dioperasikan di dalam loop yang sama.

Contoh ini mungkin kedaluwarsa karena saya berharap sebagian besar game modern menggunakan mesin fisika prebuilt seperti Havok.

Zan Lynx
sumber
2
+1 Tidak ketinggalan zaman. Ini adalah cara terbaik untuk mengatur data untuk mesin game - membuat blok data yang berdekatan, dan melakukan semua jenis operasi tertentu (katakanlah AI) sebelum pindah ke yang berikutnya (misalnya fisika) untuk meningkatkan kedekatan cache / lokalitas cache referensi.
Insinyur
Saya melihat contoh yang tepat ini dalam video di suatu tempat beberapa minggu yang lalu, tetapi sejak itu kehilangan tautannya / saya tidak ingat bagaimana cara menemukannya. Apakah ingat di mana Anda melihat contoh ini?
akan
@will: Tidak, saya tidak ingat persis di mana ini.
Zan Lynx
Ini adalah gagasan sistem komponen entitas (ECS: en.wikipedia.org/wiki/Entity_component_system ). Simpan data sebagai struct-of-array daripada array-of-struct yang lebih tradisional yang didorong oleh praktik OOP.
BuschnicK
7

Hanya satu pos yang menyentuh, tetapi masalah besar muncul saat berbagi data antar proses. Anda ingin menghindari beberapa proses yang berusaha mengubah garis cache yang sama secara bersamaan. Sesuatu yang perlu diwaspadai di sini adalah berbagi "salah", di mana dua struktur data yang berdekatan berbagi jalur cache dan modifikasi untuk satu membatalkan jalur cache untuk yang lain. Hal ini dapat menyebabkan garis cache untuk berpindah-pindah di antara cache prosesor berbagi data pada sistem multiprosesor secara tidak perlu. Cara untuk menghindarinya adalah dengan menyelaraskan dan memadatkan struktur data untuk menempatkannya pada garis yang berbeda.

RussellH
sumber
7

Sebuah komentar untuk "contoh klasik" oleh pengguna 1800 INFORMASI (terlalu panjang untuk komentar)

Saya ingin memeriksa perbedaan waktu untuk dua pesanan iterasi ("outter" dan "inner"), jadi saya membuat percobaan sederhana dengan array 2D besar:

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
    sum += A[ x + y*N ];
measure::stop();

dan kasus kedua dengan forloop ditukar.

Versi lebih lambat ("x pertama") adalah 0,88 dtk dan yang lebih cepat, adalah 0,06 dtk. Itulah kekuatan caching :)

Saya menggunakan gcc -O2dan masih loop tidak dioptimalkan. Komentar oleh Ricardo bahwa "sebagian besar kompiler modern dapat mengetahui hal ini dengan sendirinya" tidak berlaku

Jakub M.
sumber
Tidak yakin saya mendapatkan ini. Dalam kedua contoh, Anda masih mengakses setiap variabel dalam for for. Mengapa satu cara lebih cepat dari yang lain?
ed-
akhirnya intuitif bagi saya untuk memahami bagaimana pengaruhnya :)
Laie
@ EdwardCorlew Ini karena urutan di mana mereka diakses. Urutan y-first lebih cepat karena mengakses data secara berurutan. Ketika entri pertama diminta, L1 cache memuat seluruh cache-line, yang mencakup int yang diminta plus 15 berikutnya (dengan asumsi 64-byte cache-line), jadi tidak ada kios CPU yang menunggu 15. 15. X -rangka pertama lebih lambat karena elemen yang diakses tidak berurutan, dan mungkin N cukup besar sehingga memori yang diakses selalu di luar L1 cache dan setiap operasi berhenti.
Matt Parkins
4

Saya dapat menjawab (2) dengan mengatakan bahwa di dunia C ++, daftar tertaut dapat dengan mudah mematikan cache CPU. Array adalah solusi yang lebih baik jika memungkinkan. Tidak ada pengalaman tentang apakah hal yang sama berlaku untuk bahasa lain, tetapi mudah untuk membayangkan masalah yang sama akan muncul.

Andrew
sumber
@ Andrew: Bagaimana dengan struktur. Apakah cache itu efisien? Apakah mereka memiliki batasan ukuran untuk menjadi efisien cache?
goldenmean
Sebuah struct adalah satu blok memori, jadi selama itu tidak melebihi ukuran cache Anda, Anda tidak akan melihat dampaknya. Hanya ketika Anda memiliki koleksi struct (atau kelas) yang Anda akan melihat hit cache dan itu tergantung pada cara Anda mengatur koleksi. Array menabrak objek satu sama lain (bagus) tetapi daftar tertaut dapat memiliki objek di seluruh ruang alamat Anda dengan tautan di antara mereka, yang jelas-jelas buruk untuk kinerja cache.
Andrew
Beberapa cara untuk menggunakan daftar tertaut tanpa mematikan cache, paling efektif untuk daftar tidak besar, adalah dengan membuat kumpulan memori Anda sendiri, yaitu - untuk mengalokasikan satu array besar. kemudian alih-alih memori 'malloc'ing (atau' new'ing dalam C ++) untuk setiap anggota daftar tertaut kecil, yang dapat dialokasikan di tempat yang sama sekali berbeda dalam memori, dan ruang pengelolaan limbah, Anda memberikannya memori dari kumpulan memori Anda, sangat meningkatkan peluang yang secara logis menutup anggota daftar, akan berada di cache bersama.
Liran Orevi
Tentu, tetapi banyak pekerjaan mendapatkan std :: list <> et al. untuk menggunakan blok memori khusus Anda. Ketika saya masih muda, saya benar-benar menempuh jalan itu, tetapi belakangan ini ... terlalu banyak hal lain untuk diatasi.
Andrew
4

Cache diatur dalam "baris cache" dan (nyata) memori dibaca dari dan ditulis dalam potongan ukuran ini.

Struktur data yang terkandung dalam satu cache-line karenanya lebih efisien.

Demikian pula, algoritma yang mengakses blok memori yang berdekatan akan lebih efisien daripada algoritma yang melompat melalui memori secara acak.

Sayangnya ukuran garis cache bervariasi secara dramatis antara prosesor, jadi tidak ada cara untuk menjamin bahwa struktur data yang optimal pada satu prosesor akan efisien pada yang lain.

Alnitak
sumber
belum tentu. hanya berhati-hati tentang berbagi yang salah. terkadang Anda harus membagi data menjadi beberapa baris cache yang berbeda. seberapa efektif cache selalu bergantung pada bagaimana Anda menggunakannya.
DAG
4

Untuk bertanya bagaimana membuat kode, cache-cache-friendly dan sebagian besar pertanyaan lainnya, biasanya bertanya bagaimana Mengoptimalkan program, itu karena cache memiliki dampak yang sangat besar pada kinerja sehingga setiap program yang dioptimalkan adalah salah satu yang adalah cache ramah cache-efektif.

Saya sarankan membaca tentang Optimasi, ada beberapa jawaban bagus di situs ini. Dalam hal buku, saya merekomendasikan Sistem Komputer: Perspektif Programmer yang memiliki beberapa teks bagus tentang penggunaan cache yang tepat.

(btw - seburuk cache-miss bisa, ada yang lebih buruk - jika suatu program paging dari hard-drive ...)

Liran Orevi
sumber
4

Ada banyak jawaban pada saran umum seperti pemilihan struktur data, pola akses, dll. Di sini saya ingin menambahkan pola desain kode lain yang disebut pipeline perangkat lunak yang memanfaatkan manajemen cache aktif.

Idenya adalah meminjam dari teknik perpipaan lainnya, misalnya perpipaan instruksi CPU.

Jenis pola ini paling baik berlaku untuk prosedur itu

  1. dapat dipecah menjadi beberapa sub-langkah yang masuk akal, S [1], S [2], S [3], ... yang waktu eksekusi kira-kira sebanding dengan waktu akses RAM (~ 60-70ns).
  2. mengambil sejumlah input dan melakukan beberapa langkah tersebut untuk mendapatkan hasil.

Mari kita ambil contoh sederhana di mana hanya ada satu sub-prosedur. Biasanya kode ingin:

def proc(input):
    return sub-step(input))

Untuk memiliki kinerja yang lebih baik, Anda mungkin ingin meneruskan beberapa input ke fungsi dalam batch sehingga Anda mengamortisasi overhead panggilan fungsi dan juga meningkatkan lokalitas cache kode.

def batch_proc(inputs):
    results = []
    for i in inputs:
        // avoids code cache miss, but still suffer data(inputs) miss
        results.append(sub-step(i))
    return res

Namun, seperti yang dikatakan sebelumnya, jika pelaksanaan langkah ini kira-kira sama dengan waktu akses RAM Anda dapat lebih lanjut meningkatkan kode untuk sesuatu seperti ini:

def batch_pipelined_proc(inputs):
    for i in range(0, len(inputs)-1):
        prefetch(inputs[i+1])
        # work on current item while [i+1] is flying back from RAM
        results.append(sub-step(inputs[i-1]))

    results.append(sub-step(inputs[-1]))

Alur eksekusi akan terlihat seperti:

  1. prefetch (1) meminta CPU untuk mengambil input [1] ke cache, di mana instruksi prefetch mengambil siklus P itu sendiri dan kembali, dan di latar belakang input [1] akan tiba di cache setelah siklus R.
  2. works_on (0) miss dingin pada 0 dan bekerja di atasnya, yang mengambil M
  3. prefetch (2) menerbitkan pengambilan lain
  4. works_on (1) jika P + R <= M, maka input [1] harus sudah ada dalam cache sebelum langkah ini, sehingga menghindari kehilangan cache data
  5. works_on (2) ...

Mungkin ada lebih banyak langkah yang terlibat, maka Anda dapat merancang pipa multi-tahap selama waktu langkah-langkah dan kecocokan latensi akses memori, Anda akan mengalami sedikit kode / cache data yang hilang. Namun, proses ini perlu disesuaikan dengan banyak percobaan untuk mengetahui pengelompokan langkah yang tepat dan waktu pengambilan awal. Karena upaya yang diperlukan, ia melihat lebih banyak adopsi dalam pemrosesan data / paket aliran kinerja tinggi. Contoh kode produksi yang baik dapat ditemukan dalam desain saluran pipa DPDK QoS Enqueue: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Bab 21.2.4.3. Pipa Enqueue.

Informasi lebih lanjut dapat ditemukan:

https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

Wei Shen
sumber
1

Tulis program Anda untuk mengambil ukuran minimal. Itulah mengapa tidak selalu merupakan ide yang baik untuk menggunakan optimisasi -O3 untuk GCC. Ini membutuhkan ukuran yang lebih besar. Seringkali, -O sama baiknya dengan -O2. Itu semua tergantung pada prosesor yang digunakan. YMMV.

Bekerja dengan potongan kecil data sekaligus. Itulah sebabnya algoritma pengurutan yang kurang efisien dapat berjalan lebih cepat daripada quicksort jika kumpulan data besar. Temukan cara untuk memecah kumpulan data Anda yang lebih besar menjadi yang lebih kecil. Orang lain telah menyarankan ini.

Untuk membantu Anda lebih mengeksploitasi instruksi temporal / spatial locality, Anda mungkin ingin mempelajari bagaimana kode Anda dikonversi menjadi perakitan. Sebagai contoh:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

Kedua loop menghasilkan kode yang berbeda meskipun mereka hanya menguraikan array. Bagaimanapun, pertanyaan Anda sangat spesifik untuk arsitektur. Jadi, satu-satunya cara Anda untuk mengontrol penggunaan cache adalah dengan memahami cara kerja perangkat keras dan mengoptimalkan kode Anda untuk itu.

sybreon
sumber
Poin yang menarik. Apakah tembolok pandang depan membuat asumsi berdasarkan arah loop / melewati memori?
Andrew
1
Ada banyak cara untuk merancang cache data spekulatif. Langkah-langkah berbasis yang mengukur 'jarak' dan 'arah' akses data. Yang berbasis konten mengejar rantai penunjuk. Ada cara lain untuk mendesainnya.
sybreon
1

Selain menyelaraskan struktur dan bidang Anda, jika struktur Anda jika tumpukan dialokasikan, Anda mungkin ingin menggunakan pengalokasi yang mendukung alokasi yang selaras; seperti _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); jika tidak, Anda mungkin memiliki berbagi salah secara acak; ingat bahwa di Windows, tumpukan default memiliki penyelarasan 16 byte.

aracntido
sumber