캐시 기억장치

컴퓨터 기억장치의 계층적 구조

컴퓨터의 기억장치의 용량, 접근 속도, 가격의 상관관계

• 접근 속도 감소시켜 데이터의 읽기, 쓰기 속도 향상 위서는 고가이지만 고속의 기억장치 필요
• 많은 양의 데이터를 저장하기 위해서 기억장치의 용량 커지는 것 필요 (적정 비용 위해서는 저가 기억장치 필요)
• 저가의 기억장치를 사용하면 기억장치의 접근속도는 그만큼 증가
• 기억장치 계층 구조 이용
• 적절한 상호 조정이 필요

기억장치 계층구조

• 레지스터, 캐쉬 (SRAM), 주기억장치 (DRAM)는 프로그램과 데이터를 CPU 직접 참조함
• 보조기억장치는 실행되기 위해서 프로그램과 데이터가 주기억장치에 옮겨져야 한다.
• CPU 내의 레지스터 : Register
• 캐시 기억장치 (Cache Memory) : Static RAM
• 주기억장치 (Main Memory) : Dynamic RAM
• 보조기억장치 (Secondary Memory) : HDD (Hard Disk Drive), FDD (Floppy Disk Drive), Magnetic Tape

캐시 기억장치의 원리

캐시 기억장치 동작 원리

• 빠른 접근 시간을 제공하는 기억장치

• 수행할 명령어나 오퍼랜드(연산을 실행하는데 필요한 데이터 혹은 주소 값)를 주기억장치로부터 가져와 저장하고 있다가 빠른 속도로 중앙처리장치에 제공

• CPU <= (워드 전송) => 캐시 메모리 <= (블록 전송) => 주기억장치

캐시 기억장치 동작 방법

1. CPU로부터 주소를 전달 한다.

2. cache 기억장치에 명령어가 존재하는지 유뮤를 파악하고

   1. 있다면 획득한 명령어를 CPU로 전송한다. (완료)
   2. 없다면 3번을 수행한다.

3. 명령어를 포함한 주 기억 장치에 접근

4. 주기억 장치로부터 명령어 블록을 전송받기 위한 캐쉬 슬롯을 할당

5. 주기억 장치의 명령어 블록을 캐쉬에 저장하고, CPU에 전송한다. (완료)

캐시 메모리의 계층화

• RAM (Main memory)
• L1 Cache (Built into chip)
• L2 Cache (SRAM memory bank)
• L3 Cache (있을수도 없을 수도 있음)
• Local bus를 통해 이동

참조의 지역성 (locality of reference)

• 중앙처리장치가 수행할 명령어와 필요한 정보를 저장하고 있다가 즉시 제공함으로써 처리가 신속하게 이루어지도록 함

• 동작 : 프로그램 내장형 컴퓨터의 특성인 기억장치 참조의 지역성 (Locality of reference)으로 인해 가능

• 주어진 시간 동안 중앙처리장치의 기억장치 참조는 제한된 영역에서만 이루어지는 현상

• 짧은 시간 동안 중앙처리장치가 접근하는 범위는 지역적으로 제한되는 것을 의미

캐시 기억장치가 있는 시스템

• 중앙처리장치가 기억장치를 참조할 필요가 있을 경우 캐시 기억장치를 먼저 조사

• 적중 (Hit)

  • 캐시 기억장치에 접근하여 그 내용을 찾았을 때

• 실패 (Miss)

  • 캐시 기억장치에 접근하여 그 내용을 찾이 못하였을 때

• 중앙처리 장치가 1000번지 워드를 필요로 하는 경우

  1. 캐시 기억장치를 검사하고 실패 (Miss)
  2. 주기억장치로부터 정보를 획득하여 캐시 기억장치에 전송
  3. 캐시 기억장치는 정보를 다시 중앙처리장치로 전송

• 캐시 기억장치가 있는 시스템에서 중앙처리장치가 1002번지 워드를 필요로 하는 경우

  1. 캐시 기억장치 검사
  2. 적중 (Hit)
  3. 캐시 기억장치는 정보를 다시 중앙처리장치로 전송

• 캐시 기억장치가 있으면 워드를 저장하고 있기에 바로 반환 가능 (빠른 속도로 정보 획득)

적중률 (Hit ratio)

• 캐시 기억장치 성능 측정

  • 적중률 = 적중수 / 전체 메모리 참조 횟수

  • 주기억장치와 캐시 기억장치 사이에서의 평균 기억장치 접근 시간

  • 평균 기억장치 접근시간 : T(average) = 적중률 : H (hit_ratio) * 캐시 기억장치 접근시간 : T (cache) + (1 - H(hit_ratio)) * 주기억장치 접근시간 : T(main)

  • 캐시의 적중률이 높아질수록 평균 기억장치 접근 시간은 캐시 액세스시간에 접근

T(cache) = 50ns, T(main) = 400ns일 때,
적중률을 증가시키면서 기억장치 접근시간 T(average)을 계산해 봅시다.

적중률 70%의 경우 T(average) = 0.7 * 50ns + 0.3 * 400ns = 155ns
적중률 80%의 경우 T(average) = 0.8 * 50ns + 0.2 * 400ns = 120ns
적중률 90%의 경우 T(average) = 0.9 * 50ns + 0.1 * 400ns = 85ns
적중률 95%의 경우 T(average) = 0.95 * 50ns + 0.05 * 400ns = 67.5ns
적중률 99%의 경우 T(average) = 0.99 * 50ns + 0.01 * 400ns = 53.5ns


캐시 기억장치의 적중률이 높아질수록 평균 기억장치 접근시간은 캐시 기억장치 접근시간에
근접하게 되어 컴퓨터의 처리 속도의 성능 향상을 가져옴!

캐시 기억장치의 설계

캐시 기억장치를 설계함에 있어 공통적인 목표

• 캐시 적중 시 캐시 기억장치로부터 데이터를 읽어오는 시간을 짧게 함
• 캐시 실패 시 주기억장치로부터 캐시 기억장치로 데이터를 읽어 오는 시간을 최소화함
• 주기억장치와 캐시 기억장치 사이에 데이터의 일관성을 유지함

캐시 기억장치를 설계할 때 고려 사항

• 캐시 기억장치의 크기 (Size)
• 인출방식 (Fetch algorithm)
• 사상함수 (Mapping function)
• 교체 알고리즘 (Replacement algorithm)
• 쓰기 정채 (Write policy)
• 블록 크기 (Block size)
• 캐시 기억장치의 수 (Number of caches)

캐시 기억장치의 인출 방식

• 요구 인출 (demand fetch) 방식

  • 현재 필요한 정보만 주기억장치로부터 블록 단위로 인출해 오는 방식
  • 매번 주기억장치에서 인출을 수행하므로 경우에 따라 실패율이 높아져서 캐시 기억장치의 효과를 얻지 못할 때도 있음

• 선인출 (prefetch) 방식

  • 현재 필요한 정보 외에도 앞에로 필요할 것으로 예측되는 정보도 미리 인출하는 방식
  • 지역성 (locality)이 높은 경우에 효과가 높지만 그렇지 못한 경우에는 인출 시간이 길어지기 때문에 효율이 떨어짐

사상함수란?

• 주기억장치와 캐시 기억장치 사이에서 정보를 옮기는 것

• 사상함수

  • 주기억장치와 캐시 기억장치 사이에서 정보를 옮기는 것

  • CPU -> 워드요청 -> 캐시 기억장치에 요구한 워드 존재하지 않음 (Miss) -> 주기억장치에서 워드 획득 -> 캐시 기억장치 갱신

  • 사상함수 종류

    • 직접사상 (Direct Mapping)

      • 주기억장치의 블록이 특정 라인에만 적재

      • 캐시의 적중 여부는 그 블록이 적재 될 수 있는 라인만 검사

      • 장점

        • 사상 과정이 간단하고 작은 용량의 RAM을 캐시 기억장치로 사용하기 때문에 비용이 저렴

      • 단점

        • 주기억장치의 블록이 적재 될 수 있는 라인이 하나

          • 프로그램이 동일한 라인에 적재되는 두 블록들을 반복적으로 액세스 하는 경우 캐시 실패율이 매우 높아짐

    • 연관사상 (Associative Mapping)

      • 주기억장치의 블록이 캐시의 어느 라인에든 적재될 수 있어 직접사상에서 발생하는 단접을 보완

      • 적중 검사가 모든 라인에 대해서 이루어져야 하므로 검사 시간이 길어짐

      • 캐시 슬롯의 태그를 병렬로 검사하기 위해서는 매우 복잡하고 비용이 높은 회로가 필요

    • 집합연관사상 (Set-Associative Mapping)

      • 직접사상과 연관사상 방식을 조합한 방식

      • 하나의 주소 영역이 서로 다른 태그를 갖는 여러 개의 집합으로 이루어지는 방식

      • 두 개의 집합을 갖는 집합연관 캐시 기억장치의 구조

교체 알고리즘

캐시 기억장치가 가득 차 있는 상태에서 캐시 기억장치의 일부를 제거(회수)하고,
주기억장치로부터 새로운 데이터를 가져와야 하는 경우 캐시의 내용을 제거하는 방식

• 직접사상방식에서는 주기억장치의 데이터가 캐시 기억장치의 같은 주소에 저장되기 때문에
  교체 알고리즘을 사용할 필요 없음

• 연관사상 및 집합연관사상방식은 교체 알고리즘이 필요함

교체 알고리즘의 종류

• 최소 최근 사용 알고리즘 (LRU, Least Recently Used)

  • 현재까지 알려진 교체 알고리즘 중에서 가장 효과적

  • 캐시 기억장치 내에서 사용되지 않은 채로 가장 오래 있었던 블록을 교체하는 방식

• 최소 사용 빈도 알고리즘 (LFU, Least Frequently Used)

  • 캐시 기억장치에 적재된 후 가장 적게 사용된 블록을 교체하는 방식

• 선입력 선출력 알고리즘 (FIFO, First In First Out)

  • 캐시 기억장치에 적재된 지 가정 오래된 블록을 교체하는 방식

• 랜덤 (Random)

  • 캐시 기억장치에서 임의의 블록을 선택하여 교체하는 방식

FIFO 기법에 의한 주기억장치 상태 변화 과정

LRU 기법에 의한 주기억장치 상태 변화 과정

LFU 기법에 의한 주기억장치 상태 변화 과정