4

这是一个思考练习，不是一个特定的问题，但我想听听你的意见。假设我有一些使用模板（Eigen、ublas 等）的矩阵表达式 DSL。

现在假设我有一些常量矩阵，例如：

Matrix2 sigma1 = {{0,1}, {1,0}};
Matrix2 sigma2 = {{0,i}, {-i,0}};
... etc

...而且我对那些涉及运行时值的矩阵进行了一些操作：

a*sigma1 + b*sigma2; // a,b runtime

你有什么想法来实现常量矩阵，以便编译器可以最优化表达式？特别是，如何将(i,j)运算符解析为常量？

4

2 回答 2

4

根据我对问题空间的理解：给定特定领域的语言，我们希望确定最小转换，以便数据上的某些运算符（例如，(i,j)）导致查找常量而不是计算数学公式（例如，a*sigma1 + b*sigma2）。

让我们在这里探索一些可能性：

  • 直接执行数学运算

    0 级实现。如果您的编译器没有显式优化，如果我们直接执行指令会发生什么？

    答案是视情况而定。但是，在大多数处理器上，您的代码执行将落在CPU 缓存上，您的程序集和分支执行将在其中优化到您的内核的最佳能力。该过程的核心实际上非常酷，但我们假设您想要超越这些功能并直接在代码中解决操作的恒定化问题。

  • 使用编译器-编译器绑定和捕获空间

    一阶优化是使用compiler-compiler绑定和捕获可能的输入和输出空间。虽然这将有效地解决您的输入范围，将其限制为您想要的一组输入和输出，但它对性能没有任何帮助。所以，我们必须继续前进。

  • 字符串化和宏扩展

    二阶优化将是直接执行值空间的字符串或宏扩展。虽然这充满了极端情况和令人惊讶的实现级焦油坑，但如果需要该操作，可以直接由编译器完成。（另见：循环展开）

  • 封闭式表达式 的手动推导和堆栈绑定可满足性
    （例如，使用查找表）

    最后，我们的三阶优化将直接限制您的空间。这要求您具有定义明确的封闭式关系以及有界输入和输出空间才能有效地工作。如果这种关系无法确定或没有界限，那么您就不走运了，如果不知道存在更好的实现，则应该考虑保留当前的实现。

在这些优化技术中，最适用于线性代数运算的是后两种，考虑到您所描述的问题范围。因为大多数操作，例如矩阵平移、旋转和缩放操作本质上是确定性的，所以您确实可以有效地优化和限制您的空间。

对于更理论的答案，我建议咨询http://cs.stackexchange.com、http://cstheory.stackexchange.com和http://math.stackexchange.com。两者都有许多线程致力于整个方程类的封闭式多项式解的可判定性和证明。

于 2012-04-07T00:49:15.760 回答
2

好的，这很可怕，但与我对原始帖子的评论有关。

使用这种结构应该可以定义您需要的相关操作，但是编写所有适当的专业化将是很多工作。您可能还希望交换行/列。

最后定义矩阵肯定不像你原来的帖子那样优雅，但也许这可以改进，特别是在 C++11 中使用“自动”。

//-----------------------------------------------------------------------------
struct Unused {};

struct Imaginary {
    Imaginary() {}
    Imaginary(Unused const& unused) {}
};
struct MinusImaginary {
    MinusImaginary() {}
    MinusImaginary(Unused const& unused) {}
};

//-----------------------------------------------------------------------------
template <int I, int F = 0>
struct Fixed {
    Fixed() {}
    Fixed(Unused const& unused) {}
};

//-----------------------------------------------------------------------------
struct Float
{
    Float(float value) : value_(value) {}
    const float value_;
};

//-----------------------------------------------------------------------------
template <typename COL0, typename COL1>
struct Vector2
{
    typedef COL0 col0_t;
    typedef COL1 col1_t;

    template <typename T0, typename T1>
    Vector2(T0 const& t0, T1 const& t1)
        : col0_(t0)
        , col1_(t1)
    {}

    COL0 col0_;
    COL1 col1_;
};

//-----------------------------------------------------------------------------
template <typename ROW0, typename ROW1>
struct Matrix2
{
    typedef ROW0 row0_t;
    typedef ROW1 row1_t;

    Matrix2()
        : row0_(Unused(), Unused())
        , row1_(Unused(), Unused())
    {
    }
    template <typename M00, typename M01, typename M10, typename M11>
    Matrix2(M00 const& m00, M01 const& m01, M10 const& m10, M11 const& m11)
        : row0_(m00, m01)
        , row1_(m10, m11)
    {
    }

    ROW0 row0_;
    ROW1 row1_;
};

//-----------------------------------------------------------------------------
Matrix2<
    Vector2< Fixed<0>, Fixed<1> >,
    Vector2< Fixed<1>, Fixed<0> > 
> sigma1;

const float f = 0.1f;

//-----------------------------------------------------------------------------
Matrix2<
    Vector2< Fixed<0>, Imaginary >,
    Vector2< MinusImaginary, Fixed<0> > 
> sigma2;

//-----------------------------------------------------------------------------
Matrix2<
    Vector2< Fixed<0>, Float >,
    Vector2< Float, Fixed<0> > 
> m3(Unused(), 0.2f,
     0.8f, Unused());


// EDIT: Nicer initialization syntax in c++11

//-----------------------------------------------------------------------------
template <typename M00, typename M01, typename M10, typename M11>
Matrix2< Vector2<M00, M01>, Vector2<M10, M11> >
MakeMatrix(M00 const& m00, M01 const& m01, M10 const& m10, M11 const& m11)
{
    return Matrix2< Vector2<M00, M01>, Vector2<M10, M11> >(m00,m01,m10,m11);
}

auto m4 = MakeMatrix(Fixed<0>(),  Float(0.2f), 
                     Float(0.8f), Fixed<0>()  );
于 2012-04-12T12:44:57.657 回答