Eu estou escrevendo um aplicativo multi-threaded em Java para melhorar o desempenho sobre a versão sequencial. É uma versão paralela da solução de programação dinâmica para o problema da mochila 0/1. Eu tenho um processador Intel Core 2 Duo com o Ubuntu e o Windows 7 Professional em diferentes partições. Eu estou correndo no Ubuntu.

Meu problema é que a versão paralela demora mais que a versão sequencial. Eu estou pensando que isso pode ser porque os segmentos estão sendo mapeados para o mesmo segmento do kernel ou que eles estão sendo alocados para o mesmo núcleo. Existe uma maneira de garantir que cada encadeamento Java seja mapeado para um núcleo separado?

Eu li outros posts sobre este problema, mas nada parece ajudar.

Aqui está o final de main () e todo o run () para a classe KnapsackThread (que estende Thread). Observe que o modo que eu uso slice e extra para calcular myLowBound e myHiBound garante que cada thread não se sobreponha no domínio do dynProgMatrix. Portanto, não haverá condições de corrida.

    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;
        }
    }
}

Atualizar:

Eu escrevi outra versão da mochila que usa força bruta. Esta versão tem muito pouca sincronização porque eu só preciso atualizar uma variável bestSoFar no final da execução de um único thread. Portanto, cada thread praticamente deve executar completamente em paralelo, exceto para aquela pequena seção crítica no final.

Eu corri isso contra a força bruta seqüencial e ainda demora mais. Eu não vejo nenhuma outra explicação além de meus threads serem executados sequencialmente, seja porque eles estão sendo mapeados para o mesmo núcleo ou para o mesmo thread nativo.

Alguém tem algum insight?