《并行算法的设计与分析》6

《《并行算法的设计与分析》6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ParallelAlgorithmsChapter6ParallelSearch2021/6/11Y.XuCopyrightUSTC主要内容6.1单处理器上的搜索6.2SIMD共享存储模型上有序表的搜索6.3SIMD共享存储模型上随机序列的搜索6.4树连接的SIMD模型上随机序列的搜索6.5网孔连接的SIMD模型上随机序列的搜索2021/6/11Y.XuCopyrightUSTC6.1单处理器上的搜索1.随机序列顺序查找，时间O(n)2.有序序列二分查找，时间O(logn)2021/6/11Y.XuCopyrightUSTC主要内容

2、6.1单处理器上的搜索6.2SIMD共享存储模型上有序表的搜索6.3SIMD共享存储模型上随机序列的搜索6.4树连接的SIMD模型上随机序列的搜索6.5网孔连接的SIMD模型上随机序列的搜索2021/6/11Y.XuCopyrightUSTC6.2SIMD共享存储模型上有序表的搜索6.2.1SIMD-EREW上的搜索算法6.3：并行二分查找输入：有序序列S=(s1,s2,…,sn)和x输出：若sk=x,则输出k，否则输出0begin①将x播送到N个处理器中；//时间O(logN)②将S分成N个子段，S(i)={s(i-1)n/N+1

3、,…,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)2021/6/11Y.XuCopyrightUSTC6.2SIMD共享存储模型上有序表的搜索6.2.2SIMD-CREW上的搜索方法1：同SIMD-EREW;方法2:N+1分查找;算法：并行N+1分查找begin1.Pi将x与sim进行比较，其中；1.1若sim=x

4、,则返回im1.2若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)，递归并行搜索end2021/6/11Y.XuCopyrightUSTC6.2SIMD共享存储模型上有序表的搜索6.2.2SIMD-CREW上的搜索示例：S={1,2,3,4,5,

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,16m=6第2次查找：7,8,9,10,11m=2第3次查找：7(找到)2021/6/11Y.XuCopyrightUSTC6.2SIMD共享存储模型上有序表的搜索6.2.2SIMD-CREW上的搜索并行N+1分查找算法时间复杂性分析定理6.1给定长度为n的有序表和处理器数N，则SIMD-CREW上N+!分搜索算法至少需要次比较。这里g实际是满足n≤(N+1)g

6、-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-1由归纳假设，在每一子段中查找至多需g-1次比较，所以g次一定能在S中找到。2021/6/11Y.XuCopyrightUSTC6.2SIMD共享存储模型上有序表的搜索6.2.

7、2SIMD-CREW上的搜索并行N+1分查找算法时间复杂性分析其次再证至少需要g次比较。比较1次之后，各子段的长度为所以，经过g次比较之后，剩下的序列长度至少为要完成搜索，则至少应有==>g≥log(n+1)/log(N+1)综上，证毕。由定理知：并行N+1分查找算法时间:t(n)=O(logN+1(n+1))成本:c(n)=O(NlogN+1(n+1))2021/6/11Y.XuCopyrightUSTC主要内容6.1单处理器上的搜索6.2SIMD共享存储模型上有序表的搜索6.3SIMD共享存储模型上随机序列的搜索6.4树连接的S

8、IMD模型上随机序列的搜索6.5网孔连接的SIMD模型上随机序列的搜索2021/6/11Y.XuCopyrightUSTC6.3SIMD共享存储模型上随机序列的搜索6.3.1SIMD-SM上的搜索算法6.3：并行顺序查找输入：S=(s