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

《并行算法》课程总结与复习 RCNqHYR  
Ch1 并行算法基础 |6\ ?"#  
1.1 并行计算机体系结构 UR-e'Z&]  
    并行计算机的分类 Uk ?V7 ?&  
    SISD,SIMD,MISD,MIMD； W5:S+  
    SIMD,PVP,SMP,MPP,COW,DSM -<&"geJA  
    并行计算机的互连方式 A@'):V8_%C  
    静态：LA(LC),MC,TC,MT,HC,BC,SE (B]Vw+/  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks)  wb4 4  
1.2 并行计算模型 I+O!<SB  
    PRAM模型：SIMD-SM， OAw/  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW }9P)<
[>  
    SIMD-IN模型：SIMD-DM |#5JI#,vX  
    异步APRAM模型：MIMD-SM >!? f6 {\|  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 ]RnX'yw^  
    LogP模型：MIMD-DM，点到点通讯 +}4vdi"  
1.3 并行算法的一般概念 f$V']dOj1q  
    并行算法的定义 o?{VGJH<v  
    并行算法的表示 drtQEc>qT  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 pJ_Z[}d)c  
    并行算法的WT表示：Brent定理、WT最优 =#%e'\)a  
    加速比性能定律(略) 'zT/x`V  
    并行算法的同步和通讯(略) !c
1 E  
Ch2 并行算法的基本设计技术 HEe0dqG  
2.1 并行算法的三种基本设计方法 SCxzT}#J  
2.2 基本设计技术 2b|vb}|t{  
    平衡树方法：求最大值、计算前缀和 ~sSB.g  
    倍增技术：表序问题、求森林的根 (:T~*7/"  
    分治策略：FFT分治算法 DU1,i&(  
    划分原理： k7y!!AV  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) j-{WPJa4\  
    流水线技术：五点的DFT计算，Systolic算法 PVEEKKJP]J  
    加速级联(略) -QS_bQG%  
    破对称技术 2?-}(F;Z  
Ch3 比较器网络上的排序和选择算法 hr6f
}2  
3.1 Batcher归并和排序 QX(:!b  
    0-1原理的证明(略) Pi*,&D>{7  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) O4$: xjs  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) 3U:0,-j"  
    Batcher排序网络：原理、种类和复杂性 @RaMO#  
3.2 (m, n)-选择网络 VCc 4nn#  
    分组选择网络 Q_uv.\*z_  
    平衡分组选择网络及其改进 PwDQ<   
Ch4 排序和选择的同步算法  b$gDFNa  
4.1 一维线性阵列上的并行排序算法(略) #),QWTl3  
4.2 二维Mesh上的并行排序算法 NU 6P  
    ShearSort排序算法 o-)E_X  
    Thompson&Kung双调排序算法及其计算示例 }){h Qt7  
4.3 Stone双调排序算法(略) $rjv4e}7  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 rq
a;MPl  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 }l [t0C t  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 o} %  
Ch5 排序和选择的异步和分布式算法(略) +
pjD{S~Y  
5.1 MIMD-CREW模型上的异步枚举排序算法 ?NHh=H\7u  
5.2 MIMD-TC模型上的异步快排序算法 zxsnrn;|  
5.3分布式k-选择算法 Bq$bxuhV  
Ch6 并行搜索 3cOXtDV YT  
6.1 单处理器上的搜索(略) .+M4Pi  
6.2 SIMD共享存储模型上有序表的搜索：算法 ZMx<:0
ai  
6.3 SIMD共享存储模型上随机序列的搜索：算法 4`*j F'N[  
6.4 树连接的SIMD模型上随机序列的搜索：算法 (nV/-#*  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例
XE>XzsnC  
Ch8 数据传输与选路 (oTx*GP>Y  
8.1 引言 #~ >0Dr  
    信包传输性能参数 i
-/'F  
    维序选路(X-Y选路、E-立方选路) WRo#ZVt9$  
    选路模式及其传输时间公式 I/'jRM  
8.2 单一信包一到一传输 4lz9z>J.V  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) F!N
x^M1  
8.3 一到多播送 {cG&l:-r  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 o!j? )0d  
8.4 多到多播送 UDxfS4yI  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 `[`eg<xj  
8.5 贪心算法(书8.2) ?N`W,  
    二维阵列上的贪心算法 Pw+ cpM8<  
    蝶形网上的贪心算法 3tgct <"  
8.6 随机和确定的选路算法(书8.3)(略) h], _1!0  
Ch12矩阵运算 "S6d^  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 <ZCjQkka>r  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 jg2>=}  
12.3 矩阵向量乘法 $e0sa=/  
    带状划分的算法及其时间分析 V}Oxz 04  
    棋盘划分的算法及其时间分析 zvSf
W# *  
    Systolic算法(略) t*n!kXa  
12.4 矩阵乘法 edbzg#wy  
    简单并行分块算法 QCMt4`%'u  
    Cannon算法及其计算示例 wl}Q|4 rZ  
    Fox算法及其计算示例 ]BX|G`CCc  
    DNS算法及其计算示例 l? 7D
0  
    Systolic算法(略) fF<~2MiKw  
Ch13 数值计算 ^|OxlfS  
13.1 稠密线性方程组求解 &Q 3!ty  
    SIMD-CREW的上三角方程组回代算法 CSIW|R@   
    SIMD-CREW上的Gauss-Jordan算法 n{=vP`V_  
    MIMD-CREW上的Gauss-Seidel算法 *<]ulR2  
13.2 稀疏线性方程组的求解 Ptn0;GC  
    三对角方程组的奇偶规约求解法  ig jr=e  
    Gauss-Seidel迭代法的红黑着色并行算法 05$C IS>!  
13.3 非线性方程的求根(略) ?>DN7je  
Ch14 快速傅立叶变换FFT _-^a8F>/19  
14.1 快速傅里叶变换(FFT) 8)/d8@  
    离散傅里叶变换(DFT) <U$x')W  
    串行FFT递归算法及其计算原理 "V}WV!w  
    串行FFT蝶式计算及其蝶式计算流图 'HzF/RKh  
14.2 DFT直接并行算法 V*}ft@GPD  
    SIMD-MT上的并行DFT算法(略) RGf&KV/  
14.3 并行FFT算法 ;M1#M:  
    SIMD-MC上的FFT算法(略) kq8.SvIb  
    SIMD-BF上的FFT算法及其时间分析 #Ipi3  
Ch15 图论算法 _h6SW2:z!E  
15.1 图的并行搜索 kc-=5l  
    p-深度优先搜索及其计算示例 C6Lc  
    p-宽深优先搜索及其计算示例 e];lDa#4-Y  
    p-宽度优先搜索及其计算示例 J;|a)Nw  
15.2 图的传递闭包 nm Y_)s  
    基于布尔矩阵乘积的算法原理 2RG6m=Y8y  
    计算示例 v
hIZkz!9  
    SIMD-CC上的传递闭包算法 WPI<SsLd  
15.3 图的连通分量 \2)D  
    基于传递闭包的算法 EMQGP<[  
    基于顶点合并的算法 hz:h>Hwy  
15.4 图的最短路径 =g
NPS0H  
    基于矩阵乘积的算法原理 o=J-Ju
 
    计算示例 Znr@-=xZO*  
15.5 图的最小生成树 `OFW^Esc  
    SIMD-EREW模型上的Prim算法 }D>#AFs6#  
    算法的时间分析 1r$*8|p  
Ch18 随机算法 o1`\*]A7J  
18.1 引言 {Y -~7@  
    基本知识：随机算法的定义、分类、重复性定律 i/j53towe  
    时间复杂性度量 Y<L35 ?  
    设计方法 qv& Bai[  
18.2 低度顶点部分独立集 G/*;h,NbNr  
    串行算法 H-vHcqFx3  
    随机并行算法及其正确性证明 jc!m; U t  
18.5 多项式恒等的验证 i.k7qclL`  
    基本原理和方法 m9 vX8 ;.  
    矩阵乘积的验证原理 c {/J.  
18.8 格点逼近问题(略) wA\5-C7j  
18.9 SAT问题的异步随机并行算法(略) ;z.L^V0  
Ch20 模型与下界 Aa=:AkrH  
20.1不同的PRAM模型的相互模拟 l+[:Cni  
    PRAM-EREW模拟PPRAM-CRCW w lH \w?  
    PRAM-CRCW之间的模拟 XeX"IhgS>E  
20.2下界 ^|H={pd'c0  
    算法研究的两个方向：优化（上界）、可能性（下界） u<Y#J,p`e  
    Gates的工作 l%T4:p4e  
    理想的PRAM模型与下界 _
bGkJ=  
    PRAM模型的下界 12a`,~  
20.3 NP完全理论导引(略) @^A
5{qQ\  
20.4 P完全理论(略)