中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第十二章 并行程序设计基础

第十二章并行程序设计基础 习题例题: 1、假定有n个进程P(O,P(),…,P(n-1),数组元素q订开始时被分配给进程P()。试写 出求归约和q0]+q[+…+q[n-1的代码段,并以n=8示例之 2、假定某公司在银行中有三个账户X、Y和Z,它们可以由公司的任何雇员随意访问。雇 员们对银行的存、取和转帐等事务处理的代码段可描述如下: /*从账户Ⅹ支取￥100元* atomic if(balance[X]>100)balance[X]=balance[X-100 /*从账户Y存入￥100元* atomic( balancelY]=balance[Y]-100:) /*从账户X中转￥100元到帐号Z* if(balance[X>100)4 balance= balance[Z+100 其中, atomic{}为子原子操作。试解释为什么雇员们在任何时候(同时)支、取、转帐时 这些事务操作总是安全有效的。 3、考虑如下使用lock和 unlock的并行代码 noncritical section lock(S) critical section unlock(S); 假定非临界区操作取Tnεs时间,临界区操作取rs时间,加锁取o≮时间,而去锁时间可忽 略。则相应的串行程序需n(Tns+Ts)时间。试问: ①总的并行执行时间是多少? ②使用n个处理器时加速多大? ③你能忽略开销吗? 4、计算两整数数组之内积的串行代码如下: Sum=o: for(i=0;1<N;i++) Sum= Sum+Al"Bl 试用①相并行;②分治并行;③流水线并行;④主-从行并行;⑤工作池并行等五种并行编 程风范,写出如上计算内积的并行代码段。 5、图12.15示出了点到点和各种集合通信操作。试根据该图解式点倒点、播送、散步、收

第十二章 并行程序设计基础 习题例题： 1、假定有 n 个进程 P(0)，P(1)，…，P(n-1)，数组元素 a[i] 开始时被分配给进程 P(i)。试写 出求归约和 a[0] + a[1] ++ a[n −1] 的代码段，并以 n = 8 示例之。 2、假定某公司在银行中有三个账户 X、Y 和 Z，它们可以由公司的任何雇员随意访问。雇 员们对银行的存、取和转帐等事务处理的代码段可描述如下： /*从账户 X 支取￥100 元*/ atomic{ if(balance[X] > 100) balance[X] = balance[X]-100； } /*从账户 Y 存入￥100 元*/ atomic{balance[Y] = balance[Y]-100；} /*从账户 X 中转￥100 元到帐号 Z*/ atomic{ if(balance[X] > 100){ balance[X] = balance[X]-100； balance[Z] = balance[Z]+100； } } 其中，atomic{}为子原子操作。试解释为什么雇员们在任何时候（同时）支、取、转帐时， 这些事务操作总是安全有效的。 3、考虑如下使用 lock 和 unlock 的并行代码： parfor(i = 0；i < n；i++){ noncritical section lock(S)； critical section unlock(S)； } 假定非临界区操作取 Tncs 时间，临界区操作取 Tcs 时间，加锁取 tlock 时间，而去锁时间可忽 略。则相应的串行程序需 n( Tncs + Tcs )时间。试问： ①总的并行执行时间是多少？ ②使用 n 个处理器时加速多大？ ③你能忽略开销吗？ 4、计算两整数数组之内积的串行代码如下： Sum = 0； for(i = 0；i < N；i++) Sum = Sum + A[i]*B[i]； 试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编 程风范，写出如上计算内积的并行代码段。 5、图 12.15 示出了点到点和各种集合通信操作。试根据该图解式点倒点、播送、散步、收

集、全交换、移位、归约与前缀和等通信操作的含义。 P1|1 P23 +P,|3,1 P35 P3[5,1 PP2P3 P3L5,1 (a)点到点 (b)播送 PP2 PP2P P[,3,5 →·P,|3 (c)散播 (d)收集 P11,2,3 1,4,7 P P,4,5,6 P22,5,8 P23 P,3,1 P2「7,8,9 P3L3,6,9 P35 P3L5,3 (e)全交换 (f)移位 P1 PP2P P11,1 P,3 P23,4 P3[5 P35,9 (g)归约 (h)前缀和 图12.15点到点和集合通信操作

集、全交换、移位、归约与前缀和等通信操作的含义。 图 12.15 点到点和集合通信操作