Indivisible

«Si una casa está dividida contra sí misma, esa casa no podrá subsistir.»
✝ Santo Evangelio según san Marcos 3,25



Paralelización - 2021-05-19

En la versión legacy de Indivisible, usé el sistema de paralelización OpenMP[1], que permite fácilmente paralelizar los bucles, particularmente los bucles for. Y aunque esto sí que realmente ayudaba a optimizar el programa, la implementación tenía una limitación que causaba un retraso considerable en el código: que se paralelizaba la comprobación de si un número candidato es primo o no.[2]

El problema que tiene esta estrategia de paralelización es que, para cada candidato que se quiere verificar, el programa tendrá que crear y destruir los hilos usados para esto. La implicación es que esto creará un coste en el rendimiento para cada candidato que se quiere verificar.

Ahora, tratando de la nueva versión que se está escribiendo en Rust, esta estrategia funcionaría bien si tan sólo quiere comprobar si un número es primo (i.e. la funcionalidad --test), mas si quiere generar primos, más óptimo sería que cada hilo comprobase un candidato distinto. De este modo, se crearían todos los hilos necesarios al empezar el programa, y no se destruirán hasta generar los primos solicitados. Para esto, ya no se puede usar OpenMP, ya que, más allá de no poder usarlo con bucles while - a esto se le podría buscar alguna solución, aunque no fuere bonita - OpenMP no toma los valores del bucle for necesariamente en orden.[3] Esto no es un problema cuando se paraleliza la comprobación del candidato, ya que sólo hace falta que el candidato sea divisible por un primo para rechazarlo, independientemente del orden. Mas cuando queremos que cada hilo compruebe un candidato diferente, es importante que siga algún orden, ya que al menos al principio de la ejecución dependerán mucho unos de otros.

Por este motivo, no implementaré OpenMP en la versión de Rust de Indivisible. En su lugar pienso usar, al menos para empezar, el sistema de hilos que provee ya Rust, usando hilos del sistema. Quizá luego lo implemento usando Open MPI,[4] para que pueda mejor aprovechar de la paralelización en sistemas multi-procesador. Mas hacer que cada hilo compruebe un candidato distinto también presenta sus dificultades, en particular respecto a las condiciones de carrera. Dado que estamos tratando de la generación de primos, tenemos varios posibles condiciones de carrera:

  1. Selección del candidato para que lo compruebe un hilo.
  2. Inserción de un candidato verificado a la lista de primos.
  3. Comprobación usando una lista incompleta (i.e. se dice que un número es primo tan sólo porque su divisor primo aún no ha sido añadido a la lista de primos).

Las condiciones de carrera 1 y 2 se pueden solucionar simplemente con tener un hilo maestro encargado de asignar candidatos a los hilos esclavos, y luego que los esclavos manden el resultado de su verificación al maestro para que lo inserte en la lista de primos. En particular, para el caso 2, el hilo maestro puede asegurarse de que la lista de primos esté ordenada independientemente de el orden en que los hilos esclavos devuelvan los resultados. El caso más complicado sería el tercero, ya que un hilo esclavo podría (erróneamente) decir que un número compuesto es primo a falta de que su divisor primo aún no se ha añadido a la lista de primos; otro hilo esclavo aún lo está verificando. Este tipo de casos se presentaría sobre todo al principio de la generación de primos, cuando aún falta generar todos los primos menores o iguales que la raíz cuadrada de todos los candidatos. E.g. una situación donde la lista de primos contiene tan sólo el número 2, 3, y 7, a falta de 5; a la vez que aún está trabajando el hilo esclavo para comprobar el 5, también hay otro hilo esclavo sobre 25, y determina que es primo ya que no es divisible por 2 ó 3 (7 no es necesario ya que es mayor que su raíz cuadrada). Para evitar este suceso, podemos implementar una de dos soluciones: espera en el hilo esclavo o espera en asignación del candidato.

Para ambas soluciones, quizá lo primero que se nos ocurre es fijarnos en la lista de primos, y cuando el último elemento sea mayor que la raíz cuadrada del candidato el hilo esclavo puede empezar su verificación. El problema con este método es que, como vimos en el ejemplo más arriba, es posible que se compruebe otro primo mayor al divisor primo que buscamos, y por lo tanto terminaremos con una condición de carrera. La solución está en fijarnos no en la lista de primos que ya averiguamos, sino en la lista de candidatos siendo comprobados: si existe un número dentro de los candidatos que estamos comprobando que sea menor o igual a la raíz cuadrada del número candidato del hilo esclavo en cuestión, o del candidato que se quiere asignar a un hilo esclavo, entonces se ha de esperar hasta que ese hilo dé su resultado.

Ahora, entre los dos modelos propuestos para la espera, que los abreviaremos modelo maestro y modelo esclavo, ambos pueden funcionar correctamente usando la técnica expresada anteriormente. Aquí vemos que el modelo esclavo permite quitar una carga del hilo maestro, ya que el maestro tan sólo tendría que asignar candidatos y añadir candidatos a la lista; mas el modelo maestro simplifica más el código, tal que el hilo esclavo puede empezar sus comprobaciones en cuanto reciba su candidato.

Por ahora tiro más hacia el modelo maestro. Aunque como muchas cosas con Rust, seguramente terminaré haciendo lo que Rust me facilite más.

  1. OpenMP Website
  2. Indivisible-Legacy/src/main.c:240
  3. OpenMP Specification (version 5.0): 2.9.5 loop Construct
  4. Open MPI Website

Última actualización: