高速緩衝存儲器一致性

高速緩衝存儲器一致性

高速緩衝存儲器一致性(Cache coherence),也稱快取一致性,高速快取間一致性。是指在採用層次結構存儲系統的計算機系統中,保證高速緩衝存儲器中數據與主存儲器中數據相同機制。在一個系統中,當許多不同的設備共享一個共同存儲器資源,在高速快取中的數據不一致,就會產生問題。這個問題在有數個CPU的多處理機系統中特別容易出現。

簡介

記憶體系統的本質是,一個記憶體系統應該能提供一組保存值的存儲單元,當對一個存儲單元執行讀操作時,應該能返回“最近”一個對該存儲單元的寫操作所寫入的值。在串列程式中,程式設計師利用記憶體來將程式中某一點計算出來的值,傳遞到該值的使用點,實際上就是利用了以上的基本性質。同樣,運行在單處理器上的多個進程或執行緒利用共享地址空間進行通信,實際上也是利用了記憶體系統的這個性質。一個讀操作應返回最近的向那個位置的寫操作所寫的值,而不管是哪個執行緒寫的。當所有的執行緒運行在同一個物理處理器上時,它們通過相同的高速快取層次來看記憶體,因此在這種情況下,高速快取不會引起問題。當在共享存儲的多處理器系統上運行一個具有多個進程的程式時,希望不管這些進程是運行在同一個處理器上,還是在不同的處理器上,程式的運行結果都是相同的。然而,當兩個運行在不同的物理處理器上的進程通過不同的高速快取層次來看共享記憶體時,其中一個進程可能會看到在它的高速快取中的新值,而另一個則可能會看到舊值,這樣就引起了一致性問題 。

高速緩衝存儲器一致性的比較正式的一個定義是當一個共享存儲的機器滿足以下條件時,則可以認為該系統是高速緩衝存儲器一致的:

任何進程所發出的訪存操作被存儲器所觀察到的順序必須與進程發出操作的順序相同;

每個讀操作所返回的值必須是最後一次對該存儲位置的寫操作的值。

1.

任何進程所發出的訪存操作被存儲器所觀察到的順序必須與進程發出操作的順序相同;

2.

每個讀操作所返回的值必須是最後一次對該存儲位置的寫操作的值。

以上定義保證了兩個屬性寫廣播和寫串列化。寫廣播指的是寫操作被其他所有處理器所觀察到。定串列化是指對某一存儲位置的所有寫操作的順序,在所有處理器看來都是一樣的。高速緩衝存儲器一致性可以分為三個層級:

在進行每個寫入運算時都立刻採取措施保證數據一致性;

每個獨立的運算,假如它造成數據值的改變,所有進程都可以看到一致的改變結果;

在每次運算之後,不同的進程可能會看到不同的值(這也就是沒有一致性的行為)。

1.

在進行每個寫入運算時都立刻採取措施保證數據一致性;

2.

每個獨立的運算,假如它造成數據值的改變,所有進程都可以看到一致的改變結果;

3.

在每次運算之後,不同的進程可能會看到不同的值(這也就是沒有一致性的行為)。

一致性

關於一致性的概念,直觀上可以定義為每個讀操作必須返回最後寫入此位置的值。對於每個處理器單元的操作都有一個總體的、串列的操作序是我們希望在任何一個一致性存儲系統中見到的。因此,可以對高速快取一致性進行一個更加形式化的定義方法:如果某個程式的任何執行結果都滿足下列條件:對於任何單元,有可能建立一個假想的操作序列(也就是說,將所有進程發出的讀寫操作排成一個全序,此序列與執行結果一致,並且在序列中:(任何特定進程發出的操作所表現出來的序和該進程向存儲系統發出它們的序相同,且每個讀操作返回的值是對相應單元按照串列順序寫入的最後一值,那么此多處理器存儲系統是一致性。

此外,關於多個私有快取還存在另外一方面的問題:如果數據是由一個處理器核對某個單元寫入,而另一個處理器從中讀出這樣的方式來進行傳遞的話,那么我們前面所關注的一致性將是非常重要的。最終,寫在一個單元中的數據將對所有的讀取者都會是可見的,但這種一致性並沒有指明所寫入的數據何時會成為可見的。通常,在編寫一個並行程式時,我們希望在寫和讀之間建立一種序,即我們需要定義一個序模型,依照該模型,程式設計師能推斷他們程式的執行結果及其正確性。這個模型就是存儲同一性。

一個完整的一致性模型包括髙速快取一致性及存儲同一性兩個方面,且這兩個是互補的:高速快取一致性定義了對同一個存儲地址進行的讀寫操作行為,而存儲同一性模型定義了訪問所有存儲地址的讀寫行為。在共享存儲空間中,多個進程對存儲的不同單元做並發的讀寫操作,每個進程都會看到一個這些操作被完成的序。一個存儲同一性模型規定了對這種序的若干約束,值得一提的是,這裡所涉及到的並發存儲操作既包括對相同單元的,也包括對不同單元的;即可以來自同一進行,也可以來自不同的進程。在這個意義上,存儲同一性包含了高速快取一致性。

實現

高速快取一致性協定是解決快取一致性問題的主要方案,同時也是保證存儲同一性的重要手段。它定義了共享快取塊在各個私有快取中的存在形式,並詳細定義了各個私有快取之間的通信行為。學術界及工業界已經提出了多種高速快取一致性協定模型,但所有模型的出發點都是一樣的,它們都是為了保證存儲模型SWMR(single-writer,multiple-reader)屬性,即對於一個給定的快取塊,在系統運行的任意時刻,保證(1)同時只能有一個處理器核擁有對此快取的寫許可權;或者(2)同時可以有零個或者多個處理器核擁有對此快取塊的讀許可權。根據共享數據的修改方式的不同,可以將髙速快取一致性協定的實現分為兩種形式:寫無效協定、寫更新協定。其中,在寫無效協定中,處理器核在對某個存儲塊進行寫操作之前,必須保證當前的處理器核擁有對此快取塊的讀寫權。如果兩個或者多個處理器核試圖同時訪問同一個數據項並執行寫操作,那么它們中同時只能有一個在進行,另一個訪問請求會被阻塞;在某個處理器執行寫操作時,其它所有私有快取中該數據的副本都會被置為無效狀態。在當前處理器完成寫操作後,後續的對此數據的所有操作,都必須首先獲得此新寫入數據的副本。因此,寫無效型的協定強制執行了寫操作的串列化。寫更新協定也稱為寫廣播協定,它是指處理器核在對某個數據進行寫操作時,同時更新當前數據在其它所有快取中的數據副本。

有兩種主要的快取一致性協定:基於偵聽形式的高速快取一致性協定(或偵聽協定)及基於目錄結構的高速快取一致性協定(或目錄協定)。在這兩種協定中,偵聽協定的實現依賴於一個匯流排或者類匯流排形式的網路連線,使用此網路,單個處理器核的私有快取所發出的所有請求會被廣播到系統中所有的其它處理器核的私有快取中,而所有處理器的訪問請求也可以在此匯流排上進行定序操作,以實現快取一致性模型及存儲同一性模型中對訪存序的要求。此外,此協定還可以通過匯流排結構來很好的處理對同一數據塊的多個衝突請求,而且多個處理器的私有快取之間可以通過此匯流排結構進行直接的通信,減少了通信延遲。但是,由於所有請求都是通過匯流排來進行傳輸的,但匯流排頻寬資源有限,因此它會影響整個系統的擴展性。目錄協定則是釆用一個目錄結構來實現對快取塊的管理的。在目錄協定中,處理器核的私有快取發出的訪存請求,會首先傳送到擁有相應快取塊的目錄結構中,此目錄結構中記錄了當前快取塊的共享情況,目錄結構控制器會根據當前快取塊的狀態,選取回響此請求或者轉發此請求到其它相應的私有快取中。此種方法不需要依賴於特定拓撲結構的網路,並通過點對點的直接通信形式降低了網路中的頻寬消耗,因此這種協定易於擴展。但由於此協定的實現中,所有請求都必須通過目錄結構進行處理,因此會引入額外的延遲 。

MESI協定

編輯

單核Cache中每個Cache line有2個標誌:dirty和valid標誌,它們很好的描述了Cache和Memory(記憶體)之間的數據關係(數據是否有效,數據是否被修改),而在多核處理器中,多個核會共享一些數據,MESI協定就包含了描述共享的狀態。

在MESI協定中,每個Cache line有4個狀態,可用2個bit表示,它們分別是:

M(Modified):這行數據有效,數據被修改了,和記憶體中的數據不一致,數據只存在於本Cache中。

E(Exclusive):這行數據有效,數據和記憶體中的數據一致,數據只存在於本Cache中。

S(Shared):這行數據有效,數據和記憶體中的數據一致,數據存在於很多Cache中。

I(Invalid):這行數據無效。

在該協定的作用下,雖然各cache控制器隨時都在監聽系統匯流排,但能監聽到的只有讀未命中、寫未命中以及共享行寫命中三種情況。讀監聽命中的有效行都要進入S態並發出監聽命中指示,但M態行要搶先寫回主存;寫監聽命中的有效行都要進入I態,但收到RWITM時的M態行要搶先寫回主存。總之監控邏輯並不複雜,增添的系統匯流排傳輸開銷也不大,但MESI協定卻有力地保證了主存塊髒拷貝在多cache中的一致性,並能及時寫回,保證cache主存存取的正確性 。

相關詞條

熱門詞條

聯絡我們