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

《并行算法》课程总结与复习 @| z _&E  
Ch1 并行算法基础 (`.# n3{  
1.1 并行计算机体系结构 \|HtE(uCM1  
    并行计算机的分类 $)M3fZ$#  
    SISD,SIMD,MISD,MIMD； iH(7.?.r  
    SIMD,PVP,SMP,MPP,COW,DSM !l[;,l  
    并行计算机的互连方式 +x%u?ZR  
    静态：LA(LC),MC,TC,MT,HC,BC,SE zhn?;Fi  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) i2<z"v63  
1.2 并行计算模型 3ahriZe  
    PRAM模型：SIMD-SM， `O\>vn  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW e;.,x
5+  
    SIMD-IN模型：SIMD-DM 'cO8& |  
    异步APRAM模型：MIMD-SM _o~ pVBl/  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 !#0)`4O  
    LogP模型：MIMD-DM，点到点通讯 5%,3)H{;t  
1.3 并行算法的一般概念
-E7mt`:d  
    并行算法的定义 I5"wa:Z  
    并行算法的表示 /M2in]oH  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 t&U9Z
$L S  
    并行算法的WT表示：Brent定理、WT最优 "c%wq0  
    加速比性能定律(略) /zIG5RK>  
    并行算法的同步和通讯(略) mb*Yw6q  
Ch2 并行算法的基本设计技术 )LP'
4*  
2.1 并行算法的三种基本设计方法 k{*EoV[.$  
2.2 基本设计技术 l,@>J9}Se  
    平衡树方法：求最大值、计算前缀和 i c{I  
    倍增技术：表序问题、求森林的根 /?81Ypt  
    分治策略：FFT分治算法 D.
Ke  
    划分原理： +`>7cy%cZ  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) BK!Yl\I<  
    流水线技术：五点的DFT计算，Systolic算法 }IygU 6{G  
    加速级联(略) w:zo \  
    破对称技术 ANm@$xO*  
Ch3 比较器网络上的排序和选择算法 R>c>wYt
'f  
3.1 Batcher归并和排序 Z  `F[0-  
    0-1原理的证明(略) 67EGkW?hbt  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) Hzz{wY   
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) a?gF;AYk  
    Batcher排序网络：原理、种类和复杂性 KR.;X3S}  
3.2 (m, n)-选择网络 ld(60?z>FH  
    分组选择网络 *(x.egOR
d  
    平衡分组选择网络及其改进 
JpXv+V  
Ch4 排序和选择的同步算法 D5"5`w=C  
4.1 一维线性阵列上的并行排序算法(略) 2P:X_:`~[  
4.2 二维Mesh上的并行排序算法 >33=0<  
    ShearSort排序算法 L;:|bVH  
    Thompson&Kung双调排序算法及其计算示例 4j3q69TZR  
4.3 Stone双调排序算法(略) ,Ee5}#dI  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 @Z/jaAjUC  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 ]v<8l4p;  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 }h y4EJ  
Ch5 排序和选择的异步和分布式算法(略) )B]"""J  
5.1 MIMD-CREW模型上的异步枚举排序算法 ~2*LWH*@  
5.2 MIMD-TC模型上的异步快排序算法 mX|M]^_,z  
5.3分布式k-选择算法 L\mF[Kd#+T  
Ch6 并行搜索 j+3\I>  
6.1 单处理器上的搜索(略) ;8[VCU:  
6.2 SIMD共享存储模型上有序表的搜索：算法 pnu?=.O  
6.3 SIMD共享存储模型上随机序列的搜索：算法 IWYQ67Yj   
6.4 树连接的SIMD模型上随机序列的搜索：算法 o"Xv)#g&  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 pwMA,X/{  
Ch8 数据传输与选路 +1#oVl !  
8.1 引言 M?8s y  
    信包传输性能参数 p+g=Z<?`  
    维序选路(X-Y选路、E-立方选路) glC,E>  
    选路模式及其传输时间公式 hV $Zr4'  
8.2 单一信包一到一传输 \asn^V@"zz  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 0Fkr3x  
8.3 一到多播送 6}Y==GPt  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 H%vgPQ8  
8.4 多到多播送 V|A)f@ Fs  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 C'@I!m._i  
8.5 贪心算法(书8.2) pcv\|)&}  
    二维阵列上的贪心算法 <IIz-6*V  
    蝶形网上的贪心算法 2aTq?ZR|8A  
8.6 随机和确定的选路算法(书8.3)(略) @=G[mc\  
Ch12矩阵运算 cQ$[Ba  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 *_YH}U  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 qJ5b;=  
12.3 矩阵向量乘法 i~E0p ,  
    带状划分的算法及其时间分析 !]?kvf-3e  
    棋盘划分的算法及其时间分析 %
>/&&(BE  
    Systolic算法(略) K:e[#b8:R  
12.4 矩阵乘法 s5v}S'uO{  
    简单并行分块算法 N MkOx$  
    Cannon算法及其计算示例 x?rd9c
 
    Fox算法及其计算示例 =,6X_m  
    DNS算法及其计算示例 ^d
# AU7V|  
    Systolic算法(略) kbvF 9 #  
Ch13 数值计算 2f{p$YIt  
13.1 稠密线性方程组求解 >;"%Db  
    SIMD-CREW的上三角方程组回代算法 Vx
o?%Dj  
    SIMD-CREW上的Gauss-Jordan算法 A|PZ<WAY  
    MIMD-CREW上的Gauss-Seidel算法 _s<BXj  
13.2 稀疏线性方程组的求解 e34g=]"  
    三对角方程组的奇偶规约求解法 OW6dK#CFt  
    Gauss-Seidel迭代法的红黑着色并行算法 OZz/ip-!lc  
13.3 非线性方程的求根(略) fHwS12SB  
Ch14 快速傅立叶变换FFT *yHz#u'  
14.1 快速傅里叶变换(FFT) nxEC6Vh'  
    离散傅里叶变换(DFT) ,+Ocb-*  
    串行FFT递归算法及其计算原理 d~6UJ
=]@8  
    串行FFT蝶式计算及其蝶式计算流图 "5ISKuL  
14.2 DFT直接并行算法 g/FT6+&T.  
    SIMD-MT上的并行DFT算法(略) }Q9+krrow  
14.3 并行FFT算法 ,jW a&7  
    SIMD-MC上的FFT算法(略) (i\{hq/  
    SIMD-BF上的FFT算法及其时间分析 :}q)]W  
Ch15 图论算法 TtWzjt  
15.1 图的并行搜索 f6\4,()  
    p-深度优先搜索及其计算示例 `H9+]TWj<  
    p-宽深优先搜索及其计算示例 a*&&6Fo  
    p-宽度优先搜索及其计算示例 n``9H91  
15.2 图的传递闭包 'n
"we# [  
    基于布尔矩阵乘积的算法原理 uK# 2vgT  
    计算示例 M(C$SB>  
    SIMD-CC上的传递闭包算法 Gr}NgyT<!D  
15.3 图的连通分量 6Hy_7\$(-  
    基于传递闭包的算法 u|\?6fz  
    基于顶点合并的算法 xh#pw2v7V  
15.4 图的最短路径 p)z#%BY56  
    基于矩阵乘积的算法原理 F|'u0JQ)$  
    计算示例 tnBCO%uG  
15.5 图的最小生成树 Q.3 :"dT  
    SIMD-EREW模型上的Prim算法 a3A3mB
w  
    算法的时间分析 tv~Y5e&8  
Ch18 随机算法 '-XO;{,-R  
18.1 引言 ^qVBgBPb  
    基本知识：随机算法的定义、分类、重复性定律 Q`;eI a6U  
    时间复杂性度量 P1^|r}  
    设计方法 '.gi@Sr5  
18.2 低度顶点部分独立集  'mm>
E  
    串行算法 K3WaBcm  
    随机并行算法及其正确性证明 FJKlqM
5]  
18.5 多项式恒等的验证 z;/8R7L&  
    基本原理和方法 mH\2XG8nV  
    矩阵乘积的验证原理 \P"Ol\@  
18.8 格点逼近问题(略) R[*n3 wB  
18.9 SAT问题的异步随机并行算法(略) xpu2RE  
Ch20 模型与下界 9%"\s2T  
20.1不同的PRAM模型的相互模拟  `u
eOb  
    PRAM-EREW模拟PPRAM-CRCW tJ8:S@E3,  
    PRAM-CRCW之间的模拟 E'6/@xM  
20.2下界 >#g Dk K  
    算法研究的两个方向：优化（上界）、可能性（下界） vg"*%K$a  
    Gates的工作 ;i/? fw[h  
    理想的PRAM模型与下界 nZ#u#V  
    PRAM模型的下界 z!.cc6R  
20.3 NP完全理论导引(略) [7LdTY"Tl  
20.4 P完全理论(略)