并行程序设计Chapter4讲解.ppt

CHAPTER 4 Partitioning and Divide-and-Conquer Strategies;4.1 Partitioning;4.1.1 Partitioning Strategies;4.1.1 Partitioning Strategies;m次接收，每次接收1个部分和，故 Tcomm2=m(tstartup+ tdata);4.1.1 Partitioning Strategies;4.1.1 Partitioning Strategies;4.1.1 Partitioning Strategies;4.1.1 Partitioning Strategies;4.1.1 Partitioning Strategies;4.1.1 Partitioning Strategies;当n很大时，S接近m; 当n小时，S很低，m越大，S越低。;4.1.2 Divide and Conquer;4.1.2 Divide and Conquer;4.1.2 Divide and Conquer;4.1.2 Divide and Conquer;4.1.2 Divide and Conquer;4.1.2 Divide and Conquer;4.1.2 Divide and Conquer;4.1.2 Divide and Conquer;4.1.2 Divide and Conquer;4.1.3 M-ary Divide and Conquer;4.1.3 M-ary Divide and Conquer;4.2 Examples;4.2.1 Sorting Using Bucket Sort;4.2.1 Sorting Using Bucket Sort;4.2.1 Sorting Using Bucket Sort;并行算法一： 为每个桶分配一个处理器;4.2.1 Sorting Using Bucket Sort;4.2.1 Sorting Using Bucket Sort;并行执行时间分为： （1）将分割的每部分数据分发到各处理器 点对点：m(tstartup+(n/m)tdata)=m tstartup+ntdata 散播： tstartup+ntdata （2) 将每个处理器拥有的n/m个数据分到各小 桶中 n/m （3) 每个处理器中(m-1)个小桶中的数据发送 到其它(m-1)个处理器中. 各处理器发送时间不重叠 m(m-1)(tstartup+(n/m2)tdata) 各处理器发送时间重叠 (m-1)(tstartup+(n/m2)tdata) (4)每个大桶中数据排序 (n/m)log(n/m);4.2.2 Numerical Integration;4.2.2 Numerical Integration;4.2.2 Numerical Integration;4.2.2 Numerical Integration;4.2.2 Numerical Integration;4.2.3 N-Body Problem;4.2.3 N-Body Problem;4.2.3 N-Body Problem;4.2.3 N-Body Problem;4.2.3 N-Body Problem;4.2.3 N-Body Problem;4.2.3 N-Body Problem;SUMMARY;