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

《并行算法》课程总结与复习 l[oe*aYN7  
Ch1 并行算法基础 &qKigkLd  
1.1 并行计算机体系结构 |4fF T `  
    并行计算机的分类 \x(^]/@  
    SISD,SIMD,MISD,MIMD； RkA8  
    SIMD,PVP,SMP,MPP,COW,DSM FqZgdmwR  
    并行计算机的互连方式 H:
Y&OZ  
    静态：LA(LC),MC,TC,MT,HC,BC,SE :RiF3h(  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) 2 x32U MD  
1.2 并行计算模型 APq7 f8t  
    PRAM模型：SIMD-SM， ,EI:gLH  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW e)b%`ntF  
    SIMD-IN模型：SIMD-DM {[W(a<%bXm  
    异步APRAM模型：MIMD-SM Q|c|2byb  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 mp1ttGUtM  
    LogP模型：MIMD-DM，点到点通讯 N=~~EtX  
1.3 并行算法的一般概念 Oaa"T8t  
    并行算法的定义 ! %Ny0JkO  
    并行算法的表示 z_&P?+"Df  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 'SV7$,mK@  
    并行算法的WT表示：Brent定理、WT最优 x+7*ADKb  
    加速比性能定律(略) ?lKhzH.T  
    并行算法的同步和通讯(略) %\6Q .V#s  
Ch2 并行算法的基本设计技术 !OAvD#  
2.1 并行算法的三种基本设计方法 [>Fm[5x
 
2.2 基本设计技术 ^B]@Lr E^  
    平衡树方法：求最大值、计算前缀和 {dzoEM[ 1s  
    倍增技术：表序问题、求森林的根 L;/n!k.A  
    分治策略：FFT分治算法 ^$NJD  
    划分原理： 76@qHTh}  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) (MLhaux-  
    流水线技术：五点的DFT计算，Systolic算法 tj5giQ3DG)  
    加速级联(略) ?9xu{B>6  
    破对称技术 m4m<nnM  
Ch3 比较器网络上的排序和选择算法 S v`qB'e2  
3.1 Batcher归并和排序 4 b,N8  
    0-1原理的证明(略) OZ(dpV9.S  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) SSA W52xC  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) $k%Z$NSN=  
    Batcher排序网络：原理、种类和复杂性 &JhX+'U  
3.2 (m, n)-选择网络 [*4fwk^  
    分组选择网络 ]l;*$2w)  
    平衡分组选择网络及其改进 WNy3@+@GZ  
Ch4 排序和选择的同步算法 A)NkT`<)  
4.1 一维线性阵列上的并行排序算法(略) n}nEcXb  
4.2 二维Mesh上的并行排序算法 "![L#)"s  
    ShearSort排序算法 ~Xv=9@,h  
    Thompson&Kung双调排序算法及其计算示例 w0J|u'H  
4.3 Stone双调排序算法(略) K$[$4 dX]  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 L%\b'fs  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 wCKj7y[
 
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 E"PcrWB&  
Ch5 排序和选择的异步和分布式算法(略) `/IKdO*!S  
5.1 MIMD-CREW模型上的异步枚举排序算法 (<c7<_-H  
5.2 MIMD-TC模型上的异步快排序算法 r4XH =  
5.3分布式k-选择算法 ftbpqp'  
Ch6 并行搜索 4P8*k[.  
6.1 单处理器上的搜索(略) nsuX*C7  
6.2 SIMD共享存储模型上有序表的搜索：算法 L 3XB"A#  
6.3 SIMD共享存储模型上随机序列的搜索：算法 cj$6  
6.4 树连接的SIMD模型上随机序列的搜索：算法 Ym8}ZW-  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 &#
w=7L3AW  
Ch8 数据传输与选路 KY9n2u&4  
8.1 引言 CNrIIsJ  
    信包传输性能参数 LHYLC>J  
    维序选路(X-Y选路、E-立方选路)  A[N {  
    选路模式及其传输时间公式 ``K#}3  
8.2 单一信包一到一传输 {MBTP;{*~  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) gFN9jM  
8.3 一到多播送  +cu^%CXT  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 *%FA:Y  
8.4 多到多播送 >{zk qvsQ&  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 =d`5f@'rl  
8.5 贪心算法(书8.2) hGTV;eU  
    二维阵列上的贪心算法 E8[T  
    蝶形网上的贪心算法 TLa]O1=Bf.  
8.6 随机和确定的选路算法(书8.3)(略) pox,Im  
Ch12矩阵运算 Dt }rR[yJ  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 %yS3&Ju  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 kGYTl,A{  
12.3 矩阵向量乘法 N:5[,O<m_  
    带状划分的算法及其时间分析 -7qIToO.  
    棋盘划分的算法及其时间分析 va)%et0!  
    Systolic算法(略) WgQBGch,!  
12.4 矩阵乘法 T]9\VW4  
    简单并行分块算法 [5d2D,)  
    Cannon算法及其计算示例 a:STQk V  
    Fox算法及其计算示例 mh/n.*E7  
    DNS算法及其计算示例 :;]O c  
    Systolic算法(略) 2\D8.nQr  
Ch13 数值计算 !0VfbY9C  
13.1 稠密线性方程组求解 p<Z3tD;Z  
    SIMD-CREW的上三角方程组回代算法 a}yXC<}$  
    SIMD-CREW上的Gauss-Jordan算法 tfO#vw,@  
    MIMD-CREW上的Gauss-Seidel算法 j{++6<tr  
13.2 稀疏线性方程组的求解 I3
b"|%  
    三对角方程组的奇偶规约求解法 7*o*6,/  
    Gauss-Seidel迭代法的红黑着色并行算法 : esg(  
13.3 非线性方程的求根(略) D
h|w^Q  
Ch14 快速傅立叶变换FFT knp>m,w  
14.1 快速傅里叶变换(FFT) ~EiH-z4U  
    离散傅里叶变换(DFT) N3BL3:@O  
    串行FFT递归算法及其计算原理 s54nF\3V  
    串行FFT蝶式计算及其蝶式计算流图 2!1.E5.I  
14.2 DFT直接并行算法 kh$_ !BT  
    SIMD-MT上的并行DFT算法(略) `TqSQg_l  
14.3 并行FFT算法 +xv!$gJEj  
    SIMD-MC上的FFT算法(略) (46 {r}_O  
    SIMD-BF上的FFT算法及其时间分析 3Mjj'5KH!  
Ch15 图论算法 nwI3|&  
15.1 图的并行搜索 @LE[ac  
    p-深度优先搜索及其计算示例 ^?"\?M1  
    p-宽深优先搜索及其计算示例 /hWd/H]  
    p-宽度优先搜索及其计算示例 E`\8TqO  
15.2 图的传递闭包 %hS|68pN6  
    基于布尔矩阵乘积的算法原理 -XK0KYhgW  
    计算示例 rt7<Q47QE  
    SIMD-CC上的传递闭包算法 S:
Q! "U  
15.3 图的连通分量 _cH @I?B  
    基于传递闭包的算法 fG L
G$b  
    基于顶点合并的算法 kfb/n)b'  
15.4 图的最短路径 _o6G6e,  
    基于矩阵乘积的算法原理 8kL4~(hY  
    计算示例 %y[1H5)3<  
15.5 图的最小生成树 M
hEw _{?  
    SIMD-EREW模型上的Prim算法 rZ1Hf11C  
    算法的时间分析 F!!N9VIC  
Ch18 随机算法 * A|-KKo\  
18.1 引言 #G]!%  
    基本知识：随机算法的定义、分类、重复性定律 8iQ[9  
    时间复杂性度量 7^TV~E#  
    设计方法 8y';\(;  
18.2 低度顶点部分独立集 N^0uit  
    串行算法 ;;s* Ohh  
    随机并行算法及其正确性证明 )vB2!H/  
18.5 多项式恒等的验证 ,1{Ep`
 
    基本原理和方法 Bvjl-$m!v  
    矩阵乘积的验证原理 {U!St@  
18.8 格点逼近问题(略) #.B"q:CW*P  
18.9 SAT问题的异步随机并行算法(略) [`=LTBt  
Ch20 模型与下界 yR~-k?7b  
20.1不同的PRAM模型的相互模拟 B#%;Qc  
    PRAM-EREW模拟PPRAM-CRCW 8[%Ao/m  
    PRAM-CRCW之间的模拟 [&S}dQ"  
20.2下界 4JIYbb-a'  
    算法研究的两个方向：优化（上界）、可能性（下界） E .6HpIx  
    Gates的工作 C_:k8?  
    理想的PRAM模型与下界 'rP]Nw  
    PRAM模型的下界 *~$~yM/~3U  
20.3 NP完全理论导引(略) G28O%jD?  
20.4 P完全理论(略)