Este reporte fue elaborado para el curso de Programación multinúcleo del Tecnológico de Monterrey, Campus Estado de México.

1. Introducción

Según [Wolfram], el factorial de un número N se define de manera iterativa como:

N! = 1 × 2 × 3 × … × N

En esta práctica se calculó el factorial de un número muy grande en Java utilizando la clase java.math.BigInteger (ver el API de Java en [Oracle]). El objetivo consistía en resolver este problema de manera secuencial y usando threads de Java para obtener una solución paralela.

Nota
Hardware y software utilizado

Los programas se probaron en una computadora de escritorio con un procesador de dos núcleos Intel Pentium D de 3.00GHz y 2.4 GiB de memoria RAM. El sistema operativo utilizado fue Ubuntu 12.04 con un kernel de Linux 3.2.0-58. Los programas se compilaron usando el compilador de Java 1.7.0_04 de Oracle.

2. Solución secuencial

El siguiente listado muestra un programa completo en Java que calcula de forma secuencial el factorial de 100,000:

/*--------------------------------------------------------------------
 * Práctica 0: Factoriales en Java versión secuencial
 * Fecha: 21-Ene-2014
 * Autores:
 *          1166611 Pepper Pots
 *          1160611 Anthony Stark
 *--------------------------------------------------------------------*/

package mx.itesm.cem.pmultinucleo;

import java.math.BigInteger;

public class SequentialFactorial {

    public static void main(String[] args) throws InterruptedException {

        final int n = 100000;

        long timeStart = System.currentTimeMillis();
        BigInteger result = BigInteger.ONE;

        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }

        long timeEnd = System.currentTimeMillis();

        System.out.printf("Resultado = %d, Tiempo = %.4f%n", result.bitCount(),
                (timeEnd - timeStart) / 1000.0);
    }
}

Dado que el factorial de 100,000 es extremadamente grande para imprimirlo (más de cuatrocientos mil dígitos), se utilizó el método bitCount para solo contar el número de bits igual a uno que tiene el valor binario del resultado.

Esta es la salida del programa:

Resultado = 708218, Tiempo = 34.0650

3. Solución paralela

La solución paralela en Java involucra usar dos threads. El primer thread se encarga de calcular la primera mitad de la multiplicaciones: 1 × 2 × 3 × … × 50,000. El segundo thread se encarga de calcular la otra mitad de las multiplicaciones: 50,001 × 50,002 × 50,003 × … × 100,000. Una vez que terminan ambos threads, se multiplican los resultados de ambos para obtener el resultado final. El siguiente listado contiene el programa completo:

/*--------------------------------------------------------------------
 * Práctica 0: Factoriales en Java versión paralela con threads
 * Fecha: 21-Ene-2014
 * Autores:
 *          1166611 Pepper Pots
 *          1160611 Anthony Stark
 *--------------------------------------------------------------------*/

package mx.itesm.cem.pmultinucleo;

import java.math.BigInteger;

public class ParallelFactorial implements Runnable {

    private int start, end;
    private BigInteger result = BigInteger.ONE;

    public ParallelFactorial(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public void run() {
        for (int i = start; i <= end; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
    }

    public static void main(String[] args) throws InterruptedException {
        final int n = 100000;

        long timeStart = System.currentTimeMillis();

        ParallelFactorial p1 = new ParallelFactorial(2, n / 2);
        ParallelFactorial p2 = new ParallelFactorial(n / 2 + 1, n);
        Thread t1 = new Thread(p1);
        Thread t2 = new Thread(p2);
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        BigInteger total = p1.result.multiply(p2.result);

        long timeEnd = System.currentTimeMillis();

        System.out.printf("Resultado = %d, Tiempo = %.4f%n", total.bitCount(),
                        (timeEnd - timeStart) / 1000.0);
    }
}

El programa produce esta salida:

Resultado = 708218, Tiempo = 12.9380

El bit count es el mismo que en la versión secuencial, por lo que podemos suponer que nuestra versión paralela produce el resultado correcto.

4. Resultados

A continuación se muestran los tiempos de ejecución de varias corridas de los dos programas:

Tabla 1. Tiempos de ejecución del factorial secuencial
# de corrida Tiempo T1 (segundos)

Media aritmética

33.8350

1

33.9440

2

34.2370

3

33.4740

4

33.4550

5

34.0650
Tabla 2. Tiempos de ejecución del factorial paralelo
# de corrida Tiempo T2 (segundos)

Media aritmética

12.9868

1

13.1770

2

12.8350

3

12.6560

4

13.3280

5

12.9380

A partir de las medias aritméticas calculadas, el speedup obtenido con un CPU de dos núcleos es:

S2 = T1 / T2 = 33.8350 / 12.9868 = 2.6053

El speedup obtenido es muy bueno, incluso superando al speedup ideal. Sin embargo, no queda claro por qué ocurre esto.

5. Agradecimientos

Se agradece a Steve Rogeres por sugerir usar LibreOffice Calc para calcular los promedios de los tiempos de ejecución.

6. Referencias