第 3 章 并行化 Sun C 代码

Sun C 编译器可以优化代码，以便在 SPARC 共享内存的多处理器计算机上运行。该进程称为并行化。编译的代码可以使用系统上的多个处理器以并行方式执行。本章阐述如何利用编译器的并行化功能。

3.1 概述

C 编译器为那些它确定可以安全进行并行化的循环生成并行代码。通常，这些循环具有彼此独立的迭代。对于此类循环，迭代以什么顺序执行或者是否并行执行并不重要。虽然不是全部，但是许多向量循环都属于此种类。

由于 C 中使用别名的方式，难以确定并行化的安全。为帮助编译器，Sun C 提供了 pragma 和附加指针限定，以提供程序员知道但编译器无法确定的别名信息。有关更多信息，请参见第 5 章，基于类型的别名分析。

3.1.1 使用示例

以下示例说明了如何启用和控制并行化 C：

% cc -fast -xO4 -xautopar example.c -o example

这将生成一个称为 example 的可正常执行的可执行程序。如果要利用多处理器执行，请参见B.2.69 -xautopar。

3.2 OpenMP 并行化

您可以编译代码，以便使它符合 OpenMP 规范。有关针对 C 的 OpenMP 规范的详细信息，请访问 web 站点 http://www.openmp.org/specs/。

要利用编译器的 OpenMP 支持，您需要执行编译器的 -xopenmp 选项。请参见B.2.118 -xopenmp[= i]。

有关标准的指令的迁移信息，请参见《OpenMP API 用户指南》。

3.2.1 处理 OpenMP 运行时警告

OpenMP 运行时系统可针对非致命错误发出警告。使用以下函数注册一个回调函数以处理这些警告：

int sunw_mp_register_warn(void (*func) (void *) )

您可以通过对 <sunw_mp_misc.h> 发出 #include 预处理程序指令来访问该函数的原型。

如果不想注册函数，请将环境变量 SUNW_MP_WARN 设置为 TRUE，警告消息将发送给 stderr。有关 SUNW_MP_WARN 的更多信息，请参见SUNW_MP_WARN。

有关特定于此 OpenMP 实现的信息，请参见《OpenMP API 用户指南》。

3.3 环境变量

与并行化 C 相关的环境变量有四种：

• PARALLEL

• SUNW_MP_THR_IDLE

• SUNW_MP_WARN

• STACKSIZE

3.3.1 PARALLEL

如果您可以利用多处理器执行，请设置 PARALLEL 环境变量。PARALLEL 环境变量指定可供程序使用的处理器数。在下例中，PARALLEL 设置为 2：

% setenv PARALLEL 2

如果目标机器具有多个处理器，线程可以映射到独立的处理器。运行该程序将导致创建执行程序的并行化部分的两个线程。

3.3.1.1 SUNW_MP_THR_IDLE

目前，程序的起始线程创建绑定线程。绑定线程一旦创建，将会参与执行程序的并行部分（并行循环、并行区域等），并在程序的串行部分运行时保持旋转等待状态。在程序终止之前，这些绑定线程不会休眠或停止。并行化程序在专用系统上运行时，使这些线程保持旋转等待状态通常可达到最佳性能。不过，保持旋转等待的线程会占用系统资源。

使用 SUNW_MP_THR_IDLE 环境变量控制每个线程在完成其一份并行作业后的状态。

% setenv SUNW_MP_THR_IDLE value

您可以用 spin 或 sleep[n s|n ms] 替换 value。缺省值为 spin，表示线程在完成一份并行任务之后应保持旋转（或忙等待）状态，直到新的一份并行任务到来为止。

另一个选项 sleep[n s|n ms] 在旋转等待 n 个单位时间后使线程进入休眠状态。等待单位可以是秒（s，为缺省单位）或毫秒 (ms)，其中 1s 表示 1 秒；10ms 表示 10 毫秒。不带参数的 sleep 在线程完成并行任务后使线程立即进入休眠状态。sleep、sleep0、sleep0s 和 sleep0ms 均等效。

如果新作业在达到 n 个单位时间之前到达，线程将停止旋转等待并开始执行新作业。如果 SUNW_MP_THR_IDLE 包含非法值或未设置值，那么 spin 用作缺省值。

SUNW_MP_WARN

将此环境变量设置为 TRUE，可打印来自 OpenMP 和其他并行化运行时系统的警告消息。

% setenv SUNW_MP_WARN TRUE

如果通过使用 sunw_mp_register_warn() 注册某个函数来处理警告消息，那么即使将 SUNW_MP_WARN 设置为 TRUE，它也不会打印警告消息。如果未注册函数，但已将 SUNW_MP_WARN 设置为 TRUE，SUNW_MP_WARN 会将警告消息打印至 stderr。如果您未注册函数且未设置 SUNW_MP_WARN，则不会发出警告消息。有关 sunw_mp_register_warn() 的更多信息，请参见3.2.1 处理 OpenMP 运行时警告。

STACKSIZE

正在执行的程序会为主线程保留一个主内存栈，同时为每个从属线程保留不同的栈。栈是临时内存地址空间，用来存储子程序调用中的参数和自动变量。

主栈的缺省大小约为 8 兆字节。使用 limit 命令显示当前主栈大小并对其进行设置。

% limit
cputime unlimited
filesize unlimited
datasize 2097148 kbytes
stacksize 8192 kbytes <- current main stack size
coredumpsize 0 kbytes
descriptors 256
memorysize unlimited
% limit stacksize 65536 <- set main stack to 64Mb

多线程程序的每个从属线程均具有其自身的线程栈。该栈与主线程的主栈相似，但对该线程是唯一的。线程的私有数组和变量（对于线程是局部的）在线程栈中进行分配。

所有从属线程的栈大小都相同，缺省情况下，对于 32 位应用程序为 4MB，对于 64 位应用程序为 8MB。可以用环境变量 STACKSIZE 来设置该大小：

% setenv STACKSIZE 16483 <- Set thread stack size to 16 Mb

对于某些已并行的代码，可能需要将线程栈大小设置为比缺省值大的值。

有时，编译器会生成一条警告消息，指出需要更大的栈大小。然而，除了通过尝试并出错之外，不可能知道应设置多大的栈大小正合适，尤其是涉及私有/局部数组时。如果栈太小导致线程无法运行，程序将异常终止并出现段故障。

3.3.1.2 关键字

关键字 restrict 可以与并行化 C 配合使用。正确使用关键字 restrict 有助于优化器了解所需数据的别名，从而确定代码序列是否可以并行化。有关详细信息，请参阅D.1.2 C99 关键字。

3.4 数据依赖性和干扰

C 编译器通过分析程序中的循环来确定并行执行循环的不同迭代是否安全。分析的目的是确定循环的两次迭代之间是否会相互干扰。通常，如果变量的一次迭代读取某个变量而另一次迭代正在写入该变量，会发生干扰。考虑以下程序片段：

示例 3–1 带依赖性的循环

for (i=1; i < 1000; i++) {
    sum = sum + a[i]; /* S1 */
}

在3.4 数据依赖性和干扰中，任意两次连续迭代，第 i 次和第 i+1 次，将写入和读取同一变量 sum。因此，为了并行执行这两次迭代，需要以某种形式锁定该变量。否则，允许并行执行这两次迭代不安全。

然而，使用锁定会产生可能降低程序运行速度的开销。C 编译器通常不会并行化3.4 数据依赖性和干扰中所示的循环。在3.4 数据依赖性和干扰中，循环的两次迭代之间存在数据依赖性。考虑另一个示例：

示例 3–2 不带依赖性的循环

for (i=1; i < 1000; i++) {
    a[i] = 2 * a[i]; /* S1 */
}

在此情况下，循环的每次迭代均引用不同的数组元素。因此，循环的不同迭代可以按任意顺序执行。由于不同迭代的两个数据元素不可能相互干扰，因此它们可以并行执行而无需任何锁定。

编译器为确定一个循环的两次不同迭代是否引用相同变量而执行的分析称为数据依赖性分析。如果其中一个引用写入变量，数据依赖性阻止循环并行化。编译器执行的数据依赖性分析有三种结果：

• 存在依赖性。在此情况下，并行执行循环不安全。3.4 数据依赖性和干扰说明了此情况。

• 不存在依赖性。循环可使用任意数目的进程安全地并行执行。3.4 数据依赖性和干扰说明了此情况。

• 无法确定依赖性。为安全起见，编译器假定存在阻止并行执行循环的依赖性，并且不会并行化循环。

在3.4 数据依赖性和干扰中，循环的两次迭代是否写入数组 a 的同一元素取决于数组 b 是否包含重复元素。除非编译器可以确定实际情况，否则它假定存在依赖性并且不会并行化循环。

示例 3–3 可能包含也可能不包含依赖性的循环

for (i=1; i < 1000; i++) {
    a[b[i]] = 2 * a[i];
}

3.4.1 并行执行模型

循环的并行执行由 Solaris 线程完成。启动程序的初始执行的线程称为主线程。程序启动时，主线程创建多个从属线程，如下图所示。程序结束时，所有从属线程均终止。从属线程的创建只进行一次，以使开销减至最小。

图 3–1 主线程和从属线程

程序启动后，主线程开始执行程序，而从属线程保持空闲等待状态。当主线程遇到并行循环时，循环的不同迭代将会在启动循环执行的从属线程和主线程之间分布。在每个线程完成其块的执行之后，将与剩余线程保持同步。此同步点称为障碍。在所有线程完成其工作并到达障碍之前，主线程不能继续执行程序的剩余部分。从属线程在到达障碍之后进入等待状态，等待分配更多的并行工作，而主线程继续执行该程序。

在此期间，可发生多种开销：

• 同步和工作分配的开销

• 障碍同步的开销

通常存在某些特殊的并行循环，为其执行的有用工作量不足以证明开销是值得的。对于此类循环，其运行速度会明显减慢。在下图中，循环是并行化的。然而，障碍（以水平条表示）带来大量开销。如图所示，障碍之间的工作串行或并行执行。并行执行循环所需的时间比主线程和从属线程在障碍处同步所需的时间少得多。

图 3–2 循环的并行执行

3.4.2 私有标量和私有数组

对于某些数据依赖性，编译器仍能够并行化循环。考虑以下示例。

示例 3–4 带依赖性的可并行化循环

for (i=1; i < 1000; i++) {
    t = 2 * a[i];           /* S1 */
    b[i] = t;               /* S2 */
}

在本例中，假定数组 a 和 b 为非重叠数组，而由于变量 t 的存在而使任意两次迭代之间存在数据依赖性。在第一次迭代和第二次迭代时执行以下语句。

示例 3–5 第一次迭代和第二次迭代

t = 2*a[1];  /* 1 */
b[1] = t;    /* 2 */
t = 2*a[2];  /* 3 */
b[2] = t;    /* 4 */

由于第一个语句和第三个语句会修改变量 t，因此编译器无法并行执行它们。不过，t 的值始终在同一次迭代中计算并使用，因此编译器可以对每次迭代使用 t 的一个单独副本。这消除了不同迭代之间由于此类变量而产生的干扰。事实上，我们已使变量 t 成为执行迭代的每个线程的私有变量。这种情形可以说明如下：

示例 3–6 变量 t 作为每个线程的私有变量

for (i=1; i < 1000; i++) {
    pt[i] = 2 * a[i];       /* S1 */
    b[i] = pt[i];           /* S2 */
}

3.4.2 私有标量和私有数组中的示例与3.4 数据依赖性和干扰中的示例基本相同，但是每个标量变量引用 t 现在被替换为数组引用 pt。现在，每次迭代使用 pt 的不同元素，因此消除了任意两次迭代之间的所有数据依赖性。当然，本示例产生的一个问题是可能导致数组非常大。在实际运用中，编译器为参与循环执行的每个线程只分配变量的一个副本。事实上，每个此类变量是线程的私有变量。

编译器还可以私有化数组变量，以便为循环的并行执行创造机会。请看以下示例：

示例 3–7 带数组变量的可并行化循环

for (i=1; i < 1000; i++) {
    for (j=1; j < 1000; j++) {
            x[j] = 2 * a[i];        /* S1 */
            b[i][j] = x[j];         /* S2 */
    }
}

在3.4.2 私有标量和私有数组中，外部循环的不同迭代修改数组 x 的相同元素，因此外部循环不能并行化。不过，如果执行外部循环迭代的每个线程均具有整个数组 x 的私有副本，那么外部循环的任意两次迭代之间不存在干扰。这种情形说明如下：

示例 3–8 使用私有化数组的可并行化循环

for (i=1; i < 1000; i++) {
    for (j=1; j < 1000; j++) {
            px[i][j] = 2 * a[i];    /* S1 */
            b[i][j] = px[i][j];     /* S2 */
    }
}

如私有标量的情形一样，不必要为所有迭代展开数组，而只需要达到系统中执行的线程数。这由编译器自动完成，方式是在每个线程的私有空间中分配初始数组的一个副本。

3.4.3 返回存储

变量私有化对改进程序中的并行性十分有用。然而，如果在循环外部引用私有变量，则编译器需要确保私有变量具有正确的值。请看以下示例：

示例 3–9 使用返回存储的并行化循环

for (i=1; i < 1000; i++) {
    t = 2 * a[i];           /* S1 */
    b[i] = t;               /* S2 */
}
x = t;                      /* S3 */

在3.4.3 返回存储中，在语句 S3 中引用的 t 值是循环计算的最终 t 值。在变量 t 私有化并且循环完成执行之前，需要重新将 t 的正确值存储到初始变量中。这称为返回存储。此操作通过将最后一次迭代中的 t 值重新复制到变量 t 的初始位置来完成。在很多情况下，编译器自动执行此操作。但是也存在不易计算最终值的情况：

示例 3–10 不能使用返回存储的循环

for (i=1; i < 1000; i++) {
    if (c[i] > x[i] ) {         /* C1 */
            t = 2 * a[i];           /* S1 */
            b[i] = t;               /* S2 */
    }
}
x = t*t;                       /* S3 */

正确执行后，语句 S3 中的 t 值通常并不是循环最终迭代中的 t 值。事实上，它是条件 C1 为真时的最后一次迭代。通常，计算 t 的最终值十分困难。在类似情况下，编译器不会并行化循环。

3.4.4 约简变量

有时循环的迭代之间存在真正的依赖性，而导致依赖性的变量并不能简单地私有化。例如，从一次迭代到下一次迭代累计值时，会出现这种情况。

示例 3–11 可以或不可以并行化的循环

for (i=1; i < 1000; i++) {
    sum += a[i]*b[i]; /* S1 */
}

在3.4.4 约简变量中，循环计算两个数组的向量乘积，并将结果赋给一个称为 sum 的公共变量。该循环不能以简单的方式并行化。编译器可以利用语句 S1 中计算的关联特性，并为每个线程分配一个称为 psum[i] 的私有变量。变量 psum[i] 的每个副本均初始化为 0。每个线程以自己的变量 psum[i] 副本计算自己的部分和。执行循环之前，所有部分和均加到初始变量 sum 上。在本示例中，变量 sum 称为约简变量，因为它计算和约简。然而，将标量变量提升为约简变量存在的危险是：累计舍入值的方式会更改 sum 的最终值。只有在您专门授权这样做时，编译器才执行该变换。

3.5 加速

如果编译器不并行化所花时间量占主体的程序部分，则不会发生加速。这基本上是 Amdahl 定律的推论。例如，如果并行化一个占用程序执行时间的百分之五的循环，则总加速仅限于百分之五。然而，根据工作量和并行执行开销的大小，可能没有任何改善。

一般说来，并行化的程序执行所占的比例越大，加速的可能性就越大。

每个并行循环都会在启动和关闭期间发生少量开销。启动开销包括工作分配代价，关闭开销包括障碍同步代价。如果循环执行的工作总量不足够大，则不会发生加速。事实上，循环甚至可能减慢。因此，如果大量程序执行工作由许多短并行循环完成，则整个程序可能减慢而不是加速。

编译器执行几个试图增大循环粒度的循环变换。其中某些变换是循环交换和循环合并。因此，一般说来，如果程序中的并行量很小或者分散在小并行区域，则加速很少。

通常，按比例增大问题大小可提高程序中的并行程度。例如，考虑包含以下两部分的问题：按顺序的二次部分，以及可并行化的三次部分。对于此问题，工作量的并行部分的增长速度比顺序部分的增长速度快。因此在某些点，除非达到资源限制，否则问题可以大大加速。

尝试进行某些调节，使用指令、问题大小进行试验，重新构造程序，以便从并行 C 中获益。

3.5.1 Amdahl 定律

固定问题大小加速通常遵守 Amdahl 定律。Amdahl 定律明确说明：给定问题中的并行加速量受问题的顺序部分的限制。以下方程式描述问题的加速，其中 F 是在顺序区域花费的时间，剩余时间可均匀分摊到 P 个处理器。如果方程式的第二项减小到零，则总加速受第一项约束，保持固定。

下图以图表方式说明此概念。深色阴影部分表示程序的顺序部分，并且对于 1、2、4、8 个处理器均保持不变。浅色阴影部分代表程序的并行部分，可均匀地分摊在任意多个处理器之间。

图 3–3 固定问题加速

随着处理器数目的增加，每个程序并行部分所需的时间会减少，而每个程序串行部分所需的时间保持不变。

然而，实际上可能会发生由于通信以及向多个处理器分配工作而产生的开销。对于使用的任意多个处理器，这些开销可能固定，也可能不固定。

下图说明一个包含 0%、2%、5% 和 10% 顺序部分的程序的理想加速。此处假定无开销。

图 3–4 Amdahl 定律加速曲线

显示一个包含 0%、2%、5% 和 10% 顺序部分的程序的理想加速（假定无开销）的图。x 轴表示处理器的数目，y 轴表示加速。

3.5.1.1 开销

一旦将开销加入此模型中，加速曲线会发生很大的变化。为了方便说明，我们假定开销包括以下两部分：独立于处理器数的固定部分，以及随使用的处理器数呈二次增长的非固定部分：

1 除以 S 等于 1 除以下列数值之和：F 加上左括号 1 减去 F 除以 P 右括号加上 K（下标 1）加上 K（下标 2）乘以 P 的平方。

在此方程式中，K₁ 和 K₂ 是固定因子。在这些假定下，加速曲线如下图所示。值得注意的是，在此情况下，加速达到峰值。在某个点之后，增加更多处理器会降低性能，如下图所示。

图 3–5 带开销的加速曲线

此图显示：使用 5 个处理器时所有程序到达最高加速，然后添加到多达 8 个处理器时即会失去此加速优势。x 轴表示处理器的数目，y 轴表示加速。

3.5.1.2 Gustafson 定律

Amdahl 定律可能会在预测真实问题的并行加速时造成误导。花费在程序的顺序部分的时间有时取决于问题大小。也就是说，通过按比例缩放问题大小，您可以获得更多加速机会。以下示例说明了这一点。

示例 3–12 按比例缩放问题大小可能会获得更多加速机会

/*
* initialize the arrays
*/
for (i=0; i < n; i++) {
    for (j=0; j < n; j++) {
            a[i][j] = 0.0;
            b[i][j] = ...
            c[i][j] = ...
    }
}
/*
* matrix multiply
*/
for (i=0; i < n; i++) {
    for(j=0; j < n; j++) {
            for (k=0; k < n; k++) {
                a[i][j] = b[i][k]*c[k][j];
            }
    }
}

假定理想的开销为零，并假定只有第二个循环嵌套并行执行。不难发现，对于较小的问题大小（即 n 的值较小），程序的顺序部分和并行部分所用的时间彼此相差并不大。然而，随着 n 值的增大，花费在程序并行部分的时间比花费在顺序部分的时间增长得更快。对于此问题，随问题大小的增大而增加处理器数很有益。

3.6 负载平衡和循环调度

循环调度是将并行循环的迭代分布到多个线程的进程。为获得最大加速，在线程间均匀地分布工作而不产生太大开销十分重要。编译器针对不同情况提供多种调度类型。

3.6.1 静态调度或块调度

当循环的不同迭代执行的工作相同时，将工作均匀地分摊在系统上不同的线程之间很有益。此方法称为静态调度。

示例 3–13 静态调度的良好循环

for (i=1; i < 1000; i++) {
    sum += a[i]*b[i];       /* S1 */
}

在静态调度或块调度中，每个线程将获取相同次数的迭代。如果有 4 个线程，则在以上示例中，每个线程将获取 250 次迭代。假设不存在中断，并且每个线程的进度相同，则所有线程将同时完成。

3.6.2 自我调度

一般说来，当每次迭代执行的工作不同时，静态调度不会达到良好的负载平衡。在静态调度中，每个线程获取同一迭代块。除主线程之外，每个线程在完成自己的块时，将等待参与下一个并行循环的执行。主线程将继续执行程序。在自我调度中，每个线程获取不同的小迭代块，并且在完成为其分配的块之后，尝试从同一循环中获取更多块。

3.6.3 引导自我调度

在引导自我调度 (guided self scheduling, GSS) 中，每个线程获取连续变少的块。如果每次迭代的大小不同，GSS 有助于平衡负载。

3.7 循环变换

编译器执行多个循环重构变换，帮助改进程序中循环的并行化。其中某些变换还可以提高循环的单处理器执行性能。下面描述编译器执行的变换。

3.7.1 循环分布

循环通常包含少量无法并行执行的语句以及许多可以并行执行的语句。循环分布旨在将顺序语句移到单独一个循环中，并将可并行化的语句收集到另一个循环中。这一点在以下示例中描述：

示例 3–14 循环分布举例

for (i=0; i < n; i++) {
    x[i] = y[i] + z[i]*w[i];               /* S1 */
    a[i+1] = (a[i-1] + a[i] + a[i+1]/3.0;  /* S2 */
    y[i] = z[i] - x[i];                    /* S3 */
}

假定数组 x、y、w、a 和 z 不重叠，则语句 S1 和 S3 可以并行化，但语句 S2 不能并行化。以下是循环被分割或分布为两个不同循环后的情形：

示例 3–15 分布式循环

/* L1: parallel loop */
for (i=0; i < n; i++) {
    x[i] = y[i] + z[i]*w[i];              /* S1 */
    y[i] = z[i] - x[i];                   /* S3 */
}
/* L2: sequential loop */
for (i=0; i < n; i++) {
    a[i+1] = (a[i-1] + a[i] + a[i+1]/3.0; /* S2 */
}

在此变换之后，循环 L1 不包含任何阻止循环并行化的语句，因此可并行执行。然而，循环 L2 仍包含来自初始循环的不可并行化的语句。

循环分布并非始终有益或安全。编译器会进行分析，以确定分布的安全性和有益性。

3.7.2 循环合并

如果循环的粒度（或循环执行的工作量）很小，则分布的效果可能并不明显。这是因为与循环工作量相比，并行循环启动的开销太大。在这种情况下，编译器使用循环合并将多个循环合并到单个并行循环中，从而增大循环的粒度。当具有相同行程计数的循环彼此相邻时，循环合并很方便且很安全。请看以下示例：

示例 3–16 工作量小的循环

/* L1: short parallel loop */
for (i=0; i < 100; i++) {
    a[i] = a[i] + b[i];        /* S1 */
}
/* L2: another short parallel loop */
for (i=0; i < 100; i++) {
    b[i] = a[i] * d[i];        /* S2 */
}

这两个短并行循环彼此相邻，可以安全地合并，如下所示：

示例 3–17 合并的两个循环

/* L3: a larger parallel loop */
for (i=0; i < 100; i++) {
    a[i] = a[i] + b[i];       /* S1 */
    b[i] = a[i] * d[i];       /* S2 */
}

新循环产生的开销是并行循环执行产生的开销的一半。循环合并在其他方面也很有帮助。例如，如果在两个循环中引用同一数据，则合并这两个循环可以改善引用环境。

然而，循环合并并非始终安全。如果循环合并创建之前并不存在的数据依赖性，则合并可能会导致错误执行。请看以下示例：

示例 3–18 不安全合并举例

/* L1: short parallel loop */
for (i=0; i < 100; i++) {
    a[i] = a[i] + b[i];      /* S1 */
}
/* L2: a short loop with data dependence */
for (i=0; i < 100; i++) {
    a[i+1] = a[i] * d[i];    /* S2 */
}

如果合并3.7.2 循环合并中的循环，会产生语句 S2 至 S1 的数据依赖性。实际上，语句 S1 右边 a[i] 的值是在语句 S2 中计算的。如果不合并循环，此情况则不会发生。编译器执行安全性和有益性分析，以确定是否应执行循环合并。通常，编译器可以合并任意多个循环。以这种方式增大粒度有时可以大大改善循环，使其足从并行化中获益。

3.7.3 循环交换

并行化循环嵌套的最外层循环通常更有益，因为发生的开销很小。然而，由于此类循环可能携带依赖性，并行化最外层循环并非始终安全。以下对此进行说明：

示例 3–19 不能并行化的嵌套循环

for (i=0; i <n; i++) {
    for (j=0; j <n; j++) {
            a[j][i+1] = 2.0*a[j][i-1];
    }
}

在本例中，具有索引变量 i 的循环不能并行化，原因是循环的两次连续迭代之间存在依赖性。这两个循环可以交换，并行循环（j 循环）变为外部循环：

示例 3–20 交换的循环

for (j=0; j<n; j++) {
    for (i=0; i<n; i++) {
            a[j][i+1] = 2.0*a[j][i-1];
    }
}

交换后的循环只发生一次并行工作分配开销，而先前发生 n 次开销。编译器执行安全性和有益性分析，以确定是否执行循环交换。

3.8 别名和并行化

ISO C 别名通常可防止循环并行化。存在两个对同一存储单元的可能引用时，将产生别名。请看以下示例：

示例 3–21 具有对同一存储单元的两个引用的循环

void copy(float a[], float b[], int n) {
    int i;
    for (i=0; i < n; i++) {
            a[i] = b[i]; /* S1 */
    }
}

由于变量 a 和 b 为参数，因此 a 和 b 可能指向重叠的内存区域；例如，如果 copy 的调用如下：

copy (x[10], x[11], 20);

在调用的例程中，copy 循环的两次连续迭代可能读/写数组 x 的同一元素。然而，如果例程 copy 的调用如下，则循环的 20 次迭代中不可能出现重叠：

copy (x[10], x[40], 20);

通常，在不知道例程如何调用的情况下，编译器不可能正确地分析此情况。编译器提供 ISO C 的关键字扩展，使您可以传达此类别名信息。有关更多信息，请参见3.8.2 限定指针。

3.8.1 数组引用和指针引用

别名问题的部分原因是：C 语言可以通过指针运算来定义数组引用及定义。为使编译器有效地并行化循环（自动或显式使用 pragma），所有采用数组布局的数据均必须使用 C 数组引用语法而不是指针进行引用。如果使用指针语法，编译器将无法确定循环的不同迭代之间的关系。因此，它将保守而不会并行化循环。

3.8.2 限定指针

为使编译器有效地执行循环的并行执行任务，需要确定特定左值是否指定不同的存储区域。别名是其存储区域相同的左值。由于需要分析整个程序，因此确定对象的两个指针是否为别名是一个困难而费时的过程。例如下面的函数 vsq()：

示例 3–22 带两个指针的循环

void vsq(int n, double * a, double * b) {
    int i;
    for (i=0; i<n; i++) {
            b[i] = a[i] * a[i];
    }
}

如果编译器知道指针 a 和 b 访问不同的对象，可以并行化循环的不同迭代的执行。如果通过指针 a 和 b 访问的对象存在重叠，编译器以并行方式执行循环将会不安全。在编译时，编译器并不能通过简单地分析函数 vsq() 来获悉 a 和 b 访问的对象是否重叠；编辑器需要分析整个程序才能获取此信息。

限定指针用来指定哪些指定不同对象的指针，以便编译器可以执行指针别名分析。以下是函数参数声明为限定指针的函数 vsq() 示例：

void vsq(int n, double * restrict a, double * restrict b)

指针 a 和 b 声明为限定指针，因此编译器知道 a 和 b 指向不同的存储区域。有了此别名信息，编译器就能够并行化循环。

关键字 restrict 是一个类型限定符，与 volatile 一样，但它仅限定指针类型。使用 -xc99=all（使用 -Xs 时除外）时，restrict 识别为一个关键字。在某些情况下，您可能不希望更改源代码。可以使用以下命令行选项指定将返回赋值指针函数参数视为限定指针：

-xrestrict=[func1,…,funcn]

如果指定函数列表，则指定的函数中的指针参数将被视为限定的；否则，整个 C 文件中的所有指针参数均被视为限定的。例如，-xrestrict=vsq 限定前一个有关键字 restrict 的函数 vsq() 示例中给定的指针 a 和 b。

正确使用 restrict 至关重要。如果指针被限定为限定指针而指向不同的对象，编译器会错误地并行化循环而导致不确定的行为。例如，假定函数 vsq() 的指针 a 和 b 指向的对象重叠，如 b[i] 和 a[i+1] 是同一对象。如果 a 和 b 未声明为限定指针，循环将以串行方式执行。如果 a 和 b 被错误地限定为限定指针，编译器会并行化循环的执行，但这是不安全的，因为 b[i+1] 应在 b[i] 之后进行计算。

3.8.3 显式并行化和 Pragma

通常，编译器没有足够的信息来判断并行化的合法性或有益性。编译器支持 pragma，使程序员能够有效地并行化循环，否则编译器很难或根本无法处理这些循环。本节中其他地方详细介绍的 Sun 特定的 MP pragma 对 OpenMP 标准的支持已过时。有关该标准的指令的信息，请参见《OpenMP API 用户指南》。

3.8.3.1 串行 Pragma

Sun 特定的 MP pragma 已过时，并且不再受支持。但是，编译器改为支持 OpenMP 2.5 标准指定的 API。有关标准的指令的迁移信息，请参见《OpenMP API 用户指南》。

有两个串行 pragma，均适用于 for 循环：

• #pragma MP serial_loop

• #pragma MP serial_loop_nested

#pragma MP serial_loop pragma 向编译器指示：下一个 for 循环不自动并行化。

#pragma MP serial_loop_nested pragma 向编译器指示：下一个 for 循环以及该 for 循环的作用域内嵌套的任何 for 循环均不自动并行化。

这些 pragma 的作用域以 pragma 开始，并在下列先出现的项结束：下一个块的开头、当前块内的下一个 for 循环或当前块的结尾。

3.8.3.2 并行 Pragma

Sun 特定的 MP pragma 已过时，并且不再受支持。但是，编译器改为支持 OpenMP 2.5 标准指定的 API。有关标准的指令的迁移信息，请参见《OpenMP API 用户指南》。

有一个并行 pragma：#pragma MP taskloop [options]。

MP taskloop pragma 可以根据需要带下列一个或多个参数。

• maxcpus (number_of_processors)

• private (list_of_private_variables)

• shared (list_of_shared_variables)

• readonly (list_of_readonly_variables)

• storeback (list_of_storeback_variables)

• savelast

• reduction (list_of_reduction_variables)

• schedtype (scheduling_type)

这些 pragma 的作用域以 pragma 开始，并在下列先出现的项结束：下一块的开始部分、当前块内部的下一个 for 循环、当前块的结尾。该 pragma 应用于 pragmas 作用域结束前的下一个 for 循环。

每个 MP taskloop pragma 只能指定一个选项；但是，pragmas 是累积的，并应用于 pragmas 作用域中的下一个 for 循环：

#pragma MP taskloop maxcpus(4)
#pragma MP taskloop shared(a,b)
#pragma MP taskloop storeback(x)

这些选项在其所应用的 for 循环之前可能会多次出现。如果存在冲突选项，编译器将发出警告消息。

for 循环的嵌套

MP taskloop pragma 应用于当前块内部的下一个 for 循环。并行化 C 不存在并行化 for 循环的嵌套。

并行化的合格性

除非另有禁止，否则 MP taskloop pragma 建议编译器应并行化指定的 for 循环。

任何具有不规则控制流和未知循环迭代增量的 for 循环均不能进行并行化。例如，包含 setjmp、longjmp、exit、abort、return、goto、labels 和 break 的 for 循环均不能并行化。

特别重要的是，具有迭代间依赖性的 for 循环可以进行显式并行化。这意味着，如果为此类循环指定了一个 MP taskloop pragma，除非 for 循环被取消资格，否则编译器将完全遵循该 pragma。用户有责任确保此类显式并行化不会导致错误结果。

如果为 for 循环指定了 serial_loop（或 serial_loop_nested）pragma 和 taskloop pragma，则将使用最后指定的 pragma。

请看以下示例：

#pragma MP serial_loop_nested
    for (i=0; i<100; i++) {
   # pragma MP taskloop
      for (j=0; j<1000; j++) {
      ...
 }
}

i 循环将不并行化，但是 j 循环可能并行化。

处理器数

#pragma MP taskloop maxcpus (number_of_processors) 指定要用于此循环的处理器数（如果可能）。

maxcpus 的值必须为正整数。如果 maxcpus 等于 1，指定的循环将串行执行。（请注意，将 maxcpus 设置为 1 相当于指定 serial_loop pragma。）将比较 maxcpus 的值与 PARALLEL 环境变量的解释值，使用较小的值。在未指定环境变量 PARALLEL 的情况下，该 pragma 被解释为具有值 1。

如果为一个 for 循环指定了多个 maxcpus pragma，将使用最后指定的 pragma。

变量分类

循环中使用的变量可分类为 private、shared、reduction 或 readonly 变量。变量只能属于其中一种分类。通过显式 pragma 只能将变量分类为 reduction 或 readonly 变量。请参见 #pragma MP taskloop reduction 和 #pragma MP taskloop readonly。通过显式 pragma 或以下缺省作用域规则可将变量分类为 private 或 shared 变量。

private 和 shared 变量的缺省作用域规则

private 变量的值是处理 for 循环的某些迭代的每个处理器的私有值。换句话说，在 for 循环的一次迭代中赋给 private 变量的值不会传送给处理该 for 循环的其他迭代的其他处理器。而 shared 变量的当前值可处理 for 循环的迭代的所有处理器访问。处理循环迭代的一个处理器赋给 shared 变量的值可能会被处理循环的其他迭代的其他处理器识别。通过使用 #pragma MP taskloop 指令显式并行化并包含共享变量引用的循环，必须确保值的共享不会导致正确性问题（如竞争情况）。对显式并行化的循环中的共享变量的更新和访问，编译器不提供同步。

在分析显式并行化的循环时，编译器使用以下“缺省作用域规则”来确定变量是 private 变量还是 shared 变量：

• 如果变量未通过 pragma 显式分类，已声明为指针或数组，并且仅在循环内部使用数组语法进行引用，则该变量缺省分类为 shared 变量。否则，将被分类为 private 变量。

• 循环索引变量始终被视为 private 变量和返回存储变量。

强烈建议将显式并行化的 for 循环中使用的所有变量显式分类为 shared、private、reduction 或 readonly 变量，以避免使用“缺省作用域规则”。

由于编译器对共享变量的访问不执行同步，因此在对包含数组引用等的循环使用 MP taskloop pragma 之前必须格外谨慎。如果此类显式并行化的循环中存在迭代间数据依赖性，则其并行执行会导致错误结果。编译器不一定能够检测到此类潜在问题情况并发出警告消息。无论如何，编译器不会禁止具有潜在共享变量问题的循环的显式并行化。

private 变量

#pragma MP taskloop private (list_of_private_variables)

使用此 pragma 指定所有应视为此循环私有变量的变量。此循环中使用但未显式指定为 shared、readonly 或 reduction 变量的所有其他变量，按缺省作用域规则的定义，为 shared 变量或 private 变量。

private 变量的值是处理循环的某些迭代的每个处理器的私有值。换句话说，处理循环迭代的一个处理器赋给 private 变量的值不会传送给处理该循环的其他迭代的其他处理器。private 变量在循环的每次迭代开始时没有初始值，必须在循环的迭代内部第一次使用它之前，在该迭代内部设置为一个值。如果某个循环包含一个在设置之前使用其值的显式声明 private 变量，则执行包含该循环的程序将导致不确定的行为。

shared 变量

#pragma MP taskloop shared (list_of_shared_variables)

使用此 pragma 指定所有应视为此循环的 shared 变量的变量。循环中使用的但未显式指定为 private、readonly、storeback 或 reduction 变量的所有其他变量，按缺省作用域规则的定义，为 shared 变量或 private 变量。

shared 变量的当前值可被处理 for 循环的迭代的所有处理器访问。处理循环迭代的一个处理器赋给 shared 变量的值可能会被处理循环的其他迭代的其他处理器识别。

readonly 变量

#pragma MP taskloop readonly (list_of_readonly_variables)

readonly 变量是一类特殊的共享变量，不在循环的任何迭代中进行修改。使用此 pragma 向编译器指示，它可以对处理循环迭代的每个处理器使用该变量值的单独副本。

storeback 变量

#pragma MP taskloop storeback (list_of_storeback_variables)

使用此 pragma 指定所有应视为 storeback 变量的变量。

storeback 变量的值在循环中计算，并且计算的值在循环终止后使用。storeback 变量的最后一个循环迭代值在循环终止后使用。当变量为私有变量时，此类变量可以很好地通过此指令显式声明为 storeback 变量，通过将变量显式声明为私有变量或通过使用缺省作用域规则均可。

请注意，storeback 变量的返回存储操作发生在显式并行化循环的最后一次迭代中，而无论该迭代是否更新 storeback 变量的值。换句话说，处理循环最后一次迭代的处理器可能并不是当前包含 storeback 变量的最后更新值的同一处理器。请看以下示例：

#pragma MP taskloop private(x)
#pragma MP taskloop storeback(x)
   for (i=1; i <= n; i++) {
      if (...) {
          x=...
      }
}
   printf (“%d”, x);

在上例中，通过 printf() 调用打印出的 storeback 变量 x 的值可能与通过 i 循环的串行版本打印出的值不同，原因是，在显式并行化情况下，处理循环最后一次迭代（当 i==n 时）的处理器（即执行 x 的返回存储操作的处理器）可能不是当前包含 x 的最后更新值的同一处理器。编译器将尝试发出警告消息，提醒用户注意此类潜在问题。

在显式并行化的循环中，作为数组引用的变量不视为 storeback 变量。因此，如果需要此类返回存储操作（例如，如果作为数组引用的变量已声明为私有变量），则将作为数组引用的变量包括在 list_of_storeback_variables 中很重要。

savelast

#pragma MP taskloop savelast

使用此 pragma 指定要视为返回存储变量的所有私有变量。此 pragma 的语法如下：

#pragma MP taskloop savelast

通常，使用这种形式很方便，无需在将每个变量声明为返回存储变量时列出循环的每个私有变量。

reduction 变量

#pragma MP taskloop reduction (list_of_reduction_variables) 指定出现在 reduction 变量列表中的所有变量均将视为循环的 reduction 变量。reduction 变量的部分值可由处理循环迭代的每个处理器单独计算，其最终值可从其所有部分值中计算。有了 reduction 变量列表，便于编译器识别循环是否为约简循环，从而允许为其生成并行约简代码。请看以下示例：

#pragma MP taskloop reduction(x)
    for (i=0; i<n; i++) {
         x = x + a[i];
}

变量 x 是 (sum) 约简变量，i 循环是 (sum) 约简循环。

调度控制

Sun ISO C 编译器支持多种 pragma，这些 pragma 可与 taskloop pragma 配合使用，以控制给定循环的循环调度策略。此 pragma 的语法是：

#pragma MP taskloop schedtype (scheduling_type)

此 pragma 可用来指定要用来调度并行化循环的特定 scheduling_type。Scheduling_type 可为以下类型之一：

• static

  在 static 调度中，循环的所有迭代均匀地分布在参与处理的所有处理器中。请看以下示例：

#pragma MP taskloop maxcpus(4)
#pragma MP taskloop schedtype(static)
    for (i=0; i<1000; i++) {
...
}

在以上示例中，四个处理器中的每个处理器将处理循环的 250 次迭代。

• self [(chunk_size)]

  在 self 调度中，每个参与处理的处理器处理固定次数的迭代（称为“块大小”），直到循环的所有迭代均已处理完毕为止。可选的 chunk_size 参数指定要使用的“块大小”。Chunk_size 必须为正整数常量或整型变量。如果指定为变量，chunk_size 在循环开始时求出的值必须为正整数值。如果未指定这个可选的参数，或者其值不为正数，编译器将选择要使用的块大小。请看以下示例：

#pragma MP taskloop maxcpus(4)
#pragma MP taskloop schedtype(self(120))
for (i=0; i<1000; i++) {
...
}

在以上示例中，分配给每个参与处理的处理器的迭代次数按工作请求顺序依次为：

120、120、120、120、120、120、120、120、40。

• gss [(min_chunk_size)]

  在 guided self 调度中，每个参与处理的处理器处理可变次数的迭代（称为“最小块大小”），直到循环的所有迭代均已处理完毕为止。可选的 min_chunk_size 参数指定使用的每个可变块大小至少必须为 min_chunk_size。Min_chunk_size 必须为正整数常量或整型变量。如果指定为变量，min_chunk_size 在循环开始时求出的值必须为正整数值。如果未指定这个可选的参数，或者其值不为正数，编译器将选择要使用的块大小。请看以下示例：

#pragma MP taskloop maxcpus(4)
#pragma MP taskloop schedtype(gss(10))
for (i=0; i<1000; i++) {
...
}

在以上示例中，分配给每个参与处理的处理器的迭代次数按工作请求顺序依次为：

250、188、141、106、79、59、45、33、25、19、14、11、10、10、10。

• factoring [(min_chunk_size)]

  在 factoring 调度中，每个参与处理的处理器处理可变次数的迭代（称为“最小块大小”），直到循环的所有迭代均已处理完毕为止。可选的 min_chunk_size 参数指定使用的每个可变块大小至少必须为 min_chunk_size。Min_chunk_size 必须为正整数常量或整型变量。如果指定为变量，min_chunk_size 在循环开始时求出的值必须为正整数值。如果未指定这个可选的参数，或者其值不为正数，编译器将选择要使用的块大小。请看以下示例：

#pragma MP taskloop maxcpus(4)
#pragma MP taskloop schedtype(factoring(10))
for (i=0; i<1000; i++) {
...
}

在以上示例中，分配给每个参与处理的处理器的迭代次数按工作请求顺序依次为：

125、125、125、125、62、62、62、62、32、32、32、32、16、16、16、16、10、10、10、10、10、10。