performance - 指数移动平均线

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)

顺便说一句，我将开始使用速记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]
在不填满机器(执行单元或寄存器)的情况下，尽可能早地返回j。
基本上，您总体上会做更多的乘法运算，以便在关键路径上获得更少的倍数链(和减法)。
从avg [i-2]跳转到avg [i [很容易，您可能可以执行三个和四个操作。到底有多远
取决于您的机器是什么，以及您有多少个寄存器。

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

顺便说一句:我并不是要建议您创建一个avg []数组。相反，如果根据avg [i-2]计算avg [i]，则需要两个平均值，依此类推。
您可以根据需要使用avg [i]数组，但我认为您只需要创造性地将avg0和avg1(2，3 ...)称为2或4个avg，然后对其进行“旋转”。

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)，那么您可以将其宽4倍，
如果您可以使用256位AVX之类的机器。

在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))

效率更高。四舍五入的结果略有不同。

为了我的辩护，任何体面的编译器都应为您执行此操作。

但是赫纳的规则使依存关系链在乘数方面更深。
您可能需要多次展开循环并通过管道进行循环。
或者你可以做

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

您在哪里预先计算

s2 = s*s