Was bringt die Parallelisierung

[2bsquare]

Gregor schrieb:

Das kann man nicht allgemein beantworten.

Wie kommt ihr darauf, dass ich eine allgemeine Antwort will?

2bsquare schrieb:

Habt ihr bei euren Programmen schon mal getestet, wie lang etwas braucht, wenn es auf einem oder mehreren Kernen läuft? Wenn ja, wie groß war der Unterschied und was macht das Programm?

2. Ich halte es für einen Mythos, dass funktionale Programmiersprachen für die Parallelisierung besonders gut sind.

Würde ich hiermit ja mal gerne prüfen.

[2bsquare]

Gregor schrieb:

4. Wie viel ein Programm durch eine Parallelisierung gewinnt, kann man eigentlich recht leicht mit Amdahls Gesetz abschätzen. Miss vorher, wie viel Laufzeit in den parallelisierbaren Codebereichen benötigt wird, dann kannst Du auch abschätzen, wie viel das Gesamtprogramm von einer Parallelisierung profitieren würde.

Naja, das Problem ist doch den parallelisierbaren Codebereichen zu finden. Wenn du irgendein komplexeres Programm hast, das irgendwelche Datenstrukturen aufbaut, kann es zar sein, das der gesammte Prozess nicht einfach parallelisiert werden kann, aber vielleicht viele kleine Teile davon.

[Zeus]

2bsquare schrieb:

Warum antwortet ihr nur Müll?

knivil schrieb:

Genauso viel wie bei prozeduralen Programmen. Der Unterschied war 3.

Jetzt mal im Ernst du fragst, was dir es bringt und versteht nicht, was Unterschied 3 bedeutet?

[2bsquare]

Zeus schrieb:

2bsquare schrieb:

Warum antwortet ihr nur Müll?

knivil schrieb:

Genauso viel wie bei prozeduralen Programmen. Der Unterschied war 3.

Jetzt mal im Ernst du fragst, was dir es bringt und versteht nicht, was Unterschied 3 bedeutet?

Willst du sagen, der ganz Hype um die tolle Parallelisierbarkeit von mit funktionalen Sprachen geschriebene Programmen ist nur Quatsch und funktionale Sprachen bringen da rein garnichts an Vorteilen?

[Shade Of Mine]

2bsquare schrieb:

Willst du sagen, der ganz Hype um die tolle Parallelisierbarkeit von mit funktionalen Sprachen geschriebene Programmen ist nur Quatsch und funktionale Sprachen bringen da rein garnichts an Vorteilen?

Sicher. Der Vorteil ist etwa 3.

Stell eine vernuenftige Frage, dann bekommst du eine vernuenftige Antwort.

[nurso]

Gregor schrieb:

2. Ich halte es für einen Mythos, dass funktionale Programmiersprachen für die Parallelisierung besonders gut sind. Sicherlich ist es so, dass bestimmte Algorithmen mit funktionalen Programmiersprachen sehr elegant zu formulieren sind, so dass eine Parallelisierung auf dieser Basis sehr einfach ist. Bei anderen Algorithmen wird das anders sein. Nicht alle Aufgaben sind für funktionale Sprachen prädestiniert.

Und das halte ich jetzt aber für uninformiert. Es gibt zum Teil ganz nette Überblicks- Pdfs:
http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/Parallel-Haskell.pdf
http://www.doc.ic.ac.uk/teaching/distinguished-projects/2009/w.jones.pdf
http://parallel.illinois.edu/blog/so-what-new-parallel-computing-revisiting-tutorial-parallel-processing
oder auch benchmarks:
http://shootout.alioth.debian.org/u64q/benchmark.php?test=threadring&lang=all

Keine Silver Bullets - das ist soweit klar...aber das eine Sprache nicht für alles passt, das kann man zu jeder Sprache sagen.

Parallelisieren heißt aber auch, viel herumprobieren, das Genre ist nach wie vor Erfahrungshungrig, und in der Praxis muß man halt gucken, wer die ausgereifteren, prozessorfreundlicheren Compiler und Bibliotheken und ähnliches zur Verfügung hat.

Letztlich muß man aber auch unterscheiden, zwischen der Hardware (Pipelines, Datenaustausch, Hardwareboosts(Java, Komprimierung) dem Betriebsystem (threads, Schnittstellen) und den Programmen (Algorithmen, Datenstrukturen) und da bleibt letztlich eben noch viel Raum von Möglichkeiten und Kombinationen und neuen Wegen.

Ein wenig könnte man den Eindruck bekommen, die Dinge egalisieren sich irgendwie, schlechte Didaktik und schwache Community hier, Fehleranfälligkeit und Intelcompiler und Bibs dort, und anderswo - Community gut, Didaktik gut, aber lahm (Python/Basic, runtimebibgedöns), aber es interessiert keinen, weil handy und sexy usw.

[Zeus]

2bsquare schrieb:

Willst du sagen, der ganz Hype um die tolle Parallelisierbarkeit von mit funktionalen Sprachen geschriebene Programmen ist nur Quatsch und funktionale Sprachen bringen da rein garnichts an Vorteilen?

Dort wo du ein Hype siehst, ist kein Hype da. Es gibst kein Hype um die Parallelisierbarkeit sondern es gibt ein Hype um die deklarative Programmierung in funktionale Programmiersprachen, diese Elemente die seit einige Zeit von den funktionale Programmiersprache in die imperative übernommen werden: Lambda, Pattern, Typesystem, ..., in Programmiersprache wie Ruby, Python, C#, D, Cylon, Rust, ... , um Lösung effizient auszudrücken. Parallelisierbarkeit ist ein Aspekt davon, aber leider wohl der Trendsetter .

[2bsquare]

Shade Of Mine schrieb:

2bsquare schrieb:

Willst du sagen, der ganz Hype um die tolle Parallelisierbarkeit von mit funktionalen Sprachen geschriebene Programmen ist nur Quatsch und funktionale Sprachen bringen da rein garnichts an Vorteilen?

Sicher. Der Vorteil ist etwa 3.

Stell eine vernuenftige Frage, dann bekommst du eine vernuenftige Antwort.

Seit ihr ehrlich nicht in der Lage diese Frage zu verstehen?

2bsquare schrieb:

Habt ihr bei euren Programmen schon mal getestet, wie lang etwas braucht, wenn es auf einem oder mehreren Kernen läuft? Wenn ja, wie groß war der Unterschied und was macht das Programm?

Ich dachte die Leute hier schreiben Programme in Haskell oder ähnlichen Sprachen. Kann doch nicht so schwer sein die Frage dann zu beantworten. Muss ich ein Beispiel machen, damit ihr die Frage versteht.
Meinen Raytracer habe ich mit der Sprache X geschrieben, er rendert 2 FPS auf einem Core und 14 FPS auf 8 Cores.

Oder schreibt ihr nur 3 Zeiler Progrämmchen ala Fibonacci in Haskell?

Zeus schrieb:

2bsquare schrieb:

Willst du sagen, der ganz Hype um die tolle Parallelisierbarkeit von mit funktionalen Sprachen geschriebene Programmen ist nur Quatsch und funktionale Sprachen bringen da rein garnichts an Vorteilen?

Dort wo du ein Hype siehst, ist kein Hype da. Es gibst kein Hype um die Parallelisierbarkeit

Echt? http://www.c-plusplus.net/forum/p2243129#2243129 War da sogar Shade der hier die Frage dann nicht versteht.

Das merkt man schon zB wenn man sich funktionale Sprachen und automatische parallelisierung ansieht

[2bsquare]

Edit: Seid
vor wieder einer nörgelt.

[Gregor]

2bsquare schrieb:

2bsquare schrieb:

Habt ihr bei euren Programmen schon mal getestet, wie lang etwas braucht, wenn es auf einem oder mehreren Kernen läuft? Wenn ja, wie groß war der Unterschied und was macht das Programm?

Ich dachte die Leute hier schreiben Programme in Haskell oder ähnlichen Sprachen. Kann doch nicht so schwer sein die Frage dann zu beantworten. Muss ich ein Beispiel machen, damit ihr die Frage versteht.
Meinen Raytracer habe ich mit der Sprache X geschrieben, er rendert 2 FPS auf einem Core und 14 FPS auf 8 Cores.

Oder schreibt ihr nur 3 Zeiler Progrämmchen ala Fibonacci in Haskell?

Oh, ok. Wir entwickeln in unserer Arbeitsgruppe Programme, die Materialien simulieren bzw. deren physikalische Eigenschaften vorhersagen. Dafür kommen oft Cluster oder sogar massiv parallele Supercomputer zum Einsatz. Das heißt, man hat es mit Systemen folgender Art zu tun: 1. Man hat einige Rechenkerne in einem Prozessor. 2. Man hat mehrere Prozessoren in einem Rechenknoten. 3. Man hat viele Rechenknoten, die über ein Netzwerk mit einander verbunden sind. Dort können die Verbindungen zum Beispiel n-dimensionale Toroide ergeben. Jeder Rechenknoten ist dann besonders schnell vor allem mit wenigen direkten Nachbarn verbunden.

Bei der Parallelisierung hat man es hier also mit Problemen auf ganz unterschiedlichen Ebenen zu tun. Über die Rechenknoten sollte so parallelisiert werden, dass möglichst wenig Daten zwischen den jeweiligen Knoten ausgetauscht werden müssen, damit das Netzwerk nicht überlastet wird. Wenn Daten ausgetauscht werden, dann möglichst nur zwischen direkten Nachbarn. Im anderen Extrem geht es um die Parallelisierung über mehrere Rechenkerne in einem Prozessor bzw. um die Parallelisierung in einem Rechenknoten. Hier ist es wichtig, dass sich die parallelen Rechnungen nicht gegenseitig aus dem Cache hauen. Letztendlich benötigt man also auf unterschiedlichen Ebenen unterschiedliche Ansätze zur Parallelisierung, um wirklich das Optimum herauszuholen. Wie gesagt: Bei uns werden keine funktionalen Sprachen eingesetzt. Die findet man auf Supercomputern eh nicht. Sprachen, die dort zum Einsatz kommen sind Fortran und C++. Bei uns vor allem Fortran. Zur Parallelisierung wird MPI und OpenMP verwendet. ...und möglicherweise wird es auch noch andere Mittel geben, wenn zum Beispiel GPU Programming für diesen Bereich relevant wird.

[knivil]

Hier geht es nicht um Supercomputer und Simulation. Aber vielleicht eine Boersensoftware, Fughafen, Kontenverwaltung oder Ticketbuchsystem. Dort wo parallel hergenommen wird, um eine Berechnung zu beschleunigen, sondern weil der Prozess parallel ist. Dort wo es tatsaechlich zu race conditions oder Deadlocks kommt.

[Gregor]

knivil schrieb:

Hier geht es nicht um Supercomputer und Simulation. Aber vielleicht eine Boersensoftware, Fughafen, Kontenverwaltung oder Ticketbuchsystem. Dort wo parallel hergenommen wird, um eine Berechnung zu beschleunigen, sondern weil der Prozess parallel ist. Dort wo es tatsaechlich zu race conditions oder Deadlocks kommt.

Im Beispiel des Threaderstellers ging es um einen Raytracer. Wenn ich mir die Parallelisierung dort ansehe, zumindest so mir das naiv möglich ist, dann gehe ich davon aus, dass mein Beispiel nicht deplatziert war. Ok, es war insofern deplatziert, als es auf einen großen Bereich hindeutet, in dem Parallelisierung betrieben wird, der absolut nichts mit funktionalen Sprachen zu tun hat. ...andererseits ist mir auch nicht bekannt, dass Leute Raytracer mit funktionalen Sprachen programmieren, "weil die ja für die Parallelisierung so toll sein sollen".

Ich bin selbst sehr gespannt, was hier an Beispielen herumkommt, bei denen funktionale Sprachen eingesetzt werden. Ich habe eine Vermutung, was da ungefähr an Beispielen kommen wird, aber ich überlasse das mal den Leuten, die tatsächlich funktionale Sprachen nutzen.

[knivil]

Ich habe mal mal was von High Performance ML oder so gehoert. Als Beispiel haben sie die Implementation eines Raytracer verglichen. Jedoch sollte man funktionale Sprachen aus diesem Segment nicht grundsaetzlich ausschliessen, wiehe fftw. Das hat auber nur bedingt was mit "parallel" zu tun.

weil die ja für die Parallelisierung so toll sein sollen

Naja, toll bedeutet nicht immer beste Performance. Vielleicht auch einfacher Ausschluss von Programmierfehlern, die eben parallele Programmierung um ein wesentliches schwieriger macht.

[nachtfeuer]

Gregor schrieb:

Ich bin selbst sehr gespannt, was hier an Beispielen herumkommt, bei denen funktionale Sprachen eingesetzt werden. Ich habe eine Vermutung, was da ungefähr an Beispielen kommen wird, aber ich überlasse das mal den Leuten, die tatsächlich funktionale Sprachen nutzen.

vermutlich Programme, die auf "Algorithmen" wie diesem hier aufbauen:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

...
zum Thema Raytracer gibt es eine bekanntere Seite http://www.ffconsultancy.com/languages/ray_tracer/index.html , auf der Haskell aber nicht so gut bei wegkommt. Man findet aber auf anderen Bloggerseiten und Co, dass Haskeller sich darüber ein wenig darüber wundern und wie sich zeigt, nicht ganz unbegründet. Aber bei allen Vergleichen bleibt Summasummarum C++ schneller.
Nichtsdestotrotz zeigt die Entwicklung auch, dass Haskell noch relativ starken Optimierungsbedarf hat, bzw. Headroom in dieser Hinsicht (und nicht nur Compiler-und Programmiertechnisch, oder GUI betreffend), und ... - aber auch, dass eben, je mehr Kerne und Threads im Spiel sind, desto besser für Haskell und die einzelnen "Funktionen".
Und das ist, so meine ich, auch die Zukunft: Selbstlaufende, selbstentscheidende Computer mit großer paralleler Datenauswertung, möglichst tight und fehlerfrei im Code.
Und: Haskells Typenvielfalt kann einen in die Verzweiflung oder in den Wahnsinn treiben...aber Wahnsinn und Genie, so sagt man, liegen nah beieinander...;)
(Man fragt sich ein bißchen, was wohl der Herr Cantor von haskelltypisch düsteren, multiparametrisch-rekursiven Datentypen gehalten hätte...aber auf jeden Fall war der Cantor nicht nur ein hervorragender Mathematiker, sondern auch ein sehr guter Didakt)
(Die Freiheit und die mögliche Kreativität und Virtuosität, die hinter dem Wahnsinn warten, würde vielleicht aber auch die Weiterentwicklung eines Raytracers, oder der zukünftigen Hardware selber mitbestimmen.)
So gesehen, mache ich mir keine großen Gedanken um die Performance. Erstens gibt es Profiler, und man kann (fast) immer Hardwareoptimierung machen, wenn es sein muß (oder lowerlevel C, wenn C=Kerncompiler; aber neuere GHC Compiler werden besser http://www.haskell.org/ghc/docs/latest/html/users_guide/code-generators.html), und zweitens, haben funktionale Sprachen eher ein Communityproblem als Performanceprobleme. Haskell ist eine große Chance der funktionalen Community.

Und..oh Wunder...Assemblerprogrammierkenntnisse helfen bei Haskell. Erstmal, um den Code aufzupimpen, klar, aber auch, um bestimmte Funktionen zu finden.
Wenn man auf der Haskell-Wikiseite nach Fibonaccis guckt http://www.haskell.org/haskellwiki/The_Fibonacci_sequence
Dann kann man zwar viel über die Haskellprogrammierung lernen, über Tricksereien, aber über klare, einfache Performance? Wo ist mein beliebter

add rax,rbx
add rbx,rax

Ping-Pong-Algo?
(oder mal eine nähere Erklärung des Codes, andere sehen vielleicht nicht alles auf einen Blick?)
(pythonhacker können asm, sieht man gleich)

Was man also eigentlich braucht (neben mathematischen Kniffen), sind drei "Register", zwei zum Hin - und Heraddieren, und einen Zähler. Und statt den Fibonaccizahlen, wird der Zähler rekursiv heruntergezählt. Und flupp...

Diese Haskell-Wikiseite zeigt, dass viele Haskeller gar kein Assembler können oder performanten Code vernünftig dokumentieren können.
Und genau das ist in C-Kreisen ganz anders. Viele Profis, schon von Kindheit an dabei, hochoptimierte Bibliotheken, aber auch Geschäftsmodelle als Motor, gute C oder Fortrancompiler http://www.pgroup.com/resources/cudafortran.htm waren oder sind nicht unbedingt billig.

[ipsec]

Ich denke es ist prinzipiell nicht strittig, dass sich (rein) funktionaler Code besser parallelisieren lässt als imperativer. Das liegt vor allem daran, dass alle Funktionen schon per Definition seiteneffektfrei und somit thread-safe sind, ferner ist die Auswertungsreihenfolge egal und dank immutablen Variablen ist jegliche Art von Synchronisation, egal ob manuell oder automatisch, nicht notwendig. Auch bei dem tatsächlich effektvollem Code ist die Parallelisierung in Haskell dank höhere Threadabstraktion einfacher und im allgemeinen weniger fehleranfällig als in Sprachen wie C++.

Das heißt aber nicht, dass Haskell für parallele Programme generell besser geeignet ist als in C++. Gerade bei hochperformanten Anwendungen (wie z.B. Raytracer) ist C++ (noch) die bessere Wahl, zum einen dank bessere Compiler (Haskell ist generell etwas langsamer als C++), zum anderen, weil man besser optimieren kann. Auch ist die automatische Parallelisierung auch bei funktionalen Sprachen allenfalls noch in den Kinderschuhen. Dafür wird der Programmieraufwand in C++ in der Regel höher sein.

Nicht immer ist aber bei der Parallelisierung die Performance das Wichtigste bzw. das Ziel. Bei einem Server beispielsweise, der mehrere Clients gleichzeitig bedienen soll, kann Haskell mit höherer Abstraktion, einfacherem Threadmanagement, somit weniger fehleranfälligem Code und kürzerer Entwicklungszeit punkten. In C++ könnte man sicher auch dort ein paar Prozent rausholen, allerdings mit deutlich höherem Aufwand, der sich meistens nicht lohnt.

[knivil]

Auch ist die automatische Parallelisierung auch bei funktionalen Sprachen allenfalls noch in den Kinderschuhen.

Also ich fand die Paper bei Haskel schon beeindruckend. Und dann gibt es ja noch die anderen: Lisp und ML. Neu fuer die Java VM ist Clojure. Da steckt wenig in den Kinderschuhen.

Was man also eigentlich braucht (neben mathematischen Kniffen), sind drei "Register", zwei zum Hin - und Heraddieren, und einen Zähler. Und statt den Fibonaccizahlen, wird der Zähler rekursiv heruntergezählt. Und flupp...

Ja, nett. Aber es gibt eine allgemeine Strategie fuer rekursive Probleme durch Programmtransformation, nachzulesen in beispielsweise in "Algebra of Programming".

[ipsec]

knivil schrieb:

Auch ist die automatische Parallelisierung auch bei funktionalen Sprachen allenfalls noch in den Kinderschuhen.

Also ich fand die Paper bei Haskel schon beeindruckend.

Interessant, hättest du ein paar Links für mich?
Ich bezog mich aber auch eher auf die praktische Umsetzung. Soviel ich weiß, wenden aktuelle Haskell-Compiler noch keine automatische Parallelisierung an. Wie ich es verstehe, ist das Hauptproblem nicht die Parallelisierung selbst, sondern das Erkennen der Stellen, wo sich Parallelisierung lohnt. Ich gebe aber zu, ich bin in dem Thema nur oberflächlich informiert, also bitte berichtige mich.

[Der Computer Veteran]

Einfach für alles Assembler nehmen und gut is, aber dafür sind ja die werten Damen/Herren der heutigen Zeit zu faul !

[maximAL]

Welche relevante funktionale Sprache bietet überhaupt schon einen Compiler, der automatisch parallelisieren kann?

[nachtfeuer]

Der Computer Veteran schrieb:

Einfach für alles Assembler nehmen und gut is, aber dafür sind ja die werten Damen/Herren der heutigen Zeit zu faul !

Assembler für hochmoderne, intern parallele RISC-Prozessoren, die neuerdings auch äußerlich parallel - mit sagen wir mal 4 * 12 = 48 Kernen oder mehr, sagen wir mal, 64, 128 oder 256 Kernen oder noch mehr, sagen wir tausenden Threads, die aufeinander abzustimmen und optimiert zu verschachtelen wären - wäre in der Tat eine eher fummelige, langwierig-mühselige und unproduktive Angelegenheit, die zusammen mit dem Geduld erfordernden Reversen undokumentierter Hardwarekomponenten im Rechner oder undokumentierter Softwarestrukturen im Betriebsystem, eine ziemliche Strafarbeit wäre, selbst für kleine, lernunwillige Computerveteranen.