Arsitektur dan Organisasi Komputer
{ Cache Memory }
Dosen Kelas Nama
: Drs. Eko Polosoro, MM, MT : XB : Iis Widya Harmoko Ronal Chandra Yoga Prihastomo
MAGISTER ILMU KOMPUTER
UNIVERSITAS BUDI LUHUR 2011 i
Kata Pengantar
Dengan rahmat Allah SWT, kami dapat menyelesaikan tugas makalah mata kuliah “Arsitektur dan Organisasi Komputer” sesuai waktu yang telah ditentukan. Dalam makalah ini kami mengambil tema mengenai Cache Memory. Cache memory merupakan memori yang memiliki kecepatan sangat tinggi, digunakan sebagai perantara antara Main Memory dan CPU. Memori ini mempunyai kecepatan lebih tinggi daripada Main Memory, namun harganya lebih mahal. Cache memory digunakan untuk menjembatani perbedaan kecepatan CPU yang sangat tinggi dengan kecepatan RAM yang jauh lebih rendah. Dengan menggunakan cache memory, sejumlah data dapat dipindahkan ke memori ini dalam sekali waktu, dan kemudian ALU akan mengambil data tersebut dari memori ini. Dengan pendekatan seperti ini, pemrosesan data dapat dilakukan lebih cepat daripada kalau CPU mengambil data secara langsung dari RAM. Seperti pepatah mengatakan: “Tak ada gading yang tak retak”. Oleh karena itu, kami mohon masukan dari makalah yang telah kami sajikan guna penyempurnaan pada penulisan makalah ini.
Jakarta, 18 Juni 2011 Hormat kami,
Tim Penyusun
ii
Daftar Isi
Kata Pengantar ......................................................................................................... Daftar Isi .................................................................................................................... Daftar Gambar ......................................................................................................... Daftar Tabel ..............................................................................................................
ii iii iv v
BAB I MAIN MEMORY 1.1. Pendahuluan ................................................................................................... 1.2. Pengelompokkan Memory ............................................................................. 1.3. Jenis Memory ................................................................................................ 1.4. Hubungan Antara CPU dengan Main Memory dal Alat-alat I/O .................. 1.5. Karakteristik Sistem Memory ........................................................................
1 2 3 5 8
BAB II CACHE MEMORY 2.1. Cache Memory .............................................................................................. 2.2. Level Cache Memory .................................................................................... 2.3. Kapasitas Cache ............................................................................................. 2.4. Ukuran Blok ..................................................................................................
9 10 12 12
BAB III MAPPING CACHE MEMORY 3.1. Pemetaan ........................................................................................................ 3.2. Algoritma Penggantian .................................................................................. 3.3. Write Policy ................................................................................................... 3.4. Miss Cache ....................................................................................................
14 21 22 23
BAB IV PENUTUP ...................................................................................................
24
DAFTAR PUSTAKA LAMPIRAN
iii
Daftar Gambar
Gambar 1.1. Vaccum Tubes ......................................................................................
3
Gambar 1.2. Mesin Vaccum Tubesdengan Magnetic Core Storage .........................
4
Gambar 1.3. Single LayerTthin Film dengan Ta2N Resistors ..................................
4
Gambar 1.4. Semiconductor Storage berbentuk SIMM ............................................
4
Gambar 1.5. Josephson Junction Chip ......................................................................
5
Gambar 1.6. Delta-Doped Charged Coupled Devices (CCD) ...................................
5
Gambar 1.7. Keterhubungan CPU, MM, dan I/O ......................................................
6
Gambar 1.8. Keterhubungan CPU, MM, dan I/O melalui Register ..........................
6
Gambar 2.1. Posisi Cache Memory pada Sistem Memory ........................................
9
Gambar 2.2. Sistem Interkoneksi yang terkait dengan Cache Memory .....................
9
Gambar 2.3. Contoh Level Cache pada Processor .....................................................
11
Gambar 3.1. Organisasi Direct Mapping ....................................................................
15
Gambar 3.2. Contoh Pengalamatan Direct Mapping..................................................
16
Gambar 3.3. Organisasi Associative Mapping ...........................................................
17
Gambar 3.4. Contoh Pengalamatan Associative Mapping .........................................
18
Gambar 3.5. Organisasi K-Way Set Associative Mapping ........................................
19
Gambar 3.6. Contoh Pengalamatan 2-Way Associative Mapping .............................
20
iv
Daftar Tabel
Tabel 1.1.
Karakteristik Sistem Memori .................................................................
8
Tabel 3.1.
Direct Mapping .......................................................................................
17
Tabel 3.2.
Associative Mapping ..............................................................................
19
Tabel 3.3.
Set Associative Mapping .........................................................................
21
v
BAB I MAIN MEMORY
1.1. Pendahuluan Main Memory (memory utama) atau lebih dikenal sebagai memori adalah sebuah array yang besar dari word atau byte, yang ukurannya mencapai ratusan, ribuan, atau bahkan jutaan. Setiap word atau byte mempunyai alamat tersendiri. Main memory berfungsi sebagai tempat penyimpanan yang akses datanya digunakan oleh CPU atau perangkat I/O. Main-memory termasuk tempat penyimpanan data yang sementara (volatile), artinya data dapat hilang begitu sistem dimatikan. Sistem operasi bertanggung jawab atas aktivitas-aktivitas yang berkaitan dengan manajemen memori seperti: menjaga track dari memori yang sedang digunakan dan siapa yang menggunakannya; memilih program yang akan di-load ke memori; dan mengalokasikan dan mendealokasikan memoryspace sesuai kebutuhan. Main memory dapat dibayangkan sebagai kumpulan kotak-kotak yang masing dapat menyimpan suatu penggal informasi baik berupa data maupun instruksi. Umumnya 1 byte memory terdiri dari 8 bit dan tiap bit diwakili oleh 1 atau 0. Kombinasi bit dalam1 byte tersebut membentuk suatu kode yang mewakili isi dari lokasi memory. Kode yang digunakan untuk mewakilinya tergantung dari komputer yang digunakan, dapat membentuk sistem kode BCD (Binary-Coded Decimal), sistem kode SBCDIC (Standard Binary Coded Decimal Interchange Code), sistem kode EBCDIC (Extended Binary Coded Decimal Interchange Code) atau sistem kode ASCII (American Standard Code for Information Interchange). Misalnya suatu komputer mempunyai kapasitas memory 256 KB atau 262.144 byte, yang berarti mempunyai 262.144 lokasi memori. Alamat dari memori ini adalah bernomor 000000 sampai dengan 262.143.
1
1.2. Pengelompokkan Memory Main memory terdiri dari: A. RAM (Random Access Memory) Merupakan memori yang dapat diisi dan diambil isinya oleh pemrogram. Semua data dan program yang dimasukkan lewat alat input akan disimpan terlebih dahulu di RAM. Struktur dari RAM, dibagi menjadi: 1. Input Storage, digunakan untuk menampung input yang dimasukkan lewat alat input; 2. Program Storage, digunakan untuk menyimpan semua instruksi program yang akan diproses; 3. Working Storage, digunakan untuk menyimpan data yang akan diolah dan hasil dari pengolahan; 4. Output Storage, digunakan untuk menampung hasil akhir dari pengolahan data yang akan ditampilkan ke alat output. B. ROM (Read Only Memory) Memori ini hanya dapat dibaca saja, programer tidak bisa mengisi sesuatu ke dalam ROM. Isi ROM sudah diisi oleh pabrik pembuatnya berupa sistem operasi yang terdiri dari program-program pokok yang diperlukan oleh sistem komputer, seperti program untuk mengatur penampilan karakter, pengisian tombol kunci dan bootstrap program. Bootstrap program diperlukan pada waktu pertama kali sistem komputer diaktifkan, yang proses ini disebut dengan istilah booting, yang terdiri dari: 1. Cold booting, yaitu proses mengaktifkan sistem komputer pertama kali untuk mengambil bootsrap program dari keadaan listrik komputer mati. 2. Warm booting, yaitu proses pengulangan pengambilan bootstrap program dalam keadaan komputer masih hidup.
2
Instruksi yang tersimpan di ROM disebut dengan microinstruction atau microcode atau disebut juga firmware. Isi dari ROM tidak boleh hilang atau rusak, karena dapat menyebabkan sistem komputer tidak berfungsi. ROM bersifat non volatile, artinya isinya tidak hilang bila listrik komputer dimatikan. Jenis-jenis ROM: 1. PROM (Programmable Read Only Memory), yaitu ROM yang dapat diprogram sekali saja dan tidak dapat diubah kembali 2. EPROM (Erasable Programmable Read Only Memory), yaitu ROM yang dapat dihapus dengan sinar ultra violet serta dapat diprogram kembali berulang-ulang 3. EEPROM (Electrically Erasable Programmable Read Only Memory), yaitu ROM yang dapat dihapus secara elektronik dan dapat diprogram kembali
1.3. Jenis Memory Berdasarkan komponen yang digunakan terbagi atas : A. Vacuum Tubes Komputer generasi pertama ENIAC tahun 1946 menggunakan komponen tabung hampa udara untuk main memory. Memori ini relatif berukuran besar dan tiaptiap tabung hampa udara mewakili 1 bit.
Gambar 1.1 – Gambar Vacuum Tubes
B. Magnetic Core Storage Digunakan sekitar tahun 1960-1970. Terdiri dari ribuan cincin magnetik kecil berukuran 18 mm dengan lubang berdiameter 10 mm. Tiap-tiap core dihubungkan dengan kabel kawat membentuk suatu bidang core (core plane) dan ditumpuk membentuk suatu core stack.
3
Masing-masing core dapat menyimpan 1 bit bila dimagnetasi dengan suatu arus listrik dari dua arah jurusan yang masing-masing bermuatan ½ arus.
Gambar 1.2 – Gambar Mesin Vacuum Tube dengan Magnetic Core Storage
C. Planar Thin-Film Storage Terbuat dari lempengan tipis keramik atau metal tembus pandang yang berisi kumpulan besi nikel berbentuk empat persegi panjang
kecil dihubungkan
dengan kabel-kabel.
Gambar 1.3 – Gambar Single LayerTthin Film dengan Ta2N Resistors
D. Semiconductor Storage Mulai banyak digunakan sejak tahun 1970-an hingga sekarang. Terbuat dari VLSI (Very Large Scale Integration) yaitu meletakkan sejumlah besar circuit ke dalam suatu chip. Teknologi yang digunakan adalah MOS (Metal Oxide Semiconductor) dan bersifat volatile.
Gambar 1.4 – Gambar Semiconductor Storage berbentuk Single In-line Memory Module (SIMM)
4
E. Josephson Junction Diciptakan oleh Brian Josephson dari Inggris. Merupakan memori yang dapat melakukan switch dari bit 1 ke bit 0 atau sebaliknya dengan kecepatan yang tinggi, yaitu kurang dari sepertriliun detik. Menggunakan suatu tempat tertutup yang berisi helium cair dengan suhu sekitar -200 derajat celcius.
Gambar 1.5 – Gambar Josephson Junction Chip
F. Charged-Coupled Device (CCD) Merupakan memori yang terdiri dari ribuan metal bujur sangkar berukuran kecil yang masing-masing dapat menyimpan informasi digit binari dalam bentuk beban elektronik (electric charge)
Gambar 1.6 – Gambar Delta-Doped Charged Coupled Devices (CCD)
1.4. Hubungan Antara CPU dengan Main Memory dan Alat-Alat I/O Berikut ini adalah hubungan antara CPU dengan main memory dan alat-alat I/O: A. BUS Disebut juga pathway, merupakan suatu sirkuit yang merupakan jalur transportasi informasi antara dua atau lebih alat-alat dalam sistem komputer. Bus yang menghubungkan antara CPU dengan main memory disebut dengan internal bus, sedangkan yang menghubungkan CPU dengan alat-alat input/output disebut external bus.
5
Jenis-jenis bus : 1. Data bus, yaitu bus yang digunakan untuk jalur transportasi data dan instruksi; 2. Address bus, yaitu bus yang digunakan untuk jalur transportasi untuk alamat di main memory untuk data atau instruksi yang akan diambil atau direkam; 3. Control bus, yaitu bus yang digunakan untuk mengirimkan signal sebagai pemberitahuan akan dikirimkan suatu informasi atau telah diterimanya informasi yang dikirimkan dari satu alat ke alat yang lain.
Gambar 1.7 – Gambar Keterhubungan CPU, MM, dan I/O
Di dalam internal bus, hubungan antara CPU dengan main memory melalui data bus yang dihubungkan dengan memory data register (MDR), address bus yang dihubungkan dengan memory address register (MAR) dan control bus yang dihubungkan dengan control unit.
Gambar 1.8 – Gambar Keterhubungan CPU, MM, dan I/O melalui Register
6
B. I/O PORT Alat-alat input/output tidak dilekatkan langsung dengan bus tetapi melalui suatu I/O port atau I/O interface. Alat-alat input/output dapat berkomunikasi dengan CPU dengan cara mengirimkan informasi yang akan dikomunikasikan lewat bus. Informasi yang dikirim dari alat input/output (peripheral device) ke main memory atau ke register di CPU diletakan di I/O port dan dikirimkan lewat data bus. Demikian juga bila informasi dari main memory akan dikirimkan ke peripheral device juga melalui data bus dan diterima di I/O port. Cara ini disebut juga dengan program-controlled I/O. Cara ini banyak diterapkan pada alat I/O yang hanya dapat menangani satu karakter atau 1 byte atau 1 word saja tiap saat misalnya keyboard. C. DMA CONTROLLER Untuk peripheral device yang mempunyai kecepatan tinggi, tidaklah ekonomis untuk pengiriman informasi byte per byte atau word per word, dan akan lebih ekonomis bila pengiriman informasi dilakukan sekaligus per blok informasi. Bila informasi dikirim sekaligus per blok dan CPU harus selalu mengawasi pengiriman informasi, maka akan terjadi suatu waktu yang terbuang (idle time). DMA (Direct Memory Access) merupakan suatu konsep yang akan membuat komunikasi informasi antara peripheral device dengan main memory akan lebih efisien. DMA controller mempunyai suatu processor sendiri di dalamnya berupa IC khusus yang akan menangani operasi baca dan tulis antara main memory dan device peripheral. Dengan cara DMA ini, CPU cukup sekali saja memberi signal ke DMA controller untuk melakukan pengiriman sejumlah blok data antara main memory dengan device peripheral, yang selanjutnya urusan pengiriman data tersebut akan dilakukan oleh processor di DMA tanpa turut campur dari CPU, sehingga dapat melakukan pekerjaan yang lain. Cara DMA ini biasanya digunakan untuk device peripheral yang mempunyai kecepatan tinggi yang membutuhkan pengiriman blok data yang besar, misalnya hard disk drive.
7
D. I/O CHANNEL I/O Channel adalah suatu DMA controller yang digunakan bersama-sama untuk sejumlah alat-alat I/O. Masing-masing alat I/O dihubungkan dengan suatu channel lewat suatu controller. Sebuah controller dapat digunakan untuk sejumlah alat-alat I/O sejenis, misalnya akan digunakan dua atau lebih disk drive pada sebuah komputer.
1.5. Karakteristik Sistem Memori Adapun karakteristik sistem memori adalah sebagaimana tabel berikut: Karakteristik
Keterangan
Lokasi
1. 2. 3. 1. 2. 1. 2. 1. 2. 3. 4. 1. 2. 3. 1. 2. 1. 2.
Kapasitas Satuan Transfer Metode Akses
Kinerja Tipe Fisik Karakteristik Fisik
CPU Internal (main) External (secondary) Ukuran word Jumlah word Block Word Sequential Access Direct Access Random Access Associative Access Access Time Cycle Time Transfer Rate Semi konduktor Magnetik Volatile/Non-Volatile Eraseable/Non-Eraseable
Tabel 1.1. Tabel Karakteristik Sistem Memori
8
BAB II CACHE MEMORY
2.1. Cache Memory Cache memory merupakan lokasi data sementara antara prosesor dengan main memory. Penempatan cache memory ditujukan untuk mengurangi gap antara kecepatan prosesor dengan kecepatan main memory. Gambar 2.1. di bawah ini menunjukkan posisi cache memory yang diletakkan antara prosesor (CPU) dengan main memory. Sedangkan gambar 2.2. memperlihatkan sistem interkoneksi untuk cache memory.
CPU
Word Transfer
Cache Memory
Block Transfer
Main Memory
Gambar 2.1. Gambar Posisi Cache Memory pada Sistem Memory.
Gambar 2.2. Gambar Sistem Interkoneksi yang terkait dengan Cache Memory.
9
Cache berasal dari kata cash. Dari istilah tersebut cache adalah tempat menyembunyikan atau tempat menyimpan sementara. Sesuai definisi tersebut cache memory adalah tempat menympan data sementara. Cara ini dimaksudkan untuk meningkatkan transfer data dengan menyimpan data yang pernah diakses pada cache memory tersebut, sehingga apabila ada data yang ingin diakses adalah data yang sama maka maka akses akan dapat dilakukan lebih cepat. Cache memory ini adalah memori tipe SDRAM yang memiliki kapasitas terbatas namun memiliki kecepatan yang sangat tinggi dan harga yang lebih mahal dari memori utama. Cache memory ini terletak antara register dan RAM (memori utama) sehingga pemrosesan data tidak langsung mengacu pada memori utama. Karakteristik cache memory adalah sebagai berikut: Kapasitas relatif lebih kecil dari main memory, tetapi memiliki kecepatan yang relativ lebih tinggi dibanding main memory; Cache memory merupakan suatu memori buffer (salinan data) bagi memori utama; Meskipun cache menggunakan informasi yang tersimpan dalam memori utama, tetapi ia tidak berhadapan secara langsung dengan memori utama; Word yang disimpan didalam cache memory adalah word yang diambil dari main memory, yang dikerjakan sesuai perintah CPU.
2.2. Level Cache Memory Hingga saat ini, cache memory terbagi atas tiga level yaitu L1, L2 dan L3. Cache memory memori level 1 (L1) adalah cache memory yang terletak dalam prosesor (internal cache). Cache memory ini memiliki kecepatan akses paling tinggi dan harganya paling mahal. Ukuran memori berkembang mulai dari 8KB, 64KB dan 128KB. Cache memory level 2 (L2) memiliki kapasitas yang lebih besar yaitu berkisar antara 256KB sampai dengan 2MB. Namun, cache memory L2 ini memiliki kecepatan yang lebih rendah dari cache memory L1. Cache memory L2 terletak terpisah dengan prosesor atau disebut dengan external cache.
10
Sedangkan cache memory level 3 hanya dimiliki oleh prosesor yang memiliki unit lebih dari satu misalnya dualcore dan quadcore. Fungsinya adalah untuk mengontrol data yang masuk dari tembolok L2 dari masing-masing inti prosesor. Level 2 atau L2 cache merupakan bagian dari strategi penyimpanan multi level untuk meningkatkan performa komputer. Terdapat tiga level cache yang digunakan pada komputer, yaitu L1, L2 dan L3 cache. Tiap-tiap cache tersebut menjembatani jarak (gap) diantara processor yang sangat cepat, dengan memori RAM (Random Access Memory) yang jauh lebih lambat. Sementara desainnya terus mengalami perubahan, L1 cache biasanya telah terintegrasi (built in) ke dalam processor, sementara L2 cache biasanya terintegrasi pada motherboard (bersamaan dengan L2 cache). Namun, beberapa processor kini menggabungkan L2 cache serta L1 cache, dan bahkan beberapa diantaranya juga menggungkan L3 cache. Kecepatan yang paling tinggi terdapat pada L1 cache, kemudian menurun pada L2 dan L3 cache. Namun kebalikannya, semakin besar angka cache, maka semakin besar pula kapasitas penyimpanan datanya.
Gambar 2.3. Gambar Contoh Level Cache pada Processor.
Tugas dari cache processor adalah untuk mengantisipasi data request, sehingga ketika pengguna mengakses sebuah program yang sering digunakan, sebagai contohnya, instruksi-instruksi yang dibutuhkan untuk menjalankan program tersebut telah siap digunakan, disimpan pada cache. Ketika hal ini terjadi, CPU dapat memproses request tanpa adanya jeda (delay), sehingga dapat meningkatkan performa komputer secara drastis.
11
CPU pertama-tama akan memeriksa L1 cache, diikuti dengan L2 dan L3 cache. Jika processor telah menemukan bit data yang dibutuhkan, maka disebut dengan cache hit. Namun jika cache tidak menyediakan bit data yang dibutuhkan, processor mendapatkan sebuah cache miss, dan data perlu ditarik dari RAM yang lebih lambat atau hard disk yang juga lebih lambat.
2.3. Kapasitas Cache Menentukan ukuran cache memory sangatlah penting untuk mendongkrak kinerja komputer. Dari segi harga cache memory 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 memory yang besar (1MB) tetapi kinerjanya tidak bagus. Kemudian Intel pernah mengeluarkan prosesor tanpa cache memory 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 memory sekitar 128KB. Lalu berapa idealnya kapasitas cache memory? Sejumlah penelitian telah menganjurkan bahwa ukuran cache antara 1KB dan 512KB akan lebih optimum.
2.4. 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.
12
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 nilai optimum yang pasti telah ditemukan. Ukuran antara 4 hingga 8 satuan yang dapat dialamati (word atau byte) cukup beralasan untuk mendekati nilai optimum.
`
13
BAB III MAPPING CACHE MEMORY
3.1. Pemetaan Karena saluran cache memory lebih sedikit dibandingkan dengan blok memori utama, maka diperlukan algoritma untuk pemetaan blok memori utama ke dalam saluran cache memory. Pemilihan terhadap fungsi pemetaan akan sangat menentukan bentuk organisasi cache memory. Telah kita ketahui bahwa cache memory mempunyai kapasitas yang kecil dibandingkan memori utama. Sehingga diperlukan aturan blok-blok mana yang diletakkan dalam cache memory. Terdapat tiga metode, yaitu pemetaan langsung (direct mapping), pemetaan asosiatif, dan pemetaan asosiatif set. 1. Direct Mapping Setiap blok pada main memory dipetakan dengan line tertentu pada cache. i = j modulo C di mana i adalah nomor line pada cache yang digunakan untuk meletakkan blok main memory ke-j. Jika M = 64 dan C = 4, maka pemetaan antara line dengan blok menjadi seperti berikut : Line 0 can hold blocks 0, 4, 8, 12, ... Line 1 can hold blocks 1, 5, 9, 13, ... Line 2 can hold blocks 2, 6, 10, 14, ... Line 3 can hold blocks 3, 7, 11, 15, ... Pada cara ini, address pada main memory dibagi 3 field atau bagian, yaitu: o
Tag identifier.
o
Line number identifier
o
Word identifier (offset)
Pada gambar 3.1. tampak skema organisasi cache secara Direct Mapping.
14
Word identifier berisi informasi tentang lokasi word atau unit addressable lainnya dalam line tertentu pada cache. Line identifier berisi informasi tentang nomor fisik (bukan logika) line pada cache. Tag identifier disimpan pada cache bersama dengan blok pada line. o
Untuk setiap alamat memory yang dibuat oleh CPU, line tertentu yang menyimpan copy alamat tsb ditentukan, jika blok tempat lokasi data tersebut sudah dikopi dari main memory ke cache.
o
Tag yang ada pada line akan dicek untuk melihat apakah benar blok yang dimaksud ada pada line tsb.
Gambar 3.1. Gambar Organisasi Direct Mapping.
Keuntungan menggunakan Direct Mapping antara lain: Mudah dan murah diimplementasikan. Mudah untuk menentukan letak salinan data main memory pada cache.
15
Kerugian menggunakan Direct Mapping antara lain: Setiap blok main memory hanya dipetakan pada 1 line saja. Terkait dengan sifat lokal pada main memory, sangat mungkin mengakses blok yang dipetakan pada line yang sama pada cache. Blok seperti ini akan menyebabkan seringnya sapu masuk dan keluar data ke/dari cache, sehingga hit ratio mengecil. Hit ratio adalah perbandingan antara jumlah ditemukannya data pada cache dengan jumlah usaha mengakses cache.
Gambar 3.2. Gambar Contoh Pengalamatan Direct Mapping.
16
Ringkasan direct mapping nampak pada tabel berikut: Item
Keterangan
Panjang alamat Jumlah unit yang dapat dialamati Ukuran Blok sama dengan ukuran Line Jumlah blok di memori utama Jumlah line di cache Besarnya tag
(s + w) bits 2s+w words or bytes 2w words or bytes 2s+ w/2w = 2s m = 2r (s – r) bits
Tabel 3.1. Tabel Direct Mapping
2. Associative Mapping Memungkinkan blok diletakkan di sebarang line yang sedang tidak terpakai. Diharapkan akan mengatasi kelemahan utama Direct Mapping. Harus menguji setiap cache untuk menemukan blok yang diinginkan. o
Mengecek setiap tag pada line
o
Sangat lambat untuk cache berukuran besar.
Nomor line menjadi tidak berarti. Address main memory dibagi menjadi 2 field saja, yaitu tag dan word offset.
Gambar 3.3. Gambar Organisasi Associative Mapping.
17
Melakukan pencarian ke semua tag untuk menemukan blok. Cache dibagi menjadi 2 bagian : o
lines dalam SRAM
o
tag dalam associative memory
Gambar 3.4. Gambar Contoh Pengalamatan Associative Mapping.
Keuntungan Associative Mapping: cepat dan fleksibel. Kerugiannya: biaya implementasi. Misalnya : untuk cache ukuran 8 kbyte dibutuhkan 1024 x 17 bit associative memory untuk menyimpan tag identifier.
18
Ringkasan associative mapping nampak pada tabel berikut: Item
Keterangan
Panjang alamat Jumlah unit yang dapat dialamati Ukuran Blok sama dengan ukuran Line Jumlah blok di memori utama Jumlah line di cache Besarnya tag
(s + w) bits 2s+w words or bytes 2w words or bytes 2s+ w/2w = 2s undetermined s bits
Tabel 3.2. Tabel Associative Mapping
3. Set Associative Mapping Merupakan kompromi antara Direct dengan Full Associative Mapping. Membagi cache menjadi sejumlah set (v) yang masing-masing memiliki sejumlah line (k) Setiap blok dapat diletakkan di sebarang line dengan nomor set: nomor set = j modulo v
Gambar 3.5. Gambar Organisasi K-Way Set Associative Mapping.
19
Jika sebuah set dapat menampung X line, maka cache disebut memiliki Xway set associative cache. Hampir semua cache yang digunakan saat ini menggunakan organisasi 2 atau 4-way set associative mapping.
Gambar 3.6. Gambar Contoh Pengalamatan 2-Way Associative Mapping.
Keuntungan menggunakan Set Associative Mapping antara lain: Setiap blok memori dapat menempati lebih dari satu kemungkinan nomor line (dapat menggunakan line yang kosong), sehingga thrashing dapat diperkecil Jumlah tag lebih sedikit (dibanding model associative), sehingga jalur untuk melakukan perbandingan tag lebih sederhana.
20
Ringkasan set associative mapping nampak pada tabel berikut: Item
Keterangan
Panjang alamat Jumlah unit yang dapat dialamati Ukuran Blok sama dengan ukuran Line Jumlah blok di memori utama Jumlah line dalam set Jumlah set Jumlah line di cache Besarnya tag
(s + w) bits 2s+w words or bytes 2w words or bytes 2d k V=2d Kv = k*2d (s-d) bits
Tabel 3.3. Tabel Set Associative Mapping
3.2. Algoritma Penggantian Yang dimaksud algoritma penggantian adalah suatu mekanisme pergantian blokblok dalam cache memory yang lama dengan data baru. Dalam pemetaan langsung tidak diperlukan algoritma ini, namun dalam pemetaan asosiatif dan asosiatif set, algoritma ini mempunyai peranan penting untuk meningkatkan kinerja cache memory. Banyak algoritma penggantian yang telah dikembangkan. Algoritma yang paling efektif adalah Least Recently Used (LRU), yaitu mengganti blok data yang terlama berada dalam cache memory dan tidak memiliki referensi. Algoritma lainnya adalah First In First Out (FIFO), yaitu mengganti blok data yang awal masuk. Kemudian Least Frequently Used (LFU) adalah mengganti blok data yang mempunyai referensi paling sedikit. Teknik lain adalah algoritma Random, yaitu penggantian tidak berdasakan pemakaian datanya, melainkan berdasarkan slot dari beberapa slot kandidat secara acak.
21
3.3. Write Policy Apabila suatu data telah diletakkan pada cache memory maka sebelum ada penggantian harus dicek apakah data tersebut telah mengalami perubahan. Apabila telah berubah maka data pada memori utama harus di-update. Masalah penulisan ini sangat komplek, apalagi memori utama dapat diakses langsung oleh modul I/O, yang memungkinkan data pada memori utama berubah, lalu bagaimana dengan data yang telah dikirim pada cache? Tentunya perbedaan ini menjadikan data tidak valid. Teknik yang dikenalkan diantaranya, write through, yaitu operasi penulisan melibatkan data pada memori utama dan sekaligus pada cache memory sehingga data selalu valid. Kekurangan teknik ini adalah menjadikan lalu lintas data ke memori utama dan cache memory sangat tinggi sehingga mengurangi kinerja sistem, bahkan bisa terjadi hang. Teknik lainnya adalah write back, yaitu teknik meminimasi penulisan dengan cara penulisan pada cache memory saja. Pada saat akan terjadi penggantian blok data cache memory maka baru diadakan penulisan pada memori utama. Masalah yang timbul adalah manakala data di memori utama belum diupdate telah diakses modul I/O sehingga data di memori utama tidak valid. Penggunaan multi cache terutama untuk multiprocessor adan menjumpai masalah yang lebih komplek. Masalah validasi data tidak hanya antara cache memory dan memori utama saja, namun antar cache memory juga harus diperhatikan. Pendekatan penyelesaian masalah yang dapat dilakukan adalah dengan : Bus Watching with Write Through, yaitu setiap cache controller akan memonitoring bus alamat untuk mendeteksi adanya operasi tulis. Apabila ada operasi tulis di alamat yang datanya digunakan bersama maka cache controller akan menginvalidasi data cache-nya. Hardware Transparency, yaitu adanya perangkat keras tambahan yang menjamin semua updating data memori utama melalui cache direfleksikan pada seluruh cache yang ada. Non Cacheable Memory, yaitu hanya bagian memori utama tertentu yang digunakan secara bersama. Apabila ada mengaksesan data yang tidak di share merupakan kegagalan cache.
22
3.4. Miss Cache Saat miss menulis, anda bisa punya pilihan antara membawa blok ke cache (writeallocate) atau tidak (write-no-allocate). Saat miss membaca, anda selalu membawa blok ke cache (lokalitas spasial atau temporal) - blok mana yang diganti:
tidak ada pilihan untuk direct-mapped cache
memilih secara acak way yang akan diganti
mengganti way yang paling jarang dipakai (LRU)
penggantian FIFO (round-robin)
Tipe miss cache adalah sebagai berikut: Miss wajib: terjadi saat pertama kali word memori diakses. Merupakan miss untuk cache yang infinit. Miss kapasitas: terjadi karena program menyentuh banyak word yang lain sebelum menyentuh ulang word yang sama. Merupakan miss untuk cache fullyassociative. Miss konflik: terjadi karena dua work dipetakan ke lokasi yg sama di cache. Merupakan miss yang terjadi ketika berganti dari cache fully-associative ke direct-mapped.
23
BAB IV PENUTUP
Cache memory merupakan memori yang memiliki kecepatan sangat tinggi, digunakan sebagai perantara antara Main Memory dan CPU. Memori ini mempunyai kecepatan lebih tinggi daripada Main Memory, namun harganya lebih mahal. Cache memory digunakan untuk menjembatani perbedaan kecepatan CPU yang sangat tinggi dengan kecepatan RAM yang jauh lebih rendah. Dengan menggunakan cache memory, sejumlah data dapat dipindahkan ke memori ini dalam sekali waktu, dan kemudian ALU akan mengambil data tersebut dari memori ini. Dengan pendekatan seperti ini, pemrosesan data dapat dilakukan lebih cepat daripada kalau CPU mengambil data secara langsung dari RAM.
24
DAFTAR PUSTAKA
Stallings, William. 2010. Computer Organization and Architecture 8th Edition. Prentice Hall. Daftar Website: http://en.wikipedia.org/wiki/Cache_coherency http://en.wikipedia.org/wiki/Cache_algorithms http://williamstallings.com/ComputerOrganization/COA8e-Instructor/index.html http://www.tomshardware.com/reviews/athlon-l3-cache,2416-2.html
25
LAMPIRAN Processor
Type
Year
IBM 360/85
Mainframe
1968
PDP-11/70
Minicomputer
WAX 11/780
L1 Cache
L2 Cache
L3 Cache
16-32KB
-
-
1975
1KB
-
-
Minicomputer
1978
16KB
-
-
IBM 3033
Mainframe
1978
64KB
-
-
IBM 3090
Mainframe
1985
126-256KB
-
-
Intel 80486
PC
1989
8KB
-
-
Pentium
PC
1993
8KB
256-512KB
-
PowerPC 601
PC
1993
32KB
-
-
PowerPC 620
PC
1996
32KB
-
-
PowerPC G4
PC/Server
1999
32KB
256KB-1MB
-
IBM S/390 G4
Mainframe
1997
32KB
245KB
2MB
IBM S/390 G6
Mainframe
1999
256KB
8MB
2MB
Pentium 4
PC/Server
2000
8KB/8KB
256KB
-
IBM SP
High-end server
2000
64KB/32KB
8MB
-
Cray MTA
Supercomputer
2000
8KB
2MB
-
Itanium
PC/Server
2001
16KB/16KB
96KB
4MB
SGI Origin 2001
High-end server
2001
32KB/32KB
4MB
-
Itanium 2
PC/Server
2002
32 KB
256KB
6MB
IBM Power5
High-end server
2003
64KB
1.9MB
36MB
Cray XD-1
Supercomputer
2004
64KB/64KB
1MB
-
Tabel Perbandingan Cache Size. Sumber William Stalling.
26
Gambar Perbandingan Kecepatan Akses antara CPU dan Main Memory
27
