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

《并行算法》课程总结与复习 \d
:Q%S  
Ch1 并行算法基础 kQI'kL8>  
1.1 并行计算机体系结构 :{<|,3oNdR  
    并行计算机的分类 bfeTf66c  
    SISD,SIMD,MISD,MIMD； :r{-:   
    SIMD,PVP,SMP,MPP,COW,DSM {GtX:v#  
    并行计算机的互连方式 C.4(8~Y=~  
    静态：LA(LC),MC,TC,MT,HC,BC,SE Km
x4bp4  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) &._"rhz  
1.2 并行计算模型 FqyxvL.  
    PRAM模型：SIMD-SM， :X":>M;;+  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW @ws&W=NQ  
    SIMD-IN模型：SIMD-DM kRggVRM  
    异步APRAM模型：MIMD-SM sssw(F  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 P^o@x,V!&  
    LogP模型：MIMD-DM，点到点通讯 ](I||JJa9f  
1.3 并行算法的一般概念 0%xb):Ctw  
    并行算法的定义 *X3wf` C?  
    并行算法的表示 Jd ` Qa+  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 K1YxF  
    并行算法的WT表示：Brent定理、WT最优 WBKf)A^S  
    加速比性能定律(略) Bor_(eL^
 
    并行算法的同步和通讯(略) ]@y%j'e  
Ch2 并行算法的基本设计技术 o(}%b8 K  
2.1 并行算法的三种基本设计方法 N_Ezp68Fp  
2.2 基本设计技术 xi"ff.  
    平衡树方法：求最大值、计算前缀和 {zd[8TJ~xa  
    倍增技术：表序问题、求森林的根 P,zQl;  
    分治策略：FFT分治算法 4'3;{k$z  
    划分原理： `]]5!U2  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) l4mRNYv)z  
    流水线技术：五点的DFT计算，Systolic算法 nGX3_-U4  
    加速级联(略) |[r7
B*fw  
    破对称技术 =x?WZMO  
Ch3 比较器网络上的排序和选择算法 Yt=)=n  
3.1 Batcher归并和排序 ]Vj($O:  
    0-1原理的证明(略) 4cy,'B  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) DXj>u9*%
 
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) P )oNNY6}  
    Batcher排序网络：原理、种类和复杂性 Kt qOA[6  
3.2 (m, n)-选择网络 o%-KO? YW  
    分组选择网络 PI$i_3N  
    平衡分组选择网络及其改进 U<F|A!Fg  
Ch4 排序和选择的同步算法 ,gpEXUp \  
4.1 一维线性阵列上的并行排序算法(略) e[Vk+Te7  
4.2 二维Mesh上的并行排序算法 0datzEns`  
    ShearSort排序算法 _'G'>X>}WU  
    Thompson&Kung双调排序算法及其计算示例 ]7TOA$Q  
4.3 Stone双调排序算法(略) ]jI<Js*F  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 H_XspiB@  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 trjpq{,[U  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 &:ZR% f  
Ch5 排序和选择的异步和分布式算法(略) y5*z
yd  
5.1 MIMD-CREW模型上的异步枚举排序算法 l-nH  
5.2 MIMD-TC模型上的异步快排序算法 %=*|:v
 
5.3分布式k-选择算法 )w<Z4_!N4s  
Ch6 并行搜索 a6xo U;T  
6.1 单处理器上的搜索(略) Odw'Ua  
6.2 SIMD共享存储模型上有序表的搜索：算法 0=U|7%dOL  
6.3 SIMD共享存储模型上随机序列的搜索：算法 Yj bp:  
6.4 树连接的SIMD模型上随机序列的搜索：算法 7@ g0>1Fz  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 vm;%713#1  
Ch8 数据传输与选路 ?+yM3As9_V  
8.1 引言 3O-vO=D  
    信包传输性能参数 JvvN>bg  
    维序选路(X-Y选路、E-立方选路) L#'XN H "  
    选路模式及其传输时间公式 ;ow)N <Z  
8.2 单一信包一到一传输 oj{CNa  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) MCEHv}W  
8.3 一到多播送 .hG*mXw>  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 }[lP^Qs  
8.4 多到多播送 gjz-CY.hz  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 %x{kd8>u!  
8.5 贪心算法(书8.2) {PxFG<^U  
    二维阵列上的贪心算法 +XO\#$o>W  
    蝶形网上的贪心算法 } )Lz%Z  
8.6 随机和确定的选路算法(书8.3)(略) | ?vm.zp  
Ch12矩阵运算 #\=7
A  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 AIn/v`JeX  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 %1jcY0zEQ  
12.3 矩阵向量乘法 -@_v@]:  
    带状划分的算法及其时间分析 eBxm  
    棋盘划分的算法及其时间分析 (&Lt&i _  
    Systolic算法(略) RzL(Gnb  
12.4 矩阵乘法 <>{m+=gA  
    简单并行分块算法 *5k40?w  
    Cannon算法及其计算示例 4c(Em+4  
    Fox算法及其计算示例 {]}94T~/k  
    DNS算法及其计算示例 9NU0K2S  
    Systolic算法(略) UQ0<sI=  
Ch13 数值计算 MA:5'n  
13.1 稠密线性方程组求解 n6WKk+  
    SIMD-CREW的上三角方程组回代算法 m rnPZf i  
    SIMD-CREW上的Gauss-Jordan算法 :zKMw=  
    MIMD-CREW上的Gauss-Seidel算法 R^/SBrWve  
13.2 稀疏线性方程组的求解 HBOyiIm Q  
    三对角方程组的奇偶规约求解法 ML\>TDt  
    Gauss-Seidel迭代法的红黑着色并行算法 :p: C  
13.3 非线性方程的求根(略) CKK}Z;~:  
Ch14 快速傅立叶变换FFT +Z|3[#W  
14.1 快速傅里叶变换(FFT) q{Z#}|km#  
    离散傅里叶变换(DFT) 9)'f)60^  
    串行FFT递归算法及其计算原理 +K'Hr:(  
    串行FFT蝶式计算及其蝶式计算流图 ySmbX  
14.2 DFT直接并行算法 3)W zX  
    SIMD-MT上的并行DFT算法(略) gd*Gn"  
14.3 并行FFT算法 *$vH]>)p  
    SIMD-MC上的FFT算法(略) LQ# E+id&  
    SIMD-BF上的FFT算法及其时间分析 \|S!g _30m  
Ch15 图论算法 P$z_A8}  
15.1 图的并行搜索 \\FT.e
6  
    p-深度优先搜索及其计算示例 HTOr  
    p-宽深优先搜索及其计算示例 ~pQN#C)CO>  
    p-宽度优先搜索及其计算示例 G*@!M %/  
15.2 图的传递闭包 VWE>w|'  
    基于布尔矩阵乘积的算法原理 |R0f--;  
    计算示例 ccHf+=  
    SIMD-CC上的传递闭包算法 '*b]$5*p  
15.3 图的连通分量 'f-r 6'_ZX  
    基于传递闭包的算法 $0 olqt:  
    基于顶点合并的算法 A#=TR_@:  
15.4 图的最短路径 ;KlYiu  
    基于矩阵乘积的算法原理 w*ans}P7  
    计算示例 Kp`{-dUf  
15.5 图的最小生成树 #0P_\X`E   
    SIMD-EREW模型上的Prim算法 \_ 3>v5k|  
    算法的时间分析 i7Up AHd/  
Ch18 随机算法 Jay"  
18.1 引言 q<dG}aj  
    基本知识：随机算法的定义、分类、重复性定律 R c+olJ^5  
    时间复杂性度量 Qq<@;4  
    设计方法 .5(YL8d  
18.2 低度顶点部分独立集 3f[Yk#"  
    串行算法 aOwjYl[?p  
    随机并行算法及其正确性证明 JLoF!MK}  
18.5 多项式恒等的验证
; Bs~E  
    基本原理和方法 f+h\RE=BGt  
    矩阵乘积的验证原理 k QuEG5n.-  
18.8 格点逼近问题(略) X4 Arn,  
18.9 SAT问题的异步随机并行算法(略) ~L)~p%rbi  
Ch20 模型与下界 hmu>s'  
20.1不同的PRAM模型的相互模拟 ubcB<=xb  
    PRAM-EREW模拟PPRAM-CRCW O3} JOv_  
    PRAM-CRCW之间的模拟 .XJ'2yKof  
20.2下界 {&=+lr_h?  
    算法研究的两个方向：优化（上界）、可能性（下界） &k:xr,N=  
    Gates的工作 sQJ\{'g  
    理想的PRAM模型与下界 @J[@Pu O  
    PRAM模型的下界 p F-Lz<V  
20.3 NP完全理论导引(略) v(1 [n]y  
20.4 P完全理论(略)