摘要:基于数论转换的Schönhage-Strassen算法（简称SSA）是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析，然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案，并在Intel X86平台进行了验证和测试.经测试，8线程时的最大加速比可达到6.59，平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试，实验结果表明：SSA算法并行方案具有良好的扩展性，最大加速比可达21.42.
Abstract:Schönhage-Strassen algorithm (SSA) based on the number-theoretic transform is one of the faster large integer multiplication algorithms widely used in the practical applications at present. Firstly in this paper, the principle of the SSA algorithm is introduced in detail. Then, parallel optimization is applied to SSA algorithm from a fine-grained perspective in the multi-core platform. The parallel SSA algorithm is implemented based on the open source library of large integer arithmetic algorithm GMP, and its correctness and performance is validated in the Intel X86 platform. The maximum speedup can reach 6.59 and the average speedup is 6.41 by 8 threads. The scalability of the parallel SSA algorithm is tested on the Inspur TS850, and experimental results show that it has good scalability and the maximum speedup can reach 21.42.
PDF全文下载地址:
http://jos.org.cn/jos/article/pdf/5308
删除或更新信息，请邮件至freekaoyan#163.com(#换成@)
大整数乘法Schönhage-Strassen算法的多核并行化研究
本站小编 Free考研考试/2022-01-02
相关话题/方案 测试 优化 实验 算法
领限时大额优惠券,享本站正版考研考试资料!
优惠券领取后72小时内有效，10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材，产品类型包含电子书、题库、全套资料以及视频，无论您是考研复习、考证刷题，还是考前冲刺等，不同类型的产品可满足您学习上的不同需求。 ...考试优惠券 本站小编 Free壹佰分学习网 2022-09-19覆盖表生成的禁忌搜索算法
摘要:组合测试可以有效检测待测系统中由参数间交互作用而引发的故障.在其30多年的发展过程中，覆盖表生成一直是关键问题之一，相关研究文献已达200多篇.作为一种有效的覆盖表生成算法，已有的禁忌搜索算法在所生成的覆盖表规模上具备一定的优势，但其解的质量和运算速度仍有提升空间；同时，这些算法实际应用能力较 ...中科院软件研究所 本站小编 Free考研考试 2022-01-02基于切空间判别学习的流形降维算法
摘要:在基于图像集的流形降维问题中，许多算法的核心思想都是把一个高维的流形直接降到一个维数相对较低、同时具有的判别信息更加充分的流形上.投影度量学习（projectionmetriclearning，简称PML）是一种Grassmann流形降维算法.该算法是基于投影度量，并且使用RCG（Rieman ...中科院软件研究所 本站小编 Free考研考试 2022-01-02基于随机kNN图的批量边删除聚类算法
摘要:建立邻接图上的批量边删除聚类算法通用框架，提出基于高斯平滑模型的批量边删除判定准则，定义了适于聚类的邻接图的一般性质，提出并证明在kNN图基础上引入随机因子构造的随机kNN图，可以增强顶点之间的局部连通性，使聚类结果不再强烈依赖于某条边或某些边的保留或删除.RkNNClus算法简洁高效，依赖参 ...中科院软件研究所 本站小编 Free考研考试 2022-01-02一种带稀疏间隙约束的并行模式匹配算法
摘要:带通配符的模式匹配是一个经典的研究问题，带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域，提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法SGPM-SAI（patternmatchingwithsparsegapsconstraintbasedon ...中科院软件研究所 本站小编 Free考研考试 2022-01-02一种保序加密域数据库认证水印算法
摘要:加密域水印技术适用于云环境下的隐私保护（加密）和数据安全认证（加水印）.通过结合保序加密、离散余弦变换、密码哈希和数字水印技术，提出了加密域数据库认证水印算法.首先对数据进行保序加密，以达到对敏感数据内容的隐私保护；对加密后的数据进行分组和离散余弦变换处理，然后将交流系数的哈希（Hashing ...中科院软件研究所 本站小编 Free考研考试 2022-01-02面向国产申威26010众核处理器的SpMV实现与优化
摘要:世界首台峰值性能超过100P的超级计算机——神威太湖之光已经研制完成，该超级计算机采用了国产申威异构众核处理器，该处理器不同于现有的纯CPU，CPU-MIC，CPU-GPU架构，采用了主-从核架构，单处理器峰值计算能力为3TFlops/s，访存带宽为130GB/s.稀疏矩阵向量乘SpMV（sp ...中科院软件研究所 本站小编 Free考研考试 2022-01-02LFA算法的一种高效实现方法
摘要:研究表明，网络中的故障不可避免而且频繁出现.当故障发生时，目前互联网部署的域内路由协议需要经历收敛过程.在此过程中，路由信息可能不一致，从而导致报文丢失，降低了路由可用性.因此，业界提出了利用LFA（loopfreealternates）应对网络中发生的单故障情形，从而提高路由可用性.然而，已 ...中科院软件研究所 本站小编 Free考研考试 2022-01-02基于行为特征的语义工作流修正算法
摘要:工作流修正是工作流重用的重要任务.目前，在基于工作流的可重用片段——stream的语义工作流修正中，当工作流stream库中不存在与检索语义工作流中的工作流stream结构相似的stream时，无法修正检索语义工作流.针对这种情况，提出了一种改进方法——基于stream行为特征的语义工作流修正 ...中科院软件研究所 本站小编 Free考研考试 2022-01-02基于优化主题模型的临床路径挖掘
摘要:在健康领域，诊疗过程对于医疗质量至关重要.临床路径集合了各种医疗知识，是对诊疗过程进行标准化的重要途径.然而，当前大多数临床路径由专家研讨制定，往往静态不变，难以部署和实施.在之前的工作中，提出了一种基于主题的临床路径挖掘算法，可以从医疗数据中抽取历史执行路径，客观反映数据中实际存在的医疗模式 ...中科院软件研究所 本站小编 Free考研考试 2022-01-02云环境下基于多目标的多科学工作流调度算法
摘要:针对现有云环境下的多科学工作流调度算法中存在的未考虑安全调度问题，提出了多科学工作流安全-时间约束费用优化算法MSW-SDCOA（multi-scientificworkflowssecurity-deadlineconstraintcostoptimizationalgorithm）.首先， ...中科院软件研究所 本站小编 Free考研考试 2022-01-02
