并行计算（二）

并行计算中的粒度

一个程序有多少并行度？事实上，大部分指令都可以并行执行，但我们要考虑并行后的代价：并行后程序是否变得简单？以及并行后加速效率是否明显等问题。

本节的讨论主要是在概念层面上进行的；后面将详细介绍如何对并行进行实际编程。

数据并行化

对于有简单主体循环的程序来说，遍历大数据集的操作相当常见。

  1. for (i=0; i<1000000; i++)
  2.      a[i] = 2*b[i];

这样的代码被认为是「数据并行」（data parallelism）或「细粒度并行」（fine-grained parallelism）的一个实例。如果我们有和数组元素一样多的处理器，那么并行后的代码将非常简单：每个处理器将在其本地数据上执行

  1. a = 2*b

如果代码主要由数组的循环组成，它可以在所有处理器锁步的情况下有效执行。基于这种思想设计的并行架构早已存在，事实上处理器只能以锁步方式工作。这种数组上的完全并行操作出现在计算机图形学中，图像的每个像素都被独立处理。因此，GPU的并行就是基于数据并行的。

继续上面的例子，考虑以下操作 $$ \textbf{for} \quad 0\leqslant i \leqslant max \quad \textbf{do}\ i{left} = mod(i-1, max)\ i{right} = mod(i+1, max)\ ai = (b{i{left}}+b{i_{right}})/2 $$ 在数据并行机器上，可以实现为 $$ bleft \leftarrow \textbf{shiftright(b)}\ bright \leftarrow \textbf{shiftleft(b)}\ a\leftarrow (bleft+bright)/2 $$

其中shiftleft/right指令导致一个数据项被发送到数字较低或较高为1的处理器。 为了使第二个例子有效，有必要使每个处理器能够与其近邻快速通信，并使第一个和最后一个处理器彼此通信。

在各种情况下，如图形中的 “模糊 “操作，对二维数据的操作是有意义的。 $$ \textbf{for} \quad 0< i < m \quad \textbf{do}\ \quad \quad \quad \quad \textbf{for} \quad 0< j< n \quad \textbf{do}\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad a{ij}\leftarrow (b{ij-1}+b{ij+1}+b{i-1j}+b_{i+1j}) $$ 因此，处理器必须能够将数据移动到二维网格中的相邻处。

指令级并行

在ILP中，并行性仍然是在单个指令的层面上，但这些指令不一定是相似的。例如，在 $$ a\leftarrow b+c\ d\leftarrow f *f $$ 这两个赋值是独立的，因此可以同时执行。编译器可以帮助我们处理这种并行。事实上，识别ILP对于从现代超标量CPU中获得良好的性能至关重要。

任务并行

数据和指令级并行的另一种应用为「任务并行」（task parallelism），是指可以并行执行的整个子程序。例如，在树形数据结构中的搜索可以按以下方式实现。

  1. if optimal (root) then 
  2.   exit
  3. else
  4.   parallel: SearchInTree (leftchild),SearchInTree (rightchild)
  5.     Procedure SearchInTree(root)

这个例子中的搜索任务是不同步的，而且任务数量也不固定。在实际应用中，任务过多并不是一个很好的策略，因为处理器只在一个任务上工作时其效率才最高。上面的例子可以略加改写为：

  1. while there are tasks left do
  2.   wait until a processor becomes inactive; 
  3.   spawn a new task on it

(之前的两个伪代码之间有一个微妙的区别。在第一个代码中，任务是自我调度的：每个任务都会衍生出两个新的任务。第二个代码是一个Manager-Worker Paradigm的例子：一个贯穿整个程序执行过程的中心任务负责派生和分配节点任务。）

与数据并行不同，该方案中数据对处理器的分配不是事先确定的。因此，这种并行模式最适合于线程编程，例如通过OpenMP库的并行。下面考虑另一个高度任务并行的例子：

在最简单的情况下，一个有限元网格是覆盖二维物体的三角形的集合。由于应该避免过于尖锐的角度，「Delauney网格细化」（Delauney mesh refinement）过程可以选择某些三角形，用形状更好的三角形取代它们。图2.9说明了这一点：黑色的三角形违反了一些角度条件，所以要么它们自己被细分，要么它们与一些相邻的三角形（呈现为灰色）连接，然后共同被重新细分。

delauney

伪代码参考如下。

  1. Mesh m = /* read in initial mesh */ 
  2. WorkList wl; 
  3. wl.add(mesh.badTriangles()); 
  4. while (wl.size() != 0) do
  5.   Element e = wl.get(); //get bad triangle 
  6.   if (e no longer in mesh) continue; 
  7.   Cavity c = new Cavity(e);
  8.   c.expand();
  9.   c.retriangulate(); 
  10.   mesh.update(c); 
  11.   wl.add(c.badTriangles());

很明显，该算法是由一个必须在所有进程之间共享的工作列表（或任务队列）数据结构驱动的。再加上动态分配数据给进程，这意味着这种不规则的并行性适合于共享内存编程，而在分布式内存中则较难做到。

高度并行

单处理器的计算通常需要在众多不同的输入上进行。如果计算的数据不存在相关依赖，且不需要任何特定情况，则被称为「高度并行」（embarrassingly parallel）或「便捷并行」（conveniently parallel）计算。这种并行可以发生在几个层面。在诸如计算Mandelbrot set或评估国际象棋游戏中的棋子的例子中，一个子程序级别的计算被调用了许多参数值。在一个更粗略的层面上，可能是一个简单的程序需要对许多输入进行运行。在这种情况下，整体计算被称为「参数扫描」（parameter sweep）。

中粒度的数据并行化

上述数据并行假定了有与数据元素同样多的处理器。在实际中，处理器内存通常会很大，且处理的数据数量要远远大于处理器数量。因此，数组被分组到子数组的处理器上。伪代码如下

  1. my_lower_bound = // some processor-dependent number
  2. my_upper_bound = // some processor-dependent number
  3. for (i=my_lower_bound; i<my_upper_bound; i++)
  4. // the loop body goes here

这种模式有数据并行的特点，因为在大量的数据项上执行的操作是相同的。它也可以被看作是任务并行，因为每个处理器执行的代码部分较大，而且不一定对同等大小的数据块进行操作。

任务粒度

在前面的小节中，我们考虑了寻找并行工作的不同层次，或者说划分工作的不同方式，以便找到并行性。还有另一种方法：我们将并行方案的「粒度」（granularity）定义为一个处理元素在不得不与其他处理元素进行通信或同步之前可以执行的工作量（或任务大小）。

在ILP中，我们处理的是非常细粒度的并行，就像一条指令或几条指令一样。在真正的任务并行中，颗粒度要粗得多。

有趣的是，我们可以自行选择数据并行中的任务大小。SIMD机器上，我们选择的是单指令粒度，但操作可以被分为中等大小的任务。因此，在处理器数量和总问题规模之间的适当平衡下，数据并行的操作可以在分布式内存集群上执行。

练习 2.18 讨论为一个数据并行操作选择合适的粒度，如在二维网格上进行平均化。表明存在一个表面到体积的效应：通信量比计算量低一阶。这意味着，即使通信比计算慢得多，增加任务量仍然会得到一个平衡的执行。

如果试图加大任务规模以减小通信开销，则会导致另一个问题：集合操作时可能会有不同运行时间的任务，导致负载不均衡。一种解决办法是使用过度分解：创建比处理元素更多的任务，并将多个任务分配给一个处理器（或动态分配任务）以平衡不规则的运行时间。这就是所谓的「动态调度」（dynamic scheduling）。

并行编程

并行编程比串行编程更复杂。虽然对于后者来说，大多数编程语言的操作原理是相似的（除了一些例外，如函数式语言或逻辑语言），但有多种方法来处理并行问题。让我们来探讨一下其中的一些概念和实际问题。

并行编程的策略有多种。我们很难做出一个能自动将串行程序转变为并行程序的编译器。除了弄清楚哪些操作是独立的问题之外，最主要的问题是，在并行环境中定位数据的问题是非常困难的。编译器需要考虑整个代码，而不是一次一个子程序。

较为有效的方法是：用户编写串行程序，同时给出哪些计算可以并行化或数据改如何分配的指示。明确指出操作的并行性是在OpenMP中进行的；指出数据分布并将并行性留给编译器和运行时是PGAS语言的基础。这种方法在共享内存中效果最好。

到目前为止最难的并行编程方式，同时也是实际中效果最好的并行方式，就是把一切留给程序员，让程序员管理一切。这种方法在分布式内存编程的情况下是必要的。

线程并行

我们将简要介绍一下 “线程”。为了解释什么是「线程」（thread），我们首先需要从技术上了解什么是「进程」（process）。一个unix进程对应于对应于单个程序的执行。因此，它在内存中拥有

  • 程序代码，以机器语言指令的形式存在。

  • 「堆」（heap），包含malloc创建的数组。

  • 「栈」（stack），包含快速变化的信息，如「程序计数器」（program counter，PC），它显示了当前正在执行的结构。堆栈中包含快速变化的信息，如表明当前正在执行的程序计数器，以及具有本地范围的数据项，以及计算的中间结果。

这个过程可以有多个线程；这些线程的相似之处在于它们看到相同的程序代码和堆，但它们有自己的栈。因此，一个线程是通过进程执行的一个独立 “股”。

进程可以属于不同的用户，或者是一个用户并发运行的不同程序，因此它们有自己的数据空间。另一方面，线程是一个进程的一部分，因此它们共享进程堆。线程可以有一些私有数据，例如通过拥有自己的数据栈，但它们的主要特征是它们可以在相同的数据上进行协作。

叉形连接机制

线程是动态的，它们可以在程序执行过程中被创建。(这与MPI模型不同，在MPI模型中，每个处理器运行一个进程，它们都是在同一时间创建和销毁的）。当程序启动后，处于活跃状态的线程称为「主线程」（main thread），其他线程通过主线程「生成」（thread spawning）创建，主线程需等待其完成，称为「生成-汇合模型」（fork-join）。从同一个线程生成出来并同时活动的一组线程被称为「线程组」（thread team）。

fork-join

线程的硬件支持

上面所描述的线程是一种软件结构。在并行计算机出现之前，线程是可能的；例如，它们被用来处理操作系统中的独立活动。在没有并行硬件的情况下，操作系统将通过多任务或时间切片来处理线程：每个线程将定期使用CPU的一小部分时间。(从技术上讲，Linux内核通过任务的概念来处理进程和线程；任务被保存在一个列表中，并定期被激活或取消）

这可以导致更高的处理器利用率，因为一个线程的指令可以在另一个线程等待数据时被处理。(在传统的CPU上，线程之间的切换是有些耗费精力的（超线程机制是个例外），但在GPU上则不然，事实上，它们需要许多线程才能达到高性能）。

在现代多核处理器上，有一种明显的支持线程的方法：每个核有一个线程，可以有效地使用硬件的并行执行。共享内存允许线程看到相同的数据，但这也会导致问题。

线程实例

下面的例子，严格来说是在Unix上运行，在Windows上是行不通的，它清楚地说明了fork-join的模型。它使用pthreads库来生成一些任务，这些任务都会更新一个全局计数器。由于线程共享相同的内存空间，它们确实看到并更新相同的内存位置。

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include "pthread.h"
  5. int sum=0;
  7. void adder() {
  8.      sum = sum+1;
  9.      return;
  10. }
  12. #define NTHREADS 50
  13. int main() {
  14.      int i;
  15.      pthread_t threads[NTHREADS];
  16.      printf("forking\n");
  17.      for (i=0; i<NTHREADS; i++)
  18.        if (pthread_create(threads+i,NULL,&adder,NULL)!=0) return i+1;
  19.      printf("joining\n");
  20.      for (i=0; i<NTHREADS; i++)
  21.        if (pthread_join(threads[i],NULL)!=0) return NTHREADS+i+1;
  22.      printf("Sum computed: %d\n",sum);
  23. return 0; }

事实上，这段代码给出了正确的结果，但这是一个巧合：它之所以发生，只是因为更新变量比创建线程要快得多。(在多核处理器上，出错的机会将大大增加)。如果人为地增加更新的时间，我们将不再得到正确的结果。

  1. void adder() {
  2.      int t = sum; sleep(1); sum = t+1;
  3.      return;
  4. }

现在所有的线程都读出了sum的值，等待一段时间（估计是在计算什么），然后再更新。 这可以通过在应该是 “互斥 “的代码区域上设置一个锁来解决。

  1. pthread_mutex_t lock;
  2.    void adder() {
  3.      int t;
  4.      pthread_mutex_lock(&lock);
  5.      t = sum; sleep(1); sum = t+1;
  6.      pthread_mutex_unlock(&lock);
  7.      return;
  8. }
  9.    int main() {
  10.      ....
  11.      pthread_mutex_init(&lock,NULL);

锁定和解锁命令保证了没有两个线程可以干扰对方的更新。关于pthreads的更多信息，请参见例如https://computing.llnl.gov/tutorials/pthreads。

上下文

在上面的例子和它的sleep命令版本中，我们忽略了一个事实，即有两种类型的数据参与其中。首先，变量s是在线程生成部分之外创建的。因此，这个变量是「共享」（shared）的。另一方面，变量t是在每个生成的线程中创建一次的。我们称其为「私有」（private）数据。

一个线程可以访问的所有数据的总和被称为其「上下文」（context）。它包含了私有和共享数据，以及线程正在进行的计算的临时结果。(还包含程序计数器和堆栈指针。如果现在不知道这些是什么，请不用担心）

创建的线程比处理器的内核多是很有可能的，所以处理器可能需要在不同线程的执行之间进行切换。这就是所谓的「上下文切换」（context switch）。

普通的CPU进行上下文切换会造成时间开销，所以只有在线程工作的粒度足够高时，我们才会这样执行。下面几种情况则较为常见

  • 有硬件支持多线程的CPU，通过「超线程」（hyperthreading）或Intel Xeon Phi来实现
  • GPU，它实际上依赖于快速上下文切换。
  • 某些其他 “奇特 “的架构，如Cray XMT。

竞争条件、线程安全和原子操作

共享内存使程序员的工作变得简单，因为每个处理器都可以访问所有的数据：处理器之间不需要明确的数据通信。另一方面，多个进程/处理器也可以写到同一个变量，这是潜在问题的来源。

假设两个进程都试图递增一个整数变量I。

进程1：I=I+2

进程2：I=I+3

如果该变量是一个由独立进程计算的累加，这是一个合法的活动。这两个更新的结果取决于处理器读取和写入变量的顺序。

Three executions of a data race scenario

图2.12说明了三种情况。这种情况下，最终结果取决于哪个线程先执行，被称为「竞争条件」（race condition）或「数据竞争」（data race）。一个正式的定义是：如果有两个语句$S_1$，$S_2$，数据竞争为

  • 两个语句之间不存在因果关系
  • 都是访问一个位置$L$；并且
  • 至少有一个访问是写操作。

这种冲突性更新的一个非常实际的例子是内积计算。

  1.  for (i=0; i<1000; i++)
  2.       sum = sum+a[i]*b[i];

这里的乘积是真正独立的，所以我们可以选择让循环迭代并行进行，例如由它们自己的线程进行。然而，所有的线程都需要更新同一个变量的总和。

无论是串行执行还是线程执行，代码的行为都是一样的，这叫做「线程安全」（thread safe）。从上面的例子可以看出，缺乏线程安全通常是由于对共享数据的处理。这意味着程序越是使用本地数据，它是线程安全的机会就越大。不幸的是，有时线程需要写到共享/全局数据，例如，当程序进行「规约」（reduction）时。

解决这个问题的方法基本上有两种。一种是，我们将共享变量的这种更新宣布为代码的「临界区」（critical section）。这意味着临界区的指令（在内积的例子中，”从内存中读取和，更新，写回内存”）一次只能由一个线程来执行。特别是，它们需要完全由一个线程执行，然后其他线程才能启动它们，所以上面的模糊问题不会出现。当然，上述代码片段非常常见，以至于像OpenMP这样的系统有专门的机制来处理它，把它声明为一个减少操作。

例如，临界区可以通过信号机制[47]来实现。在每个临界区的周围，会有两个原子操作控制着一个信号灯，即一个信号柱。第一个遇到信号灯的进程将降低信号灯，并开始执行临界区。其他进程看到已经降低的信号灯，并等待。当第一个进程完成临界区时，它执行第二条指令，提高信号灯，允许其中一个等待的进程进入临界区。

解决共享数据的共同访问的另一种方法是在某些内存区域设置一个临时「锁」（lock）。如果对临界区的共同执行是可能的，例如，如果它实现了对数据库或哈希表的写入，那么这种解决方案可能是比较好的。在这种情况下，一个进程进入临界区将阻止任何其他进程写入数据，即使他们可能是写入不同的位置；那么锁定被访问的特定数据项是一个更好的解决方案。

锁的问题是，它们通常存在于操作系统层面。这意味着它们的速度相对较慢。由于我们希望上述内积循环的迭代能以浮点单元的速度执行，或者至少以内存总线的速度执行，所以这是不可接受的。

这方面的一个实现是「事务内存」（transactional memory），硬件本身支持原子操作；这个术语来自于数据库事务，它有一个类似的完整性问题。在交易型内存中，一个进程将执行正常的内存更新，除非处理器检测到与另一个进程的更新有冲突。在这种情况下，更新（”事务”）被取消并重新尝试，一个处理器锁定内存，另一个处理器等待锁定。这是一个优雅的解决方案；然而，取消事务可能会带来一定的「流水线冲洗」（pipeline flushing）和缓存线失效的代价。

内存模型和串行一致性

上面提到的竞争条件现象意味着一些程序的结果可能是非确定性的，这取决于指令的执行顺序。还有一个因素在起作用，它被称为处理器和/或语言使用的「内存模型」（memory model）[2]。内存模型控制一个线程或内核的活动如何被其他线程或内核看到。

例如，考虑

初始：A=B=0;，然后

进程1：A=1；x=B。

进程2：B=1；y=A。

如上所述，我们有三种情况，我们通过给出一个全局性的语句序列来描述这些情况。

场景 1. 场景 2. 场景 3.
$A\leftarrow 1$ $A\leftarrow 1$ $B\leftarrow 1$
$x\leftarrow B$ $B\leftarrow 1$ $y\leftarrow A$
$B\leftarrow 1$ $x\leftarrow B$ $A\leftarrow 1$
$y\leftarrow A$ $y\leftarrow A$ $x\leftarrow B$
$x=0, y=1$ $x=1, y=1$ $x=1, y=0$

(在第二种情况下，语句1,2和3,4都可以颠倒过来，但结果不会改变。)

这三种不同的结果可以被描述为是由尊重局部排序的状态要素的全局排序来计算的。这被称为「串行一致性」（sequential consistency）：并行的结果与顺序执行是一致的，该顺序执行将并行计算交错进行，尊重它们的本地语句排序。

保持串行一致性的代价是很昂贵的：它意味着对一个变量的任何改变都需要立即在所有其他线程上可见，或者对一个线程上的变量的任何访问都需要咨询所有其他线程。

在一个「松弛内存模型」（relaxed memory model）中，有可能会得到一个不符合顺序的结果。假设在上面的例子中，编译器决定对两个进程的语句重新排序，因为读写是独立的。实际上，我们得到了第四种情况。

场景 4.
$x\leftarrow B$
$y\leftarrow A$
$A\leftarrow 1$
$B\leftarrow 1$
$x=0, y=0$

导致结果$𝑥=0$，$𝑦=0$，这在上面的串行一致模型下是不可能的。(有寻找这种依赖关系的算法[127])。串行一致意味着

  1. integet n
  2. n=0
  3. !$omp parallel shared(n) n=n+1
  4. !$omp end parallel

效果应该与下述相同

  1. n=0
  2. n = n+1 ! for processor 0 
  3. n = n+1 ! for processor 1
  4. ! et cetera

有了串行一致性，就不再需要声明原子操作或临界区；然而，这对模型的实现提出了强烈的要求，所以可能导致代码的低效。

亲和性

线程编程非常灵活，可以根据需要有效地创建并行性。然而，本书的很大一部分内容是关于科学计算中数据移动的重要性，在线程编程中不能忽视这一方面。

在多核处理器的背景下，任何线程都可以被安排到任何核上，这没有什么直接的问题。然而，如果你关心的是高性能，这种灵活性会带来意想不到的代价。你想让某些线程只在某些核心上运行，有各种原因。由于操作系统允许迁移线程，可能你只是想让线程留在原地。

  • 如果一个线程迁移到不同的核心，而该核心有自己的缓存，你就会失去原来的缓存内容，不必要的内存转移就会发生。
  • 如果一个线程迁移了，没有什么可以阻止操作系统把两个线程放在一个核心上，而让另一个核心完全不使用。这显然导致了不太完美的速度提升，即使线程的数量等于核心的数量。

我们称亲和性为「线程亲和性」（thread affinity）或「进程亲和性」（process affinity）与核心之间的映射。亲和性通常表示为一个掩码：对允许一个线程运行的位置的描述。例如，考虑一个双插槽的节点，每个插槽有四个核心。有了两个线程和插槽的亲和力，我们就有了以下的「关联掩码」（affinity mask）。

thread socket 0 socket 1
0 0-1-2-3
1 4-5-6-7

对于核心亲和性，面具取决于亲和力类型。典型的策略是 “接近 “和 “扩散”。在亲和关系密切的情况下，掩码可以是

thread socket 0 socket 1
0 0
1 1

在同一个插槽上有两个线程意味着它们可能共享一个二级缓存，所以如果它们共享数据，这种策略是合适的。

另一方面，随着「亲和性扩散」（spread affinity），线程被进一步分开。

thread socket 0 socket 1
0 0
1 4

这种策略对于带宽受限的应用来说更好，因为现在每个线程都拥有一个插槽的带宽，而不是在 “关闭 “的情况下不得不分享它。

如果分配了所有的内核，关闭和分散策略会导致不同的安排。

socket 0 socket 1
0-1-2-3
4-5-6-7

相对于

socket 0 socket 1
0-2-4-6
1-3-5-7

亲和性也可以被认为是一种将执行与数据绑定的策略。

考虑一下这段代码：

  1. for (i=0; i<ndata; i++) // this loop will be done by threads
  2.      x[i] = ....
  3. for (i=0; i<ndata; i++) // as will this one
  4.      ... = .... x[i] ...

第一个循环，通过访问𝑥的元素，将内存带入高速缓存或页表。第二个循环以同样的顺序访问元素，所以为了性能，固定的亲和性是正确的决定。

在其他情况下，固定的映射不是正确的解决方案。

  1. for (i=0; i<ndata; i++) // produces loop
  2.      x[i] = ....
  3. for (i=0; i<ndata; i+=2) // use even indices
  4.      ... = ... x[i] ...
  5. for (i=1; i<ndata; i+=2) // use odd indices
  6.      ... = ... x[i] ...

在这第二个例子中，要么程序必须被改造，要么程序员必须实际维护一个任务队列。

  • 第一次接触：从 “把执行放在数据所在的地方 “的角度来考虑亲和性是很自然的。然而，在实践中，相反的观点有时是有意义的。例如，图2.8显示了一个集群节点的共享内存实际上是如何分布的。因此，一个线程可以连接到一个插槽，但数据可以由操作系统分配到任何一个插槽上。操作系统经常使用的机制被称为first-touch策略。
  • 当程序分配数据时，操作系统实际上并不创建数据。
  • 相反，数据的内存区域是在线程第一次访问它时创建的。
  • 因此，第一个接触该区域的线程实际上导致数据被分配到其插槽的内存中。

练习 2.19 用下面的代码解释一下这个问题。

  1. // serial initialization
  2. for (i=0; i<N; i++)
  3.   a[i] = 0.;
  4. #pragma omp parallel for
  5. for (i=0; i<N; i++)
  6.   a[i] = b[i] + c[i];

关于内存策略的深入讨论，见[134]。

Cilk Plus

还有其他基于线程的编程模型存在。例如，英特尔Cilk Plus(http://www.cilkplus.org/)是一套C/C++的扩展，程序员可以用它创建线程。

  1. //串行代码
  2. int fib(int n){
  3.   if (n<2) return 1;
  4.   else {
  5.     int rst=0;
  6.     rst += fib(n-1);
  7.     rst += fib(n-2);
  8.     return rst;
  9.   }
  10. }
  1. //Clik 代码
  2. cilk int fib(int n){
  3.   if(n<2) return 1;
  4.   else{
  5.     int rst = 0;
  6.     rst += cilk_spawn fib (n-1);
  7.     rst += cilk+spawn fib(n-2);
  8.     cilk_sync;
  9.     return rst;
  10.   }
  11. }

在这个例子中，变量rst被两个可能独立的线程更新。这种更新的语义，也就是如何解决同时写入等冲突的精确定义，是由串行一致性定义的；见2.6.1.6节。

超线程与多线程的比较

在上面的例子中，你看到在一个程序运行过程中产生的线程基本上都是执行相同的代码，并且可以访问相同的数据。因此，在硬件层面上，一个线程是由少量的局部变量唯一决定的，比如它在代码中的位置（程序计数器）和它所参与的当前计算的中间结果。

超线程是英特尔的一项技术，让多个线程真正同时使用处理器，这样处理器的一部分将得到最佳利用。

如果一个处理器在执行一个线程和另一个线程之间切换，它将保存一个线程的本地信息，并加载另一个线程的信息。与运行整个程序相比这样做的成本并不高，但与单条指令的成本相比可能很昂贵。因此，超线程不一定能带来性能的提高。

某些架构有对多线程的支持。这意味着硬件实际上对多个线程的本地信息有明确的存储，而且线程之间的切换可以非常快。GPU和英特尔Xeon Phi架构就是这种情况，每个内核可以支持多达四个线程。

OpenMP

OpenMP是对编程语言C和Fortran的一个扩展。它的主要并行方法是循环的并行执行：基于「编译器指令」（compiler directives），预处理器可以安排循环迭代的并行执行。

由于OpenMP是基于线程的，它的特点是「动态并行」（dynamic parallelism）：在代码的一个部分和另一个部分之间，并行运行的执行流的数量可以变化。并行性是通过创建并行区域来声明的，例如表明一个循环嵌套的所有迭代都是独立的，然后运行时系统将使用任何可用的资源。

OpenMP不是一种语言，而是对现有的C和Fortran语言的一种扩展。它主要通过在源代码中插入指令来操作，由编译器进行解释。与MPI不同，它也有少量的库调用，但这些不是重点。最后，还有一个运行时系统来管理并行的执行。

与MPI相比，OpenMP的一个重要优势在于它的可编程性：可以从一个串行代码开始，通过「增量并行化」（incremental parallelization）来改造它。相比之下，将串行代码转化为分布式内存MPI程序是一个全有或全无的事情。

许多编译器，如gcc或Intel编译器，支持OpenMP扩展。在Fortran中，OpenMP指令被放在注释语句中；在C中，它们被放在#pragma CPP指令中，用来表示编译器特定的扩展。因此，对于不支持OpenMP的编译器来说，OpenMP代码看起来仍然像合法的C或Fortran语句。程序需要链接到OpenMP运行库，其行为可以通过环境变量来控制。 关于OpenMP的更多信息，见[31]和http://openmp.org/wp/。

OpenMP示例

OpenMP使用的最简单的例子是并行循环。

  1. #pragma omp parallel for
  2. for (i=0; i<ProblemSize; i++) {
  3.   a[i] = b[i]; 
  4. }

很明显，所有的迭代都可以独立执行，并且以任何顺序执行。然后，pragma CPP指令将这个事实传达给编译器。

有些循环在概念上是完全并行的，但在实现上不是。

  1. for (i=0; i<ProblemSize; i++) { 
  2.   t = b[i]*b[i];
  3.   a[i] = sin(t) + cos(t);
  4. }

这里看起来好像每个迭代都在向一个共享变量t写和读。然而，t实际上是一个临时变量，是每个迭代的局部。应该是可并行的代码，但由于这样的结构而不能并行，这被称为非线程安全。

OpenMP指出，临时变量对每个迭代都是私有的，如下所示。

  1. #pragma omp parallel for shared(a,b), private(t) 
  2. for (i=0; i<ProblemSize; i++) {
  3.   t = b[i]*b[i];
  4.   a[i] = sin(t) + cos(t); 
  5. }

如果一个标量确实是共享的，OpenMP有各种机制来处理这个问题。例如，共享变量通常出现在规约操作中。

  1. s = 0;
  2. #pragma omp parallel for reduction(+:sum)
  3. for (i=0; i<ProblemSize; i++) { 
  4.   s = s + a[i]*b[i];
  5. }

正如上面所看到的，串行代码可以较为轻易地并行化。

迭代到线程的分配是由运行时系统完成的，但用户可以指导这种分配。我们主要关注迭代次数多于线程的情况：如果有$P$个线程和$N$个迭代，并且$N > P$，如何将迭代$i$分配给线程？

最简单的分配是使用「Round-robin任务调度」（round-robin task scheduling, a static scheduling），这是一种静态的调度策略，线程$p$获得迭代$p\times (N/P), …, (p + 1) \times (N/P) - 1$。这样做的好处是，如果一些数据在迭代之间被重复使用，它将留在执行该线程的处理器的数据缓存中。另一方面，如果迭代涉及的工作量不同，进程可能会遭受静态调度的负载不均衡。在这种情况下，动态调度策略的效果会更好，每个线程在完成当前迭代后就开始对下一个未处理的迭代进行工作。

我们可以用schedule关键字来控制OpenMP对循环迭代的调度，它的值包括静态和动态。也可以指出一个chunksize，它可以控制一起分配给线程的迭代块的大小。如果省略了chunksize，OpenMP将把迭代分成和线程数量一样多的块。

练习2.20 假设有$t$个线程，代码为

  1. for (i=0; i<N; i++) {
  2.   a[i] = // 执行部分计算
  3. }

如果指定chunksize为1，那么迭代0、𝑡、2𝑡……进入第一个线程，1、1+𝑡、1+2𝑡……进入第二个线程，依此类推。讨论一下为什么从性能的角度看这是一个糟糕的策略。提示：查一下「伪共享」（false sharing）的定义。什么是一个好的chunksize？

通过消息传递的分布式内存编程

虽然OpenMP程序和使用其他共享内存范式编写的程序看起来仍然非常像串行程序，但对于消息传递代码来说，情况并非如此。在我们详细讨论消息传递接口（MPI）库之前，我们先来看看并行代码编写方式的这种转变。

分布式编程中的全局视野与局部视野

在观察者看来，一个并行算法与它的实际编程方式之间可能存在明显的差异。考虑这样的情况：我们有一个处理器${Pi}{i=0…p-1}$的数组，每个处理器包含数组𝑥和𝑦中的一个元素，并且$Pi$计算 $$ \left{\begin{array}{ll} y{i} \leftarrow y{i}+x{i-1} & i>0 \ y_{i} \text { unchanged } & i=0 \end{array}\right. $$

这方面的全局描述可以是

  • 每个处理器$𝑃𝑖$（最后一个除外）都将其$𝑃𝑖$元素发送给$𝑃_{𝑖+1}$。

  • 除了第一个之外，每个$𝑃𝑖$处理器都从他们的邻居$𝑃{𝑖-1}$那里收到一个$𝑥$元素，并且

  • 他们将其添加到自己的$𝑦$元素中。

然而，在一般情况下，我们不能用这些全局术语来编码。在SPMD模型中，每个处理器执行相同的代码，而整体算法是这些单独行为的结果。本地程序只能访问本地数据—其他一切都需要用发送和接收操作来沟通—而且处理器知道自己的编号。

一种可能的写法是

  • 如果是第0个处理器，什么都不做；否则从左边接收一个元素，增加一个𝑥元素。
  • 如果是最后一个处理器，什么都不做。否则，将我的𝑦元素发送到右边。

首先，我们看一下发送和接收是所谓的「阻塞通信」（blocking communication）的情况：发送指令在实际收到发送的项目之前不会结束，而接收指令则等待相应的发送。这意味着处理器之间的发送和接收必须被仔细配对。现在我们将看到，这可能导致在通往高效代码的路上出现各种问题。

图2.13展示了上述解决方案，我们展示了描述本地处理器代码的局部时间线，以及由此产生的全局行为。你可以看到，处理器不是在同一时间工作的：我们得到的是序列化的执行。

如果我们把发送和接收操作倒过来呢？

  • 如果不是最后一个处理器，就把我的𝑥元素发送到右边。
    • 如果不是第一个处理器，从左边接收一个𝑥元素，并将其添加到𝑦元素中。

向右边发送数据的算法的局部和结果的全局视野：

wave_right_1

向右边发送数据的算法的局部和结果的全局视野：

wave_right_2

向右边发送数据的算法的局部和结果的全局视图：

wave_right_3

图2.14说明了这一点，你可以看到我们再次得到一个序列化的执行，只不过现在处理器是从右到左激活的。

如果方程2.5中的算法是循环的： $$ \left{\begin{array}{ll} y{i} \leftarrow y{i}+x{i-1} & i=1 \ldots n-1 \ y{0} \leftarrow y{0}+x{n-1} & i=0 \end{array}\right. $$ 问题会更加严重。现在，最后一个处理器无法开始接收，因为它被阻止向0号处理器发送𝑥𝑛-1。这种情况下，程序无法进展，因为每个处理器都在等待另一个处理器，这被称为「死锁」（deadlock）。

获得高效代码的解决方案是使尽可能多的通信同时发生。毕竟，在算法中没有串行的依赖性。因此，我们对算法的编程如下

  • 奇数处理器，先发后收。
  • 偶数处理器，先收后发。

图2.15说明了这一点，我们看到现在的执行是并行的。

练习 2.21 再看一下图2.3中的并行规约。其基本动作是 - 接收来自邻居的数据

  • 将其添加到自己的数据中
  • 将结果发送出去。

正如在图中看到的，至少有一个处理器不发送数据，其他的处理器在发送结果之前可能会做不同次数的接收。编写节点代码，使SPMD程序实现分布式规约。提示：用二进制写每个处理器的编号。该算法使用的步骤数等于该位串的长度。

  • 假设一个处理器收到一条消息，用步数表示到该消息的原点的距离。
  • 每个处理器最多发送一条消息。用二进制处理器编号来表示发生这种情况的步骤。

阻塞和非阻塞通信

阻断指令的原因是为了防止网络中的数据积累。如果一条发送指令在相应的接收指令开始之前完成，网络将不得不在这段时间内将数据储存在某个地方。考虑一个简单的例子：

  1. buffer = ... ;  // 生成一些数据
  2. send(buffer,0); // 发送给 0 处理器
  3. buffer = ... ;  // 生成更多数据
  4. send(buffer,1); // 发送给 1 处理器

在第一次发送后，我们开始覆盖缓冲区。如果其中的数据还没有被收到，那么第一组数值就必须在网络的某个地方被缓冲，这是不现实的。通过发送操作的阻断，数据会一直留在发送方的缓冲区中，直到它被保证复制到接收方的缓冲区。

解决由阻塞指令引起的顺序化或死锁问题的一个方法是使用「非阻塞通信」（non-blocking communication）指令，其中包括明确的数据缓冲区。使用非阻塞式发送指令，用户需要为每次发送分配一个缓冲区，并检查何时可以安全地覆盖缓冲区。

  1. buffer0 = ... ;   // data for processor 0
  2. send(buffer0,0);  // send to processor 0
  3. buffer1 = ... ;   // data for processor 1   
  4. send(buffer1,1);  // send to processor 1
  5. ...
  6. // wait for completion of all send operations.

MPI库

如果说OpenMP是对共享内存进行编程的方式，那么消息传递接口（MPI）[184]则是对分布式内存进行编程的标准解决方案。MPI（’Message Passing Interface’）是一个库接口的规范，用于在不共享数据的进程之间移动数据。MPI例程可以大致分为以下几类。

  • 进程管理。这包括查询并行环境和构建处理器的子集。
  • 点对点通信。这是一组调用，其中两个进程进行交互。这些大多是发送和接收调用的变种。
  • 集体调用。在这些程序中，所有的处理器（或整个指定的子集）都参与其中。例如，「广播」（broadcast）调用，一个处理器与其他所有处理器分享它的数据，或者收集调用，一个处理器从所有参与的处理器收集数据。

让我们考虑如何在MPI4中对OpenMP的例子进行编码。首先，我们不再分配

  1. double a[ProblemSize];

而是分配

  1. double a[LocalProblemSize];

其中，局部尺寸大约是全局尺寸的$1/P$部分。(实际的考虑决定了是让这个分布尽可能的均匀，还是在某种程度上有偏向)

并行循环是琐碎的并行，唯一的区别是它现在只对一部分数组进行操作。

  1. for (i=0; i<LocalProblemSize; i++) {
  2.      a[i] = b[i];
  3. }

然而，如果循环涉及基于迭代数的计算，我们需要将其映射到全局值。

  1. for (i=0; i<LocalProblemSize; i++) {
  2.      a[i] = b[i]+f(i+MyFirstVariable);
  3. }

(我们将假设每个进程都以某种方式计算了LocalProblemSize和MyFirstVariable的值）。 本地变量现在自动成为本地变量，因为每个进程都有自己的实例。

  1. for (i=0; i<LocalProblemSize; i++) {
  2.      t = b[i]*b[i];
  3.      a[i] = sin(t) + cos(t);
  4. }

然而，共享变量更难实现。由于每个进程都有自己的数据，因此必须明确地组装本地计算。

  1. for (i=0; i<LocalProblemSize; i++) {
  2.      s = s + a[i]*b[i];
  3. }
  4. MPI_Allreduce(s,globals,1,MPI_DOUBLE,MPI_SUM);

“规约”操作将所有的本地值s汇总到一个变量globals中，该变量在每个处理器上都收到一个相同的值。这就是所谓的「集合操作」（collective operation）。

让我们把这个例子变得稍微复杂些

  1. for (i=0; i<ProblemSize; i++) {
  2.   if (i==0)
  3.     a[i] = (b[i]+b[i+1])/2
  4.   else if (i==ProblemSize-1)
  5.     a[i] = (b[i]+b[i-1])/2
  6.   else
  7.     a[i] = (b[i]+b[i-1]+b[i+1])/3
  8. }

如果有共享内存，我们可以写出以下的并行代码。

  1. for (i=0; i<LocalProblemSize; i++) {
  2.      bleft = b[i-1]; bright = b[i+1];
  3.      a[i] = (b[i]+bleft+bright)/3
  4. }

为了将其转化为有效的分布式内存代码，首先我们要说明，对于i==0 (bleft)和i==LocalProblemSize-1 (bright)，bleft和bright需要从不同的处理器获得。我们通过与我们的左邻右舍处理器进行交换操作来做到这一点。

  1. // get bfromleft and bfromright from neighbor processors, then
  2.    for (i=0; i<LocalProblemSize; i++) {
  3.      if (i==0) bleft=bfromleft;
  4.        else bleft = b[i-1]
  5.      if (i==LocalProblemSize-1) bright=bfromright;
  6.        else bright = b[i+1];
  7.      a[i] = (b[i]+bleft+bright)/3
  8.    }

获得邻居值的方法如下。首先，我们需要询问我们的处理器编号，这样我们就可以与编号高一低一的处理器开始通信。

  1. MPI_Comm_rank(MPI_COMM_WORLD,&myTaskID);
  2. MPI_Sendrecv
  3.       (/* to be sent:  */ &b[LocalProblemSize-1],
  4.        /* destination  */ myTaskID+1,
  5.        /* to be recvd: */ &bfromleft,
  6.        /* source:      */ myTaskID-1,
  7.        /* some parameters omitted */
  8.       );
  9. MPI_Sendrecv(&b[0],myTaskID-1,
  10.        &bfromright, /* ... */ );

这段代码仍有两个问题。首先，sendrecv操作需要对第一个和最后一个处理器进行异常处理。这可以通过以下方式优雅地完成。

  1. MPI_Comm_rank(MPI_COMM_WORLD,&myTaskID);
  2. MPI_Comm_size(MPI_COMM_WORLD,&nTasks);
  3. if (myTaskID==0) leftproc = MPI_PROC_NULL;
  4.   else leftproc = myTaskID-1;
  5.   if (myTaskID==nTasks-1) rightproc = MPI_PROC_NULL;
  6.      else rightproc = myTaskID+1;
  7.   MPI_Sendrecv( &b[LocalProblemSize-1], &bfromleft,  rightproc );
  8.   MPI_Sendrecv( &b[0],                  &bfromright, leftproc);

练习 2.22 这段代码还存在一个问题：没有考虑到原版、全局的边界条件。请给出解决这个问题的代码。

如果不同的进程需要采取不同的行动，例如，如果一个进程需要向另一个进程发送数据，MPI就会变得复杂。这里的问题是每个进程执行的是同一个可执行文件，所以它需要包含发送和接收指令，根据进程的等级来执行。

  1. if (myTaskID==0) {
  2.      MPI_Send(myInfo,1,MPI_INT,/* to: */ 1,/* labeled: */,0,
  3.        MPI_COMM_WORLD);
  4.    } else {
  5.      MPI_Recv(myInfo,1,MPI_INT,/* from: */ 0,/* labeled: */,0,
  6.        /* not explained here: */&status,MPI_COMM_WORLD);
  7. }

阻塞

尽管MPI有时被称为 “并行编程的汇编语言”，因为它被认为是困难的和明确的，但它并不是那么难学，大量使用它的科学代码就证明了这一点。使MPI使用起来有些复杂的主要问题是缓冲区管理和阻塞语义。

这些问题是相关的，源于这样一个事实：理想情况下，数据不应该同时出现在两个地方。让我们简单考虑一下如果处理器1向处理器2发送数据会发生什么。最安全的策略是处理器1执行发送指令，然后等待处理器2确认数据被成功接收。这意味着处理器1被暂时阻断，直到处理器2实际执行其接收指令，并且数据已经通过网络。这是MPI_Send和MPI_Recv调用的标准行为，据说是使用「阻塞通信」（blocking communication）。

另外，处理器1可以把它的数据放在一个缓冲区里，告诉系统确保它在某个时间点被发送出去，然后再检查缓冲区是否可以重新使用。这第二种策略被称为「非阻塞通信」（non-blocking communication），它需要使用一个临时缓冲区。

集合操作

在上面的例子中，你看到了MPI_Allreduce调用，它计算了一个全局和，并将结果留在每个处理器上。还有一个本地版本MPI_Reduce，它只在一个处理器上计算结果。这些调用是集体操作或集合体的例子。集合运算有

  • 「规约」（reduction） : 每个处理器都有一个数据项，这些数据项需要用加法、乘法、最大或最小操作进行算术组合。其结果可以留在一个处理器上，也可以留在所有处理器上，在这种情况下，我们称之为allreduce操作。
  • 「广播」（broadcast）：一个处理器有一个数据项，所有处理器都需要接收。
  • 「收集」（gather）：每个处理器都有一个数据项，这些数据项需要被收集到一个数组中，而不需要通过加法等操作将其合并。其结果可以留在一个处理器上，也可以留在所有处理器上，在这种情况下，我们称其为allgather。
  • 「散发」（scatter）：一个处理器有一个数据项的数组，每个处理器接收该数组的一个片段。
  • 「全局」（all-to-all）：每个处理器都有一个项目数组，将被分散到所有其他处理器。

集合操作是阻塞的，尽管MPI 3.0（目前只是一个草案）将有非阻塞的集合操作。我们将在第6.1节详细分析集体操作的成本。

非阻塞通信

传统的计算机程序中，指令执行的方式取决于处理器中正在进行的操作，而在并行程序中，情况则较为复杂。一个简单发送操作，例如发送某个缓冲区的数据会导致程序执行停止，直至该缓冲区被另一个处理器安全发送和接收时结束。这种操作被称为「非本地操作」（non-local operation ），因为它依赖于其他进程的行动；这也被称为「阻塞通信」（blocking communication）操作，因为执行将停止以等待某个事件的发生。

阻塞操作的缺点是它们可能导致死锁。在消息传递的上下文中表现为：一个进程正在等待一个从未发生的事件；例如，它可能正在等待接收一个消息，而该消息的发送者正在等待其他事情。如果两个进程互相等待，或者更普遍的情况是，如果你有一个进程的循环，每个进程都在等待循环中的下一个进程，就会发生死锁。例如

  1. if ( /* 为处理器 0 */ )
  2.       // 等待来自处理器 1 的消息
  3. else if ( /* 为处理器 1 */ )
  4.       // 等待来自处理器 0 的消息

这里的块接收会导致死锁。即使没有死锁，处理器在等待时并没有执行任何操作，也会使其产生大量闲置时间。其优点是可以明确缓冲区何时可以被重用：在操作完成后，可以保证数据在另一端被安全地接收。

可以通过使用非阻塞通信操作来避免阻塞行为，但代价是使缓冲区语义复杂化。一个非阻塞的发送（MPI_Isend）声明需要发送一个数据缓冲区，但随后并不等待相应的接收完成。有第二个操作MPI_Wait，它实际上会阻塞，直到接收完成。这种发送和阻塞的解耦的好处是，现在有可能进行写入。

  1. MPI_ISend(somebuffer,&handle); // 开始发送，且
  2.     // 掌握这个特殊的通信
  3. { ... }  // 做一些对本地数据做有用的工作
  4. MPI_Wait(handle); // 锁住直至通信完成
  5. { ... }  // 做一些对输入的数据进行有用的工作

运气好的话，本地操作所花的时间比通信的时间多，这样就完全消除了通信时间。

除了非阻塞的发送，还有非阻塞的接收。一个典型的例子如下：

  1. MPI_ISend(sendbuffer,&sendhandle);
  2. MPI_IReceive(recvbuffer,&recvhandle);
  3. { ... }  // 做一些对本地数据有用的工作
  4. MPI_Wait(sendhandle); Wait(recvhandle);
  5. { ... }  // 做一些对输入的数据进行有用的工作

练习 2.23 再看一下方程(2.6)，给出使用非阻塞发送和接收解决问题的伪代码。与阻塞式解决方案相比，这个代码的缺点是什么？

三种版本的MPI对比

第一个MPI标准[164]有一些明显的遗漏，这些遗漏包括在MPI 2标准[91]中。其中之一是关于并行输入/输出：没有为多个进程访问同一个文件提供设施，即使底层硬件允许这样做。一个单独的项目MPI-I/O现在已经被纳入MPI-2标准。我们将在本书中讨论并行I/O。

MPI中缺少的第二个设施是进程管理，尽管它在MPI之前的PVM[50, 73]中就已经存在了：没有办法创建新的进程并让它们成为并行运行的一部分。最后，MPI-2支持单边通信：一个进程将数据放入另一个进程的内存中，而接收进程不做实际接收指令。我们将在下面的2.6.3.8节进行简短的讨论。

在MPI-3中，该标准获得了一些新的特性，如非阻塞集合体、邻接集合体和剖析接口。单边机制也得到了更新。

单边通信

MPI编写匹配发送和接收指令的方式并不理想。首先，它要求程序员两次给出相同的数据描述，一次发送，一次接收调用。其次，如果要避免死锁，它需要对通信进行相当精确的协调；如果使用异步调用的替代方法，程序将会十分繁琐，且需要程序管理大量的缓冲区。最后，它要求接收处理器知道要等待多少个传入的消息，这在不规则的应用中可能很棘手。如果有可能从另一个处理器中提取数据，或者反过来把数据放在另一个处理器上，而不需要另一个处理器明确参与，过程就会轻松很多。

一些硬件上存在的远程直接内存访问（RDMA）支持进一步鼓励了这种编程风格。一个早期的例子是Cray T3E。如今，通过在MPI-2库中的整合，单边通信被广泛使用；2.6.3.7节。

让我们简单看一下MPI-2中的单边通信，以数组值的平均化为例： $$ \foralli: a_i \leftarrow(a_i+a{i-1}+a_{i+1})/3. $$ MPI并行代码为

  1. // 做一些转换
  2. a_local = (a_local+left+right)/3

转换要完成的任务很清楚：a_local变量需要在等级较高的处理器上成为左边的变量，而在等级较低的处理器上成为右边的变量。

首先，处理器需要明确声明哪些内存区域可用于单边传输，即所谓的 “窗口”。在这个例子中，这包括处理器上的a_local、左边和右边变量。

  1. MPI_Win_create(&a_local,...,&data_window);
  2. MPI_Win_create(&left,....,&left_window);
  3. MPI_Win_create(&right,....,&right_window);

该代码现在有两个选择：可以将数据推送出去

  1. target = my_tid-1;
  2. MPI_Put(&a_local,...,target,right_window);
  3. target = my_tid+1;
  4. MPI_Put(&a_local,...,target,left_window);

或将其拉入

  1. data_window = a_local;
  2. source = my_tid-1;
  3. MPI_Get(&right,...,data_window);
  4. source = my_tid+1;
  5. MPI_Get(&left,...,data_window);

如果Put和Get调用是阻塞的，上述代码将具有正确的语义；见2.6.3.4节。然而，单边通信的部分吸引力在于它使通信的表达更加容易，为此，我们假设了一个非阻塞语义。

非阻塞的单边调用的问题是，有必要明确地确保通信成功完成。例如，如果一个处理器在另一个处理器上做了一个单边的put操作，另一个处理器就没有办法检查数据是否已经到达，或者是否已经开始传输。因此，有必要在程序中插入一个全局屏障，每个包都有自己的实现。在MPI-2中，相关调用是MPI_Win_fence例程。这些屏障实际上是将程序的执行分为超骤；见2.6.8节。

另一种形式的单边通信在Charm++包中使用；见2.6.7节。

混合共享/分布式内存计算

现代架构通常是共享和分布式内存的混合体。例如，一个集群在节点层面上是分布式的，但节点上的插槽和内核为共享内存。再往上一层，每个插槽可以有一个共享的L3缓存，但有独立的L2和L1缓存。直观地说，共享和分布式编程技术的混合似乎很清楚，可以提供与架构最匹配的代码。在这一节中，我们将讨论这种混合编程模型，并讨论其功效。

一个常见的集群设置使用分布式内存节点，每个节点包含几个彼此之间共享内存的插槽。这建议使用MPI在节点之间进行通信（节点间通信），使用OpenMP在节点上进行并行化（节点内通信）。在实践中，这实现了以下几点

  • 在每个节点上启动一个MPI进程（而不是每个核心一个）。
  • 这一个MPI进程然后使用OpenMP（或其他线程协议）来产生尽可能多的线程，这些线程在节点上有独立的套接字或核心。
  • 然后，OpenMP线程可以访问节点的共享内存。

另一种方法是在每个核或插槽上有一个MPI进程，通过消息传递进行通信，甚至可以看到进程之相同的共享内存。

注释 9：由于亲和性的原因，我们希望每个插槽启动一个MPI进程，而不是每个节点。这并没有实质性地改变上述论点。

这种混合策略听起来是个好主意，但事实上却很复杂。

尽管MPI进程之间消息传递看起来比共享内存的通信开销更大，但当MPI的优化版本检测进程在同一个节点时，就会采取时间开销更小的数据拷贝以代替通信。不使用MPI的唯一理由是：每个进程都有自己的数据空间，这会因为每个进程都要为缓冲区和被复制的数据分配空间而造成内存开销。

线程更加灵活：如果代码的某一部分需要每个进程有更多的内存，那么OpenMP方法可以限制这一部分的线程数量。另一方面，对线程的灵活处理会产生一定的操作系统开销，而MPI的固定进程是没有这种开销的。

共享内存编程在概念上很简单，但也会有意想不到的性能隐患。例如，现在两个进程的性能可能会因为需要维持缓存一致性和虚假共享而受到阻碍。

另一方面，混合方法提供了一些优势，因为它捆绑了消息。例如，如果一个节点上的两个MPI进程分别向另一个节点上的两个进程发送消息，就会有四条消息；在混合模型中，这些消息将被捆绑成一条消息。

练习 2.24 分析上面最后一项的讨论。假设两个节点之间的带宽只够一次维持一条消息。与纯分布式模型相比，混合模型的成本节约是多少？提示：分别考虑频带宽度和延时。

这种MPI进程的捆绑可能有一个更深层次的技术原因的优势。为了支持握手协议，每个MPI进程需要为每个其他进程提供少量的缓冲空间。在进程数量较多的情况下，这可能是一个限制，因此在英特尔Xeon Phi等高核数处理器上，捆绑是有吸引力的。

MPI库中明确指出了其支持的线程类型：是否完全支持多线程、是否所有的MPI调用都必须来自一个线程或一次一个线程，或者在从线程进行MPI调用时是否有完全的自由。

并行语言

缓解并行编程困难的一个方法是设计出对并行性提供明确支持的语言。下面列举了一些方法：

  • 一些语言反映了科学计算中的许多操作是数据并行的（第2.5.1节）。诸如高性能Fortran（HPF）（第2.6.5.3节）等语言有一个数组语法，其中数组的加法等操作可以表示为$A=B+C$。这种语法简化了编程，但更重要的是，它在一个抽象的层次上指定了操作，这样下层就可以对如何处理并行作出具体决定。然而，HPF中表达的数据并行只是最简单的一种，即数据包含在常规数组中。不规则的数据并行比较困难；Chapel语言（第2.6.5.5节）试图解决这个问题。

  • 并行语言中的另一个概念，不一定与前者正交，是分区全局地址空间（PGAS）模型：只有一个地址空间（与MPI模型不同），但这个地址空间是分区的，每个分区与线程或进程有亲和力。因此，这个模型包含了SMP和分布式共享内存。一种典型的PGAS语言，统一并行C（UPC），允许你编写程序，在大多数情况下看起来像普通的C代码。然而，通过指出主要阵列在处理器上的分布方式，程序可以被并行执行。

讨论

并行语言有希望使并行编程变得更容易，因为它们使通信操作看起来像简单的复制或算术操作。然而，通过这样做，它们邀请用户编写可能并不高效的代码，例如，通过诱导许多小信息。

作为一个例子，考虑将数组a,b在处理器上进行水平分割，并进行移位（见图2.16）。

  1. for (i=0; i<N; i++)
  2.      for (j=0; j<N/np; j++)
  3.        a[i][j+joffset] = b[i][j+1+joffset]

abshift

如果这段代码在共享内存机器上执行，它将是高效的，但在分布式情况下的天真翻译将在$i$循环的每个迭代中传达一个数字。显然，这些都可以结合在一个缓冲区的发送/接收操作中，但编译器通常无法进行这种转换。因此，用户被迫，实际上，重新实现了需要在MPI实现中完成的阻塞。

  1. for (i=0; i<N; i++)
  2.   t[i] = b[i][N/np+joffset]
  3. for (i=0; i<N; i++)
  4.   for (j=0; j<N/np-1; j++) {
  5.     a[i][j] = b[i][j+1]
  6.       a[i][N/np] = t[i]
  7. }

另一方面，某些机器通过全局内存硬件支持直接内存拷贝。在这种情况下，PGAS语言可以比显式消息传递更有效率，即使是物理分布式内存。

Unified Parallel C

统一并行C（UPC）[191]是C语言的一个扩展。它的主要并行来源是数据并行，编译器发现了数组上操作的独立性，并将其分配给不同的处理器。该语言有一个扩展的数组声明，允许用户指定数组是按块划分，还是以轮流方式划分。

下面的UPC程序执行了一个向量与向量加法。

  1. //vect_add.c
  2.    #include <upc_relaxed.h>
  3.    #define N 100*THREADS
  4.  shared int v1[N], v2[N], v1plusv2[N];
  5.    void main() {
  6.      int i;
  7.      for(i=MYTHREAD; i<N; i+=THREADS)
  8.        v1plusv2[i]=v1[i]+v2[i];
  9.    }

同样的程序有一个明确的并行循环结构

  1. //vect_add.c
  2.    #include <upc_relaxed.h>
  3.    #define N 100*THREADS
  4.    shared int v1[N], v2[N], v1plusv2[N];
  5.    void main()
  6.    {
  7.      int i;
  8.      upc_forall(i=0; i<N; i++; i)
  9.        v1plusv2[i]=v1[i]+v2[i];
  10.    }

在含义上与UPC相当，但基于Java而不是C。

High Performance Fortran

高性能Fortran5（HPF）是Fortran90的一个扩展，具有支持并行计算的结构，由高性能Fortran论坛（HPFF）发布。HPFF由莱斯大学的Ken Kennedy召集并担任主席。HPF报告的第一个版本发表于1993年。

在Fortran 90引入的数组语法的基础上，HPF使用数据并行计算模型来支持将单个数组计算的工作分散到多个处理器上。这使得在SIMD和MIMD风格的架构上都能有效地实现。HPF的特点包括。

  • 新的Fortran语句，如FORALL，以及创建PURE（无副作用）程序的能力。

  • 使用编译器指令来推荐阵列数据的分布。

  • 用于与非HPF并行程序接口的外在程序接口，如那些使用消息传递。

  • 额外的库例程，包括环境查询、并行前缀/后缀（例如，’扫描’）、数据散射和排序操作。

Fortran 95整合了几个HPF功能。虽然一些供应商在20世纪90年代确实将HPF纳入了他们的编译器中，但有些方面被证明是难以实现的，而且用途值得怀疑。从那时起，大多数供应商和用户都转向了基于OpenMP的并行处理。然而，HPF仍然有影响。例如，为即将到来的Fortran-2008标准提出的BIT数据类型包含了许多直接来自HPF的新的内在函数。

Co-array Fortran

Co-array Fortran（CAF）是Fortran 95/2003语言的一个扩展。支持并行的主要机制是对数组声明语法的扩展，其中一个额外的维度表示并行分布。例如，在

  1. Real,dimension(100),codimension[*] :: X
  2. Real :: Y(100)[*]
  3. Real :: Z(100,200)[10,0:9,*]

数组X,Y在每个处理器上有100个元素。数组Z的行为就像可用的处理器在一个三维网格上，其中两边是指定的，第三边可以调整以适应可用的处理器。

现在处理器之间的通信是通过沿着描述处理器网格的（共）维度的拷贝来完成的。Fortran 2008的标准包括共同数组。

Chapel

Chapel[30]是一种新的并行编程语言6，由Cray公司开发，是DARPA领导的高生产率计算系统计划（HPCS）的一部分。Chapel旨在提高高端计算机用户的生产效率，同时也是一个可移植的并行编程模型，可用于商品集群或桌面多核系统。Chapel致力于极大地提高大规模并行计算机的亲和力，同时匹配或击败当前编程模型（如MPI）的性能和可移植性。

Chapel通过对数据并行、任务并行、并发和嵌套并行的高级抽象支持多线程执行模型。Chapel的locale类型使用户能够指定并重新确定数据和任务在目标架构上的位置，以便对位置进行调整。Chapel支持具有用户定义实现的全局视图数据聚合，允许以自然方式表达对分布式数据结构的操作。与许多以前的高级并行语言相比，Chapel是围绕多分辨率哲学设计的，允许用户最初编写非常抽象的代码，然后逐步增加细节，直到他们接近机器的需要。Chapel通过面向对象的设计、类型推理和通用编程的功能，支持代码重用和快速原型设计。

Chapel是根据第一原则设计的，而不是通过扩展现有的语言。它是一种im-perative块状结构的语言，旨在使C、C++、Fortran、Java、Perl、Matlab和其他流行语言的用户易于学习。虽然Chapel建立在许多以前的语言的概念和语法上，但它的并行功能最直接地受到ZPL、高性能Fortran（HPF）和Cray MTA对C和Fortran的扩展的影响。 下面是Chapel中的向量与向量加法：

  1. const BlockDist= newBlock1D(bbox=[1..m], tasksPerLocale=...);
  2. const ProblemSpace: domain(1, 64)) distributed BlockDist = [1..m];
  3. var A, B, C: [ProblemSpace] real;
  4. forall(a, b, c) in(A, B, C) do
  5.   a = b + alpha * c;

Fortress

Fortress[67]是由Sun Microsystems开发的一种编程语言。Fortress7的目的是通过几种方式使平行主义更容易操作。首先，并行性是默认的。这是为了推动工具设计、库设计和程序员技能向并行化方向发展。第二，语言被设计成对并行更友好。不鼓励副作用，因为副作用需要同步化以避免错误。Fortress提供了事务，这样程序员就不会面临确定锁定顺序的任务，或者调整他们的锁定代码，以便有足够的正确性，但又不至于妨碍性能。Fortress的循环结构，连同库，把 “迭代 “变成了内部；而不是循环指定如何访问数据，数据结构指定如何运行循环，聚合数据结构被设计成可以有效地安排并行执行的大型部分。Fortress还包括来自其他语言的功能，旨在普遍地帮助提高生产力—测试代码和方法，与被测试的代码相联系；合同，可以在代码运行时选择检查；以及属性，可能运行成本太高，但可以反馈给定理验证器或模型检查器。此外，Fortress还包括安全的语言特性，如检查数组边界、类型检查和垃圾收集，这些在Java中已经被证明是有用的。Fortress的语法被设计为尽可能地类似于数学语法，因此任何人在解决其规范中的数学问题时，都可以写出一个与原始规范明显相关的程序。

X10

X10是一种实验性的新语言，目前正在IBM与学术伙伴合作开发。X10工作是DARPA高生产率计算机系统计划中的IBM PERCS项目（生产性易使用的可靠计算机系统）的一部分。PERCS项目专注于硬件-软件联合设计方法，以整合芯片技术、架构、操作系统、编译器、编程语言和编程工具方面的进展，提供新的可适应、可扩展的系统，在2010年之前将并行应用的开发效率提高一个数量级。

X10旨在通过开发新的编程模型，结合集成到Eclipse中的一套新的工具和新的实现技术，在可管理的运行环境中提供优化的可扩展的并行性，为提高生产率作出贡献。X10是一种类型安全的、现代的、并行的、面向对象的分布式语言，旨在让Java(TM)程序员能够使用。它的目标是未来的低端和高端系统，其节点由多核SMP芯片构成，具有非统一的内存层次，并以可扩展的集群配置互连。作为分区全局地址空间（PGAS）语言家族中的一员，X10强调以地方的形式明确地重新定义位置；体现在async、future、foreach和attach con-结构中的轻量级活动；用于终止检测（finish）和分阶段计算（clocks）的结构；使用无锁同步（原子块）；以及对全局数组和数据结构进行操作。

Linda

现在应该很清楚了，数据的处理是迄今为止并行编程最重要的方面，远比算法方面的考虑更重要。编程系统Linda[74, 75]，也被称为协调语言，旨在明确地解决数据处理问题。琳达不是一种语言，但是可以，而且已经被纳入其他语言。

琳达的基本概念是元组空间：通过给数据添加一个标签，将其添加到一个全局可访问的信息池中。然后，进程通过标签值来检索数据，而不需要知道是哪个进程将数据添加到元组空间中的。

Linda主要针对的是与高性能计算（HPC）不同的计算模型：它解决的是异步通信进程的需求。然而，它已经被用于科学计算[45]。例如，在热方程的并行模拟中（第4.3节），处理器可以将他们的数据写入元组空间，而相邻的进程可以检索他们的鬼魂重区，而不必知道它的出处。因此，Linda成为实现单边通信的一种方式。

The Global Arrays library

The Global Arrays library（http://www.emsl.pnl.gov/docs/global/）是另一个单边通信的例子，事实上它早于MPI。这个库的主要数据结构是笛卡尔积数组8，分布在相同或更低维度的处理器网格上。通过库的调用，任何处理器都可以通过放或取的操作访问阵列中的任何子砖。这些操作是非集体的。与任何单边协议一样，屏障同步是必要的，以确保发送/接收的完成。

基于操作系统的方法

可以设计一个具有共享地址空间的架构，并让数据移动由操作系统处理。Kendall Square计算机[124]有一个名为 “全缓存 “的架构，其中没有数据与任何处理器直接相关。相反，所有的数据都被认为是缓存在一个处理器上，并根据需要通过网络移动，就像数据从主内存移动到普通CPU的缓存中一样。这个想法类似于目前SGI架构中的NUMA支持。

活跃通信

MPI范式（第2.6.3.3节）传统上是基于双侧操作的：每个数据传输都需要一个明确的发送和接收操作。这种方法对于相对简单的代码来说效果很好，但是对于复杂的问题来说，就很难协调所有的数据移动。简化的方法之一是使用「活跃通信」（active message）。这在Charm++[119]包中被使用。

通过主动消息，一个处理器可以向另一个处理器发送数据，而不需要第二个处理器做明确的接收操作。相反，接收者声明处理传入数据的代码，用客观方向的说法是 “方法”，而发送处理器则用它想发送的数据调用这个方法。由于发送处理器实际上是激活了另一个处理器上的代码，这也被称为「远程调用」（remote method invocation）。这种方法的一个很大的优点是，通信和编译的重叠变得更容易实现。

作为一个例子，考虑用一个三对角矩阵进行矩阵与向量乘法 $$ \foralli: y_i\leftarrow 2x_i - x{i+1} - x_{i-1}. $$ 关于这个问题在PDEs中的起源，见4.2.2节的解释。假设每个处理器正好有一个索引$i$，MPI代码可以是这样的。

  2. if ( /* I am the first or last processor */ ) 
  3.   n_neighbors = 1;
  4. else
  5.   n_neighbors = 2;
  6. /* do the MPI_Isend operations on my local data */
  8. sum = 2*local_x_data;
  9. received = 0;
  10. for (neighbor=0; neighbor<n_neighbors; neighbor++) {
  11.   MPI_WaitAny( /* wait for any incoming data */ ) 
  12.   sum = sum - /* the element just received */ 
  13.   received++
  14.   if (received==n_neighbors)
  15.     local_y_data = sum 
  16. }

有了活跃通信，这看起来就像

  1. void incorporate_neighbor_data(x) { 
  2.   sum = sum-x;
  3.   if (received==n_neighbors)
  4.     local_y_data = sum 
  5. }
  6. sum = 2*local_xdata;
  7. received = 0; 
  8. all_processors[myid+1].incorporate_neighbor_data(local_x_data); 
  9. all_processors[myid-1].incorporate_neighbor_data(local_x_data);

批量同步并行

MPI库（2.6.3.3节）可以带来非常高效的代码。这样做的代价是，程序员需要非常详细地说明通信的内容。在光谱的另一端，PGAS语言（第2.6.5节）对程序员的要求很低，但却没有带来多少性能回报。一种试图找到中间地带的方法是「批量同步并行」（Bulk Synchronous Parallel，BSP）模型[192, 183]。在这里，程序员需要写出通信，但不是它们的顺序。

BSP模型将程序排列成一个超步的序列，每个步骤都以一个障碍物同步结束。在一个超步中开始的通信都是异步的，并依靠屏障来完成。这使得编程更容易，并消除了死锁的可能性。

此外，所有通信都是单边通信类型。

练习 2.25 考虑2.1节中的并行求和例子。论证BSP的实现需要$\log_2n$超步。

由于其通过障碍物完成超级步骤的处理器的同步，BSP模型可以对并行算法做一个简单的成本分析。

BSP模型的另一个方面是它对问题的「过度分解」（overdecomposition），即把多个进程分配给每个处理器，以及「随机放置」（random placement）数据和任务。这是以统计学的论点为依据的，表明它可以补救负载的不均衡。如果有$𝑝$个处理器，如果在一个超步中进行了$𝑝$次远程访问，那么很可能有些处理器会收到$\log𝑝/\log \log 𝑝$次访问，而其他处理器则没有收到。因此，负载不均衡的问题会随着处理器数量的增加而变得更加严重。另一方面，如果有$𝑝\log p$的访问，例如因为每个处理器上有$\log 𝑝$的进程，最大的访问次数是$3\log 𝑝$，而且概率很大。这意味着负载平衡是在一个完美的恒定系数内。

BSP模型是在BSPlib[107]中实现的。其他系统可以说是类似BSP的，因为它们使用了超步的概念；例如，谷歌的Pregel[150]。

数据依赖

如果两个语句引用了相同的数据项，我们就说这些状态之间存在着「数据依赖」（data dependency）关系。这种依赖关系限制了语句的执行可以被重新安排的程度。对这一主题的研究可追溯到20世纪60年代，当时处理器可以不按串行执行语句以提高吞吐量。语句的重新排序受到了限制，因为执行必须遵守程序的「串行语义」（program order）：结果必须像语句严格按照它们在程序中出现的串行执行一样。

语句排序以及因此而产生的数据依赖性的问题，以几种方式出现：

  • 并行化编译器必须对资源进行分析，以确定允许哪些转换。
  • 如果你用OpenMP指令并行化一个顺序代码，你必须自己进行这样的分析。

这里有两种需要进行这种分析的活动：

  • 当一个循环被并行化时，迭代不再按其程序顺序执行，所以我们必须检查依赖关系。

  • 引入任务是指程序的某些部分可以按照与顺序执行不同的顺序执行。

依赖性分析的最简单的情况是检测循环迭代是否可以独立执行。如果一个数据项在两个不同的迭代中被读取，迭代当然是独立的，但是如果同一个项目在一个迭代中被读取，在另一个迭代中被写入，或者在两个不同的迭代中被写入，我们需要做进一步分析。

数据依赖性的分析可以由编译器来执行，但是编译器必须采取一种保守的方法。这意味着迭代可能是独立的，但不能被编译器所识别。因此，OpenMP把这个责任转移给了程序员。

现在，我们将详细讨论数据依赖的细节。

数据依赖类型

这三种类型的依赖关系是

  • 「流依赖」（flow dependencies），或 “读后写”。

  • 「反依赖」（anti dependencies），即 “读后写”；以及

  • 「输出依赖」（output dependencies），即 “写完再写”。

这些依赖关系可以在标量代码中进行研究，事实上编译器也是这样做的，以确定语句是否可以重新排列，但是我们将主要关注它们在循环中的出现，因为在科学计算中很多工作都出现在这里。

  • 流依赖：如果读和写发生在同一个循环迭代中，那么流量依赖，或者说读-写，就不是一个问题。
  1. for (i=0; i<N; i++) { 
  2.   x[i] = .... ;
  3.   .... = ... x[i] ... ;
  4. }

另一方面，如果读取发生在后来的迭代中，就没有简单的方法来并行化或向量化循环。

  1. for (i=0; i<N; i++) { 
  2.   .... = ... x[i] ... ; 
  3.   x[i+1] = .... ;
  4. }

这通常需要重写代码。

练习 2.26 考虑如下代码

  1. for (i=0; i<N; i++) { 
  2.   a[i] = f(x[i]); 
  3.   x[i+1] = g(b[i]);
  4. }

其中f()和g()表示没有进一步依赖x或i的算术表达式。

  • 反依赖性：反依赖性或读后写的最简单情况是减少。
  1. for(i=0; i<N; i++){
  2.   t =t+ ...
  3. }

这可以通过明确声明循环是一个减法来处理，或者使用6.1.2节中的任何其他策略。

如果读和写是在一个数组上，情况就更复杂了。这个片段中的迭代

  1. for (i=0; i<N; i++) { 
  2.   x[i] = ... x[i+1] ... ;
  3. }

不能像这样以任意顺序执行。然而，从概念上讲，这并不存在依赖性。我们可以通过引入一个临时数组来解决这个问题。

  1. for (i=0; i<N; i++) 
  2.   xtmp[i] = x[i];
  3. for (i=0; i<N; i++) {
  4.   x[i] = ... xtmp[i+1] ... ;
  5. }

这是一个编译器不太可能执行的转换的例子，因为它可能会大大影响程序的内存需求。因此，这就留给了程序员。

  • 输出依赖：输出依赖或写后依赖的情况本身不会发生：如果一个变量被依次写了两次，中间没有读，那么第一次写可以被删除而不改变程序的意义。因此，这种情况会减少为流动依赖。

其他的输出依赖也可以被移除。在下面的代码中，t可以被声明为私有，从而消除了依赖性。

  1. for (i=0; i<N; i++) { 
  2.   t = f(i)
  3.   s += t*t;
  4. }

如果想要t的最终值，可以在OpenMP中使用lastprivate。

嵌套循环的并行化

在上述例子中，如果在一个循环的迭代$𝑖$中出现了不同的指数，如$𝑖$和$𝑖+1$，那么数据的依赖性就是非实质性的。反之，循环如

  1. for (int i=0; i<N; i++) 
  2.   x[i] = x[i]+f(i);

是简单的并行化。然而，嵌套的循环则需要更多的思考。OpenMP有一个 “折叠 “指令，用于诸如以下的循环

  1. for (int i=0; i<M; i++) 
  2.   for (int j=0; j<N; j++)
  3.     x[i][j] = x[i][j] + y[i] + z[j];

这里，整个$i$，$j$迭代空间是并行的。这是怎么回事？

  1. for (n = 0; n < NN; n++) 
  2.   for (i = 0; i < N; i++)
  3.     for (j = 0; j < N; j++)
  4.       a[i] += B[i][j]*c[j] + d[n];

练习 2.27 对这个循环做一个重用分析。假设a,b,c不能一起放进缓存。现在假设c和b的一行可以放入缓存，并且还有一点空间。你能找到一个能使性能大大提高的循环交换吗？写一个测试来证实这一点。

分析这个循环嵌套的并行性，你会发现j循环是一个减法，而n循环有流量依赖：每个a[i]在每个n次迭代中被更新。结论是，你只能合理地并行化$i$环路。

练习 2.28 这个并行性分析与练习2.27中的循环交换有什么关系？交换后的循环是否仍然是可并行的？

如果你会说OpenMP，请通过编写将a的元素相加的代码来确认你的答案，无论交换和引入OpenMP并行性，你都应该得到同样的答案。

并行程序设计

很久以前，人们认为编译器和运行时系统的某种神奇组合可以将现有的顺序程序转化为并行程序。这种希望早已破灭，所以现在的并行程序从一开始就被写成了并行程序。当然，有不同类型的并行性，它们对你如何设计你的并行程序都有各自的影响。在这一节中，我们将简要地探讨其中的一些问题。

并行数据结构

并行程序设计中的一个问题是使用数组结构（Array-Of-Structures，AOS）与结构化数组（Structure-Of-Arrays，SOA）。在正常的程序设计中，我们经常定义一个结构

  1. struct { int number; double xcoord,ycoord; } _Node; 
  2. struct { double xtrans,ytrans} _Vector;
  3. typedef struct _Node* Node;
  4. typedef struct _Vector* Vector;

而如果需要许多这样的结构，我们就创建一个这样的结构数组。

  1. Node *nodes = (Node*) malloc( n_nodes*sizeof(struct _Node) );

这就是AOS的设计。

现在，假设我们想将一个操作并行化

  1. void shift(Node the_point,Vector by) { 
  2.   the_point->xcoord += by->xtrans; 
  3.   the_point->ycoord += by->ytrans;
  4. }

这是在一个循环中完成的

  1. for (i=0; i<n_nodes; i++) { 
  2.   shift(nodes[i],shift_vector);
  3. }

这段代码具有MPI编程的正确结构（2.6.3.3节），每个处理器都有自己的本地节点数组。这个循环也很容易用OpenMP并行化（第2.6.2节）。

然而，在20世纪80年代，人们意识到AOS的设计并不适合向量计算机，因此不得不对代码进行大幅重写。在这种情况下，我们的操作数需要是连续的，所以代码必须采用SOA设计。

  1. node_numbers = (int*) malloc( n_nodes*sizeof(int) ); 
  2. node_xcoords = // et cetera
  3. node_ycoords = // et cetera

而将迭代

  1. for (i=0; i<n_nodes; i++) { 
  2.   node_xoords[i] += shift_vector->xtrans; 
  3.   node_yoords[i] += shift_vector->ytrans;
  4. }

最初的SOA设计最适合于分布式内存编程吗，这意味着在向量计算机时代的10年后，每个人都必须为集群重新编写他们的代码。当然，如今随着SIMD宽度的增加，我们也需要部分地回到AOS的设计。(在英特尔的ispc项目中，有一些实验性的软件支持这种转变，http: //ispc.github.io/，它将SPMD代码翻译成SIMD)。

延迟隐蔽性

处理器之间的通信通常很慢，比单个处理器上的内存数据传输要慢，而且比对数据的操作要慢得多。因此在设计一个并行程序时，最好考虑到网络流量与 “有用 “操作的相对数量。每个处理器必须有足够的工作来抵消通信。

应对通信相对缓慢的另一种方法是安排程序，使通信实际发生在一些计算正在进行的时候。这被称为通信的「重叠计算」（overlapping computation with communication）或「延迟隐藏」（latency hiding）。

例如，考虑矩阵与向量乘积$𝑦=𝐴$的并行执行。假设向量是分布式的，那么每个处理器$𝑝$都会执行 $$ \forall{i\in I_p}:y_i = \sum_ja{ij}xj $$ 由于$𝑥$也是分布式的，我们可以将其写为 $$ \forall{i \in I{p}}: y{i}=\left(\sum{j \text { local }}+\sum{j \text { not local }}\right) a{i j} x{j} $$ 这个方案如图2.17所示。我们现在可以按以下方式进行。

  • 开始转移$𝑥$的非本地元素。
  • 在数据传输过程中，对$𝑥$的本地元素进行操作。
  • 确保传输完成。
  • 对$𝑥$的非本地元素进行操作。

distmvp

练习 2.29 你能从计算和通信的重叠中获得多少好处？提示：考虑计算耗时为零且只有通信的边界情况，以及相反的情况。现在考虑一般情况。

当然，这种情况的前提是有软件和硬件对这种重叠的支持。MPI允许这样做（见2.6.3.6节），通过所谓的异步通信或非阻塞通信例程。这并不立即意味着重叠将实际发生，因为硬件支持是一个完全独立的问题。

拓扑

如果一些处理器一起工作在一个任务上，他们很可能需要交流数据。由于这个原因，需要有一种方法使数据从任何一个处理器到其他处理器。在本节中，我们将讨论一些可能的方案来连接并行机器中的处理器。这种方案被称为（处理器）「拓扑」（topology）。

为了明确这里的问题，请考虑两个不能 “扩展 “的简单方案。

  • 以太网是一种连接方案，网络上的所有机器都在一条电缆上（见下文注释）。如果一台机器在电线上放了一个信号来发送信息，而另一台机器也想发送信息，那么后者将检测到唯一可用的通信通道被占用，它将等待一段时间后再重新进行发送操作。在以太网上接收数据是很简单的：信息包含了目标接收者的地址，所以一个处理器只需要检查电线上的信号是否是为它准备的。

    这个方案的问题应该很清楚。通信通道的容量是有限的，所以当更多的处理器连接到它时，每个处理器可用的容量将下降。由于解决冲突的方案，信息开始前的平均延迟也会增加。

  • 在完全连接的配置中，每个处理器都有一条与其他处理器通信的线路。

    其他处理器。这种方案是完美的，因为消息可以在最短的时间内发送，而且两个消息永远不会互相干扰。一个处理器可以发送的数据量不再是处理器数量的递减函数；事实上，它是一个递增函数，如果网络控制器可以处理，一个处理器甚至可以同时进行多次通信。

    当然，这个方案的问题是，一个处理器的网络接口的设计不再是固定的：随着更多的处理器被添加到并行机器上，网络接口得到更多的连接线。网络控制器也同样变得更加复杂，机器的成本增加速度超过了处理器数量的线性增长。

注释 10 以上对以太网的描述是对原始设计的描述。随着交换机的使用，特别是在HPC的背景下，这种描述已经不再真正适用。

最初人们认为，信息碰撞意味着以太网将不如其他解决方案，如IBM的令牌环网，它明确地防止碰撞。需要相当复杂的统计分析来证明，以太网的工作原理比朴素预期好得多。

在本节中，我们将看到一些可以增加到大量处理器的方案。

图论

互联并行计算机中的处理器的网络可以方便地用一些基本的图论概念来描述。我们用一个图来描述并行机器，每个处理器都是一个节点，如果两个节点之间有直接的联系，那么这两个节点就是相连的。(我们假设连接是对称的，所以网络是一个无向图）

下面分析图的两个重要概念。

首先，图中一个节点的程度是它所连接的其他节点的数量。节点代表处理器，边代表导线，很明显，高度不仅是计算效率所希望的，而且从工程的角度来看也是昂贵的。我们假设所有处理器都有相同的度。

其次，从一个处理器到另一个处理器的信息，通过一个或多个中间节点，很可能在节点之间路径的每个阶段产生一些延迟。由于这个原因，图的直径很重要。直径被定义为任何两个节点之间的最大最短距离，包括链接的数量。 $$ d(G)=\max _{i, j} \mid \text { shortest path between } i \text { and } j \mid $$ 如果$𝑑$是直径，如果在一条线上发送一个信息需要单位时间，这意味着一个信息总是在最多$𝑑$时间内到达。

练习 2.30 找出处理器的数量、它们的程度和连接图的直径之间的关系。

除了 “一个消息从处理器A到处理器B需要多长时间 “的问题外，我们还经常担心两个同时进行的消息之间的冲突：是否存在两个同时进行的消息需要使用同一网络链接的可能性？在图 2.18 中，我们说明了如果每个处理器$𝑝𝑖$在$i < n/2$ 的情况下向$𝑝{i+n/2}$ 发送消息会发生什么：会有$n/2$ 的消息试图通过$p_{n/2-1}$ 和$p_n$之间的线路。这种冲突被称为「拥堵」（congestion）或「争夺」（contention）。显然，一台并行计算机的链接越多，发生拥堵的机会就越小。

描述拥堵可能性的一个精确方法是看「二分宽度」（bisection width）。这被定义为将处理器图分割成两个非连接图所必须移除的最小链接数。例如，考虑处理器连接成一个线性阵列，即处理器$P𝑖$与$P{i-1}$和$P_{i+1}$连接。在这种情况下，分界线宽度为1。

二分宽度𝑤描述了在一台并行计算机中可以保证有多少信息同时进行。证明：采取𝑤发送和𝑤接收处理器。这样定义的𝑤路径是不相交的：如果不相交，我们只需去除𝑤-1个链接就可以把处理器分成两组。

当然，在实践中，超过$w$条信息可以同时进行。例如，在一个线性阵列中，$w=1$，如果所有的通信都是在邻居之间，如果一个处理器在任何时候都只能发送或接收，而不能同时发送和接收，则可以同时发送和接收𝑃/2条信息。如果处理器可以同时发送和接收，那么网络中可以有𝑃个信息正在进行。

二分宽度也描述了网络中的「冗余度」（redundancy）：如果一个或多个连接出现故障，信息是否仍能从发送方找到接收方？

虽然二分宽度是一种表示导线数量的措施，但实际上我们关心的是通过导线的容量。这里的相关概念是「二分带宽」（bisection bandwidth）：横跨分节宽度的带宽，是分节宽度与导线容量（以每秒比特为单位）的乘积。二分带宽可以被认为是衡量任意一半处理器与另一半处理器进行通信所能达到的带宽。二分带宽是一个比有时引用的总带宽更现实的衡量标准，它被定义为每个处理器都在发送时的总数据率：处理器的数量乘以连接的带宽乘以一个处理器可以执行的同时发送的数量。这可能是一个相当高的数字，而且它通常不能代表实际应用中实现的通信速率。

总线

我们考虑的第一个互连设计是让所有的处理器位于同一内存总线上。这种设计将所有处理器直接连接到同一个内存池，因此它提供了一个UMA或SMP模型。

使用总线的主要缺点是可扩展性有限，因为每次只有一个处理器可以进行内存访问。为了克服这个问题，我们需要假设处理器的速度比内存慢，或者处理器有缓存或其他本地内存来操作。在后一种情况下，通过让处理器监听总线上的所有内存流量，维持缓存一致性是很容易的，这个过程被称为「监听」（snooping）。

线性阵列和环状网络

连接多个处理器的一个简单方法是将它们连接成一个「线性阵列」（linear array）：每个处理器都有一个编号$i$，处理器$Pi$与$P{i-1}$和$P_{i+1}$相连。第一个和最后一个处理器是可能的例外情况：如果它们相互连接，我们称该架构为环状网络（ring network）。

这个方案要求每个处理器有两个网络连接，所以设计相当简单。

练习2.31 线性阵列的二分宽度是什么？环状网络的二分宽度是什么？

练习2.32 由于线性数组的连接有限，你可能必须对并行算法进行巧妙的编程。例如，考虑一个 “广播 “操作：处理器0有一个数据项需要发送给其他每个处理器。

我们做了以下简化的假设。

  • 一个处理器可以同时发送任意数量的信息。

  • 但一条线一次只能携带一条信息；然而。

  • 任何两个处理器之间的通信都需要单位时间，不管它们之间有多少个处理器。

在一个「全连接」（fully connected）的网络或一个「星型」（star）网络中，你可以很容易地写出：

  1. for 𝑖 = 1 ... 𝑁 − 1:
  2.     send the message to processor 𝑖

假设一个处理器可以发送多个消息，即操作是一步到位的。现在考虑一个线性阵列。说明即使有这种无限的发送能力，上述算法也会因为拥堵而遇到麻烦。

请你尝试找到一个更好的方法来组织发送操作。提示：假装你的处理器是以二叉树的形式连接的。假设有$𝑁=2^n-1$个处理器。证明广播可以在对数$N$个阶段内完成，并且处理器只需要能够同时发送一条信息即可。

这个练习是一个将 “逻辑 “通信模式嵌入物理模式的例子。

二维和三维阵列、环面

一种流行的并行计算机设计是将处理器组织在一个二维或三维的「笛卡尔网状」（Cartesian mesh）网络中。这意味着每个处理器都有一个坐标$（i, j）$或$（i, j, k）$，并且它在所有坐标方向上都与邻居相连。处理器的设计还是相当简单的：网络连接的数量（连接图的度数）是网络的空间维数（2或3）的两倍。

拥有二维或三维网络是一个相当自然的想法，因为我们周围的世界是三维的，而且计算机经常被用来模拟现实生活的现象。如果我们暂时接受物理模型需要近邻型通信（我们将在第4.2.3节看到这种情况），那么网状计算机是运行物理模拟的自然候选者。

练习2.33 $n \times n \times n$处理器的三维立方体的直径是多少？二分宽度是多少？如果增加环绕环状的连接，会有什么变化？

练习 2.34 你的并行计算机的处理器被组织成一个二维网格。芯片制造商推出了一种具有相同时钟速度的新芯片，它是双核的，而不是单核的，而且可以装在现有的插槽上。批评以下论点：”每秒钟可以完成的工作量（不涉及通信）增加了一倍；由于网络保持不变，二分带宽也保持不变，所以我可以合理地期望我的新机器变得两倍快”。

基于网格的设计通常有所谓的环绕或环形连接，它连接二维网格的左右两边，以及顶部和底部。这在图2.19中有所说明。

torus

一些计算机设计声称是高维度的网格，例如5D，但这里并不是所有的维度都是平等的。例如，一个3D网格，其中每个节点是一个四插槽四核，可以被认为是一个5D网格。然而，最后两个维度是完全相连的。

超立方体

上面我们根据近邻通信的普遍性，对网状组织处理器的适用性做了一个挥手的论证。然而，有时会发生在随机处理器之间的发送和接收。这方面的一个例子就是上面提到的广播。由于这个原因，它希望有一个比网状网络直径小的网络。另一方面，我们希望避免全连接网络的复杂设计。

hypercubes

一种不错的解决方案是「超立方体」（hypercube）设计。一个$n$维的超立方体计算机有$2^n$个处理器，每个处理器在每个维度上都与另一个处理器相连；见图2.21。

一个简单的描述方法是给每个处理器一个由$𝑑$位组成的地址：我们给超立方体的每个节点一个数字，这个数字是描述它在立方体中的位置的比特模式；见图 2.20。

hypercubenumber

有了这个编号方案，一个处理器就会与其他所有地址正好相差一位的处理器连接起来。这意味着，与网格不同的是，一个处理器的邻居的号码并不是相差1或$\sqrt P$，而是相差1,2,4,8,….。

超立方体设计的最大优点是直径小，通过网络的流量容量大。

练习2.35 超立方体的直径是多少？二分宽度是多少？

该方案的一个缺点是，处理器的设计取决于机器的总尺寸。在实践中，处理器会被设计成可能的最大连接数，而购买较小机器的人就会为未使用的容量买单。另一个缺点是，扩展一台给定的机器只能通过加倍来实现：$2^p$以外的其他尺寸是不可能的。

练习2.36 考虑第2.1节中的并行求和例子，并给出在超立方体上并行实现的执行时间。证明在超立方体上的执行可以达到该例子的理论速度（最多一个系数）。在超立方体中嵌入网格上面我们提出了一个论点，即网格连接的处理器是许多物理现象建模应用的合理选择。超立方体看起来不像网格，但它们有足够的连接，可以通过忽略某些连接来简单地假装成网格。

比方说，我们想要一个一维数组的结构：我们想要有编号的处理器，这样处理器𝑖可以直接向𝑖 - 1和𝑖 + 1发送数据。我们不能像图2.20中那样使用明显的节点编号。例如，节点1与节点0直接相连，但与节点2的距离为2。节点3在一个环中的右邻，节点4，甚至在这个超立方体中的最大距离为3。显然，我们需要以某种方式对节点重新编号。

我们将展示的是，有可能在超立方体中行走，精确地触摸每个角落，这相当于在超立方体中嵌入一个一维网格。

Gray codes

这里的基本概念是一个（二进制反映的）「格雷编码」（Gray code）[87]。这是一种将二进制数$0…2^{𝑑-1}$排序为$𝑔0,…𝑔{2𝑑-1}$的方法，即$𝑔𝑖$和$𝑔{𝑖+1}$只相差一个比特。显然，普通的二进制数并不满足这一点：1和2的二进制表示已经有两个比特的差异。为什么格雷编码能帮助我们？因为$𝑔𝑖$和$𝑔{𝑖+1}$只相差一位，这意味着它们是超立方体中直接相连的节点数。

hypercubegraynumber

图2.22说明了如何构建一个格雷编码。这个过程是递归的，可以正式描述为 “将立方体分为两个子立方体，对一个子立方体进行编号，交叉到另一个子立方体，并按照第一个子立方体的相反顺序对其节点进行编号”。二维立方体的结果如图2.23所示。

由于格雷编码为我们提供了一种将一维 “网状 “嵌入超立方体的方法，我们现在可以继续往上做。

练习2.37 显示如何将一个$2^{2d}$节点的正方形网格嵌入到一个超立方体中，方法是将两个2𝑑节点的立方体嵌入的比特模式相加。你如何容纳一个$2^{d_1+d_2}$节点的网格？一个由$2^{d_1+d_2+d_3}$个节点组成的三维网格？

交换机网络

上面我们简要地讨论了完全连接的处理器。然而，通过在所有处理器之间制作大量的总线来进行连接是不切实际的。然而，还有另一种可能性，即通过将所有处理器连接到一个「交换机」（switch）或「交换机网络」（switch network）。一些流行的网络设计是「交叉开关」（Cross bar）、「蝶形交换」（butterfly exchange）和「胖树」（fat tree.）。

交换机网络是由交换元件组成的，每个交换元件都有少量（最多十几个）的入站和出站链接。通过将所有的处理器连接到一些交换元件上，并有多个交换阶段，那么就有可能通过网络的路径连接任何两个处理器。

交叉开关

最简单的开关网络是一个交叉开关，由$𝑛$水平线和垂直线组成，每个交叉点上都有一个开关元件，决定这些线是否连接在一起；见图2.24。如果我们把横线指定为输入，竖线指定为输出，这显然是让$𝑛$输入映射到$𝑛$输出的一种方式。每一个输入和输出的组合（有时称为 “排列组合”）都是允许的。

这种类型的网络的一个优点是，没有任何连接可以阻挡另一个连接。主要的缺点是开关元素的数量是$n^2$，是处理器数量$n$的一个快速增长的函数。

crossbar

蝶形交换

蝶形交换网络是由小型交换元件构成的，它们有多个阶段：随着处理器数量的增加，阶段的数量也随之增加。图2.25显示了连接2、4和8个处理器的蝶形网络，每个处理器有一个本地存储器。(另外，你可以把所有的处理器放在网络的一边，而把所有的存储器放在另一边）。

正如在图2.26中所示，蝶形交换允许几个处理器模拟访问内存。而且，它们的访问时间是相同的，所以交换网络是实现UMA结构的一种方式；见2.4.1节。有一台基于Butterfly交换网络的计算机是BBN Butterfly（http://en.wikipedia.org/wiki/BBN_Butterfly）。在2.7.7.1节中，我们将看到这些想法是如何在一个实际的集群中实现的。

练习 2.38 对于简单的交叉开关和蝶形交换，随着处理器数量的增加网络需要扩展。给出两种情况下连接$𝑛$处理器和存储器所需的导线数量（某种单位长度）和交换元件的数量。一个数据包从存储器到处理器所需的时间，用穿越单位长度的导线和穿越开关元件的时间表示是多少？

butterflys

通过蝶形交换网络的数据包路由是基于考虑目的地地址的位数来完成的。在第𝑖层，考虑第𝑖个数字；如果是1，则选择开关的左出口，如果是0，则选择右出口。这在图2.27中有所说明。如果我们把存储器连接到处理器上，如图2.26所示，我们只需要两个比特（到最后一个开关），但还需要三个比特来描述反向路线。

胖树

如果我们像树一样连接交换节点，那么在靠近根部的地方就会出现很大的拥堵问题，因为只有两根线连接到根注。假设我们有一棵$𝑘$级树，所以有$2^𝑘$个叶子节点。如果左边子树上的所有叶子节点都试图与右边子树上的节点通信，我们就有$2{𝑘-1}$条信息通过一条线进入根部，同样也通过一条线出去。胖树是一个树状网络，每一级都有相同的总带宽，这样就不会出现这种拥堵问题：根部实际上会有$2^{𝑘-1}$条进线和出线连接[88]。图2.28在左边显示了这种结构；右边显示了Stampede集群的一个机柜，机柜的上半部和下半部有一个叶子开关。

butterfly3

第一个成功的基于胖树的计算机结构是连接机CM5。

在胖树中，就像在其他交换网络中一样，每个信息都带有自己的路由信息。由于在胖树中，选择仅限于上升一级，或者切换到当前级别的其他子树上，因此一条信息需要携带的路由信息的位数与级别相同，对于$𝑛$处理器来说是$\log_2𝑛$。

练习 2.39 证明胖子树的分叉宽度是$𝑃/2$，其中$𝑃$是亲子叶子节点的数量。提示：说明只有一种方法可以将胖树连接的处理器集合分割成两个连接的子集。

[142]中对胖树的理论阐述表明，胖树在某种意义上是最优的：它可以像任何其他需要相同空间来构建的网络一样快速传递信息（最多对数因素）。这个说法的基本假设是，离根更近的开关必须连接更多的线，因此需要更多的组件，相应地也就更大。这个论点虽然在理论上很有趣，但没有实际意义，因为网络的物理尺寸在目前最大的使用胖树互连的计算机中几乎没有起到作用。例如，在德克萨斯大学奥斯汀分校的TACC Frontera集群中，只有6个核心交换机（即容纳胖树最高层的机柜），连接91个处理器机柜。

如上图所示，胖树的建设成本很高，因为每下一级都必须设计一个新的、更大的交换机。因此，在实践中，一个具有胖子树特征的网络是由简单的开关元件构成的；见图2.29。这个网络的带宽和路由可能性与胖树相当。路由算法会稍微复杂一些：在胖树中，一个数据包只能以一种方式上升，但在这里，一个数据包必须知道要路由到两个较高的交换机中的哪个。

这种类型的交换网络是Clos网络的一种情况[34]。

超额订购和争夺

在实践中，胖树网络不使用2进2出的元件，而是使用20进20出的开关。这使得网络中的层数有可能被限制在3或4个。(顶层交换机被称为脊柱卡）。

在这种情况下，网络分析的一个额外的复杂因素是超额订购的可能性。网卡中的端口可以配置为输入或输出，而只有总数是固定的。因此，一个40端口的交换机可以被配置为20进20出，或者21进19出，等等。当然，如果所有连接到交换机的21个节点同时发送，19个出端口将限制带宽。

还有一个问题。让我们考虑建立一个小型集群，交换机配置为有$𝑝$入端口和$w$出端口，这意味着我们有$𝑝+𝑤$端口交换机。图2.30描述了两个这样的开关，总共连接了$2^𝑝$个节点。如果一个节点通过交换机发送数据，它对$𝑤$条可用导线的选择由目标节点决定。这就是所谓的输出路由。

显然，我们只能期望$𝑤$个节点能够在有信息碰撞的情况下进行发送，因为这就是交换机之间可用导线的数量。然而，对于许多$𝑤$目标的选择，无论如何都会有对导线的争夺。这就是生日悖论的一个例子。

练习 2.40 考虑上述架构，$p$个节点通过切换间的$w$线发送。编一个模拟代码，其中$p$个节点中的$w’\leqslant w$向一个随机选择的目标节点发送一个信息。作为$w’$、$w$、$p$的函数，碰撞的概率是多少？找到一种方法来制表或绘制数据。

作为反馈，请给出简单情况下$w’ = 2$的统计分析。

fattree5

stampede_leaf

fattree-clos

集群网络

上面的讨论有些抽象，但在现实生活中的集群中，你可以实际看到网络设计的体现。例如，肥大的树形集群网络会有一个中央机柜，对应树形中的最高层。图2.31显示了TACC Ranger（已不再使用）和Stampede集群的交换机。在第二张图片中可以看出，实际上有多个冗余的胖树网络。

另一方面，像IBM BlueGene这样基于环状网络的集群，看起来将是一个相同机柜的集合，因为每个机柜都包含网络的一个相同部分；见图2.32。

案例研究: Stampede

作为实践中联网的一个例子，让我们考虑一下德克萨斯高级计算机中心的Stampede集群，它是一个多根多级的胖树。

contention

  • 每个机架由2个机箱组成，每个机箱有20个节点。

  • 每个机箱都有一个叶子开关，它是一个内部的横杆，使机箱中的节点之间有完美的连接性。

  • 叶子交换机有36个端口，其中20个连接到节点，16个向外。这种超额订阅意味着最多只有16个节点在机箱外通信时可以拥有完美的带宽。

  • 有8个中心交换机，作为8个独立的胖树根发挥作用。每个机箱通过两个连接到每个中央交换机的 “叶卡”，正好占用了16个出站端口。
  • 每个中心交换机有18个针卡，每个针卡有36个端口，每个端口连接到不同的叶卡。
  • 每台中央交换机有36个叶卡，18个端口连接到叶子交换机，18个端口连接到脊柱卡。这意味着我们可以支持648个机箱，其中640个被实际使用。

网络中的一个优化是，与同一叶卡的两个连接进行通信，没有较高树级的延迟。这意味着，一个机箱中的16个节点和另一个机箱中的16个节点可以有完美的连接。

然而，对于静态路由，如Infiniband中使用的路由，有一个与每个目的地相关的固定端口。(目的地到端口的这种映射在每个交换机的路由表中）。 因此，对于20个可能的目的地中的16个节点的某些子集，将有完美的带宽，但其他子集将看到两个目的地的流量通过同一个端口。

案例研究：Cray Dragonfly网络

Cray的蜻蜓网络是一个有趣的实际妥协。上面我们说过，一个完全连接的网络将太过昂贵，无法扩大规模。然而，如果数量保持有限的话，拥有一个完全连接的处理器集合是可能的。蜻蜓设计使用小的完全连接的组，然后将这些组组成一个完全连接的图。

这引入了一个明显的不对称性，因为一个组内的处理器拥有更大的带宽，而组与组之间则没有。然而，由于动态路由，信息可以采取非最小路径，通过其他组进行路由。这可以缓解争夺问题。

rangerswitch

stampedeswitches

带宽和延迟

上面所说的发送信息可以被认为是一个单位时间的操作，当然是不现实的。一个大的信息比一个短的信息需要更长的时间来传输。有两个概念可以对传输过程进行更现实的描述；我们已经在1.3.2节中看到了在处理器的缓存层之间传输数据的情况。

  • 延迟 在两个处理器之间建立通信需要花费大量时间，这与信息大小无关。这所花费的时间被称为信息的延时。造成这种延迟的原因有很多。
    • 两个处理器进行 “握手”，以确保收件人已经准备好，并且有适当的缓冲空间来接收信息。
    • 信息需要由发送方进行编码传输，并由接收方进行解码。
    • 实际传输可能需要时间：并行计算机通常足够大，即使在光速下，信息的第一个字节也需要数百个周期来穿越两个处理器之间的距离。
  • 带宽 在两个处理器之间的传输开始后，主要的数字是每秒可通过通道的字节数。这就是所谓的带宽。带宽通常可由信道速率（物理链路可传送比特的速率）和信道宽度（链路中物理线的数量）决定。信道宽度通常是16的倍数，通常为64或128。这也可以表示为，一个通道可以同时发送一个或两个8字节的字。

bluegenellnl

带宽和延迟被正式定义为 $$ T(n)=\alpha+\beta n $$ 为一个$n$字节的信息的传输时间。这里，$\alpha$是延迟，$\beta$是每字节的时间，也就是带宽的倒数。有时我们会考虑涉及通信的数据传输，例如在集体操作的情况下；见6.1节。然后我们将传输时间公式扩展为 $$ T(n)=\alpha+\beta n +\gamma n $$ 其中$\gamma$是每次操作的时间，也就是计算率的倒数。

也可以将这个公式细化为 $$ T(n,p) = \alpha+\beta n+\delta p $$ 其中$𝑝$是所穿越的网络 “「跳」（hops）”。然而，在大多数网络中，$\delta$的值远远低于$\alpha$的值，所以我们在这里将忽略它。另外，在胖树网络中，跳数是$\log𝑃$的数量级，其中$𝑃$是处理器的总数，所以它无论如何都不可能很大。

并行计算中的局部性

在第1.6.2节中，你发现了关于单处理器计算中的位置性概念的讨论。并行计算中的位置性概念包括所有这些以及更多的层次。

  • 核心之间：私有缓存 现代处理器上的核心有私有相干缓存。这意味着你似乎不必担心位置性问题，因为无论数据在哪个缓存中都可以访问。然而，维持一致性需要花费带宽，所以最好是保持访问的本地化。
  • 内核之间：共享高速缓存 内核之间共享的高速缓存是一个不需要担心位置性的地方：这是处理核心之间真正对称的内存。
  • 在插槽之间：节点（或主板）上的插槽在程序员看来是共享内存的，但这实际上是NUMA访问（2.4.2节），因为内存与特定的插槽相关。
  • 通过网络结构：有些网络有明显的位置效应。你在第2.7.1节中看到了一个简单的例子，一般来说，很明显，任何网格型网络都会有利于 “附近 “处理器之间的通信。基于胖树的网络似乎不存在这样的争论问题，但是层次引起了不同形式的定位性。比节点上的局域性高一级，小群的节点通常由一个叶子开关连接，它可以防止数据进入中央开关。