Cálculo inverso

La computación inversa es una aplicación de software del concepto de computación reversible .

Debido a que ofrece una posible solución al problema del calor que enfrentan los fabricantes de chips, la computación reversible ha sido ampliamente estudiada en el área de la arquitectura de computadoras. La promesa de la computación reversible es que la cantidad de pérdida de calor para arquitecturas reversibles sería mínima para un número significativamente grande de transistores. ^{[ 1 ] [ 2 ]} En lugar de crear entropía (y por lo tanto calor) a través de operaciones destructivas, una arquitectura reversible conserva la energía al realizar otras operaciones que preservan el estado del sistema. ^{[ 3 ] [ 4 ]}

El concepto de computación inversa es algo más simple que el de computación reversible, ya que la computación inversa solo requiere restaurar el estado equivalente de una aplicación de software, en lugar de admitir la reversibilidad del conjunto de todas las instrucciones posibles. Los conceptos de computación reversible se han aplicado con éxito como computación inversa en áreas de aplicaciones de software tales como el diseño de bases de datos , ^{[ 5 ]} el punto de control y la depuración, ^{[ 6 ]} y la diferenciación de código. ^{[ 7 ] [ 8 ]}

Basándose en la exitosa aplicación de conceptos de computación inversa en otros dominios de software, Chris Carothers, Kalyan Perumalla y Richard Fujimoto ^{[ 9 ]} sugieren la aplicación de la computación inversa para reducir la sobrecarga de guardado de estado en la simulación paralela de eventos discretos (PDES). Definen un enfoque basado en códigos de eventos inversos (que se pueden generar automáticamente) y demuestran las ventajas de rendimiento de este enfoque sobre el guardado de estado tradicional para aplicaciones de grano fino (aquellas con una pequeña cantidad de computación por evento). La propiedad clave que aprovecha la computación inversa es que la mayoría de las operaciones que modifican las variables de estado son de naturaleza "constructiva". Es decir, la operación de deshacer para dichas operaciones no requiere historial. Solo se requieren los valores más recientes de las variables para deshacer la operación. Por ejemplo, operadores como ++, ––, +=, -=, *= y /= pertenecen a esta categoría. Cabe señalar que los operadores *= y /= requieren un tratamiento especial en el caso de multiplicación o división por cero, y condiciones de desbordamiento/subdesbordamiento. Aquí también se incluyen operaciones más complejas, como el desplazamiento circular (el intercambio es un caso especial), y ciertas clases de generación de números aleatorios .

Las operaciones de la forma a = b, los cálculos de módulo y a nivel de bits que resultan en la pérdida de datos se denominan destructivos. Normalmente, estas operaciones solo pueden restaurarse utilizando técnicas convencionales de conservación de estado. Sin embargo, observamos que muchas de estas operaciones destructivas son consecuencia de la llegada de datos contenidos en el evento que se está procesando. Por ejemplo, en el trabajo de Yaun, Carothers, et al., con una simulación TCP a gran escala , ^{[ 10 ]} el registro de tiempo del último envío registra la marca de tiempo del último paquete reenviado en un proceso lógico del enrutador. La operación de intercambio hace que esta operación sea reversible.

En 1985, Jefferson introdujo el protocolo de sincronización optimista, que se utilizó en simulaciones paralelas de eventos discretos, conocido como Time Warp. ^{[ 11 ]} Hasta la fecha, la técnica conocida como Computación Inversa solo se ha aplicado en software para simulaciones paralelas de eventos discretos sincronizadas optimistamente.

En diciembre de 1999, Michael Frank se graduó de la Universidad de Florida . Su tesis doctoral se centró en la computación inversa a nivel de hardware, pero incluyó descripciones tanto de una arquitectura de conjunto de instrucciones como de un lenguaje de programación de alto nivel (R) para un procesador basado en computación inversa. ^{[ 12 ] [ notas 1 ]}

En 1998, Carothers y Perumalla publicaron un artículo para el taller Principios de Simulación Avanzada y Distribuida ^{[ 13 ]} como parte de sus estudios de posgrado bajo la dirección de Richard Fujimoto, introduciendo la técnica de Computación Inversa como un mecanismo de retroceso alternativo en simulaciones de eventos discretos paralelos sincronizadas optimistamente (Time Warp). En 1998, Carothers se convirtió en profesor asociado en el Instituto Politécnico Rensselaer . Trabajando con los estudiantes de posgrado David Bauer y Shawn Pearce, Carothers integró el diseño Time Warp de Georgia Tech en el Sistema de Simulación Optimista (ROSS) de Rensselaer, que solo admitía la computación inversa como mecanismo de retroceso. Carothers también construyó modelos RC para BitTorrent en General Electric, así como numerosos protocolos de red con estudiantes ( BGP4 , TCP Tahoe, Multicast ). Carothers creó un curso sobre Simulación Paralela y Distribuida en el que los estudiantes debían construir modelos RC en ROSS.

Casi al mismo tiempo, Perumalla se graduó del Instituto Tecnológico de Georgia y comenzó a trabajar en el Laboratorio Nacional de Oak Ridge (ORNL). Allí construyó el simulador uSik, un sistema PDES con protocolos optimista y conservador combinados. El sistema era capaz de determinar dinámicamente el mejor protocolo para los LP y reasignarlos durante la ejecución en respuesta a la dinámica del modelo. En 2007, Perumalla probó uSik en Blue Gene/L y descubrió que, si bien la escalabilidad se limita a 8K procesadores para la implementación de Time Warp puro, la implementación conservadora escala a 16K procesadores disponibles. Cabe destacar que la evaluación comparativa se realizó utilizando PHOLD con una tasa de eventos remotos restringida del 10%, donde la marca de tiempo de los eventos se determinó mediante una distribución exponencial con una media de 1.0, y se agregó un anticipo adicional de 1.0 a cada evento. Esta fue la primera implementación de PDES en Blue Gene utilizando computación inversa.

De 1998 a 2005, Bauer realizó estudios de posgrado en RPI bajo la dirección de Carothers, centrándose exclusivamente en la computación inversa. Desarrolló el primer sistema PDES basado únicamente en computación inversa, denominado Sistema de Simulación Optimista de Rensselaer (ROSS) ^{[ 14 ]} , para sistemas combinados de memoria compartida y distribuida . De 2006 a 2009, Bauer trabajó con EH Page en Mitre Corporation y, en colaboración con Carothers y Pearce, extendió el simulador ROSS al procesador Blue Gene/P (Intrepid) de 131 072. Esta implementación fue estable para tasas de eventos remotos del 100 % (cada evento enviado a través de la red). Durante su estancia en RPI y MITRE, Bauer desarrolló el sistema de simulación de redes ROSS.Net ^{[ 15 ]} , que admite el diseño de experimentos semiautomatizados para la optimización de caja negra de modelos de protocolos de red que se ejecutan en ROSS. Un objetivo principal del sistema era optimizar múltiples modelos de protocolos de red para su ejecución en ROSS. Por ejemplo, la creación de una estructura de capas LP para eliminar los eventos que se transmiten entre protocolos LP de red en la misma máquina simulada optimiza la simulación de nodos de red TCP/IP al eliminar las marcas de tiempo de desplazamiento cero entre los protocolos TCP e IP. Bauer también construyó modelos basados ​​en agentes RC para redes de contacto social para estudiar los efectos de las enfermedades infecciosas , en particular la gripe pandémica, que escalan a cientos de millones de agentes; así como modelos RC para redes móviles ad hoc que implementan la funcionalidad de movilidad (detección de proximidad) y la propagación de ondas electromagnéticas de capa física de alta precisión (modelo de matriz de línea de transmisión). ^{[ 16 ]}

Recientemente, la comunidad PDES ha impulsado el desarrollo de la simulación continua. Por ejemplo, Fujimoto y Perumalla, en colaboración con Tang et al. ^{[ 17 ]} , implementaron un modelo RC de partícula en celda y demostraron una excelente aceleración con respecto a la simulación continua para modelos de luz como partícula. Bauer y Page demostraron una excelente aceleración para un modelo de matriz de línea de transmisión RC (PB Johns, 1971), que modela la luz como una onda en frecuencias de microondas. Bauer también creó una variante RC de SEIR que genera una mejora considerable con respecto a los modelos continuos en el área de la propagación de enfermedades infecciosas. Además, el modelo RC SEIR es capaz de modelar múltiples enfermedades de manera eficiente, mientras que el modelo continuo crece exponencialmente con respecto al número de combinaciones de enfermedades posibles en la población.

• RC '05 – 1er Taller Internacional sobre Computación Reversible
• Ciclo de talleres/conferencias sobre computación reversible