Distributed shared memory (DSM) is a viable architecture for scalable, high performance multiprocessor systems. Directory-based cache coherence protocols are widely used for hardware DSM systems, but they suffer from overhead for processing coherence messages. The aim of speculative coherence schemes is to reduce the overhead of performing such coherence actions by speculatively changing the state of cached block in a node. Because dynamic schemes can reflect dynamic behavior of application programs without user intervention, it is a desirable form for a specualtive coherence scheme despite of its hardware overhead. However, existing proposals for dynamic speculative coherence have several disadvantages. Dynamic self-invalidation (DSI) is the first approach and it lacks the capability of predicting timing. Last-touch predictor (LTP) overcomes such handicap, however it needs a special type of integrated processor which includes DSM controller and the predictor. Moreover, it performs poorly for irregular access patterns like competing accesses in synchronization constructs and false sharing. Existing schemes also lack the capability of differentiating write patterns and show low performance for non-migratory write patterns.
In this dissertation, we propose speculative coherence using decoupling synchronization (SCDS), which predicts the timing and types of the coherence action based on synchronization information. SCDS exploits the characteristics that conflicting accesses to a block is usually decoupled by a synchronization. SCDS does not need to watch every memory access in the processor, and it is shown to be less sensitive to competing accesses and false sharing. The simulation under sequential consistency shows higher average performance (7.1% of speedup) than other two schemes (4.2% for LTP, and 2.7% for DSI). SCDS, however, assumes too strict synchronization patterns for some applications like mp3d, thus we suggest SCDS-LS (last synchronization) for such applications, and it shows better performance for em mp3d than SCDS. Limitations of SCDS are bursty traffic at the synchronization and less timely than trace-based scheme (LTP).
We propose enhanced last-touch predictor (E-LTP) to apply lessons learned from SCDS, to build more effective coherence predictor without consideration of cost. As a result, E-LTP with dual history and synchronization awareness shows stable performance over application programs and performs a little better than SCDS.
Also we suggest more techniques for future enhancement of SCDS and existing predictors. Acknowledgement grouping will reduce the bursty traffic and overhead of synchronization-based approaches. Exploiting conditional branch outcome will raise hit ratio for predictors. Finally, more applications of speculative coherence schemes and its relationship with other latency-reducing techniques are discussed.
본 연구에서는 분산 공유 메모리 시스템을 위하여 효과적인 예측적 캐쉬 일관성 기법들을 제안한다. 분산 공유 메모리(DSM)은 고성능의 확장성 있는 다중처리기 시스템을 위해 사용되고 있다. 디렉토리-기반 캐쉬 일관성 프로토콜은 하드웨어 DSM 시스템 을 위해 널리 쓰이고 있으나, 일관성 메시지를 처리하는 데에 시간 지연을 겪는다. 예측적 캐쉬 일관성 기법의 목적은 미리 노드 안에 캐쉬된 블럭의 상태를 바꿈으로써 그러한 일관성 작업의 오버헤드를 줄이는 것이다.
동적으로 운용되는 예측적 캐쉬 일관성 기법은 사용자의 간섭 없이 응용프로그램의 동적인 행동을 반영할 수 있어서 바람직하나, 제안되어 있는 방법들은 몇가지 단점을 가지고 있다. DSI(Dynamic Self-Invalidation)는 처음으로 제안된 방법이지만 일관성 작업을 미리 수행할 시간을 예측하지 못하기 때문에 너무 이른 캐쉬 무효화(invalidation) 현상이 일어난다. LTP(Last-Touch Predictor)는 그러한 단점을 극복하였지만 트레이스를 추적하는 비효율적인 방법으로 프로세서의 복잡도를 증가시키고 DSM 제어기를 프로세서에 내장시켜야 하는 단점이 있다. 또한 트레이스에 기반한 방법의 문제로서 동기화 구조 내에서 일어나는 한 메모리 블럭에 대한 경쟁적인 접근이나 거짓 공유로 인해 일어나는 불규칙한 접근 패턴에 잘 대처하지 못한다. 현존하는 방법들은 쓰기 패턴을 구별하지 않기 때문에 이동하는 쓰기 형태(migratory write pattern)가 아닌 쓰기 형태를 갖는 응용프로그램에 대해 나쁜 성능을 보인다.
본 연구에서는 이러한 단점을 극복하기 위해 SCDS(Speculative Coherence using Decoupling Synchronization)라는 방법을 제안한다. 이 방법은 동기화 정보에 기반하여 일관성 작업의 시기와 패턴을 예측하여 미리 수행한다. SCDS는 동기화에 의해 상충하는 메모리 접근이 순서화된다는 특징을 이용하기 때문에 직접적인 동기화의 노출을 필요로 한다. 그 대신 SCDS는 프로세서 안에서 각 메모리 접근을 추적할 필요가 없으며, 경쟁적인 메모리 접근이나 거짓 공유에 대해서도 민감하지 않게 반응한다. 순차적 일관성 하의 실험 결과에 따르면 SCDS는 평균 7.1%의 성능 향상을 보여 다른 두가지 방법(LTP에서 4.2%와 DSI에서 2.7%)보다 잘 동작함을 알 수 있다. 그러나 mp3d와 같은 응용프로그램은 SCDS가 가정한 형태의 동기화를 사용하지 않기 때문에 SCDS의 성능이 많이 떨어진다. 이러한 단점을 보완하기 위해 SCDS-LS를 제안하며, SCDS-LS는 mp3d에서의 성능을 향상시킨다.
SCDS는 동기화에 기반하고 있어서 동기화 시점에서 과도한 트래픽을 야기시키거나, LTP와 같은 트레이스 기반 방법보다 늦게 일관성 작업을 수행하는 경향이 있다. LTP에서 구현 비용에 관한 문제를 생각하지 않는다면 SCDS에서 알려진 사실들을 적용하여 보다 나은 예측기를 고안할 수 있다. 본 연구에서는 확장된 LTP (E-LTP)를 제안하여, 이중 자취(dual signature) 기법과 동기화 노출 기법이 고른 성능 향상을 나타냄을 보인다.
또한 본 연구에서는 SCDS와 다른 예측적 캐쉬 일관성 기법들을 위한 발전 방향을 제시한다. 캐쉬 일관성 작업의 확인 메시지를 묶는 기법은 동기화에 기반한 방법에서 일어나는 과도한 트래픽을 줄일 수 있을 것이다. 또한, 조건 분기의 내용을 활용함으로써 예측기의 성능을 높일 수 있다. 이러한 예측적 캐쉬 일관성 기법들은 다른 지연 감소 기법과 함께 활용됨으로써 더 좋은 성능을 나타낼 수 있는데, 선인출 기법이나 공유 예측기와 함께 활용하는 방법을 제시한다.
