Estou experimentando algoritmos de paralelização em Java. Comecei com a classificação por mesclagem e publiquei minha tentativa nestePergunta, questão. Minha tentativa revisada está no código abaixo, onde agora tento paralelizar a classificação rápida.

Há algum erro de novato na minha implementação ou abordagem multiencadeada para esse problema? Caso contrário, não devo esperar um aumento de velocidade de mais de 32% entre um algoritmo sequencial e um paralelo em um núcleo de duelo (veja os tempos na parte inferior)?

Aqui está o algoritmo multithreading:

    public class ThreadedQuick extends Thread
    {
        final int MAX_THREADS = Runtime.getRuntime().availableProcessors();

        CountDownLatch doneSignal;
        static int num_threads = 1;

        int[] my_array;
        int start, end;

        public ThreadedQuick(CountDownLatch doneSignal, int[] array, int start, int end) {
            this.my_array = array;
            this.start = start;
            this.end = end;
            this.doneSignal = doneSignal;
        }

        public static void reset() {
            num_threads = 1;
        }

        public void run() {
            quicksort(my_array, start, end);
            doneSignal.countDown();
            num_threads--;
        }

        public void quicksort(int[] array, int start, int end) {
            int len = end-start+1;

            if (len <= 1)
                return;

            int pivot_index = medianOfThree(array, start, end);
            int pivotValue = array[pivot_index];

            swap(array, pivot_index, end);

            int storeIndex = start;
            for (int i = start; i < end; i++) {
               if (array[i] <= pivotValue) {
                   swap(array, i, storeIndex);
                   storeIndex++;
               }
            }

            swap(array, storeIndex, end);

            if (num_threads < MAX_THREADS) {
                num_threads++;

                CountDownLatch completionSignal = new CountDownLatch(1);

                new ThreadedQuick(completionSignal, array, start, storeIndex - 1).start();
                quicksort(array, storeIndex + 1, end);

                try {
                    completionSignal.await(1000, TimeUnit.SECONDS);
                } catch(Exception ex) {
                    ex.printStackTrace();
                }
            } else {
                quicksort(array, start, storeIndex - 1);
                quicksort(array, storeIndex + 1, end);
            }
        }
    }

Aqui está como eu começo:

ThreadedQuick.reset();
CountDownLatch completionSignal = new CountDownLatch(1);
new ThreadedQuick(completionSignal, array, 0, array.length-1).start();
try {
    completionSignal.await(1000, TimeUnit.SECONDS);
} catch(Exception ex){
    ex.printStackTrace();
}

Eu testei isso com Arrays.sort e um algoritmo de classificação rápida seqüencial semelhante. Aqui estão os resultados do tempo em um laptop Intel duel-core dell, em segundos:

Elementos: 500.000, seqüencial: 0,068592, encadeado: 0,046871, Arrays.ort .: 0,079677

Elementos: 1.000.000, seqüencial: 0.14416, encadeado: 0.095492, Arrays. Sort: 0.167155

Elementos: 2.000.000, sequencial: 0,301666, encadeado: 0,205719, Arrays. Sort: 0,350982

Elementos: 4.000.000, seqüencial: 0,623291, encadeado: 0,424119, Arrays. Sort: 0,712698

Elementos: 8.000.000, seqüencial: 1.279374, encadeado: 0.859363, Arrays.Sort: 1.487671

Cada número acima é o tempo médio de 100 testes, descartando os 3 casos mais baixos e os 3 mais altos. Usei Random.nextInt (Integer.MAX_VALUE) para gerar uma matriz para cada teste, que foi inicializada uma vez a cada 10 testes com a mesma semente. Cada teste consistiu em cronometrar o algoritmo fornecido com System.nanoTime. Arredondei para seis casas decimais após a média. E, obviamente, eu verifiquei para ver se cada tipotrabalhou.

Como você pode ver, há um aumento de cerca de 32% na velocidade entre os casos sequenciais e encadeados em todos os conjuntos de testes. Como perguntei acima, não devo esperar mais do que isso?