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

《并行算法》课程总结与复习 ]`$6=)_X  
Ch1 并行算法基础 ~^2w)-N  
1.1 并行计算机体系结构 sE?%;uBb  
    并行计算机的分类 =`3r'c  
    SISD,SIMD,MISD,MIMD； KNeVSZT  
    SIMD,PVP,SMP,MPP,COW,DSM NCKR<!(  
    并行计算机的互连方式 FEk9a^Xyx  
    静态：LA(LC),MC,TC,MT,HC,BC,SE u&l;\w  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) Q#%LIkeq  
1.2 并行计算模型 \ ^(#b,k#  
    PRAM模型：SIMD-SM， #`_W?-%^  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW ]V/5<O1  
    SIMD-IN模型：SIMD-DM QT%`=b  
    异步APRAM模型：MIMD-SM r ~{nlLO}  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 "o--MBq4  
    LogP模型：MIMD-DM，点到点通讯 +PYV-@q  
1.3 并行算法的一般概念 |B(,53  
    并行算法的定义 OAkqPG&w  
    并行算法的表示 ^6l5@#)w  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 [\ku,yd%0  
    并行算法的WT表示：Brent定理、WT最优 <2(X?,N5BD  
    加速比性能定律(略) F[coa5  
    并行算法的同步和通讯(略) bmHj)^v5]  
Ch2 并行算法的基本设计技术 g
lch06  
2.1 并行算法的三种基本设计方法 8;qOsV)UDT  
2.2 基本设计技术 ar@,SKU'K  
    平衡树方法：求最大值、计算前缀和 MTwzL<@$  
    倍增技术：表序问题、求森林的根 Nn_b  
    分治策略：FFT分治算法 }D1?Z7p  
    划分原理： s
[4qC  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) <1vogUDW  
    流水线技术：五点的DFT计算，Systolic算法 R UCUEo63  
    加速级联(略) VKPsg  
    破对称技术 #: EhGlq8  
Ch3 比较器网络上的排序和选择算法 k Jz^\ Re  
3.1 Batcher归并和排序 ^d>m`*px  
    0-1原理的证明(略) qW3XA$g|j'  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) E.C=VfBW  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) nVpDjUpN  
    Batcher排序网络：原理、种类和复杂性 M\ wCZG  
3.2 (m, n)-选择网络 JiqhCt\  
    分组选择网络 F`;q9<NYRW  
    平衡分组选择网络及其改进 ht\_YiDg3  
Ch4 排序和选择的同步算法 G=e'H-  
4.1 一维线性阵列上的并行排序算法(略) k
(`>(w  
4.2 二维Mesh上的并行排序算法 \]FPv7!  
    ShearSort排序算法 f!7fz~&Sh  
    Thompson&Kung双调排序算法及其计算示例 p*jH5h cy  
4.3 Stone双调排序算法(略) #.FhN x  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 KsTE)@F:  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 iQ;lvOja  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 ~Y1nU-  
Ch5 排序和选择的异步和分布式算法(略) rZAP3)dA  
5.1 MIMD-CREW模型上的异步枚举排序算法 8V pmcGvc3  
5.2 MIMD-TC模型上的异步快排序算法 p;%5o0{1  
5.3分布式k-选择算法 uC]c`Ue  
Ch6 并行搜索 ?`:+SncI"b  
6.1 单处理器上的搜索(略) 8XCT[X  
6.2 SIMD共享存储模型上有序表的搜索：算法 2Z9ck|L>  
6.3 SIMD共享存储模型上随机序列的搜索：算法 HKC&grp  
6.4 树连接的SIMD模型上随机序列的搜索：算法 xyV7MW\?w  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 nh+h3"-d  
Ch8 数据传输与选路 >2'A~?%  
8.1 引言 B90fUK2g  
    信包传输性能参数 D;:p6q}hT  
    维序选路(X-Y选路、E-立方选路) 6/0bis H  
    选路模式及其传输时间公式 Yru,YA   
8.2 单一信包一到一传输 HbCcROl(  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) r.]IGE|  
8.3 一到多播送 |41~U\  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 CQ{p v3)  
8.4 多到多播送 7?y([i \y  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 gd0a,_`M  
8.5 贪心算法(书8.2) FZ FPzH  
    二维阵列上的贪心算法 *y~~~ 'J/  
    蝶形网上的贪心算法 wF-H{C'  
8.6 随机和确定的选路算法(书8.3)(略) U]M 5&R=?  
Ch12矩阵运算 wO]H +t  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 S""F58H n  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 wEl/s P  
12.3 矩阵向量乘法 i66/2BUh.  
    带状划分的算法及其时间分析 @><8YN^)%  
    棋盘划分的算法及其时间分析 +~xzgaL  
    Systolic算法(略) ] $F%  
12.4 矩阵乘法 S<I9`k G  
    简单并行分块算法 5hDm[*
83  
    Cannon算法及其计算示例 u} [.*e  
    Fox算法及其计算示例 j9f QV  
    DNS算法及其计算示例 HC$}KoZkC  
    Systolic算法(略) cOdgBi  
Ch13 数值计算 ^HWa owy=  
13.1 稠密线性方程组求解 4SIS#m  
    SIMD-CREW的上三角方程组回代算法 q3u:Tpn4%  
    SIMD-CREW上的Gauss-Jordan算法 `cFNO:  
    MIMD-CREW上的Gauss-Seidel算法 %/r:iD  
13.2 稀疏线性方程组的求解 N

fd'|#  
    三对角方程组的奇偶规约求解法  %d0BQ|  
    Gauss-Seidel迭代法的红黑着色并行算法 |Syulus  
13.3 非线性方程的求根(略) 4=l$wg~;  
Ch14 快速傅立叶变换FFT 3oPyh $*  
14.1 快速傅里叶变换(FFT) 1+Q@RiW  
    离散傅里叶变换(DFT) =AX"'q  
    串行FFT递归算法及其计算原理 }u;`k'J@  
    串行FFT蝶式计算及其蝶式计算流图 "BC;zH:  
14.2 DFT直接并行算法 B#o6UO\  
    SIMD-MT上的并行DFT算法(略) V17!~  
14.3 并行FFT算法 qy/t<2'  
    SIMD-MC上的FFT算法(略) d_Z?i#r0l  
    SIMD-BF上的FFT算法及其时间分析 RVh{wg  
Ch15 图论算法 V=H:`n3k  
15.1 图的并行搜索 ,Y7QmbX^  
    p-深度优先搜索及其计算示例 Lv<vMIr  
    p-宽深优先搜索及其计算示例 ^MvBW6 #1  
    p-宽度优先搜索及其计算示例 1;~|[C  
15.2 图的传递闭包 ULzrJbP'7  
    基于布尔矩阵乘积的算法原理 IJDE{)  
    计算示例 FQ u c}A  
    SIMD-CC上的传递闭包算法 D=}\]Krmay  
15.3 图的连通分量 BCh|^Pk  
    基于传递闭包的算法 wQ81wfr1:  
    基于顶点合并的算法 H`rd bE  
15.4 图的最短路径 EKEJ9Y+47H  
    基于矩阵乘积的算法原理 cVDcda|PE  
    计算示例
tNz(s)  
15.5 图的最小生成树 TrBW0Bn>p  
    SIMD-EREW模型上的Prim算法 ]D,\(|  
    算法的时间分析 x kdC-S  
Ch18 随机算法 DTHWL  
18.1 引言 e/}4Pt  
    基本知识：随机算法的定义、分类、重复性定律 \jx3Fs:Q  
    时间复杂性度量 e(Rbq8D  
    设计方法 w@LLxL>Y  
18.2 低度顶点部分独立集 ;3o7>yEv  
    串行算法 .AZwVP<  
    随机并行算法及其正确性证明 )W&{OMr  
18.5 多项式恒等的验证 PlCj<b1D:  
    基本原理和方法 U*?`tdXJ$  
    矩阵乘积的验证原理 %< `D'V@  
18.8 格点逼近问题(略) dg_w$#  
18.9 SAT问题的异步随机并行算法(略) U>DCra;  
Ch20 模型与下界 gFsqCx<q  
20.1不同的PRAM模型的相互模拟 "F[7b!>R  
    PRAM-EREW模拟PPRAM-CRCW B<0Kl.V  
    PRAM-CRCW之间的模拟 h}kJ,n  
20.2下界 <~uzKs0  
    算法研究的两个方向：优化（上界）、可能性（下界） ?wFL
\C  
    Gates的工作 s
;$f6X  
    理想的PRAM模型与下界 +wf9!_'  
    PRAM模型的下界 Sa kew  
20.3 NP完全理论导引(略) 216$,4i  
20.4 P完全理论(略)