一种大整数乘法Comba算法基于OpenMP的并行实现方法

摘要

本发明公开了一种大整数乘法Comba算法基于OpenMP的并行实现方法，基于64位无符号长整型整数操作，通过添加三个临时数组存储加乘操作计算得到的中间结果，从而解决加乘运算与进位运算的数据相关性，将加乘操作与进位操作分开执行。在加乘操作阶段，基于中间结果每个数位求取时的计算独立性，通过OpenMP多线程编程采用动态调度策略实现加乘操作阶段的并行化，而进位阶段仍然串行执行来并行化Comba算法，提高算法效率。

主权项

一种大整数乘法Comba算法基于OpenMP的并行实现方法，其特征在于包括如下步骤：(1)申请三个长度为rn的64位无符号长整型数组，分别由指针lpl，hpl，cl指向，即数组lpl[rn]，cl[rn]以及hpl[rn]，其中rn＝un+vn，un和vn可能不等，un和vn分别为乘数和被乘数的位数；(2)循环计算乘积的中间结果，缓存在步骤(1)申请的三个数组中，其中中间结果的每一位根据公式$\left(\mathrm{lpl}\right[\mathrm{ir}],\mathrm{cl}[\mathrm{ir}],\mathrm{hpl}[\mathrm{ir}\left]\right)=\underset{\mathrm{iu}+\mathrm{iv}=\mathrm{ir}}{\Sigma }{\mathrm{up}}_{\mathrm{iu}}*{\mathrm{vp}}_{\mathrm{iv}}(0\le \mathrm{ir}<\mathrm{rn})$计算，lpl[ir]，cl[ir]和hpl[ir]分别存储中间结果第ir位的低64位，中间64位以及高64位，其中up_iu和vp_iv分别表示乘数u的第iu位和被乘数v第iv位；(3)获取程序运行系统目前可用线程数；(4)由步骤(2)所述$\left(\mathrm{lpl}\right[\mathrm{ir}],\mathrm{cl}[\mathrm{ir}],\mathrm{hpl}[\mathrm{ir}\left]\right)=\underset{\mathrm{iu}+\mathrm{iv}=\mathrm{ir}}{\Sigma }{\mathrm{up}}_{\mathrm{iu}}*v{p}_{\mathrm{iv}}(0\le \mathrm{ir}<\mathrm{rn})$的循环计算过程采用OpenMP的for任务分担策略进行并行化，将中间结果的数位计算任务采用动态调度策略分配给可用线程数个计算线程并行计算，并将线程计算所得中间结果对应存储在步骤(1)所申请的数组lpl[rn]，cl[rn]以及hpl[rn]中；(5)对步骤(4)所得lpl[rn]，cl[rn]以及hpl[rn]三个数组中存储的中间结果通过串行进位将最终结果存入rp[rn]数组中，其中rp[rn]为存储最终乘积的数组。