Estoy escribiendo una aplicación de subprocesos múltiples en Java para mejorar el rendimiento en la versión secuencial. Es una versión paralela de la solución de programación dinámica para el problema de mochila 0/1. Tengo un Intel Core 2 Duo con Ubuntu y Windows 7 Professional en diferentes particiones. Estoy corriendo en Ubuntu.

Mi problema es que la versión paralela en realidad toma más tiempo que la versión secuencial. Estoy pensando que esto puede deberse a que todos los subprocesos se asignan al mismo subproceso del núcleo o que se asignan al mismo núcleo. ¿Hay alguna manera de asegurar que cada hilo de Java se asigne a un núcleo separado?

He leído otras publicaciones sobre este problema pero nada parece ayudar.

Aquí está el final de main () y todos de run () para la clase KnapsackThread (que extiende Thread). Tenga en cuenta que la forma en que utilizo slice y extra para calcular myLowBound y myHiBound aseguran que cada hilo no se superponga en el dominio de dynProgMatrix. Por lo tanto no habrá condiciones de carrera.

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

Actualizar:

He escrito otra versión de la mochila que usa fuerza bruta. Esta versión tiene muy poca sincronización porque solo necesito actualizar una variable bestSoFar al final de la ejecución de un solo hilo. Por lo tanto, cada subproceso debería ejecutarse completamente en paralelo, excepto por esa pequeña sección crítica al final.

Corrí esto contra la fuerza bruta secuencial y aún así toma más tiempo. No veo otra explicación que el hecho de que mis subprocesos se ejecutan de forma secuencial, ya sea porque se asignan al mismo núcleo o al mismo subproceso nativo.

¿Alguien tiene alguna idea?