螺旋高速缓存电源管理、自适应大小调整和接口操作

摘要

一种螺旋高速缓冲存储器，通过自组织以始终将请求值移至螺旋高速缓冲存储器的最前端存储块而为频繁存取的值提供低存取延迟。如果所述螺旋高速缓存需要逐出值以便为移至所述最前端块的值腾出空间，则通过将值从所述高速缓存逐出到后备存储器来腾出空间。使用缓冲器连同流控制逻辑来防止逐出值的写入溢出到总体较慢的后备存储器。所述螺旋高速缓存中的块可以是单个存储位置，也可以组织为某种形式的高速缓冲存储器，例如直接映射高速缓存或组关联高速缓存。通过将所述螺旋高速缓存划分成可按块调整的活动和不活动分区，可以降低所述高速缓存的功耗。块产生的或全局的断电决策可以设置所述分区的大小。

权利要求

1.一种在存储设备内缓存多个值的方法，其中所述存储设备包括在至少一个电通路中具有有序排列的多个存储块，所述至少一个电通路从所述多个存储块中的最前端存储块到所述多个存储块中的最后端存储块而互连所述多个存储块，所述方法包括：将所述多个值存储在多个存储块中；

在输入接口处接收对所述值的请求；

响应于所述请求，通过与所述最前端存储块耦合的第一输出接口提供来自所述最前端存储块的所请求的值，其中在响应于对在所述输入接口处发出的先前请求值的先前请求而在所述第一输出接口处提供所述先前请求值之前，向所述输入接口发出多个请求；

响应于腾空所述最前端存储块中的存储位置以存储特定的请求值，将所述多个值中除了所述最前端存储块中存储的值以外的一个值从第二输出接口逐出到存储器层级的更高阶级别；以及其中所述逐出从可动态选择的块位置逐出所述多个值之一，由此根据对所述可动态选择的块位置的选择来动态地调整存储电路的有效大小，并且其中所述方法进一步包括选择所述可动态选择的块位置以设置所述存储电路的有效大小。

2.如权利要求1中所述的方法，其中仅在所述多个存储块均被值占据时才执行所述逐出，并且进一步包括：如果所述多个存储块未均被占据，则从所述存储器层级接收其他值而不逐出所述多个值之一。

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

将所述多个值中被逐出的值缓冲在队列中；以及

根据流控制逻辑的操作来防止所述被逐出的值将输入溢出到所述存储器层级的更高阶级别。

4.如权利要求1中所述的方法，还包括：移除从与所述可动态选择的块位置相邻的块延伸且远离所述最前端块的一组不活动块内的至少一个存储元件的电力，由此停用所述存储电路的不活动部分以降低所述存储电路中的功耗。

5.如权利要求1中所述的方法，其中所述移除包括：

在所述多个存储块内分别地判定是否要进入断电状态；以及

其中响应于判定应进入断电状态，所述多个存储块进入断电状态。

6.一种装置，包括适于执行根据任一上述方法权利要求的方法的所有步骤的部件。

7.一种计算机程序，包括当所述计算机程序在计算机系统上执行时，用于执行根据任一上述方法权利要求的方法的所有步骤的指令。

说明书

螺旋高速缓存电源管理、自适应大小调整和接口操作

技术领域

[0001] 本发明涉及高速缓冲存储器，更具体地说，涉及螺旋高速缓冲存储器中的电源管理、自适应大小调整和接口操作。

背景技术

[0002] 在现今的高速缓冲存储器系统中，在存取最频繁存取的值所需的时间与最短存取时间内可提供的此类值的数目之间存在权衡。例如，在传统多级高速缓存层级中，一级(L1)高速缓存针对特定数目的值提供一致存取时间，并且某些系统中的控制电路和其他算法特性用于维护L1高速缓存内的最频繁存取的值。但是，由于物理布线约束以及电子系统受电子信号传播速度的限制，因此L1高速缓存越大，典型L1高速缓存的(固定)存取时间越长。类似地，当为了缩短存取时间而减小L1高速缓存的大小时，未存储在L1高速缓存内的频繁存取的值的数目将增加。未存储在L1高速缓存内的值因此被存储在存储器层级的更高阶级别(例如，L2高速缓存)中，L2高速缓存的存取时间损失远大于L1高速缓存的存取时间损失，这是因为典型高速缓冲存储器系统是包含性的，也就是说，存储器层级的较高级别包含下一较低级别高速缓存中存储的所有值。在实际应用中，给定的较高级别高速缓冲存储器一般远大于下一较低级的高速缓冲存储器，并且给定诸如RC线延迟之类的上述传播速度约束以及裸片互连中电场传播固有速度的最终限制，较高级别的高速缓存将慢得多，通常在比下一较低级别的高速缓冲存储器慢10到100倍的量级。此外，存储器层级中较大的高级别高速缓存将增加功耗，虽然可以将高速缓冲存储器分成可单独进行电源管理的分区，但是这种电源管理需要在分区之间重新组织和移动数据以便减小高速缓存的大小不会损害正确性或导致性能降低。进而，由于需要在高速缓存中重新组织数据，因此相对于数据流的速率，执行电源管理操作的速度必然较低。

[0003] 此外，此类高速缓冲存储器系统中采用的典型高速缓存控制算法通常一次处理一个对高速缓存级别的未完成请求。如果存取请求“未命中”高速缓存，则此存取将停止或失败，因此请求源(例如，下一较低编号的高速缓存级别或L1高速缓存未命中情况下的处理器存储器存取逻辑)必须重试存取。所述请求从处理器向高速缓冲存储器的更高阶级别传播，但是稍后在L1级别处重试请求确保了当依赖于请求值的硬件线程等待所述请求成功时，仍为其他可执行的指令提供对所述高速缓存的存取。可提供停止整个处理器流水线的备选方法，但是性能损失将更为严重。

[0004] 最后，一般由高速缓冲存储器层级中的控制结构(例如，高速缓存控制器)实施高速缓冲存储器层级中值的组织，所述控制结构根据诸如最近最少使用(LRU)之类的方案衡量存取频率并组织高速缓存级别以使用驱逐(cast-out)逻辑将最频繁存取的值保持在低阶高速缓存中。

[0005] 提出了除上述传统高速缓冲存储器和层级以外的解决方案，其允许将多个请求流水线化，但是需要强制使用固定的最差存取延迟和缓冲来控制流水线信息流。

[0006] 进而，提出了非传统高速缓冲存储器，其具有非一致存取延迟并且在不使用其他存取度量和驱逐逻辑的情况下进行组织，但是相对于目前高速缓冲存储器的操作而言，它总体上仅提供了很小的潜在改进，其方式是：交换高速缓存表项以便缓慢地将频繁存取的值迁移到“较近的”位置，同时将不常使用的值迁移到“较远的”位置。此类非一致高速缓冲存储器还需要额外的通路来执行交换，并且通常是路由系统，其中使用开关电路执行特定高速缓存组(cache bank)的选择。

[0007] 因此，希望提供一种可以支持多个未完成请求，针对频繁存取的值提供非常低的存取延迟，以及在不需要复杂的区域密集型路由电路以及LRU和驱逐逻辑的情况下提供此类操作的高速缓冲存储器和高速缓存操作方法。进而，希望提供此类在不需要重新组织高速缓存内容的情况下应用电源管理且具有改进的响应性的高速缓存。

发明内容

[0008] 本发明提供了如权利要求1所述的方法以及相应的装置和计算机程序。

[0009] 本发明体现在螺旋高速缓冲存储器和操作方法中。所述螺旋高速缓冲存储器包含多个块(tile)，所述块具有用于存储值的存储位置，每个块可以是诸如直接映射高速缓存或关联高速缓存之类的较小高速缓冲存储器。

[0010] 始终在到最前端块的接口处提供请求值，从高速缓存自身或包括所述高速缓存的存储器层级的更高阶级别提供这些值。如果高速缓存已满，则通过经由后备存储器接口逐出值来释放存储位置以便存储请求值。可以提供缓冲器和流控制逻辑来防止被写入后备存储器的逐出值溢出。所述螺旋高速缓存支持多个未完成请求，无需在向高速缓存发出另一请求之前将值返回到最前端块。

[0011] 可以通过将高速缓存分成可按块调整的活动和不活动部分来执行螺旋高速缓存的电源管理。划分不活动部分和活动部分的边界可以由全局控制逻辑来设置，也可以由块自身内的单独逻辑/控制算法来自动确定。

[0012] 通过下面对附图中所示的本发明优选实施例的更具体的描述，本发明的上述和其他目的、特征和优点将变得显而易见。

附图说明

[0013] 在所附权利要求中说明了被认为是本发明特性的新颖特征。但是，当结合附图阅读时，通过参考以下对本发明的详细说明，可以最佳地理解发明本身以及优选使用方式，进一步的目的和优点，其中相同的标号指示相同的组件，这些附图是：

[0014] 图1A-1C是示出根据本发明的实施例的螺旋高速缓存内的放置技术的优点的画图示意图；

[0015] 图2是示出根据本发明的实施例的螺旋高速缓存内的值的动态重新排列的画图示意图；

[0016] 图3是根据本发明的实施例的螺旋高速缓存的方块图；

[0017] 图4A-4C是示出图3的螺旋高速缓存内的几何重试的方块图；

[0018] 图5是图3的螺旋高速缓存的方块图，示出了操作期间数据流的收缩时间线；

[0019] 图6是示出图3的螺旋高速缓存内的高速缓存微操作的时序图；

[0020] 图7A-7B是示出修改为在独占层级中结合移至前端放置策略的存储器层级的方块图，图7C是包括根据本发明的实施例的螺旋高速缓存的存储器层级的方块图；

[0021] 图8A和8B是示出根据本发明的实施例的螺旋高速缓存中的电源管理技术的方块图；

[0022] 图9是示出根据本发明的实施例的块管理式电源管理技术的流程图。

具体实施方式

[0023] 简介

[0024] 本发明包括存储器电路以及操作方法，它们可体现在高速缓冲存储器结构中，所述高速缓冲存储器结构在结构上被组织为螺旋形并且自组织其内容以将最近存取的值放置在最前端中央存储位置，同时在每次存取时将其他值后移到除最前端中央存储位置之外的位置。所形成的体系结构提供根据本发明的实施例的行为，所述行为在到平铺结构的最前端块的接口处提供每个请求值，同时通过将不常请求的值逐出到后备存储器来为频繁请求的值腾出空间。所述螺旋结构还实现了电源管理，其通过根据可按块调整的边界将存储器划分为活动部分和不活动部分而降低存储器电路功耗。所述螺旋高速缓存的基本原理是传统的一致存取延迟随机存取存储器(RAM)模型对于单芯片体系结构不再有效。当今高时钟频率下跨大型裸片的信号传播延迟在数十个时钟周期的量级。同时，单芯片集成的优点使得大型片上高速缓冲存储器成为必要。大型而快速的高速缓冲存储器长期以来被视为难题，因为大型存储器需要较大空间范围，而快速存储器需要较小空间范围以便最小化传播延迟。根据本发明的螺旋高速缓存通过基本连续地动态移动高速缓存行而提供大型快速的高速缓存。根据本发明的螺旋高速缓存的关键特征包括：

[0025] 1.小型快速(例如直接映射)高速缓存的平铺体系结构在技术和物理限制下平衡线延迟和缓存存取时间；

[0026] 2.使用移至前端试探动态地放置和替换高速缓存行且理论上保证最大存取时间；

[0027] 3.所述螺旋高速缓存的N个块的行为类似N-路关联高速缓存而没有诸如最近最少使用(LRU)计数器之类的传统簿记成本；

[0028] 4.所述螺旋高速缓存体系结构提供了能够保持多个存储器存取同时处于工作状态的无冲突收缩流水线，而没有路由或切换延迟并且无需数据缓冲来实现流控制；以及[0029] 5.所述螺旋高速缓存体系结构实现自适应电源管理，所述自适应电源管理维护一组活动块中的值的工作集的压缩副本，同时能够使可动态调整的一组不活动块处于断电状态。

[0030] 如上所述，虽然提出了高速缓冲存储器的收缩体系结构，但在这些设计中，无论处于高速缓冲存储器中的哪个位置，针对每个请求值都存在最差存取延迟。在此类设计中，请求必须传送到高速缓冲存储器的远端，然后在返回处理器或其他请求方的路上遍历每个区块(或本发明使用的术语中的“块”)。所述螺旋高速缓冲存储器在每次存取时不会经历最差延迟。相反，大多数存取产生只存取最前端块的最佳延迟，因此所述螺旋高速缓存提供了改进的性能。其他流水线存储器体系结构需要内部缓冲器来控制通过一维存储器块层级的数据流。本发明的存储阵列不需要内部流控制缓冲器并且不限于一维设计。实际上，如以下实例中描述的螺旋高速缓存中体现的本发明的存储阵列利用欧几里得空间维度来减小最差存取延迟。根据本发明的一个实施例的存储阵列可以被视为所谓的非一致高速缓存体系结构(NUCA)，所述非一致高速缓存体系结构可被实现为螺旋高速缓存。

[0031] 动态高速缓存放置

[0032] 为了减小频繁存取的值的存取时间并且如上所述，在此披露的示意性存储阵列在存取期间进行动态自组织以将较频繁存取的值放置到螺旋中心处的最前端位置，并将不常存取的值放置到螺旋外侧。对于大型快速VLSI设计而言，主要设计约束在于跨线的信号传播延迟，提供了以下说明以解释本发明的存储器体系结构的优点。

[0033] 空间存储器模型

[0034] 为了说明线延时，下面通过示例引入了一种存储器模型，其中可以将宽度与一维存储器阵列的每个单元关联，如图1A中所示。当处理器P向存储单元7发出加载请求时，请求信号跨存储单元1至6传播到存储单元7，并且存储单元7中存储的数据以相反方向传播回处理器P。为了使收缩实施方式提供存储单元1-7之间的移动(将作为螺旋高速缓存中的值移动机制进一步详细描述)，必须在一个时钟周期内跨一个存储单元传送信号。如果存储单元1-7被实现为1位存储器，则所示存储器阵列的空间范围可以很小并且将支持高时钟频率以满足收缩设计的一个时钟周期要求。但是，如果存储单元被实现为较大的存储器结构，例如直接映射高速缓存或组关联高速缓存，则可以分配与存储器阵列的存取延迟匹配的时钟频率。存储器阵列越小，跨存储器阵列传送的信号的传播延迟就越短，因此与存储器阵列的存取延迟匹配的时钟频率就越高。第i个单元的存取延迟是从处理器P到单元I的往返传播时间，表示为ti＝2xi或ti＝2i个时钟周期(假设信号在一个时钟周期内通过一个存储单元的距离)。因此，在所述示例中，存取存储单元7所需的时间x7是14个时钟周期。在下面的说明中，使用空间存储器模型比较高速缓存的放置算法。

[0035] 放置算法

[0036] 高速缓存放置算法确定程序地址到存储器位置(通常为高速缓存行)的映射。在常规高速缓存设计中，使用诸如最近最少使用(LRU)之类的放置算法来管理组关联体系结构的相同组(也称为同余类)内的行。在上面给定的空间存储器模型中，放置算法对平均存取延迟具有直接影响，即使整个工作集适合高速缓存并且没有由于冲突的未命中而发生逐出也是如此。可以使用样例存取跟踪观察不同放置算法对平均存取延迟的影响：

[0037] load A、load B、load C、load C、load B、load B。

[0038] 最简单的高速缓存放置算法(直接映射高速缓存设计中采用其变型)将行地址的最低有效位解释为高速缓存行的索引。现在参考图1B，提供了一个实例，其中映射从地址到存储器单元索引，其中地址A的值存储在存储单元7中，地址B的值存储在存储单元10中，地址C的值存储在存储单元2中。要指出的是，上面的映射排除了处理器对值放置距离进行任何控制。可以通过计算样例存取跟踪的平均存取延迟来评估放置算法的有效性。假设高速缓存初始为空，由指令load A导致的第一次存取需要后备存储器存取，对应于地址A的加载值存储在存储单元7中，则产生t7＝14个时钟周期的高速缓存存取延迟。接下来的两个加载指令load B和load C也需要后备存储器存取，而其余的三个指令直接在高速缓存外部提供。下表I中给出了存取延迟(以周期为单位)。

[0039]

[0040] 表I

[0041] 除了三次后备存储器存取所需的周期以外，存取延迟消耗的时钟周期总数为82。因此，每次存取的平均存取延迟(不计后备存储器存取)为82/6＝13.7个周期。

[0042] 可以根据对地址对应值的存取频率将地址映射到存储单元1-15而实现更有效的放置算法。最频繁存取的值将存储到最靠近处理器P的位置以便最小化平均存取延迟。在样例存取跟踪中，最频繁存取的地址为B，它被存取三次。因此，地址B的值应存储在存储单元1中。第二最频繁存取的值位于地址C处，其应存储在存储单元2中，第三最频繁存取的值位于地址A处，其然后存储在存储单元3中，如图1C所示。类似于上表I中所示的对存取延迟的解释，下面的表II总结了图1C中所示的高速缓存值放置的存取延迟。

[0043]

[0044] 表II

[0045] 表II中的存取延迟总和为20个时钟周期，每次存取的平均存取延迟为20/6＝3.33个时钟周期。因此，图1B中所示的直接映射放置的平均存取延迟(每次存取为13.7个周期)是基于图1C中所示的存取频率的放置的四倍多。

[0046] 遗憾的是，通常事先不知道程序的跟踪存取频率。但是，存在一种可证明效率为最佳脱机策略两倍的联机放置策略，称为“移至前端”。移至前端策略将每个请求值移到阵列前端。为了在阵列前端给新值腾出空间，将当前存储在阵列前端的值向后推送到阵列尾端。由于值(例如高速缓存行)的放置是动态的，因此在后续存取时必须搜索每个值。

[0047] 现在参考图2，示出了移至前端试探根据值地址进行的值放置。与图1B和图1C中所示的静态放置不同，图2的动态放置在执行期间使映射适应程序跟踪的存取模式。每次存取时，前三个加载指令根据地址A、B和C从存储器取回值，并将关联的数据移到最前端存储单元1。然后，地址C处的第二次加载在存储单元1中找到请求值(即，找到与C匹配的地址)，从而产生2个时钟周期的最小存取延迟。接下来，地址B处的第二次存取将请求值(连同其地址)从存储单元2移到最前端存储单元1，从而实际上将最前端存储单元1的内容与存储单元2的内容进行交换。地址B处的最后一次存取在单元1中找到请求值，从而产生2个时钟周期的最小存取延迟。下表III示出了图2的放置方案的存取延迟。

[0048]

[0049] 表III

[0050] 存取延迟总和为14个时钟周期，每次存取的平均存取延迟为14/6＝2.3个时钟周期。忽略对主存储器的存取，值得注意的是，移至前端试探产生甚至比基于存取频率的放置更小的平均存取延迟，尽管存取频率放置基于了解整个跟踪，而移至前端放置每次仅考虑一次存取。

[0051] 移至前端试探

[0052] 移至前端试探已被示为在维护列表的上下文中竞争比为2(2-competitive)，因为在因素不变的情况下，移至前端与任何算法(包括那些基于了解整个操作顺序的算法)同样有效。移至前端试探能够组织螺旋高速缓存，从而使因加载、存储或驱逐操作而发生的总存取延迟最差为任何完全了解整个跟踪的算法所产生的存取延迟的两倍。本发明的所示实施例的螺旋高速缓存实现基于移至前端试探的放置算法。其竞争比为2，提供了此实施方式的存取延迟范围，因此提供理论上保证的存取延迟限制。

[0053] 图2进一步示出了活动块和不活动块之间的边界，即，具有存储值的块和空块之间的边界。由于移至前端试探将值放置在螺旋高速缓存的最前端位置并向后推送其他值，直到这些值填满最靠近处理器的第一个未使用位置，因此在线性阵列的前端压缩程序的工作集。如图2中所示，执行第一个加载指令“load A”之后，工作集包括地址A处的值。地址A处的值被放置在块1中，并且边界BD1将螺旋高速缓存分为一组活动块(块1)和一组不活动块(块2-5)。工作集由于随后发出的加载指令“load B”和“load C”而增大，最终导致所述工作集占用三个块(块1-3)。活动块和不活动块之间的边界相应地移动，首先在活动部分中包括两个块(边界BD2)，最后在活动部分中包括三个块(边界BD3)。工作集大于高速缓存大小的程序将边界移到高速缓存尾部块之外，使得活动块组包括螺旋中的所有块，从而将不活动块组的大小减小到零。在图2中，假设工作集小于螺旋高速缓存，使得边界BD3限定活动块和一组非空的不活动块之间的边界。如下面将进一步描述的，可以检测移至前端边界(由于作为放置策略的移至前端试探的“压缩作用”而存在)并将其用于电源管理等。

[0054] 螺旋高速缓存的体系结构

[0055] 根据所示实施例的螺旋高速缓存利用欧几里得空间维度减小最差存取延迟，并提供能够使多个存取流水线化的收缩数据流。在以下示例性实施例中，与螺旋高速缓存的块关联的存储单元本身是一个完整的存储阵列。通常，有效的块设计平衡块阵列的大小，以便连接相邻块的线的传播延迟等于块阵列的存取延迟。所述螺旋高速缓存的一个实施例在每个块内使用快速直接映射高速缓存，并使用高速缓存行作为块之间的数据传输单位。在本申请中，块内的存储器被称为存储器阵列，与块中采用的特定高速缓存体系结构和物理布局无关。如下所述，根据各个块的控制逻辑提供的分布式控制逻辑，所述块进一步在所示实施例中提供移动功能，尽管在备选实施例中，可以使用全局控制逻辑来控制信息流。

[0056] 基本螺旋高速缓存体系结构

[0057] 图3中示出了根据本发明的一个实施例的二维螺旋高速缓存的基本体系结构。示意性高速缓存的螺旋特性可以被形象地表示为围绕块1“缠绕”图1A的线性阵列，以便所述线性阵列现在形成具有曼哈顿布局的阿基米德螺旋线。处理器100(低阶高速缓存或其他数据/指令接收器)连接到螺旋前端的最前端块1。螺旋的尾端(在此实例中，在7×7块矩阵的块49处)连接到后备存储器112，后备存储器112可以是高阶高速缓存、系统存储器、盘存储器或其他数据/指令存储器。在讨论图3中所示的互连网络(多个)之前，更详细地介绍较简单线性阵列的操作很有用。当针对图1A中的线性阵列实施基于移至前端的放置算法时，需要两种功能：(1)将数据移到前端；以及(2)向后推送数据以便为移到前端的项腾出空间。例如，考虑针对图2中地址B的第二个加载指令。在执行第二个load B指令之前，地址-单元映射为C→1、B→2、A→3。要将对应于地址B的值移到前端，必须从前端开始扫描阵列以在阵列中搜索B。当在存储单元2中找到地址B时，向处理器传送关联的数据，从而使存储单元2为空。当对应于地址B的值到达最前端存储单元1时，通过将对应于地址C的值与对应于地址B的值进行交换来“释放”最前端存储单元1。然后向螺旋的尾端传送对应于地址C的值，直到遇到空单元。在此实例中，存储单元2为空，可以容纳对应于地址C的值。通常，连续向后朝着尾端交换存储单元内容，从而实际上向后推送存储单元的现有内容，直到遇到空单元或存储在尾端处的值被换出到后备存储器112中。

[0058] 对于图3中所示的螺旋高速缓存，具有相邻连接的螺旋网络114专用于向后推送操作。执行此操作使螺旋高速缓存能够在每个收缩周期内将一个新数据项移到最前端块1，因为完全占用的螺旋高速缓存可以在每个收缩周期内对每个存储单元的内容执行一次向后推送交换。下文在标题为收缩设计的部分中提供了根据本发明的一个实施例的螺旋高速缓存中的收缩周期的细节。本质上，根据下面进一步描述的流模式自动引导到达块的向后交换和向前移动的数据。位于螺旋高速缓存阵列边缘处的块(即，位于螺旋外环的存储单元)具有向螺旋外侧扩展的任何端口(由相应的电路终止)，以便单个块设计可以根据全局时钟(其提供使螺旋高速缓存工作的收缩脉冲，如下面所述)提供移至前端和向后交换的所有功能。

[0059] 为了支持搜索请求值并将请求值传送到最前端块1，提供了第二个网络，即具有相邻连接的网格式移至前端网络116，如图3中的水平、垂直和斜箭头所示。从高级的角度看，移至前端网络的工作是直接的。例如，当处理器100请求存储在块49中的值时，处理器在最前端块1处发出请求。所述请求沿对角线路径118向(角落)块49传送。在块49中找到请求值，并且所述值(连同值的地址和标志)按指定顺序以xy-路由模式经由块48、47、46、23、8移到最前端块1。将P(a，b，c，d...)定义为值从块a到b、b到c、c到d等的传输路径，要指出的是，根据上述空间存储器模型，沿路径P(1，9，25，49，48，47，46，23，8，1)的传送时间包括10个跳跃或10个周期。具有49个块的线性阵列中的类似存取延迟为t49＝
2×49＝98个周期。因此，二维螺旋组织将减小存取延迟，大约为“未缠绕”螺旋的线性存
1/k
取时间的平方根。通常，具有N个块的k维螺旋的最差存取延迟为θ(N )。在此使用的最差存取延迟指存取与块1具有最大曼哈顿距离的块的延迟。

[0060] 几何重试

[0061] 与线性阵列相比，具有N个块的k维螺旋高速缓存将最差存取延迟从θ(N)减小1/k
到θ(N )。移至前端试探用于在螺旋的前端压缩工作集，并使最频繁存取的数据项保持接近最前端块1。无法通过在每个块处执行查找的搜索策略利用上面的特性，因为这需要将每个请求广播到高速缓存的外部边界，这将导致最差存取延迟。相反，根据本发明的一个实施例的所示螺旋高速缓存实施这样的搜索策略：如果请求在最前端块1中“命中”(即，请求值位于最前端块1中)，则此搜索策略具有最佳存取延迟θ(1)。由于根据上述移至前端放置算法移动存储在螺旋高速缓存中的值，因此处理器100没有指定哪个块存储特定值的信息。因此，每次存取都导致搜索与地址对应的值。在本发明的所示实施例的螺旋高速缓存中，通过将请求传播到存储单元并且然后从找到请求值的存储单元返回请求值来在每个存储单元处执行查找，而不是在表中查找值的位置(如通常在常规关联高速缓冲存储器中执行的那样)。根据上面提供的线性阵列的移至前端竞争结果下的假设，搜索应从最前端块
1向螺旋尾端的最后端块49扫描块。在如图3中所示的二维螺旋中，以径向方式扫描块阵列。首先，执行检查以判定请求值是否存储在最前端存储单元1中。如果所述值不在最前端存储单元1中，则检查包括块2-9的半径为2的“圆环”。如果在块2-9中也未找到所述值，则检查由块10-25形成的半径为3的圆环，以此类推，从而在半径不断增加的圆环上扫描块。向外传播请求被处理为曼哈顿布局。但是应理解，类似的概念可应用于不同于曼哈顿布局的其他布局，本发明并不限于特定的正方形布局或其他形状的布局或者并不一定限于螺旋排列，因为根据本发明的存储设备的行为和电源管理可以由根据本发明的备选实施例的其他布局来提供。

[0062] 本实施例的螺旋高速缓存中的扫描搜索策略的优点是每当在块1中找到请求地址时，它将产生1个周期的最佳存取延迟。由于移至前端策略，应频繁达到这种最佳情形。在此类扫描搜索策略中遇到的一个问题是当同时存在多个存取请求时，向最前端块1移动的值流不可预测。为了避免提供内部缓冲和流控制机制(这会带来不必要的电路面积、电路功率和延迟损失)，根据本发明的一个实施例，可以采用基于几何重试原则的不同搜索策略。图4A-4C示出了根据本发明的一个实施例，移至前端网络116如何支持具有几何重试的s
搜索策略，此搜索策略根据以下原则操作：“如果在半径为2 的区域中没有找到某项，则在s+1 0
半径为2 的区域中重试搜索”。图4A示出了初始半径2 ＝1(r＝1)的过程，其表示在最
1
前端块1中的查找。如果在最前端块1中的查找失败，则搜索半径2 ＝2内的所有块(即，r＝2的块2-9)，并且还再次在半径1内搜索最前端块1，如图4B所示。如果搜索再次失
2
败，则搜索半径再次加倍为2 ＝4，这将覆盖整个螺旋高速缓存(即，r＝4的块1-49)，如图4C所示。如果搜索整个螺旋高速缓存失败，则请求值不在高速缓存中，处理器100必须存取后备存储器112以取回请求值。

[0063] 在图4A-4C中，由大箭头示出了扫描搜索期间通过螺旋高速缓存的数据流。重试0 1 2
半径2 ＝1的特定搜索情形并不重要，重试半径2 ＝2是重试半径2 ＝4所展示的较大情形的一个较小版本。下面仅描述图4C中的右上象限的传送模式，因为其他象限的操作类似并且同时被搜索。根据本发明的所示实施例的螺旋高速缓存中的请求数据流的中心原则是请求可以并且将被复制，而且将在螺旋高速缓存阵列内传送任何给定请求的多个副本，除非最前端块1中的查找立即满足请求。每次重试时将请求的副本发送到每个象限，并且可以在象限内进一步复制请求，如以下进一步详细描述的那样。

[0064] 在螺旋高速缓存的右上角中，请求沿对角线路径从最前端块1向外传播到块43。在块43，将请求同时沿图中向左方向发送到块44以及向下发送到块42，并且因此从请求的一个原始副本生成该请求的两个副本。向左的传送路径一直继续，直到到达块46，然后向下转向最前端块1。遵循所述向下路径，直到到达块40，在此将请求向左导向最前端块1。在向下路径上的每个块中，通过将请求副本发送到左侧而分离出向左导向的路径。从块42，向左导向的路径遍历块21和22，然后在块23处被向下导向。从块41，向左导向的路径遍历块20和7，并在块8处被向下导向。在上述路径遍历中，将访问象限中的每个块，并且使用随请求提供的地址执行查找。

[0065] 所示实施例中采用的几何重试不会更改渐近限，这是由于移至前端或由于螺旋的维度所致。它仅引入不变因素。更明确地说，以下原则有效：

[0066] 1.几何重试最多使最差存取延迟加倍。

[0067] 2.几何重试在4倍扫描存取延迟内成功找到某项。

[0068] 这些陈述简单明了，证明同样适用于更高维度的螺旋高速缓存。

[0069] 收缩设计

[0070] 可以将增加了几何重试机制的基本螺旋体系结构扩展为根据本发明的实施例的收缩体系结构，从而同时提供低存取延迟和高吞吐量。将时间线定义为同时接收一个对特定值的请求(即，包含一个地址的请求)的副本的块的子集。图5示出了请求从高速缓存边界的角落向最前端块1遍历的时间线TL0-TL5。假设请求沿对角线传送到角落块49、43、37和31，则如上所述，在最左侧和最右侧边界块处，请求被复制为水平导向的副本和垂直导向的副本。假设请求在周期0内到达角落块，则它在接下来的周期1内到达时间线TL1上指定的块。例如，左上角落块49中的请求在周期1内到达块26和48。此传送模式将重复执行，直到时间线TL3，其中多个入站请求存在于块46、40、34和28处。要指出的是，到达这些块中的每个块的请求必须携带相同的地址，这是由于请求的计时、请求副本的生成点和请求的导向所致。类似地，块23、8、1、4和15以无冲突的方式操作，因为多个入站请求中的每个请求都在一个周期内携带相同的地址，并且这些块将此地址一直传送到与它们的输出端相连的相邻块。对于块1，输出端为处理器。

[0071] 上述数据流不存在冲突，因为采用移至前端放置的螺旋高速缓存将与每个地址关联的数据存储在最多一个块中。地址根本不在螺旋高速缓存中或者它只被映射到一个块(并且其值被存储在该块中)。因此，最多只有一个请求可以在块中“找到”数据，并将检索的数据移到最前端块1。具有多个输入端的块中的每个块将已检索的数据从其输入端中的一个输入端传送到朝向最前端块1的输出端，或者在每个输入端上接收相同的地址，执行局部查找，并且如果命中，则检索并传送数据，或者如果未命中，则将地址继续传送到导向前端的输出端。收缩数据流能够使多个请求流水线化。将每个请求经由对角线路径从最前端块1发送到阵列的角落块，并且请求经由时间线TL0-TL5移回最前端块1。将对角线路径上的每个块和每个时间线TL0-TL5视为流水线级，图5中的7×7螺旋高速缓存实际上具有10级。所示螺旋高速缓存在每个周期内生成一个请求的吞吐量，并在运行中维持10个请求。通常，N×N螺旋高速缓存(N为奇数)具有[N/2]+2[N/2]或大约3/2N个流水线级。

[0072] 为了在存在几何重试时获得每个周期内一个请求的吞吐量，需要一个附加功能。当对角线上的块同时接收到：1)重试半径等于对角线块的半径的新请求；以及2)同一周期内正在回到最前端块1的返回请求，返回请求必须具有优先权。否则，沿时间线传送的请求的收缩模式将被破坏。在重试半径递增的对角线路径上向外发送新请求，而不是放弃该新请求。此转发的请求在对角线块上的时间线TL4、TL2和TL0的流水线中遇到“气泡(bubble)”时可以转向前端。如果没有可用的气泡，则请求将传送到与时间线TL0关联的边界上的角落，其中结构和功能设计将确保请求向前端返回而无任何冲突。

[0073] 为了执行上述操作，必须调度块内的移至前端和向后推送存取。由于示例性实施例中的螺旋高速缓存的收缩设计允许每个周期内执行一个移至前端查找操作和一个向后推送操作，因此在根据本发明的一个实施例的螺旋高速缓存中，包括微流水线，其具有包含两个时钟周期的工作周期。在第一个时钟周期T1内，执行交换操作swap作为向后推送功能的一部分，从而存储由向后推送网络114提供的输入数据push-in，并提供块(如果非空)的内容作为向后推送网络114上的输出数据push-out。在第二个时钟周期T2内，执行高速缓存查找lookup以实现与移到前端的请求m2f-in关联的搜索功能，并在移至前端网络116上向前移动请求作为请求m2f-out，从而填充与请求关联的数据区域并设置标志(如果查找成功)。图6从一个块的角度示出了高速缓存存取流水线和相邻传送。示例性螺旋高速缓存块阵列设计引入了交换(swap)操作，此操作：(1)应用向后推送地址，(2)读取高速缓存内容，以及(3)写入向后推送数据，这些操作可以在一个时钟周期内执行以满足上述双周期操作，并且可以包括时间借用技术以提供此类操作。如果在特定设计中无法实际地实现交换操作，则可以通过在单周期读取操作之后执行单周期写入操作来实现交换，并且将微流水线的工作周期扩展为三个时钟周期。

[0074] 可以使用不同的几何结构实现根据本发明的其他实施例的平铺式存储器阵列以生成在动态值移动和最近使用值与最前端块的接近度之间具有不同权衡的高速缓存设计。例如，只要请求值始终移至最前端块，便可应用其他试探，包括以最近使用(MRU)计数器或其他策略为条件的试探，而不是在每次存取时向后交换每个非存取值。

[0075] 在上述螺旋应用中，所述特定螺旋高速缓存体系结构具有一些优点，即，它能够使最近使用值尽可能长时间地与处理器(或其他数据接收器)保持紧密的物理接近度。移至前端试探确保最近使用值的存取延迟保持很小，而向后交换试探确保最近使用值与处理器的距离不会远于必要的距离。

[0076] 具有螺旋高速缓存的存储器层级设计

[0077] 上述螺旋高速缓存体系结构使用移至前端试探放置和替换螺旋高速缓存的块中的高速缓存行。所述螺旋高速缓存本身并不被认为是存储器层级。相反，螺旋高速缓存是具有非一致存取延迟的收缩存储器体系结构。尽管螺旋网络为二维或更高维螺旋高速缓存赋予了线性结构，但是该线性结构并不能与线性存储器层级进行比较，因为根据移至前端组织方式，块并未被组织为层，但是它们具有不同的存取延迟。作为类比，图5中的一组钻石形时间线TL0-TL5最接近将虚拟层级映射到螺旋高速缓存，其中每条时间线表示一个层级级别。但是很明显，时间线TL0-TL5与存储器层级中的典型层几乎没有共同之处，因为实现时间线TL0-TL5的结构和控制操作与其他“级别”的操作和结构紧密交织，并且值在各个级别之间动态地移动以执行移至前端和向后推送操作。其他特征进一步将螺旋高速缓存与传统存储器层级区分开。例如，传统存储器层级中的多数高速缓存是包含性的，而螺旋高速缓存中的块具有独占性。在螺旋高速缓存中，某个特定值一次至多存在于一个块中。但是，上述区分都不排除使用螺旋高速缓存实现传统存储器层级中的高速缓存级别，如下面所示。

[0078] 可以使用螺旋高速缓存替换传统存储器层级中的一个或多个高速缓存。参考图7C，该图示出了根据本发明的实施例，其中传统层级(例如，图7A中示出的层级)的L2高速缓存实现为螺旋高速缓存63A的存储器层级。L2螺旋高速缓存63A以提供与传统独占L2高速缓存相同功能的方式存储值，但是具有上述的伴随性能益处。但是，螺旋高速缓存和其他高速缓存级别之间存在接口差异。所示的L2螺旋高速缓存63A包含49个块，这与上面图3中所示的螺旋高速缓存相同，但是为了清晰起见，仅示出了块1和49。L1高速缓存62和L2螺旋高速缓存63A之间的接口为读/写端口，由L1高速缓存62进行控制。因为L2螺旋高速缓存63A支持多个未完成请求，所以L1高速缓存62可以向L2螺旋高速缓存63A发出多个请求，无需等待前面的请求完成。进而，L2螺旋高速缓存63A和L3高速缓存64之间的接口包括两个独立的端口。L2螺旋高速缓存63A的块1与L3高速缓存64的读取端口相连以请求在L2螺旋高速缓存63A中未命中的数据。向后推送网络将L2螺旋高速缓存63A的尾部块49与L3高速缓存64的写入端口相连。由于L2螺旋高速缓存63A可以同时向L3高速缓存64发出读写请求，所以L3高速缓存64必须在请求之间进行仲裁，或者实现能够同时处理一个读取请求和一个写入请求的双端口结构。此外，由于L3高速缓存
64一般比L2螺旋高速缓存63A慢，因此在L2螺旋高速缓存63A和L3高速缓存64之间需要流控制机制。

[0079] 尽管存在以上指出的螺旋高速缓存和传统存储器层级之间的差异，但是螺旋高速缓存的特性可以应用于包括存储器层级的其他存储器设计。现在参考图7A，示出了其中可集成图3的螺旋高速缓存的特性的分层式存储器系统。处理器60耦合到(或包括)可以有效地充当0级高速缓存的寄存器文件61，其后是线性高速缓存阵列，该阵列从L1高速缓存62开始，通过L2高速缓存63和L3高速缓存64，最后到达位于存储器层级远端的后备存储器65。尽管传统高速缓存的容量和存取时间均随与处理器60的距离增加(如图中通过描绘高速缓存62-64及后备存储器65的方块的相对大小所示)，但是所示层级可以被视为上面参考图1A-1C描述的线性阵列的一个实例。如果针对传统层级中使用的放置策略采用移至前端试探并且所有高速缓存都是独占的，则移至前端放置将使用L1高速缓存62(或可选地使用寄存器文件61)作为最前端块。由于高速缓存62-64的存取时间是不同的，因此跨高速缓存边界应用收缩设计没有意义。相反，使用基于流控制缓冲器的更通用的网络体系结构，如图7B所示。

[0080] 图7B的存储器层级包括图7A中示出的方块，并且还包括向后推送缓冲器BF1A-BFNA以及向前移动缓冲器BF1B-BFNB，所述缓冲器包括关联的流控制逻辑和信令以阻止缓冲器溢出并保持高速缓存62-64的值进入速率和值离开速率之间的平衡。当处理器60向后备存储器65发送加载请求时，所述加载请求依次被发送到每个高速缓存62-64，直到发生命中为止。当所述请求到达高速缓存62-64之一时，便执行查找操作。在命中的情况下，从发生命中的高速缓存删除所请求的数据(使该高速缓存成为独占的)，并且将数据注入朝向处理器60的网络的返回路径。否则，如果发生未命中，所述请求被转发到距离处理器60稍远的下一级高速缓存。由于后备存储器65包含所有地址的值，因此保证在线性阵列的某一点处满足所有请求。当数据到达返回到L1高速缓存62的路径时，数据被存储，从而完成移至前端操作。当L1高速缓存62中出现冲突时(即，L1高速缓存62已满)，通过将存储请求发送到距离处理器60稍远的下一级高速缓存来向后推送当前存储在L1高速缓存62中的数据。存储请求由高速缓存62-64处理，其方式与上述螺旋高速缓存的螺旋网络内的向后推送信号类似。

[0081] 在缓冲网络上实现移至前端替换试探受制于两个复杂因素。第一，即使具有大量的缓冲资源，也必须使用流控制机制来避免溢出。流控制网络的延迟通常总是高于收缩网络的延迟。第二，防止未检测到的请求和返回数据逆流所需的返回路径上的冲突解决和缓冲器检查逻辑比实现螺旋高速缓存设计中的流控制的逻辑复杂得多。图7B中示出的线性网络可以扩展为更高维度的网络，例如二维或三维网格，以便支持二维和三维设计。但是，非一致高速缓存大小增加了此类“空间填充”存储器设计的复杂性，并且可能很难提供此类体系结构的理论性能保证。

[0082] 电源管理

[0083] 上述螺旋高速缓存提供了具有低存取延迟的大型高速缓冲存储器。大型高速缓存可以处理较大的工作集，例如，指令集和/或与给定软件进程关联的数据，但是，大型高速缓存在针对具有较小工作集的程序执行时浪费了功率，因为所述工作集仅占用高速缓存的一小部分。螺旋高速缓存的结构极大地方便了动态调整活动高速缓存区域的大小以适应不同的工作集大小。螺旋网络为任意维度的高速缓存设计赋予了线性结构。所述线性结构标识移至前端放置算法的头部(最前端块)和尾部。如上所示，移至前端试探具有在螺旋头部压缩程序或压缩多程序环境中多个程序的工作集的效果。对于工作集小于螺旋高速缓存容量的程序，压缩效果尤其明显。然后，可以将螺旋高速缓存分为两个部分：位于螺旋头部的包含工作集的活动部分，以及位于螺旋尾部的块存储未被使用的不活动部分。如以上参考图2的线性阵列所述，螺旋高速缓存的压缩可用于降低螺旋高速缓存的功耗。具体而言，在非常大的螺旋高速缓存中，可以针对具有小工作集的进程/程序降低功耗。

[0084] 现在参考图8A，其中示出了根据本发明的一个实施例的在螺旋高速缓存中使用的电源管理方案。通过可按块设置的边界BD将为简洁而示为线性阵列的螺旋高速缓存活动部分101A与不活动部分101B分开。活动部分101A是最接近处理器100的部分，而不活动部分101B是最接近后备存储器112的部分。不活动部分101B内的块114的存储阵列被置于断电状态。在所示的实施例中，不需要对边界BD的位置以及活动部分101A和不活动部分101B的省电/断电状态进行全局控制。块114可以根据在块本身处观察到的活动确定何时进入省电状态，因此不需要外部逻辑或控制算法。下面将参考图9进一步详细描述块确定的电源管理的示意性算法。当边界BD移向处理器100时，必须将进入不活动状态的块114中存储的所有值都逐出到后备存储器112(其可以是距离处理器110稍远的下一级高速缓存)。

[0085] 现在参考图8B，其中示出了根据本发明的一个备选实施例的在螺旋高速缓存中使用的电源管理方案。图8B与图8A类似，因此下文仅描述它们的不同之处。在图8B中，边界BD的位置由全局电源控制逻辑116设置，控制逻辑116可以根据事前信息或指示当前工作集大小的度量选择活动部分101A的大小，从而决定所需的螺旋高速缓存“大小”。在图8A和图8B的实施例中，可以支持多个省电级别，其中螺旋高速缓存被分为两个以上的部分，这在激活处于中间省电模式(例如，低功耗“休眠”模式)的部分中的块的存取延迟小于后备存储器112的存取延迟时具有优势。如果块支持多个省电模式，则可以以类似于上面针对断电-供电状态示出的方式按块调整各部分之间的边界。

[0086] 现在参考图9，其中示出了根据本发明的一个实施例的螺旋高速缓存中的块的电源管理算法。所述算法在每个块内执行并且在供电和断电状态之间切换块存储器阵列的电源。移至前端和向后推送网络保持活动状态。每个块维护两个计数器：命中计数器HT和向后推送计数器PB。在每个工作周期内，每个块针对工作周期更新向后推送或移至前端操作涉及的计数器。接收到操作请求时(步骤140)，如果块的存储器处于不活动(断电)状态(决策141)，并且如果操作为向后推送请求(决策152)，则递增局部向后推送计数器PB(步骤153)。如果请求为M2F请求(决策154)，则所述M2F请求被转发到下一个块(步骤155)。如果局部向后推送计数器PB的值大于第一阈值ThreshPB’(决策156)，则为块的存储器供电并重置计数器PB(步骤157)。如果块的存储器处于活动(供电)状态(决策141)，并且请求为M2F查找请求(决策142)，则执行M2F查找操作(步骤143)，如果查找命中(决策
144)，则递增局部命中计数器HT(步骤145)。如果块的存储器处于活动(供电)状态(决策141)，并且请求为向后推送请求(决策146)，则执行向后推送操作(步骤147)并递增局部向后推送命中计数器PB(步骤148)。如果块的存储器处于活动(供电)状态(决策
141)，并且如果在向后推送计数器PB低于第二更低的向后推送阈值ThreshPB的同时命中计数器HT低于命中阈值ThreshHT(决策149)，则推出块存储器中的所有脏值(步骤150)并断开块中的存储阵列的电源(步骤151)。将在每个工作周期内重复算法步骤140-157，直到电源管理操作暂停或系统停机(决策158)。上述操作的效果是当接通阵列的电源时，块对移至前端查找导致的命中数和从螺旋网络接收的行数进行计数。如果命中率和推入率(一段时间内)小于给定阈值，则块没有对程序执行起到积极作用。因此，应从图8A的活动部分101A删除该块。在执行此操作之前，必须驱逐所有“脏”数据(即，已经根据后备存储器112中包含的相应值修改的数据)。当块未接收到来自螺旋网络的推入时，可通过在工作周期内将脏数据向外推出到螺旋尾端来执行驱逐。当阵列不再包含任何脏数据时，便可安全地断开存储器阵列的电源。包含已断电存储器阵列的块借助向后推送计数器监视螺旋上的向后推送活动。如果一段时间内的向后推送数超过给定阈值，则该块可以向程序执行积极贡献其存储器阵列。在此情况下，所述块接通其存储器阵列的电源，并由于到达移至前端网络的请求而恢复存储推入数据及恢复执行查找。

[0087] 螺旋高速缓存的设计考虑和特性

[0088] 总之，上述根据本发明的一个实施例的螺旋高速缓存具有若干特性，它们为设计者提供了灵活性并提供了其他优点，如下所述：

[0089] 1.螺旋高速缓存是平铺式体系结构。与传统分层存储器设计不同，这种体系结构可相对容易地复制块以实现所需大小或所需容量的螺旋高速缓存。

[0090] 2.块中存储器阵列的大小可由设计者自行决定以平衡存取延迟、吞吐量以及功耗。阵列越小，其存取时间就越短，整个螺旋高速缓存速度就越快。此外，当给定容量的螺旋高速缓存基于较小的阵列时，块的数目将增加，这会增加流水线深度并导致更高的吞吐量。但是，小型块的数量较多会增加最差存取延迟。当最差存取延迟接近后备存储器的延迟时，螺旋高速缓存的性能增益会减小，对于任何其他高速缓存体系结构而言都将如此。如果首先考虑线效率，则阵列大小一般应单纯地根据技术约束进行选择，以使跨块的传播延迟等于块内阵列的存取延迟。

[0091] 3.移至前端试探充当将高速缓存行放入块的竞争比为2的放置(替换)策略。没有其他高速缓存体系结构能提供这样的理论性能保证。

[0092] 4.移至前端试探压缩螺旋网络头部的工作集。这种自组织特性意味着较小的平均存取延迟和低功耗。另外要指出的是，所谓的“高速缓存参数无关算法”要归功于螺旋高速缓存体系结构。与传统层级相比，优势不一定是性能增益，因为高速缓存参数无关算法对于传统高速缓存也很有效。通过仿真观察到，在采用传统存储器层级的系统上执行效果非常差的应用在螺旋高速缓存上显示出巨大的性能增益。但是，高速缓存参数无关算法能够执行明显有效的移至前端压缩，这最小化了平均存取延迟。

[0093] 5.螺旋高速缓存的收缩体系结构通过采用移至前端放置策略和具有几何重试的搜索方案，避免了早期收缩设计中引发的每个存取的最差存取延迟。此外，螺旋高速缓存避免了一般流水线式分层存储器体系结构所需的缓冲和流控制机制的实现开销。相反，移至前端试探使得平均存取延迟接近当仅存取最前端块时发生的最佳存取延迟。

[0094] 6.平铺式体系结构固有地是流水线式的。这种流水线能力有利于高吞吐量存储器且在运行中支持多个存取。包括超标量处理器、多线程处理器或并行(多核)体系结构在内的各种处理器体系结构均能利用这种特性。通过交织多个线程或处理器的存取而在它们之间共享螺旋高速缓存可以提供内在一致的存储器体系结构。

[0095] 7.在每个块的阵列内将向后推送交换操作与移至前端查找进行交织的需要导致微流水线式设计，这种设计的工作周期可以是两个或三个时钟周期，具体取决于所述阵列是否支持单周期交换操作。如果关心由微流水线导致的延迟，可以通过使高速缓存的时钟频率相对于处理器增加一倍或两倍来避免延迟，或者可以借助在处理器与螺旋高速缓存之间布置的附加L1高速缓存来屏蔽延迟。

[0096] 8.所述螺旋高速缓存能够利用欧几里得空间的维度。更简单地说，具有N个块的k维螺旋高速缓存的最差存取延迟为

[0097] 9.包含N个块的螺旋高速缓存的行为类似于N-路组关联高速缓存。这假设每个块包括直接映射高速缓存。螺旋网络的移至前端试探与向后推送功能一起有效地实现每个(地址)索引的LRU栈。使用直接映射高速缓存不会导致传统组关联高速缓存中发现的显式LRU簿记成本。但是，如果每个块内的存储器阵列被组织为n路组关联高速缓存，则螺旋高速缓存将提供与(nN)路组关联高速缓存等效的关联性。

[0098] 10.螺旋网络的线性结构与移至前端试探的压缩作用一起促进了分散式电源管理。螺旋头部的活动子集中的块为高速缓存容量贡献它们的阵列，而工作集以外的不活动块可以安全地关闭它们的存储器阵列的电源。在保持包含特性的分层存储器组织中不能实现这种自适应电源管理。