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

user profile iconJakob_Ullmann hat folgendes geschrieben Zum zitierten Posting springen:
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;
{  Tan := Sin(X) / Cos(X) }
asm
        FLD    X
        FPTAN
        FSTP   ST(0)      { FPTAN pushes 1.0 after result }
        FWAIT
end;

function CoTan(const X: Extended): Extended;
{ CoTan := Cos(X) / Sin(X) = 1 / Tan(X) }
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?

user profile iconJakob_Ullmann hat folgendes geschrieben Zum zitierten Posting springen:
(@BenBE :wink: )

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

user profile iconplatzwart hat folgendes geschrieben Zum zitierten Posting springen:
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

user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconJakob_Ullmann hat folgendes geschrieben Zum zitierten Posting springen:
(@BenBE :wink: )

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. :)


BenBE - Mo 09.02.09 19:05

user profile iconJakob_Ullmann hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconBenBE hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconJakob_Ullmann hat folgendes geschrieben Zum zitierten Posting springen:
(@BenBE :wink: )

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. :)

Jap, die ham Standard-Code produziert ;-) Wie ihn jeder Codemonkey auch für Bananen schreiben würde ...


jaenicke - Mo 09.02.09 19:11

user profile iconJakob_Ullmann hat folgendes geschrieben Zum zitierten Posting springen:
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;

{ Arkuscosinus }
function _ArcCos(r: Extended): Extended;
var
  i: Byte;
  s: Extended;
begin
  s := 0;
  for i := 0 to 15 do
  { 15 ggf. durch eine andere Zahl zu ersetzen;
    je nachdem, wie gut / schlecht die Näherung
    sein muss / darf bzw. die Zeit. }

  begin
    s := s + fac(2 * i) / (Math.Power(22 * 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.