Cache: Intro & Direct Map Associativity

Post ini catatan untuk persiapan saya buat mengajar minggu ini. Highly technical, jadi maaf kalau banyak yang tidak mengerti. Sorry. 😀

Cache di Arsitektur Komputer

Di komputer yang kita sehari-hari, kita mengenal prosesor, memori, dan storage. Apabila kita menjalankan suatu program, dapat dipastikan kita menggunakan memori. Entah itu membaca atau menulis.

Nah, memori ini sendiri ada macam-macam. Kalau saya beri nomor urut:

  1. Register, ini adalah memori yang tertanam dan merupakan bagian dari arsitektur prosesor. Ukurannya paling kecil, tetapi aksesnya paling cepat. Hampir tidak ada waktu tunggunya.
  2. Cache, adalah memori yang sedikit lebih jauh dari prosesor dibanding register, tetapi umumnya masih dalam 1 chip CPU. Dia memang didesain untuk menyimpan sementara data yang dipakai oleh program. Kalau dalam prosesor modern, Intel Core i7 misalnya, dalam spesifikasinya kita sering dengar L1 cache dan L2 cache. Inilah yang dimaksud dalam spesifikasi tersebut. Kalau ada L1 dan L2, berarti cache yang digunakan ada 2 level. Bagian inilah yang akan dibahas di sini.
  3. Main Memory, kita sehari-hari biasa menggunakan istilah RAM untuk merujuknya. Karena dia merupakan komponen tersendiri, diperlukan waktu lebih banyak untuk mengakses data di dalamnya. Jalur akses dari CPU ke Main Memory kita sebut “Bus”.
  4. Secondary Memory, dalam keadaan tertentu, kadangkala storage kita, hard-disk misalnya, juga digunakan sebagai memori. Ini akan menjadi bahasan berikutnya.

Kalau kita gambarkan jenis-jenis memori di atas sebagai sebuah piramid, maka:

screenshot_113

Jika diurutkan dari nomor 1 hingga nomor 4, harga per byte semakin murah, kapasitas makin besar, dan waktu akses semakin melambat.

Kalau digambarkan secara arsitektur kurang lebih begini:

screenshot_114

Sebelum melangkah lebih jauh, mari kita bahas beberapa istilah penting terkait tentang cache ini.

Glossary

  • Hit, adalah apabila data yang diminta oleh program ada di dalam cache, sehingga tidak perlu lagi memanggil data dari tempat lain.
    • Hit time/hit latency, total waktu akses yang dibutuhkan apabila terjadi hit, hingga data sampai ke CPU.
    • Hit rate, adalah persentase terjadinya hit pada cache.
  • Miss, adalah apabila data yang diminta oleh suatu program tidak ada dalam cache. Jika ini terjadi, maka perlu memanggil data dari tempat lain.
    • Miss penalty, adalah total waktu akses yang dibutuhkan apabila terjadi miss, dari mengambil data di main memory, memasukkannya ke dalam cache, hingga data sampai ke CPU.
    • Miss rate, adalah persentase terjadinya miss pada cache. Hit rate + Miss rate = 100%.

Selain itu cache juga menganut prinsip locality. Ada 2 jenis:

  • Temporal locality, jika ada sebuah data yang diakses, umumnya data itu akan dipakai lagi secepatnya. Jadi lebih baik kita menyimpan data yang paling baru yang diakses.
  • Spatial locality, jika ada sebuah data yang diakses, umumnya data yang alamatnya berdekatan akan diakses lagi secepatnya. Jadi lebih baik menyimpan data beberapa sekaligus yang alamatnya berdekatan.

Mengenai hubungan cache dengan main memory, ada tiga tipe hubungan. Hubungan ini kita sebut associativity.

  1. Direct Mapped Cache,
  2. Fully Associative Cache,
  3. Set Associative Cache, ini adalah yang umum dipakai sekarang.

Kita akan bahas satu per satu mengenai ketiganya, dimulai dari Direct Mapped Cache.

Direct Mapped Cache

Paling mudah adalah langsung menggunakan contoh. Nanti sambil jalan, akan dibahas pengertiannya satu per satu.

Misalkan pada sebuah komputer 8-bit terdapat 16 byte cache dan 64 byte main memory. Cache menggunakan direct mapped cache dengan 4-word block.

Wah, banyak istilah aneh. Mari kita bahas satu per satu.

Pertama, karena di situ komputernya 8-bit maka 1 word = 8 bit = 1 byte. Jadi di kasus ini, “word” dan “byte” akan punya pengertian yang sama.

Kedua, besar memori kita 64 byte, jadi ada 64 word yang bisa ditaruh di sana. Untuk, addressing 64 word tersebut kita perlu alamat sebesar 6 bit (hayo dari mana?).

Kalau main memory-nya kita gambarkan:

 

screenshot_115

Di contoh tadi disebut 4-word block. Maksudnya adalah, kita mendefinisikan 1 block sebagai 4 word di main memory. Dan juga, kita nomori setiap block-nya.

screenshot_116

Atau, agar lebih mudah, kita gambarkan per block, dengan masing-masing 4 words. Jadinya akan seperti ini:

screenshot_117

Dari sini kalau kita perhatikan, apabila nomor block, atau block number, digabungkan dengan offset, maka akan menjadi address mula-mula!

Jadi address-nya bisa kita gambarkan begini:screenshot_118

Nah, kita sudah bahas dari sisi main memory-nya, selanjutnya mari kita bahas dari sisi cache-nya.

***

Di pernyataan tadi disebut besarnya cache adalah 16 byte, jadi cache-nya muat 16 word. Satu buah line pada cache besarnya sama dengan satu buah block pada main memory.

Karena 1 block tadi 4 word, maka di cache, tiap line juga ada 4 word. Jadi ada 4 buah line. Kalau digambarkan cachenya.

screenshot_119

Setiap line, kita beri nomor. Nomor ini kita sebut sebagai index, ada juga yang menyebut line number.

screenshot_120

Nah, sekarang kita mulai mempelajari hubungan antara cache dan main memory.

Pada direct mapped cache, satu block di main memory akan menempati line yang sama apabila dimasukkan ke dalam cache.

  • Block 0 bila dimasukkan ke dalam cache akan dimasukkan ke Line 0.
  • Block 1 bila dimasukkan ke dalam cache akan dimasukkan ke Line 1.
  • Block 2 bila dimasukkan ke dalam cache akan dimasukkan ke Line 2.
  • Block 3 bila dimasukkan ke dalam cache akan dimasukkan ke Line 3.
  • Block 4 bila dimasukkan ke dalam cache akan dimasukkan ke Line 0.
  • Block 5 bila dimasukkan ke dalam cache akan dimasukkan ke Line 1.
  • Block 6 bila dimasukkan ke dalam cache akan dimasukkan ke Line 2.
  • Block 7 bila dimasukkan ke dalam cache akan dimasukkan ke Line 3.

… dan seterusnya. Terlihat polanya? Sekarang mari kita coba lihat gambarnya:

screenshot_122

Kalau kita perhatikan, ternyata 2-bit terakhir dari nomor block adalah index dari cache!

Wah, kalau begitu kita bisa lebih mendetailkan gambar addressnya dong.

screenshot_123

Masih sisa 2-bit yang terdepan, bagian itu kita sebut tag, digunakan untuk mengetahui apakah akses ke cache hit atau miss. Jadi alamat akan menjadi:

screenshot_124

Jadi dalam membagi address, kita dapat menghitung panjang tag, index, dan block offset. Dengan cara:

  • Panjang block offset = log2 (banyaknya word per block)
  • Panjang index = log2 (banyaknya line pada cache)
  • Panjang tag = panjang address – panjang index – panjang block offset.

Juga pada cache kita tambahkan 1 kolom lagi, tag. Karena kolom ini untuk mencocokkan.

Juga untuk mempermudah, ada 1 kolom tambahan selebar 1 bit, yang menandakan apakah line cache sudah pernah diisi atau belum. Kolom ini kita sebut kolom valid.

screenshot_125

Supaya lebih terbayang, mari kita mengerjakan contoh soal.

Contoh:

Sebuah program memanggil beberapa address pada memori dengan urutan sebagai berikut: 1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17.

Hitunglah hit rate dan miss rate untuk program tersebut pada direct mapped cache yang mampu menampung 16 word, apabila digunakan:

  • 4-word block (4 word untuk tiap block),
  • 2-word block (2 word untuk tiap block),
  • 1-word block (1 word untuk tiap block).

See you in class!

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s