Simulasi Cache

Tingkat miss suatu pola akses tidak perlu ditebak, karena aturan penempatan dan penggantian cache dapat ditiru dalam program kecil yang mencatat setiap keputusannya. Topik ini membangun simulator cache untuk dua organisasi, yaitu direct-mapped dan 2-way dengan penggantian LRU, lalu mengukurnya terhadap tiga pola akses yang berbeda. Keluaran simulator menjadi bukti terukur bahwa pola akses dan organisasi cache sama-sama menentukan tingkat hit.

Tiga pola akses yang diuji#

Simulator menerima urutan alamat byte yang dituliskan langsung di dalam kode, bukan masukan dari pengguna, sehingga hasilnya selalu dapat dihitung ulang. Tiga pola yang dipakai mewakili perilaku yang berbeda dan masing-masing menuntut sifat cache yang berbeda pula.

Pola pertama menguji apakah cache mampu menyimpan seluruh data 1 KiB antara dua putaran, dan jawabannya bergantung pada organisasi. Pola kedua menampakkan manfaat line 64 byte, karena tiga dari setiap empat akses berada pada line yang sudah tertarik. Pola ketiga bekerja pada data yang muat dengan nyaman, sehingga menjadi pembanding ketika miss hampir tidak muncul. Istilah lokalitas temporal (temporal locality) yang dipakai pada tabel adalah kecenderungan mengakses ulang data yang baru saja dipakai, sebagai pasangan dari lokalitas spasial pada topik anatomi cache.

Simulator direct-mapped dan 2-way LRU#

Satu fungsi jalankan melayani kedua organisasi, karena perbedaannya hanya terletak pada jumlah line per set. Setiap set dimodelkan sebagai daftar tag yang terurut dari yang terlama sampai yang terbaru. Akses yang menemukan tagnya memindahkan tag itu ke ujung terbaru, sedangkan akses yang miss membuang tag terlama apabila set sudah penuh.

# Simulator cache sederhana untuk dua organisasi: direct-mapped dan 2-way LRU.
# Alamat berupa byte dengan ukuran line 64 byte dan jumlah set 8.

UKURAN_LINE = 64
JUMLAH_SET = 8

def jalankan(akses, asosiativitas):
    """Kembalikan (hit, miss) untuk satu pola akses dan satu asosiativitas."""
    set_cache = [[] for _ in range(JUMLAH_SET)]  # tiap set: daftar tag urut LRU
    hit = 0
    miss = 0
    for alamat in akses:
        blok = alamat // UKURAN_LINE
        indeks = blok % JUMLAH_SET
        tag = blok // JUMLAH_SET
        baris = set_cache[indeks]
        if tag in baris:
            hit += 1
            baris.remove(tag)  # tag yang dipakai berpindah ke posisi terbaru
            baris.append(tag)
        else:
            miss += 1
            if len(baris) >= asosiativitas:
                baris.pop(0)   # tag yang paling lama tidak dipakai dibuang
            baris.append(tag)
    return hit, miss

def pola_sekuensial():
    """Dua putaran penuh atas data 1 KiB (16 blok)."""
    return [blok * UKURAN_LINE for blok in range(16)] * 2

def pola_langkah():
    """Langkah 16 byte sebanyak 32 akses, yaitu empat akses per line."""
    return [i * 16 for i in range(32)]

def pola_berulang():
    """Empat blok kerja diakses bergantian sebanyak delapan kali."""
    return [blok * UKURAN_LINE for blok in range(4)] * 8

pola = [
    ("sekuensial dua putaran", pola_sekuensial()),
    ("langkah 16 byte", pola_langkah()),
    ("kerja kecil berulang", pola_berulang()),
]

for nama, akses in pola:
    print(f"Pola: {nama} ({len(akses)} akses)")
    for asosiativitas in (1, 2):
        hit, miss = jalankan(akses, asosiativitas)
        tingkat = 100.0 * hit / len(akses)
        org = "direct-mapped" if asosiativitas == 1 else f"{asosiativitas}-way LRU"
        print(f"  {org:14s}: miss {miss:2d}, hit {hit:2d}, tingkat hit {tingkat:.1f}%")
    print()

Pola: sekuensial dua putaran (32 akses)
  direct-mapped : miss 32, hit  0, tingkat hit 0.0%
  2-way LRU     : miss 16, hit 16, tingkat hit 50.0%

Pola: langkah 16 byte (32 akses)
  direct-mapped : miss  8, hit 24, tingkat hit 75.0%
  2-way LRU     : miss  8, hit 24, tingkat hit 75.0%

Pola: kerja kecil berulang (32 akses)
  direct-mapped : miss  4, hit 28, tingkat hit 87.5%
  2-way LRU     : miss  4, hit 28, tingkat hit 87.5%

Kedua organisasi menghitung set dari nomor blok dengan cara yang sama, yaitu blok modulo jumlah set, sehingga perbedaan hasil murni berasal dari jumlah tempat per set. Simulator ini sengaja tidak memodelkan kebijakan penulisan, prefetch, maupun hierarki cache bertingkat, karena pertanyaannya dibatasi pada hit dan miss untuk pola yang diberikan. Penyederhanaan semacam ini lazim untuk analisis pola akses, asalkan kesimpulannya tidak diperluas melampaui yang dimodelkan.

Membaca hasil simulasi#

Hasil pada pola pertama paling informatif. Pada cache direct-mapped, setiap set hanya menampung satu blok, sehingga blok 0 dan blok 8 yang sama-sama masuk ke set 0 saling mengusir selama putaran pertama, dan seluruh putaran kedua pun miss. Cache 2-way menyimpan keduanya sekaligus, sehingga seluruh putaran kedua menjadi hit dan tingkat hitnya mencapai 50 persen. Kontras ini adalah contoh miss konflik yang paling murni.

Pola langkah 16 byte memberikan hasil yang sama pada kedua organisasi, yaitu 8 miss dan 24 hit. Setiap line yang tertarik melayani empat akses, dan tidak ada set yang menerima tekanan lebih dari satu blok pada satu waktu, sehingga asosiativitas tidak ikut berperan. Pola kerja kecil berulang juga serupa, karena empat blok kerjanya masuk ke empat set yang berbeda tanpa saling mengusir. Tingkat hit 87,5 persen pada pola ini berasal murni dari lokalitas temporal berjarak pendek.

Ketiga pola menunjukkan bahwa tingkat hit bukan milik data semata, melainkan milik pasangan pola dan organisasi. Data yang sama dapat memberi tingkat hit 0 persen atau 50 persen hanya karena satu sifat struktur cache berubah. Karena itu, kesimpulan performa selalu harus menyebut keduanya.

Perlu dicatat pula bahwa tingkat hit bukan satu-satunya penentu kecepatan. Dua cache dengan tingkat hit yang sama dapat berbeda hasil apabila waktu hit dan penalti missnya berbeda, misalnya cache yang lebih besar biasanya lebih lambat saat hit. Rumus AMAT memberi kerangka untuk menimbang keduanya, yaitu mengalikan tingkat miss dengan penaltinya sebelum menyimpulkan bahwa sebuah desain lebih baik dari desain lain.

Kesalahan umum#

Tiga kekeliruan berikut paling sering muncul ketika hasil simulasi cache dinilai.

1. Melaporkan tingkat hit tanpa konfigurasi cache. Angka 50 persen tanpa keterangan ukuran line, jumlah set, dan asosiativitas tidak dapat dibandingkan dengan apa pun. Perbaikannya adalah mencantumkan konfigurasi lengkap bersama hasilnya.
2. Menggeneralisasi dari satu pola. Pola langkah memberi hasil yang sama untuk dua organisasi pada simulasi ini, sedangkan pola sekuensial memisahkannya dengan tajam. Perbaikannya adalah menguji beberapa pola yang mewakili beban kerja sungguhan.
3. Menganggap LRU selalu pilihan terbaik. LRU hanyalah heuristik yang murah diimplementasikan, dan pola tertentu dapat membuat pilihannya buruk. Perbaikannya adalah menguji aturan penggantian lain pada simulator sebelum menyimpulkan.

Ringkasan#

• Simulator menghitung hit dan miss dari urutan alamat dengan aturan index dan tag yang sama seperti cache sungguhan.
• LRU dimodelkan sebagai daftar per set, yaitu tag yang dipakai pindah ke ujung terbaru dan tag terlama dibuang saat set penuh.
• Pola sekuensial dua putaran memisahkan organisasi dengan tajam, yaitu 0 persen pada direct-mapped dan 50 persen pada 2-way.
• Pola berbasis lokalitas spasial dan kerja kecil memberi tingkat hit tinggi pada kedua organisasi, sehingga kesimpulan selalu bergantung pada pola.

Referensi#

• Computer Systems: A Programmer’s Perspective — Randal Bryant dan David O’Hallaron — Buku yang membahas simulasi cache, klasifikasi miss, dan pengaruh pola akses terhadap tingkat hit.