一种基于OpenMP的并行混合PVS算法*

针对传统串行混合PVS(Principal Variation Search,主要变例搜索)算法的计算量大、执行耗时长和无法利用多核资源的不足,提出了一种基于OpenMP(Open Multi-Processing)的并行混合PVS算法,该算法应用了PVSplitting(主要变例分裂)策略,自底向上将博弈树每一层的首个PV结点的每个分支的搜索线程化,利用多核CPU并行执行,并对临界区和线程调度进行了合理设计,以提高搜索效率。最后,基于一个真实的中国象棋博弈系统进行了实验,结果表明该算法拥有较高的剪枝率和加速比,能够明显提升混合PVS算法的执行性能。     

基于CUDA的直升机旋翼桨叶挥舞角快速测量方法

针对基于立体视觉的直升机旋翼桨叶挥舞角测量CPU串行算法耗时多、效率不高的问题,利用图像处理单元(GPU)并行计算的优势,提出一种基于CUDA统一计算设备构架的并行处理快速算法.首先,对算法中最耗时的图像去噪、阈值分割、连通域标记三部分进行并行化设计;然后,采用多层次并行策略将大量密集运算分配到不同的图像处理单元上并行执行,利用共享内存和共享寄存器加速数据访问;最后,进行多次测量实验,结果表明该方法执行效率明显高于CPU串行方法,可满足旋翼桨叶挥舞角快速测量的要求.     

基于CPU-GPU的B样条曲面并行刀具路径规划方法

针对传统串行刀具路径规划算法效率低下和在异构硬件平台上的不兼容问题,提出一种基于CPUGPU异构并行计算的刀具路径规划方法。方法针对双三次均匀B样条曲面,依据等参数线刀具路径规划方法的原理和Open CL规范设计并行算法,在CPU的逻辑控制下,采用数据并行的编程模型在GPU的多个工作项上并行执行内核,将传统串行执行的等参数线法进行了并行化重构。仿真实验结果表明,该算法在CPU-GPU异构平台上生成刀具路径的时间较传统串行算法缩短1.5~11.9倍,对实现刀具路径的实时或准实时生成具有重大意义。     

基于CUDA的数字重建影像生成算法

鉴于数字重建影像生成过程具有良好的并行性,实现了一种基于CUDA并行计算的数字重建影像生成算法。该算法首先在CPU端使用八叉树结构来剔除体数据中的空体素并将其载入GPU;然后在GPU中根据光线和线程的对应关系,设计光线内核函数来模拟一束X线穿透人体组织的衰减过程;最后在GPU中由多线程并行执行内核函数来完成DRR图像生成过程。实验结果表明,该方法在保证DRR生成质量的前提下能有效利用GPU的并行计算能力,提高DRR图像的生成效率,满足图像引导放疗中对DRR生成过程的实时性要求。     

基于密度的最小生成树聚类算法研究

基于密度的方法是一种相当有效的聚类方法,能够发现任意形状的聚类,对噪声数据不敏感,但是聚类结果严重依赖于用户参数的合理选择。针对其存在的问题,将最小生成树理论与基于密度的方法相结合,提出了一种基于密度的最小生成树聚类算法。通过构造、分割最小生成树得到确定样本空间划分的最小生成子树;根据子树特性,产生局部密度参数;并对生成子树进行局部密度聚类。理论分析和应用结果表明。该算法不仅体现了基于密度聚类方法的优点,聚类结果不依赖于用户参数的选择,使数据聚类更合理,特别是对大型数据库非常有效;也体现了数据分区的思想,使其可以并行执行,进一步提高了信息处理的时空效率和性能。     

基于GPU的并行最小生成树算法的设计与实现*

针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的minreduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语缩短关键步骤的查找时间,从而获得较高效率。实验表明,相对于传统CPU实现算法和不使用原语的算法,该算法具有较明显的性能优势。     

基于区域图数据流分析的通信优化算法

减少通信开销对于并行化编译器生成高效的分布代码是非常重要的.首先提出了一个冗余并行执行模型(RPEM)作为通信优化算法生成的目标程序的执行模型,之后给出了区域图的概念和区域最大化算法,在最大化区域图的基础上进行数据流分析可以增大数据流分析粒度,提高分析的效率,同时也有助于通信的提前与合并.最后提出了一种基于区域图数据流分析的通信优化算法.该算法能够进行跨循环、跨过程的数据流分析,提高分析的精度,改善通信优化效果.实验结果表明,该算法对于通信量较大的程序能够有效地减少通信的次数和通信量,具有良好的可扩展性.     

一种挖掘XML文档频繁子树的方法

本文主要研究从由带标签有序树构成的森林中挖掘嵌入式频繁子树,具体做法是：首先对XML文档进行预处理,生成最简结构树SST,然后从SST中挖掘出频繁子树。本文提出了SSTMiner算法,该算法针对TreeMiner算法存在的瓶颈问题,结合当前所处理的SST的结构特点进行改进,进一步提高了算法执行的效率。实验证明,本文提出的方法能够准确高效地
地挖掘出XML文档中的频繁子树。     

基于免疫-蚁群算法的度约束最小生成树算法

针对度约束最小生成树问题,借鉴人体免疫系统的适应能力和蚁群算法的全局寻优能力,提出了一种基于免疫-蚁群算法的求解方法.该算法采用Prüfer数对树进行编码及度的改进,利用免疫算法和蚁群算法的融合提高算法的执行速度和进化效率.实验结果表明,用该算法解决度约束最小生成树问题是有效的.     

面向密码流处理器的AES算法软件流水实现方法

针对轮函数在分组密码实现过程中耗时过长的问题,提出了面向可重构密码流处理器（RCSP）的高级加密标准（AES）算法软件流水实现方法。该方法将轮函数操作划分为若干流水段,不同流水段对应不同的并行密码资源,通过并行执行多个轮函数的不同流水段,从而开发指令级并行性提高轮函数执行速度,进而提升分组密码的执行性能。在RCSP的单簇、双簇和四簇运算资源下分析了AES算法的流水线划分过程和软件流水映射方法,实验结果表明,该软件流水实现方法使得单分组或多分组不同数据分块的操作并行执行,不仅能够提升单分组串行执行性能,还能够通过开发分组间的并行性来提高多分组并行执行性能。     

飞行器大数据量CAD模型并行预处理

针对虚拟仿真中飞行器大数据量CAD模型在单台计算机执行预处理非常耗时的问题,采用消息传递接口(MPI)并行开发技术搭建了机群并行处理软硬件平台.以CAD模型装配树的零部件为处理对象,设计了并行预处理算法;通过并行执行几何模型简化、LOD生成、模型分割等预处理,以及动态负载均衡与数据传输存储优化来提高并行处理的效率.实验结果表明:与单台计算机执行相比,其预处理速度提高10倍以上.包含千万级三角面片、GB级数据量的飞行器CAD模型采用该并行处理系统,可以在60 s左右完成预处理.     

图形化编程中模块间并行性的自动挖掘

在基于模块组合的图形化编程中,存在大量互不依赖的模块,这些模块具有并行执行的性质。翻译程序以拓扑排序算法遍历该有向无环图,为每个模块产生一个线程,为每条输入线产生一个信号量,以同步有依赖关系的模块的执行顺序,最终产生一个可并行执行的多线程程序,从而达到自动挖掘并行性、提高所生成程序的运行效率的目的。     

一种并行二值图像连通域标记算法

连通域标记算法在CPU运行效率比较有限,这也是连通域标记算法处理图像的症结所在,针对这一问题,提出了一种并行二值图像连通域标记算法.从二值图像处理问题的可并行化出发,根据GPU并行计算的特点设计出了一种图像预处理、溯源(伪溯源)、伪溯源处理三个步骤的并行标记算法,采用硬件支持的多个线程并行执行处理的方式来提升算法的效率并实现了该算法,实验结果表明该算法相对CPU单线程处理算法效率具有明显提升,也更具有鲁棒性,尤其是图像像素不断增多后,效率更加明显.     

一个网格服务工作流的动态调度算法

针对服务网格环境中资源的动态性,提出了一种并行调度算法PGSWA（parallel grid service workflow scheduling）,该算法引入了性能预测模型和并行就绪队列来预测下一段时间资源的性能并使得成员服务能够并行执行。实验证明,该算法能较好地缩短工作流的执行时间,提高工作流的执行性能。     

一种分布式数据流查询重用算法研究*

提出了一种基于查询树匹配的查询重用算法.首先,系统中原有查询树与新生成的查询树进行匹配并计算对新查询树的重用收益;然后根据重用收益来实现重叠的查询操作的重用.实验结果表明,该算法能够有效地减少连续查询的执行代价总量.     

一种描述逻辑程序执行过程的新方法—OR树林方法

本文提出了一种描述逻辑程序执行的新方法——OR树林方法。这种方法不仅具有并行子任务独立性强的优点,而且有效地解决了传统OR树方法中的两个问题:一是不能描述AND并行执行;二是描述OR并行执行中存在大量冗余,为建立能高效开发AND和OR两种并行性的执行模型提供了新的框架。     

一个调度Fork-Join任务图的新算法

任务调度是影响工作站网络效率的关键因素之一.Fork-Join任务图可以代表很多并行结构,但其他已有调度Fork-Join任务图算法忽略了在非全互连工作站网络环境中通信之间不能并行执行的问题,有些效率高的算法又没有考虑节省处理器个数的问题.因此,专门针对该任务图,综合考虑调度长度、非并行通信和节省处理器个数问题,提出了一个基于任务复制的静态调度算法TSA_FJ.通过随机产生任务的执行时间和通信时间,生成了多个Fork-Join任务图,并且采用TSA_FJ算法和其他调度算法对生成的任务图进行调度.结果表明,     

一种基于Agent和活动优先度的ETL过程并行方法

ETL是数据仓库获得高质量数据的关键环节,在数据仓库的构建和实施中占有重要地位。针对传统ETL串行执行方式的不足,提出一种基于Agent和活动优先度相结合的ETL并行执行方法。该方法计算ETL执行过程中各个活动的优先度,利用Agent理论和多线程并行计算技术实现并行执行具有相同优先度且相互间没有依赖关系的ETL活动。实验结果表明,该方法在数据量较大时具有较好的加速比,提高了ETL过程的执行效率。     

GPU加速的三维人脸真实表情合成

为了对输入的某用户中性表情的三维人脸合成出尽量接近该用户的、带所指定表情类型的三维人脸,提出一种三维人脸表情并行合成算法.使用基于主测地分析(PGA)和径向基函数(RBF)的学习方法建立人脸真实表情模型,并借助泊松方程变形实现表情的合成;由于采用GPU并行执行,因此能够有效地对三维人脸模型进行表情实时合成,且具有高度可并行计算的特性.在Bu-3DFED数据库上的实验结果表明,使用GPU加速后,文中算法的执行速度是使用普通双核CPU执行速度的13倍,并达到近实时合成的性能.     

基于改进的FP-树和数组技术的频繁模式挖掘算法

FP-growth算法是目前较高效的频繁模式挖掘算法之一,该算法不产生候选项集,但递归构造“条件FP-Tree”的CPU 开销和存储很大.为此提出了一种频繁模式挖掘算法IFPmine.首先,为了节省内存空间,采用了约束子树的挖掘方法;其次,采用了数组技术来减少树的遍历时间,从而提高算法的效率.实验结果表明,IFP算法是一种较有效的频繁模式挖掘算法,其挖掘效率优于STFP-树算法和FP-树算法,而需要的内存却少于STFP-树和FP-树算法.