A análise algorítmica por contagem de flop é obsoleta?

43

Nos meus cursos de análise numérica, aprendi a analisar a eficiência dos algoritmos contando o número de operações de ponto flutuante (flops) necessárias, em relação ao tamanho do problema. Por exemplo, no texto de Trefethen & Bau sobre Álgebra Linear Numérica, existem até imagens em 3D das contagens de flop.

Agora está na moda dizer que "os fracassos são gratuitos" porque a latência da memória para buscar qualquer coisa que não esteja no cache é muito maior do que o custo de um fracasso. Mas ainda estamos ensinando os alunos a contar falhanços, pelo menos em cursos de análise numérica. Em vez disso, deveríamos ensiná-los a contar acessos à memória? Precisamos escrever novos livros didáticos? Ou o acesso à memória é muito específico da máquina para gastar tempo? Qual será a tendência de longo prazo em termos de fracasso ou acesso à memória?

Nota: algumas das respostas abaixo parecem estar respondendo a uma pergunta diferente como "Devo reescrever obsessivamente minha implementação para salvar alguns fracassos ou melhorar o desempenho do cache?" Mas o que estou perguntando é mais parecido com " É mais útil estimar a complexidade algorítmica em termos de operações aritméticas ou de acesso à memória ?"

David Ketcheson
fonte
1
> "É mais útil estimar a complexidade algorítmica em termos de operações aritméticas ou de acesso à memória?" . Do ponto de vista prático, os sistemas embarcados ainda são limitados pela velocidade da FPU, e não pela largura de banda da memória. Portanto, mesmo que a contagem de fracassos tenha sido considerada obsoleta pelos padrões da HPC, ainda é útil para outras comunidades.
Damien

Respostas:

31

βFmaxBmaxFmaxβ>BmaxBmaxβ>Fmax

Eu acho que contar acessos à memória é obrigatório, mas também devemos pensar em:

  • Quanta memória local é necessária

  • Quanta simultaneidade possível temos

Então você pode começar a analisar algoritmos para o hardware moderno.

Matt Knepley
fonte
3
β
2
David fazendo mais de 8 anos antes.
Matt Knepley
3
Ok, então existe um modelo melhor e mais complexo (como sempre). Mas este modelo fornece uma resposta que depende da máquina. O que devemos ensinar aos alunos a usar como primeira análise?
David Ketcheson
3
O ponto é que a máquina foi reduzida para um único número, a proporção entre o pico de flops e o pico de largura de banda, assim como o algoritmo. Isto é o mais simples possível. Sem um modelo computacional, qualquer estimativa de complexidade é inútil e essa é a mais simples e realista.
precisa saber é o seguinte
1
Eu acho que você não entendeu o problema. Já temos transporte óptico que pode transportar grandes cargas. O problema é colocar isso em um chip. Você só tem tantos fios e uma taxa de clock máxima. O transporte óptico apenas aliviaria esse problema em um chip óptico.
Matt Knepley
22

O(N4)O(N)O(NlogN)O(N2)

De uma perspectiva mais ampla, acho que a análise do desempenho algorítmico deve ser "abrangente". Se estamos ensinando as pessoas a serem desenvolvedores e usuários reais de HPC, elas precisam entender quais são os custos de programação no mundo real. Os modelos de análise abstrata que temos não levam em consideração o tempo do programador. Deveríamos pensar em termos de "tempo total para solução", em vez de apenas contagens no flop e eficiência algorítmica. Não faz sentido gastar três ou quatro dias de programador para reescrever uma rotina que economiza um segundo de tempo do computador por trabalho, a menos que você esteja planejando executar alguns milhões de cálculos. Da mesma forma, o investimento de alguns dias para economizar uma ou duas horas de computação rapidamente compensa. Esse novo algoritmo pode ser incrível,

aeismail
fonte
7
O(NlogN)O(N2)
2
O(NlogN)O(N2)
9

Como outros já apontaram, a resposta depende, é claro, se o gargalo é a CPU ou a largura de banda da memória. Para muitos algoritmos que funcionam em alguns conjuntos de dados de tamanho arbitrário, o gargalo geralmente é a largura de banda da memória, pois o conjunto de dados não se encaixa no cache da CPU.

Além disso, Knuth menciona que a análise de acesso à memória tem maior probabilidade de resistir ao teste do tempo, presumivelmente porque é relativamente simples (mesmo considerando a compatibilidade com o cache) em comparação com as complexidades dos pipelines de CPU modernos e da previsão de ramificações.

Knuth usa o termo gigamems no Volume 4A do TAOCP, ao analisar BDDs. Não tenho certeza se ele o usa em volumes anteriores. Ele fez o comentário acima mencionado sobre resistir ao teste do tempo em sua Palestra anual da Árvore de Natal em 2010.

Curiosamente, você está fazendo errado, mostra que nem mesmo a análise do desempenho com base nas operações de memória é sempre direta, pois há elementos como a pressão da VM que entram em cena se os dados não se ajustam à RAM física de uma só vez.

Jason Davies
fonte
8

Como você determina os custos de um algoritmo depende de qual "nível" de computação científica você trabalha e de qual classe de problemas (restrita ou ampla) você considera.

Se você pensa em otimização de cache, isso é claramente mais relevante para, por exemplo, a implementação de pacotes de álgebra linear numérica como BLAS e bibliotecas semelhantes. Portanto, isso pertence à otimização de baixo nível, e é bom se você tiver um algoritmo fixo para um problema específico e com restrições suficientes na entrada. Por exemplo, a otimização de cache pode ser relevante para ter uma implementação rápida da iteração de gradiente conjugado, se prometer que a matriz é suficientemente esparsa.

Por outro lado, quanto mais ampla a classe de problemas, menos você pode prever na computação real (como, por exemplo, você não sabe o quão escassas serão as matrizes de entrada da sua implementação de CG). Quanto mais ampla a classe de máquinas em que seu programa for executado, menos você poderá prever na arquitetura de cache.

Além disso, em um nível mais alto de computação científica, pode ser mais relevante alterar a estrutura do problema. Por exemplo, se você gasta tempo na busca de um bom pré-condicionador para um sistema linear de equações, esse tipo de otimização geralmente supera qualquer otimização de baixo nível, porque o número de iterações é drasticamente reduzido.

Em conclusão, a otimização de cache é útil apenas se não houver mais nada a ser otimizado pelo paralelismo e redução do número assintótico de FLOPs.

Eu acho que é aconselhável adaptar a postura da ciência da computação teórica: no final, melhorar a complexidade assintótica de um algoritmo tem mais retorno do que a micro-otimização de algumas linhas de código existentes. Portanto, a contagem de FLOPs ainda é preferida.

shuhalo
fonte
"a otimização do cache é útil apenas se não houver mais nada a ser otimizado pelo paralelismo e redução do número assintótico de FLOPs". Discordo. Se você deseja calcular uma expressão grande de um grande número de números, é melhor executar uma etapa de cada vez com todos os números do que todas as etapas para cada número. Ambos têm o mesmo número de FLOPS, mas um é melhor no acesso à memória. Bônus se você selecionar o tamanho do grupo para caber no cache (ou o compilador fará isso por você). Isto é o que numexpr faz em Python: github.com/pydata/numexpr
Davidmh
6

Sempre me recusei a pensar em contar flops, acessos à memória ou o que você tiver. Esse é um conceito da década de 1960, quando o que você fez foi praticamente dado e somente como o fez foi até a otimização algorítmica. Pense em resolver um problema de elemento finito em uma malha xyz uniforme usando a eliminação gaussiana da iteração Jacobi.

Agora, você pode otimizar isso para o inferno e salvar alguns fracassos, ganhando 10% do tempo de execução. Ou você pode pensar em implementar um método multigrid e um pré-condicionador de bloco ideal, ganhando um fator de 10 em tempo de execução. É isso que devemos treinar nossos alunos a fazer - pense em quais algoritmos externos complexos você pode ganhar ao tentar encontrar um algoritmo interno melhor. Seu chefe (Keyes) tem esses slides sobre o progresso nos cálculos de MHD que tornam esse ponto bastante óbvio.

Wolfgang Bangerth
fonte
Na verdade, eu estava perguntando sobre o tipo de pensamento de alto nível que você sugere, e não a otimização de baixo nível. Que métrica você deve usar para determinar se o multigrid e seu pré-condicionador serão mais rápidos do que as alternativas?
David Ketcheson
Eu não saberia contar FLOPS manualmente ou qualquer outra instrução para algoritmos complexos que executam dezenas ou milhares de linhas de código. Pense, por exemplo, em quão complexa é a fase de análise e construção dos algoritmos AMG. Existem tantas partes desses algoritmos e todas dependem dos dados reais que você não pode prever o número de operações.
Wolfgang Bangerth
1
Acho que a princípio não entendi o que você estava dizendo, mas ainda discordo do seu argumento. Os "algoritmos externos" ainda podem (e eu diria que deveriam) ser projetados com a complexidade assintótica em mente. Certamente você não afirmaria que uma queda de um algoritmo quadrático para um algoritmo quase linear levaria, na melhor das hipóteses, a uma redução de 10% no tempo de execução; ainda, de que outra forma quantificar a complexidade assintótica do que através dos fracassos e / ou operações de memória?
Jack Poulson
7
Eu acho que essa abordagem "jogue suas mãos" para os algoritmos é uma porcaria. Você precisa simplificar a análise olhando apenas para os custos de primeira ordem e simplificando o modelo para que seja tratável, mas dizer que você não pode analisar algo como MG ou Cholesky porque é muito complicado está totalmente errado.
Matt Knepley
1
Bem, mas o que significa analisar MG ou Cholesky quando todos os FLOPs contados estão ocultos atrás de várias camadas de latência causadas por processadores com hyperthread, caches, RAM lenta, processadores multiscalares e vetorização automática? O que estou dizendo é que, dentro de um fator de 5 a 10, você não pode mais prever o tempo de execução de seus algoritmos sem cronometrar. Isso foi completamente diferente nos anos 50 e 60, quando as pessoas começaram a contar no FLOP.
Wolfgang Bangerth
1

Sim obsoleto. A análise algorítmica por flops, ou qualquer outro método, é tão útil quanto o modelo abstrato da máquina quando se considera o tamanho do problema em questão. O desempenho real depende da implementação e do hardware, e a aplicabilidade de qualquer modelo abstrato para este na realidade está diminuindo ao longo do tempo. Por exemplo, à medida que você paralela ainda mais a implementação de um algoritmo complexo, como a dinâmica molecular, aspectos diferentes tornam-se limitadores de taxa em diferentes hardwares e a análise algorítmica não tem nada a ver com as observações. Em um sentido, a única coisa importante é medir o desempenho da (s) implementação (ões) do (s) algoritmo (s) no (s) tipo (s) de hardware em questão.

Essas abstrações são úteis como uma ferramenta de aprendizado? Sim, como muitos modelos usados ​​para o ensino, eles são úteis desde que sejam colocados ao lado da compreensão das limitações do modelo. A mecânica clássica é boa desde que você aprecie que não funcionará em escalas de pequena distância ou grande velocidade ...

mabraham
fonte
-1

Não estou realmente respondendo à sua pergunta, mas mais adicionando outra variável a considerar: algo a ter em conta são os recursos da linguagem de programação. Por exemplo, o Python sortusa o algoritmo Timsort , projetado (entre outras propriedades legais) para minimizar o número de comparações, que podem ser potencialmente lentas para objetos Python. Por outro lado, comparar dois carros alegóricos em C ++ é rápido, mas trocá-los é mais caro, portanto eles usam outros algoritmos.

Outros exemplos são a alocação dinâmica de memória (trivial em uma lista Python, rápida tanto em tempo de execução quanto em tempo de desenvolvedor .append()), vs FORTRAN ou C, onde, embora possível e mais rápida quando implementada adequadamente, leva muito mais tempo de programação e cérebro. Veja Python é mais rápido que FORTRAN.

Davidmh
fonte
Isso é verdade, mas, como você diz, não responde à pergunta. Está em um tópico diferente.
David Ketcheson 28/03
Bem, em uma análise adequada, é algo a ser levado em consideração ao decidir qual algoritmo implementar.
Davidmh 28/03