컴퓨터 구조(12), Memory Hierarchy & Caches

Memory Hierarchy & Caches

---

Memory is Critical for Performance

- 메모리는 성능에 많은 영향을 미친다. ex) 메모리에서 로드 및 저장 -> 메인메모리나 디렘에서 한다면 매우 오랜 시간이 걸린다. ex2) 캐쉬 미스

- Fine-grained multithreading만 하더라도 매 사이클마다 발생하는 스톨을 줄일 수 있다.

- SIMD processors

 

Computation is bottlencked by Memory

- 데이터에 인텐시브하고, 큰 데이터에 대해 더 효율적이고 빠르게 처리하길 원한다.

- 이를 어떻게 핸들링하냐가 중요해진다.

- 데이터도 점차 증가한다.

 

Memory in a Modern System

- 캐쉬도 데이터를 들고 있을 수 있는 공간이다.

- L1은 각 코어마다 있다. 레지스터보단 크지만 작은 공간이다. 

- 멀티쓰레딩에서 이를 어떤식으로 디자인해야하는지는 중요하다.

- 디램으로 갈수록 더 많은 공간을 가질 수 있다.

 

Problem

- Bigger is slower: 데이터를 많이 들고 있으면 좋을 것 같지만 속도가 느려진다. 찾을 때 더 오래걸리기 때문이다.

- Faster is more expensive: SRAM > DRAM > Disk > Tape

- Higher bandwidth is more expensive: 데이터를 가져올 때 얼마나 큰 데이터를 가져올 수 있는지에 대한 내용인데 밴드 위스가 크면 더 많은 비용이 든다.

- SRAM은 캐쉬이다. 속도는 빠르지만 적은 용량에 대해서만 가능하다. 또한 매우 비싸다.

 

Why Memory Hierarchy?

- 하나의 메모리에 대해 빠르고 크기는 어렵다. 이에 따라 Hierarchy 구조로 멀티레벨 스토리지를 가지고 위의 문제점을 해결하고자한다.

 

The Memory Hierarchy

- locality: 최근에 사용한 것은 또 사용할 가능성이 높기에 가까운 곳에 놔둬서 빠르게 처리할 수 있도록 한다.

- L2, L3 캐쉬가 중간에 있는 역할을 한다.

 

Memory Hierarchy

- L1 캐쉬의 크기는 CPU의 클락 레이트에 의해 정해진다.  한클럭에 가져올 수 있는 크기로 놔둔다.

- 빠르고 큰 것을 누리기 위해서 위계 구조를 사용한다.

 

Locality

- Temporal Locality: 사용을 했으면 높은 확률로 또 사용할 가능성이 높다.

- Spatial Locality: 사용을 했으면 그와 관련이 높은 것을 할 가능성이 높다.

 

 

Memory Locality

- 예시

 

Caching Basics: Exploit Temporal Locality

- 최근에 엑세스한 데이터를 캐시에 둔다. 

 

Caching Basics: Exploit Spatial Locality

- 하나의 워드로 저장하기보단 블럭단위로 근처에 있는 데이터도 함께 캐시에 둔다.

 

 

The Bookshelf Analogy

- 책 예시를 통한 Hierarchy

- 손에 들고 있는 책은 제한되어있다. ex) register file

- 책상 위에 있는 책은 손에 들 수 있는 것보단 덜 제한적이지만 나름 제한적이다. 

- 선반 위에 있는 책 등등

- 위와 같이 최근에 접한 정도에 따라 계층적으로 둔다. 데이터를 쓰는 것도 비슷하게 최근에 접근한 데이터를 더 가까운 곳에 위치하게끔 한다.

 

Caching in a pipelined Design

- 중간 중간에 L2, L3 캐시를 둔다.

 

데이터를 어디에 둘 것인지: A Note a Manual vs Automatic Management

- 프로그래머가 수동적으로 데이터를 어디에 둘 것인지 정할 수 있다. 임베디드, GPU에서는 이를 한다.

- 하드웨어가 정해진 룰에 의해 이를 관리한다. 대부분의 경우에는 이 경우에 해당된다.

 

A Modern Memory Hierarchy

- 크기와 속도가 나와있다.

 

- 2GH라면 레지스터 파일이 0.5 ns가 걸렸으면 DRAM은 100nsec이기에 200사이클이 걸리게 된다.

 

 

Basic teminologies

- Hit: CPU가 캐시에서 데이터를 찾은 것

- Miss: CPU가 캐시에서 데이터를 못찾은 것

- Hit rate: 실제 찾은 비율

- Miss rate: 실제 못찾은 비율

- Miss penalty: 미스가 났을 때 얼마나 많은 시간이 걸리는지 

- EMAT: 원하는 데이터를 가져올 때 평균적으로 얼마의 시간이 걸리는지, Tc(캐시 엑세스 타임 -> 찾을 때 걸리는 시간) + m(미스) * Tm(미스 패널티) 

 

Multilevel Memory Hierarchy

- i는 어느 위치에 있는 것인지에 대한 내용이다.

 

---

2. Cache

- 자주 사용하는 것에 대해 기억하는 것을 의미한다. 웹 캐시도 비슷한 개념이다.

- 프로세서에서는 SRAM으로 이를 둔다.

 

Caching Basics (Conceptual Picture of a cache)

- Block: 캐시에 저장하는 단위

- 캐시를 저장할 때 중요하게 고려해야할 점

- Placement: 캐시를 어떻게 둘 것인지

- Replacement: 어떤 기존 데이터를 대체할 것인가

- Granularity of management: 블럭이 큰 것이 좋은지 작은 것이 좋은지

- Write plicy: 데이터를 어떻게 쓸 것인가

- Instructions/data: 이를 분리해서 둘 것인지

- Tag에는 캐시 블럭에 대한 정보를 나타내기에 어드레스나 밸리드한지, write bit과 같은 것, 메타데이터 등도 여기에 둔다.

 

 

Cache organization

- placement: 데이터를 어디에 둘 것인지

- Algorithm for lookup: 캐시에 있는 데이터를 어떻게 찾을 것인가

- Validity: 캐시에 있는 데이터가 유효한지 

 

 

Direct-mapped cache organization

- 8개 블럭 중에 올 수 있는 데이터를 정한다.

- Cache_index = Memory_address % Cache_Size

- Cache_tag = Memory_address / cache_size

- 태그는 어떤 데이터가 올라와있는지 표시한 것이다.

- 인덱스에 해당되는 것에 데이터를 넣는다.

 

Cache Lookup

- 4Gb Memory는 32 비트 주소이다.

- 256 Kb Cache이기에 32비트 주소 체계에서 메인 메모리에는 1G개의 워드가 있으며 캐시는 64K개의 워드가 있게 된다. 이는 16bit cache index를 사용한다. ex) 1 워드 = 4 비트

- 워드를 기준으로 30비트 주소 체계가 되고, 이를 16으로 나눈 값인 14가 태그, 나머지가 될 수 있는 16이 인덱스가 된다.

- 이는 아래와 같이 구성이 된다.

 

 

Sequence of Operation

- 인덱스는 무조건 있으니 인덱스에 태그를 보고 꺼내오고자하는 데이터인지 확인한다.

- 컴퓨터를 껐다가 켜면 랜덤하게 쓰레기 값이 캐시에 들어간다. 그러나 랜덤하게 초기화되어있는 값과 우리가 찾고자 하는 값과 동일하다고 판단하면 이를 방지하기 위해 Valid를 넣는다. 이에 따라 유효한 데이터인지 아닌지 이를 준다.

 

Hardware for direct mapped cache

- valid를 앤드조건으로 넣어서 이를 확인한다.

- Tag와 캐시 태그를 비교해 같은지 확인한다.

 

Repercussion on pipelined processor design

- 캐시에 찾는 것이 없었으면 스톨해야한다.

 

Cache read/write algorithms

- CPU가 캐시에 어드레스를 던진다. 이때 메모리에 바로 가기 전에 캐시에 접근한다. 있으면 꺼내주고, 없다면 다음 레벨에서 데이터를 전달한다.

 

- 데이터가 없다면 캐시를 로컬리티 특성에 따라 업데이트해준다.

 

Read Access to cache from CPU

- 인덱스에 들어간 뒤 태그를 비교해 같고, valid라면 이를 불러온다.

- 찾지 못한다면 다음 레벨로 넘어간다. 데이터가 실제로 리드될 때까지 이를 기다려준다.

 

 

Write Back

- 메인 메모리에 데이터를 쓰는 것이 아니라 캐시에 이를 써준다. 

- 캐시는 여유로울 때 이를 메인 메모리에 쓴다.

 

 Write Through

- 캐시와 메인 메모리 모두에 둘 다 데이터를 쓴다.

 

Write Access to Cache from CPU

- 두 가지 정책이 있다.

 

 Wirte Through Policy

- Write 버퍼: 메모리에 쓰기 위해 쌓아둘 수 있는 공간으로 이게 없으면 쓸 때까지 계속 스톨해야한다.

- Write 버퍼가 꽉차면 스톨한다.

 

 

 

Write Back Policy

 

- 캐시에다만 데이터를 쓴다.

- CPU는 상관 없을 것 같지만 업데이트가 안된다면 멀티 코어 환경에서 문제가 될 수 있다. 이에 따라 Dirty bit을 줘서 메모리 업데이트가 안된 값인지 알려준다.

- 캐시랑 메모리랑 일치하는지 확인해야한다. 이는 더티 비트로 확인한다.

- 이는 CPU 입장에서 Write Thorugh보다 조금 더 효율적이지만 복잡하다. 

 

Comparison of the Write Policies

- Write Through: 더디비트가 없기에 로직이 간단하고 빠르다. 하지만 버퍼에 꽉차면 이를 사용하지 못한다.

- Write Back: 더티비트나 엑스트라 로직이 필요하다. CPU 입장에서는 더 효율적이다.

- Multilevel cache processor는 둘 다 사용한다. L1은 Write through, L2/L3는 Write back을 한다.

- Write Through은 캐시 로직이 간단하기에 빠르기 때문에 L1에서 사용한다. 만약 write back을 하면 캐시 로직이 느려질 수 있기 때문에 L2, L3에서 사용한다.

 

 

Improving cache performance

- 캐시 퍼포먼스를 높이기 위해 miss rate를 개선하고, miss penalty를 줄이는 것이 중요하다.

 

Exploiting spatial locality to improve cache performance

- 지금 데이터를 쓰면 옆에 있는 것도 쓸 가능성이 높다. 이에 따라 블럭 단위로 데이터를 가져온다. 때문에 miss날 가능성이 낮아진다. 

 

예제)

예제: 4개의 워드로 블럭을 구성한다. 

- 256Kb에서 16 바이트만큼 사용하면 전체 블럭은 16K인 것을 알 수 있다. 이에 따라 인덱스 비트가 14개 필요하게 된다.

- 블럭 오프셋: 4개의 워드 중 어떤 데이터를 의미하는지, 이는 word offset과 바이트 offset이 2개씩 존재한다. 이는 멀티플렉서를 통해 어떤 데이터를 가져올건지에 대해 사용한다.

- 캐시는 로컬리티를 사용하기에 이를 효율적으로 개선할 수 있다. 블럭의 크기는 어떻게 할지도 중요하다.

 

Performance implications of increased blocksize

- 캐시를 디자인할 때 블럭 사이즈를 정한다. 

- y축은 miss rate, x축은 block size

- 블럭 사이즈를 키우면 Miss rate이 일정 수준까지 내려간다. 하지만 블럭 사이즈를 더 많이 키울수록 동일한 크기의 캐시에 저장할 수 있는 라인 개수가 적어지기에 저장할 수 있는 데이터가 줄어든다. 이에 따라 miss rate가 더 많이 난다.

 

Direct-Mapped Caches

- 같은 인덱스에 해당하는 메모리의 값은 캐시에 올라갈 수 없다는 단점이 있다.

- 하나의 인덱스에 하나의 엔트리만 둘 수 있다. 이에 따라 극단적으로는 hit rate가 0%가 될수도 있다. 

ex) 동일한 인덱스의 A, B를 반복해서 바꾼다.

 

Set Associativity

- 극단적인 경우를 막는다. 한 인덱스에 하나의 블럭만 두는 것이 아닌 두 개의 블럭을 둔다.

- 라인 개수는 줄어들지만 같은 인덱스에 있는 데이터도 사용 가능하다.

- Set을 나눠서 매핑해서 사용한다. 이에 따라 하나만 계속 사용하는 것을 방지한다.

- 찾을 때는 두 개를 모두 찾는다.

- 관리를 잘하면 성능이 올라간다.

 

 Flexible placement

- 사용하는 워킹 셋: 데이터 사용 공간

- 예시: Direct mapped는 위와 같이 안쓰는 공간과, 동일한 인덱스를 많이 사용하면 매우 비효율적이다.

 

Fully associative cache

- 인덱스를 없앤다. 캐시의 어느 공간이든 오래 안쓴 공간을 채워넣는다. 이에 따라 valid와 tag, data만 캐시에 존재하게 된다. 메모리 어드레스는 태그와 block offset만 가지고 있다. 이에 따라 tag를 보내어 이를 체크한다. 

- 매우 복잡하고 모두 비교를 해야하기에 하드웨어도 매우 커지게 되고 스피드도 느려진다는 단점이 있다.

 

Set associative caches

- 같은 사이즈의 캐쉬에 대한 내용이다. 

예제) 

그림은 4way이다.

 

Associativity (and Tradeoffs)

- 어소시에이티비티를 높이면 hit rate는 늘어난다. 하지만 데이터 엑세스하는데 걸리는 시간이 더 많아진다. 또한 더 많은 하드웨어를 필요로한다.

 

Instruction and Data caches

- 명령어와 데이터를 분리할 것인가.

- 동일하게 사용하면 속도가 느려지기에 분리해서 사용 가능하면 분리한다.

 

 Reducing miss penalty

- 미스 패널티를 줄이기 위해 L1 -> L2 -> L3를 가지고 중간에 계층을 둔다. 

- 이전에 비해 CPU 퍼포먼스가 증가하다보니 처음에는 L1에서 미스나면 메인 메모리에서 데이터를 찾더라도 큰 문제는 아니었지만 지금은 문제가 된다 

 

 

 

Cache Abstraction and Metrics

- 태그 스토어에 가서 어드레스에 있는 데이터가 있는지 확인한다.

- AMAT나 히트 레이트 등을 구할 수 있다.

- AMAT를 줄이는 것이 퍼포먼스에 항상 좋지는 않다. AMAT를 낮출 때 병렬처리하는 것을 잃어버릴 수 있다. 그러면 전체 성능에선 좋지 않다.

 

Blocks and Addressing in Cache

- fully associate만 아니면 인덱스가 있으니 이를 통해 tag에 간뒤, vaild인지 체크하고, 이를 찾는다. 

 

예시) Directed mapped

- 캐시에는 8블럭을 올릴 수 있고, 메인메모리는 32개의 블럭이 올 수있다. 이 중 8개만 캐시에 올릴 수 있다. Directed mapped은 갈 수 있는 곳이 정해져있다. 

- 편향되게 액세스하면 캐시를 제대로 사용못할 수 있다.

- 캐시 3 27분 영상

- Byte in block은 Data store에서 어떤 데이터를 찾는 것인지를 의미하는 것이다. 이는 MUX를 통해 찾는다.

- tag는 Tag store에 저장되어있고, 찾는 데이터인지 점검할 때 사용한다. 

 

 

higher Associativity

- 모두 vaild이고 데이터가 있다면 우선순위에 따라 데이터를 저장한다.

- Conflict miss는 줄어들지만 tag comparator가 많아지고 데이터 mux와 태그에 할당되는 것도 더 커진다.

 

 

 

Issues in Set-Associative Caches

- 캐시에 들어가 있는 정보를 대체할 때 어떤 우선순위를 둘 것인지가 중요하다. 이에 대해 세 가지 정도 주요한 디시전이 있다.

- Insertion: 데이터를 새로 채울 때 우선순위를 어떻게 둘까

- Promotion:  hit했을 때 우선순위를 어떻게 올릴 것인가.

- Eviction/replacement: 캐시가 미스됐을 때 어떤 것을 빼고 대체할 것인가

 

Eviction/Replacement

1. invalid block에 먼저 넣는다.

2. 다 vaild이면 replacement policy를정해야한다.

- 랜덤하게 넣기: 구현은 쉽다.

- FIFO: 먼저들어왔는데 중요할 수 있다. 

- Least recently used: 가장 최근에 안쓴 얘

- not most recenlty used

- Least frequently used

- Least costly to re-fetch: 하드웨어에서 정보를 다시 가져올 때 너무 오래걸리는 경우

- 블럭에 대한 정보를 tag에 두기에 위의 정책들에 대해 정하고 이 정보를 tag에 둘 수 있다.

 

Implementing LRU

- 블럭들의 최근에 쓰인 것 등의 순서를 추적해야한다.

- 2way보다 4way일 때 사용하는 비트수가 더 많아진다.

 

Approximations of LRU

- way가 매우 많아지면 이를 정확히 계산하는 것이 어려워 근사하여 사용한다.

 

Cache Replacement Policy

- LRU를 사용하더라도 4 way인데 a,b,c,d,e가 사이클을 돈다면 hit rate이 0%이다. 따라서 random이 더 좋을 수도 있다.

- Set thrashing

 

What's in a tag store entry

- vaild bit

- replacement policy bit 정책에 따른 비트

- Dirty bit 등등

 

Subblocked (Sectored) Cashes

- locality에 따라 근처에 있는 것도 블럭 단위로 가져오지만 필요없는게 있을 수 있다. 하지만 이를 가져오려면 시간이 더 오래 걸린다.

- 조금 더 어드밴스드하게 진행한다면 이를 모두 가져오는 것이 아니라 subblock 단위로 가져올 수 있고, 이를 채우지 않을 수 있다.

- 복잡한 디자인이 추가로 필요하다. Exploit spatial locality가 제한이 있다.

 

Instruction vs Data Caches

- 나눠 썼을 때와 같이 쓸 때

- 같이 쓴다면 다이나믹하게 할당해줄 수 있기에 공간을 효율적으로 사용할 수 있다. overprocisioning(캐시가 놀고있는 것)을 방지할 수 있다.

- 대신 충돌이 발생하면 느려질 수 있다.

- First level caches는 속도를 위해 항상 I cashes와 D cashes를 나눈다. 

- 높은 레벨의 캐시 (L2 ~ )는 같이 사용하는 경우가 많다.

 

Multi-level Caching in a pipelined Design

- 캐시에서 capacity와 스피드를 둘 다 잡기 위한 것이 멀티 레벨이다.

- First-level은 스피드가 중요하다. 적고 associativity도 낮다. -> 하드웨어도 작고 빠르게 하기 위해

- Second-level은 hit rate를 높이는 것이 중요하다. 

- Serial하게 동작한다. 

 

Classification of Cache Misses

- 캐시 미스는 세 가지 중 하나로 분류할 수 있다.

1. Compulsory miss: 캐시 공간이 초기화되어있고 내가 원하는 데이터가 안 들어가 있는 경우로 이는 처음에는 무조건 발생한다. such as 부팅

2. Capacity miss: 저장공간이 제한되기에 발생하는 이슈이다. Fully associative를 사용하더라도 발생할 수 있다.

3. Conflict miss: Directed mapped 등에서 발생하는 이슈로 Fully가 아니기 때문에 발생하는 이슈이다. 이는 느끼기 어렵다. 빈도수도 적다.

Compulsory는 부팅할 때 오래 걸리기에 이는 많이 느끼게 된다.

 

 

Miss를 낮추는 방법

- Prefeching을 사용하면 compulsory를 줄일 수 있다.

- Associativity를 사용하면 conflict를 줄일 수 있다. 인덱스를 랜덤하게 해줄수도 있다.

- capacity는 공간이 제한되어있기 때문에 발생하니 이를 효율적으로 배분해야한다.

 

 

- spatial locality를 높이기 위해 캐시의 라인이나 블럭 사이즈를 키우기도 한다.

- 위에 있는 내용을 했다.

 

Performance implications of memory hierarchy

- l1은 3사이클 이내에 데이터를 가져올 수 있다.

 

Memory hierarchy

- 각 코어마다 L1은 구분해둔다. I, D

- 밑으로 갈수록 정확도가 높아진다.