確保微處理器的快取存儲器層級數據一致性的裝置與方法

2023-05-17 18:57:41

專利名稱：確保微處理器的快取存儲器層級數據一致性的裝置與方法
技術領域：
本發明是有關於 一種微處理器，特別是有關於在快取存儲 器層級中快取線由低階存儲器移至高階存儲器期間內，確保微 處理器的快取存儲器層級的數據一致性。
背景技術：
現有的微處理器具有 一 或多個內部快取存儲器以減少對微 處理器存儲器的平均存取時間。快取存儲器具有多種不同的架 構及尺寸，但是一般都具有一個數據儲存區域和一個地址儲存區域。數據儲存區域一般被規劃作為一些字節的快取線(cache line)。在現有技術中，快取線可為64位元組(bytes)。快取存儲器 一般存儲指令或數據，也可以被規劃作為混合式快取存儲器， 其中，混合式快取存儲器儲存指令及數據。快取存儲器以層級 (hierarchically)的方式配置。在具有層級l ( Level 1 ， Ll )快取 存儲器與層級2 ( Level, L2 )快取存儲器的微處理器中，Ll快 取存儲器的存取最為快速，且當在微處理器的存儲器次系統中 尋找指令或數據時，Ll快取存儲器是被查閱的第一個快取存儲 器。 一般而言，L2快取存儲器的尺寸比L1快取存儲器大，其存 取速度比L1快取存儲器慢。數據由系統存儲器或高階快取存儲器(例如在具有L1快取 存儲器及L2快取存儲器的微處理器中的L2快取存儲器)轉而儲 存在低階快取存儲器(例如L1快取存儲器)的快取線時，通常 是因應於一快取失敗(cache miss )。當讀取(載入)或寫入(儲 存)企圖存取此快取存儲器時，若其正讀取的地址或所寫入的 地址不在此快取存儲器時，則發生快取失敗。對於一載入指令而言，微處理器將通常把來自L2快取存儲器或系統存儲器的數 據(不論此數據是否為最快速可存取格式)載入至L1快取存儲 器中的有效快取線。對於一儲存指令而言，假使存在有效的快 取線時，微處理器通常把數據直接儲存在L1快取存儲器中。假 使L1快取存儲器不存在有效快取線時，根據快取存儲器所使用 的快取線替代策略(cache line replacement policy),樣i處理器可 將數據移至高階快取存儲器L2的快取線。在現有技術中，快取 線替代策略可為最久未使用(least recently memory, LRU)策 略，即是優先清除在快取存儲器中最久未被使用的數據，並釋 放其空間(亦即快取線)。假使快取線替代策略是隨意地選擇快取存儲器中的任何快 取線以指派給主要存儲器中配置的任一存儲區塊，則稱為全相 聯映射(fully associative)。假使在主要存儲器中的每一存儲區塊 只可指派給快取存儲器的固定快取線，則稱為直接映射(direct mapped )。許多微處理器的快取存儲器採取"組相聯映射(set associative mapping)",其融合了直4妄映射與全相聯映射的優 點，並改良其缺點。舉例而言，在兩組相聯快取存儲器(2-way set associative cache memory)中，主要存小者器內的任何特定地 址可被快取(cache)在此快取存儲器中兩條快取線的任 一 者。同 樣的，在四組相聯快取存儲器(4-way set associative cache memory)中，主要存儲器內的任何特定地址可被快取在此快取 存儲器中四條快取線的任一者。微處理器電路自Ll快取存儲器中選擇欲移除(evict)的一快 取線，接著讀取被選擇的快取線，將該快取線寫入至L2快取存 儲器中的有效(available)快取線並無效(invalidate) Ll快取存 儲器的該快取線狀態。快取線狀態協定之一為MESI協定，其是 廣泛使用的快取存儲器與存儲器數據一致性的協定。MESI協定指定四個可能狀態給快取存儲器內的每一快取線已修改 (Modified )狀態、獨佔(Exclusive )狀態、共用(Shared ) 狀態或無效(Invalid)狀態。已{奮改MESI狀態的快取線只出現 在當前快取存儲器，且其已被主要存儲器內的一數值修改。在 允許(不再有效的)主要存儲器狀態的任何其他讀取之前，快 取存儲器被要求在某 一 時間上把數據寫回至主要存儲器。獨佔 MESI狀態的快取線只出現在當前快取存儲器，但它是最新的 (up to date)且匹配(match)主要存儲器。共用MESI狀態的快取線 可與其它快取存儲器共用，其可儲存於多個快取存儲器中。無 效MESI狀態的快取線為不可使用的快取線，其不含有效數據數 值。被移除快取線(於移除之後)具有 一無效MESI狀態。自低階快取存儲器移到高階快取存儲器的快取線通常花費 多個微處理器時脈周期。多個快取存儲器通常被設置在微處理 器中相對遠的位置，且單一移動的數據承載量(data payload)有 時少於一快取線的大小。通常而言，當快取線自快取存儲器移 除時，在此快取線內的完全或部分數據會被儲存或窺察 (snoop )。對於儲存或窺察操作而言，必須得知相關的快取線 的移除處理狀態。假使持續進行儲存或窺察操作而無法得知相 關的快取線移除處理狀態，則可能發生尚未被移除的快取線數 據將通過儲存操作而重複寫入，或者發生快取線為無效狀態。 任 一 者將導致數據錯誤，使得微處理器的快取存儲器層級的數 據無法一致。為了解決上述在快取線移除期間微處理器的快取存儲器層 級的數據一致性(data coherency)的問題，-微處理器通常通過比 較在指令管線中指向快取存儲器的儲存或窺察指令的地址與移 除快取線的地址，來判斷快取線是否處於自低階快取存儲器移 至高階快取存儲器的程序中。移除快取線的地址必須暫時地儲存在微處理器中，直到儲存指令的地址已被比較。 一般而言，可以串行方式(serially)或以並行方式(parallel)來比較地址。以 並行方式來比較多個地址則需要許多比較電路及其他邏輯電 路，以將比較結果由所有的比較電路提供至微處理器。以串行 方式來比較多個地址則需要為多個儲存指令提供足夠時間，降 低了快取線移除操作的速度與快取存儲器效能。因此，微處理 器需要一個方法來快速地確認正處於自低階快取存儲器移至高 階快取存儲器的程序中的快取線，而不需要大量額外硬體電路 來比較上述地址。發明內容基於上述目的，本發明揭露了一種在快取線移除期間確保 微處理器的快取存儲器層級內的數據一致性的裝置，該裝置包 括一移除引擎及一包括多個儲存元件的移除陣列。該移除引擎 用以將一快取線自 一低階存儲器移至一高階存儲器。該包括多 個儲存元件的移除陣列中的每一儲存元件用以儲存在該低階存 儲器的 一對應快取線的 一指示狀態，其中該指示狀態表示該移 除引擎目前是否正將該快取線自該低階存儲器移至該高階存儲 器。本發明更揭露了 一種在快取線移除期間確保微處理器的快 取存儲器層級內的數據一致性的方法，該方法包括下列步驟 將一快取線自 一低階存儲器移至一高階存儲器，其中該移除操 作由一移除引擎所執行。在進行該移除操作前，先將該低階存 儲器中的 一對應快取線的 一指示狀態儲存至 一移除陣列中的多 個儲存元件之一，其中該指示狀態表示該移除引擎目前是否正 將該快取線自該低階存儲器移至該高階存儲器。本發明的優點為相較於傳統微處理器而言需要較少的硬體電路，以判斷一微處理器的快取存儲器層級中的快取線是否正 從該低階存儲器移至該高階存儲器。已知微處理器儲存與比較 該低階快取存儲器的移除快取線的地址與指向該低階快取存儲 器的儲存或窺察操作的地址。上述操作需要多個地址比較器與
控制邏輯電路以及可能的足夠時間(possibly significant time ) 以實現多個所需地址的比較操作。本發明僅需要檢查在 一 移除 陣列中的單一位，以判斷是否正在移除該快取線。由於該移除
陣列判斷哪一條(set/way)的快取線正在移除，故明顯的減少 儲存被移除'決取線的地址的需求。
本發明的另 一優點為減少儲存或窺察地址與自低階快取存 儲器移至高階快取存儲器的快取線的地址的比較操作。快取線 移除的過程中並不需要確認，直到開始執行一儲存或窺察操作。 低階快取存儲器的移除陣列所需的為單 一 查詢操作(single lookup)，且該查詢操作在存取該低階快取存儲器時完成。
本發明的另 一優點為在電路上大大減少了判斷是否正移除 快取線所需的時間。由於儲存操作會重寫(overwrite),可能損 壞正在移除的快取線，故微處理器判斷出儲存操作指向的快取 線正在移除時，需延遲儲存操作。自一移除陣列讀取單一位的 速度相較於比較多個儲存操作的地址的速度以判斷快取線是否 正在移除要快。由於本發明的快取線的移除較已知方法快速， 故微處理器的儲存或窺察操作相對較快。
本發明的另一優點為減少標籤陣列(或包括多個標籤陣列) 的存取，其是因為移除引擎僅存取移除陣列以判斷是否對特定 快取線執行移除操作，因此自低階存儲器至高階存儲器的快取 線完全移除之前，移除引擎不需存取標籤陣列。


圖l是顯示本發明實施例的微處理器的架構示意圖。
圖2是顯示本發明實施例的快取線移除操作的步驟流程圖。
圖3 a是顯示本發明實施例的在快取線移除期間執行微處理 器的儲存操作的步驟流程圖。
圖3 b是顯示本發明實施例的在快取線移除期間執行微處理 器的載入操作的步驟流程圖。
圖4是顯示本發明實施例的在快取線移除期間執行微處理 器的窺察操作的步驟流程圖。
圖5是顯示本發明另 一 實施例的在快取線移除期間執行微 處理器的窺察操作的步驟流程圖。
圖6是顯示本發明實施例的移除陣列、標籤陣列與數據陣列 的架構示意圖。
附圖中符號的筒單說明如下
102:儲存指令
104:載入/儲存/窺察單元
106:載入指令
108:移除陣列
112:更新標籤
114:窺察指令
116:更新移除位線
118:移除位
122:移除引擎
124:L1快取數據陣列與標籤陣列
126:L2快取數據陣列與標籤陣列
128、132:快取線
134:移除完成線136.更新線
138讀取線
152重試線
602標籤陣列
604數據陣列
606載入/儲存/窺察地址索引。
具體實施例方式
為了讓本發明的目的、特徵及優點能更明顯易懂，下文特
舉較佳實施例，並配合所附圖式圖l至圖6，做詳細的說明。本 發明說明書提供不同的實施例來說明本發明不同實施方式的技 術特徵。其中，實施例中的各元件的配置是為說明之用，並非 用以限制本發明。且實施例中圖式標號的部分重複，是為了簡 化說明，並非意指不同實施例之間的關聯性。
本發明實施例揭露了 一種在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置與方法。
圖l是顯示本發明實施例的微處理器的架構示意圖。 微處理器100包括一移除引擎(Eviction Engine) 122,其 用以將微處理器100中的快取存儲器層級中的一快取線自低階 快取存儲器移至高階快取存儲器。該高階快取存儲器與該低階 快取存儲器為專用(exclusive)存儲器。也就是每一高階快取與 低階快取包括不同的快取線，而該高階快取存儲器與該低階快 取存儲器的快取線間沒有重疊。在一實施例中，低階快取存儲 器為L1快取數據陣列與標籤(tag)陣列124 ，而高階快取存儲器 為L2快取數據陣列與標'籤陣列126。簡言之，Ll快取數據陣列 與標籤陣列124標示為L1快取存儲器124，而L2快取數據陣列與 標籤陣列126標示為L2快取存儲器126。微處理器100亦包括一移除陣列108,其中移除引擎122更新 移除陣列108以表示一快取線是否正自Ll快取存儲器124移至 L2快取存儲器126。移除陣列108具有與被移除的快取線的低階 快取存儲器相同的架構，如圖1所示的L1快取存儲器124。移除 陣列108與L1快取存儲器124的數據陣列與標籤陣列間的架構 描述於圖6中。
如圖6所示，其是顯示本發明實施例的圖l的移除陣列108、 Ll快取存儲器124的標籤陣列602與數據陣列604的架構示意 圖。移除陣列108包括多個儲存元件，每一儲存元件包括一移除 位，用以儲存在L1快取存儲器124中一對應快取線的一指示狀 態(Indication),其中該指示狀態表示該移除引擎目前是否正 將該快取線自該低階存儲器移至該高階存儲器。移除引擎122 在自L1快取存儲器124移除一快取線至L2快取存儲器126之前， 通過圖1所示的更新移除位線116更新對應該快取線的該移除位 為一真值(true value),以及在移除引擎122完成該移除程序後 更新該移除位為 一假值(false value ),即此時L2快取存儲器126 已取得該快取線的所有權。上述真值為邏輯值為真的位值，上 述假值為一邏輯值為假的位值。舉例來說，真值為l，假值為0。 在圖6中，每一標籤陣列602、數據陣列604與移除陣列108分別 為多個對應陣列組。每一標籤陣列602、數據陣列604或移除陣 列108由 一載入/儲存/窺察地址606的索引(index)存取，用以選 擇每 一 標籤陣列602 、數據陣列604或移除陣列108的其中 一 陣列 組。在一實施例中，數據陣列604、標籤陣列602與移除陣列108 各自的多個對應陣列組皆包括四組(way)的儲存元件，其中數據 陣列604用以儲存快取線，標籤陣列602用以儲存地址標籤與 MESI狀態，移除陣列108用以儲存移除位。因此，在每一次存 取中，數據陣列604輸出四條快取線，標籤陣列602輸出四個標籤，以及移除陣列108輸出四個移除位。在每一標籤陣列602、 數據陣列604或移除陣列108的輸出的對應多工器(未顯示)根 據一選擇信號選擇四個輸出的其中 一個輸出以表示其具有匹配 該載入/儲存/窺察地址60 6的索引選擇的 一 標籤陣列組的 一 標 籤(若有的話)。在一實施例中，移除陣列108為一直接寫通過 (write-through)陣列，也就是把數據同時寫入移除陣列108的 一位置與主要存儲器兩者。在另一實施例中，移除陣列108偵測 讀取與寫入移除陣列108中相同位置的沖突，當發生上述衝突 時，移除陣列108令該讀取j喿作重新扭j亍(replay)。
參考圖1，移除引擎122包括一或多個緩衝器以提供暫存數 據。所述緩衝器儲存可快取的數據以及有關該數據的位置與狀 態信息。除了暫存數據外，移除引擎122亦包括狀態機(state machines),其用以管理自Ll快取存儲器124至L2快取存儲器126 的快取線的移除才乘作。；微處理器100亦包括一配置(allocation) 引擎(未顯示)，其用以配置自L2快取存儲器126至L1快取存儲 器124的快取線。移除引擎122耦接L1快取存儲器124、 L2快取 存儲器126、載入/儲存/窺察單元104以及移除陣列108。 Ll快取 存儲器124與L2快取存儲器126包括快取線的儲存空間以及每狀態。
雖然圖l的快取存儲器層級顯示了 二個快取存儲器，其中以 一移除陣列108表示自L1快取存儲器124至L2快取存儲器126的 快取線移除操作是否正在執行，但並不限於此，例如包括二個 以上的快取存儲器的其它實施例，可利用多個移除陣列來表示 該快取存儲器層級中的每一低階快取存儲器至其各自對應的高 階快取存儲器的移除操作。在上述實施例中，每一移除陣列的 架構與每一對應的低階快取存儲器相同。因此，在一實施例中，微處理器100亦包括一層級3(Level， L3)快取存儲器，其是位於 L2快取存儲器126之上。在此實施例中，微處理器100包括一第 二移除陣列，其具有與L2快取存儲器126相同的架構，且表示 自L 2快取存儲器12 6移至L 3快取存儲器的快取線移除操作是否 正在執行。
微處理器100包括載入/儲存/窺察單元104。載入/儲存/窺察 單元104中的載入單元將主要存儲器或快取存儲器的數據載入 微處理器100的暫存器。載入/儲存/窺察單元104中的儲存單元 將微處理器100的暫存器的數據儲存至主要存儲器或快取存儲 器。載入/儲存/窺察單元104中的窺察單元用以窺察微處理器總 線偵測到之上的數據傳輸(transactions)，以維護系統中不同快 取存儲器的快取一 致性(cache coherency)。載入/儲存/窺察單元 104通過讀取線138讀取L1快取存儲器124的快取線與標籤，並 且通過更新線136更新L1快取存儲器124的快取線與標籤。此 外，載入/儲存/窺察單元104讀耳又移除陣列108的移除位118。此 外，載入/儲存/窺察單元104中的窺察單元產生一真值於重試線 152上以令微處理器100的總線接口單元(未顯示)重試微處理 器100的總線的窺察操作，其詳述於下文。在一實施例中，載入 /儲存/窺察單元104可以是一單一整合電路(single monolithic group of circuits ),其管理所有微處理器100的載入指令106、儲 存指令102與窺察指令114，而在其它實施例中，載入/儲存/窺 察單元104表示為三個單元。
微處理器100中的替代策略演算法(Replacement policy algorithms )為偵測到另 一 快取線比當前的快取線更可能被微處 理器100引用時，移除引擎122將當前快取線自Ll快取存儲器 124移至L2快取存儲器126。載入/儲存/窺察單元104自移除陣列 108讀取移除位118,以判斷移除引擎122目前是否正移除包括有儲存指令102或窺察指令114指定的數據的快取線。
在開始將一快取線自L1快取存儲器124移至L2快取存儲器 126之前，移除引擎122通過更新移除位線116設定對應於正在被 移除的快取線的移除陣列108中的移除位的指示狀態以表示目 前正將該快取線自該低階存儲器移至該高階存儲器。在移除引
位後，移除引擎122讀取L1快取存儲器124的快取線128。在讀 取L1快取存儲器124的快取線128後，移除引擎122對L2快取存 儲器126的快取線132進行寫入。當完成L2快取存儲器126快取 線132的寫入時，L2快取存儲器126產生一真值通過移除完成線 134給移除引擎122。移除引擎122通過更新移除位線116來清除 移除陣列108的對應移除位，以指示完成快取線移除的操作。此 外，移除引擎122通過更新標籤線112更新L1快取存儲器124內 的標籤。舉例來說，在一實施例中，移除引擎122在將快取線由 L1快取存儲器124移至L2快取存儲器126後，將快取線的標籤更 新為無效MESI狀態。
在一實施例中，載入/儲存/蔬察單元104包括載入管線與儲 存管線。在此實施例中，執行圖1與下文流程圖所示的不同操作， 移除引擎122仲裁上述二種管線的存取操作。載入管線接收載入 指令106,並相應地讀取L1快取存儲器124的指定數據。儲存管 線接收儲存指令102與窺察指令114，並相應地讀取L1快取存儲 器124的標籤，以及在需要時更新L1快取存儲器124的標籤與快 取線。移除陣列108具有一讀耳又埠與一寫入埠 。在一實施例 中，移除陣列108的讀取埠耦接於儲存管線，而移除陣列108 的寫入埠耦接於載入管線。儲存搡作與窺察操作讀取移除陣 列10 8以判斷當前儲存與窺察的快取線是否正從L1快取存儲器 124移除。由於移除陣列108的寫入埠耦接於載入管線，移除引擎122產生一移除陣列108更新至該載入管線，其仲裁載入管 線與載入指令106的存取。載入管線相應的設定或清除由L1快 取存儲器12 4移至L 2快取存儲器12 6的快取線對應的移除位。
當處理載入指令106時，微處理器100不需存取移除陣列 108。相對的，微處理器100讀取L1快取存儲器124的標籤陣列 602以判斷L1快取存儲器124是否取得包括載入指令106指定的 數據的快取線的所有權，其將說明於圖3b中。
圖2是顯示本發明實施例的快取線移除操作的步驟流程圖。 本流程起始於步驟202。
在步驟S202中，移除引擎122判斷L1快取存儲器124的一快 取線需要移除。舉例來說，當載入/儲存/窺察單元104具有比目 前快取線會更常被存取的儲存數據，微處理器100可選擇一快取 線以進行移除。接著執行步驟S204。
在步驟S204中，移除引擎122通過更新移除位線116來設定 移除陣列108中與上述移除快取線相關的移除位。移除陣列108 具有與L1快取存儲器124相同的架構，包括與L1快取存儲器124 的每 一 快取線相關的移除位。接著執行步驟S 2 06 。
在步驟S206中，移除引擎122讀取L1快取存儲器124的移除 快取線128。接著執行步驟S208。
在步驟S208中，移除引擎122將L1快取存儲器124的移除快 取線128寫入L2快取存儲器126的一快取線132。在一實施例中， 快取線的大小大於移除引擎122與L1快取存儲器124與/或L2快 取存儲器126之間的總線大小，因此，在步驟206中，移除引擎 122通過多工讀取操作讀取L1快取存儲器124的快取線128，以 及在步驟208中，移除引擎122通過多工寫入操作寫入L2快取存 儲器126的快取線132。在一實施例中，移除引擎122串行地 (serially)4丸行多工4乘作(multiple operations )。在另 一實施例中，移除引擎122以一管線方法(pipelined manner )執行多工操作。 接著執行步驟S212。
在步驟S212中，當完成L2快取存儲器126快取線132的寫入 時，L2快取存儲器126通知移除引擎122已準備好通過產生移除 完成線(eviction completed line ) 134的真值來取得完成寫入的 快取線的所有權。當在步驟208完成寫入操作後，L2快取存儲 器126產生一真值於移除完成線134給移除引擎122。接著執行步 驟S214。
在步驟S214中，移除引擎122使L1快取存儲器124的移除快 取線無效並且清除移除陣列108中與移除快取線相關的移除位。 移除引擎122通過更新標籤線112更新L1快取存儲器124內的標 籤，並且通過更新移除位線116來清除移除陣列108中與移除快 取線相關的移除位。移除引擎122寫入對應L1快取存儲器124的 移除快取線的標籤至一無效MESI狀態，使L1快取存儲器124的 移除快取線無效。接著結束本流程。
圖3a是顯示本發明實施例的在快取線移除期間執行微處理 器100的儲存操作的步驟流程圖。本流程起始於步驟302。
在步驟S302中，載入/儲存/窺察單元104中的儲存單元接收 儲存指令102並且相應的產生一儲存操作。儲存指令102指定一 存儲器的儲存地址，其中微處理器100將微處理器100的暫存器 中的儲存數據寫入該存儲器的儲存地址。該儲存地址可能存在 於L1快取存儲器124的快取線。接著執行步驟S304。
在步驟S304中，儲存單元用儲存指令102指定的儲存地址 來存取L1快取存儲器124。若該儲存地址的標籤與通過該儲存 地址的索引選擇的標籤陣列中其中一標籤陣列組相匹配，且該 標籤的MESI狀態不是無效狀態下時，Ll快取存儲器124表示命 中(hit),其表示儲存指令102指向存在於L1快取存儲器124數據陣列中的快取線。該儲存單元亦通過儲存指令102的儲存地址 存取移除陣列10 8 ，以讀取對應儲存指令10 2的快取線的移除位 118。接著執行步驟S306。
在步驟S306中，該儲存單元評估移除位118是否設定。若 移除位118已被設定，則表示移除引擎122目前正移除該對應的 快取線，接著執行步驟S312。若移除位118未被設定，則表示 移除引擎122沒有正在執行該對應的快取線的移除操作。接著執 行步驟S308。
在步驟S308中，由於沒有對應快取線移除操作在執行，儲 存單元執行儲存指令102。特別的是，若儲存指令102指向L1快 取存儲器124中的快取線，該儲存單元將儲存數據寫入至L1快 取存儲器12 4數據陣列中的快取線，將儲存地址的標籤寫入至標 籤陣列，並且適當更新標籤陣列中的MESI狀態。然而，若儲存 指令102指向未存在L1快取存儲器124中的快取線，配置引擎 (未顯示)配置一快取線128於L1快取存儲器124中，自L2快取 存儲器126 (或系統存儲器)讀取一快取線132後，再寫入L1快 取存儲器124的快取線128。亦即，配置引擎在該儲存操作執行 之前將一快取線自該高階存儲器移至該低階存儲器以更新該快 取線。此外，若儲存指令102指向具有共用MESI狀態的快取線， 該配置引擎將該快取線更新至已修改MESI狀態。接著結束本流 程。
在步驟S312中，儲存單元重新執行該儲存操作，直到移除 位118被清除。該儲存操作通過使該儲存指令被重新執行以存取 儲存單元管線，其可有效的執行步驟3 04與3 0 6中的相同操作， 直到移除位118被清除。接著執行步驟S314。
在步驟S314中，載入/儲存/窺察單元104中的儲存單元要求 重新配置L2快取存儲器126中的快取線至L1快取存儲器124。配置引擎在儲存單元提出要求時執行重新配置操作。由於在允許
儲存該快取線前，Ll快取存儲器124必須取得該快取線的所有 權，故L2快取存儲器126至L1快取存儲器124的快取線的重新載 入操作是必要的。此外，儲存操作所需的存儲器大小比整個快 取線要小，且不是儲存操作的 一部分的快取線數據必須是在已 知的狀態。接著執行步驟S316。
在步驟S316中，在快取線重新配置至L1快取存儲器124後， 載入/儲存/窺察單元104中的儲存單元執行儲存指令102,接著 結束本流程。
在上述流程中說明了 ，該移除引擎122禁止儲存單元進行一 儲存操作以更新 一 快取線，直到該移除位118的指示狀態表示該 移除引擎122已完成將該快取線自 一低階存儲器移至一高階存 儲器。
器的載入操作的步驟流程圖。本流程起始於步驟322。
在步驟S322中，載入/儲存/窺察單元104中的栽入單元接收 一載入指令106。接著執行步驟S324。
在步驟S324中，該載入單元在載入指令106指定的地址讀 取L1快取存儲器12 4的標籤陣列與數據陣列。載入指令10 6指定 微處理器100會讀取載入數據的一存儲器位置的地址給微處理 器100的暫存器。該載入地址可能存在於L1快取存儲器124的快 取線。接著執行步驟S326。
在步驟S326中，該載入單元完成衝丸^亍載入指令106。由於 該載入單元正由L1快取存儲器124讀取快取線，故不需理會載 入指令106定址的快取線的移除位值。只要該快取線存在於L1 快取存儲器12 4中且該快取線的M E SI值為有效，則載入指令將 完成執行，4妻著結束本流程。在上述流程中說明了 ，當該移除陣列108的移除位118的指 示狀態表示該移除引擎122目前正將一快取線自 一低階存儲器 移至 一 高階存儲器時，該移除引擎12 2允許 一 載入操作以讀取該 快取線。
圖4是顯示本發明實施例的在快取線移除期間執行微處理 器10 0的窺察操作的步驟流程圖。若快取存儲器中具有窺察指令 114指定的地址，則窺察指令114令該快取存儲器使得由窺察指 令114指定的地址的快取線無效。本流程起始於步驟402。
在步驟S402中，載入/儲存/窺察單元104中的窺察單元接收 窺察指令114 , 並且相應的產生 一 窺察才喿作(snoop query operation)。當微處理器IOO的總線接口單元(未顯示)接收微 處理器1 OO的總線的窺察指令114時，該窺察單元從微處理器100 的總線接口單元接收窺察指令114。窺察指令114指定可能出現 在L1快取存儲器124中的快取線的地址為無效。接著執行步驟 S據。
在步驟S404中，該窺察單元讀取L1快取存儲器124標籤陣 列，以判斷窺察指令114是否指向L1快取存儲器124中的有效快 取線。該窺察單元亦通過窺察指令114的窺察地址存取移除陣列 108以讀取對應窺察指令114的快取線的移除位118。接著執行步 驟S楊。
在步驟S406中，該窺察單元評估在步驟404讀取的移除位 118是否設定。若移除位118已被設定，則表示移除引擎122目前 正移除對應移除位118的快取線，接著執行步驟S412。若移除 位118未被設定，則表示移除引擎122沒有正在執行對應該移除 位118的快取線的移除操作。接著執行步驟S408。
在步驟S408中，由於該窺察地址指定的快取線未正^^皮移 除，故該窺察單元正常回應該窺察指令114。特別的是，該窺察單元通過更新線136將窺察指令114定址的L1快取存儲器124的 快取線的MESI狀態更新為無效。此外，若該快取線為已修改的 MESI狀態，則該窺察單元在使該快取線無效前將該快取線寫回 存儲器總線上的主要存儲器，然後結束本流程。
在步驟S412中，該窺察單元產生重試(Retry) 152給微處 理器100的總線接口單元，使得該總線接口單元在微處理器100 的總線上重新執行窺察指令114 。該總線接口單元相應的在微處 理器100的總線上轉送窺察指令114的重試。接著執行步驟 S414。
在步驟S414中，當在步驟412中該總線4妄口單元產生該重 試後，原先產生窺察指令114的微處理器100的總線上的代理裝 置(agent)重新發送窺察指令114給系統中的所有快取存儲器。接 著回到步驟402以執行重試的窺察指令114,直到移除陣列108 表示移除操作已完成。
在上述流程中說明了 ，該移除引擎122阻止該微處理器回應 一快取線的 一窺察操作，直到對應該快取線的移除位118的指示 狀態表示該移除引擎122已完成將該快取線自該低階存儲器移 至該高階存儲器。
圖5是顯示本發明另 一實施例的在快取線移除期間執行微 處理器100的窺察操作的步驟流程圖。本流程起始於步驟502。
在步驟S502中，載入/儲存/窺察單元104中的窺察單元接收 窺察指令114，並且相應的產生窺察操作，其與圖4的步驟402 相同。接著執行步驟S504。
在步驟S504中，該窺察單元讀取L1快取存儲器124標籤陣 列，以判斷窺察指令114是否指向L1快取存儲器124中的有效快 取線。該窺察單元亦通過窺察指令114的窺察地址存取移除陣列 108以讀取對應窺察指令114的快取線的移除位118。其與圖4的步驟404相同。接著執行步驟S506。
在步驟S506中，該窺察單元評估在步驟504讀取的移除位 118是否設定，其與圖4的步驟406相同。若移除位118已被設定， 則表示移除引擎122目前正移除對應移除位118的快耳又線，接著 執行步驟S512。若移除位118未被設定，則表示移除引擎122沒 有正在執行對應該移除位118的快取線的移除操作，接著執行步 驟S508。
在步驟S508中，由於該窺察地址指定的快取線未正被移 除，故該窺察單元正常回應該窺察指令114,其與圖4的步驟408 相同，接著結束本流程。
在步驟S512中，窺察單元回應HIT信號或HITM信號給總線 接口單元，且該總線^接口單元轉送HIT信號或HITM信號給農吏處 理器10 0的總線。若快取線的M E SI狀態為獨佔狀態或共用狀態， 則窺察單元產生HIT信號。若快取線的MESI狀態為已修改狀態， 則窺察單元產生HITM信號。若窺察單元產生HITM信號，微處 理器100需要將L1快取存儲器124的已修改狀態的快取線寫回 至主要存儲器。接著執行步驟S514。
在步驟S514中，微處理器100的窺察單元輪詢(poll)移除陣 列108,直到移除位被清除。當快取線移除完成時，移除引擎122 清除移除陣列108中的移除位118,如圖2所示。由於移除操作已 經完成，通常是在下次重試窺察指令114時來清除移除位118。 然而，若未清除，則再次執行重試窺察指令114。接著執行步驟 S516。
在步驟S516中，若快取線的MESI狀態為已修改狀態，則窺 察單元指示移至L2快取存儲器126的快取線寫回至主要存儲 器，以及使L2快取存儲器126的快取線無效。本實施例中的L2 快取存儲器12 6負責使快取線無效，並且將已修改狀態的快取線寫回至主要存儲器，接著結束本流程。本發明是實作於一微處 理器裝置內，其可使用於一般用途的計算機。
本發明的方法，或特定型態或其部分，可以以程序碼(如
C、 C++、石更件描述語言(Hardware Description Languages, HDL ) (包括Verilog HDL、 VHDL…等等)或任何其它程序)的型態 存在。程序碼可以包括於實體介質，如軟盤、光碟片、硬碟、 或是任何其他機器可讀取(如計算機可讀取)儲存介質，其中， 當程序碼被機器，如計算機載入且執行時，此機器變成用以參 與本發明的裝置。程序碼也可以通過一些傳送介質，如電線或 電纜、光纖、或是任何傳輸型態進行傳送，其中，當程序碼被 機器，如計算機接收、載入且執行時，此機器變成用以參與本 發明的裝置，如中央處理器(CPU)、微處理器、微控制器、數 字信號處理器、處理器核心、系統單晶片(SOC)或任何其它 裝置。當在一般用途處理單元操作時，程序碼結合處理單元提 供一操作類似於應用特定邏輯電路的獨特裝置。
以上所述僅為本發明較佳實施例，然其並非用以限定本發 明的範圍，任何熟悉本項技術的人員，在不脫離本發明的精神 和範圍內，可在此基礎上做進一步的改進和變化，因此本發明 的保護範圍當以本申請的權利要求書所界定的範圍為準。
權利要求
1.一種在快取線移除期間確保微處理器的快取存儲器層級內的數據一致性的裝置，其特徵在於，該裝置包括一移除引擎，用以將一快取線自一低階存儲器移至一高階存儲器；以及一移除陣列，耦接於該移除引擎，該移除陣列包括多個儲存元件，每一儲存元件用以儲存在該低階存儲器中一對應快取線的一指示狀態，其中該指示狀態表示該移除引擎目前是否正將該快取線自該低階存儲器移至該高階存儲器。
2. 根據權利要求1所述的在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置，其特徵在於，該移 除引擎禁止一儲存操作更新該快取線，直到該指示狀態表示該 移除引擎已完成將該快取線自該低階存儲器移至該高階存儲 器。
3. 根據權利要求2所述的在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置，其特徵在於，更包 括一配置引擎用以在該儲存操作執行之前將該快取線自該高階 存儲器移至該低階存儲器以更新該快取線。
4.的快取存儲器層級內的數據一致性的裝置，其特徵在於，當該 指示狀態表示該移除引擎目前正將該快取線自該低階存儲器移 至該高階存儲器時，該移除引擎允許一載入操作以讀取該快取 線。
5.根據權利要求1所述的在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置，其特徵在於，該移 除引擎阻止該微處理器回應該快取線的一窺察操作，直到該指 示狀態表示該移除引擎已完成將該快取線自該低階存儲器移至 該高階存儲器。
6. 根據權利要求1所述的在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置，其特徵在於，若該 指示狀態表示該移除引擎已將該快取線自該低階存儲器移至該 高階存儲器，且該快取線的狀態為一已修改狀態，則該高階存 儲器使該'決取線無效以及將已修改狀態的該快取線寫回至 一 主 要存儲器來回應該快取線的一窺察操作。
7. 根據權利要求1所述的在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置，其特徵在於，在開 始將該快取線自該低階存儲器移至該高階存儲器之前，該移除 引擎設定該指示狀態以表示目前正將該快取線自該低階存儲器 移至該高階存儲器。
8. 根據權利要求1所述的在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置，其特徵在於，當完 成將該快取線自該低階存儲器移至該高階存儲器時，該移除引 擎清除該指示狀態以表示目前已將該快取線自該低階存儲器移 至該高階存儲器。
9. 根據權利要求8所述的在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置，其特徵在於，在該 移除引擎清除該指示狀態之前，該高階存儲器通知該移除引擎 已準備好取得該快取線的所有權。
10. 根據權利要求8所述的在快取線移除期間確保微處理器 的快取存儲器層級內的數據一致性的裝置，其特徵在於，該移 除引擎在清除該指示狀態之前，使在該低階存儲器中的該快取 線無效。
11. 一種在快取線移除期間確保微處理器的快取存儲器層 級內的數據一致性的方法，其特徵在於，該方法包括下列步驟將一快取線自 一低階存儲器移至一高階存儲器，其中該移除操作由一移除引擎所執行；以及在進行該移除操作前，先將該低階存儲器中 一 對應快取線 的一指示狀態儲存至一移除陣列中的多個儲存元件之一，其中 該指示狀態表示該移除引擎目前是否正將該快取線自該低階存 儲器移至該高階存儲器。
12. 根據權利要求11所述的在快取線移除期間確保微處理 器的快取存儲器層級內的數據一致性的方法，其特徵在於，更 包括禁止 一儲存操作更新該快取線，直到該指示狀態表示該移 除引擎已完成將該快取線自該低階存儲器移至該高階存儲器。
13. 根據權利要求12所述的在快取線移除期間確保微處理 器的快取存儲器層級內的數據一致性的方法，其特徵在於，更 包括在該儲存操作執行之前將該快取線自該高階存儲器移至該 低階存儲器以更新該快取線。
14. 根據權利要求11所述的在快取線移除期間確保微處理 器的快取存儲器層級內的數據一致性的方法，其特徵在於，更 包括當該指示狀態表示該移除引擎目前正將該快取線自該低階 存儲器移至該高階存儲器時，該移除引擎允許一載入操作以讀 耳又該快耳又線。
15 器的快取存儲器層級內的數據一致性的方法，其特徵在於，更 包括阻止該微處理器回應該快取線的 一 窺察操作，直到該指示 狀態表示該移除引擎已完成將該快取線自該低階存儲器移至該 高階存儲器。
16.根據權利要求11所述的在快取線移除期間確保微處理 器的快取存儲器層級內的數據一致性的方法，其特徵在於，若 該指示狀態表示該移除引擎已將該快取線自該低階存儲器移至 該高階存儲器，且該快取線的狀態為一已修改狀態，則使該快取線無效以及將已修改狀態的該快取線寫回至 一 主要存儲器來回應該快取線的 一 窺察操作。
17. 根據權利要求11所述的在快取線移除期間確保微處理器的快取存儲器層級內的數據一致性的方法，其特徵在於，更包括在該移除引擎開始將該快取線自該低階存儲器移至該高階存儲器之前，設定該指示狀態以表示目前正將該快取線自該低階存儲器移至該高階存儲器。
18. 根據權利要求11所述的在快取線移除期間確保微處理器的快取存儲器層級內的數據一致性的方法，其特徵在於，更包括當該移除引擎完成將該快取線自該低階存儲器移至該高階存儲器時，清除該指示狀態以表示目前未將該快取線自該低階存儲器移至該高階存儲器。
19. 根據權利要求18所述的在快取線移除期間確保微處理器的快取存儲器層級內的數據一致性的方法，其特徵在於，在清除該指示狀態之前，該高階存儲器通知該移除引擎已準備好取得該快取線的所有權。
20. 根據權利要求18所述的在快取線移除期間確保微處理器的快取存儲器層級內的數據一致性的方法，其特徵在於，更包括在清除該指示狀態前，使在該低階存儲器中的該快取線無效。
全文摘要
一種確保微處理器的快取存儲器層級數據一致性的裝置與方法，該裝置包括一移除引擎及一包括多個儲存元件的移除陣列。該移除引擎用以將一快取線自一低階存儲器移至一高階存儲器。該包括多個儲存元件的移除陣列中的每一儲存元件用以儲存在該低階存儲器的一對應快取線的一指示狀態，其中該指示狀態表示該移除引擎目前是否正將該快取線自該低階存儲器移至該高階存儲器。本發明可明顯減少儲存被移除快取線的地址的需求，且可減少自低階快取存儲器移至高階快取存儲器的快取線的地址的比較操作。
文檔編號G06F12/08GK101593161SQ200910147348
公開日2009年12月2日 申請日期2009年6月15日 優先權日2008年9月9日
發明者艾迪 柯林, E.虎克 羅德尼 申請人:威盛電子股份有限公司