Programa Java multiproceso para el juego de la vida de Conway: contención en las celdas fronterizas

Question

Estoy aprendiendo programación simultánea en Java y estoy escribiendo una simulación para Game of Life.

Aquí es lo que estoy pensando:

• Uso int [] [] para almacenar los estados de las células
• partición del int [] [] en segmentos T y el uso de subprocesos de trabajo t
• Los subprocesos t leerán de su segmento, calcularán nuevos valores para todas las celdas de su segmento y actualizarán las celdas.
• Una vez que terminaron el cálculo esperan en una barrera para que otros trabajadores terminen
• cuando se cruza la barrera, el hilo principal actualizará la IU.
• los trabajadores proceden a calcular el siguiente estado.

Ahora habrá contención en los bordes comunes de los segmentos. Si un hilo sobrescribió el estado de una celda de borde antes de que su vecino haya leído el valor anterior, el cálculo del vecino será incorrecto.

¿Cuáles son mis opciones?

• Uso exigible en lugar de ejecutable y haga que los subprocesos de trabajo devuelven el nuevo valor (en lugar de actualizar los mismos segmentos). El hilo principal puede actualizar la matriz después de cruzar la barrera. Esta opción implica copiar los resultados devueltos por subprocesos de trabajo en la matriz.
• Utilice dos barreras. El hilo de los trabajadores hace una copia de las celdas de los bordes de los segmentos de sus vecinos y espera en la primera barrera. Una vez que se pasa esta barrera, proceden a calcular los próximos estados y actualizar los segmentos en su lugar. Luego esperan en la 2da barrera. el hilo principal actualiza la interfaz de usuario.

Mi pregunta es, ¿hay alguna otra manera de hacer frente a la contención en las células del borde que no implica copiar datos o es más eficiente que las dos opciones anteriores? ¿Puede estar utilizando ReaderWriterLock, variable volátil u otro mecanismo de sincronización?

ACTUALIZACIÓN: Hasta ahora, el double buffering solution by Peter es el más limpio. Pero tengo una pregunta. Como las dos matrices son datos compartidos y no estamos utilizando ninguna sincronización (acceso sincronizado o variable volátil), ¿no creará el problema de visibilidad? ¿Podrían varias CPU almacenar en caché los valores de la matriz y actualizar solo una parte de la matriz con cada iteración? Entonces los hilos obtendrán valores obsoletos para las celdas de borde. es posible? Si no, por qué. Si es así, ¿cómo lo resuelvo? Parece declaring two arrays volatile will not make their individual elements volatile.

Answer 1

No responde su pregunta real, pero mi recomendación sería su primera opción ... que se devuelvan los nuevos valores en lugar de que los hilos de trabajo los actualicen. Daría un paso más y haré que el "agregador" combine los resultados de los subprocesos de trabajo en un nuevo conjunto de estado de tablero y luego descarte el primero. Mi razonamiento es que mejorará la legibilidad general de la lógica, ya que habrá pocas o ninguna "interacción global" de la que tenga que preocuparse.

Dicho esto, soy un poco parcial porque prefiero programar de una manera funcional, excepto cuando hay una fuerte razón para no hacerlo.

Answer 2

me gustaría probar el siguiente enfoque:

• Hacer que los trabajadores realizan los cálculos, pero sólo escribir de nuevo los valores de las celdas interiores.
• Para celdas de borde, almacene los resultados.
• Cuando los cálculos estén completos, espere en una barrera.
• Cuando todos los trabajadores están en la primera barrera, suelte y deje que cada uno escriba las celdas de los bordes.
• Esperar a una segunda barrera, mientras que los cambios de interfaz de usuario

almacenamiento requerido para una baldosa n x m es 2 * (n + m - 1), por lo general azulejos más grandes (8x8 o más) requieren proporcionalmente menos memoria para los valores almacenados en caché.

Answer 3

Sugiero tener 2 int [] [] matrices. Vamos a llamarlos A y B. A mantendrá los valores de todos los "tics" numerados impares y B mantendrá los tics pares.

Inicialice A para cualquiera que sea su estado inicial. Luego, suelte los hilos para calcular el siguiente estado de cada celda y coloque los resultados en la celda correspondiente en B. Una vez que haya terminado todos los hilos, tiene su nuevo estado en B. Ahora, use B para calcular el siguiente estado de cada celda, y almacene los resultados en A. En un momento dado, una matriz será de solo lectura, y la otra solo de escritura, por lo que nunca habrá contención.

Ventajas:

• Prohibida la reproducción de los datos en comparación con lo que se hace ahora. Solo una escritura está sucediendo por celular.
• Sin tener que preocuparse por las cajas de borde/esquina, ya que el algoritmo es simple.
• Sin asignación continua de memoria. Simplemente asigne las dos matrices cuando comience.

Desventajas:

• es necesario asignar el doble de memoria.

Answer 4

Acabo de tropezar con java.util.concurrent.Exchanger<V>. Actúa como un punto de intercambio. Probablemente pueda usarlo para intercambiar listas de estados celulares entre hilos adyacentes. Eso sería mejor que una barrera porque necesito sincronizar solo entre trabajadores adyacentes.

Answer 5

Para responder a su actualización sobre el problema del almacenamiento en caché con doble almacenamiento en búfer, no es un problema. Las CPU tienen una memoria caché coherente, y saben cuándo se han cambiado los datos en otra memoria caché de la CPU.