Algorithmus paralelisieren



  • Hi,

    Wie wuerded ihr foldendes problem paralelisieren?
    http://s14.postimg.org/ccfk06a1t/test.png

    Bitte um feedback. Bis zur max dimension von d=3.

    Lg



  • Du hast mehrere Bloecke der groesse 2^l * 2^l * ... * 2^l.
    Jeder Thread bekommt eine id, rechnet damit den index fuer seinen Block aus und verarbeitet den.



  • nur 1 block pro thread?



  • Ne. Man nimmt eine bestimmte Menge Threads (einer pro Kern bietet sich an) und die teilen sich dann die Last zu gleichen Teilen auf.

    Bei 4 Kernen teilt man das Gesamtbild quasi in 4 Teile auf und jeder Thread behandelt diesen Teil, als waere es das ganze Bild.



  • ja ok, sagen wir ich habe 4 kerne. wie kannst du bestimmen wie viele threads auf welchen kern laueft, das macht doch das os?

    um die optimale number an threads zu finden, muss ich einen benchmark durchfuehren?



  • michael1 schrieb:

    ja ok, sagen wir ich habe 4 kerne. wie kannst du bestimmen wie viele threads auf welchen kern laueft, das macht doch das os?

    Jo, das OS ist doch nicht dumm. Wobei 8=2*Kerne hier auch eine gute Anzahl wäre.



  • um die optimale number an threads zu finden, muss ich einen benchmark durchfuehren?

    wie kommst du auf 8=2*Kerne?

    jedes l-downsampled image kann ja auch in parallel durchgefuehrt werden?



  • Nach meiner Erfahrung bringt 5 Threads auf 4 Kernen am meisten Geschwindigkeit rein, aber letztendlich kaempfen dann die 5 Threads um die 4 Plaetze und verdraengen sich und andere Anwendungen, was zum einen Stromverbrauch und Luefterdrehzahl uebermaessig in die hoehe treibt und andere Anwendungen stoeren kann. Es ist mir z.B. schon passiert, dass ein Video anfaengt zu ruckeln, wenn ich im Hintergrund mit 5 oder 6 Prozessen (sind ja quasi threads mit getrenntem memory) compile.



  • ich hab leider ein problem die indices richtig umzurechnen:
    die block size ist zu start wie folgt gesetzt:
    2 (fuer 1d), 4 (fuer 2d), 8 (fuer 3d)

    void thread_downsampling(const int &num_blocks,
                             const int &block_size) {
        for (int i = 0; i < num_blocks; i++) {
          int start_row = ((i * block_size) / ROW_SIZE))
          int start_col = ((i * block_size) % COL_SIZE);
          int start_depth = ((i * block_size) % DEPTH_SIZE);
    
          block_downsampler(...);
       }
    }
    

    wie bekomme ich fuer den block_downsampler die richtige row,col,depth index?



  • im moment mache ich folgendes:
    wenn ich N blöcke habe und sie auf T threads verteilst, bekommt jeder thread eben N/T Blöcke

    das problem hier ist, das die bloecke unterschiedlich gross sind
    Bekommt man das mit statischer parallelität so hin, dass all threads halbwegs gleich lang brauchen?



  • habe mir folgendes ueberlegt.

    ich pushe alle bloecke in eine globale queue und jeder thread nimmt ein block, prozessiert es und nimmt das naechste. die threads rennen solange bloecke in der queue sind.
    ich moechte eine boost_lock_free_queue verwenden. macht der ansatz sinn?

    welche vor/nachteile gibt es von boost_lock_free_queue? (http://www.boost.org/doc/libs/1_57_0/doc/html/lockfree.html)



  • Vorteil: Die Arbeit wird so aufgeteilt, dass kein Thread bedeutend fueher fertig wird als die anderen.

    Nachteil: Da mindestens atomics verwendet werden, ist das holen neuer Aufgaben etwas langsamer. Ausserdem skalieren die Algorithmen nicht optimal, also doppelt so viele Prozessoren bedeutet nicht doppelt so schnell, sondern etwas weniger.
    Ausserdem ist die lockfree-queue schwer zu verwenden, weil sie im Grunde nur primitive typen zulaesst.



  • vorteil/nachteil bezogen auf was?

    oder waere eine statische queue pro thread besser, weil die bloecke dann im speichern hintereinander legen? und falls ein thread fertig wird, kann er sowas wie work stealing implementieren? http://supertech.csail.mit.edu/papers/steal.pdf bitte um feedback.



  • Ich sehe zwei sinnvolle Varianten.

    A: Verteil es fix, jeder Thread bekommt nen ca. gleich grossen Teil.

    B: Nimm einen fertigen gut optimierten Scheduler - Work-Stealing oder nicht spielt hier eher keine Rolle (SO klein sind die Chunks nicht die du machen wirst). Und schieb da z.B. 10*N Chunks rein.



  • @hustbaer: das problem ist das die blocksize nicht konstant ist.
    ja oefter ich downsample desto groesser wird der block den ich zu processieren habe (factor *2) ... wie kann dann jeder thread einen gleich grossen teil bekommen?



  • er.
    und?
    1x downsamplen ist 1x parallelisieren.
    dabei ist die grösse konstant.

    ansonsten musst du halt gucken dass du nicht gleiche block-anzahl vergibst sondern ca. gleiche pixel-anzahl.



  • welche moeglichkeiten gibt es den mode eines arrays zu berechnen? kann ich da nicht ne art merge sort verwenden und dann die werte fuers downsample+1 verwenden?


Log in to reply