关于串行程序并行化

并行程序设计主要有两种途径,即使用并行程序设计语言编写并行程序,或将串行程序并行化.串行程序并行化是一种比较有效的并行程序设计的途径.通过介绍并行技术的现状及相关分析的一些定义,给出了一个关于在串行程序中识别可并行执行语句的算法,论述了这一算法的意义.     

串行程序的并行划分算法研究

提出了将串行程序并行化的方法．首先对串行程序进行分段,提出并行划分模型,基于这个模型提出一种并行划分算法PDMA;然后给出了相关程度的定义,并根据程序段之间相关程度,提出了一种对PDMA进行改进的并行划分方法RPDMA;最后对这两种算法进行了比较和时间复杂度分析．     

基于OpenMP的湍流场中颗粒碰撞聚合的并行数值模拟

为了快速求解10000个粒子的湍流碰撞聚合问题,采用OpenMP对Smoluchowski方程的FORTRAN求解程序进行了并行处理.数值结果表明:在不改变串行程序结构的情况下,仅对循环体部分进行并行处理,并行效率可高达80%,且串行程序与并行程序的计算结果完全吻合.对于大计算量循环体的并行计算,采用全部处理器进行并行计算时耗时最小.但是对于小计算量循环体的并行计算,采用全部处理器进行并行计算时耗时不一定最小.     

基于循环展开的子字并行指令自动生成

针对向量编译的不足,提出一种基于循环展开的子字并行指令自动生成的方法.该方法利用传统的循环变换技术对多媒体应用中可以进行子字并行的循环进行优化,生成子字并行代码.首先识别出可并行的循环,然后通过循环展开、寄存器重命名、指令合并等技术来提升循环体基本块中的子字并行性.在TTA(transport triggered architecture)体系结构的编译框架下用该方法实现了子字并行指令的自动生成.实验表明该方法得到了较好的加速比.     

基于任务量划分的紧嵌套循环自动并行化方法

采用计算任务量大小的方法,解决了在紧嵌套循环自动并行化过程中存在循环并行化的并行粒度确定问题以及循环自动并行化中数据划分的数据访问局部性问题,在多核系统中实现了紧嵌套循环自动并行化时的数据访问局部性方案和并行化方法,从而构造了一个基于任务量划分的循环自动并行化模型,降低了程序自动并行化中小任务量并行带来的开销.     

稀薄气体直接仿真蒙特卡洛方法交互式并行化系统研究与实现

在分析稀薄气体直接仿真蒙特卡洛（Direct Simulation Monte Carlo,DsMc）方法特点的基础上,研究了基于高性能计算平台的DSMC问题交互式并行化技术,提出了DSMC交互式并行化流程和DSMC程序并行化系统体系结构,实现了能对DSMC问题进行处理的交互式并行化软件系统,并应用到两个微通道DSMC方法算例的并行化中,并行化后的两个算例在8个节点的并行集群系统上的计算结果与原串行程序完全吻合,证明了该交互式并行化方法的正确性．     

类簇级测试任务并行化研究

为了提高传统串行类簇级测试速度, 对类簇测试任务并行化方法进行研究。使用类间依赖关系和类测试依赖关系分析方法将类簇级测试任务并行化问题转化为求解对象关系图中节点的并行性。复杂的类簇关系会形成有向环路, 为确定环路中测试的起始位置需要将环路打破, 提出了综合考虑节点度数、环路数和测试桩复杂度3 种因素的破环方法; 对消除环路的对象关系图进行并行性分析, 并设计了一种分层并行算法。通过实验对串行方案和分层并行方案进行对比, 证明了分层并行方案的有效性。     

PDD算法在对称多处理器高性能计算机上的并行实现

使用基于MPI并行编程方法，对PDD算法进行了并行处理及fortran编程，给出了并行代码在上海大学计算机学院自强2000集群式高性能计算机上的运行结果，以及与串行程序相比较的并行加速比。     

SPMD型程序的自动并行化

介绍了基于共享变量的ＳＰＭＤ型程序自动并行化模型,给出了从串行源程序生成以ＥＰ８６０并行计算机系统为运行环境的并行程序源程序的过程,并详细讨论了一些关键技术和实现方法．     

基于Range Test的交互式数据相关性分析技术

数据相关性分析是开发程序并行性最重要的技术之一 ,但是传统的自动数据相关性分析难以处理实际应用程序的复杂情况 ,而且 ,程序中固有的语义信息也无法为并行化工具所理解。这种状况限制了现有并行化系统的并行效果。一种新技术——交互式数据相关性分析可以改善这一状况 ,其中核心的数据相关性信息提取模块能够将自动数据相关性分析所得的不确定性结果转化成一些简单的问题并提交给用户 ,从而使用户与并行化工具紧密合作 ,改进数据相关性分析的结果 ,进而提高并行化系统的能力。交互式数据相关性分析技术已在清华大学开发的 TIPS并行化系统中实现了。     

基于并行叠加的国土空间开发适宜性评价

在国土空间大数据环境下,基于传统串行叠加分析计算的国土空间开发适宜性评价性能已达极限,需研究并行化方法,以利用更多的计算资源提升国土空间开发适宜性评价的效率.在分析基于多空间对象叠加综合评价原理的基础上,通过引入空间数据预处理方法、空间数据划分方法及并行空间索引,提出并实现了以并行叠加分析为核心的国土空间开发适宜性评价方法.西南四省的国土空间建设用地适宜性评价应用实验表明:本文方法相比传统方法性能提升了至少30倍,且节约了大量的人力物力资源,解决了传统架构下国土空间开发适宜性评价计算效率低或无法胜任的难题.     

基于MapReduce的粒子群投影寻踪模型的设计与实现

利用MapReduce模式设计并实现了粒子群投影寻踪算法的并行化,以提高算法的效率.在分类阶段使用了基于MapReduce的KNN分类算法并行,实验结果表明:基于MapReduce实现的粒子群投影寻踪模型能够有效地寻找到较好的投影方向,确保分类效果;并且与其串行算法相比,在实现效率上有较大的提高.     

结构动力分析显式积分并行算法与实现

在分布式并行计算机环境下开展有限元并行算法研究是计算力学领域的前沿课题之一。基于区域分裂法，提出了结构动力分析两种形式的显式积分法的并行算法及步骤；同时，在用Ｔｒａｎｓｐｕｔｅｒ组成的分布式ＭＩＭＤ并行计算机上，采用３Ｌ并行Ｆｏｒｔｒａｎ编写了计算程序，并将其移植到串并行混合有限元分析软件ＰＦＥＭ中；最后，通过对三维空间钢架结构的实际分析，不仅验证了算法和程序设计的正确性，而且结果表明算法具有较高的并行效率。当２个和３个ＣＰＵ工作时，并行效率分别为０．８和０．７。     

基于MPI的二维经验模分解并行算法

针对二维经验模分解(BEMD)处理大尺寸图像耗时较长的问题,提出了一种基于MPI技术的BEMD并行算法.对BEMD串行程序中极值点选取、平面三角剖分、三角域内数值插值等几个主要部分的运行时间进行了统计,结果表明三角域内数值插值是耗时的主要部分,也是并行化的重点处理部分;随后在高性能计算平台上构建并行环境,基于MPI技术对BEMD算法的包络面生成部分实现了并行化,具体方法是先将剖分后的三角形序列按照进程数均匀划分,使整个图像分割为若干子区域并分配给相应进程,然后各进程拟合出对应子区域的上下Bezier曲面并由0进程进行合并,进而生成上下包络面;最后通过加速比等指标对该算法进行测评.结果表明,算法在30核并行执行时加速比可达20.1396,利用率为64.97%,运行效率的提升较为明显.在数据量达到原始数据的25倍时可扩展性指标为1.3975,表明该算法对大数据量的任务有很好的适应性.      

基于多核系统的隐马尔可夫模型并行算法研究

介绍了一种基于Open MP的多核并行程序设计方法,并使用此方法实现了对基于隐马尔可夫模型的Web文本挖掘程序的并行化改造.实验证明重新设计的多核并行程序相比于原有串行程序在多核微机系统上的运行时间大大减少、程序整体性能得到明显提升.     

基于共享内存的高效OpenMP并行多层快速多极子算法

提出并实现了一种基于共享内存并行平台的OpenMP并行多层快速多极子算法.结合OpenMP并行算法开发的要点和多层快速多极子算法数据分布的特性,对多层快速多极子的填充矩阵模块、矩阵向量相乘中的远相互作用部分进行了OpenMP并行化设计.在分析调度方式和循环次序对计算效率的影响的基础上,提出了一种高效的OpenMP并行多层快速多极子方案.数值实验表明,并行算法与串行精度一致,OpenMP并行算法具有较好的并行效率.     

基于OpenMP的ADPCM算法并行化及效率分析

并行计算作为计算机行业未来发展方向的趋势已显而易见,而并行程序设计是研究的一个重要分支。介绍了ADPCM算法的基本概念,阐述了ADPCM算法并行化的设计与实现,分析了ADPCM并行算法的效率。     

并行数据库查询优化技术研究

并行数据库查询优化的关键是缩减庞大的计划搜索空间，针对无共享结构（SN），充分考虑通信开销，给出代价估计模型，采用两阶段优化方法，依据代价估计模型先对查询树进行顺序优化，并提出一种新的两阶段查询优化策略．对顺序优化的查询计划进行并行化，充分利用了多处理机的并行性，获得了较快的查询响应速度。既具备良好的并行性又避免了复杂性．     

MPP上的并行松弛迭代算法

讨论了松驰迭代算法在大规模并行处理机（massively parallel processor，MPP）计算模型上的并行化，给出了在MPP上的并行算法。该算法将计算近似解向量各分量值的时间错开，从而使各个分量的迭代计算可并行进行。对算法性能进行的分析和在大规模并行处理机系统曙光2000中对算法进行的计算均表明：并行松驰迭代算法具有较好的收敛速度、较高的加速比和可扩放性。