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を使用して可能な入力および出力スペースをバインドおよびキャプチャすることです。これは入力範囲に効果的に対処し、必要な入力と出力のセットのみに制限しますが、それ以外の場合はパフォーマンスには何の影響もありません. ですから、先に進まなければなりません。

  • 文字列化とマクロ展開

    二次最適化は、値空間の文字列またはマクロ展開を直接実行することです。これにはまれなケースと驚くべき実装レベルのタール ピットが伴いますが、操作が必要な場合は、コンパイラで直接行うことができます。(参照:ループの巻き戻し)

  • 閉じた形式の式 の手動導出とスタック バインド充足可能性
    (たとえば、ルックアップ テーブルを使用)

    最後に、3 次最適化は、スペースを直接バインドすることです。これには、効果的に機能するために、制限された入力および出力スペースを持つ明確に定義された閉じた形式の関係が必要です。この関係を決定できない場合、または境界がない場合は運が悪く、より良い実装が存在しないことがわかっている場合は、現在の実装を維持することを検討する必要があります。

これらの最適化手法のうち、線形代数演算に最も適用できるのは、説明した問題の範囲を考えると、後者の 2 つです。行列の移動、回転、スケール操作などのほとんどの操作は本質的に決定論的であるため、スペースを効果的に最適化し、バインドすることができます。

より理論的な答えについては、http://cs.stackexchange.com、http://cstheory.stackexchange.com、およびhttp://math.stackexchange.comを参照することをお勧めします。どちらも、決定可能性と、方程式のクラス全体に対する閉じた形式の多項式解の証明に専念する非常に多くのスレッドを持っています。

于 2012-04-07T00:49:15.760 に答える
2

わかりました、これは恐ろしいことですが、元の投稿に対する私のコメントに関連しています。

この構造を使用すると、必要な関連操作を定義できるはずですが、適切な特殊化をすべて記述するには多くの作業が必要になります。行/列を交換することもできます。

最後に行列を定義することは、元の投稿ほどエレガントではありませんが、特に C++11 で「auto」を使用すると、おそらく改善される可能性があります。

//-----------------------------------------------------------------------------
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 に答える