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

《并行算法》课程总结与复习 LIID(s!bX  
Ch1 并行算法基础 _N`.1Dl%Q  
1.1 并行计算机体系结构 [bh?p+V  
    并行计算机的分类 _KH91$iW8m  
    SISD,SIMD,MISD,MIMD； Sb`[+i'`  
    SIMD,PVP,SMP,MPP,COW,DSM :'p)xw4K|  
    并行计算机的互连方式 G8M~}I/)  
    静态：LA(LC),MC,TC,MT,HC,BC,SE %OBW/Ti  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) &BPYlfB1  
1.2 并行计算模型 DN2 ]Y'  
    PRAM模型：SIMD-SM， ly%^\
jW  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW N1'`^a
y$  
    SIMD-IN模型：SIMD-DM w0BphK[  
    异步APRAM模型：MIMD-SM MLdwf}[  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 p'h'Cz  
    LogP模型：MIMD-DM，点到点通讯 `jE[Xt"@  
1.3 并行算法的一般概念 UXct+l  
    并行算法的定义 hV7EjQp  
    并行算法的表示 #*.!J zOg  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 }WsPuo  
    并行算法的WT表示：Brent定理、WT最优 Dmh$@Uu#F  
    加速比性能定律(略) -gs I:-Xo  
    并行算法的同步和通讯(略) gNZwD6GMe?  
Ch2 并行算法的基本设计技术 ']nI
a7  
2.1 并行算法的三种基本设计方法 oKn$g[,SJh  
2.2 基本设计技术 N?@^BZ  
    平衡树方法：求最大值、计算前缀和 7\UHADr  
    倍增技术：表序问题、求森林的根 H(^Ehv>  
    分治策略：FFT分治算法 v^&HZk= (  
    划分原理： 'Dfs&sm  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) 5HbHJ.|r  
    流水线技术：五点的DFT计算，Systolic算法 ?\\wLZ  
    加速级联(略) Q6(~VvC-  
    破对称技术 ,l&?%H9q  
Ch3 比较器网络上的排序和选择算法 =i)%AnZ^9  
3.1 Batcher归并和排序 q{9vY:`[  
    0-1原理的证明(略) :a*>PMTn  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) .<t{saToU  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) ?i<l7
 
    Batcher排序网络：原理、种类和复杂性 NCk-[I?R  
3.2 (m, n)-选择网络 [4yHXZxza  
    分组选择网络 Pim  
    平衡分组选择网络及其改进 5]
i#l3")  
Ch4 排序和选择的同步算法 R,T0!f  
4.1 一维线性阵列上的并行排序算法(略) Ny"9!3V   
4.2 二维Mesh上的并行排序算法 X0j\nXk  
    ShearSort排序算法 *A9v8$  
    Thompson&Kung双调排序算法及其计算示例 />xEpR3_A  
4.3 Stone双调排序算法(略) F.TIdkvp  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 Gm- "?4(  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 ](oeMl18R  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 #s~ITG#H  
Ch5 排序和选择的异步和分布式算法(略) }6l:'nW  
5.1 MIMD-CREW模型上的异步枚举排序算法 G:e=9qTf  
5.2 MIMD-TC模型上的异步快排序算法 .EhC\QpP  
5.3分布式k-选择算法 2@(+l*.Q  
Ch6 并行搜索 n*GB`I*g  
6.1 单处理器上的搜索(略) (B\Kb4m  
6.2 SIMD共享存储模型上有序表的搜索：算法 ;FlDRDZ%  
6.3 SIMD共享存储模型上随机序列的搜索：算法 y6am(ugE  
6.4 树连接的SIMD模型上随机序列的搜索：算法 0^{Tq0Ri[  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 86%k2~L  
Ch8 数据传输与选路 N_D=j6B  
8.1 引言 mTH[*Y,  
    信包传输性能参数 .NdsKhg b  
    维序选路(X-Y选路、E-立方选路) 6 w!qZ4$  
    选路模式及其传输时间公式 -)J*(7F(6^  
8.2 单一信包一到一传输 `LFT"qnp  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) KUW )F  
8.3 一到多播送 9on$0  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 xD7Y"%Pbx  
8.4 多到多播送 P3bRv^  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Iv7BIK^0  
8.5 贪心算法(书8.2) ~i-n_7+  
    二维阵列上的贪心算法 \sGJs8#v][  
    蝶形网上的贪心算法 937<:zo:  
8.6 随机和确定的选路算法(书8.3)(略) AJ 0Bb7  
Ch12矩阵运算 d}E6d||A  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 L%7WHtU*#  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 ,DKW_F|  
12.3 矩阵向量乘法 -b%' K}.C  
    带状划分的算法及其时间分析 Md
:*[]<~  
    棋盘划分的算法及其时间分析 t2ui9:g4j  
    Systolic算法(略) #SLiv  
12.4 矩阵乘法 99h#M3@ !  
    简单并行分块算法 -?T|1FA,  
    Cannon算法及其计算示例 vO{[P#L}  
    Fox算法及其计算示例 '@^<c#h]=  
    DNS算法及其计算示例 NnZ_x>R  
    Systolic算法(略) mX SLH'  
Ch13 数值计算 7Il /+l(  
13.1 稠密线性方程组求解 _#UhXXD  
    SIMD-CREW的上三角方程组回代算法 U,/9fzgd  
    SIMD-CREW上的Gauss-Jordan算法 $>~4RXC  
    MIMD-CREW上的Gauss-Seidel算法 (j}Wt8  
13.2 稀疏线性方程组的求解 t;%MSedn  
    三对角方程组的奇偶规约求解法 %cc<>Hi  
    Gauss-Seidel迭代法的红黑着色并行算法 vP<8,XG  
13.3 非线性方程的求根(略) !ImtnU}  
Ch14 快速傅立叶变换FFT \U`rF  
14.1 快速傅里叶变换(FFT) /Bnh%6#ab  
    离散傅里叶变换(DFT) yw?UA  
    串行FFT递归算法及其计算原理  - zEQ/6  
    串行FFT蝶式计算及其蝶式计算流图 n;dp%SD  
14.2 DFT直接并行算法 F[|aDj@q e  
    SIMD-MT上的并行DFT算法(略) 0wl31k{  
14.3 并行FFT算法 Y1FP |  
    SIMD-MC上的FFT算法(略) h "r)z6Q/  
    SIMD-BF上的FFT算法及其时间分析 0/%VejZ'  
Ch15 图论算法 Yg7C"3;Vt  
15.1 图的并行搜索 *j= whdw%J  
    p-深度优先搜索及其计算示例 b_0Xi  
    p-宽深优先搜索及其计算示例 FZtI
C77X5  
    p-宽度优先搜索及其计算示例 6c Om8#  
15.2 图的传递闭包 Zz04Pz1  
    基于布尔矩阵乘积的算法原理 A[oxG;9xi  
    计算示例 Ih0kdi  
    SIMD-CC上的传递闭包算法 <yrl_vl{  
15.3 图的连通分量 q>ps99[=  
    基于传递闭包的算法 P\H$*6v(
 
    基于顶点合并的算法 fL&bN[XA"$  
15.4 图的最短路径 |P]>[}mD  
    基于矩阵乘积的算法原理 MkG*6A  
    计算示例 rt\4We,7  
15.5 图的最小生成树 7fJWb)z!k  
    SIMD-EREW模型上的Prim算法 $McVK>=  
    算法的时间分析 tcf>9YsOr  
Ch18 随机算法 #4*~ 4/  
18.1 引言 (-(sBQa+  
    基本知识：随机算法的定义、分类、重复性定律 ZK@ENfG  
    时间复杂性度量 !7-dq w%l  
    设计方法 0xM\+R~,  
18.2 低度顶点部分独立集 I vQ]-A}N  
    串行算法 (TV ye4Z  
    随机并行算法及其正确性证明 IPoNAi<b  
18.5 多项式恒等的验证 O ?9&6x   
    基本原理和方法 IOsitMOX:  
    矩阵乘积的验证原理 _$?SKid|o  
18.8 格点逼近问题(略) w#5^A(NR  
18.9 SAT问题的异步随机并行算法(略) y#Ao6Od6  
Ch20 模型与下界 4cni_m]  
20.1不同的PRAM模型的相互模拟 G.,dP+i
 
    PRAM-EREW模拟PPRAM-CRCW VMUK|pC4K  
    PRAM-CRCW之间的模拟 SAt{At  
20.2下界 VSCOuNSc  
    算法研究的两个方向：优化（上界）、可能性（下界） #s)Wzv%OX  
    Gates的工作 ^E8XPK]-~  
    理想的PRAM模型与下界 d([NU;  
    PRAM模型的下界 1O0o18'  
20.3 NP完全理论导引(略) ?A/+DRQ(  
20.4 P完全理论(略)