Fak*_*ken 15 c++ cpu performance ram multithreading
我是一般的编程新手所以请在回答我的问题时牢记这一点.
我有一个程序,它采用一个大型3D阵列(10亿个元素)并沿各个轴汇总元素,以生成数据每一侧投影的2D数组.这里的问题是它非常密集,因为程序不断地从ram获取信息,包括读写.
问题是,如果我多线程化程序或者我最终会遇到RAM访问瓶颈,我会获得任何性能提升吗？当我说多线程时,我只是指2或4个核心的多线程,而不是更多.
如果它有帮助,我目前的计算机配置是2.4ghz core2 quad,1033 fsb,4gb ram,667mhz.
提前致谢,
-Faken
编辑:
在我看来,这里的人们对我最初预期的这个问题更感兴趣.我将扩展问题并为感兴趣的人发布一些代码.
首先,有一点关于我的背景,以便你了解我的来源.我是一名机械工程研究生,有些人设法选择一个与机械工程无关的话题.大约5年前,我在介绍性的java(强制)课程中学习了1门课程,直到大约一个月前,我才认真地开始学习论文.我还采取了(再次强迫,仍然不知道为什么)电子和计算机工程课程,我们处理微控制器(8位),它们的内部工作,以及一些ASM编码.除此之外,我对编程几乎一无所知.
这是代码:
int dim = 1000;
int steps = 7 //ranges from 1 to 255
for (int stage = 1; stage < steps; stage++)
for (int j = 0; j < dim; j++)
for (int i = 0; i < dim; i++)
{
sum = 0;
for (int k = 0; k < dim; k++)
if (partMap[(((i * dim) + k) * dim) + j] >= stage)
sum++;
projection[(j*dim) + i] = sum;
}
此部分代码仅在z轴上运行.由于构建方式的原因,主要数据有一个奇怪的寻址系统,但您不必担心这一点.还有其他代码用于执行多维数据集的其他方面的投影,但它们做了非常不同的事情.
Ore*_*ner 32
跨多个内核的多线程可以减少在轴上求和所需的时间,但需要特别小心.实际上,您可以通过对单线程代码进行的一些更改来获得更大的性能提升:
您只需要尽可能多的线程来匹配可用的核心数.这是CPU密集型操作,线程不太可能等待I/O.
如果整个阵列不适合RAM,则上述假设可能不成立.如果数组的某些部分被分页输入和输出,则某些线程将等待分页操作完成.在这种情况下,程序可能会受益于拥有比核心更多的线程.然而,由于上下文切换的成本太多,性能将下降.您可能需要尝试线程计数.一般规则是最小化就绪线程之间的上下文切换次数.
如果整个阵列不适合RAM,您希望最小化分页!每个线程访问内存的顺序很重要,所有正在运行的线程的内存访问模式也是如此.在可能的情况下,您可能希望在移动到下一个数组之前完成数组的一部分,而不是返回到覆盖区域.
每个核心都将从必须访问完全独立的内存区域中受益.您希望避免因锁和总线争用而导致的内存访问延迟.至少对于立方体的一个维度来说,这应该是直截了当的:将每个线程设置为其自己的立方体部分.
与从RAM中获取数据相比,每个内核还可以从其缓存中访问更多数据.这意味着对循环进行排序,使内循环访问附近的单词,而不是跳过行.
最后,根据阵列中的数据类型,英特尔/ AMD处理器(SSE,各代)的SIMD指令可以通过一次求和多个单元来帮助加速单核性能.VC++有一些内置的支持.
如果必须确定工作的优先级,您可能希望首先最小化磁盘分页,然后集中精力优化内存访问以利用CPU缓存,然后才处理多线程.
Ste*_*sop 11
只有一种方法可以优化代码:弄清楚你正在做什么,这很慢,而且做得少."少做"的一个特例是做一些其他事情而不是更快.
首先,根据您发布的代码,我正在做的事情:
#include <fstream>
#include <sstream>
using std::ios_base;
template<typename Iterator, typename Value>
void iota(Iterator start, Iterator end, Value val) {
while (start != end) {
*(start++) = val++;
}
}
int main() {
const int dim = 1000;
const int cubesize = dim*dim*dim;
const int squaresize = dim*dim;
const int steps = 7; //ranges from 1 to 255
typedef unsigned char uchar;
uchar *partMap = new uchar[cubesize];
// dummy data. I timed this separately and it takes about
// a second, so I won't worry about its effect on overall timings.
iota(partMap, partMap + cubesize, uchar(7));
uchar *projection = new uchar[squaresize];
for (int stage = 1; stage < steps; stage++) {
for (int j = 0; j < dim; j++) {
for (int i = 0; i < dim; i++)
{
int sum = 0;
for (int k = 0; k < dim; k++)
if (partMap[(((i * dim) + k) * dim) + j] >= stage)
sum++;
projection[(j*dim) + i] = sum;
}
}
std::stringstream filename;
filename << "results" << stage << ".bin";
std::ofstream file(filename.str().c_str(),
ios_base::out | ios_base::binary | ios_base::trunc);
file.write((char *)projection, squaresize);
}
delete[] projection;
delete[] partMap;
}
(编辑:只是注意到"投影"应该是一个int数组,而不是uchar.我的不好.这会对一些时间产生影响,但希望不会太大.)
然后我复制result*.bin到了gold*.bin,所以我可以检查我未来的变化如下:
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 1m41.978s
user 1m39.450s
sys 0m0.451s
好的,此刻100秒.
因此,推测它正在跨越数十亿项数据阵列,我们只尝试一次,而不是每个阶段一次:
uchar *projections[steps];
for (int stage = 1; stage < steps; stage++) {
projections[stage] = new uchar[squaresize];
}
for (int j = 0; j < dim; j++) {
for (int i = 0; i < dim; i++)
{
int counts[256] = {0};
for (int k = 0; k < dim; k++)
counts[partMap[(((i * dim) + k) * dim) + j]]++;
int sum = 0;
for (int idx = 255; idx >= steps; --idx) {
sum += counts[idx];
}
for (int stage = steps-1; stage > 0; --stage) {
sum += counts[stage];
projections[stage][(j*dim) + i] = sum;
}
}
}
for (int stage = 1; stage < steps; stage++) {
std::stringstream filename;
filename << "results" << stage << ".bin";
std::ofstream file(filename.str().c_str(),
ios_base::out | ios_base::binary | ios_base::trunc);
file.write((char *)projections[stage], squaresize);
}
for (int stage = 1; stage < steps; stage++) delete[] projections[stage];
delete[] partMap;
它有点快:
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 1m15.176s
user 1m13.772s
sys 0m0.841s
现在,steps在这个例子中相当小,所以我们用"计数"数组做了很多不必要的工作.在没有剖析的情况下,我猜测计数到256两次(一次清除数组和一次加总)与计数到1000(沿着我们的列运行)相比非常重要.所以让我们改变一下:
for (int j = 0; j < dim; j++) {
for (int i = 0; i < dim; i++)
{
// steps+1, not steps. I got this wrong the first time,
// which at least proved that my diffs work as a check
// of the answer...
int counts[steps+1] = {0};
for (int k = 0; k < dim; k++) {
uchar val = partMap[(((i * dim) + k) * dim) + j];
if (val >= steps)
counts[steps]++;
else counts[val]++;
}
int sum = counts[steps];
for (int stage = steps-1; stage > 0; --stage) {
sum += counts[stage];
projections[stage][(j*dim) + i] = sum;
}
}
}
现在我们只使用我们实际需要的桶数.
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 0m27.643s
user 0m26.551s
sys 0m0.483s
欢呼.代码几乎是第一个版本的4倍,并产生相同的结果.我所做的就是改变数学的顺序:我们甚至还没有看过多线程或预取.我没有尝试任何高技术循环优化,只是把它留给了编译器.所以这可以被认为是一个不错的开始.
然而,它仍然比iota运行的1s长一个数量级.所以仍有可能找到很大的收益.一个主要区别是iota按顺序在1d阵列上运行,而不是在整个地方跳跃.正如我在第一个答案中所说,您应该始终在立方体上使用顺序.
那么,让我们进行一行更改,切换i和j循环:
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++) {
这仍然不是连续的顺序,但它确实意味着我们一次只关注我们的立方体的一百万字节切片.一个现代的CPU具有至少4MB的缓存,所以运气好的话,我们只会在整个程序中点击立方体的任何给定部分的主内存.通过更好的局部性,我们也可以减少进出L1缓存的流量,但主内存最慢.
它有多大区别？
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 0m8.221s
user 0m4.507s
sys 0m0.514s
不错.事实上,仅这一变化就会使原始代码从100秒到20秒.所以这个因素是5,我做的其他事情都是另一个因素5(我认为上面'用户'和'实际'时间之间的差异主要是因为我的病毒扫描程序是运行,它不是更早.'user'是程序占用CPU的时间,'real'包括暂停的时间,等待I/O或给另一个进程时间运行).
当然,我的桶排序依赖于这样一个事实,即我们对每列中的值所做的事情都是可交换的和关联的.减少桶的数量只能起作用,因为大的值都被视为相同.这可能不适用于您的所有操作,因此您必须依次查看每个操作的内部循环以确定如何处理它.
代码有点复杂.我们不是为每个阶段的数据执行"blah",而是在数据的单次运行中同时计算所有阶段.如果你在一次通过中开始进行行和列计算,正如我在第一个答案中所建议的那样,这将变得更糟.您可能必须开始将代码分解为函数以使其可读.
最后,我的很多表现都来自优化"步骤"很小的事实.随着steps=100,我得到:
$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++ -O3 -pedantic -Wall big.cpp -o big
real 0m22.262s
user 0m10.108s
sys 0m1.029s
这不是那么糟糕.使用steps = 100,原始代码可能需要大约1400秒,尽管我不会运行它来证明这一点.但值得记住的是,我还没有完全消除对"步骤"的时间依赖性,只是让它变为亚线性.
你的代码如何工作？它会这样吗？
for each row: add up the values
for each column: add up the values
for each stack: add up the values
如果是这样,您可能想要阅读"参考地点".根据数据的存储方式,您可能会发现在执行堆栈时,必须为每个值提取整个高速缓存行,因为这些值在内存中彼此无法接近.实际上,有十亿个值,你可能会从磁盘中一路拉动东西.具有较长步幅(值之间的距离)的顺序访问是缓存的最坏可能用途.尝试进行性能分析,如果您发现添加堆栈所需的时间比添加行的时间长,这几乎就是原因.
我认为你可能会使内存总线(*)饱和,在这种情况下,多线程只有在core2 quad对不同内核使用不同总线时才有用.但是如果你没有使总线带宽饱和,即使你多线程也不能以这种方式获得最佳性能.你将有4个内核花费他们所有的时间停滞在缓存未命中而不是一个.
如果您是内存缓存绑定,那么您的目标应该是尽可能少地访问每个页面/内存行.因此,我会尝试一次运行数据,将每个值添加到三个不同的总计中.如果在单个核心上运行速度更快,那么我们就可以开展业务.下一步是使用1000x1000x1000多维数据集,您可以随时获得300万个总计.这也不适合缓存,因此您必须担心在阅读时写入相同的缓存未命中问题.
您希望确保当您在RAM中运行一行1000个相邻值时添加到它们共享的行总数时,您还要添加到列和堆栈的相邻总计(它们不存储它们).所以列总数的"平方"应该以适当的方式存储,堆栈的"正方形"应该存储.这样你就可以通过将大约12k的内存提取到缓存中来处理1000个十亿个值(1000个值为4k,1000个列总计加上4k,1000个堆栈总数加上4k).与此相反,通过一次集中总计1个(因此可能在寄存器中),您所做的商店数量超过了您的数量.
所以我不承诺任何事情,但我认为值得查看内存访问的顺序,无论你是否多线程.如果你只需要访问相对少量的内存就可以做更多的CPU工作,那么你将加速单线程版本,但也可以让自己更好地适应多线程,因为内核共享一个有限的缓存,内存总线和主RAM.
(*)信封计算的背面:在互联网上的随机随机评论中,到目前为止我发现的Core2处理器的最高估计FSB带宽是12GB/s的Extreme,2个通道,每个4x199MHz).缓存行大小为64字节,小于您的步幅.因此,总结一个列或堆栈的坏方法,每个值占用64个字节,只有在每秒执行2亿个值时才会使总线饱和.我猜它不是那么快(整件事情10-15秒),或者你不会问如何加快速度.
所以我的第一个猜测可能就此消失了.除非您的编译器或CPU插入了一些非常聪明的预取,否则单个内核不能在每个周期使用2个通道和4个同时传输.就此而言,4个核心无法使用2个通道和4个同时传输.一系列请求的有效总线带宽可能远低于物理限制,在这种情况下,您希望看到多线程的良好改进,因为您有4个内核需要4个不同的缓存行,所有这些都可以是同时加载而不会麻烦FSB或缓存控制器.但是延迟仍然是杀手,所以如果每个值总和可以加载少于一个缓存行,那么你会做得更好.
| 归档时间： |
|
| 查看次数： |
4327 次 |
| 最近记录： |