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

《并行算法》课程总结与复习 9ECS,r*B  
Ch1 并行算法基础 cjT[P"5$  
1.1 并行计算机体系结构 7^wE$
7hS  
    并行计算机的分类 H m8y]>$  
    SISD,SIMD,MISD,MIMD； W-Of[X{<  
    SIMD,PVP,SMP,MPP,COW,DSM jtLnj@,  
    并行计算机的互连方式 $rB!Ex{@ac  
    静态：LA(LC),MC,TC,MT,HC,BC,SE B1,?{Ur  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) y:9?P~  
1.2 并行计算模型 Iaa|qJ
4  
    PRAM模型：SIMD-SM， )0F^NU  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW Sj1r s#@1  
    SIMD-IN模型：SIMD-DM bL MkPty  
    异步APRAM模型：MIMD-SM 3N3*`?5c<  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 Zh? V,39  
    LogP模型：MIMD-DM，点到点通讯 k(9s+0qe  
1.3 并行算法的一般概念  J[o
${^  
    并行算法的定义 @7X\tV.Z  
    并行算法的表示 |rFJ*.nD  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 ec1Fg0Fa  
    并行算法的WT表示：Brent定理、WT最优 o
VreP  
    加速比性能定律(略) o{g@Nk'f  
    并行算法的同步和通讯(略) V^WQ6G1  
Ch2 并行算法的基本设计技术 6Ok,_ !  
2.1 并行算法的三种基本设计方法 F]0Jwm{  
2.2 基本设计技术 /rOnm=P+Q  
    平衡树方法：求最大值、计算前缀和 d4V 2[TX  
    倍增技术：表序问题、求森林的根 vj(@.uU)  
    分治策略：FFT分治算法 @21
u I{  
    划分原理： uiuTv)pwF  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) Ho>p ^p  
    流水线技术：五点的DFT计算，Systolic算法 p>!1S  
    加速级联(略) z(jU|va{_1  
    破对称技术 %qONJP  
Ch3 比较器网络上的排序和选择算法 Jfe~ ,cI  
3.1 Batcher归并和排序 c.\:peDk  
    0-1原理的证明(略) EJv!tyJ\[  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) tI `w;e%HN  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) -5o?#%  
    Batcher排序网络：原理、种类和复杂性 <%he o  
3.2 (m, n)-选择网络 e1oFnu2R  
    分组选择网络 Q-:Ah:/  
    平衡分组选择网络及其改进 ?Z5$0-g'hU  
Ch4 排序和选择的同步算法 ST#PMb'izn  
4.1 一维线性阵列上的并行排序算法(略) ws#hhW3qK  
4.2 二维Mesh上的并行排序算法 FyQOa)5  
    ShearSort排序算法 H+nr5!`kz  
    Thompson&Kung双调排序算法及其计算示例 Qh/ lT$g  
4.3 Stone双调排序算法(略) >>/nuWdpO  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 \%P ma8&d  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 $hC~af6  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 9Y;}JVS  
Ch5 排序和选择的异步和分布式算法(略) ~_(!}V
 
5.1 MIMD-CREW模型上的异步枚举排序算法 *sIi$1vHu  
5.2 MIMD-TC模型上的异步快排序算法 g]:..W7  
5.3分布式k-选择算法 AviT+^7E  
Ch6 并行搜索 3xc:Y> *`  
6.1 单处理器上的搜索(略) mm3zQ!2j.  
6.2 SIMD共享存储模型上有序表的搜索：算法 N;%j#(v j  
6.3 SIMD共享存储模型上随机序列的搜索：算法 E>o&GYc
 
6.4 树连接的SIMD模型上随机序列的搜索：算法 0;.e#(`-  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 ch%Q'DR_I)  
Ch8 数据传输与选路 wCqE4i  
8.1 引言 6,sR avs  
    信包传输性能参数 +:j4G^V  
    维序选路(X-Y选路、E-立方选路) \Qe'?LRu{  
    选路模式及其传输时间公式 W+fkWq7`Xx  
8.2 单一信包一到一传输 h5h-}qBA  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) vLVSZX
 
8.3 一到多播送 T1Ln)CS?9  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 >EPaZp6  
8.4 多到多播送 BbXmT"@  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 IFHgD}kp%#  
8.5 贪心算法(书8.2) YB(#]H|8S  
    二维阵列上的贪心算法 R$~JhcX*l'  
    蝶形网上的贪心算法 B)LXxdkOn  
8.6 随机和确定的选路算法(书8.3)(略) U^W
Q
Wa  
Ch12矩阵运算 hNgcE,67q  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 Y D1g]p  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 lW@
:q04Z$  
12.3 矩阵向量乘法 JJ= ~o@|c  
    带状划分的算法及其时间分析 6M2i?c  
    棋盘划分的算法及其时间分析 vM$#m1L?  
    Systolic算法(略) 2n\i0?RD  
12.4 矩阵乘法 ?j ;,q  
    简单并行分块算法 B@:XC&R^  
    Cannon算法及其计算示例 
X]f#w  
    Fox算法及其计算示例 `^@g2c+d  
    DNS算法及其计算示例 %E=,H?9&>  
    Systolic算法(略) bC>yIjCTn  
Ch13 数值计算 ESXU, qK]v  
13.1 稠密线性方程组求解 U~QCN[gh  
    SIMD-CREW的上三角方程组回代算法 `XRb:d^  
    SIMD-CREW上的Gauss-Jordan算法 Yqj.z|}Nb  
    MIMD-CREW上的Gauss-Seidel算法 7~k ~S>s O  
13.2 稀疏线性方程组的求解  s`{#[&[  
    三对角方程组的奇偶规约求解法 jTxChR  
    Gauss-Seidel迭代法的红黑着色并行算法 jmwQc&  
13.3 非线性方程的求根(略) ](( >i%%~  
Ch14 快速傅立叶变换FFT % /wP2O<  
14.1 快速傅里叶变换(FFT) f%{ ag  
    离散傅里叶变换(DFT) -n$rKEC4  
    串行FFT递归算法及其计算原理 Z!BQtICs  
    串行FFT蝶式计算及其蝶式计算流图 0OoO cc  
14.2 DFT直接并行算法 TW;;OS[  
    SIMD-MT上的并行DFT算法(略) "YJ;-$rb  
14.3 并行FFT算法 `E1_S  
    SIMD-MC上的FFT算法(略) PX>\j&  
    SIMD-BF上的FFT算法及其时间分析 3[g++B."pC  
Ch15 图论算法 #p:jKAc3  
15.1 图的并行搜索 (YWc%f4  
    p-深度优先搜索及其计算示例 R5~vmT5W  
    p-宽深优先搜索及其计算示例 >[3,qP]E  
    p-宽度优先搜索及其计算示例 oVZ8p-  
15.2 图的传递闭包 9/qS*Zdh)  
    基于布尔矩阵乘积的算法原理 i1H80m s  
    计算示例 q\Io6=39x  
    SIMD-CC上的传递闭包算法 Nb,H8;
 
15.3 图的连通分量 sV4tu(~  
    基于传递闭包的算法 %<o$ J~l~  
    基于顶点合并的算法 /8-VC"   
15.4 图的最短路径 Ej 3hdi)  
    基于矩阵乘积的算法原理 H_r'q9@<>  
    计算示例 >Ti2E+}[M  
15.5 图的最小生成树 (6y3"cbe  
    SIMD-EREW模型上的Prim算法 h+d;`7Z>  
    算法的时间分析 Zkep7L   
Ch18 随机算法 j24  
18.1 引言 &1C9K>  
    基本知识：随机算法的定义、分类、重复性定律 ZUI\0qh+  
    时间复杂性度量 8 =Lv7G%  
    设计方法 <UL|%9=~  
18.2 低度顶点部分独立集 )'CEWc%  
    串行算法 MOeLphY  
    随机并行算法及其正确性证明 >43yty\   
18.5 多项式恒等的验证 /'_ RI  
    基本原理和方法 ti2_kYq  
    矩阵乘积的验证原理 `*!>79_2C  
18.8 格点逼近问题(略) T/6=A$4 #  
18.9 SAT问题的异步随机并行算法(略) dct#ECT  
Ch20 模型与下界 YfU#kvE'  
20.1不同的PRAM模型的相互模拟 oKJ7i,xT  
    PRAM-EREW模拟PPRAM-CRCW ~,1q :Kue  
    PRAM-CRCW之间的模拟 >U/g*[>  
20.2下界 Bb"4^EOZ,  
    算法研究的两个方向：优化（上界）、可能性（下界） <~*Ol+/  
    Gates的工作 4^^rOi0  
    理想的PRAM模型与下界 Y6PA\7Y\  
    PRAM模型的下界 j'x{j %U  
20.3 NP完全理论导引(略) e;[8GE.   
20.4 P完全理论(略)