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

《并行算法》课程总结与复习 pnx^a}|px  
Ch1 并行算法基础 "x;FE<I  
1.1 并行计算机体系结构 Y?K?*`Pkc1  
    并行计算机的分类 37?X@@Z=  
    SISD,SIMD,MISD,MIMD； )K l@dj  
    SIMD,PVP,SMP,MPP,COW,DSM 1/ j>|  
    并行计算机的互连方式 !UPB4I  
    静态：LA(LC),MC,TC,MT,HC,BC,SE A@d 2Ukv  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) bW/T}FND  
1.2 并行计算模型 S
yl9j]  
    PRAM模型：SIMD-SM， {hf_Xro&  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW rbv  
    SIMD-IN模型：SIMD-DM jJvd!,=)  
    异步APRAM模型：MIMD-SM !U2<\!_  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 `\ IaeMvo  
    LogP模型：MIMD-DM，点到点通讯 Vx5fQ mx  
1.3 并行算法的一般概念 %$)Sz[=  
    并行算法的定义 zZ51jA9x  
    并行算法的表示 Mkt_pr  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 6kR3[]:16v  
    并行算法的WT表示：Brent定理、WT最优 V^n=@CZT9C  
    加速比性能定律(略) |7Z}#eP//  
    并行算法的同步和通讯(略) qyy.&+  
Ch2 并行算法的基本设计技术 &F[N$6:v  
2.1 并行算法的三种基本设计方法 wNFx1u^/)  
2.2 基本设计技术 ]JmE(Y1(1  
    平衡树方法：求最大值、计算前缀和 `)w=@9B)"  
    倍增技术：表序问题、求森林的根 b rDyjh  
    分治策略：FFT分治算法 9-1 'jNV  
    划分原理： xa?auv!  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) 4pcIH5)z  
    流水线技术：五点的DFT计算，Systolic算法 ,}>b\(Lk  
    加速级联(略) T(cpU ,Q  
    破对称技术 O\]{6+$fm!  
Ch3 比较器网络上的排序和选择算法 1`Bhis
9X8  
3.1 Batcher归并和排序 D6yE/QeK4  
    0-1原理的证明(略) !T~uxeZ/;  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) @l_rB~  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) M#8_Qbvfk  
    Batcher排序网络：原理、种类和复杂性 Rf=- Q %  
3.2 (m, n)-选择网络 qI74a F  
    分组选择网络 fL'Ci;.;+  
    平衡分组选择网络及其改进 Z%I ' sWOd  
Ch4 排序和选择的同步算法 aqi] 5,  
4.1 一维线性阵列上的并行排序算法(略) +^rt48${ y  
4.2 二维Mesh上的并行排序算法 wIF
'|"  
    ShearSort排序算法 Wn2J]BH  
    Thompson&Kung双调排序算法及其计算示例 =6fJUy^M\  
4.3 Stone双调排序算法(略) }C=+Tn  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 CzDg?wb  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 <]`|HJoy  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 =C)2DWJ1  
Ch5 排序和选择的异步和分布式算法(略) Wh%@  
5.1 MIMD-CREW模型上的异步枚举排序算法 "%rU1/@#  
5.2 MIMD-TC模型上的异步快排序算法 ~qA\u5sB9@  
5.3分布式k-选择算法 7<?Aou  
Ch6 并行搜索 oHu7<r  
6.1 单处理器上的搜索(略)  [cfXcl  
6.2 SIMD共享存储模型上有序表的搜索：算法 X:(t,g*7  
6.3 SIMD共享存储模型上随机序列的搜索：算法 P}!pmg6V  
6.4 树连接的SIMD模型上随机序列的搜索：算法 ^'b\OUty-  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 rPifiLl A>  
Ch8 数据传输与选路 Orlf5{P  
8.1 引言 OZ<fQf.Gh}  
    信包传输性能参数 +KP&D.wIo  
    维序选路(X-Y选路、E-立方选路) ).MV1@s  
    选路模式及其传输时间公式 uUv^]B 8GM  
8.2 单一信包一到一传输 S'IQbH
z*  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 3#`Sk`z<  
8.3 一到多播送 9N<TJp,q  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 %e/L .#0  
8.4 多到多播送 Z
,,qmwd  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 rGQ([e  
8.5 贪心算法(书8.2) *Oh]I|?  
    二维阵列上的贪心算法 lBG" COu  
    蝶形网上的贪心算法 @@6c{r^P  
8.6 随机和确定的选路算法(书8.3)(略) !qs3fe<uh"  
Ch12矩阵运算 !~}@Eoii4  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 Uee$5a>(  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 ~8lB#NuN  
12.3 矩阵向量乘法 W3B:)<f  
    带状划分的算法及其时间分析 0P4g6t}e  
    棋盘划分的算法及其时间分析 DC'L-]#<  
    Systolic算法(略) lMjeq.5nP  
12.4 矩阵乘法 !<0 `c  
    简单并行分块算法 fvV5G,lD3h  
    Cannon算法及其计算示例 }I~)o!N%7  
    Fox算法及其计算示例 $69d9g8-(!  
    DNS算法及其计算示例 U1=\ `)u;  
    Systolic算法(略) \8Yv}wQ  
Ch13 数值计算 9f3rMPVh(  
13.1 稠密线性方程组求解 -EWC3,3  
    SIMD-CREW的上三角方程组回代算法 SA,+oq(  
    SIMD-CREW上的Gauss-Jordan算法 %$+bO/f  
    MIMD-CREW上的Gauss-Seidel算法 FOSC#W9E  
13.2 稀疏线性方程组的求解 ] N7(<EV/  
    三对角方程组的奇偶规约求解法 M4L<u,\1s  
    Gauss-Seidel迭代法的红黑着色并行算法 '.t{\  
13.3 非线性方程的求根(略) 5Ln !>,  
Ch14 快速傅立叶变换FFT 7k#0EhN1>  
14.1 快速傅里叶变换(FFT) LP//\E_]  
    离散傅里叶变换(DFT) 8 v<*xy  
    串行FFT递归算法及其计算原理 249DAjn+  
    串行FFT蝶式计算及其蝶式计算流图 Qs8Rb]%|  
14.2 DFT直接并行算法 7_
5-gtD  
    SIMD-MT上的并行DFT算法(略) Ev1gzHd!i  
14.3 并行FFT算法 m/aA q8  
    SIMD-MC上的FFT算法(略) Lz`_&&6  
    SIMD-BF上的FFT算法及其时间分析 tjcG^m} _  
Ch15 图论算法 ,TQ;DxB}=E  
15.1 图的并行搜索 [LKzH!  
    p-深度优先搜索及其计算示例 &nwk]+,0W#  
    p-宽深优先搜索及其计算示例 I\$?'q>  
    p-宽度优先搜索及其计算示例 0Q:l,\lY  
15.2 图的传递闭包 _?;74VWA  
    基于布尔矩阵乘积的算法原理 <
d$t*vnq  
    计算示例 #8a k=lL  
    SIMD-CC上的传递闭包算法 G,,f' >  
15.3 图的连通分量 \&^U9=uq  
    基于传递闭包的算法 +Al*MusS  
    基于顶点合并的算法 U/ >l>J
5  
15.4 图的最短路径 *~8g:;u  
    基于矩阵乘积的算法原理 >$;,1N $bd  
    计算示例 \kC'y9k  
15.5 图的最小生成树 \qB.>f"%p|  
    SIMD-EREW模型上的Prim算法 GT-ONwVDq  
    算法的时间分析 ~f?brQ?  
Ch18 随机算法 FdS'0#$  
18.1 引言 #e&LyYx4  
    基本知识：随机算法的定义、分类、重复性定律 7O'u5N  
    时间复杂性度量 =wFl(Q6J  
    设计方法 hF9y^Hx4  
18.2 低度顶点部分独立集 p+^K$w^Cs  
    串行算法 Ny]]L  
    随机并行算法及其正确性证明 /7K7o8g  
18.5 多项式恒等的验证 GCp90  
    基本原理和方法 v
'SqH,=d  
    矩阵乘积的验证原理 a #+;BH1  
18.8 格点逼近问题(略) 6Bn
}W ?  
18.9 SAT问题的异步随机并行算法(略) 8hZc#b;  
Ch20 模型与下界 r ['zp=9  
20.1不同的PRAM模型的相互模拟 @Qd5a(5WM  
    PRAM-EREW模拟PPRAM-CRCW H=*2A!O[_  
    PRAM-CRCW之间的模拟 Fhs/<w-  
20.2下界 )H%RwV#  
    算法研究的两个方向：优化（上界）、可能性（下界） vw/GAljflu  
    Gates的工作 [q(}~0{"-  
    理想的PRAM模型与下界 VoNk.h"T  
    PRAM模型的下界 4&H&zST//m  
20.3 NP完全理论导引(略) Q8NrbMrl  
20.4 P完全理论(略)