캐시 일관성

Cache coherence
공유 리소스 역할을 하는 일부 메모리의 여러 캐시를 보여 주는 그림입니다.
일관성이 없는 캐시:캐시마다 단일 주소 위치의 값이 다릅니다.

컴퓨터 아키텍처에서 캐시 일관성은 여러 로컬 캐시에 저장되는 공유 리소스 데이터의 균일성입니다.시스템 내의 클라이언트가 공통 메모리리소스의 캐시를 유지할 경우 일관성이 없는 데이터(특히 멀티프로세서시스템 CPU의 경우)에서 문제가 발생할 수 있습니다.

오른쪽 그림에서는 양쪽 클라이언트에 이전 읽기로부터 특정 메모리 블록의 캐시된 복사본이 있다고 가정합니다.하단의 클라이언트가 메모리 블록을 업데이트/변경하고 상단의 클라이언트에 변경 알림 없이 비활성 메모리 캐시가 남아 있을 수 있다고 가정합니다.캐시 일관성은 여러 캐시에서 데이터 값의 일관성 있는 보기를 유지함으로써 이러한 충돌을 관리하기 위한 것입니다.

일관성 있는 캐시:모든 캐시의 복사본 값은 동일합니다.

개요

각 프로세서에 대해 별도의 캐시 메모리를 가진 공유 메모리 멀티프로세서 시스템에서는 공유 데이터의 복사본을 여러 개 가질 수 있습니다. 하나는 메인 메모리에, 다른 하나는 이를 요구한 각 프로세서의 로컬 캐시에 있습니다.데이터 복사본 중 하나가 변경되면 다른 복사본도 해당 변경사항을 반영해야 합니다.캐시 일관성은 공유 오퍼랜드(데이터) 값의 변경이 적시에 [1]시스템 전체에 전파되도록 하는 분야입니다.

캐시 [2]일관성에 대한 요구사항은 다음과 같습니다.

기입 전파
캐시의 데이터에 대한 변경은 피어 캐시의 다른 복사본(캐시 라인의 복사본)으로 전파되어야 합니다.
트랜잭션의 시리얼화
단일 메모리 위치에 대한 읽기/쓰기는 모든 프로세서에서 동일한 순서로 인식되어야 합니다.

이론적으로 로드/스토어 입도로 일관성을 수행할 수 있습니다.그러나 실제로는 일반적으로 캐시 [3]블록의 세밀한 수준에서 수행됩니다.

정의.

일관성은 단일 주소 [2]위치에 대한 읽기 및 쓰기 동작을 정의합니다.

서로 다른 캐시 메모리에서 동시에 발생하는 데이터의 한 유형을 캐시 일관성 또는 일부 시스템에서는 글로벌 메모리라고 합니다.

멀티프로세서 시스템에서는 여러 프로세서가 메모리 위치 X의 복사본을 캐시한 것으로 간주합니다.캐시의 [4]일관성을 실현하려면 , 다음의 조건이 필요합니다.

  1. 프로세서 P가 같은 프로세서 P에서 X로의 기입에 이은 위치 X에 대해 판독할 때, 다른 프로세서에 의한 기입이 P에 의한 판독 명령과 읽기 명령 사이에 발생하지 않을 경우, X는 항상 P에 의해 기입된 값을 반환해야 한다.
  2. 프로세서 P1이 다른 프로세서 P2~X에 의한 기입에 이은 위치 X에 대한 읽기에서 2개의 액세스 사이에 발생하는 프로세서에 의한 다른 기입은 없고, 읽기와 쓰기가 충분히 분리된 상태에서 X는 항상 P2에 의해 기입된 값을 반환해야 한다.이 조건은 기억의 일관성 있는 뷰의 개념을 정의합니다.쓰기를 공유 메모리 위치에 전파하면 모든 캐시가 메모리에 대한 일관된 보기를 가질 수 있습니다.프로세서 P1이 P2에 의한 기입 후에도 X의 오래된 값을 읽어낸다면 메모리는 일관성이 없다고 할 수 있다.

위의 조건은 캐시 일관성에 필요한 쓰기 전파 기준을 충족합니다.그러나 트랜잭션 일련화 조건을 충족하지 못하기 때문에 충분하지 않습니다.이것을 보다 잘 설명하기 위해서, 다음의 예를 검토해 주세요.

멀티프로세서 시스템은 P1, P2, P3, P4의 4개의 프로세서로 구성되어 있으며, 모두 초기값이 0인 공유 변수 S의 캐시된 복사본을 포함한다.프로세서 P1은 캐시 카피 내의 S 값을 10으로 변경하고, 그 후 프로세서 P2는 자신의 캐시 카피 내의 S 값을 20으로 변경한다.기입 전파만을 보증하는 경우, P3 및 P4는 P1 및 P2에 의한S 의 변경을 확실히 확인할 수 있습니다.단, P3는 P2의 변화를 보고 P1의 변화를 보고 S4에 대한 판독치 10을 반환할 수 있으며, 반대로 P1과 P2의 변경을 순서대로 보고 S에 대한 판독치 20을 반환할 수 있다.CPU P3와 P4는 메모리를 일관되게 표시할 수 있게 되었습니다.

따라서 트랜잭션시리얼라이제이션에 대응하여 캐시 일관성을 실현하기 위해서는 이 섹션에서 설명한 앞의 2가지 조건과 함께 다음 조건을 충족해야 합니다.

  • 같은 장소에의 기입은, 순서를 설정할 필요가 있습니다.즉, 로케이션 X가 임의의 2개의 프로세서로부터 이 순서로2개의 다른 값 A와 B를 수신했을 경우, 프로세서는 로케이션 X를 B로서 읽어낼 수 없고, 그 후 A로서 읽어낼 수 없습니다.로케이션 X는 값 A와 B의 [5]순서로 표시되어야 합니다.

코히런트 시스템의 대체 정의는 순차적 일관성 메모리 모델의 정의를 통해 이루어집니다: "캐시 코히런트 시스템은 각 스레드의 프로그램 순서를 존중하는 전체 순서로 모든 스레드의 로드와 저장을 단일 메모리 위치에 실행하는 것처럼 보여야 합니다."[3]따라서 캐시 코히런트 시스템과 순차적으로 일관된 시스템의 유일한 차이점은 정의가 말하는 주소 위치 수(캐시 코히런트 시스템의 경우 단일 메모리 위치, 순차적으로 일관된 시스템의 경우 모든 메모리 위치)에 있습니다.

또 다른 정의는 "같은 메모리 위치에 대한 모든 쓰기가 순차적으로 수행되는 경우 멀티프로세서는 캐시에 일관성이 있다"[6]입니다.

드물지만 특히 알고리즘에서 일관성은 참조의 인접성을 나타낼 수 있습니다.같은 데이터의 복수의 카피가 다른 캐시에 동시에 존재할 수 있습니다.프로세서가 자신의 카피를 자유롭게 갱신할 수 있는 경우, 메모리의 표시에 일관성이 없어질 수 있습니다.

일관성 메커니즘

주요 기사:캐시 일관성 프로토콜(예)

일관성을 확보하기 위한 가장 일반적인 두 가지 메커니즘은 스누핑과 디렉토리 기반이며 각각 고유한 장점과 단점이 있습니다.모든 트랜잭션은 모든 프로세서가 확인하는 요청/응답이므로 충분한 대역폭을 사용할 수 있는 경우 스누핑 기반 프로토콜은 더 빠른 경향이 있습니다.단점은 스누핑이 확장 가능하지 않다는 것입니다.모든 요구는 시스템 내의 모든 노드에 브로드캐스트되어야 합니다.즉, 시스템이 커질수록 (논리 또는 물리) 버스의 크기와 제공하는 대역폭이 커져야 합니다.한편 디렉토리는 지연 시간이 길어지는 경향이 있지만(3홉 요구/전송/응답) 메시지는 포인트 투 포인트이며 브로드캐스트되지 않기 때문에 대역폭이 훨씬 적게 사용됩니다.이 때문에, 대규모 시스템(64 프로세서 이상)의 상당수는, 이러한 종류의 캐시 일관성을 사용하고 있습니다.

스누핑

주요 기사:버스 스누핑
1983년에 [7]처음 도입된 스누핑은 개별 캐시가 [4]캐시된 메모리 위치에 대한 액세스에 대해 주소 라인을 모니터링하는 프로세스입니다.쓰기 무효 프로토콜 및 쓰기 업데이트 프로토콜은 이 메커니즘을 사용합니다.
스누핑 메커니즘의 경우 스누핑 필터는 여러 엔트리를 유지함으로써 스누핑 트래픽을 줄입니다.각 엔트리는 1개 이상의 노드가 소유할 수 있는 캐시 라인을 나타냅니다.엔트리의 1개를 치환해야 할 경우 스눕 필터는 각 엔트리의 존재 벡터에서 결정되는 캐시 행을 나타내는 엔트리의 치환을 선택합니다.둘 이상의 캐시 라인이 최소 [8]노드에 의해 소유되는 경우 선택을 세분화하기 위해 임시 또는 다른 유형의 알고리즘이 사용됩니다.

디렉토리 베이스

주요 기사:디렉토리 기반 캐시 일관성
디렉토리 기반 시스템에서는 공유되는 데이터는 캐시 간의 일관성을 유지하는 공통 디렉토리에 배치됩니다.디렉토리는 프라이머리 메모리에서 캐시로 엔트리를 로드하기 위한 권한을 프로세서가 요구하는 필터 역할을 합니다.엔트리가 변경되면 디렉토리는 해당 엔트리의 다른 캐시를 업데이트 또는 비활성화합니다.

분산형 공유 메모리 시스템은 느슨하게 결합된 [9]시스템에서 메모리 블록 간의 일관성을 유지하기 위해 이러한 메커니즘을 모방합니다.

일관성 프로토콜

일관성 프로토콜은 멀티프로세서 시스템에서 캐시 일관성을 적용합니다.그 목적은 두 클라이언트가 동일한 공유 데이터에 대해 서로 다른 값을 볼 수 없도록 하는 것입니다.

프로토콜은 일관성을 위한 기본 요건을 구현해야 한다.대상 시스템 또는 애플리케이션에 맞게 맞춤 제작할 수 있습니다.

프로토콜은 스누피 또는 디렉토리 기반으로 분류될 수도 있습니다.일반적으로 초기 시스템에서는 디렉토리가 공유되는 데이터와 공유자를 추적하는 디렉토리 기반 프로토콜을 사용했습니다.스누피 프로토콜에서는 트랜잭션 요청(읽기, 쓰기 또는 업그레이드)이 모든 프로세서로 전송됩니다.모든 프로세서가 요청을 스누핑하고 적절하게 응답합니다.

스누피 프로토콜의 쓰기 전파는 다음 방법 중 하나로 구현할 수 있습니다.

쓰기 무효화
캐시에 카피가 있는 장소에 기입 조작이 확인되면, 캐시 컨트롤러는 스누핑 메모리 로케이션의 독자적인 카피를 무효화해, 다음의 [4]액세스시에 새로운 값의 메인 메모리에서 읽기를 강제합니다.
기입 갱신
캐시에 복사가 있는 위치에 대한 쓰기 작업이 관찰되면 캐시 컨트롤러는 스누핑된 메모리 위치의 자체 복사본을 새 데이터로 업데이트합니다.

프로토콜 설계에 공유 데이터의 복사본이 변경될 때마다 변경 내용을 반영하기 위해 다른 모든 복사본을 "업데이트"해야 한다고 명시되어 있다면, 이는 쓰기 업데이트 프로토콜입니다.설계에 따라 프로세서에 의해 캐시된 복사본에 쓰려면 다른 프로세서가 캐시된 복사본을 폐기하거나 비활성화해야 한다고 명시되어 있다면 이는 쓰기 무효 프로토콜입니다.

그러나 확장성은 브로드캐스트 프로토콜의 단점 중 하나입니다.

MSI, MESI(일명 일리노이), MOSI, MOESHI, MERSI, MESIF, write-once, Synapse, Berkeley, Firefly [1]및 Dragon 프로토콜 등 일관성을 유지하기 위한 다양한 모델과 프로토콜이 고안되었습니다.2011년 ARM Ltd는 SoC의 일관성 처리를 위한 AMBA 4 ACE를[10] 제안했습니다.ARM Ltd의 AMBA CHI(Consistent Hub Interface) 사양은[11] AMBA5 사양 그룹에 속하며, 완전히 일관된 프로세서의 연결을 위한 인터페이스를 정의합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b E. Thomadakis, Michael (2011). The Architecture of the Nehalem Processor and Nehalem-EP SMP Platforms (PDF). Texas A&M University. p. 30. Archived from the original (PDF) on 2014-08-11.
  2. ^ a b Yan, Solihin. Fundamentals of parallel multicore architecture. OCLC 884540034.
  3. ^ a b Sorin, Daniel J.; Hill, Mark D.; Wood, David Allen (2011-01-01). A primer on memory consistency and cache coherence. Morgan & Claypool Publishers. OCLC 726930429.
  4. ^ a b c Patterson and Hennessy. Computer Organization and Design - 4th Edition. ISBN 978-0-12-374493-7.
  5. ^ 마헤시 주 뉴파네(2004년 4월 16일).캐시 일관성(PDF).2010년 6월 20일 원본(PDF)에서 아카이브 완료.
  6. ^ Steinke, Robert C.; Nutt, Gary J. (2004-09-01). "A Unified Theory of Shared Memory Consistency". J. ACM. 51 (5): 800–849. arXiv:cs/0208027. doi:10.1145/1017460.1017464. ISSN 0004-5411. S2CID 3206071.
  7. ^ "Ravishankar, Chinya; Goodman, James (February 28, 1983). "Cache Implementation for Multiple Microprocessors"" (PDF). Proceedings of IEEE COMPCON: 346–350.
  8. ^ Rasmus Ulfsnes(2013년 6월)."스눕 기반 캐시 일관성 프로토콜을 위한 스눕 필터 설계" 웨이백 머신(PDF)에 2014-02-01 아카이브됨. diva-portal.org노르웨이 과학기술 대학2014-01-20 취득.
  9. ^ https://people.eecs.berkeley.edu/~pattrsn/252F96/Lecture18.pdf[베어 URL PDF]
  10. ^ Kriouile (16 September 2013). Formal Analysis of the ACE Specification for Cache Coherent Systems-on-Chip. In Formal Methods for Industrial Critical Systems. Springer Berlin Heidelberg. ISBN 978-3-642-41010-9.
  11. ^ Ltd, Arm. "AMBA AMBA 5". Arm Developer. Retrieved 2021-04-27.

추가 정보