【图文】第十六章 并行算法

1、 16.7 MIMD-SM上的异步并行求和算法 上的异步并行求和算法 假设共享存储器多处理机系统有P个处理器，其编号为 ， 假设共享存储器多处理机系统有 个处理器，其编号为P1， 个处理器 P2，Pp-1,由一个全局变量 由一个全局变量total-sum存储数据的总和， 存储数据的总和， ， ， 由一个全局变量 存储数据的总和 每个处理器Pi分配一个并发进程都有各自的局部变量 分配一个并发进程都有各自的局部变量local每个处理器 分配一个并发进程都有各自的局部变量 sum，该局部变量是用来存储部分数据的子和，然后将所求 ，该局部变量是用来存储部分数据的子和， 得的local-sum加到全局变

2、量 加到全局变量total-sum中。 得的 加到全局变量 中 很明显可以看出此算法存在存储冲突。 很明显可以看出此算法存在存储冲突。假如说当一个进程把 所求得的部分数据子和local-sum加到全局变量 加到全局变量total-sum中 所求得的部分数据子和 加到全局变量 中 时有另一个进程也要把部分的数据子和加进去， 时有另一个进程也要把部分的数据子和加进去，那么就会产 生资源冲突，这种冲突会很频繁的发生， 生资源冲突，这种冲突会很频繁的发生，因为全局变量总和 的相加操作需要异步进行。 的相加操作需要异步进行。 我们通常所用的解决冲突的办法是当要访问全局变量时先首 先对它进行加锁，使得其他

3、进程无法同时使用这个资源， 先对它进行加锁，使得其他进程无法同时使用这个资源，当 访问结束后立即解锁以免耽误其他进程对其进行的操作。 访问结束后立即解锁以免耽误其他进程对其进行的操作。 MIMD-SM机器上的异步并行求和其实是一个进程和 个并发 机器上的异步并行求和其实是一个进程和P个并发 机器上的异步并行求和其实是一个进程和 子进程组成，每个子进程分别求出分配给他的n/p个数据的子 子进程组成，每个子进程分别求出分配给他的 个数据的子 和。 2011-5-24 36 16.7 MIMD-SM上的异步并行求和算法 上的异步并行求和算法 算法16.5 MIMD-SM机器上的异步并行求和算法 算法

4、 机器上的异步并行求和算法 begin /开始主进程 开始主进程 total_sum=0; for i=1 to p do in parallel begin sub_sum(i,local_sum; lock(total_sum; /对全局变量 对全局变量total_sum加锁 对全局变量 加锁 total _sum= total _sum+local_sum; unlock(total_sum; end end procedure sub_sum(i,local_sum /并发子进程 并发子进程 begin local_sum=0； ； for j=i to n step p do loc

5、al_sum=local_sum+xj; return local_sum; end 2011-5-24 37 16.7 MIMD-SM上的异步并行求和算法 上的异步并行求和算法 上述算法在最坏情况下的运算时间， 上述算法在最坏情况下的运算时间，该运算时间有以下几部 分组成： 分组成： （1）生成进程所需要的时间：生成 个子进程需要时间为 ）生成进程所需要的时间：生成p个子进程需要时间为 O(p; （2）局部求和所需要的时间：每个子进程都需要对 ）局部求和所需要的时间：每个子进程都需要对n/p个数 个数 据求和，所以局部求和时间为O(n/p; 据求和，所以局部求和时间为 （3）求取总和所需要的时间：因为在任何一个时间只能由一 ）求取总和所需要的时间： 个进程执行总和的操作，相当于p个处理器串行地对全局变量 个进程执行总和的操作，相当于 个处理器串行地对全局变量 total-sum进行加锁、解锁操作，所以需要的时间为 进行加锁、 进行加锁 解锁操作，所以需要的时间为O(p; （4）进程同步所需要的时间：进程是异步并行执行的，所以 ）进程同步所需要的时间：进程是异步并行执行的， 在最坏情况下p个并发进程同步结束需要的时间为 个并发进程同步结束需要的时间为O(p。 在最坏情况下 个并发进程同步结束需要的时间为 。 因此上述算法在最坏情况下的运算时