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

《并行算法》课程总结与复习 X or ,}. w  
Ch1 并行算法基础 NY;UI(<]  
1.1 并行计算机体系结构 5HIpoj;\(  
    并行计算机的分类 e>>G4g  
    SISD,SIMD,MISD,MIMD； _l ,Z38  
    SIMD,PVP,SMP,MPP,COW,DSM __fR #D  
    并行计算机的互连方式 ]dK]a:S  
    静态：LA(LC),MC,TC,MT,HC,BC,SE ?xo,)`
`  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) _% 2Umy|  
1.2 并行计算模型 tZ
YI{m{  
    PRAM模型：SIMD-SM， yUSB{DLpla  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW cMWO_$  
    SIMD-IN模型：SIMD-DM )
ra66E  
    异步APRAM模型：MIMD-SM 3.0c/v5Go  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 cGc|n3(  
    LogP模型：MIMD-DM，点到点通讯 UjDF  
1.3 并行算法的一般概念 -h@0
1  
    并行算法的定义 xs I/DW  
    并行算法的表示 &o/4hnHYt  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 9i<-\w^$  
    并行算法的WT表示：Brent定理、WT最优 ^!<7#kX  
    加速比性能定律(略) 9f^PR|F  
    并行算法的同步和通讯(略) 6{$dFwl  
Ch2 并行算法的基本设计技术 P082.:q"  
2.1 并行算法的三种基本设计方法 '^l^g
W/|\  
2.2 基本设计技术 o1WidJ"  
    平衡树方法：求最大值、计算前缀和 SO<m(o)G2  
    倍增技术：表序问题、求森林的根 GeaDaYh#T  
    分治策略：FFT分治算法 unnx#e]  
    划分原理： 1bJ]3\  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) "x;k'{S  
    流水线技术：五点的DFT计算，Systolic算法 S%X\,N  
    加速级联(略) j 3MciQ`  
    破对称技术 b3b~T]]  
Ch3 比较器网络上的排序和选择算法 3rdfg  
3.1 Batcher归并和排序 ^dnz=FB  
    0-1原理的证明(略) H@MFj>~  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) Px#QZZ  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) 9V;$v  
    Batcher排序网络：原理、种类和复杂性 d%lHa??/h  
3.2 (m, n)-选择网络 uR;-eK  
    分组选择网络 ,=Nw(GI  
    平衡分组选择网络及其改进 w2d]96*kQe  
Ch4 排序和选择的同步算法 oKYhE  
4.1 一维线性阵列上的并行排序算法(略) i.t9jN  
4.2 二维Mesh上的并行排序算法 5eOj,[?  
    ShearSort排序算法 h ??C4z  
    Thompson&Kung双调排序算法及其计算示例 P-+M,>vNy[  
4.3 Stone双调排序算法(略) )@, 90Vhh  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 (]Ye[j^"7  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 icPp8EwH  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 fJWxJSdi  
Ch5 排序和选择的异步和分布式算法(略) 7-d}pgVK  
5.1 MIMD-CREW模型上的异步枚举排序算法 S,9NUt  
5.2 MIMD-TC模型上的异步快排序算法 `z}vONXpAX  
5.3分布式k-选择算法 ypD<2z^  
Ch6 并行搜索 f6B-~x< l  
6.1 单处理器上的搜索(略) fey*la Xq  
6.2 SIMD共享存储模型上有序表的搜索：算法 *p&^!ct  
6.3 SIMD共享存储模型上随机序列的搜索：算法 _ktK+8*6`  
6.4 树连接的SIMD模型上随机序列的搜索：算法 ]<kupaRQ  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 "x(>Sj\%I  
Ch8 数据传输与选路 1Xy8|OFc[  
8.1 引言 0]T.Lh$3  
    信包传输性能参数 1BQ0M{&  
    维序选路(X-Y选路、E-立方选路) Zc'|!pT _  
    选路模式及其传输时间公式 ;)(Sdf[P  
8.2 单一信包一到一传输 `^7:7Wr]=  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) ic*->-!  
8.3 一到多播送 b7B+eN ?z  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Ap5}5 ewM  
8.4 多到多播送 [%@2
o<  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 D]IBB>F  
8.5 贪心算法(书8.2) G2.|fp_}pG  
    二维阵列上的贪心算法 b4>``n  
    蝶形网上的贪心算法 AV40:y\RW  
8.6 随机和确定的选路算法(书8.3)(略) I eG=J4:*  
Ch12矩阵运算 U1ZIuDg'E  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 t, U) ~wi  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 G&q'#3ieC  
12.3 矩阵向量乘法 00ofHZ  
    带状划分的算法及其时间分析 YT>KJ  
    棋盘划分的算法及其时间分析 #/Ruz'H1>  
    Systolic算法(略) _
7U]&Nh99  
12.4 矩阵乘法 0n Y6A~  
    简单并行分块算法 a1Hz3y~S/  
    Cannon算法及其计算示例 xwRhs!`t1  
    Fox算法及其计算示例 s~*}0-lS  
    DNS算法及其计算示例 q\%cFB}  
    Systolic算法(略) AS)UJ/lC  
Ch13 数值计算 F^QQ0h]2  
13.1 稠密线性方程组求解 rQ/,XH  
    SIMD-CREW的上三角方程组回代算法 iPq &Y*  
    SIMD-CREW上的Gauss-Jordan算法 H&#{l)  
    MIMD-CREW上的Gauss-Seidel算法 &( EHq  
13.2 稀疏线性方程组的求解 ,apNwkY  
    三对角方程组的奇偶规约求解法 +
oI3I~  
    Gauss-Seidel迭代法的红黑着色并行算法 QT! 4[,4  
13.3 非线性方程的求根(略) *O,H5lwU  
Ch14 快速傅立叶变换FFT /kgeV4]zR  
14.1 快速傅里叶变换(FFT) :4:N f  
    离散傅里叶变换(DFT) rYY$wA@  
    串行FFT递归算法及其计算原理 <A>)[u  
    串行FFT蝶式计算及其蝶式计算流图 sV/l5]b]  
14.2 DFT直接并行算法 .f:n\eT):  
    SIMD-MT上的并行DFT算法(略) Ot
J\T/q,  
14.3 并行FFT算法 +x=)/;:  
    SIMD-MC上的FFT算法(略) :`\) P,  
    SIMD-BF上的FFT算法及其时间分析 ]}Z4P-"t  
Ch15 图论算法 08s_v=cF  
15.1 图的并行搜索 ,E;;wdIt  
    p-深度优先搜索及其计算示例 (Glr\q]jF\  
    p-宽深优先搜索及其计算示例 r X'*|]  
    p-宽度优先搜索及其计算示例 b| M3`  
15.2 图的传递闭包 +k\Uf*wh  
    基于布尔矩阵乘积的算法原理 fX~'Zk\u  
    计算示例 -d+aV1n  
    SIMD-CC上的传递闭包算法 Pq9|WV#F5/  
15.3 图的连通分量 6at1bQ$  
    基于传递闭包的算法 lg:  
    基于顶点合并的算法 0(U#)  
15.4 图的最短路径 l<g5yY yf  
    基于矩阵乘积的算法原理 JyLa#\ R  
    计算示例 g.py+ ZFJ  
15.5 图的最小生成树 5xCT~y/a  
    SIMD-EREW模型上的Prim算法 ]rehW}  
    算法的时间分析 ]z/Zq  
Ch18 随机算法 Byl^?5  
18.1 引言 6W[}$#w  
    基本知识：随机算法的定义、分类、重复性定律 4y:]DC"  
    时间复杂性度量 Q?b14]6im  
    设计方法 Jn:ZYqc  
18.2 低度顶点部分独立集 zGKyN@o  
    串行算法 ^G&3sF}  
    随机并行算法及其正确性证明 }KUd7[
s  
18.5 多项式恒等的验证 ca i<,3H  
    基本原理和方法 zgx&
Pte  
    矩阵乘积的验证原理 1"Z@Q`}  
18.8 格点逼近问题(略) CTX9zrY*T  
18.9 SAT问题的异步随机并行算法(略) F+R?a+e  
Ch20 模型与下界
NBl+_/2'w  
20.1不同的PRAM模型的相互模拟 vgY3L  
    PRAM-EREW模拟PPRAM-CRCW ^b:(jI*l  
    PRAM-CRCW之间的模拟 We0.3aG  
20.2下界 8fA_p}wp  
    算法研究的两个方向：优化（上界）、可能性（下界） !It`+0S b  
    Gates的工作 rpeJkG@+  
    理想的PRAM模型与下界 #/PAA  
    PRAM模型的下界 5T sUQc  
20.3 NP完全理论导引(略) F, U*
yj  
20.4 P完全理论(略)