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: 1 | void vecMult(Vec *Ergebnis, Vec A, Mat B){
| 2 | int i,j;
| 3 | MatrixValue temp;
| 4 | assert(A.Spalten == B.Zeilen);
| 5 | assert(B.Spalten == Ergebnis->Spalten);
| 6 |
| 7 | for(i=0;i<Ergebnis->Spalten;i++){
| 8 | temp=0;
| 9 | for(j=0;j<A.Spalten;j++){
| 10 | temp += A.m[j]*B.m[j][i];
| 11 | }
| 12 | Ergebnis->m[i]=temp;
| 13 | }
| 14 |
| 15 | }
|
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): 1 | typedef int MatrixValue; //hier kann schnell zwischen int und float umgeschaltet werden
| 2 | typedef struct{
| 3 | unsigned int Zeilen;
| 4 | unsigned int Spalten;
| 5 | MatrixValue **m;
| 6 | } Mat;
| 7 |
| 8 | typedef struct{
| 9 | int Spalten;
| 10 | MatrixValue *m;
| 11 | } Vec;
|
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.
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:
1 | vecMult PROC
| 2 | PUSH {r4-r6,lr}
| 3 | CMP r1,r3
| 4 | LDR r12,[sp,#0x10]
| 5 | LDREQ r3,[r0,#0]
| 6 | LDR r4,[sp,#0x14]
| 7 | CMPEQ r12,r3
| 8 | MOVEQ r12,#0
| 9 | BEQ |L1.84|
| 10 | BL abort
| 11 | |L1.36|
| 12 | MOV lr,#0 ; \
| 13 | MOV r3,lr ; |
| 14 | |L1.44| ; |
| 15 | CMP r1,r3 ; \ |
| 16 | LDRGT r6,[r4,r3,LSL #2] ; | |
| 17 | LDRGT r5,[r2,r3,LSL #2] ; | |
| 18 | LDRGT r6,[r6,r12,LSL #2] ; |inner loop |
| 19 | ADDGT r3,r3,#1 ; | |
| 20 | MLAGT lr,r5,r6,lr ; | |outer loop
| 21 | BGT |L1.44| ; / |
| 22 | LDR r3,[r0,#4] ; |
| 23 | STR lr,[r3,r12,LSL #2] ; |
| 24 | ADD r12,r12,#1 ; |
| 25 | |L1.84| ; |
| 26 | LDR r3,[r0,#0] ; |
| 27 | CMP r3,r12 ; |
| 28 | BGT |L1.36| ; /
| 29 | POP {r4-r6,pc}
| 30 | 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/
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.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
|