實施高速緩存一致性的系統和方法
2023-05-01 20:22:16 2
專利名稱：實施高速緩存一致性的系統和方法
技術領域：
本發明涉及高速緩存一致性(Cache coherence)機制，並且尤 其涉及利用基於環的偵測響應收集(ring-based snoop response collection )在基於網絡的多處理器系統中的高速緩存一致性。
背景技術：
對稱多處理器("SMP")系統採用高速緩存一致性機制以確保 高速緩存一致性。基於偵測的高速緩存一致性是實現SMP系統的高速 緩存一致性的典型方案。利用基於偵測的高速緩存一致性，當高速緩 存缺失(Cache Miss)發生時，請求高速緩存向其對等的高速緩存廣 播高速緩存請求。適當的高速緩存偵測過濾機制用於減少由高速緩存 一致性消息和高速緩存偵測操作造成的開銷。通常，在基於總線的 SMP系統中實現基於偵測的高速緩存一致性，在該SMP系統中高速緩 存經由共享總線互相通信。為避免潛在的通信瓶頸，現代SMP系統通 常使用消息傳遞網絡，而不是在物理上共享的總線。此類SMP系統被 稱為基於網絡的SMP系統。
現在參照圖l，示出了一個示例性高速緩存一致性多處理器系統，
其包括經由節點間互連網絡互連的多個節點，其中每個節點包括中央
處理單元("CPU")和高速緩存。同樣連接到該節點間互連網絡上的
是存儲器和輸入/輸出("IO")設備。雖然存儲器被描述成一個部件，
但是存儲器可被物理地分成多個存儲器部分，其中每個存儲器部分在 操作上與節點相關。
現在參照圖2，示出了另一個示例性高速緩存一致性多處理器系 統，其包括經由節點間互連網絡互連的多個節點，其中每個節點包括 晶片多處理器("CMP")子系統。每個CMP子系統包括一個或多個能夠經由節點內結構互相通信的高速緩存。存儲器部分，以及輸入/ 輸出設備也可被連接到節點內結構上。
利用基於偵測的高速緩存一致性，當讀取高速緩存缺失發生時， 請求高速緩存通常向其對等高速緩存和存儲器廣播高速緩存數據請 求。當對等高速緩存收到高速緩存數據請求時，該對等高速緩存執行 本地高速緩存偵測操作，並且產生表明是否在對等高速緩存中找到所 請求的數據，以及相應高速緩存管線的狀態的高速緩存偵測響應。如 果在對等高速緩存中找到所請求的數據，則對等高速緩存可經由高速 緩存至高速緩存傳送向請求高速緩存提供數據。如果沒有對等高速緩 存能夠提供數據，則存儲器負責提供所請求的數據。
在高速緩存一致性SMP系統中，高速緩存請求可以是旨在獲得所 請求數據的共享拷貝的高速緩存數據請求、旨在獲得所請求數據的排 它拷貝(exclusive c叩y)的高速緩存數據和所有權請求、或旨在使其它 高速緩存中的所請求數據的共享拷貝無效的所有權請求。
用於獲得基於偵測的高速緩存一致性的若干技術為本領域技術 人員所熟知。例如，MESI偵測高速緩存一致性協議及其變型已被廣 泛地用於SMP系統中。正如名稱所暗示的，MESI具有4個高速緩存狀 態修改(M)、排它(E)、共享(S)以及無效(1)。如果高速緩存管線 在高速緩存中處於無效狀態，則數據在高速緩存中不是有效的。如果 高速緩存管線在高速緩存中處於共享狀態，則數據在高速緩存中有 效，並且在其它高速緩存中也可能有效。例如，當從存儲器或另一個 高速緩存中檢索數據時，進入該狀態，並且相應的偵測響應表明數據 在至少一個其它高速緩存中有效。如果高速緩存管線在高速緩存中處 於排它狀態，則數據在該高速緩存中有效，並且在任何其他高速緩存 中不能有效。此外，相對於保存在存儲器中的數據，該數據尚未被修 改。例如，當從存儲器或另一個高速緩存中檢索數據時，進入該狀態， 並且相應的偵測響應表明該數據在任何其他高速緩存中都不是有效 的。如果高速緩存管線在高速緩存中處於修改狀態，則數據在高速緩 存中有效，並且在任何其他高速緩存中不可能有效。此外，作為存儲
器存儲操作的結果，該數據已被修改，並且修改的數據尚未被寫入存
儲器o
利用基於偵測的高速緩存一致性，當高速緩存缺失發生時，如果 在存儲器和另一個高速緩存中都找到所請求的數據，因為高速緩存至 高速緩存傳送等待時間通常小於存儲器訪問等待時間，所以通常優選
經由高速緩存至高速緩存傳送提供數據。例如，在IBM⑧Power 4系統 中，當一個地址的數據在多晶片模塊中的一個或多個高速緩存中共享 時，具有最後收到的共享拷貝的高速緩存可經由高速緩存至高速緩存 傳送給相同多晶片模塊中的另 一 個高速緩存提供數據。
如果最初從高速緩存產生高速緩存請求，則該高速緩存被稱為高 速緩存請求的請求高速緩存。如果在給高速緩存請求提供服務過程中 需要偵測高速緩存，則該高速緩存被稱為高速緩存請求的偵測高速緩 存。如果高速緩存提供所請求數據給請求高速緩存，則該高速緩存被 稱為高速緩存請求的供給高速緩存。
同樣，如果最初從節點中的高速緩存產生高速緩存請求，則該節 點被稱為高速緩存請求的請求節點。如果在給高速緩存請求提供服務 過程中，需要偵測節點中的至少一個高速緩存，則該節點被稱為高速 緩存請求的偵測節點。如果節點中的高速緩存提供所請求數據給請求 節點，則該節點被稱為高速緩存請求的供給節點。
在基於總線的SMP系統中，總線充當中央仲裁器，其將所有總線 事務序列化，以確保總線事務的全部順序。在基於網絡的SMP系統中， 可以於不同的接收高速緩存以不同順序接收消息。該一致性消息的序 列化保證的缺乏使得難以提供有效的高速緩存一致性支持。因此，存 在對於在基於網絡的多處理器系統中能夠有效地支持高速緩存一致 性的機制的需要。
發明內容
根據本發明的一個實施例，一種用於實施高速緩存一致性的計算 機實現的方法包括通過網絡無需排序限制地從請求節點多播對於存
儲器地址的高速緩存請求，通過嵌入所述網絡中的單向環，由該請求 節點收集高速緩存請求的組合偵測響應，以及根據該組合偵測響應在 請求節點處實施存儲器地址的高速緩存一致性。
才艮據本發明的一個實施例，高速緩存一致性系統包括通過網絡連 接的多個節點，所述網絡包括嵌入的單向環，以及實現該系統的高速 緩存一致性的高速緩存一致性機制，其中所述高速緩存一致性機制無 需任何排序限制地利用網絡傳送對於存儲器地址的高速緩存請求，並 且利用嵌入的單向環收集高速緩存請求的組合偵測響應。
根據本發明的一個實施例，提供一種計算機可讀介質，其包含了 由處理器可執行的指令，該指令用來執行用於實施高速緩存一致性的
方法。該方法包括通過網絡無需排序限制地從請求節點多播對於存 儲器地址的高速緩存請求，通過嵌入所述網絡中的單向環，由該請求 節點收集高速緩存請求的組合偵測響應，以及根據該組合偵測響應在 請求節點處實施存儲器地址的高速緩存一致性。
參照附圖，下面將更詳細地描述本公開的優選實施例 圖l描述了示例性高速緩存一致多處理器系統，其包括經由節點
間互連網絡互連的多個節點，其中每個節點包括CPU和高速緩存。 圖2描述了示例性高速緩存一致多處理器系統，其包括經由節點
間互連網絡互連的多個節點，其中每個節點包括CMP子系統，該CMP
子系統包括一個或多個高速緩存。
圖3示出了圖解請求節點如何處理到來的數據請求的流程圖。 圖4示出了圖解請求節點如何處理到來的數據和所有權請求的流程圖。
圖5示出了圖解請求節點如何處理到來的所有權請求的流程圖。 圖6示出了圖解偵測節點如何處理到來的高速緩存請求的流程圖。
圖7示出了圖解偵測節點如何處理高速緩存請求的到來的部分組
合偵測響應(PCSR)的流程圖。
圖8示出了圖解偵測節點如何利用一致性沖突檢測支持處理到來 的高速緩存請求的流程圖。
圖9示出了圖解偵測節點如何利用一致性沖突檢測支持處理到來 的PCSR的流程圖。
圖10示出了圖解當使用偵測過濾時偵測節點如何利用偵測列表 處理到來的PCSR的流程圖。
圖ll示出了根據本發明的一個實施例的計算機系統節點的圖。
具體實施例方式
根據本公開的一個實施例，利用基於環的偵測響應收集實現基於 網絡的多處理器系統中的高速緩存一致性。高速緩存一致性機制通過 沒有任何排序限制地利用多處理器系統的互連網絡，同時利用嵌入互 連網絡中的單向環來收集高速緩存偵測響應，多播高速緩存請求。
高速緩存一致系統包括經由互連網絡彼此連接的多個節點。互連 網絡邏輯上包括請求網絡、響應網絡和數據網絡。請求網絡被用於高 速緩存請求傳送，響應網絡被用於高速緩存偵測響應傳送，而數據網 絡被用於所有其它傳送，包括高速緩存至高速緩存數據傳送以及高速 緩存與存儲器之間的數據傳送。雖然邏輯上互相獨立，但是請求網絡、 響應網絡和數據網絡在物理上可以共享通信管腳和連結。
對於指定的存儲器地址，響應網絡包括被用於傳送高速緩存偵測 響應的單向環。假設相同存儲器地址的高速緩存偵測響應使用相同單 向環，那麼不同的存儲器地址(通常以高速緩存管線粒度)可將嵌入所 述網絡中的不同的單向環用於高速緩存偵測響應。
對於指定的高速緩存請求的偵測節點，如果在嵌入的單向環中節 點在偵測節點前面，則該節點被稱為在前節點。如果在嵌入的單向環 中節點在偵測節點之後，則該節點被稱為後續節點。如果在嵌入的單 向環中偵測節點在請求節點之後，則該高速緩存請求的偵測節點被稱 為第一偵測節點。如果在單向環互連網絡中請求節點在偵測節點之
後，則該高速緩存請求的偵測節點被稱為最後偵測節點。
當偵測高速緩存執行高速緩存偵測操作時，偵測高速緩存產生表 明高速緩存偵測結果的高速緩存偵測響應。如果高速緩存偵測響應表 明僅在 一個偵測節點處本地高速緩存偵測操作的結果，則該高速緩存
偵測響應被稱為本地偵測響應(LSR)。如果高速緩存偵測響應表明 在一個或更多偵測節點處本地高速緩存偵測操作的結果，則該高速緩 存偵測響應被稱為部分組合的偵測響應(PCSR)。如果高速緩存偵 測響應表明在高速緩存請求的所有偵測節點處本地高速緩存偵測操 作的結果，則該高速緩存偵測響應被稱為組合偵測響應(CSR)。此 外，如果高速緩存偵測響應表明偵測節點能夠給請求節點提供所請求
數據，則該高速緩存偵測響應被稱為正偵測響應；如果高速緩存偵測
響應表明沒有偵測節點能夠給請求節點提供所請求數據，則該高速緩
存偵測響應被稱為負偵測響應。
根據本公開的說明性實施例，當存儲器地址的高速緩存缺失在請 求節點中發生時，該請求節點沒有任何排序限制地向利用請求網絡的 所有偵測節點發出正確的高速緩存請求。如果需要所請求數據，則一
旦收到所請求的數據，無論相應的CSR是否被接收，該請求節點在其 計算中能夠使用所請求的數據。當請求節點收到CSR和所請求的數據 (如果有的話)時，其完成給高速緩存請求提供服務。
當偵測節點從請求節點接收高速緩存請求時，偵測節點執行本地 高速緩存偵測操作以產生LSR;以及如果來自在前節點的在前PCSR 已被接收和記錄，則根據高速緩存請求的LSR和在前PCSR計算新的 PCSR,或者如果高速緩存請求的在前PCSR尚未被接收，則為了後面 的使用記錄LSR。偵測節點需要確定是否利用嵌入的單向環向後續節 點轉發新的PCSR，或者記錄新的PCSR (以及稍後轉發它)。
當偵測節點從在前節點接收到高速緩存請求的在前PCSR時，如 果已經產生和記錄了 LSR，則偵測節點根據高速緩存請求的在前 PCSR和先前記錄的LSR計算新的PCSR，或者如果尚未產生LSR，則 為了以後的使用記錄在前的PCSR。偵測節點需要確定是否利用嵌入
的單向環向後續節點轉發新的PCSR，或者記錄新的PCSR (以及稍後 轉發它)。
為計算高速緩存請求的新PCSR，偵測節點使用以下方法如果 在前PCSR指示數據尚未被提供給請求節點(負PCSR)，以及LSR指 示數據尚未被提供給請求節點(負LSR)，則新的PCSR指示數據尚 未被提供給請求節點(負PSCR)。另一方面，如果在前PCSR或者LSR 中的任意一個指示請求數據已被提供給請求節點(正PCSR或正 LSR)，則新的PCSR指示數據已被提供給請求節點(正PCSR)。
當高速緩存缺失在請求節點中的高速緩存中發生時，請求節點可 接收數據請求、數據和所有權請求、或所有權請求。偵測節點可接收 高速緩存請求或PCSR。現在示出如何利用基於環的偵測響應收集， 在高速緩存一致多處理器系統中處理此類請求和偵測響應。
(l)數據請求的處理(在請求節點處)
圖3示出了圖解當高速緩存缺失在請求節點中的請求高速緩存中 發生時，請求節點如何處理到來的數據請求的流程圖。當請求節點從 請求高速緩存收到高速緩存數據請求時(300)，請求節點利用請求 網絡向偵測節點發送高速緩存數據請求(301)，以及利用響應網絡向高 速緩存請求的第一偵測節點發送高速緩存請求的初始(負)PCSR (302 )。利用響應網絡，從請求節點向第一偵測節點發送的高速緩 存數據請求可與初始PCSR—起搭栽(piggyback)。請求節點等待從 供給節點接收所請求的數據，或等待從高速緩存請求的最後偵測節點 接收高速緩存請求的CSR (303 )。偵測節點檢查偵測節點是否已收 到所請求的數據或高速緩存請求的CSR (304)。
如果偵測節點已經從供給節點收到所請求的數據，則請求節點在 請求高速緩存中緩存接收的數據(305)，並且等待從最後偵測節點 接收高速緩存請求的CSR (306)。當從最後偵測節點收到高速緩存 請求的CSR時，請求節點將請求高速緩存狀態正確地設置成結束高速 緩存請求服務(307 )。
如果請求節點已經從高速緩存請求的最後偵測節點收到高速緩
存請求的CSR，則請求節點檢查高速緩存請求的CSR是否為正或負 (308)。如果高速緩存請求的CSR為正，則請求節點等待從供給節 點接收所請求的數據(309)。當從供給節點收到所請求的數據時， 請求節點在請求高速緩存中緩存接收的數據，並且將請求高速緩存狀 態正確地設置成結束高速緩存請求服務(310)。否則，如果高速緩存請 求的CSR為負，則請求節點向存儲器發送數據請求(311)，並且等待從 存儲器中接收所請求的數據(312)。當請求節點從存儲器中收到所 請求的數據時，請求節點在請求高速緩存中緩存接收的數據，並且將 請求高速緩存狀態正確地設置成結束高速緩存數據請求服務(313)。
(2)數據和所有權請求的處理(在請求節點處)
圖4示出了圖解當高速緩存缺失在請求節點中的請求高速緩存中 發生時，請求節點如何處理到來的數據和所有權請求的流程圖。當請 求節點從請求高速緩存收到高速緩存數據和所有權請求時(400 )， 請求節點利用請求網絡向偵測節點發送高速緩存數據和所有權請求 (401)，以及利用響應網絡向高速緩存請求的第一偵測節點發送高速緩 存請求的初始(負)PCSR (402)。利用響應網絡，從請求節點向第一 偵測節點發送的高速緩存數據和所有權請求可與初始PCSR—起搭 載。請求節點等待從供給節點接收所請求的數據，或等待從最後偵測 節點接收高速緩存請求的CSR (403)。請求節點檢查其是否已經從 供給節點收到所請求的數據，或者從最後偵測節點收到高速緩存請求 的CSR( 404)'
如果請求節點已經從供給節點收到所請求的數據，則請求節點在 請求高速緩存中緩存接收的數據(405)，並且等待從最後偵測節點 接收高速緩存請求的CSR (406)。當從最後偵測節點收到高速緩存 請求的CSR時，請求節點將請求高速緩存狀態正確地設置成結束高速 緩存請求服務(407 )。
如果請求節點已經從最後偵測節點收到高速緩存請求的CSR，則 請求節點檢查高速緩存請求的CSR是否為正或負(408)。如果高速 緩存請求的CSR為正，則請求節點等待從供給節點接收所請求的數據
U09)。當從供給節點收到所請求的數據時，請求節點在請求高速 緩存中緩存接收的數據，並且將請求高速緩存狀態正確地設置成結束 高速緩存數據和所有權請求服務(410)。否則，如果高速緩存請求的 CSR為負，則請求節點向存儲器發送數據請求(411)，並且等待從存儲 器中接收所請求的數據(412)。當請求節點從存儲器中收到所請求的數 據時，請求節點在請求高速緩存中緩存接收的數據，並且將請求高速 緩存狀態正確地設置成結束高速緩存數據和所有權請求服務(413)。
(3) 所有權請求的處理(在請求節點處)
圖5示出了圖解當高速緩存缺失在請求節點中的請求高速緩存中 發生時，請求節點如何處理到來的所有權請求的流程圖。當請求節點 從請求高速緩存收到高速緩存所有權請求時(500)，節點利用請求 網絡向對等(偵測)節點發送所有權請求(501)，以及利用響應網絡向 高速緩存請求的第一偵測節點發送高速緩存請求的初始(負)PCSR (502 )。利用響應網絡，從請求節點向第一偵測節點發送的高速緩 存所有權請求可與初始PCSR—起搭栽。請求節點等待從高速緩存請 求的最後偵測節點接收高速緩存請求的CSR( 503 )。當收到高速緩存 請求的CSR時，請求節點將請求高速緩存狀態正確地設置成結束高速 緩存請求服務(504 )。
(4) 高速緩存請求的處理(在偵測節點處)
圖6示出了圖解偵測節點如何處理到來的高速緩存請求的流程 圖。當偵測節點從請求節點接收高速緩存請求時(600),偵測節點 執行本地高速緩存偵測操作，產生指示所請求的數據是否應當由偵測 節點提供給請求節點的高速緩存請求的LSR,以及如果高速緩存請求 的LSR指示應當提供所請求的數據，則利用數據網絡向請求節點提供 數據(601)。偵測節點檢查是否從在前節點收到高速緩存請求的在 前PCSR(602)。如果收到高速緩存請求的在前PCSR,則偵測節點 基於高速緩存請求的在前PCSR和高速緩存請求的LSR，產生高速緩 存請求的新PCSR (603)。偵測節點利用響應網絡向後續節點轉發高 速緩存請求的新PCSR (603 )。否則，如果沒有收到高速緩存請求的 在前PCSR，則偵測節點為了未來處理記錄高速緩存請求的 LSR( 604 )。
(5) PCSR的處理(在偵測節點處)
圖7示出了圖解偵測節點如何處理到來的PCSR的流程圖。當偵測 節點從在前節點收到高速緩存請求的在前PCSR時(700)，偵測節點 檢查偵測節點處是否有可用的高速緩存請求的LSR (701)。如果存 在可用的高速緩存請求的LSR，則偵測節點基於從在前節點接收的高 速緩存請求的在前PCSR，以及高速緩存請求的可用LSR，產生高速 緩存請求的新PCSR ( 702 )。偵測節點利用響應網絡向後續節點轉發 高速緩存請求的新PCSR (702)。否則，如果偵測節點處沒有可用的 高速緩存請求的LSR，則偵測節點為了未來處理記錄從在前節點接收 的高速緩存請求的在前PCSR( 703 )。
一致性沖突檢測支持
當不止一個節點同時發出關於相同地址的高速緩存請求時，一致 性衝突可能發生。需要適當的衝突處理以確保系統為高速緩存一致 的，以及能夠正向前進。現在示出偵測節點如何利用合適的沖突檢測 支持來處理高速緩存請求和在前PCSR。
根據本公開的說明性實施例，每個節點都保存PCSR向量，其中 PCSR向量的每個位對應於請求節點，其指示是否已收到來自相應請 求節點的高速緩存請求的PCSR，以及是否尚未將該PCSR用於計算新 PCSR。此外，每個節點都保存LSR向量，其中LSR向量的每個位對 應於請求節點，其指示來自相應請求節點的高速緩存請求的LSR是否 已被產生，以及是否尚未利用該LSR來計算新PCSR。此外，每個節 點保存DRN(數據接收節點)信息，其指示請求節點(如果有約話)已 經有所請求數據了 ，其中PCSR向量指示相應的PCSR已被收到並且尚 未被用於計算新PCSR，或者LSR向量指示相應的LSR已被產生並且 尚未被用於計算新PCSR。
對於偵測節點，我們用概念PCSI^V ( r )來表示針對請求節點r， 由請求節點r發出的高速緩存請求的PCSR是否已被偵測節點接收，並
且尚未被偵測節點用於產生要轉發到後續節點的新PCSR。如果 PCSR—V(r)表明可用(AVAILABLE)，則來自請求節點r的高速緩 存請求的PCSR已被偵測節點接收，並且尚未被用於產生新PCSR。如 果PCSR—V ( r )表明不可用(UNAVAILABLE)，則來自請求節點r 的高速緩存請求的PCSR尚未被偵測節點接收，或者來自請求節點的 高速緩存請求的PCSR已被偵測節點接收，並且已被用於產生新 PCSR。最初，針對系統中的每個請求節點，PCSR向量表明不可用。 對於偵測高速緩存，我們用概念LSR一V ( r )來表示針對請求高速 緩存r,由請求節點r發出的高速緩存請求的LSR是否已被偵測節點產 生，並且尚未被偵測節點用於產生要轉發到後續節點的新PCSR。如 果LSRJS^ ( r )表明可用，則來自請求節點r的高速緩存請求的LSR已 被偵測節點產生，並且尚未被用於產生新PCSR。如果LSI^V(r)表 明不可用，則來自請求節點r的高速緩存請求的LSR尚未被偵測節點產 生，或者來自請求節點r的高速緩存請求的LSR已被偵測節點產生，並 且已被用於產生新PCSR。最初，針對系統中的每個請求節點，LSR
向量表明不可用。
對於偵測節點，我們用概念DRN來表示已經給其提供有請求數 據的請求節點r，其中PCSRJV^(r)表明可用，或者LSR—V ( r )表明可 用。DRN的初值為無。
(6)利用一致性衝突檢測處理高速緩存請求(在偵測節點處)
圖8示出了圖解偵測節點如何利用一致性衝突檢測支持處理到來 的高速緩存請求的流程圖。當偵測節點從請求節點r接收高速緩存請 求時(800 )，偵測節點執行本地高速緩存偵測操作，並且產生高速 緩存請求的LSR，其指示所請求的數據是否應當由偵測節點提供給請 求節點(801)。偵測節點檢查高速緩存請求的LSR是否指示所請求 的數據已由偵測節點提供給請求節點(802)。
如果高速緩存請求的LSR指示所請求的數據已由偵測節點提供 給請求節點，則偵測節點利用數據網絡將數據提供給請求節點 r( 803)。偵測節點檢查PCSR—V(r)是否為可用(804)。如果PCSR—V (r )為可用，則偵測節點基於從在前節點接收的高速緩存請求的 PCSR，以及高速緩存請求的LSR,產生高速緩存請求的新PCSR,並 且利用響應網絡將新PCSR轉發給後續節點(805 )。偵測節點清除 PCSR—V(r)以指示不可用(806)。否則，如果PCSR—V(r)為不可 用，則偵測節點為了未來處理而記錄高速緩存請求的LSR( 807 )，並 且將LSR—V ( r )設置成指示可用，並且將DRN設置成r( 808 )。
如果高速緩存請求的LSR指示所請求的數據未被偵測節點提供 給請求節點，則偵測節點檢查PCSR—V(r)是否為可用(809)。如果 PCSR一V ( r )為不可用，則偵測節點為了未來處理而記錄高速緩存請 求的LSR( 819 )，並且將LSR一V ( r )設置成指示可用(820 )。如果 PCSR_V ( r )為可用，則偵測節點檢查DRN是否被設置成r( 810 )。
如果DRN被設置成r,則偵測節點基於從在前節點接收的高速緩 存請求的PCSR和高速緩存請求的LSR，產生高速緩存請求的新 PCSR ，利用響應網絡將高速緩存請求的新PCSR轉發給後續節點 (811)，以及清除PCSR—V ( r )以指示不可用(812)。對於每個節 點k，如果PCSR—V(k)指示可用，以及LSR—V(k)指示可用，則偵測節 點基於相應記錄的PCSR和相應記錄的LSR產生新PCSR，利用響應網 絡將新PCSR轉發給後續節點，以及清除PCSR一V(k)和LSR一V(k)以指 示不可用(813)。
如果DRN未被設置成r，則偵測節點檢查DRN是否指示沒有請求 節點要接收數據(814)。如果沒有請求節點要接收數據，則偵測節 點基於從在前節點接收的高速緩存請求的PCSR和高速緩存請求的 LSR,產生高速緩存請求的新PCSR,利用響應網絡將高速緩存請求 的新PCSR轉發給後續節點(815),以及清除PCSR—V( r )以指示不 可用(816)。否則，如果有任意節點要接收數據，則為了未來處理 而記錄高速緩存請求的LSR(817)，並且將LSF^V (r)設置成指示可 用(818)。
(7)利用一致性衝突檢測處理PCSR (在偵測節點處)
圖9示出了圖解偵測節點如何利用一致性衝突檢測支持處理高速
緩存請求的到來的PCSR的流程圖。當偵測節點從在前節點接收高速 緩存請求的PCSR時(900)，偵測節點檢查從在前節點接收的高速緩 存請求的PCSR是否指示數據已被提供給請求節點(901)。
如果從在前節點接收的高速緩存請求的PCSR指示數據已被提供 給請求節點，則偵測節點檢查LSR-V ( r )是否為可用(卯2)。如果 LSR一V ( r )為可用，則偵測節點基於從在前節點接收的高速緩存請求 的PCSR，以及高速緩存請求的LSR，產生高速緩存請求的新PCSR， 並且利用響應網絡將高速緩存請求的新PCSR轉發給後續節點(903 )。 偵測節點清除LSRJV(r)以指示不可用(卯4)。否則，如果LSR_V (r )為不可用，則偵測節點為了未來處理而記錄從在前節點接收的高 速緩存請求的PCSR(905)，並且將PCSI^V(r)設置成指示可用，以 及將DRN設置成r(卯6 )。
如果從在前節點接收的高速緩存請求的PCSR指示數據未被提供 給請求節點，則偵測節點檢查LSF^V ( r )是否為可用(卯7)。如果 LSR—V ( r )為不可用，則偵測節點為了未來處理而記錄從在前節點接 收的高速緩存請求的PCSR( 917 )，並且將PCSI^V ( r )設置成指示可 用(918)。如果LSR—V(r)為可用，則偵測節點檢查DRN是否被設置 成r(908)。
如果DRN被設置成r，則偵測節點基於從在前節點接收的高速緩 存請求的PCSR和高速緩存請求的LSR，產生高速緩存請求的新 PCSR ，利用響應網絡將高速緩存請求的新PCSR轉發給後續節點 (909),以及清除LSR—V(r)以指示不可用(910)。對於每個節點 k，如果PCSR—V (k)指示可用，以及LSR—V (k)指示可用，則偵測節 點基於相應記錄的PCSR和相應記錄的LSR產生新PCSR，利用響應網 絡將新PCSR轉發給後續節點，以及清除PCSR—V (k)和LSR—V (k)以 指示不可用(911)。
如杲DRN未被設置成r，則偵測節點檢查DRN是否指示沒有節點 要接收數據(912)。如果沒有節點要接收數據，則偵測節點基於從 在前節點接收的高速緩存請求的PCSR和高速緩存請求的LSR，產生
高速緩存請求的新PCSR，利用響應網絡將高速緩存請求的新PCSR轉 發給後續節點(913)，以及清除LSRJS^(r)以指示不可用。 否則，如果有任何節點要接收數據，則為了未來處理而記錄從在前節 點接收的高速緩存請求的PCSR( 915 ),並且將PCSI^V ( r )設置成指 示可用(916)。
偵測過濾實施
可以利用適當的偵測過濾器來避免不必要的高速緩存請求和不 必要的本地高速緩存偵測操作，以實施基於環的響應收集系統。當請 求節點接收高速緩存請求時，相應的偵測過濾器可以確定不需要偵測 一些偵測節點。例如，如果偵測過濾器建議針對一個節點過濾高速緩 存數據請求，則在該節點中不能找到所請求的數據，或即使所請求的 數據在該節點中被緩存，也不能從該節點提供所請求的數據。相反， 如果偵測過濾器建議針對一個節點不過濾讀請求，則可以從該節點提 供所請求的數據。
現在示出在處理高速緩存請求時，偵測過濾如何用於減少不必要 的高速緩存請求和不必要的本地高速緩存偵測操作。
如果請求節點收到高速緩存數據請求，則請求高速緩存利用與圖 3相同的方法處理高速緩存數據請求，除了如下修改方框301和302之 外
(301)請求節點獲得給其發送高速緩存請求可能必需的偵測節點 的列表(高速緩存請求的偵測列表)。請求節點利用請求網絡將高速 緩存請求僅發送給在該列表中的偵測節點。
(302 )請求節點利用響應網絡將高速緩存請求的PCSR，與請求 節點向其發送高速緩存請求的偵測節點的列表一起(PCSR和偵測列 表)發送給高速緩存請求的第一偵測節點。
此外，所有對CSR的提及應當被當作CSR和偵測列表。然而，在 請求節點收到高速緩存請求的CSR和偵測列表之後，該請求節點不使 用收到的高速緩存請求的偵測列表，所以不需要進一步改變。
如果請求節點收到高速緩存數據和所有權請求，則請求高速緩存
利用與圖4相同的方法處理高速緩存數據和所有權請求，除了如下修 改方框401和402之外
(401)請求節點獲得向其發送高速緩存請求可能必需的偵測節 點的列表(高速緩存請求的偵測列表)。請求節點利用請求網絡將高 速緩存請求僅發送給該列表中的偵測節點。
(402 )請求節點利用響應網絡將高速緩存請求的PCSR，與請求 節點向其發送高速緩存請求的偵測節點的列表一起(PCSR和偵測列 表)發送給高速緩存請求的第一偵測節點。
此外，所有對CSR的提及應當被當作CSR和偵測列表。然而，在 請求節點收到高速緩存請求的CSR和偵測列表之後，該請求節點不使 用高速緩存請求的偵測列表，所以不需要進一步改變，
如果請求節點收到高速緩存所有權請求，則請求高速緩存利用與 圖5相同的方法處理高速緩存所有權請求，除了如下修改方框501和 502之外
(501)請求節點獲得向其發送高速緩存請求可能必需的偵測節 點的列表(高速緩存請求的偵測列表)。請求節點利用請求網絡將高 速緩存請求僅發送給該列表中的偵測節點。
(502 )請求節點利用響應網絡將高速緩存請求的PCSR，與請求 節點向其發送高速緩存請求的偵測節點的列表一起(PCSR和偵測列 表)發送給高速緩存請求的第 一偵測節點。
此外，所有對CSR的提及應當被當作CSR和偵測列表。然而，在 請求節點收到高速緩存請麥的CSR和偵測列表之後，該請求節點不使 用高速緩存請求的偵測列表，所以不需要進一步改變。
圖10示出了圖解當使用偵測過濾時，偵測節點如何利用高速緩存 請求的偵測列表處理到來的PCSR的流程圖。當偵測節點從在前節點 收到高速緩存請求的PCSR和偵測列表時(1000)，偵測節點檢查在 偵測節點處是否有可用的高速緩存請求的LSR (1001)。如果在偵測 節點處有可用的高速緩存請求的LSR，則偵測節點基於從在前節點接 收的高速緩存請求的PCSR，以及高速緩存請求的可用LSR產生高速
緩存請求的新PCSR ( 1002)。偵測節點利用響應網絡向後續節點轉 發高速緩存請求的新PCSR和偵測列表(1003)。否則，如果偵測節 點處沒有可用的高速緩存請求的LSR，則偵測節點檢查該偵測節點是 否被包含在收到的高速緩存請求的偵測列表中(1004 )。如果偵測節點 被包含在收到的高速緩存請求的偵測列表中，則偵測節點為了未來處 理而記錄從在前節點接收的高速緩存請求的PCSR和偵測列表 (1005)。否則，如果偵測節點未被包含在收到的高速緩存請求的偵 測列表中，則偵測節點利用響應網絡將從在前節點接收的高速緩存請 求的PCSR和偵測列錶轉發給後續節點。
應當理解，可以通過各種形式的硬體、軟體、固件、專用處理器 或其組合來實現本發明。在一個實施例中，本發明可以用軟體實現成 可觸知地嵌入在程序存儲設備上的應用程式。該應用程式可被上載到 包括任何適當體系結構的機器中，並且可被其執行。
根據本發明的實施例，參考圖ll，用於在基於網絡的多處理器系 統中實施高速緩存一致性的計算機系統(1101)可特別包括中央處理 單元(CPU)( 1102)、存儲器(1103)，以及輸入/輸出(I/0)接口 ( 1104 )。 計算機系統(1101)通常通過I/0接口 ( 1104 )連接到顯示器(1105 )， 以及諸如滑鼠和鍵盤的各種輸入設備(1106)上。支持電路可包括諸 如高速緩存、電源、時鐘電路以及通信總線的電路。存儲器(1103) 可包括隨機訪問存儲器(RAM)、只讀存儲器(ROM)、盤驅動器、磁帶 驅動器或其組合。本發明可被實現為被存儲在存儲器(1103)中的、 由CPU (1102)執行的例程(1107)來處理來自信號源(1108)的信 號。這樣，當執行本發明的例程(1107)時，計算機系統(1101)是 一種變成專用計算機系統的通用計算機系統。
計算機平臺(1101 )還包括作業系統和微指令代碼。此處描述的 各種進程和功能可以是微指令代碼的一部分，或者是通過作業系統執 行的應用程式(或其組合)的一部分。此外，各種其它外部設備可被 連接到計算機平臺上，例如附加的數據存儲設備和列印設備。
可以進一步理解，因為附圖中所示的一些組成系統部件和方法可
以用軟體實現，所以系統部件(或過程)之間的實際連接可根據編程 本發明的方式而不同。根據此處提供的本發明的指導，本領域普通技 術人員會能夠想到本發明的這些和類似實現或結構。
前面描述了在基於網絡的多處理器系統中實施高速緩存一致性 的機制和方法的實施例，應當注意，本領域技術人員根據上述教導可 以進行修改和變化。所以可以理解，在公開的本發明的具體實施例中 可以進行各種落在所附權利要求書定義的發明範圍和宗旨內的改變。
權利要求
1.一種用於實施高速緩存一致性的計算機實現的方法，包括通過網絡無需排序限制地從請求節點多播對於存儲器地址的高速緩存請求；通過嵌入所述網絡中的單向環，由所述請求節點收集所述高速緩存請求的組合偵測響應；以及根據所述組合偵測響應，在所述請求節點處實施所述存儲器地址的高速緩存一致性。
2. 如權利要求l所述的計算機實現的方法，進一步包括 通過所述網絡將所述存儲器地址的數據提供給所述請求節點； 在由所述請求節點收集所述高速緩存請求的所述偵測響應之前，使用在所述請求節點處的所述數據；以及在接收到所述高速緩存請求的數據和偵測響應後，完成在所述請 求節點處的所述高速緩存請求。
3. 如權利要求2所迷的計算機實現的方法，進一步包括 在偵測節點處從所述請求節點接收所述高速緩存請求； 在所述偵測節點處執行本地高速緩存偵測操作，並且產生所述高速緩存請求的LSR (本地偵測響應)；以及為了後續處理在所述偵測節點處記錄所述LSR。
4. 如權利要求2所述的計算機實現的方法，進一步包括 在偵測節點處從所述請求節點接收所述高速緩存請求；在所述偵測節點處執行本地高速緩存偵測操作，並且產生所述高 速緩存請求的LSR (本地偵測響應)；基於來自在前節點的所述高速緩存請求的所述LSR以及在前 PCSR,確定所述高速緩存請求的新PCSR (部分組合偵測響應)，其 中在嵌入所述網絡中的單向環中所述在前節點在所述偵測節點之前； 以及通過嵌入所述網絡中的所述單向環，將來自所述偵測節點的所述 高速緩存請求的所述新PCSR轉發給後續節點，其中在嵌入所述網絡 中的所述單向環中所述後續節點在所述偵測節點之後。
5. 如權利要求2所述的計算機實現的方法，進一步包括 在偵測節點處從在前節點接收在前PCSR(部分組合偵測響應)，其中在嵌入所述網絡中的所述單向環中所述在前節點在所述偵測節 點之前；以及為了後續處理在所述偵測節點處記錄所述在前PCSR。
6. 如權利要求2所述的計算機實現的方法，進一步包括 在偵測節點處從在前節點接收在前PCSR(部分組合偵測響應)，其中在嵌入所述網絡中的所述單向環中所述在前節點在所述偵測節 點之前；基於所述高速緩存請求的所述在前PCSR和先前記錄的LSR (本 地偵測響應)，確定所述高速緩存請求的新PCSR;以及通過嵌入所述網絡中的所述單向環，將來自所述偵測節點的所述 高速緩存請求的所述新PCSR轉發給後續節點，其中在嵌入所述網絡 中的所述單向環中所述後續節點在所述偵測節點之後，
7，如權利要求2所述的計算機實現的方法，進一步包括 在偵測節點處從在前節點接收在前PCSR (部分組合偵測響應)和偵測列表，其中所述偵測列表包括針對所述高速緩存請求需要被偵測的至少一個節點；以及如果所述偵測節點被包含在所述偵測列表中，則在所述偵測節點處為後續處理記錄所述在前PCSR。
8. 如權利要求2所述的計算機實現的方法，進一步包括 在偵測節點處從在前節點接收在前PCSR (部分組合偵測響應)和偵測列表，其中所述偵測列表包括針對所述高速緩存請求需要被偵 測的至少一個節點；以及如果所述偵測節點沒有被包含在所述偵測列表中，則通過嵌入所 述網絡中的所述單向環，將所述在前PCSR和所述偵測列錶轉發給後 續節點。
9. 如權利要求2所述的計算機實現的方法，進一步包括 在偵測節點處從在前節點接收在前PCSR (部分組合偵測響應)和偵測列表，其中所述偵測列表包括針對所述高速緩存請求需要被偵 測的至少一個節點；基於所述高速緩存請求的所述在前PCSR和先前記錄的LSR (本 地偵測響應)，確定所述高速緩存請求的新PCSR;以及通過嵌入所述網絡中的所述單向環，將來自所述偵測節點的所述 高速緩存請求的所述新PCSR和所述偵測列錶轉發給後續節點。
10. 如權利要求2所述的計算機實現的方法，其中，將所述數據 提供給所述請求節點的步驟包括提供來自偵測節點的所述數據或提 供來自存儲器的所述數據中的一個。
11. 如權利要求l所述的計算機實現的方法，其中對於所述存儲 器地址的高速緩存請求為數據請求、數據和所有權請求或所有權請 求。
12. 如權利要求l所述的計算機實現的方法，進一步包括 通過所述網絡無需排序限制地多播來自所述請求節點的、對於第二存儲器地址的第二高速緩存請求；通過嵌入所述網絡中的第二單向環，由所述請求節點收集所述第 二高速緩存請求的第二組合偵測響應；以及根據所述第二組合偵測響應，在所述請求節點處實施所述第二存 儲器地址的高速緩存一致性。
13. —種高速緩存一致性的系統，包括 通過網絡連接的多個節點，所述網絡包括嵌入的單向環；以及 實現所述系統的高速緩存一致性的高速緩存一致性機構，其中，所述高速緩存一致性機構利用所述網絡無需任何排序限制 地傳送對於存儲器地址的高速緩存請求，並且利用所述嵌入的單向環 來收集對於所述高速緩存請求的組合偵測響應。
14. 如權利要求13所述的系統，所述多個節點進一步包括 請求節點、在所述嵌入的單向環中在所述請求節點之後的第一偵測節點以及在所述嵌入的單向環中在所述請求節點之前的最後偵測 節點，其中，當所述存儲器地址的高速緩存缺失在所述請求節點中的請 求高速緩存中發生時，所述請求節點利用所述網絡、無需任何排序限 制地將對於所述存儲器地址的所述高速緩存請求多播給至少一個偵 測節點，並且將初始PCSR (部分組合偵測響應)發送給所述第一偵 測節點，其中，如果所述請求節點通過所述網絡接收到所請求的數據，則 所述請求節點將所述高速緩存請求所請求的數據用於計算，以及其中，所述請求節點在接收到所述高速緩存請求的所請求數據和 所述偵測響應後，完成在所述請求節點處的所述高速緩存請求。
15. 如權利要求13所述的系統，所述多個節點進一步包括偵測節點、在所述嵌入的單向環中在所述偵測節點之前的在前節 點、以及在所述嵌入的單向環中在所述偵測節點之後的後續節點， 其中，當所述偵測節點接收到所述高速緩存請求時，如果從所述 在前節點接收的所述高速緩存請求的在前PCSR (部分組合偵測響應) 未被記錄在所述偵測節點中，則所述偵測節點執行本地高速緩存偵測 操作以產生LSR (本地偵測響應)，並且為後續處理記錄所述LSR， 以及其中，當所述偵測節點接收到所述高速緩存請求時，如果從所述 在前節點接收的所述高速緩存請求的所述在前PCSR被記錄在所述偵 測節點中，則所述偵測節點執行本地高速緩存偵測操作以產生所述 LSR，基於所述在前PCSR和所述LSR計算新PCSR，並且將所述新 PCSR轉發給所述後續節點。
16. 如權利要求13所述的系統，所述多個節點進一步包括偵測節點、在所述嵌入的單向環中在所述偵測節點之前的在前節 點、以及在所述嵌入的單向環中在所述偵測節點之後的後續節點，其中，當所述偵測節點接收到來自所述在前節點的所述高速緩存 請求的在前PCSR (部分組合偵測響應)時，如果在所述偵測節點處 未記錄所述高速緩存請求的LSR (本地偵測響應)，則所述偵測節點 為後續處理記錄所述PCSR,以及其中，當所述偵測節點接收到來自所述在前節點的所述高速緩存 請求的所述在前PCSR時，如果在所述偵測節點處記錄了所述高速緩 存請求的所述LSR,則所述偵測節點基於所述在前PCSR和所述LSR 計算新PCSR,並且將所述新PCSR轉發給所述後續節點。
17. 如權利要求13所述的系統，所述多個節點進一步包括偵測節點、在所述嵌入的單向環中在所述偵測節點之前的在前節 點、以及在所述嵌入的單向環中在所述偵測節點之後的後續節點，其中，當所述偵測節點接收到來自所述在前節點的所述高速緩存 請求的在前PCSR (部分組合偵測響應)和偵測列表時，如果所述偵 測節點沒有包含在所述偵測列表中，則所述偵測節點將所述在前 PCSR和所述偵測列錶轉發給所述後續節點，其中，當所述偵測節點從所述在前節點接收到所述高速緩存請求的所述在前PCSR和所述偵測列表時，如果所述偵測節點包含在所述 偵測列表中，以及如果在所述偵測節點處未記錄所述高速緩存請求的 LSR(本地偵測響應)，則所述偵測節點為後續處理記錄所述在前 PCSR和所述偵測列表，以及其中，當所述偵測節點從所述在前節點接收到所述高速緩存請求 的所述在前PCSR和所述偵測列表時，如果所述偵測節點包含在所述 偵測列表中，以及如果在所述偵測節點處記錄了所述高速緩存請求的 LSR，則所述偵測節點基於所述在前PCSR和所述LSR計算新PCSR， 並且將所述新PCSR和所述偵測列錶轉發給所述後續節點。
18. 如權利要求13所述的系統，其中，對於所述存儲器地址的高 速緩存請求是數據請求、數據和所有權請求或所有權請求。
19. 如權利要求13所述的系統，所述網絡進一步包括 第二嵌入的單向環，其中所述高速緩存一致性機構利用所述網絡無需任何排序限制地傳送對於第二存儲器地址的第二高速緩存請求，並且利用所述第二嵌入的單向環收集對於所述第二高速緩存請求的第二組合偵測響應。
全文摘要
提供了一種用於實施高速緩存一致性的計算機實現的方法，包括通過網絡無需排序限制地從請求節點多播對於存儲器地址的高速緩存請求，由所述請求節點通過嵌入網絡中的單向環，收集對於高速緩存請求的組合偵測響應，以及根據該組合偵測響應，在請求節點處實施存儲器地址的高速緩存一致性。
文檔編號G06F12/08GK101178691SQ20071018124
公開日2008年5月14日 申請日期2007年10月25日 優先權日2006年11月6日
發明者卡裡恩·施特勞斯, 沈曉衛 申請人:國際商業機器公司