Memori Cache

Memori Cache

Cache memory adalah memori kecepatan tinggi, tetapi berukuran kecil, yang  digunakan untuk menyimpan salinan data / instruksi yang sering diakses oleh CPU.

Cache memory berfungsi menjembatani perbedaan kecepatan antara CPU dan Memori Utama.

Dalam implementasinya jenis memori yang digunakan untuk cache adalah statik RAM (SRAM).

Memori Cache

Operasi Cache

CPU meminta isi suatu lokasi memori

Memeriksa apakah data terdapat di cache

Jika ada di cache, ambil data dari cache (cepat)

Jika tidak ada di cache, copy isi memori ke cache dan kirimkan data yang diminta ke CPU (lambat).

Lokasi Acuan

Pada saat eksekusi program, memori cenderung membaca suatu cluster di memori.

Contoh : Loop

Desain Cache

Ukuran cache

Pemetaan (Mapping Function)

Algoritma Penggantian (Replacement Algorithm)

Write Policy

Ukuran Blok

Jumlah Cache

Ukuran Cache

Kecepatan

Semakin besar ukuran cache semakin cepat (sampai ukuran tertentu)

Apabila ukuran cache semakin besar, proses pengecekan cache lebih lama.

Harga

Semakin besar cache, semakin mahal

Pemetaan

Blok-blok memori utama akan dipetakan ke slot-slot cache.

Ukuran memori utama jauh lebih besar dari ukuran cache (C << M) sehingga tidak semua blok memori utama dapat ditempatkan pada cache.

Untuk itu diperlukan suatu cara untuk memetakan blok memori utama ke cache.

Pemetaan

Teknik Pemetaan

Direct mapping

Fully associative mapping

Set associative mapping

Teknik Pemetaan

Untuk menjelaskan teknik-teknik pemetaan ini digunakan data-data berikut :

Ukuran memori utama = 216  word

Ukuran cache = 211  word.

Ukuran blok memori = ukuran slot cache = 16 word = 24 word.

Jumlah blok memori = 216 / 24  = 4096 blok

Jumlah slot cache = 211 / 24  = 128 slot.

Pemetaan Langsung

Aturan pemetaannya:

i = j modulus m

di mana:  

i = nomor slot cache 

j = nomor blok memori utama

m = jumlah slot cache

Pemetaan Langsung

Pemetaan Langsung

Contoh:

Tentukan pada slot mana blok 0, 1,128,140 akan dipetakan.

Jawab:

Blok 0 :     

  i = j modulus m

  i = 0 modulus 128

  i = 0

Jadi blok 0 akan dipetakan ke slot 0.

Dengan cara yang sama :

Blok 1   → Slot 1

Blok 128  → Slot 0

Blok 140  → Slot 12

Struktur Alamat

7 bit pada field SLOT menentukan di slot mana word tersebut seharusnya disimpan.

4 bit pada field WORD menentukan posisi word pada slot tersebut.

5 bit pada field TAG menentukan blok memori yang mana yang saat itu tersimpan di cache.

Struktur Alamat

Contoh :

Saat ini salinan word-word dari blok 0 sedang ada di slot 0. Word-word dari blok 0 memiliki alamat 0000 0000 0000 0000 sampai 0000 0000 0000 1111.

5 bit tertinggi dari word tersebut akan disimpan pada tag yang ada pada cache. Berarti pada saat word-word dari blok 0 ada di slot 0, maka pada tag slot 0 akan tersimpan bilangan 00000.

Struktur Alamat

Misalkan CPU akan mengambil sebuah word dengan alamat 0000 0000 0000 0000.

Maka yang pertama kali diproses adalah 7 bit pada field SLOT = 000 0000.

Ini berarti data tersebut seharusnya tersimpan pada slot 0.

Untuk memastikan apakah word tersebut ada pada pada slot 0, 5 bit tertinggi dari alamat tersebut (0000 0) dibandingkan dengan isi tag slot 0. Ternyata sama, kesimpulannya word tersebut ada di cache.

Struktur Alamat

Misalkan CPU akan mengambil sebuah word dengan alamat 1000 0000 0000 0000.

Maka yang pertama kali diproses adalah 7 bit pada field SLOT = 000 0000.

Ini berarti data tersebut seharusnya tersimpan pada slot 0.

Untuk memastikan apakah word tersebut ada pada pada slot 0, 5 bit tertinggi dari alamat tersebut (1000 0) dibandingkan dengan isi tag slot 0 (0000 0). Ternyata tidak sama, kesimpulannya word tersebut tidak ada di cache.

Keuntungan & Kelemahan Direct Mapping

Keuntungan teknik direct mapping adalah pada kesederhanaan proses pemetaannya. Selain itu pada saat proses  pengecekan ada tidaknya word di cache hanya satu tag yang perlu dicek isinya.

Kelemahan teknik direct mapping adalah kurang fleksibel, sebuah blok harus dipetakan ke slot yang tetap, sehingga tidak bisa memanfaatkan slot yang kosong.

Pemetaan sepenuhnya asosiatif

Teknik ini digunakan untuk mengatasi ketidakfleksibelan teknik direct mapping.

Pada teknik ini setiap blok boleh dipetakan ke blok mana saja. Dengan cara ini pemetaan lebih fleksibel dan dapat memanfaatkan slot-slot yang kosong.

Pemetaan sepenuhnya asosiatif

Struktur Alamat

4 bit pada field WORD menentukan posisi word pada slot tersebut.

12 bit pada field TAG menentukan blok memori yang mana yang saat itu tersimpan di cache (pada slot tersebut).

Struktur Alamat

Contoh:

Misalkan CPU akan mengambil sebuah word dengan alamat 0000 0000 0000 0000.

Pada teknik direct mapping,  yang pertama kali diproses adalah 7 bit pada field SLOT untuk menentukan isi TAG slot mana yang akan dibandingkan dengan 5 bit teratas dari alamat word tersebut.

Sedangkan pada teknik fully associative mapping, karena tiap blok bisa menempati slot mana saja, maka harus dilakukan pengecekan pada isi tiap TAG untuk menentukan apakah sebuah word ada di cache atau tidak.

Kelemahan utama teknik ini adalah lambatnya proses pengecekan karena harus dilakukan proses pengecekan pada tiap TAG.

mengatur pemetaan asosiatif

Teknik ini merupakan kombinasi kedua teknik sebelumnya.

Pada teknik ini beberapa slot dikelompokkan menjadi sebuah set. Ukuran tiap set dapat diatur.

Tiap blok harus dipetakan pada set tertentu, tetapi bebas dipetakan pada slot mana saja, yang merupakan anggota dari set tersebut.

mengatur pemetaan asosiatif

Aturan pemetaan :

  i = j modulus s

  

  di mana:  

i = nomor set cache

j = nomor blok memori utama

s = jumlah set

mengatur pemetaan asosiatif

Struktur Alamat

6 bit pada field SET menentukan di SET mana word tersebut mungkin disimpan.

6 bit pada field TAG menentukan blok memori yang mana yang saat itu tersimpan di cache (pada slot tersebut).

4 bit pada field WORD menentukan posisi word pada slot tersebut.

Struktur Alamat

Misalkan CPU akan mengambil sebuah word dengan alamat 1111 0000 0000 0000.

Maka yang pertama kali diproses adalah 6 bit pada field SET = 00 0000.

Ini berarti data tersebut mungkin tersimpan pada SET 0.

Selanjutnya untuk mengetahui apakah word tersebut memang ada pada pada SET 0 atau tidak, 6 bit tertinggi dari alamat tersebut (1111 00) dibandingkan dengan isi tiap TAG yang ada pada SET 0.

Jika ada yang sama, berarti word tersebut ada pada SET 0 pada slot yang isi TAG-nya sama dengan keenam bit tersebut. Jika tidak ada yang sama, berarti word tersebut tidak ada di cache dan harus diambil dari memori utama.

Keuntungan

Keuntungan teknik ini adalah lebih fleksibel dibanding dengan teknik direct mapping, tetapi juga proses pembandingan isi tagnya relatif lebih cepat dibanding teknik fully associative karena jumlah tag yang dibandingkan lebih sedikit.

Algoritma pergantian

Pada teknik direct mapping, jika sebuah blok akan disalinkan ke sebuah slot dan slot tersebut sedang terisi, maka blok yang baru tersebut langsung akan menggantikan blok yang lama.

Pada teknik fully associative dan set associative mapping, jika sebuah blok akan disalinkan ke slot cache dan semua slot saat itu penuh, maka harus ditentukan isi slot mana yang harus diganti. Untuk itu diperlukan suatu algoritma penggantian.

Algoritma pergantian

Algorima penggantian yang bisa digunakan adalah :

First In First Out (FIFO) : mengganti blok yang paling lama menempati cache.

Least Recently Used (LRU) : mengganti blok yang paling lama tidak  digunakan.

Least Frequently Used (LFU) : mengganti blok yang paling jarang digunakan.

Random : mengganti secara acak.

menulis kebijakan

Sebelum sebuah blok yang berada di dalam cache dapat diganti, harus diketahui apakah blok tersebut sudah diubah selama di cache atau tidak.

Bila belum diubah, blok lama dapat langsung ditindih.

Bila sudah diubah, maka isi memori utama harus diperbaharui.

menulis kebijakan

Ada 2 write policy yang biasa digunakan, yaitu:

Write Through

Write Back

menulis melalui

Penulisan dilakukan pada cache dan juga memori utama

Akan menyebabkan banyak trafik

Memperlambat proses penulisan

Write Back

Pada awalnya, perubahan hanya dilakukan di cache.

Sebuah bit akan diset apabila update terjadi.

Pada saat blok akan diganti, penulisan pada memori hanya dilakukan apabila bit tersebut dalam keadaan diset.

Setiap I/O harus mengakses langsung ke cache karena isi memori utama tidak valid.

Rangkaian menjadi rumit.

Ukuran kinerja cache

Ukuran kinerja cache, dilihat berdasarkan miss ratio :

Hit ratio (HR) = Jumlah referensi yang mengacu pada cache / total jumlah referensi

Miss ratio (MR) = 1 - HR

Intel Processor’s Cache

80386 – no on chip cache

80486 – 8k using 16 byte lines and four way set associative organization

Pentium (all versions) – two on chip L1 caches

Data & instructions

Pentium 4 – L1 caches

8k bytes

64 byte lines

four way set associative

L2 cache

Feeding both L1 caches

256k

128 byte lines

8 way set associative

Pentium 4 Diagram (Simplified)

Pentium 4 Core Processor

Fetch/Decode Unit

Fetches instructions from L2 cache

Decode into micro-ops

Store micro-ops in L1 cache

Out of order execution logic

Schedules micro-ops

Based on data dependence and resources

May speculatively execute

Execution units

Execute micro-ops

Data from L1 cache

Results in registers

Memory subsystem

L2 cache and systems bus

Pentium 4 Design Reasoning

Decodes instructions into RISC like micro-ops before L1 cache

Micro-ops fixed length

Superscalar pipelining and scheduling

Pentium instructions long & complex

Performance improved by separating decoding from scheduling & pipelining

(More later – ch14)

Data cache is write back

Can be configured to write through

L1 cache controlled by 2 bits in register

CD = cache disable

NW = not write through

2 instructions to invalidate (flush) cache and write back then invalidate

  Memori Virtual

Memori Virtual

Dalam ilmu komputer, memori virtual adalah teknik manajemen memori yang dikembangkan untuk kernel multitugas

Secara sistem logika, ukuran memori lebih besar daripada ukuran memori utama secara fisik.

Melibatkan mekanisme swapping

Keuntungan model virtual memori

Lebih sedikit memori yang diperlukan per proses.

System response menjadi lebih cepat, karena tidak semua bagian image proses perlu dialokasikan ke memori utama,

  à proses dapat dieksekusi lebih cepat.

Lebih banyak proses yang dapat dijalankan

  à multiprogramming

Konsep Dasar

Image proses akan diinisialisasi di area swap space, yaitu suatu lokasi di media penyimpan sebagai ekstensi memori utama.

Swap space dapat berupa suatu berkas atau partisi khusus, dan unit terkecilnya disebut page.

Pengalihan page dari swap space ke memori utama menggunakan teknik lazy swapper, yaitu hanya page proses yang dibutuhkan yang akan dialihkan ke memori utama.

Bagaimana mengetahui page mana yang masih di swap space dan yang ada di memori utama ?

Mekanisme demand paging

Konsep dasar:

Jumlah frame di memori utama tergantung tingkat multiprogramming .

  semakin tinggi tingkat multiprogramming, semakin sedikit jatah frame untuk tiap proses

Menggunakan bit valid/invalid di page table

  misal: bit 1à berada di memori utama

       bit 0à berada di swap space

Mekanisme demand paging

Jika berstatus invalid, maka trap page fault akan dibangkitkan agar ditangani lebih lanjut oleh rutin SO yaitu: page fault handler.

Rutin page fault handler akan menangani operasi swap-in terhadap page yang diperlukan.

Mekanisme demand paging

Langkah-langkah swap-in :

Mencari frame memori utama yang kosong.

  jika tidak adaà dipilih salah satu page dalam frame (victim page) untuk di swap-out.

Swap-in

Memperbarui rekaman di page table

  à mengubah validation=1

Restart.

Page Replacement

Secara umum, algoritma dapat dibagi dua:

Global Replacement

Victim frame dapat dipilih dari semua frame yang ada

Local Replacement

Victim frame dapat dipilih dari frame-frame yang sedang ditempati oleh image proses bersangkutan

Page Replacement

Algoritma page replacement:

Algoritma FIFO (First In First Out)

Algoritma Optimal

Algoritma LRU (Least Recently Used)

Page Replacement

Algoritma FIFO

  Page yang diganti adalah page yang paling lama berada di memori atau yang pertama kali masuk.

Page Replacement

Algoritma Optimal

page yang diganti adalah page yang baru akan dipanggil lagi pada waktu yang masih lama.

Diasumsikan sistem mampu memprediksi page-page yang akan diakses

Page Replacement

Algoritma LRU

  Page yang diganti adalah page yang paling lama sudah tidak diakses.

 Seberapa banyak jumlah frame yang butuh dialokasikan ke suatu proses yang berjalan?

Alokasi Frame

Pengalokasian tiap-tiap proses bervariasi tergantung pada tingkat multiprogramming

Jika tingkat multiprogramming nya semakin tinggi, maka proses akan kehilangan beberapa frame

Sebaliknya jika tingkat multiprogramming berkurang, maka proses akan mendapat frame melebihi dari yang dibutuhkan.

Alokasi Frame

Alokasi sama rata (equal allocation)

Tiap proses mendapat jumlah frame sama banyak

Alokasi proporsional (proporsional allocation)

Tiap proses mendapat jumlah frame sesuai dengan besarnya image proses itu.

Alokasi berprioritas (priority allocation)

Jumlah frame yang dialokasikan untuk tiap proses berdasarkan prioritas.

Pelepasan sekaligus upgrade RAM memory