计算机工程与科学投稿论文格式参考:基于便笺式存储器的向量化SpMV算法的性能评估与分析 *

关键词：稀疏矩阵向量乘;便笺式存储器;CSR;ARM SVE

作者：张宗茂;董德尊;王子聪;常俊胜;张晓云;王绍聪

作者单位：国防科技大学

阿斯顿发顺丰的

　　1 引言

　　稀疏矩阵向量乘 SpMV (Sparse Matrix Vector Multiplication) 是矩阵向量运算的一种特殊形式。其主要操作是执行y=y+Ax运算其中 A 是稀疏矩阵，x 和 y 分别是稠密输入和输出向量 是稀疏线性运算的重要内核函数，广泛应用于高性能计算、人工智能、大数据等领域。SpMV 是高性能计算领域基准测试程序 HPCG (High Performance Conjugate Gradient) 代码中的重要组成部分，也是图计算库 GraphBLAS 的必备计算内核。

　　稀疏矩阵中大量的零元素给存储和计算带来了极大的挑战。为了降低稀疏矩阵存储开销并加速 SpMV 计算，研究人员提出了多种稀疏矩阵存储格式。除了 COO (COOrdinate)、CSR (CompressedSparseRow)、DIA (DIAgonal) 和 ELL (ELLPACK) 等稀疏矩阵基本存储格式外，研究人员基于这些基本存储格式开发了很多新的存储格式，如 BCCOO (Blocked Compressed common COOrdinate)、CSB (Compressed Sparse Block)、SELL (Sliced ELLPACK) 等，针对不同的计算平台和处理器体系结构状态以提升 SpMV 算法执行过程中数据局部性，从而提升 SpMV 算法性能。此外，为了对 SpMV 进行高效向量化，文献 [6] 提出了 CSR5 存储格式。Regnault 等人提出了 SPC5 格式，并借助 Intel AVX-512 对 SpMV 进行向量优化。文献 [8] 提出适合向量化的矩阵存储格式 CVR (Compressed Vectorization-oriented sparse Row)，该格式可以同时处理稀疏矩阵的多行，并将其分成多个单指令多数据 SIMD (Single Instruction Multiple Data) 通道，以利用现代处理器中的向量部件。但是，大多数改进的矩阵存储格式会引入额外的矩阵存储格式转换开销。

　　便笺式存储器 SPM (ScratchPadMemory) 是一种结构简单、访存延迟固定、功耗低、面积小的片上高速存储器，被广泛应用在嵌入式处理器、GPU 和各类加速器中。IBM CELL 处理器用便笺式存储器代替部分片上 Cache，以降低处理器功耗和面积开销。GPU 中的共享内存 SM (Shared Memory) 本质上也是便笺式存储器。与完全由硬件控制的 Cache 不同，便笺式存储器由软件管理。在计算机系统中，便笺式存储器和内存统一存储空间编址，应用开发人员可以根据应用程序的特征和需要，在程序中直接对便笺式存储器进行数据分配，以降低程序执行过程中的访存冲突，从而提升程序执行效率。

　　随着 Moore 定律和 Dennard 缩放定律的失效，计算机系统难以通过简单增加处理器上晶体管数量和提升处理器时钟频率进一步提升性能。因此，计算机体系结构研究人员和软件开发人员利用并行化提升处理器性能和应用程序执行效率。指令级并行 ILP (Instruction Level Parallelism) 和线程级并行 TLP (Thread Level Parallelism) 已经被广泛用于提升系统性能，如流水线、Tomasulo 算法和同时多线程 SMT (Simultaneous MultiThreading) 等机制 。此外，数据级并行 DLP (Data Level Parallelism) 可以通过向量运算能力和单指令多数据 SIMD 进一步提升处理器性能和能效。许多应用程序通过数据级并行，借助处理器的向量执行能力可以极大程度提升应用程序性能，但其执行效率与代码向量化的质量密不可分。

　　SpMV 是访存密集型应用程序，由于矩阵的压缩存储，在计算过程中大量的间接访存和对稠密输入向量 x 的不规则访存不仅使得性能受限，而且很难高效向量化。便笺式存储器是一种软件控制的片上高速存储器，因此，可以将 SpMV 执行过程中的输入向量存放在便笺式存储器中，以改善计算过程中的访存冲突。随着数据级并行在通用处理器中的大量应用，对应用程序进行向量化优化可以显著提升程序执行效率。本文使用 ARM SVE (Scalable Vector Extension) 对基于 CSR 格式的 SpMV 算法进行向量化；基于 gem5 模拟器实现便笺式存储器及其软件访问接口，以评估便笺式存储器对向量化 SpMV 算法性能影响。本文对稀疏矩阵库 SuiteSparse Collection 中 2562 个真实应用矩阵进行测试。实验结果表明，集成了便笺式存储器的处理器与传统多级 Cache 处理器相比，针对向量化 SpMV 算法能够实现的最大加速比为 7.45，平均加速比为 1.11。

　　2 研究背景

　　本节对稀疏矩阵基本存储格式及其 SpMV 算法、便笺式存储器结构和 ARM SVE 进行介绍。

　　2.1 稀疏矩阵存储格式与 SpMV 算法

　　由于稀疏矩阵中存在大量的零元素，故如何高效存储稀疏矩阵是 SpMV 计算首先需要解决的问题。过去几十年，研究人员根据不同的应用需求和特性提出了很多稀疏矩阵存储格式，但 CSR 存储格式仍然是当前最通用的矩阵存储格式，许多矩阵计算库和线性计算库都是基于 CSR 实现，如 Eigen、Taco 和 IntelMKL (Math Kernel Library) 等。

　　COO 矩阵存储格式是稀疏矩阵最简单的一种压缩存储格式 ，采用 data、row_ptr 和 col_idx 3 个一维数组分别存储矩阵非零元数值、非零元行号和列号。COO 格式对应的 SpMV 算法如算法 1 所示。COO 格式适用于任意结构的稀疏矩阵，其 SpMV 算法实现简单，但缺点是会存储大量重复值，导致存储效率不高。

　　CSR 格式是当前应用最广泛的矩阵存储格式。CSR 格式使用 data、row_ptr 和 col_idx 3 个一维数组存储稀疏矩阵。其中，data 用于存储矩阵非零元值，col_idx 用于存储矩阵非零元的列索引，row_ptr 用于存储矩阵每行非零元的起始位置。该格式最大的优点是压缩率高，存储开销小，对矩阵的结构和非零元分布不敏感，通用性好，适用于绝大多数应用场景。CSR 格式对应的 SpMV 算法如算法 2 所示。该算法对输入向量 x 的大量间接访问导致其数据局部性较差且向量化效率低。

　　2.2 便笺式存储器

　　便笺式存储器是一种访存延迟固定的快速随机访问的片上存储设备。便笺式存储器由译码单元、存储阵列和列电路 3 个部分构成，数据直接存放在存储阵列中，不需要额外的部件进行标识。与片上 Cache 相比，便笺式存储器没有复杂的数据失效、脏行替换和写回等机制，因此不需要用额外的 Tag 体存储标签位，其功耗和面积显著低于 Cache。

　　便笺式存储器最大的特点是具有独立的地址空间，与计算机系统主存统一存储空间编址。因此，研究人员可以直接对其进行读写控制，在程序中实现对便笺式存储器的数据分配，从而改善数据局部性，提升程序性能。Cache 和便笺式存储器特点比较如表 1 所示。

　　2.3 ARM SVE

　　SVE 是 ARM 针对高性能计算需求提出的第 2 代高级 SIMD 扩展，是面向高性能计算负载开发的一组新的向量指令。与 AVX 和 AVX512 等向量长度固定的指令集相比，SVE 是向量长度不可知 VLA (Vector Length Agnostic) 的指令集，其向量寄存器大小是可变的，范围为 128~2048bit。

　　SVE 中主要包含 4 类寄存器：32 个大小可变的数据寄存器 Z0~Z31，用于存储向量数据；16 个断言寄存器(P 0 ~ P 15)用于标识数据寄存器中哪些数据参与运算；控制寄存器，即 FFR (First Fault Register) 寄存器和 ZCR_Elx 寄存器。

　　要在程序中使用 SVE 指令，有以下几种方法： (1) SVE 优化库：直接调用 ARMPerformance Libraries 等优化库，其特点是使用方便，但灵活性较差。 (2) 内联汇编：直接在代码中添加 SVE 汇编指令，但编程难度大，程序可读性差。 (3) SVE intrinsic：ACLE (ARM C Language Extension) 中将 SVE 向量指令封装成函数的形式供用户使用。这种方法只需调用相应 intrinsic 函数即可，编程简单，代码可读性强。本文采用这种方式对 SpMV 算法进行向量化优化。

　　3 基于便笺式存储器的 SVE 向量化 SpMV 算法优化

　　本节将阐述便笺式存储器在 gem5 模拟器中的模拟实现，以及基于便笺式存储器的向量化 SpMV 算法优化实现。

　　3.1 基于 gem5 的便笺式存储器实现

　　在 gem5 模拟器中，处理器内存系统通过其定义好的存储模型以及相关接口实现，因此可以借助已有存储模型设置便笺式存储器的特征参数，如大小、带宽和访问延迟等。然后再通过 gem5 中连接不同组件的端口将便笺式存储器和处理器与其他组件进行连接即可。

　　在通用处理器中，CPU 和 Cache 通过总线直接与内存和外设连接，便笺式存储器也是通过总线和处理器的其他部件进行数据交互。在 gem5 模拟器中，CPU 模型中的片上存储设备通过无延迟的 crossbar 与各组件的对应端口进行连接。

　　本文提出的便笺式存储器基于 gem5Classic 内存模型，创建了 SPM_Xbar 用于与处理器中存储部件连接。将便笺式存储器侧端口和 SPM_Xbar 处端口进行连接，实现了处理器的存储系统扩展。为了实现便笺式存储器与 CPU 间的数据传输，CPU 侧新增的端口与 SPM_Xbar 连接以搭建 CPU 和便笺式存储器间数据通路，其实现如图 2 所示。

　　便笺式存储器和内存统一编址，要在程序中实现对便笺式存储器的访问与控制，需要提供便笺式存储器的访问接口。本文使用的便笺式存储器分配接口函数原型为void*spm_mem_alloc (uint64_t mem_size,uint64_t mem_address)，其中，mem_

　　size 表示便笺式存储器的存储空间容量，mem_address 表示便笺式存储器在内存地址空间中的起始地址。该函数的实现是通过 mmap 系统调用函数将便笺式存储器的存储空间映射到统一内存地址，返回指向便笺式存储器的指针。在程序中调用该接口会返回一个任意类型指针，通过对返回的指针进行读写操作实现对便笺式存储器的访问与控制。

　　3.2 基于 CSR 格式的 SpMV 算法的 SVE 向量化

　　本文借助 ARM 提供的 SVE intrinsics 函数对基于 CSR 存储格式的 SpMV 算法进行 SVE 向量化，如算法 3 所示。

　　其中，svsum、val、idx 和 svx 是数据寄存器，分别用于存储计算中间结果、矩阵非零元值、非零元列索引和输入向量 x 部分值；pg 是断言寄存器，用于标识寄存器中哪些数据会参与运算。在加载向量 x 的值时由于需要从多个不同位置获取对应数据，因此需要借助非零元列索引，使用 gather 指令获取数据。当矩阵一行非零元计算完成后，使用 scatter 指令对 svsum 寄存器中的数据进行归约操作并将其写回输出向量 y 对应位置。

　　4 实验与结果分析

　　在本节中使用 gem5 全系统模拟器评估基于 CSR 的向量化 SpMV 算法在集成了便笺式存储器的处理器中的性能。

　　4.1 模拟系统配置

　　本文在 gem5 中扩展并实现了便笺式存储器，并使用顺序 CPU 模型对 ARMv8 单核处理器进行模拟，采用 gem5 全系统执行模式，将 SpMV 算法执行过程中不规则访问的输入向量 x 存放在便笺式存储器中。模拟系统使用的内核为 Linux 4.18，操作系统为 Ubuntu 16.04。模拟处理器的系统配置如表 2 所示。

 

　　4.2 数据集

　　为了分析基于 CSR 的向量化 SpMV 算法性能提升，受限于便笺式存储器实验配置 (128 KB，即最多存储 16 384 个双精度浮点数)，本文选择 SuiteSparse Market Collection 数据集中行数不超过 16 384 (即 2^14) 的 2 562 个稀疏矩阵进行测试。

　　本文测试的稀疏矩阵均来自真实应用程序，涵盖了图计算、计算流体力学、网络图、机器学习和电路模拟等多个应用领域。所用稀疏矩阵的结构特点如表 3 所示。

　　4.3 实验结果分析

　　SVE 向量化的 SpMV 算法在集成便笺式存储器的处理器中的加速比如图 3 所示。与传统处理器相比，集成了便笺式存储器的处理器能够实现的最大加速比为 7.45，平均加速比为 1.11。在传统处理器中，SpMV 算法在执行过程中首先需要执行加载指令获取矩阵非零元列索引，然后再通过 gather 指令获取计算所需的输入向量值。由于矩阵非零元分布不规律，data 数组中的连续非零元间的列索引值差值通常较大，使得 gather 指令执行过程中会频繁发生 Cache 失效，从而降低了 SpMV 算法执行效率。另外，Cache 失效处理的

　　延迟不固定，对 SpMV 算法性能也有较大影响。在集成了便笺式存储器的处理器中输入向量 x 存储在便笺式存储器中，当获取到矩阵非零元列索引后，使用 gather 指令将所需数据从便笺式存储器传输到向量寄存器该方法避免了向量 x 的不规则访问，显著降低了计算过程中的访存冲突，从而提升了 SpMV 算法执行效率。

　　为了更加详细地分析便笺式存储器在不同特征矩阵下 SpMV 算法的性能影响，本文对测试的 2562 个矩阵，根据 SpMV 算法获得的加速比进行划分，分成 4 个组，编号为 1~4，不同矩阵的基本特征如表 4 所示。

　　在集成便笺式存储器的处理器中执行 SpMV 算法，加速比超过 1.5 的矩阵共 45 个，占比 1.76%。组 1 矩阵的特点是：矩阵行数最大为 13332，非零元最大数量为 5472，稀疏度最大为 15.52%。矩阵非零元数量小，非零元分布比较规律，如表 5 编号 1 的 2 个矩阵，能够实现最高的 SpMV 加速比。

　　此外，在传统多级 Cache 处理器中，Cache 缺失的延迟不固定，而在集成便笺式存储器的处理器中对输入向量 x 的访问由便笺式存储器完成访存冲突更小，因此能够实现更高的加速比。稀疏度超过平均值的 24 个矩阵，其矩阵规模较小，矩阵行数平均为 62，平均每行有 2 个非零元，可以通过一条 SVE 计算指令处理一行矩阵元素，能够进一步减小对结果向量 y 的访存开销对于另外个矩阵，虽然矩阵规模更大，但非零元的分布非常均匀，使得计算过程中访存冲突较少，因而该组矩阵性能最好。

　　组 2 矩阵数量为 923，占比 36%。该组矩阵的规模比组 1 的更大，矩阵稀疏程度有较大差异。能够实现较好加速比是因为这些矩阵的非零元分布相对均匀，计算过程中，访存冲突相对较小，能够实现较好的加速比。相比于组 1，其矩阵规模更大，计算过程中访存冲突更多，因而其性能较差。

　　组 3 矩阵数量为 1453 个，占比 56.7%。该组矩阵的特点是矩阵规模相对较小，但非零元数量远大于其他组。每行非零元数量平均为 11，非零元分布非常不规律，读取非零元列索引会频繁引发 Cache 行替换，降低了处理器的吞吐量，从而影响 SpMV 算法性能。

　　组 4 矩阵数量为 141，占比 5.5%。该组矩阵的特点是矩阵规模较大，非零元数量小，非零元分布不规律。除了非零元分布不规律导致计算过程的访存开销外，该组矩阵存在的大量空行 (非零元数量远小于矩阵行数矩阵数量为 54) 对结果向量写回造成更多 Cache 行替换，从而影响 SpMV 执行效率。

　　为了进一步分析便笺式存储器对不同应用领域下 SpMV 算法的加速效果，本文将测试矩阵按照所属应用类别进行划分。所有测试的 2562 个矩阵共包含 99 个应用类别，矩阵数量超过 20 个的应用类别共 17 个，矩阵总数为 2221，其比例为矩阵总量的 86.69%，不同类别矩阵的基本特点如表 6 所示。

　　不同应用类别对应基于 CSR 格式的向量化 SpMV 算法在集成便笺式存储器的通用处理器中的平均加速比如图 4 所示。17 个应用类别中，AG_Monien 平均加速比最大，为 1.61；加速比最小为 1.02，属于 Pajek 应用类别；平均加速比为 1.12。AG_Monien 中大多数矩阵结构比较规整，矩阵中每行连续非零元列索引差值较大。在传统多级 Cache 处理器中，SpMV 算法执行过程中会频繁发生 Cache 缺失，将计算过程中经常访问的稠密向量存放在便笺式存储器中，可以显著降低计算过程中的访存冲突，能够实现最高加速比。

　　Pajek 中的矩阵来源于不同领域的图，其数据分布没有明显的结构特征，矩阵每行非零元分布相对均匀，计算过程中访存冲突较小。因此，传统多级 Cache 处理器与集成便笺式存储器的处理器相比，其性能差异较小，从而导致具有最小加速比。

　　实验数据表明，在通用处理器中集成便笺式存储器能够有效缓解 SpMV 算法执行过程中的访存冲突，从而提升 SpMV 算法执行效率。但是，SpMV 算法性能与矩阵的稀疏结构、非零元分布也密切相关。由于便笺式存储器对不同应用领域的加速效果有显著差异，因此在加速 SpMV 算法执行过程中，还可以根据应用领域的特征，对矩阵存储格式进行改进，以改善数据局部性，从而更好地利用便笺式存储器，加速 SpMV 算法。

　　5 结束语

　　SpMV 是高性能计算、人工智能和大数据等领域中非常重要的内核函数。在传统多级 Cache 处理器中计算对稠密输入向量 x 的不规则访存会频繁导致 Cache 失效，从而影响 SpMV 算法执行效率。便笺式存储器是一种结构简单、访存延迟固定且软件可控的片上高速存储器，和处理器内存统一编址，具有用户可以直接控制的存储空间。为了改善 SpMV 算法执行过程中的访存冲突，本文利用便笺式存储器对 SpMV 算法进行了优化。为了进一步提升 SpMV 算法执行效率，本文对基于 CSR 格式的 SpMV 算法进行了向量化优化。本文使用 gem5 全系统模拟器对 SuiteSparse Matrix Collection 数据集中的 2562 个稀疏矩阵进行测试与分析。实验结果表明，集成了便笺式存储器的处理器与传统多级 Cache 处理器相比，针对向量化 SpMV 算法能够实现的最大加速比为 7.45，平均加速比为 1.11。