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

《并行算法》课程总结与复习 n|F$qV_p\  
Ch1 并行算法基础 /C29^P  
1.1 并行计算机体系结构 AZcWf8  
    并行计算机的分类 (NUwkAOM}  
    SISD,SIMD,MISD,MIMD； C,:3z  
    SIMD,PVP,SMP,MPP,COW,DSM n'ft@7>%h  
    并行计算机的互连方式 -?n|kSHX  
    静态：LA(LC),MC,TC,MT,HC,BC,SE DWDL|4 og  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) RS@*/.]o  
1.2 并行计算模型 (</cu$w>H)  
    PRAM模型：SIMD-SM， `V[{(&?,n  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW t5n$sF  
    SIMD-IN模型：SIMD-DM G@b|{!  
    异步APRAM模型：MIMD-SM qJ!&H  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 XPE{]
4 g  
    LogP模型：MIMD-DM，点到点通讯 .x7d!t:(D  
1.3 并行算法的一般概念 |RX uO  
    并行算法的定义 H `Fe|6I&  
    并行算法的表示 !q!.OQ  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 ai[st+1  
    并行算法的WT表示：Brent定理、WT最优 k_.%(ZE  
    加速比性能定律(略) %gDMz7$~  
    并行算法的同步和通讯(略) DU
#6%8~  
Ch2 并行算法的基本设计技术 ziCTvT  
2.1 并行算法的三种基本设计方法 K1a$ m2  
2.2 基本设计技术 gy/z;fB  
    平衡树方法：求最大值、计算前缀和 `qp[x%7^  
    倍增技术：表序问题、求森林的根 85Y E6^y  
    分治策略：FFT分治算法 z/aZ
D\[_  
    划分原理：  U=MFNp+  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) x\!Q[  
    流水线技术：五点的DFT计算，Systolic算法 /<)A!Nn+F  
    加速级联(略) hb'S!N5m  
    破对称技术 i/`N~r  
Ch3 比较器网络上的排序和选择算法 TyVn5XHl^  
3.1 Batcher归并和排序 EOWLGleD1  
    0-1原理的证明(略) k\X1`D}R  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) <5 G+(vP  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) rAq2  
    Batcher排序网络：原理、种类和复杂性 VJ ;4~WgBz  
3.2 (m, n)-选择网络 $Kn{x!,"(  
    分组选择网络 F[mL_JU   
    平衡分组选择网络及其改进 Ha {#  
Ch4 排序和选择的同步算法 raRb K8CQ  
4.1 一维线性阵列上的并行排序算法(略) qV2aa9p+  
4.2 二维Mesh上的并行排序算法 uc4#giCD  
    ShearSort排序算法 9`eu&n@Z  
    Thompson&Kung双调排序算法及其计算示例 !2>MaV1,  
4.3 Stone双调排序算法(略) 7xidBVx  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 -:]_DbF  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 JG-\~'9  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 }_m/3*x_  
Ch5 排序和选择的异步和分布式算法(略) 7jP C{W  
5.1 MIMD-CREW模型上的异步枚举排序算法 v;4l*)$)  
5.2 MIMD-TC模型上的异步快排序算法 Q^=drNV  
5.3分布式k-选择算法 &' E(
 
Ch6 并行搜索 >.^/Z/[.L  
6.1 单处理器上的搜索(略) #5*|/LD  
6.2 SIMD共享存储模型上有序表的搜索：算法 H]2cw
{2  
6.3 SIMD共享存储模型上随机序列的搜索：算法 {z:aZ]QhKc  
6.4 树连接的SIMD模型上随机序列的搜索：算法 %!Z9: +;B  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 !Wn^B|  
Ch8 数据传输与选路 ^]_[dqd  
8.1 引言 @AM;58.  
    信包传输性能参数 &|cg`m  
    维序选路(X-Y选路、E-立方选路) S[g{ )p)  
    选路模式及其传输时间公式 ~wtl\-cY  
8.2 单一信包一到一传输 N,N9K  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) ;VVKn=X=S=  
8.3 一到多播送 36ygI0V_  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 a B(_ZX'L  
8.4 多到多播送 w<}kY|A"=-  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 7{0;<@  
8.5 贪心算法(书8.2) _J' _9M?>  
    二维阵列上的贪心算法 jx*jYil  
    蝶形网上的贪心算法 &z'NQ!uV  
8.6 随机和确定的选路算法(书8.3)(略) \v|nRn,`-  
Ch12矩阵运算 hsYS<]  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 ,ddoI
I  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 ep|>
z#1  
12.3 矩阵向量乘法 -B+Pl*  
    带状划分的算法及其时间分析 O{YT6&.S0
 
    棋盘划分的算法及其时间分析 uO=yQ&  
    Systolic算法(略) _[J @w.l(  
12.4 矩阵乘法 u`K)dH,  
    简单并行分块算法 0^l)9zE  
    Cannon算法及其计算示例 X*4iNyIs_  
    Fox算法及其计算示例 kBF.TGT[l  
    DNS算法及其计算示例 32#|BBY  
    Systolic算法(略) 1a_R8j  
Ch13 数值计算 W
DrC  
13.1 稠密线性方程组求解 ,q[a V 6kO  
    SIMD-CREW的上三角方程组回代算法 }02#[vg  
    SIMD-CREW上的Gauss-Jordan算法 yf 7Sz$Eq  
    MIMD-CREW上的Gauss-Seidel算法 $-x@P9im  
13.2 稀疏线性方程组的求解 Ev%_8CO4e  
    三对角方程组的奇偶规约求解法 397IbZ\  
    Gauss-Seidel迭代法的红黑着色并行算法 |"gg2p  
13.3 非线性方程的求根(略) cu~dbv6H  
Ch14 快速傅立叶变换FFT moop.}O<  
14.1 快速傅里叶变换(FFT) CO%o.j=1  
    离散傅里叶变换(DFT) Ah_,5Z@&R  
    串行FFT递归算法及其计算原理 /Soc,PjZ  
    串行FFT蝶式计算及其蝶式计算流图 hN#A3FFo L  
14.2 DFT直接并行算法 F\K&$
5J{p  
    SIMD-MT上的并行DFT算法(略) =qg;K'M 5  
14.3 并行FFT算法 k'(d$;Jgr  
    SIMD-MC上的FFT算法(略) w# -J ?/m  
    SIMD-BF上的FFT算法及其时间分析 CC,f*I  
Ch15 图论算法 2kX

a  
15.1 图的并行搜索 c] '- :=  
    p-深度优先搜索及其计算示例 $;k2b4u  
    p-宽深优先搜索及其计算示例 F4b$  
    p-宽度优先搜索及其计算示例 REK(^1 h  
15.2 图的传递闭包 h<1p
GQV  
    基于布尔矩阵乘积的算法原理 )XFaVkQ}  
    计算示例  K}OY!|  
    SIMD-CC上的传递闭包算法 XCP/e p  
15.3 图的连通分量 ]-2Q0wTj  
    基于传递闭包的算法 #a$k3C  
    基于顶点合并的算法 0
t^Tm0RzH  
15.4 图的最短路径 ge[hAI2I  
    基于矩阵乘积的算法原理 uE;bNs'  
    计算示例 zP`&X:8  
15.5 图的最小生成树 GN=ugP 9  
    SIMD-EREW模型上的Prim算法 l5/!0]/  
    算法的时间分析 5ltrr(MeD  
Ch18 随机算法 ^+MG"|)u~  
18.1 引言 &BZjQK  
    基本知识：随机算法的定义、分类、重复性定律 "<=HmE-;  
    时间复杂性度量 l|Y?]LNr  
    设计方法 8-_\Q2vG  
18.2 低度顶点部分独立集 7`pK=E}+  
    串行算法 i^Ip+J+[  
    随机并行算法及其正确性证明 VJoobu1h  
18.5 多项式恒等的验证 I #bta  
    基本原理和方法 AEw~LF2w  
    矩阵乘积的验证原理 I%b}qC"5M  
18.8 格点逼近问题(略) mh:eUFe  
18.9 SAT问题的异步随机并行算法(略)
M\!z='Fi  
Ch20 模型与下界 _Z0O]>KH  
20.1不同的PRAM模型的相互模拟 L Rn)  
    PRAM-EREW模拟PPRAM-CRCW of<(4<T  
    PRAM-CRCW之间的模拟 %h^ f?.(:  
20.2下界 o'*7I|7a  
    算法研究的两个方向：优化（上界）、可能性（下界） rsPo~nA  
    Gates的工作 Xt$o$V  
    理想的PRAM模型与下界 277Am*2  
    PRAM模型的下界 8;q2W F{AX  
20.3 NP完全理论导引(略) tGVC"a  
20.4 P完全理论(略)