Matemáticas y computación
Números, demostraciones, grafos y máquinas, investigados mediante cálculo además de deducción.
Las matemáticas y la informática ya ponen a prueba sus propias ideas mediante simulación. Generan millones de grafos aleatorios para ver qué es típico. Ejecutan una máquina para ver qué hace de verdad un algoritmo. Atacan un cifrado una y otra vez para aprender cómo falla. Nada de esto describe el mundo físico. Explora el espacio de los números, las estructuras y las propias computaciones. La práctica va desde la matemática experimental hecha a mano durante siglos hasta las herramientas modernas de verificación que comprueban un diseño frente a todos los estados alcanzables antes de construirlo.
Experimentos con matrices aleatorias
Matrices grandes llenas de números aleatorios, diagonalizadas una y otra vez para estudiar la estadística de sus valores propios.
Pregunta que responde: ¿En qué patrón se asientan los valores propios de una matriz aleatoria, y coincide con otras áreas de las matemáticas y la física?
Deja fuera: Solo muestrea un rincón diminuto de un espacio infinito de matrices posibles.
Se ejecuta en: unos 1012 FLOPS aproximado un clúster universitario que genera y diagonaliza muchas matrices grandesDesde: 1955 Trabajo temprano de Wigner sobre la estadística de valores propios de matrices aleatorias
Experimentos con grafos aleatorios
Grafos generados por una regla aleatoria, nodo por nodo o arista por arista, para ver qué propiedades, como la conectividad o el agrupamiento, aparecen de forma típica.
Pregunta que responde: ¿Cómo es una red «típica» bajo esta regla para añadir nodos y aristas?
Deja fuera: Las redes del mundo real rara vez son tan limpias como la regla que genera el modelo.
Se ejecuta en: unos 1010 FLOPS aproximado se ejecuta en un escritorio para grafos de hasta millones de nodosDesde: 1959 El modelo de grafos aleatorios de Erdős y Rényi
Simulación de percolación
Una retícula o red con sitios o enlaces que se abren al azar, vigilada hasta el punto en que un camino conectado cruza de pronto todo el sistema.
Pregunta que responde: ¿A qué densidad una red aleatoria se vuelve de pronto conexa de extremo a extremo?
Deja fuera: Las redes idealizadas se comportan de forma más limpia que cualquier material poroso o red reales.
Se ejecuta en: unos 1010 FLOPS aproximado un equipo de escritorio para grandes barridos de retículaDesde: 1957 La introducción de la teoría de la percolación por Broadbent y Hammersley
Búsquedas de matemática experimental
Búsqueda numérica por fuerza bruta de patrones, contraejemplos o relaciones exactas entre números, llevada mucho más allá de lo que se podría comprobar a mano.
Pregunta que responde: ¿Es cierta esta conjetura en todos los casos que alguien puede permitirse comprobar, y surge algún patrón?
Deja fuera: Ninguna cantidad de casos comprobados es una demostración, por muchos que se vea que se cumplen.
Se ejecuta en: unos 1011 FLOPS aproximado un clúster universitario que se ejecuta durante días en una sola búsquedaDesde: 1963 ya en 1963, búsquedas por computadora de relaciones entre enteros y de patrones de números primos
Estimación de constantes por Monte Carlo
Muestreo aleatorio usado para estimar una constante o una integral matemática, como esparcir puntos para estimar un área, como ejercicio y no para un modelo físico.
Pregunta que responde: ¿Con qué precisión puede el muestreo aleatorio a ciegas, por sí solo, fijar una cantidad matemática exacta?
Deja fuera: Converge mucho más despacio que casi cualquier método numérico más sofisticado.
Se ejecuta en: unos 109 FLOPS aproximado se ejecuta en una laptop en segundos o minutosDesde: 1946 La idea de Ulam de 1946; von Neumann propuso una versión para computadora electrónica en marzo de 1947, y el método se publicó por primera vez en 1949 fuenteEn el árbol de Simulaciones: Método de Monte Carlo
Búsquedas computacionales en teoría de números
Números grandes a los que se comprueba la primalidad, que se factorizan o en los que se buscan propiedades especiales, como los números perfectos, con algoritmos ejecutados a gran escala y no a mano.
Pregunta que responde: ¿Tiene este número enorme la propiedad que buscamos, y hasta dónde puede la búsqueda empujar el récord?
Deja fuera: Las búsquedas que baten récords dicen poco de los números que nadie ha pensado todavía en comprobar.
Se ejecuta en: unos 1013 FLOPS aproximado un proyecto de computación voluntaria distribuida en muchas máquinas donadasDesde: 1951 La prueba manual de Lucas para los primos de Mersenne, ejecutada por primera vez en computadora en 1951
Cálculo numérico de atractores caóticos
Un pequeño conjunto de ecuaciones no lineales integrado paso a paso para revelar la dependencia sensible de las condiciones iniciales y un atractor fractal.
Pregunta que responde: ¿Por qué un sistema determinista simple se vuelve impredecible?
Deja fuera: El redondeo numérico implica que una trayectoria larga no es una órbita verdadera, solo una que se mantiene cerca de una.
Se ejecuta en: unos 103 FLOPS aproximado unas pocas ecuaciones, segundos en una laptop.Desde: 1963 El flujo determinista no periódico de Lorenz, un modelo de convección ejecutado en una computadora. fuenteEn el árbol de Simulaciones: La convección caótica de Lorenz
Experimentos de redes no lineales
Una cadena de masas con resortes no lineales que se pone en marcha en un solo modo y se sigue para ver si la energía se reparte de forma uniforme, como sugeriría la termodinámica.
Pregunta que responde: ¿Reparte una cadena no lineal su energía por igual entre todos sus movimientos?
Deja fuera: Los resultados dependen de la cadena elegida y del estado inicial.
Se ejecuta en: unos 103 FLOPS aproximado diminuto para los estándares modernos; el original usaba unas pocas docenas de masas.Desde: 1955 Los estudios de problemas no lineales de Fermi, Pasta y Ulam en una de las primeras computadoras digitales. fuente
Experimentos numéricos con solitones
Una ecuación de onda no lineal resuelta en una cuadrícula para ver cómo los pulsos se atraviesan entre sí y conservan su forma, algo que las ondas lineales no hacen.
Pregunta que responde: ¿Por qué algunas ondas no lineales se atraviesan sin cambiar?
Deja fuera: Muestra una sola familia de ecuaciones, no el comportamiento general de las ondas no lineales.
Se ejecuta en: unos 104 FLOPS aproximado una cuadrícula unidimensional, trivial hoy.Desde: 1965 Interacción de solitones en un plasma sin colisiones y recurrencia de los estados iniciales, de Zabusky y Kruskal. fuente
Renderizado de conjuntos fractales
Una fórmula iterada sencilla que se prueba en cada punto del plano complejo para ver si escapa, y que dibuja la frontera del conjunto de puntos estables.
Pregunta que responde: ¿Cuál es la forma del conjunto en el que una iteración simple permanece acotada?
Deja fuera: Las pruebas de escape solo sugieren pertenencia, y la imagen es un muestreo de resolución finita de un conjunto infinitamente detallado.
Se ejecuta en: unos 109 FLOPS aproximado los acercamientos profundos necesitan iteración de precisión ampliada en millones de puntos.Desde: 1980 Los aspectos fractales de la iteración de z a lambda z(1-z) de Mandelbrot, las primeras imágenes por computadora del conjunto de Mandelbrot. fuente
Criticalidad autoorganizada de la pila de arena
Granos que caen sobre una cuadrícula y se derrumban cuando la pendiente es demasiado empinada, lo que da avalanchas de todos los tamaños sin ajustar nada, como modelo de cómo los sistemas llegan a un estado crítico.
Pregunta que responde: ¿Por qué aparecen avalanchas de todos los tamaños sin ningún ajuste?
Deja fuera: Se discute si los sistemas reales comparten la misma escala.
Se ejecuta en: unos 109 FLOPS aproximado ejecuciones largas en mallas grandes para ver el escalado.Desde: 1987 La criticalidad autoorganizada de Bak, Tang y Wiesenfeld: una explicación del ruido 1/f. fuente
Cálculo de ceros de la función zeta de Riemann
Los valores de la función zeta a lo largo de su recta crítica se calculan para localizar y contar sus ceros, y comprobar que están donde dice la hipótesis.
Pregunta que responde: ¿Están todos los ceros no triviales de la función zeta en una misma recta?
Deja fuera: Una comprobación finita, por larga que sea, no puede demostrar que no exista más allá de ella ningún cero fuera de la recta.
Se ejecuta en: unos 1018 FLOPS aproximado décadas de tiempo de CPU en las mayores búsquedas.Desde: 1953 Cálculos de Turing de la función zeta de Riemann. fuente
Cifras de pi por computadora
Series para pi sumadas hasta cantidades enormes de dígitos con aritmética exacta, que ponen a prueba tanto el número como la máquina.
Pregunta que responde: ¿Parecen aleatorias las cifras de pi, y se puede confiar en la máquina a esta escala?
Deja fuera: Los dígitos no responden a ninguna pregunta abierta, y las comprobaciones detectan errores de hardware solo si el método es independiente.
Se ejecuta en: unos 1017 FLOPS aproximado meses en un servidor para cientos de billones de dígitos.Desde: 1950 La determinación de pi y e con más de 2000 decimales en el ENIAC, de Reitwiesner (publicada en 1950, reimpresa en Pi: A Source Book). fuente
Descubrimiento de conjeturas guiado por IA
El aprendizaje automático sobre grandes tablas de objetos matemáticos encuentra qué propiedades están vinculadas, para sugerir una conjetura que los matemáticos intentan después demostrar.
Pregunta que responde: ¿Qué relación oculta entre estas cantidades matemáticas vale la pena demostrar?
Deja fuera: Solo sugiere patrones y no prueba nada por sí mismo, y algunas regularidades de los datos pueden ser artefactos de cómo se produjeron.
Se ejecuta en: unos 1015 FLOPS aproximado días en unas pocas GPU por conjunto de datos.Desde: 2021 Davies y sus colegas, avanzar en las matemáticas guiando la intuición humana con IA. fuente
Búsqueda aprendida de algoritmos y construcciones
Un sistema de juego o de modelo de lenguaje busca procedimientos u objetos matemáticos nuevos, y una computadora comprueba que cada candidato sea correcto.
Pregunta que responde: ¿Puede un programa descubrir un algoritmo más rápido o un ejemplo mayor que los que han hallado las personas?
Deja fuera: Cada resultado es un único ejemplo nuevo, y la búsqueda cubre solo los tipos de objetos que sus diseñadores plantearon como un juego.
Se ejecuta en: unos 1017 FLOPS aproximado de días a semanas en clústeres de aceleradores.Desde: 2022 AlphaTensor de Fawzi y sus colegas, que descubre algoritmos de multiplicación de matrices más rápidos con aprendizaje por refuerzo. fuente
Verificación de modelos
Cada estado alcanzable de un sistema finito, como un protocolo o el diseño de un circuito, enumerado por computadora para comprobar que una propiedad se cumple en todos ellos.
Pregunta que responde: ¿Hay algún estado alcanzable en el que este diseño rompa sus propias reglas?
Deja fuera: Los espacios de estados crecen más allá de lo que se puede comprobar, así que los diseños reales se simplifican primero.
Se ejecuta en: unos 1012 FLOPS aproximado un clúster universitario que agota un espacio de estados grande pero acotadoDesde: 1981 La introducción de la verificación de modelos por Clarke y Emerson
Búsqueda de demostración automática de teoremas
Una búsqueda a través de cadenas de inferencia lógica, generadas por computadora paso a paso, en busca de una prueba o una refutación de un enunciado matemático.
Pregunta que responde: ¿Existe una cadena válida de pasos lógicos desde los axiomas hasta este enunciado?
Deja fuera: Halla demostraciones que ningún humano elegiría, y a veces ninguna al alcance.
Se ejecuta en: unos 1011 FLOPS aproximado un clúster universitario que busca durante horas o díasDesde: 1956 el Logic Theorist, uno de los primeros programas de búsqueda automática de demostraciones
SAT y resolución de restricciones
Millones de combinaciones de valores verdaderos o falsos exploradas de forma sistemática para satisfacer un gran conjunto de restricciones lógicas, usadas para programar, trazar rutas o verificar diseños.
Pregunta que responde: ¿Existe alguna asignación de valores que cumpla a la vez todas estas restricciones?
Deja fuera: Algunas instancias son tan difíciles que ningún solucionador, por bueno que sea, termina a tiempo.
Se ejecuta en: unos 1011 FLOPS aproximado de una estación de trabajo a un clúster, según el tamaño del problemaDesde: 1962 el procedimiento de Davis-Putnam para la búsqueda de satisfacibilidad
Modelado de ataques criptográficos
Un esquema de códigos o de intercambio de claves atacado millones de veces en simulación, por fuerza bruta, sesgo estadístico o una debilidad modelada, para medir cuánto esfuerzo cuesta realmente romperlo.
Pregunta que responde: ¿Cuántas operaciones haría falta realmente para romper esto, y sigue siendo ese número lo bastante grande para ser seguro?
Deja fuera: Solo prueba los ataques que el analista pensó en modelar, no el que nadie ha encontrado todavía.
Se ejecuta en: unos 1014 FLOPS aproximado un clúster distribuido de muchas máquinas que ejecutan ensayos de ataqueDesde: 1976 ya en 1976, el análisis computacional de la fortaleza de cifrados y de intercambios de claves
Simulación de fugas por canal lateral
El consumo de energía, el tiempo o la emisión electromagnética de un dispositivo, modelados mientras ejecuta una operación criptográfica, para ver qué podría aprender de ello alguien que escuche desde fuera.
Pregunta que responde: ¿Cuánto de la clave secreta se filtra por el comportamiento físico del dispositivo, y no por las matemáticas?
Deja fuera: Las condiciones de laboratorio captan señales más limpias de lo que suele dar un dispositivo real con ruido.
Se ejecuta en: unos 1010 FLOPS aproximado una estación de trabajo que modela la traza de consumo o de tiempos de un dispositivoDesde: 1996 La demostración de Kocher de los ataques de temporización contra implementaciones criptográficas
Verificación de protocolos de seguridad
Cada mensaje que un atacante podría enviar, repetir o falsificar en un protocolo de comunicación, enumerado por computadora para comprobar si se le puede arrancar un secreto o una identidad.
Pregunta que responde: ¿Puede alguna secuencia de mensajes engañar a este protocolo para que filtre un secreto o acepte una identidad falsa?
Deja fuera: Verifica el protocolo tal como está especificado, no los atajos que toma una implementación real.
Se ejecuta en: unos 1011 FLOPS aproximado de una estación de trabajo a un clúster que revisa el espacio de mensajes de un protocoloDesde: 1989 el modelo de Dolev-Yao, una base fundamental para la verificación de protocolos
Demostración asistida por computadora mediante comprobación exhaustiva de casos
Un teorema reducido a una lista finita de casos, cada uno verificado por un programa, porque ningún humano podría comprobarlos todos.
Pregunta que responde: ¿Se puede completar una demostración con una máquina que compruebe todos los casos?
Deja fuera: La confianza pasa al programa, al hardware y al argumento de reducción de casos.
Se ejecuta en: unos 109 FLOPS aproximado unas mil horas en un mainframe para el original; mucho menos ahora.Desde: 1977 La demostración de Appel y Haken de que todo mapa plano se puede colorear con cuatro colores, con reducibilidad comprobada por computadora. fuente
Numérica validada
Cálculos hechos con cotas garantizadas, de modo que un resultado numérico demuestra un enunciado matemático, como la existencia de un atractor caótico.
Pregunta que responde: ¿Se puede demostrar que una respuesta calculada es correcta, y no solo probablemente precisa?
Deja fuera: Las cotas pueden dispararse a lo largo de tiempos largos, y limitan las demostraciones a problemas cortos o bien comportados.
Se ejecuta en: unos 109 FLOPS aproximado la aritmética de intervalos multiplica el costo por un factor modesto.Desde: 2002 El solucionador riguroso de EDO de Tucker y el 14.º problema de Smale, que demuestra que existe el atractor de Lorenz. fuente
Enumeración de máquinas de Turing
Cada programa pequeño de una máquina mínima ejecutado para ver cuáles se detienen y cuáles corren para siempre, y hallar el de mayor duración que se detiene de cada tamaño.
Pregunta que responde: ¿Cuánto tiempo puede funcionar un programa diminuto antes de detenerse?
Deja fuera: La indecidibilidad significa que algunas máquinas nunca pueden clasificarse, por mucho que funcionen.
Se ejecuta en: unos 1015 FLOPS aproximado miles de millones de máquinas, con demostraciones para las que no se detienen.Desde: 1965 Los estudios por computadora de Lin y Rado sobre problemas de máquinas de Turing. fuente
Verificación estadística de modelos
Un sistema de comportamiento aleatorio simulado muchas veces para estimar con confianza la probabilidad de que incumpla una propiedad.
Pregunta que responde: ¿Qué probabilidad hay de que un sistema aleatorio rompa una regla de seguridad?
Deja fuera: Las ejecuciones estadísticas dan una probabilidad con un nivel de confianza, no una prueba, y los fallos raros exigen muestreo por importancia.
Se ejecuta en: unos 109 FLOPS aproximado miles a millones de ejecuciones muestreadas.Desde: 2002 Verificación probabilística de sistemas de eventos discretos mediante muestreo de aceptación, de Younes y Simmons. fuente
Pruebas de fuzzing
A un programa se le dan enormes cantidades de entradas aleatorias o mutadas para hallar las que lo hacen fallar, lo que equivale a simular un mundo hostil o descuidado.
Pregunta que responde: ¿Qué entrada hará fallar este software?
Deja fuera: Solo encuentra los fallos a los que llegan las entradas aleatorias, y un programa puede pasar años sin problemas mientras esconde un error tras un caso poco frecuente.
Se ejecuta en: unos 1014 FLOPS aproximado años-máquina de tiempo de CPU para una gran base de código.Desde: 1990 El estudio empírico de la fiabilidad de las utilidades de UNIX, de Miller, Fredriksen y So. fuente
Ejecución simbólica
Un programa se ejecuta con entradas desconocidas escritas como símbolos, recogiendo las condiciones de cada camino, y luego un solucionador halla los valores que toman cada rama.
Pregunta que responde: ¿Qué entradas hacen que se ejecute cada ruta de este programa, y alguna llega a un error?
Deja fuera: El número de rutas crece exponencialmente con el tamaño del programa, así que los grandes se cubren solo en parte.
Se ejecuta en: unos 1012 FLOPS aproximado horas de tiempo de resolución por programa, con un crecimiento brusco según el número de trayectorias.Desde: 1976 La ejecución simbólica y las pruebas de programas, de King. fuente
Interpretación abstracta
Un programa se ejecuta sobre conjuntos de valores posibles, como rangos, en lugar de valores sueltos, para demostrar propiedades que se cumplen para toda entrada.
Pregunta que responde: ¿Puede este programa dividir alguna vez por cero o desbordarse, para alguna entrada?
Deja fuera: La aproximación segura da falsas alarmas, así que las personas siguen teniendo que revisar cada aviso.
Se ejecuta en: unos 1011 FLOPS aproximado horas en una estación de trabajo para una base de código aviónico grande.Desde: 1977 La interpretación abstracta de Cousot y Cousot, un modelo unificado de retículas para el análisis estático de programas. fuente
Verificación acotada de modelos
El comportamiento de un diseño hasta un número fijo de pasos se escribe como una fórmula lógica y se entrega a un solucionador de satisfacibilidad para hallar cualquier camino corto hacia un error.
Pregunta que responde: ¿Puede este circuito o programa llegar a un estado de error en un número dado de pasos?
Deja fuera: No prueba nada más allá del límite de pasos, a menos que un argumento aparte muestre que basta.
Se ejecuta en: unos 1013 FLOPS aproximado horas en un servidor por propiedad.Desde: 1999 La verificación simbólica de modelos sin BDD de Biere, Cimatti, Clarke y Zhu. fuente
Pruebas aleatorias basadas en propiedades
Se enuncia una regla que siempre debería cumplirse, y la computadora genera muchos casos aleatorios y reduce cualquier fallo a un contraejemplo pequeño.
Pregunta que responde: ¿Obedece este código su propia especificación con una amplia gama de entradas?
Deja fuera: Los casos aleatorios pueden no llegar nunca a una condición rara, y la propiedad escrita puede no ser la que importa.
Se ejecuta en: unos 109 FLOPS aproximado minutos en una laptop para miles de casos.Desde: 2000 QuickCheck de Claessen y Hughes, una herramienta ligera para probar al azar programas en Haskell. fuente
Verificación de redes neuronales
Los solucionadores de restricciones demuestran que, para toda entrada de una región, la salida de una red neuronal se mantiene dentro de unos límites, en lugar de probar muestras.
Pregunta que responde: ¿Puede un pequeño cambio en una entrada hacer que la red dé una respuesta equivocada?
Deja fuera: Las demostraciones solo escalan a redes pequeñas, y el conjunto de perturbaciones que se pueden comprobar es estrecho.
Se ejecuta en: unos 1013 FLOPS aproximado de horas a días en un servidor para una red pequeña.Desde: 2017 Reluplex, un solucionador SMT para verificar redes neuronales profundas, de Katz y sus colegas. fuente
Simulación de arquitectura de computadoras
El pipeline, las cachés y el predictor de saltos de un procesador propuesto, modelados instrucción por instrucción, para estimar la velocidad de un chip antes de construirlo.
Pregunta que responde: ¿Con qué rapidez ejecutaría programas reales este diseño de procesador, antes de cortar ningún silicio?
Deja fuera: Simplifica tanto del chip real que el silicio final siempre difiere un poco del modelo.
Se ejecuta en: unos 1011 FLOPS aproximado un clúster universitario que ejecuta programas de referencia en el modeloDesde: 1990 ya en 1990, simuladores de procesadores exactos al ciclo para la investigación de arquitectura
Simulación de sistemas distribuidos y consenso
Muchas computadoras modeladas que se envían mensajes entre sí con retrasos, pérdidas y fallos, para comprobar si un algoritmo distribuido sigue acordando la respuesta correcta.
Pregunta que responde: ¿Sigue este algoritmo llegando al acuerdo correcto cuando se pierden o se retrasan mensajes o fallan nodos?
Deja fuera: Los fallos inyectados son los que el diseñador previó, no los que surgen de forma inesperada en producción.
Se ejecuta en: unos 1010 FLOPS aproximado un clúster que simula cientos de nodos virtualesDesde: 1978 Los primeros trabajos de Lamport sobre el orden y el fallo en sistemas distribuidos
Simulación de sistemas de almacenamiento
Discos, unidades y sistemas de archivos modelados según cómo distribuyen los datos, fallan y se recuperan, para probar un diseño de almacenamiento antes de comprar y llenar unidades reales.
Pregunta que responde: ¿Cómo rinde y cómo sobrevive a los fallos este diseño de almacenamiento, a una escala demasiado cara para probarla primero de verdad?
Deja fuera: Las unidades reales fallan de maneras más desordenadas y más correlacionadas que la tasa de fallos aleatoria del modelo.
Se ejecuta en: unos 1010 FLOPS aproximado de una estación de trabajo a un clúster pequeño que modela un sistema de almacenamientoDesde: 1988 ya en 1988, modelos de simulación de la fiabilidad de matrices de discos
Simulación de planificadores de sistemas operativos
Un flujo de tareas de cómputo que llegan y compiten por un procesador, modelado y ejecutado con distintas reglas de planificación para ver cuál es la más justa o la más rápida.
Pregunta que responde: ¿Qué manera de ordenar la cola de tareas hace más trabajo, o es más justa con cada tarea?
Deja fuera: Las cargas de trabajo sintéticas rara vez coinciden con la mezcla irregular de tareas que encuentra una máquina real.
Se ejecuta en: unos 109 FLOPS aproximado se ejecuta en una laptop o una estación de trabajo en segundos o minutosDesde: 1968 ya en 1968, los estudios de simulación de políticas de planificación de procesadores
Búsqueda de optimización de compiladores y programas
Un enorme número de pequeñas variaciones de un fragmento de código, probadas y medidas, en busca de la versión más rápida o más corta que siga haciendo el mismo trabajo.
Pregunta que responde: De todas las formas equivalentes de escribir este pequeño fragmento de código, ¿cuál es realmente la más rápida?
Deja fuera: Los programas hallados son a veces tan inusuales que no hay ninguna explicación disponible de por qué funcionan.
Se ejecuta en: unos 1010 FLOPS aproximado un clúster que busca en un gran espacio de variantes de códigoDesde: 2006 ya en 2006, búsqueda de superoptimización sobre secuencias cortas de instrucciones
Pruebas empíricas del rendimiento de algoritmos
Un algoritmo ejecutado miles de veces con entradas generadas al azar o reales de tamaño creciente, para medir cómo crece de verdad su tiempo de ejecución en lugar de demostrarlo sobre el papel.
Pregunta que responde: ¿Cómo crece en la práctica el tiempo de ejecución de este algoritmo, con las entradas que va a ver de verdad?
Deja fuera: Un peor caso ausente de las entradas de prueba sigue sin detectarse hasta que ocurre.
Se ejecuta en: unos 109 FLOPS aproximado se ejecuta en una estación de trabajo sobre muchas entradas de prueba generadasDesde: 1970 ya en 1970, la comprobación empírica sistemática de los tiempos de ejecución de algoritmos
Ejecución de programas por modelos de lenguaje
Un modelo de lenguaje escribe paso a paso los estados intermedios mientras sigue lo que calcularía un programa.
Pregunta que responde: ¿Puede un modelo de lenguaje emular la ejecución de código?
Deja fuera: No se garantiza que el resultado sea correcto, y los programas largos fallan.
Se ejecuta en: unos 1014 FLOPS aproximado Inferencia por consultaDesde: 2021 Show your work: scratchpads for intermediate computation with language models (2021) fuente
Simulación del consenso en cadenas de bloques
Una red de nodos que producen y comparten bloques con retrasos, para probar cómo afectan el tamaño del bloque, el momento y los atacantes a la seguridad y al rendimiento.
Pregunta que responde: ¿Qué tan seguro y rápido es un blockchain con retrasos de red y ataques?
Deja fuera: El comportamiento real de los nodos y las topologías de red solo se miden en parte.
Se ejecuta en: unos 108 FLOPS aproximado ejecuciones guiadas por eventos de miles de nodos.Desde: 2016 El análisis de seguridad y rendimiento de cadenas de bloques de prueba de trabajo con un simulador, de Gervais y sus colegas. fuente
Simulación paralela de eventos discretos
Una simulación de eventos en el tiempo se reparte entre muchos procesadores, cada uno de los cuales avanza su propio reloj y retrocede si llega algo tarde.
Pregunta que responde: ¿Cómo puede ejecutarse rápido, en muchas máquinas, una enorme simulación guiada por eventos, como una red o un campo de batalla?
Deja fuera: Las reversiones pueden encadenarse, y la aceleración depende mucho de lo estrechamente acoplados que estén los eventos.
Se ejecuta en: unos 1014 FLOPS aproximado horas en una supercomputadora para miles de millones de eventos.Desde: 1985 El tiempo virtual de Jefferson, el mecanismo Time Warp de sincronización optimista. fuente
Simulación de la arquitectura de procesadores gráficos
Los núcleos, los warps y la memoria de un procesador gráfico se modelan ciclo a ciclo, ejecutando programas reales para evaluar un diseño antes de construirlo.
Pregunta que responde: ¿Cómo afectaría un cambio de diseño a la velocidad de los programas paralelos en un chip gráfico?
Deja fuera: Los detalles de los chips reales son secretos o desconocidos, así que el modelo coincide solo de forma aproximada con las cifras de los diseños existentes.
Se ejecuta en: unos 1012 FLOPS aproximado de horas a días de tiempo del anfitrión por segundo de ejecución simulada.Desde: 2009 El análisis de Bakhoda y sus colegas de cargas de trabajo CUDA con un simulador detallado de GPU. fuente
Simulación de sistemas acelerada con FPGA
El diseño de un chip se carga en muchos circuitos reconfigurables que lo ejecutan ciclo a ciclo con exactitud a velocidades de megahercios, y simulan servidores enteros y redes de ellos.
Pregunta que responde: ¿Cómo se comportarán este procesador y su clúster al ejecutar software real, antes de fabricarlos?
Deja fuera: Es mucho más lento que el chip real, y un diseño que no cabe en los circuitos no se puede ejecutar.
Se ejecuta en: unos 1015 FLOPS aproximado días en una nube de cientos de circuitos reconfigurables.Desde: 2018 FireSim, de Karandikar y sus colegas: simulación de sistemas a gran escala, exacta al ciclo y acelerada con FPGA, en la nube pública. fuente
Simulación de sistema completo
Una computadora entera, con procesadores, memoria, discos y tarjetas de red, se simula con la fidelidad suficiente para arrancar un sistema operativo sin modificar y ejecutar sus programas.
Pregunta que responde: ¿Cómo se comporta un software real en una máquina que todavía no existe, o que se puede pausar y reproducir a voluntad?
Deja fuera: La temporización se aproxima por velocidad, así que no puede dar el rendimiento exacto, solo el comportamiento funcional.
Se ejecuta en: unos 1011 FLOPS aproximado casi en tiempo real en un servidor por máquina simulada.Desde: 2002 Simics, de Magnusson y sus colegas, una plataforma de simulación de sistemas completos. fuente
Emulación de redes ligera
Decenas o cientos de hosts y conmutadores virtuales ejecutan software de red real en una sola laptop, enlazados por cables emulados con velocidad y retardo fijados.
Pregunta que responde: ¿Funcionará este programa de control de red en toda una topología antes de desplegarlo?
Deja fuera: El propio procesador del anfitrión lo comparten todos los nodos virtuales, así que los enlaces rápidos se vuelven lentos.
Se ejecuta en: unos 1010 FLOPS aproximado tiempo real en una sola estación de trabajo.Desde: 2010 “A network in a laptop”, de Lantz, Heller y McKeown, prototipado rápido para redes definidas por software. fuente
Recocido simulado
Una computadora enfría poco a poco un modelo de átomos o un diseño, aceptando a veces disposiciones peores, para hallar una buena solución a un problema de optimización difícil.
Pregunta que responde: ¿Cuál es una disposición o un calendario casi óptimo entre una cantidad astronómica de posibilidades?
Deja fuera: No garantiza la mejor respuesta, y los resultados dependen del programa de enfriamiento.
Se ejecuta en: unos 1012 FLOPS aproximado horas en una estación de trabajo para la colocación de un chip.Desde: 1983 La optimización por recocido simulado de Kirkpatrick, Gelatt y Vecchi. fuente
Computación bayesiana aproximada
Un simulador se ejecuta con muchos valores de prueba de los parámetros, y se conservan los que producen datos cercanos a los observados, lo que da una imagen de qué valores son plausibles.
Pregunta que responde: ¿Qué ajustes de un modelo complicado podrían haber producido los datos que observamos?
Deja fuera: El resultado depende de qué resúmenes de los datos se usen y de cuánto debe parecerse un ajuste para contar.
Se ejecuta en: unos 1013 FLOPS aproximado millones de ejecuciones de simulador en un clúster.Desde: 1997 Inferencia de tiempos de coalescencia a partir de secuencias de ADN mediante simulación, de Tavaré y colegas. fuente