逐出高速緩存的行的電路布置、數據處理系統和方法
2023-11-05 02:22:42 2
專利名稱：逐出高速緩存的行的電路布置、數據處理系統和方法
技術領域：
本發明涉及計算機和數據處理系統，具體地涉及用於在這種計算機和數據處理系統的高速緩存的逐出(eviction)算法。
背景技術：
隨著對處理器(計算機的「大腦」)和存儲由計算機所處理的信息的存儲器兩者在性能上的大量改進，計算機技術正以極快的步伐繼續發展。
通常，處理器通過執行形成電腦程式的指令序列來操作。指令典型地存儲在具有多個由唯一存儲器地址標識的存儲位置的存儲系統中。存儲器地址共同地定義了「存儲器地址空間」，其表示可由處理器訪問的存儲器地址的可尋址範圍。
形成電腦程式的指令和這些指令所操作的數據兩者常常存儲在存儲系統中，並且當執行該電腦程式時根據需要由處理器取回。但是，處理器的速度相對於存儲設備的速度已經增加的程度，使得從存儲器中取回指令和數據常常會成為性能上的嚴重瓶頸。為了減少該瓶頸，期望儘可能使用最快可利用的存儲設備，例如，靜態隨機訪問存儲器(SRAM)設備等等。但是，存儲器速度和存儲器容量通常與成本直接相關，因此，許多計算機設計必須在存儲器速度和容量與成本之間做出平衡。
獲得這種平衡的重要方式是在存儲系統中使用多「級」存儲器，從而試圖以對系統性能產生最小影響來減少成本。通常，計算機依靠相對大的、慢的以及便宜的大容量存儲系統(例如硬碟驅動器或者其它外部存儲設備)、使用動態隨機訪問存儲設備(DRAM)或者其它易失存儲器存儲設備的中間主存儲器、以及一個或者多個利用SRAM等等實現的高速但容量有限的高速緩衝存儲器(cache memories)或者高速緩存。然後，一個或者多個存儲控制器被用來在各種存儲器級之間交換來自通常被稱為「高速緩存行」的存儲器地址的分段的信息，以試圖令所請求的存儲器地址被存儲在可由處理器訪問的最快的高速緩衝存儲器中的頻率最大化。只要存儲器訪問請求試圖訪問沒有高速緩存在高速緩衝存儲器中的存儲器地址，就會發生「高速緩存未命中」。作為高速緩存未命中的結果，典型地，通常必須從相對慢的、較低的存儲器級中取回對於存儲器地址的高速緩存行，而這通常會對性能造成極大的影響。
已經開發的一種多級存儲器體系結構被稱為「非統一存儲器訪問(NUMA)體系結構」，其中多個主存儲器基本上分布在計算機上，並且按照處理器和高速緩存的組，被物理上分成多個物理子系統或者模塊，在此也被稱為「節點」。在NUMA計算機的每個節點中的處理器、高速緩存和存儲器通常設置在同一電路板或者卡上，以提供對於節點而言為「本地」的所有部件之間的高速交互。通常，包括一個或者多個集成電路晶片的「晶片組」被用來管理處理器和存儲器體系結構中的各個部件之間的數據通信。節點也通過例如系統總線或者點到點互聯的集合的網絡相互耦合，由此允許一個節點處的處理器訪問存儲在另一個節點處的數據，這樣有效地擴展了計算機的整體容量。此外，在處理器中以及每個晶片組中利用一個或者多個高速緩存級。當對存儲在本地存儲器(即駐留在與處理器相同節點處的存儲器)中數據的訪問時間與對遠程存儲器中存儲(即駐留在另一個節點處的存儲器)的數據的訪問時間相比非常短時，存儲器訪問被稱為「非統一的」。
典型的高速緩存利用將高速緩存行映射到多個組之一的高速緩存目錄，其中，每組包括高速緩存目錄條目及其所參考的高速緩存行。此外，存儲在高速緩存目錄條目中的對於一組的標籤被用來確定是否存在對於那組的高速緩存命中或者未命中，即驗證特定存儲器地址所映射到的組中的高速緩存行是否包含對應於該存儲器地址的信息。
常常，高速緩存中的每個目錄條目還包括狀態信息，其中狀態信息表示該條目所參考的高速緩存行的狀態，並且使用該狀態信息，以在存儲器體系結構中的不同存儲器之間保持一致性。一個通用的一致性協議被稱為MESI一致性協議，它按照以下四個狀態之一對高速緩存中的每個條目進行標記修改的、排他的、共享的或者無效的。「修改的」狀態表示條目包含有效的高速緩存行，並且該條目具有其最接近的副本，即，如果有其他副本的話，所有其它副本不再有效。「排他的」狀態類似於「修改的」狀態，但是表示條目中的高速緩存行仍然沒有被修改。「共享的」狀態表示高速緩存行的有效副本存儲在條目中，但是高速緩存行的其它有效副本也可以在其它設備中。「無效的」狀態表示沒有有效的高速緩存行存儲在條目中。
高速緩存也可以具有不同的關聯度，並且通常被稱為N路組關聯。每「路」或者類代表在高速緩存目錄中對於給定組的單獨目錄條目和高速緩存行。因此，在單路組關聯的高速緩存中，每個存儲器地址被映射到高速緩存中的一個目錄條目以及一個高速緩存行。多路組關聯的高速緩存，例如四路組關聯的高速緩存，提供特定存儲器地址可以被映射到多個目錄條目以及高速緩存行，由此降低了在單路組關聯的高速緩存中比較常見的性能限制熱點的可能性。
另外，一些高速緩存在性質上可以是「包含式」的，因為這些高速緩存維護著由與這些高速緩存相耦合的較高級高速緩存所高速緩存的高速緩存行的冗餘副本。雖然由於在較高級高速緩存中高速緩存的高速緩存行的冗餘副本的存儲使得包含式高速緩存的有效容量比「排他式」高速緩存的低，但是包含式高速緩存提供了以下性能好處，即通過檢查包含式高速緩存中的高速緩存行的狀況，可以簡單地確定由與包含式高速緩存相耦合的較高級高速緩存所高速緩存的高速緩存行的狀況。
可能影響系統性能的高速緩存的一個可能操作是高速緩存行的逐出操作。只要需要對於新的高速緩存行的空間，就會頻繁地要求任何尺寸受限的高速緩存從高速緩存中放棄或者逐出高速緩存行。在單路組關聯的高速緩存情況下，高速緩存行的逐出很平常，因為每個高速緩存行是被映射到高速緩存中的單個條目，這樣輸入的高速緩存行必然代替存儲在輸入的高速緩存行所映射到的單個條目中的現有的高速緩存行。
另一方面，在多路組關聯高速緩存中，輸入的高速緩存行可能潛在地存儲在映射到同一組的多個條目之一中。已經發現選擇哪個條目存儲輸入的高速緩存行(這通常必須逐出先前存儲在所選擇的條目中的高速緩存行)可能會對系統性能產生極大影響。因此，已經開發了各種選擇算法(通常被稱為逐出算法)，以試圖最小化高速緩存行逐出對系統性能的影響。
許多傳統的逐出算法儘可能地選擇組中空的條目(例如具有無效MESI狀態的條目)。但是，在沒有空條目存在的情況下，可以使用各種算法，包括選擇最近最少使用(LRU)的條目、選擇最近最頻繁使用(MRU)的條目、隨機選擇、按照循環的方式選擇以及它們的變型。通常，不同的算法在不同的環境下能更好地工作。
與一些傳統逐出算法(例如基於LRU和MRU的算法)相關聯的一個缺陷是要求這些算法跟蹤對組中的各種條目的訪問，以確定哪個條目最近最頻繁使用和最近最少使用。但是，在一些高速緩存中，不太可能確定高速緩存行的真實參考模式。具體地，包含式高速緩存典型地不具有對於也在較高級高速緩存中高速緩存的高速緩存行的參考模式。
作為一個例子，在前述NUMA存儲器體系結構的一種實現中，在體系結構中的每個節點可以包括通過一個或者多個處理器總線耦合到節點控制器晶片組的多個處理器，每一個處理器具有僅僅可由該處理器訪問的一個或者多個專用高速緩存器，例如第一級(L1)數據和/或指令高速緩存、第二級(L2)高速緩存和第三級(L3)高速緩存。在節點控制器本身中可以實現附加的第四級(L4)高速緩存，並由所有處理器共享。
在L4高速緩存被實現為包含式高速緩存的情況下，L4高速緩存通常對於給定高速緩存行的真實參考模式不具有充分的可見性。具體地，只要L4高速緩存檢測到在處理器總線上的訪問，通過處理器總線耦合到每個處理器的外部L4高速緩存通常僅僅可以確定什麼時候訪問高速緩存行。但是，在高速緩存行起初裝載到處理器的專用高速緩存之後，由同一處理器所頻繁使用的高速緩存行不再產生在處理器總線上執行的任何操作。因此，依靠對高速緩存行的跟蹤訪問的L4高速緩存的高速緩存逐出算法可能會做出關於這些高速緩存存儲行的參考模式的不正確假設，並且因此選擇將錯誤的高速緩存行逐出。
因此，在本領域中，十分需要與包含式高速緩存一起使用的改進的逐出算法。
發明內容
通過利用對於包含式高速緩存的基於狀態的高速緩存逐出算法，本發明旨在解決與現有技術相關的這些和其它問題，該算法可以至少部分地基於在較高級高速緩存中的高速緩存行的狀態，來確定從包含式高速緩存中逐出多個高速緩存行中的哪一行。具體地，與本發明一致的高速緩存逐出算法從對於較低級高速緩存的包含式高速緩存目錄確定高速緩存行是否高速緩存在較低級高速緩存中而沒有高速緩存在任何多個較高級高速緩存，其中對於所述較高級高速緩存，高速緩存目錄信息附加地存儲在高速緩存目錄中；以及基於確定高速緩存行高速緩存在較低級高速緩存中而沒有高速緩存在多個較高級高速緩存的任何一個中，從較低級高速緩存中逐出高速緩存行。
在所附的權利要求中，闡述了表徵本發明特徵的這些和其它優勢和特徵，它們構成本發明的另外一部分。但是，為了更好地理解本發明以及通過它的使用所實現的優勢和目的，應當參考附圖以及所附的描述性內容，其中描述了本發明的示例性實施例。
圖1是適合於利用與本發明一致的基於狀態的高速緩存逐出算法的多節點計算機系統的方框圖；
圖2是圖1的多節點計算機系統的節點之一的高速緩存體系結構的方框圖；圖3是描述在圖2的高速緩存體系結構的L4高速緩存中實現基於狀態的高速緩存逐出算法的高速緩存行填充請求處理例程的流程圖；圖4是存儲在圖2的高速緩存體系結構中的一組高速緩存行的示例性狀態的方框圖；圖5是描述命中L4高速緩存的高速緩存行請求產生的從圖4狀態的狀態變化的方框圖；圖6是一方框圖，描述當對於L4高速緩存中所請求的高速緩存行在關聯組中具有可利用的空條目時，未命中L4高速緩存的高速緩存行請求產生的從圖5狀態的狀態變化；圖7是一方框圖，描述當對於L4高速緩存中所請求的高速緩存行在關聯組中具有可利用的條目時未命中L4高速緩存的高速緩存行請求產生的從圖6狀態的狀態變化，其中該所請求的高速緩存行對應於在L4高速緩存中高速緩存的而沒有在任何較高級高速緩存中高速緩存的高速緩存行；圖8是一方框圖，描述當對於L4高速緩存中所請求的高速緩存行在關聯組中沒有可利用的條目時未命中L4高速緩存的高速緩存行請求產生的從圖7狀態的狀態變化，其中該所請求的高速緩存行對應於在L4高速緩存中高速緩存的而沒有在任何較高級高速緩存中高速緩存的高速緩存行；以及圖9是一方框圖，描述當對於L4高速緩存中所請求的高速緩存行在關聯組中具有多個可利用的條目時未命中L4高速緩存的高速緩存行請求產生的從圖8狀態的狀態變化，其中該所請求的高速緩存行對應於在L4高速緩存中高速緩存的而沒有在任何較高級高速緩存中高速緩存的高速緩存行。
具體實施例方式
此後所討論和描述的實施例實現了一種用於包含式高速緩存的基於狀態的高速緩存逐出算法，其至少部分地基於較高級高速緩存中的高速緩存行的狀態。具體地，與本發明一致的高速緩存逐出算法試圖確定高速緩存在包含式高速緩存中而沒有高速緩存在任何與其耦合的較高級高速緩存中的高速緩存行。因此，與仍然高速緩存在較高級高速緩存中並且由此假設為仍然被處理器所使用的高速緩存行相比，選擇逐出不再存在於較高級高速緩存中並且假設為不為這些高速緩存所服務的處理器所使用的高速緩存行。由此，減小了處理器需要在不久的將來訪問逐出的高速緩存行的可能性，從而最小化了高速緩存未命中以及對性能產生影響的可能性。
另外，在許多實現中，由於最小化了與通知較高級高速緩存無效它們的逐出高速緩存行的副本相關聯的開銷，因此實現了附加的性能好處，因為逐出沒有高速緩存在較高級高速緩存中的高速緩存行不需要通知任何較高級高速緩存這種高速緩存行的逐出。特別地，在包含式高速緩存經由例如處理器總線的有限帶寬接口耦合到較高級高速緩存的環境中，這種後無效(back-invalidate)業務量的消除減少了處理器總線的使用並且釋放帶寬用於其它操作。另外，在管線處理器體系結構中，消除後無效業務量也可以最小化由於這些業務量引起的內部處理器管線中斷。
與本發明一致的高速緩存逐出算法典型地根據對於較低級高速緩存的包含式高速緩存目錄，來確定高速緩存行是否高速緩存在較低級高速緩存中而沒有高速緩存在多個較高級高速緩存的任一個中，其中對於較高級高速緩存，高速緩存目錄信息附加地存儲在高速緩存目錄中。正如以下將更詳細地討論的，該確定可以基於維護在較低級高速緩存目錄中的狀態信息，其中該狀態信息表示高速緩存行是否高速緩存在較高級高速緩存中。這種狀態信息可以與對於較低級高速緩存中的高速緩存行的狀態信息相結合，或者可以獨立地進行維護。而且，狀態信息可以表示哪個較高級高速緩存具有高速緩存行的有效副本，或者狀態信息可以簡單地表示耦合到較低級高速緩存的一些較高級高速緩存具有高速緩存行的有效副本，而不確定哪個較高級高速緩存具有該有效副本。例如通過處理器或者通過處理器總線，可以將對於多個較高級高速緩存的狀態信息分組在一起，或者可以分別維護對於每個高速緩存的狀態信息。狀態信息也可以標識較高級高速緩存中的高速緩存行的真實狀態，或者可替換地，可以僅僅表示較高級高速緩存具有處於非無效狀態的高速緩存行的副本。作為一個例子，對於較低級高速緩存的高速緩存目錄可以僅僅需要單個比特，其表示關聯的高速緩存行的有效副本是否高速緩存在較高級高速緩存中。但是，應當理解，在其他實施例中，附加的狀態信息可以存儲在較低級高速緩存目錄中。
也正如以下將變得更加清楚的，可以將本發明基於較高級目錄中的高速緩存行的狀態的高速緩存行逐出結合到各種已知逐出算法中。例如，正如以下將更詳細地描述的，可以期望在多路組關聯的包含式高速緩存中實現逐出算法，其中首先選擇關聯組中的空條目，如果不存在空條目則選擇高速緩存在包含式高速緩存中但沒有高速緩存在任何較高級高速緩存中的高速緩存行的條目，以及最後如果沒有找到高速緩存在包含式高速緩存中但沒有高速緩存在較高級高速緩存中的高速緩存行，則通過MRU、LRU、隨機、循環或者其它傳統算法選擇條目。另外，可以期望在一些實施例中與確定關聯組中的多個條目具有沒有高速緩存在較高層高速緩存中的高速緩存行相結合來應用MRU、LRU、隨機、循環或者其它技術。
應當理解，只要一個較低級高速緩存耦合到計算機的較高級高速緩存和主存儲器的中間，該高速緩存就是相對於包含式較低級高速緩存的「較高級高速緩存」。在以下描述的實施例中，例如，較低級高速緩存是多節點計算機的節點控制器中的L4高速緩存，而較高級高速緩存是設置在與節點控制器耦合的處理器內的L1、L2和L3高速緩存。應當理解，較高級高速緩存和較低級高速緩存可以直接相互耦合，或者經由中間存儲器或者高速緩存相互耦合。另外，較高級高速緩存可以專用於特定處理器，或者可以由多個處理器共享。而且，較高級高速緩存可以是多路組相關聯或者單路組相關聯，本身可以是包含式的或者排他的，並且可以僅僅是數據或者指令高速緩存。對於從該即時公開中受益的本領域技術人員來說，其它變型是顯而易見的。
現在回到附圖，其中相同的數字在全部若干視圖中代表相同的部分，圖1描述了表示一個合適環境的多節點計算機50，其中，可以按照與本發明一致的方式實現在此所描述的基於狀態的高速緩存逐出算法。計算機50通常表示例如各種多用戶計算機中的任意一種，多用戶計算機例如網絡伺服器、中程計算機、大型計算機等等。但是，應當理解，本發明可以在實際上能夠利用包括多個高速緩存級的共享存儲器體系結構的任何設備中實現，這種設備包括其它計算機和數據處理系統，例如在單用戶計算機(如工作站、臺式計算機、可攜式計算機等等)或者在其它可編程電子器件(例如併入嵌入式控制器等等)中實現。可編程電子器件如機頂盒、遊戲機等等。
實現為多節點計算機的計算機50包括多個節點52，每個節點通常包括一個或者多個處理器54，每個處理器包括一個或者多個高速緩存55，並且耦合到一個或者多個系統或者處理器總線56。將晶片組高速緩存59、處理器總線接口60以及存儲器接口62相結合的晶片組58也耦合到每個處理器總線24，存儲器接口62通過存儲器總線66連接到存儲器子系統64。存儲器子系統通常包括多個存儲設備，例如DRAM 68，其為每個節點52提供主存儲器。
為了與外設和其它外部設備連接，晶片組58還包括輸入/輸出接口70，提供到I/O子系統72的連接。而且，為了提供節點間連接，在每個節點中提供了節點間接口，例如可擴展埠接口74，以經由通信鏈路75耦合到一個或者多個其它節點52。晶片組58通常還包括駐留在其中的多個緩存器，例如中央緩存器77，以及分別設置在處理器總線接口60和可擴展埠接口74中的一個或者多個專用緩存器61、75。晶片組58還包括在此稱為一致性單元76的控制邏輯，以管理對以下存儲器請求的處理，該請求由處理器54和/或者遠程節點52通過可擴展埠互聯75提供給晶片組。
應當理解，在晶片組58中，可以支持任何給定類型的多埠或者接口。正如圖1所示，例如，可以期望在每個節點中支持多個處理器總線(或者總線分段)，這可能會需要獲得由一個處理器總線上的處理器所請求的數據的來源，而這通過傳送來自另一個處理器總線上處理器的數據來實現。而且，由晶片組58支持的各種接口可以實現任意數目的已知協議。例如，晶片組58可以與來自英特爾公司的用於處理器的Xeon行的處理器總線協議相兼容。但是，應當理解，本發明的原理可應用到其它計算機實現中，包括其它多節點設計、單節點設計、以及利用多級存儲器系統的其它設計。
可以使用一個或者多個集成電路器件來實現晶片組58，並且晶片組58可以用來與附加的電子部件連接，這些部件例如圖形控制器、音效卡、固件、服務處理器等等。因此，應當理解，術語「晶片組」可以描述實現在此所描述的功能的單個集成電路晶片，並且甚至可以整體上或者部分地集成到例如處理器晶片的另一個電子部件中。
計算機50，或者其中部件的任何子集，此後可以被稱為「裝置」。應當意識到，術語「裝置」可以被認為包括了例如計算機和其它電子器件的各種數據處理系統以及這些系統內的各種部件，包括單獨的集成電路器件或者它們的組合。而且，在裝置內，可以包括一個或者多個邏輯電路，它們將各個布置連接成電路，這些布置通常實現在一個或者多個集成電路器件上，並且可選地包括與其連接的附加分立部件。
還應當意識到，通常至少部分地使用在此被稱為硬體定義程序的一個或者多個計算機數據文件來設計和製造電路布置，其中硬體定義程序定義了在集成電路器件上電路布置的布圖設計。通常通過設計工具以已知的方式生成程序，並且隨後在製造期間加以使用來創建布圖設計掩模，掩模定義了應用到半導體晶片上的電路布置。通常，使用硬體定義語言(HDL)(例如VHDL、Verilog、EDIF等等)以預定格式提供程序。這樣，雖然在以充分實現了功能的集成電路器件來實現的電路布置的上下文中已經對本發明並且隨後還將對本發明進行描述，但是，本領域技術人員應當理解，與本發明一致的電路布置能夠作為程序產品以各種形式來分發，並且本發明可以等效地來應用，而不管用來實際執行該分發的計算機可讀介質的特定類型。計算機可讀介質的例子包括但不局限於有形的可記錄類型介質，例如，易失和非易失存儲設備、軟盤、硬碟驅動器、CD-ROM和DVD等等，以及傳輸類型介質，例如數字和模擬通信鏈路。
圖2描述了在計算機50上多個節點52之一的示例性高速緩存體系結構。在該體系結構中，四個處理器晶片54(也被表示為處理器0-3)經由一對處理器總線56(也被表示為處理器總線A和B)耦合到晶片組。處理器0和1耦合到處理器總線A，而處理器2和3耦合到處理器總線B。
另外，在該示例性體系結構中，提供了四級高速緩存，L1、L2和L3高速緩存55A、55B和55C設置在每個處理器晶片54中，以及晶片組高速緩存59被實現為L4高速緩存。L1高速緩存55A被實現為分立的指令和數據高速緩存，而L2和L3高速緩存55B和55C高速緩存指令和數據兩者。
L4高速緩存59包括高速緩存目錄80和數據組82，它們可能設置在同一集成電路中或者可能不設置在同一集成電路中。L4高速緩存被實現為包含式4路組相關聯高速緩存，包括N個關聯組0到N-1，在目錄80中的每個關聯組84包括分別與四個關聯類0、1、2和3相關聯的四個條目86、88、90和92。在目錄80中的每個條目86-92包括標籤欄位94，其存儲當前高速緩存的高速緩存行的標籤；以及狀態欄位96，其例如使用MESI協議或者現有技術中已知的其它狀態協議存儲當前高速緩存的高速緩存行的狀態。每個條目86-92在數據組82中具有相關聯的存儲區(slot)98，其中存儲對於每個高速緩存的高速緩存行的數據。
在每個條目86-92中的狀態欄位96存儲對於L4高速緩存和較高級L1-L3高速緩存55A、55B和55C兩者的狀態信息。在所描述的實施例中，對於較高級高速緩存的狀態信息是基於通過處理器總線基礎的處理器總線，並且此外，用於每個處理器總線以及L4高速緩存的狀態信息被編碼成單個欄位。例如，在與發明一致的一個實施例中，用於L4高速緩存、處理器總線A(PBA)高速緩存以及處理器總線B(PBB)高速緩存的狀態信息被編碼成5比特欄位，正如以下表1所顯示的那樣。此外，在所描述的實施例中，每當處理器修改了它的高速緩存行的副本，處理器並不會通知L4高速緩存，這樣L4高速緩存就不能區分對於每個處理器總線的「排他的」或者「修改的」狀態。在另一個實施例中，處理器可以通知L4高速緩存從「排他的」狀態變化到「修改的」狀態，使得L4高速緩存將更新對於高速緩存行的合適PBA或者PBB。
表1實例狀態編碼
本領域的一個普通技術人員應該理解，可以使用其它狀態協議，正如其它映射和編碼那樣。此外，可以在逐個處理器基礎上劃分狀態信息，或者狀態信息可以簡單地表示任何處理器是否具有高速緩存行的有效副本。從該即時公開中受益的本領域的一個技術人員將可以理解存儲表示較高級高速緩存是否具有高速緩存行的有效副本的狀態信息的其它變型。
圖3接下來描述了高速緩存行填充請求處理例程100，其在計算機50的L4高速緩存59的控制邏輯中實現基於狀態的高速緩存逐出算法。具體地，塊102描述了接收到來自耦合到晶片組58的處理器54之一的輸入的高速緩存行填充請求。接下來，塊104確定所請求的高速緩存行是否在L4高速緩存中，以及L4 MESI狀態是否為除無效之外的任何狀態(即，高速緩存命中)。如果是，控制進行到塊106，以便通過訪問來自L4高速緩存的數據並且將數據返回請求的處理器來處理該請求。另外，在該示例性實施例中假設在以下情況下高速緩存執行LRU算法，即沒有在關聯組中找到未使用的高速緩存行的條目，或者如果所有條目當前正在使用，則在關聯組中沒有找到在L4高速緩存中高速緩存但沒有在較高級高速緩存中高速緩存的條目。同樣地，塊106也更新存儲在L4高速緩存目錄中的LRU信息。則完成了高速緩存行請求的處理。
返回到塊104，如果沒有發生高速緩存命中，則必須從替換源(例如節點存儲器、遠程節點等等)中提取數據。另外，必須在L4高速緩存中分配用於新高速緩存行的空間。如此，控制進行到塊108，以便例如通過確定關聯組中的任何條目是否具有無效的狀態，來確定關聯組中是否存在所請求的高速緩存行的可利用或者未使用的條目。如果是，則控制進行到塊110，以便從節點存儲器或者遠程節點(當合適時)訪問所請求的數據。一旦取回了數據，則數據就被寫入到空的條目，同時相應更新該條目的MESI狀態和LRU信息。則完成了高速緩存行請求的處理。
返回到塊108，如果沒有找到可利用的條目，控制進行到塊112，以便例如通過確定對於所有處理器總線任何條目是否具有無效狀態，來確定關聯組中所請求的高速緩存行的條目是否與當前沒有在較高級高速緩存中高速緩存的高速緩存行相關聯。如果是，控制進行到塊114，以便從節點存儲器或者遠程節點(當合適時)訪問所請求的數據。一旦取回了數據，則移走所確定的條目中現有的數據，並且利用取回的數據代替它，同時相應更新對於該條目的MESI狀態和LRU信息。則完成了高速緩存行請求的處理。
返回到塊112，如果沒有找到與沒有在較高級高速緩存中高速緩存的高速緩存行相關聯的條目，則控制進行到塊116，以根據替代的算法(例如前述LRU算法)選擇條目。如此，塊116從節點存儲器或者遠程節點(當合適時)訪問所請求的數據，並且根據替代的算法(例如最近最少使用的條目)選擇條目。另外，將無效請求發送到對於與所選擇條目相關聯的高速緩存行相關的一個處理器總線或者多個處理器總線，移走選擇條目中現有的數據，並且利用取回的數據代替它，同時相應更新對於該條目的MESI狀態和LRU信息。則完成了高速緩存行請求的處理。
應當理解，可替代地，其它的邏輯可以在例程100中實現。例如在塊108找到多個可利用的條目或者在塊112中找到與沒有高速緩存在較高級高速緩存中的高速緩存行相關聯的多個條目的情況下，可以使用與在塊116中所使用的相同或者不同的替代算法來從多個條目中進行選擇。
通過描述經由例程100中實現的邏輯來處理一系列高速緩存行請求的結果，圖4-9提供了在計算機50中實現的基於狀態的高速緩存逐出算法的作的另一個示意圖。具體地，圖4描述了存儲在L4高速緩存目錄80中的一組四個關聯組84，具有存儲在每個關聯類條目86、88、90和92中的示例性標籤和狀態信息94、96。在圖4中，假設標識為A0-A3、B0-B3、C0-C3和D0-D3的高速緩存行存儲在以下高速緩存中，這些高速緩存在每個條目86-92中具有標識相關高速緩存行的關聯標籤信息，並且對於每個條目具有標識在L4高速緩存、處理器總線A處理器和處理器總線B處理器的每一個中的高速緩存行狀態的MESI狀態信息。明顯地，在關聯組0的類2中的高速緩存行C0被顯示為無效的，而其餘條目被顯示為具有有效高速緩存行。圖4也描述了在相關聯的較高級高速緩存55中每個高速緩存行的本地MESI狀態。
圖5描述了對來自處理器總線B上處理器的對地址120的高速緩存行請求的處理，該地址具有標識高速緩存行D0的標籤部分122、標識關聯組0的索引部分和表示所請求的高速緩存行中地址偏移的偏移部分126。明顯地，因為與關聯組0的類3中的高速緩存行D0一起高速緩存了地址120，所以例程100(圖3)在塊104中將檢測到高速緩存命中，以及正如上述結合塊106所描述的那樣處理該請求，通過處理器總線B將所請求的高速緩存行返回到請求的處理器，並更新對於高速緩存行D0的狀態信息，以表示在處理器總線B上的處理器現在具有處於排他狀態的高速緩存行。
圖6接下來描述了對來自處理器總線A上處理器的對地址128的高速緩存行請求的處理，該地址具有標識高速緩存行E0的標籤部分122以及標識關聯組0的索引部分。明顯地，因為當前沒有對高速緩存行E0進行高速緩存(即高速緩存行E0的標籤信息與關聯組0中的任何條目86-92的標籤信息不相匹配)，所以例程100(圖3)在塊104中將檢測到高速緩存未命中。此外，因為在關聯組0中的其中一個條目(條目90)表示所有狀態是無效的，所以塊108將確定存在可利用的條目，並且正如上述結合塊110描述的那樣處理該請求，通過處理器總線A將所請求的高速緩存行返回到請求的處理器，並在條目90中寫入高速緩存行E0的標籤和狀態信息，以表示在處理器總線A上的處理器現在具有處於排他狀態的高速緩存行。
圖7接下來描述了對來自處理器總線B上處理器的對地址130的高速緩存行請求的處理，該地址具有標識高速緩存行F3的標籤部分122以及標識關聯組3的索引部分。明顯地，因為目前沒有對高速緩存行F3進行高速緩存(即高速緩存行F3的標籤信息與關聯組3中的任何條目86-92的標籤信息不相匹配)，所以例程100(圖3)在塊104中將檢測到高速緩存未命中。此外，因為在關聯組3中沒有條目表示所有狀態是無效的，所以塊108將確定不存在可利用的條目。此外，因為在關聯組3的關聯類0中的條目86表示沒有在任何處理器中對高速緩存行A3進行高速緩存(因為對於每個處理器總線的狀態是無效的)，所以塊112將確定存在對於沒有在較高級高速緩存中高速緩存的高速緩存行的條目，並且正如上述結合塊114描述的那樣處理該請求，通過處理器總線B將所請求的高速緩存行返回到請求的處理器，並將對於高速緩存行F3的標籤和狀態信息寫入到條目86，以表示處理器總線B上的處理器現在具有處於排他狀態的高速緩存行。明顯地，因為沒有在任何處理器中對高速緩存行A3進行高速緩存，所以不需要將無效請求發送給任何處理器總線，如果另外要求，則選擇關聯組中另一個高速緩存行來代替。
圖8接下來描述了對來自處理器總線A上處理器的對地址132的高速緩存行請求的處理，該地址具有標識高速緩存行G1的標籤部分122以及標識關聯組1的索引部分。明顯地，因為當前沒有對高速緩存行G1進行高速緩存(即高速緩存行G1的標籤信息與關聯組1中的任何條目86-92的標籤信息不相匹配)，所以例程100(圖3)在塊104中將檢測到高速緩存未命中。此外，因為在關聯組1中沒有條目表示所有狀態是無效的，所以塊108將確定不存在可利用的條目。此外，因為在關聯組1沒有條目與沒有在任何處理器中高速緩存的高速緩存行相關聯(因為對於每個條目的狀態具有對於處理器總線之一的至少一個非無效狀態)，所以塊112將確定不存在對於沒有在較高級高速緩存中高速緩存的高速緩存行的條目，並且正如上述結合塊116描述的那樣處理該請求。假設例如條目88是關聯組1中最近最少使用的條目，則塊116可以選擇該條目來代替，通過處理器總線A將所請求的高速緩存行返回到請求的處理器，並將對於高速緩存行G1的標籤和狀態信息寫入到條目88，以表示處理器總線A上的處理器現在具有處於排他狀態的高速緩存行。另外，塊116將通過處理器總線B發送無效請求，以無效對於處理器3在高速緩存中的高速緩存行B1的副本(見圖4)。
圖9接下來描述了對來自處理器總線A上處理器的對地址134的高速緩存行請求的處理，該地址具有標識高速緩存行H2的標籤部分122以及標識關聯組2的索引部分。明顯地，因為當前沒有對高速緩存行H2進行高速緩存(即高速緩存行H2的標籤信息與關聯組2中的任何條目86-92的標籤信息不相匹配)，所以例程100(圖3)在塊104中將檢測到高速緩存未命中。此外，因為在關聯組2中沒有條目表示所有狀態是無效的，所以塊108將確定不存在可利用的條目。此外，因為在關聯組2的關聯類0和1中的條目86和88表示沒有在任何處理器中對高速緩存行A2和B2進行高速緩存(因為對於每個處理器總線的狀態是無效的)，所以塊112將確定存在對於沒有在較高級高速緩存中高速緩存的高速緩存行的條目，並且正如上述結合塊114描述的那樣處理該請求。此外，因為多個條目與該標準匹配，所以在塊114中，將使用替代算法(例如LRU、MRU、隨機、循環等等)從多個條目中進行選擇。例如，可以期望在相匹配的條目中簡單地選擇最低關聯類，在這種情況下為關聯類0。這樣，在該實例中，塊114將通過處理器總線A將所請求的高速緩存行返回到請求的處理器，並將對於高速緩存行H2的標籤和狀態信息寫入到條目86，以表示處理器總線A上的處理器現在具有處於排他狀態的高速緩存行。明顯地，因為沒有在任何處理器中對高速緩存行A2進行高速緩存，所以不需要將無效請求發送給任何處理器總線。
應當理解，可以對與本發明一致的所描述的實施例做出各種修改。也應當理解，在設置在晶片組或者其它合適的集成電路器件的邏輯電路內實現上述功能將適當地在從該即時公開中受益的本領域普通技術人員的能力之內。
權利要求
1.一種電路布置，包括多個處理器，每個處理器包括至少一個較高級高速緩存；以及包含式多路組關聯的較低級高速緩存，耦合到所述多個處理器，所述較低級高速緩存包括高速緩存目錄，所述高速緩存目錄包括對於多個高速緩存行的高速緩存目錄信息，其中所述多個高速緩存行當前高速緩存在所述較低級高速緩存和多個處理器中的任何一個中，所述較低級高速緩存被配置為響應於對所請求的高速緩存行的高速緩存未命中，基於對一個高速緩存行高速緩存在所述較低級高速緩存中而沒有高速緩存在所述多個處理器的任何一個中的確定，從所述較低級高速緩存中有選擇地逐出該高速緩存行。
2.一種電路布置，包括包含式高速緩存目錄，與較低級高速緩存相關聯，並且被配置為存儲對於所述較低級高速緩存和多個較高級高速緩存的高速緩存目錄信息；以及控制邏輯，耦合到所述包含式高速緩存目錄，並且被配置為基於對一個高速緩存行高速緩存在所述較低級高速緩存中而沒有高速緩存在所述多個較高級高速緩存的任何一個中的確定，從所述較低級高速緩存中有選擇地逐出該高速緩存行。
3.根據權利要求2的電路布置，其中，所述較低級高速緩存設置在多節點數據處理系統的節點控制器中，並且其中所述多個較高級高速緩存設置在耦合到所述節點控制器的多個處理器中。
4.根據權利要求3的電路布置，其中，所述較低級高速緩存是第四級高速緩存，並且其中所述多個較高級高速緩存包括設置在耦合到所述節點控制器的所述多個處理器的每個處理器中的至少一個第一、第二和第三級高速緩存。
5.根據權利要求2的電路布置，還包括對於所述較低級高速緩存的高速緩存存儲器。
6.根據權利要求2的電路布置，其中，所述控制邏輯被配置為響應於對於在所述較低級高速緩存上未命中的另一高速緩存行的請求，有選擇地逐出所述高速緩存行。
7.根據權利要求6的電路布置，其中，所述包含式高速緩存目錄包括多路組關聯的高速緩存目錄，其中，所述另一高速緩存行在與所述逐出的高速緩存行相同的關聯組中，並且其中所述控制邏輯被配置為僅僅在確定對於所述關聯組不存在空的關聯類之後，有選擇地逐出所述高速緩存行。
8.根據權利要求7的電路布置，其中，所述控制邏輯進一步被配置為響應於在所述關聯組中沒有關聯類存儲如下高速緩存行的確定而應用高速緩存替代算法，所述高速緩存行高速緩存在所述較低級高速緩存中但沒有高速緩存在所述多個較高級高速緩存的任何一個中。
9.根據權利要求8的電路布置，其中，從由最近最少使用、最近最多使用、隨機和循環組成的組中選擇所述高速緩存替代算法。
10.一種集成電路器件，包括權利要求2的所述電路布置。
11.一種晶片組，包括權利要求2的所述電路布置。
12.一種數據處理系統，包括多個處理器；以及節點控制器，耦合到所述多個處理器，並且包括權利要求2的所述電路布置，其中，所述多個較高級高速緩存設置在所述多個處理器中。
13.根據權利要求12的數據處理系統，其中，所述多個處理器和所述節點控制器設置在所述數據處理系統的多個節點當中的第一節點中。
14.一種程序產品，包括定義權利要求2的所述電路布置的硬體定義程序，以及載有所述硬體定義程序的計算機可讀介質。
15.一種從高速緩存中逐出高速緩存行的方法，該方法包括從對於較低級高速緩存的包含式高速緩存目錄中確定高速緩存行是否高速緩存在所述較低級高速緩存中但是沒有高速緩存在多個較高級高速緩存的任何一個中，其中對於所述較高級高速緩存的高速緩存目錄信息附加地存儲在所述高速緩存目錄中；以及基於對所述高速緩存行高速緩存在所述較低級高速緩存中而沒有高速緩存在所述多個較高級高速緩存的任何一個中的確定，從所述較低級高速緩存中逐出該高速緩存行。
16.根據權利要求15的方法，其中，所述較低級高速緩存設置在多節點數據處理系統的節點控制器中，並且其中所述多個較高級高速緩存設置在耦合到所述節點控制器的多個處理器中。
17.根據權利要求16的方法，其中，所述較低級高速緩存是第四級高速緩存，並且其中所述多個較高級高速緩存包括設置在耦合到所述節點控制器的所述多個處理器的每個處理器中的至少一個第一、第二和第三級高速緩存。
18.根據權利要求15的方法，其中，響應於對於在所述較低級高速緩存上未命中的另一高速緩存行的請求，執行確定和逐出。
19.根據權利要求18的方法，其中，所述包含式高速緩存目錄包括多路組關聯的高速緩存目錄，其中，所述另一高速緩存行在與所述逐出的高速緩存行相同的關聯組中，並且其中僅僅在確定對於所述關聯組不存在空的關聯類之後，執行逐出所述高速緩存行。
20.根據權利要求19的方法，還包括響應於在所述關聯組中沒有關聯類存儲如下高速緩存行而應用高速緩存替代算法，所述高速緩存行高速緩存在所述較低級高速緩存中但沒有高速緩存在所述多個較高級高速緩存的任何一個中。
21.根據權利要求20的方法，其中，從由最近最少使用、最近最多使用、隨機和循環組成的組中選擇所述高速緩存替代算法。
全文摘要
一種用於包含式高速緩存的高速緩存逐出算法，它可以至少部分地基於在較高級高速緩存中的高速緩存行的狀態，來確定從包含式高速緩存中逐出多個高速緩存行當中的哪一行。具體地，高速緩存逐出算法從對於較低級高速緩存的包含式高速緩存目錄中確定高速緩存行是否高速緩存在較低級高速緩存中但沒有高速緩存在多個較高級高速緩存的任何一個中，對於較高級高速緩存，高速緩存目錄信息附加地存儲在高速緩存目錄中。然後，基於對高速緩存行高速緩存在較低級高速緩存中但沒有高速緩存在多個較高級高速緩存的任何一個中的確定，高速緩存逐出算法可以選擇該高速緩存行，用於從該高速緩存中逐出。
文檔編號G06F12/08GK1940892SQ200610095979
公開日2007年4月4日 申請日期2006年6月29日 優先權日2005年9月29日
發明者布賴恩·T·范德普爾, 杜安·阿林恩·埃夫裡爾 申請人:國際商業機器公司