MESI 프로토콜

MESI protocol

MESI 프로토콜은 무효화 기반 캐시 일관성 프로토콜이며, 쓰기-백 캐시를 지원하는 가장 일반적인 프로토콜 중 하나이다.일리노이 의전(University of Illinois at Urbana-Champaign[1])으로도 알려져 있다.캐시 백 쓰기는 일반적으로 캐시를 통한 쓰기 작업에서 낭비되는 대역폭을 많이 절약할 수 있다.쓰기 백 캐시에 항상 더러운 상태가 있어 캐시의 데이터가 메인 메모리의 데이터와 다르다는 것을 나타낸다.일리노이 프로토콜은 블록이 다른 캐시에 있는 경우 누락된 데이터를 캐시할 캐시를 요구한다.이 프로토콜은 MSI 프로토콜에 관한 메인 메모리 트랜잭션의 수를 줄인다.이것은 실적의 현저한 향상을 나타낸다.[2]

미국.

약자 MESI의 문자는 캐시 라인에 표시할 수 있는 (2개의 추가 비트를 사용하여 인코딩됨) 4개의 독점적 상태를 나타낸다.

수정(M)
캐시 라인은 현재 캐시에만 존재하며 더럽다 - 메인 메모리의 값에서 수정되었다(M 상태).캐시는 (더 이상 유효하지 않은) 주 메모리 상태의 다른 읽기를 허용하기 전에 미래의 어느 시점에 주 메모리에 데이터를 다시 쓰기 위해 필요하다.쓰기-백은 라인을 공유 상태로 변경한다.
배타적(E)
캐시 라인은 현재 캐시에만 존재하지만 깨끗하며 메인 메모리와 일치한다.읽기 요청에 따라 언제든지 공유 상태로 변경할 수 있다.또는 쓸 때 수정 상태로 변경될 수 있다.
공유(S)
이 캐시 라인이 기계의 다른 캐시에 저장될 수 있고 깨끗하다는 것을 나타냄 - 그것은 메인 메모리와 일치한다.회선은 언제든지 폐기(유효한 상태로 변경)할 수 있다.
유효하지 않음(I
이 캐시 라인이 잘못됨(사용되지 않음)을 나타냄

주어진 캐시 쌍에 대해, 주어진 캐시 라인의 허용 상태는 다음과 같다.

M E S I
M Red XN Red XN Red XN Green tickY
E Red XN Red XN Red XN Green tickY
S Red XN Red XN Green tickY Green tickY
I Green tickY Green tickY Green tickY Green tickY

블록이 M(수정) 또는 E(배타)로 표시되면, 다른 캐시의 블록 복사본은 I(유효하지 않음)로 표시된다.

작전

이미지 1.1 MESI 프로토콜 Red: 버스 개시 트랜잭션의 상태 다이어그램검은색: 프로세서 시작 트랜잭션.[3]

FSM 상태는 두 가지 자극에 기초하여 한 상태에서 다른 상태로 전환된다.첫 번째 자극은 프로세서별 읽기 및 쓰기 요청이다.예를 들어, 프로세서 P1의 캐시에 블록 X가 있으며, 프로세서에서 해당 블록을 읽거나 쓰도록 요청하는 요청이 있다.두 번째 자극은 프로세서를 연결하는 버스를 통해 캐쉬 블록이나 캐시에 업데이트된 데이터가 없는 또 다른 프로세서에서 온다.버스 요청은 모든 버스 거래를 감시하는 [4]스누퍼스의 도움을 받아 모니터링된다.

다음은 프로세서 요청과 버스 측면 요청의 다른 유형이다.

캐시에 대한 프로세서 요청에는 다음 작업이 포함된다.

  1. PrRd: 프로세서가 캐시 블록을 읽도록 요청함.
  2. PrWr: 프로세서가 캐시 블록 쓰기를 요청함

버스 측의 요청은 다음과 같다.

  1. BusRd: 다른 프로세서에서 요청한 캐시 블록에 대한 읽기 요청이 있음을 나타내는 스누프된 요청
  2. BusRdX: 블록이 아직 없는 다른 프로세서가 요청한 캐시 블록에 대한 쓰기 요청이 있음을 나타내는 스누프 요청.
  3. BusUpgr: 다른 프로세서에서 캐시 블록에 대한 쓰기 요청이 있지만 해당 프로세서에 캐시 블록이 이미 자체 캐시에 있음을 나타내는 스누프된 요청.
  4. 플러시: 전체 캐시 블록이 다른 프로세서에 의해 주 메모리에 다시 기록됨을 나타내는 스누프 요청.
  5. 플러시옵션: 다른 프로세서에 캐시 대 캐시 전송을 제공하기 위해 전체 캐시 블록이 버스에 게시됨을 나타내는 스누프 요청.

(이러한 캐시 간 전송은 기본 메모리에서 블록을 가져오는 대기 시간이 캐시 간 전송 시간보다 많으면 읽기 누락 지연 시간을 줄일 수 있으며, 일반적으로 버스 기반 시스템에서 그러하다. 그러나 일관성이 L2 캐시의 수준으로 유지되는 멀티코어 아키텍처에서는 칩 L3 캐시에 저장되며, 다른 L2보다 누락된 블록을 L3 캐시에서 가져오는 것이 더 빠를 수 있다.)

스누핑 작업:스누핑 시스템에서는 버스 모니터의 모든 캐시가 모든 버스 트랜잭션을 스누핑한다.모든 캐시는 저장한 물리적 메모리의 모든 블록의 공유 상태 복사본을 가지고 있다.블록의 상태는 사용되는 프로토콜의 상태 도표에 따라 변경된다. (MESI 상태 도표는 위의 이미지 참조).버스 양쪽에 스누퍼가 있다.

  1. 프로세서/캐시 쪽을 향해 스누퍼하십시오.
  2. 메모리 쪽의 스누핑 기능은 메모리 컨트롤러에 의해 수행된다.

설명:

각 캐시 블록에는 고유한 4 상태 유한 상태 기계(이미지 1.1 참조)가 있다.다른 입력에 대한 상태 전환 및 특정 상태에서의 반응은 표1.1과 표 1.2에 나타나 있다.

표 1.1 다양한 프로세서 작업에 대한 상태 전환 및 응답
초기 상태 작전 반응
유효하지 않음(I Prrd
  • 버스로 버스Rd 발행
  • 다른 캐시가 BusRd를 보고 유효한 복사본이 있는지 확인하고 캐시 전송에 대해 알림
  • (S)Shared로 상태 전환(다른 캐시가 유효한 복사본을 가지고 있는 경우)
  • (E)독점(없을 경우)으로 주 전환(다른 모든 사용자가 보고했는지 확인해야 함)
  • 다른 캐시가 복사본을 가지고 있는 경우, 그 중 하나가 값을 보내고, 그렇지 않으면 기본 메모리에서 가져오기
PrWr
  • 버스에서 BusRdX 신호 발생
  • (M)로 상태 전환요청자 캐시에서 수정됨
  • 다른 캐시가 복사한 경우 값을 전송하고, 그렇지 않으면 기본 메모리에서 가져오기
  • 다른 캐시가 복사본을 가지고 있으면 BusRdX 신호를 보고 복사본을 무효화한다.
  • 캐시 블록에 쓰기하면 값이 수정된다.
배타적(E) Prrd
  • 버스 트랜잭션이 생성되지 않음
  • 주(州)는 그대로다.
  • 블록 읽기 캐시 적중
PrWr
  • 버스 트랜잭션이 생성되지 않음
  • 배타적에서 (M)으로 상태 전환수정
  • 블록에 쓰기가 캐시 적중
공유(S) Prrd
  • 버스 트랜잭션이 생성되지 않음
  • 주(州)는 그대로다.
  • Read to the block은 캐시 히트다.
PrWr
  • 버스에서 BusUpgr 신호 발생
  • (M)로 상태 전환 수정됨.
  • 다른 캐시들은 BusUpgr을 보고 블록의 복사본을 (I)잘못된 것으로 표시한다.
수정(M) Prrd
  • 버스 트랜잭션이 생성되지 않음
  • 주(州)는 그대로다.
  • 블록에 대한 읽기 캐시 적중
PrWr
  • 버스 트랜잭션이 생성되지 않음
  • 주(州)는 그대로다.
  • 블록에 대한 쓰기가 캐시 히트다.
표 1.2 다양한 버스 운행에 대한 상태 전환 및 대응
초기 상태 작전 반응
유효하지 않음(I 버스Rd
  • 주(州) 변경 금지.신호가 무시됨.
BusRdX/BusUpgr
  • 주(州) 변경 금지.신호가 무시됨
배타적(E) 버스Rd
  • 공유로 전환(다른 캐시에서 읽기가 발생함을 의미하므로)
  • 버스에 블록 내용과 함께 FlashOpt를 넣으십시오.
버스RdX
  • 유효하지 않음으로 전환.
  • 지금 유효하지 않은 블록의 데이터와 함께 버스에 FlushOpt를 넣으십시오.
공유(S) 버스Rd
  • 상태 변경 없음(다른 캐시가 이 블록에서 읽기를 수행하므로 공유됨).
  • 버스에 블록의 내용과 함께 FlashOpt를 넣을 수 있음(설계 선택, Shared 상태로 캐시가 이 작업을 수행하는 경우).
버스업그레이
  • 잘못된 상태로 전환(BusUpgr을 보낸 캐시가 수정됨)
  • 버스에 블록의 내용과 함께 FlashOpt를 넣을 수 있음(설계 선택, Shared 상태의 캐시가 이 작업을 수행하는 경우)
수정(M) 버스Rd
  • (S)Shared로 전환.
  • 데이터와 함께 버스에 FlashOpt를 넣으십시오.BusRd 및 Memory Controller의 발신인이 수신하여, Main Memory에 기록.
버스RdX
  • 유효하지 않은 (I)valid로 전환.
  • 데이터와 함께 버스에 FlashOpt를 넣으십시오.BusRdx 및 Memory Controller의 송신자가 수신하며, Main Memory에 기록한다.

캐시 라인이 수정 또는 배타적 상태일 경우에만 자유롭게 쓰기를 수행할 수 있다.공유 상태인 경우 다른 캐시된 복사본은 먼저 무효화되어야 한다.이는 일반적으로 소유권 요청(RFO)으로 알려진 브로드캐스트 작업에 의해 이루어진다.

수정 상태에서 라인을 포함하는 캐시는 해당 메인 메모리 위치의 모든 시도된 읽기(시스템에 있는 다른 모든 캐시로부터)를 스누핑(절제)하고 해당 캐시가 보유한 데이터를 삽입해야 한다.이 작업은 읽기를 강제로 꺼지게 한 다음(즉, 나중에 다시 시도) 데이터를 주 메모리에 쓰고 캐시 라인을 공유 상태로 변경하여 수행할 수 있다.또한 수정 캐시에서 읽기를 수행하는 캐시로 데이터를 전송하는 방법으로도 수행할 수 있다.참고: 읽기 누락에만 스누핑이 필요함(프로토콜은 다른 캐시가 읽기 적중을 수행할 수 있는 경우 수정이 존재하지 않도록 보장함).

공유 상태에서 회선을 보유하는 캐시는 다른 캐시의 무효화 또는 소유권 요청 방송을 청취해야 하며, 해당 회선을 (유효하지 않은 상태로 이동하여) 일치에서 폐기해야 한다.

수정 및 배타적 상태는 항상 정확하다. 즉, 시스템의 실제 캐시 라인 소유 상황과 일치한다.공유 상태는 정확하지 않을 수 있다. 다른 캐시가 공유 라인을 삭제하면 이 캐시가 해당 캐시 라인의 유일한 소유자가 될 수 있지만 배타적 상태로 승격되지 않는다.다른 캐시는 캐시 라인을 폐기할 때 통지를 브로드캐스트하지 않으며, 이 캐시는 공유 복사본의 개수를 유지하지 않고는 이러한 통지를 사용할 수 없다.

그러한 점에서 배타적 상태는 기회주의적 최적화다.CPU가 상태 S에 있는 캐시 라인을 수정하려면 다른 모든 캐시된 복사본을 무효화하기 위해 버스 트랜잭션이 필요하다.상태 E는 버스 거래 없이 캐시 라인을 수정할 수 있다.

MESI 프로토콜 작동 그림[5]

다음 스트림 읽기/쓰기 참조를 가정해 봅시다.모든 참조는 동일한 위치에 있으며 숫자는 참조를 발행하는 프로세서를 가리킨다.

하천은 : R1, W1, R3, W3, R1, R3, R2이다.

처음에는 모든 캐시가 비어 있는 것으로 가정한다.

표 1.3 MESI가 작동하는 방법의 예(예: "R3"는 프로세서 3에 의한 읽기 블록을 의미한다)
국부적 부탁한다 P1 P2 P3 생성됨

버스 요청

데이터 공급자
0 처음에 - - - - -
1 R1 E - - 버스Rd 밈
2 W1 M - - - -
3 R3 S - S 버스Rd P1의 캐시
4 W3 I - M 버스업그레이 -
5 R1 S - S 버스Rd P3의 캐시
6 R3 S - S - -
7 R2 S S S 버스Rd P1/P3의 캐시

참고: 아래에 언급된 스누핑 용어는 대칭 다중 처리 환경에서 캐시 정합성을 유지하기 위한 프로토콜이다.버스에서 요청된 데이터 블록의 복사본이 있으면 버스 모니터의 모든 캐시가 버스를 감시(스눕)한다.

1단계: 캐시가 처음에 비어있기 때문에 메인 메모리는 블록과 함께 P1을 제공하고 배타적 상태가 된다.

2단계: 블록이 이미 캐쉬와 배타적 상태에 있으므로 버스 지침 없이 직접 수정한다.그 블록은 이제 변형된 상태에 있다.

3단계: 이 단계에서 버스Rd가 버스에 게시되고 P1의 스누퍼는 이를 감지한다.그런 다음 데이터를 플러싱하고 상태를 공유로 변경한다.P3의 블록도 다른 캐시에서 데이터를 수신함에 따라 상태를 공유로 변경한다.데이터는 메인 메모리에 다시 기록되기도 한다.

4단계: 버스에 BusUpgr이 게시되고 P1의 스누퍼는 이를 감지하여 다른 캐시에 의해 블록이 수정되므로 무효화한다.그런 다음 P3는 블록 상태를 수정으로 변경한다.

5단계: 현재 상태가 유효하지 않기 때문에 버스에 BusRd를 게시한다.P3의 스누퍼는 이것을 감지할 것이고, 따라서 데이터가 유출될 것이다.P1과 P3의 두 블록의 상태는 이제 공유될 것이다.이것은 메인 메모리 조차도 이전에 수정된 데이터로 업데이트될 때라는 점에 유의하십시오.

6단계: 캐시에 적중 현상이 있고 공유 상태에 있으므로 여기서는 버스 요청이 이루어지지 않는다.

7단계: P2에 캐시 미스가 있고 BusRd가 게시된다.P1과 P3의 스누퍼는 이것과 둘 다 플러시를 시도할 것이다.어느 쪽이 먼저 버스에 접근하든 그 운영을 할 것이다.

소유권에 대한 읽기

소유권을 위한 읽기(RFO)는 읽기 및 무효화 브로드캐스트를 결합한 캐시 일관성 프로토콜의 작업이다.이 작업은 프로세서가 MESI 프로토콜의 공유(S) 또는 유효(I) 상태에 있는 캐시 라인에 쓰려고 시도하여 실행된다.이 수술은 다른 모든 캐시가 그러한 선의 상태를 I로 설정하게 한다.소유권 거래를 위한 읽기 작업은 해당 메모리 주소에 쓰려는 읽기 작업이다.따라서 이번 작전은 배타적이다.캐시에 데이터를 가져오고 이 메모리 라인을 포함하는 다른 모든 프로세서 캐시를 무효화한다.이것은 위의 표에서 "BusRdX"라고 불린다.

메모리 장벽

MESI의 순진하고 간단한 구현에서는 두 가지 특정한 성능 문제가 나타난다.첫째, 유효하지 않은 캐시 라인에 쓸 때 다른 CPU에서 라인이 가져오는 동안 긴 지연이 발생한다. 둘째, 캐시 라인을 유효하지 않은 상태로 이동하는 것은 시간이 많이 걸린다.이러한 지연을 완화하기 위해 CPU는 저장소 버퍼를 구현하고 대기열을 무효화한다.[6]

저장 버퍼

잘못된 캐시 라인에 쓸 때 저장소 버퍼가 사용된다.쓰기는 어차피 진행될 것이기 때문에 CPU는 읽기-유효하지 않은 메시지(해당 캐시 라인과 해당 메모리 주소를 저장하는 다른 모든 CPU의 캐시 라인이 무효화됨)를 발행한 다음, 쓰기 작업을 저장 버퍼에 밀어넣어 캐시 라인이 마침내 캐시에 도착할 때 실행된다.

저장 버퍼의 존재에 대한 직접적인 결과는 CPU가 쓰기를 커밋할 때, 그 쓰기가 캐시에 즉시 쓰이지 않는다는 것이다.따라서 CPU가 캐시 라인을 읽어야 할 때마다 동일한 라인이 이전에 동일한 CPU에 의해 작성되었지만 아직 캐시에 작성되지 않았을 가능성이 있기 때문에(앞의 쓰기가 여전히 스토어 버퍼에서 대기하고 있기 때문에, CPU는 동일한 라인의 존재를 위해 먼저 자체 스토어 버퍼를 스캔해야 한다.CPU는 해당 저장소 버퍼에서 자체 이전 쓰기를 읽을 수 있지만 다른 CPU는 저장소 버퍼에서 캐시로 플러시되기 전에 해당 쓰기를 볼 수 없음 - CPU는 다른 CPU의 저장소 버퍼를 검색할 수 없음.

대기열 무효화

무효화 메시지에 관해서 CPU는 무효화 대기열을 구현하는데, 이 대기열은 들어오는 무효화 요청을 즉각적으로 인식하지만 실제로 실행되지는 않는다.대신 무효화 메시지는 무효화 대기열을 입력하기만 하면 가능한 한 빨리 처리된다(그러나 반드시 즉시 처리되는 것은 아님).따라서 무효화 대기열에 수신되었지만 아직 적용되지 않은 무효화가 포함되어 있기 때문에 CPU는 캐시의 캐시 라인이 실제로 유효하지 않다는 사실을 망각할 수 있다.CPU와 무효화 대기열이 물리적으로 캐시의 반대쪽에 있기 때문에, 저장 버퍼와 달리 CPU는 무효화 대기열을 검색할 수 없다는 점에 유의하십시오.

그 결과 기억장벽이 요구된다.저장소 장벽은 저장소 버퍼를 플러시하여 모든 쓰기가 CPU의 캐시에 적용되었는지 확인한다.읽기 장벽은 무효화 대기열을 플러시하므로 다른 CPU에 의한 모든 쓰기가 플러싱 CPU에 표시되도록 한다.게다가, 메모리 관리 장치는 저장 버퍼의 스캔을 하지 않아 유사한 문제를 야기한다.이러한 효과는 단일 스레드 프로세서에서도 볼 수 있다.[7]

MSI 대비 MESI의 장점

두 프로토콜 사이의 가장 현저한 차이는 MESI 프로토콜에 존재하는 추가적인 "독점적" 상태라는 것이다.이 여분의 주는 많은 장점이 있기 때문에 추가되었다.프로세서가 다른 프로세서가 가지고 있지 않은 블록을 읽고 그것에 쓸 필요가 있을 때, MSI의 경우 두 개의 버스 거래가 이루어진다. 먼저, 블록에 쓰기 전에 블록을 읽고 BusRdX 요청을 따르는 BusRd 요청이 발행된다.이 시나리오의 BusRdX 요청은 다른 캐시가 동일한 블록을 가지고 있지 않기 때문에 무용지물이지만, 하나의 캐시가 이것에 대해 알 방법이 없다.따라서, MESI 프로토콜은 배타적 상태를 추가함으로써 이러한 한계를 극복하여 버스 요청을 저장하게 된다.이는 순차 애플리케이션이 실행 중일 때 큰 차이를 만든다.하나의 프로세서만이 그것을 작업할 것이기 때문에, 모든 접속은 독점적일 것이다.MSI는 이 경우 매우 나쁜 성능을 발휘한다.데이터 공유가 최소인 병렬 애플리케이션의 경우에도 MESI가 훨씬 빠르다.배타적 상태 추가는 3개 상태와 4개 상태가 모두 2비트로 인코딩되므로 비용이 들지 않는다.

MESI의 단점

특정 블록의 다양한 캐시에 의해 연속적인 읽기 및 쓰기 작업이 수행되는 경우, 데이터는 매번 버스로 플러시되어야 한다.따라서 주 기억장치는 이것을 모든 플러쉬에서 잡아당겨 깨끗한 상태로 유지될 것이다.그러나 이것은 요구사항이 아니며 MESI의 이행으로 인한 추가 오버헤드일 뿐이다.이 도전은 MOESI 프로토콜에 의해 극복되었다.[8]S(공유 상태)의 경우 복수의 스누퍼가 동일한 데이터로 FlashOpt로 응답할 수 있다(위의 예 참조).이러한 이중화를 제거하기 위한 MESIF 주소의 F 상태.

참고 항목

참조

  1. ^ Papamarcos, M. S.; Patel, J. H. (1984). "A low-overhead coherence solution for multiprocessors with private cache memories" (PDF). Proceedings of the 11th annual international symposium on Computer architecture - ISCA '84. p. 348. doi:10.1145/800015.808204. ISBN 0818605383. Retrieved March 19, 2013.
  2. ^ Gómez-Luna, J.; Herruzo, E.; Benavides, J.I. "MESI Cache Coherence Simulator for Teaching Purposes". Clei Electronic Journal. 12 (1, PAPER 5, APRIL 2009). CiteSeerX 10.1.1.590.6891.
  3. ^ Culler, David (1997). Parallel Computer Architecture. Morgan Kaufmann Publishers. pp. Figure 5–15 State transition diagram for the Illinois MESI protocol. Pg 286.
  4. ^ Bigelow, Narasiman, Suleman. "An evaluation of Snoopy Based Cache Coherence protocols" (PDF). ECE Department, University of Texas at Austin.{{cite web}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  5. ^ Solihin, Yan (2015-10-09). Fundamentals of Parallel Multicore Architecture. Raleigh, North Carolina: Solihin Publishing and Consulting, LLC. ISBN 978-1-4822-1118-4.
  6. ^ Handy, Jim (1998). The Cache Memory Book. Morgan Kaufmann. ISBN 9780123229809.
  7. ^ Chen, G.; Cohen, E.; Kovalev, M. (2014). "Store Buffer Reduction with MMUs". Verified Software: Theories, Tools and Experiments. Lecture Notes in Computer Science. Vol. 8471. p. 117. doi:10.1007/978-3-319-12154-3_8. ISBN 978-3-319-12153-6.
  8. ^ "Memory System (Memory Coherency and Protocol)" (PDF). AMD64 Technology. September 2006.

외부 링크