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

《并行算法》课程总结与复习 >Gd.&flSj
 
Ch1 并行算法基础 N_'+B+U?  
1.1 并行计算机体系结构 [S Tj
e8+V  
    并行计算机的分类 cK}Pf+r>  
    SISD,SIMD,MISD,MIMD； K^D82tP  
    SIMD,PVP,SMP,MPP,COW,DSM A!HK~yk~Q  
    并行计算机的互连方式 [!+D<Y  
    静态：LA(LC),MC,TC,MT,HC,BC,SE d.}}s$Q  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) Lt<oi8'N   
1.2 并行计算模型 S=9E@(]  
    PRAM模型：SIMD-SM， nk08>veG  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW vo;5f[>4i  
    SIMD-IN模型：SIMD-DM z[#6-T &  
    异步APRAM模型：MIMD-SM ya>N
.h  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 Y^eX@dEFR  
    LogP模型：MIMD-DM，点到点通讯 x`2p
r
 
1.3 并行算法的一般概念 wixD\t59X  
    并行算法的定义 NhlJ3/J j  
    并行算法的表示 Sr7@buF  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 ZQLB`n@  
    并行算法的WT表示：Brent定理、WT最优 Y@:3 B:m#  
    加速比性能定律(略) $MT}l  
    并行算法的同步和通讯(略) )kA2vX^=Z  
Ch2 并行算法的基本设计技术 cju@W] !  
2.1 并行算法的三种基本设计方法 WB;
J1TpM7  
2.2 基本设计技术 ![H
hxu  
    平衡树方法：求最大值、计算前缀和 7,su f }=  
    倍增技术：表序问题、求森林的根 A:xb!= 2  
    分治策略：FFT分治算法 /'`6 ; uRN  
    划分原理： w%~qB5wF6  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) Nh :JU?h  
    流水线技术：五点的DFT计算，Systolic算法 ;_bq9x  
    加速级联(略) z@n+7p`w  
    破对称技术 VVN# $  
Ch3 比较器网络上的排序和选择算法 6m\*]nOy4  
3.1 Batcher归并和排序 kI]=&Rw  
    0-1原理的证明(略) XWf7"]%SX  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) yI *M[0  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) ndB@J*Im
u  
    Batcher排序网络：原理、种类和复杂性 6i^0T
 
3.2 (m, n)-选择网络 _32/WQF6  
    分组选择网络 +}\29@{
W  
    平衡分组选择网络及其改进 8}J(c=4Gk  
Ch4 排序和选择的同步算法 ?^eJ:  
4.1 一维线性阵列上的并行排序算法(略) MsSoX9A{D  
4.2 二维Mesh上的并行排序算法 LP8o7%sv!  
    ShearSort排序算法 &F9OZMK=  
    Thompson&Kung双调排序算法及其计算示例 @!,D%]8"  
4.3 Stone双调排序算法(略) ] &
/0  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 !+%Az*ik  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 \}n !yYh(  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 v5P*<U Ax  
Ch5 排序和选择的异步和分布式算法(略) "@aq@mY@  
5.1 MIMD-CREW模型上的异步枚举排序算法 ,d3Q+9/  
5.2 MIMD-TC模型上的异步快排序算法 ipgN<|`?@  
5.3分布式k-选择算法 *c!;^Qyp&  
Ch6 并行搜索 z^YeMe  
6.1 单处理器上的搜索(略) C8!8u?k  
6.2 SIMD共享存储模型上有序表的搜索：算法 BJ_+z gf`  
6.3 SIMD共享存储模型上随机序列的搜索：算法 5F% h>tqh  
6.4 树连接的SIMD模型上随机序列的搜索：算法 ^ n6)YX  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 $@5%5  
Ch8 数据传输与选路 Qd9-u)L<  
8.1 引言 (9Fabo\SH  
    信包传输性能参数 (R9QBZP5  
    维序选路(X-Y选路、E-立方选路) 3(cU )  
    选路模式及其传输时间公式 Q:'qw#P/C  
8.2 单一信包一到一传输 Tz+HIUIxF  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) -[i40 1  
8.3 一到多播送 c13vEn!c  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 f ho=<|-  
8.4 多到多播送 4r68`<mn[  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 61ON  
8.5 贪心算法(书8.2) H9oXZSm  
    二维阵列上的贪心算法 &/J.0d-*``  
    蝶形网上的贪心算法 {mC KTyN+  
8.6 随机和确定的选路算法(书8.3)(略) +1E?He:iQ  
Ch12矩阵运算 uz zWZ9Tv  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 Q#yu(  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 xI. Orpw  
12.3 矩阵向量乘法 Fi?U)T+%+  
    带状划分的算法及其时间分析 JLFFh!J  
    棋盘划分的算法及其时间分析 XwHu:v'=  
    Systolic算法(略) P3,Z5| )  
12.4 矩阵乘法 Q
2_WH)J 3  
    简单并行分块算法 Cg]3(3   
    Cannon算法及其计算示例 k"3Z@Px :  
    Fox算法及其计算示例 l`~a}y"n  
    DNS算法及其计算示例 8|S1|t,  
    Systolic算法(略) yi AG' [  
Ch13 数值计算 ]noP  
13.1 稠密线性方程组求解 rA1zyZlz  
    SIMD-CREW的上三角方程组回代算法 +[X.-,yW  
    SIMD-CREW上的Gauss-Jordan算法 6\)8mK  
    MIMD-CREW上的Gauss-Seidel算法 0,"n-5Im  
13.2 稀疏线性方程组的求解 {LMS~nx  
    三对角方程组的奇偶规约求解法 Hz!
U_?  
    Gauss-Seidel迭代法的红黑着色并行算法 hX'z]Am<  
13.3 非线性方程的求根(略) Sug~FV?k$e  
Ch14 快速傅立叶变换FFT ?C#F?N0  
14.1 快速傅里叶变换(FFT) O>b&-U"R  
    离散傅里叶变换(DFT) /`j K  
    串行FFT递归算法及其计算原理 t`Y1.]@U  
    串行FFT蝶式计算及其蝶式计算流图 NejsI un%  
14.2 DFT直接并行算法 L8?Z!0D/h  
    SIMD-MT上的并行DFT算法(略) "x=@,*Bk  
14.3 并行FFT算法 c^dl+-{Mc  
    SIMD-MC上的FFT算法(略) '^.=gTk  
    SIMD-BF上的FFT算法及其时间分析 0%&fUz36E6  
Ch15 图论算法 "PDS qYA  
15.1 图的并行搜索 9rf|r 3  
    p-深度优先搜索及其计算示例 1=o(s IeA  
    p-宽深优先搜索及其计算示例 go%X%Os]  
    p-宽度优先搜索及其计算示例 ./BP+\)lO  
15.2 图的传递闭包 u{E^<fW]  
    基于布尔矩阵乘积的算法原理 e G*s1
uQl  
    计算示例 aP6%OI  
    SIMD-CC上的传递闭包算法 Vp{RX8?.  
15.3 图的连通分量 x1hs19s  
    基于传递闭包的算法 "|l oSf@  
    基于顶点合并的算法 qdkTg:QJ,  
15.4 图的最短路径 zm)CfE F 8  
    基于矩阵乘积的算法原理 WE Svkm;  
    计算示例 ,n,7.m.D  
15.5 图的最小生成树 1rm$@ L  
    SIMD-EREW模型上的Prim算法 ^x1D]+  
    算法的时间分析 <4A(Z$ZX)  
Ch18 随机算法 I+4qu|0lA  
18.1 引言 3bI|X! j  
    基本知识：随机算法的定义、分类、重复性定律 0wE8GmG  
    时间复杂性度量 fY+ .#V  
    设计方法 u!Eu
lAl  
18.2 低度顶点部分独立集 ~pBxFA  
    串行算法  d7-F&!sQ  
    随机并行算法及其正确性证明 G
}
hkr  
18.5 多项式恒等的验证 C`1\$U~%  
    基本原理和方法 4#Nd;gM2  
    矩阵乘积的验证原理 QX~72X=(  
18.8 格点逼近问题(略) O [ ;6E  
18.9 SAT问题的异步随机并行算法(略) ,vY I O  
Ch20 模型与下界 [?r\b  
20.1不同的PRAM模型的相互模拟 6`$z*C2{  
    PRAM-EREW模拟PPRAM-CRCW x?k |i
}Q  
    PRAM-CRCW之间的模拟 * jNu?$  
20.2下界 B(vz$QE,$r  
    算法研究的两个方向：优化（上界）、可能性（下界） HvfTC<+H  
    Gates的工作 <HX-qN
A?  
    理想的PRAM模型与下界 UtW3KvJ#=  
    PRAM模型的下界 Fe>#}-`  
20.3 NP完全理论导引(略) &7y1KwfXn  
20.4 P完全理论(略)