EC3003 - Sistem Komputer
Bagian 10 Cache Memory
Departemen Teknik Elektro Institut Teknologi Bandung 2005
Pembahasan Organisasi cache memory Direct mapped cache Set associative cache Pengaruh cache pada kinerja komputer
Cache Memory
10-2
Cache Memory Cache memory adalah memori berbasis SRAM berukuran kecil dan berkecepatan tinggi yang dikendalikan secara otomatis oleh hardware. Menyimpan suatu blok dari main memory yang sering diakses oleh CPU
Dalam operasinya, pertama-tama CPU akan mencari data di L1, kemudian di L2, dan main memory. CPU register file L1 cache cache bus
L2 cache
Cache Memory
ALU system bus memory bus
bus interface
I/O bridge
main memory
10-3
L1 Cache register dalam CPU memiliki tempat untuk menyimpan empat word berukuran 4-byte.
Satuan transfer antara register dan cache dalam blok berukuran 4-byte
L1 cache memiliki tempat untuk menyimpan dua blok berukuran 4-word
baris 0 baris 1
Satuan transfer antara cache dan main memory dalam blok berukuran 4-word blok 10
abcd
... blok 21
pqrs
... blok 30
main memory memiliki tempat untuk meyimpan blok-blok berukuran 4-word
wxyz
... Cache Memory
10-4
Organisasi Cache Memory Cache adalah array dari kumpulan set. Setiap set berisi satu atau lebih baris. Setiap baris menyimpan satu blok data. S=
2s
set
1 valid bit t tag bit per baris per baris valid
tag
B = 2b byte per blok cache 0
1
•••
B–1 E baris per set
•••
set 0: valid
tag
0
1
•••
B–1
valid
tag
0
1
•••
B–1
1
•••
B–1
1
•••
B–1
1
•••
B–1
•••
set 1: valid
tag
0 •••
valid Ukuran cache : C = B x E x S byte data Cache Memory
tag
0 •••
set S-1: valid
tag
0
10-5
Pengalamatan Cache Alamat A: t bit
s bit
b bit
m-1
v
tag
v
tag
v
tag
v
tag
set 0:
set 1:
0 ••• 0
1
• • • B–1
1
• • • B–1
0 ••• 0
1
• • • B–1
1
• • • B–1
1
• • • B–1
1
• • • B–1
••• v
tag
v
tag
set S-1:
0 ••• 0
0
<set index>
Data word pada alamat A berada dalam cache jika bit dan <set index> cocok dan berada dalam baris yang valid. Isi word dimulai dari byte ofset pada awal blok
Cache Memory
10-6
Direct-Mapped Cache Cache yang sederhana Setiap set hanya memiliki satu baris (line)
set 0:
valid
tag
blok cache
set 1:
valid
tag
blok cache
E=1 baris per set
••• set S-1:
Cache Memory
valid
tag
blok cache
10-7
Mengakses Direct-Mapped Cache Memilih set Menggunakan bit set index untuk memilih set yang digunakan
set dipilih
set 0:
valid
tag
blok cache
set 1:
valid
tag
blok cache •••
t bit m-1
tag
s bit b bit 00 001 set index block offset0
Cache Memory
set S-1: valid
tag
blok cache
10-8
Mengakses Direct-Mapped Cache Pencocokan baris dan pemilihan word Pencocokan baris : mencari baris valid dalam set yang dipilih dengan mencocokan tag Pemilihan word : Selanjutnya mengekstraksi word =1?
(1) Bit valid harus di-set 0
Set dipilih (i):
1
0110
1
2
3
4
w0
5
w1 w2
(2) Bit tag pada cache harus cocok dengan = ? bit tag pada alamat
m-1
Cache Memory
t bit 0110 tag
6
s bit b bit i 100 set index block offset0
7
w3
(3) Jika (1) dan (2), maka cache hit, dan block offset memilih posisi awal byte
10-9
Simulasi Direct-Mapped Cache t=1 s=2 x xx
M=16 byte alamat, B=2 byte/blok, S=4 set, E=1 entri/set
b=1 x
Penelusuran alamat (baca): 0 [00002], 1 [00012], 13 [11012], 8 [10002], 0 [00002]
v 11
0 [00002] (miss) tag data 0
m[1] m[0] M[0-1]
(1)
(3)
v (4)
13 [11012] (miss) v tag data
8 [10002] (miss) tag data
11
1
m[9] m[8] M[8-9]
1
1
M[12-13]
Cache Memory
1 1
0
m[1] m[0] M[0-1]
1 1
1
m[13] m[12] M[12-13]
v (5)
0 [00002] (miss) tag data
11
0
m[1] m[0] M[0-1]
11
1 1
m[13] m[12] M[12-13]
10-10
Bit Tengah Sebagai Indeks 4-baris cache 00 01 10 11
Bit indeks orde tinggi Baris memori yang bersebelahan akan dipetakan pada lokasi cache sama Spatial locality yang buruk
Bit indeks orde tengah Baris memori yang berurutan dipetakan pada baris cache berbeda Dapat menyimpan urutan byte pada cache dalam satu waktu Cache Memory
Bit atas 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Bit tengah 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 10-11
Set Associative Cache Setiap set memiliki lebih dari satu baris set 0:
set 1:
valid
tag
blok cache
valid
tag
blok cache
valid
tag
blok cache
valid
tag
blok cache
E=2 baris per set
••• set S-1:
Cache Memory
valid
tag
blok cache
valid
tag
blok cache
10-12
Mengakses Set Associative Cache Memilih set Serupa dengan direct-mapped cache
set 0:
Set dipilih
set 1:
valid
tag
blok cache
valid
tag
blok cache
valid
tag
blok cache
valid
tag
blok cache •••
t bit m-1
tag
set S-1: s bit b bit 00 001 set index block offset0
Cache Memory
valid
tag
blok cache
valid
tag
blok cache
10-13
Mengakses Set Associative Cache Pencocokan baris dan pemilihan word Harus membandingkan setiap tag pada baris yang valid dalam set yang dipilih (1) Bit valid harus di-set.
=1?
0
Set dipilih (i):
1
1001
1
0110
(2) Bit tag pada salah satu baris cache harus cocok dengan bit tag pada alamat
m-1
Cache Memory
=?
t bit 0110 tag
1
2
3
4
5
w0
6
w1 w2
7
w3
(3) Jika (1) dan (2), maka cache hit, dan block offset memilih posisi awal byte s bit b bit i 100 set index block offset0 10-14
Multi-Level Cache Pada cache, data dan instruksi dapat dipisah atau diletakkan dalam tempat yang sama
Prosesor
Reg
L1 d-cache L1 i-cache
Ukuran : 200 B Kecepatan : 3 ns $/Mbyte: Baris: 8B
8-64 KB 3 ns 32 B
Unified Unified L2 L2 Cache Cache
1-4MB SRAM 6 ns $100/MB 32 B
Memori Memori
128 MB DRAM 60 ns $1.50/MB 8 KB
disk disk
30 GB 8 ms $0.05/MB
Bertambah besar, lambat dan murah Cache Memory
10-15
Hirarki Cache Intel Pentium
Reg.
L1 Data 1 cycle latency 16 KB 4-way assoc Write-through 32B lines
L1 Instruction 16 KB, 4-way 32B lines
L2 L2Unified Unified 128KB--2 128KB--2MB MB 4-way assoc 4-way assoc Write-back Write-back Write Writeallocate allocate 32B lines 32B lines
Main Main Memory Memory Hingga Hingga4GB 4GB
Chip ChipProsesor Prosesor
Cache Memory
10-16
Metrik Kinerja Cache Miss Rate Persentase referensi memori yang tidak ditemukan dalam cache (miss/referensi). Umumnya 3-10% untuk L1, < 1% untuk L2.
Hit Time Waktu untuk mengirimkan data dari cache ke prosesor (termasuk waktu untuk menentukan apakah data tersebut terdapat dalam cache). Umumnya 1 siklus clock untuk L1, 3-8 siklus clock untuk L2.
Miss Penalty Waktu tambahan yang diperlukan karena terjadi miss Umumnya 25-100 siklus untuk main memory.
Cache Memory
10-17
Menulis Kode yg Cache Friendly Kode yang baik : Melakukan referensi berulang-ulang terhadap suatu variabel (temporal locality) Pola referensi stride-1 (spatial locality) Contoh : cold cache, 4-byte words, 4-word cache blocks
int sumarrayrows(int a[M][N]) { int i, j, sum = 0;
int sumarraycols(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; }
for (j = 0; j < N; j++) for (i = 0; i < M; i++) sum += a[i][j]; return sum; }
Miss rate = 1/4 = 25% Cache Memory
Miss rate = 100% 10-18
Gunung Memori Membaca throughput (membaca bandwidth) Banyaknya byte yang terbaca dari memori setiap detik (MB/detik)
Gunung memori Ukuran throughput sebagai fungsi dari spatial locality dan temporal locality. Cara untuk menentukan kinerja sistem memori.
Cache Memory
10-19
Fungsi Tes Gunung Memori /* The test function */ void test(int elems, int stride) { int i, result = 0; volatile int sink; for (i = 0; i < elems; i += stride) result += data[i]; sink = result; /* So compiler doesn't optimize away the loop */ } /* Run test(elems, stride) and return read throughput (MB/s) */ double run(int size, int stride, double Mhz) { double cycles; int elems = size / sizeof(int); test(elems, stride); /* warm up the cache */ cycles = fcyc2(test, elems, stride, 0); /* call test(elems,stride) */ return (size / stride) / (cycles / Mhz); /* convert cycles to MB/s */ }
Cache Memory
10-20
Rutin Utama Gunung Memori /* mountain.c - Generate the memory mountain. */ #define MINBYTES (1 << 10) /* Working set size ranges from 1 KB */ #define MAXBYTES (1 << 23) /* ... up to 8 MB */ #define MAXSTRIDE 16 /* Strides range from 1 to 16 */ #define MAXELEMS MAXBYTES/sizeof(int) int data[MAXELEMS]; int main() { int size; int stride; double Mhz;
/* The array we'll be traversing */
/* Working set size (in bytes) */ /* Stride (in array elements) */ /* Clock frequency */
init_data(data, MAXELEMS); /* Initialize each element in data to 1 */ Mhz = mhz(0); /* Estimate the clock frequency */ for (size = MAXBYTES; size >= MINBYTES; size >>= 1) { for (stride = 1; stride <= MAXSTRIDE; stride++) printf("%.1f\t", run(size, stride, Mhz)); printf("\n"); } exit(0); }
Cache Memory
10-21
Gunung Memori
read throughput (MB/s)
1200 1000
L1
Pentium III Xeon 550 MHz 16 KB on-chip L1 d-cache 16 KB on-chip L1 i-cache 512 KB off-chip unified L2 cache
800 600 Punggung gunung memperlihatkan Temporal Locality
400 xe
Cache Memory
8k 2k
32k
128k
512k
2m
8m
s15
s13
mem s11
s7
s9
stride (words)
s5
s3
L2
s1
Kemiringan 200 untuk Spatial 0 Locality
working set size (bytes)
10-22
Punggung Gunung - Temporal Potongan gunung memori dengan stride=1 Memperlihatkan throughput dari cache dan memori berbeda. 1200 main memory region
L2 cache region
L1 cache region
read througput (MB/s)
1000
800
600
400
200
1k
2k
4k
8k
16k
32k
64k
128k
256k
512k
1024k
2m
4m
8m
0
working set size (bytes)
Cache Memory
10-23
Kemiringan – Spatial Locality Potongan pada gunung memori dengan ukuran 256 KB. Memperlihatkan ukuran blok cache 800
read throughput (MB/s)
700 600 500 one access per cache line 400 300 200 100 0 s1
s2
s3
s4
s5
s6
s7
s8
s9 s10 s11 s12 s13 s14 s15 s16
stride (words)
Cache Memory
10-24
Contoh Perkalian Matriks Pengaruh utama cache yang penting : Total ukuran cache
Memperlihatkan temporal locality, tetap mempertahankan working set tetap kecil (contoh : dengan menggunakan blocking)
Ukuran blok
Memperlihatkan spatial locality
Deskripsi :
Perkalian matriks NxN Total operasi O(N3) Akses
/* /* ijk ijk */ */ for for (i=0; (i=0; i
N pembacaan untuk setiap elemen sumber N nilai dijumlahkan untuk setiap tujuan Dapat disimpan di register
Cache Memory
10-25
Analisis Miss Rate Analisis miss rate pada perkalian matriks Asumsi : Ukuran baris = 32B (cukup besar untuk 4 buah 64-bit word) Dimensi matriks (N) sangat besar Aproksimasi 1/N sama dengan 0.0
Cache tidak terlalu besar untuk menyimpan beberapa baris.
Metoda analisis : Melihat pola akses pada loop bagian dalam. k i
k
A
Cache Memory
j
j i
B
C
10-26
Layout Array C dalam Memori Array C dialokasikan dalam urutan row-major
Setiap baris (row) terletak dalam memori yang berurutan
Berpindah antar kolom dalam satu baris : for (i = 0; i < N; i++) sum += a[0][i];
Mengakses elemen yang berurutan Jika ukuran blok (B) > 4 bytes, eksploit spatial locality miss rate = 4 bytes / B
Berpindah antar baris dalam satu kolom : for (i = 0; i < n; i++) sum += a[i][0];
Mengakses elemen yang jauh Tidak terjadi spatial locality! miss rate = 1 (i.e. 100%)
Cache Memory
10-27
Perkalian Matriks ijk /* /* ijk ijk */ */ for for (i=0; (i=0; i
Loop bagian dalam : (*,j) (i,j) (i,*) A
Baris
B
Kolom
C
Tetap
Miss pada setiap iterasi loop bagian dalam : A B C 0.25 1.0 0.0 Cache Memory
10-28
Perkalian Matriks jik /* /* jik jik */ */ for for (j=0; (j=0; j
Loop bagian dalam : (*,j) (i,j) (i,*) A
Baris
B
Kolom
C
Tetap
Miss pada setiap iterasi loop bagian dalam : A B C 0.25 1.0 0.0 Cache Memory
10-29
Perkalian Matriks kij /* /* kij kij */ */ for for (k=0; (k=0; k
Loop bagian dalam : (i,k)
(k,*) (i,*)
A
B
C
Tetap
Baris
Kolom
Miss pada setiap iterasi loop bagian dalam : A B C 0.0 0.25 0.25 Cache Memory
10-30
Perkalian Matriks ikj /* /* ikj ikj */ */ for for (i=0; (i=0; i
Loop bagian dalam : (i,k)
(k,*) (i,*)
A
Tetap
B
Baris
C
Baris
Miss pada setiap iterasi loop bagian dalam : A B C 0.0 0.25 0.25 Cache Memory
10-31
Perkalian Matriks jki /* /* jki jki */ */ for for (j=0; (j=0; j
Loop bagian dalam : (*,k)
(*,j) (k,j)
A
Kolom
B
Tetap
C
Kolom
Miss pada setiap iterasi loop bagian dalam : A B C 1.0 0.0 1.0 Cache Memory
10-32
Perkalian Matriks kji /* /* kji kji */ */ for for (k=0; (k=0; k
Loop bagian dalam : (*,k)
(*,j) (k,j)
A
Kolom
B
Tetap
C
Kolom
Miss pada setiap iterasi loop bagian dalam : A B C 1.0 0.0 1.0 Cache Memory
10-33
Ringkasan Perkalian Matriks
ijk (& jik):
kij (& ikj):
jki (& kji):
• 2 load, 0 store
• 2 load, 1 store
• 2 load, 1 store
• miss/iterasi = 1.25
• miss/iterasi = 0.5
• miss/iterasi = 2.0
for (i=0; i
for (k=0; k
for (j=0; j
for (j=0; j
for (i=0; i
for (k=0; k
sum = 0.0;
r = a[i][k];
r = b[k][j];
for (k=0; k
for (j=0; j
for (i=0; i
sum += a[i][k] * b[k][j];
c[i][j] += r * b[k][j];
c[i][j] = sum; }
c[i][j] += a[i][k] * r;
} }
} }
}
Cache Memory
10-34
Kinerja Perkalian Matriks Pentium Miss rate bukan selalu perkiraan yang baik Penjadwalan kode juga berpengaruh 60
50
Cycles/iteration
40
kji jki kij ikj jik ijk
30
20
10
0 25 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400 Array size (n)
Cache Memory
10-35
Meningkatkan Temporal Locality Meningkatkan temporal locality dengan blocking. Contoh : perkalian matriks dengan blocking “blok” (di sini) bukan berarti “blok cache blok”. Tetapi berarti suatu sub-blok dalam matriks. Contoh : N = 8; ukuran sub-blok = 4 A11 A12 A21 A22
C11 C12
B11 B12 X
= B21 B22
C21 C22
Ide dasar: Sub-blok (mis., Axy) dapat diperlakukan seperti skalar C11 = A11B11 + A12B21
C12 = A11B12 + A12B22
C21 = A21B11 + A22B21
C22 = A21B12 + A22B22
Cache Memory
10-36
Perkalian Matriks dengan Blok for (jj=0; jj
Cache Memory
10-37
Analisis Perkalian Matriks Blok Pasangan loop paling dalam mengalikan potongan A 1 x bsize dengan blok B bsize x bsize dan mengakumulasikan menjadi C 1 x bsize. Loop dengan j langkah melalui potongan A dan C n baris, memakai B sama. for (i=0; i
A
kk
i
B
Potongan baris diakses bsize kali blok dipakai n kali secara berurutan Cache Memory
C update potongan elemen berurutan 10-38
Kinerja Blocking pada Pentium Kinerja perkalian matriks dengan blocking pada Pentium Blocking (bijk and bikj) meningkatkan kinerja dengan faktor dua kali di atas versi unblocked (ijk and jik) Relatif tidak sensitive terhadap ukuran array. 60
Cycles/iteration
50
kji jki kij ikj jik ijk bijk (bsize = 25) bikj (bsize = 25)
40
30
20
10
75 10 0 12 5 15 0 17 5 20 0 22 5 25 0 27 5 30 0 32 5 35 0 37 5 40 0
50
25
0
Array size (n)
Cache Memory
10-39
Kesimpulan Pemrogram dalam melakukan optimisasi kinerja cache Bagaimana struktur data dikelola Bagaimana data diakses Struktur nested loop Blocking merupakan teknik umum
Seluruh sistem menyukai “cache friendly code” Memperoleh kinerja optimum absolut sangat tergantung pada platform yang digunakan. Ukuran cache, ukuran line, associativities, dll.
Keuntungan paling besar dapat diperoleh dengan kode generik Tetap bekerja dalam working set yang kecil (temporal locality) Gunakan stride yang kecil (spatial locality)
Cache Memory
10-40
