Cache coherence is an important and well-known problem in shared-memory multiprocessors. When each processor in a multiple processors maintains a locally cached copy of a memory block, any local modification of the cached copy can result in a globally inconsistent view of memory. The directory-based scheme is an attractive approach to solve the cache coherence problem in a large-scale shared-memory multiprocessor. However, the existing directory based schemes have some problems such as the enormous storage overhead for a directory, the long invalidation latency, the heavy network congestion, and the low scalability.
For resolving these problems, we propose a new directory-based cache coherence scheme, called BIND scheme, which is suitable for building scalable, shared-memory multiprocessors. The BIND scheme uses a form of the write-update by means of a memory update policy. The scheme is a class of distributed directory schemes, since the information for the cache coherency is decentralized and distributed among the cache entries. Each directory entry for a given memory block is made up of a number-balanced binary tree (NBBT) structure. The NBBT has several properties to efficiently maintain the directory for the cache consistency such that the shape is unique, the maximum depth is [$log_2n$], and the tree is semi-full binary tree in the binary tree with n nodes. Therefore, the BIND scheme can reduce the storage overhead, the network traffic, and the write latency and can ensure the high scalability in the scalable, shared-memory multiprocessors.
In this thesis, we also develop a cache coherence protocol which and efficiently maintain the consistency of the cached copies. certifying its efficiency, compare the BIND scheme with the existing directory schemes with respect to the storage overhead, the network traffic, the invalidation latency, and the memory access latency.
캐쉬를 가진 공유기억 다중처리기에서의 가장 중요한 문제 중 하나가 캐쉬 일관성 문제 (cache coherence problem)이다. 다중처리기의 각 프로세서가 주기억장치 자료 블록의 복제를 가지고 있을 때, 같은 블록의 복제를 가진 한 프로세서가 그 복제를 수정하게 되면 자료의 불일치성 문제가 발생하게 된다. 이러한 문제를 해결하기 위하여 여러가지 캐쉬 일관성 유지 기법들이 제안되어 있다. 그 중 디렉토리를 이용하는 캐쉬 일관성 유지 기법들(directory-based cache coherence schemes)은 많은 프로세서를 다단계 연결망과 같은 상호연결망으로 연결시킨 대규모 공유기억 다중처리기에서 사용하기 위하여 제안되었다.
이러한 기법들은 크게 풀맵 디렉토리 방식, 제한 디렉토리 방식, 그리고 연결 디렉토리 방식으로 나누어진다. 그러나 풀맵 디렉토리 방식은 성능이 뛰어나지만 캐쉬 일관성 유지를 위하여 과다한 메모리를 요구하고, 제한 디렉토리 방식은 메모리량은 줄일 수 있지만 제한된 포인터로 인하여 자료 블록의 복제가 증가하게 되면 상호연결망의 통신량이 급증하는 문제가 발생하며, 연결 디렉토리 방식에서는 메모리량은 현저하게 줄일 수 있지만 쓰기 실패 시 복제 무효화 시간이 길어지는 문제가 발생한다.
이러한 문제를 해결하기 위하여 본 논문은 BIND 기법이라는 새로운 디렉토리 캐쉬 일관성 유지기법을 제안하였다. 이 기법은 캐쉬 일관성 유지를 위한 디렉토리를 수 평형 이진 트리 (number-balanced binary tree) 형태로 분산시켜 유지 관리한다. 수 평형 이진 트리는 대규모 공유기억 다중처리기에서의 캐쉬 일관성 유지를 효율적으로 관리하게끔 하는 다음과 같은 특징들을 가지고 있다. 첫째, 노드 갯수가 정해지면 트리 형태가 결정되어 진다. 즉, 노드갯수에 대하여 일정한 트리 형태가 되어진다. 둘째, 트리의 최대 깊이는 노드 갯수가 n개 일 때 log n이다. 셋째, 이 트리는 세미풀 이진 트리이고, n개의 노드를 가지는 세미풀 이진 트리 중에서 가장 작은 수의 리프 노드를 가지며, 총 노드 수가 결정되면 리프 노드의 갯수도 결정되어진다. 따라서 이러한 특성을 이용한 BIND 기법은 확장 가능한 대규모 공유기억 다중처리기에서, 확장성을 유지하면서도 메모리량과 연결망의 통신량을 줄일 수 있으며 쓰기 실패 시 무효화 시간도 줄일 수 있다.
본 논문에서는 캐쉬 일관성 유지를 위한 BIND 기법에서, 발생되는 메시지, 주기억장치 블록과 캐쉬 앤트리의 상태, 그리고 메시지에 따른 상태 전이도 정의하고, 이들을 바탕으로 캐쉬 읽기, 쓰기, 대체 시의 일관성 유지프로토콜도 설계하였다.
그리고 BIND 기법의 효율성을 입증하기 위하여 기존의 기법들과 메모리 오버헤드, 네트웍 트래픽, 무효화 시간, 대체 시간, 메모리 접근 시간 등을 비교 분석하였다.
