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

《并行算法》课程总结与复习 LRl2@&z<  
Ch1 并行算法基础 ak]:ir`o  
1.1 并行计算机体系结构 seO7/h_a  
    并行计算机的分类 qBL>C\V +  
    SISD,SIMD,MISD,MIMD； H<bYm]a%  
    SIMD,PVP,SMP,MPP,COW,DSM !0Hx1I<*x  
    并行计算机的互连方式 5{?J5  
    静态：LA(LC),MC,TC,MT,HC,BC,SE  vU(2[  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) $<&N#  
1.2 并行计算模型 P:,@2el  
    PRAM模型：SIMD-SM， zi M~V'  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW fHK`u'  
    SIMD-IN模型：SIMD-DM M}Sn$h_  
    异步APRAM模型：MIMD-SM LDilrG)  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 RJ+i~;-  
    LogP模型：MIMD-DM，点到点通讯 BWRM gN'.  
1.3 并行算法的一般概念 $mfZ{  
    并行算法的定义 f'501MJu  
    并行算法的表示 Rs *]I\  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 w"?H4  
    并行算法的WT表示：Brent定理、WT最优 7{0;<@  
    加速比性能定律(略) /{h@A~<96  
    并行算法的同步和通讯(略) E8$k}I  
Ch2 并行算法的基本设计技术  3-^z<*  
2.1 并行算法的三种基本设计方法 -%R3YU3  
2.2 基本设计技术 hsYS<]  
    平衡树方法：求最大值、计算前缀和 L;jzDng<  
    倍增技术：表序问题、求森林的根 Yi?X|
"\`  
    分治策略：FFT分治算法 v D"4a w  
    划分原理： cOz8YVR-  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) # !:u *1  
    流水线技术：五点的DFT计算，Systolic算法 6}b1*xQ  
    加速级联(略) LmCr[9/  
    破对称技术 K=S-p3\g  
Ch3 比较器网络上的排序和选择算法 VTM*=5|c  
3.1 Batcher归并和排序 Nu}x`Qkmr  
    0-1原理的证明(略) )Q:.1 H
gl  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) L$T23*9XY  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) . }#R  
    Batcher排序网络：原理、种类和复杂性 by*?PhfF  
3.2 (m, n)-选择网络 3 VNPdXsh  
    分组选择网络 c~, OU7[  
    平衡分组选择网络及其改进 0O@UT1M;v  
Ch4 排序和选择的同步算法 g3fxf(iY(  
4.1 一维线性阵列上的并行排序算法(略) |->P|1 P  
4.2 二维Mesh上的并行排序算法 3u&>r-V6Fn  
    ShearSort排序算法 Z{Si`GA  
    Thompson&Kung双调排序算法及其计算示例 F},#%_4  
4.3 Stone双调排序算法(略) \:7G1_o  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 CP5vo-/)-  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 -}
_X'h&"  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 !Eqp,"ts7  
Ch5 排序和选择的异步和分布式算法(略) [m*E[0Hu  
5.1 MIMD-CREW模型上的异步枚举排序算法 AbqeZn  
5.2 MIMD-TC模型上的异步快排序算法 j'\!p):H  
5.3分布式k-选择算法 >^fpQG  
Ch6 并行搜索 'MWu2L!F  
6.1 单处理器上的搜索(略) 3zr95$ Mt  
6.2 SIMD共享存储模型上有序表的搜索：算法 XA1gV>SJ  
6.3 SIMD共享存储模型上随机序列的搜索：算法 %I`%N2ss  
6.4 树连接的SIMD模型上随机序列的搜索：算法 {/u}  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 }{oZdO  
Ch8 数据传输与选路 ?FV>[&-h#I  
8.1 引言 Qp?+G~*  
    信包传输性能参数 6g6BE^o\  
    维序选路(X-Y选路、E-立方选路) $2><4~T;|A  
    选路模式及其传输时间公式  K}OY!|  
8.2 单一信包一到一传输 XCP/e p  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) ^!F Li7X  
8.3 一到多播送 l`mNOQ@}'  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Q 1:7 9  
8.4 多到多播送 P {0iEA|k  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 F<YXkG4pO  
8.5 贪心算法(书8.2) rFJPeK7  
    二维阵列上的贪心算法 ?l/$cO  
    蝶形网上的贪心算法 CI8bHY$  
8.6 随机和确定的选路算法(书8.3)(略) Wcf;ZX
  
Ch12矩阵运算 0Mo?9??  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 z m{U.Q  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 \@eaSa  
12.3 矩阵向量乘法 02F\1fXS  
    带状划分的算法及其时间分析 UXd nN;0  
    棋盘划分的算法及其时间分析 -ld1o+'`v!  
    Systolic算法(略) 71I: P|.>  
12.4 矩阵乘法 Ia%S=xU{=  
    简单并行分块算法  Qk)E:  
    Cannon算法及其计算示例 VZ1u/O?
ub  
    Fox算法及其计算示例 Yp@i{$IUW  
    DNS算法及其计算示例 -"}mmTa*<  
    Systolic算法(略) mh:eUFe  
Ch13 数值计算 Oe_*(q&  
13.1 稠密线性方程组求解 tYzpL  
    SIMD-CREW的上三角方程组回代算法 IPa)+ ZQ  
    SIMD-CREW上的Gauss-Jordan算法 6%\&m|S  
    MIMD-CREW上的Gauss-Seidel算法 Ni Y.OwKr  
13.2 稀疏线性方程组的求解 ^)%TQ.  
    三对角方程组的奇偶规约求解法 8Rric[v  
    Gauss-Seidel迭代法的红黑着色并行算法 4.&hV?Kxz  
13.3 非线性方程的求根(略) F&6Xo]?  
Ch14 快速傅立叶变换FFT [39  
14.1 快速傅里叶变换(FFT) 0w9[Z  
    离散傅里叶变换(DFT) '.5_
L8  
    串行FFT递归算法及其计算原理 Pgo^$xn'6  
    串行FFT蝶式计算及其蝶式计算流图 Jr.4Y>;}e3  
14.2 DFT直接并行算法 --BS/L-  
    SIMD-MT上的并行DFT算法(略) xL#UMvZ>;h  
14.3 并行FFT算法 V'm4DR#M  
    SIMD-MC上的FFT算法(略) 4lsg%b6_%,  
    SIMD-BF上的FFT算法及其时间分析 F\BD7W  
Ch15 图论算法 i286`SLU  
15.1 图的并行搜索 eUZvJTE  
    p-深度优先搜索及其计算示例 )2dTgvy  
    p-宽深优先搜索及其计算示例 4PDxmH]y  
    p-宽度优先搜索及其计算示例 r{ }&* Y  
15.2 图的传递闭包 $`'Xb  
    基于布尔矩阵乘积的算法原理 g|V
md  
    计算示例 T$vDw|KSVP  
    SIMD-CC上的传递闭包算法 8TV "9{ n  
15.3 图的连通分量 xa]e9u%  
    基于传递闭包的算法 SO8b~N  
    基于顶点合并的算法 _X"G(  
15.4 图的最短路径 ^f_4w|u,+  
    基于矩阵乘积的算法原理 e0cVg  
    计算示例 na-mh E,H  
15.5 图的最小生成树 hJkF-yW  
    SIMD-EREW模型上的Prim算法 S3F8Chk5  
    算法的时间分析 OHyB
NJ  
Ch18 随机算法 jp|1S^b  
18.1 引言 =lG/A[66  
    基本知识：随机算法的定义、分类、重复性定律 N}5'Hk4
+  
    时间复杂性度量 VY]L<4BfGL  
    设计方法 o'auCa,N  
18.2 低度顶点部分独立集 nQ}$jOU&  
    串行算法 ux=0N]lc  
    随机并行算法及其正确性证明 ),;O 3:n  
18.5 多项式恒等的验证 (yxHXO9N  
    基本原理和方法 A[6D40o  
    矩阵乘积的验证原理 &m8Z3+Ea  
18.8 格点逼近问题(略) JrgpDZ  
18.9 SAT问题的异步随机并行算法(略) C<u<:4^H  
Ch20 模型与下界 T=D| jt  
20.1不同的PRAM模型的相互模拟 7v{s?h->$  
    PRAM-EREW模拟PPRAM-CRCW c3]X#Qa#m$  
    PRAM-CRCW之间的模拟
Exu>%  
20.2下界 `iT{H]po  
    算法研究的两个方向：优化（上界）、可能性（下界） Yv ZcG3@c3  
    Gates的工作 V_p[mSKJv  
    理想的PRAM模型与下界 Z:3SI$tO  
    PRAM模型的下界 ;eQOBGX9  
20.3 NP完全理论导引(略) L^><APlX  
20.4 P完全理论(略)