一种对称矩阵与向量相乘的并行计算方法及其系统

摘要

本发明提出了一种对称矩阵与向量相乘的并行计算方法及其系统，方法包括：获取对称矩阵和向量，确定线程数；划分子区域；在每个子区域中，划定与对称轴平行的第一轴和/或第二轴；计算对称轴区域与向量，并写入寄存器；对第一轴进行两次不同的第一乘法计算，得到两组不同的数据并分别写入寄存器；对第二轴进行两次不同的第二乘法计算，得到两组或四组不同的数据并分别写入寄存器，得到对称矩阵与向量相乘的计算结果。本发明的方案，能够准确、快速的实现对称矩阵与向量的乘法计算，通过合理规划矩阵中元素处理的顺序，使各线程合理分配资源，能有效避免写入冲突，实现多线程并行计算，计算效率高，且各线程负载均衡，线程资源分布合理。

说明书

技术领域

本发明涉及矩阵数据处理领域，特别涉及一种对称矩阵与向量相乘的并行计算方法及其系统。

背景技术

一个实数矩阵A是由M×N个实数所构成的数据块。而一个向量x可以认为是一个由N×1个实数所构成的矩阵。矩阵A与向量间x的乘法结果y为一个M×1的向量。矩阵和向量的乘法定义如下：

通过处理器对矩阵乘法并行计算能有效缩短数据处理时间。开发并行算法时，一个重要的问题就是如何规避写入冲突。简单地说，写入冲突就是很多个同时运行的线程需要同时写入同一个内存地址。如果不做任何处理，则前面写入的结果可能会被后面的覆盖掉，造成结果错误。比如，两个线程同时想要往同一个内存地址上加1。假如原有的值为0，则正确的结果应为2。但如果线程执行顺序如下：

线程A：读取内存，得到0

线程B：读取内存，得到0

线程A：执行加法0+1＝1，得到结果为1

线程B：执行加法0+1＝1，得到结果为1

线程A：将结果1写回内存

线程B：将结果1写回内存

经过上述线程执行后，由于存在写入冲突，内存上结果仍为1。

现有技术在针对对称矩阵的计算时，或者是没有考虑到a

潜在的回写冲突是影响对称矩阵计算准确性和高效性的重要影响因素。此外，在并行计算过程中，线程的负载极不均衡，严重浪费处理器的线程资源。部分线程在处理完数据之后就会闲置，而部分线程则需处理大量的数据。

发明内容

有鉴于此，本发明提出了一种对称矩阵与向量相乘的并行计算方法及其系统，具体方案如下：

一种对称矩阵与向量相乘的并行计算方法，包括：

获取待计算的对称矩阵和向量，确定全部线程可并行计算的线程数；

以对称轴为界将所述对称矩阵划分为对称轴区域、上三角区域和下三角区域，将上三角区域或下三角区域以行为单位按照线程数分别划分多个子区域；在每个子区域中，划定与所述对称轴平行的第一轴和/或第二轴，所述第一轴上元素的数量等于所述线程数，所述第二轴上元素的数量小于所述线程数；

采用全部或部分线程并行计算所述对称轴区域与所述向量的乘积得到第一矩阵，将所述第一矩阵写入第一寄存器、第二寄存器或第三寄存器；

在每个子区域中，依序选定一个第一轴作为当前第一轴，采用全部线程对当前第一轴进行两次不同的第一乘法计算，得到两组不同的数据并分别写入第一寄存器和第二寄存器；

在每个子区域中，依序选定一个或两个第二轴作为当前第二轴，采用全部或部分线程对当前第二轴进行两次不同的第二乘法计算，得到两组不同的数据并分别写入第一寄存器和第二寄存器，或得到四组不同的数据并分别写入第一寄存器、第二寄存器和第三寄存器；

完成所述对称轴区域和各个子区域的计算后，基于第一寄存器、第二寄存器和第三寄存器中累加的数据构建矩阵，得到对称矩阵与向量相乘的计算结果。

在一个具体实施例中，当所述线程数大于1时，将所述子区域分为第一子区域和第二子区域，所述第一子区域的行数等于所述线程数，所述第二子区域的行数小于所述线程数；

所述上三角区域或所述下三角区域中至少有一个第一子区域；

在每个第一子区域中，划定第一轴和第二轴；

在每个第二子区域中，划定第二轴。

在一个具体实施例中，所述第二轴分为具备互补关系的第二轴和不具备互补关系的第二轴；

所述互补关系具体表现为：在同一子区域中，存在两个第二轴在元素数量之和上等于所述线程数；

当某一子区域中存在具备互补关系的第二轴时，则依序选定两个具备互补关系的第二轴作为当前第二轴，对当前第二轴分别进行两次乘法计算后，得到四组不同的数据。

在一个具体实施例中，所述第一乘法计算包括：

当前第一轴上的元素a

将a

将a

在一个具体实施例中，所述第二乘法计算包括：

当选定一个第二轴作为当前第二轴时，当前第二轴上的元素a

将a

将a

当选定两个第二轴作为当前第二轴时，其中一个当前第二轴上的元素a

将a

将a

将a

将a

在一个具体实施例中，在两个具备互补关系的第二轴中，元素数量不同；

对元素数量较多的第二轴进行两次乘法计算，得到两组数据，并将这两组数据分别写入到第一寄存器和第二寄存器；

对元素数量较少的第二轴进行两次乘法计算，得到两组数据，并其中一组数据写入到第三寄存器，另一组数据写入到第一寄存器或第二寄存器。

在一个具体实施例中，设对称矩阵阶数为M，所述线程数为L；

当M＝2nL+1时，将上三角区域或下三角区域以行为单位按照线程数分别划分2n个第一子区域；

其中，M、L、n均为正整数。

一种对称矩阵与向量相乘的并行计算系统，包括：

输入单元，用于获取待计算的对称矩阵和向量，确定全部线程可并行计算的线程数；

区域划分单元，用于以对称轴为界将所述对称矩阵划分为对称轴区域、上三角区域和下三角区域，将上三角区域或下三角区域以行为单位按照线程数分别划分多个子区域；在每个子区域中，划定与所述对称轴平行的第一轴和/或第二轴，所述第一轴上元素的数量等于所述线程数，所述第二轴上元素的数量小于所述线程数；

对称轴计算单元，用于采用全部或部分线程并行计算所述对称轴区域与所述向量的乘积得到第一矩阵，将所述第一矩阵写入第一寄存器、第二寄存器或第三寄存器；

第一轴计算单元，用于在每个子区域中，依序选定一个第一轴作为当前第一轴，采用全部线程对当前第一轴进行两次不同的第一乘法计算，得到两组不同的数据并分别写入第一寄存器和第二寄存器；

第二轴计算单元，用于在每个子区域中，依序选定一个或两个第二轴作为当前第二轴，采用全部或部分线程对当前第二轴进行两次不同的第二乘法计算，得到两组不同的数据并分别写入第一寄存器和第二寄存器，或得到四组不同的数据并分别写入第一寄存器、第二寄存器和第三寄存器；

结果计算单元，用于在完成所述对称轴区域和各个子区域的计算后，基于第一寄存器、第二寄存器和第三寄存器中累加的数据构建矩阵，得到对称矩阵与向量相乘的计算结果。

在一个具体实施例中，在所述第一轴计算单元中，所述第一乘法计算包括：

当前第一轴上的元素a

将a

将a

在一个具体实施例中，在所述第二轴计算单元中，所述第二乘法计算包括：

当选定一个第二轴作为当前第二轴时，当前第二轴上的元素a

将a

将a

当选定两个第二轴作为当前第二轴时，其中一个当前第二轴上的元素a

将a

将a

将a

将a

有益效果：

本发明提供了一种对称矩阵与向量相乘的并行计算方法及其系统，能够准确、快速的实现对称矩阵与向量的乘法计算，通过合理规划矩阵中元素处理的顺序，使各线程合理分配资源，能有效避免写入冲突，实现多线程并行计算，计算效率高，且各线程负载均衡，线程资源分布合理。

附图说明

图1为本发明实施例的并行计算方法流程图；

图2为本发明实施例的矩阵各区域示意图；

图3为本发明实施例的并行计算系统结构示意图。

为了更清楚地说明本发明实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本发明的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。

附图标记：1-输入单元；2-区域划分单元；3-对称轴计算单元；4-第一轴计算单元；5-第二轴计算单元；6-结果计算单元。

具体实施方式

在下文中，将更全面地描述本发明公开的各种实施例。本发明公开可具有各种实施例，并且可在其中做出调整和改变。然而，应理解：不存在将本发明公开的各种实施例限于在此公开的特定实施例的意图，而是应将本发明公开理解为涵盖落入本发明公开的各种实施例的精神和范围内的所有调整、等同物和/或可选方案。

需要说明的是，本发明的针对对称矩阵和向量的乘法运算，必须严格遵守矩阵乘法的规则。对称矩阵是M×N，向量为N×1，M＝N并且满足a

需要说明的是，线程数表示可并行运行的最大线程数量。不同的处理器具有不同的线程数。采用全部线程即表示以线程数的线程并行运行，采用部分线程即表示以小于线程数的线程进行并行计算。线程数同样可以是奇数，也可以是偶数。一般而言，为避免线程资源的浪费，线程数要小于等于阶数。线程数越高，则可并行处理越高阶数的对称矩阵。

需要说明的是，对称矩阵的对称轴即为主对角线，对称轴区域即为对称轴所在的区域，上三角区域即为对称矩阵中对称轴上方的三角形区域，下三角区域即为对称矩阵中对称轴下方的三角形区域。在本申请中，上三角区域和下三角区域均不包括对称轴，对称轴区域与上三角区域、下三角区域是并列关系。

需要说明的是，本申请中某一区域与向量的计算，均是该区域中的元素与向量的计算。例如，并行计算对称轴区域与向量的乘积，即为对称轴区域上各个元素，与向量中对应位置的元素进行乘积。

需要说明的是，本申请中的第一轴、第二轴，均是与对称轴平行的线，是为方便描述矩阵上元素的位置。关于第一轴、第二轴的计算，均是轴上元素的计算。第二轴上可以只有一个元素，也可以有多个元素。

在本发明公开的各种实施例中使用的术语仅用于描述特定实施例的目的并且并非意在限制本发明公开的各种实施例。如在此所使用，单数形式意在也包括复数形式，除非上下文清楚地另有指示。除非另有限定，否则在这里使用的所有术语(包括技术术语和科学术语)具有与本发明公开的各种实施例所属领域普通技术人员通常理解的含义相同的含义。所述术语(诸如在一般使用的词典中限定的术语)将被解释为具有与在相关技术领域中的语境含义相同的含义并且将不被解释为具有理想化的含义或过于正式的含义，除非在本发明公开的各种实施例中被清楚地限定。

实施例1

本发明实施例1公开了一种对称矩阵与向量相乘的并行计算方法，能够避免写入冲突，实现多线程并行计算，且各线程负载均衡，线程资源分布合理。并行计算方法流程图如说明书附图1所示，具体方案如下：

一种对称矩阵与向量相乘的并行计算方法，包括如下步骤：

101、获取待计算的对称矩阵和向量，确定全部线程可并行计算的线程数；

102、以对称轴为界将对称矩阵划分为对称轴区域、上三角区域和下三角区域，将上三角区域或下三角区域以行为单位按照线程数分别划分多个子区域；在每个子区域中，划定与对称轴平行的第一轴和/或第二轴，第一轴上元素的数量等于线程数，第二轴上元素的数量小于线程数；

103、采用全部或部分线程并行计算对称轴区域与向量的乘积得到第一矩阵，将第一矩阵写入第一寄存器、第二寄存器或第三寄存器；

104、在每个子区域中，依序选定一个第一轴作为当前第一轴，采用全部线程对当前第一轴进行两次不同的第一乘法计算，得到两组不同的数据并分别写入第一寄存器和第二寄存器；

105、在每个子区域中，依序选定一个或两个第二轴作为当前第二轴，采用全部或部分线程对当前第二轴进行两次不同的第二乘法计算，得到两组不同的数据并分别写入第一寄存器和第二寄存器，或得到四组不同的数据并分别写入第一寄存器、第二寄存器和第三寄存器；

106、完成对称轴区域和各个子区域的计算后，基于第一寄存器、第二寄存器和第三寄存器中累加的数据构建矩阵，得到对称矩阵与向量相乘的计算结果。

其中，对称轴区域的计算与各个子区域的计算之间并无固定的顺序关系。可先计算完对称轴区域，再计算各个子区域；也可先计算完各个子区域，再计算对称轴区域；也可以在计算各个子区域的过程中，穿插进行对称轴区域的计算。可采用全部或部分线程将对称轴区域进行计算，并将得到的结果写入到第一寄存器、第二寄存器或第三寄存器中。

优选地，本申请的方案针对三阶以上的对称矩阵，且线程数至少为2。当线程数等于1时，即为单线程计算，不适用于本申请的方案。当线程数大于1时，将子区域分为第一子区域和第二子区域，第一子区域的行数等于线程数，第二子区域的行数小于线程数。上三角区域或下三角区域中至少有一个第一子区域。对称矩阵阶数的奇偶性、线程数的奇偶性都会影响子区域、第一轴、第二轴的划定。说明书附图2提供了8×8的矩阵，线程数设定为4，第一子区域如A2所示，第二子区域如A1所示。

矩阵去除对称轴区域，上三角区域和下三角区域在行数上必定相同，且元素关于对称轴对称。因此，只需要处理上三角区域和下三角区域中的一个即可得出另一个。划定子区域时，需要保证至少一个子区域的行数等于线程数。例如，线程数为4，阶数为8，去掉对称轴区域，上三角区域和下三角区域的行数均为7。在上三角区域或下三角区域中划定出一个第一子区域和一个第二子区域，第二子区域位于上三角区域或下三角区域的中数据较少的位置。需要说明的是，数据较少的位置针对的是连续多行的元素数量较少的区域。在图2中，线程数为4，在7行的下三角区域中，可划定一个4行的第一子区域和一个3行的第二子区域，第二子区域A1位于上三行，上三行的数据较少，第一子区域A2位于下三角区域的下三行。

在每个第一子区域中，划定第一轴和第二轴；在每个第二子区域中，划定第二轴。第一轴和第二轴主要是元素数量不同。第一轴和第二轴是以矩阵中元素之间的连线构成的，针对矩阵左下角或右上角的单独一个元素，也可认定为第二轴。第一轴和第二轴如说明书附图2所示。在图2中，c1、c2、c3、c4每条线上的元素都是4个，与线程数相等。因此，c1、c2、c3、c4为第一轴。b1、b2、b3每条线上的元素都小于4个。因此，b1、b2、b为第二轴。

每个第一轴上的元素数量等于线程数，处理器处理第一轴时能够以最大线程运行，当每个线程处理到(非对角元素，即非对称轴上的元素)a

第一乘法计算包括：当前第一轴上的元素a

其中，第二轴分为具备互补关系的第二轴和不具备互补关系的第二轴。互补关系具体表现为：在同一子区域中，存在两个第二轴在元素数量之和上等于线程数。在图2中，c为第一轴，b为第二轴，且b1的元素数量为1，b3的元素数量为3，b1与b3的元素数量之和为4，对应线程数，则b1和b3具有互补关系。

当某一子区域中存在具备互补关系的第二轴时，则依序选定两个具备互补关系的第二轴作为当前第二轴，对当前第二轴分别进行两次乘法计算后，得到四组不同的数据。针对具备互补关系的第二轴，处理器同时对两个第二轴上的元素进行计算，能保证处理器始终以最大线程工作，充分利用线程资源，尽可能减少线程闲置。当处理两个第二轴时，需要修改存储方式，以避免新老线程之间存在写入冲突。

第二乘法计算包括：

当选定一个第二轴作为当前第二轴时，当前第二轴上的元素a

当选定两个第二轴作为当前第二轴时，即这两个第二轴具备互补关系。其中一个当前第二轴上的元素a

将a

将a

将a

将a

设对称矩阵阶数为M，所述线程数为L；当M＝2nL+1时，将上三角区域或下三角区域以行为单位按照线程数分别划分2n个第一子区域；其中，M、L、n均为正整数。此时不存在第二子区域。例如，计算97×97的矩阵，而并发线程(一个warp)数量为32。因此，整个乘法计算分成了三步，分别对应：上32行，中32行和下32行。

以8×8的矩阵为例，处理下三角区域，将下三角区域分成上三行和下四行。以下四行为例。令四个线程分别对应处理四行。但处理顺序是从靠近对称轴的第一轴开始，从右往左处理。预设了一个寄存器r

在第一阶段，处理第一轴上的元素。当每个线程处理到(非对角的)a

其中，-表示重复并被省略的数据(以只处理下三角区域为例)，表示已处理的数据，加粗的数据表示正在处理的数据。

在第二阶段，部分上方的线程触及矩阵左侧，即第一轴处理完毕，开始处理具有互补关系的第二轴。这时，将其切换到左下角，并将它的处理顺序改为从下往上：

在上述矩阵中，原本最上方的线程开始处理a

在第三阶段中，处理不具备互补关系的第二轴。在最后阶段，只剩下半数的斜行数据。简单将修改过的线程关闭，让下方的线程继续处理即可：

完成所有阶段后，所有线程可以同时将自己所持有的寄存器(r

本实施例提供了一种对称矩阵与向量相乘的并行计算方法，能够准确、快速的实现对称矩阵与向量的乘法计算，通过合理规划矩阵中元素处理的顺序，使各线程合理分配资源，能有效避免写入冲突，实现多线程并行计算，计算效率高，且各线程负载均衡，线程资源分布合理。

实施例2

本发明实施例2公开了一种对称矩阵与向量相乘的并行计算系统。在实施例1的基础上，将实施例1的方法系统化，具体结构如说明书附图3所示，具体方案如下：

一种对称矩阵与向量相乘的并行计算系统，包括：

输入单元1，用于获取待计算的对称矩阵和向量，确定全部线程可并行计算的线程数；

区域划分单元2，用于以对称轴为界将对称矩阵划分为对称轴区域、上三角区域和下三角区域，将上三角区域或下三角区域以行为单位按照线程数分别划分多个子区域；在每个子区域中，划定与对称轴平行的第一轴和/或第二轴，第一轴上元素的数量等于线程数，第二轴上元素的数量小于线程数；

对称轴计算单元3，用于采用全部或部分线程并行计算对称轴区域与向量的乘积得到第一矩阵，将第一矩阵写入第一寄存器、第二寄存器或第三寄存器；

第一轴计算单元4，用于在每个子区域中，依序选定一个第一轴作为当前第一轴，采用全部线程对当前第一轴进行两次不同的第一乘法计算，得到两组不同的数据并分别写入第一寄存器和第二寄存器；

第二轴计算单元5，用于在每个子区域中，依序选定一个或两个第二轴作为当前第二轴，采用全部或部分线程对当前第二轴进行两次不同的第二乘法计算，得到两组不同的数据并分别写入第一寄存器和第二寄存器，或得到四组不同的数据并分别写入第一寄存器、第二寄存器和第三寄存器；

结果计算单元6，用于在完成对称轴区域和各个子区域的计算后，基于第一寄存器、第二寄存器和第三寄存器中累加的数据构建矩阵，得到对称矩阵与向量相乘的计算结果。

其中，在第一轴计算单元4中，每个第一轴上的元素数量等于线程数，处理器处理第一轴时能够以最大线程运行，当每个线程处理到(非对角元素，即非对称轴上的元素)a

第一乘法计算包括：

当前第一轴上的元素a

将a

将a

在第二轴计算单元5中，第二轴分为具备互补关系的第二轴和不具备互补关系的第二轴；互补关系具体表现为：在同一子区域中，存在两个第二轴在元素数量之和上等于线程数。在图2中，c为第一轴，b为第二轴，且b1的元素数量为1，b3的元素数量为3，b1与b3的元素数量之和为4，对应线程数，则b1和b3具有互补关系。

当某一子区域中存在具备互补关系的第二轴时，则依序选定两个具备互补关系的第二轴作为当前第二轴，对当前第二轴分别进行两次乘法计算后，得到四组不同的数据。针对具备互补关系的第二轴，处理器同时对两个第二轴上的元素进行计算，能保证处理器始终以最大线程工作，充分利用线程资源，尽可能减少线程闲置。当处理两个第二轴时，需要修改存储方式，以避免新老线程之间存在写入冲突。

第二乘法计算包括：

当选定一个第二轴作为当前第二轴时，当前第二轴上的元素a

将a

将a

当选定两个第二轴作为当前第二轴时，其中一个当前第二轴上的元素a

将a

将a

将a

将a

本实施例提供了一种对称矩阵与向量相乘的并行计算系统，将实施例1的方法系统化，使其更具实用性。

本发明提供了一种对称矩阵与向量相乘的并行计算方法及其系统，能够准确、快速的实现对称矩阵与向量的乘法计算，通过合理规划矩阵中元素处理的顺序，使各线程合理分配资源，能有效避免写入冲突，实现多线程并行计算，计算效率高，且各线程负载均衡，线程资源分布合理。

本领域技术人员可以理解附图只是一个优选实施场景的示意图，附图中的模块或流程并不一定是实施本发明所必须的。本领域技术人员可以理解实施场景中的装置中的模块可以按照实施场景描述进行分布于实施场景的装置中，也可以进行相应变化位于不同于本实施场景的一个或多个装置中。上述实施场景的模块可以合并为一个模块，也可以进一步拆分成多个子模块。上述本发明序号仅仅为了描述，不代表实施场景的优劣。以上公开的仅为本发明的几个具体实施场景，但是，本发明并非局限于此，任何本领域的技术人员能思之的变化都应落入本发明的保护范围。