Rekap: Technology Memory
Perkembangan teknologi dan organisasi CPU jauh lebih cepat dari memori Dalam kurun waktu: 1980 – 2000 • Peningkatan kecepatan DRAM memory access: 6x • CPU cycle time: 750x
Review: Dasar Cache Memory
IKI 30210: Organisasi Sistim Komputer
Johny Moningka (
[email protected]), Fakultas Ilmu Komputer Universitas Indonesia
Terdapat “gap” yang semakin lebar antara CPU dan memory. Teknologi memori/storages: Cepat => kapasitas kecil dan mahal. Kapasitas besar dan murah => lambat. Solusi: Cache memory => fast, small memory system (SRAM) antara CPU dan main memory. Tahun 1980: IBM PC (8086) tanpa cache memory Tahun 2004: Pentium 4, L1 cache: 8 KB/96KB, L2 on-chip cache: 512 KB (P4 Xeon: L3 on-chip cache: 1 MB).
OSK/JM-2003/V1.1/2
Rekap: Memory Hirarkis
Memory Technology: implementation
Pengamatan sifat program: Tidak semua kode/data program mempunyai kemungkinan yang sama diakses oleh CPU Program menganut prinsip lokalitas: temporal dan spatial BIG IDEA: Memori hirarkis adalah pilihan terbaik dalam menyediakan sistim memori yang cepat dengan kapasitas besar dan cost yang termurah Caching merupakan prinsip umum manajemen storages mendukung memori hirarkis. Penulisan program => menganut prinsip lokalitas supaya kinerja lebih cepat memanfaatkan memori hirarkis.
cache
CPU CPU regs regs
Register size: speed: $/Mbyte:
64 KB 1 - 10 ns $20/MB
disk disk I/O Bus
Memory
Disk Memory
512 MB 20 – 60 ns $ 0.175/MB ($90/512MB) SDRAM
120 GB 5.000.000 ns $0.00075/MB ($90/120GB)
Source: CAQA, Harga: http://bhinneka.com (Juni, 2004)
OSK/JM-2003/V1.1/4
Four Questions for Caches and Memory Hierarchy
Kapasitas memory kedua level dibagi atas: blok, yg sama besar Ukuran blok: tipikal 2x s/d 16x word size. Data dipindahkan sesuai dengan kebutuhan, dan dalam kelompok blok (block-sized chunks). Upper-level blocks a subset of lower-level blocks (copy) Access word w in block “a” (hit)
Access word v in block “b” (miss)
v
w High Level
Cache
Memory Memory
larger, slower, cheaper
Accessing Data in Cache
Memory Bus
SRAM
OSK/JM-2003/V1.1/3
500 B 0.25 ns
C a c h e
virtual memory
a
a
a
Q1: Where can a block be placed in the upper level? (Block placement) Q2: How is a block found if it is in the upper level?(Block identification) Q3: Which block should be replaced on a miss? (Block replacement) Q4: What happens on a write? (Write strategy)
b b Low Level
b a
b
a
b a
OSK/JM-2003/V1.1/5
Rujukan: P&H; Bab 5.2 (Hal. 375) Baca Rujukan!!!. OSK/JM-2003/V1.1/6
1
Q1: Where can a block be placed in the upper level?
Contoh: Kemungkinan Blok 12 dari memory berada pada cache dengan jumlah blok: 8
Block no.
01234567
Set associative: block 12 dapat menempati pada blok mana saja dari set 0 (12 mod 4)
Fully associative: block 12 dapat menempati di mana saja
Direct mapped: block 12 hanya dapat menempati blok 4 (12 mod 8) Block no.
01234567
Block no.
Set Set Set Set 0 1 2 3
Block-frame address
Block no.
01234567
1111111111222222222233 01234567890123456789012345678901 OSK/JM-2003/V1.1/7
Finding block in cache: Direct-Mapped
Sebab lebih dari satu nomor blok memory dapat menempati suatu blok pada cache, Bagaimana kita dapat mengetahui (identifikasi) nomor blok memory mana yang berada di cache? Memory byte addressable! Bagaimana kita dapat mengetahui byte mana yang akan diambil pada blok tersebut (ukuran blok > 1 byte)? Answer: divide memory address into three fields
ttttttttttttttttt iiiiiiiiii oooo tag to check if have correct block
index to select block
Q2: How is a block found if it is in the upper level? Block Memory Address
Cache Index 0 1 2 3
Memory
0 1 2 3 4 5 6 7 8 9 A B C D E F
4 Byte Direct Mapped Cache
Direct Map Cache
Lokasi blok 0 pada cache ditempati oleh: Lokasi memory blok: 0, 4, 8, ... Secara umum lokasi nomor blok memory kelipatan 4 (mod 4). OSK/JM-2003/V1.1/8
Direct-Mapped Cache Terminology
Semua fields => unsigned integers
Index: merupakan indeks blok cache (blok mana pada cache)
Offset: setelah menentukan blok pada cache, offset menentukan byte mana pada blok yang akan diakses
Tag: sisa dari bits setelah offset dan index ditentukan; digunakan untuk membedakan antara blok-blok pada main memory yang dipetakan (mapping) pada blok yang sama di cache memory.
byte offset within block OSK/JM-2003/V1.1/9
Direct-Mapped Cache Example (1/3)
Misalkan cache memory: Besar 16 KB direct mapped, dengan ukuran blok 4 word (1 word = 32 bits arsitektur).
Tentukan ukuran tag, index, dan offset (field)!!!
Offset Diperlukan untuk menentukan byte mana pada blok yang akan diakses. Setiap blok 4 words = 16 bytes = 24 bytes. • Jadi diperlukan 4 bits offset utk identifikasi byte pada suatu blok (16 bytes). OSK/JM-2003/V1.1/11
OSK/JM-2003/V1.1/10
Direct-Mapped Cache Example (2/3)
Index: (~index memilih dari “array of blocks”) Diperlukan untuk identifikasi nomor/lokasi blok pada cache. Besarnya cache 16 KB = 214 bytes Besarnya blok: 24 bytes (4 words) Jumlah blok/cache:
=
214 bytes/cache 24 bytes/block
=
210 blocks/cache
Perlu 10 bits untuk menentukan nomor blok OSK/JM-2003/V1.1/12
2
Direct-Mapped Cache Example (3/3)
Caching Terminology
Tag: Gunakan sisa bits sebagai tag tag length = addr length – offset - index = 32 - 4 - 10 bits = 18 bits Jadi tag: leftmost 18 bits dari alamat memory
18 bits
10 bits
tag to check if have correct block
index to select block
When we try to read memory, 3 things can happen:
1.
cache hit: cache block is valid and contains proper address, so read desired word
2.
cache miss: nothing in cache in appropriate block, so fetch from memory
3.
cache miss, block replacement: wrong data is in cache at appropriate block, so discard it and fetch desired data from memory (cache always copy)
4 bits byte offset within block OSK/JM-2003/V1.1/13
Example: Accessing data in a direct mapped cache
Ex.: 16KB of data, direct-mapped, 4 word blocks Read 4 addresses 1. 0x00000014 2. 0x0000001C 3. 0x00000034 4. 0x00008014 Memory values on right: only cache/ memory level of hierarchy
Memory Address (hex)Value of Word ... ... a 00000010 b 00000014 c 00000018 d 0000001C ... ... e 00000030 f 00000034 g 00000038 h 0000003C ... ... i 00008010 j 00008014 k 00008018 l 0000801C ... ... OSK/JM-2003/V1.1/15
OSK/JM-2003/V1.1/14
Accessing data in a direct mapped cache
4 Addresses: 0x00000014, 0x0000001C, 0x00000034, 0x00008014
Contoh: alamat tsb dalam bentuk field: Tag (18 bits), Index (10 bits), Byte Offset fields (4 bits) 000000000000000000 0000000001 0100 000000000000000000 0000000001 1100 000000000000000000 0000000011 0100 000000000000000010 0000000001 0100 Tag
Valid bit: set saat copy blok memory, Note: 32 bits arsitektur (words= 4 bytes) =>
Valid Index Tag 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 ...
0x0-3 => 4 bytes dari word pertama
0x4-7
0x0-3
0x8-b
0xc-f
1. Read 0x00000014
000000000000000000 0000000001 0100
Valid Index Tag 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 ...
...
Offset OSK/JM-2003/V1.1/16
16 KB Direct Mapped Cache, 16B blocks
Index
Tag field
Index field Offset 0x4-7
0x0-3
0x8-b
0xc-f
...
1022 0 1023 0
1022 0 1023 0 OSK/JM-2003/V1.1/17
OSK/JM-2003/V1.1/18
3
So we read block 1 (0000000001)
No valid data pada cache!
000000000000000000 0000000001 0100
Valid Index Tag 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0
Tag field
Index field Offset 0x4-7
0x0-3
...
0x8-b
0xc-f
...
000000000000000000 0000000001 0100
Valid Index Tag 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0
Tag field 0x0-3
...
1022 0 1023 0
Index field Offset 0x4-7
0x8-b
...
1022 0 1023 0 OSK/JM-2003/V1.1/19
OSK/JM-2003/V1.1/20
So load that data into cache, setting tag, valid
Read from cache at offset, return word b
000000000000000000 0000000001 0100
Valid Index Tag 0 0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0
Tag field
Index field Offset 0x4-7
0x0-3 a
...
b
0x8-b
0xc-f
c
d
...
000000000000000000 0000000001 0100
Valid Index Tag 0 0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0
Tag field
Index field Offset 0x4-7
0x0-3 a
...
1022 0 1023 0
b
0x8-b
0xc-f
c
d
...
1022 0 1023 0 OSK/JM-2003/V1.1/21
OSK/JM-2003/V1.1/22
2. Read 0x0000001C = 0…00 0..001 1100
...
Tag field
Index field 0x4-7
0x0-3 a
b
Index is Valid
000000000000000000 0000000001 1100
Valid Index Tag 0 0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0
0xc-f
Offset
0x8-b
0xc-f
c
d
...
000000000000000000 0000000001 1100
Valid Index Tag 0 0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0 ...
1022 0 1023 0
Tag field
Index field 0x4-7
0x0-3 a
b
Offset
0x8-b
0xc-f
c
d
...
1022 0 1023 0 OSK/JM-2003/V1.1/23
OSK/JM-2003/V1.1/24
4
Index valid, Tag Matches
Index Valid, Tag Matches, return d
000000000000000000 0000000001 1100
Valid Index Tag 0 0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0
Tag field
Index field 0x4-7
0x0-3 a
...
b
Offset
0x8-b
0xc-f
c
d
...
000000000000000000 0000000001 1100
Valid Index Tag 0 0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0
Tag field 0x0-3 a
...
1022 0 1023 0
Index field 0x4-7 b
0xc-f
c
d
...
1022 0 1023 0 OSK/JM-2003/V1.1/25
OSK/JM-2003/V1.1/26
So read block 3
3. Read 0x00000034 = 0…00 0..011 0100
000000000000000000 0000000011 0100
Tag field Valid 0x0-3 Index Tag 0 0 a 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0 ...
Index field Offset 0x4-7 0x8-b 0xc-f b
c
d
...
000000000000000000 0000000011 0100
Valid Index Tag 0 0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0
Tag field 0x0-3
Index field Offset 0x4-7 0x8-b 0xc-f
a
...
b
c
...
OSK/JM-2003/V1.1/27
OSK/JM-2003/V1.1/28
No valid data
Load that cache block, return word f
000000000000000000 0000000011 0100
Valid Index Tag 0 0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 0 ...
d
1022 0 1023 0
1022 0 1023 0
Offset
0x8-b
Tag field 0x0-3
Index field Offset 0x4-7 0x8-b 0xc-f
a
b
c
d
...
000000000000000000 0000000011 0100
Valid Index Tag 0 0 1 1 0 2 0 3 1 0 4 0 5 0 6 0 7 0 ...
1022 0 1023 0
Tag field 0x0-3
Index field Offset 0x4-7 0x8-b 0xc-f
a
b
c
d
e
f
g
h
...
1022 0 1023 0 OSK/JM-2003/V1.1/29
OSK/JM-2003/V1.1/30
5
So read Cache Block 1, Data is Valid
4. Read 0x00008014 = 0…10 0..001 0100
000000000000000010 0000000001 0100
Tag field Valid 0x0-3 Index Tag 0 0 a 1 1 0 2 0 e 3 1 0 4 0 5 0 6 0 7 0 ...
Index field Offset 0x4-7 0x8-b 0xc-f b
c
d
f
g
h
...
000000000000000010 0000000001 0100
Valid Index Tag 0 0 1 1 0 2 0 3 1 0 4 0 5 0 6 0 7 0
Tag field 0x0-3 a
b
c
d
e
f
g
h
...
1022 0 1023 0
Index field Offset 0x4-7 0x8-b 0xc-f
...
1022 0 1023 0 OSK/JM-2003/V1.1/31
Cache Block 1 Tag does not match (0 != 2)
...
Miss, so replace block 1 with new data & tag
000000000000000010 0000000001 0100
Tag field Valid 0x0-3 Index Tag 0 0 a 1 1 0 2 0 e 3 1 0 4 0 5 0 6 0 7 0
OSK/JM-2003/V1.1/32
Index field Offset 0x4-7 0x8-b 0xc-f b
c
d
f
g
h
...
000000000000000010 0000000001 0100
Tag field Valid 0x0-3 Index Tag 0 0 i 1 1 2 2 0 e 3 1 0 4 0 5 0 6 0 7 0 ...
k
l
g
h
...
OSK/JM-2003/V1.1/33
000000000000000010 0000000001 0100
Tag field Valid 0x0-3 Index Tag 0 0 i 1 1 2 2 0 e 3 1 0 4 0 5 0 6 0 7 0
OSK/JM-2003/V1.1/34
Summary
And return word j
...
j f
1022 0 1023 0
1022 0 1023 0
Index field Offset 0x4-7 0x8-b 0xc-f
Index field Offset 0x4-7 0x8-b 0xc-f j
k
l
f
g
h
Cache memory => managed by hardware (chipsets) Manajemen dan transfer blok data antara main memory dan cache memory. Efisien dan cepat => simple is faster. Direct Mapped: cara sederhana rancangan cache, dengan membagi alamat memory => 3 field, yang tetap yakni: • Offset => tergantung besarnya blok (block size) dari cache • Index => tergantung jumlah blok pada cache (cache size / block size) • Tag => sisa bits (leftmost).
...
1022 0 1023 0 OSK/JM-2003/V1.1/35
OSK/JM-2003/V1.1/36
6
