Los 5 pilares de la paralelización

Posted on agosto 21, 2007. Filed under: Hardware |

Falta poco para que muchos de nosotros tengamos un Core 2 Quad o un Phenom X4 en casa y, sin embargo, ¿tenemos seguridad de que las aplicaciones que utilizamos sacarán provecho de esa configuración? En el siguiente artículo, una revisión a los puntos que, según Intel, constituyen la gran dificultad de programar para sistemas multinúcleo.

Introducción

Vivimos en una época en que la computación desechó el modelo de los núcleos monstruosos de Mhz por las nubes y se inclinó por una expansión en paralelo, un enfoque de muchos núcleos no tan bestiales, pero que en su conjunto puedan ofrecer mayor poder de procesamiento al usuario.

Ahora bien, una respuesta sencilla cuando nos preguntamos la ventaja de esta arquitectura escalable, es pensar que podemos correr múltiples tareas a la vez y no por ello sentir que alguna de ellas se queda estancada o, peor, que el conjunto anda a tropiezos compitiendo cada parte por hacerse de la potencia de un solo proveedor de cálculo. Esto pudimos verlo cuando revisamos el Athlon X2 4800+, en donde comparamos cómo un procesador de doble núcleo de 2.4Ghz vencía en forma apabullante a un Pentium 4 a 3.8Ghz o a un Athlon FX55 a 2.6Ghz cuando se corrían dos tareas demandantes a la vez.

Sin embargo, aunque para correr tareas en paralelo la ventaja pueda ser obvia, en muchos casos el usuario desea experimentar un aumento de rendimiento en LA gran aplicación. ¿Un rendereo? ¿Codificación de video? Los ejemplos de lo anterior pueden ser muchos y para todos ellos el usuario sentirá que no obtuvo lo que esperaba. Tiene un procesador con cuatro núcleos de 2.6Ghz y su aplicación corre más lento que en un sólo núcleo de 3Ghz. ¿Acaso salió perdiendo? En su caso, sí, pero no por culpa de la arquitectura, sino porque su gran aplicación no está sacando provecho de los múltiples núcleos.

Ahora bien, ¿Porqué los programadores son tan necios que no programan para aprovechar esa multiplicidad? La respuesta, querido lector, es porque programar de esa manera es radicalmente distinto, y sustancialmente más difícil.

En el Blog Corporativo de Intel han abordado el problema y, aunque no dan la receta de cocina para solucionarlo, sí pretenden brindar una metodología para plantear un programa de tal manera que pueda sacar partido de los núcleos múltiples o de cualquier clase de escalamiento como puede ser, por ejemplo, un cluster. Según Intel, el enfoque se apoya sobre cinco pilares:

1 Encontrar el paralelismo
2 Evitar los errores
3 Ajustar el rendimiento
4 Asegurar que sea compatible a futuro
5 Utilizar métodos de programación modernos

A continuación intentaremos explicar, en nuestras palabras y de la manera más sencilla posible -en atención a que no todos los lectores son programadores avezados- a qué se refieren estos cinco pilares.

Primer Pilar: Encontrar el paralelismo

Los paralelismos en la aplicación pueden ser aparentemente muy sencillos: si un programa fuese como hacer un Chop Suey, en vez de tener al mismo cocinero japonés invencible con el cuchillo jinzu cortando a la velocidad de la luz los cebollines, luego las zanahorias, luego el apio, luego bueno, cada uno de los ingredientes, podrías tener a cuatro cocineros no tan veloces haciendo cada uno una parte y juntando los vegetales al final en el Wok. Pero hey, no todos los programas son como un Chop Suey, y ahí está el problema.

Hay aplicaciones cuyo cometido es como en atletismo la posta 4×100. No puedes poner a los 4 participantes a correr al mismo tiempo, porque hasta que el corredor anterior no te pasa el bastón, no puedes empezar a correr, a menos que quieras hacer el ridículo corriendo con las manos vacías. El ejemplo más clásico se da en las aplicaciones de compresión de video. Verán, la compresión se basa en intentar predecir dónde una porción del cuadro de vídeo actual aparecerá en el próximo cuadro, esto se llama “Motion Estimation” o Estimación de Movimiento. De esta manera, la compresión opera manteniendo del cuadro actual todo lo que permanece inalterado, y modificando (doh!) sólo aquello que se mueve de lugar. Aquí la paralelización ya no es tan fácil como en el Chop Suey, porque el algoritmo que inserta los elementos que se han movido sólo puede trabajar como función del cuadro anterior. En el fondo, cada pieza del puzzle es función de la pieza anterior. ¿Cómo paralelizas eso?

En conclusión, el primer pilar es analizar lo que quieres hacer y ver cómo puedes pasar de un sistema completamente secuencial, al modelo Chop Suey, y esto, muchas veces, implica replantearte por completo el algoritmo que estás usando. Primer pilar: primer gran problema.

Segundo Pilar: Evitar los errores

Supongamos que el programador logró replantear su código de acuerdo al Chop Suey, él cree que sus problemas se terminaron pero en realidad sólo han comenzado.

Cuando se tiene más de un hilo ejecutándose al mismo tiempo, accediendo datos al mismo tiempo, se generan errores cuyo origen no es nada de inmediato, porque no es que ninguno de los hilos esté haciendo algo mal, sino que el hilo del lado le juega sucio y altera datos que el primer hilo necesita.

Los errores antes descritos se conocen como “data races”, aquellos casos en que más de un hilo opera sobre el mismo universo de datos. El primero que llegue a ellos hará lo correcto, pero cuando el segundo acceda, los datos que toma han sido de alguna manera alterados por el primero.

Sucede que el resultado del cómputo normalmente depende de el resultado de múltiples hilos compitiendo para escribir un dato compartido. Los programadores tienen que estar seguros no sólo de que la operación sobre los datos sea correcta, sino además coordinar las operaciones para no crear una debacle.

Intel ilustra el problema con una simple función que intercambia el valor de dos variables:

función intercambio($variable1, $variable2) {
$temporal=$variable1;
$variable1=$variable2;
$variable2=$temporal;
}

Pensemos ahora en este programa:

$yo=”pedro”;
$tu=”juan”;
$el=”diego”;

intercambio($yo,$tu); <—— función 1 intercambio($yo,$el); <—— función 2 El resultado será, finalmente: $yo=”diego”
$tu=”pedro”
$el=”juan”

Si, en cambio, se ejecuta primero la función 2 y luego la 1, el resultado es:
$yo=”juan”;
$tu=”diego”;
$el=”pedro”;

Si ambas funciones se ejecutan como hilos paralelos… ¿Cuál es el resultado final?

El segundo pilar nos muestra que cuando se trata de aplicaciones paralelizadas, el programador tiene que tener una visión ya no secuencial, porque de lo contrario no tiene idea de lo que va a resultar de la interacción de ambos hilos.

Pilar 3: Ajustar el rendimiento

Aunque los núcleos realizan tareas en paralelo, también operan sobre componentes compartidos. Así como muchas aplicaciones corriendo en paralelo en un procesador mononuclear se dan de patadas para hacerse con la potencia del CPU, incluso en arquitecturas multinúcleo pasará que a la hora de usar el caché compartido los núcleos se darán de patadas compitiendo por el recurso común.

En algoritmos de álgebra lineal, se usa mucho que determinadas porciones de l problema a resolver bloquean una parte del caché asegurándose la prioridad para los puntos más duros del problema. ¿Pero qué pasa cuando hay más de un núcleo usando ese caché? Por priorizar el desempeño de uno podríamos estar dejando al otro completamente cojo, y el desempeño general se empobrecería.

En el mundo de los núcleos múltiples, el problema se complica por cuanto no es una sola torta la que hay que compartir, sino asimismo administrar segmentos exclusivos y segmentos compartidos del caché. Por poner un ejemplo, los procesadores Phenom X4 de AMD comparten el caché L3 pero tienen un caché L2 exclusivo, más conexiones directas entre núcleos. ¿Qué segmentos de datos hay que mandar al caché compartido, al caché propio o directo al núcleo vecino? No es nada de sencillo.

El tercer pilar nos dice, querido lector, que hay que poner un empeño infinitamente superior en lograr la sintonía fina cuando hablamos de aplicaciones paralelizadas.

Pilar 4: Asegurar la compatibilidad a futuro

En aplicaciones secuenciales, era tan simple como pensar que el año siguiente aparecería un nuevo CPU más potente que haría correr más rápido el programa. En aplicaciones paralelizadas esto ya no es tan así.

Todo lo que corre para aplicaciones secuenciales, cuando se habla de aplicaciones paralelizadas pierde validez, puesto que al año siguiente puede aparecer un procesador con distinto número de núcleos, tamaños del cache, interconexiones, etc… Cuando la programación se ajusta a estos parámetros de manera específica, se hace imposible programar en forma clarividente para productos que aún ni siquiera son diseñados, y como consecuencia nuestra aplicación puede no sacar provecho de los nuevos CPU o incluso correr más lento y generar errores.

Por ejemplo, una de las cosas sujetas a cambios es la cantidad de ciclos que toma a un núcleo comunicarse con el otro. Más importante aún, la cantidad de cálculos aritméticos que el núcleo puede hacer mientras se comunica con el otro núcleo, un factor que debiera aumentar con el tiempo y para el cual es imposible sintonizar la aplicación a priori. Si hacemos un algoritmo que hace 100 operaciones aritméticas en 100 ciclos mientras se sincroniza con otro núcleo que calcula 50 ciclos, entonces mantendremos a ambos núcleos ocupados. Sin embargo, si corro el mismo código binario en un sistema con una frecuencia mayor, lo que eleva el tiempo de sincronización relativo a 100 o mas ciclos, estaré desaprovechando la mitad de la capacidad, dejando un núcleo ocioso la mitad del tiempo: imperdonable.

La conclusión del cuarto pilar es la necesidad de diseñar pensando que la sintonización del programa pueda adaptarse dinámicamente, incluso sin saber como serán las arquitecturas futuras, para aprovechar el progresivo levantamiento de las restricciones actuales.

Pilar 5: Utilizar métodos de programación modernos

En los antiguos métodos de programación, basados en kernels que a su vez se constituyen básicamente de loops, como en C, es sencillo identificar los segmentos intensivos en procesamiento o, dicho de otra manera, los mastodontes que querríamos paralelizar. Sin embargo, ese estilo de programación ha cambiado radicalmente ahora que se utilizan lenguajes orientados a objetos, como Java, C#, Ruby o Python.

La abstracción que se alcanza con las actuales técnicas de programación está llena de iteraciones complejas que involucran infinidad de llamados virtuales a funciones, e incluso los segmentos destinados a realizar tareas sobre grandes colecciones de datos están plagados de interacciones transversales con objetos, y estructuras de datos complejas, que ocurren en forma prácticamente impredecible.

El quinto pilar indica, entonces, que lejos de intentar devolverse al viejo sistema de loops, es necesario aprender a identificar aquello que debemos paralelizar sin renunciar, en caso alguno, a la riqueza de la programación orientada a objetos, por difícil que sea.

Palabras al cierre

Como podemos ver, aun falta mucho para que el software logre adaptarse al hardware, por el momento es mejor un Dual Core con velocidades mas altas que un Quad Core para jugar. En una entrevista reciente el programador en jefe de Epic Games Tim Sweeney, afirmó esto desde su punto de vista de desarrollador de juegos y hablando del motor UE3, sus palabras fueron “Si te vas a comprar un procesador para jugar el “Sweet Spot” en estos momentos tiene que ser un Dual Core, pues un ejemplar de alta velocidad vale menos que un Quad Core de menor frecuencia.” luego agregó “Todos los juegos UE3 por ejemplo, escalan realmente bien de un núcleo a dos núcleos por lo que obtienes rendimientos significativamente mejores la mayoría del tiempo con dos núcleos. Aunque es cierto que el motor de UE3 y otros escalan hasta 4 núcleos las mejoras no son grandes”.

Por otra parte cuando las empresas de Juegos o aplicaciones en general programan lo hacen también pensando quienes lo usarán y dónde debe correr el juego o aplicación, si bien muchos podemos tener PCs bastante poderosos para el promedio, generalmente no son el estándar buscado por 2 motivos.

Primero, es mas caro invertir en programadores para optimizar el código en paralelo y, segundo, aunque las empresas lo hagan, el cuarto pilar nos dice que no hay ninguna garantía de que este código paralelizado pueda sacar provecho a futuro.

En conclusión, contrastando la visión de Intel contra la de una enorme empresa de juegos, podemos ver que -bueno, como todas las empresas- su meta está en ganar dinero, algo que logran vendiendo la mayor cantidad de copias posibles y no haciendo el código paralelizado perfecto: muchas veces optarán por crear un producto que saque provecho del PC promedio, no de los multinúcleos actuales ni menos de aquellos que están por venir.

Fuente: Chilehardware

Make a Comment

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Liked it here?
Why not try sites on the blogroll...

A %d blogueros les gusta esto: