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

《并行算法》课程总结与复习  Jiylrf`o  
Ch1 并行算法基础 &-Er n/[  
1.1 并行计算机体系结构 A_U0HVx_  
    并行计算机的分类 48rYs}  
    SISD,SIMD,MISD,MIMD； jt?%03iuk  
    SIMD,PVP,SMP,MPP,COW,DSM 3
-%~{(T/  
    并行计算机的互连方式 z4:09!o_  
    静态：LA(LC),MC,TC,MT,HC,BC,SE W?Abx  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) 8^i,M^f^{  
1.2 并行计算模型 `&7
?+s  
    PRAM模型：SIMD-SM， d0E5;3tQ  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW 0LuY"(LR  
    SIMD-IN模型：SIMD-DM >m{-&1Tx  
    异步APRAM模型：MIMD-SM Z9bPj8d  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 ,{t!->K  
    LogP模型：MIMD-DM，点到点通讯 W7>_nK+g?  
1.3 并行算法的一般概念 -bQvJ`iF  
    并行算法的定义 >pHvBFa3G  
    并行算法的表示 c3-bn #  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 2mG?ve%m)  
    并行算法的WT表示：Brent定理、WT最优 T8 /'`s  
    加速比性能定律(略) C,.{y`s'  
    并行算法的同步和通讯(略) Ut@)<N  
Ch2 并行算法的基本设计技术 ]TN}`]  
2.1 并行算法的三种基本设计方法 -ZJ:<  
2.2 基本设计技术 izA3INT  
    平衡树方法：求最大值、计算前缀和 kp"cHJNx  
    倍增技术：表序问题、求森林的根 AP@d2{"m}  
    分治策略：FFT分治算法 '-{jn+,
 
    划分原理： vi|ASA{V  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) _bsfM;u.%  
    流水线技术：五点的DFT计算，Systolic算法 VtFh1FDI\  
    加速级联(略) )I_I?e  
    破对称技术 @,.H)\a4  
Ch3 比较器网络上的排序和选择算法 A+&Va\|x  
3.1 Batcher归并和排序 nK$m:=  
    0-1原理的证明(略) CPG %*E*  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) E u  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) i"@?eq#h  
    Batcher排序网络：原理、种类和复杂性 cj)~7 WF  
3.2 (m, n)-选择网络 iV=#'yY  
    分组选择网络 X:5*LB\/v  
    平衡分组选择网络及其改进 lQjq6Fl2  
Ch4 排序和选择的同步算法 IA'AA|v  
4.1 一维线性阵列上的并行排序算法(略) usip>y  
4.2 二维Mesh上的并行排序算法 s+11) ~  
    ShearSort排序算法 ,58[WZ
G  
    Thompson&Kung双调排序算法及其计算示例 A{vG@Pwc:  
4.3 Stone双调排序算法(略) K||85l?<  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 FtXEudk  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 2},}R'aR  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 O%I'  
Ch5 排序和选择的异步和分布式算法(略) vL7}0n>tz  
5.1 MIMD-CREW模型上的异步枚举排序算法 6pse@x?  
5.2 MIMD-TC模型上的异步快排序算法 -eya$C  
5.3分布式k-选择算法 {+MMqJCa  
Ch6 并行搜索 y? g7sLDc  
6.1 单处理器上的搜索(略) d=pq+  
6.2 SIMD共享存储模型上有序表的搜索：算法 C~B ^sG@;  
6.3 SIMD共享存储模型上随机序列的搜索：算法 dxA=gL2  
6.4 树连接的SIMD模型上随机序列的搜索：算法 =uH`EkY:  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例 S=Zjdbd  
Ch8 数据传输与选路 T-MLW=Vu  
8.1 引言 -4;u|0_  
    信包传输性能参数 *KMCU m  
    维序选路(X-Y选路、E-立方选路)  `@p*1  
    选路模式及其传输时间公式 E5rNC/Ul$$  
8.2 单一信包一到一传输 h*Ej}_  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) )wC>Hq[mhW  
8.3 一到多播送 3k=q>~&@  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 h)w<{/p(  
8.4 多到多播送  QS!b]a3  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 0-@waK  
8.5 贪心算法(书8.2) cNHNh[ C  
    二维阵列上的贪心算法 ?#W>^Z a=  
    蝶形网上的贪心算法 e='3gzz  
8.6 随机和确定的选路算法(书8.3)(略) :ZUy(8%Wl  
Ch12矩阵运算 2o
NlQiE_  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 EV9m\'=j  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 6ik6JL$AI  
12.3 矩阵向量乘法 !nu#r$K(  
    带状划分的算法及其时间分析 sh0O~%]g  
    棋盘划分的算法及其时间分析 CxO)d7c  
    Systolic算法(略) sg3%n0Ms.W  
12.4 矩阵乘法 fUa`YryQ  
    简单并行分块算法 i
oZ2J"s  
    Cannon算法及其计算示例 0-=QQOART\  
    Fox算法及其计算示例 f1JvP\I0Q  
    DNS算法及其计算示例 VRD2e ,K  
    Systolic算法(略) bO-8<IjC_3  
Ch13 数值计算 ?g9Ce eH*  
13.1 稠密线性方程组求解 BV<LIrAS  
    SIMD-CREW的上三角方程组回代算法 m'%F,c)  
    SIMD-CREW上的Gauss-Jordan算法 hj-M #a  
    MIMD-CREW上的Gauss-Seidel算法 0O[q6!&]  
13.2 稀疏线性方程组的求解 O^LzS&I*  
    三对角方程组的奇偶规约求解法 1y>P<[  
    Gauss-Seidel迭代法的红黑着色并行算法 6MZfoR  
13.3 非线性方程的求根(略) Qg3 -%i/@  
Ch14 快速傅立叶变换FFT :V`q;g  
14.1 快速傅里叶变换(FFT) _c`Gxt%  
    离散傅里叶变换(DFT) Q7i^VN  
    串行FFT递归算法及其计算原理 rGx1>xd(k  
    串行FFT蝶式计算及其蝶式计算流图 #U'n=@U@(  
14.2 DFT直接并行算法 GAQVeL1  
    SIMD-MT上的并行DFT算法(略) {<&x9<f9  
14.3 并行FFT算法 $lUZm\R|k  
    SIMD-MC上的FFT算法(略) +i{&"o4}  
    SIMD-BF上的FFT算法及其时间分析 nJrV  
Ch15 图论算法 QRx'BY$5  
15.1 图的并行搜索 }&ZO q'B  
    p-深度优先搜索及其计算示例 *pj&^W?  
    p-宽深优先搜索及其计算示例 7(ZI]<  
    p-宽度优先搜索及其计算示例 ]l`?"X|^  
15.2 图的传递闭包 }[?
X%=  
    基于布尔矩阵乘积的算法原理 ASPfzW2  
    计算示例 ig3uY
#  
    SIMD-CC上的传递闭包算法 _epi[zf @  
15.3 图的连通分量 ; *r5 d+]  
    基于传递闭包的算法 ,}F{V>dhn  
    基于顶点合并的算法 HtPasFrJ  
15.4 图的最短路径 DCFYpkR%  
    基于矩阵乘积的算法原理 NkA|T1w7  
    计算示例 }D{y u+)  
15.5 图的最小生成树 dKi+~m'w  
    SIMD-EREW模型上的Prim算法 02SFFqm  
    算法的时间分析 BPwFcT)i!(  
Ch18 随机算法 !Zlvz%X  
18.1 引言 >@`D@_v  
    基本知识：随机算法的定义、分类、重复性定律 q>?uB4>^  
    时间复杂性度量 g;D [XBp  
    设计方法 ku&IVr%  
18.2 低度顶点部分独立集 H<Ed"-n$I<  
    串行算法 /2tgxm$}  
    随机并行算法及其正确性证明 Vd1.g{yPV  
18.5 多项式恒等的验证 DgGGrV`  
    基本原理和方法 c>,|[zP{  
    矩阵乘积的验证原理 $&OoxC  
18.8 格点逼近问题(略) j:0(=H!#  
18.9 SAT问题的异步随机并行算法(略) ]9pK^<  
Ch20 模型与下界 Mnn\y Tblp  
20.1不同的PRAM模型的相互模拟 ^0Cr-  
    PRAM-EREW模拟PPRAM-CRCW c!d>6:
\  
    PRAM-CRCW之间的模拟 NnRR"'   
20.2下界 h%|Jkx!v-t  
    算法研究的两个方向：优化（上界）、可能性（下界） *VmJydd  
    Gates的工作 _e E(P1  
    理想的PRAM模型与下界 *F42GiBZR  
    PRAM模型的下界 k z"F4?,  
20.3 NP完全理论导引(略) !vH7vq  
20.4 P完全理论(略)