Qual modelo de computação é "o melhor"?

41

Em 1937, Turing descreveu uma máquina de Turing. Desde então, muitos modelos de computação foram descritos na tentativa de encontrar um modelo que seja como um computador real, mas ainda simples o suficiente para projetar e analisar algoritmos.

Como resultado, temos dezenas de algoritmos para, por exemplo, o problema SORT para diferentes modelos de computação. Infelizmente, nem podemos ter certeza de que uma implementação de um algoritmo com tempo de execução O (n) em uma palavra RAM com operações de vetor de bits permitidas seja executada mais rapidamente do que uma implementação de um algoritmo com tempo de execução O (n⋅logn) em uma palavra RAM (estou falando apenas de implementações "boas", é claro).

Portanto, quero entender qual dos modelos existentes é "o melhor" para projetar algoritmos e estou procurando uma pesquisa atualizada e detalhada sobre modelos de computação, que ofereça prós e contras dos modelos e sua proximidade com a realidade.

Tatiana Starikovskaya
fonte
11
Postagens cruzadas no MathOverflow ( mathoverflow.net/questions/44558/… ), embora redirecionadas aqui.
Dave Clarke
@ Tatiana, boa pergunta, o que você quer dizer com "o melhor"? Você quer dizer um modelo com tempo de execução teórico próximo ao tempo de execução "real"?
Mohammad Al-Turkistany
8
Se você deseja modelar com precisão os tempos de execução "reais", parece que pode ser importante modelar com precisão os caches. Em particular, a computação moderna possui muitas camadas de armazenamento em cache (CPU, RAM, Disco, etc ...), com algumas camadas sendo ordens de magnitude mais lentas que outras; não está fora de questão que o tempo de execução "real" de um algoritmo seja determinado pelo número de falhas de cache. Curiosamente, ouvi dizer que uma das razões pelas quais os métodos de barreira na programação linear funcionam tão bem, apesar de suas más garantias teóricas, é porque geralmente são bastante eficientes em cache.
Mhum
4
Tanto quanto posso dizer, como diz mhum, as maiores discrepâncias dos tempos de execução previstos na palavra modelo de RAM e os tempos de execução reais geralmente surgem devido à recuperação de dados ... as variáveis ​​incorretas estão na memória em cache e o tempo de recuperação diminui caiu enormemente por causa disso. Houve várias tentativas de modelar isso com um modelo teórico de memória hierárquica, e não acredito que nenhuma dessas tentativas tenha sido muito bem-sucedida, porque os modelos acabam sendo muito complicados para trabalhar com facilidade.
Peter Shor
2
Se você possui um algoritmo que considera útil na prática e deseja vê-lo realmente usado, a melhor coisa a fazer é garantir que seja implementado ou que outra pessoa o implemente (mesmo que não seja um bom implementação suficiente para ser incorporada ao software prático). Para um estudo de caso, veja o histórico do algoritmo de compactação de dados LZW. De fato, provavelmente não há sentido em tentar entender como o cache afeta o algoritmo, a menos que seja um que as pessoas estejam interessadas em implementar; caso contrário, ninguém prestará atenção aos seus resultados.
quer

Respostas:

30

Sempre considerei o modelo padrão de RAM do Word o "melhor" no seu sentido. Todo mundo que aprendeu a programar em uma linguagem como C (ou qualquer equivalente solto como Java, etc) tem precisamente esse modelo em mente quando pensa em um computador.

Claro, às vezes você precisa de generalizações, dependendo dos regimes em que trabalha. O modelo de memória externa é importante para se ter em mente. Ele se aplica não apenas quando você trabalha com discos, mas também no entendimento (forçando você a se preocupar com) cache. Obviamente, tratá-lo com muita seriedade também pode levar a resultados sem sentido, uma vez que o modelo de memória externa pura não conta com computação. Outra generalização da palavra RAM é o paralelismo, mas estamos todos um pouco confusos no momento :)

Um algoritmo com tempo de execução certamente será executado mais rapidamente do que um com tempo de execução . É um fato matemático que o primeiro seja mais rápido para grandes :) O tamanho do seu problema pode não ser grande o suficiente para que isso importe. Como você seleciona a classificação, garanto-lhe que será muito difícil vencer a classificação radix com um algoritmo baseado em comparação para um razoável .O ( n lg n ) n nO(n)O(nlgn)nn

Uma observação final sobre algoritmos e "realidade": sempre lembre-se do que você está tentando alcançar. Quando trabalhamos em algoritmos, estamos tentando resolver os problemas mais difíceis do mercado (por exemplo, SAT em 50 variáveis ​​ou classificar um bilhão de números). Se você está tentando classificar 200 números ou resolver o SAT em 20 variáveis, não precisa de nenhum algoritmo sofisticado. É por isso que a maioria dos algoritmos na realidade é meio trivial. Isso não diz nada de ruim sobre a pesquisa algorítmica - por acaso nos interessamos por 1/1000 incomuns dos problemas reais que são difíceis ...

Mihai
fonte
Obrigado pela sua resposta. Eu quero entender, quais generalizações valem a pena adicionar à palavra RAM. Podemos descrever um modelo, que incluirá todos esses truques, como operações de vetor de bits, paralelismo, caches e ainda será simples?
Tatiana Starikovskaya
10

Não existe um modelo computacional totalmente satisfatório para analisar tristemente os algoritmos, mesmo no que se poderia considerar um cenário tradicional. Isso pressupõe que todos os dados estejam prontamente acessíveis e que o espaço de trabalho seja efetivamente ilimitado.

A máquina de Turing multi-fita é certamente teoricamente bem especificada e muitos algoritmos foram projetados e analisados ​​nesse modelo ao longo dos anos. No entanto, para alguns, isso não se relaciona suficientemente com o modo como os computadores reais funcionam para realmente ser um bom modelo a ser usado no século XXI. Por outro lado, o modelo de palavra RAM tornou-se popular e parece capturar com mais precisão o funcionamento de computadores modernos (operações em palavras e não bits, acesso constante a locais de memória). No entanto, existem aspectos que são menos que ideais. Por exemplo, não há um modelo de RAM de uma palavra. É preciso primeiro especificar quais operações nas palavras devem ser permitidas em tempo constante. Existem muitas opções para isso, sem uma única resposta aceita. Segundo, o tamanho da palavra w é normalmente definido para aumentar com o tamanho da entrada (que é pelo menos tão rápido quanto log (n)) para permitir que qualquer item na memória seja endereçado usando um número constante de palavras. Isso significa que é preciso imaginar uma classe infinita de máquinas nas quais o algoritmo é executado ou, pior ainda, que a máquina muda à medida que você fornece mais dados. Este é um pensamento desconcertante para os mais puros entre meus alunos, pelo menos. Finalmente, você obtém resultados surpreendentes de complexidade com o modelo de palavra-RAM, que pode não corresponder àqueles que aprendemos quando estudante. Por exemplo, a multiplicação de dois números de n bits é o tempo O (n) neste modelo e a simples leitura de uma sequência de n bits é uma operação de tempo sublinear de repente. Isso significa que é preciso imaginar uma classe infinita de máquinas nas quais o algoritmo é executado ou, pior ainda, que a máquina muda à medida que você fornece mais dados. Este é um pensamento desconcertante para os mais puros entre meus alunos, pelo menos. Finalmente, você obtém resultados surpreendentes de complexidade com o modelo de palavra-RAM, que pode não corresponder àqueles que aprendemos quando estudante. Por exemplo, a multiplicação de dois números de n bits é o tempo O (n) neste modelo e a simples leitura de uma sequência de n bits é uma operação de tempo sublinear de repente. Isso significa que é preciso imaginar uma classe infinita de máquinas nas quais o algoritmo é executado ou, pior ainda, que a máquina muda à medida que você fornece mais dados. Este é um pensamento desconcertante para os mais puros entre meus alunos, pelo menos. Finalmente, você obtém resultados surpreendentes de complexidade com o modelo de palavra-RAM, que pode não corresponder àqueles que aprendemos quando estudante. Por exemplo, a multiplicação de dois números de n bits é o tempo O (n) neste modelo e a simples leitura de uma sequência de n bits é uma operação de tempo sublinear de repente.

Dito tudo isso, se você quiser apenas saber se é provável que seu algoritmo seja executado rapidamente, será mais provável :-)

Rafael
fonte
2
Acho que se você está evitando operações aritméticas bit a bit ou modelo de palavra na tentativa de evitar o problema "a máquina cresce com o tamanho da entrada", mas ainda usando uma máquina de apontador ou RAM de custo uniforme, está se enganando: esses outros modelos têm o mesmo problema. Como eles indexam sua entrada? A resposta é: computadores reais ficam sem memória, mas, apesar disso, ainda é mais conveniente projetar algoritmos para eles, assumindo que são uma RAM (ou talvez até melhor usar um modelo que seja responsável pelos custos da hierarquia de memória) do que assumindo que eles são um DFA.
David Eppstein
4
Um modelo de RAM que Knuth discute, por exemplo, custa w tempo para procurar um endereço com w bits e da mesma forma w para adicionar dois números de w bits (é assim que ele obtém Theta (n log n) pelo tempo para multiplicar dois n números de bits em um modelo de RAM sem operações de tempo constante em palavras). É interessante como os modelos mais amplamente aceitos mudaram nos últimos 20 anos e quantos modelos simplesmente nunca mais são discutidos.
Raphael
8

Modelos são apenas modelos. Eu não iria longe demais; eles dizem algo sobre alguns aspectos de seus algoritmos, mas não toda a verdade.

Gostaria de sugerir que você simplesmente usar o modelo palavra RAM padrão em sua análise e implementar o algoritmo e ver o quão bem ele executa na prática.

(Na verdade, apenas implementar seu algoritmo sem nunca executá-lo já diz muito sobre ele ... Por um lado, ele é comprovadamente implementável.)

Jukka Suomela
fonte
3
Bem, eu tenho duas objeções. Primeiro, não há muitos teóricos que implementem algoritmos e, no entanto, devemos compará-los de alguma forma. Em segundo lugar, quero entender quais recursos de um computador podemos adicionar a um modelo, sem perder sua simplicidade.
Tatiana Starikovskaya
11
A solução proposta por David Johnson para isso é fazer com que mais pessoas implementem algoritmos - ele iniciou o ALENEX e os Desafios DIMACS para resolver isso. Eu tenho alguma experiência com isso também. Com Ken Clarkson, desenvolvi um algoritmo de casco convexo randomizado que achamos que funcionaria bem na prática. Clarkson teve um aluno de verão no Bell Labs implementá-lo. Com base na promessa dessa implementação, as idéias foram trabalhadas no programa qhull (escrito no Geometry Center), mas com algumas acelerações heurísticas, o que significa que o algoritmo não tem mais uma garantia teórica de que ele é executado rapidamente.
quer
5

Se sua tarefa computacional é mais sobre mover dados do que executar operações (aritméticas) (os conjuntos de dados são enormes para que nem se encaixem na memória principal), então o modelo de E / S (introduzido por Aggarwal e Vitter em 1988 ) pode ser muito preciso. Para tarefas como permutar uma grande variedade de elementos na memória principal, pode ajudar a usar os algoritmos que são ideais para E / S (em uma implementação cuidadosa).

Para computadores modernos com vários núcleos, a variante paralela introduzida por Arge, Goodrich, Nelson e Sitchinava em 2008 pode ser um modelo preciso.

Riko Jacob
fonte
5

Se você quer dizer "o melhor" modelo computacional para tornar sua vida mais complicada, pode usar a máquina de turing universal de dois estados e três símbolos da Wolfram.

PROS : nenhum, exceto a sensação de andar na linha tênue entre razão e loucura;

CONTRAS : toneladas ...

:-D (apenas uma piada, eu basicamente concordo com as respostas anteriores ...)

Marzio De Biasi
fonte
1

Em uma nota mais teórica: O artigo Modelos teóricos finais de nanocomputadores argumenta que o modelo de malha 3D reversível é o modelo físico ideal de computação, no sentido de que nenhum outro modelo físico poderia ser assintoticamente mais rápido. Considerações físicas como a velocidade da luz, o princípio de Landauer e o limite de Bekenstein são discutidas.

Para citar o resumo:

Descobrimos que, usando a tecnologia atual, uma máquina reversível contendo apenas algumas centenas de camadas de circuitos poderia superar qualquer máquina existente e que um computador reversível baseado em nanotecnologia precisaria apenas de alguns mícrons para superar qualquer tecnologia irreversível possível.

Argumentamos que uma implementação de silicone da malha 3D reversível pode ser valiosa hoje para acelerar certos cálculos científicos e de engenharia, e propomos que o modelo se torne um foco de estudos futuros na teoria dos algoritmos paralelos para uma ampla gama de problemas.

user76284
fonte