跳轉至內容

平行計算與計算機叢集/記憶體

來自 Wikibooks,開放世界中的開放書籍

在早期單 CPU 機器中,CPU 通常位於一個專用的系統匯流排之間,連線自身與記憶體。每次記憶體訪問都將透過匯流排,並直接從 RAM 返回。隨著 CPU 速度的提高,RAM 和匯流排速度也隨之提高。由於涉及到的電子元件,記憶體訪問和 RAM 響應週期成為瓶頸,迫使 CPU 浪費寶貴的計算週期等待響應返回(稱為延遲)。

為了克服這種延遲,一些設計涉及在系統總線上放置一個記憶體控制器,它接收來自 CPU 的請求並返回結果 - 記憶體控制器會在本地保留最近訪問的記憶體部分的副本(一個快取),因此能夠更快地響應許多涉及順序(例如程式程式碼)或區域性分散的請求(例如程式程式碼定期訪問的變數)。

隨著 CPU 變得更快,即使從記憶體控制器快取區域檢索 RAM 所涉及的延遲也變得非常昂貴。下一階段的發展將看到記憶體控制器被放置在 CPU 本身晶片的鑄造中(在許多情況下,將記憶體控制器保留在總線上作為副本),從而誕生了 CPU 快取。由於 CPU 快取位於 CPU 晶片上,因此 CPU 核心和 CPU 記憶體控制器之間的匯流排長度大大減少,記憶體控制器可以更快地響應,從而減少 CPU 的延遲,直到需要非快取元素為止。

後來,進一步的工程改進意味著 CPU 快取的速度開始與 CPU 本身的速度相匹配,允許每個指令週期都無需來自其快取的等待狀態。不幸的是,這種設計的成本很高,因此第二層或二級快取被放置在晶片上,並使用更便宜(更舊)的設計製成:CPU 現在有了一級二級快取。由於二級快取更便宜,因此可以比一級快取以更大的數量進行晶片鑄造,並且在保持合理的生產成本和節省普通 RAM 訪問速度的同時,也節省了與 RAM 訪問速度相比從二級快取填充有限的一級快取的成本。

RAM 和多個 MPU

[編輯 | 編輯原始碼]

在最簡單的多 MPU 設計中,每個 MPU 沒有快取,並直接位於總線上,允許訪問 RAM(直接 RAM 訪問或透過記憶體控制器)。從單 CPU 設計擴充套件而來,一個僅讀取資訊的 MPU 多設計可以簡單地設計:每個 MPU 在總線上傳送其請求,但需要一種方法來識別請求來自何處。為此,必須以某種方式擴充套件請求以標記請求,最明顯的標識是 MPU 所在的插槽(如 CPU 啟動過程中 BIOS 所指示)。返回到 MPU 的響應,如果沒有其 ID,則可以安全地忽略。識別過程通常由一個控制器執行,該控制器不是多 MPU 的一部分,而是在總線上一個單獨的專業 MPU,稱為可程式設計中斷控制器 (PIC)。

不幸的是,無法寫入任何資料的系統在靈活性方面將非常有限,因此必須能夠將資料寫回 RAM。寫回 RAM 的機制再次成為單 CPU 系統的簡單擴充套件:寫回 RAM 指示請求來自哪個 MPU 插槽,任何確認響應都可以以相同的方式正確識別,允許任何單個 MPU 知道其寫入請求是否成功。

唉,有一個重大的缺陷:如果兩個(或更多)MPU 同時處理同一塊資料會發生什麼?每個 MPU 從 RAM 讀取資料,根據各個 MPU 正在處理的程式程式碼處理資料,並將結果寫回 RAM。問題在於哪個 MPU 最後執行了寫入請求,因為正是該 MPU 的結果將駐留在 RAM 中,而不是第一個。為了更清楚地說明這個問題,請考慮以下情況,其中活動引用同一個記憶體位置(一個數字)。

活動 MPU 1 MPU 2
從程式程式碼讀取記憶體 被指示增加 RAM 位置 0001 被指示減少 RAM 位置 0001
讀取程式碼引用的記憶體資料 接收值為 1 接收值為 1
處理指令 計算結果為 2 計算結果為 0
從程式程式碼讀取記憶體 被指示將結果放入 RAM 位置 0002 被指示將結果放入 RAM 位置 0002
處理指令 將值 2 放入 RAM 位置 0002 將值 0 放入 RAM 位置 0002

如果這是一個 SMP 系統,則兩個 MPU 將以相同的速度進行處理,並且兩個 MPU 都將同時到達管道的每個階段。結果,每個 MPU 都將嘗試同時將其對資料的解釋寫回 RAM 位置 0002。之後 RAM 位置 0002 的值是多少?不幸的是,沒有保證,除非首先實施其他方法來強制此競爭條件不發生。

非快取 MPU

[編輯 | 編輯原始碼]

在非快取 MPU 中,MPU 將在總線上請求鎖定一組記憶體範圍,以防止其他處理器更新記憶體區域,直到鎖定 MPU 完成其自身任務。這種方法效率低下,因為鎖定阻止了第二個(或後續)MPU 訪問記憶體區域。

引入快取

[編輯 | 編輯原始碼]

隨著在處理器中引入快取,問題最初變得更加普遍。回到具有快取的單處理器體系結構以更好地說明這個問題,快取提供了對已訪問的記憶體區域的快速訪問。MPU 從一個完全標記為無效的快取開始,從那裡,對 RAM 位元組的任何請求都將自動載入 RAM 的頁面到快取中(僅填充快取的一部分)。當處理器訪問非快取 RAM 的不同部分時,該 RAM 頁面也將與已快取的頁面一起載入。該過程持續進行,直到快取充滿了有效頁面。

一旦快取已滿,並且處理器需要訪問尚未快取的 RAM 頁面,它必須決定在快取的哪個位置寫入此新頁面:無論頁面寫入何處,它都將覆蓋現有的快取 RAM。那麼,處理器如何決定?使用兩種基本方法:保留最近訪問的頁面和隨機選擇。在第一種方法中,MPU 的記憶體控制器跟蹤快取頁面的最近訪問順序,並選擇最舊的快取頁面作為要覆蓋的頁面。

在特別複雜的演算法中,最舊訪問的快取頁面可能不是最方便刪除的頁面:程式碼可能會在 RAM 頁面之間跳躍,從許多不同的頁面中訪問很少的資料,同時很少訪問資料集(與所有程式程式碼相比)或反之亦然。由於在 RAM 中跳躍,快取會丟失其快取中的資料集(RAM 最常訪問的單個頁面)。在這種情況下,處理器最好丟失任何一個不常訪問的程式程式碼頁面,而不是資料集本身(請注意,有一個非常有力的論點說明任何以這種方式執行的程式要麼程式編寫不當,要麼編譯不當)。

除了快取從 RAM 讀取的資料外,還可以透過處理器類似地快取資料寫回 RAM,然後在重新整理頁面時將其作為整個頁面寫入。對於單 MPU 系統,寫入快取對系統中的其他元件沒有影響,因此可以在寫回任何修改的快取頁面時花費時間(請注意,在 CPU 將修改後的資料寫回 RAM 之前,RAM 保持不變)。這種方法稱為延遲寫入

簡單的快取寫入

[編輯 | 編輯原始碼]

回到多處理器系統和使用快取的問題,這個問題變得更加明顯:當任何處理器寫入RAM的一部分時,資料會被放入其快取中,而不是寫回RAM。如果另一個處理器嘗試讀取同一部分RAM,它接收到的資料將過時。必須使每個處理器快取的內容彼此保持一致(或相干,因此稱為快取一致性)。已經設計了各種方法來確保快取儘可能保持一致。最簡單的方法是確保任何寫操作都透過匯流排立即將資料推回RAM,體系結構中的所有處理器都在監控總線上的寫操作:當在總線上看到寫操作時,處理器檢查其自己的快取中是否存在同一頁RAM,如果已快取,則該頁會立即從RAM中重新載入。對於使用資料公共子集的大型並行系統來說,這是一種非常昂貴的方法:當單個處理器寫入資料段時,每個其他快取了該資料的處理器都必須重新請求資料。透過其他處理器在資料寫回RAM時從總線上讀取資料(稱為嗅探)可以大大改進該方法,從而無需潛在的n - 1個請求來讀取同一RAM位置。在更高階的改進中,嗅探應用於所有匯流排資料包,這樣任何單個讀取操作都可能被快取到體系結構中的所有處理器中。

基於目錄的寫入

[編輯 | 編輯原始碼]

無論是否使用快取,基於目錄的寫入技術都涉及所有RAM由一個位於中心的記憶體管理器控制。所涉及的處理器只遵守記憶體管理器提供給它們的資訊,寫請求可以來自記憶體管理器到單個處理器,請求立即寫回資料。

MOESI & 前身

[編輯 | 編輯原始碼]

存在更高階的快取一致性技術,這些技術從一組類似的功能開始。幾乎普遍地,這些方法中的每一種都將所有RAM頁面標記為修改、共享或無效之一。更復雜的方法引入了獨佔和/或所有者的標記。這些方法的名稱通常以實現方法的首字母縮寫來表示:MSI、MESI、MOSI和MOESI。

狀態 描述
已修改 該頁面被標記為已更改,並駐留在處理器的快取中,但RAM中沒有有效副本。在也使用所有者狀態的方法中,其他任何處理器都不需要修改的頁面。
所有者 修改狀態的補充,其中一個原本已修改的頁面被其他處理器需要和使用。在大規模並行系統中,體系結構的記憶體控制器儲存有關哪些其他處理器需要該頁面的資訊,因此能夠跨越匯流排邊界分發必要的頁面。
獨佔 擁有該頁面的處理器是唯一快取了該頁面的處理器。沒有其他處理器請求或保留該頁面。
共享 標記為共享的頁面表示一個或多個處理器在其快取中擁有該頁面。如果該方法使用獨佔,則共享表示多個處理器擁有該頁面。
無效 無效的快取頁面是指不能依賴其有效資料的頁面。處理器通常只以無效頁面開始(一些系統在引導之前預載入處理器的快取中一些簡單的引導程式碼)。一些MOESI實現會在將頁面寫入RAM時將其標記為無效。

避免競爭條件

[編輯 | 編輯原始碼]

無論使用哪種記憶體管理技術(並且存在比上面描述的更多變體和技術),在快取中生成無效資料的可能性仍然存在。但是,這些可能性是由於程式設計技術差或理解錯誤以及/或編譯差的性質造成的。這將在軟體章節中深入介紹。

統一記憶體訪問

[編輯 | 編輯原始碼]

顧名思義,統一記憶體訪問(UMA)描述了一種所有對記憶體的訪問都以統一、平等的方式執行的方法。在UMA設計中,RAM通常被集中在一起,並且通常有一個記憶體控制器來幫助CPU訪問RAM。UMA是SMP中實現RAM訪問最常見的方法。

非統一記憶體訪問

[編輯 | 編輯原始碼]

在並行處理體系結構和叢集中非常流行。非統一記憶體訪問(NUMA)體系結構是一個系統(單機或叢集),它包含一個分佈在整個系統中的單個RAM塊。例如,一個四處理器體系結構可以由兩對處理器組成,每對處理器可以直接訪問2GB的RAM。在這種情況下,每對處理器都連線到一個本地匯流排及其共享的2GB。對另一對的2GB的訪問是透過匯流排間連結(通常是記憶體控制器)執行的。

NUMA系統的一個更極端的示例通常用於試圖呈現單一系統映像的叢集:叢集中的每個節點都包含一部分系統RAM,叢集軟體是本地化的記憶體控制器。存在於叢集的一個節點上的程序必須訪問儲存在另一個節點上的記憶體部分。與第一個節點透過(其本地化的叢集記憶體控制器)訪問其自己的真實RAM相比,嘗試訪問備用節點上的RAM部分涉及一個更復雜的情況:第一個節點必須向第二個節點發出請求,要求它透過網路傳送RAM;第二個節點必須檢查該部分是否已被另一個(第三個)節點修改;如果正在被修改,則第二個節點必須請求第三個節點放棄RAM訪問;第三個節點將修改寫回第二個節點,最後第二個節點將RAM部分釋放給請求節點。如果兩個節點需要頻繁修改訪問同一RAM部分,則結果會嚴重影響叢集以有價值的方式處理資料的能力。值得慶幸的是,存在軟體技術(與這裡描述的技術非常相似)來減少這種情況的影響。

進一步閱讀

[編輯 | 編輯原始碼]
華夏公益教科書