Cache Memory: Direct mapping, Set Associative

mapping, Associative mapping

1. Cache Memory

Cache memory adalah jenis memori yang digunakan dalam sistem komputer untuk
menyimpan data yang sering digunakan dengan tujuan mempercepat akses ke data tersebut.
Cache memory bekerja sebagai perantara antara CPU (Central Processing Unit) dan memori
utama (RAM) dalam sistem komputer.

Tujuan utama dari cache memory adalah mengurangi waktu akses ke data yang sering
digunakan. Ketika CPU membutuhkan data, ia akan mencari data tersebut di cache memory
terlebih dahulu. Jika data tersebut ada di cache, CPU dapat mengambilnya dengan cepat karena
cache memiliki waktu akses yang lebih rendah daripada memori utama. Hal ini mengurangi
latensi yang terjadi ketika CPU harus menunggu data diambil dari memori utama.

Cache memory bekerja berdasarkan prinsip lokalitas, yaitu asumsi bahwa jika data
tertentu diakses, kemungkinan besar data yang berkaitan dengan itu akan diakses juga dalam
waktu dekat. Cache memory biasanya terbagi menjadi beberapa tingkat (level) dengan tingkat
yang lebih tinggi memiliki kapasitas yang lebih kecil namun waktu akses yang lebih cepat.
Ada beberapa jenis cache memory, termasuk cache level 1 (L1), cache level 2 (L2), dan
cache level 3 (L3). Cache L1 adalah yang paling dekat dengan CPU dan memiliki waktu akses
yang sangat cepat, sedangkan cache L2 dan L3 memiliki kapasitas yang lebih besar tetapi
memiliki waktu akses yang sedikit lebih lambat.

2. Dirrect Mapping (Pemetaan Langsung)

Pemetaan langsung atau dirrect mapping adalah teknik paling sederhana diantara
teknik pemetaan lain, yaitu. memetakan setiap blok memori utama hanya ke satu saluran cache.
Setelah satu blok disimpan, maka lokasinya sudah ditentukan. Keuntungan keuntungan dari
teknik pememtaan ini adalah sederhana dan murah. Namun, kerugiannya adalah bahwa jika suatu
blok tersebut memiliki lokasi tetap (jika program menggunakan 2 blok yang dipetakan ke baris
yang sama beberapa kali, maka cache miss sangat besar).

Berikut ini penjelasan lebih rinci:

Setiap blok memori utama terhubung ke baris tertentu dari memori cache. i = j modulo C
di mana i adalah nomor baris cache yang digunakan untuk menyimpan blok memori utama ke-j.

Untuk M = 64 dan C = 4, pemetaan antara garis dan balok adalah:

 Baris/line 0 berisi balok 0, 4, 8, 12, ...
Baris /line 1 berisi balok 1, 5, 9, 13, ...
Baris /line 2 berisi balok 2, 6, 10, 14, ...
Baris/line 3 berisi balok 3 , 7, 11, 15, ...
Dengan cara ini alamat/address di memori utama dibagi menjadi 3 field atau bagian,
yaitu: tag identifikasi (tag identifier) pengenal nomor baris (Line number identifier) dan
pengidentifikasi kata (word identifier/offset).

Word identifier berisi informasi tentang lokasi word atau unit addressable lainnya dalam

line tertentu pada cache.
Line identifier berisi informasi tentang nomor fisik (bukan logika) line pada chace
Tag identifier disimpan pada cache bersama dengan blok pada line.

 Untuk setiap alamat memory yang dibuat oleh CPU, line tertentu yang menyimpan copy alamat
tsb ditentukan, jika blok tempat lokasi data tersebut sudah dikopi dari main memory ke cache.
 Tag yang ada pada line akan dicek untuk melihat apakah benar blok yang dimaksud ada line tsb
 Ringkasan direct mapping nampak pada tabel berikut:
Item Keterangan
Panjang alamat (s+w) bits
Jumlah unit yang dapat dialamati 2s+w words or bytes
Ukuran Bloks sama dengan ukuran Line 2w words or bytes
Jumlah blok memori utama 2s+ w/2w = 2s
Jumlah line di chace M = 2r
Besarnya tag (s - r) bits

Contoh soal:

1. Suatu sistem komputer memiliki memory utama sebesar 64 Mbyte, memiliki cache
sebesar 128 Kbyte. Transfer data antar memory utama dengan cache dalam ukuran block
yang besarnya 16 byte, jika digunakan pemetaan langsung (Direct Mapping) tunjukkan
masing-masing berapa bit untuk TAG (T),  SLOT (Cache Line : L) dan WORD (W).
Dik :   Memory : 64 MB
Cache      : 128 KB
Block       : 16 Byte
Dit : T L W  ?
Jawab : Memory 64 MB =  220 .  26 = 226 , Maka  lebar Alamat = 26 bit.
1 Block 16 Byte =  24 , Maka Wordnya =  4 bit.
Line Memory = Cache / Block
= 128 KB / 16 Byte
=  8 K Line

Line Cache = 8 K =  210 .  23 = 213 , Maka Linenya 13 bit.

Jadi Besar TAG = Memory – Lebar Word – Ukuran Line

= 26 – 4 (Word) – 13(Line) = 9 bit.

3. Associative Mapping

Associative mapping (pemetaan asosiatif) adalah salah satu metode yang digunakan dalam
desain cache memory untuk menentukan bagaimana blok-blok data dari memori utama akan
disimpan di dalam cache. Dalam metode ini, setiap blok data dari memori utama tidak memiliki
lokasi tetap dalam cache, melainkan dapat disimpan di mana saja dalam cache yang tersedia.

Dalam associative mapping, setiap blok data dari memori utama memiliki tag yang
menyimpan informasi tentang alamat memori asli blok tersebut. Ketika CPU membutuhkan
sebuah data, cache akan mencocokkan tag tersebut dengan tag yang ada di setiap baris cache
untuk mencari kecocokan. Jika ada kecocokan, maka blok data tersebut dianggap ditemukan
dalam cache, dan data dapat diambil dengan cepat. Jika tidak ada kecocokan, maka ini disebut
sebagai "miss", dan cache harus mencari data tersebut di memori utama, yang membutuhkan
waktu yang lebih lama.

Keuntungan dari associative mapping dalam desain cache memory adalah sebagai berikut:

1. Fleksibilitas Penyimpanan: Dalam associative mapping, setiap blok data dapat

ditempatkan di mana saja dalam cache. Hal ini memungkinkan cache untuk secara
fleksibel menyimpan dan mengelola blok-blok data dari memori utama tanpa
memperhatikan lokasi tetap dalam cache. Ini memungkinkan cache untuk
mengoptimalkan penggunaan ruang dan kapasitas cache, serta memperhitungkan pola
akses data yang kompleks.

2. Efisiensi Penggunaan Cache: Karena blok-blok data tidak memiliki lokasi tetap dalam
cache, associative mapping dapat mengoptimalkan penggunaan cache dengan lebih baik.
 Blok-blok data yang sering diakses atau memiliki lokalitas yang tinggi dapat tetap ada
dalam cache lebih lama, sementara blok-blok data

Kerugian dari associative mapping adalah sebagai berikut:

1. Kompleksitas pencarian: Pencarian data dalam associative mapping membutuhkan

pencocokan dengan semua tag dalam cache, yang dapat memakan waktu yang lebih lama
dibandingkan dengan metode pemetaan lainnya. Hal ini bisa mempengaruhi kinerja cache
dan meningkatkan latensi akses.
2. Kelebihan logika dan konsumsi daya: Implementasi associative mapping memerlukan
logika tambahan untuk melakukan pencarian yang kompleks, yang menghasilkan
penggunaan sirkuit yang lebih besar dan meningkatkan konsumsi daya dalam sistem.
3. Biaya: Asosiasi mapping membutuhkan lebih banyak sumber daya dan sirkuit
dibandingkan dengan metode pemetaan lainnya, sehingga dapat meningkatkan biaya
produksi cache memory.
4. Kurangnya prediktabilitas: Karena blok data tidak memiliki lokasi tetap dalam cache,
prediktabilitas akses data dalam associative mapping dapat menurun. Hal ini dapat
menyebabkan variasi dalam latensi akses dan performa cache secara keseluruhan.

Ringkasan Associative Mapping nampak pada tabel berikut:

Item Keterangan
Panjang alamat (s+w) bits
Jumlah unit yang dapat dialamati 2s+w words or bytes
Ukuran Bloks sama dengan ukuran Line 2w words or bytes
Jumlah blok memori utama 2s+ w/2w = 2s
Jumlah line di chace Undetermined
Besarnya tag s bits

Contoh Soal:

3. Suatu sistem komputer memiliki memory utama sebesar 512 Mbyte, memiliki cache
sebesar 128 Kbyte. Transfer data antar memory utama dengan cache dalam ukuran block
yang besarnya 8 byte, jika digunakan pemetaan langsung (Direct Mapping) tunjukkan
masing-masing berapa bit untuk TAG (T),  SLOT (Cache Line : L) dan WORD (W).

Dik :   Memory : 512 MB

Cache      : 128 KB
Block       : 8 Byte
Dit : T?W?
Jawab : Memory 512 MB =  220 .  29 = 229 , Maka  lebar Alamat = 29 bit.
1 Block 8 Byte =  23 , Maka Wordnya =  3 bit.
Line Memory = Cache / Block
= 128 KB / 8 Byte
=  16 K Line

Jadi Besar TAG = Memory – Lebar Word

= 29 – 3 (Word) =12 bit.

4. Set Associative Mapping

Set associative mapping (pemetaan set asosiatif) adalah metode yang menggabungkan
kelebihan associative mapping dan direct mapping dalam desain cache memory. Dalam set
associative mapping, cache dibagi menjadi sejumlah set yang lebih kecil, dan setiap blok data
dari memori utama dapat disimpan dalam set tertentu di cache.
Kelebihan dari set associative mapping adalah sebagai berikut:
1. Efisiensi Penggunaan Cache: Dengan membagi cache menjadi beberapa set, setiap blok
data memiliki beberapa tempat yang mungkin untuk disimpan di dalam cache. Ini
mengurangi konflik yang dapat terjadi dalam direct mapping dan memungkinkan cache
untuk lebih efisien mengelola blok-blok data yang sering diakses.
2. Pencarian Data yang Cepat: Set associative mapping menyederhanakan pencarian data
dibandingkan dengan associative mapping. Cache hanya perlu mencocokkan tag dalam
set yang sesuai, bukan dengan semua tag dalam cache. Hal ini mengurangi kompleksitas
pencarian dan meningkatkan kecepatan akses data.
3. Fleksibilitas dalam Pengelolaan Blok Data: Set associative mapping memungkinkan
fleksibilitas dalam pengelolaan blok data dalam cache. Blok-blok data yang sering
diakses dapat tetap ada dalam cache lebih lama, sementara blok-blok data yang jarang
diakses dapat digantikan oleh blok-blok data baru.

Kelemahan dari set associative mapping adalah sebagai berikut:

 1. Kompleksitas Pencarian dan Penempatan: Meskipun lebih sederhana daripada associative
mapping, pencarian dalam set associative mapping masih membutuhkan pencocokan tag
dalam set yang lebih kecil. Selain itu, pengelolaan penempatan blok data dalam set juga
memerlukan logika tambahan, yang dapat meningkatkan kompleksitas implementasi dan
konsumsi daya.

2. Konflik dalam Set yang Sama: Terkadang, dua blok data dengan alamat memori yang
berbeda dapat jatuh ke dalam set yang sama. Ini dapat menyebabkan konflik dan
peningkatan miss rate, yang berdampak negatif pada performa cache.

3. Batasan Kapasitas: Set associative mapping memiliki batasan kapasitas yang ditentukan
oleh jumlah set dan jumlah baris dalam set. Jika jumlah blok data melebihi kapasitas
cache yang tersedia, blok-blok data harus digantikan, yang dapat menyebabkan miss rate
yang tinggi.
Dalam prakteknya, set associative mapping sering digunakan sebagai kompromi antara
associative mapping dan direct mapping, untuk mencapai efisiensi penggunaan cache yang baik
dengan kompleksitas pencarian yang lebih rendah.

Ringkasan Set Associative Mapping nampak pada tabel berikut:

Item Keterangan
Panjang alamat (s+w) bits
Jumlah unit yang dapat dialamati 2s+w words or bytes
Ukuran Bloks sama dengan ukuran Line 2w words or bytes
Jumlah blok memori utama 2d
Jumlah line dalam set k
Jumlah set V=2d
Jumlah line di chace Kv = k*2d
Besarnya tag ( s – d )bits

Contoh soal:
1. Jika set associative menggunakan 2 ways dan diketahui memory sebesar 512 Mbyte,
memiliki cache sebesar 128 Kbyte, dan ukuran block sebesar 8 byte. Petakan data
berikut:
 2 way set
Dik :   Memory : 512 MB
Cache      : 128 KB
Block       : 8 Byte
Dit : Petakan dari : 10010001101000101011001111000
T L W  ?
Jawab : Memory 512 MB =  220 .  29 = 229 , Maka  lebar Alamat = 29 bit.
1 Block 8 Byte =  23 , Maka Wordnya =  3 bit.
Line Memory = Cache / Block
= 128 KB / 8 Byte
=  16 K Line

Besar set = 16K/2-way set = 8k =  210 .  23 =  213, , Maka setnya 13 bit
Jadi Besar TAG = Memory – Lebar Word
= 29 – 3 (Word)- 13(Line) =13 bit.