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

《并行算法》课程总结与复习 <K>qK]|C  
Ch1 并行算法基础 _Kh8 <$h  
1.1 并行计算机体系结构 wSdiF-ue  
    并行计算机的分类 C~n
L3w  
    SISD,SIMD,MISD,MIMD； hvA|d=R(  
    SIMD,PVP,SMP,MPP,COW,DSM }^b  
    并行计算机的互连方式 dYlVJ_0Zr  
    静态：LA(LC),MC,TC,MT,HC,BC,SE 5Q8s {WQ  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) [9F  
1.2 并行计算模型 g0
IvcA  
    PRAM模型：SIMD-SM， THgEHR0,}[  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW |eJR
3o  
    SIMD-IN模型：SIMD-DM k@gQY_  
    异步APRAM模型：MIMD-SM S/l6 c P  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 m6A\R KJ'  
    LogP模型：MIMD-DM，点到点通讯 lg{/5gQG  
1.3 并行算法的一般概念 `}FZ;q3DP  
    并行算法的定义 Y'#uZA3KA  
    并行算法的表示
IP)%y%ycw  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 F%O+w;J4  
    并行算法的WT表示：Brent定理、WT最优 ,e GF~  
    加速比性能定律(略) 8kE3\#);\  
    并行算法的同步和通讯(略) 7?);wh7`  
Ch2 并行算法的基本设计技术 !\^W*nQ>l  
2.1 并行算法的三种基本设计方法 k[@/N+;")`  
2.2 基本设计技术 eax"AmO  
    平衡树方法：求最大值、计算前缀和 Z.s0ddMs  
    倍增技术：表序问题、求森林的根 8==_43  
    分治策略：FFT分治算法 0Fsa&<{6?  
    划分原理： 7")~JBH  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) E@AV?@<sc  
    流水线技术：五点的DFT计算，Systolic算法 *55unc  
    加速级联(略) zw iS%-F  
    破对称技术 ^ohIJcI-  
Ch3 比较器网络上的排序和选择算法 k^zU;  
3.1 Batcher归并和排序 EG3u)}vI  
    0-1原理的证明(略) e{ *yV#Wl  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) $\M];S=CY  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) GR_caP  
    Batcher排序网络：原理、种类和复杂性 @Y}G,i  
3.2 (m, n)-选择网络 JY~CMR5#.O  
    分组选择网络 yD@eT:lyi  
    平衡分组选择网络及其改进 *.Z~f"SZy*  
Ch4 排序和选择的同步算法 V7cr%tY5  
4.1 一维线性阵列上的并行排序算法(略) ~=|QPO(d  
4.2 二维Mesh上的并行排序算法 z<.? 8bd  
    ShearSort排序算法 Y%>u.HzL  
    Thompson&Kung双调排序算法及其计算示例 Aq\K N.  
4.3 Stone双调排序算法(略) tg\o"QKW9  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 81w"*G5AM  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 pbw{Ez
M  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 z\woTL6D]  
Ch5 排序和选择的异步和分布式算法(略) 6RDy2JAOP  
5.1 MIMD-CREW模型上的异步枚举排序算法 E
xeZj8U  
5.2 MIMD-TC模型上的异步快排序算法  L|6I  
5.3分布式k-选择算法 \k^ojzJ  
Ch6 并行搜索 8IE^u<H(:  
6.1 单处理器上的搜索(略) -Zp BYX5e_  
6.2 SIMD共享存储模型上有序表的搜索：算法 sV\K[4HG  
6.3 SIMD共享存储模型上随机序列的搜索：算法 6Rmdf> a  
6.4 树连接的SIMD模型上随机序列的搜索：算法 VKf&}u/  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 v G9>e&Be  
Ch8 数据传输与选路 HxcL3Bh$~}  
8.1 引言 [^^Pl:+  
    信包传输性能参数 TPak,h(1  
    维序选路(X-Y选路、E-立方选路) =itQ@``r  
    选路模式及其传输时间公式 `!AI:c*3p1  
8.2 单一信包一到一传输 XUD Ztxa  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) yxU9W,D v  
8.3 一到多播送 ou-uZ"$,c  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 /?($W|9+l  
8.4 多到多播送 &b7_%,Bx
4  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 d325Cw?  
8.5 贪心算法(书8.2) S>S7\b'  
    二维阵列上的贪心算法 lk[Y6yE  
    蝶形网上的贪心算法 e<[ ] W4"A  
8.6 随机和确定的选路算法(书8.3)(略) Vu=/<;-N  
Ch12矩阵运算 1@JusS0^K  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 D9?.Ru0.  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 0U H]
 
12.3 矩阵向量乘法 wy0?*)~  
    带状划分的算法及其时间分析 y@<2`h  
    棋盘划分的算法及其时间分析 / *PHX@  
    Systolic算法(略) 32j}ep.*  
12.4 矩阵乘法 N5h9){Mx  
    简单并行分块算法 \"Y,1in#  
    Cannon算法及其计算示例 t(9q6x3|e  
    Fox算法及其计算示例 @un+y9m[C  
    DNS算法及其计算示例 Z7RBJK7|.  
    Systolic算法(略) K,$rG%czX  
Ch13 数值计算 (xRcG+3];  
13.1 稠密线性方程组求解 J9p4\=9  
    SIMD-CREW的上三角方程组回代算法 -Ou.C7ol  
    SIMD-CREW上的Gauss-Jordan算法 q$mc{F($D  
    MIMD-CREW上的Gauss-Seidel算法 "\KBF  
13.2 稀疏线性方程组的求解 XNv2xuOcJ  
    三对角方程组的奇偶规约求解法 +38R#2JV  
    Gauss-Seidel迭代法的红黑着色并行算法 #mA(x@:*  
13.3 非线性方程的求根(略)
s&(;  
Ch14 快速傅立叶变换FFT });Rjg  
14.1 快速傅里叶变换(FFT) va'F '|  
    离散傅里叶变换(DFT) ^}B,0yUu'  
    串行FFT递归算法及其计算原理 .8Bo5)q$a-  
    串行FFT蝶式计算及其蝶式计算流图 Cul=,;pkB  
14.2 DFT直接并行算法 wz*iwd-  
    SIMD-MT上的并行DFT算法(略) $?G@ijk,  
14.3 并行FFT算法 E<[ s+iX  
    SIMD-MC上的FFT算法(略) yy7(')wKO  
    SIMD-BF上的FFT算法及其时间分析 >m,hna]RZ  
Ch15 图论算法 pUb1#
=  
15.1 图的并行搜索 ]myRYb5Z
 
    p-深度优先搜索及其计算示例 P*OG`%y  
    p-宽深优先搜索及其计算示例 czuIs|_K*  
    p-宽度优先搜索及其计算示例 MMs~f*  
15.2 图的传递闭包 E,}{iqAb  
    基于布尔矩阵乘积的算法原理 '\tI|  
    计算示例 C,Nf|L((6  
    SIMD-CC上的传递闭包算法 ]VRa4ZB{u  
15.3 图的连通分量 3k`Q]O=OU  
    基于传递闭包的算法 v$|~ g'6  
    基于顶点合并的算法 qTr P@F4`g  
15.4 图的最短路径 ;7QXs39S  
    基于矩阵乘积的算法原理 :ZV|8xI  
    计算示例 oLT#'42+H  
15.5 图的最小生成树 s)a-ky(  
    SIMD-EREW模型上的Prim算法 I)Xf4FS@  
    算法的时间分析 +[!S[K E  
Ch18 随机算法 I'
4(Ibl+  
18.1 引言 OlO Og  
    基本知识：随机算法的定义、分类、重复性定律 N}?|ik
 
    时间复杂性度量 EAGvP&~P  
    设计方法 rexv)!J  
18.2 低度顶点部分独立集 mgAjD.  
    串行算法 /?'~`4!(  
    随机并行算法及其正确性证明 h;gc5"mG  
18.5 多项式恒等的验证 /iU <\+ H  
    基本原理和方法 bC `<A  
    矩阵乘积的验证原理 R^l0Bu]X  
18.8 格点逼近问题(略) i1vz{Tc  
18.9 SAT问题的异步随机并行算法(略) V*j l  
Ch20 模型与下界 &n6{wtBP  
20.1不同的PRAM模型的相互模拟  J=` 8  
    PRAM-EREW模拟PPRAM-CRCW Lv%3 jj  
    PRAM-CRCW之间的模拟 .G{cx=;  
20.2下界 ~T_|?lU`R  
    算法研究的两个方向：优化（上界）、可能性（下界） r3'J{-kl  
    Gates的工作 |OH*c3~r  
    理想的PRAM模型与下界 5Z>a}s_i  
    PRAM模型的下界 ~ WWhCRq  
20.3 NP完全理论导引(略) jJ#D`iog5  
20.4 P完全理论(略)