Computación paralela

La ley de Moore

Procesadores con multiples núcleos (cores)

Clusters y supercomputadores

  • En el cluster del IFA, Kosmos, hay $\sim 500$ cores disponibles.
  • En supercomputadores modernos típicamente hay miles y miles de cores (Guacolda-Leftraru tiene 5236 CPU cores).
  • El computador Fugaku (en Japón) es el más poderoso en el mundo por ahora, con más que 7,6 millones de cores. (Top500)
Kosmos (IFA)
Guacolda-Leftraru (NLHPC/UChile)

Programación Tradicional

Programación en Paralelo

La jerga del paralelismo

Proceso: algo que se ejecuta en el sistema. Podría ser un browser, Skype, un videojuego, un terminal de Python, un script de Python, etc.

La jerga del paralelismo

Hilo (Thread): un subproceso comenzado por algún proceso controlador. Por ejemplo, un script de Python podría usar varios hilos durante su ejecución.

La jerga del paralelismo

Memoria compartida: una arquitectura donde cada unidad de procesamiento accede al mismo bloque de memoria global.

La jerga del paralelismo

Memoria distribuida: una arquitectura donde cada unidad de procesamiento tiene su propio bloque de memoria.

Las unidades se comunican mediante una red (network).

Tipos de paralelismo

  • Multiproceso: se divide el problema en varios procesos que comunican entre si.
  • Multihilo (multithread): hay un proceso, que puede usar varios threads durante su ejecucion para trabajar en paralelo.
  • Muchos algorítmos para procesamiento paralelo ocupan una mezcla de los dos tipos.
  • Hay una relación entre el tipo de paralelismo y la arquitectura de la memoria...

Memoria para procesos

  • Un proceso: basicamente un programa que se ejecuta en el sistema.
  • Cada proceso tiene acceso a la memoria que el sistema asigna.
  • Típicamente el bloque de memoria asignada al proceso pertenece exclusivamente al proceso - los otros procesos en el sistema no lo pueden acceder.

Paralelismo multi-proceso

  • Hay multiples "versiones" de un sólo programa (procesos multiples).
  • Cada proceso corre en uno de los procesadores (cores).
  • Ya que cada proceso tiene su bloque exclusivo de memoria, tiene sentido que este tipo de paralelismo se ocupa con memoria distribuida.

Paralelismo multithread (multi-hilo)

  • Un proceso lanza multiples threads (hilos) de ejecución.
  • Cada procesador (core) ejecuta un subconjunto de los hilos.
  • Ya que todos los hilos tienen acceso al bloque de memoria "global" del proceso, tiene sentido usar memoria compartida para procesamiento multi-hilo.

Paralelismo mezclado

  • La mayoría de los supercomputadores hoy en día tienen las dos arquitecturas de memoria.
  • Los cores están organizados en nodos (con memoria compartida). La memoria para los nodos está distribuida.
  • De hecho, se puede correr cualquier tipo de proceso paralelo en cualquier tipo de arquitectura (pero posiblemente con menos eficiencia).

Ejemplo: paralelismo multiproceso

Ahora vamos a ver un ejemplo de la idea de paralelismo multiproceso en una simulación del clima.

Simulaciones del clima

  • En la simulación hay una malla esférica en $3D$.
  • En cada "celda" de la malla el programa calcula presión, densidad, temperatura, etc.
  • Las simulaciones modernas incluyen cálculos de procesos que ocurren a escalas mucho menor que la escala de cada celda.
  • Veremos mucho más sobre simulaciones más tarde...

Simulaciones del clima

  • Típicamente la malla computacional tendrá $1.5$ millones de puntos (celda de área $100$ km$^2$, $30$ capas de la atmósfera).
  • La simulación tiene que calcular el estado de la atmósfera en cada uno de estos puntos para $100$ años (de tiempo en la simulación), en intervalos de $30$ minutos.

$\Rightarrow$ $1.7$ millones de pasos en el tiempo...

$\Rightarrow$ $2.5 \times 10^{12}$ cálculos...

  • Aún si cada cálculo demora $1$ microsegundo (optimista, dado la complejidad de las ecuaciones) la simulación demorará $\sim 30$ días corriendo en un procesador.
  • Además, no estamos tomando en cuenta los requirimientos de memoria...

Simulaciones del clima

  • Para acelerar la simulación, usamos paralelismo.
  • En el caso de paralelismo multi-proceso, tenemos varias copias del programa que hace la simulación, pero donde cada copia se ocupa de solamente una parte de la malla total.

Simulaciones del clima

  • Por ejemplo, si usamos $50$ procesadores, podemos dividir la malla en $30.000$ puntos por procesador (y $1.7$ millones de pasos en el tiempo, como antes).
  • Así que, cada procesador hace una tarea un poco menos exigente - una división del trabajo.

Pasos para correr la simulación en paralelo

  1. Se ejecuta el programa que hace la simulación: el primer proceso, que corre en uno de los procesadores.
  2. El proceso $1$ divida la malla en sub-mallas. Esta división parece fácil, pero puede ser muy difícil encontrar la división que es la más eficiente (primer gran desafio del paralelismo).
  3. $49$ otros procesos están lanzados (cada uno en un procesador diferente) para hacer los cálculos en la sub-malla asignada.

La ventaja de correr la simulación en paralelo

  • Hemos dividido el trabajo entre $50$ procesadores.
  • Si la división fue óptima, en principio la simulación debería ejecutarse $50$ veces más rápido.
  • Entonces, terminará en $14$ horas, en vez de $30$ días!

Comunicación

  • ¡Ojo! Hemos olvidado algo MUY importante...
  • Cada parte de la atmósfera está conectada con otras partes: no están aislados y el aire se mueve!
  • Necesitamos comunicación entre los procesos para actualizar los valores en los bordes de las sub-mallas

Comunicación

  • El segundo gran desafio del paralelismo: comunicación entre los procesos/hilos.
  • En este ejemplo, podemos escribir en el programa que cada proceso tiene que compartir los resultados en el borde de la sub-malla con todas las sub-mallas vecinas, en cada paso del tiempo.
  • Típicamente eso se hace con librerías específicas para el paralelismo (MPI, OpenMP, etc.)
  • Hay lenguajes de programación paralela que intentan simplificar la parte de comunicación (e.g. Co-array Fortran, Parallel C, Chapel, etc.)
  • Mucho más sobre este en el curso de Programación Paralela!

Para terminar de correr la simulación en paralelo

  1. Los resultados de todos los procesadores están reunidos en procesador $1$ por el proceso $1$ (usando comunicación entre los procesos).
  2. Luego, proceso $1$ puede guardar los resultados en un archivo en el disco duro.

Resumen

  • La rapidez de un core no está creciendo mucho actualmente, pero hoy en día los CPUs tienen muchos.
  • Por lo tanto, hay que saber como diseñar algoritmos paralelos.
  • Hay dos métodos principales: multi-proceso (memoria distribuida) y multi-hilo (memoria compartida).
  • En el área de computación científica, la programación paralela es conocimiento esencial!