SMP in eigenem C-Programm nutzen

Herakles

Herakles

Profifragensteller
Moin!

Ich habe ein kleines Programm, das in einer dreifach verschachtelten Schleife ordentlich CPU-Leistung zieht. Die Berechnung, wie ich sie vor habe, hat bei mir in einem ersten Versuch 5 Sekunden gedauert, wenn ich diese dann mit der tatsächlich gedachten Schleifentiefe betreiben würde, komme ich auf mehr als 100 Stunden.

Das Ganze habe ich in einem eigenen C-Programm geschrieben. Nun dachte ich mir, dass ich den Zeitaufwand auch runterschrauben kann, indem ich alle Kerne meines Rechners arbeiten lasse. Leider habe ich sowas aber nie gemacht.

Bekomme ich das hin, indem ich mein Programm einfach mit fork() spalte, muss ich Multithreading programmieren oder gibt es andere (einfachere) Lösung?

Danke im Voraus,
Herakles
 
Kommt auch auf die Daten-Abhängigkeit in deiner Routine an. Wenn jeder Durchlauf der untersten Schleifenebene unabhängig von denen darüber ist, dann ist es relativ simpel das auf mehrere Kerne zu verteilen. Alles andere kann eklig werden.

Ansonsten einfach mal testen, vor die Schleife:
#pragma omp parallel for

Also:

#pragma omp parallel for
for(...) {
}

und dann mit gcc -fopenmp kompilieren
 
Wie schwer das ganze wird hängt im einfachsten Fall hauptsächlich von den Zugriffsmustern ab. Es lohnt sich einen blick auf OpenMP zu werfen. OpenMP ist eine Compilerextension mit der man überwiegend deklarativ seinem Compiler mitteilt wie Objekte zugegriffen werden und welche Schleifen man gerne wie parallelisiert hätte. OpenMP wurde für SMP Workstations entwickelt. Leider fehlt in Clang noch OpenMP Support. Du musst also wohl oder übel den Gnu oder Intel Compiler nehmen. Die nächste Alternative wäre MPI das wurde für verteilte Systeme entwickelt und zwingt dich damit den Problem zu partitionieren. Mir liegt MPI besser. Das mag aber auch an den Problemen liegen die ich lösen musste.

Das wären die halbwegs eleganten Lösungen. Beide sind nur auf parallele Berechnung ausgelegt. Für parallele I/O sind sie nicht so gut zu gebrauchen.

Für völlig triviale Probleme reicht natürlich auch POSIX Threads direkt zu verwenden. Bei komplizierten Problemen hilft einem manchmal keine bestehende Abstraktion.

Mein Rat daher: Sieh dir OpenMP an. Ignoriere MPI, denn es zwingt dich vermutlich dein ganzes Programm neu zu schreiben. Sollte OpenMP nicht das richtige sein oder dir danach sein nimm direkt POSIX Threads. Ansonsten gibt es für C++ auch noch die Intel TBB zu denen ich nichts sagen kann.
 
Du bist in O(n^3) und glaubst Du bekommst das mit Parallelisierung in den Griff?

Ich glaube Du solltest lieber Deinen Algorithmus beschreiben/optimieren.
 
Hmm, und wenn du so 100 Stunden brauchst, sollte der Aufwand doch auch noch recht hoch bleiben, selbst wenn du vier Kerne z.B. nutzen kannst.

Das wären dann im minimalen Fall noch immer mehr als 25 Stunden oder sehe ich das falsch?
 
Kamikaze schrieb:
Du bist in O(n^3) und glaubst Du bekommst das mit Parallelisierung in den Griff?

Ich glaube Du solltest lieber Deinen Algorithmus beschreiben/optimieren.
Zum Vergrößern anklicken....

Du kennst doch unseren Herakles für ihn ist das Forum sein Ersatz fürs K&R Buch und printf()/Debugger.

Sieht so aus als kämen langsam auch komplizierte Probleme dran.
 
Nun, es gibt auch tatsächlich Dinge die gehen nicht unter O(n^3). Ich habe in meiner Thesis sogar ein O(n^3 log(n)) drin.

Aber bevor ich meine Finger in den Bereich Simulation gesteckt habe ist mir so etwas noch nicht untergekommen. Man kann fast überall schummeln, besonders wenn eine gute Lösung reicht.

Ach so, ganz nebenbei. Ich habe C++ verwendet. Der konsequente Einsatz von const und inline (wo es Sinn macht) machen bei mir ca. 50% Performance. Zumindest const Parameter kann und sollte man auch unter C verwenden. Wenn man mit LTO linkt bekommt man auch ohne inline Inlining. Das könnte sich je nach Anwendung extrem rechnen.
 
Dafür fehlt C++98 noch immer restrict. Dort wo const passt ersetzt es restrict oft. Inline bzw. Templates können tatsächlich helfen auch dort generisch zu programmieren wo es in C99 nur die Wahl zwischen fürchterliche Macros oder Funktionspointern gibt.
 
@Crest: Deine Hilfen an vielen Stellen in allen Ehren, aber ich nutze das Forum nicht als Ersatz für Bücher oder eigenes Debugging. Ich stelle Fragen, die sich auf Themen im Bereich "programmieren" beziehen, die ich gewiss auch selbst durch intensive Recherche herausfinden könnte. Mein Nachteil bei dieser Art und Weise des Studiums ist, dass es letztendlich ein SELBSTstudium bleibt und ich damit evtl. auf einem kleinen Stückchen Wissen hängen bleibe("lokales Optimum" ;) ) und mich darauf versteife, obwohl es dann insgesamt doch eine veraltete Idee ist oder es gar viele unterschiedliche Lösungsmöglichkeiten gibt, die ich aber bei meiner Suche übersehe.

Mein Problem ist einfach oftmals, dass ich Themen ankratze, mit denen ich zuvor nicht zu tun hatte und leider niemanden haben, mit dem ich mich persönlich austauschen kann. Hier habe ich ein Forum von - meiner bescheidenen persönlichen Meinung - exzellenten Experten(und ja, dazu zähle ich auch Dich, Crest), von denen ich "Wissenspointer" abgreifen kann - sprich mich zu Themen hinleiten lassen kann. wie in diesem Fall das Thema "Openmp".

Im aktuellen Fall habe ich beispielsweise beim "googlen" Artikel im Internet von Anfang des Jahrtausends gefunden, wo ich direkt dachte "das geht heute besimmt noch eleganter oder effizienter oder auf jeden Fall wird's sicher heute anders gemacht". Ein Beispiel eines Ergebnisses meiner Suche:

Ein Linux SMP Howto

Über das Thema "Forumsbenutzung" hatten gerade wir zwei uns doch schon in diesem Thread unterhalten. Ich halte mich nicht für faul, sondern für außerordentlich interessiert, leider mit wenig Zeit ausgestattet, aber auf jeden Fall Willens, über den Tellerrand hinauszuschauen. Und genau dieses Weiterblicken versuche ich mit Hilfe der Forenuser zu erreichen - ich möchte mir zeigen lassen, welche anderen Optionen es noch gibt und welche Option der echte Experte im jeweiligen "Programmierunterkontext" wählen würde. Resultat dieses Threads wird für mich sein, dass ich mir Openmp sehr viel genauer anschauen werde, denn ich finde die Thematik sehr spannend. Für mich ist das Forum ein großer Fundus, den ich im persönlichen Umfang auf dieser Ebene(professionelle Programmierung) nicht finde. Ich hoffe, ich finde dafür aber Dein Verständnis, Crest. :) Und jetzt bitte kein Flamewar...

...sondern back to topic! Wenn ich also einmal Kamikaze zitieren darf:

Ich glaube Du solltest lieber Deinen Algorithmus beschreiben/optimieren.
Zum Vergrößern anklicken....

Dann versuchen wir das doch mal - zumindest diejenigen, die es interessiert und die Lust drauf haben. Ich habe einfach einmal ein sehr primitives Programm zusammengeschrieben, das zumindest vom Prinzip her macht, was hier hinterfragt wurde. Ich würde gern sehen, wie man so etwas "eleganter" oder "effektiver" macht. Natürlich ist es vollkommen sinnfrei, es erzielt einfach nichts und davon abgesehen macht es auch in jedem Schleifenlauf immer wieder dasselbe. Ich denke aber, dass das in diesem Fall egal ist, da es nur um's Schleifenprinzip geht.

Also: Nehmen wir an, so eine "analyze_databse"-Funktion würde etwas Sinnvolles tun, wie würdet Ihr es anders programmieren, was würdet Ihr optimieren? Der Code ist als Textdatei angehängt.

Nur kurz nebenbei meine Ergebnisse(habe das auf meinem Thinkpad T530 gerechnet, ist mein Arbeitsrechner und dort rennt ein Ubuntu-Linux):

Code: 
herakles@countach ~ $ gcc smp_test.c -Wall -fopenmp
herakles@countach ~ $ time ./a.out 
best: 58719, wert: 2147477479

real	0m7.622s
user	0m44.843s
sys	0m0.076s
herakles@countach ~ $ uname -a
Linux countach 3.5.0-17-generic #28-Ubuntu SMP Tue Oct 9 19:31:23 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux

Das parallelisieren bringt mir also in der Tat einen beachtlichen zeitlichen Vorteil, dafür sind auch entsprechend viele Kerne auf dieser Kiste vorhanden.

Any comments?

Herakles
 

Anhänge

Denke daran, im besten Fall ist dein Performance Gewinn per Core linear. Wenn sich also Dein Datensatz verdoppelt benötigst Du mindestens 8 * so viele Cores um die Performance zu halten.

So jetzt zu deinem Algo. Wieso gehst du mehr als einmal durch die Liste? So wie ich das sehe machst du einfach nur unglaublich oft immer wieder das gleiche. Beschreibe einfach mal was das Ding tun soll, ich werde daraus nicht schlau.
 
Wie ich bereits schrieb:

Natürlich ist es vollkommen sinnfrei, es erzielt einfach nichts und davon abgesehen macht es auch in jedem Schleifenlauf immer wieder dasselbe. Ich denke aber, dass das in diesem Fall egal ist, da es nur um's Schleifenprinzip geht.
Zum Vergrößern anklicken....

Es geht also in diesem Fall um rein gar kein Ergebnis, sondern nur um das Prinzip. Ein und dieselbe Funktion wird einfach immer wieder durchgenudelt. Man könnte sich einfach vorstellen, dass die Funktion drei Parameter brauchen könnte - die werden dann in jeder Schleife anders sein, wenn es die Variablen "i", "j", und "k" wären, die an die Funktion übergeben würden.

Ich habe dafür jetzt so keinen Code, es geht mir einfach nur darum, was man do so anders machen könnte.

Wenn Du mit "besser beschreiben" oder "optimieren" den Inhalt des Analyse-Algotihmus meinst, dann ist mir damit auch geholfen. Dann haben wir danach einfach aneinander vorbei geredet.

Nxi für Ungut,
Herakles
 
Nein, die Idee ist natürlich, dass es so eine Schleife schlicht nicht existieren sollte. Ich dachte es ginge hier um eine konkrete Anwendung.
 
Herakles: Bitte verstehe mich nicht falsch. Ich beteilige mich an deinen Threads, weil sie zum Großteil interessante Fragen betreffen. Nur habe ich oft den Eindruck dir fehlt ein Überblick, den kein Forum sondern nur ein paar Bücher und das Lesen von viel fremden Code dir geben können.
 
Ich muss hier jetzt noch mal nachhaken. Meiner Meinung nach ist alles über O(n log(n)) erst mal nicht tragbar.

O(n log(n)) ist noch ziemlich gut aber schon O(n^2) geht nur noch wenn man garantieren kann dass n klein ist. Ein Beispiel dafür ist 3-D Grafik, die Verarbeitungsdauer für eine Geometrie wächst linear, also O(n) mit der Zahl der Polygone.

Aber das Zeichnen wächst mit x * y was O(n^2) nach unserem Verständnis von Auflösung ist. In all der Zeit seitdem ich 3-D Spiele spiele hat die Auflösung sich gerade mal versechsfacht.

Wer sich etwas mit Sensorik und Signalverarbeitung auskennt weiß, dass Abtastraten von 10 * der gewünschten Auflösung ziemlich üblich sind (Beispiel CAN-Bus, da verwende ich in der Regel 12 Samples für ein Bit).

Entsprechendes müsste auch für Menschliche Wahrnehmung gelten. Das Menschliche Gehirn ist darauf optimiert Störungen zu erkennen, es gibt Menschen die noch bei 100Hz Flimmern wahrnehmen obwohl wir nur ca. 15 Bilder pro Sekunde verarbeiten können. Erst bei 120Hz merkt wirklich niemand mehr etwas (Quelle ist ein Probandentest aus dem professionellen Umfeld, keine veröffentlichte Studie).
Astronauten können von der ISS mit bloßem Auge einzelne LKWs in der Sahara erkennen. Die sind zwar eigentlich viel zu klein gemessen an der Nervendichte im Auge, aber das menschliche Auge zittert und erhöht auf diese Weise die Auflösung.

Entsprechend müsste 3-D Grafik also mit einem vielfachen der Auflösung des menschlichen Auges mit 120 FPS gerendert werden. Ich habe ja schon öfter geäußert, dass ich 240DPI, das sind ~ 8000x5000 Bildpunkte bei einem 24" 16:10 Monitor, für angemessen halte.

Warum das alles noch nicht so ist, liegt alles an der O(n^2) Problematik. Die schlägt gleich doppelt zu, in der Grafikverarbeitung und bei der Herstellung von Panels. Denn auch die wahrscheinlichkeit von Pixelfehlern wächst mit O(n^2).

Oder anders gesagt. Alles was in O(n^2) oder schlimmer läuft gehört auf einen Rechencluster für industrielle oder wissenschaftliche Anwendungen.

Dein Beispiel ist einfach so Praxisfern, dass der Lernerfolg erst mal keinen Wert hat.
 
Zuletzt bearbeitet:
Moin!

Auch auf die Gefahr hin, dass ich mir nun wieder den Unmut von Crest zuziehe, möchte ich mein aktuelles Problem mit dem beschriebenen Programm darstellen.

Speicher, den ich mit malloc(3) anlege, wird offenbar mit free(3) nicht wieder freigegeben.

Folgendes Problem: Ich alloziere also mit malloc, lasse das eine längere Zeit so laufen, damit auch sichtbar viel Speicher benutzt wird, warte dann ein paar Sekunden, damit ich mit free(1) auf der Konsole beobachten kann, dass auch wirklich gerade Speicher "benutzt" wird und gebe diesen Speicher dann mit free(3) wieder frei.

Problem: Das scheint überhaupt nicht zu geschehen. Das Programm schreibt "alloc fertig", wenn es Speicher alloziert hat, waret dann 20 Sekunden, damit man die Speicherauslastung beobachten kann, schreibt dann "free fertig", wenn es den Speicher wieder freigegeben hat, wartet dann wieder 20 Sekunden, damit man wieder die Speicherauslastung beobachten kann und beendet sich dann.

Dabei ist folgendes zu beobachten:

Vor der Prgrammausführung sieht der Speicher wie folgt aus:

Code: 
$ free
             total       used       free     shared    buffers     cached
Mem:       7634216    2987444    4646772          0      73716    2114728
-/+ buffers/cache:     799000    6835216
Swap:      7833596          0    7833596

Dann wird das Programm losgelassen:

Code: 
$ ./a.out 
alloc fertig

Hier sieht man, dass auch einiges an Speicher genutzt wird. Man beachte "Mem used: 3143948", was zuvor nur bei 2987444 lag.
Code: 
$ free
             total       used       free     shared    buffers     cached
Mem:       7634216    3143948    4490268          0      73724    2114728
-/+ buffers/cache:     955496    6678720
Swap:      7833596          0    7833596

Nun also kommt das free(3) im Programm:

Code: 
free fertig

Das resultiert in folgender Speicherauslastung:

Code: 
$ free
             total       used       free     shared    buffers     cached
Mem:       7634216    3143940    4490276          0      73724    2114728
-/+ buffers/cache:     955488    6678728
Swap:      7833596          0    7833596

Das sieht verdächtig ähnlich aus, wie zuvor, als das Programminterne free(3) noch nicht gearbeitet hatte.

Wenn das Programm nun ans Ende kommt, also die 20 Sekunden finale Wartezeit abgelaufen sind, dann wird der Speicher freigegeben:
Code: 
$ free
             total       used       free     shared    buffers     cached
Mem:       7634216    2987568    4646648          0      73724    2114728
-/+ buffers/cache:     799116    6835100
Swap:      7833596          0    7833596

Warum ist das so? Wieso wird der Speicher nicht schon freigegeben, während das Programm es macht, sondern erst nach Beendigung des Programms? Ich denke da wirklich schon sehr lange drüber nach und finde den Fehler einfach nicht. Das Programm habe ich angehängt.

Ach ja:
Aus bereits zuvor in diesem Thread genannten Gründen läuft das Programm auf einem Linux.

Es grüßt der grübelnde
Herakles
 

Anhänge

Ich denke das läuft nicht synchron. Das System wird da erst bei Bedarf aufräumen. Nur eine Vermutung.
 
Hmmm. Ja, das mag sein. Blöd nur, dass das System, wenn ich das Ganze in eine Schleife packe(also Speicher allozieren und anschließend wieder freigeben) und das lange genug treibe, beginnt auszulagern. Der Speicher wird dann also irgendwann knapp bzw. geht aus.

Das würde wiederum bedeuten, dass free(3) gar keinen Effekt hätte und das fänd ich doch sehr fadenscheinig.

Vielleicht ist es aber ein reines Linux-Problem. Ich sollte also mal auf einem *BSD testen, ob dasselbe Phänomen autritt, oder?

So wirklich überzeugt mich das nicht... (Ach ja, es hat übrigens schon nichts mehr mit Parallelisierung und OpenMP zu tun...)

Herakles
 
Also für Speicher den man bis (fast) zum Ende seines Programms braucht ist es technisch gesehen nicht nötig ihn per free() frei zu geben. Es nicht zu tun ist nur sehr schlechter Stil. Sobald ein Prozess sich beendete wird all sein Speicher eh freigegeben. Solltest du später Memoryleaks mit Valgrind o.ä. suchen hast du soviele Falsepositives, dass dir schnell der Spaß vergehen wird, wenn du deinen Speicher nicht brav frei gibst sobal du ihn nicht mehr brauchst.
 
Herakles schrieb:
Das Programm habe ich angehängt.
Zum Vergrößern anklicken....

Läuft unter OpenBSD wie erwartet, reserviert also Speicher und gibt ihn wieder frei.

... jedenfalls nachdem ich einen Programmierfehler korrigiert habe. Du musst Ppoint_element vor der while-Schleife auf NULL setzen, denn sonst springst du schon von Anfang an wild im Speicher herum, was dann zum Segfault führt.

Ich bezweifel aber, dass Linux dadrüber hinwegsieht. Weiß nicht wie es da mit Werten im Stackspeicher aussieht, aber aus C-Sicht hattest du einfach Glück. ;)
 
Paldium, Du hast recht, die Initialisierung fehlte.

Doch auch mit Deinem Bugfix arbeitet das Programm in Linux wie gehabt...

Was soll man davon halten?
 
Also auf den ersten Blick würde Kamikaze zustimmen, die glibc deines Linux-Systems wird wohl Doug Leas malloc einsetzen. Diese malloc-Implementation besitzt ein Caching, mit dem einmal reservierte Speicherbereiche gecacht werden, weil sie "wahrscheinlich wieder angefragt werden."

Wenn ich mir aus malloc-Sicht deinen Beispielcode ansehe, dann würde ich auch tippen, dass du bald wieder neuen Speicher für Nodes anfragen wirst. ;)

Aber ist jetzt auch nur ins Nichts geraten. Was ich persönlich schlimmer finde, ist dass eine Prüfung auf NULL von malloc()s Rückgabewert unter Linux nichts bringt... Der wird nämlich erst bei Bedarf physisch reserviert, womit der Zeiger im virtuellen Adressraum erstmal blanko ausgestellt wird. Aber jedem wie er mag.

PS: Ja, ich weiß dass man unter Linux im proc-Dateisystem einstellen kann, dass malloc() sich anders verhalten soll. Standard ist aber: Erst allozieren wenn wirklich jemand reinschreibt.
 
Paldium: Das macht OpenBSD nicht anders. Bloß weil du per mmap() ein Stück Speicher gemapped hast heisst das nicht das da auch physikalischer Speicher drauf gemapped ist. Es ist ebenso möglich das du eine als COW markierte genullte Seite geraten bist und später(tm) beim ersten Schreibzugriff der Kernel sehen muss wo er Pageframes für dich findet. Was allerdings OpenBSD macht, wenn es auch durch Swapping nicht genug RAM findet kann ich aus dem Stand nicht sagen. Nur gehe ich mal davon aus das es keinen OOM Killer gibt oder ähnlichen Schwachsinn.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben