中国科学技术大学并行算法期末考试范围

《并行算法》课程总结与复习 UM|GX  
Ch1 并行算法基础 AA>5h<NM  
1.1 并行计算机体系结构 px//q4U  
    并行计算机的分类 gW/H#T,  
    SISD,SIMD,MISD,MIMD； Ct}"o  
    SIMD,PVP,SMP,MPP,COW,DSM <'P|g  
    并行计算机的互连方式 xBgf)'W_Z  
    静态：LA(LC),MC,TC,MT,HC,BC,SE R#Bt!RNZ  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) ,yV pB)IQ  
1.2 并行计算模型 \lKQDct. -  
    PRAM模型：SIMD-SM， w2+RX-6Ie  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW ^ /
f*5k  
    SIMD-IN模型：SIMD-DM &CUkR
6  
    异步APRAM模型：MIMD-SM I=(O,*+PQ  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 et9 c<'  
    LogP模型：MIMD-DM，点到点通讯 A: 0] n  
1.3 并行算法的一般概念 J SGUl4N  
    并行算法的定义
`Z%XA>  
    并行算法的表示 )B}]0`z:P  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 |I OTW=>  
    并行算法的WT表示：Brent定理、WT最优 
}Ecm  
    加速比性能定律(略) 1"v;w!uh  
    并行算法的同步和通讯(略)  t8?+yG;  
Ch2 并行算法的基本设计技术 c#HocwP@  
2.1 并行算法的三种基本设计方法 t:M>&r:BL  
2.2 基本设计技术 b]|7{yMV  
    平衡树方法：求最大值、计算前缀和 FfD2 &(-R  
    倍增技术：表序问题、求森林的根 }DZkCzK  
    分治策略：FFT分治算法 E>4 \9  
    划分原理： mY`b|cS3p$  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) 8i:b~y0  
    流水线技术：五点的DFT计算，Systolic算法 IgFz [)  
    加速级联(略) ~)ByARao=  
    破对称技术 G53!wIW2:  
Ch3 比较器网络上的排序和选择算法 -C8awtbC  
3.1 Batcher归并和排序 .S5&MNE  
    0-1原理的证明(略) D~mGv1t"  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) 7XwFO0==  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) [6/%ynlP  
    Batcher排序网络：原理、种类和复杂性 
r;Dl  
3.2 (m, n)-选择网络 `mWg$e,  
    分组选择网络 D!@c,H  
    平衡分组选择网络及其改进 L3kms6ch  
Ch4 排序和选择的同步算法 UhEnW8^bz1  
4.1 一维线性阵列上的并行排序算法(略) kwyvd`J8  
4.2 二维Mesh上的并行排序算法 /\=g; o'  
    ShearSort排序算法 W5yqnjK $4  
    Thompson&Kung双调排序算法及其计算示例 U#Z}a d?VX  
4.3 Stone双调排序算法(略) /Wj9Stj5  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 ~Aq UT]l  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 r-!8in2  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 XS1>ti|<  
Ch5 排序和选择的异步和分布式算法(略) U,+=>ns>  
5.1 MIMD-CREW模型上的异步枚举排序算法 zb9$
 
5.2 MIMD-TC模型上的异步快排序算法 '7E?|B0],  
5.3分布式k-选择算法 QiZThAe  
Ch6 并行搜索
dwmj *
+  
6.1 单处理器上的搜索(略) IRcZyry  
6.2 SIMD共享存储模型上有序表的搜索：算法 .IG(Y!cB  
6.3 SIMD共享存储模型上随机序列的搜索：算法 |#MA?oz3T  
6.4 树连接的SIMD模型上随机序列的搜索：算法 un..UU4  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 OP>'<FK  
Ch8 数据传输与选路 3 D+dM0wM  
8.1 引言 Ao=.=0os  
    信包传输性能参数 //AS44^IS  
    维序选路(X-Y选路、E-立方选路) Gh@QR`xxc  
    选路模式及其传输时间公式 q,+d\-+  
8.2 单一信包一到一传输 P/0n) Q  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) s K s D  
8.3 一到多播送 ^S[Mg6J  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 fpzC#  
8.4 多到多播送 ku?i[Th  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 CFn!P;.!  
8.5 贪心算法(书8.2) !R4`ihi1  
    二维阵列上的贪心算法 uZg Kex;c  
    蝶形网上的贪心算法 rbs:q
La%  
8.6 随机和确定的选路算法(书8.3)(略) DmPp&  
Ch12矩阵运算 M"5,8Q`PkI  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 {3!v<CY'  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 6x6PP}IX  
12.3 矩阵向量乘法 ?!8M I,c/  
    带状划分的算法及其时间分析 p]IF=~b  
    棋盘划分的算法及其时间分析 FhS:.  
    Systolic算法(略) Oe*emUX7  
12.4 矩阵乘法 De\&r~bTW9  
    简单并行分块算法 hQPiGIs
  
    Cannon算法及其计算示例 X>=`{JS1  
    Fox算法及其计算示例 WHMt$W}%  
    DNS算法及其计算示例
TD
k'  
    Systolic算法(略) )<t5' +d%  
Ch13 数值计算
eDgRYa9\  
13.1 稠密线性方程组求解 `/8Dmg  
    SIMD-CREW的上三角方程组回代算法 E"nIC,VZ  
    SIMD-CREW上的Gauss-Jordan算法 iLNKC'  
    MIMD-CREW上的Gauss-Seidel算法 &}Cm9V  
13.2 稀疏线性方程组的求解 [
n44;  
    三对角方程组的奇偶规约求解法 ab: yH ')  
    Gauss-Seidel迭代法的红黑着色并行算法 uL\ B[<:  
13.3 非线性方程的求根(略) kW3V"twx  
Ch14 快速傅立叶变换FFT 1c8J yp  
14.1 快速傅里叶变换(FFT) (Xi?Y/  
    离散傅里叶变换(DFT) #Huvn4x  
    串行FFT递归算法及其计算原理 nK)U.SZ  
    串行FFT蝶式计算及其蝶式计算流图 {.K>9#^m  
14.2 DFT直接并行算法 Xk8+m>   
    SIMD-MT上的并行DFT算法(略) 3Gubq4r  
14.3 并行FFT算法 xlZ"F  
    SIMD-MC上的FFT算法(略) ^y]CHr  
    SIMD-BF上的FFT算法及其时间分析 Ep>3%{V  
Ch15 图论算法 w$MFCJ:p&  
15.1 图的并行搜索 `lX |yy"  
    p-深度优先搜索及其计算示例 <Wn={1Ts"  
    p-宽深优先搜索及其计算示例 0&}
"!)  
    p-宽度优先搜索及其计算示例 w]J9Kv1)-  
15.2 图的传递闭包 e)]9u$x  
    基于布尔矩阵乘积的算法原理
BT.;l I  
    计算示例 _~ZNX+4  
    SIMD-CC上的传递闭包算法 o{f|==<t3#  
15.3 图的连通分量 [p^N].K$  
    基于传递闭包的算法 Ue^2H[zs-  
    基于顶点合并的算法 >~8;H x].d  
15.4 图的最短路径 (LbAP9Zj#f  
    基于矩阵乘积的算法原理 YB qu7
&  
    计算示例 KCu@5`p  
15.5 图的最小生成树 VJmX@zX9  
    SIMD-EREW模型上的Prim算法 MB06=N  
    算法的时间分析 PY- 1 oP  
Ch18 随机算法 t{Ck"4Cg  
18.1 引言 eM Ym@~4  
    基本知识：随机算法的定义、分类、重复性定律 {|nm0vg`A  
    时间复杂性度量 PLD6Ug  
    设计方法 HI)MBrj;r  
18.2 低度顶点部分独立集 -e0C Bp  
    串行算法 x(pq!+~K  
    随机并行算法及其正确性证明 g S xK9P  
18.5 多项式恒等的验证 B7BXS*_b  
    基本原理和方法 `]%\Y>(a}  
    矩阵乘积的验证原理 9c9FC  
18.8 格点逼近问题(略) V;0{o  
18.9 SAT问题的异步随机并行算法(略) |TM&:4D]^  
Ch20 模型与下界 WwG +Xa  
20.1不同的PRAM模型的相互模拟 3yg22y&l  
    PRAM-EREW模拟PPRAM-CRCW ?|!167/O  
    PRAM-CRCW之间的模拟 ^T*^L=L_(  
20.2下界 C/V{&/5w  
    算法研究的两个方向：优化（上界）、可能性（下界） NJK?5{H'  
    Gates的工作 =qPk'n9i8  
    理想的PRAM模型与下界 f[v~U<\R  
    PRAM模型的下界 [GKSQt{)  
20.3 NP完全理论导引(略) FD>j\  
20.4 P完全理论(略)