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

《并行算法》课程总结与复习 Z;JZ<vEt92  
Ch1 并行算法基础 +C !A@  
1.1 并行计算机体系结构 "i_}\p.,X  
    并行计算机的分类 'u2Qq"d+
 
    SISD,SIMD,MISD,MIMD； +iPS=
?S  
    SIMD,PVP,SMP,MPP,COW,DSM RFkJ^=}  
    并行计算机的互连方式 XJ;JDch  
    静态：LA(LC),MC,TC,MT,HC,BC,SE (7rG~d1iS  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) 1xo<V5  
1.2 并行计算模型 g3%t+>$*  
    PRAM模型：SIMD-SM， Ucnit^,  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW U)p P^:|  
    SIMD-IN模型：SIMD-DM ;G3{ e  
    异步APRAM模型：MIMD-SM r(yb%p+  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 wWflZ"%  
    LogP模型：MIMD-DM，点到点通讯 UmU=3et<Wj  
1.3 并行算法的一般概念 "t"=9:_t  
    并行算法的定义 .n`MPx'  
    并行算法的表示 viBf".  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 /=\__$l)  
    并行算法的WT表示：Brent定理、WT最优 +-#| M|a  
    加速比性能定律(略) $hO8 S=  
    并行算法的同步和通讯(略) 0p$?-81BJ  
Ch2 并行算法的基本设计技术 |P2GL3NR  
2.1 并行算法的三种基本设计方法 !U/:!e`N  
2.2 基本设计技术 {R,rc!yF  
    平衡树方法：求最大值、计算前缀和 wy_TFV  
    倍增技术：表序问题、求森林的根 0tB9X9:,  
    分治策略：FFT分治算法 2#1FI0,Pa*  
    划分原理： mXF pGo5 s  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) zAB-kE\)  
    流水线技术：五点的DFT计算，Systolic算法 S,S_BB<Y[b  
    加速级联(略) %_SE$>v^  
    破对称技术 kC9A  
Ch3 比较器网络上的排序和选择算法 &"C1XM  
3.1 Batcher归并和排序 dGh<R|U3  
    0-1原理的证明(略) x'JfRz  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) +bf%]   
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) V |?  
    Batcher排序网络：原理、种类和复杂性 ;N"XW=F4e  
3.2 (m, n)-选择网络 Cfz1\a&V{  
    分组选择网络 7P|(j<JX6'  
    平衡分组选择网络及其改进 Bdbw!zRR$  
Ch4 排序和选择的同步算法 [S</QS!  
4.1 一维线性阵列上的并行排序算法(略) aeBth{  
4.2 二维Mesh上的并行排序算法 Dh +^;dQ6  
    ShearSort排序算法 s^KxAw_IV  
    Thompson&Kung双调排序算法及其计算示例 U-n33ty`H  
4.3 Stone双调排序算法(略) 6/#= dv  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 [[s k  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 4a2&kIn  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 ":-)mfgGU  
Ch5 排序和选择的异步和分布式算法(略) ? ! 1uw  
5.1 MIMD-CREW模型上的异步枚举排序算法 swLgdk{8
n  
5.2 MIMD-TC模型上的异步快排序算法 ([9h.M6v  
5.3分布式k-选择算法 SV\x2 ^Ea0  
Ch6 并行搜索 BgpJ;D+N4  
6.1 单处理器上的搜索(略) M2zfN ru  
6.2 SIMD共享存储模型上有序表的搜索：算法 >$Fc=~;Ba  
6.3 SIMD共享存储模型上随机序列的搜索：算法 s~]nsqLt9p  
6.4 树连接的SIMD模型上随机序列的搜索：算法 40c#zCE  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 g3Xz-  
Ch8 数据传输与选路 ~hxB Pn."  
8.1 引言 yh0|f94m  
    信包传输性能参数 )$]+R
?v  
    维序选路(X-Y选路、E-立方选路) %cm5Z^B1"  
    选路模式及其传输时间公式 -91l"sI  
8.2 单一信包一到一传输 q;>BltU  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) !gk\h  
8.3 一到多播送 TAAsV#l  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 Ch.T}%  
8.4 多到多播送 ]Z84w!z  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 5PPy+3
6<~  
8.5 贪心算法(书8.2) )-QNWN H  
    二维阵列上的贪心算法 }agl:~C  
    蝶形网上的贪心算法 3=<iGX"z  
8.6 随机和确定的选路算法(书8.3)(略) NuooA  
Ch12矩阵运算 XeB>V.<y  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 V? O%kd  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 - dOT/%Ux  
12.3 矩阵向量乘法 z67=v9+7  
    带状划分的算法及其时间分析 F889JSZ%  
    棋盘划分的算法及其时间分析 L
|2COX  
    Systolic算法(略) 28)TXR r-  
12.4 矩阵乘法 ~r!5d@f.6  
    简单并行分块算法 qE` =^  
    Cannon算法及其计算示例 ?V{k\1A  
    Fox算法及其计算示例 >b["T+  
    DNS算法及其计算示例 fD~!t 8J  
    Systolic算法(略) B@;)$1-UT  
Ch13 数值计算 NqZRS>60v  
13.1 稠密线性方程组求解 Hr+-ndH!Pq  
    SIMD-CREW的上三角方程组回代算法 jSFN/C.9h  
    SIMD-CREW上的Gauss-Jordan算法 
#c^Q<&B  
    MIMD-CREW上的Gauss-Seidel算法 NVjJ/  
13.2 稀疏线性方程组的求解 +r0eTP=zf  
    三对角方程组的奇偶规约求解法 yo*iv+l  
    Gauss-Seidel迭代法的红黑着色并行算法 ;ULC|7rL  
13.3 非线性方程的求根(略) ?&"^ \p  
Ch14 快速傅立叶变换FFT vaj66nV  
14.1 快速傅里叶变换(FFT) >$mSFJz5S  
    离散傅里叶变换(DFT) _=L;`~=C9e  
    串行FFT递归算法及其计算原理 t%U[\\ic  
    串行FFT蝶式计算及其蝶式计算流图 s\W  
14.2 DFT直接并行算法 &'7"i~pC  
    SIMD-MT上的并行DFT算法(略) g&4~nEp  
14.3 并行FFT算法 
j/9
QV  
    SIMD-MC上的FFT算法(略) CjQ"oQw  
    SIMD-BF上的FFT算法及其时间分析 4VNb`!e  
Ch15 图论算法 d=Do@) m|  
15.1 图的并行搜索 uXLZtfu
{  
    p-深度优先搜索及其计算示例 ]zyX@=mM  
    p-宽深优先搜索及其计算示例 ZCBPO~&hO'  
    p-宽度优先搜索及其计算示例 )@qup _M@  
15.2 图的传递闭包 P/pjy  
    基于布尔矩阵乘积的算法原理 m`$>:B  
    计算示例 Blbq3y+Sq  
    SIMD-CC上的传递闭包算法 yIIET E  
15.3 图的连通分量 5}
eQaW48  
    基于传递闭包的算法 _;:rkC fj  
    基于顶点合并的算法 NGD*ce"w  
15.4 图的最短路径 g(<T u^F  
    基于矩阵乘积的算法原理 XY{:tR_al  
    计算示例 d;~ 3P   
15.5 图的最小生成树 poD\C;o"  
    SIMD-EREW模型上的Prim算法 7%9)C[6NSs  
    算法的时间分析 Ka]@[R6
e  
Ch18 随机算法 U,<]J*b(@4  
18.1 引言 f<89$/w
 
    基本知识：随机算法的定义、分类、重复性定律 w(/DTQc~d  
    时间复杂性度量 mP pvZ  
    设计方法 :)p)=c8%  
18.2 低度顶点部分独立集 .Z=Ce!  
    串行算法 bar0{!Y"  
    随机并行算法及其正确性证明 wmo{YS3t|  
18.5 多项式恒等的验证 SY,I>- %  
    基本原理和方法 a@#Q:O)4  
    矩阵乘积的验证原理 0e+W/Tq  
18.8 格点逼近问题(略) =4tO0  
18.9 SAT问题的异步随机并行算法(略) :N@U[Wx0A  
Ch20 模型与下界 ~BZXt7DE  
20.1不同的PRAM模型的相互模拟 $n= O  
    PRAM-EREW模拟PPRAM-CRCW r C_d$Jv  
    PRAM-CRCW之间的模拟 G02ox5X  
20.2下界 RF_[?O)Q  
    算法研究的两个方向：优化（上界）、可能性（下界） qy_%~c87  
    Gates的工作 _Vjpw,  
    理想的PRAM模型与下界 .^i<
xY  
    PRAM模型的下界 {A|bBg1!  
20.3 NP完全理论导引(略) ~TDzq -U)  
20.4 P完全理论(略)