Abstract
在共用記憶體之多處理機系統中，某些演算法使各處理機對資料的存取行 為呈現輪流使用的型態。由於這些共享的資料在眾處理機間被相互傳遞、 交替使用，我們稱之為遷移型物件。以遷移型物件為主的應用程式可以藉 由改良的快取記憶體一致協定而大幅提升執行效率。然而在缺少編譯時期 資訊的情況下，這種協定必須在執行期間動態地偵測出遷移型物件並予以 妥善處理。基於前人的研究成果，本文提出一種新的遷移型共享偵測法： 供應者偵測法。由於採用分散式的偵測方法，它僅需要少量的空間卻能夠 達成準確的辨識。我們採取靜態的分析及動態的模擬來評估供應者偵測法 的成本與效能。在分析方面，文中指出了空間需求上的改進並且正規地證 明了它在準確性上的提升。在模擬方面，我們以三個真實的測試程式來比 較供應者偵測法與現有偵測法之準確性與執行效能。結果證明供應者偵測 法能以相當少量的空間需求達到相同的效能。本文共分六章：第一章簡述 遷移型共享偵測法之演進。第二章解說遷移型共享及偵測遷移型共享之必 要性。除了回顧史氏偵測法之概念及其演算法，並指出了其在空間需求及 精確性上之缺點。第三章詳細陳述供應者偵測法之概念及其協定。第四章 分析供應者偵測法所需之空間及其辨識之精確度，並與史氏偵測法作一比 較。第五章說明模擬方法與結果。在非遷移型共享的應用程式中，供應者 偵測法的精確性有非常良好的表現。第六章總結供應者偵測法為提升多處 理機系統效能一經濟有效之途徑。 In a shared-memory multiprocessor with caches, data accessed by processors exclusively and alternatively are called migratory objects because they look like migrating among the caches. Migratory objects based applications can be improved significantly by an optimizing cache coherence protocol. However without the compiling information, such an optimizing protocol has to detect migratory sharing dynamically at runtime. Based on the previous work, we propose a distributed detecting algorithm, provider detection, which distributively maintains the information and detects migratory sharing. Statically, we analyse the spatial requirement and prove the exactness of provider detection formally. Dynamically, we employ trace-driven simulation and three benchmark programs to compare the exactness and performance of several detecting algorithms. We show that provider detection requires much less memory than the existing solution does while achieves the same performance.