建立一個針對Busy-Waiting演算法之分散式共享記憶體模型

Abstract

在非同步共享記憶體系統中，busy-waiting 現象為許多實際問題無法避免的負擔， 例如：互斥問題或是 barrier synchronization 問題。然而，如果busy-waiting 機制是利 用不斷讀取遠端記憶體來判斷是否該停止waiting，則將產生大量處理器與記憶體之間 的流量，進而大大降低系統效能。因此，最近研究焦點之一為利用local spinning 方式 來設計busy-waiting 機制，以減少遠端記憶體的讀取次數。不過，目前仍沒有一個正 規模型可以用來分析關於遠端記憶體讀取次數的複雜度。本計畫目的為首先提出一個 針對分散式共享記憶體系統的模型，使得可以清楚地定義何謂一個遠端記憶體讀取。 為了說明這個新模型的功用，我們將推導下列的結果： (1) 明確定義何謂一個 local-spin 演算法，目前文獻對於local-spin 皆只是訴諸系統使用者經驗累積之判斷而 使用模糊概念語言加以描述； (2) 證明互斥問題與barrier synchronization 問題針對讀 取遠端記憶體次數的極限值 (lowerbusy-waiting、local spinning、barrier synchronization、互斥問題、分散式共享 記憶體系統 bounds)。