Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Sin, Cos, Arccos -> Problem mit meheren Threads
platzwart - Mo 09.02.09 15:02
Titel: Sin, Cos, Arccos -> Problem mit meheren Threads
Hallo,
ich habe eine Software zur Bildanalyse geschrieben. Da sehr viele Bilder analysiert werden müssen, habe ich den Analysealgorithmus eines Bildes in einen Thread gepackt. Nun kann ich z.B. auf einem Quadcore 4 dieser Threads starten und somit 4 Bilder gleichzeitig analysieren. Der Performancegewinn ist enorm, es skaliert linear.
Jedoch ein kleines Problem besteht: Ich habe die Unit Math eingebunden, da an einer Stelle Sin, Cos und ArcCos berechnet werden müssen. An dieser Stelle kommen die Threads sich in die Quere und das Programm stürzt ab (Zugriffsverletzung...).
Aus diesem Grund habe ich um diesen Block herum eine CriticalSection gebaut, sodass immer nur ein Thread auf Sin, Cos und Arccos zugreift. Dann funktioniert auch alles wunderbar.
Warum gibt es mit diesen Funktionen Probleme? Warum muss man diesen Programmteil sequentiell ausführen? Kann ich das nicht doch parallelisieren?
Vielen Dank für Vorschläge!!
Xentar - Mo 09.02.09 15:08
Äh, bist du wirklcih sicher, dass der Fehler an den Math Funktionen liegt..? Kann ich mir eigentlich nicht vorstellen, da diese ja nur ein paar Berechnungen ausführen.
Kann es nicht eher sein, dass der Fehler darin liegt, dass du von den Threads aus auf das Bild zugreifst?
platzwart - Mo 09.02.09 15:24
So unglaublich wie es sich auch anhört, aber es ist genau so. Ich habe sehr lange gebraucht, um die Fehlerquelle zu entdecken, da ich mir auch nicht vorstellen konnte, dass der Fehler hier liegt. Ich habe beispielsweise nur eine einzige Zeile nicht in die CriticalSection aufgenommen (sowas in der Art arccos:= (tmp_bitmap32.width+10)/2;) und schon gibt es in dieser Zeile eine Zugriffsverletzung.
Ja, ich greife auf das Bild zu, aber dieses ist eine lokale Kopie (jeder Thread hat lokale Variable vom Typ Bitmap32). Außerdem greift ja jeder Thread auf ein anderes Bild zu... (und nicht nur einmal, der Teil, wo Sin, Cos, Arccos berechnet wird, macht weniger als 1% des Thread-Quelltextes aus, überall sonst funktioniert es ja auch...)
Jakob_Ullmann - Mo 09.02.09 15:38
Also Sin und Cos sind doch in der System und nicht in der Math definiert. :? Nur bei ArcCos könnte man mal darüber nachdenken, ob man den nicht selber implementiert, als Taylorreihe oder Assembler (@BenBE :wink: )
BenBE - Mo 09.02.09 15:58
Jakob_Ullmann hat folgendes geschrieben : |
Also Sin und Cos sind doch in der System und nicht in der Math definiert. :? Nur bei ArcCos könnte man mal darüber nachdenken, ob man den nicht selber implementiert, als Taylorreihe oder Assembler |
hmmm, ich schau mal in die betroffene Unit rein und guck mal, was die dort machen ...
Math.pas
689: 690: 691: 692: 693: 694: 695: 696: 697: 698: 699: 700: 701: 702: 703: 704: 705: 706: 707: 708: 709: 710: 711: 712: 713: 714: 715: 716: 717: 718: 719: 720: 721: 722: 723:
| { ... } function ArcCos(const X: Extended): Extended; begin Result := ArcTan2(Sqrt(1 - X * X), X); end;
function ArcSin(const X: Extended): Extended; begin Result := ArcTan2(X, Sqrt(1 - X * X)) end;
function ArcTan2(const Y, X: Extended): Extended; asm FLD Y FLD X FPATAN FWAIT end;
function Tan(const X: Extended): Extended;
asm FLD X FPTAN FSTP ST(0) FWAIT end;
function CoTan(const X: Extended): Extended;
asm FLD X FPTAN FDIVRP FWAIT end; |
Sqrt ist Compiler Magic, nutzt aber eigentlich auch nur die FPU.
Und genau HIER vermute ich das Problem: Ich weiß nicht, ob die FPU per Core oder per CPU vorhanden ist.
Könntest Du bitte einmal die relevante Code-Stellen aus deinem Thread-Source posten, speziell die Zeilen innerhalb der betroffenen Critical Section?
Wie soll ich diese Aufforderung jetzt verstehen ... Hat Borland doch schon gemacht ;-)
platzwart - Mo 09.02.09 16:08
Die Stelle mit dem Arccos:
Delphi-Quelltext
1:
| angle:= arccos((shadow.ll.Position.Y-shadow.ul.Position.Y)/sqrt((shadow.ul.Position.X-shadow.ll.Position.X)*(shadow.ul.Position.X-shadow.ll.Position.X)+(shadow.ul.Position.Y-shadow.ll.Position.Y)*(shadow.ul.Position.Y-shadow.ll.Position.Y)); |
jaenicke - Mo 09.02.09 16:20
platzwart hat folgendes geschrieben : |
Ich habe beispielsweise nur eine einzige Zeile nicht in die CriticalSection aufgenommen (sowas in der Art arccos:= (tmp_bitmap32.width+10)/2;) und schon gibt es in dieser Zeile eine Zugriffsverletzung.
Ja, ich greife auf das Bild zu, aber dieses ist eine lokale Kopie (jeder Thread hat lokale Variable vom Typ Bitmap32). Außerdem greift ja jeder Thread auf ein anderes Bild zu... (und nicht nur einmal, der Teil, wo Sin, Cos, Arccos berechnet wird, macht weniger als 1% des Thread-Quelltextes aus, überall sonst funktioniert es ja auch...) |
Hast du einmal auch diese Zugriffe aus der CriticalSection herausgelassen, auch wenn sie eigentlich in der selben Zeile standen? So dass in der CriticalSection ausschließlich der Sin/Cos/... Aufruf steht?
Geht es dann immer noch?
Bei deinem letzten Beispiel z.B. berechne den Wert doch mal vor der CriticalSection, den du da an arccos übergibst.
Allesquarks - Mo 09.02.09 17:09
Ich weiß es zwar nicht, denke aber schon, dass auch die FPU mehrmals vorhanden ist. Sonst würde der ganze multicore Zirkus im HPc oder zumindest wissenschaftlichen Rechnen sinnlos sein.
Kannst mal aus meinem Projekt RaFX aus der rmath unit die Funktionen runterladen. Sind alle in Assembler (was für ein Wunder bei vierzeilern sind sie ähnlich bis identisch nur das fwait habe ich häufig weggelassen glaube ich) und vlt kannst du damit die Compiler Magic, wenn es denn an der liegt umgehen.
Jakob_Ullmann - Mo 09.02.09 18:33
BenBE hat folgendes geschrieben : |
Wie soll ich diese Aufforderung jetzt verstehen ... Hat Borland doch schon gemacht ;-) |
Du kennst dich halt sehr gut mit Assembler aus und verstehst das unter Umständen auch, was Borland dort zusammengeschrieben hat. :)
jaenicke - Mo 09.02.09 19:11
Jakob_Ullmann hat folgendes geschrieben : |
was Borland dort zusammengeschrieben hat. :) |
Das ist an der Stelle ja nicht viel, da das in der FPU bereits implementiert ist. ;-)
Es reicht also in Assembler diese Befehle aufzurufen, was der Quelltext oben ja auch macht. FLD ist push für den FPU Stack, FPATAN und FPTAN ist sicher nicht schwer zu erraten ;-) und FSTP ist pop für den FPU Stack. FDIVRP ist eine Division kombiniert mit Pop. Und FWAIT wartet solange die FPU beschäftigt ist.
Jakob_Ullmann - Mo 09.02.09 21:31
Also wenn ich demnächst eine ruhige Minute habe, werde ich mich intensiv mit Assembler beschäftigen.
Hier mal meine (Delphi-)Implementation als Taylor-Reihe:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27:
| function fac(n: Byte): Integer; var i, j: Integer; begin j := 1; for i := 1 to n do j := j * i; Result := j; end;
function _ArcCos(r: Extended): Extended; var i: Byte; s: Extended; begin s := 0; for i := 0 to 15 do begin s := s + fac(2 * i) / (Math.Power(2, 2 * i) * Math.Power(fac(i), 2)) * Math.Power(r, (2 * i + 1)) / (2 * i + 1); end; Result := DegToRad(pi / 2 - s); end; |
delfiphan - Mo 09.02.09 22:00
Du greifst im Thread auf TBitmap() zu? Zeig mal den ganzen Code.
Die FPU wird wohl kaum das Problem sein, sonst würde der PC ja ständig abstürzen, wenn man mehrere Programme am laufen hat ;)
Rechner braucht man zum Rechnen, u.A. zum wissenschaftlichen Rechnen. Wenn das nicht parallelisierbar wäre, wäre das Unsinn.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!