TWI237181B - Non-uniform memory access (NUMA) computer system that grants exclusive ownership of data based on history information - Google Patents

Description

1 1237181 A7 B7 五、發明説明（η ) 相關申請案之對照 本申請案係有關下列待審之申請案，這些待審之申請案 係在與本申請案相同的日期提出申請，且係讓渡給本申請 案之受讓人，本申請案特此引用該等待審之申請案以供參 照，這些待審之申請案包括： (1)美國專利申請案 / AUS920000893U S 1)； ( 内 部 案 號 (2)美國專利申請案 / AUS920000894US 1)； ( 内 部 案 號 • 1 (3)美國專利申請案 / AUS920000895U S 1)； ( 内 部 案 號 (4)美國專利申請案 / AUS920000896US 1)； ( 内 部 案 號 V (5)美國專利申請案 / AUS920000897U S 1)； ( 内 部 案 號 h (6)美國專利申請案 / AUS920000900US 1)； ( 内 部 案 號 Φ\ (7)美國專利申請案 / AUS920000902US 1)；以及 ( 内 部 案 號 線 (8)美國專利申請案 / ( 内 部 案 號 AUS920000903U S 1) ° · 發明背景 1.技術領域： 本發明係大致有關資料處理系統，尤係有關非均勻式記 -4- 本紙張尺度適用中國國家標準(CNS) Α4規格(210X 297公釐) 1237181 A7 B7

憶體存取（Non-Uniform Memory Access ;簡稱 NUMA)、以 及具有更佳的佇列、通訊及（或）儲存效率之其他多處理器 資料處理系統。 2.相關技藝說明： 在電腦技藝中，大家都知道：控制_聯的多個各別處理 器之處理能力，即可獲致較大的電腦系統效能。可利用若 干種不、同的拓撲來設計多處理器（Multi_Pr〇cess〇r ;簡稱Mp) 電腦系統，在這些拓撲中，各種拓撲可能因每一特定應用 的效能要求及軟體環境而較適用於該應用。一種常見的 MP電腦拓撲是對稱式多處理器（Symmetdc Muhi_ Processor ;簡稱SMP)組態，其中多個，處理器中的每一處理 器共用諸如系統記憶體及輸入/輸出（1/〇)子系統等的一組 共同的貝源，而遠等資源通常係镇合到一共用的系統連 線。因為一 SMP電腦系統中的所有處理器在理想上是對該 共用系統記憶體中儲存的資料有相同的存取延遲時間。 雖然SMP電腦系統可使用較簡單的處理器間之通訊及資 料共用方法，但是SMP電腦系統的延展性是有限的。換言 之，雖然通常可預期一典型SMP電腦系統的效能會隨著規 模（亦即，加入更多的處理器）而提昇，但是固有的匯流 排、記憶體、及輸入/輸出（I/O)頻寬上的限制，使得盏法 因將一SMP的規模推展到這些共用資源的使用已最佳化的 一特定實施規模之外而得到顯著的好處。因此，當系統的 規模加大時，SMP拓撲本身多少會受到頻寬上的限制，尤 其會受到系統記憶體頻寬的限制。SMp電腦系統也是不是 裝 訂

線 -5- 1237181 A7 ---------_ 五、發明説明（3 ) 一 擴充的例如，一使用者貝了 一部具有兩個或四個處理器 的SMP電腦系統，後來當處理的需求增加時，該使用者通 Φ典法將該系統擴充到八個或十六個處理器。 因此，目岫已出現了一種被稱為非均勻式記憶體存取 (NUMA)的MP電腦系統，以便解決對SMp電腦系統的延展 性及擴充性的限制。如圖丨所示，一傳統的NUMA電腦系 、.先8 〇 §由文換器12連接的若干節點1 〇。可實施為一 SMP系統的每一節點1〇包含一區域連接裝置η，且若干處 理單7C 14係耦合到該區域連接裝置u。各處理單元分別 匕 έ 中央處理單元（Central Processing Unit ;簡稱 CPU) 16及相關聯的快取記憶體階層18。在該揮發性記憶體階層 的最低層上，各節點10進一步包含一系統記憶體22，可將 孩系統記憶體22集中在每一節點1〇内，亦可如圖所示將該 系統记憶體22分散到各處理單元14。各cpu 16係經由一記 憶體控制器20而存取記憶體22。 每一節點10進一步包含一各別的節點控制器24，該節點 控制器24保持資料的一貫性，並協助各節點1〇之間經由交 換备12的要求及回應之傳送。每一節點控制器以具有：一 相關聯的區域記憶體目錄（Local Mem〇ry Direct〇7 ;簡稱 LMD) 26，用以識別來自系統記憶體22且原先係緩衝儲存 在其他節點ίο之資料，· 一遠端快取記憶體（Rem〇te Mem〇ry Cache;簡稱RMC) 28,用以暫時緩衝儲存自遠端系統記憶 體擷取的資料；以及一遠端記憶體目錄（Rem〇te Directory ;簡稱RMD) 30 ,用以提供111^(： 28的内容之一目 I -6- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公爱)--------- 1237181 4 五、發明説明（ 錄。 比^明$為雖然圖1所示的該傳統NUMA架構可提供 :傳統SMP架構更佳的延展性及 二 NUMA架構還是有若干 ^ 疋^傳，..无的 默”、、占。首先，郎點間之通訊會有比 ^域連接裝置11的通訊高出許多的延遲時咖如， :出：倍至十倍的延遲時間），此即意指：減少節點間之 2 ^將會提高效率。因此，最好是採用-較大的遠端 細己憶體28，以便限制必須在各節點10之間傳送的資料 要长的數目。然而’以靜態機存取記憶體 J _八⑽“ Mem〇ry ;簡稱SRAM)構成的RMC 28之傳統 ^施例是高成本的，且限制了實際實施時的RMC 28之容 I义因此，每一即點只能緩衝儲存來自其他節點的有限量 长〃料因而而要有頻繁的長延遲時間之節點間資料要 傳統NUMA電腦系統與節點間通訊延遲時間有關的第二 個缺點是服務不必要的節點間一貫性通訊所引發的要求時 之延遲。例如，諸如圖丨所示的先前技藝NUMA電腦系統 可讓遠端節點沈默地解除分配未修改的快取線。換言之， 該等遠端節點中之快取記憶體可解除分配自另一節點擷取 的共用或無效之快取線，而無須通知在該快取線被"取消” 所在的節點上的本地節點之區域記憶體目錄。因此，該本 地節點的區域記憶體目錄只維護一個哪一遠端節點存放有 來自相關聯的系統記憶體的快取線之不嚴密之指示。因 此，當在一節點上接收到一儲存要求時，該節點必須將一 本纸張尺度適财@ g家標準(CNS) Μ規格(21GX297公爱） 1237181 五、發明説明（ 清—）㈣咖㈣爾域記咖 ^中指:為存放有目標快取線之所有其他節點，而不論該 等其他即點是否仍然緩衝儲存了該目標快取線的一份拷 7在某些作業情況中，不必要的清除作業可能會延遲對 儲^要求的服務，因而對系統效能有不利的影響。 a罘三，諸如NUMA電腦系統8等傳統的NUMA電腦系統經 吊會在整個系統中分佈的各節點控制器、記憶體控制器、 及快取屺憶體控制器内實施較深的佇列，以便容許因節點 間通訊所造成的較長之延遲時間。雖然每一個別佇列的實 她不疋南成本的，但是在整個傳統NUMA電腦系統中實施 的幸X深之仔列則代表了整體系統成本中的一顯著成分。本 發明因而認為：減少NUMA電腦系統的佇列中的作業之未 决狀怨’並提鬲佇列的使用率，因而可降低佇列深度及因 而產生的系統成本，此種方式將是有利的。 有鑑於傳統NUMA電腦系統的前文所述之及其他的缺 點’本發明認為：提供一種具有更佳的佇列、儲存、及/ 或通訊效率的NUMA架構將是有用的且需要的。 發明概述 本發明由於提供了一種非均勻式記憶體存取（NUMA)電 腦系統、以及用來根據歷史資訊而將資料的唯一所有權授 予遠端節點中提出要求的裝置的相關聯之作業方法，而克 服了先前技藝中的前文所述之及其他的缺點。 根據本發明的一較佳實施例，一 NUMA電腦系統包含由 一節點連接裝置耦合之至少一個遠端節點及一本地節點。 -8 - 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐） A7 B7 1237181 五、發明説明（6 ) 該本地節點包含一本地系統記憶體及一記憶體控制器。該 記憶體控制器回應自一遠端節點接收到一資料要求，而查 詢用來指示該遠端節點中發出的先前資料存取之歷史資 訊，以便決定授予該資料要求中指定的所要求資料之唯一 所有權或非唯一所有權。該記憶體控制器然後將所要求的 資料及唯一所有權或非唯一所有權之一指示傳送到該遠端 節點。. 若參閱下文中之詳細說明，將可易於了解本發明的前文 所述之及其他之目的、特徵、及優點。 圖式簡述 本發明之創新特徵係述於最後的申請專利範圍中。然 而，若參照下文中對一實施例之詳細說明，並配合各附 圖，將可更易於了解本發明、以及其較佳使用模式、其他 目的、及優點，這些附圖有： 圖1是根據先前技藝的一 NUMA電腦系統之方塊圖； 圖2A示出根據本發明的一NUMA電腦系統之一實施例， 該實施例具有在一系統記憶體内所設之一遠端快取記憶體 (RMC)； 圖2B示出根據本發明的一 NUMA電腦系統之一實施例， 該實施例具有在一系統記憶體内所設之一遠端快取記憶體 (RMC)及一相關聯的遠端記憶體目錄（RMD); 圖3是圖2A或2B所示NUMA電腦系統内的一記憶體控制 器之詳細方塊圖； 圖4是圖2A或2B所示NUMA電腦系統中的一較低階快取 -9- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐） 1237181 A7 B7 五、發明説明（7 ) 記憶體之詳細方塊圖； 圖5是發出用來向根據本發明的一 NUMA電腦系統中之 另一節點要求資料的讀取類型要求的一例示方法之高階邏 輯流程圖； 圖6示出根據本發明的一例示讀取類型要求； 圖7是用來自根據本發明的一遠端節點解除分配處於一 共用一貫性狀態的一要被取代的快取線的一例示方法之高 階邏輯流程圖； 圖8是用來自根據本發明的一 NUMA電腦系統的一遠端 節點解除分配處於一經過修改的一貫性狀態的一要被取代 的快取線的一例示方法之高階邏輯流程圖； 圖9示出圖8所示方法中可採用的一例示逐出寫入作業； 圖10A及10B是合而示出利用一清除查詢來要求解除分 配根據本發明的一 NUMA電腦系統中存放的各快取線之高 階邏輯流程圖； 圖Π是用來在一採用根據本發明的分散式一貫性管理的 NUMA電腦系統之一遠端節點中執行一清除作業的一例示 方法之高階邏輯流程圖； 圖12是利用一 Numafy命令來傳送對一讀取類型作業的一 目標快取線的整體一貫性管理的責任之一時間-空間圖； 圖13示出圖2A或2B所示NUMA電腦系統中的區域記憶體 目錄（LMD)之一例示目錄資料項； 圖14是一 NUMA電腦系統的一系統記憶體控制器用來回 應一讀取類型要求而更新區域記憶體目錄（LMD)内的一遠 -10- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐） I237i8l A7 ------- B7___ 五、發明説明（8 ) 端節點的歷史資訊的一例示方法之狀態圖；以及 圖15A-15C合而示出一 NUMA電腦系統的一系統記憶體 控制器根據本發明一較佳實施例而用來控制資料及指令的 預先提取之一例示方法。 實施例之詳細說明 凊參閱各圖式，尤其請參閱圖2A，圖中示出根據本發 明的一 NUMA電腦系統50之一實施例。可以諸如一工作 站、伺服器、或大型電腦之方式來實現所示之實施例。雖 然下文中主要係參照NUMA電腦系統50而說明本發明，但 疋熱習此項技藝者當可了解，本發明的許多特徵亦可適用 於其中包括SMP架構的其他電腦系統架構。 如圖所示，NUMA電腦系統50包含由一節點連接裝置55 耦合的兩個或更多個節點52 ,而如圖所示，該節點連接裝 置55可實施為一交換器。雖然本發明並無要求，但是在所 不實施例中，每一節點52是相同的，其中每一節點包含： 耦合到一區域連接裝置58的一個或多個處理單元54、以及 耦σ於區域連接裝置58與節點連接裝置55之間的一節點控 制器56。每一節點控制器56將在區域連接裝置58上接收到 的所選擇之作業經由節點連接裝置55而冑送到其他節點 52，並在區域連接裝置58上傳送經由節點連接裝置兄接收 到的所選擇之作業，而用來作為其他節點52之-區域中介 器。 處理單元54包含_CPU6G，該cpU6()具有若干暫存器、 本紙張 ^^"^標準(cnsG;見格(210_ 11- X 297公釐） 1237181 A7 -----— _ B7 五、發明説明—Γ ' " 指令流程邏輯電路、及用來執行軟體指令的若干執行單 元。每一處理單元54進一步包含一快取記憶體階層62，該 快取記憶體階層62包含用來將資料自整個NUMA電腦系統 •勺各貝料儲存卓元扼供給相關聯的Cpu 60之一階或多階 的晶片内建快取記憶體。下文中將參照圖4而說明可在快 取記憶體階層62内採用的一適用之快取記憶體架構。此 外’母’一處理單元54具有一介面單元65，用以處理處理單 元54與區域連接裝置58間之位址、資料、及一貫性作業的 傳送，且如將於下文中進一步說明的，每一處理單元54又 包含回應邏輯電路63 ,用以利用對區域連接裝置58上發出 的一作業之各種監視回應而決定該作業之一合併回應。最 後，每一處理單元54包含一記憶體控制器64，用以控制對 分佈在各處理單元54的該等實體系統記憶體66中的一個相 關聯的系統記憶體之存取。在本發明的一替代實施例中， 每一節點中如有任何系統記憶體，可將該系統記憶體實施 為文到耦合到區域連接裝置58的一相關聯的記憶體控哭 控制之一單一系統記憶體。 在本說明中，係將”系統記憶體”定義為一實體資料儲存 裝置，且係利用與該實體資料儲存裝置中的各別儲存位置 水久相關聯的各唯一位址（並無錯誤的狀況）來定址到該實 體資料儲存裝置。若節點52將一資料儲存在該節點的系統 記憶體66中之一儲存位置，且該儲存位置係與可在整個 NUMA電腦系統50中用來唯一地識別該資料的一位址相關 聯，則將該節點52定義為該資料之本地節點；相反地，係 -12-

1237181 A7 B7 五、發明説明（10 ) 將其他的節點52定義為該資料之遠端節點。 如圖2A及圖3所示，為了支援各節點52間之資料共用， 記憶體控制器64採用了一區域記憶體目錄（LMD) 72、及具 有一相關聯的遠端記憶體目錄（RMD) 74之一遠端快取記憶 體（RMC) 70。在本文的用法中，係將一區域記憶體目錄 (LMD)定義為用來針對一相關聯的系統記憶體中存放的資 料而儲、存與是否將該等資料緩衝儲存在一個或多個遠端節

點有關的指示之一目錄。相反地，係將一遠端記憶體目錄 (RMD)定義為用來指示來自其他節點中的系統記憶體之哪 些資料被緩衝儲存在相關聯的遠端快取記憶體（RMC)之一 裝 目錄。為了便於說明，在本文中將用來控制對一相關聯的 系統1己憶體66内的本地節點資料的存取之一記憶體控制器 64電路稱為一系統記憶體控制器71，並將用來控制 70的存取之一記憶體控制器64電路稱為一 RMC控制器。 訂

當然，NUMA電腦系統50可進一步包含額外的裝置，在 了解本發明上，這些額外的裝置不是必要的，目而省略了 該等額外的裝置，㈣免模糊了本發明。例如，任何節點 如可支援1/0及網路介面+、用來儲存作業系統及庫用 軟體的非揮發性儲存裝置、以及用來連接到網路或附屬裝 置的序列及平行蟑。 記憶體組緒_ ::電腦系统50的效能尤其受資料存取延遲時 資料要求的存取延遲時間通常遠小於節點 間貝料要求的存取延遲時間，所以如果包含_處理單以 -13- 1237181 A7 B7 五、發明説明（Ή ) 的每一節點52有較大的資料儲存容量，因而儘量減少節點 間資料要求，則通常可提昇系統效能。例如，在NUMA電 腦系統50包含四個節點，且每一節點包含四個處理單元54 及四個系統記憶體66之一實施例中，四個系統記憶體66中 之每一系統記憶體都有8 GB (gigabyte ;十億位元組）或更 大的容量，將可提供128 GB或更大的總系統記憶體儲存容 量。因為系統記憶體的此種大容量，所以在成本的考慮 上，通常會指定以諸如動態隨機存取記憶體（Dynamic Random Access Memory ;簡稱DRAM)等具有較低的單位位 元組成本之儲存技術來實施系統記憶體66。 根據本發明，可將系統記憶體66的儲存容量諸如由 NUMA電腦系統50的作業系統分成一個或多個位址空間。 在圖2A所示之實施例中，每一系統記憶體66包含一系統記 憶體位址空間68，且係由NUMA電腦系統50之作業系統將 該系統記憶體位址空間68分配給各作業系統及應用程序， 以便儲存指令及資料。此外，包含一處理單元54的每一節 點52中之至少一個系統記憶體66包含一 RMC 70，用以儲 存對應於一個或多個其他節點52的系統記憶體66中存放的 資料之資料。因此，本發明並不實施如圖1所示的一單一 獨立的遠端快取記憶體28，而是在每一節點52中的一個及 或有的多個系統記憶體66内實施遠端快取記憶體。在將 RMC 70分散到多個系統記憶體66的實施例中，最好是將 至少同一節點52内的任何CPU 60都可存取的快取線對映到 若干特定的RMC 70，其方式是以赫許法（hashing)轉換與該 -14- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐） 1237181 A7 B7 五、發明説明（12 ) 等快取線相關聯的實體或邏輯位址。 因為並非以高成本的SRAM而是以低成本的DRAM來實 施遠端快取記憶體，所以與先前技藝比較時，RMC 70的 單位位元組成本大幅降低，此即意指：可以在沒有或只有 很少額外成本的情形下，大幅增加RMC 70的容量。此 外，藉由使該遠端快取記憶體分佈到同一節點中的多個系 統記憶體，可以獲致比先前技藝優異的較高頻寬，其方式 是將存取控制分配到多個記憶體控制器64，而不是由一單 一的節點控制器執行存取控制。 請注意，在本發明的某些實施例中，作業系統可選擇將 實體系統記憶體的全部或部分分配給該遠端快取記憶體， 且不將任何實體系統記憶體分配給系統記憶體位址空間。 在此種實施例中，可使該系統記憶體位址空間侷限在被實 施為諸如一機架系統中的碟狀記憶體抽取盒的一個或多個 節點中，但是係將包含處理單元的其他節點中之該實體系 統記憶體分配為遠端快取記憶體。 如前文所述，與被分配為用來存放RMC 70的至少一部 分的一系統記憶體66相關聯之每一記憶體控制器64設有一 RMD 74，且該記憶體控制器64係將RMC 70中與其相關聯 的部分之内容記錄在該RMD 74中#。如同傳統的快取記憶 體目錄，RMD 74最好是不只儲存與RMC 70中的資料有關 的位址資訊，而且也儲存一貫性資訊、取代資訊、及或有 的額外狀態資訊例如蘊含性。 為了支援記憶體控制器64對RMD 74的迅速存取，可如 -15- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐） 1237181 A7 B7 五、發明説明（13 ) 圖2A所示以高速SRAM來實施RMD 74。此種實施例可促進 對要求回應而進行迅速的目錄查詢，而有利地減少存取延 遲時間。然而，如同RMC 70，將SRAM用於RMD 74時，將 是高成本的，且將限制實際系統的RMD 74(及相關的RMC 70)之容量。可採用兩種不同的方式來解決這些顧慮之 處。 首先，如果係以SRAM(或其他高成本的儲存技術）來實 施RMD 74，則RMD 74可採用較大的區段（亦即，使較大的 資料區段與每一組標記及軟體指令相關聯），因而將SRAM 儲存容量的使用最佳化。以圖2B所示的NUMA電腦系統 (5 0’）例示之一第二種方式係將RMD 74連同RMC 70包含在 系統記憶體66中。在此種方式下，可大幅降低RMD 74的 實施成本，或者可在不增加額外成本的情形下大幅增加 RMD 74及RMC 70的容量。雖然將RMD 74包含在系統記憶 體66的DRAM内可能導致較緩慢的目錄存取時間，但是如 圖3所示，使RMC控制器73設有其中存放最近存取的（因而 有可能教要被存取的）目錄資料項之一小型目錄快取記憶 體75，即可減輕上述額外的目錄存取延遲時間。 NUMA電腦系統50的作業系統分配給RMD 74及/或RMC 70的系統記憶體66量是一重要的效能考慮點，這是因為分 配較大的RMC 70及RMD 74時，必然將減少系統記憶體位 址空間68。在一較佳實施例中，可根據所執行應用程式的 需求，而動態地改變分配給RMC 70及RMD 74的系統記憶 體66與系統記憶體位址空間68間之比率。例如，如果作業 -16- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐） 1237181 A7 B7 五、發明説明（14 ) 系統偵測到一應用程式將只需要存取將要用來執行該應用 程式的節點52内之記憶體，則作業系統可將一個比系統記 憶體位址空間68小許多的空間分配給RMC 70(及其相關聯 的RMD 74)。相反地，如果作業系統偵測到一應用程式將 需要對遠端記憶體進行相當多的存取，則作業系統可將系 統記憶體的一較大部分分配給RMC 70(及其相關聯的RMD 74) 〇 可根據兩種替代的方法來安排存放在各RMC 70(及RMD 74)的内容。首先，可將各RMC 70實施為内容蘊含式（或虛 擬内容蘊含式）快取記憶體，用以全體地儲存區域快取記 憶體階層62中來自其他節點的資料之超集合。在該實施例 中，當自其他節點52接收到所要求的快取線時，係將該等 快取線載入一節點52的R M C 7 0中。在替代實施例中，可 將各R M C 7 0實施為π取代式快取記憶體"，該取代式快取 記憶體只存放已自區域快取記憶體階層62解除分配的處於 共用或經過修改的一貫性狀態的遠端資料之快取線。 記憶體一貫性 因為NUMA電腦系統50内的任一 CPU 60通常都可要求、 存取、及修改每一系統記憶體66内儲存的資料，所以 NUMA電腦系統50(或50’）實施一種或多種快取記憶體一貫 性協定，來保持各節點52中的快取記憶體階層62與RMC 70間之一貫性（亦即，一貫性地檢視系統記憶體位址空間 68的整體内容）。因此，適當地將NUMA電腦系統50歸類為 CC-NUMA電腦系統。該快取記憶體一貫性協定係與實施 -17- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐） 1237181 A7 B7 五、發明説明（15 ) 例無關的，且可包含諸如習知的MESI (Modified，Exclusive, Shared, Invalid ;經過修改的、獨有的、共用的、無效的） 協定、或該協定之變形。熟習此項技藝者當可了解，快取 記憶體階層62所採用的一貫性協定需要經由區域連接裝置 58及節點連接裝置55傳輸各種與實施例無關的訊息，以便 取得所需的資料及指令，將經過修改的資料寫回到系統記 憶體66，並執行為了維持一貫性所需的其他功能。 為了維持各節點間之一貫性，系統記憶體控制器7 1在 LMD 72内儲存自相關聯的系統記憶體位址空間68取出到 各遠端節點52的資料（亦即快取線）的系統記憶體位址之指 示。在保持小容量的目錄是重要考慮點的低階實施例中， LMD 72可以使每一資料單位只與該資料單位是否被”取出 ”到至少一個遠端節點52的寬鬆之指示相關聯。替代性 地，在高階實施例中，LMD 72最好是以與每一資料單位 相關聯之方式儲存每一遠端節點52上的快取線的一貫性狀 態之一指示。根據本發明一實施例而在LMD 72的各資料 項中存放的每一節點之一貫性狀態包含表1所概述的狀 態。 -18- 本纸張尺度適用中國國家標準(CNS) A4規格(210X 297公釐） 裝 訂

線 1237181 A7 B7 五、發明説明（16 )

[ip— 卜貫性 目錄狀態 — 區域快取 記憶體中 可能的狀態 表I "一 遠端快取 記憶體中 可能的狀怨 意義 I • ,v""" - I jyl、Ε、或I 可在一遠端節點上修改| 與本地節點上的系統記 憶體有關的快取線。I 共用的(s) ---__ S或I S或I 一 可在遠端節點上非唯一 地存放快取線。 無效的(I) L_I_ Μ、E、S、或I I 任何遠端節點都不存放 快取線。 I 如表I所示，縱使在高階實施例中，可在某種不嚴密的 程度下規定遠端處理節點所存放的快取線的一貫性狀賤之 訊息。如下文中將參照圖7及8所述的，此種不1密的=度 係取決於孩一貫性協定的實施例是否容許存放在遠端的一 快取線在不通知本地節點上的LMD 72之情形下自s轉變為 I、自E轉變為I、或自e轉變為Μ。 在本發明的一較佳實施例中，如圖2八及2]5所示，係以 高速SRAM來實施LMD 72。然而’請注意，亦可替代性地 將LMD 72連同RMC川及/或謂㈣包含在系統記憶體^ 中。然而’不太有誘因將LMD 72包含在系統記憶體^ 中，這是因為如此實施時，並不會因有助於得到較大的 RMC 70及RMD 74而減少遠端記憶體的平 間。此外，將…包含在系統記憶體 -19-

1237181

統!己憶體66之存取時間幾乎加倍，這是因為將需要 取時間來查詢LMD 72,且將需要有一相同的第 間來自系統記憶體位址空間68取得所需的資料。 . 1取記憶體組鏃 現在請參閱圖4，®巾示出可在快取記憶體階層62内實 施的一例示較低階快取記憶體132之方塊圖。可以類似之 方式建，構快取記憶體階層62内的其他較高階快取記憶體。 如圖所示，快取記憶體132包含資料儲存單元13〇、一快 取圮憶體目錄140、及一快取記憶體控制器156。最好是將 貧料儲存單元130實施為被組織成若干一致的類別且每一 類別包含複數個快取線之一組關聯式陣列。用來記錄資料 儲存單元130的内容及相關聯之狀態資訊的快取記憶體目 錄140包含若干組142，且每一組142對應於資料儲存單元 130内的一個一致類別。每一組142包含若干目錄資料項 M4，用以儲存資料儲存單元13〇中與該組ι42相關聯的該 一致類別内的一對應的快取線之位址標記及一貫性狀態。 快取記憶體目錄140具有相關聯的LRU邏輯電路150 ,用 以儲存資料儲存單元13〇的每一個一致類別内的每一資料 項最近被存取情形之一指示。LRU邏輯電路150内與每一 個致類別相關聯的該指示因而指示了最近最少被存取的 成員、第二最近最少被存取的成員、及第三最近最少被存 取的成員等。 在作業中，快取記憶體132自與其相關聯的CPU 60可能 經由一較高階快取記憶體及區域連接裝置58接收與快取記 -20- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐) 1237181 A7 B7 五、發明説明（18 ) 憶體作業要求相關聯的要求位址。該等要求位址包括高階 標記位元、中階索引位元、及低階偏移量位元。如圖4所 示’快取記憶體132所接收的每一要求位址之索引位元被 輸入到快取記憶體目錄140及LRU邏輯電路150。LRU邏輯 電路15 0回應接收到該等索引位元，而輸出一經過解碼的 CASTOUT一VICTIM信號152，用以指示所選擇的該一致類 別中回應該快取記憶體作業要求而可能被取代的一成員。 CASTOUT-VICTIM信號152被輸入到快取記憶體控制器 156及一多工器154。 該要求位址的該等索引位元選擇快取記憶體目錄14〇内 的一組142。然後利用比較器146將所選擇組142的每一資 料項144内儲存之該標記T各別地與該要求位址的該等標記 位元比較，而每一次的比較將產生一個1位元的比對指 示。比較器146所輸出的該等位元合而形成一經過解碼的 HIT/MISS信號148，而該HIT/MISS信號148被輸入到快取 記憶體控制器156、多工器154、及邏輯”或”閘153。邏輯 ”或”閘153在邏輯上合併該HIT/MISS信號148，以便產生一 選擇信號，該選擇信號回應一命中而選擇HIT/MISS信號 148作為多工器154之輸出，並回應一未命中而選擇 CASTOUT—VICTIM信號152作為多工器154之輸出。多工器 154之輸出形成一經過解碼的SELECT信號155。 在比較器146對該等標記位元進行比較之同時，將所選 擇的組142的每一資料項内儲存的一貫性狀態（CS)及標記 (T)輸入到多工器147。如果該要求位址命中快取記憶體目 -21- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐） 1237181 A7 B7 五、發明説明（19 錄140，則SELECT信號155選擇與相符的成員相關聯的一 男性狀怨及物τ 5己作為多工器14 7之輸出；如果該要求位址 並未命中快取記憶體目錄140，則SELECT信號155選擇與 最近最少使用的（LRU)成員相關聯之一貫性狀態及標記作 為多工器147之輸出。然後將所選擇的一貫性狀態及標記 149輸入到快取記憶體控制器156。

裝 訂

快取記憶體控制器156回應接收到該快取記憶體作業要 求、HIT/MISS #號148、一貫性狀態及標記149、以及 CASTOUT一VICTIM信號152，而使該要求在該快取記憶體 控制器的其中一個要求佇列134内等候，並執行適當的資 料處理及目錄更新作業。例如，快取記憶體控制器156回 應相關聯的CPU 60所提出的一讀取類型要求並未命中快取 1己憶體目錄140，而將其中包含該要求位址的對該快取線 之一要求放置在區域連接裝置58，然後於自一區域快取記 憶體階層62、區域系統記憶體68、或其他節點52接收到所 要求的資料時’將所要求的資料供應到相關聯的CPU 60， 並將所要求的快取線儲存在CASTOUT_VICTIM信號152所 指定的一致類別成員。此外，快取記憶體控制器丨56回應 相關聯的CPU 60所提出的一讀取要求命中快取記憶體目錄 140，而自資料儲存單元13〇讀出所要求的資料，並將該資 料供應到该相關聯的CPU 60。當對一快取記憶體作業要求 的服務需要存取或取代一快取線時，快取記憶體控制器 156產生一 LRU—UPDATE信號158 ,而LRU邏輯電路150利用 該LRU—UPDATE信號158來更新與所存取的該_致類別相 -22·

1237181 A7 B7

關聯之LRU指示 。如將於下文中說明的，快取記 明的，快取記憶體控制

處理作業。 遠端讀取類型作翠

圖中示出用來根據本發明而服務一 的一方法之高階邏輯流程圖。圖5所 π :私序開始於步騾1〇〇，然後進入步騾1〇1，此時numa 電腦系統50(或50·)的其中一個節點52中之一最低階快取記 隐把132自相關聯的CPU 6〇接收對資料或指令（後文中將簡 單地稱為資料”）的一要求。在最低階快取記憶體132接收 到β要求時指示該要求未命中快取記憶體階層62的較高階 快取記憶體。 如以文所述’最低階快取記憶體132回應接收到該要 求，而在步驟1〇2中決定該要求是否命中最低階快取記憶 體132。如果確係如此，則快取記憶體控制器I%在步驟 103中將所要求的資料供應到CPU 60，而服務該要求，然 後本私序終止於步驟1丨8。然而，如果在步驟1 〇2中決定該 要求並未命中最低階快取記憶體Π2，則最低階快取記憶 體132的快取記憶體控制器156在步驟1〇4中於其區域連接 裝置58上發出一個目標針對所要求的資料之一讀取類型要 求（例如，對一載入要求的一讀取、或對一儲存要求的一 思圖修改之謂取（Read-With-Intent-To-Modify ;簡稱 RWITM) 〇 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 1237181 A7 -—__ _B7 五、發明説明（21 ) 圖6示出根據本發明的讀取類型要求之一實施例。如圖 所π ’该謂取類型要求包含諸如來源及目的地標記欄位 U 9及120、位址及同位攔位12丨及122、以及用來指示作業 的大小及類型（例如，READ或RWITM)的一交易描述碼攔 位124等的傳統攔位。此外，該讀取類型要求可包含一將 於下文中參照圖15A- 15C而說明的預先提取櫚位128。此 外，根據本發明，該讀取類型要求包含一節點控制器佇列 (Node Controller Queue ;簡稱 NCQ)旗標 126，用以指示是 否應將该碩取類型要求放入區域節點控制器56的其中_個 佇列57中等候。根據本發明，首先（諸如步驟1〇4所示）發出 NCQ欄位126被設定為〇的該讀取類型要求，以便指示節點 控制器56不要使該讀取類型要求在佇列中等候，而減少節 點控制器56的各佇列57内作業之懸而未決的情形。 即 請參閱圖5,本程序繼續自步驟1〇4進入步驟1〇6，此時 其他的區域快取記憶體階層62、記憶體控制器64、及節點 控制器56皆監視該讀取類型要求，並提供適當的監视回 應。該等可能的監視回應最好是包含下表„所二出:監二 -24-

l237l8l

五、 發明説明（ 22

共用式介入

快取線在快取記憶體諸被修改過，且將該快取線自 快取記憶體傳送巧舞出要求的來_ 快取線在快取記憶體諸未被修改過(且可能是共用 的）’且將該快取線自快取記憶體傳送到提出要求的 來源。 中。 快取線在快取記憶體中是^7^ ^ ^要的是：雖然區域節點控制器56將—"遠端位址 回應提供給對以另一節點作為本地節點的資现視 要求’但是節點控制器56並不立即將此種讀取類型 置在:個其仵列57中等候，以便傳送到遠端節點% ^放 為琢謂取類型要求的NCQ欄位126係被設定為〇。 疋因 如步驟108所示，發出該讀取類型要求的介面 足回應邏輯電路63合併所有該等監視回應，以便產生—中 來指示將如何服務該要求(例如’藉由指示最 二 的監視回應的方式）之合併回應。介面單元Μ將該〜貝序 應供應到區域連接裝置58上的每一監視裝置，其中=开回 出要求的快取記憶體階層62。如果該合併回應指示=提 址命中可用來作為所要求的資料的一來源之_:仫 憶體階層62或RMC 70，則該程序繼續自步驟! 记 %八步驟 ____-25- ^紙張尺“用A4規格(21()><297公爱） 1237181 A7 -- --- - B7 五、發明説明（23~J ~ -- 110此時s區域快取記憶體階層62或rmc 服務該讀取 類型要求。本程序然後終止於步驟118。 一回到步騾108，如果該讀取類型要求的合併回應是一指 π並無任何區域快取記憶體階層62或RMC 70可用來作為 所要求的資料的一來源之"遠端位址，，合併回應，則提出要 求的陕取名憶體階層62中之最低階快取記憶體的快取 記憶體，控制器I56在步驟i U中在區域連接裝置58上重新發 f NCQ旗標126被設定為丨之讀取類型要求。如前文所述， 每里視裝置將一監視回應提供給該讀取類型要求，且介 面單兀65提供一合併回應。然而，如步驟丨14所示，當節 點控制器56再度監視到該讀取類型要求時，因為ncq欄位 I26被設定為1，所以節點控制器56將該要求放置在其中一 個該節點控制器的佇列57中等候，以便傳送到該要求位址 的本地節點52。在將該讀取類型要求放置在佇列中等候之 後’印點控制器56將該讀取類型要求傳送到該本地節點 52 ’以便在無須等候第二合併回應的情形下進行服務。 (節點把制器5 6不需要等候接收該合併回應，這是因為 NCQ攔位126業已經指示節點控制器56必須處理對該讀取 類型要求之服務。）如步驟116所示，該本地節點52將所要 求的資料經由節點連接裝置55而供應到節點控制器56，節 點控制器56又將所要求的資料經由區域連接裝置58而供應 到提出要求的快取記憶體階層62(及RMC 70(在被實施為一 内容蕴含式快取記憶體之情形下）），而服務該要求。本程 序然後終止於步騾118。 -26- Ϊ紙張尺度適用中國國家標準(CNS)—M規格(21()χ297公爱) 1237181 A7

1237181 A7 — ___B7 五、發明説明（25 ) 各節點52之間傳輸的各讀取類型要求之服務增加了额外的 位址至合併回應的延遲時間。然而，在有大量7〇的 情形下，此種要求是相當少的。此外，因為與必須傳送到 本地節點的服務要求相關聯之延遲時間通常是相當長，所 以在遠端節點造成額外的位址至合併回應的延遲時間時並 不會嚴重影響到效能。 最後，熟習此項技藝者當可了解，圖5之方法並不限於 NUMA電腦系統。相反地，本發明大致適用於具有階層式 連接架構的SMP電腦系統、及各監視裝置間之通訊延遲時 間不均勻的其他電腦系統。 兹取線解险分配 當如圖5的步驟114及116所示自另一節點52要求並接收 一快取線時，必須自提出要求的快取記憶體階層62及/或 RMC 70將一快取線解除分配，以便容納新的快取線。與 前文所述的各遠端節點必然沈默地將為經過修改的各快取 線解除分配之先前技藝NUMA電腦系統不同，根據本發明 的NUMA電腦系統取好是實施一種解除分配作業，該解 除分配作業在一遠端節點將自一本地節點取出的一快=線 解除分配時，可讓該遠端節點通知該本地節點。因此，本 發明可讓LMD 72存放與來自相關聯的系統記憶體位址空 間6 8且係存放在遠端節點5 2的資料有關的更精確之資訊。 現在請參閱圖7及8，圖中示出根據本發明一較佳實施例 而將來自一 RMC 70的一解除分配的方法之高階邏輯流程 圖，其中係將RMC 70實施為一”取代式快取記憶體，，，用 -28- 本紙張尺度適用中國國家標準(CNS) A4規格(21〇 X 297公爱） Ϊ237181

五、發明説明（ 26 以儲存自區域快取記憶體階層62解除分配的遠端資料。然 而 4 έ此項技藝者當可了解，所示之該解除分配程序亦 適用於RMC 70蘊含了區域快取記憶體階層62中存放的遠 端資料之實施例。 雙先請參閱圖7，本程序開始於步騾丨70，然後本程序繼 續進入步騾172，此時控制一 RMC 7〇的一記憶體控制器64 之RMC控制器73諸如根據哪一快取線是最近最少使用的 (Least Recently Used ;簡稱 LRU)、最近最常使用的（Most Recently Used ;簡稱MRU)、隨機選擇、或其他要被取代 的快取線選擇準則’而選擇一個要被取代的快取線，以供 解除分配。在步驟174中，RMC控制器73然後根據RMD 74 中記錄的一貫性狀態，而將要被取代的快取線解除分配。 如果RMD 74指示該要被取代的快取線之一貫性狀態是無 效的’則只須以所要求的資料蓋寫該要被取代的快取線， 而無須將任何通知提供給本地節點52。因此，本程序直接 自步騾174進入步驟190，且結束了本程序。 另一方面，如果RMD 74指示相對於本地節點52上的系 統記憶體位址空間68中存放的對應資料而已經修改了所選 擇的要被取代的快取線，則記憶體控制器64在步驟丨76中 開始一個對已修改的資料之解除分配程序，且下文中將參 照圖8而詳纟田說明該解除分配程序。最後，如果rmd 74指 示該要被取代的快取線係處於一共用的一貫性狀態（亦 即，亦可將該要被取代的快取線在本地緩衝儲存在一快取 記憶體階層62，且如果確係如此，則對本地節點52中的系 -29- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 1237181 A7 -------_____ B7 五、發明説明（27 ) 統記憶體66而言並未修拎#西、丄# 1 /文舔要被取代的快取線），則， 體控制器64可通知本地節點φ脊 心 也即點中與存放有被解除分配的快取 線的-份拷貝的系統記憶體66相關聯之記憶體控制器“， 且縱使該通知衫是在轉—貫性上有絕對的必要，也可 進行該通知。 如步騾178所示，記憶體控制器64在區域連接裝置“上 發出〜有位址的解除分配作|，而開始自遠端快取記憶體 70將一共用的要被取代之快取線解除分配。節點控制器56 回應監視到該只有位址的解除分配作業，而將該作業放置 在佇列中等候，且區域快取記憶體階層62及其他的監視裝 置在步驟180中提供該解除分配作業的一監視回應，用以 指示該要被取代的快取線新對於快取記憶體階層62的一貫 性狀態（通常為一共用的或無效的狀態）。發出該解除分配 作業的介面單元65中之回應邏輯電路合併這些監視回應， 以便產生一合併回應，然後將該合併回應提供給韓合到區 域連接裝置58的所有監視裝置。如步驟182所示，如果該 合併回應指示一個或多個區域快取記憶體階層62儲存了處 於一共用狀態的要被取代的快取線，則本程序終止於步驟 190 ’而指示可在無須通知本地節點52的情形下自7〇 將該要被取代的快取線解除分配。因為不需要對本地節點 52的LMD 72進行任何更新，所以不將任何通知提供給該 本地節點。 然而，如果該合併回應指示並未在一共用狀態下在本地 緩衝儲存該要被取代的快取線（亦即，該合併回應是空 -30- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐) 1237181

則區域節點控制器56在步驟184中將在仵列中等候的 =有位址之解除分配作業傳送到本地節點52的節點控制 為，且不將該解除分配作業放置在传列中等候。本地節 點52上的節點控制器兄然後在其區域連接裝置％上發出只 有位址的解除分配作業。如步騾186所示，負貴該要被取 代的快取線的位址之記憶體控制器64將對應於LMD 72中 處於共用狀態的該要被取代的快取線之資料項更新為無效 狀怨，以便指不該特定的遠端節點52不再緩衝儲存該要被 取代的快取線。然後，圖7所示之本程序終止於步驟19〇。 現在請參閱圖8，圖中示出用來根據本發明而自一 70將一經過修改的快取線解除分配之一例示方法。在所示 實施例中，假設快取記憶體階層62及RMC %所實施的一 貝性協定是其中包含一標記（Tagged ;簡稱τ) 一貫性狀態 的習知MESI協定之一變形。如讓到給本發明的受讓人且 為本發明所引用以供參照的美國專利申請案〇9/〇24,393所 述，該標記（Τ) 一貫性狀態指示了 ：（1)相對於系統記憶體 而修改了一快取線；（2)可將該快取線存放在與不同的處 理單元相關聯之多個快取記憶體中；以及（3)用來存放處 於Τ狀態的該快取線之快取記憶體目前負責將該快取線寫 回到系統記憶體。 圖8所示之本程序開始於步驟200，然後如圖7之步驟 172-174所示，決定被選擇要分配給的RMC 70中之一要被 取代的快取線是一經過修改的快取線。本程序然後繼續進 入步驟202，此時與該RMC 70相關聯的RMC控制器73在區 -31- 尺度適用中國國家標準(CNS) Α4規格(210χ 297公爱)

裝 訂

線 1237181 A7 B7 五、發明説明（29 域連接裝置58上發出一逐出寫入作業。 如圖9所示’根據本發明的_逐出寫入作業24〇可包冬諸 如來源及目的地標記欄位241及242、位址及位址同位搁位 243及244、以及用來指示作業的大小及類型的_交易描述 碼欄位246等的傳統欄位。此外，如將於下文中進一步說 明的，菘逐出窝入作業可包含一共用（s)旗標248，且可設 定該共'用（S)旗標248，以便指示當在一區域連接裝置58^ 發出一共用監視回應時該逐出寫入作業是否接收到該共用 監視回應。最後’該逐出窝人作業包含—用來存放該經過 修改的要被取代之快取線的資料欄位25〇、及一相關聯的 資料同位攔位252。 如步驟204所示，耦合到區域連接裝置58的每一監視裝 置回應監視到㈣出寫入作t，而提供一監視回應7而對 於快取記憶體階層62而言，該監視回應係用來指示該要被 取代的快取線在每一監視裝置上的一貫性狀態。此外，節 點控制器56將該逐出寫入作業放置在佇列57中等候。如前 文所述與發出该逐出寫入作業的記憶體控制器Μ相關聯 的介面單元65内之回應邏輯電路63合併該等監視回應，以 便產生一合併回應，並將該合併回應提供給所有的該等監 視裝置。如果該合併回應是一重新嘗試合併回應，則本程 序回到已經說明過的步驟202。然而，如果該合併回應並 不是重新嘗試，則節點控制器56根據該合併回應而設定被 放置在佇列中等候的該逐出寫入作業之共用旗標248。因 此，如果如步驟208所示，該合併回應是共用合併回應， -32- 本紙張尺度適用中國國家標準(CNS) Α4規格(21〇χ 297公釐) 1237181

而f示^中一個快取記憶體階層62存放有標記（T) 一貫性 “斤谷許的為經過修改的要被取代的快取線之一份拷 貝，則節點控制器56將該共用旗標248設定為i。另—方 面，如果並未有任何區域快取記憶體階層62存放有該要被 取代的快取線之一份有效拷貞，則節·點控制器56接收一空 的合併回應，並在步騾210中因應地將共用旗標248設定為 0 〇 如步驟212所示，節點控制器56然後不將該逐出寫入作 業放置在佇列中等候，並將該逐出.窝入作業傳送到該要被 取代的快取線之本地節點52。本地節點52接收到該逐出寫 入作業之後，在本地節點52上的節點控制器56在本地節點 52的區域連接裝置58上發出該逐出窝入作業。如步驟213 所7F，負責泫要被取代的快取線的位址之記憶體控制器 回應茲逐出寫入作業，而以該逐出的資料來更新系統記憶 體位址空間68。此外，記憶體控制器64根據共用旗標248 的狀態而更新LMD 72中的該遠端節點52之相關聯的一貫 性狀怨。因此，如步驟218所示，如果共用旗標248被設定 為1，則圮憶體控制器64將先前發出該逐出寫入作業的遠 端節點52上的要被取代的快取線之一貫性狀態設定為共用 狀怨。此外，如步驟216所示，如果共用旗標248被設定為 〇，則記憶體控制器64將遠端節點52上的該要被取代的快 取線之一貝性狀態更新為無效狀態。然後，圖8所示之該 解除分配程序終止於步騾220。 因此，藉由實施圖7及8所示的這兩種解除分配程序或其 -33- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐)

裝 訂

線 1237181 A7

中I 將可大幅降低本地節點52上的記憶體栌制哭 64(回應RWITM要求而、脾了 ♦ 丨〜把&制斋 節㈣之可能性。因」:需要的使無效作業傳送到遠端 因此’提昇了多個節點52間有時合 的快取線的儲存作業之平祕$呼Θ共用 一、口 千均效把。亦請注意，可將圖7所 Κ ’、址的冑除分配作業實&為一較弱(亦即不嚴穷 的)作業。例如，如果發出該只有位址的解除分配作業： =控制器64接收到-預定數目以上的重新嘗試監視回 ^貝、己憶體控制器64可中斷對該解除分配作業的重新嘗 弋在此種方式下，效能將不會碰到將造成重新嘗試合併 回應的動態狀況。 口 1域記憶體目錄雒卞t 在，發明的某些實施例中，除了圖7及8所示之方法之 σ此希i κ施一種用來將遠端存放的快取線解除分配 的替代或額外之方法。更具體而言，如果並未實施圖7及8 所除分配方法，及/或各RMC 7〇是相當大，則可在 一遠端節點已停止要求存取一快取線之後的很長的一段時 間中，仍然可將該快取線存放在該遠端節點（或者至少在 本地節點的LMD 72中指示該快取線係存放在該遠端節 ‘”’占）因此，本發明認為：最好是將非經要求的清除作業 發出到遠端節點，而實施某種可減少因對存放在遠端節點 的資料進行使無效作業而延遲了獨有式作業（例如rwitm 要求）的頻度之機制。 根據圖3所示的本發明之一較佳實施例，係將該機制實 施為兄憶體控制器64的系統記憶體控制器7丨内的目錄，，清 ___— -34- I紙張尺度適财g sT^(CNS) A4規格(21GX 297公爱)

裝 訂

線 1237181

1237181

續進入步驟268’此時‘系統記憶體控制器7i讀取lmd 由目錄貝料項指標指示的一目錄資科項。如果^顧72 中之該目錄資㈣(例如，藉由_2中之一無效狀態)指 不相關聯的資料並未被存放在任何遠端節點52，則本程序 直接進入將於下文中雄日3的半” 人Υ $明的步驟274。然而，如果自[ΜΕ) 72讀取的該目錄資料指示至少_個遠端節點咖能存放 相關聯，的資料之-份拷貝，則本程序繼續自步驟27〇進入 步驟272。在步驟272中，系統記憶體控制器71在其區域連 接裝置58上發出一只有位址的清除查詢。區域節點控制器 56監視到該清除查詢，且節點控制器72的資 料項中所存放的資訊量，而將該清除查詢傳送到該清除查 詢中指定的每一遠端節點52、或所有的遠端節點52。在步驟272之後，系統記憶體控制器71遞增該目錄資料項指 標，以便指向RMC 70中之次一資料項。然後，本程序回 到步驟2 6 2 ’然後重複前文所述的各步驟。 現在請參閱圖10Β，圖中示出在一遠端節點52上的一 RMC控制器73根據本發明一較佳實施例而處理自本地節點 52發出的一只有位址的清除查詢所用的一例示方法之高階 邏輯流程圖。本程序開始於步驟3〇〇，且繼續進入步驟 3 02，此時本程序反覆，直到一記憶體控制器64監視到一 只有位址的清除查詢為止。本程序回應監視到一只有位址 的清除查詢，而繼續進入步驟3 04，此時記憶體控制器64 讀取由其RMD 74的清除查詢中之位址所識別之目錄資料 項。根據該目錄資料項所指示的一貫性狀態，記憶體控制 -36- 本紙張尺度適用中國國家標準(CNS) Α4規格(210 X 297公釐)

裝 訂

線 1237181 A7 ^_ B7 五、發明説明（34 ) 器64決定RMC 70是否存放了與該清除查詢位址相關聯的 有效資料。如果並非如此，則本程序回到已經說明過的步 驟 302。 回到步驟306，記憶體控制器64回應RMD 74中的該目錄 資料項指示RMC 70存放了與該清除查詢位址相關聯的一 有效快取線之一決定，而又在步驟308及3 10中決定是否要 將遠快取線解除分配。該決定可基於諸如遠端節點52現在 是否仍在使用該快取線、及/或記憶體控制器64是否具有 任何可使用的監視佇列、及/或其他的因素。在係將rMC 70實施為蘊含了區域快取記憶體階層62所存放的遠端資料 之本發明實施例中，記憶體控制器64可決定自RMD 74讀 取的該目錄資料項中的任何蘊含性位元是否被設定，而決 定是否現在仍然在使用被指示的該快取線。如果記憶體控 制器64(諸如因為仍然在使用該快取線，及/或沒有任何可 用的監視仔列’而）決定不要將該清除查詢中識別的快取 線解除分配’則不將所識別的該快取線解除分配，且本程 序只須回到已經說明過的步驟3〇2。 另一方面’如果遠端節點52中的記憶體控制器64決定要 將該快取線解除分配，則本程序進入步驟3丨2_3丨6 ,此時 將進行一快取線解除分配程序。根據所示之解除分配程 序’記憶體控制器64只須更新RMD 74中之目錄資料項， 而將並未被修改過的快取線解除分配；並不將辞何通知提 供給本地節點52。相反地，在rmD 74中使經過修改的快 取線無效’並也按照傳統的方式將該等經過修改的快取線 -37- 本紙張尺度適用中國國家標準(CNS)八4規_格(210>< 297公爱) 1237181 A7 ______ B7 五、發明説明（35 ) 寫回到本地節點52。當然，熟習此項技藝者當可了解，亦 可替代性地實施圖7及8所示之解除分配方法，以取代步驟 3 12-3 16所示之該解除分配裎床 +、、& π上 刀亂狂序。在該快取線解除分配程 序之後，圖10Β所示之該程序回到步騾3〇2。 圖1〇Α&1〇Β所示之該LMD清除程序能使低階及高階的 NUMA電腦系統得矛卜在成本是一主要考慮點的低階 NUMA電腦系統中，如果將各咖保持得較小是有利 的。因此’通常並不在該LMD維護緩衝儲存―快取線的遠 端拷貝的一個或多個節點之特定節點識別碼。因此，當要 求本地節穿古Ji的- #憶、體控帝j $回應對一快取線的唯一存 取的-要求而強制使該快取線無效(而且如果該快取線被 修改過，則又要強制將資料寫回到本地節點）時，該記憶 體控制器必須將一清除命令廣播到所有的其他節點，這是 因為該記憶體控制器並沒有哪些節點實際已存取該快取線 的任何記錄。圖10A及10B所示的該目錄清除方法因減少 了在-新的提出要求的裝置正在等候資料時必須廣播一要 求清除命令之機會’所以提昇了低階系統的效能。雖然本 發明之低階實施例仍然可&需要料除查詢I播到所有節 點，但是經常要在一後續的提出要求的裝置要求唯一存取 之前，即執行此種廣播。 在具有若干極大RMC的高階NUMA電腦系統中，利用清 除且珣知不需要的遠端存放的快取線解除分配所得到的效 益很f部分要歸功於該等RMC的管理。因為高階系統通常 具有若干極大的RMC，所以一特定節點中的各處理單元不 .38- 家標準(⑽）Μ規格(⑽X297公爱） 1237181 A7 B7 五、發明説明（30 ) --- 再而要的各快取線可在一段很長的時間中保留在該節點的 中而且在某些情形中，可能永遠不會被解除分配。 在此種凊形中，除了本發明之外，強制將一快取線自快取 記憶體取出的唯一方式就是：本地節點回應對該快取線的 唯一存取要求，而發出一要求清除命令。因此，本發明 微弱地’’強制各遠端節點使目前在LMD中被追蹤的一快取 線I各，份拷貝無效，因而當本地節點接收到對該快取線的 a的新的存取要求時，有較有可能可立即自系統記憶體取 得琢快取線，而無須相關聯的記憶體控制器先將要求清除 命令發出到一個或多個遠端節點。 亦凊；王意，在本發明的某些實施例中，快取記憶體階層 之决取α己憶體控制器15 6亦可監視清除查詢，並按照清 除旦珣而執行。然而，因為一快取記憶體階層62内的該清 除查詢的目標快取線出現時可能指示隨後可能會存取該資 料所以遵循清除查詢的效益在快取記憶體階層62中存放 有目標快取線的較高階快取記憶體中將會遞減。因此，例 如如果目標快取線只被存放在一 L3快取記憶體，則遵循 ⑺除查珣可能是明智的；但是如果該目標快取線（或其 一部分）被存放在相關聯的。或L1快取記憶體，則不必理 會該清除查詢。 分散t整體一貫性管理 如前文所述，本發明由於減少了節點控制器56將需要在 另一節點52接受服務的讀取類型作業放置在佇列中等候之 時間長度，而有利地減少節點控制器56中所需的佇列57數 _ - 3 9- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 2^17 1237181 A7 B7 五、發明説明（37 ) 目。本發明又使節點控制器56不必負責整體一貫性管理， 而進一步減少節點控制器56中所需的位址、資料、及命令 佇列57的數目。 在諸如圖1所示的NUMA電腦系統8等的先前技藝系統 中，當在節點連接裝置12上接收到一清除命令時，節點控 制器24即負貴確保在其節點1〇中成功地完成該清除命令。 因此，自經由節點連接裝置12接收到該清除命令至所有的 區域快取記憶體階層18及RMC 28使目標快取線的各份拷 貝（如果有這些拷貝）無效並將經過修改的資料（如果有經過 修改的資料）寫回到本地節點的這段時間中，節點控制器 24必須將遠清除命令儲放在該節點控制器的一個佇列32 中。我們當了解’在已知經由節點連接裝置12的通訊延遲 時間 < 情形下’上述的程序可能要耗用25〇〇或更多的時脈 週期。因此’縱然先前技藝的節點控制器24配備有若干較 木的仔列32 ’但在一貫性協定通訊量相當大的情形下，這 些仔列32仍有能成為效能上的瓶頸。為了解決效能瓶頸的 問過，本發明的一較佳實施例實施了一種採用RMC控制器 73的分散式一貫性管理。 I現在叫參閱圖11，圖中示出根據本發明而採用分散式一 貝丨ϊ理來處理清除命令的一較佳方法之高階邏輯流程 圖:在所示實施例中，假設每一節點52内的HMC 70全體 地^ 3 了區域快取記憶體階層62内緩衝儲存的來自其他節 點5 2之所有資料。 -斤示圖11所示之程序開始於步驟2 6 0，然後繼績

297公釐） 1237181

進入步驟262，此時_遠端節點52上的_節點控制器叫妾 收⑺除命令，琢清除命令指定該節點52中將要成為無效 々f夬取、、·泉之μ除位址，並指定如果有經過修改的資料 則將該經過修改的資料窝回到本地節點52。如前文所述， 本地節點52中6勺6己憶體控制器64通常回應接收到對在 LMD 72中私示為被取出"的一快取線之一驟I項要求， 而將此種/目除叩令發出到一個或多個遠端節點52。遠端節 點52上的節點控制器56回應接收到該清除命令，而將該清 除命令放置在佇列57中等候，並如步驟所示，在其區 域連接裝置58上傳送該清除命令。 每一區域記憶體控制器64回應監視到該清除命令，而提 供一監視回應。如步驟266所示，與目標位址所對映到的 RMC 70相關聯之記憶體控制器64(後文中將其稱為負貴的 圮憶體控制器）提供一用來指示該記憶體控制器64正在接 受該清除命令的一貫性管理貴任之監視回應（該監視回應 可以只是一個空的監視回應），並將該清除命令放置在該 記憶體控制器的一個佇列57中等候。節點控制器56合併這 些監視回應，以便產生一”接受清除”合併回應（例如一個 空的合併回應），且節點控制器56將該”接受清除，，合併回 應提供給所有的監視裝置。重要的是：因為該合併回應指 示負責的記憶體控制器64已接受確保將在該遠端節點52中 芫成茲清除命令的貴任，所以節點控制器56在步驟268中 將分配給該清除命令的佇列57解除分配，因而空出該資 源，而可用來處理其他的作業。 -41- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公爱) 1237181 A7 B7 五、發明説明（39 ) 然後，如步騾270所示，該負責的記憶體控制器64之 RMC控制器73查詢其RMD 74中之蘊含性資訊，而決定與 該清除位址相關聯的快取線之一份有效拷貝是否被存放在 任何區域快取記憶體階層62中。如果確係如此，則本程序 進入步騾272，此時RMC控制器73在區域連接裝置58上發 出該清除命令，以便強制使與該清除位址相關聯的快取線 的存放在本地之拷貝無效。快取記憶體階層62及其他記憶 體控制器64回應監視到該清除命令，而提供監視回應。如 前文所述，並朱存放有該目標快取線的一有效拷貝之各快 取記憶體階層62提供一空的監視回應，且存放有該目標快 取線的一份拷貝之各快取記憶體階層62在該目標快取線變 成無效之前，將一重新嘗試監視回應提供給該清除命令， 並且如果有經過修改的資料，則將該經過修改的資料寫回 到本地節點。與該負貴的記憶體控制器64相關聯的介面單 元65中之回應邏輯電路63合併這些監視回應。如步驟274 所示，如果該合併回應是一重新嘗試合併回應，而指示至 少有一個快取記憶體階層62仍然處於使目標快取線的拷貝 無效或將經過修改的資料寫回到本地節點52之程序中，則 本程序回到已經說明過的步驟272。然而，如果接收到了 一艾的合併回應，而指示在遠端節點52中完成了該清除程 序’則本程序自步騾274進入步驟275。 在步驟275中，RMC控制器73查詢RMD 74，而決定其相 關聯的RMC 70是否存放有該清除位址所識別的該快取線 之一有效拷貝。如果並非如此，則本程序進入將於下文中 ____ -42- 本紙張尺歧用巾S S家料(CNS) A4規格(210 X 297公爱) ·— 1237181 A7 B7 五、發明説明（40 ) 說明的步騾276。然而，如果rMc 70存放有該清除命令的 目標快取線之一有效拷貝，則RMC控制器73使RMC 70中 的該目標快取線無效，並且在步騾277中，在有經過修改 的資料的情形下，將該經過修改的資料寫回到本地節點52 中的系統記憶體。 本程序然後繼續自步騾277進入步驟276，此時RMC控制 器73在區域連接裝置58上發出一 Flush—Ack作業，以便指 不：已在本地完成了該清除作業，並將被分配於處理該清 除命令的佇列77解除分配。如步驟278所示，節點控制器 56簡單地將該Flush—Ack作業放置在佇列中等候，並將該 Hush—Ack作業傳送到本地節點52，以便向該本地節點: 冗憶體控制器64指示：已在遠端節點Μ上完成了該清除作 業。然後，圖11所示之程序終止於步驟28〇。 、 如圖η所示的程序顯示的，本發明增加了可同時服務的 整體-貫性管理作業數目，並將整體—貫性f理的責任自 節點控制器轉移到記憶體控制器，而可簡化節點控制器的 設計。在有由RMC控制器73提供的一組較大的佇 下，該實施例不只是可支搓*吾沾门仏 ^^ 疋』叉後大I的同時一貫性維護作業， 而且在處理單元54的數目増加時具有延展性 潛在的效能瓶頸。 奸沃f 全散式整體一貫性管玻 本：明不只是由各記憶體控制器促成了分散 理’提供了優於由一節點控制器執行的集中式一貫性； 理’而且也將對所選擇作業的整體一貫性任 '43- 1237181 A7 B7 五、發明説明（41 給多個控制益，以便促進對佇列資源作有效率的使用。 在諸如圖1所示NUMA電腦系統8等的先前技藝numa電 腦系統中，係在自一遠端節點接收到一要求至該遠端節點 成功地接收到所要求的快取線的這段時間中，係將本地節 點的節點控制器24内之一個一貫性管理佇列32分配給一讀 取類型要求（例如READ* RWITM)。該節點控制器必須在 整段持，績時間中保持該佇列的分配，這是因為在將前要求 的目標快取線傳送到本地節點之前，節點控制器24不容許 ▲本地節點發出一目“係針對同一快取線的一清除作業。 換吕之，為了維護先前技藝NUMA電腦系統中之整體一貫 性，該本地節點的節點控制器負責回應一第一要求、及因 一後續要求而產生的一清除作業，而嚴格地安排至一遠端 節點的資料傳送順序，且因而必須在所要求的資料被成功 地傳送到該遠端節點之前，都要保持將一佇列分配給該第 一要求。 本發明實施一種用來在各控制器之間轉移整體一貫性管 理責任的特殊命令（後文中稱為Numafy命令），而改良了前 文所述的先前技藝一貫性管理技術，因而不需要會妨礙先 前技藝NUMA電腦系統效能的排序及佇列等候要求。本發 明的Numafy命令的例示使用方式之時序圖係示於圖12。 現在請參閱圖12，圖中示出在NUMA電腦系統（5〇)的一 遠端節點及一本地節點的區域連接裝置上的各作業之時間 -空間圖，其中該等作業係用來服務該遠端節點所提出的 一項取類型要求。所示之該程序採用前文中參照圖5戶斤厂、 _ -44- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐)

裝 訂

線 1237181 A7 B7 五、發明説明（42 ) 之創新式讀取重新發出方法。 如圖所示，本程序開始時，一遠端節點52(在圖12中被 標示為節點1)中的一較低階快取記憶體132之一快取記憶 體控制器156在其區域連接裝置58上發出一讀取類型要求 (在此例中為一 RWITM要求300，以便可唯一地存取係為本 地節點52的另一節點之一快取線。如前文所述，快取記憶 體控制器156回應CPU儲存要求未命中其快取記憶體目錄 140，而發出RWITM要求300。在RWITM要求300内，NCQ 爛位126於開始時被設定為0’因而在決定於本地無法服務 RWITM要求300之前，區域節點控制器56不會將RWITM要 求300放置在佇列中等候。該RWITM要求也被放置在快取 記憶體控制器156的一個要求佇列134中等候。 耦合到區域連接裝置58的各監視裝置（亦即，各快取記 憶體控制器156、各記憶體控制器64、及節點控制器56回 應監視到RWITM要求300，而提供監視回應302，而發出 RWITM要求300的介面單元65中之回應邏輯電路63合併這 些監視回應302，以便產生一合併回應304，並將該合併回 應304提供給所有的監視裝置。圖12所示之該例示作業情 況假設合併回應304指示：節點1内並無任何監視裝置可對 目標快取線提供唯一的存取，且RWITM要求300的目標位 址是一遠端位址。具有該目標快取線的一共用拷貝之任何 其他區域快取記憶體階層62或RMC 70回應合併回應304， 而開始使其本身的該目標快取線拷貝無效之程序，且快取 記憶體控制器156重新發出NCQ欄位126被設定為1的一 -45- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐） 1237181 A7 B7 五、發明説明（43 ) RWITM要求306。耦合到區域連接裝置58的該等監視裝置 於回應該重新發出的RWITM要求306時，提供監視回應 3 08，且該等監視回應308被合併，以便產生一第二合併回 應 3 10。 如前文中參照圖5所述的，節點1之節點控制器56將該 RWITM要求傳送到節點2(亦即該目標快取線的本地節 點）’以便要求服務，並將一節點控制器確認訊息經由合 併回應3 10而提供給快取記憶體132，而指示已傳送了該要 求。快取記憶體控制器156於接收到合併回應310時，設定 與被放置在佇列中等候的該RWITM要求相關聯之一區域 旗標136。區域旗標136指示該快取記憶體132已取得該目 標快取線的區域所有權，並”保護”其對該目標快取線的所 有權，使該保護期間T0，不讓或有的後續要求該目標快取 線的其他本地提出要求的裝置取得該目標快取線之所有 權，其保護之方式為將重新嘗試監視回應提供給這些後續 的要求。然而，如果快取記憶體控制器156監視到來自該 本地節點的一清除作業，則快取記憶體控制器156將不理 會遠清除作業，這是因為快取記憶體13 2還沒有該目標快 取線的一有效拷貝、或該目標快取線的整體所有權。此 時，快取記憶體控制器156正在等候自該本地節點接收到 下列項目：（1)該目標快取線、以及（2)用來指示已授予該 目標快取線的整體所有權之一 Numafy命令。視動態作業狀 況而定’快取記憶體控制器15 6可以任何順序來接收該目 標快取線及該Numafy命令。 -46- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 1237181 A7 B7 五、發明説明（44 ) 如圖所示，節點2之節點控制器5 6回應經由節點連接裝 置55接收到該RWITM要求，而在節點2的區域連接裝置58 上發出一對應的RWITM要求320。節點2内的各監視裝置提 供適當的監視回應322，且節點控制器56合併該等監視回 應322，以便形成一合併回應324，用以指示與該目標快取 線資料所存放的系統記憶體位址空間68相關聯之記憶體控 制器64將服務RWITM要求320。一旦記憶體控制器64接受 RWITM要求320，且該記憶體控制器64的系統記憶體控制 器71將RWITM要求320放置在其一貫性管理佇列79中等候 之後，系統記憶體控制器71將一清除命令330發出到LMD 72指示存放了該目標快取線的一份拷貝的節點1以外的或 有之其他遠端節點52。此外，系統記憶體控制器71將一只 有位址的Numafy命令326發出到節點1，並派發一記憶體讀 取佇列，已將該所要求的資料供應到節點1。如果LMD 72 指示並不需要自一遠端節點52清除掉該目標快取線，則可 立即開始對系統記憶體位址空間68的讀取，並可在發出 Numafy命令326之前，即將目標快取線資料332供應到節點 1 ° 一旦發出了 Numafy命令326之後，即完成了任何必須的 清除作業，且開始系統記憶體讀取作業，系統記憶體控制 器71將該RWITM要求320視為已被服務過，然後縱然節點1 可能尚未接收到該目標快取線資料，也可將原先指定給 RWITM要求320的該一貫性管理佇列79重新分配給一後續 的要求。因此，與先前技藝不同的是：根據本發明，並不 -47- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐） 1237181 A7 ______B7 五、發明説明（45 ) 將授予一快取線的整體所有權與目標快取線資料332的傳 送這兩件事轉合在一起。 節點1的節點控制器56回應經由節點連接裝置55接收到 該只有位址的Numafy命令，而在區域連接裝置％上發出一 只有位址的Numafy命令340。當節點J的提出要求之快取記 憶體控制器156監視到只有位址的Numafy命令時，快取 記憶體，控制器156設定與該汉貿汀“要求相關聯的整體旗標 138。一個被設定的整體旗標138指示：提出要求的快取記 憶體132已接收到該目標快取線的整體所有權，且因而現 在必須在一第二保護期間丁丨中，不但要使其他的區域要求 無法取得該目標快取線的所有權，而且要使來自該本地節 點的任何清除（Flush)命令或清洗（clean)命令盔 標快取線的所有權。因此，在提出要求的法完= RWITM要求的服務時即結束的該保護期間τι中，提出要 求的快取記憶體控制器156必須將一重新嘗試監視回應提 供給自當地或自本地節點（亦即節點2)接收的任何清除、 清洗、或其他類似的作業。 一旦提出要求的快取記憶體控制器156接收到目 線資料342之後，快取記憶體控制器156即服務該待處理的 CPU儲存要求，並將其快取記憶體目錄14〇中的該目標快 取線之一貫性狀態更新為一經過修改的一貫性狀態。此 時，即完成了對該RWITM要求之服務，且快取記憶體控 制器156重定區域旗標136及整體旗標138。快取記憶體控 制器156然後將不把一重新嘗試監視回應提供給目標針對 -48- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公爱) 1237181 A7 __ _ B7 五、發明説明（46 ^ " " ^ 該目標快取線之清除或清洗命令，而是將轉而經過修改的 資料”推送”回該本地節點，而允准此種要求，並針對清除 命令而使該快取線的其本身之拷貝無效。 因此，圖12示出了一種將整體一貫性管理分散到一 NUMA電腦系統内的各控制器之方法，且該方法將系統層 級的一貫性管理貴任與所要求資料的傳送這兩件事分離， 而促進.了對系統記憶體控制器的一貫性管理佇列作更有效 率的使用。因此，只要該系統記憶體控制器涉及了服務一 要求，即將該系統記憶體控制器中的各佇列資源分配給該 要求’且隨後可在比先前技藝的系統早許多的時間上（亦 即，早了至少等於節點連接裝置55的延遲時間的時間，可 能早了 2000個或更多的時脈週期）將該等佇列資源用來服 務其他的要求。因此，只需較少的一貫性管理佇列，即可 支援一特定水準的效能。 LMD資料所有禮歷史 當一系統記憶體控制器7 1如圖12所示自一遠端節點接收 到一 RWITM要求時，系統記憶體控制器71必須將目標快取 線的系統層級之唯一所有權授予提出要求的節點，以便服 務该RWITM要求。然而’當系統記憶體控制器7谈收到對 一目標快取線的讀取要求時，系統記憶體控制器7丨可授予 該目標快取線的共用所有權或唯一所有權。 在諸如圖1所示的先前技藝Ν υ Μ A電腦系統中，如果 LMD 2 6指π該目標快取線被"取出”到任何的的遠端節點 10，則本地節點通常並不回應來自一遠端節點的_讀取要 -49- 本紙張尺度適用中國國家標準(CNS) Α4規格(210X297公爱) 1237181 A7 B7 五、發明説明（47 ) 求而授予唯一所有權。在此種方式下，可避免在一個或多 個遠端節點上的該目標快取線的共用拷貝之不必要的使無 效作業。然而’當L M D 2 6指示該目標快取線並未被 ’·取出"到一遠端節點10時，曾經採用了兩種實施例。 在第一先前技藝實施例中，該本地節點必然回應一讀取 要求，而將目標快取線的非唯一所有權授予一遠端節點。 雖然該實施例並不會造成對該目標快取線的存放在遠端的 拷貝之不必要的使無效作業，但是可能造成目標針對同一 快取線的後續儲存作業之較·長延遲時間，這是因為發出該 謂取要求的該遠端節點必須隨即發出一 RWITM要求以便 取得該目標快取線的唯一存取權。目標針對遠端資料的儲 存指令因而可能有較長的延遲時間（例如，2〇〇〇個或更多 的時脈週期）。 根據一第二先前技藝實施例，在LMD 26指示一目標快 取線並未被”取出，，到一遠端節點的情形下，總是回應讀取 要求而將該目標快取線的唯一所有權授予一遠端節點，即 可消除一儲存指令的效能下降。然而，因為不論具有唯一 所有權的第一遠端節點是否實際修改了該快取線，該本地 郎點總是必須要回應一第二遠端節點提出的一後續讀取要 求’而將一清洗作業（亦即，如果該快取線被修改過則強 制寫回該快取線但並不使該快取線無效的一種作業）發出 到該第一遠端節點，所以該第二實施例可能也會有問題。 因此’在許多情況中，該後續的讀取要求將非必要地被延 遲到該清洗作業完成為止。 - ___ -50- 本紙張尺度適用巾g g *標準(CNS) Μ規格(灿χ 公爱) 1237181 A7 -~----- B7_五、發明説明（明) 本發明由於維護每一 LMD資料項的某一節點之歷史資 訊=而克服了先前技藝的缺點，其中該歷史資訊指示回應 一遠端節點的一讀取要求時是要授予相關聯的快取線之唯 所有權或非唯一所有權。例如，在圖丨3所示之一較佳實 施例中，LMD 72諸的每一目錄資料項36〇包含每一節點的 一貫性狀態資訊362及每一節點的歷史資訊364。 熟I'此項技藝者當可了解，系統記憶體控制器7丨可根據 許多種適用方法中之一種方法來更新每一節點的歷史資訊 364。圖14示出用來更新歷史資訊364的一種較佳方法之狀 怨圖。在所7F之實施例中，系統記憶體控制器7丨維護每一 遠端節點的一個2位元之歷史指示，而提供了在圖14中標示 為歷史狀態A、B、C、及D的四種可能狀態。系統記憶體 控制器71回應自一遠端節點52接收的每一讀取類型要求 (例如，READ或RWITM)，而更新該遠端節點52之歷史狀 您、。當一遠輛節點52對存放在相關聯的系統記憶體位址空 間68的一快取線之資料的一讀取要求時，系統記憶體控制 器7 1即參照該快取線及遠端節點的歷史狀態，而決定要授 予該快取線之非唯一所有權或唯一所有權。例如，用來授 予所有權的該Numafy命令中之一唯一性旗標可指示系統記 憶體控制器71所授予的所有權之類型。 如圖14所示’系統記憶體控制器7丨將lmd 72的每一目 錄資料項360中之每一遠端節點52的歷史狀態之起始狀態 設定為歷史狀態A。然後，如自狀態a轉變為狀態b及狀態 B上的迴圈所示，系統記憶體控制器7丨將一快取線的非唯 -51- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐)

裝 訂

線 1237181 A7

一所有權授予一遠端節點52，直到該遠端節點52發出一 RWITM要求而取得該快取線的唯一所有權為止。 系統記憶體控制器71回應接收到一 RWITM要求，而授 予該目標快取線之唯-所有#，並將提出要求的該遠端節 點之歷史狀悲自任一可能的歷史狀態A_ D更新到狀態c。 如狀態C與D之間及狀態〇與B之間的可能轉變所示，系統 記憶體，控制器71隨即回應同一遠端節點52提出的多達兩個 的後續謂取要求，而授予該快取線之唯一所有權。如果自 同一遠端節點接收到對同一快取線的第三後續讀取要求， 則在該遠端節點再度發出對該快取線的一 RWITM要求之 前，系統記憶體控制器71只授予非唯一所有權。 藉由採用每一節點的歷史狀態資訊來決定要針對來自一 遠端節點的讀取要求而授予一目標快取線的唯一所有權或 非唯一所有權，與同一遠端節點内的後續儲存指令或其他 遠端節點的一讀取要求相關聯的不必要之延遲時間即可比 先削技藝有大幅的減少。因此，提昇了 NUMA電腦系統5〇 的整體效能。 資料及指令預先搓取 在諸如圖1所示NUMA電腦系統8等的先前技藝NUMA電 腦系統中，係由一 CPU的預先提取引擎發出資料及指令預 先提取要求，然後由由CPU的最低階内部快取記憶體之快 取記憶體控制器在區域連接裝置上發出對所要預先提取的 每一快取線之一讀取要求。對於較深的預先提取演算法而 言，該傳統的預先提取技術要求該快取記憶體控制器配備 -52- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐)

裝 訂

線 1237181

有大量的讀取仵列。在大型多處理器系統中，當然是要將 =源的成本乘以CPU晶片的數目，因而可能形成總系 統成本的一可觀部分。 視預先提取資料的來源(例如’是在區域系統記憶體， 返疋在另一即點中之系統記憶體)而《，處理器預先提取 要求的讀取仔列可能在一段長時間中保持在使用（忙碌）狀 怨。顯然自效能的觀點而論’最好是不要延遲對需求讀取 要求的服務，這是因為已將所有㈣取㈣分配給預先提 取要求4了解決需求讀取要求與預先提取讀取要求對讀 取仔列的爭奪，可設有一組獨立的預先提取讀取件列；然 此種作法可此產生額外的成本及複雜性，而且無法減 少分配給預先提取讀取要求的各佇列停留在忙碌狀態之 續時間。 本發明導人-種並非由快取記憶體控制器而是由記憶體 控制器產生預先提取作業之改良式預先提取技i根據本 發明’當提出要求的處理單元發出_起始需求資料載入或 指令提取時，即將預先提取示意資訊附加到讀取作業。該 ，意資訊可包括諸如要預先提取的快取線數目、及各快取 ’泉1之位址跨距。记憶體控制器回應接收到該讀取作業， 而利用預先提取示意資訊取得所需求的資料或指令，然後 利用寫入作業將@先提取的f料傳送到i出要求的處理單 元。 現在，月參閱圖15A，圖中示出一較低階快取記憶體132的 一快取記憶體控制器156根據本發明的預先提取技術而發

1237181

出具有-附加預先提取示意資訊的—需求讀取要求的一例 不万法之高階邏輯流程圖。如圖所示，該程序開始於步驟 jo’然後停留在步驟382中，直到快取記憶體控制器156 自其相關聯的CPU 60接收到一載入要求為止。，決取記憶體 控制器156回應接收到—載入要求，而在步驟384中決定^ 載入要求是否命中了其快取記憶體目錄刚。如果確係如 此，則快取記憶體控制器156在步騾386中 13。讀取所要求的資料，並將所要求的資料== 6〇 °本程序然後回到步驟382。 回到步騾384，快取記憶體控制器156回應該載入要求並 未命中快取記憶體目錄140的決定，而在步驟39〇及392中 根據該載入要求而建立一讀取要求，並將該預先提取要求 中或許包含的預先提取示意資訊附加到或包含到該讀取要 求内。如圖6所示，可在該讀取要求的一預先提取攔位128 中傳送該預先提取示意資訊，且該預先提取示意資訊可指 定所要預先提取的快取線之數目、及該等預先提取快取線 間之位址跨距。然後在步騾394中，快取記憶體控制器156 將一要求佇列134分配給該讀取要求，並在其區域連接裝 置58上發出該讀取要求，然後在步騾396中等候所要求資 料的送回。如前文中參照圖6所述，該讀取要求最好是包 含一來源標記欄位1 19，用以識別發出的快取記憶體控制 器156或其處理單元54。 如步驟398所示，當接收到作為該讀取要求的目標之所 要求的快取線時，快取記憶體控制器156將該快取線儲存 一 -54- ^紙張尺度適用中國國家標準(CNS) A4規格(210X297公爱了

裝 訂

1237181

、發明説明（ 52 :貝料儲存早兀130内，更新快取記憶體目錄140，將分配 ^讀取要求的要求侍列134解除分配，並將該載入要求 、，求的資料提供給相關聯的cpu 6〇。然後，圖Μ所示 之程序回到已經說明過的步驟3 82。 現在請參閱圖15B，圖中示出_記憶體控制器M回應其 中包括根據本發明的一預先提取示意資訊的一讀取要求所 用的一.例示方法之高階邏輯流程圖。如圖所示，本程序開 口於步驟400 ’然後在步驟4〇2中反覆，t到記憶體控制器 64(尤指系統記憶體控制器71)接收到一諸如在圖i5A所示 步驟3 94中發出的碩取要求為止。回應接收到一讀取要 求，本程序繼續進入步驟4〇4，此時系統記憶體控制器7工 查詢LMD 72而決定是否有一遠端節點52唯一地存放了該 讀取要求的目標快取線。如果並非如此，則本程序直接進 入步驟408。然而，如果LMD 72指示該目標快取線被唯一 地存放在遠端，則系統記憶體控制器71最好是根據前文中 參照圖11所述之程序，而自該遠端節點清除該快取線。 然後在步驟408中，系統記憶體控制器7丨自相關聯的系 統記憶體位址空間68讀取該目標快取線，並將所要求的該 快取線傳送到提出要求的快取記憶體132。此外，如步騾 4 10所示，系統記憶體控制器71決定該讀取要求的預先提 取欄位128中是否包含了 一預先提取示意資訊。如果並非 如此，則完成了對該讀取要求的服務，且本程序回到已經 說明過的步騾402。然而，如果該讀取要求的預先提取欄 位128中包含了 一預先提取示意資訊，則系統記憶體控制 -55- ^紙張尺度適财國S家標準(CNS) A4規格(⑽x 297公釐) 裝 訂 線 1237181 A7 I---------- -B7 五、發明説明（於) I分配給預先提取要求 ’列79，或者決定是否 。如果可分配給預先 系統記憶體控制器71 1序回到步騾402。因 要求的服務最好是不 可選擇提供預先提取 資訊，則並不重新嘗 佇列79分配給一預先 14，此時系統記憶體 提取佇列，以便服務 示，系統記憶體控制 空間68讀取預先提取 窆之一個或多個快取 的預先提取資料傳送 勺是：並非一讀取資 勺一預先提取寫入作 的快取記憶體132， 杈要求。為了確保正 范憶體控制器71將該 [於該寫入作業的位 I1該等快取線的預先 豐階層62之後，系統 本紙張尺度適财S S釋平(⑶^ Α4^^_χ297公《) '—

!237181 五、 發明說明（ 54 己$ 控制器71即將自各佇列79分配的該預先提取佇列解 余刀配’且本程序回到步騾402。 現在清參閱圖15c，圖中示出一提出要求的快取記憶體 根據本發明而處理一被監視的預先提取寫入作業所用的一 例示方法之高階邏輯流程圖。如圖所示，本程序開始於步 b 然後在步驟432中反覆，直到其中一個快取記憶體 =層62的一最低階快取記憶體132在其區域連接裝置“上 ^預先提取窝入作業為止。快取記憶體132的快取 :己憶體控制器156回應在區域連接裝置58上監視到一預先 、寫入作業，而檢查該預先提取寫入作業的目的地標記 ，二242則更在步驟434中決定該快取記憶體是否為該預 提取寫人作業的目標。如果並非如此，則本程序終止， 並回到步驟432。 、 回口到步驟434，如果目的地標記欄位242指示快取記憶體 132是被監視的該預先提取窝入作業之目標，則快取記憶 體控制器156決定是否可將其監視件列⑴(請參閱圖4)中之 -監視佇列分配給該預先提取寫入作業。如果可指定給預 先提取寫入作業的所有監視许列135都在忙碌中，叫本程 序終止，並回到步驟432，且指示快取記憶體控制器⑼不 接受㈣先提取資料，或者在沒有可用的監視仔列⑴之 情形下發出-重新嘗試監视回應。然而，如果可將其中一 個監視件列B5分配給該預先提取寫入作業，列快取纪惊 體控制器156在步驟4财將其中—個監視㈣135分配: 取窝入作業’㈣在步驟44〇中等候該快取線的 .57- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公袭·） 1237181

預先提取資料之傳送。然後，快取記憶體控制器156將該 預先提取資料儲存在資料儲存單元13〇，並適當地更新快 取记憶體目錄140。然後，快取記憶體控制器156在步驟 444中將分配給該預先提取寫入作業的監視佇列135解除分 配’且本程序回到已經說明過的步騾432。 圖15A- 15C所示之該預先提取方法有若干項勝過先前技 藝的優.點。在第一項優點中，本發明的預先提取方法由於 在提出要求的處理單元無須用到預先提取讀取佇列，而降 低了整體系統佇列成本。又加入了記憶體控制器佇列來處 理預先提取窝入作業，此種方式大致有較低的成本，且所 而的佇列數目少於在每一較低階快取記憶體中提供佇列之 方式。在第二項優點中，因為係以不嚴密的作業來實施預 先提取’所以在記憶體控制器或快取記憶體控制器忙碌的 情形下，可以安全地不理會預先提取示意資訊。因此，不 會有因回應重新嘗試回應而重新發出預先提取作業的匯流 排訊息流動。第三項優點，在本發明中，因為被分配用來 服務預先提取寫入作業的快取記憶體控制器的監視佇列之 忙碌持續時間遠短於先前技藝中採用的預先提取讀取佇列 之fc碌持續時間，所以各佇列被更有效率地使用。換言 之，與先前技藝中必須自發出預先提取讀取要求開始到自 系統記憶體接收到所要求的預先提取資料為止的這段時間 中保持在可用狀態的預先提取讀取佇列不同，在本發明 中，在監視到一預先提取窝入作業之前，一快取記憶體控 制器的監視仔列並不會被分配。 -58- 冢紙張尺度it财g g家標準(CNS) M規格(⑽χ 297公董) 1237181 A7 B7 五、發明説明（56 ) 結論 如前文所述，本發明提供了 一種具有更佳的資料儲存、 佇列、及通訊效率之NUMA電腦系統及作業方法。雖然已 參照一較佳實施例而詳細示出並說明了本發明，但是熟習 此項技藝者當可了解，在不脫離本發明的精神及範圍下， 尚可對本發明的形式及細節作出各種改變。例如，雖然在 本發明中係以組合的方式呈現對一 NUMA架構的若干強 化，但是我們當了解，亦可以獨立或次組合之方式實施每 一該等強化。 -59- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐)

Claims (1)

1. 8 8 8 8 A B c D 1237181 >、申請專利範圍 --- 種操作非均勻式記憶體存取（NUMA)電腦系统之方 法，該NUMA電腦系統包含由一節點連接裝置耦合之至 少一個本地節點及至少一個遠端節點，該方法包含下列 步騾： 回應在該本地節點上自一遠端節點接收到一資料要 求，而查珣用來指示該遠端節點中發出的先前資料存取 之歷史資訊，以便決定授予該資料要求中指定的所要求 貝料之唯一所有權或非唯一所有權；以及 將所要求的資料及唯一所有權或非唯一所有權之一指 示傳送到該遠端節點。 2. 如申請專利範圍第1項之方法，其中該傳送步驟包含下 列步驟·在各獨立的傳輸中，傳送所要求的該資料及唯 一所有權或非唯一所有權之該指示。 3. 如申請專利範圍第1項之方法，其中該本地節點包含一 本地系統記憶體及一相關聯的記憶體目錄，該方法進一 步包含下列步驟： 在該記憶體目錄中維護與所要求的該資料相關聯之歷 史資訊’其中該歷史資訊個別地指示每一遠端節點對所 要求的該資料之先前資料要求。 4. 如申請專利範圍第1項之方法，進一步包含下列步驟： 接收該資料要求，其中該資料要求是一讀取要求。 5·如申請專利範圍第1項之方法，該本地節點包含一本地 系統記憶體及一相關聯的記憶體目錄，其中 該方法進一步包含下列步驟：在該記憶體目錄中，記 •60- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐） 裝 訂 ^37181 中請專利範圍 AS B8 C8 D8 綠與所要求的該資科相關聯之一貫性狀態資訊，其中該 〜貫性狀態資訊指示在一個或多個遠端節點上的所要求 的該資料之所有權；以及 孩決足步驟進一步包含下列步騾：查詢歷史資訊及該 貝性狀怨資訊’而決定授予該資料要求中指定的所要 求資料之唯一所有權或非唯一所有權。 如申请專利範圍第1項之方法，其中該決定步驟包含下 列步騾：回應該歷史資訊指示最近將所要求的該資料之 隹—所有權授予該遠端節點，而決定授予唯一所有權。 如申清專利範圍第6項之方法，其中該決定步騾包含下 列步驟·：如果該歷史資訊並未指示最近將所要求的該資 料之唯一所有權授予該遠端節點，則決定授予非唯一所 有權。 .—種用於一多節點電腦系統中之一本地節點之記憶體控 制器，該多節點電腦系統包含由一節點連接裝置耦合之 至V 個遠端節點及一本地節點，其中該本地節點包含 一本地系統記憶體，該記憶體控制器包含： 決定裝置，用以回應自一遠端節點接收到一資料要 长而查。句用來指示該遠端節點中發出的先前資料存取 <歷史資訊，以便決定授予該資料要求中指定的所要求 資料之唯一所有權或非唯一所有權；以及 傳送裝置，用以將所要求的資料及唯一所有權或非唯 一所有權之一指示傳送到該遠端節點。 9.如申請專利範圍第8項之記憶體控制器，其中該傳送裝 ___ -61- Ϊ紙張尺度適财s s家標^規格_ x 297/U 訂 鲁線 1237181

   Α包含在各獨立的傳輸中傳送所要求的該資料及唯一所 有權或非唯一所有權的該指示之裝置。 .如申清專利範圍第8項之記憶體控制器，其中該本地節 點包含一記憶體目錄，該記憶體控制器進一步包含： 在讀記憶體目錄中維護與所要求的諸資料相關聯的歷 史貝訊之裝置，其中該歷史資訊個別地指示每一遠端節 點對所要求的該資料之先前資料要求。 U.如申請專利範圍第8項之記憶體控制器，其中該資料要 求是一讀取要求。 12. 如申請專利範圍第8項之記憶體控制器，該本地節點包 έ 一兒憶體目錄，其中： 孩記憶體控制器進一步包含記錄裝置，用以在該記憶 體目綠中，記錄與所要求的該資料相關聯之一貫性狀態 資訊’其中該一貫性狀態資訊指示在一個或多個遠端節 點上的所要求的該資料之所有權；以及 該決定裝置包含查詢歷史資訊及該一貫性狀態資訊而 決疋授予該資料要求中指定的所要求資料之唯一所有權 或非唯一所有權之裝置。 13. 如申請專利範圍第8項之記憶體控制器，其中該決定裝 置包含回應該歷史資訊指示最近將所要求的該資料之唯 一所有權授予該遠端節點而決定授予唯一所有權之裝 置。 14·如申請專利範圍第i 3項之記憶體控制器，其中該決定 裝置包含如果該歷史資訊並未指示最近將所要求的該資 -62- 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐)

   1237181 未斗乏 其一所有權授予該遠端節點則決定授予非唯一所有 權之裝置。 h 了種用於一多節點電腦系統的一本地節點之記憶體系 、先 j夕即點電腦系統包含由〜節點連接裝置耦合到該 »·、、古之一個或多個遠端卽點，該記憶體系統包含·· 根據申請專利範圍第8項之〜記憶體控制器；以及 耦合到該記憶體控制器之一本地系統記憶體。 16· 一種多節點電腦之節點，該節點包含： 一區域連接裝置； 搞合到該區域連接裝置之一節點控制器；以及 搞合到孩區域連接裝置的申請專利範圍第1 5項之一 記憶體系統。 17. —種電腦系統，包含： 由一節點連接裝置耦合之至少一個遠端節點及一本地 節點其中遠本地郎點包含一本地系統記憶體及一記憶 體控制器，該記憶體控制器包含： 決足裝置，用以回應自一遠端節點接收到一資料要 求，而查詢用來指示該遠端節點中發出的先前資料存取 之歷史資訊，以便決定授予該資料要求中指定的所要求 資料之唯一所有權或非唯一所有權；以及 傳送裝置，用以將所要求的資料及唯一所有權或非唯 一所有權之一指示傳送到該遠端節點。 18. 如申請專利範圍第1 7項之電腦系統，其中該傳送裝置 包含在各獨立的傳輸中傳送所要求的該資料及唯一所有 -63· 本紙張尺度適用中國國家標準(CNS) A4規格(210χ297公釐） !237181

   申請專利範圍 權或非唯一所有權的該指示之裝置。 19·如申請專利範圍第i 7項之電腦系統，其中該本地節點 包含一記憶體目錄，該記憶體控制器進一步包含： 在孩記憶體目錄中維護與所要求的該資料相關聯的歷 史資訊之裝置，其中該歷史資訊個別地指示每一遠端節 點對所要求的該資料之先前資料要求。 -〇·如申請專利範圍第丨7項之電腦系統，其中該資料要求 是一讀取要求。 21.如申請專利範圍第丨7項之電腦系統，其中該本地節點 包含一記憶體目錄，其中： 踢该圮憶體控制器進一步包含記錄裝置，用以在該記憶 把目錄中，記錄與所要求的該資料相關聯之一貫性狀態 貪訊，其中該一貫性狀態資訊指示在一個或多個遠端節 點上的所要求的該資料之所有權；以及 Z決定裝置包含查詢歷史資訊及該一貫性狀態資訊而 決疋抆予泫資料要求中指定的所要求資料之唯一所有權 或非唯一所有權之裝置。 及如申請專利範圍第17項之電腦系統，其中該決定裝置 包含回應該歷史資訊指示最近將所要求的該資料之唯一 所有權授予該遠端節點而決定授予唯一所有權之裝置。 23.如申請專利範圍第22項之電腦系統，其中該決定裝置 包含如果該歷史資訊並未指示最近將所要求的該資料之 唯一所有權授予該遠端節點則決定授予非唯一所 裝置。 張足

   裝 訂 -64-