一种大整数乘法Karatsuba算法的并行实现方法

摘要

本发明公开了一种大整数乘法Karatsuba算法的并行实现方法，基于64位无符号长整型整数操作，通过巧妙的公式转换技巧，指针运算以及存储方式，以解决部分积存储与计算的相关性问题，通过OpenMP多线程编程，采用section任务分担策略将算法进行并行化，从而开启8个线程在递归程序的第一层并行求取8个部分积，每个section负责一个部分积的计算任务，待部分积均求取完毕后进行串行归并，从而并行化Karatsuba算法，提高算法效率。

说明书

技术领域

本发明涉及一种大整数乘法Karatsuba算法的并行实现方法，通过开启多个线程并 行计算，提高计算机多核利用率，从而提高算法效率。

背景技术

Karatsuba算法是当大整数数位较小时调用的重要底层大整数快速乘法算法，该算法 应用非常广泛，其通过分治思想以及巧妙的运算技巧以加减运算代替部分乘法运算，降 低了算法计算时间复杂度，然而该运算本身在运行时仍然具有较大空间开销和时间开 销，尤其当数据达到一定规模时，其内存空间和计算时间的消耗将是巨大的。因此提高 Karatsuba算法的性能尤为必要。Karatsuba算法作为重要的大整数底层乘法运算如果能 够提高运行速度，整个计算的运行效率将会大大改善，在实际应用中也有着十分重要的 作用。

伴随着多核处理器和加速部件的普及，通过充分挖掘算法本身的并行度将算法并行 化，高效地提升算法性能，已经成为一种行之有效的方法。目前Karatusba算法优化方 面，TudorJebelean曾在9核paclib计算机中将算法进行3线程和9线程并行，其中基 为2²⁹，与串行算法相比，3线程并行最高可达2.93倍加速，9线程最高可达7.98倍加 速，该并行算法虽然有较好的性能加速，但性能平台依赖性大，数据表示能力受到限制。

Karatsuba算法基于分治思想，将参与运算的乘数与被乘数进行拆分，通过运算技巧 将部分乘法操作转换为加减操作，表述如下：假设乘数u、被乘数v均为2n位，拆分为 两部分后分别为u₁、u₀和v₁、v₀，位数均为n，R为基，则u、v可分别表示成如(1)、(2) 所示：

u＝u₁*Rⁿ+u₀(1)

v＝v₁*Rⁿ+v₀(2)

则由公式(1)和(2)得：

r＝u*v＝u₁*v₁*R²ⁿ+(u₁*v₀+u₀*v₁)Rⁿ+u₀*v₀(3)

由公式(3)可转化为如下公式：

r＝u₁*v₁*R²ⁿ+[u₁*v₁+u₀*v₀-(u₁-u₀)*(v₁-v₀)]Rⁿ+u₀*v₀(4)

基于公式(4)，可将2n位的大整数乘法转换成3个n位的大整数乘法以及若干次加 法和减法运算，减少单精度乘法的次数，而部分积也可采用相似的方法求解，从而提高 算法执行效率。

TudorJebelean所提出的并行化Karatusba算法策略虽然已经达到了很好的效果，但 是其实现时基为2²⁹，数据表达能力受到限制，且受限于机器平台的核数为3或9时性能 达到最优。

发明内容

本发明技术解决问题：克服现有技术的不足，提供一种大整数乘法Karatsuba算法 的并行实现方法，实现基为2⁶⁴，将原始算法乘数与被乘数拆分为两部分改为根据计算资 源拆分为相应数目的数据部分，再通过运算技巧将加减运算代替部分乘法运算以减少乘 法运算次数，同时增加算法的并行度，实现了并行化。

Karatsuba算法基于分治思想，将参与运算的乘数与被乘数的乘积运算拆分成3个部 分积的计算，每个部分积的计算可采用相同的策略递归求取，而部分积的计算具有独立 性。为了充分挖掘Karatusba算法的并行性，本发明基于64位无符号长整型数据操作， 提供一种适用于通用多核平台的并行思路，即将原始算法乘数与被乘数拆分为两部分改 为根据计算资源拆分为相应数目的数据部分，再通过运算技巧将加减运算代替部分乘法 运算以减少乘法运算次数，同时增加算法的并行度，若运行平台核数较多时可通过结合 在递归更深层次进行并行的方式，将算法并行化。基于本实验平台为8核平台，接下来 的并行化方案阐述将基于此8核平台进行阐述。本发明实施实例通过解决部分积存储与 计算的相关性，对Karatsuba递归实现算法采用运算技巧将原有乘数与被乘数的运算修 改为8个部分积的运算，并在递归第一层进行并行，通过存储策略解决其计算时的数据 相关性问题，从而保证此8个部分积计算时的独立性，通过并行编程技术实现此8个部 分积的并行计算，而8个部分积更深层的递归计算仍调用已有串行算法求取，待所有部 分积求取完毕，再对所得的8个部分积的结果进行串行归并。

为方便阐述，设乘数u、被乘数v的位数均为w，基仍设为R，则u、v分别拆分成 三个部分，u拆分成u₀、u₁、u₂，v拆分成v₀、v₁、v₂，其中u₀、u₁、v₀、v₁位数均为n 位，u₂、v₂位数均为s位，n＝w/3，s＝w-2*(w/3)，则u、v分别表示成如公式(7)、 (8)所示：

u＝u₂*R²ⁿ+u₁*Rⁿ+u₀(7)

v＝v₂*R²ⁿ+v₁*Rⁿ+v₀(8)

乘积r进而可表示成如下公式：

r＝u₂*v₂*R⁴ⁿ+[u₁*v₂+u₂*v₁]*R³ⁿ+[u₁*v₁+u₀*v₂+u₂*v₀]*R²ⁿ

+[(u₁+u₀)*(v₁+v₀)-u₁*v₁-u₀*v₀]Rⁿ+u₀*v₀(9)

即转换为8个部分积的计算以及若干次大整数加减运算。KKaratsuba算法基于递归实 现，其核心为部分积的计算，而根据公式(9)可知，部分积在最终乘积rp指向的数组 有位数重叠，例如u₀*v₂、u₂*v₀、u₁*v₁三个部分积在最终结果中位数是重叠的，若将 结果直接存储在乘积rp指向的数组中，进行并行计算则会出现错误。可通过申请额外的 内存空间，存储第一层部分积的计算结果，即u₀*v₀、u₁*v₁、u₂*v₂、(u₁+u₀)*(v₁+v₀)、 u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁，以解决数据相关性问题，从而在递归第一层实现部分 积的并行计算，且在递归计算部分积的第一层时采用OpenMP(OpenMulti-Processing， 一种开源多核并行技术)并行编程实现其并行化，而更深层次的部分积调用已有的串行 程序，待所有层次的部分积均计算完毕，再对第一层已经求得的部分积结果进行串行归 并，从而得到最终结果。

本发明的技术方案包含以下方面：

1)申请长度为N的64位无符号长整型临时数组tmp[N]，数组长度N＝3*w+s+2， 其中w为乘数与被乘数的位数，其不一定被3整除，且s＝w-2*(w/3)；

2)根据公式(9)，在递归第一层，计算部分积u₀*v₀、u₁*v₁、u₂*v₂、(u₁+u₀)*(v₁+v₀)、 u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁，且在求此8个部分积时，仍然调用原始串行递归 Karatsuba算法，且u₀*v₀、u₁*v₁、u₂*v₂的计算结果分别存储在rp指向数组的低2*n， 中2*n位，以及高2*s位，(u₁+u₀)*(v₁+v₀)、u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁的计算结 果由低到高连续存储在步骤1)申请的临时数组的tmp的2*n+2，n+s，n+s，n+s， n+s位，其中rp为指向最终存储乘数与被乘数乘积结果数组的指针，w为乘数与被乘数 的位数，n＝w/3，s＝w-2*(w/3)，数组tmp中存储策略如图2所示；

所述在递归算法第一层计算8个部分积u₀*v₀、u₁*v₁、u₂*v₂、(u₁+u₀)*(v₁+v₀)、 u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁时，采用OpenMP并行编程section并行策略进行并行 化，开启8个计算线程并行计算这8个部分积，每个线程执行一个部分积的计算过程； 3)由步骤2)所述得到的8个部分积分别存储在数组rp以及临时数组tmp中，根据公式 (9)将存储在数组rp以及临时数组tmp中的部分积进行大整数加减归并运算，并将最 终结果存储在数组rp中。

本发明的有益效果：本发明通过巧妙地将乘数与被乘数进行拆分，并通过运算技巧 将计算乘积的公式转化为8个部分积的计算，通过申请临时数组以及相应的存储策略， 解决并行计算时的数据相关性问题，通过8线程并行计算，显著提高算法效率。

与上述TudorJebelean所提出的并行化Karatsuba算法策略相比，本发明在算法第一 层实现8线程并行计算，较好地适应于8核计算平台，且具有较强的数据表达能力。

附图说明

图1为本发明的Karatsuba算法并行策略的示意图；

图2为在计算8个部分积时临时数组tmp的存储策略示意图；

图3为串行Karatsuba算法与本发明并行Karatsuba算法运行结果对比柱状图。

具体实施方式

下面结合附图及具体实施步骤对本发明进行详细说明。

本发明公开一种基为2⁶⁴的大整数乘法Karatsuba算法的并行实现方法，基于64位 无符号长整型整数操作，通过巧妙的公式转换技巧，指针运算以及存储方式，以解决部 分积存储与计算的相关性问题，通过OpenMP多线程编程，采用section任务分担策略 将算法进行并行化，从而开启8个线程在递归程序的第一层并行求取8个部分积，每个 section负责一个部分积的计算任务，待部分积均求取完毕后进行串行归并，从而并行化 Karatsuba算法，提高算法效率。

如图1所示，本发明具体实现如下：

1)申请长度为2*n+2的64位无符号长整型临时数组lowab[2*n+2]，其中令w为乘 数和被乘数的位数，且w不一定整除3，n＝w/3；

2)通过大整数加运算将乘数u低n位与中间n位相加得到u₀+u₁，并存储在步骤1) 申请的临时数组lowab的低n+1位；

3)通过大整数加运算将被乘数v的低n位与中间n位相加得到v₁+v₀，并存储在步骤 1)申请的临时数组的lowab数组的高n+1位；

4)申请长度为N的64位无符号长整型临时数组tmp[N]，数组长度N＝3*w+s+2， 其中w为乘数与被乘数的位数，其不一定被3整除，且s＝w-2*(w/3)；

5)根据公式(9)，在递归第一层，计算部分积u₀*v₀、u₁*v₁、u₂*v₂、(u₁+u₀)*(v₁+v₀)、 u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁，且在求此8个部分积时，仍然调用原始串行递归 Karatsuba算法，且u₀*v₀、u₁*v₁、u₂*v₂的计算结果分别存储在rp指向数组的低2*n， 中2*n位，以及高2*s位，(u₁+u₀)*(v₁+v₀)、u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁的计算结 果由低到高连续存储在步骤4)申请的临时数组的tmp的2*n+2，n+s，n+s，n+s， n+s位，其中数组tmp存储策略如图2所示，参与运算的数据u₀、u₁、u₂分别为乘数u 的低n位，中n位，高s位，v₀、v₁、v₂被乘数v的低n位，中n位，高s位，可通过指针 指向获取，u₀+u₁以及v₁+v₀由步骤1)、2)和步骤3)计算存储在数组lowab中，rp为 指向最终存储乘数与被乘数乘积结果数组的指针，w为乘数与被乘数的位数，n＝w/3， s＝w-2*(w/3)；

6)由步骤5)所述在递归算法第一层计算8个部分积u₀*v₀、u₁*v₁、u₂*v₂、 (u₁+u₀)*(v₁+v₀)、u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁时，采用OpenMP并行编程section 并行策略进行并行化，开启8个计算线程并行计算这8个部分积，每个线程执行一个部 分积的计算过程，且计算结果根据步骤5)所述策略存储；

7)由步骤5)和步骤6)所述得到的8个部分积分别存储在数组rp以及临时数组tmp 中，根据公式(9)将存储在数组rp以及临时数组tmp中的部分积进行大整数加减归并 运算，并将最终结果存储在数组rp中；

测试结果如说明书附图中图3所示，测试平台为8核IntelXeon55系列处理器，CPU 主频为2.67GHz，以C语言为开发语言，IntelC++Compiler11.1为编译器，并基于大整 数运算开源库GMP5.1.3版本进行算法的正确性验证和效率测试，测试时并行Karatsuba 算法为8线程，其中数据规模以64位无符号长整型数据为单位，程序运行时间单位为 微秒，串行Karatsuba算法测试时间为调用大整数开源库GMP中实现库函数的运行时间。

本发明测试选取了10组大整数进行实验，每组数据为几百到上万数据单位的两个 整数，为了使得实验具有一般性，所有数据均是由程序随机产生。

实验中使用本发明中提出的并行执行程序与串行Karatsuba算法在Intel的X86平台 上进行实验和性能对比。

从图3中可以看出，本发明选取的10组大整数进行实验得到的加速性能图，不同 数据规模下并行Karatsuba算法与串行Karatsuba算法的性能加速有所不同，其并行 Karatsuba算法与串行Karatsuba算法的加速比平均可达到5.12，性能提升了很多。

提供以上实施例子仅仅是为了描述本发明的目的，而并非要限制本发明的范围。本 发明的范围由所附权利要求限定。不脱离本发明的精神和原理而做出的各种等同替换和 修改，均应涵盖在本发明的范围之内。

提供以上实施例仅仅是为了描述本发明的目的，而并非要限制本发明的范围。本发 明的范围由所附权利要求限定。不脱离本发明的精神和原理而做出的各种等同替换和修 改，均应涵盖在本发明的范围之内。