본 포스팅은 시험 보기 전에 저 혼자 간단하게 요약해보는 글입니다. 분명히 틀린 부분들이 있을 거에요, 참고 바랍니다.

Cache miss 종류

Compulsory : cold start, 처음엔 캐시에 아무것도 없어서 miss

Capacity : 데이터보다 캐시가 작아 miss 발생 → 캐시 사이즈 늘리기

Conflict : 같은 block에 매핑된 경우 miss → 캐시사이즈 늘리기, set 늘리기

Coherence : 다른 프로세스가 메모리를 update해서 cache와 memory가 일치하지 않음

Cache Hit Process in direct mapping cache

1. index (5 bit)로 cache의 index로 접근
2. cache에 저장된 tag와 physical address의 tag가 같은지 확인
3. hit면 data (5 bit block offset 사용) 읽기, miss면 하위 메모리로 요청

• fully associative는 physical address에서 index 필드 없이 tag - block offset만 있음

LRU (Least Recently Used)

새로운 캐시 블록이 오면 가장 priority를 높게 주고 가장 오래동안 안 쓴 cache를 evict

RRIP(Re-Reference Interval Prediction)

새로운 캐시 블록이 오면 뒤에서 두 번째에 넣음 (가장 낮은 block을 evict)

만약 큐에 존재하는 블록이 다시 reference되면 맨 앞에 넣음, 가장 높은 priority

Block Size Benefits and Drawbacks

• spatial locality에서 prefetch 효과가 있다.
• Spatial Locality가 별로 없을 때는 miss가 늘어난다
• block size가 커져서 access하는데 오래 걸리므로 miss penalty가 증가한다.

6 Basic Cache Optimizations

• larger total cache capacity miss는 줄이지만 hit time이 늘어나고 power comsumption 하다 → $\sqrt2$ rule(캐시가 2배 커지면, miss rate는 $\sqrt2$만큼 줄어듦
  
• Higher associativity conflict miss 줄어듦, hit time은 증가(mux logic이 복잡해짐), 다수의 tag comparison으로 power comsumption
  
• Pseudo Associativity
  • Direct mapped cache의 빠른 hit time과 Set associative cache의 낮은 conflict miss를 둘 다 잡을 수 있는 방법,
  • Cache를 나누고, 해시 함수를 이용해서 conflict 발생 시 다른 block으로 mapping될 수 있도록 함 (Direct mapped 기반에서 여러 번 conflict 발생 시 서로 다른 해시 함수 사용)
• Higher Number of Cache Levels
  • 전체적인 memory access time은 줄어듦 → 계산하는 법 외우기
  • Inclusive Multi-Level Cache : 바깥 캐시 사이즈가 안쪽 캐시 사이즈보다 클 경우 안쪽 캐시 내용을 바깥 캐시가 모두 cover, 반대는 Exclusive multilevel cache
    • 장점 : 가장 바깥 쪽 캐시만 보면 모든 데이터를 참조 가능
    • 단점 : 사실상 용량 낭비
• Read Miss를 Write Miss보다 먼저
• Address Translation을 avoid → hit time을 줄이도록, TLB 사용

VIPT (Virtually Indexed Physically Tagged)

Address Translation은 very expensive하다. 그래서 나온 방법이 TLB이다.

VIPT는 index는 virtual이고 Tag는 physical address를 사용하는 것이다.

direct mapped cache에서 VIPT를 사용하는 process

1. Tag를 TLB에서 virtual tag로 변환한다.
2. virtual index를 통해 cache block을 꺼낸다
3. 변환한 virtual tag와 cache에 저장된 tag를 비교하여 hit인지 아닌기 판단한다.

32KB 4-way set-associative에서 VIPT를 적용하는 방법

virtual tag에서 하나의 bit를 선택한 후 bit가 0인지 1인지에 따라 하나의 16KB 4-way set-associative cache를 선택한다.

10 Advanced Cache Optimization

• L1에서는 simple하고 작은 cache를 사용 → hit time과 power를 줄임
• Way Prediction → hit time을 줄임, 모든 way를 다 read하는 것은 매우 power consuming, 또한 MUX 연산도 time consuming. 그러니 way를 예측하자
• Non-blocking Cache
  • MSHR을 통해서 miss penalty 줄이기, miss가 나도 그 다음 request를 처리 가능하도록
• Multi Bank Caches
  • 캐시 bandwidth를 늘림
  • 캐시를 여러 independent bank로 구성한 다음 동시접근이 가능하도록 만든다.
  • 배열의 index를 다르게 만들면 bank conflict avoid 가능
• Critical Word First, Early Restart
  • miss penalty 줄임
  • line fill buffer에서는 보통 첫 번째 data가 가장 critical
  • line fill buffer는 바로 cpu에게 데이터 전송 가능 (hit under miss)
• Write merging (or coalescing) in the write buffer
  • miss penalty 줄임
• Compiler Optimization
  • Merging Array : struct같은걸로 배열 merge, spatial locality 향상
  • Loop Interchange : 루프의 순서 바꿈, 바깥 쪽이 row를 담당하도록, spatial locality 향상
  • Loop Fusion/Fission : 두 개의 루프로 할지, 하나의 루프 안에 계산할지 정하는 것, fusion은 temporal locality 향상, Fission은 레지스터를 적게 쓸 수 있어 load/store 연산을 줄일 수 있음 (fusion은 한 루프에 너무 많은 load/store 를 쓰게 됨)
• Hardware Prefetching
  • miss penalty / miss rate 줄임
  • when / where / what to be prefetched? 를 항상 고려해야 함
    • When : 너무 빠르게 prefetch하면 다른 useful data를 대체하게됨(cache pollution) 또한 그게 사용되기 전에 다시 replaced될 수 있음, 또 너무 느리면 processor stall을 멈출 수 없음
    • Where : Cache나 dedicated buffer에 저장, 캐시에 저장 시 cache pollution 가능
    • What : prefetch 정확도에 영향
  • Side Effects
    • prefetch된 데이터말고 evicted된 데이터가 필요하게 되면 cache pollution
    • 불필요한 prefetch는 불필요한 memory bandwidth를 늘림
  • Software based : Prefetch function 사용
  • Hardware Based : 캐시 내에 특정 하드웨어를 사용
  • Software based가 정확도는 더 높지만, 컴파일러 support 필요함, Hardware Based가 더 일반적임
  • Alpha AXP 21064 : cache miss가 나면 request된 block과 그 연속된 다음 block 두 개를 prefetch
    • requested block(i)은 캐시에, 연속의 다음 block(i+1)은 instruction stream buffer에 저장 → avoid cache pollution
    • cache miss but hit in the instruction stream buffer, then move stream buffer data(i + 1) into cache and prefetch next block(i + 2)
  • Prefetch-On-Miss : block b가 miss나면 b+1을 prefetch
  • One-Block-Lookahead(OBL) : block b가 access되면 b+1을 prefetch
  • Strided Prefetch : b, b + N, b + 2N이 access된 것이 관찰되면, b + 3N을 prefetch
  • Dead Block Problem : dead된 데이터는 빨리 evict하자,(대부분의 데이터는 dead임) 그러나 실제로는 dead data를 찾는 기법들이 있는데 실제 상황에 exploit하기 어려움
  • 너무 많은 prefetch는 memory bandwidth를 잡아먹음 → performance degradation
• Compiler-controlled prefetching

MSHR(Miss State Holding Register)

프로세서가 캐시에게 request를 보내면, MSHR은 request 정보를 저장한다.(requested data의 주소, read/write 정보, 기타 등등). MSHR은 해당 정보를 cache에서 가져올 수 있을 때까지 계속 지니고 있는다.

만약 요청한 데이터가 캐시에 없으면 MSHR은 miss state가 된다. 그 다음 MSHR이 캐시에서 해당 데이터를 가지고 올 수 있기 전까지는 다른 요청들을 처리하고 있는다. 마침내 캐시에서 가지고 올 수 있을때 비로소 해당 요청을 처리한다.

Non blocking cache

cache miss가 나도 그 다음 요청을 계속해서 이행한다. 메모리 측에서도 마찬가지로 병렬로 처리가 가능해야한다.(Bank 이용)

Memory

Accessing DRAM cells with time constraints

TRCD

TRAS + TRP = TRC

TRCD + CAS = TRAS…??

Memory Access Scheduling Problem

FCFS : 처음 온 거 처음 serve → 매우 안 좋음

FR-FCFS(First-Ready First-Come-First-Served) : open row 먼저, idle bank 먼저

Read Over Write : 일반적으로 read가 write보다 urgent하다. 따라서 먼저 처리해야됨

Consecutive read or writes : DRAM I/O pin은 bi-directional인데 changing direction은 1-2 cycle이 소비된다. 따라서 연속으로 read나 write를 처리해 direction change를 가급적 줄여야됨

Memory Commands

캐시 미스 종류(Compulsory, Capacity, Conflict, Coherence), direct mapping cache에서의 캐시 히트 프로세스, 블록 크기의 이점과 단점, 6가지 캐시 최적화 방법(larger total cache capacity, higher associativity, pseudo associativity, higher number of cache levels, read miss를 write miss보다 먼저, address translation을 avoid), VIPT(Virtually Indexed Physically Tagged), 10가지 고급 캐시 최적화 방법(L1에서는 simple하고 작은 cache를 사용, way prediction, non-blocking cache, multi bank caches, critical word first, early restart, write merging in the write buffer, compiler optimization, hardware prefetching, MSHR), DRAM 셀에 대한 시간 제약, 메모리 접근 스케줄링 문제(FCFS, FR-FCFS, Read Over Write, Consecutive read or writes), 메모리 명령어 등에 대해 다루고 있다.

Open/Close Row Policy

언제 precharge할건지, close page policy는 column access가 끝나는대로 바로바로 precharge

open page policy는 다음 access가 row buffer hit이길 hope하면서 precharge를 delay : timeout을 통해 어느 정도 기다림