Threads Mergesort mit limitierter Threadanzahl

[TimoH.]

Hallo,

ich implementiere zur Zeit einen Mergesort, welcher mit Threads zum Teil paralellisiert werden soll. Dabei achte ich darauf, dass nie mehr als eine bestimmte Anzahl an Threads gespawnt werden.

Hier ist das was ich mir überlegt habe:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class MergesortConcurrentLimited implements Sort{
    
    private static final int nThreads = Runtime.getRuntime().availableProcessors();
    private int threads = 1; //Startet mit 1, da wir einen root thread haben
    private Lock lock = new ReentrantLock();
    
    @Override
    public void sort(int[] array) {
        try {
            int [] tmp = new int[array.length]; //Wir arbeiten mit einem Hilfsarray, das mitgereicht wird
            Mergesorter root = new Mergesorter(array,tmp,0,array.length-1);
            root.join();
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        }
    }
    
    private void mergesort(int[] array, int[] tmp, int lower, int upper) {
        if (lower < upper) {
            int pivot = (lower + upper) / 2;
            try {
                Mergesorter m1 = null;
                Mergesorter m2 = null;
                /* Es wird überprüft, ob wir einen neuen Thread spawnen können.
                 * Nur möglich, wenn kritischer Abschnitt freigegeben ist, bzw. weniger als nThreads laufen.
                 * Ansonsten rufen wir mergesort imperativ auf. (Das ganze für linke bzw. rechte) Teilliste
                 */
                if(threads < nThreads && lock.tryLock()){
                    try{
                        m1 = new Mergesorter(array,tmp,lower,pivot);
                        threads += 1;
                    }finally{
                        lock.unlock();
                    }
                }else{
                    mergesort(array,tmp,lower,pivot);
                }
                if(threads < nThreads && lock.tryLock()){
                    try{
                        m2 = new Mergesorter(array, tmp, pivot + 1, upper);
                        threads += 1;
                    }finally{
                        lock.unlock();
                    }
                }else{
                    mergesort(array, tmp, pivot + 1, upper);
                }
                if(m1 != null){
                    m1.join();
                }
                if(m2 != null){
                    m2.join();
                }
            } catch (Exception ex) {
                ex.printStackTrace();
            }
            merge(array, tmp, lower, pivot, upper);
        }
    }

    private void merge(int[] array,int[] tmp, int lower, int pivot, int upper){
        System.arraycopy(array, lower, tmp, lower, upper - lower + 1);
        int left = lower, right = pivot+1, i = lower;
        while(left <= pivot && right <= upper){
            if(tmp[left] <= tmp[right]){
                array[i] = tmp[left];
                left++;
            }else{
                array[i] = tmp[right];
                right++;
            }
            i++;
        }
        System.arraycopy(tmp, left, array, i, pivot-left+1);
    }
    
    private class Mergesorter implements Runnable{
        private int[] array,helper;
        private int lower,upper;
        private Thread thread;
        public Mergesorter(int[] array, int[] helper, int lower, int upper){
            this.array = array;
            this.helper = helper;
            this.lower = lower;
            this.upper = upper;
            thread = new Thread(this);
            thread.start();
        }
        
        @Override
        public void run() {
            mergesort(array,helper,lower,upper);
        }
        
        public void join() throws InterruptedException{
            thread.join();
            threads -= 1;
        }
    }
}

Ich bemerke, dass ich bei erst ca. 2mio+ Elemente einen Speedup habe. Meine Frage ist nun, kann ich dieses Code eventuell noch optimieren?

mfg Timo

 

[SlaterB]

mir scheint, du nutzt einige Threads gar nicht,
Beispiel 4 Threads,
root ist selber einer, der soll die ganze Zeit nur warten, warum?

der erste von drei eigenen Thread bekommt das ganze Array und startet zwei weitere für die Hälften, und was macht er selber?
fast gar nichts, wartet nur auf deren Ende und führt dann das finale join durch,
nur zwei Threads arbeiten die meiste Zeit am Problem

spontan überlegt müsste es schon etwas bringen, bei jeder Rekursion maximal einen neuen Thread zu starten,
die linke Hälfte der Arbeit abgeben (an X),
aber nicht die rechte auch noch und selber Pause machen, sondern die rechte Hälfte selber erledigen,
bei nächster Rekursionstiefe durchaus evtl. wieder die Hälfe der eigenen Hälfte abgeben (so wie X auch),
aber wiederum insgesamt ein Viertel behalten

so sollten hier mindestens 3 Threads einige Zeit zu tun haben, wenn auch nicht alle gleich lang,
maximal kann damit 50% mehr geschafft werden, falls du bisher die Hälfte der Threads zum Schlafen verdammt hast,
grundsätzlich dürfte das nur wenig bringen wenn du bisher eh nur mikroskopische Speedups festgestellt hast..,

bist du aus anderen Beispielen sicher, dass bei dir Threads überhaupt ordentlich auf CPUs verteilt werden usw.?
deutlicher ist vielleicht zunächst ein Simpel-Programm a la
http://www.java-forum.org/allgemeine-java-themen/132973-game-life-threads.html#post873777
(nicht Game of Life, mein Dummy-Programm dort )

-------

ein weiteres Problem ist die möglicherweise nicht ideale Nutzung der Threads, sobald sie wieder frei sind,
mit etwas Pech je nach aktueller Situation wird für kleinste Blätter ein eigener Thread gestartet,
das dauert vielleicht auch nicht so lange aber ist unnötig,
hast du mal mitgezählt wieviele Threads bei dir insgesamt gestartet werden?

generell müssten Threads nicht mehrfach gestartet und beendet werden,
erstelle einmalig die Anzahl zu verwendender Threads und lasse diese dauerhaft laufen, verschiedene Arbeiten verrichten,
ok, das wäre alles zusammen ein aufwendigerer Umbau, ganz andere Arbeitsweise als Baum per Rekursion

eine relativ einfache Möglichkeit wäre noch, nur auf relativ hoher oder zumindest mittlerer Ebene im Baum überhaupt auf mögliche neue Threads zu prüfen,

das würde ganz kleine Threads vermeiden und auch die in meinen Augen etwas unschönen
Vergleiche, Testen auf Lock, try/catch usw. im so häufigen niedrigen Bereich vermieden werden, gefällt mir auch nicht so richtig,
wobei letztlich nur ein anderer weiterer Test dazukommt, wohl auch nicht schneller..,

wenn upper - lower < als m, welches am Anfang ausgerechnet wurde, z.B. array.length/2^6,
also Rekursionstiefe ~6 von maximal 20 etwa bei 2^20 = 1 Mio. Einträge, Tiefe auch als Parameter durchreichbar,
wenn jedenfalls diese Grenze erreicht, dann nicht threads-Anzahl und Lock prüfen sondern alles selber zu Ende machen,

------------

dein Klassenaufbau ist etwas komisch, die wichtigen Methoden sollten meiner Ansicht nach alle in die Mergesorter-Klasse,
die ruft sie schließlich auf..

auf die wenigen gemeinsamen Daten kann doch auch dort zugegriffen werden

 

[TimoH.]

@SlaterB

ersteinmal danke für die ausführliche Hilfe. Das mit der Grenze für den Baum, also ab welcher Tiefe ich Threads seinlassen sollte hab ich inzwischen auch schon implementiert gehabt, wobei ich einen festen Wert für die Verbleibenden Elemente nutze (1024).

Ich habe es nun auch so angepasst, dass jedeglich die linke Hälfte, wenn möglich, in einem Thread arbeitet. An sich erhalte ich im Durchschnitt ab 4 möglichen Threads gleichzeitig einen Speedup vom Faktor 2 (Und je größer die Anzahl der Zahlen, umso größer wird der Faktor , bei 100mio ist es ca. 3).

Hier nochmal der angepasste Code:

...
    @Override
    public void sort(int[] array) {
        int [] tmp = new int[array.length]; //Wir arbeiten mit einem Hilfsarray, das mitgereicht wird
        mergesort(array,tmp,0,array.length-1);
    }
    
    private void mergesort(int[] array, int[] tmp, int lower, int upper) {
        if (lower < upper) {
            int pivot = (lower + upper) / 2;
            try {
                Mergesorter m1 = null;
                /* Es wird überprüft, ob wir einen neuen Thread spawnen können.
                 * Nur möglich, wenn kritischer Abschnitt freigegeben ist, bzw. weniger als nThreads laufen.
                 * Ansonsten rufen wir mergesort sequentiell auf. (Das ganze nur für die linke Seite).
                 * Der rechte Rekursionsschirtt wird immer sequentiell verarbeitet.
                 */
                if((pivot-lower) > minTreshold && threads < nThreads && lock.tryLock()){
                    try{
                        m1 = new Mergesorter(array,tmp,lower,pivot);
                        threads += 1;
                    }finally{
                        lock.unlock();
                    }
                }else{
                    mergesort(array,tmp,lower,pivot);
                }
                mergesort(array, tmp, pivot + 1, upper);
                if(m1 != null){
                    m1.join();
                }
            } catch (Exception ex) {
                ex.printStackTrace();
            }
            merge(array, tmp, lower, pivot, upper);
        }
    }
...

Zu deiner Frage, wieviele Threads ca. erzeugt werden. Also bei 40mio, waren es um die 3000, wobei natürlich immer nur nThreads gleichzeitig da sind