英特尔® 多线程应用开发指南

《英特尔® 多线程应用开发指南》的目标是为开发人员在基于英特尔® 架构的对称多处理器（SMP）和/或支持英特尔® 超线程（HT）技术的系统上，开发高效多线程应用提供一些有用的指导。应用开发人员可以在本文建议下提高当前及未来支持英特尔® 处理器的 SMP 架构上的多线程处理性能，最大限度减少意外出现的性能故障。

本指南针对如何改进多线程性能提供了各种建议。文中有意保留了通过优化硬件提高线程性能的方法。但在本指南的更新版中将涵盖此硬件优化法，为那些愿意牺牲可移植性换取更高性能的开发人员提供一个参考。

1.2 前提条件

读者应具备使用高级编程语言（最好是 C、C++ 和/或 Fortran）编程的经验，尽管本文所提供的许多建议同样适用于 Java、C# 和 Perl 等编程语言。同时，读者还必须了解基本并行编程知识，熟悉一种以上线程化方法，最好是 OpenMP*、POSIX 线程（又名 Pthreads）或 Win32* 线程化 API。

1.3 适用范围

本指南的主要目的是为开发人员在英特尔® 平台上开发多线程应用提供快速设计和优化参考指导。本文不应用作多线程教材，也不是向英特尔平台实施迁移的指南。

1.4 结构

《英特尔® 多线程应用开发指南》涵盖从适用于所有多线程方法的一般性建议到英特尔® 软件产品在应对 API 有关问题时的使用指南在内的各类主题。涉及每个主题的文章之间互相独立，可用作单独的参考文章。所有主题可分为四类：应用线程化、同步处理、内存管理与编程工具。尽管每个主题是对各个关键线程问题的独立探讨，这些主题之间却会形成内容互补。读者可以在阅读这一系列文章时交叉参考相关主题。

1.5 作者与编者

参与《英特尔® 多线程应用开发指南》的撰稿、审核以及编辑工作的英特尔工程师和技术专家如下：Henry Gabb、Martyn Corden、Todd Rosenquist、Paul Fischer、Julia Fedorova、Clay Breshears、Thomas Zipplies、Vladimir Tsymbal、Levent Akyil、Anton Pegushin、Alexey Kukanov、Paul Petersen、Mike Voss、Aaron Tersteeg 和 Jay Hoeflinger。

1.6 并行编程人员有关本指南的意见

Tom Spyrou's在以编程工具为主题的文章《采用英特尔® Parallel Amplifier 解决线程不平衡问题》中提出了有关如何优化线程间工作任务分配的建议，并在《检测线程化应用的内存带宽饱和度》中分享了他在发现主内存带宽导致程序瓶颈时的检测经历。

Dmitriy Vyukov 在《避免并识别线程间伪共享》中提出了有关伪共享的想法。

Asaf Shelly 在《避免线程间出现堆争用情况》中探讨了如何通过为每条线程分配属于自己的堆来正确实施内存分配。

Clay Breshears 撰写了一篇与《粒度与并行性能》有关的文章《吹雪的艺术》。

-----------------------------华丽分割线-----------------------------

第一章、应用线程化

本章节将涵盖并行性能领域的常见主题，同时也会偶尔涉及针对 API 的问题。

-----------------------------华丽分割线-----------------------------

预测和测量并行性能

提交新文章

Published On :
2010年02月27日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

构建软件的并行版本可使应用在更短的时间内运行给定数据集，在固定时间内运行多个数据集，或运行非线程软件无法运行的大型数据集。并行化的成功通常通过并行版本相对于串行版本的加速比来量化表示。除了这种比较之外，将该加速比与可能的加速比上限进行比较也十分有用。这一点可使用阿姆达尔定律和古斯塔夫森定律做到。
本文是《英特尔® 多线程应用开发指南》系列的一部分，后者用于指导开发人员针对英特尔® 平台开发高效的多线程应用。

背景

应用运行的速度越快，用户等待结果所需的时间越短。此外，执行时间的缩短使用户在可接受的时间内能够运行更大规模的数据集（例如，更多的数据记录，更多的像素，或更大的物理模型）。串行与并行执行时间之间一个具体的比较指标便是加速比（speedup）。
简单来说，加速比是串行执行时间与并行执行时间的比率。例如，如果串行应用运行需 6720 秒，对应的并行应用运行需 126.7 秒（使用 64 个线程和核心），则并行应用的加速比是53X (6720/126.7 = 53.038)。
对于扩展良好的应用，加速比增加的速度应与核心（线程）数量增加的速度相同或接近。当增加使用的线程数时，如果测量的加速比不能维持不变或开始下降，那么就测量的数据集，该应用的扩展性不够理想。如果该数据集是典型的实际数据集，而应用将在此之上执行，那么该应用的扩展性能则不理想。
与加速比相关的另一个指标是效率（efficiency）。正如加速比是衡量并行执行比串行执行快多少的指标，效率表示的是软件对系统计算资源的利用程度。要计算并行执行的效率，只需将观察到的加速比除以使用的核心数，然后将得到的数值以百分数表示即可。例如，加速比为53X，使用 64个核心，那么效率就等于82% (53/64 = 0.828)。这意味着，在应用执行过程中，平均每个核心大约有17% 的时间处于闲置状态。
阿姆达尔定律
在启动一个并行化项目前，开发人员会希望预估他们能够实现的性能提升量（加速比）。如果知道（或预估出)能够以并行方式执行的串行代码的百分数，那么开发人员可使用阿姆达尔定律计算应用的加速比上限，无需实际编写任何并发代码。本系列介绍了阿姆达尔定律公式的几种变形。每种变形均使用并行执行时间 (pctPar) 、串行执行时间 (1 - pctPar) 和线程/核心 (p) 的百分数（建议）。下面是一个简单的阿姆达尔定律公式，用于评估基于 p 个核心的并行应用的加速比。

该公式只是串行时间（标准化为 1）与预估的并行执行时间的简单相除，使用标准化的串行时间的百分数。并行执行时间表示为串行执行的百分数 (1 - pctPar)加上能够以并行方式执行的百分数与所用核心数 (pctPar/p)的除数。例如，如果 95% 的串行应用运行时间可以在 8 个核心上以并行方式执行，根据阿姆达尔定律，预估的加速比等于6X (1 / (0.05 + 0.95/8)= 5.925)。
除了在公式中的小于或等于关系 (≥)，阿姆达尔定律公式假设这些能够以并行方式执行的计算可被无限核心数整除。这一假设实际消除了分母中的第二项，意味着最大的加速比即是剩余串行执行百分数的倒数。
因为忽略了实际开销，例如通信、同步和其它线程管理，以及无限核心处理器的假设，阿姆达尔定律一直饱受批评。除了没有考虑并发算法固有的开销，对阿姆达尔定律最强烈的批评之一是，随着核心数量的增加，处理的数据量也可能会增加。阿姆达尔定律假设不论核心数量如何，数据集大小均为固定，并且整体串行执行时间保持不变。
斯塔夫森定律
如果使用 8 核的并行应用能够计算的数据集是原始大小的 8 倍，串行部分的执行时间会增加吗？即使有增加，它也并非与数据集的增加同比例增长。实际数据显示串行执行时间几乎保持不变。
斯塔夫森定律又被称为扩展的加速比（scaled speedup），它考虑了数据大小与核心数量成比例的增加并计算应用的加速比（上限），假设大数据集能够以并行方式执行。扩展的加速比公式如下：

与阿姆达尔定律公式相同，p 代表核心数量。为简化表述，对于指定的数据集大小，s 代表并行应用中的串行执行时间的百分数。例如，如果在 32 个核心上 1% 的执行时间用于串行执行，对于同一数据集，基于单个核心和单个线程运行的应用的加速比是：

现在来考虑阿姆达尔定律基于这些假设估计的加速比。假设串行执行的百分比是 1%，阿姆达尔定律等式得出 1/(0.01 + (0.99/32)) = 24.43X。这是个错误计算，因为给定的串行时间百分数与 32 核心执行有关。该示例没有指出对于更多或更少的核心（甚至只有一个核心），对应的串行执行百分数将是多少。如果代码扩展完美，并且数据大小与核心数同时扩展，那么该百分数能够保持不变，阿姆达尔定律计算的结果将是 32 核心上（固定大小）单核问题的预测加速比。
另一方面，如果在 32 核心的案例中知道总的并行应用执行时间，则可以计算全部串行执行时间，并且针对固定大小问题的加速比（进一步假设该值可以使用单核计算）可以通过阿姆达尔定律基于 32 核心进行预测。假设在 32 核心上并行应用的总执行时间是 1040 秒，则该时间的 1% 是串行执行时间，或 10.4 秒。乘以 32 核心上并行执行的秒数 (1029.6)，该应用完成总工作量所花时间为 1029.6*32+10.4 = 32957.6 秒。非并行时间（10.4 秒）是总工作时间的 0.032%。使用该数字，阿姆达尔定律计算出的加速比为1/(0.00032 + (0.99968/32)) = 31.686X。
要使用斯塔夫森定律，必须知道并行执行期间串行时间的百分数，因此该公式的一个典型用例是计算扩展的并行执行（数据集大小随着核心数量的增加而增加）与相同大小问题串行执行的加速比。从上面的示例可以看出，由于在阿姆达尔定律的公式中有关应用执行数据的严格使用，得出的估值比扩展的加速比公式得出的值悲观得多。

建议

在计算加速比时，必须对最佳的串行算法和最快的串行代码进行比较。通常，非最佳串行算法将更容易并行化。即便如此，虽然有更快的串行版本，但也不是所有人都会使用串行代码。因此，即使底层算法不同，必须使用最快串行代码中的最佳串行运行时间来计算可比较并行应用的加速比。
在说明加速比时，应使用乘数值。过去，加速比一直以百分数表示。在本文中，使用百分数会引起困惑。例如，如果说并行代码比串行代码快 200%，那么它的运行时间是串行版本时间的一半，还是该时间的三分之一？105%的加速比是几乎与串行执行时间相同还是比串行执行时间快两倍？基准串行时间是 0% 加速比还是 100% 加速比？另一方面，如果并行应用的加速比是 2X，很显然它使用一半的时间（即，并行版本在相同的时间内能够执行两次，而串行代码执行一次）
在极少数情况下，应用的加速比大于核心数。这种现象被称为超级线性加速。发生超级线性加速的典型原因是固定大小数据集被分解得足够小（对内核而言），可以放入本地高速缓存。当以串行方式运行时，数据必须通过高速缓存获取，在获取期间处理器只能等待。如果数据足够大，需占用清空之前使用的某些高速缓存行，那么后续对这些高速缓存行的任何复用都会导致处理器再次等待。当数据被分解成可放入核心上高速缓存的数据块时，一旦这些数据被全部存入高速缓存，则无需经历复用高速缓存行所带来的等待复用。因此，使用多个核心可以消除在单个核心上与串行代码执行相关的一些系统开销。这样，过小的数据集（小于一般的数据大小）便会产生性能提升的错觉。

使用准则

此外还有其它并行执行模型尝试对阿姆达尔定律简单模型中的缺陷给出合理假设。
然而，因为其简单性和用户理解这只是理论上限（几乎不可能达到或超越），所以阿姆达尔定律仍是表示串行应用加速比潜力的一项简单、有用的指标。

其它资源

英特尔® 软件网络并行编程社区
John L. Gustafson，“重新评估阿姆达尔定律” 《美国计算机协会通讯》，第31卷，第532-533页，1988年。
Michael J. Quinn，“在C语言中使用MPI 和 OpenMP并行编程 ”，McGraw-Hill出版社，2004 年

-----------------------------华丽分割线-----------------------------

循环修改增强数据并行性能

提交新文章

Published On :
2010年01月14日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

在数据并行应用中，相同的独立操作针对不同数据重复执行。循环通常是数据并行应用的最密集计算段，因此循环优化直接影响性能。当面对嵌套循环时，分配给线程的计算粒度将直接影响性能。循环转换如分裂（循环裂变）与合并（循环融合）嵌套式循环可使并行化更加高效。
本文是《英特尔® 多线程应用开发指南》系列的一部分，该系列介绍了针对英特尔® 平台开发高效多线程应用的指导原则。

背景

循环优化为提高数据并行应用性能提供了一个很好的机会。这些优化，例如循环融合、循环交换和循环展开等可帮助改善粒度、负载平衡和数据本地化，同时最大限度地减少同步化和其他并行费用。一般来说，迭代次数多的循环最适合并行化，尤其是当运行线程数量较少时。高迭代率能够实现更好的负载平衡，因为有大量的任务可以分配给线程。但仍需考虑每次迭代需要完成的工作量。除非另有说明，否则本章节所讨论的内容均假设一个循环内每个迭代的计算量与该循环内其他迭代的计算量（大致）相同。
考虑将 OpenMP* 用于如下示例代码的工作分享结构时的循环场景。当循环迭代分布多于四个线程时，低迭代次数将会导致负载不平衡。如果一个迭代运行仅需几微妙，那么这种不平衡可能不会造成严重影响。然而，如果每个迭代运行均需一个小时，那么在第四个迭代运行完成时，将会有三个线程处于 60 分钟的闲置状态。将这一结果与 1003 一小时迭代和四线程的相同循环进行对比。在这种情况下，任务执行十天后，一小时的闲置时间就显得微不足道了。

- collapse source view plain copy to clipboard print ?

#pragma omp for
for (i = 0; i < 13; i++)
{...}

#pragma omp for
for (i = 0; i < 13; i++)
{...}

建议

对于多个嵌套式循环，选择最外层循环进行并行化最为安全。这种方法通常会生成最为粗糙的粒度。确保工作能够平均分配给每个线程。如果因最外层循环的迭代次数较低而无法实施平均分配，则最好选择具有较大迭代次数的内层循环进行线程分配。例如，考虑下面包含四个嵌套循环的代码：

- collapse source view plain copy to clipboard print ?

void processQuadArray (int imx, int jmx, int kmx,
double**** w, double**** ws)
{
for (int nv = 0; nv < 5; nv++)
for (int k = 0; k < kmx; k++)
for (int j = 0; j < jmx; j++)
for (int i = 0; i < imx; i++)
ws[nv][k][j][i] = Process(w[nv][k][j][i]);
}

void processQuadArray (int imx, int jmx, int kmx,
  double**** w, double**** ws)
{
  for (int nv = 0; nv < 5; nv++)
    for (int k = 0; k < kmx; k++)
      for (int j = 0; j < jmx; j++)
        for (int i = 0; i < imx; i++)
          ws[nv][k][j][i] = Process(w[nv][k][j][i]);
}

如果线程数量多余或少于五个，并行外部循环将会导致负载不平衡和闲置线程。如果阵列维数imx、jmx和kmx非常大的话，并行效率将会很低。这种情况下最好选择并行其中一个内部循环。
如果能确保安全性，应尽可能排除工作分享结构底端的隐性障碍。所有 OpenMP 工作分享结构（不论整段还是单个）均在结构块底端含有一个隐性障碍。只有所有线程都在此障碍处集合后，并行才能执行。有时，这些障碍很不必要，并且会影响性能。应使用 OpenMP nowait 子句来消除这些障碍，如下面这个示例：

- collapse source view plain copy to clipboard print ?

void processQuadArray (int imx, int jmx, int kmx,
double**** w, double**** ws)
{
#pragma omp parallel shared(w, ws)
{
int nv, k, j, i;
for (nv = 0; nv < 5; nv++)
for (k = 0; k < kmx; k++) // kmx is usually small
#pragma omp for shared(nv, k) nowait
for (j = 0; j < jmx; j++)
for (i = 0; i < imx; i++)
ws[nv][k][j][i] = Process(w[nv][k][j][i]);
}
}

void processQuadArray (int imx, int jmx, int kmx,
  double**** w, double**** ws)
{
  #pragma omp parallel shared(w, ws)
  {
    int nv, k, j, i;
    for (nv = 0; nv < 5; nv++)
      for (k = 0; k < kmx; k++) // kmx is usually small
        #pragma omp for shared(nv, k) nowait
          for (j = 0; j < jmx; j++)
            for (i = 0; i < imx; i++)
              ws[nv][k][j][i] = Process(w[nv][k][j][i]);
  }
}

由于最内层循环的计算都是独立的，因此在进行下一次迭代之前，线程没有必要在隐性障碍处等待。如果每次迭代的工作量各不相同，nowaitnowait 子句可使线程继续处理有用工作，而非闲置在隐性障碍处。
如果一个循环带有一种可防止循环被并行执行的循环传递相关性，可以将循环体分裂成单独的循环，进而实现并行执行。一个循环体被划分为两个或两个以上的循环被称为“循环分裂”。下面的示例演示了循环分裂过程，一个具有循环传递相关性的循环体创建出新的循环，进而完成并行执行。

- collapse source view plain copy to clipboard print ?

float *a, *b;
int i;
for (i = 1; i < N; i++) {
if (b[i] > 0.0)
a[i] = 2.0 * b[i];
else
a[i] = 2.0 * fabs(b[i]);
b[i] = a[i-1];
}

float *a, *b;
int i;
for (i = 1; i < N; i++) {
  if (b[i] > 0.0) 
    a[i] = 2.0 * b[i];
  else 
    a[i] = 2.0 * fabs(b[i]);
  b[i] = a[i-1];
}

一个阵列内的元素分配均是独立的，无需考虑相应 b 元素的符号。在 b 中的一个元素的每个任务均独立于其他任务，但却依赖于所需 a 元素的任务完成情况。因此，正如所写的一样，上述循环不能并行处理。
但是，若将一个循环体分裂成两个独立的操作，这两个操作均可并行执行。例如，英特尔® 线程构建模块（Intel® TBB）parallel_for 算法可应用于每一个生成的循环：

- collapse source view plain copy to clipboard print ?

float *a, *b;
parallel_for (1, N, 1,
[&](int i) {
if (b[i] > 0.0)
a[i] = 2.0 * b[i];
else
a[i] = 2.0 * fabs(b[i]);
});
parallel_for (1, N, 1,
[&](int i) {
b[i] = a[i-1];
});

float *a, *b;

parallel_for (1, N, 1, 
  [&](int i) {
    if (b[i] > 0.0) 
      a[i] = 2.0 * b[i];
    else 
      a[i] = 2.0 * fabs(b[i]);
    });
parallel_for (1, N, 1, 
  [&](int i) {
    b[i] = a[i-1];
  });

在第二次 parallel_for 调用执行之前，第一次 parallel_for 调用的返回可以确保了 a 阵列内所有更新均已在 b 阵列更新开始之前完成。
再次使用循环分裂可增加数据局部性。考虑一下下面的筛形代码：

- collapse source view plain copy to clipboard print ?

for (i = 0; i < list_len; i++)
for (j = prime[i]; j < N; j += prime[i])
marked[j] = 1;

for (i = 0; i < list_len; i++)
  for (j = prime[i]; j < N; j += prime[i])
    marked[j] = 1;

外层循环选择主阵列内层循环的起始索引和步长。内层循环通过已标记阵列的长度运行，将 ‘1’ 值存入所选择的元素中。如果标记的阵列足够大，内层循环的执行可将缓存行从早期的标记阵列元素中提取出来，进而满足随后的外层循环迭代需求。此行为将会导致串行和并行循环缓存命中率降低。
通过循环裂变，内部循环迭代可以分裂成块，从而更适应缓存，并可随时重新使用缓存行。若要在这种情况下完成分裂，则需要加入另一个循环来控制内部循环执行范围。

- collapse source view plain copy to clipboard print ?

for (k = 0; k < N; k += CHUNK_SIZE)
for (i = 0; i < list_len; i++) {
start = f(prime[i], k);
end = g(prime[i], k);
for (j = start; j < end; j += prime[i])
marked[j] = 1;
}

for (k = 0; k < N; k += CHUNK_SIZE)
  for (i = 0; i < list_len; i++) {
    start = f(prime[i], k);
    end = g(prime[i], k);
    for (j = start; j < end; j += prime[i])
      marked[j] = 1;
  }

对于上述代码中最外层循环的每个迭代，i-循环中的全套迭代都将执行。必须从主阵列中所选择的元素中发现标记阵列块内的起始和结束指数（受外层循环控制）。这些计算已被封装在 f() 和 g() 例程之内。因此，同一标志块将会依次进行处理。并且，鉴于每个块的处理过程完全独立于其他块，因而外层迭代也可并行运行。
合并嵌入式循环增加迭代次数为另一种优化，有助于循环迭代的高效并行化。例如，考虑一下左边带有两个嵌入式循环的代码，其迭代次数分布为 23 和 1000。鉴于 23 为质数，因而无法平均划分外层迭代；同样，1000 迭代可能无法充分削减仅处理内层循环的线程费用。另一方面，借助20 23,000 迭代（见右侧），循环可能被融合成一个单一循环，并通过并行原始代码，缓解上述问题。

- collapse source view plain copy to clipboard print ?

#define N 23
#define M 1000
. . .
for (k = 0; k < N; k++)
for (j = 0; j < M; j++)
wn[k][j] = Work(w[k][j], k, j);

#define N 23
#define M 1000
. . .
for (k = 0; k < N; k++)
  for (j = 0; j < M; j++)
    wn[k][j] = Work(w[k][j], k, j);

- collapse source view plain copy to clipboard print ?

#define N 23
#define M 1000
. . .
for (kj = 0; kj < N*M; kj++) {
k = kj / M;
j = kj % M;
wn [k][j] = Work(w[k][j], k, j);
}

#define N 23
#define M 1000
. . .
for (kj = 0; kj < N*M; kj++) {
  k = kj / M;
  j = kj % M;
  wn [k][j] = Work(w[k][j], k, j);
}

然而，如果迭代变量在循环体中均被使用，新的循环计数必须转换成相应的组件值，这就造成了原始算法所没有的额外开销。
具有相似指数的融合（或合并）循环将改善粒度和数据本地化，而且在并行化时最大限度地减少费用支出。左边示例代码中的前两个循环可以很容易地合并：

- collapse source view plain copy to clipboard print ?

for (j = 0; j < N; j++)
a[j] = b[j] + c[j];
for (j = 0; j < N; j++)
d[j] = e[j] + f[j];
for (j = 5; j < N - 5; j++)
g[j] = d[j+1] + a[j+1];

  for (j = 0; j < N; j++)
    a[j] = b[j] + c[j];

  for (j = 0; j < N; j++)
    d[j] = e[j] + f[j];

  for (j = 5; j < N - 5; j++)
    g[j] = d[j+1] + a[j+1];

- collapse source view plain copy to clipboard print ?

for (j = 0; j < N; j++)
{
a[j] = b[j] + c[j];
d[j] = e[j] + f[j];
}
for (j = 5; j < N - 5; j++)
g[j] = d[j+1] + a[j+1];

  for (j = 0; j < N; j++)
  {
    a[j] = b[j] + c[j];
    d[j] = e[j] + f[j];
  }

  for (j = 5; j < N - 5; j++)
    g[j] = d[j+1] + a[j+1];

合并这些循环增加了每次迭代的工作量（即粒度），并减少了循环开销。因为第三个循环的迭代次数不同，因而其不易被合并。然而，更重要的是，第三个循环和前两个循环之间存在数据相关性。
如果子句选择基于运行时间信息的串行和并行执行，这时可使用 OpenMP。有时一个循环内的迭代数量在运行前无法确定。如果执行一个采用多线程（例如，迭代数量较少）的OpenMP 并行区域会带来消极性能，那么指定一个最低临界值将有助于保持性能，如下面的例子所示：

- collapse source view plain copy to clipboard print ?

#pragma omp parallel for if(N >= threshold)
for (i = 0; i < N; i++) { ... }

#pragma omp parallel for if(N >= threshold)
  for (i = 0; i < N; i++) { ... }

对于本示例代码，如果迭代次数超过了程序规定的临界值，那么循环只能并行执行。
鉴于 Intel® TBB 中没有相同项，需要进行明确条件测试以确定是否需要并行和串行执行代码。或者调度一个并行算法，并由 Intel® TBB 任务调度程序自由确定单一线程应用于足够低的 N 值。这种做法可能需要一些开销。

其它资源

英特尔® 软件网络并行编程社区
OpenMP* 规范
英特尔® 线程构建模块
英特尔® 开放源线程构建模块
James Reinders，《英特尔线程构建模块：打造 C++ 编程以实现多核处理器并行》（Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism.）O'Reilly Media, Inc.，Sebastopol, CA，2007 年

-----------------------------华丽分割线-----------------------------

粒度与并行性能

提交新文章

Published On :
2010年02月13日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

实现出色并行性能的关键是选择适合应用的粒度。粒度是指并行任务的实际工作量。如果粒度太细，则并行性能会因通信开销增加而受到影响。如果粒度太粗，则并行性能会因负载不均衡而受到影响。为确保实现最佳并行性能，开发人员应确定适合并行任务的粒度（通常粒度越大越好），同时还应避免负载不均衡和通信开销增加的情况发生。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

多线程应用的并行任务工作量大小（粒度）会对其并行性能产生很大影响。在分解一项应用使之适用于多线程处理时，开发人员通常采用的方法是从逻辑上将问题分割成尽量多的并行任务，或者在并行任务内根据共享数据与执行顺序决定进行哪些必要的通信。由于分割任务、将任务分配给线程以及在任务之间进行数据通信（共享）涉及到一定的成本，开发人员通常需要聚合或整合分割的任务，用于避免随之产生的开销，尽量实现应用高效运行。通过聚合分割的任务可确定并行任务的最佳粒度。
粒度通常与工作负载在线程之间的均衡程度有关。尽管平衡大量小型任务的工作负载更容易，但这样做却可能导致通信和同步等方面的并行开销过高。此时，开发人员可以通过将小型任务整合成一项任务，增加每项任务的粒度（工作量）来减少并行开销。您可以借助英特尔® Parallel Amplifier 等工具确定一项应用的适宜粒度。
本文将列举下列代码示例向您展示如何通过减少通信开销和确定线程的适宜粒度来提高并行程序的性能。本文所列出的所有代码示例均为质数计数算法，该算法采用一套简单的强力测试方法来执行，让每个潜在质数除以所有可能存在的因数直到除数被找到或该数字经证实为质数为止。由于正奇数可以被（4k+1）或（4k+3）（其中 k ≥ 0）整除，因此使用下列代码还可以计算各种形式的质数数量。所列举的代码示例将计算从 3 到 1 百万的所有质数数量。
下列为采用 OpenMP* 的并行版代码：

- collapse source view plain copy to clipboard print ?

#pragma omp parallel
{ int j, limit, prime;
#pragma for schedule(dynamic, 1)
for(i = 3; i <= 1000000; i += 2) {
limit = (int) sqrt((float)i) + 1;
prime = 1; // assume number is prime
j = 3;
while (prime && (j <= limit)) {
if (i%j == 0) prime = 0;
j += 2;
}
if (prime) {
#pragma omp critical
{
numPrimes++;
if (i%4 == 1) numP41++; // 4k+1 primes
if (i%4 == 3) numP43++; // 4k-1 primes
}
}
}
}

#pragma omp parallel 
{ int j, limit, prime;
#pragma for schedule(dynamic, 1) 
  for(i = 3; i <= 1000000; i += 2) {
    limit = (int) sqrt((float)i) + 1;
    prime = 1; // assume number is prime
    j = 3;
    while (prime && (j <= limit)) {
      if (i%j == 0) prime = 0;
      j += 2;
    }
  
    if (prime) {
      #pragma omp critical
      {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
      }
    }
  }
}

运行该代码的通信开销（表现为同步开销）较高，且个别任务的规模太小，不足以分配给多条线程。在循环内部存在一个可用于为增加计数变量提供安全机制的关键区域。这一关键区域可将同步与锁定开销添加至并行循环（如图 1 中英特尔® Parallel Amplifier 视图所示）。

图 1： 锁定与等待分析结果显示，OpenMP* 关键区域是同步开销产生的原因。
在一个大型数据集内根据数值增加计数变量是削减开销的常用方法。通过清除关键区域和添加 OpenMP reduction 子句可避免生成锁定与同步开销：

- collapse source view plain copy to clipboard print ?

#pragma omp parallel
{
int j, limit, prime;
#pragma for schedule(dynamic, 1) \
reduction(+:numPrimes,numP41,numP43)
for(i = 3; i &;lt;= 1000000; i += 2) {
limit = (int) sqrt((float)i) + 1;
prime = 1; // assume number is prime
j = 3;
while (prime && (j &;lt;= limit))
{
if (i%j == 0) prime = 0;
j += 2;
}
if (prime)
{
numPrimes++;
if (i%4 == 1) numP41++; // 4k+1 primes
if (i%4 == 3) numP43++; // 4k-1 primes
}
}
}

#pragma omp parallel 
{
  int j, limit, prime;

  #pragma for schedule(dynamic, 1) \
    reduction(+:numPrimes,numP41,numP43) 
  for(i = 3; i &;lt;= 1000000; i += 2) {
    limit = (int) sqrt((float)i) + 1;
    prime = 1;  // assume number is prime
    j = 3;
    while (prime && (j &;lt;= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }

    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}

根据循环所执行的迭代次数在循环体内清除关键区域可以使迭代执行速度提升几个数量级。然而，运行上述代码可能仍然会产生一些并行开销。这些开销主要由工作量过小的任务导致。Schedule（dynamic，1）子句规定调度程序一次可向每条线程动态分配一次迭代（数据块）。每条辅助线程会处理一次迭代，接着返回调度程序，并同步获取另外一次迭代。通过增加数据块大小，我们可以增加分配给线程的每项任务的工作量，进而缩减每条线程与调度程序实现同步所需的时间。
尽管采用上述方法可以提高并行性能，但请务必记住：过度增加粒度会导致负载不均衡（上文已提及）。例如，在下列代码中将数据块大小增加到 10000：

- collapse source view plain copy to clipboard print ?

#pragma omp parallel
{
int j, limit, prime;
#pragma for schedule(dynamic, 100000) \
reduction(+:numPrimes, numP41, numP43)
for(i = 3; i <= 1000000; i += 2)
{
limit = (int) sqrt((float)i) + 1;
prime = 1; // assume number is prime
j = 3;
while (prime && (j <= limit))
{
if (i%j == 0) prime = 0;
j += 2;
}
if (prime)
{
numPrimes++;
if (i%4 == 1) numP41++; // 4k+1 primes
if (i%4 == 3) numP43++; // 4k-1 primes
}
}
}

#pragma omp parallel
{
  int j, limit, prime;
  #pragma for schedule(dynamic, 100000) \
    reduction(+:numPrimes, numP41, numP43)
  for(i = 3; i <= 1000000; i += 2)
  {
    limit = (int) sqrt((float)i) + 1;
    prime = 1; // assume number is prime
    j = 3;
    while (prime && (j <= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }

    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}

通过 Parallel Amplifier 对上述代码的执行情况进行的分析显示，使用四条线程完成的计算量分布不均衡（如图 2 所示）。在这个计算示例中，每个数据块的工作量各不相同，可用于指派任务的数据块太少（四条线程瓜分十个数据块），因而才会导致负载不均衡的情况发生。随着潜在质数的值不断增加（从 for 循环开始），需要运行更多迭代来让质数除以尽可能多的因数（在 while 循环中）。这样一来，每个数据块完成全部工作量所需的 while 循环迭代比旧数据块要多。

图 2：并发性分析结果显示，每条线程所使用的执行时间存在不均衡性。
在为程序选择合适的粒度时应采用更适宜的工作量大小（100）。此外，连续任务之间存在的工作量差异在旧数据块上表现得不太显著，通过采用静态调度程序替代动态调度程序可以进一步消除并行开销。下列代码显示改写 schedule 子句将最终削减该代码片断的开销，最大限度提高整体并行速度。

- collapse source view plain copy to clipboard print ?

#pragma omp parallel
{
int j, limit, prime;
#pragma for schedule(static, 100) \
reduction(+:numPrimes, numP41, numP43)
for(i = 3; i <= 1000000; i += 2)
{
limit = (int) sqrt((float)i) + 1;
prime = 1; // assume number is prime
j = 3;
while (prime && (j <= limit))
{
if (i%j == 0) prime = 0;
j += 2;
}
if (prime)
{
numPrimes++;
if (i%4 == 1) numP41++; // 4k+1 primes
if (i%4 == 3) numP43++; // 4k-1 primes
}
}
}

#pragma omp parallel
{
  int j, limit, prime;
  #pragma for schedule(static, 100) \
    reduction(+:numPrimes, numP41, numP43)
  for(i = 3; i <= 1000000; i += 2)
  {
    limit = (int) sqrt((float)i) + 1;
    prime = 1;  // assume number is prime
    j = 3;
    while (prime && (j <= limit))
    {
      if (i%j == 0) prime = 0;
      j += 2;
    }
  
    if (prime)
    {
      numPrimes++;
      if (i%4 == 1) numP41++;  // 4k+1 primes
      if (i%4 == 3) numP43++;  // 4k-1 primes
    }
  }
}

建议

多线程代码的并行性能取决于其粒度：如何在线程之间分配工作任务以及如何在这些线程之间展开通信。下面就通过调整粒度提高并行性能提供一些指导：

了解您的应用
- 了解需要并行处理的应用的各个部分正在执行的工作任务数量。
- 了解应用的通信要求。同步化是一种常见的通信形式，但实施同步化需要考虑在各个内存层面（高速缓存、主内存等）上进行讯息传递和数据共享的开销。
了解您的平台和线程模式
- 了解采用线程模式在目标平台上实施并行和同步化的成本。
- 确保应用的每项并行任务工作量比线程负担大。
- 最大限度减少同步操作和同步化成本。
- 使用英特尔® 线程构建模块并行算法中的分区对象（partitioner object），支持任务调度程序为每项工作任务选择合适的粒度以及实现执行线程上的负载平衡。
了解您的工具
- 在英特尔® Parallel Amplifier“锁定与等待”分析中，锁定、同步和并行开销高是通信开销过高的标志。
- 在英特尔® Parallel Amplifier“并发性”分析中，负载不均衡是粒度过大或线程间任务分配需要优化的标志。

使用指南

尽管上述代码示例多次提及 OpenMP，但本文所提供的所有建议和指导均适用于 Windows 线程和 POSIX* 线程等其它线程模式。所有线程模式都会生成与其各类函数（如实施并行化、锁定、关键区域、讯息传递等）相关的开销。本文在此建议在保持负载平衡的情况下减少通信开销和增加每条线程的工作量，且这一建议适用于所有线程模式。但因不同线程模式所产生的不同成本可能导致开发人员选择不同的粒度。

负载平衡与并行性能

提交新文章

Published On :
2010年01月15日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

实现线程之间应用工作负载平衡是确保出色并行性能的关键。实现负载平衡主要是为了最大限度缩短线程的闲置时间。在尽量减少工作任务分配开销的情况下，在所有线程之间平均分配工作负载可以减少浪费在不能加快计算速度的闲置线程上的时间，进而可显著提高性能。然而，实现完美的负载平衡绝非易事，这主要取决于应用并行性、工作负载、线程数量、负载平衡策略和线程实施情况。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

在执行计算任务时拥有一枚闲置内核无异于拥有一项废弃资源，在该内核上实施有效并行操作会延长线程化应用的整体运行时间。这枚内核处于闲置状态的原因有很多种，需要从内存或 I/O 中取出便是其中一个原因。尽管完全避免内核进入闲置状态不太可能，但编程人员仍然可以采取一些措施来缩短闲置时间，如采用重叠 I/O、内存预取的方式或重新排列数据访问模式的顺序，提高高速缓存利用率。
同样，闲置线程在执行多线程任务时也相当于废弃资源。分配给各线程的工作量不一样会导致名为“负载不均衡”的状况发生。这种不均衡程度越大，保持闲置状态的线程就会越多，完成计算任务所需的时间便会越长。分配给可用线程的各部分计算任务越均衡，完成整个计算任务的时间将会越短。
例如，一项任务由十二项独立任务组成，完成这些独立任务所需要的时间分别是：{10, 6, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1}。假设现有四条线程共同承担这项计算任务，最简单的任务分配法是按照上述时间排列顺序为每条线程分配三项任务，即线程 0 完成所有分配的任务需要 20 个时间单元（10+6+4），线程 1 需要 8 个时间单元（4+2+2），线程 2 需要 5 个时间单元（2+2+1），线程 3 则只需要 3 个时间单元（1+1+1）。图 1（a）展示了这一任务分配状态，由此可见，完成全部十二项任务总共需要 20 个时间单元（完成整个任务所需时间应以最后完成的子任务用时为准）。

图 1：四条线程之间的任务分配示例。

您也可以采用一种更合理的任务分配法，即线程 0 完成一项任务所需时间是 {10}，线程 1 完成四项任务所需时间是 {4, 2, 1, 1}，线程 2 完成三项任务所需时间是 {6, 1, 1}，而线程 3 完成四项任务所需时间是 {4, 2, 2, 2}（如图 1（b）所示）。这样安排时间的优势是完成整个任务只需 10 个时间单元，四条线程中只有两条线程分别闲置了 2 个时间单元。

建议

如果完成所有任务所需时间长度相同，则在可用线程之间实施静态任务分配（即将整个任务划分为相同数量的子任务组并将每个子任务组分配给每条线程）是一种简单且合理的解决方案。但实际上就算事先已知道所有任务的执行时间长度，要找到一个在线程间实施最佳任务分配的方法仍然十分困难。如果各项子任务的执行时间长度不同，则可能需要采用一种更加动态的任务分配法来分配线程任务。
在默认情况下，OpenMP* 向线程调度迭代的策略是静态调度（如果不是静态调度则会另外注明）。当迭代之间的工作负载不同以及负载模式不可预知时，采用动态调度迭代的方法可以更好地平衡负载。动态调度和指数调度这两种静态调度替代方案都会通过 schedule 子句指定。在动态调度下，迭代数据块分配给线程；一旦分配完成，线程会申请获得一个新的迭代数据块。Schedule 子句的可选数据块参数会指明用于动态调度的迭代数据块固定尺寸。

- collapse source view plain copy to clipboard print ?

#pragma omp parallel for schedule(dynamic, 5)
for (i = 0; i < n; i++)
{
unknown_amount_of_work(i);
}

#pragma omp parallel for schedule(dynamic, 5)
  for (i = 0; i < n; i++)
  {
    unknown_amount_of_work(i);
  }

指数调度最初会向线程分配大型迭代数据块；分配给所需线程的迭代数量会随着未分配迭代集的减少而减少。由于分配模式不同，指数调度的开销往往少于动态调度。Schedule 子句的可选数据块参数会指明在指数调度下一个数据块中所分配的迭代最低数量。

- collapse source view plain copy to clipboard print ?

#pragma omp parallel for schedule(guided, 8)
for (i = 0; i < n; i++)
{
uneven_amount_of_work(i);
}

#pragma omp parallel for schedule(guided, 8)
  for (i = 0; i < n; i++)
  {
    uneven_amount_of_work(i);
  }

其中一个特例是迭代之间的工作负载单调递增或递减。例如，下三角形矩阵中每行元素数量会以正则表达式的形式增加。在此类情况下，通过静态调度设置一个相对较低的数据块尺寸（创建大量数据块/任务）可能有助于实现良好的负载平衡，同时还不会产生采用动态调度或指数调度所导致的开销。

- collapse source view plain copy to clipboard print ?

#pragma omp parallel for schedule(static, 4)
for (i = 0; i < n; i++)
{
process_lower_triangular_row(i);
}

#pragma omp parallel for schedule(static, 4)
  for (i = 0; i < n; i++)
  {
    process_lower_triangular_row(i);
  }

如果调度策略不明显，采用运行时调度可以随意改变数据块尺寸和调度类型，而无需对程序进行重新编译。
在使用英特尔® 线程构建模块（英特尔® TBB）的 parallel_for 算法时，调度程序会将迭代空间划分为可分配给线程的小型任务。一旦某些迭代的计算用时比其它迭代长，英特尔® TBB 调度程序能够从线程中动态“盗取”任务，以便更好地实现线程间的工作负载平衡。
显式线程模式（如 Windows* 线程、Pthreads* 和 Java* 线程）无法自动为线程调度一系列独立任务。编程人员必须根据需要将这种能力编入应用程序中。静态调度任务是一种十分简单、直接的调度方法，而动态调度任务则可通过两种相关的方法轻松予以实施：生产者/消费者（Producer/Consumer）模式和老板/工人（Boss/Worker）模式。在前一个模式下，一条线程（生产者）会将任务置入共享队列结构中，而消费者线程会根据需要清除要处理的任务。生产者/消费者模式通常适用于在任务分配给消费者线程之前需要进行预处理之时（但也并非一定得采用这种模式）。
在老板/工人模式下，工人线程与老板线程会在需要直接分配的工作任务增多时会合。在划分任务十分简单的情况下（如将各类指数分配给数组进行处理），可以采用具备适宜同步化程度的全局计数器来取代单独的老板线程，即工人线程访问当前数值并针对下一条需要承担更多工作任务的线程调整（可能增加）计数器。
无论采用哪种任务调度模式，您都必须使用适量的线程和正确的线程组合，以确保这些肩负工作任务的线程执行所需计算任务，而不是进入闲置状态。例如，如果消费者线程有时处于闲置状态，则您需要减少消费者线程数量或可能需要再配备一条生产者线程。采用何种解决方案主要取决于算法以及需要分配的任务数量与执行时间长度。

使用指南

所有动态任务调度方法都将因分配任务而产生一定的开销。将独立的小型任务整合成为一项可分配的工作任务有助于减少上述开销；相应地，如果采用 OpenMP schedule 子句，您需要在任务内设置代表最少迭代次数的非默认数据块尺寸。将一项任务划分成多项计算任务的最佳方法取决于需要完成的计算量、线程的数量以及执行计算任务时可以使用的其它资源。

通过避免或消除人工依赖性实现并行性

提交新文章

Published On :
2010年01月14日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

实现线程之间应用工作负载平衡是确保出色性能的关键。实现负载平衡主要是为了最大限度缩短线程的闲置时间。在尽量减少工作任务分配开销的情况下，在所有线程之间平均分配工作负载，可以减少浪费在不能进行运算的闲置线程上的时间，进而可显著提高性能。然而，实现完美的负载平衡绝非易事，这主要取决于应用并行性、工作负载、线程数量、负载平衡策略和线程实施情况。
本文是《英特尔® 多线程应用开发指南》系列的一部分，该系列介绍了针对英特尔® 平台开发高效多线程应用的指导原则。

背景

面向并行处理的多线程是确保性能的重要因素，同时也对确保每个线程高效运行起着重要的作用。尽管优化编译器有助于实现这一点，程序员一般不会通过重复利用数据以及选择有利于设备的指令，来更改源代码以提高性能。遗憾的是，可提高串行性能的相同方法也会带来数据相关性，从而难以通过多线程获得更出色的性能。
重复使用中间结果来避免重复计算就是一个例子。例如，用相邻图像中的加权平均像素（包括该图像）来替换每个图像像素，便可通过模糊的方式来弱化图像。以下伪代码介绍了 3x3 模糊模板：

- collapse source view plain copy to clipboard print ?

for each pixel in (imageIn)
sum = value of pixel
// compute the average of 9 pixels from imageIn
for each neighbor of (pixel)
sum += value of neighbor
// store the resulting value in imageOut
pixelOut = sum / 9

for each pixel in (imageIn)
  sum = value of pixel
  // compute the average of 9 pixels from imageIn
  for each neighbor of (pixel)
    sum += value of neighbor
  // store the resulting value in imageOut
  pixelOut = sum / 9

事实上，多种计算都会使用所有的像素值，从而有助于通过重复使用数据来提高性能。在以下伪代码中，中间结果被计算和使用了三次，从而获得了更佳的串行性能。

- collapse source view plain copy to clipboard print ?

subroutine BlurLine (lineIn, lineOut)
for each pixel j in (lineIn)
// compute the average of 3 pixels from line
// and store the resulting value in lineout
pixelOut = (pixel j-1 + pixel j + pixel j+1) / 3
declare lineCache[3]
lineCache[0] = 0
BlurLine (line 1 of imageIn, lineCache[1])
for each line i in (imageIn)
BlurLine (line i+1 of imageIn, lineCache[i mod 3])
lineSums = lineCache[0] + lineCache[1] + lineCache[2]
lineOut = lineSums / 3

subroutine BlurLine (lineIn, lineOut)
  for each pixel j in (lineIn)
    // compute the average of 3 pixels from line
    // and store the resulting value in lineout
    pixelOut = (pixel j-1 + pixel j + pixel j+1) / 3

declare lineCache[3]
lineCache[0] = 0
BlurLine (line 1 of imageIn, lineCache[1])
for each line i in (imageIn)
  BlurLine (line i+1 of imageIn, lineCache[i mod 3])
  lineSums = lineCache[0] + lineCache[1] + lineCache[2]
  lineOut = lineSums / 3

这种优化方式使得输出图像的相邻行的计算之间产生了相关性。如果并行计算该循环的迭代，相关性将会造成错误的结果。
另一个常见的例子是循环内部的指针发生偏移：

- collapse source view plain copy to clipboard print ?

ptr = &someArray[0]
for (i = 0; i < N; i++)
{
Compute (ptr);
ptr++;
}

ptr = &someArray[0]
for (i = 0; i < N; i++)
{
  Compute (ptr);  
  ptr++;
}

通过增加 ptr，代码可能会利用寄存器增量的快速运算方法，并避免使用计算所有迭代的 someArray[i] 的算法。在所有计算相互独立时，指针将会产生依赖性，它在每次迭代中的值将取决于其在之前迭代中的值。
最后，经常会发生这样的情况，当需要执行并行算法时，数据结构已被用于其它目的，从而会无意地阻碍并行性。稀疏矩阵算法就是这样的例子。因为大多数矩阵元素都为零，常规矩阵表达式通常会被“封装的 (packed)”形式所代替，包含了元素值以及相关的偏移量，用来跳过零值的项。
本文介绍了在这些棘手情形中有效引入并行性的策略。

建议

当然，最好能够找到无需移除现有优化或进行大量源代码变更同时能够充分利用并行性的方式。在移除串行优化以利用并行性之前，需要考虑是否能够通过将现有内核运用于整体问题的子集来保留优化。通常情况下，如果初始算法包含了并行性，则也可以将子集作为独立单元进行定义，并进行并行计算。
为了有效地实现模糊运算线程化，可以考虑将图像细分为子图像，或固定大小的数据块。模糊算法支持独立地对数据块进行计算。以下伪代码阐释了图像模块化的使用方法：

- collapse source view plain copy to clipboard print ?

// One time operation:
// Decompose the image into non-overlapping blocks.
blockList = Decompose (image, xRes, yRes)
foreach (block in blockList)
{
BlurBlock (block, imageIn, imageOut)
}

// One time operation:
// Decompose the image into non-overlapping blocks.
blockList = Decompose (image, xRes, yRes)

foreach (block in blockList)
{
BlurBlock (block, imageIn, imageOut)
}

用于模糊整个图像的现有代码可在执行 BlurBlock 时重复使用。利用 OpenMP 或显式线程来并行运算多个数据块有助于获得多线程优势，并保留最初优化的内核。
在其它情况下，由于现有串行优化的优势不足以冲抵所有迭代的整体成本，所以没有必要进行模块化。通常在迭代的粗粒度足以使并行处理加速时会出现此类情况。指针增量就是这样的例子。归纳变量可以轻松地为显式指数 (explicit indexing) 所取代，从而移除相关性，并支持循环进行简单的并行处理。

- collapse source view plain copy to clipboard print ?

ptr = &someArray[0]
for (i = 0; i < N; i++)
{
Compute (ptr[i]);
}

ptr = &someArray[0]
for (i = 0; i < N; i++)
{
  Compute (ptr[i]);
}

注意，初始优化虽然比较小，但不可丢失。编译器通常会通过利用增量或其它快速运算对指数计算进行大范围的优化，从而带来串行和并行性能的双重优势。
在其它情况下，对涉及封装稀疏矩阵的代码进行线程化更加困难。通常情况下，对数据结构进行解包并不可行，但通常可以将矩阵细分为数据块，将指针存储在每个数据块的开始位置。当这些矩阵与合适的数据块算法实现配对时，便可同时获得封装表达式和并行性的双重优势。
上面介绍的模块化方法是一种更加普遍的方法，该方法被称为“域分解 (domain decomposition)。”分解后，每个线程都可在一个或多个域中独立运行。在某些情况下，算法和数据的特性可以表明，每个域中的工作几乎是连续进行的。在其它情况下，工作的总量会因域的不同而有所差异。而在域的数量与线程的数量相等的情况下，并行性能将会受到负载不平衡的限制。总而言之，最好能够确保域的数量要大于线程的数量。这将有助于通过动态调度 (dynamic scheduling) 等技术来实现整个线程的负载平衡。

使用准则

一些串行优化能够带来巨大的性能提升。要确保并行处理加速的优势超过与移除优化有关的性能损失，考虑一下所需的处理器的数量。
引入数据块算法有时会阻碍编译器区分别名 (aliased) 和非别名 (unaliased) 数据。如果在模块化后，编译器无法再确定数据是否属于非别名数据，那么性能将会受到影响。可考虑利用严格的关键词来明确地阻止进行别名化 (aliasing)。利用程序间的优化也能帮助编译器检测非别名数据。

任务取代线程工具

提交新文章

Published On :
2010年01月21日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

任务是可以取代线程的小巧解决方案，借助它可提高启动和关机速度，实现更好的负载平衡，高效使用可用资源以及提高抽象化水平。英特尔® 线程构建模块（英特尔® TBB）和 OpenMP* 都是包括基于任务的编程模式。本文将简要介绍基于任务的编程，并会指导您应何时使用线程或任务。

本文是《英特尔® 多线程应用开发指南》系列的一部分，后者用于指导开发人员针对英特尔”® 平台开发高效的多线程应用。

背景

对于多线程编程来说，直接使用本地线程包编程并不理想。这些本地线程包所创建的线程均为逻辑线程，它们通过操作系统映射到硬件的物理线程上。创建太少逻辑线程将会导致系统认购不足，进而造成部分可用硬件资源的浪费。创建太多的逻辑线程将会导致系统认购过多，这样一来操作系统需承担大笔开销，因为需要分段访问硬件资源。通过直接使用本地线程，开发人员负责将应用中的并行处理与硬件中的资源进行匹配。

执行这个平衡任务很困难，最普通的方法是创建一个能在整个应用生命周期中使用的线程池。通常需要为每个物理线程创建一个逻辑线程。然后，应用会动态地向线程池中的线程调度计算。使用线程池不仅有助于并行处理与硬件资源的匹配，同时也可避免因重复创建和销毁线程而产生的花费。

一些并行编程模式，例如 Intel TBB 和 OpenMP API 为开发人员提供了线程池优势，而且他们无需管理线程池。借助这些模式，开发人员用任务来表示应用中的逻辑并行处理，并且运行库会将这些任务调度至工作线程的内部池中。借助任务，开发人员可专注于应用的逻辑并行处理，而无需担心并行器的管理。同时，鉴于任务较线程更加轻便，因此能以更加精细的粒度来表达并行。

下面是使用任务的一个示例。函数fibTBB calculates the n^th使用一个 TBBtask_group来计算第 n 个斐波纳契数。每次调用至 n >= 10 时，将会创建一个任务组，并且有两个任务运行。本示例中，描述每个任务的一个 lambda 表达式（拟定 C++0x 标准的一个特性）被传递给函数运行。这些调用产生了任务，从而可被线程池中的线程所执行。随后的调度函数将等待拦截，直至任务组的所有任务都已运行完毕。

- collapse source view plain copy to clipboard print ?

int fibTBB(int n) {
if( n<10 ) {
return fibSerial(n);
} else {
int x, y;
tbb::task_group g;
g.run([&]{x=Fib(n-1);}); // spawn a task
g.run([&]{y=Fib(n-2);}); // spawn another task
g.wait(); // wait for both tasks to complete
return x+y;
}
}

int fibTBB(int n) {
  if( n<10 ) {
    return fibSerial(n);
  } else {
    int x, y;
    tbb::task_group g;
    g.run([&]{x=Fib(n-1);}); // spawn a task
    g.run([&]{y=Fib(n-2);}); // spawn another task
    g.wait();                // wait for both tasks to complete
    return x+y;
  }
}

例程 fibSerial 被假定为一个序列变量。尽管任务比线程更能实现精细的并行，但与一个子程序调用相比，其开销仍非常大。因此，串行解决小型子问题更加划算。

另一个支持任务的运行库是 OpenMP API。与 Intel TBB 不同，这些模式均需要编译支持，其特点是接口较为简单，但不便于携带。例如，上述使用 TBB任务执行的斐波纳契示例，同样也可使用 OpenMP任务作为 fibOpenMP 来执行。因为 OpenMP 需要编译支持，只需要简单的编程就可以指示任务。然而，只有支持 OpenMP API 的编译器才会理解这些程序。

- collapse source view plain copy to clipboard print ?

int fibOpenMP( int n ) {
int i, j;
if( n < 10 ) {
return fibSerial(n);
} else {
// spawn a task
#pragma omp task shared( i ), untied
i = fib( n - 1 );
// spawn another task
#pragma omp task shared( j ), untied
j = fib( n - 2 );
// wait for both tasks to complete
#pragma omp taskwait
return i + j;
}
}

int fibOpenMP( int n ) {
  int i, j;
  if( n < 10 ) {
  return fibSerial(n);
  } else {
    // spawn a task
  #pragma omp task shared( i ), untied
    i = fib( n - 1 ); 
    // spawn another task
  #pragma omp task shared( j ), untied
    j = fib( n - 2 );
    // wait for both tasks to complete
  #pragma omp taskwait
  return i + j;
  }
}

Intel TBB 和 OpenMP API 通过工作窃取来管理任务调度。在工作窃取过程中，线程池中的每个线程维护一个双端列队本地任务池。一个线程像使用堆栈一样使用自身的任务池，并将所产生的新任务推堆栈顶部。当一个线程执行了一个任务, 它会首先从本地堆栈的顶部弹出一个任务。堆栈顶部的任务是最新的，因此最有可能访问到数据缓存中的热点数据。如果本地任务池中没有任务，它会试图从另一线程（）那里窃取工作。当工作被窃取时，一个线程会将偷窃对象的双端队列作为普通队列来使用，因，所窃取的仅是偷窃对象双端队列中最旧的任务。对于递归算法，这些最旧的任务均为位于任务树高处的节点，因此属于大型工作块，并且通常不是偷窃对象数据缓存中的热点。因此，工作窃取是一个实现负载平衡并且维持本地化缓存的高效机制。

当任务库被启用时，开发人员将无法看到线程池和向线程分配任务的工作窃取调度器。因此，任务提供了高水平的抽象，用户在考虑其应用中的逻辑并行性时，无需担心并行处理器的管理。工作窃取提供的负载平衡、低任务创建与销毁成本使基于任务的平衡处理成为大部分应用的高效解决方案。

使用指南

尽管任务通常是添加线程并增强性能的最好方法，但如果使用不当，仍会造成一些问题。Intel TBB 和 OpenMP API 使用的任务调度器均为非抢占型。因此，任务主要面向无障碍的高性能运算。如果任务阻碍较少，那么也可以使用任务。然而，如果任务阻碍非常频繁，那么当一个任务受阻时，性能将会受到损失，而且已经分配任务的线程也无法执行其他任务。若等待 I/O 或互拆时间过长，通常会发生阻碍现象。如果线程持有互拆时间过长，那么无论有多少线程，代码也无法被充分执行。对于阻碍任务，最好使用线程而非任务。

即使任务为最佳方案时，也不一定要从头开始执行任务模式。Intel TBB 库不仅提供了任务接口，同时也提供了高层次运算来执行最普通的任务模式，例如 parallel_invoke、parallel_for、parallel_reduce 和管线等。OpenMP AP 提供并行循环。由于这些模式已被调校和测试，因此应该尽可能使用这些高层次运算。

下面的示例为一个使用 tbb::parallel_for 进行运算的简单串行循环及其并行版本。

- collapse source view plain copy to clipboard print ?

// serial loop
for (int i = 0; i < 10000; ++i)
a[i] = f(i) + g(i);
// parallel loop
tbb::parallel_for( 0, 10000, [&](int i) { a[i] = f(i) + g(i); } );

// serial loop
for (int i = 0; i < 10000; ++i)
  a[i] = f(i) + g(i);

// parallel loop
tbb::parallel_for( 0, 10000, [&](int i) { a[i] = f(i) + g(i); } );

上述示例中，TBB parallel_for 创建的任务将循环体，即 a[i] = f(i) + g(i)，应用到了 [0,10000) 范围内的所有元素。Lambda 表达式中的 & 表示变量 a 应被参考捕获。当使用 parallel_for 时，TBB 运行库在一个任务中选择了适当数量的迭代，从而最大限度地减少开销，并为负载平衡提供大量任务。

更多资源

-----------------------------华丽分割线-----------------------------

发掘有序数据流的数据并行性

提交新文章

Published On :
2010年01月19日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

许多计算密集型应用都涉及从有序输入数据到有序输出数据的复杂转换。例如声音与视频代码转换、无损数据压缩，以及地震数据处理。然而这些转换中使用的算法通常都是并行的，所以管理 I/O 顺序依赖性将面临挑战。本文介绍了一些此类挑战，并阐述了有关应对这些挑战，同时确保并行性能的策略。

本文是《英特尔® 多线程应用开发指南》系列的一部分，该系列介绍了针对英特尔® 平台开发高效多线程应用的指导原则。

背景

考虑对视频压缩引擎进行线程化，从现场视频资源到磁盘或网络客户端，该引擎专门用于实时处理未压缩的视频。显而易见，满足此类应用的实时需求的关键便是充分利用多个处理器的性能优势。

MPEG2 和 MPEG4 等视频压缩标准专门针对在不可靠的链接上进行流处理而设计。因此，用户可以轻松地将一个视频流作为一系列更小的单独视频流来处理。通过以并行的方式处理这些更小的视频流，速度可得到显著的提升。通过多线程来获得此类并行性所带来的优势将面临以下挑战：

定义问题的非重叠子集，并将其分配到线程中
确保输入数据可被准确、即时地读取，并确保其排列顺序正确无误
无论处理完成后的实际顺序如何，都要以正确的顺序导出数据块，并确保不会对性能造成重大影响
执行上述操作时，不知道输入数据的实际范围

在其它情况下，例如无损数据压缩，通常能够提前确定输入数据的大小，并明确地将数据划分为单独的输入数据块。这里所述的方法同样适用于本例。

建议

使用该方法可能是希望创建一个生产者和消费者链条，但该方法不具可扩展性，并且容易导致负载不平衡。相反，本文所采用的数据分解能够应对上述所有挑战，从而实现扩展性更高的设计。
此处所采取的方法是创建一组线程，每个线程都能够读取视频数据块，并对其进行编码，然后将其输出到重排序缓冲区。在完成对一个数据块的处理后，线程将返回读取并处理下一个视频数据块，以此类推。这种动态分配方法可以最大限度地减少发生负载不平衡的可能性。重排序缓冲区能够确保以正确的顺序写入编码的视频数据块，而不受其完成时的顺序的影响。

初始视频编码算法可能采取这种形式：

- collapse source view plain copy to clipboard print ?

inFile = OpenFile ()
outFile == InitializeOutputFile ()
WriteHeader (outFile)
outputBuffer = AllocateBuffer (bufferSize)
while (frame = ReadNextFrame (inFile))
{
EncodeFrame (frame, outputBuffer)
if (outputBuffer size > bufferThreshold)
FlushBuffer(outputBuffer, outFile)
}
FlushBuffer (outputBuffer, outFile)

inFile = OpenFile ()
outFile == InitializeOutputFile ()
WriteHeader (outFile)
outputBuffer = AllocateBuffer (bufferSize)
while (frame = ReadNextFrame (inFile))
{
  EncodeFrame (frame, outputBuffer)
  if (outputBuffer size > bufferThreshold)
    FlushBuffer(outputBuffer, outFile)
}
FlushBuffer (outputBuffer, outFile)

首先要利用基于数据块的算法来替换读取和编码帧的结果，提出在一组线程内进行分解的问题。

- collapse source view plain copy to clipboard print ?

WriteHeader (outFile)
while (block = ReadNextBlock (inFile))
{
while(frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
if (outputBuffer size > bufferThreshold)
FlushBuffer (outputBuffer, outFile)
}
FlushBuffer (outputBuffer, outFile)
}

WriteHeader (outFile)
while (block = ReadNextBlock (inFile))
{
  while(frame = ReadNextFrame (block))
  {
    EncodeFrame (frame, outputBuffer)
    if (outputBuffer size > bufferThreshold)
      FlushBuffer (outputBuffer, outFile)
  }
  FlushBuffer (outputBuffer, outFile)
}

数据块的定义因应用的不同而有所差异,但在视频数据流情况下,自然数据块边界可能是第一个帧,在该帧的输入中检测到场景发生变化，并且会受到最小和最大数据块的限制。基于数据块的处理要求在处理前对输入缓冲进行分配，并对源代码进行少量变更以填满缓冲区。同样，必需对 readNextFrame 方法进行更改，以便从缓冲区（而非文件）读取。

接下来改变输出缓冲策略，以确保能够将整个数据块作为一个单元进行写入。这种方法显著简化了输出重新排序的方式，因为只要确保以正确的顺序输出数据块即可。以下代码反映了对基于数据块的输出所进行的变更：

根据最大数据块的体积，可能需要较大的输出缓冲区。

因为每个数据块之间都是相互独立的，所以通常所有输出数据块会以特定的头为开始。在 MPEG 视频数据流中，与已定义的未来帧相比，该头先于完整的帧,被称为 I 帧。因此，该头被迁移到了数据块上方的循环中：

- collapse source view plain copy to clipboard print ?

while (block = ReadNextBlock (inFile))
{
WriteHeader (outputBuffer)
while (frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
}
FlushBuffer (outputBuffer, outFile)
}

while (block = ReadNextBlock (inFile))
{
  WriteHeader (outputBuffer)
  while (frame = ReadNextFrame (block))
  {
    EncodeFrame (frame, outputBuffer)
  }
  FlushBuffer (outputBuffer, outFile)
}

借助这些变化，可以利用线程库（即，Pthreads 或 Win32 线程 API）或 OpenMP 引入并行性。

- collapse source view plain copy to clipboard print ?

// Create a team of threads with private
// copies of outputBuffer, block, and frame
// and shared copies of inFile and outFile
while (AcquireLock,
block = ReadNextBlock (inFile),
ReleaseLock, block)
{
WriteHeader (outputBuffer)
while (frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
}
FlushBuffer (outputBuffer, outFile)
}

// Create a team of threads with private
// copies of outputBuffer, block, and frame
// and shared copies of inFile and outFile
while (AcquireLock,
       block = ReadNextBlock (inFile),
       ReleaseLock, block)
{
  WriteHeader (outputBuffer)
  while (frame = ReadNextFrame (block))
  {
    EncodeFrame (frame, outputBuffer)
  }
  FlushBuffer (outputBuffer, outFile)
}

这是一种简单而有效的策略，有助于安全、有序地读取数据。所有线程都需要一个锁定，读取数据块，然后释放该锁。共享输入文件可以确保按顺序读取数据块，并且只读取一次。因为准备线程通常需要一个锁，因此需要以动态或先到先得 (first-come-first-served) 的方式分配数据块，这样通常可以最大限度地避免负载不平衡。

最后的任务是确保能够以正确的顺序安全地输出数据块。其中一个简单的方法是利用锁和共享的输出文件来确保一次只写入一个数据块。这种方法能够确保线程的安全，但可能会以其它顺序（而非初始顺序）输出数据块。另外，线程将一直处于等待状态，直到刷新输出之前写入所有之前的数据块。很遗憾，这种方法会使效率降低，因为线程在等待写入时处于闲置状态。

更有效的方法是针对输出数据块创建循环的重新排序缓冲区。为每个数据块指派按顺序排列的序列号。缓冲区的“末端 (tail)”将会创建下一个将要写入的数据块。如果线程可以完成对数据块的处理，而无需缓冲区末端的指派，那么它会将数据块排列在合适的缓冲区位置，然后返回读取并处理下一个数据块。同样，如果线程发现刚刚完成的数据块是由缓冲区末端指派，那么它将会写入该数据块，以及之前排列的其它临近的数据块。最后，它将更新缓冲区末端，以指向下一个将要输出的数据块。重新排序缓冲区允许完成后的数据块以乱序的方式排列，同时确保有序地写入这些数据块。

图 1. 写入前示例重新排序缓冲区的状态。

图 1 阐述了重新排序缓冲区的一个可能的状态。数据块 0 至 35 已经得到处理和写入，而数据块 37、38、39、40 和 42 已得到处理，正在排队等待写入。在线程完成对数据块 36 的处理后，它将写出数据块 36 至 40，使重新排序缓冲区处于如图 2 所示的状态。在数据块 41 完成处理之前，数据块 42 将仍然排列在队列中。

图 2. 写入后示例重新排序缓冲区的状态。

当然，您需要采取特定的预防措施，以确保该算法快速高效：

读取或写入时，共享的数据结构必须处于锁定状态。
缓冲区中的插槽数量必须多于线程数量。
如果缓冲区中不具有合适的插槽，线程必须有效地等待。
为每个线程预先分配多个输出缓冲区，以便使指针 (pointer) 在缓冲区中排队，并避免进行无关的数据复制和内存分配。

使用输出队列时，最终算法如下所示：

- collapse source view plain copy to clipboard print ?

inFile = OpenFile ()
outFile == InitializeOutputFile ()
// Create a team of threads with private
// copies of outputBuffer, block, and frame, shared
// copies of inFile and outFile.
while (AcquireLock,
block = ReadNextBlock (inFile),
ReleaseLock, block)
{
WriteHeader (outputBuffer)
while (frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
}
QueueOrFlush (outputBuffer, outFile)
}

inFile = OpenFile ()
outFile == InitializeOutputFile ()
// Create a team of threads with private 
// copies of outputBuffer, block, and frame, shared
// copies of inFile and outFile.
while (AcquireLock,
       block = ReadNextBlock (inFile),
       ReleaseLock, block)
{
  WriteHeader (outputBuffer)
  while (frame = ReadNextFrame (block))
  {
    EncodeFrame (frame, outputBuffer)
  }
  QueueOrFlush (outputBuffer, outFile)
}

该算法支持有序 I/O，但还可提供灵活的高性能和无序并行处理方法。

使用准则

在某些情况下，读取和写入数据的时间与处理数据所需的时间相当。本例中，以下方法可能更实用：

Linux* 和 Windows* 可提供 API 来启动读写操作，以及之后进行等待或告知完成处理。利用这些接口来预取输入数据，以及之后写入输出数据，同时执行其它计算，可以有效地规避 I/O 延迟。在 Windows 中，通过提供 FILE_FLAG_OVERLAPPED 属性，可打开异步 I/O 的文件。在 Linux 中，异步运算会受到许多 aio_* 函数（由 libaio 提供）的影响。
当输入数据的量较大时，由于硬件试图同时为大量并发但非连续的读取提供服务，因此静态分解方法容易导致物理磁盘发生“抖动（thrashing）”。按照以上共享文件中所述的建议，采用动态、先到先得的算法能够执行有序、连续的读取操作，从而显著提高整体 I/O 子系统的吞吐量。

仔细选择数据块的大小和数量至关重要。通常，数量庞大的数据块可以提供最高的灵活性，从而减少负载不平衡的情况。另一方面，数量非常小的数据块可能带来不必要的锁定开销，甚至造成数据压缩算法效率的下降。

更多资源

-----------------------------华丽分割线-----------------------------

第二章、同步处理

本章节将主要谈论采用哪些技术来降低同步处理对性能的负面影响。

-----------------------------华丽分割线-----------------------------

管理锁争用：大、小关键代码段（Critical Section）

提交新文章

Published On :
2010年01月21日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

在多线程应用中，程序员会使用锁来同步线程进入可访问共享资源的代码区域的行为。受这些锁保护的代码区域被称为关键代码段（Critical Section）。如果关键代码段中已存在一条线程，那么其它任何线程都不可进入该代码段。由此可见，关键代码段采用序列化执行方式。本文介绍了关键代码段大小这一概念及其对性能的影响。关键代码段大小指线程在关键代码段中花费的时间长度。

本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

关键代码段可在多条线程尝试访问共享资源时确保数据的完整性。它们还对自身内部的代码执行进行了序列化。线程应尽量缩短在关键代码段中花费的时间，进而减少其它线程在代码段外闲置等待获得锁的时间——这种状态被称之为“锁争用”。换句话说，关键代码段越小越好。然而，使用大量独立的小代码段会导致与获取和释放各个独立锁相关的系统开销。本文中描述的情景阐明了什么时候最适合使用大型或小型关键代码段。

代码示例 1 中的线程函数包含两个关键代码段。假设这两个关键代码段可保护不同数据，并且函数 DoFunc1 和 DoFunc2 中的工作是相互独立的。与此同时，假设执行上述两个更新函数中的任意一个所花费的时间都非常短。

代码示例 1：

- collapse source view plain copy to clipboard print ?

Begin Thread Function ()
Initialize ()
BEGIN CRITICAL SECTION 1
UpdateSharedData1 ()
END CRITICAL SECTION 1
DoFunc1 ()
BEGIN CRITICAL SECTION 2
UpdateSharedData2 ()
END CRITICAL SECTION 2
DoFunc2 ()
End Thread Function ()

Begin Thread Function ()
  Initialize ()

  BEGIN CRITICAL SECTION 1
    UpdateSharedData1 ()
  END CRITICAL SECTION 1

  DoFunc1 ()

  BEGIN CRITICAL SECTION 2
    UpdateSharedData2 ()
  END CRITICAL SECTION 2

  DoFunc2 ()
End Thread Function ()

关键代码段被一个 DoFunc1 调用请求分离开来。如果线程在 DoFunc1 函数上只花费了很短的时间，那么同步两个关键代码段所产生的开销根本没有实际意义。在这种情况下，更好的方案是将两个小关键代码段合并为一个稍大的关键代码段，如代码示例 2。

代码示例 2：

- collapse source view plain copy to clipboard print ?

Begin Thread Function ()
Initialize ()
BEGIN CRITICAL SECTION 1
UpdateSharedData1 ()
DoFunc1 ()
UpdateSharedData2 ()
END CRITICAL SECTION 1
DoFunc2 ()
End Thread Function ()

Begin Thread Function ()
  Initialize ()

  BEGIN CRITICAL SECTION 1
    UpdateSharedData1 ()
    DoFunc1 ()
    UpdateSharedData2 ()
  END CRITICAL SECTION 1

  DoFunc2 ()
End Thread Function ()

如果花费在 DoFunc1 函数上的时间远远超过执行两个更新例程的总时间，那么该方案可能不可行。增加的关键代码段大小可提高出现锁争用现象的可能性，而且线程数量越多越是如此。

现在让我们假设上一示例中的情况稍有改变，线程在 UpdateSharedData2 函数上会花费较长时间，那么结果又会如何呢？此时，使用单个关键代码段同步到 UpdateSharedData1 和 UpdateSharedData2 的访问（如代码示例 2）不再是适当的解决方案，因为出现锁争用现象的几率增加了。执行过程中，获得关键代码段访问权的线程将在代码段中花费非常长的时间，导致所有其它线程全部阻塞在外。当占用锁的线程将锁释放后，正等待的线程中只有一条可进入关键代码段，所有其它线程还要阻塞很长一段时间。因此，在这种情况下，代码示例 1 反而是更好的选择。

将锁关联到特定共享数据是一项不错的编程实践。使用同一个锁保护到某共享变量的所有访问并不能阻止其它线程访问由不同锁保护的其它共享变量。假设使用共享数据结构，您可以为该结构中的每个元素创建一个独立的锁，或者创建单个锁来保护到整个结构的访问。考虑到更新元素的计算成本，这两种极端的方法都有可能是切实可行的解决方案。不过，最佳锁粒度也可能处于在这两者之间。例如，在某个指定的共享数组中，可以创建两个锁：一个用于保护偶数编号的元素，另一个则用于保护奇数编号的元素。

如果执行 UpdateSharedData2 函数需要较长时间，最佳方案是按照该例程划分工作，并创建新的关键代码段。在代码示例 3 中，原始的 UpdateSharedData2 函数被分解为两个使用不同数据进行运算的函数。这样做的原因是希望通过使用分离的关键代码段来减少锁争用。如果 UpdateSharedData2 的整个执行过程都不需要保护，您应该考虑在函数中需要访问共享数据的点插入关键代码段，而不是封闭整个函数调用。

代码示例 3：

- collapse source view plain copy to clipboard print ?

Begin Thread Function ()
Initialize ()
BEGIN CRITICAL SECTION 1
UpdateSharedData1 ()
END CRITICAL SECTION 1
DoFunc1 ()
BEGIN CRITICAL SECTION 2
UpdateSharedData2 ()
END CRITICAL SECTION 2
BEGIN CRITICAL SECTION 3
UpdateSharedData3 ()
END CRITICAL SECTION 3
DoFunc2 ()
End Thread Function ()

Begin Thread Function ()
  Initialize ()

  BEGIN CRITICAL SECTION 1
    UpdateSharedData1 ()
  END CRITICAL SECTION 1

    DoFunc1 ()

  BEGIN CRITICAL SECTION 2
    UpdateSharedData2 ()
  END CRITICAL SECTION 2

  BEGIN CRITICAL SECTION 3
    UpdateSharedData3 ()
  END CRITICAL SECTION 3

  DoFunc2 ()
End Thread Function ()

建议

根据获取和释放锁的开销调整关键代码段的大小。考虑整合小关键代码段，以分担锁定开销。将锁争用现象严重的大型关键代码段划分为较小的关键代码段。将锁关联至特定的共享数据，借以最大限度减少锁争用问题。最佳解决方案可能处于为每个共享数据元素创建一个锁和为所有共享数据创建一个锁两种极端之间。

切记，同步操作会将执行序列化。采用大关键代码段意味着算法本身的并发性非常低，或者线程间的数据划分并不理想。对于前者，只能更改算法。对于后者，可尝试为共享数据创建本地拷贝，支持线程异步访问。

之前对关键代码段大小和锁粒度的讨论并没有将环境切换成本考虑在内。当线程阻塞在关键代码段之外等待获取锁时，操作系统将使用活动线程交换闲置线程，这便是所谓的环境切换。一般来说，该行为很有用，可释放 CPU 以执行更重要的任务。然而，对于正等待进入小关键代码段的线程来说，使用旋转等待 (spin-wait) 循环可能比环境切换操作更为有效。但是，鉴于处于等待状态的线程在旋转等待循环中仍将占用 CPU 资源，只有当线程在关键代码段中所花费的时间极短，不良影响低于环境切换成本时，才推荐使用旋转等待循环。

代码示例 4 展示了使用 Win32 线程 API 时可采用的一种较为有效的试探法。该示例针对 Win32 CRITICAL_SECTION 对象使用了旋转等待选项。无法进入关键代码段的线程将自旋，而不是释放 CPU 资源。如果在旋转等待过程中 CRITICAL_SECTION 变为可用，便可避免环境切换。自旋计数参数决定了线程在进入阻塞状态前将旋转的次数。在单处理器系统中，自旋计数参数将被忽略。代码示例 4 将应用中所有线程的自旋次数均设定为 1000，而允许的最大自旋次数是 8000。

代码示例 4：

- collapse source view plain copy to clipboard print ?

int gNumThreads;
CRITICAL_SECTION gCs;
int main ()
{
int spinCount = 0;
...
spinCount = gNumThreads * 1000;
if (spinCount > 8000) spinCount = 8000;
InitializeCriticalSectionAndSpinCount (&gCs, spinCount);
...
}
DWORD WINAPI ThreadFunc (void *data)
{
...
EnterCriticalSection (&gCs);
...
LeaveCriticalSection (&gCs);
}

int gNumThreads;
CRITICAL_SECTION gCs;

int main ()
{
  int spinCount = 0;
  ...
  spinCount = gNumThreads * 1000;
  if (spinCount > 8000) spinCount = 8000;
  InitializeCriticalSectionAndSpinCount (&gCs, spinCount);
  ...
}

DWORD WINAPI ThreadFunc (void *data)
{
  ...
  EnterCriticalSection (&gCs);
  ... 
  LeaveCriticalSection (&gCs);
}

使用指南

在支持英特尔® 超线程技术（英特尔® HT 技术）的处理器中，需要对代码示例 4 中使用的自旋计数参数进行单独调整，因为旋转等待循环通常会对此类处理器的性能造成极大影响。与具备多个物理 CPU 的真正对称多处理器 (SMP) 系统不同，英特尔 HT 技术可在同一 CPU 核心上创建两路逻辑处理器。旋转线程和正执行有用任务的线程务必会争夺逻辑处理器资源。显而易见，与对称多处理器系统相比，旋转线程对采用英特尔超线程技术的系统中多线程应用性能的影响更大。在这种情况下，应将代码示例 4 中的旋转次数调低，或者根本不采用旋转等待循环。

更多资源

-----------------------------华丽分割线-----------------------------

采用线程化 API 提供的同步例程替代手工编码

提交新文章

Published On :
2010年01月20日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

应用编程人员有时候手工编写同步例程而非使用线程 API 提供的结构，以便减少同步开销，或提供不同于现有结构所提供的功能。遗憾的是，使用手工编写的同步例程可能对性能、性能调谐或多线程应用的调试造成负面影响。

本文是《英特尔® 多线程应用开指南》系列的一部分，后者用于指导开发人员针对英特尔 ® 平台开发高效的多线程应用。

背景

通常，编程人员喜欢手工编写同步例程，以避免有时候由线程 API 提供的同步例程产生的相关开销。编程人员自己编写同步例程的另外一个原因是，线程 API 提供的功能与实际需求能不完全匹配。遗憾的是，与使用线程 API 例程相比，手工编写同步例程存在严重的缺点。

这种缺点之一是不能确保针对不同的硬件架构与操作系统均能提供出色的性能。下面是一个以 C 语言手工编写的自旋锁示例，可帮助说明这些问题：

- collapse source view plain copy to clipboard print ?

#include <ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h>
void acquire_lock (int *lock)
{
while (_InterlockedCompareExchange (lock, TRUE, FALSE) == TRUE);
}
void release_lock (int *lock)
{
*lock = FALSE;
}
<ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h><ia64intrin.h></ia64intrin.h>

#include 

void acquire_lock (int *lock)
{
  while (_InterlockedCompareExchange (lock, TRUE, FALSE) == TRUE);
}

void release_lock (int *lock)
{
  *lock = FALSE;
}

编译器内部函数 _InterlockedCompareExchange 是一种互锁的内存操作，可确保在函数执行期间其它线程不能修改指定的内存位置。该函数首先将第一个参数中的地址对应的内存内容与第三个参数中的值进行比较，如果匹配，则将第二个参数中的值存储到第一个参数中指定的内存地址。在指定地址的内存内容中发现的初始值被内部函数返回。在本例中，acquire_lock 例程不停自旋，直到内存位置锁中的内容处于解锁状态(FALSE)，此时（通过将锁的内容设置为TRUE）获得锁并例程返回。release_lock 例程将内存位置锁的内容重新设为 FALSE ，以便释放锁。

尽管乍一看该锁的实施似乎非常简单高效，但是它存在以下几个问题：

如果许多线程在同一个内存位置自旋，在锁被释放时，该点就会出现过多的高速缓存无效和过多的内存流量，结果导致随着线程数量增加扩展能力变差。
该代码使用的原子内存基元可能不适用于所有处理器架构，因而限制了可移植性。
紧密的自旋循环可能导致某些处理器架构特性的性能变差，例如英特尔 ® 超线程技术。
While 循环对于操作系统来说好像是在执行有用的计算，但是它能对操作系统调度的公平性产生负面影响。

尽管解决所有这些问题的技术已存在，但它们通常使代码变得极其复杂，以至于难以验证其正确性。此外，很难做到代码调谐的同时保持可移植性。这些问题最好留给线程 API 的作者，后者有更多的时间对同步结构进行验证和调谐，以实现出色的可移植性和可扩展性。

手工编写同步例程的另一个严重缺点是，它通常会降低编程工具在线程化环境中的准确性。例如，英特尔 ® Parallel Studio 工具必须能够识别同步结构，以便提供有关线程化应用程序的性能（使用英特尔 ® Parallel Amplifier）和正确性（使用英特尔 ® Parallel Inspector）的精确信息。

线程工具在设计上通常会考虑发现和区别所支持线程API 提供的同步结构的功能。如果没有使用标准的同步 API 来实现，这些工具将难以发现和理解同步，如上面的示例所示。

有时候，编程人员以工具专用指令、编译指示或 API 调用的形式提供工具支持提示，以便发现和区别手工编写的同步例程。尽管为特定工具所支持，但与使用线程 API 同步例程相比，这样的提示可能导致应用程序分析准确性降低。出现性能问题的原因可能难以检测，或者线程更正工具可能会报告严重的竞争状态或失去同步。

建议

如果可能，尽量避免使用手工编写的同步例程。相反，使用您青睐的线程 API 提供的例程，例如面向英特尔 ® 线程构建块的 queuing_mutex 或 spin_mutex，omp_set_lock/omp_unset_lock，或面向 OpenMP* 的critical/end critical 指令，或面向 Pthreads* 的 pthread_mutex_lock/pthread_mutex_unlock。学习线程 API 同步例程，以便找到一个适合您应用的例程。

如果线程 API 中没有能够提供所需功能的同步例程，可考虑针对程序使用对同步要求不高或要求其它同步的不同算法。此外，专业的编程人员可以通过简单的 API 同步结构构建一个自定义同步结构，而非从零开始。如果因为性能原因而必须使用手工编写的同步例程，可以考虑使用预处理指令，以便能够轻松使用与线程 API 功能相当的同步例程替换手工编写的同步例程。

使用准则

编程人员如果通过简单的 API同步结构创建自定义同步结构，应避免在共享位置使用自旋循环，从而避免性能不可扩展。如果代码必须可移植，还应避免使用原子内存基元。线程性能和更正工具的准确性可能受到影响，因为这些工具可能无法推论出自定义同步结构的功能，即使构建该结构所使用的简单同步结构能够被正确识别。

其它资源

-----------------------------华丽分割线-----------------------------

选择合适的同步原语最大限度减少开销

提交新文章

Published On :
2010年01月20日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

如果线程在一个同步点等待，那么它们无法做有用功。然而，多线程程序中通常需要一定程度的同步化，明确的同步有时甚至优于数据复制或复杂的非阻塞调度算法，然而其本身也存在一些问题。当前市场上存在着大量同步技术，应用程序开发人员应选择一种适当的技术，从而最大限度地降低整体同步开销。

本文是《英特尔® 多线程应用开发指南》的一部分，该系列文章为开发面向英特尔? 平台的高效多线程应用提供了指导。

背景

同步本身可构建序列执行，因此限制了并行能力，而且可能降低整体应用性能。事实上，当前只有很少的多线程程序能够完全避免同步。但幸运的是，我们可通过选择合适的结构来减少与同步有关的系统开销。本文将阐述一些可用的解决方案，针对每个解决方案提供示例代码，并列举出它们的主要优缺点。

Win32* 同步 API

Win32 API 提供了几种保护原子性（atomicity）的机制，本章节主要讨论其中的 3 种。一个增量语句（increment statement ）（例如 = var++）说明了不同的结构。如果正在更新的变量在线程之间共享，那么加载→写入→存储指令必须为原子操作（即操作完成之前不能抢占指令序列。）下面的代码演示了如何使用这些 API。

- collapse source view plain copy to clipboard print ?

#include <windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h>
CRITICAL_SECTION cs; /* InitializeCriticalSection called in main() */
HANDLE mtx; /* CreateMutex called in main() */
static LONG counter = 0;
void IncrementCounter ()
{
// Synchronize with Win32 interlocked function
InterlockedIncrement (&counter);
// Synchronize with Win32 critical section
EnterCriticalSection (&cs);
counter++;
LeaveCriticalSection (&cs);
// Synchronize with Win32 mutex
WaitForSingleObject (mtx, INFINITE);
counter++
ReleaseMutex (mtx);
}
<windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h>

#include 

CRITICAL_SECTION cs; /* InitializeCriticalSection called in main() */
HANDLE mtx;  /* CreateMutex called in main() */
static LONG counter = 0;

void IncrementCounter ()
{
  // Synchronize with Win32 interlocked function
  InterlockedIncrement (&counter);

  // Synchronize with Win32 critical section
  EnterCriticalSection (&cs);
    counter++;
  LeaveCriticalSection (&cs);

  // Synchronize with Win32 mutex
  WaitForSingleObject (mtx, INFINITE);
    counter++
  ReleaseMutex (mtx);
}

比较这三种机制，进而说明哪种机制在各种同步方案中更为适合。Win32 互锁函数（InterlockedIncrement、InterlockedDecrement、InterlockedExchange、 InterlockedExchangeAdd、InterlockedCompareExchange）仅限于简单操作，但它们比关键区域更快。此外，需要调用的函数更少；进出一个 Win32 关键区域需要调用 EnterCriticalSection、 LeaveCriticalSection 或者 WaitForSingleObject 和 ReleaseMutex。互锁函数也同样无阻碍，但如果同步对象不可用，那么 EnterCriticalSection和WaitForSingleObject（或WaitForMultipleObjects）将阻碍线程。

如果需要一个关键区域，那么在一个 Win32 CRITICAL_SECTION 上实现同步化所需的开销远远低于实现 Win32 mutex、信号量和 event HANDLE 同步化所需的花费，因为前者是用户空间对象，而后者是内核空间对象。尽管 Win32 关键区比 Win32 mutexes 要快，然而它们并可通用。同其它内核对象一样，Mutexes 也可用于流程内同步化。采用 WaitForSingleObject 和 WaitForMultipleObjects 函数也将有等待时间。线程在指定时间期限结束后继续执行，而不是为获取一个互斥体而无限期等待。将等待时间设置为零，以便线程可无阻碍地测试一个互斥体是否可用。（请注意，使用 TryEnterCriticalSection 函数也可以无阻碍地检测一个 CRITICAL_SECTION 是否可用。）最后，如果一个线程终止而同时带有一个互斥体，操作系统将会发出信号进行处理，从而防止等待线程成为死锁。如果一个线程终止而带有 CRITICAL_SECTION，那么等待进入 CRITICAL_SECTION 的线程变为死锁。

当一个 Win32 线程试图获取一个已被另一线程持有的 CRITICAL_SECTION 或 mutex HANDLE 时，它会立即将 CPU 让与操作系统。通常来说，这是一个好现象。线程受到阻碍，CPU 可做有用功。然而，阻碍和疏通一个线程的开销较大。有时，线程在受阻塞之前试图再次获得锁则更具优势（例如，在 SMP 系统中，在较小的关键段）。Win32 CRITICAL_SECTION 具有一个用户可配置的自旋计数，用以控制放弃 CUP 之前线程的等待时间。InitializeCriticalSectionAndSpinCount 和 SetCriticalSectionSpinCount 函数为试图进入一个特定 CRITICAL_SECTION 的线程设定自转计数。

建议

例如，针对变量（例如增量、减量、交换量）的简单操作而采用速度更快、开销更低的 Win32 互锁函数。

当流程间需要同步化或时间等待，使用 Win32 mutex，信号量或 event HANDLE。否则请使用系统开销更低的 Win32 CRITICAL Sections。

使用 InitializeCriticalSectionAndSpinCount 和 SetCriticalSectionSpinCount 函数来控制 Win32 CRITICAL_SECTION 的自转计数。在放弃 CPU 之前，控制等待线程自转时间对于低争用和高争用关键区域尤为重要。自转计数可显著影响 SMP 系统和采用英特尔® 超线程技术处理器的性能。

英特尔® 线程构建模块同步化 API

英特尔® 线程构建模块（英特尔® TBB）针对原子操作提供了便携式包装器（模板类原子）和不同版本的互斥机制，其中包括在一个“原生”互斥体周围的包装器。鉴于前面已经讨论了采用原子操作和依赖于操作系统的同步化 API 的优势与不足，本章节将跳过tbb::原子和 tbb::互斥体，而将重点放在快速的用户级同步化类别，例如 spin_mutex、queuing_mutex、spin_rw_mutex 和 queuing_rw_mutex。

最简单的互斥为 spin_mutex。一个线程在获取 spin_mutex 上的锁之前将会保持等待状态。当只针对少数指令保留锁时，spin_mutex 例如，下面的代码使用一个互斥体 FreeListMutex 来保护一个共享的变量空闲表。

- collapse source view plain copy to clipboard print ?

Node* FreeList;
typedef spin_mutex FreeListMutexType;
FreeListMutexType FreeListMutex;
Node* AllocateNode()
{
Node* n;
{
FreeListMutexType::scoped_lock lock(FreeListMutex);
n = FreeList;
if( n )
FreeList = n->next;
}
if( !n )
n = new Node();
return n;
}

Node* FreeList;
typedef spin_mutex FreeListMutexType;
FreeListMutexType FreeListMutex;

Node* AllocateNode()
{
  Node* n;
  {
    FreeListMutexType::scoped_lock lock(FreeListMutex);
    n = FreeList;
    if( n )
    FreeList = n->next;
  }
  if( !n )
    n = new Node();
  return n;
}

scoped_lock 的构造函数将会一直等待，直到 FreeListMutex 上没有其它的锁。析构函数释放锁。AllocateNode 函数内另外的大括号的作用是尽可能缩短锁的生命周期，因此其它等待的线程才能尽快有机会获得锁。

英特尔 TBB 提供的另一个用户级自转互斥是 queuing_mutex，它也是用户级互斥，但与 spin_mutex 相比，queuing_mutex 更为公平。一个公平的互斥体让线程有秩序地抵达。公平互斥避免了“挨饿”线程，因为每个线程均能轮到。不公平互斥较公平互斥的速度更为快些，因为它们首先让正在运行的线程通过，而不是按顺序通过，因此部分线程可能会因中断而进入睡眠状态。如果非常注重可扩展性和公平性，那么应该采用队列互斥体（Queuing mutex）。

并非所有共享数据的访问都需要相互排斥。在大多数实际应用中，对并发数据结构的访问通常是读取访问，只有少部分是写入访问。对于这样的数据结构，读取者之间的相互排斥是没有必要的，这样的序列是可以避免的。英特尔 TBB 读/写锁允许许多读取者进入到关键区域，只有写入者线程能够获得一个排斥访问。忙碌等待读/写互斥体的不公平版本为 spin_rw_mutex，其公平版本为queuing_rw_mutex。读/写互斥体提供与 spin_mutex 和 queuing_mutex 相同的 scoped_lock API，此外它还提供特殊函数，允许一个读锁升级至一个写锁，或将一个写锁降级至一个读锁。

建议

成功地选择合适的同步机制的关键是了解您的应用，其中包括正在处理的数据和处理的方式。

如果关键区域仅有几个指令，并且无需顾及公平性问题，那么应选择 spin_mutex。如果关键区域空间较小，但需要线程按照抵达顺序访问关键区域，那么应使用 queuing_mutex。

如果大多数并发数据访问为读取访问，并且仅有小部分线程需要写入访问数据，则可以使用读/写锁来帮助避免不必要的序列化，从而提高整体应用性能。

使用准则

当连续调用 Win32 互锁函数时，请注意线程抢占问题。例如，当执行多线程时，下列代码段不会针对局部变量生成相同的值。

- collapse source view plain copy to clipboard print ?

static LONG N = 0;
LONG localVar;
…
InterlockedIncrement (&N);
InterlockedIncrement (&N);
InterlockedExchange (&localVar, N);
static LONG N = 0;
LONG localVar;
…
EnterCriticalSection (&lock);
localVar = (N += 2);
LeaveCriticalSection (&lock);

static LONG N = 0;
LONG localVar;
…
InterlockedIncrement (&N);
InterlockedIncrement (&N);
InterlockedExchange (&localVar, N);
  
static LONG N = 0;
LONG localVar;
…
EnterCriticalSection (&lock);
 localVar = (N += 2);
LeaveCriticalSection (&lock);

例如，若使用互锁函数，那么任意函数调用之间的线程抢占都可能会产生无法预期的后果。关键区域比较安全，因为原子操作（例如更新全球变量 N 并分配到局部变量）可得到保护。

为了确保安全，无论是采用 CRITICAL_SECTION 变量还是 mutex HANDLE 构建的 Win32 关键区域仅有一个进出点。进入关键区将使同步化失效。跳出一个关键区域而不调用 LeaveCriticalSection 或 ReleaseMutex 将使等待线程变为死锁。单一进出点同样产生清晰代码。

防止线程在终止时持有 CRITICAL_SECTION 变量的情况发生，因为这种情况将会导致等待线程变为死锁。

其它资源

-----------------------------华丽分割线-----------------------------

尽量使用非阻塞锁

提交新文章

Published On :
2010年01月25日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

通过执行由辅助线程实施提供的同步基元，线程可在共享资源上实现同步。这些基元例如互斥体 (mutex) 和信号量 (semaphore) 等只允许单条线程持有锁，其它线程则依据自身的超时机制自旋或阻塞。阻塞线程将导致成本昂贵的环境切换操作，而旋转等待则会浪费 CPU 执行资源（除非等待时间非常短）。另一方面，非阻塞系统调用则允许未成功获得锁的竞争线程原路返回，继续执行有意义的工作，进而避免浪费执行资源。

本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

大多数线程实施，包括 Windows* 和 POSIX* 线程 API，均可提供阻塞和非阻塞两种线程同步基元。默认情况下通常使用阻塞基元。成功争得锁之后，线程便获得锁的控制权，进入关键代码段执行代码。但是，如果没有争得锁，系统便会执行环境切换，线程将被置于等待队列中。环境切换的成本非常高，需尽量避免，具体原因如下：

环境切换开销特别高，基于内核线程的线程实施尤为如此。
应用中跟随同步调用之后的有用工作必须等线程获得锁后才能够执行。

使用非阻塞系统调用有助减少性能损失。在这种情况下，应用线程如果没能成功锁定关键代码段，便会继续执行代码。这不但可以消除环境切换开销，同时也可避免线程在等待获得锁定权的过程中自旋。事实上，线程在重新尝试争夺锁定权之前会一直执行有用工作。

建议

使用非阻塞线程调用来避免生成环境切换开销。非阻塞同步调用通常以关键字 try 开始。例如，Windows 线程实施提供的阻塞和非阻塞版本关键代码段同步基元如下所示：

如果线程在争夺锁的过程中成功获得关键代码段的所有权，TryEnterCriticalSection 调用将返回“True”Boolean 值。否则，它将返回“False”，线程便可以继续执行应用代码。

void EnterCriticalSection (LPCRITICAL_SECTION cs);
bool TryEnterCriticalSection (LPCRITICAL_SECTION cs);

非阻塞系统调用的典型使用示例如下：

- collapse source view plain copy to clipboard print ?

CRITICAL_SECTION cs;
void threadfoo()
{
while(TryEnterCriticalSection(&cs) == FALSE)
{
// some useful work
}
// Critical Section of Code
LeaveCriticalSection (&cs);
}
// other work
}

CRITICAL_SECTION cs;
void threadfoo()
{
  while(TryEnterCriticalSection(&cs) == FALSE)
  {
  // some useful work
  }
    // Critical Section of Code
    LeaveCriticalSection (&cs);
  }
  // other work
}

同样地，POSIX 线程提供非阻塞版本的互斥体 (mutex)、信号量 (semaphore) 和条件变量同步基元。阻塞和非阻塞版本的互斥体同步基元如下所示：

int pthread_mutex_lock (pthread_mutex_t *mutex);
int pthread_mutex_try_lock (pthread_mutex_t *mutex);

在 Windows* 线程实施中，还可以为线程锁定基元设定超时时间。Win32* API 提供了 WaitForSingleObject 和 WaitForMultipleObjects 系统调用，用于在内核对象上实现同步。执行这些调用的线程将一直等待直至相应的内核对象可用，或者用户指定的时间间隔已过。一旦超时间隔已过，线程便可继续执行有用工作。 DWORD WaitForSingleObject (HANDLE hHandle, DWORD dwMilliseconds);

在上面的代码中，hHandle 是内核对象的句柄 (handle)；dwMilliseconds 是超时间隔，如果该间隔过后内核对象仍不可用函数便会自动返回。“INFINITE”值表示线程将无限期地等待下去。下方列出了使用该 API 调用的代码片断。

- collapse source view plain copy to clipboard print ?

void threadfoo ()
{
DWORD ret_value;
HANDLE hHandle;
// Some work
ret_value = WaitForSingleObject (hHandle,0);
if (ret_value == WAIT_TIME_OUT)
{
// Thread could not gain ownership of the kernel
// object within the time interval;
// Some useful work
}
else if (ret_value == WAIT_OBJECT_0)
{
// Critical Section of Code
}
else { // Handle Wait Failure}
// Some work
}

void threadfoo ()
{
  DWORD ret_value;
  HANDLE hHandle;
    // Some work
  ret_value = WaitForSingleObject (hHandle,0);

  if (ret_value == WAIT_TIME_OUT)
{ 
    // Thread could not gain ownership of the kernel 
    // object within the time interval;
// Some useful work
    }
    else if (ret_value == WAIT_OBJECT_0)
{
    // Critical Section of Code
    }
    else { // Handle Wait Failure}
    // Some work
}

同样地，WaitForMultipleObjects API 调用允许线程等待多个内核对象进入可用状态。

使用非阻塞系统调用如 TryEnterCriticalSection 时，在释放共享对象前应查看同步调用的返回值，确保请求已得到满足。

使用指南

英特尔® 软件网络并行编程社区

Aaron Cohen 和 Mike Woodring，《Win32 多线程编程》(Win32 Multithreaded Programming)，O'Reilly Media；第 1 版，1997 年

Jim Beveridge 和 Robert Wiener，《Win32 中的多线程应用——完整的线程指南》(Multithreading Applications in Win32 – the Complete Guide to Threads)，Addison-Wesley Professional，1996 年

Bil Lewis 和 Daniel J Berg，《使用 Pthreads 进行多线程编程》(Multithreaded Programming with Pthreads)，Prentice Hall PTR，第 136 版，1997 年

-----------------------------华丽分割线-----------------------------

第三章、内存管理

线程为内存管理开辟了另外一个不容忽视的新空间。本章节将涵盖对于多线程应用至关重要的内存问题。

-----------------------------华丽分割线-----------------------------

避免线程之间发生堆冲突

提交新文章

Published On :
2010年02月17日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

由于系统运行时库使用锁定的方式同步对堆的访问，因此从系统堆分配内存的操作成本非常高。对于锁的争用限制了多线程的性能优势要解决这个问题，可采用一个避免使用共享锁的分配战略，或使用第三方堆管理器。

本文是《英特尔® 多线程应用开发指南》系列的一部分，后者用于指导开发人员针对英特尔® 平台开发高效的多线程应用。

背景

系统堆（为 malloc 所用）是一种共享资源。为了确保多线程可以安全使用系统堆，必须添加同步机制以管理对共享堆的访问。实现同步（在本例中获得锁）需要与操作系统进行两次交互（即，锁定和解锁），这会带来大笔开销。所有内存分配的串行化问题更大，因为线程需要花费大量时间等待锁，而不是执行有用的工作。

在图1 和图 2 中显示的 Intel Parallel Amplifier 截屏说明了多线程 CAD 应用中的堆争用问题。

图1. 堆分配例程和其所调用的内核函数是主要的性能瓶颈，消耗了大部分应用执行时间。

图 2. 堆分配例程中的关键部分是争夺最激烈的同步对象，导致大量等待时间和较低的利用率。

建议

英特尔编译器中的 OpenMP* 实施导出两个函数：kmp_malloc 和 kmp_free。这两个函数确保为OpenMP所用的每个线程分配一个线程堆，避免使用保护标准系统堆访问的锁。

Win32* API 函数 HeapCreate 可用于为应用使用的所有线程分配独立的堆。HEAP_NO_SERIALIZE 标志用于禁止在该新堆上使用同步，因为只有单条线程可以访问它。堆句柄可存储在线程本地存储(TLS)位置，以便在应用线程需要分配或释放内存时随时使用该堆。注意，以这种方式分配的内存必须由执行分配的同一线程明确释放。

下面的示例演示了如何使用上面提到的 Win32 API 特性来避免堆争用。例子中，新线程创建伊始便使用动态加载库(.DLL)加以注册，并为每条线程请求独立管理的非同步堆，然后使用 TLS 来记录分配给线程的堆。

- collapse source view plain copy to clipboard print ?

#include <windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h>
static DWORD tls_key;
__declspec(dllexport) void *
thr_malloc( size_t n )
{
return HeapAlloc( TlsGetValue( tls_key ), 0, n );
}
__declspec(dllexport) void
thr_free( void *ptr )
{
HeapFree( TlsGetValue( tls_key ), 0, ptr );
}
// 此例使用了WIN32编程API的多项特性
// 它使用了一个.DLL 模块来实现待记录线程的创建和销毁
BOOL WINAPI DllMain(
HINSTANCE hinstDLL, // 交给DLL 模块
DWORD fdwReason, //函数调用原因
LPVOID lpReserved ) // 预定
{
switch( fdwReason ) {
case DLL_PROCESS_ATTACH:
// 使用线程本地存储来记忆堆
tls_key = TlsAlloc();
TlsSetValue( tls_key, GetProcessHeap() );
break;
case DLL_THREAD_ATTACH:
//使用 HEAP_NO_SERIALIZE 来避免锁开销
TlsSetValue( tls_key, HeapCreate( HEAP_NO_SERIALIZE, 0, 0 ) );
break;
case DLL_THREAD_DETACH:
HeapDestroy( TlsGetValue( tls_key ) );
break;
case DLL_PROCESS_DETACH:
TlsFree( tls_key );
break;
}
return TRUE; // 成功的 DLL_PROCESS_ATTACH
}
<windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h><windows.h></windows.h>

#include 

static DWORD tls_key;

__declspec(dllexport) void *
thr_malloc( size_t n )
{
  return HeapAlloc( TlsGetValue( tls_key ), 0, n );
}

__declspec(dllexport) void 
thr_free( void *ptr )
{
  HeapFree( TlsGetValue( tls_key ), 0, ptr );
}

// 此例使用了WIN32编程API的多项特性
// 它使用了一个.DLL  模块来实现待记录线程的创建和销毁

BOOL WINAPI DllMain(
  HINSTANCE hinstDLL, // 交给DLL 模块
  DWORD fdwReason, //函数调用原因
  LPVOID lpReserved ) // 预定
{
  switch( fdwReason ) { 
    case DLL_PROCESS_ATTACH:
    // 使用线程本地存储来记忆堆
    tls_key = TlsAlloc();
    TlsSetValue( tls_key, GetProcessHeap() );
      break;

    case DLL_THREAD_ATTACH:
      //使用 HEAP_NO_SERIALIZE 来避免锁开销
    TlsSetValue( tls_key, HeapCreate( HEAP_NO_SERIALIZE, 0, 0 ) );
      break;

  case DLL_THREAD_DETACH:
    HeapDestroy( TlsGetValue( tls_key ) );
      break;

  case DLL_PROCESS_DETACH:
    TlsFree( tls_key );
      break;
  }
  return TRUE; //  成功的  DLL_PROCESS_ATTACH
}

在使用POSIX* 线程(Pthreads*)的应用中，可通过thread_key_create 和 pthread_{get|set}特定 API 获取 TLS 的访问权，但是并无通用API可供创建独立堆。虽然可以为每个线程分配大块内存，并将其地址存储在 TLS 中，但是管理这部分存储还是编程人员的责任。

除了使用多个独立堆，还可以结合其它技术最大限度地减少因共享锁（用于保护系统堆）引起的锁争用。如果仅在小语境中访问内存，那么有时候可使用 alloca 例程从当前堆栈帧分配内存。当函数返回后，该内存自动释放

- collapse source view plain copy to clipboard print ?

// 有时可用alloca() 取代 malloc()
{
…
char *p = malloc( 256 );
// 使用分配的内存
process( p );
free( p );
…
}
// 如果内存在同一例程中分配和释放。
{
…
char *p = alloca( 256 );
// 使用分配的内存
process( p );
…
}

// 有时可用alloca() 取代 malloc() 
{
  …
  char *p = malloc( 256 );

  //  使用分配的内存 
  process( p );

  free( p );
  …
}

// 如果内存在同一例程中分配和释放。

{
  …
  char *p = alloca( 256 );

  // 使用分配的内存
  process( p );
  …
}

注意，微软不赞成使用 _alloca，而是推荐使用安全性更高的 _malloca 例程。该例程可根据请求的内存大小从堆栈或堆进行分配；因此，通过 _malloca 获得的内存应使用 _freea 释放。

按线程释放列表是另一项技巧。最初，使用 malloc 从系统堆中分配内存。当内存要正常释放时，它会被添加到一个按线程链接列表。如果该线程需要重新分配同样大小的内存，它可以立即在该列表中检索存储的分配信息，而不必回到系统堆。

- collapse source view plain copy to clipboard print ?

struct MyObject {
struct MyObject *next;
…
};
// 按线程释放内存列表对象
static __declspec(thread)
struct MyObject *freelist_MyObject = 0;
struct MyObject *
malloc_MyObject( )
{
struct MyObject *p = freelist_MyObject;
if (p == 0)
return malloc( sizeof( struct MyObject ) );
freelist_MyObject = p->next;
return p;
}
void
free_MyObject( struct MyObject *p )
{
p->next = freelist_MyObject;
freelist_MyObject = p;
}

struct MyObject {
  struct MyObject *next;
  …
};

// 按线程释放内存列表对象
static __declspec(thread)
struct MyObject *freelist_MyObject = 0;

struct MyObject *
malloc_MyObject( )
{
  struct MyObject *p = freelist_MyObject;

  if (p == 0)
    return malloc( sizeof( struct MyObject ) );

  freelist_MyObject = p->next;

  return p;
}

void
free_MyObject( struct MyObject *p )
{
  p->next = freelist_MyObject;
  freelist_MyObject = p;
}

如果上述技巧不适用（例如，分配内存的线程不一定就是释放内存的线程）或内存管理仍然存在瓶颈，可以考虑使用第三方技术来替代堆管理器。英特尔 ® 线程构建块(Intel TBB)提供了一个支持多线程的内存管理器，可与支持 Intel TBB 并使用OpenMP的应用以及手动线程化应用配合使用。在本文最后的其它资源部分列举了一些其它第三方堆管理器。

使用准则

使用任何一种优化方法，都存在取舍问题。在本例中是用更低的系统堆争用以换取更高的内存利用率。当每个线程保有其自己的私有堆或对象集时，这些区域对于其它线程来说不可用。这可能导致不同线程之间的内存不平衡，类似于线程执行不同的工作负载时遇到的负载不平衡。内存不平衡可能引起工作集的大小和应用使用的总内存增加。内存使用的增加通常对性能有轻微影响。当内存使用的增加耗尽了所有可用内存时就会发生异常。如果发生这种状况，可能会引起应用中断或 swap（切换）到磁盘。

其它资源

-----------------------------华丽分割线-----------------------------

采用线程本地存储减少同步开销

提交新文章

Published On :
2010年02月28日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

同步化通常是一个昂贵的操作，并且会限制一个多线程程序的性能。使用线程局部数据结构来代替由线程共享的数据结构可在某些情况下减少同步化，使一个程序运行得更快。

本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

当数据结构由一组线程共享，并且至少有一个线程写入其中时，有时需要对线程进行同步化来确保所有线程均始终能看到一致的共享数据。这种情况下，典型的线程同步化访问机制是由一个线程获取锁，读取或写入共享数据结构，然后解锁。

所有形式的锁都有一定的开销以维持锁数据结构，并且采用了可减慢现代处理器速度的原子结构。同步化也会减慢程序运行速度，因为其消除了同步代码中的并行执行，形成了一系列执行瓶颈。因此，当同步化在一个时延敏感的代码段上发生时，代码性能将会受到影响。

如果该程序可被重新写入并使用线程局部存储而非共享数据结构，那么同步化可以从多线程、时延敏感代码段中消除。如果代码的属性能让共享数据访问的实时定序变得不再重要，那么消除同步化是完全可能的。如果在不频繁、非时延敏感代码段间，安全地推迟定序的执行，即使访问定序重要，也可以消除同步化。

思考一下，例如，使用一个变量来统计发生在几个线程上的事件。下面是用 OpenMP* 编写这样一个程序的一种方法：

- collapse source view plain copy to clipboard print ?

int count=0;
#pragma omp parallel shared(count)
{
. . .
if (event_happened) {
#pragma omp atomic
count++;
}
. . .
}

int count=0;
#pragma omp parallel shared(count)
{
  . . .
  if (event_happened) {
#pragma omp atomic
    count++;
}
. . .
}

每次发生事件时，该程序都需要付出代价，因为只有实施同步化才能确保一次只统计一个线程增量。每个事件都会引发同步化。消除同步化可以加快程序运行。其中一种方法是让每个线程在并行区域统计其自身的事件，然后再合计事件数量。下面的编程中使用了该技术：

- collapse source view plain copy to clipboard print ?

int count=0;
int tcount=0;
#pragma omp threadprivate(tcount)
omp_set_dynamic(0);
#pragma omp parallel
{
. . .
if (event_happened) {
tcount++;
}
. . .
}
#pragma omp parallel shared(count)
{
#pragma omp atomic
count += tcount;
}

int count=0;
int tcount=0;
#pragma omp threadprivate(tcount)

omp_set_dynamic(0);

#pragma omp parallel 
{
. . .
  if (event_happened) {
    tcount++;
  }
  . . .
}
#pragma omp parallel shared(count)
{
#pragma omp atomic
  count += tcount;
}

这个编程使用了一个对应每个线程的 tcount 变量，以存储单个线程的事件统计。在第一个并行区域统计完所有局部事件后，随后的一个区域将在这个统计基础上继续统计。该解决方案用事件同步化替换了线程同步化。如果事件数量远高于线程数量，那么性能将会提高。请注意，该编程前提是假设并行区域均执行相同数量的线程。调度 omp_set_dynamic(0) 可防止线程的数量不同于该编程所需的数量。

在编程中时延敏感的部分使用线程局部存储的另一个好处是，如果处理器没有共享一个数据缓存，数据停留在处理器缓存的时间会更长。当几个处理器的数据缓存中存在相同的地址，并且该地址是由它们其中一个写入的，必须禁用所有其他处理器的缓存。这样，当其他处理器访问该地址时，需要重新从内存中获取。然而，线程局部数据只支持局部处理器写入，其他任何处理器都无法写入，因此更有可能留在自身处理器缓存中。

上述代码段展示了借助 OpenMP 指定线程局部数据的方法之一。若使用 Pthreads 来指定线程局部数据，编程者必须创建一个线程局部数据钥匙，然后通过这个钥匙来访问数据。例如：

- collapse source view plain copy to clipboard print ?

#include <pthread.h>
pthread_key_t tsd_key;
<arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary> value;
if( pthread_key_create(&tsd_key, NULL) ) err_abort(status, “Error creating key”);
if( pthread_setspecific( tsd_key, value))
err_abort(status, “Error in pthread_setspecific”);
. . .
value = (<arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary>)pthread_getspecific( tsd_key );
With Windows threads, the operation is very similar. The programmer allocates a TLS index with TlsAlloc, then uses that index to set a thread-local value. For example:
DWORD tls_index;
LPVOID value;
tls_index = TlsAlloc();
if (tls_index == TLS_OUT_OF_INDEXES) err_abort( tls_index, “Error in TlsAlloc”);
status = TlsSetValue( tls_index, value );
if ( status == 0 ) err_abort( status, “Error in TlsSetValue”);
. . .
value = TlsGetValue( tls_index );
<arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><arbitrary></arbitrary><pthread.h></pthread.h></pthread.h>

#include 

pthread_key_t tsd_key;
 value;


if( pthread_key_create(&tsd_key, NULL) ) err_abort(status, “Error creating key”);
if( pthread_setspecific( tsd_key, value)) 
  err_abort(status, “Error in pthread_setspecific”);
. . .
value = ()pthread_getspecific( tsd_key );


With Windows threads, the operation is very similar. The programmer allocates a TLS index with TlsAlloc, then uses that index to set a thread-local value. For example:

DWORD tls_index;
LPVOID value;

tls_index = TlsAlloc();
if (tls_index == TLS_OUT_OF_INDEXES) err_abort( tls_index, “Error in TlsAlloc”);
status = TlsSetValue( tls_index, value );
if ( status == 0 ) err_abort( status, “Error in TlsSetValue”);
  . . .
value = TlsGetValue( tls_index );

使用 OpenMP 时，编程者可以通过在并行程序上的一个私有子句中指定变量来创建线程局部变量。这些变量将会被自动分配在并行区域末尾。此外，还有一种不考虑线程模式的线程局部数据指定方法，即使用一个在给定范围内分配在堆栈上的变量。这样的变量将被分配到范围末尾。

建议

如果同步化在一个代码的时延敏感段内被编码，而且需要对一个同步操作进行实时定序，则可以使用线程局部存储技术。如果操作的实时定序比较重要，并且在时延敏感段可获取足够的信息来进行随后的复制定序，那么此项技术在编码的非时延敏感段仍适用。

思考一下下面的示例，示例中，线程将数据写入共享缓存区：

- collapse source view plain copy to clipboard print ?

int buffer[NENTRIES];
main() {
. . .
#pragma omp parallel
{
. . .
update_log(time, value1, value2);
. . .
}
. . .
}
void update_log(time, value1, value2)
{
#pragma omp critical
{
if (current_ptr + 3 > NENTRIES) { print_buffer_overflow_message(); }
buffer[current_ptr] = time;
buffer[current_ptr+1] = value1;
buffer[current_ptr+2] = value2;
current_ptr += 3;
}
}

int buffer[NENTRIES];

main() {

  . . .

#pragma omp parallel
{
  . . .
  update_log(time, value1, value2);
  . . .
}

  . . . 
}
void update_log(time, value1, value2)
{
  #pragma omp critical
  {
    if (current_ptr + 3 > NENTRIES) { print_buffer_overflow_message(); }

    buffer[current_ptr] = time;
    buffer[current_ptr+1] = value1;
    buffer[current_ptr+2] = value2;
    current_ptr += 3;
  }
}

假设时间是递增值，而且该程序的唯一要求是缓冲区数据可不定期写入一个文件内，并按时间排序。可以使用线程局部缓冲在 update_log 例程中消除同步化。每个线程将分配一个单独的 tpbuffer 和 tpcurrent_ptr 副本。借此可消除 update_log 中的临界区。随后，来自各个线程私有缓冲区的条目将根据时间值在该程序的一个非时延敏感段内合并。

使用指南

请务必仔细权衡使用该技术的利弊。此项技术不能消除同步化需求，它仅能将同步化从代码的一个时延敏感段迁移至该代码的一个非时延敏感段内。

首先，需确定包含同步化的原代码段性能是否因同步化而大幅下降。Intel® Parallel Amplifier 和/或Intel® VTune ™ Performance Analyzer 可用来检测每个代码段的性能问题。
其次，需确定时间操作定序是否对应用至关重要。如果不是，则可以消除同步化，例如事件统计代码中的同步化。如果时间定序非常重要，则需考虑随后能否正确地重新构建定序？
最后，验证同步化被迁移至代码的另一个位置不会在新的地点引发类似的性能问题。其中一种验证方法是观察同步化次数是否会因为该技术的使用而显著减少（例如上述示例中的事件统计）。

其它资源

-----------------------------华丽分割线-----------------------------

检测线程化应用的内存带宽饱和度

提交新文章

Published On :
2010年02月24日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

内存子系统组件在很大程度上影响着应用的性能特征。现在，随着越来越多的线程和进程共享有限的高速缓存容量和内存带宽等资源，线程化应用的可扩展性受到了极大限制。内存密集型线程化应用在运行多个线程时可能会出现内存带宽饱和的问题。在这种情况下，线程化应用将无法像预期一样扩展，性能也可能有所下降。本文介绍了在线程化应用中检测内存带宽饱和度的技巧。

本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

鉴于当前的处理器集成有更多的核心和高速缓存，它们与内存子系统组件相比频率更高，速度更快。每芯片上内核数的不断增加为高速缓存容量和内存带宽带来了巨大的压力。最终，最大限度提高每枚内核对可用高速缓存和内存带宽的利用率成为开发向前扩展应用的根本。如果系统无法足够迅速地将主内存中的数据传输至内核，那么内核在等待数据时便会处于闲置状态。计算过程中的闲置内核是对资源的浪费，将导致总计算执行时间延长，浪费多核心配置的部分优势。

当前基于 Nehalem 架构的英特尔® 处理器从传统的前端总线 (FSB) 解决方案迁移至非统一内存访问/架构 (NUMA) 模型，增加了内核可用的内存带宽大小，减少了上文提到的内存饱和现象。图 1 描述了从 FSB 到 NUMA 的迁移。

图 1. 从 FSB 到 NUMA 的迁移。

任何并行应用达到带宽饱和的明显症状均是停止扩展。换句话说，一个应用的可用内存带宽一旦达到饱和，该应用便无法有效扩展至更多线程或内核。不过，导致多线程应用不再扩展的原因有很多，其中部分性能妨碍因素包括线程开销、同步开销、负载不平衡和不适当的粒度等。英特尔® 线程档案器经过专门设计，可有效识别应用层面的此类性能问题。

以下结果是使用不同数量的线程执行 STREAM 5.6 性能指标评测所得到的数据（只列出了 Triad 得分）。

功能

频率（MB/秒）

平均时间

最短时间

最长时间

1 条线程

Triad:

7821.9511

0.0094

0.0092

0.0129

2 条线程

Triad:

8072.6533

0.0090

0.0089

0.0093

4 条线程

Triad:

7779.6354

0.0096

0.0093

0.0325

从以上结果中不难看出，STREAM 在该特定平台（单插槽英特尔® 酷睿™ 2 四核处理器架构系统）上并未因拥有更多线程而受益。深入剖析可以发现，虽然双线程版本的 Triad 得分有些微提高，但四线程版本的性能比单线程版本还要低。

图 2 列出了英特尔线程档案器对性能指标评测的分析结果。时间轴 (Timeline) 视图表明，所有线程均实现完美平衡，没有同步开销。虽然英特尔线程档案器是一款识别应用层面线程性能问题的强大工具，但它无法检测出线程化应用的内存带宽饱和度。

图 2. 英特尔线程档案器的 STREAM 性能指标评测（使用四条 OpenMP* 线程）时间轴视图。

建议

英特尔® VTune™ 性能分析器和性能调试实用程序 (PTU) 与基于事件的采样功能相结合，可帮助开发人员测量应用带宽的使用情况，并与系统上的最高可用（或理论）带宽进行对比。基于事件的采样功能需要依赖由处理器支持的性能监控单元 (PMU) 来实现。

VTune 分析器和 PTU 可帮助开发人员使用 EBS 功能估算某具体应用的内存带宽使用情况。在英特尔® 酷睿™ 微架构上，CPU_CLK_UNHALTED.CORE 和 BUS_TRANS_MEM.ALL_AGENTS 性能事件可用来估算内存带宽。

CPU_CLK_UNHALTED.CORE 事件可计算内核非停机状态下的内核周期数。内核运行 HLT 指令时将进入停机状态。
BUS_TRANS_MEM.ALL_AGENTS 事件可计算总线上任何代理程序发起的活动数量。如果系统中的各路处理器均连接至不同的总线，那么该数值只代表处理器所在总线上的活动数量。

对于采用英特尔酷睿 2 处理器的系统，可使用以下公式来计算内存带宽：

（64 * BUS_TRANS_MEM.ALL_AGENTS * CPU 频率） / CPU_CLK_UNHALTED.CORE

图 3. VTune 分析器对四线程 STREAM 性能指标评测的 EBS 分析结果。

图 3 列出了使用四条线程进行 STREAM 性能指标评测的 EBS 结果。使用上面的公式，可以估算出 STREAM 内存带宽的使用情况为 7.6Gb/秒。

内存带宽 = (64 * 1,419,200,000 * 2.9GHz) / 35,576,000,000 = 7.6GB/秒

STREAM 报告的可容忍 Triad 得分是 7.7GB/秒，由此可看出基于 VTune 分析器的计算方法很合理。我们选择 STREAM 性能指标评测的目的是展示如何通过使用 EBS 测量的内存带宽大致估算指定系统的可用内存带宽。

如果应用在添加了更多线程时无法进行扩展以充分利用现有内核，并且英特尔线程档案器没有如上所述显示任何应用层面的线程问题，那么以下三步操作可帮助用户判断某具体应用的可用内存带宽是否已达到饱和：

执行 STREAM 或类似的性能指标评测，了解目标系统上的可持续内存带宽。
在 VTune 分析器或 PTU 下运行目标应用，并使用 EBS 功能收集适当的性能计数器。对于英特尔酷睿 2 微架构而言，这些事件是 CPU_CLK_UNHALTED.CORE 和 BUS_TRANS_MEM.ALL_AGENTS（公式 1）。
将 VTune 分析器测量的内存带宽数据与在第 1 步中测量到的可持续和可用内存带宽进行比较。如果应用的可用带宽即将达到饱和，那么该应用不会再扩展至更多内核。

一般来说，受限于内存的应用程序（性能受到内存访问速度的限制）不会因拥有多条线程而受益。

使用指南

英特尔® 酷睿™ i7 处理器和英特尔® 至强® 5500 系列处理器被称为带“非内核”部件。“非内核”是处理器中位于所有其它独立内核外部的组成部分。例如英特尔® 酷睿™ i7 处理器拥有四枚共享一个三级高速缓存和一个内存接口的内核。其中，三级高速缓存和内存接口便视作非内核部分（参见图 4）。

VTune 分析器和 PTU 均不支持由处理器非内核部分触发的事件采样行为，必须使用其它方法测量内存带宽。用于测量内存带宽的相关性能事件并不是像常见 VTune 分析器或 PTU 模式那样使用 EBS 功能进行采样，而是使用基于时间的采样功能进行计算。这测量的是指定时间范围内整个系统的内存带宽，而无法估算具体功能、进程和模块的带宽使用情况。

图 4. 简化的四核 Nehalem 处理器结构图。

上文给出的公式可用来测量英特尔酷睿 2 架构系统上任何应用、模块或函数的内存带宽使用情况，但同样具备非内核部件的基于酷睿 2 的英特尔至强多路处理器除外。在 Nehalem 架构系统上测量内存带宽的基本公式如下：

内存带宽 = 1.0e-9 * (UNC_IMC_NORMAL_READS.ANY+UNC_IMC_WRITES.FULL.ANY)*64 / （挂钟时间，以秒计）

更多资源

-----------------------------华丽分割线-----------------------------

避免并识别线程间伪共享

提交新文章

Published On :
2010年02月18日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

在对称多处理器系统中，每个处理器均有一个本地高速缓存。内存系统必须保证高速缓存的一致性。当不同处理器上的线程修改驻留在同一高速缓存行中的变量时就会发生共享错误，结果导致高速缓存行无效，并强制执行更新，进而影响系统性能。本文介绍了检测和更正错误共享的方法。

本文是《英特尔® 多线程应用开发指南》系列的一部分，后者用于指导开发人员针对英特尔®平台开发高效的多线程应用。

背景

错误共享是 SMP 系统上的一种常见性能问题。在SMP系统中，每个处理器均有一个高速缓存。如果图1所示，当不同处理器上的线程修改驻留在同一高速缓存行中的变量时就会发生这种问题，之所以被称为错误共享，是因为每个线程并非真正共享相同变量的访问权。访问同一变量或真正共享要求编程式同步结构，以确保有序的数据访问。

在下面的代码示例中以红色显示的源代码行引起错误共享：

- collapse source view plain copy to clipboard print ?

double sum=0.0, sum_local[NUM_THREADS];
#pragma omp parallel num_threads(NUM_THREADS)
{
int me = omp_get_thread_num();
sum_local[me] = 0.0;
#pragma omp for
for (i = 0; i < N; i++)
sum_local[me] += x[i] * y[i];
#pragma omp atomic
sum += sum_local[me];
}

double sum=0.0, sum_local[NUM_THREADS];
#pragma omp parallel num_threads(NUM_THREADS)
{
  int me = omp_get_thread_num();
  sum_local[me] = 0.0;

  #pragma omp for
  for (i = 0; i < N; i++)
    sum_local[me] += x[i] * y[i];

  #pragma omp atomic
  sum += sum_local[me];
}

数组sum_local存在潜在的错误共享。该数组的大小取决于线程数，并且足够小，可写入单个高速缓存行。在并行执行时，这些线程会修改不同、但相邻的 sum_local 元素（源代码行以红色显示），结果使所有处理器的高速缓存行无效。

图1. 当不同处理器上的线程修改驻留在同一高速缓存行中的变量时就会发生共享错误，从而导致高速缓存行无效，并强制内存更新以维持高速缓存的一致性。

在图1中，线程 0 和线程 1 会用到不同变量，它们在内存中彼此相邻，并驻留在同一高速缓存行。高速缓存行被加载到 CPU 0 和 CPU 1 的高速缓存中（灰色箭头）。尽管这些线程修改的是不同变量（红色和蓝色箭头），高速缓存行仍会无效，并强制内存更新以维持高速缓存的一致性。

要确保多个高速缓存中的数据一致性，支持多处理器的英特尔®处理器遵循MESI (Modified/Exclusive/Shared/Invalid，修改/独占/共享/无效)协议。首次加载高速缓存行时，处理器将该高速缓存行标记为独占访问一旦该高速缓存行被标记为独占，后续加载可以自由使用缓存中的现有数据。如果该处理器看到相同的高速缓存行被其它处理器加载到总线上，就会将该高速缓存行标记为“共享”访问。如果处理器存储一个标记为“S（共享）”的高速缓存行，该缓存行被标记为敁已修改，所有其它处理器会收到一条敁无效的缓存行信息。”如果处理器看到标记为 “M（已修改）”相同的高速缓存被其它处理器访问，该处理器将该高速缓存行存回内存，并将其标记为“S”。访问相同高速缓存行的其它处理器发生高速缓存丢失。

当高速缓存行被标记为“无效”时，处理器之间的频繁协调要求将高速缓存行写入内存，然后再加载。错误共享增加了这种协调工作，因此会显著降低应用性能。

由于编译器可以感知错误共享，所以在消除可能发生的错误共享方面大有可为。例如，当使用优化选项编译上述代码时，编译器会利用线程专有临时变量消除错误共享。上述代码中的运行时错误共享只有在编译代码时禁用了优化选项才会成为问题。

建议

避免错误共享的主要方式是进行代码检查。可能的错误共享主要出现在线程访问全局或动态分配共享数据结构的例程中。注意，在线程访问内存中碰巧相近的几个完全不同的全局变量时，也会出现假的错误共享。线程本地存储或本地变量不会导致错误共享。

运行时检测方法是使用 Intel VTune Performance Analyzer 或 Intel_ Performance Tuning Utility（Intel PTU，请见http://software.intel.com/en-us/articles/intel-performance-tun= ing-utility/）。此方法通过基于事件取样（可发现哪些位置存在高速缓存行共享）来揭示性能影响。但是，这种影响不区分真正共享与错误共享。

针对基于英特尔 ® 酷睿™ 2处理器的系统，配置 VTune 分析器或 Intel PTU 以取样 MEM_LOAD_RETIRED.L2_LINE_MISS 和 EXT_SNOOP.ALL_AGENTS.HITM 事件。针对基于英特尔 ® 酷睿™ i7 处理器的系统，配置取样 MEM_UNCORE_RETIRED.OTHER_CORE_L2_HITM 事件。在英特尔 ® 酷睿™ 2处理器系列CPU上，如果您在某些代码区域看到 EXT_SNOOP.ALL_AGENTS.HITM 事件频繁发生，多少与INST_RETIRED.ANY 事件成一定比例，或者在英特尔 ® 酷睿™ i7 处理器系列CPU上，如果您看到MEM_UNCORE_RETIRED.OTHER_CORE_L2_HITM事件频繁发生，那么您就遇到了或真或假的共享了。检查对应系统中位于或接近加载/存储指令处MEM_LOAD_RETIRED.L2_LINE_MISS 和 MEM_UNCORE_RETIRED.OTHER_CORE_L2_HITM 事件集中区段的代码，以确定内存地址驻留在相同高速缓存行并引起错误共享的可能性。

Intel PTU 自带预定义的配置文件，用于收集有助于定位错误共享的事件。这些配置文件包括“英特尔_® 酷睿™ 2处理器系列竞争性使用”和“英特尔 ® 酷睿™ 处理器系列错误和真正共享”。Intel PTU 数据访问分析通过监控被不同线程访问的同一高速缓存行的不同偏移量来识别可能的错误共享。当您在数据访问窗口（Data Access View）中打开分析结果时，如图2 所示，内存热点（Memory Hotspot）面板将按照高速缓存行的粒度给出有关错误共享的提示。

图2.Intel PTU Memory Hotspots 面板中显示的错误共享。

在图2 中，（位于地址 0x00498180 的高速缓存行的）内存偏移量 32 和 48 在工作函数中被 ID=3D59 线程和 ID=3D62 线程访问。由于 ID=3D59 线程执行数组初始化，其中也存在部分真正共享。

粉色用于提示高速缓存行中的错误共享。请注意与高速缓存行及其对应的偏移量相关的 MEM_UNCORE_RETIRED.OTHER_CORE_L2_HITM 的较高数值。

一旦检测到错误共享，可通过几项技术予以更正。目的是确保引起错误共享的变量在内存中存放的位置相隔足够远，从而不会驻留在同一个高速缓存行中。下面介绍了三种可能方法（并非全部）。
一种技术是使用编译指令强制对齐单个变量。下面的源代码演示了这种方法，即使用 __declspec (align(n))，其中 n=64（64字节边界），来按高速缓存行边界对齐单个变量。

__declspec (align(64)) int thread1_global_variable;
__declspec (align(64)) int thread2_global_variable;

在使用数据结构数组时，将该结构填充到高速缓存行末尾，以确保该数组元素始于高速缓存行边界。如果不能确保该数组对齐于高速缓存行边界，可填充该数据结构至高速缓存行的两倍大小。下面的源代码演示了如何填充数据结构到高速缓存行边界，并使用 compiler __declspec (align(n)) 语句确保数组对齐，其中 n= 64（64字节边界）。如果该数组是动态分配的，可以增加分配大小，并调整指针以便与高速缓存行边界对齐。

- collapse source view plain copy to clipboard print ?

struct ThreadParams
{
//对于以下4 个变量：4*4 = 16 字节
unsigned long thread_id;
unsigned long v; //频繁读/写访问变量
unsigned long start;
unsigned long end;
//扩展到64 字节以避免错误共享
//(4 个无符号的长变量+ 12 个填充值)*4 = 64
int padding[12];
};
__declspec (align(64)) struct ThreadParams Array[10];

struct ThreadParams
{
  //对于以下4 个变量：4*4 = 16 字节
  unsigned long thread_id;
  unsigned long v; //频繁读/写访问变量
  unsigned long start;
  unsigned long end;

  //扩展到64 字节以避免错误共享
  //(4 个无符号的长变量+ 12 个填充值)*4 = 64
  int padding[12];
};

__declspec (align(64)) struct ThreadParams Array[10];

使用数据的线程本地拷贝也可以减少发生错误共享的频率。线程本地拷贝可频繁读取并修改，只需在完成这些操作后再将结果拷贝回数据结构即可。下面的源代码演示了如何使用本地拷贝避免错误共享。

- collapse source view plain copy to clipboard print ?

struct ThreadParams
{
//对于以下4 个变量：4*4 = 16 字节
unsigned long thread_id;
unsigned long v; //频繁读/写访问变量
unsigned long start;
unsigned long end;
};
void threadFunc(void *parameter)
{
ThreadParams *p = (ThreadParams*) parameter;
//读/写访问变量的本地拷贝
unsigned long local_v = p->v;
for(local_v = p->start; local_v < p->end; local_v++)
{
//函数计算
}
p->v = local_v; //只需更新一次共享数据结构
}

struct ThreadParams
{
  //对于以下4 个变量：4*4 = 16 字节
  unsigned long thread_id;
  unsigned long v; //频繁读/写访问变量
  unsigned long start;
  unsigned long end;
};

void threadFunc(void *parameter) 
{
  ThreadParams *p = (ThreadParams*) parameter;
  //读/写访问变量的本地拷贝
  unsigned long local_v = p->v;

  for(local_v = p->start; local_v < p->end; local_v++)
  {
    //函数计算
  }

  p->v = local_v;  //只需更新一次共享数据结构
}

使用准则

避免错误共享，但是要谨慎使用这些技术。过度使用会影响处理器可用高速缓存的有效使用。即便对于多处理器共享高速缓存设计，仍然建议避免错误共享。尝试最大限度提高多处理器共享高速缓存设计中的高速缓存利用率可能会带来一些好处，但一般不会超过支持不同高速缓存架构的多代码路径所需的软件维护成本。

其它资源

-----------------------------华丽分割线-----------------------------

第四章、编程工具

本章节将说明如何利用英特尔软件产品开发、调试和优化多线程应用。

-----------------------------华丽分割线-----------------------------

借助英特尔® 编译器实现自动并行化

提交新文章

Published On :
2010年01月10日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

通过多线程化应用来提高性能是一件十分耗时的工作。对于多数计算在简单循环内执行的应用来说，英特尔 ® 编译器可以自动生成多线程化的版本。
除了高水平的代码优化，英特尔编译器通过自动并行处理和OpenMP* 功能支持线程化功能。借助自动化并行功能，编译器可检测能够以并行的方式安全、高效地执行的循环，并生成多线程代码。OpenMP 允许编程人员通过编译器指令和 C/C++ 编译指令表达并行性。
本文是《英特尔® 多线程应用开发指南》大型系列的一部分，提供了针对英特尔 ® 平台开发高效的多线程应用的指南。

背景

英特尔 ® C++ 和 Fortran 编译器能够分析循环中的数据流，以确定哪些循环可以并行的方式安全、高效地执行。在多核系统上，自动化并行处理有时可能会导致缩短执行时间。此外，它还可在以下几方面减轻编程人员的负担：

寻找适合并行执行的循环
执行数据流分析以确定正确的并行执行
手动添加并行编译指令。

编程人员唯一要做的就是向编译命令中添加 -Qparallel (Windows*) 或 -parallel (Linux* 或 Mac OS* X) 参数。但是，成功的并行化取决于下一部分介绍的特定条件。
下面的 Fortran 程序包含一个具有较大迭代计数的循环：

- collapse source view plain copy to clipboard print ?

PROGRAM TEST
PARAMETER (N=10000000)
REAL A, C(N)
DO I = 1, N
A = 2 * I - 1
C(I) = SQRT(A)
ENDDO
PRINT*, N, C(1), C(N)
END

PROGRAM TEST
PARAMETER (N=10000000)
REAL A, C(N)
DO I = 1, N
A = 2 * I - 1
C(I) = SQRT(A)
ENDDO
PRINT*, N, C(1), C(N)
END

数据流分析确认该循环不包含数据相关性。编译器生成的代码在运行时尽可能在线程内平均划分迭代。线程数默认为处理器核心的总数（如果支持英特尔®超线程技术，该数值可能大于物理核心的总数），但是可以通过 OMP_NUM_THREADS 环境变量单独设置。面向特定循环的并行加速取决于工作负载数量、线程之间的负载平衡以及线程创建和同步的开销等，但是相对于使用的线程数，通常低于线性加速的数值。对于整个程序，加速取决于并行与串行计算的比率（参考任意针对阿姆达尔定律的并行计算的教科书）。

建议

编译器要实现循环的并行化，必须符合三个条件：首先，在进入一个循环前，必须知道迭代的数量，以便可以提前划分工作负载。例如，通常不能并行执行 while 循环。其次，不能发生跳进或跳出循环的情况。最后，也是最重要的，循环迭代必须是独立的。换句话说，正确的结果不能在逻辑上依赖迭代执行的顺序。但是，在累计舍入误差中可能包含微小变化，例如，当以不同的顺序添加相同的数量。在一些情况下，例如数组或其它临时标量使用的求和，编译器可通过简单的转换去掉明显的相关性。
指针或数组参考的潜在别名是安全并行化的另一个常见障碍。指向同一个内存位置的两个指针将被赋予别名。编译器可能无法确定两个指针或数组参考是否指向同一个内存位置，例如，如果它们依靠函数参数、运行时数据或复杂计算的结果。如果编译器不能证明指针或数组参考的安全性和迭代的独立性，它将不能实现循环并行化，除非认为值得生成备用代码路径，以便在运行时对别名进行明确的测试，但这种情况非常少见。如果编程人员认为某个特定循环的并行化是安全的，并且可能的别名可以忽略，则可以通过 C 编译指令或 (#pragma parallel) Fortran 编译指令 (!DIR$ PARALLEL) 将这种情况通知编译器。在 C 中确定指针没有被赋予别名的另一种方式是在指针声明中使用严格的关键字，同时使用 -Qrestrict (Windows) 或 -restrict (Linux 或 Mac OS* X) 命令行参数。但是，如果循环被证明是不安全的，编译器不会对其进行并行化。
编译器只能有效地分析结构相对简单的循环。例如，它不能确定包含外部函数调用的循环的线程安全性，因为它不知道该函数调用是否造成引入相关性的副作用。Fortran 90 编程人员可以使用 PURE 属性来确定子例程和函数不会造成副作用。在 C 或 Fortran 中的另一种方法是通过 -Qipo (Windows) 或 -ipo (Linux 或 Mac OS X) 编译器参数调用内部程序优化。这种方法使编译器有机会针对副作用内联或分析所调用的函数。
当编译器无法自动并行化编程人员认为可以安全、并行执行的复杂循环时，OpenMP 是首选解决方案。通常，编程人员对代码的理解优于编译器，并能以更大的粒度表达并行性。另一方面，自动并行化针对嵌套循环可能非常有效，例如矩阵相乘中的嵌套循环。粒度大小适中的并行性源于外部循环的线程化，可以使用向量化或软件流水线优化内部循环以获得精细粒度并行性。
可以并行化的循环不代表一定要实现并行化。编译器使用带有阈值参数的成本模型来确定是否应对循环进行并行化。-Qpar-threshold[n] (Windows) 和 -par-threshold[n] (Linux) 编译器蚕食可调整该参数。n 值的范围是 0-100，0 表示始终并行化安全的循环，而不考虑成本模型；100 表示编译器只并行化那些很可能获得高性能的循环。缺省的 n 值被保守地设置为 100；有时候，阈值降到 99 可能会显著增加并行循环的数量。编译指令 #parallel always（在 Fortran 中是 !DIR$ PARALLEL ALWAYS) 可以用于忽略单个循环的成本模型。
开关 -Qpar-report[n] (Windows) 或 -par-report[n] (Linux)，其中 n 为 1-3，显示哪些循环得到并行化。查找信息，例如：

- collapse source view plain copy to clipboard print ?

test.f90(6) : (col. 0) remark: LOOP WAS AUTO-PARALLELIZED

test.f90(6) : (col. 0) remark: LOOP WAS AUTO-PARALLELIZED

如下例所示，编译器还可以报告哪些循环不能并行化以及相应的原因。

- collapse source view plain copy to clipboard print ?

serial loop: line 6
flow data dependence from line 7 to line 8, due to "c"

serial loop: line 6
flow data dependence from line 7 to line 8, due to "c"

下面的例子对此进行了阐述：

- collapse source view plain copy to clipboard print ?

void add (int k, float *a, float *b)
{
for (int i = 1; i < 10000; i++)
a[i] = a[i+k] + b[i];
}

void add (int k, float *a, float *b)
{
for (int i = 1; i < 10000; i++)
a[i] = a[i+k] + b[i];
}

编译命令 'icl -c -Qparallel -Qpar-report3 add.cpp' 可生成下列信息：

- collapse source view plain copy to clipboard print ?

procedure: add
test.c(7): (col. 1) remark: parallel dependence: assumed ANTI dependence between a line 7 and a line 7. flow data dependence assumed
...
test.c(7): (col. 1) remark: parallel dependence: assumed FLOW dependence between a line 7 and b line 7.

procedure: add
test.c(7): (col. 1) remark: parallel dependence: assumed ANTI dependence between a line 7 and a line 7. flow data dependence assumed
...
test.c(7): (col. 1) remark: parallel dependence: assumed FLOW dependence between a line 7 and b line 7.

对于 k 是否等于 -1 的例子，由于编译器不知道 k 的值，因此它必须假设迭代之间相互依赖。不过，由于对应用的了解，编程人员可能知道该值（例如 k 总是大于 10000），并可通过插入下面的编译指令忽略编译器：

- collapse source view plain copy to clipboard print ?

void add (int k, float *a, float *b)
{
#pragma parallel
for (int i = 1; i < 10000; i++)
a[i] = a[i+k] + b[i];
}

void add (int k, float *a, float *b)
{
#pragma parallel
for (int i = 1; i < 10000; i++)
a[i] = a[i+k] + b[i];
}

此信息表明该循环得到并行化。

- collapse source view plain copy to clipboard print ?

procedure: add
test.c(6): (col. 1) remark: LOOP WAS AUTO-PARALLELIZED.

 procedure: add
test.c(6): (col. 1) remark: LOOP WAS AUTO-PARALLELIZED.

但是，编程人员调用此函数时，K 的值必须大于 10000，以避免可能的错误结果。

使用准则

尝试使用 -parallel (Linux or Mac OS X) 或 -Qparallel (Windows) 编译开关构建应用的计算密集型内核。使用-par-report3 (Linux) 或 -Qpar-report3 (Windows) 提供报告，以便找出并行化的循环与不能并行化的循环。对于后者，尝试消除数据相关性和/或帮助编译器消除可能具有别名的内存参考的歧义。通过 -O3 编译可实现额外的高级循环优化（例如循环合并），此操作有时候可实现自动并行化。以 -opt-report-phase hlo 生成的编译器优化报告中对此额外优化进行了报告。始终在具有和没有并行化的情况下测量性能，以确定是否实现了加速。如果 -openmp 和 –parallel 在同一个命令行中指定，编译器将只尝试对不包含 OpenMP 指令的循环进行并行化。对于拥有独立的编译和链接步骤的程序，当使用自动并行化功能时要确保链接到 OpenMP 运行时库。最简单的方法就是使用编译器驱动程序进行连接，例如通过icl -Qparallel (Windows) 或ifort -parallel (Linux 或 Mac OS X)。在 Mac OS X 系统上，您可能需要在 Xcode 中设置环境变量 DYLD_LIBRARY_PATH，以确保在运行时可以找到 OpenMP 动态库。

其它资源

英特尔 ® 软件网络并行编程社区
英特尔® C++ 编译器用户和参考指南或英特尔® Fortran 编译器用户和参考指南中的“优化应用/使用并行性：自动并行化”
在基于奔腾 ® III 和奔腾 ® 4 处理器的系统上高效开发并行功能
Intel ® Parallel Composer中实施并行化的概述

-----------------------------华丽分割线-----------------------------

英特尔® 数学核心函数库并行性

提交新文章

Published On :
2010年01月10日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

软件库可帮助程序员轻松地即刻获得多核、多处理器和集群计算系统的卓越性能优势。英特尔® 数学核心函数库（英特尔® MKL）内含有大量函数，可为数学密集型应用带来巨大优势。本文将着重描述英特尔 MKL 可如何帮助程序员在普通应用领域获得超凡的串行和并行性能。此处信息适用于 Windows*、Linux* 和 Mac OS* X 操作系统上的 IA-32 和英特尔® 64 处理器。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

一般来说，若要在当前的多核和多处理器系统上获得最优性能，需要充分开发和把握并行化机会，以及有效管理架构的基本内存特征。顺序代码要达到最高性能必须在极大程度上依赖指令和寄存器级 SIMD 并行性以及高速缓存分块功能。线程化应用必须通过先进的分块战略来确保多个核心和处理器均能得到充分利用，并行任务也得到均匀分配。在部分实例中，还可以使用核外实施来处理无法在内存中解决的大型问题。

建议

在数学密集型应用中添加并行性的一种最轻松的方法便是使用经优化的线程化函数库。这样不但能够节省程序员大量的开发时间，还可减少必要的测试与评估行为。另外，标准化的 API 还能帮助增加最终代码的可移植性。
英特尔 MKL 提供有一系列完整的数学函数，这些函数经过优化和线程化，可充分利用最新英特尔® 处理器的全部特性。第一次从库中调用函数时，MKL 将执行运行时检查，确定程序正在什么硬件上运行。根据该检查结果，MKL 会选择一条合适的代码路径，最大限度发挥指令和寄存器级 SIMD 并行性的优势，同时选择最出色的高速缓存分块战略。英特尔 MKL 在设计时还集成了线程安全性 (threadsafe)，这意味着当同时从多条应用线程调用库中的函数时，这些函数能够保持正常运行。
英特尔 MKL 基于英特尔® C++ 和 Fortran 编译器构建而成，并使用 OpenMP* 实现了线程化。该函数库的算法能够平均分配数据和任务，充分利用多个核心和处理器。下表列出了包含线程化应用的数学域（该信息基于英特尔 MKL 10.2 Update 3）：

线性代数
用于包括有限元素分析工程设计代码和现代动画在内的各种应用。

BLAS（基本线性代数子程序）
所有矩阵间运算（三级）均面向密集和稀疏 BLAS 实现了线程化。许多矢量间运算（一级）和矩阵与矢量的运算（二级）均面向英特尔® 64 架构上 64 位程序中的密集型矩阵实现了线程化。对于稀疏矩阵，除三角形稀疏矩阵解算器外的所有二级运算均实现了线程化。

LAPACK（线性代数程序包）
部分计算例程针对以下某类型的问题实现了线程化：线性方程解算器、正交因子分解、单值分解和对称特征值问题。LAPACK 也调用 BLAS，因此即使是非线程化函数也可能并行运行。

ScaLAPACK（可扩展 LAPACK）
面向集群的 LAPACK 分布式内存并行版本。

PARDISO
该并行直接稀疏矩阵解算器的三个阶段均实现了线程化：重新排序（可选）、因子分解和解算（如果采用多个右侧项）。

快速傅立叶转换
用于信号处理和石油开采及医疗成像等。

线程化FFT（快速傅立叶转换）
除 1 维实数和分裂复数 FFT 外均实现了线程化。

集群 FFT
适用于集群的分布式内存并行 FFT。

矢量数学
在多种财务代码中使用。

VML（矢量数学库）
算数、三角函数、指数/对数函数、约数等。

由于线程的创建和管理流程涉及一定的开销，因此使用多条线程并非总是物有所值的。考虑到这一点，英特尔 MKL 不会针对小问题创建线程。问题的大小是相对域和函数而言的。对于三级 BLAS 函数，可能小至 20 的维数也会经过线程化处理，而在一级 BLAS 和 VML 函数中，小于 1000 的矢量都不会分配到线程。
当从应用的线程化区域进行调用时，英特尔 MKL 应在单条线程上运行，以免过渡占用系统资源。对于使用 OpenMP 实现了线程化的应用而言，该流程可自动完成。如果使用其它方法对应用进行线程化处理，则应通过下文描述的控件设置英特尔 MKL 的行为。如果需要通过多条线程依次使用该函数库，英特尔 MKL 的部分功能可以起到关键作用。例如，矢量统计库 (VSL) 提供了一系列矢量化的随机数生成器，这些生成器虽然没有经过线程化，但却可以帮助在应用线程间划分随机数流。SkipAheadStream() 函数可将随机数流划分为多个独立的块，每条线程一个。LeapFrogStream() 函数对随机数流进行划分后可确保每条线程均获得原始流的一个子序列。例如，在两条线程之间划分流时，Leapfrog 方法会将带奇指数的数字分配给一条线程，然后将带偶指数的数字分配给另一条线程。

性能

图 1 举例说明了用户使用英特尔 MKL 中的双精度一般矩阵乘法函数 DGEMM 可实现的性能级别。该 BLAS 函数在提升许多应用的性能方面均发挥着重要作用。下图列出了 DGEMM 处理不同大小三角形矩阵的性能（以 Gflops 计），同时展示了性能如何在多个处理器之间扩展（处理两条线程的速度提高了 1.9 倍，处理四条线程的速度提高了 3.8 倍，处理八条线程的速度则提高了 7.9 倍），最终达到峰值性能的 94.3%，即 96.5 Gflops。

图 1. BLAS 矩阵乘法函数的性能与可扩展性。

使用指南

鉴于英特尔 MKL 是通过 OpenMP 实现的线程化，它的行为可能会受到 OpenMP 控件的影响。对于新增的线程化行为控制，英特尔 MKL 可提供多个服务函数来反映相关的 OpenMP 控件。这些函数支持用户控制函数库使用的线程数量，既可对整个库进行控制，也可以域为单位进行控制（即单独控制 BLAS、LAPACK 等）。这些独立控件的一项重要应用便是部署嵌套式并行处理。例如，程序员可使用 OMP_NUM_THREADS 环境变量或 omp_set_num_threads() 函数来设置使用 OpenMP 实现线程化的应用的行为，使用专门面向英特尔 MKL 的控件单独设置英特尔 MKL 的线程化行为。该控件可以是MKL_NUM_THREADS 或 mkl_set_num_threads()，视具体情况而定。最后，对于必须在单条线程上运行英特尔 MKL 函数的应用，系统将提供一个对线程运行时无任何依赖关系的顺序库。
当每条线程分别执行不同类型的运算且处理器上存在未充分利用的资源时，英特尔® 超线程技术将发挥最大的作用。然而，英特尔 MKL 完全不符合这两项标准，因为该函数库的线程化部分高效运行，占用了大部分可用资源，并且每条线程上所执行的运算完全相同。鉴于此，英特尔 MKL 在默认情况下只使用与物理内核数一样多的线程。

线程化与英特尔® IPP 高效多媒体函数库

提交新文章

Published On :
2010年01月11日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

现在并不存在适用于所有应用的通用线程化解决方案。同样，内建英特尔® IPP 高效多媒体函数库（英特尔® IPP）的应用可以通过许多方式充分发挥多条执行线程的优势。线程化可以在低级基元（位于英特尔® IPP 高效多媒体函数库内）层面或更高的操作系统层面上予以实施。本章将说明采用英特尔® IPP 的应用可以通过哪些方式安全、成功地发挥多条执行线程的优势。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

英特尔® IPP 是一个针对数字媒体和数据处理应用进行高度优化的函数库。该函数库由针对各类域（包括信号处理、图像、音频和视频编解码、数据压缩、字符串处理和加密在内）中常用的基本算法进行优化的函数组成，它可充分利用各类 SIMD（单指令多数据）和 SSE（SIMD 流指令扩展）指令集以及新型英特尔® 处理器上的多条硬件执行线程。当前处理器上使用的许多 SSE 指令根据 DSP（数字信号处理器）上的指令复制而来，它们十分适用于优化运行于阵列和数据向量的算法。
英特尔® IPP 适用于专为 Windows*、Linux*、Mac OS* X、QNX* 和 VxWorks* 操作系统而构建的应用。它能与英特尔® C 和 Fortran 编译器、Microsoft Visual Studio* C/C++ 编译器和 gcc 编译器（包括大多数 Linux 发行版）兼容。该函数库已通过多代英特尔® 处理器（包括英特尔® 酷睿™ 处理器和英特尔® 凌动™ 处理器）和兼容的 AMD 处理器的应用验证。它同时支持 32 位和 64 位操作系统与架构。

简介

英特尔® IPP 经过精心设计，可支持各种多线程方法。该函数库采用了线程安全设计，即一项应用支持多条线程调用此库内函数。此外，不同版本的英特尔® IPP 还具备多线程性能，能够经由英特尔® OpenMP* 库直接提升您的应用性能，无需您朝着多线程应用的方向重新编写应用。
英特尔® IPP 基元（构成英特尔® IPP 基础的低级函数）是一套算法元素集，它们经过设计，可在数据向量和阵列上重复运行（多线程应用的理想实施状态）。这些基元独立于提供支持的操作系统；它们无需利用锁、信号量或全局变量，只需依靠面向临时和固定内存存储的标准 C 库内存分配例程（malloc/realloc/calloc/free）即可。为进一步减少与外部系统函数的关联，您可以通过 i_malloc 界面使用您自己的内存分配例程代替标准 C 例程。
除了低级算法基元外，英特尔® IPP 还包括一系列行业标准高级应用和图像、媒体与语音编解码器（编码器和解码器）部署工具、数据压缩库、字符串处理函数以及加密工具。这些高级工具大部分需要借助多条线程向两条以上的硬件线程分配工作任务。
即使在单线程应用内，英特尔® IPP 也能通过一套专为满足计算密集型算法要求而设计的函数集支持用户轻松访问 SIMD 指令（MMX、SSE 等），显著提升应用性能。
图 1 所示为针对各类英特尔® IPP 产品域测量的相对平均性能提升值（与在无 MMX/SSE 指令支持下部署的等价函数相比）。您所获得的实际性能提升可能会有所差异。

图 1： 针对各类英特尔® IPP 产品域测量的相对性能提升值。
系统配置：英特尔® 至强® 四核处理器，配备 2.8 GHz 主频、2GB 内存，采用 Windows* XP 操作系统和英特尔® IPP 6.0 函数库。

建议

通过英特尔® IPP 发挥多条硬件线程优势的最简单、快速的方法是采用该函数库的多线程版本或集成该函数库提供的众多线程化示例应用中的一项应用。这样做不仅可避免执行大量的代码重编工作，还能在采用英特尔® IPP 所带来的性能提升优势基础上进一步提高性能。
英特尔® IPP 拥有三个基本版本（截至 6.1 版）：单线程静态函数库、多线程静态函数库和多线程动态函数库。这三个版本的函数库均采用了线程安全设计。单线程静态函数库适用于处于内核模式的应用或不兼容、不支持 OpenMP 库的应用（在实时操作系统下可能存在这种情况）。
两种线程选择：OpenMP 线程与英特尔® IPP
英特尔® IPP 所包含的低级基元均为基本原子操作，它们限制了约 15% 的库函数可以利用的并行操作数量。英特尔® OpenMP 库一直以来都被用于实施“后台”并行操作，而且使用多线程版英特尔® IPP 会默认支持该库。
位于英特尔® IPP 文档目录的 ThreadedFunctionsList.txt 文件包含一份多线程基元完整列表。
注：事实上，英特尔® IPP 内建英特尔® C 编译器，且 OpenMP 无需通过这些工具完成构建。英特尔® IPP 基元可采用与适用于相关操作系统（OS）平台的英特尔® C 编译器兼容的二进制格式，并支持连接应用。编程人员可以借助英特尔工具或其它喜欢的开发工具来构建采用英特尔® IPP 应用的应用。
控制英特尔® IPP 基元内的 OpenMP 线程
在默认情况下，线程化英特尔® IPP 基元所采用的 OpenMP 线程数量与系统中的硬件线程数量相同（这由所使用的处理器数量和类型决定）。例如，一颗支持英特尔® 超线程（HT）技术（英特尔® HT 技术）的四核处理器拥有八条硬件线程（四枚内核均支持两条线程）。一颗不支持英特尔® HT 技术的双核处理器拥有两条硬件线程。
通过两个英特尔® IPP 基元能够对多线程版英特尔® IPP（ippSetNumThreads() 和 ippGetNumThreads()）内的 OpenMP 线程实施通用控制，查看与之相关的状态。调用 ippGetNumThreads 可以确定当前的线程数上限，而使用 ippSetNumThreads 则可以修改该上限值。但您通过 ippSetNumThreads 设置的线程数上限不能超过现有可用硬件线程数。此上限同时也可作为多线程基元可以采用的 OpenMP 软件线程数上限。为了实现最佳并行效率，一些英特尔® IPP 函数采用的线程可能少于该线程数上限，它们采用的线程数量不会超过此上限。
通过在开始运行应用时调用 ippSetNumThreads(1) 或将应用与英特尔® IPP 单线程静态函数库相连，可以禁用多线程版英特尔® IPP 的 OpenMP。
OpenMP 库可引用几个配置环境变量。其中，通过 OMP_NUM_THREADS 能够设置 OpenMP 库在运行时可以采用的线程数默认值（线程数上限）。不过，英特尔® IPP 库会覆盖该值，将应用所能采用的 OpenMP 线程数重新设置为系统内的硬件线程数（如上所述）或调用 ippSetNumThreads 所指定的线程数值。最终设定的值应为两者中较低的那一个。不使用英特尔® IPP 的 OpenMP 应用可能仍然会受到 OMP_NUM_THREADS 环境变量的影响。同时，此类 OpenMP 应用不会受到在英特尔® IPP 应用中调用 ippSetNumThreads 函数的影响。
嵌套 OpenMP
如果英特尔® IPP 应用同时使用 OpenMP 部署了多条线程，则该应用调用的多线程英特尔® IPP 基元可能充当单线程基元运行。这取决于英特尔® IPP 基元是否在一个 OpenMP 并行代码段被调用以及嵌套并行性是否已在英特尔® OpenMP 库内被禁用（在默认情况下）。
嵌套并行 OpenMP 区域可能会导致有效超额订阅可用硬件线程数的大量线程生成。创建并行区域总是会产生一定的开销，与嵌套并行 OpenMP 区域所带来的优势相比，因此产生的开销可能更为突出。总而言之，使用英特尔® IPP 基元的 OpenMP 线程化应用应通过调用 ippSetNumThreads(1) 或采用单线程静态英特尔® IPP，禁用英特尔® IPP 的多线程功能。
内核关联性
一些位于信号处理域的英特尔® IPP 基元经过设计，可通过一个合并的二级高速缓存运行并行线程。这些函数（单精度和双精度 FFT、Div、Sqrt 等）需要一个共享高速缓存来最大限度提高它们的多线程性能。换而言之，这些基元内的线程应通过一个共享高速缓存在位于同一块芯片的内核上运行。为确保达到所需条件，您应在运行采用英特尔® IPP 的应用之前设置下列 OpenMP 环境变量：

- collapse source view plain copy to clipboard print ?

KMP_AFFINITY=compact

KMP_AFFINITY=compact

对于在同一块芯片上配备两枚以上内核的处理器，您可以不用设置环境变量即可自动满足所需条件。但在那些拥有两块以上芯片的系统（如英特尔® 奔腾® D 处理器或多插座主板）上，为每块芯片提供支持的高速缓存并未实现共享，因而如果不设置上述 OpenMP 环境变量可能会显著降低该系列多线程英特尔® IPP 基元的性能。

使用指南

英特尔® IPP 应用内的线程
许多采用英特尔® IPP 基元的多线程示例应用都是英特尔® IPP 的一部分。这些示例应用全部都包含源代码，其中一些示例应用部署了应用级线程，也有一些应用采用了内建于英特尔® IPP 的线程。在大多数情况下，部署多条线程可显著提升性能。
在多线程应用中使用基元时，我们建议采用前面提及的技术禁用英特尔® IPP 的内建线程。这样做可以确保该函数库的内建线程与应用的线程机制不发生冲突，从而有助于避免软件线程数量超过可用硬件线程数量。
英特尔® IPP 的大多数基元侧重于执行数组运算，这是因为该函数库可以充分利用十分适用于向量运算的处理器 SIMD 指令。在针对多个独立数据元素进行运算时实施线程化是一件水到渠成的事。总而言之，通过英特尔® IPP 实施线程化最简单的方法是利用数据分解或将大型数据块分解成小型数据块，采用多条相同的并行执行线程在小型数据块上执行工作任务。
内存与高速缓存对齐
在大型数据块上工作时，对齐不当的数据会降低吞吐量。英特尔® IPP 包含一系列内存分配与对齐函数，它们可以帮助解决这个问题。此外，大多数编译器也可以在经过配置后通过添加新的结构来确保实现数据高效对齐。
与高速缓存行相关的高速缓存对齐和数据间距在执行并行线程——尤其是包含循环英特尔® IPP 基元构想的并行线程时十分重要。如果运行多条并行线程需要频繁采用同步或共享数据结构，则执行一条线程的写入操作可能会使与“邻近”线程数据结构相关的高速缓存行无效。
在构建相同英特尔® IPP 操作（数据分解）的并行线程时，请务必考虑在并行线程上运行的已分解数据块的相对间距以及这些线程内基元所采用的所有控制数据结构的间距。同时，还请特别注意这些控制结构是否包含在英特尔® IPP 函数的每次迭代上更新的状态信息。如果这些控制结构共享一个高速缓存行，则更新一个控制结构可能会使一个邻近结构失效。
最简单的解决方案是分配这些控制数据结构，便于它们使用处理器高速缓存行尺寸（通常为 64 字节）的倍数。开发人员也可以采用编译器的对齐操作器来确保这些结构及相关数据阵列始终与高速缓存行边界对齐。任何用于添加控制结构的废弃字节都将足以弥补因更新基元每次迭代的高速缓存行而损失的总线周期。
借助 DMIP 实施管线式处理
在理想状态下，应用会在运行时进行调整，优化可用 SIMD 指令用途、现有硬件线程数量以及高速缓存容量。只有实现这三大资源的最佳配置，才可能使应用几近完美地并行运行，这是英特尔® IPP 的一部分 DMIP 库所肩负的基本职责。
采用 DMIP 并行方法（构建在针对高速缓存进行尺寸优化的数据块上执行的英特尔® IPP 基元的并行顺序）可提高几项变量利用每次函数调用按顺序计算整个数据集的应用性能。
例如，尽管图像仍然保存在高速缓存中，您无需在整个图像上进行操作，而是可以将该图像分解成几个可缓存片断，然后在每个片断上执行多项操作。执行上述操作的顺序便是一条计算管线，它可应用于每个计算层面，直到整个数据集得到处理为止。通过构建并行运行的多条管线可以提高性能。
如欲了解关于此项技术的更多信息，请查阅《图像处理领域的里程碑：DMIP》。
线程化性能优势
包括英特尔® IPP 在内的其它高级线程化函数库工具在应用于多核环境中时有助于显著提升应用性能。例如，英特尔® IPP 数据压缩库能与常用 ZLIB、BZIP2、GZIP 和 LZO 无损数据压缩库完全兼容。英特尔® IPP 版 BZIP2 和 GZIP 库可通过利用本地线程将大型文件分割成许多可供并行压缩的数据块或在独立线程中处理多个文件，来充分发挥多线程环境的优势。借助此项技术，GZIP 库能够提升一颗四核处理器的性能高达 10 倍（与不支持英特尔® IPP 的单线程库相比）。
在多媒体领域（如视频和图像处理领域），英特尔® IPP 版 H.264 和 VC 1 解码器几乎能实现理论上最高的可用硬件线程扩展，并可利用多条本地线程在视频帧上执行并行解码、重组和解除闭锁操作。在一颗四核处理器上运行这款英特尔® IPP 增强型 H.264 解码器时，您将能获得高达 3 倍到 4 倍的高清比特流性能提升。

结论

目前没有哪种方法能够在各种情况下确保提供最佳性能。使用线程和英特尔® IPP 所能达到的性能提升程度取决于应用本身的性质（如实施线程化的容易度）、应用可以采用的英特尔® IPP 基元组合（线程化基元对比非线程化基元、使用频率等）以及应用运行的硬件平台（内核数量、内存带宽、高速缓存容量和类型等）。

使用英特尔® Parallel Inspector 查找基于 OpenMP* 的多线程代码中存在的竞态条件

提交新文章

Published On :
2010年01月10日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

英特尔® Parallel Inspector是英特尔® Parallel Studio套件中的一项工具，用于调试使用 Win32*、英特尔® 线程构建模块（英特尔® TBB）或 OpenMP* 线程化模型的应用中出现的多线程错误。英特尔 Parallel Inspector 可自动查找存储冲突、死锁（或可能导致出现死锁的条件），以及线程停止等等。本文详细介绍了与调试 OpenMP 线程化应用相关的特定问题。本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

OpenMP 应用编程接口 (API) 支持在所有架构上使用 C/C++ 和 Fortran 语言进行多平台共享内存并行编程，其中包括 UNIX* 和 Windows* 平台。OpenMP 是一个可移植和可扩展的模型，为共享内存并行编程人员提供了一个简单、灵活的接口，帮助他们轻松开发用于台式机和超级计算机等各种平台的并行应用。
调试线程化应用是一个十分棘手的过程，因为调试器会改变运行时性能，掩盖竞态条件。甚至打印声明都可以掩盖问题，因为它们会用到同步和操作系统函数。 OpenMP 更是加剧了情况的复杂性。OpenMP 会插入私有变量、共享变量，以及不使用专用 OpenMP 感知调试器根本不可能检测到和跨越的其它代码。
以下代码展示了 OpenMP 的易用性，以及出现数据争用现象的高概率：

- collapse source view plain copy to clipboard print ?

double x, pi, sum = 0.0;
int i;
step = 1.0 / (double)num_steps;
#pragma omp parallel for
for (i = 0; i < num_steps; i++)
{
x = (i + 0.5) * step;
sum = sum + 4.0 / (1.0 + x * x);
}
pi = sum * step;

  double x, pi, sum = 0.0;
  int i;
  step = 1.0 / (double)num_steps;

#pragma omp parallel for
  for (i = 0; i < num_steps; i++)
  {
    x = (i + 0.5) * step;
    sum = sum + 4.0 / (1.0 + x * x);
  }
  pi = sum * step;

仔细观察循环可以发现，上例中使用了“工作共享”。“工作共享”是 OpenMP 中使用的一个一般术语，主要用于描述线程间工作的分配情况。如上例所示，当工作共享用于 for 结构时，循环迭代会在多个线程间进行分配，以便每个循环迭代只执行一次，并与一个以上的线程并行执行。OpenMP 完全可以自行决定创建的线程数量，以及如何以最佳方式创建、同步和毁坏线程。
编译器将对循环进行线程化，但并不会成功，这是因为至少有一个循环迭代与另外一个不同的迭代存在着数据相关性。我们将这样的情形称之为竞态条件。竞态条件只在使用共享资源（如内存）和并行执行时出现。要解决该问题，必须通过进行同步化来消除数据争用现象。
一般来说，竞态条件很难被检测到，这是因为在给定的实例中，变量可能会采用确保程序正常运行所需的顺序，借以“赢得竞争”。而且，一项程序某一次可以正常运行并不表示它永远都能正常运行。最好先在多个不同平台上对程序进行测试，譬如支持英特尔® 超线程（HT）技术的平台和采用多路物理处理器的平台等等。英特尔 Parallel Inspector 等工具也可提供一定的帮助。传统调试器在探测竞态条件方面毫无用处，因为它们能让一个线程停止“竞争”，而其它线程则继续大幅度地改变运行时行为。

建议

使用英特尔 Parallel Inspector 帮助调试 OpenMP、英特尔 TBB 和 Win32 多线程应用。英特尔 Parallel Inspector 提供了非常有价值的并行执行信息和调试提示。借助动态二进制插桩 (dynamic binary instrumentation)，英特尔 Parallel Inspector 可监控 OpenMP 编译指示、Win32 线程 API 和所有内存访问，借以识别编码错误，特别是测试过程中没有出现但仍可能发生的不常见错误。使用该工具时，请务必谨记在访问尽可能少内存的情况下测试所有代码路径，以便加快数据收集进程。通常情况下，您需要对源代码或数据集稍作修改，以减少应用处理的数据量。
使用英特尔 Parallel Inspector 对程序进行分析之前，需完成一定的准备工作，例如在编译代码时禁用优化选项，启用调试符号。英特尔 Parallel Inspector 作为一个 Microsoft Visual Studio* 插件运行。找到相应的工具栏或菜单命令，启动英特尔 Parallel Inspector，然后在分析类型下拉列表中选择“Inspect:Threading Errors”（检查：线程错误）。英特尔 Parallel Inspector 提供有四种分析级别，具体情况视预期深度和开销而定。该工具将打开在当前 Microsoft Visual Studio 项目中编译的应用。
图 1 中，通过计算每个迭代的部分和，英特尔 Parallel Inspector 在 x 变量经过修改的源代码行和下一个源代码行中发现数据争用错误。这些错误非常明显，因为多条线程正同时对全局变量 x 和 sum 进行读写访问。此外，英特尔 Parallel Inspector 还发出“Potential privacy infringement”（潜在隐私侵犯）警告，指出在工作线程 (worker thread) 中访问了位于主线程堆栈上的变量。

图 1. 英特尔 Parallel Inspector 中的问题集概述

如欲深入调查问题根源，英特尔 Parallel Inspector 可借助函数调用堆栈和 reach filtering（范围筛选）工具提供详细的错误信息。快速参考源代码有助轻松判断检测到错误的代码范围。如图 2 所示，“Sources”（源代码）选项卡显示了详细的两部分源代码窗口，反映了不同线程到共享变量的访问情况，其中包括详细信息，双击可导航至本地源代码。

图 2. 英特尔 Parallel Inspector 中的源代码视图

在英特尔 Parallel Inspector 的帮助下获得错误报告并确定问题根源后，开发人员便可以开始考虑采用什么方法解决问题。下文介绍了在并行 OpenMP 循环中避免出现数据争用现象的一般考虑事项，以及关于如何修复被检查代码中所存在问题的有效建议。
管理共享数据和私有数据
几乎每个有用的循环都会读取或写入内存，所以程序员必须告知编译器哪部分内存应在线程间共享，哪部分应保持私有状态。一旦某部分内存确定为共享内存，所有线程都将访问该同一内存位置。而当内存确定为私有时，每条线程都将获得一份用于私有访问的单独变量副本。当循环结束时，这些私有副本将被销毁。在默认情况下，除了私有循环变量外，所有变量均共享。内存将通过以下两种方式宣告私有：

不用静态关键词，宣告变量位于循环内部（实际位于并行 OpenMP 指令内部）。
指定 OpenMP 指令上的私有子句。

导致上面示例中的循环无法正常执行的原因有两个，其中一个便是变量 x 的状态为共享，而实际上它应该是私有变量。下方的编译指示表达式宣告变量 x 为私有内存，可用来更正该问题：

- collapse source view plain copy to clipboard print ?

#pragma omp parallel for private(x)

#pragma omp parallel for private(x)

关键代码段（Critical Section）
上述示例失败的另外一个原因便是在线程间共享了全局变量 sum。变量 sum 不可针对线程设为私有变量，因为它需要收集每条线程中所有为各个迭代计算的部分和。解决这一问题的方法是使用关键代码段。
关键代码段可以保护代码块免受多条线程的同时访问。一条线程如果遇到关键代码段，只有当任何关键代码段中都没有其它线程时，它才能进入其中一个或几个代码段。以下范例使用了一个未命名的关键代码段。

- collapse source view plain copy to clipboard print ?

#pragma omp critical
sum = sum + 4.0 / (1.0 + x * x);

#pragma omp critical
sum = sum + 4.0 / (1.0 + x * x);

全局或未命名的关键代码段未必能够提高性能，因为每条线程都必须有效竞争相同的全局代码段。为此，OpenMP 对关键代码段进行了命名。命名的关键代码段可支持更细化的同步，确保只有需要在某具体代码段上被阻隔的线程才会被阻隔。下面的范例即依此对以上范例的编码进行了改进。

- collapse source view plain copy to clipboard print ?

#pragma omp critical(sumvalue)
sum = sum + 4.0 / (1.0 + x * x);

#pragma omp critical(sumvalue)
sum = sum + 4.0 / (1.0 + x * x);

通过为关键代码段命名，应用可以拥有多个关键代码段，线程也可一次进入多个关键代码段。值得注意的是，进入嵌套的关键代码段有可能导致死锁，这一点即使是 OpenMP 也检测不出来。使用多个关键代码段时，要格外注意检查可能隐藏在子程序中的关键代码段。
原子操作 (Atomic Operations)
使用关键代码段可有效提升性能，直至线程对受保护代码段的争用情况过为严重。如果某条线程需要等待一段时间才可进入关键代码段，操作系统将启动核心级同步机制，让该线程进入睡眠模式，当相关资源可用时再将其唤醒。这会导致额外的程序执行开销，不过，使用原子操作便可解决该问题。
根据定义，原子操作 (atomic operations) 保证不会被打断，并且可有效帮助相关语句更新共享内存位置，以避免一些竞态条件。在下面的代码中，程序员已经明确了变量在语句当中保持稳定的重要性。

- collapse source view plain copy to clipboard print ?

a[i] += x; // may be interrupted half-complete

a[i] += x;  // may be interrupted half-complete

虽然单独汇编指令的执行绝不会被打断，但是高级语言（如 C/C++）的语句却会被翻译为多条汇编指令，因此有可能被打断。在上例中，a[i] 的值可能会在读值、添加变量 x 和将值写回内存等汇编语句之间有所变化。但是，下面的 OpenMP 结构却能确保语句自动执行，不存在被打断的可能性。

- collapse source view plain copy to clipboard print ?

#pragma omp atomic
a[i] += x; // never interrupted

#pragma omp atomic
a[i] += x;  // never interrupted

如果操作系统具备相关特性和硬件能力，那么 OpenMP 将选择最有效的方法来执行语句。然而，原子操作可被视作与加/减、乘/除等相同的简单基本操作，带有赋值运算符，且运算过程中只有两个表达式。如此看来，原子操作可能无法有效保护示例中的 sum 变量。
Reduction 子句
事实上，累计值的循环十分普遍，OpenMP 便有一个特定的子句来支持此类循环。假设循环用于计算 double 值部分和的总和。变量 sum 必须与其它循环共享，才能生成正确的结果，但是它只有作为私有变量才允许多条线程访问。为解决变量的这一两难处境，我们可以使用 OpenMP 提供的 reduction 子句，高效地对循环中的一个或更多变量进行数学归约运算联合操作。下列循环就是采用 reduction 子句，生成了正确的结果。

- collapse source view plain copy to clipboard print ?

#pragma omp parallel for private(x) reduction(+:sum)
for (i = 0; i < num_steps; i++)
{
x = (i + 0.5) * step;
sum = sum + 4.0 / (1.0 + x * x);
}

#pragma omp parallel for private(x) reduction(+:sum)
  for (i = 0; i < num_steps; i++)
  {
    x = (i + 0.5) * step;
    sum = sum + 4.0 / (1.0 + x * x);
  }

实际上，OpenMP 可为每条线程提供变量 sum 的私有副本。当线程退出时，它会将值加在一起，并将结果放在变量的一个全局副本中。

使用指南

英特尔 Parallel Inspector 支持 OpenMP、Win32 线程 API 和英特尔 TBB 线程 API。使用 OpenMP 一般要求必须配备英特尔® 编译器。也可以使用 Microsoft 的 OpenMP 实施，但必须将英特尔 OpenMP 运行时库连接至处于兼容模式的项目。如欲获得更出色的支持和最为详细的分析结果，不妨考虑使用英特尔编译器的最新 OpenMP 运行时库。
请注意，英特尔 Parallel Inspector 执行的是动态分析，而不是静态分析。英特尔 Parallel Inspector 只分析正执行的代码。因此，可能有必要针对程序的不同部分执行多项分析，以确保覆盖所有相关代码。
英特尔 Parallel Inspector 插桩提高了应用对 CPU 和内存资源的要求，因此选择规模小但极具代表性的测试问题非常重要。运行时间只有几秒钟的工作负载将是最佳选择。工作负载不一定是现实存在的，但它们必须用到多线程代码的相关代码段。

采用英特尔® Parallel Amplifier 解决线程不平衡问题

提交新文章

Published On :
2010年02月23日 20:00

评级

请登录后评级！当前分数： 0 由 0 用户

摘要

线程应用性能的限制因素之一是负载不平衡。平衡线程间的工作量对应用性能来说至关重要。负载平衡的主要目的是最大限度地削减线程的闲置时间，同时以最小的工作分享开销帮助所有线程平均分享工作负载。Intel® Parallel Amplifier 为 Intel® Parallel Studio 中的一个产品，主要用于并行应用的微调，进而实现多核处理器的最佳性能。Intel Parallel Amplifier 能够快速找出多核性能的瓶颈，并帮助开发人员加速识别和修复此类问题的进程。实现完美的负载平衡绝非易事，这主要取决于应用、负载和线程实施内的并行性。
本文是《英特尔® 多线程应用开发指南》系列的一部分，后者用于指导开发人员针对英特尔 ® 平台开发高效的多线程应用。

背景

一般来说，独立任务（负载）向线程的映射和调度通常以两种形式发生：静态和动态。如果所有任务的长度相同，那么应将任何在可用线程之间进行简单的静态分工，将总任务量平等划分并分配给每个线程，此为最佳解决方案。反之，当单个任务长度不同时，向线程动态分配任务为最佳解决方案。
Intel Parallel Amplifier 提供的同步分析将测量应用是如何利用一个给定系统上的可用核心。在分析过程中，Parallel Amplifier 收集并提供关于多少线程正在活动的信息。活动线程即正在运行或排队的线程，它们并没有在一个指定的等待或阻碍 API 进行等候。正在运行的线程数量对应着一个应用的并发级别。通过比较并发等级和处理器的数量，Intel Parallel Amplifier 将应用对系统中处理器的利用情况进行分级。
为了展示 Intel Parallel Amplifier 如何识别热点与负载不平衡问题，下面提供了一个C语言编写的示例程序。此程序计算出基于三维距离的一个质点系统的势能。这是为一个多线程应用，它使用本机的 Win32* 线程，并创建由 NUM_THREADS 变量指定的线程数量。本次讨论的范围不包括 Win32 线程的介绍、线程方法或如何引入线程。此次将主要演示Intel Parallel Amplifier 如何帮助识别负载不平衡和辅助可扩展并行应用的开发。

- collapse source view plain copy to clipboard print ?

for (i = 0; i < NUM_THREADS; i++)
{
bounds[0][i] = i * (NPARTS / NUM_THREADS);
bounds[1][i] = (i + 1) * (NPARTS / NUM_THREADS);
}
for (j = 0; j < NUM_THREADS; j++)
{
tNum[j] = j;
tHandle[j] = CreateThread(NULL,0,tPoolComputePot,&tNum[j],0,NULL);
}
DWORD WINAPI tPoolComputePot (LPVOID pArg) {
int tid = *(int *)pArg;
while (!done)
{
WaitForSingleObject (bSignal[tid], INFINITE);
computePot (tid);
SetEvent (eSignal[tid]);
}
return 0;
}

for (i = 0; i < NUM_THREADS; i++)
{
  bounds[0][i] = i * (NPARTS / NUM_THREADS);
  bounds[1][i] = (i + 1) * (NPARTS / NUM_THREADS);
}
for (j = 0; j < NUM_THREADS; j++)
{
  tNum[j] = j;
  tHandle[j] = CreateThread(NULL,0,tPoolComputePot,&tNum[j],0,NULL);
}


DWORD WINAPI tPoolComputePot (LPVOID pArg) {
  int tid = *(int *)pArg;
  while (!done)
  {
    WaitForSingleObject (bSignal[tid], INFINITE);
    computePot (tid);
    SetEvent (eSignal[tid]);
  }
  return 0;
}

下面给出的例程中，每个线程均并行执行。在computePot 例程中，每个线程均使用由线程的分配标识号索引的存储边界，以校准所用质点的起始和终止范围。在每个线程将其迭代空间（开始与结束值）初始化后，它开始计算质点的势能。

- collapse source view plain copy to clipboard print ?

void computePot (int tid) {
int i, j, start, end;
double lPot = 0.0;
double distx, disty, distz, dist;
start = bounds[0][tid];
end = bounds[1][tid];
for (i = start; i < end; i++)
{
for (j = 0; j < i-1; j++)
{
distx = pow ((r[0][j] - r[0][i]), 2);
disty = pow ((r[1][j] - r[1][i]), 2);
distz = pow ((r[2][j] - r[2][i]), 2);
dist = sqrt (distx + disty + distz);
lPot += 1.0 / dist;
}
}
gPot[tid] = lPot;
}

void computePot (int tid) {
  int i, j, start, end;
  double lPot = 0.0;
  double distx, disty, distz, dist;
  start = bounds[0][tid];
  end = bounds[1][tid];

  for (i = start; i < end; i++)
  {
    for (j = 0; j < i-1; j++)
    {
      distx = pow ((r[0][j] - r[0][i]), 2);
      disty = pow ((r[1][j] - r[1][i]), 2);
      distz = pow ((r[2][j] - r[2][i]), 2);
      dist = sqrt (distx + disty + distz);
      lPot += 1.0 / dist;
    }
  }
  gPot[tid] = lPot;
}

热点分析用于找出应用中的热点，从而帮助确定适合的函数。在基于英特尔® 酷睿2 4核处理器的单插槽系统上，该应用运行所消耗的总时间大约为15.4秒。热点分析表明，computePot 例程为主要热点，消耗了大量 CPU 时间（23.331秒）。对 computePot 函数的深入分析揭示出该热点（图 1 ）的主要促成因素。

图 1. 热点分析的源代码视图

并发性分析结果显示，相同例程的 CPU 利用率较差（图 2），应用程序平均使用 2.28 个核。主要热点并没有利用全部的可用核心；CPU 的利用率大部分时间或者较差（仅使用一个核心）或者一般（使用 2-3 个核心）。接下来的问题是，是否存在一定的负载不平衡，导致 CPU 利用率较差。最简单的方法是选择函数-线程-自下而上树或是线程-函数-自下而上树作为新的粒度，如图 4 所示。

图 2. 并发性分析结果

图 3. 并发性结果摘要视图

并发分析时间值结果对应下列应用类型：

闲置：程序中所有线程都在等待；没有线程在运行。
较差：在默认情况下，较差利用率通常定义为线程数量增至目标并发的 50%。
一般：在默认情况下，一般利用率是指当线程数量为目标并发的 51-85%。
理想：在默认情况下，理想利用率是指线程数量为目标并发的 86-115%。

图 4. 并发分析结果显示函数－>线程组

图 4 表明，并行执行这个例程的 4 个工作线程的工作量并不相同，因此可能导致负载不平衡和较差的 CPU 利用率。这种行为将阻止多线程应用的适当扩展。仔细观察源代码可以发现，主例程内的外部循环根据将在线程池内（起始边界 3D [0][TID]，结束边界 3D [1][TID]）创建的工作线程数量，静态划分质点迭代。这个例程内的内部循环使用外部索引作为退出条件。这样一来，外部循环使用的质点数量越多，内部循环执行迭代次数也就越多。因此，每对质点仅在势能计算中计算一次。这种静态分布明确分配了不同的计算量。
修复负载不平衡的一个办法是更加动态地向线程分配质点。例如，不再分配连续质点组（如原始版本中），每个线程均以线程识别号（tid）索引的质点而开始，因此能够计算所有其质点号与线程号不同的质点。例如，当运行两个线程时，一个线程处理偶数质点，另一个线程处理奇数质点。

- collapse source view plain copy to clipboard print ?

void computePot(int tid) {
int i, j;
double lPot = 0.0;
double distx, disty, distz, dist;
for(i=tid; i<NPARTS; i+= NUM_THREADS ) { //<-for( i=start; i<end; i++ )
for( j=0; j<i-1; j++ ) {
distx = pow( (r[0][j] - r[0][i]), 2 );
disty = pow( (r[1][j] - r[1][i]), 2 );
distz = pow( (r[2][j] - r[2][i]), 2 );
dist = sqrt( distx + disty + distz );
lPot += 1.0 / dist;
}
}
gPot[tid] = lPot;

void computePot(int tid) {
  int i, j;
  double lPot = 0.0;
  double distx, disty, distz, dist;
  for(i=tid; i<NPARTS; i+= NUM_THREADS ) { //<-for( i=start; i<end; i++ )
    for( j=0; j<i-1; j++ ) {
    distx = pow( (r[0][j] - r[0][i]), 2 );
    disty = pow( (r[1][j] - r[1][i]), 2 );
    distz = pow( (r[2][j] - r[2][i]), 2 );
    dist = sqrt( distx + disty + distz );
    lPot += 1.0 / dist;
    }
  }
  gPot[tid] = lPot;

此次更改之后分析应用并发性，显示得出热点函数现在充分利用所有可用核心（图5）。

图 5. 更改之后的并发分析结果

概要窗格（图 6）提供了更改结果和影响的快速查看。耗时从大约 15. 4 秒减少至 9.0 秒，CPU 平均利用率从 2.28 增长至 3.9.通过让工作线程执行平等的计算量，速度提高了 1.7 倍，用时减少了大约 41.5%。

图 6. 负载平衡版本概要视图

概要和并行结果表示，应用程序的新版本几乎使用了所有可用核心，并且串行代码段（较差使用率）和未充分使用段均已消失。

建议

目前存在许多种线程方法，每个方法均提供了处理线程任务分布的不同机制。一些常用线程方法包括：

显式或本地线程方法（例如，Win32 和 POSIX* 线程）
线程抽象
- 英特尔® 线程化构建模块
- OpenMP*

显式线程方法（例如Win32 和 POSIX* 线程）没有任何能力来自动为线程调度一组独立任务。当有需要时，必须将这种能力编入应用程序。正如这个例子所示，静态的任务调度是最简单直接的方法。对于动态调度，有两种相关方法较容易实施：生产商/消费者和管理者/工人在前者，一个或多个线程（生产商）列队放置任务，而消费者线程根据需要进行任务处理。如果部分预处理需在消费者线程获取任务之前完成，这时通常采用生产商/消费者模式（并非严格必要）。在管理者/工人模式中，工人线程与管理者线程结合（rendezvous），每当需要增加工作量时，可直接接受任务分配。
无论采用哪种模式，必须使用正确的线程数量和组合，以确保执行所需计算任务的线程并没有闲置。单个管理者线程易于编码并可确保任务的合理分配，相比之下，消费者线程有时会闲置，这时可能需要减少消费者线程数量或是增加生产商线程数量。合适的解决方案主要取决于算法考虑以及所分配任务的数量和长度。
OpenMP 提供了四种针对迭代工作共享结构的调度方法。通常默认使用静态的迭代调度。当每迭代工作量不同并且模式无法预测时，动态的迭代调度能更好地平衡工作负载。
当使用动态调度时，可能出现成为“错误共享”的微构架问题。错误共享是一种会降低性能的模式访问问题。当两个或多个线程重复写入相同的缓存行（在英特尔架构中为64 位）时，错误共享将会发生。当在线程之间动态分配工作负载时，应特别予以注意。
Intel® Threading Building Blocks （Intel® TBB）是一个基于运行时的并发编程模型，包含基于模板的运行库，可帮助开发人员充分利用多核处理器的潜在性能。 Intel® TBB 可帮助开发人员编写可扩展应用程序，以充分利用并发收集与并行算法的优势。它提供了一种采取工作窃取（work-stealing）机制的分而治之的调度算法，因此开发人员无需操心各种调度算法。借助工作窃取机制，Intel TBB 可动态地平衡工作线程之间的任务。

其它资源

英特尔 ® 软件网络并行编程社区
英特尔® Parallel Studio
OpenMP* 技术规范
英特尔® 线程构建模块
面向开源的英特尔线程构建块
James Reinders，《英特尔线程构建模块：装备 C++ 语言以支持多核处理器并行性》O'Reilly Media, Inc.，Sebastopol, CA，2007 年

-----------------------------华丽分割线-----------------------------

采用英特尔® Parallel Composer 编写并行执行代码

摘要

开发人员可以选择使用多种方法在代码中引入并行处理能力。本文概括介绍了使用英特尔® Parallel Composer 进行并行编码的几种方法，并对它们的主要优势进行了比较。虽然英特尔 Parallel Composer 只适用于 Windows* 环境下的 C/C++ 开发，但许多方法同样适用于 Fortran 语言和 Linux* 环境（只要具备适当的编译器即可）。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇，旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。

背景

英特尔® 编译器可通过多种方法自动检测和优化适合并行执行的代码结构（例如矢量化和自动/并行化），其中大部分方法要求修改代码。插入的编译指示或函数均依赖于真正执行并行线程分解和调度操作的运行时数据库，例如 OpenMP*、英特尔® 线程构建模块（英特尔® TBB）和 Win32* API。这些方法之间的主要区别在于它们对执行详情的控制级别；一般来说，控制力度越大，所需代码变更的介入性便越强。
使用 OpenMP* 添加并行性
OpenMP 是可移植多线程应用开发的行业标准。英特尔® C++ 编译器支持 OpenMP C/C++ 3.0 版 API 规范，有关该规范的具体内容请访问 OpenMP 网站（http://www.openmp.org/)）。使用 OpenMP 添加并行性的流程可由用户通过 OpenMP 指令来控制。该方法对细粒度（循环级别）和粗粒度（函数级别）线程极为有效。在将串行应用转换为并行应用方面，OpenMP 指令提供了一种易于使用且功能强大的方法，帮助多核系统通过并行执行获得显著的性能提升。这些指令需通过 /Qopenmp 编译器选项启用，如果没有编译器选项它们便会被忽略。这一特点使得用户能够通过相同的源代码构建串行和并行版本应用。对于共享内存的并行计算机，该特点还支持用户简单对比串行和并行执行。
下表列出了常用的 OpenMP* 指令：

指令
描述

#pragma omp parallel for [clause] ... for - loop
对紧随编译指示之后的循环进行并行化。

#pragma omp parallel sections [clause] ... { [#pragma omp section structured-block] ... }
在并行组的线程之间分配不同代码段的执行任务。每个结构化块由并行组中的一条线程在其隐式任务环境中执行一次。

#pragma omp master structured-block
主结构中包含的代码由线程组中的主线程执行。

#pragma omp critical [ (name) ] structured-block
提供到结构化块的互斥访问。在程序的任意位置，每次只允许执行一个关键代码段。

#pragma omp barrier
用于对并行区域内多条线程的执行进行同步。确保在任何线程开始执行越过屏障指令的任何代码之前，所有线程均已完成执行屏障前的各个代码。

#pragma omp atomic expression-statement
使用硬件同步基元实现互斥。关键代码段可提供到某代码块的互斥访问，而原子指令则提供到单个赋值语句的互斥访问。

#pragma omp threadprivate (list)
指定要复制的全局变量列表，每条线程一个实例（即每条线程均持有一个独立的变量副本）。

示例 1：

- collapse source view plain copy to clipboard print ?

void sp_1a(float a[], float b[], int n) {
int i;
#pragma omp parallel shared(a,b,n) private(i)
{
#pragma omp for
for (i = 0; i < n; i++)
a[i] = 1.0 / a[i];
#pragma omp single
a[0] = a[0] * 10;
#pragma omp for nowait
for (i = 0; i < n; i++)
b[i] = b[i] / a[i];
}
}
icl /c /Qopenmp par1.cpp
par2.cpp(5): (col. 5) remark: OpenMP DEFINED LOOP WAS PARALLELIZED.
par2.cpp(10): (col. 5) remark: OpenMP DEFINED LOOP WAS PARALLELIZED.
par2.cpp(3): (col. 3) remark: OpenMP DEFINED REGION WAS PARALLELIZED.

void sp_1a(float a[], float b[], int n) {
int i;
#pragma omp parallel shared(a,b,n) private(i)
{
#pragma omp for
for (i = 0; i < n; i++)

a[i] = 1.0 / a[i];

#pragma omp single
a[0] = a[0] * 10;
#pragma omp for nowait
for (i = 0; i < n; i++)
b[i] = b[i] / a[i];
}
} 
icl /c /Qopenmp par1.cpp
par2.cpp(5): (col. 5) remark: OpenMP DEFINED LOOP WAS PARALLELIZED.
par2.cpp(10): (col. 5) remark: OpenMP DEFINED LOOP WAS PARALLELIZED.
par2.cpp(3): (col. 3) remark: OpenMP DEFINED REGION WAS PARALLELIZED.

/Qopenmp-report[n] 编译器选项可用来控制 OpenmMP 并行化工具的诊断消息级别，其中 n 是 0 和 2 之间的一个数值。若想使用该选项，程序员必须首先指定 /Qopenmp 选项。如果没有为 n 指定具体值，选项将采用默认值 /Qopenmp-report1，此时的诊断消息将显示成功实现并行化的循环、区域和代码段。
鉴于只在代码中插入指令，程序员可以循序渐进地逐步更改代码，这有助于他们维持串行一致性。当代码在一路处理器上执行时，最终结果与未经修改的源代码相同。OpenMP 是一款可支持多个平台和操作系统的单一源代码解决方案。程序员不必费尽心思判断合适的内核数量，因为 OpenMP 运行时能够自动选择正确的内核数。
除了程序员最常使用的循环级并行化结构外，OpenMP 3.0 还集成了一个新的任务级并行化结构，显著简化了对函数进行并行化的流程。该任务模型可对带有不规则动态数据结构模式或诸如递归等不易并行化的复杂控制结构的程序进行并行处理。任务编译指示在并行区域环境中执行，将创建显式任务。如果在并行区域内遇到词法域编译指示，那么该任务块中的代码将概念性地排成一队，等待由执行并行区域的线程组中的一条线程执行。为了保留顺序语义，需确保并行区域内所有排队等待的任务在并行区域结束处均可完成。程序员应确保结构中不存在任何依赖关系，并且依赖关系已在显式任务之间，以及显式任务内外的代码之间的实现了适当同步化。
示例 2：

- collapse source view plain copy to clipboard print ?

#pragma omp parallel
#pragma omp single
{
for(int i = 0; i < size; i++)
{
#pragma omp task
setQueen (new int[size], 0, i, myid);
}
}

#pragma omp parallel
#pragma omp single
{
  for(int i = 0; i < size; i++)
  {
    #pragma omp task
    setQueen (new int[size], 0, i, myid);
  }
}

面向并行化的英特尔® C++ 编译器语言扩展
英特尔® 编译器使用简单的 C 和 C++ 语言扩展让并行编程变得更加轻松。该版本编译器中引入了四个关键词。

__taskcomplete
__task
__par
__critical

为了让应用在由这些关键词提供的并行性中获益，必须在编译过程中使用编译器开关 /Qopenmp。编译器将连接至适当的运行时支持库，运行时系统将管理实际并行化程度。并行扩展充分利用 OpenMP 3.0 运行时库，抽象出 OpenMP 编译指示和指令的使用，帮助程序员使用 C 或 C++ 语言更为自然地编写代码。并行化扩展和 OpenMP 结构间的映射关系如下表所示：

并行扩展
OpenMP

__par
#pragma omp parallel for

__critical
#pragma omp critical

__taskcomplete S1
#pragma omp parallel #pragma omp single { S1 }

__task S2
#pragma omp task { S2 }

这些关键词用作语句前缀。
示例 3：

- collapse source view plain copy to clipboard print ?

__par for (i = 0; i < size; i++)
setSize (new int[size], 0, i)
__taskcomplete {
__task sum(500, a, b, c);
__task sum(500, a+500, b+500, c+500)
)
if ( !found )
__critical item_count++;

__par for (i = 0; i < size; i++) 
setSize (new int[size], 0, i)

__taskcomplete {
__task sum(500, a, b, c);
  __task sum(500, a+500, b+500, c+500)
)

if ( !found )
__critical item_count++;

英特尔® 线程构建模块（英特尔® TBB）
英特尔® TBB 是一个含有丰富线程化方法的函数库，可帮助程序员在 C++ 编程中轻松添加并行性，充分发挥多核处理器性能的优势。它呈现了更高级别的任务级并行性，抽象出相关平台细节和线程化机制以帮助提高性能和可扩展性，同时还可平稳地融入至面向对象的泛型 C++ 框架中。英特尔 TBB 采用基于运行时的编程模型，为开发人员提供了基于类似 STL（标准模板库）的模板库的一般并行算法。
示例 4：

- collapse source view plain copy to clipboard print ?

#include "tbb/ParallelFor.h"
#include "tbb/BlockedRange2D.h"
void solve()
{
parallel_for (blocked_range<size_t>(0, size, 1), [](const blocked_range<int> &r)
{
for (int i = r.begin(); i != r.end(); ++i)
setQueen(new int[size], 0, (int)i);
}
}

#include "tbb/ParallelFor.h"
#include "tbb/BlockedRange2D.h"

void solve()
{
  parallel_for (blocked_range<size_t>(0, size, 1), [](const blocked_range<int> &r)
  {
    for (int i = r.begin(); i != r.end(); ++i)
      setQueen(new int[size], 0, (int)i);
  }
}

英特尔® TBB 任务调度程序可自动执行负载平衡操作，这样开发人员便无需亲自执行这项可能非常复杂的任务。英特尔 TBB 任务调度程序将编程流程分解为诸多小任务，并在各线程之间平均分配。
英特尔 C++ 编译器和英特尔 TBB 均支持新的C++0x lambda 函数，让 STL 与英特尔 TBB 算法的使用变得更加简单。若想使用英特尔的 lambda 表达式实施，程序员必须使用 /Qstd=3Dc++0X 编译器选项来编译代码。
Win32* 线程 API 和 Pthreads*
在某些情况下，开发人员更偏爱本地线程 API 的灵活性。与本文之前讨论的线程抽象方法相比，本地线程 API 的主要优势在于用户对线程的控制力度更高。然而，采用该方法实施指定解决方案所需要的代码数量更多，因为程序员必须手动执行所有单调乏味的线程实施任务，例如创建、调度、同步、本地存储、负载平衡和销毁等，而这些任务在其它方法中均可由运行时系统来处理。此外，程序员还必须自己确定可用内核的数量，这会影响到要创建的正确线程数。该任务执行起来可能非常复杂，尤其是对独立于平台的解决方案而言。
示例 5：

- collapse source view plain copy to clipboard print ?

void run_threaded_loop (int num_thr, size_t size, int _queens[])
{
HANDLE* threads = new HANDLE[num_thr];
thr_params* params = new thr_params[num_thr];
for (int i = 0; i < num_thr; ++i)
{
// Give each thread equal number of rows
params[i].start = i * (size / num_thr);
params[i].end = params[i].start + (size / num_thr);
params[i].queens = _queens;
// Pass argument-pointer to a different
// memory for each thread's parameter to avoid data races
threads[i] = CreateThread (NULL, 0, run_solve,
static_cast<void *> (&params[i]), 0, NULL);
}
// Join threads: wait until all threads are done
WaitForMultipleObjects (num_thr, threads, true, INFINITE);
// Free memory
delete[] params;
delete[] threads;
}

void run_threaded_loop (int num_thr, size_t size, int _queens[])
{
  HANDLE* threads = new HANDLE[num_thr];
  thr_params* params = new thr_params[num_thr];

  for (int i = 0; i < num_thr; ++i)
  {
    // Give each thread equal number of rows
    params[i].start = i * (size / num_thr);
    params[i].end = params[i].start + (size / num_thr);
    params[i].queens = _queens;
    // Pass argument-pointer to a different 
    // memory for each thread's parameter to avoid data races
    threads[i] = CreateThread (NULL, 0, run_solve, 
      static_cast<void *> (&params[i]), 0, NULL);
  }

  // Join threads: wait until all threads are done
  WaitForMultipleObjects (num_thr, threads, true, INFINITE);

  // Free memory
  delete[] params;
  delete[] threads;
}

线程库
在应用中添加并行性的另一种方法是使用线程库，如英特尔® 数学核心函数库（英特尔® MKL，并非英特尔 Parallel Composer 的组成部分）和英特尔® 高性能多媒体函数库（英特尔® IPP）。英特尔® MKL 使用 OpenMP 进行线程化处理，能够提供高度优化的线程化数学例程，可最大限度提升性能。若要使用线程化英特尔 MKL 函数，只需将 OMP_NUM_THREADS 环境变量设定为大于 1 的值即可。英特尔 MKL 带有内部阀值，用于自行判断执行并行还是串行计算，或者程序员还可以使用 OpenMP API 手动设置阀值，具体说是 omp_set_num_threads 函数。在线技术说明介绍了有关 MKL 并行性的更多详细信息（MKL 9.0 for Windows*，英特尔® MKL 10.0 threading）。
英特尔® IPP 是一个面向多核技术的扩展函数库，其中包含众多针对多媒体数据处理和通信应用高度优化的软件函数。英特尔 IPP 同样使用 OpenMP 进行多线程处理。在线技术说明提供了关于IPP 线程和 OpenMP 支持的更多信息。
英特尔® 编译器还提供了一项 STL valarray 实施，使用英特尔 IPP 为数学和超越运算提供数据并行性能。C++ valarray 模板类由支持高性能计算的数组运算组成。这些运算经过专门设计，可充分利用诸如矢量化等低级硬件功能。英特尔的 valarray 实施提供了多个面向英特尔 IPP 实现优化的 valarray 运算版本，采用优化的替换 valarray 头文件，且无需对源代码进行任何形式的更改。若要利用英特尔优化性能头文件改善 valarray 循环，请使用 /Quse-intel-optimized-headers 编译器选项。
自动并行化
自动并行化是英特尔 C++ 编译器的一项功能。在自动并行化模式下，编译器将自动检测程序中固有的并行性。该自动并行化工具可分析应用源代码中各个循环的数据流，并为可安全、高效地并行执行的循环生成多线程代码。如果存在数据依赖关系，可能需要重构循环，以实现循环的自动并行化。
在自动并行化模式中，所有并行化决策均由编译器制定，开发人员根本无法控制哪些循环将实现并行化。自动并行化还可与 OpenMP 结合使用，以实现更高的性能。结合使用 OpenMP=20 和自动并行化功能时，OpenMP 将用来对含 OpenMP 指令的循环进行并行化处理，自动并行化功能则将用来对非 OpenMP 循环进行并行化处理。自动并行化是通过 /Qparallel 编译器选项实现的。
示例 6：

- collapse source view plain copy to clipboard print ?

#define N 10000
float a[N], b[N], c[N];
void f1() {
for (int i = 1; i < N; i++)
c[i] = a[i] + b[i];
}
> icl /c /Qparallel par1.cpp
par1.cpp(5): (col. 4) remark: LOOP WAS AUTO-PARALLELIZED.

#define N 10000
float a[N], b[N], c[N];

void f1() {
  for (int i = 1; i < N; i++)
  c[i] = a[i] + b[i];
}

> icl /c /Qparallel par1.cpp
par1.cpp(5): (col. 4) remark: LOOP WAS AUTO-PARALLELIZED.

默认情况下，自动并行化工具将报告哪些循环已成功经过自动并行化。使用 /Qpar-report[n] 选项，其中 n 代表 0 和 3 之间的数值，自动并行化工具可报告已实现自动并行化以及无法进行自动并行化的循环的诊断信息。例如，/Qpar-report3 要求自动并行化工具报告成功和未成功实现自动并行化的循环的诊断信息，以及任何经验证或假设可能阻碍自动并行化进程的依赖关系。诊断信息可帮助开发人员重构循环，以成功实现自动并行化。
自动矢量化
矢量化是一项用来在英特尔® 处理器上优化循环性能的技巧。由矢量化技巧定义的并行性基于通过处理器SIMD硬件实现的矢量级并行性 (VLP)。英特尔 C++ 编译器中的自动矢量化工具可自动检测程序中可并行执行的低级别运算，然后转换顺序代码，在一次运算中处理 1、2、4、8 或最多 16 字节数据元素，在未来处理器中可扩展至 32 和 64 字节。循环必须是独立的，只有这样编译器才可对它们进行自动矢量化处理。自动矢量化功能可与其它线程级并行化技巧如自动并行化和 OpenMP 一起使用。大部分浮点应用和部分整数应用均可通过矢量化获得巨大优势。默认的矢量化级别是 /arch:SSE2，可为英特尔® SIMD 流指令扩展 2（英特尔® SSE2）生成代码。如果希望对默认目标之外的其它对象进行自动矢量化处理，请使用 /arch（如 /arch:SSE4.1）或 /Qx（如 /QxSSE4.2、QxHost）编译器选项。
在下图中，左侧展示了未实现矢量化的循环迭代串行执行情况，其中 SIMD 寄存器的下半部分并未得到利用。右侧的矢量化版本则显示，每个循环迭代均并行添加了四个 A、B 数组元素，充分利用了 SIMD 寄存器的全宽。

图 1. 实现矢量化和未实现矢量化的循环迭代。
示例 7：

- collapse source view plain copy to clipboard print ?

#define N 10000
float a[N], b[N], c[N];
void f1() {
for (int i = 1; i < N; i++)
c[i] = a[i] + b[i];
}
> icl /c /QxSSE4.2 par1.cpp
par1.cpp(5): (col. 4) remark: LOOP WAS VECTORIZED.

#define N 10000 
float a[N], b[N], c[N]; 

void f1() {
  for (int i = 1; i < N; i++)
  c[i] = a[i] + b[i];
}

> icl /c /QxSSE4.2 par1.cpp 
par1.cpp(5): (col. 4) remark: LOOP WAS VECTORIZED.

默认情况下，矢量化工具将报告实现矢量化的循环。使用 /Qvec-report[n] 选项，其中 n 代表 0 和 5 之间的数值，自动矢量化工具可报告已实现矢量化以及未实现矢量化的循环的诊断信息。例如，/Qvec-report5 选项要求矢量化工具报告未实现矢量化的循环以及其中的原因。诊断信息可帮助开发人员重构循环，以成功实现矢量化。

建议/使用指南

不同方法利弊权衡
不同的并行化方法可根据抽象、控制和简易性进行分类。英特尔 TBB 和 API 模型没有具体的编译器支持要求，但 OpenMP 却并非如此。使用 OpenMP 方法要求必须配备一个可识别 OpenMP 指令的编译器。基于 API 的模型要求程序员手动将当前的并行任务分配给各个线程。线程间不存在显式父子关系，所有线程全部属于同一级别。在这些模型中，程序员可以控制线程创建、管理和同步化流程的所有低级别因素。这一灵活性是基于数据库的线程化方法的主要优势。但不足之处在于，要获得该灵活性，必须对代码进行大幅度修改，另外还必须执行大量其它编码任务。当前的并行化任务必须压缩至可映射至线程的函数之中。另一个不足之处是，大多数线程 API 均使用鲜为人知的调用协定，并且仅接受一个变元。因此，对更适合 C 语言而不是面向对象的 C++ 语言的编程设计而言，程序员通常需要修改可能破坏编程设计抽象的函数原型和数据结构。
作为一种基于编译器的线程化方法，OpenMP 为基本线程库提供了一个高级别接口。借助 OpenMP，程序员可使用 OpenMP 指令向编译器描述并行性。该方法消除了显式线程化方法的大部分复杂性，因为编译器会处理相关细节。采用增量式并行化方法，应用的串行结构将始终完整无缺，无需对源代码进行大幅度的修改。非 OpenMP 编译器则完全忽视 OpenMP 指令，保持基本串行代码原封不动。
然而，使用 OpenMP 时，编程人员会丢失许多对线程的细微控制。此外，OpenMP 不支持程序员为线程设定优先级别，或执行基于事件的或进程间同步化操作。OpenMP 是一个 fork-join 线程化模型，线程间存在着显式主从关系。这些特征缩小了 OpenMP 的适用范围。总的来说，OpenMP 最适合表达数据并行性，而显式线程 API 方法则最适用于函数分解。OpenMP 以它的循环结构和 C 代码支持而闻名，但并没有为 C++ 编程带来任何具体优势。OpenMP 3.0 支持任务指派，增加了不规则结构支持，例如 while 循环和递归结构，进一步扩展了 OpenMP 的适用范围。但是，由于对 C++ 的支持级别极低，OpenMP 目前仍只会让人联想到普通的 C 和 FORTRAN 语言编程。
英特尔 TBB 支持使用 C++ 代码如 STL 进行一般性可扩展并行编程。它没有特殊的语言或编译器要求。如果程序员需要一种灵活、高级别的并行化方法，与某个抽象或面向对象的一般方法完美结合，那么英特尔 TBB 将是他们的理想选择。英特尔 TBB 使用面向通用并行迭代模式的模板，支持带嵌套式并行处理能力的可扩展数据并行编程。与 API 方法不同，程序员需要指定任务而不是线程，并且函数库可使用英特尔 TBB 运行时高效地将任务指派给不同线程。英特尔 TBB 调度程序更倾向于使用一种自动化分治法来进行调度。它可执行任务窃取操作，将任务从负载较高的内核中迁移至闲置内核。与 OpenMP x 相比，该方法在英特尔 TBB 中实施，支持由开发人员定义的不局限于自带类型的并行性结构。
下表对英特尔 Parallel Composer 中的不同线程化技巧进行了对比：

方法
描述
优势
劣势

显式线程 API
低级别 API 如 Win32* 线程 API 和用于低级别多线程编程的 Pthreads*

最高的控制力度和灵活性
不需要特定的编译器支持

编写、调试和维护代码的流程相对比较复杂；非常耗时
所有线程管理和同步操作均需由程序员来完成

OpenMP*
（通过 /Qopenmp 编译器选项实现）
OpenMP.org制定的一项规范，用于支持使用 API 和编译器指令在 C/C++ 和 Fortran 环境下进行共享内存并行编程

能够以相对较少的付出获得显著的性能提升
非常适合快速创建原型
可用于 C/C++ 和 Fortran 编程
支持使用编译器指令进行增量式并行处理
用户可以控制对哪些代码进行并行化处理
适用于多个平台的单一来源解决方案
串行和并行版本采用相同的代码库

用户对线程的控制力度不高，例如不能设置线程优先级或执行基于事件的或进程间同步化操作

英特尔并行扩展
（通过 /par 编译器选项实现）
英特尔® C++ 语言扩展（__tasktemplate、__task、__par、__critical）可简化并行编程

使用简单的句法表达并行性
在 C++ 应用方面，句法使用起来比 OpenMP 简单很多

要求特定编译器支持
不支持 Fortran
句法扩展至 OpenMP* 句法，因此具有和 OpenMP 相同的局限性

英特尔® 线程构建模块
英特尔 C++ 运行时库可提供并行算法和并行数据结构，消除单调乏味的线程实施工作，进而简化线程化流程，提高性能。

不需要特定的编译器支持
使用标准 C++ 代码如 STL
自动化的线程创建、管理和调度流程
允许在任务而不是线程级别表达并行性

主要适用于 C++ 编程
不支持 Fortran

自动并行化
（通过 /Qparallel 编译器选项实现）
英特尔® C++ 编译器的一项功能，用于自动对程序中没有循环传递相关性的循环进行并行处理

编译器自动为可并行执行的循环生成多线程代码
可与其它线程化技巧一起使用

只适用于编译器在静态状态下通过数据依赖关系和别名分析断定可实现并行处理的循环

自动矢量化
（通过 /arch:和 /Qx 选项实现）
在英特尔® 处理器上优化循环性能的技巧，将顺序指令转换为每次可运算多个数据元的SIMD指令

通过编译器实现自动化矢量级并行处理
可与其它线程化技巧一起使用

如果使用了面向特定处理器的选项，最终生成的代码可能无法在所有处理器上成功执行

“并行解决 N 皇后问题”是一篇动手练习培训文章，要求读者使用本文中讨论的各项并行化技巧制定一个并行解决方案来解决 N 皇后问题（八皇后迷题的更常见版本）。英特尔® C++ 编译器安装文件夹下的“Samples”文件夹中提供有更多的示例。

只有注册用户登录后才能发表评论。


相关文章: 英特尔® 多线程应用开发指南 [转]C/C++中动态链接库的创建和调用 [翻译]高效使用auto_ptr [转]从C++的Return Value Optimization (RVO)到C#的value type 关于线程同步的一些总结（用户模式/内核模式）如何编译TrueCrypt源码最大公约数问题 Emacs 快速指南 [知识库][转载]十年MFC经历认识的Microsoft技术(ZT)

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

MyMSDN

导航

统计

公告

常用链接

留言簿(10)

随笔分类

随笔档案

文章档案

相册

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜