Optimierung von Exprssion-template-ausdrücken

otze

Hi Leute!

Zuerstmal das Problem an einem einfachen Beispiel Illustriert.

Bei Matrix-Vektor Operationen kann man viel gewinnen, wenn man Ausdrücke passend umordnet. Ein Bispiel ist der Matrix-Ausdruck

$C=I+AA^T$
wobei I die Identität und A eine große Matrix ist. Dieser Ausdruck lässt sich straightforward berechnen:

C=I
C+=AA^T

nun schaue ich mir aber den folgenden Ausdruck an:

$y=(I+AA^T)x$
wobei y nun ein Vektor ist. Auf einmal ändert sich die optimale Berechnung zu:

t = A^Ty
y = At
y+=x

Dies ist extrem viel schneller, weil ich ein matrix-matrix produkt gegen ein Matrix-Vektor produkt tausche. ausserdem wird weniger Speicher gebraucht, weil ich C nicht explizit berechnen muss.

Nun würde ich das gerne meiner linearen Algebra beibringen, weil es Fälle gibt, bei denen ein Ausdruck nicht transformiert werden kann. Ein Beispiel wäre, wenn ich den Ausdruck für C einer Funktion übergebe, die dann mit der Matrix ein Matrix-Vektor Produkt berechnet.

Der Ausdruck für C wird bei mir (vereinfacht) über expression-templates durch den folgenden Typ dargestellt:

matrix_plus<
  Identity,
  matrix_product<Matrix,transpose<Matrix> > 
>

und der Vektor Ausdruck naiv als

matrix_vector_prod<
    matrix_plus<
        Identity,
        matrix_product<Matrix,transpose<Matrix> > 
    >,
    Vector
>

und der optimale Ausdruck hat die Form

vector_plus<
    Vector, 
    matrix_vector_prod<
        Matrix, 
        matrix_vector_prod< transpose<Matrix>, Vector > 
    > 
>

nur wie kann ich jetzt a) sinnvolle Regeln definieren, die den Ausdruck vereinfachen und b) wie kann ich die Transformation dann implementieren?

Irgendwelche Ideen seitens der Cracks? Ich tendiegere gerade zu Substitutionsregeln, aber die schiere Anzahl möglicher Fälle erschreckt mich dann doch sehr. Ein Algorithmischer Ansatz der ohne konkretes Wissen der Typen auskommt wäre mir lieber.

Die Substitutionsregeln wären vermutlich das einfachste umzusetzen, und compilezeitmässig am schnellsten. In TMP-Pseudocode:

deep_simplify<T> =
  while !is_same<T, simplify<T> >
    T = simplify<T>
  foreach U in T::operands:
    U = deep_simplify<U>

// Substitutionsregeln
simplify<T> = identity

simplify<matrix_vector_prod<...> > = vector_plus<...>

Damit wird der Ausdruck schön linear vereinfacht.

Ein algorithmischer Ansatz würde in Richtung Fallunterscheidungen laufen.

cost<T> = // Anzahl nötige Multiplikationen für T (angenommen, die Grösse steht fest)

better<T1, T2> = std::conditional<(cost<T1> < cost<T2>), T1, T2>

simplify<T> = identity

simplify<matrix_vector_prod<Identity,T> > = T;
simplify<matrix_vector_prod<T,Identity> > = T;

simplify<matrix_vector_prod<matrix_plus<A,B>,C>> = better<
  simplify<matrix_plus<matrix_vector_prod<A,C>,matrix_vector_prod<B,C> >,
  matrix_vector_prod<simplify<matrix_plus<A,B>>,simplify<C>>
>

Machen würde ich das erst ab C++11. Dann kannst du das Expressiontemplate durchgehen und jede Variable mit einem eindeutigen Index versehen.
( matrix_id<1> , matrix_id<2> , ...). Dann simplifizieren und nachher wieder zurückeinsetzen (

tuple all_arguments = ...; // Liste
  // zwei Listen lassen sich mit tuple_cat zusammenführen
tuple_get<matrix_id::id>(all_arguments) // Id durch Parameter ersetzen

)

knivil

otze schrieb:

wobei y nun ein Vektor ist. Auf einmal ändert sich die optimale Berechnung zu:
t = A^Ty
y = At
y+=x

Du meinst wohl

t = A'x

Auf einmal ändert sich die optimale Berechnung zu

Wie auf einmal? Du rechnest ja was komplett anderes aus.

otze

@xprssn Ja, an so etwas habe ich auch gedacht, auch wenn ich C++11 nicht verwenden kann. Aber ich vermute, dass die Regeln nicht so einfach umsetzbar sind. Das Problem ist, das die Genauen Kosten nicht bekannt sind, sondern nur die asymptotischen Kosten.

Das Problem, das ich mit einfachen Regelbasierten Ansätzen habe ist, das sie nicht skalieren, einfach weil es zu viele möglichkeiten gibt.

Wenn ich mir einen komplexeren Ausdruck betrachte:

$y=(AA^T+B+C)^T x$

Dann kann es sein, das AA^T so tief im Templateausdruck versteckt ist, das ich kein Substitutionsregel mit der nötigen Tiefe haben kann.

Das einzige was dann ginge sind Brute-Force Methoden wie:

simplify<matrix_vector_prod<matrix_add<A,B>, x> = 
    simplify < vector_add<
         simplify <matrix_vector_prod<A,x> >,
         simplify <matrix_vector_prod<B,x> >
    > //(1)

simplify<vector_matrix_prod<x, matrix_add<A,B> > = 
    simplify < vector_add<
         simplify <vector_matrix_prod<x,A> >,
         simplify <vector_matrix_prod<x,B> >
    >//(2)

simplify<matrix_vector_prod<transpose<A>, x> = 
    simplify<vector_matrix_prod<x,A> > //(3)

simplify<vector_matrix_prod<x,transpose<A>> = 
    simplify<matrix_vector_prod<A,x> > //(4)

simplify<matrix_vector_prod<matrix_matrix_prod<A,B>, x>=
    simplify<matrix_vector_prod<
        simplify <A>,
        simplify <matrix_vector_prod<B,x>
    > //(5)
simplify<vector_matrix_prod<x,matrix_matrix_prod<A,B> >=
    simplify<vector_matrix_prod<
        simplify <vector_matrix_prod<x,A>
        simplify <B>,
    > //(6)

Und die Auswrtung des Ausdrucks wäre dann (Für den Vektor x lass ich das transponiertzeichen ^T weg, weil vektoren in den regeln oben keine orientierung haben):

(AA^T+B+C)^T x \xrightarrow{(3)} x(AA^T+B+C) \xrightarrow{(2)} xAA^T+x(B+C) \xrightarrow{(2)} xAA^T+xB+xC \xrightarrow{(5)} (xA)A^T+xB+xC \xrightarrow{(4)} A(xA)+xB+xC

Und dann wäre die optimale Berechnung:

t=xA
y=At 
y+=xB
y+=xC

Und das ist noch ein recht einfaches Beispiel, meine lineare Algebra kann leider noch ein wenig mehr. Die Anzahl der Regeln sollte exponentiell mit der Anzahl der Operationen wachsen. Und dann stellen sich auf einmal Fragen wie: "gibt es zyklen in den Regeln?" "ist der entstehend Ausdruck optimal?" "ist das Resultat eindeutig?" usw.

Ein weiteres ungelöstes Problem ist noch, wie ich die Ausdrücke dann überhaupt transformiere. Selbst wenn ich den Typ des Ausdrucks optimiere, muss ich ihn hinterher noch zusammenbauen.

Angenommen das Standardinterface für einen unären Ausdruck (zum Beispiel transpose<A>) sieht so aus:

template<class A>
struct Transpose{
    Transpose(A):m_expression(A){}

    A const& expression()const{
         return m_expression;
    }
private:
    A m_expression;
};

und für einen binären ausdruck dann equiavalent mit jeweils 2 Ausdrücken. Wie würdet ihr dann aus dem ursprünglichen Ausdruck den neuen Ausdruck konstruieren? Es gäbe da zwei Möglichkeiten: entweder auf dem selben Weg wie jetzt die Regeln angewandt werden, das heißt der Ausdruck wird für jede Regelanwendung einmal neu konstruiert. Dies würde die Konstruktion des Ausdrucks vereinfachen, man müsste aber darauf hoffen, das der Compiler das optimiert kriegt. Oder die einzelnen Blätter werden enumeriert und über die transformationen gespeichert, welche Blätter am Ende wo gebraucht werden.

Im ersten Fall hätte man dann zum Beispiel noch eine Funktion wie:

//implementation von (1)
//constructs new tree simplify((A+B)x)-> simplify(simplify(Ax)+simplify(Bx)) 
template<class A,class B, class x>
typename simplify<matrix_vector_prod<matrix_add<A,B>, x > >::type
construct_simplified(matrix_vector_prod<matrix_add<A,B>, x > e){
    typedef typename simplify<matrix_vector_prod<A,x> >::type LeftExpression;
    typedef typename simplify<matrix_vector_prod<B,x> >::type RightExpression;
    //apply inner rule for the left expression
    //simplify<matrix_vector_prod<A,x> >
    matrix_vector_prod<A,x> unsimplified_left(
        e.expression1().expression1(),//A
        e.expression2()//x
    );
    LeftExpression left = construct_simplified(unsimplified_left);
    //apply inner rule for the right expression
    //simplify<matrix_vector_prod<B,x> >
    matrix_vector_prod<B,x> unsimplified_left(
        e.expression1().expression2(),//B
        e.expression2()//x
    );
    RightExpression right = construct_simplified(unsimplified_right);

    //construct resulting whole expression and simplify it again
    vector_add<LeftExpression,RightExpression> simplified_expression(left,right);
    return construct_simplified(simplified_expression);
}

Sieht mir nach echt viel Arbeit aus...

@knivil ich verstehe dein Problem nicht, halte dich aber für zu intelligent als das ich das unter Trollen abstempeln will. Ich geh erstmal von Morgenmüdigkeit vor dem ersten Kaffee aus. Bei einer ungenannten Sprache über Syntax zu streiten ist aber genauso sinnvoll, wie im nächsten Absatz einen Nebenkriegsschauplatz über Semantik zu eröffnen. Abr wenn du willst, substitutiere ^T durch '. Ich machs nicht.

Wie sehen in der Regel dein Matrizen aus? Schwachbesetzt? Band? Obere-/Unterere-Δ-matrix?

knivil

Ich habe Matlab-Syntax verwendet weil fuer ^T zu faul war und ich bezog mich auf das y in der Gleichung t = A'y das eigentlich t = A'x heissen sollte.

Hauptproblem wird wohl sein, dass mehrere Wege zum Ziel fuehren. Beispiel:
ABx -> ((Bx)'A')' -> t = Bx; u = tA' y = u'
ABx -> (A(Bx)) -> t = Bx; y = At

in beiden Varianten kommen nur noch dein gewuenschten Basisoperationen vor. Wie entscheidest du, welcher Pfad als erstes ausprobiert wird? Wie sieht die Verallgemeinerung beispielsweise fuer Tensoren aus?

vektoren in den regeln oben keine orientierung haben

Viele Physiker wuerden jetzt vielleicht aufschreien, co- und kontravariant.

otze

Unterschiedlich.

Meistens dicht, manchmal gibt es dichte und spärliche Teile (unstrukturiert). obere/untere dreiecksmatrizeen kommen so gut wie nie ausserhalb der üblichen Solver vor, banded matrizen werden gar nicht unterstützt.

Ich besitze für jeden Matrixtyp bereits eigene operationen die dann im letzten Schritt bei der Transformation Ausdruck->Auswertereihenfolge gewählt werden.

Mir geht es gerade um den grundsätzlichen Aufbau von so einer Ausdrucksoptimierung. Natürlich kann ich noch beliebig Metainformationen der einzelnen Argumente mit einfließen lassen.

@Knivil ahh okay :). Sorry.

Die Bibliothek richtet sich nicht an Physiker, sondern Maschinenlerner. Ich geb dir Recht, das es in der Formelschreibweise einen Unterschied macht und das ziehe ich normalerweise auch durch. Hier hätte ich aber bei der Ausformulierung Probleme gehabt, weil eine Regel dann zu einer ziemlich "komischen" Vereinfachung geführt hätte - eine ziemlich große Menge an transponiertzeichen

Ansonsten:
Ja es kann mehrere Wege geben. Für mich wäre dein Beispiel nicht anwendbar, weil ich mein vektoren nicht transponieren kann und weil meine Regeln Ausdrücke mit wenig transponierten bevorzugen:

((Bx)'A')' -> A(Bx) -> t=Bx; y=At

Im Allgemeinen stimme ich dir aber zu. Wenn im jetzigen Ansatz 2 Regeln gleich gut matchen ist der Aufruf von simplify mehrdeutig. Wäre sicher spannend zu sehen, ob man das beweisen kann

Die Verallgemeinerung auf Tensoren hingegen hat untergeordnete Relevanz, weil ich die nicht einmal unterstütze ;). Wenn ich mal Tensoren haben sollte, kann ich mir dafür ja was überlegen, aber dafür müsste ich mich darin erst einmal einlesen

knivil

Vielleicht gibt es hier Anregungen: http://cpp-next.com/archive/2011/01/expressive-c-expression-optimization/ und dann gibt es ja noch blitz++.

otze

danke für den Link.