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

Muy buenas!

Chicos y chicas, se va acercando el fin del fin de semana... lo que significa que es hora de descansar, y por supuesto de aprender un poco conmigo :D

Vamos a seguir con la identificación de puntos críticos para implementar la arquitectura BigInteger en CUDA. En este caso, nos toca la división.

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

¡Vamos allá!

La función de la división en su implementación CUDA cambiaría ligeramente respecto a su versión standard.

Como hicimos con la multiplicación, os adjunto primero el esquema, y después pasamos a la explicación.

Como se aprecia, es bastante más sencilla que su hermana, la multiplicación.

Para empezar, como siempre, se validan "a" y "b", y se sincroniza mediante un semáforo.

Acto seguido obtenemos el signum, y hacemos las comparaciones "a = b" y "b = 1" (son las validaciones que hacemos para ganar rendimiento en la versión standard.

En caso de ser necesaria la división, como hicimos con la multiplicación por CUDA, precalculamos la tabla BIT de manera paralela, y sincronizamos de nuevo.

Finalmente, se hacen las divisiones. Pero, oh... ¡problema! el algoritmo actual nos hace depender del anterior resultado parcial para procesar el siguiente (ya que restamos "parcial - BIT"), por tanto ¿cómo mejoramos aquí el rendimiento?

Pues, para eso tenemos la tabla BIT al completo :)

De manera paralela, realizamos todas las comparaciones entre el resultado parcial y BIT, y esto nos dará un array de 10 posiciones, con posibles valores 0, 1, y 2; solo nos queda iterar ese array hasta encontrar un valor distinto de "2", y ya tenemos nuestro índice de BIT para ese resultado parcial.

Con esto, cada resultado parcial tendrá el coste de dos restas (calcular el índice, y calcular el resultado parcial correspondiente).

Tras esto, simplemente podemos dar por finalizada la operación.

Y con esto, terminamos la entrada de hoy.

En próximas entradas, pasamos a las operaciones más complejas (potenciación y raíz), y finalmente nos quedarán las funciones auxiliares. ¡Ya queda menos para empezar la programación!

Nos vemos!