本资料由国科大学者叶笑春与王展精心编制，专为《并行处理》课程的期末复习设计。涵盖核心概念和关键知识点，助力学生深入理解和掌握并行计算原理及其应用。
### 国科大-叶笑春、王展-并行处理-期末复习资料
#### 重要知识点概览
本段落将详细解析给定的并行处理知识点，包括负载均衡的方法、Flynn分类法、多核通信方式、系统域点对点通信的基本元素、并行程序的通用模型、并行执行的主要形式、多线程的收益与代价、并行编程模型、局部性的概念、Cache Miss的原因及避免方法、降低通信开销的方法，以及影响应用可扩展性的因素。
### 负载均衡的方法
负载均衡是确保各处理单元工作量相等以最大化整体系统效率的重要手段。常见方法包括：
1. **任务开始前的负载均衡**：根据任务特点和处理能力预先分配工作。
2. **动态负载均衡**：在执行过程中调整各个处理单元的工作量，例如快速完成任务的核心可以接收更多新任务。
### Flynn分类法
Flynn分类法通过指令流和数据流的特点区分并行处理系统。四种类型包括：
1. **SISD（单指令流单数据流）**：典型的顺序处理器。
2. **SIMD（单指令流多数据流）**：适用于大量相似数据的计算，如GPU中的某些单元。
3. **MISD（多指令流单数据流）**：少见的应用于特定场景，例如信号处理系统。
4. **MIMD（多指令流多数据流）**：最通用架构，每个处理器独立执行不同指令。
### 多核通信方式
在多核环境中，核心之间的有效通信至关重要。主要方式有：
1. **共享地址空间**：所有核心可访问同一内存区域。
2. **消息传递**：通过发送消息进行通信，适用于分布式系统或多节点集群环境。
3. **数据并行**：将大规模数据集分割后分配给不同核心处理。
### 系统域点对点通信的基本元素
基本构成包括：
1. **节点**: 单个计算机或多处理器系统的单一处理器。
2. **网络接口**: 如高速网卡，例如万兆以太网卡或InfiniBand HCA。
3. **链路**：线缆和接插件，如光纤连接及其光模块。
4. **网络包**：由头部、载荷及尾部构成的传输基本单位。
### 并行程序通用模型
从上层应用角度考虑：
1. **任务并行**: 问题分解为子任务，在不同处理单元中执行，并通过显式通信协调。
2. **数据并行**: 数据集分割分配给多个核心，每个单元执行相同的操作。
### 处理器并行执行的主要形式
主要形式包括：
1. **超标量**：在同一周期内执行多条指令，利用硬件自动发现并行性。
2. **多核**：多个核心协同工作支持线程级的并行处理。
3. **SIMD**: 单个核心内的向量化计算。
### 多线程的收益与代价
- 收益：
- 更好地使用处理器资源
- 隐藏内存访问延迟
- 提高整体吞吐量
- 代价：
- 增加上下文切换开销
- 可能增加单一线程运行时间
- 对内存带宽要求更高
- 缓存空间有限导致频繁的内存访问
### 并行编程模型
1. **共享地址空间**: 易于实现但难以确保良好的性能。
2. **消息传递**：结构化良好，利于开发可扩展程序。
3. **数据并行**：强调对大规模数据集进行处理，并限制迭代间的通信量。
### 局部性的概念
局部性包括：
1. **时间局部性**: 短期内重复访问相同的数据
2. **空间局部性**: 访问相邻地址的数据
3. 缓存利用: 主要依赖于时间和空间的局部性来减少缓存缺失（Cache Miss）
### Cache Miss的原因及避免方法
- 首次访问：无法避免。
- 容量不足：增加缓存大小。
- 冲突：调整缓存关联或改变数据访问模式。
- 通信引起的Miss: 最优化通信设计。
### 降低通信开销的方法
1. **减少通信次数**：
2. **减少延迟**:
3. **减少竞争**:
4. **重叠计算与通讯**
### 影响应用可扩展性的因素
包括：
1. 应用本身的串行算法实现。
2. 关键路径优化：缩短关键任务的执行时间
3. 处理瓶颈: 使用更高效的通信机制或采用主从架构。
### 结合Roofline模型优化Stencil程序
针对3-D 7
5星
