Multi-threading es útil en cualquier situación donde un solo hilo tiene que esperar un recurso y puede ejecutar otro hilo mientras tanto. Esto incluye un hilo esperando una solicitud de E/S o acceso a la base de datos, mientras que otro hilo continúa con el trabajo de la CPU.
multi-threading es también útil si los hilos individuales pueden ser arrendados a las CPU diffent (o núcleos), ya que entonces se ejecutan simultáneamente en verdad, a pesar de que en general, tendrán que compartir los datos por lo que todavía habrá algunos contención.
No puedo ver ningún motivo por el cual un solucionador de sudoku multihilo sea más eficiente que uno de un solo subproceso, simplemente porque no hay recursos a la espera. Todo se hará en la memoria.
Pero recuerdo algunos de los deberes que hice en Uni, y fue igualmente inútil (código de Fortran para ver qué tan profundo era un túnel cuando excavaba a 30 grados por una milla y luego a 15 grados por otra milla - sí, Soy bastante viejo :-). El punto es mostrar que puedes hacerlo, no que sea útil.
En el algoritmo.
Escribí un único solucionador de subprocesos que básicamente ejecutaba una serie de reglas en cada pasada para intentar llenar otro cuadrado. Una regla de muestra era: si la fila 1 solo tiene un cuadrado libre, el número es evidente de todos los otros números en la fila 1.
Había reglas similares para todas las filas, todas las columnas, todas las minirrejillas de 3x3. También había reglas que marcaban intersecciones entre filas y columnas (por ejemplo, si un cuadrado dado solo podía contener 3 o 4 debido a la fila y 4 o 7 debido a la columna, entonces era 4). Había reglas más complejas que no detallaré aquí, pero básicamente son de la misma manera que lo resuelves manualmente.
Sospecho que tienes reglas similares en tu implementación (ya que aparte de la fuerza bruta, no se me ocurre otra manera de resolverlo, y si has usado la fuerza bruta, no hay esperanza para ti :-).
Lo que sugeriría es asignar cada regla a una secuencia y hacer que compartan la grilla. Cada hilo haría su propia regla y solo esa regla.
Actualización:
Jon, basado en tu edición:
[editar] Se me olvidó mencionar, el número de hilos que se utilizarán se especifica como un argumento para el programa, por lo por lo que puedo decir, no está relacionado con el estado del rompecabezas de ninguna manera ...
Además, puede que no haya una solución única: una entrada válida puede ser una placa totalmente vacía.Tengo que informar el mínimo (1000, número de soluciones) y mostrar uno de ellos (si existe)
Parece que su profesor no quiere que se divida según las reglas, sino que en el tenedor puntos (donde se pueden aplicar múltiples reglas).
Con esto quiero decir, en cualquier punto de la solución, si hay dos o más movimientos posibles hacia adelante, debe asignar cada posibilidad a un hilo separado (aún usando sus reglas de eficiencia pero revisando concurrentemente cada posibilidad). Esto le daría una mejor concurrencia (suponiendo que los hilos se puedan ejecutar en CPU/núcleos separados) ya que no habrá contención para la placa; cada hilo obtendrá su propia copia.
Además, como está limitando el número de subprocesos, tendrá que trabajar un poco de magia de grupo de subprocesos para lograr esto.
Lo que sugeriría es tener una cola de trabajo y N hilos. La cola de trabajos está inicialmente vacía cuando el hilo principal inicia todos los hilos de trabajo. Luego, el hilo principal pone el estado inicial del rompecabezas en la cola de trabajo.
Los hilos de trabajo simplemente esperan a que se coloque un estado en la cola de trabajo y uno de ellos lo toma para procesarlo. El subproceso de trabajo es el solucionador de un único subproceso con una pequeña modificación: cuando hay X posibilidades de avanzar (X> 1), el trabajador vuelve a colocar X-1 en la cola de trabajo y luego continúa procesando la otra posibilidad.
Entonces, digamos que solo hay una solución (verdadero Sudoku :-). El primer hilo de trabajo se reducirá en la solución sin encontrar ninguna bifurcación y eso será exactamente como en su situación actual.
Pero con dos posibilidades en el movimiento 27 (digamos que 3 o 4 podrían ir a la celda superior izquierda), el hilo creará otro tablero con la primera posibilidad (poner 3 en esa celda) y colocarlo en la cola de trabajo . Luego pondría 4 en su propia copia y continuaría.
Otro hilo recogerá el tablero con 3 en esa celda y continuará. De esta forma, tiene dos hilos ejecutándose simultáneamente manejando las dos posibilidades.
Cuando un hilo decide que su placa es insoluble, lo tira y vuelve a la cola de trabajo para más trabajo.
Cuando un hilo decide que su placa está resuelta, notifica el hilo principal que puede almacenarlo, sobrescribe cualquier solución anterior (la solución encontrada es la primera) o la descarta si ya tiene una solución (último se encuentra la solución), luego el hilo de trabajo vuelve a la cola de trabajo para más trabajo. En cualquier caso, el hilo principal debería incrementar el número de soluciones encontradas.
Cuando todos los subprocesos están inactivos y la cola de trabajo está vacía, el principal tendrá o no una solución. También tendrá un recuento de soluciones.
Tenga en cuenta que todas las comunicaciones entre los trabajadores y el hilo principal deberán omitirse (supongo que lo sabe según la información de su pregunta).
Ayudaría si describiera su algoritmo de subproceso único un poco más. –
en realidad, es casi exactamente lo que has publicado :) Me parece que funciona bastante bien y es muy fácil de codificar ... – Jon
De acuerdo, consulte mi nota adicional a continuación con una justificación simple para el multihilo. –