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

《并行算法》课程总结与复习 TwFb%YM  
Ch1 并行算法基础 O]{*( J/t  
1.1 并行计算机体系结构 g z61FW  
    并行计算机的分类 Wc|z7P~',%  
    SISD,SIMD,MISD,MIMD； _wh
F^g8  
    SIMD,PVP,SMP,MPP,COW,DSM Spgg+; 9  
    并行计算机的互连方式 M|r8KW~S)  
    静态：LA(LC),MC,TC,MT,HC,BC,SE K-(;D4/sQE  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) wmYv
D<  
1.2 并行计算模型 d#\W hRE  
    PRAM模型：SIMD-SM， rk,p!}FqL  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW U$'y_}V  
    SIMD-IN模型：SIMD-DM "EH,J  
    异步APRAM模型：MIMD-SM LgHJo-+>  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 <xlm K(  
    LogP模型：MIMD-DM，点到点通讯 nwf7M#3d  
1.3 并行算法的一般概念 K@r*;T  
    并行算法的定义 ce'TYkPM  
    并行算法的表示 ><Uk*mwL  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 D1Yh,P<CF\  
    并行算法的WT表示：Brent定理、WT最优 1TRN~#ix  
    加速比性能定律(略) &&PgOFD  
    并行算法的同步和通讯(略) XDYosC:  
Ch2 并行算法的基本设计技术 p
5<2N  
2.1 并行算法的三种基本设计方法 I7 m
G/  
2.2 基本设计技术 F_ljx  
    平衡树方法：求最大值、计算前缀和 c3k|G<C2  
    倍增技术：表序问题、求森林的根 T~s}Nx#  
    分治策略：FFT分治算法 Wsm`YLYkt!  
    划分原理： Z;b
+>2oL  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) E*|tOj9`1n  
    流水线技术：五点的DFT计算，Systolic算法 Z@J.1SaB  
    加速级联(略) B*@6xS[IL  
    破对称技术 7>-yaL{  
Ch3 比较器网络上的排序和选择算法 jO)&KEh  
3.1 Batcher归并和排序 7&6Y  
    0-1原理的证明(略) i&Kz*,pt  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) ',mW`ZN  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) )+Y&4Qu  
    Batcher排序网络：原理、种类和复杂性 o4)hxs  
3.2 (m, n)-选择网络 /#t&~E_|  
    分组选择网络 7Dt"
]o"+  
    平衡分组选择网络及其改进 )saR0{e0N  
Ch4 排序和选择的同步算法 Z+idLbIs  
4.1 一维线性阵列上的并行排序算法(略) 1^{`lK~2  
4.2 二维Mesh上的并行排序算法 40K2uT{cq  
    ShearSort排序算法 e.;M.8N#SQ  
    Thompson&Kung双调排序算法及其计算示例 :oa9#
c`L  
4.3 Stone双调排序算法(略) p|VcMxT 9-  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析
"mZ.V  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 )=H{5&e#u  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 nGa1a  
Ch5 排序和选择的异步和分布式算法(略) <qY5SV,  
5.1 MIMD-CREW模型上的异步枚举排序算法 CLK^gZ
 
5.2 MIMD-TC模型上的异步快排序算法 '29WscU  
5.3分布式k-选择算法 +1@AGJU3  
Ch6 并行搜索 NWKi ()nA%  
6.1 单处理器上的搜索(略) +ld;k/  
6.2 SIMD共享存储模型上有序表的搜索：算法 9<cOYY  
6.3 SIMD共享存储模型上随机序列的搜索：算法 SrZ50Se  
6.4 树连接的SIMD模型上随机序列的搜索：算法 e@jfIF0=}  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 D4Sh9
:\  
Ch8 数据传输与选路 l{%a&/  
8.1 引言 -g~~]K%  
    信包传输性能参数 6P+DnS[]  
    维序选路(X-Y选路、E-立方选路) S< x:t(  
    选路模式及其传输时间公式 fNoR\5}!  
8.2 单一信包一到一传输 6tdI6  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) -e*BqH2t  
8.3 一到多播送 D/s?i[lb  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 ?
,% TU&Yn  
8.4 多到多播送 4<}A]BQVkJ  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Y6VQ:glDT-  
8.5 贪心算法(书8.2) 8p=>?wG  
    二维阵列上的贪心算法 cyMs(21  
    蝶形网上的贪心算法 OCW+?B;  
8.6 随机和确定的选路算法(书8.3)(略) k18$JyaG  
Ch12矩阵运算 F]5\YYXO  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分
~zyQ('  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 ]{Ek[Av  
12.3 矩阵向量乘法 0QoLS|voA/  
    带状划分的算法及其时间分析 ,qy&|4Jz  
    棋盘划分的算法及其时间分析 FpzP#;  
    Systolic算法(略) x,1=D~L}  
12.4 矩阵乘法 EUZq$@uWL  
    简单并行分块算法 ^s*\Qw{Ii  
    Cannon算法及其计算示例 m!Af LSlwm  
    Fox算法及其计算示例 FpdHnu i1  
    DNS算法及其计算示例 D rTM $)  
    Systolic算法(略) (1 yGg==W.  
Ch13 数值计算 ~4^p}{  
13.1 稠密线性方程组求解 <gcmsiB|  
    SIMD-CREW的上三角方程组回代算法 Wp
4K6x  
    SIMD-CREW上的Gauss-Jordan算法 >zR14VO`_|  
    MIMD-CREW上的Gauss-Seidel算法 $e1:Q#den2  
13.2 稀疏线性方程组的求解 w_H2gaQ  
    三对角方程组的奇偶规约求解法 ]ymC3LV]  
    Gauss-Seidel迭代法的红黑着色并行算法 z8tl
0gd%D  
13.3 非线性方程的求根(略) fq(5Lfe}  
Ch14 快速傅立叶变换FFT (H-cDsh;c  
14.1 快速傅里叶变换(FFT) p1^
0{ILx  
    离散傅里叶变换(DFT) -<
d(  
    串行FFT递归算法及其计算原理 6eo4#/+%  
    串行FFT蝶式计算及其蝶式计算流图 f9F2U )  
14.2 DFT直接并行算法 >Bx8IO1_\d  
    SIMD-MT上的并行DFT算法(略) ucM.Ro=@  
14.3 并行FFT算法 l $w/Fz  
    SIMD-MC上的FFT算法(略) ~#t*pOC5BR  
    SIMD-BF上的FFT算法及其时间分析 InN{^uN  
Ch15 图论算法 @T/qd>T o  
15.1 图的并行搜索 hiIyaWU  
    p-深度优先搜索及其计算示例 4 P f+]R  
    p-宽深优先搜索及其计算示例 idz9YpW  
    p-宽度优先搜索及其计算示例 OA5f}+  
15.2 图的传递闭包 XLocg  
    基于布尔矩阵乘积的算法原理 R9r)C{63S&  
    计算示例 \*J.\f  
    SIMD-CC上的传递闭包算法 ^Rk^XQCh  
15.3 图的连通分量 9R>~~~{-Go  
    基于传递闭包的算法 !"%S#nrL$  
    基于顶点合并的算法 #@ q1Ko!NZ  
15.4 图的最短路径 M#T#:wf~  
    基于矩阵乘积的算法原理 ,@479ZvvR3  
    计算示例 w-M7opkq  
15.5 图的最小生成树 J eL~]F  
    SIMD-EREW模型上的Prim算法 \eT/%$  
    算法的时间分析 )tCx5 9  
Ch18 随机算法 @x*.5:[  
18.1 引言 #XfT1  
    基本知识：随机算法的定义、分类、重复性定律 ]h0Y8kpd  
    时间复杂性度量 }9 ?y'6l  
    设计方法 xjE7DCmA  
18.2 低度顶点部分独立集 Gj*SPU  
    串行算法 gz#+  
    随机并行算法及其正确性证明 ys/vI/e\  
18.5 多项式恒等的验证 Zq^^|[)bA  
    基本原理和方法 Eh:yRJ_8  
    矩阵乘积的验证原理 zv,\@Z9.($  
18.8 格点逼近问题(略) vLr&ay!w  
18.9 SAT问题的异步随机并行算法(略) 8'n#O>V@  
Ch20 模型与下界 K` 2i  
20.1不同的PRAM模型的相互模拟 i"vDRrDe  
    PRAM-EREW模拟PPRAM-CRCW +<z7ds{Z  
    PRAM-CRCW之间的模拟 :ET x*c  
20.2下界 8cB=}XgYS  
    算法研究的两个方向：优化（上界）、可能性（下界） \6Xn]S
 
    Gates的工作 }tu4z+T2  
    理想的PRAM模型与下界 =#jTo|~u4o  
    PRAM模型的下界 ` 4OMZMq  
20.3 NP完全理论导引(略) $4sAnu]  
20.4 P完全理论(略)