3. Benötige Hilfe bei Optimierung

Benötige Hilfe bei Optimierung

  • X

    Hi,
    Ich möchte folgenden Code soweit wie möglich optimieren.
    Ich konnte meine ursprüngliche (naive) Implementation schon sehr beschleunigen (von >80min auf ca fünf Minuten auf einem 1GHz Prozessor), Wenn ich beim gcc noch die Optimierung einschalte (-O3), dann verkürzt sich die Rechenzeit noch einmal um mehr als die Hälfte. Daher würde mich interessieren was der Compiler da so alles optimieren kann und was ich noch besser machen kann(Der Algorithmus soll später nach VHDL "umgeschrieben" werden, deshalb sollte bei der Optimierung möglichst die parallele Verarbeitbarkeit erhalten bleiben).

    Ich hoffe sehr auf eure Hilfe.

    LG

    P.S.: falls der Post im falschen Forum ist, bitte verschieben.

    0
  • ?

    Aufn ersten Blick machst du jedenfalls nichts ganz Fürchterliches, aber dein Problem ist nicht trivial. Was sagt denn dein Profiler, was genau noch lange dauert?
    Auch kannste ja mal sagen, was dein Algorithmus macht. Dann kann man ja mal auf Suche nach prinzipiell besseren Algorithmen für dein Problem gehen.

    Ansonsten habe ich zwei Tipps, die ab und zu etwas bewirken (schmeiß trotzdem deinen Profiler an :-))
    - Bei häufig durchlaufenden Schleifen keine Ifs, damit die CPU besser die Sprünge vorhersagen kann; evtl. danach Fehler in der Berechnung bereinigen.
    - Son If

    if(l_weight1/l_weight2 < l_minval)
                {
                    l_minval = l_weight1/l_weight2;   
                    dispL2R->imageData[y*props.width+x] = d*255/16;
                }

    lässt sich doch gut entfernen. Vielleicht berechnest du dann zwar zu viel, aber dafür macht die CPU gute und richtige Vorhersagen; und eine vollgestopfte Pipeline ist doch gut 🙂
    - l_values[(x*windowsize*windowsize+i)] Das könnte vielleicht evtl langsam werden, weil der Zugriff mehr oder weniger zufällig ist; die CPU lädt ne ganze Cache-Line, wobei nur ein einzelner Wert wichtig ist. Vielleicht speicherst du nicht l_values in der üblichen Reihenfolge sondern auf Index 0 kommt 0*windowsize*windowsize+0, auf Index 1 kommt 0*windowsize*windowsize+1, usw. Dann sparst du dir diese minimale Rechnung, aber viel wichtiger ist, dass der nächste Zugriff hierauf nur um eine Position versetzt ist (Lokalität)

    0
  • X

    Leider sagt mein Profiler (gprof) nur welche Funktion wie oft aufgerufen wird, und das bringt mir nicht viel.

    foobie schrieb:

    if(l_weight1/l_weight2 < l_minval)
                {
                    l_minval = l_weight1/l_weight2;   
                    dispL2R->imageData[y*props.width+x] = d*255/16;
                }

    lässt sich doch gut entfernen.

    Wie?

    l_values[(x*windowsize*windowsize+i)] wird doch genauso wie von dir beschrieben gefüllt.

    for(int x = 0; x < props.width; x++) 
{
           ...
           for(int i = 0; i< windowsize*windowsize; i++)
           {
                      l_values[(x*windowsize*windowsize+i)] = ...
           }
}

    Ach ja, die Aufgabe des Algorithmus ist es eine Disparity-Map aus 2 Stereo-Bildern zu generieren. (siehe dieses Paper, allerdings erhalte ich (noch) nicht die selben Ergebnisse wie gezeigt 😞 ) Eine Alternative fürchte ich kommt nicht in Frage, da dieser der zweitbeste (meines Wissens nach) lokale Algorithmus (=> leicht parallelisierbar) ist und der Rechenaufwand gering genug ist um in Echtzeit zu laufen.

    LG

    0
  • R

    wenn du das unter linux laufen laesst, kannst du mal kostenlos vtune laufen lassen, das hat ordentliches profiling.

    0
  • X

    @rapso: danke für den Hinweis, aber ich habe keine Lust bei Intel meine Telefonnummer zu hinterlassen. Dafür habe ich valgrind ausprobiert allerdings auch nicht mit mehr Erfolg als mit gprof.

    Hat keiner mehr eine Idee, oder einen Tipp für mich?

    LG

    0
  • Mod

    gprof sollte dir eigentlich auch eine genaue Analyse darüber geben, welcher Programmteil warum wie viel CPU-Zeit gebraucht hat. Wundert mich eigentlich, dass du das nicht gesehen hast, das sollte ein ziemlich großer Abschnitt im Ergebnis sein, weil das ganze sehr detailliert ist.

    0
  • X

    Bei meiner Ausgabe ist nicht sonderlich viel Information enthalten:

    gcc matching.c -o matching `pkg-config --cflags --libs opencv` -pg
./matching
gprof ./matching ./gmon.out > out.txt

    ergibt das:

    Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
100.00   2447.03  2447.03        4   611.76   611.76  localWindowMatching(char const*, char const*, _imgProp, char const*)
  0.00   2447.03     0.00        8     0.00     0.00  cvSize(int, int)

 %         the percentage of the total running time of the
time       program used by this function.

cumulative a running sum of the number of seconds accounted
 seconds   for by this function and those listed above it.

 self      the number of seconds accounted for by this
seconds    function alone.  This is the major sort for this
           listing.

calls      the number of times this function was invoked, if
           this function is profiled, else blank.

 self      the average number of milliseconds spent in this
ms/call    function per call, if this function is profiled,
	   else blank.

 total     the average number of milliseconds spent in this
ms/call    function and its descendents per call, if this 
	   function is profiled, else blank.

name       the name of the function.  This is the minor sort
           for this listing. The index shows the location of
	   the function in the gprof listing. If the index is
	   in parenthesis it shows where it would appear in
	   the gprof listing if it were to be printed.

		     Call graph (explanation follows)

granularity: each sample hit covers 4 byte(s) for 0.00% of 2447.03 seconds

index % time    self  children    called     name
                                                 <spontaneous>
[1]    100.0    0.00 2447.03                 main [1]
             2447.03    0.00       4/4           localWindowMatching(char const*, char const*, _imgProp, char const*) [2]
-----------------------------------------------
             2447.03    0.00       4/4           main [1]
[2]    100.0 2447.03    0.00       4         localWindowMatching(char const*, char const*, _imgProp, char const*) [2]
                0.00    0.00       8/8           cvSize(int, int) [6]
-----------------------------------------------
                0.00    0.00       8/8           localWindowMatching(char const*, char const*, _imgProp, char const*) [2]
[6]      0.0    0.00    0.00       8         cvSize(int, int) [6]
-----------------------------------------------

 This table describes the call tree of the program, and was sorted by
 the total amount of time spent in each function and its children.

 Each entry in this table consists of several lines.  The line with the
 index number at the left hand margin lists the current function.
 The lines above it list the functions that called this function,
 and the lines below it list the functions this one called.
 This line lists:
     index	A unique number given to each element of the table.
		Index numbers are sorted numerically.
		The index number is printed next to every function name so
		it is easier to look up where the function in the table.

     % time	This is the percentage of the `total' time that was spent
		in this function and its children.  Note that due to
		different viewpoints, functions excluded by options, etc,
		these numbers will NOT add up to 100%.

     self	This is the total amount of time spent in this function.

     children	This is the total amount of time propagated into this
		function by its children.

     called	This is the number of times the function was called.
		If the function called itself recursively, the number
		only includes non-recursive calls, and is followed by
		a `+' and the number of recursive calls.

     name	The name of the current function.  The index number is
		printed after it.  If the function is a member of a
		cycle, the cycle number is printed between the
		function's name and the index number.

 For the function's parents, the fields have the following meanings:

     self	This is the amount of time that was propagated directly
		from the function into this parent.

     children	This is the amount of time that was propagated from
		the function's children into this parent.

     called	This is the number of times this parent called the
		function `/' the total number of times the function
		was called.  Recursive calls to the function are not
		included in the number after the `/'.

     name	This is the name of the parent.  The parent's index
		number is printed after it.  If the parent is a
		member of a cycle, the cycle number is printed between
		the name and the index number.

 If the parents of the function cannot be determined, the word
 `<spontaneous>' is printed in the `name' field, and all the other
 fields are blank.

 For the function's children, the fields have the following meanings:

     self	This is the amount of time that was propagated directly
		from the child into the function.

     children	This is the amount of time that was propagated from the
		child's children to the function.

     called	This is the number of times the function called
		this child `/' the total number of times the child
		was called.  Recursive calls by the child are not
		listed in the number after the `/'.

     name	This is the name of the child.  The child's index
		number is printed after it.  If the child is a
		member of a cycle, the cycle number is printed
		between the name and the index number.

 If there are any cycles (circles) in the call graph, there is an
 entry for the cycle-as-a-whole.  This entry shows who called the
 cycle (as parents) and the members of the cycle (as children.)
 The `+' recursive calls entry shows the number of function calls that
 were internal to the cycle, and the calls entry for each member shows,
 for that member, how many times it was called from other members of
 the cycle.

Index by function name

   [2] localWindowMatching(char const*, char const*, _imgProp, char const*) [6] cvSize(int, int)
    0
  • M

    Du bekommst die Laufzeiten nach Funktionen gelistet. Wenn du also deine Megafunktion in kleinere Funktionen aufteilst, kannst du sehen, wo die meiste Zeit draufgeht. Nach der Verbesserung kannst du wieder alles zusammen in ein Monstrum stecken, wenn du das willst.

    0
  • K

    Hi,

    Wenn du valgrind --tool=callgrind ./matching ausführst und das Ganze mit Debugsymbolen kompiliert hast, dann zeigt dir kcachegrind auch wieviel Zeit jede Zeile des Quellcodes benötigt hat.

    KaPtainCugel

    0

  • Und wenn du es einfach mal auf einer GPU implementierst? f'`8k

    Gruß, TGGC (der kostenlose DMC Download)

    0
  • Mod

    Irgendwie bin ich etwas verwirrt von deiner ausgabe. Hast du nur die Hauptdatei mit der Profiling-Option compiliert? Denn selbst wenn du alles in einer Funktion hast, deine Funktion wird ja wohl irgendetwas tun. Normalerweise wird das Ergebnis aufgesplittet bis in die allerkleinste Einheit, so dass man sogar sehen kann wie viel Zeit man mit dem Zugriff auf Feldindizes* verbracht hat.

    edit: Oh, ich sehe gerade du hast dein Programm schon gepostet. Deine Hauptfunktion ruft ja tatsächlich keine Unterfunktionen auf. Oje. Dann kann ich mich nur dem Rat anschließen, das Programm etwas prozeduraler zu gestalten. Meistens ist das auch allgemein eine sehr gute Idee, weil man dabei schon viele mögliche Verbesserungen sieht.

    *: Natürlich nur in C++, wo der Zugriff auf Felder als Funktionsaufruf abstrahiert ist.

    0
  • X

    KPC schrieb:

    Wenn du valgrind --tool=callgrind ./matching ausführst und das Ganze mit Debugsymbolen kompiliert hast, dann zeigt dir kcachegrind auch wieviel Zeit jede Zeile des Quellcodes benötigt hat.

    Danke für den Tipp, das Ergebnis sieht (nach 2.3h 🙄 ) in etwa so aus:

    2.26%    sqrt (228.219.779 Aufrufe)
0.78%    isnan (228.219.779 Aufrufe)
0.09%    0x00003517 (228.219.782 Aufrufe)
0.01%    cvLoadImage (2 Aufrufe)
0.00%    0x00016a0f (260.022 Aufrufe)
....

    mal sehen, vielleicht kann ich statt sqrt eine Aproximation verwenden.

    TGGC schrieb:

    Und wenn du es einfach mal auf einer GPU implementierst?

    "Einfach mal" spielt es bei mir leider nicht (keine Erfahrung damit und meine Grafikkarte unterstützt noch kein CUDA), außerdem soll das Ganze ohnehin auf einem FPGA realisiert werden.

    Damit weiß ich aber immer noch nicht was der Compiler optimiert, sodass die Rechenzeit halbiert wird.

    LG

    EDIT:
    jetzt habe ich die Source-Code Ansicht gefunden und da werden die beiden Zeilen mit jeweils 17.81% bewertet:

    l_e = abs(left[l_pos]-right[l_pos1])+abs(left[l_pos+1]-right[l_pos1+1])+abs(left[l_pos+2]-right[l_pos1+2]);
r_e = abs(left[r_pos1]-right[r_pos])+abs(left[r_pos1+1]-right[r_pos+1])+abs(left[r_pos1+2]-right[r_pos+2]);

    Ich nehme an das es an der abs() Funktion liegt, aber das sollte doch besser gehen. ich werd mal statt der Summe der absoluten Differenzen (SAD) die kleinsten Quadrate probieren (SSD).

    EDIT 2:
    Ach ja, gibt es eine Funktion die sowohl Rest als auch das Ergebnis der Division liefert??

    0
  • M

    XBert schrieb:

    Ach ja, gibt es eine Funktion die sowohl Rest als auch das Ergebnis der Division liefert??

    Nach DIV steht der Rest AFAIK in AH.

    0
  • I

    ... viel hübscher und platformunabhängiger ist aber div.

    0

  • Wenn du nur wissen willst, was der Compiler optimiert, warum schaust du dir nicht einfach den Compileroutput an? f'`8k

    Gruß, TGGC (der kostenlose DMC Download)

    0
  • X

    TGGC schrieb:

    Wenn du nur wissen willst, was der Compiler optimiert, warum schaust du dir nicht einfach den Compileroutput an?

    Gerne, wenn du mir sagst wie ich das mache. Mit -E bekomme ich nur das Ergebnis nach dem Preprozessor, und mit Assemblercode kann ich leider nicht viel anfangen.

    Aber alleine durch die Verwendung von div() anstatt der Division und modulo-Operation einzeln wurde die Ausführzeit von ~618s auf ~427s reduziert. Um die abs() funktion komme ich aber vermutlich nicht herum, denn wenn ich die Abstandsquadrate verwende ist die Qualität des Endergebnisses deutlich schlechter.

    LG

    0

  • XBert schrieb:

    mit Assemblercode kann ich leider nicht viel anfangen.

    Tja, dann wirst du die Optimierungen wohl "leider nicht" verstehen.

    Verstehe auch nicht, warum du die Zeilen nicht mal auseinandernimmst, anstatt einfach nur das abs zu vermuten. f'`8k

    Gruß, TGGC (der kostenlose DMC Download)

    0
Anmelden zum Antworten