Lec 19 · Prefetching 후반: 성능 metric·software/hardware·FDP·execution-based(runahead)

1.1ca_L12 p14~48: prefetcher performance metric(accuracy·coverage·timeliness)과 aggressiveness(distance·degree)

1.2software prefetching 의 어려움(x86 명령, 삽입 위치, HP PA8000 예)과 hardware prefetcher(next-line, stride, stream buffer, Pentium 4 locality-based)

1.3feedback-directed prefetching 으로 aggressiveness·insertion policy 적응, Q&A(mcf, BIOS prefetcher 설정)

1.4execution-based prefetcher 와 runahead execution, hybrid·multi-core prefetching 조율

상황·문제PLMS 에 갱신된 lecture note 를 올렸고 slide 순서를 바꿨다고 안내. 지난 시간 basic concept 이후 prefetch performance 부터 시작

상황·문제prefetcher 를 어떤 metric 으로 평가해야 하는가. 한 metric 만 보면 잘못 판단한다

원인보수적으로 쉬운 pattern 만 prefetch 하면 accuracy(정확도)는 높지만 coverage(커버리지)는 작다. timeliness(적시성)는 Venn diagram 에 안 잡힌다

해결accuracy·coverage·timeliness 를 동시에 보고, bandwidth 소비와 cache pollution(캐시 오염)도 고려. idle bus bandwidth 에 prefetch 를 보내고 demand 를 우선

상황·문제aggressiveness(공격성)가 모든 performance metric 에 영향. 최종 평가는 workload 의 IPC

원인너무 aggressive 하면 bandwidth·pollution, 너무 conservative 하면 coverage·timeliness 손해

해결두 knob 로 조절: prefetch distance(demand stream 보다 얼마나 앞서) 와 prefetch degree(demand access 당 몇 개)

상황·문제compiler/programmer 가 prefetch instruction 을 코드에 넣는 방식. 어디에, 얼마나 앞에 넣을지가 문제

원인모든 load 에 넣으면 대부분 cache hit 이라 memory·execution bandwidth 낭비. profile 입력이 대표성이 없을 수 있고, 수백 instruction 앞에 넣으면 사이의 branch 때문에 accuracy 하락

해결profile 로 miss 가능 load 만 골라 삽입, distance 도 profile 로 추정 (입력 대표성 한계는 남음)

상황·문제단순 loop X(i)=Y(i)+B*Z(i) 에서 prefetch distance 와 삽입 정책을 바꿔 speedup 측정

원인distance 를 늘리면 어느 지점까지 speedup 이 커지다 이후 오히려 감소. 이상적인 distance 는 다 돌려 봐야 안다

해결prefetch instruction minimization 여부 비교: capacity miss 가 많은 경우 차이 없음(70%), cache hit 이 높은 경우 minimization 안 하면 -55% (하면 -13%)

상황·문제전용 hardware 가 load/store(또는 miss) pattern 을 관찰해 과거 행동으로 prefetch

원인software prefetch 는 같은 binary 가 processor 마다 효과가 달라 portability 문제, execution bandwidth 도 소모

해결hardware 는 구현에 맞게 tuning, portability 문제 없음, instruction bandwidth 낭비 없음. 대가는 pattern detection 복잡도

상황·문제next-line 보다 일반적인 stride pattern 을 잡는 prefetcher

원인loop 안에서 여러 array 를 서로 다른 stride 로 접근하는 경우가 많음

해결PC 기반(Baer & Chen: load 별 last address·stride 기록 → last+stride prefetch) 또는 cache block address 기반(entry 별 tag·stride·confidence). stream buffer 는 별도 FIFO 에 prefetch

상황·문제많은 program 은 완전한 stride 가 아니라 근처 주소 안에서 random 해 보이는 pattern

원인stride detector 로는 region 내 localized random access 를 못 잡음

해결region 별 tracking entry: Invalid → Allocated(L2 demand miss) → Training(±16 block 안의 다음 2 miss 로 direction) → Monitor and Request. region 에 access 오면 P 부터 N 개 prefetch 후 region 을 N 만큼 이동

상황·문제Intel Pentium 4 결과: hardware prefetcher 를 켜면 최대 97% 성능 향상

원인single core 라 bandwidth 경쟁이 없었을 가능성. multi-core 에선 다른 core 의 demand access 와 경쟁

해결application 별 accuracy–IPC 변화 scatter: 대부분 향상되지만 일부는 저하/무영향 → 그런 경우 prefetcher 를 끄는 것이 나음

상황·문제고정 aggressiveness 는 application 에 따라 성능을 오히려 떨어뜨림

원인application 마다 최적 aggressiveness·insertion 위치가 다름. static policy 는 모두에 최적일 수 없음

해결accuracy·lateness·pollution 을 static threshold 로 분류해 aggressiveness(distance 4·degree 1 ~ 64·4) 조절, pollution 정도로 insertion 위치(MID/LRU-4/LRU) 선택

상황·문제왜 mcf 는 policy 에 따라 차이가 없나? program 이나 OS 가 thread 별 prefetch policy 를 고를 수 있나?

원인mcf 는 memory intensive·irregular access 에 miss rate 가 높아 prefetch 효과·pollution 영향 모두 작음 (강의자: 정확한 이유는 모름, 논문 참조). locality prefetcher 의 max N 이 4 뿐이라 작은 region

해결program 이 고르려면 hardware prefetcher 종류를 알아야 하고 새 세대에 적응 못함. 실제로는 BIOS 에서 일부 prefetcher 를 끌 수 있음

상황·문제pattern 기반 prefetcher 로 잡기 어려운 access 를 program 을 미리 실행해 prefetch

원인speculative thread 가 main thread 보다 충분히 앞서야 하고, address 생성과 무관한 계산은 낭비

해결miss 를 유발할 부분만 추출한 speculative thread 를 별도 core·SMT context·같은 context 의 idle cycle 에서 실행. branch/value prediction 을 쓰고 address 계산만 수행

상황·문제ROB 의 oldest instruction 이 long-latency cache miss 면 processor 가 오래 stall

원인small window 에서는 dependent instruction 때문에 곧 멈추고, 다음 miss(load 2)는 첫 miss 해결 뒤에야 발생

해결architectural state 를 checkpoint 하고 runahead mode 로 speculative pre-execute, L2 miss 의존 instruction 은 INV 로 표시. 원 miss 가 돌아오면 checkpoint 복원 후 재실행 → load 2 가 hit

상황·문제streaming·stride·linked structure·localized random 등 pattern 이 다양

원인여러 prefetcher 를 합치면 complexity·bandwidth 증가, prefetcher 간·demand 와 contention. multi-core 에선 shared data prefetch 가 다른 core 의 line 을 invalidate 할 수 있고 bus bandwidth 가 더 귀함

해결utility 추정 기반 우선순위, cost-benefit 분석, local controller throttling 을 override 하는 global controller

used prefetches / sent prefetches

prefetched misses / all misses. accuracy 와 함께 봐야 함

used prefetch 중 demand access 전에 도착한 비율

demand stream 보다 얼마나 앞서 / demand access 당 몇 line 을 prefetch 하는가

demand access/miss 뒤 항상 다음 N line. 단순하지만 stride·역방향에 무용

sequential prefetch line 을 cache 가 아닌 FIFO 에 보관, miss 시 head 비교

accuracy·lateness·pollution feedback 으로 aggressiveness·insertion 위치를 동적 조절

long-latency miss 동안 checkpoint 후 pre-execute 해 미래 miss 를 prefetch, 복귀 시 복원

여러 miss 를 동시에 처리하는 능력. runahead 효과의 상한

4.1accuracy 가 매우 높은 prefetcher 가 좋은 prefetcher 가 아닐 수 있는 이유는?

4.2next-line prefetcher 가 무용한 두 access pattern 은?

4.3FDP 가 prefetch 가 late 이고 pollution 이 없을 때 하는 일은?

4.4runahead execution 이 dependent cache miss 를 prefetch 하지 못하는 이유는?

4.5multi-core 에서 prefetch 효율이 더 중요한 이유는?