帶有根據頁面大小指示符而進行散列的局部標記的翻譯後援緩衝器的製作方法

2023-05-29 17:02:01

專利名稱：帶有根據頁面大小指示符而進行散列的局部標記的翻譯後援緩衝器的製作方法
技術領域：
本發明涉及翻譯後援緩衝器的領域，更具體而言，涉及用於快速設計周期的翻譯後援緩衝器體系結構。
現代的微處理器系統典型地運用虛擬尋址。虛擬尋址使系統能有效地創建比實際的物理存儲空間更大的虛擬存儲空間。把實際的物理存儲空間分解成虛擬存儲空間這一過程稱為分頁(paging)。分頁將物理存儲空間的線性地址空間分解為稱作頁面的固定塊。頁面允許利用較小的物理的主存儲器加上低廉的後臺存儲器來實施大容量的線性地址空間。這種配置稱為″虛擬存儲″。分頁允許通過與後臺存儲器來回進行交換的按頁面管理存儲器來實施虛擬存儲。分頁帶來了另外的優點，包括減少了主存儲器碎片、對不同頁面有可選擇的存儲器寫入策略，和為不同的頁面所用的可變化的存儲器保護方案。典型情況下，分頁機制的出現對應用程式而言是透明的。
頁面的大小是靈活性和性能之間的折衷。小的頁面大小允許在虛存系統上進行更精確控制，不過會因分頁操作而增加了開銷。因此，許多CPU都支持頁面大小的混合，例如，一個特定的MIPS實施方案支持4kB、16kB、64kB、256kB、1MB、4MB和16MB頁面的任意混合。
處理器繼而能夠有利地使用虛擬地址在虛擬地址空間中操作。然而，常常必須將這些虛擬地址翻譯成物理地址——實際的存儲位置。實現將虛擬地址翻譯成物理地址的一種方式就是使用在主存儲器中經常訪問的和存儲的翻譯表。翻譯表是存儲在主存儲器中的，因為它們在大小方面通常很大。令人遺憾的是，對存儲在主存儲器中的翻譯表的經常訪問勢必會減慢總體的系統性能。
為了避免需要經常訪問主存儲器中的翻譯表以實現地址翻譯，現代的微處理器系統往往利用翻譯後援緩衝器(TLB)來存儲或高速緩存最近生成的虛擬地址到物理地址的譯本。TLB是一種特殊類型的高速緩衝存儲器。正如其它類型的高速緩衝存儲器的情況一樣，TLB典型地是由專門設計成可被快速訪問的相對少量的存儲器組成的。TLB典型地包括標記陣列和數據陣列兩者，正如在高速緩衝存儲器中提供的那樣。在標記陣列內部，每個標記行都存儲一個虛擬地址。然後，使這個標記行與數據陣列中對應的數據行相關聯，在所述數據陣列中存儲有對應虛擬地址的物理地址譯本。因此，在從主存儲器中的翻譯表中尋找虛擬地址的譯本之前，處理器首先查詢TLB以確定虛擬地址的物理地址譯本目前是否存儲在該TLB中。如果虛擬地址和對應的物理地址都存儲了在TLB中，那麼所述TLB就在其輸出埠處提供對應的物理地址，並且避免了消耗時間與資源的對主存儲器的訪問。因此為了簡化TLB的操作並且減少變址需求，在TLB內通常提供一個內容可尋址存儲器(CAM)。CAM是並行的模式匹配電路。在一個匹配操作模式中，所述CAM允許並行地搜索所有它的數據以查找匹配。
令人遺憾的是，常規的TLB需要定製的電路設計技術以實現CAM。利用定製的電路設計不是有利的，因為每個TLB及相關的CAM都需要大量的設計工作以便在處理器系統設計中實現相同的目的。當然，當處理器缺少CAM電路時，來自於處理器的信號將離開晶片而向CAM傳送，從而導致時延。
因此，本發明的一個目的是，提供一種由傳統可合成電路塊構成的CAM體系結構。
依照本發明，提供一種翻譯後援緩衝器(TLB)，它包括至少一個輸入埠，用於接收虛擬地址的一部分；隨機存取存儲器；一組寄存器；和可合成邏輯，用於根據所接收到的部分虛擬地址確定散列值以及用於將該散列值與寄存器組內已存儲的一個散列值進行比較以確定這樣的可能性，即在隨機存取存儲器內的某一行內存儲著與虛擬地址相關聯的物理地址並且與來自寄存器組中的一個寄存器相關聯，在所述寄存器內部存儲有所述散列值。
依照本發明的一個方面，提供了一種翻譯後援緩衝器，包括隨機存取存儲器；與存儲器中一行相關聯的第一寄存器；和散列電路，用於接收與一個其譯本目前被存儲在該存儲器中的虛擬地址不同的虛擬地址，用於確定散列值和用於在第一寄存器中存儲散列值；並且該散列電路用於在存儲器的所述行中存儲虛擬地址及其譯本。
依照本發明的又一個方面，提供了一種翻譯後援緩衝器，包括RAM；和可合成邏輯，用於根據虛擬地址來確定RAM內部的至少一個可能的地址，以固定的關係對所述RAM進行搜索以查找與虛擬地址相關聯的物理地址，該至少一個可能的地址是RAM內的一個僅有的已知地址以外的地址，它以固定的關係在所述RAM中存儲與虛擬地址相關聯的物理地址。
依照本發明的又一個方面，提供了一種為包含RAM和可合成邏輯的翻譯後援緩衝器實現虛擬地址查找功能的方法，包括以下步驟向可合成邏輯提供虛擬地址；將所提供的虛擬地址散列以提供散列結果；根據散列結果確定在RAM內部的存儲位置，相對於該位置來存儲虛擬地址標識符和與之相關的物理地址；將虛擬地址與虛擬地址標識符進行比較以確定物理地址是否對應於所提供的虛擬地址；並且當物理地址與所提供的虛擬地址相對應時，提供物理地址以作為輸出值。
現在將參照附圖來描述本發明，在附圖中

圖1說明了現有技術中的SRAM電路的半導體管實施方案；圖1b說明了現有技術中的CAM電路的半導體管實施方案；圖2說明了現有技術中的從虛擬地址(VA)到物理地址(PA)的翻譯過程；圖3說明了結合直接映射的高速緩衝存儲器所實現的現有技術從VA到PA的翻譯過程；圖4a總體上說明了利用可合成邏輯元件和隨機存取存儲器形成的翻譯後援緩衝器；圖4b更詳細地說明了由可合成邏輯元件形成的翻譯後援緩衝器；圖4c概述了TLB的操作所採取的步驟；圖5更詳細地說明了散列電路；和圖6說明了圖5中所示的散列電路的變形。
CAM電路包括結構上類似於SRAM電路的存儲電路。然而，CAM電路還包括搜索電路，它提供了並行檢索操作模式的增添的益處，因此能夠實現利用硬體並行地搜索CAM的內容。當為特定的數據值而搜索CAM時，所述CAM在CAM內找到那個數據值的匹配時提供匹配信號。CAM與SRAM之間的主要區別就在於在CAM中，將數據提交給表示虛擬地址的CAM並且返回與所述數據有關的地址，而在SRAM中，向SRAM提供地址並且返回在那個地址上所存儲的數據。
CAM的信元是這樣排列的，使得每排信元都保存一個存儲地址，並且那排信元通過匹配行而連接到數據陣列的對應字行上以便當在那個匹配行上發生匹配時能夠實現那個字行中的數據陣列的存取。在完全關聯的高速緩衝存儲器中，CAM的每一排都保存對應的主存儲位置的全地址，並且輸入到CAM需要輸入所述全地址。
Steven A Guccione等人的名為″A Reconfigurable ContentAddressable Memory(可重新配置的內容可尋址的存儲器)″的現有技術出版物中，論述了FPGA內部實施CAM的方式。正如在現有技術的圖1中看到的那樣，在半導體管級別上，CAM電路101的實施方式非常類似於標準SRAM 100的實施方式。CAM和SRAM電路兩者差不多是相同的，除增加了三個匹配半導體管103外，每一個都具有6個半導體管102，所述這三個匹配半導體管提供了CAM 101的並行檢索能力。令人遺憾的是，使用標準的可編程邏輯裝置並不方便於實現這類半導體管層電路。
在該現有技術的出版物中，論述了以FPGA實現的CAM。利用門級別的邏輯來實現CAM往往會導致不合理的CAM大小。在CAM內部觸發器被用作為數據存儲元件，其結果是利用FPGA實現的可達到的CAM電路的大小要取決於FPGA內可用的觸發器的數量。以FPGA實現CAM會迅速地耗盡許多FPGA資源，因而不是一個可行的解決方案。令人遺憾的是，這已經導致早先的設計者推斷只能在半導體管級別上高效地實現所述CAM。
該現有技術的出版物還提出在FPGA中使用查找表(LUT)來實現CAM。不是在FPGA內使用觸發器來存儲需要匹配的數據，這種實施方式提出了使用LUT來存儲需要匹配的數據。通過使用LUT而不是使用觸發器，可以得到更小的CAM結構。
令人遺憾的是，利用可合成元件來形成CAM不容易被實現，所以提供CAM的現有技術的處理器在其內具備CAM核心。在處理器內提供CAM核心不適當地使製造出的電路很昂貴，因為增加了設計複雜性。這類額外的設計複雜性不適合於小批量定製設計的處理器。
圖2說明了從虛擬地址(VA)201到物理地址(PA)202的翻譯過程。所述VA 201是32位地址，VA[31:0]，而所述PA 202也是32位地址PA[31:0]。所述VA具有兩個部分虛擬頁面號(VPN)203和頁面偏移量(PO)204。所述VPN 203通常位於VA 201的較高部分，而所述PA 202通常位於較低部分，不過這不是必須的。典型地講，對於32位的尋址方案而言，所述VPN是20位，而所述PA是12位。所述PA或較低的12位直接翻譯成PA。所述VPN 203用於對TLB 205變址以便從中檢索物理頁面號(PPN)206。換句話說，所述VPN 203經歷到PPN 206的翻譯。將PA 202的較高部分中的PPN 206和PO組合成PA的較低部分提供了從VA到PA的譯本。
圖3說明了結合直接映射的高速緩衝存儲器301所實現的從VA 201到PA 202的翻譯過程。在翻譯周期的開始，利用VA來訪問高速緩衝存儲器301和TLB 205兩者。利用VA的頁面偏移量部分來訪問高速緩衝存儲器301-該頁面偏移量是翻譯過程中未被修改的地址的部分。使用頁面偏移量來對高速緩衝存儲器301中所找到的標記陣列302和數據陣列303進行變址，其中使用所述頁面偏移量來對高速緩衝存儲器301內部的超高速緩衝存儲器行302a進行變址。對TLB的訪問是利用VA 201的VPN部分203執行的。所述TLB 205典型地包括TLB標記陣列304和TLB數據陣列305。TLB標記陣列304和TLB數據陣列305兩者都包含來自於VPN 203的那些位，以便當向這些陣列中的每一個提供VPN時，構成VPN的那些位與那些存儲在陣列304、305內部的位進行比較以定位TLB 205內的項。
一旦訪問TLB數據陣列305並且在VPN和TLB數據陣列305a內的項之間發現匹配，就檢索PPN 206並將所述PPN 206提供給高速緩衝存儲器301並且使用所述PPN 206與從標記陣列302中檢索出的標記302a進行比較。匹配表示高速緩存″命中″306。如果在VPN 203與TLB標記陣列304a內的項之間發現匹配，那麼就生成TLB命中信號307。照此，訪問高速緩存僅僅利用了PPN 206的各個位。上述示例說明了直接映射式高速緩衝存儲器的使用；然而，同樣的VA到PA的翻譯本也適用於按組相關的高速緩存。當使用按組相關的高速緩存時，本領域技術人員認識到的是，高速緩存路線的大小小於或等於虛擬頁的大小。
令人遺憾的是，當在SRAM中實現TLB時，要求對存儲器作窮舉搜索以支持CAM功能。因此，當TLB具有1024個虛擬地址及其對應的物理地址的存儲器時，每一次地址翻譯都需要多達1024次的存儲器存取和比較操作。這類CAM實施方式是不切實際的，因為性能隨CAM的大小而線性下降。
圖4a總體上說明了利用可合成邏輯元件499和隨機存取存儲器(RAM)410所形成的TLB 400。經由VPN_IN輸入埠450提供用於翻譯的VPN，其中位VPN_IN[31:12]是從VA[31:0]提供到這個輸入埠450的。經由CP0_PAGE_MASK輸入埠451提供頁面屏蔽信號。經由CP0_TRANSLATION輸入埠452提供CP0_TRANSLATION輸入信號。取決於使用TLB 400從VA到PA的譯本，經由TLB_TRANSLATION輸出埠453提供TLB_TRANSLATION輸出信號。
圖4b更詳細地說明了由可合成邏輯元件形成的TLB 400，並且在圖4c中，概括示出了TLB 400的操作步驟。在TLB操作的更詳細說明中，經由VPN_IN輸入埠450提供用於翻譯的VPN(480)，其中位VPN_IN[31:12]是作為VPN從VA[31:0]到這個輸入埠450提供的。經由CP0_PAGE_MASK輸入埠451提供頁面屏蔽。向頁面屏蔽編碼器408提供這個頁面屏蔽，用於根據表1來對頁面屏蔽進行編碼。
表1頁面屏蔽編碼所述頁面屏蔽編碼器408用於接收其輸入埠上的CP0_PAGE_MASK輸入信號，並且用於使這個輸入信號與3位向量MASK[2:0]進行相關。進一步向散列電路406提供所述3位向量MASK[2:0]。所述散列電路406經由第一輸入埠406a來接收VPN_IN[31:12]，並且經由第二輸入埠406b來接收MASK[2:0]。散列向量H_VPN[5:0]是通過散列電路406的散列操作481而從其輸出埠406c那裡提供的。進一步向48個寄存器409中的每一個寄存器提供散列向量H_VPN[5:0]和MASK[2:0]，其中每個寄存器包括多個觸發器，共同稱為491。每個寄存器409都具有兩個輸出埠。向比較電路403提供來自於其第一輸出埠的第一輸出信號。向48個散列電路406的其中一個的第二輸入埠406b提供來自於第二輸出埠的第二輸出信號。這個散列電路上的第一輸入埠接收VPN_IN[31:12]。所述散列電路406輸出埠耦合到用於對寄存器輸出和散列電路輸出信號之間進行比較的48個比較電路403的其中一個。取決於兩個輸入信號的比較，如果所述信號是相同的則每個比較器都提供『1』，如果它們是不同的則提供『0』。來自48個比較器的每一個的輸出信號hiti提供給48個單位的二輸入多路復用器411中的一個。來自於每個多路復用器的輸出埠耦合到觸發器404。每個觸發器404都生成在標記為tryi的輸出埠提供的輸出信號，其中對於0＜i＜47的情況下，這些輸出信號try
一起被提供給優先級編碼器電路401。所述優先級編碼器電路進一步耦合到二進位解碼器電路402，其中所述優先級編碼器電路向二進位解碼器電路402和RAM 410確立TLB_ENTRY[5:0]信號。在TLB 400內提供三個輸出埠，ENTRY_FOUND輸出埠454、ENTRY_NOT_FOUND輸出埠455和TLB_TRANSLATION輸出埠453，以分別提供ENTRY_FOUND、ENTRY_NOT_FOUND和TLB_TRANSLATION輸出信號。
將對於從VA到PA的譯本的地址存儲在隨機存取存儲器(RAM)410中，其中所述RAM 410最好按行的形式具有48項。在使用中，每當執行新的翻譯時，分別通過輸入埠450、451和452向TLB電路400提供輸入信號VPN_IN、CP0_PAGE_MASK和CP0_TRANSLATION。對於給定的索引i由TLB所執行的譯本存儲在RAM 410中。所述給定的索引對保存PPN的譯本的RAM內的其中一行410a進行索引。所述散列電路406計算散列函數H(VPN_IN，MASK)並且在相應的6位寄存器hi中存儲結果(490)。在3位寄存器mi中存儲頁面屏蔽(491)。
當利用TLB請求翻譯時，經由輸入埠提供VPN並且為所有的i計算散列函數H(VPN_IN，mi)並與hi相比(450)。這產生48位的向量hit0…hit47(492)，所述48個位向量隨後被加載到48位的寄存器try0…try47中(493)。為了確定所請求的VPN_IN是否存在於RAM中所存儲的翻譯表當中(482)，只檢查RAM中那些tryi已經確立的項或行。如果它產生『1′(483)，則確立48位的tryi向量中的一項。當然，可能在tryi向量中有不止一位被確立，但是優先級編碼器401選擇具有最低索引值的項以便對RAM內的項尋址。所述解碼器402將這個索引轉換成48位的一次命中的向量clr0…clr47(494)。當時鐘脈衝從時鐘電路(未示出)來臨時，除與剛才用來尋到RAM的索引相對應的已清除的位之外，所述tryi向量被重新加載。每次一項地重複這個過程(483)。一旦如ENTRY_FOUND輸出埠454上的ENTRY_FOUND信號所指示的那樣查找到了所請求的項時，或當tryi中的所有位都為0時，所述過程就立即停止(484)。當tryi中的所有位都是『0』時，那麼就經由ENTRY_NOT_FOUND輸出埠455來提供ENTRY_NOT_FOUND信號。在第一種情況下，翻譯是成功的並且利用TLB_TRANSLATION輸出埠453上的TLB_TRANSLATION信號從RAM 410那裡提供用於翻譯的信息(485)。在第二種情況下，翻譯不成功，並且TLB報告TLB再填充異常。
圖5更詳細地說明了散列電路506。利用MASK[2:0]和VPN[31:12]向散列電路506輸入信號，7對1多路復用器501依據提供給第二輸入埠506b的MASK[2:0]信號從散列電路506那裡提供H_VPN[5:0]輸出信號。這個散列電路從VPN中選擇6個最低位。所述選擇受頁面屏蔽的控制，因為″最低的″的定義隨頁面大小而變化。例如，對於4kB的頁面大小來說，VPN的6個最低位(LSB)是位22:17，而對於16kB的頁面大小來說，6個LSB是位19:14。由於TLB 400的每個TLB項都存儲兩個相鄰的虛擬頁，稱作奇/偶對，因而對於4kB頁面的6個LSB來說，奇/偶對是位18:13。因此，第12位確定是返回偶數(0)還是返回奇數(1)譯本，而對於16kB的奇/偶對來說，所述位是20:15。然而，這個散列函數是冗餘的，因為位H_VPN[5:0]的排序是不相干的。圖6展示出了位的排序是不相干的。
圖6說明了圖5中所示的散列電路的變形。向第一輸入埠606a提供VPN[31:12]信號，而向第二輸入埠606b提供MASK[2:0]信號。所述屏蔽信號MASK[2:0]由位m0、m1和m2組成。在這個散列電路606內部有三個3對1多路復用器601至603。第一多路復用器601在其選擇輸入埠上接收下列位{m2，m2(m1+m2)}，其中向多路復用器數據輸入埠0至2分別提供來自VPN的位VPN[13:14]、VPN[19:20]、VPN[25:26]。由此，多路復用器601給H_VPN[5:0]輸出信號提供第5位和第4位。第二多路復用器602在其選擇輸入埠上接收下列位{m2(m1+m0)，m2m1+m2m2m0)}，其中向標記為0至2的多路復用器數據輸入埠分別提供來自於VPN的位VPN[15:16]、VPN[21:22]、VPN[27:28]。由此，多路復用器602給H_VPN[5:0]輸出信號提供第3位和弟2位。所述第三多路復用器603在其選擇輸入埠上接收下列位:{m2m1，m2m1m0+m2m1)}，其中向標記為0至2的多路復用器數據輸入埠分別提供來自於VPN的位VPN[17:18]、VPN[23:24]、VPN[29:30]。由此，多路復用器603給H_VPN[5:0]輸出信號提供第1位和第0位。
優選地，散列函數H_VPN[5:0]對於MASK[2:0]和對於VPN_IN[31:12]輸入信號而言是均勻分布的。在TLB錯失的情況下，查找RAM內起初為之確立tryi的所有項。循環數Nmiss可以用下式表示Nmiss=j=04848jpj(1-p)48-j(1+j)]]>，其中p是比較器輸出信號hiti被確立的概率。下列項48jpj(1-p)48-j]]>，給出在try向量tryi中正好有j個位最初被確立的概率。當均勻散列函數H在它的輸出信號上具有n個位的情況下，p＝2-n，其中在圖4b的情況下，n＝6。
在TLB命中的情況下，需要對RAM 410進行至少一次訪問，這與不訪問RAM的情況下進行檢測的TLB錯失的狀況相反，因為在TLB錯失狀況中，try向量tryi包含的全部是0。
為命中翻譯在TLB中需要執行的平均循環數是由下列公式給出的
Nhit=k=04747kpk(1-p)47-k(1+k2)]]>對於TLB命中而言，在try向量tryi中一定存在至少一個『1』。唯一的不定性就是向量內帶有其餘元素造成的。變量k用來表示對於k處於0…47的範圍內、try向量tryi內被設置為『1』的其餘項的數量。如果k＝0，那麼在RAM內僅僅查出一項。因此，由於對於i＝0時要使用一個時鐘周期來查找第一位置中的譯本，因此就要利用總共兩個時鐘周期來執行所述翻譯。平均起來，需要花費2+k/2循環以從RAM410中返回所請求的譯本。
就執行翻譯和中斷等待而言，要檢查長的查找序列所需的時鐘周期數，例如k高達25或25以上。下列關係式P{N25}=254848jpj(1-p)48-j]]>，給出了TLB將使用25個或25個以上的循環來完成翻譯的概率。表2列出了在散列函數寬度(n)的範圍內為了找到翻譯Nhit，檢測錯失Nmiss需要花費的平均循環數和TLB操作佔用25個周期數或更多周期數的概率。
表2作為散列位『n』的數量的函數的TLB等待時間從表2來看，很明顯P{N25}是如此之小，以致即使具有4位散列函數，它也需要超過6000年的連續操作才能碰上TLB翻譯需要25到48個之間的時鐘周期的情況。
Nhitq(″命中快速″)列適用於連續地向TLB電路400施加VPN_IN的情況。從這個表來看，很明顯當重點在於最重要的數即Nhit時，n＝5或n＝6就足夠了。超過6位不會得到更大收穫，因為當n＝＞20時Nhit趨近2.0。在TLB電路400中使用n＝6的數值，因為散列函數可能不是很均勻。因此，TLB內使用的6位散列函數接近於5位真正均勻的散列函數的性能。
有利的是，當向TLB提供VA時，它被傳送到對每一行的合成邏輯中，並且提供這樣的結果，它由tryi向量內各個位中至少一個確立的位來表明。然後，為了提供PPN只要在物理上訪問那些其結果表現出匹配已發生的那些行。因此，對於翻譯過程只要訪問TLB行的一小部分，由此導致實質的性能改善。
在不背離本發明的精神或範圍的情況下，可以設想出許多其它的實施例。
權利要求
1.一種翻譯後援緩衝器(TLB)，包括至少一個輸入埠(450)，用於接收虛擬地址的一部分；隨機存取存儲器(410)；一組寄存器(491)；和可合成邏輯(499)，用於根據所接收到的部分虛擬地址確定散列值以及用於將該散列值與寄存器組(491)內的已存儲的一個散列值進行比較以確定這樣的可能性，即在隨機存取存儲器(410)內的某一行(410a)內存儲著與虛擬地址相關聯的物理地址並且與來自寄存器組(491)中的一個寄存器(409)相關聯，在所述寄存器內部存儲有所述散列值。
2.根據權利要求1所述的翻譯後援緩衝器，其中所述可合成邏輯(499)包括編碼器電路(408)，用於接收至少一個可表示頁面大小的頁面大小信號，並且用於根據該至少一個頁面大小信號來確定供確定散列值之用的至少一個屏蔽位。
3.根據權利要求2所述的翻譯後援緩衝器，其中所述可合成邏輯包括第一散列電路(406)，它包括輸出埠(406c)並且用於接收所接收到的部分虛擬地址和至少一個屏蔽位，該第一散列電路(406)用於根據所接收到的部分虛擬地址和該至少一個屏蔽位來確定性地生成第一散列值，並且用於向它的輸出埠(406c)提供該第一散列值。
4.根據權利要求3所述的翻譯後援緩衝器，其中所述可合成邏輯包括至少一個寄存器(409)，用於存儲至少一個屏蔽位。
5.根據權利要求4所述的翻譯後援緩衝器，其中所述可合成邏輯包括第二散列電路(406)，用於從至少一個寄存器(409)中接收該部分虛擬地址和至少一個已存儲的屏蔽位，所述第二散列電路(406)用於確定該散列值。
6.根據權利要求5所述的翻譯後援緩衝器，包括比較器(403)，並且其中所述隨機存取存儲器(410)包括一個存儲在其中的翻譯表，其中在所述翻譯表內存儲所述行(410a)並且其中在比較器(403)內比較所述散列值以確定虛擬地址是否存在於翻譯表內的相關的行中；一個肯定的指示，表明對於相關行內的虛擬地址可能有匹配；和一個否定的指示，表明相關行內的虛擬地址沒有可能匹配。
7.根據權利要求5所述的翻譯後援緩衝器，包括第三散列電路(406)，所述第三散列電路用於從至少一個寄存器(409)中接收該部分虛擬地址和至少一個已存儲的屏蔽位，所述第三散列電路(406)用於與第二散列電路(406)平行地確定一個散列向量，該散列向量中已存儲著對於隨機存取存儲器(410)中至少兩行的確定性地生成的散列值。
8.根據權利要求7所述的翻譯後援緩衝器，其中所述第一散列電路(406)預先將該虛擬地址和至少一個檢索出的屏蔽位散列，以便提供用於供給第二和第三散列電路的預先散列值。
9.根據權利要求8所述的翻譯後援緩衝器，包括至少一個第二寄存器(404)，所述至少一個第二寄存器(404)用於存儲散列值和在存儲器內的一個相關行(410a)之間的比較結果，所述比較結果提供表明相關行內的虛擬地址可能匹配的一個肯定指示和表明沒有可能匹配的一個否定指示。
10.根據權利要求9所述的翻譯後援緩衝器，其中該至少一個第二寄存器(404)中的多個包括一些寄存器(493)，其數量等於或多於翻譯後援緩衝器的存儲器(410)中的行數量。
11.根據權利要求1所述的翻譯後援緩衝器，其中所述可合成邏輯包括多個比較器(403)，用於將多個散列值與多個期望的散列值進行比較以確定在存儲器中的每個相關的行內存儲著用於虛擬地址的譯本的可能性，其中每一個所述期望的散列值都與存儲器(410a)中的一行相關聯，所述比較器在組合時用於提供一個包含著與存儲器(410)中的每一行相關聯的值的向量。
12.根據權利要求11所述的翻譯後援緩衝器，其中所述可合成邏輯包括一個分解電路，用於在表明含有譯本的存儲器中一行的可能譯本的多個值之間進行分解。
13.根據權利要求1所述的翻譯後援緩衝器，包括散列電路(406)，用於對除其譯本目前已被存儲的虛擬地址之外的虛擬地址進行散列以確定一個散列值，並且用於將該散列值存儲在與存儲器中的可用的行(410a)相關聯的寄存器(404)中，所述散列電路用於在存儲器(410)中的可用的行中存儲虛擬地址和對應於它的譯本。
14.一種翻譯後援緩衝器，包括隨機存取存儲器(410)；與存儲器(410)中一行(410a)相關聯的第一寄存器(404)；和散列電路(406)，用於接收與一個其譯本目前被存儲在該隨機存取存儲器(410)中的虛擬地址不同的虛擬地址，用於確定散列值和用於在第一寄存器(404)中存儲該散列值；並且該散列電路用於在存儲器的所述行中存儲虛擬地址及其譯本。
15.一種翻譯後援緩衝器，包括RAM；和可合成邏輯(499)，用於根據虛擬地址來確定RAM(410)內的至少一個可能的地址，以固定的關係對所述RAM(410)進行搜索以查找與虛擬地址相關聯的物理地址，該至少一個可能的地址是RAM(410)內的一個僅有的已知地址以外的地址，它以固定的關係在所述RAM(410)中存儲與虛擬地址相關聯的物理地址。
16.根據權利要求15所述的翻譯後援緩衝器，其中所述可合成邏輯包括一個散列電路(406)，用於將虛擬地址散列以確定一個表明RAM(410)中的一行(410a)的值，在所述行(410a)處開始搜索該虛擬地址的譯本。
17.根據權利要求16所述的翻譯後援緩衝器，其中所述可合成邏輯包括查找分解電路，用於反覆地將RAM(410)中的多個行內所存儲的虛擬地址數據與虛擬地址進行比較以確定用於虛擬地址的譯本的存在，所述查找分解電路用於在它的輸出埠(453)上提供分解後的譯本。
18.根據權利要求17所述的翻譯後援緩衝器，其中所述查找分解電路包括遞增電路(401)，用於在連續比較操作之間按行遞增存儲器內的行的地址。
19.根據權利要求17所述的翻譯後援緩衝器，其中查找分解電路包括一個散列電路，用於在連續比較操作之間按行來改變存儲器內的行的地址。
20.一種為包含RAM和可合成邏輯的翻譯後援緩衝器實現虛擬地址查找功能的方法，包括以下步驟向可合成邏輯提供虛擬地址(490)(499)；將所提供的虛擬地址散列以提供散列結果(481)；根據散列結果確定RAM(410)內部的存儲位置，相對於該位置來存儲虛擬地址標識符和與之相關的物理地址(482)；將虛擬地址與虛擬地址標識符進行比較以確定物理地址是否對應於所提供的虛擬地址(483)；並且當物理地址與所提供的虛擬地址相對應時(484)，提供物理地址以作為輸出值(485)。
21.根據權利要求20所述的方法，其中確定存儲位置的步驟包括以下步驟相對於與RAM(410)中的一個行(410a)相關聯的已知的散列結果來比較該散列結果以確定一個比較結果；形成一個包含著多個值的命中向量(492)，與RAM(410)中的該行(410a)相關聯的每一個值與該已知的散列結果相關聯，並且同與該值相關聯的RAM中的該行包含一個該虛擬地址的譯本的或然率有關。
22.根據權利要求21所述的方法，其中該確定的步驟是對RAM(410)內的每一行執行的。
23.根據權利要求22所述的方法，其中該比較的步驟是順序地對RAM(410)中不同的行而實施的，這些行與一個表明該虛擬地址的可能譯本的值相關聯，直到確定了包含譯本的行的位置為止。
24.根據權利要求20所述的方法，其中確定的步驟是對RAM(410)內的每一行執行的。
25.根據權利要求24所述的方法，其中存儲器中的一個行包括從單個虛擬地址到單個對應的物理地址的單個地址譯本。
26.根據權利要求20所述的方法，其中該散列的步驟包括如下步驟把虛擬地址和與存儲器中的每一行相關聯的已存的值散列以便獨立地確定與存儲器中的每一行相關聯的散列值。
27.根據權利要求26所述的方法，其中存儲器中的一個行包含從單個虛擬地址到單個對應的物理地址的單個地址譯本。
28.根據權利要求20所述的方法，其中該散列的步驟包括以下步驟將虛擬地址預先散列；將預先散列的虛擬地址獨立地與多個已存儲的值中的每一個相組合以便獨立地確定與RAM(410)中的每一行相關聯的散列值，所述每一個已存儲的值都與存儲器(410)中的一個行相關聯。
29.根據權利要求28所述的方法，其中該比較的步驟是順序地對RAM(410)中不同的行而實施的，這些行與一個表明該虛擬地址可能的譯本的值相關聯，直到確定了包含所述譯本的行(410a)的位置為止。
30.根據權利要求28所述的方法，其中存儲器中的一個行包括從單個虛擬地址到單個對應的物理地址的單個地址譯本。
31.根據權利要求20所述的方法，其中該散列的步驟包括如下步驟把虛擬地址散列以確定表明RAM(410)中可能存儲著虛擬地址的譯本的一個行的值。
32.根據權利要求31所述的方法，其中該比較的步驟包括如下步驟以已知的順序從與該已確定的值相關的RAM中的該行開始，反覆比較RAM中的多個行，直到確定了對應虛擬地址的譯本位置為止。
33.根據權利要求32所述的方法，其中在連續比較之間按行來遞增該已知的順序。
34.根據權利要求32所述的方法，其中通過根據該已確定的值求解一個函數來確定該已知的順序。
全文摘要
公開了一種利用RAM和可合成邏輯電路形成的翻譯後援緩衝器(TLB)。所述TLB在可合成邏輯內部提供用於把若干存儲單元組合成對的邏輯，對這些單元必須進行搜索以找到從收到的虛擬地址到物理地址的譯本。所述邏輯提供了用於把接收到的虛擬地址散列的散列電路，並且利用散列後的虛擬地址來對RAM變址以便對提供所述譯本的RAM內的行進行定位。
文檔編號G06F12/00GK1682200SQ03821569
公開日2005年10月12日 申請日期2003年9月12日 優先權日2002年9月13日
發明者P·斯特拉維斯, J·-W·范德瓦爾德特 申請人:皇家飛利浦電子股份有限公司