Arsitektur Komputer dan Sistem Operasi
Hirarki Memori
Sekolah Teknik Elektro dan Informatika - ITB 2009 1
Pembahasan Referensi locality Cache pada hirarki memori
2
Locality Prinsip locality : Program cenderung untuk memakai ulang data dan instruksi yang letaknya berdekatan dengan yang sebelumnya digunakan, atau yang pernah mereferensikannya. Temporal locality : sesuatu yang pernah direferensikan cenderung akan direferensikan kembali pada waktu yang tidak lama. Spatial locality : sesuatu yang letak alamatnya berdekatan cenderung untuk direferensikan secara bersama pada satu waktu 3
Locality Contoh locality : 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 4
Contoh Locality Kemampuan untuk melihat kode dan mengetahui locality secara kualitatif merupakan kunci yang harus dimiliki oleh seorang programmer profesional. Apakah fungsi di bawah ini memiliki locality yang baik ? 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 } 5
Contoh Locality Apakah fungsi berikut memiliki locality yang baik ? 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 }
6
Contoh Locality Lakukan permutasi pada loop sehingga fungsi dapat 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 }
7
Hirarki Memori Beberapa perilaku 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 memori dan sistem penyimpanan yang dikenal dengan hirarki memori.
8
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.
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 (hard disk)
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) 9
Cache Perangkat penyimpan cepat dan kecil, berfungsi sebagai 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 level k+1
Mengapa hirarki memori digunakan ? Program cenderung untuk mengakses data pada 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 10
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
11
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. Misalnya blok 12. Jika cache level k penuh, maka suatu blok harus diganti isinya. Blok mana yang menjadi “korban” ? Placement policy : dimana blok baru diletakkan. Misalnya b mod 4 Replacement policy : blok mana yang harus terusir ? Misalnya LRU 12
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. Conflict miss terjadi jika cache level k berukuran cukup besar, tetapi suatu kumpulan obyek data dipetakan pada blok yang sama di level k. Misalnya jika mereferensikan blok 0, 8, 0, 8, 0, 8, … akan terjadi miss secara terus menerus.
Capacity miss Terjadi ketika blok data yang aktif (working set) lebih besar dari kapasitas cache 13
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 server 14
