一種弱一致性存儲模型的數據訪存系統和方法

2023-04-28 20:19:01

專利名稱：一種弱一致性存儲模型的數據訪存系統和方法
技術領域：
本發明涉及共享存儲系統數據存取技術領域，特別是涉及片上網絡(Network on Chip,N0C)共享存儲中的存儲一致性模型(Memory consistent model)和緩存(cache) — 致性協議(Cache coherent protocol)的數據存取技術領域，尤其是涉及一種針對無數據競爭(Data Race Free, DRF)程序的基於弱一致性模型的無目錄緩存(cache) —致性協議的數據訪存系統和方法。
背景技術：
隨著現代多核共享存儲系統的研究發展，現有技術中存在多種存儲一致性模型(Memory consistent model)共享存儲系統，包括順序一致性模型Sequential Consistency)共享存儲系統等。存儲一致性模型描述的是程序在執行過程中存儲操作正確性的問題。存儲操作包括讀操作和寫操作，每一操作又可以用兩個時間點界定發出(Invoke)和響應 (Response)。在假定沒有流水線的情況下(即單個處理器內指令的執行是按順序執行的)， 設系統內共有N個處理器，每個處理器可發出<n^N)個存儲操作(讀或寫)，那麼
總共有/ . 種可能的執行順序。存儲一致性模型描述的就是這些操作可能的執行
Ili…Γ ■
順序中那些是正確的。存儲一致性通過限制訪存事件的次序來保證並行程序在共享存儲系統中的正確執行，即讀操作應該獲得該次操作之前最近一次對數據的寫更新，寫操作對數據的修改能被隨後的讀操作看到。順序一致性模型共享存儲系統被普遍認為是判斷一個並行執行是否正確的標準， 在該模型中，任一處理器都嚴格按照訪存指令在進程中出現的次序執行訪存指令，且在當前訪存指令徹底完成之前不能開始執行下條訪存指令。但是順序一致性對於程序的限制過於嚴格，導致系統性能不好，在實際系統中很少用到，為了放鬆對訪存事件發生次序的限制，人們提出很多限制更弱的一致性，其中最為常用的一種是弱一致性(Weak Consistency)模型共享存儲系統。該模型共享存儲系統要求用同步操作把對於共享數據的訪問保護起來。弱一致性保證同步操作的執行滿足順序一致性條件；普通訪存不能越過同處理器中先於該訪存的同步操作執行；同步操作的執行需要等待所有在同處理器中先於該同步操作的普通訪存操作完成。弱一致性模型共享存儲系統允許同步訪存之間的普通訪存操作以任意次序執行。緩存(Cache)用於降低系統的訪存延遲，在共享存儲系統中佔有重要地位。在多處理器中存在緩存(cache) —致性問題，為了保證同一地址在不同私有緩存(cache)以及共享緩存(cache)中的多個備份保持數據一致，人們提出了若干緩存(cache) —致性方法 (Cache-coherent protocol)0緩存(Cache) —致性方法的本質是把某個處理器新寫的值傳播給其他處理器以確保處理器看到一致的共享存儲內容，是對某種存儲一致性模型的具體實現。廣泛使用的一致性方法包括基於目錄的緩存(cache) —致性方法(目錄方法)和基於偵聽總線的無目錄方法(偵聽方法)。在基本的緩存(cache) —致性方法中，緩存(cache)的每一行都有四種狀態，即無效狀態(INV)、共享狀態(SHD)、獨佔狀態(EXC)及修改狀態(MOD)。緩存(Cache)的無效狀態(INV)表示該行數據無效，處理器的讀寫操作都不命中；緩存(cache)行處於共享狀態(SHD)表明可能有多個處理器擁有該行數據的有效備份；緩存(cache)行處於獨佔狀態(EXC)說明這是該緩存(cache)行唯一的有效備份；處於修改狀態(MOD)的緩存(cache)行表明該數據行已被某個處理器改寫。基於目錄的緩存(cache) —致性方法在共享緩存(cache)的每行都保存一個目錄項，該目錄項記錄所有當前持有此行備份的處理器號以及此行是否已被改寫等信息。當一個處理器想要對一緩存(cache)行進行寫操作且可能引起數據不一致時，它會主動根據目錄的內客立即通過片上網絡(Network on Chip，N0C)向持有此行數據備份的處理器發出無效或更新信號，從而防止其他想要讀寫該數據的處理器訪問到舊的備份數據，引起數據不一致的問題。基於偵聽總線的無目錄方法在一個處理器對共享數據的訪存失效或可能引起數據不一致時，通過總線廣播該事件給系統中的所有處理器，當其他處理器中的緩存(cache) 包含該共享數據備份時，則根據偵聽到的廣播採取相應的維護一致性的行動，對本緩存 (cache)中的備份無效或者向總線更新數據。在程序中主要包括私有數據和共享數據。私有數據只有一個線程能對其進行訪存操作，因而保持該數據的目錄是無意義的，浪費了存儲空間；共享數據可以由多個處理器進行訪存操作，並且可能存在多個備份。兩個來自不同處理器的對同一共享數據進行的訪存操作同時發生，並且其中至少有一個是寫操作的情況稱之為數據競爭(data race)。存在數據競爭的程序其執行常常具有不確定性，可能無法按照期望正確運行。因而一種方法是並行程序中不允許數據競爭的存在，其通過在兩個對於同一共享數據的訪存操作之間加上同步操作使其互斥來消除潛在的數據競爭，從而實現無數據競爭(DRF)程序的數據訪存。但是，基於目錄的緩存(cache) —致性方法所需的目錄存儲器容量隨著系統中處理器數目的增大而迅速提升，當處理器很多時，實現目錄方法的開銷變得很大，導致緩存 (cache)的利用率降低；其次，該方法會隨著每次寫操作通過片上網絡(NOC)向所有擁有該數據備份的處理器發出無效或更新操作，而其中大量操作並非必要的，這些額外的通信開銷增加了片上網絡(NOC)的負擔，影響系統性能；此外，維護目錄信息的複雜性也嚴重限制了系統的可擴展性。而基於偵聽總線的無目錄方法雖然簡單有效，避免了目錄的存儲開銷，但是由於它需要廣播，因而只適用於可擴展性差的共享總線結構；並且同樣存在通信開銷過大，嚴重影響系統性能的問題。

發明內容
本發明的目的在於針對無數據競爭(DRF)程序的數據訪存而提供一種弱一致性存儲模型的數據訪存系統和方法，其有效避免了偵聽方法只能基於共享總線結構的缺陷， 同時減少了目錄方法中龐大的片上網絡(NOC)通信開銷，防止了目錄方法所帶來的存儲空間的浪費，增強了系統的可擴展性。為實現本發明目的而提供的一種弱一致性存儲模型的數據訪存系統，包括至少兩個處理器，與所述每個處理器連接的包括至少一作為私有緩存的第一緩存層，以及至少一作為共享緩存的第二緩存層，所述第一緩存層通過片上網絡與所述第二緩存層連接；所述片上網絡，包括一致性訪存控制模塊、請求應答模塊，其中所述一致性訪存控制模塊，用於在處理器間進行訪存操作時，控制所述私有緩存和共享緩存在不同訪存請求下的狀態轉換；所述請求應答模塊，用於通過片上網絡在所述私有緩存和共享緩存之間傳遞狀態轉換的請求和應答數據包。較優地，所述第一緩存層的數據結構包括數據域、標籤域和狀態位；所述第二緩存層的數據結構包括數據域、標籤域、狀態位和獨佔域；所述獨佔域，用於標記獨佔該緩存行數據的處理器號。較優地，所述第一緩存層或第二緩存層的狀態位的狀態為無效狀態，或者共享狀態，或者私有狀態。較優地，所述狀態轉換的請求和應答數據包，包括讀失效、寫失效、替換、共享讀、 獨佔寫、應答、同步請求和應答數據包中的一種。較優地，所述一致性訪存控制模塊包括初始化模塊，用於在系統初始化時，對多個處理器第一緩存層和第二緩存層的各行狀態進行復位，全部設置為無效狀態；並且所有第二緩存層行的獨佔域值都為表示無獨佔處理器的預設值。為實現本發明目的還提供一種弱一致性存儲模型數據訪存方法，在由多個處理器連接的包括至少一作為私有緩存的第一緩存層，通過片上網絡與至少一作為共享緩存的第二緩存層之間進行緩存一致性訪存操作，包括如下步驟在多個處理器間進行訪存操作時，控制所述私有緩存和共享緩存在不同訪存請求下的狀態轉換的步驟；以及；通過片上網絡(NOC)在所述私有緩存和共享緩存之間傳遞狀態轉換的請求和應答數據包的步驟。較優地，所述的弱一致性存儲模型數據訪存方法，還包括初始化步驟系統初始化時，對多個處理器第一緩存層和第二緩存層的各行狀態進行復位，全部設置為無效狀態，並且所有第二緩存層行的獨佔域值都為表示無獨佔處理器的預設值。較優地，所述狀態轉換的請求和應答數據包，包括讀失效、寫失效、替換、共享讀、 獨佔寫、應答、同步請求和應答數據包中的一種，其中所述讀失效請求是由第一緩存層發給第二緩存層的請求，表示在該處理器的第一緩存層發生了讀失效，需要從第二緩存層讀數據；
所述寫失效請求是由第一緩存層發給第二緩存層的請求，表示在該處理器的第一緩存層發生了寫失效，包括對處於無效狀態或共享狀態緩存行的寫操作；替換請求當處理器向第二緩存層發出替換請求時，用於替換第二緩存層中的一緩存行，若該緩存行處於私有狀態，則先根據獨佔域從獨佔者處理器的第一緩存層取回該緩存行的最新備份，並將獨佔者處理器置為無效狀態，然後把第二緩存層中的最新數據寫回處理器的主存，把第二緩存層的緩存行置為無效狀態；或者，當處理器只對第一緩存層中的緩存行進行替換時，若該緩存行處於私有狀態，則先把最新備份寫回第二緩存層，並將第二緩存層的相應行由私有狀態置為共享狀態，獨佔域值改為所述表示無獨佔處理器的預設值，然後將第一緩存層相應行狀態位置為無效狀態；當對第一緩存層或第二緩存層中處於無效狀態或者共享狀態的緩存行進行替換時，只需將其狀態位統一置為無效即可，無其他特別操作；共享讀請求是由第二緩存層發向獨佔域中處理器號所標記的處理器的請求，表示此時有其他處理器要對該數據進行讀操作；獨佔寫請求是由第二緩存層發給獨佔域中處理器號所標記的處理器的請求，表示此時有其他處理器要對該數據進行寫操作，其中包含需要改寫的數據包；應答是對於請求的應答，其中包含緩存行中的數據；同步同步操作。較優地，所述狀態轉換，包括如下步驟當第一緩存層設置處於無效狀態時，表明該行數據無效，對其的訪存操作產生第一緩存層失效，處理器轉發該訪存操作到第二緩存層；當第一緩存層設置處於共享狀態時，表明該行數據在其他處理器的第一緩存層中還存在備份，對其的讀操作產生第一緩存層命中，對其的寫操作產生第一緩存層失效並轉發該訪存操作到第二緩存層，到同步信號點時，該緩存行狀態由共享狀態變為無效狀態；當第一緩存層設置處於私有狀態時，表明該行數據由本處理器第一緩存層獨佔， 對其的讀寫訪存操作都會產生第一緩存層命中；當收到獨佔寫請求時，根據請求中的數據包更新緩存行，發送應答並修改狀態位為共享狀態；當收到共享讀請求時，只發送應答不改變狀態；當收到替換請求時，發送應答給第二緩存層並置狀態位為無效狀態，並且第二緩存層相應緩存行狀態由私有狀態變為共享狀態，獨佔域值改為所述表示無獨佔處理器的預設值；當第二緩存層設置處於無效狀態時，表明該行數據無效，對其的訪存操作產生第二緩存層失效，轉發該操作到處理器的主存的訪存隊列，此時獨佔域值為所述表示無獨佔處理器的預設值；如果訪存為讀操作，從處理器的主存中取回數據後狀態位變為共享狀態， 獨佔域值保持為所述表示無獨佔處理器的預設值不變；如果訪存為寫操作，從主存中取回數據並根據寫操作做相應修改後，狀態位變為私有狀態，獨佔域值改為發送該寫操作的處理器號；當第二緩存層設置處於共享狀態時，表明該行數據可能在多個處理器的第一緩存層中存在備份，不被任何第一緩存層獨佔，此時獨佔域值為所述表示無獨佔處理器的預設值；如果訪存為讀操作，產生第二緩存層命中，狀態位及獨佔域值都保持不變；如果訪存為寫操作，產生第二緩存層命中，狀態位變為私有狀態，獨佔域值改為發送該寫請求的處理器號；當第二緩存層設置處於私有狀態，表明有且僅有一個處理器的第一緩存層獨佔該行數據，獨佔域值為該處理器號，對其的讀寫訪存操作都會產生第二緩存層命中；如果訪存為讀操作，第二緩存層發送共享讀請求給獨佔者處理器，並且轉發獨佔者處理器返回的應答給發送讀操作的請求者處理器；如果訪存為寫操作，第二緩存層發送獨佔寫請求給獨佔者處理器，其中包含新的數據包，並且轉發獨佔者處理器返回的應答給發送寫操作的請求者處理器，然後獨佔域值更新為該請求者處理器的處理器號；如果第二緩存層收到替換請求，第二緩存層發送替換請求給相應獨佔者處理器，等待隨後由獨佔者處理器發送的應答並更新相應數據，將數據寫回處理器的主存，狀態位設置為失效，獨佔域值置為所述表示無獨佔處理器的預設值；如果第二緩存層收到獨佔者處理器第一緩存層被替換時發來的應答數據包，根據數據包更新數據，狀態位設置為共享狀態，獨佔域值置為所述表示無獨佔處理器的預設值。本發明的有益效果是本發明的一種弱一致性存儲模型的數據訪存系統和方法， 避免了基於偵聽總線的無目錄方法(偵聽方法)只能基於共享總線結構的缺陷，適用於可擴展性更高的基於片上網絡(NOC)的分布式系統；消除了基於目錄的緩存(cache) —致性方法(目錄方法)所帶來的存儲空間的浪費，提高了緩存(cache)利用率；並且由於其不需要發出大量對數據備份的無效請求或者向總線發出廣播，減少了片上網絡(NOC)的通信開銷，有效提升了系統性能。其實現起來簡單有效，更有利於系統的擴展。


圖1為本發明實施例的弱一致性存儲模型的數據訪存系統結構示意圖；圖2為本發明實施例的一級緩存(Li cache)行結構示意圖；圖3為本發明實施例的二級緩存(L2 cache)行結構示意圖；圖4為本發明實施例的一級緩存(Li cache)狀態轉化示意圖；圖5為本發明實施例的二級緩存(L2 cache)狀態轉化示意圖；圖6為本發明實施例以無數據競爭(DRF)程序段為例實現弱一致性存儲模型的數據訪存過程示意圖。
具體實施例方式為了使本發明的目的、技術方案及優點更加清楚透徹，以下結合附圖及實施例，對本發明的一種弱一致性存儲模型的數據訪存系統和方法進行進一步詳細說明。應當理解， 此處所描述的具體實施例僅僅用以解釋本發明，並不用於限定本發明。如圖1所示，本發明實施例的一種弱一致性存儲模型數據訪存系統，包括至少兩個處理器1，與所述每個處理器1連接的包括至少一作為私有緩存的第一緩存層2，以及至少一作為共享緩存的第二緩存層4，所述第一緩存層2通過片上網絡(NOC) 3與所述第二緩存層4連接。所述片上網絡3，包括一致性訪存控制模塊31、請求應答模塊32，其中所述一致性訪存控制模塊31，用於在處理器1間進行訪存操作時，控制所述私有緩存和共享緩存在不同訪存請求下的狀態轉換；
請求應答模塊32，用於在所述私有緩存和共享緩存之間傳遞狀態轉換的請求和應答數據包。所述一致性訪存控制模塊31設置或者改寫所述作為私有緩存的第一緩存層2和 /或作為共享緩存的第二緩存層4的狀態，並通過請求應答模塊32將請求和應答數據包傳遞給其他緩存層或者其他處理器的其他緩存層，並由所述一致性訪存控制模塊31控制根據所述請求和應答數據包設置或者改寫所述私有緩存或者共享緩存的狀態從而實現緩存一致性；較佳地，其中，如圖2所示，所述第一緩存層的數據結構保持不變，同現有技術中一樣，其仍然包括數據域(Data)、標籤域(Tag)和狀態位(State)；如圖3所示，所述第二緩存層的數據結構除包括數據域(Data)，標籤域(Tag)和狀態位(State)外，還包括一獨佔域(owner)；所述獨佔域(owner)，用於標記獨佔該緩存行數據的處理器號(reqid)；本發明的實施例中，預先設置了一個與各處理器號不同的數值表示沒有獨佔緩存行數據的處理器。較佳地，在本發明實施例中，預設「 -1」表示無獨佔處理器。較佳地，在本發明實施例中，作為一種可實施方式，所述第一緩存層或第二緩存層的狀態位(State)的狀態為無效狀態(INV)，或共享狀態(SHD)，或私有狀態(OWN)。所述狀態轉換的請求和應答數據包，包括讀失效(RD)、寫失效(WR)、替換(REPL)、 共享讀(RD_SHD)、獨佔寫(WR_0WN)、應答(ACK_DATA)、同步(SYNC)請求和應答數據包中的一種。較佳地，本發明實施例的弱一致性存儲模型數據訪存系統，所述一致性訪存控制模塊31還包括初始化模塊33，用於在系統初始化時，對多個處理器第一緩存層和第二緩存層的各行狀態進行復位，全部設置為無效狀態；並且所有第二緩存層行的獨佔域(owner) 值都為「-1 」，表示無獨佔處理器。下面詳細說明本發明實施例的弱一致性存儲模型數據訪存系統工作過程。在本發明實施例中，作為一種可實施方式，將第一緩存層設為一級緩存(Level 1 Cache, Ll Cache)；將第二緩存層設為二級緩存((Level 2 Cache, L2 cache)進行說明。作為一種可實施方式，本發明實施例的弱一致性存儲模型數據訪存系統，其共享數據緩存一致性訪存包括請求和應答數據包的傳遞以及私有緩存(cache)和共享緩存 (cache)在不同訪存請求下的狀態轉換。為方便描述說明，本發明實施例以P0，Pl兩個處理器，且包含一級緩存(Li cache)和二級緩存(L2 cache)兩級結構對本發明具體實施方式
進行描述，但是其並不是對本發明保護範圍的限制。顯然，本發明也可以擴展到包含更多處理器以及更多緩存(cache)層次結構的系統裡，例如在一個包含三層緩存(cache)結構的系統中一般一級緩存(Li cache)和二級緩存(L2 cache)都為各處理器的私有緩存 (cache)，三級緩存(L3 cache)為共享緩存(cache)，在這種情況下二級緩存(L2 cache)實際上是一級緩存(Li cache)的擴展，其實現方式與本發明實施例中的一級緩存作為第一緩存層的結構沒有太大差別，因此不在此具體說明，但是都應該視為包含在本發明保護範疇裡。在本發明實施例中，作為一種可實施方式，以兩層緩存(cache)結構作為例子來說明本發明實施例無數據競爭程序的共享數據緩存一致性訪存系統，其中一級緩存(Llcache)為私有緩存(cache)，二級(Level 2，L2)緩存(cache)為共享緩存(cache)。顯然，本發明也可以擴展到更多層次的緩存(cache)結構中。對於由同步操作保證的無數據競爭(DRF)程序，在兩個同步點間對同一共享數據的訪存操作包括兩種情況1)只有一個處理器讀寫該數據(至少一個寫操作)，則在此期間該數據實際上可視為只被本處理器佔有的私有數據，稱這個處理器為獨佔者(owner)處理器，用reqid表示其處理器號；2)兩個同步點間沒有處理器對該數據進行寫操作，但是有多個處理器會對此數據進行讀操作，則該數據視為共享數據。本發明在二級緩存(L2 cache)行中取消了用於保存目錄的數據域，增加獨佔域 (owner)作為一標記位，用於標記獨佔該緩存行數據的處理器號(reqid)。其相比於傳統的基於目錄的緩存(cache) —致性方法，由於每個緩存(cache)行只需要保存一個擁有者，從而大大降低了存儲開銷，提高了緩存(cache)利用率。同時由於當存在對共享數據的寫操作時，可以確信在下個同步點之前沒有其他處理器會訪問該數據，因此，沒必要像目錄方法一樣在每次寫操作時都主動向其他擁有該數據備份的處理器發送無效或更新請求，或者如偵聽方法一樣在每次可能引起數據不一致時都向總線廣播該事件，從而大大降低了片上網絡(NOC)的通信開銷。由於寫操作不再發送無效或更新請求，各處理器無法知道一級緩存 (Li cache)中處於共享狀態(SHD)的數據在同步期間是否被其他處理器修改，為了保證正確性，作為一種可實施方式，本發明實施例中，處理器在每個同步點將一級緩存(Li cache) 中的處於共享狀態(SHD)緩存(cache)行改為無效狀態(INV)，由於各處理器可以主動採取措施來維護一致性，避免了偵聽方法需要時刻偵聽總線廣播並採取相應行動的缺點。在本發明中，一級緩存(Li cache)的結構保持不變，仍然包含數據域(Data)，標籤域(Tag)和狀態位(State) ；二級緩存(L2 cache)的結構比一級緩存(Li cache)多一個獨佔域(owner)標記位。一級緩存(Li cache)和二級緩存(L2 cache)的結構分別如圖 2，圖3所示。本發明實施例中還提供一種弱一致性存儲模型數據訪存方法，其由多個處理器連接的包括至少一作為私有緩存的第一緩存層，通過片上網絡與至少一作為共享緩存的第二緩存層之間進行緩存一致性訪存操作。包括如下步驟在多個處理器間進行訪存操作時，控制所述私有緩存和共享緩存在不同訪存請求下的狀態轉換的步驟；以及；通過片上網絡(NOC)在所述私有緩存和共享緩存之間傳遞狀態轉換的請求和應答數據包的步驟。較佳地，本發明實施例的弱一致性存儲模型數據訪存方法，還包括初始化步驟系統初始化時，對多個處理器第一緩存層和第二緩存層的各行狀態進行復位，全部設置為無效狀態，並且所有第二緩存層行的獨佔域(owner)值都為「_1」，表示無獨佔處理器。系統初始化時，對處理器P0，處理器Pl的一級緩存(Li cache)和二級緩存 (L2cache)的各行狀態進行復位，全部設置為無效狀態(INV)，並且所有二級緩存(L2 cache)行的獨佔(owner)域值都為「_1」。
較佳地，作為一種可實施方式，本發明實施例中，通過請求和應答數據包通過片上網絡(NOC)在一級緩存(Li cache)和二級緩存(L2 cache)間傳遞狀態轉換數據。所述狀態轉換的請求和應答數據包，包括讀失效(RD)、寫失效(WR)、替換(REPL)、 共享讀(RD_SHD)、獨佔寫(WR_0WN)、應答(ACK_DATA)、同步(SYNC)請求和應答數據包，其中讀失效(RD)請求由一級緩存(Li cache)發給二級緩存(L2 cache)的請求，表示在該處理器的一級緩存(Li cache)發生了讀失效，需要從二級緩存(L2 cache)讀數據；寫失效(WR)請求由一級緩存(Li cache)發給二級緩存(L2 cache)的請求，表示在該處理器的一級緩存(Li cache)發生了寫失效，包括對處於無效狀態(INV)或共享狀態(SHD)緩存行的寫操作；替換(REPL)請求當處理器向二級緩存(L2 cache)發出替換請求(Mplace) 時，用於替換二級緩存(L2 cache)中的一緩存(cache)行，若該緩存(cache)行處於私有狀態(OWN)，則先根據獨佔域(owner)從獨佔者處理器的一級緩存(Li cache)取回該緩存(cache)行的最新備份，並將獨佔者處理器置為無效狀態(INV)，然後把二級緩存(L2 cache)中的最新數據寫回處理器的主存(未示出)，把二級緩存(L2 cache)行置為無效狀態(INV)；或者，當處理器只對一級緩存(Li cache)的緩存(cache)行進行替換(Mplace) 時，若該緩存(cache)行處於私有狀態，則先把最新數據備份寫回二級緩存(L2 cache)，並將二級緩存(L2 cache)的相應行由私有狀態(OWN)置為共享狀態(SHD)，獨佔域值改為 「_1」，然後將一級緩存(Li cache)相應行狀態位置為無效狀態(INV)；當對一級緩存(Li cache)或二級緩存(L2 cache)中處於無效狀態(INV)或者共享狀態(SHD)的緩存(cache) 行進行替換(replace)時，只需將其狀態位統一置為無效(INV)即可，無其他特別操作；共享讀(RD_SHD)請求由二級緩存(L2 cache)發向獨佔域(owner)中處理器號 (reqid)所標記的處理器的請求，表示此時有其他處理器要對該數據進行讀操作；獨佔寫(WR_0WN)請求由二級緩存(L2 cache)發給獨佔域(owner)中處理器號 (reqid)所標記的處理器的請求，表示此時有其他處理器要對該數據進行寫操作，其中包含需要改寫的數據包(Data)；應答(ACK_DATA)對於請求的應答，其中包含緩存(cache)行中的數據；同步(SYNC)同步操作。在本發明實施例中，作為一種可實施方式，所述緩存(cache)的狀態位(Mate)的狀態為無效狀態(INV)，共享狀態(SHD)，私有狀態(OWN)。所述狀態轉換，包括如下步驟當一級緩存(Li cache)設置處於無效狀態(INV)時，表明該行數據無效，對其的訪存操作產生一級緩存(Li cache)失效，處理器轉發該訪存操作到二級緩存(L2 cache)；當一級緩存(Li cache)設置處於共享狀態(SHD)時，表明該行數據在其他處理器的一級緩存(Li cache)中還存在備份，對其的讀操作產生一級緩存(Li cache)命中，對其的寫操作產生一級緩存(Li cache)失效並轉發該訪存操作到二級緩存(L2 cache)，到同步信號點時，該緩存(cache)行狀態由共享狀態(SHD)變為無效狀態(INV)；當一級緩存(Li cache)設置處於私有狀態(OWN)時，表明該行數據由本處理器一級緩存(Li cache)獨佔，對其的讀寫訪存操作都會產生一級緩存(Li cache)命中。當收到
12獨佔寫(WR_0WN)請求時，根據請求中的數據包更新緩存(cache)行，發送應答(ACK_DATA) 並修改狀態位為共享狀態(SHD)；當收到共享讀(RD_SHD)請求時，只發送應答(ACK_DATA) 不改變狀態；當收到替換(REPL)請求時，發送應答(ACK_DATA)給二級緩存(L2 cache)並置狀態位為無效狀態(INV)，並且二級緩存(L2 cache)相應緩存(cache)行狀態由私有狀態(OWN)變為共享狀態(SHD)，獨佔域(owner)值改為「_1」；當二級緩存(L2 cache)設置處於無效(INV)狀態時，表明該行數據無效，對其的訪存操作產生二級緩存(L2 cache)失效，轉發該操作到處理器的主存(未示出)的訪存隊列，此時獨佔(owner)域值為「_1」。如果訪存為讀操作，從處理器的主存中取回數據後狀態位變為共享狀態(SHD)，獨佔域(owner)值保持為「_1」不變；如果訪存為寫操作，從主存中取回數據並根據寫操作做相應修改後，狀態位變為私有狀態(OWN)，獨佔域(owner)值改為發送該寫操作的處理器號(reqid)；當二級緩存(L2 cache)設置處於共享(SHD)狀態時，表明該行數據可能在多個處理器的一級緩存(Li cache)中存在備份，不被任何一級緩存(Li cache)獨佔，此時獨佔域 (owner)值為「_1」。如果訪存為讀操作，產生二級緩存(L2 cache)命中，狀態位及獨佔域 (owner)值都保持不變；如果訪存為寫操作，產生二級緩存(L2 cache)命中，狀態位變為私有狀態(0WN)，獨佔域(owner)值改為發送該寫請求的處理器號(reqid)；當二級緩存(L2 cache)設置處於私有狀態(OWN)，表明有且僅有一個處理器的一級緩存(Li cache)獨佔該行數據，獨佔域(owner)值為該處理器號(reqid)，對其的讀寫訪存操作都會產生二級緩存(L2 cache)命中。如果訪存為讀操作，二級緩存(L2CaChe) 發送共享讀(RD_SHD)請求給獨佔者處理器，並且轉發獨佔者處理器返回的應答(ACK_ DATA)給發送讀操作的請求者處理器；如果訪存為寫操作，二級緩存(L2 cache)發送獨佔寫(WR_0WN)請求給獨佔者處理器，其中包含新的數據包，並且轉發獨佔者處理器返回的應答(ACK_DATA)給發送寫操作的請求者處理器，然後獨佔域(owner)值更新為該請求者處理器的處理器號(reqid)；如果二級緩存(L2 cache)收到替換請求(REPL)，二級緩存(L2 cache)發送替換請求(REPL)給相應獨佔者處理器，等待隨後由獨佔者處理器發送的應答 (ACK_DATA)並更新相應數據，將數據寫回處理器主存，狀態位設置為失效(INV)，獨佔域值置為「_1」；如果二級緩存(L2 cache)收到獨佔者處理器一級緩存Ll cache)被替換時發來的應答(ACK_DATA)數據包，根據數據包更新數據，狀態位設置為共享狀態(SHD)，獨佔 (owner)域值置為「_1」。一級緩存(Li cache)和二級緩存(L2 cache)在本發明中的狀態轉換分別如圖4， 圖5所示。作為一種可實施方式，在寫數據假共享時，由於一個緩存(cache)行往往包含多個數據，因此可能存在多個處理器同時對同一個緩存(cache)行的不同數據進行並不衝突的訪存操作。該情況在本發明實施例中已經考慮到並且已經得到解決。在一個同步區間， 如果一個處理器對一個緩存(cache)行進行寫操作，發現此時二級緩存(L2 cache)已經處於私有狀態(0WN)，並且獨佔者(owner)是另一個處理器，由於程序已經保證無數據競爭 (DRF)，在一個同步區間裡不可能有多個處理器對同一數據進行寫操作，可以判定此時發生了寫數據假共享。本發明實施例中，所述二級緩存(L2 cache)把新寫的數據合併到之前處理器號(reqid)所指的處理器的一級緩存(Li cache)中，並在其一級緩存(Li cache)中將狀態修改為共享狀態(SHD)，然後在二級緩存(L2 cache)中將獨佔者(owner)域改為新的處理器號(reqid)，並返回從前一個獨佔者(owner)處理器處帶回的數據給新的獨佔者(owner) 處理器。數據假共享是指兩個或多個被不同處理器訪問的內容恰好是在存儲器的同一塊， 使得幾個處理器雖沒有真正共享數據，卻共享同一存儲塊。下面以圖6所示無數據競爭(DRF)程序段為例，進一步詳細說明本發明的一種無數據競爭程序的共享數據緩存一致性訪存系統和方法的實現。在弱一致性模型數據訪存系統中，允許同步操作之間的普通訪存操作以任意次序執行，作為一種可實施方式，本發明實施例以無數據競爭(DRF)程序的緩存(Cache) —致性訪存實現本發明實施例的弱一致性存儲模型數據訪存系統，保證無數據競爭(DRF)程序的正確執行。在弱一致性存儲模型數據訪存系統中，通過區分同步操作和普通訪存操作，用同步操作把對於共享數據的訪問保護起來，以保證多個處理器對於寫共享數據的訪問是互斥的，實現無數據競爭(DRF)程序的共享數據的訪存。系統初始化時，對處理器P0，處理器Pl的一級緩存(Li cache)和二級緩存 (L2cache)的各行狀態進行復位，全部設置為無效狀態(INV)，並且所有二級緩存(L2 cache)行的獨佔(owner)域值都為「_1」。無數據競爭程序運行一段時間後，緩存(cache)各行中存儲著處於各種狀態的數據。設地址a在圖6所示程序段之前由處理器Pl獨佔，則地址a在處理器PO的一級緩存(Li cache)的狀態位是無效狀態(INV)；在處理器Pl的一級緩存(Li cache)的狀態位是私有狀態(OMN)，在二級緩存(L2 cache)中的狀態位為私有狀態(OMN)，獨佔域(owner) 值為「 1 」，表示獨佔者為處理器Pl。設處理器PO在同步點SYNCl後對地址a進行寫操作(store)，在此期間處理器 Pl不會對地址a進行任何訪存；由於在處理器PO中此時地址a處於無效狀態(INV)，發生處理器PO的一級緩存(Li cache)寫失效(WR)，則轉發寫失效請求(WR)到二級緩存(L2 cache) ；二級緩存(L2 cache)處於私有狀態(OMN)，寫操作命中，二級緩存(L2 cache)根據獨佔域(owner)值(reqid)轉發獨佔寫(WR_0WN)請求給處理器P1，其中包括處理器PO 對地址a所寫的數據；處理器Pl收到獨佔寫(WR_0WN)請求，將獨佔寫(WR_0WN)中的數據包與自己之前所寫數據進行合併後返回應答(ACK_DATA)，並將狀態由私有狀態(OWN)改為共享狀態(SHD) ；二級緩存(L2 cache)收到處理器Pl的應答(ACK_DATA)後轉發該應答給處理器P0，把獨佔域(owner)中的處理器號(reqid)改為「0」，表示現在獨佔者為處理器PO，狀態位保持私有狀態(OWN)不變；處理器PO收到應答(ACK_DATA)後，發生一級緩存 (Li cache)寫命中，將地址a的數據更新，狀態變為私有狀態(OWN)，處理器PO對地址a的寫(store)操作完成。設地址b在圖6所示無數據競爭程序段處於共享狀態(SHD)，則地址b在處理器 P0，處理器Pl以及二級緩存(L2 cache)中的狀態位都處於共享狀態(SHD)，且二級緩存(L2 cache)的獨佔域(owner)值為「_1 」，沒有獨佔者。
在同步點SYNCl和SYNC2之間沒有處理器對地址b進行寫操作，可以有多個處理器對其進行讀操作(load)。由於在處理器P0，處理器Pl中地址b處於共享狀態(SHD)，都發生讀命中，狀態位不變，二級緩存(L2 cache)的獨佔域(owner)值保持「_1」，處理器P0， 處理器Pl對地址b的讀操作(load)完成。設地址c在同步點SYNC2之前處於共享狀態(SHD)，按現有技術，由於在每個同步點處理器會無效各自一級緩存(Li cache)中處於共享狀態(SHD)的數據，則在同步點 SYNC2後地址c在處理器P0、處理器Pl的一級緩存(Li cache)中都處於無效狀態(INV)， 在二級緩存(L2 cache)中地址c的狀態位為共享狀態(SHD)，獨佔域(owner)值為「_1」， 表示沒有獨佔者。由於在處理器P0，處理器Pl中地址c處於無效狀態(INV)，發生一級緩存(Li)讀失效(RD)，轉發讀失效(RD)請求給二級緩存(L2 cache) ；二級緩存(L2 cache)中地址b處於共享狀態(SHD)，發生讀命中，返回應答(ACK_DATA)給處理器PO和處理器P1，狀態位和獨佔域(owner)保持不變；處理器P0，處理器Pl收到應答(ACK_DATA)，讀命中，地址c的狀態由無效狀態(INV)變為共享狀態(SHD)，處理器P0，處理器Pl對地址c的讀操作(load) 完成。同步點SYNC2之後處理器PO對地址b進行了寫操作，此時在處理器PO的一級緩存(Li cache)中，地址b由於處理器自身在同步點對處於共享狀態(SHD)數據的無效操作，處於無效狀態(INV)，發生一級緩存(Li cache)寫失效(WR)請求，轉發寫失效(WR)請求給二級緩存(L2 cache) ；二級緩存(L2 cache)中地址b處於共享狀態(SHD)，發生寫命中，按照寫失效(WR)請求中的數據包修改數據，狀態變為私有狀態(0WN)，並根據發送寫失效(WR)請求的處理器號(reqid)修改獨佔域(owner)值為0 ；處理器PO修改一級緩存(Li cache)中地址b的數據，狀態位變為私有狀態(0WN)，處理器PO對地址b的寫操作(store) 完成。同步點SYNC2之後處理器Pl對地址a進行了讀操作，此時地址a在處理器Pl中處於無效狀態(INV)，發生一級緩存(Li cache)讀失效請求(RD)，轉發讀失效請求(RD)給二級緩存(L2 cache) ；二級緩存(L2 cache)中地址a處於私有狀態(0WN)，獨佔域(owner) 值為「0」，發生讀命中，二級緩存(L2 cache)發送共享讀(RD_SHD)請求給獨佔者處理器PO ； 處理器PO收到共享讀(RD_SHD)請求，返回包含最新數據的應答(ACK_DATA)，狀態位保持私有狀態(OWN)不變；二級緩存(L2 cache)收到處理器PO發送的應答(ACK_DATA)，轉發給處理器P1，不修改狀態位和獨佔域(owner)值；處理器Pl收到應答(ACK_DATA)，由於無數據競爭(DRF)的保證，在下個同步點之前不會有其他處理器對地址a進行寫操作，狀態位置為共享狀態(SHD)，可以多次讀寫，處理器Pl對地址a的讀操作(load)完成。以上只是本發明的部分實例，實際還有很多情況沒有在此一一列舉，但是都應視為本發明的一部分。本發明的實施例的弱一致性存儲模型的數據訪存系統和方法，避免了基於偵聽總線的無目錄方法(偵聽方法)只能基於共享總線結構的缺陷，適用於可擴展性更高的基於片上網絡(NOC)的分布式系統；消除了基於目錄的緩存(cache) —致性方法(目錄方法) 所帶來的存儲空間的浪費，提高了緩存(cache)利用率；並且由於其不需要發出大量對數據備份的無效請求或者向總線發出廣播，減少了片上網絡(NOC)的通信開銷，有效提升了
15系統性能。 最後應當說明的是，很顯然，本領域的技術人員可以對本發明進行各種改動和變型而不脫離本發明的精神和範圍。這樣，倘若本發明的這些修改和變型屬於本發明權利要求及其等同技術的範圍之內，則本發明也意圖包含這些改動和變型。
權利要求
1.一種弱一致性存儲模型的數據訪存系統，包括至少兩個處理器，與所述每個處理器連接的包括至少一作為私有緩存的第一緩存層，以及至少一作為共享緩存的第二緩存層， 所述第一緩存層通過片上網絡與所述第二緩存層連接；其特徵在於所述片上網絡，包括一致性訪存控制模塊、請求應答模塊，其中所述一致性訪存控制模塊，用於在處理器間進行訪存操作時，控制所述私有緩存和共享緩存在不同訪存請求下的狀態轉換；所述請求應答模塊，用於在所述私有緩存和共享緩存之間傳遞狀態轉換的請求和應答數據包。
2.根據權利要求1所述的弱一致性存儲模型的數據訪存系統，其特徵在於，所述第一緩存層的數據結構包括數據域、標籤域和狀態位；所述第二緩存層的數據結構包括數據域、標籤域、狀態位和獨佔域；所述獨佔域，用於標記獨佔該緩存行數據的處理器號。
3.根據權利要求2所述的弱一致性存儲模型的數據訪存系統，其特徵在於，所述第一緩存層或第二緩存層的狀態位的狀態為無效狀態，或者共享狀態，或者私有狀態。
4.根據權利要求3所述的弱一致性存儲模型的數據訪存系統，其特徵在於，所述狀態轉換的請求和應答數據包，包括讀失效、寫失效、替換、共享讀、獨佔寫、應答、同步請求和應答數據包中的一種。
5.根據權利要求3或4所述的弱一致性存儲模型的數據訪存系統，其特徵在於，所述一致性訪存控制模塊還包括初始化模塊，用於在系統初始化時，對多個處理器第一緩存層和第二緩存層的各行狀態進行復位，全部設置為無效狀態；並且所有第二緩存層行的獨佔域值都為表示無獨佔處理器的預設值。
6.一種弱一致性存儲模型數據訪存方法，在由多個處理器連接的包括至少一作為私有緩存的第一緩存層，通過片上網絡與至少一作為共享緩存的第二緩存層之間進行緩存一致性訪存操作，其特徵在於，包括如下步驟在多個處理器間進行訪存操作時，控制所述私有緩存和共享緩存在不同訪存請求下的狀態轉換的步驟；以及；在所述私有緩存和共享緩存之間傳遞狀態轉換的請求和應答數據包的步驟。
7.根據權利要求6所述的弱一致性存儲模型數據訪存方法，其特徵在於，還包括初始化步驟系統初始化時，對多個處理器第一緩存層和第二緩存層的各行狀態進行復位，全部設置為無效狀態，並且所有第二緩存層行的獨佔域值都為表示無獨佔處理器的預設值。
8.根據權利要求6或7所述的弱一致性存儲模型數據訪存方法，其特徵在於，所述狀態轉換的請求和應答數據包，包括讀失效、寫失效、替換、共享讀、獨佔寫、應答、同步請求和應答數據包中的一種，其中所述讀失效請求是由第一緩存層發給第二緩存層的請求，表示在該處理器的第一緩存層發生了讀失效，需要從第二緩存層讀數據；所述寫失效請求是由第一緩存層發給第二緩存層的請求，表示在該處理器的第一緩存層發生了寫失效，包括對處於無效狀態或共享狀態緩存行的寫操作；所述替換請求當處理器向第二緩存層發出所述替換請求時，用於替換第二緩存層中的一緩存行，若該緩存行處於私有狀態，則先根據獨佔域從獨佔者處理器的第一緩存層取回該緩存行的最新備份，並將獨佔者處理器置為無效狀態，然後把第二緩存層中的最新數據寫回處理器的主存，把第二緩存層的緩存行置為無效狀態；或者，當處理器只對第一緩存層中的緩存行進行替換時，若該緩存行處於私有狀態，則先把最新備份寫回第二緩存層，並將第二緩存層的相應行由私有狀態置為共享狀態，獨佔域值改為所述表示無獨佔處理器的預設值，然後將第一緩存層相應行狀態位置為無效狀態；當對第一緩存層或第二緩存層中處於無效狀態或者共享狀態的緩存行進行替換時，只需將其狀態位統一置為無效即可，無其他特別操作；所述共享讀請求是由第二緩存層發向獨佔域中處理器號所標記的處理器的請求，表示此時有其他處理器要對該數據進行讀操作；所述獨佔寫請求是由第二緩存層發給獨佔域中處理器號所標記的處理器的請求，表示此時有其他處理器要對該數據進行寫操作，其中包含需要改寫的數據包； 所述應答是對於請求的應答，其中包含緩存行中的數據； 所述同步同步操作。
9.根據權利要求8所述的弱一致性存儲模型數據訪存方法，其特徵在於，所述狀態轉換，包括如下步驟當第一緩存層設置處於無效狀態時，表明該行數據無效，對其的訪存操作產生第一緩存層失效，處理器轉發該訪存操作到第二緩存層；當第一緩存層設置處於共享狀態時，表明該行數據在其他處理器的第一緩存層中還存在備份，對其的讀操作產生第一緩存層命中，對其的寫操作產生第一緩存層失效並轉發該訪存操作到第二緩存層，到同步信號點時，該緩存行狀態由共享狀態變為無效狀態；當第一緩存層設置處於私有狀態時，表明該行數據由本處理器第一緩存層獨佔，對其的讀寫訪存操作都會產生第一緩存層命中；當收到獨佔寫請求時，根據請求中的數據包更新緩存行，發送應答並修改狀態位為共享狀態；當收到共享讀請求時，只發送應答不改變狀態；當收到替換請求時，發送應答給第二緩存層並置狀態位為無效狀態，並且第二緩存層相應緩存行狀態由私有狀態變為共享狀態，獨佔域值改為所述表示無獨佔處理器的預設值；當第二緩存層設置處於無效狀態時，表明該行數據無效，對其的訪存操作產生第二緩存層失效，轉發該操作到處理器的主存的訪存隊列，此時獨佔域值為所述表示無獨佔處理器的預設值；如果訪存為讀操作，從處理器的主存中取回數據後狀態位變為共享狀態，獨佔域值保持為所述表示無獨佔處理器的預設值不變；如果訪存為寫操作，從主存中取回數據並根據寫操作做相應修改後，狀態位變為私有狀態，獨佔域值改為發送該寫操作的處理器號；當第二緩存層設置處於共享狀態時，表明該行數據可能在多個處理器的第一緩存層中存在備份，不被任何第一緩存層獨佔，此時獨佔域值為所述表示無獨佔處理器的預設值；如果訪存為讀操作，產生第二緩存層命中，狀態位及獨佔域值都保持不變；如果訪存為寫操作，產生第二緩存層命中，狀態位變為私有狀態，獨佔域值改為發送該寫請求的處理器號； 當第二緩存層設置處於私有狀態時，表明有且僅有一個處理器的第一緩存層獨佔該行數據，獨佔域值為該處理器號，對其的讀寫訪存操作都會產生第二緩存層命中；如果訪存為讀操作，第二緩存層發送共享讀請求給獨佔者處理器，並且轉發獨佔者處理器返回的應答給發送讀操作的請求者處理器；如果訪存為寫操作，第二緩存層發送獨佔寫請求給獨佔者處理器，其中包含新的數據包，並且轉發獨佔者處理器返回的應答給發送寫操作的請求者處理器，然後獨佔域值更新為該請求者處理器的處理器號；如果第二緩存層收到替換請求， 第二緩存層發送替換請求給相應獨佔者處理器，等待隨後由獨佔者處理器發送的應答並更新相應數據，將數據寫回處理器的主存，狀態位設置為失效，獨佔域值置為「_1」；如果第二緩存層收到獨佔者處理器第一緩存層被替換時發來的應答數據包，根據數據包更新數據， 狀態位設置為共享狀態，獨佔域值置為所述表示無獨佔處理器的預設值。
全文摘要
本發明公開一種弱一致性存儲模型的數據訪存系統和方法。該數據訪存系統包括至少兩個處理器，與所述每個處理器連接的包括至少一作為私有緩存的第一緩存層，以及至少一作為共享緩存的第二緩存層，所述第一緩存層通過片上網絡與所述第二緩存層連接；所述片上網絡包括一致性訪存控制模塊，用於在處理器間進行訪存操作時，控制所述私有緩存和共享緩存在不同訪存請求下的狀態轉換；請求應答模塊，用於通過片上網絡在所述私有緩存和共享緩存之間傳遞狀態轉換的請求和應答數據包。其有效避免了偵聽方法只能基於共享總線結構的缺陷，同時減少了目錄方法中龐大的片上網絡(NOC)通信開銷，防止了目錄方法所帶來的存儲空間的浪費，增強了系統的可擴展性。
文檔編號G06F12/08GK102591800SQ201110460579
公開日2012年7月18日 申請日期2011年12月31日 優先權日2011年12月31日
發明者劉道福, 張戈, 王磊, 郭崎, 陳雲霽 申請人:龍芯中科技術有限公司