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

《并行算法》课程总结与复习 [7ZFxr\:!  
Ch1 并行算法基础 {^1GHU  
1.1 并行计算机体系结构 @ |6n.'f+  
    并行计算机的分类 -]~&Pi|  
    SISD,SIMD,MISD,MIMD； 29 L~SMf  
    SIMD,PVP,SMP,MPP,COW,DSM cXFNX<  
    并行计算机的互连方式 B t-o:)pa  
    静态：LA(LC),MC,TC,MT,HC,BC,SE 8xs[{?|:  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) DmM<Kkg.J  
1.2 并行计算模型 FylL7n  
    PRAM模型：SIMD-SM， DF-`nD  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW 5vj;lJKcd`  
    SIMD-IN模型：SIMD-DM %kS+n_*  
    异步APRAM模型：MIMD-SM \]e"#"v}}_  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 ~&4Hc%*IB  
    LogP模型：MIMD-DM，点到点通讯 f ."bq43(  
1.3 并行算法的一般概念 ^\Nsx)Y;  
    并行算法的定义 tI|?k(D  
    并行算法的表示  #:_qo  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 N W :_)1  
    并行算法的WT表示：Brent定理、WT最优 ;t{Ew+s  
    加速比性能定律(略) nR-`;lrF~  
    并行算法的同步和通讯(略) Jiyt,D*wX  
Ch2 并行算法的基本设计技术 1-r#v  
2.1 并行算法的三种基本设计方法 ;|6kFBGC"+  
2.2 基本设计技术 y8'WR-;  
    平衡树方法：求最大值、计算前缀和 Lg0Vn&k  
    倍增技术：表序问题、求森林的根 1O>wXq7q  
    分治策略：FFT分治算法 x*Y&s<  
    划分原理： 9>\P]:  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) ^I=c]D]);  
    流水线技术：五点的DFT计算，Systolic算法 s!esk%h{K  
    加速级联(略) 19Xc0ez  
    破对称技术 #5-5N5-1  
Ch3 比较器网络上的排序和选择算法 |7XSC,"  
3.1 Batcher归并和排序 mr dG-t(k  
    0-1原理的证明(略) D's'LspQ  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) M9'Qs m  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) *{8<4CVv  
    Batcher排序网络：原理、种类和复杂性 C` ?6`$Y  
3.2 (m, n)-选择网络 YUU |!A8x  
    分组选择网络 /fC @T  
    平衡分组选择网络及其改进 DFKFsu8s  
Ch4 排序和选择的同步算法 GxE"q-G  
4.1 一维线性阵列上的并行排序算法(略) Pw i6Ly`  
4.2 二维Mesh上的并行排序算法 6X2>zUHR  
    ShearSort排序算法 _Mq0QQ42  
    Thompson&Kung双调排序算法及其计算示例 v'nM=   
4.3 Stone双调排序算法(略) iU3)4(R  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 B7r={P!0  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 BayO+,>K
 
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 \?uaHX`1  
Ch5 排序和选择的异步和分布式算法(略) y57]q#k  
5.1 MIMD-CREW模型上的异步枚举排序算法 eFDhJ  
5.2 MIMD-TC模型上的异步快排序算法 jY>|>]4X  
5.3分布式k-选择算法 ~wG.'d]  
Ch6 并行搜索 QWVH4rg  
6.1 单处理器上的搜索(略) #eSVFD5ZU  
6.2 SIMD共享存储模型上有序表的搜索：算法 7L~LpB  
6.3 SIMD共享存储模型上随机序列的搜索：算法 ?w'a^+H  
6.4 树连接的SIMD模型上随机序列的搜索：算法 EQZu-S`kv  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 1,@-y#V_  
Ch8 数据传输与选路 mUW|4zl i}  
8.1 引言 Vj?{T(K1[  
    信包传输性能参数 Trd/\tX#v&  
    维序选路(X-Y选路、E-立方选路) hz#S b~g  
    选路模式及其传输时间公式 +E8\g  
8.2 单一信包一到一传输  .b] 32Ww  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) {! 5"Y(>X  
8.3 一到多播送 XQC
u\\>;  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 K..L8#SC  
8.4 多到多播送 R^zTgyr  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 0CXh|AU  
8.5 贪心算法(书8.2) 'Okitq+O  
    二维阵列上的贪心算法 Cb}hE ro  
    蝶形网上的贪心算法 weQC9e~d{-  
8.6 随机和确定的选路算法(书8.3)(略) H
':dLR  
Ch12矩阵运算 (?MRbX]@  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 mq~rD)T  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 (ov=D7>t0  
12.3 矩阵向量乘法 [@D+kL*>  
    带状划分的算法及其时间分析 {l&6=z  
    棋盘划分的算法及其时间分析 zt/p'khP3  
    Systolic算法(略) fdr.'aMf%  
12.4 矩阵乘法 G<.p".o4  
    简单并行分块算法 {XYv&K  
    Cannon算法及其计算示例 KQsS)ju  
    Fox算法及其计算示例 M$O}roOa  
    DNS算法及其计算示例 4-^LC<}k  
    Systolic算法(略)  _Y@'<S.  
Ch13 数值计算 @}@`lv65}  
13.1 稠密线性方程组求解 W]|;ZzZ=m  
    SIMD-CREW的上三角方程组回代算法 1M&n=s _  
    SIMD-CREW上的Gauss-Jordan算法 =x "N0p  
    MIMD-CREW上的Gauss-Seidel算法 FG8genCH@  
13.2 稀疏线性方程组的求解 ]/;0  
    三对角方程组的奇偶规约求解法 Ve>*KHDSt  
    Gauss-Seidel迭代法的红黑着色并行算法 Zyqh
  
13.3 非线性方程的求根(略) FY"!%)TV  
Ch14 快速傅立叶变换FFT )mO|
1IDTN  
14.1 快速傅里叶变换(FFT) 6L@g]f|Y@  
    离散傅里叶变换(DFT) "dwx;E  
    串行FFT递归算法及其计算原理 W2 h^ShG  
    串行FFT蝶式计算及其蝶式计算流图 Qg  
14.2 DFT直接并行算法 V
.J[Uwf  
    SIMD-MT上的并行DFT算法(略) A S;ra,x  
14.3 并行FFT算法 SZJ~ktXC-V  
    SIMD-MC上的FFT算法(略) Eugt~j3  
    SIMD-BF上的FFT算法及其时间分析 7SYU^GD  
Ch15 图论算法 @;x|+@ r  
15.1 图的并行搜索 DV +DJcF  
    p-深度优先搜索及其计算示例 (_-<3)q4  
    p-宽深优先搜索及其计算示例 hBDPz1<  
    p-宽度优先搜索及其计算示例 gsufd{{  
15.2 图的传递闭包 ' U{?"FP  
    基于布尔矩阵乘积的算法原理 YhFB*D;  
    计算示例 l i }4d+  
    SIMD-CC上的传递闭包算法 k V"'; a  
15.3 图的连通分量 Y1EN|!WZ  
    基于传递闭包的算法 |0n h  
    基于顶点合并的算法 (qHI>3tpY  
15.4 图的最短路径 Sai_rNRWB  
    基于矩阵乘积的算法原理 -fVeE<[  
    计算示例 mzTF2K  
15.5 图的最小生成树 \p1H" A  
    SIMD-EREW模型上的Prim算法 qJB9z0a<Ov  
    算法的时间分析 \^SL Zhe  
Ch18 随机算法 mIq6\c$  
18.1 引言 HH+NNSR
O  
    基本知识：随机算法的定义、分类、重复性定律 By6C+)up  
    时间复杂性度量 <I'kJ{"
 
    设计方法 =K{$?%"  
18.2 低度顶点部分独立集 -QCo]:cp  
    串行算法 i}ypEp  
    随机并行算法及其正确性证明 L+bO X  
18.5 多项式恒等的验证
ovzIJbf  
    基本原理和方法 UZMo(rG.]{  
    矩阵乘积的验证原理 pmB}a7  
18.8 格点逼近问题(略) u*{hXR-"  
18.9 SAT问题的异步随机并行算法(略) _WtX8  
Ch20 模型与下界 cEi{+rfZd|  
20.1不同的PRAM模型的相互模拟 RfDIwkpp  
    PRAM-EREW模拟PPRAM-CRCW z,}1K!  
    PRAM-CRCW之间的模拟 P1=bbMk  
20.2下界 6 +^V  
    算法研究的两个方向：优化（上界）、可能性（下界） ?2OT:/I,  
    Gates的工作 C\dQ6(3}\  
    理想的PRAM模型与下界 NWNH)O@  
    PRAM模型的下界 inZMq(_@$  
20.3 NP完全理论导引(略) -'3vQXj&  
20.4 P完全理论(略)