Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativamente grande se divide recursivamente en problemas más pequeños que son resueltos de la misma manera hasta que se encuentre un tamaño de problema mínimo que se resuelva de forma directa. Un ejemplo típico de problemas que pueden ser resueltos con este enfoque es el algoritmo de ordenación rápida o QuickSort (ver entrada dedica a este algoritmo aquí).

En la nueva versión de JAVA se ha hecho disponible una nueva funcionalidad que permite la ejecución de algoritmos del estilo "divide y vencerás" en múltiples hilos de ejecución que son asignados entre los diferentes procesadores de la máquina. En el siguiente ejemplo se presenta una versión modificada levemente del algoritmo de ordenación rápida para utilizar esta funcionalidad:

import java.util.concurrent.*;

public class Ordenador extends RecursiveAction {
    int[] v;        // El arreglo a ordenar
    int   inicio;   // Posición inicial desde la que se va a ordenar
    int   fin;      // Posición final hasta la que se va a ordenar
    
    Ordenador(int[] x, int i, int f) {
        v      = x;
        inicio = i;
        fin    = f;
    }
    
    // Este es el método que se ejecuta cada vez que se crea un hilo de ejecución recursiva
    public void compute() {         
        if(inicio >= fin ) return ; // Cuando el arreglo tiene un elemento está ordenado y termina el proceso.
        int pivote = inicio;        // Se selecciona como pivote el primer elemnto
        int izq = inicio + 1 ;      // Apuntador izquierdo
        int der = fin ;             // Apuntador derecho
        while(izq < der) {          // Este ciclo se realiza mientras los apuntadores no se hayan cruzado
            while(izq<=fin      && v[izq]< v[pivote]) izq++;    //  Si el elemento izquierdo es menor que el pivote avanza
            while(der>=inicio+1 && v[der]>=v[pivote]) der--;    //  Si el elemento derecho es mayor que el pivote, retrocede
            if(izq < der ) {        //  Si los apuntadores no se han cruzado se intercambian los elementos derecho e izquierdo
                int tmp = v[der];
                v[der] = v[izq]; 
                v[izq] = tmp;
            }   // fin if
        }   // fin while
        // Se intercambian el valor del pivote con el valor del apuntador derecho
        int tmp   = v[der];
        v[der]    = v[pivote];
        v[pivote] = tmp;
        //  Se llaman recursivamente los objetos que van a ordenar los dos subvectores
        invokeAll(new Ordenador(v, inicio, der-1), 
                  new Ordenador(v, der+1, fin));
    }
    
    public void quickSort(int inicio, int fin) {
        if(inicio >= fin ) return ; // Cuando el arreglo tiene un elemento está ordenado
        int pivote = inicio;        // Se selecciona como pivote el primer elemnto
        int izq = inicio + 1 ;
        int der = fin ;
        while(izq < der) {
            while(izq<=fin      && v[izq]< v[pivote]) izq++;
            while(der>=inicio+1 && v[der]>=v[pivote]) der--;
            if(izq < der ) {
                int tmp = v[der];
                v[der] = v[izq]; 
                v[izq] = tmp;
            }
        }
        int tmp   = v[der];
        v[der]    = v[pivote];
        v[pivote] = tmp;
        quickSort(inicio, der-1);
        quickSort(der+1, fin);
    }
}

Para probar el uso de esta clase se crea una clase diferente que contenga el método main, así como la creación del vector y la invocación del proceso. En este programa se prueban los tiempos de ejecución obtenidos para diferentes tamaños de problema con los métodos recursivo tradicional y el nuevo método multiproceso de Java 7:

import java.util.*;
import java.util.concurrent.*;

public class TestFork {
    static Random rnd = new Random();       // Generador de números aleatorios
    // Método para crear un vector de números enteros aleatorios
    public static int[] getVector(int N) {  
        int[] v = new int[N];
        for(int i=0; i<N; i++) v[i]=rnd.nextInt(2*N);
        return v;
    }
    
    public static void main(String[] args) {
        final int MAX_SIZE = 500_000_000;
        int size = 1;                                           // tamaño del vector a crear
        System.out.println("Prueba con método recursivo tradicional");
        while(size < MAX_SIZE) {                                // Mientras el tamaño no es mayor al máximo
            int[] v = getVector(size);      
            Ordenador     ord = new Ordenador(v,0,v.length-1);  // Se crea el objeto Ordenador
            long  t1 = System.currentTimeMillis();              // Tiempo de inicio del proceso
            ord.quickSort(0, v.length-1);                       // Invocación de la ordenación con el método recursivo simple
            long  t2 = System.currentTimeMillis();              // Tiempo final del proceso
            double t = (t2-t1)/1000.0;                          // Tiempo real
            System.out.printf("%,20d %20.4f %n", size, t);      // Tamaño del vector y el tiempo requerido para ordenarlo con el viejo modelo
            size*=2;
        } // fin while
        
        System.out.println("\nPrueba con método recursivo multiproceso");
        System.out.println("Numero de procesadores disponibleS: "+Runtime.getRuntime().availableProcessors());
        size=1;
        while(size < MAX_SIZE) {                                // Mientras el tamaño no es mayor al máximo
            int[] v = getVector(size);      
            Ordenador     ord = new Ordenador(v,0,v.length-1);  // Se crea el objeto Ordenador
            long  t1 = System.currentTimeMillis();              // Tiempo de inicio del proceso
            v = getVector(size);                                // Crea un vector del mismo tamaño
            ForkJoinPool pool = new ForkJoinPool();             // Pool de procesos
            pool.invoke(ord);                                   // Invocación del pool de procesos
            long  t2 = System.currentTimeMillis();              // Tiempo final del proceso
            double t = (t2-t1)/1000.0;                          // Tiempo real
            System.out.printf("%,20d %20.4f %n", size, t);      // Tamaño del vector y el tiempo requerido para ordenarlo con el viejo modelo
            size*=2;
        } // fin while
    }
}