整理您的数据和代码: 数据和布局 - 第 2 部分

这两篇关于性能和内存的文章介绍了一些基本概念,用于指导开发人员更好地改善软件性能。为实现此目标,文章内容重点阐述了内存和数据布局方面的注意事项。第 1 部分介绍了寄存器使用以及覆盖或阻塞算法,以改善数据重用情况。文章从考虑数据布局以提供通用并行处理能力(与线程共享内存编程)开始,然后还考虑了基于 MPI 的分布式计算。本文扩展了在实现并行处理能力时需考虑的概念,包括矢量化(单指令多数据 SIMD)、共享内存并行处理(线程化)和分布式内存计算等。最后,文章考虑了数据布局结构阵列 (AOS) 以及阵列结构 (SOA) 数据布局。

第 1 部分强调的基本性能原则是:在寄存器或缓存中重新利用数据然后再将其去除。在本文中强调的性能原则为:在最常用数据的地方放置数据,以连续访问模式放置数据,并避免数据冲突。

 

与线程共享内存编程

让我们从考虑与线程共享内存编程开始。全部线程都共享进程中的相同内存。有许多常用的线程模型。最为闻名的是 Posix* 线程和 Windows* 线程。正确创建和管理线程中涉及的工作容易出错。涉及大量模块和大型开发团队的现代软件让线程的并行编程极易出错。在此过程中开发团队需要开发数个程序包,以简化线程创建、管理和充分利用并行线程。最常用的两个模型为 OpenMP* 和英特尔® 线程构建模块。第三个线程模型英特尔® Cilk™ Plus 还未达到与 OpenMP 和线程构建模块相似的采用级别。所有这些线程模型形成线程池,该线程池被重新用于每个并行操作或并行区域。OpenMP 的优势在于可通过使用指令,逐步提高并行处理能力。OpenMP 指令通常可添加至现有软件,并仅需对每一步骤的过程进行最少的代码变更。它允许使用线程运行时库来管理大量线程维护工作,可显著简化线程软件的开发。同时它还可以为所有代码开发人员提供一个可沿用的一致线程模型,减少一些常见线程错误的可能性,并提供由专注于线程优化的开发人员制作的最优线程化运行时库。

简介段落中提及的基本并行原则为将数据置于使用该数据之处,并避免移动数据。在线程化编程中,默认模型是在进程中全局共享数据,并可由所有线程访问数据。有关线程的简介文章强调了通过将 OpenMP 应用至循环 (Fortran*) 或用于循环 (C) 来开始线程的便利性。当在两到四核上运行时,这些方法通常能够带来速度提升。这些方法会经常地扩展至 64 条线程或更多。但很多时候也不会进行此类扩展。在不进行扩展的一些情况中,主要是因为它们尊虚了良好的数据分解计划。这要求为良好的并行代码设计一个架构。

在代码调用堆栈的较高级别利用并行处理能力非常重要,而不是局限于由开发人员或软件工具确定的并行机会。当开发人员认识到可并行操作任务或数据时,依据埃坶德尔定律考虑这些问题: “在进行这点之前,我是否可以开始更高级别的并行运算? 如果我这样做,增大我代码的并行区域是否会带来更好的可扩展性?”

仔细考虑数据的放置以及必须通过消息共享什么数据。数据被置于最常使用的地方,然后根据需要发送至其他系统。对于以网格表示的应用程序,或具有特定分区的物理域,MPI 软件中常见的做法是围绕子网格或子域添加一行“虚拟”单元。虚拟单元用于存储 MPI 进程发送的数据的值,该进程会更新这些单元。通常虚拟单元不会用在线程化软件中,但是正如您沿着用于消息通过的分区最大程度减少边缘的长度一样,需要使用共享内存为线程最大程度减少分区的边缘。这样可最大程度减少对于线程锁(或关键部分)或关系到缓存所有权的缓存使用代价的需求。

大型多路系统共享全局内存地址空间,但通常具有非均匀的内存访问 (NUMA) 时间。和位于最靠近运行代码的插槽的内存条中的数据相比,最靠近另一插槽的内存条中的数据进行检索所需的时间更长,或者延迟更久。对于靠近的内存的访问延迟更短。

. Latency memory access, showing relative time to access data

图 1. 延迟内存访问,显示访问数据的相对时间。

如果一个线程分配并初始化数据,则通常会将该数据置于最靠近线程分配和初始化正在其上运行的插槽的内存条(图 1)。您可通过每个线程分配以及先引用其将主要使用的内存来改善性能。这通常足以确保内存最靠近线程在其上运行的插槽。一旦创建了线程,并且线程处于活动状态,操作系统通常会将线程留在相同插槽上。有时明确将线程绑定至核心以防止线程迁移较为有利。当数据具有特定模式时,实用的做法是将线程的亲缘性分配、绑定或设置到特定核心以匹配该模式。英特尔 OpenMP 运行时库(英特尔® Parallel Studio XE 2016 的一部分)提供了明确的映射属性,这些属性经过证明可用于英特尔® 至强融核™ 协处理器。

这些类型包括紧凑、分散和平衡。 

  • 紧凑属性将连续或相邻的线程分配至单核上的系统性多线程 (SMT),以将线程分配至其他核心。这在线程和连续编号(相邻)的线程共享数据的地方非常重要。
  • 分散亲缘性功能将线程分配至每个核心,然后再回到初始核心以在 SMT 上安排更多线程。
  • 平衡亲缘性功能以平衡的方式将连续或相邻 ID 的线程分配至相同的核心。如果期望根据英特尔 16.0 C++ 编译器文档优化线程亲缘性,在开始亲缘性时建议进行平衡。平衡的亲缘性设置仅可用于英特尔® 至强融核™ 产品系列。它并非一般 CPU 的有效选项。当利用了至强融核平台上的所有 SMT 时,平衡以及紧凑属性的效果相同。如果在至强融核平台上只利用了某些 SMT,紧凑方法将填补第一批内核上的所有 SMT 并在最后适当保留某些内核。

花些一些时间将线程数据靠近使用它的地方放置很重要。就和数据布局对于 MPI 程序很重要一样,这可能也对线程化软件很重要。  

在内存和数据布局方面,需要考虑两个较短的项目。这些是相对易于解决的部分,但是可能有很大影响。第一个是错误共享,第二个是数据对齐。和线程化软件相关的性能问题之一是错误共享。所运算的每个线程数据均为独立状态。它们之间没有共享,但是会共享包含两个数据点的高速缓存行。正因如此,将其称为错误共享或错误数据共享;虽然它们没有共享数据,但是性能行为表现和已经共享一样。

我们假设每个线程递增自身计数器,但是计数器处于一维阵列中。每个线程递增其自身的计数器。要递增其计数器,内核必须拥有高速缓存行。例如,插槽 0 上的线程 A 获得高速缓存行的所有权并递增 iCount[A] 。同时插槽 1 上的线程 A+1 递增 iCount[A+1],要实现这些操作,插槽 1 上的内核获得高速缓存行的所有权,并且线程 A+1 更新其值。由于高速缓存行中的值改变,使得插槽 0 上处理器的高速缓存行无效。在下次迭代时,插槽 0 中的处理器获得来自插槽 0 的高速缓存行的所有权,并修改 iCount[A] 中的值,该值继而让插槽 1 中的高速缓存行无效。当插槽 1 上的线程准备好写入时,循环重复。受到高速缓存行无效、重获控制以及同步至有性能影响的内存的影响,需要使用大量循环来保持缓存一致性。

对此的最佳解决方案并非让缓存无效。例如,在循环的入口,每个线程可读取其计数并将其存储在其堆栈上的本地变量中(读取不会让缓存无效)。当工作完成时,线程可将该本地值复制回最初的位置(参见图 2)。另一个备选方案是填补数据,使数据主要由其自身高速缓存行中的特定线程使用。

int iCount[nThreads] ;
      .
      .
      .
      for (some interval){
       //some work . . . 
       iCount[myThreadId]++ // may result in false sharing
     }

Not invalidating the cache

int iCount[nThreads*16] ;// memory padding to avoid false sharing
      .
      .
      .
      for (some interval){
       //some work . . . 
       iCount[myThreadId*16]++ //no false sharing, unused memory
     }

No false sharing, unused memory

int iCount[nThreads] ; // make temporary local copy

      .
      .
      .
      // every thread creates its own local variable local_count
      int local_Count = iCount[myThreadID] ;
      for (some interval){
       //some work . . . 
       local_Count++ ; //no false sharing
     }
     iCount[myThreadId] = local_Count ; //preserve values
     // potential false sharing at the end, 
     // but outside of inner work loop much improved
     // better just preserve local_Count for each thread

图 2.

相同的错误共享也可能在分配给相邻内存位置的标量上发生。这是如下面代码段所示的最后一种情况:

int data1, data2 ; // data1 and data2 may be placed in memory 
                   //such that false sharing could occur 
declspec(align(64)) int data3;  // data3 and data4 will be 
declspec(align(64)) int data4;  // on separate cache lines, 
                                // no false sharing

如果开发人员从一开始就设计并行处理,并最小化共享数据使用,通常要避免错误共享。 如果您的线程化软件没有很好地扩展,尽管有大量独立的工作在持续进行并且有少量障碍(互斥器、关键部分),检查错误共享也非常重要。

 

数据对齐

当以 SIMD 方式(AVX512、AVX、SSE4 等)运算的数据在高速缓存行边界上对齐时 , 软件性能最佳。数据访问未对齐的代价根据处理器系列而有所不同。英特尔® 至强融核™ 协处理器对于数据对齐尤其敏感。  在英特尔至强融核平台上,数据对齐至关重要。该差异在其他英特尔® 至强® 平台上不是很明显,但是当数据和高速缓存行边界对齐时,性能也能够得到显著的改进。因此建议软件开发人员务必在 64 字节边界上对齐数据。在 Linux* 和 Mac OS X* 上,这可通过英特尔编译器选项完成,没有源代码更改,只需使用以下命令行选项: /align:rec64byte。    

对于 C 语言中的动态分配的内存,malloc() 可由 _mm_alloc(datasize,64) 取代。当使用了 _mm_alloc() 时,应当使用 _mm_free() 取代 free()。专门针对数据对齐的完整文章位于以下网址:https://software.intel.com/zh-cn/articles/data-alignment-to-assist-vectorization。 

另外也请查看编译器文档。为了展现数据对齐的影响,我们创建了两个相同大小的矩阵,并且两个矩阵都运行该系列第 1 部分中使用的阻塞矩阵多层代码。 对于第一种情况,对齐了矩阵 A,对于第二种情况,特意将矩阵 A 偏移 24 个字节(3 的倍数),在将英特尔 16.0 编译器用于大小从 1200x1200 到 4000x4000 的矩阵的情况下,性能减少 56% 至 63%。在该系列的第 1 部分,我显示了一个表格,其中有使用了不同编译器的循环排序的性能,当一个矩阵偏移时使用英特尔编译器不再有任何性能优势。建议开发人员就数据对齐和可用的选项查看其编译器文档,从而当数据对齐时,编译器能够最有效地利用该信息。用于为偏离高速缓存行的的矩阵评估性能的代码嵌入在第 1 部分的代码中 - 该试验的代码位于:https://github.com/drmackay/samplematrixcode

编译器文档也有详细信息。

为了展现数据对齐的效果,我们创建了两个相同大小的矩阵,并且两个矩阵都运行第 1 部分中使用的阻塞矩阵多层代码。我们对齐了第一矩阵 A,第二个矩阵特意被偏移 24 个字节(3 的倍数),在将英特尔 16.0 编译器用于大小从 1200x1200 到 4000x4000 的矩阵的情况下,性能减少 56% 至 63%。

 

结构阵列对比阵列结构

处理器在内存连续流入时性能更佳。这在高速缓存行的每个元素移入 SIMD 寄存器时很有效, 前提是连续高速缓存行也以有序的方式载入了处理器预取。在结构阵列中,数据可采用类似以下形式的布局:

struct {
   uint r, g, b, w ; // a possible 2D color rgb pixel layout
} MyAoS[N] ;

在该布局中,连续陈列出 rgb 值。如果软件跨彩色平面处理数据,则整个结构可能被拉入缓存,但是每次仅使用一个值,例如 g。如果数据存储在阵列结构中,布局可能类似以下形式:

struct {
   uint r[N] ;
   uint g[N] ;
   uint b[N] ;
   uint w[N] ;
} MySoA ;

如果数据以阵列结构组织,并且软件运算所有 g 值(也可以是 r 或 b),当将高速缓存行引入高速缓存时,可能会在运算中使用整个高速缓存行。数据被更有效地载入 SIMD 寄存器,效率和性能显著改善。在许多情况下,软件开发人员用时间在实际操作中临时将数据移入要运算的阵列结构,然后根据需要将其复制回原位。在可行时,最好避免该额外的复制操作,因为这会占用执行时间。

英特尔 (Vectorization) Advisor 2016“内存访问模式”(MAP) 分析确定了具有连续(“单位步幅”)、非连续并且“非常规”的访问模式的循环:

“步幅分配”列提供关于每个模式在给定源循环中发生的频率的汇总统计数据。在上图中,条形图左边的三分之二为蓝色,表示连续访问模式,而右边的三分之一为红色,其表示非连续内存访问。对于具有纯 AoS 模式的代码,Advisor 也可自动获取特定“建议”以执行 AoS -> SoA 转换。 

在 Advisor MAP 中访问模式以及更为一般的内存位置分析得到简化,具体方法为额外提供内存“占用空间”指标,并将每个“步幅”(即访问模式)诊断映射至特定 C++ 或 Fortran* 对象/阵列名称。有关英特尔 Advisor 的详细信息,请访问

https://software.intel.com/zh-cn/get-started-with-advisor https://software.intel.com/zh-cn/intel-advisor-xe

阵列结构和结构阵列数据布局关系到许多图形程序以及 nbody(例如分子动态),或任何时间数据/属性(例如质量、位置、速度、电量),并且可与点或特定主体关联。通常,阵列结构更加有效,并且具有更高性能。

从英特尔编译器 2016 Update 1 开始,通过引入英特尔® SIMD 数据布局模板(英特尔® SDLT),AoS -> SoA 转换变得更简单。借助 SDLT,可以采用下面的方式方便地重新定义 AoS 容器:

SDLT_PRIMITIVE(Point3s, x, y, z)
sdlt::soa1d_container<Point3s> inputDataSet(count);  

从而可通过 SoA 方式访问 Point3s 实例。在此处阅读有关 SDLT 的更多信息。

几篇专论文章专门阐述了 AoS 对比 SoA 的主题。读者可通过下面的链接查看:

https://software.intel.com/zh-cn/articles/a-case-study-comparing-aos-arrays-of-structures-and-soa-structures-of-arrays-data-layouts

https://software.intel.com/zh-cn/articles/how-to-manipulate-data-structure-to-optimize-memory-use-on-32-bit-intel-architecture
http://stackoverflow.com/questions/17924705/structure-of-arrays-vs-array-of-structures-in-cuda

尽管大多数情况下,阵列结构匹配该模式并提供最佳性能,但也存在少数情况,其中数据参考和使用更紧密地匹配结构阵列布局,并且在该情况下结构阵列可提供更好的性能。

 

总结

下面总结了数据布局和性能方面要遵守的基本原则。将代码结构化以最小化数据移动。在数据处于寄存器或高速缓存中时重新使用它;这也有助于最小化数据移动。循环分块有助于最小化数据移动。对于具有 2D 或 3D 布局的软件尤其如此。考虑并行化布局,包括如何为并行计算分配任务和数据。良好的域分解做法有利于消息传送 (MPI) 和共享内存编程。阵列结构移动的数据通常比结构阵列更少,并且效果更佳。避免错误共享,并创建真正的本地变量或提供填充,从而使每个线程在不同的高速缓存行中引用值。最后,将数据对齐设置为在高速缓存行上开始。 

完整的代码可在以下网址下载: https://github.com/drmackay/samplematrixcode

如果您错过了第 1 部分,可在此处找到它。

您可应用这些技巧并了解代码性能如何得到改善。

有关编译器优化的更完整信息,请参阅优化通知