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

《并行算法》课程总结与复习 .?vHoNvo  
Ch1 并行算法基础 k Nvb>v  
1.1 并行计算机体系结构 OqWm5(u&S  
    并行计算机的分类 $1$0M  
    SISD,SIMD,MISD,MIMD； 0xx4rpH  
    SIMD,PVP,SMP,MPP,COW,DSM "F =NDF  
    并行计算机的互连方式 Pr:\zI  
    静态：LA(LC),MC,TC,MT,HC,BC,SE &) 64:l&  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) .{t*v6(TP  
1.2 并行计算模型 Z3yy(D>*  
    PRAM模型：SIMD-SM， ;\v&4+3S  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW HC}vO0X4  
    SIMD-IN模型：SIMD-DM 02tt.0go  
    异步APRAM模型：MIMD-SM h% KEg667  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 ,]@K,|pC)  
    LogP模型：MIMD-DM，点到点通讯 D>8p:^3g  
1.3 并行算法的一般概念 Ab]tLz|Z  
    并行算法的定义 tz8fZ*n  
    并行算法的表示 Wsgp#W+  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 L2p?]:-  
    并行算法的WT表示：Brent定理、WT最优 2{.g7bO  
    加速比性能定律(略) =IW!ZN_  
    并行算法的同步和通讯(略) Qu1&$oO  
Ch2 并行算法的基本设计技术 Z.&/,UU:4  
2.1 并行算法的三种基本设计方法 >|c?ZqW  
2.2 基本设计技术 I-/>M/66  
    平衡树方法：求最大值、计算前缀和 Gh/nNwyu <  
    倍增技术：表序问题、求森林的根 bf@g*~h@  
    分治策略：FFT分治算法 'YB[4Q /0  
    划分原理： 6}m`_d?  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) z\oTu W*B  
    流水线技术：五点的DFT计算，Systolic算法 Pn^`_  
    加速级联(略) cE:s\hG  
    破对称技术 {ZrlbDQX  
Ch3 比较器网络上的排序和选择算法 [Q{\Ik  
3.1 Batcher归并和排序 rH!sImz,  
    0-1原理的证明(略) ;&n
iZKoe  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) jhf# gdz%  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) (BPO*'   
    Batcher排序网络：原理、种类和复杂性 \?]U*)B.r  
3.2 (m, n)-选择网络 .n1&Jsey  
    分组选择网络 FJDC^@Ne  
    平衡分组选择网络及其改进 X5YOxMq  
Ch4 排序和选择的同步算法 g3c<c S^l  
4.1 一维线性阵列上的并行排序算法(略) @]%eL  
4.2 二维Mesh上的并行排序算法 #lrwKHZ+  
    ShearSort排序算法 ']TWWwj$  
    Thompson&Kung双调排序算法及其计算示例 7bk77`qWr  
4.3 Stone双调排序算法(略) /M%>M]  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 {7jim  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 lwq:0Rj@Q  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 nf^?X`g  
Ch5 排序和选择的异步和分布式算法(略) kW)3naUf<  
5.1 MIMD-CREW模型上的异步枚举排序算法 #Z1-+X8P  
5.2 MIMD-TC模型上的异步快排序算法 TL2E|@k1]  
5.3分布式k-选择算法 Tk?uJIS :  
Ch6 并行搜索 c 9f "5~  
6.1 单处理器上的搜索(略) U}5fjY  
6.2 SIMD共享存储模型上有序表的搜索：算法 6&os`!  
6.3 SIMD共享存储模型上随机序列的搜索：算法 O3@DU#N&s  
6.4 树连接的SIMD模型上随机序列的搜索：算法 %jzTQ+.%]^  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 .qSDe+A  
Ch8 数据传输与选路 u:f ]|Q
 
8.1 引言 fgd2jr3T  
    信包传输性能参数 7.<jdp  
    维序选路(X-Y选路、E-立方选路) q13fmK(n-5  
    选路模式及其传输时间公式 &N^~=y^`C'  
8.2 单一信包一到一传输 oj djy#:  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) = g{I`u  
8.3 一到多播送 (U.Go/A#wE  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Mpojabsh  
8.4 多到多播送 Ax&!Nz+?  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 !G-+O#W`  
8.5 贪心算法(书8.2) W_2;j)i  
    二维阵列上的贪心算法 %3a-@!|1<  
    蝶形网上的贪心算法 gS'{JZu2  
8.6 随机和确定的选路算法(书8.3)(略) cF8 2wg  
Ch12矩阵运算 W^[FWFUTY  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 G1z*e.+y  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 :cC$1zv@
 
12.3 矩阵向量乘法 R'v~:wNTNs  
    带状划分的算法及其时间分析 RE;A0E_3  
    棋盘划分的算法及其时间分析 >}V?GK36  
    Systolic算法(略) `3F#k[IR  
12.4 矩阵乘法 :/T\E\Qr  
    简单并行分块算法 7.h{"xOx{  
    Cannon算法及其计算示例 '0D$C},^|8  
    Fox算法及其计算示例 mU #F>  
    DNS算法及其计算示例 Dx-P]j)4x  
    Systolic算法(略) &'z _:Wm  
Ch13 数值计算 LU:xmDv  
13.1 稠密线性方程组求解 ({!!b"B2  
    SIMD-CREW的上三角方程组回代算法 }YDi/b7  
    SIMD-CREW上的Gauss-Jordan算法 6YM X7G]  
    MIMD-CREW上的Gauss-Seidel算法 TwkT|Piw S  
13.2 稀疏线性方程组的求解 |qw0:c=7!  
    三对角方程组的奇偶规约求解法 V9oBSP'kt  
    Gauss-Seidel迭代法的红黑着色并行算法 dVb6u  
13.3 非线性方程的求根(略) +5zXbfO  
Ch14 快速傅立叶变换FFT -%`~3*L  
14.1 快速傅里叶变换(FFT) [Fr](&Tx  
    离散傅里叶变换(DFT) EsGu#lD2  
    串行FFT递归算法及其计算原理 &ys>z<Z  
    串行FFT蝶式计算及其蝶式计算流图 -8n 1y[  
14.2 DFT直接并行算法 $f =`fPo  
    SIMD-MT上的并行DFT算法(略) arL>{mj  
14.3 并行FFT算法 [ inlxJD  
    SIMD-MC上的FFT算法(略) DhM=
q  
    SIMD-BF上的FFT算法及其时间分析 xWG@<}H  
Ch15 图论算法 u} mj)Nk  
15.1 图的并行搜索 ukR0E4p  
    p-深度优先搜索及其计算示例 \L*%?~  
    p-宽深优先搜索及其计算示例 uuY^Q;^I*  
    p-宽度优先搜索及其计算示例 &BPYlfB1  
15.2 图的传递闭包 # ?2*I2_  
    基于布尔矩阵乘积的算法原理 ly%^\
jW  
    计算示例 |A3"Jc.2o  
    SIMD-CC上的传递闭包算法 9<Pg2#*N0  
15.3 图的连通分量 ^EUR#~b5iy  
    基于传递闭包的算法 2b$>1O&2  
    基于顶点合并的算法 #kW=|8X  
15.4 图的最短路径 Usf@kVQ  
    基于矩阵乘积的算法原理 8:TX9`,  
    计算示例 d7V/#34  
15.5 图的最小生成树 G+c&e:ip<  
    SIMD-EREW模型上的Prim算法 Dmh$@Uu#F  
    算法的时间分析 )O[8 D  
Ch18 随机算法 2|,$#V=  
18.1 引言 i V{_?f1jo  
    基本知识：随机算法的定义、分类、重复性定律 45JL{YRN  
    时间复杂性度量 ;?Pz0,{h  
    设计方法 ? $B4'wc5  
18.2 低度顶点部分独立集 L~&S<5?  
    串行算法 6(E4l5%  
    随机并行算法及其正确性证明 o9xc$hX}  
18.5 多项式恒等的验证  7UBDd1  
    基本原理和方法 IUOf/mM5  
    矩阵乘积的验证原理 Y(,RJ&7  
18.8 格点逼近问题(略)  P@O_MT  
18.9 SAT问题的异步随机并行算法(略) MXSD8]
je  
Ch20 模型与下界 |<{SSA  
20.1不同的PRAM模型的相互模拟 I"x'  
    PRAM-EREW模拟PPRAM-CRCW C1-U2@  
    PRAM-CRCW之间的模拟 ~ikp'5  
20.2下界 8
O^x~[sQ  
    算法研究的两个方向：优化（上界）、可能性（下界） f,O10`4s  
    Gates的工作 gV]4R"/  
    理想的PRAM模型与下界 'fn}I0Vc  
    PRAM模型的下界 XGZZKvp  
20.3 NP完全理论导引(略) 9'(_*KSH  
20.4 P完全理论(略)