Matemática e computação

Experimentos com matrizes aleatórias

Grandes matrizes preenchidas com números aleatórios, diagonalizadas repetidas vezes para estudar a estatística de seus autovalores.

Pergunta que responde: Em que padrão os autovalores de uma matriz aleatória se acomodam, e ele coincide com o de outras áreas da matemática e da física?

Deixa de fora: Só amostra um cantinho minúsculo de um espaço infinito de matrizes possíveis.

Roda em: cerca de 10¹² FLOPS aproximado um cluster universitário gerando e diagonalizando muitas matrizes grandesDesde: 1955 O trabalho pioneiro de Wigner sobre a estatística dos autovalores de matrizes aleatórias

Experimentos com grafos aleatórios

Grafos gerados por uma regra aleatória, nó a nó ou aresta a aresta, para ver quais propriedades, como conectividade ou agrupamento, aparecem tipicamente.

Pergunta que responde: Como é uma rede “típica” sob esta regra de adição de nós e arestas?

Deixa de fora: As redes do mundo real raramente são tão limpas quanto a regra que gera o modelo.

Roda em: cerca de 10¹⁰ FLOPS aproximado roda em um desktop para grafos de até milhões de nósDesde: 1959 O modelo de grafo aleatório de Erdős e Rényi

Simulação de percolação

Uma rede com sítios ou ligações abertos ao acaso, observada até o ponto em que um caminho conectado de repente atravessa o sistema todo.

Pergunta que responde: Em que densidade uma rede aleatória de repente se torna conexa de ponta a ponta?

Deixa de fora: Redes idealizadas se comportam de forma mais limpa do que qualquer material poroso ou rede real.

Roda em: cerca de 10¹⁰ FLOPS aproximado um computador desktop para grandes varreduras de redeDesde: 1957 A introdução da teoria da percolação por Broadbent e Hammersley

Buscas de matemática experimental

Busca numérica por força bruta de padrões, contraexemplos ou relações exatas entre números, levada muito além do que se poderia conferir à mão.

Pergunta que responde: Esta conjectura é verdadeira para todos os casos que alguém consegue conferir, e surge algum padrão?

Deixa de fora: Nenhuma quantidade de casos conferidos é uma prova, por mais que se verifique que valem.

Roda em: cerca de 10¹¹ FLOPS aproximado um cluster universitário rodando por dias em uma única buscaDesde: 1963 já em 1963, buscas por computador de relações inteiras e padrões de números primos

Estimativa de constantes por Monte Carlo

Amostragem aleatória usada para estimar uma constante ou integral matemática, como espalhar pontos para estimar uma área, como exercício e não como modelo físico.

Pergunta que responde: Com que precisão a amostragem aleatória cega, sozinha, consegue determinar uma quantidade matemática exata?

Deixa de fora: Converge muito mais devagar que quase qualquer método numérico mais sofisticado.

Roda em: cerca de 10⁹ FLOPS aproximado roda em um laptop em segundos a minutosDesde: 1946 A ideia de Ulam, de 1946; von Neumann propôs uma versão para computador eletrônico em março de 1947, e o método foi publicado pela primeira vez em 1949 fonteNa árvore de simulações: Método de Monte Carlo

Executar o modelo interativo

Buscas computacionais em teoria dos números

Números grandes testados quanto à primalidade, fatorados ou examinados em busca de propriedades especiais, como os números perfeitos, com algoritmos executados em grande escala e não à mão.

Pergunta que responde: Esse número enorme tem a propriedade que procuramos, e até onde a busca consegue empurrar o recorde?

Deixa de fora: Buscas que batem recordes dizem pouco sobre números que ninguém pensou em conferir ainda.

Roda em: cerca de 10¹³ FLOPS aproximado um projeto de computação voluntária distribuída em muitas máquinas doadasDesde: 1951 O teste manual de Lucas para primos de Mersenne, rodado pela primeira vez em computador em 1951

Numérica de atratores caóticos

Um pequeno conjunto de equações não lineares integrado passo a passo para revelar a dependência sensível das condições iniciais e um atrator fractal.

Pergunta que responde: Por que um sistema determinístico simples se torna imprevisível?

Deixa de fora: O arredondamento numérico faz com que uma trajetória longa não seja uma órbita verdadeira, apenas uma que se mantém próxima de uma.

Roda em: cerca de 10³ FLOPS aproximado algumas equações, segundos em um laptop.Desde: 1963 O fluxo determinístico não periódico de Lorenz, um modelo de convecção rodado em computador. fonteNa árvore de simulações: A convecção caótica de Lorenz

Experimentos de rede não lineares

Uma cadeia de massas com molas não lineares, iniciada em um único modo e acompanhada para ver se a energia se espalha por igual, como sugeriria a termodinâmica.

Pergunta que responde: Uma cadeia não linear reparte sua energia por igual entre todos os seus movimentos?

Deixa de fora: Os resultados dependem da cadeia escolhida e do estado inicial.

Roda em: cerca de 10³ FLOPS aproximado minúsculo para os padrões modernos; o original usava algumas dezenas de massas.Desde: 1955 Os estudos de problemas não lineares de Fermi, Pasta e Ulam em um dos primeiros computadores digitais. fonte

Experimentos numéricos com sólitons

Uma equação de onda não linear resolvida em uma grade para ver pulsos se atravessarem e manterem a forma, o que ondas lineares não fazem.

Pergunta que responde: Por que algumas ondas não lineares passam umas pelas outras sem mudar?

Deixa de fora: Mostra uma família de equações, não o comportamento geral das ondas não lineares.

Roda em: cerca de 10⁴ FLOPS aproximado uma grade unidimensional, trivial hoje.Desde: 1965 A interação de sólitons num plasma sem colisões e a recorrência dos estados iniciais, de Zabusky e Kruskal. fonte

Renderização de conjuntos fractais

Uma fórmula iterada simples testada em cada ponto do plano complexo para ver se escapa, desenhando a fronteira do conjunto de pontos estáveis.

Pergunta que responde: Qual é a forma do conjunto em que uma iteração simples permanece limitada?

Deixa de fora: Os testes de escape só sugerem pertencimento, e a imagem é uma amostragem de resolução finita de um conjunto infinitamente detalhado.

Roda em: cerca de 10⁹ FLOPS aproximado zooms profundos exigem iteração com precisão estendida em milhões de pontos.Desde: 1980 Os aspectos fractais da iteração de z para lambda z(1-z), de Mandelbrot, as primeiras imagens por computador do conjunto de Mandelbrot. fonte

Criticalidade auto-organizada de pilhas de areia

Grãos jogados em uma grade que desmoronam quando a inclinação fica grande demais, gerando avalanches de todos os tamanhos sem nenhum ajuste, como modelo de como os sistemas chegam a um estado crítico.

Pergunta que responde: Por que avalanches de todos os tamanhos aparecem sem nenhum ajuste?

Deixa de fora: Se os sistemas reais compartilham a mesma escala é contestado.

Roda em: cerca de 10⁹ FLOPS aproximado longas execuções em grades grandes para ver a escala.Desde: 1987 A criticalidade auto-organizada de Bak, Tang e Wiesenfeld: uma explicação para o ruído 1/f. fonte

Cálculo dos zeros da função zeta de Riemann

Os valores da função zeta ao longo de sua linha crítica são calculados para localizar e contar seus zeros, conferindo se estão onde a hipótese diz.

Pergunta que responde: Todos os zeros não triviais da função zeta estão em uma mesma reta?

Deixa de fora: Uma verificação finita, por mais longa que seja, não pode provar que não existe um zero fora da reta além dela.

Roda em: cerca de 10¹⁸ FLOPS aproximado décadas de tempo de CPU nas maiores buscas.Desde: 1953 Os cálculos de Turing da função zeta de Riemann. fonte

Dígitos de pi por computador

Séries para pi somadas até números enormes de dígitos com aritmética exata, testando tanto o número quanto a máquina.

Pergunta que responde: Os dígitos de pi parecem aleatórios, e dá para confiar na máquina nessa escala?

Deixa de fora: Os dígitos não respondem a nenhuma questão em aberto, e as verificações só pegam erros de hardware se o método for independente.

Roda em: cerca de 10¹⁷ FLOPS aproximado meses em um servidor para centenas de trilhões de dígitos.Desde: 1950 A determinação de pi e e com mais de 2000 casas decimais no ENIAC, de Reitwiesner (publicada em 1950, reimpressa em Pi: A Source Book). fonte

Descoberta de conjecturas guiada por IA

O aprendizado de máquina em grandes tabelas de objetos matemáticos descobre quais propriedades estão ligadas, para sugerir uma conjectura que os matemáticos então tentam provar.

Pergunta que responde: Que relação ainda desconhecida entre essas grandezas matemáticas vale a pena provar?

Deixa de fora: Só sugere padrões e não prova nada por si, e algumas regularidades nos dados podem ser artefatos do modo como os dados foram produzidos.

Roda em: cerca de 10¹⁵ FLOPS aproximado dias em algumas GPUs por conjunto de dados.Desde: 2021 O trabalho de Davies e colegas sobre avançar a matemática guiando a intuição humana com IA. fonte

Busca aprendida de algoritmos e construções

Um sistema que joga ou um modelo de linguagem procura novos procedimentos ou objetos matemáticos, com um computador verificando a correção de cada candidato.

Pergunta que responde: Um programa consegue descobrir um algoritmo mais rápido ou um exemplo maior que os achados por pessoas?

Deixa de fora: Cada resultado é um único exemplo novo, e a busca cobre só os tipos de objeto que seus projetistas enquadraram como um jogo.

Roda em: cerca de 10¹⁷ FLOPS aproximado de dias a semanas em clusters de aceleradores.Desde: 2022 O AlphaTensor de Fawzi e colegas, que descobre algoritmos mais rápidos de multiplicação de matrizes com aprendizado por reforço. fonte

Verificação de modelos

Todo estado alcançável de um sistema finito, como um protocolo ou um projeto de circuito, enumerado por computador para conferir que uma propriedade vale em todos eles.

Pergunta que responde: Existe algum estado alcançável em que este projeto viole as próprias regras?

Deixa de fora: Os espaços de estados explodem além do que se pode verificar, então os projetos reais são simplificados antes.

Roda em: cerca de 10¹² FLOPS aproximado um cluster universitário esgotando um espaço de estados grande, mas limitadoDesde: 1981 A introdução da verificação de modelos por Clarke e Emerson

Busca automatizada de demonstração de teoremas

Uma busca por cadeias de inferência lógica, geradas por computador passo a passo, em busca de uma prova ou refutação de um enunciado matemático.

Pergunta que responde: Existe uma cadeia válida de passos lógicos dos axiomas a este enunciado?

Deixa de fora: Acha provas que nenhum humano escolheria e, às vezes, nenhuma ao alcance.

Roda em: cerca de 10¹¹ FLOPS aproximado um cluster universitário buscando por horas a diasDesde: 1956 o Logic Theorist, um dos primeiros programas de busca automática de provas

SAT e resolução de restrições

Milhões de combinações de valores verdadeiros ou falsos pesquisadas de forma sistemática para satisfazer um grande conjunto de restrições lógicas, usadas para programar, rotear ou verificar projetos.

Pergunta que responde: Existe alguma atribuição de valores que satisfaça todas estas restrições ao mesmo tempo?

Deixa de fora: Algumas instâncias são tão difíceis que nenhum solucionador, por melhor que seja, termina a tempo.

Roda em: cerca de 10¹¹ FLOPS aproximado de uma estação de trabalho a um cluster, conforme o tamanho do problemaDesde: 1962 o procedimento de Davis-Putnam para busca de satisfatibilidade

Modelagem de ataques criptográficos

Um código ou esquema de troca de chaves atacado milhões de vezes em simulação, por força bruta, viés estatístico ou uma fraqueza modelada, para medir quanto esforço realmente custa quebrá-lo.

Pergunta que responde: Quantas operações seriam realmente necessárias para quebrar isto, e esse número ainda é seguramente grande?

Deixa de fora: Só testa os ataques que o analista pensou em modelar, não o que ninguém descobriu ainda.

Roda em: cerca de 10¹⁴ FLOPS aproximado um cluster distribuído de muitas máquinas rodando testes de ataqueDesde: 1976 já em 1976, a análise computacional da força de cifras e de trocas de chaves

Simulação de vazamento por canais laterais

O consumo de energia, o tempo ou a emissão eletromagnética de um dispositivo modelados enquanto ele executa uma operação criptográfica, para ver o que alguém de fora poderia aprender com isso.

Pergunta que responde: Quanto da chave secreta vaza pelo comportamento físico do dispositivo, e não pela matemática?

Deixa de fora: As condições de laboratório captam sinais mais limpos do que um dispositivo real e ruidoso costuma entregar.

Roda em: cerca de 10¹⁰ FLOPS aproximado uma estação de trabalho modelando o consumo de energia ou o traço de tempo de um dispositivoDesde: 1996 A demonstração de Kocher de ataques de temporização contra implementações criptográficas

Verificação de protocolos de segurança

Cada mensagem que um atacante poderia enviar, repetir ou forjar em um protocolo de comunicação, enumerada por computador para conferir se um segredo ou uma identidade pode ser arrancado dele.

Pergunta que responde: Alguma sequência de mensagens consegue enganar esse protocolo para vazar um segredo ou aceitar uma identidade falsa?

Deixa de fora: Verifica o protocolo como foi especificado, não os atalhos que uma implementação real toma.

Roda em: cerca de 10¹¹ FLOPS aproximado de uma estação de trabalho a um cluster, conferindo o espaço de mensagens de um protocoloDesde: 1989 o modelo de Dolev-Yao, base fundamental para a verificação de protocolos

Prova assistida por computador por verificação exaustiva de casos

Um teorema reduzido a uma lista finita de casos, cada um verificado por programa, porque nenhum humano poderia conferir todos.

Pergunta que responde: Uma prova pode ser concluída por uma máquina que confere todos os casos?

Deixa de fora: A confiança passa para o programa, o hardware e o argumento de redução de casos.

Roda em: cerca de 10⁹ FLOPS aproximado cerca de mil horas em um mainframe para o original; bem menos hoje.Desde: 1977 A prova de Appel e Haken de que todo mapa plano é colorível com quatro cores, usando redutibilidade verificada por computador. fonte

Métodos numéricos validados

Cálculos feitos com limites garantidos, de modo que um resultado numérico prova um enunciado matemático, como a existência de um atrator caótico.

Pergunta que responde: Dá para provar que uma resposta calculada está correta, e não apenas provavelmente precisa?

Deixa de fora: Os limites podem explodir ao longo de tempos longos, restringindo as provas a problemas curtos ou bem-comportados.

Roda em: cerca de 10⁹ FLOPS aproximado a aritmética de intervalos multiplica o custo por um fator modesto.Desde: 2002 O solucionador rigoroso de EDOs de Tucker e o 14º problema de Smale, provando que o atrator de Lorenz existe. fonte

Enumeração de máquinas de Turing

Todo programa pequeno de uma máquina mínima executado para ver quais param e quais rodam para sempre, a fim de achar o que mais demora a parar em cada tamanho.

Pergunta que responde: Por quanto tempo um programa minúsculo pode rodar antes de parar?

Deixa de fora: A indecidibilidade significa que algumas máquinas nunca poderão ser classificadas, por mais tempo que rodem.

Roda em: cerca de 10¹⁵ FLOPS aproximado bilhões de máquinas, com provas para as que não param.Desde: 1965 Os estudos de Lin e Rado em computador sobre problemas de máquinas de Turing. fonte

Verificação estatística de modelos

Um sistema com comportamento aleatório simulado muitas vezes para estimar com confiança a probabilidade de violar uma propriedade.

Pergunta que responde: Qual a probabilidade de um sistema aleatório violar uma regra de segurança?

Deixa de fora: Execuções estatísticas dão uma probabilidade com um nível de confiança, não uma prova, e falhas raras exigem amostragem por importância.

Roda em: cerca de 10⁹ FLOPS aproximado milhares a milhões de execuções amostradas.Desde: 2002 A verificação probabilística de sistemas de eventos discretos por amostragem de aceitação, de Younes e Simmons. fonte

Fuzz testing

Um programa recebe enormes quantidades de entradas aleatórias ou mutadas para achar as que o fazem travar, simulando, na prática, um mundo hostil ou descuidado.

Pergunta que responde: Que entrada fará este software falhar?

Deixa de fora: Só encontra as falhas que as entradas aleatórias alcançam, e um programa pode passar anos sem problemas escondendo um erro atrás de um caso raro.

Roda em: cerca de 10¹⁴ FLOPS aproximado anos-máquina de tempo de CPU para uma grande base de código.Desde: 1990 O estudo empírico de Miller, Fredriksen e So sobre a confiabilidade de utilitários do UNIX. fonte

Execução simbólica

Um programa é executado com entradas desconhecidas escritas como símbolos, coletando as condições de cada caminho, e então um solucionador acha valores que seguem cada ramo.

Pergunta que responde: Que entradas fazem cada caminho deste programa rodar, e algum deles chega a um defeito?

Deixa de fora: O número de caminhos cresce exponencialmente com o tamanho do programa, então os grandes só são cobertos em parte.

Roda em: cerca de 10¹² FLOPS aproximado horas de tempo de solucionador por programa, crescendo de forma acentuada com o número de caminhos.Desde: 1976 A execução simbólica e o teste de programas, de King. fonte

Interpretação abstrata

Um programa é executado com conjuntos de valores possíveis, como intervalos, em vez de valores únicos, para provar propriedades que valem para toda entrada.

Pergunta que responde: Esse programa pode dividir por zero ou estourar o limite alguma vez, para alguma entrada?

Deixa de fora: A aproximação segura gera alarmes falsos, então as pessoas ainda precisam conferir cada aviso.

Roda em: cerca de 10¹¹ FLOPS aproximado horas em uma estação de trabalho para uma grande base de código de aviônica.Desde: 1977 A interpretação abstrata de Cousot e Cousot, um modelo unificado em reticulado para análise estática de programas. fonte

Verificação limitada de modelos

O comportamento de um projeto até um número fixo de passos é escrito como uma fórmula lógica e entregue a um solucionador de satisfatibilidade para achar qualquer caminho curto até um defeito.

Pergunta que responde: Esse circuito ou programa pode chegar a um estado de erro em um dado número de passos?

Deixa de fora: Não prova nada além do limite de passos, a menos que um argumento à parte mostre que ele basta.

Roda em: cerca de 10¹³ FLOPS aproximado horas em um servidor por propriedade.Desde: 1999 Biere, Cimatti, Clarke and Zhu's symbolic model checking without BDDs. fonte

Teste aleatório baseado em propriedades

Uma regra que deveria valer sempre é enunciada, e o computador gera muitos casos aleatórios e reduz qualquer falha a um pequeno contraexemplo.

Pergunta que responde: Esse código obedece à própria especificação em uma ampla gama de entradas?

Deixa de fora: Casos aleatórios podem nunca chegar a uma condição rara, e a propriedade escrita pode não ser a que importa.

Roda em: cerca de 10⁹ FLOPS aproximado minutos em um laptop para milhares de casos.Desde: 2000 O QuickCheck de Claessen e Hughes, uma ferramenta leve de teste aleatório de programas em Haskell. fonte

Verificação de redes neurais

Solucionadores de restrições provam que, para toda entrada em uma região, a saída de uma rede neural fica dentro de limites, em vez de testar amostras.

Pergunta que responde: Uma pequena mudança em uma entrada pode fazer a rede dar uma resposta errada?

Deixa de fora: As provas só escalam para redes pequenas, e o conjunto de perturbações que podem ser verificadas é estreito.

Roda em: cerca de 10¹³ FLOPS aproximado de horas a dias em um servidor para uma rede pequena.Desde: 2017 O Reluplex, de Katz e colegas, um solucionador SMT para verificar redes neurais profundas. fonte

Simulação de arquitetura de computadores

O pipeline, os caches e o preditor de desvios de um processador proposto, modelados instrução por instrução, para estimar a velocidade de um chip antes de ele ser construído.

Pergunta que responde: Com que rapidez este projeto de processador rodaria programas reais, antes de cortar qualquer silício?

Deixa de fora: Simplifica tanto do chip real que o silício final sempre difere um pouco do modelo.

Roda em: cerca de 10¹¹ FLOPS aproximado um cluster universitário rodando programas de referência pelo modeloDesde: 1990 já em 1990, simuladores de processador precisos por ciclo para pesquisa de arquitetura

Simulação de sistemas distribuídos e consenso

Muitos computadores modelados trocando mensagens entre si com atrasos, perdas e falhas, para testar se um algoritmo distribuído ainda chega ao mesmo acordo sobre a resposta certa.

Pergunta que responde: Esse algoritmo ainda chega ao acordo correto quando mensagens se perdem, atrasam ou nós travam?

Deixa de fora: As falhas injetadas são as que o projetista previu, não as que surgem de forma inesperada em produção.

Roda em: cerca de 10¹⁰ FLOPS aproximado um cluster que simula centenas de nós virtuaisDesde: 1978 O trabalho pioneiro de Lamport sobre ordenação e falha em sistemas distribuídos

Simulação de sistemas de armazenamento

Discos, unidades e sistemas de arquivos modelados quanto a como organizam dados, falham e se recuperam, para testar um projeto de armazenamento antes de comprar e encher unidades reais.

Pergunta que responde: Como este projeto de armazenamento se comporta e sobrevive a falhas, em uma escala cara demais para testar de verdade antes?

Deixa de fora: Os discos reais falham de modos mais bagunçados e correlacionados do que a taxa aleatória de falhas do modelo.

Roda em: cerca de 10¹⁰ FLOPS aproximado de uma estação de trabalho a um pequeno cluster, modelando um sistema de armazenamentoDesde: 1988 já em 1988, modelos de simulação da confiabilidade de matrizes de discos

Simulação do escalonador de um sistema operacional

Um fluxo de tarefas de computação modelado chegando e disputando um processador, rodado com diferentes regras de escalonamento para ver qual é a mais justa ou a mais rápida.

Pergunta que responde: Que forma de ordenar a fila de tarefas faz mais trabalho, ou é mais justa com cada tarefa?

Deixa de fora: Cargas de trabalho sintéticas raramente correspondem à mistura irregular de tarefas que uma máquina real encontra.

Roda em: cerca de 10⁹ FLOPS aproximado roda em um laptop ou estação de trabalho em segundos a minutosDesde: 1968 já em 1968, estudos de simulação de políticas de escalonamento de processadores

Busca de otimização de compiladores e programas

Um número enorme de pequenas variações de um trecho de código testadas e medidas, em busca da versão mais rápida ou mais curta que ainda faça o mesmo trabalho.

Pergunta que responde: De todas as maneiras equivalentes de escrever este pequeno trecho de código, qual é de fato a mais rápida?

Deixa de fora: Os programas encontrados às vezes são tão incomuns que não há explicação disponível de por que funcionam.

Roda em: cerca de 10¹⁰ FLOPS aproximado um cluster que busca em um grande espaço de variantes de códigoDesde: 2006 já em 2006, busca de superotimização sobre sequências curtas de instruções

Teste empírico de desempenho de algoritmos

Um algoritmo rodado milhares de vezes com entradas geradas ao acaso ou reais de tamanho crescente, medindo como seu tempo de execução realmente cresce, em vez de prová-lo no papel.

Pergunta que responde: Como o tempo de execução deste algoritmo cresce de fato na prática, com as entradas que ele realmente vai receber?

Deixa de fora: Um pior caso ausente das entradas de teste continua sem ser detectado até ocorrer.

Roda em: cerca de 10⁹ FLOPS aproximado roda em uma estação de trabalho sobre muitas entradas de teste geradasDesde: 1970 já em 1970, testes empíricos sistemáticos de tempos de execução de algoritmos

Execução de programas por modelos de linguagem

Um modelo de linguagem escreve, passo a passo, os estados intermediários ao rastrear o que um programa computaria.

Pergunta que responde: Um modelo de linguagem consegue emular a execução de código?

Deixa de fora: A saída não tem garantia de estar correta, e programas longos falham.

Roda em: cerca de 10¹⁴ FLOPS aproximado Inferência por consultaDesde: 2021 Show your work: scratchpads for intermediate computation with language models (2021) fonte

Simulação de consenso em blockchain

Uma rede de nós que produzem e compartilham blocos sob atrasos, para testar como o tamanho do bloco, o tempo e os atacantes afetam a segurança e a vazão.

Pergunta que responde: Quão seguro e rápido é um blockchain sob atraso de rede e ataque?

Deixa de fora: O comportamento real dos nós e as topologias de rede são medidos só em parte.

Roda em: cerca de 10⁸ FLOPS aproximado execuções orientadas a eventos de milhares de nós.Desde: 2016 Gervais and colleagues' security and performance analysis of proof-of-work blockchains with a simulator. fonte

Simulação paralela de eventos discretos

Uma simulação de eventos no tempo é dividida entre muitos processadores, cada um avançando seu próprio relógio e voltando atrás se algo chega atrasado.

Pergunta que responde: Como uma enorme simulação orientada a eventos, como uma rede ou um campo de batalha, pode rodar rápido em muitas máquinas?

Deixa de fora: Os retrocessos podem se propagar em cascata, e o ganho de velocidade depende muito de quão estreitamente os eventos estão acoplados.

Roda em: cerca de 10¹⁴ FLOPS aproximado horas em um supercomputador para bilhões de eventos.Desde: 1985 O tempo virtual de Jefferson, o mecanismo Time Warp de sincronização otimista. fonte

Simulação de arquitetura de processadores gráficos

Os núcleos, warps e memória de um processador gráfico são modelados ciclo a ciclo, rodando programas reais para avaliar um projeto antes de construí-lo.

Pergunta que responde: Como uma mudança de projeto afetaria a velocidade de programas paralelos em um chip gráfico?

Deixa de fora: Os detalhes dos chips reais são secretos ou desconhecidos, então o modelo só se aproxima dos números de projetos existentes.

Roda em: cerca de 10¹² FLOPS aproximado de horas a dias de tempo do hospedeiro por segundo de execução simulada.Desde: 2009 Bakhoda and colleagues' analysis of CUDA workloads using a detailed GPU simulator. fonte

Simulação de sistemas acelerada por FPGA

O projeto de um chip é carregado em muitos circuitos reconfiguráveis que o executam ciclo a ciclo, em velocidades de megahertz, simulando servidores inteiros e redes deles.

Pergunta que responde: Como este processador e seu cluster vão se comportar rodando software real, antes de ser fabricado?

Deixa de fora: É muito mais lento que o chip real, e um projeto que não cabe nos circuitos não pode ser executado.

Roda em: cerca de 10¹⁵ FLOPS aproximado dias em uma nuvem de centenas de circuitos reconfiguráveis.Desde: 2018 O FireSim, de Karandikar e colegas, simulação de sistemas em escala com precisão de ciclo acelerada por FPGA na nuvem pública. fonte

Simulação de sistema completo

Um computador inteiro, com processadores, memória, discos e placas de rede, é simulado bem o bastante para dar boot em um sistema operacional sem modificações e rodar seus programas.

Pergunta que responde: Como um software real se comporta em uma máquina que ainda não existe, ou que pode ser pausada e repetida à vontade?

Deixa de fora: O tempo é aproximado por velocidade, então não dá o desempenho exato, apenas o comportamento funcional.

Roda em: cerca de 10¹¹ FLOPS aproximado quase em tempo real em um servidor por máquina simulada.Desde: 2002 O Simics, de Magnusson e colegas, uma plataforma de simulação de sistema completo. fonte

Emulação leve de redes

Dezenas ou centenas de hospedeiros e comutadores virtuais rodam software de rede real em um laptop, ligados por cabos emulados com velocidade e atraso definidos.

Pergunta que responde: Este programa de controle de rede vai funcionar numa topologia inteira antes de ser implantado?

Deixa de fora: O próprio processador do hospedeiro é compartilhado por todos os nós virtuais, então os links rápidos ficam mais lentos.

Roda em: cerca de 10¹⁰ FLOPS aproximado tempo real em uma única estação de trabalho.Desde: 2010 'A network in a laptop', de Lantz, Heller e McKeown, prototipagem rápida para redes definidas por software. fonte

Recozimento simulado

Um computador esfria devagar um modelo de átomos ou um projeto, aceitando às vezes arranjos piores, para achar uma boa solução para um problema difícil de otimização.

Pergunta que responde: Qual é um arranjo ou cronograma quase ótimo entre possibilidades astronomicamente numerosas?

Deixa de fora: Não garante a melhor resposta, e os resultados dependem do cronograma de resfriamento.

Roda em: cerca de 10¹² FLOPS aproximado horas em uma estação de trabalho para o posicionamento de um chip.Desde: 1983 A otimização por recozimento simulado, de Kirkpatrick, Gelatt e Vecchi. fonte

Computação bayesiana aproximada

Um simulador é rodado com muitos valores de teste dos parâmetros, e os que produzem dados próximos dos observados são mantidos, dando uma ideia de quais valores são plausíveis.

Pergunta que responde: Que configurações de um modelo complicado poderiam ter produzido os dados que observamos?

Deixa de fora: O resultado depende de quais resumos dos dados são usados e de quão próxima uma correspondência precisa ser para valer.

Roda em: cerca de 10¹³ FLOPS aproximado milhões de execuções de simulador em um cluster.Desde: 1997 A inferência de tempos de coalescência a partir de sequências de DNA por meio de simulação, de Tavaré e colegas. fonte