Cache, Memori Virtual, Dasar - Dasar I/O • Topik Hari Ini: Hirarki cache Memori virtual Overview I/O Dasar - dasar disk RAID
1
Hirarki Cache •Data dan instruksi disimpan dalam chip DRAM - DRAM adalah teknologi dengan densitas bit yang tinggi, tapi buruk di latensi - sebuah akses data ke memori membutuhkan 300 siklus! •Maka, sebagian data disimpan di dalam prosesor dalam struktur yang dinamakan cache - cache menggunakan teknologi SRAM, yang lebih cepat, tapi densitas bitnya lebih rendah •Browser Internet juga me-cache halaman web - konsep yang sama 2
Hirarki Memori •Semakin jauh, kapasitas dan latensi bertambah
Register 1KB 1 siklus
Cache L1 data atau instruksi 32KB 2 siklus
Cache L2 2MB 15 siklus
Memori 1GB 300 siklus
Disk 80 GB 10M siklus
3
Lokalitas •Mengapa cache berfungsi? •Lokalitas temporal: jika anda akhir - akhir ini menggunakan beberapa data, anda sangat mungkin akan menggunakan lagi •Lokalitas spasial: jika anda akhir - akhir ini menggunakan beberapa data, anda sangat mungkin akan mengakses data di sekitarnya •Tanpa hirarki: rata - rata waktu akses untuk data: 300 siklus •32 KB 1-siklus cache L1 yang memiliki laju hit 95%: rata - rata waktu akses = 0.95 x 1 + 0.05 x (301) = 16 siklus
4
Mengakses Cache Byte address 101000 Offset 8-byte words
8 words: 3 index bits Direct-mapped cache: setiap address dipetakan ke sebuah alamat yg unik Sets Data array
5
Array dari Tag Byte address 101000 Tag 8-byte words
Compare Direct-mapped cache: setiap address dipetakan ke sebuah alamat yg unik
Tag array
Data array
6
Contoh Pola Akses Byte address 101000
Asumsi addressnya memiliki lebar 8 bit Berapakah yang meminta address berikut yang hit / miss? 4, 7, 10, 13, 16, 68, 73, 78, 83, 88, 4, 7, 10…
Tag 8-byte words
Compare Direct-mapped cache: setiap address dipetakan ke sebuah alamat yg unik
Tag array
Data array
7
Meningkatkan Ukuran Line Byte address 10100000 Tag
Array tag
Ukuran line cache yg lebih besar array tag yg lebih kecil, miss yg lebih sedikit krn lokalitas spasial 32-byte cache line size or block size
Offset
Array data
8
Associativity Byte address 10100000 Tag
Tag array
Associativity set konflik yg lbh sedikit; power banyak terbuang karena pembacaan data dan tag yang ganda Way-1
Perbandingan
Way-2
Array Data
9
Associativity Byte address
Berapa banyak hit offset/indeks/tag jika sebuah cache memiliki 64 set, setiap set memiliki 64 byte, 4 way?
10100000 Tag
Array tag
Way-1
Perbandingan
Way-2
Array Data
10
Contoh •Data cache sebesar 32 KB 4-way set-associative dengan 32 byte ukuran line •Berapa set? •Berapa bit indeks, bit offset, bit tag? •Berapa besar array tagnya?
11
Miss dari Cache •Saat miss menulis, anda bisa punya pilihan antara membawa blok ke cache (write-allocate) 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)
12
Menulis / Write •Ketika kita menulis ke sebuah blok, apakah juga membaharui kopi di L2? write-through: setiap menulis di L1 -> menulis di L2 write-back: tandai blok sebagai kotor, kemudian blok diganti dari L1, ditulis ke L2 •Writeback menggabungkan menulis ganda dalam sebuah blok L1 menjadi menulis tunggal di L2 •Writethough menyederhanakan koherensi protokol dalam sistem multiprosesor dimana L2 selalu memiliki kopi data •yang terbaru 13
Tipe dari Miss di Cache •Miss wajib: terjadi saat pertama kali word memori diakses - miss untuk cache yang infinit •Miss kapasitas: terjadi karena program menyentuh banyak word yang lain sebelum menyentuh ulang word yang sama - miss untuk cache fully-associative •Miss konflik: terjadi karena dua work dipetakan ke lokasi yg sama di cache - miss yang terjadi ketika berganti dari cache fully-associative ke direct-mapped
14
Memori Virtual •Proses - proses berhubugan dengan memori virtual - terdapat ilusi bahwa tersedia ruang alamat / address yang sangat besar •Terdapat memori fisik yang terbatas yang dibagi oleh semua proses - sebuah proses menempatkan sebagian dari memori virtualnya di memori fisik dan sisanya disim pan di disk (disebut swap space) •Berkat lokalitas, akses ke disk kemungkinan sangat jarang •Perangkat keras memastikan bahwa satu proses tidak dpt mengakses memori dari proses yang lainnya 15
Terjemahan Alamat / Address •Memori virtual dan fisik dipecah menjadi halaman / pages
ukuran halaman 8KB
Alamat virtual 13 nomor halaman offset halaman virtual Diterjemahkan ke nomor halaman fisik
Alamat fisik 16
Karakteristik Hirarki Memori •Sebuah halaman memori virtual dapat ditempatkan dimana pun di memori fisk (fully-associative) •Penggantian biasanya LRU (karena penalti krn miss besar, kita bisa investasi usaha disini untuk meminalisir miss) •Sebuah tabel halaman (di-indeks oleh nomor halaman virtual dipergunakan untuk menterjemahkan nomor halaman virtual ke fisik •Tabel halaman sendiri terdapat di memori 17
TLB •Karena jumlah halaman sangat besar, kapasitas tabel halaman terlalu banyak utk dimasukkan dalam chip •Sebuah translation lookaside buffer (TLB) meng-cache terjemahan nomor halaman virtual ke fisik untuk akses yang terkini •Sebuah miss TLB membutuhkan sebuah akses ke tabel halaman, yg mungkin tdk ditemukan di cache - akses memori look-ups yang mahal 2 kali untuk mengambil satu word data! •Sebuah ukuran halaman yg besar dpt meningkatkan kisaran TLB dan mengurangin kapasitas dari tabel halaman, 18 tapi juga meningkatkan pemborosan memori
TLB dan Cache •Apakah cache perlu di-indeks dengan alamat virtual atau fisik? – Untuk meng-indeks dgn alamat fisik, kita pertama harus melihat TLB, baru cache -> waktu akses lbh lama – Alamat - alamat virtual yg ganda dapat memetakan ke alamat fisik yg sama - harus memastikan bahwa alamat virtual yg berbeda ini akan memetakan ke lokasi yg sama di cache - kalau tdk, akan terdapat dua kopi yg – berbeda untuk word di memori fisik yg sama. •Apakah array tag menyimpan alamat virtual atau fisik? – Karena alamat virtual ganda dapat memetakan alamat fisik yg sama, sebuah perbandingan tag virtual dapat menandakan sebuah miss meskipun terdapat word di 19 – memori fisik yg benar
Cache dan Pipeline TLB
Alamat virtual No. halaman virtual
indeks Virtual
Offset
TLB Tag array
Data array
No. halaman fisik Tag fisik Perbandingan tag fisik
Di-indeks secara virtual; Cache di-tag secara fisik 20
Kejadian - kejadian buruk •Pertimbangkan latency terlama yg mungkin utk instruksi load: – miss TLB: harus lihat table halaman ukt mencari terjemahn v.page P – Menghitung alamat memori virtual untuk entri tabel halaman yg mempunyai terjemahan utk page P - misalnya disebut v.page Q – miss TLB untuk v.page Q: membutuhkan navigasi dari hirarki tabel halaman (utk sementara diabaikan, anggap berhasil dapat lokasi memori (R) utk halaman Q) – Mengakses lokasi memori R (terlekat mungkin di L1, L2, atau memori) – Sekarang kita dapat terjemahan utk v.page P - dimasukkan ke TLB – Sekarang mendapat hit TLB dan mengetahui nomor halaman fisik ini memungkinkan kita untuk perbandingan tag dan cek cache L1 utk hit – Jika terjadi miss di L1, cek L2 - jika miss juga, cek di memori – Di kejadian manapun, jika entri di tabel halaman mengklaim bahwa halaman ada di disk, diindikasikan page fault - kemudian OS mengkopi halaman dari disk ke memori dan perangkat keras kembali ke pekerjaan sebelumnya ... (panjang bgt!) 21
Input/Output
CPU Cache
Bus
Memory
Disk
Network
USB
DVD
…
22
Hirarki I/O CPU Cache
Memory Bus
Memory
Disk
I/O Controller
I/O Bus
Network
USB
DVD
… 23
Contoh di Intel P4 Processor System bus 800 MHz, 604 GB/sec Memory 2.1 GB/sec Graphics output Main DDR 400 Controller Memory 3.2 GB/sec Hub (North Bridge) 266 MB/sec 1 Gb Ethernet
Disk
Serial ATA 150 MB/s
266 MB/sec 100 MB/s
I/O Controller Hub USB 2.0 60 MB/s (South Bridge)
100 MB/s
CD/DVD Tape
24
Desain Bus •Bus adalah sumberdaya yg di-share - semua perangkat dapat mengirim data ke bus (setelah sebelumnya mengumumkannya) dan perangkat yg lain akan membaca data ini dari bus •Signal - signal alamat / kontrol pada bus menyatakan siapakah penerima yg dituju dari pesan ini. •Panjang dari bus menentukan kecepatannya (maka, sebuah hirarki sangat masuk akal) •Bus - bus dapat synchronous (sebuah clock menentukan kapan operasi harus dilakukan) atau asynchronous (sebuah protokol handshaking dipergunakan untuk koordinasi operasi 25
Memory-Mapped I/O •Setiap perangkat I/O memiliki kisaran alamatnya sendiri – CPU akan mengeluarkan perintah seperti ini: • sw [bbrp data][bbrp alamat] – Biasanya, memori melayani permintaan ini ... jika alamat di kisaran I/O, memori akan mengabaikan – Data ditulis dalam beberapa register di perangkat I/O yg sesuai - ini berfungsi sebagai perintah – ke perangkat tersebut
26
Polling Vs. Interrupt-Driven •Ketika sebuah perangkat I/O siap untuk merespon, ia dapat mengirimkan sebuah interrupt ke CPI; CPU menghentikan kegiatannya; OS memeriksa interrupt dan membaca data yg dihasilkan perangkat I/O (dan biasanya disimpan di memori) •Di pendekatan secara polling, CPU (OS) secara periodik mengecek status perangkat I/O dan jika perangkatnya siap •dengan data, maka OS akan membacanya
27
Direct Memory Access (DMA) •Pertimbangkan contoh pembacaan disk: sebuah blok di disk dibaca ke memori •Untuk setiap word, CPU melakukan lw [register tujuan][alamat perangkat I/O] dan sw[data di register diatas][alamat memori] •Tugas ini membutuhkan CPU time yg terlalu lama - maka, tugas ini dilimpahkan ke kontroler DMA - CPU memberitahu DMA kisaran alamat yg perlu dikopi dan DMA akan memberitahu CPU apabila sudah selesai membaca 28
Peran dari I/O •Aktifitas ke luar CPU biasanya jauh lebih lambat •Contoh: ketika kinerja CPU bertambah 50% per tahun, latensi disk hanya bertambah 10% per tahun •Strategi yg biasa di I/O: pindah konteks dan bekerja ke hal yg lainnya •Metriks yang lainnya, seperti lebar pita, kehandalan, ketersediaan, dan kapasitas, sering menerima pertian yang lebih daripada kinerja 29
Disk Magnetik •Sebuah disk magnetik terdiri dari 1 - 12 plat (disk logam atau kaca yang dibungkus oleh material penyimpan magnetik pada kedua sisi), dgn diameter 1 - 3.5 inchi •Setiap plat terdiri dari jalur (track) konsentris (5 - 30K) dan setiap jalur dibagi menjadi sektor (100 - 500 setiap jalur, masing - masing sekitar 512 bytes) • Lengan bergerak membawa head untuk baca / tulis di setiap permukaan dan menggerakkan semuanya secara bersamaan (tandem) - sebuah silinder dari data dapat diakses pada suatu waktu. 30
Latensi dari Disk •Untuk baca / tulis data, lengan harus ditempatkan pada jalur yg tepat - waktu cari (seek time) ini biasanya 5 - 12 ms rata - rata - dapat lebih pendek apabila ada lokalitas spasial. •Latensi rotasional adalah waktu yang dibutuhkan untuk berotasi di sektor yang tepat dibawah head - rata-ratanya secara tipikal lebih dari 2 ms (15,000 rpm) •Waktu transfer (transfer time) adalah waktu untuk mentransfer blok dari bits keluar dari disk dan biasanya 3 - 65 MB / detik. • Sebuah kontroler disk memelihara sebuah cache disk (lokalitas spasial dapat dieksplorasi) dan menyusun transfer ke bus (overhead dari kontroler). 31
Mendefinisikan Kehandalan dan Ketersediaan •Sebuah sistem akan berganti diantara Pemenuhan layanan: layanan yang memenuhi spesifikasi Interupsi layanan: layanan yang diluar spesifikasi •Pergantian ini disebabkan karena kegagalan dan restorasi •Kehandalan (reliability) mengukur keberlanjutan pemenuhan layanan dan biasanya dinyatakan sebagai mean time to failur (MTTF) •Ketersediaan (availability) mengukur pecahan waktu dimana layanan sesuai dgn spesifikasi, dinyatakan dlm •MTTF / (MTTF + MTTR) 32
Kinerja I/O •Throughput (lebar pita) dan waktu respon (latensi) adalah metrik kinerja kunci untuk I/O •Deskripsi dari perangkat lunak menjelaskan karakteristik dari throughput maksimum dan rata-rata waktu respon (biasanya tanpa delay krn queue). •Deskripsi dari workload menjelaskan karakteristik dari throughput “sebenarnya” - bersamaan dengan sebiah rata - rata waktu respon
33
Throughput Vs. Waktu Respon •Saat load meningkat, throughput meningkat (tingkat utilisasi tinggi) - secara bersamaan, waktu respon juga meningkat karena probabilititas untuk menunggu layanan juga meningkat: imbal-balik antara throughput dan waktu respon. •Dalam sistem yang menyertakan interaksi manusia, terdapat tiga delay relevan: waktu entri data, waktu respon sistem, dan waktu berpikir - studi menunjukkan bahwa peningkatan waktu respon menghasilkan peningkatan waktu berpikir waktu respon dan throughput yg lebih baik •Kebanyakan kumpulan benchmark mencoba menentukan throughput ketika menempatkan batasan untuk waktu respon 34
RAID 0 dan RAID 1 •RAID 0 tidak memiliki redundansi tambahan (misnomer) - menggunakan rangkaian disk dan men-strip (menggabungkan) data sepanjang rangkaian untuk meningkatkan paralelitas dan throughput •RAID 1 me-mirror dan me-shadow setiap disk - setiap tulis terjadi di dua disk. • Baca ke mirror mungkin terjadi hanya ketika disk primer gagal - atau, anda mencoba membaca keduanya bersamaan dan respon yg lebih cepat yang diterima. •Solusi mahal: kehandalan tinggi dengan biaya 2 kali lipat 35
RAID 3 •Data di interleaved secara bit sepanjang beberapa disk dan disk yg berbeda akan memelihara informasi parity dari bit set. •Sebagai contoh: dgn 8 disk, bit 0 di disk-0, bit 1 di disk-1, ..., bit 7 di disk-7; disk-8 memelihara parity dari semua 8 bits •Untuk setiap baca, ke-8 disk harus diakses (kita biasanya membaca lebih dari satu byte sekali waktu) dan untuk setiap tulis, 9 disk harus diakses karena parity harus dihitung ulang •Throughput yg tinggi untuk permintaan (request) tunggal, biaya rendah utk redundansi (overhead: 12.5%), paralelisme tingkat tugas rendah (low task-level) 36
RAID 4 dan RAID 5 •Data di interleaved dalam blok - ini mengijikan kita untuk mendapatkan data dalam disk tunggal saat baca - jika error, membaca dari semua 9 disk. •Interleaving dalam blok mengurangi throughput untuk request tunggal (karena disk tunggal melayani request), tapi meningkatkan paralelisme task-level karena disk yg lain bebas utk melayani request yg lainnya. • Saat nulis, kita mengakses disk yg menyimpan data dan disk parity - informasi parity dapat diperbarui hanya dengan mencheck apakah data baru berbeda dari data lama 37
RAID 5 •Jika kita memiliki disk tunggal utk parity, menulis secara multipel tidak dapat terjadi secara paralel (karena semua nulis harus memperbarui informasi parity) •RAID 5 mendistribusikan blok parity untuk mengijinkan •penulisan secara simultan (bersamaan).
38
Ringkasan RAID •RAID 1-5 mentoleransi sebuah fault tunggal - mirroring (RAID 1) memiliki overhead 100%, namun parity (RAID 3,4,5) memiliki overhead yg minim •RAID 6 dan RAID 2 (memory-style ECC) tidak •diaplikasikan secara komersial
39
