大整数Comba和Karatsuba乘法的多核并行化研究

大整数运算广泛地应用于公钥加密算法、大规模科学计算中高精度浮点数运算类以及构建大特征值等领域,然而其大部分算法空间和时间开销都很大,尤其对于核心运算之一的大整数乘法,当数据达到一定规模时,超长的串行计算时间已成为制约算法应用的巨大瓶颈.近几年来,伴随着多核、众核芯片的迅猛发展,通过充分挖掘算法本身的并行度以利用并行处理器的强大计算能力,进而高效地提升算法性能,成为一种研究趋势.本文基于通用多核并行计算平台,研究了大整数乘法Comba及Karatsuba快速算法的并行化,提出了高效的多核并行算法.在算法实现及性能优化上,采用了OpenMP+SIMD的多级并行技术,使性能获得巨大提升.在性能测试上,我们使用优化的并行算法与原始串行算法进行对比试验,结果显示,8线程并行Comba算法和Karatsuba算法相比串行对应算法分别实现了5.85倍以及6.14倍的性能加速比提升.     

基于CUDA的快速大整数乘法

针对快速傅里叶变换下的快速大整数乘法,给出了一种基于CUDA架构的GPU并行化加速的实现方法。通过分析整数快速乘法中的每一步骤,分别给出各步骤的并行化实现方法,并采用数据压缩等策略,对算法进行优化。实验表明该方法有效地提高了算法效率,随着数据规模的增长,可获得18倍以上的加速比。     

一种新的大整数乘法算法

为解决超出计算机系统基本整数类型表达能力的整数(大整数)算术运算问题,以基础算法--大整数乘法为研究对象,根据大整数的表示形式与多项式表示形式上的相似性,结合大整数乘法进位与取模的特点,给出了一种关于大整数乘法的多项式算法.其方法与别的方法最大的不同是,虽然是求两个大整数乘法,但整个算法没有使用乘法,只是用加法运算而已...     

数据全并行FFT处理器的设计

讨论了基4和混和基算法的FFT处理器设计问题,提出的操作数地址映射方法充分利用了FFT算法本身的同址性质,能同时提供蝶形运算所需的4个操作数,具有最大的数据并行性,按照旋转因子存放规则,蝶形运算所需的3个旋转因子地址相同,且寻址方式简单,运算部件采用3个乘法的复数运算算法,有效减少了运算部件的大小,它既可以作基4蝶形运算,也可以同时进行2个基2蝶形运算．采用Altera公司的EP200K400E,工作频率达到89MHz,1024点16位复数FFT需要14．1μs,4096点需要67μs。     

SIMD-LA模型上的大整数乘法

本文提出了一种基于SIMD-LA模型的大整数乘法的算法,将分治策略与Karatsuba-Offman算法相结合改进了已有的算法.当使用p台处理器,大整数长度n＜=256p时,其时间复杂度为O(p);大整数长度n＞256p时,其时间复杂度为O(p[n]1.58/|p|+p).其时间复杂度比传统算法有了进一步的提高.     

对大整数乘法求解问题改进算法的思考

通过对大整数乘法的研究可知,在求解此类问题时可以使用分治法加以解决。但究竟将一个大整数分为几段做乘法可以得到最优的情况,则是本章讨论并研究的问题。特此,在教学的实践过程中,通过进一步的分析,撰写出如下的比较过程。     

基于多项式的大整数相乘算法

为解决超出计算机系统基本整数类型表达能力的整数(大整数)计算问题,以基础算法--大整数乘法为研究对象,根据大整数的表示形式与多项式表示形式上的一致性,结合大整数乘法进位与取模的特点,给出了一种关于大整数乘法的多项式算法.与现有的大整数位乘法进行了比较,证明该算法将大数相乘问题的复杂度降低到位乘法的1/3,并通过程序验证了该算法的性能,其结果与对于它们时间复杂度的分析基本一致.     

基于多核的Rijndael算法的并行优化与实现

为提高Rijndael算法的执行效率,从对Rijndael算法的核心部分-轮变换的分析入手,在多核平台下提出了一种基于数据流分解的方式对Rijndael算法进行并行优化.采用的主要方法是将轮变换的各构成变换对整个状态的作用分割成对状态的每个组成单元的作用,使得各构成变换可以并行进行.实验结果表明,采用基于数据流的分解方式对Rijndael算法分解可有效的提高其执行效率.     

基于TBB的谐波分析多核并行化研究

电能质量谐波分析中通常使用快速傅立叶变换算法(FFT),但在大数据量时其循环体执行效率低,实时性不高。针对上述问题,提出在多核处理器上采用TBB(Intel线程构建模块)并行实现复序列FFT的思路,提高谐波分析的速度,增强实时性。此外,与其他并行库改造程序的实验对比结果表明,TBB可以以更简单的手段,实现更高效的程序并行。     

面向众核结构的并行Comba乘法研究

为发挥众核处理器性能优势及求解更大规模问题,针对大整数乘法在众核处理器上的并行化进行研究。在对笔算乘法和Comba乘法并行性进行分析的基础上,针对Comba乘法并行化时面临的负载均衡问题提出了多种解决方法;然后针对SW26010的结构特征,选择借鉴笔算乘法改进的Comba乘法,并且实现过程使用了向量化、寄存器通信等优化方法。测试结果说明改进后的并行Comba算法具有较好的并行性,能够很好地利用SW26010众核处理器的性能优势。     

改进的大整数相乘快速算法

利用分治法思想,提出一种大整数相乘快速算法,减少乘法运算次数,使2个数相乘的计算复杂度从O(n)降低到O(1)。根据不同的加法思路,提出累加求和及统一求和2种改进算法,给出2种改进算法的形式化描述,并通过实验给出改进算法和现有的典型大整数位相乘算法的时间比较。研究结果表明,该算法能够提高密码算法和信息安全协议的运算效率。     

快速傅里叶变换乘法的性能研究

大数相乘是密码学的一种关键运算,其性能影响许多密码算法,如RSA、ElGamal等公钥密码运算的性能。对常见的大数乘法算法进行了实验、分析和比较,特别针对快速傅里叶变换（Fast Fourier Transform,FFT）算法,分析了其在大数乘法中的应用,并与其他常见大数算法的效率进行了比较,归纳了快速傅里叶变换的优势范围与劣势范围。同时,由于快速傅里叶变换计算过程中有误差,当数据位足够多时,可能导致计算结果不正确,因此进一步分析了傅里叶快速变换计算正确的数据位上限,这些工作对于快速乘法算法的正确选择有重要的实际意义。     

大型直线稀疏阵列的迭代FFT算法优化

提出了一种基于迭代FFT算法的大型直线稀疏阵列(可放置阵元的栅格数为1 000)的旁瓣电平优化方法,并给出了详细的优化步骤。在给定的旁瓣约束条件下,利用阵列因子与阵元激励之间存在的傅里叶变换关系,对不同的初始随机阵元激励分别进行迭代循环来降低稀疏阵列的旁瓣电平。在迭代过程中,根据稀疏率将阵元激励按幅度大小置1置0来完成阵列稀疏。仿真实验证明了该方法的高效性和稳健性。     

基于混合卷积窗和双窗法的FFT算法研究

FFT算法是信号处理中一个不可或缺的部分,也是其中需要改进的部分.设计一个精度优良的FFT算法有助于推进频谱分析的实用化进程.针对FFT改进算法的实现需求,文章采用了C语言结构设计了一个任意点数的FFT算法,分析了混合卷积窗的频谱特性,并总结了任意窗函数的幅值恢复方法.最终通过构建混合卷积窗和双窗法结合的处理方法有效提...     

改进相位差测量在感应加热电源频率跟踪中的应用

在感应加热电源的频率跟踪环节中,需要对负载电压和电流信号相位差进行测量.由于待测负载信号存在波形畸变,使得常用的过零比较法在实现时存在一定误差.为了解决这一问题,提出一种改进的相位差测量方法.利用dsPIC的输入捕捉模块测量负载信号的周期,配合快速傅里叶变换得到负载电压和电流信号相位差,然后对测得的相位差进行修正和补偿,最终实现系统频率跟踪功能.实验结果表明,该方法可以使逆变电路输出较为准确地跟踪负载固有谐振频率的变化,提高了系统的工作性能,较好地达到系统频率跟踪的要求,在实际设计中有一定的应用价值.     

基于快速傅里叶变换和选择性卷积核网络的图像补全

较传统方案而言, 目前基于深度学习的图像补全方法取得了更优的修复效果. 但大都忽视了建立像素的长距离依赖, 深度学习模型处理大面积不规则缺失时效果不佳、生成图像整体契合度不足. 另一方面, 很多通过融合多尺度感受野来保留更多细节信息的补全算法, 由于无法动态的调节感受野, 而受到输入尺度与补全目标尺度变化带来的影响, 最终导致生成结果产生明显的伪影误差. 针对这类问题, 本文提出一种基于快速傅里叶变换和选择性卷积核网络的补全算法, 在实现像素长距离依赖的同时保证模型的高效率运行. 此外, 本算法还改进了选择性卷积核网络, 可按照各卷积核特征的贡献, 自适应调整相应权重, 从而为模型提供精确的局部性信息补充, 最终生成全局融合度更高、局部细节更丰富的补全结果. 在Celeb-A和Place2数据集的实验表明, 本文方法不仅在PSNR和SSIM指标上超越了现有的前沿图像补全方法, 且处理受遮挡率为80%以上的图像时具有明显优势, 能够生成更真实地结果.     

基于PSO和外部知识的时序数据异常检测

在时间序列数据的异常检测中, 单一模型往往只提取与自身模型结构相关的时序特征, 从而容易忽略其他特征. 同时, 面对大规模的时序数据, 模型难以对时序数据的局部趋势进行建模. 为了解决这两个问题, 本文提出一种基于粒子群优化算法(particle swarm optimization, PSO)和外部知识的异常检测模型PEAD. PEAD模型以深度学习模型作为基模型, 引入快速傅里叶变换生成的外部知识来提高基模型对局部趋势的建模能力, 随后PEAD模型以Stacking集成学习的方式训练基模型, 再使用PSO算法对基模型的输出加权求和, 对加权求和后的重构数据进行异常检测, PSO算法能够让模型的最终输出共同关注时序数据的全局特征和时间特征, 丰富模型提取的时序特征, 从而提高模型的异常检测能力. 通过对6个公开数据集进行测试, 研究结果表明PEAD模型在大部分数据集上表现良好.