Minggu, 28 September 2014
Cache Memory
Nama : Rizky Budhi Setiawan
Kelas : 2IC01
NPM : 27413962
a. Elemen Cache Memory
Memang terdapat banyak implementasi cache, hanya saja terdapat sedikit elemen-elemen dasar rancangan yang dapat mengklasifikasikan dan membedakan arsitektur cache. Adapun elemen yang akan dibahas adalah elemen pertama yaitu ukuran cache. Semakin besar cache maka semakin besar jumlah gate yang terdapat pada pengalamatan cache. Akibatnya adalah cache yang berukuran besar cenderung untuk lebih lambat dibanding dengan cache berukuran kecil (walaupun dibuat dengan teknologi rangkaian terintegrasi yang sama dan ditaruh pada keping dan board yang sama
Bagian ini menyediakan suatu uraian parameter perancangan cache dan laporan beberapa hasil yang umum. Kita adakalanya mengacu pada penggunaan cache pada high-performance Computing (HPC). HPC berhubungan dengan superkomputer dan perangkat lunak superkomputer, terutama untuk aplikasi ilmiah yang melibatkan sejumlah data besar, vektor, dan perhitungan matriks, dan penggunaan algoritma paralel.
- Ukuran cache,
Menentukan ukuran memori cache sangatlah
penting untuk mendongkrak kinerja komputer. Dari segi harga cache sangatlah
mahal tidak seperti memori utama. Semakin besar kapasitas cache tidak berarti
semakin cepat prosesnya, dengan ukuran besar akan terlalu banyak gate
pengalamatannya sehingga akan memperlambat proses. Kita bisa melihat beberapa
merek prosesor di pasaran beberapa waktu lalu. AMD mengeluarkan prosesor K5 dan
K6 dengan cache yang besar (1MB) tetapi kinerjanya tidak bagus. Kemudian Intel
pernah mengeluarkan prosesor tanpa cache untuk alasan harga yang murah, yaitu
seri Intel Celeron pada tahun 1998-an hasil kinerjanya sangat buruk terutama
untuk operasi data besar, floating point, 3D. Intel Celeron versi
berikutnya sudah ditambah cache sekitar 128KB. Lalu berapa idealnya kapasitas
cache? Sejumlah penelitian telah menganjurkan bahwa ukuran cache antara 1KB dan
512KB akan lebih optimum [STA96].
Ukuran cache disesuaikan dengan
kebutuhan untuk membantu kerja memori. Semakin besar ukuran cache semakin
lambat karena semakin banyak jumlah gerbang dalam pengalamatan cache.
- Fungsi Pemetaan (Mapping)
Karena saluran cache lebih sedikit dibandingkan dengan
blok memori utama, diperlukan algoritma untuk pemetaan blok-blok memori utama
ke dalam saluran cache. Selain itu diperlukan alat untuk menentukan blok memori
utama mana yang sedang memakai saluran cache. Pemilihan fungsi pemetaan akan
menentukan bentuk organisasi cache. Dapat digunakan tiga jenis teknik, yaitu
sebagai berikut :
a. Pemetaan Langsung
(Direct Mapping)
Pemetaan ini memetakan masing-masing blok memori utama
hanya ke satu saluran cache saja. Jika suatu blok ada di cache, maka
tempatnya sudah tertentu. Keuntungan dari direct mapping adalah sederhana dan
murah. Sedangkan kerugian dari direct mapping adalah suatu blok memiliki lokasi
yang tetap (Jika program mengakses 2 block yang di map ke line
yang sama secara berulang-ulang, maka cache-miss sangat tinggi).
b. Pemetaan Asosiatif (Associative
Mapping)
Pemetaan ini mengatasi kekurangan pemetaan langsung
dengan cara mengizinkan setiap blok memori utama untuk dimuatkan ke sembarang
saluran cache. Dengan pemetaan asosiatif, terdapat fleksibilitas penggantian
blok ketika blok baru dibaca ke dalam cache. Kekurangan pemetaan asosiatif yang
utama adalah kompleksitas rangkaian yang diperlukan untuk menguji tag seluruh
saluran cache secara paralel, sehingga pencarian data di cache menjadilama
c.
Pemetaan Asosiatif Set (Set Associative
Mapping)
Pada pemetaan ini, cache dibagi dalam sejumlah sets.
Setiap set berisi sejumlah line. Pemetaan asosiatif set memanfaatkan
kelebihan-kelebihan pendekatan pemetaan langsung dan pemetaan asosiatif.
- Algoritma Penggantian,
Algoritma
penggantian adalah algoritma yang digunakan untuk memilih blok data mana yang
ada di cache yang dapat diganti dengan blok data baru
Direct
mapping tidak perlu algoritma,, Mapping pasti (tidak ada alternatif lain).
Sedangkan Associative & Set Associative memerlukan algoritma diimplementasi
dengan H/W (supaya cepat)’
Jenis
algoritma:
1. Least
Recently used (LRU)
Blok
yang diganti adalah blok yang paling lama di cache
dan tidak digunakan
Kelebihan:
- Paling
efektif
-
Mempunyai hit
ratio tinggi data yang sering digunakan
saja yang ditaruh di cache
-
Paling
mudah diimplementasikan pada two-way set associative mapping (digunakan
sebuah bit tambahan = USE bit, line yang
direfer USE bit = 1))
Contoh:
Kapasitas
cache hanya 4 baris sedangkan jumlah blok data jauh lebih banyak. Jika urutan
pengaksesan data adalah:
a b c d c b a b c kemudian
datang data e maka data yang diganti adalah ???
Jawaban: d
Kalau
data yang diakses sebelum data e adalah d, maka data yang diganti ???
Jawaban: a (a
lebih lama tidak diakses dibanding d)
2. First
in first out (FIFO)
Blok
yang diganti adalah blok yang paling awal berada di cache
Contoh:
Kapasitas
cache hanya 4 baris sedangkan jumlah blok data jauh lebih banyak. Jika urutan
pengaksesan data adalah:
a b c d c b a b c kemudian
datang data e maka data yang diganti adalah ???
Jawaban: a (a
paling lama/awal berada di cache)
Kalau
data yang diakses sebelum data e adalah d, maka data yang diganti adalah ???
Jawaban: a (a
paling lama/awal berada di cache)
3. Least
frequently used (LFU)
Blok
yang paling jarang digunakan yang diganti
Setiap
baris mempunyai counter
Contoh:
Kapasitas
cache hanya 4 baris sedangkan jumlah blok data jauh lebih banyak. Jika urutan
pengaksesan data adalah:
a b c d c b a b c a d
kemudian datang data e maka data yang diganti adalah ???
Jawaban:
d (d paling jarang diakses)
Kalau
urutan data yang diakses sebelum data e adalah a b c d c b a b c a d d, maka
data yang diganti adalah ???
Jawaban:
(i) (nilai counter a sama dengan yang lain, tetapi karena a datang paling awal
maka a berada pada baris paling
awal) FIFO
(ii)
(paling lama tidak diakses) LRU
4. Random
Penggantian
blok dilakukan secara acak. Algoritma random adalah
algoritma yang cukup sederhana juga selain algoritma FIFO. Dalam algoritma ini,
halaman yang dipilih menjadi korban dipilih secara acak. Meskipun terdengar
asal, tetapi algoritma ini relatif low cost, karena tidak
memerlukan stack, queue atau counter.
Dibandingkan dengan FIFO, rata-rata kasus menunjukkan page fault rate algoritma random lebih
rendah daripada algoritma FIFO. Sedangkan dibandingkan dengan LRU,
algorima random ini lebih unggul dalam hal memory looping
reference , karena algoritma random sama sekali tidak
memerlukan looping.
- Ukuran blok,
Elemen
rancangan yang harus diperhatikan lagi adalah ukuran blok. Telah dijelaskan
adanya sifat lokalitas referensi maka nilai ukuran blok sangatlah penting.
Apabila blok berukuran besar ditransfer ke cache akan menyebabkan hit ratio
mengalami penurunan karena banyaknya data yang dikirim disekitar referensi.
Tetapi apabila terlalu kecil, dimungkinkan memori yang akan dibutuhkan CPU tidak
tercakup. Apabila blok berukuran besar ditransfer ke cache, maka akan terjadi :
1.
Blok – blok yang berukuran lebih besar mengurangi jumlah blok yang menempati
cache. Karena isi cache sebelumnya akan ditindih.
2.
Dengan meningkatnya ukuran blok maka jarak setiap word tambahan menjadi lebih
jauh dari word yang diminta, sehingga menjadi lebih kecil kemungkinannya
digunakan cepat.
Hubungan
antara ukuran blok dan hit ratio sangat rumit untuk dirumuskan, tergantung pada
karakteristik lokalitas programnya dan tidak terdapat nilaioptimum yang
pasti telah ditemukan. Ukuran antara 4 hingga 8 satuan yang dapat dialamati
(word atau byte) cukup beralasan untuk mendekati nilai optimum [STA96].
Blok-blok
yang berukuran Iebih besar mengurangi jumlah blok yang menempati cache. Setiap
pengambilan blok menindih isi cache yang lama, maka sejumlah kecil blok akan
menyebabkan data menjadi tertindih setelah blok itu diambil. Dengan
meningkatnya ukuran blok, maka jarak setiap word tambahan menjadi lebih jauh
dari word yang diminta,sehingga menjadi lebih kecil kemungkinannya untuk di
perlukan dalam waktu dekat
- Jumlah cache
Terdapat dua macam letak cache.
Berada dalam keping prosesor yang disebut onchip cache atau
cache internal. Kemudian berada di luar chip prosesor yang
disebut off chip cache atau cache eksternal.
Cache internal diletakkan dalam
prosesor sehingga tidak memerlukan buseksternal, akibatnya waktu
aksesnya akan cepat sekali, apalagi panjang lintasan internal bus prosesor
sangat pendek untuk mengakses cache internal. Cache internal selanjutnya
disebut cache tingkat 1 (L1).
Cache eksternal berada diluar
keping chip prosesor yang diakses melalui bus eksternal. Pertanyaannya, apakah
masih diperlukan cache eksternal apabila telah ada cache internal? Dari
pengalaman, masih diperlukan untuk mengantisipasi permintaan akses alamat yang
belum tercakup dalam cache internal. Cache eksternal selanjutnya disebut cache
tingkat 2 (L2). Selanjutnya terdapat perkembangan untuk memisah cache
data dan cache instruksi yang disebutunified cache. Keuntungan unified
cache adalah :
• Unified cache memiliki hit
rate yang tinggi karena telah dibedakan antara informasi data dan informasi
instruksi.
• Hanya sebuah cache saja yang
perlu dirancang dan diimplementasikan.
Namun terdapat kecenderungan
untuk menggunakan split cache, terutama pada mesin – mesin
superscalar seperti Pentium dan PowerPC yang menekankan pada paralel proses dan
perkiraan – perkiraan eksekusi yang akan terjadi. Kelebihan utama split
cache adalah mengurangi persaingan antara prosesor instruksi dan unit
eksekusi untuk mendapatkan cache, yang mana hal ini sangat utama bagi
perancangan prosesor – prosesor pipelining.
b. Prinsip dari Cache Memory
Dalam dunia komputer dikenal dengan adanya cache (dibaca: kash) memory. Cache memory merupakan memori berkapasitas terbatas, berkecepatan tinggi yang lebih mahal dibanding memori utama. Cache memori terletak diantara memori utama dan register CPU, dan berfungsi agar CPU tidak langsung mengacu ke memori utama tetapi di cache memori yang kecepatan aksesnya lebih tinggi. Metode ini akan meningkatkan kinerja sistem. Dahulu cache disimpan di luar prosesor dan dapat ditambahkan untuk meningkatkan kinerja, saat ini cache ditanamkan di prosesor.
Memori komputer diorganisir ke dalam suatu hierarki. Ditingkatan yang paling tinggi (terdekat ke prosesor) menjadi register prosesor. Satu atau lebih tingkatan dari cache berikutnya. Ketika tingkatan multiple digunakan, maka ditandai dengan L1, L2, dan seterusnya untuk memori utama berikutnya, yang biasanya dibuat dari DynamicRandom Access Memory (DRAM). Semuanya mempertimbangkan internal sistem komputer. Hierarki melanjutkannya dengan memori eksternal, dengan tingkatan berikutnya secara umum menjadi hard-disk tetap, dan satu atau lebih tingkatan bawah yang terdiri dari media yang dapat dipindahkan seperti ZIP, disk optik, dan pita.
Dengan semakin menurunnya tingkat hierarki memori, semakin berkurang cost per bit, peningkatan kapasitas, dan waktu akses yang lebih lambat. Hal yang sangat enak untuk menggunakan hanya memori yang cepat, tetapi akan menjadi sangat mahal, kita mengorbankan waktu akses untuk biaya dengan menggunakan memori lebih lambat. Trik untuk mengorganisir program dan data dalam memori sehingga word memori umumnya diperlukan dalam memori yang lebih cepat.
Secara umum, ada kemungkinan bahwa pada waktu yang akan datang akses ke memori utama oleh prosesor akan menjadi lokasi akses terbaru. Sehingga cache secara otomatis mempertahankan salinan sebagian dari word terbaru yang digunakan dari DRAM. Jika cache dirancang dengan baik, maka sebagian besar waktu prosesor akan meminta word memori yang telah siap di dalam cache.
c. Organisasi Cache Memory pada Pentium & PC
1. Organisasi cache pentium 4
Evolusi: organisasi cache dilihat dengan jelas di dalam evolusi mikroprosesor intel 80386 tidak mencakup suatu cache on-chip. 80486 meliputi cache on-chip tunggal 8 kbyte, menggunakan ukuran baris 16 byte dan suatu organisasi asosiatif set empat ara. Semua prosesor pentium meliputi dua cache on-chip L1, satu untuk data dan satu untuk instruksi. Untuk pentium 4, cache data L1 adalah 8 kbyte, menggunakan ukuran baris 64 byte dan suatu organisasi asosiatif set empat arah.
.
A. Evolusi organisasi dilihat jelas pada
1. Evolusi microprosesor Intel 80386 tidak memiliki on-chip.
2. Cache 80486 menggunakan on-chip cache tunggal 8 byte dengan memakai saluran berukuran 16 byte.
3. Organisasi asosiatif set 4 pentium menggunakannya 2 on-chip cache.
4. Data cache -> operasi integer maupun floating point.
5. Data cache -> dua port dan menggunakan write-back policy.
B. Gambar Struktur Cache Data Internal Pentium [ANDE93]
C. Konsistensi Data Cache
•Data cache mendukung protokol -> yang dikenal sebagai MESI (modified/exclusive/shared/invalid). -> dirancang -> mendukung persyaratan konsitensi cache sistem multiprosesor dan organisasi pentium berprosesor tunggal.
• Tabel Keadaan-keadaan Saluran Cache MESI
M E S I
Modified Exclusive Shared Invalid
Saluran cache ini invalid? Ya Ya Ya Ya
Salinan memorynya… out of date valid valid __
Salinan ada dalam cache lain? Tidak Tidak Mungkin Mungkin
Suatu write pada saluran ini… Tidak Tidak Pergi Pergi
Pergi ke bus pergi ke bus ke bus dan langsung
Meng-update ke bus Cache
-> Modified: Saluran pada cache telah dimodifikasi (berbeda dengan memory utama).
-> Exclusive: Saluran pada cache sama seperti saluran pada memori utama dan tidak terdapat pada cache lainnya.
-> Shared: Saluran pada cache sama seperti pada saluran pada memori utama dan dapat berada pada cache lainnya.
-> Invalid: Saluran pada cache tidak berisi data yang valid.
Cache Control
1. Cache internal dikontrol oleh dua bit pada salah satu resgister kontrol, yang berlabel bit CD (cache disable) dan bit NW (Not writethrough).
2. Tabel Mode Pengoperasian Cache Pentium
Control Bits Operating Mode
CD NW Cache Fills Write-Throughs Invaliddates
0 0 Enabled Enabled Enabled
1 0 Disabled Enabled Enabled
1 1 Disabled Disabled Disabled
2. Organisasi Cache power PC
Organisasi cache power PC telah meningkatkan secara menyeluruh arsitektur dari kelompok power PC, mencerminkan kemudahan kinerja yang mengarahkan kekuatan bagi semua perancang mikroprosesor
A. Organisasi cache Power PC telah mengalami modifikasi dengan masing-masing model dalam kelompok PowerPC.
B. Gambar dibawah ini -> bentuk yang disederhanakan dari organisasi PowerPC 620. Unit-unit eksekusi inti merupakan arithmetic.
Gambar Diagram blok PowerPC 620
 |
| Add caption |
C. Gambar di bawah ini menunjukkan Diagram Keadaan cache Power PC yang disederhanakan
.png)
III. ORGANISASI DRAM TINGKAT LANJUT
A. Bentuk diagram blok dasar memori utama masih berupa keping DRAM.
• Keping DRAM tradisional memiliki kendala dalam hal arsitektur internal, olah interface, dan interface untuk bus memori prosesor.
B. Enhanced DRAM
• Arsitektur DRAM baru yang paling sederhana enhanced DRAM (EDRAM)
• Dibuat oleh Ramtron [BOND94]. EDRAM mengintegrasikan cache SRAM yang kecil pada keping DRAM generik.
• EDRAM mencakup beberapa feature lainnya yang dapat meningkatkan kinerja.
C. Cache DRAM
• Cache DRAM (CDRAM) dibuat oleh Mitsubishi [HIDA90] = EDRAM.
• CDRAM mencakup cache SRAM cache SRAM yang lebih besar dari EDRAM (16 vs 2 kb).
D. Synchronous DRAM
• Pendekatan yang berbeda meningkatkan kinerja DRAM synchronous DRAM (SDRAM)
• SDRAM bertukar data dengan prosesor yang disinkronkan dengan signal pewaktu eksternal dan bekerja dengan kecepatan penuh bus prosesor/memori tanpa mengenal keadaan wait.
• Dengan menggunakan akses sinkron. DRAM memindahkan data ke dalam dan keluar di bawah kontrol waktu sistem
Referensi :
http://asroidaulay.blogspot.com/2011/11/operasi-pembacaan-cache_970.html
http://tha-yunita.blogspot.com/2011/04/elemen-rancangan-pada-memori-cache.html
http://chrisanto92.blogspot.com/2013/10/prinsip-prinsip-elemen-cache-memory.html
