并行计算讲义

燕山大学课程讲义燕山大学课程讲义 并行计算导论并行计算导论 授课人 郭栋梁授课人 郭栋梁 学时 学时 32 学时学时 其中实验课 其中实验课 8 学时学时 三级项目 三级项目 16 学学 时时 第第 1 章章 引言引言 1 1 概述概述 单处理器计算机即将成为过时的概念 我们需要考虑如下因素来着手改进提高计算机 的性能 1 单纯依靠单处理器很难提升现有计算机的性能 即使有一个性能十分强大的单处理 器 其功耗也让人无法接受 想要提升计算机的性能 更加可行的方法是同时使用 多个简单处理器 它所能达到的性能可能是现有单处理器计算机性能的几千倍 2 观察结果显示 除非使用并行处理技术 一个程序在一台型号更新的单处理器计算 机上的运行速度 可能比在旧的计算机上的运行速度更慢 能依照给定算法检测出 程序中的并行结构的编程工具还有待开发 此算法需要能够检测出变 ja 之间的依 赖关系是否规则 而且不管这些依赖是否规则 此算法都能在保证程序正确性的前 提下 通过将程序中的一些子任务并行化来加速程序的执行 3 提升未来的计算机性能的关键就在于并行程序的开发 这涉及各个层面的工作 算 法 程序开发 操作系统 编译器及硬件设备 4 并行计算除了要考虑到参与并行计算的处理器的数量 还应该考虑处理器与处理器 处理器与内存之间的通信 最终计算性能的提升既依赖于算法能够提升的空间 更 依赖于处理器执行算法的效率 而通信性能的提升则依赖于处理器对数据的供应和 提取的速度 5 内存系统的速度始终比处理器慢 而且由于一次只能进行单个字的读写操作 内存 系统的带宽也有限制 6 内存系统的速度始终比处理器慢 而且由于一次只能进行单个字的读写操作 内存 系统的带宽也有限制 本书内容主要涉及并行算法与为了实现这些算法而设计的硬件结构 硬件和软件是相 互影响的 任何软件的最终运行环境是由处理器组成的底层硬件设备和相应的操作系统组 成 我们在本章开始的部分会介绍一些概念 之后再来讨论为了实现这些概念有哪些方法和 限制 1 2 自动并行编程自动并行编程 对于算法在软件中的实现过程我们都很熟悉 在编程并不需要了解目标计算机系统的 具体细节 因为编译器会处理这些细节 但是在编程和调试时依旧沿用着在单一央处理器 CPU 上顺序处理的模式 从另一方面讲 为了实现并行算法 硬件和软件之间的相互联系需 要比我们想象的更加密切 图 1 1 展示了基于软件和硬件 利用并行计算机来运行程序的 主要步骤和层次 从最顶层开始 第 5 层是指应用层 在这一层里描述的是需要并行计算 平台实现的应用和问题 对应所需的输入和输出的格式也在这层进行定义 某些输人和输 出 I O 接口的描述还需要考虑数据存储的位置和时间相关性 这一层的结果会被更低一层 采纳以便指导并行算法的开发工作 第 4 层是算法开发层 这里需要考虑到应用在问题中的实现 需要应用实现的计算内 容决定了算法的具体任务和任务之间的相互依赖关系 interdependence 在这一阶段 算 法的并行性并不一定会显现出来 因为在探索算法子任务执行的时候仍然在运用传统的线 性思考 在这一阶段 也不需要考虑子任务的时间调度和处理器分配的问题 可能在现阶 段就将这些问题解决的做法看起来很诱人 但是这样做会适得其反 因为这会掩盖程序中 潜在的并行性 该层的结果是一个依赖图 或是一个有向图 或者是一个概括了任务之间 依赖关系的临界矩阵 第 3 层是并行化层 在这一层将试着释放算法中潜在的并行性 这一层接收了第 4 层 对算法的描述并且给出了基于软件实现的线程时间调度和处理器分配 另一种选择是在这 一层进行基于超大规模集成电路的硬件实现的任务调度和处理器分配 本书内容主要集中 在这一层上 在图 1 1 用灰色方形显示 第 2 层是代码层 在本层中并行算法用高级语言表示为代码 使用何种语言取决于目 标并行计算在何种平台执行 图 1 1 中右侧的分支表示算法在通用并行计算平台上的实现 过程 这一做法即是我们所说的 并行编程 并行计算机程序由所谓的 并发平台 执行 此种平台帮助编程人员管理线程 处理处理器级别的任务执行时间调度 并发平台包括 Cilk OpenMP CUDA compute unified device architecture 统一计算设备架构 图 1 1 中左侧的分支表示并行算法在定制的硬件设备上的实现 例如脉动阵列计算机 编程人员使用硬件描述语言 HDL 例如 Verilog 或者超高速集成电路硬件描述语言 VHDL 第 1 层的目标是算法的实现 或是在并行计算机平台的应用 实现的途径可以是在并行 计算平台上使用多线程 也可以是在特定用途集成电路 ASIC 上或者现场可编程门阵列 FPGA 上使用特定的应用并行处理系统 那么并行计算机自动编程又是什么意思呢 现在我们已经可以进行线性计算机自动编程 程 序员用像 C Java FORTRAN 这样的高级语言编写代码 这些代码可以被计算机自动编译 不 需要程序员再去做进一步的工作 更重要的是 程序员编程的时候也不需要了解底层计算 平台的硬件细节 甚至在程序员完全不需要知道内存结构 也不知道 CPU 的信息和产他细节 的情况下 代码就可以迅速地转化为结果 上述的一切能用在并行编程上吗 我们需要的并行编译器要能找到简单环路和解决处理 器的分配等问题 而且这种编译器还能轻松地解决现在被称为 让人尴尬的并行算法 译 注 也就是相对独立的可以完全并行执行的算法 的问题 2 3 除此之外 程序员还需要对 处理器之间的行为有着充分的了解 并且知道算法需要在何时执行 1 2 自动并行编程自动并行编程 IEEE 电子工程名词标准词典里对于 算法 一词的定义如下 为了描述在有限步骤内解 决某一个问题而定义的过程或者规则 一个算法的任务或者过程一般是独立的 有些任务 可以并发执行 但有些必须线性地按顺序进行 根据上述的定义 任何算法都是由并行和非 并行两部分组成的 除了某些极端的情况 很难定义某些算法是并行的而某些是完全串行 的 即非并行 后面将探讨如何量化一个算法的并行度 如果某个算法由 W 个子任务组成 则称与这个算法有关的操作数是 W 定义一个算法的基本组成部分如下 1 不同的子任务 2 子任务之间的依赖关系 当某一个子任务的输入是另一个子任务的输出时 他 们之间则存在依赖关系 3 算法的初始输入集 4 算法的最终输出集 1 3 1 算法有向图算法有向图 我们通常用有向图 以下简称 DG 来直观地表示算法的子任务之间的数据依赖关系 DG 在描述算法的时候表示依赖图 需要用带箭头的线段强调子任务之间的数据流向关系 换句 话说 如果一个依赖图的边没有箭头表示方向 就很难从图中得知数据的依赖关系 定义 1 1 一个依赖图是边和结点的集合 结点表示算法的子任务 边表示子任务用到的 数据 数据包括输人 输出和中间结果 需要注意的是 在一个依赖图中出现的不带箭头的边表示此边连接的两个结点之间没 有数据依赖关系 它们只是共用算法中的某一个变量 这个变量可以是输入 输出或者在 算法中作为 I O 媒介的中间结果 定义 1 2 DG 是有向边和结点的集合 结点表示算法需要处理的子任务 有向边表示 子任务之间的数据依赖关系 一个子任务的输出在一条边的开端部分 箭头指向的一端表示 一个子任务的输入 定义 1 3 有向无环图 DAG 址指一个没有任何环路的 DG 图 1 2 是一个示例算法的 DAG 根据源结点和目标结点的关系来加以分类 在一个 DAG 或者 DG 里有 3 种不通过的边 定义 1 4 一个 DG 中的输人边是指只有目标结点而没有任何源结点的边 表述了算法的 一个输入 在图 1 2 中 可以粉到有 3 条这样的输人边 分别表示了输人 in0 in1 和 in2 定义 1 6 一个 DG 中的内部边是指既有源结点又有目标结点的边 表述了算法的一个内 部变量 定义 1 7 一个 DG 中的输入结点是指所有的人边都是输入边的结点 在图 1 2 中 可以看到结点 0 1 和 2 都表示输人结点 输人结点所表示的子任务在算 法输人变量就绪后就被处理 定义 1 8 一个 DG 中的输出结点是指所有的出边都是输出边的结点 图 1 2 中 可以看到结点 7 和 9 都表示输人结点 但结点 3 不是输出结点 因为结点 3 的一条出边是指向结点 7 的内部边 定义 1 9 一个 DG 中的内部结点是有至少一条人边和至少一条出边的结点 1 3 2 算法的邻接矩阵算法的邻接矩阵 一个算法也可以用一个邻接矩阵 A 来表示 若算法中有 W 个子任务 就有一个 W W 阶的 0 1 矩阵来表示这个算法 其中 a i j 1 表示结点 i 的输人依赖于结点 j 的输出 j 是源结点而 i 是目标结点 当 a i j 0 表示结点 i 的输入不依赖于节点 j 的输出 对于任何 0 iN 此时每 个处理器都需要从共享内存中读取数据 从而产生了内存冲突 可以把上述内容总结为 若处理器试图访问同一组内存模块时 将结果写回内存也有可能发生冲突 对单一处理器而言 完成一个任务所需的时间 包括内存通信时间开销 表示如下 考虑到通信开销的加速比计算等式如下 内存不匹配比 R 的定义如下 R 表示从内存读取一个数据块的延迟和处理一个数据块的延迟的比位 根据子任务的粒 以及内存读写的速度不同 应比小几个数量级 p m 还可以将等式 1 17 用 N 和 R 表示为 图 1 7 展示了以 N 和 R 为参考量 在 1 的情况下加速比的变化情况 数学模拟结果 显示的变化对结果并无显著影响 由以上等式可知 在 RN O 1 时加速比开始迅速下降 当 R 1 时出现了通信边界问题 井行化的优势 也消失了 这提醒我们内存系统的设计和处理器之间的通信问题是很重要的 第 3 章还会 讨论多核处理器 由于多核处理器将处理单元都染成在一块芯片上 相比于跨芯片的多处理 器系统 多核处理器的处理单元之间的通信速率拐到了大辐提升 在多核系统中 Tm减小了 几个数量级 R 值也大幅减小 考虑内存的读写时间 多核处理器间的通信开销表示如下 其中 0 由内存系统和算法决定 0 时表示单处理器系统 处理器之间无数据 交换 在某些算法中 p 的值可能等于 log2 N 甚至等于 N 其原因可能是程序员在编程时完 全没有考虑到处理器之间的通信问题 1 9 针对多处理器系统的针对多处理器系统的 Amdahl 法则法则 假设一个算法或者一个任务由可并行部分 f 和串行部分 1 f 组成 由单一处理器完成这个算 法的所需时间则是 等式的第一个部分的右手部 RHS 表示处理器完成串行部分所需的时间 等式的第二个部分 的 RHS 表示完成并行部分的所需时间 若有 N 个并行处理器来处理此任务 所需时间表示 为 可以将算法的并行部分分配到 N 个处理器上来实现提速 在 Amdahl 法则中 使用 N 个处 理器时的加速比 S N 表示为 由此不等式可以看出 若要加速某个算法的执行 并行部分 f 需要十分接近 1 特别是在 N 很大的时候 图 1 8 中展示了加速比与 N 和 f 的关系 实线表示 f 0 99 虚线表示 f 0 9 点线表示 f 0 5 可以从这三条曲线看出 加速比受 f 值的影响 同预期的一样 f 值越接近 1 加速比越 大 f O 5 时加速效果更加显著 随着 N 值变大 加速比的曲线也趋于饱和 当 N 值足够大时 等式 1 23 中的加速比可以表示为 由上式可以看出 若系统的处理器数目大于 10 时 加速比的提升主要依核于能挖掘出 多少程序中的可并行部分 以及能同时执行多少子任务 图 1 8 证实了这些假设 在 f 取得极限值时 等式 1 23 变形为 式的推导过程很简单 在程序完全并行时加速比等于并行处理器的数目 我们能从上述等式中得到什么结论 首先 应该知道或者大致知道给定算法的 f 值 知 道 f 值可以预测一个多处理器系统的加速比 此外 f 值也可以帮助我们判断如何将算法映 射到多处理器系统上 1 10 Gustafson Barsis 法则法则 根据 Amdahl 法则得出的加速比值是比较悲观的 因为在 Amdahl 法则中可并行化部分 f 的值是固定不变的 但是 Gustafson 的观测结果表示随着问题规模的增长一个应用的并行 度也在增长 为了推导出 Gustafson Barsis 公式 首先计算一个任务在 N 个并行处理器上完成的时间 为 若此任务在单处理器系统上处理完成 其串行部分所需时间不变 并行部分相应改变 加速比为 图 1 9 展示了加速比与 f 和 N 的对应关系 实线表示 f 0 99 虚线表示 f 0 9 点线表示 f 0 5 从图中可以看出即使 f 的值很小 加速效果依旧很明显 加速比随着 N 的提高而提高 为了得到加速效果 需满足 f N 1 1 需注意若 f 的值很小而 N 的值很大 加速效果依旧明显 相比于等式 1 24 Gustafson barsis 公式对加速比的条件限制比较宽松 1 11 并行计算的应用并行计算的应用 廉价而且强大的并行计算技术的出现 将为人们的生活带来无法预见的重大影响 搜 索引擎的技术就是并行计算的一种应用 实际上当人们输人关键词的时候搜索已经开始进 行了 并行计算技术仍有很大的提升空间 而且有很多可以创新的应用领域 本节将详述 这些应用 1 11 1 气象建模气象建模 气象模拟用来预测天气变化 也用于预测人类活动和各类现象对全球气候的影响 有 文献表示现阶段气象模拟的解析度是 200km 然而有许多气象系统的规模要小于 200km 因 此迫切需要提高解析度 假设有一个高精度的气象模拟模型 将地球划分为无数个 1km3的独立的 3D 单元 地球 的表面积大约是 510X106 km2 大气的厚度大约是 1000km 我们需要模拟大约 5X 1011个独 立的 3D 气象单元 若每个单元需要在一次迭代模拟计算中完成 200 次浮点运算 进行一 次迭代计算总计要完成 1014次浮点运算操作 假设完成一个完整周期的气象模拟需要做性能需求 运算操作总数 1014次运算 每次迭代 X106次迭代 1020浮点运算操作 1 32 使用一台每秒能完成 109次浮点运算 FLOPS 的计算机来完成上述的计算内容需要 1011 秒 约等于 31 个世纪 若要在一天内完成上述运算 需要系统的性能达到 2 8 1015FLOPS 很显然单处理器计算机无法达到这样的性能要求 我们需要将计算任务分 配至 第第 3 章章 并行计算机并行计算机 3 1 概述概述 算法和多处理器架构相互之间是紧密联系的 在考虑并行算法的时候不能脱离将要支 持这个算法的并行硬件 反过来 在考虑并行硬件的时候也不能脱离将要运行于其上的并 行算法 计算机系统中可以通过硬件和软件的手段在不同的层次实现并行 1 数据级并行 在这一层我们对一个数据的多个位或多个数据同时进行操作 例如位 并行加法 乘法 以及二进制数的除法 向量处理器和处理多数据单元的脉动式阵列 2 指令级并行 ILP 在这一层我们在处理器中同时执行多个指令 例如指令流水线的 使用 3 线程级并行 TLP 线程是程序的一部分 它与其他线程共享处理器资源 线程有时 也被称为一个轻量级的进程 在 TLP 中 多个软件线程在一个处理器或多个处理器上同时 被执行 4 进程级并行 进程是一个在计算机中正在运行的程序 一个进程保留着其拥有的 计算机资源 如内存空间和寄存器 当然 这是典型的多任务和分时计算 其中多个程序 同 时运行在共享的一台计算机或几台计算机上 3 2 并行计算并行计算 本节试图说明可用于构建并行计算机系统的不同方案 最著名的处理器分类方式是由 弗林基于数据及其被执行的操作而提出的 1 单指令单数据流 SISD 这是单处理器的情况 2 单指令多数据流 SIMD 的 所有的处理器在不同的数据上执行相同的指令 每个处 理器都在本地内存存储它自己的数据 它们之间通过典型的简单通信机制进行数据交换 许多科学和工程应用程序使用这种并行处理机制 这种应用的例子包括图形处理 视频压 缩 医学影像分析等 3 多指令单数据流 MISD 神经网络和数据流机是这种并行处理器的例子 4 多指令多数据流 MIMD 每个处理器在其本地数据上运行各自的指令 这种并行处 理器的例子通常来说就是多核处理器和多线程多处理器 弗林的分类有点粗糙 而且我们还希望在并行计算机中更加详细地探索包括 SIMD 和 MIMD 在内的其他领域 处理器之间的同步问题并不在弗林分类标准的考虑范围内 本章将 讨论最常用的并行计算机体系结构 而不是探索其他分类机制 应该指出 上述最后一种 处理器类型正在迅速成为一个流行的处理系统 共享内存多处理器 分布式内存多处理器 SIMD 处理器 脉动式处理器 集群什算 网格运算 多核处理器 流多处理器 SM 3 3 共享内存的多处理器 统一内存访问共享内存的多处理器 统一内存访问 UMA 共享内存处理器的流行是由于简单和通用的编程模型 它使得支持共享代码和数据 的并行软件开发变得简单 共享内存处理器的另一个名字是并行随机访问机 PRAM 共享内 存或共享地址空间作为处理器之间的一种通信方式 共享内存架构中的所有处理器可以通 过互联网络访问一个公用内存的相同地址空间 如图 3 1 a 所示 通常情况下 这个互联网 络是一种总线 似是对于更大的系统来说 网络取代了总线以提高性能 我们所说的性能是指在单位时间内进行的处理器 内存访问次数 吞吐址 以及从处理 器请求内存访问到该请求被允许之间的时延 延迟 互联网络类型及其性能分析可在文献 28 中找到 可以直观地看到 内存带宽成为系统瓶颈 因为在一个给定的时问内只能有一个处理 器访问内存 要解决这个问题 图 3 1 h 的配置用互联网络替代了总线 它允许多个处理 器同时访问网络 这种配置还使用多个内存取代单个内存模块 这使得多个内存读 写操作 可以同时发生 共享内存系统以及一般并行计算机的另一个常见问题是缓存一致性 共享内存中的任 何信息必须和不同 CPU 上的本地缓存中的所有副本保持一致 缓存一致性协议用于确保处 理器之间的缓存一致性 在共享内存多处理器中 任何处理器可以访问任何内存模块 图 3 1 b 显示了共享内 存多处理器架构 多个内存模块允许多个处理器同时访问多个内存模块 这当然增加了受互连 网络限制和内存冲突影响的内存带宽 内存冲突在多于一个的处理器试图访问相同的内存模 块时发生 任何内存模块设计面临的主要问题是 它通常只有一个访问端日 所以 无论 内存模块有多大 只有一个数据字节可以在任意时间内被访问 在共享内存多处理器中 每个处理器都认为只有一个内存地址空间并且访问任何内存 模块花费相同的时间 这被称为 UMA 多处理器系统 在许多共享内存多处理器中 互联网络 是一个简单的总线 这就是两个以及四个奔腾处理器时的情况 开发共享内存的多处理器并行程序不是太困难 因为所有的内存读操作对于程序员是 不可见的 并且能够以小行程序一样的方式进行编写 相对来说 写指令的编程更加困难 因为这个操作需要锁定数据访问直到某些线程完成对数据的处理 程序员必须识别出 程序中的临界区 并引人进程间和线程间的同步机制以确保数据的完整性 诸如 POSIX 的编程库和诸如 OpenMP 的指令通过屏障 锁 监听 互斥和信号量来支持同步 在共享内存多处理器系统中遇到的一个问题是缓存一致性 通常情况下 处理器在其 自己的高速缓存中留有一个在内存模块中的数据副本 现在 如果另一个处理器改变了内 存模块中这个块的内容 那么缓存中的内容就过时了 这时缓存更新政策必须被执行 以 确保所有处理器中高速缓存内的副本得到更新 同步也必须被执行 以确保多个处理器读写数据不产生冲突 信号量 互斥体和监听 被用来确保数据的完整性 第 4 章对共享内存处理器有更详细的讨论 3 4 分布式内存多处理器 非统一内存访问分布式内存多处理器 非统一内存访问 NUMA 在分布式内存多处理器中 每个内存模块和一个处理器关联在一起 如图 3 2 所示 任何处理器可以直接访问它自己的内存 消息传递 MP 机制用于允许一个处理器访问与其 他处理器关联的内存模块 消息传递接口 MPI 是一种与语言无关的通信协议 从这个意义上说 处理器的内存访问不是统一的 因为它取决于处理器正试图访问哪 个内存模块 这被称为 NUMA 多处理器系统 如果分布式内存多处理器是由相同的处理器组成的 则是一个对称多处理器 SMP 如 果内存的分布式多处理器是由异构的处理器组成的 则是一个非对称多处理器 ASMP 当分布式内存多处理器的互联网络是全球性的 如互联网 那么这个分布式内存系统 通常是由成千上万台计算机集合而成 以合作解决庞大的科学问题 并且这个系统被称内 不同的名字 如大规模并行计算 分布式计算 网格计算等 3 5 SIMD 处理器处理器 SIMD 可以被归类为一个单一程序多数据流的特殊情况 SPMD SIMD 处理器属于共享 内存多处理系统或分布式内存多处理系统 使用共享内存建立的 SIMD 适用于需要频繁交 换数据的应用程序 其中一个处理器作为新的数据的生产者 许多其他的处理器作为数据 的消费者 每个处理器与其他处理器同步执行相同的任务 正在执行的任务可能是一个简单的指 令 一个线程或进程 在处理器之间分布内存可以减少内存带宽问题 许多应用程序应用了 SIMD 处理模型 只要应用程序是可并行的 这些应用包括生物信 息学 生物医学诊断 流体力学 图像处理 视频处理等 SIMT 能够 I 著提高应用程序的 性能 有些计算机制造商在它们的处理器中加入 SIMT 扩展 并且可以运行现有的程序而 不需要重新编译 同样地一些容易学习的编程规范也利用了 SIMT 架构 例如英特尔 C 并 行探测编译器 适用干 SIMD 的共享内存模型的一个例子 是以下方程所描述的递归滤波器 其中 a j 和 a j 是滤波器系数 N 是滤波器的阶数或长度 请注意 在上面的方程中 b 0 0 所有的处理器实现上述方程 单指令 程序 但作用于不同的输入数据 处理器 i 将负责 生产过滤器的输出采样 y i 并且其他 N 个处理器可能需要在各自的计算中读取这个值 当算法的粒度很粗糙时 SIMD 机器将被称为 SPMD 机 3 6 脉动式处理器脉动式处理器 许多作者认为脉动式处理器属于流水线系统 而事实上 流水线处理是脉动式处理的一 个特殊情况 正如我们在第 2 章中看到的 流水线是一维的 并且数据流是单向的 一个典型 的管道在相邻阶段之间传输数据 脉动阵列可以是一维 二维或是不维的 如果有必要 甚 至可以是更高维度的 数据沿一个或多个方向在相邻的处理器之间沿着一个或多个方向流 动 在流水线系统中 每个流水线阶段执行不同的任务 在脉动式处理器中 所有的处理单元 PE 通常执行相同的任务 一般来说 PE 之间的互连模式是从邻点到邻点的 可能还有一些全局互连 每个 PE 有一 个小容量的内存来存储数据和中间结果 脉动架构适合实施数据依赖简单的高度规则的算 法 这些算法包括 1 线性代数 矩阵矩阵和矩阵向量乘法 求解线性方程组 2 字符串搜索和模式匹配 3 数字滤波器 例如一维 二维和三维数字滤波器 4 在视频数据压缩中的运动估计 5 有限域运算 如椭圆曲线运算 图 3 3 显示了一个用于实现矩阵一矩阵乘法算法的简单 SIMD 处理器的例子 从图中 可以看到 矩阵系数是以分布式内存的方式被存储在 PE 上的 我们也看到 处理器之间的通 信是从邻点到邻点的 正如垂直箭头所示 并且使用全局布线 如水平线所示 输入数据必 须是主要提供给左边缘上的处理器 输出数据从处于顶部的处理器获得 与脉动式架构相关的设计问题有以下几种 1 脉动式处理器旨在实现一个特定的算法 它必须重新设计以实现不同的算法 即 使在实施相同的算法时 问题规模的改变可能需要对系统进行大量的重新设计 2 提供大量输入数据给多个处理器对系统输入 输出 I O 的带宽是个严重的制约 在 一维脉动处理器中 输入通常是先送到一个处理器再经过流水线传输到其他处理器 在其他 时间 输人是通过广播总线送到 PE 或 PE 阵列的一个边缘的所有 PE 这会把脉动式处理器的 性能变成受 I O 影响的 廉价磁盘冗余阵列 RAID 可以提供一个高内存带宽的大规模存储 这个理念可以应用到闪存而非磁盘 3 从多个处理器获取大量的输出数据对系统 I O 带宽是一个严重的制约 输出可以从 一个处理器 从连接所有处理器的总线 或从一个 PE 阵列的一个边缘获得 RAID 可提供高内 存带宽的大规模存储 在我们离开本节前 有必要比较一下脉动式处理器和 SIMD 处理器 因为表面上看 这两种 类型的处理器都在多个数据上执行单一指令 表 3 1 从架构 内存和任务粒度相关的不同 方面比较了 SIMD 和脉动阵列处理器 3 7 集群计算集群计算 计算机集群是一组两个或两个以上的计算机用于执行给定问题或代码段 通常情况下 在计算集群中 将计算机连接在一起的是一个局域网络 LAN 图 3 4 显示了一个集群计算 机系统的体系结构集群中的计算机在彼此之间以及共享内存之间通信 因此 集群中处理 器的通信主要通过局域网数据包 局域网通常架设在能够支持处理器之间的高速流量的服 务器计算机上 共享内存必须能够在同一时间与多个处理器通信 根据共享的内存大小 它可以使用 RAID 实现 客户机在集群的处理器之间分配任务并且收集结果 3 8 网格计算 云计算 网格计算 云计算 网格计算是指为用户提供使用分布在广域网 WAN 上的计算资源的服务 从这个意义 上说 网格计算机是一个分布在广阔的地理区域的大量处理器的集合 网格计算处理的计算 任务规模较大 如 N 体模拟 地震模拟 大气和海洋模拟 相对于集群计算 网格计算机是 一个大的集群 其中 LAN 被诸如 Internet 的 WAN 取代 本章后面的习题总结了集群计算和 云计算之问的主要区别 一些使用云计算实现的应用包括 对等 P2P 计算 作为服务的软件 像 Google App Google Calendar 和 Google Mail 海量存储 Web 应用程序和社交网络 3 9 多核系统多核系统 多核系统通常是指所有处理器都在同一芯片上的多处理器系统 它也可以指处理器在 不同的芯片上 但在同一个封装内 即一个多芯片模块 的系统 这种紧密的封装保证了较 快的处理器间通信 同时保持了较低的功耗 对于双核或四核系统 处理器通信使用一条 简单的总线 对于更多数量的核心 处理器使用片上网络 NOC 进行互连 另一方面 多处 理器系统的处理器分布在不同的芯片上 并目 处理器间互连依靠的是底板总线 继续研究并 且得到一种每个芯片都是多核心芯片的多处理器系统是可能的 多核系统的开发主要是为了提高系统的性能同时限制其功耗 换句话说 即使其组成核 心是低性能处理器 多核系统仍具有良好的性能表现 相比之下 多处理器系统的开发提高了 系统性能 却很少考虑功耗 一个多处理器系统具有良好的性能并且使组成的处理器也是高 性能的 表 3 2 总结了多核系统与多处理器系统的主要区别 图 3 5 显示了多核处理器的草图 一个多核系统由以下部分组成 1 通用的可编程核心 2 特殊用途的加速核心 3 共享内存模块 4 NoC 互联网络 5 I O 接口 为什么要走向多核系统 最主要的原因是可扩展性 当我们通过增加处理器数量来提高 性能时 多核系统限制了功耗和处理器问的通信开销 多核系统还可以通过加入更多的 CPU 内核或者调整互连网络来进行扩展 要充分利用增加的资源还要做更多的工作 增加 CPU 资源数量是一回事 更好地调度它们来有效地处理任务又是另一回事了 一些能够高效地在多核系统上实现的应用程序包括 1 通用多任务计算 2 网络协议处理 3 加密 解密处理 4 图像处理 3 10 流多处理器流多处理器 流多处理器 SM 是一种 SIMD 或 MIMD 机器 其组成处理器是流处理器 SP 或线程处理 器 流处理器定义为一个处理数据流的处理器 其指令集架构 ISA 包含了 核 来处理这些 流 流处理的概念与图形处理单元 GPU 密切相关 从而使 GPU 能够执行一般的计算密集型 的通用计算 GPU 也因此成为了通用 GPU 数据流的例子有浮点数向量或视频数据处理中 的一组帧像素 这种类型的数据显示出了时间和空间局部性 时间局部性是输入的数据流 只使用几次来产生输出流 空间局部性是输入数据流处于内存的同一个块内 流多处理器 的一个成功的例子是新一代的 GPU 如 NVIDIA 的 Fermi 适合 SM 的应用程序必须满足 3 个特点 1 计算密集性 2 数据并行性 3 消费一者一生产者局部性 也就是时问和空间局部性 计算密集性的定义是算术运算次数与 I O 或全局内存访问次数的比值 适合流处理的 应用中 这个比例可能达到 50 1 以上 数据并行性是对输入流的所有数据并行地进行同 一操作 生产者一消费者局部性是数据被读取或使用一次或若干次以产生输出流 诸如 NVIDIA 的 Ferrni 的 GPU 能够支持数以万计的并行线程 因为适合流多处理的数据显示出局限性 这些数据使用本地高速缓存 井且没有缓存命中 失败 这消除了内存延时大的问题 简而言之 SM 或 GPU 适合长数据序列的应用 这些数据 能够使用数千个线程执行 3 11 并行处理器之间的通信并行处理器之间的通信 我们在本节中回顾并行处理器如何通信以及使用什么类型的通信策略 并行处理器为 了完成分配给它们的任务需要彼此之间交换数据 3 11 1 通信类型通信类型 我们可以定义以下类型的通信模式 1 一对一 单播 2 一对多 组播 3 一对全部 广播 4 收集 5 规约 图 3 8 显示了不同类型的通信模式 一对一 单播 一对一操作涉及一对处理器 发送端和接收端 这种模式有时也称为点对点通信 我们 往往在 SIMD 机中遇到这样的通信 其中每个处理器与它的邻居交换数据 图 3 8 a 显示了 处理器之间的一对一通信模式 图中只显示一对处理器之间的通信 但通常情况下 所有的处 理器都可以在同一时间执行一对一通信 此操作通常是在每次迭代中进行的 因此须做到 高效率 大部分时间里 假设相邻的处理器之间的时钟同步已经完成 源寄存器和目的寄 存器之间使用一个简单的数据交换 在其他情况下 双向方式 即数据一确认 甚至四向握 手 即请求一确认一数据一确认 也是必要的 一对多 组播 一对多操作涉及一个发送端处理器和多个接收端处理器 图 3 8 b 给出了一对多的通 信模式 图中只显示了一个源到多个接收处理器的通信 但通常情况下 所有的处理器可 以在同一时间执行一对多通信 接收处理器的数量取决于该算法的细节 以及如何完成任 务到处理器的映射 此操作通常是在每次迭代中进行 因此必须做到高效率 大部分时间 里 假设相邻的处理器之间的时钟同步已经完成 源寄存器和目的寄存器之间进行一个简 单的数据交换 在其他情况下 双向方式 即数据一确认 甚至四向握手 即请求一确认一数 据一确认 也是必要的 一对全部 广播 广播业务涉及在系统中发送相同的数据给所有处理器 图 3 8 c 显示了处理器之间的广 播通信模式 这种模式在提供数据给所有处理器时非常有用 它也可能意味着一个处理器作 为发送端 其他处理器接收数据 我们将在脉动阵列和 SIMD 机上看到这种通信 收集 收集操作包括从几个或全部处理器收集数据 图 3 8 d 显示了处理器之间的收集通信 模式 假设我们有 P 个处理器 所需收集数据的时间可以被计算为 其中 tc为传输一接收一处理一个数据项所需的时间 规约 规约操作与收集操作类似 除了一些操作是针对收染到的数据 图 3 8 d 显示了处理 器之间的规约通信模式 一个规约操作的例子是当所有的处理器产生的所有数据相加以产 生一个最终值 当需要规约的数据很多时 这项任务可能需要很长一段时间 似设我们有 P 个产生待加数据的处理器 总的时间预计为 T reduce T gather P 一 1 tc 3 3 其中 tc是处理器处理一对已收到数据单元所猫的时间 层次化执行规约操作可能是值得的 在这种情况下 规约延迟时间为 T reduce logs P tc tp 3 4 3 11 2 消息传递 消息传递 MP 通信机制 通信机制 MP 主要用于分布式内存机器 两个处理器之问传递消息过程涉及使用 send 和 recv 库函数 程序员使用 Send destination message 库之函数来确定目的处理器成进程的 ID 以及 要发送的数据 程序员还必须使用 recv source message type 库函数指定源处理器或进程的 ID 和接收数据的类型 为了让两个处理器使用 MP 通信 需要两个操作 1 在它们之间建立通信链路 链路建立依赖于互联网络的特性 我们可以考虑链路的 物理性质 硬件 或它的逻辑性质 地址 单向或双向 能力 信息大小等 2 通过 send 和 recv 库函数交换消息 MPI 是一个为了改善 MP 的使用和可移植性而开发的标准 MP 同步确保处理器之间的正确通信 同步必须由程序员认真处理 因为执行 Send 和 RECV 库函数是在操作系统或运行在处理器上的系统的控制下的 同步策略有类型 同步或阻塞 发送方在它执行了 send 库函数之后暂停执行 直到消息被接收 此 外 接收方在执行 RECVO 库调函数后暂停 直到消息可用 异步或非阻塞 发送方执行 send 库函数后继续执行 此外 接收方执行 RECV 库函 数后也继续执行 MPI 标准支持单播和广播通信方式 3 12 并行体系结构总结并行体系结构总结 前面的部分简要介绍了已经广泛应用的 5 个并行处理器系统 共享内存 分布式内存 SIMD 脉动式 多核 各个种类很难被严格区分开来 例如 可以在共享内存系统上面建立 SIMD 我们可以 通过以下几点来总结这些多处理器的突出特性 1 除脉动式处理器外 所有多处理器都使用了容易确认的互联网络进行通信 2 脉动式处理器拥有邻点到邻点的连接 却没有全局总线 3 除脉动式处理器外 所有多处理器在特性上与 SIMD 相比更加通用 它们应用于各 种任务和算法 4 脉动式处理器旨在执行特定的算法 算法决定了一些细节 如处理器间通信 I O 数据计时和 I O 数据的进人或提取点 5 多核系统使用加速核心来实现一个需要较高速度执行的特殊任务 例如 我们可以 在多核系统中放置一个 GPU 来实施密集的图形处理任务 这种加速核心是采用脉动式处理 器建立的 第第 4 章章 共享内存多处理器共享内存多处理器 4 1 概述概述 共享内存多处理器拥有简单和通用的编程模型 不仅推动了支持代码和数据共享的并 行软件的发展 也使它们在业界受到普遍欢迎 共享内存多处理器为每个处理器提供一个唯一的物理地址空间 使得每个处理器能够 使用本地的内存和高速缓存运行自己的程序 这些处理器也可以存取分布在不同模块的共 享内存 处理器主要与高速缓存通信 因为高速缓存是访问速度最快的存储设备 能够跟上处 理器的速度 这就引出两个重要问题 1 高速缓存一致性 2 同步和互斥 4 2 高速缓存一致性和内存一致性高速缓存一致性和内存一致性 为什么高速缓存是有效的 访问速度快 但是空间很小 时间局部性 如果一个数据正在被访问 那么近期它很可能还会被访问 空间局部性 在最近的将来将用到的数据很有可能与现在正在使用的数据在空间上是 临近的 对于共享内存系统 当两个以上处理器试图存取相同的内存模块时 高速缓存有助于 消除内存资源的竞争 什么是高速缓存一致性 共享内存中数据的副本必须与高速缓存中的数据副本一致 举例 在一个拥有四个处理器和一个共享内存模块的系统中 这些处理器读取共享内 存中一个块的数据 随后多个处理器对该块数据进行更改 将产生问题 全写式策略 考 虑 会有什么问题 还有这样一个问题 当处理器读取共享内存中的一个块 随后这个块的值被其他处理器更 改 假设使用写回式策略 怎么解决更新块 b 的正确顺序呢 遵循下面两种方法 1 块 b 的正确更新是基于程序的顺序执行 2 块 b 的正确更新是基于数据的依赖性 常见的两种高速缓存一致性协议 目录协议和 Snoopy 协议 1 目录协议 每个处理器的本地缓存都有一个本地缓存控制器用于更新其内存中共享变量的副 本 中央控制器负责整个系统的缓存一致性 有一部分共享内存是目录结构 目 录中每一项对应存放着相应共享内存块的信息 目录项的结构依赖于所使用的目 录协议的部署细节 中央控制器处理本地缓存请求 当共享变量的状态发生变化 时 中央控制器负责通知本地缓存控制器相应变化 互连网络是控制器间通信的 介质 同时也连接缓存和共享内存 图 4 4 描述了全映射目录协议的细节 每项包含 n 2 位 其中 n 表示处理器的数量 假设 n 8 标志为 D 的位只是数据有效 0 或已更改 1 标志为 X 的位指示是否 使用广播更新数据到处理器 广播为 B 非广播为 NB 可以从图中看出 如果该 项所对应的块已更改 那么只有处理器 1 和 4 中的缓存会得到更改通知 特点 每个一致性失误必须发送个中央管理器 可能导致中央控制器成为瓶颈 并且 当处理器的数量发生变化时 目录项的大小也会同时发生变化 2 Snoopy 协议 Snoopy 协议不是在共享内存中使用目录和中央控制器 而是块的一致性是通过相 应的本地缓存和共享内存的通信维持的 其他本地缓存将监听这些通信 互连网 络需要支持数据的广播传输 使得每个处理器都能监控整个网络的活动 一个共 享的总线适合这种广播模式 缺点 共享总线的带宽是有限的 一次连接只能允许一个事务发生 当有一个处理器对内存进行写操作 所有其他的处理器需要判断操作是否与自己 相关 若处理器 Pj有一个被处理器 Pi访问到的内存块副本 那么 Pi的这个写操作 与 Pj相关的 Pj有两种选择 基于无效的策略和基于更新的策略 4 3 同步和互斥同步和互斥 临界区 任何一个对共享变量进行操作的程序和线程多拥有的一个代码区域 互斥 是指散步在不同进程间的若干程序片段 当某个进程运行其中一个程序片段时 其 它进程不能运行这些程序片段 只能等到该进程运行完成后才可以运行 同步 是指散步在不同进程之间的若干程序片段 他们的运行必须严格按照规定的某种先 后次序来运行 这种先后次序依赖于要完成的特定的任务 显然 同步是一种更为复杂的互斥 软件实现的同步和互斥方法 锁机制 信号量 监听器和栅栏 4 3 1 锁机制锁机制 所有的临界区问题都会用到锁 Boolean TestandSet Boolean lock Boolean v lock 读操作 lock true 修改和写操作 Return v 进入临界区的过程 Code before critical section 试图获得锁 while TestAndSet 空闲并继续尝试获取锁 临界区代码开始 critical section code 临界区代码结束 lock FALSE Code after critical section 4 3 2 互斥量互斥量 信号量是一个数 两个基本的原子操作 wait 和 signal Wait While m 0 do nothing M decrement M if it is 1 Signal M M increment 1 执行临界区时的过程 Code before critical section 试图获得信号量 wait M 空闲并继续尝试获取信号量 临界区代码开始 critical section code 临界区代码结束 signal M 释放信号量 Code after critical section 4 3 3 栅栏栅栏 栅栏主要使用在多个独立的作业或者线程用于并行完成一些任务的情况 同步栅栏用于事 件同步 适合用于串并行算法中 初始化栅栏 1 include 2 pthread barrier t barrier 3 pthread barrierattr t attribute 4 unsigned count 5 int return value 6 return value pthread barrier init 以下代码使用栅栏同步线程的执行 1 Code before the barrier 2 3 在栅栏处等待 4 ret pthread barrier wait 5 6 Code after the barrier barrier 类型初始化所使用的方法是 pthread barrier init 第第 5 章章 互连网络互连网络 并行计算机借助互连网络使得数据能够在处理器之间或者处理器与内存之间进行传递 影响互连网络性能的因素主要有 1 网络连接介质 可以是有线的 无线的或是光通道的 2 交换机 switches 将所有链接连接在一起 3 软件固件协议 software firmware protocol 通过交换机和链接在处理器之间传输 信息 4 网络拓扑 即交换机连接在一起的方式 互连网络的容量和特性对处理器系统的性能有直接影响 本章要介绍多处理器中常用 的几种互连网络 主要介绍片内网络 多核处理器中的核和链接这些核的互连网络同在一 个芯片上 网络直径 拓扑中距离最长的两个节点之间的距离 这里距离表示信息从源点传到终 点所要经历的交换机或结点的个数 5 2 逻辑拓扑结构中互连网络的分类逻辑拓扑结构中互连网络的分类 5 2 1 总线型总线型 所有的处理器和内存模块都连接在总线上 任意两个处理器之间通信所有时间都是相 同的 但是任意时刻总线上只允许一个处理器对共享资源进行访问 为了防止总线访问冲 突 需要执行 MAC 仲裁机制 影响总线型系统性能的因素 连接到总线上的处理器数量 随着总线的增加 系统性能会降低 处理器请求访问总线的次数 MAC 仲裁锁使用的机制 5 2 2 星型星型 所有的处理器都连接在一个中央集线器上 处理器之间的通信必须经过中央集线器 由于要负责和所有处理器通信并处理他们的请求 因此集线器限制了系统的性能 优点是 扩展性好 很容易增加处理器 但会增加集线器的负担 5 2 3 环型环型 环型网络中 每个处理器都通过交换器连接到环上 方格代表介质访问控制器 交换 器知道连接到它上面的处理器的 MAC 地址 交换器允许多个处理器同时传输和接收数据 处理器将要发送的数据传输给它的交换器 随后交换器将数据传输给它相邻的交换器 这 样 数据就在环中的交换器中传输直到它到达目的主机 5 2 4 网型网型 每个交换器和路由器都部署了路由算法 通过算法信息可以从源处理器传递到目的处理器 确定路由算法是在传输前就确定好的 自适应路由算法是动态变化的 5 2 5 交叉开关网络交叉开关网络 一个 N N 的交叉开关网络由 N 个输人和 N 个输出组成 它能连接任意一个输人和输出 图 5 5 给出了一个 6 6 的交叉开关网络 该网络由一组交叉点 CP 构成 它们以网格的形 式排列 CP i j 表示第 i 行第