BigInteger - Identificación de puntos paralelos y críticos: Multiplicación de BigInteger

Buenas a todos y a todas.

Otro fin de semana, otra entrada más en el blog :-)

Se está volviendo a convertir en un hábito, y eso está bien... así se mantiene uno entretenido un ratillo!

Desde ya os anuncio que tengo preparada otra saga de entregas... así que la idea es terminar esta, terminar un tema que tengo a medias (precisamente relacionado con BigInteger), y ponerme con la nueva saga... ¡esto promete!

En fin, hoy toca seguir con los puntos críticos de BigInteger, en concreto, los de la multiplicación.

• ¿No es la entrada que buscabas? Entra en el índice
• ¿Buscas el código fuente? Aquí lo tienes

¡Vamos allá!

Como ya adelantaba en la anterior entrada, vamos a ver bastantes cosas en esta función, ya que es de las más completas.

Antes de entrar en detalle, os vos a dejar cómo funcionaría idealmente la función de multiplicación:

Vale, vamos poco a poco...

Primero hacemos el clásico movimiento de validación, donde usamos dos clústeres para validar "a" y "b" simultáneamente (en este punto ya nos estamos ahorrando el coste de validación de uno de los BigInteger).

Seguidamente abrimos tres clústeres

1. Validamos si "a = 0"
2. Validamos si "b = 0"
3. Normalizamos los datos (y abrimos un clúster nuevo)
1. Validamos si "a = 1"
2. Validamos si "b = 1"

Tras esto, de nuevo sincronizamos a través del semáforo, y validamos los resultados.

Si se ha de hacer la multiplicación, abrimos un nuevo clúster que nos servirá para precalcular BIT. Esto es importante, ya que es un cambio respecto la multiplicación habiutal de BigInteger, donde calculamos BIT bajo demanda.

En este caso, hará falta sincronizar de nuevo para poder entrar a las sumas parciales. La idea es que se abran varios clústeres, teniendo en cuenta el número de operaciones a realizar, de manera que se busque un equilibrio entre clústeres paralelos y operaciones realizadas por los mismos.

Es decir, hablando en números absolutos de hilos (no en clústeres de 16 hilos), no es lo mismo tener 16 hilos y que cada hilo realice 16 operaciones, que tener 64 hilos y que cada hilo haga 4 operaciones.

¿Por qué no?

Buena pregunta... y la respuesta también es buena.

Porque cada hilo va a dejar un BigInteger con el resultado de las sumas parciales que haya realizado, y se tendrá que hacer una suma de todas las sumas parciales (en la imagen, suma total) para obtener el resultado final.

Suena bastante complicado (y es algo complicado), así que os dejo una imagen más con el detalle de esta operación

Supongamos un número "B" con 8 dígitos (a, b, c, d, e, f, g, h). En este ejemplo estaríamos usando cuatro clústeres de hilos, con un hilo por clúster.

El primer clúster contendría los dígitos "a" y "e", el segundo "b" y "f", etc; entonces, cada hilo obtendría su producto parcial a través de un acceso a BIT, y lo sumaría al resultado actual (0). Acto seguido accedería al producto parcial del segundo dígito, y lo sumaría al resultado actual.

Al terminar, tendríamos un BigInteger que representaría la suma de todos los productos parciales tratados por el hilo (en el primer hilo, tendríamos "a' + e'", por ejemplo).

Finalmente, hay que sumar los resultados de todos los hilos para obtener el resultado completo.

¿Y cómo hacemos esto?

Otra pregunta a tener en cuenta. La tecnología GPU funciona muy bien cuando hay dos conjuntos de datos, pero no tan bien cuando solo hay un conjunto de datos.

La solución a este problema pasaría por una suma en forma de árbol binario (es decir, ir sumando por parejas, como se ve en la imagen superior).

Una implementación preliminar podría ser la siguiente

Get Raw

0001let input = [];

0002let maxLen = 4096;

0003let i = 0;

0004 

0005//añadimos datos aleatorios

0006for(;i < maxLen;i++)

0007  input.push(Math.floor(Math.random() * 10));

0008 

0009console.log("Resultado: " + vecSum(input, maxLen));

0010 

0011function vecSum(input, maxLen){

0012  let prev = 0;

0013  let offset = 0;

0014  let base = 2;

0015  let exp = 0;

0016  let i = 0;

0017   

0018  while(offset < maxLen){

0019    prev = offset;

0020

0021    //offet = 2^i

0022    offset = Math.pow(base, ++exp);

0023    

0024    //en el primer cálculo hay que tratar de manera especial

0025    if(prev === 0)

0026      prev = offset - 1;

0027    

0028    //sumamos por parejas (1 + 2, 3 + 4, ...; luego 1 + 3; ...

0029    for(i = 0;i < maxLen;i+=offset)

0030      input[i] = binSum(input[i], input[i], input[(i + prev)]);

0031  }

0032  

0033  //al terminar, la posición [0] tiene el resultado

0034  return input[0];

0035}

0036 

0037function binSum(res, a, b){

0038  res = a + b;

0039  

0040  return res;

0041}