Ich schreibe eine Multithread-Anwendung in Java, um die Leistung gegenüber der sequentiellen Version zu verbessern. Es ist eine parallele Version der dynamischen Programmierlösung für das 0/1-Rucksackproblem. Ich habe einen Intel Core 2 Duo mit Ubuntu und Windows 7 Professional auf verschiedenen Partitionen. Ich laufe in Ubuntu.

Mein Problem ist, dass die parallele Version tatsächlich länger dauert als die sequentielle Version. Ich denke, dies kann daran liegen, dass die Threads alle demselben Kernel-Thread zugeordnet sind oder dass sie demselben Kern zugeordnet sind. Kann ich sicherstellen, dass jeder Java-Thread einem separaten Kern zugeordnet wird?

Ich habe andere Beiträge zu diesem Problem gelesen, aber nichts scheint zu helfen.

Hier ist das Ende von main () und von run () für die KnapsackThread-Klasse (die Thread erweitert). Beachten Sie, dass die Art und Weise, wie ich mit slice und extra myLowBound und myHiBound berechne, sicherstellt, dass sich die einzelnen Threads in der Domäne von dynProgMatrix nicht überschneiden. Daher wird es keine Rennbedingungen geben.

    dynProgMatrix = new int[totalItems+1][capacity+1];
    for (int w = 0; w<= capacity; w++)
        dynProgMatrix[0][w] = 0;
    for(int i=0; i<=totalItems; i++)
        dynProgMatrix[i][0] = 0;
    slice = Math.max(1,
            (int) Math.floor((double)(dynProgMatrix[0].length)/threads.length));
    extra = (dynProgMatrix[0].length) % threads.length;

    barrier = new CyclicBarrier(threads.length);
    for (int i = 0; i <  threads.length; i++){
        threads[i] = new KnapsackThread(Integer.toString(i));
    }
    for (int i = 0; i < threads.length; i++){
        threads[i].start();
    }

    for (int i = 0; i < threads.length; i++){
        try {
            threads[i].join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

public void run(){
    int myRank = Integer.parseInt(this.getName());

    int myLowBound;
    int myHiBound;

    if (myRank < extra){
        myLowBound = myRank * (slice + 1);
        myHiBound = myLowBound + slice;
    }
    else{
        myLowBound = myRank * slice + extra;
        myHiBound = myLowBound + slice - 1;
    }

    if(myHiBound > capacity){
        myHiBound = capacity;
    }

    for(int i = 1; i <= totalItems; i++){
        for (int w = myLowBound; w <= myHiBound; w++){

            if (allItems[i].weight <= w){
               if (allItems[i].profit + dynProgMatrix[i-1][w-allItems[i].weight]
                        > dynProgMatrix[i-1][w])
                {
                    dynProgMatrix[i][w] = allItems[i].profit +
                                      dynProgMatrix[i-1][w- allItems[i].weight];
                }
                else{
                    dynProgMatrix[i][w] = dynProgMatrix[i-1][w];
                }
            }
            else{
                dynProgMatrix[i][w] = dynProgMatrix[i-1][w];
            }
        }
        // now place a barrier to sync up the threads
        try {
            barrier.await(); 
        } catch (InterruptedException ex) { 
            ex.printStackTrace();
            return;
        } catch (BrokenBarrierException ex) { 
            ex.printStackTrace(); 
            return;
        }
    }
}

Aktualisieren:

Ich habe eine andere Version des Rucksacks geschrieben, die brachiale Gewalt anwendet. Diese Version hat sehr wenig Synchronisation, da ich eine bestSoFar-Variable nur am Ende der Ausführung eines einzelnen Threads aktualisieren muss. Daher sollte jeder Thread bis auf den kleinen kritischen Abschnitt am Ende vollständig parallel ausgeführt werden.

Ich habe dies gegen die sequenzielle Brute Force ausgeführt und es dauert immer noch länger. Ich sehe keine andere Erklärung als die, dass meine Threads nacheinander ausgeführt werden, entweder weil sie demselben Kern oder demselben systemeigenen Thread zugeordnet sind.

Hat jemand einen Einblick?