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

《并行算法》课程总结与复习 H-\{w   
Ch1 并行算法基础 A 4W  
1.1 并行计算机体系结构 l_j<aCY?|  
    并行计算机的分类 jhEg#Q$  
    SISD,SIMD,MISD,MIMD； 4W//Oc@e  
    SIMD,PVP,SMP,MPP,COW,DSM X\$W'^np  
    并行计算机的互连方式 a@_
Cx  
    静态：LA(LC),MC,TC,MT,HC,BC,SE Sfoy8<j  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) C +?@iMh  
1.2 并行计算模型 ]htZ!; 8J  
    PRAM模型：SIMD-SM， E][{RTs  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW :2UC{_  
    SIMD-IN模型：SIMD-DM y'2kV6TtqD  
    异步APRAM模型：MIMD-SM :rs\ydDUF  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 >K|GLP  
    LogP模型：MIMD-DM，点到点通讯 D"] [&m  
1.3 并行算法的一般概念 kW2nrkF  
    并行算法的定义 2bn@:71`  
    并行算法的表示 Z/05 wB  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 ?'/5%f`  
    并行算法的WT表示：Brent定理、WT最优 r?yJ  
    加速比性能定律(略)
u g:G9vjQ  
    并行算法的同步和通讯(略) j.'"CU  
Ch2 并行算法的基本设计技术 =W
y`X0h  
2.1 并行算法的三种基本设计方法 F/od,w9_  
2.2 基本设计技术 vsz^B :j  
    平衡树方法：求最大值、计算前缀和 ?6YUb
;  
    倍增技术：表序问题、求森林的根 j]l}K*8(  
    分治策略：FFT分治算法 \;:@=9`  
    划分原理： 6p=xgk-q  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) ;1g-z]  
    流水线技术：五点的DFT计算，Systolic算法 YG1`%,OW`  
    加速级联(略) .n F  
    破对称技术 kbT-Oz  2  
Ch3 比较器网络上的排序和选择算法 #M^Yh?~%w  
3.1 Batcher归并和排序 x(zZqOed  
    0-1原理的证明(略) kmr 4cU5  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) ApJf4D<V  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) V\`="  
    Batcher排序网络：原理、种类和复杂性 hG;=ci3EE  
3.2 (m, n)-选择网络 f uNXY-;  
    分组选择网络 d~Ry>   
    平衡分组选择网络及其改进 Hh;6B!zb+  
Ch4 排序和选择的同步算法 _%Ld Ez  
4.1 一维线性阵列上的并行排序算法(略) JIKxY$GS  
4.2 二维Mesh上的并行排序算法 eL?si!ZL^  
    ShearSort排序算法 _%TeTNY#  
    Thompson&Kung双调排序算法及其计算示例 7c
]Ai  
4.3 Stone双调排序算法(略) UYrzsUjg&  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 ViT 5Jn7  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 Bg0cC  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 _O,ZeES  
Ch5 排序和选择的异步和分布式算法(略) y/6LMAI  
5.1 MIMD-CREW模型上的异步枚举排序算法 T>%ny\?tHW  
5.2 MIMD-TC模型上的异步快排序算法 5t?2B]  
5.3分布式k-选择算法 gbf=H8]  
Ch6 并行搜索 *9(1:N;#  
6.1 单处理器上的搜索(略) {1DYXKe
 
6.2 SIMD共享存储模型上有序表的搜索：算法 pDq_nx9  
6.3 SIMD共享存储模型上随机序列的搜索：算法 }V;]c~Q/H  
6.4 树连接的SIMD模型上随机序列的搜索：算法 Y(Ezw !a  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 <1.mm_pw  
Ch8 数据传输与选路 swL|Ff`$  
8.1 引言 9,eR=M]+:  
    信包传输性能参数 &)jZ|Q~  
    维序选路(X-Y选路、E-立方选路) 4H)"d  
    选路模式及其传输时间公式 %\&
dFwb  
8.2 单一信包一到一传输 p=gUcO8  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) wT yM9wz&  
8.3 一到多播送 ^(vd8&71  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 yvisoZX  
8.4 多到多播送 f.^w/ GJO/  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 T["(YFCByg  
8.5 贪心算法(书8.2) =W*`HV- w  
    二维阵列上的贪心算法 V<pjR@  
    蝶形网上的贪心算法 9W$)W  
8.6 随机和确定的选路算法(书8.3)(略) toJ&$HrE  
Ch12矩阵运算 ved Qwzh  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 <U pjAuG8  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 AI;=k  
12.3 矩阵向量乘法 mP[u[|]  
    带状划分的算法及其时间分析 ,0~TvJS  
    棋盘划分的算法及其时间分析 i%8 sy  
    Systolic算法(略) j~q`xv+
R  
12.4 矩阵乘法 x)L@xQ  
    简单并行分块算法 /Ql}jSKi  
    Cannon算法及其计算示例 l:f sZO4  
    Fox算法及其计算示例 \]%U?`A  
    DNS算法及其计算示例 5K{h)* *5  
    Systolic算法(略) EdpR| z  
Ch13 数值计算 'DQyB`V2y  
13.1 稠密线性方程组求解 n\
I xv  
    SIMD-CREW的上三角方程组回代算法 [=+/  
    SIMD-CREW上的Gauss-Jordan算法 (Lnh> '2  
    MIMD-CREW上的Gauss-Seidel算法 `f]O  
13.2 稀疏线性方程组的求解 W$S.?[
X  
    三对角方程组的奇偶规约求解法 uLF55:`<  
    Gauss-Seidel迭代法的红黑着色并行算法 h[T3WE  
13.3 非线性方程的求根(略) aK'r=NU
 
Ch14 快速傅立叶变换FFT 2-84  
14.1 快速傅里叶变换(FFT) `l#g`~L  
    离散傅里叶变换(DFT) 7ow1=%Q  
    串行FFT递归算法及其计算原理 ^h=kJR9  
    串行FFT蝶式计算及其蝶式计算流图 t/|^N t@XT  
14.2 DFT直接并行算法 6-"&jbvm  
    SIMD-MT上的并行DFT算法(略) 2|BE{91  
14.3 并行FFT算法 x{$NstGB  
    SIMD-MC上的FFT算法(略) v*3 :8 Y,  
    SIMD-BF上的FFT算法及其时间分析 O5 SX "A  
Ch15 图论算法  u:ISwAp  
15.1 图的并行搜索 m='OnTeOE  
    p-深度优先搜索及其计算示例 odDt.gQXU  
    p-宽深优先搜索及其计算示例  t2iFd?  
    p-宽度优先搜索及其计算示例 7Y/_/t~Y  
15.2 图的传递闭包 bxs@_fH  
    基于布尔矩阵乘积的算法原理 $G3P3y: [  
    计算示例 TL>e[PBO  
    SIMD-CC上的传递闭包算法 'mF}+v^  
15.3 图的连通分量 y+a&swd2(U  
    基于传递闭包的算法 }R^{<{KVJ  
    基于顶点合并的算法 wr`eBPu  
15.4 图的最短路径 x>cu<,e$d\  
    基于矩阵乘积的算法原理 %:lQ ~yn  
    计算示例 -IE;5f#e  
15.5 图的最小生成树  _ 0-YsD  
    SIMD-EREW模型上的Prim算法 g:HIiGN0Ic  
    算法的时间分析 Ch3##-  
Ch18 随机算法 EOL03N  
18.1 引言 rAWBuEU;!  
    基本知识：随机算法的定义、分类、重复性定律 9 wc=B(a|  
    时间复杂性度量 _wIAr  
    设计方法 uJQeZEe  
18.2 低度顶点部分独立集 NJ.kT uk  
    串行算法 Ks4TBi&J   
    随机并行算法及其正确性证明 ]Sh&8 #  
18.5 多项式恒等的验证 0/c4%+ Ln  
    基本原理和方法  u!(|y9p  
    矩阵乘积的验证原理 yDPek*#^"q  
18.8 格点逼近问题(略) bz 1\EkLL  
18.9 SAT问题的异步随机并行算法(略) {+!_; zzZ  
Ch20 模型与下界 Epx.0TA=t  
20.1不同的PRAM模型的相互模拟 _v-sb(* J  
    PRAM-EREW模拟PPRAM-CRCW }G]]0Oi2  
    PRAM-CRCW之间的模拟 jk~< si  
20.2下界 \o/oM,u  
    算法研究的两个方向：优化（上界）、可能性（下界） d<y B ~Y  
    Gates的工作 FK- >|  
    理想的PRAM模型与下界 ST{<G  
    PRAM模型的下界 -50|r;a  
20.3 NP完全理论导引(略) o^Ms(?K%t  
20.4 P完全理论(略)