드래곤 프로토콜

Dragon protocol

Dragon[1] Protocol은 멀티프로세서 시스템에서 사용되는 업데이트 기반 캐시 일관성 프로토콜입니다.쓰기 전파는 여러 프로세서에 걸쳐 캐시된 모든 값을 직접 업데이트하여 수행됩니다.Dragon 프로토콜과 같은 업데이트 기반 프로토콜은 업데이트된 캐시 블록을 모든 프로세서와 연결된 캐시에서 쉽게 사용할 수 있기 때문에 캐시 블록에 쓴 후 다른 프로세서가 여러 번 읽을 때 효율적으로 수행됩니다.

미국.

각 캐시 블록은 exclusive-clean, shared-clean, shared-modified 및 modify의 4가지 상태 중 하나에 있습니다.

  • 전용 청소(E):즉, 캐시 블록은 현재 프로세서에 의해 처음 Import되었으며 이후 다른 프로세서에 의해 액세스되지 않았습니다.
  • 공유 클린(Sc): 이것은 캐시 블록이 여러 프로세서의 캐시에 확실히 존재하며 현재 프로세서가 블록을 쓰는 마지막 프로세서가 아님을 의미합니다.상태 E와 Sc는 공유되지 않는 캐시 블록에서의 읽기/쓰기 조작이 버스 트랜잭션을 유도하여 실행 속도를 늦추는 것을 방지하기 위해 프로토콜에 의해 별도로 유지됩니다.이것은 단일 스레드 프로그램에서 흔히 볼 수 있는 현상입니다.
  • Shared modified (Sm): 이는 블록이 여러 프로세서의 캐시에 존재하며 현재 프로세서가 블록을 수정하는 마지막 프로세서임을 의미합니다.따라서 현재의 프로세서는 블록의 오너라고 불립니다.무효화 프로토콜과 달리 블록은 메인 메모리에서 최신일 필요가 없고 프로세서에서만 최신일 필요가 있습니다.캐시 블록이 제거되었을 때 메인 메모리를 업데이트하는 것은 프로세서의 책임입니다.
  • Modify (M): 이는 메모리 블록을 가진 프로세서가 1개뿐이며 메모리로부터 가져온 이후 값을 변경했음을 의미합니다.

특정 캐시 쌍에 대해 특정 캐시 블록과 다른 캐시 상태의 상태를 조합하여 허용되는 상태는 다음과 같습니다(위의 순서로 생략된 상태).

E 스케이 SM M
E Red XN Red XN Red XN Red XN
스케이 Red XN Green tickY Green tickY Red XN
SM Red XN Green tickY Red XN Red XN
M Red XN Red XN Red XN Red XN

트랜잭션

4개의 프로세서 트랜잭션과 2개의 버스 트랜잭션이 있습니다.

프로세서 읽기(PrRd):이 문제는 프로세서가 캐시에 있는 특정 캐시 블록에 대한 읽기를 성공적으로 완료했을 때 발생합니다.

프로세서 쓰기(PrWr):이 문제는 프로세서가 캐시에 있는 특정 캐시 블록에 정상적으로 쓰기를 완료했을 때 발생합니다.이것에 의해, 프로세서가 캐시 블록의 최신 업데이트가 됩니다.

프로세서 읽기 미스(PrRdMiss):이 문제는 프로세서가 캐시에서 캐시 블록을 읽지 못하고 메모리 또는 다른 캐시에서 블록을 가져와야 할 때 발생합니다.

프로세서 쓰기 미스(PrWrMiss):이 문제는 프로세서가 캐시에서 캐시 블록에 쓰지 못하고 메모리 또는 다른 캐시에서 블록을 가져온 다음 써야 할 때 발생합니다.이것에 의해, 프로세서가 캐시 블록의 최신 업데이트가 됩니다.

버스 읽기(BusRd):이 문제는 프로세서가 메인 메모리 또는 다른 프로세서의 캐시에서 캐시 블록의 최신 값을 가져오도록 버스에 요청할 때 발생합니다.

플래시: 이것은 프로세서가 캐시 블록 전체를 버스에 배치했을 때 발생합니다.이는 프로세서가 변경한 내용을 메인 메모리의 캐시된 블록에 반영하기 위한 것입니다.

버스 업데이트(BusUpd):이 문제는 프로세서가 캐시 블록을 수정하고 다른 프로세서가 각각의 캐시 블록에 업데이트를 필요로 할 때 발생합니다.이는 쓰기 업데이트 프로토콜에만 해당됩니다.BusUpd는 메모리에 비해 캐시에 쓰는 속도가 빠르기 때문에 플래시 작업에 비해 시간이 더 짧습니다.또 하나의 주의사항은 캐시가 캐시 블록의 로컬복사를 갱신할 수 없다는 것입니다.그 후 버스에 버스업데이트 송신을 요구할 수 없습니다.이 경우 2개의 캐시가 개별적으로 로컬복사를 갱신하여 버스를 요구할 수 있습니다.그러면 순차적 일관성을 따르지 않는 두 개의 쓰기가 동시에 표시됩니다.

특정 캐시 블록을 여러 캐시에서 사용할 수 있는지 여부를 나타내기 위해 공유 회선이 필요합니다.이것은 캐시 중 하나가 다른 블록을 업데이트하지 않고 블록을 제거할 수 있기 때문에 필요합니다.공유회선은 블록을 1개의 캐시에서만 사용할 수 있으므로 버스 업데이트가 필요하지 않은 경우에 메모리 및 버스 트랜잭션을 줄이는 데 도움이 됩니다.공유를 감지하기 위한 이러한 전용 라인은 Firefly 프로토콜과 같은 쓰기 업데이트 프로토콜 전반에 걸쳐 나타나고 Futurebus(IEEE 표준 P896.1)[2]와 같은 버스 표준에 따라 구현됩니다.

이행

Dragon 프로토콜 - 프로세서 시작 트랜잭션

프로세서에 의한 이행

캐시 블록은 블록의 현재 상태와 프로세서에 의해 개시된 트랜잭션에 기초하여 다음 중 하나의 상태 천이를 거칩니다.

  • 프로세서 읽기 미스(PrRdMiss)가 발생하여 캐시 블록이 공유되지 않으면 상태가 Exclusive로 전환됩니다.
  • 프로세서 읽기 미스(PrRdMiss)가 발생하여 캐시 블록이 공유되면 상태가 Shared Clean 상태로 전환됩니다.
  • 프로세서 쓰기 미스(PrWrMiss)가 발생하여 캐시 블록이 공유되면 상태가 Shared Modified로 전환되고 프로세서가 소유자가 됩니다.
  • 프로세서 쓰기 미스(PrWrMiss)가 발생하여 캐시 블록이 공유되지 않으면 상태가 수정됨으로 전환됩니다.
  • Processor Read(PrRd; 프로세서 읽기) 히트 시 캐시 블록 상태는 변경되지 않고 값이 유지됩니다.이는 읽기 명령일 뿐 버스 트랜잭션을 생성하지 않기 때문입니다.
  • 캐시 블록이 [수정(Modified)]상태이고 프로세서가 블록에 기입(PrWr)할 경우 블록이 공유되지 않기 때문에 이행은 없습니다.
  • 캐시 블록이 [Shared Modified]상태이고 프로세서가 (PrWr)를 쓰지만 공유회선이 아사트되지 않으면 상태는 [Modified]으로 이행합니다.
  • 쓰기(PrWr)가 발생하여 공유회선이 아사트되었을 때 캐시 블록이 Shared Modified 상태이면 버스 갱신(BusUpd)이 생성되어 다른 캐시 블록을 갱신한다.
  • 쓰기(PrWr)가 발생하여 공유회선이 아사트되었을 때 캐시 블록이 Shared Clean 상태일 경우 버스 업데이트(BusUpd)가 생성되어 다른 캐시 블록을 업데이트하고 상태가 Shared Modified로 변경됩니다.
  • 단, 쓰기(PrWr)가 발생했을 때 캐시 블록이 Shared Clean 상태에 있지만 공유 회선이 아사트되지 않은 경우 상태는 Modified로 전환되며 버스 트랜잭션은 생성되지 않습니다.
  • 블록이 Exclusive 상태이고 프로세서가 블록에 쓰기(PrWr)를 하면 Modified 상태로 변경됩니다.
Dragon 프로토콜 - 버스 시작 트랜잭션

버스에 의한 이행

블록의 현재 상태와 버스에 의해 시작된 트랜잭션에 기초하여 캐시 블록은 다음 중 하나의 상태 천이를 거칩니다.

  • 캐시 블록이 Modified 상태이고 Bus Read(BusRd)가 발행되면 플래시가 발행되어 메인메모리가 갱신되고 블록이 여러 캐시에 있기 때문에 상태가 Shared Modified로 이행됩니다.
  • 캐시 블록이 Shared Modified 상태이고 버스 읽기(BusRd)인 경우 플래시가 발행되어 메인 메모리가 갱신되고 상태는 그대로 유지됩니다.
  • 캐시 블록이 Shared Modified 상태이고 Bus Update(BusUpd) 트랜잭션이 발행되면 상태가 Shared Clean으로 전환되고 모든 캐시가 업데이트됩니다.
  • 캐시 블록이 Shared Clean 상태이고 버스 읽기(BusRd) 또는 버스 업데이트(BusUpd)를 수신한 경우 캐시 블록은 값이 여전히 공유되므로 상태를 유지합니다.단, 업데이트의 경우 캐시 블록의 값이 업데이트됩니다.
  • 캐시 블록이 Exclusive 상태이고 버스가 값(BusRd)을 읽을 경우 블록이 더 이상 하나의 캐시에만 상주하지 않으므로 상태가 Shared Clean으로 전환됩니다.

낮은 수준의 설계 선택지

공유 수정 상태 삭제

캐시 블록이 Sm 상태인 프로세서는 캐시 블록이 교체될 때 메모리를 업데이트합니다.그러나 버스 업데이트 트랜잭션이 발생할 때마다 메인 메모리가 업데이트되면 별도의 Sm 및 Sc 상태가 필요하지 않으며 프로토콜은 단일 공유 상태를 제공할 수 있습니다.그러나 이로 인해 메모리 트랜잭션이[3] 훨씬 더 많이 발생하여 특히 여러 프로세서가 같은 캐시 블록에 쓸 경우 시스템 속도가 느려질 수 있습니다.

Sc 블록 교체 방송

이 프로토콜을 사용하면 버스 활동 없이 Sc 상태의 캐시 블록을 자동으로 교체할 수 있습니다.다른 캐시에 Sc 블록이 교환되고 있음을 알리기 위해 브로드캐스트가 이루어졌을 경우 공유회선을 테스트하고 다른 공유자가 없는 경우 상태E로 이행할 수 있습니다.블록이 상태E인 장점은 나중에 블록이 작성되면 M 상태가 되어 버스 업데이트 트랜잭션을 생성할 필요가 없다는 것입니다.따라서 Sc 블록의 대체를 브로드캐스트하는 비용으로 버스 업데이트 거래를 피할 수 있습니다.브로드캐스트 교환은 시간적으로 중요하지 않기 때문에 즉시 교환 처리를 위해 캐시가 필요하지 않은 경우에도 단점은 없습니다.한편, 캐시가 업데이트를 즉시 처리하지 않으면 업데이트가 잘못된 순서로 진행될 수 있습니다.이러한 경우 Firefly 프로토콜과 같은 세 가지 상태 업데이트 프로토콜은 성능 이점을 가질 수 있습니다.

비교

Dragon vs Write 프로토콜 무효화

Write Invalidate는 캐시 일관성 프로토콜의 또 다른 집합으로, 캐시 블록이 수정되면 다른 캐시에서 동일한 블록의 다른 값은 업데이트되지 않고 [4]비활성화됩니다.Write Invalidate 프로토콜은 동일한 캐시 블록에 대한 후속 쓰기가 많은 경우에 더 효율적입니다. 이는 무효화가 한 번 발생하고 다른 프로세서에 의한 추가적인 버스 트랜잭션이 방지되기 때문입니다.그러나 쓰기 업데이트 프로토콜은 블록에 쓰기 후 동일한 블록에 대한 여러 읽기가 이어지는 경우에 더 효율적입니다.데이터를 쓰면 다른 캐시된 값을 업데이트하기 때문에 데이터에 즉시 액세스할 수 있습니다.이런 경우에는.write invalidate protocol은 캐시 블록이 다른 캐시에서 수정될 때마다 나머지 캐시들은 일관성 오류를 만나 새로운 값을 읽기 위해 버스 트랜잭션을 시작하기 때문에 매우 불리하다.이와는 대조적으로 쓰기 업데이트 프로토콜은 때때로 블록의 값을 필요 이상으로 오랫동안 업데이트하는 경향이 있으며, 이로 인해 충돌 및 용량 누락과 같은 다른 유형의 누락이 증가하게 됩니다.

드래곤 vs 파이어플라이 프로토콜

Firefly의 경우 수정된 블록의 캐시 간 전송도 동시에 메인 메모리에 다시 기록됩니다.그러나 메인 메모리에 대한 접근은 캐시에 비해 몇 배나 느리기 때문에 별도의 버스 조작으로 라이트백을 수행해야 하는 복잡성이 가중됩니다.어떤 경우에도 퍼포먼스가 [5]저하됩니다.공유 블록은 메모리에 전혀 기록되지 않으므로 Dragon 프로토콜의 경우 이 문제를 완전히 피할 수 있습니다.단, 여기에는 1개의 추가 스테이트(Shared-modified)의 비용이 듭니다.

레퍼런스

  1. ^ Atkinson, Russell R.; McCreight, Edward M. (1987-01-01). The Dragon Processor. Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS II. Los Alamitos, CA, USA: IEEE Computer Society Press. pp. 65–69. doi:10.1145/36206.36185 (inactive 28 February 2022). ISBN 978-0818608056.{{cite book}}: CS1 유지 : 2022년 2월 현재 DOI 비활성화 (링크)
  2. ^ Stenström, Per (1990-06-01). "A Survey of Cache Coherence Schemes for Multiprocessors". Computer. 23 (6): 12–24. doi:10.1109/2.55497. ISSN 0018-9162.
  3. ^ Culler, David; Singh, Jaswinder Pal; Gupta, Anoop (1999). Parallel Computer Architecture, 1st Edition David Culler, Jaswinder Pal Singh, Anoop Gupta . store.elsevier.com. ISBN 9781558603431. Retrieved 2016-10-24.
  4. ^ Solihin, Yan (2015). Fundamentals of Parallel Multicore Architecture. Chapman and Hall/CRC. pp. 205–206, 231–232. ISBN 9781482211184.
  5. ^ Archibald, James; Baer, Jean-Loup (1986-09-01). "Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model". ACM Trans. Comput. Syst. 4 (4): 273–298. doi:10.1145/6513.6514. ISSN 0734-2071. S2CID 713808.

「 」를 참조해 주세요.