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

《并行算法》课程总结与复习 iEO2Bil]  
Ch1 并行算法基础 2_DtzY:=  
1.1 并行计算机体系结构 Lh$ac-Ct  
    并行计算机的分类 56aJE .?<  
    SISD,SIMD,MISD,MIMD； mw.aavB  
    SIMD,PVP,SMP,MPP,COW,DSM TyXOd,% zl  
    并行计算机的互连方式 pMrfi}esx  
    静态：LA(LC),MC,TC,MT,HC,BC,SE ^?`,f>`M  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) LM`#S/h  
1.2 并行计算模型 }('QIvq2  
    PRAM模型：SIMD-SM， h"m7r4f  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW 5mBk[{  
    SIMD-IN模型：SIMD-DM j* ja )  
    异步APRAM模型：MIMD-SM hZG{"O!2s  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 -^N '18:  
    LogP模型：MIMD-DM，点到点通讯 CtxK{:  
1.3 并行算法的一般概念  .l'QCW9  
    并行算法的定义 `buTP?]4.  
    并行算法的表示 6?~pjMV  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 |9JYg7<  
    并行算法的WT表示：Brent定理、WT最优 3N \X{za  
    加速比性能定律(略) T hB2U(Wf  
    并行算法的同步和通讯(略) SS

-   
Ch2 并行算法的基本设计技术 8ttw!x69)_  
2.1 并行算法的三种基本设计方法 }= )"uv  
2.2 基本设计技术 9bvd1bKEW  
    平衡树方法：求最大值、计算前缀和 Rh^$0Q*2  
    倍增技术：表序问题、求森林的根 Su^Z{ Ud`  
    分治策略：FFT分治算法 $ S/8T  
    划分原理： !b_I H0]U  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) W[DB!ue  
    流水线技术：五点的DFT计算，Systolic算法 nwYeOa/t  
    加速级联(略) zSO9 U  
    破对称技术 +!wc(N[(2  
Ch3 比较器网络上的排序和选择算法
N11am  
3.1 Batcher归并和排序 g;1 UZE;  
    0-1原理的证明(略) c=CXj3  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) p- _j0zv  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) 'rgV]Oy  
    Batcher排序网络：原理、种类和复杂性 %G*D0pE  
3.2 (m, n)-选择网络 Ar_/9@n
 
    分组选择网络 G<I5%Yo6G  
    平衡分组选择网络及其改进 }I0^n
v1  
Ch4 排序和选择的同步算法 Hqk2W*UTl  
4.1 一维线性阵列上的并行排序算法(略) t<=L&:<N  
4.2 二维Mesh上的并行排序算法 l;fH5z  
    ShearSort排序算法 uB?YJf .T@  
    Thompson&Kung双调排序算法及其计算示例 -=Hr|AhE  
4.3 Stone双调排序算法(略) a &j?"o  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 1vr/|RWW  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 ~a}pYLxl  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 }\F>z  
Ch5 排序和选择的异步和分布式算法(略) d>}%A ]  
5.1 MIMD-CREW模型上的异步枚举排序算法 R.7"ZG  
5.2 MIMD-TC模型上的异步快排序算法 Ok
M>  
5.3分布式k-选择算法 k dqH36&<  
Ch6 并行搜索 KRQ/wuv  
6.1 单处理器上的搜索(略) * HVO  
6.2 SIMD共享存储模型上有序表的搜索：算法 VmW_,  
6.3 SIMD共享存储模型上随机序列的搜索：算法 E_z@\z MB  
6.4 树连接的SIMD模型上随机序列的搜索：算法 l40$}!!<  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 We`axkC  
Ch8 数据传输与选路 8CL05:&  
8.1 引言 9f "*Oj  
    信包传输性能参数 6\bbP>ql  
    维序选路(X-Y选路、E-立方选路) LTF%bAQ,  
    选路模式及其传输时间公式 S'WmPv  
8.2 单一信包一到一传输 sTb/l!=o  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 9:Y\D.
M  
8.3 一到多播送 )gR&Ms4  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 [x&&N*>N  
8.4 多到多播送 5H79) n>  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Og["X
0j  
8.5 贪心算法(书8.2) /xmd]XM=_  
    二维阵列上的贪心算法 D -jew&B  
    蝶形网上的贪心算法 6 3HxQH  
8.6 随机和确定的选路算法(书8.3)(略) ?TXFOr]g]2  
Ch12矩阵运算 &^}w|J?  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 oxRu:+N
 
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 3RD Q{
&J:  
12.3 矩阵向量乘法 NzEuiI}  
    带状划分的算法及其时间分析 5=dg4"b]  
    棋盘划分的算法及其时间分析 NENbr$,G  
    Systolic算法(略) 8z+ CYeV  
12.4 矩阵乘法 YrdK@I  
    简单并行分块算法 -Oo$\ =d  
    Cannon算法及其计算示例 XW1
9hG   
    Fox算法及其计算示例 6PTD%Rf\  
    DNS算法及其计算示例 u^`B#b'  
    Systolic算法(略) ''V:+@Toh  
Ch13 数值计算 8T%z{A1T  
13.1 稠密线性方程组求解 OaEOk57%de  
    SIMD-CREW的上三角方程组回代算法 LO QEU?z  
    SIMD-CREW上的Gauss-Jordan算法 %9M_*]  
    MIMD-CREW上的Gauss-Seidel算法 y:457R2F  
13.2 稀疏线性方程组的求解 $ ,R|$0B7  
    三对角方程组的奇偶规约求解法 <AB]FBo(  
    Gauss-Seidel迭代法的红黑着色并行算法 LOp<c<+aW  
13.3 非线性方程的求根(略) ?&N JN/+%  
Ch14 快速傅立叶变换FFT i |C'_gw`n  
14.1 快速傅里叶变换(FFT) *
t~(_j  
    离散傅里叶变换(DFT) )O_Y(^+ $  
    串行FFT递归算法及其计算原理 E$RH+):|  
    串行FFT蝶式计算及其蝶式计算流图 VG)kPKoi  
14.2 DFT直接并行算法 lwa  
    SIMD-MT上的并行DFT算法(略) w,^!kO0)~8  
14.3 并行FFT算法 JD,/oL.KA  
    SIMD-MC上的FFT算法(略) }VyDX14j  
    SIMD-BF上的FFT算法及其时间分析  aj1Zi3h  
Ch15 图论算法 wVp  
15.1 图的并行搜索 O{Wy;7i  
    p-深度优先搜索及其计算示例 WOquG  
    p-宽深优先搜索及其计算示例 ]x?`&f8i  
    p-宽度优先搜索及其计算示例 Ioj F/
 
15.2 图的传递闭包 %I?uO( @  
    基于布尔矩阵乘积的算法原理 TTu<~GH  
    计算示例 -FdhV%5]  
    SIMD-CC上的传递闭包算法 <w<&,xM  
15.3 图的连通分量 jgbE@IA@!'  
    基于传递闭包的算法 S}mqK|!
 
    基于顶点合并的算法 r+ k5Bk'  
15.4 图的最短路径 Yq} (O<ol  
    基于矩阵乘积的算法原理 \$W>@w0  
    计算示例 "'~55bG  
15.5 图的最小生成树 }HRM6fR1S  
    SIMD-EREW模型上的Prim算法 r< sx On  
    算法的时间分析 aOIE9wO  
Ch18 随机算法 +a 0q?$\  
18.1 引言 .0}]/%al  
    基本知识：随机算法的定义、分类、重复性定律 U8m/L^zh  
    时间复杂性度量 fq-e2MCX5  
    设计方法 $t}t'uJ  
18.2 低度顶点部分独立集 -
C1,$mkj  
    串行算法 .?|pv}V  
    随机并行算法及其正确性证明
1CX
O=Q  
18.5 多项式恒等的验证 $q%r }Cdg  
    基本原理和方法 js^+{~
 
    矩阵乘积的验证原理 "&lQ5]N.%  
18.8 格点逼近问题(略) VI_8r5o  
18.9 SAT问题的异步随机并行算法(略) 1g<jr.  
Ch20 模型与下界 aGSix}b1P  
20.1不同的PRAM模型的相互模拟 #k?uY g8
 
    PRAM-EREW模拟PPRAM-CRCW }JPLhr|d^  
    PRAM-CRCW之间的模拟 ^V,?n@c!  
20.2下界 oU"!"t  
    算法研究的两个方向：优化（上界）、可能性（下界） >JVdL\3  
    Gates的工作 GP<PU  
    理想的PRAM模型与下界 U4s)3jDw  
    PRAM模型的下界 M it3q  
20.3 NP完全理论导引(略) 8U86-'Pq  
20.4 P完全理论(略)