[컴퓨터구조] 캐시(2)

현재 글은 이 글에서 이어진다.

---

Replacement Algorithm

 캐시의 크기는 메모리 용량의 0.1% 수준으로 새로운 데이터를 캐시에 들여놓기 위해서는 기존에 캐시 내에 존재하던 데이터를 캐시 밖으로 내보내야 한다. 이때 캐시 내 어떤 데이터가 먼저 대체되어야 하는지에 대한 규칙이 필요하며, 이를 위해 Replacement Algorithm이 존재한다.

 캐시 매핑 방식에는 Direct, Fully Associative, Set Associative가 존재했다. 이때 Direct mapping 방식에서는 모듈러 연산에 의해 모든 데이터가 들어갈 캐시 상의 라인이 정해져 있으므로 어떤 데이터를 먼저 제거할지에 대해 고민할 필요가 없다. 대체 알고리즘은 Associative 방식들에 대해서만 필요하다.

 여기서 중요한 점은 캐시가 속도 향상을 위한 하드웨어라는 사실이다. 캐시가 높은 속도를 유지하기 위해서는 알고리즘이 하드웨어 상에 구현될 수 있어야 하며, 구현 방식도 간단해야만 한다. 소프트웨어로 구현해야 할 만큼 회로가 복잡해지는 경우 해당 알고리즘은 사용되지 않는다.

캐시의 replacement 알고리즘에는 3가지가 있다.

• Least Recently Used(LRU)
• First-In-First-Out(FIFO)
• Least Frequently Used(LFU)

---

Least Recently Used(LRU)

 사용된 지 가장 오래된 것부터 교체하는 방식이다. 최근에 사용된 데이터는 가까운 미래에 다시 사용될 확률이 높다는 temporal locality을 반영하여 가장 오랫동안 참조되지 않은 캐시를 제거하고 새로운 데이터를 해당 자리에 받는다. 상대적으로 구현이 간단하며 locality을 반영한다는 점에서 자주 사용된다고 한다.

4way set associative. 순위 업데이트 과정

 4 way set-associative 기준으로 각 자리마다 순서를 구분하기 위해 2비트 크기의 플래그를 둔다. 특정 라인에 접근할 때 00이 되며, 다른 라인들은 숫자가 하나씩 늘어난다. 만약 miss가 발생하는 경우 플래그 상태가 11인 참조가 가장 오래된 라인의 데이터와 새로운 데이터를 교체한다. 이 방식은 간단해 보이지만 각 자리를 업데이트하는데 오버헤드가 발생할 수 있으며 하드웨어 구현이 다소 복잡해질 수 있다. 따라서 비트를 더 약식으로 나타낸 pseudo-LRU 방식을 이용한다.

https://en.wikipedia.org/wiki/Pseudo-LRU 

 pseudo-LRU는 가장 오랫동안 접근하지 않은 대상을 명확하게 대략적으로 찾아내는 방식으로, 한 세트에 대해 3비트를 이용하여 대략적으로 변경 대상을 찾는다. 3비트로는 총 2³ = 8가지 경우의 수만 나타낼 수 있으므로 4 way LRU에서 표현할 수 있던 24가지 경우의 수에 비해 정확도는 떨어져 근사적으로 위치를 선택할 수밖에 없지만, 구현이 훨씬 간단해서 일반적인 LRU보다 더 많이 사용된다. 현재 비트가 가리키고 있지 않은 위치의 라인에 새로운 데이터를 넣는다.

pseudo-LRU : https://en.wikipedia.org/wiki/Pseudo-LRU#/media/File:Plruexample.png

First-In-First-Out(FIFO)

 단순히 처음 들어온 순서대로 데이터를 대체하는 방법이다. round-robin이나 원형 큐 구조만 있으면 구현할 수 있을 정도로 매우 간단하며, 캐시에서 miss가 발생하는 시점에만 순위 값을 업데이트해주면 된다는 점은 좋지만, FIFO의 사용을 정당화하기 위한 근거가 없다는 문제가 있다. LRU의 경우 temporal locality을 근거로 업데이트를 진행하여 효율적일 것을 예측할 수 있지만, FIFO은 그렇지 않다.

Least Frequently Used(LFU)

 가장 덜 접근한 라인의 데이터와 새로운 데이터를 대체하는 방법이다. 자주 접근하는 데이터는 이후에도 많이 접근할 가능성이 높다고 판단할 수 있으므로, 웹처럼 사용자가 자주 접근하는 사이트가 따로 존재하는 경우 LFU를 소프트웨어적으로 구현하여 사용하기도 한다.

 문제는 캐시에서는 LFU을 하드웨어로 구현해야 한다는 점이다. LFU는 접근 횟수를 기준으로 대치할 라인을 선택하는 특성상 각 라인에 대한 접근 횟수를 기록하기 위한 카운터와 이를 관리하기 위한 로직이 추가적으로 필요해지는데, 이를 하드웨어적으로 구현하면 하드웨어가 너무 복잡해지기 때문에 실제로 이 방법을 쓸 일은 없다.

---

Write Policy

 캐시의 내용을 읽는 것은 별로 어렵지 않다. 읽기 동작은 어떤 값도 변경하지 않으므로 단순히 hit 하면 해당 데이터를 읽고, miss 하면 메인 메모리에서 읽어오면 끝이다. 그러나 캐시에 내용을 쓰는 경우 캐시와 메모리 사이에서 값이 달라지기 때문에 문제가 발생할 수도 있다. 예를 들어 다음과 같은 문제들이다.

1. DMA(Direct Memory Access)를 통해 I/O를 할 때 메인 메모리에 있는 유효하지 않은 데이터를 기준으로 출력한다.
2. power failure의 발생을 감지하면 컴퓨터는 메인 메모리의 내용을 하드디스크 등 보조기억장치에 저장해두는데, 이 경우 캐시의 새로운 내용은 반영되지 않는다.
3. 캐시에 있는 데이터가 우선순위에 밀려 나가는 경우 변경된 캐시의 내용이 메모리에 복사되어야 한다. 이때 수정되었음을 알리는 dirty bit는 캐시의 블록단위마다 존재하기 때문에 블록 내 한 비트만 수정되더라도 전체를 모두 수정해야 하는 오버헤드가 발생한다.

 위와 같은 여러 문제들로 인해 캐시에 어떻게 내용을 작성할 것인지 정책을 정하는 것이 중요하다. 주요 정책은 write 할 때 hit 한 경우와 miss 한 경우에 대해 2개씩 존재한다.

• write hit: 캐시 내에 찾는 내용이 있는 상황
  • write through: 값이 수정될 때마다 모든 레벨의 대응되는 값을 교체
  • write back: 캐시의 값을 수정하고 dirty bit 설정. 대체될 때 dirty bit가 수정된 경우 메모리 수정
• write miss: 캐시 내에 찾는 내용이 없는 상황
  • write allocate(fetch-on-write) : 메모리에서 캐시로 가져온 후 WRITE 하고 다시 하위 계층에 작성
  • write around : 메모리 상에서 WRITE 하고 캐시로 가져오지는 않음

---

Write through

 캐시에서 내용을 쓸 때마다 자신의 하위 계층의 캐시 및 메모리의 내용도 모두 수정하는 방식이다. 가장 단순한 방법이며 항상 캐시의 내용과 메모리의 내용이 일치한다는 장점이 있지만, 캐시 내에 hit이 발생할 때마다 하위 모든 계층의 내용을 수정해야 하기 때문에 메모리 트래픽이 크게 증가하고 병목 현상이 발생할 수 있다는 문제점이 존재한다. 단, Read : Write = 8 : 2 인 컴퓨터 동작 특성상 Write through 방식을 채택하더라도 큰 성능 저하는 아니라는 입장도 있다.

Write back

 캐시에 내용을 쓸 때 dirty bit을 수정하여 라인이 수정되었음을 나타내고, 차후 해당 라인이 replace algorithm 등에 의해 다른 데이터와 대체되는 시점에 dirty bit을 검사하여 값이 변경된 경우에만 메모리에 내용을 쓰는 방식이다. 캐시에 대해 miss 가 발생할 때 메모리 내용이 수정되므로 write through 방식에 비해 메모리 접근 횟수가 적다는 장점이 존재하나(miss ratio는 대략 5%), 각 라인에 대해 dirty bit을 둬야 하므로 캐시 구조가 복잡하며, DMA 방식으로 I/O을 수행할 때 캐시와 메인 메모리 사이의 데이터 일관성 유지를 위한 명령어 체계가 필요하다는 단점이 있다.

---

Write Allocate

 캐시에서 miss가 발생했을 때 메모리에서 캐시로 값을 가져온 후 Write을 수행하는 방식이다. 결과적으로 캐시로 메모리를 읽어오는 과정 및 캐시의 내용을 다시 메모리에 쓰는 과정에서 메모리를 여러 번 접근해야 하므로 오버헤드가 크다.

Write Around

 캐시에서 miss가 발생했을 때 메모리 상에서 Write을 수행하고 캐시로는 가져오지 않는 방식이다. Write 한 데이터는 이미 작업을 수행했으므로 차후에 다시 사용될 가능성이 없을 수도 있다. 예를 들어 단순히 로그를 작성하는 경우 내용은 작성하지만, 해당 로그를 프로그램 상에서 찾아보는 일은 거의 없다. 이 경우 캐시로 데이터를 가져오더라도 근 미래에 다른 데이터로 대체될 가능성이 높다. 이러한 발상을 기초로 하여 write 과정에 cache miss가 발생했을 때 그냥 메모리 상에서 내용을 수정하고 캐시로 가져오지 않는 정책이 write around다.

---

캐시의 성능

캐시의 성능은 메모리 접근 시간으로 나타낼 수 있으며, 3가지 상황에 대해 나타내면 다음과 같다.

(1) write-through, write-allocate

 hit 하면 캐시 및 메모리의 내용을 즉시 변경하고, miss 하면 캐시로 데이터를 읽어 Write 한 후 다시 메모리에 쓰는 경우를 의미한다. 전체적으로 메모리에 접근하는 횟수가 많기 때문에 이 조합으로 캐시를 구성하는 경우는 별로 없다.

(2) write-through, write-around

hit하면 캐시 및 메모리의 내용을 즉시 변경하고, miss 하면 메모리 상에서 값을 바꾸는 방식이다. write-allocate와는 다르게 miss 했을 때 메모리의 내용을 읽어온 후 다시 작성하는 번거로움이 없으므로 마지막이 2t_m이 아니라 t_m이 된다.

(3) write-back

write-back 방식에서는 dirty ratio에 따라 소모되는 메모리 접근 시간이 다른 것이 특징적이다.

---

Multi cache coherence problem

버스 기반 공유 메모리 구조

SMP(symmetric multiprocess processor)은 동일한 성능의 프로세서들이 동일한 I/O 디바이스나 메모리에 연결되어 동일한 시간을 소모하는 특성을 지니는 모델로, 멀티코어 시스템의 대표적인 모델 중 하나이다. 이런 멀티 프로세서 시스템에서는 동일한 작업을 다수의 프로세서에서 병렬적으로 처리하는 경우가 있다. 이때 프로세서들에서 사용되는 데이터 사이의 일관성이 유지되지 않는다면 각 프로세서는 의도되지 않은 값을 이용하여 이상한 연산을 수행하게 될 것이다. 이렇듯 다수의 프로세서 혹은 코어 사이에서 캐시 일관성을 유지하는 것은 중요한 문제이다.

 다수의 코어 사이에서 일관성을 유지하는 데 사용하는 매체는 2가지가 있다.

• Directory
  : 메인 메모리 혹은 캐시 공간에 분산되어 있는 장소로, 특정 캐시에 특정 내용이 있다는 정보를 담고 있다. 따라서 어떤 캐시 내 값이 바뀌면 디렉터리의 내용을 읽고, 해당 값이 있는 다른 프로세서의 캐시에 접근할 수 있다. 멀티 프로세서가 버스가 아닌 PPI 등의 방식으로 연결되어 있는 경우에 유용하다.
• Bus snooping
  : 멀티 프로세서가 버스에 연결되어 있는 경우, 각 캐시가 버스를 관찰하고 있다가 변경사항이 나타나면 이를 자신이 보유한 값에 반영하는 방식이다. 병렬적으로 연결되는 버스의 성질을 이용한다.

다른 캐시에 대한 write 정책 차이에 대해 2가지 방법이 존재한다. 위에 설명했던 write 정책이 캐시와 메모리 사이의 일관성을 중심으로 설명한 것과는 달리, 이 정책은 다른 프로세서에 속한 캐시 사이의 일관성을 유지하기 위한 것임을 명확히 구분하자. 

• write update
  : 하나의 캐시에서 write가 발생했을 때 다른 프로세서에 있는 캐시들에게도 수정 사항을 알리고 데이터를 보내 수정하는 방식으로, 버스의 broadcast 속성을 이용한다. 수시로 데이터를 업데이트하기 때문에 오버헤드 및 버스 트래픽이 크게 나타날 수 있다.
• write invalidate
  : 하나의 캐시에서 write가 발생하면 다른 프로세서의 캐시들에게 해당 내용이 수정되었다는 사실만 통보하고, 필요한 경우에 값을 다시 가져와서 사용하도록 하는 정책. 다른 캐시들은 메시지를 받으면 대상이 되는 값을 무효화한다.

MESI Protocol

 MESI 프로토콜은 컴퓨터 내에서 꽤 사용되는 프로토콜로, 캐시 라인의 상태를 Modified, Exclusive, Shared, Invalid 4가지로 나누어 관리한다. 각 라인의 상태에 대한 설명은 다음과 같다.

• Modified: 현재 캐시 라인이 수정되었으며, 다른 캐시에는 해당 데이터가 없다.
• Exclusive: 현재 캐시 라인은 원본이며, 다른 캐시에 존재하지 않는다.
• Shared: 현재 캐시 라인은 원본이며, 다른 캐시에 존재할 수 있다.
• Invalid: 현재 캐시 라인은 유효하지 않다.

MESI 프로토콜 도입의 장점은 캐시의 상태를 나눔으로써 Modified 및 Exclusive 상태에서의 수정이 어떤 추가적인 동작도 수행하지 않도록 설정한 것이다. Modified와 Exclusive은 둘 다 현재 캐시에만 해당 데이터가 존재한다는 의미로, 자신의 내용을 수정하더라도 다른 캐시에게 해당 사실을 전파할 필요가 없는 장점을 가진다.

각 상태를 표 형태로 나타낸 것

상태 전이도