一种GMRES与GMERR的混和算法

近年来Krylov子空间类算法得到了很大的发展，其中GMRES算法已成为求解大型稀疏非对称线性系统的一种成熟并且很有效的解法，但该算法有时会出现停滞，并且它是以残量来判断收敛，并不能很好地衡量近似解的精确程度，而GMERR算法是最近几年出现的另一种Krylov子空间类算法，它和GMRES算法相比是各有千秋，文章结合两种算法的优点，提出了一种组合算法，它对求解大型稀疏非对称线性系统相当有效。     

一种改进的并行关联规则挖掘算法

在FDM算法的基础上,提出了一种改进的并行关联规则挖掘算法FDM_DT,此算法利用DHP算法中的Hash表技术改进了2阶侯选项集的生成过程,并采用Apriori Tid算法中的Tid表技术对事务数据库中的事务数进行有效消减。因此,此算法在处理大规模数据时有较高的综合效率。     

RAPWBN模型上的快速高效并行排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出了RAPWBN模型上的抽取压缩操作算法,并由此得到了RAPWBN模型上的两种快速高效并行排序算法,对长度为N的序列进行排序,在具有N2个处理器和N条行总线的RAPWBN模型上,若总线带宽ω＞logN字节,可以在O(1)时间完成排序.在具有N个处理器和N条行总线的RAPWBN模型上,最好情况下以O(logN)时间、最坏情况下以O(N)时间完成排序.     

基于BSP模型的并行神经网络训练算法

提出了一种适合集群计算机上实现的基于BSP模型的并行神经网络训练算法，分析了其他价函数和加速比，在作者研制的集群计算机上进行了实现和测试，结果表明：当问题规模比较大时，此并行算法能区委了的加速比。     

一种适于串行机实现的图像并行细化算法

为解决现有的图像并行细化算法在串行机上的高效实现问题 ,首先提出了一种 4× 4邻域二值图像的双字节图像编码方案 ,由于在该方案中将每个 4× 4邻域的像素用一个双字节的整数来表示 ,从而将基于整个邻域 16个像素的细化处理转化为一个双字节整数的读、写和比较运算的问题 ;然后在此基础上提出了一种可在串行机上实现的并行细化算法。实验证明 ,该算法适用于当前通用的各种基于模板匹配的并行细化算法 ,其不仅可以取得完全相同的细化结果 ,而且可以大幅度提高图像细化过程在串行机上的执行速度 ;最后简要讨论了该算法利用 PC机中的 MMX技术来进一步提高并行粒度和运算效率方面所具有的潜力     

一种面向并行设计规划的快速布局模型与算法

面向并行设计规划的快速布局是高性能计算机概念设计不可缺少的重要手段,布局目标、布局对象、布局结果等方面的特殊性,决定了传统布局方法难以满足并行设计规划需求。针对巨型机概念设计需求,在传统芯片级与系统级布局规划方法基础上,提出一种面向并行设计规划的快速布局模型与算法。该算法是基于有向图分解模型的分级布局算法,将定时驱动布局思想引入结群过程,是集定时驱动布局、基于结群的布局、基于划分的布局和有向图分解为一体的快速布局算法。该算法被成功应用到某巨型机概念设计的并行设计规划过程。     

RAPWBN计算模型上的快速并行归并排序算法

在介绍带有宽总线网络的可重构计算模型(RAPWBN)的基本结构及其二进制值的前缀和操作的基础上,提出该模型上的一种并行归并排序算法,在具有N~α(1＜α＜2)个处理器和N条行总线的RAPWBN模型上,若总线带宽ω>logN字节,对长度为N的序列进行归并排序,可以在O((loglogN)~2)时间完成.     

蔓叶线的一种并行生成算法

主要研究了著名的几何曲线——蔓叶线的一种并行生成算法,以Bresenham算法为基础,对蔓叶线的并行生成算法进行了分析和讨论。首先,从蔓叶线图像的一个已知点开始,根据递推公式逐点选择最靠近蔓叶线的像素点;然后引入并行机制生成蔓叶线的图像;最后,利用C#多线程模拟实现了该算法。模拟结果表明,这是关于蔓叶线图像的一种快速、高效的并行算法。     

一种更有效的并行系统可扩展性模型

文中首先分析了等效率、等速度和等并行开销计算比三种并行系统可扩展性模型的特点,论证了等效率、等速度和等并行开销计算比三种条件的等价性,并指出这三种模型在描描可扩展性时的不直观及其局限性。然后提出了一种新的可扩展性模型。此模型直观地反映出并行系统在机器规模和问题规模扩展时,其性能的扩展特性。实例研究表明,该模型能更有效地解决下列问题：（1）定量研究并行系统的可扩展性;（2）全面地反映程序、机器、环境方面的因素对可扩展性的影响;（3）指导如何保持并行系统的可扩展性。     

一种快速的基于并行的碰撞检测算法

提出一种基于并行的碰撞检测算法。该算法主要采用并行算法中的分治策略建立环境中每个物体的平衡包围盒树,通过遍历每两棵包围盒树形成对一任务树的遍历,采用并行算法中的流水线技术,利用划分进程遍历任务树从而加速碰撞检测算法。该算法在进程中也应用了多线程技术,因而能运行于单处理机和多处理机上。     

Particle-field decomposition and domain decomposition in parallel particle-in-cell beam dynamics simulation

Particle-in-cell (PIC) simulation is widely used in many branches of physics and engineering. In this paper, we give an analysis of the particle-field decomposition method and the domain decomposition method in parallel particle-in-cell beam dynamics simulation. The parallel performance of the two decomposition methods was studied on the Cray XT4 and the IBM Blue Gene/P Computers. The domain decomposition method shows better scalability but is slower than the particle-field decomposition in most cases (up to a few thousand processors) for macroparticle dominant applications. The particle-field decomposition method also shows less memory usage than the domain decomposition method due to its use of perfect static load balance. For applications with a smaller ratio of macroparticles to grid points, the domain decomposition method exhibits better scalability and faster speed. Application of the particle-field decomposition scheme to high-resolution macroparticle-dominant parallel beam dynamics simulation for a future light source linear accelerator is presented as an example.     

黑油模型新解法器的研制

引言 大型稀疏线性代数方程组的迭代求解是当前数值代数研究领域的核心问题之一,许多成熟的算法已经在大规模科学与工程计算中产生了重要作用.具体到油藏数值模拟软件,线性代数方程组的求解占据了超过80%以上的计算量,故其性能好坏直接决定了油藏模拟的速度和质量,其中由黑油模拟形成的稀疏线性代数方程组迭代     

区域分解型并行预条件的一种粗网格校正算法

区域分解是并行计算的基本手段之一,在稀疏线性方程组迭代求解时,对不完全分解等串行计算时很有效的预条件,经常采用区域分解的思想进行并行化。但区域分解的本质是利用局部解来近似全局解,从而必然存在较大误差,为此,提出一种粗网格校正算法,通过非重叠子区域浓缩,每个非重叠子区域浓缩为一个超结点,形成一个含全局信息且阶数等于子区域个数的小线性方程组,之后用其对原并行预条件进行校正。对块Jacobi型、经典加性Schwarz、以及因子组合型并行不完全分解预条件的实验表明,粗网格校正能有效改善收敛性并提高求解效率。     

A parallel molecular dynamics simulation scheme for a molecular system with bond constraints in NPT ensemble

Equations of motion based on an atomic group scaling scheme are described for a molecular system with bond constraints. The NPT ensemble extended system method is employed along with a numerical integration scheme using an operator technique. For parallelization of the integration scheme, a domain decomposition scheme is employed based on a group of atoms which share common constraints. This decomposition scheme fits well into the integration scheme and involves no extra inter-processor communication during the SHAKE/RATTLE procedures. An example is given for a solvated protein system containing a total of 23 558 atoms on 64 processors.     

无网格方法中的结点分布算法

本文针对无网格法的特点,设计了一种适应于气固两相流直接模拟计算的结点分布算法．该算法在计算域内均匀分布结点,在颗粒周围以辐射状分布结点,并删除其中距离过近以及强烈影响当地结点均匀度的结点．计算表明,该算法在分布结点过程中不需要借助网格,可以直接得到比较理想的结点分布,从而为无网格法应用于气固两相流的直接模拟计算打下坚实的基础．     

化学驱油藏数模并行化中的关键技术

本文描述了化学复合驱数值模拟程序UTCHEM在分布式内存多计算机并行系统SMP-CLUSTER上并行化的关键技术。化学复合驱并行模型采用单程序多数据（SPMD）程序模型,利用区域分解方法将整个求解区域分解为子区域,使得多个计算节点同时求解一个单一的模拟问题。各计算节点通过消息传递对重叠区域的共享数据进行通信,以协调各节点之问的计算。目前仅对压力方程组求解部分进行了并行化实现。测试结果显示了较好的并行效率。     

一类递推方程的一个新的优化向量并行算法

本文提出一种新的解Ｋｏｇｇｅ和Ｓｔｏｎｅ所定义的一类递推方程的优化的并行算法，当采用ｐ台处理机，对规模为Ｎ的一类递推方程求解时，该算法的加速比为Ｏ（ｐ），其中１≤ｐ≤Ｎ＾１－ε，ε是一个任意小的正数，与已有的并行算法相比，该算法具有效率高，适用范围广的优点，该算法可以在ＥＲＥＷ ＰＲＡＭ模型机上实现，也可以在具有素数内存系统的流水线向量处理机上实现。     

高性能网络并行计算模型LogP的剖析

并行计算模型是设计和分析并行算法的基础和关键,在实现高性能网络计算中起重要作用。ＬｏｇＰ是一个面向高性能并行计算的现实模型,它可以用来作为的,可移植的并行算法的基础,这个模型基于四个参数,即。Ｌ,ｏ,ｇ,Ｐ．这些参数反映了高性能网络并行计算的计算带宽,通信带宽,通信延迟,以及传输和计算的结合效率．     

A decomposition method with minimum communication amount for parallelization of multi-dimensional FFTs

The fast Fourier transform (FFT) is undoubtedly an essential primitive that has been applied in various fields of science and engineering. In this paper, we present a decomposition method for the parallelization of multi-dimensional FFTs with the smallest communication amounts for all ranges of the number of processes compared to previously proposed methods. This is achieved by two distinguishing features: adaptive decomposition and transpose order awareness. In the proposed method, the FFT data is decomposed based on a row-wise basis that maps the multi-dimensional data into one-dimensional data, and translates the corresponding coordinates from multi-dimensions into one dimension so that the one-dimensional data can be divided and allocated equally to the processes using a block distribution. As a result and different from previous works that have the dimensions of decomposition pre-defined, our method can adaptively decompose the FFT data on the lowest possible dimensions depending on the number of processes. In addition, this row-wise decomposition provides plenty of alternatives in data transpose, and different transpose order results in different amounts of communication. We identify the best transpose orders with the smallest communication amounts for the 3-D, 4-D, and 5-D FFTs by analyzing all possible cases. We also develop a general parallel software package for the most popular 3-D FFT based on our method using the 2-D domain decomposition. Numerical results show good performance and scaling properties of our implementation in comparison with other parallel packages. Given both communication efficiency and scalability, our method is promising in the development of highly efficient parallel packages for the FFT.     

基于MPI的FDTD并行算法及其优化策略

由高性能PC机通过网络互联构成的集群(COW)并行计算系统上应用基于消息传递(Message Passing)的方式实现FDTD的并行算法,获得了足够的加速比,有效地解决了传统的FDTD方法计算电大尺寸目标电磁散射问题时的不足.通过区域分割,各个子区域在边界处与其相邻的子区域进行场值的数据传递,从而实现了FDTD算法的并行化.利用并行FDTD方法研究了电磁波的介质层的散射,结果表明并行算法和串行计算结果的一致性,并有效提高计算效率.最后还给出了对算法进行通信隐藏的优化方法,进一步提高了并行计算的效率.