《并行算法》课程总结与复习 2020.05.28
题型
填空
简答 4 题*5 分
答题:4-5 题,设计并行算法,分析复杂度,Chap8 路由传输时间计算,写过程
Chap12 矩阵计算
Chap13 Gauss-Seidel 迭代法的红黑着色并行算法
Chap14 串行 FFT 蝶式递归计算及其蝶式计算流图,老师上课补充的
SIMD-BF 上的 FFT 算法及其时间分析:01 序列
Chap15 p 深度优先等算法生成树
连通矩阵
Chap18 低度顶点部分独立集用到了破对称技术
补充 GPU:只考概念,算法不考
Ch1 绪论
1.1 并行计算机体系结构
并行计算机的分类
SISD,SIMD,MISD,MIMD;
SIMD,PVP,SMP,MPP,COW,DSM
并行计算机的互连方式
静态:LA(LC),MC,TC,MT,HC,BC,SE
动态:Bus, Crossbar Switcher, MIN(Multistage Interconnection
Networks)
1.2 并行计算模型
PRAM 模型:SIMD-SM,
又分 CRCW(CPRAM,PPRAM,APRAM),CREW,EREW
SIMD-IN 模型:SIMD-DM
异步 APRAM 模型:MIMD-SM,显式同步:SMP,DSM。CMP。
BSP 模型:MIMD-DM,块内异步并行,块间显式同步:Cluster
LogP 模型:MIMD-DM,点到点通讯(隐式同步)
1.3 并行算法的基础知识和性能分析
并行算法的定义
并行算法的表示:par-do,forall
并行算法的复杂度:
运行时间 t、处理器数目 p、成本 c=t*p、成本最优 c=串行最坏 t
加速比 s=ts/tp、并行效率 E=s/p
工作量 W:并行算法所执行的总操作步数。工作量最优:W=等于串行算
法工作量
c 最优、W 最优:能耗省,时间快
并行算法的 WT 表示:Brent 定理
评论0