La Naturaleza del Software

Google versus los médicos

2009-11-02T04:15:05Z

Yo no sabía, o al menos no era conciente, de que el exceso de paracetamol puede provocar daños al hígado, hasta que lo leí en Twitter. Hice una búsqueda en Google, y efectivamente, es así. Tras eso siempre insisto en mi familia que no abusen del paracetamol cuando tienen dolor de cabeza.

En 2006 médicos ingleses realizaron un estudio en que tomaron 26 casos de la New England Journal of Medicine, y buscaron en Google por los síntomas, al comparar los resultados del buscador con los de la revista médica, obtuvieron un diagnóstico acertado en el 58% de los casos (me gustaría saber cual es la tasa de diagnóstico de un médico, para compararlas).

La conclusión del estudio fue que a medida que más información de casos reales esté disponible en la web, los buscadores serán una herramienta más valiosa para los médicos.

Hace rato que Google está incorporando información médica a sus bases de datos, entre otras fuentes directamente de las personas, a través de Google Health.

¿Será que algún día se haga realidad la visión de George Lucas de androides médicos, como el de la imagen?

Para curar heridas, reparar huesos rotos, aplicar cuidados intensivos, o un tratamiento, puede que se logre. La mejora de los buscadores, y de sistemas de inteligencia artificial puede llegar a crear un médico robot, con capacidades de diagnóstico mejores que las de un humano ¿por qué no? ¿qué tendría eso de malo?

Creo que el valor agregado que dan los médicos humanos, y que los hace irreemplazable es la empatía, el respeto, y la compasión por sus pacientes. Lamentablemente muchos médicos actuales no se preocupan de eso, y se han convertidos en máquinas de producir dinero. Dada esa realidad, cualquier avance que permita automatizar la medicina, lo veo con buenos ojos.

La naturaleza del software, según Octavio Paz

2009-10-22T16:01:25Z

"La revelación de nuestra condición es, asimismo creación de nostros mismos. Según se ha visto, esa revelación puede darse de muchas formas e incluso no recibir formulación verbal alguna. Pero aun entonces implica una creación de aquello mismo que revela: el hombre. Nuestra condición original es, por esencia, algo que siempre esta haciéndose a sí mismo"

Así comienza Octavio Paz el capítulo "Inspiración", en su libro el "Arco y La Lira", y acudo

precisamente a el, en busca del impulso necesario para saltar el abismo, para salir de la comodidad del túnel y ver si más allá de la luz de salida que me ofrece la pantalla en blanco, puedo reencontrarme con el afán creador y así dar vida a mi primer artículo para la Naturaleza del Software. Como punto de partida nada mejor que el propio título de este blog, "La Naturaleza del Software" y ver si las revelaciones de nuestra condición, no son sino creaciones nuestras. "La programación es un arte" plantea Donald Knuth, frase agradable a nuestro ego y que nos permite soñar con ser artistas, tomar la investidura del creador y volver a repetir la historia de Prometeo, Brian Kernighan rápidamente sentencia nuestra vuelta a tierra con su cita "Controlar la complejidad es la esencia del

software", ¿Somos eso, los controladores de la complejidad? Más aún tipos como Ken Thompson, nos recuerdan lo primitivo que puede llegar a ser el hacer del software, "En caso de duda, aplica fuerza bruta". Estas contradicciones aparentes, son las fuerzas que lucha por algo que siempre se esta haciendo así mismo, el software como creación del hombre y en definitiva el hombre mismo por medio del uso de la técnología.

Sin embargo, para muchos la visión de la programación como arte, es la expiación de la culpa por no haber podido controlar la complejidad de la esencia del software y de los problemas que resuelven, la redención por haber aplicado fuerza bruta cuando las musas andaban de vacaciones y no había tiempo para esperar su regreso.

El ver la programación como una creación, de manera inconsciente nos lleva al enfoque "creacionista" con respecto a la naturaleza del software, en un principio el caos, luego seis días de arduo trabajo y trasnoches, y al final del proyecto, obtenemos ese orden maravilloso denominado universo junto al merecido premio del descanso al séptimo día. Si el universo no resultó tan ordenado, culpar al creador es de poco respeto, mal que mal, antes solo estaba el caos. ¿Y después del séptimo día?. Bueno hacemos "Mantención de Software". Controlamos la complejidad, sin fuerza bruta, pero cada día más brutos. Instalamos la idea de que existe un orden permanente. El hombre de Neanderthal, de seguro pensaba igual.

A diferencia del artesano, que utiliza sus instrumentos y materiales para servirse, el artista busca trascender más allá del lenguaje que utiliza, es alguien que se pone al servicio del lenguaje o medio de expresión y busca que este recupere su naturaleza original y lo trascienda. Es en ese contexto donde la programación es un arte, porque la naturaleza del software, es la naturaleza del hombre que transforma su medio y trasciende en sus posibilidades. Este es el sentido que le doy a la cita de Donald Knuth y en ello va la naturaleza del software.

Seducciones de la Informática

2009-10-18T16:05:01Z

Recientemente Ricardo Galli (el creador de Meneame) dió una charla muy interesante una llamada las seducciones de la informática". Les recomiendo ver el video, es bastante bueno y luego leer este apunte complementario en su blog.

Para los jóvenes que se preguntan el valor de estudiar informática, espero que este video los inspire.

Paradoja

2009-10-16T14:05:58Z

Lo malo es que hay algunos escépticos que quieren buscar soluciones de este tipo:

Tomado de la pulga snob.

Convenciones de codificación

2009-10-14T16:23:37Z

Hay convenciones que no aportan, lo que importa es ser coherente, y si adoptas una convención de código mantenerla, pero sin exagerar. No existe la convención perfecta.

Tomado de Geek and Poke

Eolas ataca de nuevo

2009-10-10T17:47:33Z

En 2005 les contaba sobre el Caso Eolas:

Eolas significa "Embedded Objects Linked Across Systems" (objetos incrustados enlazados a lo largo de sistemas +/-). Pero en gaelico significa Sabiduría.

Los muchachos de Eolas tienen una patente desde 1994 que cubre la incrustación de objetos en browsers internet.

De acuerdo a la página de tecnología de Eolas la patente cubre, "los browsers para la web que soporten tecnologías populares como componentes ActiveX, applets Java y plug-ins para navegadores".

Por supuesto una vez obtenida la patente fueron contra el pez mas grande, y las emprendieron primero contra Microsoft, ganando unos 500 millones de dolares...

Cuatro años se tomaron en Eolas para ir detrás de las otras empresas:

Es más o menos obvio que Eolas tiene en la mira a Macromedia (ahora Adobe) y a Sun. Incluso Firefox puede ser afectado. Esto es tan dañino que hasta el W3C habia decidido combatir a Eolas, solicitando la búsqueda masivas de pruebas de "prior art", todo esto con el fin de que la oficina de patentes de Estados Unidos reconsiderara la patente entregada. Pero, aunque no sabemos en que va la cosa, Microsoft decidió que definitivamente los plugins deberán ser activados explícitamente por el usuario.

No sabemos el acuerdo al que llegaron Microsoft y Eolas, pero ahora la empresa anuncia que la demanda incluye a dos patentes de Eolas: la U.S. Patent No. 5,838,906 ('906 Patent) y la U.S. Patent No. 7,599,985 ('985 Patent).

La patente '906 fue el objeto de litigio contra Microsoft en 2004 y que terminó con el resultado de 565 millones de dolares a favor de Eolas. De acuerdo a Eolas la oficina de PAtentes de Estados Unidos ha confirmado la validez de la patente '906 en tres procesos distintos, incluyendo dos nuevos exámenes, el más reciente de los cuales concluyó en febrero de 2009.

De acuerdo a Eolas, la patente '985 es una continuación de la patente '906, y permite a los sitios webs agregar aplicaciones incrustadas totalemente interactivas a su oferta en linea a través del uso de los plug-ins y AJAX (asynchronous JavaScript and XML) como técnica de desarrollo web. La patente '985 fue otorgada en octubre de 2009.

Esta vez Eolas está demandando, entre otros a: Adobe, Amazon, Go Daddy, Google, Sun Microsystems Inc. (por lo tanto a Oracle), Yahoo, y Youtube.

El diagrama de abajo corresponde a un esquema de como opera la patente '985 de octubre de 2009:

Como pueden apreciar practicamente toda la dinámica de la Web 2.0 y de Ajax está cubierta por esta patente.

Un resumen de la patente la describe así:

Un sistema que permite al usuario de un programa navegador en un computador conectado a un hipermedio abierto y distribuido, acceder y ejecutar un programa objeto incrustado. El programa objeto es incrustado en un documento hipermedia de la misma forma que los objetos de datos.

El usuario puede selecciona el programa objeto desde la pantalla. Una vez seleccionado el programa se ejecuta en el computador del usuario (cliente) o puede ejecutar en un servidor remoto o computadores remotos adicionales organizados como procesadores distribuidos.

Después de lanzar el programa objeto, el usuario es capaz de interactuar con el objeto dado que la invención provee de la comunicación entre procesos necesaria entre la aplicación el programa objeto y el programa navegador.

Esta patente fue solicitada en 2002.

Esto de las patentes de software tiene muchos paralelos con la guerra fría, y la amenaza de las armas nucleares, las potencias se armaron con patentes de modo de asegurar la destrucción mutua (ya saben, yo tengo esta patente, pero no te demando si tu no me demandas por esa otra patente que tu tienes). En general las empresas grandes tienen las patentes en su arsenal pero tienen miedo de usarlas para no desatar una apocalipsis de las patentes.

Pero no contaban con que un chico se hiciera con una patente también, es como el caso de Irán, o Corea del Norte desarrollando armas nucleares. Solo que en el caso de las patentes el chico ya ha lanzado las bombas.

Perdónalos porque no saben lo que hacen...

2009-10-10T01:55:25Z

Al parecer la frase del Evangleio de Lucas 23:34 "Padre, perdónalos porque no saben lo que hacen", sería un invento liberal, y los conservadores norteamericanos se han decidido a arreglar esto, eliminando este tipo de frases liberales de la biblia: el proyecto de La Biblia Conservadora.

La cosa es de locos, por ejemplo, al parecer las traducciones actuales de los evangelios estarían plagados de términos socialistas:

Por ejemplo, el término conservador "voluntario" es mencionado sólo una vez en la ESV (English Standard Version), sin embargo, la palabra socialista "camarada" se utiliza tres veces, "obrero(s)" se usa 13 veces, "laboraron" en 15 ocasiones, y "compañero" (como en "compañero de trabajo") se usa 55 veces.

Todo esto en forma arbitraria, sin siquiera consultar los textos desde sus fuentes originales, ¡sino que a partir de la versión King James! Y así la ignorancia sigue perpetúandose...

Las aventuras de la primera programadora

2009-10-06T03:25:51Z

Sydney Padua respondió al llamado del Día de Ada Lovelace con una caricatura, la que posteriormente convirtió en una serie (en progreso) titulada Las Emocionantes Aventuras de Lovelace y Babbage.

Traduje la primera historieta, El Origen, para el blog de dcc8090, La Cajita Feliz, les dejo el link, que lo disfruten.

Si tan sólo el 1%...

2009-10-05T00:45:58Z

Un músico compró un anuncio de un cuarto de página para una revista con circulación de un millón de ejemplares:

El músico preparó 10.000 copias de su CD anticpándose a las 10.000 órdenes que él estaba seguro que llegaría esa semana.

Repetía constantemente: "si sólo un uno por ciento de la gente que lee la revista compra mi CD... ¡eso serán 10.000 copias! ¡Y eso es sólo el uno por ciento!"
Compró 10.000 sobres acolchados y etiquetas de correo. Convirtió su garage en un gran centro de despacho de correspondencia.
Seguía diciendo, "a lo mejor podemos lograr el 10 por ciento. ¡Es son 100.000! Pero en el peor escenario, con sólo el 1%... ¡eso aún es impresionante!
La edición de la revista salió a circulación, y... nada. Se compró un número. Allí estaba su anuncio. ¡Pero las ordenes no entraban! ¿Había algo mal? No. Hizo las pruebas. Todo estaba funcionando.
En las siguiente semanas recibió cuatro ordenes. Total de CDs vendidos: CUATRO.
El músico había olvidado algo muy importante: olvido que hay un número inferior al uno por ciento.

Tomado de And if only 1% of those people, escrito por Derek Sivers

El Arte de Programar

2009-10-02T01:21:32Z

(En mi opinión hay lenguajes de programación que permiten ser más expresivos ;)

El arte de la programación

- No entiendo tu código. ¿Para qué son esas lineas?

- Epresan mis sentimientos internos

Los programadores son artistas.

Tomado de Geek and Poke.

El problema de paralelizar 3

2009-09-28T23:34:54Z

Aunque mucha gente cita el acrónimo FUD, no muchos saben que fue Gene Amdahl el que inventó este famoso acrónimo:

"FUD is the fear, uncertainty, and doubt that IBM sales people instill in the minds of potential customers who might be considering Amdahl products."
"FUD es el temor (fear), incerteza (uncertainty) y duda (doubt) que la gente de ventas de IBM instalará en las mentes de los clientes potenciales que consideren los productos Amdahl.".

En 1975 Gene Amdahl inventó el acrónimo para referirse a las prácticas de IBM que trataban de impedir el éxito de Amdahl Corporation, la empresa creada por él cuyo producto eran los computadores compatibles con IBM. Una maniobra coercitiva para impedir la fuga de los clientes a la competencia.

Actualmente el término FUD es usado para referirse a cualquier táctica que use la desinformación como arma competitiva.

Estas son las cosas anexas que me gusta encontrar cuando investigo sobre un tema.

Curiosamente hay un poquito de desinformación e incerteza está asociada a la Ley de Amdahl (en otro sentido, por cierto).

Primero, Amdahl nunca fomuló una ley, de hecho el no sabía que la llamaban así, y se enteró bastante después de su paper. (Si a alguien le interesa puede descargar su paper de 1967 desde acá).

Segundo, en su paper el no escribe la fórmula que expresamos anteriormente, eso fue introducido por comentaristas posteriores a su trabajo.

Tercero, al observar sus datos Amdahl observa que la curva estadística que se ajusta es que el desempeño es proporcional a la raiz cuadrada del costo, y cita la Ley de Grosch de 1965:

"El desempeño de un computadore incrementa con el cuadrado del costo. Si un computador A cuesta el doble de un computador B, debería esperarse que el computador A fuera cuatro veces más rápido que el computador B."

Hoy en día la Ley de Grosch se considera una evidencia histórica de las percepciones equivocada que ha tenido la ciencia de la computación (curiosamente la Ley de Moore fue formulada ese mismo año).

Finalmente, Amdahl escribió su trabajo como parte de una disputa que tenía con Daniel Slotnick, académico de la Universidad de Illinois y arquitecto del polémico super computador ILLIAC IV (una historia que merece en otra oportunidad)

La polémica

A principio de los 1960s el diseño de los computadores estaba enfrentando el límite de los rendimientos decrecientes. En ese tiempo la idea era dotar a las CPU de tantas instrucciones como fuera posible, para hacer programas lo más pequeños y eficientes en el uso de memoria. Esto, por supuesto, generaba computadores muy complejos, sobretodo en una era en que las CPUs se construían soldando transitores individuales a mano.

Una solución para problema, que se empezó a explorar en aquel tiempo, fue la sobreposición, que derivó en lo que conocemos actualmente como instruction pipelining, que permite que una CPU trabaje en pequeñas partes de varias instrucciones al mismo tiempo.

La otra solución al problema era la computación paralela: constuir un computador a partir de un número de CPUs de propósito general. La idea es que el computador se encargue de mantener ocpupadas a todas las CPUs, pidiéndole a acada una que trabaje en una pequeña parte del problema y después recolectando los resultados en la respuesta final.

Este era el contexto en que Amdahl escribe su artículo, tras una discusión con Slotnick sobre el futuro de las arquitecturas de computadores.

Es por eso que no hay que ver la Ley de Amdahl como una visión pesimista, o un intento de frenar el procesamiento masivo.

En 1996 Yuan Shi demostró que la Ley de Amdahl y la Ley de Gustafson son la misma y que la confusión se debe a un problema de formulación. De hecho hay un pre requisito muy importante para aplicar la Ley de Amdahl (o de Gustafson), y es que los programas seriales y paralelos tomen la misma cantidad de pasos de cálculo para una misma entrada.

Hay tres posibles relaciones entre la mejora de velocidad (speedup) y la cantidad de procesadores P:

Speedup < P, o mejora sublineal;
Speedup = P, o mejora lineal;
Speedup > P, o mejora super lineal.

Dado que cualquier programa parelelo práctivo debe consolidar la respuesta final en un paso serial, el porcentaje serial en la ley de Amdahl nunca es cero en la práctica. Luego, en teoría no es posible alcanzar speedups lineales o super lineales.

Pero, Yuan Shi descubrió que es posible saltarse algunas de las pre condiciones de la ley de Amdahl, y se pueden alcanzar mejoras lineales o super lineales si se arma un algoritmo inteligentemente.

De hecho propone una clase de algoritmos que se pueden alterar para conseguir velocidades superlineales. Un resultado interesante es que un algoritmo de ordenamiento (sort) de O(n²) puede ser paralelizado de forma tal que tenga una mejora super lineal (rompiendo la Ley de Amdahl), mientras que no es posible hacer esto con un algoritmo de sort de O(n lg n).

Lo que pasa es que al paralelizar ciertos algoritmos podemos alterar su estructura, de modo que para ciertos datos de entrada su desempeño será mejor que la versión serial del mismo. No voy a entrar en detalles, pueden leerlo en el paper.

Lo importante es notar que la Ley de Amdahl no puede ser usada como un argumento en contra de la paralelización masiva, porque, aunque hay un límite, y en general el desempeño es sub lineal, hay muchos problemas en que la parte serial es muy pequeña y la mejora es considerable. Los experimentos de Gustafson son una demostración de esto.

Empecé mi investigación sobre este tema inspirado por una nota en la edición de septiembre de CACM. En esta nota se cita a un investigador de Intel, Tim Mattson que nos urge a programar en paralelo: "Hemos llegado a la programación en paralelo no por causa del éxito de nuestro software, sino por la falla de nuestro hardware." En esa misma nota James Larus, investigador de Microsoft quien pide cautela cuando abordemos este tema, "la consecuencia de tener que moverse a multicore es que tenemos que imaginarnos como usar paralelismo en lugares donde necesitamos un mejor desempeño... No todo necesita ser paralelizado, ¿acaso eso hará que Word funcione más rápido?"

Y es Larus el que nos recuerda la Ley de Amdahl, porque habrá mucha presión por paralelizar aplicaciones y muchos de esos esfuerzos pueden estar mal dirigidos.

En el lado de los servidores (y del cloud computing), la paralelización funciona bastante bien, porque la clase de problemas que se pueden resolver en ese lado son paralelizables en forma casi natural. Pero si queremos mejorar el rendimiento en nuestros computadores multicore en el lado cliente, o en nuestro escritorio, nos enfrentamos a un desafío interesante.

Probablemente en muchos casos es mejor gastar el esfuerzo en mejorar un algoritmo secuencial que en tratar de paralelizarlo.

Esa es la lección que nos da la Ley de Amdahl. No basta con la voluntad y la urgencia por resolver los problemas de una forma (en este caso, paralelizar). Hay que analizar la complejidad del problema, y Amdahl con unos argumentos sencillos notó que hay un límite inherente al problema de paralelizar. Otros investigadores como Gustafson y Yuan Shi mejoraron el análisis y formularon las condiciones reales para que se aplique esta ley.

La Ley de Amhdal se puede "quebrar", cuando los problemas son "vergonzozamente paralelizables", o cuando nos encontramos con las clases de algoritmos identificados por Yuan Shi, pero en este último caso, las condiciones no siempre son fáciles de encontrar.

Este problema del parelelismo está lleno de problemas abiertos, muy interesantes, y es un área de mucha investigación de punta en estos momentos, sobretodo con mucho financiamiento de los grandes fabricantes de chips multicore.

Para finalizar les dejo, y para los que les interese, les dejo este video, en que Mark Hill presenta el impacto de la Ley de Amdahl en el diseño de los actuales y futuros procesadores multicore:

El problema de paralelizar 2

2009-09-24T00:42:23Z

Durante una hora un automovil ha recorrido la mitad de la distancia entre dos ciudades, las que se encuentran separadas por 120 Kms. No importa la velocidad que tome el auto para recorrer el resto del camino, su velocidad media siempre será menor a 120 Km/hr (sólo si la velocidad fuera infinita se podría alcanzar los 120 Km/hr).

Ese ejemplo sirve para entender la Ley de Amdahl que presenté anteriormente.

Pero supongamos que un automovil ya ha estado viajando por un tiempo a menos de 120 Km/hr. Dado suficiente tiempo y distancia para viajar, la velocidad media del auto puede eventualmente alcanzar los 120 Km/hr, no importa cuan lento ha viajado.

Este otro ejemplo es más o menos lo que dice la Ley de Gustafson.

En 1988 John Gustafson cuestionó la validez del argumento de Amdahl. En ese tiempo este investigador usaba supercomputadores en los laboratorios de alta energía Sandia Labs, y descubrió que los tiempos que medía no calzaban con lo predicho por la Ley de Amdahl.

De acuerdo a la fórmula que vimos antes, la mejora de velocidad, o speedup está dada por Speedup = 1 / (s + p / N). Donde s es el tiempo en la parte serial y p es el tiempo que toma 1 procesador en la parte paralela del problema, y N es la cantidad de procesadores.

Gustafson notó que para un valor de s entre 0,4% y 0,8% obtenía valores de speedup de 1020 ó 1016, usando un hipercubo con 1024 procesadores. Si hacen los cálculos verán que eso no se ajusta a lo predicho por la Ley de Amhdal (para s = 0,4% el valor speedup es = 1 / (0,004 + 0,996/1024) = 201,099).

Gustafson se dió cuenta que Amdahl asume que la parte paralelizable p es independiente del valor N, o sea, de la cantidad de procesadores, esto casi nunca se da, de acuerdo a Gustafson, en la práctica el tamaño del problema escala con la cantidad de procesadores.

Gustafson propuso una ley distinta para los problemas en que la parte paralela p' depende linealmente de la cantidad de procesadores N.

Scaled Speedup = N + (1 - N ) s'

Gustafson publicó su resultado en Communications of the ACM en 1988, pueden leer el artículo acá.

Las siguientes figuras resumen el argumento de Gustafson (recuerden el argumento de los automóviles para poder comprender mejor):

La figura 2a asume un modelo donde la parte paralela es independiente de la cantidad de procesadores (modelo de tamaño fijo).

La figura 2b asume que la parte paralelizable (p') del problema escala según la cantidad de procesadores (en forma lineal), si tengo 2 procesadores la parte paralelizable corre al doble de la velocidad.

Con el argumento de Gustafson la ley de Amdahl parecía destronada, y los partidarios del procesamiento paralelo masivo podían respirar tranquilos, la mejora en velocidad es proporcional a la cantidad de procesadores.

Piensen lo siguiente, supongan que tienen un proceso que puede ser trivialmente paralelizable. No es dificil imaginar ese problema, por ejemplo, multiplicar todos los elementos de una matriz A de NxM por un valor constante, por ejemplo 2.

A[i,j] = A[i,j] * 2

En este caso s = 0, p = 1, y queda claro que el speedup es N, cualquiera que sea la fórmula que usemos, la de Gustafson o la de Amdahl.

Pero fuera de estos problemas "vergonzosamente paralelizables" los otros problemas que observan el comportamiento de la ley de Gustafson son aquellos que exhiben un paralelismo escalable (los problemas trivialmente paralelizable son escalables en paralelo).

Muchos de los problemas que se ajustan mejor a la ley de Gustafson son susceptibles de ser paralelizados en forma automática, y hay compiladores que pueden detectar dependencias de los datos y generar código altamente paralelizable.

Estos problemas se dan mucho en la física, o en cálculos matemáticos sobre matrices y vectores.

Pero lo interesante es que en realidad la Ley de Gustafson y la Ley de Amdahl están emparentadas, de hecho, la ley de Gustafson es otra forma de ver la Ley de Amdahl, son leyes equivalentes. Por años esto no se comprendió muy bien, y generó malas interpretaciones.

En palabras de Yuan Shi, el investigador que descubrió la equivalencia de ambas leyes:

"En 1967, la Ley de Amhdal fue usada como un argumento en contra del procesamiento paralelo masivo. Desde 1988 la Ley de Gustafson ha sido usada para justificar el procesamiento paralelo masivo. Interesantemente, un análisis cuidadoso revela que estas dos leyes son de hecho idénticas. Los bien publicitados argumentos fueron el resultado de un malentendido sobre la naturaleza de ambas leyes".

Y sobre la naturaleza de estas leyes vamos a hablar en la tercera parte.

Filosofía y Matrix

2009-09-21T22:06:50Z

Interesante documental para acercarse a la filosofía a partir de la película The Matrix:

Filosofía en Matrix from Vajra on Vimeo.

El problema de paralelizar

2009-09-13T18:21:24Z

¿Cómo aumentar el desempeño de nuestros sistemas?

La respuesta a esta pregunta pasa por definir primero cómo medimos el desempeño de nuestros sistemas. Ya hemos visto que una mala definición de la medida de desempeño nos puede llevar a profundos errores de juicio (¿recuerdan el problema con los kilómetros por litro de bencina?).

Algo parecido pasa con el aumento de desempeño de nuestros sistemas de cómputo, debido a la disponibilidad de procesadores multicore. Desde hace un tiempo se nos viene diciendo que el truco para mejorar el desempeño de nuestros sistemas consiste en aumentar la cantidad de procesadores, y adoptar el paralelismo en el diseño del software que construimos.

Si tenemos un problema que podemos paralelizar ¿cuanto mejora el desempeño del mismo al agregar más procesadores? En otras palabras, si un problema lo resolvíamos con 1 CPU en un tiempo T, entonces al tener una CPU dualcore ¿deberíamos resolverlo en T/2?

Sabemos que no es así. Todos los que tenemos acceso a computadores multicore hemos notado que las cosas no mejoran tanto en realidad.

Claro, mucho de nuestro software aún opera en forma secuencial. Pero ¿cuanto se gana en general en un proceso si aumentamos la cantidad de cores? ¿Hay algún límite a nuestra capacidad de paralelizar, o el procesamiento paralelo promete un promisorio futuro de progreso permanente en nuestras capacidades de cómputo?

La respuesta les va a sorprender, y fue deducida por Gene Amdahl en 1967.

La Ley de Amhdal

En 1967 Amdahl propuso la siguiente observación: "la mejora obtenida en el rendimiento de un sistema debido a la alteración de uno de sus componentes está limitada por la fracción de tiempo que se utiliza dicho componente".

En términos simples: "es el algoritmo el que decide la mejora de velocidad, no el número de procesadores" [1].

Si del tiempo total de un sistema una proporción P del mismo se puede paralelizar, y esta parte se puede acelerar en un factor S, entonces la mejora total obtenida sera: 1 / ((1-P)+P/S) [2].

Es fácil ver que si S tiende a infinito, la mejora tiende a 1/(1-P).

Por ejemplo, supongamos que tenemos un problema y que un 30% del algoritmo puede ser paralelizado, mientras el 70% restante sigue siendo secuencial, la ley de Amhdal dice que al paralelizar al máximo el programa la nueva versión será 1/(1 -0.30) = 1.4285 veces más rápida que la versión no paralelizada.

La ley de Amhdal sigue un patrón de rendimientos decrecientes, si graficamos esta ley obtenemos lo siguiente:

Hay que hacer notar que esta ley sólo considera el efecto de agregar más procesadores, si además agregamos el acceso al bus de datos, la sincronización y otros factores, el efecto es mayor.

La falsa esperanza de la Ley de Moore

Por años muchos desarrolladores de software han descansado en la reconfortante promesa de la Ley de Moore, que dice que aproximadamente cada 18 meses se duplica el número de transistores en un circuito integrado.

Una esperanza expresada en la forma de un mito, de acuerdo a Alan Kay[3]: "El mito de que no importa cual sea tu arquitectura de proceso, la Ley de Moore se encargará de todo".

Si los procesadores aumentan su capacidad cada 18 meses, entonces la velocidad de los mismos se duplica también, ¿no es cierto?

Pero la velocidad de los procesadores depende de la frecuencia del reloj interno que estos usan. El problema que al aumentar la velocidad del reloj aparecen problemas técnicos complejos (a mayor velocidad aumenta la disipación de color, y se pierde la sincronía de los datos). Para solventar estos problemas los diseñadores de microprocesadores han decidido adoptar otras estrategias. El desarrollo de los procesadores multi core es una consecuencia de estas limitaciones técnicas.

La idea es que se puede obtener un mejor desempeño paralelizando tareas, sin tener que aumentar la velocidad del reloj del procesador. Con esto los desarrolladores de procesadores pueden seguir aprovechando la Ley de Moore, construyendo cada 18 meses procesadores con mayor capacidad de procesamiento.

El problema es que antes los desarrolladores de software aprovechábamos la mayor velocidad de los procesadores para compensar los problemas de desempeño de nuestros algoritmos o diseños.

Con frecuencias de reloj que se mantienen casi iguales durante el tiempo, ya no podemos esperar ayuda de la Ley de Moore, la esperanza se derrumba.

La propuesta que viene desde el hardware es simple: paralelizar.

¡Cómo si fuera tan sencillo!

La Ley de Amhdal nos dice que no importa la cantidad de procesadores (o cores) con que dispongamos, la ganancia está limitada por aquella parte del algoritmo que no se puede paralelizar.

Esto nos da otra perspectiva sobre la supuesta crisis del multicore.

Ahora disponemos de más procesadores, pero como hemos visto, contar con más núcleos en nuestros procesadores tiene un límite.

Se está investigando profusamente sobre cómo usar los multicore que nos entregan estos procesadores nuevos, hay detrás de esto motivaciones económicas, de negocio. Compañías como Intel están financiando programas de investigación que permitan aprovechar las nuevas capacidad de paralelización con que contamos.

Pero como hemos visto, las verdaderas ganancias están por otro lado: crear mejores algoritmos.

El desafío, como siempre, está en el lado del software, no del hardware.

Referencias:

[1] Wikipedia: La ley de Amhdal.

[2] Deducción de la Ley de Amhdal.

[3] A conversation with Alan Kay.

¿Qué es Agilidad?

2009-09-12T23:51:54Z

La agilidad se define por la siguiente ecuación vectorial:

Agilidad = Flexibilidad + Rapidez