Matrixfunktionen - schnell durch Inline-Assembler

Arndt

In XProfan X4 fehlen eine Reihe von Matrix- und Vektorfunktionen, obwohl mit der MAT-Anweisung schon einige Funktionen verfügbar sind. Programmiert man eine Matrixmultiplikation mit Profan-Befehlen steigen die Rechenzeiten exorbitant an. Damit kann man nur kleine Matrizen bearbeiten.
Dank des Inline-Assemblers kann man diese Operationen aber in praktikabler Zeit ausführen. Die angefügten Prozeduren leisten:
1. Skalarprodukt zweier Vektoren
2. Vektornorm
3. Determinante einer quadratischen Matrix
4. Lösung eines linearen Gleichungssystems
5. transponieren einer Matrix
6. echte Multiplikation zweier Matrizen
7. echte Multiplikation zweier quadratischer Matrizen (braucht weniger Parameter als 6.)
8. Multiplikation einer quadratischen Matrix mit einem Vektor
9. Inverse einer quadratischen Matrix
10. Zeilenvektor einer quadratischen Matrix
10. Spaltenvektor einer quadratischen Matrix
Damit können auch relativ große Matrizen (Dimension im 3-stelligen Bereich) bearbeitet werden.
Mit meinem Rechner (Intel i7 12700K) werden zwei Matrizen der Dimension 1000 x 1000 in 1,6 s multipliziert. Die Lösung eines Gleichungssystems mit 1000 Gleichungen und 1000 Unbekannten dauerte 567 ms (alles Momentanwerte aus einem Durchlauf). Die Berechnung der inversen Matrix brauchte 38 s.
Für die Dimension 100 x 100 betragen die Werte: Matrizenmultiplikation: < 10 ms; lineares Gleichungssystem: 16 ms; Inverse Matrix: 377 ms (ebenfalls nur ein Durchlauf).
Ich habe ein kleines Demo-Programm beigefügt. In der zugehörigen Include-Datei sind u.a. Routinen zur Ausgabe von Matrizen und Vektoren enthalten.
Noch eine Anmerkung zum Inline-Assembler. Der Einsatz bietet sich immer dort an, wo Daten für Berechnungen in den Registern des Prozessors gehalten werden könne und wo Schleifen abzuarbeiten sind. Beides ist in den obigen Funktionen der Fall.

Gruß
Arndt

Der Inhalt kann nicht angezeigt werden, da Sie keine Berechtigung haben, diesen Inhalt zu sehen.

H.Brill

Sehr interessant.

Werde ich mir am Wochenende auf jeden Fall mal anschauen.

Was mich an MAT etwas stört, ist daß man den &index nicht mittendrin greifen kann,

z. B. mit einer IF() - Funktion. z.b.

Code

MAT c[] + If(&index Mod 2 = 0, Rnd(a - b) - b, 0)

Zufallszahl nur bei geraden Zahlen.

Ansonsten ist es ja mit dem AUSDRUCK auch so eine Sache :

Code

declare Long c[], a, b
SetSize c[], 10
Randomize
Cls
a = 100
b = 1
MAT c[] < 0
MAT c[] + Rnd(a - b) - b
Ausgabe()
Print
WhileLoop 0, 9
c[&LOOP] = Rnd(a - b) - b
EndWhile
Ausgabe()
Proc Ausgabe
WhileLoop 0, 9
Print c[&LOOP]
EndWhile
EndProc
waitkey

Alles anzeigen

Arndt

Ich habe da mal einen Beispielcode geschrieben. Leider bringt das an der Stelle überhaupt nichts. Für diese Aufgabe ist eine einfache For-Schleife in Profan wahrscheinlich die effektivste Lösung.

Code

proc test
parameters long i
declare long rw
 ifnot testbit(i,0)
   rw = Rnd(233 + 12) - 12
 else
   rw = 0
 endif
 return rw
endproc  
Var Pointer pproc = ProcAddr(test, 1)
asm "vfill",3  ' Adresse ext. Proc, Adresse Zielvektor, Anzahl Werte
 CLD
 MOV  EDI,par2
 MOV  ECX,par3
 MOV  EDX,0
sch:
 PUSH EDI        ' benutzte Register müssen zwischengespeichert werden
 PUSH ECX
 PUSH EDX
 PUSH EDX        ' Parameterübergabe
 call par1
 POP  EDX
 POP  ECX
 POP  EDI
 INC  EDX
 STOSD
 LOOP sch
endasm  
 
declare long x[100000], i, zm
cls
randomize
print "Start mit Assembler"
 zm = &gettickcount
 vfill(pproc,addr(x[0]),100001)
 zm = &gettickcount-zm
print "fertig in",zm,"ms"
 for i,0,10
   print x[i]
 endfor
 
print "Start ohne Assembler"
 zm = &gettickcount
 for i,0,100000
   ifnot testbit(i,0)
     x[i] = Rnd(233 + 12) - 12
   else
     x[i] = 0
   endif
 endfor  
 zm = &gettickcount-zm
print "fertig in",zm,"ms"
 
 for i,0,10
   print x[i]
 endfor
 
 waitinput
end

Alles anzeigen

Die Rechenzeit wird wahrscheinlich von der RND-Funktion dominiert.

Gruß

Arndt

H.Brill

So, wie ich das sehe, wird die Funktion bzw. Ausdruck schon beim Aufruf von

MAT ausgewertet bzw.berechnet. In der eigentlichen Schleife von MAT wird

nur das Ergebnis davon mit +, -, /, * < mit dem &index verrechnet. Das Rnd()

wird nur einmalig bei Aufruf ausgeführt. Ich hätte gerne sowas gehabt :

Code

Proc MatArrayLong
Parameters Long x[]
Randomize
WhileLoop 0, SizeOf(x[]) - 1
 x[&LOOP] = Rnd(a - b) - b
EndWhile
EndProc

Wenn ich als Parameter noch ausdruck mitgeben würde, würde dieser ja auch

beim Aufruf der Proc einmalig berechnet und übergeben. Und genau da ist der Haken,

den auch RGH wohl nicht beseitigen konnte. Vielleicht könnte man da auch eine Art

CALLBACK-Funktion einklinken.

Wie auch immer, der Geschwindigkeitsvorteil, um den es ja auch geht, wäre dann dahin.

Arndt

Dieses Beispiel realisiert eine Multiplikation mit dem Index. Für die anderen Operationen sind geringfügige Anpassungen der Assemblerroutine erforderlich. Was allerdings nicht geht ist die Verwendung von &Index in dem zu übergebenden Ausdruck. Dieser wird ja bereits vor dem Beginn der Schleife ausgewertet. Damit ist dies Routine mit MAT x[] < <Ausdruck> identisch. Man kann mit dieser Vorgehensweise lediglich die Multiplikation der Werte auf Addition, Subtraktion und Division ausweiten.

Code

Proc MatArrayLong
Parameters Long x[], aw
Randomize
'WhileLoop 0, SizeOf(x[]) - 1
' x[&LOOP] = Rnd(a - b) - b
'EndWhile
vfill(addr(x[0]),sizeof(x[]),aw)
EndProc

asm "vfill",3  ' Adresse Zielvektor, Anzahl Werte, Wert des Ausdrucks
CLD
MOV  EDI,par1
MOV  ECX,par2
MOV  EBX,par3
MOV  ESI,0     ' ESI wird hier als Datenregister benutzt
sch:
MOV  EAX,ESI
MUL  EBX
INC  ESI
STOSD
LOOP sch
endasm  

declare long x[10000], i, zm, zw
cls
print "Start mit Assembler"
zm = &gettickcount
randomize
MatArrayLong(x[],Rnd(233 + 12) - 12)
zm = &gettickcount-zm
print "fertig in",zm,"ms"
for i,0,10
  print x[i]
endfor

print "Start ohne Assembler"
zm = &gettickcount
randomize
zw = Rnd(233 + 12) - 12
for i,0,10000
    x[i] = i*zw
endfor  
zm = &gettickcount-zm
print "fertig in",zm,"ms"

for i,0,10
  print x[i]
endfor

waitinput
end

Alles anzeigen

Für den Datentyp double kann man die Routine ebenfalls anpassen. Für Strings macht es keinen Sinn.

Gruß

Arndt

Jetzt mitmachen!