并行计算

简介

类型

• 时间并行：并发

• 空间并行：并行

层次

• 位级并行：位

• 指令级并行：指令流水线

• 数据级并行：数据流

• 任务级并行：CPU并行执行多个任务

并行计算和分布式计算

• 并行计算共享内存

• 并行计算具有同构性，处理机类型相同

• 并行计算交互频繁，细粒度和低开销

• 并行计算节点结算结果相互影响；分布式分解后的小任务有独立性

并行操作系统

共享内存

• 单一OS映像

• 同意内存地址空间，不同内存模块的访问时间相同

分布式内存

• 每个节点有自己的本地内存，访问本地内存和全局内存的时间不同

• 集群/MPP：多台独立计算机通过网络互联，共同完成计算

并行计算机体系结构

并行计算机分类

Flynn分类法

• SISD 单指令单流数据流
• 传统冯诺依曼计算机

• SIMD
• 对多个数据进行相同操作

• MISD

• MIMD 多指令流多数据流
使用多个控制器来异步地控制多个处理器，从而实现空间上的并行性
• SMP、多核、集群

• 缩放比定律、摩尔定律的终结，并行计算是未来

按功能部件互连位置不同分类

• 处理器处
• 单指令流多数据流SIMD
• 控制单元的成本在多个数据通路分担，多个通路同步工作
• 并行编程模型的灵活性有限

• 存储系统处
• 多个CPU共享同一个映射到物理内存上的虚拟地址空间
• 共享存储处理器SMP
• 所有CPU都能平等地访问所有的内存模块和输入/输出设备，而且在操作系统看来这些CPU是可以互换的
• 低延迟，但要求适当的同步才能获得较高的并行效率

• I/O系统处
• 使用标准网络互联
• 集群
• 高性能计算集群
• 尽快完成大计算任务
• 节点通信频繁，节点耦合、紧耦合
• 高可用集群
• 容错、高可用
• 多个冗余节点
• 双机热备、一种是双机互备。这两种方式都是共享一个磁盘阵列
• 负载均衡集群
• 较高资源利用率
• 两台或多台服务器同时处理来自同一个应用的服务请求
• 同时具备高可用功能
• 多种模式实现服务的负载均衡
• 基于客户端的负载均衡
• 基于服务器的负载均衡
• 多用途集群
• 网络延迟大，价格低
• 使用专用网络互联
• 多计算机
• 性能强，价格高

互连网络

静态互连网络

• 一维线性阵列
• 只有左右临近节点相连
• n个节点n-1条边
• 节点度为2
• 网络直径为n-1
• 对刨度为1
• 首位相连成环

• 四近邻连接



• 网状结构
• (dx,dy) = (x2-x1,y2-y1) dx > 0, move down dx < 0, move up dy > 0, move right dy < 0, move left
• 环状结构
• If |dx|>X_dim/2 or |dy|>Y_dim/2, 向相反方向移动

• 树形结构
• 路径唯一、路由简单
• 上层节点负担重

• 超立方体

动态互连网络

并行计算机性能评价

基本参数

• 处理器数量、时钟频率、存储器容量/带宽

• 工作负载：求解问题的总计算量

• 串行分量：工作负载中必须串行执行的部分

• 串行分量占比：工作负载中串行分量所占比例，

• 并行分量：工作负载中可以并行执行的部分，

• 串行执行时间：使用个处理器串行处理所需时间。

• 并行执行时间：个处理器并行系统处理所需时间。

• 额外开销：包括并行处理开销和通信开销。
• 并行处理开销：任务分配、任务调度、结果汇总等涉及的开销。
• 通信开销：同步操作、通信操作等涉及的开销。

• 加速比S：P个处理器的并行系统执行程序时速度提升倍数—

• 处理器利用率（并行效率）

加速比定律

Amdahl阿姆达尔定律

• 不考虑额外开销

• 考虑额外开销

• 顺序瓶颈
• 串行分量占比f被称为程序的顺序瓶颈
• 随着并行系统中的处理器数量不断增大，并行系统所能达到的加速比的上限为1\/𝑓

Gustafson古斯塔夫森加速比定律

• 不以获得最短运行时间为目的，更看重计算精度

• 扩大系统规模，获得更高计算精度

• 通过增加问题规模，形成更大的工作负载

• 串行工作负载保持W_s不变，并行工作负载从W_p增大为〖p«W〗_p，问题处理时间保持不变。因此，Gustafson加速比也叫作固定时间加速比

• 充分大时，加速比与几乎成线性关系,不再是瓶颈

Sun&Ni孙-倪加速比定律

• 条件
• 所有节点的存储器集合能形成全局地址空间，即共享分布式存储空间。
• 所有可用的存储区都用于求解可扩展问题

• 系统规模增大到p时，并行系统的存储器容量增大为pM。

• G(p)：存储器容器量增大为pM时工作负载的增加量，则扩大后的工作负载为：𝑊=𝑓𝑊+(1−𝑓)𝐺(𝑝)𝑊

基准测试程序

• MIPS可用时钟频率和平均CPI(平均指令周期)计算得到。

并行程序设计模型

数据并行模型

消息传递模型