03-第03章-并行计算性能评测-并行计算的基础-并行计算(共15章)

国家高性能计算中心（合肥）12013/7/24Wednesday第三章并行计算性能评测3.13.1并行机的一些基本性能指标并行机的一些基本性能指标3.23.2加速比性能定律加速比性能定律3.2.13.2.1AmdahlAmdahl定律定律3.2.23.2.2GustafsonGustafson定律定律3.2.33.2.3SunSun和和NiNi定律定律3.33.3可扩放性评测标准可扩放性评测标准3.3.13.3.1并行计算的可扩放性并行计算的可扩放性3.3.23.3.2等效率度量标准等效率度量标准3.3.33.3.3等速度度量标准等速度度量标准3.3.43.3.4平均延迟度量标准平均延迟度量标准国家高性能计算中心（合肥）22013/7/24WednesdayCPU的某些基本性能指标工作负载工作负载执行时间执行时间浮点运算数浮点运算数指令数目指令数目并行执行时间并行执行时间TTcomputcomput为计算时间，为计算时间，TTparoparo为并行开销为并行开销时间，时间，TTcommcomm为相互通信时间为相互通信时间TTnn=T=Tcomputcomput+T+Tparoparo+T+Tcommcomm例：估计例：估计APRAMAPRAM模型下执行时间模型下执行时间TnTTTnTn11,max国家高性能计算中心（合肥）32013/7/24Wednesday存储器性能存储器的层次结构存储器的层次结构((C,L,B)C,L,B)估计存储器的带宽估计存储器的带宽RISCaddr1,r2,r3r8bytes100MHzRISCaddr1,r2,r3r8bytes100MHzB=3*8*100*10B=3*8*100*1066B/s=2.4GB/sB/s=2.4GB/s寄存器1级高速缓存2级高速缓存主存磁盘远程存储器C2KBL=0周期B=1-32GB/S4-256KB0-2周期1-16GB/S64KB-4MB2-10周期1-4GB/S16MB-16GB10-100周期0.4-2GB/S1-100GB100K-1M周期1-16MB/S1-100GB100-100K周期1-300MB/S国家高性能计算中心（合肥）42013/7/24Wednesday并行与通信开销并行和通信开销：相对于计算很大。并行和通信开销：相对于计算很大。PowerPC(PowerPC(每个周期每个周期1515nsns执行执行44flops;flops;创建一个进程创建一个进程1.41.4msms可执行可执行372000372000flops)flops)开销的测量：乒开销的测量：乒----乓方法（乓方法（PingPing--PongSchemePongScheme））节点节点00发送发送mm个字节给节点个字节给节点11；节点；节点11从节点从节点00接收接收mm个字节后，立即将消息发回节点个字节后，立即将消息发回节点00。总的时间除。总的时间除以以22，即可得到点到点通信时间，也就是执行单，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。一发送或接收操作的时间。可一般化为热土豆法（可一般化为热土豆法（HotHot--PotatoPotato），），也称为救也称为救火队法（火队法（FireFire--Brigade)0Brigade)0————11————22————……————--nn--11————00国家高性能计算中心（合肥）52013/7/24WednesdayPing-PongSchemeifif（（my_node_id=0my_node_id=0））then/*then/*发送者发送者**//start_time=secondstart_time=second（（））sendanmsendanm--bytemessagetonode1bytemessagetonode1receiveanmreceiveanm--bytemessagefromnode1bytemessagefromnode1end_time=secondend_time=second（（））total_time=end_timetotal_time=end_time––start_timestart_timecommunication_time[i]=total_time/2communication_time[i]=total_time/2elseifelseif（（my_node_id=1my_node_id=1））then/*then/*接收者接收者**//receiveanmreceiveanm--bytemessagefromnode0bytemessagefromnode0sendanmsendanm--bytemessagetonode0bytemessagetonode0endifendif国家高性能计算中心（合肥）62013/7/24Wednesday并行开销的表达式：点到点通信通信开销通信开销tt((mm)=)=tt00++mm//rr∞∞通信启动时间通信启动时间tt00渐近渐近带宽带宽rr∞∞：：传送无限长的消息时的通信速率传送无限长的消息时的通信速率半半峰值长度峰值长度mm1/21/2：达到一半渐近带宽所要的消息长度：达到一半渐近带宽所要的消息长度特定性能特定性能ππ00：表示短消息带宽：表示短消息带宽tt00=m=m1/21/2//rr∞∞=1/=1/ππ00国家高性能计算中心（合肥）72013/7/24Wednesday并行开销的表达式：整体通信典型的整体通信有：典型的整体通信有：播送（播送（BroadcastingBroadcasting）：）：处理器处理器00发送发送mm个字节给所有的个字节给所有的nn个个处理器处理器收集（收集（GatherGather）：）：处理处理00接收所有接收所有nn个处理器发来在消息，所个处理器发来在消息，所以处理器以处理器00最终接收了最终接收了mnmn个字节；个字节；散射（散射（ScatterScatter）：）：处理器处理器00发送了发送了mm个字节的不同消息给所有个字节的不同消息给所有nn个处理器，因此处理器个处理器，因此处理器00最终发送了最终发送了mnmn个字节；个字节；全交换（全交换（TotalExchangeTotalExchange）：）：每个处理器均彼此相互发送每个处理器均彼此相互发送mm个个字节的不同消息给对方，所以总通信量为字节的不同消息给对方，所以总通信量为mnmn22个字节；个字节；循环移位（循环移位（CircularCircular--shiftshift）：）：处理器处理器ii发送发送mm个字节给处理器个字节给处理器i+1i+1，，处理器处理器nn--11发送发送mm个字节给处理器个字节给处理器00，所以通信量为，所以通信量为mnmn个个字节。字节。国家高性能计算中心（合肥）82013/7/24Wednesday机器的成本、价格与性/价比机器的成本与价格机器的成本与价格机器的性能机器的性能//价格比价格比Performance/CostRatioPerformance/CostRatio：：系指系指用单位代价（通常以百万美元表示）所获取的性能（通用单位代价（通常以百万美元表示）所获取的性能（通常以常以MIPSMIPS或或MFLOPSMFLOPS表示）表示）利用率（利用率（UtilizationUtilization）：）：可达到的速度与峰值速度之比可达到的速度与峰值速度之比国家高性能计算中心（合肥）92013/7/24Wednesday算法级性能评测加速比性能定律加速比性能定律并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。AmdahlAmdahl定律定律GustafsonGustafson定律定律SunNiSunNi定律定律可扩放性评测标准可扩放性评测标准等效率度量标准等效率度量标准等速度度量标准等速度度量标准平均延迟度量标准平均延迟度量标准国家高性能计算中心（合肥）102013/7/24WednesdayAmdahl定律PP：：处理器数；处理器数；WW：：问题规模（问题规模（计算负载、工作负载，给定问题的总计算量计算负载、工作负载，给定问题的总计算量）；）；WWss：：应用程序中的串行分量，应用程序中的串行分量，ff是串行分量比例（是串行分量比例（f=Wf=Wss/W/W，，WWss=W=W11）；）；WWPP：：应用程序中可并行化部分，应用程序中可并行化部分，11--ff为并行分量比例；为并行分量比例；WWss+W+Wpp=W=W；；TTss=T=T11：：串行执行时间，串行执行时间，TTpp：：并行执行时间；并行执行时间；SS：：加速比，加速比，EE：：效率；效率；出发点：出发点：固定不变的计算负载；固定不变的计算负载；固定的计算负载分布在多个处理器上的，固定的计算负载分布在多个处理器上的，增加处理器加快执行速度，从而达到了加速的目的。增加处理器加快执行速度，从而达到了加速的目的。国家高性能计算中心（合肥）112013/7/24WednesdayAmdahl定律（cont‘d)固定负载的加速公式：固定负载的加速公式：WWss+W+Wpp可相应地表示为可相应地表示为f+f+（（11--ff））pp→∞→∞时，上式极限为：时，上式极限为：S=1/fS=1/fWWoo为额外开销为额外开销pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWf)1(1)1(国家高性能计算中心（合肥）122013/7/24WednesdayAmdahl’slaw(cont’d)程序中顺序部分的百分比f(c)0%1%2%3%4%100%加速比SS1024=1024/(1+1023f)1024x91x48x31x24x1xWpWpWpWpWpWpW1W1W1W1W1W1工作负载W处理器数P(a)123456T1T1TpTpTpTpTpTpT1T1T1执行时间T处理器数P(b)T1123456国家高性能计算中心（合肥）132013/7/24WednesdayGustafson定律出发点：出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不须加大计算量，相应地亦必须增多处理器数才能维持时间不变；变；除非学术研究，在实际应用中没有必要固定工作负载而计算程除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。题规模才有实际意义。GustafsonGustafson加速定律加速定律::并行开销并行开销WWoo：：PSSSSWWpWpWpWppWpWpWS/')p-f(p--p)f(p-f)p(fS'111WWfpf国家高性能计算中心（合肥）142013/7/24WednesdayGustafson定律（cont‘d)程序中顺序部分的百分