Cómo distribuir cálculos entre varios núcleos para acelerar procesos de computación [ejemplos en C++]

Hace años, más o menos a finales del siglo XX y principios del XXI y, como vimos en mi anterior post, hubo una guerra por los Megahercios. Es decir, las grandes compañías de procesadores, en aquella época Intel y AMD que, aunque había más fabricantes, éstos eran los que más sonaban, peleaban para que sus procesadores corrieran más que los de la competencia. Es más, como el usuario de a pie siempre se ha regido por la frase: " burro grande, ande o no ande ", siempre querrá un procesador con más megahercios, una cámara con más megapixels o una televisión con más pulgadas.

Pero ahora vivimos una realidad un poco distinta. Los procesadores actuales, que podemos tener en nuestro ordenador personal o encontramos en un servidor, grosso modo, intentan hacer operaciones más complejas utilizando menos ciclos, realizar varias operaciones a la vez y, también, consumir menos energía. Es más, en 2004 se alcanzaron los 4GHz, y pocos procesadores actuales los superan. Para entendernos mejor, antes sabían sumar, restar, multiplicar y dividir. Y, cuando queríamos hacer una raíz cuadrada teníamos que hacerlo en función de las operaciones que sabíamos hacer. Pero ahora las CPUs saben hacer raíces cuadradas sin necesidad de más indicaciones. Al mismo tiempo, si tenemos que hacer muchas operaciones, podemos agruparlas y procesar varios grupos a la vez. Esta explicación no es muy exacta, pero así nos hacemos una idea de cómo va la cosa.

Hoy vamos a centrarnos en la capacidad de desempeñar varios trabajos a la vez por la CPU. Y eso vendrá determinado por el número de núcleos o de hilos de ejecución que sea capaz de ejecutar dicha CPU. Por supuesto, el buen funcionamiento del sistema vendrá determinado por cómo el sistema operativo reparta las tareas entre los núcleos del procesador. O si, por ejemplo, tenemos una placa base con varias CPU, cómo se repartan las tareas entre éstos.

Varios procesos diferentes

Empecemos por el principio. Una vez que los sistemas operativos han evolucionado, y ya son capaces de manejar los núcleos como churros, podemos ver cómo si ejecutamos varias aplicaciones pesadas en nuestro sistema, éstas se ejecutan utilizando varios núcleos. Mientras que si sólo ejecutamos una, sólo habrá un núcleo trabajando.
Como vemos en las siguientes imágenes, podemos ver cuándo había sólo una aplicación gorda (por así decirlo) corriendo. En este caso sólo está trabajando intensamente la CPU3, las demás, algo también, porque un ordenador ejecuta muchos servicios.

Pero como vemos en la siguiente imagen, hay dos CPUs trabajando intensamente, la CPU4 y la CPU5. Porque tengo dos programas de cálculo corriendo a la vez (el segundo terminó muy pronto, pero se puede ver el intervalo de trabajo).

Cuando un proceso necesita músculo

Pero seguro que se nos ocurren tareas en las que necesitamos mucha más potencia de cálculo. Éstas pueden ser, por citar algunos ejemplos: compresión/descompresión de vídeo, simulaciones, procesamiento 3D, tratamiento de imagen, criptografía, etc. Son procesos que, pueden llevar mucho tiempo y, aunque podremos lanzar varios procesos iguales a la vez y comprimir 4 vídeos en el tiempo que se tarda en comprimir uno solo. A nosotros nos interesaría poder comprimir uno, pero en una cuarta parte del tiempo...

Es cierto que la compresión de vídeo es un terreno que ya está muy dominado en este aspecto. Existe tanto software como hardware especializado en realizar esta tarea de manera muy eficiente y muy rápida (como hablaré en futuros posts, podemos, por ejemplo, utilizar ffmpeg o avconv para comprimir vídeo utilizando varios núcleos y acelerar dicho proceso). Pero siempre está bien poder hacer lo mismo por nosotros mismos a la hora de crear un programa que realice un cálculo complejo, o un efecto, o análisis de imagen. De la misma manera de antes, ya que tenemos varios núcleos en nuestro ordenador, nos interesa terminar pronto en lugar de hacer varias imágenes a la vez. Incluso en un programa de edición de vídeo, nos interesa tener una previsualización en tiempo real y, a veces, en la máxima resolución posible.

Algunas cosas a tener en cuenta

Eso sí, para aprovechar el multiprocesamiento, y hacer que varios núcleos puedan coordinarse para procesar el trabajo que queremos y sacarlo antes, primero necesitamos optimizar nuestros algoritmos para ello y tener en cuenta algunas cosas:

• Tenemos que independizar los cálculos lo más posible. Es decir, si un cálculo depende del resultado de la iteración anterior, no vamos a poder paralelizar el cálculo total. Aunque, por ejemplo, si queremos aplicar un filtro a una imagen (si no anula lo que he dicho en la frase anterior), sí que podemos dividirla en trozos y procesar cada trozo por separado. O, si es un sumatorio, y cada elemento se puede calcular de forma independiente, podemos calcular y sumar resultados parciales y, cuando acabemos, sumar los resultados parciales... ya lo iremos viendo.
• Cuidado con la memoria. Es aconsejable utilizar, en la medida de lo posible, zonas de memoria diferentes en cada uno de los hilos de ejecución que lancemos para evitar condiciones de carrera, o el tener que introducir mutex o bloqueos a la hora de acceder a un dato.
• ¡Cuidado con los bloqueos! Un poco realacionado con el punto anterior. Si necesitamos hacer que un hilo espere a otro, puede que tengamos potencia desaprovechada y tardemos mucho. Hay veces que es inevitable, pero en muchos casos no.
• Monitorizar el tiempo. Si una tarea, programada para un sólo hilo, imaginemos que tarda 10 segundos. Cuando la programamos de forma multihilo y lanzamos dos hilos, es muy difícil que tarde la mitad, 5 segundos. Tal vez, tardará 6 segundos, y si lanzamos 3 hilos, se aproximará a 5 segundos. Esto está bien, ya que seguramente tengamos algún acceso más a variables, tendremos que acceder a algún dato de otra forma, o incluso hacer operaciones antes y después del procesamiento en grupo. Eso sí, si procesando con dos hilos tardamos 9 segundos, o más de 10 pueden pasar dos cosas: o la tarea no es viable en multiproceso, o estamos haciendo algo mal.
• ¿Es viable el multiproceso? Hay tareas que tardan tan poco que no merece la pena ponerse a paralelizarlas. O, al menos, complicarnos la vida para ello. Es decir, muchas veces, para paralelizar una tarea, tenemos que preparar los datos datos, realizar el procesamiento y reorganizar los datos de nuevo. Así que el hecho de preparar los datos y reorganizarlos, no debe invertir mucho tiempo. Como ejemplos de esto, podemos pensar, en calcular un sumatorio, debemos reservar memoria para hacer sumas parciales y definir qué parte calculará cada hilo. Cuando termine el procesamiento debemos sumar todas las sumas parciales. Vemos que el proceso se complica un poco, así que, en operaciones muy sencillas y rápidas, tal vez la preparación y reorganización tarden mucho en comparación con el cálculo y estaremos perdiendo tiempo.

Hilos y núcleos

Para realizar el reparto de tareas, vamos a crear varios hilos de ejecución en nuestro programa. El sistema operativo se va a encargar de repartir estos hilos entre los núcleos o cores de nuestra CPU (o los hilos que sea capaz de ejecutar, porque muchas CPUs pueden correr dos hilos por cada core. A lo mejor no son dos hilos simultáneos simultáneos, pero casi). Aunque, por ejemplo si nuestro ordenador puede ejecutar 4 hilos a la vez, como poder, podemos lanzar 10 o 12 hilos. En este caso, esos 12 hilos se van repartiendo el tiempo en los 4 núcleos y, si la tarea a realizar es muy pesada, puede que el multiprocesamiento nos haga perder tiempo.

De toda la vida de la informática, o gran parte de ella, hemos tenido un núcleo y ese núcleo ha tenido que ejecutar cientos de tareas pequeñas. El núcleo se las ha repartido para que parezca que se ejecutan a la vez. Si tenemos 4 núcleos, los 4 se repartirán las tareas.

Repartir tareas entre hilos

Existen muchas técnicas para el multiprocesamiento. Por ejemplo, cuando tenemos un servidor (web, base de datos, ftp, etc), normalmente se crearán varios hilos dependiendo de las peticiones que vayan entrando. O puede que necesitemos varios hilos corriendo constantemente generando y recibiendo datos a la vez.

Aunque en este post me voy a centrar en bucles, tareas que podemos hacer de forma iterativa, de las que conocemos su inicio y su final. Y por eso los ejemplos sobre compresión y cálculos. Procesos del tipo: tengo que dar 100 iteraciones, del 0 al 99 y tengo 4 núcleos:

• núcleo0, tú darás darás las 25 primeras, del 0 al 24 (for i=0;i
• núcleo1, las siguientes 25, del 25, al 49 (for i=25;i
• núcleo2, las siguientes, del 50 al 74 (for i=50;i
• núcleo3, las restantes, del 75 al 99 (for i=75;i

Por lo que ahora, el inicio y el fin del bucle tendremos que calcularlo en función del número de hilos que vayamos a lanzar, no es difícil, ni pesado, pero ya estamos haciendo cosas que antes no hacíamos.

Si, por ejemplo tenemos un bucle for que se inicia en 0 y finaliza en n, cada hilo tendrá su propio bucle for desde:

y terminará en:

Por supuesto, dadas estas fórmulas, cada hilo sabe qué número de hilo es y cuántos vecinos tiene en ese procesamiento. Y así, sustituyendo, n=100, totalHilos=4 e hilo, dependiendo del hilo actual por 0,1,2,3 nos saldrán los números de antes. Ya de manera general, si tenemos un inicio que no es 0, llamémosle xi y un fin xf, podemos decir, de manera general que:

Donde siempre podemos coger, sacar (xf-xi), llamarlo n y nos queda algo muy parecido a lo de antes.

Uso de bibliotecas

¡Cómo no! Hay herramientas que permiten hacer esto en muchos lenguajes, por ejemplo, ya que estamos con C++, tenemos OpenMP capaz de hacer muchas cosas. Pero hoy vamos a centrarnos un poco en teoría, matemáticas y cómo funciona todo esto.

¡Ejemplos, ejemplos!

Cálculo de PI

Para los ejemplos voy a utilizar C++11, más que nada porque no tenemos que liar mucho jaleo para hacer threads. Empecemos calculando el número Pi con la fórmula:

Este ejemplo tal vez tendría más sentido si utilizáramos precisión arbitraria, aunque como ejercicio no viene mal.
Para compilar este ejemplo debemos hacer:

g++ -o pi pi.cpp -std=c++11 -lpthread

Modificando una imagen jpeg

Para terminar, vamos a modificar el brillo y contraste de una imagen de una imagen por componentes. Pudiendo aumentar brillo y contraste de rojos, verdes o azules por separado. Utilizaré el ejemplo del post del enlace, aunque añadiré algunas modificaciones para hacerlo multihilo.

He de decir que no he optimizado mucho el código, por lo que, seguro que trabajando un poco más en él se pueden conseguir mejores resultados. Además, hay que tener en cuenta que la lectura y escritura del fichero de imagen no es multiproceso por lo que esto es un tiempo fijo que nuestro programa tiene que invertir.

Para compilar debemos hacer:

También podría interesarte...