具有主高速缓存器和溢出FIFO高速缓存器的高速缓存器系统

摘要

高速缓冲存储器系统包括使用搜索地址共同进行搜索的主高速缓存器和溢出高速缓存器。溢出高速缓存器作为主高速缓存器所用的驱逐阵列进行工作。使用搜索地址的位来对主高速缓存器进行寻址，并且溢出高速缓存器被配置为FIFO缓冲器。高速缓冲存储器系统可用于实现微处理器所用的转译后备缓冲器。

说明书

相关申请的交叉引用

本申请要求2014年10月8日提交的美国临时申请序列号62/061,242的优 先权，在此通过引用包含其全部内容以用于所有的目的和用途。

技术领域

本发明通常涉及微处理器高速缓存系统，并且更特别地涉及具有主高速 缓存器和溢出FIFO高速缓存器的高速缓存系统。

背景技术

现代微处理器包括用于减少存储器访问延迟并且提高整体性能的存储 器高速缓存器系统。系统存储器位于微处理器的外部并且经由系统总线等访 问该系统存储器，使得系统存储器访问相对较慢。通常，高速缓存器是用于 以透明方式存储根据先前请求从系统存储器中检索到的数据、使得将来针对 相同数据的请求可以更快检索的更小且更快速的本地存储器组件。高速缓存 器系统自身通常是以具有多个高速缓存级的层级方式配置成的，其中这多个 高速缓存级诸如包括更小且更快速的第一级(L1)高速缓冲存储器和略大且略 慢的第二级(L2)高速缓冲存储器等。尽管可以设置附加的级，但由于附加的 级以相似的方式相对于彼此进行工作、并且由于本公开主要关注L1高速缓存 器的结构，因此没有进一步论述这些附加的级。

在所请求的数据位于L1高速缓存器中从而引起高速缓存器命中(cache hit)的情况下，在延迟最小的情况下检索到该数据。否则，在L1高速缓存器 中发生高速缓存未命中(cachemiss)并且在L2高速缓存器中搜索同一数据。L2 高速缓存器是以与L1高速缓存器分开的方式进行搜索的单独的高速缓存器 阵列。此外，L1高速缓存器具有的组(set)和/或路(way)更少，与L2高速缓存 器相比通常更小且更快速。在所请求的数据位于L2高速缓存器中、从而调用 L2高速缓存器中的高速缓存器命中的情况下，与L1高速缓存器相比，在延迟 增加的状态下检索到数据。否则，如果在L2高速缓存器中发生高速缓存未命 中，则在与该高速缓冲存储器相比延迟明显变大的状态下从更高的高速缓存 级和/或系统存储器检索数据。

将来自L2高速缓存器或系统存储器的所检索到的数据存储在L1高速缓 存器中。L2高速缓存器用作将从L1高速缓存器驱逐的条目存储在L2高速缓 存器中的“驱逐(eviction)”阵列。由于L1高速缓存器是有限的资源，因此新检 索到的数据可以移置或驱逐L1高速缓存器中否则将为有效的条目，该条目被 称为“丢弃者(victim)”。如此将L1高速缓存器的丢弃者存储在L2高速缓存器 中，并且将L2高速缓存器的任何丢弃者(在存在的情况下)存储在更高级中、 或者丢弃。可以实现诸如本领域普通技术人员所理解的最近最少使用(LRU) 等的各种替换策略。

许多现代微处理器还包括虚拟存储器能力、并且特别是存储器分页机 制。如本领域内众所周知的，操作系统创建该操作系统存储在系统存储器中 的用于将虚拟地址转译成物理地址的页表。诸如根据如2006年6月出版的 IA-32IntelArchitectureSoftwareDeveloper’sManual,Volume3A:System ProgrammingGuide,Part1中的第三章所述的x86架构处理器所采用的众所周 知的方案等，这些页表可以是以层级方式配置的，其中上述文献的全部内容 通过引用包含于此以用于所有的目的和用途。特别地，页表包括存储物理存 储器页的物理页地址和物理存储器页的属性的各页表条目(PTE)。用于获取 虚拟存储器页地址并且使用该虚拟存储器页地址遍历页表层级体系以最终 获得与该虚拟地址相关联的PTE、从而使虚拟地址转译成物理地址的处理通 常被称为表查找(tablewalk)。

物理系统存储器访问的延迟相对较慢，使得表查找由于涉及潜在地向物 理存储器的多个访问，因此是相对昂贵的操作。为了避免引发与表遍历相关 联的时间，处理器通常包括对虚拟向物理的地址转译进行高速缓存的转译后 备缓冲器(TLB)高速缓存方案。TLB的大小和结构影响性能。典型的TLB结 构可以包括L1TLB和相应的L2TLB。各TLB通常被配置为被组织为多个组 (或行)的阵列，其中各组具有多个路(或列)。与大多数高速缓存方案相同， L1TLB具有的组和路更少，与L2TLB相比通常更小，由此也更快速。尽管 更小且更快速，但期望在不会影响性能的情况下进一步缩小L1TLB的大小。

这里参考TLB高速缓存方案等来说明本发明，其中应当理解，原理和技 术等同地适用于任何类型的微处理器高速缓存方案。

发明内容

根据一个实施例的高速缓冲存储器系统包括主高速缓冲存储器和溢出 高速缓冲存储器，其中该溢出高速缓冲存储器作为主高速缓冲存储器所用的 驱逐阵列进行工作，以及在主高速缓冲存储器和溢出高速缓冲存储器内共同 搜索与所接收到的搜索地址相对应的存储值。主高速缓冲存储器包括被组织 为多个组和多个路的第一组存储位置，并且溢出高速缓冲存储器包括被组织 为先进先出(FIFO)缓冲器的第二组存储位置。

在一个实施例中，主高速缓冲存储器和溢出高速缓冲存储器共同形成用 于存储微处理器所用的主系统存储器的物理地址的转译后备缓冲器。微处理 器可以包括提供可用作搜索地址的虚拟地址的地址生成器。

根据一个实施例的一种对数据进行高速缓存的方法，包括以下步骤：将 第一组的条目存储在被组织为多个组和相应的多个路的主高速缓冲存储器 中；将第二组的条目存储在被组织为FIFO的溢出高速缓冲存储器中；使所述 溢出高速缓冲存储器作为针对所述主高速缓冲存储器的驱逐阵列进行工作； 以及在所述主高速缓冲存储器和所述溢出高速缓冲存储器内同时搜索与所 接收到的搜索地址相对应的存储值。

附图说明

将针对以下的说明和附图来更好地理解本发明的益处、特征和优点，其 中：

图1是包括根据本发明的实施例所实现的高速缓冲存储器系统的微处理 器的简化框图；

图2是示出图1的微处理器的前端管道、保留站、MOB的一部分和ROB 之间的接口的更详细框图；

图3是用于提供虚拟地址(VA)并且检索图1的微处理器的系统存储器中 的所请求数据位置的相应物理地址(PA)的MOB的一部分的简化框图；

图4是示出根据本发明的一个实施例所实现的图3的L1TLB的框图；

图5是示出包括16组4路(16×4)主L1.0阵列和8路溢出FIFO缓冲器L1.5阵 列的更具体实施例的图3的L1TLB的框图；以及

图6是根据一个实施例使用图5的L1TLB结构的驱逐处理的框图。

具体实施方式

期望在不会实质影响性能的情况下减小L1TLB高速缓存器阵列的大小。 本发明人已意识到与传统的L1TLB结构相关联的低效率。例如，大多数应用 程序的代码不能使L1TLB的利用率最大化，往往使得一些组被过度利用而其 它组未得到充分利用。

因此，本发明人开发了提高性能和高速缓冲存储器利用率的、具有主高 速缓存器和溢出先进先出(FIFO)高速缓存器的高速缓存器系统。该高速缓存 器系统包括溢出FIFO高速缓存器(或L1.5高速缓存器)，其中该溢出FIFO高速 缓存器用作高速缓存器搜索期间主高速缓存器阵列(或L1.0高速缓存器)的扩 展，而且还用作针对L1.0高速缓存器的驱逐阵列。L1.0高速缓存器与传统结 构相比大小大幅减小。溢出高速缓存器阵列或L1.5高速缓存器被配置为FIFO 缓冲器，其中在该FIFO缓冲器中，L1.0和L1.5这两者的存储位置的总数与传 统的L1TLB高速缓存器相比大大减少。从L1.0高速缓存器所驱逐的条目被推 入到L1.5高速缓存器上，并且在L1.0高速缓存器和L1.5高速缓存器内共同进 行搜索以由此扩展L1.0高速缓存器的设备大小。从FIFO缓冲器被推出的条目 是L1.5高速缓存器的丢弃者并且存储在L2高速缓存器中。

如这里所述，TLB结构根据改进后的高速缓存器系统而被配置为包括溢 出TLB(或L1.5TLB)，其中该溢出TLB用作高速缓存器搜索期间主L1TLB (或L1.0TLB)的扩展，而且还用作L1.0TLB所用的驱逐阵列。组合后的TLB 结构与较大的L1高速缓存器相比，在实现相同的性能的同时扩展了较小的 L1.0的设备大小。主L1.0TLB使用诸如传统的虚拟地址索引等的索引，而溢 出L1.5TLB阵列被配置为FIFO缓冲器。尽管这里参考TLB高速缓存方案等来 说明本发明，但应当理解，原理和技术等同地适用于任何类型的层级式微处 理器高速缓存方案。

图1是包括根据本发明的实施例所实现的高速缓冲存储器系统的微处理 器100的简化框图。微处理器100的宏架构可以是x86宏架构，其中在该x86宏 架构中，微处理器100可以正确地执行被设计成在x86微处理器上执行的大多 数应用程序。在获得了应用程序的预期结果的情况下，正确地执行了该应用 程序。特别地，微处理器100执行x86指令集的指令并且包括x86用户可见的 寄存器集。然而，本发明不限于x86架构，在本发明中，微处理器100可以是 根据如本领域普通技术人员所知的任何可选架构。

在例示实施例中，微处理器100包括指令高速缓存器102、前端管道104、 保留站106、执行单元108、存储器排序缓冲器(MOB)110、重排序缓冲器(ROB) 112、2级(L2)高速缓存器114和用于连接并访问系统存储器118的总线接口单 元(BIU)116。指令高速缓存器102对来自系统存储器118的程序指令进行高速 缓存。前端管道104从指令高速缓存器102提取程序指令并且将这些程序指令 解码成微指令以供微处理器100执行。前端管道104可以包括共同将宏指令解 码并转译成一个或多个微指令的解码器(未示出)和转译器(未示出)。在一个 实施例中，指令转译将微处理器100的宏指令集(诸如x86指令集架构等)的宏 指令转译成微处理器100的微指令集架构的微指令。例如，可以将存储器访 问指令解码成包括一个或多个加载微指令或存储微指令的微指令序列。本公 开主要涉及加载操作和存储操作以及这里简单称为加载指令和存储指令的 相应微指令。在其它实施例中，加载指令和存储指令可以是微处理器100的 原生指令集的一部分。前端管道104还可以包括寄存器别名表RAT(未示出)， 其中该RAT针对各指令基于其程序顺序、其指定的操作数源和重命名信息来 生成依赖信息。

前端管道106将解码后的指令及其关联的依赖信息调度到保留站106。保 留站106包括保持从RAT接收到的指令和依赖信息的队列。保留站106还包括 发出逻辑，其中该发出逻辑使来自队列的指令在准备好执行的情况下发出至 执行单元108和MOB110。在消除了指令的所有依赖的情况下，该指令准备 好被发出并执行。与调度指令相结合地，RAT向该指令分配ROB112中的条 目。因而，将指令按程序顺序分配到ROB112中，其中该ROB112可被配置 为循环队列以确保这些指令按程序顺序退出。RAT还将依赖信息提供至ROB 112以存储在其中指令的条目中。在ROB112重放指令的情况下，ROB112在 指令的重放期间将ROB条目中所存储的依赖信息提供至保留站106。

微处理器100是超标量，并且包括多个执行单元且能够在单个时钟周期 内向执行单元发出多个指令。微处理器100还被配置为进行乱序执行。也就 是说，保留站106可以不按由包括指令的程序指定的顺序发出指令。超标量 乱序微处理器通常尝试维持相对较大未处理指令池，使得这些微处理器可以 利用更大量的指令并行。微处理器100在确定知晓指令实际上是否将完成之 前还可以进行指令的预测执行，在预测执行中该微处理器100执行指令或者 至少进行该指令所规定的动作中的一部分。由于诸如错误预测分支指令和异 常(中断、页故障、除零状况、一般保护错误等)等的各种原因，因而指令可 能无法完成。尽管微处理器100可以以预测方式进行指令所规定的动作中的 一部分，但该微处理器在确定知晓指令将完成之前不利用指令的结果更新系 统的架构状态。

MOB110处理经由L2高速缓存器114和BIU116与系统存储器118的接 口。BIU116使微处理器100连接至处理器总线(未示出)，其中该处理器总线 连接有系统存储器118和诸如系统芯片组等的其它装置。微处理器100上所运 行的操作系统将页映射信息存储在系统存储器118中，其中如这里进一步所 述，微处理器100针对该系统存储器118进行读取和写入以进行表查找。在保 留站106发出指令时，执行单元108执行这些指令。在一个实施例中，执行单 元108可以包括微处理器的诸如算术逻辑单元(ALU)等的所有执行单元。在例 示实施例中，MOB110包含用于执行加载指令和存储指令的加载执行单元和 存储执行单元，以如这里进一步所述访问系统存储器118。执行单元108在访 问系统存储器118时与MOB110连接。

图2是示出前端管道104、保留站106、MOB110的一部分和ROB112之间 的接口的更详细框图。在该结构中，MOB110通常进行工作以接收并执行加 载指令和存储指令这两者。保留站106被示出为划分成加载保留站(RS)206 和存储RS208。MOB110包括针对加载指令的加载队列(加载Q)210和加载管 道212，并且还包括针对存储指令的存储管道214和存储Q216。通常，MOB 110使用加载指令和存储指令所指定的源操作数来解析加载指令的加载地址 并且解析存储指令的存储地址。操作数的源可以是架构寄存器(未示出)、常 数和/或指令所指定的位移。MOB110还从数据高速缓存器中的所计算出的加 载地址读取加载数据。MOB110还向数据高速缓存器中的所计算出的加载地 址写入加载数据。

前端管道104具有按如下的程序顺序推入加载指令条目和存储指令条目 的输出201，其中在该程序顺序中，将加载指令按顺序依次加载到加载Q210、 加载RS206和ROB112。加载Q210存储系统中的所有活动加载指令。加载 RS206对加载指令的执行进行调度，并且在“准备好”以供执行的情况下(诸如 在加载指令的操作数可利用时等)，加载RS206将加载指令经由输出203推入 到加载管道212以供执行。在例示结构中，可以以乱序和预测方式进行加载 指令。在加载指令完成的情况下，加载管道212将完成指示205提供至ROB 112。如果出于任何原因、加载指令不能完成，则加载管道212向加载Q210 发出未完成指示207，使得现在加载Q210控制未完成的加载指令的状态。在 加载Q210判断为可以重放未完成的加载指令的情况下，该加载Q210将重放 指示209发出至重新执行(重放)加载指令的加载管道212，但这次加载指令是 从加载Q210所加载的。ROB112确保了指令按原始程序的顺序的有序退出。 在已完成的加载指令准备好退出、意味着该加载指令是ROB112中按程序顺 序的最早指令的情况下，ROB112向加载Q210发出退出指示211并且该加载 指令从加载Q210有效地弹出。

将存储指令条目按程序顺序推入存储Q216、存储RS208和ROB112。存 储Q216存储系统中的所有活动存储指令。存储RS208调度存储指令的执行， 并且在“准备好”以供执行的情况下(诸如在存储指令的操作数可利用时等)， 存储RS208将存储指令经由输出213推入到存储管道214以供执行。尽管存储 指令可以不按程序顺序来执行，但这些存储指令不是以预测方式提交的。存 储指令具有执行阶段，其中在该执行阶段中，该存储指令生成其地址、进行 异常检查、获得线路的所有权等，而这些操作可以是以预测方式或以乱序方 式进行的。然后，存储指令具有提交阶段，其中在该提交阶段中，该存储指 令实际上进行不是预测或乱序方式的数据写入。存储指令和加载指令在被执 行的情况下彼此比较。在存储指令完成的情况下，存储管道214将完成指示 215提供至ROB112。如果出于任何原因、存储指令不能完成，则存储管道214 向存储Q216发出未完成指示217，使得现在存储Q216控制未完成的存储指 令的状态。在存储Q216判断为可以重放未完成的存储指令的情况下，该存 储Q216将重放指示219发送至重新执行(重放)该存储指令的存储管道214，但 这次存储指令是从存储Q216所加载的。在已完成的存储指令准备好退出的 情况下，ROB112向存储Q216发出退出指示221并且该存储指令从存储Q216 有效地弹出。

图3是用于提供虚拟地址(VA)并且检索系统存储器118中的所请求数据 位置的相应物理地址(PA)的MOB110的一部分的简化框图。使用操作系统使 给定处理可用的一组虚拟地址(还已知为“线性”地址等)来引用虚拟地址空 间。加载管道212被示出为接收加载指令L_INS并且存储管道214被示出为接 收存储指令S_INS，其中L_INS和S_INS这两者都是针对最终位于系统存储器 118中的相应物理地址处的数据的存储器访问指令。响应于L_INS，加载管道 212生成被示出为VA_L的虚拟地址。同样，响应于S_INS，存储管道214生成 被示出为VA_S的虚拟地址。虚拟地址VA_L和VA_S通常可被称为搜索地址，其中 这些搜索地址用于在高速缓冲存储器系统(例如，TLB高速缓存器系统)中搜 索与搜索地址相对应的数据或其它信息(例如，与虚拟地址相对应的物理地 址)。在例示结构中，MOB110包括对有限数量的虚拟地址的相应物理地址 进行高速缓存的1级转译后备缓冲器(L1TLB)302。在命中的情况下，L1TLB 302将相应的物理地址输出至请求装置。因而，如果VA_L生成命中，则L1TLB 302输出针对加载管道212的相应的物理地址PA_L，并且如果VA_S生成命中，则 L1TLB302输出针对存储管道214的相应的物理地址PA_S。

然后，加载管道212可以将所检索到的物理地址PA_L应用于数据高速缓存 器系统308以访问所请求的数据。高速缓存器系统308包括数据L1高速缓存器 310，并且如果在该数据L1高速缓存器310中存储有与物理地址PA_L相对应的 数据(高速缓存器命中)，则将被示出为D_L的所检索到的数据提供至加载管道 212。如果L1高速缓存器310发生未命中、使得所请求的数据D_L没有存储在 L1高速缓存器310中，则最终或者从L2高速缓存器114或者从系统存储器118 检索到该数据。数据高速缓存器系统308还包括FILLQ312，其中该FILLQ312 用于连接L2高速缓存器114以将高速缓存行加载到L2高速缓存器114中。数据 高速缓存器系统308还包括探测Q314，其中该探测Q314维持L1高速缓存器 310和L2高速缓存器114的高速缓存一致性。对于存储管道214而言，操作相 同，其中存储管道214使用所检索到的物理地址PA_S以将相应的数据D_S经由数 据高速缓存器系统308存储到存储器系统(L1、L2或系统存储器)中。没有进 一步说明数据高速缓存器系统308以及L2高速缓存器114和系统存储器118相 互作用的操作。然而，应当理解，本发明的原理可以以类推方式等同地应用 于数据高速缓存器系统308。

L1TLB302是有限的资源，使得最初并且随后周期性地，没有将所请求 的与虚拟地址相对应的物理地址存储在L1TLB302中。如果没有存储物理地 址，则L1TLB302将“MISS(未命中)”指示连同相应的虚拟地址VA(VA_L或 VA_S)一起设置向L2TLB304，以判断L2TLB304是否存储有与所提供的虚拟 地址相对应的物理地址。尽管物理地址可能存储在L2TLB304内，然而该物 理地址将表查找连同所提供的虚拟地址一起推入到表查找引擎306中 (PUSH/VA)。表查找引擎306作为响应而发起表查找，以获得在L1TLB和L2 TLB中未命中的虚拟地址VA的物理地址转译。L2TLB304更大且存储更多的 条目，但与L1TLB302相比更慢。如果在L2TLB304内发现与虚拟地址VA 相对应的被示出为PA_L2的物理地址，则取消推入到表查找引擎306的相应表 查找操作，并且将虚拟地址VA和相应的物理地址PA_L2提供至L1TLB302以存 储在该L1TLB302中。将指示提供回到诸如加载管道212(和/或加载Q210) 或者存储管道214(和/或存储Q216)等的请求实体，使得使用相应的虚拟地址 的后续请求允许L1TLB302提供相应的物理地址(例如，命中)。

如果在L2TLB304中请求也未命中，则表查询引擎306所进行的表查找 处理最终完成并且将所检索到的被示出为PA_TW的物理地址(与虚拟地址VA 相对应)返回提供至L1TLB302以存储在该L1TLB302中。在L1TLB304中发 生未命中、使得物理地址由L2TLB304或表查找引擎306来提供的情况下， 并且如果所检索到的物理地址驱逐了L2TLB30内的否则为有效的条目，则 将所驱逐的条目或“丢弃者”存储在L2TLB中。L2TLB304的任何丢弃者简单 地被推出，以有利于新获取到的物理地址。

向物理系统存储器118的各访问的延迟缓慢，使得可能涉及多个系统存 储器118访问的表查找处理是相对昂贵的操作。如这里进一步所述，L1TLB 302是以与传统的L1TLB结构相比提高性能的方式配置成的。在一个实施例 中，L1TLB302的大小与相应的传统L1TLB相比由于物理存储位置较少因此 更小，但如这里进一步所述，针对许多程序例程实现了相同的性能。

图4是示出根据本发明的一个实施例所实现的L1TLB302的框图。L1 TLB302包括表示为L1.0TLB402的第一或主TLB和表示为L1.5TLB404的 溢出TLB(其中，符号“1.0”和“1.5”用于区分彼此以及与整体L1TLB302区分 开)。在一个实施例中，L1.0TLB402是包括多个组和路的组关联高速缓存器 阵列，其中L1.0TLB402是包括J个组(编索引为I₀～I_J-1)和K个路(编索引为 W₀～W_K-1)的存储位置的J×K阵列，其中J和K各自是大于1的整数。J×K个存储 位置各自具有适合用于如这里进一步所述存储条目的大小。使用到系统存储 器118中所存储信息的“页”的表示为VA[P]的虚拟地址来访问(搜索)L1.0TLB 402的各存储位置。“P”表示仅包括完整虚拟地址的足以对各页进行寻址的高 位的信息的页。例如，如果信息的页的大小为2¹²＝4,096(4K)，则丢弃低12 位[11…0]以使得VA[P]仅包括其余的高位。

在提供VA[P]以在L1.0TLB402内进行搜索的情况下，使用VA[P]地址的 序列号较低的位“I”(仅高于完整虚拟地址的被丢弃的低位)作为索引VA[I]以 对L1.0TLB402的所选择的组进行寻址。将针对L1.0TLB402的索引位数“I” 确定为LOG₂(J)＝I。例如，如果L1.0TLB402具有16个组，则索引地址VA[I] 是页地址VA[P]的最低4位。使用VA[P]地址的其余高位“T”作为标签值VA[T]， 以使用L1.0TLB402的一组比较器406与所选择的组中的各个路的标签值进 行比较。这样，索引VA[I]选择L1.0TLB402中的存储位置的一组或行，并且 利用比较器406将所选择的组的被示出为TA1.0₀、TA1.0₁、…、TA1.0_K-1的K 个路各自内所存储的标签值分别与标签值VA[T]进行比较，以确定相应集合 的命中位H1.0₀、H1.0₁、…、H1.0_K-1。

L1.5TLB404包括包含Y个存储位置0、1、…、Y-1的先进先出(FIFO)缓 冲器405，其中Y是大于1的整数。不同于传统的高速缓存器阵列，没有对L1.5 TLB404编索引。作为代替，将新条目简单地推入FIFO缓冲器405的被示出 为FIFO缓冲器405的尾部407的一端，并且所驱逐的条目从FIFO缓冲器405的 被示出为FIFO缓冲器405的头部409的另一端被推出。由于没有对L1.5TLB 404编索引，因此FIFO缓冲器405的各存储位置具有适合存储包括完整虚拟页 地址以及相应的物理页地址的条目的大小。L1.5TLB404包括一组比较器 410，其中该一组比较器410各自的一个输入连接至FIFO缓冲器405的相应存 储位置以接收所存储的条目中的相应条目。在L1.5TLB404内进行搜索的情 况下，向该一组比较器410各自的另一输入提供VA[P]，从而将VA[P]与所存 储的各条目的相应地址进行比较以确定相应集合的命中位H1.5₀、H1.5₁、…、 H1.5_Y-1。

在L1.0TLB402和L1.5TLB404内共同进行搜索。将来自L1.0TLB402 的命中位H1.0₀、H1.0₁、…、H1.0_K-1提供至K输入逻辑OR门412的相应输入， 以在所选择的标签值TA1.0₀、TA1.0₁、…、TA1.0_K-1中的任一个等于标签值 VA[T]的情况下，提供表示L1.0TLB402内的命中的命中信号L1.0命中(L1.0 HIT)。此外，将L1.5TLB404的命中位H1.5₀、H1.5₁、…、H1.5_Z-1提供至Y输 入逻辑OR门414的相应输入，以在L1.5TLB404的条目其中之一的任何页地 址等于页地址VA[P]的情况下，提供表示L1.5TLB404内的命中的命中信号 L1.5命中(L1.5HIT)。将L1.0命中信号和L1.5命中信号提供至2输入逻辑OR门 416的输入，从而提供命中信号L1TLB命中(L1TLBHIT)。因而，L1TLB命 中表示整体L1TLB302内的命中。

L1.0高速缓存器402的各存储位置被配置为存储具有条目418所示的形 式的条目。各存储位置包括标签字段TA1.0_F[T](下标“F”表示字段)，其中该 标签字段TA1.0_F[T]用于存储条目的具有与标签值VA[T]相同的标签位数“T” 的标签值，以利用比较器406中的相应比较器进行比较。各存储位置包括用 于存储条目的用于访问系统存储器118中的相应页的物理页地址的相应物理 页字段PA_F[P]。各存储位置包括包含表示条目当前是否有效的一个或多个位 的有效字段“V”。可以针对各组设置用于确定替换策略的替换向量(未示出)。 例如，如果给定组的所有路均有效并且新条目要替换组中的条目其中之一， 则使用该替换向量来确定要驱逐哪个有效条目。然后，所驱逐的条目被推入 到L1.5高速缓存器404的FIFO缓冲器405上。在一个实施例中，例如，根据最 近最少使用(LRU)策略来实现替换向量，使得最近最少使用的条目是驱逐和 替换的对象。所例示的条目格式可以包括相应页的诸如状态信息等的附加信 息(未示出)。

L1.5高速缓存器404的FIFO缓冲器405的各存储位置被配置为存储具有 条目420所示的形式的条目。各存储位置包括用于存储条目的具有P位的虚拟 页地址VA[P]的虚拟地址字段VA_F[P]。在这种情况下，代替存储各虚拟页地 址的一部分作为标签，将整个虚拟页地址存储在条目的虚拟地址字段VA_F[P] 中。各存储地址还包括用于存储条目的访问系统存储器118中的相应页用的 物理页地址的物理页字段PA_F[P]。此外，各存储位置包括包含表示条目当前 是否有效的一个或多个位的有效字段“V”。所示出的条目格式可以包括相应 页的诸如状态信息等的附加信息(未示出)。

同时或者在同一时钟周期内访问L1.0TLB402和L1.5TLB404，由此对 这两个TLB的所有条目共同进行搜索。此外，由于从L1.0TLB402所驱逐的 丢弃者被推入到L1.5TLB404的FIFO缓冲器405上，因此L1.5TLB404用作针 对L1.0TLB402的溢出TLB。在L1TLB302内发生命中(L1TLBHIT)的情况 下，从L1.0TLB402或L1.5TLB404内的表示命中的相应存储位置中检索到 相应的物理地址条目PA[P]。L1.5TLB404使L1TLB302可以存储的总条目数 增加以提高利用率。在传统的TLB结构中，基于单一索引方案，某些组被过 度使用而其它组未得到充分使用。溢出FIFO缓冲器的使用提高了整体利用 率，使得L1TLB302尽管所具有的存储位置大大减少且大小在物理上缩小但 看似为更大的阵列。由于传统的TLB的一些行被过度使用，因此L1.5TLB404 用作溢出FIFO缓冲器，从而使得L1TLB302看似为所具有的存储位置的数量 比实际具有的存储位置数量更大。这样，整体L1TLB302与条目数量相同的 一个更大型TLB相比通常具有更佳性能。

图5是根据更具体实施例的L1TLB302的框图，其中：J＝16，K＝4，并 且Y＝8，使得L1.0TLB402是存储位置的16组4路的阵列(16×4)并且L1.5TLB 404包括具有8个存储位置的FIFO缓冲器405。此外，虚拟地址是表示为 VA[47:0]的48个位，并且页大小是4K。加载管道212和存储管道214这两者内 的虚拟地址生成器502提供虚拟地址的高36位或VA[47:12]，其中由于对4K页 的数据进行寻址，因此低12位被丢弃。在一个实施例中，VA生成器502进行 相加计算以提供用作针对L1TLB302的搜索地址的虚拟地址。将VA[47:12] 提供至L1TLB302的相应输入。

虚拟地址的低4位构成提供至L1.0TLB402的索引VA[15:12]，以对16个 组其中之一的被示出为所选择的组504进行寻址。虚拟地址的其余高位构成 提供至比较器406的输入的标签值VA[47:16]。将所选择的组504的4个路的所 存储的各条目内的各自具有形式VTX[47:16]的标签值VT0～VT3提供至比较 器406的各个输入以与标签值VA[47:16]进行比较。比较器406输出四个命中位 H1.0[3:0]。如果在所选择的四个条目中的任意条目中存在命中，则还提供相 应的物理地址PA1.0[47:12]作为L1.0TLB402的输出。

还将虚拟地址VA[47:12]提供至L1.5TLB404的一组比较器410各自的一 个输入。将L1.5TLB404的8个条目各自提供至一组比较器410中的相应比较 器410的另一输入，从而输出8个命中位H1.5[7:0]。如果在FIFO缓冲器405的 条目中的任一条目中存在命中，则还提供相应的物理地址PA1.5[47:12]作为 L1.5TLB404的输出。

将命中位H1.0[3:0]和H1.5[1:0]提供至表示OR门412、414和416的OR逻辑 505的各个输入，从而输出针对L1TLB302的命中位L1TLB命中(T1TLB HIT)。将物理地址PA1.0[47:12]和PA1.5[47:12]提供至PA逻辑506的各个输入， 从而输出L1TLB302的物理地址PA[47:12]。在命中的情况下，物理地址 PA1.0[47:12]和PA1.5[47:12]中的仅一个可以有效，并且在未命中的情况下， 物理地址输出均非有效。尽管没有示出，但还可以提供来自表示命中的存储 位置的有效字段的有效性信息。PA逻辑506可被配置为用于选择L1.0TLB 402和L1.5TLB404的物理地址中的有效的物理地址的选择或多路复用器 (MUX)逻辑等。如果没有设置L1TLB命中、从而表示针对L1TLB302的 MISS，则相应的物理地址PA[47:12]被忽略或被视为无效而丢弃。

图5所示的L1TLB302包括用于存储总共72个条目的16×4(L1.0)+8 (L1.5)个存储位置。L1TLB的现有传统结构被配置为用于存储总共192个条目 的16×12的阵列，这比L1TLB302的存储位置的数量的2.5倍大。L1.5TLB404 的FIFO缓冲器405用作L1.0TLB402的任意组和路所用的溢出，使得L1TLB 302的组和路的利用率相对于传统结构得以提高。更具体地，FIFO缓冲器405 与组或路的利用率无关地存储从L1.0TLB402所驱逐的任何条目。

图6是根据一个实施例的使用图5的L1TLB302结构的驱逐处理的框图。 该处理等同地适用于图4的更一般结构。在框602内共同示出L2TLB304和表 查找引擎306。在如图3所示、在L1TLB302中发生未命中的情况下，将未命 中(MISS)指示提供至L2TLB304。将引发未命中的虚拟地址的低位作为索引 应用于L2TLB304，以判断在该L2TLB304内是否存储有相应的物理地址。 此外，使用相同的虚拟地址来向表查找引擎306推入表查找。L2TLB304或 表查找引擎306返回虚拟地址VA[47:12]以及相应的物理地址PA[47:12]，其中 这两者均被示出为块602的输出。将虚拟地址的低4位VA[15:12]作为索引应用 于L1.0TLB402，并且将虚拟地址的其余高位VA[47:16]和相应返回的物理地 址PA[47:12]存储在L1.0TLB402内的条目中。如图4所示，VA[47:16]位形成 新的标签值TA1.0并且物理地址PA[47:12]形成所访问的条目内所存储的新的 PA[P]页值。根据可应用的替换策略，将该条目标记为有效。

提供至L1.0TLB402的索引VA[15:12]对L1.0TLB402内的相应组进行寻 址。如果存在相应组的至少一个无效条目(或路)，则在不会引起丢弃者的情 况下将新数据存储在否则为“空”的存储位置内。然而，如果不存在无效条目， 则利用该新数据驱逐并替换有效条目其中之一，并且L1.0TLB402输出相应 的丢弃者。关于利用新条目替换哪个有效条目或路的判断基于替换策略，诸 如根据最近最少使用(LRU)方案、伪LRU方案或者任何适当的替换策略或方 案等。L1.0TLB402的丢弃者包括丢弃者虚拟地址VVA_1.0[47:12]和相应的丢 弃者物理地址VPA_1.0[47:12]。从L1.0TLB402被驱逐的条目包括用作丢弃者 虚拟地址的高位VVA_1.0[47:16]的先前存储的标签值(TA1.0)。丢弃者虚拟地址 的低位VVA_1.0[15:12]与条目被驱逐的组的索引相同。例如，可以使用索引 VA[15:12]作为VVA_1.0[15:12]，或者可以使用标签值被驱逐的组中的相应内部 索引位。将标签值和索引位附加到一起以形成丢弃者虚拟地址VVA_1.0[47:12]。

丢弃者虚拟地址VVA_1.0[47:12]和相应的丢弃者物理地址VPA_1.0[47:12]共 同形成推入到L1.5TLB404的FIFO缓冲器405的尾部407处的存储位置的条 目。如果在接收到新条目之前L1.5TLB404没有满、或者如果L1.5TLB404 包括至少一个无效条目，则L1.5TLB404可以不驱逐丢弃者条目。然而，如 果L1.5TLB404已充满条目(或者至少充满有效条目)，则FIFO缓冲器405的头 部409处的最后条目被推出并且作为L1.5TLB404的丢弃者被驱逐。L1.5TLB 404的丢弃者包括丢弃者虚拟地址VVA_1.5[47:12]和相应的丢弃者物理地址 VPA_1.5[47:12]。在例示结构中，L2TLB304较大并且包括32个组，使得将来 自L1.5TLB404的丢弃者虚拟地址VVA_1.5[47:12]的低5位作为索引提供至L2 TLB304以访问相应的组。将丢弃者虚拟地址的其余高位VVA_1.5[47:17]和丢 弃者物理地址VPA_1.5[47:12]作为条目提供至L2TLB304。这些数据值被存储 在L2TLB304内的索引组的无效条目(如果存在)中，或者在驱逐先前存储的 条目的情况下存储在所选择的有效条目中。可以简单地丢弃从L2TLB304驱 逐的任何条目以有利于新数据。

可以使用各种方法来实现和/或管理FIFO缓冲器405。在上电复位(POR) 时，FIFO缓冲器405可被初始化为空的缓冲器或者通过将各条目标记为无效 而被初始化为空的缓冲器。最初，在不会引起丢弃者的情况下，将新条目(L1.0 TLB402的丢弃者)放置在FIFO缓冲器405的尾部407，直到FIFO缓冲器405变 为满为止。在FIFO缓冲器405为满的状态下向尾部407添加新条目的情况下， 头部409处的条目作为丢弃者VPA_1.5从FIFO缓冲器405被推出或“弹出”，然后 如前面所述可被提供至L2TLB304的相应输入。

在操作期间，可以将先前有效的条目标记为无效。在一个实施例中，无 效的条目保持作为条目，直到从FIFO缓冲器405的头部被推出为止，其中在 这种情况下，该无效的条目被丢弃并且不存储在L2TLB304中。在另一实施 例中，在将否则有效的条目标记为无效的情况下，现有值可能发生偏移，使 得无效条目被有效条目替代。可选地，将新值存储在无效化的存储位置中并 且更新指针变量以维持FIFO操作。然而，较后的这些实施例增加了FIFO操 作的复杂度，并且在某些实施例中可能不是有利的。

已呈现了前述说明，以使得本领域普通技术人员能够如在特定应用及其 要求的上下文内所提供的那样实行和使用本发明。尽管已参考本发明的特定 优选版本相当详细地说明了本发明，但还可进行并考虑其它版本和变化。针 对优选实施例的各种变形对于本领域技术人员而言将是显而易见的，并且这 里所定义的一般原理还可应用于其它实施例。例如，可以以包括逻辑装置或 电路等的任何适当方式实现这里所述的电路。尽管利用TLB阵列等例示了本 发明，但这些概念等同地适用于以与第二高速缓存器阵列不同的方式对第一 高速缓存器阵列进行编索引的任何多级高速缓存方案。不同的编索引方案提 高了高速缓存器的组和路的利用率，并由此提高了性能。

本领域技术人员应当理解，在没有背离本发明的精神和范围的情况下， 这些技术人员可以容易地使用所公开的概念和具体实施例作为用于设计或 修改用于执行本发明的相同目的的其它结构的基础。因此，本发明并不意图 局限于这里所示和所述的特定实施例，而是应当符合与这里所公开的原理和 新颖特征一致的最宽范围。