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

《并行算法》课程总结与复习 XecU&  
Ch1 并行算法基础 rB5+~ K@  
1.1 并行计算机体系结构 kc:2ID&
 
    并行计算机的分类 <4Cy U j  
    SISD,SIMD,MISD,MIMD； ,1e@Y~eZ  
    SIMD,PVP,SMP,MPP,COW,DSM 7PI|~Ifi  
    并行计算机的互连方式 px_%5^zRQ  
    静态：LA(LC),MC,TC,MT,HC,BC,SE J7rfHhz  
    动态：Bus, Crossbar Switcher, MIN(Multistage Interconnection Networks) SkA"MhX  
1.2 并行计算模型 @BXV>U2B{  
    PRAM模型：SIMD-SM， x68s$H  
又分CRCW(CPRAM,PPRAM,APRAM),CREW,EREW jl4rEzVu  
    SIMD-IN模型：SIMD-DM LIHf]+  
    异步APRAM模型：MIMD-SM $(%t^8{a~G  
    BSP模型：MIMD-DM，块内异步并行，块间显式同步 ZCVN+::Y  
    LogP模型：MIMD-DM，点到点通讯 1YMu\(  
1.3 并行算法的一般概念 bwh.ekf8  
    并行算法的定义 <$ Ar*<,6  
    并行算法的表示 \(bML#I  
    并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量 ?2b9N~  
    并行算法的WT表示：Brent定理、WT最优 3^zOG2  
    加速比性能定律(略) = 8%+$vX  
    并行算法的同步和通讯(略) RA+k/2]y!  
Ch2 并行算法的基本设计技术 ]={{$}8.  
2.1 并行算法的三种基本设计方法 Ie?C<(8Ul  
2.2 基本设计技术 ),)]gw71QW  
    平衡树方法：求最大值、计算前缀和 j7 D\O  
    倍增技术：表序问题、求森林的根 YvK8;<k@-?  
    分治策略：FFT分治算法 VscEd
t
kd  
    划分原理： gI^*O@Q4{b  
均匀划分(PSRS排序)、对数划分(并行归并排序)、方根划分(Valiant归并排序)、功能划分( (m,n)-选择 ) >2~q{e  
    流水线技术：五点的DFT计算，Systolic算法 j>Htaa  
    加速级联(略) ~$i36"  
    破对称技术 /%U+kW  
Ch3 比较器网络上的排序和选择算法 :_Y@,CpIEg  
3.1 Batcher归并和排序 PDo%ob\Ym  
    0-1原理的证明(略) o84!$2P+w  
    奇偶归并网络：计算流程和复杂性(比较器个数和延迟级数) T0Q)}%L  
    双调归并网络：计算流程和复杂性(比较器个数和延迟级数) |,Y(YSg.  
    Batcher排序网络：原理、种类和复杂性 ,xrXby|R"  
3.2 (m, n)-选择网络 Jn.WbS  
    分组选择网络 C_Y^
<  
    平衡分组选择网络及其改进 'kK}9VKl  
Ch4 排序和选择的同步算法 'k#^Z  
4.1 一维线性阵列上的并行排序算法(略) FMuM:%&J]  
4.2 二维Mesh上的并行排序算法 m-UI^M,@<  
    ShearSort排序算法 Os@ d&wm  
    Thompson&Kung双调排序算法及其计算示例 41WnKz9c  
4.3 Stone双调排序算法(略) *.AokY)_a  
4.4 Akl并行k-选择算法：计算模型、算法实现细节和时间分析 &'UYV>  
4.5 Valiant并行归并算法：计算模型、算法实现细节和时间分析 1j<=TWit  
4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度 J A ]s  
Ch5 排序和选择的异步和分布式算法(略) ]C-hl}iq  
5.1 MIMD-CREW模型上的异步枚举排序算法 ^PfFW  
5.2 MIMD-TC模型上的异步快排序算法 =usx' #rb  
5.3分布式k-选择算法 Pm6/sO  
Ch6 并行搜索 T&I*8 R~  
6.1 单处理器上的搜索(略) !q! =VC  
6.2 SIMD共享存储模型上有序表的搜索：算法 ._"U{ f2V  
6.3 SIMD共享存储模型上随机序列的搜索：算法 ?ZDXT2b~~  
6.4 树连接的SIMD模型上随机序列的搜索：算法 (t1:2WY@  
6.5 网孔连接的SIMD模型上随机序列的搜索：算法和计算示例  cpp0Y^  
Ch8 数据传输与选路 Sb+pB58&N  
8.1 引言 Y(ly0U}  
    信包传输性能参数 @!&\Z[",  
    维序选路(X-Y选路、E-立方选路) {n=)<w  
    选路模式及其传输时间公式 qC40/1-m8K  
8.2 单一信包一到一传输 I|,^a|\  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方) ' D+h_*H  
8.3 一到多播送 CeoK@y=o  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 xxgS!J  
8.4 多到多播送 G*ZHLLO4S\  
SF和CT传输模式的传输时间(一维环、带环绕的Mesh、超立方)及传输方法 kN>%y&cK  
8.5 贪心算法(书8.2) wj9CL1Gx  
    二维阵列上的贪心算法 v{^_3 ]  
    蝶形网上的贪心算法 f@T/^|`mh  
8.6 随机和确定的选路算法(书8.3)(略) *r$Yv&c,  
Ch12矩阵运算 e'mm42  
12.1 矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分 | Uf6k`  
12.2 矩阵转置：网孔和超立方连接的算法及其时间分析 _9wX8fh3D  
12.3 矩阵向量乘法 $&Ng*oX
 
    带状划分的算法及其时间分析 ttuQ,SD  
    棋盘划分的算法及其时间分析 3:X3n\z  
    Systolic算法(略) 3:7J@>  
12.4 矩阵乘法 o {Sc  
    简单并行分块算法 U0q{8 " Pl  
    Cannon算法及其计算示例 O&Q_vY  
    Fox算法及其计算示例 R<@s]xX_  
    DNS算法及其计算示例 j|TcmZGO  
    Systolic算法(略) YwyP+Sr\  
Ch13 数值计算 l7]:b8  
13.1 稠密线性方程组求解 xV[X#.3  
    SIMD-CREW的上三角方程组回代算法 RiqYC3Ka  
    SIMD-CREW上的Gauss-Jordan算法 NypM+y  
    MIMD-CREW上的Gauss-Seidel算法 m.e+S,i  
13.2 稀疏线性方程组的求解 0B#9CxU%  
    三对角方程组的奇偶规约求解法 nfET;:{  
    Gauss-Seidel迭代法的红黑着色并行算法 DW&%"$2  
13.3 非线性方程的求根(略) F
]DRT6)  
Ch14 快速傅立叶变换FFT b<>GF-`w  
14.1 快速傅里叶变换(FFT) 'g.9 goQ  
    离散傅里叶变换(DFT) m/RX~,T*v&  
    串行FFT递归算法及其计算原理 Qn'Do4Le  
    串行FFT蝶式计算及其蝶式计算流图 0YK`wuZGS  
14.2 DFT直接并行算法 ZDuP|" ^  
    SIMD-MT上的并行DFT算法(略) jA_wOR7$  
14.3 并行FFT算法 m}&cX
Y  
    SIMD-MC上的FFT算法(略) s\i:;`l:=5  
    SIMD-BF上的FFT算法及其时间分析 |^9+c2  
Ch15 图论算法 7Mq4$|qhD  
15.1 图的并行搜索 zmd,uhNc:  
    p-深度优先搜索及其计算示例 /{@^
h#4M1  
    p-宽深优先搜索及其计算示例 4g<F."  
    p-宽度优先搜索及其计算示例 @a-u_|3q
 
15.2 图的传递闭包 -5;Kyio  
    基于布尔矩阵乘积的算法原理 QcQ
QQM  
    计算示例 7{F(NJUO1  
    SIMD-CC上的传递闭包算法 z\64Qpfm  
15.3 图的连通分量 V6l~Aj}/  
    基于传递闭包的算法 vC$Q4>m  
    基于顶点合并的算法 fXfBDB  
15.4 图的最短路径 >d#oJ?goX  
    基于矩阵乘积的算法原理 }xhat,9  
    计算示例 O`Ht|@[6  
15.5 图的最小生成树 OS|uZ<"Rq3  
    SIMD-EREW模型上的Prim算法 5A|4  
    算法的时间分析 r*$$82 s  
Ch18 随机算法 55lL aus  
18.1 引言 Qa*?iD  
    基本知识：随机算法的定义、分类、重复性定律 ! C}t)R]^  
    时间复杂性度量 2hB';Dv  
    设计方法 !
%w#h0(b  
18.2 低度顶点部分独立集 3Ee8_(E\  
    串行算法 \=n0@1Q=>  
    随机并行算法及其正确性证明 *Nfn6lVB  
18.5 多项式恒等的验证 +a'QHtg  
    基本原理和方法 agQ5%t#  
    矩阵乘积的验证原理 *7`N^e  
18.8 格点逼近问题(略) FN$hEc!  
18.9 SAT问题的异步随机并行算法(略) ,.# SEv5  
Ch20 模型与下界 w8~J5XS  
20.1不同的PRAM模型的相互模拟 F[aow$",+}  
    PRAM-EREW模拟PPRAM-CRCW 8mjP 2  
    PRAM-CRCW之间的模拟 G5^gwG+  
20.2下界 7Pt*V@DHS  
    算法研究的两个方向：优化（上界）、可能性（下界） #xWC(*Ggp  
    Gates的工作 *q5'~)W<  
    理想的PRAM模型与下界 jgiP2k[Xom  
    PRAM模型的下界 9JF*xXd>Q  
20.3 NP完全理论导引(略) )B d`N^k+  
20.4 P完全理论(略)