处理器片上缓存内及时局部性环境分析

胡九川，范东睿， 程建聪， 严 龙， 彭 燕， 叶笑春， 李灵枝， 钟海斌

(1.北京交通大学 计算机科学与技术学院，北京 100044； 2.中国科学院计算技术研究所 计算机体系结构国家重点实验室，北京 100190)

在计算机运行过程中，处理器不断在各个指令或数据之间切换执行焦点.如果这些被切换的指令或数据能够在一个相对的时间片内动态地保留在容量十分有限的处理器片上缓存内，那么这些指令或数据组成的群组便具有了满足处理器内核访存需求的局部性的特色，提高了处理器内核的访存效率，消减了处理器内核去内存访问指令和数据的延迟.由于缓存是临近处理器内核的功能部件，这样的局部性就具有了及时的特点.在这个执行时间片内，这些被切换的指令或数据之间具备了满足处理器内核访存需求的时间和空间联系[1-5].及时局部性(In-Time Locality)概括了指令和数据之间存在的客观联系，可以将处理器的执行过程抽象为执行焦点在不同的具有局部性的指令或数据族群之间进行切换的过程.

这种客观存在的及时局部性来源于程序执行逻辑的内在规定.指令执行顺序、数据存储结构与形式的安排是程序这个逻辑复合体的基本构件，在根本上决定了指令之间、数据之间不可割舍的时空联系.这种时空联系自然需要在指令和数据从内存迁往片上缓存的过程得到保持和维护，如此才能够在处理器片上缓存内建立有利于处理器访存的及时局部性环境.所以，如何在从内存迁往片上缓存中保持和维护指令或数据之间存在的局部性便成为一个需要深入研究分析的问题.分析研究指令和数据在片上缓存和内存之间往返迁移的规律、最大限度保持指令和数据之间的时间和空间联系具有重要的现实意义.

一般地，在指令和数据迁移进出处理器时，它们之间存在的局部性联系很可能由于它们在内存和片上缓存的存储位置的改变、共存于缓存中的其他指令或数据的占位而发生变化，使得在处理器原计划遵照程序内在的逻辑展开运算时，前来向处理器内核“报到”的指令或数据可能并不是处理器内核所需的，导致这内在的程序执行逻辑面临具体展开的困境，形成需求错位的局面.这样的矛盾局面产生的根源是由于片上缓存容量十分有限，而要进入缓存的指令和数据量却是巨大的、乃至逻辑上是无限的，片上缓存中的指令和数据需要不断地从内存中迁移更新才能将所有指令和数据从内存中推到处理器核的面前，方便处理器核的访问.因此，在处理器内核访问指令或数据时，应该将与之存在时空关系的其它指令、数据一起组合为一个临时的整体迁移到处理器的片上缓存内，尽量保持指令或数据之间的时空联系，并且将指令之间、数据之间的时空关系转化为指令、数据在片上缓存中的分布形态.控制此分布形态必然有助于提高处理器内核的访存命中率、减缓访存延迟，营造出片上及时局部性环境.

根据上面的分析，可以发现片上及时局部性环境的两个基本要素：第一、处理器所需要的指令或数据可以及时在片上寄存器或缓存内找到；第二、处理器所需要的指令或数据可以在片上寄存器或缓存中就近找到.因此，为了提高处理器访存效率，消减访存延迟，营造及时局部性环境，指令和数据不但要迁移到片上缓存内，而且要确保指令和数据的局部性在一定的时间内不被消解.

如果将指令和数据规约为一个个及时局部组，将指令和数据组织在及时局部组内，那么处理器内核在各个指令和数据之间切换执行焦点的情形可以进一步清晰化为执行焦点在各个及时局部组之间切换，于是营造及时局部环境可以以及时局部组为基本构件.实际上，只有处理器内核的执行焦点遍历完一个程序的所有及时局部组，程序执行的整体效应才会出现.如果及时局部组内的指令或数据都能够满足处理器内核的访存需要，那在整体上程序的执行将是一个理想状态.在这个过程中，不但要关心及时局部组在迁移过程中产生的变化，而且还要关注各个及时局部组在迁移过程中产生的相互影响.

及时局部组是一个以处理器访存焦点即当前被访问的指令或数据为中心、涵盖一定范围内的指令或数据组成的、具有时空关联关系的指令或数据族群.在本文作者以及时局部组内的指令或数据之间的关联关系在迁移过程中发生的变化为入手点，研究分析及时局部环境内在机制，探索理想状态产生的前提条件.运用抽象的数学方法研究分析指令或数据在处理器片上缓存和内存之间往返迁移的规律，寻找迁移过程中保持指令或数据及时局部性的前提条件.为了行文简便，在本文中指令和数据统称为数据.

1 内存、片上缓存的抽象描述

1.1 内存、地址和基本寻址单位

地址是计算机体系结构的核心概念，地址的结构组成规定着计算机内存和片上缓存的关联法则[3,6].由于存储空间是描述地址结构及其形式的基础，所以，先给出存储空间的定义.设m为自然数，D={0,1}，称集合Dm={(dl,d2,…,dm)|di∈D,i=1,2,3,…,m}为存储空间，m为存储空间维数.存储空间维数决定存储空间的容量.由于m维存储空间中的向量可以构成m位的二进制数，存储空间中的所有向量构成一个由m位二进制数组成、按数值大小关系排列顺序的全序集合[7]，这种序关系本质上为地址的序关系.

定义1设m为自然数，Dm为m维的存储空间，≤为存储空间中的全序关系，称集合{Dm,≤}为地址空间，地址空间中的向量为地址.

定义2设m,n,k为自然数，m=kn，Dn为地址空间，Dm为存储空间，设

Dn×Dm={(a1,a2,…,an,d1,d2,…,dm)}

其中

(a1,a2,…,an)∈Dn,(d1,d2,…,dm)∈Dm

则称Dn×Dm为内存；Dm中的向量为存储槽，内存空间中的向量为基本寻址单位.

从定义2可知，基本寻址单位泛指存储在内存中的指令或数据.两个基本寻址单位的距离可以定义为地址之间的距离.

1.2 片上缓存

处理器片上缓存可以视为“漂浮”在内存上面的视窗，内存中的数据只能在视窗“飞临”其上的条件下才可以出现在视窗里.数据在内存中存储的位置与其在缓存中停留的位置之间的呼应关系便是缓存和内存的关联关系，即全相联、直接相连和组相联.这样的关联关系影响数据从内存中迁移来缓存后的在缓存内的分布形态.缓存和内存全相联需要复杂的逻辑电路，但是数据来到缓存里可以自由进驻缓存槽，而直接相连和组相联的逻辑电路相对简单，数据来到缓存进驻缓存槽需要遵循关联约定.为描述这关联约定，下面给出片上缓存的定义.

定义3设m,n,p,q为自然数，Dp×Dq和Dn×Dm为内存.如果映射

Q:Dn×Dm→Dp×Dq

使得对内存Dn×Dm中任意的基本寻址单位

u=(a1,a2,…,an,d1,d2,…,dm)

存在内存Dp×Dq中的基本寻址单位

v=(i1,i2,…,ip,c1,c2,…,cq)

的地址满足：

a12n-1+a22n-2+…+an=g2p+I

其中g为自然数，2p>I，

I=i12p-1+i22p-2+…+ip

则称内存Dp×Dq为内存Dn×Dm的常规缓存，称I为基本寻址单位在常规缓存Dp×Dq中的索引号, 映射Q为从Dn×Dm到Dp×Dq为常规相联.

将一个大容量结构内的数据纳入到一个容量相对十分小的结构内的基本方法是将大容量结构内的数据分成等价类，使得等价类中的数据能够出现在这个容量相对小的结构“视窗”之中，如此才能在逻辑意义上将一个大容量结构置于小容量结构之中.目前，片上缓存与内存之间的关联结构主要是通过等价分类实现的[3,6].定义3揭示了该等价类方法的本质，其中基本寻址单位在缓存中的索引号就是通过模运算折算出来，模运算是对数值进行等价分类的常用方法.

图1是一个将内存的数据置于缓存的原理解释图.按照定义3中规定的模运算，内存中数据的地址被予以换算，模运算所得的余数为数据被迁移到缓存中的索引号，该索引号标注了这些数据在缓存中所安置的位置，称为存储槽索引号.例如，以缓存容量值c=7为模数，对数值为9的地址进行模运算得到余数为2，则位于内存位置9上的数据被迁移到缓存中后，其在缓存中的索引号为2.图1显示了从内存地址到片上缓存地址(缓存槽索引号)之间的对应关系.

图1 内存和缓存关联关系示意图Fig.1 Schematic diagram of memory and cache association

不难发现，内存空间Dn×Dm中的基本寻址单位的地址u与另一个内存空间Dp×Dq的容量2p做模运算，所得余数正好为基本寻址单位v在内存空间Dp×Dq里的地址，即缓存槽索引号.又根据拓扑学的知识[7-8]，模运算将内存空间中的所有基本寻址单位分成2p个等价类.这样的等价类可以为确定片上缓存容量提供启发.

缓存是层次结构意义上的内存，且靠近处理器核更近，数据局部组的及时性只有在其进驻缓存后才能显著地呈现出来.本文的讨论仅围绕常规缓存展开.

1.3 访存焦点与及时局部性

处理器当前访存所指向的内存位置称为处理器的访存焦点.与访存焦点存在局部性联系的其他数据具有一定程度的焦点色彩.这种焦点关联在实践中的表现是，当缓存内的数据被访问后，该数据或被再次访问，或与该数据相邻的数据将被访问.所以作为焦点和焦点化的数据应作为一整体迁移到缓存中来，使数据的位置相互靠拢汇聚起来，处理器内核因此能方便定位到它们.

定义4设m,n为自然数，r为非负整数，

u=(a1,a2,…,an,d1,d2,…,dm)

为内存Dn×Dm中任意一个基本寻址单位，称集合

N(u,r)={u′:e(u-u′)

为以基本寻址单位u为中心的邻域.其中，e(u-u')为两个基本可寻址单位u和u′之间的向量距离.

以一个处理器内核的当前访存焦点u为中心，以距离r为半径，可在内存中划定一个不超出此半径的对称区域，区域内汇集了一组按照地址顺序排列的基本寻址单位，访存焦点位于队列正中央，该对称区域构成一个以访存焦点为中心的邻域N(u,r)，该邻域是一个对称及时局部组.

在处理器运行中，访存焦点u可能被多次访问，多次成为处理器的执行焦点，执行焦点短暂保持在相对固定位置的处理器运行态势反映的正是时间局部性(Time Locality) .当访存焦点发生改变，处理器要访问邻域N(u,r)内其他的基本寻址单位，且处理器的执行焦点不超出邻域范围的微漂移执行态势反映的正是空间局部性(Space Locality).执行焦点在固定位置重复出现，或相对于固定位置产生微漂移的执行态势说明了及时局部组内数据之间具有相对突出的汇聚性，这种瞬息变化的汇集性是及时局部性的动态形式.

以基本寻址单位的邻域为媒介，可营造处理器内核访问数据的及时局部性环境，完善片上缓存内数据迁移的机制.这意味将改进计算性能的探索不再静止停留在缓存结构层面，而是上升到动态利用数据局部性关联的新层面.局部性跨度是反映局部性状态变化的指标.

定义5设m,n,p,q为自然数，r为非负整数，

u=(a1,a2,…,an,d1,d2,…,dm)

为内存Dn×Dm中任意一个基本寻址单位,

Q:Dn×Dm→Dp×Dq

为一个常规相联，称

Q(u+r)-Q(u-r)

为以基本寻址单位u为中心的局部性跨度.

局部性跨度是一个刻画数据局部性涉及范围的尺度，意味那些存在于跨度之外的数据不再纳入局部性考虑的范围.在数据及时局部组从内存迁往片上缓存的过程中，局部性跨度可能因片上缓存和内存的关联关系而发生改变.

2 数据迁移分析

为营造在片上缓存内服务处理器内核访存的及时局部性环境，作为整体迁移的及时局部组邻域N(u,r)内数据之间的局部性关系应该保持稳定，即保持邻域结构的拓扑结构[7]稳定，不被迁移所改变.故引入如下概念.

定义6设Dp×Dq,Dn×Dm为内存,m,n,p,q为自然数.对任意的u∈Dn×Dm,如果映射

s:Dn×Dm→Dp×Dq

满足：对任意的u′∈N(u,r),有

s(u')∈N(s(u),r)

则称s为从内存Dn×Dm到内存Dp×Dq的一个局部性保持迁移.

在数据从内存迁移到缓存的过程中，及时局部组内数据的局部性关系可能会发生形变，造成及时局部组邻域被分拆或折叠，详见下面的实例.

例1 图2显示了一个常规缓存中缓存槽索引号和内存地址的对应关系.例如索引号为3的缓存槽可以接纳来自内存地址为3、11、19、27、…的数据.以任意一个内存地址为中心，取邻域半径为2，可以构成一个以该地址为中心的及时局部组.

图2 片上缓存中数据分配示意图Fig.2 Diagram of data allocation in the on-chip cache

在图2中，以那些分别以索引号为2、3、4、5关联的地址上的数据为中心的及时局部组可以保持局部性地迁移到缓存内.例如，以地址20为中心的局部组占据一个连续的地址段18、19、20、21、22，这些内存地址上的数据之间的关联关系可以不被分拆地迁移到缓存内一组相邻索引号2、3、4、5、6所指定的缓存槽内.然而，以那些只能和索引号为0、1、6、7的地址上的数据为中心的及时局部组却不能保持其局部性迁移到缓存内.例如，以地址15为中心的及时局部组占据一个连续地址段13、14、15、16、17，该地址段上的数据被迁移到缓存内一组由不相邻索引号5、6、7、0、1所指定的片上缓存槽内.索引号为5的缓存槽与索引号为1的缓存槽之间的距离为3，超过了及时局部组的邻域半径2.

及时局部组迁移后其邻域半径被拉长的情形称为局部性分拆 .反之，如果及时局部组半径过大，会出现一个缓存槽被来自内存中地址不同的两个数据同时占据的不合理情形.

例2 在图2中，选择及时局部组邻域半径为6，以地址22为中心的及时局部组占据一个连续地址段16、…、21、22、23、…、28，这些地址上的数据被迁移到缓存内后，一些缓存槽将同时被两个来自不同内存地址的数据所占据.例如图2中索引号为3的缓存槽被来自内存地址为19，27的不同数据同时占据，这显然是不合理的.

同一缓存槽被来自不同地址的数据所同时占领的情形称为及时局部性折叠.局部性折叠是数据过度靠拢的畸形形态，在数据从内存迁往缓存的过程中，应杜绝局部性折叠.

定理1设m,n,p,q为自然数，内存Dp×Dq为内存Dn×Dm的常规缓存，r为对称及时局部组的半径，则发生局部性折叠的充分必要条件是r≥c/2.其中，c为缓存Dp×Dq容量，c=2p.

证明1 先证明必要条件.任取内存Dn×Dm里一个基本寻址单位，设其在常规缓存Dp×Dq内的索引号为h.如果出现局部组折叠，则只能出现图3和图4所示的两种情形.在图3中，索引号为h的缓存槽到索引号为c的缓存槽的距离(c-h)小于及时局部组的邻域半径r，且

r-(c-h)≥h-r

于是r-c+h≥h-r，则2r≥c，即

r≥c/2

同理，在图3(b)中，索引号为h的缓存槽到索引号为0的缓存槽的距离h小于及时局部组的邻域半径r且

r-h≥c-(h+r)

于是r-h≥c-h-r，则2r≥c，即

r≥c/2

所以，如果发生局部性折叠，则必然有r≥c/2.

下面证明充分条件.假设不发生局部性折叠，则r-(c-h)

r

所以，如果r≥c/2，则一定发生局部性折叠.

(a)高地址端

(b)低地址端图3 靠近缓存地址端Fig.3 Close to the cache address end

定理2设m,n,p,q为自然数，内存Dp×Dq为内存Dn×Dm的常规缓存，r为对称及时局部组的半径，则不发生局部性折叠的充分必要条件是

r

其中，c为缓存Dp×Dq容量，c=2p.

证明2 由定理1可以推得定理2成立.

根据定理1和定理2，只要及时局部组邻域半径的数值不超过缓存容量的一半，局部性折叠就不会发生.然而定理3指出局部性分拆必然经常发生.

定理3设Q为从内存Dn×Dm到缓存Dp×Dq的常规相联，m,n,p,q为自然数，r为及时局部组邻域半径，c为缓存Dp×Dq的容量，c=2p，0

证明3 根据0，当0

当r

(a) h

(b) r

(c) c-r

定理4设Q为从内存Dn×Dm到缓存Dp×Dq的常规相联，m,n,p,q为自然数，r为局部组邻域半径，c为缓存Dp×Dq的容量，c=2p，r

证明4 任取基本寻址单位u′∈N(u,r)，设u′在缓存Dp×Dq中的缓存槽索引号为h′，u，u′在内存中的地址分别是Du,Du′,根据定义3必然存在正整数g，g′满足

Du=gc+h

Du′=g′c+h′

其中，r

Du-Du=(g-g′)c+h-h′

不妨设g>g′>0,于是

如果g≠g′，那么产生矛盾.因此，g=g′,r>h-h′.Q是局部性保持迁移.

根据定理4，只要控制内存地址的取值范围和及时局部组邻域半径规模，常规相联可以使得及时局部组在从一个存储空间迁往另一个存储空间的过程中，及时局部组内各个数据之间的局部性关系不被破坏，也意味当前处理器中片上缓存和内存之间的相联机制能够实现保持数据局部性的迁移.

3 及时局部性环境分析

3.1 计算过程与及时局部组

计算展开的过程是一个在计算机内的能量传递改变物质载体能量状态的控制过程，更是一个实践活动逻辑展开的过程；逻辑关系的衔接决定了这个过程中产生的中间结果、最终结果必须予以保存.所以，寄存器、片上缓存、内存的客观存在是计算的内在规定.

表达逻辑过程的基本工具是指令集，指令集决定着处理器内部的数据通路和流水线的基本形态.内存、缓存、数据通路中和流水线上散布的数据却只能伴随计算过程的展开顺势而动.高性能计算要求来到片上缓存的数据能够满足处理器内核的访存需要.这实质是要求在高速计算的条件下，处理器的访存焦点能够按照程序的执行逻辑在不同的数据之间进行顺畅地切换.如果顺畅地切换访存焦点能够在片上缓存里实现，那么处理器内核访存延迟会大幅度缩短，计算性能得到提高.为了最大限度地实现访存焦点的顺畅切换，应该改变数据在处理器运行过程中“顺势而动”的被动的局面，使之呈现“迎势而行”的主动姿态.这就是营造片上缓存中及时局部性环境的根本原因.

在存储容量十分有限的缓存里营造及时局部性环境，需要保证有效数据持续地来到片上缓存中.因此，控制数据在内存和缓存之间往来迁移的方式方法是关键.为了确保迁移数据的功效，自然需要将具有局部性关联关系的数据一起迁往缓存.所以，要研究分析数据局部性、迁移数据的片上环境.

在前面的工作中分析了数据局部性存在的根源，抽象概括了当前片上缓存和内存的关联结构的本质特征，从处理器内核的访存姿态揭示了数据及时局部性的时间和空间含义，并以反映数据局部性本质的抽象概念局部组邻域为工具描述了数据及时局部性在数据迁移过程中发生变化的基本规律.

3.2 及时局部组的分拆

从第3节中给出的研究结果可以发现：数据及时局部性是一个以处理器内核的访存焦点为原点的时空视野.由于内存中存储单元是线性排列的，数据及时局部性被抽象为一个邻域形式来描述以访存焦点为中心的覆盖范围.这种邻域覆盖下的数据被迁移到片上缓存里后，邻域形式要么保持，要么发生分拆(由于缓存容量远远小于内存，发生及时局部组邻域折叠只是理论上有可能，实践上几乎不可能)，但是，具有局部性关系的数据都以邻域为单位齐聚到了片上缓存里，来到了处理器内核的周边.不论这些数据是否聚集在一起，对于处理器内核来讲，构成片上缓存的逻辑电路可以让处理器内核瞬间访问到邻域中的任何数据，所以，能够及时访问这些数据，意味局部组内聚的及时性在处理器的片上缓存中可以成为及时访问的现实.

这种可及时地访问的现实能否在一段时间内在缓存中存在下去与及时局部组邻域分拆与否有关.处理器内核对一个及时局部组的访问是一个计算过程里的一个短暂瞬间，这些对各个及时局部组访问的短暂瞬间串接起来形成一个以时间度量的过程.在这个过程中，处理器内核的访存过程可以先粗颗粒地划分为对及时局部组的逐个访问，然后在对每个及时局部组的访问中细颗粒地划分为对每个数据的访问.当处理器的访存焦点不是在一个及时局部组内的各个数据之间切换,而是在各个及时局部组之间切换时，作为切换目标的及时局部组会存在两种不理想的可能:要么该及时局部组未曾被迁移到缓存中来，要么该及时局部组曾经被迁移到缓存内却被后来迁移到缓存的其他及时局部组所覆盖.如果及时局部组在缓存内发生分拆，那么及时局部组被覆盖的可能性降低，于是及时局部组内聚的可及时访问的现实性在缓存内存在下去的可能性就会提高.

3.3 及时局部组的覆盖

尽管由于处理器片上缓存容量有限，迁来缓存的数据最终是要被后续到来的数据所覆盖的.但是，控制数据在片上缓存内的分布，保证数据在一段时间内不被覆盖是可行的.如果片上缓存和内存之间的关联关系是满足定义3要求的常规相联关系，那么通过控制及时局部组邻域半径或者及时局部性跨度，利用及时局部组的分拆，就可以增加数据在缓存中的驻留机会.因此，当内存中的数据以及时局部组邻域为单位迁来片上缓存后，应该化整为零分散隐蔽起来，避免被后续到来的数据所覆盖，争取驻留缓存的最大机会.定理3和定理4指出，在缓存和内存之间存在常规相联的条件下，如果一个及时局部组邻域中的任何一个数据在内存中的地址的数值是缓存容量的整数倍，那么该及时局部组邻域前往缓存后必然发生分拆.所以，利用分拆增加数据驻留缓存的机会是可行的.

总而言之，为了营造片上及时局部性环境不仅要以群组为单位从内存往缓存迁移数据以提高处理器内核的访存命中率，而且要分拆来到缓存的数据群组以保持、提高片上及时局部性环境的质量，维持命中率处于一个持续的理想状态.这个结论说明，当把数据群组迁往缓存时，尽量将它们分拆开来.比如，可以在进程的虚地址和实地址的转化过程中变换数据地址，使得群组数据的地址产生分拆.这样不仅可以提高内存的访存命中率，而且使得进程的执行安全可控.

4 结论

1)随着数据及时局部组不断进驻片上缓存，及时局部环境发挥了积累效应.从数据在内存中的地址排列顺序看，内存中的及时局部组所涵盖的局部性具有显著的线性特征.这种线性特征是内存的线性特质所决定的.内存的线性特质来源于计算机体系结构的设计选择.

2)当具有局部性关系的数据从内存迁往片上缓存的时候，及时局部组的分拆使得局部组的线性特征出现淡化.这种分拆导致局部组线性特征的淡化恰恰使得局部组内含的局部性冲破了线性的束缚展现了出来.

3)应该围绕数据的局部性来从理论和实践两个方面探索片上缓存的未来体系结构，以及处理器内核中缓存数据的存储装置，以此提升处理器的计算性能.