并行程序设计 Chapter4要点.ppt

CHAPTER 4 Partitioning and Divide-and-Conquer Strategies 4.1 Partitioning 划分 1. 划分策略 Partitioning Strategies 2. 分治 Divide and Conquer 3. M维树状分治 M-ary Divide and Conquer 4.2 Examples 1. Sorting Using Bucket Sort 2. Numerical Integration 3. N-Body Problem 4.1 Partitioning Partitioning simply divided the problem into separate parts and each part is computed separately. Divide and Conquer is characterized by dividing problem into subproblems of same form as larger problem. Further divisions into still smaller sub-problems,usually done by recursion. 4.1.1 Partitioning Strategies data partitioning or domain decomposition 数据划分 Every processor executes the same task on different data parallelly. functional decomposition 功能划分 Divide the whole program into some separate parts in function. Every processor executes the different task on different data parallelly. Partitioning example : 数组求和(找出一组数中的最大、最小值、某个字符（串）出现次数。） 4.1.1 Partitioning Strategies 4.1.1 Partitioning Strategies 1、基于send/recv的并行程序 master: s=n/m; /*每个处理器计算s个数之和*/ for(i=0,x=0; im; i++, x=x+s) send(numbers[x], s, Pi); sum=0; for(i=0; im; i++){ recv(part_sum, Pany); sum+=part_sum; } 4.1.1 Partitioning Strategies slave: recv(numbers, s, Pmaster); part_sum=0; for(i=0; is; i++) part_sum+=numbers[i]; send(part_sum,Pmaster); 4.1.1 Partitioning Strategies 2、基于bcast的并行程序 master: s=n/m; bcast(numbers, n, Pslave_group); sum=0; for(i=0; im; i++){ recv(part_sum, Pany); sum+=part_sum; } 4.1.1 Partitioning Strategies slave: bcast( numbers, n, Pmaster); start=slave_number*s; end=start+s; part_sum=0; for(i=start; iend; i++) part_sum+=numbers[i]; send(part_sum,Pmaster); 4.1.1 Partitioning Strategies 3、基于scatter/reduce的并行程序 master: s=n/m; root=Pmaster; scatter(numbers, s, Pgroup, root); reduce(sum, s, ADD, Pgroup, root); 4.1.1 Partitioning Strategies slave: scatter(numbers, s, Pgroup, root); /* add s 个数之和存于part_s