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

《并行算法》课程总结与复习 :"oQ _bLT  
Ch1 并行算法基础 ]wQ#8}zO  
1.1 并行计算机体系结构 Cg!]x o  
    并行计算机的分类 ZOK,P
 
    SISD,SIMD,MISD,MIMD； =7U_ jDME  
    SIMD,PVP,SMP,MPP,COW,DSM )Q%hd|R  
    并行计算机的互连方式 J!GWP:b3  
    静态：LA(LC),MC,TC,MT,HC,BC,SE g}B|ZRz+{  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) 0Th
X1)SH  
1.2 并行计算模型 @N-P[.qL"  
    PRAM模型：SIMD-SM， [*k25N  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW +W6QtB6  
    SIMD-IN模型：SIMD-DM &7YTz3aj  
    异步APRAM模型：MIMD-SM A
Ge\PCn-  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 /b)V=mcR  
    LogP模型：MIMD-DM，点到点通讯 |9F^"7Q~C  
1.3 并行算法的一般概念 m*d {pX  
    并行算法的定义 dt -=7mz#  
    并行算法的表示 w)hH8jx{  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 Jmp%%
^  
    并行算法的WT表示：Brent定理、WT最优 VqeK~,}  
    加速比性能定律(略) 4[ 7)$  
    并行算法的同步和通讯(略) {v,O  
Ch2 并行算法的基本设计技术 m;S!E-W  
2.1 并行算法的三种基本设计方法 )\bA'LuFy  
2.2 基本设计技术 \!erP!$x.  
    平衡树方法：求最大值、计算前缀和 D[7+xAwS  
    倍增技术：表序问题、求森林的根 (W~')A"hC'  
    分治策略：FFT分治算法 NEpom
E(>x  
    划分原理： _dgS@n;6  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) u]W$'MyY  
    流水线技术：五点的DFT计算，Systolic算法 F.s*^}L[  
    加速级联(略) 1gA9h-'w  
    破对称技术 zJH#J=O  
Ch3 比较器网络上的排序和选择算法 {
W[OjPC~F  
3.1 Batcher归并和排序 zT\nj&7  
    0-1原理的证明(略) [IF5Iv\b  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) 6%hr]>L  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Md4hd#z  
    Batcher排序网络：原理、种类和复杂性 J
H4hy 9i  
3.2 (m, n)-选择网络 H+ P&} 3  
    分组选择网络 ~]MACG:'  
    平衡分组选择网络及其改进 +[JvpDv%  
Ch4 排序和选择的同步算法 AG3iKk??T  
4.1 一维线性阵列上的并行排序算法(略) qT<OiIMj^  
4.2 二维Mesh上的并行排序算法 D#=$? {w  
    ShearSort排序算法 ^V1.Y  
    Thompson&Kung双调排序算法及其计算示例 o =oXL2}  
4.3 Stone双调排序算法(略) |XDbf3^6  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 WE-cq1)  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 tJ"8"T#6Vr  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 88@" +2  
Ch5 排序和选择的异步和分布式算法(略) 6n|R<DO%\  
5.1 MIMD-CREW模型上的异步枚举排序算法 o9<)rUy  
5.2 MIMD-TC模型上的异步快排序算法 4Bn <L&@/  
5.3分布式k-选择算法 MO_-7,.y  
Ch6 并行搜索 o*fNY  
6.1 单处理器上的搜索(略) ?M}W;Z  
6.2 SIMD共享存储模型上有序表的搜索：算法 Jq5](F!z  
6.3 SIMD共享存储模型上随机序列的搜索：算法 L
@|xpq  
6.4 树连接的SIMD模型上随机序列的搜索：算法 1edeV48{:  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 (GeOD V?U  
Ch8 数据传输与选路 wNfWHaH" m  
8.1 引言 !_No\O  
    信包传输性能参数 @@1Sxv_  
    维序选路(X-Y选路、E-立方选路) ]8m_+:`=  
    选路模式及其传输时间公式 Vx~N`|yY  
8.2 单一信包一到一传输 W x`|u  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) <`f~Z|/-_(  
8.3 一到多播送 * NB:"1x  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 4Odf6v,*@  
8.4 多到多播送 S^,q{x*T  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 O>M4%p  
8.5 贪心算法(书8.2) O$K?2-  
    二维阵列上的贪心算法 &^I2NpT  
    蝶形网上的贪心算法 ju8DmC5  
8.6 随机和确定的选路算法(书8.3)(略)  j1sgvh]D  
Ch12矩阵运算 ImG7E w  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分
/7o{%~O  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 u&npUw^Va  
12.3 矩阵向量乘法 Lc?q0x^s  
    带状划分的算法及其时间分析 )Bb:?!EuEH  
    棋盘划分的算法及其时间分析 RHIGNzSz  
    Systolic算法(略) 5ieF8F%  
12.4 矩阵乘法 qJyGr ?  
    简单并行分块算法 <`P7^ 'z!  
    Cannon算法及其计算示例 # VAL\Z  
    Fox算法及其计算示例 4r-CF#o  
    DNS算法及其计算示例 TEEt]R-y  
    Systolic算法(略) z"PU`v  
Ch13 数值计算 SU$%nK)  
13.1 稠密线性方程组求解 Y *?hA'  
    SIMD-CREW的上三角方程组回代算法 w dpd`  
    SIMD-CREW上的Gauss-Jordan算法
()`cW>[  
    MIMD-CREW上的Gauss-Seidel算法 *vS)aRK  
13.2 稀疏线性方程组的求解 5@/hqOiu  
    三对角方程组的奇偶规约求解法 6jpfo'uB$  
    Gauss-Seidel迭代法的红黑着色并行算法 .Z #8,<+  
13.3 非线性方程的求根(略) ])v WvNx  
Ch14 快速傅立叶变换FFT U3rpmml  
14.1 快速傅里叶变换(FFT) &3~_9+  
    离散傅里叶变换(DFT) k>W}9^ cK  
    串行FFT递归算法及其计算原理 #}8 x  
    串行FFT蝶式计算及其蝶式计算流图 I;rh(FMV  
14.2 DFT直接并行算法 {K ,-fbE  
    SIMD-MT上的并行DFT算法(略) DMpNmF>  
14.3 并行FFT算法 JM>4m)h#  
    SIMD-MC上的FFT算法(略) JXKo zy41  
    SIMD-BF上的FFT算法及其时间分析 'M=c-{f~  
Ch15 图论算法 {I p)%uR  
15.1 图的并行搜索 XMi)PXs$  
    p-深度优先搜索及其计算示例 ~X2 cTG
!,  
    p-宽深优先搜索及其计算示例 <v+M~"%V  
    p-宽度优先搜索及其计算示例 c8}jO=/5+  
15.2 图的传递闭包 [D= KI&@&O  
    基于布尔矩阵乘积的算法原理 EhK ~S(r^  
    计算示例 6SVh6o@]  
    SIMD-CC上的传递闭包算法 y>iote~  
15.3 图的连通分量 %LZ-i?DL4Q  
    基于传递闭包的算法 ;{S7bH'6m  
    基于顶点合并的算法 y _A7CG"^  
15.4 图的最短路径 ^/_
1 y[j  
    基于矩阵乘积的算法原理 y - Ge"mY  
    计算示例 GJP\vsaQ  
15.5 图的最小生成树 n^:Wc[[m  
    SIMD-EREW模型上的Prim算法 !PuW6  
    算法的时间分析 n1+,Pe*)  
Ch18 随机算法 &Rxy]kBA  
18.1 引言 ^iz2=}Q8  
    基本知识：随机算法的定义、分类、重复性定律 h&Q9
 
    时间复杂性度量 +t`QHvx v  
    设计方法 I$vM )+v=  
18.2 低度顶点部分独立集 _?J:Z*z?  
    串行算法 ~ @Au<  
    随机并行算法及其正确性证明 {nyVC%@Y  
18.5 多项式恒等的验证 WzxDnd<B  
    基本原理和方法 xfqW~&  
    矩阵乘积的验证原理 q[T='!Z\  
18.8 格点逼近问题(略) y*fU_Il|!  
18.9 SAT问题的异步随机并行算法(略) ^d[s*,i?  
Ch20 模型与下界 j@b18wZ  
20.1不同的PRAM模型的相互模拟 ' *x?8-KP  
    PRAM-EREW模拟PPRAM-CRCW AroXf#.  
    PRAM-CRCW之间的模拟 i][af  
20.2下界 Vg^@6zU  
    算法研究的两个方向：优化（上界）、可能性（下界） @vc
vte  
    Gates的工作 {2,OK=XM|  
    理想的PRAM模型与下界 |Lz:i+;  
    PRAM模型的下界 |[]"{Eo"}  
20.3 NP完全理论导引(略) =W Q_5}  
20.4 P完全理论(略)