动力系统数字仿真的异步并行迭代方法

费景高

文章主题:动力系统 数字仿真 并行迭代法

文章内容：动力系统数字仿真的异步并行迭代方法费景高(北京计算机应用和仿鼻拉术研宽所)(提要)对于动力系统的数字仿真,本文蛤出一类异步并行选代方法,给出可在多处理机系统上并行实现的方法的构造格式,证明了保证异步选代收敛的定理,最后.蛤出数值例子.一,引言考虑由常微分方程初值问题=,.1),(^)0=0…(1_1)所描述的动力系统的数字仿真问题,其中是时间,是状态变量,为维向量,(,)是变量,的维向量值函数,为给定的韧值.设韧值问题(1.)的求解区间为(.当很大或者右端函数(')很复杂时.在串行计算机上进行数字仿真将会遇到根大的困难,需要花费太多的时间.应用目前逐步得到广泛应用的并行计算机系统.将可以克服上述的困难.但由于传统的数值积分方法本质上是串行的,直接将它们移植到并行计算机上效率非常低.需要构造适台手并行计算机的算法.构造常微分方程数值积分的并行算法是一个比较困难的问题.作者在文(1)中将传统的线性多步公式的应用方式进行改变,构造了适合在向量计算机上实现的一类并行算法.何裒平在文(2)中对由一般线性多步公式出发构造的另外两类并行迭代格式进行讨论.向量计算机是单指令多数据流()计算机.由于许多动力系统(1-1)的性质比较复杂,右端函数(,)中可进行向量运算的量不根多,在向量机上对许多动力系统进行数字仿真时并不能达到很高的效串,按作者的观点.用多指令流多数据流计算机()对许多问题(-1)进行数字仿真是比较合适的,它允许对(1.1)的各个分系统进行并行计算.文(3)(4)中的分析表明.算法的同步化是计算机上算法性能下降的主要因素.因此.研究异步并行算法将是在计算机上有效她对动力系统(.1)进行数字仿真的重要途径.本文针对由台处理机和一个共享存贮器组成的多处理机系统构造数值求解(.1)的异步迭代算法.该系统的每台处理机具有自己的存贮器(局部存贮器).可根据处理机中的指令流进行运行.并通过共享存贮器与其它处理机交换信息.对于这种并行计算机系统,允许在属于它的各个处理机上独立地执行多个程序,这些程序可以是不同的,从算法构造的观点来看,按文(5),它属于运算块分解型并行计算机.构造的并行算法称作运算块分解型并行算法.在二中.我们将提出异步并行迭代算法的构造模式,在三.中给出算法异步迭代的收敛一65—性定理.四,中给出一些具体算法及对三,中定理条件的一些验证.在五中我们将给出具体的算倒.-二,异步并行迭代算法的构造模式为了构造数值积分(1.1)的异步并行迭代算法,首先将问题(1.1)分割成若干个(可以解耦舶)子问题.这种分害可按动力系统(1.1)的各个分系统进行.使各个分系统的数字仿真可以并行进行;也可按运动的特征分割,倒如将系统(1.1)中的刚性分量归并成一组,将高额振荡分量归并成一组.从而可对它们采用不同的数字仿真方法进行并行计算.从数学上.上述分割可描述成将向量的分量归并成1个子向量1,.…相应地将问题(1.1)分割成1个子问题.其第个子问题为口.(1,2,…,,,1),(1)(2.1)其中是维向量.(,2.….【')是.维向量值函数.有=+2--.?呻和分别为第个子同题求解的初始时刻和韧值.(2.1)中的右函数'的计算可能非常复杂.计算量报大,并且可能有些量的计算是若干个的计算共有的.为了使各个右函数'的计算量比较均衡.避免重复计算.我『门将右函数'的计算进行分割,将其表示成,2,…,,1)=,1,2,…,,,,2,…,,,)(2.2)其中为其变量?2?…-】,'2,…,'的比较简单的函数,是量1.2.…,,的函数膏,高,(1,2,(2.3)它是右函数=,2,….1的计算过程的予块.为了各个处理机之间进行通讯,在共享存贮器中设置整体变量和=,2,…,,=,2,…?;各个处理机可对其进行读或写.整体变量和中分别存放组(2.1)的解()和的函数一66一,(),(1),2(),…,,(1),1)(2.4)的信息.整体变量,和是这样形成的:设我们已得到散组和1,2.…,.=,2,…,'它们分别存放变量和变量在一些时间点上的值.数组和旦存放在局部存贮器中,它们的构造分别由表2.1和表2.2表示-数组和量中的时间表2.1数组_的构造,蚯表2.2数组的构造啦咖丑集"'七=0,,2,…,七1和"._=0,1-…,1分别称作计算量和的格点集?区间[蚋,删]称作子同题(2.1)的当前数值求解区间,它是问题(1?1)的求解区间[1.,_,]的子区间?通过插值过程-由散组可得到函数(1)的近似(),不限制讨论的一般性?下面采用三次多项式插值,记,()=三口0一),=,,…,一1,.其中盘是插值系数,取,()≤,,()=,()肚&;≤伸+=1'2,…,】一2(2.5),一()≥,删一整体变量中存放插值多项式(2.5)中的插值系数-其构造由表2,3表示,若采用二次多项式插值-可删去表2.3中的第五行的元素?其余类推,由数组,通过插值可得到函数(1)的近似函数,(1),假定,()也具有式(2.5)的形状,其中系数用6表示?将其存放到整体变量中,一67—表2.3整体变量的构造朔】】础5!嘏娟蝎迥啦趣整体变量的构造由表2.4表示,这样,由整体变量和,我们立即可计算.()()-表2.4整体变量口,的构造<>卜.0.11:娘33这样构造的由数组,<>唯一确定,在对数组作一些限定后,它们之间存在一一线性映射,为讨论简单起见,我们认为它们是等同的?-对数组有类似的说明-将歹(),,=1,2,…一1+1,…,,,(1),2,….,代人(2.),我们得到初值同题.循(,),2(,),…,,(),(),…,-(),,…(),…,(),),(埘)(2.6)应用数值积分方法.,对问题(2.6)进行数值积分,得到初值问题(2.6)在格点集¨上的近似值,,=01,…,.由这些值更新数组,再更新整体变量-一68—将函数(1),2,…?肝人的表达式(2.3),计算格点集上的值,((),2(),…,,(),)(2?7)并用这些值更新效组再更新整体变量.我们把整体变量.的每一次更新计