Sistem Operasi – 14 – Memory 2: Caching

Posted on 2023-10-152023-11-05 by Wirabumi Software Posted in Computer Science

This is post 2 of 6 in the series “Sistem Operasi”

Cache adalah komponen perangkat keras atau perangkat lunak yang menyimpan data sehingga permintaan di masa mendatang untuk data tersebut dapat dilayani lebih cepat.

Contents

Sumber Utama

Time seek	Note from CS162 Lecture 14: Memory 2: Virtual Memory (Con’t), Caching and TLBs
1:08:03	Start talk about caching concept (CS61c)
1:12:58	temporal locality and spatial locality
1:20:14	summary on sources of cache misses

Time seek	Note from CS162 Lecture 15: Memory 3: Caching and TLBs (Con’t), Demand Paging
8:40	how block found in a cache
9:20	example of direct mapped cache
12:00	set associative cache
14:30	fully associative cache
19:23	where does a block got placed in a cache?
20:31	which block should be replaced on a miss?
21:43	what happen on a write?
23:18	physically-indexed vs virtually-indexed caches
33:50	what TLB organization make sense?
41:48	current Intel x86 TLB and cache organization
46:05	what happen on a context switch?
47:16	put everything together

Poin-poin Penting

dibuat cache yang memetakan antara virtual address dengan physical address. jika tidak ada di cache (disebut cache misses), maka lakukan address translation → fetch → simpan hasilnya di cache. di cycle berikutnya, jika butuh data di alamat yang sama, tidak perlu translation, langsung ambil dari cache (disebut cache hit).
urutan bagaimana processor mendapatkan value dari sebuah address di address space: processor → TLB → cache → DRAM.
TLB (translation lookaside buffer): terdapat cache yang menyimpan hasil address translation.
- jika virtual address yang diminta processor ternyata ada dalam TLB, maka address translation dilakukan dengan cara me-lookup dari cache-nya TLB.
- jika tidak ada di TLB, maka TLB melakukan address transalation menggunakan page table. hasil translation akan disimpan pada cache-nya TLB, sehingga pada cycle berikutnya jika butuh virtual address yang sama, sudah tidak perlu melakukan address translation, cukup look-up dari cache-nya TLB.
cache performance dihitung dengan Average Memory Access Time (AMAT) = (hit rate x hit time) + (miss rate x miss time), dimana hit rate + miss rate = 1.
Dengan multi-level cache, untuk context switching (sistem operasi menyatakan thread sleep dan pindah ke thread lain), maka cukup menyimpan 1 PageTablePtr register saja, dimana PageTablePtr ini mewakili page table di level berikutnya, sehingga tidak perlu simpan semua sebagaimana pada metode base-and-bound. cukup simpan CR3 (PTE Page Table Entry disimpan di register CR3), sudah cukup untuk menyimpan state DRAM.
Apa implementasi cache yg paling cepat?
- Direct mapped cache adalah cache paling cepat karena desain hardware yang paling sederhana, karena tidak butuh multi level access sebagaimana two/fully associative cache.
- fully associative cache juga membutuhkan speed yang sangat besar, sedangkan dalam skala chip, ukuran (propagation speed) sangat berperan dalam performance.
- sebagai trade-off, modern processor menggabungkan antara direct mapped cache dengan fully associative cache, membentuk n-way associative cache. Sebagai contoh Ryzen 5 5600H., memiliki 384 KiB L1 cache in total, 8-way set associative. (referensi disini).
Apa replacement policy yang performanya paling baik (miss rate paling rendah)?
- direct mapped cache → hanya ada 1 kemungkinan, tinggal replace saja.
- N-way associative → ada N kemungkinan. LRU menunjukkan miss rate yg lebih rendah dari pada random, dan ukuran cache yg lebih tinggu menunjukkan miss rate yang lebih rendah.

Latar Belakang

akses 1 memory address, butuh 3x akses memory address (karena melewati 4 level page table translation)
reference locality probability.
- temporal locality: kita berasumsi jika instruction/data yang sama dipakai berulang ulang. milsanya loop i=0 sampai i=100, maka 100 akan dipakai berulang-ulang, begitu juga instruction i=100 juga dipakai berulang ulang.
- spatial locality: kita berasumsi jika next instruction/data, ada disekitar current instruction/data. contoh:
  - array, next item ada persis di sebelahnya.
  - stack, next/prev item ada persis di sebelahnya.
  - loop, next instruction ada persis di sebelahnya.

Cache Misses

compulsory (sebuah keharusan), milsanya: program baru saja dimulai, atau pointing untuk pertama kali, atau akses ke memory block untuk pertama kali.
capasity: tidak semua blok memory yang diperlukan muat di dalam cache, solusinya: besarkan ukuran cache.
conflict: beberapa memory location menempati cache location yang sama.
- solusi 1: besarkan ukuran cache, karena memory location bisa menempati cache location sendiri-sendiri.
- solusi 2: tingkatkan associativity. Full associativity memiliki tingkatan tertinggi, dimana memory location dapat menempati cache location mana saja. namun dengan resiko desain hardware yang kompleks.
coherence (invalidation): other process (misalnya: I/O) mengubah isi memory.

Perbandingan kecepatan akses tiap jenis memory

Menghitung performa cache

Semakin besar hit-rate, semakin bagus.

Bagaimana sebuah block dapat dicari dalam cache?

Direct mapped cache

Dalam sistem 32 bit misalnya, maka panjang address pada gambar diatas adalah 32 bit. 5 bit paling kanan (lowest) adalah offset, 5 bit berikutnya adalah index, dan 22 bit terakhir (upper most) adalah tag.

Block adalah ukuran terkecil keluar masuknya cache, misalnya 1 blok 32 byte, maka sekali write pada cache besarnya 32 byte.

Direct Mapped 2^N byte cache

uppermost (32-N) bits adalah cache tag
lowest M bits adalah bit select (block size = 2^M)

Contoh: 1 KB direct mapped cache dengan 32 B blocks. 1 KB = 1024 B = 2¹⁰. N =32-10 = 22. artinya cache tag 2 bits, index dan offset total 10 bit. dengan block size 32 byte, artinya 1 slot (aka block) 32 byte, maka 1kb terdiri dari 32 byte x 32 block. karena ada 32 blok, dimana 32 = 2⁵, maka index terdiri dari 5 bits. Sisa 5 bits untuk byte select, sebagaimana gambar ilustrasi dibawah ini:

Pertama, kita pakai index untuk melokalisir blok nya. misalnya index 0x01, maka blok ke 1 (blok dimulai dari 0) yang dipilih. Kedua, dari cache, ambil cache tag, dan cocokkan dengan request. jika cocok, maka baca byte sesuai dengan byte select. Perhatikan gambar dibawah ini:

Two associative cache

Ada model lain dalam cache layout:

Cache index digunakan untuk membaca pada blok dari cache, yang akan dikeluarkan. Gambar diatas ada 2 bank cache, dua-dua-nya diambil. Kemudian dicari, mana dari 2 bank tadi yang cache tag nya cocok dengan requets. Gambar diatas menunjukkan bank kiri yang cocok, sehingga dengan menggunakan multiplexer hardware, data dari bank kiri dikeluarkan (blocknya ketemu, yaitu sebelah kiri). Layout ini dinamanya 2-way associative cache. Sebagai contoh, AMD dengan arsitektur zen 2, dengan cache L1 32 KB 8-way.

Fully associative cache

Pada contoh kasus sebelumnya, terdapat 2 bank cache. Jika seandainya bank nya cukup banyak, sedemikian hingga tidak lagi diperlukan cache index, dalam kasus ini kita punya 32 bank, maka tag bisa menempati 27 bits long, dan proses untuk menemukan block, cukup dengan mencocokkan tag dari request dengan cache tag, sebagaimana gambar dibawah ini:

Dari ketiga model cache, Direct mapped cache adalah yang paling cepat. Karena direct mapped sangat cepat dari sisi hardware, karena tidak ada multi level access. Badingkan dengan fully associative, meskipun pengecekan 32 cache tag berlangsung parallel, byte select tetap membutuhkan multi level access, dan itu berada dibalik 32x multiplexer. Dalam skala chip, propagation speed (waktu yg dibutuhkan sinyal listrik sampai pada chip untuk di proses), sangat berpengaruh, dan itu tidak instant meski kecepatannya mendekati kecepatan cahaya.

Pada kasus two associative cache, sama dengan fully associative, hanya saja 2x multiplexer, tetap saja direct mapped lebih cepat.

Namun demikian, cache misses karena conflict itu paling jarang terjadi pada fully associative cache, dan cache misses itu ongkos komputasi yang mahal, maka boleh jadi secara aggregate, fully associative cache menjadi yang tercepat.

Sehingga, sebagai trade-off, modern processor menggabungkan antara direct mapped cache dengan fully associative cache, membentuk n-way associative cache. Sebagai contoh Ryzen 5 5600H., memiliki 384 KiB L1 cache in total, 8-way set associative. Ref: https://en.wikichip.org/wiki/amd/ryzen_5/5600h.

Bagaimana sebuah block ditempatkan dalam cache?

Misalnya ada address space sebesar 32 blok, kemudian blok ke-12 ditempatkan dalam cache berukuran 8 blok. Maka:

direct mapped: hanya ada 1 tempat → 12 mod 8 = 4.
two-way associative: kemungkinan ada 2 tempat → 12 mod 4.
fully associative: kemungkinan ada 8 tempat, karena dalam harware ini, semua tempat bisa ditempati.

Blok mana yang akan ditimpa jika terjadi cache misses?

Pada kasus direct mapped cache, hanya ada 1 kemungkinan → mudah.

Pada kasus two-way associative, ada 2 kemungkinan, maka ada beberapa alternatif:

random
LRU (least recently used

Apa yang terjadi jika sebuah block pada cache di-update (write)?

Write through: data ditulis pada cache dan lower-level memory. Misalnya pada address x di cache, valuenya A. kemudian processor merubah isi x menjadi B. maka B ditulis baik pada cache maupun pada lower-level memory.
Write back: data ditulis hanya ada cache saja, belum dilakukan update pada lower-level memory.
- lower-level memory diupdate jika cache block di-relace (berarti ada cache miss, sedemikian hingga TLB harus fetch dari DRAM, dan sedemikian hingga apa yang sudah di fetch harus disimpan di cache, dan menempati block yang ini).
  - ini make-sense, sebab jika prosesor butuh informasi di address x, sementara ada di cache, kan tidak perlu fetch ke DRAM. sehingga DRAM tidak di update juga tidak mengapa. namun ketika block ini di-replace, maka value x di lower level memory harus diupdate, ada kemungkinan valuenya beda antara cache dengan lower level memory, sehingga lowe level memory harus di update, supaya valuenya tetep sinkron dengan cache sebelum cache nya di-replace.