Parallelisierung von Algorithmen

Hallo,

ich habe schon das halbe Internet durchforstet auf der Suche nach Möglichkeiten Algorithmen zu parallelisieren.
Jedoch wurden entweder nur Seminare angeboten, fertige Programme, die parallelisieren oder Tutorials, die wenig hilfreich waren, da sie um den heißen Brei herum geschrieben haben, ohne den Konsens zu erwischen.

Kann mir hier vielleicht jemand bei dem Thema weiterhelfen, sagen, wo es gute Tutorials/HowTo´s/etc. gibt?

Ein fertiger Algorithmus, den man nur noch implementieren muss, wäre zwar sehr schön, aber ich denke, dass nicht nur dies, sondern auch ein evtl. umfassende, relativ leicht verständliche (ich bin schwer von Begriff und stecke noch mitten in der Schulzeit) Dokumentation sehr nützlich wäre.

Eine reine Dokumentation, aus welcher man den Algorithmus noch entwerfen muss, wäre auch nützlich, aber für mich begriffsstutzigen Schüler vielleicht zu komplex.

Danke im Voraus!

Viele Grüße
frolic

Moin

Tutorials, die wenig
hilfreich waren, da sie um den heißen Brei herum geschrieben
haben, ohne den Konsens zu erwischen.

naja, es ist ein weites Feld und zu jedem Algo und zu jeder Infrastruktur gibt es einen eigenen Lösungsansatz. Das Umbauen auf parallele Ausführung ist kein 0815-Standart Vorgang. Das ist und bleibt Handarbeit.

Schränk mal die Auswahl der Algo. ein. Geht’s im Mircoparallelisierung à la Intel HT oder geht es eher Richtung Beowolf ? Oder gar Richtung Seti ?

cu

Moin

Tutorials, die wenig
hilfreich waren, da sie um den heißen Brei herum geschrieben
haben, ohne den Konsens zu erwischen.

naja, es ist ein weites Feld und zu jedem Algo und zu jeder
Infrastruktur gibt es einen eigenen Lösungsansatz. Das Umbauen
auf parallele Ausführung ist kein 0815-Standart Vorgang. Das
ist und bleibt Handarbeit.

Das hatte ich mir schon fast gedacht, da es ja auch sonst zu einfach gewesen wäre.

Schränk mal die Auswahl der Algo. ein. Geht’s im
Mircoparallelisierung à la Intel HT oder geht es eher Richtung
Beowolf ? Oder gar Richtung Seti ?

Intel HT, Beowulf.
Es ist zwar nicht die Microparallelisierung, aber es wird ein Projekt zum verteilten Berechnen, in dem der User seinen Algorithmus eingibt.

Ich werde die Algorithmen aber auf eine Problemklasse beschränken…

Danke erstmal für die bisherige Antwort

cu

Moin

Intel HT, Beowulf.

OK, das sind 2 unterschiedliche Konzepte, spezialsier dich erstmal auf eines von beiden.

Man unterteilt die Konzepte generell nach der Zeit die man braucht um an Daten von einem anderen Knoten zu kommen. Da beim P4-HT die Daten schon in der gleichen CPU sind ist die Zeit sehr klein. Bei Beo müssen die Daten schon über ein Netzwerk wandern. Das sind einige Grössenordnungen mehr.

Es ist zwar nicht die Microparallelisierung, aber es wird ein
Projekt zum verteilten Berechnen, in dem der User seinen
Algorithmus eingibt.

Dann müsstest du dem User eigentlich möglichst viele Freiheiten lassen. Der User müsste selbst wissen wie sein Algo am besten mehrere PC gleichzeitig benutzen kann.

Am einfachsten wäre ein SIMD-Ansatz: der User gibt einen Algo vor (der auf einem Datensatz arbeitet) und viele Datensätze die er durchackern möchte. Bei jedem Durchlauf wird nur ein Datensatz gebraucht, d.h. die Datensätze sind völlig unabhängig voneinander. Dann muss man nur noch viele „freie“ CPU’s finden, denen Algo und ein paar Datensätze schicken, nachher einsammeln… das funktioniert wenn die Datensätze und ihre Ergebnisse nicht zu gross sind UND jeder Datensatz viel Zeit braucht.

Das ist aber auch der Ansatz mit den wenigsten Möglichkeiten. Seti, Climateprediction, LHC, destributed.net,… arbeiten damit weils einfach ist und sie ihre Algos so definieren können.

Aber es gibt auch viele Projekt die nicht so arbeiten können (z.B. weil für die Berrechnung eines Datensatz die Ergebnisse von anderen Datensätzen vorliegen müssen, siehe EarthSimulator, Wettersimulation, nukleare Simu. ,…). Da greift man dann zu etwas i.d.A. http://www-unix.mcs.anl.gov/mpi/ . Aus sowas Leistung rauszuholen ist komplexer als es aussieht. Meistens ist der Overhead für die Organisation und Verwaltung der Daten wesentlich höher als der Nutzen. Da ein universelles, für alle User verständliches und durchschaubares System zu zaubern ist nicht drin.

cu

Moin

Intel HT, Beowulf.

OK, das sind 2 unterschiedliche Konzepte, spezialsier dich
erstmal auf eines von beiden.

Man unterteilt die Konzepte generell nach der Zeit die man
braucht um an Daten von einem anderen Knoten zu kommen. Da
beim P4-HT die Daten schon in der gleichen CPU sind ist die
Zeit sehr klein. Bei Beo müssen die Daten schon über ein
Netzwerk wandern. Das sind einige Grössenordnungen mehr.

Wenn du es so schreibst: BeoWulf - Es soll verteiltes Berechnen von Problemen in Netzwerken werden.

Es ist zwar nicht die Microparallelisierung, aber es wird ein
Projekt zum verteilten Berechnen, in dem der User seinen
Algorithmus eingibt.

Dann müsstest du dem User eigentlich möglichst viele
Freiheiten lassen. Der User müsste selbst wissen wie sein Algo
am besten mehrere PC gleichzeitig benutzen kann.

Es soll ja auch kein Programm für DAUs werden. Der User sollte auf jeden Fall dll’s programmieren können, da diese die Grundvoraussetzungen für das Projekt sind.

Bei jedem Durchlauf wird nur ein
Datensatz gebraucht, d.h. die Datensätze sind völlig
unabhängig voneinander. Dann muss man nur noch viele „freie“
CPU’s finden, denen Algo und ein paar Datensätze schicken,
nachher einsammeln…

Und hier liegt eines meiner Hauptprobleme: Wie schaffe ich es, unabhängige Datensätze zu finden?

Dass ich dazu Datensätze brauche, habe ich auch schon mitbekommen. Aber wie kann ich eine bestmöglich Teilung erzielen - dies war, zum Beispiel, eines der eigentlichen Probleme…

Da ein universelles, für alle
User verständliches und durchschaubares System zu zaubern ist
nicht drin.

hmm - generell nicht? schade! Dass es für den Anfangsstatus nicht zu schaffen ist, ist klar, aber zum Beispiel Dual-Prozessor-Systeme müssen sowas doch auch hinkriegen…
-Um den Ansatz gleich zu nutzen: Es soll im Prinzip ein Dual-(besser: Poly-)Prozessorsystem werden.

Danke für deine Hilfe!
Ich würde sonst wirklich kaputt gehen.

cu

Moin

Und hier liegt eines meiner Hauptprobleme: Wie schaffe ich es,
unabhängige Datensätze zu finden?

Das ist Handarbeit und bei jedem Programm unterschiedlich. Wenn’s irgendwie geht: überlass dem User die Einteilung.

Es gibt graphentheoretische Ansätze (minimal/maximal Cut) um das vom PC machen zu lassen. Allerdings brauchen diese Ansätze viel Rechenzeit. Wenn ein User seine Datenblöcke doof aufteilt braucht das ausrechnen des cut mehr Zeit als das Prog selbst.

Sieh dir mal boinc näher an. Die haben das was du machen willst umgesetzt, allerdings haben die Knoten keinen Kontakt untereinander. Den Teil müsstest du nachbauen. (http://boinc.berkeley.edu/)

Wenn du Probleme mit dem „welches Resultat zu welchem Rechner für welchen Schritt“ hast: Tomasulo-Algorithmus. Ist eigentlich für CPU-interens Aufteilen gedacht, lässt sich aber wunderbar auf Netzwerke umbauen. Man muss nur die Piplines als einzelen Recher ansehen.

Da ein universelles, für alle
User verständliches und durchschaubares System zu zaubern ist
nicht drin.

hmm - generell nicht?

leider.

Dass es für den Anfangsstatus
nicht zu schaffen ist, ist klar, aber zum Beispiel
Dual-Prozessor-Systeme müssen sowas doch auch hinkriegen…

Das ist keine Frage der Rechenleistung, das ist eine Frage der unterschiedlichen Ansprüche der USer. Es gibt keine universelle Master-Lösung für alle verteilt-Rechnen-Probleme. Manche brauchen nunmal andere Vorraussetzungen…

-Um den Ansatz gleich zu nutzen: Es soll im Prinzip ein
Dual-(besser: Poly-)Prozessorsystem werden.

Da gehst du wieder in Richtung HT…

Ich würde sonst wirklich kaputt gehen.

Arbeit an einer Uni ?

cu

'n abend
Es ist sehr schön, dass ich jemanden gefunden habe, der mir wirklich hilfreiche und kompetente Tipps geben konnte.
Vielen Dank nochmal.

Ich würde sonst wirklich kaputt gehen.

Arbeit an einer Uni ?

leider nicht: Schulprojekt - wie gesagt, Parallelisierung ist nur ein Teilproblem…

cu

gruß
frolic