set associative mapping
Post on 17-Mar-2016
538 Views
Preview:
DESCRIPTION
TRANSCRIPT
Set Associative Mapping
Disusun Oleh :
1. NURHALIM2. FIKIH3. IKA NUR’AINI
Set Associative Mapping• 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 sembarang line
dengan nomor set = j modulo v• Jika sebuah set dapat menampung X line, maka
cache disebut memiliki Xway set associative cache.• Hampir semua cache yang digunakan saat ini
menggunakan organisasi 2 atau 4-way set associative mapping.
Ketika alamat dipetakan untuk mengatur, skema pemetaan langsung digunakan, dan kemudian pemetaan asosiatif digunakan dalam set
• Format untuk alamat 13 bit di bidang yang ditetapkan,
• Identifikasi set dituju akan ditemukan jika berada dalam cache,
• Ada 5bit untuk bidang Kata, ada 14bit bidang tag, 32bit sisanya dari alamat
• Set digunakan untuk memberikan identitas unik ke set yang di cache yang menampung block yang diminta oleh prosesor.
• Tag digunakan untuk memberikan identitas unik dari block yang diminta berdasarkan set yang ditentukan.
• Word digunakan untuk memberikan identitas pada elemen (word) dalam block yang diminta oleh prosesor.
Set Associative Mapping • Cache dibagi kedalam beberapa jumlah set• Tiap set memiliki beberapa jumlah block• Block main memory dipetakan ke dalam set di
cache dengan rumus s = i mod SS = jumlah set yang diinginkan ada di cachei = jumlah block main memorys = jumlah set yang ada berdasarkan i
• Prosesor meminta data ke cache dengan format
Tag set word
Direct Mapping Set0123
Set 0 Set 1
Set 3 Set 2
Set Assosiative Mapping
• Untuk mencari nilai fieldWord = log2 B, B adalah ukuran blok dalam satuan wordSet = log2 S, S adalah jumlah set dalam cache
• Catatan :Harus diingat, total jumlah bit yang dihitung berdasarkan 3 rumus diatas harus di tambah ke dalam panjang alamat main memory. Bisa digunakan untuk mengecek kesalahan dalam perhitungan kita.
Contoh soal :Hitung 3 paramater ( word, set, dan tag ) untuk system memori dengan spesifikasi :-ukuran main memory = 128 MB-ukuran dari cache = 256 KB-ukuran block cache = 16 B
• Diasumsikan menggunakan set-associative mapping dengan 4 block per set nya.S = word = log¬¬2 B = log¬¬2 16 = log¬¬2 24 = 4 bits
set = log¬¬2 64K = 16 bitstag = 28 – ( 4 + 16 ) = 8 bitbit untuk ram = log2 128MB = 28 bit
Berdasarkan data di atas, sekarang membuat ilustrasi dalam memory.
• Gunakan set ( 16 bits ) untuk menentukan ( secara langsung ) ke set yang di tuju ( salah satu dari 32 set yang ada ).
• Main memory address Tag Set Word 8 16 4
• Gunakan tag untuk mencocokkan block yang diminta dengan block yang ada di cache sesuai dengan set yang sudah dipilih. Jika ada tag yang sama, berarti cache hit, sebaliknya cache miss.
• Dari 16 word (element) yang ada di cache block yang hit, word yang diminta dipilih berdasarkan selector yang dibantu oleh word field.
Contoh : 4 sets dari 3 lines 8 word (16 bit)
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0Tag Set Word X
CONTOH : 32 32 32 32 12832 32 32 32 12832 32 32 32 12832 32 32 32 128
512
Address = 32 bitCache = 32 KB Lines = 64 byteNumber of Lines 32 KB / 64 = 5124 Way Set Assosiative MappingNumber of sets = 512/ 4 = 128Set bits = log2 (128) = 7
19 bits 7 bits 6 bitsTag Set Offset
0111110101110111000 1101100 111000
Gambar Organisasi K-Way Set Associative Mapping.
Misal 2 WaySetAssosiative cache Mapping yaitu baris cache 2 per set
16K ke set 2 karenanya ada 8K ( 214/2 = 213 ) set dalam memori cache
CacheSize = (NumberofSet)* (SizeofEachset)*(Cache Linesize)
219=(jumlahSet)*2*25
JumlahSet = 219/(2*25) = 213
Misal Main Memory = 4GB (232 )
Setiap byte di alamatkan oleh alamat 32 bit
Setiap blok 32 byte ( 25) Jadi Ada 128M (232 / 25 ) =
227 blok dalam memoriMemori Cache 512KB (219) Blok dari masing 2 32 byte(25) Jadi ada 16K yaitu
(219/25=214)
16 Mbyte Main MemoryGambar Contoh Pengalamatan 2-Way Associative Mapping.
Contoh :
• Memory =16MB alamat =24bit• Blok = 4 B 22 jadi lebar word 2bit• Cache = 64 KB = 8 K terdapat 13bit • Data masuk = 16339C• Dengan two-way set data masuk
pada alamat 0CE7 dengan tag=02C, set=0CE7 dan word=0
16 Mbyte Main MemoryTag Set Word9 13 2
Algoritma Pengganti Ketika sebuah blok baru dibawa ke
dalam cache maka salah satu blok yang ada harus digantikan.
Untuk direct mapping hanya terdapat satu kemungkinan baris bagi sembarang blok
Untuk teknik assosiatif dan set assosistif diperlukan algortima pengganti
Untuk mencapai kecepatan tinggi algoritma harus diterapkan dalam perangkat keras dengan cara : Least Recently used (LRU)
mengganti blok yang berada dalam set yang telah berada paling lama dalam cacheKeuntungan : Mengambil lokalitas ke rekeningKerugian : jumlah blok u/ melacak meningkat menjadi lebih mahal, sulit u/ pelaksanaan,
lambat First in first out (FIFO)
Mengganti blok dalam set yang telah berada pada cache terpanjangMenjadi rumit u/ menghitung dengan menentukan blok tertua
Least frequently usedMengganti blok dalam set yang telah berada dalam set yang mengalami acuan sedikit.
AcakMenyebarkan alokasi seragam, blok kandidat dipilih secara acak.Keuntungan : Sederhana untuk menerapkan di hardwareKerugian : mengabaikan locality principle
Keuntungan menggunakan Set Associative Mapping antara lain:• Setiap blok memori dapat menempati
lebih dari satu kemungkinan nomorline (dapat menggunakan line yang kosong), sehingga thrashing dapatdiperkecil
• Jumlah tag lebih sedikit (dibanding model associative), sehingga jalur untukmelakukan perbandingan tag lebih sederhana.
Ringkasan set associative mapping nampak pada tabel berikut:
ItemPanjang alamatJumlah unit yang dapat dialamatiUkuran Blok sama dengan ukuran Line Jumlah blok di memory utamaJumlah line dalam setJumlah setJumlah line di cache Besarnya tag
Keterangan(s + w) bitss+w words or bytes2w words or bytes2dkV = 2dKv = k*2d(s-d) bits
Tabel Set Associative Mapping
S E K I A N
top related