A WCET Analysis Method for Multi-Core Processors with Multi-Tier Coherence Protocol
-
摘要:
由于多核处理器优越的计算性能，多核处理器现已广泛应用在嵌入式实时系统中. 相对于单核处理器，多核处理器存在资源共享竞争、并行任务干扰等因素，尤其是缓存（Cache）一致性问题，导致任务最坏情况执行时间（worst-case execution time，WCET）的预测更加困难.基于以上因素，提出基于多级一致性协议的多核处理器WCET分析方法.该方法针对多级一致性协议体系架构，提出多级一致性域的概念，将多核处理器的数据访问分为域内访问和跨域访问2个层次，根据Cache读写策略和MESI（modify exclusive shared invalid）一致性协议，得出一致性域内部和跨一致性域的Cache状态更新函数，从而实现多级一致性协议嵌套情况下的WCET分析.实验结果表明，在改变Cache配置参数的情况下，该方法分析结果与GEM5仿真结果的变化趋势一致，经过相关性分析，GEM5仿真结果与该方法分析结果相关性系数不低于0.98；在分析精度方面，该方法的平均过估计率为1.30，相比现有方法降低了0.78.
-
关键词:
- 最坏情况执行时间 /
- Cache一致性协议 /
- 跨一致性域 /
- 静态分析 /
- 时序分析
Abstract:Due to the high parallel computing performance of multi-core processors, it has become a trend in real-time systems. Compared with single-core processors, the WCET (worst-case execution time) analysis of multi-core processors is confronted with greater challenges because of shared resources competition and parallel tasks interference. Especially, the Cache coherence protocol in multi-core processors makes WCET analysis more complex. We present a multi-tier coherence protocol WCET analysis method for multi-core processors with MESI coherence protocol based on the reasons above. Aiming at the architecture of multi-core processor with multi-tire coherence protocol, a multi-level consistency domain is defined which determines cores using the same coherence protocol. According to the access rules on memory hierarchy, the shared data access of multi-core processors is divided into intra-domain access and cross-domain access, proposing a Cache update function for multi-core processors with multi-tier coherence protocol. Thus, WCET analysis in the case of multi-tier coherence protocol nesting is realized. The experimental results show that the estimated results are consistent with the simulation results of GEM5 for different Cache configurations, and correlation analysis reveals that the estimated WCET is significantly correlated with simulation results. Furthermore, the average overestimation rate of this method is 1.30, which is decreased 0.78 than the representative related work.
-
计算密集型应用的发展使得向量处理单元（vector processing unit，VPU）[1-5] 被广泛地应用在当前的高性能处理器设计中，几乎所有处理器中都使用了VPU并提供了向量扩展指令. VPU通过并行处理多个数据通道来高效地开发数据级并行性（data level parallelism，DLP），例如Intel Xeon，ARM V8，Brainwave[6]，Imagine[7]，NX27V [8]，DaVinci[9]，VT [10]，MAVEN[11]等高性能通用处理器或专用加速器. SODA [12]，FT-Matrix [13]，AnySP[14]等数字信号处理器也使用了VPU. 近年来，神经网络得到了快速的发展，其高度并行的计算特性与向量处理单元的结构完美匹配，使得带有向量功能单元的处理器不断扩展其向量宽度，即提供更强的数据级并行开发能力（如DaVinci结构[9]），以更好地支持神经网络中的密集计算.
尽管VPU已被广泛应用于各类芯片的设计中，但其总体性能仍受到数据混洗操作的限制. 数据混洗操作是为重新排列向量元素而设计的，其目的是将VPU中的计算通道与向量寄存器文件中的数据一一对齐. 这样之后，处理器才能有效地并行处理多个数据. 当读取到的数据与计算通道不对齐时，处理器就必须在计算之前执行额外的数据混洗操作. 神经网络中的卷积层占据了其整体性能开销的90%以上[15-16]，为了在VPU或类似的结构上高效地实现卷积，Chellapilla等人[17]提出了使用图像重排算法Img2Col（image to column）搭配通用矩阵乘法（general matrix multiplication，GEMM）算法的优化算法. Img2Col的关键思想是展开图像并复制图像中部分像素点，重新排列图像像素和内核参数，从而生成对VPU友好的矩阵乘法数据布局，这样只需要再进行GEMM运算就可以完成卷积. 虽然Img2Col搭配GEMM可以显著提高卷积的性能，但Img2Col占用了大部分的执行时间，导致计算单元的计算效率较低.
图1为Img2Col和GEMM在1个卷积层中执行时间的占比. x轴表示输入图像的大小，y轴表示执行时间的占比. 在对不同大小数据集的测试中，Img2Col的执行时间最多是GEMM的28.3倍，其占总执行时间的比例超过了85.6%，最多达到98.9%. 数据混洗操作已成为对VPU性能制约最严重的瓶颈之一[18-19].
![]()
图 1 Img2Col和GEMM在卷积层中执行时间的占比Figure 1. Execution time proportion of Img2Col and GEMM in the convolutional layer为了在处理器中实现数据混洗操作，现有处理器都使用了定制的混洗单元[20]. 定制混洗单元通常采用交叉开关结构，以满足应用中混洗操作多样性的需求. 例如，FT-Matrix和DaVinci都使用了基于交叉开关的硬件混洗单元. 然而，这种结构的混洗单元硬件开销较大，且可伸缩性较差. 随着未来向量宽度的不断增加，定制混洗单元所面临的问题将变得更加严重[21].
与加、减、乘累加等向量算数运算不同，数据混洗操作只会改变数据的布局，而不进行任何运算. 在理想的情况下数据混洗操作应该在内存中完成，从而有效地减少内存访问次数. 而现在的高性能处理器通常使用静态随机访问存储器（static random access memory，SRAM）来保存向量数据，并将其直接与向量寄存器连通，以便为VPU提供高带宽低延迟的访问. 这种存储器叫做向量内存，1.1节将对其详细介绍. 此外，近年来基于SRAM的存内计算技术也得到了快速发展，现有的技术已经能够在SRAM中实现复制、逻辑、算数等多种位运算. 基于上述观察，本文提出了混洗SRAM，一种In-SRAM的混洗架构. 其关键思想是利用SRAM中的位级数据移动能力作为数据混洗操作的主要数据传输引擎. 通过适当的数据预布局和控制逻辑，混洗SRAM可以高效地实现各种常用的混洗算法，包括矩阵转置、蝴蝶混洗、Img2Col等.
我们在FT-2000处理器[22]上对混洗SRAM进行了测试，混洗SRAM能够带来平均3.18倍的性能提升，同时降低了12.3%的能耗.
本文的主要贡献有3个方面：
1）利用SRAM的存内计算体系结构中的位线数据移动能力作为数据混洗的主要引擎，提出了混洗SRAM来实现存内数据混洗操作.
2）设计了数据预布局映射算法和向量扩展指令，使混洗SRAM能够支持广泛的混洗操作.
3）对混洗SRAM进行了性能评估. 结果表明，对于常用的混洗操作，混洗SRAM可以实现28倍的性能增益. 使用混洗SRAM，VPU的整体性能平均可提高3.18倍，功耗降低12.3%，而混洗SRAM仅会给芯片设计带来4.4%的额外面积开销.
1. 相关背景
1.1 向量内存
向量内存是一种基于SRAM实现的高速缓存，已被不少高性能处理器[9,13,23-24]所使用. 向量内存中的数据被直接送往向量寄存器文件，因而可以为VPU提供高带宽低延迟的数据访问. 与高速缓存（cache）不同，向量内存由程序员直接管理，以充分发挥其潜力.
在向量内存中，SRAM被组织成多体的形式，每个单指令多数据（single instruction multiple data，SIMD）通道只能访问其私有存储体，这被称为“混洗限制”. 如果一个存储体中的数据需要在另一个SIMD进行通道内计算，就需要引入额外的通道间通信操作，也就是所谓的混洗操作. 为了打破混洗限制，就需要在数据被取到向量寄存器文件后，使用混洗指令来使向量寄存器文件中的数据与SIMD计算通道对齐. 在EEMBC基准测试[25]中，混洗指令平均占据了总指令数的23%. 因为在关键循环中总是需要数据混洗指令，而循环是并行应用程序的主要组成部分，占用了大部分的处理器时间. GPU中提供了Gather与Scatter指令来共享SIMD计算通道之间的内存空间，VPU则采用混洗单元（shuffle unit，SU）来完成SIMD计算通道之间的数据交换.
目前混洗单元主要有2种实现方法：一种方法是定制的交叉开关[19]，它的实现开销较小但不能支持具有不同混洗操作的应用. 另一种方法是使用SRAM体来替换交叉开关[14]处的触发器，但这种方法的空间开销很大. 后来的一些工作[9,22]也采用了类似的思路，这些工作要么具有更少的内存开销，要么支持更灵活的混洗模式. 然而，这些方案都需要先将数据从内存传输到处理器中，并通过显式的混洗指令来处理，严重限制了处理器的性能. 混洗SRAM作为一种新颖的方案，可以将混洗操作交由内存来处理，为处理器带来更高的性能和更低的能耗. 相关研究[26-28]探索了在SRAM中实现混洗操作的可能性.
1.2 SRAM存内计算技术
为了在不影响访存效率的情况下在SRAM中引入计算，需要使用8个晶体管来构建SRAM的位点（bitcell）. 如图2（a）所示，该位点由1对交叉耦合的逆变器和4个接入晶体管组成. 交叉耦合的逆变器有2个稳定状态，因此可以存储1b的数据. 2个横向的接入晶体管用于数据读写，由水平字线（horizontal word line，HWL）控制. 2个纵向的接入晶体管用于计算，由垂直字线（vertical word line，VWL）控制. 图2（b）展示了经典的8T SRAM存储体结构. 该存储体由1个位点阵列（bitcell array）组成，通常使用水平位线（horizontal bit line，HBL）和垂直位线（vertical bit line，VBL）来加载或存储数据. 在图2（b）中，存储体内已经预加载了2组向量，左侧一组向量用浅色表示，右侧一组用深色表示. 同一向量的数据被放置在存储体不同的行中，而数据的不同位被分散到不同的列中，从最高位到最低位依次排列.
图3展示了现有的In-SRAM的复制和逻辑操作. 执行复制操作时，首先要激活源VWL，将列向数据传入到灵敏放大器（sense amplifier，SA）中. 然后，激活写使能信号，将SA放大的结果回传到HBLs中. 最后，激活目标VWL，将数据写入. SRAM中的位线（bit line，BL）由2条线组成，这2条线保存着相反的数据. 为了区分它们，一条成为正位线，另一条成为反位线. 执行逻辑操作，首先需要同时激活2个源VWL. 经过SA放大后，正位线中会产生与（and）的结果，反位线中则会产生或非（nor）的结果. 之后，激活写回使能信号，将逻辑运算的结果回传到HBLs中. 最后，激活目标VWL以存储结果. 此外，通过在SA外部添加更多的逻辑电路，再加上位运算逻辑，就可以支持更实用的复杂计算操作. 本文基于已有的复制和逻辑操作，实现了一个更高效且节能的位交换引擎.
2. In-SRAM并行按位混洗架构
有2个观察结果启发了我们的研究. 首先，任何混洗操作都可以表示为2个或多个VWL之间的交换操作. 其次，对于大多数混洗操作，它们的模式是由应用或算法决定的，通常在一个循环中保持不变，例如对内存访问[29]的重新对齐. 因此，应用程序中往往具有足够多且模式相同的混洗操作，只要将向量在SRAM体中整齐地排列，通过列向的位交换操作，就可以实现高并行性的混洗操作.
为了在SRAM中实现并行的混洗操作，我们重新设计了SRAM存储体. 图4显示了In-SRAM并行按位数据混洗的整体架构. 与传统的SRAM存储体相比，1个混洗SRAM融合了8个位点阵列，这些阵列共享HWLs、HBLs、解码器、多路选择器（multiplexer，MUX）和SA等模块. 混洗逻辑（shuffle logic）单元是由多个数据交换单元（图4（a）中的浅灰色模块）组成的，每个HBL连接了1个数据交换单元.
混洗SRAM对传统的SRAM进行了2处修改，并添加了2个新组件. 第1处修改是连通了不同位点阵列的水平位线，以支持跨位点阵列的数据传输. 第2处则是设计了混洗逻辑单元来支持混洗SRAM中的复制和信号位设置指令. 新增的2个组件是指令缓存和开关组. 指令缓存用于缓存来自处理器的二进制指令（2.2节有详细介绍）. 开关组由分布在不同HBLs上的晶体管组成. 当开关打开时，混洗逻辑单元可以交换2个混洗块之间的数据；当开关关闭时，2个混洗块可以通过各自的混洗逻辑单元独立地进行数据交换.
随着向量数据中元素个数的增加，位串行混洗操作的延迟也会增加. 为了减少在混洗SRAM中按位混洗的延迟，在实际的设计中还可以通过增加混洗逻辑单元和开关组的数量，将混洗SRAM分为更多的混洗块（最多8个，混洗块的数量需小于等于位点阵列的数量）. 这样，当开关单元关闭时，所有的混洗块都可以独立地交换数据. 图4展示了具有2个混洗逻辑单元的混洗SRAM的结构，这个混洗SRAM被分为了2个混洗块. 通过2个混洗块，混洗SRAM可以实现最高的性能面积比. 相关评测结果见4.5节.
2.1 数据交换单元
图4（a）显示了混洗SRAM中1个混洗块中1行的详细视图. 混洗SRAM和传统SRAM之间最大的区别在于HBL连通了所有的位点阵列. 图4（a）还展示了数据交换单元的详细设计，每条HBL都连接着数据交换单元. 混洗SRAM支持4条机器指令. 如图5所示，2条用于数据传输（读和写），另外2条用于数据混洗（传输和信号位设置）. 混洗SRAM采用32 b二进制来编码这些操作. [31:30]两位作为操作码. 对于读/写机器指令，[29:19]，[18:11]，[10:0]三个字段分别代表混洗SRAM中的行地址、列地址以及数据地址. 对于传输和信号位设置机器指令，[29:19]和[18:8]两个字段代表了2个列地址. [7:4]字段代表了数据交换模块的使能信号，我们将混洗SRAM的HBL分为了4组，当混洗SRAM中需要处理不同的混洗操作时，就可以将数据放在不同的HBL组中，进行哪种混洗操作就将哪一组数据混洗单元的使能位置1，这样就可以在同一个混洗SRAM体中执行不同模式的混洗操作. 传输操作中的字段[3:0]代表了锁存器（latch，L）L1和锁存器L2的复位信号. 信号位设置指令中的字段[3:0]代表了L1和L2的启用信号（0启用L1；1启用L2）. 读/写指令在VBL中执行，通过HWL控制. 传输和信号位设置指令，在HBL中执行，通过VWL控制，由列数据交换单元完成.
图6展示了传输和信号位设置机器指令的控制信号时序图. 对于控制指令，每位需要通过2个2选1的MUX. MUX1由L1控制，MUX2由L2控制. 如果锁存器接收到控制信号“1”时，就会输出上方的输入；收到控制信号“0”时，则会输出下方的输入. 在经过MUX之后，位就会被写回目标位点. 在执行信号位设置指令时，没有位需要被写回. L1存储2位的与（and）结果，L2存储2位的异或（xor）结果. 当某个VWL被激活时，所有垂直方向同列的位点都将被激活，所有的HBL可以并行地执行相同的机器指令.
图6（a）展示传输机器指令的控制信号. 首先，混洗SRAM指令译码器接收到传输指令. 传输指令中包含VWLA和VWLB的地址. 在对第A列所有的VBL进行预充电后，混洗SRAM就会先激活VWLA来从位点中输出位数据. 接下来，位数据经过SA放大后，又会通过2个选择器，再通过写回开关，位数据又被传输到了原本的位线上. 最后激活VWLB，在这列的位点中写入来自VWLA的位数据. 为了防止同时从2个位点同时读取而导致潜在的干扰问题，我们为VWLA和VWLB的驱动器分别设置了单独的电源电压，以便在必要时降低字线电压. 我们还使用了伪差分SA来代替传统的SA，允许在更小的位线电压摆动时更快地感知放大结果.
2.2 向量混洗扩展指令
通过复制和信号位设置指令的灵活组合，混洗SRAM目前可以支持5条向量混洗扩展指令：复制（copy）、数据交换（switch）、条件复制（if-copy）、取反（invert）和绝对值（absolute），如表1所示.
表 1 混洗SRAM支持的向量混洗扩展指令Table 1. Vector Shuffle Extended Instructions Supported by Shuffle-SRAM操作码 源A 源B 目的C 数据位宽 描述 copy √ √ N C=A switch √ √ N A=B, B=A if-copy √ √ N if (A>0)C=A invert √ N A=A absolute √ √ N C=|A| 图7展示了1 b数据交换指令和条件复制指令的控制信号时序图. 为了实现2列数据的交换，我们使用了1个信号位设置指令和2个复制指令的组合来实现最基本的1 b数据交换指令. 1 b数据交换将经过以下过程. 首先，同时激活需要交换的2列（VWLA和VWLB），此时位经过SA放大后，在HBL上就会产生“A and B”的结果，在水平反位线上产生“A nor B”的结果. 接下来，将HBL和水平反位线上产生的结果输入NOR门就会产生“A xor B”的结果. 之后，打开L2的写使能信号，使L2能够保存“A xor B”的结果. 接下来，再激活VWLA，将输出写回VWLA. 激活VWLB，将输出写回到VWLB. 根据L2中保存的结果，如果VWLA和VWLB的位不同，那么“A xor B”的结果就为“1”，MUX1就会输出取反的结果，这样VWLA和VWLB分别取反后就相当于交换了2列中的位数据. 最后，重置L2，这样1个多位数据的交换可以通过逐位的1 b交换操作来实现. 我们使用1个4 b数据交换操作的例子来说明. 假设有2个4 b数据“0110”和“0101”，按位异或的结果是“0011”. 根据异或的结果，这2个数据的最后2 位将被取反. 这2个数据最终将变为“0101”和“0110”，取反的结果就是这2个数据被交换了位置.
![]()
图 7 向量混洗扩展指令的控制信号时序图Figure 7. Control signal timing diagrams of vector shuffle extended instructions条件复制、取反和绝对值这3条向量扩展指令可以通过组合1个信号位设置指令和多个复制指令来实现（复制指令的具体数量由数据长度决定）. 以条件复制扩展指令为例，使用信号位设置指令在L1中存储条件位. 通过MUX，如果L1保存的信号为“1”，则该位将被置为“0”. L1需要在最后一条复制指令结束后被复位. 而复制向量扩展指令是通过组合多个复制机器指令来实现的.
为了提高混洗SRAM的可编程性，我们又向原始指令集中添加了2个额外的指令，分别是copy to SRAM和start execution. copy to SRAM指令用于将二进制指令复制到指令缓冲区，被复制的指令将在混洗SRAM中执行. 当混洗SRAM接收到start execution指令时，它将开始执行存储在指令缓冲区中的二进制代码. 在所有二进制指令被执行后，指令缓冲区将被清空.
2.3 混洗SRAM的优势
In-SRAM并行按位混洗架构具有提升数据并行性的潜力，同时也可以显著地减少处理器需要执行的指令数和数据移动的开销. 图8通过比较数据混洗单元和混洗SRAM的工作流程，来展示混洗SRAM的优势. 如图8（a）所示，数据混洗单元采用位并行的模式来执行混洗操作，混洗操作只有在向量被加载到向量寄存器后才能执行. 使用数据混洗单元，1次混洗操作最多只能重排2个向量之间的元素. 如图8（b）所示，混洗SRAM使用位串行模式来执行混洗操作. 通过12条指令就可以完成图中所有向量的混洗，且所有的混洗操作都是在混洗SRAM中完成的. 向量寄存器可以直接加载被混洗后的向量. 1个混洗SRAM通常都具有成百上千个HWL，这些HWL都可以并行地混洗数据，从而在SRAM中开发了数据级并行性. 此外，In-SRAM并行按位混洗架构通过将混洗操作移动到内存中，不仅能减少了芯片上数据的混洗开销，还能减少数据在片上和内存之间的移动开销.
2.4 讨 论
1）混洗逻辑单元数量的选择
根据前面的介绍，虽然数据交换引擎可以加速按位混洗操作. 但在位串行混洗模式下，单次混洗操作的延迟仍然较大、无法忽略. 随着向量长度与数据长度的增加，并行混洗操作的延迟也会增加. 增加混洗逻辑和开关单元的数量可以进一步提升混洗SRAM的并行性. 4.5节将详细讨论如何选择混洗SRAM参数，以获得最佳的性能面积比.
2）多种混洗模式（MSM）的处理
在一些特殊的循环中，同时会有多组数据需要同时进行混洗，且不同组的数据具有不同的混洗模式. 我们将这种循环称为具有“多混洗模式”的循环. 图4只显示了1个混洗SRAM体的结构. 在向量内存的设计中，混洗SRAM体是构建向量内存的基本单元. 整个向量内存由多个混洗SRAM体组成. 这些混洗SRAM体是串联的，它们的地址是连续的. 想要使用混洗SRAM来优化具有多种混洗模式的循环，程序员需要直接控制数据的传输，以将不同的数组分布到不同的混洗SRAM体中. 通过给每个混洗SRAM体发送不同的指令，不同的数据组就可以并行地被混洗.
图9展示了混洗SRAM构成的向量内存如何处理具有多种混洗模式的循环.
在这个循环中，数组A，B，C都有自己的混洗模式. 在计算之前，程序员应将数组数据复制到不同的混洗SRAM体中（假设数组A，B，C分别保存在混洗SRAM体1，2，3中）. 然后，混洗SRAM体1聚合数组A中步长为1的元素，混洗SRAM体2聚合数组B中步长为3的元素，混洗SRAM体3聚合数组C中步长为2的元素. 在处理过程中，向量处理器只需要执行“取数、计算、写回”的指令循环. 在所有计算结束后，混洗SRAM体3再以3为间隔离散元素，就可以完成整个循环. 我们在实验中测试了这类循环的性能，结果见4.2节.
3. 数据重组的实现
3.1 数据映射
在混洗SRAM执行操作之前，向量数据应该按一定规律整齐地放置在混洗SRAM中. 对于1维数组，只需要将向量按混洗SRAM的地址顺序对齐放置在混洗SRAM的不同行中. 对于2维数组，在将向量存入混洗SRAM之前，需要根据混洗SRAM的行大小将向量分块. 直接存储器存取（DMA）单元可以支持不同存储器之间的高速传输，因此实现数据在混洗SRAM布局的主要挑战是如何为每个向量生成对应的地址.
混洗SRAM中数据映射的本质是要找出具有相同混洗模式的混洗操作，并将相应的向量对齐地放在混洗SRAM的每一行上. 这样，所有的向量都就可以通过同一条指令同时被混洗，这是利用混洗SRAM高并行性的关键.
3.2 向量指令集中的混洗操作
向量指令集中的混洗操作很简单，所有的混洗指令只涉及到在1个向量内或在多个向量间对元素进行重新排列. Gather2是ARM SVE向量扩展指令集中的1条，用于收集元素索引模2为0的元素. 类似地，Gather3收集元素索引模3为0的元素. 快速傅里叶变换（FFT）中的蝴蝶混洗就是主要通过Gather2指令实现的. 要利用混洗SRAM来实现这些Gather指令，就需要使用式（1）来生成向量在混洗SRAM中的地址. 式（1）中Rs代表混洗SRAM的行大小，Es代表数组的元素大小，Addr代表混洗SRAM的地址，i代表数组元素的索引.
Addr=i×Es/Rs. (1) 混洗SRAM实现数据混洗操作需要在多个源到多个目的VBL之间执行位交换，从而为不同的SIMD通道提供所需的数据，激活哪些源VWL与目的VWL则是由混洗模式决定的. 对于传统的数据混洗单元，由于对多粒度混洗操作的需求，可伸缩性是一个关键问题. 随着SIMD宽度的增加，数据混洗单元的硬件开销也会不断变大. 在混洗SRAM中，混洗操作是逐位进行的，它的可伸缩性范围由硬件宽度决定. 因此，混洗SRAM的可伸缩性要远优于数据混洗单元.
在混洗SRAM的支持下，混洗操作在3个方面得到了优化. 首先，使用混洗SRAM可以支持任意粒度的混洗操作，这使得混洗操作能够摆脱硬件宽度的限制. 其次，混洗SRAM支持统一混洗模式下的并行处理，这提高了SIMD器件的性能和能效. 最后，混洗SRAM支持具有不同控制流路径的混洗操作，这扩展了混洗操作的功能，使其能够处理更多的有数据重组需求的应用.
3.3 矩阵转置
假设Rs代表混洗SRAM的行大小，Es代表数组的元素大小，M×N代表矩阵大小，Addr代表混洗SRAM的地址. 对于矩阵转置中的数据混洗，向量地址可以用式（2）生成：
Addr=i×NX×Y+jY, (2) X=√Rs/Es,Y=√Rs/Es. 许多重要的数字信号处理算法（包括线性代数、音频处理和图像处理等应用）的性能在很大程度上都取决于矩阵转置的效率. 传统的矩阵转置实现方案都需要处理器的参与来完成矩阵转置：首先从内存中先加载源矩阵中的每个向量；然后使用混洗操作交换多个向量之间的数据；最后再将结果向量写回内存. 虽然矩阵转置的混洗模式很简单，但由于混洗的并行性非常差，极大地影响了矩阵转置的性能，大型矩阵因转置带来的性能延迟更为突出. 传统的矩阵转置方案不仅占用了访存单元和带宽，还影响了计算任务的处理，这是因为矩阵转置和计算任务只能串行执行. 使用混洗SRAM，经过分块与数据映射，每个HBL上的矩阵块可以同时被转置，不需要处理器的参与，也没有额外的数据传输开销. 此外，混洗SRAM中的矩阵转置和处理器的后续计算也可以通过灵活的编程来实现流水化执行.
图10显示了一个矩阵转置的例子. 该矩阵大小为6×6，Rs = 16，Es = 4. 矩阵被分为9个块，每个块包含4个元素. 根据式（2），每个块都可以被映射到混洗SRAM的每一行中. 通过4个交换操作，整个矩阵的转置操作就可以被完成.
![]()
图 10 使用混洗SRAM实现矩阵转置Figure 10. Implementation of matrix transposition by using Shuffle-SRAM3.4 Img2Col
假设Ks表示卷积核（kernel）大小，S表示步长，矩阵的大小为M×N，Addr表示为混洗SRAM的地址. 在Img2Col中，元素[i][j]在混洗SRAM中的地址可以用式（3）生成. 与矩阵转置不同，Img2Col需要根据核大小多次输入数据.
Addr=(i−z+1)×(N+S−√Ks)X2+j+S−√KsY,z−1<i<M+z√Ks, (3) X=2√Ks−S,Y=2√Ks+S×(RsEs×Ks−2). 图11显示了一个4×4大小的矩阵，它需要由一个3×3大小的内核进行卷积，每个元素的长度为4 b. 根据式（3），当“z=1”时，矩阵的前2行输入到混洗SRAM的“1”行和“2”行（源矩阵第1行的元素被放在“1”行中，源矩阵第2行的元素被放在“2”行中）. 由于页面大小的原因，图11中的“1”行和“2”行应当更长，图11中“1”行和“2”行被分为了3段. 之后的输入并不会替换之前的输入，而是紧接着之前的输入存放. 当“z=2”时，源矩阵第2行的元素被放在“1”行中，源矩阵第3行的元素被放在“2”行中. 以此类推，当“z=3”时，源矩阵第4行的元素被放在“1”行中，源矩阵第4行的元素被放在“2”行中. 到此为止，数据映射过程完成. 然后，可以通过执行2次4×9个复制操作就可以完成算法Img2Col. 随着矩阵尺寸的增大，使用混洗SRAM的性能优势也将不断提升.
3.5 ReLU
ReLU中数据的地址也可以通过式（1）生成. ReLU函数是人工神经网络中常见的激活函数. ReLU激活函数只需要简单的计算：如果输入大于0，则返回输入值；如果输入为0，则返回值为0. 它可以用式（4）来表示.
f(x)=max (4) 使用混洗SRAM中的条件复制操作就可以容易且高效地实现ReLU. 图12展示了如何对位长为4的数据实现ReLU变换，从而来解释元素的每1位如何从最高位逐位执行到最低位的. 这4个元素占据混洗SRAM的4列. 首先使用信号位设置操作将4个元素的符号位输入到数据交换单元的L1中. 接下来使用4个复制操作将这4列都转移到目标位置. L1锁存器保存的符号位是“1”，则MUX将输出“0”. 图12中，混洗SRAM并行完成了4个数据的ReLU变换.
4. 实验与评估
本节展示了对混洗SRAM的评估方法与结果. 评估以1 GHz 的FT-2000处理器[22]为基准. FT-2000使用ARM V8指令集，支持ARM V8的向量扩展指令，以其作为基准具有一定的代表性.
4.1 模拟器配置
表2展示了FT-2000模拟器的一些体系结构参数. 在我们的模拟中，设置的SIMD指令的延迟和吞吐量都与FT-2000文档中的数据相同.
表 2 向量处理器参数Table 2. Parameters of Vector Processor配置 描述 处理器频率/GHz 1 向量长度/b 2048 向量单元 16 × 8 SRAM容量/MB 8 混洗SRAM 8 MB；8 个位点阵列；
位点阵列大小:2048 ×256；
2个混洗块4.2 内核测试
表3展示了我们在实验中使用的6个数据重组内核，这些内核经常出现在多媒体、CNN和其他应用程序中. 这些内核都需要大量的混洗操作来实现，包括不对齐的内存访问、数据重组和控制分支流. 它们可以用来显示In-SRAM并行按位混洗架构的高效性和广泛适用性. Gather2（G2）和Gather3（G3）内核广泛应用于FFT、线性预测编码和图像处理. 矩阵转置（matrix transpose，MT）、Img2Col和ReLU被广泛应用于GEMM中，它们都有相对简单且统一的数据混洗模式. 在测试中，假设需要混洗的数据已经按照第3节中所介绍的方式在混洗SRAM中摆放好. 基准结构和混洗SRAM之间有2个主要的区别：一是基准结构需要先将每个数据移动到一个特定的混洗单元来完成数据重组，而混洗SRAM可以在不移动数据的情况下完成数据混洗. 另一个区别是，模拟的混洗SRAM可以同时对
2048 个向量进行混洗，而基准结构1次只能对1个向量进行混洗.表 3 混洗SRAM和基准在处理测试内核时的性能比较Table 3. Performance Comparison Between Shuffle-SRAM and Baseline When Shuffling Test Kernels测试内核 数据大小/MB 数据长度/b 延迟/μs 加速比 输入 输出 基准 混洗SRAM G2 2 2 32 3.67 0.061 60.1 G3 3 3 8 10.62 0.018 590.0 MT 1 1 32 2.88 0.011 361.8 Img2Col 3 27 32 14.16 0.590 24.0 ReLU 3 3 32 1.77 0.004 442.5 MSMs 6 3 32 6.23 1.380 4.5 注：基准的时钟频率比混洗SRAM的快4倍. 图13展示了在使用1个混洗SRAM（512 KB）时，采用不同大小的数据集时的实验结果. 当增加输入数据的大小时，混洗SRAM有不同的加速比. 当数据大小为无限大时，相比于基准结构，混洗SRAM可以被平均加速4.22倍. 我们发现了一个现象，随着数据大小的增加，加速比持续减小. 导致这个现象的原因是：当数据大小较小时，所有数据都可以提前以适当的布局放置在混洗SRAM中. 当数据大小增加时，1个混洗SRAM容量消耗完时，就需要交换混洗数据. 即在完成一批数据的混洗后，再将下一批数据放入混洗SRAM中，再对这一批数据进行混洗，依此类推. 正是数据移动开销的占比不断增大才导致了加速比的持续减小.
![]()
图 13 输入数据大小的不同时不同混洗内核的加速比Figure 13. Speedup of different shuffle kernels with different input data size图14展示了基于混洗SRAM构建的向量内存在不同数据大小时内核的加速效果. 我们在这个测试中使用的输入数据大小为2 MB. 如图14所示，随着向量内存数据大小的增加，加速比也会不断增加. 当向量数据大小为8 MB时，加速比为373. 我们发现一个现象，随着混洗SRAM数据大小的增加，加速比在一定范围内显著增加（G2：1~4 MB；G3：2~8 MB；MT：4~8 MB；Img2Col：4~8 MB；ReLU：2~4 MB）. 导致这个现象的原因是在这个范围内，所有数据都可以预先按照适当布局被放置在混洗SRAM中，因此消除了数据移动的开销. 对于G2，数据大小在1~2 MB下的加速比增加的原因是消除了数据移动的开销，而在2~4 MB下的加速比增加的原因是用2个复制操作替换了1个交换操作. 对于MT，加速比在数据大小2~4 MB下不会增加. 原因是当混洗SRAM大小为2 MB时，混洗SRAM可以保存所有数据. 但是，当混洗SRAM大小为4 MB时，复制操作不能代替交换操作，从而减少了性能收益.
由于多混洗模式内核是一个混合了计算和混洗操作的内核，因此它的加速主要来源于减少的内存访问. 此外，它的加速比不会随着不同的混洗SRAM大小或不同的输入数据大小而变化. 因此，我们没有在图13和图14中展示多混洗模式内核的性能收益，相关数据被放在了表3中.
4.3 实际应用测试
表4展示了我们选取的3个实际测试应用. 图15显示了运行FFT，VggNet16，AlexNet的总加速比. 与基准结构性能相比，FFT加速了2.01倍，AlexNet加速了2.84倍，VggNet16加速了4.69倍. 如此显著的加速比可以归因于减少的额外访存开销以及消失的处理器中的数据混洗开销.
表 4 测试应用Table 4. Test Applications图16显示了另一个性能加速的来源. 宏流水线是一种多指令、多数据流并行算法，它有序且易于在多处理器或超长指令字结构中实现，适用于批量处理. 使用混洗SRAM后，向量计算和数据重组可以在不同的设备中处理. 同时，混洗SRAM支持并行的读/写和混洗操作. 因此，处理器将数据进行分批，并不需要将所有数据都混洗后再进行计算. 可以先混洗一部分就开始计算，这样就可以使处理器与混洗SRAM并行工作.
FFT性能的提高来自3个方面：1）使用混洗SRAM执行混洗操作，消除了处理器中蝴蝶混洗操作的延迟；2）通过混洗SRAM混洗后的数据，向量中有效元素的占比更高，从而提高了向量功能单元的利用率；3）通过宏流水编程技术将FFT的各数据点分为实部和虚部，每个数据点都需要对另一个数据点进行蝴蝶计算，包括复数的加、减、乘法. 为了利用SIMD体系结构的性能，数据需要在计算过程中连续地进行蝴蝶混洗. 如图16（a）所示. 值得注意的是，当采用混洗SRAM时，蝴蝶混洗的计算时间开销更低. 因为在基准结构下蝴蝶计算前必须做混洗操作，而最后3级的蝴蝶混洗需要更多额外的混洗操作. 使用混洗SRAM，大部分延迟可以通过宏管道编程来隐藏.
表5显示了AlexNet和VggNet16延迟的分解. 无论哪个网络，卷积层几乎花费了所有的执行时间. 在基准结构下，卷积层花费的时间占AlexNet总执行时间的99.1%，而在ReLU层上花费了2.63 s，池化层需要1.23 s. 卷积层是最耗时的部分；其余的部分是全连接层（full connect，FC）FC4096和FC1000的时间花费，分别占1.57 s和0.19 s. 对于VggNet16，卷积层花费的时间占VggNet16总执行时间的99.3%，在ReLU层上花费0.20 s，池化层需要15.35 s. 卷积层同样是最耗时的部分.
表 5 VggNet16和AlexNet的延迟Table 5. Latency of VggNet16 and AlexNets 测试用例 网络 卷积层 ReLU 池化层 FC4096 FC1000 总计 基准 VggNet16 615.43 2.63 1.23 1.57 0.19 621.05 AlexNet 2441.57 0.20 15.35 1.57 0.19 2458.89 混洗
SRAMVggNet16 215.63 0.05 1.23 1.57 0.19 218.67 AlexNet 507.16 0.01 15.35 1.57 0.19 524.28 使用混洗SRAM，我们可以用GEMM来划分卷积从而并行化Img2Col，如图16（b）所示，除了初始的混洗时间外，所有的Img2Col开销都可以被GEMM的计算延迟隐藏. 总的来说，AlexNet的卷积比例下降了65.0%，ReLU下降了98.1%；VggNet16的卷积比例下降了79.2%，ReLU下降了95.0%.
4.4 能耗与面积的影响
为了获得能耗与处理器面积，我们模拟了基于40 nm SOI CMOS工艺下的位点阵列，该阵列使用标准8T位点结构. 1个8T位点的面积为0.589 µm2，1个数据交换单元的面积为
246.9032 µm2. 每个读/写指令的延迟为3.497 ns，每个复制/信号位设置指令的延迟为3.968 ns. 与传统的8T SRAM相比，总面积增加了4.4%. 在能耗评估中，我们对上述参数与每个指令的能量进行相加，来确定混洗SRAM的总能耗，具体数据如表6所示.表 6 单条机器指令的能耗Table 6. Energy Consumption per Machine Instruction能耗 read write trans signal Energy/nW 0.815 0.856 10.282 6.519 图17展示了混洗SRAM与具有32 B宽度SIMD单元的处理器的能耗对比. 结果表明，混洗SRAM可以为这些应用平均节省1.14倍的能耗. 降低能耗有3个方法：一是通过多个水平位线并行混洗提升了的数据并行性；二是减少内存和向量寄存器文件之间的数据移动；三是消除了处理器所需处理的混洗指令.
![]()
图 17 混洗SRAM向量内存为测试应用带来的总能耗收益Figure 17. Total energy benefit of Shuffle-SRAM vector memory for applications4.5 性能面积比
图18显示了当混洗SRAM具有不同数量的混洗逻辑单元时的性能面积比. x轴表示混洗逻辑单元的数量. 横坐标“0”处表示8T SRAM传统结构的性能面积比，其面积和加速比都设为1. 随着混洗逻辑单元数量的增加，加速比和面积开销都在不断增加. 性能面积比显示了加速比与面积的比率. 当混洗SRAM中混洗块数量为2时，性能面积比最高，为3.04. 在图4和表3中，我们评估的结果是基于具有2个混洗逻辑单元的混洗SRAM所构成的向量内存.
![]()
图 18 不同混洗块数量时处理器性能面积比Figure 18. Performance to area ratio under different shuffle block numbers4.6 讨 论
In-SRAM并行按位数据混洗架构的主要优势是将数据混洗操作从向量处理器中解耦到向量内存中，混洗操作可以在1个混洗SRAM中并行处理所有水平位线上的数据. 将数据混洗操作集成到内存中需要做到：1）用混洗SRAM替换传统的SRAM，并添加相关的控制逻辑来执行特定的指令；2）将混洗SRAM微指令集成到现有的向量ISA中. 混洗SRAM可适配于任何SIMD架构. 虽然在实验中只评估了1个SIMD架构，但混洗SRAM是通用的，当数据混洗操作和SIMD算术指令可以并行处理时，SIMD设备的性能优势将进一步凸显. 因为在消除了数据混洗开销之后，SIMD通道可以专注于执行算术指令. 随着数据大小的增加，通过宏流水编程，使用混洗SRAM带来的加速比也会更高.
混洗SRAM对现有算法的实现带来了一定的影响. 以卷积层的实现为例. 目前所采用的方法是将整个图像转换为矩阵模式，然后调用GEMM高性能计算库. 使用混洗SRAM时，一种方法需要将图像进行更细粒度的划分，这样使用混洗SRAM进行数据重排的时间就可以被GEMM计算的时间隐藏起来. 另一种方法是设计一种新的卷积实现方案，专用于In-SRAM的处理模式. 之所以目前高速卷积的实现方案都不采用传统的卷积串行计算方法，是因为列方向上的数据局部性很差，且高速缓存的容量有限，难以缓存大规模的数据，从而导致处理器性能下降. 对于3×3卷积内核，计算每个数据点时使用的数据将跨越3个不同的列. 使用混洗存储器就可以提前将这些数据排列在一起，这意味着卷积的实现有进一步研究的空间，来判断传统的卷积实现方案在混洗向量内存的支持下是否能进一步地提升.
5. 结束语
传统的SRAM仅作为中间低延迟的存储单元使用. 我们的工作直接挑战了这种传统的设计范式，并提出将数据混洗操作从向量处理器中解耦到向量内存中. 本文中，我们提出了带有In-SRAM并行按位混洗架构的混洗SRAM，以减少片上数据重组的开销. 混洗SRAM实现了4个基本操作，同时我们设计了5条向量扩展指令来支持存内灵活的混洗编程. 我们提出的混洗SRAM位交换引擎和数据布局方面的方案使我们在与先进向量处理器性能相比时具有竞争力. 混洗SRAM的评估结果证明，通过精心设计的硬件机制和编程策略，可以消除大部分数据的混洗延迟，从而实现高效的SIMD计算. 总的来说，In-SRAM并行按位混洗架构的引入为开发更有效的并行算法开辟了一条新的道路，这些算法可以用于进一步优化向量SIMD架构的性能.
作者贡献声明：张敦博提出了架构思路和实验方案，并且完成实验和撰写论文；曾灵灵参与了架构的设计；王若曦协助修改论文；王耀华和沈立提出指导意见并修改论文.
-
![]()
图 5 域内读访问时间延迟及状态转换图
Figure 5. Read-visit latency and state transition diagram of intra-domain
![]()
图 6 域内写访问时间延迟及状态转换图
Figure 6. Write-visit latency and state transition diagram of intra-domain
![]()
图 7 跨域读访问时间延迟及状态转换图
Figure 7. Read-visit latency and state transition diagram of cross-domain
![]()
图 9 GEM5仿真结果与分析结果对比
Figure 9. Comparison of GEM5 simulation results and analysis results
![]()
图 10 GEM5与Roban相关性系数矩阵图
Figure 10. Correlation coefficient matrix diagram of GEM5 and Roban
表 1 多核处理器参数配置
Table 1 Parameters Configuration of Multi-Core Processor
Cache
层次结构数据访问延时/cycle 一致性
协议替换策略 L1 L2 L3 4 核, 2 簇 4 14 42 MESI LRU 注：LRU为最近最少使用（least recently used）替换策略. 
下载: 导出CSV
-
[1] Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the ACM, 1973, 20(1): 46−61
[2] Davis R I, Cucu-Rosjean L. A survey of probabilistic timing analysis techniques for real-time systems[J]. Leibniz Transactions on Embedded Systems, 2019, 6(1): 1−60
[3] Hennessy J L, Patterson D A. Computer Architecture: A Quantitative Approach[M]. San Francisco: Morgan Kaufmann, 2017: 377−393
[4] Nagar K, Srikant Y N. Fast and precise worst-case interference placement for shared cache analysis[J]. ACM Transactions on Embedded Computing Systems, 2016, 15(3): 1−26
[5] Lunniss W, Altmeyer S, Lipari G, et al. Cache related pre-emption delays in hierarchical scheduling[J]. Real-Time Systems, 2016, 52(2): 201−238
[6] Yan Jun, Zhang Wei. Analyzing the worst-case execution time for instruction caches with prefetching[J]. ACM Transactions on Embedded Computing Systems, 2009, 8(1): 1−19
[7] Gan Zhihua, Gu Zhimin. WCET-aware task assignment and cache partitioning for WCRT minimization on multi-core systems[C] //Proc of the 7th Int Symp on Parallel Architectures. Piscataway, NJ: IEEE, 2015: 143−148
[8] 吕鸣松, 关楠, 王义. 面向WCET估计的Cache分析研究综述[J]. 软件学报, 2014, 25(2): 179−199 Lü Mingsong, Guan Nan, Wang Yi. Survey of cache analysis for worst-case execution time estimation[J]. Journal of Software, 2014, 25(2): 179−199 (in Chinese)
[9] Gracioli G, Fröhlich A A. On the design and evaluation of a real-time operating system for cache-coherent multicore architectures[J]. ACM SIGOPS Operating Systems Review, 2016, 49(2): 2−16
[10] Gracioli G, Alhammad A, Mancuso R, et al. A survey on cache management mechanisms for real-time embedded systems[J]. ACM Computing Surveys , 2015, 48(2): 1−36
[11] Ferdinand C, Wilhelm R. Efficient and precise cache behavior prediction for real-time systems[J]. Real-Time Systems, 1999, 17(2): 131−181
[12] Cousot P, Cousot R. Abstract interpretation: Past, present and future[C/OL] //Proc of the Joint Meeting of the 23rd EACSL Annual Conf on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symp on Logic in Computer Science (LICS). New York: ACM, 2014 [2022-04-19]. https://dl.acm.org/doi/pdf/10.1145/2603088.2603165
[13] Huynh B K, Ju Lei, Roychoudhury A. Scope-aware data cache analysis for WCET estimation[C] //Proc of the 17th IEEE Real-Time and Embedded Technology and Applications Symp (RTAS). Piscataway, NJ: IEEE, 2011: 203−212
[14] Stock G, Hahn S, Reineke J. Cache persistence analysis: Finally exact[C] //Proc of the 40th IEEE Real-Time Systems Symp. Piscataway, NJ: IEEE, 2019: 481−494
[15] Baier C, Katoen J P. Principles of Model Checking[M]. Cambridge, MA: MIT Press, 2008
[16] Wilhelm R. Why AI + ILP is good for WCET, but MC is not, nor ILP alone[C] //Proc of the 5th Verification, Model Checking, and Abstract Interpretation. Berlin: Springer, 2004: 11−13
[17] Metzner A. Why model checking can improve WCET analysis[C] //Proc of the 16th Int Conf on Computer Aided Verification. Berlin: Springer, 2004: 334−347
[18] Dalsgaard A E, Olesen M C, Toft M, et al. Metamoc: Modular execution time analysis using model checking[C] //Proc of the 10th Int Workshop on Worst-Case Execution Time Analysis (WCET 2010). Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010: 113−123
[19] Gustavsson A, Ermedahl A, Lisper B, et al. Towards WCET analysis of multicore architectures using UPPAAL[C] //Proc of the 10th Int Workshop on Worst-Case Execution Time Analysis (WCET 2010). Dagstuhl: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010: 101−112
[20] Cassez F, de Aledo P G, Jensen P G. WUPPAAL: Computation of worst-case execution-time for binary programs with UPPAAL[M] //Models, Algorithms, Logics and Tools. Cham, Switzerland: Springer, 2017: 560−577
[21] Lü Mingsong, Guan Nan, Deng Qingxu, et al. McAiT—A timing analyzer for multicore real-time software[C] //Proc of the 9th Int Symp on Automated Technology for Verification and Analysis. Berlin: Springer, 2011: 414−417
[22] 陈芳园, 张东松, 刘聪, 等. 基于取指执行时序范畴的多核共享Cache干扰分析[J]. 计算机研究与发展, 2013, 50(1): 206−217 Chen Fangyuan, Zhang Dongsong, Liu Cong, et al. Analysis of inter-thread interference on shared Cache multi-core architectures based on instruction fetch timing frame[J]. Journal of Computer Research and Development, 2013, 50(1): 206−217 (in Chinese)
[23] Uhrig S, Tadros L, Pyka A. MESI-based cache coherence for hard real-time multicore systems[C] //Proc of the 8th Int Conf on Architecture of Computing Systems. Berlin: Springer, 2015: 212−223
[24] Hassan M, Kaushik A M. Patel H. Predictable cache coherence for multi-core real-time systems[C] //Proc of the 23rd IEEE Real-Time and Embedded Technology and Applications Symp (RTAS). Piscataway, NJ: IEEE, 2017: 235−246
[25] Tsoupidi R M. Two-phase WCET analysis for cache-based symmetric multiprocessor systems[D]. Stockholm, Sweden: KTH Royal Institute of Technology, 2017
[26] 陈继承, 李一韩, 赵雅倩, 等. 一种基于共享转发态的多级缓存一致性协议[J]. 计算机研究与发展, 2017, 54(4): 764−774 Chen Jicheng, Li Yihan, Zhao Yaqian, et al. A shared-forwarding state based multiple-tier cache coherency protocol[J]. Journal of Computer Research and Development, 2017, 54(4): 764−774 (in Chinese)
-
期刊类型引用(1)
1. 刘行，郭靓，王正琦，韦小刚，徐雪菲，刘京. 基于Q学习的安全服务功能链编排算法. 计算机与现代化. 2024(11): 34-40 . 
百度学术
其他类型引用(1)
计量
- 文章访问数: 270
- HTML全文浏览量: 17
- PDF下载量: 169
- 被引次数: 2
