Programación paralela, introducción #1

Holaaaaaaa, soy yo otra vez, pero con un nuevo tema “Programación paralela”, estoy estudiándola en la fecha de haber escrito este post para mi máster. Así que no hay mejor forma de aprender que escribir uno mismo de lo aprendido

¿Por qué existe HPC? 🚀

HPC (High Performance Computing) es la palabra elegante para decir que son “supercomputadores y clústeres en centros de investigación, empresas y universidades”. Pero el objetivo de fondo no es tan distinto de programar en tu laptop, quieres el mismo resultado, solo que usando muchos procesadores o núcleos a la vez, para llegar antes o para poder resolver algo que un solo procesador ni siquiera podría intentar (por tiempo, o directamente por falta de memoria).

¿Cuándo hace falta de verdad? Básicamente en tres casos, cuando lo que necesitás computar se pasa de lo que da una desktop normal, cuando el problema exige modelos matemáticos más precisos (y por lo tanto más caros en cómputo, memoria y disco), o cuando el resultado solo sirve si llega a tiempo (una predicción del clima a 24 horas que tarda 3 días en calcularse no le sirve a nadie).

Hay incluso un grupo de problemas, las Grand Challenge applications, que solo se pueden abordar en sistemas HPC, dinámica molecular a gran escala, simulación climática global, ese tipo de cosas. Los dos obstáculos de siempre para meterse ahí son el acceso a esas máquinas y la dificultad de programarlas. Paralelizar te obliga a pensar distinto, no es solo “el mismo código pero más rápido”.

La mayoría de las aplicaciones reales de HPC son modelado y simulación, automoción, industria naval y aeroespacial, ingeniería estructural, simulación de combustiones, mecánica de fluidos, química computacional, bioinformática, predicción meteorológica, sismología, diseño de circuitos. Y debajo de todo eso hay un puñado de algoritmos que se repiten una y otra vez, así que vale la pena reconocerlos, simulaciones de Montecarlo, problemas N-body, la FFT, particionamiento de grafos, algoritmos genéticos, álgebra matricial densa y dispersa.

Un dato random pero interesante, existe el TOP500, un ranking de los supercomputadores más potentes del planeta. Lo que importa ahí no es tanto quién está primero, sino la tendencia, cada vez pesa más la industria y los servicios web frente al uso puramente académico de hace una década. HPC dejó de ser solo cosa de laboratorios de física.

Ahora, tranquilo, la inmensa mayoría de los problemas que vas a resolver en tu vida no necesitan nada del TOP500, a menos que seas un investigador, ojo, aquí nadie limita a nadie.

Pero en realidad un clúster multicore chiquito, de pocos nodos con varios núcleos cada uno, es la arquitectura HPC con la que te vas a topar de verdad en el día a día.

Dos arquitecturas de HPC 🏗️

Bueno, para simplificar muchas cosas, podemos englobar el mundo del HPC en 2 arquitecturas basadas en cómo tienen que comunicarse los procesadores entre sí, ¿todos ven la misma memoria, o cada uno tiene la suya?

flowchart LR
    subgraph SC["🟢 Memoria compartida"]
        direction TB
        P0[P0] --- M1[(memoria compartida)]
        P1[P1] --- M1
        P2[P2] --- M1
        P3[P3] --- M1
    end
    subgraph SD["🔴 Memoria distribuida"]
        direction TB
        Q0[P0] --- L0[(mem. local)]
        Q1[P1] --- L1[(mem. local)]
        Q2[P2] --- L2[(mem. local)]
        Q3[P3] --- L3[(mem. local)]
        Q0 <--> RED[red de interconexión]
        Q1 <--> RED
        Q2 <--> RED
        Q3 <--> RED
    end

    classDef proc fill:#dcefdd,stroke:#1f5c2e,color:#1f5c2e,font-weight:bold;
    classDef mem fill:#4a8f57,stroke:#1f5c2e,color:#ffffff,font-weight:bold;
    classDef dproc fill:#fbd8d3,stroke:#8a241b,color:#8a241b,font-weight:bold;
    classDef dmem fill:#c0392b,stroke:#8a241b,color:#ffffff,font-weight:bold;
    class P0,P1,P2,P3 proc
    class M1 mem
    class Q0,Q1,Q2,Q3 dproc
    class RED,L0,L1,L2,L3 dmem
    style SC fill:#f2faf3,stroke:#4a8f57
    style SD fill:#fdf3f2,stroke:#c0392b

En memoria compartida (multiprocesadores, hoy en día básicamente cualquier CPU multicore), todos los procesadores ven un único espacio de direcciones. No hay que distribuir nada, te comunicás implícitamente, leyendo y escribiendo variables compartidas. La contra es que tenés que sincronizar a mano (semáforos, secciones críticas, barreras) para que los accesos concurrentes no se pisen entre sí.

En memoria distribuida (multicomputadores, hoy en día clústeres), cada procesador tiene su propio espacio de direcciones, privado. Tenés que repartir los datos vos mismo entre las memorias locales, y saber en todo momento dónde está cada cosa (eso se llama explotar la localidad). La comunicación es explícita, por mensajes, lo cual es más trabajo de programar, pero la sincronización te sale casi gratis porque va implícita en el propio mensaje.

La regla mental que me quedó grabada al estudiar este tema es muy básica, comunicación fácil pero sincronización manual, distribuida es sincronización casi gratis pero comunicación manual.

Okay ahora podemos decir a muyyy groso modo que todas las demás arquitecturas de HPC (híbrido, PGAS, data-parallel) son variaciones o mezclas de estas dos ideas.

Las cuatro fases de diseñar algo paralelo 🪜

Para mí esto es algo nuevo. A ver, vengo de programar en Go concurrencia pero no grandes sistemas de cómputos distribuidos con memorias compartidas y demás, así que realmente es algo secuencial la programación que hago a diario, y no sabía que había unas normas de diseño.

Bueno, en fin, no importa qué paradigma termines usando, diseñar un programa paralelo siempre pasa por estas cuatro decisiones, en este orden.

flowchart TD
    A["🔪 1. Descomposición
    dividir el cómputo en tareas"] --> B["📦 2. Asignación
    estática o dinámica"]
    B --> C["🔗 3. Coordinación
    comunicación y sincronización"]
    C --> D["🗺️ 4. Mapeo
    qué proceso corre en qué núcleo"]

    classDef fase fill:#dcefdd,stroke:#1f5c2e,color:#1f5c2e,font-weight:bold;
    class A,B,C,D fase

Descomposición. Dividir el cómputo secuencial en tareas repartibles. El objetivo es el balanceo de carga, que ningún procesador se quede esperando mientras otro sigue trabajando.

Asignación. Cómo repartís esas tareas entre procesos o threads. Puede ser estática (se decide antes de correr, más simple) o dinámica (se decide en tiempo de ejecución, mejor cuando la carga es irregular).

Coordinación. Las comunicaciones y sincronizaciones necesarias entre tareas. Regla de oro, minimizarlas, porque son puro overhead comparado con la versión secuencial.

Mapeo. Decidir qué proceso o thread corre en qué procesador físico. En la práctica casi siempre es 1:1, un proceso o thread por núcleo.

Un consejo que se repite mucho en el mundo de la programación paralela es que no intentes optimizar el programa entero por igual. Concéntrate en los hot spots, las zonas más costosas (típicamente bucles que iteran sobre montañas de datos), porque ahí es donde el paralelismo de verdad justifica el esfuerzo de programarlo.

Memoria compartida en la práctica, OpenMP 🧵

El modelo típico de programación en memoria compartida es concurrencia basada en threads, siguiendo el patrón fork-join, un thread master corre secuencial hasta que llega a una región paralela, ahí “lanza” (fork) un grupo de threads que trabajan en paralelo, y cuando todos terminan se reincorporan (join) en el master, que sigue solo hasta la próxima región paralela.

flowchart LR
    M1((master)) --> F1{fork}
    F1 --> T1[thread]
    F1 --> T2[thread]
    F1 --> T3[thread]
    T1 --> J1{join}
    T2 --> J1
    T3 --> J1
    J1 --> M2((master)) --> F2{fork}
    F2 --> T4[thread]
    F2 --> T5[thread]
    T4 --> J2{join}
    T5 --> J2
    J2 --> M3((master))

    classDef master fill:#141414,stroke:#141414,color:#ffffff,font-weight:bold;
    classDef fj fill:#c0392b,stroke:#8a241b,color:#ffffff,font-weight:bold;
    classDef thread fill:#dcefdd,stroke:#1f5c2e,color:#1f5c2e,font-weight:bold;
    class M1,M2,M3 master
    class F1,F2,J1,J2 fj
    class T1,T2,T3,T4,T5 thread

Se puede programar esto con threads nativos (Pthreads, por ejemplo en C) portable, pero de bajo nivel, y se tiene que crear, sincronizar y destruir threads a mano con llamadas a biblioteca y bla bla bla, cosas que realmente nos complican la vida. Lo bueno de todo esto es que existe una alternativa de alto nivel que prácticamente es un estándar en la industria OpenMP. Es un estándar de facto para programar sistemas de memoria compartida en Fortran, C y C++, hecho de directivas que se insertan sobre tu código secuencial sin cambiarlo casi nada. Hermoso la verdad 🤯

OpenMP se apoya en tres elementos.

• Control del paralelismo. La directiva parallel, y directivas de reparto de trabajo como for.
• Control de datos y comunicación. Las cláusulas shared y private.
• Sincronización. Barreras, secciones críticas, atomic.

Información medio importante, para tener en mente qué es OpenMP. Lo mantiene la OpenMP Architecture Review Board (fabricantes de hardware, software y centros de cómputo, AMD, ARM, Intel, IBM, entre otros), las specs son libres, no necesitás licencia, y toda la info está en openmp.org.

Cómo se ve una directiva 🔍

En C y C++, las directivas de OpenMP usan el mecanismo #pragma del propio lenguaje.

#pragma omp directiva [cláusulas]

Siempre en minúscula. Y acá viene un detalle. Si el compilador no reconoce el pragma, simplemente lo ignora. Esto pasa por tres motivos, el compilador no soporta OpenMP, te olvidaste del flag para activarlo (-fopenmp en gcc), o hay un error de tipeo (por ejemplo escribiste #pragma openmp en vez de #pragma omp). En los tres casos tu programa compila sin ningún error, pero corre completamente en secuencial. Si tu “programa paralelo” siempre actúa como si tuviera un solo thread, este es el primer sospechoso.

La mayoría de las directivas se aplican sobre un bloque estructurado. Código sin saltos que entren o salgan del bloque desde afuera (nada de goto cruzando el borde), OJO CON ESTO!!!

El modelo de memoria de OpenMP 💾

OpenMP te deja definir dos tipos de variables.

• shared. Una sola copia en memoria, visible para todos los threads.
• private. Cada thread tiene su propia copia, invisible para los demás.

Cada thread tiene también su propio stack (para guardar los argumentos y variables locales de las funciones que ese thread llama), y ahí es donde vive el espacio de las variables privadas. El tamaño de ese stack depende de la implementación, pero se puede configurar con la variable de entorno OMP_STACKSIZE.

Actualizar (escribir) una variable compartida puede salir caro si hay muchos threads de por medio, o si estás en una arquitectura NUMA y el acceso es a memoria remota de otro procesador en vez de local. Las variables privadas reducen la frecuencia con la que tienes que tocar variables compartidas (menos overhead), a costa de usar más memoria total del programa. En general conviene usar variables compartidas cuando son de solo lectura, cuando distintos threads acceden a elementos distintos de la misma variable, o cuando justamente se quiere comunicar un valor entre threads.

Un matiz importante aquí, la actualización de variables compartidas puede quedarse temporalmente en la vista privada (caché) de cada thread, así que en un momento dado dos threads podrían ver valores distintos de la misma variable compartida. OpenMP obliga a que los objetos compartidos se hagan visibles (se escriban a memoria de verdad) en los puntos de sincronización. Si un thread necesita un valor que escribió otro, tiene que haber un punto de sincronización de por medio. Para forzar esto manualmente existe la directiva flush, muy seguramente si vienes de estudiar C ya la conocías.

La directiva parallel, en detalle 🔀

#pragma omp parallel [cláusulas]
{
    /* bloque estructurado */
}

Define una región paralela. Un bloque de código que corren varios threads a la vez. Cuando un thread llega a esta directiva, crea un equipo de threads, se convierte en el master de ese equipo, y el número de threads del equipo lo decide una cláusula, la variable de entorno OMP_NUM_THREADS, o una llamada a omp_set_num_threads(). Al final de la región hay una barrera implícita, y solo el thread master sigue de largo.

double A[1000];
int ID;
omp_set_num_threads(4);

#pragma omp parallel private(ID) shared(A)
{
    ID = omp_get_thread_num();
    calcula(ID, A);
}

printf("\nfin");

Con esto se crean 4 threads dentro de la región paralela, y cada uno corre calcula con su propio ID (0, 1, 2 o 3), todos compartiendo la misma copia de A.

Las cláusulas más importantes de parallel.

• if(expresión). La región solo se ejecuta en paralelo si la expresión es verdadera.
• num_threads(n). Fija el número de threads del equipo.
• private(lista). Cada thread tiene su copia local, sin inicializar, de esas variables.
• firstprivate(lista). Igual que private, pero la copia arranca con el valor que tenía antes de entrar a la región.
• shared(lista). Una sola copia, visible por todos, sin exclusión mutua garantizada (eso es responsabilidad tuya).
• default(shared | none). Define el comportamiento por defecto. Con none te obliga a especificar explícitamente el tipo de cada variable, cosa que en general es buena idea porque te fuerza a pensar en cada una.
• reduction(operador:lista). Ya la vas a ver en detalle en el próximo post.
• copyin(lista). Para variables threadprivate, no la vas a necesitar seguido.

Por defecto, los datos globales, estáticos y con duración dinámica son shared, las variables locales son private, y el índice de un bucle asociado a un for (o parallel for) siempre es private. Aun así, se recomienda mucho especificar explícitamente el tipo de cada variable en vez de confiar en el valor por defecto.

Si un thread de un equipo que ya está corriendo una región paralela encuentra otra región paralela adentro, crea un nuevo equipo y se vuelve su master (esto se llama paralelismo anidado). Por defecto, las regiones anidadas vienen serializadas, el nuevo equipo tiene un solo thread, pero se puede cambiar con OMP_NESTED o omp_set_nested().

Compilando y corriendo en Ubuntu 🐧

Antes de tocar código, en Ubuntu (o cualquier Debian-like) el compilador estándar es GCC, y ya trae soporte para OpenMP integrado hace muchísimas versiones. No hay que instalar ninguna librería aparte, solo agregar un flag.

Primero, revisá qué compilador tenés.

gcc --version
g++ --version

Si te aparece algo tipo gcc (Ubuntu 13.2.0-...) 13.2.0, ya tienes compilador de C y C++!!! Genial. Si te dice command not found, instalá el paquete que trae ambos de una.

sudo apt update
sudo apt install build-essential

build-essential te instala gcc, g++, make y las cabeceras estándar de C/C++.

Después, confirmá que ese compilador de verdad soporta OpenMP.

echo | gcc -fopenmp -dM -E - | grep _OPENMP

Debería imprimir algo como #define _OPENMP 201511 (ese número es la fecha, año-mes, de la versión del estándar que soporta, 201511 es OpenMP 4.5). Si no imprime nada, ese gcc se compiló sin soporte OpenMP, algo bastante raro en Ubuntu.

Fijate cuántos núcleos tiene tu máquina, porque ese número es en la práctica el límite de threads con el que tiene sentido probar tus programas.

nproc

Y estas son las cuatro líneas que vas a reutilizar para todos los ejemplos de esta serie.

gcc  -fopenmp -O2 fichero.c   -o programa     # compilar C
g++  -fopenmp -O2 fichero.cpp -o programa     # compilar C++
OMP_NUM_THREADS=4 ./programa                  # ejecutar forzando 4 threads
./programa                                    # ejecutar usando todos los núcleos disponibles

El error más común al empezar. Olvidarse del -fopenmp. El programa compila sin ningún error (el compilador ignora los #pragma omp que no reconoce), pero corre completamente en secuencial. Si tu programa “paralelo” siempre imprime que hay un solo thread corriendo, revisá ese flag antes que nada.

Hola mundo, con threads 👋

Mucha teoría y poca práctica, mejor cerremos con el ejemplo obligatorio en cualquier lenguaje, un Hola mundo, pero una región paralela que identifica a cada thread.

#include <stdio.h>
#include <omp.h>

int main(void) {
    #pragma omp parallel
    {
        int id       = omp_get_thread_num();
        int nthreads = omp_get_num_threads();
        printf("Hilo %d de %d: Hola mundo!\n", id, nthreads);
    }
    return 0;
}
/* salida (orden no determinista):
   Hilo 2 de 4: Hola mundo!
   Hilo 0 de 4: Hola mundo!
   Hilo 3 de 4: Hola mundo!
   Hilo 1 de 4: Hola mundo!            */

Esto es exactamente el fork-join de más arriba. Hasta el #pragma omp parallel hay un solo hilo (el master) corriendo main secuencial. Ahí se crean los threads adicionales (por defecto tantos como núcleos tenga la máquina, salvo que hayas fijado OMP_NUM_THREADS o num_threads(n)), y todos, incluido el master, corren una copia del bloque. Al llegar a la llave de cierre, los threads adicionales se destruyen y volvés a tener un solo hilo de control.

Dos cosas que sorprenden la primera vez, el orden de salida no está garantizado (el sistema operativo decide en qué orden corre cada thread, así que cada corrida puede imprimir en un orden distinto), y en teoría, si varios threads llaman a printf casi al mismo tiempo, el output podría entrelazarse carácter a carácter. En la práctica la mayoría de las libc protegen cada llamada a printf como una unidad, pero eso es garantía de la implementación de entrada/salida del sistema, no del estándar de OpenMP.

Con esto ya tenemos más o menos una idea, sabemos por qué existe HPC y cómo programar con OpenMP. Falta bastante, pero es un buen comienzo.

La canción del post

QUÉ BUENA CANCIÓN PARA COMENZAR ALGO, YA NO DIRÉ MÁS NADA, ES MUY BUENA.

Last Nite
· The Strokes