java - Algoritmo multi-hilo para resolver sudoku?

multithreading algorithm (13)

¿Necesita beneficiarse de los subprocesos múltiples, o simplemente hacer uso de subprocesos múltiples para que pueda aprender para la tarea?

Si utiliza un algoritmo de fuerza bruta, es bastante fácil dividirlo en varios subprocesos, y si la asignación se centra en codificar subprocesos que pueden ser una solución aceptable.

Tengo una tarea para escribir un solucionador de sudoku de subprocesos múltiples, que encuentra todas las soluciones a un rompecabezas determinado. Anteriormente he escrito un solucionador de sudoku de retroceso de un solo hilo muy rápido, por lo que no necesito ayuda con el aspecto de resolución de sudoku.

Probablemente mi problema esté relacionado con no realmente la concurrencia de grokking, pero no veo cómo este problema se beneficia de los subprocesos múltiples. No entiendo cómo puedes encontrar diferentes soluciones para el mismo problema al mismo tiempo sin mantener varias copias del rompecabezas. Teniendo en cuenta esta suposición (por favor, demuestre que es incorrecto), no veo que la solución de subprocesos múltiples sea más eficiente que un solo subproceso.

Agradecería que alguien me diera algunas sugerencias de inicio para el algoritmo (por favor, sin código ...)

Olvidé mencionar que la cantidad de hilos a usar se especifica como un argumento para el programa, por lo que puedo decir que 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 min(1000, number of solutions) y mostrar una de ellas (si existe)

Algunos puntos generales: no ejecuto procesos en paralelo a menos que 1) es fácil dividir el problema 2) Sé que obtendré un beneficio al hacerlo, por ejemplo, no voy a tener otro cuello de botella. Evito por completo compartir valores mutables entre hilos, o minimizarlos. Algunas personas son lo suficientemente inteligentes como para trabajar de forma segura con mutexes. No soy.

Necesita encontrar puntos en su algoritmo que creen ramas naturales o grandes unidades de trabajo. Una vez que haya identificado una unidad para trabajar, colóquela en una cola para que se retire un hilo. Como ejemplo trivial. 10 bases de datos para actualizar. Inicie la actualización asíncrona en los 10 servidores. Espera a que todo se complete. Puedo evitar fácilmente compartir el estado entre subprocesos / procesos y puedo agregar fácilmente los resultados.

Lo que viene a la mente para el sudoku es que una solución suduko eficiente debe combinar 2-3 estrategias (o más) que nunca pasen de cierta profundidad. Cuando hago Sudoku, es evidente que, en un momento dado, diferentes algoritmos proporcionan la solución con el menor trabajo. Simplemente puede disparar un puñado de estrategias, dejar que investiguen a una profundidad limitada, esperar el informe. Enjuague, repita. Esto evita "forzar" la solución. Cada algoritmo tiene su propio espacio de datos, pero usted combina las respuestas.

Sciam.com tenía un artículo sobre este año o dos atrás, pero parece que no es público.

Aquí está mi propio centavo. Espero eso ayude.

Recuerde que las comunicaciones entre procesadores / entre subprocesos son caras. No hagas múltiples hilos a menos que tengas que hacerlo. Si no hay mucho trabajo / cálculo que hacer en otros subprocesos, es mejor que continúe con un único subproceso.

Intente lo más posible para evitar compartir datos entre subprocesos. Úsalos solo cuando sea necesario

Aproveche las extensiones SIMD siempre que sea posible. Con Vector Extensions puede realizar cálculos en múltiples datos en un solo swoop. Te puede ayudar en abundancia.

Aquí hay un solucionador de un solo hilo codicioso de fuerza bruta:

Seleccione la siguiente celda vacía. Si no hay mas celdas vacias, victoria
Valor de celda posible = 1
Compruebe si hay una solución parcial no válida (duplicados en la fila, columna o bloque 3x3).
Si la solución parcial no es válida, aumente el valor de la celda y vuelva al paso 3. De lo contrario, vaya al paso 1.

Si observa el esquema anterior, la combinación de los pasos 2 y 3 son candidatos obvios para el multihilo. Las soluciones más ambiciosas implican la creación de una exploración recursiva que genera tareas que se envían a un grupo de subprocesos.

EDITA para responder a este punto: "No entiendo cómo puedes encontrar diferentes soluciones para el mismo problema al mismo tiempo sin mantener varias copias del rompecabezas".

Usted no puede Ese es todo el punto. Sin embargo, un ejemplo concreto de 9 hilos podría aclarar los beneficios:

Comience con un problema de ejemplo.
Encuentra la primera celda vacía.
Cree 9 hilos, donde cada hilo tenga su propia copia del problema con su propio índice como valor candidato en la celda vacía.
Dentro de cada subproceso, ejecute su algoritmo de subproceso único en esta copia modificada local del subproceso del problema.
Si uno de los hilos encuentra una respuesta, detenga todos los otros hilos.

Como puede imaginar, cada subproceso ahora está ejecutando un espacio de problemas ligeramente más pequeño y cada subproceso tiene el potencial de ejecutarse en su propio núcleo de CPU. Con un solo algoritmo de un solo hilo, no puede obtener los beneficios de una máquina de varios núcleos.

Cuando dices todas las soluciones a un rompecabezas determinado, ¿te refieres a la última y única solución al rompecabezas? ¿O las diferentes formas de llegar a la única solución? Comprendí que, por definición, un rompecabezas sudoku podría tener una sola solución ...

Para el primero, ya sea el enfoque basado en reglas de Pax o la adopción de Tom Leys en el subprocesamiento múltiple de su algoritmo de retroceso existente podría ser el camino a seguir.

Si es lo último, podría implementar algún tipo de algoritmo de bifurcación que inicie un nuevo hilo (con su propia copia del rompecabezas) para cada movimiento posible en cada etapa del rompecabezas.

Dependiendo de cómo haya codificado su único solucionador de hilos, podrá reutilizar la lógica. Puede codificar un solucionador de subprocesos múltiples para comenzar cada hilo usando un conjunto diferente de estrategias para resolver el rompecabezas.

Usando esas estrategias diferentes, su solucionador de múltiples hilos puede encontrar el conjunto total de soluciones en menos tiempo que su único solucionador de hilos (tenga en cuenta que un verdadero rompecabezas de Sudoku solo tiene una solución ... usted no es el único que Tuvo que lidiar con ese horrible juego de dios en clase.

Hace unos años, cuando miraba la resolución de sudoku, parecía que la solución óptima utilizaba una combinación de algoritmos de análisis lógicos y solo recurría a la fuerza bruta cuando era necesario. Esto le permitió al solucionador encontrar la solución muy rápidamente y también clasificar el tablero por dificultad si quería usarlo para generar un nuevo rompecabezas. Si adoptó este enfoque, sin duda podría introducir algo de concurrencia, aunque hacer que los subprocesos realmente trabajen juntos puede ser complicado.

La idea detrás de los subprocesos múltiples es aprovechar las ventajas de tener varias CPU, lo que le permite realizar varios cálculos simultáneamente. Por supuesto, cada hilo necesitará su propia memoria, pero eso no suele ser un problema.

En su mayoría, lo que desea hacer es dividir el posible estado de la solución en varios subespacios que sean lo más independientes posible (para evitar tener que gastar demasiados recursos en la sobrecarga de creación de subprocesos) y, sin embargo, "ajustar" su algoritmo (para beneficiarlo) de tener múltiples hilos).

Los subprocesos múltiples son útiles en cualquier situación en la que un solo subproceso tiene que esperar un recurso y, mientras tanto, puede ejecutar otro subproceso. Esto incluye un subproceso en espera de una solicitud de E / S o acceso a la base de datos mientras otro subproceso continúa con el trabajo de la CPU.

Los subprocesos múltiples también son útiles si los subprocesos individuales se pueden agrupar en diferentes CPU (o núcleos), ya que luego se ejecutan de forma simultánea, aunque generalmente tendrán que compartir datos para que aún haya alguna disputa.

No veo ninguna razón por la que un solucionador de Sudoku con múltiples subprocesos sea más eficiente que uno de un solo subproceso, simplemente porque no hay que esperar por recursos. Todo se hará en la memoria.

Pero recuerdo algunas de las tareas que hice en Uni, y fue igualmente inútil (código de Fortran para ver qué tan profundo fue el túnel cuando excavaste a 30 grados por una milla y luego a 15 grados por otra milla. Sí, soy bastante antiguo :-). El punto es mostrar que puedes hacerlo, no que sea útil.

En el algoritmo.

Escribí un solo solucionador de hilos que básicamente ejecutaba una serie de reglas en cada paso para intentar rellenar 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.

Hubo reglas similares para todas las filas, todas las columnas, todas las mini cuadrículas de 3x3. También hubo reglas que verificaron las intersecciones de fila / columna (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). Hubo reglas más complejas que no detallaré aquí, pero son básicamente de la misma manera que se resuelven manualmente.

Sospecho que tiene reglas similares en su implementación (ya que, aparte de la fuerza bruta, no se me ocurre otra forma de resolverlo y, si ha utilizado la fuerza bruta, no hay esperanza para usted :-).

Lo que sugeriría es asignar cada regla a un hilo y hacer que compartan la cuadrícula. Cada hilo haría su propia regla y solo esa regla.

Actualizar:

Jon, basado en tu edición:

[editar] Olvidé mencionar, el número de subprocesos a utilizar se especifica como un argumento para el programa, por lo que puedo decir que 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 min (1000, número de soluciones) y mostrar una de ellas (si existe)

Parece que tu profesor no quiere que te dividas según las reglas, sino en los puntos de la horquilla (donde podrían aplicarse varias reglas).

Con eso quiero decir, en cualquier punto de la solución, si hay dos o más avances posibles, debe asignar cada posibilidad a un subproceso separado (aún utilizando sus reglas para la eficiencia pero al mismo tiempo verificando cada posibilidad). Esto le daría una mejor concurrencia (asumiendo que los subprocesos pueden ejecutarse en CPU / núcleos separados) ya que no habrá disputa por la placa; Cada hilo tendrá su propia copia.

Además, como está limitando el número de subprocesos, tendrá que trabajar un poco de magia de agrupación de subprocesos para lograrlo.

Lo que sugeriría es tener una cola de trabajo y N hilos. La cola de trabajo está inicialmente vacía cuando el subproceso principal inicia todos los subprocesos 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 hilo de trabajo es su solucionador de un solo hilo con una pequeña modificación: cuando hay X posibilidades de avanzar (X> 1), su trabajador coloca X-1 de esos 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 subproceso del trabajador reducirá la solución sin encontrar ninguna bifurcación y será exactamente como en su situación actual.

Pero con dos posibilidades en la jugada 27 (por ejemplo, 3 o 4 podrían ir a la celda superior izquierda), su hilo creará otra placa con la primera posibilidad (ponga 3 en esa celda) y la colocará en la cola de trabajo. Entonces pondría 4 en su propia copia y continuaría.

Otro hilo recogerá el tablero con 3 en esa celda y continuará. De esa manera, tienes dos hilos que se ejecutan de forma simultánea y que manejan las dos posibilidades.

Cuando un hilo decide que su placa es insoluble, la tira y vuelve a la cola de trabajo para más trabajo.

Cuando cualquier hilo decide que su placa se resuelve, notifica al hilo principal que puede almacenarlo, sobreescribe cualquier solución anterior (la primera solución encontrada) o la tira si ya tiene una solución (la última solución encontrada es) luego, el subproceso de trabajo vuelve a la cola de trabajo para obtener más trabajo. En cualquier caso, el hilo principal debe incrementar un conteo de soluciones encontradas.

Cuando todos los subprocesos están inactivos y la cola de trabajo está vacía, main tendrá o no tendrá una solución. También contará con un conteo de soluciones.

Tenga en cuenta que todas las comunicaciones entre los trabajadores y el subproceso principal deberán ser excluidas (supongo que usted sabe esto en base a la información de su pregunta).

Muy simple en realidad. El concepto básico es que en su solución de backtrack se ramificaría cuando hubiera una opción. Probaste una rama, retrocediste y luego probaste la otra opción.

Ahora, genere un hilo para cada elección y pruebe ambos simultáneamente. Solo genere un nuevo hilo si hay <un cierto número de hilos en el sistema (ese sería su argumento de entrada), de lo contrario, solo use una solución simple (es decir, existente) de un solo hilo. Para mayor eficiencia, obtenga estos subprocesos de trabajo de un grupo de subprocesos.

Esto es, en muchos sentidos, una técnica de dividir y conquistar, estás utilizando las opciones como una oportunidad para dividir el espacio de búsqueda a la mitad y asignar una mitad a cada hilo. Lo más probable es que una mitad sea más difícil que la otra, lo que significa que la vida útil del hilo variará, pero eso es lo que hace que la optimización sea interesante.

La manera fácil de manejar los problemas obvios de sincronización es copiar el estado actual de la placa y pasarlo a cada instancia de su función, por lo que es un argumento de función. Esta copia significará que no tiene que preocuparse por ninguna concurrencia compartida. Si su solución de un solo hilo usó una variable global o miembro para almacenar el estado de la placa, necesitará una copia de este en la pila (fácil) o por hilo (más difícil). Todo lo que debe devolver a su función es un estado del tablero y una serie de movimientos realizados para alcanzarlo.

Cada rutina que invoca varios subprocesos para realizar el trabajo debe invocar n-1 subprocesos cuando hay n trabajos, hacer el enésimo trabajo y luego esperar con un objeto de sincronización hasta que todos los otros subprocesos hayan finalizado. A continuación, evalúa sus resultados: tiene n estados de tablero, devuelva el que tenga el menor número de movimientos.

Sólo una nota al margen. De hecho, implementé un solucionador de sudoku optimizado y estudié multihilo, pero dos cosas me detuvieron.

Primero, la sobrecarga simple de iniciar un hilo tomó 0.5 milisegundos, mientras que toda la resolución tomó entre 1 y 3 milisegundos (usé Java, otros lenguajes o entornos pueden dar resultados diferentes).

En segundo lugar, la mayoría de los problemas no requieren ningún retroceso. Y aquellos que lo hacen, solo lo necesitan al final de la resolución del problema, una vez que se hayan agotado todas las reglas del juego y tengamos que hacer una hipótesis.

Tengo una idea que es muy divertida aquí ... ¡hazlo con el Modelo Actor! Yo diría que usar erlang .. ¿Cómo? Comienzas con la tabla original, y ...

1) al principio, la celda vacía crea 9 niños con un número diferente, luego se suicida
2) cada niño verifica si es inválido, si es así se suicida, de lo contrario
- Si hay una celda vacía, vaya a 1)
- Si está completo, este actor es una solución.

Claramente cada actor sobreviviente es una solución al problema =)

Usted dijo que utilizó el seguimiento de vuelta para resolver el problema. Lo que puede hacer es dividir el espacio de búsqueda en dos y manejar cada espacio en un hilo, luego cada hilo hará lo mismo hasta que llegue al último nodo. Hice una solución a esto que se puede encontrar en www2.cs.uregina.ca/~hmer200a, pero usando un solo hilo, pero el mecanismo de división del espacio de búsqueda está utilizando ramas y enlaces.