Bagaimana cache bisa secepat itu?

Berikut ini adalah screenshot dari tolok ukur cache:

Dalam benchmark, kecepatan baca cache L1 adalah sekitar 186 GB / s, dengan latensi sekitar 3-4 siklus clock. Bagaimana kecepatan seperti itu bahkan dicapai?

Pertimbangkan memori di sini: kecepatan maksimum teoritis adalah 665 MHz (frekuensi memori) x 2 (kecepatan data ganda) x 64 bit (lebar bus) yaitu sekitar 10,6 GB / s, yang lebih dekat dengan nilai patokan 9,6 GB / s .

Tetapi dengan cache L1, bahkan jika kita bisa membaca di setiap siklus dengan prosesor pada frekuensi maksimum (3 GHz), kita akan membutuhkan sekitar 496 jalur data untuk mencapai throughput yang terdengar tidak realistis. Ini berlaku untuk cache lainnya juga.

Apa yang saya lewatkan? Bagaimana kita menghitung throughput cache dari parameternya?

CPU ini memiliki ...

2 core Sebuah instruksi 32-KB dan cache level pertama data (L1) 32-KB untuk setiap core

Karena ada dua inti, kita dapat mengharapkan patokan menjalankan dua utas secara paralel. Situs web mereka memberikan sedikit informasi, tetapi jika kita lihat di sini , CPU dengan core lebih banyak tampaknya memberikan throughput L1 yang lebih tinggi. Jadi saya pikir apa yang ditampilkan adalah total throughput dengan semua core bekerja secara paralel. Jadi, untuk CPU Anda, kami harus membaginya dengan dua untuk satu inti dan satu cache:

Read   93 GB/s
Write  47 GB/s
Copy   90 GB/s

Sekarang, fakta "menyalin" 2x lebih cepat dari "menulis" sangat mencurigakan. Bagaimana bisa menyalin lebih cepat daripada yang bisa ditulis? Saya akan bertaruh bahwa apa yang ditampilkan oleh benchmark sebagai "copy" adalah jumlah dari read + write throughput, dan dalam hal ini keduanya akan membaca dan menulis pada 45 GB / s, tetapi menampilkan 90, karena itu adalah benchmark, dan siapa yang percaya tolok ukur? Jadi mari kita abaikan "copy".

Read   93 GB/s => 30 bytes/clock
Write  47 GB/s => 15 bytes/clock

Sekarang, satu register 128-bit adalah 16 byte, cukup dekat, sehingga sepertinya cache ini dapat melakukan dua pembacaan 128-bit dan satu penulisan per jam.

Inilah tepatnya yang Anda ingin benar-benar merampingkan instruksi penguraian angka SSE: dua membaca dan satu menulis per siklus.

Ini kemungkinan besar akan diimplementasikan dengan banyak jalur data paralel, yang merupakan cara biasa untuk mengangkut banyak data dengan sangat cepat di dalam sebuah chip.

Jawaban @ peufeu menunjukkan bahwa ini adalah bandwidth agregat seluruh sistem. L1 dan L2 adalah cache pribadi per-inti dalam keluarga Intel Sandybridge, sehingga jumlahnya 2x apa yang dapat dilakukan oleh satu inti. Tapi itu masih membuat kita dengan bandwidth yang sangat tinggi, dan latensi rendah.

Cache L1D dibangun tepat ke inti CPU, dan sangat erat dengan unit eksekusi beban (dan buffer toko) . Demikian pula, cache L1I tepat di sebelah instruksi mengambil / mendekodekan bagian inti. (Saya sebenarnya belum melihat floorplan silikon Sandybridge, jadi ini mungkin tidak benar secara harfiah. Masalah / mengganti nama bagian dari front-end mungkin lebih dekat dengan "L0" cache cache yang diterjemahkan, yang menghemat daya dan memiliki bandwidth yang lebih baik dari pada decoder.)

Tetapi dengan L1 cache, bahkan jika kita bisa membaca di setiap siklus ...

Kenapa berhenti di situ? Intel sejak Sandybridge dan AMD sejak K8 dapat mengeksekusi 2 beban per siklus. Tembolok multi-port dan TLB adalah suatu hal.

Tulisan mikroarsitektur Sandybridge milik David Kanter memiliki diagram yang bagus (yang juga berlaku untuk CPU IvyBridge Anda):

("Unified scheduler" menahan ALU dan memory uops menunggu input mereka siap, dan / atau menunggu port eksekusi mereka. (Mis. vmovdqa ymm0, [rdi]Menerjemahkan ke load uop yang harus menunggu rdijika sebelumnya add rdi,32belum dieksekusi, untuk contoh). Intel menjadwalkan uops ke port pada masalah / mengubah nama waktu . Diagram ini hanya menunjukkan port eksekusi untuk memori uops, tetapi ALU yang tidak dieksekusi juga bersaing untuk itu. Tahap masalah / ganti nama menambahkan uops ke ROB dan penjadwal Mereka tetap berada di ROB hingga pensiun, tetapi hanya dalam penjadwal hingga mengirim ke port eksekusi (Ini adalah terminologi Intel; orang lain menggunakan masalah dan mengirim berbeda)). AMD menggunakan penjadwal terpisah untuk integer / FP, tetapi mode pengalamatan selalu menggunakan register integer

Seperti yang ditunjukkan, hanya ada 2 port AGU (unit pembangkit alamat, yang mengambil mode pengalamatan seperti [rdi + rdx*4 + 1024]dan menghasilkan alamat linear). Ia dapat menjalankan 2 ops memori per jam (masing-masing 128b / 16 byte), hingga salah satunya menjadi toko.

Tapi ada triknya: SnB / IvB menjalankan 256b AVX memuat / menyimpan sebagai uop tunggal yang membutuhkan 2 siklus dalam port load / store, tetapi hanya membutuhkan AGU pada siklus pertama. Itu memungkinkan uop store-address dijalankan pada AGU pada port 2/3 selama siklus kedua tanpa kehilangan throughput beban. Jadi dengan AVX (yang Intel Pentium / Celeron CPU tidak mendukung: /), SnB / IvB dapat (secara teori) mempertahankan 2 beban dan 1 toko per siklus.

CPU IvyBridge Anda adalah die-shrink dari Sandybridge (dengan beberapa perbaikan mikroarsitektur, seperti mov-elimination , ERMSB (memcpy / memset), dan prefetching perangkat keras halaman berikutnya). Generasi setelah itu (Haswell) menggandakan bandwidth L1D per-jam dengan memperluas jalur data dari unit eksekusi ke L1 dari 128b menjadi 256b sehingga beban AVX 256b dapat mempertahankan 2 per jam. Itu juga menambahkan port AGU toko tambahan untuk mode pengalamatan sederhana.

Puncak throughput Haswell / Skylake adalah 96 byte dimuat + disimpan per jam, tetapi manual optimasi Intel menunjukkan bahwa throughput berkelanjutan Skylake rata-rata (masih dengan asumsi tidak ada kehilangan L1D atau TLB) adalah ~ 81B per siklus. (Lingkaran bilangan skalar dapat menopang 2 beban + 1 toko per jam menurut pengujian saya di SKL, menjalankan 7 (domain tidak terpakai) uops per jam dari 4 domain domain menyatu. Tetapi agak melambat dengan operan 64-bit alih-alih 32-bit, jadi ternyata ada beberapa batasan sumber daya mikroarsitektur dan itu bukan hanya masalah penjadwalan toko-alamat uops ke port 2/3 dan mencuri siklus dari banyak.)

Bagaimana kita menghitung throughput cache dari parameternya?

Anda tidak bisa, kecuali parameternya menyertakan angka throughput praktis. Seperti disebutkan di atas, bahkan Skylake's L1D tidak bisa mengimbangi unit eksekusi load / store untuk 256b vektor. Meskipun dekat, dan bisa untuk bilangan bulat 32-bit. (Tidak masuk akal untuk memiliki lebih banyak unit muat daripada cache membaca port, atau sebaliknya. Anda hanya akan meninggalkan perangkat keras yang tidak pernah dapat sepenuhnya digunakan. Perhatikan bahwa L1D mungkin memiliki port tambahan untuk mengirim / menerima saluran ke / dari core lain, serta untuk membaca / menulis dari dalam inti.)

Hanya dengan melihat lebar bus data dan jam tidak memberi Anda keseluruhan cerita. Bandwidth L2 dan L3 (dan memori) dapat dibatasi oleh jumlah kesalahan luar biasa yang dapat dilacak L1 atau L2 . Bandwidth tidak dapat melebihi latensi * max_concurrency, dan chip dengan L3 latensi lebih tinggi (seperti Xeon banyak-inti) memiliki bandwidth L3 inti-tunggal jauh lebih sedikit daripada CPU dual / quad core dari mikroarsitektur yang sama. Lihat bagian "platform terikat latensi" pada jawaban SO ini . CPU Sandybridge-family memiliki 10 buffer line-fill untuk melacak kesalahan L1D (juga digunakan oleh toko NT).

(L3 / memori bandwidth agregat dengan banyak core aktif sangat besar pada Xeon besar, tetapi kode single-threaded melihat bandwidth lebih buruk daripada pada quad core pada kecepatan clock yang sama karena lebih banyak core berarti lebih banyak pemberhentian di ring bus, dan dengan demikian lebih tinggi latensi L3.)

Latensi cache

Bagaimana kecepatan seperti itu bahkan dicapai?

Latensi penggunaan cache 4 siklus L1D cukup menakjubkan , terutama mengingat bahwa ia harus dimulai dengan mode pengalamatan seperti [rsi + 32], sehingga harus melakukan penambahan sebelum bahkan memiliki alamat virtual . Maka harus menerjemahkannya ke fisik untuk memeriksa tag cache untuk kecocokan.

(Mengatasi mode selain [base + 0-2047]mengambil siklus tambahan pada Intel Sandybridge-family, jadi ada jalan pintas di AGU untuk mode pengalamatan sederhana (tipikal untuk kasus pengejaran pointer di mana latensi penggunaan beban rendah mungkin paling penting, tetapi juga umum pada umumnya) (Lihat manual pengoptimalan Intel , Sandybridge bagian 2.3.5.2 L1 DCache.) Ini juga mengasumsikan tidak ada pengesampingan segmen, dan alamat basis segmen 0, yang merupakan hal normal.)

Itu juga harus menyelidiki buffer toko untuk melihat apakah itu tumpang tindih dengan toko sebelumnya. Dan itu harus mencari tahu ini bahkan jika sebelumnya (dalam urutan program) toko-address uop belum dieksekusi, jadi alamat toko tidak diketahui. Tetapi mungkin ini bisa terjadi secara paralel dengan memeriksa hit L1D. Jika ternyata data L1D tidak diperlukan karena store-forwarding dapat menyediakan data dari buffer toko, maka itu bukan kerugian.

Intel menggunakan cache VIPT (Virtually Indexed Physically Tagged) seperti hampir semua orang, menggunakan trik standar untuk memiliki cache yang cukup kecil dan dengan asosiasi yang cukup tinggi sehingga berperilaku seperti cache PIPT (tanpa alias) dengan kecepatan VIPT (dapat mengindeks dalam sejajar dengan virtual-> TLB fisik lookup).

Cache Intel L1 adalah 32kiB, asosiatif 8 arah. Ukuran halaman adalah 4kiB. Ini berarti bit "index" (yang memilih 8 cara mana yang bisa men-cache setiap baris yang diberikan) semuanya di bawah halaman offset; yaitu bit alamat tersebut adalah offset ke halaman, dan selalu sama di alamat virtual dan fisik.

Untuk detail lebih lanjut tentang itu dan detail lain mengapa cache kecil / cepat bermanfaat / mungkin (dan berfungsi dengan baik ketika dipasangkan dengan cache lebih lambat yang lebih besar), lihat jawaban saya tentang mengapa L1D lebih kecil / lebih cepat daripada L2 .

Tembolok kecil dapat melakukan hal-hal yang akan terlalu mahal daya dalam tembolok yang lebih besar, seperti mengambil array data dari set pada saat yang sama dengan mengambil tag. Jadi, begitu pembanding menemukan tag mana yang cocok, itu hanya harus mux salah satu dari delapan baris cache 64-byte yang sudah diambil dari SRAM.

(Ini tidak sesederhana itu: Sandybridge / Ivybridge menggunakan cache L1D yang dibelokkan, dengan delapan bank potongan 16 byte. Anda bisa mendapatkan konflik bank-cache jika dua akses ke bank yang sama di baris cache yang berbeda coba dieksekusi dalam siklus yang sama. (Ada 8 bank, jadi ini bisa terjadi dengan alamat kelipatan 128 terpisah, yaitu 2 baris cache.)

IvyBridge juga tidak memiliki penalti untuk akses yang tidak selaras asalkan tidak melewati batas cache-line 64B. Saya kira itu menentukan bank mana yang harus diambil berdasarkan bit alamat rendah, dan mengatur perubahan apa pun yang perlu terjadi untuk mendapatkan 1 hingga 16 byte data yang benar.

Pada pemisahan cache-line, itu masih hanya satu uop, tetapi melakukan beberapa akses cache. Hukumannya masih kecil, kecuali pada split 4k. Skylake bahkan membuat pemecahan 4k cukup murah, dengan latensi sekitar 11 siklus, sama seperti split cache-line normal dengan mode pengalamatan yang kompleks. Tetapi throughput 4k-split secara signifikan lebih buruk daripada cl-split non-split.

Sumber :

• Artikel microarch David Kanter SnB (dengan diagram yang sangat bagus, dan lebih fokus pada desain uarch daripada cara mengoptimalkannya).
• Manual optimasi Intel
• Pdf microarch Agner Fog (dan tabel instruksi dan panduan pengoptimalan).
• Tag wiki x86 SO untuk tautan ke tautan ini dan lainnya.

Pada CPU modern, memori cache berada tepat di sebelah CPU pada die (chip) yang sama , dibuat menggunakan SRAM yang jauh, jauh lebih cepat daripada DRAM yang digunakan untuk modul RAM pada PC.

Per unit memori (sedikit atau byte) SRAM jauh lebih mahal daripada DRAM. Jadi itu sebabnya DRAM digunakan di PC juga.

Tetapi karena SRAM dibuat dalam teknologi yang sama dengan CPU itu sendiri, itu secepat CPU. Juga, hanya ada bus internal (pada CPU) yang harus ditangani sehingga jika perlu 496 jalur lebar bus maka mungkin itu.

Cache L1 adalah struktur memori yang cukup lebar. Arsitektur cache L1 dalam prosesor Intel dapat ditemukan di manual ini (disediakan oleh hack-berikutnya). Namun, interpretasi beberapa parameter tidak benar, "ukuran garis cache" bukan "lebar data", itu adalah ukuran blok serial akses data atom.

Tabel 2-17 (bagian 2.3.5.1) menunjukkan bahwa pada beban (dibaca), bandwidth cache adalah 2x16 = 32 Bytes per core per CYCLE . Ini saja memberikan bandwidth teoretis 96 Gb / s pada inti 3GHz. Tidak jelas apa yang dikutip dari laporan benchmark, sepertinya mengukur dua core yang bekerja secara paralel, sehingga menghasilkan 192 Gbps untuk dua core.

Gerbang penundaan apa? 10 picoseconds? Waktu siklus untuk seluruh operasi jaringan pipa adalah 333 picoseconds, dengan berbagai kegiatan decoding dan bus dan pengambilan data flip-flop sebelum siklus clock berikutnya dimulai.

Saya berharap aktivitas paling lambat dalam membaca cache sedang menunggu dataline untuk bergerak cukup jauh terpisah (kemungkinan ini adalah diferensial: satu referensi dan satu biaya aktual dari read-bit) bahwa pembanding / kait dapat clock untuk menerapkan positif- aksi umpan balik untuk mengubah tegangan kecil menjadi ayunan tegangan level logika rail-to-rail yang besar (sekitar 1 volt).