디렉토리 기반의 일관성

Directory-based coherence

디렉토리 베이스의 일관성은 Distributed Shared Memory(DSM; 분산 공유 메모리)의 캐시 일관성의 문제를 처리하기 위한 메커니즘입니다.Non-Uniform Memory Access(NUMA)또 다른 일반적인 방법은 모든 노드 간에 특수 유형의 컴퓨터 버스를 "공유 버스"(일명 "공유 버스")로 사용하는 것입니다.시스템 버스).[1]디렉토리 기반 일관성은 버스 기반 일관성 프로토콜에서 공유 버스 대신 특별한 디렉토리를 사용하여 서비스를 제공합니다.이들 설계 모두 대응하는 매체(디렉토리 또는 버스)를 서로 다른 노드 간의 통신을 용이하게 하고 모든 통신 노드에서 일관성 프로토콜이 올바르게 동작하고 있음을 보증하는 도구로 사용합니다.디렉토리 베이스의 캐시 일관성에서는, 이 디렉토리를 사용해 모든 캐시 블록의 상태를 추적합니다.각 블록의 상태에는, 그 블록이 「상태」인 캐시 일관성, 그 시점에서 그 블록을 공유하고 있는 노드가 포함됩니다.이것에 의해, 모든 신호를 모든 노드에 브로드캐스트 할 필요가 없어집니다.이 단일 블록에 관심이 있는 노드에 전송합니다.

다음은 디렉토리 기반 캐시 일관성 프로토콜의 몇 가지 장점과 단점입니다.

  • 확장성:이것은 디렉토리 베이스의 설계로 가는 가장 큰 동기 중 하나입니다.즉, scalability란 특정 시스템이 증가하는 작업량을 처리하는 데 얼마나 뛰어난지를 의미합니다.이 기준의 경우 모든 노드가 동시에 사용하는 공유 버스를 가질 때 발생하는 제한으로 인해 버스 기반 시스템이 제대로 작동하지 않습니다.비교적 적은 수의 노드에서는 버스 시스템이 잘 작동합니다.다만, 노드의 수가 증가하고 있는 동안은, 이 점에 관해서 몇개의 문제가 발생할 가능성이 있습니다.특히 한 번에 1개의 노드만 버스를 사용할 수 있기 때문에 시스템 전체의 퍼포먼스가 크게 저하됩니다.한편, 디렉토리 베이스의 시스템을 사용하면, 시스템의 scalability를 제약하는 이러한 보틀 넥은 없어집니다.
  • 심플성:이것이 버스 시스템이 우월한 점 중 하나입니다.버스 구조 자체는 시스템을 통과하는 모든 트래픽의 주관자 역할을 할 수 있기 때문에 통과하는 모든 신호의 원자성을 확보할 수 있습니다.따라서 디렉토리 기반 시스템의 경우와 같이 원자성을 확보하고 신호 간의 순서를 정하는 데 더 많은 노력을 기울일 필요가 없으며, 이는 일관성 등의 문제를 다룰 때 이후의 시스템 설계에서 직면하게 되는 몇 가지 오버헤드로 이어집니다.

위의 논의에 따르면, 버스 기반 시스템을 사용하는 것이 상대적으로 작은 시스템에 더 매력적으로 보인다는 것이 명백하다.그러나 시스템이 확장되고 노드 수가 증가하면 디렉토리 기반 시스템이 매우 중요합니다.따라서 버스 기반 캐시와 디렉토리 기반 캐시 일관성 [1]설계를 비교할 때 단순성과 확장성 사이에는 일종의 트레이드오프가 있습니다.

역사

디렉토리 기반 캐시 일관성 시스템의 개념은 오래 전에 시작되었습니다.DASH(Directory Architecture for SHARED-Memory)의 아이디어는 C.K.에 의해 처음 제안되었다.1970년대[2] 중반 탕.그러나 캐시 일관성에 적용하는 것은 몇 년 후, 특히 1978년 스탠포드 대학의 연구진이 이러한 설계와 관련된 어려움과 개선점을 시스템에 설명한 논문에서[3] 스탠포드 DASH라고 불리는 이 일관성 시스템의 첫 버전을 제안했을 때 제안되었습니다.이 접근법 외에도 확장 가능한 시스템을 제공하기 위한 여러 시도가 이루어졌습니다.예를 들어 1985년에 소개된 BBN[4] Butterfly와 1987년에 소개된[5] IBM PR3가 확장 가능한 멀티프로세서 시스템의 예입니다.단, 이들 시스템에는 모두 단점이 있습니다.예를 들어 BBN Butterfly에는 캐시가 없습니다.마찬가지로, IBM PR3는 하드웨어 캐시 일관성을 제공하지 않으므로, 특히 [6]고성능 프로세서를 사용할 때 이 두 설계의 성능을 모두 제한합니다.

다른 경쟁업체의 한계로 인해 캐시 기반 노드에서 확장성이 필요한 캐시 일관성 시스템 및 기타 시스템을 설계할 때 DASH 기반 시스템을 쉽게 선택할 수 있었습니다.1985년 워싱턴 대학의 James[7] Archibald와 Jean-Loup Baer는 설계의 하드웨어 사용 측면에서 "글로벌 디렉토리" 접근방식의 보다 경제적이고 확장 가능하며 모듈식 변형을 제안하는 논문을 발표했다[8].

1992년 스탠포드 대학의 Daniel Lenoski는 디렉토리 기반 시스템을 위한 캐시 일관성 프로토콜의 발전을 제안하는 논문을[9] 발표했습니다.1996년 [10]논문에서 그는 디렉토리 기반 캐시 일관성을 사용하는 서버 컴퓨터 제품군인 SGI Origin 2000의 설계를 소개했습니다.그 후의 오리진[11] 3000은 2000년 7월에 도입되었습니다.

프로토콜

스누피 일관성 프로토콜과는 달리, 디렉토리 기반 일관성 접근법에서, 어떤 캐시가 블록의 복사본을 가지고 있는지에 대한 정보는 디렉토리라고 불리는 구조로 유지됩니다.디렉토리 베이스의 스킴에서는, 참가 캐시는 캐시된 카피를 찾기 위해서, 블록의 다른 모든 공유 캐시에 요구를 브로드캐스트 하는 것은 아니고, 어느 블록이 캐시된 카피를 가지는지에 관한 정보를 취득하기 위해서 디렉토리에 문의해, 이러한 특정의 프로세서에만 송신해, 스누피 프로토콜에 비해 트래픽을 삭감합니다.커요.최적화된 애플리케이션에서 대부분의 데이터 공유는 읽기 전용이며, 자주 읽고 쓰는 데이터 공유는 거의 없습니다.디렉토리 어프로치를 사용하면, 그러한 애플리케이션의 브로드캐스트/스누피 어프로치에 비해, 트래픽을 큰폭으로 절약할 수 있습니다.

[12] 다양한 액터 및 메시지를 보여주는 디렉토리 기반 일관성 체계 개요 다이어그램.

데이터 플로우 다이어그램에 나타나듯이 디렉토리 기반의 일관성 프로토콜을 구현하는 분산 공유 메모리 시스템에 관여하는 행위자는 다음과 같습니다.

  • [Requestor Node] : 이 노드는 메모리 블록의 읽기/쓰기를 요구하는 프로세서입니다.
  • [Directory Node] : 이 노드는 시스템 내의 각 캐시 블록 상태 정보를 유지하며 요청자는 해당 요청을 디렉토리 노드로 전송합니다.
  • 소유자 노드:소유자 노드는 캐시 블록의 최신 상태를 소유합니다. 디렉토리가 항상 최신 데이터로 최신 상태는 아닐 수 있습니다.
  • 공유기 노드:캐시 블록의 복사본을 공유하는 하나 이상의 노드.
이미지 1: 디렉토리 기반 프로토콜 상태 전이도

요청자 및 소유자 노드는 MESI 프로토콜과 같은 스누피 일관성 프로토콜과 유사하게 상태 전환을 유지합니다.그러나 노드가 공통 버스를 사용하여 통신하는 버스 기반 구현과 달리 디렉토리 기반 구현은 메시지 전달 모델을 사용하여 캐시 일관성을 유지하기 위해 필요한 정보를 교환합니다.

디렉토리 노드는 시리얼라이징 포인트로서 기능해, 모든 통신은 이 노드를 개입시켜 올바른 상태를 유지합니다.

디렉토리 노드

디렉토리 노드는 모든 프로세서에 대해 캐시 시스템 전체의 캐시 블록 상태를 추적합니다.다음의 3가지 상태로 할 수 있습니다.

  • 캐시되지 않은 (U): 데이터가 캐시된 프로세서가 없고 메모리가 최신입니다.
  • 공유(S): 1개 이상의 프로세서에 데이터가 캐시되어 있으며 메모리가 최신 상태입니다.이 상태에서는 디렉토리 및 공유자는 캐시된 블록의 깨끗한 복사본을 가집니다.
  • 배타적/수정적(EM): 1개의 프로세서(소유자)에 데이터가 캐시되어 메모리가 오래되었습니다.프로세서가 버스 트랜잭션 없이 배타적 상태에서 수정적 상태로 이행할 수 있기 때문에 디렉토리는 프로세서에서 배타적 또는 수정된 상태로 캐시된 블록을 구별할 수 없습니다.

디렉토리 상태 전이 유한 상태 머신(이미지 1)에 대한 설명은 다음 표에 기재되어 있습니다.

초기 상태 버스 요청 대응/액션 새 주
U 버스 또는

버스 RdX

  • 디렉터리에 블록의 업데이트된 복사본이 있으므로 블록을 메모리에서 가져옵니다.
  • 메시지(ReplyD)를 사용하여 메모리 블록을 요청자에게 보냅니다.
  • 공유자: requestor = first shareer가 없는 경우 디렉토리가 EM 상태로 전환됩니다.
 전자파
전자파 BusRd
  • 소유자에게 개입(Int)을 송신
 S
버스 RdX
  • 현재 소유자에게 무효화(Inv)를 송신합니다.
 -
S BusRd
  • 메모리 블록(ReplyD)을 사용하여 요청자에게 응답합니다.
 -
버스 RdX
  • 메모리 블록(ReplyD)을 사용하여 요청자에게 응답합니다.
  • 모든 공유자를 비활성화(Inv)합니다.
 전자파
버스업그레이드
  • 모든 공유자를 비활성화(Inv)합니다.
  • 업그레이드 가능함을 요청자에게 회신합니다.(응답)
 전자파

공유 상태일 때 캐시 상태 외에 디렉토리는 데이터를 가진 프로세서를 추적해야 합니다.이는 캐시 블록이 공유 상태인 개별 프로세서 캐시에 비활성화 및 개입 요청을 보내는 데 필요합니다.일반적인 구현 방식은 다음과 같습니다.

  • 풀 비트 벡터: 디렉토리 노드의 각 프로세서의 비트필드가 유지됩니다.스토리지 오버헤드는 프로세서 수에 따라 확장됩니다.
  • 제한된 포인터:이 접근 방식에서는 제한된 블록 수의 디렉토리 정보가 디렉토리에 유지되어 스토리지 오버헤드를 줄입니다.

위에서 설명한 프로토콜은 기본 구현이며 디렉토리가 캐시와 동기화되지 않을 수 있으며 프로세서 간의 메시지가 중복될 수 있기 때문에 레이스 조건이 발생할 수 있습니다.복수의 상태를 가지는 스케일러블·코히런트·인터페이스와 같이, 보다 복잡한 실장을 이용할 수 있습니다.

DASH 캐시 일관성 프로토콜은[3] 디렉터리 기반 일관성 체계를 사용하는 또 다른 프로토콜입니다.DASH 프로토콜은 클러스터된 접근 방식을 사용합니다. 클러스터 내의 프로세서는 버스 기반 스누핑 방식을 사용하여 일관성을 유지하고 클러스터는 디렉토리 접근 방식으로 연결됩니다.다양한 프로토콜이 캐시 블록을 추적하기 위해 서로 다른 구현을 사용하지만, 디렉토리의 개념은 동일합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Solihin, Yan (2009). Fundamentals of parallel computer architecture. pp. 319–360.
  2. ^ Tang, C.K. "Cache system design in the tightly coupled multiprocessor system". AFIPS '76 Proceedings of the June 7–10, 1976, National Computer Conference and Exposition.
  3. ^ a b "The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor" (PDF). Computer Systems Laboratory.
  4. ^ Schmidt, G.E. "The Butterfly Parallel Processor". In Proc. Of ICS.
  5. ^ "The IBM research parallel processor prototype PR3: Introduction and architicture". In Proceeding of the 1985 International Conference of Parallel Processing.
  6. ^ "Design of Scalable Shared-Memory Multiprocessors: The DASH approach". Computer System Laboratory, Stanford University.
  7. ^ "James Archibald". ece.byu.edu. Retrieved 2016-11-15.
  8. ^ "An economical solution to the cache coherence problem". ISCA '84 Proceedings of the 11th Annual International Symposium on Computer Architecture.
  9. ^ Lenoski, Daniel; Laudon, James; Gharachorloo, Kourosh; Weber, Wolf-Dietrich; Gupta, Anoop; Hennessy, John; Horowitz, Mark; Lam, Monica S. (1992-03-01). "The Stanford Dash Multiprocessor". Computer. 25 (3): 63–79. doi:10.1109/2.121510. ISSN 0018-9162.
  10. ^ Laudon, James; Lenoski, Daniel (1997-01-01). The SGI Origin: A ccNUMA Highly Scalable Server. Proceedings of the 24th Annual International Symposium on Computer Architecture. ISCA '97. New York, NY, USA: ACM. pp. 241–251. doi:10.1145/264107.264206. ISBN 978-0897919012.
  11. ^ Corp., Silicon Graphics International. "Support Home Page". support1-sgi.custhelp.com. Retrieved 2016-11-16.
  12. ^ Solihin, Yan (2009). Fundamentals of Parallel Multicore Architecture. pp. 319–361.