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.
¡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
- Validamos si "a = 0"
- Validamos si "b = 0"
- Normalizamos los datos (y abrimos un clúster nuevo)
- Validamos si "a = 1"
- 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
[code lan=gral]
let input = [];
let maxLen = 4096;
let i = 0;
//añadimos datos aleatorios
for(;i < maxLen;i++)
input.push(Math.floor(Math.random() * 10));
console.log("Resultado: " + vecSum(input, maxLen));
function vecSum(input, maxLen){
let prev = 0;
let offset = 0;
let base = 2;
let exp = 0;
let i = 0;
while(offset < maxLen){
prev = offset;
//offet = 2^i
offset = Math.pow(base, ++exp);
//en el primer cálculo hay que tratar de manera especial
if(prev === 0)
prev = offset - 1;
//sumamos por parejas (1 + 2, 3 + 4, ...; luego 1 + 3; ...
for(i = 0;i < maxLen;i+=offset)
input[i] = binSum(input[i], input[i], input[(i + prev)]);
}
//al terminar, la posición [0] tiene el resultado
return input[0];
}
function binSum(res, a, b){
res = a + b;
return res;
}
[/code]
Este código serviría para sumarizar todos los datos parciales, que podrían quedar en un array temporal.
Una vez terminada la suma total, podríamos asignar el resultado final a la operación "a * b", y liberar memoria.
Un último apunte... una vez obtenida la tabla BIT asociada a "a", se puede desasignar la memoria asociada al dato temporal, y así ahorrar unos cuantos bytes de memoria adicional ;-).
Y, nada, amigos... hasta aquí la multiplicación (no ha sido poco, ¿eh?)
En la próxima entrada... ¡la división!
¡Nos vemos!
No hay comentarios:
Publicar un comentario