Pemetaan atau Mapping Cache Memory
MAPPING CACHE MEMORY
2.1 Mapping (Pemetaan)
Saluran cache lebih sedikit dibandingkan dengan blok
memori utama sehingga diperlukan algoritma untuk pemetaan blok-blok memori
utama ke dalam saluran cache. Selain itu, diperlukan juga alat untuk menentukan
blok memori utama mana yang sedang memakai saluran cache. Pemilihan fungsi
pemetaan akan menentukan bentuk organisasi cache. Terdapat tiga metode yang
digunakan yaitu :
1.
Pemetaan
Langsung (Direct Mapping)
Pemetaan langsung adalah teknik
yang paling sederhana, yaitu teknik ini memetakan blok memori utama hanya ke
sebuah saluran cache saja. Jika suatu block ada di cache, maka tempatnya sudah
tertentu. Keuntungan dari direct mapping adalah sederhana dan murah. Sedangkan
kerugian dari direct mapping adalah suatu blok memiliki lokasi yang tetap (jika
program mengakses 2 blok yang di map ke line yang sama secara berulang-ulang,
maka cache-miss sangat tinggi).
Berikut penjelasan
lebih detail :
§
Setiap
blok pada main memory dipetakan dengan line tertentu pada cache. i
= j modulo C di mana i adalah nomor line pada cache yang digunakan
untuk meletakkan blok main memory ke-j.
§
Jika
M = 64 dan C = 4, maka pemetaan antara line dengan blok menjadi
seperti berikut
:
Line 0 can hold blocks 0, 4, 8, 12, ...
Line
1 can hold blocks 1, 5, 9, 13, ...
Line
2 can hold blocks 2, 6, 10, 14, ...
Line
3 can hold blocks 3, 7, 11, 15, ...
§ Pada
cara ini, address pada main memory dibagi 3 field atau bagian,
yaitu:
o
Tag identifier.
o
Line number identifier
o
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.
o
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.
o
Tag yang ada pada line akan dicek untuk
melihat apakah benar blok yang dimaksud ada line tsb.
Gambar 2.1 : Gambar
Organisasi Direct Mapping.
Keuntungan Menggunakan Direct Mapping antara lain :
§ Mudah
dan Murah diimplementasikan
§ Mudah
untuk menentukan letak salinan data main memory pada chace.
Kerugian menggunakan Direct Mapping antara lain :
§ Setiap
blok main memory hanya dipetakan pada 1 line saja.
§ Terkait
dengan sifat lokal pada main memory, sangat mungkin mengakses blok yang
dipetakan pada line yang sama pada cache. Blok seperti ini akan
menyebabkan seringnya sapu masuk dan keluar data ke/dari cache, sehingga
hit ratio mengecil. Hit ratio adalah perbandingan antara jumlah
ditemukannya data pada cache dengan jumlah usaha mengakses cache.
Gambar 2.2 : Gambar
Contoh Pengalamatan Direct Mapping.
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
|
2.
Pemetaan
Asosiatif (Associative Mapping)
Pemetaan asosiatif mengatasi
kekurangan pemetaan langsung dengan cara mengizinkan setiap blok memori utama
untuk dimuatkan ke sembarang saluran cache. Dengan pemetaan assosiatif,
terdapat fleksibilitas penggantian blok ketika blok baru dibaca ke dalam cache.
Kekurangan pemetaan asosiatif yang utama adalah kompleksitas rangkaian yang
diperlukan untuk menguji tag seluruh saluran cache secara parallel, sehingga
pencarian data di cache menjadi lama.
§
Memungkinkan
blok diletakkan di sebarang line yang sedang tidak terpakai.
§
Diharapkan
akan mengatasi kelemahan utama Direct Mapping.
§
Harus
menguji setiap cache untuk menemukan blok yang diinginkan.
o
Mengecek
setiap tag pada line
o
Sangat
lambat untuk cache berukuran besar.
§
Nomor
line menjadi tidak berarti. Address main memory dibagi menjadi 2 field
saja, yaitu tag dan word offset.
Gambar 2.3 : Gambar
Organisasi Associative Mapping.
§
Melakukan
pencarian ke semua tag untuk menemukan blok.
§
Cache
dibagi menjadi 2 bagian :
o
lines
dalam SRAM
o
tag dalam associative memory
Gambar 2.4 : Gambar
Contoh Pengalamatan Associative Mapping
Keuntungan Associative Mapping : Cepat dan
fleksibel.
Kerugian Associative Mapping : Biaya
Implementasi, misalnya untuk cache ukuran 8 kbyte dibutuhkan 1024 x 17 bit associative memory untuk menyimpan tag identifier.
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
|
3.
Pemetaan
Asosiatif Set (Set Associative Mapping)
Pada pemetaan ini, cache dibagi
dalam sejumlah sets. Setiap set berisi sejumlah line. Pemetaan asosiatif set
memanfaatkan kelebihan-kelebihan pendekatan pemetaan langsung dan pemetaan
asosiatif.
§
Merupakan
kompromi antara Direct dengan Full Associative Mapping.
§
Membagi
cache menjadi sejumlah set (v) yang masing-masing memiliki sejumlah line (k)
§
Setiap
blok dapat diletakkan di sebarang line dengan nomor set: nomor set = j
modulo v
Gambar 2.5 :
Gambar Organisasi K-Way Set Associative Mapping.
§ Jika sebuah set
dapat menampung X line, maka cache disebut memiliki X way set associative
cache.
§ Hampir semua cache
yang digunakan saat ini menggunakan organisasi 2 atau 4-way set
associative mapping.
Gambar 2.6 :
Gambar Contoh Pengalamatan 2-Way Associative Mapping.
Keuntungan
menggunakan Set Associative Mapping antara lain:
Setiap blok
memori dapat menempati lebih dari satu kemungkinan nomor line
(dapat menggunakan line yang kosong), sehingga thrashing dapat diperkecil
Jumlah tag lebih
sedikit (dibanding model associative), sehingga jalur untuk melakukan
perbandingan tag lebih sederhana.
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
|
2.2 Algoritma Penggantian
Algoritma penggantian adalah suatu mekanisme
pergantian blok-blok dalam memori cache yang lama dengan data baru. Dalam
pemetaan langsung tidak diperlukan algoritma ini, namun dalam pemetaan
assosiatif dan asosiatif set, algoritma ini mempunyai peranan penting untuk
meningkatkan kinerja cache memori.
Banyak algoritma penggantian yang telah
dikembangkan, algoritma yang paling efektif adalah Least Recently Used (LRU),
yaitu mengganti blok data yang terlama berada dalam cache dan tidak memiliki
referensi. Algoritma lainnya adalah First In First Out (FIFO), yaitu mengganti
blok data yang awal masuk. Kemudian Least Frequently Used (LFU) adalah mengganti
blok data yang mempunyai referensi paling sedikit. Teknik lain adalah algoritma
Random, yaitu penggantian tidak berdasarkan pemakaian datanya, melainkan
berdasar slot dari beberapa slot kandidat secara acak.
2.3 Write Policy
Apabila suatu data telah diletakkan pada cache maka
sebelum ada penggantian harus dicek apakah data tersebut telah mengalami
perubahan. Apabila telah berubah maka data pada memori utama harus di-update.
Masalah penulisan ini sangat kompleks, apalagi memori utama dapat diakses langsung
oleh modul I/O, yang memungkinkan data pada memori utama berubah,lalu bagaimana
dengan data yang telah dikirim pada cache? Tentunya perbedaan ini menjadikan
data tidak valid.
Teknik yang dikenal diantaranya, write through,
yaitu operasi penulisan melibatkan data pada memori utama dan sekaligus pada
cache memori sehingga data selalu valid. Kekurangan teknik ini adalah
menjadikan lalu lintas data ke memori utama dan cache sangat tinggi sehingga
mengurangi kinerja system, bahkan bisa terjadi hang.
Teknik lainyya adalah write back, yaitu teknik
meminmasi penulisan dengan cara penulisan pada cache saja. Pada saat akan
terjadi penggantian blok data cache maka baru diadakan penulisan pada memori
utama. Masalah yang timbul adalah manakala dat di memori utama belum di-update
telah diakses modul I/O sehingga data di memori utama tidak valid.
Penggunaan multi cache terutama untuk multi prosesor
akan menjumpai masalah yang lebih kompleks. Masalah validasi data tidak hanya
antara cache dan memori utama saja, namun antar cache juga harus diperhatikan.
Pendekatan penyelesaian masalah yang dapat dilakukan adalah dengan :
Bus
Watching with Write Through. Yaitu setiap cache controller akan memonitoring
bus alamat untuk mendeteksi adanya operasi tulis. Apabila ada operasi tulis di
alamat yang datanya digunakan bersama maka cache controller akan menginvalidasi
data cache-nya.
Hardware
Transparency. Yaitu adanya perangkat keras tambahan yang menjamin semua
updating data memori utama melalui cache direfleksikan pada seluruh cache yang
ada.
Non
Cacheable Memory. Yaitu hanya bagian memori utama tertentu yang digunakan
secara bersama. Apabila ada pengaksesan data yang tidak di-share merupakan
kegagalan cache.
2.4 Miss Cache
Saat miss menulis, anda bisa
punya pilihan antara membawa blok ke cache (writeallocate) atau
tidak (write-no-allocate). Saat miss membaca, anda selalu
membawa blok ke cache (lokalitas spasial atau temporal) - blok mana yang
diganti:
tidak
ada pilihan untuk direct-mapped cache
memilih
secara acak way yang akan diganti
mengganti
way yang paling jarang dipakai (LRU)
penggantian
FIFO (round-robin)
Tipe miss cache adalah
sebagai berikut:
Miss wajib: terjadi saat pertama kali word
memori diakses. Merupakan miss untuk cache yang infinit.
Miss kapasitas: terjadi karena program
menyentuh banyak word yang lain sebelum menyentuh ulang word yang sama.
Merupakan miss untuk cache fullyassociative.
Miss konflik: terjadi karena dua work dipetakan
ke lokasi yg sama di cache. Merupakan miss yang terjadi ketika
berganti dari cache fully-associative ke direct-mapped.
Lihat Selengkapnya DISINI dalam makalah cache memory
Search Income :
- Pengertian cache memory
- Makalah cache memory
- Cache memory pada processor
- Definisi cache memory
- fungsi dan kegunaan cache memory
- Kecepatan cache memory
- Cache Memory dalam Arsitektur dan Organisasi Komputer
0 komentar: