指数移动平均线

Question

我有一个指数移动平均值被调用了数百万次,因此是我代码中最昂贵的部分:

double _exponential(double price[ ], double smoothingValue, int dataSetSize)
{
    int i;
    double cXAvg;
    cXAvg = price[ dataSetSize - 2 ] ;  

    for (i= dataSetSize - 2; i > -1; --i)   
        cXAvg += (smoothingValue * (price[ i ] - cXAvg)) ;

     return ( cXAvg) ;
}

是否有更有效的方法对此进行编码以加快速度？我有一个多线程的应用程序,我使用的是Visual C++.

谢谢.

Answer 1

哎哟!

当然,多线程可以提供帮助.但您几乎可以肯定地提高单线程机器的性能.

首先,你是在错误的方向计算它.只有最现代化的机器才能进行负步幅预取.几乎所有的机械装置都能更快地完成单元步伐.即改变阵列的方向,使您从低到高而不是从高到低扫描几乎总是更好.

接下来,重写一下 - 请允许我缩短变量名称以便更容易输入:

avg = price[0]

for i
    avg = s * (price[i] - avg)

顺便说一句,我将开始使用shorthands p进行价格和s进行平滑,以节省打字.我很懒...

avg0 = p0
avg1 = s*(p1-p0)
avg2 = s*(p2-s*(p1-p0)) = s*(p2-s*(p1-avg0))
avg3 = s*(p3-s*(p2-s*(p1-p0))) = s*p3 - s*s*p2 + s*s*avg1

而且,一般而言

avg[i] = s*p[i] - s*s*p[i-1] + s*s*avg[i-2]

预先计算s*s

你可能会这样做

avg[i] = s*p[i] - s*s*(p[i-1] + s*s*avg[i-2])

但它可能更快

avg[i] = (s*p[i] - s*s*p[i-1]) + s*s*avg[i-2])

然后,avg [i]和avg [i-2]之间的等待时间是1乘以加法,而不是avg [i]和avg [i-1]之间的减法和乘法.比我快两倍多.

通常,您希望重写重复,以便尽可能早地根据avg [j]计算avg [i],而无需填充机器(执行单元或寄存器).
你基本上会做更多的乘法运算,以便在关键路径上获得更少的倍数链(和减法数).从avg [i-2]跳到avg [i [很容易,你可以做三个和四个.究竟有多远取决于您的机器是什么,以及您拥有多少个寄存器.

以及浮点加法器和乘法器的延迟.或者,更好的是,您拥有的组合乘法 - 加法指令的风格 - 所有现代机器都有它们.例如,如果MADD或MSUB长度为7个周期,即使您只有一个浮点单元,也可以在其阴影中进行多达6个其他计算.完全流水线.等等.如果在每个其他循环中流水线,则较少,这对于较旧芯片和GPU的双精度是常见的.汇编代码应该是软件流水线的,以便不同的循环迭代重叠.一个好的编译器应该为你做,但你可能不得不重写C代码以获得最佳性能.

顺便说一下:我并不是说你应该创建一个avg []数组.相反,如果以avg [i-2]计算avg [i],则需要两个平均值,依此类推.如果你愿意,你可以使用avg [i]数组,但我认为你只需要2或4个avgs,创造性地称为avg0和avg1(2,3 ......),然后"旋转"它们.

avg0 = p0
avg1 = s*(p1-p0)
/*avg2=reuses*/avg0 = s*(p2-s*(p1-avg0))
/*avg3=reusing*/avg3 = s*p3 - s*s*p2 + s*s*avg1
for i from 2 to N by 2 do
    avg0 = s*p3 - s*s*p2 + s*s*avg0
    avg1 = s*p3 - s*s*p2 + s*s*avg1

这种技巧,将累加器或平均值分成两个或更多,结合重复的多个阶段,在高性能代码中很常见.

哦,是的:预先计算s*s等

如果我做得对,无限精确,这将是相同的.(请仔细检查我.)

但是,在有限精度FP中,由于不同的舍入,您的结果可能会有所不同,希望只是略有不同.如果展开是正确的并且答案明显不同,那么您可能具有数值不稳定的算法.你是那个知道的人.

注意:浮点舍入错误将改变答案的低位.两者都是因为重新排列代码和使用MADD.我认为这可能没问题,但你必须做出决定.

注意:avg [i]和avg [i-1]的计算现在是独立的.因此,您可以使用SIMD指令集,如Intel SSE2,它允许一次在128位宽寄存器中对两个64位值进行操作.在具有足够ALU的机器上,这几乎可以达到2倍.

如果你有足够的寄存器用avg [i-4]来重写avg [i](我相信你在iA64上做的话),那么如果你有权使用像256位AVX这样的机器,你就可以达到4倍宽.

在GPU上...你可以进行更深层次的重复,用avg [i-8]重写avg [i],依此类推.

某些GPU具有将AX + B或甚至AX + BY计算为单个指令的指令.虽然32位比64位精度更常见.

在某些时候我可能会开始问:你想一次以多种价格做这件事吗？这不仅可以帮助您进行多线程处理,还可以在GPU上运行.并使用宽SIMD.

次要的晚期增加

我有点尴尬,没有将霍纳的规则应用于像

avg1 = s*p3 - s*s*p2 + s*s*avg1

给

avg1 = s*(p3 - s*(p2 + avg1))

效率稍高.四舍五入的结果略有不同.

在我的辩护中,任何体面的编译器都应该为你做这件事.

但是Hrner的规则使得依赖链在乘法方面变得更深.您可能需要将循环展开并流水线化几次.或者你可以做到

avg1 = s*p3 - s2*(*p2 + avg1)

你预先计算的地方

s2 = s*s