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

《并行算法》课程总结与复习 I7@|{L1|FB  
Ch1 并行算法基础 Oe)d|6=  
1.1 并行计算机体系结构 ',WnT:  
    并行计算机的分类 Z<wJ!|f  
    SISD,SIMD,MISD,MIMD； Q9yIQ{>H[  
    SIMD,PVP,SMP,MPP,COW,DSM L;7u0Yg  
    并行计算机的互连方式 <y S| \Z|  
    静态：LA(LC),MC,TC,MT,HC,BC,SE v)b_bU]Hx  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) -JEiwi,  
1.2 并行计算模型 |rgp(;iO  
    PRAM模型：SIMD-SM， <2n5|.:>  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW kF;N}O2?{  
    SIMD-IN模型：SIMD-DM rAn:hR
{  
    异步APRAM模型：MIMD-SM o7r7HmA@  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 d-sT+4o}  
    LogP模型：MIMD-DM，点到点通讯 e9=UTn{!  
1.3 并行算法的一般概念 u|mTF>L  
    并行算法的定义 (GW"iL#.  
    并行算法的表示 ~n"?*I`  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 k-Z:z?M  
    并行算法的WT表示：Brent定理、WT最优 e7S
p?>-d  
    加速比性能定律(略) kR+7JUq]  
    并行算法的同步和通讯(略) /fSsh;F  
Ch2 并行算法的基本设计技术 B? aMX,1  
2.1 并行算法的三种基本设计方法 AI^!?nJ%'  
2.2 基本设计技术 = yFOH~_  
    平衡树方法：求最大值、计算前缀和 -d.i4X3j  
    倍增技术：表序问题、求森林的根 hh-a+] c0  
    分治策略：FFT分治算法 YNB7`:  
    划分原理： l
u?:1V-  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) #`ZBA>FLaQ  
    流水线技术：五点的DFT计算，Systolic算法 GJ{XlH  
    加速级联(略) !,^y!+,Qy  
    破对称技术 .0rTk$B  
Ch3 比较器网络上的排序和选择算法 A"O\u=!  
3.1 Batcher归并和排序 #P1U]@  
    0-1原理的证明(略) l>?f+70  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) KO\-|#3y>  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) zm{`+boH<  
    Batcher排序网络：原理、种类和复杂性 nMJ(tQ  
3.2 (m, n)-选择网络 kWacc&*|  
    分组选择网络 *10qP?0H  
    平衡分组选择网络及其改进 c
*y*UG  
Ch4 排序和选择的同步算法 I)kc[/^j$  
4.1 一维线性阵列上的并行排序算法(略) o`Af6C;Q  
4.2 二维Mesh上的并行排序算法 Dkx}}E:<  
    ShearSort排序算法 %^d<go^  
    Thompson&Kung双调排序算法及其计算示例 n2~WUK  
4.3 Stone双调排序算法(略) ,c-*/{3  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 J(K/z,4h  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析  LJ;&02w@  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 %{7*o5`
 
Ch5 排序和选择的异步和分布式算法(略) 6oq5CDoq  
5.1 MIMD-CREW模型上的异步枚举排序算法 ACy}w?D<  
5.2 MIMD-TC模型上的异步快排序算法 mK/E1a)AG3  
5.3分布式k-选择算法 +p`BoF9~  
Ch6 并行搜索 "iGQ1#6|d  
6.1 单处理器上的搜索(略) A|4om=MO  
6.2 SIMD共享存储模型上有序表的搜索：算法 a~J!G
:(  
6.3 SIMD共享存储模型上随机序列的搜索：算法 c|(J%@B)  
6.4 树连接的SIMD模型上随机序列的搜索：算法 6"+9$nFyW  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 x[$KZGK+GL  
Ch8 数据传输与选路 9XYm8g'X  
8.1 引言  xAl 8e  
    信包传输性能参数 @/?i|!6  
    维序选路(X-Y选路、E-立方选路) NMfHrYHbh  
    选路模式及其传输时间公式  A'rd1"K  
8.2 单一信包一到一传输 Dn@ZS_f  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) 9-V'U\}L  
8.3 一到多播送 k\qFWFR  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 MUsF  
8.4 多到多播送 9r+'DX?>  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 ~;]kqYIJ  
8.5 贪心算法(书8.2) l*OR{!3H$  
    二维阵列上的贪心算法 zw U[!i)  
    蝶形网上的贪心算法 @MVul_@6  
8.6 随机和确定的选路算法(书8.3)(略) 9Bw #VQ  
Ch12矩阵运算 7M4J{}9  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 =R'O5J  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 _tX=xAO9  
12.3 矩阵向量乘法 qEXN}P
q<  
    带状划分的算法及其时间分析 J'sa{/ #  
    棋盘划分的算法及其时间分析 EnlAgL']|  
    Systolic算法(略) qzJ<9H  
12.4 矩阵乘法 HV)aVkr/&  
    简单并行分块算法 &PRoT#,  
    Cannon算法及其计算示例 _J!&R:]$  
    Fox算法及其计算示例 k9OGnCW\  
    DNS算法及其计算示例 ,8Po _[  
    Systolic算法(略) &K60n6q{aQ  
Ch13 数值计算 /q\e&&e  
13.1 稠密线性方程组求解 ,>rvl P  
    SIMD-CREW的上三角方程组回代算法 Nj3iZD|  
    SIMD-CREW上的Gauss-Jordan算法 ZHN'j]?  
    MIMD-CREW上的Gauss-Seidel算法 C{pOGc@  
13.2 稀疏线性方程组的求解 yD7}  
    三对角方程组的奇偶规约求解法 S}VS@KDO  
    Gauss-Seidel迭代法的红黑着色并行算法 i(;`x  
13.3 非线性方程的求根(略) '7el`Ff  
Ch14 快速傅立叶变换FFT f0sGE5  
14.1 快速傅里叶变换(FFT) 1J"9Y81  
    离散傅里叶变换(DFT) b{ xlW }S  
    串行FFT递归算法及其计算原理 g?v
(>#i  
    串行FFT蝶式计算及其蝶式计算流图 W6i{yneW  
14.2 DFT直接并行算法 iBAP,cR?`  
    SIMD-MT上的并行DFT算法(略) C$6FI
`J  
14.3 并行FFT算法 YPI)^ }  
    SIMD-MC上的FFT算法(略) Ql)hIf$Oo  
    SIMD-BF上的FFT算法及其时间分析 8i`>],,ch  
Ch15 图论算法 \OVtvJV]  
15.1 图的并行搜索 5F~l;zT  
    p-深度优先搜索及其计算示例 rl%,9JD!  
    p-宽深优先搜索及其计算示例 X n!md R  
    p-宽度优先搜索及其计算示例 #mu L-V  
15.2 图的传递闭包 lJu^Bcrv  
    基于布尔矩阵乘积的算法原理 ?x #K:a?  
    计算示例 JyM k @Y  
    SIMD-CC上的传递闭包算法 tr,W)5O@L  
15.3 图的连通分量
A%.mIc.  
    基于传递闭包的算法 ,-y9P  
    基于顶点合并的算法 )FQ"l{P  
15.4 图的最短路径 ?ZRF]\dP]  
    基于矩阵乘积的算法原理 AYA{_^#+3  
    计算示例
`3rwqcxA  
15.5 图的最小生成树 a'i Q("  
    SIMD-EREW模型上的Prim算法 Sf,z   
    算法的时间分析  l!|c_  
Ch18 随机算法 CjQO5  
18.1 引言 ^}=)jLS  
    基本知识：随机算法的定义、分类、重复性定律 'K,\
  
    时间复杂性度量 {q0
+PzgP  
    设计方法 >j5\J_(;D  
18.2 低度顶点部分独立集 YP2VSK2Q  
    串行算法 ?gE=hh  
    随机并行算法及其正确性证明 .{1$;K @  
18.5 多项式恒等的验证 &bsq;)wzs  
    基本原理和方法 ;28d7e}  
    矩阵乘积的验证原理 Xsq @E#@S  
18.8 格点逼近问题(略) k)p`x"To  
18.9 SAT问题的异步随机并行算法(略) &BVH
Q7[  
Ch20 模型与下界 bwsKdh  
20.1不同的PRAM模型的相互模拟 +MoUh'/u  
    PRAM-EREW模拟PPRAM-CRCW ,MY7h8V/  
    PRAM-CRCW之间的模拟 :;k?/KU7  
20.2下界 FZe/3sY  
    算法研究的两个方向：优化（上界）、可能性（下界） :5t4KcQ  
    Gates的工作 !7N:cx'Qy  
    理想的PRAM模型与下界 NdXHpq;  
    PRAM模型的下界 8?yIixhw  
20.3 NP完全理论导引(略) O =Z}DGa+  
20.4 P完全理论(略)