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

《并行算法》课程总结与复习 5u
D'Kd$H  
Ch1 并行算法基础 xmwH~ UWp  
1.1 并行计算机体系结构 "uD^1'IW2  
    并行计算机的分类 Z$ 6yB  
    SISD,SIMD,MISD,MIMD； YojYb]y+j  
    SIMD,PVP,SMP,MPP,COW,DSM LE@`TPg$R  
    并行计算机的互连方式 ]` }R,'P  
    静态：LA(LC),MC,TC,MT,HC,BC,SE gfU!sYZ  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) v`9n'+h-c6  
1.2 并行计算模型 J2Eb"y>/;  
    PRAM模型：SIMD-SM， H
v<jf38  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW H8?Kgaj~vf  
    SIMD-IN模型：SIMD-DM ?o.Q  
    异步APRAM模型：MIMD-SM Av i8&@ya  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 y w>T1  
    LogP模型：MIMD-DM，点到点通讯 Zv)x-48  
1.3 并行算法的一般概念 'U3+'du^8  
    并行算法的定义 M}BqSzd*  
    并行算法的表示 m\?H <o0  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 Ee-yP[2 *  
    并行算法的WT表示：Brent定理、WT最优 d}RR!i`<N  
    加速比性能定律(略) 63n<4VSH  
    并行算法的同步和通讯(略) I:G4i}mA  
Ch2 并行算法的基本设计技术 U>s$}Y:+Z  
2.1 并行算法的三种基本设计方法 V+2C!)f(  
2.2 基本设计技术 dSm; e_s  
    平衡树方法：求最大值、计算前缀和 )I`Ma6bX  
    倍增技术：表序问题、求森林的根 fG*366W  
    分治策略：FFT分治算法  ]7yr.4?a  
    划分原理： O5eTkKUc  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) I?!7]Sn$  
    流水线技术：五点的DFT计算，Systolic算法 f]Q`8nU  
    加速级联(略) q:/<^|  
    破对称技术 _M;M-hk/  
Ch3 比较器网络上的排序和选择算法 oWo/QNw9  
3.1 Batcher归并和排序 MF["-GvP/  
    0-1原理的证明(略) lboi\GP|  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) -%eBip,'yl  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) qoXncdDHZ  
    Batcher排序网络：原理、种类和复杂性 =~f\m:Y  
3.2 (m, n)-选择网络 %}=:gF  
    分组选择网络 @ =M:RA  
    平衡分组选择网络及其改进 K7CrRT3>6  
Ch4 排序和选择的同步算法 -x?I6>{  
4.1 一维线性阵列上的并行排序算法(略) d1rIU6  
4.2 二维Mesh上的并行排序算法 m<X[s   
    ShearSort排序算法 m=hUHA,p4  
    Thompson&Kung双调排序算法及其计算示例 B<" `<oG@|  
4.3 Stone双调排序算法(略) }; ;Thfd  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 ~DYv6-p%  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 tr t^o  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 0;V "64U  
Ch5 排序和选择的异步和分布式算法(略) 0<";9qN)6  
5.1 MIMD-CREW模型上的异步枚举排序算法 ?8GggJC  
5.2 MIMD-TC模型上的异步快排序算法 ;"K;D@xzh]  
5.3分布式k-选择算法 zY=eeG+4s  
Ch6 并行搜索  4,]z  
6.1 单处理器上的搜索(略) zv8AvNDK  
6.2 SIMD共享存储模型上有序表的搜索：算法 miTySY6^  
6.3 SIMD共享存储模型上随机序列的搜索：算法 'fIoN%  
6.4 树连接的SIMD模型上随机序列的搜索：算法 H-|%\9&{S  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 n,_q6/!  
Ch8 数据传输与选路 IGQcQ/M  
8.1 引言 <(c_[o/  
    信包传输性能参数
Qu;cl/&  
    维序选路(X-Y选路、E-立方选路) o#~Lb9`@U  
    选路模式及其传输时间公式 ^kO+NH40  
8.2 单一信包一到一传输 = G,wR'M  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) qbsmB8rh  
8.3 一到多播送 e"D%eFkDW  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 tg%#W`  
8.4 多到多播送 qC x|}5:  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 M(/ATOJ(  
8.5 贪心算法(书8.2) xk*&zAt  
    二维阵列上的贪心算法 77b^d9! ~  
    蝶形网上的贪心算法 I?&/J4o:  
8.6 随机和确定的选路算法(书8.3)(略)
}NJKkj?  
Ch12矩阵运算 QJ,[K_  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 9,wD  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 omM OA  
12.3 矩阵向量乘法 CBr(a'3{Z  
    带状划分的算法及其时间分析 (hJ&`Tt  
    棋盘划分的算法及其时间分析 J6I:UML  
    Systolic算法(略) l@)`Q  
12.4 矩阵乘法 r@a]fTf  
    简单并行分块算法 I
E|? &O  
    Cannon算法及其计算示例 "vka7r  
    Fox算法及其计算示例 m{;j r<  
    DNS算法及其计算示例 `y|_hb  
    Systolic算法(略) w*M&@+3I  
Ch13 数值计算 X- ZZLl#  
13.1 稠密线性方程组求解 I`f5)iF?0  
    SIMD-CREW的上三角方程组回代算法 ]t0St~qUL)  
    SIMD-CREW上的Gauss-Jordan算法 J= [D'h  
    MIMD-CREW上的Gauss-Seidel算法 d9&   
13.2 稀疏线性方程组的求解 /go|r '  
    三对角方程组的奇偶规约求解法 AP1&TQ,&  
    Gauss-Seidel迭代法的红黑着色并行算法 5-hnk' ~  
13.3 非线性方程的求根(略) 3K=%I+G(4  
Ch14 快速傅立叶变换FFT `*l aUn  
14.1 快速傅里叶变换(FFT) ,$} xPC  
    离散傅里叶变换(DFT) {Q}F.0Q  
    串行FFT递归算法及其计算原理 gYCr,-_i  
    串行FFT蝶式计算及其蝶式计算流图 o1vK2V  
14.2 DFT直接并行算法 q;}iW:r&Q  
    SIMD-MT上的并行DFT算法(略) w_f.\\1r  
14.3 并行FFT算法 aeISb83Y|  
    SIMD-MC上的FFT算法(略) PY;tu#W!%  
    SIMD-BF上的FFT算法及其时间分析 #R>x]Nt}  
Ch15 图论算法 =?c""~7  
15.1 图的并行搜索 au04F]-|j8  
    p-深度优先搜索及其计算示例 ae2Q^yLA  
    p-宽深优先搜索及其计算示例 o{6q>Jm  
    p-宽度优先搜索及其计算示例 ruQt0q,W3%  
15.2 图的传递闭包 H %c6I  
    基于布尔矩阵乘积的算法原理 'Oj 1@0*0  
    计算示例 ESNI$[`  
    SIMD-CC上的传递闭包算法 i!zFW-*5  
15.3 图的连通分量 cT(6>@9@  
    基于传递闭包的算法 S3:
AitGJ  
    基于顶点合并的算法 ^$50[  
15.4 图的最短路径 B Z=I/L  
    基于矩阵乘积的算法原理 i84!x%|P  
    计算示例 Z4EmRa30 p  
15.5 图的最小生成树 s/=%kCo  
    SIMD-EREW模型上的Prim算法 'S1u@p,q  
    算法的时间分析 ~N/r;omVc  
Ch18 随机算法 4;I\%qes  
18.1 引言 ."H;bfcL_  
    基本知识：随机算法的定义、分类、重复性定律 #n'.a1R  
    时间复杂性度量 y-db CYMc  
    设计方法 Bz<hP*.O  
18.2 低度顶点部分独立集 U fyhd
 
    串行算法 cf88Fd6l/  
    随机并行算法及其正确性证明 J7* o%W*V  
18.5 多项式恒等的验证 Xva(R<W7d<  
    基本原理和方法 . P$m?p#  
    矩阵乘积的验证原理 =nGFLH6)  
18.8 格点逼近问题(略) B=!!R]dxA  
18.9 SAT问题的异步随机并行算法(略) ]*#i_dho7  
Ch20 模型与下界 =3.dgtH  
20.1不同的PRAM模型的相互模拟 "_q~S$i
^  
    PRAM-EREW模拟PPRAM-CRCW 9h amxi  
    PRAM-CRCW之间的模拟 lN#j%0MaUo  
20.2下界 >jX"  
    算法研究的两个方向：优化（上界）、可能性（下界） :$$~$P  
    Gates的工作 =mO5~~"W+v  
    理想的PRAM模型与下界 c,xdkiy3  
    PRAM模型的下界 UZI:st   
20.3 NP完全理论导引(略) . vb##D  
20.4 P完全理论(略)