cache memory

CACHE MEMORY
Karena perbedaan kecepatan antara CPU dan MM cukup jauh berbeda, perlu diatur sinkronisasi antara keduanya. Sebuah program terdiri dari beberapa bahkan ratuasan sampai ribuan instruksi. Ada instruksi yang di eksekusi berulangkali, ada juga instruki yang jarang dieksekusi. Gejala demikian disebut sebagai Locality of reference.

Untuk itu perlu diatur sedemikian hingga Segmen aktif program berada dalam memory yang cepat, sehingga waktu eksekusi total dapat berkurang. Memori yang dipakai untuk tempat segmen aktif program dikenal dengan nama cache memory. Cache memory diletakkan diantara CPU dan MM. Kecepatannya lebih tinggi daripada MM.
Ketika cache penuh dan memori word (instruksi atau data) yang diminta tidak berada di cache, keputusan harus diambil, blok manakah yg harus dihilangkan agar cukup tempat tersedia bagi blok word baru yang akan dimuat. Kumpulan teknik untuk membuat keputusan ini disebut Repacement Algorithm

Mekanisme penempatan instruksi didalam cache memori dikenal dengan Mapping Function (Fungsi Pemetaan)

Beberapa jenis Mapping Function (Fungsi Pemetaan) :
DIRECT MAPPING CACHE
ASSOSIATE MAPPING CACHE
BLOCK SET ASSOSIATE MAPPING CACHE

DIRECT - MAPPING CACHE
Merupakan cara paling sederhana untuk menentukan lokasi cache yang digunakan. Dengan teknik ini, blok j memori utama memetakan ke blok j pada cache memori.
Untuk jelasnya lihat gambar di bawah ini.

MISAL :
Jika sebuah cache memori dengan ukuran 2K akan dihubungkan dengan Main Memori kapasitas 64K dengan ketentuan :
Masing-masing blok terdiri dari 16 word
1 word = 16 bit
Maka dapat dihitung :
Jumlah blok dalam CACHE
2048/16 = 128 BLOK

Jumlah blok dalam MAIN MEMORI
65.534/16 = 4096 BLOK

Perbandingan blok main dan Cache
4096/128 = 32

jadi 1 cache bisa untuk 32 main secara bergantian atau cache : main = 1 : 32

Untuk blok cache 0 bisa ditempati blok memori
0
128
256
384
32 blok 512
640
768
s/d
3968 (128 X 31)

Untuk blok cache 1 bisa ditempati blok memori
1
129
257
385
513
32 blok 641
769
s/d
3969 (3968+1)

Untuk blok cache 127 bisa ditempati blok memori
127
255
383
511
639
32 blok 767
895
s/d
4095 (3969+127)

Jika ada pernyataan : alamat 2013 H
00100 0000001 0011 = 2013 H
tag blok word

Artinya :
(Tag : label)
TAG ke 4 = urutan masuk ke blok cache adalah urutan yang ke 4
Blok ke 1 = tempatnya di blok cache yang ke 1
word ke 3 = word ke 3 dari blok

kita lihat blok cache ke 1 diurutan ke 4 itu berisi :
Untuk blok cache 1 bisa ditempati blok memori
1
129
257
385
513
641
769
s/d
3969( 3968+1)

Jadi address sesungguhnya dari main memori adalah :
Blok yang ke 385, word yang ke 3
alamatnya adalah 385 X 16 + 3 = 6163 D
dijadikan HEXA, 6163 D = 1813 H


Teknik direct mapping mudah untuk diterapkan tetapi sangat tidak fleksible
Karena lebih dari satu blok memori dipetakan dalam satu blok cache tertentu maka sangat mungkin muncul perebutan untuk posisi cache tersebut.

ASSOSIATE - MAPPING CACHE
Metode mapping ini jauh lebih fleksibel, yaitu blok memori utama dapat diletakkan ke dalam tiap posisi blok cache. Untuk seperti kasus dalam direct mapping di atas diperlukan 12 bit tag untuk mengidentifikasi blok memori saat blok tersebut berada dalam cache.

Dari gambar di atas 127 blok cache bisa langsung di access oleh blok main Memori maka
Untuk blok cache0 bisa ditempati blok memori
0
1
2
3
4
5
6
s/d
4095

Untuk blok cache1 bisa ditempati blok memori
0
1
2
3
4
5
6
s/d
4095

Jadi jika ada pernyataan: alamat : CC06 H

1100 1100 0000 0110
tag word

Address sebenarnya adalah blok ke CC06 H

Teknik ini menghasilkan kebebasan penuh dalam memilih lokasi cache untuk meletakkan blok memori.
Biaya yang diperlukan untuk menyelidiki seluruh pola 128 tag untuk menentukan apakah suatu blok memori berada dalam chace lebih tinggi dari direct mapped.

BLOK SET ASSOSIATE MAPPING CACHE
Metode ini merupakan gabungan dua metode sebelumnya. Blok cache dikelompokkan ke dalam set, dan mapping memungkinkan blok memori utama untuk berada dalam blok set tertentu. Karenanya masalah perebutan dalam metode direct dikurangi dengan menggunakan beberapa pilihan penempatan blok. Pada saat yang sama biaya hardware dikurangi dengan mengurangi ukuran penelusuran assosiatif.

Pada cache dibuat set, yang masing-masing setnya terdiri dari 2 blok :
Misalkan
Blok 0 | Set 0 Blok 4 | Set 2
Blok 1 | Blok 5 |

Blok 2 | Set 1 Blok 6 | Set 3
Blok 3 | Blok 7 |

Shg dari yang 128 BLOK tadi dibagi menjadi 2 128/2 = 64 SET

Karena Blok 0 dan Blok 1 digabung dalam 1 set berarti kemungkinan 1 SET akan di akses oleh 32 X 2 ( 1 set = 2 blok dan tiap blok ada 32 kemungkinan)

Berarti Tiap 64 SET Cache ini kemungkinan akan diakses oleh 4096 BLOK Main shg : 4096/64 = 64 (TAG)

Untuk set cache 0 bisa ditempati blok memori
0
64
128
192
256
320
384
s/d
4032 (64 X 63)

Untuk set cache 1 bisa ditempati blok memori
1
65
129
193
257
321
385
s/d
4033

Jika ada pernyataan: alamat 1011 H
000100 000001 0001
tag Set word

TAG ke 4 = urutan masuk ke blok cache adalah urutan yang ke 4
Blok ke 1 = tempatnya di blok yang ke 1
word ke 3 = word ke 3 dari blok

kita lihat set cache ke 1 diurutan ke 4 itu berisi :
Untuk set cache 1 bisa ditempati blok memori
1
65
129
193
257
321
385
s/d
4033

Algoritma Penggantian
Algoritma penggantian data cache memori tidak berlaku pada Direct Mapping. Karena pada direct mapping posisi tiap blok telah ditentukan.
Pada metode associative dan set-associative, saat blok baru akan dibawa ke cache dan semua blok cache telah penuh, maka harus diputuskan blok mana yang akan di overwrite.
Secara umum metode ini adalah mempertahankan data yang tampaknya akan segera digunakan (direferensi) dan mengganti data yang tidak/belum akan direferensi.

Properti locality of reference dapat menjadi petunjuk, karena kemungkinan besar blok yang telah direferensi akan segera direferensi lagi. Maka jika harus melakukan overwrite dapat dipilih blok yang lama tidak direferensi.
Blok yang paling lama tidak direferensi ini disebut blok LAST Recently Used (LRU), dan teknik tersebut disebut algoritma penggantian LRU (LRU replacement algorithm).

Algoritma LRU
misal terdapat 4 blok dalam satu tag cache set associative
Saat cache belum penuh maka blok yang diakses CPU akan dimasukkan cache, dan counter blok cache ini diset ke 0. Blok lain yang telah terisi nilainya ditambah satu.
Jika sebuah blok akan diletakkan pada cache saat cache penuh, maka blok cache dengan nilai counter 3 dihapus dan digantikan dengan blok baru.
Blok yang baru menempati cache ini akan diberi nilai counter 0, sedang blok cache yang nilainya sama akan ditambah satu. Demikian juga untuk blok yang nilai counternya sama dengan blok yang counternya baru di update akan ditambah satu.

Contoh Teknik Mapping:
Berikut contoh ilustrasi efek teknik mapping pada cache memori.

Asumsi :
Prosesor memiliki cache instruksi dan data terpisah.
Cache data hanya memiliki ruang 8 blok data.
Setiap blok terdiri dari 16 bit (1 word) data.
Main memori yang digunakan sebesar 64KB (65.536), sehingga terdapat 16 bit alamat untuk memori ini.

Terdapat array bilangan 4 X 10, masing-masing menggunakan satu word.
Array ini ditempatkan pada alamat memori utama 7A00H – 7A27H.
Elemen array ini , A, disimpan dalam order kolom (lihat Gb 11.3)

Aplikasi :
Sum := 0
For j := 0 to 9 do
Sum := Sum + A(0,j)
Ave := Sum / 10
For i := 9 downto 0 do
A(0,i) := A(0,i) / Ave
end