摘要:本文描述了TI DM642 L1D的硬件结构和运行规则,以及与L1D相关的阻塞发生的条件和避免这些阻塞的方法,并通过一个实例介绍了在算法优化中,内存布局与L1D运行调度之间的关系,以及由此引起的算法性能的差异。

关键词:TI DM642,DSP,CACHE,算法优化

近年来，随着诸如数字音视频通讯、数字音视频监控及数字音视频娱乐等市场需求的大幅度增长，数字音视频处理技术得到了长足的发展，为了满足音视频压缩算法的高强度运算要求，数字信号处理器(DSP)扮演了重要角色，各重要的DSP厂商也分别推出了各具特色的产品。老牌DSP厂商TI不干示弱，推出了一系列这方面的产品，特别是随着DM64x的推出，凭借强劲的运算能力和完备的外部配置，迅速占据了市场并成为主流。

    在DSP上进行算法开发与应用软件开发有很大的区别，开发者需要充分了解DSP的内部结构，指令集和运行规则，才能开发出高性能的产品。正因为如此，不同水平的开发者在同一平台上，开发出的算法性能差距很大。笔者从事嵌入式上的算法开发已有多年，也积累了一些经验，下面就以TI 的DM642为例，将笔者在CACHE优化方面的一些经验和大家一起探讨。

    算法的优化主要分两部分，一是代码的调整，二是系统结构的调整。代码的调整主要就是利用DM642的多个运算单元和流水线特性，以及DSP特有的SIMD(单指令多数据)指令，写出高并行、深软件流水的代码来。结构调整主要是系统对存储器资源的合理使用，特别是片内资源的合理使用，DM642的片上内存分为两级，L1和L2，L2为256KB，可以作为普通的RAM使用，也可作为CACHE使用，还可以部分配置为RAM部分配置为CACHE使用，L1只能做为CACHE使用，分为两部分，L1D和L1P，即数据缓存和程序缓存，L1P的优化思路较为简单，主要的原则就是：尽量以循环、迭代方式实现算法，减小代码量。本文将重点讨论L1D的使用，在视频编解码算法中，数据块都很大，比如一帧4:2:0的D1图像有607Kb，而且还需要同时使用几帧，因此，这些数据基本上无法在片内存放，只能通过合理的内存布局和内存调度，来实现对片内存储器的优化使用，从而达到优化算法效率的目的。

一．L1D的结构和内存映射规则

为了合理使用L1D，我们需要了解它的结构和运行规则。L1D为16k字节，采用双路组联合结构（two-way set associative cache），每路有128组（sets）,行大小为64字节，如图1（a）：

                  图1（a） L1D 结构                  图1（b） sets与地址对应关系

内存数据访问的地址分为3个部分进行解析，Bits 5～0定义L1D cache行内的地址偏移量，Bits 12～6唯一确定该地址对应128组中的哪一组，高位Bits 31～13可以理解为各行的Tag标记。

如下图2：

图2  DM64x L1D的地址解析  

由于L1D是两路cache，每组有两个cache行对应，即每路各有一行。访问数据时，先解析该地址Set段对应哪一组，再比较地址高位的Tag段与该组对应行的Tag段是否相等。若Tag段与某一行匹配，则cache命中；若不相等，则cache缺失。

cache sets与地址有固定的对应关系（即：由地址的6～12位决定）。对于直接映射结构，每个set index在cache中只有一路。在N路组联合结构中，每个set index在cache中有N路，即：每组最多可以同时保存N行数据在cache中。依此来看，直接映射结构也可以看作是单路组联合结构。

理解L1D读的行分配原理（L1D写不分配）：读任何一个地址的数据，它在L1D中对应的组（set）只有两路，于是运用LRU策略从这两行中分配一行。如图1（b）所示，哪个组与哪些地址对应是固定的，相差8k整数倍的两个地址在L1D中对应同一组。

//示例代码:

#define N 2048

short in1 [N];

short other1 [N];

short in2 [N];

short other2 [N];

short w1 [N];

short other3 [N];

short w2 [N];

r1 = dotprod(in1, w1, N);

r2 = dotprod(in2, w2, N);

r3 = dotprod(in1, w2, N);

r4 = dotprod(in2, w1, N);

int dotprod

(

const short *restrict x,

const short *restrict h,

int nx

)

{

int i, r = 0;

for (i=0; i<nx; i++)

{

r += x[i] * h[i];

}

return r;

}

其中数组other1、other2、other3由其它函数调用。对DSP未作特殊配置时，以上数组按照顺序分配地址。定义N等于2048，则以上各个short型数组的大小都是L1D的四分之一，则in1、in2、w1、w2映射到L1D中的同一组。对于DM64x，图3中S=128。实际上各数组在L1D中的分配与in1的起始地址有关，但即使in1的起始地址与图3不同，它们在L1D中发生的分配与踢出情况相同。

如图3(a)所示，第一次调用dotprod时，in1、w1在L1D中发生读缺失分配，导致S次L1D不命中；第二次调dotprod时，in2与w2映射到L1D中，in1、w1被踢出L1D，同样有S次不命中；第三次调用时，in1踢出in2，发生S/2次不命中。最后一次调用，in2、w1分别踢出in1、w2，导致S次不命中。由此可以看出，内存结构不合理，将会导致数组反复的读分配与踢出，大量的L1D缺失使得算法效率低下。

若将数组改为如下定义，则在四次调用dotprod过程中，数组分配如图3（b）所示，各个数组仅发生读缺失分配，已经在L1D中分配的数组得到反复利用，处理效率大为改善。

short in1 [N];

short in2 [N];

short w1 [N];

short w2 [N];

short other1 [N];

short other2 [N];

short other3 [N];

              图3（a）                               图3（b）

二．L1D的bank结构与阻塞条件

L1D读命中时的阻塞与它的bank结构有关，C64x的L1D被组织为8个32位（bit）宽度的存储体（bank）。Banks采用单端口结构，如果在一个执行周期内对同一个bank访问两次，则引起bank阻塞。

L1D解析地址与bank映射关系，如下图。其中地址的4—2位决定哪个bank，地址1—0位决定该bank内四个字节中的哪个字节。

图4  DM64x L1D的bank解析

对于L1D，以下数据访问不引起阻塞:

  Add     a4 ,x ,b4               ;其中x=8,16,24

  Lddw   *a4 , a31:a30

||  Lddw   *b4 , b31:b30

如：

or     0,a4, b5

  Lddw   *a4 , a31:a30

||  Lddw   *b5[2] , b31:b30

对于L1D，以下数据访问引起阻塞:

Add     0,a4 , b4

  Lddw   *a4 , a31:a30

||  Lddw   *b4[4] , b31:b30       ;这里相差4的整数倍阻塞

也就是说，访问L1D，地址相差32 Bytes整数倍，则引起阻塞。

三．与L1相关的阻塞

L1D命中时,发生bank阻塞（L1D Bank Conflict），会阻塞1个时钟周期。

L1D读缺失（L1D Read Miss）时，会发生阻塞，若L2 cache中包括所需数据，每次读缺失最快需要8个周期得到数据。但在下列情况下，会阻塞更多个时钟周期：(1)L2 cache 读缺失（L2 cache read miss）。所需数据不在L2中，需要从外存读取，先发出EDMA申请，等待队列响应；(2)读数据与L1P缺失冲突时，L1P的请求优先于L1D得到响应，也会引起L1D阻塞；(3)L2 bank冲突，与L1D不同的是，在连续两个周期内访问L2的同一个bank同样引起冲突；(4)L1D写缓存冲洗（L1D write buffer flush），若读缺失发生时，L1D写缓存非空，先将写缓存中的数据全部写入L2中，然后才响应L1D读缺失；（5）L1D的victim缓存回写（L1D Victim Buffer Writeback），若读缺失发生时，Victim Buffer非空，先将缓存中的数据全部写入L2中，然后才响应L1D读缺失。

DSP对并行或连续L1D读缺失可进行流水处理，以降低阻塞周期，但必须满足以下两个条件：（1）L1D读缺失的数据地址不是对应于L1D的同一组（set）；（2）读取的数据就在L2中，并且立即得到返回，没被以下因素延迟：L1P与L1D同时缺失、L2 bank访问冲突、write buffer非空和victim buffer非空。

L1D写缓存已满（L1D Write Buffer Full），再有L1D写不命中时，就会发生阻塞，直到写缓冲有空闲。4×64bit写缓存在每个周期自动驱逐64bit，产生一个可用的入口（entry）。如果每个指令周期有一条stdw，即使L1D连续写都不命中，也不会因为L1D写缓存阻塞。L1D写缓存中的数据写入L2时，以下因素会进一步增加阻塞周期：（1）L2 cache写缺失，从外存读取整行数据，与L1D写的新数据合并；（2）L2写数据与L1P缺失冲突；（3）L2 bank阻塞。

L1P读缺失会引起阻塞，每次L1P读指令需要8个周期从L2返回，以下因素会进一步增加阻塞周期：（1）L2 cache读缺失，需要从外存取指；（2）L2 bank阻塞。

当DSP通过L2访问外部存储器时，阻塞周期主要取决于EDMA队列等待时间和外部存储器的读写速率。所以较高的外存时钟频率能够提高嵌入式系统的效率。

连续写数据时，写缓存（L1D Write Buffer）可将两个写缺失合并为一个双字操作，需要满足的必要条件是L2配置为SRAM。若将DM642的二级缓存L2全部配置为cache，则写操作肯定无法合并。

EDMA搬运数据或维护cache一致性时，监听也会引起阻塞。每次监听会访问L1D tag值。如果监听命中L1D,则CPU访问L1D一直被阻塞，直到回写置无效（writeback-invalidate）操作完成。如果监听和CPU对L1D访问同时发生，CPU的访问请求优先得到处理。

    以上是笔者在L1D优化方面所掌握的一些经验和技巧。当然，要充分挖掘DSP潜力，提升算法性能，不仅需要优化L1D cache，还要考虑L2的优化、外存的读写速率以及DMA数据传输等问题。

    为了更科学的设计内存布局，在结构设计时就能了解我们所设计的内存结构和运作方式在L1D中的运行情况，将设计的失误发现在代码编写之前，笔者设计了一款L1D的模拟运行软件，可以将我们所设计的内存结构和运行情况编写成特定格式的伪码，然后用此软件来模拟运行，就可以得到在L1D中的运行情况，并对其中的阻塞和冲突给出建议。