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

¡Hola a todos!

¿Qué os parece todo el entramado de funciones que componen BigInteger? Seguro que no creíais que se podía sacar tanto jugo a unas simples operaciones matemáticas...

La verdad, estoy muy contento, porque ahora empieza la parte de la explicación que dará lugar a un cambio, a investigación...

Por otra parte, es posible que en próximas entregas se ralentice un poco el ritmo (la verdad es que estas semanas ha sido frenético el ritmo de las publicaciones), ya que voy a tener que ir investigando y realizando pruebas de los diferentes puntos que vayan surgiendo... todo sea para daros un buen contenido :)

En fin, en esta entrada vamos a entrar de lleno en la identificación de puntos críticos y paralelos de la creación de BigInteger.

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

¡Vamos allá!

La mejor manera para que esta arquitectura sea paralela es a través de la GPU (es decir, el procesador de las tarjetas gráficas), ya que la GPU se caracteriza por trabajar con grandes cantidades de hilos paralelos.

Sobre la GPU, es cierto que cada fabricante tiene su propio modelo de trabajo, y por otra parte, tenemos el modelo Open CL que es multi-plataforma. No obstante, de momento nos vamos a centrar en la arquitectura CUDA (específica de nVidia), y más adelante plantearemos el portarla a Open CL para hacerla accesible a toda la comunidad.

El usar CUDA es básicamente porque tengo el set-up preparado, y domino más los conceptos (ya he trabajado alguna otra vez con CUDA), por lo que ciertos aspectos se simplificarán.

Un aspecto clave a tener en cuenta, es que CUDA trabaja con bloques de 16 hilos, es decir, a la hora de crear un bloque de hilos, CUDA siempre los asignará en bloques de 16 (si por ejemplo, indicamos 6, dejará 10 hilos sin usar, pero asignados al bloque); por tanto, debemos tener la precaución de tener esto siempre en cuenta.

Vamos pues, a analizar la función de creación de BigInteger.

[code lan=gral] /* * Función newBI. * * Genera un nuevo dato BI a partir del string que recibe como entrada. * Se cargan en orden inverso para permitir el crecimiento de manera sencilla. * Si "sig" es -1, se crea el número en negativo */ void newBI(void *dst, char* s, int sig){ struct BigInteger* ret = (struct BigInteger*)malloc(sizeof(struct BigInteger)); int i = strlen(s) - 1; int f = i; int j = 0; int c; //validamos puntero if (ret == NULL) showError(2); //limpiamos el array clean(ret); if (i > MAX_LENGTH) showError(1); //recorremos el string y lo guardamos en integers for (; i >= 0; i--) { c = (int)(s[i] - 48); if (c >= 0 && c <= 9) ret->n[j++] = c; else showError(3); } ret->count = f; if(sig == -1) ret->n[ret->count] *= -1; memcpy(dst, ret, sizeof(struct BigInteger)); free(ret); } [/code]

En esta función, a simple vista, podemos ver dos puntos que podemos optimizar: la llamada a "clean", y el bucle que llena "ret"

Por otra parte, estos dos puntos son también puntos críticos, es decir, se deben ejecutar de manera secuencial. ¿Qué pasaría si movemos "9" a la posición BigInger.n[100], y justo después "clean" nos mueve un "0" en BigInteger.n[100]?

Exacto, perderíamos los datos.

No obstante, sí que hay cosas que se pueden ir haciendo de manera paralela, como muestra el siguiente gráfico:

En definitiva, tenemos que tener en cuenta que los puntos críticos son aquellos en los que dos secciones de código pueden llegar a acceder a la misma posición de BigInteger; por otra parte, una sección de código es paralelizable cuando se acceden secuencialmente a todas las posiciones de BigInteger.n

Tenemos que tener presente que las líneas que se muestran intermitentes, serán en realidad un clúster de hilos, es decir, un grupo de 16n hilos que harán todos la misma operación (es decir, el sistema tendrá especial cuidado en que todo el clúster haya terminado).

¿Qué ganamos con esta paralelización? Bien, si definimos un clúster de hilos tan grande como BigInteger.count, el coste de las operaciones que pasen por el clúster se reduce al coste de una única operación (teóricamente), ya que al realizarse las "BigInteger.count" operaciones paralelamente, todo ocurrirá en el lapso de una sola operación.

Es más, en el mismo lapso de tiempo, se realizarán todas las tareas paralelas hasta llegar al semáforo; obviamente, hay que descontar el tiempo de sincronización, pero en definitiva, se espera ganar tiempo con esta arquitectura.

Aunque de momento no entremos en implementación, si que vamos a anotarnos "mentalmente", que la estructura BigInteger tendrá un nuevo dato llamado "blocks", que nos indicará cuantos bloques de 16 dígitos llena, de cara a poder gestionar los clústeres de hilos.

Y poco más queda por revisar de esta función. Espero que este humilde inicio a la paralelización con GPU os sirva de claro ejemplo podamos ir ahondando juntos en esta nueva etapa de la arquitectura :)

¡Nos vemos!