公开(公告)号：CN105653239B

公开(公告)日：2018-06-22

申请号：CN201510996000.6

申请日：2015-12-25

Applicant: 中国科学院软件研究所

Inventor： 蒋丽娟 ,  杜胜 ,  杨超 ,  许永超 ,  刘芳芳 ,  钟伟 ,  赵玉文 ,  申超

IPC: G06F7/53

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

公开(公告)号：CN105653239A

公开(公告)日：2016-06-08

申请号：CN201510996000.6

申请日：2015-12-25

Applicant: 中国科学院软件研究所

Inventor： 蒋丽娟 ,  杜胜 ,  杨超 ,  许永超 ,  刘芳芳 ,  钟伟 ,  赵玉文 ,  申超

IPC: G06F7/53

CPC classification number: G06F7/5324

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