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

《并行算法》课程总结与复习 L=fy!R  
Ch1 并行算法基础 5ArgM%  
1.1 并行计算机体系结构 *e<}hmDr  
    并行计算机的分类 _1mpsY< k  
    SISD,SIMD,MISD,MIMD； |MagK$o  
    SIMD,PVP,SMP,MPP,COW,DSM !"&-k:|g  
    并行计算机的互连方式 >P
:U9 b  
    静态：LA(LC),MC,TC,MT,HC,BC,SE _l1"X^Aa  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) Ab>Kfr#  
1.2 并行计算模型 U_;="y  
    PRAM模型：SIMD-SM， FP}I+Ys  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW &[ ], rT  
    SIMD-IN模型：SIMD-DM ob'" ^LO\  
    异步APRAM模型：MIMD-SM H_Va$}8z  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 LI&E.(:  
    LogP模型：MIMD-DM，点到点通讯 +u*Pi  
1.3 并行算法的一般概念 _0FMwC#DY  
    并行算法的定义 0 f$96sl  
    并行算法的表示 *po o.Zz  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 r!O[|h  
    并行算法的WT表示：Brent定理、WT最优 60cQ3.e  
    加速比性能定律(略) s6Dkh}:d  
    并行算法的同步和通讯(略) { Ie~MW  
Ch2 并行算法的基本设计技术 uv8kea .(  
2.1 并行算法的三种基本设计方法 ^IyQzBOj  
2.2 基本设计技术 UNwjx7usD  
    平衡树方法：求最大值、计算前缀和 hN~H8.g  
    倍增技术：表序问题、求森林的根 UKV<Ye|  
    分治策略：FFT分治算法 0l& '`  
    划分原理： <66%(J>  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) 7SH3k=x  
    流水线技术：五点的DFT计算，Systolic算法 &0\:MJc  
    加速级联(略) , V,Q(!$F  
    破对称技术 q_` j-!  
Ch3 比较器网络上的排序和选择算法 <#57q%  
3.1 Batcher归并和排序 /k K!xe  
    0-1原理的证明(略) d$x vE m  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) 'J-a2oiM(  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) WcS`T?Xa  
    Batcher排序网络：原理、种类和复杂性 .9=4Af  
3.2 (m, n)-选择网络 ,7:-V<'Yv  
    分组选择网络 1 I.P7_/  
    平衡分组选择网络及其改进 `''y,{Fs  
Ch4 排序和选择的同步算法 )g^qgxnnV  
4.1 一维线性阵列上的并行排序算法(略) &4}=@'G@  
4.2 二维Mesh上的并行排序算法 @mxaZ5Vv}  
    ShearSort排序算法 X$1YvYsID  
    Thompson&Kung双调排序算法及其计算示例 H25Qx;(dTk  
4.3 Stone双调排序算法(略) Ab/JCZNn  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 ma@V>*u  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 =Hn--DEMg  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 ezY^T  
Ch5 排序和选择的异步和分布式算法(略) m%[/w wL  
5.1 MIMD-CREW模型上的异步枚举排序算法 z_lKq}^~6  
5.2 MIMD-TC模型上的异步快排序算法 ^0cbN[~/ns  
5.3分布式k-选择算法 ~8mz.ZdY  
Ch6 并行搜索 f~Pce||e  
6.1 单处理器上的搜索(略) [ 't.x=  
6.2 SIMD共享存储模型上有序表的搜索：算法 7%? bl  
6.3 SIMD共享存储模型上随机序列的搜索：算法 ){#INmsF  
6.4 树连接的SIMD模型上随机序列的搜索：算法 SJh~4R\  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 hLuv  
Ch8 数据传输与选路 |94o P>d  
8.1 引言 XR7v
\rd  
    信包传输性能参数
^M
q@} 0  
    维序选路(X-Y选路、E-立方选路) un~`|   
    选路模式及其传输时间公式 [?9 `x- Q  
8.2 单一信包一到一传输 : -#w  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) .uS`RS8JM  
8.3 一到多播送 Nj2l>[L;  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 g~.#.S ds  
8.4 多到多播送 5XHejHn>  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 ]ilLed  
8.5 贪心算法(书8.2) 'SlZ-SdR  
    二维阵列上的贪心算法 3~3tjhw;]9  
    蝶形网上的贪心算法 EKF 4]  
8.6 随机和确定的选路算法(书8.3)(略) ~BuBma_  
Ch12矩阵运算 < B]qqqP  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 L YB@L06a  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 Y %bb-|\W  
12.3 矩阵向量乘法 Y ? n4#J<  
    带状划分的算法及其时间分析 in
O;Uwlv  
    棋盘划分的算法及其时间分析 2/V%jS[4#y  
    Systolic算法(略) ^c}3o|1m(  
12.4 矩阵乘法 PcT]  
    简单并行分块算法 \ZV>5N3hS  
    Cannon算法及其计算示例 [[<TW }   
    Fox算法及其计算示例 XK/l1E3N  
    DNS算法及其计算示例 "PRHQW  
    Systolic算法(略) 3]JJCaf  
Ch13 数值计算 aBaiX
v/*  
13.1 稠密线性方程组求解 g.`Ntsi$wI  
    SIMD-CREW的上三角方程组回代算法 Pi?G:IF  
    SIMD-CREW上的Gauss-Jordan算法 +3zQ"lLD^  
    MIMD-CREW上的Gauss-Seidel算法 Ty{ SZUJ  
13.2 稀疏线性方程组的求解 A. tGr(r  
    三对角方程组的奇偶规约求解法 '
bM=  
    Gauss-Seidel迭代法的红黑着色并行算法 qCrpc=  
13.3 非线性方程的求根(略) H"w;~;h  
Ch14 快速傅立叶变换FFT .K4)#oC  
14.1 快速傅里叶变换(FFT) sDg1nKw(  
    离散傅里叶变换(DFT) N3#^If n[  
    串行FFT递归算法及其计算原理 7
\g#'#K  
    串行FFT蝶式计算及其蝶式计算流图 ;/4x.t#b  
14.2 DFT直接并行算法 yLCMu | +  
    SIMD-MT上的并行DFT算法(略) .3_u5N|[=W  
14.3 并行FFT算法 a;; Es  
    SIMD-MC上的FFT算法(略) _fn7-&6  
    SIMD-BF上的FFT算法及其时间分析 Sw>> ]UjU  
Ch15 图论算法 ~cO
iv  
15.1 图的并行搜索 K>~YO~~  
    p-深度优先搜索及其计算示例 K5`*Y@  
    p-宽深优先搜索及其计算示例 Ici4y*`M  
    p-宽度优先搜索及其计算示例 $i<+O,@-  
15.2 图的传递闭包 havmhS)O  
    基于布尔矩阵乘积的算法原理 C]JK'K<7-  
    计算示例 d:A'|;']  
    SIMD-CC上的传递闭包算法 :'q$emtY  
15.3 图的连通分量 |%XcI3@*  
    基于传递闭包的算法 &|'yq zS3  
    基于顶点合并的算法 b=sY%(2s  
15.4 图的最短路径 s"$K2k;J  
    基于矩阵乘积的算法原理 t&x\@p9  
    计算示例 +]wM$
bP  
15.5 图的最小生成树 M(\{U"%@?  
    SIMD-EREW模型上的Prim算法 m-~3c]pA  
    算法的时间分析 3]}RjOTU  
Ch18 随机算法 ~bzac2Rp  
18.1 引言 mb3aUFxA;  
    基本知识：随机算法的定义、分类、重复性定律 "|&3z/AUh  
    时间复杂性度量 4=y&}3om(0  
    设计方法 'ks .TS&  
18.2 低度顶点部分独立集 yXEI%2~)  
    串行算法  o4yl3o  
    随机并行算法及其正确性证明 (w"(RM~  
18.5 多项式恒等的验证 6pC1C.  
    基本原理和方法 pih 0ME}z  
    矩阵乘积的验证原理 Pq{p\Qkj  
18.8 格点逼近问题(略) @\oZ2sB  
18.9 SAT问题的异步随机并行算法(略) x}WP1YyT~  
Ch20 模型与下界 y.8nzlkE{  
20.1不同的PRAM模型的相互模拟 Tu}EAr  
    PRAM-EREW模拟PPRAM-CRCW };P=|t(r  
    PRAM-CRCW之间的模拟 8a8D0}'  
20.2下界 ofz?L#:2  
    算法研究的两个方向：优化（上界）、可能性（下界） km^ZF<.@  
    Gates的工作 X6w+L?A  
    理想的PRAM模型与下界 fY78  
    PRAM模型的下界 BOA7@Zaa$p  
20.3 NP完全理论导引(略) %2\Pe 2Z  
20.4 P完全理论(略)