Lec 21 · Directory 마무리·Shared cache·NUCA, Virtual Memory(base&bound·paging·TLB·virtual cache)

1.1ca_L13 후반: directory protocol 의 block state 별 처리를 마치고, private vs shared LLC, NUCA(Skylake 예), shared cache 공간 분배 문제

1.2ca_L14 Virtual Memory: bare machine → base & bound(segment, carry-save adder) → external fragmentation → paging

1.3Atlas demand paging, page table 크기와 hierarchical page table(RISC-V Sv32), TLB 설계·reach·miss 처리(hardware/software)

1.4page fault handler·TLB shootdown, TLB latency 를 숨기는 virtual address cache(VIVT)의 aliasing 문제까지, VIPT 는 다음 강의

상황·문제지난 강의에서 끝내지 못한 directory-based coherence 의 state 별 처리를 마무리

원인snoop 기반은 broadcast 때문에 scalability 가 없고, directory 는 home node 가 line 별 state·sharer 를 보관한다

해결요청자는 home 의 directory 에 문의, directory controller 가 필요한 node 에만 message. uncached·shared·exclusive block 마다 read miss·write miss·write back 처리 규칙

상황·문제CMP 에서 last-level cache(L2)를 core 별 private 로 둘지 shared 로 둘지

원인private 는 공유 data 가 여러 L2 에 중복되고, shared 는 core 간 contention·interference 와 긴 latency 가 생긴다

해결shared 는 중복이 없어 용량을 효율적으로 쓰므로 최근 Intel·AMD 는 LLC 를 공유. 대신 큰 cache 의 latency 문제가 남음

상황·문제하나의 큰 shared cache 는 가장 먼 block 이 worst-case latency 를 결정

원인wire delay 때문에 모든 위치를 같은 access time 으로 만드는 것은 비싸다

해결cache 를 bank 로 나눠 core 와의 거리에 따라 latency 를 다르게. mapping 은 static(interleaving) 또는 dynamic(core 가까이 배치, 성능↑ 대신 복잡)

상황·문제실제 processor 는 NUCA 를 어떻게 구현하는가

원인core 마다 L3 slice 가 붙어 있고 on-chip network 거리만큼 latency 차이

해결실제 설계는 static mapping — line 위치가 address 로 정해지며, 먼 slice 는 request·response 가 멀리 오가 latency 가 가장 김

상황·문제shared cache 를 택할 때 얻는 것과 잃는 것

원인중복이 없고 한 위치에만 block 이 있지만, 여러 core 가 같은 용량을 두고 경쟁

해결장점: 높은 유효 용량, dynamic partitioning, coherence 쉬움, 공유 data·lock ping-pong 없음. 단점: 느린 접근, inter-core conflict miss, 성능 예측 어려움

상황·문제LRU 등 단일 core 정책을 그대로 쓰는 free-for-all sharing 의 문제

원인thread 를 구분하지 않아 cache 를 thrash 하는 core 가 다른 core 성능을 크게 떨어뜨리고, 추가 용량의 이득도 app 마다 다름

해결많은 CMP 가 cache partitioning 으로 core 별 공간을 제어, 전체 성능을 최대화하는 동적 할당 연구가 많다

상황·문제address translation 이 없는 bare machine 에서는 physical address 만 존재

원인초기엔 한 번에 한 program 이라 문제없었으나, location-independent library 가 생기며 physical 위치 결정이 필요

해결linker·loader 가 library module 을 실제 physical 위치로 relocate

상황·문제느린 I/O 동안 CPU 가 놀지 않도록 여러 program 을 동시에 실행(multiprogramming)해야 한다

원인program 마다 physical 위치가 달라지고, 서로의 memory 를 침범하지 않아야 함

해결base register 로 logical→physical 변환, bound register 로 범위 검사. 두 register 는 supervisor mode(OS)만 변경 가능

상황·문제segment 를 여러 개(code, data) 두면 무엇이 좋은가 (수업 중 질문)

원인single segment 로는 process 간 일부만 공유하는 것이 불가능

해결code segment 는 여러 process 가 공유, data segment 는 private. segment 를 더 두면 read-only 공유 등 다양한 공유. pipeline 에서는 address 계산에 base 를 더하는 세 수 덧셈을 carry-save adder 로

상황·문제Job 2 종료 후 빈 공간 합은 32K 인데 연속이 아니라 Job 4(32K)를 실행할 수 없다

원인base & bound 는 연속된 physical 영역을 요구 → external fragmentation, compaction 은 비쌈

해결paging: address 를 page number + offset 으로 나누고 page table 로 불연속 page frame 에 mapping. OS free list 로 할당이 쉽고 사용량이 동적으로 증감

상황·문제paging 으로도 physical memory 보다 큰 문제는 drum·disk 와 data 를 오가야 한다

원인manual overlay 는 tedious·error-prone, software interpretive coding 은 쉽지만 비효율

해결Atlas(1962) demand paging: primary memory 를 secondary(drum) 의 cache 로, 접근한 page 를 processor 가 자동으로 가져옴. PAR 32 개를 비교해 없으면 page fault

상황·문제linear page table 은 너무 크다: 64-bit VA, 40-bit PA, 4KB page 면 16×2^50 byte, 그것도 process 하나에

원인virtual address space 대부분은 실제로 쓰이지 않는데 모든 page 의 entry 를 둠. larger page 는 internal fragmentation·page fault penalty 증가

해결hierarchical page table: address bit 를 나눠 level 별 index (RISC-V Sv32 는 10+10 bit), 안 쓰는 영역의 하위 table 을 생략

상황·문제모든 memory access 마다 translation 과 protection check 가 필요하다

원인page walk 는 memory access 여러 번이라 최적화 없이는 매우 비쌈

해결TLB 에 PTE 를 cache — hit 면 single cycle, miss 면 page walk. miss 처리는 hardware(MMU page walker) 또는 software(OS handler)

상황·문제TLB 와 page walk 를 pipeline·OS 와 어떻게 연결하는가

원인모든 cache 접근 전에 translation 이 필요하고, page fault 는 ms 단위로 매우 길다

해결Inst/Data TLB 를 cache 앞에, miss 면 hardware walker. page fault 는 OS 가 untranslated mode 로 처리하며 그동안 다른 process 실행. restartable(precise) exception 필요

상황·문제TLB access 가 cache access 앞에 더해져 latency 가 늘어난다

원인clock 을 늦추거나 TLB·cache 를 pipelining 하면 모두 성능 손해

해결virtual address cache(VIVT, StrongARM): hit 면 translation 없음, miss 때만 TLB. 단점은 context switch flush(또는 ASID), aliasing, coherence. aliasing 은 OS 가 공유 page 의 cache index bit 를 맞춰 해결(early SPARC). 대안 VIPT 는 다음 강의

home 은 주소 담당 memory·directory, local 은 요청자, remote 는 복사본 보유 node

private 는 core 별 L2 로 중복·coherence 필요, shared 는 중복 없으나 contention·긴 latency

큰 cache 를 bank 로 나눠 core 와의 거리마다 latency 를 다르게 둠

shared cache 에 thread 구분 없이 LRU·pseudo-LRU 를 그대로 적용, interference 발생

physical = logical + base, bound 로 범위 검사, supervisor mode 에서만 변경

세 수(register·immediate·base) 덧셈을 두 수 덧셈과 비슷한 delay 로

external: 빈 공간이 불연속이라 할당 불가, internal: 고정 크기 page 안의 미사용 byte

page number + offset, page table 로 불연속 physical frame 에 mapping

접근 시 page 가 없으면 page fault 로 secondary storage 에서 가져옴 (Atlas 1962)

Atlas 의 page frame 당 1 개 register, 전부 비교해 없으면 page fault

level 별 index 로 쓰지 않는 영역의 table 생략, 대신 walk 에 memory access 여러 번

PTE 를 cache, hit 면 1 cycle translation, miss 면 page walk

TLB 가 동시에 mapping 하는 최대 virtual address 범위 = entry 수 × page size

page table 변경 시 다른 core TLB 의 stale entry 를 무효화, 보통 software 라 비쌈

virtual address 로 index·tag, miss 때만 translation — flush·aliasing·coherence 문제

cache line 에 process id 를 붙여 context switch flush 를 피함, tag overhead

두 VA 가 같은 PA 를 가리켜 virtual cache 에 두 복사본이 생기는 문제

4.1directory protocol 에서 exclusive block 에 read miss 가 나면 home 은 왜 owner 에게 fetch 하는가?

4.2shared LLC 가 private 보다 유효 용량이 큰 이유와 대가는?

4.3NUCA 의 static mapping 과 dynamic mapping 차이는?

4.4base & bound 방식에서 Job 4 를 실행할 수 없던 이유는?

4.5code·data segment 를 분리하면 얻는 이점은?

4.664-bit VA, 40-bit PA, 4KB page 의 linear page table 크기는?

4.7TLB 를 fully associative 로 만드는 이유는?

4.864 entry, 4KB page TLB 의 reach 는?

4.9software TLB miss handling 이 out-of-order superscalar 에서 비싼 이유는?

4.10virtual address cache 의 세 가지 단점은?