并行仿真

2020/7/201第九章并行仿真引言9.1并行处理的一般概念9.2并行计算机的分类及结构9.3并行算法9.4控制系统的并行仿真2020/7/202引言并行仿真的概念是相对于串行仿真提出的。研究目的：进一步提高仿真速度和精度；满足大型动态系统的实时仿真需要。2020/7/2039.1并行处理的一般概念一、串行仿真1、仿真过程：建模选择算法，选择步长编程序计算在学习并行仿真之前，对串行仿真过程进行回顾，以便更好地理解并行仿真的特点。2020/7/204例：doty=(b/a)y+cy(t0)=y0用欧拉法求解：yn+1=yn+hfn=yn+h(b/a*yn+c)从yn到yn+1一步计算的过程如下：b/ax，x*ynx，x+cx，h*xx，x+ynyn+1运算符：/*+*+运算数：b,a,xx,yn,xx,c,xh,x,xx,yn,yn+1运算符称为指令流；运算数称为数据流；指令流与数据流合称信息流。2020/7/2052、串行计算机在前面例子的计算中，一个操作符只对应一组操作数，产生一个计算结果，这种方式称为单指令流单数据流方式（SISD）。以SISD方式工作的计算机是串行计算机，进行的仿真是串行仿真。串行计算机的结构模型可用下图表示。存储器指令部件运算器指令流数据流2020/7/206二、并行处理并行处理的一般概念是指硬件设备的多倍重复，以处理机部件的多倍重复实现并行运算。并行处理有两种含义：同时性、并发性1、同时性两个或两个以上事件在同一时刻发生。2、并发性两个或两个以上事件在同一时间间隔内发生。第一种情况属于并行计算问题，第二种情况属于串并行混合计算问题。2020/7/2079.2并行计算机的分类及结构一、按信息流传递形式分类并行计算机是并行仿真的硬件基础，根据不同的标准，可分为不同的类型。1、SIMD计算机AP1AP2APnCUISDS1DS2DSn一个操作符作用于多组操作数，产生多个结果。CU：控制单元APi：运算部件2020/7/2082、MIMD计算机AP1AP2APnCU1IS1DS1DS2DSnCU2CUnIS2ISn多个操作符作用于多组操作数，产生多个结果。可进行并行处理，也可单独使用其中之一。3、MISD计算机AP1AP2APnCU1IS1DSCU2CUnIS2ISn多个操作符作用于一组操作数，产生多个结果。2020/7/209二、按并行工作单元的层次等级分类1、关联并行处理机：实现存储器操作的并行。关联存储器：按内容寻址，具有信息并行存储功能。2、流水线处理机（向量机）：实现处理器的并行操作。将计算机的运算部件或控制单元装配成若干有序的子部件。2020/7/20103、并行处理机：实现处理机的并行操作。不同的处理机完成不同的子任务。4、多计算机系统：实现指令和任务的并行。可同时对多条指令及分别有关的数据进行处理，（MIMD）。每个并行单元有独立的操作系统，每个单元均可独立运行。2020/7/20119.3并行算法并行算法及并行计算机的程序与硬件结构密切相关，我们这里学习的是并行算法的基本概念和一般原则。2020/7/2012一、计算问题的分类1、串行计算问题若一个问题的计算是按照SISD方式进行，即：每步计算都是一个操作符作用于一组操作数，产生一个结果，当前步计算依赖于前一步的结果，则称为串行计算问题。2020/7/20132、并行计算问题：若一个问题的计算是按照SIMD方式或MIMD方式进行，各分量之间无依赖，则称为并行计算问题。2020/7/2014例：ui,n+1=ui,n+a(ui+1,n-2ui,n+ui-1,n)，i=1,2,……N从第n步到第n+1步：u1,n+1=u1,n+a(u2,n-2u1,n)，u2,n+1=u2,n+a(u3,n-2u2,n+u1,n)，..uN,n+1=uN,n+a(-2uN,n+uN-1,n)在一步计算中，各分量之间互不依赖，可并行计算。2020/7/20153、串并行混合计算问题若一个问题既有串行计算部分又有并行计算部分，则称为串并行混合计算问题。2020/7/2016例、求向量内积：A=(a1,a2,……,an)’，B=(b1,b2,……bn)’niiibaBA1计算公式：（1）n个乘法：a1b1、a2b2、anbn的计算可同时进行（并行）（2）：两两相加可并行计算，继续相加则为串行。从（1）到（2）为串行。niiiba12020/7/2017二、计算机算法的划分按指令流与数据流的执行方式，计算机算法可分为三类：1.串行算法：SISD，串行计算机2.同步并行算法：SIMD，并行计算机3.异步并行算法：MIMD，并行计算机2020/7/2018三、并行算法的计算树计算树：表示求值过程的二叉树型图，双目操作。ABCDEFG***+++S123456例如，可将S=A+B*（C+DEF）+G的计算过程用计算树表示。每步只有一个操作符，为SISD方式。共进行了6步操作。2020/7/20191、名词术语树叶：输入的n个数。节点：双目操作数的操作符。树枝：节点-节点间或树叶-节点间的连线。树根：计算结果。枝高度：树叶到树根间的枝数。树高：最大枝高度，即计算次数。前面例子的计算树树高为6。应力求降低树高。2020/7/2020例：S=A+B*（C+DEF）+G=A+G+B*（C+DEF）对计算式做一定的变化，使用两台处理机，则计算树可变为如下形式。ABCDEFG***+++S12345树高为5。由于采用两台处理机，计算步数有所减少。2020/7/2021例：对计算式做进一步的变化S=A+B*(C+DEF)+G=A+G+BC+BDEF则计算树为：ABCDEFGB***++++S1234使用2台处理机树高为4。利用率较高ABCDEFGB***++++S123使用4台处理机树高为3。利用率较低2020/7/2022四、N个数求和的计算树以N=16为例，讨论使用不同数量处理机时的计算树。Niias11、使用8台处理机+++++++++++++++1234Sa1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16树高为4，但处理机利用效率较低：从第二步开始大部分处理机闲置。2020/7/20232、使用4台处理机每步最多有4个操作。++++++++1234a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16+++++++S5树高为5，处理机利用效率较高。应采用有限并行度算法，以提高效率。2020/7/20243、使用2台处理机每步最多有2个操作。++++++++1234a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15a16+++++++S5678树高为8。处理机利用效率很高，但树高增加过多，计算时间延长，不是一个好方案。2020/7/2025计算N个数求和的并行算法是同步并行算法，每步的操作符相同，属于SIMD算法。在确定处理机数量时，应综合考虑树高（即计算时间）与处理机利用效率，一般应采用有限并行度算法，兼顾计算时间与利用效率。2020/7/20269.4控制系统的并行仿真求解控制系统的动态响应---数值积分法---串行计算机在某些情况下：仿真模型复杂/仿真实时性要求高将并行处理技术应用到系统仿真中。这就是控制系统的并行仿真。2020/7/2027一、并行仿真讨论如何将并行处理技术应用到系统仿真中。在多台处理机上对同一动态系统进行并行求解，达到减少仿真时间的目的。需要解决的问题：1、设计实用的并行仿真算法；2、将计算任务在单台处理机上合理分配；3、实现信息在各处理机之间的通讯；4、设计并行计算程序，在并行处理机上实现。2020/7/2028二、分割法并行仿真1、基本思想将一个系统分割成两个或两个以上的子系统，将每个子系统分配到一台处理机上进行计算。各处理机并行操作，并协调通讯，求得仿真结果。2020/7/20292、仿真过程设系统的微分方程为：其中：Y=(y1,y2,……,yN)T,F=(f1,f2,……,fN)T（1）将其分割为两个子系统：Y=(Y1,Y2)T于是有)2,1,(22)2,1,(11YYtFYYYtFY00)(),,(YtYYtFY2020/7/2030（2）算法：从分割结果可知，两个子系统之间存在耦合。这种分割法适合在MIMD计算机上进行求解。采用2-RK法，其计算公式为：)12,11,(22)12,11,(21),,(12),,(11)2212(21)2111(21,2,12,2,11,2,2,12,1,2,11,21,2,11,1kYkYhthFkkYkYhthFkhFYYthFkhFYYthFkkkYYkkYYiiiiiiiiiiiiiiiiii2020/7/2031（3）时序：将Y1、Y2分别放在P1、P2处理机内计算，设P1的每步计算时间小于P2每步计算时间，则并行仿真计算一步的时序如下图所示。F2,i,k12F1,i,k11Y2,i+k12Y1,i+k11TwTwTTTTk21k22Y1,i+1Y2,i+1TTTTF1,i+1,F2,i+1,P1:P2:每计算一步，P1、P2之间通讯两次。虽然增加了用于系统同步的时间，但合理分配，可比只用一台处理机快。2020/7/2032（4）特点分割法在本质上是串行的，两个子系统的计算公式互相依赖。由于是通过任务分配实现并行仿真，故影响节省时间的因素主要有：•耦合回路的数量；•各子系统的方程数；•通讯方式2020/7/2033三、并行预报校正法基本思想：得到一组能独立进行运算的迭代公式，以减少通讯量，提高计算速度和效率。1、并行Adams法（并行二阶预报校正法）00)(),,(YtYYtFY系统微分方程为：2020/7/2034)(2::1111cipicicipicipiFFhYYChFYYP并行Adams法是多步法，由预估和校正两个公式组成。开始计算需要出发值，从第三步开始按照公式计算。pcppppYYhFYYhFYY11112001出发值：并行Adams法的公式:2020/7/2035在任务分配时，将预估公式用处理机P计算，将校正公式用处理机C计算，则可实现迭代公式的独立运算。并行仿真计算一步的时序如下图。TTP:Yi+1pFi+1pYi+2pTTC:YicFicYi+1c............一步计算只通讯一次。2020/7/2036对比串行的二阶Adams方法：)(2:)3(2:1111cipicicicicicipiFFhYYCFFhYYP其计算过程为：Yic---Fic---Ypi+1---Fpi+1---Yci+1是一个串行过程。2020/7/20372、MPC法（并行四阶预报校正法）)5199(24:)458(3:321132111cicicipicicicicicipicipiFFFFhYYCFFFFhYYPMPC法是多步法，由预估和校正两个公式组成。开始计算需要出发值。pcpcpcpppppppYYYYYYhFYYhFYYhFYY332211223112001,,,,2020/7/2038在任务分配时，将预估公式用处理机P计算，将校正公式用处理机C计算，则可实现迭代公式的独立运算。并行仿真计算一步的时序如下图。TTP:Yi+1pFi+1pYi+2pTTC:YicFicYi+1c............一步计算只通讯一次。2020/7/20393、并行预报校正法的特点（1）每计算一步只通讯一次。（2）任务分配由算法本身决定，与系统模型无关。（3）与同阶的串行预报校正法计算精度等价。（4）稳定性比串行算法有所下降。在计算Yic时，用到的Yip、Fip是上一步计算求得的，这一步延迟影响了稳定性。