¿El progreso en los algoritmos supera al progreso en el hardware?

Un informe de 2010 al presidente y al Congreso de EE. UU. sobre los avances pasados ​​y futuros en tecnología de la información señala que:

Mientras que las mejoras en el hardware representaron un aumento de aproximadamente 1000 veces en la velocidad de cálculo durante un período de 15 años, las mejoras en los algoritmos representaron un aumento de más de 43 000 veces".

Estoy intrigado por cómo se les ocurrió esta figura. Cita una investigación de Professor Martin Grötschel of Konrad-Zuse-Zentrum für Informationstechnik Berlin, pero no pude encontrar la fuente específica.

Este informe también fue citado por el New York Times aquí , donde el título dice "El progreso del software vence a la ley de Moore" y el autor afirma que "[los hallazgos] contradicen claramente la sabiduría convencional".

De cualquier manera, la conclusión del informe parece ser que las mejoras de software representan un mayor aumento en la velocidad de cálculo que las mejoras de hardware (aparentemente en el período entre 1988 y 2003).

¿Es esto cierto? ¿Cómo lo midieron?

Solo soy escéptico ante la afirmación de que esto contradice la sabiduría convencional. De hecho, es mucho lo que esperaría de la experiencia.
@KonradRudolph Creo que el NYT se refería a las personas que usan software, no a las personas que crean software. Estoy bastante seguro de que la mayoría de los departamentos de informática obtienen el beneficio de la mejora algorítmica frente a la mejora del hardware el día después de mostrarle cómo anidar bucles for(), pero esos malditos usuarios tienen un historial de quejas de que la versión 3 es más lenta que la versión 2 a pesar de tener todas estas características nuevas y brillantes :)
@Tacroy No lo creo. Los usuarios de software no conocen la ley de Moore, no saben qué son los algoritmos y no saben a qué ritmo las computadoras se vuelven más rápidas. No tienen "sabiduría convencional" en un dominio del que no saben nada. por supuesto que podemos debatir este punto sin cesar, pero creo que el NYT se refería aquí a la opinión de expertos, ya que así suele usarse la frase "sabiduría convencional". De lo contrario, habrían dicho "creencia común" o algo similar.
En el caso de mejorar la complejidad de los algoritmos, realmente no se puede decir " aumento de X veces". Supongamos que desarrolla O (log n) para algo que solía hacerse en O (n) , el aumento de velocidad en números absolutos depende del tamaño del problema.

Respuestas (1)

Esta es una cita errónea. No proviene del informe que cita. Es una paráfrasis sin suficiente contexto.

La cita real, en contexto, es mucho menos emocionante (énfasis mío, enlace en cuestión):

En el campo de los algoritmos numéricos, sin embargo, la mejora puede cuantificarse. Aquí hay solo un ejemplo, proporcionado por el profesor Martin Grötschel de Konrad-Zuse-Zentrum für Informationstechnik Berlin.
Grötschel, experto en optimización, observa que un modelo de planificación de la producción de referenciaresuelto usando programación lineal habría tomado 82 años para resolver en 1988, usando las computadoras y los algoritmos de programación lineal de la época. Quince años después, en 2003, este mismo modelo podía resolverse en aproximadamente 1 minuto, una mejora de un factor de aproximadamente 43 millones. De esto, un factor de aproximadamente 1000 se debió a una mayor velocidad del procesador, mientras que un factor de aproximadamente 43 000 se debió a mejoras en los algoritmos. Grötschel también cita una mejora algorítmica de aproximadamente 30.000 para la programación de enteros mixtos entre 1991 y 2008.

La idea de que una subclase limitada de algoritmos (es decir, para realizar una cierta forma de modelado matemático ) puede haber mejorado no 'contradice agudamente [...] la sabiduría convencional'.

Gracias. Todavía me pregunto cómo calcularon esos números. En particular, me pregunto a qué algoritmo se refieren que se supone que salió después de 1988. También me pregunto hasta qué punto es generalizable la afirmación de que Software Progress Beats Moore's Law(del resumen en el informe original) de este ejemplo en particular.
¿El progreso en los algoritmos supera al progreso en el hardware?
RespuestasAquíPolítica de privacidad1y, 0v