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

《并行算法》课程总结与复习 q9 GSUkb  
Ch1 并行算法基础 O>YXvu  
1.1 并行计算机体系结构 Ood8Qty(  
    并行计算机的分类 *h=|KOS  
    SISD,SIMD,MISD,MIMD； uWs5+  
    SIMD,PVP,SMP,MPP,COW,DSM C_>dJYM  
    并行计算机的互连方式 h^{D "  
    静态：LA(LC),MC,TC,MT,HC,BC,SE ,uEi*s>  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) !}u'%  
1.2 并行计算模型 4%h@K(iN  
    PRAM模型：SIMD-SM， iqCZIahf  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW c< ke)@  
    SIMD-IN模型：SIMD-DM 9(.P2yO  
    异步APRAM模型：MIMD-SM &.sfu$]  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 ?n$;l-m[  
    LogP模型：MIMD-DM，点到点通讯 [12^NEt  
1.3 并行算法的一般概念 jl# )CEx  
    并行算法的定义 Pb05>J3N  
    并行算法的表示 (+'*_   
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 G813NoS o  
    并行算法的WT表示：Brent定理、WT最优 S |U/m m  
    加速比性能定律(略) &%QtUPvr9  
    并行算法的同步和通讯(略) '%&i#Eb  
Ch2 并行算法的基本设计技术 V #!ftu#c?  
2.1 并行算法的三种基本设计方法 X|Gsf= 1S  
2.2 基本设计技术 -\mbrbG9H  
    平衡树方法：求最大值、计算前缀和 Y|bCbaF  
    倍增技术：表序问题、求森林的根 L&td4`2y  
    分治策略：FFT分治算法 p#:.,;  
    划分原理：
U0}]3a0  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) (/J$2V5 -  
    流水线技术：五点的DFT计算，Systolic算法 E}S)uI,gn  
    加速级联(略) W(N@`^  
    破对称技术 FuEgI8+b  
Ch3 比较器网络上的排序和选择算法 /"d5<B`%  
3.1 Batcher归并和排序 @}&o(q1M0  
    0-1原理的证明(略) Hd(|fc{2  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) SooSOOAx[  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Snx_NH#tA  
    Batcher排序网络：原理、种类和复杂性 m S[Vl6  
3.2 (m, n)-选择网络 0*?~I;.2m$  
    分组选择网络 ;Wjb}_
V:_  
    平衡分组选择网络及其改进 D0(QZrVa  
Ch4 排序和选择的同步算法 kJP fL s  
4.1 一维线性阵列上的并行排序算法(略) U[5  
4.2 二维Mesh上的并行排序算法 ,]e!OZ[$m  
    ShearSort排序算法 M~Tq'>Fn  
    Thompson&Kung双调排序算法及其计算示例 z@hlN3dg  
4.3 Stone双调排序算法(略) Q5'DV!0aSv  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 BwO^F^Pr?k  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 (I~-mz
u\  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 $Oa}U3  
Ch5 排序和选择的异步和分布式算法(略) ;c"T#CH.  
5.1 MIMD-CREW模型上的异步枚举排序算法 ;2K_u  
5.2 MIMD-TC模型上的异步快排序算法 (JS1}T  
5.3分布式k-选择算法 mx s=<  
Ch6 并行搜索 )+2GF0%  
6.1 单处理器上的搜索(略) E.kGBA;a?  
6.2 SIMD共享存储模型上有序表的搜索：算法 ES72yh]  
6.3 SIMD共享存储模型上随机序列的搜索：算法 %<%ef+*  
6.4 树连接的SIMD模型上随机序列的搜索：算法 DYlu`j_ux  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 [@MV[$W5  
Ch8 数据传输与选路 ]dB6--  
8.1 引言 XiE  
    信包传输性能参数  ~0 <?^  
    维序选路(X-Y选路、E-立方选路) Y9fktg.  
    选路模式及其传输时间公式 1t{h)fwi  
8.2 单一信包一到一传输 6?nAO  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 3B:U>F,]4  
8.3 一到多播送 o*H j E  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Eh\0gQ=  
8.4 多到多播送 w[@>k@=  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 -MZLkSU  
8.5 贪心算法(书8.2) [80jG+6  
    二维阵列上的贪心算法 iD=VNf  
    蝶形网上的贪心算法 fNOsB
^Y  
8.6 随机和确定的选路算法(书8.3)(略) kW>Q9Nc=V  
Ch12矩阵运算 <H3njv  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 *x3";
%o  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 8:hUj>qx  
12.3 矩阵向量乘法 37'@,*m`  
    带状划分的算法及其时间分析 jH26-b<  
    棋盘划分的算法及其时间分析 
sU"D%G  
    Systolic算法(略) "5*n(S{ks  
12.4 矩阵乘法 e R"XXF0u  
    简单并行分块算法 ' O1X+  
    Cannon算法及其计算示例 5&]|p'"W\  
    Fox算法及其计算示例 7Yp;B:5@  
    DNS算法及其计算示例 Z(LDA ZG  
    Systolic算法(略) gAt[kW< n  
Ch13 数值计算 [v$_BS#u^3  
13.1 稠密线性方程组求解 T;D`=p#  
    SIMD-CREW的上三角方程组回代算法 Wlm%W>%  
    SIMD-CREW上的Gauss-Jordan算法 .ruGS.nS4  
    MIMD-CREW上的Gauss-Seidel算法 QF:">G  
13.2 稀疏线性方程组的求解 n|`L>@aw,  
    三对角方程组的奇偶规约求解法 W70J2
 
    Gauss-Seidel迭代法的红黑着色并行算法 /VB n  
13.3 非线性方程的求根(略) weCRhA  
Ch14 快速傅立叶变换FFT !%b.k6%>w  
14.1 快速傅里叶变换(FFT) o"D`_ER  
    离散傅里叶变换(DFT) A-gNfXP,D  
    串行FFT递归算法及其计算原理 Pnq[r2#]:  
    串行FFT蝶式计算及其蝶式计算流图 pjr,X+6o  
14.2 DFT直接并行算法 Kl.xe&t@j  
    SIMD-MT上的并行DFT算法(略) SrzlR)  
14.3 并行FFT算法 rq'Cj<=Zj  
    SIMD-MC上的FFT算法(略) iyNyj44 H  
    SIMD-BF上的FFT算法及其时间分析 I=)Hb?qT~  
Ch15 图论算法 D&_Ir>"\  
15.1 图的并行搜索 VQE8hQ37  
    p-深度优先搜索及其计算示例 
dA-ik  
    p-宽深优先搜索及其计算示例 J
\U}U'qP  
    p-宽度优先搜索及其计算示例 <(x[Qp/5P  
15.2 图的传递闭包 +T:F :X`  
    基于布尔矩阵乘积的算法原理 $(v1q[ig  
    计算示例 lVY`^pw?  
    SIMD-CC上的传递闭包算法 ($:s}_<>s  
15.3 图的连通分量 D*3\4=6x  
    基于传递闭包的算法 j48cI3C  
    基于顶点合并的算法 prE~GO7Z  
15.4 图的最短路径 <;\T e4g[  
    基于矩阵乘积的算法原理 "o&_
tB;O  
    计算示例 SPKGbp&  
15.5 图的最小生成树 dn/0>|5OF(  
    SIMD-EREW模型上的Prim算法 }R5>ja0  
    算法的时间分析 OI;0dS  
Ch18 随机算法 v3 4!rL  
18.1 引言 j|3p.Cy
 
    基本知识：随机算法的定义、分类、重复性定律 88~BE ^  
    时间复杂性度量 HV'xDy[)  
    设计方法 K~gt=NH  
18.2 低度顶点部分独立集 YCod\}
3  
    串行算法 y7aBF13Kl  
    随机并行算法及其正确性证明 ^t4T8ej
n  
18.5 多项式恒等的验证 uPbvN[~t  
    基本原理和方法 u 0KVp6`  
    矩阵乘积的验证原理 a$!|)+  
18.8 格点逼近问题(略) d dB}mk6  
18.9 SAT问题的异步随机并行算法(略) eqD|3Y
X  
Ch20 模型与下界 :f (UZmV$  
20.1不同的PRAM模型的相互模拟 6J[ {?,  
    PRAM-EREW模拟PPRAM-CRCW +{Yd\{9  
    PRAM-CRCW之间的模拟 m~"<k d  
20.2下界 ^(7<L<H  
    算法研究的两个方向：优化（上界）、可能性（下界） B|E4(,]^  
    Gates的工作 7+wy`xi  
    理想的PRAM模型与下界 >Qg`Us
#y  
    PRAM模型的下界 -[A4B)  
20.3 NP完全理论导引(略) iev02 8M  
20.4 P完全理论(略)