A parallel and scalable algorithm for ADI method with pre-propagation and message vectorization

It is hard to implement the ADI method in an efficient way on distributed-memory parallel computers. We propose “P-scheme” which parallelizes a tridiagonal linear system of equations for the ADI method, but its effectiveness is limited to the cases where the problem size is large enough mainly because of the communication cost of the propagation phase of the scheme.

In order to overcome this difficulty, we propose an improved version of the P-scheme with “message vectorization” which aggregates several communication messages into one and alleviates the communication cost. Also we evaluate the effectiveness of message vectorization for the ADI method and show that the improved version of the P-scheme works well even for smaller problems and linear and super-linear speedups can be achieved for 8194 × 8194 and 16,386 × 16,386 problems, respectively.     

峡谷和垭口地形风场特征的CFD数值模拟

为获得峡谷和垭口地形的风场特征和典型位置的风加速效应,采用计算流体动力学(CFD)方法进行模拟计算,将计算得到的单山结果与风洞试验及规范进行对比以验证CFD计算的有效性,对峡谷和垭口地形进行数值模拟计算,分析峡谷和垭口在不同山脚间距时的加速效应,针对内侧山脚和山顶处的加速比给出设计建议.研究表明:山顶处加速比最大;山体横风切面的加速效应比顺风切面显著;CFD模拟与风洞试验结果吻合较好;山顶处,垭口地形风加速效应比峡谷和单山都大;内侧山脚加速比随着两山靠近而增大;内侧山脚处,峡谷地形的加速比小于规范下限,垭口地形在山间距小于一半山体底部直径、离山表面高度低于0.4倍山体高度时的加速比大于规范上限;山顶处的加速比在各种工况下均比较接近;不建议将山顶和垭口位置作为构筑物的选址地点.     

基于核方法的并行模糊聚类算法

介绍并分析了模糊C-均值聚类算法、基于核方法的模糊C-均值聚类算法以及硬聚类算法.将硬聚类算法和模糊聚类算法结合起来,利用硬聚类算法初始化聚类中心,有效的减少模糊聚类算法的迭代次数.针对海量数据处理问题,将改进后的算法并行化,有效地提高了数据处理速度和效率,并在分布式互联PC环境下进行了性能测试.测试结果表明,基于核方法的并行模糊聚类算法具有很好的规模增长性和加速比.     

无约束最优化问题的BFGS并行算法与实现

介绍无约束最优化问题的BFGS算法及其收敛性,提出利用行卷帘格式并行Cholesky分解法、同步并行Wolfe-Powell非线性搜索和并行处理BFGS修正公式来构建BFGS的并行算法,并对该算法的时间复杂性、加速比进行分析。在PC机群数值实验的结果表明,BFGS并行算法提高了无约束最优化问题的求解速度,理论分析与实验结果相一致,并行算法具有线性加速比。     

并行程序的优化与性能评价

文中讨论了并行程序的优化问题,指出并行程序的优化应从数据划分、通信优化和串行优化三个方面着手。针对传统加速比的缺点和不足,我们提出了优化加速比模型来评价优化并行程序的性能;对ＮＡＳ基准测试程序ＭＧ和ＦＴ进行了优化,用优化加速比模型分析了上述两个程序在ＩＢＭ ＳＰ２上的性能。     

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

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

MPEG2到H.264的并行视频转码算法

针对高清视频的实时转码需求,提出一种基于多核处理器的并行视频转码算法。在确定转码系统所需核数的基础上,采用功能划分和数据划分相结合的方法对转码器进行划分,通过优化核间数据交互,实现MPEG2到H.264的高清视频转码。实验结果表明,该算法能提高转码模块的并行程度以及数据交互性能。     

粗粒度并行遗传算法性能分析

依据实验来分析影响并行遗传算法性能的因素得到的结论缺乏理论上的说服力．通过对粗粒度并行遗传算法加速比公式的分析，提出了影响并行遗传算法性能的关键因素，同时否定了以迁移率作为评价并行遗传算法性能指标的合理性，并通过实难进一步验证结论的正确性．得到的结论为提高遗传算法的并行化效率提供了可靠的依据。     

弹性地基上各向异性平行四边形板

推导出弹性地基上各向异性平行四边形板的控制微分方程和内力方程。并利用对称性将其分解成中心对称和中心反对称两个问题,进而对每个问题给出了两个齐次解和一个特解,通过叠加而得到用重傅立叶级数表示的全解,该解克服了过去人们用重傅立叶级数仅在一个方向用一种级数(正弦或是余弦函数)表示导致的弊端。另外还给出了加快傅立叶级数收敛速度的计算公式。     

用于含过程调用DO循环的循环嵌入方法

循环是程序中蕴含并行性最为丰富的一种结构，因此成为并行化编译最主要的对象．但循环内的过程调用严重妨碍了循环的数据相关性分析，使得循环语句潜在的大量并行性得不到开发．本文提出的循环嵌入方法使部分含过程调用循环语句的并行化成为可能，对部分用其它过程间分析技术也能开发其并行性的这一类循环语句采用循环嵌入方法，并行化开销低，并且分析更精确．采用循环嵌入方法还可降低程序由于多次过程调用带来的调度开销．这一方法在作者开发的自动并行化编译系统AFT（automaticPortrantransformer）中得到了实现，对Spec92测试程序包的试验结果表明了本文提出的方法是行之有效的．