什么是并行计算
Parallel computing：the use of two or more processors (computers), usually within a single system, working simultaneously to solve a single problem.
并行计算：使用两个或两个以上的处理器（计算机），通常在一个系统内，同时工作，以解决单个问题。
Distributed computing：any computing that involves multiple computers remote from each other that each have a role in a computation problem or information processing.
分布式计算：任何涉及多个计算机彼此远程的计算，每个计算机在计算问题或信息处理中都发挥作用。
什么是并行计算机
并行计算机就是一个支持并行程序的多处理器的计算机系统
两类并行计算机：
- 多机：用多台计算机和互连网络构建起来的并行计算机（通过消息）
- 集中多处理器（对称多处理器或SMP）：一个所有CPU共享一个全局内存的更加高度集中的系统（通过全局内存通信和同步）
并行系统和分布式系统的比较
| 并行系统 | 分布式系统 | |
|---|---|---|
| 内存 | 紧密耦合共享内存、UMA、NUMA、分布式内存、消息传递 | 分布式内存、消息传递、RPC、和/或用于分布式共享内存 |
| 控制 | 全局时钟控制、SIMD、MIMD | 没有全局时钟控制、需要同步算法 |
| 进程互连 | 按Tbps组织、总线、网格、树、树网、超立方体网络 | 按Gbps组织、以太网（总线）、令牌和SCI、以太网（交换网络） |
| 粒度 | 精细 | 粗 |
| 可靠性 | 假定 | 未假定 |
| 主要关注 | 性能（时间和规模）、科学计算 | 性能（成本和可扩展性）、可靠性/可用性、信息/资源共享 |
为什么并行计算
科技趋势
微处理器计算能力不断提升，摩尔定律：每1.5年每个芯片上晶体管数量翻倍
但是有诸多限制：
- 功率密度限制，由于“立方效应”，并不是越多的晶体管串行处理器的能力就提升越多
- 系统架构更改
- 芯片收益率限制
应用程序推动
- 传统实验有很多局限性，利用计算机进行仿真可以克服这些缺点
- 科学数据集呈指数增长
- 一些特别具有挑战性的计算
并行计算的问题
硬件问题
- 流水线，ILP……
- 缓存一致性
- 连接问题：单个共享总线与网络
- UMA、NUMA……
程序模型问题
- 数据共享——单个地址空间与多个地址空间
- 过程协调——使用锁、消息、其他方法同步
- 分布式与集中式内存
- 容错性/可靠性
性能问题
- 指标
- 型号
- 评估并行算法方法
其他问题
- 并行计算机语言
- 并行编程工具
- 便携式并行程序
- 并行计算机的自动编程
- 并行计算机哲学教育
怎样写并行计算程序
以n个数的求和为例，我们有p个核，p<<n
方法一
每个核求n/p个数的和，最后把结果发给0号核由其求总和
改进
让大家一起完成汇总的工作，0号核汇总0号和1号、2号核汇总2号和3号、等等，循环，直到都汇总给0号核
分析
方法一中，主核心需要完成7次接收和加法；
改进后，主核心只需要完成3次接收和加法
编写并行程序的几个步骤
任务并行化
划分各种任务，解决核心问题
数据并行化
将用于解决核心问题的数据进行分区，每个核心都对数据的一部分执行类似的操作
核之间需要协调工作
- 通信
- 负载平衡
- 同步
小思考
对于n个数求和的并行代码中，如下图，怎么设计my_first_i和my_last_i呢？（假设n可以被p整除）
参考：为了均分，我们肯定是将任务等分成p份，每份计算数的数量n/p，我们假设变量id表示进程（核）id号，范围是0-（p-1），那么my_first_i=id*(n/p)，my_last_i=(id+1)*(n/p)-1。这样分完以后i的范围是0-（n-1）。