Scalable shared memory multiprocessor (SSMP) systems achieve both the easy programming model and the scalable performance. The former comes from the provision of a single, coherent view of shared address space; the latter from the scalable interconnection networks (IN) and the distribution of physical memory sections to individual node computers connected with one another by them. For low-latency, high-bandwidth shared memory accesses, per-processor caches should be allowed to cache data from the shared address space. Multiple copies of a shared data object, however, become incoherent if multiple processors are permitted to write to the cached copies simultaneously without coordination. This problem, which is called the {\em cache coherence problem}, is of great significance in the performance of cache coherent SSMP systems.
Directory cache coherence schemes keep caches coherent by point-to-point communications only to those processors caching the memory block by using the directory next to memory which stores the locations of cached copies of every memory block. By avoiding costly broadcast, saturation in the IN can be avoided and system scalability increases. Unfortunately, the most straightforward directory scheme, the full map directory scheme, requires directory memory which grows as the square of the system size. Many directory schemes have been proposed to mitigate this directory memory overhead scaling problem, but they usually either require large bandwidth for coherence traffic or exhibit poor system performance.
This dissertation explores various design points of the scalable directories: the individual directory element design, the arrangement of such directory elements, and the communication support for cache coherence.
First, this dissertation proposes a new directory element called the segment directory, which is a hybrid of the full map vector and the pointer. It can be used in place of the pointer in most pointer-based directory schemes to improve directory storage efficiency: a segment directory element can point to several processors with almost the same number of bits as the pointer which can point to only one. In this dissertation, the segment directory is applied to four of the previous limited and extended directory schemes, and performance improvement is then evaluated. Through detailed execution-driven simulations with the SPLASH-2 benchmark suite, we prove that the segment directory eliminates directory overflows by up to 85\%, and reduces the traffic and execution time accordingly, for all the workloads run on the four schemes. This is the first effort in literature to reduce directory overflows themselves. Moreover, the segment directory does not introduce additional hardware overhead or protocol complexity.
Second, this dissertation proposes a new directory organization called the dynamic vector directory, which improves the dynamic pointer directory of the Stanford FLASH multiprocessor by replacing the pointer with the full map vector. With reasonable amount of directory memory, it eliminates the costly link traversals to delete entries that are evicted in the per-processor caches, thereby reducing directory controller occupancy by much. It can be thought of an implementation of the sparse directory having full associativity, with greatly reduced hardware complexity.
Third, this dissertation introduces a new method of augmenting the mesh network with row and column buses. We augment point-to-point mesh with virtual row/column buses each of which is dynamically established upon request by using those links of the corresponding row/column of the mesh. On-going messages on the row/column are frozen intact in the switch buffers bypassed during bus transaction. Bus data propagates in a pipelined fashion, following the repeater delay model. Network bandwidth is shared between mesh and buses dynamically. As a result, the virtual buses resolves the static bandwidth allocation which is a problem of conventional mesh with buses.
Finally, this dissertation proposes a new collective cache invalidation technique utilizing the virtual buses. Because invalidation delivery is collective in nature, multiaccess media such as the virtual buses can efficiently distribute the invalidations. For cache coherence, we use a customized coarse vector directory scheme, where a coarse vector bit represents the aggregate caching status of processors on a single column bus after directory overflows. Multiple unicast invalidations by a coarse vector bit are merged into one bus transaction. Through the detailed simulations with real workloads, we prove that the new coarse vector scheme having only two pointers per memory block exhibits better performance than does the full map directory scheme. Furthermore, the invalidation mechanism can be implemented with minor changes to network switches and wiring.
대규모 공유 메모리 다중 프로세서 (SSMP) 시스템들은 사용자에게 일관된 하나의 공유 주소 공간을 제공하면서도, 메모리들을 확장성이 우수한 상호 연결 네크워크로 연결된 단위 컴퓨터들에게 분산시킴으로써, 편리한 프로그래밍 모델을 제공하는 동시에 확장성이 우수하여 높은 성능을 제공한다. SSMP 시스템에서 공유 메모리 접근 지연을 낮추고, 대역폭을 키우기 위해, 프로세서 캐쉬들이 공유 주소 공간의 데이터를 캐쉬하도록 허용되어야 한다. 그러나, 만약 복수 개의 프로세서들이 캐쉬 복사본들에 아무런 제약 없이 동시에 쓰기 동작을 수행할 수 있다면, 하나의 공유 데이터 객체의 여러 복사본들의 내용이 서로 일치되지 않게 된다. 이는 캐쉬 일관성 문제라고 불리며, SSMP 시스템의 성능에 매우 중요한 요소이다.
버스를 기반으로 하는 다중 프로세서에서는, 버스라는 공통의 방송 매체를 사용하여 캐쉬의 일관성을 유지한다. 캐쉬 제어기들이 버스 상의 모든 동작을 감시하여 적절한 일관성 유지 동작을 취한다. 하지만, SSMP에서 사용되는 확장성이 우수한 상호 연결 네트워크에서는 방송을 통해 일관성 유지 메시지를 전달하는 비용이 너무 크다. 만약 일관성 유지 메시지들이 방송된다면, 확장성이 우수한 상호 연결 네트워크를 쓰는 것이 무의미해 질 것이다.
디렉토리 캐쉬 일관성 유지 방법에서는 메모리 블록의 복사본을 가지고 있는 프로세서들의 위치를 디렉토리에 기록한다. 기록된 디렉토리 정보를 이용하여 그러한 프로세서들과의 일대일 통신으로 캐쉬 일관성을 유지한다. 따라서, 상호 연결 네트워크의 포화를 피할 수 있고, 시스템의 확장성을 향상시켜 획기적인 성능 증가를 이룰 수 있다.
그러나, 불행하게도, 가장 기본적인 디렉토리 방법인 전체 디렉토리 방법은 시스템 크기의 제곱에 비례하는 디렉토리 메모리를 필요로 한다. 디렉토리 메모리의 크기를 줄이기 위해 여러 디렉토리 방법들이 제안되었으나, 전체 디렉토리 방법을 사용하였을 때에 비해 프로그램 수행 시간이 증가되고 네트워크 대역폭 요구량 또한 증가된다는 단점이 있다.
본 학위 논문은 디렉토리 메모리 크기 문제를 해결하기 위해, 보다 더 확장성이 우수한 디렉토리 구조와 방법들을 제안하고, 효율적인 캐쉬 무효화 방법을 제시한다.
첫째, 본 학위 논문은 전체 벡터와 포인터의 장점을 결합한 새로운 디렉토리 요소인 세그먼트 디렉토리를 제안한다. 이는 대부분의 포인터 기반 디렉토리 방법에서 포인터 대신 사용될 수 있으며 디렉토리 저장 효율을 향상시킨다. 하나의 포인터가 단지 하나의 프로세서만을 가리킬 수 있는 반면, 하나의 세그먼트 디렉토리 요소는 거의 같의 양의 메모리를 사용하여 복수 개의 프로세서들을 가리킬 수 있다. 또한, 본 논문은 세그먼트 디렉토리를 네 개의 한정 디렉토리 및 확장 디렉토리 방법들에 적용하여 성능 향상을 측정하고 분석하였다.
SPLASH-2 벤치마크 프로그램을 작업부하로 하는 자세한 실행 구동 시뮬레이션을 통하여, 세그먼트 디렉토리가 위의 네 개의 디렉토리 방법들에서 85% 까지의 디렉토리 넘침을 제거하고, 모든 벤치마크 프로그램의 통신 요구량과 수행시간이 이에 따라 감소한 것을 확인하였다. 실제로, 이는 디렉토리 넘침 자체를 줄이려는 최초의 시도이다. 더구나, 제안된 세그먼트 디렉토리는 추가적인 하드웨어 혹은 프로토콜 복잡도를 야기하지 않는다.
둘째, 본 논문은 동적 벡터 디렉토리라는 새로운 디렉토리 구조를 제안한다. 이는 동적 포인터 디렉토리의 포인터를 벡터로 대치하여 성능 향상을 꾀하는 방법으로서, 일반적인 크기의 디렉토리 메모리를 사용하여 동적 포인터 디렉토리의 링크 탐색을 제거한다. 결과적으로 디렉토리 제어기 점유도를 감소시켜 다중 프로세서의 성능 향상의 병목을 제거한다.
세째, 본 논문은 점대점 그물 네트워크에 보조적인 가상 행/열 버스들을 추가하는 새로운 방법을 고안한다. 각 가상 행/열 버스는 요구가 있을 때에만 그물 네트워크의 해당 행/열의 통신 링크를 그대로 사용하여 동적으로 생성된다. 해당 행/열 상에서 진행 중이던 기존 메시지들은 가상 버스 동작 동안 우회되는 라우터 내의 버퍼에 그대로 보관된다. 버스 데이터는 반복기 지연 모델을 따라, 파이프라인 형식으로 전파된다. 결과적으로, 그물 네트워크와 버스들이 네트워크 대역폭을 동적으로 공유한다. 따라서, 가상 버스 그물 네트워크는 기존의 다중 방송 그물 네트워크가 갖는 대역폭 낭비 및 불균형 문제를 해결한다. 어떠한 형태의 통신 부하에서도 효율적으로 대역폭을 사용할 수 있다.
네째, 본 학위 논문은 그물 구조로 연결된 SSMP 시스템에서 가상 행/열 버스들을 사용하는 새로운 집단적 캐쉬 무효화 기법을 제시한다. 디렉토리 방법에서는 무효화 메시지가 점대점으로 전송되지만, 크기가 큰 무효화 동작들에는 본질적으로 방송이 적합하다. 제시된 집단 캐쉬 무효화 기법은 위의 가상 버스 상에서, 캐쉬 일관성을 위해 특성화된 거친 벡터 디렉토리 방법을 사용한다. 디렉토리 넘침이 일어난 메모리 블록에 대해, 거친 벡터의 각 비트는 하나의 열 버스 상의 프로세서들의 집단 캐쉬 정보를 나타낸다. 하나의 거친 벡터 비트에 의한 복수 개의 일대일 무효화 메시지들이 하나의 버스 동작으로 융합된다. 가상 버스를 사용함으로써 버스의 확장성 제한을 해결하고, 거친 벡터를 사용함으로써 가상 버스의 대역폭 요구량을 줄인다.
실제 프로그램을 입력으로 하는 자세한 실행 구동 시뮬레이션을 통하여, 메모리 블록 당 단지 두 개 씩의 포인터들을 가지는 새로운 거친 벡터 디렉토리 방법이 전체 디렉토리 방법보다 10% 까지 우수한 성능을 보이는 것을 확인하였다. 게다가, 제시된 캐쉬 무효화 방법은 네트워크 라우터와 배선에 미미한 수정만을 가함으로써 구현될 수 있다.
