例:n=8, p=8, C01~C08为前缀和
PRAM求前缀和算法
sequence T
SCAN(sequence T x, ⊕: T ×T →T )
8个
元
素
的
数
据
流
分
析n个元素的列表L,求出每个元素在L
rank(k)可视为元素k至表尾的距离;
(1)p[a]=b, p[b]=c, p[c]=d, p[d]=e,
r[a]=r[b]=r[c]=r[d]=r[e]=r[f]=1, r[g]=0
(2)p[a]=c, p[b]=d, p[c]=e, p[d]=f, p[e]=p[f]=p[g]=g
r[a]=r[b]=r[c]=r[d]=r[e]=2, r[f]=1, r[g]=0
如果k的后继不等于k的后继之后继,则
(i) distance[k]= distance[k]+ distance[p[k]]
rank[k]=distance[k] //O(1)运行时间:t(n)=O(logn) p(n)=n
P157算法6.11
运行时间:t(n)=O(logn) W(n)=O(nlogn)
分治设计技术
6.2.1 并行分治设计步骤
比较器排序网络
Time Comlexity
Phase b中,由於各處理器平行進行Quicksort,故所需時間為O(k log k),其中k=n/p。
Phase d中,對p2個資料做排序需要O(p2log p2)的時間。在Phase f中各個處理器對本地排序好的list做p-1次binary search(list的長度不大於k),所以總共需要的時間為O(p2log p2+ p log k)。
在Phase h中,各處理器所需要merge的大小不會超過2k,故Phase h可在O(2k log p)時間完成。
將上述结果相加,所需時間為O(k log k + k log p + p log k + p2log p2)。當n≧p3時,近似於O(k log k)=
O((n/p)log n),顯然是cost optimal的。
林育德
(1)归并过程: 设有序序列A[1..n]和B[1..m]
j[i]=rank(b ilogm :A)为b ilogm 在A中的位序,即A中小于等于b ilogm 的元素个数(2)例:A=(4,6,7,10,12,15,18,20), B=(3,9,16,21) n=8, m=4
=>logm=log4=2
=> j[1]=rank(b :A)=rank(b :A)=rank(9:A)=3, j[2]=: 3, 9 B : 16, 21
: 4, 6, 7 A : 10, 12, 15, 18, 20 A和B归并转化为(A 0, B 并行算法的基本设计技术划分设计技术分治设计技术平衡树设计技术倍增设计技术流水线设计技术
P1,1P1,2P1,3P1,4 P2,1P2,2P2,3P2,4 P3,1P3,2P3,3P3,4 P4,1P4,2P4,3P4,4
第一次大作业
1. 3D-Mesh上的排序算法,分别给出算法的原理描述和
具体描述,并进行时间复杂度分析;
设计超立方体上的并行排序算法,分别给出算法的原理描述和具体描述,并进行时间复杂度分析;
3. 编程实现PSRS算法,给出带注解代码和运行测试结果;
4. 给出一个算法例子,该算法能够体现出模型的全部
内容,并给出这个算法的原理描述、具体描述以及分析结果。