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

《并行算法》课程总结与复习 QI[WXxp  
Ch1 并行算法基础 6?,qysm06  
1.1 并行计算机体系结构 vL_yM  
    并行计算机的分类 \Hb!<mrp  
    SISD,SIMD,MISD,MIMD； UovN"8W+  
    SIMD,PVP,SMP,MPP,COW,DSM e^*&&  
    并行计算机的互连方式 ,xU#uyB  
    静态：LA(LC),MC,TC,MT,HC,BC,SE >C,0}lj  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) o x SSEs  
1.2 并行计算模型 OX.5olb  
    PRAM模型：SIMD-SM， 0 -PT%R  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW dk
g`T#}  
    SIMD-IN模型：SIMD-DM d%}?%VH  
    异步APRAM模型：MIMD-SM (w-"1(  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 f IV"U  
    LogP模型：MIMD-DM，点到点通讯 MY{Kq;FvRP  
1.3 并行算法的一般概念 @|\;#$?XW3  
    并行算法的定义 Zs^zD;zU  
    并行算法的表示 QH>< ! sa  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 6MOwn*%5k  
    并行算法的WT表示：Brent定理、WT最优 C2LG@iCIE  
    加速比性能定律(略) 7r,GdP.  
    并行算法的同步和通讯(略) 7VfXE/  
Ch2 并行算法的基本设计技术 )[Rwc#PA;  
2.1 并行算法的三种基本设计方法 fV9+FOZn  
2.2 基本设计技术 8r}tf3xMCM  
    平衡树方法：求最大值、计算前缀和 v$`3}<3-  
    倍增技术：表序问题、求森林的根 5<X"+`=9  
    分治策略：FFT分治算法 MuO(%.H  
    划分原理： >WO;q  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 )
Y< ^Or  
    流水线技术：五点的DFT计算，Systolic算法 NjS<DzKhK  
    加速级联(略) gT []"ZT7  
    破对称技术 D0\*WK$  
Ch3 比较器网络上的排序和选择算法 ZLaht(`+  
3.1 Batcher归并和排序 eOVln1a  
    0-1原理的证明(略) G wgY{-|`  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) [)X(Qtk  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) u<
"-S63+  
    Batcher排序网络：原理、种类和复杂性
1OY 5tq  
3.2 (m, n)-选择网络 E0i!|H  
    分组选择网络 "kt7m  
    平衡分组选择网络及其改进 Gf7r!Ur;g  
Ch4 排序和选择的同步算法 P2>_qyX  
4.1 一维线性阵列上的并行排序算法(略) Ye^#]%m  
4.2 二维Mesh上的并行排序算法 aEUEy:.  
    ShearSort排序算法 (<`>B  
    Thompson&Kung双调排序算法及其计算示例 QeQwmI  
4.3 Stone双调排序算法(略) ME*zMLoF+  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 2e,cE6r  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 s7`2ky()kz  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 YqKQm+G  
Ch5 排序和选择的异步和分布式算法(略) 'uqY%&U  
5.1 MIMD-CREW模型上的异步枚举排序算法 Fyz1LOH[X  
5.2 MIMD-TC模型上的异步快排序算法 8N<2RT8W  
5.3分布式k-选择算法 MA=gCG/JD  
Ch6 并行搜索 %Q93n {?  
6.1 单处理器上的搜索(略) LK|rLoia:  
6.2 SIMD共享存储模型上有序表的搜索：算法 Y>i Qp/k:  
6.3 SIMD共享存储模型上随机序列的搜索：算法  #
3C]"  
6.4 树连接的SIMD模型上随机序列的搜索：算法 Zh:@AFz:R  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 utdus:B#0  
Ch8 数据传输与选路  =VSUE Pq  
8.1 引言 p1s& y0:d  
    信包传输性能参数 UnTvot6~  
    维序选路(X-Y选路、E-立方选路) H"JzTo8u  
    选路模式及其传输时间公式
(Ixmg=C6y  
8.2 单一信包一到一传输 *kGk.a=  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) FPAj}
as  
8.3 一到多播送 eeUEqM$7EX  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 VPDd*32HC  
8.4 多到多播送 dr=h;[Q'  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 DvBRK}'  
8.5 贪心算法(书8.2) O=}jg0k  
    二维阵列上的贪心算法 KupQtT<  
    蝶形网上的贪心算法 I|P#|0< 2  
8.6 随机和确定的选路算法(书8.3)(略) Y7@$#/1  
Ch12矩阵运算 Ly T[  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 D7,{p2<2T  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 d+6-ten  
12.3 矩阵向量乘法 '_M"yg6d  
    带状划分的算法及其时间分析 k 3oR:  
    棋盘划分的算法及其时间分析 ,uhOf! |  
    Systolic算法(略) $mDlS  
12.4 矩阵乘法 ~&8 bVA= .  
    简单并行分块算法 `^CIOCK%  
    Cannon算法及其计算示例 b~EA&dc
 
    Fox算法及其计算示例 kiR+ Dsl  
    DNS算法及其计算示例 <.c#l':  
    Systolic算法(略) Xp_G9I,+  
Ch13 数值计算
:)Z.!  
13.1 稠密线性方程组求解 =bl6:  
    SIMD-CREW的上三角方程组回代算法 {P $sQv  
    SIMD-CREW上的Gauss-Jordan算法 ]=T-Cv=t  
    MIMD-CREW上的Gauss-Seidel算法 i|OG#PsY-  
13.2 稀疏线性方程组的求解 >_LZD4v!<  
    三对角方程组的奇偶规约求解法 l]__!X  
    Gauss-Seidel迭代法的红黑着色并行算法 3Ay<2v
  
13.3 非线性方程的求根(略) ^Y+P(o$HM  
Ch14 快速傅立叶变换FFT v?qU/  
14.1 快速傅里叶变换(FFT) ,7w[r<7  
    离散傅里叶变换(DFT) <aGfQg|554  
    串行FFT递归算法及其计算原理 !p|d[  
    串行FFT蝶式计算及其蝶式计算流图 YgW 50)q^  
14.2 DFT直接并行算法 3YOYlb %j  
    SIMD-MT上的并行DFT算法(略) ?*2Uw{~}  
14.3 并行FFT算法 UU"'  
    SIMD-MC上的FFT算法(略) We*&\e+"T  
    SIMD-BF上的FFT算法及其时间分析 "3X~BdH&J  
Ch15 图论算法 Ij9ezNZT=  
15.1 图的并行搜索 7,&
M
6<~  
    p-深度优先搜索及其计算示例 ;7w4BJcq']  
    p-宽深优先搜索及其计算示例 ]B3\IT  
    p-宽度优先搜索及其计算示例 E|l qlS7  
15.2 图的传递闭包 y?@(%PTp  
    基于布尔矩阵乘积的算法原理
El: &  
    计算示例 hqVxvS"  
    SIMD-CC上的传递闭包算法 9s@$P7N5B  
15.3 图的连通分量 2u?k;"]V  
    基于传递闭包的算法 U>=& 2Z2?  
    基于顶点合并的算法 XpU%09K  
15.4 图的最短路径 oVYW'~OID  
    基于矩阵乘积的算法原理 |v31weD8  
    计算示例 N#zh$0!8bJ  
15.5 图的最小生成树 5T- N\)@  
    SIMD-EREW模型上的Prim算法 pZaOd;t  
    算法的时间分析 :#&Y  
Ch18 随机算法 +JrbC/&  
18.1 引言 n+9rx]W,  
    基本知识：随机算法的定义、分类、重复性定律 *N!>c&8  
    时间复杂性度量 * j]"I=D  
    设计方法 $=GnoS  
18.2 低度顶点部分独立集 %6eQ;Rp*  
    串行算法 %kSpMj|  
    随机并行算法及其正确性证明 $>=?'wr  
18.5 多项式恒等的验证 a15kFun  
    基本原理和方法 {]V+C=`  
    矩阵乘积的验证原理 PG*:3![2  
18.8 格点逼近问题(略) g6p:1;Evf  
18.9 SAT问题的异步随机并行算法(略) nkii0YB!  
Ch20 模型与下界 ,ctm;T1H+  
20.1不同的PRAM模型的相互模拟 ZxvBo4>tH  
    PRAM-EREW模拟PPRAM-CRCW (>a8h~Na  
    PRAM-CRCW之间的模拟 *p Q'w  
20.2下界 vE<z0 l  
    算法研究的两个方向：优化（上界）、可能性（下界） 5nSi2
9C  
    Gates的工作 |';oIYs|$  
    理想的PRAM模型与下界 F*rsi7#!pG  
    PRAM模型的下界 6Ud6F t6  
20.3 NP完全理论导引(略) QK0-jYG^  
20.4 P完全理论(略)