[CSAPP] 6.3 The Memory Hierarchy(메모리 계층구조)

• 위 그림은 일반적인 메모리 계층구조를 보여준다.
• 일반적으로 저장 장치는 더 높은 수준에서 낮은 수준으로 이동할수록 더 느리고, 더 저렴하고, 더 커진다.
• 최고 수준 (L0)에는 CPU가 단일 클럭 사이클로 엑세스 할 수 있는 소수의 빠른 CPU 레지스터가 있다.
• 다음은 몇 번의 CPU 클럭 주기로 액세스할 수 있는 하나 이상의 소형에서 중간 크기의 SRAM 기반 캐시 메모리이다.
• 그 다음에는 수십에서 수백 번의 클럭 사이클로 액세스할 수 있는 대용량 DRAM 기반 메인 메모리이다.
• 다음은 느리지만 거대한 로컬 디스크이다.
• 마지막으로, 일부 시스템에는 네트워크를 통해 액세스할 수 있는 추가 수준의 디스크이다.
  • 예를 들어, AFS(Andrew File System) 또는 NFS(Network File System)와 같은 분산 파일 시스템을 사용하면 프로그램이 원격 네트워크에 연결된 서버에 저장된 파일에 액세스할 수 있다. 마찬가지로 월드 와이드 웹을 사용하면 프로그램이 전 세계 어디서나 웹 서버에 저장된 원격 파일에 액세스할 수 있다. 

6.3.1 Caching in the Memory Hierarchy(메모리 계층구조에서 캐싱)

• cashe는 작고 빠른 저장 장치로, 크고 느린 장치에 저장된 데이터를 staging 해놓는 역할을 한다.
• cashe를 사용하는 프로세스를 캐싱(caching)이라고 한다.
• 메모리 계층 구조에서 핵심은 계층의 각 단계(더 작고 빠른, K)는 하위 단계(더 느리고 큰, K + 1)의 저장 장치의 캐시 역할을 한다.
  • 예를 들어, 로컬 디스크는 네트워크를 통해 원격 디스크에서 검색된 파일(웹 페이지 등)의 캐시 역할을 하고, 메인 메모리는 로컬 디스크의 데이터를 위한 캐시 역할을 한다.
• 위 그림은 메모리 계층구조에서 캐싱의 일반적인 개념을 보여준다. 
  • k + 1 레벨의 스토리지를 보면 'block'이라고 하는 연속적인 데이터의 chunks로 불리된다. 
  • 각 블록은 다른 블록과 구별되는 고유한 주소 또는 이름이 있다.
  • 블록은 일반적인 경우 고정 크기, 웹 서버에 저장된 원격 HTML 파일의 경우 가변 크기이다. 
    • 위 그림의 예를 보면, K + 1 레벨의 스토리지에서는 0~15까지 번호가 붙은 16개의 고정 크기 블록으로 분할된다.
    • 레벨 K 스토리지에서는 레벨 K + 1 블록과 동일한 크기의 더 적은 블록 집합으로 분할된다.
    • 레벨 K의 캐시에는 레벨 K + 1의 블록의 하위 집합 복사본이 포함된다. 
  • 블록 크기는 인접한 계층 단계에서는 특정 쌍 단계끼리는 고정되지만 멀리 떨어진 다른 단계와는 서로 다른 블록 크기를 가질 수 있다.
    • 예를 들어, 그림 6.21에서 L1과 L0 사이의 전송은 일반적인 Word 크기의 블록을 사용한다. 반면, L5와 L4 간의 전송은 수백 또는 수천 바이트의 블록을 사용한다. 일반적으로 하위 계층(CPU와 멀리 떨어진) 장치는 액세스 시간이 더 길기 때문에 더 긴 액세스 시간을 상각하기 위해 더 큰 블록 크기를 사용한다.

Cache Hits(캐시 히트)

• 프로그램이 레벨 k + 1에서 특정 데이터 객체를 필요로 할 때, 프로그램은 먼저 레벨 K에 현재 저장된 블록 중 하나에서 d를 찾는다.
• 만약 d가 레벨 k에서 캐시된다면, 이 경우를 Cache Hits(캐시 히트)라 한다.
• 프로그램은 레벨 k에서 직접 읽기 때문에, 메모리 계층의 특성상 레벨 k + 1에서 읽는 것 보다 더 빠르다. 
  • 예를 들어, 시간적 지역성(temporal locality)이 좋은 프로그램은 특정 블록 d에서 데이터 개체를 읽어서 레벨 k에서 Cache Hits가 일어난다.

Cache Misses(캐치 미스)

• 만약 데이터 개체 d가 수준 k에서 캐시되지 않을 경우를 Cache Misses(캐치 미스)라 한다.
• Cache Misses(캐치 미스)가 일어날 경우 레벨 k의 캐시는 레벨 k + 1의 캐시에서 블록을 가져온다.
• 레벨 k 캐시가 이미 가득 찬 경우 기본 블록을 overwrite(덮어쓸 수)할 수 있다.
• 기존 블록을 overwriting 하는 이 프로세스를 replacing or evicting the block(블록 교체 또는 제거)라 한다. 
• 제거되는 블록을 victim block(피해자 블록)이라고도 한다.
• 대체할 블록에 대한 결정은 cache’s replacement policy(캐시 교체 정책)에 의해 결정된다. 
  • 예를 들어, random replacement policy(랜덤 교체 정책)은 a random victim block을 교체할 것이다.
  • a least recently used (LRU)replacement policy(최근 사용 교체 정책)은 가장 오래 전에 엑세스 했던 블록을 교체할 것이다.
• 레벨 k의 캐시가 레벨 k + 1에서 블록을 fetch(가져온 후) 프로그램은 레벨 k에서 해당 블록을 읽을 수 있게 된다.
  • 예를 들어, 그림 6.22에서 레벨 k 캐시의 블록 12에서 데이터 객체를 읽으면 블록 12가 현재 레벨 k 캐시에 저장되어 있지 않기 때문에, Cache Misses(캐치 미스)가 발생한다. 레벨 k + 1에서 레벨k로 복사된 블록12는 나중에 액세스할 것으로 예상되어 그대로 유지된다.

Kinds of Cache Misses(캐치 미스의 종류)

• compulsory misses or cold misses(필수 누락, 콜드 누락): cold cache라 불리는 빈 캐시가 있을 때 데이터 개체에 대한 액세스가 누락된다.

 

• 캐치 미스가 있을 때마다 레벨 k의 캐시는 레벨 k + 1에서 검색한 블록을 배치할 위치를 결정하는 배치 정책(placement policy)을 실행해야 한다.
• 가장 유연한 정책(The most flexible placement policy)은 레벨 k + 1의 블럭을 레벨 k의 랜덤한 블럭에 저장하는 것이다.
• 하드웨어에서 구현되고 속도가 높은 메모리 계층(CPU 근처)의 캐시의 경우 랜덤하게 배치된 블럭을 찾는 데 비용이 많이 들어 이 정책을 그대로 전부 실행하기에는 비용이 너무 많이 든다.
• 따라서 하드웨어 캐시는 일반적으로 레벨 k + 1에서 특정 블럭을 레벨 k에서 블록의 작은 부분 집합(sometimes a singleton)으로 제한하는 더 단순한 배치 정책을 실행한다. 
  • 예를 들어, 그림 6.22에서 레벨 k + 1의 블럭 i를 레벨 k의 블럭(i mod 4)에 배치해야 한다고 결정할 수 있다.
  • 예를 들어, 레벨 k + 1의 블럭 0, 4, 8, 12는 레벨 k의 블럭 0에 맵핑되고, 블럭 1, 5, 9, 13은 레벨 k의 블럭 1에 맵핑된다. (열 단위로 접근)
  • 그림 6.22 예제 캐시는 이 정책을 사용한다.
• 이러한 제한된 배치 정책은 conflict miss(충돌 누락)이라고 하는 유형의 미스로 이어진다. 
• 이 경우 캐시는 참조된 데이터 개체를 보유할 수 있을 만큼 크지만 동일한 캐시 블럭에 맵핑되기 때문에 캐시가 누락된 상태로 유지된다. (직접 블럭을 올려 캐싱 해놓지 않고 작은 부분 집합에 맵핑하기 때문에)
  • 예를 들어, 그림 6.22에서 프록램이 블럭 0, 블럭 8, 블럭 0, 블럭 8을 요청하는 경우, 이 캐시가 총 4개의 블럭을 포함할 수 있는 크기를 가진다하더라도 이 두 블럭(블럭 0, 블럭8)에 대한 참조는 레벨 k의 캐시에서 누락된다. (k +1에 맵핑되어 있을 뿐)

 

• capacity misses(용량 누락): 중첩된 루프에서 동일한 배열의 요소를 계속해서 액세스 할 경우, 이 블럭 집합을 working set of the phase이라 한다. 작업 세트의 크기가 캐시 크기를 초과하면 캐시에서 capacity misses(용량 누락)이 발생한다. 즉, 캐시가 작아서 이 특정 작업 세트를 처리할 수 없는 경우이다. 

Cache Management(캐시 관리)

• 앞서 말했듯이, 메모리 계층구조에서 핵심은 각 레벨(빠른 단계)의 스토리지 디바이스가 다음 레벨의(더 느린 단계) 캐시라는 것이다.
• 각 수준에서 캐시를 관리하는 로직이 필요하다.
• 즉, 캐시 스토리지를 블럭으로 분할하고, 서로 다른 레벨 간에 블럭을 전송하고, 캐시히트와 미스가 발생하는 시기를 결정한 다음 이를 처리해야 한다.
• 캐시를 관리하는 로직은 하드웨어, 소프트웨어 또는 둘의 조합일 수 도 있다.
• 예를들어, 컴파일러는 캐시 계층의 가장 높은 수준인 레지스터 파일을 관리한다. 컴파일러는 캐치 미스가 있을 때 로드를 실행할 시기를 결정하고 데이터를 저장할 레지스터를 결정한다.
• 위 그림 6.21 L1, L2, L3 수준의 캐시는 캐시에 내장된 하드웨어 로직에 의해 관리된다.
• 가상 메모리가 있는 시스템에서 DRAM 메모리는 디스크에 저장된 데이터 블럭의 캐시 역할을 하고 CPU의 운영 체제 소프트웨어와 주소 변환 하드웨어(address translation hardware)의 조합에 의해 관리된다.
• AFS와 같은 분산 파일 시스템이 있는 시스템의 경우 로컬 디스크는 로컬 시스템에서 실행 중인 AFS 클라이언트 프로세스에 의해 관리된다. 
• 대부분의 캐시는 이러한 로직에 의해 자동으로 작동하며 프로그램에서 특정한 명시적인 작업이 필요하지 않다.

6.3.2 Summary of Memory Hierarchy Concepts(메모리 계층 구조 개념 요약)

• 요약하자면 캐싱을 기반으로 하는 메모리 계층 구조는 지역성(locality)의 장점을 가진다.
  • 시간적 지역성(temporal locality): 캐시 덕분에 동일한 데이터 개체가 여러 번 재사용될 가능성이 높다. 데이터 개체가 첫 번째 누락 시 캐시에 복사될 경우 향후 해당 개체에 대한 캐시히트가 일어날 수 있기 때문이다.
  • 공간적 지역성(spatial locality): 블럭에는 일반적으로 여러 개의 데이터 개체가 포함되기 때문에 같은 향후 블럭에 대한 참조(캐시 히트)가 일어날 경우 공간적 지역성이 좋아진다.
• 캐시는 현대 컴퓨터 시스템의 모든 곳에서 사용된다. 그림 6.23에서 알 수 있듯이 캐시는 CPU칩, 운영체제, 분산 파일 시스템 및 World Wide Web에서 사용된다. 
• 하드웨어와 소프트웨어의 다양한 조합으로 구축되고 관리된다.
• 그림 6.23에서는 아직 다루지 않은 여러 용어와 약어가 있는데 이는 캐시가 얼마나 일반적인지 보여주기 위해 이러한 기능이 포함되어 있다.