预取单元、数据预取方法以及微处理器的制作方法.docx

预取单元、数据预取方法以及微处理器的制作方法专利名称：：预取单元、数据预取方法以及微处理器的制作方法技术领域：：本发明涉及一般微处理器的快取存储器，特别是涉及将数据预取至微处理器的快取存储器背景技术：：以最近的计算机系统而言，在快取失败(cachemiss)时，微处理器存取系统存储器所需的时间，会比微处理器存取快取存储器(cache)多上一或两个数量级因此，为了提高快取命中率(cachehitrate)，微处理器整合了预取技术，用来测试最近数据存取样态(examinerecentdataaccesspatterns)，并且企图预测哪一个数据为程序下一个存取的对象，而预取的好处已是众所皆知的范畴然而，申请人注意到某些程序的存取样态并不为现有微处理器的预取单元所能检测的例如，图1所示为当执行的程序包括经由存储器进行一序列的储存操作时，第二级快取存储器(L2Cache)的存取样态，而图中所描绘的为各时间的存储器地址由图1可知，虽然总趋势为随着时间而增加存储器地址，即由往上的方向，然而在许多状况下，所指定的存取存储器地址亦可较前一个时间往下，而非总趋势的往上，使其不同于现有预取单元实际所预测的结果。

虽然就数量相对大的样本而言，总趋势是朝一个方向前进，但现有预取单元在面临小样本时却可能出现混乱状况的原因有两个第一个原因为程序是依循其架构对存取存储器，不论是由演算法特性或是不佳的编程(poorprogramming)所造成第二个原因为非循序(out-of-orderexecution)微处理器核心的管线与队列在正常功能下执行时，常常会用不同于其所产生的程序顺序来进行存储器存取因此，需要一个数据预取单元(器)能够有效地为程序进行数据预取，其必须考虑到在较小时窗(timewindows)进行存储器存取指令(操作)时并不会呈现明显的趋势(nocleartrend)，但当以较大样本数进行审查时则会出现明显的趋势发明内容本发明揭示一种预取单元，设置于具有一快取存储器的一微处理器中，其中预取单元用以接收对一存储器区块的多个地址的多个存取要求，每一存取要求对应存储器区块的地址中的一个，并且存取要求的地址随着时间函数非单调性地(non-monotonically)增加或减少预取单元包括一储存装置以及一控制逻辑控制逻辑，耦接至储存装置，其中当接收到存取要求时，控制逻辑则用以维持储存装置中的存取要求的一最大地址以及一最小地址，以及最大地址以及最小地址的变化的计数值、维持存储器区块中最近被存取的快取线的一历史记录，最近被存取的快取线是与存取要求的地址相关、根据计数值，决定一存取方向、根据历史记录，决定一存取样态，并且根据存取样态并沿着存取方向，将快取存储器内尚未被历史记录指示为已存取的快取线预取至存储器区块中。

本发明揭示一种数据预取方法，用以预取数据至一微处理器的一快取存储器，数据预取方法，包括接收对一存储器区块的多个地址的多个存取要求，每一存取要求对应存储器区块的地址中的一个，并且存取要求的地址随着时间函数非单调性地(non-monotonically)增加或减少；当接收到存取要求时，维持存储器区块中的一最大以及一最小地址，并且计算最大以及最小地址的变化的计数值；当接收到存取要求时，维持存储器区块中最近被存取的快取线的一历史记录，最近被存取的快取线是与存取要求的地址相关；根据计数值决定一存取方向；根据历史纪录决定一存取样态；以及根据存取样态并沿着存取方向，将快取存储器内尚未被历史记录指示为已存取的快取线预取至存储器区块中本发明揭示一种微处理器，包括多个核心、一快取存储器以及一预取单元快取存储器，由核心所共享，用以接收对一存储器区块的多个地址的多个存取要求，每一存取要求对应存储器区块的地址中的一个，存取要求的地址随着时间函数非单调性地(non-monotonically)增加或减少预取单元，用以监视存取要求，并维持存储器区块中的一最大地址以及一最小地址，以及最大地址以及最小地址的变化的计数值、根据计数值，决定一存取方向并且沿着存取方向，将存储器区块中未命中的快取线预取至快取存储器中。

本发明揭示一种微处理器，包括一第一级快取存储器、一第二级快取存储器以及一预取单元预取单元用以检测出现在第二级快取存储器中的最近存取要求的一方向以及样态，以及根据方向以及样态，将多个快取线预取至第二级快取存储器中、从第一级快取存储器，接收第一级快取存储器所接收的一存取要求的一地址，其中地址与一快取线相关、决定在方向中所相关的快取线的后被样态所指出的一个或多个快取线并且导致一个或多个快取线被预取至第一级快取存储器中本发明揭示一种数据预取方法，用以预取数据至具有一第二级快取存储器的一微处理器的一第一级快取存储器，数据预取方法包括检测出现在第二级快取存储器中的最近存取要求的一方向以及样态，以及根据方向以及样态，将多个快取线预取至第二级快取存储器中；从第一级快取存储器，接收第一级快取存储器所接收的一存取要求的一地址，其中地址与一快取线相关；决定在方向中所相关的快取线的后被样态所指出的一个或多个快取线；以及导致一个或多个快取线被预取至第一级快取存储器中本发明揭示一种微处理器，包括一快取存储器以及一预取单元预取单元用以检测具有一第一存储器区块的多个存储器存取要求的一样态，并且根据样态从第一存储器区块预取多个快取线至快取存储器中、监视一第二存储器区块的一新的存储器存取要求、决定第一存储器区块是否虚拟邻近于第二存储器区块，并且当自第一存储器区块延续至第二存储器区块时，则决定样态是否预测到第二存储器区块的新的存储器存取要求所相关的一快取线在第二存储器区块中、并且根据样态，从第二存储器区块将相映的快取线预取至快取存储器中。

本发明揭示一种数据预取方法，用以预取数据至一微处理器的一快取存储器，数据预取方法包括检测具有一第一存储器区块的多个存储器存取要求的一样态，并且根据样态从第一存储器区块预取快取线至上至快取存储器中；监视一第二存储器区块的一新的存储器存取要求；决定第一存储器区块是否虚拟邻近于第二存储器区块，并且当自第一存储器区块延续至第二存储器区块时，决定样态是否预测到第二存储器区块的新的存储器存取要求所相关的一快取线在第二存储器区块中；以及根据样态，从第二存储器区块将多个快取线预取至快取存储器中，以回应决定步骤图1所示为当执行经由存储器包括一序列储存操作的的程序时，一种第二级快取存储器的样态存取表现图2为本发明的一种微处理器的方块图图3为本发明图2的预取单元更详细的方块图图4为本发明图2的微处理器以及特别是图3的预取单元的操作流程图图5为本发明图3的预取单元对图4的步骤的操作流程图图6为本发明图3的预取单元对图4的步骤的操作流程图图7为本发明图3的预取要求队列的操作流程图图8A和图8B为本发明一存储器区块的两个图型存取点，用以表示本发明的定界框预取单元图9为本发明图2所示的微处理器的操作范例的方块图图10为本发明延续图9的范例的图2所示的微处理器的操作范例的方块图。

图IlA和图IlB为本发明延续图9以及10图的范例的图2所示的微处理器的操作范例的方块图图12为本发明另一实施例的一种微处理器的方块图图13为本发明图12所示的预取单元的操作流程图图14为本发明根据图13步骤的图12所示的预取单元的操作流程图图15为本发明另一实施例具有一定界框预取单元的一种微处理器的方块图图16为本发明图15的虚拟杂凑表的方块图图17为本发明图15的微处理器的操作流程图图18为本发明根据经由图17范例叙述的在预取单元的操作后的图16的虚拟杂凑表的内容图19A和图19B为本发明图15的预取单元的操作流程图图20为本发明另一实施例的用在图15的预取单元的一杂凑物理地址至杂凑虚拟地址库的方块图图21本发明的一多核微处理器的方块图附图符号说明100微处理器102指令快取存储器104指令解码器106暂存器别名表108保留站112执行单元132其他执行单元134载入/储存单元124预取单元114引退单元116第一级数据快取存储器118第二级快取存储器122总线接口单元162虚拟杂凑表198队列172第一级数据搜寻指标器178第一级数据样态地址196第一级数据存储器地址194样态预测快取线地址192快取线配置要求188快取线数据354存储器区块虚拟杂凑地址栏356状态栏302区块位遮罩暂存器303区块号码暂存器304最小指标暂存器306最大指标暂存器308最小改变计数器312最大改变计数器314总计数器316中间指标暂存器318周期匹配计数器342方向暂存器344样态暂存器346样态顺序暂存器348样态区域暂存器352搜寻指标暂存器332硬件单元322控制逻辑328预取要求队列324提取指标器326推进指标器2002杂凑虚拟地址库2102A核心A2102B核心B2104高度反应式的预取单元2106共享的高度反应式的预取单元具体实施例方式以下将详细讨论本发明各种实施例的制造及使用方法。

然而值得注意的是，本发明所提供的许多可行的发明概念可实施在各种特定范围中这些特定实施例仅用于举例说明本发明的制造及使用方法，但非用于限定本发明的范围广泛而言，关于上述问题的解决方法可以后续叙述加以解释当一存储器的所有存取(指令、操作或要求)皆表示在一张图上时，所有存取(指令、操作或要求)的一集合可被一定界框圈起来当外加的存取要求亦表示于同一图上时，这些存取要求亦可被调整大小后的定界框圈起来上述首张图如图8所示为一存储器区块的两次存取(指令或操作)中图8的X轴表示指令的存取的时间，Y轴表示具有4KB区块的存取的64字节快取线的索引首先，描绘第一次的两个存取第一个存取是对快取线5进行存取，第二个存取要求是对快取线6进行存取如图所示的一定界框将代表存取要求的两点圈起来再者，第三个存取要求发生于快取线7，定界框变大使得代表第三个存取要求的新点可被定界框圈起在内随着新的存取不断发生，定界框必随着X轴扩大，并且定界框的上缘亦随着Y轴扩大(此为向上的例子)上述定界框上缘以及下缘的移动的历史纪录将用以决定存取样态的趋势为向上、向下或者都不是除了追踪定界框的上缘以及下缘的趋势以决定一趋势方向外，追踪个别的存取要求也是必要的，因为存取要求跳过一或两个快取线的事件时常发生。

因此，为了避免跳过所预取快取线的事件发生，一旦检测到一向上或向下的趋势，预取单元则使用额外的准则决定所要预取的快取线由于存取要求趋势会被重新排列，预取单元会将这些暂态的重新排列存取历史纪录予以删除此操作藉由标记位(markingbit)在一位遮罩(bitmask)中完成的，每一位对应具有一存储器区块的一快取线，，且当位遮罩中对应的位被设置时，表示特定的区块可被存取一旦对存储器区块的存取要求已达到一充分数量，预取单元会使用位遮罩(其中位遮罩不具有存取的时序的指示)，并基于如下所述的较大的存取观点(广义largeview)去存取整个区块，而非基于较小的存取观点(狭义smallview)以及现有预取单元般仅根据存取的时间去存取的区块图2所示为本发明的微处理器100的方块图微处理器100包括一个具有多个阶层的传递路径，并且传递路径中亦包括各种功能单元传递路径包括一指令快取存储器102，指令快取存储器102耦接至一指令解码器104；指令解码器104耦接至一暂存器别名表106(registeraliastable,RAT)；暂存器别名表106耦接至一保留站108(reservationstation)；保留站108耦接至一执行单元112(executionunit)；最后，执行单元112耦接至一引退单元114(retireunit)。

指令解码器104可包括一指令转译器(instructiontranslator)，用以将巨集指令(例如x86架构的巨集指令)转译为微处理器100的类似精简指令集(reduceinstructionsetcomputerRISC)的巨集指令。