Java: Paralelización de ordenación rápida a través de subprocesos múltiples
Estoy experimentando con algoritmos de paralelización en Java. Comencé con un tipo de fusión y publiqué mi intento en estepregunta. Mi intento revisado está en el código a continuación, donde ahora trato de paralelizar la ordenación rápida.
¿Hay algún error de novato en mi implementación o enfoque de subprocesos múltiples para este problema? Si no es así, ¿no debería esperar un aumento de velocidad de más del 32% entre un algoritmo secuencial y uno paralelo en un núcleo de duelo (ver los tiempos al final)?
Aquí está el algoritmo multihilo:
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);
}
}
}
Así es como empiezo:
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();
}
Probé esto contra Arrays.sort y un algoritmo de ordenación rápida secuencial similar. Estos son los resultados de tiempo en una computadora portátil Intel Duel-Core Dell, en segundos:
Elementos: 500,000, secuencial: 0.068592, roscado: 0.046871, matrices.sort: 0.079677
Elementos: 1,000,000, secuencial: 0.14416, roscado: 0.095492, Arreglos.Orden: 0.167155
Elementos: 2,000,000, secuencial: 0.301666, roscado: 0.205719, Arreglos.Orden: 0.350982
Elementos: 4,000,000, secuencial: 0.623291, roscado: 0.424119, Arreglos.Orden: 0.712698
Elementos: 8,000,000, secuencial: 1.279374, roscado: 0.859363, Arreglos.Orden: 1.487671
Cada número anterior es el tiempo promedio de 100 pruebas, arrojando los 3 casos más bajos y los 3 más altos. Usé Random.nextInt (Integer.MAX_VALUE) para generar una matriz para cada prueba, que se inicializó una vez cada 10 pruebas con la misma semilla. Cada prueba consistió en cronometrar el algoritmo dado con System.nanoTime. Redondeé a seis decimales después de promediar. Y obviamente, verifiqué si cada tipotrabajó.
Como puede ver, hay un aumento de aproximadamente el 32% en la velocidad entre los casos secuenciales y roscados en cada conjunto de pruebas. Como pregunté anteriormente, ¿no debería esperar más que eso?