Cache prosesor menjaga memory yang baru digunakan tetap dekat dengan execution core, tetapi kapasitas cache saja tidak menentukan data mana yang dapat tetap resident. Sebagian besar cache CPU general-purpose membagi storage menjadi sejumlah set dan memberi setiap set jumlah slot tetap yang biasa disebut way.

Satu blok memory dipetakan ke set tertentu. Blok itu dapat menempati way mana pun di dalam set tersebut, tetapi tidak dapat berpindah ke set lain hanya karena set lain memiliki slot kosong. Aturan penempatan ini membuat lookup hardware praktis dan cepat, sekaligus menciptakan sumber miss tersendiri ketika terlalu banyak blok aktif bersaing pada set yang sama.

Perilaku inilah yang disebut cache associativity. Ia menghubungkan pemetaan alamat, replacement policy, dan pola akses workload dengan performa.

Cache line adalah unit penempatan

Cache CPU memindahkan dan melacak memory dalam blok berukuran tetap yang disebut cache line. Ukuran line yang umum adalah 64 byte, meskipun ukuran persisnya merupakan properti arsitektur.

Ketika kode membaca satu byte yang tidak ada di cache, hardware biasanya mengambil seluruh line yang memuat byte tersebut. Byte di sekitarnya ikut masuk. Granularitas spasial ini berarti penempatan cache bekerja berdasarkan alamat line, bukan alamat setiap byte.

Alamat line yang disederhanakan adalah

line_address = memory_address / line_size

Cache kemudian menggunakan sebagian dari alamat line tersebut untuk memilih set. Bit identitas yang tersisa disimpan sebagai tag sehingga hardware dapat mengetahui blok memory mana yang sedang menempati suatu way.

Jumlah set dan way membagi kapasitas total

Pertimbangkan cache 32 KiB dengan line 64 byte dan delapan way. Totalnya memiliki 512 slot line:

32768 / 64 = 512 lines

Dengan delapan way per set, cache tersebut memiliki 64 set:

512 / 8 = 64 sets

Setiap memory line dipetakan ke salah satu dari 64 set tersebut. Di dalam set yang dipilih, line itu memiliki delapan kemungkinan slot.

Kapasitas total yang sama dapat diorganisasi secara berbeda. Cache direct-mapped memiliki satu way per set. Cache fully associative mengizinkan line menempati slot mana pun. Desain set-associative berada di antara dua ekstrem tersebut.

Lebih banyak way memberi fleksibilitas penempatan lebih besar, tetapi juga mengharuskan hardware membandingkan lebih banyak candidate tag dan memilih di antara lebih banyak line resident.

Banyak alamat dapat bersaing pada satu set

Untuk organisasi cache sederhana dengan ukuran berbasis pangkat dua, pemilihan set secara konseptual dapat ditulis sebagai

set = line_address mod number_of_sets

Prosesor nyata dapat menerapkan teknik indexing tambahan, terutama pada cache yang lebih besar atau shared, sehingga rumus ini adalah model, bukan aturan implementasi universal.

Model tersebut tetap memperlihatkan efek intinya. Jika beberapa memory line aktif menghasilkan set index yang sama, semuanya bersaing untuk way pada set itu.

Dalam contoh delapan way, delapan line yang bersaing dapat tinggal bersama. Mengakses line berbeda kesembilan yang dipetakan ke set yang sama mengharuskan satu victim diganti, meskipun banyak slot di set lain belum digunakan.

Akses berikutnya ke line yang ter-evict kemudian menghasilkan miss dan harus mengambilnya dari cache level lain atau lokasi lain di memory hierarchy.

Conflict miss dapat muncul sebelum kapasitas nominal penuh

Sebuah working set dapat lebih kecil daripada kapasitas cache yang diiklankan tetapi tetap sering mengalami miss. Kondisi yang relevan bukan hanya jumlah byte total. Distribusi antar-set juga penting.

Misalkan sebuah loop berulang kali mengakses sembilan line yang semuanya dipetakan ke satu set pada cache delapan way. Data aktifnya hanya berukuran 576 byte:

9 * 64 = 576 bytes

Namun sembilan line tersebut tidak dapat semuanya resident pada set yang sama secara bersamaan. Bergantung pada urutan akses dan perilaku replacement, loop dapat terus meng-evict data yang sebentar lagi akan diminta lagi.

Ini adalah pola conflict. Ia berbeda dari capacity miss murni, ketika data aktif memang melebihi seluruh storage cache yang dapat digunakan.

Associativity yang lebih tinggi mengurangi banyak pola conflict karena setiap set dapat mempertahankan lebih banyak line yang bersaing. Namun ia tidak menghilangkan kapasitas yang terbatas atau menjamin setiap pola akses tetap resident.

Replacement policy menentukan way yang dibebaskan

Ketika sebuah set penuh dan line baru datang, cache perlu memilih victim. Penjelasan buku teks sering memakai least recently used replacement, tetapi implementasi prosesor dapat memakai pendekatan perkiraan atau policy lain yang menekan biaya hardware atau meningkatkan perilaku pada workload umum.

Replacement policy penting karena associativity hanya menentukan berapa banyak slot candidate yang tersedia. Ia tidak menentukan line resident mana yang dibuang.

Dua prosesor dengan ukuran cache, line size, dan associativity yang sama karena itu dapat bereaksi berbeda terhadap urutan akses yang sama bila mekanisme replacement-nya berbeda. Prefetching dan policy cache inclusivity juga dapat mengubah hasil yang terlihat.

Untuk analisis performa, associativity adalah satu faktor struktural, bukan model cache yang lengkap.

Stride dapat memusatkan tekanan pada set tertentu

Akses array yang teratur dapat memperlihatkan efek pemetaan set. Jika alamat berturut-turut dipisahkan oleh stride yang berulang kali memilih kelompok set kecil yang sama, cache besar dapat digunakan secara tidak merata.

Pada contoh sederhana 64 set dan line 64 byte, alamat yang berjarak 4096 byte berbeda sebanyak 64 cache line:

4096 / 64 = 64 lines

Dengan pemetaan modulo sederhana, line tersebut memilih set yang sama. Mengakses cukup banyak lokasi seperti itu berulang kali dapat melampaui jumlah way yang tersedia.

Mengubah layout data, padding, urutan traversal, atau allocation alignment dapat mengubah set mana yang menerima tekanan. Perubahan seperti ini spesifik terhadap workload dan sebaiknya diukur, bukan diterapkan secara mekanis.

Address hashing modern, detail virtual indexing, prefetcher, dan banyak level cache dapat membuat perilaku fisik lebih rumit daripada contoh sederhana tersebut.

Associativity yang lebih tinggi memiliki biaya hardware

Cache satu way hanya perlu memeriksa satu candidate tag setelah memilih set. Cache N-way mungkin perlu menentukan mana dari N candidate tag yang cocok dengan alamat yang diminta.

Associativity lebih tinggi dapat mengurangi conflict miss, tetapi way tambahan meningkatkan pekerjaan perbandingan tag dan kompleksitas replacement state. Perancang menyeimbangkan hit rate, access latency, energi, area, dan timing implementasi.

Trade-off ini membantu menjelaskan mengapa set associativity moderat umum digunakan alih-alih membuat setiap cache fully associative. Kebebasan penempatan penuh menarik dari sisi miss, tetapi mencari di antara banyak kemungkinan entry pada kecepatan cache CPU mahal.

Setiap level cache dapat memakai associativity berbeda karena ukuran, target latency, model sharing, dan perannya dalam hierarchy juga berbeda.

Kapasitas, line size, dan associativity menjelaskan properti yang berbeda

Spesifikasi cache sering menuliskan kapasitas terlebih dahulu, tetapi tiga nilai ini menjawab pertanyaan berbeda:

  • Kapasitas menyatakan total storage data yang tersedia.
  • Line size menyatakan granularitas transfer dan penempatan.
  • Associativity menyatakan jumlah slot yang tersedia di dalam set yang dipilih.

Cache yang lebih besar tetap dapat mengalami conflict yang terkonsentrasi. Cache dengan lebih banyak way tetap dapat terlalu kecil untuk working set. Line yang lebih besar dapat meningkatkan spatial reuse untuk data berurutan sekaligus membuang bandwidth dan kapasitas ketika byte di sekitarnya tidak digunakan.

Analisis performa membutuhkan pola akses bersama properti struktural tersebut.

Pengukuran perlu memvariasikan layout, bukan hanya ukuran data

Benchmark yang hanya menyapu ukuran working set dapat menunjukkan transisi antar-level cache, tetapi dapat melewatkan sensitivitas terhadap penempatan. Menguji stride, alignment, dan layout data yang berbeda dapat memperlihatkan efek conflict.

Hardware performance counter dapat memberikan data cache reference dan cache miss, bergantung pada event yang diekspos prosesor. Pengukuran waktu atas pola akses berulang juga dapat menunjukkan perubahan tajam ketika jumlah line yang bersaing melampaui effective residency sebuah set.

Microbenchmark perlu hati-hati. Optimisasi compiler, prefetching, out-of-order execution, translation cache, page placement, dan measurement overhead semuanya dapat memengaruhi hasil.

Kesimpulan strukturalnya adalah byte cache dipartisi oleh aturan penempatan. Sebuah line hanya memiliki sejumlah tempat yang mungkin, dan persaingan berat pada tempat tersebut dapat memaksa replacement sebelum cache secara global penuh.

CPU Cache Memori Performa