Torre de Babel

Tutorial sobre programación y paralelismo (threads, MPI, GPGPU, WebCL)

by Francisco Charte.

Los ordenadores no tendrían utilidad alguna si no existiesen programadores que creasen software que les hiciese funcionar y ofrecer a los usuarios finales aquello que necesitan. Dicho software puede tomar distintas formas, desde el firmware que se incluye en ROM (o alguna variante PROM/EPROM/etc.) y se encarga de la puesta en marcha y ofrece los servicios más básicos hasta las aplicaciones de control de procesos o diseño asistido, pasando por los sistemas operativos y los propios compiladores e intérpretes de multitud de lenguajes.

Tiempo compartido

En los primeros ordenadores el software se ejecutaba en forma de procesos por lotes: cada programador ponía su tarea en cola y esperaba a que llegase su turno para obtener la salida correspondiente. Cada tarea era intrínsecamente secuencial, en el sentido de que no ejecutaba más de una instrucción de manera simultánea. Posteriormente llegaron los sistemas de tiempo compartido capaces de atender interactivamente a varios usuarios y, en apariencia, ejecutar múltiples tareas en paralelo, si bien la realidad era que el sistema operativo se encargaba de que el procesador fuese saltando de una tarea a otra cada pocos ciclos, consiguiendo esa ilusión de paralelismo o multitarea.

Para los programadores de un sistema operativo la implementación del tiempo compartido implicaba codificar algoritmos relativamente complejos, de los cuales el más conocido es Round Robin, capaces de seleccionar en cada momento el proceso que ha de pasar a ejecutarse e impedir situaciones indeseadas como, por ejemplo, que una tarea no obtenga nunca tiempo de procesador. Con el tiempo los microprocesadores implementaron en hardware una gran cantidad de lógica que facilitaba el intercambio rápido de tareas, haciendo más fácil el trabajo de los programadores de sistemas.

Los programadores de aplicaciones, por el contrario, siguieron durante décadas diseñando software asumiendo que sus programas obtenían el control total del ordenador, implementando los algoritmos para que se ejecutasen secuencialmente de principio a fin y dejando que el sistema operativo los interrumpiese cada cierto tiempo para volverlos a poner en marcha un instante después, todo ello a tal velocidad que los usuarios tenían la sensación esperada: la aplicación les atendía de manera continua sin problemas. Esto es especialmente cierto en aquellos programas en los que existe comunicación con el usuario, ya que la mayor parte del tiempo se encuentran a la espera de una acción por parte de éste: una entrada por teclado, la pulsación de un botón, etc.

Threads y SMP

Dado que los microprocesadores solamente eran capaces de ejecutar una tarea en un instante dado, antes de que contasen con pipelines primero, varias unidades funcionales después (procesadores superescalares) y múltiples núcleos finalmente; los programadores de aplicaciones que querían ejecutar más de un trabajo en paralelo recurrían a diversos trucos, como el uso de interrupciones. De esta forma era posible, por ejemplo, imprimir un documento o realizar otra tarea lenta mientras se seguía atendiendo al usuario. De ahí se pasó a la programación con múltiples hilos o threads, de forma que un programa podía ejecutar múltiples secuencias de instrucciones en paralelo. Esos hilos eran gestionados por el sistema operativo mediante el citado algoritmo de tiempo compartido: el procesador seguía ejecutando únicamente una tarea en cada instante.

Aunque el multiproceso simétrico existe desde la década de los 60 en máquinas tipo mainframe, no fue hasta finales de los 90 cuando los servidores y estaciones de trabajo con zócalos para dos procesadores se hicieron suficientemente asequibles como para adquirir cierta popularidad. Estas máquinas contaban con dos procesadores y, en consecuencia, tenían capacidad para ejecutar dos tareas con paralelismo real. Obviamente los algoritmos de tiempo compartido seguían estando presentes, ya que el número de procesos en ejecución suele ser mucho mayor, pero el rendimiento era muy superior al ofrecido por los ordenadores personales.

GPGPU y MPI

El escenario de la computación personal ha cambiado drásticamente desde el inicio del nuevo milenio. Si en los años previos los fabricantes de microprocesadores competían casi exclusivamente en velocidad, lo que permitía al software aprovechar la mayor potencia sin trabajo adicional por parte del programador, en la última década han aparecido los microprocesadores multinúcleo y los procesadores gráficos con capacidades GPGPU (General-Purpose Computation on Graphics Hardware), lo que ha traído el final del Free Lunch para los programadores. Ahora aprovechar la potencia de un ordenador implica necesariamente el uso de todo ese paralelismo de una forma u otra.

A los microprocesadores multinúcleo y las GPU habría que sumar una opción cada vez más alcance de cualquiera: los cluster de ordenadores. Si bien antes eran una opción reservada a centros de supercomputación, en la actualidad hay multitud de usuarios que disponen de varias máquinas conectadas en red local, lo cual abre las puertas (con el software adecuado) a la configuración en cluster para aprovechar el paralelismo y ejecutar software distribuyendo el trabajo entre múltiples máquinas.

En conjunto la popularización de estos mecanismos de paralelización implican la aparición de un nuevo modelo de diseño de software y el necesario reciclaje de los programadores. Ya no basta con escribir sentencias que se ejecutarán una tras otra, sin más, siendo preciso planificar una arquitectura de mayor complejidad si se quiere obtener el mayor beneficio del hardware disponible. Algunas ideas al respecto:

  • Distribuir el trabajo a realizar entre varios ordenadores conectados en red local es una tarea relativamente simple gracias a MPI (Message Passing Interface), una interfaz de la que existen múltiples implementaciones para diferentes sistemas operativos. Personalmente he usado Open MPI, una implementación Open Source de MPI, y su funcionamiento en un cluster con red Ethernet es muy simple.
  • En cada una de los ordenadores del cluster (o el único ordenador si no se dispone de uno) el software ha de estructurarse de forma que se aprovechen al máximo los núcleos con que cuente el microprocesador. Esto implica trabajar con múltiples hilos, algo realmente simple en la plataforma Java o la plataforma .NET y que en el caso de lenguajes como C/C++ significa recurrir a bibliotecas como POSIX threads.
  • Si los ordenadores en que se ejecute el software cuentan con hardware de vídeo de última generación, todos aquellos procesos con alto nivel de paralelismo tipo SIMD (Single Instruction Multiple Data) pueden acelerarse hasta un punto realmente sorprendente, ya que las GPU pueden realizar en un ciclo operaciones en paralelo sobre 256, 320 e incluso más operandos, mientras que un microprocesador tendría que recurrir a un bucle y consumir un número mucho mayor de ciclos. Hasta no hace mucho programar tareas a ejecutar en una GPU tenía el inconveniente de que cada fabricante ofrecía su solución propietaria: CUDA en el caso de NVidia (es la opción que he usado en algunas ocasiones y sobre la que publiqué un artículo hace aproximadamente un año en una conocida revista española) o Stream en el de ATI. Desde hace algo más de un año existe otra opción: OpenCL, un estándar que no solamente funciona con GPU de diferentes fabricantes sino que, además, está diseñado para repartir tareas entre CPU y GPU. Una opción adicional, siempre que se trabaje sobre Windows, es DirectCompute, una API similar a OpenCL que hace posible la programación GPGPU sin que importe el fabricante de hardware.

El Grupo Khronos ha hecho pública recientemente la versión 1.1 de OpenCL y tanto ATI como NVidia ofrecen controladores para esta API, por lo que posiblemente sea la mejor alternativa si uno no quiere atarse a la oferta de una determinada empresa.

Aprender a usar estas herramientas será (sino lo es ya) un requisito indispensable para cualquier programador, no exclusivamente para los desarrolladores de software de sistemas. El proceso, sin embargo, será lento y mientras tanto el hardware de que disponemos en nuestro escritorio estará muy infrautilizado, ya que muy pocas aplicaciones aprovechan su potencia. El sistema operativo utiliza los múltiples núcleos de los actuales microprocesadores para repartir la carga de trabajo, pero apenas hace uso de la GPU. De hecho las GPU, salvo en el caso de los juegos y algunas aplicaciones específicas de gráficos/vídeo, son el recurso mas desaprovechado. La próxima generación de navegadores, no obstante, promete hacer uso de esa potencia a través de la aceleración por hardware de la composición de páginas.

CPU vs GPU

Todos los ordenadores cuentan con una CPU o microprocesador (en ocasiones con varios) y, desde hace unos años, dichos circuitos integrados dejaron de competir en velocidad bruta, regida únicamente por la frecuencia de funcionamiento, para incrementar su potencia por otra vía: la integración de múltiples núcleos. Una configuración hardware con un único microprocesador de 4 núcleos resulta mucho más barata que otra que cuente con 4 microprocesadores (que también existen) de un único núcleo, ya que en la placa base es necesario un único zócalo y el número de interconexiones es también mucho menor, aparte de que fabricar un único chip es más barato que fabricar cuatro. La potencia de estos dos hipotéticos sistemas no es idéntica, pero sí muy similar.

Además de varios núcleos ciertos fabricantes, como es el caso de Intel con su tecnología Hyperthreading, diseñan sus microprocesadores de manera que cada núcleo (duplicando ciertas unidades operativas) tiene capacidad para ejecutar dos hilos simultáneamente. Con un micro de 4 núcleos podrían ejecutarse 8 hilos con paralelismo real (sin recurrir a técnicas de tiempo compartido). Este fabricante ya cuenta con microprocesadores que ofrecen 6 núcleos/12 hilos y en muestras de tecnología futura, puesta a disposición de universidades, experimenta con un chip que dispone de 48 núcleos. Es fácil darse cuenta de que en pocos años tendremos ordenadores cuyas CPU integrarán decenas sino cientos de núcleos, equivalente cada uno de ellos a un procesador tipo Pentium.

La escalada del número de núcleos integrados en un mismo circuito no se inició, sin embargo, en el campo de las CPU, sino que viene precedida por una carrera similar en el de las GPU desde hace ya varios años, producto de la directa competencia entre nVidia y ATI (ahora AMD). Los productos de estos fabricantes hace tiempo que se componen de cientos de núcleos de procesamiento y grandes cantidades de memoria, ofreciendo una potencia impensable hasta hace muy poco. Aunque en un principio esos núcleos se empleaban exclusivamente para ejecutar shaders, pequeños programas encargados de realizar transformaciones sobre vértices, aplicar texturas, cálculos de iluminación, etc., (véase la serie sobre shaders que he ido publicando en los últimos meses, en el margen derecho), gracias a las técnicas GPGPU ahora también es posible usarlos para otros fines.

A pesar de que la denominación núcleo ha sido utilizada tanto por fabricantes de GPU como de CPU, debe tenerse en cuenta que no hace referencia exactamente al mismo concepto. En una CPU cada núcleo es equivalente a un microprocesador completo, con sus propios registros, unidades aritméticas y de ejecución e incluso memoria propia, si bien comparte también memoria con los demás núcleos, así como las líneas de entrada/salida y buses que permiten a la CPU comunicarse con el exterior. Los núcleos de una GPU son mucho más sencillos, básicamente unidades aritmético-lógicas con capacidad para operar en coma flotante y llevar a cabo algunas operaciones específicas, pero no ejecutar código de propósito general.

A la hora de planificar el grado de concurrencia de un software o algoritmo hay que diferenciar, por tanto, entre paralelismo SIMD y paralelismo MIMD. Las GPU son ideales para el primer caso, en el que un mismo conjunto de sentencias se aplica simultáneamente sobre múltiples datos independientes entre sí, produciendo por lo general tantos resultados como datos de entrada existan. Es una configuración ideal para, por ejemplo, realizar operaciones sobre matrices que, dependiendo de su tamaño, pueden ser calculadas en un único ciclo de reloj. Para paralelizar tareas del segundo tipo, en las que flujos de sentencias diferentes se aplican sobre conjuntos de datos que pueden ser independientes o no, es necesario recurrir a los núcleos de la CPU, ya que cada uno de ellos puede ejecutar un programa distinto: un núcleo puede controlar la interfaz de usuario de un programa mientras otro se dedica a procesar datos introducidos en dicha interfaz, tareas paralelas pero que no tienen mucho que ver entre sí.

Estas diferencias entre un tipo de paralelismo y otro dan lugar también a diferentes modelos de programación. Las tareas a ejecutar en los núcleos de un procesador se implementan como hilos o threads. Incluso cuando no se crean explícitamente, cada programa/proceso tiene asociado al menos un hilo de ejecución que se encarga de procesar el flujo principal de sentencias. Los sistemas operativos cuentan con una API de bajo nivel para la creación y control de hilos, siendo mucho más habitual el uso de los servicios de alto nivel que ofrecen la mayoría de plataformas y lenguajes para esta tarea, dejándoles la gestión de los detalles más delicados. Incluso hay plataformas/lenguajes, como es el caso de Erlang, en los que este paralelismo es prácticamente implícito sin necesidad de vérselas con los hilos.

En contraposición, las tareas de tipo SIMD a ejecutar en una GPU se implementan como un kernel o porción de código que se aplicará en paralelo sobre todos los datos a tratar, sería equivalente a tener múltiples hilos ejecutando exactamente las mismas sentencias pero cada uno de ellos sobre un dato diferente de una estructura mayor. Ese grupo de sentencias suele ser breve, llevando a cabo operaciones relativamente sencillas. A diferencia de lo que ocurre con los hilos, ni sistemas operativos ni plataformas/lenguajes (como .NET o Java) permiten crear este tipo de programas para ejecutarlos en GPU, siendo necesario recurrir a soluciones dependientes de cada fabricante como puede ser CUDA en el caso de NVidia o Stream en el de ATI.

¿Cómo podría una misma aplicación, con el objetivo de explotar toda la potencia de un ordenador actual, aprovechar tanto el paralelismo de la CPU como de la GPU? Hasta no hace tanto esto implicaba crear hilos en la CPU para las tareas MIMD y kernels en la GPU para las tareas SIMD, con herramientas distintas y en ocasiones lenguajes de programación distintos, integrando los diversos componentes de la mejor manera posible. Una alternativa que cuenta con el favor de una gran parte de la industria es OpenCL, un estándar que hace posible la ejecución de código escrito en C/C++ distribuyendo las tareas entre CPU y GPU, sin que importe el fabricante de la GPU. Esa capacidad, no obstante, es actualmente teórica en un escenario en el que cada empresa intenta favorecer su oferta sobre la de la competencia.

Si se cuenta con un hardware gráfico de nVidia, los controladores OpenCL de esta empresa solamente reconocerán como dispositivo la propia GPU, tal y como se aprecia en la ventana de la izquierda de la imagen inferior. Los controladores de ATI/AMD (menos avanzados que los de nVidia en el soporte OpenCL), por el contrario, sí reconocen la CPU como dispositivo (ventana de la derecha), pero obviamente no pueden usar la GPU de nVidia.

Es necesario, por tanto, contar con una configuración hardware específica si se quiere usar OpenCL o, de lo contrario, recurrir a la oferta específica de cada fabricante: CUDA o Stream. Una opción adicional, pero que tal como indiqué en la entrada antes citada es válida únicamente para Windows, sería DirectCompute, una API similar a OpenCL que hace posible la programación GPGPU sin que importe el fabricante de hardware. En realidad ésta es una verdad a medias, ya que recientemente Microsoft el equipo de desarrollo de Mesa/Galium3D anunció que habrá una implementación nativa de DirectX 10/11 para Linux, lo cual permitiría usar DirectCompute en Windows/Linux (por ahora no en Mac) sin que importe el fabricante.

Otra alternativa más, aunque habrá que esperar para ver qué ofrece, sería usar CUDA para x86, una versión de CUDA que se ejecutaría sobre las actuales CPU y que acaba de ser anunciada por nVidia. Todavía no conozco los detalles, pero es de suponer que esto permitirá usar CUDA para ejecutar código tanto en la GPU como en la CPU, situando a CUDA como el competidor más directo de OpenCL que, anecdóticamente, debe gran parte de su desarrollo a la propia nVidia.

Paralelismo y aplicaciones web - WebCL

La única vía que hay actualmente para obtener provecho del gran rendimiento que ofrece el hardware, tanto los microprocesadores multi-core (CPU) como las GPU con sus cientos de núcleos de procesamiento, pasa por un rediseño del software a fin de afrontar explícitamente el paralelismo.Ya se han descrito en los apartados previos las diferentes opciones a disposición de los desarrolladores: threads, MPI, CUDA, OpenCL, etc., habiéndose establecido las diferencias fundamentales entre paralelismo en CPU y en GPU.

Al tratar el tema del paralelismo siempre se asume que el objetivo es emplearlo en programas que serán instalados y ejecutados en un ordenador de forma nativa, ya sea a través de compiladores específicos para un hardware concreto o el uso de máquinas virtuales que se ocupan de los detalles de más bajo nivel. En cualquier caso son aplicaciones dirigidas a funcionar bajo una cierta configuración: microprocesador, GPU, sistema operativo, etc. De un tiempo a esta parte, sin embargo, la web está ganando terreno rápidamente como plataforma para la ejecución de aplicaciones superando esas especificidades, no precisando más que un navegador que se ajuste a los estándares: HTML5, CSS3 y Javascript.

El código Javascript de una aplicación web puede ejecutar código en múltiples hilos en la CPU gracias a los Web Workers pero, hasta el momento, no existía un método que permitiese aprovechar la gran potencia con la que cuentan las GPU actuales con independencia del hardware, sistema operativo o navegador que el usuario emplee para acceder a la aplicación web. Por suerte es una situación que, todo parece indicar, cambiará en un futuro reciente gracias a WebCL.

WebCL es a las aplicaciones web lo que OpenCL a las aplicaciones nativas: una capa de abstracción que permite ejecutar código en paralelo tanto en CPU como en GPU, sin importar el fabricante del hardware ni el sistema operativo empleado. Sobre OpenCL ya escribí en Programación y paralelismo (CPU vs GPU) y en Python + OpenCL = PyOpenCL. Es un estándar regido por el Khronos Group y que siguen múltiples fabricantes de hardware, entre ellos AMD/ATI, nVidia e Intel. En realidad WebCL es, fundamentalmente, un enlace o binding para poder acceder a OpenCL desde Javascript.

WebCL es un estándar en desarrollo y ningún navegador lo incluye de serie actualmente. Para poder probarlo es necesario instalar un complemento en el navegador y, por el momento y hasta donde sé, únicamente hay dos disponibles: un prototipo de Samsung para Webkit que puede utilizarse en Safari sobre MacOS X (10.6 ó 10.7) y otro de Nokia para Firefox 6 disponible para Windows y Linux (en versiones de 32 bits). Una vez instalado el complemento es posible crear desde Javascript un objeto WebCLComputeContext (en la implementación de Samsung) y usarlo para obtener información sobre el hardware disponible, preparar el código a ejecutar paralelamente y enviarlo a la CPU/GPU.

WebCL está dando sus primeros pasos. El grupo de trabajo encargado de este estándar dentro del Khronos Groups fue creado el pasado mes de mayo y, en principio, su objetivo es facilitar una guía de implementación para fabricantes conservando la esencia de OpenCL y poniendo especial énfasis en el tema de la seguridad, ya que el código se ejecutaría en el ordenador de los usuarios al acceder a una aplicación desde su navegador, sin necesidad de instalar ni ejecutar explícitamente un programa externo. En la presentación de más abajo, realizada por el Khronos Group, se ofrecen algunos ejemplos y enlaces a vídeos demostrativos del uso de WebCL y su integración con WebGL.