캐시 배치 정책

Cache placement policies
캐시 교체 정책과 혼동하지 마십시오.

CPU 캐시는 프로세서가 최근에 사용한 데이터를 저장하는 메모리다.메모리 블록은 반드시 캐시에 랜덤하게 배치될 수 없으며 캐시 배치 정책에 의해 단일 캐시 라인 또는 캐시 라인[1] 집합으로 제한될 수 있다.[2][3]즉, 캐시 배치 정책은 특정 메모리 블록이 캐시에 들어갈 때 배치할 수 있는 위치를 결정한다.

캐시에 메모리 블록을 배치하기 위해 사용할 수 있는 세 가지 다른 정책이 있다: 직접 매핑, 완전 연결 및 세트 연결.원래 캐시 조직의 이 공간은 "합치 매핑"[4]이라는 용어를 사용하여 설명되었다.

직접 매핑된 캐시

직접 매핑된 캐시 구조에서 캐시는 세트당 하나의 캐시 라인으로 여러 세트로[1] 구성된다.메모리 블록의 주소를 기준으로 하면 캐시 라인 하나만 차지할 수 있다.캐시는 (n*1) 열 매트릭스로 프레임을 설정할 수 있다.[5]

캐시에 블록을 배치하려면 다음과 같이 하십시오.

  • 세트는 메모리 블록 주소에서 파생된 인덱스[1] 비트에 의해 결정된다.
  • 메모리 블록은 식별된 세트에 배치되고 태그는[1] 세트와 관련된 태그 필드에 저장된다.
  • 캐시 라인이 이전에 사용되었으면 새 데이터는 캐시의 메모리 블록을 대체한다.

캐시에서 단어를 검색하려면

  • 세트는 주소의 인덱스 비트로 식별된다.
  • 메모리 블록 주소에서 파생된 태그 비트는 세트와 연관된 태그 비트와 비교된다.태그가 일치하면 캐시 적중이 발생하고 캐시 블록이 프로세서로 반환된다.그렇지 않으면 캐시 누락이 발생하고 메모리 블록이 하위 메모리(메인 메모리, 디스크)에서 가져오게 된다.

이점

  • 이 배치 정책은 모든 캐시 라인을 통한 검색을 피하기 때문에 전력 효율적이다.
  • 배치방침과 교체방침은 간단하다.
  • 한 번에 하나의 태그만 확인하면 되기 때문에 저렴한 하드웨어가 필요하다.

단점

  • 한 세트에 캐시 라인이 하나만 가능하기 때문에 캐시 적중률이 낮다.새 메모리를 동일한 세트에 참조할 때마다 캐시 라인이 교체되어 충돌 누락의 원인이 된다.[6]

예

직접 맵 캐시

4바이트 블록으로 구성된 16킬로바이트의 메인 메모리와 블록 크기가 4바이트인 256바이트의 다이렉트맵 캐시를 생각해 보자.메인 메모리는 16kB이기 때문에 메모리 주소를 고유하게 나타내려면 최소 14비트가 필요하다.

각 캐시 블록은 크기가 4바이트이므로 캐시의 총 세트 수는 256/4로 64세트와 같다.

캐시로 들어오는 주소는 오프셋, 인덱스, 태그의 비트로 나뉜다.

  • 오프셋은 캐시 라인에서 액세스할 바이트를 결정하는 데 사용되는 비트에 해당한다.캐시 라인의 길이가 4바이트이기 때문에 오프셋 비트가 2개 있다.
  • 인덱스는 캐시 집합을 결정하는 데 사용되는 비트에 해당한다.캐시에 64세트가 있고, 2^6 = 64이기 때문에 6개의 인덱스 비트가 있다.
  • 태그는 나머지 비트에 해당한다.이는 캐시 요청 시 주소와 일치하도록 태그 필드에 저장되는 14 – (6+2) = 6 태그 비트가 있음을 의미한다.

다음은 메모리 주소와 해당 주소가 매핑되는 캐시 라인에 대한 설명:

  1. 주소0x0000(태그 -0b00_0000, 인덱스 –0b00_0000, 오프셋 –0b00)는 메모리의 블록 0에 해당하며 캐시의 세트 0에 매핑된다.
  2. 주소0x0004(태그 -0b00_0000, 인덱스 –0b00_0001, 오프셋 –0b00)는 메모리의 블록 1과 캐시의 세트 1에 매핑하는 것에 해당한다.
  3. 주소0x00FF(태그 –0b00_0000, 인덱스 –0b11_1111, 오프셋 –0b11)는 메모리의 블록 63에 해당하고 캐시의 세트 63에 매핑한다.
  4. 주소0x0100(태그 –0b00_0001, 인덱스 –0b00_0000, 오프셋 –0b00)는 메모리의 블록 64에 해당하며 캐시의 세트 0에 매핑된다.

완전 연관 캐시

완전한 연관 캐시에서 캐시는 여러 캐시 라인이 있는 단일 캐시 세트로 구성된다.메모리 블록은 캐시 라인 중 하나를 차지할 수 있다.캐시 조직은 (1*m) 행 매트릭스로 프레임을 설정할 수 있다.[5]

캐시에 블록을 배치하려면 다음과 같이 하십시오.

  • 캐시 라인은 연관된 유효한 비트를[1] 기반으로 선택된다.유효한 비트가 0이면 새 메모리 블록을 캐시 라인에 배치할 수 있으며, 그렇지 않으면 유효한 비트 0이 있는 다른 캐시 라인에 배치해야 한다.
  • 캐시가 완전히 점유되면 블록이 제거되고 메모리 블록이 캐시 라인에 배치된다.
  • 캐시에서 메모리 블록의 퇴거는 교체 정책에 의해 결정된다.[7]

캐시에서 단어를 검색하려면

  • 메모리 주소의 태그 필드는 모든 캐시 라인과 관련된 태그 비트와 비교된다.일치하면 블록이 캐시에 존재하며 캐시 적중이다.일치하지 않으면 캐시 누락이고 낮은 메모리에서 가져와야 한다.
  • 오프셋에 따라 바이트를 선택하고 프로세서로 반환한다.
완전 연관 캐시

이점

  • 완전한 연관 캐시 구조는 어떤 캐시 라인에 메모리 블록을 배치하여 캐시의 완전한 활용을 가능하게 한다.
  • 배치 정책은 더 나은 캐시 적중률을 제공한다.
  • 캐시 미스 발생 시 다양한 대체 알고리즘을 활용할 수 있는 유연성을 제공한다.

단점들

  • 모든 노선을 반복하는 데 시간이 걸리기 때문에 배치 방침이 더디다.
  • 배치 정책은 블록을 찾기 위해 전체 캐시 세트에 반복해야 하기 때문에 전력이 부족하다.
  • 연관 비교 하드웨어의 높은 비용 때문에 모든 방법 중 가장 비용이 많이 든다.

예

4바이트 블록으로 구성된 16킬로바이트의 주 메모리와 256바이트의 완전한 연관 캐시와 4바이트의 블록 크기를 고려한다.메인 메모리는 16kB이기 때문에 메모리 주소를 고유하게 나타내려면 최소 14비트가 필요하다.

각 캐시 블록은 크기가 4바이트이므로 캐시의 총 세트 수는 256/4로 캐시 라인 64개와 같다.

캐시로 들어오는 주소는 오프셋과 태그의 비트로 나뉜다.

  • 오프셋은 캐시 라인에서 액세스할 바이트를 결정하는 데 사용되는 비트에 해당한다.이 예에서는 캐시 라인의 4바이트를 처리하는 데 사용되는 오프셋 비트가 2개 있다.
  • 태그는 나머지 비트에 해당한다.이는 캐시 요청 시 주소와 일치하도록 태그 필드에 저장되는 14 – (2) = 12 태그 비트가 있음을 의미한다.

메모리 블록은 어떤 캐시 라인에 매핑될 수 있기 때문에, 메모리 블록은 교체 정책에 근거하여 캐시 라인 중 하나를 차지할 수 있다.

연결 캐시 설정

집합 연관 캐시는 직접 매핑된 캐시와 완전히 연관되는 캐시 사이의 절충이다.

집합 연관 캐시는 (n*m) 매트릭스로 상상할 수 있다.캐시는 'n' 세트로 나뉘며 각 세트에는 'm' 캐시 라인이 포함되어 있다.메모리 블록은 먼저 세트에 매핑된 다음 세트의 캐시 라인에 배치된다.

직접맵에서 완전 연관성까지의 캐시 범위는 집합 연관성의 연속이다. (직접 매핑된 캐시는 단방향 집합 연관성이고 m 캐시 라인과 완전하게 연관되는 캐시는 m-way 집합 연관성이다.)

오늘날 설계의 많은 프로세서 캐시는 직접 매핑, 양방향 세트 연결 또는 4방향 세트 연결이다.[5]

캐시에 블록을 배치하려면 다음과 같이 하십시오.

  • 세트는 메모리 블록 주소에서 파생된 인덱스 비트에 의해 결정된다.
  • 메모리 블록은 식별된 집합의 사용 가능한 캐시 라인에 배치되고 태그는 라인과 연결된 태그 필드에 저장된다.집합의 모든 캐시 라인이 점유된 경우, 교체 정책을 통해 식별된 블록을 새 데이터로 대체한다.

캐시에서 단어를 찾으려면

  • 세트는 메모리 블록 주소에서 파생된 인덱스 비트에 의해 결정된다.
  • 태그 비트는 선택한 집합에 있는 모든 캐시 라인의 태그와 비교된다.태그가 캐시 라인 중 하나와 일치하면 캐시 적중이고 적절한 라인이 반환된다.태그가 어느 선과도 일치하지 않으면 캐시 누락이며 메모리 계층의 다음 레벨에서 데이터를 요청한다.

이점

  • 배치 정책은 직접 매핑된 캐시와 완전히 연관된 캐시 사이의 절충이다.
  • 캐시 누락이 발생할 경우 대체 알고리즘을 사용할 수 있는 유연성을 제공한다.

단점들

  • 배치 정책은 캐시에 있는 모든 사용 가능한 캐시 라인을 효과적으로 사용하지 않으며 충돌 누락으로 인해 어려움을 겪는다.

예

4바이트 블록으로 구성된 16킬로바이트의 주 메모리와 블록 크기가 4바이트인 256바이트의 2방향 설정 연관 캐시를 생각해 보자.메인 메모리는 16kB이기 때문에 메모리 주소를 고유하게 나타내려면 최소 14비트가 필요하다.

각 캐시 블록은 크기가 4바이트이고 2방향 집합 연관성이 있기 때문에 캐시의 총 집합 수는 256/(4 * 2)로 32 집합과 같다.

집합 연관 캐시

캐시로 들어오는 주소는 오프셋, 인덱스, 태그의 비트로 나뉜다.

  • 오프셋은 캐시 라인에서 액세스할 바이트를 결정하는 데 사용되는 비트에 해당한다.캐시 라인의 길이가 4바이트이기 때문에 오프셋 비트가 2개 있다.
  • 인덱스는 캐시 집합을 결정하는 데 사용되는 비트에 해당한다.캐시에는 32개의 세트가 있고, 2^5 = 32이기 때문에 5개의 인덱스 비트가 있다.
  • 태그는 나머지 비트에 해당한다.이는 캐시 요청 시 주소와 일치하도록 태그 필드에 저장되는 14 – (5+2) = 7비트가 있음을 의미한다.

다음은 메모리 주소와 해당 주소가 매핑되는 캐시 라인에 대한 설명:

  1. 주소0x0000(태그 -0b000_0000, 인덱스 –0b0_0000, 오프셋 –0b00)는 메모리의 블록 0에 해당하며 캐시의 세트 0에 매핑된다.블록은 캐시 교체 정책에 의해 결정되는 세트 0의 캐시 라인을 차지한다.
  2. 주소0x0004(태그 -0b000_0000, 인덱스 –0b0_0001, 오프셋 –0b00)는 메모리의 블록 1과 캐시의 세트 1에 매핑하는 것에 해당한다.블록은 캐시 교체 정책에 의해 결정되는 세트 1의 캐시 라인을 차지한다.
  3. 주소0x00FF(태그 –0b000_0000, 인덱스 –0b1_1111, 오프셋 –0b11)는 메모리의 블록 63에 해당하며 캐시의 세트 31에 매핑된다.블록은 캐시 교체 정책에 의해 결정된 세트 31의 캐시 라인을 점유한다.
  4. 주소0x0100(태그 –0b000_0001, 인덱스 –0b0_0000, 오프셋 –0b00)는 메모리의 블록 64에 해당하며 캐시의 세트 0에 매핑된다.블록은 캐시 교체 정책에 의해 결정되는 세트 0의 캐시 라인을 차지한다.

양방향 기울어진 연관 캐시

위와 같이 way 0에 대한 인덱스가 직접이지만 way 1에 대한 인덱스는 해시 함수로 형성되는 [8]편향된 캐시와 같은 다른 체계들이 제안되었다.좋은 해시함수는 해시함수와 매핑할 때 직접 매핑과 충돌하지 않는 문제를 다루는 속성을 가지고 있기 때문에, 병리학적 접근 패턴으로 인해 예기치 않게 많은 충돌 누락으로 프로그램이 피해를 볼 가능성이 적다.단점은 해시함수 계산으로 인한 추가 대기시간이다.[9]또한, 새로운 라인을 로드하고 이전 라인을 제거해야 할 때가 되면, 새로운 라인이 각 방식에서 다른 인덱스의 데이터와 충돌하기 때문에 가장 최근에 사용된 기존 라인이 무엇인지 판단하기가 어려울 수 있다. 비스케일 캐시에 대한 LRU 추적은 대개 세트 단위로 이루어진다.그럼에도 불구하고, 편향된 연관성 캐시는 기존의 연관성 캐시에 비해 큰 장점을 가지고 있다.[10]

유사 연관 캐시

진정한 집합 연관 캐시는 컨텐츠 주소 지정 메모리 같은 것을 사용하여 가능한 모든 방법을 동시에 테스트한다.사이비 연관 캐시는 각각의 가능한 방법을 한 번에 하나씩 테스트한다.해시-해시 캐시와 열 연관 캐시는 유사 연관 캐시의 예다.

1차 시험에서 히트를 찾아내는 일반적인 경우, 사이비 연관 캐시는 직접 매핑된 캐시만큼 빠르지만, 완전한 연관 캐시의 미스율에 가까운 직접 매핑된 캐시보다 훨씬 낮은 충돌 미스율을 가진다.[9]

참고 항목

참조

  1. ^ a b c d e "The Basics of Cache" (PDF).
  2. ^ "Cache Placement Policies".
  3. ^ "Placement Policies".
  4. ^ Mattson, R.L.; Gecsei, J.; Slutz, D. R.; Traiger, I (1970). "Evaluation Techniques for Storage Hierarchies". IBM Systems Journal. 9 (2): 78–117. doi:10.1147/sj.92.0078.
  5. ^ a b c Solihin, Yan (2015). Fundamentals of Parallel Multi-core Architecture. Taylor & Francis. pp. 136–141. ISBN 978-1482211184.
  6. ^ "Cache Miss Types" (PDF).
  7. ^ "Fully Associative Cache".
  8. ^ André Seznec (1993). "A Case for Two-Way Skewed-Associative Caches". ACM SIGARCH Computer Architecture News. 21 (2): 169–178. doi:10.1145/173682.165152.
  9. ^ a b C. Kozyrakis. "Lecture 3: Advanced Caching Techniques" (PDF). Archived from the original (PDF) on September 7, 2012.
  10. ^ 마이크로아키텍처 "Skeed-associative caches는 기존의 세트 연관 캐시에 비해 ... 큰 이점을 가지고 있다."