分散式共享記憶體中一致性問題之研究

Abstract

在分散式系統中，透過網路去結合各種不同的電腦系統已成目前的發展趨 勢，如何達到透明化的執行環境是個很重要的研究課題。在本論文中，我 們著手研究分散式共享記憶體的架構──它是一塊由網路上各電腦工作元 間所形成的虛擬記憶體。而在這樣的架構上，最有待克服的即是各工作元 間記憶體一致性的問題。首先，我們設計了一個自我調整式的分散式共享 記憶體系統，主要的根據是在於──如何選擇解決一致性問題的演算法則 取決於資料的存取特性。我們會設計三套演算法則分別解決不同資料種類 的一致性問題，另一方面在應用程式的執行過程中，我們的系統將隨著資 料存取特性的改變而調整適合的演算法則。實驗數據顯示自我調整式的分 散式共享記憶體系統有相當不錯的結果。此外，在分散式共享記憶體中還 有一個假共享的問題，這會使得產生大量不必要的一致性錯誤，因此有許 多一致性的模式產生以減少網路和記憶體時間延遲的影響，所以我們也提 出了一個結合放鬆式記憶體一致性的模式和編譯器輔助式策略的混合式方 法去同時解決一致性和假共享的問題。實驗數據顯示混合式的方法的確可 以有效減少分散式共享記憶體中一致性的負荷。由於我們已成功地發展了 兩套分散式共享記憶體系統，相信未來由於網路傳輸速度的提升，會使分 散式共享記憶體成為分散式系統中撰寫平行化程式的良好環境。 Software distributed shared memory (DSM) provides a convenient and effective solution for programming parallel applications on distributed systems. However, the performance of current implementations suffers from large overhead in enforcing memory coherence. In this thesis, we propose two coherence schemes to solve memory coherence problems. The first scheme is based upon the observation that the performance of distributed shared memory depends on the memory coherence algorithms and the access characteristics of shared data. Therefore, we propose an efficient directory-based coherence scheme using multiple coherence algorithms with self-adjusting feature. This method can dynamically choose suitable coherence algorithm for each shared variable class. The second scheme is based on the observation that there exists false sharing problem that causes unnecessarily large amount of coherence faults. Various memory consistency models have been proposed in order to eliminate the effects of network traffic and memory latency. We present a hybrid approach that combines relaxed memory consistency models and a compiler strategy to solve memory coherence and false sharing problems for DSM. Experimental results show that this hybrid approach produces fewer coherence faults and is effective for reducing the memory coherence overhead of DSM.