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

《并行算法》课程总结与复习 #?bOAWAwLh  
Ch1 并行算法基础 SFRYX,0m  
1.1 并行计算机体系结构 H7 Pw>Ta ;  
    并行计算机的分类 uecjR8\e  
    SISD,SIMD,MISD,MIMD； s18 A  
    SIMD,PVP,SMP,MPP,COW,DSM H`T}k+e2-N  
    并行计算机的互连方式 &"X1w $  
    静态：LA(LC),MC,TC,MT,HC,BC,SE tSaD=#v  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) g=S|lVQm  
1.2 并行计算模型 `(@{t:L  
    PRAM模型：SIMD-SM， sQT<I]e  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW !Ee&e~"  
    SIMD-IN模型：SIMD-DM e`%<D[-  
    异步APRAM模型：MIMD-SM e{*z4q1  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 kfy|3KA3m  
    LogP模型：MIMD-DM，点到点通讯 *BQy$dfE  
1.3 并行算法的一般概念 4pFoSs?\  
    并行算法的定义 iMp_1EXe  
    并行算法的表示 ]#J-itO
  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 Vq
dR  
    并行算法的WT表示：Brent定理、WT最优 r7*'s  
    加速比性能定律(略) 4J2C#Cs  
    并行算法的同步和通讯(略) NQ\<~a`Eq  
Ch2 并行算法的基本设计技术 <#7j ~<  
2.1 并行算法的三种基本设计方法 q]m$%>  
2.2 基本设计技术 5f#]dgBe  
    平衡树方法：求最大值、计算前缀和 -2y>X`1Y  
    倍增技术：表序问题、求森林的根 6?3\P>`3Y  
    分治策略：FFT分治算法 l~GcD  
    划分原理： f15n ~d  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) e>$E67h<~  
    流水线技术：五点的DFT计算，Systolic算法 MrpT5|t  
    加速级联(略) ^9oJuT!tu  
    破对称技术 ~*ll,<L:  
Ch3 比较器网络上的排序和选择算法 a &tl@y1  
3.1 Batcher归并和排序 hN.{H:skL)  
    0-1原理的证明(略) 7cZ(gdQ/  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数)  :O{ ZZ  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数)
IHNl`\Le  
    Batcher排序网络：原理、种类和复杂性 :%"$8o*0W  
3.2 (m, n)-选择网络 F]^ZdJ2  
    分组选择网络 (T2\   
    平衡分组选择网络及其改进 W= $, \D+  
Ch4 排序和选择的同步算法 kY`L[1G$  
4.1 一维线性阵列上的并行排序算法(略) #N `Z)}Jm  
4.2 二维Mesh上的并行排序算法 @wOX</_g  
    ShearSort排序算法 +(J{~A~  
    Thompson&Kung双调排序算法及其计算示例 ^`oyf{w@  
4.3 Stone双调排序算法(略) |fg{Fpc  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 ma(E}s  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 jsnk*>j  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 \Dr?}D  
Ch5 排序和选择的异步和分布式算法(略) h;2n2.Q  
5.1 MIMD-CREW模型上的异步枚举排序算法 V<G=pPC'H  
5.2 MIMD-TC模型上的异步快排序算法 ,xsFBNCC  
5.3分布式k-选择算法 ;]xJC j  
Ch6 并行搜索 '"14(BvW  
6.1 单处理器上的搜索(略) %,[p[`NRYR  
6.2 SIMD共享存储模型上有序表的搜索：算法 0*}%v:uN9  
6.3 SIMD共享存储模型上随机序列的搜索：算法 7!"OF  
6.4 树连接的SIMD模型上随机序列的搜索：算法 ;33LuD<h.  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 Ju.B!)uS#  
Ch8 数据传输与选路 +Q6}kbDI  
8.1 引言 Foc) u~  
    信包传输性能参数 Pf?y!dK<  
    维序选路(X-Y选路、E-立方选路) V[T`I a\  
    选路模式及其传输时间公式 QvN=<V  
8.2 单一信包一到一传输 dwAFJhgh  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) C|W\qXCqu  
8.3 一到多播送 szx7CP`<8  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 8Qt'Y9|  
8.4 多到多播送 uNSbAw3  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 w0iv\yIRQ  
8.5 贪心算法(书8.2)  ,Bg)p_B  
    二维阵列上的贪心算法 <_~> YJ  
    蝶形网上的贪心算法 {Ex*8sU%p%  
8.6 随机和确定的选路算法(书8.3)(略) \KJ\>2Y  
Ch12矩阵运算 (d2|r)O  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 bijE]:<AE7  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 mOkf   
12.3 矩阵向量乘法 xF4>G0  
    带状划分的算法及其时间分析 *>a+`|[1*  
    棋盘划分的算法及其时间分析 U3f a*D  
    Systolic算法(略) ,>rr|O  
12.4 矩阵乘法 ~Yw`w2  
    简单并行分块算法 8- U1Y  
    Cannon算法及其计算示例 ;/Z9M"!u[  
    Fox算法及其计算示例 mu?6Phj  
    DNS算法及其计算示例 `N69xAiy  
    Systolic算法(略) CAhkv0?8  
Ch13 数值计算 @1w9!\7Vt  
13.1 稠密线性方程组求解 [8o!X)  
    SIMD-CREW的上三角方程组回代算法 cx(aMcX6  
    SIMD-CREW上的Gauss-Jordan算法 u
::2c  
    MIMD-CREW上的Gauss-Seidel算法 ]H4T80wm&  
13.2 稀疏线性方程组的求解 T7!"gJ  
    三对角方程组的奇偶规约求解法 ]}~[2k.  
    Gauss-Seidel迭代法的红黑着色并行算法 \[Dxg`;4  
13.3 非线性方程的求根(略) +x3T^G  
Ch14 快速傅立叶变换FFT tCJ+OU5/  
14.1 快速傅里叶变换(FFT) ,&1DKx  
    离散傅里叶变换(DFT) MMZdF{5@G  
    串行FFT递归算法及其计算原理 {q[l4_  
    串行FFT蝶式计算及其蝶式计算流图 8KQ]3Z9

p  
14.2 DFT直接并行算法 UUf-G0/P  
    SIMD-MT上的并行DFT算法(略) gRk%ObJGqm  
14.3 并行FFT算法 }w0>mA0=H  
    SIMD-MC上的FFT算法(略) 0<8pG:BQ  
    SIMD-BF上的FFT算法及其时间分析 u z(3ml^S  
Ch15 图论算法 p@H3NX  
15.1 图的并行搜索 Jzg>Y?jN R  
    p-深度优先搜索及其计算示例 SxHj3,`#C  
    p-宽深优先搜索及其计算示例 1mLd_]F'F  
    p-宽度优先搜索及其计算示例 \a|FhhI  
15.2 图的传递闭包 S}/?Lm}  
    基于布尔矩阵乘积的算法原理 n(|~z  
    计算示例
#bqc}h9  
    SIMD-CC上的传递闭包算法 jIq@@8@o  
15.3 图的连通分量 ;^9Ao>(?y  
    基于传递闭包的算法 |a(%a43fC  
    基于顶点合并的算法 JF%eC}[d  
15.4 图的最短路径 &i&k 4  
    基于矩阵乘积的算法原理 hPs7mnSW  
    计算示例 y ~.k-b<{[  
15.5 图的最小生成树 $*035f  
    SIMD-EREW模型上的Prim算法 1}moT#  
    算法的时间分析 mVg$z  
Ch18 随机算法 d-=RS]j;j  
18.1 引言 e/pZLj]M  
    基本知识：随机算法的定义、分类、重复性定律 *o}LI6_u  
    时间复杂性度量 gWxpGW^eZ~  
    设计方法 rOt`5_2f  
18.2 低度顶点部分独立集 cmpT_51~O  
    串行算法 f^P:eBgpx  
    随机并行算法及其正确性证明 +d7s
y0  
18.5 多项式恒等的验证 DrfOz#a0Uu  
    基本原理和方法 AY{-Hf&  
    矩阵乘积的验证原理 cR/-FR  
18.8 格点逼近问题(略) }ze,6T*z  
18.9 SAT问题的异步随机并行算法(略) 5pJ)OX  
Ch20 模型与下界 334UMH__  
20.1不同的PRAM模型的相互模拟 ' }G !D  
    PRAM-EREW模拟PPRAM-CRCW fOE8{O^W  
    PRAM-CRCW之间的模拟
5H (CP  
20.2下界 |T!^&t  
    算法研究的两个方向：优化（上界）、可能性（下界） 5Ocd2T'  
    Gates的工作 t7A '  
    理想的PRAM模型与下界 /i$-ws-  
    PRAM模型的下界 aNZJs<3;'D  
20.3 NP完全理论导引(略)  $D`~X`  
20.4 P完全理论(略)