本技术涉及计算机体系结构，尤其涉及面向稀疏矩阵向量乘计算的软硬件协同设计方法和框架。
背景技术：
1、spmv是图计算、神经网络、经济建模等科学或工程应用中广泛应用的核心算法。由于在这些应用程序中spmv通常占据主要的执行时间，因此需要一个高性能的spmv加速器。而fpga具有较大的片外带宽、可定制的逻辑单元和高性能的浮点单元，是加速spmv的合适平台。
2、由于spmv中的矩阵包含大量零元素，所以通常对其进行压缩，使计算中只包含非零元素及其行列索引。在压缩矩阵之后，spmv成为了一个受内存约束的问题。对于给定位宽的片外存储器接口，如何充分利用带宽对spmv的性能至关重要。因此，带宽利用率(bu)是基于fpga的spmv加速器广泛采用的指标。对于固定长度的数据行，即从片外存储器传输到片上存储器的最小数据移动单元，在数据行中存放更多的非零元素及其索引可以提高bu。同时进行更多的乘法运算需要更多被并行处理的非零元素，也就需要更多对向量元素的随机访问。然而，使用传统的内存划分方法也无法有效应对大量的并行数据访问，因此很容易发生访问冲突，导致流水线停滞和较差的bu。因此，如何处理这种不规则的内存访问对于spmv加速器是一个很有挑战的任务。
3、为了应对上述挑战，现有工作主要分为四种。第一种方法通过按列执行spmv，将不规则的向量访问转换为流式访问从而使向量元素可以得到最大程度的重用。然而，按列执行很容易发生部分和的读后写问题，从而导致更长的延迟和较差的bu。第二种方法设计一种新的数据格式，在这种格式中列索引会被对应的向量元素替代。但是，在没有任何向量元素复用的情况下，数据行可以包含的非零元素就会减少，这就会导致糟糕的bu。第三种对非零元素重排序，以便将具有相同列索引的非零元素分配到同一数据行中。通过部分数据重用，数据行中需要的列索引就更少，从而提供了实现更高bu的机会。然而，重排序的效果，即有多少非零元素可以共享同一个非零元素，高度依赖于稀疏矩阵中非零元素的分布，导致对不同矩阵的bu结果产生很大干扰。最后一种方法通过部分向量复制为向量元素访问提供了更多的端口。由于只在硬件层面做了优化，这种方法只能取得有限的bu。现有的工作或把重点放在软件层面的优化，或专注于硬件层面的优化。因此，他们无法在各种不同的矩阵上都取得最优的性能。
技术实现思路
1、本技术旨在至少在一定程度上解决相关技术中的技术问题之一。
2、为此，本技术的第一个目的在于提出一种面向稀疏矩阵向量乘计算的软硬件协同设计方法，用于提升spmv任务的带宽利用率。
3、本技术的第二个目的在于提出一种面向稀疏矩阵向量乘计算的软硬件协同设计框架。
4、为达上述目的，本技术第一方面实施例提出了一种面向稀疏矩阵向量乘计算的软硬件协同设计方法，包括：根据矩阵参数和设备参数定义可扩展的压缩数据格式；评估不同的参数组合在矩阵上的性能，确定最优参数组合，其中，最优参数组合包括批次高度h、批次宽度w、组大小n、端口数量p；基于最优参数组合，根据预定义的模板确定硬件参数，并确定对应的spmv加速器；基于最优参数组合和定义的可扩展的压缩数据格式，使用重排序算法对矩阵和对应的向量进行数据打包，生成压缩存储数据并在spmv加速器上执行，完成矩阵向量的乘计算。
5、本技术实施例的面向稀疏矩阵向量乘计算的软硬件协同设计方法，针对特定的稀疏矩阵在软件和硬件上进行设计空间探索。通过为不同的矩阵选择最合适的软硬件参数并基于预定义的硬件模板快速生成适配的加速器来获得最优的性能。
6、可选地，在本技术的一个实施例中，可扩展的压缩数据格式包括头区域、重用标志区域和类coo数据区域，每个区域使用一条或多条数据行，头区域包括标识批次的头标识符、复用标志行数、行索引基址和列索引基址，类coo数据区域的每一行由n个非零元素及其行索引和列索引组成，每一行包含p个用来获取向量元素的列索引，每一行还包含n-p个用来复用来自同一组或前面相邻组的向量元素的非零元素，其中，p/2≤bs，bs为目标器件的bram大小。
7、可选地，在本技术的一个实施例中，评估不同的参数组合在矩阵上的性能，确定最优参数组合，包括：
8、获取不同的参数组合(n，p，h，w)、矩阵和加速器流水线深度；
9、选定当前评估的参数组合(n，p，h，w)，并根据参数h和w将矩阵划分为多个批次；
10、对每个批次进行评估，并基于所有批次的评估结果和加速器流水线深度确定当前评估的参数组合的周期数；
11、将周期数最少的参数组合确定为最优参数组合。
12、可选地，在本技术的一个实施例中，对当前批次进行评估，包括：
13、对当前批次统计得到单个元素的数量ns、复用列的数量nr、所有复用列中的非零元素数量ne、矩阵中非零元素总数nnz和数据分组后剩余的不能复用向量元素的单个元素数量residue，其中，
14、根据residue和nnz计算得到组的数量作为当前批次的评估结果；
15、基于所有批次的评估结果和加速器流水线深度确定当前评估的参数组合的周期数，包括：
16、基于所有批次的组的数量、数据头数量、块切换开销确定当前评估参数组合的周期数。
17、可选地，在本技术的一个实施例中，基于最优参数组合和定义的可扩展的压缩数据格式，使用重排序算法对矩阵和对应的向量进行数据打包，包括：
18、使用重排序算法对矩阵进行预处理，并将预处理后的矩阵和对应的向量存储在dram中；
19、根据确定的最优参数组合(n，p，h，w)对存储在dram中的矩阵和对应的向量进行划分，得到不同批次的数据；
20、在数据打包过程中，将不同批次的数据按照压缩数据格式的头、重用标志行和类coo的数据附加到输出文件中。
21、可选地，在本技术的一个实施例中，压缩存储数据在spmv加速器上的执行包括数据准备阶段、数据处理阶段、数据累加阶段和数据写回阶段，加速器包括解码器、矩阵缓冲区、向量缓冲区、复用标志fifo、向量扩展模块、pe阵列、无冲突加法器树、交叉阵列开关、累加器、uram，压缩存储数据在spmv加速器上的执行过程包括：
22、在数据准备阶段，通过解码器将块对应的向量段从dram加载并存储在向量缓冲区中，并将按照压缩数据格式存储的数据通过解码器从dram以流水线方式发送到复用标志fifo或矩阵缓冲区中，并使用向量扩展模块根据复用标志fifo中的复用标志将向量元素数量从p扩展到n；
23、在数据处理阶段，使用pe阵列中的n个pe对数据准备阶段产生的n对矩阵元素和向量元素进行乘法运算，并使用无冲突加法器树对乘法运算结果进行累加；
24、在数据累加阶段，将无冲突加法器树的结果通过交叉阵列开关传到对应的累加器中进行累加；
25、在数据写回阶段，在当前批次的数据执行结束后，将对应的部分和写回到uram，在整个矩阵完成后，将uram中的结果写回到片外dram中。
26、可选地，在本技术的一个实施例中，确定对应的spmv加速器，包括：
27、通过5阶段浮点数加法器和20阶段浮点数乘法器实现pe阵列、无冲突加法器树和累加器，其中，每个累加器包括第一寄存器组、第二寄存器组和第三寄存器组，第一寄存器组组保存当前批次的部分和，第二寄存器组保存上一批次计算得到的数据并写回uram，第三寄存器组从uram预取下一批次的部分和，uram的接口构造有高带宽片上数据总线，用于保证在当前批次的执行过程中回写上一批次计算的结果，并获取获取下一批次的所有初始部分和。
28、可选地，在本技术的一个实施例中，使用无冲突加法器树对乘法运算结果进行累加，包括：
29、对输入的部分和进行重新排序，使得具有相同行索引的部分和彼此相邻；
30、将排序后的部分和分成若干组，发送给多个子树进行累加，得到相应的结果；
31、将无冲突加法器树的结果通过交叉阵列开关传到对应的累加器中进行累加，包括：
32、对于每个组，使用一个完整的交叉阵列开关从相应的子树中选择对应的结果，其中，选择过程包括：
33、若一个部分和与另一个部分和相加，则完整的交叉阵列开关选择零作为输出，并发送到下一阶段，若不同组的输出之间有冲突的部分和，则通过一个边界加法器将冲突的结果累加。
34、为达上述目的，本发明第二方面实施例提出了一种面向稀疏矩阵向量乘计算的软硬件协同设计框架，包括压缩数据格式定义模块、最优参数组合选择模块、spmv加速器确定模块、计算模块，其中，
35、压缩数据格式定义模块，用于根据矩阵参数和设备参数定义可扩展的压缩数据格式；
36、最优参数组合选择模块，用于评估不同的参数组合在矩阵上的性能，确定最优参数组合，其中，最优参数组合包括批次高度h、批次宽度w、组大小n、端口数量p；
37、spmv加速器确定模块，用于基于最优参数组合，根据预定义的模板确定硬件参数，并确定对应的spmv加速器；
38、计算模块，用于基于最优参数组合和定义的可扩展的压缩数据格式，使用重排序算法对矩阵和对应的向量进行数据打包，生成压缩存储数据并在spmv加速器上执行，完成矩阵向量的乘计算。
39、可选地，在本技术的一个实施例中，可扩展的压缩数据格式包括头区域、重用标志区域和类coo数据区域，每个区域使用一条或多条数据行，头区域包括标识批次的头标识符、复用标志行数、行索引基址和列索引基址，类coo数据区域的每一行由n个非零元素及其行索引和列索引组成，每一行包含p个用来获取向量元素的列索引，每一行还包含n-p个用来复用来自同一组或前面相邻组的向量元素的非零元素，其中，p/2≤bs，bs为目标器件的bram大小。
40、本技术附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本技术的实践了解到。
1.一种面向稀疏矩阵向量乘计算的软硬件协同设计方法，其特征在于，包括以下步骤：
2.如权利要求1所述的方法，其特征在于，所述可扩展的压缩数据格式包括头区域、重用标志区域和类coo数据区域，每个区域使用一条或多条数据行，所述头区域包括标识批次的头标识符、复用标志行数、行索引基址和列索引基址，所述类coo数据区域的每一行由n个非零元素及其行索引和列索引组成，每一行包含p个用来获取向量元素的列索引，每一行还包含n-p个用来复用来自同一组或前面相邻组的向量元素的非零元素，其中，p/2≤bs，bs为目标器件的bram大小。
3.如权利要求1所述的方法，其特征在于，评估不同的参数组合在矩阵上的性能，确定最优参数组合，包括：
4.如权利要求3所述的方法，其特征在于，对当前批次进行评估，包括：
5.如权利要求2所述的方法，其特征在于，基于所述最优参数组合和定义的可扩展的压缩数据格式，使用重排序算法对矩阵和对应的向量进行数据打包，包括：
6.如权利要求5所述的方法，其特征在于，所述压缩存储数据在所述spmv加速器上的执行包括数据准备阶段、数据处理阶段、数据累加阶段和数据写回阶段，所述加速器包括解码器、矩阵缓冲区、向量缓冲区、复用标志fifo、向量扩展模块、pe阵列、无冲突加法器树、交叉阵列开关、累加器、uram，所述压缩存储数据在所述spmv加速器上的执行过程包括：
7.如权利要求6所述的方法，其特征在于，所述确定对应的spmv加速器，包括：
8.如权利要求6所述的方法，其特征在于，使用所述无冲突加法器树对乘法运算结果进行累加，包括：
9.一种面向稀疏矩阵向量乘计算的软硬件协同设计框架，其特征在于，包括压缩数据格式定义模块、最优参数组合选择模块、spmv加速器确定模块、计算模块，其中，
10.如权利要求9所述的装置，其特征在于，所述可扩展的压缩数据格式包括头区域、重用标志区域和类coo数据区域，每个区域使用一条或多条数据行，所述头区域包括标识批次的头标识符、复用标志行数、行索引基址和列索引基址，所述类coo数据区域的每一行由n个非零元素及其行索引和列索引组成，每一行包含p个用来获取向量元素的列索引，每一行还包含n-p个用来复用来自同一组或前面相邻组的向量元素的非零元素，其中，p/2≤bs，bs为目标器件的bram大小。
