23.09.14 최초 작성
23.12.11 내용 추가 (TLB & Context Switching)

1. 용어

일반적으로 메모리 속도가 빠를수록 가격은 비싸지고 메모리 가격이 싸면 메모리 속도가 느려진다. 이를 해결하기 위해 Locality를 활용하고자 메모리를 계층 구조로 만들었다.

• Locality
  1. Temporal Locality : 최근에 접근한 메모리 공간에 다시 접근할 가능성이 높다.
  2. Spatial Locality : 최근 접근한 메모리 공간에 인접한 공간에 접근할 가능성이 높다.
  
• Block : 계층 간 데이터의 최소 단위이며 여러개의 Word로 구성되어 있음
• Hit : 접근한 데이터가 상위계층에 존재하는 경우
• Miss : 접근한 데이터가 상위계층에 존재하지 않는 경우
• Hit Ratio : 메모리 계층 구조의 특정 계층에서 찾을 수 있는 메모리의 접근 비율
• Hit Time : 메모리 계층구조의 상위 계층에 접근하는 시간
• Miss Penalty : 낮은 계층에서 상위 계층으로 블록을 인출하는 데 걸린 시간

2. Cache 동작

2.1 Cache Miss 처리

• 요청한 데이터가 올때까지 다른 파이프라인에 지연(Stall)발생
• 명령어 Cache Miss 시
  1. 원래 PC값을 메모리에 저장한다.
  2. 메인 메모리에 읽기를 지시하고 메모리가 접근을 끝마칠 때까지 기다린다.
  3. 메모리에서 인출한 데이터를 캐시에 저장한다.
  4. 명령어 수행을 처음부터 다시 시작한다.

2.2 Write 처리

2.2.1 Write-Through

• 캐시의 데이터가 수정된 경우 바로 메모리에도 수정된 내용을 반영하는 방법.
• 메모리에 접근해야하는 만큼 쓰기 작업 시간이 오래 걸리게 된다.
• Write Buffer를 활용해 해결할 수 있다.(메모리에 데이터가 쓰일 때 까지 데이터를 저장하는 공간) 하지만 Write Buffer가 비어있지 않을 때 지연이 발생할 수 있다.

2.2.2 Write-Back

• 캐시의 데이터가 수정된 경우 수정되었다는 표시(Dirty)를 남겨두고 일정 주기로 메모리에 업데이트하는 방법.
• Dirty Block이 제거되면 메모리에 해당 값을 수정한다.

2.2.3 Write Miss

• Write-Through
  1. Allocate on Miss : 해당 블록을 인출하고 캐시에 내용을 수정한다.
  2. Write Around : 블록을 인출하지 않고 메모리에 바로 수정한다.
• Write-Back : 요청한 블록을 읽어온다.

3. Cache Memory

3.1 Direct Mapped

• 메모리 주소에 의해 매핑할 캐시를 정하는 방법. 메모리 주소 비트의 일정 부분을 어느 캐시에 저장할지 정하는 Index로 두어 매핑 위치를 결정한다.
• 캐시에 존재하는 데이터가 원하는 데이터와 일치하는지 알 수 없다. Tag는 캐시 내의 Word가 요청한 것인지 아닌지 알 수 있는 정보를 나타내며 이는 인덱스로 사용되지 않은 주소의 상위 비트로 구성된다.
• 만약 메모리에 있는 정보가 변경되었고 캐시에 갱신되지 않은 경우 이를 Miss로 판단한다. 이를 해결하기 위해 Valid Bit를 캐시에 두어 캐시에 저장된 데이터의 유효성을 검사한다.

• 이 예시의 경우 Binary Address of Reference의 하위 3비트를 Index로 두고 상위 2비트를 Tag로 설정했다.

• 이 예시의 경우 31-14비트를 Index, 16-6비트를 Tag, 5-2비트를 Block Offset으로 두어 캐시에 적재된 4워드 중에 어떤 워드가 인출될지를 결정한다.

3.2 Associative Cache

• Fully Associative
  - 블록이 캐시 내의 어느 곳에나 위치할 수 있는 방식.
  - 데이터를 요청할 경우 모든 캐시 공간을 탐색해야 한다.

• n-way Set Associative
  - 한 블록이 들어갈 수 있는 자리의 개수가 고정되어 있다.

  • 데이터가 들어갈 한 집합을 선택하고 그 집합 내에서 데이터는 어느 곳에나 위치할 수 있다.
  • Index와 맞는 캐시 공간에 저장하고 데이터 인출 시 Tag를 통해 값을 찾을 수 있다.

• 4-way Set의 경우 예시
  

3.2.1 Replacement Policy

• LRU(Least Recently Used) : 가장 오랫동안 쓰이지 않은 데이터를 교체한다. (4-way까지는 효율적으로 사용할 수 있다)

• Random : 집합의 갯수가 많을 수록 LRU와 비슷한 성능을 가진다.

3.3 Multilevel Cache

기존 계층적 구조와 같이 캐시를 여러개 두고(Level 1, 2...) Level-n 캐시에 miss가 발생하면 Level-(n+1) 캐시에서 데이터를 탐색한다.

4. Cache Performance

프로세서의 성능지표인 CPU Time은 두 가지 종류로 분류할 수 있다.

• Instruction Execution Cycle : 명령어가 수행되는 시간
• Memory Stall Time : 메모리 인출 때문에 CPU가 멈춰있는 시간
  • Miss로 인한 지연시간을 Miss Penalty라고 한다.

$Memory\;Stall\;Time = Read\;Stall\;Cycle+Write\;Stall\;Cycle$

$Read\;Stall\;Cycle=(\frac{Count_{Read}}{Program}\times Miss\;Rate \times Miss\;Penalty)$

$Write\;Stall\;Cycle=(\frac{Count_{Write}}{Program}\times Miss\;Rate \times Miss\;Penalty)+ Write\; Buffer\; Delay$

메모리 지연 클럭 사이클
$Memory\;Stall \; Cycle = \frac{Instructions}{Program} \times frac{Misses}{Instruction} \times Miss \; Penalty$

4.1 Average Memory Access time

AMAT : 캐시 Hit, Miss, 여러 접근 빈도를 모두 고려한 메모리 접근 평균 시간

$AMAT = Time \; for \; hit \times Miss \; rate \times Miss \; Penalty$

5. Virtual Memory

5.1 Virtual Machine

• 물리적인 컴퓨터 상에 SW로 만들어낸 컴퓨터로 한 컴퓨터가 여러개의 VM을 실행시킬 수 있다.

• 하나의 컴퓨터 위에 하나의 OS만 있은 것을 효율화하고자 가상화층을 만들고 그 위에 새로운 OS를 새로 설치하는 기법.

• VM을 지원하는 소프트웨어를 Hypervisor (Virtual Machine Monitor)라고 한다.

• 기본이 되는 하드웨어 플랫폼을 Host라고 하며 호스트의 자원을 Guest VM에 공유된다.

• VMM은 가상자원을 물리자원으러 어떻게 사상할지를 결정한다.

• 소프트웨어 스택을 실행할 수 있는 추상화를 제공한다.

• 응용 프로그램이 컴퓨터에서 적합한 운영체제하에서 돌아가도록 하기 위함. 다양한 소프트웨어 스택이 하드웨어는 공유하면서 독립적으로 동작하는것을 가능하게 한다.

5.2 Virtual Memory

• 메인 메모리를 외부 저장장치를 위한 캐시로 사용하는 방법.
• 각 프로세스는 메인 메모리를 공유하며 자주 사용되는 데이터와 코드를 저장하는 자신만의 고유 주소 영역을 가지고 있다.
• 각 프로세스의 고유 주소 영역을 가상주소로 관리하여 다른 프로세스로부터 보호해준다.
• CPU(MMU)와 OS가 이러한 가상 주소를 실제 주소로 변환해준다.
• CPU는 가상 주소를 생성하고 캐시에는 실제 주소로 전달된다.
• 가상 메모리는 Block을 Page라고 하며 miss가 발생할 경우 Page Fault라고 한다.

• 가상 메모리 시스템의 주소는 Virtual Page Number와 Page Offset으로 나뉘어진다.
• Virtual Page Number는 Physical Page Number로 변환되며 Page Offset의 비트 수는 페이지의 크기를 결정한다.

5.2.1 Page Table

• 페이지가 저장되어 있는 위치를 저장하는 메모리의 공간이다.

  

• Page Table Register : 페이지 테이블이 존재하는 메모리 공간의 시작 주소를 나타냄

• Virtual Page Number : 페이지 테이블의 인덱스를 표시함

• Physical Page Number : 실제 주소의 정보를 가지고 있는 영역

5.2.2 Write 방식

• Disk Write 동작의 경우 수백만 사이클이 걸리기 때문에 Write Through방식을 활용하지 못한다.
• Write Back방식을 활용해 데이터가 수정되면 Dirty Bit를 1로 바꿔 OS가 어떤 페이지를 교체 대상으로 선택하면 새로운페이지를 갱신하기 전 그 페이지를 디스크에 써야할지 여부를 알려준다.

5.3 TLB(Translation-Lookaside Buffer)

• 메모리에 Page Table을 둬 주소를 변환하는 것 보다 이를 관리하는 캐시를 따로 두어 주소를 변환하는 것이 훨씬 빠르다. 이런 역할을 하는 캐시를 TLB라고 한다.

5.3.1 TLB Miss 처리

1. Page가 메모리의 Page Table에 있는 경우 : Page Table로부터 Page 정보를 인출해 재시도한다.

   • HW로 처리할 수 있지만 Page Table Structure가 복잡해질 수 있다.
   • SW적으로 특별한 예외처리를 통해 처리할 수 있다.

2. Page가 메모리의 Page Table에 없는 경우 : OS가 페이지를 인출하고 Page Table을 갱신한다. 그리고 나서 명령어를 다시 실행한다.

5.3.1.1 TLB Miss Handler

• TLB Miss가 발생한 경우는 1)Page Table에 페이지가 존재하지만 TLB에 존재하지 않는 경우, 2) Page Table에 페이지가 없는 경우가 있다.
• 모든 경우 Rd가 갱신되기 전에 TLB Miss를 인지해야 하며 Exception을 발생시킨다.
• 1)의 경우 TLB를 갱신해 명령어를 다시 시작하면 되고 2)의 경우 Page Fault를 처리해야 한다.

5.3.1.2 Page Fault Handler

1. 가상 주소로부터 인출할 주소를 찾는다.
2. 디스크에서 페이지를 찾는다.
3. 교체할 페이지를 찾고 dirty bit를 확인해 해당 페이지를 갱신할지 정한다.
4. Page Table을 갱신하고 프로세스를 다시 실행한다.

5.3.2 TLB & Context Switching

• Context Switching시 TLB 내용 flush되는 경우
  • TLB는 가상 주소 기준 주소를 변환
• TLB Entry에 프로세스 정보 저장
  • ASID (Address Space ID)를 TLB Miss시 저장해 Context Switching시 flush 필요 없음

6. Common Framework for Cache

1. Block Placement : 어떤 set에 Block을 위치시켜야 하는지
2. Finding a Block : set 내에서 원하는 Block을 어떻게 찾는지
3. Replacement : Block교체시 기존의 어떤 Block을 제거할건지
4. Write Policy : Write 작업 시 어떤 방법을 활용할건지(Write-Through, Write-Back)

6.1 Miss의 종류

1. Compulsory Misses (Cold Misses) : 접근하고자 하는 공간에 실행 이후 처음 접근할 때
2. Capacity Misses : 캐시가 필요한 모든 Block을 모두 포함할 수 없을 때
3. Conflict Misses (Collision Misses) : 캐시에 들어있는 데이터 사이에 경쟁을 벌일 때 (Fully-Association에서는 발생하지 않음)

• Trade Off

설계 변경	장점	단점
캐시 크기 증가	Compulsory Misses 감소	접근 시간 증가
연관도(n-way)증가	Conflict Misses 감소	접근 시간 증가
Block 크기 증가	공간적 지역성이 커져 블록 크기에 대한 miss 감소	Miss Penalty증가

7. Cache Control (Finite State Machine)

• Idle : 프로세서에서 읽기 / 쓰기 요청이 오기를 기다림

• Compare Tag : 읽기 / 쓰기 요청이 Hit인지 Miss인지 확인
  -Hit인 경우

  1. Cache Ready신호가 인가된다.
  2. 쓰기 요청일시 갱신 비트가 1이 된다.
  3. Block이 유효하면 Idle상태로 돌아간다.
  • Miss인 경우
  1. dirty bit가 1일 경우 Write-Back상태로 변경된다.
  2. 0이면 Allocate상태로 변경된다.

• Allocate : 태그와 인덱스로 이루어진 주소를 참조해 블록을 메모리에 쓰고 메모리로부터 Ready신호가 오면 Allocate상태로 넘어감

• Write-Back : 메모리에서 새로운 Block을 읽고 메모리에서 Ready신호가 오면 Compare Tag상태로 넘어감