Matrixmultiplikation auf dem ARM

[Jens B. (meddle)]

Hallo,
eine einfache int-Multiplikation dauert auf dem ARM7-Controller 4Zyklen.


ich möchte nun eine Vektor-Matrix Multiplikation durchführen, dafür habe 
ich mir folgende Funktion geschrieben:

void vecMult(Vec *Ergebnis, Vec A, Mat B){
  int i,j;
  MatrixValue temp;
  assert(A.Spalten  == B.Zeilen);
  assert(B.Spalten  == Ergebnis->Spalten);

  for(i=0;i<Ergebnis->Spalten;i++){
    temp=0;
    for(j=0;j<A.Spalten;j++){
      temp += A.m[j]*B.m[j][i];
    }
    Ergebnis->m[i]=temp;
  }

}

In dem schritt, wo temp das nächste Produkt aufaddiert wird, dauert die 
Multiplikation nun ca. 22 Zyklen.

Dieser Mehraufwand liegt sicher an den drei Indizierungen des Vektors 
und der Matrix.

Kann man das beschleunigen, in dem man statt der Array-Schreibweise 
[m][n] mit Pointern und Doppelpointern rechnet? Oder vl. mit 
Assembler-code?
wie müsste sowas aussehen?


(hier noch die Strukturen):

typedef int MatrixValue;   //hier kann schnell zwischen int und float umgeschaltet werden
typedef struct{
  unsigned int Zeilen;
  unsigned int Spalten;
  MatrixValue **m;
  } Mat;

typedef struct{
  int Spalten;
  MatrixValue *m;
} Vec;

[Karl H. (kbuchegg)]

Jens B. schrieb:

> In dem schritt, wo temp das nächste Produkt aufaddiert wird, dauert die
> Multiplikation nun ca. 22 Zyklen.
>
> Dieser Mehraufwand liegt sicher an den drei Indizierungen des Vektors
> und der Matrix.

Sehr wahrscheinlich.

> Kann man das beschleunigen, in dem man statt der Array-Schreibweise
> [m][n] mit Pointern und Doppelpointern rechnet?

Hast du den Optimizer ein?
Ein sehr guter Optimizer kann sowas selbstständig auf Pointer und 
Pointerinkrements umstellen.
Wenn nicht, musst du das händisch machen.

> Oder vl. mit
> Assembler-code?

Pointer werden wahrscheinlich reichen. Ds Problem ist, dass bei jeder 
Array Indizierung selbst wieder konzeptionell eine Multiplikation 
dazukommt.

  a[i] <==>  a + i * sizeof(*a);

> wie müsste sowas aussehen?

Das Prinzip ist einfach (xyz sei irgendein Datentyp)

   xyz * a;   // Quellaray

   for( i = 0; i < Obergrenze; ++i )
     machwas mit a[i];

kann umgeformt werden zu

   xyz * a;   // QUellarray
   xyz * b;   // Hilfspointer

   b = a;
   for( i = 0; i < Obergrenzen; ++i ) {
     machwas mit *b;
     b++
   }

man ersetzt also die Multiplikationen durch eine Serie von Additionen. 
Dies geht deshalb, weil i ja schön monton ansteigt.

Bei dir könnte man sogar noch einen Trick weitergehen und die äussere 
i-Schleife nach folgenden Muster ersetzen:

  xyz * a;
  xyz * b;
  xyz * b_end;

  b_end = a + Obergrenze;
  for( b = a; b < b_end; ++b )
    mach was mit *b;

man macht also den Bock zum Gärtner, eliminiert das i komplett und 
benutzt den Hilfspointer um die Schleife zu steuern.

Wie man dasselbe Konzept in einem 2D Array anwendet, kannst du dir jetzt 
selbst erarbeiten. Ist nicht weiter schwer. Nur soviel: Papier und 
Bleistift sind deine Freunde. Zeichne dir die Datenstruktur auf, geh 
händisch durch deine Schleifen durch und stell das Muster fest, in 
welcher Reihenfolge welche Elemente benötigt werden. Dieses Muster 
drückst du dann durch einen (oder mehrere) Startpointer aus und stellst 
fest um wieviel du diese jeweils erhöhen musst damit die ZUgriffssequenz 
dieselbe bleibt.

[Marcus H. (mharnisch)]

Jens B. schrieb:
> In dem schritt, wo temp das n�chste Produkt aufaddiert wird, dauert die
> Multiplikation nun ca. 22 Zyklen.
>
> Dieser Mehraufwand liegt sicher an den drei Indizierungen des Vektors
> und der Matrix.

Nein. Dieser Mehraufwand liegt vermutlich daran, dass Du GCC
verwendest, der erst bei -O3 was (halbwegs) anst�ndiges daraus macht.

Ein guter C Compiler f�r ARM setzt den Code sehr effizient um. Man
muss schon in arger Bedr�ngnis sein, um hier noch was rausholen zu
wollen:

vecMult PROC
        PUSH     {r4-r6,lr}
        CMP      r1,r3
        LDR      r12,[sp,#0x10]
        LDREQ    r3,[r0,#0]
        LDR      r4,[sp,#0x14]
        CMPEQ    r12,r3
        MOVEQ    r12,#0
        BEQ      |L1.84|
        BL       abort
|L1.36|
        MOV      lr,#0               ;             \
        MOV      r3,lr               ;             |
|L1.44|                              ;             |
        CMP      r1,r3               ; \           |
        LDRGT    r6,[r4,r3,LSL #2]   ; |           |
        LDRGT    r5,[r2,r3,LSL #2]   ; |     |
        LDRGT    r6,[r6,r12,LSL #2]  ; |inner loop |
        ADDGT    r3,r3,#1            ; |           |
        MLAGT    lr,r5,r6,lr         ; |           |outer loop
        BGT      |L1.44|             ; /           |
        LDR      r3,[r0,#4]          ;             |
        STR      lr,[r3,r12,LSL #2]  ;             |
        ADD      r12,r12,#1          ;             |
|L1.84|                              ;             |
        LDR      r3,[r0,#0]          ;             |
        CMP      r3,r12              ;             | 
        BGT      |L1.36|             ;             /
        POP      {r4-r6,pc}
        ENDP

> Kann man das beschleunigen, in dem man statt der Array-Schreibweise
> [m][n] mit Pointern und Doppelpointern rechnet? Oder vl. mit
> Assembler-code?

Einen Versuch ist's wert. Aber vor allem gilt: Beim GCC unbedingt -O3
aktivieren.

Gru�
Marcus
http://www.doulos.com/arm/

[Jens B. (meddle)]

Compiler ist der IAR. Es wurde jedoch wg. Debug-support keine 
Quellcodeoptimierung eingestellt. Die Pointer-increment Methode von 
Karl-Heinz hat die Anzahl deutlich reduzieren können. Der Übersicht 
halber lassen wir das mit dem Assembler-Code wohl besser sein.

Nachteilig bei der Pointer-increment-Methode ist, dass man die Matrix 
transponiert ablegen sollte, also im ersten Index die Spalten und im 
zweiten die Zeilen. Nur so hat man bei der Matrix in der inneren 
Schleife auch pointerincrements. Wenn man wie wir parallel mit Matlab 
arbeitet, dann ist das natürlich leicht irritierend, wenn die Indizes 
getauscht sind.

Vielen Dank für die Tipps.