多核及GPU程序设计1简介
1 简介[*]计算机设计的趋势及其对软件开发的影响。
[*]Flynn 分类法
[*]评估多核/并行性能、加速比和效率的基本工具。
[*]测量和报告性能的正确实验程序。
[*]阿姆达尔定律和古斯塔夫森-巴塞尔定律，并运用它们来预测并行程序的性能。
1.1 多核时代
自 20 世纪 80 年代以来，数字计算机一直是我们经历的许多科技进步的基石。正如摩尔在 20 世纪 70 年代最初观察到的那样，它们处理信息的速度呈指数级增长，这使我们能够解决越来越复杂的问题。
令人惊讶的是，摩尔定律甚至在今天仍然适用于描述行业趋势，但需要澄清一个很容易被科普忽视的小问题：呈指数增长的是晶体管数量，而不是运行速度！这是一个很容易犯的错误，因为晶体管数量的增加伴随着工作频率（也称为“时钟”）的飞跃，这是电路小型化所适应的。然而，增加时钟频率会导致发热量增加。芯片设计人员通过降低电子电路的工作电压（目前运行电压低至 1.29 V！）来应对，但这不足以解决问题。这不可避免地阻碍了时钟频率的增长，自 2000 年代中期以来，时钟频率一直保持在 2-5 GHz 范围内。因此，满足更多计算能力需求的唯一途径是在芯片内塞入更多的计算逻辑和计算核心。自 IBM 于 2001 年推出首款双核单芯片芯片 Power 4 以来，各种多核芯片相继问世，既包括拥有大量内核的同构芯片，例如 64 核 Tilera TILE642，也包括为索尼Playstation 3 (PS3) 等游戏提供动力的 Cell BE 等异构芯片。
这些芯片是20世纪90年代中后期多路平台（即可在独立芯片上承载多个CPU的机器）的自然演进。然而，出乎意料的是GPGPU计算（General-Purpose computing on Graphics Processing Units ：通用图形处理器计算）的出现，这是一种使用图形处理单元（GPU）进行通用计算的范例。虽然与当代CPU核心相比，单个GPU核心的性能不足，但GPU拥有大规模并行架构，拥有数百或数千个核心，并由高带宽、高速RAM“驱动”。其结果是计算速度提高了几个数量级！
在能源日益匮乏的今天，GPGPU还提供了一项独特的优势：它提供了卓越的GFlop/Watt性能，即单位能耗可以完成更多计算。这在服务器和云基础设施领域尤为重要，因为在这些领域，CPU在其运行生命周期内消耗的能耗可能远高于其实际价格。 GPGPU技术被认为是一项颠覆性技术，这体现在多个层面：
它能够解决当代单核甚至多核CPU技术无法解决的问题，但它也需要新的软件设计和开发工具及技术。预计在不久的将来，需要数百万个线程才能掌握即将问世的下一代高性能计算硬件的计算能力！
多核芯片为我们带来的所有这些性能并非无缘无故：它需要对算法进行明确的重新设计，而这些算法传统上是基于单一确定性步骤序列运行的。
1.2 并行机的分类
通过利用多种资源来提升当代计算技术的性能并非新事物。早在20世纪60年代，这种探索就已开始，因此找到一种描述并行机架构特征的方法至关重要。迈克尔·弗林 (Michael Flynn) 于 1966 年提出了一种计算架构分类法，该分类法根据机器能够同时处理的数据项数量以及能够同时执行的不同指令数量对机器进行分类。这两个标准的答案可以是单个，也可以是多个，这意味着它们的组合可以产生四种可能的结果：
[*]单指令单数据 (SISD：Single instruction, single data)：简单的顺序执行机器，每次执行一条指令，操作单个数据项。令人惊讶的是，绝大多数当代CPU并不属于这一类。即使是如今的微控制器也提供多核配置。它们的每个核心都可以被视为SISD机器。
[*]单指令多数据（SIMD：Single instruction, multiple data）：每条指令应用于一组数据项的机器。矢量处理器是最早遵循这种范式的机器。GPU也遵循这种设计，例如NVidia的流式多处理器（SM）3和AMD的SIMD单元。
[*]多指令单数据（MISD：Multiple instruction, single data）：这种配置似乎有些奇怪。如何将多条指令应用于同一个数据项？在正常情况下，这没有道理。但是，当系统需要容错功能时（军事或航空航天应用符合这种描述），数据可以由多台机器处理，并根据多数原则做出决策。
[*]多指令多数据 (MIMD：Multiple instruction, multiple data)：用途最广泛的机器类别。包括 GPU 在内的多核机器遵循此范式。GPU 由一系列 SM/SIMD 单元组成，每个单元都可以执行自己的程序。虽然每个 SM 都是一台 SIMD 机器，但它们总体上表现得像一台 MIMD 机器。
多年来，该分类法不断完善，尤其是在 MIMD 领域增加了子类别：
MIMD 可分为两大类：
[*]共享内存MIMD
具有通用可访问共享内存空间的机器架构。共享内存以最小的开销简化了 CPU 之间需要进行的所有事务，但它也构成了限制系统可扩展性的瓶颈。解决这个问题的一个方法是在CPU之间划分内存，这样每个CPU就“拥有”一部分内存。这样，一个CPU可以更快地访问其本地内存，但它仍然可以访问其他CPU的非本地内存，尽管速度较慢。这种划分不会影响通用的寻址方案。这种设计被称为非均匀内存访问 (NUMA：non-uniform memory access)，它允许共享内存的机器扩展到几十个CPU。
[*]分布式内存或无共享多数据流多任务处理器 (MIMD)：
由通过交换消息进行通信的处理器组成的机器。通信成本很高，但由于没有单一的介质竞争，这种机器可以扩展，除了空间和能量限制外，没有任何实际限制。
共享内存机器可以进一步细分为主从式和对称多处理平台。在后者中，所有参与的CPU都是相同的，并且能够执行系统中的任何程序，包括系统和应用软件。在主从架构中，一些处理器专用于执行特定软件，也就是说，我们可以将它们视为协处理器。配备 GP的系统可以被视为属于此类，尽管大多数高性能 GPU 平台为 CP 和 GPU 提供了不同的内存空间。因此，它们并非共享内存平台，尽管最近的驱动软件进步隐藏了在两个内存之间移动数据所涉及的大部分复杂性。
配备英特尔至强融核协处理器的机器也存在同样的配置。英特尔至强融核协处理器的初始版本包含 61 个 Pentiu 核心，作为共享内存 MIMD 平台运行。它安装在 PCIe 卡上，尽管它与主机 CPU 位于同一机箱/底盘上，但组合 CPU/协处理器系统最合适的分类是分布式内存 MIMD 系统。
1.3 有影响力的计算机一瞥
当代计算机模糊了 Flynn 所列出的类别之间的界限。对更高性能的追求导致了机器既支持 MIMD 指令集，又支持 SIMD 指令集，具体取决于所处的测试级别。目前，利用微型化和半导体材料进步带来的晶体管数量增加，主要有两种趋势：
[*]
[*]增加片上核心数量，并结合增强的专用 SIM 指令集（例如 SSE 及其后续版本、MMX、AESNI、AVX 等）和更大的缓存。英特尔的 Xeon Phi 协处理器以及 AMD 的 Ryzen 和 Epyc 系列就是最好的例子。
[*]
[*]将异构核心组合在同一封装中，通常是 CPU 和 GPU 核心，每个核心针对不同类型的任务进行优化。AMD 的加速处理单元 (APU) 系列芯片就是最好的例子，这些芯片通常用于索尼的 PS4 和 PS5 以及微软的 XBox One 等游戏主机。英特尔也在其集成显卡的 CPU 系列中提供基于 OpenCL 的计算。
但是，为什么在同一块芯片上同时配置 CPU 和 GPU 核心如此重要呢？让我们先来讨论一下 GPU 究竟能给游戏带来什么！
GPU，也称为图形加速卡（graphics accelerator card），是为了在海量图形数据被放入卡的显示缓冲区之前对其进行快速处理而开发的。它们的设计范围决定了其布局与传统 CPU 的传统布局截然不同。CPU 采用大型片上（有时是多个）内存缓存、少量复杂（例如流水线式）算术和逻辑处理单元 (ALU)，以及复杂的指令解码和预测硬件，以避免在等待数据从主内存到达时出现停顿（空闲）。相反，GPU 设计人员选择了一条不同的路径：小型片上缓存，以及一组能够并行操作的简单 ALU，因为对于图形处理来说，数据重用率通常较低，而且程序相对简单。为了给 GPU 上的多个核心提供数据，设计人员还专门设计了非常宽、快速的内存总线来从 GPU 的主内存中获取数据。在 CPU 中，内存缓存占据了芯片的主导地位，而在 GPU 中，计算逻辑占据了主导地位。
GPU 已被证明能够提供前所未有的计算能力。然而，在系统中，它们以专用显卡的形式使用，并通过 PCIe 等慢速总线与主 CPU 通信，这会影响其效率。原因是数据必须先在主计算机内存和 GPU 内存之间传输，然后 GPU 才能处理它们。这实际上创建了一个数据大小阈值，低于该阈值，GPU 就不是有效的工具。每个 SMX SIM 块包含 192 个核心和 64 KiB 的缓存/共享内存。每个 i7 核心都包含其私有的 32 KiB 数据一级缓存和 32 KiB 指令一级缓存，以及 256 KiB 二级缓存。i7-5960X 中的共享三级缓存为 20 MiB。CPU 和 GPU 核心共享和访问同一内存空间的重要性显而易见。原则上，这种安排可以更好地整合计算资源，并可能带来更高的性能，但只有时间才能给出答案。
1.3.1 Cell BE 处理器
Cell BE（宽带引擎）处理器因驱动索尼的 PS3 游戏机而闻名，于 2007 年推出，是索尼东芝和 IBM 合资的成果。Cell 的设计远远超越了时代：一个主从异构 MIMD 芯片机器。PS3 游戏机配备的芯片版本包含以下内容：
[*]master是一个 64 位 PowerPC 核心（称为 Power 处理单元 ），能够运行两个线程。它负责运行操作系统并管理工作单元。
[*]workers是八个 128 位矢量处理器（称为协同处理单元 ）。每个 SPE 都有自己专用的片上本地内存（而非缓存），称为“本地存储器”，用于保存正在运行的数据和代码。
SPE 核心与 PPE 不二进制兼容：它们拥有专为 SIMD 操作设计的指令集。PPE 负责初始化并启动其上的作业。SPE 通过称为元素互连总线 (EIB) 的高速环形互连进行通信。SPE 无法直接访问主内存，但它们可以在主内存和本地存储之间执行 DMA 传输。
该硬件的设计目标是实现最高的计算效率，但却牺牲了编程的简易性。Cell 因其是最难编程的平台之一而臭名昭著。
Cell 在推出时是市场上最强大的处理器之一，八个 SPE 合计的双精度运算峰值性能高达 102.4 GFlops。它很快成为以 PS3 集群形式构建“廉价超级计算机”的组件。这些机器上运行的应用程序包括天体物理模拟、卫星成像和生物医学应用。值得注意的是，IBM Roadrunne 超级计算机是 2008-2009 年间全球速度最快的超级计算机，它包含 12.24 台 PowerXCell 8i 处理器和 6562 台 AMD Opteron 处理器。PowerXCell 8i 是原始 Cell 的增强版，改进了双精度浮点运算能力点性能。
Cell 处理器已停止开发，可能是由于其编程复杂性和 GPU 计算技术的进步。
1.3.2 NVidia 的 Amper
Ampere 是 NVidia 专为计算应用设计的第八个 GPU 架构。对于初学者来说，这种新架构和之前的架构一样令人惊讶！只有当人们尝试编写这种设计的程序时，它与“传统” SMP 芯片的区别才会变得显而易见。在本节中，我们将了解使这款 GPU 和其他 GPU 成为强大计算机器的架构特性。
Ampere GPU 中的内核按称为流多处理器 (SM： Streaming Multiprocessors) 的组排列。每个 Ampere SM 包含 64 个内核，这些内核以 SIMD 方式执行，即它们运行相同的指令序列，但处理不同的数据。不过，每个 SM 都可以运行自己的程序。SM 块的总数是同一系列不同芯片之间的主要区别因素。目前，安培系列中最强大的芯片是 A100 GPU，它启用了 108 个 SM，最多可启用 128 个，以提高生产良率。这意味着每个 A100 GPU 总共配备 108·64=6912 个核心！这些核心的双精度运算峰值性能为 9.7 TFlops，使用张量核心时可提升至 19.5 TFlops 。张量核心是一种专门用于快速执行乘法和累加运算的单元，以满足人工智能 (AI) 应用程序的要求。张量核心首次出现在 NVidia 的 Volta 架构中。
GPU 用作协处理器，从主 CPU 分配工作项。在这种情况下，CPU 被称为主机。如果让代码为这 6912 个核心分别生成一个线程，会显得有些笨拙。相反，GPU 编程环境允许启动称为内核的特殊函数，这些函数使用不同的内部/内置变量运行。事实上，单个语句/内核启动可以生成的线程数量高达数万甚至数百万。每个线程将轮流在 GPU 核心上运行。
该顺序可以概括为主机 (a) 向 GPU 发送数据 (b) 启动内核，以及 (c) 等待收集结果。
截至 2021 年 6 月，排名前九的最强大的超级计算机按其最大交付 TFlop/KW 比率降序排列如下：
为了加速线程执行，片上内存配置旨在将数据“靠近”核心。该片上内存子系统包含一个大型寄存器文件，每个线程可分配 255 个 32 位寄存器，并配备 40 MB 二级缓存以降低延迟。Ampere 与传统 CPU 的最大区别在于其组合式一级缓存/共享内存。这是每个 S 独有的，其分区可由主机通过编程控制。共享内存对应用程序而言并不像缓存那样透明。它是可寻址内存，可以被视为一种用户管理的缓存。
192 MB 的一级缓存/共享内存与不久前每个 SM 仅有 16 MB 共享内存的 GP 设计相比，是一个巨大的飞跃。多年来，我们在 GPU 设计中见证了更大、更复杂的缓存层级、更强大的核心（Kepler，2012 年的架构，每个 SM 拥有 192 个核心）以及专用硬件/指令集（张量核心）的加入。GPU 正变得越来越像 CPU，反之亦然！
GPU 的一个普遍特征是能够以更少的资源实现更高的性能：以更少的能耗完成更多的计算。这在高性能计算 (HPC) 领域至关重要，因为该领域的能耗成本远低于硬件本身的成本，这使得 GPU 成为数字运算的首选。
就 A100 而言，通过将设备内存与 GPU 连接在同一基板上，效率得到了进一步提升。GPU 与六个第二代高带宽内存 (HBM2：second-generation high bandwidth memor) 模块耦合，从而降低了与 GPU 之间数据传输所需的功耗。
1.3.3 从多核到众核：TILERA 的 TILE-Gx8072 和英特尔的 Xeon Phi
GPU 十多年来一直承载着数百或数千个（虽然很简单）计算核心。但它们可以在图形工作负载等特殊情况下保持高效运行。对于通用计算平台而言，实现同样的性能能够运行操作系统任务和应用软件的 ose CPU 则完全是另一回事。两种成功实现这一壮举的设计都采用了硅片，这种众所周知的网络配置在过去几十年中一直用于构建并行机器。这是一个小型化的成功案例。
多核范式的首个体现是 TILERA 的 TILE64 协处理器，于 2007 年 8 月发布。TILE64 提供 64 个内核，以二维网格排列。TILERA 后来提供的设计采用了不同的配置，包括 9 核、16 核、36 核和 72 核。72 核版本（即 TILE-Gx8072,4）的框图如图。被称为 iMesh Interconnect 的二维通信信道网格包含五个独立的网状网络，可提供超过 110 Tbps 的总带宽。通信通过无阻塞直通交换完成，每跳一个时钟周期。每个核心拥有 32 KiB 数据和 32 KiB 指令一级缓存以及 256 KiB 二级缓存。核心之间共享 18 MiB 三级一致性缓存。通过四个 DDR3 控制器访问主 RAM。
TILE-Gx8072 CPU 的目标应用是网络（例如，过滤、节流）、多媒体（例如，转码）和云应用。网络功能备受关注，其 32 个 1 Gbps 端口、8 个 10 Gbps XAUI 端口以及两个专用压缩和加密加速引擎 (MiCA) 就是明证。
与 GPU 一样，TILERA 的芯片可以用作协处理器，从主 CPU/主机卸载繁重的计算任务。它提供四个多通道 PCIe 接口，可加速与主机之间的数据传输。它还可以用作独立平台，因为它运行Linux内核。TILERA提供其多核开发环境（MDE）作为其芯片的软件开发平台。MDE基于开源软件（OSS）工具构建，例如GNU C/C++编译器、Eclips IDE、Boost、线程构建块（TBB）和其他库。因此，它利用现有的多核开发工具，并与多种语言、编译器和库保持兼容。第3章和第8章介绍了适用于TILERA芯片软件开发的工具和技术。
英特尔进入多核领域的时间要晚得多（2012 年），英特尔至强融核推出时，它是 Top50 榜单前 10 名超级计算机中的 2 台的构建模块。至强融核配备 61 个 x86 核心，这些核心是高度定制的奔腾核心。定制包括能够同时处理四个线程以隐藏管道停顿或内存访问延迟，以及一个特殊的 512 位宽矢量处理单元 (VPU)，它以 SIMD 模式运行，每个时钟周期处理 16 个单精度或 8 个双精度浮点数。VPU 还具有扩展数学单元 (EMU)，用于处理超越函数，例如矢量上的倒数、平方根和指数函数。每个核心配备 32 KiB 数据一级缓存和 32 KiB 指令一级缓存，以及 512 KiB 二级缓存一致性缓存。
这些核心通过另一种著名的通信架构连接，该架构也用于 Cell BE 芯片：环。该环是双向的，实际上由六个独立的环组成，每个方向三个。每个方向都有一个 64 字节宽的数据环和两个较窄的环：一个地址环 (AD) 和一个确认环 (AK)。AD 环用于发送读/写命令和内存地址。AK 环用于保持二级缓存一致性。一致性由分布式标签目录 (TD) 管理，其中包含有关芯片上每个二级缓存行的信息。
当某个核心发生二级缓存未命中时，它会通过 AD 环向标签目录发送地址请求。如果请求的数据块位于另一个核心的二级缓存中，则会通过 AD 环向该核心的二级缓存发送转发请求，随后请求的数据块会通过数据环转发。如果请求的数据不在芯片上，则内存地址会从标签目录发送到内存控制器。
冗余设计（即每种类型的环各有两个）确保了可扩展性，因为测试表明，仅使用 AK 和 AD 类型的环会导致性能在 30 到 35 个核心左右时趋于平稳。GDDR5 内存控制器跨核心交错排列，并通过这些环进行访问。内存地址在各个控制器之间平均分配，以避免任何一个控制器成为瓶颈。
硬件性能令人印象深刻。但如何对 61 个核心进行编程呢？至强 Ph 协处理器以运行 Linux 的 PCIe 卡形式提供。特殊的设备驱动使 PCIe 总线作为网络接口，这意味着协处理器在主机看来就像另一台通过网络连接的机器。用户可以使用 SSH 登录 Xeon Phi 主机！
应用程序可以在主机上运行，并将部分内容卸载到 Xeon Phi 卡上，也可以完全在协处理器上运行，在这种情况下，它们被称为以“本机模式”运行。Xeon Phi 利用所有现有的共享和分布式内存工具的基础设施。人们可以使用线程、OpenMP、Intel TBB、MPI 等为其构建应用程序。这也是多核架构相对于 GPU 的一大优势，因为后者需要掌握新的工具和技术。
最后，值得注意的是所有承载多核的架构都有一个共同的特点：相对较低的时钟频率。 GPU（0.8-1.5 GHz）、TILE-Gx8072（1.2 GHz）和英特尔至强融核（1.2-1.3 GHz）均具备这一特性。这是在同一块芯片上塞入数十亿个晶体管所必须付出的代价，信号传播延迟会增加。
英特尔于2017年停止了至强融核的开发。然而，为其开发的许多架构特性已经渗透到主流桌面和服务器计算处理器设计中。
1.3.4 AMD 的 Epyc Rome：利用更小的芯片进行扩展
在 CPU 或 GPU 芯片封装内塞入越来越多的计算逻辑是该行业的驱动原则。这导致芯片的表面积变得巨大。尽管 7 纳米工艺和即将推出的 5 纳米节点工艺不断发展。例如，英特尔 8086 CPU 是 20 世纪 80 年代微型计算机的热门选择，采用 3 微米（3000 纳米）工艺制造，表面积为 16 平方毫米。相比之下，采用 10 纳米工艺制造的集成显卡的英特尔 Ice Lake CPU，表面积约为 122 平方毫米。反过来，更大的芯片往往会产生更多的制造缺陷，从而降低良率（生产的良品率与缺陷品率），并推高价格。
AMD 于 2017 年提出了解决这个问题的解决方案，即用于生产第一代 Epyc Naples CPU 的多芯片模块 (MCM：multi-chip module)。MCM CP 不是将所有逻辑都集成在一块硅芯片上的单片 CPU，而是由多个较小的芯片（小芯片）连接在一起，以提供预期的全部功能。由于芯片体积小，因此可以实现更高的良率。此外，它们还可以以不同的配置连接，从而构成不同功能和价位的 CPU。
2019 年底发布的第二代 Epyc CPU 令人耳目一新：7742 型号在单个封装中集成 64 个核心和 256 MB 三级缓存，基本主频为 2.25 GHz，最高可加速至 3.4 GHz。每个芯片的正式名称是核心复合体 (CCD)，它包含两个核心复合体 (CCX) 部分。每个 CCX 包含四个 Zen2 核心、它们各自的专用二级缓存以及它们共享的三级缓存。
实际上，这种设计使用片上系统 (SoC) 来实现过去多路服务器平台复杂且昂贵的电路。虽然从技术上讲这是一个单 CPU 封装，但存在不相交的 L3 缓存，这意味着数据缓存局部性是线程布局的重要决策因素。因此，该芯片可以在软件中以四种不同的方式配置为 NUMA 平台，从将整个 CPU 视为单个 NUMA 域（即，好像所有节点都以相同的成本访问所有可用内存），到将其分成每个 CCX 一个 NUMA 域，总共 16 组四个核心。
1.3.5 富士通 A64FX：计算和内存集成
富士通的 A64FX 是一款基于 ARM 的处理器，为本文撰写时世界上最强大的机器——日本的富岳（Fugaku）提供动力。 A64FX 通过以下方式实现如此高的性能：(a) 实现带有 512 位可扩展矢量扩展指令集 (SIMD 指令，类似于英特尔的 AVX)；更重要的是，(b) 将 CPU 与 32 GiB 的 HBM2 内存紧密集成，能够为核心提供 1 TiB/秒的带宽（每个 HBM2 模块 256 GiB）。这种方法类似于 NVidia A100 加速器的内存连接方式，但这并非该 CPU 与当代 GPU 的唯一相似之处。A64FX 由四个核心内存组 (CMG) 组成，总共提供 52 个核心 。每个 CMG 包含 12 个计算核心和一个辅助核心，后者负责执行操作系统任务（例如 I/O 等）。由于每个 CMG 直接连接到 HBM2 模块，因此无需使用 L 缓存，从而节省了硅片空间和运行所需的能耗。四个 CMG 模块通过网络内部连接，其连接方式与之前的 Cell BE 和 Xeon Phi 类似。
内存和 CPU 共享多核意味着存储器容量和速度不再是设计能力或关注点，而是在速度、能效、散热和封装方面具有巨大优势，而这些因素都是惠普设备的关键因素。
1.4 性能指标
推动多核硬件和软件开发的动机是提取更高的性能：更短的执行时间、更大的问题和数据集等。显然，需要一个或多个客观标准来评估这些努力的有效性或益处。
至少，并行程序应该能够在执行时间方面胜过其顺序程序（但这不是每次都能拿到银行的东西）。执行时间的提升通常以加速比 (speedup) 来表示，其正式定义为以下比率：
其中，t-seq 是顺序程序的执行时间，t-par 是并行程序的执行时间，用于解决同一问题实例。
tseq 和 tpar 均为实际时间，因此并非客观数据。它们可能受以下因素影响：
[*]编写实现的程序员的技能 •
[*]编译器的选择（例如，GNU C++ 与 Intel C++） •
[*]编译器开关（例如，打开/关闭优化） •
[*]操作系统
[*]保存输入数据的文件系统类型（例如，EXT4、NTFS 等） •
[*]时间（不同的工作负载、网络流量等）。
为了对报告的加速比数据有一定程度的信心，应遵循以下规则：
[*]所有程序（顺序和并行）都应在相同的软件和硬件平台上，并在类似的条件下进行测试。
[*]顺序程序应是已知问题中最快的解决方案。
第二个要求是两者中最不明显的，但却是一个至关重要的要求：并行算法与顺序算法完全不同。事实上，顺序算法可能没有并行派生算法。甚至并行派生算法根本不可能被创建。第二个要求背后的原因是一个根本性的原因：实现并行程序所需的大量工作（就开发成本而言，高昂的工作量）只有在能够带来切实的收益时才是合理的。
对于给定数量的处理器，并行算法提供的加速比仍然会根据输入数据而变化。因此，通常在对大量相同规模的输入测试两个程序后，报告其加速比的平均值，或者甚至报告观察到的平均值、最大值和最小值。
加速比仅能说明部分问题：它可以告诉我们加速问题的求解是否可行，例如，加速比是否大于 1。它无法告诉我们是否可以高效地完成求解，即是否可以使用少量资源。为此目的采用的第二个指标是效率。效率的正式定义为以下比率：
其中，N 是用于执行并行程序的 CPU/核心数量。效率可以理解为并行执行期间节点被利用时间的平均百分比。如果效率等于 100%，则意味着加速比为 N，工作负载在 N 个处理器之间平均分配，这些处理器的利用率为 100%（执行期间从不空闲）。当加速比 = N 时，相应的并行程序表现出所谓的线性加速。
遗憾的是，这只是理想情况。当多个处理器共同努力实现某个目标时，它们需要花时间相互协调，无论是图 1.1 (a) 加速比曲线，还是 (b) 效率曲线，它们都用于在多核 CPU 上通过可变数量的线程执行并行积分计算。每条曲线对应于 x 范围的不同划分数（如图例所示）。(a) 中的理想加速比线衡量了性能下降，这是协调成本增加的一个常见问题。通过交换消息或处理共享资源。与活动相关的协调会占用 CPU 时间，最终导致加速比低于 N。
下图展示了一个示例程序的加速比和效率曲线，该程序通过应用梯形规则算法计算函数的定积分。
计算负载由计算中使用的梯形数量控制。结果是在 i7 950 四核 CP 上获得的，并且是 10 次运行的平均值。对于谨慎的读者来说，这里有一个矛盾之处：如果我们只有四核 CPU，如何测试和报告八个线程的加速比？i7 950 四核 CPU 支持一种称为超线程的技术，6 该技术允许一个 CPU 内核通过复制CPU 硬件的各个部分。启用此功能的 CPU 看起来拥有实际两倍的物理核心数。遗憾的是，性能平均只提高了 30%，与建议的两倍提升相差甚远。因此，上图报告的结果存在偏差，因为在给定平台上，我们并没有 8 个不同的物理 CPU 来运行 8 个线程。
然而，随着线程数增加，效率下降并非偶然：这是并行应用程序的典型行为，尽管下降程度因应用程序而异。这一切都归结于我们通常所说的协调成本，而这只有在更多参与方/CPU 相互通信时才会增加。超线程是英特尔创造的一个营销术语，指的是所谓的硬件线程。
上图有两个用途：(a) 它展示了典型的速度和效率曲线；(b) 它提高了人们对正确实验技术的认识。衡量性能应该涉及真实的硬件资源，而不是超线程提供的虚拟资源。
上图中的理想加速曲线衡量了并行程序的成功程度。正如我们提到的，这是性能的上限。但并非总是如此！在某些情况下，加速比 > N，效率 > 1，这被称为超线性加速场景。根据我们对效率的解释，这似乎是不可能的。然而，我们应该记住，顺序程序和并行程序以不同的方式处理其输入数据，遵循不同的执行路径。因此，如果程序的目标是在搜索空间中获取某个对象，那么并行程序可能只需遵循不同的路径即可比所用计算资源数量所暗示的更快地达到这一点。
加速比涵盖了并行解决方案的有效性：它是否有用？效率是衡量资源利用率的标准：我们投入的计算资源所能提供的潜力有多少被实际利用？效率低表明设计不佳，或者至少需要进一步改进。
最后，我们想知道并行算法在计算资源和/或问题规模增加时的表现如何：它是否具有可扩展性？
通常，可扩展性是指（软件或硬件）系统高效处理不断增长的工作量的能力。在并行算法和/或平台的背景下，可扩展性转化为能够 (a) 解决更大的问题和/或 (b) 整合更多的计算资源。
有两个指标用于量化可扩展性：强扩展效率（与 (b) 相关）和弱扩展效率（与 (a) 相关）。强扩展效率的定义与公式 (1.2) 中定义的通用效率相同：
它是用于解决与单个处理器相同问题的处理器数量 N 的函数。
弱扩展效率同样是用于解决处理器数量 N 的函数：
其中 t′par 是解决比单个机器解决时间 tseq 大 N 倍的问题所需的时间。
有许多当涉及 GPU 计算资源时，计算扩展效率时存在一些问题：应该使用多少 N 值？GPU 通常拥有数百或数千个核心，但将单个 GPU 核心上的执行时间报告为 tseq 会显得笨拙或不科学。如果我们选择将单个 CPU 核心的执行时间报告为 tseq，那么在计算效率时，我们是否应该将 GPU 核心总数作为 N？此外，GPU 是托管设备，即它需要一个 CPU 代表其执行 I/O。这个 CPU 算数吗？
显然，在这种情况下，效率可以通过多种不同的方式计算。为了避免争议，我们仅报告涉及异构平台的案例研究中的加速比数据。
参考资料
[*]软件测试精品书籍文档下载持续更新 https://github.com/china-testing/python-testing-examples 请点赞，谢谢！
[*]本文涉及的python测试开发库 谢谢点赞！ https://github.com/china-testing/python_cn_resouce
[*]python精品书籍下载 https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
[*]Linux精品书籍下载 https://www.cnblogs.com/testing-/p/17438558.html
[*]python八字排盘 https://github.com/china-testing/bazi
[*]联系方式：钉ding或V信: pythontesting
1.5 预测和测量并行程序性能
构建并行应用程序比构建其对应的顺序应用程序更具挑战性。程序员必须解决协调问题，例如如何正确访问共享资源、负载平衡问题（即如何在可用计算资源之间分配工作负载以最小化执行时间）、终止问题（即以协调的方式暂停程序）等等。
只有当应用程序能够通过加速问题解决方案真正受益时，才应该尝试进行此类尝试。开发成本决定了我们不能仅仅实现多个备选设计并进行测试以选出最佳方案，或者更糟的是，评估项目的可行性。对于最简单的问题来说，这或许是可行的，但即使如此，如果我们能够先验地确定最佳的开发路线，那就更好了。
问题的并行解决方案的开发始于其串行变体的开发！这听起来似乎自相矛盾，但请尝试回答这些问题：如果我们没有串行解决方案可以比较，我们如何知道并行解决方案的速度有多快？我们需要一个基准，而这只能通过顺序解决方案获得。此外，我们如何检查并行程序生成的解决方案是否正确？顺序程序的输出并不能保证正确，但使其正确要容易得多。
顺序算法和相关程序的开发也可以为并行化设计提供重要的参考。
这是一个实际问题，因为我们需要回答以下与并行程序的可行性和成本效益相关的问题：
[*]程序中最耗时的部分是什么？这些部分应该是并行执行的主要候选。
[*]一旦确定了这些部分并假设它们可以并行化，可以预期获得多少性能提升？
这里需要澄清的是：所需的顺序程序并非只是解决同一问题的任何顺序程序。它必须是被并行化的同一算法的顺序实现。例如，如果我们需要并行排序数据，那么适合并行实现的算法是桶排序。桶排序的顺序实现可以帮助预测并行性能，并找出算法中最耗时的部分。快速排序的顺序实现可以提供基准性能信息，但它无法解决上述两个问题。
一旦实现了顺序版本，我们就可以使用性能分析器来回答这些问题。性能分析器是一种工具，可以收集有关程序各部分调用频率、调用持续时间以及内存使用量的信息。性能分析器使用多种不同的技术来执行其任务。最常用的技术是：
[*]仪表化：修改被分析程序的代码，以便收集信息，例如，在执行任何指令之前增加一个特殊计数器。这会产生非常准确的信息，但同时也会大大增加执行时间。此技术需要重新编译目标程序。
[*]采样：目标程序的执行会被定期中断，以便查询正在执行的函数。显然，这种方法的准确性不如仪表化。虽然需要进行插桩，但程序不需要重新编译，执行时间也仅会受到轻微影响
下图为kcachegrind 的示例屏幕截图，显示了顺序桶排序实现的分析结果，该实现在桶较小时会切换到快速排序。
valgrind 分析工具集合包含一个基于插桩的分析器。插桩在分析之前执行，这意味着无需用户干预。这是一个调用示例：
$ valgrind --tool=callgrind ./bucketsort 1000000其中 ./bucketsort 1000000 是待分析的程序及其参数。分析结果文件名为“callgrind.out”，其中包含分析结果。分析结果可以通过 kcachegrind 等前端程序进行可视化。
经验和对问题领域的深入了解是宝贵的资源，它们可以帮助人们精准定位需要并行化的“热点”，而无需对顺序程序进行性能分析。
然而，性能分析器可以帮助我们回答上面提出的第二个问题，即我们可以从并行解决方案中获得多少潜在性能。传统上，这是通过近似数学模型来实现的，这些模型使我们能够捕捉待执行计算的本质。这些模型的参数可以通过对顺序应用程序进行性能分析来估算。在下一节中，我们将描述基于这种简单模型的阿姆达尔定律。
无论数学模型的性能预测如何，出于两个原因，必须对已实施的并行设计进行实际测试：正确性和性能。必须验证并行实现的正确性。并行程序的行为可能具有不确定性，因为以未指定的顺序发生的事件可能会影响计算结果。除非事先计划，否则不确定性是一种不良特性，如果存在，必须根除。此外，测试还可以揭示原始设计的缺陷或需要解决的性能问题。
以下列表包含执行正确实验程序的准则：
[*]除非另有明确说明，否则应测量整个执行的持续时间。例如，如果仅要并行化程序的一部分，则只能针对执行时间线的特定部分计算速度和效率。然而，总体时间可以用来衡量并行解决方案的影响及其是否具有成本效益。例如，一个程序解决问题需要 100 秒，如果其中 10% 的部分以 100 倍的速度执行，仍然需要 90 多秒。
[*]结果应以多次运行的平均值形式报告，可能包含标准差。运行次数因应用而异，例如，将一个持续 3 天的实验重复 100 次，并且对于许多不同的场景来说，这是完全不现实的。然而，为了解决这个问题，三次运行的平均值只能产生不可靠的统计数据。因此，必须谨慎权衡。
[*]异常值（即过大或过小的结果）应从平均值计算中排除，因为它们通常表示异常情况（例如，主内存耗尽或机器工作负载发生变化）。然而，应给出理由，以免不利结果被一笔带过，而只加解释。
[*]可扩展性至关重要，因此应报告各种输入规模（理想情况下涵盖实际数据的大小和/或质量）和各种并行平台规模的结果。
[*]测试输入应从非常小到非常大不等，但如果可以识别，则应始终包含生产环境中典型的问题规模。
[*]当使用多核机器时，如果要计算效率，线程和/或进程的数量不应超过可用的硬件核心数量。超线程是一种特殊情况，因为这项技术使CPU在操作系统看来拥有实际核心数量的两倍（或更多）。然而，这些逻辑核心与满负荷核心的能力并不匹配。因此，尽管操作系统可能报告例如八个核心的可用性，但相应的硬件资源并不存在，这实际上损害了任何可扩展性分析。理想情况下，为了衡量可扩展性，应该禁用超线程，或者将线程数限制为硬件核心数。
在某些情况下，线程数多于核心数是有利的：如果某些线程因某种原因阻塞，其余线程仍然可以利用 CPU。但是，在计算效率时，N 应该是核心数，而不是线程/进程数。为了在不经历昂贵的并行程序实现和测试步骤的情况下预测并行性能，提出了以下章节中描述的两条定律。尤其是阿姆达尔定律，尽管已被证明存在缺陷，但仍然具有影响力。
1.5.1 阿姆达尔定律
1967 年，吉恩·阿姆达尔 (Gene Amdahl) 设计了一个简单的思想实验，用于推导并行程序可以预期的性能优势。阿姆达尔假设：
[*]顺序应用程序，在单个 CPU 上执行需要 T 时间。
[*]该应用程序由 0 ≤ α ≤ 1 个可并行的部分组成。剩余的 1 − α 必须顺序执行。
[*]并行执行不会产生通信开销，并且可并行化的部分可以在任意数量的 CPU 之间平均分配。此假设尤其适用于多核架构，因为这些架构中的内核可以访问相同的共享内存。
基于上述假设，N 个节点获得的加速比应该有上限：
因为我们忽略了任何分区/通信/协调成本。如果我们获得 N → ∞ 的极限，则等式 (1.5) 也可以给出最大可能的加速比：
上面以简单易记的形式解决了一个难题：并行程序能将问题解决得快多少？而且，它以一种完全抽象的方式进行计算，没有考虑计算平台的特性。它仅依赖于问题的特性，即 α。显而易见的是，预测的加速比受到严重限制。即使对于较小的 α 值，最大加速比也很低。例如，如果 α = 0.9，则无论使用多少处理器来解决问题，加速比都小于 10。
阿姆达尔定律有一个有趣的推论，这或许就是它被提出的动机。阿姆达尔定律是在小型计算机问世的时代制定的。小型计算机比当时占主导地位的大型机便宜得多，但性能也较弱。图 1.1 不同 α 值下的加速曲线，即应用程序中可以并行化的部分，正如阿姆达尔定律所预测的那样。
1.5.2 Gustafson–Barsis 的反驳
阿姆达尔定律存在根本性缺陷，因为它已被反复证明无法解释经验数据：并行程序通常会超出预测的加速极限。
最终，在阿姆达尔定律发表二十年后，Gustafson 和 Barsis 终于从正确的角度审视了这个问题。
并行平台的作用不仅仅是加快顺序程序的执行速度。它可以容纳更大的问题实例。因此，与其考察并行程序相对于顺序程序的性能，不如考察如果顺序机器需要解决并行程序能够解决的相同问题，其性能会如何。
假设：
[*]我们有一个并行应用程序，在 N 个 CPU 上执行需要 T 时间。
[*]该应用程序在所有机器上运行的总时间中，0 ≤ α ≤ 1。剩余的 1 − α 必须顺序执行。
在顺序机器上解决同一问题需要的总时间为：
Tseq = (1 − α)T + N · α · T
那么加速比为：
https://img2024.cnblogs.com/blog/3174021/202508/3174021-20250806143335829-738357366.png
相应的效率为：
当 N 趋于无穷大时，效率的下限为 α。
上图所示的加速曲线完全忽略了通信成本，结果显然过于理想化，但潜力确实存在。
下图的效率曲线仍然乐观。即使 α = 50%，在最多 16 个 CPU 的情况下，效率也不会低于 50%。这简直好得令人难以置信。即使对于所谓的高度并行问题，随着 N 的增加，通信开销也会成为一个决定性因素，导致加速增益降低，效率骤降。一般来说，在实践中获得 90% 以上的效率，我认为是一项值得称道的成就。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]