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

《并行算法》课程总结与复习 uS+b* :  
Ch1 并行算法基础 *~aI>7H  
1.1 并行计算机体系结构 +Y%I0.?&5  
    并行计算机的分类 &wWGZ~T  
    SISD,SIMD,MISD,MIMD； C @[9 LB  
    SIMD,PVP,SMP,MPP,COW,DSM &cv/q$W4  
    并行计算机的互连方式 "i5AAP?_]{  
    静态：LA(LC),MC,TC,MT,HC,BC,SE 7}HA_@[  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) r?{LQWP>e  
1.2 并行计算模型 KHC(MdZ  
    PRAM模型：SIMD-SM， Z-r0 D  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW N pIlQaMo4  
    SIMD-IN模型：SIMD-DM IaZAP  
    异步APRAM模型：MIMD-SM \V7x3*nA  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 FH@e:-*=  
    LogP模型：MIMD-DM，点到点通讯 sg~/RSJ3  
1.3 并行算法的一般概念 63\>MQcLy  
    并行算法的定义 ="*C&wB^  
    并行算法的表示 9# ay(g  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 =>TtX@Q{  
    并行算法的WT表示：Brent定理、WT最优 mi3q1npb7[  
    加速比性能定律(略) "PM:&v  
    并行算法的同步和通讯(略) ]5M Rp7  
Ch2 并行算法的基本设计技术 6v#sq  
2.1 并行算法的三种基本设计方法 uX!y,a/"  
2.2 基本设计技术 0R{R=r]  
    平衡树方法：求最大值、计算前缀和 "alO"x8t  
    倍增技术：表序问题、求森林的根 Xrs~ove1V  
    分治策略：FFT分治算法 B,qZwc|  
    划分原理： W5yu`Br  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) :)S4MoG  
    流水线技术：五点的DFT计算，Systolic算法 ZI*A0_;L  
    加速级联(略) Rf$6}F  
    破对称技术 ;(Va_   
Ch3 比较器网络上的排序和选择算法 W..>Ny;'3  
3.1 Batcher归并和排序 U-:Z^+Y  
    0-1原理的证明(略) MA QY/s~F  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) {:+^[rerj  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Y'":O W#oN  
    Batcher排序网络：原理、种类和复杂性 H`..)zL|  
3.2 (m, n)-选择网络 %6?}gc_  
    分组选择网络  D-EM  
    平衡分组选择网络及其改进 `qEm5+`  
Ch4 排序和选择的同步算法 1e%Xyqb  
4.1 一维线性阵列上的并行排序算法(略) _Xe< JJvq  
4.2 二维Mesh上的并行排序算法 5.;$9 ~d  
    ShearSort排序算法 $VNn`0^gF  
    Thompson&Kung双调排序算法及其计算示例 f4^_FK&  
4.3 Stone双调排序算法(略) Y)5}bmL
 
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 tV%\Jk),  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 'v5gg2  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 ?NeB_<dLa`  
Ch5 排序和选择的异步和分布式算法(略) 4H'&5  
5.1 MIMD-CREW模型上的异步枚举排序算法 qa#F}aGd  
5.2 MIMD-TC模型上的异步快排序算法 T!$HVHh&,}  
5.3分布式k-选择算法 Qk?Jy<Ra  
Ch6 并行搜索 < duM8  
6.1 单处理器上的搜索(略) A>S2BL#=  
6.2 SIMD共享存储模型上有序表的搜索：算法 ,\"gN5[$(  
6.3 SIMD共享存储模型上随机序列的搜索：算法 =-T etp  
6.4 树连接的SIMD模型上随机序列的搜索：算法 z81!F'x;  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 pm|]GkM  
Ch8 数据传输与选路 *2hzReM  
8.1 引言 ~Y[b QuA=)  
    信包传输性能参数 L@uK E jR  
    维序选路(X-Y选路、E-立方选路) B 8,{j wB  
    选路模式及其传输时间公式 j'cS_R  
8.2 单一信包一到一传输 'JVvL  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) T!r7RS  
8.3 一到多播送 %UhF=C  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 s"Wdbw(O'  
8.4 多到多播送
Nq3P?I(<  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 3._fbAN%e  
8.5 贪心算法(书8.2) L x&ZWF$  
    二维阵列上的贪心算法 =<icHt6s  
    蝶形网上的贪心算法 "a7d`l:  
8.6 随机和确定的选路算法(书8.3)(略) 64cmv}d_  
Ch12矩阵运算 ;DpK*A  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 Zl*!pQ  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 oB@C-(M  
12.3 矩阵向量乘法 {I ,
'  
    带状划分的算法及其时间分析 1d6pQ9 N  
    棋盘划分的算法及其时间分析 Uw!v=n3#!  
    Systolic算法(略) J0k~ %  
12.4 矩阵乘法 z m%\L/BF  
    简单并行分块算法 OZD/t(4?6s  
    Cannon算法及其计算示例 W*2SlS7  
    Fox算法及其计算示例 Y|L57F  
    DNS算法及其计算示例 &}ow-u9c3  
    Systolic算法(略) YL+W4ld  
Ch13 数值计算 `:&{/|uP7  
13.1 稠密线性方程组求解 KK}&4^q  
    SIMD-CREW的上三角方程组回代算法 9UZ X+@[F  
    SIMD-CREW上的Gauss-Jordan算法 ]cD!~nJ  
    MIMD-CREW上的Gauss-Seidel算法 ]z,?
{S  
13.2 稀疏线性方程组的求解 n9%rjS$  
    三对角方程组的奇偶规约求解法 ,yoT3_%P  
    Gauss-Seidel迭代法的红黑着色并行算法 x8^Dhpr6  
13.3 非线性方程的求根(略) &}oDSD H^,  
Ch14 快速傅立叶变换FFT [,c>-jA5  
14.1 快速傅里叶变换(FFT) S/4kfsN  
    离散傅里叶变换(DFT) udB}`<Q  
    串行FFT递归算法及其计算原理 )`)cB)s  
    串行FFT蝶式计算及其蝶式计算流图 g!8-yri  
14.2 DFT直接并行算法 `
fH6E8N  
    SIMD-MT上的并行DFT算法(略) cG<?AR?wDT  
14.3 并行FFT算法 m{g{"=}YR  
    SIMD-MC上的FFT算法(略) C-Mop,w  
    SIMD-BF上的FFT算法及其时间分析 \<5xf<{  
Ch15 图论算法 T|u)5ww%  
15.1 图的并行搜索 gP}M\3-O  
    p-深度优先搜索及其计算示例 $I.'7 &h;  
    p-宽深优先搜索及其计算示例 7}Gy%SJ`  
    p-宽度优先搜索及其计算示例 :KQ<rL d  
15.2 图的传递闭包 7"gy\_M  
    基于布尔矩阵乘积的算法原理 vm(% u!_P  
    计算示例 .e6:/x~p*  
    SIMD-CC上的传递闭包算法 *ce h ]v  
15.3 图的连通分量 DV.m({?  
    基于传递闭包的算法 5yry$w$G)  
    基于顶点合并的算法 %l>^q`p  
15.4 图的最短路径 P63f0F-G  
    基于矩阵乘积的算法原理 Z@1r s#  
    计算示例 kWgxswl7H  
15.5 图的最小生成树 Uu G
;z5  
    SIMD-EREW模型上的Prim算法 G,J$lTX  
    算法的时间分析 -G{}8GM  
Ch18 随机算法 RJ0w3T]7  
18.1 引言 5@i/4%S  
    基本知识：随机算法的定义、分类、重复性定律 Z yIn>]{  
    时间复杂性度量 / Qbt  
    设计方法 _KKG
^ u<  
18.2 低度顶点部分独立集 ,9=a(j"  
    串行算法 4B) prQ3  
    随机并行算法及其正确性证明 L='GsjF0}  
18.5 多项式恒等的验证 8}4V
$b`Z  
    基本原理和方法 t ; "o,T  
    矩阵乘积的验证原理 y6$5meh.T  
18.8 格点逼近问题(略) ibEQ52  
18.9 SAT问题的异步随机并行算法(略) }E*#VA0/nY  
Ch20 模型与下界 =*}| y;I  
20.1不同的PRAM模型的相互模拟 |06G)r&  
    PRAM-EREW模拟PPRAM-CRCW gVA$P  
    PRAM-CRCW之间的模拟 {eS!cZJ  
20.2下界 qL(Qmgd  
    算法研究的两个方向：优化（上界）、可能性（下界） s2q#D.f  
    Gates的工作 L[D}pL=  
    理想的PRAM模型与下界 D/rKqPp|!  
    PRAM模型的下界 hmQD-E{Ab  
20.3 NP完全理论导引(略) UDhW Y.`'~  
20.4 P完全理论(略)