Brainstorming: Paralleles Programmieren

[antisteo]

Hi,

ich habe auf Github mal ein Wiki eingerichtet, in dem ich ein bisschen über eine mögliche neue Sprache gebrainstormt habe: https://github.com/carli2/moduleson/wik ... -moduleson
Bitte gebt euren Senf dazu, damit ich gute Ideen bekomme, wie diese Sprache aussehen soll, vor allem wie grob die Granularität der Parallelisierung sein soll.

Anmerkung: Ich habe auch kein Problem damit, wenn die parallelen Programme nicht mehr auf der CPU, sondern z.B. auf einem FPGA laufen, wenn das schneller ist bzw. die Parallelisierungsmethoden dadurch effizienter werden. (Datendurchsatz)

[dot]

Wenn du Durchsatz willst: Schau mal, was so eine GPU anders macht als die CPU... ;)

[LONy]

Hm, die Frage ist ja, welche (mathematischen) Probleme sich wie aufteilen lassen, um sie überhaupt zu parallelisieren.
Es müsste denke ich eine Mischung aus paralleler und sequentieller Programmierung dabei herraus kommen.
Ein digitaler Filter (FIR) lässt sich gut parallelisieren, allerdings müssen x Werte (je nach Filterordnung) gleichzeitig zur Verfügung stehen. Ich weiß nicht, wie das in einer GraKa organisiert ist, die ja schon stark parallel arbeitet, allerdings ist bei einer normalen Multicore CPU hier denk ich der RAM der Flaschenhals... Die Architektur müsste sich wohl für so eine Programmiersprache auch ändern? In Richtung FPGA, was dann allerdings auch nur wieder sehr spezielle Problemstellungen betrifft.
Einen Programmablauf programmiert man allerdings leichter in einer klassischen sequentiellen Sprache, nicht umsonst haben FPGAs kleine Softcores von normalen Mikrocontrollern, da man bei umfrangreichen Statemachines schnell im VHDL code ersticken würde ;)

Der beste Ansatz währe wohl ein ereignisgesteuertes System, bei der man jeden Programmschritt in kleien Tasks aufteilen kann, die dann alle auf einem extra Kern ablaufen können... ich denke da z.B. an ein Spiel, bei dem alle Objekte nach Objekten in ihrer Umgebung suchen.. normal würde ich eine zweifach verschachtelte schleife Programmieren, wo der Abstand zwischen jedem Objekt berechnet wird (pseudocode):

Code: Alles auswählen

for(i=0;i<max;i++)
for(j=0;j<max;j++)
if(i!=j)
if(berechne_abstand(i,j)<100)
tu_was()

Ausführung nur auf einem Kern... sehr langsam. Besser wäre denke ich die äußere Schleife auf alle vorhandenen Kerne aufzuteilen (und vielleicht sogar die innere?)

Code: Alles auswählen

starte_neue_prozesse(max)
for(j=0;j<max;j++)
if(j!=Prozessnummer)
if(berechne_abstand(prozessnumer,j)<100)
tu_was()

tu_was() müsste hier natürlich jeweils wieder automatisch in einem neuen Prozess gestartet werden (wenn tu_was() sehr häufig aufgerufen wird) Die frage ist hier denke ich, wie kann ich allen Prozessen die entscheidenden Daten (z.B. die koordinaten der objekte) gleichzeitig bereit stellen. Man bräuchte eine art Multiport RAM, der so viele Ausgänge hat, wie prozessorkerne auf ihn zugreifen können.

wenn tu_was() nur als singleprozess abläuft und ansonsten in einer Warteschlange kommt, hätte man keine Probleme mit gleichzeitig anstehenden Ergebnissen... ansonsten müsste die Sprache befehle bereit stellen, welches Ergebnis bevorzugt wird, oder, dass in einem weiteren Thread die Ergebnisse verrechnet werden und so lange weitere Threads gestartet werden, bis nur noch ein Thread genau ein ergebnis liefert, welches dann zur weiteren Bewertung / Verarbeitung in einen dieser Multiport RAMs geschrieben wird...

Soweit mein Beitrag erstmal zum Brainstorming :D Ich kann sowohl gut C++ als auch VHDL, hab allerdings von Grafikprogrammierung auf der Graka keinen blassen Schimmer... vielleicht wird es da ja schon lange so gemacht^^ Ich hoffe meine wirren Gedanken bringen dich ein Stück weiter ;)

[antisteo]

Hm, die Frage ist ja, welche (mathematischen) Probleme sich wie aufteilen lassen, um sie überhaupt zu parallelisieren.
Es müsste denke ich eine Mischung aus paralleler und sequentieller Programmierung dabei herraus kommen.

Richtig. Das ist auch meine Grundidee.

Ein digitaler Filter (FIR) lässt sich gut parallelisieren, allerdings müssen x Werte (je nach Filterordnung) gleichzeitig zur Verfügung stehen. Ich weiß nicht, wie das in einer GraKa organisiert ist, die ja schon stark parallel arbeitet, allerdings ist bei einer normalen Multicore CPU hier denk ich der RAM der Flaschenhals... Die Architektur müsste sich wohl für so eine Programmiersprache auch ändern? In Richtung FPGA, was dann allerdings auch nur wieder sehr spezielle Problemstellungen betrifft.

Die Sprache sollte nach Möglichkeit nicht auf Shared Memory angewiesen sein. Dass Aufgaben auf komplett andere Knoten abgewälzt werden und eine Netzwerkverbindung an Bandbreite genügen muss, ist die große Kunst daran. Und genau hier muss man sehen, auf welcher Ebene man ansetzt, wie feingranular man also das System baut. Am Ende muss man genau den Punkt finden, wo die wenigsten Daten zur Kommunikation gebraucht werden und setzt dort die Grenze.

Einen Programmablauf programmiert man allerdings leichter in einer klassischen sequentiellen Sprache, nicht umsonst haben FPGAs kleine Softcores von normalen Mikrocontrollern, da man bei umfrangreichen Statemachines schnell im VHDL code ersticken würde ;)

Das sehe ich anders. Ein Programmablauf ist heutzutage eher eventgetrieben. Das kann man prima parallelisieren, wenn die Elemente sich denn nicht auf der Low-Level Ebene im Speicher so behaken würden. "Unten" macht e dann eher Sinn, sequenzielle Programme zu haben, weil das immer noch die effizienteste Methode auf heutigen SMP-Systemen ist.

Der beste Ansatz währe wohl ein ereignisgesteuertes System, bei der man jeden Programmschritt in kleien Tasks aufteilen kann, die dann alle auf einem extra Kern ablaufen können... ich denke da z.B. an ein Spiel, bei dem alle Objekte nach Objekten in ihrer Umgebung suchen.. normal würde ich eine zweifach verschachtelte schleife Programmieren, wo der Abstand zwischen jedem Objekt berechnet wird (pseudocode):

Code: Alles auswählen

for(i=0;i<max;i++)
for(j=0;j<max;j++)
if(i!=j)
if(berechne_abstand(i,j)<100)
tu_was()

Ausführung nur auf einem Kern... sehr langsam. Besser wäre denke ich die äußere Schleife auf alle vorhandenen Kerne aufzuteilen (und vielleicht sogar die innere?)

Ich finde, an dem Punkt darf man auf der äußeren Ebene nicht mehr von "Schleifen" reden, denn Schleifen sind ein sequenzielles Konstrukt. Besser wären Batches, also Stapel von unterschiedlichen Parametern, die alle in denselben Closure eingeführt werden. Map Reduce funktioniert auch nach diesem System.

Code: Alles auswählen

starte_neue_prozesse(max)
for(j=0;j<max;j++)
if(j!=Prozessnummer)
if(berechne_abstand(prozessnumer,j)<100)
tu_was()

tu_was() müsste hier natürlich jeweils wieder automatisch in einem neuen Prozess gestartet werden (wenn tu_was() sehr häufig aufgerufen wird) Die frage ist hier denke ich, wie kann ich allen Prozessen die entscheidenden Daten (z.B. die koordinaten der objekte) gleichzeitig bereit stellen. Man bräuchte eine art Multiport RAM, der so viele Ausgänge hat, wie prozessorkerne auf ihn zugreifen können.

Dabei dachte ich auch an eine Prozessorarchitektur, die nicht mehr nach Kernen, sondern nach RAM-Blöcken aufgeteilt ist. Anstatt Cachelines zu den Kernen zu bewegen, werden Threads zum richtigen RAM-Abschnitt bewegt. Resultat: man kann viel mehr Threads gleichzeitig starten (im Idealfall alle, die das Betriebssystem gerade ausführt), die Single Core Performance ist allerdings etwas geringer; Caches und Kohärenz-Probleme gehören der Vergangenheit an, da ja jeder RAM-Block nur einen Thread gleichzeitig an sich ranlässt. (Hat ein Thread allen Speicher, wird er im Chip dann in einen Bereich bewegt, wo sich ALUs befinden, um seine Rechnungen abzuarbeiten)

Alternativ kann man auch statt großen Knoten viele kleine Rechner benutzen, wo ebenfalls die Devise gilt: Das Programm muss zu den Daten und nicht anders herum.

wenn tu_was() nur als singleprozess abläuft und ansonsten in einer Warteschlange kommt, hätte man keine Probleme mit gleichzeitig anstehenden Ergebnissen... ansonsten müsste die Sprache befehle bereit stellen, welches Ergebnis bevorzugt wird, oder, dass in einem weiteren Thread die Ergebnisse verrechnet werden und so lange weitere Threads gestartet werden, bis nur noch ein Thread genau ein ergebnis liefert, welches dann zur weiteren Bewertung / Verarbeitung in einen dieser Multiport RAMs geschrieben wird...

Durchsteig' ich momentan nicht. Ich finde ja, der Programmierer sollte sich nicht um Speicherlokalität kümmern, sondern der Scheduler der Sprache sollte das gut abschätzen.

Soweit mein Beitrag erstmal zum Brainstorming :D Ich kann sowohl gut C++ als auch VHDL, hab allerdings von Grafikprogrammierung auf der Graka keinen blassen Schimmer... vielleicht wird es da ja schon lange so gemacht^^ Ich hoffe meine wirren Gedanken bringen dich ein Stück weiter ;)

Auf alle Fälle.
Naja die GRAKAs haben massive Hyperthreading, Memory-Fetch-Abschnitte im Programmabfluss und Rechen dann Stöße von Aufgaben, sobald genug Speicher da ist. Im Allgemeinen ist aber paralleles Programmieren mit OpenCL oder CUDA noch nicht die reine Intuition eines Programmierers und benötigt immer noch einen Orchestrierer, der den GPU-State aufsetzt und die Kernel startet (die alle denselben Code haben müssen).

[antisteo]

Ich werfe einfach mal ein Sprachkonzept in die Runde:

Alle Funktionen sind Abbildungen eines JSON-Objekts auf ein JSON-Objekt.

Code: Alles auswählen

Hello: {}=>{result: string}
 = {result: "Hello World"}

Auf der unteren Ebene kann man also Dinge auswerten, Datenbanken abfragen und so weiter. Auf welchem Kern oder gar Knoten das ausgeführt wird, ist egal, da ja nur der Input als JSON (notfalls serialisiert) ankommt und die Ausgabe anschließend (notfalls auch serialisiert) zur Weiterverarbeitung weitergeschickt wird.

Auf der höheren Ebene müssen diese Funktionsaufrufe dann orchestriert werden. Das heißt im Klartext, dass man über Patternmatching Felder der Ausgabefelder in neue Input-Objekte steckt, die Outputs von mehreren gleichen Ausführungen in Arrays zusammenfasst und bei anderen Prozessen ins Input steckt (reduce-Operation), aus Zahlen-Ranges neue Jobs spawnt...

Am liebsten würde ich ja gerne alles über Closures machen:

Code: Alles auswählen

spawn from 0 to 99 function(nr) {some javascript}

[antisteo]

Noch etwas ist mir in die Finger gekommen: http://strongloop.com/strongblog/promis ... callbacks/
Wenn man es noch schafft, die einzelnen Closures der Q.all-Funktion auf verschiedene Knoten aufzuteilen (Shared Memory auseinanderdröseln), wird das was.

[BeRsErKeR]

But there is one problem: We cannot keep on programming the way we program today. We mainly write sequential programs. But they only run fine on machines with a good single core performance. Due to heat problems, CPUs will not become faster.

Das versteh ich nicht so ganz. Was ist denn daran so schlimm, dass CPUs nicht mehr schneller werden? Das zeitkritischste heutzutage sind doch irgendwelche superkomplexen Berechnungen, die eh in irgendwelchen parallelisierten Supercomputern berechnet werden oder halt Computerspiele, bei denen aber meist die Grafik das Aufwendige ist (-> läuft über GPU, ist eh bereits stark parallelisiert).

Ich find es sinnvoller, dass die Leute einfach mal effizienter programmieren oder die Sprachen nicht unnötigen Overhead erzeugen, dann kommen wir auch mit heutigen CPUs gut klar.

[Krishty]

Due to heat problems, CPUs will not become faster.

Großer Schwachsinn.

[LONy]

Ich find es sinnvoller, dass die Leute einfach mal effizienter programmieren oder die Sprachen nicht unnötigen Overhead erzeugen, dann kommen wir auch mit heutigen CPUs gut klar.

Sehr guter Punkt, auch wenn er in diesem Fall leicht OT ist. Auf unserem alten 386 lief win 3.1 und word. Ich glaube man konnte damals schneller ab dem einschalten mit dem schreiben beginnen als heute...

Wir bräuchten quasi eine Sprache, bei der man weniger ineffizienten code fabrizieren kann. Eigentlich Traurig, dass heutige browsergames mot einem grafikniveau von vor 5-10 Jahren aktuelle PCs auslasten.

Rechenintensive wissenschaftliche Sachen brauchen eh experten, die wissen was sie Tun und was sie berechnen wollen. Da ist eine anspruchsvolle sprache dann nicht so das problem...

[Krishty]

Wo haben OpenCL, CUDA, AMD CAL, GLSL, und HLSL unnötigen Overhead? Im Gegenteil, viel enger an den Transistoren geht es kaum. Aber deshalb kann man ja auch nur Einmal-Benutzen-dann-Wegwerfen-Code damit schreiben …

[antisteo]

Ich find es sinnvoller, dass die Leute einfach mal effizienter programmieren oder die Sprachen nicht unnötigen Overhead erzeugen, dann kommen wir auch mit heutigen CPUs gut klar.

Sehr guter Punkt, auch wenn er in diesem Fall leicht OT ist. Auf unserem alten 386 lief win 3.1 und word. Ich glaube man konnte damals schneller ab dem einschalten mit dem schreiben beginnen als heute...

Wir bräuchten quasi eine Sprache, bei der man weniger ineffizienten code fabrizieren kann. Eigentlich Traurig, dass heutige browsergames mot einem grafikniveau von vor 5-10 Jahren aktuelle PCs auslasten.

Rechenintensive wissenschaftliche Sachen brauchen eh experten, die wissen was sie Tun und was sie berechnen wollen. Da ist eine anspruchsvolle sprache dann nicht so das problem...

Was läuft denn deiner Meinung falsch in aktuellen Sprachen?

[LONy]

Was läuft denn deiner Meinung falsch in aktuellen Sprachen?

Das etwas falschläuft kann ich so eigentlich nicht sagen. Das Problem ist denk ich, dass die Softwareprojekte aufgrund ihrer immer größer werdenden Komplexität mit immer mehr Zwischenschichten aufgebaut sind, welche Reibungsverluste bedeuten.
Früher hat man Programme für Mikrocontroller in Assembler geschrieben. Heute schreibt man meist die Programme in C. Es ist bequemer, aber man hat (geringe) Geschwindigkeitsverluste, weil man nicht mehr so nah an der Hardware programmiert.
Selbiges gilt für alle Engines, Frameworks usw. Wenn man komplexe Software entwickeln will muss man aber auf vorhandenen Code zurück greifen und kann nicht alles immer individuell und somit effizient entwickeln.
-> Leistungsstärkere (parallel arbeitende) Hardware, die neue Sprachen braucht um effizeint genutzt zu werden... und darum gehts ja hier :)

[antisteo]

Früher hat man Programme für Mikrocontroller in Assembler geschrieben. Heute schreibt man meist die Programme in C. Es ist bequemer, aber man hat (geringe) Geschwindigkeitsverluste, weil man nicht mehr so nah an der Hardware programmiert.

Also ich sehe in C eher einen Vorteil, da man dem Compiler noch die Möglichkeit gibt, den Code zu optimieren. Ich kenne nicht den kompletten x86_64-Befehlssatz und auch nicht, welche Anweisungen gegenüber welchen schneller sind. Ich würde im Gegenteil alles mit Calling Convention machen. Ein C-Compiler würde da schon inlinen.

Selbiges gilt für alle Engines, Frameworks usw. Wenn man komplexe Software entwickeln will muss man aber auf vorhandenen Code zurück greifen und kann nicht alles immer individuell und somit effizient entwickeln.
-> Leistungsstärkere (parallel arbeitende) Hardware, die neue Sprachen braucht um effizeint genutzt zu werden... und darum gehts ja hier :)

Korrekt. Die Sprache sollte einem helfen, parallele Hardware mit weniger Kopfaufwand auszureizen. Anstatt Code von Hand zu optimieren, würde ich immer den Optimierer des Compilers weiterentwickeln oder es sein lassen.

[Chromanoid]

Schon mal Erlang ausprobiert?

[kimmi]

Welche Aspekte decken denn die bestehenden Sprachen nicht ab? Also als beispiel Erlang oder Scala oder Clojure oder Haskell?

Gruß Kimmi

[antisteo]

Die Parallelen haben zu viel Overhead und die optimierten haben keine guten parallelen Primitiven.

Momentan steck ich bei Go, was sehr vielversprechend aufgebaut ist.