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

《并行算法》课程总结与复习 9E5*%Hu_  
Ch1 并行算法基础 B7qi|Fw  
1.1 并行计算机体系结构 ghW`xm87  
    并行计算机的分类 1h`F*:nva  
    SISD,SIMD,MISD,MIMD； g3'dkS!  
    SIMD,PVP,SMP,MPP,COW,DSM eI`%J3BxR  
    并行计算机的互连方式 ,e 7 ~G  
    静态：LA(LC),MC,TC,MT,HC,BC,SE jp_)NC/~g  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) xv>8rW(Np5  
1.2 并行计算模型 #(}{*dR  
    PRAM模型：SIMD-SM， x/]G"?Uix  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW 'p!&&.%  
    SIMD-IN模型：SIMD-DM >G?*rg4  
    异步APRAM模型：MIMD-SM =v|$dDz  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 $p P
c}M[h  
    LogP模型：MIMD-DM，点到点通讯 d+h~4'ebv  
1.3 并行算法的一般概念 m_ wv
i  
    并行算法的定义 ae3 Gn}tf  
    并行算法的表示 w"kBAi&  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 9^sz,auB  
    并行算法的WT表示：Brent定理、WT最优 !6taOT >v  
    加速比性能定律(略) ~.e~YI80  
    并行算法的同步和通讯(略) C.u)2[(  
Ch2 并行算法的基本设计技术 b H5lLcdf  
2.1 并行算法的三种基本设计方法 F6DVq8f9  
2.2 基本设计技术 hE\gXb  
    平衡树方法：求最大值、计算前缀和 Cvt/ot-J?  
    倍增技术：表序问题、求森林的根 b,ZBol|X  
    分治策略：FFT分治算法 1,P2}mYv  
    划分原理： \,nhGh  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) {vd +cE  
    流水线技术：五点的DFT计算，Systolic算法 -:!T@
rV,d  
    加速级联(略) N-<,wUxf  
    破对称技术 Y)S f;  
Ch3 比较器网络上的排序和选择算法 ucLh|}jJ5  
3.1 Batcher归并和排序 SrdCLT8  
    0-1原理的证明(略) Cw.DLg  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) >6(e6/C-9  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) {oo(HD;5  
    Batcher排序网络：原理、种类和复杂性 ^D {v L  
3.2 (m, n)-选择网络 up?S (.*B  
    分组选择网络 y>J6)F =  
    平衡分组选择网络及其改进 ` gor  
Ch4 排序和选择的同步算法 eg"!.ol  
4.1 一维线性阵列上的并行排序算法(略) gyMy;}a  
4.2 二维Mesh上的并行排序算法 un N*L  
    ShearSort排序算法 P=4o)e7E!  
    Thompson&Kung双调排序算法及其计算示例 90Z4saSUw  
4.3 Stone双调排序算法(略) &xFs0Ri(  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 S }G3ha  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 nhq,Y0YH  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 l2 #^}-
 
Ch5 排序和选择的异步和分布式算法(略) 4Z{ r  
5.1 MIMD-CREW模型上的异步枚举排序算法 2ZMVYa2%(  
5.2 MIMD-TC模型上的异步快排序算法 G'_5UP!  
5.3分布式k-选择算法 =:^f6"p&Z  
Ch6 并行搜索 Y]}>he1/ 5  
6.1 单处理器上的搜索(略) KJ6:ZTbW  
6.2 SIMD共享存储模型上有序表的搜索：算法  {0} Q5  
6.3 SIMD共享存储模型上随机序列的搜索：算法 7/c9azmC  
6.4 树连接的SIMD模型上随机序列的搜索：算法 +&)&Ny$W  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 <K~mg<ff$  
Ch8 数据传输与选路 &G!2T!xx  
8.1 引言 BIEeHN4  
    信包传输性能参数 BxXP]od  
    维序选路(X-Y选路、E-立方选路) 'y:+w{I2o  
    选路模式及其传输时间公式 :eTzjW=  
8.2 单一信包一到一传输 kF"G {5  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) ^sZ,(sc{G  
8.3 一到多播送 0VlB7oF  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 vEb_z[gd  
8.4 多到多播送 e^Lt{/  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 "+ 8Y{T  
8.5 贪心算法(书8.2) iN@+,]Yjl  
    二维阵列上的贪心算法 ' +[fJ>Le  
    蝶形网上的贪心算法 Mhj.3nN  
8.6 随机和确定的选路算法(书8.3)(略) ]$a,/Jt  
Ch12矩阵运算 UZRCJ  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 O'<cEv'B*  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 q6 Rr?  
12.3 矩阵向量乘法 ni
P/i  
    带状划分的算法及其时间分析 -_|U"C$  
    棋盘划分的算法及其时间分析 h4dT N}  
    Systolic算法(略) 75t5:>"[  
12.4 矩阵乘法 )\r;|DN  
    简单并行分块算法 LZG~1tf  
    Cannon算法及其计算示例 Yv[j5\:x  
    Fox算法及其计算示例 } h pTS_  
    DNS算法及其计算示例 x_TtS|  
    Systolic算法(略) B^u qu  
Ch13 数值计算 !@[@xdV  
13.1 稠密线性方程组求解 rG|*74Q]  
    SIMD-CREW的上三角方程组回代算法 JQ.w6aE  
    SIMD-CREW上的Gauss-Jordan算法 &7\q1X&Rr  
    MIMD-CREW上的Gauss-Seidel算法 w\z6-qa  
13.2 稀疏线性方程组的求解 =9ISsI\Y6  
    三对角方程组的奇偶规约求解法 <_"^eF+fZ  
    Gauss-Seidel迭代法的红黑着色并行算法 1"Z61gXrz  
13.3 非线性方程的求根(略) aZMMcd  
Ch14 快速傅立叶变换FFT K qt,sJ  
14.1 快速傅里叶变换(FFT) S4? N_"
m9  
    离散傅里叶变换(DFT) .(8sa8{N  
    串行FFT递归算法及其计算原理 Iv5ag h%  
    串行FFT蝶式计算及其蝶式计算流图 kM,$0@  
14.2 DFT直接并行算法 T]%:+_,  
    SIMD-MT上的并行DFT算法(略) HjO-6F#s  
14.3 并行FFT算法 {)QSx O  
    SIMD-MC上的FFT算法(略) `E),G;I  
    SIMD-BF上的FFT算法及其时间分析 G3&l|@5  
Ch15 图论算法 ;(0E#hGN  
15.1 图的并行搜索 A:3:Cr  
    p-深度优先搜索及其计算示例 iS{8cN3R  
    p-宽深优先搜索及其计算示例 9Xg+$/  
    p-宽度优先搜索及其计算示例 'o#ve72z1  
15.2 图的传递闭包 )PU?`yLT r  
    基于布尔矩阵乘积的算法原理 od7 [h5r  
    计算示例 xsq+RBJi  
    SIMD-CC上的传递闭包算法 SV4a_m?  
15.3 图的连通分量 Z[DiLXHL  
    基于传递闭包的算法 Q_bF^4gt  
    基于顶点合并的算法 XujVOf  
15.4 图的最短路径 "`Q.z~  
    基于矩阵乘积的算法原理 j#TtY|Po  
    计算示例 z@nJ-*'U8  
15.5 图的最小生成树 Kzw)Q  
    SIMD-EREW模型上的Prim算法 )|88wa(M  
    算法的时间分析 5y
. n  
Ch18 随机算法 KrhAObK  
18.1 引言 yB&+2  
    基本知识：随机算法的定义、分类、重复性定律 gxX0$\8o7  
    时间复杂性度量 8#gS{  
    设计方法 b5
hJaXJN  
18.2 低度顶点部分独立集 eGZX6Q7m  
    串行算法 . m Dh9
V5  
    随机并行算法及其正确性证明 ?NZKu6  
18.5 多项式恒等的验证 gHLBtl/  
    基本原理和方法 [Yx)`e  
    矩阵乘积的验证原理 F)we^'X  
18.8 格点逼近问题(略) }E5oa\1u  
18.9 SAT问题的异步随机并行算法(略) |fMjg'%{}  
Ch20 模型与下界 AnV\{A^  
20.1不同的PRAM模型的相互模拟 ]&za^%q0&  
    PRAM-EREW模拟PPRAM-CRCW +?[,y  
    PRAM-CRCW之间的模拟 /P*mF^Y  
20.2下界 lMu}|d  
    算法研究的两个方向：优化（上界）、可能性（下界） N;XaK+_2F  
    Gates的工作 -e"~UDq`  
    理想的PRAM模型与下界 o
T7
=  
    PRAM模型的下界 &UhI1mi]h  
20.3 NP完全理论导引(略) :"+/M{qz  
20.4 P完全理论(略)