元素矢量mutiplication

Question

对于以下两个n元素整数向量乘法的替代方法,可以更快(在代码所需的时间方面):

{
// code for obtaining two n element int vectors, a and b
}
int temp = 0;  // a temporary variable
for (int ii = 0; ii < n; ++ii)
    temp += a[ii]*b[ii];

编辑:收到几个不错的想法.我必须检查每一个,看看哪一个是最好的.当然,每个回答都告诉我一些新的东西.

Answer 1

我能看到在C++中加快速度的唯一方法是修复"循环携带依赖",这意味着每次迭代必须等到前一个临时值可用于总和.这可以通过展开和使用几个累积变量来完成:

int t0=0, t1=0, t2=0, t3=0;
for (int ii = 0; ii < n; ii += 4) {
    t0 += a[ii]*b[ii];
    t1 += a[ii+1]*b[ii+1];
    t2 += a[ii+2]*b[ii+2];
    t3 += a[ii+3]*b[ii+3];
}
int temp = t0 + t1 + t2 + t3;

现代处理器可以在每个周期执行多个操作,但前提是它们没有依赖性.在我的系统上,这大约提高了20%.注意:n必须是4的倍数,或者你需要添加一个循环"epilog"来完成剩下的元素.测试和测量!我不知道4是否是"正确"的展开量.

通过调用特定于处理器的SIMD内在函数可以获得更多改进,但这不是标准的C++.