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

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

结合遗传算子的并行萤火虫算法及在车间调度中的应用

论文提出了一种结合遗传算子的并行萤火虫算法,该算法借鉴了萤火虫闪烁移动的思想,对两个种群进行同步并行迭代求解,以提升算法的求解速度和质量;在其中一个种群中引入多尺度协同变异算子,利用不同大小方差的自适应高斯变异机制使整个种群以尽量分散的变异尺度来对解空间进行更详尽的探索,从而使整个种群进行有效变异。函数优化结果表明了该算法的有效性,该算法用于求解以最小化最大完工时间为优化目标的流水车间调度问题,实验结果表明,较传统的单一算法而言,结合遗传算子的并行萤火虫算法在求解车间调度问题方面具有更好的性能。

基于GPU并行算法的景观斑块周长模拟测量仿真

针对景观斑块周长模拟测量过程中收敛速度较慢的问题,提出基于GPU并行算法的景观斑块周长模拟测量方法。通过航拍技术采集景观斑块航拍图像,利用纠偏处理过程与高斯滤波处理过程对景观斑块航拍图像进行预处理。将景观斑块航拍图像输入GPU内,通过计算机GPU片段程序构建景观斑块航拍图像的高斯差分金字塔模型,并行运算过程提取景观斑块航拍图像特征点,确定景观斑块航拍图像中景观斑块的边界线。以边界线为基础,计算景观斑块周长。仿真测试结果显示,上述方法特征点提取过程中横轴与纵轴误差完全收敛时间分别为2.12s和1.80s,周长测量绝对误差与相对误差分别控制在0.60m和1.00%以下。

大规模协同虚拟环境下并行层次兴趣匹配算法

大规模协同虚拟环境运行过程中易产生大量冗余通信数据,影响虚拟现实技术性能的发挥。为了提升虚拟环境运行效率,提出并行层次兴趣匹配算法。创建协同虚拟环境概念模型,分解处理订阅区域信息,引入树结构理论搭建兴趣管理树,将订阅区域映射到兴趣管理树节点上,形成层次化结构,结合LSQR并行算法,实现更新区域与订阅区域的快速匹配。实验结果表明,提出算法获得的兴趣匹配消耗时间最小值为0.36 s,兴趣匹配成功指数最大值为0.94,充分证实了提出算法兴趣匹配性能较好。

基于GPU加速的全源对最短路径并行算法

针对最短路径算法处理大规模数据集低效的问题,提出了基于图形处理器(Graphics Processing Unit,GPU)加速的全源对最短路径并行算法.首先通过优化矩阵乘法算法实现了在工作组内和组间进行并行运算数据,然后减少了非规则行造成的工作项分支,最后降低了工作项对邻接矩阵计算条带存储资源的访问延时.实验结果表明,与基于AMD Ryzen5 1600X CPU的串行算法、基于开放多处理(Open Multi-Processing, OpenMP)并行算法和基于统一计算设备架构(Compute Unified Device Architecture, CUDA)并行算法相比,最短路径并行算法在开放式计算语言(Open Computing Language, OpenCL)架构下NVIDIA GeForce GTX 1 070计算平台上分别获得了196.35、36.76和2.25倍的加速比,验证了提出的并行优化方法的有效性和性能可移植性.

面向动态网络的介数中心度并行算法

介数中心度是评价图中节点重要性的一项常用指标,然而在大规模动态图中介数中心度的更新效率很难满足应用需求。随着多核技术的发展,算法并行化已成为解决该问题的有效手段之一。因此,提出一种面向动态网络的介数中心度并行算法(PAB)。首先,通过社区过滤、等距剪枝和分类筛选等操作减少了冗余点对的时间开销;然后,基于对算法确定性的分析和处理实现了并行化。在真实数据集和合成数据集上进行了对比实验,结果显示在添加边更新时PAB的更新效率为并行算法中最新的batch-iCENTRAL的4倍。可见,所提算法能够有效提高动态网络中介数中心度的更新效率。

RPC模型影像校正并行算法设计及优化

随着遥感技术的发展,卫星遥感影像在环境监测、城市规划、灾害评估、气候变化、农业监测等多个领域的应用越来越广泛。为了应对大规模遥感数据处理带来的计算挑战,提出了基于GPU及多核CPU实现卫星遥感影像RPC几何校正的并行算法,并采用了多流优化、I/O优化、内存分配优化等策略。实验表明,与串行算法相比,GPU并行算法获得了22.9~71.5的计算加速比及2.4~32.4的综合加速比,多核CPU并行算法获得了5.4~5.7的计算加速比及2.1~5.0的综合加速比。

CASC2D分布式水文模型异构并行算法研究

针对CASC2D模型精细化水文模拟时面临的计算耗时长、效率低等问题,在保持产汇流算法和流域拓扑结构的基础上,采用CPU+GPU的异构并行算法对CASC2D模型程序进行重新设计和优化,模型程序中的降雨、产流、坡面汇流和河道汇流过程均优化为并行计算,以提高CASC2D模型的计算效率。将优化后的CASC2D模型应用于前毛庄流域的洪水流量过程模拟,计算结果与原CASC2D模型保持一致。在栅格分辨率为30 m,计算步长为3 s时,与原CPU串行计算方法相比,并行加速比达到34倍以上,并且栅格单元数据精度越高,加速比提升越明显。异构并行算法可在不降低模拟精度的条件下显著提升CASC2D模型的计算效率,满足实时水文预报的应用需求。

基于OpenMP的Floyd并行算法研究

Floyd算法是求解两点之间最短路径的算法之一,但因其时间复杂度较高,在面对大规模的图数据求解最短路径时效率并不高.通过使用OpenMP编程模型对Floyd算法进行并行优化,使其在求解最短路径时可以充分利用多核CPU资源,发挥多核性能,降低时间代价.与依赖于特定硬件的算法相比,基于OpenMP的Floyd并行算法具有更高的通用性和可移植性,可以在各种通用计算平台上实现,包括普通的多核CPU和共享内存系统.相较依赖于特定平台的算法,基于OpenMP实现的Floyd并行算法更具有普适性,可以让更多的研究人员和开发者受益.实验结果表明,并行优化后的Floyd算法在执行效率上得到了显著提升.

遥感影像三角网几何校正并行算法及优化研究

近年来随着遥感技术快速发展,遥感数据处理压力越来越大,科学的遥感影像处理并行算法能有效降低计算时间成本,提升成果时效性。以基于三角网遥感影像几何校正算法为对象,设计了多核CPU,GPU并行算法,并在算法实现过程中进行代码优化,获得了较为理想的加速效果,其中多核CPU算法获得了4.35x-6.43x的加速比,GPU算法获得了1.32 x-19.93x的加速比。结果表明,该算法能够为遥感影像几何校正处理效率改进提供有效途径。

分数布朗运动驱动的随机方程在时间并行算法下的数值收敛性

分数布朗运动是指分子或一些胶体粒子的无 规则运动过程。其每一步行走的时间间隔相等,但步长大小不一样。 本文研究了分数布朗运动驱动的随机方程在时间并行算法下的数值收敛性。粗传播器和细传播器 均采用 Euler-Maruyama 算法,从数值上得到了不同的 Hurst 参数下的算法收敛性。数值结果表明,当 Hurst参数H e [1,1]时,随着Hurst参数递增,收敛速度递增;当Hurst参数H E [2,10]时,随着 Hurst 参数递增,收敛速度递减。

关于发展方程最优控制问题的时间并行算法研究

对发展型微分方程线性二次最优控制问题和带有逐点控制约束的线性二次最优控制问题的数值求解进行了研究和分析,提出了一种新的时间并行算法,并通过数值算例验证了该算法的有效性和收敛性。新的时间并行算法将求解最优控制问题的计算任务拆分成多个独立的子问题进行求解,显著提高了计算效率。这为解决实际工程应用中的最优控制问题提供了一种高效的计算手段,对控制系统的优化和性能提升具有重要意义。

并行算法研究方法学

并行算法是计算机科学中重要的研究内容,已有几十年的发展历程.回顾一下其研究历程,既有高潮也有低谷,究其原因是,它没有形成自身的一套研究方法学.为此文中提出并行算法研究要建立起一套完整的"理论-设计-实现-应用"的学科体系,也就是所谓的并行算法研究的生态环境.只有这样才能够保持并行算法研究稳定、可持续发展,并使得并行算法的研究成果更加实用,从而更富有生命力.

面向新型硬件构架的新一代GIS基础并行算法研究

随着减灾应急、流域模拟、智能交通、宏观规划、区域发展等大型地学问题的不断涌现,地理信息系统(GIS)处理的数据量和计算规模不断扩大,而主流GIS仍以串行计算为基础框架,不能充分利用和发挥当前新型硬件构架(单机多核、多机多核、集群等)计算机资源的能力,难以满足实际应用的规模与高效需求。该文在分析了基础地理算法研究现状的基础上,按计算数据的关联性将基础地理算法的计算特征分为本地计算、邻域计算、区域计算和全局计算,按计算过程的资源消耗分为数据密集型、计算密集型和I/O密集型,提出了相应的并行计算策略,包括串行算法的并行改造、并行算法的性能提升和并行算法的创新设计等。进而研发了面向新型硬件构架的新一代GIS的基础地理并行计算算法库和中间件,并已集成到国产高性能GIS平台——HiGIS中,将会促进我国GIS研究、技术、系统和应用的跨越式发展。

POM海洋模式的并行算法

POM模式目前尚无正式发布的并行版本。通过对POM串行程序的数据流向分析,讨论了POM模式并行化所涉及的关键算法和主要技术问题;并基于消息传递接口(MPI),研发了POM模式的并行版本。测试结果表明,POM并行软件效率较高,达到了业务化要求,业已应用于国家海洋信息中心的再分析业务化系统中。

电力系统暂态稳定仿真并行算法的研究进展

随着高性价比的可扩展集群并行系统的逐步成熟和应用,大规模电力系统暂态稳定并行计算和分布式实时仿真成为可能。本文首先介绍了电力系统暂态稳定的计算模型及基本算法,分析了算法中存在的困难。然后从算法的基本原理和实用效果入手,综述了空间并行、波形松弛和时空并行电力系统暂态稳定算法的研究进展,比较了各种并行算法的优点和局限性,并指出基于集群系统的粗粒度区域分解暂态稳定并行算法最具发展潜力。

采掘关联规则的高效并行算法

采掘关联规则是数据采掘领域的一个重要问题．文中对采掘关联规则问题进行了简单的回顾；给出了一种提高顺序采掘关联规则效率的方法；分析了已有并行采掘关联规则算法的优缺点；设计了一个效率较高的并行采掘关联规则的算法ＰＭＡＲ；并与其它相应算法进行了比较．实验证明，算法ＰＭＡＲ是有效的．

利用最小二乘直接法反演卫星重力场模型的MPI并行算法

针对海量卫星重力数据反演高阶次地球重力场模型的密集型计算任务与高内存耗用问题,基于MPI实现了最小二乘直接法恢复高阶次位系数的并行算法。引入并行读写、分块存储与分块计算等方式完成了设计矩阵的构建、法方程的形成与求解等密集型计算任务的并行算法,数值计算结果表明三者的并行相对效率峰值可分别达到95%、68%、63%。利用GOCE轨道跟踪和径向扰动重力梯度数据(共518 400个历元)分别反演了120、240阶次地球重力场模型,计算时间仅为40min、7h,内存耗用峰值仅为290MB、1.57GB;采用与GOCE同等噪声水平的观测数据恢复的重力场模型精度与GOCE已发布模型的解算精度相一致,联合GRACE和GOCE的解算模型能够实现二者独立信息的频谱互补,表明本文方法可高效稳定地恢复高阶次地球重力场模型。

三维有限差分深度偏移并行算法的设计和实现

针对分布式并行系统的特点 ,设计出一个高效实用的同步并行算法 .使用PVM编程 ,将串行的三维叠后深度偏移软件 ,在SP2上实现了并行化 ,获得了理想的并行效率和可扩展性 .已经在地质情况十分复杂的桩西地区进行实验 .在获得的叠后深度偏移剖面上 ,同相轴归位准确 ,断面清晰 ,构造形态鲜明 ,符合本地区的地质背景 。

从图像中快速检测直线的并行算法

提出了一种在具有可扩展机群体系结构的通用超级并行机环境下的快速直线检测算法.采用最优域划分法将原图像进行N×N等面积划分,并映射到并行系统各节点的局部坐标下进行直线检测.通过先后两次在Hough变换的扫描过程中提前引入阈值作用,可有效减小计算的复杂度.同时证明了,划分后的子图像采用原阈值的1/(2N-1)进行检测,可满足原图像中的直线目标不丢失的要求.实验结果表明,所提算法具备高鲁棒性和强抗噪能力,能有效提升加速比,该比值的最大值可为25.320.