分布式计算复习题重点.docVIP

课外作业 用MPI编写BucketSort 程序 假设数据为统计均匀分布数据;假设每一处理机为一个装数据的桶(Bucket). 将数据平均分散到各处理机; 各处理机同时求最大与最小值; 同步操作后; 通过reduce操作求全局最大与最小值; 将最大、小值广播到各处理机中; 设L=MAX-MIN,则第i处理机上的局部数据范围可以是(MIN+L*i/n)~MIN+L*(i+1)/n); 各处理机根据数据所落的范围送到相应的各处理机中; 同步操作; 各处理机分别排序; 最后按处理机编号顺序排列的数据即为全局排序的结果; 要求:数据为分布大致均匀,否则可能有的处理机中没有相应的数据,导致负载不平衡!  The Review of Parallel Process The Sieve of Primes (8 —10) The Sequential algorithms (semigroup, prefix computation, routing, broadcasting, sorting) (20,21,23) Maximum-finding, Computing prefix sum on linear arrays (24,25) Odd-even sort on linear array (27) Finding the rank of each 1s in a list of 0s and 1s (29) Packet routing on a tree (30) Find maximum value, computing prefix sum and shearsort on 2D mesh (33) SIMD vs. MIMD Architecture (49-52) PRAM cycle (53) PRAM submodel (61-62) Data broadcasting in EREW PRAM (63-65) Semigroup computation in CRCW PRAM (66) Parallel Prefix computation (68,69) Matrix multiplication in PRAM (72,73) Sequential Rank-based selection(77-79) A parallel select algorithm and a selection-based sorting algorithm (80-82) Parallel radix sort (84) Some low-cast sorting network (94) Batcher sorting networks (97-99) Searching and Dictionary Operations(108-109) Mesh-Connected Computer (125-126) Shearsort algorithm (128-130) Recursive Sorting algorithm (132-133) Routing Operation (140) Routing multiple packet on a linear array (142) Data routing on a 2-D array (143) Greedy Routing algorithm (144-145) sorting on a 3D mesh(p172) Mesh with a global bus and semigroup computation(p179,180) embedding concept(195) Embeding of array and tree(196) Bitonic sorting on a hypercube(211 Dimension order routing(215-217)