CS/컴퓨터 구조론

컴퓨터 구조론 5장 [기억장치- 교체 알고리즘, 쓰기 정책, 다중 캐시]

devrabbit22 2025. 4. 2. 00:31

교체 알고리즘

  • 캐시 미스가 발생하여 새로운 블록이 주기억장치로부터 캐시로 올라왔을 때 그 블록이 적재될 수 있는 라인들이 이미 다른 블록들로 채워져 있다면, 그 블록들 중 하나가 교체(replace)되어야 한다.
  • 직접 사상에서는 새로운 블록이 적재될 수 있는 라인이 하나뿐이기 때문에 선택의 여지가 없다. 
  • 완전-연관 사상과 세트-연관 사상에서는 적절한 교체 알고리즘이 필요하다.

가장 널리 사용되고 있는 네 가지 알고리즘

최소 최근 사용(LRU)알고리즘

  • 세트 라인에 적재되어 있는 블록들 중에서 최근의 사용 빈도가 가장 낮은 블록을 선택하여 교체하는 방식이다.
  • 가장 효과적인 것으로 알려진 것은 최소 최근 사용(Least Recently Used:LRU) 알고리즘이다.
  • 이 알고리즘은 사용되지 않은 채로 가장 오랫동안 적재되어 있던 블록을 교체하는 것이다.
  • 2-way 세트-연관 방식에서는 각 라인이 USE 비트를 가지고 있도록 함으로써 이 알고리즘을 구현할 수 있다.
  • 어떤 라인이 액세스되면, 그 라인의 USE 비트는 1로 세트된다. 그리고 그 세트 내 다른 라인의 USE 비트는 0으로 리셋된다. 
  • 새로운 블록이 그 세트로 적재된다면, USE 비트가 0인 라인이 교체된다.
  • 더 최근에 사용되었던 데이터들이 앞으로도 다시 사용될 가능성이 높다는 가정이 맞는 경우가 실제로 많기 때문에, LRU 알고리즘은 높은 적중률을 보여준다.

FIFO 알고리즘

  • 캐시에 적재된 지 가장 오래된 블록을 교체하는 방식
  • FIFO(First-In-First-Out) 알고리즘은 캐시에 적재된 지 가장 오래된 블록을 교체하는 것이다. 
  • 다른 알고리즘으로는 최소 사용빈도 LFU(Least Frequently Used)가 있다.
  • 최소 사용 빈도(LFU) 알고리즘
  • 캐시에 적재된 이래 사용된 빈도가 가장 낮은 블록을 교체하는 방식
  • 즉, 캐시에 적재도니 이후 참조되었던 횟수가 가장 적은 블록을 교체하는 것이다.
  • LFU 알고리즘을 구현하려면 각 라인에 카운터(counter)를 설치해야 하기 때문에 하드웨어가 복잡해진다. 
  • 사용 횟수에 근거하지 않는 기법으로는 후보 라인들 중에서 한 라인을 임의(random)로 선택하는 것이다.

쓰기 정책

  • 캐시에 적재되어 있는 데이터가 프로그램 처리 과정에서 다른 내용으로 변경되는 경우가 있다. 
  • 사실상 캐시에 있는 데이터는 주기억장치에 있는 데이터의 복사본(copy)에 해당한다. 
  • 그 데이터가 캐시에서만 변경되고 주기억장치에는 갱신(update)되지 않는다면, 캐시와 주기억장치에 있는 그 데이터들이 서로 다른 내용을 가지게 된다. 그런 상태에서 어떤 I/O장치가 주기억장치로부터 그 데이터를 읽어간다면 잘못된 결과를 초래하게 된다.
  • 따라서 캐시에서 데이터가 변경되면, 그 즉시 주기억장치에 데이터를 쓰는 동작은 캐시에 비하여 시간이 오래 걸리기 때문에, 캐시에서 데이터가 변경될 때마다 주기억장치에도 그 값을 갱신한다면 기억장치 쓰기 시간이 그 만큼 더 길어진다.

그 문제를 해결하는 방법으로는 캐시에서 어떤 데이터가 변경되더라도 주기억장치에는 갱신하지 않는 것이다.

  • 쓰기 동작이 캐시에서만 수행되므로 쓰기 시간이 짧아진다. 그러나 교체 알고리즘에 의하여 그 데이터를 포함하고 있는 라인이 다른 블록으로 교체되어야 한다면, 그 라인의 내용을 주기억장치에 먼저 갱신한 다음에 교체해야 한다. 
  • 이러한 정책이 사용되는 시스템에서는 캐시의 라인을 교체할 때마다 해당 데이터가 캐시에 적재되어 있는 동안에 수정된(modified)적이 있는 지를 반드시 확인해야 한다.
  • 수정된 적이 없다면, 그 데이터가 포함된 라인에 다른 블록을 즉시 적재할 수 있다. 그러나 수정된 적이 있다면, 수정된 데이터가 포함된 라인의 내용을 주기억장치의 해당 블록에 저장한 다음에, 새로운 블록을 적재해야 한다.

유의사항

  • CPU가 어떤 데이터를 캐시에서만 변경했다면, 캐시의 해당 데이터9라인)의 상태를 수정으로 표시해야 한다. 
  • 그 후에 I/O 장치가 주기억장치로부터 그 데이터를 읽으려 한다면, 캐시 제어회로가 그것을 감지하여 수정된 새로운 데이터를 캐시로부터 주기억장치로 갱신한 다음에, I/O 장치가 읽어가도록 해야 한다. 
  • 이 경우 일반적으로 그 데이터가 포함된 라인 전체를 주기억장치로 갱신한다.

 

쓰기 정책(write policy)

캐시에 적재된 데이터를 새로운 값으로 변경할 때 주기억장치에 갱신하는 시기와 방법을 결정하는 방식

캐시에 적재되어 있는 데이터가 수정되었을 때 그 내용을 주기억장치에 갱신하는 시기와 방법을 결정하는 것을 쓰기 정책이라고 한다.

대표적인 두가지 정책

write-through

  • 캐시에 쓰기 동작을 수행할 때 주기억장치에도 동시에 이루어지는 방식이다.
  • 가장 간단한 정책이며, 주기억장치의 내용들은 항상 유효하다(캐시의 내용과 같다)
  • 이 방법의 단점은 쓰기 동작에 걸리는 시간이 길어진다는 것이다.

write-back

  • 쓰기 동작이 캐시까지만 이루어지는 방식
  • write-back이라고 불리는 쓰기 정책에서는 캐시에서 데이터가 수정되어도 주기억장치에는 갱신되지 않는다. 
  • 만약 캐시에서 데이터가 수정되면 그 라인의 M(modified) 비트가 세트된다.
  • 나중에 그 라인이 교체될 때, M비트가 세트된 경우에는 그 라인 전체가 주기억장치에 갱신된 다음에 교체된다.
  • 결과적으로 write-back 정책을 사용하면 기억장치에 대한 쓰기 동작의 횟수가 최소화 된다. 또한 쓰기 동작이 캐시까지만 이루어지므로 쓰기 시간이 짧아진다. 
  • 그러나 읽기 및 쓰기 동작에서 미스가 발생한 경우에 새로운 블록을 적재하려는 라인의 데이터가 수정된 상태일 때는 주기억장치 갱신을 위하여 추가적인 시간이 소요된다.

write-back 정책의 가장 큰 문제점

  • 캐시에서 수정된 내용이 갱신될 때까지는 주기억장치의 해당 블록이 무효 상태에 있게 된다.
  • 캐시 라인의 상태를 확인하고 갱신하는 동작들을 지원하기 위한 캐시 제어 회로가 복잡해지고, 각 라인이 상태 비트를 가지고 있어야 하는 단점도 있다.

예제5-7

주기억장치 액세스 시간이 100ns, 캐시 액세스 시간이 10ns인 시스템이 있다. 전체 기억장치 액세스 요구들 중에서는 70%는 읽기 동작이고, 30%는 쓰기 동작이었으며, 캐시 적중률은 90%였다. 캐시 쓰기 정책이 write-through일 때와 write-back일 때의 평균 기억장치 액세스 시간을 각각 구하라. 단, write-back에서 미스가 발생한 경우에 새로운 블록을 적재하기 위하여 교체할 라인들의 20%는 수정된 상태에 있다고 가정한다.

풀이

  1. Write-througt 정책의 경우
    • 읽기 동작의 평균 시간 = 0.9 x 10ns + 0.1 x 100ns - 19ns
    • 쓰기 동작의 평균 시간 = 100ns(모든 쓰기 동작은 주기억장치를 액세스)
    • 평균 기억장치 액세스 시간 = 0.7 x 19ns + 0.3 x 100ns = 43.3ns
  2. Write-back 정책의 경우 : 읽기 동작과 쓰기 동작에 같은 시간이 걸리므로, 평균 기억장치 액세스 시간 = 0.9 x 10ns + 0.1 x (100ns + 0.2 x 100ns) = 21ns

[참고] 다중프로세서시스템에서의 데이터 불일치 문제

  • 다중프로세서시스템에서의 데이터 불일치 문제(data inconsistency problem) : 주기억장치에 있는 블록의 내용과 캐시 라인에 적재된 블록의 내용이 서로 달라지는 문제
  • 캐시 일관성 프로토콜(cache coherence protocol) 필요
  • ex) MESI 프로토콜 

다중 캐시

  • 캐시가 도입되기 시작한 초기에는 컴퓨터 시스템에 캐시가 한 개만 설치되었다. 그러나 최근에는 캐시들이 계층적 구조로 설치되거나 기능별로 분리된 다수의 캐시들을 사용하는 것이 보편화 되고 있다.

온-칩 캐시(On-Chip Cache)

  • CPU 칩 내부에 포함되어 있는 캐시
  • 캐시는 원래 별도의 SRAM 칩을 사용하여 CPU와 가까운 곳에 위치시켰다.
  • 그러나 칩에 집적할 수 있는 회로의 밀도가 높아짐에 따라 캐시를 CPU 킵 내부에 포함시키는 것이 가능해졌다. 그것을 온-칩 캐시라고 한다.
  • 외부 버스를 통하여 액세스할 수 있는 캐시와 비교해 볼때, 온-칩 캐시는 액세스 시간이 더 짧아져서 전체 시스템의 성능 향상에 도움이 된다. 인출할 명령어나 데이터가 온-칩 캐시에 있다면, 시스템 버스를 이용할 필요 없이 CPU 내부 버스를 통하여 캐시를 더욱 신속하게 액세스 할 수 있다.

계층적 캐시(hierarchical cache)

  • 여러 레벨의 캐시들을 계층적으로 설치한 구조

2-단계 캐시를 가진 시스템

  • 온-칩 캐시를 1차(L1) 캐시로 사용하고, 칩 외부에 더 큰 용량의 2차 (L2) 캐시를 설치하는 방식
  • L2는 L1의 슈퍼-세트(super-set): L2 의 용량이 L1보다 크며, L1 의 모든 내용이 L2에도 존재
  • 먼저 L1을 검사하고, 만약 원하는 정보가 L1에 없다면 L2를 검사하며, L2에도 없는 경우에는 주기억장치를 액세스
  • L1은속도가빠르지만용량이작기때문에,L2 보다적중률은더낮다
  • 2-단계 캐시 시스템의 평균 기억장치 액세스 시간 :
  • Ta = H1 x TL1 + (H2 - H1) x TL2 + (1 - H2) x Tm
  • 만약 H2가 L1에서 미스 된 액세스들에 대한 L2의 적중률이라면,
  • Ta= H1 xTL1 +(1-H1)H2 xTL2 +{1-H1-(1-H1)H2}xTm

분리 캐시(split cache)

  • 명령어와 데이터를 분리하여 별도로 저장하는 캐시 구조
  • 최근에는 온-칩 캐시 를 명령어만 저장하는 명령어 캐시(instruction cache)와 데이터만 저장하는 데이터 캐시(data cache)로 분리시켜 용도를 구분하고 있다.
  • 특히 여러 개의 명령어들을 동시에 실행하는 명령어 병렬 실행 및 명령어 선인출을 강조하는 고성능 프로세서들에서 는 모두 그와 같이 구현되고 있다. -> 대부분의 고속 프로세서들에서 사용한다.
  • 이러한 캐시 조직을 분리 캐시(split cache)라고 하는데, 주요 장점은 명령어 실행 파이프라인에서 명령어 인출 단계와 오퍼랜드 인출 단계 간에 캐시에 대한 충돌 현상을 제거할 수 있다는 점이다.

PowerPc 620 프로세서의 내부 조직

  • 분리 캐시 조직을 가진 프로세서의 예로서, Power PC 모델 620의 내부 조직이다.
  • 620은 분리된 명령어 캐시와 데이터를 가지고 있으며, 각 캐시의 용량은 32KByte이다.
  • 이들은 모두 8-way 세트-연관 사상 방식을 이용한다.
  • 캐시 내의 각 세트는 8개의 라인들로 구성되어 있다.
  • 이 프로세서는 명령어 실행을 위한 유니트들로서 병렬로 실행되는 세 개의 정수 ALU들과 정수 레지스터들, 그리고 부동소수점 레지스터들과 ALU등을 포함하고 있다.
  • 데이터 캐시는 정수 및 부동소수점 연산을 위한 데이터들을 Load/Store 유니트를 경유하여 적재 혹은 저장한다.
  • 명령어 캐시는 명령어 유니트(instruction unit)로 명령어를 동시에 두 개씩 공급한다.

계층적 분리 캐시의 사례 : 인텔 이타늄(Itanium) 프로세서

인텔 이타늄 프로세서의 캐시 조직[INT01]

  • 3-레벨 캐시 구조를 가지고 있다. 첫 번째 레벨의 캐시는 명령어 캐시(L1I)와 데이터 캐시(L1D)로 분리되어 있으며, 4-way 세트-연관 사상 방식을 이용하고 있다.
  • 캐시 용량은 각각 16KByte씩이다. 명령어 캐시는 쓰기 정책이 필요하지 않으며, 데이터 캐시는 write-through 쓰기 정책을 사용한다.
  • 두 번째 레벨 캐시인 L2는 명령어와 데이터를 모두 저장하는 96KByte 크기의 통합 캐시(unified cache)로서, 6-way 세트-연관 조직을 가진다.
  • L2는 write-back 쓰기 정책을 이용한다. 그리고 L1과 L2캐시는 모두 라인 크기가 32바이트이다.
  • 용량이 가장 큰 세 번째 레벨의 L3캐시는 4-way 세트-연관 사상 조직을 가지며, 라인 크기는 64바이트이다. L1캐시들과 L2캐시는 칩 내부에 포함되어있는 반면, L3는 칩 외부에 위치하지만 프로세서 카트리지 내에 프로세서 칩과 함께 패키징 된다.

멀티-코어 프로세서의 캐시 구조

ex) 인텔 i7-990X 쿼드-코어 프로세서의 3-레벨 캐시 구조

인텔 i7-990X 쿼드 코어 프로세서의 캐시 구조

Reference

컴퓨터 구조론 개정 5판

https://yz-zone.tistory.com/88

 

[ 컴퓨터구조 ] 5.5.3 캐시 기억장치 (계속)

큰 용량의 세트-연관 사상 캐시 조직의 예 ▣ 큰 용량의 세트-연관 사상 캐시 조직의 예 ▪ 주기억장치의 용량은 16M (224)바이트이다. 따라서 주기억장치의 주소는 24비트이고, 바이트 단위로 주소

yz-zone.tistory.com