一种基于GMP的大整数加法和减法多核并行化实现方法

摘要

本发明涉及一种基于GMP的大整数加法和减法多核并行化实现方法，首先借助于临时数组来解决加法或减法操作产生的进位或借位带来的数据相关性问题，然后采用将迭代循环for中的运算进行任务划分，基于OpenMP多线程编程实现，使用动态调度策略，多线程并行求取各区域的计算任务的策略解决负载不均衡问题。本发明能借助多核平台，通过充分利用多核条件提高运行速度，在实际应用中有着十分重要的作用。

主权项

一种基于GMP的大整数加法和减法多核并行化实现方法，其特征在于实现步骤如下：(1)获取程序运行系统目前可用线程数；(2)根据步骤(1)中得到的可用线程数分配和初始化用于存储区域进位的临时数组，其元素个数为N；(3)根据步骤(1)中得到的可用线程数将需要进行按位逐位相加操作的任务进行区域划分，区域中的区域任务的个数与临时数组的个数一一对应，大于等于可用线程数；(4)基于OpenMP(共享存储并行编程)多线程编程技术，使用动态调度策略，多线程并行求取各区域的计算任务，率先执行完任务的线程接着从由区域任务形成的任务池中领取一个区域任务，各线程在求取区域任务时需判断当前区域任务是不是最后一个区域任务，如果是最后一个区域任务需要根据具体情况调用串行加法算法，否则可以直接调用串行加法算法计算当前区域任务，然后将最后的进位值保存到步骤(2)临时数组中相应的元素中，将结果存储在结果的相应位置；(5)对步骤(4)中已更新的临时数组中每个区域的进位结果进行统一操作；具体过程：遍历临时数组中除临时数组N‑1的每一个值，如果进位值为零，则继续遍历下一个，如果值为非零，则对步骤(4)得到的结果中从下一个区域结果开始到结果的最高位的整个区域进行加1操作，且当加1过程中新的临时进位不为1时，跳出此次遍历过程；遍历完除临时数组N‑1的每一个值后更新最高位的进位情况。