现代处理器上的并行内存访问
Parallel memory access on modern processors
我有一个最近的 12 核 Intel CPU（Haswell 架构），它有 4 个内存通道。机器可以并行执行多少次 DRAM 内存访问？
例如，如果我有一个程序使用 12 个线程，这些线程处于紧密循环中，从范围太大而无法放入缓存的随机内存地址读取单个字节。我预计所有 12 个线程将花费几乎所有时间来等待内存获取。
线程是否必须轮流使用DRAM总线？
注意：假设我使用的是 1 GB 的 VM 页面大小，因此没有 TLB 缓存未命中。
英特尔数据表几乎可以回答这个问题。
我的第一个线索是英特尔论坛上的一个问题：
https://communities.intel.com/thread/110798
Jaehyuk.Lee，2017 年 2 月 1 日 09:27 问了几乎和我一样的问题：
The Second question is about simultaneous requests on IMC and its
support on brand-new CPU models such as skylake and kaby-lake
http://www.intel.com/Assets/PDF/datasheet/323341.pdf Following the
above link, "The memory controller can operate on up to 32
simultaneous requests(reads and writes)" I would like to know how many
simultaneous requests are supported in skylake and kabylake CPUs. I've
already checked the 6th and 7th generation of the Intel CPU datasheet,
but I cannot find any information.
link 已死。但他的“32”数字听起来很合理。
一名英特尔工作人员回应，引用自6th Generation Intel® Processor Families for S-Platforms, Vol 1：
The memory controller has an advanced command scheduler where all
pending requests are examined simultaneously to determine the most
efficient request to be issued next. The most efficient request is
picked from all pending requests and issued to system memory
Just-in-Time to make optimal use of Command Overlapping. Thus, instead
of having all memory access requests go individually through an
arbitration mechanism forcing requests to be executed one at a time,
they can be started without interfering with the current request
allowing for concurrent issuing of requests. This allows for optimized
bandwidth and reduced latency while maintaining appropriate command
spacing to meet system memory protocol.
令人恼火的是，我的 Xeon E5-2670 v3 数据表不包含等效部分。
另一部分答案是E5-2670有4个DDR通道。内存以 256 字节的粒度交错以优化带宽。换句话说，如果您从地址 0 读取一个 1024 字节的块，则前 256 个字节是从 DIMM 0 中获取的。字节 256 到 511 来自 DIMM 1 等
将两者放在一起，我怀疑内存控制器可以并行执行 4 次读取并且足够智能，如果有 4 个或更多线程正在等待映射到 4 个不同 DIMM 的读取，它将并行执行它们。并且它有足够的硬件在其调度 table.
中保持大约 32 reads/writes
我可以想出另一种可能的方法来实现并行性。每个 DDR 通道都有自己的数据和地址总线。当内存控制器请求读取时，它使用地址线+一些控制线来请求读取，然后等待响应。对于随机读取，通常有两个等待——RAS 到 CAS 延迟和 CAS 延迟——每个等待大约 15 个周期。您可以想象内存控制器在这些等待期间从不同的 DIMM (*) 开始另一次读取，而不是让地址线空闲。我不知道这是否完成了。
* 实际上，根据 this Anandtech article，DRAM 硬件中的并行性比每个通道具有多个 DIMM 的并行性更高。每个 DIMM 可能有多个列，每个列有多个内存条。我认为您可以切换到 DIMM 中的任何其他列和组以并行执行另一次访问。
编辑
我测得我的机器可以并行进行至少 6 次随机访问，尽管只有 4 个内存通道。因此单个内存通道可以并行执行 2 次或更多次随机访问，也许使用我在上一段中描述的方案。
为了获取此信息，我使用 tinymembench 来测量我机器上 DRAM 访问的延迟。结果是 60 ns。然后我编写了一个小的 C 程序来从 1 GB table 的随机数中执行 32 位读取，并使用结果来增加校验和。伪代码：
uint32_t checksum = 0;
for (int i = 0; i < 256 * 1024 * 1024; i++) {
unsigned offset = rand32() & (TABLE_SIZE - 1);
checksum += table_of_random_numbers[offset];
}
循环的每次迭代平均花费 10 ns。这是因为我的 CPU 中的乱序和推测执行功能能够将此循环并行化 6 次。即 10 ns = 60 ns / 6.
如果我将代码替换为：
unsigned offset = rand32() & (TABLE_SIZE - 1);
for (int i = 0; i < 256 * 1024 * 1024; i++) {
offset = table_of_random_numbers[offset];
offset &= (TABLE_SIZE - 1);
}
然后每次迭代需要 60 ns，因为循环无法并行化。不能并行化，因为每次访问的地址都取决于上一次读取的结果。
我还检查了编译器生成的程序集，以确保它没有完成并行化。
编辑 2
我决定测试当我 运行 并行测试时会发生什么，每个测试都是一个单独的过程。我使用了上面包含校验和的程序片段（即每次访问似乎有 10 ns 的延迟）。通过 运行 并行 6 个实例，我得到 13.9 ns 的平均表观延迟，这意味着 大约 26 次访问必须并行发生。（60 ns / 13.9 ns） * 6 = 25.9.
6 个实例是最佳的。任何更多导致整体吞吐量下降。
编辑 3 - 回答 Peter Cordes RNG 问题
我尝试了两种不同的随机数生成器。
uint32_t g_seed = 12345;
uint32_t fastrand() {
g_seed = 214013 * g_seed + 2531011;
return g_seed;
}
和
// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t;
uint32_t pcg32_random_r(pcg32_random_t* rng)
{
uint64_t oldstate = rng->state;
// Advance internal state
rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
// Calculate output function (XSH RR), uses old state for max ILP
uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
uint32_t rot = oldstate >> 59u;
return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}
他们的表现差不多。我不记得确切的数字。我看到的峰值单线程性能来自更简单的 RNG，它为我提供了 8.5 ns 的分摊延迟，这意味着 7 次并行读取。定时循环的程序集是：
// Pseudo random number is in edx
// table is in rdi
// loop counter is in rdx
// checksum is in rax
.L8:
imull 4013, %edx, %edx
addl 31011, %edx
movl %edx, %esi
movl %edx, g_seed(%rip)
andl 73741823, %esi
movzbl (%rdi,%rsi), %esi
addq %rsi, %rax
subq , %rcx
jne .L8
ret
我不明白"g_seed(%rip)"。那是内存访问吗？为什么编译器会那样做？
编辑 4 - 从随机数生成器中删除了全局变量
我按照 Peter 的建议从随机数生成器中删除了全局变量。生成的代码确实更干净。我还切换到 Intel 语法进行反汇编（感谢提示）。
// Pseudo random number is in edx
// table is in rdi
// loop counter is in rdx
// checksum is in rax
.L8:
imul edx, edx, 214013
add edx, 2531011
mov esi, edx
and esi, 1073741823
movzx esi, BYTE PTR [rdi+rsi]
add rax, rsi
sub rcx, 1
jne .L8
ret
单进程和多进程情况下的性能没有变化。
我有一个最近的 12 核 Intel CPU（Haswell 架构），它有 4 个内存通道。机器可以并行执行多少次 DRAM 内存访问？
例如，如果我有一个程序使用 12 个线程，这些线程处于紧密循环中，从范围太大而无法放入缓存的随机内存地址读取单个字节。我预计所有 12 个线程将花费几乎所有时间来等待内存获取。
线程是否必须轮流使用DRAM总线？
注意：假设我使用的是 1 GB 的 VM 页面大小，因此没有 TLB 缓存未命中。
英特尔数据表几乎可以回答这个问题。
我的第一个线索是英特尔论坛上的一个问题： https://communities.intel.com/thread/110798
Jaehyuk.Lee，2017 年 2 月 1 日 09:27 问了几乎和我一样的问题：
The Second question is about simultaneous requests on IMC and its support on brand-new CPU models such as skylake and kaby-lake http://www.intel.com/Assets/PDF/datasheet/323341.pdf Following the above link, "The memory controller can operate on up to 32 simultaneous requests(reads and writes)" I would like to know how many simultaneous requests are supported in skylake and kabylake CPUs. I've already checked the 6th and 7th generation of the Intel CPU datasheet, but I cannot find any information.
link 已死。但他的“32”数字听起来很合理。
一名英特尔工作人员回应，引用自6th Generation Intel® Processor Families for S-Platforms, Vol 1：
The memory controller has an advanced command scheduler where all pending requests are examined simultaneously to determine the most efficient request to be issued next. The most efficient request is picked from all pending requests and issued to system memory Just-in-Time to make optimal use of Command Overlapping. Thus, instead of having all memory access requests go individually through an arbitration mechanism forcing requests to be executed one at a time, they can be started without interfering with the current request allowing for concurrent issuing of requests. This allows for optimized bandwidth and reduced latency while maintaining appropriate command spacing to meet system memory protocol.
令人恼火的是，我的 Xeon E5-2670 v3 数据表不包含等效部分。
另一部分答案是E5-2670有4个DDR通道。内存以 256 字节的粒度交错以优化带宽。换句话说，如果您从地址 0 读取一个 1024 字节的块，则前 256 个字节是从 DIMM 0 中获取的。字节 256 到 511 来自 DIMM 1 等
将两者放在一起，我怀疑内存控制器可以并行执行 4 次读取并且足够智能，如果有 4 个或更多线程正在等待映射到 4 个不同 DIMM 的读取，它将并行执行它们。并且它有足够的硬件在其调度 table.
中保持大约 32 reads/writes我可以想出另一种可能的方法来实现并行性。每个 DDR 通道都有自己的数据和地址总线。当内存控制器请求读取时，它使用地址线+一些控制线来请求读取，然后等待响应。对于随机读取，通常有两个等待——RAS 到 CAS 延迟和 CAS 延迟——每个等待大约 15 个周期。您可以想象内存控制器在这些等待期间从不同的 DIMM (*) 开始另一次读取，而不是让地址线空闲。我不知道这是否完成了。
* 实际上，根据 this Anandtech article，DRAM 硬件中的并行性比每个通道具有多个 DIMM 的并行性更高。每个 DIMM 可能有多个列，每个列有多个内存条。我认为您可以切换到 DIMM 中的任何其他列和组以并行执行另一次访问。
编辑
我测得我的机器可以并行进行至少 6 次随机访问，尽管只有 4 个内存通道。因此单个内存通道可以并行执行 2 次或更多次随机访问，也许使用我在上一段中描述的方案。
为了获取此信息，我使用 tinymembench 来测量我机器上 DRAM 访问的延迟。结果是 60 ns。然后我编写了一个小的 C 程序来从 1 GB table 的随机数中执行 32 位读取，并使用结果来增加校验和。伪代码：
uint32_t checksum = 0;
for (int i = 0; i < 256 * 1024 * 1024; i++) {
unsigned offset = rand32() & (TABLE_SIZE - 1);
checksum += table_of_random_numbers[offset];
}
循环的每次迭代平均花费 10 ns。这是因为我的 CPU 中的乱序和推测执行功能能够将此循环并行化 6 次。即 10 ns = 60 ns / 6.
如果我将代码替换为：
unsigned offset = rand32() & (TABLE_SIZE - 1);
for (int i = 0; i < 256 * 1024 * 1024; i++) {
offset = table_of_random_numbers[offset];
offset &= (TABLE_SIZE - 1);
}
然后每次迭代需要 60 ns，因为循环无法并行化。不能并行化，因为每次访问的地址都取决于上一次读取的结果。
我还检查了编译器生成的程序集，以确保它没有完成并行化。
编辑 2
我决定测试当我 运行 并行测试时会发生什么，每个测试都是一个单独的过程。我使用了上面包含校验和的程序片段（即每次访问似乎有 10 ns 的延迟）。通过 运行 并行 6 个实例，我得到 13.9 ns 的平均表观延迟，这意味着 大约 26 次访问必须并行发生。（60 ns / 13.9 ns） * 6 = 25.9.
6 个实例是最佳的。任何更多导致整体吞吐量下降。
编辑 3 - 回答 Peter Cordes RNG 问题
我尝试了两种不同的随机数生成器。
uint32_t g_seed = 12345;
uint32_t fastrand() {
g_seed = 214013 * g_seed + 2531011;
return g_seed;
}
和
// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t;
uint32_t pcg32_random_r(pcg32_random_t* rng)
{
uint64_t oldstate = rng->state;
// Advance internal state
rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
// Calculate output function (XSH RR), uses old state for max ILP
uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
uint32_t rot = oldstate >> 59u;
return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}
他们的表现差不多。我不记得确切的数字。我看到的峰值单线程性能来自更简单的 RNG，它为我提供了 8.5 ns 的分摊延迟，这意味着 7 次并行读取。定时循环的程序集是：
// Pseudo random number is in edx
// table is in rdi
// loop counter is in rdx
// checksum is in rax
.L8:
imull 4013, %edx, %edx
addl 31011, %edx
movl %edx, %esi
movl %edx, g_seed(%rip)
andl 73741823, %esi
movzbl (%rdi,%rsi), %esi
addq %rsi, %rax
subq , %rcx
jne .L8
ret
我不明白"g_seed(%rip)"。那是内存访问吗？为什么编译器会那样做？
编辑 4 - 从随机数生成器中删除了全局变量
我按照 Peter 的建议从随机数生成器中删除了全局变量。生成的代码确实更干净。我还切换到 Intel 语法进行反汇编（感谢提示）。
// Pseudo random number is in edx
// table is in rdi
// loop counter is in rdx
// checksum is in rax
.L8:
imul edx, edx, 214013
add edx, 2531011
mov esi, edx
and esi, 1073741823
movzx esi, BYTE PTR [rdi+rsi]
add rax, rsi
sub rcx, 1
jne .L8
ret
单进程和多进程情况下的性能没有变化。