10

我有一个涉及矩阵的小型 c# 项目。我正在处理大量数据，方法是将其拆分为 n 长度的块，将卡盘视为向量，并乘以 Vandermonde** 矩阵。问题是，根据条件，卡盘的大小和相应的 Vandermonde** 矩阵可能会有所不同。我有一个易于阅读的通用解决方案，但太慢了：

    public byte[] addBlockRedundancy(byte[] data) {
        if (data.Length!=numGood) D.error("Expecting data to be just "+numGood+" bytes long");

        aMatrix d=aMatrix.newColumnMatrix(this.mod, data);
        var r=vandermonde.multiplyBy(d);
        return r.ToByteArray();
    }//method

这可以在我的 i5 U470 @ 1.33GHz 上每秒处理大约 1/4 兆字节。我可以通过手动内联矩阵乘法来加快速度：

        int o=0;
        int d=0;
        for (d=0; d<data.Length-numGood; d+=numGood) {
            for (int r=0; r<numGood+numRedundant; r++) {
                Byte value=0;
                for (int c=0; c<numGood; c++) {
                    value=mod.Add(value, mod.Multiply(vandermonde.get(r, c), data[d+c]));
                }//for
                output[r][o]=value;
            }//for
            o++;
        }//for

这可以处理大约 1 兆每秒。

（请注意，“mod”是对 GF(2^8) 模我最喜欢的不可约多项式进行运算。）

我知道这可以变得更快：毕竟，Vandermonde** 矩阵大多为零。我应该能够创建一个例程，或者找到一个例程，它可以获取我的矩阵并返回一个优化的方法，该方法将有效地将向量乘以给定的矩阵，但速度更快。然后，当我给这个例程一个 5x5 Vandermonde 矩阵（单位矩阵）时，根本不需要执行任何算术运算，只是复制了原始数据。

** 请注意：我使用的术语“范德蒙德”实际上是指一个身份矩阵，其中附加了范德蒙德矩阵中的一些行（见评论）。这个矩阵非常棒，因为所有的零，而且如果你删除足够多的行（你选择的）使它成为正方形，它就是一个可逆矩阵。而且，当然，我想使用相同的例程将这些倒置矩阵中的任何一个转换为优化的指令系列。

我怎样才能使这个矩阵乘法更快？

谢谢！

（编辑以纠正我对范德蒙德矩阵的错误）

4

4 回答 4

3

也许您可以使用Reflection.Emit在运行时定义矩阵接口并构建实现。

IMatrix m = MatrixGenerator.CreateMatrix(data);

m.multiplyBy(...)

在这里，MatrixGenerator.CreateMatrix将创建一个定制的 IMatrix 实现，具有完整的循环展开和进一步的代码修剪（0 单元格、身份等）。MatrixGenerator.CreateMatrix可能会缓存矩阵以避免稍后为同一组数据重新创建它。

于 2010-12-29T10:44:31.087 回答
3

我见过使用 Reflection.Emit 的解决方案，也见过涉及 TPL 的解决方案。在大多数情况下，真正的答案是，您希望通过 P/Invoke 使用现有的非托管库，例如英特尔 MKL。或者，如果您使用的是 GPU，则可以使用 GPGPU 方法，这样会快很多。

是的，SSE 与多核处理一起是在 CPU 上完成的最快方法。但我不建议您编写自己的算法 - 相反，去寻找已经存在的东西。最有可能的是，它最终会成为一个 C++ 库，可能带有 C# 包装器。

于 2010-12-29T11:47:38.397 回答
1

虽然它不会加快数学运算速度，但您至少可以将所有内核与 .Net 4.0 中的 Parallel.For 一起使用。微软链接

于 2010-12-29T16:49:02.427 回答
0

从数学的角度

您可以查看特征空间、特征向量、特征值。我不确定您的应用程序是做什么的，以及它是否会有所帮助。

你可以看看LU分解。

以上所有主题都可以在维基百科上找到

从编程的角度

您可以尝试 SIMD，但它们是为 4x4 矩阵设计的，用于对 3D 空间进行均匀变换，主要用于计算机图形。

您可以为最常见的维度编写特殊算法。

可以在 c# 中使用 SSE 吗？

于 2010-12-29T10:41:03.050 回答