Direct, Set Associative, Associative Mapping

A. DIRECT MAPPING

Blok address akan disimpan pada sebuah baris unik pada cache. Dari 24 bit address, dapat dibagi menjadi: (dari belakang)

• 2 bit LSB berisi byte dari blok.
• 22 bit sisanya berisi byte dari memory dari terdiri atas

          a. 14 bit LSB untuk membedakan cache line

          b. 8 bit terakhir adalah MSB berisi “tag”, sebuah elemen unik yang menjadi penanda akan               keunikan memory blok yang direferensikan oleh cache line tersebut

Keuntungan dari direct mapping antara lain.

• Sederhana
• Elemen “tag” pada setiap cache line pendek(8bit), sehingga mempercepat proses compare
• Pengaksesan blok memory cepat

Kerugian dari direct mapping antara lain.

• Jika terdapat memory address baru yang akan disimpan di cache yang memiliki line yang sama dengan sebuah cache line yang telah ada pada cache, walaupun menunjuk ke blok memory yang berbeda pada memory, address baru akan menimpa cache line lama.

Untuk menangkal kelemahan pada direct mapping, telah dikembangkan strategi yang baik:
1. Victim Cache Strategies
2. Selected Victim Cache Strategies

B. SET ASSOCIATIVE MAPPING
Memory blok disimpan pada cache line manapun pada set blok pada cache.
Keuntungan dari set associative mapping:

• Sederhana
• Elemen “tag” pada setiap cache line pendek(9bit), sehingga mempercepat proses compare
• Pengaksesan blok memory cepat
• Flexible

C. ASSOCIATIVE MAPPING

Memory blok disimpan pada cache line manapun pada cache.

Keuntungan dari set associative mapping:

• Fleksibilitas tinggi

Kerugian dari set associative mapping :

• Kompleks
• Elemen “tag” pada setiap cache line panjang (22 bit), sehingga memperlamabat proses compare
• Membutuhkan cache dengan performansi tinggi

D. REPLACEMENT ALGORITHM

Replacement algorithm adalah algoritma untuk melakukan penggantian address dari blok memory yang telah tersimpan pada cache dengan sebuah address blok memory lain. Baris pada cache line yang menjadi subjek pencarian replacement algorithm disebut baris-baris kandidat.

• Pada direct mapping, algoritma ini tidak dapat diimplementasikan.
• Pada set associative mapping, algoritma ini dibutuhkan untuk menentukan baris mana pada cache yang dapat diganti pada suatu set tertentu tergantung kepada ke set mana blok memory baru akan diletakkan.
• Pada associative mapping, algoritma ini dibutuhkan untuk menentukan baris mana pada cache yang dapat diganti dengan blok memory baru.

Ada 4 replacement algotihm yang banyak digunakan sekarang

1. Random Replacement (paling sederhana)

    Dari baris-baris kandidat, dipilih sebuah baris secara acak.

2. Least Recently Used (paling efisien)

    Dari baris-baris kandidat, dipilih sebuah baris yang paling lama telah mereferensikan sebuah blok       memory yang tidak terpakai.

3. First in First Out

    Dari baris-baris kandidat, dipilih sebuah baris yang paling lama telah mereferensikan sebuah blok       memory.

4. Least Frequently Used

   Dari baris-baris kandidat, dipilih sebuah baris yang telah mereferensikan sebuah blok memory yang     paling jarang diakses.

Selain itu, terdapat pula replacement algorithm lain yang ada, beberapa di antaranya antara lain.

1. Least Recently Used –K

    Gabungan antara least recently used dengan least frequently used, dengan K adalah jarak antara           jumlah pemakaian terbanyak dengan jumlah pemakaian baris tersebut.

2. Adaptive Replacement Cache

    Gabungan antara least recently used dengan least frequently used, dengan menggunakan algoritma      kompleks.

3. Clock with Adaptive Replacement

    Gabungan antara least recently used dengan least frequently used, dengan bantuan clock.

E.WRITE STRATEGIES

Intinya adalah bagaimana cara menjaga kekonsistenan antara isi pada cache dengan isi pada main memory saat dilakukan penulisan pada cache.

Beberapa cara penulisan pada cache antara lain.

• Write-through

         Setiap proses penulisan diserahkan pada main memory, jika blok memory terdapat pada cache, maka isi cache diupdate pula. Proses ini cenderung berjalan lambat karena melakukan akses pada main memory.

• Write-through with buffered write

         Setiap proses penulisan diserahkan pada buffer, jika blok memory terdapat pada cache, maka isi cache diupdate pula. Sedang proses ini berjalan, isi pada buffer disimpan ke main memory pada jalur lain. Proses ini cenderung berjalan lebih cepat daripada write-through karena melakukan akses pada buffer, bukan pada min memory.

• Copy-back

        Setiap proses penulisan diserahkan pada cache, jika blok pada cache tersebut akan di-replace, barulah isi pada main memory diupdate. Proses ini cenderung berjalan cepat karena proses pengupdatean dilakukan pada cache.