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

《并行算法》课程总结与复习 LS}dt?78`V  
Ch1 并行算法基础 ,Y6Me+5B  
1.1 并行计算机体系结构 b `)^Ao:  
    并行计算机的分类 r~N0P|Tq  
    SISD,SIMD,MISD,MIMD； c;
C:$B7  
    SIMD,PVP,SMP,MPP,COW,DSM
]{ ;=<t6  
    并行计算机的互连方式 x>THyY[sq  
    静态：LA(LC),MC,TC,MT,HC,BC,SE l6IpyIex  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) R]L|&{  
1.2 并行计算模型 `uo'w:Q  
    PRAM模型：SIMD-SM， gh>'O/9  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW *J&XM[t  
    SIMD-IN模型：SIMD-DM P]hS0,sE<(  
    异步APRAM模型：MIMD-SM }c?/-ab>  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 H}5zKv.T  
    LogP模型：MIMD-DM，点到点通讯 \WKly  
1.3 并行算法的一般概念 vs}_1o  
    并行算法的定义 :\[W]  
    并行算法的表示 $Kw)BnV  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 )D?\ru H  
    并行算法的WT表示：Brent定理、WT最优 f.SV-{O_  
    加速比性能定律(略) uSh!A  
    并行算法的同步和通讯(略) huVw+vAA  
Ch2 并行算法的基本设计技术 ~7a(KJgvd"  
2.1 并行算法的三种基本设计方法 O&h3=?O&B  
2.2 基本设计技术 p(dJf&D  
    平衡树方法：求最大值、计算前缀和 )* 5R/oy,  
    倍增技术：表序问题、求森林的根 F/G fEMSE  
    分治策略：FFT分治算法 "|<6bA  
    划分原理： 5=]q+&y\H  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) xDv 5'IGBb  
    流水线技术：五点的DFT计算，Systolic算法 ".ay
pD)W  
    加速级联(略) MR:GH.uM:  
    破对称技术 (3PkTQlE  
Ch3 比较器网络上的排序和选择算法 Ws2SD6!4`  
3.1 Batcher归并和排序 /Xa_Xg7  
    0-1原理的证明(略) Q(Q.(  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) uLFnuK  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) {@j0?s  
    Batcher排序网络：原理、种类和复杂性 1NJ,If]  
3.2 (m, n)-选择网络 :6R0=oz  
    分组选择网络 M->/ vi  
    平衡分组选择网络及其改进 s>y=-7:N  
Ch4 排序和选择的同步算法 %J)n#\  
4.1 一维线性阵列上的并行排序算法(略) o&M2POI~q  
4.2 二维Mesh上的并行排序算法 $@]tTz;b  
    ShearSort排序算法 LObS 7U  
    Thompson&Kung双调排序算法及其计算示例 .1F(-mLd  
4.3 Stone双调排序算法(略) $gKMVgD"  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 [Y@?l]&  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 rHhn)m  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 H"v3?g`S%  
Ch5 排序和选择的异步和分布式算法(略) 2de[ yz  
5.1 MIMD-CREW模型上的异步枚举排序算法 QEd>T"@g  
5.2 MIMD-TC模型上的异步快排序算法 k&Z3v.  
5.3分布式k-选择算法 l+# l\q%l  
Ch6 并行搜索 ] ;@"-H  
6.1 单处理器上的搜索(略) m e\S:  
6.2 SIMD共享存储模型上有序表的搜索：算法 V?KACYd@O  
6.3 SIMD共享存储模型上随机序列的搜索：算法 f5)4H  
6.4 树连接的SIMD模型上随机序列的搜索：算法 P}=u8(u  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 &S\q* H=}i  
Ch8 数据传输与选路 IYtM'!u  
8.1 引言 Z0yy<9q]2  
    信包传输性能参数 D$k<<dv v
 
    维序选路(X-Y选路、E-立方选路) dQhh,}  
    选路模式及其传输时间公式 8J60+2Wa  
8.2 单一信包一到一传输 f<!3vA
h  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) OyTEd5\3  
8.3 一到多播送 t- Rp_2t  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 ;Od;q]G7L  
8.4 多到多播送 q2qbbQ6H  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 YS$?Wz  
8.5 贪心算法(书8.2) o_un=ygU  
    二维阵列上的贪心算法 lWYZAF>?Ym  
    蝶形网上的贪心算法 ?NazfK  
8.6 随机和确定的选路算法(书8.3)(略) ^:JZ.r  
Ch12矩阵运算 VUfV=&D-*g  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 hdFIriE3  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 L,I5/K6  
12.3 矩阵向量乘法 GyE-fB4C  
    带状划分的算法及其时间分析 7nh,j <~;2  
    棋盘划分的算法及其时间分析 nxzdg5A(w  
    Systolic算法(略) P#`Mg@.  
12.4 矩阵乘法 ?sb O b  
    简单并行分块算法 6
#NptXB  
    Cannon算法及其计算示例 XqD/~_z;  
    Fox算法及其计算示例 e}qG _*  
    DNS算法及其计算示例 fV[(s7vW  
    Systolic算法(略) A aLj.HR  
Ch13 数值计算 5<-_"/_  
13.1 稠密线性方程组求解 j~
+<~2%c  
    SIMD-CREW的上三角方程组回代算法 ,3^gB,ka  
    SIMD-CREW上的Gauss-Jordan算法 ;g[C=yhK`C  
    MIMD-CREW上的Gauss-Seidel算法 n[zP}YRr  
13.2 稀疏线性方程组的求解 79:Wo>C3-  
    三对角方程组的奇偶规约求解法 YmP`Gg#>p  
    Gauss-Seidel迭代法的红黑着色并行算法 & i,on6  
13.3 非线性方程的求根(略) esCm`?qCP  
Ch14 快速傅立叶变换FFT ,Y~{RgG  
14.1 快速傅里叶变换(FFT) oXA3i  
    离散傅里叶变换(DFT) v ?b9TE  
    串行FFT递归算法及其计算原理 qTK\'trgx]  
    串行FFT蝶式计算及其蝶式计算流图 /]=dPb%  
14.2 DFT直接并行算法 & [)1LRt_  
    SIMD-MT上的并行DFT算法(略) as\6XW$;Q  
14.3 并行FFT算法 x\ieWF1  
    SIMD-MC上的FFT算法(略) -uZ bVd  
    SIMD-BF上的FFT算法及其时间分析 neW_mu;~Z  
Ch15 图论算法
<b74L  
15.1 图的并行搜索 b&.j>=  
    p-深度优先搜索及其计算示例 9z9z
:PU  
    p-宽深优先搜索及其计算示例 8>.l4:`  
    p-宽度优先搜索及其计算示例 ,: X+NQ  
15.2 图的传递闭包 S4]}/Imn)  
    基于布尔矩阵乘积的算法原理 j?Ki<MD1  
    计算示例 [u[`!L=  
    SIMD-CC上的传递闭包算法 u}u;jTi>2  
15.3 图的连通分量 *0ZL@Kw  
    基于传递闭包的算法 @MIBW)P<  
    基于顶点合并的算法 [KXxn>n  
15.4 图的最短路径 #~um F%#  
    基于矩阵乘积的算法原理 3ThCY`  
    计算示例 [Af&K22M(X  
15.5 图的最小生成树 P+pL2BA  
    SIMD-EREW模型上的Prim算法 a~YFJAkg9  
    算法的时间分析 & f7{3BK  
Ch18 随机算法 ,eq[X\B>  
18.1 引言 gd'#K~?  
    基本知识：随机算法的定义、分类、重复性定律 Xv3u}nPMq  
    时间复杂性度量 hNB;29r~  
    设计方法 e*_8B2da  
18.2 低度顶点部分独立集 )@.
bkzW  
    串行算法 4?XX_=+F|  
    随机并行算法及其正确性证明 _[8xq:G  
18.5 多项式恒等的验证 &fA`Od6l"  
    基本原理和方法 qq}EXq^  
    矩阵乘积的验证原理 0S@O]k)  
18.8 格点逼近问题(略) \3dMA_5  
18.9 SAT问题的异步随机并行算法(略) PT4Xr=z =  
Ch20 模型与下界 f9H;e(D9]  
20.1不同的PRAM模型的相互模拟 tr"iluwGc  
    PRAM-EREW模拟PPRAM-CRCW aNb=gjLpt  
    PRAM-CRCW之间的模拟 [dFxW6n  
20.2下界 [oOZ6\?HB  
    算法研究的两个方向：优化（上界）、可能性（下界） B9|!8V  
    Gates的工作 <lZyUd  
    理想的PRAM模型与下界 d{&+xl^ll  
    PRAM模型的下界 K^tM$l\  
20.3 NP完全理论导引(略) # 'G/&&<  
20.4 P完全理论(略)