Bagaimana cara kerja garis cache?

Saya mengerti bahwa prosesor membawa data ke cache melalui jalur cache, yang - misalnya, pada prosesor Atom saya - membawa sekitar 64 byte pada suatu waktu, berapapun ukuran data aktual yang sedang dibaca.

Pertanyaanku adalah:

Bayangkan Anda perlu membaca satu byte dari memori, yang 64 byte akan dimasukkan ke dalam cache?

Dua kemungkinan yang dapat saya lihat adalah bahwa, 64 byte dimulai pada batas 64 byte terdekat di bawah byte yang diinginkan, atau 64 byte tersebar di sekitar byte dalam beberapa cara yang telah ditentukan (misalnya, setengah di bawah, setengah di atas, atau semua diatas).

Yang mana itu?

Jika garis cache yang berisi byte atau kata yang Anda muat belum ada di cache, CPU Anda akan meminta 64 byte yang dimulai pada batas baris cache (alamat terbesar di bawah yang Anda butuhkan adalah kelipatan 64) .

Modul memori PC modern mentransfer 64 bit (8 byte) sekaligus, dalam delapan transfer , sehingga satu perintah memicu pembacaan atau penulisan baris cache penuh dari memori. (DDR1 / 2/3/4 SDRAM ukuran transfer burst dapat dikonfigurasi hingga 64B; CPU akan memilih ukuran transfer burst agar sesuai dengan ukuran garis cache mereka, tetapi 64B adalah umum)

Sebagai aturan praktis, jika prosesor tidak dapat memperkirakan akses memori (dan mengambilnya), proses pengambilan dapat memakan waktu ~ 90 nanoseconds, atau ~ 250 clock cycle (dari CPU yang mengetahui alamat hingga CPU menerima data).

Sebaliknya, hit pada cache L1 memiliki latensi penggunaan beban 3 atau 4 siklus, dan reload toko memiliki latensi penerusan toko 4 atau 5 siklus pada CPU x86 modern. Hal serupa pada arsitektur lain.

Bacaan lebih lanjut: Apa yang Harus Tahu Setiap Programmer Ulrich Drepper Tentang Memori . Saran prefetch software agak ketinggalan jaman: prefetcher HW modern lebih pintar, dan hyperthreading jauh lebih baik daripada di P4 hari (jadi thread prefetch biasanya sia-sia). Jugax86 tag wiki memiliki banyak tautan kinerja untuk arsitektur itu.

Jika garis cache 64 byte lebar, maka mereka sesuai dengan blok memori yang dimulai pada alamat yang dapat dibagi dengan 64. 6 bit paling signifikan dari alamat apa pun adalah offset ke baris cache.

Jadi untuk setiap byte yang diberikan, garis cache yang harus diambil dapat ditemukan dengan membersihkan enam bit alamat yang paling signifikan, yang sesuai dengan pembulatan ke alamat terdekat yang dapat dibagi dengan 64.

Meskipun ini dilakukan oleh perangkat keras, kami dapat menunjukkan perhitungan menggunakan beberapa definisi makro referensi C:

#define CACHE_BLOCK_BITS 6
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS)  /* 64 */
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1)    /* 63, 0x3F */

/* Which byte offset in its cache block does this address reference? */
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK)

/* Address of 64 byte block brought into the cache when ADDR accessed */
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK)

Pertama-tama akses memori utama sangat mahal. Saat ini CPU 2GHz (paling lambat sekali) memiliki kutu 2G (siklus) per detik. CPU (virtual core saat ini) dapat mengambil nilai dari registernya sekali per centang. Karena inti virtual terdiri dari beberapa unit pemrosesan (ALU - unit logika aritmatika, FPU dll), maka sebenarnya dapat memproses instruksi tertentu secara paralel jika memungkinkan.

Akses memori utama berharga sekitar 70ns hingga 100ns (DDR4 sedikit lebih cepat). Kali ini pada dasarnya mencari cache L1, L2 dan L3 dan kemudian mengenai memori (kirim perintah ke pengontrol memori, yang mengirimkannya ke bank memori), tunggu tanggapannya dan selesai.

100ns berarti sekitar 200 ticks. Jadi pada dasarnya jika sebuah program akan selalu melewatkan cache yang diakses oleh setiap memori, CPU akan menghabiskan sekitar 99,5% dari waktunya (jika hanya membaca memori) menganggur menunggu memori.

Untuk mempercepat, ada cache L1, L2, L3. Mereka menggunakan memori yang langsung ditempatkan pada chip dan menggunakan berbagai jenis rangkaian transistor untuk menyimpan bit yang diberikan. Ini membutuhkan lebih banyak ruang, lebih banyak energi dan lebih mahal daripada memori utama karena CPU biasanya diproduksi menggunakan teknologi yang lebih maju dan kegagalan produksi dalam memori L1, L2, L3 memiliki kesempatan untuk membuat CPU tidak berharga (cacat) sehingga cache L1, L2, L3 yang besar meningkatkan tingkat kesalahan yang menurunkan hasil yang secara langsung menurunkan ROI. Jadi ada trade off besar ketika datang ke ukuran cache yang tersedia.

(saat ini seseorang menciptakan lebih banyak cache L1, L2, L3 untuk dapat menonaktifkan bagian-bagian tertentu untuk mengurangi kemungkinan cacat produksi yang sebenarnya adalah area memori cache membuat kerusakan CPU membuat kerusakan CPU secara keseluruhan).

Untuk memberikan ide pengaturan waktu (sumber: biaya untuk mengakses cache dan memori )

• L1 cache: 1ns hingga 2ns (2-4 siklus)
• L2 cache: 3ns hingga 5ns (6-10 cycle)
• L3 cache: 12ns hingga 20ns (24-40 siklus)
• RAM: 60ns (120 siklus)

Karena kami mencampur jenis CPU yang berbeda, ini hanya perkiraan tetapi memberikan ide bagus apa yang sebenarnya terjadi ketika nilai memori diambil dan kami mungkin memiliki hit atau miss di lapisan cache tertentu.

Jadi cache pada dasarnya mempercepat akses memori (60ns vs 1ns).

Mengambil nilai, menyimpannya dalam cache untuk kesempatan membaca ulang itu baik untuk variabel yang sering diakses tetapi untuk operasi salinan memori masih lambat karena seseorang hanya membaca nilai, menulis nilai di suatu tempat, dan tidak pernah membaca nilai. lagi ... tidak ada cache hit, mati lambat (di samping ini dapat terjadi secara paralel karena kita memiliki eksekusi yang tidak sesuai pesanan).

Salinan memori ini sangat penting sehingga ada berbagai cara untuk mempercepatnya. Pada masa-masa awal, memori sering dapat menyalin memori di luar CPU. Itu ditangani oleh pengontrol memori secara langsung, sehingga operasi penyalinan memori tidak mencemari cache.

Tetapi selain dari salinan memori biasa, akses serial lainnya terhadap memori juga cukup umum. Contohnya adalah menganalisis serangkaian informasi. Memiliki array bilangan bulat dan menghitung jumlah, rata-rata, rata-rata, atau bahkan lebih sederhana, menemukan nilai tertentu (filter / pencarian) adalah kelas algoritma yang sangat penting yang dijalankan setiap saat pada CPU tujuan umum.

Jadi dengan menganalisis pola akses memori, jelas bahwa data dibaca berurutan sangat sering. Ada probabilitas tinggi bahwa jika suatu program membaca nilai pada indeks i, maka program tersebut juga akan membaca nilai i +1. Probabilitas ini sedikit lebih tinggi daripada probabilitas bahwa program yang sama juga akan membaca nilai i + 2 dan seterusnya.

Jadi diberi alamat memori itu (dan masih) adalah ide yang bagus untuk membaca dan mengambil nilai tambahan. Ini adalah alasan mengapa ada mode boost.

Akses memori dalam mode boost berarti, bahwa suatu alamat dikirimkan dan beberapa nilai dikirimkan secara berurutan. Setiap pengiriman nilai tambahan hanya membutuhkan sekitar 10ns tambahan (atau bahkan di bawah).

Masalah lain adalah alamat. Mengirim alamat membutuhkan waktu. Untuk menangani sebagian besar memori, alamat besar harus dikirim. Pada hari-hari awal itu berarti bahwa bus alamat tidak cukup besar untuk mengirim alamat dalam satu siklus (centang) dan lebih dari satu siklus diperlukan untuk mengirim alamat menambahkan lebih banyak penundaan.

Misalnya, cache line 64 byte berarti memori dibagi dalam blok memori yang berbeda (tidak tumpang tindih) yang berukuran 64bytes. 64bytes berarti alamat awal setiap blok memiliki enam bit alamat terendah yang selalu nol. Jadi mengirim enam bit nol ini setiap kali tidak diperlukan meningkatkan ruang alamat 64 kali untuk sejumlah lebar bus alamat (efek selamat datang).

Masalah lain yang dipecahkan oleh baris cache (di samping membaca di depan dan menyimpan / membebaskan enam bit pada bus alamat) adalah cara mengatur cache. Sebagai contoh jika cache akan dibagi dalam 8 byte (64bit) blok (sel) seseorang perlu menyimpan alamat sel memori sel cache ini menyimpan nilai untuk bersama dengannya. Jika alamatnya juga 64bit, ini berarti bahwa setengah ukuran cache dikonsumsi oleh alamat yang menghasilkan overhead 100%.

Karena garis cache adalah 64bytes dan CPU mungkin menggunakan 64bit - 6bit = 58bit (tidak perlu menyimpan bit nol terlalu kanan) berarti kita dapat melakukan cache 64bytes atau 512bits dengan overhead 58bit (overhead 11%). Pada kenyataannya alamat yang disimpan bahkan lebih kecil dari ini tetapi ada informasi status (seperti apakah garis cache valid dan akurat, kotor dan perlu ditulis kembali dalam ram dll).

Aspek lain adalah bahwa kita memiliki cache set-asosiatif. Tidak setiap sel cache dapat menyimpan alamat tertentu tetapi hanya sebagian dari mereka. Ini membuat bit alamat tersimpan yang diperlukan menjadi lebih kecil, memungkinkan akses paralel cache (setiap subset dapat diakses satu kali tetapi tidak tergantung pada subset lainnya).

Ada lebih khusus ketika datang untuk menyinkronkan cache / akses memori antara core virtual yang berbeda, beberapa unit pemrosesan independen per inti dan akhirnya beberapa prosesor pada satu mainboard (yang ada papan perumahan sebanyak 48 prosesor dan banyak lagi).

Ini pada dasarnya adalah ide saat ini mengapa kita memiliki garis cache. Manfaat membaca di depan sangat tinggi dan kasus terburuk membaca byte tunggal dari cache-line dan tidak pernah membaca sisanya lagi sangat tipis karena probabilitasnya sangat tipis.

Ukuran cache-line (64) adalah pilihan trade-off yang dipilih secara bijak antara cache-line yang lebih besar membuatnya tidak mungkin untuk byte terakhir dari itu dibaca juga dalam waktu dekat, durasi yang diperlukan untuk mengambil garis cache lengkap dari memori (dan untuk menulisnya kembali) dan juga overhead dalam organisasi cache dan paralelisasi cache dan akses memori.

Prosesor mungkin memiliki cache multi-level (L1, L2, L3), dan ini berbeda pada ukuran dan kecepatan.

Namun, untuk memahami apa yang sebenarnya masuk ke setiap cache Anda harus mempelajari prediktor cabang yang digunakan oleh prosesor spesifik itu, dan bagaimana instruksi / data program Anda berperilaku menentangnya.

Baca tentang prediktor cabang , cache CPU dan kebijakan penggantian .

Ini bukan tugas yang mudah. Jika pada akhirnya Anda hanya menginginkan tes kinerja, Anda dapat menggunakan alat seperti Cachegrind . Namun, karena ini adalah simulasi, hasilnya mungkin berbeda pada tingkat tertentu.

Saya tidak bisa mengatakan dengan pasti karena setiap perangkat keras berbeda, tetapi biasanya "64 byte mulai dari batas 64 byte terdekat di bawah" karena itu adalah operasi yang sangat cepat dan sederhana untuk CPU.