c - 如何避免多个线程写入共享数组导致缓存行失效？

Question

问题的背景:

我正在编写一个创建 32 个线程的代码，并将它们与我的多核多处理器系统中的 32 个内核中的每一个内核设置关联。

线程简单地执行RDTSCP指令，并将值存储在共享数组中的非重叠位置，这就是共享数组:

uint64_t rdtscp_values[32];

因此，每个线程都将根据其核心编号写入特定的数组位置。

据了解，除了我知道我可能没有使用正确的数据结构来避免缓存行弹跳之外，一切都正常工作。

附注: 我已经检查过我的处理器的缓存行是 64 字节宽。

因为我使用的是一个简单的 uint64_t 数组，这意味着由于预读，单个缓存行将存储该数组的 8 个位置。

问题:

因为这个简单的数组，虽然线程写入不同的索引，但我的理解是每次写入这个数组都会导致所有其他线程的缓存失效？

如何创建与缓存行对齐的结构？

编辑 1

我的系统是:2x Intel Xeon E5-2670 2.30GHz(8 核，16 线程)

Answer 1

是的，您绝对想避免“虚假共享”和缓存行乒乓。 但这可能没有意义:如果这些内存位置是线程私有(private)的，而不是它们被其他线程收集的频率更高，那么它们应该与其他每线程数据一起存储，这样您就不会浪费 56 字节的缓存占用空间填充。另见 Cache-friendly way to collect results from multiple threads . (没有很好的答案；如果可以，请避免设计需要非常细粒度地​​收集结果的系统。)

---

但是让我们假设一下，不同线程的槽之间未使用的填充实际上是您想要的。

是的，您需要将步幅设置为 64 字节(1 个缓存行)，但实际上您不需要将所用的 8B 置于每个缓存行的开始。因此，您不需要任何额外的对齐方式，只要 uint64_t 对象是自然对齐的(因此它们不会跨缓存行边界拆分)。

如果每个线程都写入其缓存行的第 3 个 qword 而不是第 1 个，那很好。 OTOH，与 64B 对齐可确保没有其他元素与第一个元素共享缓存行，这很容易，所以我们也可以这样做。

---

静态存储:在 ISO C11 中使用 alignas() 对齐静态存储非常容易，或使用特定于编译器的内容。

对于结构，填充是隐式的，以使大小成为所需对齐的倍数。让一个成员具有对齐要求意味着整个结构至少需要那么多的对齐。编译器会通过静态和自动存储为您解决这个问题，但您必须使用 aligned_alloc 或过度对齐的动态分配的替代方法。

#include <stdalign.h>   // for #define alignas _Alignas  for C++ compat
#include <stdint.h>     // for uint64_t

// compiler knows the padding is just padding
struct { alignas(64) uint64_t v; } rdtscp_values[32];

int foo(unsigned t) {
    rdtscp_values[t].v = 1;
    return sizeof(rdtscp_values[0]);  // yes, this is 64
}

或者用数组 as suggested by @ Eric Postpischil :

alignas(64) // optional, stride will still be 64B without this.
uint64_t rdtscp_values_2d[32][8];  // 8 uint64_t per cache line

void bar(unsigned t) {
    rdtscp_values_2d[t][0] = 1;
}

alignas() 是可选的，如果你不关心整个事情是 64B 对齐的，只是在你使用的元素之间有 64B 步幅。您还可以在 GNU C 或 C++ 中使用 __attribute__((aligned(64)))，或 __declspec(align(64))对于 MSVC，使用 #ifdef 定义可移植到主要 x86 编译器的 ALIGN 宏。

---

两种方式都产生相同的 asm。我们可以检查编译器输出来验证我们得到了我们想要的。 I put it up on the Godbolt compiler explorer .我们得到:

foo:   # and same for bar
    mov     eax, edi              # zero extend 32-bit to 64-bit
    shl     rax, 6                # *64 is the same as <<6
    mov     qword ptr [rax + rdtscp_values], 1    # store 1

    mov     eax, 64               # return value = 64 = sizeof(struct)
    ret

两个数组的声明方式相同，编译器从汇编器/链接器请求 64B 对齐 with the 3rd arg to .comm :

    .comm   rdtscp_values_2d,2048,64
    .comm   rdtscp_values,2048,64

---

动态存储:

如果线程数不是编译时常量，那么您可以使用对齐分配函数来获得对齐的动态分配内存(特别是如果您想支持非常线程)。参见 How to solve the 32-byte-alignment issue for AVX load/store operations? , 但实际上只使用 C11 aligned_alloc .它非常适合这一点，并返回一个与 free() 兼容的指针。

struct { alignas(64) uint64_t v; } *dynamic_rdtscp_values;
void init(unsigned nthreads) {
    size_t sz = sizeof(dynamic_rdtscp_values[0]);
    dynamic_rdtscp_values = aligned_alloc(nthreads*sz, sz);
}

void baz(unsigned t) {
    dynamic_rdtscp_values[t].v = 1;
}


 baz:
    mov     rax, qword ptr [rip + dynamic_rdtscp_values]

    mov     ecx, edi            # same code as before to scale by 64 bytes
    shl     rcx, 6
    mov     qword ptr [rax + rcx], 1
    ret

数组的地址不再是链接时常量，因此有一个额外的间接级别来访问它。但是指针在初始化后是只读的，因此它将在每个内核的缓存中共享并在需要时重新加载它非常便宜。

---

脚注:在 i386 System V ABI 中，uint64_t 默认情况下在结构内部只有 4B 对齐(没有 alignas(8) 或 __attribute__((aligned (8)))), 所以如果你把一个 int 放在一个 uint64_t 之前并且没有对整个结构进行任何对齐，这将是可能的获得缓存行拆分。但是编译器会尽可能将其对齐 8B，因此您的结构填充仍然没问题。