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

《并行算法》课程总结与复习 Ug^v ]B9  
Ch1 并行算法基础 -]h3s >
t  
1.1 并行计算机体系结构 CL$mK5u  
    并行计算机的分类 O W12m{  
    SISD,SIMD,MISD,MIMD； Px)/`'D  
    SIMD,PVP,SMP,MPP,COW,DSM >aZ$x/U+Iw  
    并行计算机的互连方式 MyOdWD&7  
    静态：LA(LC),MC,TC,MT,HC,BC,SE Iz#h:O  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) N*Owfr1N  
1.2 并行计算模型 ; ,y9  
    PRAM模型：SIMD-SM， 'l U9*e9  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW k.DDf uKN  
    SIMD-IN模型：SIMD-DM ,OLN%2Sq  
    异步APRAM模型：MIMD-SM ]~z2s;J{/  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 V$wf;v0d(  
    LogP模型：MIMD-DM，点到点通讯 a<[@p  
1.3 并行算法的一般概念 0j1I  
    并行算法的定义 j0k"iv  
    并行算法的表示 WZ'3
 
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 M[0@3"}}  
    并行算法的WT表示：Brent定理、WT最优 YXJjqH3  
    加速比性能定律(略) S2"p(  
    并行算法的同步和通讯(略) KX9+*YY,  
Ch2 并行算法的基本设计技术 :JqH.Sqk  
2.1 并行算法的三种基本设计方法 +"a .,-f!  
2.2 基本设计技术 2-u>=r0L  
    平衡树方法：求最大值、计算前缀和 RaAi9b[/S  
    倍增技术：表序问题、求森林的根 rZZueYuXO  
    分治策略：FFT分治算法 Xi5ZQo!t  
    划分原理： :t]YPt
  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) ekfD+X  
    流水线技术：五点的DFT计算，Systolic算法 J(S.iTD  
    加速级联(略) y&A*/J4P  
    破对称技术 ^l ~i>:V  
Ch3 比较器网络上的排序和选择算法 by&#g  
3.1 Batcher归并和排序 cxrUk$f  
    0-1原理的证明(略) 4W~pAruwr  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) 6Ez} A|i  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) VLc=!W}  
    Batcher排序网络：原理、种类和复杂性 "Sc_E}q|e  
3.2 (m, n)-选择网络 @P4fR7  
    分组选择网络 gc7S_D~;  
    平衡分组选择网络及其改进 Ej ip%m  
Ch4 排序和选择的同步算法 "Nn/vid;  
4.1 一维线性阵列上的并行排序算法(略) \q(RqD  
4.2 二维Mesh上的并行排序算法 a [iC!F2   
    ShearSort排序算法 uv}[MXOP  
    Thompson&Kung双调排序算法及其计算示例 +%=Ao6/#  
4.3 Stone双调排序算法(略) ?7'uo$  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 Z[yQKy  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 /);cl;"  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 (01M0b#  
Ch5 排序和选择的异步和分布式算法(略) :O{`!&[>L  
5.1 MIMD-CREW模型上的异步枚举排序算法 9Y- Sqk+  
5.2 MIMD-TC模型上的异步快排序算法 * 'WzIk
2  
5.3分布式k-选择算法 ;+g p#&i`  
Ch6 并行搜索 G\?fWqx  
6.1 单处理器上的搜索(略) j~(rG^T  
6.2 SIMD共享存储模型上有序表的搜索：算法 PCH&eTKN  
6.3 SIMD共享存储模型上随机序列的搜索：算法 3gaijVN  
6.4 树连接的SIMD模型上随机序列的搜索：算法 "D'A7DA  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 #Sr_PEo _  
Ch8 数据传输与选路 %kS+n_*  
8.1 引言 -~~"}u  
    信包传输性能参数 |G~LJsXW!v  
    维序选路(X-Y选路、E-立方选路) V~tq _  
    选路模式及其传输时间公式 Q>] iRx>MZ  
8.2 单一信包一到一传输 o;.PZi2k  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) NOLw119K  
8.3 一到多播送 " G-} wt+P  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 @cA`del  
8.4 多到多播送 BoE;,s>]NW  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 wN\%b}pp  
8.5 贪心算法(书8.2) Xp@8vu  
    二维阵列上的贪心算法 fhw.A5Ck  
    蝶形网上的贪心算法 ]pp
i962Z  
8.6 随机和确定的选路算法(书8.3)(略) Z{s&myd  
Ch12矩阵运算 D7H,49#1Q  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 4nQk*:p(X  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 x%ju(B>  
12.3 矩阵向量乘法 2A7 g}V  
    带状划分的算法及其时间分析 ++d(}^C;  
    棋盘划分的算法及其时间分析 1 t haQ"  
    Systolic算法(略) DFKFsu8s  
12.4 矩阵乘法 8.FBgZh*  
    简单并行分块算法 86igP  
    Cannon算法及其计算示例 dR~4*59Bg  
    Fox算法及其计算示例 qu- !XC0p  
    DNS算法及其计算示例 gdkl,z3N3  
    Systolic算法(略) r \+&{EEG  
Ch13 数值计算 2 <HG=iSf  
13.1 稠密线性方程组求解 y3l3XLI*b  
    SIMD-CREW的上三角方程组回代算法 jY>|>]4X  
    SIMD-CREW上的Gauss-Jordan算法 i bAZ*I  
    MIMD-CREW上的Gauss-Seidel算法 *fyC@fI>  
13.2 稀疏线性方程组的求解 (qd$wv^h  
    三对角方程组的奇偶规约求解法 [<SM*fQ>t  
    Gauss-Seidel迭代法的红黑着色并行算法 ]"bkB+I  
13.3 非线性方程的求根(略) ~Wy&xs ZH  
Ch14 快速傅立叶变换FFT Ei!t#'*D<  
14.1 快速傅里叶变换(FFT) 6&/H XqP  
    离散傅里叶变换(DFT) lF-;h{   
    串行FFT递归算法及其计算原理 XVwaX2=L  
    串行FFT蝶式计算及其蝶式计算流图 K..L8#SC  
14.2 DFT直接并行算法 }G^Bc4@b  
    SIMD-MT上的并行DFT算法(略) 'Okitq+O  
14.3 并行FFT算法 Co6ghH7T  
    SIMD-MC上的FFT算法(略) >C""T`5]  
    SIMD-BF上的FFT算法及其时间分析 BM bT:)%  
Ch15 图论算法 Gy {C*m7Q  
15.1 图的并行搜索 oXw}K((|  
    p-深度优先搜索及其计算示例 cgKK(-$ny  
    p-宽深优先搜索及其计算示例 :`BZ,j_  
    p-宽度优先搜索及其计算示例 !>XG$-$`Z  
15.2 图的传递闭包 Bkg/A;H  
    基于布尔矩阵乘积的算法原理 C~o6]'+F_  
    计算示例 [\N,ow,n  
    SIMD-CC上的传递闭包算法 jJ% *hDZ6t  
15.3 图的连通分量 w <zO  
    基于传递闭包的算法 =IBdnEz:M  
    基于顶点合并的算法 >@^z?nb  
15.4 图的最短路径 z,XM|-"#<K  
    基于矩阵乘积的算法原理 -L7Q,"a$  
    计算示例 b6!?K!imT  
15.5 图的最小生成树 "dwx;E  
    SIMD-EREW模型上的Prim算法 *,1^{mb  
    算法的时间分析 TL@_m^SM  
Ch18 随机算法 b\~rL,7(  
18.1 引言 *ie#9jA  
    基本知识：随机算法的定义、分类、重复性定律 *1iJa  
    时间复杂性度量 cT^,[3i:c  
    设计方法 EOhUr=5~  
18.2 低度顶点部分独立集 xin<.)!E  
    串行算法 1fwCQM   
    随机并行算法及其正确性证明 4VLrl8$K  
18.5 多项式恒等的验证 W|~Lmdzj  
    基本原理和方法 LoUi Yf  
    矩阵乘积的验证原理 2Jrr;"r  
18.8 格点逼近问题(略) (i>VJr  
18.9 SAT问题的异步随机并行算法(略) oH!sJ&"#_  
Ch20 模型与下界 DIodQkF  
20.1不同的PRAM模型的相互模拟 [qlq&?"  
    PRAM-EREW模拟PPRAM-CRCW HH+NNSR
O  
    PRAM-CRCW之间的模拟 NZYtA7  
20.2下界 K97lP~Hu  
    算法研究的两个方向：优化（上界）、可能性（下界） 3WS`,}  
    Gates的工作 t*y4)I !gR  
    理想的PRAM模型与下界 z~+_sTu  
    PRAM模型的下界 b,/fz6 {N  
20.3 NP完全理论导引(略) 0}hN/2}&  
20.4 P完全理论(略)