解非对称矩阵特征值问题的并行NSM-APA算法

在矩阵特征值分布理论和APA算法的基础上,给出了一种求非对称实矩阵特征值问题的并行NSM-APA算法,理论分析和在PVM下的数值结果表明,该算法比基于矩阵特征值分布理论的二分法收敛快,而且有较高的加速比.

基于Spark和NRSCA策略的并行深度森林算法

针对并行深度森林在大数据环境下存在冗余及无关特征过多、两端特征利用率过低、模型收敛速度慢以及级联森林并行效率低等问题,提出了基于Spark和NRSCA策略的并行深度森林算法——PDF-SNRSCA。首先,该算法提出了基于邻域粗糙集和Fisher score的特征选择策略(FS-NRS),通过衡量特征的相关性和冗余度,对特征进行过滤,有效减少了冗余及无关特征的数量;其次,提出了一种随机选择和等距提取的扫描策略(S-RSEE),保证了所有特征能够同概率被利用,解决了多粒度扫描两端特征利用率低的问题;最后,结合Spark框架,实现级联森林并行化训练,提出了基于重要性指数的特征筛选机制(FFM-II),筛选出非关键性特征,平衡增强类向量与原始类向量维度,从而加快模型收敛速度,同时设计了基于SCA的任务调度机制(TSM-SCA),将任务重新分配,保证集群负载均衡,解决了级联森林并行效率低的问题。实验表明,PDF-SNRSCA算法能有效提高深度森林的分类效果,且对深度森林并行化训练的效率也有大幅提升。

多核数字信号处理卷积算法并行优化

针对国防科技大学自主研发的异构多核数字信号处理(digital signal processing, DSP)芯片的特征以及卷积算法自身特点,提出了一种面向多核DSP架构的高性能多核并行卷积实现方案。针对1×1卷积提出了特征图级多核并行方案;针对卷积核大于1的卷积提出了窗口级多核并行优化设计,同时提出了逐元素向量化计算的核内并行优化实现。实验结果表明,所提并行优化方法实现单核计算效率最高能达到64.95%,在带宽受限情况下,多核并行扩展效率可达到48.36%~88.52%,在典型网络ResNet50上的执行性能与E5-2640 CPU相比,获得了5.39倍性能加速。

用于太赫兹通信的双向全并行相位估计算法

在太赫兹通信的超宽带应用场景下,太赫兹载波是通过多次倍频实现,因而导致相噪严重恶化。基于太赫兹频率下的多极/零相位噪声模型,在传统的盲相位估计算法的基础上,提出了一种全并行化的相位估计算法。该算法通过在每个并行数据中插入导频,将导频相噪信息作为初始相位对并行数据进行相位扩展及旋转鉴相。借鉴传统盲相位估计算法的最佳相位估计值的判决选择思路,同时利用前一时刻导频和当前时刻导频,对当前并行数据从前后两个方向进行相位估计并对前后两个估计相位基于距离前后导频的位置进行加权求和以获得最佳相位估计信息。经过仿真验证,通过该算法后残余相噪在1 MHz和10 MHz处分别降低10 dBc/Hz和25 dBc/Hz。

基于混合人工蜂群算法的并行测试任务优化研究

并行测试技术可以同时进行多个任务的测试,提高资源利用率,节约测试成本;并行测试调度问题是一种复杂的组合优化问题,是并行测试技术的核心要素;并行测试系统作为并行测试技术的载体,自身的性能和求解效率尤其重要;文章对并行测试完成时间极限定理进行了研究,建立了并行测试任务调度的数学模型,分析了传统元启发式算法求解并行测试问题的不足,提出了基于动态规划的递归搜索技术和人工蜂群算法相结合的混合人工蜂群算法,并采用整数规划精确算法和遗传算法对混合人工蜂群算法进行验证;得出结论采用混合人工蜂群算法进行并行测试任务的调度节约了接近50%的时间,降低了约20%的硬件资源占用,提高了测试效率,可以满足工程实际的应用。

北斗卫星船载导航信号并行捕获算法

信号捕获作为实现北斗卫星船载导航的第一阶段,也是最重要的一环,为此研究基于北斗卫星船载导航信号并行捕获算法,在短时间内捕获卫星信号,为船舶提供高精度的定位和导航服务。建立北斗卫星导航信号模型,依据模型生成的北斗卫星导航信号,采用傅里叶变换(Fast Fourier Transformation,FFT)算法以及快速傅里叶逆变换(Inverse Fast Fourier Transform,IFFT)算法,通过并行频率搜索和并行码相位搜索分别将伪随机码相位、载波频移的二维搜索变成一维进行并行搜索,获取北斗卫星信号的伪随机码和载波频移,实现北斗卫星船载导航信号并行捕获。实验结果表明,该算法可以成功地捕获船载导航信号,并且捕获耗时短;对船载导航信号的载波频率估计误差小。

任务并行编程模型下排列熵算法的并行实现

排列熵算法随着嵌入维数的增大,运算规模将会呈平方级数增大,计算时效性问题突出,亟待解决。为此,提出一种基于任务并行编程模型的线程级并行方法,通过任务并行运行系统(StarPU)将密集型计算划分为多个独立的任务,再由调度器将任务调度到不同的CPU上执行,实现排列熵算法的并行化。基于StarPU的排列熵并行算法与串行程序相比较,加速比为23.79倍,相较于OpenMP(一种用于共享内存并行系统的并行计算方案),在分配28个线程时,加速比为1.17倍,结果表明该方法能够有效实现排列熵算法的加速执行。

基于AES算法和混沌映射的嵌入式终端数据传输并行加密方法

传统嵌入式终端数据传输并行加密方法易受到数据传输迭代过程中暂态特性的影响,加密后数据信息丢失量较大,加密效果不佳。为了减少加密后的信息丢失量,提升加密安全性,提出基于高级加密标准算法和混沌映射的嵌入式终端数据传输并行加密方法。根据嵌入式系统中数据的属性分布情况,对其进行编码设计,基于混沌映射原理,对数据进行初级加密,并对传输数据进行整合,求取其状态矩阵,以消除数据传输迭代过程中暂态的影响,以此为依据,采用AES算法,对数据进行轮钥加密,由此实现数据传输并行加密。对比实验结果显示,所提方法能够为数据提供一个安全且稳定的传输空间,加密后的信息丢失量很小。

基于全流程并行遗传算法的贝叶斯网络结构学习

为解决海量数据情况下学习贝叶斯网络(Bayesian network,BN)结构的算法性能急剧降低问题,基于Spark框架设计了一种全流程并行遗传算法用于BN结构学习(简称为SparkGA-BN)。SparkGA-BN包含互信息计算并行化、遗传算子并行化和适应度评分并行化3个部分。互信息并行计算可以高效减少搜索空间;在演化前增加对种群信息与选择信息的广播来对全种群执行选择操作。选择与交叉算子共用选择信息以并行执行,从而高效演化并减少数据落盘时间。对约束和评分两阶段产生的中间数据作记忆化存储,提升数据复用率和全局执行效率。实验结果表明,所提算法在执行效率和学习准确率方面均优于对比算法。

线云隐私攻击算法的并行加速研究

线云定位方法能保护场景隐私,但也存在被隐私攻击算法破解的风险。该攻击算法能从线云恢复近似点云,但其计算效率较低。针对该问题,提出了一种并行优化算法,并对其运行时间和加速比进行了分析。具体来说,分别采用SPMD模式和流水线模式实现了CPU多核并行和GPGPU并行。然后,进一步结合数据并行模式实现了异构计算,以达到最高的并行度。实验结果表明,并行优化算法加速比最大为15.11,最小为8.20;相比原算法,并行优化算法的还原点云相对误差控制在原误差的0.4%以内,保证了算法的精度。该研究对线云隐私攻击算法以及其他密度估计问题、不同场景下的线云隐私保护算法等有重要意义和参考价值。

基于并行自适应遗传算法的水文模型率定研究

【目的】参数率定是影响水文模型预报精度的重要因素,采用人工智能算法可以有效提高水文模型参数的率定效果。【方法】采用基于种群离散程度的自适应算子,对GA算法的交叉、变异和迁移过程进行自适应优化,并利用粗粒度并行计算模型提高种群进化效率,综合以上手段研究了一种基于自适应策略的并行遗传算法。将传统遗传算法(GA),串行自适应遗传算法(AGA)和并行自适应遗传算法(PAGA),应用于屯溪流域新安江模型的参数率定,从率定效率、率定收敛性、率定稳定性和率定效果四个方面,验证PAGA算法的综合性能。【结果】结果表明:PAGA算法的计算加速效果显著,在10核环境下相对于AGA算法计算时间减少了87.9%;在进化后期,PAGA算法能够更加稳定的收敛于最优解,收敛后的目标函数值具有更好的稳定性;在验证期的场次洪水模拟中,采用PAGA算法率定的模型模拟效果最优,总体洪水合格率大于90%,确定性系数均值为0.85。【结论】PAGA算法能够明显降低模型参数寻优耗时,改善模型率定效果和收敛性能,为水文模型参数的率定提供了新思路。

异构并行计算下高维混合型数据聚类算法研究

高维数据维度增加,数据空间的体积呈指数增长,容易陷入“维数灾难”,导致聚类算法执行效率低,为此,提出异构并行计算下高维混合型数据聚类算法。构建高维混合型数据相异度矩阵,提取高维混合型数据的统计序列特征值,利用时间窗口进行特征优化。采用K⁃Prototypes聚类算法提取高维混合型数据的统计序列特征,评估数据与类中心的相异性,计算数据与类中心的欧氏距离,实现高维混合型数据聚类。采用异构并行计算技术进行高维混合型数据K⁃Prototypes聚类的并行化处理,合理分配CPU与GPU工作,达到CPU与GPU的工作负载平衡,提高K⁃Prototypes的聚类效率。实验结果表明,此算法对于高维混合型数据的聚类效果好、运行时间短、性能稳定。

基于并行计算的电力系统状态估计算法分析

阐述通过引入OpenMP和CUDA并行计算编程模型和框架,能够充分利用多核处理器和GPU硬件资源,并行计算的电力系统状态估计算法大幅度提升计算速度,确保电网状态的评估准确度。

Floyd多源最短路径算法的并行化研究

首先对现有的Floyd多源最短路径算法进行分析,指出了该算法执行效率低下,无法在数据量大的稠密图上高效运行这一问题。为解决这一问题,从并行计算的角度着手研究,将算法中插入点给定时进行一次矩阵迭代并逐条刷新所有当前最短路径的顺序过程优化为基于并行计算的同步刷新过程。该优化使得Floyd算法的时间复杂度由原来的立方阶降低为线性阶,从理论上提高了算法的执行效率,使该算法对数据量大的稠密图顺利进行计算和求解成为了可能。

基于多级并行蚁群算法的智能医疗建筑综合布线系统设计

最小生成树算法(Minimum Spanning Tree,MST)是一种用于在加权连通图中找到最小生成树的算法。其目标是选择连接所有顶点并且边权重之和最小的边的子集。改进的A算法通过动态评估优先级来进行搜索。这种评估方式能够通过启发信息的引导。由于智能医疗建筑综合布线系统架构复杂,导致最小树算法、改进A*算法在安全方面较差,因此,提出基于多级并行蚁群算法的智能医疗建筑综合布线系统设计。在系统的硬件设计上,设计配线架,之后进入嵌入式处理器,最后到达随机存取存储器。在系统的软件设计上,构建医疗建筑综合布线路径的目标函数,根据目标函数,建立布线规划约束条件,完成基于多级并行蚁群算法的最优建筑预埋布线方案求解。对该系统进行性能测试,结果表明,该系统在耗时方面表现较为稳定,满足实际应用需求。

基于KD树和混沌蜉蝣优化的并行谱聚类算法

针对大数据环境下并行谱聚类算法存在的节点负载不均衡、冗余计算、矩阵相乘时间开销大以及初始簇中心敏感等问题,提出了基于KD(k-dimension)树和混沌蜉蝣优化算法的并行谱聚类算法(PSC-MO)。首先,提出基于采样的KD-tree数据分区策略(DPS)划分数据,保证了节点间负载均衡;其次,在构建稀疏相似矩阵过程中,提出优化的分区分配策略(OPA)和基于三角不等式的KD树剪枝策略以进行跨分区的t近邻搜索,避免了过多的冗余计算;然后,提出正规化定理,通过元素对应相乘的方式代替矩阵相乘以优化Laplacian矩阵正规化过程,有效地减少了时间开销;最后,提出混沌蜉蝣优化算法(CMO),得到最佳位置作为初始簇中心后进行k-means并行聚类,解决了算法对初始簇中心敏感的问题。实验表明,PSC-MO算法不但具有良好的聚类效果,而且在大规模数据集上表现出了良好的数据和系统可扩展性。

基于Spark和三路交互信息的并行深度森林算法

针对并行深度森林在处理大数据时存在冗余及无关特征过多、类向量过长、模型收敛速度慢以及并行化训练效率低等问题,提出了基于Spark和三路交互信息的并行深度森林(PDF-STWII)算法。首先,提出基于特征交互的特征选择(FSFI)策略过滤原始特征,剔除无关及冗余特征;其次,提出多粒度向量消除(MGVE)策略,融合相似类向量,缩短类向量长度;再次,提出级联森林特征增强(CFFE)策略提高信息利用率,加快模型收敛速度;最后,结合Spark框架提出多级负载均衡(MLB)策略,通过自适应子森林划分和异构倾斜数据划分,提高并行化训练效率。实验结果表明,所提算法能显著提升模型分类效果,缩短并行化训练时间。

基于Spark的并行频繁项集挖掘算法

针对大数据环境下基于Spark的频繁模式增长(FP-Growth)算法存在创建条件频繁模式树(FP-tree)时空效率低,节点间通信开销大,以及冗余搜索等问题,提出了基于Spark的并行频繁项集挖掘算法(PAFMFI-Spark)。首先,该算法提出非负矩阵分解策略(SNMF),通过提供支持度计数查询和分解储存支持度计数的矩阵,解决了创建条件FP-tree的时空效率低的问题;其次,提出基于遗传算法的分组策略(GS-GA),均衡分配频繁1项集至各节点,解决了节点间的通信开销大的问题;最后,提出高效缩减树结构策略(ERTSS),缩减FP-tree树结构,解决了冗余搜索的问题。实验结果验证了PAFMFI-Spark算法的可行性以及相较于其他挖掘算法的性能优势,所提算法能有效适应各种数据的频繁项集挖掘。

研究生课程“并行算法”教学内容优化设计研究

研究生课程“并行算法”是在大规模科学与工程计算需求越来越大的情况下开设的,旨在让学生学会如何实现并行计算的方法,熟练掌握并行计算的实现过程。基于课程教学经验和实践,论述了侧重并行计算思维训练和理论实践相结合的教学理念,以及基于该理念与模块化方式,从基本概念、基本技术、具体算法到编程实践等层面对教学内容的优化设计,以提升学生的学习效果与综合素质。

改进粒子群算法的不相关并行批处理调度优化

针对粒子群优化(particle swarm optimization,PSO)算法在处理不相关并行批处理调度问题中存在的种群多样性丢失、易陷入局部最优等问题,提出了一种改进PSO的调度优化算法,用于最小化最大完工时间求解。采用基于工件序列的实数编码方式进行编码操作;基于该问题的混合整数规划模型,设计了一种J_B局部搜索的新策略;将模拟退火算法的Metropolis准则引入种群粒子的个体极值搜索。通过随机生成的小型、中型和大型实例对该算法的性能进行了测试,并与针对该调度问题提出的元启发式算法和其他3种元启发式算法进行了比较。实验结果和统计测试表明,该算法的性能明显优于对比算法。