循环顺序存储器预取

摘要

一种使用被构成为顺序存储来自存储器的项的多个独立缓冲器的存储器存取体系结构及技术。该存储器被逻辑分割，并且每个独立缓冲器与对应的存储器分区相关。该分区是基于缓冲器的总数K，以及缓冲器的大小N而循环连续的。第一个N个存储单元被分配给第一分区；下一个N个存储单元被分配给第二分区；等等直到第K个分区。在第K个分区后的下一N个存储单元被分配给第一分区；下一个N个存储单元被分配给第二分区；等等。当从存储器存取一项时，对应于该项的存储单元的缓冲器被从存储器装入，并且下一顺序分区的预取开始装入下一缓冲器。在程序执行期间，缓冲器内容的“稳定状态”对应于含有当前指令的一缓冲器，含有立即跟随该当前指令的指令的一个或多个缓冲器，以及含有立即先于该当前指令的指令的一个或多个缓冲器。该稳定状态条件特别好地适合于执行程序循环，或程序指令的一连续序列，以及其它通用程序结构。参数K和N被选择以适应典型地按大小排列的程序循环。

说明书

相关申请的引用

本申请与同时申请的名为“MEMORY ACCELERATOR FOR ARMPROCESSORS”，申请号为09/788.691(代理人案号US018011)的美国专利申请有关。

发明背景

1.发明领域

本发明涉及计算机系统领域，并且更具体地涉及用于通过使用存储器分割，顺序预取，以及多个独立缓冲器来最小化存储器存取延迟的系统及方法。

2.相关技术的描述

各种技术可共同用于最小化与从存储器元件检索程序代码及数据有关的延迟的影响。通常，程序及数据项存储在处理器外部的存储器设备中，并且从外部存储器存取一项的时间实际上比从与该处理器相配置的存储器(内部存储器)存取一项的时间长。为了便于参考，这里所用的术语存储器是指相对于处理器的速度而言有着相对低的存取时间的存储装置，所用的术语缓冲器是指相对于处理器的速度而言有着短的存取时间的存储装置。

一种通用技术是高速缓存缓冲器的使用。当存取存储器内的一项时，含有该项的存储器块被读入该处理器本地的高速缓冲存储器内。同样被包含在已被读入该高速缓冲存储器内的存储器块中的被顺序寻址的项被直接从该高速缓冲存储器存取，从而避免了与存储在存储器内的项相关的延迟。当一个被顺序寻址的项不在该高速缓冲存储器内时，适当的存储器块被读入该高速缓冲存储器，引起存储器存取延迟。高速缓冲存储器的大小越大，一被寻址项越有可能在该高速缓冲存储器之内。其它参数也可能会影响一个项处于该高速缓冲存储器内的可能性。例如，一条例程可以重复调用另一条例程。如果这两条例程彼此近似，那么它们可以均位于该高速缓冲存储器内，并且将不引起任何存储器存取延迟；否则，在例程之间的每个调用及返回之间都需要一次存储器存取。通常，采用多个独立的高速缓冲存储器，因此来自存储器的潜在相隔的部件的不同存储器块能够被存储。在一条例程重复地调用另一条例程的例子中，一个高速缓冲存储器可以包含第一条例程，而另一个高速缓冲存储器可以包含第二条例程，经由对应的高速缓冲存储器来对任一条例程的存取将避免存储器存取延迟。当诸如循环的例程超越块间的边界时产生了关于高速缓冲存储器缓冲的一个特殊问题。不考虑程序的大小，将要求两个块被存入两个高速缓冲存储器中。为了最小化超越边界的例程的相似性，块/高速缓冲存储器的大小一般很大，从而降低边界的数量。

为了成为有效，高速缓冲存储器缓冲一般需要相当大的高速缓存缓冲器，典型地为数百或数千字节的数量级。传统的高速缓冲存储器缓冲的一个替代是预取缓冲，其中当处理器正在从缓冲器存取先前的一条指令时，随后的指令被从存储器读入该缓冲器中。由于该缓冲器中的内容基于当前所执行指令的地址，或是基于随后的一条转移指令而被不断地更新，因此预取缓冲器的大小能够实质上小于高速缓存缓冲器的大小而实现相同的效果。通过将预取技术应用于传统的转移指令能够进一步提高预取方案的效率，以优化当执行传统的转移指令时适当代码在该预取缓冲器内的相似性。例如，能够鉴别循环结构，以及能够构造预取算法来假设程序将比退出循环更经常地返回到循环起始处，并因此在控制是否重新执行循环或退出循环的传统转移指令后立即把该指令放于循环起始处。只有当传统的转移指令导致退出时处理器才被延迟，同时该循环后的指令被从存储器装入到缓冲器中。

在高速缓冲存储器以及预取缓冲途径中，执行程序所需的时间基本上是不确定的，这是因为处于本地缓冲器内的所需项的相似性是不确定的，并且因此所需的存储器存取的次数是不确定的。

发明概述

本发明的一个目的是提供一种有基本确定性的存储器存取技术。本发明的还一个目的是提供一种考虑到内部缓冲器的大小的有效的存储器存取技术。本发明的再一个目的是提供一种考虑到整个存储器存取时间的有效的存储器存取技术。本发明的又一个目的是提供一种能够与其它存储器存取技术，如高速缓存技术结合的存储器存取技术。

通过提供一种使用被构成为顺序存储来自存储器的项的多个独立缓冲器的存储器存取体系结构及技术来实现本发明的这些及其它目的。该存储器被逻辑分割，并且每个独立缓冲器与对应的存储器分区相关。该分区是基于缓冲器的总数K，以及缓冲器的大小N而循环连续的。第一个N个存储单元被分配给第一分区；下一个N个存储单元被分配给第二分区；等等直到第K个分区，并重复该分配。在分配给K个分区的K*N存储单元后，下一N个存储单元被分配给第一分区；下一个N个存储单元被分配给第二分区；等等。当从存储器存取一项时，对应于该项的存储单元的缓冲器被从存储器装入，并且下一顺序分区的预取开始装入下一缓冲器。在程序执行期间，缓冲器内容的“稳定状态”对应于含有当前指令的一缓冲器，含有直接跟随该当前指令的指令的一个或多个缓冲器，以及含有直接先于该当前指令的指令的一个或多个缓冲器。该稳定状态条件特别好地适合于执行程序循环，或程序指令的一连续序列，以及其它通用程序结构。参数K和N被选择以适应典型地按大小排列的程序循环。

附图的简要说明

参照附图，并通过例子将更为详细地解释本发明，其中：

图1说明本发明的一示例存储器存取体系结构。

图2A和2B说明用于本发明存储器存取体系结构中的一示例地址结构及缓冲器寄存器。

图3说明用于本发明存储器存取的一示例流程图。

在全部附图中，相同的参考数字表示类似或对应的特征或功能。

发明的详细说明

图1说明本发明的一示例存储器存取体系结构。把存储器110举例为含有从左至右的连续存储单元101，102，103，等等，并逻辑地分割为存储区I，II，---VIII。如所示例的，在存储单元第一行末尾的存储单元132后的下一个连续的存储单元是存储单元133，位于存储单元101底下的下一行。存储单元101和133的每一个均对应于所分割的第一存储单元。也就是，由于一行的最后一个存储单元环绕下一行的第一个存储单元，因此存储单元能够被视为构成一螺旋形。为便于参照，这里把该分割定义为循环顺序分割，其中N个存储单元块被顺序分配给各个分区，并且该分配被循环使用，其中把在被分配给最后分区的块之后的N个存储单元块分配给第一个分区，并且重复该顺序及循环处理直到把所有的存储单元块分配给这些分区。

下文代替“行”使用术语“段”来表示从第一分区的第一个存储单元到最后一个分区的最后一个存储单元的连续存储单元的一个唯一集合。如果存在K个分区，并且每一分区为N个存储单元宽，那么第一个段对应于第一个K*N存储单元，第二个段对应于下一个K*N存储单元，等等。

如果分区数，K，是2的乘方，并且每一分区的宽度，N，也是2的乘方，那么能够使用如图2A所例举的地址结构210来直接识别段211，段211内的分区212，以及在所寻址项的分区212内的存储单元。为便于参照，下文中的每个存储单元定义为含有一程序或数据字，并且把地址结构210中的位置域213称作“字”域213。

根据本发明，每个分区I，II，---VIII与一对应的缓冲器I，II，---VIII 120有关。当处理器130启动存储器存取时，存储器存取控制器140把所寻址段211及分区212的N个字装入缓冲器120，对应于地址210，并且该处理器从缓冲器120读。与此同时，控制器140把下一个N个字预取到对应于下一个分区的缓冲器内。由于每个连续的项均被寻址，因此控制器140进行检验以确定是否已把项装入缓冲器120，并且若是，则允许处理器130从缓冲器120中读取项。否则，控制器140把对应的N个字从存储器中取到缓冲器120内。由于N个字中的每一组都存储在缓冲器120内，因此控制器140利用，例如，图2B所例举的一组寄存器230来记录对应于所存储字的段211。注意，与特定分区有关的寄存器内的所存储段号码足以唯一地识别对应于缓冲器120内的存储器110中的存储单元。随着每次存取，控制器140进行检验以保证下一缓冲器包含N个字的下一组，并如所需要的不断地预取下一组。在此方式中，缓冲器组120将最终含有在当前被寻址的字之前的一组字，以及在当前被寻址的字之后的一组字。

由于从存储器的一致的和连续的取的特殊意义，能够在程序序列的任何一点处相当好地确定缓冲器120中的内容。利用具有控制其结束处的循环的传统分支指令的循环结构的例子，如上所述，当传统分支指令被执行时，将得知在传统分支指令后的指令位于当前的或下一缓冲器中，这是因为控制器140自动地预取下一缓冲器。在传统分支指令前的指令将被得知位于当前的或之前的缓冲器中，这是因为控制器140并不重写缓冲器，除了当发生前述的预取时。如果存在大小为N的K个缓冲器，那么任何一个(K-2)*N+1字长的或较该字长短的循环都将被得知位于缓冲器组120内，这是因为之前的K-2个缓冲器将不被重写。由于存储器110的分割的循环特性(例如，连续存储元件132，133)，因此第K-1个缓冲器对应于“下个”缓冲器，并将通过伴随对先前缓冲器的存取的预取而被重写。比(K-1)*N的字长大的任何循环将被得知位于缓冲器组120外，并将引起存储器存取延迟。对于(K-2)*N+1与(K-1)*N之间的循环，该循环起始与结束处的特定字存储单元将确定该特殊循环是否将处于缓冲器组120内。例如，如果传统分支为缓冲器内的最后一个字，并且该循环的起始是在缓冲器的第一个字处，那么该循环能够是和(K-1)*N个字一样大，这是因为只有超出该传统分支的N个字将被存储在缓冲器120内。另一方面，如果传统分支是在缓冲器的第一个字处，那么超出该传统分支的2N-1将被存储在缓冲器120内，只留下K*N-(2N-1)个字可用来包含该循环。注意，在实际向存储器分配程序之前，比(K-2)*N+1个字小的循环，以及比(K-1)*N个字大的循环能够被识别，以为了用户的改进考虑而大概地从“问题”循环中区分“安全”循环。在向存储器的特定分配之后，如果希望的话，那些大小在(K-2)*N+1与(K-1)*N个字之间的循环能够被识别，基于传统分支指令字-存储单元而被标记为“安全”或“问题”。

以类似方式，根据预先的程序结构，或实际的程序结构能够提供各种存取方案。例如，可以实现N个字块的多个预取以支持在该循环的起始处具有其传统分支指令的循环。在这样的一个实施例中，当程序开始执行时，可以把用N个字块来表示的预取的大小定义为一个参数，或定义为能够通过程序指令而被动态地改变的一个参数。在后一情形中，能够配置编译器或汇编程序以根据代码的特定部分的结构来调整预取的大小。鉴于本公开的内容，这些以及其它的存储器存取优化方案对于本领域的普通技术人员来说是显而易见的。

通过提供一种相当大确定性的存储器存取方案，能够估算一条程序的执行时间，并且能够作出结构上的变化以提高存储器存取的效率。也就是，例如，为了用户的改变考虑，能够提供一分析程序来识别超过(K-1)*N个字的程序循环。与其中“建议的改进”是以一般规则及公共试探法为基础的其它技术相比，本发明的存储器存取方案允许相当确定的建议改进，有着实质上已知的结果。也可以把自动化的配置配备在编译器中以构造合成码来适应本发明的确定性约束。鉴于本公开的内容，具有确定性性能的高效存储器存取方案的这些以及其它的优点对于本领域的普通技术人员来说是显而易见的。

根据将存储在存储器110内的程序的所期望结构，以及根据本地于处理器130的缓冲器的大小及花费来选择参数K和N。一般根据提供高效存储器存取的大小，以及根据与缓冲器存储相比的存储器存取的相对速度来选择宽度N。某些存储器结构被专门设计用于多字存取，并且N应当被选作为该多字存取能力大小的倍数。而且，如上所论述的，如果需要，当从缓冲器120取一个字时，向下一缓冲器内的字预取就生效。假设一顺序流从缓冲器内的第一个字至最后一个字，那么最好把N选择为足够长以使执行N条指令所需的时间比预取到下一缓冲器内所需的存取时间长，这样当完成先前的指令时下一缓冲器就含有适当的指令。一般在选择N之后，根据所期望的程序，如通常将使用的循环的长度来选择参数K。如上所指出的，在长度上少于(K-2)*N+1个字的程序循环将被保证完全位于K个缓冲器内。如果L是所估算的公共循环结构的最大大小，那么最好把K选为至少是L/N+2。而且，如上所指出的，把K和N选为2的乘方提供了容易的地址解码。共同未决的、申请人为Gregory K.Goodhue，Ata R.Khan，John H.Wharton，以及Robert Kallal，申请日为2001.2.20的第09/788.691号名为“MEMORY ACCELERATOR FOR ARM PROCESSORS”的美国专利申请(代理人案号为US018011)教导了把存储器分为四个象限的一种分割，每个象限为四个字宽，这特别适合于微控制器的实施例。

特别需要注意的是每个循环的存储器存取延迟的最大数量，不考虑循环大小，为1。对少于(K-2)*N+1条指令的循环更少数量，以及在(K-2)*N+1与(K-1)*N条指令之间的一些循环，每一循环的存取延迟数量为0，对于所有其他循环，每一循环的存取延迟数量为1。因此，对于(K-1)*N+1条指令的循环产生了更坏情形的性能；由于循环的大小增加，因此自动顺序预取不断地消除存储器存取延迟，从而与(K-2)*N+1条指令的循环相比改进了整个存储器存取的效率。

图2A和2B的地址结构和寄存器安排是为了举例说明目的而提出的；同样也可以采用本技术领域内通用的另外的存储器管理技术。以类似方式，各种技术中的任何一种能够被用来便利本发明的存储器存取方案。为了完整，图3说明了本发明的用于存储器存取的一示例流程图，尽管本发明并不限于该示例实施例。

在步骤310，存储器存取控制器获得将要被处理的下一个地址。一般地，该地址对应于一识别将由处理器所执行的下一条指令的常规程序计数器的内容。在常规分支的例子中，处理器根据与该常规分支相关的一测试的执行来更新该程序计数器。照这样，该实际地址可以仅在该地址被处理时才被得知。

在步骤315，存储器存取控制器检验对应于该地址的段是否存储在同样对应于与该地址相对应的分区的缓冲器内。也就是，参见图1，2A和2B，如果地址210的分区字段212表示是在存储器120的分区II内，那么检验对应于分区II的InBuffer寄存器232以查看在存储于寄存器232内的段号与对应于地址210的段号211之间是否存在匹配。

如果，在步骤315，存在段号匹配，那么在步骤340，直接从缓冲器120(本例中的缓冲器II)中读寻址字213，从而避免了从存储器110读。

如果，在步骤315，地址210的段211与当前被包含在对应于地址210的分区212的缓冲器120内的段232不匹配，那么在步骤320，段211的N个字以及地址210的分区212被从存储器110取到对应于分区212的缓冲器120中。在步骤330，分区212的InBuffer寄存器被更新以反映对应于分区212的缓冲器120的当前段211。在步骤340，从缓冲器120(本例中的缓冲器II)直接读出寻址字213。

在步骤350-370，如果需要，实现下一N个字的预取。在步骤350，考虑到该分割方案的循环特性，下一段以及分区号被确定。也就是，分区号被加1。如果这一增加产生超出分区号码的一个分区号，那么就被复位到第一分区号，并且段号被加1。在图3的流程图中，项n段和n分区对应于结果循环递增的段以及分区号。方框355-370对应于上述方框315-330，除了下一参数n段和n分区代替先前的参数段和分区。在此方式中，确保了下一寻址的N个字块被包含在缓冲器120内。

如同将对于本领域内的普通技术人员所显而易见的，能够与读和/或取处理310-340相并行地执行预取处理350-370。也就是，例如，在步骤310，在确定段及地址的分区后，处理350-370可以被立即产生作为一个单独的处理线程，或者，它能够包含其自己的段及分区确定装置，并且在执行方框310的同时被产生。类似地，也可以出现在处理310-340的结束处但是被配置以便允许处理器继续工作，只要该字被读，在步骤340。基于存储器110的特殊存取能力以及处理器130所提供的并行性，其它方案也是显而易见的。

注意，尽管使用了对存储器的读存取范例来介绍了本发明，但是本发明同样适用于对存储器的读写存取。在读写存取的实施例中，给上述方案增加了把缓冲器的内容写入存储器，只要该缓冲器被重新分配给一不同的段并且由于它最初被从存储器取出，因此该缓冲器的内容已经改变。方便和优化从临时缓冲器向存储器的这一更新的存储器管理方案在本领域是通用的。

以类似方式，为了便于理解而介绍了图1-2的特殊结构。存储器存取控制器140，缓冲器120，控制器140，以及寄存器230可以，例如，构成一单独的逻辑块；这些项的任何一个或是全部被包含在处理器130内；等等。类似地，还可以使用硬件与固件的组合。在某些系统中，例如，存储器存取控制器可以是被在微码引擎内执行的一组微码，或者它可以是一组逻辑门，等等。

尽管主要从用于程序指令的存储器存取的角度介绍了本发明，但是本发明同样适用于数据存取方案，尤其是对于涉及对数据项的连续存取，以及对数据项块的重复存取，如图形处理系统的应用。这一实施例中的缓冲器可以是被从含有图形对象，纹理，等等的磁盘文件的对应部分装入的程序中的数据阵列。

以上仅仅说明了本发明的原理。因此应指出本领域的技术人员将能够设计出各种包含有本发明原理的设备，尽管这里未直接描述或示出，并且由此而落入本发明的精神及范围之内。例如，这里所介绍的存储器存取方案能够同样与其它存取方案一起使用。跟随多高速缓存范例，多个缓冲器组I，II，...VIII能够从存储器110的不同区域被提供给缓冲器项。当一条分支指令，或一条数据存取指令出现了引用在与当前指令相当大距离上的地址时，对应于该地址的N个字能够被装入到第二组缓冲器的一对应缓冲器中，并且如上所介绍的考虑到该单独的缓冲器组，下一N个字被预取到该第二组缓冲器的下一缓冲器中。在此方式中，如果一例程重复调用另一例程，或在存储器的另一区域存取数据，那么存储器的这两个区域都被缓冲，由此避免了重复的存储器存取。两组缓冲器的使用，例如，特别好地适合于对程序代码及数据的交错存取。鉴于本公开的内容，这些以及其它系统配置和优化特征对于本领域的普通技术人员来说将是显而易见的，并且被包含在下列权利要求书的范围内。