并行算法设计与分析6.pptVIP

Y.Xu Copyright USTC 主要内容 6.1 单处理器上的有哪些信誉好的足球投注网站 6.2 SIMD共享存储模型上有序表的有哪些信誉好的足球投注网站 6.3 SIMD共享存储模型上随机序列的有哪些信誉好的足球投注网站 6.4 树连接的SIMD模型上随机序列的有哪些信誉好的足球投注网站 6.5 网孔连接的SIMD模型上随机序列的有哪些信誉好的足球投注网站 6.1 单处理器上的有哪些信誉好的足球投注网站 1. 随机序列 顺序查找，时间O(n) 2. 有序序列 二分查找，时间O(logn) 主要内容 6.1 单处理器上的有哪些信誉好的足球投注网站 6.2 SIMD共享存储模型上有序表的有哪些信誉好的足球投注网站 6.3 SIMD共享存储模型上随机序列的有哪些信誉好的足球投注网站 6.4 树连接的SIMD模型上随机序列的有哪些信誉好的足球投注网站 6.5 网孔连接的SIMD模型上随机序列的有哪些信誉好的足球投注网站 6.2 SIMD共享存储模型上有序表的有哪些信誉好的足球投注网站 6.2.1 SIMD-EREW上的有哪些信誉好的足球投注网站 算法6.3：并行二分查找 输入：有序序列S=(s1,s2,…,sn)和x 输出：若sk=x, 则输出k，否则输出0 begin ①将x播送到N个处理器中； //时间O(logN) ②将S分成N个子段，S(i)={s(i-1)n/N+1,…,sin/N}, i=1~N 含播送N操作; //时间O(logN) ③Pi在S(i)中用二分查找； //时间O(log(n/N)) ④某个Pi找到sk=x，则返回k, 否则返回0; //O(logN) end 时间: O(log(n/N))+O(logN)+ O(logN)=O(logn) 6.2 SIMD共享存储模型上有序表的有哪些信誉好的足球投注网站 6.2.2 SIMD-CREW上的有哪些信誉好的足球投注网站 方法1：同SIMD-EREW; 方法2: N+1分查找; 算法：并行N+1分查找 begin 1. Pi将x与sim进行比较，其中 ； 1.1 若sim=x, 则返回im 1.2 若xsim, 则标记ci=左 1.3 若xsim, 则标记ci=右 2. 取可能含x的子段 2.1 若c1=左，则取S(0)=(s1,..,sm-1)，递归并行有哪些信誉好的足球投注网站； 2.2 若cN=右，则取S(N)=(sNm+1,..,sn)，递归并行有哪些信誉好的足球投注网站； 2.3 必存在唯一的i0, 使ci0=右，ci0+1=左,则取S(i0)=(si0*m+1,..,s(i0+1)m)，递归并行有哪些信誉好的足球投注网站 end 6.2 SIMD共享存储模型上有序表的有哪些信誉好的足球投注网站 6.2.2 SIMD-CREW上的有哪些信誉好的足球投注网站 示例：S={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}, x=7, n=16, p(n)=2 第1次查找： 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 m=6 第2次查找： 7,8,9,10,11 m=2 第3次查找： 7 (找到) 6.2 SIMD共享存储模型上有序表的有哪些信誉好的足球投注网站 6.2.2 SIMD-CREW上的有哪些信誉好的足球投注网站 并行N+1分查找算法时间复杂性分析 定理6.1 给定长度为n的有序表和处理器数N，则SIMD-CREW上N+!分有哪些信誉好的足球投注网站算法至少需要 次比较。这里g实际是满足n≤(N+1)g-1的最小整数。 证: 首先证明g次比较一定能找到。对g作归纳 (1)g=1，n≤(N+1)1-1=N, 显然1次可找到； (2)假设g-1成立。下证：长度为n≤(N+1)g-1的有序表，g次比较能找到。 第1次比较: Pi将x与sj比较, 其中j=im=i(N+1)g－1, 如下图： 若x找到，进行了1次比较； 若未找到，确定出在某一子段内继续查找，子段长不超过(N+1)g－1