Parallelprogrammierung?

[Arp]

Hallo,

Ich kenne mich mit der Theorie hinter der Paralllel-Programmierung nicht wirklich aus (bin ja auch kein Informatiker ), aber ich hab hier ein Programm, welches sich prima auf alle Kerne verteilen lassen würde.

Der Hauptteil des Programmes geht eine Fits Datei (das ist eine Bild Datei) Pixel für Pixel durch, und jedes Pixel wird verarbeitet.

Da die Berechnung der einzelnen Pixel unabhängig von den anderen ausgeführt werden kann, und das ergebniss in einem globalen Array gespeichert (Die Position im Array hängt von der Pixel Koordinate ab, daher kann es da auch keine Kollisionen geben).

Beispiel:

Code: Alles auswählen

import numpy
bildarray = numpy.random((200,200))
resultatarray = numpy.zeros(shape=bildarray.shape)

for x in range(200):
   for y in range(200):
      resultatarray[x][y] = bildarray[x][y]**2
      print x,y

Ich weiss, man könnte einfach so quadrieren, aber das soll ja nur ein Beispiel sein das ich hier pixel für pixel durch gehe. Da man ein einzelnes Pixel quadrieren kann ohne zu wissen wie die anderen sind, dachte ich mir das man das jetzt auch parallel machen könnte.

Meine Idee war nun das ich thread benutze.

Code: Alles auswählen

import numpy,thread
bildarray = numpy.random(shape=(200,200))
resultatarray = numpy.zeros(shape=bildarray.shape)

def calc(x,y):
   global resultatarray
   resultatarray[x][y] = bildarray[x][y]**2
   global threads
   threads-=1
   print x,y


threads = 0
threadlimit = 3   # 3 von 4 kernen sollen benutzt werden

for x in range(200):
   for y in range(200):
      while threads>=threadlimit:
         pass
      threads+=1
      thread.start_new_thread(calc,(x,y))

Der teil mit dem pass, dem +=1 und -=1 soll dafür sorgen das nie mehr als 3 Prozesse parallel laufen sollen. Ich hatte das dann mal getimed, und der zweite teil läuft sogar langsamer als der erste. In der Prozessorübersicht sehe ich das auch mehrere Kerne teilweise ausgelastet sind, statt nur einer.

Aber nun sind die Ausgaben total durcheinander, abundzu stehen sogar die x y Koordinaten in einander, also als würde ein Prozess anfangen die Ausgabe zu schreiben, und noch bevor es fertig ist, ein anderer ebenfalls direkt daneben weiter schreibt.
Und am Ende gibt es dann noch ein paar unhandled thread exceptions.
Wie gesagt, in der Theorie hab ich nicht viel Ahnung davon, aber so ganz naiv gedacht, dachte ich das das so in etwa funktionieren sollte.

Gehts leichter/angenehmer/effizienter? Das Ziel des ganzen ist die beschleunigung des Prozesses. Wenn ich das z.b. auf 2 Kernen parallel laufen lassen kann, würde es schon doppelt so schnell gehen.
Thx.

[BlackJack]

@Arp: Threads starten bekommt man nicht umsonst, das kostet Rechenzeit. Wenn also die Berechnung eines *einzelnen* Pixels nicht deutlich mehr Zeit kostet als das erstellen und beenden eines Threads, dann ist das ganz logisch das es am Ende langsamer ist.

Das `thread`-Modul sollte man nicht verwenden — steht auch in der Dokumentation. Das `threading` Modul ist zum Verwenden gedacht.

CPython hat allerdings das Problem, dass auch bei mehreren Threads nur einer zu jeder Zeit Python-Bytecode ausführen kann. Wirklich parallel werden die also nur ausgeführt, wenn ein Thread C-Code ausführt, der das sogenannte „Global Interpreter Lock” (GIL) freigibt. Das tun viele blockierende Aufrufe wie `time.sleep()` und I/O-Opererationen und auch `numpy` tut das wo es Sinn macht. Wenn Du also nicht wirklich jedes Pixel einzeln behandeln musst, sondern ein ganzes (Teil)Array mit `numpy`-Operationen berechnen kannst, dann wäre da mit Threads in CPython was zu gewinnen.

Uneingeschränkt parallel geht mit Prozessen über das `multiprocessing`-Modul. Da hat man dann allerdings keine gemeinsame Datenstrukturen mehr, es muss also hinter den Kulissen Interprozesskommunikation stattfinden. Was Zeit kostet, die man durch die Parallelität mindestens gewinnen muss, damit das was bringt.

Was bei Deinem Beispiel sehr ineffizient ist, ist die ``while``-Schleife die quasi einen Kern einfach nur mit Warten beschäftigt. Für so etwas gibt es Mechanismen wie Semaphoren im `threading`-Modul oder noch schöner abstrahiert Prozess-Pools im `multiprocessing`-Modul.

Ich würde an Deiner Stelle eine Funktion schreiben die ein Pixel-Array verarbeitet, einen Prozesspool erstellen, und dem Unterarrays von Deinem ursprünglichen Array zur Verarbeitung übergeben. Wie gross Du die Teilaufgaben am besten machst, solltest Du experimentell heraus finden. Ein Pixel pro Aufruf ist sicher zu klein. Das andere Extrem — das Array in die Anzahl der Prozesse aufzuteilen, funktioniert am besten wenn jedes Pixel gleich lang bei der Verarbeitung benötigt.

[Arp]

Hallo,

Hast du da viellleicht einen Link mit, für nicht-informatiker, verständlichen Beispielen?

[BlackJack]

@Arp: Die Dokumentation zum `multiprocessing`-Modul ist umfangreich, mit einem eigenen Abschnitt für Beispiele. Und einen Pool erstellen, ein Array in eine Liste mit n Teilarrays aufspalten, und dann zum Beispiel `map()` auf dem Pool aufrufen ist nicht wirklich „rocket science”.

[Hyperion]

Evtl. schaust Du mal auf die Seiten von Doug Hellman; der hatte iirc auch schon mal das `multiprocessing`-Modul in seiner Reihe "python module of the week"...

[Arp]

Ich hab mit Pool fortschritte gemacht. Es scheint schnell durchzulaufen... bei einem kleinen Test läuft mein code nun in 5 statt in 70 sekunden durch.

Ich hab nur ein kleines Problem. Scheintbar wird was aus dem Pool nicht in eine globale Variable geschrieben?

beispiel:

Code: Alles auswählen

from multiprocessing import Pool

result = 0

def multiplizieren(a,b):
   return a*b

def calc(coords):
   global result
   result = multiplizieren(coords[0],coords[1])

coords =[]

for x in range(20):
   for y in range(20):
      coords.append((x,y))   #lässt sich bestimmt auch einfacher lösen.

p = Pool(10)
p.map(calc,coords)

Nun sollte in X ja eigentlich das letzte Ergebniss stehen, 400, (bzw. 361 weil die 20 ja in range nicht mehr benutzt wird) aber es bleibt bei 0. Gibts da noch irgendwelche Schwierigkeiten beim benutzen von globalen Variablen?

[deets]

Natuerlich kannst du keine globalen variablen benutzen (mal von deren prinzipieller Ablehungswuerdigkeit abgesehen) - denn "calc" wird ja in jeweils einem eigenen Proezess ausgefuehrt. Du hast also nicht eine, sondern viele results, pro prozess.

Stattdessen musst du die Summe ueber die Ergebnisse von map bilden. So werden die Ergebnisse von den Unterprozessen zurueckgegeben.

Code: Alles auswählen

from multiprocessing import Pool


def multiplizieren(a,b):
   return a*b

def calc(coords):
   return multiplizieren(coords[0],coords[1])

coords =[]

for x in range(20):
   for y in range(20):
      coords.append((x,y))

p = Pool(10)
print sum(p.map(calc,coords))

[Arp]

Hmm, Danke.

Das verwirrt mich jetzt eigentlich noch mehr. Ich verstehe es zwar, aber ich krieg das jetzt nicht unbedingt in das eigentlich programm implementiert, denn da werden nicht solche trivialen Berechnungen gemacht.

Vorallem gibt es auch ständig returns von irgendwelchen Listen. Am ende brauch ich eine Liste die einfach nur die zuletzt rausgeschriebene Liste enthält.
Weiterhin wird im normalen Programm anhand einer Pixelkoordinate ein Wert in einem 3D Kubus geändert. Ich seh jetzt grad nicht wie ich mittels map oder sum(map) komplizierteres machen kann....

Es wär so viel einfacher das über eine globale Variable zu machen da Konflikte eben ausgeschlossen sind.

[Hyperion]

Du musst doch wissen, an welcher Stelle Deiner Berechnungen es generell möglich ist, zu parallelisieren!? Wenn Du arg "komplexe" Sachen machst und dann mit globalen Variablen hantierst, sollte Dir auch ohne Parallelisierung Angst und Bange sein

[Arp]

Ich geh ja bei der Berechnung ein Bild pixel für pixel durch. Und jedes Pixel lässt sich unabhängig von einander Bearbeiten. Daher wollte ich mehrere Pixel gleichzeitig abarbeiten. Nur die Berechnungsfunktionen die auf jedes Pixel angewendet werden, schreibt im original an einer bestimmten Stelle es 3D arrays einen Wert hinein. Diese Stelle ist für jedes Pixel einzigartig, deswegen können sich die Threads nicht in die Quere kommmen. Die müssten halt nur auf das gleiche 3D Array zugriff zum schreiben haben müssen.

Um es vielleicht noch genauer zu schreiben:

Für jedes Pixel wird folgendes gemacht:

a, b = funktion1(irgendwelche argumente)
c,d,e = funktion2(irgendwelche argument,a,b)

Kubus1[x,y] = c
Kubus2[x,y] = d
Kubus3[x,y] = e

Und das jetzt mit returns zu versehen und am ende irgendwie aus dem p.map wieder raus zu ziehen verwirrt mich grad arg.

[Hyperion]

Ich geh ja bei der Berechnung ein Bild pixel für pixel durch. Und jedes Pixel lässt sich unabhängig von einander Bearbeiten.

Na dann parallelisiere doch genau *das*. Das Ergebnis sammelst Du eben ein und trägst es danach in die Datenstruktur ein...

[Arp]

S.o. für ein konkreteres Beispiel

Wie genau sammel ich denn die Ergebnisse? Und wie stell ich sicher das die Sortierung noch stimmt? Denn ein Pixel könnte auch je nach Wert schneller abgearbeitet sein als ein anderes.

[BlackJack]

@Arp: Welche Sortierung? Ich denke es ist egal in welcher Reihenfolge die Pixel abgearbeitet werden und die Berechnungen eines Pixels sind unabhängig von denen der anderen. Denn nur dann ist das ja auch tatsächlich parallelisierbar.

[Arp]

Ich meine die Sortierung im resultat.

wenn ich jetzt, um alles zu sammeln z.b. result = p.map(..) machen würde. Dann hab ich ne Menge Einträge in result. Woher weiss ich nun ob result[0] das Ergebnis von pixel (0,0) ist, oder (0,1) weil dieses Pixel als erstes fertig berechnet und als erstes zurück gegeben wurde? Die Reihenfolge des bearbeitens ist in der Tat egal, ich muss nur am Ende wissen welches Resultat zu welchem Pixel gehört.

[Hyperion]

Jetzt bin ich verwirrt! Ein Pixel wird doch durch seine "Lage" im Raum / Ebene bestimmt. Wähle als Ergebnisstruktur eben eine solche, die darauf passt; also etwas eine verschachtelte List, die Du dann via Indexzugriff a la`result[23][56]` ansprechen kannst...

[BlackJack]

@Arp: Wenn Du `Pool.map()` verwendest dann sind die Ergebnisse in der Liste in der Reihenfolge wie die Eingabewerte im Argument. Egal in welcher Reihenfolge die *berechnet* wurden. Die Methode verhält sich da wie die Standardfunktion `map()`. Die einzige map-Variante von `Pool` die sich nicht so verhält ist `imap_unordered()` — und da sagt das der Name ja auch recht deutlich.

[Arp]

@Hyperion

Diese c,d,e variablen aus meinem Beispiel weiter oben sind an sich schon listen (oder numpy 1D arrays, ich weiss grad nicht mehr). Im Finalen Kubus erhält dann jedes Pixel, diese Liste als dritte Dimension hinzu.

@BlackJack

Ah, wunderbar. Das ist eine sehr nützliche Information!

Um es nur klarzustellen, wenn ich folgende funktion habe:
def bla():
return a,b

und wende dann result = Pool.map() mit den koordinaten (0,0),(0,1),(1,0),(1,1) an, steht in result quasi:
a,b,a,b,a,b,a,b für die jeweiligen koordinatentupel.
Right?

Dann kann ich nämlich nachträglich aus der Result immer die richtigen rausnehmen... in dem Fall z.b. kommt jedes Element mit ungeradem index in Liste 1, und jedes mit geradem index in Liste 2. Daraus sollte ich dann vermutlich über numpy.reshape wieder den 3D kubus bauen können.

Ich probiers gleich mal aus. Danke.

[BlackJack]

@Arp: Im Ergebnis steht (a,b),(a,b),(a,b),(a,b) für die jeweiligen Koordinaten in der Eingabeliste.

[Arp]

Wunderbar, ich habs hingekommen. Es tut genau das was es tun soll, und läuft parallel. Der Code läuft jetzt in 1.5 Stunden statt 30 Stunden.... das ist geil

Danke für die Hilfe!

[jens]

schon mal über pypy nachgedacht?