a. Direct Mapped Cache
Jika setiap blok dari memori utama hanya memiliki satu tempat dapat muncul dalam cache, cache dikatakan Direct Mapped. Untuk menentukan urutan baris Cache blok memori utama dipetakan kita dapat menggunakan rumus di bawah ini:
Cache Line Number = (Main Memory Block Number) MOD (Number of Cache Lines)
Mari kita asumsikan kita memiliki ukuran Main Memory 4GB (2 32), dengan setiap byte secara langsung dialamatkan oleh sebuah alamat 32-bit. Kami akan membagi memori menjadi blok utama dari masing-masing 32 byte (2 5). Jadi ada 128M (yaitu 2 32 / 2 5 = 2 27) blok dalam memori utama.
Memori Cache memiliki 512KB (yaitu 2 19), dibagi menjadi blok dari masing-masing 32 byte (2 5). Jadi ada 16K (yaitu 2 19 / 2 5 = 2 14) blok juga dikenal sebagai slot Cache atau garis Cache di memori cache. Hal ini jelas dari nomor di atas bahwa ada blok memori lebih utama dari slot Cache.
Satu set 8k (yaitu 2 27 / 2 14 = 2 13) blok memori utama akan dipetakan ke slot cache tunggal. Dalam rangka untuk melacak mana dari 2 13 blok memori mungkin Utama di setiap slot Cache, lapangan tag 13-bit ditambahkan ke setiap slot Cache yang memegang sebuah identifier dalam berkisar dari 0 sampai 13-1 Februari.
Semua tag yang disimpan dalam memori tag khusus di mana mereka dapat dicari secara paralel. Setiap kali blok baru disimpan dalam cache, tag yang disimpan dalam lokasi memori yang sesuai tag.
Ketika program pertama kali dimuat ke memori utama, cache di-clear, sehingga sementara program adalah melaksanakan, sedikit yang valid diperlukan untuk menunjukkan apakah atau tidak slot memegang blok yang dimiliki oleh program yang sedang dieksekusi. Ada juga dirty bit yang melacak apakah atau tidak blok telah dimodifikasi ketika sedang dalam cache. Sebuah slot yang dimodifikasi harus ditulis kembali ke memori utama sebelum slot digunakan kembali untuk blok lain. Ketika program ini awalnya dimuat ke memori, bit yang valid semua set ke 0. Instruksi pertama yang dieksekusi dalam program karena itu akan menyebabkan kehilangan, karena tidak ada program ini di cache pada saat ini. Blok yang menyebabkan kehilangan terletak di memori utama dan dimuat ke cache.
Skema ini disebut “direct mapping” karena setiap slot cache sesuai dengan set eksplisit blok memori utama. Untuk cache dipetakan langsung, setiap blok memori utama dapat dipetakan hanya satu slot, tetapi masing-masing slot dapat menerima lebih dari satu blok.
Alamat memori 32-bit utama dipartisi menjadi bidang tag 13-bit, diikuti oleh medan slot 14-bit, diikuti dengan bidang 5-bit kata. Ketika referensi dibuat untuk sebuah alamat memori utama, slot mengidentifikasi bidang di mana dari 214 slot cache blok akan ditemukan jika berada dalam cache.
Jika bit valid adalah 1, maka field tag dari alamat direferensikan dibandingkan dengan bidang tag slot cache. Jika field tag adalah sama, maka kata tersebut diambil dari posisi di slot yang ditentukan oleh medan kata. Jika bit valid adalah 1 tetapi ladang tag tidak sama, maka slot ditulis kembali ke memori utama jika sedikit kotor diatur, dan blok memori yang sesuai utama kemudian membaca ke dalam slot. Untuk program yang baru saja dimulai eksekusi, bit valid akan 0, dan blok hanya ditulis untuk slot. Bit berlaku untuk blok ini kemudian di set ke 1, dan program resume eksekusi.
b. Fully Associative Mapped Cache
Jika sebuah blok memori utama dapat ditempatkan dalam salah satu slot cache, maka cache dikatakan fully associative mapped cache.
Diasumsikan kita memiliki ukuran Main Memory 4GB (2 32), dengan setiap byte secara langsung dialamatkan oleh sebuah alamat 32-bit. Kami akan membagi memori menjadi blok utama dari masing-masing 32 byte (2 5). Jadi ada 128M (yaitu 2 32 / 2 5 = 2 27) blok dalam memori utama.
Memori Cache memiliki 512KB (yaitu 2 19), dibagi menjadi blok dari masing-masing 32 byte (2 5). Jadi ada 16K (yaitu 2 19 / 2 5 = 2 14) blok juga dikenal sebagai slot Cache atau garis Cache di memori cache. Hal ini jelas dari nomor di atas bahwa ada blok memori lebih utama dari slot Cache.
Dalam fully associative mapped cache salah satu dari 128M (yaitu 2 27) blok memori utama dapat dipetakan ke salah satu slot Cache tunggal. Untuk melacak yang salah satu dari 2 27 blok yang mungkin adalah di setiap slot, lapangan 27-bit tag ditambahkan ke setiap slot yang memegang sebuah identifier dalam rentang dari 0 sampai 27-1 Februari. Bidang tag yang paling signifikan 27 bit dari alamat memori 32-bit disajikan untuk cache.
Dalam fully associative mapped cache, setiap blok memori utama dapat dipetakan ke slot apapun. Mapping dari blok memori utama untuk slot cache dilakukan oleh partisi alamat ke dalam kolom untuk tag dan kata (juga dikenal sebagai bidang “byte“).
Ketika referensi dibuat untuk sebuah alamat memori utama, menyadap perangkat keras cache referensi dan mencari memori tag cache untuk melihat apakah blok yang diminta dalam cache. Untuk masing-masing slot, jika bit berlaku adalah 1, maka field tag dari alamat direferensikan dibandingkan dengan bidang tag slot. Semua tag yang dicari secara paralel, dengan menggunakan memori asosiatif. Jika ada tag dalam memori tag cache sesuai bidang tag referensi memori, maka kata tersebut diambil dari posisi di slot yang ditentukan oleh medan kata. Jika kata yang direferensikan tidak ditemukan dalam cache, maka blok memori utama yang berisi kata tersebut dibawa ke dalam cache dan kata dirujuk kemudian diambil dari cache. Tag, bidang yang valid, dan kotor diperbarui, dan program resume eksekusi.
Fully associative mapped cache memiliki keuntungan menempatkan setiap blok memori utama ke baris cache manapun. Ini berarti bahwa terlepas dari bagaimana tidak teratur data dan referensi program, jika slot yang tersedia untuk blok, dapat disimpan dalam cache. Hal ini menyebabkan overhead yang cukup besar dalam perangkat keras yang diperlukan untuk cache bookkeeping.
Meskipun skema pemetaan cukup kuat untuk memenuhi berbagai macam situasi akses memori, ada dua masalah pelaksanaan yang membatasi kinerja.
Proses memutuskan yang slot harus dibebaskan ketika sebuah blok baru dibawa ke dalam cache dapat menjadi kompleks. Proses ini memerlukan sejumlah besar hardware dan memperkenalkan keterlambatan dalam mengakses memori.
Ketika cache dicari, bidang tag dari alamat yang direferensikan harus dibandingkan dengan semua bidang 2 14 tag dalam cache.
c. Set Associative Mapped Cache
Skema pemetaan asosiatif set menggabungkan kesederhanaan direct mapping dengan fleksibilitas fully associative mapped . Hal ini lebih praktis daripada fully associative mapped karena bagian asosiatif terbatas hanya beberapa slot yang membentuk set.
Dalam mekanisme pemetaan, memori cache dibagi menjadi set ‘v’, masing-masing terdiri dari baris cache ‘n’. Sebuah blok dari memori utama pertama dipetakan ke satu set cache tertentu, dan kemudian dapat ditempatkan di manapun dalam set yang. Jenis pemetaan memiliki rasio yang sangat efisien antara implementasi dan efisiensi.
Cache set number = (Main memory block number) MOD (Number of sets in the cache memory)
Jika ada cache ‘n’ baris dalam satu set, penempatan cache disebut n-way set associative contohnya jika ada dua blok atau baris cache per set, maka itu adalah 2-way set associative cache dan empat blok atau cache garis per set, maka itu adalah 4-way set associative cache mapping.
Misalnya diasumsikan kita memiliki ukuran Main Memory 4GB (2 32), dengan setiap byte secara langsung dialamatkan oleh sebuah alamat 32-bit. Kami akan membagi memori menjadi blok utama dari masing-masing 32 byte (2 5). Jadi ada 128M (yaitu 2 32 / 2 5 = 2 27) blok dalam memori utama.
Memori Cache memiliki 512KB (yaitu 2 19), dibagi menjadi blok dari masing-masing 32 byte (2 5). Jadi ada 16K (yaitu 2 19 / 2 5 = 2 14) blok juga dikenal sebagai slot Cache atau Line Cache di memori cache. Hal ini jelas dari nomor di atas bahwa ada blok memori lebih utama dari slot Cache.
Misalnya 2-way set associative cache mapping yaitu baris cache 2 per set. Kami akan membagi baris cache 16K ke set 2 dan karenanya ada 8K (2 14 / 2 = 2 13) set dalam memori cache.
Cache Size = (Number of Sets) * (Size of each set) * (Cache line size)
Jadi, bahkan dengan menggunakan rumus di atas kita dapat mengetahui jumlah set dalam yaitu cache memory.
2 19 = (Jumlah Set) * 2 * 2 5
Jumlah Set = 2 19 / (2 * 2 5) = 2 13
Ketika alamat dipetakan untuk mengatur, skema pemetaan langsung digunakan, dan kemudian pemetaan asosiatif digunakan dalam set.
Format untuk alamat memiliki 13 bit di bidang yang ditetapkan, yang mengidentifikasi set di mana kata ditujukan akan ditemukan jika berada dalam cache. Ada lima bit untuk bidang kata seperti sebelumnya dan ada 14-bit tag bidang yang bersama-sama membentuk 32 bit sisanya dari alamat.
2. Block Identification
Pada umumnya cache memiliki dua bagian penting, data cache line dan tag cache. Detailnya sebagai berikut:
Valid Bit: diatur ke 1 ketika data yang valid yang disimpan dalam cache.
Dirty Bit: di set ke 1 ketika data berubah dan tidak diperbarui untuk memori utama dalam waktu yang sama.
Tag: bidang ini memberitahu alamat mana sejalan itu.
Data: data diambil dari memori utama.
Jika ukuran cache total menyimpan associativity, sama meningkatkan meningkatkan jumlah blok per set, sehingga mengurangi ukuran indeks dan meningkatkan ukuran dari tag.
3. Block Replacement
Ketika terjadi miss, cache controller harus memilih blok harus diganti dengan data yang diinginkan. Satu manfaat langsung dipetakan penempatan adalah bahwa keputusan hardware disederhanakan – pada kenyataannya, sangat sederhana bahwa tidak ada pilihan: Hanya satu frame blok diperiksa untuk dihilangkan, dan hanya blok yang dapat diganti. Dengan fully associative cache mapped, ada banyak blok untuk memilih dari pada miss. Ada tiga strategi utama yang digunakan:
Random – Untuk menyebarkan alokasi seragam, blok kandidat dipilih secara acak. Beberapa sistem menghasilkan angka pseudorandom blok untuk mendapatkan perilaku direproduksi, yang sangat berguna ketika debugging hardware.
Keuntungan: sederhana untuk menerapkan di hardware
Kerugian: mengabaikan locality principle
Least-Used (LRU) – Untuk mengurangi kemungkinan membuang informasi yang akan dibutuhkan segera, akses ke blok dicatat. Mengandalkan masa lalu untuk memprediksi masa depan, blok diganti adalah salah satu yang telah terpakai untuk waktu yang lama. LRU bergantung pada lokalitas wajar: Jika blok terakhir digunakan kemungkinan akan digunakan lagi, maka calon yang baik untuk pembuangan adalah blok paling-terakhir digunakan.
Keuntungan: mengambil lokalitas ke rekening.
Kerugian: sebagai jumlah blok untuk melacak meningkat, LRU menjadi lebih mahal (sulit untuk melaksanakan, lambat dan sering hanya didekati).
First In First Out (FIFO) – Karena LRU dapat menjadi rumit untuk menghitung, ini mendekati LRU dengan menentukan blok tertua daripada LRU.
4. Hubungan dengan Main Memory
Pada dasarnya operasi READ mendominasi cache prosesor mengakses karena banyak mengakses instruksi yang READ operasi dan sebagian besar instruksi tidak MENULIS ke dalam memori. Ketika alamat blok yang akan READ tersedia maka tag dibaca dan jika HIT maka READ dari itu.
Dalam kasus kehilangan kebijakan READ adalah:
Read Through - Membaca blok langsung dari memori utama.
No Read Through - Membaca blok dari memori utama ke dalam cache dan kemudian dari cache ke CPU. Jadi kita bahkan memperbarui memori cache.
Pada dasarnya Miss relatif lambat karena mereka memerlukan data yang akan ditransfer dari memori utama ke CPU yang menimbulkan keterlambatan karena memori utama jauh lebih lambat dari memori cache, dan juga menimbulkan overhead untuk merekam data baru dalam cache sebelum disampaikan ke prosesor. Untuk mengambil keuntungan dari Locality of Reference , CPU salinan data ke cache setiap kali ia mengakses alamat tidak hadir dalam cache. Karena kemungkinan sistem akan mengakses lokasi yang sama yang lama, sistem akan menghemat menunggu menyatakan dengan memiliki data dalam cache. Jadi memori cache menangani aspek temporal dari akses memori, tetapi bukan aspek spasial.
Mengakses lokasi Caching memori tidak akan mempercepat eksekusi program jika kita terus-menerus mengakses lokasi memori yang berurutan. Untuk mengatasi masalah ini, kebanyakan sistem caching membaca byte berurutan dari memori saat terjadi cache miss. CPU 80×86, misalnya, membaca antara 16 dan 64 byte pada tembakan (tergantung CPU) pada cache miss. Jika Anda membaca 16 byte, mengapa membacanya di blok, bukan karena Anda membutuhkan mereka? Ternyata, chip memori yang paling tersedia saat ini memiliki mode khusus yang memungkinkan Anda dengan cepat mengakses beberapa lokasi memori yang berurutan pada chip. Cache memanfaatkan kemampuan ini untuk mengurangi jumlah rata-rata negara menunggu diperlukan untuk mengakses memori.
