多核程序设计（曲冠南）2 并行计算基础（字体修正版）

1、2小节小节章节章节重点内容重点内容2.0关于并行计算什么是并行计算，怎么并行计算2.1并行计算机体系结构并行计算机体系结构多级存储体系，Cache，并行访存模型。2.2并行计算模型并行计算模型同步并行计算和异步并行计算模型；PRAM，BSP，logP, C3模型2.3进程复习进程知识2.4线程复习线程知识2.5并行编程环境依据并行化粒度2.6编程语言与编译器介绍几种流行的并行编译技术2.7并行计算性能评测并行计算性能评测三大定律，性能评测方法，程序性能优化2.8常用并行数值算法常用并行数值算法从操作数的角度并行化2.9并行编译器流分析、代码优化细粒度细粒度并行通常是在基本块或循环级上通过并行化

2、或向量化编译并行通常是在基本块或循环级上通过并行化或向量化编译器来开发的；器来开发的；中粒度并行一般要求由程序员和编译器共同来开发；中粒度并行一般要求由程序员和编译器共同来开发；粗粒度的并行性的开发则主要依赖于高效的操作系统和所用并行粗粒度的并行性的开发则主要依赖于高效的操作系统和所用并行算法的效率。算法的效率。在通信方面，在通信方面，共享变量的通信常用来支持细粒度和中粒度并行计算；共享变量的通信常用来支持细粒度和中粒度并行计算；消息传递的通信常用来支持中粒度和粗粒度并行计算。消息传递的通信常用来支持中粒度和粗粒度并行计算。一般而言，并行粒度越小，通信和调度的开销也越大；粒度越大，一般而言，并

3、行粒度越小，通信和调度的开销也越大；粒度越大，所开发的并行性的潜力也就越低，但是通信和调度的开销也就越所开发的并行性的潜力也就越低，但是通信和调度的开销也就越小。小。总之：总之：1011内存模块与节点分离内存模块与节点分离内存模块位于节点内部内存模块位于节点内部12131617More chancesEasy to be foundHard to be foundCould be occupied全相联 直接映射组相联Big hallCubicleClassroom212223242526P1P2PnI/OSM1SMm共享存储器处理器（）系统互连总线 交叉开关多级,网络2728LM1P1LM2

4、P2LMnPn互连网络共享本地存储模型29303132消 息 传 递 互 连 网 络(网 络 ， 环 网 ， 超 立 方 ，立 方 环 等 )PMPMMPMPMPMPMPPMPMPM.3334I/ONIC,DIR,RC系统互连网路MemP/CP/CI/ONIC,DIR,RCMemP/CP/C节点N节点 1总线或 交叉 开关总线或 交叉 开关353637383940424344454647484950515253545657585960616264pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWfWWWpWWWWSOOOPSPS/) 1(1)1 (WWfSo/166程

5、 序 中 顺 序 部 分 的 百 分 比f(c)0% 1% 2% 3% 4% 100%加速比SS1024=1024/(1+1023f)1024x91x48x31x24x1x WpWp Wp WpWp WpW1W1W1W1W1W1工作负载W处 理 器 数P (a)123456T1 T1 Tp Tp Tp Tp Tp Tp T1 T1 T1执行时间T处 理 器 数P (b)T112345667686970PSSSSWWpWpWpWppWpWpWS/) p-f (p-p) f ( p -f) p ( f S 111WWfpfWWWpWWSOOPSPS/1171程 序 中 顺 序 部 分 的 百 分

6、比f(c)S1024=1024-1023f0%1%2%3%4%1024x1014x 1004x993x983x加速比S 处 理 器 数P工作负载W (a)W1W1W1W1W1W1WpWpWpWpWpWp123456 TpT1T1T1T1T1T1执行时间T处 理 器 数P (b)123456 Tp Tp Tp Tp Tp72 ppGffpGff/11 pWpGffWWpGffWS/11 73T1Tp执行时间T处理器数P (b)T1T1T1T1T1TpTpTpTpTp处理器数P工作负载W (a)W1WpWpWpWpWpWpW1W1W1W1W112345612345675 微处理器的浮点峰值性能：C

7、PU内部浮点乘加指令流水线的条数、每条流水线每个时钟周期完成的浮点运算次数、处理器主频三者的乘积。 并行计算机的峰值性能得等于处理器峰值性能和处理器个数的乘积。 并行程序的实际浮点性能（衡量并行程序的绝对指标）：总的浮点运算次数和并行程序执行时间的比值。 并行程序能否发挥并行计算机浮点峰值性能主要是看并行程序的实际浮点性能和并行计算机的峰值性能的比值。76TP Ci Di piTLrpii,.2 , 1piDOWiii,.2 , 1pCCipipiii1010maxTspCTNE TTTpDCCPEiiTiiTDDCC,pTTTpDCppTTTTsppPENEDCCCTpSE注释： Sp为加速

8、比84对程序性能进行评测的主要目的就是发现程序的性能瓶颈，对程序性能进行评测的主要目的就是发现程序的性能瓶颈，实施有效的程序性能优化。实施有效的程序性能优化。878889000000000001000002000003000004000005000006000007FFFFFFFFFFFEFFFFFDFFFFFCM0M1M2M396979899 b0=a0*a0; c0=1/b0; b1=a1*a1; c1=1/b1; b2=a2*a2; c2=1/b2; 虽然因为虽然因为c0紧接着紧接着b0计算，让计算的内在含义计算，让计算的内在含义更明显，也更符合通常的更明显，也更符合通常的思维习惯，但对

9、于流水线思维习惯，但对于流水线来说效率极差。来说效率极差。 b0=a0*a0; b1=a1*a1; b2=a2*a2; c0=1/b0; c1=1/b1; c2=1/b2; 先把数组先把数组b计算出来，然后再计算出来，然后再计算数组计算数组c，此时，需要的，此时，需要的b数组数组中的数据都已经计算出来了，就不中的数据都已经计算出来了，就不会存在流水线停滞的问题。会存在流水线停滞的问题。1001051060001020304050607101112131415161720212223242526273031323334353637404142434445464750515253545556576

10、0616263646566677071727374757677aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa10810nkkjikijbac1, 11 , 10 , 11, 11 , 10 , 11, 01 , 00 , 01, 11 , 10 , 11, 11 , 10 , 11, 01 , 00 , 01, 11 , 10 , 11, 11 , 10 , 11, 01 , 00 , 0,)()()(nnnnnnnnnnnnnnnnnnnnijnnijnnijbbbbbbbbbaaaaaaaaacccccccccBACcCbBaA设jiABC109ENDDOENDDOENDDOENDDO110111112011011,TTTTppAAAABBBB,()()i jijCCA BTTif (if (i i !=p-1) then send( !=p-1) the