드래곤 프로토콜

드래곤 프로토콜(영어: Dragon protocol)^[1]은 멀티프로세서 시스템에서 사용되는 업데이트 기반 캐시 일관성 프로토콜이다. 쓰기 전파는 여러 프로세서에 걸쳐 모든 캐시된 값을 직접 업데이트함으로써 수행된다. 드래곤 프로토콜과 같은 업데이트 기반 프로토콜은 캐시 블록에 대한 쓰기 이후에 다른 프로세서에 의한 여러 읽기가 뒤따를 때 효율적으로 작동하는데, 이는 업데이트된 캐시 블록이 모든 프로세서와 관련된 캐시에서 즉시 사용 가능하기 때문이다.

상태

각 캐시 블록은 다음 네 가지 상태 중 하나에 있다: 독점-청결, 공유-청결, 공유-수정, 수정.

독점-청결 (Exclusive-clean, E): 캐시 블록이 현재 프로세서에 의해 처음 가져와졌으며 이후 다른 어떤 프로세서에 의해서도 접근되지 않았음을 의미한다.
공유-청결 (Shared clean, Sc): 캐시 블록이 여러 프로세서의 캐시에 확실히 존재하며, 현재 프로세서가 해당 블록에 마지막으로 쓴 프로세서가 아님을 의미한다. 프로토콜에 의해 E와 Sc 상태는 별도로 유지되어 공유되지 않는 캐시 블록에 대한 읽기-쓰기 작업이 버스 트랜잭션을 유발하여 실행 속도를 늦추는 것을 방지한다. 이는 단일 스레드 프로그램에서 흔히 발생하는 상황이다.
공유-수정 (Shared modified, Sm): 블록이 여러 프로세서의 캐시에 존재하며, 현재 프로세서가 해당 블록을 마지막으로 수정한 프로세서임을 의미한다. 따라서 현재 프로세서는 해당 블록의 소유자라고 불린다. 무효화 프로토콜과 달리, 블록은 메인 메모리에 최신 상태일 필요는 없으며 프로세서에만 최신 상태이면 된다. 캐시 블록이 퇴거될 때 메인 메모리를 업데이트하는 것은 프로세서의 책임이다.
수정 (Modify, M): 한 프로세서만 메모리 블록을 가지고 있으며, 메모리에서 가져온 이후 값을 수정했음을 의미한다.

어떤 캐시 쌍에 대해 주어지는 캐시 블록의 허용되는 상태는 다른 캐시의 상태와 함께 다음과 같다 (위에서 약어된 상태 순서):

	E	Sc	Sm	M
E	N	N	N	N
Sc	N	OK	OK	N
Sm	N	OK	N	N
M	N	N	N	N

트랜잭션

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

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

프로세서 쓰기 (PrWr): 프로세서가 캐시에 있는 특정 캐시 블록에 대한 쓰기를 성공적으로 완료할 때 발생한다. 이는 프로세서가 해당 캐시 블록을 마지막으로 업데이트하게 만든다.

프로세서 읽기 미스 (PrRdMiss): 프로세서가 캐시에서 캐시 블록을 읽는 데 실패하고 메모리나 다른 캐시에서 블록을 가져와야 할 때 발생한다.

프로세서 쓰기 미스 (PrWrMiss): 프로세서가 캐시에서 캐시 블록에 쓰기를 실패하고 메모리나 다른 캐시에서 블록을 가져온 다음 쓰기를 수행해야 할 때 발생한다. 이는 다시 프로세서가 해당 캐시 블록을 마지막으로 업데이트하게 만든다.

버스 읽기 (BusRd): 프로세서가 캐시 블록의 최신 값을 가져오기 위해 버스를 요청할 때 발생하며, 이는 메인 메모리 또는 다른 프로세서의 캐시에서 가져올 수 있다.

플러시 (Flush): 프로세서가 전체 캐시 블록을 버스에 배치할 때 발생한다. 이는 프로세서가 캐시된 블록에 대해 메인 메모리에서 수행한 변경 사항을 반영하기 위한 것이다.

버스 업데이트 (BusUpd): 프로세서가 캐시 블록을 수정하고 다른 프로세서가 해당 캐시 블록을 업데이트해야 할 때 발생한다. 이는 쓰기 업데이트 프로토콜에만 고유한 특징이다. BusUpd는 캐시에 대한 쓰기가 메모리에 대한 쓰기보다 빠르기 때문에 Flush 작업보다 짧은 시간이 소요된다. 또 다른 주목할 점은 캐시가 캐시 블록의 로컬 복사본을 업데이트한 다음 버스 업데이트를 보내기 위해 버스를 요청할 수 없다는 것이다. 만약 이런 일이 발생하면 두 캐시가 독립적으로 로컬 복사본을 업데이트한 다음 버스를 요청할 가능성이 있다. 그런 다음 두 쓰기를 동시에 보게 되며, 이는 순차적 일관성을 따르지 않는다.

또한 공유 라인은 특정 캐시 블록이 여러 캐시에서 사용 가능한지 여부를 나타내는 데 필요하다. 이는 캐시 중 하나가 다른 블록을 업데이트할 필요 없이 블록을 퇴거할 수 있기 때문에 필요하다. 공유 라인은 블록이 하나의 캐시에만 사용 가능하고 버스 업데이트가 따라서 필요하지 않은 경우 메모리 및 버스 트랜잭션을 줄이는 데 도움이 된다. 공유를 감지하기 위한 이러한 전용 라인은 파이어플라이 프로토콜과 같은 쓰기 업데이트 프로토콜 전반에 걸쳐 볼 수 있으며 퓨처버스(IEEE 표준 P896.1)와 같은 버스 표준을 기반으로 구현된다.^[2]

전이

프로세서 시작 전이

블록의 현재 상태와 프로세서에 의해 시작된 트랜잭션에 따라 캐시 블록은 다음 상태 전이 중 하나를 거친다.

프로세서 읽기 미스 (PrRdMiss)가 발생하고 캐시 블록이 공유되지 않으면 상태는 독점으로 전이된다.
프로세서 읽기 미스 (PrRdMiss)가 발생하고 캐시 블록이 공유되면 상태는 공유 청결 상태로 전이된다.
프로세서 쓰기 미스 (PrWrMiss)가 발생하고 캐시 블록이 공유되면 상태는 공유 수정으로 전이되고 프로세서가 소유자가 된다.
프로세서 쓰기 미스 (PrWrMiss)가 발생하고 캐시 블록이 공유되지 않으면 상태는 수정으로 전이된다.
프로세서 읽기 (PrRd) 히트가 발생하면 캐시 블록의 상태는 변경되지 않고 값을 유지한다. 이는 단순히 읽기 명령이며 버스 트랜잭션을 생성하지 않기 때문이다.
캐시 블록이 수정 상태에 있고 프로세서가 블록을 쓰면 (PrWr) 블록이 공유되지 않으므로 전이가 발생하지 않는다.
캐시 블록이 공유 수정 상태에 있고 프로세서가 쓰기를 수행하지만 (PrWr) 공유 라인이 주장되지 않으면 상태는 수정으로 전이된다.
캐시 블록이 쓰기 (PrWr) 발생 시 공유 수정 상태에 있고 공유 라인이 주장되면 다른 캐시 블록을 업데이트하기 위해 버스 업데이트 (BusUpd)가 생성된다.
캐시 블록이 쓰기 (PrWr) 발생 시 공유 청결 상태에 있고 공유 라인이 주장되면 다른 캐시 블록을 업데이트하기 위해 버스 업데이트 (BusUpd)가 생성되고 상태는 공유 수정으로 변경된다.
하지만 캐시 블록이 쓰기 (PrWr) 발생 시 공유 청결 상태에 있지만 공유 라인이 주장되지 않으면 상태는 수정으로 전이되고 버스 트랜잭션은 생성되지 않는다.
블록이 독점 상태에 있고 프로세서가 해당 블록에 쓰면 (PrWr) 수정 상태로 변경된다.

버스 시작 전이

블록의 현재 상태와 버스에 의해 시작된 트랜잭션에 따라 캐시 블록은 다음 상태 전이 중 하나를 거친다.

캐시 블록이 수정 상태에 있고 버스 읽기 (BusRd)가 발행되면 메인 메모리를 업데이트하기 위해 플러시가 발행되고 블록이 여러 캐시에 있으므로 상태는 공유 수정으로 전이된다.
캐시 블록이 공유 수정 상태에 있고 버스 읽기 (BusRd)가 발생하면 메인 메모리를 업데이트하기 위해 플러시가 발행되고 상태는 동일하게 유지된다.
캐시 블록이 공유 수정 상태에 있고 버스 업데이트 (BusUpd) 트랜잭션이 발행되면 상태는 공유 청결으로 전이되고 모든 캐시가 업데이트된다.
캐시 블록이 공유 청결 상태에 있고 버스 읽기 (BusRd) 또는 버스 업데이트 (BusUpd)를 받으면 값은 여전히 공유되므로 상태를 유지한다. 그러나 업데이트의 경우 캐시 블록의 값을 업데이트한다.
캐시 블록이 독점 상태에 있고 버스가 값을 읽으면 (BusRd) 블록이 더 이상 하나의 캐시에만 있지 않으므로 상태는 공유 청결으로 전이된다.

하위 수준 설계 선택

공유-수정 상태 제거

Sm 상태에서 캐시 블록을 가진 프로세서는 캐시 블록이 교체될 때 메인 메모리를 업데이트할 책임이 있다. 하지만 버스 업데이트 트랜잭션이 발생할 때마다 메인 메모리가 업데이트된다면 별도의 Sm 및 Sc 상태가 필요 없으며, 프로토콜은 단일 공유 상태로 충분하다. 그러나 이로 인해 훨씬 더 많은 메모리 트랜잭션이 발생하며^[3] 특히 여러 프로세서가 동일한 캐시 블록에 쓰기를 수행할 때 시스템 속도를 늦출 수 있다.

Sc 블록 교체 브로드캐스팅

이 프로토콜은 Sc 상태의 캐시 블록이 버스 활동 없이 조용히 교체될 수 있도록 허용한다. 다른 캐시에 Sc 블록이 교체되고 있음을 알리기 위해 브로드캐스트가 이루어진다면 다른 공유자가 없다면 공유 라인을 테스트하고 E 상태로 이동할 수 있다. 블록을 E 상태로 두는 장점은 블록이 나중에 쓰여지면 M 상태가 되고 버스 업데이트 트랜잭션을 생성할 필요가 없다는 것이다. 따라서 Sc 블록의 교체를 브로드캐스팅하는 비용으로 버스 업데이트 트랜잭션을 피할 수 있다. 그리고 교체 브로드캐스팅은 시간에 중요하지 않으므로 캐시가 즉시 교체를 처리할 필요가 없다면 단점은 없다. 반면에 캐시가 즉시 업데이트를 처리하지 않으면 순서가 뒤바뀐 업데이트가 발생할 수 있다. 이러한 경우 파이어플라이 프로토콜과 같은 세 가지 상태 업데이트 프로토콜이 성능 이점을 가질 수 있다.

비교

드래곤 vs 쓰기 무효화 프로토콜

쓰기 무효화는 다른 캐시 일관성 프로토콜 집합으로, 캐시 블록이 수정되면 다른 캐시에 있는 동일한 블록의 다른 값은 업데이트되지 않고 무효화된다.^[4] 쓰기 무효화 프로토콜은 동일한 캐시 블록에 대한 후속 쓰기가 많은 경우에 더 효율적인데, 무효화가 한 번 발생하고 다른 프로세서에 의한 추가 버스 트랜잭션이 방지되기 때문이다. 그러나 쓰기 업데이트 프로토콜은 블록에 대한 쓰기 뒤에 동일한 블록에 대한 여러 읽기가 뒤따르는 경우에 더 효율적이다. 다른 캐시된 값에 쓰자마자 업데이트하기 때문에 즉시 데이터에 접근할 수 있다. 이러한 경우 쓰기 무효화 프로토콜은 다른 캐시에서 캐시 블록이 수정될 때마다 나머지 캐시가 일관성 미스에 부딪히고 새 값을 읽기 위해 버스 트랜잭션을 시작해야 하므로 매우 불리하다. 대조적으로 쓰기 업데이트 프로토콜은 때때로 필요 이상으로 블록 값을 최신 상태로 유지하는 경향이 있어 다른 유형의 미스, 즉 충돌 및 용량 미스를 증가시킨다.

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

파이어플라이의 경우, 수정된 블록의 캐시 간 전송은 동시에 메인 메모리로도 쓰여진다. 하지만 메인 메모리에 대한 접근은 캐시에 비해 수십 배 느리므로 별도의 버스 작업으로 쓰기 백을 수행하는 복잡성이 추가된다. 어떠한 경우에도 성능이 저하된다.^[5] 드래곤 프로토콜의 경우 공유된 블록은 메모리로 전혀 쓰여지지 않으므로 이 문제는 완전히 피할 수 있다. 그러나 이는 하나의 상태 (공유-수정) 추가 비용을 수반한다.

각주

↑ Atkinson, Russell R.; McCreight, Edward M. (1987년 1월 1일). 〈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. 65–69쪽. doi:10.1145/36206.36185. ISBN 978-0818608056. S2CID 7019821.
↑ Stenström, Per (1990년 6월 1일). 《A Survey of Cache Coherence Schemes for Multiprocessors》. 《Computer》 23. 12–24쪽. doi:10.1109/2.55497. ISSN 0018-9162.
↑ Culler, David; Singh, Jaswinder Pal; Gupta, Anoop (1999). 《Parallel Computer Architecture, 1st Edition | David Culler, Jaswinder Pal Singh, Anoop Gupta |》. 《store.elsevier.com》 (Gulf Professional). ISBN 9781558603431. 2016년 10월 24일에 확인함.
↑ Solihin, Yan (2015). 《Fundamentals of Parallel Multicore Architecture》. Chapman and Hall/CRC. 205–206, 231–232쪽. ISBN 9781482211184.
↑ Archibald, James; Baer, Jean-Loup (1986년 9월 1일). 《Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model》. 《ACM Trans. Comput. Syst.》 4. 273–298쪽. doi:10.1145/6513.6514. ISSN 0734-2071. S2CID 713808.

같이 보기

[1] Atkinson, Russell R.; McCreight, Edward M. (1987년 1월 1일). 〈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. 65–69쪽. doi:10.1145/36206.36185. ISBN 978-0818608056. S2CID 7019821.

[2] Stenström, Per (1990년 6월 1일). 《A Survey of Cache Coherence Schemes for Multiprocessors》. 《Computer》 23. 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》 (Gulf Professional). ISBN 9781558603431. 2016년 10월 24일에 확인함.

[4] Solihin, Yan (2015). 《Fundamentals of Parallel Multicore Architecture》. Chapman and Hall/CRC. 205–206, 231–232쪽. ISBN 9781482211184.

[5] Archibald, James; Baer, Jean-Loup (1986년 9월 1일). 《Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model》. 《ACM Trans. Comput. Syst.》 4. 273–298쪽. doi:10.1145/6513.6514. ISSN 0734-2071. S2CID 713808.

[1]

[2]

[3]

[4]

[5]