基於指令基址寄存器的高速緩存路線預測的製作方法

2023-07-19 05:50:56 1

專利名稱：基於指令基址寄存器的高速緩存路線預測的製作方法
發明
背景技術：
1.發明領域這個發明涉及計算機系統領域，尤其涉及一個預測性的n路相關聯高速緩存，它使用指令基址寄存器作為在高速緩存中的特定路線的一個預測器，其中該高速緩存可能包含一個被尋址的數據項。
2.相關技術描述高速緩存系統通常被用於降低與訪問相對低速存儲設備有關的有效延遲。當一個處理器請求訪問在低速存儲器中的一個特定數據項時，高速緩存系統把所請求的數據加載到一個高速存儲器中。爾後，經由該高速存儲器提供對這個同一數據項的後續訪問，由此避免了與低速存儲器有關的延遲。通常，當數據項被請求時，把包含所請求數據項的一「行」數據項從低速存儲器中加載到高速存儲器中，以便在所加載行內的任何數據項都能夠隨後由該高速存儲器提供。
一個高速緩衝存儲器存取系統的效率是由將來數據存取與先前的數據存取相關的可能性提供的。通常，一個請求的數據正被包含在與一個先前請求的數據項同一行的高速緩存中的可能性實質上大於零，因此滿足來自於高速的高速緩衝存儲器請求的可能性相應地實質上大於零。
高速存儲器比低速存儲器更昂貴，因此可用的高速緩衝存儲器數量通常是有限的。高速緩存管理方案被用來確定當新的一行數據需要被加載到高速存儲器中時，哪些數據項將從該高速存儲器中除去。通常使用的一種用於在高速存儲器中保持數據項的優先化方案是一種「最近最少使用(LRU)」標準，其中最近最少使用的(即「舊的」)存儲器存取行被新的一行代替，由此保持最近使用/存取的數據項。也可以典型地結合LRU優先化方案使用其它標準、諸如「最經常使用的」。
相關聯高速緩存通常被用來基於所請求項的一個地址子集存儲多行數據項。

圖1說明了一種傳統的、用於一個相關聯高速緩存100的尋址方案。一般來自於一個處理器的地址110被邏輯分區成為一個標記欄位111、一個變址欄位112、和一個字欄位113，這將在以下進行進一步討論。變址欄位112在一個高速緩存120中向相關的一組高速緩存線提供一個變址。該組中的每條高速緩存線路被稱為一「路」，而且高速緩存100對應於一個n路相關聯高速緩存。字欄位113的大小j對應於一個數據行的大小2j。也就是說，如果每一數據行有十六個字，則字欄位113的大小將是四位；如果每一數據行有六十四個字，則字欄位113將是六位寬。使用在字欄位113和數據行大小之間的這個2次冪關係，標記和變址欄位唯一地標識該存儲器中的每一數據行。
當從一個低速存儲器(未顯示)中把一個被尋址的數據項加載到高速緩存120中時，包含該數據項的那個數據行被放置在一個選擇路中，變址欄位定義在所選擇路中用於放置該數據行的位置。使用各種普通可用算法中的一種、諸如上述的LRU優先化方案，實現該路的選擇。當所尋址的數據項被保存在該高速緩存中的一個特定行區域DLine-a、DLine-b等中時，標記欄位111也被存儲，如在圖1中的欄位Tag-a、Tag-b所示。所存儲的標記欄位與在該路內、對應於數據行的變址欄位的數據行位置唯一地標識被保存在高速緩存120中的數據行。
在一個被尋址的數據項被加載到高速緩存120中之前，檢查高速緩存120以確定該數據項是否已經位於高速緩存120中了，以潛在地避免不得不從低速存儲器中加載數據項。由於對這個數據項的一個先前訪問，或者由於對在與當前被尋址數據項在同一數據行DLine-a、DLine-b等內的一個數據項的先前訪問，被尋址的數據項可以位於高速緩存中。變址欄位112定義在高速緩存中、與這個地址有關的n行組。經由比較器130a、130b等把每一個被存儲的、對應於在相關組中的每一個被存儲行125a、125b等的標記121a、121b等，與被尋址數據項的標記欄位111進行比較。在這個比較正在進行的同時，對應於變址欄位113的每一個被存儲數據行125a、125b等被加載到一個高速緩存140中，以便如果該數據項當前被加載到高速緩存中，則是可用的。
如果被尋址的數據項當前被加載到高速緩存中，則相應的比較器130a、130b等聲明一個高速緩存命中信號，由此標識包含該數據行的特定路線Hit-a、Hit-b等。如果聲明了一次命中，則使用字欄位113從包含在緩存140中的數據行中選擇適當的字141a、141b等，從相應的緩存140中得到適當的字。把所得到的字發送到提供地址110的處理器。在高速緩存系統100的一個傳統實施例中，當發生一個高速緩存命中時，實現標記欄位111與所存儲的標記欄位120a、120b等的比較、以及適當字141a、141b等的後續選擇，所要求的時間實質上小於對應於低速存儲器的延遲時間。這樣，當數據項位於高速緩存120中時，對一個數據項的有效存取時間實質上被減小了。
如果沒有發生一個高速緩存命中，則典型地，如上所述，通過加載該數據行到最近最少使用的(LRU)路中或者其它優先化方案，實現以上描述的、從存儲器中加載被尋址的數據行到高速緩存120的一個選擇路Way-a、Way-b等中。
有效地從處理器中把字存儲到存儲器所要求的時間通過使用高速緩存120被同樣加速了。通過使用以上描述的比較處理，確定在高速緩存120中存在被尋址的數據項。如果數據項當前位於高速緩存120中，則用來自於處理器的新數據項值代替緩存140中的所選擇字，而且緩存140被加載到包含所尋址數據項的數據行125a、125b等中。「被修改的」欄位129用來發信號通知一條高速緩存線的內容已經改變了。在用新的數據行覆蓋一個數據行之前，檢查被修改的欄位129，而且如果該數據行已經被修改了，則使用所存儲的標記欄位121a、121b等以標識在存儲器中用以存儲該行的位置，把被修改了的數據行存儲回存儲器中。
雖然一個n路相關聯高速緩存提供了一個用於增加有效存儲器訪問速度的有效裝置，但是同時的路線比較方案與一個單路相關聯高速緩存相比要以比其高n倍的比率損耗能量，其中把被尋址的數據項標記與所有存儲的標記進行比較。使n路相關聯高速緩存實質上比一個集成電路、或者印刷電路板的其它區域更熱是很平常的。
為了減少一個傳統的n路相關聯高速緩存的能量損耗，應用預測技術以選擇一條對應於一個給定地址的可能路線。在一個路線預測方案的傳統實施例中，可能的路線是首先檢查被尋址的數據項，而且只有當那條路線不包含被尋址的數據項時才檢查剩餘的路線。在KojiInoue等人刊登於2000年2月的IEICE Trans.Electron.E83-C卷2期186-194頁上的「A HIGH-PERFORMANCE AND LOW-POWERCACHE ARCHITECTURE WITH SPECULATIVE WAY-SELECTION」中，提出了一種路線預測方案，並且把通過路線預測方案的能量損耗與非預測方案進行比較，其中該文章被包含在內作為參考。如果預測成功率高，則節能就能夠是十分實質的，是因為每當路線預測正確時使能量減少到n分之一。
在圖1中說明了一個路線預測表150的例子，它被用於預測與一個被尋址數據項有關的特定路線。數據地址110的子集被用來索引路線預測表150。可以使用各種方案定義這個地址子集110，並且定義用於提供路線預測表150內容的算法。一個簡單的實施例使用變址欄位113作為用於索引表格150的子集，並且表格150的內容對應於用於每個索引的最近最少使用(LRU)路線Way-a、Way-b等。做為選擇，還可以使用變址欄位112的一個子集、或者從標記欄位111和變址欄位112中取用的一個子集以提供一個到路線預測表150的索引。對用於索引路線預測表的地址子集110和路線數量n的選擇確定了所需要的路線預測表的尺寸。在一個8路相關聯高速緩存中，要求有三位以唯一地標識在路線預測表中的每一條路線，而且在表格150中的三位入口數目是由用於索引表格150的地址子集的唯一組合數目確定的。如果例如使用了十位來索引表格150，則在表格150中必須支持1024(210)個三位入口。
當請求一個地址110時，使用來自於路線預測表150的預測路線來有選擇地僅僅訪問被預測的路線。為了方便起見，在下文中使用了下標p來指定被預測的路線。把在所選擇路線p中對應於變址欄位112的所存儲標記121p提供給所選擇路線的比較器130p，並且把相應的數據行125p提供給所選擇路線p的緩存140p。如果被預測的路線包含該數據行則聲明Hit-p信號，並且把被尋址的字從緩存140p中提供給請求處理器。如果被預測的路線p沒有包含被尋址的數據項，則使用以上討論的、用於在一個n路相關聯高速緩存中檢查一個被尋址數據項的技術，檢查其它每一條未被預測的路線中被尋址數據項的存在。
如果沒有路線包含被尋址的數據項，則從存儲器中加載包含被尋址數據項的數據行到高速緩存120中，典型地在索引位置處加載到最近最少使用的路線中。假定路線預測表150被配置為存儲最近使用的路線，把用於存儲該數據行的路線的一個標識存儲到路線預測表150中。這樣，對與當前被尋址數據項在同一數據行中的一個數據項的後續請求將會產生正確的被預測路線，並且由此節省能量損耗。
還可以使用在這個節能方案上的變體。例如，所有的標記121a、121b等可以被加載到相應的比較器130a、130b等中，但是只有被預測的路線p中的數據行125p可以被加載到緩存140p中。這樣，通過避免加載所有的未被預測路線中的數據行125a、125b到緩存120a、120b等中，同時還避免了當被預測的路線不包含被尋址的數據項時、再檢查所有標記欄位121a、121b所要求的時間，實現了一定的節能。如果其它標記比較器130中的一個聲明了一個命中信號，則相應路線中的數據行被加載到相應的緩存140中，並且把適當的字提供給處理器。如果其它標記比較器130都沒有聲明一個命中信號，則把被尋址的數據行從存儲器中加載到高速緩存120中，如以上所討論那樣。
注意到，在如圖1說明的一種傳統路線預測方案中，在對應於在該指令中的間接地址的存儲器地址確定之後發生路線預測。在流水線結構中，存儲器地址的確定經常是在關鍵路線上，並且為路線預測引入的任何額外延遲可能在整個處理器性能上具有一個直接的影響。
發明簡要概述這個發明的一個目的是提供一種在一個處理器的關鍵路線外允許路線預測的方法和系統。這個發明的一個進一步目的是提供一種潛在地提高在一個n路相關聯高速緩存中的路線預測成功率的方法和系統。這個發明的一個進一步目的是提供一個比傳統基於地址的路線預測方案更有效的路線預測方案。
通過提供一種基於使用間接尋址來訪問在存儲器中的數據項的指令內容、用於一個n路相關聯高速緩存的路線預測方案來實現這些以及其它目的。該間接地址指令的內容在任何時候都可用於流水線處理，而且這個發明的路線預測方案不需要一個存儲器地址計算。一條間接尋址指令的內容還提供了存儲器訪問的一個高級抽象，而且因此和數據項的絕對地址相比，可能更能指示在數據項當中的關係。在一個最佳實施例中，包含在間接地址指令中的基址寄存器提供了一個到一個路線預測表的索引。使用同一個基址寄存器間接尋址的數據項很可能是相關的，而且因此基於一個間接地址指令的基址寄存器在一個n路關聯存儲器中預測一個特定路線很可能導致一個高速緩存命中，由此減小了與訪問在該高速緩存中的所有路線有關的能量損耗。
附圖簡要說明通過舉例並結合附圖對本發明進行了進一步詳細描述，其中圖1說明了一個現有技術的、具有路線預測的n路相關聯高速緩存的框圖實例。
圖2說明了依據這個發明的、具有路線預測的一個n路相關聯高速緩存的框圖實例。
在整個附圖中，相同的標記數字指示了類似或相應的特徵或功能。具有後綴字母的項指示一個共用的特徵或功能的特定例子。在說明書中對沒有一特定後綴字母的這種項的標記指示具有同一個數字標記的任一或所有舉例說明的項。
本發明的詳細說明在圖1中說明了一種用於經由一條間接尋址指令160間接尋址在存儲器中的數據項的共用方法。被提供給處理器的指令160包含一個操作碼欄位161、諸如「加載」、「存儲」等，它定義了將要被執行的操作。基址寄存器162和偏移量164欄位用來間接地引用在存儲器中的一個地址，如以下將進一步詳細描述得那樣。寄存器欄位163標識接收(在一條「加載」指令中)或提供(在一條「存儲」指令中)數據項的處理器內部寄存器。
對於一個大的尋址空間，為包含一個清楚、或直接的地址所必需的一條指令的尺寸將會是大的。即使為了尋址例如64K字的相對小地址空間，也需要在一條指令中分配十六位以包含該地址。較大的地址空間將需要相對大的指令寬度以包含該地址。作為在每條數據傳送指令中提供一個顯式地址的一個備選方案，地址被保存在一寄存器170中，而且指令160僅僅包含這個寄存器的一個標識符162。在一條指令160中對寄存器170的引用提供了一個對包含在寄存器170中地址的間接引用。典型地，提供了8、16、32、或64個寄存器，分別僅需要3、4、5、或6位，用於在指令160中存儲地址的標識162。每一個寄存器170的大小足以包含對應於存儲器地址空間的地址。為了避免不得不用每個新地址重新加載一個寄存器170，在間接地址指令160中提供了一個偏移量欄位164。通過經由加法器180把基址寄存器170內容和偏移量164求和，確定在一條指令160中、對應於到基址寄存器170的引用162和偏移量164的絕對地址110。取決於特定處理器，偏移量可以是一個有符號的或無符號的整數，有符號的整數配置考慮了距基址寄存器170內容的正向和反向偏移。
這個發明是以間接尋址指令經常在一程序中提供一個較高水平的抽象數據關係的觀察為前提的。例如，編譯器將典型地把在一子程序範圍之內的所有臨時變量放置在連續的存儲單元中。假定這些臨時變量每個都在一個基地址的偏移量範圍內，編譯器將相應地標識一個特定基址寄存器用於引用這些臨時變量中的每一個。每當引用一個臨時變量時，同一個基址寄存器將出現在指令160中。同樣地，傳遞給一個子程序的自變量、或指向這些自變量的指針通常想會被暫時地保存在連續或近似連續的存儲單元中，並且將相應地被一個共用的基址寄存器引用。使用一個共用的基址寄存器引用在存儲器中空間上相關的數據項的其它例子包含引用在一個數組中的項、在一個文本字符串中的字符等。查看另一條路線，包含同一個基址寄存器的間接尋址指令很可能引用空間上彼此相關的項，因此基於包含同一個基址寄存器的間接尋址指令的發生預測數據關係很可能是成功的，即提供了一個高的高速緩存命中率。
儘管這個發明尤其非常適於在一個n路相關聯高速緩存中使用，但是它也可以被應用到通常使用一個地址欄位預測可能包含一個被引用數據項的高速緩存區域的其它高速緩存方案中。由於在使用一個基址寄存器和在數據項當中存在空間關係之間隱含相關性，通過增加或代替傳統的、用於利用一個被引用的基址寄存器標識進行預測的地址欄位，能夠預期一個較高的高速緩存命中率。儘管對本領域普通技術人員來說顯然本發明可以應用到使用分區高速緩存的其它高速緩存方案中，但是為便於參考，在此是使用一個n路相關聯高速緩存的範例提出了本發明。
圖2說明了依據這個發明的具有路線預測的一個n路相關聯高速緩存200的框圖實例。如圖2所示，提供了一個路線預測表，它使用提供給處理器的一條間接尋址指令160的內容作為一個用於預測高速緩存120中對應於一個被引用數據項的一條路線的基礎。在所示的例子中，基址寄存器162提供了一個到路線預測表250的索引用於產生被預測的路線。由於包含同一個基址寄存器162的指令很可能引用在基址寄存器170內容的偏移量164範圍之內的相關數據項，所以，如果數據項實際上在高速緩存120中，則被預測的路線很可能是包含被引用數據項的路線。
被預測路線包含被引用數據項的可能性取決於包含在每一高速緩存線路中的數據項數目；在線路中的項越多，被引用數據項在該線路範圍之內的可能性較高。同樣地，被預測路線包含被引用數據項的可能性通過使用高速緩存分配方案而增加了，其中高速緩存分配方案可能把相關的高速緩存線存儲到同一條路線中。也就是說，例如，上述的、用於確定使用哪條路線加載一條新高速緩存線的LRU優先化方案能夠被修改，以有利於把新的高速緩存線加載到和具有同一基址寄存器162的先前加載高速緩存線相同的路線中。如這個公開中講授的、這些及其它用於提高一種基於間接地址的預測方案效率的方案對本領域普通技術人員來說是顯然的。
除了提供一種不需要存儲器地址計算、並且潛在地提高了預測成功率的預測方案之外，能夠預期這個發明中的路線預測表250與傳統的路線預測表150相比損耗相當少的資源。如上所述，寄存器170的數目通常局限於64，而且一般為32。依據這個發明，用於一個路線預測表250的總存儲需要量等於寄存器170的數目乘以唯一地標識高速緩存120中的每條路線所要求的位數。通常，寄存器170的數目實質上比在地址110變址欄位112中提供的索引數目少，因此實現了路線預測表大小的減少。
在一個最佳實施例中，指令160被處理以在該指令被實際執行之前開始數據存取，儘管數據存取可以在該指令被執行時開始。基址寄存器162的內容被用來索引在路線預測表250中的一條被預測路線。這條被預測的路線被用來啟用在高速緩存120中的該被預測路線p，以便經由比較器130p檢查被尋址數據項是否包含在被預測路線中。在這個檢查的同時，如果被預測的路線p包含已經尋址的數據項，則數據行125p被加載到緩存140p中，以便是立即可用的。如果已經預測的路線包含被尋址的數據項，則字欄位113從在緩存140p中的數據行中選擇被尋址的數據項，並且在執行指令160時把它提供給處理器。如果被預測的方法p不包含被尋址的數據項，則檢查其它路線，如結合圖1詳細描述得那樣。
上述僅僅舉例說明了本發明的原則。因此將要理解，本領域技術人員能夠設計出各種儘管在此未明確描述或顯示、但體現了本發明原理，因此在它的精神和範圍之內的方案。例如能夠使用基址寄存器162和偏移量164子集的組合以在預測中提供一個額外的精確水平。也就是說，例如，如果偏移量是一個有符號的整數，則基址寄存器162和偏移量164的最高有效位的組合為引用包含在寄存器170中在基地址以下項的路線預測、以及引用在基地址以上項的路線預測作好了準備。使用偏移量164的附加位進一步改善了預測；極端地，路線預測表可以被配置為為偏移量164的每一數據行大小的段提供預測。儘管這個配置可能需要與傳統基於地址的標記預測一樣多的存儲器位數，或者更多，但是可以預計使用基址寄存器以組織路線預測表與傳統基於地址的路線預測方案相比，提供了一個實質上較高的高速緩存命中率。鑑於這個公開，這些及其它系統配置和最優化特徵對本領域普通技術人員來說將會是顯然的，而且被包含在下列權利要求的範圍內。
權利要求
1.一個高速緩存系統(200)，包含一個高速緩衝存儲器(120)，包含多個區域(Way-a、b、......n)，這多個區域中的每個區域包含多個存儲數據行(125)其特徵在於高速緩存系統(200)被配置為在這多個區域中的一個被預測區域(p)中確定一個被尋址的數據項是否位於這多個存儲數據行(125)中的一個相應數據行中；以及被預測的區域(p)基於提供該被尋址數據項地址(110)的一條間接尋址指令(160)的子集(162，164)。
2.如權利要求1所述的高速緩存系統(200)，其特徵在於高速緩衝存儲器(120)相當於一個n路相關聯高速緩存，該n路相關聯高速緩存中的每條路線都形成這多個區域中的一個區域，被預測區域(p)是一條被預測的路線，每條路線進一步包含對應於這多個存儲數據行(125)的多個存儲標記(121)，這多個存儲數據行(125)和多個存儲標記(121)中的每一個都可經由被尋址數據項的地址(110)中的變址欄位(112)被唯一地可尋址，其中n路相關聯高速緩存被配置為通過在被預測路線中把地址(110)的標記欄位(111)與對應於該地址(110)的變址欄位(112)的多個存儲標記(121)的一個存儲標記進行比較，確定被尋址數據項是否位於被預測的路線中。
3.如權利要求2所述的高速緩存系統(200)，其特徵在於n路相關聯高速緩存被進一步配置為如果被尋址數據項沒有位於被預測路線中的相應數據行(125)中，則把地址(110)的標記欄位(111)與在該多個區域其它路線中的存儲標記(121)進行比較，以便確定被尋址的數據項是否位於在其它路線中的一個相應數據行(125)中。
4.如權利要求3所述的高速緩存系統(200)，其特徵在於n路相關聯高速緩存被進一步配置為如果被尋址的數據項沒有位於在被預測或其它路線中的相應數據行(125)中，則從一個存儲器中加載被尋址的數據項，並且加載到該多個區域中的一條選擇路線中。
5.如權利要求1所述的高速緩存系統(200)，其特徵在於間接尋址指令(160)的子集(162，164)包含一個基址寄存器(162)標識，該基址寄存器包含一個基地址，並且被尋址數據項的地址(110)基於這個基地址。
6.如權利要求5所述的高速緩存系統(200)，其特徵在於在間接尋址指令(160)中子集(162，164)進一步包含一個偏移量欄位(164)的一部分，並且被尋址數據項的地址(110)進一步基於該偏移量欄位(164)。
7.如權利要求1所述的高速緩存系統(200)，其特徵在於被預測的區域(p)基於一個最近最少使用的確定。
8.一種處理器，包含一個指令寄存器(160)，被配置為接收包含至少一條間接尋址指令的程序指令，其中該間接尋址指令提供了對在一存儲器中的一個被引用數據項的間接引用(162，164)，以及一個預測設備(250)，被配置為基於包含在指令寄存器(160)中的位子集(162，164)，標識在一個高速緩存(200)的多個區域(Way-a、b、......n)中的一個被預測區域。
9.如權利要求8所述的處理器，其特徵在於包含在指令寄存器(160)中的該位子集(162，164)包含了一個基址寄存器標識，其中該基址寄存器包含一個用來確定在存儲器中的被引用數據項的地址(110)的基地址。
10.如權利要求9所述的處理器，其特徵在於包含在指令寄存器(160)中的該位子集(162，164)進一步包含一個偏移量欄位的至少一部分，其中該偏移量欄位也被用來確定在存儲器中的被引用數據項的地址(110)。
11.如權利要求8所述的處理器，其特徵在於在高速緩存(200)中的多個區域對應於在一個n路相關聯高速緩存中的多條路線，以及被預測的區域(p)對應於這多條路線中的一條被預測的路線。
12.一種用於預測一個很可能包含一個被引用數據項的高速緩存(200)的一個區域的方法，包含從一條間接尋址該被引用數據項的間接尋址指令(160)中提取多位(162，164)，以及基於來自於間接尋址指令(160)的這多位(162，164)，確定(250)該高速緩存(200)的區域。
13.如權利要求12所述的方法，其特徵在於這多位(162，164)包含一個用來確定被引用數據項地址(110)的基址寄存器(162)的標識符。
14.如權利要求13所述的方法，其特徵在於這多位(164，164)進一步包含一個進一步用來確定被引用數據項地址(110)的偏移量欄位(164)的至少一部分。
全文摘要
一種用於一個分區高速緩存的路線預測方案，其基於使用間接尋址訪問在存儲器中的數據項的指令的內容。間接地址指令的內容可以直接用於使用而不需要存儲器地址計算，而且基於這種可直接使用信息的預測方案尤其非常適於流水線結構。間接尋址指令還提供了存儲器訪問的一個高級抽象，而且與數據項的絕對地址相比，很可能更能指示出在數據項當中的關係。在一個最佳實施例中，包含在間接地址指令中的基址寄存器提供了一個到用於一個n路相關聯高速緩存的一個路線預測表的索引。使用同一個基址寄存器間接尋址的數據項很可能是相關的，而且因此基於一個間接地址指令的基址寄存器在一個n路關聯存儲器中預測一條特定路線很可能導致一個高速緩存命中，由此減小了與訪問在該高速緩存中的所有路線有關的能量損耗。
文檔編號G06F12/08GK1459058SQ02800633
公開日2003年11月26日 申請日期2002年2月28日 優先權日2001年3月13日
發明者J·W·范德維爾德特, P·斯特拉維爾斯 申請人:皇家菲利浦電子有限公司