第十二章 并行程序设计基础.doc

第十二章并行程序设计基础
习题例题:
1、假定有n个进程P(0),P(1),…,P(n-1),数组元素开始时被分配给进程P(i)。试写出求归约和的代码段,并以示例之。
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、。试根据该图解式点倒点、播送、散步、收集、全交换、移位、归约与前缀和等通信操作的含义。