TW542964B - Method and apparatus for centralized snoop filtering - Google Patents

Description

542964

五、發明説明G 發明領域 該發明關於電腦系統領域。尤 點電腦系統的窺探操作。 -’該發明關於執行多節 發明背景 决：』&性(coherency)是任何電腦系統的關鍵性 素。在網路飼服器電腦系統，維持快取器-致性是_的 工作是由於-個典型網路㈣器包含在多快取器外工作的 !處理器。一些電腦系統建立於節似的、架構其中一些處理 為，它們的快取器記情體，知金 和糸統記憶體區塊構成一節 點。電腦系統可以擁有多節點。 在一個典型的先前系統.，為了去維護快取器一致性，窺 探過濾、器包含在每-節點中。這個結構可以被解釋為分散 式窺探架構。每個節點中的該窺探過遽器追縱（所有同時快 速緩衝儲存於㈣節點處理器快㈣的快㈣列}的快取器 -致性協定狀態資訊。-個較流行的快取器一致隹協定是 MESI(修改的、獨佔的、共享的或無效的）協定。， 在分散式的窺探架構下，當一個節點希望去從記憶體去 5貝取一列的貝料，首先必須清楚是否有任何系統中的快取 器具有那列資料的備份。該列資料的許多備份存於一些節 點的快取為中是可能的並且備份可能快速緩衝儲存於任何 狀態，只要MESI協定許可。為了決定哪一節點有該資料列 的備份以及疋在什麼狀態該列被快速緩衝儲存，節點希望 讀取該資料列必須詢問其它所有點。因此，所有節點必須 被詢問縱使其中一些節點可能沒有詢問（in questi〇n)快速緩 裝 訂 線 542964 五、發明説明（, 衝儲存該資料列。這個結果浪費排線頻寬並創造出 的系統額外負擔和增加延遲。 / 另一個先前㈣統來維護快取器_致性引人了窺探目錄 (lre^t〇ry)。在這個架構了，每個有系統記憶體的節點包含 -，窺探目錄。該窺探目錄追㈣有快取器動作資訊包含 座落於那個節點的記憶體位置（i_lving ！。如^ located at that node)。每個窺探目錄從窺探目錄節點系統記 憶體追縱哪個節點有快速緩衝儲存該資料列並且追縱被快 速緩衝儲存該列在什麼狀態。如此，有了這個分散式目錄 =構，當一個節點（提出請求的節點）希望從其他節點（終點 即點）上讀取記憶體位置，提出請求的節點必須與查詢它的 目錄的（who consults its direct〇ry)終點節點聯繫。接著終 點即點运出窺探請求到任一節點，其中該任意節點有詢問 (in question )快速緩衝儲存記憶列（mem〇ry Hne)的備份。 然後各個不同的節點回應給終點節點而終點節點因此可以 提供要求的資料給提出要求的節點。第一步驟聯繫終點節 點然後終點節點聯繫其它節點來窺探資訊會導致非期待的 系統額外負擔，尤其是在電腦系統中，其中該電腦系統的 節點藉由交換裝置連結在一起。 圖式簡述 本發明將從下列具體實施例中詳細的說明和伴隨的圖式 更加了解，然而這些說明和圖式不應該被拿來限制發明於 所敘述的特定具體實施例，而只是拿來說明和了解而已。 圖1疋一個系統的具體實施例的方塊圖，該系統係包含幾 裝 訂 線 542964 五 A7 B7

其中該交換裝置包含一 個藉由一個交換裝置連結的節點， 個中央窺探過濾器。 個系統的具體實施例之方塊圖，該系統係_ 個錯由兩個交換裝置連結的節點，其中該兩個交換裝 個包含一個中央窺探過濾器。 '、 是一個方法的具體實施例之流程圖，該方法是為了值 用在交換裝置中的中央窺探過濾、器而執行—個窺探週期。 -圖4是一個方法的具體實施例之流程圖，該方法是為了朝 仃-讀取處理’該讀取處理包含一個使用在交換裝置中的 中央窺探過濾器之窺探週期。 詳細說明. 一個使用中央窺探過濾器之電腦系統的具體實施例，該 中央窺探過濾器包含數個經由交換裝置連結在一起的節 點。每個節點可能包含數個處理器和快取器和系統記憶 體。從一個節點到另一節點的所有流量皆透過交換裝置發 生。該交換裝置包含一個窺探過濾器，該窺探過濾器針對 所有在電腦系統中的快取器追蹤快取器列的連貫性資訊， 該窺探過渡器有至少足夠的入口（ entrieS )來追蹤所有系統節 點中所有快取器的所有入口的標記位址（tag address)和狀態 資訊。除了標記位址和狀態資訊外，該窺探過濾器儲存資 訊指出哪些節點具有每個快取器列的備份。該窺探過濾器 部分適用（serves in part to)於避免窺探動作（transactions)執 行於沒有包含對象主體快取器列的一個備份之節點中藉此 減少系統額外負擔處理，減少跨系統互連匯流排的流量， 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐) , 裝 訂

線 542964 A7 B7 五、發明説明（4 和減少執行窺探作業所需的時間。 一個中央窺探器的具體實施例使用一種不同的Mesi協 疋。在這個具體實施例中的窺探過濾器追縱快取器列是否 疋無效的、共旱的或修改/獨佔的。該完整的MESI協定支援 在不同節點上的快取器中。其它協定可以使用，只要在所 有快取器代理人程式（agents)上的動作（transactions)是一致 的。 因為中央窺探過濾器包含所有在快取器代理人程式上的 快取裔，所以快取裔代理人程式不應該具有沒有出現在窺 探過濾、益中之快取器列的備份。如果一列被從窺探過遽器 中除去，該列也必須從包含該列備份的所.有節點之快取器 代理人程式中除去。 該窺探過濾、器利用存在向量（vect〇r)追縱那些節點，具有 著一個列（line)的備份。該存在向量是一位元欄位，其中每 個位元對應到一個特定節點。 不同的具體實施例可能在每一個節點上不是使用向量組 (vector field)而是使用不同的窺探過濾器。窺探過濾器位 於父換裝置上並且因此集中放置。可以實施該窺探過濾器 或多個窺探過濾器使得特定窺探過濾器入口適用於一個節 點，其它入口適用於其它節點，如此推演下去。 圖1是一個系統的區塊圖，該系統包含節點A、節點B和 節點C。節點A可以包含多個標為1〇5到1的處理器。節點B 可以包含多個標為115到Μ之處理器。節點c可以包含多個 標為1 2 5到Ν之處理。節點a也可以包含一節點控制電路

542964

1〇2和一個系統記憶體區塊1〇4。節點B也包含節點控制電 路112和一個系統記憶體區塊1 1 4。另外節點C包含一節點 控制電路1 2 2和一個系統記憶體區塊丨2 4。節點a、b和c的 處理器包含快取器。 節點A、B和C每個都連結到一交換裝置13〇上。該交換裝 置130包含一個中央窺探過濾器132。一輸入/輸出集線器 140亦連接至該交換裝置13〇。輸入/輸出集線器14〇也可以 匕吞個陕取态。該窺探過濾、器132包含足夠入口來追縱目 刖所有系統節點的所有快取器的所有入口的標記、狀態和 貢訊，該等系統節點包含該處理器快取器和該輸入/輸出集 線器140快取器。 現在时論一個向沒有快速緩衝儲存於任何系統快取器之 中的兄憶列執行資料讀取動作的例子。對這個例子而言， 節點A是提出請求的節點（該結點發送出讀取動作），節點匸 是終點節點（該節點包含讀取請求所定址（addressed)的系統 記憶體部分）。節點A發出一個讀取請求到交換裝置丨3 〇。該 窺探過遽1 3 2接者執行一個查詢（lookup )操作來決定被讀 取請求定址的記憶列是否已經被快速缓衝儲存於任何節點 A、B或C，或在輸入/輸出集線器14〇中。當該窺探過濾器 132正在執行查詢（lookup)操作時，該交換裝置13〇發送出 一個推測的（speculative)記憶體讀取到節點c。該交換裝置 1 3 0包含記憶體解碼電路，其中該記憶體解碼電路使得交換 裝置1 3 0可以決定哪一個節點正被該讀取請求所定址。對這 個例子而言，該窺探過渡器查詢（lookup )指出由該讀取請求 本紙張尺度適用中國國家標準(CNS) A4规格(210X297公釐)

裝 訂

線 542964

所疋址的記憶列沒有快速緩衝儲存於任何系統快取器中。 該父換裝置1 3 0傳送一個窺探回應給節點a並且也送一個記 憶體讀取確認訊息給節點c。回應記憶體讀取確認訊息，節 點c傳送所請求的資料到交換裝置13〇。該交換裝置13〇然 後傳运該請求的資料到節點A。因為節點A是唯一快速緩衝 儲存主（subject)快取器列的節點，該窺探過濾器132將它的 用於此决取列之入口標5己為獨佔（exclusive)並且設定存在 向量以指出節點A有著該快取器列的一個備份。 現在將討論一個寫入到由兩個節點共享之快取器列的記 憶體寫入動作之例子，對這個例子而言，節點A是提出請求 的節點並且也是終點節點。換句話說，節點A正在寫入一列 貢料到它自己的記憶體。節點A藉由發送出一個無效的周期 到該交換裝置130而開始。該窺探過濾器132接著執行一個 查詢操作來決定那些節點有著快取器列的備份並且也決定 在何種狀態快取益列被快速緩衝儲存。該查詢操作在這個 例子中指出快取器列是“共享的，，並且節點B和c都有備 份。該交換裝置130接著發送出多個無效的循環到節點B和 C。節點B和C以窺探回應訊號來回應，接著該交換裝置 130發送一個窺探回應給節點八來完成整個動作。該窺探過 濾器132現在顯示，節點A有著該快取器列的唯一備份並且 該列是在獨佔/修改”的狀態。 現在將討論一個針對一個“修改的”快取器列之讀取週 期（cycle)的例子，對這個例子而言，節點A是發出請求的 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 542964 A7 B7

節點，節點B是已修改過所關心的快取器列之備份的節 點，並且節點C是終點節點（該節點的系統記憶體區塊包含 對應到快取器列的記憶體位置）❶節點A藉由發送一個取請 求到交換裝置130開始動作。當交換裝置13〇發出一個推測 性（speculative)的記憶體讀取到節點c時，該窺探過渡器

132執行一個查行操作。窺探過濾器查詢的結果指出節點B 有一個快取器列修改過的備份。該交換裝置丨3 〇送出一個窺 探請求到節點B，節點B以伴隨有該修改資料的窺探回應來 回應。該交換裝置1 3 0接著傳送該窺探回應和該資料到節點 A ,並且同時傳送該資料到節點c，使得系統記憶體可以被 更新。節點C接著發信一個完成信號到交換裝置13〇 ,並且 遠元成#號從該交換裝置1 3 〇轉送到節點a來完成該動作 (transaction)。 有可能在一個系統中使用多個窺探過濾器，以提供充分 的窺探過濾器處理效能（throughput)和能力以符合系統可擴 展性（scalability)需求。在這種情況下，不同的窺探過濾器 持續追蹤快取器列的互斥集合。所有時候一個快取器列都 被唯一的一個窺探過濾器所追蹤。 圖2是一個系統的方塊圖，該系統包含節點D、節點£和 節點F，並且也包含兩個窺探過濾器232和234。節點D可以 包含多個標為205到P之處理器。節點E可以包含多個標為 215到Q之處理器。節點F可以包含多個標為225到尺之處理 器。節點D也包含一個節點控制電路2〇2和一個系統記憶體 區塊2 04。節點E也包含一個節點控制電路2丨2和一個系統

。己隐體區塊2 1 4。另外續點F包含_個節點控制電路222和 一個系統記憶體區塊224。該節點D、E、和F的處理器包含 快取器。 節點D、E和F每一個由交換裝置23〇所連結並且也連到交 換裝置240。該交換裝詈7 白人1 + 乂俠扠罝23〇包含該中央窺探過濾器232。 一個輸入/輸出集線器250也和交換裝置24〇 一樣連結到交換 裝置230。該輸人/輸出集線器25()也可以包含—個快取器。、 該交換裝置240包含該中央窺探過濾、器242。—個輸入/輸出 集線器260也連接到交換裝置24〇並且也連到交換裝置 230。該輸入/輸出集線器26〇也可以包含一個快取器。 該窺探過壚器232包含足夠的入口來追蹤針對所^系統節 點中的所有快取器的所有一半的入口之標籤、狀態和現在 的資訊’該等系統節點包含該處理器快取器和輸入/輸出集 線器快取器。該窺探過渡器242包含針對該系統快取器的: 餘部分之入口。在一個具體實施例中，該節點d、£和 一個交替（alternating)的快取器列基礎上，交替存取交換 置230和240 ° 一圖3是-個方法的具體實施例的流程圖。該方法係關於執 行一個窺探週期（cycle)，其中該窺探週期係使用位於交換 ，置中的中央窺探過滤器。在區塊31G中個讀取請求從 第一個節點發送出到一個交換裝置。該交換裝置包含一個 窺探過渡器。在方塊32G中，執行—個窺探過渡器查二來決 定是否位於第二節點的一個快取器有著對應於該 2 的快取器列之備份。 Μ求 542964

圖4是一個方法的具體實施例的流程圖。該方法執行一個 包含使用位於一個交換裝置中的中央窺探裝置的一個窺探 週期之讀取動作。在方塊41〇中，一個讀取請求從第一個節 2發送到一個交換裝置，該交換裝置包含一個窺探過濾 态。該讀取請求定址（addressed)於位於第二節點中的記憶 體位置。在方塊420中執行，一個窺探過濾器查詢，同時在 方塊43 0中，一個推測的記憶體讀取提取從該交換裝置發送 到第二個節點。方塊44〇指出如果該窺探過濾器查詢決定， 由讀取請求所載明的記憶列被快速緩衝儲存於一個或多個 該節點中，然後一個快取器列演算法在方塊45〇中執行。這 種形式的演算法的例子在上面被討論並與圖1有關。方塊 440也指出如果該窺探過濾器查詢決定，由讀取請求所載明 的該記憶列不藉由任何快取器代理者快速緩衝儲存，則在 方塊460中一個窺探回應從該交換裝置傳送到第一個節點❶ 同時，在方塊470—個記憶體讀取確認訊息從該交換裝置傳 送到第二節點。最後，在方塊48 0該提取的資料藉由交換裝 置從第二節點傳送到第一節點。 在前面的說明中，本發明已經參考特定範例性的具體實 施例說明。然而很明顯地，可生不背離如附加的申請專利 範圍所述之本發明的較廣的精神和範圍，而對本發明進行 不同的修改和改變。因此，本說明書和圖式可視為範例而 非限制。 涉及到說明中的“一具體實施例，，、“一個具體實施例”、 “一些具體實施例”或“其它具體實施例，，意思是，參考各具 ____· 12 - 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公爱)

裝 訂

542964 A7 B7 五、發明説明（1〇 ) 體實施例所述之一個特別的特徵、結構或特性是包含在本 發明的至少一些具體實施例但未必是所有具體實施例。“一 具體實施例”、“一個具體實施例”或“一些具體實施例”的出 現未必指的是相同的具體實施例。 -13 - 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐)

Claims (1)

1. >64 >64

   第〇9012〇537號專利申請案 中文申請專利範圍替換本(92年5月）S L 一種用於中心化窥探過濾器之裝置，包含：· 钕數個節點介面埠，提供複數個節點的通聯，·和 個▲板過攄态’用來維持該等多個節點的快取器一 致性（coherency)資訊。 2·如申請專利範圍第1項之裝置，其中該等複數個節點的每 個節點係包含一個快取器，並且其中該窥探過滤器另外 包含至少多個和位於多節點中所有快取器所包含的入口 的數量相同之入口。 3.如申請專利範圍第2項之裝置，其中每個窥探過濾器入口 包含一個位址標記。 4·如申請專利範圍第3項之裝置，其中每個窥探過遽器入口 包含一個攔位（field)，指示一個相對應之快取器列的快 取器連貫性協定狀態。 5. 如申請專利範圍第4項之裝置，其中每個窥探過濾器入口 包含一個欄位（field)指出該多節點哪一個有相對應快取 器列的備份在它的快取器中。 6. 如申請專利範圍第5項之裝置，該等多節點介面埠的一個 接收來自該等多節點和窥探過濾器中的一個的窥探請 求，決定（該多節點的其它哪-個有相對應於該窥探^求 快取器列的備份）並且決定（哪一個快取器連貫性協定狀 態被指定給該快取器列）。 7· —種用於中心化窥探過濾器之系統，係包含： 一個交換裝置，其包括一個窺探過滤器； 一個第一個節點，其連到該交換裝置；和 542064— 修正甲w利:範園

   AS B8 C8 Ό8 一個第二個節點，其連到該交換裝置。 S·如申請專利範圍第7項之系統，其中該第一個節點係包括 個處理咨和一個快取器。 9. 如申請專利範圍第8項之系統，其中該第二個節點係包括 一個處理器、一個記憶裝置和一個快取器。 10. 如申請專利範圍第9項之系統，其中該窥探過濾器係包括 和為弟一個節點和該第二個節點中包括的入口至少相同 數量的入口。 11. 如申清專利範圍第i 〇項之系統，其中每個窥探過濾器入 口係包括一個位址標記。 12·如申明專利範圍第i i項之系統，其中每個窥探過濾器入 口係包括一個欄位，指出一個相對應的快取器列的一個 快取器連貫性協定狀態。 13·如申明專利範圍第丨2項之系統，其中每個窥探過濾器入 口係包括一個欄位，指出該第一個節點和第二個節點哪 一個有一個相對應快取器列的一個備份在它的快取器 中〇 Η如申請專利範圍第13項之系統，該交換裝置接收一個來 自於該第一個節點和該窥探過濾器的窥探請求，以決定 該第-個節點和該第二個節點哪—個有相對應於該窥探 請求之快取器列的備份並且決定哪—個快取器連貫性協 定狀態被指定給該快取器列。 15·—種用於中心化窺探過濾器之方法，係包含·· 從一個第一個節點發出一個讀取請求到一交換裝置， 本紙張尺度適用中國國家標準(CNS) Α4規格(210X297公釐) 54291CT 修正補充 A8 B8 C8 D8 申請專利範圍 該交換裝置包括一個窥探過濾器； 執行一個窺探過濾器查詢，來決定是否一個位於一個 第二個節點的快取器有一個相對應於該讀取請求快取器 列的備份。 16. 如申請專利範圍第1 5項之方法，另外包含緊接著該窺探 過濾器查詢，從該交換裝置發出一個窥探回應到該第一 個節點。 17. 如申請專利範圍第1 6項之方法，另外包含藉由從一個位 於該第二個節點之記憶體提取資料而執行該讀取請求， 以回應該讀取請求，該資料提取由該交換裝置執行。 18. —種用於中心化窥探過濾器之方法，係包含： 從一個第一個節點發出一個讀取請求到一交換裝置， 該交換裝置包括一個窥探過濾器，該第一個節點是該多 節點中的一個，該讀取請求定址（a d d r e s s e d)至位於第二 個節點的記憶體位置，該第二個節點也是該多節點中的 一個，該多節點中每一個包括一個快取器； 執行一個窥探過濾器查詢而從該交換裝置發出一個推 測的（speculative)記憶體讀取提取到該第二個節點； 從該交換裝置傳送一個窥探回應到該第一個節點，而 同時，如果該窥探過濾查詢指出該無節點有一個相對應 於該讀取請求所指明的記憶體位址的記憶體快取器列， 一個記憶體讀取確認訊息被傳送到該第二個節點； 傳送資料，以回應從該第二個節點到該交換裝置的該 記憶體讀取確認訊息，以及 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐) 542964—

   A8 B8 C8 D8 六、申請專利範圍 裝置傳送該資料從該交換到該第一個節點。 · 19.如申請專利範圍第1 8項之方法，另外包含在窥探過濾器 内指出該傳送資料已被該第一個節點在一個獨佔狀態下 快速緩衝儲存。 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐)