### 国科大-叶笑春、王展-并行处理-期末复习资料
#### 重要知识点概览
本篇文章将根据题目要求,详细解析给定的并行处理知识点,主要包括负载均衡的方法、Flynn分类法、多核通信方式、系统域点对点通信的基本元素、并行程序的通用模型、并行执行的主要形式、多线程的收益与代价、并行编程模型、局部性的概念、Cache Miss的原因及避免方法、降低通信开销的方法、以及影响应用可扩展性的因素。
### 负载均衡的方法
**负载均衡**是并行处理中的一个重要概念,目的是确保各处理单元的工作量大致相等,从而最大化整体系统的效率。常见的两种方法是:
1. **任务开始前的负载均衡**:在任务开始之前,根据任务的特点和处理单元的能力预先分配工作量,使得每个处理单元的工作量尽可能均衡。
2. **任务执行过程中的动态负载均衡**:随着任务的执行,动态调整各个处理单元的工作量,以适应实际情况的变化,比如某个处理单元完成得较快,则可以分配更多任务给它。
### Flynn分类法
**Flynn分类法**是一种用于区分并行处理系统的分类方法,主要依据指令流和数据流的特性来划分,包括以下四种类型:
1. **单指令流单数据流结构(SISD)**:典型的顺序处理计算机,如传统的CPU。
2. **单指令流多数据流结构(SIMD)**:适用于处理大量相似数据的任务,如图形处理器(GPU)中的某些计算单元。
3. **多指令流单数据流结构(MISD)**:较少见,主要用于某些特殊应用场景,如信号处理。
4. **多指令流多数据流结构(MIMD)**:最通用的并行处理架构,每个处理单元可以独立执行不同的指令流。
### 多核通信方式
在多核处理器环境中,不同核心之间的通信至关重要,主要有以下三种方式:
1. **共享地址空间**:所有核心都可以访问相同的内存空间,通信简单直接,但需要注意同步和一致性问题。
2. **消息传递**:通过发送消息的方式进行通信,适用于分布式系统或多节点集群环境。
3. **数据并行**:针对大规模数据集的处理,将数据分割后分配给不同的核心进行并行处理。
### 系统域点对点通信的基本元素
系统域内的点对点通信是并行计算中常见的一种通信方式,其基本构成包括:
1. **节点**:可以是集群中的单个计算机或者多处理器系统中的单一处理器。
2. **网络接口**:如高速网络接口卡(NIC),例如万兆以太网卡或InfiniBand HCA(主机通道适配器)。
3. **链路**:包括线缆和接插件,例如光纤连接和相应的光模块。
4. **网络包**:由包头、载荷、包尾三部分组成,是网络传输的基本单位。
### 从上层应用出发的并行程序通用模型
1. **任务并行**:问题被分解为多个子任务,这些子任务可以在不同的处理单元上并行执行,子任务之间通过显式通信来协调。
2. **数据并行**:对于包含大量数据的问题,数据集被分割并分配给不同的处理单元进行并行处理,每个单元执行相同的操作。
### 代处理器并行执行的主要形式
1. **超标量**:在同一时钟周期内执行多条指令,利用指令级并行(ILP),由硬件自动发现并行性。
2. **多核**:多个核心协同工作,支持线程级并行性,软件负责调度线程到不同的核心上。
3. **SIMD**:在单个核心内,通过多个ALU同时执行同一条指令的不同实例,实现数据级并行。
### 多线程的收益与代价
**收益**:
- 更好地利用处理器资源。
- 隐藏内存访问延迟。
- 提高并行应用的整体吞吐量。
**代价**:
- 需要额外的线程上下文。
- 可能增加单一线程的运行时间。
- 对内存带宽的要求更高。
- Cache空间受限可能导致频繁访问内存。
### 并行编程模型
1. **共享地址空间**:易于实现但难以确保良好的性能。
2. **消息传递**:结构化良好,有利于实现可扩展的并行程序。
3. **数据并行**:强调数据集的并行处理,限制迭代间的通信量。
### 局部性的概念
1. **时间局部性**:短期内重复访问相同数据。
2. **空间局部性**:访问附近地址的数据。
3. **Cache利用**:主要利用时间局部性和空间局部性来减少Cache Miss。
### Cache Miss的原因及避免方法
- **首次访问**:无法避免。
- **缓存容量不足**:增加缓存大小。
- **冲突**:调整缓存关联性或改变数据访问模式。
- **通信引起的Miss**:优化通信设计。
### 降低通信开销的方法
1. **减少通信次数**。
2. **减少通信延迟**。
3. **减少通信竞争**。
4. **增加通信与计算的重叠**。
### 影响应用可扩展性的因素
1. **应用本身的串行算法实现**。
2. **关键路径**:优化方法是缩短关键路径上的任务。
3. **处理瓶颈**:使用更高效的通信机制或采用主从计算架构。
### 结合Roofline模型优化Stencil程序
针对3-D 7点Jacobi Stencil算法,我们可以考虑以下几点优化策略:
1. **减少通信开销**:尽量减少数据交换的需求。
2. **提高计算密集度**:增加每个计算单元的数据处理量。
3. **优化数据布局**:改进数据的存储方式以提高缓存利用率。
4. **利用SIMD指令**:利用向量化指令加速数据处理。
通过以上策略,可以有效提升并行程序的性能和可扩展性。
1