2016.4.1 II ( ) 1 1.1 DRAM RAM DRAM DRAM SRAM RAM SRAM SRAM SRAM SRAM DRAM SRAM SRAM DRAM SRAM 1.2 (DRAM, Dynamic RAM) (SRAM, Static RAM) (RAM Random Access Memory ) DRAM 1 1 1 1 SRAM 4 1 2 DRAM 4 DRAM 3 DRAM 2 C CDROM 1 1 0 2 3 Dynamic RAM SRAM 1
DRAM SRAM SDRAM (Synchronous DRAM) DDR SDRAM (Double Data Rate SDRAM) DRAM 4 C Wikipedia 1.8 SRAM DRAM DRAM SRAM DRAM SRAM (256M 1G bit) (32 64M bit) (50 70 ns) (0.5 5 ns) IC 20-80 80% 20% 1 プロセッサ 大 容 量 低 速 メモリ 小 容 量 高 速 メモリ 1: 4 DDR2 SDRAM, DDR3 SDRAM 2
プロセッサ 命 令 メモリ データメモリ 大 容 量 メモリ( 主 記 憶 ) 2: 20-80 100 98 (cache) 2 1 2 1 2 CPU 1 3
0 1 2 3 4 5 6 7 キャッシュ 0mod 8 = 0 27 mod 8 = 3 31 mod 8 = 7 メインメモリ 0 1 2 3 4 5 6 7 27 28 29 30 31 3: 1.3 1.3.1 1 4 1 8 32 8 32 32KB 32 128 4GB 0 7 0 31 3 (direct map) 3 5 4 4 4 4KB 4GB 6 4 5 6 4GB 32 4GB 32 4
20 アドレス 10 2 120627 512 00 インデックス 有 効 タグ データ 1 20 32 キャッシュメモリ 0 1 512 1 120627 1234567890 1022 1023 = データ ヒット 4: 1 4 2 10 I (9) ALU 5
OS OS 1 4 1. (PC-4) 2. 3. 4. 7 5. PC 8 1 2 3 4 1.3.2 (consistency) (write-through) (write buffer) 1 (write-back) 7 8 OS 6
16 12 2 2 アドレス タグ インデックス bidx bofs 0x1234 0xFFE 1 0 0x5678 0x1 0 0 読 出 しの 例 書 込 みの 例 書 込 みデータ 0x00005555 1 1 0x5678 有 効 書 込 タグ 1 0x1234 デマルチプレクサ 0 1 2 3 0x5555 キャッシュブロック 0x1111 0x2222 0x3333 0x4444 0 1 0xFFE 0xFFF キャッシュ メモリ 比 較 (=) 0 1 2 3 マルチプレクサ ヒット 読 出 しデータ 0x00002222 5: 1.3.2 1 5 1 4 16 4096 1 7
1.4 1.4.1 CPU CPU CPU =(CPU + ) 9 LRU = 9 8
10 [ ] 2% 4% CPI 2 100 36% [ ] I 2% = I 2% 100 = 2.00 I 4% = I 36% 4% 100 = 1.44 I CPI 2 = 2 I + 2.00 I + 1.44 I = 5.44 I 2 I 2.72 5.44 2 = 2.72 11 [ ] 2 [ ] T clock A = 5.44I T clock B = 8.88I T clock 1 2 A B = 1.23 2 1.23 CPU CPU CPI CPI clock per instruction 1 CPI 1 10 4 p.441 11 3 9
CPI 1.3.1 1.5 ( ) (fully associative) 12 (set associative) 1.5.1 n n 6 4-way 1 4 22 6 4:1 12 TLB 10
22 0627 アドレス 8 71 2 00 キャッシュ メモリ インデッ クス 有 効 タグ データ 1 22 32 有 効 タグ データ 1 22 32 有 効 タグ データ 1 22 32 有 効 タグ データ 1 22 32 0 1 71 1 0627 10345678 1 0727 12045678 0 0637 12305678 1 1627 12340678 255 = = = = ヒット 4:1 MUX データ 6: 4-way 71 71 0 LRU(Least Recently Used) 2 (FF) FF 2 FF FF FF LRU 4 1.6 8 11
n=2 adr blk 0x0100 0 fact: sub $sp, $sp, 8 0x0104 1 sw $ra, 4($sp) 0x0108 2 sw $a0, 0($sp) 0x010C 3 slt $t0, $a0, 1 0x0110 4 beq $t0, $zero, L1 0x0114 5 add $v0, $zero, 1 0x0118 6 add $sp, $sp, 8 0x011C 7 jr $ra 0x0120 8 L1: sub $a0, $a0, 1 0x0124 9 jal fact 0x0128 10 lw $a0, 0($sp) 0x012C 11 lw $ra, 4($sp) 0x0130 12 add $sp, $sp, 8 0x0134 13 mul $v0, $a0, $v0 0x0138 14 jr $ra 1.9 1.7 [ ] 4K 4 32 2 4 [ ] 4 16 28 log 4K = 12 32-12-4=16 16 4K = 64K 2 = /2 log(4k/2) = 11 32-11-4=17 17 2 2K = 64K 2 4 = /4 10 18 4 1K = 72K =1 28 28 4K = 112K 12
[ ] CPI 1 1 4GHz 100ns 1 2% 2 5ns 0.5% [ ] 100ns / 0.25ns = 400 clock cycle 1 CPI 1+0.02*400=9 8 CPI 2 1 2 5ns / 0.25 ns = 20 clock cycle 2% 1 0.5% 2 CPI 1 + 0.02 20 + 0.005 400 = 1 + 0.4 + 2 = 3.4 2 9/3.4 = 2.6 (associative memory) 1.8 7 7 SRAM 1 4 ( ) ( ) ROM RAM SRAM ( ) ( ) (1or0) (Vcc) (Tr1) P P ( ) Tr1 P 13
SRAMのメモリセル 構 成 DRAMのメモリセル 構 成 7: SRAM DRAM MYCOM ) 1 0 1.9 0,1,2,3,4,8,9,0,1,2,3,4,8,9,0,1,2,3,4,5,6,7,10,11,12,13,14,10,11,12,13,14 32 8 () m/h ( ) LRU 14
/ () 0 (0) m 1 (0,1) m 2 (0,1,2) m 3 (0,1,2,3) m 4 (0,1,2,3,4) m 8 (0,1,2,3,4,8) m 9 (0,1,2,3,4,8,9) m 0 (1,2,3,4,8,9,0) h 0 1 (2,3,4,8,9,0,1) h 2 (3,4,8,9,0,1,2) h 3 (4,8,9,0,1,2,3) h 19 5 (8,9,0,1,2,3,4,5) m 6 (9,0,1,2,3,4,5,6) m LRU 8 7 (0,1,2,3,4,5,6,7) m 10 (1,2,3,4,5,6,7,10) m 11 (2,3,4,5,6,7,10,11) m 12 (3,4,5,6,7,10,11,12) m 13 (4,5,6,7,10,11,12,13) m 14 (5,6,7,10,11,12,13,14) m 10 (5,6,7,11,12,13,14,10) h 10 11 (5,6,7,12,13,14,10,11) h 12 (5,6,7,13,14,10,11,12) h 13 (5,6,7,14,10,11,12,13) h 14 (5,6,7,10,11,12,13,14) h 15 17 15
2 ((),(),(),()) m/h / ((),(),(),()) 0 ((0),(),(),()) m 1 ((0),(1),(),()) m 2 ((0),(1),(2),()) m 3 ((0),(1),(2),(3)) m 4 ((0,4),(1),(2),(3)) m 8 ((4,8),(1),(2),(3)) m 9 ((4,8),(1,9),(2),(3)) m 0 ((8,0),(1,9),(2),(3)) m 1 ((8,0),(9,1),(2),(3)) h 2 ((8,0),(9,1),(2),(3)) h 3 ((8,0),(9,1),(2),(3)) h 4 ((0,4),(9,1),(2),(3)) m 8 ((4,8),(9,1),(2),(3)) m 9 ((4,8),(1,9),(2),(3)) h 0 ((8,0),(1,9),(2),(3)) m 1 ((8,0),(9,1),(2),(3)) h 2 ((8,0),(9,1),(2),(3)) h 3 ((8,0),(9,1),(2),(3)) h 4 ((0,4),(9,1),(2),(3)) m 5 ((0,4),(1,5),(2),(3)) m 6 ((0,4),(1,5),(2,6),(3)) m 7 ((0,4),(1,5),(2,6),(3,7)) m 10 ((0,4),(1,5),(6,10),(3,7)) m 11 ((0,4),(1,5),(6,10),(7,11)) m 12 ((4,12),(1,5),(6,10),(7,11)) m 13 ((4,12),(5,13),(6,10),(7,11)) m 14 ((4,12),(5,13),(10,14),(7,11)) m 10 ((4,12),(5,13),(14,10),(7,11)) h 11 ((4,12),(5,13),(14,10),(7,11)) h 12 ((4,12),(5,13),(14,10),(7,11)) h 13 ((4,12),(5,13),(14,10),(7,11)) h 14 ((4,12),(5,13),(14,10),(7,11)) h 20 12 16
(,,,,,,,) m/h / (,,,,,,,) 0 (0,,,,,,,) m 1 (0,1,,,,,,) m 2 (0,1,2,,,,,) m 3 (0,1,2,3,,,,) m 4 (0,1,2,3,4,,,) m 8 (8,1,2,3,4,,,) m 9 (8,9,2,3,4,,,) m 0 (0,9,2,3,4,,,) m 1 (0,1,2,3,4,,,) m 2 (0,1,2,3,4,,,) h 3 (0,1,2,3,4,,,) h 4 (0,1,2,3,4,,,) h 8 (8,1,2,3,4,,,) m 9 (8,9,2,3,4,,,) m 0 (0,9,2,3,4,,,) m 1 (0,1,2,3,4,,,) m 2 (0,1,2,3,4,,,) h 3 (0,1,2,3,4,,,) h 4 (0,1,2,3,4,,,) h 5 (0,1,2,3,4,5,,) m 6 (0,1,2,3,4,5,6,) m 7 (0,1,2,3,4,5,6,7) m 10 (0,1,10,3,4,5,6,7) m 11 (0,1,10,11,4,5,6,7) m 12 (0,1,10,11,12,5,6,7) m 13 (0,1,10,11,12,13,6,7) m 14 (0,1,10,11,12,13,14,7) m 10 (0,1,10,11,12,13,14,7) h 11 (0,1,10,11,12,13,14,7) h 12 (0,1,10,11,12,13,14,7) h 13 (0,1,10,11,12,13,14,7) h 14 (0,1,10,11,12,13,14,7) h 21 11 17
2 2.1 13 36 64GB 4GB 8GB 32GB 14 64GB 8GB 15 16 2.2 (virtual memory) 0 0 8GB 0 8G 17 2 2 OS ( 13 14 15 16 10 17 8GB 4GB 0 4GB 4GB 0xF00000000 36 8GB 2 18
仮 想 アドレス ページ0 物 理 アドレス ページ0 ページk ページn ページm 2 次 記 憶 :ハードディスク 8: ( ) 8 8 k 2 2.3 9 9 18 8 18 19
24 仮 想 アドレス 12 仮 想 ページ 番 号 ページ 内 オフセット 変 換 20 12 物 理 ページ 番 号 ページ 内 オフセット 物 理 アドレス 9: 2 8 2 CPU 4KB 16KB 32KB 64KB 2.4 2.4.1 10 1 4 10 64MB 20
24 仮 想 アドレス 12 ページ 表 レジスタ 有 効 仮 想 ページ 番 号 物 理 ページ 番 号 ページ 内 オフセット + ページ 表 0ならページフォールト 1なら 物 理 ページ 番 号 20 物 理 ページ 番 号 12 ページ 内 オフセット 物 理 アドレス 10: 2.4.2 1 2 2 OS 0 LRU 5 10,12,9,7,11,10 8 LRU 12 12 8 LRU OS LRU 2.4.3 11 21
アドレス 上 位 メモリ 空 間 スタック 領 域 ~~ 下 に 伸 びる ~~ 上 に 伸 びる ヒープ 領 域 静 的 データ アドレス 下 位 プログラム 11: 11 2 2.4.4 2.5 TLB 2 1 (Translation-Lookaside Buffer)TLB TLB 12 36 32 12 TLB 22
仮 想 ページ 番 号 有 効 タグ 物 理 ページ 1 1 1 0 1 TLB ページ 表 有 効 物 理 ページ ページ0 物 理 メモリ ページ0 ページn ページm 2 次 記 憶 :ハードディスク 12: (TLB) 1: TLB TLB 16 512 4 8 0.5 1 10 100 0.01 1 % TLB TLB TLB TLB TLB 1 TLB 1 TLB LRU 2.4.2 TLB TLB TLB TLB LRU 2 TBL LRU 1 TLB 1 16 512 TLB LRU TLB TLB 13 23
仮 想 アドレス 35 12 11 0 仮 想 ページ 番 号 ページ 内 オフセット 有 効 24 ダーティ タグ 物 理 ページ 番 号 12 TLB ヒット TLB 20 タグ 部 分 は 連 想 メモリ 物 理 ページ 番 号 ページ 内 オフセット 物 理 アドレス 物 理 アドレスタグ バイト 16 キャッシュインデックス オフセット 14 2 有 効 タグ データ キャッシュ キャッシュ ヒット = 32 データ 13: TLB 13 TLB 14 TLB TLB TLB TLB TLB TLB TLB 14 TLB TLB TLB TLB TLB TLB 100 99 19 19 20-80 20-80 20-80 10-90 5-95 24
仮 想 アドレス Load block to cache TLBミス 例 外 処 理 no no TLBアクセス Hit? Cache read Hit? yes yes no 読 出 しデータ Write? no 書 込 保 護 例 外 処 理 物 理 アドレス yes Write allowed? Load block to cache yes Cache write no yes Hit? 書 込 み, TLBのダーティビットセット 14: TLB, 2.6 MIPS EPC 1 EPC 2.7 A B OS 0 25
OS OS OS OS OS OS OS OS OS A B A B OS 20 B A OS OS 21 20 OS 21 26