使用所存储的经编码关键字的高速内容可寻址存储器查找

摘要

用至少为二的海明距离对高速缓存器中的CAM的搜索关键字及关键字字段进行编码以通过确保每一错配的匹配线被至少两个并联的晶体管放电来提高所述CAM的速度。在所述高速缓存器经物理标记的地方，所述搜索关键字是物理地址。在存储在TLB中之前对所述物理地址的页地址部分进行编码。将页偏移位与所述TLB存取并行编码，且将所述页偏移位与经编码的TLB条目连接。如果页地址寻址大的存储器页大小，那么可产生多个对应的子页地址，每一子页地址寻址一较小的页大小。可将这些子页地址编码并存储在微型TLB中。所述经编码的关键字及关键字字段容许单个位的软错误。

说明书

技术领域

本发明大体来说涉及电子电路领域且更特定来说涉及一种使用经编码的关键字字段及所存储的经编码关键字来高速存取内容可寻址存储器的方法。

背景技术

微处理器在各种各样的应用中执行计算任务，所述应用包括嵌入式应用，例如便携式电子装置。所述装置的不断扩展的特征集及增强的功能性需要计算功能甚至更强大的处理器。因此，需要提高执行速度的处理器改善。

大多数现代处理器通过将最近执行的指令及最近存取的数据存储在一个或一个以上高速缓冲存储器中供指令执行管线的就绪存取来利用大多数程序的空间及时间局部性性质。高速缓存器是包含随机存取存储器(RAM)及对应的内容可寻址存储器(CAM)的高速、(通常)芯片上存储器结构。所述指令或数据驻存于存储在所述RAM中的高速缓冲存储“线”中。为确定特定的资料是否驻存于所述RAM中，将其地址的一部分应用到所述CAM。CAM是特定的存储器结构，其中将所应用的比较输入(本文中是指关键字或搜索关键字)同时与存储在每一CAM条目(本文中是指关键字字段)中的数据相比较，且所述CAM的输出是关键字字段匹配所述关键字(如果存在)的指示。在高速缓存器中，所述关键字及关键字字段是地址的部分(虚拟的或物理的)，且如果匹配发生(即，存取在所述高速缓存器中“命中”)，那么所述匹配的位置给RAM加索引，且存取对应的高速缓冲存储线。

图1描绘CAM结构的一个关键字字段的一部分的功能性方块图，其大体由数字100指示。所述CAM关键字字段j包括跨越第j个关键字字段110的所有位位置的匹配线102。匹配线102由接通将匹配线102连接到电源的通过晶体管104的栅极的预充电(PRECHARGE)信号拉高。在所述第j个CAM条目的每一位处，将通过晶体管106插入匹配线102与接地之间。放电晶体管106的栅极是关键字112位及对应的关键字字段110位的逻辑“异或”运算108。在每一第i个位位置处，如果关键字112位与关键字字段110位匹配，那么“异或”运算栅极108的输出为低且通过晶体管106不将电荷从匹配线102引导到接地。如果关键字112位与关键字字段110位错配，那么“异或”运算栅极108的输出为高，从而接通通过晶体管106并将匹配线102拉低。

以此方式，如果关键字112的任何位与关键字字段110的任何对应的位错配，那么匹配线102被拉低。相反，仅当关键字112的每一位与关键字字段110匹配，才不会建立到接地的路径，且匹配线102保持为高。读出电路114在最糟情况匹配线102放电时间所确定的时间检测第j个匹配线102的电平。如果每一关键字字段110是唯一的，也就是在正常的高速缓冲存储操作的情况下，那么仅一个关键字字段110应与关键字112匹配。在所述情况下，CAM内的仅一个匹配线102将保持为高。为确保情况如此，每一匹配线读出电路114的输出去往冲突检测电路116，其检测多个匹配且如果匹配出现则产生错误。在CAM应用而非高速缓冲存储器中，可能出现多个匹配，且优先权编码器(未显示)可从与所应用的关键字112匹配的两个或更多个关键字字段110中选择。

代表性CAM的关键字字段110可以是20到30个位宽，且所述CAM可包括256个条目。因此，所述CAM可包括5000到超过7000个匹配线放电晶体管106。为将如此大的数量的晶体管106实施于小的芯片面积中要求每一晶体管106较小。由于小的晶体管106具有较低的电流携载容量，因此在数据误比较的情况下其需要较长的持续时间来将匹配线102放电。最糟的情况是关键字112与关键字字段110之间的单个位的误比较，其中仅接通一个晶体管106，且其必须携载用以驱散匹配线102上的所有电荷的电流。如果是两个或更多个位的误比较，那么两个或更多个晶体管106并行工作以更快地将匹配线102放电。因此，所述CAM的操作的整体速度由单个位的误比较的定时决定。

因此，可通过确保每一错配关键字字段110的至少两个位将误比较来获得更快的CAM操作。所属技术领域中已知将关键字字段110(且对应地，关键字112)编码以增加其海明距离，海明距离是任何两个数字值之间误比较的位的数量。举例来说，二的海明距离(还称作单个位校验)确保对于相差一个位的关键字112与关键字字段110来说，两个位将在关键字112的经编码的版本与关键字字段110的经编码的版本之间误比较。特定来说，所述经编码的版本中的两个误比较位是在未经编码的数据中相差的位及所述校验位。因此，通过单个位校验来将关键字112及关键字字段110编码确保至少两个位将在其中关键字112与关键字字段110之间存在至少一个位的差异的每一匹配线102上误比较。此确保至少两个晶体管106将并行将匹配线102拉低，从而导致更快的CAM操作。

当高速缓冲存储线在高速缓冲存储未命中之后的处理中被取代时，可容易地在将关键字字段112写入所述CAM之前将其编码。然而，对于经物理标记的高速缓存器来说，关键字110的部分(页地址)被从执行虚拟-物理地址转换的转换后备缓冲器(TLB)检索，且剩余部分(页偏移)包含管线中所产生的虚拟地址的较低阶位。在经虚拟标记的高速缓存器的情况下，整个关键字112在所述管线中产生。在任一情况下，检索/产生所述地址及存取所述CAM是在临界定时路径上，且存在充足的时间在将关键字112的所有或大部分对照经编码的关键字字段110进行比较之前将其编码，而不增加机器循环时间。

发明内容

在一个或一个以上实施例中，在存储到TLB中之前，将物理地址(其是CAM查找的搜索关键字)的页地址部分编码。然后，从从事于地址转换的TLB中检索所述经编码的页地址，且将其作为经编码的搜索关键字应用到所述CAM，以在所述CAM中对照经编码的关键字字段进行搜索。所述编码确保至少二的海明距离，从而保证至少两个晶体管针对所述CAM中的每一非匹配关键字字段并行将匹配线放电。可将物理地址的页偏移位(其不存储在所述TLB中)与TLB存取并行编码，且在存取所述CAM之前将所述两个经编码的物理地址部分连接。在其中存储在所述TLB中的页地址寻址大的存储器页大小的一个实施例中，可将所述页地址分为多个子页地址，每一子页地址寻址较小的页大小。可在将这些子页地址存储在微型TLB中之前将其编码。

一个实施例涉及存取具有多个经编码的关键字字段的内容可寻址存储器(CAM)的方法。将搜索关键字编码并存储。使用所述所存储、经编码的搜索关键字来存取所述CAM。

另一实施例涉及匹配内容可寻址存储器(CAM)中的地址的方法。将所述地址的经编码版本作为关键字字段存储在所述CAM中。将所述地址的至少第一部分的经编码版本存储在转换后备缓冲器(TLB)中。将所述来自所述TLB的经编码地址对照所述CAM中的多个经编码的关键字字段进行比较以检测是否匹配。

另一实施例涉及处理器。所述处理器包括包含内容可寻址存储器(CAM)及随机存取存储器(RAM)的高速缓冲存储器。当搜索关键字与存储在所述CAM中的对应的关键字字段匹配时，所述高速缓存器操作以向或从RAM条目存储或供应数据。所述关键字字段由至少二的海明距离编码。所述处理器还包括操作以将物理地址作为所述CAM的搜索关键字存储且输出的转换后备缓冲器(TLB)。通过与所述CAM关键字字段相同的算法将所述物理地址编码。

附图说明

图1是CAM结构中的代表性匹配线的部分的功能性方块图。

图2是处理器的功能性方块图。

图3是编码及存储页地址的流程图。

图4是检索经编码的页地址、编码页偏移及将所述经编码的物理地址应用到CAM的流程图。

具体实施方式

图2描绘代表性处理器10的功能性方块图。处理器10根据控制逻辑14在指令执行管线12中执行指令。所述管线包括各种寄存器或锁存器16(其组织于管线级中)及一个或一个以上算术逻辑单元(ALU)18。通用寄存器(GPR)堆20提供包含存储器层级的顶部的寄存器。

所述管线从指令高速缓存器(I-高速缓存器)21提取指令，所述高速缓存器包括CAM 22及RAM 23。指令存储器寻址及准许由指令侧转换后备缓冲器(ITLB)24管理。从包括CAM 26及RAM 27的高速缓存器25存取数据。数据存储器寻址及准许由主TLB 28管理。在各个实施例中，ITLB 24可包含TLB 28的部分的拷贝。另一选择为，可将ITLB 24与TLB 28整合在一起。

另外，处理器10可包括微型TLB 29。微型TLB 29是小的高速电路，其通常保存最近从主TLB 28存取的物理地址。处理器10可首先将虚拟地址应用到微型TLB 29，且仅当在微型TLB 29中无法找到对应的页地址及属性时存取主TLB 28。在一个实施例中，微型TLB 29条目可寻址比对应的TLB 28条目小的页大小，如本文所述。

在处理器10的各个实施例中，可整合或联合I高速缓存器22与D高速缓存器26。在存储器接口30的控制下，I高速缓存器22及/或D高速缓存器26中的未命中导致对主(芯片外)存储器32的存取。处理器10可包括输入/输出(I/O)接口34，从而控制对各个外围装置36的存取。所属技术领域的技术人员将认识到处理器10的多种变化形式是可行的。举例来说，处理器10可包括用于I及D高速缓存器21、25中的任一者或两者的第二阶(L2)高速缓存器。此外，可在特定实施例中省略描绘于处理器10中的功能性块中的一者或一者以上。

如在所属技术领域中所熟知，大多数程序就像其对整个处理器可寻址存储器(例如，32个地址位)具有排他性的使用一样来执行。此被认作虚拟地址，且是在所述管线中所利用的寻址模式。当存取实际的存储器时，所述虚拟地址由TLB 28(或针对指令的ITLB 24)转换为物理地址。所述操作系统将每一程序的虚拟地址映射到存储器的具体区域(称作存储器页)。通常，虚拟地址的上或最高有效位被映射到页地址(TLB28所提供的部分)。所述虚拟地址的下或最低有效位(称作页偏移)将所述存储器页内的数据加索引；不转换所述页偏移。为简明及清楚起见，在从D高速缓存器25的数据存取的上下文中提供以下论述，将从TLB 28获得的地址与CAM 26相比较。然而，相同的揭示内容适用于从I高速缓存器21、ITLB 24及I高速缓存器CAM 22的指令存取。

在一个或一个以上实施例中，当存取经物理标记的高速缓存器25时，通过在将所述页地址存储到TLB 28中之前执行大多数关键字112(其是物理地址)的编码来将将要应用于CAM 26的所述编码从临界定时路径移除。当程序被初始化时，页表格由操作系统软件在TLB 28中设立。可在所述时间将所述页地址编码而不影响处理器性能。随后，在对高速缓存器25的存取之后，来自所述管线的虚拟地址由TLB 28转换以获得经编码的页地址。可与所述TLB 28查找并行将必要的页偏移位编码，因为所述地址的此部分比所述页地址短得多，可在可用的时间中完成所述编码操作。然后，可将所述经编码的页偏移连接到TLB 28所提供的经编码页地址，且可将每一编码操作所产生的校验位执行“异或”运算以获得最终的校验位。然后，将所述经编码的物理地址作为关键字112应用到CAM 26，用于对照经编码的关键字字段110进行比较。此使CAM 26能够通过使用经编码的关键字字段110及经编码的关键字112而使用较短的比较时间来操作以确保至少两个误比较且因此至少接通两个放电晶体管106来在单个位的错配的最糟情况下将匹配线102放电。

存储在TLB 28中的页地址的大小根据其寻址的存储器页的大小相反地变化。对于较大的页大小，更少的位被转换及存储在TLB 28中，且虚拟地址的更多的位用于所述偏移。在具有非常大的存储器页的应用中，大量的页偏移位可排除与TLB 28存取并行地在“运行中”将这些位编码。在此情况下，可将所述页地址分为两个或更多个子页地址，每一子页地址寻址较小的存储器页大小。举例来说，可将寻址64K的存储器页的页地址划分为四个子页地址，每一子页地址寻址4K的存储器页。可复制所述64K页的TLB 28属性且可使其与所述子页地址中的每一者相关联。

可不将所述4K的子页地址存储在TLB 28中，因为当执行转换操作时其将与所述64K的页地址冲突。在一个实施例中，将所述子页地址编码并存储在微型TLB 29中。此是对微型TLB 29的低效率使用，因为(例如)需要四个条目来转换在主TLB 28中仅需要一个条目的相同虚拟地址范围。然而，存储在微型TLB 29中的经编码子页地址各包含比对应的页地址多的位，从而剩下在存取CAM 26之前必须在“运行中”转换的更少的位。

在图3及4中以流程图描绘根据各个实施例的编码及存储关键字112以及存取所存储的经编码关键字112及将其应用到CAM 26的过程。图3描绘当操作系统软件设立TLB 28时所采取的动作；图4描绘在程序执行(即，在临界定时路径上)期间存取CAM 26的步骤。

参照图3，操作系统软件在TLB 28中设立页表格(块40)。取决于所述存储器页的大小(块42)，所述编码可通过不同的过程继续前进。如果所述页相对较小(块42)，意指所述页地址长而所述页偏移短，那么所述页地址由至少二的海明距离编码(块44)。然后，将所述经编码的页地址存储在TLB 28中(块46)。

另一方面，如果所述存储器页较大(块42)，意指所述页地址较短而所述页偏移较长，那么可能不存在充足的时间来在地址转换期间在“运行中”将所述页偏移的必要部分编码。在此情况下，可产生两个或更多个子页地址，每一子页地址寻址比对应的页地址小的存储器页(块48)。此增加所述子页地址的长度而减小所述对应的页偏移的长度，从而允许将所述偏移运行中编码而不影响机器循环时间。每一子页地址由至少二的海明距离编码(块50)，且将所述经编码的子页条目存储在微型TLB 29中。

注意，标签“大”及“小”指示从决策块42的退出路径是相对的。如本文所使用，小的存储器页大小是产生小到足以由至少二的海明距离与TLB 28存取并行运行中编码的页偏移的存储器页大小。相反，大的存储器页大小是产生大到足以与对TLB28的存取并行运行中编码的页偏移的存储器页大小。其证明为大或小的实际存储器页大小可随每一实施方案而变化，此取决于许多因素，例如半导体技术，时钟速度、操作电压等。在图3的流程图的结尾，将足够长的经编码(子)页地址存储在TLB 28或微型TLB 29中。

在随后的程序执行期间，存储器存取指令在所述执行管线中产生虚拟地址(块54)，且将所述虚拟地址提供到TLB 28及/或微型TLB 29以供转换。TLB 28或微型TLB 29转换所述虚拟地址，且提供经编码的(子)页地址(块56)。与TLB 28或微型TLB 29查找并行，所述页偏移的必要部分由至少二的海明距离编码(块58)。在一个实施例中，然后，将所述经编码的(子)页地址与经编码的页偏移连接，且将所述两个校验位执行“异或”运算，从而产生具有单个校验位的经编码物理地址(块60)。然后，将此物理地址作为搜索关键字112提供到CAM 26以对照多个经编码的关键字字段110进行比较(块62)。

在另一实施例中，将所述页地址及页偏移作为每一CAM条目100的单独关键字字段110存储。即，每一CAM条目100包括两个匹配线102段，且任一段的放电将示意错配。在一个实施例中，每一匹配线102段包括匹配线读出电路114，且在应用到冲突检测逻辑116之前将匹配线读出电路114的输出AND在一起。在此情况下，将来自TLB 28的经编码页地址及来自微型TLB 29的子页地址应用到CAM 26的对应页地址部分。与TLB 28或微型TLB 29存取并行，所述页偏移由至少二的海明距离编码。然后，与所述(子)页地址并行将所述经编码的页偏移应用到CAM 26。所述经编码的(子)页地址及经编码的页偏移中的每一者包括校验位。

在其它实施例中，可出于速度、扇出数、功率消耗或其它设计考虑而视需要进一步将CAM 26的匹配线102(且对应地，关键字110)分段。段的数量及每一段的位长度可由实施方案的技术、布局、将要比较的位的数量、所需要的循环速度等决定。此外，可以每一CAM条目100仅需要一个匹配线读出电路114的各种方式来配置及布置所述段。举例来说，在一个实施例中，可将匹配线102段级联在一起或形成波纹，使得任一段中的有源放电电路106将整个匹配线102放电。在另一实施例中，匹配线102可采用层级结构，其中每一段连接到全局匹配线102，其在所述所附装的段中的任一者放电时放电。所属技术领域的技术人员将认识到有利地将匹配线102分割的各种各样的方式。

如所属技术领域的技术人员将了解，随着时间通过高速缓冲存储未命中处理操作将经编码的关键字字段110载入CAM 26中。在高速缓冲存储未命中之后，存储器存取指令从主存储器提取所需要的数据，且将其放入RAM 27中，从而取代现有的信息。对应的CAM 26条目由未被命中的经编码物理地址取代。

通过使用至少二的海明距离来将CAM 26的关键字112及关键字字段110编码，由于与关键字112相差至少一个位的每一关键字字段110，至少两个放电晶体管106将匹配线102放电到接地。可有利地将整个CAM 26定时设定为两个晶体管106将匹配线102放电所需要的时间，而不是一个晶体管106将匹配线102放电所需要的时间，从而改善CAM 26的操作速度。

所有固态存储器倾于出现软错误，所述错误是由带电粒子或辐射导致的所存储的数据中的错误。阿尔法粒子可导致软错误，或宇宙射线可导致电扰。辐射的两种形式是随机的，且软错误可导致关键字字段110中的单个位错误。此增加关键字112与关键字字段110之间出现单个位错配的可能性。考虑若干种可能性。

首先，如果关键字112与关键字字段110匹配，且所述匹配的关键字字段110接收单个位的软错误，那么可以或可不将对应的CAM 26条目检测为命中。因为使用每一匹配线102的两个误比较的最糟情形情景来设定整个CAM 26定时，因此单个位的误比较可具有充足的时间来在读出电路114做出评价之间将对应的匹配线102完全放电。在此情况下，将检测到匹配线102处于高的状态，其指示匹配。由于关键字112应与此关键字字段110匹配，且由于软错误而仅处于被视为错配的危险中，那么检测到匹配产生高速缓存器26的正确操作，且所述软错误无关紧要。

在第二种情况中，因软错误而产生的单个位误比较可足够快地将匹配线102拉低以便相关联的读出电路114将CAM 26条目视为错配。由于关键字112应另外与每一其它CAM 26条目错配，因此此导致地址在应命中时反而错误地在所述高速缓存器中未命中。处理器10将检测到高速缓冲存储未命中，且执行对主存储器32的存取，从而取代高速缓存器25中的对应的线并用所述未命中、经编码的地址更新CAM 26，从而更正所述软错误(以所述主存储器存取的延迟为代价)。

另一种可能性是关键字112与第一关键字字段110匹配，且与第二关键字字段110相差单个位。由于用二或更多的海明距离将关键字112及关键字字段110编码，因此第二(错配)关键字字段110将通过至少两个放电晶体管106正常放电。如果所述错配位或所述校验位是被软错误破坏的位，那么对应的匹配线102将仅通过一个晶体管106放电，此需要如此长的时间以至于对应的读出电路114将匹配线102检测为高，其指示匹配。关键字112另外与第一关键字字段110匹配；因此，关键字112看似已匹配或命中多于一个CAM 26条目。在此情况下，监视所有匹配线读出电路114的输出的冲突检测电路116将检测到所述明显的双重匹配并导致错误。

又一种可能性是关键字112与关键字字段110相差两个位。通过二的海明距离将关键字112及关键字字段110编码意指其将具有相同的校验位。举例来说，包含所有0的关键字字段110在偶校验的情况下将具有0校验位。关键字112包含两个1，且所有其它位是0；此关键字112也将具有0校验位。如果软错误在对应于关键字112中的1位中的一者的位置中将关键字字段110的0位中的一者破坏为1，那么关键字112与关键字字段110仅相差一个位(关键字112中的另一1位)。如果将CAM 26定时设定为每一误比较两个放电电路106的最糟情形，那么匹配线102可在此情形中保持为高，且CAM 26将检测到错误匹配，从而在高速缓存器21、25中产生错误的命中。

一种避免此种可能性的方式是通过三或更多的海明距离将关键字112及关键字字段110编码。此在计算上更加复杂，且对于CAM 26中的每一条目110以及对于TLB28或微型TLB 29中的每一(子)页地址需要多于一个的校验位。另一方面，三的海明距离将提高CAM 26的速度(针对同一种技术)，因为至少三个放电106将将每一误比较的匹配线102放电(至少在不存在软错误的情况下)。给定本揭示内容的教示，更高阶的海明距离当然是可能的且将是所属技术领域的技术人员明了的实施方案。然而，在CAM 26加速中存在回报递减，以通过增加更多的冗余存储元件110(“异或”运算栅极108及放电晶体管106)来增加CAM 26的大小及其功率消耗为代价。

作为增加海明距离的替代方案，可在所述(错误的)高速缓冲存储命中之后通过所述高速缓存器控制器来检测上述错误状况，且如果检测到所述状况，那么错误产生。在高速缓冲存储命中之后，所述高速缓存器控制器读出关键字字段110。撇开所述校验位，且重新产生剩余关键字字段110的校验且将其与从CAM 26读取的校验相比较。如果所述校验位不匹配，那么所述高速缓存器控制器使条目100失效并产生例外。在将机器状态恢复到所述高速缓存器存取之前的状态之后，所述处理器将再次存取高速缓存器21、25，从而产生高速缓冲存储未命中。然后，将正确的、经编码的关键字字段110作为所述高速缓冲存储未命中处理操作的部分写入到CAM 26。由于所述高速缓存器控制器在将所述高速缓冲存储线传递到处理器管线12之后读取并校验-检查字段关键字110，因此此操作不会不利地影响高速缓存器性能。

虽然在本文中在作为高速缓冲存储器25的部分的CAM 26的上下文中阐述本发明，但所属技术领域中的技术人员将容易地认识到本发明并不限于所述应用。内容可寻址存储器用于各种电路及系统，包括其中“窥探”地址以支持高速缓存器一致性方案的数据缓冲器、其中对照CAM搜索IP地址的包路由器及类似物。在许多此类应用中，可通过将所述关键字字段编码而导致两个或更多个放电电路在错配时启用来改善CAM速度，通过存储将要对照所述CAM应用的经编码关键字而不影响整体循环时间。

虽然本文已就本发明的特定特征、方面及实施例阐述了本发明，但应了解，在本发明的广泛范围内的许多变化形式、修改及其它实施例是可行的，且因此应认为所有变化形式、修改及实施例归属于本发明的范围内。因此，应在所有方面中将本发明实施例视为说明性的而并非限制性，且归属于随附权利要求书的意义和等效范围内的所有变化既定涵盖于其中。