Parallelisierung von Earth Mover's Distance

This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

  • Parallelisierung von Earth Mover's Distance

    Hallo,

    wir sollen für eine aufgabe in softwaretechnik I die methode unten parallelisieren, so dass die schneller ausgeführt wird. Dazu haben wir einen Testfall bekommen, der einmal sequentiell das berechnen soll und danach mit mehrern threads.
    Bis jetzt habe ich die Differenzen parallelisiert indem jeder thread in der run() methode

    temp = f1 - f2[i] ;

    ausrechnet in einem bestimmten bereich und in ein temporäres array zwischenspeichert. Wenn alle fäden fertig sind wird sequentiell

    Source Code

    1. for (int i = 0; i < f1.length; i++) {
    2. diff += temp[i];
    3. sum += Math.abs(diff);
    4. }


    Das Problem dabei es wird dadurch langsamer.

    Kann mir jemand vielleicht einen anderen Ansatz liefern mit dem dieses Problem schneller zu lösen ist?




    Source Code

    1. /**
    2. * Ermittelt die Earth Mover's Distance zwischen zwei gleich großen
    3. * Gleitkommazahlenfeldern (im Kontext: Graustufenhistogramme).
    4. *
    5. * Der Algorithmus ermittelt die Summe der "Mengen", die von Index zu Index
    6. * "bewegt" werden müssen, um die beiden Felder deckungsgleich zu bekommen.
    7. *
    8. * @param f1
    9. * Das eine Gleitkommazahlenfeld
    10. * @param f2
    11. * Das andere Gleitkommazahlenfeld
    12. * @return Gleitkommawert, der die Distanz der beiden Gleitkommazahlenfelder
    13. * angibt.
    14. */
    15. float calcEarthMovingDistance(float[] f1, float[] f2) {
    16. if (f1.length != f2.length) {
    17. throw new IllegalArgumentException(
    18. "Die Histogramme sind nicht gleich breit!");
    19. }
    20. final float worstCaseDiff = f1.length - 1;
    21. float sum = 0;
    22. float diff = 0;
    23. for (int i = 0; i < f1.length; i++) {
    24. diff = (f1[i] + diff) - f2[i];
    25. sum += Math.abs(diff);
    26. }
    27. sum /= worstCaseDiff;
    28. return Math.abs(1 - sum);
    29. }
    Display All
  • genau, calcEarthMovingDistance ist die sequentielle Methode.
    Wir geben den Threads Bereiche die dieses f1 - f2[i] berechnen. Allerdings müssen wir danach ja nochmal komplett drüberlaufen um die Differenz dazu zu addieren, da diese ja immer vom Vorgänger abhängt. Oder gibt es da eine geschicktere Methode?
  • Systeme die von vorherigen Werten abhängigen sind können nicht parallelisiert werden. Es gilt die Funktion zu Analysieren und die Frage in wie fern ist deine Differenzbildung nun wirklich abhängig vom vorherigen Wert zu klären.
    Hab die Funktion jetzt nicht genau angeschaut, vielleicht kannst du ja auch mit geschicktem rechnen diese Summenbildung der Differenzen auch teilweise im Thread machen.

    Mfg Rushh0ur