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

《并行算法》课程总结与复习
cgb2K$B_"  
Ch1 并行算法基础 %?aS#4jI  
1.1 并行计算机体系结构 mKT>,M  
    并行计算机的分类 MWNPPYww  
    SISD,SIMD,MISD,MIMD； bsd
99-_(4  
    SIMD,PVP,SMP,MPP,COW,DSM bWZbG{Y.  
    并行计算机的互连方式 ~+<olss_  
    静态：LA(LC),MC,TC,MT,HC,BC,SE S!PzLTc  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) /T,Z>R  
1.2 并行计算模型 []0mX70N  
    PRAM模型：SIMD-SM， lCF`*DM#  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW 'TTUN=y  
    SIMD-IN模型：SIMD-DM 8?*RIA.a  
    异步APRAM模型：MIMD-SM pq:7F  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 ;f,c't@w  
    LogP模型：MIMD-DM，点到点通讯 \v6M:KR5/  
1.3 并行算法的一般概念 $ n,Z  
    并行算法的定义 'a^{=+  
    并行算法的表示 - }!H3]tr  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 YF:2>w<  
    并行算法的WT表示：Brent定理、WT最优 Xnuzr"4u  
    加速比性能定律(略) {B *W\[ns  
    并行算法的同步和通讯(略) 6DL[aD  
Ch2 并行算法的基本设计技术 T@%m7|P  
2.1 并行算法的三种基本设计方法 ;WT{|z  
2.2 基本设计技术 xsj O)))f  
    平衡树方法：求最大值、计算前缀和 Jti(b*~  
    倍增技术：表序问题、求森林的根 C K_(b"  
    分治策略：FFT分治算法 5cK@WE:  
    划分原理： >QHo@Zqj(  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) 3`HnLD/  
    流水线技术：五点的DFT计算，Systolic算法 91of~ffh  
    加速级联(略) $jI>[%  
    破对称技术 `>D9P_Y"jI  
Ch3 比较器网络上的排序和选择算法 6zIgQ4Bp24  
3.1 Batcher归并和排序 U,1AfzlF  
    0-1原理的证明(略) bg?"I
Lpk  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) V 'X;jC  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) gQ~5M '#  
    Batcher排序网络：原理、种类和复杂性 L;W.pe0  
3.2 (m, n)-选择网络 OMihXt[  
    分组选择网络 gLL-VvJ[  
    平衡分组选择网络及其改进 5 waw`F  
Ch4 排序和选择的同步算法 GR'Ti*Qi  
4.1 一维线性阵列上的并行排序算法(略) ^_p%Yv  
4.2 二维Mesh上的并行排序算法 ^T4Ay=~{  
    ShearSort排序算法 ZF#Rej?  
    Thompson&Kung双调排序算法及其计算示例 OySy6IN]q  
4.3 Stone双调排序算法(略) m:`@?n~..  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 77gysd\(  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 3Rl,GWK  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 =l
r)gj  
Ch5 排序和选择的异步和分布式算法(略) -ewQp9)G  
5.1 MIMD-CREW模型上的异步枚举排序算法 -E&e1u,Mi  
5.2 MIMD-TC模型上的异步快排序算法 5b#QYu  
5.3分布式k-选择算法 H!IDV}dn  
Ch6 并行搜索 ;5|1M8]=0  
6.1 单处理器上的搜索(略) _JGs}aQ  
6.2 SIMD共享存储模型上有序表的搜索：算法 s<T?pH  
6.3 SIMD共享存储模型上随机序列的搜索：算法 Edt}",s7  
6.4 树连接的SIMD模型上随机序列的搜索：算法 pe04#zQK  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 BQgoVnQo_c  
Ch8 数据传输与选路 8KjRCm,I  
8.1 引言 k1
N$+h ;\  
    信包传输性能参数 &d$
~6'x*  
    维序选路(X-Y选路、E-立方选路) Jj"HpK>[  
    选路模式及其传输时间公式 EO"C8z'al  
8.2 单一信包一到一传输 2z2`  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) E)YVfM  
8.3 一到多播送 ~a+NJ6e1  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 )r!e2zc=Q  
8.4 多到多播送 Px4/O~bLk  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 ,-#GX{!  
8.5 贪心算法(书8.2) ZCiY,;c  
    二维阵列上的贪心算法 r?p{LF  
    蝶形网上的贪心算法 ubGs/Vzye  
8.6 随机和确定的选路算法(书8.3)(略) .|]IwyD &  
Ch12矩阵运算 &IQ%\W#aY  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分
!=zx  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 .H;B=nd*  
12.3 矩阵向量乘法 X8 qIia  
    带状划分的算法及其时间分析 W);W.:F  
    棋盘划分的算法及其时间分析 *TnzkNN_,  
    Systolic算法(略) z\Ui8jo:;  
12.4 矩阵乘法 T\3[F%?  
    简单并行分块算法 ZgF/;8!~V-  
    Cannon算法及其计算示例 jH0Bo;  
    Fox算法及其计算示例 Vipp /WV  
    DNS算法及其计算示例 l{EU_|q  
    Systolic算法(略) T|+$
@o  
Ch13 数值计算 ZLJNw0!=|t  
13.1 稠密线性方程组求解 |
cu`f{E2]  
    SIMD-CREW的上三角方程组回代算法 R
uj.J,  
    SIMD-CREW上的Gauss-Jordan算法 YN^jm  
    MIMD-CREW上的Gauss-Seidel算法 3H'*?|Y(#  
13.2 稀疏线性方程组的求解 oc;VIK)g]c  
    三对角方程组的奇偶规约求解法 ]L(54q;W  
    Gauss-Seidel迭代法的红黑着色并行算法 EI
K*49b2  
13.3 非线性方程的求根(略) nP u`;no  
Ch14 快速傅立叶变换FFT 5mIXyg 0:  
14.1 快速傅里叶变换(FFT) msG3~@q  
    离散傅里叶变换(DFT) GC?S]
;PL  
    串行FFT递归算法及其计算原理 5G oK"F0i  
    串行FFT蝶式计算及其蝶式计算流图 xN"wF-s4?  
14.2 DFT直接并行算法 ||fvKyKW>  
    SIMD-MT上的并行DFT算法(略) L5C2ng>  
14.3 并行FFT算法 @#CF".fuN>  
    SIMD-MC上的FFT算法(略) j`Nh7+qs  
    SIMD-BF上的FFT算法及其时间分析 -fQX4'3R  
Ch15 图论算法 $owb3g(%4  
15.1 图的并行搜索 U%,;N\:_  
    p-深度优先搜索及其计算示例 MC6)=0:KX  
    p-宽深优先搜索及其计算示例 $2is3;h  
    p-宽度优先搜索及其计算示例 PS/W h  
15.2 图的传递闭包 i\vpGlx  
    基于布尔矩阵乘积的算法原理 sSy$(%  
    计算示例 AtT"RG-6  
    SIMD-CC上的传递闭包算法 zM\IKo_"  
15.3 图的连通分量 r8F{A6iN  
    基于传递闭包的算法 A{1 \f*  
    基于顶点合并的算法 *{Yi}d@h(  
15.4 图的最短路径 qkiJHT  
    基于矩阵乘积的算法原理 n
{z8Ao%  
    计算示例 LVoyA/F  
15.5 图的最小生成树 F/xCG nP-  
    SIMD-EREW模型上的Prim算法 7\f{'KL  
    算法的时间分析 _Ws#UL+Nq  
Ch18 随机算法 &b!vWX1N  
18.1 引言  c,.0d  
    基本知识：随机算法的定义、分类、重复性定律 xl|ghjn  
    时间复杂性度量 L%k67>  
    设计方法 @|E;}:?u  
18.2 低度顶点部分独立集 |$Qp0vOA}  
    串行算法 CH55K[{<  
    随机并行算法及其正确性证明 /G{&[X<4U  
18.5 多项式恒等的验证 5"$e=y/  
    基本原理和方法 Y'2-yB  
    矩阵乘积的验证原理 ZMP?'0h=  
18.8 格点逼近问题(略) N/(ofy  
18.9 SAT问题的异步随机并行算法(略) AL(n*,  
Ch20 模型与下界 SgyqmYTvZw  
20.1不同的PRAM模型的相互模拟 Th.3j's  
    PRAM-EREW模拟PPRAM-CRCW H U:1f)aa  
    PRAM-CRCW之间的模拟 x`Vy<h 33  
20.2下界 %uh R'8"  
    算法研究的两个方向：优化（上界）、可能性（下界） CM`x>J  
    Gates的工作 6.k^m&-A  
    理想的PRAM模型与下界 Z`^ K%P=  
    PRAM模型的下界 Xs{/}wc.q;  
20.3 NP完全理论导引(略) ])+Sc"g4k  
20.4 P完全理论(略)