set associative mapping
Download as PPT, PDF
2 likes11,937 views
Set associative mapping merupakan kompromi antara direct mapping dan full associative mapping. Cache dibagi menjadi beberapa set, dengan masing-masing set menampung beberapa blok. Hal ini memungkinkan blok memori utama untuk dialokasikan ke beberapa lokasi di cache.
set associative mapping
- 1. Set Associative Mapping Disusun Oleh : 1.NURHALIM - 1211600075 2.FIKIH - 1211600083 3.IKA NURAINI - 1211600091
- 2. Set Associative Mapping Merupakan kompromi antara Direct dengan Full Associative Mapping. Membagi cache menjadi sejumlah set (v) yang masing-masing memiliki sejumlah line (k) 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.
- 3. 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 S S = jumlah set yang diinginkan ada di cache i = jumlah block main memory s = jumlah set yang ada berdasarkan i Prosesor meminta data ke cache dengan format Tag set word
- 4. 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.
- 5. Direct Set 0 Set 1 Mapping Set 0 1 2 Set 3 Set 2 3 Set Assosiative Mapping
- 7. 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測測24 K = 16 bits tag = 28 ( 4 + 16 ) = 8 bit bit untuk ram = log2 128MB = 28 bit = 4+16+28 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 ).
- 8. Untuk mencari nilai field Word = log2 B, B adalah ukuran blok dalam satuan word Set = log2 S, S adalah jumlah set dalam cache Catatan : Harus diingat, total jumlah bit yang dihitung berdasarkan 3 rumus diatas (Word, set, tag) 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
- 9. 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.
- 10. Gambar Organisasi K-Way Set Associative Mapping.
- 11. Ketika sebuah blok baru dibawa ke dalam cache maka salah satu blok yang ada harus digantikan Ukuran Blok Jumlah Jumlah Line Blok Besaran F0..Fk-1 Tagnya Mencocokkan Blok yang ada dgn yang Jumlah Set Set0 ... SetN Panjang Alamat Jumlah unit yang diamati dipilih Jika Tagnya Sama Jika Tagnya Berbeda Gambar Organisasi K-Way Set Associative Mapping.
- 12. Studi Kasus : Jika diketahui sebuah sistem komputer dengan Main Memory = 16 MB , dilengkapi dengan Cache = 64 KB , 1 Block Data = 4 byte Ditanyakan: Struktur Address Set Associative Mapping Solusi: 16 MB memory memiliki total address sebanyak 224 = 16.777.216 (a) TOTAL field = 24 bit (16 M = 224) (b) WORD field = 2 bit ( 1 block = 4 = 22 ) (c) TAG field = 9 bit (16 M / 32 k = 512= 29) (d) SET field = (2429)=13 bit 24 bit 9 bit 13 bit 2 bit Tag Set Word
- 13. Hasil : Set Associative Mapping
- 14. 16 Mbyte Main Memory Gambar Contoh Pengalamatan 2-Way Associative Mapping.
- 15. Contoh : Memory =16MB alamat =24bit Blok = 4 B 22 jadi lebar word 2bit Cache = 64 KB = 8 K terdapat 13bit Data masuk = 339C Dengan two-way set data masuk pada alamat 0CE7 dengan tag=02C, set=0CE7 dan word=0
- 16. 16 Mbyte Main Memory Tag Set Word 9 13 2
- 17. 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
- 18. 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 cache Keuntungan : Mengambil lokalitas ke rekening Kerugian : 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 terpanjang Menjadi rumit u/ menghitung dengan menentukan blok tertua
- 19. Least frequently used Mengganti blok dalam set yang telah berada dalam set yang mengalami acuan sedikit. Acak Menyebarkan alokasi seragam, blok kandidat dipilih secara acak. Keuntungan : Sederhana untuk menerapkan di hardware Kerugian : Mengabaikan locality principle
- 20. 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.
- 21. Ringkasan set associative mapping nampak pada tabel berikut: Item Keterangan (s+w) bits Panjang alamat s+w words or bytes Jumlah unit yang dapat dialamat i 2w words or bytes Ukuran Blok sama dengan ukuran Line 2d Jumlah blok di memory utama k Jumlah line dalam set V = 2d Jumlah set Kv = k*2d Jumlah line di cache (s-d) bits Tabel Set Associative Mapping Besarnya tag
- 22. S E K IA N