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

《并行算法》课程总结与复习 3k5OYUk  
Ch1 并行算法基础 ($' rV!}  
1.1 并行计算机体系结构 HQK%Y2S  
    并行计算机的分类 ouK &H|'  
    SISD,SIMD,MISD,MIMD； EYd`qk3  
    SIMD,PVP,SMP,MPP,COW,DSM z)=D&\HX  
    并行计算机的互连方式 <g5Btwo%  
    静态：LA(LC),MC,TC,MT,HC,BC,SE rv1kIc5Za<  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) -7*,}xV  
1.2 并行计算模型 /d9I2~}B  
    PRAM模型：SIMD-SM， !v<r=u  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW <w(
UDZ  
    SIMD-IN模型：SIMD-DM a Umcs!@  
    异步APRAM模型：MIMD-SM 7m{
'V`F  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 [#$-kd ~  
    LogP模型：MIMD-DM，点到点通讯 *qj @y'1\  
1.3 并行算法的一般概念 !m^;Apuy  
    并行算法的定义 <33[ qt~  
    并行算法的表示 L
peQx\  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 $)vljM<<  
    并行算法的WT表示：Brent定理、WT最优 `QXO+'j4  
    加速比性能定律(略) :"g^y6i  
    并行算法的同步和通讯(略) mS6 #\'Qa  
Ch2 并行算法的基本设计技术 m,,-rC  
2.1 并行算法的三种基本设计方法 ! pR&&uG  
2.2 基本设计技术 ) &+j#:  
    平衡树方法：求最大值、计算前缀和 }|%dN*',  
    倍增技术：表序问题、求森林的根 xm b]L:4F  
    分治策略：FFT分治算法 Bab`wfUve  
    划分原理： _,"T;i  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) <w` R;  
    流水线技术：五点的DFT计算，Systolic算法 CO%7^}xSE,  
    加速级联(略) T=(/n=  
    破对称技术 cKdn3 2Y4  
Ch3 比较器网络上的排序和选择算法 'Xo if"  
3.1 Batcher归并和排序 CeSr~Ikg|  
    0-1原理的证明(略) m.pB]yq&  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) [^$nt  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) Fm_^7|  
    Batcher排序网络：原理、种类和复杂性 $~!%Px)  
3.2 (m, n)-选择网络 O`Er*-O  
    分组选择网络 H<#M)8  
    平衡分组选择网络及其改进 7n9&@D3:P  
Ch4 排序和选择的同步算法 '#!nK O2<  
4.1 一维线性阵列上的并行排序算法(略) r@ujE,D=k  
4.2 二维Mesh上的并行排序算法 2-728  
    ShearSort排序算法 DDQ}&`s  
    Thompson&Kung双调排序算法及其计算示例 Q@?8-  
4.3 Stone双调排序算法(略) 5. 5<.")  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 F M;NA{  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 g"ha1<y<  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 #%N v\g;  
Ch5 排序和选择的异步和分布式算法(略) :+NZW9_  
5.1 MIMD-CREW模型上的异步枚举排序算法 ?!^ow5"8  
5.2 MIMD-TC模型上的异步快排序算法 k>E^FB=  
5.3分布式k-选择算法 /4/'&tY  
Ch6 并行搜索 pMB!I9q  
6.1 单处理器上的搜索(略) -{`8Av5)E%  
6.2 SIMD共享存储模型上有序表的搜索：算法 .a2b&}/.d  
6.3 SIMD共享存储模型上随机序列的搜索：算法 <|Srbs+  
6.4 树连接的SIMD模型上随机序列的搜索：算法 5;'(^z-bL  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 01=nS?
 
Ch8 数据传输与选路 'yxN1JF  
8.1 引言 @~k4,dJ  
    信包传输性能参数 %"-bG'Yc  
    维序选路(X-Y选路、E-立方选路) %O
6r   
    选路模式及其传输时间公式 g)$/'RB  
8.2 单一信包一到一传输 "uCO?hv0  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) [wU e"{  
8.3 一到多播送 J^<Gi/:*^  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 `eZzYe
(N  
8.4 多到多播送 wcH,!;3z+  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 i>z_6Gax*[  
8.5 贪心算法(书8.2) 4Vtug>  
    二维阵列上的贪心算法 Q$+6f,m#W  
    蝶形网上的贪心算法 ^h\(j*/#X  
8.6 随机和确定的选路算法(书8.3)(略) :eIi^K z[  
Ch12矩阵运算 e"oTlB  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 /RVwhA+c  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 "C0?s7Y  
12.3 矩阵向量乘法 9|D*}OY >  
    带状划分的算法及其时间分析 I(<9e"1O  
    棋盘划分的算法及其时间分析 Su/8P[q_  
    Systolic算法(略) )ifjK6*  
12.4 矩阵乘法 W4;/;[/L  
    简单并行分块算法 IR2=dQS  
    Cannon算法及其计算示例 {FQ@eeU  
    Fox算法及其计算示例 @An}  
    DNS算法及其计算示例 |\zzOfaO  
    Systolic算法(略) :Kmn
wYm  
Ch13 数值计算 C@`rg ILc  
13.1 稠密线性方程组求解 2&"qNpPtE  
    SIMD-CREW的上三角方程组回代算法 3v@h&7<E  
    SIMD-CREW上的Gauss-Jordan算法 qk~m\U8r  
    MIMD-CREW上的Gauss-Seidel算法 VwudNjL  
13.2 稀疏线性方程组的求解 T;G<62`
.h  
    三对角方程组的奇偶规约求解法 vPz$+&{I  
    Gauss-Seidel迭代法的红黑着色并行算法 {E; bT|3z  
13.3 非线性方程的求根(略) ?7>"ZGDe>  
Ch14 快速傅立叶变换FFT mC0_rN^Aj  
14.1 快速傅里叶变换(FFT) t"zi'9$t  
    离散傅里叶变换(DFT) ZN Vrja*  
    串行FFT递归算法及其计算原理 dz?On\6 6  
    串行FFT蝶式计算及其蝶式计算流图 UX+vU@Co[  
14.2 DFT直接并行算法 c/F
gx/hr  
    SIMD-MT上的并行DFT算法(略) 'W,*mfB  
14.3 并行FFT算法 uu9IUqEq2  
    SIMD-MC上的FFT算法(略) d~AL4~}  
    SIMD-BF上的FFT算法及其时间分析 @DIEENiM  
Ch15 图论算法 42~.N=2  
15.1 图的并行搜索 wVqp')e  
    p-深度优先搜索及其计算示例 76bMy4re  
    p-宽深优先搜索及其计算示例 _p>F43%p  
    p-宽度优先搜索及其计算示例 n$`+03a  
15.2 图的传递闭包 m}u)C&2>  
    基于布尔矩阵乘积的算法原理 "={*0P  
    计算示例 IITUM)  
    SIMD-CC上的传递闭包算法 ?"*JV1 9  
15.3 图的连通分量 AT)b/y
cC  
    基于传递闭包的算法 aZ$5"  
    基于顶点合并的算法 iGSA$U P|  
15.4 图的最短路径 *L9v(Kc  
    基于矩阵乘积的算法原理 :_y!p  
    计算示例 ^D5Jqh)
 
15.5 图的最小生成树 }% f7O  
    SIMD-EREW模型上的Prim算法 q\}+]|nGs  
    算法的时间分析 H0#=oJr$)W  
Ch18 随机算法 ;1[Z&Uv8  
18.1 引言 ,,BP}f+l$  
    基本知识：随机算法的定义、分类、重复性定律 g9q}D-  
    时间复杂性度量 CvmIDRP
*  
    设计方法 SOq:!Qt
  
18.2 低度顶点部分独立集  *<W8j[?  
    串行算法 ;xe.0j0h  
    随机并行算法及其正确性证明 c\2rKqFD8  
18.5 多项式恒等的验证 PBnH#zm  
    基本原理和方法 m)} 01N4  
    矩阵乘积的验证原理 C<AW)|r_  
18.8 格点逼近问题(略) Bp_R"DS7A  
18.9 SAT问题的异步随机并行算法(略) r":anR( ;  
Ch20 模型与下界 >iae2W`
 
20.1不同的PRAM模型的相互模拟 Nwz?*~1  
    PRAM-EREW模拟PPRAM-CRCW ?/"|tuQMW  
    PRAM-CRCW之间的模拟 dgF%&*Il]O  
20.2下界 l@Vv%w9H  
    算法研究的两个方向：优化（上界）、可能性（下界） z,G_&5|f%  
    Gates的工作 Cl`i|cF\  
    理想的PRAM模型与下界 EM*I%|n@m  
    PRAM模型的下界 IGcq*mR=  
20.3 NP完全理论导引(略) ,JE_aje7  
20.4 P完全理论(略)