디렉토리 기반 캐시 일관성

Directory-based cache coherence

컴퓨터 엔지니어링에서 디렉토리 기반 캐시 일관성은 캐시 일관성 메커니즘의 한 종류로, 디렉토리는 확장성 때문에 스누피 메서드 대신 캐시를 관리하기 위해 사용됩니다.버스 스누핑 방식은 브로드캐스트 사용으로 인해 확장성이 떨어집니다.이러한 방법을 사용하여 디렉토리 [1]시스템의 성능과 확장성을 모두 공략할 수 있습니다.

풀비트 벡터 포맷

전체 비트 벡터 디렉터리 형식의 다이어그램(E=Darched, S=Shared, M=Darched 및 U=Darched)

풀 비트 벡터 포맷에서는, 메모리내의 가능한 캐시 라인 마다, 비트를 사용해 각각의 프로세서가 그 라인을 [2]캐시에 격납하고 있는지 아닌지를 추적한다.풀 비트 벡터 포맷은 구현이 가장 간단하지만 확장성이 가장 [1]낮은 구조입니다.SGI Origin 2000은 프로세서 [3]수에 따라 풀비트 벡터와 로우비트 벡터의 조합을 사용합니다.

각 디렉토리 엔트리에는 디렉토리 상태를 추적하기 위한 비트와 함께 캐시 라인별로 프로세서당 1비트가 저장되어 있어야 합니다.따라서 필요한 총 크기는 (프로세서 수)×캐시 라인 수이며 스토리지 오버헤드 비율은 (프로세서 수)/(캐시 블록 크기×8)입니다.

디렉토리 오버헤드는 프로세서 수에 따라 선형적으로 확장됩니다.이것은 소수의 프로세서에서는 문제가 없을 수 있지만, 대규모 시스템에 실장되어 있는 경우, 디렉토리의 사이즈가 과도하게 요구됩니다.예를 들어 블록 크기가 32바이트이고 프로세서가 1024개인 경우 스토리지 오버헤드 비율은 1024/(32×8) = 400%[2]가 됩니다.

저속 비트 벡터 형식

저속 비트 벡터 디렉터리 형식 다이어그램

로우 비트 벡터 포맷은 풀 비트벡터 포맷과 유사한 구조를 가지고 있지만 캐시 라인마다 프로세서당 1비트를 추적하는 것이 아니라 여러 프로세서를 노드로 그룹화하여 캐시 라인이 아닌 노드에 저장되는지 여부를 저장합니다.이로 인해 버스 트래픽 절약(노드당 프로세서 수)×(총 라인 수) 비트의 공간을 [3]희생하면서 크기 요구사항이 개선됩니다.따라서 프로세서의 수를 프로세서 그룹의 수로 대체하는 것만으로 오버헤드는 동일합니다.그룹내의 1개의 프로세서가 가지는 캐시 라인에 대해서 버스 요구가 이루어지면, 디렉토리는 그 신호를 격납하는 캐시만이 아니고, 노드내의 모든 프로세서에 브로드캐스트 하기 때문에, 데이터가 [2]캐쉬 되어 있지 않은 노드에의 불필요한 트래픽이 발생합니다.

이 경우 디렉토리 엔트리는 각 캐시 행의 프로세서 그룹에 대해1비트를 사용합니다.전체 비트 벡터 형식과 동일한 예에서 8개의 프로세서에 대한 1비트를 그룹으로 고려할 경우 스토리지 오버헤드는 128/(32×8)=50%가 됩니다.이는 풀비트 벡터 포맷에 비해 대폭 개선된 것입니다.

스파스 디렉토리 형식

캐시는 특정 시간에 주 메모리에 블록의 작은 부분 집합만 저장합니다.따라서 디렉토리의 대부분의 엔트리는 캐시되지 않은 블록에 속합니다.sparse 디렉토리 형식에서는 [2]캐시된 블록만 디렉토리에 저장함으로써 낭비가 줄어듭니다.캐시 크기가 64KB이고 블록 크기가 32바이트이고 기본 메모리 크기가 4MB인 프로세서를 고려합니다.디렉토리가 sparse 디렉토리 형식으로 가질 수 있는 엔트리의 최대수는 2048 입니다.디렉토리에 메모리내의 모든 블록의 엔트리가 있는 경우, 디렉토리내의 엔트리의 수는 131072가 됩니다.따라서 스파스 디렉토리 포맷에 의해 제공되는 스토리지 개선은 매우 중요합니다.

번호 균형 바이너리 트리

이 형식에서는 디렉토리가 분산되어 메모리 블록을 공유하는 캐시 간에 배포됩니다.메모리 블록을 공유하는 다른 캐시는 바이너리 트리 형태로 배열됩니다.메모리 블록에 가장 먼저 액세스하는 캐시는 루트 노드입니다.각 메모리 블록에는 루트 노드 정보(HEAD)와 공유 카운터 필드(SC)가 있습니다.SC 필드에는 블록을 공유하는 캐시 수가 있습니다.각 캐시 엔트리에는 L-CHD 및 R-CHD로 알려진 다음 공유 캐시에 대한 포인터가 있습니다.이 디렉토리의 조건은 바이너리 트리가 번호 균형을 이루어야 한다는 것입니다.즉, 왼쪽 서브트리의 노드 수가 오른쪽 서브트리의 노드 수보다 크거나 같아야 합니다.또한 모든 서브트리는 번호 균형을 [4]이루어야 합니다.

연결된 디렉토리 형식

이 형식에서 메모리는 블록에 액세스한 최신 캐시에 대한 디렉토리 포인터를 보유하고 있으며 각 캐시는 블록에 액세스한 이전 캐시에 대한 포인터를 가지고 있습니다.따라서 프로세서가 메모리 내의 블록에 쓰기 요구를 송신하면 프로세서는 포인터의 체인을 통해 무효화를 송신합니다.이 디렉토리에서는 캐시 블록이 교체될 때 디렉토리를 변경하기 위해 목록을 통과해야 합니다.이것에 의해, 레이텐시가 증가합니다.이러한 이중 링크 목록을 방지하기 위해 현재 캐시된 각 복사본에는 [5]블록에 액세스하는 이전 캐시와 다음 캐시에 대한 포인터가 있습니다.

제한된 포인터 형식

제한된 포인터 형식은 설정된 수의 포인터를 사용하여 데이터를 캐싱하는 프로세서를 추적합니다.새 프로세서가 블록을 캐시할 때 해당 프로세서를 가리키는 풀에서 빈 포인터가 선택됩니다.공유자 수가 자유지시자 수를 초과하는 경우를 처리하는 방법에는 몇 가지가 있다.한 가지 방법은 새 요청자에 대한 포인터를 사용하여 공유자 중 하나를 비활성화하는 것이지만, 블록에 잠금과 같이 많은 수의 판독기가 있는 경우에는 비용이 많이 들 수 있습니다.또 다른 방법은 모든 블록에서 사용할 수 있는 별도의 자유 포인터 풀을 갖는 것입니다.이 방법은 일반적으로 다수의 프로세서가 공유하는 블록 수가 [2]많지 않기 때문에 효과적입니다.

레퍼런스

  1. ^ a b Reihnhart, Steven; Basu, Arkaprava; Beckmann, Bradford; Hill, Mark (2013-07-11). "CMP Directory Coherence: One Granularity Does Not Fit All" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  2. ^ a b c d e Solihin, Yan (2015-10-09). Fundamentals of Parallel Multicore Architecture. Raleigh, North Carolina: Solihin Publishing and Consulting, LLC. pp. 331–335. ISBN 978-1-4822-1118-4.
  3. ^ a b Laudon, James; Lenoski, Daniel (1997-06-01). The SGI Origin: a ccNUMA highly scalable serve. Proceedings of the 24th annual international symposium on Computer architecture.
  4. ^ Seo, Dae-Wha; Cho, Jung Wan (1993-01-01). "Directory-based cache coherence scheme using number-balanced binary tree". Microprocessing and Microprogramming. 37 (1): 37–40. doi:10.1016/0165-6074(93)90011-9.
  5. ^ Chaiken, D.; Fields, C.; Kurihara, K.; Agarwal, A. (1990-06-01). "Directory-based cache coherence in large-scale multiprocessors". Computer. 23 (6): 49–58. CiteSeerX 10.1.1.461.8404. doi:10.1109/2.55500. ISSN 0018-9162.