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!

Iklan

SuperAyam

Seorang biologis, namanya William Muir, melakukan eksperimen sederhana. Mengembang biakkan ayam. Tujuan percobaannya sederhana, mengukur produktivitas ayam, karena cukup mudah mengatakan ayam “produktif” atau tidak. Cukup dengan menghitung telurnya.

Mula-mula, Muir beternak sekelompok ayam petelur hingga 6 generasi. Setelah itu dia membaginya menjadi dua kandang. Kandang pertama, diisi ayam yang biasa-biasa saja produksi telurnya, kita sebut saja kandang ini “Kandang Ayam”. Kandang kedua, diisi dengan ayam-ayam yang paling produktif jumlah telurnya dari setiap generasi. Sebutlah namanya “Kandang SuperAyam”.

Muir mengamati kedua kandang tersebut, menghitung produktivitas mereka, hingga enam generasi.

Di “Kandang Ayam”, terus produktif mengeluarkan telur. Ayam-ayam di sana sehat, berkembang biak dengan baik, telur-telur yang diproduksinya juga berkualitas prima. Bahkan jumlah telur terus bertambah. Semakin produktif.

Jika sekelompok ayam yang biasa-biasa saja bisa seperti itu, bagaimana dengan SuperAyam? Seharusnya dengan intuisi, “Kandang SuperAyam” akan jauh lebih produktif bukan?

Tidak, di “Kandang SuperAyam” hanya tersisa tiga ayam dari yang mula-mula ditaruh Muir. Sisanya dipatuk oleh mereka bertiga, hingga mati. Apa yang terjadi di sini?

Para SuperAyam ini, menurut Muir adalah ayam-ayam yang sangat kompetitif. Mereka produktif dengan cara membandingkannya dengan ayam lain. Mereka hanya bisa sukses dengan menekan produktivitas ayam lain. Bahkan, pada akhirnya mereka sampai membunuh ayam lain.

***

Super Ayam. Kata seorang teman, “Kebanyakan dari kita juga demikian, bukan? Senang meremehkan orang lain agar dapat terlihat ‘paling’. Menjatuhkan orang lain agar terlihat ‘wah’.”

Seberapa sering kita merasa “paling jago”, “paling pintar”, “paling benar”, “paling hebat”, dan paling-paling yang lain? Seberapa sering rasa “paling” kita ini membuat kita merasa lebih dari orang lain? Seberapa sering kita merendahkan orang lain?

Saya jadi ingat sebuah spanduk yang dahulu selalu dibentangkan di kampus ketika mahasiswa baru tiba. “Selamat datang putra-putri terbaik bangsa”. Para mahasiswanya dipilih dari yang paling baik di antara para siswa SMA. Datang dengan dipuji setinggi langit, menciptakan iklim “SuperAyam”.

Untunglah beberapa tahun terakhir, spanduk itu tak pernah dipasang lagi.

The Wisdom of The Crowd?

Sebuah video dari BBC ini menarik perhatian saya, judulnya The Wisdom of The Crowd. Menarik dan sederhana eksperimen yang dilakukan sang presenter.

Kalau tak punya cukup waktu atau kuota untuk membuka videonya, singkatnya, sang presenter menanyakan kepada 160 orang, “Berapakah jumlah permen yang ada dalam toples ini?”. Ada yang menjawab dari 400 buah hingga 30 000 buah. Tidak satu pun yang menebak dengan benarTapi ada yang menarik, rata-rata dari seluruh jawabannya hanya salah 0.1% dari keadaan sebenarnyaJumlah permen di toples adalah 4520 buah, sedangkan rata-rata jawabannya adalah 4515 buah. Hanya selisih 5 dari sekitar 4000-an!

Wah, menarik. Si presenter bilang, “It’s interesting that nobody is right, but everybody is right.”

Penasaran, saya pun sedikit mencari-cari tentang ini. Bu Ruomeng Cui, seorang dosen, melakukan sedikit eksperimen di kelasnya dengan menyuruh seisi kelas menebak berat badan beliau. Tiap kelas berisi 40 orang, di kelas pertama, rata-rata dan kenyataan berat badan beliau hanya berselisih 0.08 pound. Sedangkan di kelas kedua, hanya selisih 0.25 pound. Angka yang fantastis. Akurat.

***

Wah, menarik, bagaimana kalau kita coba sendiri? 40 sampel mestinya mudah kan? Dan pertanyaan yang paling mendasar buat saya adalah

Apakah wisdom of the crowd ini berlaku untuk semua pertanyaan?

Hari ini saya dan adik saya melakukan sedikit eksperimen kecil di Car Free Day hari ini, kami menanyakan kepada 40 orang, “Berapakah isi celengan adik saya?”. Isinya koin dari 100-an hingga 1000-an, penuh seisi wadah Mr. Potato.

photo304996996923631932
Koin
photo304996996923631933
Bertanya pada orang-orang

Setelah selesai menanyai 40 orang, kami pun pulang dan mencoba merekap data yang kami punya. Jadi jawaban untuk pertanyaan kami

Berapakah jumlah uang di wadah ini?

Adalah:

  • Rata-rata jawaban 40 responden adalah 260 360 Rupiah,
  • Median jawaban 40 responden adalah 200 000 Rupiah, dan
  • Modus jawaban 40 responden adalah 200 000 Rupiah.

Sedangkan setelah kita hitung benar-benar jumlah uang di wadah keripik kentang itu, ternyata jumlahnya adalah 177 600 Rupiah. Sehingga kalau dilihat dari rata-rata, kesalahannya sekitar 46%, sedangkan kalau dilihat dari modus dan median, sekitar 12%.

***

Emm. Eksperimen yang lebih menyisakan tanda tanya daripada tanda titik. Error yang dihasilkan cukup tinggi, sama sekali tidak mencerminkan wisdom of the crowd.

  • Apakah sampel kami kurang? Tapi eksperimen berat badan yang dilakukan Ruomeng Cui juga melibatkan 40 orang, kan?
  • Apakah pertanyaan yang bisa dilakukan untuk memperoleh wisdom of the crowd ini hanya pertanyaan tertentu saja? Harus yang sederhana? Mengingat jumlah koin di dalam celengan adalah sesuatu yang cukup kompleks dibanding berat badan seseorang misalnya.
  • Jika memang hanya pertanyaan tertentu saja, apakah pertanyaan “Siapakah yang paling pantas jadi pemimpin?” adalah salah satu pertanyaan yang bisa dijawab oleh orang banyak? Pada dasarnya pemilu adalah memperoleh wisdom of the crowd bukan?

Masih banyak yang menggantung.

Simple does not Mean Easy

Simple may be, but not easy

– Alfred Borden in The Prestige.

Seringkali kita dengar kalau ada sesuatu yang inovatif misalnya, ada yang bergumam, “Ah, ini kan sederhana, mestinya kita bisa buat juga”. Atau, “si A ini Thesisnya sederhana sekali, mestinya saya bisa lulus cepat kalau ngerjain Thesis kaya punya dia.”

Padahal, sederhana itu tidak berarti mudah. Pernah ke gym saat pergantian tahun? Ramai bukan? Tapi berapa banyak yang bertahan hingga beberapa bulan? Apalagi beberapa tahun. Pergi berolahraga rutin itu hal yang sederhana, mudah? Urusan lain lagi.

Pengeluaran harus lebih kecil dari pendapatan, spend less than what you earn. Itu juga prinsip dasar keuangan yang sederhana. Mudah? Mudah darimananya? Berapa banyak orang yang terlilit hutang karena gaya hidup? Berapa orang yang sampai menjual semua hartanya di saat darurat karena keadaan yang memaksanya? Sampai-sampai buku-buku tentang pengaturan keuangan pribadi sangat laku di toko buku. Isinya pun intinya nasehat bahwa spend less than what you earn. Sederhana.

Diet dan pengaturan pola makan juga sederhana, kalau hendak menurunkan berat badan, kalori masuk harus kurang dari kalori keluar. Sebaliknya, jika hendak menaikkan, kalori masuk harus  lebih dari kalori keluar. Sederhana. Mudah? Coba perhatikan teman yang sedang melakukan diet. Berapa banyak godaannya? Cemilan, traktiran gratis, minuman manis, keinginan makan ini dan itu. Tidak mudah.

Saya pernah mencoba menaikkan berat badan, menghitung kalori masuk dan kalori keluar dengan aplikasi. MyFitnessPal. Alasannya saya perlu berat badan yang ideal, saya underweight, 7 kilogram di bawah berat ideal. Mestinya makan banyak itu sederhana bukan? Tapi mudah? Ternyata susah. Memenuhi kalori yang harus dimasukkan itu membuat perut saya terasa kenyang sekali. Belum lagi harus berolahraga, agar yang ditumpuk adalah otot, bukan lemak, dan olahraga ternyata mengurangi kalori cukup banyak, dan berarti makannya juga harus lebih banyak. Anyway, saya hanya berhasil meningkatkan 2 kilogram, belum sampai 7 kilogram.

Sederhana != mudah.

Berburu Tulisan Ilmiah (1)

Bagi yang sedang mengerjakan Tugas Akhir, Tesis, atau Disertasi tentunya akrab dengan yang namanya tulisan ilmiah atau paper. Demikian juga yang sedang melakukan penelitian di lembaga riset tertentu. Masalahnya kadang kita perlu membaca paper yang harganya mahal (~$35 untuk satu paper) dan universitas atau lembaga riset kita bekerja tidak memiliki akses ke sana.

Nah, untuk itu, saya hendak berbagi cara mendapatkan paper-paper itu secara gratis. Sebagai catatan, di sini saya tidak terlalu peduli cara mendapatkan papernya legal atau ilegal, yang penting paper sampai ke tangan kita. Cobalah cara-cara ini satu per satu.

(1) Simple Google Search

Kalau kita beruntung, kita bisa menggunakan cara paling sederhana, cukup dengan mengetikkan judul paper ke google.

Misalkan kita ingin mendapatkan paper dari Oxford Journal, berjudul “Promise and perils of electronic public engagement“. Nah, saya tinggal memasukkan judulnya dan, voila! Dengan melakukan google search sederhana, saya sudah bisa memperolehnya!

Google Search!
Google Search!

Bagaimana kalau kita tidak seberuntung itu? Mari coba langkah selanjutnya.

(2) Google Scholar

Masih tidak jauh-jauh dari google, kali ini kita menggunakan salah satu layanan google yang memang diperuntukkan untuk mencari paper. Instead of searching in google.com, search it at scholar.google.com.

Kali ini yang menjadi “korban” adalah paper dari IEEE: “Model-integrated development of embedded software“. Kalau saya di kampus (ITB) sih mudah mendownload ini, tapi bagaimana jika Anda bukan dari kampus ITB? Mari kita coba google scholar.

Google scholar!
Google scholar!

Nah, itu di kanan ada tulisan [PDF]! Mari kita coba klik! Waaahh!

Screenshot_13
Paper!

Nah kan!

(3) Perpustakaan Nasional Republik Indonesia

Tahukah Anda bahwa Perpustakaan Nasional Republik Indonesia berlangganan beberapa jurnal internasional seperti Taylor & Francis dan Sage? Cukup dengan memberikan data diri sesuai KTP di website-nya, dan kita sudah memiliki akses ke sana secara gratis!

Mari kita melakukan eksperimen di sana dengan men-download paper dari Taylor & Francis berjudul “Dielectric properties of BaTiO3 by molecular dynamics simulations using a shell model“.

Mari masuk ke website perpustakaan nasional, dan login (saya sudah teregistrasi di sana, jika belum, registrasilah).

Tampilan PNRI
Tampilan PNRI

Lalu saya masuk ke Taylor & Francis (dengan mengklik No 17). Lalu mengetikkan apa yang saya cari di kolom search yang muncul.

Hasil pencarian
Hasil pencarian

Nah, di situ ada tulisan “Download Full Text”! Mari kita coba klik, daaan, hohoho:

Hasil PNRI
Hasil PNRI

Bravo PNRI! Ayo dong diperbanyak langganan jurnalnya! Hehehe.


 

Bagaimana kalau masih belum berhasil juga? Nantikan di seri Berburu Tulisan Ilmiah selanjutnya! Jangan lewatkan! Follow blog ini!

Capek juga nulis banyak-banyak.

 

Fantasy Premier League

Sudah 3 musim ini, saya (dan beberapa teman) bermain Fantasy Premier League. Sebuah game resmi dari website English Premier League. Kebetulan saya memang penggemar Liga Inggris, dan di sana ada klub favorit saya, Arsenal.

Pada game ini kita diharuskan membeli beberapa pemain dengan batasan dana tertentu, ada yang mahal dan ada yang murah. Setiap minggu, pemain akan dinilai poinnya berdasarkan performa yang sebenarnya di lapangan. Gol, assist, menit bermain, dan clean sheet adalah penentu apakah pemain mendapat banyak atau sedikit poin. Kadang kalau beruntung, beberapa pemain diberi bonus karena performa yang eksepsional di lapangan.  Detailnya bisa dibaca di halaman rule website FPL.

Tidak, saya tidak ingin membahas strategi pada game ini, saya hanya ingin membahas game ini berdasarkan perhitungan sederhana. Yang ada di kepala saya saja.

Jadi, pada game ini, sebuah tim akan dinilai total performanya berdasarkan jumlah seluruh poin yang dikumpulkannya. Liga inggris terdiri dari 38 minggu, maka total poin yang kita dapat adalah:

\sum\limits_{i=1}^{38} \text{Gwp}_i

Terkadang ada transfer cost yang harus dibayarkan karena melakukan transfer berlebih (-4, -8, -12, dan seterusnya). Transfer cost ini bisa tidak diberikan kalau wildcard digunakan. Sayangnya wildcard hanya ada dua, satu bisa dipakai sepanjang musim, dan satunya saat bursa transfer Januari. Sehingga:

\sum\limits_{i=1}^{38} (\text{Gwp}_i - \text{Tc}_i)

Setiap gameweek points, sebenarnya adalah rata-rata seluruh tim pada gameweek itu ditambah dengan delta. Delta adalah angka yang membedakan tim kita dengan rata-rata gameweek. Sehingga:

\sum\limits_{i=1}^{38} (\text{Avg}_i + \Delta_i - \text{Tc}_i)

Targetnya adalah jumlah sigma tersebut menghasilkan nilai yang maksimum. Jadi yang sangat berpengaruh adalah \Delta_i dan \text{Tc}_i.

Untuk memaksimalkan faktor transfer cost, saya berusaha disiplin untuk tidak melakukan -4. Dulu sewaktu musim pertama saya, saya melakukan -4 hampir setiap minggu. Jumlah poin saya yang hilang berarti sekitar 38 \times 4 = 152 poin. Jumlah yang tidak sedikit!

Faktor berikutnya adalah Delta, variabel ini bisa positif dan negatif. Karena seluruh tim fantasy mendapatkan rata-rata yang sama, faktor inilah yang membedakan tim kita dengan tim yang lain. Bila tim kita dipenuhi oleh pemain-pemain yang dipilih oleh banyak orang, nilai kita akan mendekati rata-rata.

Pemain-pemain yang akan membuat nilai dekat rata-rata musim ini.
Pemain-pemain yang akan membuat nilai dekat rata-rata musim ini.

Untuk itu, jika mau memaksimalkan delta, pemain kita haruslah yang tidak banyak dipilih orang. Tapi ini problematis, karena kita tidak hanya bermain untuk satu pekan, tapi 38. Kita berlari marathon bukan sprint. Memilih seluruh pemain anti-mainstream, akan mengakibatkan nilai \Delta_i bisa menjadi positif sangat besar, tetapi pada saat lain akan menjadi negatif sangat besar.

Hal lain yang berpengaruh pada \Delta_i adalah pilihan kapten. Dengan pertimbangan yang kurang lebih sama.

Jadi pilihan terbijaknya adalah, memakai beberapa pemain mainstream (agar nilai mendekati rata-rata), lalu beberapa pemain anti-mainstream sebagai \Delta.

Well, that’s too much theory!

Come on Badaksinga! Catch that Ratu Minang!

Badaksinga chasing Ratu Minang!
Badaksinga chasing Ratu Minang!