ACM通信
传统编程能够弥合并行计算应用程序的忍者性能差距吗?
信贷:Softpedia
当前的处理器趋势是将更多的核心与更广泛的单指令多数据(SIMD)单元集成，以及更深入和复杂的内存层次结构，这使得从应用程序中提取性能越来越具有挑战性。有些人认为传统的编程方法不适用于这些现代处理器，因此必须设计出全新的语言。在本文中，我们质疑这种想法，并提供证据支持传统编程方法，以及多核处理器和即将到来的多核架构在提供显著的加速和接近最优性能的常用并行计算工作负载方面的性能与编程效率。
我们首先量化了"忍者的差距，这是在不知道并行性(通常是串行的)的C/ c++代码和现代多/多核处理器上的最佳优化代码之间的性能差距。使用一组具有代表性的吞吐量计算基准测试，我们表明存在一个平均值忍者的差距6核Intel®酷睿i7 X980 Westmere CPU的24倍(最高可达53X)，如果不解决这个问题，这个差距将不可避免地扩大。我们展示了一组著名的算法变化，加上现代编译器技术的进步，如何将Ninja的差距缩小到平均1.3倍。与生成Ninja代码所需的大量工作相比，这些更改通常只需要很少的编程工作。我们展示了同样令人鼓舞的结果，即将推出的Intel®Xeon Phi架构具有更多的核心和更广泛的SIMD。因此，我们证明了我们可以控制忍者差距的增长，并在未来的架构中提供更稳定和可预测的性能增长，这提供了强有力的证据，表明不需要彻底改变语言。
1.简介
以前，跨处理器代的性能扩展依赖于增加时钟频率。程序员可以利用这一趋势，并且不必为提高代码性能而对代码进行重大更改。然而，时钟频率的调整已经触及了电源墙，16程序员的免费午餐结束了。
最近提高处理器性能的技术关注于将更多的核心与更广泛的单指令多数据(SIMD)单元集成，同时使内存层次结构更深入、更复杂。虽然最近处理器上的峰值计算和内存带宽一直在增加，但从这些平台上提取性能变得越来越具有挑战性。这导致了一种情况，即只有少数专业程序员(“忍者程序员”)能够利用现代多/多核处理器的全部功能，而普通程序员只能获得这种性能的一小部分。我们将术语“忍者间隙”定义为在现代多/多核处理器上编写的不知道并行性(通常是串行)的代码和最佳优化的代码之间的性能差距。
最近有许多出版物8，14，17，24通过优化特定于平台的并行实现，实际应用程序的性能提高了10100X，证明存在很大的忍者差距。这通常需要大量的编程工作，并且可能需要为每一代处理器重新优化。然而，这些论文并没有对这些优化所涉及的工作进行评论。在本文中，我们的目标是量化忍者差距的程度，分析差距的原因，并调查使用传统的C/ c++编程语言，通过较少的努力可以弥合多少差距。一个
我们首先将忍者差距进行量化。我们使用了一组真实世界的应用程序，这些应用程序需要高吞吐量(并且天生具有大量的并行性可以利用)。我们选择吞吐量应用程序是因为它们构成了越来越重要的一类应用程序7因为它们为开发架构资源提供了最多的机会，如果幼稚的代码没有利用这些资源，就会导致巨大的漏洞。我们在不同世代的各种平台上测量我们的基准性能:2核Conroe, 4核Nehalem, 6核Westmere, Intel®Xeon Phib， NVIDIA C2050 GPU。图1显示了我们在三种CPU平台上的基准测试差距:2.4 GHz的2核E6600 Conroe, 3.33 GHz的4核Core i7 975 Nehalem，以及3.33 GHz的6核Core i7 X980 Westmere。从图中可以看出，在简单的C/ c++代码和最近的6核Westmere CPU上的最佳优化代码之间有53X的差距。图中还显示，这种差距在不同处理器的世代之间一直在增加，在两核Conroe系统上的差距是520X(平均7X)，在Westmere系统上是2053X(平均25X)。尽管微架构的改进减少了执行各种优化的需求和影响。
接下来，我们分析造成这种巨大性能差距的原因。有很多原因可以解释为什么幼稚代码的性能很差。首先，代码可能不是并行的，编译器不会自动识别并行区域。这意味着初始代码不会使用不断增加的核心计数，而优化的代码会充分利用这一点。第二，代码可能没有向量化，因此无法充分利用不断增加的SIMD宽度。虽然自动向量化已经被研究了很长一段时间，但是仍然存在许多困难的问题，如依赖分析、内存别名分析和控制流分析，这些问题使得编译器无法向量化外部循环、带聚集的循环(不规则内存访问)，甚至是最内部的循环，其中依赖和别名分析都失败了。造成较大性能差距的第三个原因可能是代码受到内存带宽的限制，例如，如果代码没有被缓存层次阻塞，就可能发生这种情况，从而导致缓存丢失。
我们对Ninja程序员编写的代码的分析表明，这类程序员在使用线程技术(如pthreads)和低层次的向量化技巧(vectorization)以获得性能方面投入了大量精力。这可能导致非常复杂的代码，特别是当向不规则循环进行矢量化时。在这项工作中，我们展示了我们可以利用最新的编译器技术，以相对较低的程序员工作量实现代码的并行化和向量化。并行化可以通过在要并行化的循环上使用OpenMP pragmas来实现，并且程序员可以避免编写复杂的线程代码。对于没有依赖关系的简单循环，自动的循环并行化也是可能的——我们假设在这项工作中使用了pragmas。对于向量化，最近的编译器(如Intel®Composer XE 2011版本)引入了一个pragma，让程序员通过避免进行依赖和别名分析来强制循环向量化。这个版本的编译器还具有向量化外部级循环的能力，以及Intel®Cilk Plus功能11当它不是自动触发时，帮助程序员使用这个新功能。c这些特性允许程序员不用使用较低级的intrinsic和/或汇编代码，并极大地提高了性能。使用这些功能，我们展示了忍者差距降低到平均2.95X的Westmere．剩下的差距要么是代码中的带宽瓶颈造成的，要么是由于不规则的内存访问导致代码只能部分向量化。然而，随着SIMD宽度的增加和带宽计算比的降低，剩余的差距虽然相对较小，但在未来的架构中不可避免地会增加。
为了弥合剩余的差距，需要程序员的干预。当前的编译器不能在算法级别自动进行涉及内存布局更改的更改，这些更改必须由程序员手动执行。我们确定并建议三个关键的算法变化:阻塞对于缓存，带宽/SIMD友好数据布局在某些情况下，选择替代SIMD-friendly算法。一种重要的算法变化包括阻塞数据结构以适应缓存，从而减少内存带宽压力。另一类更改涉及到消除内存聚集/分散操作的使用。这种不规则的内存操作会增加延迟和带宽使用，并限制编译器向量化的范围。一种常见的数据布局更改是将以数组结构(AOS)表示写入的数据结构转换为数组结构(SOA)表示。这有助于防止跨数组元素访问结构的一个字段时聚集，并帮助编译器对遍历数组的循环进行向量化。最后，在某些情况下，由于循环迭代之间的背靠背依赖关系，代码无法向量化，在这些情况下，可能需要选择不同的simd友好算法。
执行算法更改确实需要程序员的努力和洞察力，我们期望并行编程方面的教育和培训将在使程序员开发更好的并行算法方面发挥重要作用。回报是很大的，我们显示在执行算法更改之后，我们有平均性能差距仅为1.3倍在最佳优化的代码和编译器生成的代码之间。此外，这项工作可以在不同的处理器世代之间摊销，也可以在不同的计算平台(如gpu)之间摊销。由于底层硬件倾向于增加内核，SIMD宽度和缓慢增加的带宽已经优化为，a小的和可预测的性能差距将在未来的架构中继续存在。我们通过重复实验来证明这一点英特尔®Xeon Phi Knights Corner协处理器架构，一个最近的基于86X的多核心平台。我们证明忍者的差距几乎是一样的(1.2倍)。事实上，硬件集合支持的增加使得至少一个基准测试的可编程性变得更容易。算法变化与现代编译器技术的结合是使程序员能够利用传统编程来驾驭并行处理趋势的重要一步。
2.基准描述
在我们的研究中，我们分析了最近提出的基准套件的计算和内存特性，2，3.，5然后选择一组具有代表性的基准吞吐量计算应用程序。吞吐量工作负载处理在给定时间内处理大量数据，并要求对所有处理的数据进行快速响应。这包括来自高性能计算、金融服务、图像处理、数据库等领域的工作负载。5吞吐量计算应用程序具有大量的数据级和线程级并行性，并已被确定为未来应用程序中最重要的类之一计算而且内存特性影响当前和未来的多/多核处理器的设计。它们还提供了利用架构资源的最大机会，如果幼稚的代码没有利用增加的计算资源，就会导致巨大的忍者间隙。我们制定了一组具有代表性的基准，如下所述涵盖广泛的应用领域吞吐量的计算。我们捕获了在吞吐量计算应用程序中花费大部分时间的关键计算内核。因此，在我们的基准中减少忍者差距也将转化为应用本身。
- NBody:NBody计算被用于许多科学应用，包括天体物理学和统计学习算法领域。1对于给定N体，基本的计算是O(N2)算法，该算法在物体上有两个循环，并计算和积累它们之间的成对互动。
- 投影:在CT数据的锥束重建中，后向投影是一种常用的核。13一组2D图像被“反向投影”到一个3D体量上，以构建密度值的网格。对于每一幅输入图像，将每个三维网格点投影到图像上，并对相邻2 × 2像素点的密度进行双线性插值和累积。
- 级模板:钢网计算被广泛应用于科学领域。8计算包括对空间输入的三维网格进行多次扫描，每次扫描将计算每个网格点及其相邻网格点的加权和，并将计算值存储到输出网格中。
- 点阵玻尔兹曼方法(LBM):LBM是一类能够模拟复杂流动问题的计算流体力学。25它模拟了粒子分布函数在三维晶格上在多个时间步上的演化。对于每个时间步，在每个网格点，所执行的计算包括网格点及其面(6)和边(12)邻居(也称为D3Q19)的方向密度值。
- 伦敦同业拆借利率(LIBOR)蒙特卡罗:LIBOR市场模型4用于为掉期交易组合定价。它模拟了一组远期利率为对数正态分布。典型的蒙特卡洛方法会为该分布生成随机样本，并使用大量独立路径计算导数价格。
- 复杂的一维卷积:它被广泛应用于图像处理、雷达跟踪等应用领域。它用一个大的复杂滤波器对复杂的一维图像进行一维卷积。
- BlackScholes:BlackScholes模型给出了期权价格演化的偏微分方程(PDE)。对于欧洲选项，PDE的解有一个封闭形式的表达式。20.这涉及到许多数学运算:指数、对数、平方根和除法运算的计算。
- TreeSearch:在商业数据库中，常用内存树结构索引搜索。14这个应用程序涉及到使用不同查询在树上的多个并行搜索，每个查询根据对每个树级别的节点值的比较结果跟踪树中的路径。
- 归并排序:MergeSort通常用于数据库等领域，6同时也为未来的结构选择提供了排序算法。22它对数组进行排序N元素使用日志N通过合并整个数组。
- 2D 5 × 5卷积:卷积是一种常用的图像滤波操作，用于处理模糊、浮雕等效果。15对于给定的2D图像和一个5 × 5空间滤波器，每个像素计算并存储一个5 × 5邻域像素的加权和，其中权值为滤波器中相应的值。
- 体绘制:体绘制是医学成像领域中常用的方法，24等。给定一个3D网格和一个2D图像位置，基准通过3D网格生成垂直于图像平面的射线，它积累颜色和不透明度，以计算图像每个像素的最终颜色。
忍者性能:表1提供每种基准测试的代表性数据集大小的详细信息。每一种都有一个对应的最佳性能代码，其性能数据已经被引用过d不同于我们研究中使用的平台。为了进行公平的比较，我们实现并积极优化(包括使用intrinsic /汇编代码)基准测试,并获得类似的性能到相应平台上最好的报告数字。然后在我们的平台上执行这段代码，以获得我们在本文中使用的相应的最佳优化性能数字。表1(第3列)显示最佳优化(忍者)的性能，适用于所有英特尔®酷睿i7 X980基准。对于论文的其余部分，Ninja Performance指的是性能数据通过在我们的平台上执行此代码获得。
3.弥合忍者之间的鸿沟
在本节中，我们将使用第2节中描述的每个基准，并尝试从使用较低的编程工作量编写简单的代码开始，弥合Ninja之间的差距。要获得详细的性能分析，请参阅我们的ISCA论文。23
平台:我们测量了3.3 GHz 6核Intel®酷睿i7 X980的性能(代号Westmere，峰值计算:158 GFlops，峰值带宽:30 GBps)。核心的特点是无序的超标量微架构，具有双向同步多线程(SMT)。它还拥有4宽SIMD单元，支持广泛的指令。每个核有一个单独的32 KB的L1和256 KB的L2缓存。核心共享一个12 MB的最后级缓存(LLC)。我们的系统有12 GB内存，运行SuSE Enterprise Linux (ver。11)。我们使用Intel®Composer XE 2011编译器。
方法:对于每个基准测试，我们试图首先通过利用指令和数据级的并行性来获得良好的单线程性能。为了利用数据级别的并行性，我们通过运行启用/禁用自动向量化(-no-vec编译器标志)的代码来衡量每个基准测试的SIMD可伸缩性。如果SIMD扩展没有接近峰值，我们将分析生成的代码以确定体系结构瓶颈。然后，我们通过添加OpenMP pragmas来并行化基准测试，并通过评估瓶颈来评估线程伸缩，从而获得线程级的并行性。最后，我们对算法进行了必要的修改，以克服瓶颈。
编译器语法使用:我们使用OpenMP来实现线程级并行，并使用自动矢量化或最近的技术，如作为Intel®Cilk Plus(以下简称数组表示法)一部分引入的数组表示法来实现数据并行。Tian等人提供了具体编译技术的细节。26我们添加到代码和命令行的编译器指令如下:
- ILP优化:我们使用# pragma展开指令在最内层循环之前，和# pragma unroll_and_jam外层循环外的原语。两者都可选地接受展开循环的次数。
- 在最内层循环级别向量化:如果自动向量化失败，程序员可以使用强制向量化# pragma simd。这是Cilk Plus最近推出的一个功能。11
- 在外环层向量化:可以通过两种不同的方式实现:(1)直接在外环层向量化;(2)Stripmine外环迭代并更改循环体中的每条语句，以对条带进行操作。在本研究中，我们使用了第二种数组表示法。
- 并行化:我们使用OpenMP# pragma omp并行化循环。我们通常在外层的for循环中使用#pragma omp parallel for构造。
- 快速数学:我们用-fimf-precision根据精度需求有选择地标记到我们的基准。
- Nbody:我们在拥有100万个身体(16 MB内存)的数据集上实现了Nbody。图2显示各种优化的分解。该代码由两个循环组成，循环遍历所有对。我们首先执行展开优化来改进ILP，这将带来1.4倍的好处。编译器可以很好地自动向量化代码，无需程序员干预，并提供3.7X SIMD缩放。我们获得了3.1X的并行伸缩性，这促使我们对算法进行优化，阻塞数据结构以适应L3缓存(一维阻塞，代码见章节4.1)。一旦阻塞完成，我们获得了额外的1.9倍线程伸缩性，编译代码和最佳优化代码之间的性能差距为1.1倍。
- 投影:我们将500张尺寸为2048 × 2048像素的图像反向投影到1024 × 1024 × 1024的3D网格上。反向投影每格点需要80次操作。映像(16 MB)和卷(4 GB)都太大了，无法驻留在缓存中。图2显示，我们得到的SIMD的缩放较差，从自动向量化1.2倍。此外，并行缩放只有1.8倍。这是因为代码是bandwidth-bound(1.6字节/失败)。我们在3D体积上执行阻塞以减少带宽(3 d阻塞在图2)．由于空间局部性，图像工作集相应减小。这导致代码变成的计算。然而，由于道集无法在CPU上进行矢量化，SIMD的缩放只提高了1.6倍(总共提高了1.8倍)。我们获得了额外的4.4倍线程缩放(总共7.9倍)，显示了SMT的好处。净性能是最佳优化代码的1.1倍。
- 级三维模板:应用程序在一个3D网格上迭代，每个点执行8次失败的计算。采用网格点大小为512 × 512 × 512的三维数据集。图2显示我们从自动向量化得到的SIMD比例很差，只有1.8X (带宽约束)．为了提高伸缩性，我们同时执行这两种操作空间而且时间阻止提高性能。17生成的代码执行以下操作四个时间步同步，并将DLP进一步提高1.7X(由于边界上的重复计算开销，净SIMD缩放比4X低3.1 x)。线程缩放进一步提高了2.5倍(总的是5.3倍)。净性能仅为最佳优化代码的10.3%以内。
- 点阵玻尔兹曼方法(LBM):计算模式类似于模板内核。我们使用了一个256 × 256 × 256的数据集。图2说明我们的初始代码(SPEC CPU2006)没有实现任何SIMD扩展和2.9X核心扩展。SIMD无法伸缩的原因是导致收集操作的AOS数据布局。为了提高性能，我们执行以下操作两个算法的变化。首先，我们对数据进行AOS到SOA的转换。最终的自动向量化代码将SIMD的可伸缩性提高到1.65X。其次，我们进行3.5D的阻塞。最终的代码进一步将SIMD的伸缩性提高了1.3倍，实现了2.2倍的净伸缩性。由此产生的线程缩放进一步增加了1.95X(总共5.7X)。然而，编译器生成了额外的溢出/填充指令，这导致了1.4倍的性能差距。
- 伦敦同业拆借利率(LIBOR):伦敦银行间拆放款利率4在蒙特卡洛模拟的所有路径上有一个外部环路，在单个路径上的正向速率上有一个内部环路。图3显示自动向量化的性能优势仅为1.5倍，因为当前编译器只尝试对内部循环进行向量化，它具有背靠背依赖关系，只能部分向量化。为了解决这个问题，我们执行了一个算法更改，将布局从AOS转换为SOA。我们使用数组标记技术来表示外循环向量化(代码在图7 b)．执行这些更改允许外部循环向量化，并提供额外的2.5X SIMD缩放(净3.8X)。性能类似于最佳优化的代码。
- 复杂的一维卷积:我们使用的图像有1280万个点，核大小为8 K。第一个小节图3展示了由编译器启用的展开所实现的性能，它导致1.4X的伸缩。自动矢量化只实现了1.1倍的缩放。实现的TLP为5.8X。为了提高SIMD性能，我们执行了一个重排的数据从AOS到SOA格式。因此，编译器生成了高效的SSE代码，性能进一步提高了2.9倍。我们的总体性能比优化后的数值低1.6倍(编译器无法阻塞内核权重)。
- BlackScholes:BlackScholes计算看涨期权，并将期权组合在一起。计算总次数为200次，带宽为36字节。图3展示了使用自动向量化的SIMD加速1.1倍。低伸缩性主要是由于AOS的布局，这导致了聚集操作。为了提高业绩，我们更改了数据布局从AOS到SOA。因此，自动向量器生成了SVML(简短的矢量数学库)代码，导致伸缩性增加了2.7X(总共是3.0X)。它的净性能是最佳代码的1.1倍。
- TreeSearch:二叉树以宽度优先的方式展开。自动矢量化实现了1.4倍的SIMD加速(图4一)．这是因为它同时操作4个查询，每个查询可能遍历不同的路径，从而产生一个收集操作。为了提高性能，我们执行了一个算法的改变，并一次遍历2个级别(类似于SIMD宽度阻塞14)．但是，编译器没有生成所描述的代码序列，导致1.55X Ninja的差距。
- 归并排序:我们的分析是对包含256 M个元素的输入数组进行排序。图4一显示我们从自动向量化得到1.2倍的缩放。这是为了合并而收集的操作四个对列表。并行扩展只有4.1倍，因为最后几个合并阶段受带宽限制。为了提高性能，我们执行以下操作两个算法的变化。首先，我们利用合并网络实现了列表的合并6(代码见章节4.1)。其次，为了减少带宽需求，我们一起进行多个合并阶段。结果代码的并行扩展速度进一步提高了1.9倍。最终的性能是最佳优化代码的1.3倍以内。
- 二维卷积:我们对一个2k × 2k的图像和一个5 × 5的核进行卷积。代码包含四个循环。图4 b结果表明，通过循环展开，我们获得了1.2 2x的收益。我们使用数组表示法实现了这两个内部循环。这启用了外部循环的矢量化，并将SIMD宽度缩放3.8X。线程级并行度为6.2倍。我们的净性能是最佳优化代码的1.3倍。
- 体绘制:所示图4 b，我们实现了8.7倍的张力腿放大(SMT为1.5倍)。就DLP而言，由于各种控制密集型语句，早期的编译器版本没有对代码进行向量化。但是，最近的编译器使用每个分支指令的掩码值对代码进行向量化，并使用适当的掩码执行每个分支的两个执行路径。忍者的表现只有1.3倍的差距。
简介:在本节中，我们分析了每个基准测试，并通过应用必要的算法更改和最新的编译器技术，将忍者差距缩小到1.11.6X以内。
4.分析和总结
在本节中，我们将介绍如何用程序员的低工作量来弥合忍者之间的差距。所采取的关键步骤是，首先执行一组著名的算法优化，以克服伸缩性瓶颈，其次使用最新的编译器技术进行向量化和并行化。现在，我们就每一步所取得的成果总结一下我们的发现。
4.1算法的改变
算法的改变确实需要程序员的努力和一些洞察力，但对于避免矢量化问题和带宽瓶颈是必不可少的。图5展示了由于我们下面描述的一组著名的算法优化而带来的性能改进。
AOS到SOA的转换:一种有助于防止向量化代码中聚集和分散的常见优化方法是将数据结构从数组结构(Array-Of-Structures, AOS)转换为数组结构(Structure-Of-Array, SOA)。在执行向量化时，每个字段的单独数组允许连续的内存访问。AOS结构需要聚集和散射，这可能会影响SIMD效率，并为内存访问带来额外的带宽和延迟。硬件聚集/分散机制的存在并不能消除这种转换的需要，聚集/分散访问通常需要比连续负载更高的带宽和延迟。包括gpu在内的各种体系结构都提倡这种转换。19图5在我们的基准测试中，AOS到SOA的转换平均帮助了1.4倍。
屏蔽:阻塞是一种众所周知的优化，它可以帮助避免许多应用程序中的带宽瓶颈。关键思想是通过确保数据在空间域(1-D、2-D或3-D)和时间域的多个使用中仍然保存在缓存中，从而利用应用程序中可用的固有数据重用。
就代码更改而言，阻塞包括循环分割和交换的组合。中的代码片段图6展示了一个阻塞NBody代码的例子。有两个循环(body1和body2)遍历所有主体。的原始代码在顶部，流通过内部循环中的整个body集，并且必须在每次迭代中从内存中加载body2值。的阻塞的代码通过将body2循环分割为一个以块，以及一个内部body22循环，对块内的元素进行迭代。此代码重用了一组块Body2值跨body1循环的多次迭代。如果块如果选择使这组值适合缓存，则内存通信量会受到块。按工作表现(图5)，我们实现了平均1.6倍的改进(LBM和7点模板高达4.3倍)。
SIMD-friendly算法:在某些情况下，由于循环迭代之间的背靠背依赖关系，或者由于代码中大量使用了聚集和分散，朴素的算法无法容易地向量化。这时可能需要一种对SIMD更友好的不同算法。图6 b在MergeSort中展示了一个例子。左边的代码显示的是传统算法，每次只合并两个元素，并写出最小值。由于数组递增操作，存在背靠背的依赖关系，因此代码不能向量化。右边的图显示了simd友好的合并网络的代码，6哪个合并了两个simd宽度的序列年代大小元素使用一个序列的最小，最大和交错操作。这段代码自动向量化每个高亮显示的行对应于一个SIMD指令。然而，这段代码确实需要进行更多的计算(通过log(S)的常数因子)，但对于4宽SIMD仍然可以产生2.3倍的增益。由于这些算法更改涉及到总计算量和simd友好性之间的权衡，因此必须决定是否使用它们这是程序员有意识的。
简介:使用著名的算法技术，我们得到平均的2.4倍性能在6-core Westmere。随着核心、SIMD宽度和计算带宽比的增加，算法变化带来的收益将进一步增加。
4.2编译器技术
一旦考虑到算法的变化，我们将展示利用最近编译器中出现的并行化和向量化技术在弥合Ninja差距方面的影响。
并行化。我们通常在最外层循环上使用OpenMP pragmas来并行执行基准测试。OpenMP提供了一种可移植的解决方案，它允许指定启动的线程数量、线程与核心的关系、指定线程私有/共享变量。由于吞吐量基准测试提供了重要的TLP(通常是外部for循环)，我们通常使用omp平行的编译指示。中的一个例子图7对于复杂一维卷积。使用SMT线程可以帮助隐藏代码中的延迟，因此我们有时可以在6核系统上获得超过6倍的伸缩性。
向量化。
上交所和AVX:图8展示了在Westmere上使用内循环和外循环自动向量化的好处，只要对算法进行适当的修改。我们还将其与手动最佳优化代码的SIMD扩展进行比较，并显示在AVX(8宽SIMD)上的扩展图8 b使用4核3.4 GHz Intel®酷睿i7-2600 K Sandybridge系统。我们使用相同的编译器，并且只将编译标志更改为-xAVX从-xSSE4.2。就性能而言，我们使用编译的代码平均获得2.75X SIMD缩放，这与使用最佳优化的代码获得2.9X缩放的比例相差不到10%。在8宽的AVX中，我们使用编译和最佳优化的代码获得4.9X和5.5X的缩放(同样非常接近)。
除了MergeSort、TreeSearch和BackProjection之外，我们对于最佳优化代码的整体SIMD扩展对于我们的大多数基准都是有益的。正如在4.1节中所解释的，我们在MergeSort和TreeSearch中执行了算法上的改变，但代价是执行更多的操作，导致比线性加速更低。由于代码中存在不可避免的聚集/散射，反向投影不会线性缩放。对于反向投影，这将SIMD缩放限制为SSE上的1.8X (AVX上的2.7X)。
内循环向量化:我们的大多数基准测试在代码的内部循环上向量化，要么使用编译器自动向量化，要么# pragma simd当依赖或内存别名分析失败时。这个pragma的添加是向编译器发出的指令，要求必须对循环进行向量化(并且这样做是安全的)。图7展示了一个使用此pragma的示例。内环矢量化的平均加速是SSE的2.2倍(AVX的3.6倍)。
外层循环向量化:向量化一个外环是一项挑战:需要针对多个环层分析归纳变量;而回路控制流，如零跳闸测试和退出条件，必须转换为条件/预测的多个向量元素的执行。数组表示法技术可以帮助程序员避免这些复杂情况，而无需对程序进行详细的更改。我们从LIBOR的外环向量化中获益，其中内环只能部分向量化。目前，我们使用数组表示法对外部(完全独立)循环进行向量化(图7 b)．修改标量代码，改变外循环索引以反映向量化，并并行计算多次迭代的结果。注意，程序员声明了大小数组年代(simd宽度)，和X[a: b表示访问bX元素，从index开始一个。通常可以直接将标量代码更改为数组符号代码。这一变化导致上交所的3.6倍(AVX的7.5倍)的高加速。
5.总结
图9显示了优化后的代码相对于修改算法前后编译器生成的代码的相对性能。我们假设程序员已经努力引入前面章节中描述的pragmas和编译器指令。有一个3.5倍的平均差距在编译的代码和最佳优化的代码之间在我们执行算法更改之前。这一差距主要是因为编译的代码被内存带宽或较低的SIMD效率所绑定。在我们执行4.1节中描述的算法更改之后，这个差距缩小到平均1.4X。唯一有明显差距的基准测试是TreeSearch，其中编译器使用gather对外部循环进行矢量化。其余的显示了1.11.4X Ninja漏洞，主要是由于额外的溢出/填充指令产生的额外指令，加载/存储这些都是编译器依赖启发性的困难问题。
多核架构的影响:为了在多核平台上测试忍者间隙，我们在Intel®Xeon Phi“Knights Corner”协处理器(KNC)上进行了相同的实验，该处理器在单个芯片上有60/61个核，每个核都具有有序的微架构，带有4路SMT和512位SIMD单元。
图10显示了忍者在KNC和Westmere的表现差距。KNC的忍者平均差距只有1.2倍，这与cpu几乎相同(略小)。这两种性能差距的主要区别来自于TreeSearch，它受益于Xeon Phi上的硬件集合支持，并且在性能上接近最佳优化代码(1.1倍)。
尽管KNC上的核心数量和SIMD宽度要大得多，但在算法变化之后，剩下的忍者差距在KNC和cpu之间仍然很小，而且很稳定。这是因为我们的算法优化专注于解决代码中的向量化和带宽瓶颈。一旦这些问题得到解决，未来的架构将能够利用不断增加的硬件资源，从而产生稳定和可预测的性能增长。
6.讨论
我们在第4.1节中描述的算法优化适用于包括gpu在内的各种架构。以前的一些出版物19，21讨论了在gpu上获得最佳性能所需的优化。在本节中，我们将展示相同的算法优化对GPU性能的影响。本研究使用NVIDIA C2050 Tesla GPU。
虽然gpu有硬件聚集/分散，但最佳编码实践(例如CUDA C编程指南)19)声明需要避免未合并的全局内存访问，包括将数据结构从AOS转换到SOA，以减少延迟和带宽使用。gpu还需要阻塞优化，这涉及到数据传输/管理到gpu的共享内存(或缓存)。最后，使用SIMD友好算法大大有利于SIMD宽度比当前cpu更宽的gpu。平均算法优化带来的性能提升是3.8倍（图11)比cpu上的2.5倍增益更高，因为gpu有更多的SMs和更大的SIMD宽度，因此次优的算法选择对性能有很大的影响。
7.相关工作
已经发表的许多论文表明，使用经过仔细调优的代码比以前的工作提高了10100X的性能。1，8，14，17，24李等人。15总结了相关硬件架构特点，并针对CPU和gpu的平台软件优化指南。虽然这些作品显示了忍者们在性能上的巨大差距，但它们并没有描述编程工作或如何弥合忍者之间的差距。
在这项工作中，我们分析了忍者差距的来源，并使用传统的编程模型来弥补这一差距。这篇论文的前一个版本发表在Satish等人。23生产式编译器最近开始支持并行化和向量化技术，这些技术已经在编译器研究中发表。这种技术的例子包括最近GCC和ICC编译器中可用的用于并行化的OpenMP，以及自动向量化技术，18处理对齐约束和外环矢量化。这些技术已经使用简单的pragmas和技术，如数组表示法，英特尔®Cilk Plus的一部分。11
然而，即使有编译器的支持，编写的代码也可能无法伸缩，因为它们会受到诸如内存带宽、聚集/分散等架构特性的瓶颈，或者因为算法无法向量化。在这种情况下，需要进行算法更改，如阻塞、SOA转换和simd友好算法。有各种各样的技术被提出来解决这些算法的变化，使用编译器辅助优化，使用缓存无关算法或专门的语言。这样的更改通常需要程序员的干预和程序员的努力，但是可以跨许多体系结构和代使用。例如，许多论文已经展示了类似的算法优化对gpu的影响。21
虽然我们的工作集中在传统的编程模型上，但已经提出了一些根本性的编程模型更改来弥合这一差距。最近的建议包括领域特定语言(一份调查可以在Fowler上找到9)，伯克利视图(Berkeley View)项目2和OpenCL编程异构系统。也有一些面向库的方法被提出，如Intel®线程构建模块、Intel®数学内核库、Microsoft并行模式库(PPL)等。我们认为这些是正交的，并与传统模型结合使用。
还有大量的文献介绍了采用自动调优作为弥补这一差距的方法。8，25自动调优的结果可能比最佳优化的代码糟糕得多。例如，对于自动调整的模板计算，8我们优化后的代码性能提高了1.5倍。因为我们对于模板的忍者差距只有1.1倍，所以我们编译的代码比自动调优代码的性能要好1.3倍。我们希望编译后的结果在总体上与自动调优的结果相竞争，同时提供使用标准工具链的优势，可以简化跨处理器代的可移植性。
8.结论
在这项工作中，我们展示了一组最近的多处理器的真实吞吐量计算基准测试的Ninja性能差距为24X。如果不加以解决，这一差距将不可避免地扩大。我们展示了一组简单而知名的算法技术，再加上现代编译器技术的进步，如何将Ninja的差距缩小到平均水平只有1.3 x。这些更改只需要较低的编程工作量，而忍者代码需要很高的工作量。
参考文献
1.Arora, N.， Shringarpure, A.， Vuduc, R.W.多核平台的直接N体核。在ICPP(2009), 379387。
2.Asanovic, K.， Bodik, R.， Catanzaro, B.， Gebis, J.，丈夫，P.， Keutzer, K.， Patterson, D.A, Plishker, W.L.， Shalf, J.等。并行计算研究的前景:来自伯克利的观点。技术报告UCB/ eecs - 183,2006。
3.Bienia, C.， Kumar, S.， Singh, J.P.， Li, K. PARSEC基准套件:特性和架构含义。在协议(2008), 7281。
4.布雷斯，A.，加塔雷克，D.，穆西拉，M.利率动态的市场模型。数学金融学72(1997), 127155。
5.陈玉坤，Chhugani, J.，等。识别、挖掘和综合工作负载及其影响的收敛。IEEE 965(2008), 790807。
6.Chhugani, J.， Nguyen，公元，等。多核simd cpu架构上的高效排序实现。PVLDB 1， 2(2008)， 13131324。
7.Dally, W.J.否认架构的终结和吞吐量计算的兴起。在在设计自动化会议上的主题演讲(2010)。
8.基于缓存的多核平台模板代码的自动调优。博士论文，美国加州大学伯克利分校EECS系(2009年12月)。
9.福勒,M。领域特定语言1版。Addison-Wesley Professional, Boston, MA 2010。
10.贾尔斯,M.B.计算金融中的蒙特卡罗敏感性评估。技术报告。牛津大学计算实验室，2007年。
11.英特尔。一种快速、简单、可靠的提高线程性能的方法，2010。software.intel.com/articles/intel-cilk-plus．
12.蜂窝宽带引擎处理器上卷积的性能评估。IEEE PDS 22， 2(2011)， 337351。
13.Kachelrieb, M.， Knaup, M.， Bockenbach, O. Hyperfast透视锥束后投影。IEEE核科学3,(2006), 16791683。
14.Kim C.， Chhugani, J.， Satish, N.等人。FAST:现代cpu和gpu上的快速架构敏感树搜索。在SIGMOD(2010)。339350.
15.Lee, V.W.， Kim, C.， Chhugani, J.， Deisher, M.， Kim, D.， Nguyen, A.D, Satish, N.等。揭穿100X GPU vs. CPU的神话:CPU和GPU上的吞吐量计算评估。在ISCA(2010)。451460.
16.t . n .玛吉。动力:一流的建筑设计约束。IEEE计算机34， 4(2001)， 5258。
17.Nguyen, A.， Satish, N.等。现代cpu和gpu上模板计算的3.5 d块优化。在SC10(2010)。113.
18.Nuzman, D.， Henderson, R.多平台自动向量化。在CGO(2006)。281294.
19.Nvidia。CUDA C最佳实践指南2(2010)。
20.Podlozhnyuk, V. BlackScholes期权定价。英伟达, 2007年。http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x86_website/projects/BlackScholes/doc/BlackScholes.pdf．
21.Ryoo, S.， Rodrigues, c.i.， Baghsorkhi, s.s.， Stone, s.s.， Kirk, d.b.， Hwu, W.M.W.使用CUDA的多线程GPU的优化原理和应用性能评估。在PPoPP(2008)。7382.
22.Satish, N.， Kim, C.， Chhugani, J.等。cpu和gpu上的快速排序:带宽无关SIMD排序的一个例子。在SIGMOD(2010)。351362.
23.Satish, N.， Kim, C.， Chhugani, J.， Saito, H.， Krishnaiyer, R.， Smelyanskiy, M.等。传统编程能够弥合并行计算应用程序的忍者性能差距吗?在ISCA(2012)。440451.
24.M. Smelyanskiy, M.， Holmes, D.等。高保真卷渲染映射到CPU、GPU和多核。IEEE TVCG， 15, 6(2009)， 15631570。
25.Sukop, M.C, Thorne, Jr. D.T。晶格玻尔兹曼建模:地球科学家和工程师导论, 2006年。
26.Tian, X.， Saito, H.， Girkar, M.， Preis, S.， Kozhukhov, S.， Cherkasov, a.g.， Nelson, C.， Panchenko, N.， Geva, R.，编译多核SIMD处理器上函数和循环向量化的C/ c++ SIMD扩展。在IPDPS研讨会(施普林格,纽约,2012)。23492358.
脚注
a.由于编程的容易程度(如编程时间或代码行数)在很大程度上是主观的，我们展示了代码片段和实现性能所需的代码更改。
b. Intel、Xeon和Intel Xeon Phi是Intel Corporation在美国和/或其他国家的商标。
c.有关编译器优化的更多完整信息，请参阅优化通知http://software.intel.com/en-us/articles/optimization-notice/．
d.最好的报告数字引用自数据库、高性能计算、图像处理等领域的最新顶级出版物。据我们所知，是这样的不存在任何执行速度更快的代码。
这篇论文的原始版本发表在39年会议纪要th计算机体系结构年度国际研讨会(2012年6月)。IEEE计算机学会，华盛顿特区，440451。
数据
图1。在2核Conroe (CNR)、4核Nehalem (NHM)和6核Westmere (WSM)系统上，Naive串行C/ c++代码与最佳优化代码之间的性能差距越来越大。
图2。在NBody、BackProjection、Stencil和LBM算法改变前后，忍者在指令(ILP)、任务(TLP)和数据级别并行(DLP)方面的性能差距的分解。算法的改变涉及到阻塞。
图3。《忍者缺口》(a)树研究和合并排序，(b) 2D卷积和VR。(a)中的基准测试需要重新考虑算法以使其更有利于simd，而(b)中的基准测试不需要任何算法更改。
图4。Libor、Complex 1D convolution和BlackScholes的Ninja性能差距分解。所有基准测试都需要AOS到SOA的转换，以获得良好的SIMD伸缩性。
图5。对我们的基准测试进行三种不同的算法更改的好处是在任何算法更改之前将代码标准化。算法变化的影响是累积的。
图6。代码片段显示了(a) NBody中的阻塞和(b) simd友好的MergeSort算法的算法更改。
图7。展示编译器技术的代码片段(a)复杂一维卷积的并行化和内环向量化，(b) LIBOR的外环向量化。请注意，所需的代码更改很小，并且可以通过较少的程序员工作来实现。
图8。内环和外环矢量化对(a) SSE和(b) AVX的好处的分解。我们还比较了最佳优化的性能。
图9。优化后的代码、修改算法后的编译器生成的代码和修改算法前的编译器生成的代码的相对性能。修改算法后，性能被规范化为编译后的代码。
©2015 0001 - 0782/15/05 ACM
如果您不是为了盈利或商业利益而制作或分发本作品的部分或全部，并在第一页注明本通知和完整引用，则允许您免费制作本作品的部分或全部数字或纸质副本，供个人或课堂使用。本作品的组成部分必须由ACM以外的其他人享有版权。信用文摘是允许的。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org或传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2015 ACM股份有限公司