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

《并行算法》课程总结与复习 @W+m;4HH  
Ch1 并行算法基础 n 9X:s?B/  
1.1 并行计算机体系结构 z&a>cjt_;  
    并行计算机的分类 3{*nG'@Mal  
    SISD,SIMD,MISD,MIMD； K#>@T<  
    SIMD,PVP,SMP,MPP,COW,DSM ;[,r./XmH  
    并行计算机的互连方式 T4lE-g2%M  
    静态：LA(LC),MC,TC,MT,HC,BC,SE lcqpwSk  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks)
9H6
%\#rw  
1.2 并行计算模型 p}:"@6
  
    PRAM模型：SIMD-SM， lK0pr  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW Q%Fa1h:2&  
    SIMD-IN模型：SIMD-DM o NqIrYH'  
    异步APRAM模型：MIMD-SM % r>v^1Vo  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 xb22:  
    LogP模型：MIMD-DM，点到点通讯 d09qZj>  
1.3 并行算法的一般概念 dum(T  
    并行算法的定义 px>g  
    并行算法的表示 .FWi$B';  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 JMVh\($,x  
    并行算法的WT表示：Brent定理、WT最优 T_NN.Ol  
    加速比性能定律(略) WLkfo 6Nw  
    并行算法的同步和通讯(略) (BG wBL  
Ch2 并行算法的基本设计技术 Vu1swq)l  
2.1 并行算法的三种基本设计方法 ,GTIpPj  
2.2 基本设计技术 kX8Ey  
    平衡树方法：求最大值、计算前缀和 agUdPl$e\  
    倍增技术：表序问题、求森林的根 ;cD&qheDV  
    分治策略：FFT分治算法 <#%kmYSL  
    划分原理： U0fr\kM  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) >Nr~ 7s  
    流水线技术：五点的DFT计算，Systolic算法 \F5d p  
    加速级联(略) x4^*YZc$,  
    破对称技术 Wa!}$q+  
Ch3 比较器网络上的排序和选择算法 5JggU  
3.1 Batcher归并和排序 j3&tXZ;F  
    0-1原理的证明(略) W>cH
Z. _  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) <4,LTB]9-  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) ee
\xj$,  
    Batcher排序网络：原理、种类和复杂性 7rSads  
3.2 (m, n)-选择网络 MG(qQ#;j/  
    分组选择网络 a
YrbB#  
    平衡分组选择网络及其改进 .z}*!   
Ch4 排序和选择的同步算法 dO!5`
]  
4.1 一维线性阵列上的并行排序算法(略) i{2ny$55h  
4.2 二维Mesh上的并行排序算法 I|/\L|vo  
    ShearSort排序算法 o|bm=&f  
    Thompson&Kung双调排序算法及其计算示例 V PaW-o  
4.3 Stone双调排序算法(略) Su*f`~G];  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 bv9nDNPD4  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 z( ^ r  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 Z,JoxK2"  
Ch5 排序和选择的异步和分布式算法(略) 716r/@y$6  
5.1 MIMD-CREW模型上的异步枚举排序算法 ck\TTNA  
5.2 MIMD-TC模型上的异步快排序算法 .Hm1ispq  
5.3分布式k-选择算法 D V=xqC6}  
Ch6 并行搜索 wHE1Jqpo  
6.1 单处理器上的搜索(略) @G?R(  
6.2 SIMD共享存储模型上有序表的搜索：算法 Ac8t>;=&  
6.3 SIMD共享存储模型上随机序列的搜索：算法 J|.n bSE  
6.4 树连接的SIMD模型上随机序列的搜索：算法 Ux+UcBKm-  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 Rg\D-F6:  
Ch8 数据传输与选路 v]c+|
nRs  
8.1 引言 :]uz0s`>  
    信包传输性能参数 a_U[!`/w  
    维序选路(X-Y选路、E-立方选路) L7PMam  
    选路模式及其传输时间公式 'tn-o  
8.2 单一信包一到一传输 }I I)<g'  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) >^J
  
8.3 一到多播送 h%8C_mA  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Qv;q*4_  
8.4 多到多播送 bu,xIT^  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 4
;V;8a
\A  
8.5 贪心算法(书8.2) `9 mc+  
    二维阵列上的贪心算法 k~IRds@G  
    蝶形网上的贪心算法 fir#5,*q|  
8.6 随机和确定的选路算法(书8.3)(略) 8Az|SJ<  
Ch12矩阵运算 nUScDb2|  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 vpz l{  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 ~*hCTqHvN  
12.3 矩阵向量乘法 Q9{f'B  
    带状划分的算法及其时间分析 NKMVp/66D  
    棋盘划分的算法及其时间分析 EqF>=5*  
    Systolic算法(略) c!]Q0ib6  
12.4 矩阵乘法 Mk8k,"RG&Z  
    简单并行分块算法 Rh%C$d(  
    Cannon算法及其计算示例 {Lugdf'  
    Fox算法及其计算示例 &EJ/Rl
 
    DNS算法及其计算示例 7}puj%JS /  
    Systolic算法(略) P1dFoQz   
Ch13 数值计算 [E)&dl_k  
13.1 稠密线性方程组求解 0.0r?T  
    SIMD-CREW的上三角方程组回代算法 8f>v[SQ"  
    SIMD-CREW上的Gauss-Jordan算法 ?\_vqW  
    MIMD-CREW上的Gauss-Seidel算法 5,9cD`WR^  
13.2 稀疏线性方程组的求解 =}'7}0M_=  
    三对角方程组的奇偶规约求解法 @`XbM7D 5  
    Gauss-Seidel迭代法的红黑着色并行算法 vQ8$C 3  
13.3 非线性方程的求根(略) 2Ws'3Jz  
Ch14 快速傅立叶变换FFT H^<?h6T  
14.1 快速傅里叶变换(FFT) t|C?=:_  
    离散傅里叶变换(DFT) Mo]a
B:a  
    串行FFT递归算法及其计算原理 wU-Cb<^  
    串行FFT蝶式计算及其蝶式计算流图 ?;GXFKy  
14.2 DFT直接并行算法 ?f:ND1jU  
    SIMD-MT上的并行DFT算法(略) 3{M0iNc1  
14.3 并行FFT算法 B$MHn?  
    SIMD-MC上的FFT算法(略)
L
s'8  
    SIMD-BF上的FFT算法及其时间分析 #rQT)n  
Ch15 图论算法 nPhREn!  
15.1 图的并行搜索 9Us'Q{CD   
    p-深度优先搜索及其计算示例 [a7S?%>Bh  
    p-宽深优先搜索及其计算示例 1w#vy1m J  
    p-宽度优先搜索及其计算示例 7%W@Hr,%F  
15.2 图的传递闭包 Ct]?  /  
    基于布尔矩阵乘积的算法原理 GQ}R
xu]  
    计算示例 ~*L
@|?  
    SIMD-CC上的传递闭包算法 V o%GO9b;  
15.3 图的连通分量 W?0u_F  
    基于传递闭包的算法 vH@$?b3VP  
    基于顶点合并的算法 E//*bmww  
15.4 图的最短路径 )2J#pz?.  
    基于矩阵乘积的算法原理 VM+l9 z>  
    计算示例 A:*$rHbzl  
15.5 图的最小生成树 .jl^"{@ 6  
    SIMD-EREW模型上的Prim算法 &Qt1~#1  
    算法的时间分析 ]0g1P-&,U  
Ch18 随机算法 ^9
XAWj"  
18.1 引言 rLcXo%w  
    基本知识：随机算法的定义、分类、重复性定律 Oyp)Wm;@  
    时间复杂性度量 ~e=KBYDBu  
    设计方法 5K00z?kD2V  
18.2 低度顶点部分独立集 '8b=4mrbH  
    串行算法
F8B:P7I  
    随机并行算法及其正确性证明 Jo9c|\4  
18.5 多项式恒等的验证 EC?U#!kv  
    基本原理和方法 4}Hf"L[ l  
    矩阵乘积的验证原理
$B `bsJ  
18.8 格点逼近问题(略) g$mqAz<  
18.9 SAT问题的异步随机并行算法(略) Job&qW9W`  
Ch20 模型与下界 hYh~[Kr^@^  
20.1不同的PRAM模型的相互模拟
/!-ypIY  
    PRAM-EREW模拟PPRAM-CRCW >u=nGeO  
    PRAM-CRCW之间的模拟 a!:R_P} 7  
20.2下界 T7Yg^ -"  
    算法研究的两个方向：优化（上界）、可能性（下界） ;MjOs&1f0K  
    Gates的工作 Wl3fR[@3Q  
    理想的PRAM模型与下界 a0Q\]S  
    PRAM模型的下界 ;sd] IZ$#  
20.3 NP完全理论导引(略) .T}S[`Yx5  
20.4 P完全理论(略)