Automatisierte Performance Messungen



  • Ich habe einen numerischen Algorithmus, von dem ich die Performance messen will. Dafür will ich u.a. die Flops zählen, die der Algorithmus benötigt. Der Algorithmus ist ziemlich komplex, die Operationen von Hand zu zählen wäre zu umständlich. Außerdem möchte ich viele verschiedene Implementierungen automatisiert messen. Also suche ich ein Tool, was mein Programm ausführt und dabei die Flops mitzählt. Später brauche ich noch andere Daten (z.B. Cachemisses), aber da weiß ich schon in etwa wie ich da ran komme.

    Das ganze soll unter Linux auf Intel CPUs (Core 2 und neuer) funktionieren.

    Gefunden habe ich bis jetzt:

    • "perf". Einfach zu bedienen, aber ich weiß nicht wirklich wie ich nur an Flops komme (bekomme nur die Anzahl Instruktionen gesamt)
    • "oprofile"
    • "perfmon2/libpfm"
    • "Intel VTune"

    Mit den meisten Tools kann ich irgendwie Hardware Performance Counter auslesen. Aber welche(n) Counter soll ich nehmen um aussagekräftige Daten zu erhalten? Oder kennt jemand andere Tools, um aussagekräftige Flopcounts zu erhalten? Performancemessungen in Flop/s sehe ich ständig, sowas muss doch automatisiert gehen?

    Danke schonmal,
    nevermore


  • Mod

    Flops ist doch praktisch Instruktionen pro Zeit - die paar Operationen die nicht FLießkommarechnungen sind, sind doch genau so wichtig für die Gesamtzeit. Aber was interessieren dich bei einem Algorithmus die Flops? Das ist eine Kenngröße für Rechnerperformace. Das ist so als würdest du fragen, wieviel PS die Strecke Hamburg-Müchen braucht. Für einen Algorithmus willst du die Zeit pro Eingangsdaten wissen. Kann es sein, dass du einfach nur ein paar Schlagwörter aufgeschnappt, aber nicht verstanden hast? Ich kann dir eine Warteschleife programmieren, die ganz wunderbar viele Flops hat.

    Also was du wissen möchtest ist die Zeit pro Aufruf - und eventuell noch feiner aufgelöst, um herauszufinden, an welchen Stellen es warum hakt. Hierfür willst du einen Profiler benutzen - das sind Tools, die automatisiert solche Messungen durchführen.

    Was ich noch empfehlen kann:
    gprof: Quasi der Standardprofiler für Linux. Nicht so mächtig wie die professionellen Tools von Intel, aber dafür wesentlich einfacher zu lernen, benutzen und verstehen.
    cachegrind: Teil von valgrind. Auch ein Profiler, aber detaillierter als gprof - fast schon auf VTune-Niveau ohne auf Intel spezialisiert zu sein (und ist zudem freie Software!). Gibt genauere Analysen, nicht nur wo es hakt, sondern auch warum (wenn man die Ergebnisse versteht).



  • SeppJ schrieb:

    Flops ist doch praktisch Instruktionen pro Zeit - die paar Operationen die nicht FLießkommarechnungen sind, sind doch genau so wichtig für die Gesamtzeit. Aber was interessieren dich bei einem Algorithmus die Flops? Das ist eine Kenngröße für Rechnerperformace. Für einen Algorithmus willst du die Zeit pro Eingangsdaten wissen. Kann es sein, dass du einfach nur ein paar Schlagwörter aufgeschnappt, aber nicht verstanden hast? Ich kann dir eine Warteschleife programmieren, die ganz wunderbar viele Flops hat.

    Nee, ich weiß schon was ich machen will und habs auch verstanden. Klar sind Flop/s eine Kenngröße für Rechnerperformance. Aber natürlich auch für die Performance einer konkreten Implementierung eines Algorithmus. Ich möchte die Performance der Implementierung in Flop/s messen, damit ich diesen Wert dann mit der Peak Performance des Rechners vergleichen kann und sehe, ob die Implementierung eben mit 100% Performance läuft oder nur 10%... Das die Implementierung nicht zwangsläufig auch die schnellste sein muss (dein Argument mit der Warteschleife) ist mir schon klar. Man vergleicht ja auch prinzipiell nur Algorithmen mit gleichem Opcount.

    Und damit sollte auch klar sein, warum man nicht einfach den gesamten Opcount nimmt: Wenn alle Instruktionen zähle, kann ich den Wert nicht mehr mit der Peak Performance der Architektur (in Flop/s) vergleichen. Außerdem brauche ich den Flopcount um meine Implementierung im Roofline Modell einzuordnen.

    Es geht mir nicht darum, die Hotspots meines Algorithmus zu finden oder diesen zu optimieren (dafür würde ich einen Profiler benutzen). Ich möchte lediglich zeigen, welchen Effekt meine Optimierungen hatten.


  • Mod

    Dann bau doch einfach noch ein paar sinnlose Rechnungen auf dem Coprozessor, der SSE-Einheit, der MMX-Einheit oder auf der GPU ein. Je nachdem, was du davon nicht benutzt. Die brauchen dann keine/kaum Zusatzzeit nebenher, treiben aber deine Flops in ungeahnte Höhen.



  • Man vergleicht ja auch prinzipiell nur Algorithmen mit gleichem Opcount.

    Opcount abgeleitet von Opcode? Wenn ja, dann duerfte man gar keine Algorithmen vergleichen.

    Aber welche(n) Counter soll ich nehmen um aussagekräftige Daten zu erhalten

    Schau dir den ASM-Code an und zaehle Instructionen und gewichte sie mit ihrer Latenz.

    Ich möchte lediglich zeigen, welchen Effekt meine Optimierungen hatten.

    Ja aeh, wie waere es mit der Gesamtlaufzeit?



  • SeppJ schrieb:

    Dann bau doch einfach noch ein paar sinnlose Rechnungen auf dem Coprozessor, der SSE-Einheit, der MMX-Einheit oder auf der GPU ein. Je nachdem, was du davon nicht benutzt. Die brauchen dann keine/kaum Zusatzzeit nebenher, treiben aber deine Flops in ungeahnte Höhen.

    Das könnte ich zwar tun, ich fürchte aber dass ich damit nicht durchkomme 🙂 Abgesehen davon müsste ich die Flops immer noch zählen 😉

    Man vergleicht ja auch prinzipiell nur Algorithmen mit gleichem Opcount.

    Opcount abgeleitet von Opcode? Wenn ja, dann duerfte man gar keine Algorithmen vergleichen.

    Ich meinte: Performancedaten (in Flop/s) zweier Implementierungen werden idR nur verglichen, wenn beide Implementierungen gleiche Anzahl Operationen aufweisen. Sonst ist die Metrik nicht aussagekräftig. Beispiel: hochperformante, optimierte Insertion-Sort Implementierung vs. schlampig geschriebenes Quicksort macht keinen Sinn.



  • knivil schrieb:

    Aber welche(n) Counter soll ich nehmen um aussagekräftige Daten zu erhalten

    Schau dir den ASM-Code an und zaehle Instructionen und gewichte sie mit ihrer Latenz.

    Manuell zählen würde ich ja gerne vergleichen. Warum nach Latenz gewichten?

    knivil schrieb:

    Ich möchte lediglich zeigen, welchen Effekt meine Optimierungen hatten.

    Ja aeh, wie waere es mit der Gesamtlaufzeit?

    Klar, auch. Aber ich hab oben schon geschrieben, dass ich gerne auch zeigen möchte, wie nah ich an der Peak Performance der Architektur bin. Das ist eigentlich bei allen Veröffentlichungen zu High Performance Code die ich kenne so üblich.



  • Dann schau doch wie die Testprogramme anderer Bibliotheken das machen, beispielsweise FFTW. Und wenn man dort etwas stoebert, dann findet man http://www.bitmover.com/lmbench/ . Bei FFTW warden alle Instruktionen hergenommen. Waere ja auch sinnlos andere zu nehmen. Denn was verhindert denn, maximale Flops zu erreichen? Na die Operationen, die keine Flops sind.


  • Mod

    nevermore schrieb:

    Klar, auch. Aber ich hab oben schon geschrieben, dass ich gerne auch zeigen möchte, wie nah ich an der Peak Performance der Architektur bin.

    Gib die Instruktionen pro Takt an. Instruktionen zählen, Zeit messen, dann hohe Mathematik (Division), fertig.



  • knivil schrieb:

    Dann schau doch wie die Testprogramme anderer Bibliotheken das machen, beispielsweise FFTW.

    Gute Idee 👍 Ich werde mal schauen, was ich so finde.

    knivil schrieb:

    Und wenn man dort etwas stoebert, dann findet man http://www.bitmover.com/lmbench/ .

    Das ist ein Benchmark für Unix Systeme. Floating Point Performance wird da gar nicht gemessen? Übersehe ich was?

    knivil schrieb:

    Bei FFTW warden alle Instruktionen hergenommen. Waere ja auch sinnlos andere zu nehmen. Denn was verhindert denn, maximale Flops zu erreichen? Na die Operationen, die keine Flops sind.

    Das stimmt so nicht, heutige CPUs haben ILP. Nicht-Flops spielen daher bei floating-point-lastigem Code kaum eine Rolle, man betrachtet sie daher gar nicht. Wenn ich alle Instruktionen mitrechne, kann ich meine gemessene Performance auch nicht mehr mit der Peak Floating Point Performance des Systems vergleichen. Woher hast du die Information zu FFTW?



  • SeppJ schrieb:

    nevermore schrieb:

    Klar, auch. Aber ich hab oben schon geschrieben, dass ich gerne auch zeigen möchte, wie nah ich an der Peak Performance der Architektur bin.

    Gib die Instruktionen pro Takt an. Instruktionen zählen, Zeit messen, dann hohe Mathematik (Division), fertig.

    Instruktionen pro Takt ist doch das selbe wie Flop/s, nur dass die Taktfrequenz rausgerechnet ist? Das ist ja das was ich haben will, nur in einer anderen Einheit. Problem ist das Instruktionen zählen. Das würde ich gerne automatisieren. Zur Not muss ich den Code mit Countern instrumentieren, ich hatte nur gehofft dass es eine einfachere Lösung gibt.



  • knivil schrieb:

    Denn was verhindert denn, maximale Flops zu erreichen?

    -latenz von instruktionen bsp:

    idiv eax,ebx
    add eax,5 ;stall bis idiv fertig ist
    

    -durchsatz von instruktionen bsp:

    imul eax,ebx
    imul ecx,ebx ;//stall 1cycle auf atom cpus
    

    -latenz von cache misses (bsp linked list von 4GB)
    -bandbreite (linear durch 4GB von floats durchgehen und davon "max" bestimmen -> 400ms -> '5gflops' aufs cpus die 100gflops+ schaffen)
    -auslastung einzelner cpu units bsp

    fdiv ;cycle 0
    fmul ;cycle 1
    

    vs

    fadd ;cycle 0
    fmul ;cycle 0
    

    Na die Operationen, die keine Flops sind.

    das ist eher nicht der fall, wenn man code hat der wirklich viel rechnet, da bei AMD diese instruktionen in ganz unabhaengigen pipelines abgearbeitet und bei Intel die pipeline genug durchsatz hat um float und anderweitige einheiten zu fuettern (im schnitt wohl ca 2.4einheiten/cycle).
    natuerlich ist das nicht der fall bei etwas wie quicksort, selbst wenn man floats vergleichen wuerde, aber dabei wuerde man wohl auch nicht die gflop leistung optimieren wollen.

    ich finde das vorgehen vom threadstarter gut, ich rechne (bzw schaetze) immer erst die potentiel moegliche leistung aus, bevor ich anfange zu optimieren, wie sonst kann man wissen wann man fertig ist? (wenn einem die ideen ausgehen? 🤡 )

    statt instruktionen zu zaehlen, kann man manchmal auch die groesse des problems analysieren und so errechnen wieviele 'flops' noetig sind um das problem zu loesen, das klappt auch mit komplexeren algorithmen.
    ich habe zudem einen wrapper um alle SIMD instruktionen, der im profiling mode einen counter hochzaehlt (pro instruktionen um zu wissen was genau stallt).
    leider hab ich die gunst tools zu nutzen die nicht so leicht zugaenglich sind, deswegen kann ich nichts wirklich empfehlen (ich glaube pix fuer windows hat keine tolle cpu analyse, wenn ich mich recht entsinne), frueher hab ich immer vtyne genutzt, das ist ja auch kostenlos fuer linux zu haben, wuerde ich auf jedenfall mal ausprobieren 😉



  • Hmmm, danke für den Input. Das mit den Wrappern um die SIMD Intrinsics ist ganz pfiffig. Leider würde ich das ganze gerne schon auf einen Code anwenden, an dem noch nichts optimiert wurde und daher auch noch keine Instrinsics verwendet werden.

    Scheint wohl wirklich keine einfache Lösung zu geben. Ich schaue mir nochmal VTune an und welche Performance Counter mir das so anbietet.



  • nevermore schrieb:

    Hmmm, danke für den Input. Das mit den Wrappern um die SIMD Intrinsics ist ganz pfiffig. Leider würde ich das ganze gerne schon auf einen Code anwenden, an dem noch nichts optimiert wurde und daher auch noch keine Instrinsics verwendet werden.

    das ist nicht anders, du kannst dir ein typedef machen

    typedef float REAL;
    

    basteln, und alles an floats darauf umstellent (sollte fast komplett mit replace-all gehen).
    und zum benchmarken erstellst du dir eine float klasse mit den basis operationen und casts und dann

    typedef MyFloat REAL;
    

    und schon hast du deine antworten 😉



  • Perfekt, so mach ich es! Ist zwar eine Lösung auf Sourcecodeebene, aber die Änderungen sind minimal. Und wenn ich den Code ändere, muss ich die Zählung nicht anpassen. Ich hatte mir nämlich schonmal für ein anderes Projekt ein paar Makros zum Zählen gebaut, so in der Art von INCREASE_FLOP_COUNTER(...), aber das ist natürlich sehr fehleranfällig.

    Das Beste: Den typedef gibt es eh schon, um von float auf double umzuschalten. Einfacher geht's nicht 🙂

    Danke 👍



  • @rapso: Ich weiss, was alles die Performance drueckt. Ich sehe kein Beispiel das speziell fuer floating point operations gedacht ist.



  • knivil, es kommt natürlich auf den Algorithmus an. Aber oft ist es eben so, dass hauptsächlich Floating Point Operationen benötigt werden. Das bisschen Integerarithmetik etc. macht die CPU dann nebenbei (ILP, Superskalarität) und kann ignoriert werden.

    Bei FFTs ist das auch der Fall. Du hattest ja FFTW angesprochen: die rechnen einfach mit 5*n*log n Floating Point Operationen in ihren Benchmarks. Aus dem FFTW Paper (http://www.fftw.org/fftw-paper-ieee.pdf):

    We show the benchmark results as a series of graphs. Speed is measured in “MFLOPS,” defined for a transform of size n as (5n log2 n)/t, where t is the time in µs for one transform, not including one-time initialization costs. This count of floating-point operations is based on the asymptotic number of operations for the radix-2 Cooley-Tukey algorithm (see [17, page 45]), although the actual count is lower for most DFT implementations

    rapsos Beispiele zeigen nur, dass auch andere Dinge als non-flops die Floating Point Performance drücken.



  • knivil schrieb:

    @rapso: Ich weiss, was alles die Performance drueckt.

    deine aussage, von der sache die am wenigsten einfluss hat bei algorithmen bei denen man gflops misst, hat den gegenteiligen anschein bei mir hinterlassen, oder hab ich sarkasmus uebersehen? 😕

    Ich sehe kein Beispiel das speziell fuer floating point operations gedacht ist.

    meine beispiele? die waren zumeist auf float bezogen bzw kann man die darauf anwenden.



  • rapso schrieb:

    ich finde das vorgehen vom threadstarter gut, ich rechne (bzw schaetze) immer erst die potentiel moegliche leistung aus, bevor ich anfange zu optimieren, wie sonst kann man wissen wann man fertig ist? (wenn einem die ideen ausgehen? 🤡 )

    😕 Wie rechnest du die potentiel mögliche Leistung aus? Leistung in was?


Log in to reply