![]() |
兴奋的草稿本 · 【创世理想乡】简单说一下为什么会卡和掉帧_单 ...· 3 月前 · |
![]() |
低调的沙发 · 江苏省信访局 重点工作 ...· 5 月前 · |
![]() |
小胡子的匕首 · 以政府有为推动市场有效 ...· 8 月前 · |
![]() |
独立的汉堡包 · FGO:剧透FGO第二部序章剧情,达芬奇要出 ...· 8 月前 · |
![]() |
呐喊的罐头 · 定价和许可- ...· 9 月前 · |
http://software.intel.com/zh-cn/articles/intel-guide-for-developing-multithreaded-applications/
Published On :
2010年02月25日 20:00
评级
目录:
应用线程化
本章节将涵盖并行性能领域的常见主题,同时也会偶尔涉及针对 API 的问题。
1-1 - 预测与测量并行性能
1-2 - 循环修改增强数据并行性能
1-3 - 粒度与并行性能
1-4 - 负载平衡与并行性能
1-5 - 避免或消除人为相依性有利于揭示并行性
1-6 - 任务取代线程工具
1-7 - 发掘有序数据流的数据并行性
同步处理
本章节将主要谈论采用哪些技术来降低同步处理对性能的负面影响。
2-1 - 管理锁争用:大、小关键代码段(Critical Section)
2-2 - 采用线程化 API 提供的同步例程替代手工编码
2-3 - 选择合适的同步原语最大限度减少开销
2-4 - 尽量使用非阻塞锁
内存管理
线程为内存管理开辟了另外一个不容忽视的新空间。本章节将涵盖对于多线程应用至关重要的内存问题。
3-1 - 避免线程之间发生堆冲突
3-2 - 采用线程本地存储减少同步开销
3-3 - 检测线程化应用的内存带宽饱和度
3-4 - 避免并识别线程间伪共享
编程工具
本章节将说明如何利用英特尔软件产品开发、调试和优化多线程应用。
4-1 - 借助英特尔® 编译器实现自动并行
4-2 - 英特尔® 数学核心函数库并行性
4-3 - 线程化与英特尔® IPP 高效多媒体函数库
4-4 - 使用英特尔® Parallel Inspector 查找基于 OpenMP* 的多线程代码中存在的竞态条件
4-5 - 采用英特尔® Parallel Amplifier 解决线程不平衡问题
4-6 - 采用英特尔® Parallel Composer 编写并行执行代码
2010 年 3 月 9 日,位于英特尔® 软件网络上的 并行编程社区 发布了一系列技术文章,旨在为软件开发人员提供应用线程化、同步处理、内存管理和编程工具领域的最新技术信息。我们期待看到您提出自己的想法和建议,希望您能参与 英特尔® 并行架构线程化论坛 的讨论,提出您的疑问。
1.1 动因
《英特尔® 多线程应用开发指南》的目标是为开发人员在基于英特尔® 架构的对称多处理器(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
评级
应用运行的速度越快,用户等待结果所需的时间越短。此外,执行时间的缩短使用户在可接受的时间内能够运行更大规模的数据集 (例如,更多的数据记录,更多的像素,或更大的物理模型)。串行与并行执行时间之间一个具体的比较指标便是
加速比 (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。
要使用斯塔夫森定律,必须知道并行执行期间串行时间的百分数,因此该公式的一个典型 用例是计算扩展的并行执行(数据集大小随着核心数量的增加而增加)与相同大小问题串行执行的加速比。从上面的示例可以看出 ,由于在阿姆达尔定律的公式中有关应用执行数据的严格使用,得出的估值比扩展的加速比公式得出的值悲观得多。
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月14日 20:00
评级
- collapse source view plain copy to clipboard print ?
#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,如果线程数量多余或少于五个,并行外部循环将会导致负载不平衡和闲置线程。如果阵列维数imx、jmx和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,由于最内层循环的计算都是独立的,因此在进行下一次迭代之前,线程没有必要在隐性障碍处等待。如果每次迭代的工作量各不相同,nowaitnowait 子句可使线程继续处理有用工作,而非闲置在隐性障碍处。
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]);
}
}
float *a, *b;一个阵列内的元素分配均是独立的,无需考虑相应 b 元素的符号。在 b 中的一个元素的每个任务均独立于其他任务,但却依赖于所需 a 元素的任务完成情况。因此,正如所写的一样,上述循环不能并行处理。
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;在第二次 parallel_for 调用执行之前,第一次 parallel_for 调用的返回可以确保了 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];
});
for (i = 0; i < list_len; i++)外层循环选择主阵列内层循环的起始索引和步长。内层循环通过已标记阵列的长度运行,将 ‘1’ 值存入所选择的元素中。如果标记的阵列足够大,内层循环的执行可将缓存行从早期的标记阵列元素中提取出来,进而满足随后的外层循环迭代需求。此行为将会导致串行和并行循环缓存命中率降低。
for (j = prime[i]; j < N; j += prime[i])
marked[j] = 1;
for (k = 0; k < N; k += CHUNK_SIZE)对于上述代码中最外层循环的每个迭代,i-循环中的全套迭代都将执行。必须从主阵列中所选择的元素中发现标记阵列块内的起始和结束指数(受外层循环控制)。这些计算已被封装在 f() 和 g() 例程之内。因此,同一标志块将会依次进行处理。并且,鉴于每个块的处理过程完全独立于其他块,因而外层迭代也可并行运行。
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;
}
#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 (kj = 0; kj < N*M; kj++) {
k = kj / M;
j = kj % M;
wn [k][j] = Work(w[k][j], k, j);
}
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];
d[j] = e[j] + f[j];
}
for (j = 5; j < N - 5; j++)
g[j] = d[j+1] + a[j+1];
#pragma omp parallel for if(N >= threshold)对于本示例代码,如果迭代次数超过了程序规定的临界值,那么循环只能并行执行。
for (i = 0; i < N; i++) { ... }
-----------------------------华丽分割线-----------------------------
Published On :
2010年02月13日 20:00
#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根据循环所执行的迭代次数在循环体内清除关键区域可以使迭代执行速度提升几个数量级。然而,运行上述代码可能仍然会产生一些并行开销。这些开销主要由工作量过小的任务导致。Schedule(dynamic,1)子句规定调度程序一次可向每条线程动态分配一次迭代(数据块)。每条辅助线程会处理一次迭代,接着返回调度程序,并同步获取另外一次迭代。通过增加数据块大小,我们可以增加分配给线程的每项任务的工作量,进而缩减每条线程与调度程序实现同步所需的时间。
- 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通过 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建议
多线程代码的并行性能取决于其粒度:如何在线程之间分配工作任务以及如何在这些线程之间展开通信。下面就通过调整粒度提高并行性能提供一些指导:
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月15日 20:00
图 1:四条线程之间的任务分配示例。
您也可以采用一种更合理的任务分配法,即线程 0 完成一项任务所需时间是 {10},线程 1 完成四项任务所需时间是 {4, 2, 1, 1},线程 2 完成三项任务所需时间是 {6, 1, 1},而线程 3 完成四项任务所需时间是 {4, 2, 2, 2}(如图 1(b)所示)。这样安排时间的优势是完成整个任务只需 10 个时间单元,四条线程中只有两条线程分别闲置了 2 个时间单元。
- collapse sourceview plaincopy to clipboardprint?
#pragma omp parallel for schedule(dynamic, 5)指数调度最初会向线程分配大型迭代数据块;分配给所需线程的迭代数量会随着未分配迭代集的减少而减少。由于分配模式不同,指数调度的开销往往少于动态调度。Schedule 子句的可选数据块参数会指明在指数调度下一个数据块中所分配的迭代最低数量。
for (i = 0; i < n; i++)
{
unknown_amount_of_work(i);
}
#pragma omp parallel for schedule(guided, 8)其中一个特例是迭代之间的工作负载单调递增或递减。例如,下三角形矩阵中每行元素数量会以正则表达式的形式增加。在此类情况下,通过静态调度设置一个相对较低的数据块尺寸(创建大量数据块/任务)可能有助于实现良好的负载平衡,同时还不会产生采用动态调度或指数调度所导致的开销。
for (i = 0; i < n; i++)
{
uneven_amount_of_work(i);
}
#pragma omp parallel for schedule(static, 4)如果调度策略不明显,采用运行时调度可以随意改变数据块尺寸和调度类型,而无需对程序进行重新编译。
for (i = 0; i < n; i++)
{
process_lower_triangular_row(i);
}
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月14日 20:00
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
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
ptr = &someArray[0]通过增加 ptr,代码可能会利用寄存器增量的快速运算方法,并避免使用计算所有迭代的 someArray[i] 的算法。在所有计算相互独立时,指针将会产生依赖性,它在每次迭代中的值将取决于其在之前迭代中的值。
for (i = 0; i < N; i++)
{
Compute (ptr);
ptr++;
}
// One time operation:用于模糊整个图像的现有代码可在执行 BlurBlock 时重复使用。利用 OpenMP 或显式线程来并行运算多个数据块有助于获得多线程优势,并保留最初优化的内核。
// Decompose the image into non-overlapping blocks.
blockList = Decompose (image, xRes, yRes)
foreach (block in blockList)
{
BlurBlock (block, imageIn, imageOut)
}
ptr = &someArray[0]注意,初始优化虽然比较小,但不可丢失。编译器通常会通过利用增量或其它快速运算对指数计算进行大范围的优化,从而带来串行和并行性能的双重优势。
for (i = 0; i < N; i++)
{
Compute (ptr[i]);
}
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月21日 20:00
任务是可以取代线程的小巧解决方案,借助它可提高启动和关机速度,实现更好的负载平衡,高效使用可用资源以及提高抽象化水平。英特尔® 线程构建模块(英特尔® TBB)和 OpenMP* 都是包括基于任务的编程模式。本文将简要介绍基于任务的编程,并会指导您应何时使用线程或任务。
本文是《英特尔® 多线程应用开发指南》系列的一部分,后者用于指导开发人员针对英特尔”® 平台开发高效的多线程应用。
对于多线程编程来说,直接使用本地线程包编程并不理想。这些本地线程包所创建的线程均为逻辑线程,它们通过操作系统映射到硬件的物理线程上。创建太少逻辑线程将会导致系统认购不足,进而造成部分可用硬件资源的浪费。创建太多的逻辑线程将会导致系统认购过多,这样一来操作系统需承担大笔开销,因为需要分段访问硬件资源。通过直接使用本地线程,开发人员负责将应用中的并行处理与硬件中的资源进行匹配。
执行这个平衡任务很困难,最普通的方法是创建一个能在整个应用生命周期中使用的线程池。通常需要为每个物理线程创建一个逻辑线程。然后,应用会动态地向线程池中的线程调度计算。使用线程池不仅有助于并行处理与硬件资源的匹配,同时也可避免因重复创建和销毁线程而产生的花费。
一些并行编程模式,例如 Intel TBB 和 OpenMP API 为开发人员提供了线程池优势,而且他们无需管理线程池。借助这些模式,开发人员用任务来表示应用中的逻辑并行处理,并且运行库会将这些任务调度至工作线程的内部池中。借助任务,开发人员可专注于应用的逻辑并行处理,而无需担心并行器的管理。同时,鉴于任务较线程更加轻便,因此能以更加精细的粒度来表达并行。
下面是使用任务的一个示例。函数fibTBB calculates the nth使用一个 TBBtask_group来计算第 n 个斐波纳契数。每次调用至 n >= 10 时,将会创建一个任务组,并且有两个任务运行。本示例中,描述每个任务的一个 lambda 表达式(拟定 C++0x 标准的一个特性)被传递给函数运行。这些调用产生了任务,从而可被线程池中的线程所执行。随后的调度函数将等待拦截,直至任务组的所有任务都已运行完毕。
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 sourceview plaincopy to clipboardprint?
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 sourceview plaincopy to clipboardprint?
// 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
许多计算密集型应用都涉及从有序输入数据到有序输出数据的复杂转换。例如声音与视频代码转换、无损数据压缩,以及地震数据处理。然而这些转换中使用的算法通常都是并行的,所以管理 I/O 顺序依赖性将面临挑战。本文介绍了一些此类挑战,并阐述了有关应对这些挑战,同时确保并行性能的策略。
本文是《英特尔® 多线程应用开发指南》系列的一部分,该系列介绍了针对英特尔® 平台开发高效多线程应用的指导原则。
考虑对视频压缩引擎进行线程化,从现场视频资源到磁盘或网络客户端,该引擎专门用于实时处理未压缩的视频。显而易见,满足此类应用的实时需求的关键便是充分利用多个处理器的性能优势。
MPEG2 和 MPEG4 等视频压缩标准专门针对在不可靠的链接上进行流处理而设计。因此,用户可以轻松地将一个视频流作为一系列更小的单独视频流来处理。通过以并行的方式处理这些更小的视频流,速度可得到显著的提升。通过多线程来获得此类并行性所带来的优势将面临以下挑战:
在其它情况下,例如无损数据压缩,通常能够提前确定输入数据的大小,并明确地将数据划分为单独的输入数据块。这里所述的方法同样适用于本例。
使用该方法可能是希望创建一个生产者和消费者链条,但该方法不具可扩展性,并且容易导致负载不平衡。相反,本文所采用的数据分解能够应对上述所有挑战,从而实现扩展性更高的设计。
此处所采取的方法是创建一组线程,每个线程都能够读取视频数据块,并对其进行编码,然后将其输出到重排序缓冲区。在完成对一个数据块的处理后,线程将返回读取并处理下一个视频数据块,以此类推。这种动态分配方法可以最大限度地减少发生负载不平衡的可能性。重排序缓冲区能够确保以正确的顺序写入编码的视频数据块,而不受其完成时的顺序的影响。
初始视频编码算法可能采取这种形式:
- collapse sourceview plaincopy to clipboardprint?
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)
首先要利用基于数据块的算法来替换读取和编码帧的结果,提出在一组线程内进行分解的问题。
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 帧。因此,该头被迁移到了数据块上方的循环中:
while (block = ReadNextBlock (inFile))
{
WriteHeader (outputBuffer)
while (frame = ReadNextFrame (block))
{
EncodeFrame (frame, outputBuffer)
}
FlushBuffer (outputBuffer, outFile)
}
借助这些变化,可以利用线程库(即,Pthreads 或 Win32 线程 API)或 OpenMP 引入并行性。
// 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 阐述了重新排序缓冲区的一个可能的状态。数据块 0 至 35 已经得到处理和写入,而数据块 37、38、39、40 和 42 已得到处理,正在排队等待写入。在线程完成对数据块 36 的处理后,它将写出数据块 36 至 40,使重新排序缓冲区处于如图 2 所示的状态。在数据块 41 完成处理之前,数据块 42 将仍然排列在队列中。
当然,您需要采取特定的预防措施,以确保该算法快速高效:
使用输出队列时,最终算法如下所示:
- collapse sourceview plaincopy to clipboardprint?
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,但还可提供灵活的高性能和无序并行处理方法。
在某些情况下,读取和写入数据的时间与处理数据所需的时间相当。本例中,以下方法可能更实用:
仔细选择数据块的大小和数量至关重要。通常,数量庞大的数据块可以提供最高的灵活性,从而减少负载不平衡的情况。另一方面,数量非常小的数据块可能带来不必要的锁定开销,甚至造成数据压缩算法效率的下降。
-----------------------------华丽分割线-----------------------------
第二章、同步处理
本章节将主要谈论采用哪些技术来降低同步处理对性能的负面影响。
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月21日 20:00
在多线程应用中,程序员会使用锁来同步线程进入可访问共享资源的代码区域的行为。受这些锁保护的代码区域被称为关键代码段(Critical Section)。如果关键代码段中已存在一条线程,那么其它任何线程都不可进入该代码段。由此可见,关键代码段采用序列化执行方式。本文介绍了关键代码段大小这一概念及其对性能的影响。关键代码段大小指线程在关键代码段中花费的时间长度。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇,旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。
关键代码段可在多条线程尝试访问共享资源时确保数据的完整性。它们还对自身内部的代码执行进行了序列化。线程应尽量缩短在关键代码段中花费的时间,进而减少其它线程在代码段外闲置等待获得锁的时间——这种状态被称之为“锁争用”。换句话说,关键代码段越小越好。然而,使用大量独立的小代码段会导致与获取和释放各个独立锁相关的系统开销。本文中描述的情景阐明了什么时候最适合使用大型或小型关键代码段。
代码示例 1 中的线程函数包含两个关键代码段。假设这两个关键代码段可保护不同数据,并且函数 DoFunc1 和 DoFunc2 中的工作是相互独立的。与此同时,假设执行上述两个更新函数中的任意一个所花费的时间都非常短。
代码示例 1:
- collapse sourceview plaincopy to clipboardprint?
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:
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:
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:
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 中的旋转次数调低,或者根本不采用旋转等待循环。
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月20日 20:00
应用编程人员有时候手工编写同步例程而非使用线程 API 提供的结构,以便减少同步开销,或提供不同于现有结构所提供的功能。遗憾的是,使用手工编写的同步例程可能对性能、性能调谐或多线程应用的调试造成负面影响。
本文是《英特尔® 多线程应用开指南》系列的一部分,后者用于指导开发人员针对英特尔 ® 平台开发高效的多线程应用。
通常,编程人员喜欢手工编写同步例程,以避免有时候由线程 API 提供的同步例程产生的相关开销。编程人员自己编写同步例程的另外一个原因是,线程 API 提供的功能与实际需求能不完全匹配。遗憾的是,与使用线程 API 例程相比,手工编写同步例程存在严重的缺点。
这种缺点之一是不能确保针对不同的硬件架构与操作系统均能提供出色的性能。下面是一个以 C 语言手工编写的自旋锁示例,可帮助说明这些问题:
- collapse sourceview plaincopy to clipboardprint?
#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 ,以便释放锁。
尽管乍一看该锁的实施似乎非常简单高效,但是它存在以下几个问题:
尽管解决所有这些问题的技术已存在,但它们通常使代码变得极其复杂,以至于难以验证其正确性。此外,很难做到代码调谐的同时保持可移植性。这些问题最好留给线程 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同步结构创建自定义同步结构,应避免在共享位置使用自旋循环,从而避免性能不可扩展。如果代码必须可移植,还应避免使用原子内存基元。线程性能和更正工具的准确性可能受到影响,因为这些工具可能无法推论出自定义同步结构的功能,即使构建该结构所使用的简单同步结构能够被正确识别。
John Mellor-Crummey,“共享内存多处理器上的可扩展同步算法”《美国计算机协会计算机系统汇刊》,第 9 卷,第一期,1991 年2 月,21-65 页。
《英特尔奔腾 4 和英特尔至强处理器优化参考手册》,第 7 章:“多处理器和超线程技术。”订购编号:248966-007。
James Reinders,《英特尔线程构建模块:装备 C++ 语言以支持多核处理器并行性》 O'Reilly Media, Inc.,Sebastopol, CA,2007 年
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月20日 20:00
如果线程在一个同步点等待,那么它们无法做有用功。然而,多线程程序中通常需要一定程度的同步化,明确的同步有时甚至优于数据复制或复杂的非阻塞调度算法,然而其本身也存在一些问题。当前市场上存在着大量同步技术,应用程序开发人员应选择一种适当的技术,从而最大限度地降低整体同步开销。
本文是《英特尔® 多线程应用开发指南》的一部分,该系列文章为开发面向英特尔? 平台的高效多线程应用提供了指导。
同步本身可构建序列执行,因此限制了并行能力,而且可能降低整体应用性能。事实上,当前只有很少的多线程程序能够完全避免同步。但幸运的是,我们可通过选择合适的结构来减少与同步有关的系统开销。本文将阐述一些可用的解决方案,针对每个解决方案提供示例代码,并列举出它们的主要优缺点。
Win32* 同步 API
Win32 API 提供了几种保护原子性(atomicity)的机制,本章节主要讨论其中的 3 种。一个增量语句(increment statement )(例如 = var++)说明了不同的结构。如果正在更新的变量在线程之间共享,那么加载→写入→存储指令必须为原子操作(即操作完成之前不能抢占指令序列。)下面的代码演示了如何使用这些 API。
- collapse sourceview plaincopy to clipboardprint?
#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 sourceview plaincopy to clipboardprint?
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 互锁函数时,请注意线程抢占问题。例如,当执行多线程时,下列代码段不会针对局部变量生成相同的值。
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 变量的情况发生,因为这种情况将会导致等待线程变为死锁。
Johnson M. Hart 《Win32 系统程序》(第二版)。Addison-Wesley 出版社,2001 年。
Jim Beveridge 和 Robert Wiener 《Win32 多线程应用》Addison-Wesley,1997年。
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月25日 20:00
通过执行由辅助线程实施提供的同步基元,线程可在共享资源上实现同步。这些基元例如互斥体 (mutex) 和信号量 (semaphore) 等只允许单条线程持有锁,其它线程则依据自身的超时机制自旋或阻塞。阻塞线程将导致成本昂贵的环境切换操作,而旋转等待则会浪费 CPU 执行资源(除非等待时间非常短)。另一方面,非阻塞系统调用则允许未成功获得锁的竞争线程原路返回,继续执行有意义的工作,进而避免浪费执行资源。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇,旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。
大多数线程实施,包括 Windows* 和 POSIX* 线程 API,均可提供阻塞和非阻塞两种线程同步基元。默认情况下通常使用阻塞基元。成功争得锁之后,线程便获得锁的控制权,进入关键代码段执行代码。但是,如果没有争得锁,系统便会执行环境切换,线程将被置于等待队列中。环境切换的成本非常高,需尽量避免,具体原因如下:
使用非阻塞系统调用有助减少性能损失。在这种情况下,应用线程如果没能成功锁定关键代码段,便会继续执行代码。这不但可以消除环境切换开销,同时也可避免线程在等待获得锁定权的过程中自旋。事实上,线程在重新尝试争夺锁定权之前会一直执行有用工作。
使用非阻塞线程调用来避免生成环境切换开销。非阻塞同步调用通常以关键字 try 开始。例如,Windows 线程实施提供的阻塞和非阻塞版本关键代码段同步基元如下所示:
如果线程在争夺锁的过程中成功获得关键代码段的所有权,TryEnterCriticalSection 调用将返回“True”Boolean 值。否则,它将返回“False”,线程便可以继续执行应用代码。
void EnterCriticalSection (LPCRITICAL_SECTION cs);
bool TryEnterCriticalSection (LPCRITICAL_SECTION cs);
非阻塞系统调用的典型使用示例如下:
- collapse sourceview plaincopy to clipboardprint?
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 调用的代码片断。
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
由于系统运行时库使用锁定的方式同步对堆的访问,因此从系统堆分配内存的操作成本非常高。对于锁的争用限制了多线程的性能优势要解决这个问题,可采用一个避免使用共享锁的分配战略,或使用第三方堆管理器。
本文是《英特尔® 多线程应用开发指南》系列的一部分,后者用于指导开发人员针对英特尔® 平台开发高效的多线程应用。
系统堆(为 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 来记录分配给线程的堆。
#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 sourceview plaincopy to clipboardprint?
// 有时可用alloca() 取代 malloc()
{
…
char *p = malloc( 256 );
// 使用分配的内存
process( p );
free( p );
…
}
// 如果内存在同一例程中分配和释放。
{
…
char *p = alloca( 256 );
// 使用分配的内存
process( p );
…
}
注意,微软不赞成使用 _alloca,而是推荐使用安全性更高的 _malloca 例程。该例程可根据请求的内存大小从堆栈或堆进行分配;因此,通过 _malloca 获得的内存应使用 _freea 释放。
按线程释放列表是另一项技巧。最初,使用 malloc 从系统堆中分配内存。当内存要正常释放时,它会被添加到一个按线程链接列表。如果该线程需要重新分配同样大小的内存,它可以立即在该列表中检索存储的分配信息,而不必回到系统堆。
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(切换)到磁盘。
Microsoft 开发人员网络:HeapAlloc、HeapCreate、HeapFree
Microsoft 开发人员网络: TlsAlloc、TlsGetValue、TlsSetValue
Microsoft 开发人员网络:_alloca、malloca、freea
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月28日 20:00
同步化通常是一个昂贵的操作,并且会限制一个多线程程序的性能。使用线程局部数据结构来代替由线程共享的数据结构可在某些情况下减少同步化,使一个程序运行得更快。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇,旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。
当数据结构由一组线程共享,并且至少有一个线程写入其中时,有时需要对线程进行同步化来确保所有线程均始终能看到一致的共享数据。这种情况下,典型的线程同步化访问机制是由一个线程获取锁,读取或写入共享数据结构,然后解锁。
所有形式的锁都有一定的开销以维持锁数据结构,并且采用了可减慢现代处理器速度的原子结构。同步化也会减慢程序运行速度,因为其消除了同步代码中的并行执行,形成了一系列执行瓶颈。因此,当同步化在一个时延敏感的代码段上发生时,代码性能将会受到影响。
如果该程序可被重新写入并使用线程局部存储而非共享数据结构,那么同步化可以从多线程、时延敏感代码段中消除。如果代码的属性能让共享数据访问的实时定序变得不再重要,那么消除同步化是完全可能的。如果在不频繁、非时延敏感代码段间,安全地推迟定序的执行,即使访问定序重要,也可以消除同步化。
思考一下,例如,使用一个变量来统计发生在几个线程上的事件。下面是用 OpenMP* 编写这样一个程序的一种方法:
- collapse sourceview plaincopy to clipboardprint?
int count=0;
#pragma omp parallel shared(count)
{
. . .
if (event_happened) {
#pragma omp atomic
count++;
}
. . .
}
每次发生事件时,该程序都需要付出代价,因为只有实施同步化才能确保一次只统计一个线程增量。每个事件都会引发同步化。消除同步化可以加快程序运行。其中一种方法是让每个线程在并行区域统计其自身的事件,然后再合计事件数量。下面的编程中使用了该技术:
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 来指定线程局部数据,编程者必须创建一个线程局部数据钥匙,然后通过这个钥匙来访问数据。例如:
#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 sourceview plaincopy to clipboardprint?
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 中的临界区。随后,来自各个线程私有缓冲区的条目将根据时间值在该程序的一个非时延敏感段内合并。
请务必仔细权衡使用该技术的利弊。此项技术不能消除同步化需求,它仅能将同步化从代码的一个时延敏感段迁移至该代码的一个非时延敏感段内。
David R. Butenhof,《POSIX线程编程POSIX线程编程》,Addison-Wesley,1997年。
Johnson M. Hart,《Win32 系统编程》 (第二版), Addison-Wesley, 2001年。
Jim Beveridge 和 Robert Weiner,《Win32 多线程应用》, Addison-Wesley,1997年。
-----------------------------华丽分割线-----------------------------
Published On :
2010年02月24日 20:00
内存子系统组件在很大程度上影响着应用的性能特征。现在,随着越来越多的线程和进程共享有限的高速缓存容量和内存带宽等资源,线程化应用的可扩展性受到了极大限制。内存密集型线程化应用在运行多个线程时可能会出现内存带宽饱和的问题。在这种情况下,线程化应用将无法像预期一样扩展,性能也可能有所下降。本文介绍了在线程化应用中检测内存带宽饱和度的技巧。
本文是《英特尔® 多线程应用开发指南》系列文章中的一篇,旨在为开发人员开发适用于英特尔® 平台的高效多线程应用提供指导。
鉴于当前的处理器集成有更多的核心和高速缓存,它们与内存子系统组件相比频率更高,速度更快。每芯片上内核数的不断增加为高速缓存容量和内存带宽带来了巨大的压力。最终,最大限度提高每枚内核对可用高速缓存和内存带宽的利用率成为开发向前扩展应用的根本。如果系统无法足够迅速地将主内存中的数据传输至内核,那么内核在等待数据时便会处于闲置状态。计算过程中的闲置内核是对资源的浪费,将导致总计算执行时间延长,浪费多核心配置的部分优势。
当前基于 Nehalem 架构的英特尔® 处理器从传统的前端总线 (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 性能事件可用来估算内存带宽。
对于采用英特尔酷睿 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 测量的内存带宽大致估算指定系统的可用内存带宽。
如果应用在添加了更多线程时无法进行扩展以充分利用现有内核,并且英特尔线程档案器没有如上所述显示任何应用层面的线程问题,那么以下三步操作可帮助用户判断某具体应用的可用内存带宽是否已达到饱和:
英特尔® 酷睿™ i7 处理器和英特尔® 至强® 5500 系列处理器被称为带“非内核”部件。“非内核”是处理器中位于所有其它独立内核外部的组成部分。例如英特尔® 酷睿™ i7 处理器拥有四枚共享一个三级高速缓存和一个内存接口的内核。其中,三级高速缓存和内存接口便视作非内核部分(参见图 4)。
VTune 分析器和 PTU 均不支持由处理器非内核部分触发的事件采样行为,必须使用其它方法测量内存带宽。用于测量内存带宽的相关性能事件并不是像常见 VTune 分析器或 PTU 模式那样使用 EBS 功能进行采样,而是使用基于时间的采样功能进行计算。这测量的是指定时间范围内整个系统的内存带宽,而无法估算具体功能、进程和模块的带宽使用情况。
上文给出的公式可用来测量英特尔酷睿 2 架构系统上任何应用、模块或函数的内存带宽使用情况,但同样具备非内核部件的基于酷睿 2 的英特尔至强多路处理器除外。在 Nehalem 架构系统上测量内存带宽的基本公式如下:
内存带宽 = 1.0e-9 * (UNC_IMC_NORMAL_READS.ANY+UNC_IMC_WRITES.FULL.ANY)*64 / (挂钟时间,以秒计)
如何使用英特尔® VTune™ 性能分析器测量英特尔® 酷睿™ i7 或英特尔® 至强® 5500 系列处理器平台上的内存带宽?
-----------------------------华丽分割线-----------------------------
Published On :
2010年02月18日 20:00
在对称多处理器系统中,每个处理器均有一个本地高速缓存。内存系统必须保证高速缓存的一致性。当不同处理器上的线程修改驻留在同一高速缓存行中的变量时就会发生共享错误,结果导致高速缓存行无效,并强制执行更新,进而影响系统性能。本文介绍了检测和更正错误共享的方法。
本文是《英特尔® 多线程应用开发指南》系列的一部分,后者用于指导开发人员针对英特尔®平台开发高效的多线程应用。
错误共享是 SMP 系统上的一种常见性能问题。在SMP系统中,每个处理器均有一个高速缓存。如果图1所示,当不同处理器上的线程修改驻留在同一高速缓存行中的变量时就会发生这种问题,之所以被称为错误共享,是因为每个线程并非真正共享相同变量的访问权。访问同一变量或真正共享要求编程式同步结构,以确保有序的数据访问。
在下面的代码示例中以红色显示的源代码行引起错误共享:
- collapse sourceview plaincopy to clipboardprint?
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字节边界)。如果该数组是动态分配的,可以增加分配大小,并调整指针以便与高速缓存行边界对齐。
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;
};
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
- collapse sourceview plaincopy to clipboardprint?
PROGRAM TEST数据流分析确认该循环不包含数据相关性。编译器生成的代码在运行时尽可能在线程内平均划分迭代。线程数默认为处理器核心的总数(如果支持英特尔®超线程技术,该数值可能大于物理核心的总数),但是可以通过 OMP_NUM_THREADS 环境变量单独设置。面向特定循环的并行加速取决于工作负载数量、线程之间的负载平衡以及线程创建和同步的开销等,但是相对于使用的线程数,通常低于线性加速的数值。对于整个程序,加速取决于并行与串行计算的比率(参考任意针对阿姆达尔定律的并行计算的教科书)。
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
test.f90(6) : (col. 0) remark: LOOP WAS AUTO-PARALLELIZED如下例所示,编译器还可以报告哪些循环不能并行化以及相应的原因。
serial loop: line 6下面的例子对此进行了阐述:
flow data dependence from line 7 to line 8, due to "c"
void add (int k, float *a, float *b)编译命令 'icl -c -Qparallel -Qpar-report3 add.cpp' 可生成下列信息:
{
for (int i = 1; i < 10000; i++)
a[i] = a[i+k] + b[i];
}
procedure: add对于 k 是否等于 -1 的例子,由于编译器不知道 k 的值,因此它必须假设迭代之间相互依赖。不过,由于对应用的了解,编程人员可能知道该值(例如 k 总是大于 10000),并可通过插入下面的编译指令忽略编译器:
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.
void add (int k, float *a, float *b)此信息表明该循环得到并行化。
{
#pragma parallel
for (int i = 1; i < 10000; i++)
a[i] = a[i+k] + b[i];
}
procedure: add但是,编程人员调用此函数时,K 的值必须大于 10000,以避免可能的错误结果。
test.c(6): (col. 1) remark: LOOP WAS AUTO-PARALLELIZED.
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月10日 20:00
线性代数
用于包括有限元素分析工程设计代码和现代动画在内的各种应用。
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. BLAS 矩阵乘法函数的性能与可扩展性。
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月11日 20:00
KMP_AFFINITY=compact对于在同一块芯片上配备两枚以上内核的处理器,您可以不用设置环境变量即可自动满足所需条件。但在那些拥有两块以上芯片的系统(如英特尔® 奔腾® D 处理器或多插座主板)上,为每块芯片提供支持的高速缓存并未实现共享,因而如果不设置上述 OpenMP 环境变量可能会显著降低该系列多线程英特尔® IPP 基元的性能。
-----------------------------华丽分割线-----------------------------
Published On :
2010年01月10日 20:00
double x, pi, sum = 0.0;仔细观察循环可以发现,上例中使用了“工作共享”。“工作共享”是 OpenMP 中使用的一个一般术语,主要用于描述线程间工作的分配情况。如上例所示,当工作共享用于 for 结构时,循环迭代会在多个线程间进行分配,以便每个循环迭代只执行一次,并与一个以上的线程并行执行。OpenMP 完全可以自行决定创建的线程数量,以及如何以最佳方式创建、同步和毁坏线程。
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;
图 1. 英特尔 Parallel Inspector 中的问题集概述
如欲深入调查问题根源,英特尔 Parallel Inspector 可借助函数调用堆栈和 reach filtering(范围筛选)工具提供详细的错误信息。快速参考源代码有助轻松判断检测到错误的代码范围。如图 2 所示,“Sources”(源代码)选项卡显示了详细的两部分源代码窗口,反映了不同线程到共享变量的访问情况,其中包括详细信息,双击可导航至本地源代码。
图 2. 英特尔 Parallel Inspector 中的源代码视图
在英特尔 Parallel Inspector 的帮助下获得错误报告并确定问题根源后,开发人员便可以开始考虑采用什么方法解决问题。下文介绍了在并行 OpenMP 循环中避免出现数据争用现象的一般考虑事项,以及关于如何修复被检查代码中所存在问题的有效建议。
管理共享数据和私有数据
几乎每个有用的循环都会读取或写入内存,所以程序员必须告知编译器哪部分内存应在线程间共享,哪部分应保持私有状态。一旦某部分内存确定为共享内存,所有线程都将访问该同一内存位置。而当内存确定为私有时,每条线程都将获得一份用于私有访问的单独变量副本。当循环结束时,这些私有副本将被销毁。在默认情况下,除了私有循环变量外,所有变量均共享。内存将通过以下两种方式宣告私有:
- collapse sourceview plaincopy to clipboardprint?
#pragma omp parallel for private(x)关键代码段(Critical Section)
#pragma omp critical全局或未命名的关键代码段未必能够提高性能,因为每条线程都必须有效竞争相同的全局代码段。为此,OpenMP 对关键代码段进行了命名。命名的关键代码段可支持更细化的同步,确保只有需要在某具体代码段上被阻隔的线程才会被阻隔。下面的范例即依此对以上范例的编码进行了改进。
sum = sum + 4.0 / (1.0 + x * x);
#pragma omp critical(sumvalue)通过为关键代码段命名,应用可以拥有多个关键代码段,线程也可一次进入多个关键代码段。值得注意的是,进入嵌套的关键代码段有可能导致死锁,这一点即使是 OpenMP 也检测不出来。使用多个关键代码段时,要格外注意检查可能隐藏在子程序中的关键代码段。
sum = sum + 4.0 / (1.0 + x * x);
a[i] += x; // may be interrupted half-complete虽然单独汇编指令的执行绝不会被打断,但是高级语言(如 C/C++)的语句却会被翻译为多条汇编指令,因此有可能被打断。在上例中,a[i] 的值可能会在读值、添加变量 x 和将值写回内存等汇编语句之间有所变化。但是,下面的 OpenMP 结构却能确保语句自动执行,不存在被打断的可能性。
#pragma omp atomic如果操作系统具备相关特性和硬件能力,那么 OpenMP 将选择最有效的方法来执行语句。然而,原子操作可被视作与加/减、乘/除等相同的简单基本操作,带有赋值运算符,且运算过程中只有两个表达式。如此看来,原子操作可能无法有效保护示例中的 sum 变量。
a[i] += x; // never interrupted
#pragma omp parallel for private(x) reduction(+:sum)实际上,OpenMP 可为每条线程提供变量 sum 的私有副本。当线程退出时,它会将值加在一起,并将结果放在变量的一个全局副本中。
for (i = 0; i < num_steps; i++)
{
x = (i + 0.5) * step;
sum = sum + 4.0 / (1.0 + x * x);
}
-----------------------------华丽分割线-----------------------------
Published On :
2010年02月23日 20:00
for (i = 0; i < NUM_THREADS; i++)下面给出的例程中,每个线程均并行执行。在computePot 例程中,每个线程均使用由线程的分配标识号索引的存储边界,以校准所用质点的起始和终止范围。在每个线程将其迭代空间(开始与结束值)初始化后,它开始计算质点的势能。
{
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;
}
void computePot (int tid) {热点分析用于找出应用中的热点,从而帮助确定适合的函数。在基于 英特尔® 酷睿2 4核处理器的单插槽系统上,该应用运行所消耗的总时间大约为15.4秒。热点分析表明,computePot 例程为主要热点,消耗了大量 CPU 时间(23.331秒)。对 computePot 函数的深入分析揭示出该热点(图 1 )的主要促成因素。
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;
}
图 1. 热点分析的源代码视图
并发性分析结果显示,相同例程的 CPU 利用率较差(图 2),应用程序平均使用 2.28 个核。主要热点并没有利用全部的可用核心;CPU 的利用率大部分时间或者较差(仅使用一个核心)或者一般(使用 2-3 个核心)。接下来的问题是,是否存在一定的负载不平衡,导致 CPU 利用率较差。最简单的方法是选择函数-线程-自下而上树或是线程-函数-自下而上树作为新的粒度,如图 4 所示。
图 2. 并发性分析结果
图 3. 并发性结果摘要视图
并发分析时间值结果对应下列应用类型:
图 4. 并发分析结果显示函数->线程组
图 4 表明,并行执行这个例程的 4 个工作线程的工作量并不相同,因此可能导致负载不平衡和较差的 CPU 利用率。这种行为将阻止多线程应用的适当扩展。仔细观察源代码可以发现,主例程内的外部循环根据将在线程池内(起始边界 3D [0][TID],结束边界 3D [1][TID])创建的工作线程数量,静态划分质点迭代。这个例程内的内部循环使用外部索引作为退出条件。这样一来,外部循环使用的质点数量越多,内部循环执行迭代次数也就越多。因此,每对质点仅在势能计算中计算一次。这种静态分布明确分配了不同的计算量。
修复负载不平衡的一个办法是更加动态地向线程分配质点。例如,不再分配连续质点组(如原始版本中),每个线程均以线程识别号(tid)索引的质点而开始,因此能够计算所有其质点号与线程号不同的质点。例如,当运行两个线程时,一个线程处理偶数质点,另一个线程处理奇数质点。
- collapse sourceview plaincopy to clipboardprint?
void computePot(int tid) {此次更改之后分析应用并发性,显示得出热点函数现在充分利用所有可用核心(图5)。
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. 更改之后的并发分析结果
概要窗格(图 6)提供了更改结果和影响的快速查看。耗时从大约 15. 4 秒减少至 9.0 秒,CPU 平均利用率从 2.28 增长至 3.9.通过让工作线程执行平等的计算量,速度提高了 1.7 倍,用时减少了大约 41.5%。
图 6. 负载平衡版本概要视图
概要和并行结果表示,应用程序的新版本几乎使用了所有可用核心,并且串行代码段(较差使用率)和未充分使用段均已消失。
-----------------------------华丽分割线-----------------------------
指令
描述
#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 sourceview plaincopy to clipboardprint?
void sp_1a(float a[], float b[], int n) {/Qopenmp-report[n] 编译器选项可用来控制 OpenmMP 并行化工具的诊断消息级别,其中 n 是 0 和 2 之间的一个数值。若想使用该选项,程序员必须首先指定 /Qopenmp 选项。如果没有为 n 指定具体值,选项将采用默认值 /Qopenmp-report1,此时的诊断消息将显示成功实现并行化的循环、区域和代码段。
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.
#pragma omp parallel面向并行化的英特尔® C++ 编译器语言扩展
#pragma omp single
{
for(int i = 0; i < size; i++)
{
#pragma omp task
setQueen (new int[size], 0, i, myid);
}
}
并行扩展
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 sourceview plaincopy to clipboardprint?
__par for (i = 0; i < size; i++)英特尔® 线程构建模块(英特尔® TBB)
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++;
#include "tbb/ParallelFor.h"英特尔® TBB 任务调度程序可自动执行负载平衡操作,这样开发人员便无需亲自执行这项可能非常复杂的任务。英特尔 TBB 任务调度程序将编程流程分解为诸多小任务,并在各线程之间平均分配。
#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);
}
}
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 *> (¶ms[i]), 0, NULL);
}
// Join threads: wait until all threads are done
WaitForMultipleObjects (num_thr, threads, true, INFINITE);
// Free memory
delete[] params;
delete[] threads;
}
#define N 10000默认情况下,自动并行化工具将报告哪些循环已成功经过自动并行化。使用 /Qpar-report[n] 选项,其中 n 代表 0 和 3 之间的数值,自动并行化工具可报告已实现自动并行化以及无法进行自动并行化的循环的诊断信息。例如,/Qpar-report3 要求自动并行化工具报告成功和未成功实现自动并行化的循环的诊断信息,以及任何经验证或假设可能阻碍自动并行化进程的依赖关系。诊断信息可帮助开发人员重构循环,以成功实现自动并行化。
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默认情况下,矢量化工具将报告实现矢量化的循环。使用 /Qvec-report[n] 选项,其中 n 代表 0 和 5 之间的数值,自动矢量化工具可报告已实现矢量化以及未实现矢量化的循环的诊断信息。例如,/Qvec-report5 选项要求矢量化工具报告未实现矢量化的循环以及其中的原因。诊断信息可帮助开发人员重构循环,以成功实现矢量化。
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.
方法
描述
优势
劣势
显式线程 API
低级别 API 如 Win32* 线程 API 和用于低级别多线程编程的 Pthreads*
OpenMP*
(通过 /Qopenmp 编译器选项实现)
OpenMP.org制定的一项规范,用于支持使用 API 和编译器指令在 C/C++ 和 Fortran 环境下进行共享内存并行编程
英特尔并行扩展
(通过 /par 编译器选项实现)
英特尔® C++ 语言扩展(__tasktemplate、__task、__par、__critical)可简化并行编程
英特尔® 线程构建模块
英特尔 C++ 运行时库可提供并行算法和并行数据结构,消除单调乏味的线程实施工作,进而简化线程化流程,提高性能。
自动并行化
(通过 /Qparallel 编译器选项实现)
英特尔® C++ 编译器的一项功能,用于自动对程序中没有循环传递相关性的循环进行并行处理
自动矢量化
(通过 /arch:和 /Qx 选项实现)
在英特尔® 处理器上优化循环性能的技巧,将顺序指令转换为每次可运算多个数据元的SIMD指令
“并行解决 N 皇后问题”是一篇动手练习培训文章,要求读者使用本文中讨论的各项并行化技巧制定一个并行解决方案来解决 N 皇后问题(八皇后迷题的更常见版本)。英特尔® C++ 编译器安装文件夹下的“Samples”文件夹中提供有更多的示例。
-----------------------------华丽分割线-----------------------------
2010 年 3 月 9 日,位于英特尔® 软件网络上的并行编程社区发布了一系列技术文章,旨在为软件开发人员提供应用线程化、同步处理、内存管理和编程工具领域的最新技术信息。我们期待看到您提出自己的想法和建议,希望您能参与英特尔® 并行架构线程化论坛的讨论,提出您的疑问。
1.1 动因
《英特尔® 多线程应用开发指南》的目标是为开发人员在基于英特尔® 架构的对称多处理器(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 撰写了一篇与《粒度与并行性能》有关的文章《吹雪的艺术》。
-----------------------------华丽分割线-----------------------------
整理于2010/09/05 by Volnet。 posted on 2010-09-05 02:20 volnet 阅读(3430) 评论(0) 编辑 收藏 引用 所属分类: 知识库(KnowledgeLibrary) 、C/C++