Anatomi Cache

Cache tidak menyimpan byte satu per satu, melainkan mengelola isinya dalam satuan tetap dan menempatkannya pada posisi yang ditentukan oleh aturan pemetaan. Topik ini membedah struktur tersebut mulai dari line, pembagian alamat menjadi tag, index, dan offset, tingkat asosiativitas, sampai tiga jenis miss. Setelah topik ini dibaca, satu alamat dapat diurai secara manual menjadi bagian-bagian yang dipakai cache untuk menemukan atau menyimpan data.

Line, satuan penyimpanan cache#

Cache line, yang juga disebut block, adalah satuan tetap yang dipindahkan antara memori utama dan cache, umumnya berukuran 64 byte. Ketika program meminta satu byte, cache tidak menarik byte itu saja, melainkan satu line utuh yang memuatnya. Mekanisme ini mengandalkan lokalitas spasial (spatial locality), yaitu kecenderungan program mengakses alamat yang berdekatan dalam waktu yang berdekatan pula, sehingga byte-byte tetangga yang ikut tertarik biasanya akan dipakai juga.

Ukuran line menentukan bentuk tarik-menarik itu. Line yang besar menyambut program sekuensial dengan hit yang murah, tetapi membawa lebih banyak data yang mungkin tidak terpakai dan mengurangi jumlah line yang tersedia. Line yang kecil bekerja sebaliknya. Nilai 64 byte menjadi pilihan umum karena menyeimbangkan kedua arah tersebut.

Pembagian alamat menjadi tag, index, dan offset#

Untuk mengetahui tempat penyimpanan sebuah alamat, cache membagi alamat menjadi tiga bagian. Bagian offset memilih byte di dalam line, dan jumlah bitnya adalah $\log_2(\text{ukuran line})$. Bagian index memilih set, yaitu kelompok line tempat alamat itu berhak menempati, dengan jumlah bit $\log_2(\text{jumlah set})$. Bagian tag berupa sisa bit tertinggi yang mengenali isi line, karena banyak alamat berbeda berbagi tempat yang sama. Diagram berikut menguraikan ketiga bagian itu untuk alamat 32 bit.

Diagram di atas memakai cache direct-mapped berkapasitas 1 KiB dengan line 64 byte. Ukuran line 64 byte membutuhkan 6 bit offset, kapasitas 1 KiB menghasilkan 16 set yang membutuhkan 4 bit index, dan 22 bit sisanya menjadi tag. Ketiga bagian bekerja serentak pada setiap akses, yaitu index memilih set, tag diperiksa terhadap isi set yang terpilih, dan offset memilih byte di dalam line yang cocok.

Asosiativitas: direct-mapped, k-way, dan fully associative#

Aturan pemetaan dari alamat ke tempat penyimpanan menentukan seberapa bebas cache menaruh line barunya. Tingkat kebebasan itu disebut asosiativitas, dan tiga desainnya menghasilkan karakter performa yang berbeda.

Pada desain k-way, setiap set memuat k line dan pemeriksaan tag dijalankan serentak untuk seluruh isi set. Apabila set yang dituju sudah penuh, satu line harus dikorbankan, dan aturan penggantian yang paling umum adalah LRU (least recently used), yaitu line yang paling lama tidak dipakai yang dibuang. Desain fully associative pada praktiknya hanya dipakai untuk struktur kecil seperti TLB (Translation Lookaside Buffer), yaitu cache kecil yang menyimpan terjemahan alamat, karena membandingkan tag terhadap ribuan line sekaligus tidak ekonomis.

Mengurai alamat dalam Python#

Perhitungan pembagian alamat mudah ditiru dalam program kecil. Skrip berikut mengurai empat alamat 16 bit untuk cache direct-mapped dengan line 16 byte dan 16 set, sehingga offset membutuhkan 4 bit, index membutuhkan 4 bit, dan tag memakai 8 bit sisanya.

# Pembagian alamat 16 bit menjadi tag, index, dan offset.
# Konfigurasi cache: direct-mapped, line 16 byte, dengan 16 set.

UKURAN_LINE = 16  # byte, sehingga bagian offset membutuhkan 4 bit
JUMLAH_SET = 16   # sehingga bagian index membutuhkan 4 bit

BIT_OFFSET = UKURAN_LINE.bit_length() - 1  # 4
BIT_INDEX = JUMLAH_SET.bit_length() - 1    # 4

def urai(alamat):
    """Kembalikan (tag, index, offset) dari satu alamat 16 bit."""
    offset = alamat & (UKURAN_LINE - 1)
    index = (alamat >> BIT_OFFSET) & (JUMLAH_SET - 1)
    tag = alamat >> (BIT_OFFSET + BIT_INDEX)
    return tag, index, offset

for alamat in (0x0004, 0x0044, 0x1044, 0xFFE8):
    tag, index, offset = urai(alamat)
    print(f"alamat 0x{alamat:04X} -> tag 0x{tag:02X}, set {index:2d}, offset {offset:2d}")

alamat 0x0004 -> tag 0x00, set  0, offset  4
alamat 0x0044 -> tag 0x00, set  4, offset  4
alamat 0x1044 -> tag 0x10, set  4, offset  4
alamat 0xFFE8 -> tag 0xFF, set 14, offset  8

Empat baris keluaran itu memuat beberapa informasi penting. Alamat 0x0004 dan 0x0044 berbagi tag 0x00 tetapi masuk ke set yang berbeda, sehingga keduanya tidak saling berebut tempat. Sebaliknya, alamat 0x0044 dan 0x1044 masuk ke set 4 yang sama dengan tag yang berbeda, sehingga keduanya bersaing memperebutkan satu line. Konfigurasi ini sengaja memakai alamat 16 bit agar tag ringkas, sedangkan cara pembagiannya sama persis dengan alamat 32 bit yang lebih panjang.

Tiga jenis miss#

Miss dikelompokkan menjadi tiga jenis menurut penyebabnya. Miss wajib (compulsory miss) terjadi pada akses pertama terhadap sebuah line, dan tidak ada cache yang dapat menghindarinya tanpa bantuan mekanisme seperti prefetch. Miss kapasitas (capacity miss) terjadi karena kerja program lebih besar daripada kapasitas cache, sehingga line yang lama tergeser sebelum sempat dipakai lagi. Miss konflik (conflict miss) terjadi karena beberapa alamat bersaing pada set yang sama, padahal cache masih memiliki tempat kosong di set lain.

Jenis-jenis ini bukan sekadar taksonomi, melainkan panduan perbaikan. Miss konflik ditangani dengan menaikkan asosiativitas atau mengubah tata letak data, sedangkan miss kapasitas baru mereda apabila ukuran kerja atau kapasitas cache bertambah. Miss wajib menurun dengan sendirinya seiring bertambahnya jumlah akses ulang, sehingga proporsi ketiganya selalu bergantung pada pola akses program.

Kesalahan umum#

Tiga kekeliruan berikut paling sering muncul ketika struktur cache baru dipelajari.

1. Menganggap satu byte ditarik sendiri-sendiri. Satuan pemindahan adalah line utuh, sehingga alamat yang berdekatan biasanya dibayar sekali. Perbaikannya adalah menata data yang diakses bersama agar berdekatan.
2. Menukar tugas index dan tag. Index memilih set, sedangkan tag mengenali line di dalam set. Perbaikannya adalah mengingat bahwa dua alamat dengan index yang sama tetap berbeda isi apabila tagnya berbeda.
3. Menilai kapasitas tanpa melihat asosiativitas. Dua cache berkapasitas sama dapat menghasilkan jumlah miss yang jauh berbeda pada pola yang berkonflik. Perbaikannya adalah menyebut ukuran line, jumlah set, dan asosiativitas setiap kali tingkat miss dilaporkan.

Ringkasan#

• Cache memindahkan data dalam satuan line, umumnya 64 byte, dengan mengandalkan lokalitas spasial.
• Alamat terbagi menjadi tag, index, dan offset, dengan offset $\log_2(\text{ukuran line})$ bit dan index $\log_2(\text{jumlah set})$ bit.
• Asosiativitas menentukan kebebasan penempatan, dari direct-mapped yang satu tempat sampai fully associative yang bebas.
• Miss terbagi atas compulsory, capacity, dan conflict, dan setiap jenis menuntut perbaikan yang berbeda.

Referensi#

• Computer Systems: A Programmer’s Perspective — Randal Bryant dan David O’Hallaron — Buku yang membahas anatomi cache, pembagian alamat, dan klasifikasi miss dari sudut pandang pemrogram.