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

《并行算法》课程总结与复习 `aDVN_h{6  
Ch1 并行算法基础 FEO/RMh  
1.1 并行计算机体系结构 b~*CJ8Ad  
    并行计算机的分类 FN/siw(?3  
    SISD,SIMD,MISD,MIMD； ?="?)t[  
    SIMD,PVP,SMP,MPP,COW,DSM LC4W?']/  
    并行计算机的互连方式 *zwo="WA\t  
    静态：LA(LC),MC,TC,MT,HC,BC,SE +i ~kqiy.  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) R2A#2{+H  
1.2 并行计算模型 ,1B`Ve  
    PRAM模型：SIMD-SM， ,u=+%6b)A  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW A">R-1R  
    SIMD-IN模型：SIMD-DM ^X-6j[".  
    异步APRAM模型：MIMD-SM :Y|[
?;  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 Q*hXFayx  
    LogP模型：MIMD-DM，点到点通讯 #||D,[ _=+  
1.3 并行算法的一般概念 `n
RF"T_  
    并行算法的定义 [V_+/[AA)  
    并行算法的表示 [1mEdtqf*  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 Qff.QI,  
    并行算法的WT表示：Brent定理、WT最优 Ciy%7_~\  
    加速比性能定律(略) M.HMnN#  
    并行算法的同步和通讯(略) e$Mvl=NYp\  
Ch2 并行算法的基本设计技术 sDY+J(Z  
2.1 并行算法的三种基本设计方法 h\2iArw8  
2.2 基本设计技术 z8XWp[K  
    平衡树方法：求最大值、计算前缀和 _'4S1  
    倍增技术：表序问题、求森林的根 pfs]pDjS:  
    分治策略：FFT分治算法 B}"V.Msv/  
    划分原理： hV+=hX<h  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) !L@<?0xLW  
    流水线技术：五点的DFT计算，Systolic算法 Omi/sKFMi  
    加速级联(略) gWL`J=DiU  
    破对称技术 yzMGZi`ut  
Ch3 比较器网络上的排序和选择算法 Cg|\UKfy$  
3.1 Batcher归并和排序 %E"v@  
    0-1原理的证明(略) ~ToU._  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) (AX$Svw  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) ` Z/ MQ  
    Batcher排序网络：原理、种类和复杂性 Qm=iCZ|E^!  
3.2 (m, n)-选择网络 Zu<S<??Jf  
    分组选择网络 5^R?+<rd  
    平衡分组选择网络及其改进 ]G D` f  
Ch4 排序和选择的同步算法 ,p#r; O<O  
4.1 一维线性阵列上的并行排序算法(略) IA{W-RRb  
4.2 二维Mesh上的并行排序算法 =6+99<G|%M  
    ShearSort排序算法 RehraY3q  
    Thompson&Kung双调排序算法及其计算示例 ->X>h_k.Y  
4.3 Stone双调排序算法(略) N!MDD?0  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 c&x1aF "B  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 z{FFTb^B  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 5KDCmw  
Ch5 排序和选择的异步和分布式算法(略) H cyoNY  
5.1 MIMD-CREW模型上的异步枚举排序算法 q3#+G:nh  
5.2 MIMD-TC模型上的异步快排序算法 (KwC,0p  
5.3分布式k-选择算法 1q@R04i  
Ch6 并行搜索 dGi HO  
6.1 单处理器上的搜索(略) R&BWCC{  
6.2 SIMD共享存储模型上有序表的搜索：算法 Wy*+8~@A  
6.3 SIMD共享存储模型上随机序列的搜索：算法 9X%: ){  
6.4 树连接的SIMD模型上随机序列的搜索：算法 @K+gh
#  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 IM7<z,*oF  
Ch8 数据传输与选路 ]@b9m  
8.1 引言 AWYlhH4c?t  
    信包传输性能参数 (ie%zrhS  
    维序选路(X-Y选路、E-立方选路) L<0_e^8  
    选路模式及其传输时间公式 u '/)l}  
8.2 单一信包一到一传输 (XW'1@b  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) Eu:/U*j  
8.3 一到多播送 ux)*B}/xh  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 z<mN-1PM7&  
8.4 多到多播送 -{k8^o7$  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 IsE3-X|  
8.5 贪心算法(书8.2) L!zdrCM  
    二维阵列上的贪心算法 oKCy,Ot<  
    蝶形网上的贪心算法 m7g*zu2#  
8.6 随机和确定的选路算法(书8.3)(略) <<CWN(hQWO  
Ch12矩阵运算  +:-xV  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 c6#EgN,X  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 y|KQ`;  
12.3 矩阵向量乘法 g:a[N%[C  
    带状划分的算法及其时间分析 NRJp8G Z%U  
    棋盘划分的算法及其时间分析 Qd kus214  
    Systolic算法(略) BK+P  
12.4 矩阵乘法 YR-G:-(#b  
    简单并行分块算法 [;Lgbgt3f  
    Cannon算法及其计算示例 J.R\h!  
    Fox算法及其计算示例 q9rm9#}[J#  
    DNS算法及其计算示例 (~N?kh:  
    Systolic算法(略) y!P!Fif'  
Ch13 数值计算 iSezrN  
13.1 稠密线性方程组求解 XdCP!iq*8  
    SIMD-CREW的上三角方程组回代算法 c.Sd~k:3  
    SIMD-CREW上的Gauss-Jordan算法 c86KDEF  
    MIMD-CREW上的Gauss-Seidel算法 Y?J/KW
3  
13.2 稀疏线性方程组的求解 hQ<7k'V  
    三对角方程组的奇偶规约求解法 7:?\1a  
    Gauss-Seidel迭代法的红黑着色并行算法 Vsl,u  
13.3 非线性方程的求根(略) 0l[52eZ/  
Ch14 快速傅立叶变换FFT 27Z qdHd  
14.1 快速傅里叶变换(FFT) }6-olVg  
    离散傅里叶变换(DFT) $rcv@-l  
    串行FFT递归算法及其计算原理 F*@2)  
    串行FFT蝶式计算及其蝶式计算流图 1k4\zVgi  
14.2 DFT直接并行算法 E7iAN\vo  
    SIMD-MT上的并行DFT算法(略) NJsaTBT  
14.3 并行FFT算法 07:V[@'  
    SIMD-MC上的FFT算法(略) {guOAT-w  
    SIMD-BF上的FFT算法及其时间分析 y@~ VE5N  
Ch15 图论算法 _LwF:19Il  
15.1 图的并行搜索 3JQ7Cc>  
    p-深度优先搜索及其计算示例 8b'@_s!_  
    p-宽深优先搜索及其计算示例 i;9X_?QF  
    p-宽度优先搜索及其计算示例 lM4Z7mT /  
15.2 图的传递闭包 %p
 
    基于布尔矩阵乘积的算法原理 bKsjbYuo  
    计算示例 C\5G43`  
    SIMD-CC上的传递闭包算法 L#K`F8Wi=  
15.3 图的连通分量 Y|r7gy9%  
    基于传递闭包的算法 Pp!4Ak4TT9  
    基于顶点合并的算法 q{9 \hEeb  
15.4 图的最短路径 [G$#jUt/O  
    基于矩阵乘积的算法原理 ;G8H'gM07  
    计算示例 o+=wQ$"tP  
15.5 图的最小生成树 _?O'A"  
    SIMD-EREW模型上的Prim算法  >Vt2@E
e  
    算法的时间分析 \7b, Mz!  
Ch18 随机算法 *V',@NH#Os  
18.1 引言 LcvczST  
    基本知识：随机算法的定义、分类、重复性定律 r9{@e^Em  
    时间复杂性度量 5GScqY,aB  
    设计方法 7s6+I_n  
18.2 低度顶点部分独立集 eg/itty  
    串行算法 ,on]Fts  
    随机并行算法及其正确性证明 ^7+;XUyg  
18.5 多项式恒等的验证 l,h`YIy  
    基本原理和方法 KX9IC5pR  
    矩阵乘积的验证原理 o+{,>t  
18.8 格点逼近问题(略) xk~gGT&  
18.9 SAT问题的异步随机并行算法(略) Lp:VU-S  
Ch20 模型与下界 WeRDaG  
20.1不同的PRAM模型的相互模拟 J' uaZI>'  
    PRAM-EREW模拟PPRAM-CRCW Ty
&1
R?  
    PRAM-CRCW之间的模拟 :5/Ue,~ag  
20.2下界 'qT;Eht5  
    算法研究的两个方向：优化（上界）、可能性（下界） 2fr%_GNu  
    Gates的工作 ,e'm@d$Q*  
    理想的PRAM模型与下界 id9QfJ9t  
    PRAM模型的下界 9k71h`5  
20.3 NP完全理论导引(略) u=InE|SH  
20.4 P完全理论(略)