Uso de la GPU en Java: Producto entre dos arreglos (cublasSdot).

Un ejemplo práctico en el uso de las librerías "JCuda" sería calcular el producto entre dos vectores (arrays), ya que es una operación muy común y podría usarse para calcular totales.

Ejemplo de uso (producto entre dos arrays de datos):

- Arrays de datos:
 Precios = {54.1, 21, 8, 39, 12}
 Cantidades = {12, 3, 10, 14, 2}

- Cálculos (suma de los productos entre los elementos correspondientes):
 (54.1 * 12) + (21 * 3) + (8 * 10) + (39 * 14) + (12 * 2) = 1362.2

- Resultado:
 Total a pagar: 1362.2

*Recordar que antes de empezar hay que agregar al proyecto las librerías jCuda.


Código Java (JavaCudaP1.java):

package javacudap1;

import java.util.Arrays;
import jcuda.Pointer;
import jcuda.Sizeof;
import jcuda.jcublas.JCublas2;
import jcuda.jcublas.cublasHandle;
import static jcuda.jcublas.JCublas2.cublasCreate;
import static jcuda.jcublas.JCublas2.cublasDestroy;
import static jcuda.jcublas.JCublas2.cublasSdot;
import static jcuda.jcublas.JCublas2.cublasSetPointerMode;
import static jcuda.jcublas.cublasPointerMode.CUBLAS_POINTER_MODE_DEVICE;
import jcuda.runtime.JCuda;
import static jcuda.runtime.JCuda.cudaFree;
import static jcuda.runtime.JCuda.cudaMalloc;
import static jcuda.runtime.JCuda.cudaMemcpy;
import static jcuda.runtime.cudaMemcpyKind.cudaMemcpyDeviceToHost;
import static jcuda.runtime.cudaMemcpyKind.cudaMemcpyHostToDevice;

public class JavaCudaP1 {

    public static void main(String[] args) {
        
        // Activa excepciones y omite los errores posteriores:
        JCublas2.setExceptionsEnabled(true);
        JCuda.setExceptionsEnabled(true);

        // Tamaños de los arrays.
        int n = 5;

        // Crea y rellena los datos a tratar (precios y cantidades).
        float hostData1[] = {54.1f, 21f, 8f, 39f, 12f}; // precios
        float hostData2[] = {12f, 3f, 10f, 14f, 2f}; // cantidades

        // Declaración punteros de los datos:
        Pointer deviceData1 = new Pointer();
        Pointer deviceData2 = new Pointer();

        // Reservar espacio en memoria en el dispositivo:
        cudaMalloc(deviceData1, n * Sizeof.FLOAT);
        cudaMalloc(deviceData2, n * Sizeof.FLOAT);

        // Copia las entradas (arrays) al DISPOSITIVO (GPU):
        cudaMemcpy(deviceData1, Pointer.to(hostData1), n * Sizeof.FLOAT, cudaMemcpyHostToDevice);
        cudaMemcpy(deviceData2, Pointer.to(hostData2), n * Sizeof.FLOAT, cudaMemcpyHostToDevice);

        // Crea handle (para el manejo) de las CUBLAS: 
        cublasHandle handle = new cublasHandle();
        cublasCreate(handle);

        // Implica ejecutar el producto de la función dentro el DISPOSITIVO (GPU).
        // El resultado será anotado en un puntero que apunta a la memoria del DISPOSITIVO.
        // Ajusta el modo de puntero a DISPOSITIVO.
        cublasSetPointerMode(handle, CUBLAS_POINTER_MODE_DEVICE);

        // Prepara el puntero para el resultado en la memoria del DISPOSITIVO.
        Pointer deviceResultPointer = new Pointer();
        cudaMalloc(deviceResultPointer, Sizeof.FLOAT);

        // Realiza el calculo producto de los arrays (precios * cantidades).
        cublasSdot(handle, n, deviceData1, 1, deviceData2, 1, deviceResultPointer);

        // Copia el resultado realizado en el DISPOSITIVO (Ram GPU) al Host (Ram CPU).
        float deviceResult[] = {-1f};
        cudaMemcpy(Pointer.to(deviceResult), deviceResultPointer, Sizeof.FLOAT, cudaMemcpyDeviceToHost);

        // Muestra el resultado.
        System.out.println("Precios: \t" + Arrays.toString(hostData1));
        System.out.println("Cantidades: \t" + Arrays.toString(hostData2));
        System.out.println("Total a pagar: \t" + deviceResult[0]);

        // Limpia.
        cudaFree(deviceData1);
        cudaFree(deviceData2);
        cublasDestroy(handle);

    }

}


Resultado:

run:
Precios: [54.1, 21.0, 8.0, 39.0, 12.0]
Cantidades: [12.0, 3.0, 10.0, 14.0, 2.0]
Total a pagar: 1362.2
BUILD SUCCESSFUL (total time: 0 seconds)


Nota: Aunque en el ejemplo los arrays son de solo 5 elementos (n = 5), lo normal sería trabajar con arrays compuestos de millones de elementos, ya que las librerías "jCuda" están pensadas para realizar cálculos masivos.

Uso de la GPU en Java: Instalación de librerías CUDA de Nvidia.

Las GPUs deberían verse como procesadores simétricos, donde el hilo de ejecución es el mismo en todos sus núcleos y lo que varia es el conjunto de datos sobre el que se realiza esa ejecución. A diferencia de las CPUs que son procesadores de propósito general con sus propios hilos de ejecución y datos, y con un número limitado de núcleos.
La principal ventaja de ese tipo de arquitectura (GPU) es el procesamiento en paralelo masivo, que intentaremos aprovechar mediante el uso de las librerías "jCuda" que conecta Java con la GPU.

Requisitos: 
- Tarjeta gráfica Nvidia compatible con "Cuda".
- Drivers/librerías Cuda ToolKit (descargable desde la URL oficial de Nvidia).
- Drivers/librerías jCuda (descargable desde la URL "www.jcuda.org").

Lo que tengo instalado:
- Tarjeta gráfica Nvidia Geforce 9400 GT (compatible con instrucciones CUDA).
- Sistema Operativo Windows XP.
- NetBeans 8.x.x


Instalación:

01- Descargar e instalar la versión CUDA Toolkit compatible con nuestro sistema operativo (descargable desde la URL oficial de Nvidia):
    cuda_6.5.14_winxp_general_32.exe

02- Descargar jCuda (descargable desde la URL "www.jcuda.org"):
    JCuda-All-0.6.5-bin-windows-x86.rar

 02.1 Descomprimir fichero:

 02.2 Meter las librerías *.dll a la ruta:
     C:\Archivos de programa\NVIDIA GPU Computing Toolkit\CUDA\v6.5\bin\

 02.3 Agregar las librerías *.jar al proyecto de Netbeans.
    Carpeta "Libraries" y seleccionar [Add JAR/Folder].

03- Descargar y descomprimir documentación de las librerías jCuda (opcional):
    JCuda-All-0.6.5-doc.rar (descargable desde www.jcuda.org).

 03.1 Agregar documentación en Netbeans: 
      Tools - Library Name: JCudaXXXX - Pestaña [Javadoc] - [Add Zip/Folder] - Seleccionar carpetas:
      - JCublas-0.6.5-doc
      - JCuda-0.6.5-doc
      - JCufft-0.6.5-doc
      - JCusparse-0.6.5-doc

A partir de ahora ya tenemos todo listo para trabajar con la GPU Nvidia desde Java.

Problema del viajante de comercio TSP (III.3). Cálculo por fuerza bruta aprovechando las CPUs multi-núcleos.

Con este método se saca más partido a la CPUs multi-núcleo. Consiste en dividir el problema en varias partes y todas estas partes son ejecutadas simultáneamente mediante el uso de Threads (hilos), reduciendo significativamente el tiempo de cálculo.
En este ejemplo se trata de buscar la ruta más corta entre 13 nodos. Para hacerse una idea tiene que elegir una ruta entre 6.227.020.800 posibles.

Requisito: Disponer de una CPU multinúcleo.


Código (TSP_Optimitzar.java):

package tsp_optimitzar;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TSP_Optimitzar {

    @SuppressWarnings("empty-statement")
    public static void main(String[] args) throws InterruptedException {
        String[] nombre_nodos = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"};
        float[] vDistancias = {
            0.0F, 820.8666F, 475.23F, 630.9444F, 175.44064F, 360.75314F, 755.7496F, 186.8207F, 591.06683F, 298.11227F, 681.6526F, 289.17914F, 995.64746F,
            8.357133F, 0.0F, 366.78992F, 83.80908F, 217.9351F, 237.86781F, 581.63153F, 925.394F, 453.48624F, 636.67017F, 200.24031F, 695.21234F, 890.6944F,
            70.59399F, 368.34445F, 0.0F, 764.7878F, 182.2146F, 93.2886F, 194.98314F, 180.56621F, 363.5746F, 443.70917F, 641.6165F, 549.982F, 931.1095F,
            874.7707F, 874.603F, 605.9038F, 0.0F, 25.786762F, 147.78946F, 533.5506F, 47.42154F, 108.01653F, 471.1008F, 261.24738F, 656.25104F, 99.16098F,
            4.8551674F, 361.6684F, 245.69385F, 652.172F, 0.0F, 100.449036F, 633.9419F, 670.09125F, 150.59242F, 907.34863F, 275.1372F, 938.0571F, 38.05818F,
            652.2065F, 238.30981F, 927.4687F, 318.43414F, 429.15936F, 0.0F, 595.4067F, 431.22238F, 388.80447F, 283.0264F, 249.39452F, 8.14694F, 899.722F,
            671.8014F, 811.3296F, 355.1809F, 8.395913F, 157.35182F, 596.0345F, 0.0F, 306.99182F, 192.86949F, 298.59897F, 432.59073F, 633.6216F, 817.70074F,
            301.66046F, 462.99008F, 147.49551F, 730.2186F, 902.4855F, 160.01877F, 485.22964F, 0.0F, 495.07837F, 358.40677F, 555.7709F, 983.111F, 318.58316F,
            160.77138F, 3.104256F, 998.9104F, 310.08047F, 295.39194F, 466.86356F, 673.8137F, 499.67224F, 0.0F, 423.98648F, 855.799F, 779.7313F, 947.50555F,
            372.0423F, 715.80835F, 866.05927F, 57.02963F, 696.6522F, 65.42037F, 388.12494F, 826.8198F, 912.82697F, 0.0F, 304.32504F, 886.0547F, 788.8762F,
            157.58907F, 235.23514F, 575.64496F, 682.70575F, 689.79407F, 57.43567F, 877.0111F, 659.9925F, 658.1151F, 196.0468F, 0.0F, 549.32043F, 440.2496F,
            957.9573F, 699.2848F, 57.796417F, 461.52716F, 881.24054F, 752.86084F, 748.3989F, 42.0304F, 459.0128F, 424.106F, 206.15532F, 0.0F, 386.36868F,
            69.71372F, 877.4519F, 881.0224F, 954.1217F, 924.6164F, 813.5333F, 743.41473F, 956.4676F, 509.52542F, 867.4073F, 202.12968F, 515.76715F, 0.0F};

        List<String> lista_nombre_nodos = new ArrayList<>();
        lista_nombre_nodos.addAll(Arrays.asList(nombre_nodos));
        int nNodos = nombre_nodos.length;
        int nHilos = 4;

        // mostrar tabla distancias
        tDistancias(vDistancias, nNodos);

        System.out.println("\nCalculando...");
        TSP_FuerzaBruta tsp[] = new TSP_FuerzaBruta[nHilos];
        for (int i = 0; i < nHilos; i++) {
            tsp[i] = new TSP_FuerzaBruta(lista_nombre_nodos, vDistancias, nHilos, i + 1);
            tsp[i].start();
        }

        // control de finalización hilos
        int cont;
        do {
            try { // +15%
                Thread.sleep(600);
            } catch (Exception e) {
            }
            cont = 0;
            for (int i = 0; i < nHilos; i++) {
                if (!tsp[i].isAlive()) {
                    cont++;
                }
            }
        } while (cont != nHilos);

        // balance final
        float minimo = Float.MAX_VALUE;
        String ruta = "";
        System.out.println("\nResultados Hilos:");
        for (int i = 0; i < nHilos; i++) {
            System.out.println("Thread " + i + ": " + tsp[i].getDistancia());
            if (tsp[i].getDistancia() < minimo) {
                minimo = tsp[i].getDistancia();
                ruta = tsp[i].getRuta();
            }
        }
        System.out.println("\nResultado más óptimo: ");
        System.out.println("Ruta: " + ruta + "\nDistancia: " + minimo);
    }

    private static void tDistancias(float[] vDistancias, int n) {
        n = (int) Math.sqrt(vDistancias.length);
        float[][] tabla = new float[n][n];
        int cont = 0;
        for (int x = 0;
                x < n;
                x++) {
            for (int y = 0; y < n; y++) {
                tabla[y][x] = vDistancias[cont];
                cont++;
            }
        }
        System.out.println("Tabla distancias:");
        String str;
        for (int i = 0; i < n; i++) {
            str = "| ";
            for (int j = 0; j < n; j++) {
                str += tabla[j][i] + " | ";
            }
            System.out.println(str);
            str = "";
        }
    }

}

Código (TSP_FuerzaBruta.java):

package tsp_optimitzar;

import java.util.List;

public class TSP_FuerzaBruta extends Thread {

    private final int nNodos;

    private final int nHilos;

    private final int part;

    private int[] v_ruta = null;

    private float minimo = Float.MAX_VALUE;

    private float sumatorio = 0;

    private final List<String> lista_nombre_nodos;

    private final float[] v_distancias;

    public TSP_FuerzaBruta(List<String> lista_nombre_nodos, float[] v_distancias, int nHilos, int part) {

        this.lista_nombre_nodos = lista_nombre_nodos;

        this.v_distancias = v_distancias;

        this.nNodos = lista_nombre_nodos.size();

        this.nHilos = nHilos;

        this.part = part;

    }

    @Override

    public void run() {

        double beta;

        double alfa;

        int[] pAlfa = new int[nNodos];

        double nPermutacions = Math.abs(Factorial(nNodos) / nNodos);

        double div = nPermutacions / nHilos;

        alfa = (part - 1) * div;

        beta = alfa + Math.abs(div);

        TSP_Factoradic p1 = new TSP_Factoradic(nNodos, alfa);

        pAlfa = p1.getPermutacion();

        float[][] t_distancias = conversorVT(v_distancias);

        int[] perm = new int[nNodos];

        for (int i = 0; i < nNodos; i++) {

            perm[i] = i;

        }

        System.out.println("Hilo: " + this.getName());

        perm = pAlfa.clone();

        do {

            alfa++;

            sumatorio = 0;

            sumatorio += t_distancias[perm[nNodos - 1]][perm[0]];

            for (int i = 0; i < (nNodos - 1); i++) {

                sumatorio += t_distancias[perm[i]][perm[i + 1]];

                if (sumatorio > minimo) { // +200%

                    break;

                }

            }

            if (sumatorio < minimo) {

                minimo = sumatorio;

                v_ruta = perm.clone();

            }

        } while (nextPermutation(perm) && beta > alfa); // +25%

    }

    private static boolean nextPermutation(int[] array) {

        int i = array.length - 1;

        while (i > 0 && array[i - 1] >= array[i]) {

            i--;

        }

        if (i <= 0) {

            return false;

        }

        int j = array.length - 1;

        while (array[j] <= array[i - 1]) {

            j--;

        }

        int aux = array[i - 1];

        array[i - 1] = array[j];

        array[j] = aux;

        j = array.length - 1;

        while (i < j) {

            aux = array[i];

            array[i] = array[j];

            array[j] = aux;

            i++;

            j--;

        }

        return true;

    }

    public float[][] conversorVT(float[] v_distancias) {

        float[][] t_distancias = new float[nNodos][nNodos];

        int cont = 0;

        for (int i = 0; i < nNodos; i++) {

            for (int j = 0; j < nNodos; j++) {

                t_distancias[j][i] = v_distancias[cont];

                cont++;

            }

        }

        return t_distancias;

    }

    public float getDistancia() {

        return minimo;

    }

    public String getRuta() {

        String ruta = "";

        for (int i = 0; i < nNodos; i++) {

            ruta += lista_nombre_nodos.get(v_ruta[i]) + " - ";

        }

        return ruta;

    }

    private double Factorial(int nNodos) {

        double factorial = 1;

        while (nNodos != 0) {

            factorial = factorial * nNodos;

            nNodos--;

        }

        return factorial;

    }

}

Código (TSP_Factoradic.java):

package tsp_optimitzar;

public class TSP_Factoradic {

    private int[] perm = null;

    int[] factoradic;

    // n = Número elementos

    // k = Indice

    public TSP_Factoradic(int n, double k) {

        this.perm = new int[n];

        // Calcula factoradic de k

        factoradic = new int[n];

        for (int j = 1; j <= n; ++j) {

            factoradic[n - j] = (int) (k % j);

            k /= j;

        }

        // Convierte factorádico a permutación

        double[] temp = new double[n];

        for (int i = 0; i < n; ++i) {

            temp[i] = ++factoradic[i];

        }

        this.perm[n - 1] = 1;

        for (int i = n - 2; i >= 0; --i) {

            this.perm[i] = (int) temp[i];

            for (int j = i + 1; j < n; ++j) {

                if (this.perm[j] >= this.perm[i]) {

                    ++this.perm[j];

                }

            }

        }

        for (int i = 0; i < n; ++i) {

            --this.perm[i];

        }

    }

    public int[] getFactoradico() {

        return factoradic;

    }

    public int[] getPermutacion() {

        return perm;

    }

}

Resultado:

run:

Tabla distancias:

| 0.0 | 820.8666 | 475.23 | 630.9444 | 175.44064 | 360.75314 | 755.7496 | 186.8207 | 591.06683 | 298.11227 | 681.6526 | 289.17914 | 995.64746 | 

| 8.357133 | 0.0 | 366.78992 | 83.80908 | 217.9351 | 237.86781 | 581.63153 | 925.394 | 453.48624 | 636.67017 | 200.24031 | 695.21234 | 890.6944 | 

| 70.59399 | 368.34445 | 0.0 | 764.7878 | 182.2146 | 93.2886 | 194.98314 | 180.56621 | 363.5746 | 443.70917 | 641.6165 | 549.982 | 931.1095 | 

| 874.7707 | 874.603 | 605.9038 | 0.0 | 25.786762 | 147.78946 | 533.5506 | 47.42154 | 108.01653 | 471.1008 | 261.24738 | 656.25104 | 99.16098 | 

| 4.8551674 | 361.6684 | 245.69385 | 652.172 | 0.0 | 100.449036 | 633.9419 | 670.09125 | 150.59242 | 907.34863 | 275.1372 | 938.0571 | 38.05818 | 

| 652.2065 | 238.30981 | 927.4687 | 318.43414 | 429.15936 | 0.0 | 595.4067 | 431.22238 | 388.80447 | 283.0264 | 249.39452 | 8.14694 | 899.722 | 

| 671.8014 | 811.3296 | 355.1809 | 8.395913 | 157.35182 | 596.0345 | 0.0 | 306.99182 | 192.86949 | 298.59897 | 432.59073 | 633.6216 | 817.70074 | 

| 301.66046 | 462.99008 | 147.49551 | 730.2186 | 902.4855 | 160.01877 | 485.22964 | 0.0 | 495.07837 | 358.40677 | 555.7709 | 983.111 | 318.58316 | 

| 160.77138 | 3.104256 | 998.9104 | 310.08047 | 295.39194 | 466.86356 | 673.8137 | 499.67224 | 0.0 | 423.98648 | 855.799 | 779.7313 | 947.50555 | 

| 372.0423 | 715.80835 | 866.05927 | 57.02963 | 696.6522 | 65.42037 | 388.12494 | 826.8198 | 912.82697 | 0.0 | 304.32504 | 886.0547 | 788.8762 | 

| 157.58907 | 235.23514 | 575.64496 | 682.70575 | 689.79407 | 57.43567 | 877.0111 | 659.9925 | 658.1151 | 196.0468 | 0.0 | 549.32043 | 440.2496 | 

| 957.9573 | 699.2848 | 57.796417 | 461.52716 | 881.24054 | 752.86084 | 748.3989 | 42.0304 | 459.0128 | 424.106 | 206.15532 | 0.0 | 386.36868 | 

| 69.71372 | 877.4519 | 881.0224 | 954.1217 | 924.6164 | 813.5333 | 743.41473 | 956.4676 | 509.52542 | 867.4073 | 202.12968 | 515.76715 | 0.0 | 

Calculando...

Hilo: Thread-0

Hilo: Thread-1

Hilo: Thread-3

Hilo: Thread-2

Resultados Hilos:

Thread 0: 1197.6255

Thread 1: 1525.2883

Thread 2: 1566.8871

Thread 3: 1360.7714

Resultado más óptimo: 

Ruta: A - B - I - D - G - C - H - L - F - J - K - M - E - 

Distancia: 1197.6255

BUILD SUCCESSFUL (total time: 12 seconds)

Permutaciones: Conversor sistema decimal a factorádico y a permutación.

El sistema de numeración factorádico proporciona un índice lexicográfico para permutaciones. En este ejemplo se pasa del sistema decimal a factorádico y este a su vez a permutación.


Código (permutar4.java):

package permutar4;

import java.util.Arrays;

public class Permutar4 {

    public static void main(String[] args) {
        int indice = 90;
        int nElementos = 5;
        Permutation p1 = new Permutation(nElementos, indice);
        System.out.println("Elementos:\n" + nElementos);
        System.out.println("Decimal:\n" + indice);
        System.out.println("Factorádico:");
        System.out.println(Arrays.toString(p1.getFactoradico()));
        System.out.println("La 90 permutación de orden 5 es:");
        System.out.println(Arrays.toString(p1.getPermutacion()));
    }

}



Código (Permutation.java):


package permutar4;

public class Permutation {

    private int[] perm = null;

    int[] factoradic;

    public Permutation(int n, int k) {

        this.perm = new int[n];

        // Calcular factorádico de k
        factoradic = new int[n];

        for (int j = 1; j <= n; ++j) {
            factoradic[n - j] = k % j;
            k /= j;
        }

        // Convertir factoradic a permutación
        int[] temp = new int[n];

        for (int i = 0; i < n; ++i) {
            temp[i] = ++factoradic[i];
        }

        this.perm[n - 1] = 1;

        for (int i = n - 2; i >= 0; --i) {
            this.perm[i] = temp[i];
            for (int j = i + 1; j < n; ++j) {
                if (this.perm[j] >= this.perm[i]) {
                    ++this.perm[j];
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            --this.perm[i];
        }

    }

    public int[] getFactoradico() {
        return factoradic;
    }

    public int[] getPermutacion() {
        return perm;
    }

}

Resultado:

run:
Elementos:
5
Decimal:
90
Factorádico:
[4, 4, 1, 1, 1]
La 90 permutación de orden 5 es:
[3, 4, 0, 1, 2]
BUILD SUCCESSFUL (total time: 0 seconds)