优化索引阵列求和

我有以下C++代码：优化索引阵列求和

const int N = 1000000 
int id[N]; //Value can range from 0 to 9 
float value[N]; 

// load id and value from an external source... 

int size[10] = { 0 }; 
float sum[10] = { 0 }; 
for (int i = 0; i < N; ++i) 
{ 
    ++size[id[i]]; 
    sum[id[i]] += value[i]; 
}

我应该如何优化循环？

我考虑使用SSE将每4个浮点数加到一个总和上，然后在N次迭代之后，总和只是xmm寄存器中4个浮点数的总和，但是当源索引像这样时这不起作用，需要写出10个不同的阵列。

来源

2010-12-04 Dmi

只是为了确保，在重新al代码是`size`和`sum`自动变量在这里？如果它们不是（例如，如果它们是通过指针或引用传入到实际例程中的话），那么可能会由于sum和value之间出现混叠的可能性而导致人为的低效率和/大小`和`id`。 – 2010-12-04 20:28:01

这里将并行化算作一个优化吗？即将数组分割成多个子数组，然后将每个子数组传递给一个单独的线程进行迭代，然后在最后组合结果。对于足够大的阵列，至少在多核机器上可以提供很好的加速。 – 2010-12-04 20:32:02

是的，大小和总和是这样的变量。分区听起来像是一个好主意，我会尝试memcpy将它们分解成四个宿区并且并行运行它们。 – Dmi 2010-12-04 20:35:10

这种循环很难使用SIMD指令进行优化。在大多数SIMD指令集中，不仅没有一种简单的方法来进行这种索引读取（“聚集”）或写入（“分散”），即使存在，这个特定的循环仍然存在您可能遇到的问题两个值在一个SIMD寄存器中映射到相同的id，例如当

id[0] == 0 
id[1] == 1 
id[2] == 2 
id[3] == 0

在这种情况下

，明显的方法（这里的伪代码）

x = gather(size, id[i]); 
y = gather(sum, id[i]); 
x += 1; // componentwise 
y += value[i]; 
scatter(x, size, id[i]); 
scatter(y, sum, id[i]);

不会工作！

你可以通过，如果有一个非常小的一些可能的情况下（例如，假设sum和size只有各3片）通过只是在做蛮力相比，但并没有真正规模。不使用SIMD稍快得到这个

一种方式是通过破坏指令之间的依赖关系使用展开了一下：

int size[10] = { 0 }, size2[10] = { 0 }; 
int sum[10] = { 0 }, sum2[10] = { 0 }; 
for (int i = 0; i < N/2; i++) { 
    int id0 = id[i*2+0], id1 = id[i*2+1]; 
    ++size[id0]; 
    ++size2[id1]; 
    sum[id0] += value[i*2+0]; 
    sum2[id1] += value[i*2+1]; 
} 

// if N was odd, process last element 
if (N & 1) { 
    ++size[id[N]]; 
    sum[id[N]] += value[N]; 
} 

// add partial sums together 
for (int i = 0; i < 10; i++) { 
    size[i] += size2[i]; 
    sum[i] += sum2[i]; 
}

这是否有助于与否虽然取决于目标CPU上。

来源

2010-12-04 20:24:54

那么，你在你的循环中调用id [i]两次。如果你愿意，你可以将它存储在一个变量或一个寄存器int中。

register int index; 
for(int i = 0; i < N; ++i) 
{ 
index = id[i]; 
++size[index]; 
sum[index] += value[i]; 
}

MSDN文档说明这大约寄存器：

寄存器关键字指定变量是要被存储在一机寄存器。微软具体

编译器不接受用户请求寄存器变量; 取而代之的是，当全局寄存器分配优化（/ Oe 选项）打开时，它自己的寄存器选项。但是，与寄存器关键字相关联的所有其他语义都是可以接受的。

来源

2010-12-04 20:22:51

东西你能做的就是用-S标志（或者，如果你不使用gcc当量）进行编译和比较使用-O，-O2和-O3标志的各种组件的输出。优化循环的一种常见方法是做某种程度的展开，对于（一个非常简单的，天真的）例子：

int end = N/2; 
int index = 0; 
for (int i = 0; i < end; ++i) 
{ 
    index = 2 * i; 
    ++size[id[index]]; 
    sum[id[index]] += value[index]; 
    index++; 
    ++size[id[index]]; 
    sum[id[index]] += value[index]; 
}

这将减少一半的cmp指令数。但是，任何半体面优化编译器都会为您做到这一点。

来源

2010-12-04 20:23:10 Tristan

你确定它会有很大的区别吗？可能性是加载“来自外部来源的ID”将花费比合计值更长的时间。

不要优化，直到你知道瓶颈在哪里。

编辑回答评论：你误会了我。如果从硬盘加载ID需要10秒钟，那么在处理列表时花费的秒数是非常重要的。可以说加载需要10秒，处理需要1秒：

您优化了处理循环，所以它需要0秒（几乎不可能，但它说明一个点），那么它仍然需要10秒钟。 11秒真的不是性能受到影响，你最好把你的优化时间集中在实际的数据负载上，因为这很可能是缓慢的部分。

事实上，双缓冲数据加载可能是非常理想的。即加载缓冲区0，然后启动缓冲区1的加载。当缓冲区1正在加载进程缓冲区0.完成时，启动下一个缓冲区的处理，同时处理缓冲区1，等等。这样你可以完全分摊处理成本。

进一步编辑：事实上，您的最佳优化可能来自加载到一组桶中，消除了te计算的“id [i]”部分。然后您可以简单地卸载到3个线程，每个线程使用SSE添加。通过这种方式，你可以让它们全部同时进行，并且，如果你至少有一台三核机器，则可以在10秒内处理整个数据。组织数据以获得最佳处理将始终允许进行最佳优化，IMO。

来源

2010-12-04 20:24:18 Goz

根据你的目标机器和编译器，看看你是否有_mm_prefetch内在属性并给它一个镜头。回到Pentium D时代，只要您在需要数据之前预取几次循环迭代，使用该内在函数的asm指令预取数据是真正的速度胜利。

请参阅here（第95页，在PDF中）了解更多英特尔信息。

来源

2010-12-04 20:41:24 JimR

这个计算是平行的;只需添加

的#pragma OMP parallel_for时减少（+：大小，+：总和）（-fopenmp在GCC）时间表（静态）

立即上述循环，如果您有支持OpenMP不过，我不希望在典型的多核台式机上加快速度;你所做的每个项目的计算量很小，几乎肯定会受到内存带宽的限制。

如果您需要对给定的id映射执行多次求和（即值[]数组的更改频率比id []更频繁），则可以通过预先对值[]元素进行排序来减少内存带宽需求入ID顺序和消除每个元件从ID []取：

为（I = 0，J = 0，K = 0;Ĵ< 10;和[J] + = TMP，J ++）

用于第（k + =大小[J]，TMP = 0;我< K表;我++）

tmp += value[i];

来源

2010-12-05 16:08:30 spillner

优化索引阵列求和

回答

相关问题