CN109564550B - 更新最近最少使用的数据以获得更高普遍性的高速缓存条目的更大持久性 - Google Patents

Abstract

公开了一种用于改进转换后备缓冲器(TLB)操作的技术。所述TLB的特定条目将用与大页大小相关联的数据来更新。所述TLB更新用于所述大页大小的所述TLB条目的替换策略数据，以指示所述TLB条目不是最近最少使用的。为了防止较小的页清除所述大页大小的所述TLB条目，所述TLB还更新用于所述较小的页大小的所述TLB条目的替换策略数据以指示所述TLB条目不是最近最少使用的。

Description

更新最近最少使用的数据以获得更高普遍性的高速缓存条目 的更大持久性

相关申请的交叉引用

本申请要求2016年8月12日提交的美国申请号15/235,214的权益，所述申请的内容通过引用的方式并入本文，如同完整阐述一样。

背景技术

转换后备缓冲器(“TLB”)是存储用于对存储器系统进行寻址的虚拟到物理地址转换的高速缓存。TLB可使计算机操作加速，因为大量操作参考使用虚拟地址的存储器。在没有TLB的情况下，此类操作将需要访问主系统存储器以便获得转换，从而引起大量延迟。因此，TLB操作的改进可提高计算机操作的速度。

附图说明

从以下结合附图通过举例给出的描述中可得到更详细的理解，在附图中：

图1是其中可实现一个或多个所公开实施例的示例性装置的框图；

图2是根据一个示例的处理器-存储器接口系统的框图；

图3是根据一个示例的转换后备缓冲器的框图；

图4是示出了根据一个示例的用于在高速缓存未命中的情况下修改最近最少使用的数据的操作的框图；并且

图5是根据一个示例的用于更新转换后备缓冲器的最近最少使用的数据的方法的流程图。

具体实施方式

本公开涉及用于改进转换后备缓冲器(“TLB”)的操作的技术。当要使用与大页大小相关联的数据更新TLB的特定条目时，TLB更新用于所述大页大小的所述TLB条目的替换策略数据(诸如最近最少使用(“LRU”)数据)，以指示TLB条目不是最近最少使用的。为了防止较小的页清除大页大小的TLB条目，TLB还更新用于较小页大小的所述TLB条目的替换策略数据以指示TLB条目不是最近最少使用的。

调整较小页大小的LRU数据以指示经修改的TLB条目不是这些页大小的最近最少使用条目有助于防止较小存储页的TLB条目清除较大页大小的TLB条目。因此，大页的转换比小页的转换更“持久”。较大页的转换服务于系统存储器的较大部分。因此，使较大页的转换更持久有助于允许TLB在任何给定时间服务于系统存储器的较大部分，这减少了TLB中发生的未命中的数量，并且减少了与从页表中获取转换相关联的总延迟。这通常还提高了使用虚拟地址的TLB和存储器操作的整体速度和性能。

图1是其中实现本公开的各方面的示例性装置100的框图。装置100包括例如计算机、游戏装置、手持装置、机顶盒、电视、移动电话或平板计算机。装置100包括处理器102、存储器104、存储装置106、一个或多个输入装置108、以及一个或多个输出装置110。装置100还可任选地包括输入驱动器112和输出驱动器114。应理解，装置100可包括图1中未示出的额外部件。

处理器102包括中央处理单元(CPU)、图形处理单元(GPU)、位于同一管芯上的CPU和GPU，或者一个或多个处理器内核，其中每个处理器内核可为CPU或GPU。存储器104可与处理器102位于同一管芯上，或者可与处理器102分开定位。存储器104包括易失性或非易失性存储器，例如随机存取存储器(RAM)、动态RAM或高速缓存。

存储装置106包括固定或可移除存储装置，例如硬盘驱动器、固态驱动器、光盘或闪存驱动器。输入装置108包括键盘、小键盘、触摸屏、触摸板、检测器、麦克风、加速度计、陀螺仪、生物特征扫描器或网络连接(例如，用于发射和/或接收无线IEEE 802信号的无线局域网卡)。输出装置110包括显示器、扬声器、打印机、触觉反馈装置、一个或多个灯、天线或网络连接(例如，用于发射和/或接收无线IEEE 802信号的无线局域网卡)。

输入驱动器112与处理器102和输入装置108通信，并且允许处理器102从输入装置108接收输入。输出驱动器114与处理器102和输出装置110通信，并且允许处理器102将输出发送到输出装置110。应注意，输入驱动器112和输出驱动器114是可选部件，并且如果输入驱动器112和输出驱动器114不存在，则装置100将以相同方式操作。

图2是示出了根据一个示例的处理器-存储器接口系统200的各方面的框图。如图所示，处理器-存储器接口系统200包括图1的处理器102和图1的存储器104。

处理器102包括内核202，所述内核执行用于处理数据的指令。处理器102还包括耦合到转换后备缓冲器(TLB)206的存储器管理单元(MMU)204。由处理器102执行的指令可经由物理地址(通常与操作系统操作相关联)或虚拟地址(通常与用户模式应用程序相关联)来查阅存储器。使用用于应用程序的虚拟地址空间将此类应用隔离，从而通过写入到与这些应用程序或操作系统相关联的存储器来防止所述应用程序意外干扰其他应用程序或操作系统的操作。

为了便于经由虚拟地址访问存储器104，处理器102包括MMU 204。MMU 204将从核心202接收的虚拟地址转换成物理地址，并且经由这些物理地址来访问存储器104。指示如何将虚拟地址转换成物理地址的数据被存储在存储器104中的页表208中。地址不会向下转换成字节或字词，而是向下转换成页码。更具体地，页表208将包括用于表示单个页的地址的足够数量的最高有效位的虚拟页码转换成物理页码。地址的最低有效位不被转换，并且在物理地址和虚拟地址两者中是相同的。

TLB 206充当页表208的高速缓存。在没有TLB 206的情况下，每个虚拟存储器地址查找都将需要访问系统存储器104，从而增加了存储器访问延迟。由TLB 206提供的高速缓存有助于减少此延迟。然而，TLB 206通常不包括页表208中的所有转换的完整副本。在操作中，作为执行存储器访问指令的一部分，内核202请求从MMU 204转换虚拟存储器地址。作为响应，MMU 204对TLB 206进行搜索以获得转换。在高速缓存命中(意味着TLB 206包括转换)的情况下，MMU 204从转换获得物理地址，并且使用所获得的物理地址向存储器104发送存储器访问请求。在高速缓存未命中的情况下(意味着TLB 206不包括转换)，MMU 204执行页表遍历，从而对页表208进行搜索以获得所需转换。MMU 204随后将所述转换置于TLB 206中，从而在TLB 206中存在的空间不足的情况下清除另一条目。MMU 204基于最近获得的转换来执行存储器访问。

带来困难的地址转换的一个方面是不同页大小的可能性。更具体地，在存储器104中存储有不同大小的存储页的选项引起了如何在TLB 206中高速缓存不同大小的页的转换的问题。

图3是根据一个示例的转换后备缓冲器(TLB)300的框图。如图所示，TLB 300被实现为斜相联高速缓存，其适用于高性能地用作用于存储不同页大小的页的转换的页表208的高速缓存。图3所示的示例性TLB 300包括四个路304和七个组，七行最近最少使用(“LRU”)数据，以及每个LRU数据行四个LRU条目。示出了示例性地址302。示例性TLB 300是图2所示的TLB 206的示例。示例性虚拟地址302包括索引314、标签310和选择位312，并且还与特定页大小308相关联。页大小308指示在虚拟地址302处存储数据的存储页的大小。

斜相联高速缓存是组相联高速缓存的变型，其允许减少高速缓存未命中的机会。高速缓存响应于查找而提供有效载荷数据。对于各种类型的高速缓存(包括组相联高速缓存)，地址的高速缓存索引部分用于识别高速缓存中可存储具有所述索引的地址的数据的条目。在直接映射的高速缓存中，高速缓存索引唯一地识别高速缓存中的单个条目。因此，在直接映射的高速缓存中，用于任何特定地址的条目仅可存储在单个高速缓存条目中。在全相联高速缓存(fully-associative cache)中，每个地址都可存储在任何高速缓存条目中。在组相联高速缓存(set-associative cache)中，任何特定的高速缓存索引值都可映射到高速缓存中的数量n的条目，其中n大于1并且小于高速缓存的大小(n＝1高速缓存是直接映射的高速缓存并且n＝高速缓存大小的高速缓存是全相联高速缓存)。在组相联高速缓存中，高速缓存索引映射到特定组，其中每个组包括多个高速缓存条目。整个高速缓存也被分成n个“存储组”(也称为“路”)。组相联高速缓存中的特定高速缓存条目由组号和存储组(“路”)号的特定组合来识别。

斜相联高速缓存(skewed associative cache)是对组相联高速缓存的修改，其中针对不同的路，组的选择是不同的。TLB 300被实现为斜相联高速缓存。因此，在TLB 300中，任何特定地址可以不同方式映射到不同组。

此外，斜相联TLB 300适应不同大小的页的转换。更具体地，每个路304中的每个条目可存储每个可能页大小的转换。每个虚拟地址在每个路304中具有可能且唯一的映射位置。然而，每个地址和页大小组合无法存储在每个路304中。可存储特定地址的路304由页大小函数来确定。页大小函数定义如下。对于TLB 300的任何给定路I并且对于任何给定的虚拟地址A，当且仅当虚拟页的大小为S(A,I)时，包括虚拟地址A的页P(A)可映射在路I上，其中S(A,I)是页大小函数。换句话说，页大小函数为每个虚拟地址和页大小组合指示虚拟地址可映射到的路。页大小函数基于虚拟地址302的选择位312生成结果。可使用任何技术上可行的页大小函数的实现方式。

页大小函数的功能也可由选择函数Sel(A)表示。选择函数为任何给定地址生成单个数值。由选择函数生成的数值指示哪些页大小映射到哪些路。在图3的示例性TLB 300中，TLB 300包括四个路。两个路(路0和路1)一起分组在第一组316(1)中，并且另外两个路(路2和路3)一起分组在第二群组316(2)中。此外，TLB 300被配置成存储两种不同大小的页的转换。选择函数的值0指示第一路群组316(1)存储第一大小的页，并且第二路群组316(2)存储第二大小的页。选择函数的值1指示第一路群组316(1)存储第二大小的页，并且第二路群组316(2)存储第一大小的页。如图3所示，在一种方法中，页大小函数(以及因此选择函数)基于虚拟地址302的映射位。在一个示例性选择函数中，不同的选择位312被分配给不同的选择值。在一个示例中，地址具有三个选择位312。值000、001、010和011被分配给选择值0。值100、101、110和111被分配给选择值1。可使用任何其他技术上可行的选择函数(或页大小函数)。

适用于任何特定地址和页大小的组是基于索引函数确定的。更具体地，索引函数接受地址、页大小和页大小函数的输出作为输入，并且输出用于其中可存储地址和页大小组合的每个路的特定组。在图3的示例中，索引函数接受虚拟地址302的索引部分314、页大小308和选择功能的输出(其基于虚拟地址302的选择位312)作为输入，并且输出用于其中可存储地址的每个路的组号。在一个示例中，索引函数在路群组316中为每个组输出相同的组(其中，如上所述，路群组316包括为了页选择目的而被分组在一起的路304)。

如上所述，MMU 204使用TLB 300以通过基于虚拟地址302和页大小索引TLB 300来将虚拟地址302转换成物理地址。由于TLB 300的斜相联性质，对于任何特定虚拟地址和页大小组合，TLB 300包括可存储所述虚拟地址/页大小组合的多个路。因此，为了尝试转换虚拟地址302，MMU 204基于索引函数来识别组，并且基于页大小函数来识别多个可能的路。MMU 204尝试将地址302的标签部分310与所识别的组和路中的一个条目的标签310进行匹配。如果标签310在一个条目中匹配，则发生命中，并且如果标签310不匹配，则发生未命中。

在未命中的情况下，MMU 204从页表208请求与虚拟地址302相关联的转换，并且将接收的转换置于TLB 300的TLB条目301中的一个中。MMU 204基于地址302、页大小308和替换策略来确定将转换置于哪个TLB条目301中，所述替换策略检查最近最少使用(“LRU”)数据306。

对于任何特定地址和页大小组合，所述地址的条目可存储在多于一个路304中。为了确定将所提取的转换存储在哪个路304中，MMU 204查询LRU数据306。LRU数据306包括用于每个选择值/页大小组合的LRU条目308。在图3的示例性TLB 300中，对于选择值0/大小1组合存在一个LRU条目308，对于选择值0/大小2组合存在一个LRU条目308，对于选择值1/大小1组合存在一个LRU条目308，并且对于选择值1/大小2组合存在一个LRU条目308。在具有更多页大小的TLB中，将包括额外的LRU条目。

对于选择值/页大小组合，每个LRU条目308指示可存储所述特定选择值/页大小组合的转换的路中的哪个路304被认为是最近最少使用的路。例如，对于选择值为0和页大小为1(并且对于组1)，LRU条目308(1)指示路0或路1是否存储被认为是最近最少使用的条目301的条目301。类似地，对于选择值为1和页大小为2，LRU条目308(4)指示路0或路1是否存储被认为是最近最少使用的条目301的条目301。

应注意，以上假设索引函数，对于任何特定路群组316，所述索引函数将任何特定地址映射到具有所述路群组316的相同组。术语“路群组”316是指路304的集合，对于所述路的集合，任何特定的虚拟地址映射到同一组。在图3中，存在两个路群组316。第一路群组316包括路0和路1，并且第二路群组316包括路2和路3。

“路群组”316的概念允许LRU数据以每个选择值/页大小为基础来进行存储。更具体地，所述概念允许一旦MMU 204确定特定地址/页大小组合可映射到哪个路群组316，就在不同路之间进行有意义的比较。在一个示例中，一旦MMU 204已确定特定地址/页大小组合属于由路0和路1组成的路群组316，则路304的分组意味着对应的LRU条目308允许MMU 204将路群组316中的一个路识别为最近最少使用的路。

在替换算法的一个示例中，每个路群组316包括两个路304。LRU数据306包括每组一个LRU条目308、选择函数值和页大小组合。每个LRU条目308是一个位。对于特定页大小，所述位指示特定路群组316中的两个路中的哪一个存储最近最少使用的TLB条目，并且因此当MMU 204将新提取的转换写入到TLB时替换哪一个。在一个示例中，与第一组相关联的具有第一路群组316(路0和路1)并且具有第一页大小的条目指示路0存储最近最少使用的TLB条目。与同一路组和路群组316(路0和路1)相关联并且具有第二页大小的条目指示路1存储最近最少使用的TLB条目。这些特定值意味着路群组316内的替换将根据要转换的地址是在第一页大小的存储页内还是在第二页大小的存储页内而不同地发生。

尽管本文描述了特定的LRU替换策略，但是其他替换策略也是可能的。例如，可使用利用伪LRU(“PLRU”)、树-pLRU等替换算法。此外，替换算法可用在其中路群组316包括多于两个路304的情境中。在这种情况下，每个LRU数据条目可存储多于一个位。

大页和小页两者都可存储在任何特定路304中的事实意味着小页可替换大页。此外，LRU数据以每个页大小为基础存储的事实意味着一个页大小的替换数据可能指示应替换特定TLB条目，而另一个页大小的替换数据可能指示应替换不同的TLB条目。这种可能性意味着小页的转换可能导致清除大页的转换，在此情况下，发生这种清除是不利的。

在一个示例中，MMU 204在组1、路0中写入小页大小的TLB条目，并且更新对应的LRU条目以指示对于小页并且在组1中，在路0和路1中，路1是最近最少使用的。随后，MMU204在组1、路1中写入用于大页大小的TLB条目，并且更新对应的LRU条目以指示对于大页大小和组1，在路0和路1中，路0是至少最近使用过的。随后，MMU 204将用于小页大小的TLB条目写入到组1中。基于LRU数据，MMU 204确定在组1中并且对于小页，在路0和路1中，路1是最近最少使用的。因此，MMU 204将用于小页大小的TLB条目写入组1、路1中。然而，此动作会导致用于大页的新添加的TLB条目被清除，所述大页被存储在组1、路1中。

实际上，小页的新转换已清除大页的新转换。此操作是不期望的，因为大页的转换应优先于小页的转换。更具体地，因为大页的转换比小页的转换覆盖了更多的系统存储器，所以清除大页的转换以添加小页的转换具有减少TLB可服务的系统存储器的部分从而增加了在TLB中发生未命中的可能性的效果。当要将小页的转换写入到TLB时，需要将所述转换存储在某处。然而，将所述转换存储在不是最近最少使用的大页大小的条目的TLB条目中会导致清除大页大小的转换，与大页大小最近最少使用的条目相比，这被认为(至少从最近最少使用的替换语义的角度来看)更具相关性。出于这些原因，下面提供了额外的替换算法技术。

图4是示出了根据一个示例的用于在高速缓存未命中的情况下修改LRU数据的操作的框图。如图所示，图4示出了第一操作400、第二操作410、第三操作420和第四操作430。

第一操作、第二操作、第三操作和第四操作示出了用于以允许LRU中的较大页的转换与较小页的转换相比更加持久的方式来修改LRU数据的技术。通常，这些操作涉及在更新较大大小页的LRU数据时更新较小大小页的LRU数据。更具体地，当MMU 204确定要将大页的转换置于TLB中时，MMU 204更新所述大页的LRU数据条目308以及对应的小页的LRU数据条目308两者。更具体地，在检测到大尺寸页内的地址的高速缓存未命中时，MMU 204识别在其中放置所述大页的转换的特定TLB条目。应注意，此TLB条目由特定组和路来限定。MMU 204将转换置于所述TLB条目中并且更新对应的LRU数据以指示最近更新的TLB条目不包含最近最少使用的数据。此更新的LRU数据由选择值、组和页大小定义。此外，MMU 204更新用于同一TLB条目(由组和选择值定义)以及用于较小页大小的LRU数据，以指示同一TLB条目不是最近最少使用的条目。对较小页大小的这种额外更新具有防止对较小页大小的相同的路群组316的后续更新会清除最近添加的用于大页大小的转换的效果。

实际上，此额外更新操作会导致较大页大小的转换比未发生此额外更新操作的情况更持久。较大页的转换服务于系统存储器的较大部分。因此，使较大页的转换更持久有助于允许TLB 300在任何给定时间服务于系统存储器的较大部分，这减少了TLB 300中发生的未命中的数量，从而减少了与从页表208中获取转换相关联的总延迟，并且提高了TLB 300以及通常使用虚拟地址的存储器操作的整体速度和性能。

图4中所示的操作是上述技术的示例。图4中的每个操作示出了TLB的几个组，分组成两个路群组316(0、1和2、3)的四个路，以及用于第一组的LRU数据。为简单起见，未示出用于除第一组之外的任何组的LRU数据，但应理解每个组将具有对应的LRU数据。

在第一操作400中，MMU 204已开始处理页大小4K的页内的地址的转换(在所述示例中，4K是小页大小，并且2MB是大页大小)。MMU 204还确定TLB中发生未命中、已从页表208接收到转换、已基于地址将选择值计算为0、已识别出与选择值0和4K页大小匹配的路、并且已基于地址和页大小函数识别出组(图中最顶部的组)。MMU 204还已识别路群组316(包括0和1)，其中存储新接收的转换，并且已基于LRU数据306识别其中存储转换的一个路。所识别的路是路0。因此，MMU 204已确定新接收的转换将被存储在组1和路0处发现的TLB条目中，即标记有数字“1”的TLB条目。响应于所述确定，MMU 204更新LRU数据306。具体地，MMU 204更新LRU数据条目308以获得选择值0、页大小4K、以及组1，以指示最近最少使用的TLB条目是TLB条目2。因为4K是最小页大小，所以MMU 204不更新任何其他LRU数据。

除了选择值是1之外，第二操作(操作410)类似于操作400。页大小仍为4K。因为选择值是1，所以提取的转换会替换路2和路3中的一个中的TLB条目(具体地，路2中的TLB条目3)而不是路0和路1中的一个中的TLB条目。如同操作400，因为页大小是4K，所以MMU 204不更新任何其他LRU数据。

第三操作(操作420)是其中用于转换的地址是大尺寸(2MB)页中的地址的操作。在TLB中发生未命中，并且MMU 204从页表208获得转换。MMU 204处理所述地址并且确定选择值为0。MMU 204检查LRU数据306并且确定存储最近接收的转换的TLB条目是标记为3的TLB条目。在确定哪个TLB条目存储从页表208中检索的转换之后，MMU 204更新LRU数据306以便获得选择值和页大小组合。更具体地，MMU 204更新对应于选择值0和页大小2M的LRU数据条目308，以指示标记为4的TLB条目是最近最少使用的条目(因为条目3刚被写入)。此外，因为所提取的地址是用于具有大页大小的存储页中的地址，所以MMU 204更新LRU数据条目308，其对应于相同的路群组316但是用于较小的页大小。所述LRU数据条目是用于选择值1和页大小4K的数据条目。MMU 204更新所述LRU数据条目以还指示TLB条目4是最近最少使用的。更新用于此较小大小页的LRU数据条目有助于防止用于相同路的组的TLB未命中清除刚写入的大页大小的TLB条目。

除了第四操作的地址评估选择值1而不是选择值0之外，第四操作430类似于第三操作420。因此，代替更新选择0/2MB和选择1/4K，MMU 204更新选择0/4K和选择1/2MB。

仅为简单起见，索引函数被示出为在每个操作中评估组1；索引函数可评估任何组。虽然在图3和图4中仅示出了两个路群组(每群组两个路)以及两种页大小，但是本文描述的技术可应用于具有不同数量的路群组的TLB、每群组不同数量的路以及不同数量的页大小。对于更多页大小，每个大小具有相关联的路群组。当MMU 204由于提取对应TLB条目的转换而更新特定页大小的LRU数据时，MMU204还更新每个较小页大小的LRU数据，以指示接收到新检索的转换的TLB条目不是最近最少使用的。

图5是根据一个示例的用于更新转换后备缓冲器的最近最少使用的数据的方法500的流程图。尽管关于图1-图4所示和所述的系统进行了描述，但是应理解，被配置成以任何技术上可行的顺序执行所述方法的任何系统都落入本公开的范围内。

如图所示，方法500开始于步骤502处，其中MMU 204检测由于TLB 300中不存在虚拟到物理转换而导致的TLB 300中的未命中。MMU 204从页表208中提取所请求的转换。在步骤504处，MMU 204确定用于转换的虚拟地址的页大小。可从页表208或一组配置寄存器(诸如但不限于，x86架构中存在的存储器类型范围寄存器)中检索用于任何特定地址的页大小信息。MMU 204还基于页大小函数并且基于地址来计算选择值。所述选择值指示将哪个路群组316分配给哪个页大小。

在步骤506处，MMU 204基于页大小、选择值、地址和LRU数据来识别TLB中用于存储地址转换的组和路。更具体地，MMU 204基于页大小函数和页大小来识别可存储转换的可能的路、基于用于所识别的路的索引函数来计算索引结果以确定其中可放置转换的组，并且基于LRU数据在其中存储转换的所识别的组中识别特定路。例如，如果LRU数据指示所识别的路和所识别的组的特定TLB条目是最近最少使用的路，则MMU 204将所述TLB条目识别为将新获得的转换置于其中的条目。

在步骤508处，MMU 204将转换存储在所识别的组和路中，并且更新用于所识别的组、选择值和页大小的LRU数据。如上所述，针对每个组并且针对每个选择值和页大小组合，存在LRU数据。LRU数据指示所识别的组中以及(基于选择值和页大小识别的)适当的路群组316中的哪个TLB条目存储最近最少使用的数据。MMU 204更新用于组/选择值/页大小的LRU数据，以指示在适当的路群组316内和在除了更新的TLB条目之外的所识别的组内的TLB条目存储最近最少使用的数据。在一个示例中，每个路群组316包括两个路。如果在步骤508中更新一个路中的条目，则MMU 204更新LRU数据以指示所述路群组316中的另一个路是最近最少使用的。在其他示例中，每个路群组316包括多于两个路。在这种情况下，MMU 204更新LRU数据以指示在与更新的TLB条目相同的路组和路群组316中的其他TLB条目包括比更新的TLB条目最近更少使用的数据。

在步骤510处，响应于更新用于特定组/选择值/页大小组合的LRU数据，MMU 204还更新用于同一组但是用于不同的页大小/选择值组合的LRU数据。更具体地，MMU 204更新用于与更新的LRU数据相同的组并且用于与在步骤508处更新LRU数据的路群组316匹配的每个页大小/选择值组合的LRU数据。对于小于在步骤508处修改TLB条目的页大小的每个页大小，MMU 204更新这种LRU数据以指示在步骤508处更新的TLB条目不是最近最少使用的TLB条目。更新此类较小页大小的LRU数据有助于使较大页大小的TLB条目比较小页的TLB条目更持久。

本文描述的技术改进了TLB的操作。更具体地，调整较小页大小的LRU数据以指示经修改的TLB条目不是这些页大小的最近最少使用条目有助于防止较小存储页的TLB条目清除较大存储页的TLB条目。因此，大页的转换比小页的转换更“持久”。较大页的转换服务于系统存储器的较大部分。因此，使较大页的转换更持久有助于允许TLB 300在任何给定时间服务于系统存储器的较大部分，这减少了TLB 300中发生的未命中的量，从而减少了与从页表208中获取转换相关联的总延迟，并且提高了TLB 300以及通常使用虚拟地址的存储器操作的整体速度和性能。

尽管在斜相联高速缓存的上下文中进行了描述，但是以上提供的技术也可应用于组相联高速缓存。如上所述，这种组相联高速缓存中的路仍将被分组成路群组316，其中每个路群组316将基于取决于地址的选择函数(或页大小函数)来选择，但是这种组相联高速缓存将不会表现出相同地址映射到不同路群组316中的不同组的斜相联特性。相反，地址将映射到每个路群组316中的相同组。用于组相联高速缓存的LRU数据将以与上述类似的方式来存储。

此外，尽管在计算机系统的标准MMU中的转换后备缓冲器的上下文中进行了描述，但是以上提供的技术可用于其他MMU，诸如输入/输出MMU，其为输入输出装置而不是为诸如CPU等处理器提供地址转换服务。此外，上述技术也可应用于除TLB之外的高速缓存，只要高速缓存将不同级别通用性的地址转换进行高速缓存即可。例如，上述技术可在存储用于互联网协议地址的不同部分的互联网协议地址转换的高速缓存中使用(例如，XXX.XXX.______对XXX.XXX.XXX.______--表示一类IP地址对另一类IP地址(例如，A类对B类))。术语“通用性级别”是指由特定高速缓存条目覆盖的地址空间的部分。对于TLB，“更高级别的通用性”对应于较大页大小的转换，并且“更小级别的通用性”(或“更具体级别的通用性”)对应于较小页大小的转换。对于IP地址转换，较小IP地址部分的转换(因此覆盖更多的总IP地址)将具有比较大IP地址部分的转换更高级别的通用性。在任何实现方式中，上述教导规定，当更新具有更高级别的通用性的高速缓存条目的替换策略数据时，还对具有较小级别的通用性的相同高速缓存条目的替换策略数据进行类似的更新。对于不是TLB的任何高速缓存实现方式，可认为MMU的操作由管理这种高速缓存的高速缓存控制器来执行。

尽管以上提供了一些示例性LRU机制，但是LRU机制可为任何技术上可行的LRU技术(或者甚至是非LRU替换技术)。此外，可使用任何技术上可行的页大小函数、选择函数和索引函数。

本文公开了一种用于更新包括转换后备缓冲器的高速缓存的替换策略数据的方法。检测对高速缓存的第一高速缓存条目的更新。检测对应于第一高速缓存条目的第一替换策略数据条目的第一修改，第一替换策略数据条目与第一页大小相关联。识别与小于第一页大小的第二页大小相关联的第二替换策略数据条目，第二替换策略数据条目也与第一高速缓存条目相关联。对第二替换策略数据条目进行第一修改。

在一些示例中，第一高速缓存条目被配置成存储从虚拟地址到物理地址的转换。在一些示例中，高速缓存包括被分组成多个路群组的多个路，第一替换策略数据条目存储包括第一高速缓存条目的路群组中的第一路群组的替换策略数据，并且第二替换策略数据条目存储第一路群组的替换策略数据。

在一些示例中，第一高速缓存条目存储第一存储页的转换，并且第一存储页映射到高速缓存在第一路群组中的第一组，并且映射到高速缓存在多个路群组中的第二路群组中的第二组，第二组是与第一组不同的组。在一些示例中，所述方法还包括检测高速缓存中的未命中，响应于未命中来提取要置于高速缓存中的项目，基于与项目相关联的地址并且基于与所述项目相关联的页大小来识别所述项目的路组和路群组，并且基于第一替换策略数据条目来识别路群组中的路。对所识别的路、组和路群组执行对高速缓存的第一高速缓存条目的更新。在一些示例中，识别路群组中的路包括确定第一替换策略数据条目指示所述路群组中的路存储与所述项目相关联的页大小的最近最少使用的高速缓存条目。

在一些示例中，第一替换策略数据条目包括一个位，所述位指示所述路群组中的哪个路包括最近最少使用的数据。在一些示例中，所述方法还包括检测对高速缓存的第二高速缓存条目的第二更新，检测对应于第二高速缓存条目的第三替换策略数据条目的第二修改，第三替换策略数据条目与第二页大小相关联，并且确定第二页大小是高速缓存中的数据的最小页大小，其中响应于第三替换策略数据条目与高速缓存中的数据的最小页大小相关联而不修改其他替换数据。

本文还提供高速缓存。高速缓存包括存储高速缓存数据的高速缓存存储器，所述高速缓存存储器包括转换后备缓冲器、存储替换策略数据的替换策略存储器、以及高速缓存控制器。高速缓存控制器被配置成检测对高速缓存存储器的第一高速缓存条目的更新，检测对应于第一高速缓存条目的第一替换策略数据条目的第一修改，第一替换策略数据条目与第一页大小相关联，识别与小于第一页大小的第二页大小相关联的第二替换策略数据条目，第二替换策略数据条目也与第一高速缓存条目相关联，并且对第二替换策略数据条目进行第一修改。

在一些示例中，第一高速缓存条目被配置成存储从虚拟地址到物理地址的转换。在一些示例中，高速缓存包括被分组成多个路群组的多个路，第一替换策略数据条目存储包括第一高速缓存条目的路群组中的第一路群组的替换策略数据，并且第二替换策略数据条目存储第一路群组的替换策略数据。

在一些示例中，第一高速缓存条目存储第一存储页的转换，并且第一存储页映射到高速缓存在第一路群组中的第一组，并且映射到高速缓存在多个路群组中的第二路群组中的第二组，第二组是与第一组不同的组。在一些示例中，高速缓存控制器还被配置成检测高速缓存中的未命中，响应于未命中来提取要置于高速缓存中的项目，基于与项目相关联的地址并且基于与所述项目相关联的页大小来识别用于所述项目的路组和路群组，并且基于第一替换策略数据条目来识别路群组中的路。对所识别的路、组和路群组执行对高速缓存的第一高速缓存条目的更新。在一些示例中，识别路群组中的路包括确定第一替换策略数据条目指示所述路群组中的路存储与所述项目相关联的页大小的最近最少使用的高速缓存条目。

在一些示例中，第一替换策略数据条目包括一个位，所述位指示所述路群组中的哪个路包括最近最少使用的数据。在一些示例中，高速缓存控制器还被配置成检测对高速缓存的第二高速缓存条目的第二更新，检测对应于第二高速缓存条目的第三替换策略数据条目的第二修改，第三替换策略数据条目与第二页大小相关联，并且确定第二页大小是高速缓存中的数据的最小页大小，其中响应于第三替换策略数据条目与高速缓存中的数据的最小页大小相关联而不修改其他替换数据。

还提供了一种处理器，其包括被配置成执行指令的执行流水线以及包括存储高速缓存数据的高速缓存存储器的高速缓存，所述高速缓存存储器包括用于将指令的虚拟存储器地址转换成物理存储器地址的转换后备缓冲器、存储替换策略数据的替换策略存储器以及高速缓存控制器。高速缓存控制器被配置成检测对高速缓存存储器的第一高速缓存条目的更新，检测对应于第一高速缓存条目的第一替换策略数据条目的第一修改，第一替换策略数据条目与第一页大小相关联，识别与小于第一页大小的第二页大小相关联的第二替换策略数据条目，第二替换策略数据条目也与第一高速缓存条目相关联，并且对第二替换策略数据条目进行第一修改。

在一些示例中，第一高速缓存条目被配置成存储从虚拟地址到物理地址的转换。在一些示例中，高速缓存包括被分组成多个路群组的多个路，第一替换策略数据条目存储路群组中的包括第一高速缓存条目的第一路群组的替换策略数据，并且第二替换策略数据条目存储第一路群组的替换策略数据。在一些示例中，第一高速缓存条目存储第一存储页的转换，并且第一存储页映射到高速缓存在第一路群组中的第一组，并且映射到高速缓存在多个路群组中的第二路群组中的第二组，第二组是与第一组不同的组。

应理解，基于本文的公开内容，许多变化是可能的。尽管上面以特定组合描述了特征和元件，但是每个特征或元件可在不具有其他特征和元件的情况下单独使用，或者在具有或不具有其他特征和元件的情况下以各种组合使用。

所提供的方法可在通用计算机、处理器或处理器内核中实现。通过举例，合适的处理器包括通用处理器、专用处理器、常规处理器、数字信号处理器(DSP)、多个微处理器、与DSP内核相关联的一个或多个微处理器、控制器、微控制器、专用集成电路(ASIC)、现场可编程门阵列(FPGA)电路、任何其他类型的集成电路(IC)和/或状态机。可通过使用处理的硬件描述语言(HDL)指令和包括网表的其他中间数据的结果配置制造过程来制造这种处理器(这种指令能够存储在计算机可读介质上)。这种处理的结果可为掩膜件，所述掩膜件随后在半导体制造工艺中用来制造实现所述实施例的各方面的处理器。

本文提供的方法或流程图可在计算机程序、软件或固件中实现，所述计算机程序、软件或固件并入在非暂时性计算机可读存储介质中，以供通用计算机或处理器来执行。非暂时性计算机可读存储介质的示例包括只读存储器(ROM)、随机存取存储器(RAM)、寄存器、高速缓冲存储器、半导体存储器装置、诸如内部硬盘和可移除磁盘等磁介质、磁光介质以及诸如CD-ROM盘和数字多功能磁盘(DVD)等光学介质。

Claims (17)

1.一种用于更新存储从第一地址空间到第二地址空间的转换的高速缓存的替换策略数据的方法，所述高速缓存包括多个集合，每个集合包括被分成多个缓存路组的多个缓存路，所述方法包括：

检测对所述高速缓存的第一高速缓存条目的更新，所述高速缓存的所述第一高速缓存条目与所述多个集合中的第一集合相关联，并且与所述多个缓存路组中的第一组缓存路相关联；

响应于对所述第一高速缓存条目的所述更新，修改对应于所述第一高速缓存条目和所述第一组缓存路的第一替换策略数据条目，所述第一替换策略数据条目与第一级别的通用性相关联，所述修改致使所述第一替换策略数据条目指示所述高速缓存的所述第一高速缓存条目对于所述第一级别的通用性不是最近最少使用的；

响应于所述修改所述第一替换策略数据条目，识别与第二级别的通用性相关联的第二替换策略数据条目，所述第二级别的通用性比所述第一级别的通用性更具体，所述第二替换策略数据条目也与所述第一高速缓存条目相关联并且与所述第一组缓存路相关联；以及

修改所述第二替换策略数据条目以还指示所述高速缓存的所述第一高速缓存条目对于所述第二级别的通用性不是最近最少使用的。

2.如权利要求1所述的方法，其中所述第一高速缓存条目被配置成存储从虚拟地址到物理地址的转换。

3.如权利要求1所述的方法，其中：

所述第一高速缓存条目存储第一存储页面的转换，并且

所述第一存储页面映射到所述第一组缓存路中的所述高速缓存的第一集合，并且映射到所述多个缓存路组中的第二组缓存路中的所述高速缓存中的第二集合，所述第二集合是与所述第一集合不同的集合。

4.如权利要求1所述的方法，其还包括：

检测所述高速缓存中的未命中；

响应于所述未命中来获取将要置于所述高速缓存的所述第一高速缓存条目中的项目；

基于与所述项目相关联的地址并且基于与所述项目相关联的所述第一级别的通用性来识别用于所述项目的所述第一集合和所述第一组缓存路；以及

基于所述第一替换策略数据条目来识别所述缓存路组中的缓存路，

其中对所述识别的缓存路、所述集合和所述缓存路组执行对所述高速缓存的所述第一高速缓存条目的所述更新。

5.如权利要求4所述的方法，其中识别所述缓存路组中的所述缓存路包括：

确定所述第一替换策略数据条目指示所述缓存路组中的所述缓存路存储用于与所述项目相关联的页面大小的最近最少使用的高速缓存条目。

6.如权利要求4所述的方法，其中：

所述第一替换策略数据条目包括一位，所述一位指示所述缓存路组中的哪个缓存路包括最近最少使用的数据。

7.如权利要求1所述的方法，其还包括：

检测对所述高速缓存的第二高速缓存条目的第二更新；

检测对与所述第二高速缓存条目对应的第三替换策略数据条目的第二修改，所述第三替换策略数据条目与所述第二级别的通用性相关联；以及

确定第二页面大小是用于所述高速缓存中的数据的最具体级别的通用性，

其中响应于所述第三替换策略数据条目与用于所述高速缓存中的数据的所述最具体级别的通用性相关联而不修改其他替换数据。

8.一种高速缓存，其被配置成存储从第一地址空间到第二地址空间的转换，所述高速缓存包括多个集合，每个集合包括被分成多个缓存路组的多个缓存路，所述高速缓存包括：

高速缓存存储器，所述高速缓存存储器存储高速缓存数据；

替换策略存储器，所述替换策略存储器存储替换策略数据；以及

高速缓存控制器，所述高速缓存控制器被配置成：

检测对所述高速缓存存储器的第一高速缓存条目的更新，所述高速缓存的所述第一高速缓存条目与所述多个集合中的第一集合相关联，并且与所述多个缓存路组中的第一组缓存路相关联；

响应于对所述第一高速缓存条目的所述更新，修改对应于所述第一高速缓存条目和所述第一组缓存路的第一替换策略数据条目，所述第一替换策略数据条目与第一级别的通用性相关联，所述修改致使所述第一替换策略数据条目指示所述高速缓存的所述第一高速缓存条目对于所述第一级别的通用性不是最近最少使用的；

响应于所述修改所述第一替换策略数据条目，识别与第二级别的通用性相关联的第二替换策略数据条目，所述第二级别的通用性比所述第一级别的通用性更具体，所述第二替换策略数据条目也与所述第一高速缓存条目相关联并且与所述第一组缓存路相关联；以及

修改所述第二替换策略数据条目以还指示所述高速缓存的所述第一高速缓存条目对于所述第二级别的通用性不是最近最少使用的。

9.如权利要求8所述的高速缓存，其中所述第一高速缓存条目被配置成存储从虚拟地址到物理地址的转换。

10.如权利要求8所述的高速缓存，其中：

所述第一高速缓存条目存储第一存储页面的转换，并且

所述第一存储页面映射到所述第一组缓存路中的所述高速缓存的第一集合，并且映射到所述多个缓存路组中的第二组缓存路中的所述高速缓存中的第二集合，所述第二集合是与所述第一集合不同的集合。

11.如权利要求8所述的高速缓存，其中所述高速缓存控制器被配置成：

检测所述高速缓存存储器中的未命中；

响应于所述未命中来获取将要置于所述高速缓存的所述第一高速缓存条目中的项目；

基于与所述项目相关联的地址并且基于与所述项目相关联的所述第一级别的通用性来识别用于所述项目的所述第一集合和所述第一组缓存路；以及

基于所述第一替换策略数据条目来识别所述缓存路组中的缓存路，

其中对所述识别的缓存路、所述集合和所述缓存路组执行对所述高速缓存的所述第一高速缓存条目的所述更新。

12.如权利要求11所述的高速缓存，其中所述高速缓存控制器被配置成通过以下步骤识别所述缓存路组中的所述缓存路：

确定所述第一替换策略数据条目指示所述缓存路组中的所述缓存路存储用于与所述项目相关联的页面大小的最近最少使用的高速缓存条目。

13.如权利要求11所述的高速缓存，其中：

所述第一替换策略数据条目包括一位，所述一位指示所述缓存路组中的哪个缓存路包括最近最少使用的数据。

14.如权利要求8所述的高速缓存，其中所述高速缓存控制器被配置成：

检测对所述高速缓存的第二高速缓存条目的第二更新；

检测对与所述第二高速缓存条目对应的第三替换策略数据条目的第二修改，所述第三替换策略数据条目与所述第二级别的通用性相关联；以及

确定第二页面大小是用于所述高速缓存中的数据的最具体级别的通用性，

其中响应于所述第三替换策略数据条目与用于所述高速缓存中的数据的所述最具体级别的通用性相关联而不修改其他替换数据。

15.一种处理器，其包括：

执行流水线，所述执行流水线被配置成执行指令；以及

高速缓存，所述高速缓存被配置成存储从第一地址空间到第二地址空间的转换，所述高速缓存包括多个集合，每个集合包括被分成多个缓存路组的多个缓存路，所述高速缓存包括：

高速缓存存储器，所述高速缓存存储器存储高速缓存数据；

替换策略存储器，所述替换策略存储器存储替换策略数据；以及

高速缓存控制器，所述高速缓存控制器被配置成：

检测对所述高速缓存存储器的第一高速缓存条目的更新，所述高速缓存的所述第一高速缓存条目与所述多个集合中的第一集合相关联，并且与所述多个缓存路组中的第一组缓存路相关联；

响应于对所述第一高速缓存条目的所述更新，修改对应于所述第一高速缓存条目和所述第一组缓存路的第一替换策略数据条目，所述第一替换策略数据条目与第一级别的通用性相关联，所述修改致使所述第一替换策略数据条目指示所述高速缓存的所述第一高速缓存条目对于所述第一级别的通用性不是最近最少使用的；

响应于对所述第一替换策略数据条目的所述修改，识别与第二级别的通用性相关联的第二替换策略数据条目，所述第二级别的通用性比所述第一级别的通用性更具体，所述第二替换策略数据条目也与所述第一高速缓存条目相关联；以及

修改所述第二替换策略数据条目以还指示所述高速缓存的所述第一高速缓存条目对于所述第二级别的通用性不是最近最少使用的。

16.如权利要求15所述的处理器，其中所述第一高速缓存条目被配置成存储从虚拟地址到物理地址的转换。

17.如权利要求15所述的处理器，其中：

所述第一高速缓存条目存储第一存储页面的转换，并且

所述第一存储页面映射到所述第一组缓存路中的所述高速缓存的第一集合，并且映射到所述多个缓存路组中的第二组缓存路中的所述高速缓存中的第二集合，所述第二集合是与所述第一集合不同的集合。

Images