跳转至

Parallel Processors

Introduction

通过简单的将更小的计算机进行连接以创造出更强性能的计算机是多处理器(multiprocessor)的设计思路。如果软件能够高效利用多处理器，那么将一个大型的低效的处理器替换为多个高效的小型处理器可以获得更好的性能。因此，多处理器软件必须能够在可变数量的处理器上正常运行。

对于相互独立的任务，高性能意味着高吞吐量，称为任务级并行或者进程级并行。这些任务通常是同时运行在多个处理器上的单一程序，被称为并行处理程序(parallel processing program)

为了避免重复，多处理器通常被称为多核微处理器而不是多处理器微处理器，多核芯片中的处理器被称为核(core)。这些多核处理器通常都是共享内存处理器(shared memory processor, SMP)，因为它们总是共享一个物理地址空间

下图展示了串行(serial)、并行(parallel)、顺序(sequential)和并发(concurrent)之间的差异

从图中可以看出，顺序程序和并发程序既可以运行在串行硬件上，也可以运行在并行程序上

并发变革的主要挑战不是使顺序程序在并行硬件上获得更高性能，也是使并发程序在多处理器上获得更高性能

The Difficulty of Creating Parallel Processing Program

并发的挑战不在于硬件，而在于编写一个使用多处理器更快的完成一个任务的软件，并且这个问题还会随着处理器数量的增加变得愈发困难。我们必须能够通过运行在多处理器上的并行进程获得更好的性能或能耗，否则编写并行程序是没有意义的。

并行程序的挑战主要包括：调度，将任务划分为并行的部分，平衡不同处理器之间的加载，同步以及在不同部分之间进行交流

下面我们通过 Amdahl 定理推导出并行程序相较于串行程序的加速比

\[ \begin{aligned} &\text{Execution time affected after improvement}=\\ &\frac{\text{Execution time affected by improvement}}{\text{Amount of improvement}} +\text{Execution time unaffected} \end{aligned} \]

对上面的式子做一些变换

\[ \text{Speed-up}=\frac{\text{Execution time before}}{\text{(Execution time before - Execution time affected)}+\dfrac{\text{Execution time affected}}{\text{Amount of improvement}}} \]

分子分母同时除以 \(\text{Execution time before}\) 可以得到

\[ \text{Speed-up}=\frac{1}{(1-\text{Execution time affected)}+\dfrac{\text{Fraction time affected}}{\text{Amount of improvement}}} \]

在保持问题规模不变的情况下获得一个更好的加速比的难度大于增大问题的规模的情况

因此，可以引出两个相关概念

  • 强扩展(strong scale):在保持问题规模不变的情况下测得的加速比
  • 弱扩展(weak scale):在问题规模随着处理器数量成比例变化的情况下测得的加速比

假设问题的规模为 \(M\) ，处理器的数量为 \(P\) ，那么每个处理器的强扩展近似为 \(M/P\) ，而弱扩展近似为 \(M\)

需要注意的是，存储器层级结构可能会对弱扩展比强扩展更简单的传统观念造成影响

SISD, MIMD, SIMD, SPMD, and Vector

可以按照指令流和数据流的数量对并行处理器进行分类，如下图所示

一个传统的单核处理器具有单个指令流和单个数据流(single instruction stream, single data stream, SISD)，而一个传统的多核处理器具有多个指令流和多个数据流(multiple instruction streams,multiple data streams, MIMD)

单个程序通常会运行在一个 MIMD 计算机的所有处理器上，不同的处理器通过条件语句执行不同的代码，这被称为单程序多数据(single program multiple data, SPMD)

最接近多指令流单数据流(MISD)的处理器在单数据流上以流水线方式执行一系列计算。相比之下，与 MISD 相反的类型SIMD(Single Instruction stream, Multiple Data streams)则对数据向量进行操作

SIMD 的一个好处是所有并行的执行单元全都是同步的，它们都响应由同一程序计数器(PC)中发出的同一指令。除此之外，使用 SIMD 还可以摊销多个执行单元的控制成本，减少指令带宽和空间

虽然每个单元都执行相同的指令，但每个执行单元有独立的地址寄存器，可以使用不同的数据地址

SIMD 在相同的数据结构上表现良好，例如使用 for 循环处理数组；在每个执行单元必须执行不同的操作时表现欠佳，例如 switch-case 语句

Multimedia Extensions

x86指令集通过多媒体扩展指令(multimedia extensions, MMX)的方式实现 SIMD ，窄整数的子字并行最早是受到了 x86的 MMX的启发。随着摩尔定律持续发挥作用，越来越多的指令被添加，从最早的 SSE 到现在的 AVX 。其中AVX 支持同时处理8个64位的浮点数

Vector

一个更古老但是更优雅的实现 SIMD 的方式是向量(vector architecture)，其采用流水线化的 ALU，从而以更低的功耗获得良好的性能。

向量的基本原理是从内存中收集数据元素，将数据按顺序放在一大组寄存器中，使用流水线执行单元顺序操作寄存器中的数据，将结果写回内存。向量的核心特性是一组向量寄存器

Vector and Scalar

对于 DAXPY(double precision \(a \times X\) plus \(Y\))循环 $$ Y=a\times X+Y $$ 其中 \(X\) 和 \(Y\) 是64位双精度浮点数的向量，初始时位于内存中；\(a\) 是一个双精度的标量。假设 \(X\) 和 \(Y\) 的起始地址分别位于 x19 和 x20 对比一下传统的 RISC-V 代码和向量化的 RISC-V 代码

        fld     f0, a(x3)       // load scalar a
        addi    x5, x19, 512    // end of array X
loop:   fld     f1, 0(x19)      // load x[i]
        fmul.d  f1, f1, f0      // a * x[i]
        fld     f2, 0(x20)      // load y[i]
        fadd.d  f2, f2, f1      // a * x[i] + y[i]
        fsd     f2, 0(x20)      // store y[i]
        addi    x19, x19, 8     // increment index to x
        addi    x20, x20, 8     // increment index to y
        bltu    x19, x5, loop   // repeat if not done

    fld         f0, a(x3)       // load scalar a
    vsetvli     x0, x0, e64     // 64-bit-wide elements
    vle.v       v0, 0(x19)      // load vector x
    vfmul.vf    v0, v0, f0      // vector-scalar multiply
    vle.v       v1, 0(x20)      // load vector y
    vfadd.vv    v1, v1, v0      // vector-vector add
    vse.v       v1, 0(x20)      // store vector y

向量处理器极大减少了动态指令的带宽，只需要执行7条指令，而传统的 RISC-V 指令则需要超过500条；另一个差异是使用向量减少了流水线冒险的频率

Vector versus Scalar

与传统指令相比向量指令（标量）有以下几个优点：

  • 一个向量指令等价于一个完整的循环，取值和解码所需的带宽极大地减少
  • 向量中每一个结果的计算与同一向量中其他结果的计算是独立的，因此不需要检查向量指令内的数据冒险
  • 当程序中存在数据级并行时，相比使用 MIMD 多处理器，使用向量体系结构和编译器的组合更容易写出高效的应用程序
  • 只需要检查两条向量指令之间的向量操作数是否会发生数据冒险，这将减少检查的次数从而节省能耗和时间。
  • 访问存储器的向量指令具有确定的访问模式。如果向量中的数据元位置都是连续的，则对整个向量而言，主存储器的延迟开销只有一次，而不是对向量中的每个字都产生一次。
  • 因为整个循环被具有已知行为的向量指令所取代，所以通常由循环引发的控制冒险不再存在。
  • 与标量体系结构相比，节省的指令带宽和冒险检查以及对存储器带宽的有效利用，使得向量体系结构在功耗和能耗方面更具有优势

由于以上的原因，对于同样数量的数据，向量操作比一系列标量操作更快

Vector versus Multimedia Extension

向量和 MMX 主要有以下几点不同：

  1. 向量指令可以指定几十种操作，而 MMX只能表示几种操作
  2. 向量操作的元素个数存放在一个单独的寄存器中，而不是像 MMX 放在 opcode 中
  3. 向量的数据不需要是连续的，其支持步长访问，即加载内存中的每隔 \(n\) 的元素的数据和索引访问，即按照数据项的地址将数据加载到向量寄存器中，也称为聚集-散射(gather-scatter)

与 MMX类似，向量可以支持多种不同的数据宽度，可以使向量操作处理 32 个 64位数据、64 个 32 位数据、128 个 16 位数据或者 256 个 8 位数据。向量指令的并行特性可以使其采用深度流水线的功能单元、并行功能单元阵列或者并行功能单元与流水功能单元的组合来执行这些操作。下图展示了如何通过并行流水线来提高向量加法的性能

向量算术操作通常只允许一个向量寄存器的 \(N\) 个元素与另一个向量寄存器的 \(N\) 个元素进行运算，这使得我们可以将并行向量单元构建为多个并行的向量通道(vector lane)，下图展示了四通道向量单元的结构

为了利用多通道，应用程序和体系结构都必须支持长向量。否则，指令将很快执行完毕以至于没有足够的新指令可以被执行，可以使用指令级并行技术为向量单元提供足够的向量指令

向量的缺陷

向量寄存器巨大的状态会增加上下文切换的时间，加大处理向量加载和存储中的页错误的难度 。除此之外 SIMD 指令已经实现了向量指令的部分优点

Hardware Multithreading

硬件多线程是一个与 MIMD 相关的概念

评论