三维前处理有限差分网格剖分的并行化技术

针对前处理中网格剖分模块计算量大、处理速度慢等问题,对网格剖分串行算法进行并行化处理,利用多线程并行机制加以实现。同时对该并行算法进行测试。实验结果表明,该算法相对于串行算法在处理速度上具有绝对优势,且其加速度和并行效率均会随网格精度的提高以及基本实体个数的增多而提高。     

并行数据库的改进Hash划分方法及并行Join算法

文中提出了Ｈａｓｈ划分的改进方法－－ＩＨ划分,ＩＨ划分为结点扩充时数据的重新划分提供了方便,在论述ＩＨ划分的基础上,给出了基于该数据划人垢并行Ｊｏｉｎ算法,利用已有数据分布,文中提出的并行Ｊｏｉｎ算法提高算法的效率。最后,从理论上对以上并行算法的计算复杂性进行了分析。     

像素级遥感图像融合并行算法研究与实现

本文针对遥感图像IHS、HPF、DWT等典型的像素级融合算法,提出并实现了相应的基于数据并行的并行融合算法P-IHS、P-HPF、P-DWT,并在算法时空复杂度分析的基础上进行了通信、I/O优化。针对IKONOS卫星遥感图像在机群系统上的测试结果表明,我们提出的并行算法可获得良好的并行加速比,并行效率较高。这三类算法适合于对实时性要求比较高的遥感应用领域。     

基于PRAM并行模型最大值查找的方法与改进

随着多处理器的出现,并行技术受到了广泛的关注,成为了加速处理问题速度的重要技术.但是使用并行技术在加速计算的同时也带来了对处理器数量需求的急剧提升,并行成本的显著增加.针对这一问题,通过研究基于PRAM （Parallel Random Access Machine）下的3种最大值查找并行算法中的不足,提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本（cost）更优的基于数据划分方法的最大值查找并行算法.基于数据划分方法的最大值查找算法有效的解决了现有并行方法中处理器工作量分配不均,对处理器需求过大,实现条件苛刻等问题.为此后类似并行算法降低并行成本提供一个方向.     

一个基于故障敏化模式分解的并行ATPG算法SPPTG

提出了一个基于故障敏化模式分解的搜索空间并行ATPG算法SPPTG。它与现有的基于PODEM算法的搜索空间并行ATPG算法的显著不同是可对搜索空间进行静态划分。SPPTG已用C语言在SUN工作站上实现 ,并已集成到并行测试生成原型系统P -ATGTA中。实验结果表明 ,SPPTG既可通过扩大搜索空间办法提高单机ATPG的故障覆盖率 ,又可在较短的时间内遍历单机需要搜索的空间 ,获得较高的加速比。     

基于Pthreads的车辆图像兴趣区域提取并行算法研究

为了提高公安机关查找犯罪车辆的效率,提高车辆识别的效率很必要。据统计,提取兴趣区域(Region Of Interest,ROI)约占车型识别过程的60%,因此如何加速提取ROI过程尤其重要。首先,通过数据划分方法实现基本并行算法;然后,经过实验分析,在基本并行算法的基础上,精心设计预处理过程的分解方案,设置多队列缓冲区,减少共用缓冲区的线程数量和每个缓冲区互斥锁锁定的次数。实验证明,所提算法在双CPU 12核(支持超线程到24线程)的服务器上运行,相对于串行算法,实现了13.1x的加速比。     

开源关系数据库集群的并行空间连接算法实现

当前对并行空间连接查询的研究主要集中在算法设计上,缺少在并行关系数据库管理系统上的应用实现研究.通过分析并行空间连接算法流程,利用开源并行关系数据库集群项目PL/Proxy,提出了混合式计算迁移模式并扩展了对空间操作的支持,并在其上实现了可扩展的基于空间划分的并行空间连接算法.通过真实数据的实验表明：设计实现的并行空间连接算法在空间数据划分负载均衡的情况下,可实现近线性的加速比;而在空间划分产生数据倾斜严重的情况下,仍具有一定的加速比,同时具备针对空间划分方案改进的可扩展能力.算法的实现方式为进行并行空间数据管理研究提供了一种可行的解决方案.     

基于对角划分的矩阵乘并行算法

提出了一种新的基于对角划分的矩阵乘并行算法，它在以往行列划分策略的基础上，采用基于对角划分的策略。数值试验表明该算法具有较高的加速比和并行效率。     

一类基于迭代空间条块的并行有限差分Stencil 算法

高效的并行有限差分Stencil 算法对于求解大型线性方程组是十分重要的.针对并行有限差分Stencil 算法中数据局部性差、同步和通信开销大的问题.首先改进传统有限差分Stencil 算法,提出了多层对称遍历有限差分Stencil 算法.然后给出了以迭代空间条块序作为执行序的串行算法,通过沿时间轴对迭代空间进行时滞划分,在不改变迭代算法性质的同时,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行算法,该算法利用改进的多面体模型对迭代空间网格划分,并通过网格条块重排序减少了Cache 缺失率、通信启动和同步次数.理论分析和实验结果表明,该并行模型比传统的区域分解方法和红黑排序并行算法具有更好的数据局部性,并行效率和可扩展性.     

基于代理的并行空间查询语言

目前针对并行空间数据处理的研究主要集中在空间数据划分及其在其基础上的并行空间算法,对空间并行数据库平台本身的可用性,如应用程序的开发模式、高并发请求支持等研究较少。为此,对开源并行关系数据库查询语言进行空间查询扩展,提出一种基于代理的并行空间查询语言,并实现相应的并行数据库平台原型。基于该平台开发标准的网络地图绘图服务,在高并发环境下使用该服务对海量矢量数据进行实时渲染。实验结果表明,该平台具有与传统关系数据库一致的开发应用模式,可提供无缝的衔接方式,在海量数据高并发的情况下具有较高的可用性及查询性能。     

一类大规模稀疏矩阵特征问题求解的并行算法

本文提出一种求解大规模稀疏矩阵特征问题的并行共轭梯度算法.为了提高算法的并行效率,设计了负载平衡的行划分方式,实现了计算和通信重叠的稀疏矩阵重排序方法,通过预处理减少计算过程中各进程间消息传递的通信量.另外,基于多核处理器高性能并行计算,实现了MPI和细粒度(线程级)OpenMP混合并行算法.在深腾7800并行计算机上对并行算法进行了测试,结果表明在进程数增多时并行算法可保持通信时间稳定性,在并行计算机上有很好的扩展性,适合大规模稀疏特征问题的求解.     

迭代空间交错条块并行Gauss-Seidel算法

针对并行GS(Gauss-Seidel)迭代算法中数据局部性差、同步和通信开销大的问题,首先改进传统GS迭代,提出了多层对称GS迭代算法.然后给出了以迭代空间条块序作为执行序的串行执行模型.该模型通过对迭代空间进行"时滞"划分,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行执行模型.该模型改进了迭代空间网格划分,并通过网格条块重排序减少了cache缺失率、通信启动和同步次数.实验结果表明,迭代空间交错条块并行算法比传统的区域分解方法和红黑排序并行算法具有更好的并行效率和可扩展性.     

并行数据库上的并行CMD_Join算法

并行数据库在多处理机之间的分布方法(简称数据分布方法)对并行数据操作算法的性能影响很大.如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法.本文研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基于CMD多维数据分布方法的并行CMD_Join算法.理论分析和实验结果表明,并行CMD_Join算法的效率高于其它并行Join算法.     

A*算法的改进及并行化

针对串行A^*算法时间性能较差的问题,提出了一种基于并行搜索和快速插入(PSFI)的算法。首先,研究了共享存储平台上的常见并行启发式搜索算法;然后,通过使用一种延迟的单表搜索(DSTS)方法和新的数据结构,改进了串行算法;其次,在此基础上,设计出一种基于共享存储平台的并行算法;最后,采用OpenMP加以实现。对24数码问题的测试结果表明,改进的串行和并行算法将运行时间分别减少到原算法的1/140和1/450;与并行的NBlock优先(PBNF)算法相比,并行算法将加速比提高到3.2,同时,改进算法是严格的最佳优先搜索算法,保证了解的质量,且易于实现。     

分布式计算环境下的并行体绘制算法

分布式计算环境中基于消息传递机制的分布式共享缓冲区中，Ｃａｃｈｅ效率是算法性能的“瓶颈”。本文在分布式共享缓冲区上实现了一个并行体绘制算法。在数据空间，八叉树快速分类改善了Ｃａｃｈｅ的空间相关性；在图象空间。Ｈｉｂｅｒｔ象素遍历方式改善了Ｃａｃｈｅ的时间相关性，在曙光１０００和ＳＧＩ工作站网络上的实验结果都表明，算法的网络数据传送量大大减少，Ｃａｃｈｅ效率明显提高，绘制时间大大缩短。     

基于MapReduce的互联网拓扑特征参数算法研究

针对传统单机算法在计算大规模互联网拓扑特征参数时效率低的问题,基于MapReduce分布式计算框架对网络拓扑特征参数算法进行研究。通过分析单机图算法并行移植时存在的问题,提出了图算法并行化设计的原则和消息传递机制;根据设计原则和消息传递机制,为4个网络拓扑参数设计了并行算法。实验证明,并行的拓扑参数算法能够有效提高计算效率,且具备良好的可扩展性。     

并行数据库上的并行CMD－Join算法

并行数据库在多处理机之间的分布方法(简称数据分布方法)对并行数据操作算法的性能影响很大.如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法.本文研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基于CMD多维数据分布方法的并行CMD－Join算法.理论分析和实验结果表明,并行CMD－Join算法的效率高于其它并行Join算法.     

基于OpenMP的Multi-Critical分子动力学并行算法优化

为提高分子动力学模拟在多核共享内存式服务器上的运算速度,在现有的分子动力学并行算法基础上提出了Multi-Critical算法。该算法使用手动划分力矩阵的方法,使多个线程进入不同名的临界区,并使用分块叠加的方法优化了并行算法,提高了并行效率。实验结果表明,对比之前的Critical算法,该算法的加速比和并行效率均有较大幅度的提高。     

多核图像处理并行设计范式的研究与应用

多核计算环境下采用图像处理并行算法可提高图像处理的速度,但已有的并行设计只针对边缘检测、图像投影等特定算法进行,没有形成通用的并行算法设计范式。为此,在研究图像处理算法可并行处理机制和多核架构特点的基础上,提出分析、建模、映射、调试和性能评价及测试发布等5个设计步骤的基于多核计算环境的图像处理算法并行设计范式,以图像傅里叶变换并行算法设计为例在单核、双核、四核、八核计算环境下验证了该并行范式的有效性。实验结果表明,该范式在图像处理并行设计方面可扩展图像处理的应用空间。     

基于多层次并行架构的H.264解码算法

针对高清图像视频的实时解码需求,提出一种基于多层次并行流水架构的解码算法。该算法首先针对图像的宏块行实现基于功能模块的行级并行算法,并通过功能模块的二次划分进行核间负载均衡的优化,再针对解码过程中开销较大的滤波环节,利用宏块之间的依赖关系进行多核并行处理,对行级并行算法进行更深层次上的再优化设计。实验结果表明,该算法可以在TILEPro64平台上实现1 080P全高清码流的实时解码,实现了较高的并行加速比,最高达到10.01,和已有的并行解码算法相比,加速比提升80%。