Organisasi Sistem Komputer. Hirarki Memori. Sekolah Teknik Elektro dan Informatika ITB

Organisasi Sistem Komputer

Bagian 9 Hirarki Memori

Sekolah Teknik Elektro dan Informatika ITB 2009 1

Pembahasan e d te o og pe y pa a Trend teknologi penyimpanan Referensi locality Cache pada hirarki memori

2

Random Access Memory (RAM) Karakteristik

ƒ RAM dibungkus paket dib k dalam d l k berbentuk b b k chip hi ƒ Satuan penyimpanan dasar adalah sel (1 bit per sel) ƒ Gabungan beberapa chip RAM membentuk memori

Static RAM (SRAM) ƒ ƒ ƒ ƒ

Setiap sel menyimpan bit dalam rangkaian dgn enam transistor Datanya akan bertahan terus, selama diberi daya Relatif tahan terhadap gangguan, seperti noise Lebih cepat dan mahal dari DRAM

ƒ ƒ ƒ ƒ

Setiap sel menyimpan bit dalam kapasitor dan transistor D t Datanya h harus di di-refresh f h setiap ti 10-100 10 100 ms Sensitif terhadap gangguan Lebih lambat dan murah dibandingkan dengan SRAM

Dynamic RAM (DRAM)

3

Perbandingan SRAM vs DRAM

Transistor per bit

Waktu akses

Data bertahan

Sensitif

Harga

Aplikasi

SRAM

6

x1

ya

tidak

x 100

Cache memory

DRAM

1

x 10

tidak

ya

x1

Main memory

4

Organisasi DRAM Konvensional Total d x w bit, disimpan dalam d buah supersel berukuran w bit 16 x 8 DRAM chip 0 2 bit /

kolom 1 2

3

0

alamat

1 baris

memory controller

supersel (2,1)

2

(ke CPU) 8 bit /

3

data

buffer baris internal 5

Membaca DRAM – Supersel (2,1) Langkah 1(a): Row access strobe (RAS) memilih baris ke 2. Langkah 1(b): Baris 2 disalin dari DRAM array ke buffer baris. 16 x 8 DRAM chip 0

RAS = 2 2 /

kolom 1 2

3

0

alamat 1 baris

memory controller

2 8 /

3

data

Buffer baris internal 6

Membaca DRAM – Supersel (2,1) Langkah 2(a): Column access strobe (CAS) memilih kolom 1. Langkah 2(b): Supercell (2,1) disalin dari buffer ke saluran data & dikirim ke CPU 16 x 8 DRAM chip 0 CAS = 1 2 /

3

0

alamat

ke CPU

1 b i baris

memory controller supersel p (2,1)

kolom 1 2

2 8 /

3

data

supersel (2,1)

Buffer baris internal 7

Modul Memori alamat (baris = i, kolom = j) : supersel p (i,j) ( j) DRAM 0

Modul memori 64 MB terdiri dari : 8M x 8 DRAM (baris x kolom)

DRAM 7

bit bit bit bit bit bit bit 56-63 48-55 40-47 32-39 24-31 16-23 8-15

63

56 55

48 47

40 39

32 31

24 23 16 15

8 7

bit 0-7

0

64-bit doubleword pd main memory alamat A

64-bit doubleword

Memory controller

8

Enhanced DRAM Seluruh DRAM yang ada saat ini dibangun berdasarkan DRAM konvensional, k i l yaitu it : ƒ Fast Page Mode DRAM (FPM DRAM) ƒ Mengakses isi baris secara [RAS, CAS, CAS, CAS], bukan [(RAS,CAS), ((RAS,CAS), ) (RAS,CAS), ( ) (RAS,CAS)] ( )]

ƒ Extended Data Output DRAM (EDO DRAM) ƒ Peningkatan FPM DRAM, jarak antara sinyal CAS lebih dekat

ƒ Synchronous DRAM (SDRAM) ƒ Dikendalikan Dik d lik secara sinkron i k pada d sisi i i clock l k naik ik

ƒ Double Data-Rate Synchronous DRAM (DDR SDRAM) ƒ Peningkatan SDRAM, sinyal kontrol menggunakan kedua sisi clock

ƒ Video RAM (VRAM) ƒ Seperti FPM DRAM, output diperoleh dengan menggeser buffer baris (shift) ƒ Memiliki dua port (dapat melakukan proses baca dan tulis secara bersamaan

9

Nonvolatile Memory DRAM dan SRAM termasuk kategori volatile memory ƒ Informasi hilang jika daya listrik dimatikan

Nonvolatile memory dapat mempertahankan isinya walaupun daya dimatikan ƒ Nama g generiknya y adalah read-onlyy memoryy ((ROM)) ƒ Terjadi salah arti, karena beberapa ROM dapat dimodifikasi

Jenis-jenis ROM ƒ ƒ ƒ ƒ

Programmable ROM (PROM) Eraseable Programmable ROM (EPROM) Electrically Eraseable PROM (EEPROM) Flash memory

Firmware

ƒ Program yang disimpan di ROM

ƒ Boot time code, BIOS (basic input/output system) ƒ Graphic card, disk controller

10

Struktur Bus CPU-Memori Bus adalah kumpulan saluran paralel yang mengalirkan sinyal alamat, data dan kontrol. Umumnya digunakan bersama oleh beberapa devais. CPU chip register file ALU system bus

bus interface

I/O bridge

memory bus

main memory

11

Proses Membaca Memori (1) CPU meletakkan alamat A pada memory bus. register file %eax

Operasi LOAD : movl A, %eax ALU

I/O bridge bus interface

A

main memory 0 x

A

12

Proses Membaca Memori (2) Main memory membaca A dari memory bus, mengambil word x, dan meletakkannya da e eta a ya pada bus register file %eax

Operasi LOAD : movl A, %eax ALU

I/O bridge bus interface

x

main memory 0 x

A

13

Proses Membaca Memori (3) CPU membaca word x dari bus dan menyalinnya ke register %eax register file %eax

x

Operasi LOAD : movl A, %eax ALU

I/O bridge bus interface

main memory 0 x

A

14

Proses Menulis ke Memori (1) CPU meletakkan alamat A pada bus. Main memory membacanya dan menunggu da e u ggu munculnya u cu ya word o d data. data register file %eax

y

Operasi STORE : movl %eax, A ALU

I/O bridge bus interface

A

main memory 0 A

15

Proses Menulis ke Memori (2) CPU meletakkan word data y pada bus register file %eax

y

Operasi STORE : movl %eax, A ALU

I/O bridge bus interface

y

main memory 0 A

16

Proses Menulis ke Memori (3) Main memory membaca word data y dari bus dan menyimpannya di alamat l t A. A register file %eax

y

Operasi STORE : movl %eax, A ALU

I/O bridge bus interface

main memory 0 y

A

17

Hard Disk Hard disk terdiri dari beberapa piringan, masing-masing memiliki dua permukaan. Pada d setiap i permukaan k terdapat d li k lingkaran konsentrik k ik yang disebut di b track. k Setiap track terbagi atas beberapa sektor yang dipisahkan oleh jarak tertentu (gap). track permukaan track k

gap

Pemutar (spindle)

sektor 18

Geometri Hard Disk Track pada jalur yang sama membentuk silinder silinder k permukaan 0 piringan 0

permukaan 1 permukaan 2 permukaan 3 permukaan 4 permukaan 5

piringan 1 piringan 2

spindle

19

Kapasitas Hard Disk Kapasitas : banyaknya bit maksimum yang dapat disimpan ƒ Produsen menulis kapasitas dalam satuan gigabyte (GB) ƒ 1 GB = 109

Kapasitas ditentukan oleh faktor teknologi berikut : ƒ R Recording di density d it (bit/inci): (bit/i i) banyaknya b k bit yang dapat d t ditempatkan dit tk dalam segmen track sepanjang 1 inci. ƒ Track density (track/inci): banyaknya track yang dapat ditempatkan dalam satu segmen radial sepanjang 1 inci. ƒ Areal density (bit/inci2): perkalian dari recording density dan track density.

Hard disk saat ini membagi track menjadi beberapa bagian yang tidak saling berhubungan, berhubungan disebut recording zones ƒ Setiap track dalam satu zona memiliki jumlah sektor yang sama, ditentukan oleh panjang track yang paling dalam. Setiap ap zona o a memiliki e jumlah ju a sektor/track se to /t ac yang ya g berbeda be beda ƒ Set 20

Menghitung Kapasitas HardDisk Kapasitas = (# byte/sektor) x (rata2 # sektor/track) x (# track/permukaan) x (# permukaan/piringan) x (# piringan/disk) Contoh : ƒ ƒ ƒ ƒ ƒ

512 byte/sektor 300 sektor/track (rata-rata) 20,000 track/permukaan 2 permukaan/piringan pe m kaan/pi ingan 5 piringan/disk

Kapasitas = 512 x 300 x 20000 x 2 x 5 = 30,720,000,000 = 30.72 GB

21

Operasi Hard Disk Permukaan hard disk berputar dengan kecepatan rotasi tetap spindle e

s spindle

Head baca/tulis diletakkan pada ujung lengan, dan melayang di atas permukaan disk ketika disk berputar

spindle

spindle

Dengan bergerak secara radial, lengan dapat memposisikan head baca/tulis pada berbagai track

22

Operasi Hard Disk Head H db baca/tulis /t li bergerak bersamaan dari silinder ke silinder

lengan

spindle

23

Waktu Akses Hard Disk Waktu rata-rata untuk mengakses suatu sektor target dapat dihitung : dihit ƒ Taccess = Tavg seek + Tavg rotasi + Tavg transfer

Waktu pencarian (Tavg seek) ƒ Waktu yang diperlukan untuk meletakkan head di atas silinder yang mengandung sektor target ƒ Umumnya Tavg seek = 9 mdetik

Delay rotasi (Tavg rotasi) ƒ Waktu untuk menunggu bit pertama sektor target berada di bawah head baca/tulis ƒ Tavg rotasi = ½ x 1/RPM x 60 detik/1 menit

Waktu transfer (Tavg transfer) ƒ Waktu untuk membaca bit-bit pada sektor target ƒ Tavg transfer = 1/RPM x 1 (rata2 # sektor/track) x 60 detik/1 menit

24

Contoh Waktu Akses HardDisk Diketahui : ƒ Kecepatan rotasi = 7,200 RPM ƒ Waktu pencarian rata-rata = 9 ms. ƒ Rata2 # sektor/track = 400.

Diturunkan : ƒ Tavg rotasi = 1/2 x (60 det/7200 RPM) x 1000 mdetik/detik = 4 mdetik ƒ Tavg transfer = 60/7200 RPM x 1/400 sektor/track x 1000 mdetik/detik = 0.02 mdetik ƒ Taccess = 9 mdetik + 4 mdetik + 0.02 mdetik

Hal penting : ƒ Waktu akses didominasi oleh waktu p pencarian dan delayy rotasi ƒ Bit pertama pada sektor adalah yang paling berpengaruh. ƒ Waktu akses SRAM sekitar 4 ndetik/doubleword, DRAM 60 ndetik ƒ Hard disk sekitar 40.000 kali lebih lambat dari SRAM ƒ 2.500 2 500 llebih bih lambat l b t dari d i DRAM 25

Blok Logika Hard Disk Pada hard disk modern, sektor geometri yang rumit dapat direpresentasikan dengan sudut pandang yang lebih sederhana ƒ Set dari sektor yang tersedia dimodelkan dalam urutan blok logika berukuran b (0, 1, 2, …)

Memetakan blok logika dan sektor fisik sesungguhnya ƒ Dikelola oleh suatu devais p perangkat g keras yang y g disebut harddisk controller. ƒ Menerjemahkan permintaan akan blok logika menjadi urutan permukaan-track-sektor

Harddisk controller mengatur penggunaan silinder untuk setiap zona ƒ Menghitung g g perbedaan p antara “kapasitas p setelah diformat” dan “kapasitas maksimum” 26

Bus I/O CPU chip

register file ALU

system bus

memory bus

main memory

I/O bridge

bus interface

I/O bus USB controller mouse keyboard

graphics adapter

Hard disk controller

Expansion p slots untuk devais lain seperti LAN, dll

monitor disk

27

Membaca Sektor Hard Disk (1) CPU

register file ALU

CPU memulai pembacaan hard disk dengan menulis perintah, bilangan blok logika, alamat memori tujuan ke suatu port (alamat) yang diterjemahkan oleh hard disk controller. main memory

bus interface

I/O bus

USB controller mouse keyboard

graphics adapter

Hard disk controller

monitor disk 28

Membaca Sektor Hard Disk (2) CPU

register file ALU

Hard disk controller membaca sektor dan melakukan direct memory access (DMA) transfer ke main memory

main memory

bus interface

I/O bus

USB controller mouse keyboard

graphics adapter

Hard disk controller

monitor disk 29

Membaca Sektor Hard Disk (3) CPU

register file ALU

Setelah transfer DMA selesai, hard disk controller memberitahu CPU dengan memberikan sinyal interupsi

main memory

bus interface

I/O bus

USB controller mouse keyboard

graphics adapter

Hard disk controller

monitor disk 30

Perkembangan Memori SRAM

DRAM

Disk

metrik

1980

1985

1990

1995

2000

2000:1980

$/MB akses(ndetik)

19,200 19 200 300

2,900 2 900 150

320 35

256 15

100 2

190 100

metrik

1980

1985

1990

1995

2000

2000:1980

$/MB akses (ndetik) ukuran k (MB)

8,000 375 0 064 0.064

880 200 0 256 0.256

100 100 4

30 70 16

1 60 64

8,000 6 1 000 1,000

metrik

1980

1985

1990

1995

2000

2000:1980

$/MB akses (mdetik) ukuran (MB)

500 87 1

100 75 10

8 28 160

0.30 10 1,000

0.05 8 9,000

10,000 11 9,000

31

Kecepatan Clock CPU

Prosesor clock rate(MHz) cycle time(ns)

1980 8080 1 1,000

1985 286 6 166

1990 386 20 50

1995 Pent 150 6

2000 P-III 750 1.6

2000:1980 750 750

32

Gap Kecepatan CPU - Memori Perbedaan kecepatan antara DRAM, Hard disk dan CPU terus meningkat 100,000,000 10,000,000 1,000,000 Disk seek time

ns s

100,000

DRAM access time

10,000

SRAM access time

1,000

CPU cycle time

100 10 1 1980

1985

1990

1995

2000

year

33

Locality s p locality oca ty : Prinsip ƒ Program cenderung untuk memakai ulang data dan instruksi yang letaknya berdekatan dengan yang sebelumnya b l digunakan, di k atau t yang pernah h mereferensikannya. ƒ Temporal locality : sesuatu yang pernah direferensikan cenderung akan direferensikan kembali pada waktu yang tidak lama. ƒ Spatial S i l locality l li : sesuatu yang letak l k alamatnya l berdekatan cenderung untuk direferensikan secara pada satu waktu bersama p 34

Locality Co to locality oca ty : Contoh sum = 0; for (i = 0; i < n; i++) sum += a[i]; return sum;

ƒ Data ƒ Mereferensikan elemen array secara berurutan (pola stride-1 reference) : Spatial locality ƒ Mereferensikan sum pada setiap iterasi : Temporal locality

ƒ Instruksi ƒ Mereferensikan instruksi secara berurutan : Spatial locality ƒ Berputar dalam loop secara berulang-ulang : Temporal locality 35

Contoh Locality Kemampuan untuk melihat kode dan mengetahui locality localit secara seca a kkualitatif alitatif merupakan me pakan kunci k nci yang ang harus ha s dimiliki oleh seorang programmer profesional. A k h fungsi Apakah f i di bawah b h ini i i memiliki iliki locality l lit yang baik b ik ? int sumarrayrows(int a[M][N]) { int i, j, sum = 0; for (i = 0; i < M; i++) for (j = 0; j < N; j++) sum += a[i][j]; return sum } 36

Contoh Locality p g berikut memiliki localityy yang y g baik ? Apakah fungsi int sumarraycols(int a[M][N]) { int i, j, sum = 0; for (j = 0; j < N; j++) for (i = 0; i < M; i++) sum += a[i][j]; return sum }

37

Contoh Locality p p p sehingga gg fungsi g dapat p Lakukan permutasi pada loop melacak array 3D a[] dengan pola stride-1 reference (dan menghasilkan locality spasial yang baik). int sumarray3d(int a[M][N][N]) { int i, j, k, sum = 0; for (i = 0; i < M; i++) for (j = 0; j < N; j++) for (k = 0; k < N; k++) sum += a[k][i][j]; return sum }

38

Hirarki Memori p perilaku p p Beberapa dasar pada hardware dan software : ƒ Teknologi penyimpanan yang cepat memiliki biaya per byte lebih tinggi dan kapasitas lebih rendah ƒ Perbedaan kecepatan antara CPU dan memori bertambah lebar ƒ Program yang dibuat dengan baik cenderung untuk memiliki locality yang baik

Setiap perilaku dasar tersebut saling mengisi satu sama lain dengan baik Diusulkan untuk mengelola g memori dan sistem penyimpanan yang dikenal dengan hirarki memori.

39

Hirarki Memori Kecepatan semakin tinggi, harga per bit semakin mahal, ukuran semakin kecil

L0: register

Register pada CPU menyimpan word data yang diambil dari L1 cache cache.

L1: on-chip L1 cache (SRAM) L2:

L3:

off-chip L2 cache (SRAM)

L1 cache menyimpan baris-baris cache yang diambil dari L2 cache memory. L2 cache menyimpan baris-baris cache yang diambil dari main memory

main memory (DRAM)

Semakin lambat, murah dan besar L4:

L5:

Penyimpan cadangan lokal (h d disk) (hard di k)

Main memory menyimpan blok-blok data yang diambil dari hard disk

Hard disk menyimpan file yang diambil dari server jaringan jarak jauh

Penyimpan cadangan jarak jauh (distributed file systems, Web servers) 40

Cache g p y p cepat p dan kecil,, berfungsi g sebagai g Perangkat penyimpan area antara dengan data yang berada pada penyimpan yang lambat dan besar. Ide dasar dari hirarki memori : ƒ Untuk setiap k, devais pada level k yang lebih cepat dan kecil merupakan cache dari devais yang lebih lambat dan besar pada l level l k+1

Mengapa hirarki memori digunakan ? ƒ Program g cenderung g untuk mengakses g data pada p level k lebih sering dari data pada level k+1 ƒ Penyimpan pada level k+1 dapat lebih lambat, besar dan harga per bit lebih rendah p 41

Cache Pada Hirarki Memori Level k:

48

9

10 4

Level k+1:

14 10

3

Devais penyimpan yang lebih kecil, cepat dan mahal pada level k merupakan cache dari subset blok pada level k+1

Data disalin antara level dengan satuan transfer dalam blok

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Devais penyimpan yang besar, lambat dan murah pada level k+1 dipartisi menjadi blok-blok

42

Konsep Umum Cache 14 12

Level k:

0

1

2

3

4* 12

9

14

3

12 4*

Level k+1:

Request 12 14

Program memerlukan obyek d yang disimpan dalam suatu blok b Cache hit ƒ Program menemukan b dalam cache level k. Misalnya pada blok 14.

Cache miss

Request 12

0

1

2

3

4 4*

5

6

7

8

9

10

11

12

13

14

15

ƒ B tidak terdapat pada level k, sehingga cache level k harus mengambilknya dari level k+1 k+1. Misalnya blok 12. 12 ƒ Jika cache level k penuh, maka suatu blok harus diganti isinya. Blok mana yang menjadi “korban” korban ? ƒ Placement policy : dimana blok baru diletakkan. Misalnya b mod 4 p policy p y : blok mana yyang g ƒ Replacement harus terusir ? Misalnya LRU 43

Konsep Umum Cache Jenis cache miss : ƒ Cold (compulsary) miss ƒ Cold miss terjadi jika cache kosong.

ƒ Conflict miss ƒ Cache pada level k+1 membagi blok menjadi subset berukuran kecil yang dapat diletakkan pada level k. ƒ Misalnya, blok i pada level k+1 harus diletakkan pada blok (i mod 4) pada level k+1. k+1 ƒ Conflict miss terjadi jika cache level k berukuran cukup besar, tetapi suatu kumpulan obyek data dipetakan pada blok yang sama di level k. ƒ Misalnya Mi l jika jik mereferensikan f ik blok bl k 0, 0 8, 8 0, 0 8, 8 0, 0 8, 8 … akan k terjadi t j di miss secara terus menerus.

ƒ Capacity miss ƒ Terjadi ketika blok data yang aktif (working set) lebih besar dari kapasitas cache 44

Cache Dalam Hirarki Memori Jenis Cache

Obyek Cache

Lokasi Cache

Delay

Pengelola

Registers

4-byte word

CPU registers

0 Compiler

TLB

Address translations 32-byte block 32-byte block 4-KB page

On-Chip TLB

0 Hardware

On-Chip L1 Off-Chip L2 Main memory

Parts of files

Main memory

1 Hardware 10 Hardware 100 Hardware+ OS 100 OS

Parts of files

Local disk

Web pages

Local disk

Web pages

Remote server disks

L1 cache L2 cache Virtual Memory Buffer cache Network buffer cache Browser cache Web cache

10,000,000 AFS/NFS client 10,000,000 Web browser 1 000 000 000 Web proxy 1,000,000,000 server 45