如何使用数据结构优化 32 位英特尔® 架构上的内存使用

签署人: IDZSupport KS

已发布:12/26/2019   最后更新时间:12/27/2018

挑战

使用数据结构布局提高内存利用率。 对于 3D 转换和照明等某些算法,有两种排列顶点数据的基本方法。传统方法是结构阵列 (AoS) 排列,每个顶点都有一个结构,如下所示:

typedef struct{
float x,y,z;
int a,b,c;
...
} Vertex;
Vertex Vertices[NumOfVertices];

这种方法没有充分利用 SIMD 技术的功能。


解决方案

利用阵列 (SoA) 结构处理方法,将每个坐标的数据排列在阵列中。 SoA 数据结构如下所示:

typedef struct{
float x[NumOfVertices];
float y[NumOfVertices];
float z[NumOfVertices];
int a[NumOfVertices];
int b[NumOfVertices];
int c[NumOfVertices];
...
} VerticesList;
VerticesList Vertices;

有两种方法可以计算 AoS 格式的数据:对 AoS 格式的数据进行操作 或将其动态重新排列 (swizzle it) 为 SoA 格式。以下代码示例显示了基于点积计算的每个选项:

; The dot product of an array of vectors (Array) and a
; fixed vector (Fixed) is a common operation in 3D
; lighting operations,
; where Array = (x0,y0,z0),(x1,y1,z1),...
; and Fixed = (xF,yF,zF)
; A dot product is defined as the scalar quantity
; d0 = x0*xF + y0*yF + z0*zF.

; AoS code
; All values marked DC are “don’t-care.”
; In the AOS model, the vertices are stored in the
; xyz format
movaps xmm0, Array    ; xmm0 = DC, x0, y0, z0
movaps xmm1, Fixed    ; xmm1 = DC, xF, yF, zF
mulps xmm0, xmm1      ; xmm0 = DC, x0*xF, y0*yF, z0*zF
movhlps xmm1, xmm0    ; xmm1 = DC, DC, DC, x0*xF
addps xmm1, xmm0      ; xmm0 = DC, DC, DC,
                      ; x0*xF+z0*zF
movaps   xmm2, xmm1
shufps   xmm2, xmm2,55h ; xmm2 = DC, DC, DC, y0*yF
addps    mm2, xmm1 ; xmm1 = DC, DC, DC,
; x0*xF+y0*yF+z0*zF
; SoA code
;
;
X = x0,x1,x2,x3
; Y = y0,y1,y2,y3
; Z = z0,z1,z2,z3
; A = xF,xF,xF,xF
; B = yF,yF,yF,yF
; C = zF,zF,zF,zF
movaps xmm0, X        ; xmm0 = x0,x1,x2,x3
movaps xmm1, Y        ; xmm0 = y0,y1,y2,y3
movaps xmm2, Z        ; xmm0 = z0,z1,z2,z3
mulps xmm0, A         ; xmm0 = x0*xF, x1*xF, x2*xF, x3*xF
mulps xmm1, B         ; xmm1 = y0*yF, y1*yF, y2*yF, y3*xF
mulps xmm2, C         ; xmm2 = z0*zF, z1*zF, z2*zF, z3*zF
addps xmm0, xmm1
addps xmm0, xmm2      ; xmm0 = (x0*xF+y0*yF+z0*zF), ...

以原始 AoS 格式执行 SIMD 操作可能需要更多计算,并且某些操作无法利用所有可用的 SIMD 元素。因此,这个选项通常效率较低。

在计算 AoS 格式的数据时,建议在使用 SIMD 技术处理数据之前将每组元素转换为 SoA 格式。这种转换既可以在程序执行期间动态完成,也可以在生成数据结构时静态完成。有关转换代码的特定示例,请参见  英特尔® 64 和 IA-32 架构 优化参考手册 的第 4 章和第 5 章。动态执行转换通常比使用 AoS 效果更好,但效率低下,因为在计算过程中会产生额外指令开销。最好在安排数据结构时静态执行转换,因为没有运行时开销。

如前所述,SoA 排列支持更高效地利用 SIMD 技术的并行性,因为数据可以通过更优化的垂直方式进行计算:使用 4 个 SIMD 执行插槽将 x0,x1,x2,x3 乘以 xF,xF,xF,xF,生成 4 个独特结果。相比之下,直接在 AoS 数据上计算会导致占用 SIMD 执行插槽但仅产生单个标量结果的水平操作,如先前代码示例中的许多“无关” (DC) 插槽所示。
将 SoA 格式用于数据结构还可以更有效地使用高速缓存和带宽。如果没有以相同的频率访问结构的各个元素(例如,元素 x, y, z 的访问频率是其他条目的 10 倍),那么 SoA 不仅可以节省内存,还可以防止获取不必要的数据项a, b, c

请注意,SoA 可能具有需要更多独立内存流引用的缺点。使用“解决方案”部分第一个代码示例中的 x, y,z 阵列的计算将需要三个单独的数据流。这可能需要使用更多的预取和备用地址生成计算,并对页面访问效率产生更大的影响。另一种混合 SoA 方法将两种方案混合在一起:

NumOfGroups = NumOfVertices/SIMDwidth
typedef struct{
float x[SIMDwidth];
float y[SIMDwidth];
float z[SIMDwidth];
} VerticesCoordList;
typedef struct{
int a[SIMDwidth];
int b[SIMDwidth];
int c[SIMDwidth];
...
} VerticesColorList;
VerticesCoordList VerticesCoord[NumOfGroups];
VerticesColorList VerticesColor[NumOfGroups];

在这种情况下,仅生成和引用两个单独的地址流:一个包含 xxxx,yyyy,zzzz,zzzz,另一个包含 aaaa,bbbb,cccc,aaaa,dddd,...如果变量 x, y, z 始终一起使用,而变量 a, b, c 也一起使用,但并非与 x, y, z 同时使用,这也可以防止获取不必要的数据。这种混合式 SoA 方法可确保:

  • 数据进行了整理,可实现更高效的垂直 SIMD 计算
  • 比 AoS 更简单/更少的地址生成
  • 更少的数据流,可减少页面遗漏
  • 由于数据流较少,因此使用的预取较少
  • 对并发使用的数据元素进行高效的缓存行打包

随着 SIMD 技术的出现,数据组织的选择变得越来越重要,应根据要执行的数据操作谨慎选择。在某些应用中,传统的数据整理可能无法实现最佳性能。我们鼓励应用开发人员研究不同的数据整理和数据分段策略,以实现高效计算。这可能意味着在特定应用中结合使用 AoS、SoA 和混合 SoA。

以下项目与此相关:

资料来源

英特尔® 64 和 IA-32 架构优化参考手册 (PDF)

 

存在疑问?
请访问我们的 “获取帮助” 页面,获取您的支持选项。

产品和性能信息

1

英特尔的编译器针对非英特尔微处理器的优化程度可能与英特尔微处理器相同(或不同)。这些优化包括 SSE2、SSE3 和 SSSE3 指令集和其他优化。对于在非英特尔制造的微处理器上进行的优化,英特尔不对相应的可用性、功能或有效性提供担保。该产品中依赖于微处理器的优化仅适用于英特尔微处理器。某些非特定于英特尔微架构的优化保留用于英特尔微处理器。关于此通知涵盖的特定指令集的更多信息,请参阅适用产品的用户指南和参考指南。

通知版本 #20110804