Large scale shared memory multiprocessors favor a directory-based cache coherence scheme for its scalability. The directory space needed to record the information for sharers has a complexity of Θ($N^2$) when a full-mapped vector is used for an N-node system. Though this overhead can be reduced by limiting the directory size assuming that the sharing degree is small, it will experience significant inefficiency when a data is widely shared. As a reason of the coherence overhead, we notice that most coherence actions in directory-based protocols are initiated by home nodes, and this nature consequently leads to limit the scalability.
In order to lessen the burden of home nodes, we propose a new directory scheme and an efficient broadcast capability for a direct interconnection network. The broadcast capability is based on the fact that all switching technologies allow each router to watch a message passed by, and thus a message can be used to perform a broadcast mission without extra traffic, which can be utilized for the cache coherence problem. Only a slight change on a typical router is needed to implement our scheme. The Splash parallel program suite is used in the simulation study where our scheme is compared with other directory based schemes. Our scheme is proved to generate much less traffic for cache coherence while the space complexity is slightly more scalable (Θ($N^{3/2}log N$)). This scheme is also applicable to any k-ary n-cube networks including a mesh.
Based on the proposed broadcast mechanism, we present two enhanced schemes which aggressively exploit the nature of wide sharing pattern in conjunction with software. One scheme is motivated by the fact that most widely shared data have relatively short write runs, and thus updates to those data are more effective while the invalidate scheme is still effective for other data. For this scheme, it is more important to accurately identify the widely shared data.
As another problem of wide sharing, most read accesses to a widely shared data are generated almost at the same time. This burst of requests to a memory module inevitably results in the increase of contention to network bandwidth and a memory module. Thus it is of much help to reduce the explosive traffic by combining the requests and further supplying a data block to all caches which need to access it. We present another cache coherence scheme that implements such a combining/broadcast mechanism under the write invalidate scheme.
직접 상호 연결망이 갖는 우수한 확장성으로 인해 많은 대규모 공유메모리 다중처리기들이 메쉬, 하이퍼큐브, 토러스 등의 직접 연결망으로 구성되고 있으며 디렉토리 기반 캐쉬 일관성 기법들을 채택하고 있다. 초기에 제안된 전사벡터(full-mapped vector)방식이 디렉토리의 크기면에서 좋지 않은 확장성(N 프로세서 시스템의 경우 Θ($N^2$))을 보이면서, 일정 수의 포인터만으로 구성된 한정된 디렉토리(limited directory) 기법들이 대안으로 제시되었다. 이들의 제안 동기는 "대부분의 병렬 프로그램에서 데이터에 대한 공유도는 매우 작다"는 것이다. 따라서 적은 수의 포인터로도 충분히 데이터 공유를 지원할 수 있다고 주장한다. 그러나 본 연구에서는 상당수의 병렬 프로그램들이 동기화 변수와 일부 데이터에 대해 대단히 높은 공유도 (광공유, wide sharing)를 보일 뿐만아니라, 광공유 데이터가 비록 적게 나타나는 프로그램에서도 그들로 인한 부담이 전체 성능을 크게 좌우할 수 있음을 밝혔다.
위의 관찰 결과를 토대로 광공유 데이터를 효과적으로 지원하는 디렉토리 기법을 제안한다. 이 기법의 특징은 기존의 점대점 방식에 의존하던 기법들이 갖는 막대한 캐쉬 일관성 통신량과 디렉토리 메모리량, 홈노드들에 지나치게 편중된 일관성 방식 등을 개선하기 위해, 방송 디렉토리(broadcast directory)라는 새로운 개념을 제안한 것이다. 기존 방식에서 디렉토리 포인터가 하나의 특정 노드를 가리킨데 반해, 방송 디렉토리의 포인터는 다수의 노드로 구성된 일정 영역을 가리키도록 한다. 이 기법은 대부분의 직접 상호연결망이 지원하는 결정적 경로 배정 방식과 웜홀 스위칭방식의 특성을 활용함으로써 가능하다. 캐쉬 일관성 동작은 이 포인터가 지시하는 영역 전체에 속한 모든 노드들에게 하나의 메세지를 방송하는 것으로 이뤄진다. 각 노드의 라우터는 이 방송 메세지들을 구분할 수 있는 관찰 능력(snooping capability)을 갖도록 수정할 필요가 있다. SPLASH 병렬프로그램들을 이용한 실험결과에서, 제안한 기법이 전체 통신량과 수행시간 측면에서 기존의 모든 디렉토리 기법들을 앞서는 것으로 나타났다. 특히 전사벡터 기법보다 우수한 수행 시간을 보인것은 흥미있는 결과인데, 이는 감소한 통신량에 따른 낮은 빈도의 네트웍 충돌, 적은 메세지 수에 따른 노드 점유 시간의 감소 등이 기여한 것이다. 또한 이 방송 기법이 요구하는 디렉토리 메모리의 양은 Θ(N logN)으로써 전사방식에 비해 보다 우수한 확장성을 보인다.
본 논문의 후반부에서는 새롭게 제안된 방송 기법을 바탕으로 광공유 데이터의 특성을 활용한 개선된 캐쉬 일관성 기법들을 소개한다. 하나는 광공유 데이터의 쓰기열 길이(write-run length)가 매우 작다는 점을 이용하여, 이 데이터들에 대해 '쓰기 무효화 기법'이 아닌 '쓰기 갱신 기법'을 사용하는 것이다. 이 기법에서 특히 중요한 것은 각 프로그램에서 광공유 데이터들을 구별하는 방법과 이의 정확성이었다. 다른 하나의 개선책은 여전히 쓰기 무효화 기법이 효과적인 광공유 데이터들을 효과적으로 지원하는 것이다. 이 데이터들은 대개 한 프로세서에 의해 쓰기가 일어난 후, 거의 동시에 다수의 프로세서에 의해 읽혀지는 특성을 보인다. 이러한 읽기 폭주현상은 네트웍과 메모리 모듈에 대한 지나친 경쟁을 초래하여 시스템의 성능 저하를 가져 온다. 따라서 앞서 제안된 방송 기법을 활용 하여 네트웍상에서 동일 메모리에 대한 읽기 요구를 병합(combining)하는 한편, 해당 메모리의 데이터를 하나의 메세지로 방송함으로써 전체 통신량의 현저한 감소와 수행 시간의 단축을 가능하게 한다.
