为什么随机数生成器在并行执行时会出现问题？
Why do random number generators cause problems when executed in parallel?
我有一个作业，并且提到了以下内容：
Parallelism adds further complications, as the random number
generator function must behave correctly when two or more threads call
it simultaneously, i.e., it must be thread-safe.
但是，我一开始就不明白为什么这是个问题。随机生成器通常以种子作为参数调用，并通过对其进行多次操作来输出一个数字，我知道我们需要每个线程使用不同的种子，但除此之外，问题从何而来？我已经意识到在并行区域而不是串行区域中生成和调用随机生成器也确实会降低性能，但我不明白为什么会发生这种情况，从外观上看，随机数生成器应该 运行同时没有任何问题，因为它们没有依赖关系。
如果能帮助理解这背后的理论，我们将不胜感激。
除了从竞争条件（@MitchWheat 指出）中得到错误的值外，由于缓存行共享，代码效率会降低 主流 x86 处理器内核之间。
这是一个（很糟糕但很简单）32 位随机生成器（用 C 语言编写）的示例：
uint32_t seed = 0xD1263AA2;
uint32_t customRandom() {
uint32_t old = seed;
seed = (uint32_t)(((uint64_t)seed * 0x2E094C40) >> 24);
return old;
}
void generateValues(uint32_t* arr, size_t size) {
for(size_t i=0 ; i<size ; ++i)
arr[i] = customRandom();
}
如果你 运行 这个例子是顺序的（见结果 here），状态 seed 可能会使用主流编译器（即 GCC 和铛）。这个 32 位内存块将 read/written 在非常靠近执行代码的核心的 L1 缓存中。
当您天真地并行化循环时，例如在 OpenMP 中使用 #pragma omp parallel for，状态为 read/written 并发由多个线程。存在竞争条件：状态值seed可以被多个线程并行读取并并行写入。因此，多个线程可以生成相同的值，而结果应该是随机的。比赛条件不好，必须修复。您可以在此处使用线程本地状态来解决此问题。
假设您因为想了解竞争条件对该代码的最终性能的影响而没有修复代码，您应该会看到并行性能下降。问题来自 cache coherence protocol used by x86 mainstream processors. Indeed, seed is shared between all the threads executed on each core so the processor will try to synchronize the cache of the core so they are kept coherent. This process is very expensive (much slower than reading/writing in the L1 cache). More specifically, when a thread on a given core write in seed, the processor invalidate the seed stored in all the other threads located in the caches of the other cores. Each thread must then fetch the updated seed (typically from the much slower L3 cache) when seed is read. You can find more information here.
我有一个作业，并且提到了以下内容：
Parallelism adds further complications, as the random number generator function must behave correctly when two or more threads call it simultaneously, i.e., it must be thread-safe.
但是，我一开始就不明白为什么这是个问题。随机生成器通常以种子作为参数调用，并通过对其进行多次操作来输出一个数字，我知道我们需要每个线程使用不同的种子，但除此之外，问题从何而来？我已经意识到在并行区域而不是串行区域中生成和调用随机生成器也确实会降低性能，但我不明白为什么会发生这种情况，从外观上看，随机数生成器应该 运行同时没有任何问题，因为它们没有依赖关系。
如果能帮助理解这背后的理论，我们将不胜感激。
除了从竞争条件（@MitchWheat 指出）中得到错误的值外，由于缓存行共享，代码效率会降低 主流 x86 处理器内核之间。
这是一个（很糟糕但很简单）32 位随机生成器（用 C 语言编写）的示例：
uint32_t seed = 0xD1263AA2;
uint32_t customRandom() {
uint32_t old = seed;
seed = (uint32_t)(((uint64_t)seed * 0x2E094C40) >> 24);
return old;
}
void generateValues(uint32_t* arr, size_t size) {
for(size_t i=0 ; i<size ; ++i)
arr[i] = customRandom();
}
如果你 运行 这个例子是顺序的（见结果 here），状态 seed 可能会使用主流编译器（即 GCC 和铛）。这个 32 位内存块将 read/written 在非常靠近执行代码的核心的 L1 缓存中。
当您天真地并行化循环时，例如在 OpenMP 中使用 #pragma omp parallel for，状态为 read/written 并发由多个线程。存在竞争条件：状态值seed可以被多个线程并行读取并并行写入。因此，多个线程可以生成相同的值，而结果应该是随机的。比赛条件不好，必须修复。您可以在此处使用线程本地状态来解决此问题。
假设您因为想了解竞争条件对该代码的最终性能的影响而没有修复代码，您应该会看到并行性能下降。问题来自 cache coherence protocol used by x86 mainstream processors. Indeed, seed is shared between all the threads executed on each core so the processor will try to synchronize the cache of the core so they are kept coherent. This process is very expensive (much slower than reading/writing in the L1 cache). More specifically, when a thread on a given core write in seed, the processor invalidate the seed stored in all the other threads located in the caches of the other cores. Each thread must then fetch the updated seed (typically from the much slower L3 cache) when seed is read. You can find more information here.