1、1矩阵乘在通用 DSP 上的峰值性能模型摘要：DSP 具有能效比高的特点，可以用于通用高性能计算.矩阵乘是许多科学与计算问题的核心算法，在 DSP 上取得高性能具有重要的理论和现实意义.面向通用 DSP，提出了矩阵乘并行算法，建立了矩阵乘峰值性能模型，根据性能模型，构建了矩阵乘性能达 Tflops 级 DSP 体系结构参数配置，对通用 DSP 的设计参数给出了明确的性能指标要求，包括乘加流水线数量、寄存器数目、带宽和延迟. 关键词：通用 DSP；矩阵乘；并行算法；性能评测 中图分类号：TP332.2 文献标识码：A A Peak Performance Model for Matrix Mul
2、tiplication on General-Purpose DSP LIU Jie， CHI Li-hua， XIE Lin-chuan， WANG Yang， GAN Xin-biao， FENG Hua，HU Qing-feng （Science and Technology on Parallel and Distributed Processing Laboratory， National Univ of Defense Technology， Changsha， Hunan 410073，China） Abstract： DSP processor can be used to s
3、olve the high performance computation problems， which has the characteristics of high computing performance and low power. Matrix multiplication algorithm is the kernel of many 2scientific and technology computation， so it is of importance for theorem and practice. Based on general purpose DSP （GPDS
4、P） ，a new parallel algorithm for matrix multiplication was proposed. And a peak performance model for matrix multiplication was built. From the peak performance model， an architecture of GPDSP was set up， and the parameter of GPDSP with Tflops was given， which includes the number of pipe-line， the n
5、umber of SIMD registers， the breadth and latency for the hierarchical memories. Key words： general purpose DSP； matrix multiplication； parallel algorithm； performance evaluation DSP 是强调实时处理的低功耗体系结构，对 FFT 等信号处理专门计算具有很好的支持能力.2011 年，基于 TI 的 KeyStone 构建 C66xDSP 双精度性能达到 66 Gflops，功耗为 10 W，能效比高1.目前面向高性能计算
6、的通用 DSP 成为重要的研究方向. 矩阵乘是许多科学与工程计算问题的核心算法2，厂商和科研人员为不同的硬件平台研制了矩阵乘高性能优化库.AMD 公司开发了 ACML 基本数学运算库，Intel 公司开发了 MKL 基本数学运算库，均包含了使用汇编语言手工优化的高性能 BLAS 库3-4.GotoBLAS5-6和 ATLAS7针对不同的微处理器提供高性能 BLAS 库.因为新架构硬件平台不停地推出，新算法和优化方法的研制从未停止过，特别是当前多核多线的微处理器提供的新的依赖平台的并行技术，使得科研人员不断探索新的最优实现方3法. 矩阵乘算法（CM，N=AM，K*BK，N）C 中的每个结果元素可
7、以看成是A 的一行元素和 B 的一列元素的内积，为提高性能需要采用分块算法，并行计算时要进行二维的数据划分，对许多科学与工程计算问题具有借鉴意义.研制一款新型的面向科学计算的通用 DSP，首先要保证矩阵乘能达到峰值性能，Igual 等人8针对单精度 DSP TI 公司的 C66x 设计了矩阵乘并行算法，可以发挥峰值性能的 70%，能效比达到 7.4 Gflops/W，具有明显的低功耗、高性能特点. 本文面向基于多核和短向量技术的通用 DSP 模型，提出了一种新型的矩阵乘并行算法，建立了峰值性能模型，根据性能模型，对通用 DSP的设计参数给出了明确的性能指标要求，包括乘加流水线数量、寄存器数目、
8、带宽和延迟等，构建了矩阵乘性能达到 1 Tflops， 2 Tflops 和 4 Tflops 的 DSP 体系结构框架. 1 通用 DSP 模型 现代高性能微处理器中大多使用了 SIMD 技术，如 Intel 的 MMX 和SSE 系列，以及 AMD 的 3DNOW！等，使多个运算单元在一条指令的控制下对多个数据并行操作，这些 SIMD 扩展指令基于固定长度的短向量，通常为 256 位或 512 位，将多个数据打包存放在向量寄存器中进行并行计算，硬件代价低，控制简单，可以在较低的功耗下获得较高的性能. 图 1 给出了基于超长指令字结构的通用 DSP 模型，采用 SIMD 和多核技术构建.每个
9、单核由 SPU 和 VPU 构成，SPU 包括 L1I Cache， L1D Cache， SPE， 标量寄存器和流控制器，SPE 用于一些指令流的控制、对4向量单元的配置以及主要的通信任务；VPU 包括 AM， 向量寄存器和多个可并发执行的 VPE，多个 VPE 组成的向量 SIMD 单元主要用于数值运算. 假设存储不受限，通用 DSP 的峰值性能取决于以下参数设置：1）主频h（单位为 GHz） ；2）核数 c；3）单核内 VPE 的数量 v；4）单 VPE 浮点性能 f（单位为每周期双精度浮点数 flop/cycle）.峰值性能有以下计算公式： Rmax=hcvf. 影响通用 DSP 性能
10、的带宽和延迟主要包括：1）Global Memory（下文简称 GM）到 DMA 的带宽和延迟；2）DMA 到 Array Memory（下文简称AM）的带宽和延迟；3）AM 到向量寄存器的带宽和延迟；4）L1D 到标量寄存器的带宽和延迟. 2 矩阵乘并行算法 考虑矩阵乘法运算 C=C+AB，其中 C 是 mn 矩阵、A 是 mk 矩阵、B 是 kn 矩阵.矩阵乘要在通用 DSP 模型上获得高性能，需要针对通用DSP 的结构对矩阵乘进行并行算法的重新设计，基本原理是采用分块算法，将原矩阵乘运算转换为图 3 给出的分块矩阵乘运算. 4 通用 DSP 参数配置 通用 DSP 的设计只要满足带宽和延
11、迟的需求，矩阵乘就可以获得峰值性能，基本原理是将计算过程和数据迁移重叠起来，屏蔽数据迁移时间.假设每核向量寄存器的数目是 64 个，每拍从 AM 到向量寄存器可以读取 2 个向量，向量长度是 16，每个 VPE 拥有 2 条乘加流水线，单核每拍可以完成 4 个向量运算，AM 被平均分成两部分，一部分用来存储当前使5用的 AIJ 数据，一部分用于数据预取 AIJ.向量寄存器的一半用来存储矩阵 C，矩阵 C 以流水的方式进入 AM，C 的子矩阵大小为 1284，即 512个双精度数据，留相同大小空间预取数据，C 的子矩阵共使用 1 024 个double 数据空间. AM 用于存储矩阵 A 和矩阵
12、 C 的当前计算数据和预取数据.AM 为 1 MB时，共存储 131 072 个双精度数，可用于存储矩阵 A 的元素共 130 048个双精度数，其中 65 024 个用于存放当前参与计算的子矩阵，故子矩阵A 的大小为 256254.AM 为 2 MB 时，共存储 262 144 个双精度数，可以用于存储矩阵 A 的元素共 261 120 个双精度数，其中 130 560 个用于存放当前参与计算的子矩阵，故子矩阵 A 的大小可以取为 256510. 标量 L1D Cache 的大小取为 32 KB，4 096 个双精度数. 公式（5）和（6）中的 n 为矩阵 C 的列数，一般取值较大，对带宽的
13、影响较小，不妨取为 8 192；当向量寄存器的数目为 64 时，内层循环展开取为 884；每拍取两个向量；公式（7）实际使用中，需要根据每拍从 AM 读取向量寄存器的数目决定带宽要求，比如每拍两个向量，向量长度为 16，则从 AM 到向量寄存器的带宽需求为 256 Bytes/cycle. 根据上面给出的矩阵乘峰值性能模型可以得到通用 DSP 的参数配置，配置表见表 3. 至此我们构建了矩阵乘峰值性能 Tflops 级通用 DSP 模型，只要通用DSP 满足上述的参数配置，就可以得到峰值性能达到 1Tflops，2 Tflops和 4 TFlops 的通用 DSP. 5 结 论 6DSP 具有
14、高性能 、低功耗的特点，非常适用于具有计算密集特点的通用计算，并且越来越受到高性能计算领域的重视.本文尝试在通用 DSP模型上，提出了一种通过 DMA 完成数据迁移的高性能矩阵乘并行算法，基于分块算法，使用计算与数据迁移重叠技术屏蔽数据迁移时间，建立了峰值性能模型，重点对带宽和延迟进行了分析，基于矩阵乘峰值性能模型构建了 Tflops 级的通用 DSP 模型，可以给通用 DSP 的设计提供指导. 下一步需要对具体实现做模拟和仿真，验证通用 DSP 模型的实用性和有效性，并可以根据矩阵乘峰值性能模型、结构具体应用问题的计算特点，有针对性地构建新的通用 DSP. 参考文献 1 Texas Inst
15、ruments Incorporated. TMS320C66x multicore DSPs for high-performance computing R. Dallas， Texas： Texas Instruments Incorporated， 2011. 2 DONGARRA J J， CROZ J D， HAMMARLING S， et al. An extended set of FORTRAN basic linear algebra subprograms J. ACM Transactions on Mathematical Software， 1988， 14（1）：
16、 1-17. 3 DONGARRA J J， CROZ J D， HAMMARLING S， et al. A set of level 3 basic linear algebra subprograms J. ACM Transactions on Mathematical Software，1990， 16（1）： 1-17. 4 KAGSTROM B， LING P， LOAN C V. Gemm-based level3 7BLAS： high performance model implementations and performance evaluation benchmark
17、 J. ACM Transactions on Mathematical Software， 1998， 24（3）： 268-302. 5 GOTO K， VAN DE GEIJN R.High-performance implementation of the level-3 BLAS J. ACM Transactions on Mathematical Software， 2008， 35（1）：1-14. 6 GOTO K， VAN DE GEIJN R. Anatomy of high-performance matrix multiplication J. ACM Transac
18、tions on Mathematical Software，2008， 34（3）： 1-25. 7 WHALEY R C， PETITET A， DONGARRA J J. Automated expirical optimizations of software and the ATLAS project J. Parallel Computing， 2001， 27（3）： 3-35. 8 IGUAL F D， ALI M， FRIEDMANN A， et al. Unleashing the high-performance and low-power of multi-core DSPs for general-purpose HPCC/SC12 Proceedings of the International Conference on High Performance Computing， Networking， Storage and Analysis. Los Alamitos， CA， USA： IEEE Computer Society Press， 2012：26.1-26.19.
