Aceleração de avanços algorítmicos vs. hardware

14

Lembro-me de ver um estudo ou artigo há um tempo atrás, alegando que a maior parte da aceleração observada em programas de computador nas últimas décadas é de algoritmos melhores e não de hardware mais rápido. Alguém conhece o estudo ou artigo?

John
fonte
8
Provavelmente, um ajuste melhor para o cs.stackexchange.
Yuval Filmus 11/10
há de fato uma mudança grande de paradigma dentro de poucos lei moores anos WRT, velocidades de clock, e paralelismo e que foi coberta em muitos artigos / papers ....
vzn

Respostas:

8

essa é uma pergunta involuntariamente complexa. essa ideia de que os ganhos de software ultrapassaram os ganhos de hardware está aparentemente enraizada em um relatório real do governo, mas (como sua pergunta indica) possivelmente se aproximando de um status menor de lenda urbana devido a ser mal interpretado ou mal interpretado. as manchetes de resumo / trechos de sons não correspondem realmente ao argumento real apresentado no relatório.

veja [1] ou [2] quais estados

Um relatório de um grupo independente de consultores de ciência e tecnologia da Casa Branca, publicado em dezembro passado, citou pesquisas que mostram que os ganhos de desempenho nas tarefas de computação resultantes de melhorias nos algoritmos de software geralmente superam os ganhos atribuíveis aos processadores mais rápidos.
...
Mas o relatório consultivo da Casa Branca citou pesquisas, incluindo um estudo de progresso em um período de 15 anos em uma tarefa de planejamento de produção de referência. Nesse período, a velocidade de conclusão dos cálculos aumentou em um fator de 43 milhões. Do total, um fator de aproximadamente 1.000 foi atribuído a velocidades mais rápidas do processador, de acordo com a pesquisa de Martin Grotschel, cientista e matemático alemão. No entanto, um fator de 43.000 ocorreu devido a melhorias na eficiência dos algoritmos de software.

mas a questão do software versus hardware está muito longe dessa simplificação unidimensional, muito mais complexa, e o blog Lohrs tem mais precisão - software e hardware formam uma espécie de fusão simbiótica yin-yang e ambos avançaram muito significativamente, mesmo de maneira impressionante. as décadas.

advertência / cópia fina: não se pode obter ganhos individuais em algoritmos de software específicos, que em alguns casos foram muito substanciais, e generalizar isso em todos os algoritmos.

a cotação real do relatório está na página 71:

Ainda mais notável - e ainda menos amplamente compreendido - é que, em muitas áreas, os ganhos de desempenho devido a melhorias nos algoritmos excederam enormemente até os dramáticos ganhos de desempenho devido ao aumento da velocidade do processador. Os algoritmos que usamos hoje para reconhecimento de fala, tradução de linguagem natural, xadrez e planejamento logístico evoluíram notavelmente na última década. É difícil quantificar a melhoria, no entanto, porque ela se refere tanto à qualidade quanto ao tempo de execução.

Portanto, este relatório do governo é altamente pesquisado e polido, a alegação básica de ganhos massivos devido aos avanços teóricos do software em algumas áreas está correta e está promovendo a pesquisa (teórica / algorítmica) parcialmente nessa base.

no entanto, existem vários outros fenômenos / tendências / mudanças fundamentais novos / recentes / recentes / recentes nos últimos anos ou o que Intels Grove chama de "pontos de inflexão" que estão ocorrendo no design de hardware versus software. também conhecido como "gamechangers":

  • o aumento da supercomputação "Exascale" pode não ser tão facilmente alcançado quanto o "Petascale" devido a restrições de escala de hardware
  • as velocidades do relógio, um dos principais impulsionadores dos ganhos de velocidade anteriores, atingiram o pico (em parte devido a restrições de calor / resfriamento)
  • o hardware está passando por uma mudança maciça em direção a dispositivos menos intensivos em computação e mais eficientes em termos de energia, como móveis, datacenters / virtualização / nuvem etc.
  • melhorar o paralelismo em software e hardware (por exemplo, "multicore") está se tornando mais crítico para melhorias de desempenho (onde a teoria tem muito a dizer sobre como paralelizar algoritmos)

[1] skeptic.se, o progresso nos algoritmos supera o progresso no hardware

[2] O progresso do software supera o blog do NYT da lei de Moores, de Lohr

[3] RELATÓRIO AO PRESIDENTE E AO CONGRESSO QUE DESENHAM UM FUTURO DIGITAL: PESQUISA E DESENVOLVIMENTO FINANCIADOS FEDERALMENTE EM TECNOLOGIA DE REDE E INFORMAÇÃO Dezembro de 2010

vzn
fonte
termo aditivo. provavelmente existem alguns bons exemplos de algoritmos importantes que não avançaram na eficiência das implementações ao longo das décadas. Ideias? uma área candidata pode ser algoritmos matriciais que não são paralelizáveis ​​ou outros algoritmos que parecem inerentemente não-paralelizáveis ​​... também, alguns algoritmos sofreram melhorias teóricas na complexidade de limites inferiores, mas os algoritmos não são realmente implementados ou não são viáveis ​​para tarefas típicas entradas de tamanho etc ... por exemplo, multiplicação de matrizes?
vzn
1
Esta é uma ótima resposta - cheia de detalhes, nuances e discussões qualificadas!
Joshua Grochow