缓存友好阵列迭代图案

我有结构的数组上的一段代码，迭代，在更改每个元素在它：缓存友好阵列迭代图案

const size_t nThreads = 4; 

struct foo { 
    int a = 0; 
    float b = 10; 
}; 

void process(foo * array, size_t i, size_t end) { 
    for (; i < end; i++) array[i].a += array[i].b; 
} 

int main() { 
    foo fooArray[512]; 
    process(fooArray, 0, 512); 
    return 0; 
}

现在，我打算利用没有其他代码正在访问fooArray，并且每个元素是相互独立的，以便在fooArray的不同部分上分割process()，每个部分位于其自己的线程中。我知道通常每个核心都有自己独立的（仅限L1的？）缓存，当它们有重叠的缓存区域时，一个核心缓存中的写入必须与指向它的其他缓存同步，从而导致数据停顿。我也知道通常通过FSB访问RAM是同步的，而且这也会导致在不同内核频繁发生缓存缺失的情况下停顿。

接下来的问题是：有了这一切在心中，什么是访问fooArray考虑，我希望尽量减少缓存缺失和数据摊位最好的模式：通过条纹或切片？

通过切片：

void process(foo * array, size_t i, size_t end) { 
    for (; i < end; i++) array[i].a += array[i].b; 
} 

for (int i = 0; i < nThreads; i++) { 
    std::thread t = std::thread([fooArray, i]() { 
    process(fooArray, i * 512/nThreads, (i+1) * 512/nThreads -1); 
    } 
    t.join(); 
}

在这种情况下，每个线程将遍历阵列（线程T1的切片将经过0至127，T2从128到255，从256 T3到383和t4从384到511）。我相信这可以通过内核之间的高速缓存同步来最小化数据停顿，因为每个片可能由不同的内核高速缓存处理，但如果所有内核试图在同一时间尝试获取高速缓存行，则可能会因FSB同步访问而增加停顿。

通过条纹：（注意到i+=nThreads）

void process(foo * array, size_t i, size_t end) { 
    for (; i < end; i+=nThreads) array[i].a += array[i].b; 
} 

for (int i = 0; i < nThreads; i++) { 
    std::thread t = std::thread([fooArray, i]() { 
    process(fooArray, i, 512); 
    } 
    t.join(); 
}

在这种情况下，T1将遍历元素0，4，8，12，...，508中，t1超过1， 5,9,13，...，509，t3超过2,6,10,14，...，510和t4超过3,7,11,15，...，511.我相信这会使FSB最小化访问，因为每个缓存未命中只会触发一次RAM访问，但由于缓存同步导致的数据停顿将会增加。

来源

2014-08-30 Leonardo

我认为切片表现会更好。这对缓存行来说不会太苛刻。 – Arunmu 2014-08-30 19:39:09

切分数据结构是一个好主意，因为这会告诉编译器您已经创建了一个并行代码并准备好执行。但是，您现在必须使用pthread函数来使其成为现实，您对代码有一些变量依赖性。你需要调用pthread_create（）函数，这个函数将同时运行你所有的三个切片。 – Juniar 2014-08-30 21:36:36

我认为切片应该效果最好。预取器应该能够提取您正在访问的连续内存区域，因此应该能够提供最佳性能。另外，你的代码将不依赖于缓存行大小。也就是说，它看起来像你在数据上做的工作量是最小的，并且你很可能成为内存访问速度的瓶颈。如果您在多插槽系统上运行，则应确保将阵列切片，以便每个切片都驻留在内存区域，内核区域可由正在处理它的内核快速访问。 – bluescarni 2014-08-30 21:58:29

你可以参考下面的SO链接，通过关于这一主题的专家包含有关这一概念和各种信息的链接伟大的信息：https://stackoverflow.com/a/23172120/2724703

虽然对性能相关的问题的工作，我们应该经常测量的执行时间通过你自己并了解可能影响的各种参数。第一件事应该测量所有三种情况下的时间。

说了这么多，我想你的“通过切片”做法会比其他由于以下原因，更好地：

因此，为了实现高速缓存友好的逻辑在我们的计划，我们应该尽量做到线性存储器访问越多越好。这真的会被高速缓存机制所喜爱，因为具有L1高速缓存的内存可能性会更高。在这种情况下，线程对数组段的线性访问会比另一个更好。现在这个概念是适用的，如果我们的数据集很大并且不适合一级缓存，那么。在任何一种情况下，您都可以轻松地将整个数据放入L1缓存。因此，如果我们的工作/逻辑是实质性的，并且在这种情况下这种并发症可能不会带来任何好处（有时执行时间可能会增加），那么这样的技术会更合适。可以了解这些概念，但实际上，如果我们通过测量发现这会导致瓶颈，我们应该尝试优化代码。

我不认为应该由于内核之间的高速缓存同步而导致数据停顿。这种开销应同样适用于这两种情况。

来源

2014-08-31 02:21:03

缓存友好阵列迭代图案

回答

相关问题