¿Qué modelo de cálculo es "el mejor"?

41

En 1937, Turing describió una máquina de Turing. Desde entonces, se han descrito muchos modelos de computación en un intento de encontrar un modelo que sea como una computadora real pero que sea lo suficientemente simple como para diseñar y analizar algoritmos.

Como resultado, tenemos una docena de algoritmos para, por ejemplo, SORT-problem para diferentes modelos de computación. Desafortunadamente, ni siquiera podemos estar seguros de que una implementación de un algoritmo con tiempo de ejecución O (n) en una palabra RAM con operaciones de vector de bits permitidas se ejecutará más rápido que una implementación de un algoritmo con tiempo de ejecución O (n⋅logn) en una palabra RAM (estoy hablando solo de implementaciones "buenas", por supuesto).

Por lo tanto, quiero entender cuál de los modelos existentes es "el mejor" para diseñar algoritmos y estoy buscando una encuesta actualizada y detallada sobre modelos de computación, que ofrezca ventajas y desventajas de los modelos y su cercanía a la realidad.

Tatiana Starikovskaya
fuente
1
Publicación cruzada en MathOverflow ( mathoverflow.net/questions/44558/… ), aunque redirigido aquí.
Dave Clarke
@Tatiana, buena pregunta, ¿qué quieres decir con "el mejor"? ¿Te refieres a un modelo con tiempo de ejecución teórico que está cerca del tiempo de ejecución "real"?
Mohammad Al-Turkistany
8
Si está buscando modelar con precisión tiempos de ejecución "reales", entonces parece que puede ser importante modelar con precisión los cachés. En particular, la informática moderna tiene muchas capas de almacenamiento en caché (CPU, RAM, disco, etc.), y algunas capas son de un orden de magnitud más lento que otras; no está descartado que el tiempo de ejecución "real" de un algoritmo se determine por el número de errores de caché. Como anécdota, he escuchado que una de las razones por las que los métodos de barrera en la programación lineal funcionan tan bien a pesar de sus pobres garantías teóricas es porque a menudo son bastante eficientes en caché.
mhum
44
Por lo que puedo decir, como dice mhum, las mayores discrepancias de los tiempos de ejecución pronosticados en el modelo RAM de la palabra y los tiempos de ejecución reales generalmente surgen debido a la recuperación de datos ... las variables incorrectas están en la memoria caché y el tiempo de recuperación se ralentiza abajo enormemente por esto. Ha habido varios intentos de modelar esto con un modelo teórico de memoria jerárquica, y no creo que ninguno de estos intentos haya tenido mucho éxito, porque los modelos terminan siendo demasiado complicados para trabajarlos fácilmente.
Peter Shor el
2
Si tiene un algoritmo que cree que podría ser útil en la práctica, y desea verlo realmente utilizado, lo mejor que puede hacer para garantizar esto es implementarlo o hacer que alguien más lo implemente (incluso si no es un buen implementación suficiente para ser incorporada en software práctico). Para un estudio de caso en esto, mire la historia del algoritmo de compresión de datos LZW. De hecho, probablemente no tenga sentido tratar de imaginar cómo el almacenamiento en caché afecta el algoritmo a menos que sea algo que las personas estén interesadas en implementar; de lo contrario, nadie prestará atención a sus resultados.
Peter Shor

Respuestas:

30

Siempre he considerado que el modelo estándar de Word RAM es "el mejor" en su sentido. Todos los que aprendieron a programar en un lenguaje como C (o cualquier equivalente suelto como Java, etc.) tienen precisamente este modelo en mente cuando piensan en una computadora.

Por supuesto, a veces necesita generalizaciones dependiendo de los regímenes en los que trabaja. El modelo de memoria externa es importante a tener en cuenta. Se aplica no solo cuando trabaja con discos, sino también en la comprensión (obligando a preocuparse) de la memoria caché. Por supuesto, tratarlo demasiado en serio también puede conducir a resultados sin sentido, ya que el modelo de memoria externa pura no cuenta la computación. Otra generalización de la palabra RAM es el paralelismo, pero en este momento todos estamos un poco confundidos :)

Un algoritmo con un tiempo de ejecución ciertamente se ejecutará más rápido que uno con un tiempo de ejecución . Es un hecho matemático que el primero es más rápido para grande :) El tamaño de su problema puede simplemente no ser lo suficientemente grande como para que esto importe. Dado que menciona la clasificación, permítame asegurarle que será muy difícil superar la clasificación de radix con un algoritmo basado en comparación para un razonable .O ( n lg n ) n nO(n)O(nlgn)nn

Un comentario final sobre algoritmos y "realidad": siempre tenga en cuenta lo que está tratando de lograr. Cuando trabajamos en algoritmos, estamos tratando de resolver los problemas más difíciles que existen (por ejemplo, SAT en 50 variables, o clasificando mil millones de números). Si está intentando ordenar 200 números o resolver SAT en 20 variables, no necesita ningún algoritmo sofisticado. Es por eso que la mayoría de los algoritmos en realidad son algo triviales. Esto no dice nada malo sobre la investigación algorítmica: simplemente estamos interesados ​​en ese inusual 1/1000 de los problemas reales que resultan ser difíciles ...

Mihai
fuente
Gracias por tu respuesta Quiero entender qué generalizaciones vale la pena agregar a la palabra RAM. ¿Podemos describir un modelo, que incluirá todos estos trucos como operaciones de vectores de bits, paralelismo, cachés, y aún así ser simple?
Tatiana Starikovskaya el
10

No existe un modelo computacional totalmente satisfactorio para analizar los algoritmos con tristeza, incluso en lo que se podría considerar una configuración tradicional. Eso supone que todos los datos sean fácilmente accesibles y que el espacio de trabajo sea efectivamente ilimitado.

La máquina de Turing multicinta, sin duda, está teóricamente bien especificada y muchos algoritmos han sido diseñados y analizados en este modelo a lo largo de los años. Sin embargo, para algunos no se relaciona lo suficiente con la forma en que funcionan las computadoras reales para ser realmente un buen modelo para usar en el siglo XXI. Por otro lado, el modelo de palabra RAM se ha vuelto popular y parece capturar con mayor precisión el funcionamiento de las computadoras modernas (operaciones en palabras, no bits, acceso de tiempo constante a ubicaciones de memoria). Sin embargo, hay aspectos que son menos que ideales. Por ejemplo, no hay una sola palabra modelo de RAM. Primero hay que especificar qué operaciones en las palabras se permitirán en tiempo constante. Hay muchas opciones para esto sin una respuesta única aceptada. Segundo, el tamaño de palabra w normalmente está configurado para crecer con el tamaño de entrada (que es al menos tan rápido como log (n)) para permitir que cualquier elemento en la memoria se aborde utilizando un número constante de palabras. Esto significa que uno tiene que imaginar una clase infinita de máquinas en las que se ejecuta su algoritmo o, lo que es peor, que la máquina cambia a medida que le proporciona más datos. Este es un pensamiento desconcertante para los más puros entre mis alumnos al menos. Finalmente, obtienes resultados de complejidad algo sorprendentes con el modelo de palabra RAM que podría no coincidir con aquellos que aprendes como estudiante. Por ejemplo, la multiplicación de dos números de n bits es O (n) tiempo en este modelo y simplemente leer en una cadena de n bits es una operación de tiempo sublineal de repente. Esto significa que uno tiene que imaginar una clase infinita de máquinas en las que se ejecuta su algoritmo o, lo que es peor, que la máquina cambia a medida que le proporciona más datos. Este es un pensamiento desconcertante para los más puros entre mis alumnos al menos. Finalmente, obtienes resultados de complejidad algo sorprendentes con el modelo de palabra RAM que podría no coincidir con aquellos que aprendes como estudiante. Por ejemplo, la multiplicación de dos números de n bits es O (n) tiempo en este modelo y simplemente leer en una cadena de n bits es una operación de tiempo sublineal de repente. Esto significa que uno tiene que imaginar una clase infinita de máquinas en las que se ejecuta su algoritmo o, lo que es peor, que la máquina cambia a medida que le proporciona más datos. Este es un pensamiento desconcertante para los más puros entre mis alumnos al menos. Finalmente, obtienes resultados de complejidad algo sorprendentes con el modelo de palabra RAM que podría no coincidir con aquellos que aprendes como estudiante. Por ejemplo, la multiplicación de dos números de n bits es O (n) tiempo en este modelo y simplemente leer en una cadena de n bits es una operación de tiempo sublineal de repente.

Habiendo dicho todo eso, si solo quiere saber si su algoritmo es probable que se ejecute rápidamente, lo más probable es que :-)

Rafael
fuente
2
Creo que si está evitando operaciones aritméticas a nivel de bits o de modelo de palabras en un intento de evitar el problema de "la máquina crece con el tamaño de entrada", pero todavía está usando una RAM o un puntero de costo uniforme, entonces se está engañando a sí mismo: esos otros modelos tienen el mismo problema. ¿Cómo indexan sus aportaciones? La respuesta es: las computadoras reales se quedan sin memoria, pero a pesar de eso, es aún más conveniente diseñar algoritmos para ellos suponiendo que son una RAM (o tal vez incluso mejor usar un modelo que tenga en cuenta los costos de la jerarquía de memoria) que asumir que son un DFA
David Eppstein el
44
Un modelo de RAM que Knuth analiza, por ejemplo, cuesta w tiempo para buscar una dirección con w bits y, de manera similar, w tiempo para agregar dos números w bit (así es como obtiene Theta (n log n) por el tiempo para multiplicar dos n -bits en un modelo de RAM sin ninguna operación de tiempo constante en palabras). Es interesante cómo los modelos más aceptados han cambiado en los últimos 20 años y cuántos modelos ya nunca más se discuten.
Raphael el
8

Los modelos son solo modelos. No lo empujaría demasiado lejos; Dicen algo sobre algunos aspectos de sus algoritmos, pero no toda la verdad.

Sugeriría que simplemente use el modelo de palabra estándar RAM en su análisis e implemente el algoritmo y vea qué tan bien funciona en la práctica.

(En realidad, solo implementando su algoritmo sin ejecutarlo ya le dice mucho sobre él ... Por un lado, es demostrablemente implementable).

Jukka Suomela
fuente
3
Bueno, tengo dos objeciones. Primero, no muchos teóricos implementan algoritmos y, sin embargo, debemos compararlos de alguna manera. En segundo lugar, quiero entender qué características de una computadora podemos agregar a un modelo sin perder su simplicidad.
Tatiana Starikovskaya
11
La solución propuesta de David Johnson para esto es hacer que más personas implementen algoritmos: comenzó ALENEX y los desafíos DIMACS para abordar esto. Tengo algo de experiencia con esto también. Con Ken Clarkson, ideé un algoritmo aleatorio de casco convexo que pensamos que funcionaría bien en la práctica. Clarkson hizo que un estudiante de verano de Bell Labs lo implementara. Basado en la promesa de esta implementación, las ideas se trabajaron en el programa qhull (escrito en el Centro de Geometría), pero con algunas aceleraciones heurísticas, eso significa que el algoritmo ya no tiene una garantía teórica de que se ejecute rápidamente.
Peter Shor el
5

Si su tarea computacional se trata más de mover datos que de realizar operaciones (aritméticas), (los conjuntos de datos son enormes para que ni siquiera encajen en la memoria principal), entonces el modelo de E / S (introducido por Aggarwal y Vitter en 1988 ) Puede ser muy preciso. Para tareas como permutar una gran variedad de elementos en la memoria principal, puede ser útil usar los algoritmos que son óptimos para E / S (en una implementación cuidadosa).

Para las computadoras multinúcleo modernas, la variante paralela introducida por Arge, Goodrich, Nelson y Sitchinava en 2008 puede ser un modelo preciso.

Riko Jacob
fuente
5

Si te refieres al "mejor" modelo computacional para hacer tu vida más complicada, entonces puedes usar la máquina de turing universal de 2 estados y 3 símbolos de Wolfram.

PROS : ninguno excepto la sensación de caminar por la delgada línea entre la razón y la locura;

CONTRAS : toneladas ...

:-D (solo una broma, básicamente estoy de acuerdo con las respuestas anteriores ...)

Marzio De Biasi
fuente
1

En una nota más teórica: el artículo Los modelos teóricos finales de nanocomputadoras argumentan que el modelo de malla 3D reversible es el modelo físico óptimo de computación, en el sentido de que ningún otro modelo físico podría ser asintóticamente más rápido. Se discuten consideraciones físicas como la velocidad de la luz, el principio de Landauer y el límite de Bekenstein .

Para citar del resumen:

Encontramos que usando la tecnología actual, una máquina reversible que contiene solo unos pocos cientos de capas de circuitos podría superar a cualquier máquina existente, y que una computadora reversible basada en nanotecnología solo necesitaría unos pocos micrones de ancho para superar cualquier posible tecnología irreversible.

Argumentamos que una implementación de silicio de la malla 3D reversible podría ser valiosa hoy para acelerar ciertos cálculos científicos y de ingeniería, y proponemos que el modelo se convierta en un foco de estudio futuro en la teoría de algoritmos paralelos para una amplia gama de problemas.

usuario76284
fuente