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

《并行算法》课程总结与复习 C*6S@4k  
Ch1 并行算法基础 E8}+k o  
1.1 并行计算机体系结构 H}0dd"  
    并行计算机的分类 JqUADm  
    SISD,SIMD,MISD,MIMD； !>^JSHR4t  
    SIMD,PVP,SMP,MPP,COW,DSM ;&;W
T  
    并行计算机的互连方式 v Y| !  
    静态：LA(LC),MC,TC,MT,HC,BC,SE B/uniR^x  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) l 95<QI  
1.2 并行计算模型 d.<~&.-$  
    PRAM模型：SIMD-SM， tJI ,r_  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW +{`yeZ9S  
    SIMD-IN模型：SIMD-DM lT8\}hNI+  
    异步APRAM模型：MIMD-SM VrP}#3I  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 uV6g[J  
    LogP模型：MIMD-DM，点到点通讯 2YwVU.*>  
1.3 并行算法的一般概念 TQ :/RT  
    并行算法的定义 Tp%(I"H'_;  
    并行算法的表示 eARk QV  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 {OMgd3%14  
    并行算法的WT表示：Brent定理、WT最优 %kI} [6J_  
    加速比性能定律(略) g9h(sLSF  
    并行算法的同步和通讯(略) 7LZ^QC  
Ch2 并行算法的基本设计技术 tOd T[&  
2.1 并行算法的三种基本设计方法 M+ +0zh
S  
2.2 基本设计技术 8s}J!/2  
    平衡树方法：求最大值、计算前缀和 jh ez  
    倍增技术：表序问题、求森林的根 SqPtWEq@P  
    分治策略：FFT分治算法 =Ov7C[(  
    划分原理： `|e!Kq?#Q  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) XH4d<?qu  
    流水线技术：五点的DFT计算，Systolic算法 M7}Q=q\9
 
    加速级联(略) X~T/qFS  
    破对称技术 - Xupq/[,  
Ch3 比较器网络上的排序和选择算法 LC69td&  
3.1 Batcher归并和排序 (-yl|NFBw  
    0-1原理的证明(略) ]TpU"JD  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) &K%aw  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) wGKo.lt   
    Batcher排序网络：原理、种类和复杂性 |WqOk~)[Z3  
3.2 (m, n)-选择网络 &V=7D#L  
    分组选择网络 >wON\N0V_  
    平衡分组选择网络及其改进 #B}?Zg  
Ch4 排序和选择的同步算法 <-C!;Ce{  
4.1 一维线性阵列上的并行排序算法(略) <lwuTow  
4.2 二维Mesh上的并行排序算法 Un=a fX?j  
    ShearSort排序算法 r#876.JK  
    Thompson&Kung双调排序算法及其计算示例 OKue" p  
4.3 Stone双调排序算法(略) 3}Xc71|v  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析  $g8}^1  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 $xW**&  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 >l1r,/\\
 
Ch5 排序和选择的异步和分布式算法(略) Utl t<  
5.1 MIMD-CREW模型上的异步枚举排序算法 eD#XDK  
5.2 MIMD-TC模型上的异步快排序算法 'ig, ATY  
5.3分布式k-选择算法 NP t(MFK\  
Ch6 并行搜索 u=K2 Q4  
6.1 单处理器上的搜索(略) d"<F!?8  
6.2 SIMD共享存储模型上有序表的搜索：算法 S3\jcgrS  
6.3 SIMD共享存储模型上随机序列的搜索：算法 ? Nj)6_&  
6.4 树连接的SIMD模型上随机序列的搜索：算法 L:f)i,S"5q  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 b5`KB75sbo  
Ch8 数据传输与选路 wT_^'i*@I  
8.1 引言 KX+ey8@[  
    信包传输性能参数 a|qsQ'1,;  
    维序选路(X-Y选路、E-立方选路) ';YgG<u  
    选路模式及其传输时间公式 XAic9SNu;  
8.2 单一信包一到一传输 f6ZZ}lwaV  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) wyQb5n2`;~  
8.3 一到多播送 fEqC] *s  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 )2j:z#'>  
8.4 多到多播送 &a #GXf  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 4O$2]D.\  
8.5 贪心算法(书8.2) @p!Q1-]=  
    二维阵列上的贪心算法 #BJ\{"b_}z  
    蝶形网上的贪心算法 *@M3p}',M  
8.6 随机和确定的选路算法(书8.3)(略) S!dHNA:iU  
Ch12矩阵运算 7`Du5>b8  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 5P+YK\~  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 &=w|vB)(p  
12.3 矩阵向量乘法 r _o<SH  
    带状划分的算法及其时间分析 !#}>Hv^N  
    棋盘划分的算法及其时间分析 #x)}29%e#  
    Systolic算法(略) j$PI,
`  
12.4 矩阵乘法 ]Z@k|Nw  
    简单并行分块算法 OlGR<X  
    Cannon算法及其计算示例
*x,HnHT  
    Fox算法及其计算示例 YmDn+VIg  
    DNS算法及其计算示例 &oN/_7y  
    Systolic算法(略) <Jwo?[a  
Ch13 数值计算 #v/ry)2Y=  
13.1 稠密线性方程组求解 >d%VDjk .  
    SIMD-CREW的上三角方程组回代算法 _E
x?Xk  
    SIMD-CREW上的Gauss-Jordan算法 2Ow<`[7  
    MIMD-CREW上的Gauss-Seidel算法 _S5gcPcF"  
13.2 稀疏线性方程组的求解 mQ,{=C=D  
    三对角方程组的奇偶规约求解法 :~-i&K
Nk  
    Gauss-Seidel迭代法的红黑着色并行算法 !%62Phai  
13.3 非线性方程的求根(略) 9[{sEg=C$e  
Ch14 快速傅立叶变换FFT hAAUecx  
14.1 快速傅里叶变换(FFT) fI}c 71b`  
    离散傅里叶变换(DFT) m/?h2McS  
    串行FFT递归算法及其计算原理 j],&z^O$  
    串行FFT蝶式计算及其蝶式计算流图 *`.LA@bHU  
14.2 DFT直接并行算法 )52#:27F  
    SIMD-MT上的并行DFT算法(略) <G9<"{  
14.3 并行FFT算法 O3xz|&xY&  
    SIMD-MC上的FFT算法(略) ^0eO\wc?O  
    SIMD-BF上的FFT算法及其时间分析 a
m(#Fa  
Ch15 图论算法 JP%RTGu  
15.1 图的并行搜索 wRi~Yb?  
    p-深度优先搜索及其计算示例  J[o
${^  
    p-宽深优先搜索及其计算示例 @7X\tV.Z  
    p-宽度优先搜索及其计算示例 Bxt_a.LthH  
15.2 图的传递闭包 dcP88!#5-  
    基于布尔矩阵乘积的算法原理 Q'C4pn@  
    计算示例 Vy r] x  
    SIMD-CC上的传递闭包算法 x{j+}'9  
15.3 图的连通分量 C\/b~HU  
    基于传递闭包的算法 R/rcXX7%  
    基于顶点合并的算法 Tz2x9b\82  
15.4 图的最短路径 ^@Y9!G=  
    基于矩阵乘积的算法原理 Y`q!V=  
    计算示例 J]\s*,C&  
15.5 图的最小生成树 fGG 9zB6  
    SIMD-EREW模型上的Prim算法 uiuTv)pwF  
    算法的时间分析 dkETM,
 
Ch18 随机算法 '%:5axg?]  
18.1 引言 }il%AAI9}r  
    基本知识：随机算法的定义、分类、重复性定律 <BQ%8}  
    时间复杂性度量 PQQgDtiH  
    设计方法 01-p `H+  
18.2 低度顶点部分独立集 LuLy6]6D;  
    串行算法 <kROH0+  
    随机并行算法及其正确性证明 1RURZoL  
18.5 多项式恒等的验证 l(.7t'  
    基本原理和方法 ADTU{6UPS  
    矩阵乘积的验证原理 Bk@bN~B4  
18.8 格点逼近问题(略) 3SmqXPOw  
18.9 SAT问题的异步随机并行算法(略) EWSr@}2j .  
Ch20 模型与下界 T3 =) F%  
20.1不同的PRAM模型的相互模拟 T..-)kL+p  
    PRAM-EREW模拟PPRAM-CRCW )0'Y et}  
    PRAM-CRCW之间的模拟 n})  
20.2下界 DrW/KU,{+(  
    算法研究的两个方向：优化（上界）、可能性（下界） n(9F:N  
    Gates的工作 o@Dk%LxP  
    理想的PRAM模型与下界 KwY`<t1lA;  
    PRAM模型的下界 ,^Ex }Z  
20.3 NP完全理论导引(略) 5L/Yi  
20.4 P完全理论(略)