网格工作流中基于优先级的调度方法研究

根据网格用户的身份、信誉，以及网格工作流中应用程序的时间紧迫度和依赖关系，提出了网格工作流中应用程序的优先级计算方法．其中，完全优先级调度算法根据网格工作流中的应用程序优先级向量生成调度序列，而且每次只将队列中优先级最高的应用程序提交给网格，而非完全优先级调度算法可同时调度若干无依赖的网格应用程序进入网格，以弥补完全优先级调度算法的并行化问题．实验表明，当网格中的资源较少且资源的性能差异较大时，使用完全优先级调度算法可以保证优先级较高的工作流的应用程序优先使用优势资源；当网格中的资源性能差异不大时，非完全优先级调度算法可解决因资源未充分利用而造成工作流完成时间大幅增加的问题．     

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

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

基于单元级矩阵分解的EBE-PCG算法及其在网络机群并行环境上的实现

基于EBE策略，讨论求解大型线性方程组CG方法及PCG方法的并行计算．在不显式形成总刚度阵的情况下利用单元级矩阵的Cholesky分解构造总刚度阵的近似，形成预条件矩阵，提出了求解大型线性方程组的EBE—PCG并行算法，并讨论了算法在网络机群(COW)并行计算环境下的实现．结合实际算例，对EBE-PCG并行算法进行了并行效率分析．结果表明基于单元级Cholesky分解的EBE—PCG算法具有很好的并行效率，是一种适合网络机群并行环境的高效并行算法．     

网络并行计算在轨道结构动力分析中的应用

针对车辆-轨道结构动力分析问题，提出了一种基于网络并行计算环境的并行求解方法．考虑车辆和轨道结构特征，建立车辆-轨道结构动力分析模型，推求动力响应微分方程．针对推导的微分方程，改进串行求解算法，提出一种宏流水并行算法．针对算法的性质分析了该算法的适用范围，并从理论上分析了最佳节点机个数和最大加速比．考虑车辆通过轨道不平顺情况，实现了求解轨道结构动力响应的宏流水并行程序．分别在工作站和个人计算机组成的网络并行环境中，测试了提出的宏流水算法性能．实验结果表明，宏流水并行算法可以获得良好的加速比．     

嵌入原子势的分子动力学并行算法研究

针对嵌入原子势,提出了1种新的并行分子动力学算法--作用力分解算法.并与另外2种并行算法进行了比较.作用力分解算法并行代码编写简单,不要求模拟区域具有规则形状.而测试并行后的速度表明,当计算的原子数目小于104数量级时,它是最佳的并行算法.     

基于Spark的LIBSVM参数优选并行化算法

利用Spark集群设计LIBSVM参数优选的并行化实现.LIBSVM是一款广泛使用的SVM软件包,广泛应用于模型搭建、样本训练和结果预测等方面.在用LIBSVM训练数据集时,参数的选择对训练结果影响显著,其中以参数C和g最为重要.LIBSVM软件包中采用网格搜索算法对C、g参数组合进行寻优,尽管该算法在单机上实现了并行化,但当数据量达到一定程度时,仍需要花费大量的时间.基于Spark并行计算架构,进行了LIBSVM的C、g参数网格优选并行算法的设计与实现.实验结果表明,提出的并行粗粒度网格搜索C、g参数优选算法比传统算法速度提升了近7倍,而且这一提升将随着集群规模的扩大而进一步加大.另一方面,在粗粒度网格搜索的基础上,进而提出的细粒度并行网格搜索算法又进一步提升了C、g参数组合的优选结果.     

Burgers方程的高精度多步显式格式

为提高Burgers方程的数值计算精度和效率，提出了一种新的高精度多步显式格式．在空间坐标上按差分法离散，在时间方向上将差分改为积分，应用显式指数时程差分法构造出了不同精度的计算格式．对不同初边值Burgers方程进行了数值模拟，并与显式交替分组法、交替Crank-Nicolson并行算法和小波法等算法进行了比较．结果表明，当新方法的网格比是参考算法网格比的2．5～20倍时，新方法数值解的绝对误差仍然小于参考算法数值解的绝对误差．该方法为数值求解非线性偏微分方程提供了一族不同精度计算格式，扩大了指数时程差分法的应用领域．     

弹性动力边界元的并行计算

针对弹性动力边界元实际应用中计算资源不足的矛盾，提出了两种弹性动力边界元的并行算法，即并行积分变换法和并行时间步进法.这两种并行算法都具有在时间上的高度并行性.在算法中采用了合理的计算任务分配方案，使得计算负载达到了尽可能的平衡.算例结果表明，算法具有良好的并行效率.     

基于性能势理论对闭排队网络进行梯度估计的并行仿真算法

对Ｍａｒｋｏｖ性能势理论在一类闭排队网络中的应用给出了一种高效的并行仿真算法．针对仿真中占总运算量７０％以上的一类参数矩阵运算的特点，提出了一种新的矩阵元素对处理器的分配方法：“螺旋式”划分法，使该部分矩阵运算在所有处理器上达到了完全负载平衡；针对仿真中样本轨道数据的大量的广播通讯开销，该文提出用“公共随机数”使所有处理器产生相同的样本轨道，从而以增加很小工作量的代价去掉了这部分通讯开销．另外，由于仿真中占总运算量９０％以上的两部分矩阵计算的特征：没有矩阵元素在各处理器间相互交换的通讯开销，该文算法能广泛地适用于各种体系结构的并行机．最后给出了该并行算法在一台ＳＰＭＤ并行机上的计算结果，显示出该算法能取得接近线性的加速比和较高的并行效率．     

有限元网格自动生成的并行区域划分算法

提出了一种基于网格生成递归法的并行区域划分算法,该算法依据网格生成代价的估算分析,采用迭代分解法对区域进行并行划分．在曙光１０００Ａ系统上的运行结果表明,该网格算法的效率和加速比均优于串行递归算法     

A class of ebe time integration algorithms for transient finite element structural dynamical analysis

A new class of algorithms for transient finite element structural dynamical analysis which is amenable to an efficient implementation in parallel computers (especially Massively Parallel Computers) is proposed. The suitability of the method for parallel computation stems from the fact that, given an arbitrary partition of the finite element mesh, each element in the partition can be processed over a time step independently and simultaneously with the rest, and no global equation solving effort is involved. Although the proposed EBE time integration algorithms are shown to have the structure of an explicit scheme, they are unconditionally stable over a certain range of the algorithmic parameter.     

FPGA+DSP航片并行处理系统

研究了一种采用FPGA +双DSP的航片高速并行处理系统 ,并用区域分解算法对航片处理任务进行划分与分配 .FPGA实现对航片预处理 .DSP实现航片高层处理 .DSP部分由双TMS32 0C6 2 0 1芯片构成高速运算处理单元 ,峰值处理能力每s可达 3.2× 10 9条指令 .FPGA和DSP具有各自的存储器 .在系统中应用符合数字图像处理特点的区域分解并行算法 ,这样使在空间域串行图像处理算法得到并行化 ,从而合理地对任务进行划分与分配 ,同时保证各DSP处理机负载平衡 .该方法适合多种图像处理算法 ,实现简单 ,大大减少了开发的工作量 .经试验表明 ,该实时航片处理系统具有高效、简单、可靠的特点 .     

进程流程图并行划分性质的研究

本文以已赋权的进程流程图作为基础,研究了并行划分的基本性质,探讨了并行划分中程序响应的限界问题。所得结果在一定程度上对于静态调度算法设计具有理论上的意义。文中还提出了一个利于性质研究的并行划分模型。     

并行数据库系统PAROII连接算法

介绍PAROII采用的哈希轮转 (Hash -Round -Robin)数据划分方法以及基于该划分方法的并行RDBn树 ,着重、详细地讨论了基于该树的并行连接算法 ,该算法充分利用了数据的已有分布、Bn 树的特性、叶结合点有序连接、哈希轮转划分的特性 ,这些特性减少了系统的额外消耗 ,提高了并行连接的效率     

利用确定性退火技术的并行聚类算法

划分聚类和分级聚类是两种基本的聚类手段。划分聚类常常可以转换为一个全局最优化问题 ,传统的划分聚类方法很难得到全局最优解。基于确定性退火技术 ,给出了解决划分聚类问题的一种算法 ,并给出了在集群系统上的并行化方案 ,推导出了参与并行计算的最佳处理机数目 ,给出了加速比的估算公式。通过模拟算例可知 ,该算法的特殊结构适合在机群系统上进行并行计算 ,特别对聚类点集相当大的聚类问题 ,由于任务间的通信开销与计算量相比很小 ,能够达到很好的并行效果     

面向同步时序电路的电路并行测试生成算法

面对VLSI设计规模日益增大的挑战，除了电路并行以外，其它已有的基本并行策略都无法从根本上解决测试生成的复杂性问题，然而，已有的电路并行测试生成算法并未取得理想的结果，尤其对时序电路，因此，如何划分电路，成为电路并行算法的设计基础和成功的关键，面向逻辑级描述的同步时序电路，以触发器为核的电路划分算法BWFSF将电路划分为大功能块。对Benchmark-89电路的实验结果表明，基于G-F二值算法和BWFSF算法的电路并行测试生成算法在有效减少存储空间消耗的同时，还能够获得稳定的加速比。     

基于PAR方法的并行最大和算法的推导

在基于薛锦云提出的PAR（Partition-and-Recursion)方法的思想上,通过并行划分数据空间－－自然地称之为并行分划递推,给出了在PRAM和超立方互联网络模型上的并行最大和最优算法,它们的时间复杂性为O（log N)。     

平行六边形上的周期正交小波

通过构造三向剖分下平行六边形上的周期多尺度分析, 利用三向剖分下平行六边形上的离散Fourier变换方法, 给出一类以平行六边形为周期的非张量积二元正交小波的构造方法. 构造的正交尺度函数和小波的两尺度方程中只包含4项,因而相应的分解和重构算法也只有4项. 构造方法易于实现、 计算简单并具有一般性.     

Research on Petri Net System Parallel Subnet Partitioning Completeness Theory and Algorithm

In order to solve the parallel algorithm of Petri net system with concurrent function, so as to achieve the parallel control and simulation operation of this system, this paper proposes the function partition completeness theory and algorithms of Petri net parallelization, thereby providing the theoretical support for the realization of Petri parallel algorithms. Firstly, according to the concurrent characteristics of Petri net model, we analyze the parallelism of Petri net system; then, by giving the solving process of place invariants and the function partitioning of Petri net, we propose the function partitioning conditions and determination theorem of Petri net parallelization, and conduct its theoretical proof and practical verification. On this basis, we conduct the theoretical study and analysis on the situation that Petri net system has several kinds of parallel function partitioning, propose the completeness theorem of parallelism function partitioning in Petri net system, and verify it. Finally, we give the algorithms, application examples and simulation experiment results of parallel function partitioning of Petri net systems based on place invariant. The theoretical proof and experimental results show that the function partitioning conditions and completeness theory of Petri net parallelization based on place invariant are correct, and the parallel algorithms under such theoretical basis are also correct and effective.     

基于机群系统的并行划分聚类算法

从划分聚类要求的时间和空间上看，传统的串行算法已很难适应海量的数据，有必要研发高性能、可扩展的并行算法来解决这一问题，基于一些主要的并行划分聚类算法所存在的问题，提出了在机群系统上采取数据并行策略设计的并行划分聚类算法思想。