常微分方程（组）的Runge Kutta异步并行算法及在多Transputer…

并行算法的研究应以实用性，可实现性以及最大的并行处理效率为出发点，在解常微分方程Ｒｕｎｇｅ Ｋｕｔｔａ并行地的基础上进一步提出了一种针对Ｔｒａｎｓｐｕｔｅｒ并行多处理机系统实现的异步并行算法，该算法可划分若干ＯＣＣＡＭ并发进程一一映射到多个处理机上且进程间采用异步通讯机制。     

网格中数据并行流水线的任务指派优化

为了缩短网格中数据并行流水线在吞吐率受限下的延迟,提出了一种优化任务指派的算法.在一个流水线中,每个任务都可以是一个数据并行程序.当多个任务被指派到同一个并行系统时,假设每个任务排他地使用一组处理机.根据优化目的,优化过程可分成连续的两个阶段,即提高吞吐率和缩短吞吐率受限下的延迟.对不同的优化阶段,用不同的启发式算法确定一个并行系统中每个任务的处理机数.改派任一任务都会使流水线的性能发生变化,性能提高的幅度被称为任务优先级.通过重复改派优先级最高的任务,流水线的性能可迅速提高,这在仿真实验中已得到了证实.     

一类椭圆型方程边值问题异步并行算法的构造

基于多数据流多指令流MIMD计算机上的异步并行运算机理，针对一类二阶椭圆型偏微分方程第一边值问题，研究了并行迭代算法的构造方法。在构造差分格式的网格中，对非正则的边界点采用特殊的归类处理方法，从而对差分方程组的系数阵实现了估值判定，并在各处理机完成相应子任务的自治运算下，推出了一个异步并行计算的迭代格式，最后给出了该算法收敛的充分条件。     

常微分方程（组）的RunaeKutta异步并行算法及在多Transputer系统上的实现

并行算法的研究应以实用性、可实现性以及最大的并行处理效率为出发点．在解常微分方程（组）ＲｕｎｇｅＫｕｔｔａ并行算法的基础上进一步提出了一种针对Ｔｒａｎｓｐｕｔｅｒ并行多处理机系统实现的异步并行算法，该算法可划分成若干ＯＣＣＡＭ并发进程一一映射到多个处理机上且进程间采用异步通讯机制．作为一个应用实例，文中用ＯＣＣＡＭ语言编写了三阶ＲｕｎｇｅＫｕｔｔａ异步并行算法程序，做了算例，并获得了令人满意的结果．实例表明，由于该算法避免了进程间同步通讯等待所需的时间开销，而使算法的效率得以提高．     

并行后缀树的构造及查询算法

针对生物信息领域中传统后缀树构造算法在时间和空间上的限制,从结构并行的角度提出了一种新颖的、适用于生物信息学应用的并行后缀树结构和相应的构造算法·该算法首先将给定字符串分成若干连续的片段,并在各个处理机上分别构造这些片段的后缀树,形成了一种分布于多个处理机上的并行后缀树结构·该并行算法不仅大大缩短了后缀树的构造时间,而且避免了主存大小的限制·经分析,其性能优于现有的任何一种并行算法·在此基础上,提出了一种高效的基于这种并行后缀树的字符串匹配算法,解决了传统后缀树的基本查询问题·     

并行查询中的处理机分派算法研究

讨论了并行查询中丛生树的自顶向下和自底向上两类处理机分派算法的优点及其不足之处，在此基础上提出了一个新的处理机分派的调度算法，本算法可达到近似最优调度效果．     

非线性规划问题的异步并行的拟牛顿算法

提出了一种求解非线性规划问题的异步并行拟牛顿算法，若假设目标函数是凸的，线性搜索采用Wolfe原则，讨论了所设计的并行算法的全局收敛性。     

并行查询中的处理机分派算法研究

讨论了并行查询中丛生树的自顶向下和自底向上两类处理机分派算法和优点及其不足之处，在此基础上提出了一个新的处理机分派的调度算法，本算法可达到近似最优调度效果。     

机组组合的扩散并行遗传算法

研究了在细粒度并行机上的扩散并行遗传算法．遗传算法中个体为矩阵个体,选种采用竞争法．并行处理机拓扑结构为三维网格．对一个十机系统的机组组合问题进行了串行模拟,结果表明,当最大遗传代数或并行处理机个数增大时,均可找到更好的解,同时加速比也得以提高,且异步法优于同步法．     

网格中数据并行流水线的任务指派优化

为缩短网格中数据并行流水线在吞吐率受限下的延迟,提出了一种优化任务指派的算法.在一个流水线中,每个任务都可以是一个数据并行程序.当多个任务被指派到同一个并行系统时,假设每个任务排它地使用一组处理机.     

NonlinearAsynchronousBlockIterativeMethod

ＮｏｎｌｉｎｅａｒＡｓｙｎｃｈｒｏｎｏｕｓＢｌｏｃｋＩｔｅｒａｔｉｖｅＭｅｔｈｏｄ＊ＬｉＱｉｎｇｙａｎｇ（李庆扬），ＣａｏＹａｎｇ（曹阳），ＴｉａｎＺｈａｏｙｕｎ（田肇云）ＤｅｐａｒｔｍｅｎｔｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，Ｔｓｉｎｇｈｕａ...     

异步并行非线性多分裂Newton-GAOR方法的收敛性

本文首先给出了解非线性方程组的Ｎｅｗｔｏｎ－ＧＡＯＲ方法．在此基础上，我们得到了异步并行非线性多分裂Ｎｅｗｔｏｎ－ＧＡＯＲ（简记为ＡＰＮＭ－Ｎ－ＧＡＯＲ）方法，证明了方法的局部收敛性，给出了其Ｒ１收敛因子，并得出了多步ＡＰＮＭ－Ｎ－ＧＡＯＲ方法比一步方法收敛更快的结论，文［１］［４］可看作本文的特例     

关于新拟牛顿法的一种异步并行算法

对于新拟牛顿方程，文章提出了一种求解无约束优化问题的异步并行算法，并讨论了所设计算法的全局收敛性．     

异步并行牛顿法的单调收敛性

本文对非线性方程组ＦＸ＝０提出异步并行牛顿法的单调型算法,算法的整体收敛性及局部超线性收敛性的证明。     

用平行法确定单相异步电动机的启动电容

用平行法确定了单相异步电动机的最佳启动电容，并作了与之相关的讨论．     

异步并行Newton迭代法的单调收敛性

文中讨论在多处理机系统上求解非线性方程组的异步并行Newton迭代法及其单调收敛性     

求解图最大团的并行算法

本文给出了一个求解图中最大团的异步并行算法。在算法中采用了最优先搜索和分枝限界法等人工智能搜索技术,避免了无意义的搜索。其特点是易于在共享内存多处理机的并行计算机上实现,其执行时间曲线表明,对图中任意2点之间边存在概率小于1/3的无向图,具有较高效率的求解过程。还给出了在一定条件限制下,求解 NP—完全问题的方法。     

求解可分离凸优化问题的非精确混合分裂算法

针对一类有四个块变量的可分离凸优化问题,提出一种非精确混合分裂算法.在每一轮迭代中,该算法需要求解四个子问题,根据子问题计算工作量的大小,将四个子问题分为两组,每组包含工作量相当的两个子问题.算法在组内执行平行分裂方法,两组间执行交替方向方法,并允许迭代子问题的非精确求解.在适当的条件下,证明了所提出的混合分裂算法具有全局收敛性.     

A class of stable difference schemes for linear elliptic PDEs and their asynchronous parallel computation

This paper improves and generalizes the two difference schemes presented in paper [1] and gives a new difference scheme for second order linear elliptic partial differential equations, its difference matrix is a M-matrix and because of the stability of the M-matrix, it is convergent by the asynchronous iterative method on multiprocessors. Then this paper gives a class of difference schemes for linear elliptic PDEs so that their difference matrixes are all M-matrixes and their asynchronous parallel computation are convergent.