并行计算 考前复习.pdf

《并行计算 考前复习.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、考前复习魏立斐第二章系统互连与基本通信操作使用SF进行多到多播送1(6)1(5)1(4)7654(7)(6)(5)(4)环1(7)1(3)(0)(1)(2)(3)0123步骤1(0)1(1)1(2)第1通信步同时向右(或左)播送2(5)2(4)2(3)刚接收到的信包7654(7,6)(6,5)(5,4)(4,3)示例2(6)2(2)(0,7)(1,0)(2,1)(3,2)0123通讯时间：2(7)2(0)2(1)第2通信步......talltoall(SF)(tsmtw)(p1)7(0)7(7)7(6)7654

2、(4,3,2,1,0,7,6)(6,5,4,3,2,1,0)(7,6,5,4,3,2,1)(5,4,3,2,1,0,7)7(1)7(5)(0,7,6,5,4,3,2)(2,1,0,7,6,5,4)(1,0,7,6,5,4,3)0123(3,2,1,0,7,6,5)7(2)7(3)7(4)第7通信步第二章系统互连与基本通信操作使用SF进行多到多播送(6)(7)(8)(6,7,8)(6,7,8)(6,7,8)环绕网孔678678步骤(3)(4)(5)(3,4,5)(3,4,5)(3,4,5)先进行行的播送345345再进行列的播送

3、注意：信包变大012012示例(0)(1)(2)(0,1,2)(0,1,2)(0,1,2)(a)(b)通讯时间：t(SF)(tmt)(p1)(tmpt)(p1)alltoallswsw2t(p1)mt(p1)sw第二章系统互连与基本通信操作使用SF进行多到多播送(6)67(7)(6,7)67(6,7)(2,3)超立方(2)23(3)23(2,3)(4,5)(5,6)步骤(4)45(5)45(4,5)(0,1)依次按维进(0)01(1)01(0,1)行多到多的(a)(b)播送(4,5,6,7)(4,

4、5,6,7)(0,...,7)(0,...,7)6767(0,...,7)(0,1,2,3)(0,...,7)示例(0,1,2,3)2323(4,5,6,7)(4,5,6,7)(0,...,7)(0,...,7)4545(0,1,2,3)(0,...,7)01(0,1,2,3)01(0,...,7)(c)(d)logp通讯时间：i1talltoall(SF)(ts2mtw)i1tlogpmt(p1)sw第四章并行计算性能评测Amdahl定律：出发点：科学计算中实时性要求很高，时间是个关键的因素，而固定不变的

5、计算负载；=>在一定的计算负载下，为达到实时性可利用增加处理器加快执行速度固定的计算负载分布在多个处理器上的，=>增加了处理器就加快执行速度，从而达到了加速的目的。1967年，Amdahl提出固定负载的加速公式：WsWpSWsWP/p第四章并行计算性能评测Amdahl定律WsWp固定负载的加速公式：SWsWP/pWs+Wp可相应地表示为f+(1-f)f(1f)pS1f1f(p1)fp当p→∞时，上式极限为：S=1/f例：一个串行程序94%的执行时间花费在一个可并行化的函数中。现使其并行化，问该并

6、行程序在10个处理机上执行所能达到的加速比是多少？第六章并行算法的基本设计策略快速排序算法的串行实现输入：无序序列(A,…,A)输出：有序序列(A,…,A)qrqrProc.QUICKSORT（A,q,r）(4)swap(Aq,As)Begin(5)QUICKSORT(A,q,s)ifq

7、}，第六章并行算法的基本设计策略快排序算法的并行化算法PRAM-CRCW上的快排序二叉树构造算法输入：序列(A,…,A)和n个处理器1n输出：供排序用的一棵二叉排序树Begin(1)foreachprocessorido(2)repeatforeachprocessori<>rootdo(1.1)root=iif(A

8、(2.3)RC=ifi(2.4)ifi=RCthenexitelsef=RCendiffiifiendifendrepeatEnd第六章并行算法的基本设计策略程序说明序列(A1,…,An)和n个处理器处理器Pi保存：