Lec 22 · VIPT·alias 방지·hashed page table·VM 역사, Memory Consistency(SC·TSO·fence)

1.1전반(~31분): Lec14 마무리 — VIVT alias 복습, VIPT 와 associativity 한계, MIPS R10000 의 L2 기반 alias 방지

1.2Atlas PAR 의 scalability 문제 → hashed page table·PowerPC, VM 기능의 역사와 오늘날의 VM 사용

1.3후반: Lec15 memory consistency — producer-consumer 투표, coherence vs consistency, write serialization vs atomicity

1.4SC 와 그 최적화(non-binding prefetch, speculation), store buffer 가 SC 를 깨뜨림 → relaxed model, TSO, fence (RC 는 다음 강의)

상황·문제translation 을 cache 접근 전에 하면 너무 비싸다 → virtual address 로 cache 를 접근하는 VIVT

원인같은 physical address 를 가리키는 두 VA 가 cache line 두 개로 존재 → 한쪽 write 후 다른 쪽이 stale data

해결OS 가 page 할당 시 page number 를 골라 duplication 이 생기지 않게 함 (software 해법)

상황·문제두 번째 해법: translation 과 cache 접근을 동시에

원인cache 가 크지 않으면 index 를 page offset bit 만으로 만들 수 있다

해결index 로 tag 를 읽는 동안 TLB translation, 둘 다 끝나면 physical tag 비교 → TLB latency 완전히 숨김

상황·문제VPN bit 를 index 에 쓰지 않으면서 cache 를 키우고 싶다

원인direct-mapped 를 2-way 로 바꾸면 set 수가 절반 → index bit 1개 감소

해결용량 2배면 4-way 로 → 같은 offset bit 로 set 접근. 그러나 L1 에 64-way 같은 건 너무 비싸 확장성 없음

상황·문제큰 L1 이 VPN bit a 를 index 에 쓰면 alias 가 생길 수 있다

원인L1 은 inclusive L2 가 뒷받침 → L1 miss 때 L2 정보로 alias 여부를 판단할 수 있다

해결L2 tag 옆에 VA bit a 저장. L1 miss·L2 hit 인데 a 가 다르면 기존 line 을 L1 에서 purge 후 새 line 설치 → alias 없음

상황·문제Atlas 는 physical page 마다 PAR 1개(최대 32개), PAR 에 VPN 저장

원인모든 PAR 를 비교해야 match 를 안다 → main memory 가 크면 비교 비용이 prohibitive

해결장점은 구조 크기가 main memory 에 비례. 단점은 scalability → hashing 으로 해결(다음 섹션)

상황·문제모든 page frame 과 VPN 을 비교하는 비용을 없애고 싶다

원인VPN(+PID) 의 hash 로 한 entry 만 접근. hash collision 가능

해결table 을 physical page frame 수의 2~3배로 두어 collision 감소, 못 찾으면 OS 의 full page table 조회. PowerPC 는 slot 당 PTE 8개를 hardware walker 가 검색, 실패 시 두 번째 hash

상황·문제VM 관리 방식은 컴퓨터 사용 방식과 함께 바뀌었다

원인bare machine(한 program) → batch multiprogramming(base&bound, external fragmentation) → time sharing(fixed-size page)

해결virtual machine monitor 는 guest VA → guest PA → host machine PA 로 translation 한 단계 추가

상황·문제smartphone~server 는 full demand-paged VM: portability, protection, 작은 physical memory 공유

원인supercomputer(vector) 는 swap 중 CPU 가 놀면 낭비가 크고 restartable vector instruction 구현도 어려움

해결job 이 memory 에 맞도록 운용 (학과 cluster 도 swap 하면 성능 급락). GPU 는 원래 수동 copy, 이후 host-device demand paging 추가. embedded·DSP 는 VM 없이 필요한 용량을 맞춤

상황·문제producer 가 data 를 쓰고 flag=1, consumer 는 flag 가 0 이 아닐 때까지 spin 후 data load

원인각 instruction 이 atomic 이고 context switch 가 없어도 동작 보장 여부는 알 수 없다 (투표)

해결답: machine 의 memory consistency model 에 달려 있다

상황·문제consistency 를 coherence 와 혼동하기 쉽다

원인coherence 는 같은 위치에 대한 eventual write propagation 과 write 의 single order 만 보장. 다른 위치, 전파 시점, write atomicity 는 보장 안 함

해결consistency model 은 서로 다른 위치에 대한 load/store 순서를 정하는 hardware·compiler·programmer 사이의 contract. fence·barrier 가 safety net

상황·문제P1 이 X=1, P4 가 X=2 를 쓸 때 P2 는 1→2, P3 은 2→1 로 관측

원인write 순서가 processor 마다 달라 write serialization 위반 (coherence protocol 이 막는 것)

해결write atomicity: store 가 모든 core 에 논리적으로 동시에 보여야 함. X·Y 예에서 P2 는 X 만, P3 는 Y 만 본 경우가 위반

상황·문제가장 기본적인 model: 각 processor 가 program order 로 issue, 모든 processor 가 같은 single order 를 봄

원인switch 가 memory 를 한 번에 한 processor 에만 연결하는 모델 — 사실상 bus(random 제외)

해결producer-consumer 는 store-store, load-load 순서가 SC 로 보장되어 동작. 단점은 concurrent memory access 불가로 성능 제한

상황·문제program order 를 엄격히 지키면 성능 손해

원인cache 내용 변경은 architectural state 를 바꾸지 않는다

해결non-binding prefetch 로 line 을 S(읽기)·M(쓰기) 상태로 미리 가져오되 register 에 넣지 않음. 뒤 load 를 먼저 수행하고 commit 전 invalidation 이 오면 squash·replay

상황·문제flag1=1 후 flag2==0 이면 critical section 진입 (반대편도 대칭)

원인store 가 store buffer 에 머무는 사이 load 가 bypass → 두 CPU 모두 flag 0 을 읽고 동시 진입

해결store buffer 없이는 성능 손해가 커서 대부분 machine 은 SC 를 포기. uniprocessor 최적화를 multiprocessor 로 묶으며 weaker model 이 생김

상황·문제read/write 쌍 사이 ordering 을 완화해 reordering 허용, 일부는 write atomicity 도 미보장

원인필요하면 fence·barrier, 또는 acquire/release 같은 명시적 synchronization

해결TSO(SPARC, x86): W→R 완화 / PSO: W→W 도 / RMO: 4가지 모두 / RC(Itanium): 4가지 모두 + release store·acquire load

상황·문제IBM-370·x86·SPARC TSO, RISC-V RVTSO(선택)

원인processor 가 자기 write 를 다른 processor 보다 먼저 볼 수 있음(store buffer), read 가 write 를 bypass 해 write latency 를 숨김

해결producer-consumer 는 store 순서가 유지되어 여전히 동작. 하지만 A=1;print B / B=1;print A 에서 A==0·B==0 이 가능 (SC 는 불가)

상황·문제relaxed model 에서 원하는 ordering 을 보장하고 싶다

원인hardware 가 아무 보장도 안 하면 결과를 예측할 수 없고 programmer 는 모든 연산 사이에 fence 를 넣어야 함

해결fence w,w 는 앞선 write 완료 후 다음 write, fence r,r 은 read 간 순서 강제. release consistency 는 다음 강의로

page offset bit 로 index 해 TLB 와 cache 를 동시 접근, physical tag 비교. 크기 ≤ page size × way

같은 PA 를 가리키는 두 VA 가 cache 에 두 copy → write 가 다른 copy 에 안 보임

L1 의 모든 line 이 L2 에도 있음. R10000 은 여기에 VA bit 를 저장해 alias 감지

physical frame 기준 table 을 VPN hash 로 접근, 2~3배 크기로 collision 감소

서로 다른 위치 load/store 의 순서 규약. hardware·compiler·programmer 사이의 contract

같은 위치 write 의 단일 순서(coherence) vs store 가 모든 core 에 동시에 보임

program order + 모든 processor 가 보는 single global order (Lamport 1979)

line 을 S/M 으로 미리 가져오되 register·data 불변 → SC 를 깨지 않는 최적화

store 를 buffer 에 두고 load 가 bypass → W→R reordering, SC 위반의 주원인

W→R 만 완화(x86·SPARC). data/flag 는 동작, A=1;print B 류에서 0·0 허용

fence w,w / fence r,r 로 앞뒤 연산 순서를 강제

4.1VIPT 에서 alias 가 생기지 않는 cache 크기 조건은?

4.2MIPS R10000 은 L1 alias 를 어떻게 막는가?

4.3Atlas PAR 방식의 단점과 hashed page table 의 대응은?

4.4cache coherence 가 보장하지 않는 것은?

4.5store buffer 가 SC 를 깨는 예는?

4.6TSO 에서 A=1;print B / B=1;print A 가 0,0 을 출력할 수 있는 이유는?