计算向量表达式的范数|| aW + bX + cY ||

Question

我是博士生.在我的论文的介绍中,我对线性代数工具的表现力和表现之间的妥协深感兴趣.

举个简单的例子,我使用向量表达式的范数计算.我的例子的C代码是:

float normExpression3(float a, float *W, float b, float *X, float c, float*Y){
double norm = 0;
for (int i=0; i<n; ++i) // n in [3e6; 2e8]
{
    float tmp = a*W[i]+b*X[i]+c*Y[i];
    norm+=tmp*tmp;
}
return sqrtf(norm);

}

我比较了用不同技术实现的性能.由于矢量很大(几百万个元素),性能受到存储器带宽的限制.但是,不同方法之间存在巨大差异.

我编写的优化C版本不具有表现力(一个新函数必须写为第四个向量)并且非常难看(线程化和向量化)但实现了6.4 GFlops.另一方面,MATLAB代码非常好:

result = norm(a*W+b*X+c*Y)

但只能达到0.28 GFlops.

C++模板表达式点菜闪电++提供既表达性和表演给用户(6.5 GFLOPS).

作为我的分析的一部分,我想知道功能语言如何与这些方法进行比较.我想在Haskell或OCaml中展示一个例子(AFAIK,两者都很适合这种操作).

我不知道这些语言.我可以了解他们提供我的例子,但这不是一个公平的比较:我不确定是否能够提供一个允许表现力和表现的实现.

所以我的两个问题是:1)哪种语言最适合？2)如何在不影响实现的一般性的情况下有效地计算向量表达式的范数？

提前,谢谢!

威尔弗里德K.

---

编辑:纠正的类型norm累加器float到double

Answer 1

值得一提的是,以下是您的函数的OCaml版本:

let normExpression3 a w b x c y =
    let n = Array.length w in
    if not (n = Array.length x && n = Array.length y)
        then invalid_arg "normExpression3";
    let (@) = (Array.unsafe_get : float array -> int -> float) in
    let rec accum a w b x c y n i norm =
        if i = n then sqrt norm else
        let t = a *. (w @ i) +. b *. (x @ i) +. c *. (y @ i) in
        accum a w b x c y n (i + 1) (norm +. t)
    in accum a w b x c y n 0 0.

它为性能提供了一些补贴,即:

• 未经检查的数组访问(或者更确切地说,数组边界检查从循环中手动提升)
• 单态阵列访问
• 递归内循环,以避免装箱和拆箱浮动累加器
• 内部循环的Lambda提升以避免引用封闭值

应该针对封闭的内循环检查最后的优化,因为如此多的参数寄存器溢出可能超过引用封闭参数的成本.

请注意,通常不会对这种优化感到烦恼,除非有人在benchark中竞争;-)注意,您还需要使用64位OCaml进行测试,因为数组限制为4兆元素.