Матричное выражение шаблона с известными матрицами

Question

Это мысленное упражнение, а не особая проблема, но я хотел бы услышать ваше мнение. Предположим, что у меня есть матричное выражение DSL с использованием шаблонов (Eigen, ublas и т. Д.).

Теперь предположим, что у меня есть матрицы, которые являются постоянными, например:

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

... и у меня есть какие-то операции с матрицами эти значения с участием среды выполнения:

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

Какие идеи у вас должны реализовать постоянные матрицы, чтобы компилятор мог оптимизировать выражения больше всего? В частности, как мне разрешить оператор (i,j) константе?

Answer 1

Из того, что я понимаю в пространстве проблемы: дан domain-specific language, мы хотим определить минимальное преобразование, что некоторый оператор над данными (например, (i,j)), приводит к поиску константы вместо вычисления математические формулы (например, a*sigma1 + b*sigma2).

Давайте рассмотрим некоторые из возможностей здесь:

• Выполнение математических операций непосредственно

  0th-level реализации. Если явным образом не оптимизирую ваш компилятор, что произойдет, если мы выполним инструкции напрямую?

  Ответ на это зависит. Но на большинстве процессоров исполнение вашего кода упадет на the CPU cache, где ваши сборки и ветвления будут оптимизированы с учетом лучших возможностей ваших ядер. Гибкость этого процесса: actually really cool,, но мы предположим, что вы хотите выйти за пределы этих возможностей и обратиться к константизации своей операции непосредственно в своем коде.

• Bound и захватить пространство с помощью оптимизации с compiler-compiler

  Первый заказ будет связан и захватить возможного ввода и вывода пространства с использованием compiler-compiler. Хотя это будет эффективно решать ваш входной диапазон, ограничивая его только набором желаемых входов и выходов, ничего для исполнения в противном случае. Итак, мы должны двигаться дальше.

• Stringification и Macro Expansion

  Оптимизация второго порядка будет выполнить строку или макро расширения вашего пространства значений непосредственно. Хотя это fraught with corner-cases and surprising implementation-level tar pits, это может быть сделано непосредственно вашим компилятором, если требуется операция. (Смотри также: loop unwinding)

• Ручной вывод и стек переплете выполнимости closed-form expression
  (с использованием, например, таблицы перекодировки)

  Наконец, наша оптимизация третьего порядка будет оценка ваше пространство напрямую.Для этого требуется, чтобы вы хорошо определили closed-form relation с ограниченным пространством ввода и вывода для эффективной работы. Если это отношение не может быть определено или не имеет границ, you're out of luck и следует рассмотреть вопрос о сохранении вашей текущей реализации, если, как известно, не существует лучшего.

Из этих методов оптимизации, наиболее применимы к linear algebraic operations являются последними двумя, учитывая проблемы ограничивающий, что вы описали. Поскольку большинство операций, таких как операция преобразования матрицы, вращения и масштабирования, детерминированы по своему характеру, вы действительно можете эффективно оптимизировать и ограничить свое пространство.

Для получения более теоретического ответа я рекомендую обратиться к http://cs.stackexchange.com, http://cstheory.stackexchange.com и http://math.stackexchange.com. У обоих есть много и много потоков, посвященных decidability и доказательству закрытой формы, polynomial solutions для целых классов уравнений.

Answer 2

Хорошо, это ужасно, но связано с моим комментарием на исходное сообщение.

Используя эту структуру, вы можете определить соответствующие операции, которые вам нужны, но для выполнения всех необходимых специализаций потребуется много работы. Вы также можете поменять местами свои строки/столбцы.

Определение матриц в конце, конечно, не так элегантно, как в исходном посте, но, возможно, это может быть улучшено, особенно с использованием «auto» в 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>() );