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

《并行算法》课程总结与复习 $&&+2?cx0  
Ch1 并行算法基础 &}t8O?!  
1.1 并行计算机体系结构 !JBj%|!  
    并行计算机的分类 'hFL`F*  
    SISD,SIMD,MISD,MIMD； y#
= j{  
    SIMD,PVP,SMP,MPP,COW,DSM z6P~HF+&h  
    并行计算机的互连方式 3"sXN)j  
    静态：LA(LC),MC,TC,MT,HC,BC,SE 13 %:3W(  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) pK ^$^*#  
1.2 并行计算模型 (/E@.z[1  
    PRAM模型：SIMD-SM， 4K 8(H9(  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW D G|v'#  
    SIMD-IN模型：SIMD-DM 5hh6;)  
    异步APRAM模型：MIMD-SM ;%k C?Vzi  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 P#V}l'j(<a  
    LogP模型：MIMD-DM，点到点通讯 IVVX3RI  
1.3 并行算法的一般概念 ou{V/?rb  
    并行算法的定义 :^-\KE`3  
    并行算法的表示 Ktu~% )k%  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 yYP>3]z  
    并行算法的WT表示：Brent定理、WT最优 D;*cy<_K8  
    加速比性能定律(略) x&"P^gh)  
    并行算法的同步和通讯(略) A~^x*#q{4  
Ch2 并行算法的基本设计技术 0{XT#H  
2.1 并行算法的三种基本设计方法 .8GXpt^U(  
2.2 基本设计技术 H/Rzs$pnv  
    平衡树方法：求最大值、计算前缀和  FsQoQ#*  
    倍增技术：表序问题、求森林的根 Z[0/x.pp$  
    分治策略：FFT分治算法 }8s&~fH  
    划分原理： fJ6Q:7  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) EXwU{Hl  
    流水线技术：五点的DFT计算，Systolic算法 E}THG =6  
    加速级联(略) Mvp|S.  
    破对称技术 G}LV"
0?  
Ch3 比较器网络上的排序和选择算法 PHUeN]s#  
3.1 Batcher归并和排序 j(}pUV B  
    0-1原理的证明(略) a5/Dz&>j6
 
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) l|iOdKr h  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) l;&kX6 w  
    Batcher排序网络：原理、种类和复杂性 e,Y<$kPV  
3.2 (m, n)-选择网络 NF C/4  
    分组选择网络 fVVD}GM=  
    平衡分组选择网络及其改进 =BJe}AV  
Ch4 排序和选择的同步算法 Q04 `+Vr  
4.1 一维线性阵列上的并行排序算法(略) &
49Wfc
tT  
4.2 二维Mesh上的并行排序算法 z@V9%xF-3  
    ShearSort排序算法 E@#<p-@~  
    Thompson&Kung双调排序算法及其计算示例 pf+VYZ#)  
4.3 Stone双调排序算法(略) shP}T[<  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 ?;.= o?e9  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析  ls7P$qq  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 TCIbPsE  
Ch5 排序和选择的异步和分布式算法(略) LGVy4D  
5.1 MIMD-CREW模型上的异步枚举排序算法 lV$#>2Hh5  
5.2 MIMD-TC模型上的异步快排序算法 g}uSIv^  
5.3分布式k-选择算法 tmM; Z(9t  
Ch6 并行搜索 jzZ
]+'t  
6.1 单处理器上的搜索(略) >,I'S2_Zl  
6.2 SIMD共享存储模型上有序表的搜索：算法 G;/l[mvh,  
6.3 SIMD共享存储模型上随机序列的搜索：算法 AT1{D!b  
6.4 树连接的SIMD模型上随机序列的搜索：算法 yy&L&v'  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 e$JC
ak=  
Ch8 数据传输与选路 v-^tj}jA  
8.1 引言 q ">}3`
k  
    信包传输性能参数 i\gt @  
    维序选路(X-Y选路、E-立方选路) ir>+p>s.  
    选路模式及其传输时间公式 [!8bjc]c
 
8.2 单一信包一到一传输 o)x&|0_  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) t~nW&]E  
8.3 一到多播送 \pTv;(  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 2Vu?Y
 
8.4 多到多播送 mFxt  +\  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 7Kb&BF|Q  
8.5 贪心算法(书8.2) W tHJG5  
    二维阵列上的贪心算法 Q~k |lTf  
    蝶形网上的贪心算法  6E:H   
8.6 随机和确定的选路算法(书8.3)(略) i[{*(Y$L   
Ch12矩阵运算 %L7DC`  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 %g3QE:(2@q  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 ^Jdg%U?  
12.3 矩阵向量乘法 ITi#p%  
    带状划分的算法及其时间分析 4mEJu  
    棋盘划分的算法及其时间分析 ko'V8r`V  
    Systolic算法(略) =MD) F  
12.4 矩阵乘法 Fm6]mz%~u#  
    简单并行分块算法 UX.rzYM&T  
    Cannon算法及其计算示例 $ndBT+i  
    Fox算法及其计算示例 #N64ZXz_  
    DNS算法及其计算示例 :?m"kh ~  
    Systolic算法(略) g2'K3e?.%  
Ch13 数值计算 Z?3B1o9  
13.1 稠密线性方程组求解 R\#5;W^  
    SIMD-CREW的上三角方程组回代算法 QR8]d1+GV  
    SIMD-CREW上的Gauss-Jordan算法 G{Ju2HY  
    MIMD-CREW上的Gauss-Seidel算法 DRXUQH  
13.2 稀疏线性方程组的求解 XpK  Y#  
    三对角方程组的奇偶规约求解法 >TawJ"q-6R  
    Gauss-Seidel迭代法的红黑着色并行算法 >c
5  
13.3 非线性方程的求根(略) 7v0VZ(UR  
Ch14 快速傅立叶变换FFT /l3O i@\  
14.1 快速傅里叶变换(FFT) e7&RZ+s#wZ  
    离散傅里叶变换(DFT) vS3Y9
|-:  
    串行FFT递归算法及其计算原理 _+7P"B|\  
    串行FFT蝶式计算及其蝶式计算流图 ]iFW>N*a  
14.2 DFT直接并行算法 Jcs /i  
    SIMD-MT上的并行DFT算法(略) ,nPnH1vb  
14.3 并行FFT算法 !,5qAGi0  
    SIMD-MC上的FFT算法(略) xUa9>=JU{  
    SIMD-BF上的FFT算法及其时间分析 oblw!)  
Ch15 图论算法 mc@Z+t'  
15.1 图的并行搜索 * 0JF|'  
    p-深度优先搜索及其计算示例 O<Ay`p5  
    p-宽深优先搜索及其计算示例 H/8u?OC  
    p-宽度优先搜索及其计算示例 d& v 7l  
15.2 图的传递闭包 YWV)C?5x&  
    基于布尔矩阵乘积的算法原理 UX|3LpFX&I  
    计算示例 3!#FG0Z  
    SIMD-CC上的传递闭包算法 M;KeY[u  
15.3 图的连通分量 Ip8:~Fl]  
    基于传递闭包的算法 G2@'S&2@s  
    基于顶点合并的算法 CR#-!_=4  
15.4 图的最短路径 H&k&mRi  
    基于矩阵乘积的算法原理 T`<Tj?:^&  
    计算示例 [W<j  
15.5 图的最小生成树 )2Y]A^Y   
    SIMD-EREW模型上的Prim算法 b0se -#+  
    算法的时间分析 \]\GDpu[  
Ch18 随机算法 As tuM]  
18.1 引言 &rG]]IO  
    基本知识：随机算法的定义、分类、重复性定律 e-lc2$o7{  
    时间复杂性度量 { W5 _KX  
    设计方法 } z7yS.{  
18.2 低度顶点部分独立集 f& ] !;)  
    串行算法
9]/:B8k  
    随机并行算法及其正确性证明 -h8Z@r~a/  
18.5 多项式恒等的验证 a^O>i#i  
    基本原理和方法 FZ8Qj8  
    矩阵乘积的验证原理 CWd &  
18.8 格点逼近问题(略) v&f\ Jv7  
18.9 SAT问题的异步随机并行算法(略) v9t'CMU  
Ch20 模型与下界 Q(BZg{  
20.1不同的PRAM模型的相互模拟  8#1o  
    PRAM-EREW模拟PPRAM-CRCW tWTC'Gx-J  
    PRAM-CRCW之间的模拟 -Wre4^,v  
20.2下界 C 8d9(u  
    算法研究的两个方向：优化（上界）、可能性（下界） |0_5iFAB|  
    Gates的工作 '#Q Zhz(+  
    理想的PRAM模型与下界 l#p?lBm1  
    PRAM模型的下界 rQPO+  
20.3 NP完全理论导引(略) ]2[\E~^KU  
20.4 P完全理论(略)