¿Las unidades de procesamiento paralelo masivo de hoy en día pueden ejecutar autómatas celulares de manera eficiente?

Me pregunto si las unidades de cómputo masivamente paralelas proporcionadas en las tarjetas gráficas hoy en día (una que es programable en OpenCL , por ejemplo) son lo suficientemente buenas como para simular de manera eficiente autómatas celulares 1D (¿o tal vez autómatas celulares 2D?).

Si elegimos la cuadrícula finita que cabría en la memoria del chip, ¿podemos esperar que una transición de un autómata celular definido en esta cuadrícula se calcule en tiempo (casi) constante?

Supongo que los autómatas celulares 2D requerirían más ancho de banda para la comunicación entre las diferentes partes de los chips que los autómatas 1D.

También me interesaría la misma pregunta en el caso de la programación FPGA o los chips personalizados.

Excelente pregunta Creo que la respuesta es si.

La evolución de un autómata celular es esencialmente equivalente a realizar un cálculo de plantilla. En algunas cuadrículas 1D, 2D o 3D, los valores sucesivos de puntos (o celdas) se calculan en función del último valor de la vecindad del punto. En una CA 1D simple, este vecindario podría ser la celda y las dos celdas a la izquierda y a la derecha. Hay muchos ejemplos de cálculos de plantilla que se realizan en GPU; El conjunto de pruebas SHOC de ORNL para OpenCL / CUDA contiene un ejemplo de plantilla 2D, por ejemplo.

La idea básica es hacer que cada hilo obtenga una copia local del vecindario para varios puntos, luego calcule los siguientes valores para los puntos determinados por ese vecindario. Al utilizar adecuadamente la jerarquía de memoria en, por ejemplo, CUDA (registros, compartidos, constantes, textura y memorias globales) y el modelo de procesamiento SIMT (por ejemplo, al calcular adecuadamente la función de transición sin introducir una divergencia de deformación excesiva), se puede lograr un buen rendimiento.

Esta respuesta sería mucho mejor si tuviera que dar un ejemplo, pero estoy demasiado ocupado para escribir cualquier código en este momento ... Pero en teoría, creo que debería ser posible simular CA de manera eficiente en las GPU al modelarlas después de la plantilla cálculos Sin embargo, hay muchas consideraciones para escribir un buen cálculo de plantilla para GPU.

Hagas lo que hagas, calcular el siguiente estado para un autómata celular requiere tantos cálculos como celdas en el autómata. Por lo tanto, para obtener un tiempo constante, necesita tantos núcleos informáticos como celdas.

El número de estos en GPU es actualmente de unos pocos miles, mientras que el cálculo del siguiente estado es tan simple que espero que el resultado esté vinculado a IO, es decir, puede obtener una muy buena aproximación del tiempo necesario simplemente considerando el se necesita movimiento de datos (y si no es una buena aproximación, la implementación tiene una ineficiencia o la arquitectura no es adecuada, pero eso sería muy sorprendente).

Para FPGA, la pregunta es más difícil y probablemente dependerá de la combinación de unidades de memoria y cálculo disponibles. Si no estoy demasiado lejos, no tendrás suficiente memoria para mantener ocupadas todas las unidades y si confías en la memoria externa, estás en el mismo asiento que la GPU, el ancho de banda de la memoria será el factor limitante y no se sorprenderá si la conclusión es que no hay ventaja sobre la GPU. (Tenga en cuenta que si bien trabajé con FPGA, fue hace años, ahora puede haber modelos FPGA con una combinación correcta).

ASIC ofrece más flexibilidad. Puede tener fácilmente una implementación similar a la sistólica (pero con el flujo de datos bidireccional, algunos sistólicos generalmente están restringidos al flujo de datos unidireccional), cada celda física es una lógica: un poco de memoria y la lógica necesaria para calcular su próximo estado y se presenta para que sea vecino físico es lógico. Obviamente estás en el reino del tiempo constante. Dependiendo de las macros duras que tenga, puede ser mejor ser un poco menos obvio y tener células físicas que reagrupen varias lógicas. El objetivo es maximizar lo que se hace en un chip, en otras palabras, minimizar la comunicación con el exterior del chip tan pronto como sus necesidades de comunicación sean proporcionales al número de celdas, tendrá un ancho de banda limitado. Sí, eso significa que si necesita mirar todas las celdas para cada paso, probablemente no seas mucho mejor que con GPU. (La personalización completa solo proporcionaría una mejor integración, es decir, más celdas por chip).

Resumen: si desea ver todos los estados intermedios, la GPU es el enfoque más efectivo; si no lo hace, necesita el volumen para justificar que un ASIC tenga algo mejor, FPGA probablemente no ofrecerá suficiente ventaja si tener alguno.

Me pregunto si las unidades de cómputo masivamente paralelas proporcionadas en las tarjetas gráficas hoy en día son lo suficientemente buenas como para simular de manera eficiente autómatas celulares 1D (¿o tal vez autómatas celulares 2D?).

Siendo muy general, sí, la informática GPU es la mejor alternativa en hardware estándar disponible para todos.

$O(1)$$n \le P$$n$$P$$O(1)$

en el lado de FPGA y ASIC, sé que hay investigaciones sobre la construcción de una CA física como una cuadrícula de puertas lógicas con estados, todos conectados por sus vecinos; es decir, matrices sistólicas . La idea sería no usar más una memoria global sino confiar en los estados de cada nodo en la cuadrícula. Una máquina de este tipo sería revolucionaria ya que entonces podríamos dejar de hablar de una computadora que simula una CA y comenzar a hablar de una CA que se ejecuta como una computadora (algunas CA se están completando).