PMVS算法的CPU多线程和GPU两级粒度并行策略

PMVS(Patch-based Multi-View Stereo)三维重建算法被广泛应用于无人机航拍影像的三维场景重建中。针对PMVS三维重建算法计算量大、时间复杂度高的问题,提出了PMVS算法的CPU多线程和GPU两级粒度并行策略(Multithread and GPU Parallel Schema,MGPS),方法具体包括:基于GPU的PMVS算法特征提取和片面扩散的并行设计;多影像的GPU和CPU任务分配机制,以使得部分任务分配给CPU采用多线程并行,部分任务分配给GPU并行时,程序总运行时间最短。实验采用搭载24核CPU和NVIDIA Tesla K20 GPU的高性能服务器作为测试平台,针对分辨率为4081×2993的16幅无人机影像进行三维重建。实验结果表明,相比串行的PMVS算法,基于MGPS的PMVS算法取得4倍左右的加速比,其中特征提取最高加速13倍,计算误差在10%以内,该方法实现了更高效的PMVS三维重建。基于MGPS的PMVS算法还可用于文物保护、医学图像处理、虚拟现实等领域。     

面向科学计算可视化的两级并行数据读取加速方法

为了匹配超级计算机的整体计算能力,超级计算机存储子系统通常具有良好的I/O性能可扩展性,表现为：应用获得存储子系统最佳性能时的I/O访问并发度,与超级计算机系统总计算核数(可达数万至数百万)通常处于同一数量级.然而,科学计算可视化应用通常使用的进程数(等于I/O访问并发度)相对较小(经验上常设为计算进程数的1%,典型值为数个至数百个),因此无法充分发挥超级计算机存储子系统的最佳I/O性能.提出了一种面向科学计算可视化的两级并行数据读取加速方法,在可视化进程内部引入多线程并行数据读取,通过进程间和进程内两级并行,增加超级计算机存储子系统的I/O访问并发度,提升可视化应用数据读取速率.测试结果表明:在不同的可视化进程规模下,两级并行比单级并行峰值数据读取速率提高33.5%~269.5%,均值数据读取速率提高26.6%~232.2%;随着科学计算应用种类以及应用规模的变化,两级并行数据读取可使可视化应用整体峰值运行速度加速19.5%~225.7%,均值运行速度加速15.8%~197.6%.     

多重链路网络分区与QoS度量两级并行QoSR算法

在多重链路上联网络环境下,采用并行路由搜索的思想寻找最优路径,能够获得较好的路径寻优结果,并且算法的时间复杂度较低.给出一种两级并行QoSR算法,将多重链路环境按一定规则划分为若干分区,为每个分区分配一定数量的QoS度量并行处理器和1个分区处理器,在各个分区分别采用QPAS算法,由QoS度量并行处理器并行计算出各分区内的QoS度量Pareto最佳路径,最终由分区处理器调用最短路径并行算法完成分区间代价最小路径的计算.     

基于序列划分策略的Hmmsearch程序两级并行实现

Hmmsearch程序是生物序列分析软件包HMMER中最主要程序之一,采用集中式动态负载平衡方案。为了提高其可扩展性,提出一种基于序列划分策略的两级并行算法,采用分布式动态负载平衡方案。通过增加中间层形成“Master-subMaster’Slave”结构,来改善原“Master-Slave”结构的不足。实验数据表明改进算法比原算法具有更好的可扩展并行性能。     

面向云测试的并行测试用例自动生成方法

为实现云计算环境下的高效软件测试,提出一种Web 应用系统功能测试的并行测试用例自动生成方法。该方法首先根据场景流图采用深度优先遍历算法生成并行测试路径,录制组合产生并行测试脚本,并进行参数化处理;然后,使用基于搜索的软件测试(SBST)方法自动生成可经过目标路径的有效测试数据集,脚本与数据耦合形成大量可并行部署的自动化测试用例。为验证方法的有效性设计了自动化云测试原型系统。实验结果表明,该并行测试用例自动生成方法可以高效地为云平台提供测试用例输入,提高测试效率。     

一种面向地震数据的两级索引

地震数据处理中的数据读取具有块小量大的特点,常规磁盘所用的数据读取方式,其处理速度缓慢。设计了一种基于Fast DFS的分布式地震数据存取系统。该系统将数据分块存储在硬盘上,在Fast DFS中建立基于炮号和道号的两级索引结构,并选取Trie树作为一级索引,AVL树或红黑树作为二级索引,提高了系统读取速度。实验结果表明,该地震数据存取系统减少了相应的查询响应时间,提高了系统存取性能。     

基于两级算法的混沌控制

提出了一种两级算法,可以解决连续混沌系统的最小能量控制问题,首先,给出一个二次目标函数,同时把混沌系统分解为线性部分和非线性部分.上级算法对混沌系统中的非线性部分进行预估,并把整个原系统表为带有常系数的线性系统;下级算法用极小值原理解决这个典型线性二次最优控制问题,并把解返回到上级算法,上级算法根据下级的解对非线性部分重新预估.这样通过两级间不断的信息交换,最终得到混沌系统的最优控制律.该方法不仅实现了对混沌系统的控制,而且在整个控制过程中保证控制能耗为最小.证明了算法的收敛性和闭环系统的稳定性.对统一混沌系统的仿真结果表明了控制策略的有效性.     

基于JavaCC的C代码自动并行化的设计与实现

针对当前大量遗产代码无法重复利用的问题,设计一种新的编译工具将C的串行代码转换为基于MPI+OpenMP的混合并行编程代码,降低了并行编程的开发成本。首先,通过对JavaCC的优化,实现一种可以解析C语言的词法和语法分析器,进行源代码分析并生成抽象语法树;其次,根据语法树对源代码进行控制依赖性和数据依赖性分析,产生可并行化的语句块分区;再次,按照提出的并行代码生成方法得到目标代码;最后,基于Visual Studio 2010构建目标代码仿真验证环境。实验结果表明,该工具可以较为理想地实现串行代码自动并行化,与手工编写的代码在加速比上的误差为8.2%~18.4%。     

面向SoC的系统级并行划分方法

为缩短复杂SoC系统的设计周期,降低系统设计的复杂性,提出了一种SoC系统级的并行划分方法.引入带有信号激活率和输入输出延时的过程模型图,为SoC系统构建模型.设计一启发式算法对该过程模型图进行并行划分,同时,该算法能解决有环图的划分问题.通过大量的实验证明,划分结果同要求吻合,说明该划分方法是可行、有效的.     

面向三维街景重构的立体平行拼图自动生成算法

针对目前已有的多视点拼图技术只注重其二维展示效果,而未考虑三维重构的问题,提出一种面向三维街景重构并结合纹理与深度信息的立体平行拼图(SPM)技术及其生成算法.通过深度信息获得图像场景的平面拟合结果;以最大涵盖建筑物正面和侧面为选取标准,根据平面的参数与位置选出用于拼接的关键视图;基于双缝合线与泊松融合技术对相邻关键视图进行拼接和融合,得到平滑无缝的SPM.实验结果证明,SPM中的纹理拼图具有较好的二维街景展示效果,更主要的是其结合深度信息能够完成街景的三维重构,可为用户提供自由漫游的虚拟城市环境.     

日冕暗化图像检测算法的并行设计与实现

日冕物质抛射（Coronal mass ejection,CME）是空间灾害天气最主要的驱动源。在CME的众多伴生现象中,日冕暗化与之最为紧密相关。因此,对日冕暗化现象进行检测,有助于预报CME的爆发。随着观测数据量的增加,现有日冕暗化检测算法的效率亟待提升。本文基于一种半自动暗化检测算法,提出并实现该算法的并行方案,以提高算法效率,为实现日冕暗化的实时检测奠定基础。首先介绍了日冕暗化的现有工作,接着详细分析了一种半自动暗化检测方法,它在一定程度上提高了人工识别暗化区域的效率,但其效率并不能满足检测的实时性要求。然后,基于Matlab R2014a平台并行机制的特点,从数据、计算量和图像分块角度对半自动暗化检测算法提出了3种不同的并行方案,实验对比分析结果表明图像分块并行方案的效果最优。     

基于互信息的遥感图像区域配准并行算法的研究与实现

图像配准是图像融合、变化检测、目标识别等遥感应用中的重要步骤。互信息由于具有无需预处理、自动化程度高以及鲁棒性强等特点,将其作为一种相似性测度进行图像配准成为近几年图像处理领域的研究热点。随着遥感图像数据量的不断加大,传统的单机处理模式已经无法满足一些应用的时效性要求。基于对串行算法计算瓶颈的实验分析,研究并提出了一种基于互信息的遥感图像区域配准并行算法,分别给出了数据划分策略和互信息计算并行处理方案,采用边界冗余划分和二叉树归约方法减少数据通信,并对算法进行了定量的复杂度分析。实验结果表明该算法可扩展性好,通用性强。     

一种高效的FDE并行传播算法

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相容性算法用于缩减搜索空间.目前,最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇,如Compact-Table (CT)和STRbit算法.它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC).此外,完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性.最为高效的维持fPWC算法是PW-CT算法.多年来,人们提出了多种表约束相容性算法来提高剪枝能力和执行效率.因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码.它一定程度地扩大了问题模型,使在新的问题上维持相对较弱的GAC等价于在原问题...     

基于GEP的分形图像压缩并行算法

传统图像压缩算法存在图像压缩率不高、寻找最优分形图像压缩编码速度慢的不足。为此,提出一种基于基因表达式编程(GEP)的分形图像压缩并行算法。分析二值图像压缩变换的求解过程,给出分形图像基因和染色体的编码表示,设计适应度函数,研究GEP遗传进化操作的编码步骤。在PC机群上的实验结果表明,与串行算法相比,该算法的图像压缩率较高、运行速度较快,具有线性加速比。     

点云重建的并行算法

在三维重建问题中,为了提高重建模型的精确度和完整性,需要增大三维重建的数据量,由此会增加重建的计算量和运行时间。针对该问题,对点云重建过程进行并行设计,降低耗时、提高三维重建的效率,提出在多核CPU、GPU架构和CPU/GPU异构环境下点云重建的并行算法,并在不同实验平台上对Kermit和hallFeng数据集进行了点云重建的并行实验。实验结果表明,相比于串行的点云重建算法,点云重建并行算法在保证重建精度的条件下,取得了较好的加速比,并且并行算法具有实验平台和数据规模的可扩展性。     

A Parallel Implementation of the Katsevich Algorithm for 3-D CT Image Reconstruction

Yu and Wang [1, 2] implemented the first theoretically exact spiral cone-beam reconstruction algorithm developed by Katsevich [3, 4]. This algorithm requires a high computational cost when the data amount becomes large. Here we study a parallel computing scheme for the Katsevich algorithm to facilitate the image reconstruction. Based on the proposed parallel algorithm, several numerical tests are conducted on a high performance computing (HPC) cluster with thirty two 64-bit AMD-based Opteron processors. The standard phantom data [5] is used to establish the performance benchmarks. The results show that our parallel algorithm significantly reduces the reconstruction time, achieving high speedup and efficiency.     

A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times

A hybrid estimation of distribution algorithm (EDA) with iterated greedy (IG) search (EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times (UPMSP-SDST). For makespan criterion, some properties about neighborhood search operators to avoid invalid search are derived. A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region. Two types of deconstruction and reconstruction as well as an IG search are designed in the IG-based exploitation phase. Computational complexity of the algorithm is analyzed, and the effect of parameters is investigated by using the Taguchi method of design-of-experiment. Numerical tests on 1640 benchmark instances are carried out. The results and comparisons demonstrate the effectiveness of the EDA-IG. Especially, the bestknown solutions of 531 instances are updated. In addition, the effectiveness of the properties is also demonstrated by numerical comparisons.      

基于CUDA的拉普拉斯边缘检测算法

拉普拉斯边缘检测算法常用于去除CCD天文图像中的宇宙射线噪声,但其串行算法计算复杂度较高。为此,分析拉普拉斯边缘检测算法的并行性,在统一计算设备架构(CUDA)并行编程环境下,提出一种基于CUDA的拉普拉斯边缘检测图形处理单元(GPU)并行算法。分割天文图像得到多幅子图,根据GPU的硬件配置设定Block和Grid的大小,将子图依次传输到显卡进行并行计算,传回主存后拼接得到完整的图像输出。实验结果表明,图像尺寸越大,该并行算法与串行算法相比具有的速度优势越大,可获得10倍以上的加速比。     

基于并行动态学习型免疫算法的永磁同步电机状态监测

为提高永磁同步电机(Permanent magnet synchronous machine, PMSM)系统参数辨识与状态监测效率,利用图形处理器(Graphics processing unit, GPU)并行计算与 人工免疫技术相结合的研究方法,建立面向永磁同步电机系统基于GPU并行动态学习型 免疫进化的参数估计与状态监测模型.为提高算法的动态跟踪性能,在抗体演化进 程中,通过知识学习策略来引导算法进化过程,首先将抗体群划分为B细胞群、浆细胞 群以及记忆细胞群,对处于不同进化群体中的抗体分别设计免疫综合学习策略、免 疫反向学习策略和高斯学习策略,以增强抗体间的信息交互;接着,应用图形处 理器并行计算技术进一步加速算法求解过程;最后,将所提算法应用于永磁同 步电机系统参数辨识与状态监测中,实验表明,所提方法能同时准确地对电机的定子 电阻、dq轴电感和永磁磁链等系统关键参数进行估计.依据参数变化实现对系统 运行状态进行在线监测与预警.计算结果表明, GPU并行技术能大幅度提高计算效率.