Sobre la computación paralela, la Ley de Moore, y Snow Leopard

Segunda versión del artículo, en la que se añade el impacto que el cambio a procesadores multinúcleo puede tener para Microsoft y las próximas versiones de Windows. Se puede encontrar la primera versión del artículo en la página 2.

Repasando una noticia salida en Faq-Mac, acerca de que Intel buscaba la “excelencia en el código”, me encontré con varias afirmaciones, y un comentario, que creo que merece la pena comentar, para entender mejor qué es la Ley de Moore, qué tiene que ver con la potencia de cálculo y la computación paralela, y si vamos a vernos en problemas por no poder aumentar la potencia de cálculo disponible.

Sobre la Ley de Moore

En primer lugar, vamos con el comentario sobre el artículo en sí. En el se afirma que:

Para no infringir la Ley de Moore, el número de núcleos debe doblarse cada 18 meses.

La Ley de Moore no es algo que pueda infringirse. En cierto modo, es incorrecto referirse a la Ley de Moore como tal, sino que más bien habría que llamarla Observación de Moore, Relación de Moore, o algo similar. No es comparable a la Ley de Newton, por ejemplo, que liga directamente la fuerza aplicada sobre una masa dada, y la aceleración que se produce sobre la misma, porque no se trata de algo intrínseco a la fabricación de circuitos integrados.

En 1965, un ingeniero de Intel llamado Gordon E. Moore publicó un artículo en el que analizaba cuántos transistores se iban integrando por unidad de superficie desde la invención del circuito integrado, y encontró con que ese número se duplicaba cada año. A partir de ahí, extrapoló cuántos transistores podrían integrarse al mínimo coste por unidad de área en el futuro, y realizó predicciones a 10 años vista.

Gráfica original de la primera formulación de la Ley de Moore; obtenida del artículo sobre la Ley de Moore de Ars Technica.

Lo que ocurrió fue que las empresas de fabricación de circuitos integrados, que hasta ahora habían trabajado al ritmo que les permitían sus capacidades de investigación y desarrollo, fueron conscientes de cuál había sido ese ritmo, y se comenzó a utilizar esta relación para incentivar a los equipos de investigación para que fuesen capaces de proporcionar incrementos en la densidad de integración de forma que esta se duplicase aproximadamente cada doce meses, manteniendo el máximo

A partir de 1975, el propio Gordon Moore cambió el ritmo de crecimiento de forma que la duplicación se produciría cada 24 meses, porque se pensaba que la investigación estaba llegando a los límites de la física de materiales. Sin embargo, internamente en Intel se trabajaba con una tasa de duplicación cada 18 meses como objetivo… pero sobre una métrica diferente, de rendimiento, en lugar de integración.

Ajuste de las densidades de transistores de microprocesadores de Intel a la Ley de Moore. Puede verse que el ritmo de doblado cada 18 meses es más rápido que el ritmo alcanzado realmente, que es de doblado de densidad cada 24 meses. Imagen de WikiMedia Commons bajo licencia Creative Commons de Atribución.

Y es que, originalmente, el rendimiento de los microprocesadores estaba ligado al número de transistores que incorporaban, puesto que se utilizan transistores para las unidades aritméticas, los registros internos, memorias caché… cuantos más transistores se puedan incorporar en un chip, más capacidades tendrá.

Sin embargo, el rendimiento no sube linealmente con el número de transistores, puesto que para conseguir mayores rendimientos se hace necesario predecir cuál será el resultado de una instrucción de salto, para evitar tener el microprocesador parado, pero para eso es necesario poder deshacer el efecto de instrucciones que se han ejecutado a resultas de una predicción errónea… pero para eso hacen falta muchos transistores de control que no tienen una repercusión en el rendimiento tan directa como proporcionar múltiples unidades de ejecución.

De modo que el ritmo de aumento de rendimiento observado es inferior al ritmo extrapolado a partir de la Relación de Moore revisada, que a su vez es inferior al ritmo que se suele indicar, que implicaría una duplicación cada 18 meses, y se parece más, últimamente, a una duplicación cada 24 meses.

Relación de Moore y computación paralela

Lo que hemos visto en el apartado anterior es que el rendimiento depende de forma algo indirecta del número de transistores que se puedan integrar por unidad de área. Lo que ocurre es que el rendimiento también depende de la velocidad de reloj que se pueda aplicar, y del voltaje que se aplique. Si aumenta la densidad de transistores, y se mantiene la velocidad de reloj, aumenta la densidad de energía que hay que disipar. Si se duplica cada dos años la densidad de integración, llegará el momento en que la densidad de energía dentro de un microchip fuese comparable a la densidad de energía en una central nuclear, o en el mismo sol. Y eso no nos lo podemos permitir 😉

Así que el remedio está en reducir frecuencias y voltajes, para disminuir la densidad de energía, pero seguir subiendo el número de transistores… que están haciendo cosas independientes, de modo que la densidad de energía está más distribuida, y se pueden hacer muchas más cosas por ciclo de reloj. La cuestión es… ¿qué cosas podemos hacer en paralelo?

Por ejemplo, una suma no tiene sentido repartirla entre varios núcleos. Pero sumar vectores puede que sí. Y vectores son cada pixel de una imagen, que tiene tres o cuatro elementos por pixel: intensidad de rojo, de verde, de azul, y de transparencia.

Otro ejemplo suele ser realizar tareas similares sobre conjuntos de datos diferentes, como normalizar el histograma de múltiples imágenes, o calcular el volumen de reproducción ideal para todas las canciones de la biblioteca iTunes.

Si abrimos la aplicación Monitor de Actividad que se encuentra en /Aplicaciones/Utilidades, veremos que existen multitud de procesos funcionando simultáneamente, y que Mac OS X mantiene los dos, cuatro, u ocho núcleos con una carga de trabajo similar, para garantizar el máximo rendimiento. Si tienes instaladas las herramientas CHUD, de análisis del hardware, se puede desactivar y activar varios núcleos, y se puede ver cómo se reasignan las tareas a los núcleos restantes o a los nuevos núcleos disponibles de forma instantánea, de modo que ya existen en Mac OS X los elementos necesarios para aprovechar, siquiera rudimentariamente, múltiples núcleos.

Otra forma de aprovechar múltiples núcleos implica hacer cambios en las aplicaciones: en una aplicación como el Ajedrez de Mac OS X, la parte que gestiona la representación visual del tablero, incluyendo los movimientos de fichas, es independiente de la parte de cálculo de movimientos; pero es que el cálculo de movimientos se puede dividir también, según qué ficha se considere que va a ser la que comience la secuencia de movimientos siguiente.

De todas formas, existen problemas que no se pueden dividir, y para esos programas el rendimiento de cada núcleo se va a mantener más o menos estable… aunque es posible que pueda ir bajando en el futuro. De todas formas, esas herramientas únicas normalmente van a vivir en núcleos con menos carga de trabajo, y podrán dar respuestas en tiempos iguales o inferiores a los que necesitan hoy en día.

El rendimiento del software y la ruptura de la Relación de Moore

Hemos visto que existen tareas susceptibles de paralelización, mientras que otras no pueden paralelizarse. Y que el aumento de transistores predicho por la Relación de Moore no implica necesariamente más rendimiento por núcleo, porque las unidades individuales pueden llegar a volverse más lentas, de modo que se hace necesario encontrar otras formas de aumentar el rendimiento por núcleo.

Y para mejorar el rendimiento por núcleo, posiblemente haya que volver a viejas técnicas de optimización:

1. Medir el rendimiento de nuestros algoritmos.
2. Investigar nuestros algoritmos para encontrar alternativas más rápidas.
3. Acercarnos más a la máquina para aumentar el rendimiento.

Medir el rendimiento de algoritmos

El primer punto es fundamental: necesitamos poder medir de forma fiable el rendimiento de nuestros algoritmos. Y no basta con medidas subjetivas —aunque estas también son importantes—, sino con medidas utilizando la máxima fiabilidad.

En ese aspecto, Mac OS X está bien dotado. Las herramientas de desarrollo de Mac OS X incluyen programas como Shark, para medir el rendimiento de las aplicaciones, sin necesidad de escribir código adicional; pero se pueden conseguir resultados incluso más detallados si se utilizan. Esto permite encontrar cuáles son los cuellos de botella reales, no los percibios o imaginados, y mejorar el rendimiento de nuestras aplicaciones sobre el mismo hardware. No en vano Mac OS X ha ido mejorando de rendimiento sobre las mismas máquinas (eso sí, cargadas de memoria) de forma constante.

Investigación algorítmica, y funciones de sistema

El rendimiento de muchas operaciones, a veces, depende de haber sido inteligente a la hora de elegir la forma de abordarlas.

Por ejemplo, encontrar un nombre entre 16384 fichas, si las fichas no están ordenadas, puede llegar a implicar hasta 16384 comparaciones, en el caso de que el nombre que busquemos se encuentre en la última ficha, pero en promedio ocupará unas 8192 comparaciones. En cambio, si las fichas están ordenadas, podemos comparar el nombre con la ficha central, y o bien coincide, o bien está en las 8192 fichas superiores, o en las 8192 fichas superiores. Y si seguimos haciendo esa división, como mucho necesitaremos 14 comparaciones (porque 2^14 = 16384), o lo que es lo mismo: en el peor caso el algoritmo de búsqueda binaria es casi 1200 veces más rápido en el peor caso, y unas 600 veces más rápido en promedio… y se va haciendo cada vez más rápido cuantas más fichas vayamos considerando. De otra parte, esa búsqueda binaria implica que todos los elementos que se inserten se inserten en orden, o manteniendo un índice.

Esto demuestra la importancia de estudiar bien el problema que queremos resolver, y utilizar algoritmos adecuados, en lugar de utilizar directamente la primera solución que se ofrezca. Y es que, en ocasiones, las herramientas que proporciona un lenguaje de programación, o una biblioteca de funciones, pueden ser mejorables.

Sin embargo, al final existen algoritmos que se demuestran tan útiles que el propio sistema operativo, o lenguaje de programación, acaba por implementarlos. Por ejemplo, la búsqueda binaria se encuentra implementada en diferentes bibliotecas de funciones, a la espera de que el usuario proporcione la función que se encarga de comparar cualquier cosa que se quiera comparar, y devuelva si son iguales, o si la primera es mayor o menor que la segunda. Si usamos la función de sistema, escribimos menos código, y además nos beneficiaremos cada vez de las diferentes capacidades que se vayan implementando… y sobre todo, podemos delegar la optimización de esas funciones, y su expansión a un uso concurrente, multinúcleo, a los creadores del sistema operativo.

Ése es el caso de bibliotecas de funciones (frameworks) como Accelerate, CoreAnimation, CoreGraphics, CoreAudio… que se han ido optimizando para las diferentes capacidades que han ido proporcionando los diferentes sistemas operativos. En Leopard, existen otras funciones para el uso multinúcleo, que son NSOperation y NSOperationQueue, que están pensadas para crear series de operaciones que puedan ser independientes entre sí, de modo que el sistema operativo pueda decidir lanzarlas sobre unidades de ejecución diferentes… si existen.

Seguramente, el Grand Central anunciado para Snow Leopard sea una combinación de las tecnologías anteriormente citadas, pero mucho más generalizadas, de forma que prácticamente cualquier aplicación Cocoa se beneficie de estas tecnologías de la forma más sencilla… incluyendo el acceso a la capacidad de proceso de la GPU. Si además se pudieran añadir tarjetas de expansión al estilo de las antiquísimas Rocket Radius, o el más moderno Elgato Turbo.264, pero sin necesidad de software específico, sino incluido en el sistema, sería genial 😉

Acercarnos a la máquina

Al final, cuando se ha probado todo, lo mejor es acercarnos al lenguaje de ceros y unos que realmente entiende la máquina, pero eso implica un enorme esfuerzo: hay que conocer las decenas de variantes de operaciones que soportan las diferentes versiones de microprocesadores. Incluso en Mac OS X, que en su versión Intel sólo tiene que tratar con las instrucciones i386 de Intel Core Duo e Intel Core 2 Duo, y las instrucciones x86_64 de los Intel Core 2 Duo en versiones de sobremesa y Xeon, y las instrucciones PowerPC G3, G4, G4+ y G5, ya estamos hablando de al menos 7 variantes. Si además queremos ampliar el uso a diferentes tarjetas gráficas, las combinaciones se multiplican. De modo que resulta más razonable dejar ese trabajo cercano al metal al fabricante del sistema operativo.

Por cierto, parte de este trabajo recae sobre los compiladores: si se mejoran los compiladores, el código generado resulta más rápido. Y aquí también Apple aporta su granito de arena, puesto que desde que decidió utilizar gcc como compilador para el sistema no han parado de optimizar la generación de código PowerPC, lo que indirectamente mejora Mac OS X.

¿Sobre quién recae el esfuerzo de optimización?

Pues ya lo hemos estado viendo: el peso de la optimización viene a caer por igual entre el creador de las aplicaciones, y el creador del sistema operativo. Pero teniendo en cuenta la modularidad de Cocoa, y la tendencia normal de Apple a proporcionar funciones que vienen a sustituir gran cantidad de código creado por el programador para sustituirlo por una única línea de código, vemos que Apple ha decidido, en lo que respecta a Mac OS X, asumir mucha más responsabilidad a la hora de optimizar código, mediante la optimización del sistema y herramientas de medición de rendimiento para los desarrolladores.

Eso sí, hay un compromiso: cuanto más modernas sean las funciones que utiliza un programa, más difícil es para el programador hacer que funcione con versiones anteriores. Pero el resultado puede ser tan bueno para el programador, y finalmente para el usuario, a cambio de pedir una versión del sistema más reciente, que al final merece la pena esa actualización.

Apple puede decidirse también a introducir el nuevo asignador de tareas, llamado ULE (porque es el final de la palabra inglesa SCHED_ULE, lo que viene a decir que es el asignador de tareas final, y también por contraste con el asignador tradicional, llamado SCHED_4BSD). ULE, que está disponible como opción desde la versión 5.4 de FreeBSD, se considera tan maduro como para ser el asignador de tareas por defecto para el próximo FreeBSD 7.1.

En el caso de Microsoft, vamos a tener un par de efectos curiosos. Desde que Windows 2000 heredó el núcleo de Windows NT, el Windows de consumo ha dispuesto de capacidades multinúcleo en cuanto a la asignación de tareas. Sin embargo, es fácil ver que el asignador de tareas de Windows XP (que contiene un núcleo muy similar al de Windows 2000) muestra una preferencia por el primer núcleo instalado, y que es difícil que pasen tareas a otros núcleos.

La API .Net de Microsoft para Windows XP y Vista, así como las WinFX (originalmente sólo disponibles para Vista, y que se portarán retroactivamente para Windows XP), permitirán un mejor uso de las capacidades multinúcleo… a cambio de que los programadores dejen de utilizar las API tradicionales (Win32), en las que se encuentran escritas la inmensa mayoría de las aplicaciones Windows. Así que es posible que Microsoft tenga que sufrir un periodo similar al que Apple sufrió con la migración de Classic a Mac OS X, antes de que todas las aplicaciones puedan disponer de las optimizaciones multinúcleo. El problema para Microsoft es que poca gente está migrando a Windows Vista, de modo que la base instalada que no puede ejecutar aplicaciones WinFX sigue siendo enorme, lo que impide que muchos programas puedan aprovechar las nuevas características de gestión de recursos de estas APIs, al estar dirigidos a la base instalada.