考点

课堂内容

1. 主体,MPI,扩展性好
2. 并行算法的各方面
   1. 简单划分分治同步流水线负载均匀...
3. 几种典型应用
4. 目的:知道经典用法,在遇到大规模问题时知道如何处理
5. 需要从数学角度理解运行原理
6. 伪代码
7. 绝大部分例题都可能会考

题型

1. 填空
2. 单项选择
3. 判断
4. 大题
5. 题量不少

题型涉及

1. 前两章有些东西需要记忆
   1. 并行计算的基本条件
   2. 如何并行
   3. 最重要的并行计算机类型
      1. 比如阵列处理机,有矢量,标量两种数据类型
      2. 比如共享存储的多处理机,以及其瓶颈
      3. 比如并行计算加速比
      4. MPI的消息信封组成,信纸组成
      5. 网络性
      6. SMP
      7. 指令流/数据流划分依据以及其主流机型
2. 用p个CPU,分治,桶排序,若n>p,求复杂度
3. 负载均衡,线性分散,集中负载均衡的原则和问题
4. Amdal's Law
5. 并行的奇偶归并排序,若有n个处理器,则复杂度是?
6. 主流并行编程环境及类型,消息传递,数据并行,共享内存...
7. MPI不同的数据交互方式,通用常见例子
   1. 阻塞/非阻塞通讯
8. Scatter,Gather等群集通信方式,及其复杂度,对于接收方,Scatter是常数的,Gather线性
9. 用n^2个处理器对两个n*n矩阵做乘法运算
10. 用n个处理器对上三角求解.
11. 一个非阻塞的通讯+test不等于阻塞型通讯.(还需要wait)
12. openMP不是基于消息传递,而是基于共享内存.
13. 基本的机型及其特点
14. 流水线
    1. 有P个进程构成的流水线完成M个任务需要多少流水线周期,证明当流水线工作周期延长后工作效率接近于一个周期
15. 全局性同步
    1. Barrier
    2. 蝶形栅栏,工作原理,复杂度(对数)
16. 线性结构的负载均衡
    1. 一种折中
    2. 工作原理,伪代码,工作流程
17. 流水线方式做并行插入排序
    1. 当n>p时,阐述工作机制复杂度
18. 并行的快速归并等排序方法的实现复杂度.