面向众核处理器的大整数乘法研究
发布时间：2021-03-19 21:45
算数运算一直是人类科学发展过程中非常重要的研究领域,很多科学问题的解决依赖于准确、快速的算术运算。在计算机上,算数运算是实现各种应用的基础,尤其大整数的乘法运算在密码算法、科学计算中有着广泛的应用。目前,计算机体系结构开始向多核、众核结构发展,众核处理器已经开始在高性能计算等领域普遍使用。研究如何在众核处理器上高效实现大整数乘法,对发挥现代众核处理器性能优势,求解更大规模问题具有重要意义。基于计算机体系结构的发展变化,以及现实应用中对高效大整数乘法需求不断的提升,本文对众核处理上的大整数乘法进行了研究,主要工作和创新有:（1）对笔算乘法和Comba乘法等基本乘法算法的并行性进行研究,并提出多种实现高效并行Comba乘法的改进方法,以及给出了在SW26010众核处理器实现并行Comba乘法的具体方法。（2）对Karatsuba乘法等分治类乘法的并行性进行研究,并提出面向众核处理器的Karatsuba乘法的改进方法,以及研究了在SW26010众核处理器实现并行Karatsuba乘法的方法。（3）对FFT乘法进行分析与研究,提出在SW26010众核处理器实现高效并行FFT乘法的方法,实现过程...
【文章来源】：郑州大学河南省 211工程院校
【文章页数】：71 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
1 引言
1.1 课题背景
1.2 研究意义
1.3 论文主要工作
1.4 论文结构
2 研究基础
2.1 基本概念
2.2 数学基础
2.2.1 多项式表示
2.2.2 多项式乘法
2.3 大整数乘法
2.3.1 基本乘法
2.3.2 分治乘法
2.3.3 FFT乘法
2.4 大整数运算库
2.5 SW26010众核处理器
2.6 本章小结
3 Comba乘法的改进及众核并行化
3.1 基本乘法分析
3.1.1 笔算乘法分析
3.1.2 Comba乘法分析
3.2 Comba乘法改进
3.2.1 任务划分策略
3.2.2 改进的Comba算法
3.3 并行Comba算法在SW众核处理器上的实现
3.4 本章小结
4 Karatsuba乘法的改进及众核并行化
4.1 分治乘法
4.1.1 Karatsuba乘法
4.1.2 Toom-Cook乘法
4.2 Karatsuba乘法分析
4.3 Karatsuba乘法的改进
4.4 改进Karatsuba乘法的并行实现
4.5 本章小结
5 FFT乘法的众核并行化
5.1 快速傅里叶变换
5.2 FFT乘法原理
5.3 FFT乘法的众核并行化实现
5.3.1 FFT乘法众核并行化实现思路
5.3.2 复数运算的向量化
5.3.3 寄存器通信
5.4 本章小结
6 大整数乘法系统构造及测试
6.1 乘法算法测试与分析
6.2 面向SW26010的大整数乘法系统
6.3 本章小结
7 结论
7.1 工作总结
7.2 展望与计划
参考文献
个人简历及发表论文情况
致谢
【参考文献】：
期刊论文
[1]基于Intel MIC架构的3D有限差分算法优化[J]. 郝鑫,郭绍忠. 计算机科学. 2017(05)
[2]以深度学习为目标,NVIDIA发布首款Volta架构GPU[J]. 寒意. 华东科技. 2017(05)
[3]大整数Comba和Karatsuba乘法的多核并行化研究[J]. 蒋丽娟,刘芳芳,赵玉文,杨超,蔡颖. 计算机系统应用. 2016(11)
[4]高性能计算的发展[J]. 臧大伟,曹政,孙凝晖. 科技导报. 2016(14)
[5]The Sunway Taihu Light supercomputer:system and applications[J]. Haohuan FU,Junfeng LIAO,Jinzhe YANG,Lanning WANG,Zhenya SONG,Xiaomeng HUANG,Chao YANG,Wei XUE,Fangfang LIU,Fangli QIAO,Wei ZHAO,Xunqiang YIN,Chaofeng HOU,Chenglong ZHANG,Wei GE,Jian ZHANG,Yangang WANG,Chunbo ZHOU,Guangwen YANG. Science China（Information Sciences）. 2016(07)
[6]一种面向高性能计算的自主众核处理器结构[J]. 郑方,许勇,李宏亮,谢向辉,陈左宁. 中国科学:信息科学. 2015(04)
[7]SIMD自动向量化编译优化概述[J]. 高伟,赵荣彩,韩林,庞建民,丁锐. 软件学报. 2015(06)
[8]基于CUDA的快速大整数乘法[J]. 许亮,王震. 计算机工程与应用. 2013(16)
[9]PPAT:一种Pthread并行程序线程性能分析工具[J]. 温莎莎,刘轶,刘弢宋,平李,博钱,德沛. 计算机应用与软件. 2012(11)
[10]一种改进的二分查找算法[J]. 邹国霞,何南. 软件导刊. 2010(03)
硕士论文
[1]基于MIC加速部件的长整数基础计算[D]. 赵明祥.华南理工大学 2016
[2]基于MPI和Linux机群环境的FFT算法的并行设计与实现[D]. 卢可佩.曲阜师范大学 2015
[3]基于ElGamal算法的多级匿名通信系统[D]. 许尚妹.西安电子科技大学 2014
[4]基于多核多线程的FFT算法和堆排序算法的并行优化和实现[D]. 徐金棒.郑州大学 2011
[5]公钥密码体制中强素数生成算法与大数乘法的研究[D]. 蔡刚.中南民族大学 2009
[6]RSA公钥密码算法的快速实现[D]. 王安.山东大学 2008
本文编号：3090278
【文章来源】：郑州大学河南省 211工程院校
【文章页数】：71 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
1 引言
1.1 课题背景
1.2 研究意义
1.3 论文主要工作
1.4 论文结构
2 研究基础
2.1 基本概念
2.2 数学基础
2.2.1 多项式表示
2.2.2 多项式乘法
2.3 大整数乘法
2.3.1 基本乘法
2.3.2 分治乘法
2.3.3 FFT乘法
2.4 大整数运算库
2.5 SW26010众核处理器
2.6 本章小结
3 Comba乘法的改进及众核并行化
3.1 基本乘法分析
3.1.1 笔算乘法分析
3.1.2 Comba乘法分析
3.2 Comba乘法改进
3.2.1 任务划分策略
3.2.2 改进的Comba算法
3.3 并行Comba算法在SW众核处理器上的实现
3.4 本章小结
4 Karatsuba乘法的改进及众核并行化
4.1 分治乘法
4.1.1 Karatsuba乘法
4.1.2 Toom-Cook乘法
4.2 Karatsuba乘法分析
4.3 Karatsuba乘法的改进
4.4 改进Karatsuba乘法的并行实现
4.5 本章小结
5 FFT乘法的众核并行化
5.1 快速傅里叶变换
5.2 FFT乘法原理
5.3 FFT乘法的众核并行化实现
5.3.1 FFT乘法众核并行化实现思路
5.3.2 复数运算的向量化
5.3.3 寄存器通信
5.4 本章小结
6 大整数乘法系统构造及测试
6.1 乘法算法测试与分析
6.2 面向SW26010的大整数乘法系统
6.3 本章小结
7 结论
7.1 工作总结
7.2 展望与计划
参考文献
个人简历及发表论文情况
致谢
【参考文献】：
期刊论文
[1]基于Intel MIC架构的3D有限差分算法优化[J]. 郝鑫,郭绍忠. 计算机科学. 2017(05)
[2]以深度学习为目标,NVIDIA发布首款Volta架构GPU[J]. 寒意. 华东科技. 2017(05)
[3]大整数Comba和Karatsuba乘法的多核并行化研究[J]. 蒋丽娟,刘芳芳,赵玉文,杨超,蔡颖. 计算机系统应用. 2016(11)
[4]高性能计算的发展[J]. 臧大伟,曹政,孙凝晖. 科技导报. 2016(14)
[5]The Sunway Taihu Light supercomputer:system and applications[J]. Haohuan FU,Junfeng LIAO,Jinzhe YANG,Lanning WANG,Zhenya SONG,Xiaomeng HUANG,Chao YANG,Wei XUE,Fangfang LIU,Fangli QIAO,Wei ZHAO,Xunqiang YIN,Chaofeng HOU,Chenglong ZHANG,Wei GE,Jian ZHANG,Yangang WANG,Chunbo ZHOU,Guangwen YANG. Science China（Information Sciences）. 2016(07)
[6]一种面向高性能计算的自主众核处理器结构[J]. 郑方,许勇,李宏亮,谢向辉,陈左宁. 中国科学:信息科学. 2015(04)
[7]SIMD自动向量化编译优化概述[J]. 高伟,赵荣彩,韩林,庞建民,丁锐. 软件学报. 2015(06)
[8]基于CUDA的快速大整数乘法[J]. 许亮,王震. 计算机工程与应用. 2013(16)
[9]PPAT:一种Pthread并行程序线程性能分析工具[J]. 温莎莎,刘轶,刘弢宋,平李,博钱,德沛. 计算机应用与软件. 2012(11)
[10]一种改进的二分查找算法[J]. 邹国霞,何南. 软件导刊. 2010(03)
硕士论文
[1]基于MIC加速部件的长整数基础计算[D]. 赵明祥.华南理工大学 2016
[2]基于MPI和Linux机群环境的FFT算法的并行设计与实现[D]. 卢可佩.曲阜师范大学 2015
[3]基于ElGamal算法的多级匿名通信系统[D]. 许尚妹.西安电子科技大学 2014
[4]基于多核多线程的FFT算法和堆排序算法的并行优化和实现[D]. 徐金棒.郑州大学 2011
[5]公钥密码体制中强素数生成算法与大数乘法的研究[D]. 蔡刚.中南民族大学 2009
[6]RSA公钥密码算法的快速实现[D]. 王安.山东大学 2008
本文编号：3090278
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3090278.html
