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

《并行算法》课程总结与复习 /uX*FZ  
Ch1 并行算法基础 :Q>e54]'&  
1.1 并行计算机体系结构 myR{}G  
    并行计算机的分类 'k[qx}  
    SISD,SIMD,MISD,MIMD； G9^`cTvv'8  
    SIMD,PVP,SMP,MPP,COW,DSM ~q}L13^k  
    并行计算机的互连方式 !i~(h&z  
    静态：LA(LC),MC,TC,MT,HC,BC,SE cVW7I  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) :vb5J33U  
1.2 并行计算模型 B6 (\1  
    PRAM模型：SIMD-SM， <`uu e  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW &L$9Ii  
    SIMD-IN模型：SIMD-DM }6%XiP|  
    异步APRAM模型：MIMD-SM ]|tg`*l!>  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步  RbTG AA  
    LogP模型：MIMD-DM，点到点通讯 B4RrUA32  
1.3 并行算法的一般概念 |-}.Y(y  
    并行算法的定义 &M}X$k I  
    并行算法的表示 B1)Eo2i#  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 _x<NGIz  
    并行算法的WT表示：Brent定理、WT最优 49Jnp>h  
    加速比性能定律(略) n8<?<-2  
    并行算法的同步和通讯(略) dYrgL3'  
Ch2 并行算法的基本设计技术 z;>$["t]6  
2.1 并行算法的三种基本设计方法 bwXeEA@{  
2.2 基本设计技术 ]qT&6:;-]  
    平衡树方法：求最大值、计算前缀和 t|>zke!'  
    倍增技术：表序问题、求森林的根 =4eJ@EVM  
    分治策略：FFT分治算法 !l0]IX` F  
    划分原理： am]M2+,2Ip  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) nU>P%|loXx  
    流水线技术：五点的DFT计算，Systolic算法 Sk|e#{  
    加速级联(略) R7Y_ 7@p  
    破对称技术 pr#%VM[':R  
Ch3 比较器网络上的排序和选择算法 M9W zsWM  
3.1 Batcher归并和排序 VhkM{O  
    0-1原理的证明(略) |X8?B=  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) >4X2uNbZS  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) "sN%S's  
    Batcher排序网络：原理、种类和复杂性 >8(i;)(3  
3.2 (m, n)-选择网络 _cs(f<>oCO  
    分组选择网络 M(I%y 0  
    平衡分组选择网络及其改进 $v@$C
4  
Ch4 排序和选择的同步算法 UN.;w3`Oc  
4.1 一维线性阵列上的并行排序算法(略) vdq=F|&  
4.2 二维Mesh上的并行排序算法 <==uK>pET  
    ShearSort排序算法 {}YA7M:L  
    Thompson&Kung双调排序算法及其计算示例 %VO+\L8Fs  
4.3 Stone双调排序算法(略) _Z0 .c@0  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 :VT%d{Vp_  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 g{
]6*`/Z  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 Nu"v .]Y2  
Ch5 排序和选择的异步和分布式算法(略) yt
IPY7E  
5.1 MIMD-CREW模型上的异步枚举排序算法 MIZdk'.U  
5.2 MIMD-TC模型上的异步快排序算法 j?N<40z  
5.3分布式k-选择算法 dS6 $  
Ch6 并行搜索 uBRlvNJ  
6.1 单处理器上的搜索(略) |c/=9Bb  
6.2 SIMD共享存储模型上有序表的搜索：算法 u4Nh_x8\Nr  
6.3 SIMD共享存储模型上随机序列的搜索：算法 r/sSkF F  
6.4 树连接的SIMD模型上随机序列的搜索：算法 %P0  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 hQ@k|3=Re  
Ch8 数据传输与选路 XH?//.q  
8.1 引言 %/Wk+r9uu  
    信包传输性能参数 qk<jvha  
    维序选路(X-Y选路、E-立方选路) "&2 F  
    选路模式及其传输时间公式 ]<^2B?}  
8.2 单一信包一到一传输 _2jL]mB  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) _^BA;S@  
8.3 一到多播送 "/zgh  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 qYA~Os1e  
8.4 多到多播送 |P>
7C  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 T<B}Z11R  
8.5 贪心算法(书8.2) a.V5fl0?I@  
    二维阵列上的贪心算法 G<7M;vRvP  
    蝶形网上的贪心算法 r84^/+"T  
8.6 随机和确定的选路算法(书8.3)(略) C+TB>~Gv`  
Ch12矩阵运算 Cy[G7A%  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 9G/!18 X?f  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 }MQ:n8  
12.3 矩阵向量乘法 \U$:/#1Oe  
    带状划分的算法及其时间分析 _Tj&gyS  
    棋盘划分的算法及其时间分析 I0+6p8,  
    Systolic算法(略) CGi;M=xr  
12.4 矩阵乘法 @-sWXz*W  
    简单并行分块算法 !h.hJt  
    Cannon算法及其计算示例 xxur4@p!  
    Fox算法及其计算示例 ;U=b6xE  
    DNS算法及其计算示例 u+j\PWOtm  
    Systolic算法(略) 3:iEt (iCI  
Ch13 数值计算 N (4H}2  
13.1 稠密线性方程组求解 #Nh'1@@  
    SIMD-CREW的上三角方程组回代算法 -Rpra0o. C  
    SIMD-CREW上的Gauss-Jordan算法 m#'eDO
:  
    MIMD-CREW上的Gauss-Seidel算法 UQDAql  
13.2 稀疏线性方程组的求解 pT|
s#- }  
    三对角方程组的奇偶规约求解法 OInl?_,,T#  
    Gauss-Seidel迭代法的红黑着色并行算法 t$$Yi O  
13.3 非线性方程的求根(略) *\XOQWrF  
Ch14 快速傅立叶变换FFT V[(fE=cIN~  
14.1 快速傅里叶变换(FFT) xq((]5P y  
    离散傅里叶变换(DFT) (X "J)xaQ  
    串行FFT递归算法及其计算原理 C][$0  
    串行FFT蝶式计算及其蝶式计算流图 -~]H5er`  
14.2 DFT直接并行算法 F-s{#V1=  
    SIMD-MT上的并行DFT算法(略) S($/Ov  
14.3 并行FFT算法 #%[;vK  
    SIMD-MC上的FFT算法(略) v":q_w<k  
    SIMD-BF上的FFT算法及其时间分析 1%v6d !  
Ch15 图论算法 <G}Lc  
15.1 图的并行搜索 Tow =B  
    p-深度优先搜索及其计算示例 Pg8.RvmQ  
    p-宽深优先搜索及其计算示例 2jyWkAP'  
    p-宽度优先搜索及其计算示例 VNTbjn
]  
15.2 图的传递闭包 56)!&MF  
    基于布尔矩阵乘积的算法原理 7*P BJt\  
    计算示例 3/+kjY/  
    SIMD-CC上的传递闭包算法 $rX CNew(  
15.3 图的连通分量 ;8^k=8  
    基于传递闭包的算法 c0zcR)=mL  
    基于顶点合并的算法 ,Wd=!if  
15.4 图的最短路径 *F1TZ_GS  
    基于矩阵乘积的算法原理 ^UKAD'_#%O  
    计算示例 _]zX W  
15.5 图的最小生成树 3JGrJ!x  
    SIMD-EREW模型上的Prim算法 3WP\
MM  
    算法的时间分析 G[ U5R?/  
Ch18 随机算法 )8C` EPe  
18.1 引言 X|a{Z*y;r*  
    基本知识：随机算法的定义、分类、重复性定律 Tv"T+!Z  
    时间复杂性度量 .T3N"}7[  
    设计方法 av!;k2"
 
18.2 低度顶点部分独立集 q\<l"b z  
    串行算法 ;D~#|CB  
    随机并行算法及其正确性证明 QQW}.>N  
18.5 多项式恒等的验证 )G)6D"5,+G  
    基本原理和方法 uaO.7QSwN  
    矩阵乘积的验证原理 `o#(YEu  
18.8 格点逼近问题(略) x\Q}fk?{t  
18.9 SAT问题的异步随机并行算法(略) ]t)N3n6Bc  
Ch20 模型与下界 LY0f`RX*&  
20.1不同的PRAM模型的相互模拟 yo[Sh6r/9b  
    PRAM-EREW模拟PPRAM-CRCW N~ flao^  
    PRAM-CRCW之间的模拟 4 *}H3-`  
20.2下界 zH~P-MqC  
    算法研究的两个方向：优化（上界）、可能性（下界） ntH`\ )xi  
    Gates的工作 i6HRG\9nU  
    理想的PRAM模型与下界 <<LLEdB  
    PRAM模型的下界 Z5v_- +K  
20.3 NP完全理论导引(略) b[:,p?:@  
20.4 P完全理论(略)