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

《并行算法》课程总结与复习 Dr`\  
Ch1 并行算法基础 CG9X3%xO%  
1.1 并行计算机体系结构 no?)GQ  
    并行计算机的分类 `4}!+fXQ  
    SISD,SIMD,MISD,MIMD； q'(WIv@  
    SIMD,PVP,SMP,MPP,COW,DSM 'dWJ#9C  
    并行计算机的互连方式 6j"(/X|Ex5  
    静态：LA(LC),MC,TC,MT,HC,BC,SE k|A!5A2  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) NYP3uGH]
  
1.2 并行计算模型 ,;+\!'lS  
    PRAM模型：SIMD-SM， MCh8Q|Yx4  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW
\)M5o  
    SIMD-IN模型：SIMD-DM {Y/|7Cl0  
    异步APRAM模型：MIMD-SM n[4Nu`E9  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 VdeK~#k  
    LogP模型：MIMD-DM，点到点通讯 -m|b2g}"3  
1.3 并行算法的一般概念 0[v:^H  
    并行算法的定义 #eUfwd6.Y  
    并行算法的表示 pK'WJ 72U  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 IN%>46e`  
    并行算法的WT表示：Brent定理、WT最优 'oT}jI
 
    加速比性能定律(略) NPo
Xz  
    并行算法的同步和通讯(略) >`{i[60r  
Ch2 并行算法的基本设计技术 rM?D7a{q  
2.1 并行算法的三种基本设计方法 ;~1r{kXxA"  
2.2 基本设计技术 Ki=7nKs  
    平衡树方法：求最大值、计算前缀和 BPG)m,/b  
    倍增技术：表序问题、求森林的根 eGTK^p  
    分治策略：FFT分治算法 grfF\_[:  
    划分原理： 6~!YEuA  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) <`r+l5  
    流水线技术：五点的DFT计算，Systolic算法 3?O|X+$p
 
    加速级联(略) Cf i2N V  
    破对称技术 J.nVEqLZ  
Ch3 比较器网络上的排序和选择算法 'I<j`)4`d  
3.1 Batcher归并和排序 (C3d<a\:  
    0-1原理的证明(略) 6AwnmGL(;;  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) Hug{9Hr3.  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Dw#&x/G  
    Batcher排序网络：原理、种类和复杂性 b?Jm)  
3.2 (m, n)-选择网络 F4&N;Zm2  
    分组选择网络 ZH}NlEn  
    平衡分组选择网络及其改进 gK<-*v  
Ch4 排序和选择的同步算法 R/wSGP`W  
4.1 一维线性阵列上的并行排序算法(略) /,>.${,;u  
4.2 二维Mesh上的并行排序算法 3>(` Y  
    ShearSort排序算法 B
.G!7>=  
    Thompson&Kung双调排序算法及其计算示例 5&kR1Bp#-  
4.3 Stone双调排序算法(略) sy`s$Ed!  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 !K 9(OX2;  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 C\; 8l}t  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 C
49 G&  
Ch5 排序和选择的异步和分布式算法(略) GM Nb;D(>K  
5.1 MIMD-CREW模型上的异步枚举排序算法 L[bGO|O  
5.2 MIMD-TC模型上的异步快排序算法 U .Od  
5.3分布式k-选择算法 OL'=a|g|c  
Ch6 并行搜索 8`t%QhE2  
6.1 单处理器上的搜索(略) bS'r}  
6.2 SIMD共享存储模型上有序表的搜索：算法 ^pjez+  
6.3 SIMD共享存储模型上随机序列的搜索：算法 [GP(r  
6.4 树连接的SIMD模型上随机序列的搜索：算法 8<kme"%s  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 =c,gK8C  
Ch8 数据传输与选路 ) G{v>Z,  
8.1 引言 oW[,EW+u  
    信包传输性能参数 $Y`aS^IW  
    维序选路(X-Y选路、E-立方选路) -!0LIr:"  
    选路模式及其传输时间公式 8joQPHkI\  
8.2 单一信包一到一传输 .vv*bx   
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 752wK|o0|;  
8.3 一到多播送 ]~^/w}(K  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 kpH;D= ;  
8.4 多到多播送 cDiz!n*.q  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 0 MIMs#  
8.5 贪心算法(书8.2) AD\<}/3U  
    二维阵列上的贪心算法 6p"c^  
    蝶形网上的贪心算法 qN[7zsaj  
8.6 随机和确定的选路算法(书8.3)(略)  nvPE N  
Ch12矩阵运算 Q:O>kCDV  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 m0Syxb  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 pK9^WT@  
12.3 矩阵向量乘法 EY
xRw  
    带状划分的算法及其时间分析 x acLlX+  
    棋盘划分的算法及其时间分析 CFm1c1%Hg  
    Systolic算法(略) ZZU8B?)  
12.4 矩阵乘法 =&pN8PEn\  
    简单并行分块算法 kI3zYD^:  
    Cannon算法及其计算示例 Zd U{`>v  
    Fox算法及其计算示例 \83A|+k  
    DNS算法及其计算示例 \( <{)GpBi  
    Systolic算法(略) NNwd;AC  
Ch13 数值计算 ^<\} Y  
13.1 稠密线性方程组求解 +.]}f}Y  
    SIMD-CREW的上三角方程组回代算法 (?BgT i\  
    SIMD-CREW上的Gauss-Jordan算法
&}0wzcMg  
    MIMD-CREW上的Gauss-Seidel算法 g0j4<\F2\  
13.2 稀疏线性方程组的求解 OgN1{vRFx  
    三对角方程组的奇偶规约求解法 (kQ.tsl  
    Gauss-Seidel迭代法的红黑着色并行算法 qH Ga  
13.3 非线性方程的求根(略) ;Uqx&5P}  
Ch14 快速傅立叶变换FFT < }wAP_
y  
14.1 快速傅里叶变换(FFT) 46Q;F  
    离散傅里叶变换(DFT) wUCDJY:,1  
    串行FFT递归算法及其计算原理 %<C G|]W  
    串行FFT蝶式计算及其蝶式计算流图 2^bpH%  
14.2 DFT直接并行算法 ?4>y2!OC9  
    SIMD-MT上的并行DFT算法(略) <W51oO  
14.3 并行FFT算法 '<D`:srV  
    SIMD-MC上的FFT算法(略) r.wIk0  
    SIMD-BF上的FFT算法及其时间分析 2v9s@k/k)6  
Ch15 图论算法 Xc2B2c  
15.1 图的并行搜索 mU+FQX  
    p-深度优先搜索及其计算示例 8<-oJs_o+  
    p-宽深优先搜索及其计算示例 7#9'2dI  
    p-宽度优先搜索及其计算示例 ;Co[y=Z  
15.2 图的传递闭包 ]v@tZ}  
    基于布尔矩阵乘积的算法原理 @b!R2Yq  
    计算示例 r$r&4dY  
    SIMD-CC上的传递闭包算法 ~6:LUM  
15.3 图的连通分量 LA+$_U"Jk  
    基于传递闭包的算法 7c
29Ua~[  
    基于顶点合并的算法 ]\a\ 6&R  
15.4 图的最短路径 1>@]@ST[:  
    基于矩阵乘积的算法原理 Ie2w0Cs28  
    计算示例 CFBUQMl>  
15.5 图的最小生成树 iVq#aXN  
    SIMD-EREW模型上的Prim算法 ?b@q5Y  
    算法的时间分析 :n+y/6*  
Ch18 随机算法 2%5^Fi  
18.1 引言 P )t]bS  
    基本知识：随机算法的定义、分类、重复性定律 z^P* :  
    时间复杂性度量 0r0\b*r  
    设计方法 W>?f^C!+m  
18.2 低度顶点部分独立集 5DkK'tCI9Z  
    串行算法 m6_~`)R8  
    随机并行算法及其正确性证明 I3G*+6V  
18.5 多项式恒等的验证 +H [}T ]  
    基本原理和方法 Ms:KM{T0  
    矩阵乘积的验证原理 ,#E3,bu6_4  
18.8 格点逼近问题(略) `'xQ6Sy  
18.9 SAT问题的异步随机并行算法(略) yD3bl%uZ
 
Ch20 模型与下界 VQy9Y  
20.1不同的PRAM模型的相互模拟 j}rgO
z.  
    PRAM-EREW模拟PPRAM-CRCW <pTQpU  
    PRAM-CRCW之间的模拟 zj~nnfoys  
20.2下界 VM-qVd-  
    算法研究的两个方向：优化（上界）、可能性（下界） Em~7D]Y  
    Gates的工作 'DCKD4@C/  
    理想的PRAM模型与下界 lfxuc7Rdla  
    PRAM模型的下界 WZ^
{zFoZ  
20.3 NP完全理论导引(略) o,S!RG&  
20.4 P完全理论(略)